Алгоритмы блочного шифрования

a + b целочисленное сложение по модулю 2^w;

a b целочисленное вычитание по модулю 2^w;

a b побитовое "исключающее ИЛИ" w-битовых слов;

a ? b целочисленное умножение по модулю 2^w;

a << b циклический сдвиг w-битового слова влево на величину, заданную log₂ w младшими битами b;

a >> b циклический сдвиг w-битового слова вправо на величину, заданную log₂ w младшими битами b;

Шифрование при помощи RC6w/r/b описывается следующим образом:

Вход: Исходный текст, записанный в 4 w-битовых входных регистрах A, B, C, D;

Число циклов шифрования r;

Ключевая таблица S[0; ... 2r + 3] w-битовых слов

Выход: Шифрованный текст в регистрах A, B, C, D.

Процедура:

B = B + S[0]

D = D + S[1]

for i = 1 to r do {

t = (B ? (2B + 1)) << log₂ w

u = (D ? (2D + 1)) << log₂ w

A = ((A t) << u) + S[2i]

C = ((C u) << t) + S[2i + 1]

(A; B; C; D) = (B; C; D; A)

}

A = A + S[2r + 2]

C = C + S[2r + 3]

Расшифрование в этих обозначениях выглядит очень похоже:

Вход: Шифрованный текст, записанный в 4 w-битовых входных регистраx A,B,C,D;

Число циклов шифрования r;

Ключевая таблица S[0;... 2r + 3] w-битовых слов.

Выход: Исходный текст в регистрах A, B, C, D.

Процедура:

C = C S[2r + 3]

A = A S[2r + 2]

for i = r downto 1 do {

(A; B; C; D) = (D; A; B; C)

u = (D ? (2D + 1)) << log₂ w

t = (B ? (2B + 1)) << log₂ w

C = ((C S[2i + 1]) >> t) u

A = ((A S[2i]) >> u) t

}

D = D S[1]

B = B S[0]

Алгоритм вычисления ключей для RC6-w/r/b выглядит следующим образом:

Пользователь задает ключ длиной b байтов. Достаточное число ненулевых байтов дописываются в конец, чтобы получилось целое число слов. Затем эти байты записываются начиная с младшего в массив из с слов, т.е. первый байт ключа записывается в L[0], и т.д., а L[c 1] при необходимости дополняется со стороны старших разрядов нулевыми байтами. В результате работы алгоритма генерации ключей будет вычислено 2r+ 4 слов, которые будут записаны в массиве S[0;...; 2r + 3].

Константы P₃₂ = B7E15163h and Q₃₂ = 9E3779B9h это константы, получаемые из двоичного представления e2, где e основание натуральных логарифмов, и ?1, где ? золотое сечение, соответственно. Подобные же константы могут быть аналогичным образом получены и для RC6 с другим размером слова. Выбор констант является в некотором роде произвольным, и поэтому можно использовать и другие константы, получая при этом "частные" версии алгоритма.

Вход: Определенный пользователем b-байтовый ключ, предварительно загруженный в массив L[0; ... c 1];

Число циклов шифрования r.

Выход: Ключевая таблица S[0; ... 2r +4] из w-битовых слов.

Процедура:

S[0] = P_w

for i = 1 to 2r + 3 do

S[i] = S[i 1] + Q_w

A = B = i = j = 0

v = 3 ? max{c, 2r + 4}

for s = 1 to v do {

A = S[i] = (S[i] + A + B) << 3

B = L[j] = (L[j] + A + B) << (A + B)

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

j = (j + 1) mod c

}

Структура шифра RC6 является обобщением сети Фейстела. Блок текста разбивается не на 2, а на 4 подблока, и на каждой итерации изменяются 2 подблока из четырех. При этом в конце итерации шифрования производится циклический сдвиг подблоков влево (при расшифровании, соответственно, вправо). Однако, такое обобщение привело к тому, что было утеряно свойство инвариантности блоков шифрования и расшифрования, хотя это и не является определяющим в оценке данного алгоритма.

3.4 Российский стандарт шифрования ГОСТ 28147-89

В Российской Федерации установлен единый стандарт криптографического преобразования текста для информационных систем. Он носит обязательный характер для государственных органов, организаций, предприятий, банковских и иных учреждений, чья деятельность связана с обеспечением информационной безопасности государства. Рекомендован к использованию для защиты любых данных, представленных в виде двоичного кода, хотя не исключаются и другие методы шифрования.

Данный стандарт формировался с учетом мирового опыта и, в частности, были приняты во внимание недостатки и нереализованные возможности алгоритма DES, поэтому использование стандарта ГОСТ предпочтительнее. Алгоритм построен с использованием сети Фейстела.

Рис. 3.2. Алгоритм шифрования ГОСТ 28147-89

Режим простой замены

Введем ассоциативную операцию конкатенации, используя для нее мультипликативную запись. Кроме того будем использовать следующие операции сложения:

A B побитовое сложение по модулю 2;

A [+] B сложение по модулю 2³²;

A {+} B сложение по модулю 2³²1;.

Алгоритм криптографического преобразования предусматривает несколько режимов работы. Во всех режимах используется ключ W длиной 256 бит, представляемый в виде восьми 32-разрядных чисел X(i).

W = X(7)X(6)X(5)X(4)X(3)X(2)X(1)X(0)

Для расшифрования используется тот же ключ, но процесс расшифрования является инверсным по отношению к исходному.

Базовым режимом работы алгоритма является режим простой замены.

Пусть открытые блоки разбиты на блоки по 64 бит в каждом, которые обозначим как T₀.

Очередная последовательность бит T₀ разделяется на две последовательности B(0) и A(0) по 32 бита (левый и правый блоки). Далее выполняется итеративный процесс шифрования, описываемый следующими формулами:

для i = 1?24

для i = 25?31

и для i = 32

Здесь i обозначает номер итерации. Заметим, что подобно DES, на последнем цикле перестановка половин блока не производится.

Функция шифрования включает две операции над 32-разрядным аргументом K() и R().

Первая операция является подстановкой. Блок подстановки K состоит из 8 узлов замены K(1)...K(8) с памятью по 64 бита каждый. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4-разрядных вектора, каждый из который преобразуется в 4-разрядный вектор соответствующим узлом замены, представляющим из себя таблицу из 16 целых чисел в диапазоне 0...15. Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем полученные 4-разрядные векторы вновь последовательно объединяются в 32-разрядный выходной. ГОСТ 28147-89 в явном виде не указывает таблицы подстановок.

Вторая операция циклический сдвиг 32-разрядного вектора, полученного в результате подстановки K на 11 шагов влево.

64-разрядный блок зашифрованных данных Т_ш представляется в виде

Т_ш = А(32)В(32).

Остальные блоки открытых данных в режиме простой замены зашифровываются аналогично.

Следует учитывать, что данный режим шифрования рекомендуется использовать только для шифрования ключевой информации. Для шифрования данных следует использовать два других режима.

Второй режим шифрования называется режимом гаммирования.

Открытые данные, разбитые на 64-разрядные блоки T_O⁽ⁱ⁾ (i=1,2,...,m), где m определяется объемом шифруемых данных, зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 с гаммой шифра ?_Ш, которая вырабатывается блоками по 64 бита, т.е.

Г_Ш=(Г_Ш⁽¹⁾,…,Г_Ш^(m)).

Уравнение шифрования данных в режиме гаммирования может быть представлено в следующем виде:

Т_Ш⁽ⁱ⁾=Г_Ш⁽ⁱ⁾ T_O⁽ⁱ⁾=E_K(Y_i-1[+]C₂,Z_i-1{+}C₁)T⁽ⁱ⁾_O).

В этом уравнении T⁽ⁱ⁾_Ш обозначает 64-разрядный блок зашифрованного текста, E_K функцию шифрования в режиме простой замены (аргументами этой функции являются два 32-разрядных числа). С₁ =01010104h и С₂ = 01010101h константы, заданные в ГОСТ 28147-89. Величины Y_i и Z_i определяются итерационно по мере формирования гаммы следующим образом:

(Y₀, Z₀) = E_K(S),

где S 64-разрядная двоичная последовательность;

(Y_i, Z_i) = (Y_i-1 [+] C₂, Z_i-1 {+} C₁), i = 1, 2, ..., m.

64-разрядная последовательность S, называемая синхропосылкой, не является секретным элементом шифра, но ее наличие необходимо как на передающей стороне, так и на приемной.

Режим гаммирования с обратной связью очень похож на режим гаммирования. Как и в последнем, разбитые на 64-разрядные блоки T_O⁽ⁱ⁾ открытые данные зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра ?_Ш, которая вырабатывается блоками по 64 бита:

Г_Ш=(Г_Ш⁽¹⁾,…,Г_Ш^(m)).

Уравнения шифрования данных в режиме гаммирования с обратной связью выглядят следующим образом:

Т_Ш⁽¹⁾=E_K(S)T_O⁽¹⁾= Г_Ш⁽¹⁾T_O⁽¹⁾

Т_Ш⁽ⁱ⁾=E_K(Т_Ш^(i-1)) T_O⁽ⁱ⁾= Г_Ш⁽ⁱ⁾T_O⁽ⁱ⁾.

Заметим, что в отличие от режима гаммирования с обратной связью, в режиме гаммирования гамма шифра не зависит от исходного текста.

3.5 Алгоритм SAFER+, SAFER++

Алгоритм SAFER+

Алгоритм SAFER+ был предложен калифорнийской корпорацией Cylink как один из кандидатов на принятие в качестве нового стандарта шифрования AES и прошел первый тур отбора. Он является примером шифра, не использующего структуру сети Фейстела. Шифр работает с блоками длиной 128 бит и с ключами длиной 128, 192 или 256 бит, в соответствии с требованиями NIST к новому стандарту. Процедуры шифрования и расшифрования представляют собой последовательность итераций, число которых зависит от длины ключа и равно 8, 12 и 16 соответственно. При шифровании после (а при расшифровании перед) всех итераций производится еще одно подмешивание подключа.

Рис. 3.3. Один раунд алгоритма SAFER+

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

Слои подмешивания первого и второго подключа имеют сходную структуру. На i-й итерации используются два подключа K_2i-1 и K_2i длиной по 128 бит. При добавлении первого подключа байты 1, 4, 5, 8, 9, 12, 13 и 16 текстового блока складываются с соответствующими байтами подключа поразрядно по модулю 2, а байты 2, 3, 6, 7, 10, 11, 14 и 15 складываются с байтами подключа по модулю 256. Второй подключ в конце итерации добавляется аналогично, только те байты, которые складывались поразрядно, теперь складываются по модулю 256, и наоборот.

Слой нелинейной замены устроен следующим образом. Значение x байта j преобразуется в 45^x (mod 257) для байтов с номерами j = 1, 4, 5, 8, 9, 12, 13 и 16. При этом если x = 128, то 45¹²⁸ (mod 257) = 256 представляется нулем. Значения байтов с номерами j = 2, 3, 6, 7, 10, 11, 14 и 15 преобразуются в log₄₅(x), при этом если x = 0, то log₄₅(0) представляется числом 128. Нетрудно заметить, что эти операции являются обратимыми (в действительности, они обратны друг другу). Производить вычисления экспонент и логарифмов при шифровании и расшифровании не обязательно можно заранее вычислить таблицы замены (всего для их хранения потребуется 512 байтов) и использовать их при работе.

Линейное перемешивание представляет собой умножение текстового блока справа на специальную невырожденную матрицу M. При этом все операции выполняются побайтно по модулю 256.

 Подмешивание подключа K_2r+1 производится так же, как и подмешивание первого подключа в каждой итерации.

При расшифровании вначале подмешивается подключ K_2r+1, при этом операция сложения по модулю 256 заменяется на вычитание. Затем выполняются итерации расшифрования.

i-я итерация расшифрования выполняет преобразование, обратное к r-i+1-й итерации шифрования (r число итераций) и также содержит 4 слоя. Вначале текстовый блок умножается на матрицу, обратную к матрице шифрования.

Затем подмешивается подключ K_2r-2i+2 , так же, как и второй подключ в итерации шифрования, только сложение с ключом по модулю 256 заменяется вычитанием.

После этого производится обратная нелинейная замена, т.е. те байты, которые при шифровании возводились в степень, логарифмируются, и наоборот.

И, наконец, подмешивается подключ K_2r-2i+1 (с учетом тех же замечаний, что относились к подмешиванию подключа K_2r-2i+2).

Для завершения описания алгоритма осталось указать, как из ключа пользователя получаются подключи для итераций.

При обработке ключа пользователя применяются так называемые слова смещения B₂, B₃, ..., B₃₃ длиной по 16 байт, которые вычисляются по формулам:

где B_i,j j-й байт i-го слова смещения (j = 1…16). При этом значение B_i,j=256 представляется нулем. Слова смещения являются константами и могут быть вычислены заранее. Для длины ключа в 128 бит используются только слова B₂, ... B₁₇, для ключа в 192 бита используются слова смещения B₂, … ,B₂₅, а для ключа в 256 бит используются все слова.

Генерация подключей осуществляется по следующему алгоритму:

В качестве первого подключа используются первые шестнадцать байтов пользовательского ключа. Далее пользовательский ключ записывается в ключевой регистр размером на один байт больше длины ключа. После этого все байты ключа суммируются поразрядно по модулю 2 и результат записывается в дополнительный байт регистра. После чего для получения требуемых подключей повторяется итеративная процедура, заключающаяся в следующем:

* Содержимое каждого байта в регистре циклически сдвигается влево на 3 позиции;

* Производится выборка 16 байт из регистра. При этом для получения подключа K_i выбираются идущие подряд байты регистра, начиная с i-го и далее по циклу (если достигнут конец регистра, то оставшиеся байты выбираются с его начала);

* Выбранные байты складываются с соответствующими байтами слова смещения B_i по модулю 256. Результат сложения и является подключом K_i.

Алгоритм SAFER++

Алгоритм SAFER++ является дальнейшим развитием алгоритма SAFER+ и был представлен на европейский конкурс алгоритмов NESSIE. Но эксперты сочли, что шифр слишком медленный на всех машинах, кроме смарт-карт, а запас безопасности шифра слишком мал. Этот алгоритм работает с блоками длиной 128 бит, но предусмотрен режим «обратной совместимости» для блоков 64 бита. Длина ключа может быть 128 или 256 бит.

Основная структура алгоритма осталась без изменений. Количество итераций равно 7 или 10 в зависимости от длины ключа. Структура итераций в целом тоже осталась прежней. Итерация зашифрования состоит из слоя подмешивания подключа, слоя нелинейной замены, еще одного слоя подмешивания подключа и линейного обратимого преобразования. Основное отличие алгоритма заключается в структуре линейного преобразования, которое сделано более эффективным с вычислительной точки зрения. Рассмотрим его более подробно.

Рис. 3.4. Структура блока линейного преобразования алгоритма SAFER++

Линейное преобразование, как видно из схемы, состоит из следующих этапов:

* 16 входных байтов перемешиваются в следующем порядке: [9, 6, 3, 16, 1, 14, 11, 8, 5, 2, 15, 12, 13, 10, 7, 4];

* Байты в новом порядке разбиваются на группы по 4. Каждая группа подвергается 4-точечному псевдопреобразованию Адамара;

* После преобразования байты вновь перемешиваются в том же порядке, что и в п.1;

* Аналогично п.2 байты снова проходят через псевдопреобразования Адамара. Результат подаётся на выход.

Псевдопреобразование Адамара заключается в умножении 4-байтовой строки на невырожденную матрицу 4?4, которая имеет следующую структуру:

Обратная матрица, используемая при расшифровании, имеет вид:

Замечательная особенность этого преобразования заключается в том, что умножение на матрицы может быть реализовано путем всего лишь шести операций сложения (вычитания). Если входные байты обозначить как a, b, c, d, а выходные как A, B, C, D, то вычисления будут проводиться по формулам:

D=a+b+c+d (3 сложения),

A=D+a (1 сложение),

B=D+b (1 сложение),

C=D+c (1 сложение),

И обратно:

a=A - d (1вычитание),

b=B - d (1 вычитание),

c=C - d (1 вычитание),

d=D - a - b - c (3 вычитания).

Существуют также некоторые отличия от SAFER+ в алгоритме генерации подключей, используемых на различных раундах шифрования. Слова смещения B₁, … ,B_2r+1 вычисляются по следующим формулам (слово B_{1 ,} как и в алгоритме SAFER+, не используется, можно считать его равным 0):

В SAFER++ чётные и нечётные подключи генерируются независимо друг от друга. Рассмотрим алгоритм более детально.

Для генерации подключей с нечетными номерами берутся первые 16 байт пользовательского ключа. Для генерации подключей с четными номерами берутся вновь первые 16 байт пользовательского ключа, если используется ключ 128 бит, либо оставшиеся 16 байт, если используется ключ 256 бит. Далее вычисляется байтовая контрольная сумма выбранных 16 байт, которая добавляется к ним справа. Затем из полученного расширенного ключа происходит выборка 16 байт подключа итерации с заданным номером.

Выборка происходит следующим образом:

* Выбираются 16 байт из регистра, начиная с номера i и далее по циклу. Так, для ключа с номером i=5 байты будут выбраны следующим образом: [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 1, 2, 3],

* Полученные байты складываются с соответствующим словом смещения,

* Содержимое всех байт регистра циклически сдвигается на 6 бит в случае нечётного i, и на 3 бита в случае чётного i. Процедура повторяется до получения всех требуемых подключей итерации.

Список литературы

1. Баричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной криптографии. - М.: «Горячая линия - Телеком», 2001 - 120 с.

2. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии: Учебное пособие. - М.: Гелиос АРВ, 2002 - 480 с.

3. Скляров Д.В. Искусство защиты и взлома информации. -- СПб.: БХВ-Петербург, 2004 - 288 с.

4. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. -- М.: Триумф, 2002 -- 816 с.

5. В.А. Носов. Краткий исторический очерк развития криптографии 12.02.2003 Из материалов конференции "Московский университет и развитие криптографии в России" (МГУ, 17-18 октября 2002 г.).

6. Ященко В.В. Введение в криптографию,- СПб: Питер, 2001г.

Размещено на Allbest.ru