Практическая реализация и исследование криптостойкости. Часть 4.

Страницы:   1   2   3   4   5   6

---

2. Проектирование модифицированного алгоритма RC6

 

В данной работе описывается разработка алгоритма шифрования, основанная на стандартном алгоритме RC6, как одном из широко распространенных в настоящее время.

Данный алгоритм шифрования обладает следующими свойствами:

1. Алгоритм RC6 является алгоритмом AES по криптостойкости шифра и успешно противостоит всем широко известным методам криптоанализа (при условии длины ключа 512 и 1024 бита).
2. Шифрование и расшифрование текста происходит за сравнительно быстрый период времени, т.к. используются сети Фейштеля и ассемблерные вставки.
3. Зашифрованный текст поддается чтению только при наличии ключа.
4. Знание алгоритма шифрования не снижает криптостойкость шифра.
5. Число операций, необходимых для расшифрования информации путем перебора всевозможных ключей имеет строгую нижнюю оценку и выходит за пределы возможности современных компьютеров или требует создания использования дорогих вычислительных систем.
6. Незначительное изменение ключа или исходного текста приводит к существенному изменению вида зашифрованного текста.
7. Структурные элементы алгоритма шифрования неизменные.
8. Любой ключ из множества возможных обеспечивает равную криптостойкость.
9. Изменение длины ключа не ведет к качественному ухудшению алгоритма шифрования.

2.1 Стандартный вариант шифрования RC6

 

Алгоритм RC6 является продолжением криптоалгоритма RC5, разработанного Роном Ривестом (англ. Ron Rivest) – очень известной личностью в мире криптографии. RC5 был незначительно изменен для того, чтобы соответствовать требованиям AES по длине ключа и размеру блока. При этом алгоритм стал еще быстрее, а его ядро, унаследованное от RC5, имеет солидный запас исследований [5. C. 15-20].

Алгоритм является сетью Фейштеля с 4 ветвями смешанного типа: в нем два четных блока используются для одновременного изменения содержимого двух нечетных блоков. Затем производится обычный для сети Фейштеля сдвиг на одно машинное слово, что меняет четные и нечетные блоки местами. Сам алгоритм изображен на рис 1. Разработчики рекомендуют при шифровании использовать 20 раундов сети, хотя в принципе их количество не регламентируется. При 20 повторах операции шифрования алгоритм имеет самую высокую скорость среди 5 финалистов AES.

 

Преобразование f(x)=x*(2*x+1)(mod 2^w). Оно используется в качестве нелинейного преобразования с хорошими показателями перемешивания битового значения входной величины. В табл. 1 представлены условные обозначения, применяемые в схематичном рисунке.

Табл. 1. Условные обозначения

2.1.1 Процедура шифрования стандартного RC6

 

Шифрование для RC6-w/r/b (w – длина слова в битах, 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

begin

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

v = (D * (2 * D + 1)) << log₂w

A = (A xor t) << u + s[2*i]

C = (C xor u)<< t) + s[2*i+1]

(A,B,C,D) = (B,C,D,A)

End

A = A + S[2*r +2]

C = C + S[2*r +3]

Программная реализация алгоритма шифрования:

//Шифрование регистров в блоке по алгоритму RC6:

procedure EnCryption;

var

Temp, A, B, C, D, t, v: Dword;

i: Byte;

begin

//Шифрование производится для блока информации в 4-х 32-x битовых регистрах Buf:

A := Buf[1];

B := Buf[2];

C := Buf[3];

D := Buf[4];

B := B + S[0];

D := D + S[1];

for i:=1 to r do begin

t := LRot32(B*(2*B+1), 5);

v := LRot32(D*(2*D+1), 5);

A := LRot32(A xor t, v)+S[2*i];

C := LRot32(C xor v, t)+S[2*i+1];

Temp := A;

A := B;

B := C;

C := D;

D := Temp;

end;

A := A + S[2*r+2];

C := C + S[2*r+3];

PreBuf := Buf;

Buf[1] := A;

Buf[2] := B;

Buf[3] := C;

Buf[4] := D;

end;

Исходный файл разбивается на блоки по 128 бит (16 байт). Эти блоки, в свою очередь, состоят из четырех регистров (которые как раз и используются в четырех ветвях сети Фейштеля). Блоки считываются последовательно в цикле из файла. Первый блок считывается, и к четным регистрам прибавляются по модулю 2^w первые два 32-битовых слова ключа. В цикле над четными регистрами производится операция преобразования f(x)=x*(2*x+1)(mod 2^w) и циклический сдвиг влево на log₂32 = 5 бит. Далее над преобразованными регистрами и исходными нечетными регистрами производится операция XOR и циклический сдвиг влево на количество бит, хранимое после преобразования в четных блоках. Заключительная операция в цикле — сложение по модулю 2^w с (2*i)-м и (2*i+1)-м 32-битовыми словами ключа. После окончания цикла к нечетным регистрам прибавляются по модулю 2^w последние два 32-битовых слова ключа. На каждой итерации производится сдвиг на машинное слово, что меняет четные и нечетные регистры местами и начинается новая итерация цикла.

 

2.1.2 Процедура расшифрования стандартного RC6

 

Расшифрование выполняется следующим образом:

Вход:

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

Число итераций циклов шифрования (перемешивания) регистров r

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

Выход:

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

Процедура:

A = A — S[2*r +2]

C = C — S[2*r +3]

for i = r downto 1 do

begin

(A,B,C,D) = (D,A,B,C)

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

v = (D * (2 * D + 1))<< log₂w

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

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

end

D = D — S[1]

B = B — S[0]

Программная реализация алгоритма расшифрования:

//Расшифрование регистров в блоке по алгоритму RC6:

procedure DeCryption;

var

Temp, A, B, C, D, t, v: Dword;

i: Byte;

begin

//Расшифрование производится для блока информации в 4-х 32-x битовых регистрах Buf:

A := Buf[1];

B := Buf[2];

C := Buf[3];

D := Buf[4];

A := A — S[2*r+2];

C := C — S[2*r+3];

for i:=r downto 1 do begin

Temp := D;

D := C;

C := B;

B := A;

A := Temp;

t := LRot32(B*(2*B+1), 5);

v := LRot32(D*(2*D+1), 5);

A := RRot32(A-S[2*i], v) xor t;

C := RRot32(C-S[2*i+1], t) xor v;

end;

B := B — S[0];

D := D — S[1];

PreBuf := Buf;

Buf[1] := A;

Buf[2] := B;

Buf[3] := C;

Buf[4] := D;

end;

Расшифрование аналогично шифрованию.

2.1.3 Процедура генерации ключа стандартного RC6

 

Алгоритм вычисления ключей для RC6:

Вход:

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

Число раундов шифрования (перемешивания) регистров r

Выход:

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

Процедура:

S[0] = P₃₂

for i = 1 to 2*r+3 do

S[i] = S[i-1] +Q₃₂

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

A = B = i = j

for k = 1 to v do

begin

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

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

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

j = (j+1) mod c;

end

Программная реализация генерации ключа:

//Генерация ключа:

procedure Tfmmain.MakeEnKey;

var

L: array [0..63] of Dword;

e, k, v, i, j: Byte;

A, B: Dword;

begin

Key := fmEncrypt.EdKey.Text;

Len := Length(Key);

//Записываем байты в массив из C слов, начиная с младшего, дописываем в конце нули:

FillChar(L, Sizeof(L), 0);

Move(Key, L, Len+1);

c := Len div 4;

if Len mod 4 <> 0 then Inc(c);

//Формирование ключевой таблицы S[0;2r+4] 32-битовых слов

S[0] := $B7E15163;

for i:=1 to 2*r+3 do

S[i] := S[i-1] + $9E3779B9;

i := 0; j := 0;

A := 0; B := 0;

if c>2*r+4 then v := 3*c else v := 3*(2*r+4);

for k:=1 to v do

begin

A := LRot32((S[i]+A+B), 3);

S[i] := A;

B := LRot32((L[j]+A+B), (A+B));

L[j] := B;

i := (i+1) mod (2*r+4);

j := (j+1) mod c;

end;

end;

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

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

Константы P32 = b7e15163 и Q32 = 9e3779b9 – это константы, получаемые из двоичного представления е – 2, где е – основание натурального логарифма, и ф – 1, где ф – золотое сечение соответственно.

После того, как пользователь задает исходный ключ, который записывается в исходный массив L, начинает формироваться ключевая таблица S. Первый элемент S = b7e15163. Далее, в цикле для всех 2*r+3 элементов таблицы S ее элементы задаются следующим образом: каждый следующий элемент равен предыдущему плюс константа 9e3779b9. Далее, определяется, что больше, число ненулевых элементов массива L или 2*r+4. Это значение, помноженное на 3, используется далее в качестве предела итераций для цикла.

В новом цикле снова преобразуются элементы таблицы S. Каждый элемент S[i] равен сумме самого себя, предыдущего элемента S[i-1] и предыдущего элемента L[j-1]. К этому значению применяется циклический сдвиг влево на 3 бит. Аналогичным образом в этом же цикле рассчитывается j-й элемент массива L, за исключение того, что сдвиг влево производится на число бит, равное сумме L[j] и S[i]. Каждые следующие индексы массивов i и j равны самим себе, взятым с увеличением на 1 по модулю (2*r+4) или С соответственно.

 

2.2 Модифицированный вариант шифрования RC6

 

В данной работе алгоритм RC6 модифицировался следующим образом:

1. Добавлены 2 новых регистра E и F.
2. Некоторые добавления в генерации ключа.

Длина слова в битах (32 бит) и длина ключа в байтах (256 байт) остались неименными.

Сам модифицированный алгоритм изображен на рис 2.

 

2.2.1 Процедура шифрования модифицированного RC6

 

Шифрование для RC6-w/r/b (w – длина слова в битах, r – ненулевое количество итерационных циклов зашифрования, b – длина ключа в байтах) описывается следующим образом (изменения помечены жирным шрифтом):

Вход:

Исходный текст, записанный в 6-и w-битовых регистрах A,B,C,D,E,F

Число раундов шифрования (перемешивания) регистров r

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

Выход:

Шифрованный текст в регистрах A,B,C,D,E,F

Процедура:

B = B + S[0];

D = D + S[1];

F = F + S[2];

for i = 1 to r do

begin

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

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

x = (F * (2 * F + 1)) << log₂w

A = (A xor t) << x + s[2*i]

C = (C xor u) << t) + s[2*i+1]

E = (E xor x) << u) + s[2*i+2]

(A,B,C,D,E,F) = (F,A,B,C,D,E)

end

A = A + S[2*r +2]

C = C + S[2*r +3]

E = E + S[2*r +4]

Программная реализация алгоритма шифрования:

//Шифрование регистров в блоке по алгоритму RC6:

procedure EnCryption;

var

Temp, A, B, C, D, E, F, t, v, w: Dword;

i: Byte;

begin

//Шифрование производится для блока в 6-и 32-x битовых регистрах Buf:

A := Buf[1];

B := Buf[2];

C := Buf[3];

D := Buf[4];

E := Buf[5];

F := Buf[6];

B := B + S[0];

D := D + S[1];

F := F + S[2];

for i:=1 to r do

begin

t := LRot32(B*(2*B+1), 5);

v := LRot32(D*(2*D+1), 5);

w := LRot32(F*(2*F+1), 5);

A := LRot32(A xor t, w)+S[2*i];

C := LRot32(C xor v, t)+S[2*i+1];

E := LRot32(E xor w, v)+S[2*i+2];

Temp := A;

A := B;

B := C;

C := D;

D := E;

E := F;

F := Temp;

end;

A := A + S[2*r+1];

C := C + S[2*r+2];

E := E + S[2*r+3];

PreBuf := Buf;

Buf[1] := A;

Buf[2] := B;

Buf[3] := C;

Buf[4] := D;

Buf[5] := E;

Buf[6] := F;

end;

Исходный файл разбивается на блоки по 192 бит (24 байта). Эти блоки, в свою очередь, состоят из шести регистров. Блоки считываются последовательно в цикле из файла. Первый блок считывается, и к четным регистрам прибавляются по модулю 2^w первые два 32-битовых слова ключа. В цикле над четными регистрами производится операция преобразования f(x)=x*(2*x+1)(mod 2^w) и циклический сдвиг влево на log₂32 = 5 бит. Далее над преобразованными регистрами и исходными нечетными регистрами производится операция XOR и циклический сдвиг влево на количество бит, хранимое после преобразования в четных блоках. Заключительная операция в цикле — сложение по модулю 2^w с (2*i)-м и (2*i+1)-м 32-битовыми словами ключа. После окончания цикла к нечетным регистрам прибавляются по модулю 2^w последние два 32-битовых слова ключа. На каждой итерации производится сдвиг на машинное слово, что меняет четные и нечетные регистры местами и начинается новая итерация цикла.

---

Страницы:   1   2   3   4   5   6