Алгоритм шифрования MARS

2. Алгоритм шифрования MARS

Коропорация IBM, создавшая DES, представила алгоритм MARS, обладающий как хорошей криптостойкостью так и высокой скоростью шифрования.

Процесс шифрования состоит из трех стадий: прямого и обратного перемешивания, которые оборачивают шифрование и состоят из 8 раундов, и 16 раундового шифрования. Обратное перемешивание производят для более быстрого достижение лавинного эффекта и нарушения симметричности при перемешивании. Стадии прямого и обратного перемешивания инвертированы относительно друг друга.

Перед прямым перемешиванием происходит входное забеливание (добавление к входному блоку ключей). Далее в течение 8 раундов производится перемешивание без использования ключа. На стадии перемешивания используются операции битового сдвига, исключающего "ИЛИ", сложения и Sbox'ы.

Рис. 2.1 Схема алгоритма MARS

Непосредственное шифрование представляет собой сеть Фейстеля с 4 ветвями. От первой ветви вычисляется функция F. На вход функции F подается 32 битное слово, функция выдает на выход три 32 битных слова. Полученные слова складываются с тремя оставшимися ветвями, далее выполняется перестановка ветвей. Структура функции представлена на рис. 2.2

Рис 2.2 Структура функции зашифрования и расшифрования алгоритма MARS

B первых восьми раундах производится прямое шифрование, в следующих восьми раундах обратное. Прямое и обратное шифрование отличаются порядком функций, выполняемых над выходами функции F.

MARS поддерживает переменную длину ключа от 128 до 448 битов, используя процедуру расширения входного ключа до 40 32-битовых слов, которые используются при шифровании и дешифровании.

Одним из недостатков алгоритма является сложность его криптоанализа из-за использования двойного перемешивания. Алгоритм показал хорошую скорость шифрования. Скорость шифрования на Intel-Pentium 200 МГц достигала 65 Мбит/с, скорость выполнения блока прямого и обратного шифрования достигала 100 Мбит/с.

3. Алгоритм шифрования RC4

Алгоритм RC4 состоит из трех частей:

Создание ключа (иногда называют - расширение ключа).

Алгоритм шифрования.

Алгоритм расшифровки.

Создание ключа

Ключ в RC4 представляет собой последовательность байтов произвольной длинны, по которой строится начальное состояние шифра S - перестановка всех 256 байтов. Алгоритм получения начального состояния изображен на рис.3.1.

Рис 3.1 Алгоритм получения начального состояния шифра RC4

Первоначально S заполняется последовательными значениями от 0...255. Затем каждый очередной элемент S обменивается местами с элементом , номер которого определяется элементом ключа K, самим элементом и суммой номеров элементов, с которыми происходил об мен на предыдущих итерациях.

Значения счетчиков i и с изначально равны 0. Сплошные стрелки означают передачу значений между элементами схемы ( присваивание ), двусторонние стрелки - обмен значениями, пунктирные стрелки - индексацию в массиве.

Алгоритм шифрования.

Алгоритм схематически изображен на рис. 3.2.

Рис 3.2 Алгоритм шифрования RC4

Очередной элемент псевдослучайной перестановки S всех байтов обменивается с другим, номер которого равен сумме элементов, выбрнных на предыдущих шагах. В качестве очередного байта выдается значение третьего элемента S, номер которого равен сумме первых двух. Значение счетчика x первоначально равно 0, но оно увеличивается на 1 уже перед первой выборкой S(x). Значение y первоначально равно 0. Но затем высчитывается как элемент ключа по номеру x + предыдущее значение y и вся сумма по mod 256.

Некоторые полезные свойства алгоритма RC4.

Преобразование очередного состояния генератора (S,x,y) обратимо, так что все возможные состояния повторяются с одинаковой частотой с некоторым периодом.

Поскольку S содержит каждый байт ровно один раз, маловероятно, что одни байты будут выдаваться в качестве результата чаще, чем другие.

4. Алгоритм шифрования RC5

RC5 представляет собой блочный фильтр с большим числом параметров: размером блока, размером ключа и количеством этапов. Он был изобретен Роном Ривестом и проанализирован в RSA Laboratories [1324, 1325].

Используется три действия: XOR, сложение и циклические сдвиги. На большинстве процессоров операции циклического сдвига выполняются за постоянное время, переменные циклические сдвиги являются нелинейной функцией. Эти циклические сдвиги, зависящие и от ключа, и от данных, представляют собой интересную оп е-рацию.

RC5 использует блок переменной длины, но в приводимом примере мы остановимся на 64-битовом блоке данных. Шифрование использует 2r+2 зависящих от ключа 32-битовых слов - So, Si, S2, ... S2r+i – где r - число этапов. Эти слова мы сгенерируем позднее. Для шифрования сначала блок открытого текста делится на два 32-битовых слова: А и В. (RC5 предполагает следующее соглашение по упаковке байтов в слова: первый байт занимает младшие биты регистра А, и т.д.) Затем:

A=A + S0

B = B + S1

For i = 1 to r:

A = ((AÅ B) <« B) + S2i

В = ((В Å A) <« A) + S2i+1

Результат находится в регистрах А и В.

Дешифрирование также просто. Блок открытого текста разбивается на два слова, А и В, а затем:

For i = r down to 1:

B = ((B-S2i+1)>>>A) Å A

A = ((A-S2i)>>>B) Å B

B = B – S1

A=A - S0

Символ ">>>" обозначает циклический сдвиг направо. Конечно же, все сложения и вычитания выполняются по модулю 232.

Создание массива ключей более сложно, но также прямолинейно. Сначала, байты ключа копируются в ма с-сив L из с 32-битовых слов, дополняя при необходимости заключительное слово нулями. Затем массив S инициализируется при помощи линейного конгруэнтного генератора по модулю 232:

S = P

For I =1 to 2(r+1)-1

Si = (Si-1 + Q) mod 232

P = 0xb7el5163 и Q = 0х9е377989, эти константы основываются на двоичном представлении е и phi. Наконец, подставляем L в S:

i=j = 0

А=В = 0

выполнить п раз (где п - максимум 2(r + 1) и с):

А = Si = (Si + А+ В)<<<3

B = Li = (Li +A+B) <<< (А + В) ;

i = (i+1) mod 2(r+l)

j = (j + 1 ) mod с

По сути, RC5 представляет собой семейство алгоритмов. Только что мы определили RC5 с 32-битовым cл овом и 64-битовым блоком, не существует причин, запрещающих использовать тот же алгоритм с 64-битовым словом и 128-битовым. Для w = 64, Р и Q равны 0xb7el51628aed2a6b и 0x9e3779b97f4a7cl5, соответственно. Ривест обозначил различные реализации RC5 как RC5- wlrlb, где w - это размер слова, r - число этапов, а b -длина ключа в байтах.

RC5 является новым алгоритмом, но RSA Laboratories потрптила достаточно много времени, анализируя его работу с 64-битовым блоком. После 5 этапов статистика выглядит очень хорошо. После 8 этапов каждый бит открытого текста влияет по крайней мере на один циклический сдвиг. Дифференциальное вскрытие требует 2 24 выбранных открытых текстов для 5 этапов, 245 для 10 этапов, 253 для 12 этапов и 268 для 15 этапов. Конечно же, существует только 264 возможных открытых текстов, поэтому такое вскрытие неприменимо против алгоритма с 15 и более этапами. Оценка для линейного криптоанализа показывает, что алгоритм безопасен после 6 этапов. Ривест рекомендует использовать не меньше 12 этапов, а лучше 16 [1325]. Это число может меняться.

RSADSI в настоящее время патентует RC5, а это названия заявлено, как торговая марка. Компания утверждает, что плата за лицензирование будет очень мала, но это лучше проверить.