Базы данных и знаний. Управление базами и защита информации учебное п
.pdf32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17
18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1
Для полученного 48-разрядного кода и ключа выполняется операция исключающее ИЛИ (XOR). Результирующий 48-раз- рядный код преобразуется в 32-разрядный с помощью S-матриц. На выходе S-матриц осуществляется перестановка согласно схеме, показанной ниже (числа представляют собой порядковые номера бит).
16 7 20 21 29 12 28 17 1 15 23 26 8 31 10 2 8 24 14 32 27 3 9
19 13 30 6 22 11 4
Преобразование начинается с перестановки бит (IP–Initial Permutation) в 64-разрядном блоке исходных данных. 58-й бит становится первым, 50-й – вторым и т.д. Схема перестановки битов показана ниже.
58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30
22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27
19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
Полученный блок делится на две 32-разрядные части L0 и R0. Далее 16 раз повторяются следующие 4 процедуры: Преобразование ключа с учетом номера итерации i (перестановки разрядов с удалением 8 бит, в результате получается 48-разрядный ключ)
Пусть A=Li, а J – преобразованный ключ. С помощью функции f(A,J) генерируется 32-разрядный выходной код. Выполняется операция XOR для Ri f(A,J), результат означается Ri+1. Выполняется операция присвоения Li+1=Ri.
S-матрицы представляют собой таблицы, содержащие 4 ряда и 16 столбцов. Матрица S(1) представлена ниже (эта матрица так же, как и те, что приведены в ссылке 2, являются рекомендуемыми).
161
No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
Исходный 48-разрядный код делится на 8 групп по 6 разрядов. Первый и последний разряд в группе используется в качестве адреса строки, а средние 4 разряда – в качестве адреса столбца. В результате каждые 6 бит кода преобразуются в 4 бита, а весь 48-разрядный код в 32-разрядный (для этого нужно 8 S-матриц). Существуют разработки, позволяющие выполнять шифрование в рамках стандарта DES аппаратным образом, что обеспечивает довольно высокое быстродействие.
Преобразования ключей Kn (n=1,…,16; Kn = KS(n,key), где n – номер итерации) осуществляются согласно алгоритму, показанному на рис. 7.2.
Рис. 7.2. Алгоритм вычисления последовательности ключей Kn
162
Для описания алгоритма вычисления ключей Kn (функция KS) достаточно определить структуру “Выбор 1” и “Выбор 2”, а также задать схему сдвигов влево. “Выбор 1” и “Выбор 2” представляют собой перестановки битов ключа (PC-1 и PC-2;) При необходимости биты 8, 16,…, 64 могут использоваться для контроля четности. Для вычисления очередного значения ключа таблица делится на две части С0 и D0. В С0 войдут биты 57, 49, 41,…, 44 и 36, а в D0 – 63, 55, 47,…, 12 и 4. Поскольку схема сдвигов задана, C1,D1; Cn, Dn и т.д. могут быть легко получены из C0 и D0. Так, например, C3 и D3 получаются из C2 и D2 циклическим сдвигом влево на 2 разряда.
7.2. Программная реализация алгоритма DES
//Создание ключа в 64 бит
begin
//Создание ключа
St8:='короварс'; st:=' ';// Предположим, это слово принимается за ключ
Form2.memo1.lines.add(st8); For j:=1 to 8 do begin
B16[j]:=ord(st8[j]); // числовой массив ключа – символ переводится в числовой код
st:=st+' '+inttostr(b16[j]); // строка чисел массива
data0:= B16[j]; //слово из массива помещается в перемен-
ную
Data1:=(data0 and $FF) shl (64-8*j); // переменная со сдви-
гом байтов влево
Data:=data or Data1; // Получена переменная на 8 чисел из символов end;
Form2.memo1.lines.add('Числовой массив ключа'+st); // Ключ на 64
163
Form2.memo1.lines.add(' вывод ключа переменной= '+inttostr (data));
// Получение двоичного значения ключа st:=' '; s1:=' ';
For j:=0 to 63 do begin
bit:=(data Shl J) shr (63);//побитное выделение, начиная с левого
s1:=chr(ord('0')+bit);//преобразование бита в символ St:=St+s1;// набор строки битов
Kl64[j+1]:=StrToint(s1);end;end;//создание массива битов
// Получение Ключа на 56 из 64 бит
I:=1; For j:=1 to 64 do begin
if (j Mod 8 <>0) then begin//Пропускается каждый 8 бит
Jk:= PC_1[i];//определяется номер перестановки бита
KL56[I]:=KL64[JK];inc(I); // создается требуемый массив из
56бит
//PC_1[i]-управляющий массив dec(i); end;end;
//Получение сессионных ключей
//на основании полученного ключа необходимо получить 16 ключей
//для 16 циклового расчета ключей begin
// Получение ключа для следующих 15 итераций
For j:=1 to 28 do begin
Ci28[1,j]:=Kl56[j]; // левая половина ключа 1 сессии
Di28[1,j]:=Kl56[j+28]; // правая половина ключа1 сессии end; For i:=1 to 16 do begin // число сесси1 =16
For j:=1 to 28 do begin
C28[j]:=Kl56[j]; // левая половина ключа D28[j]:=Kl56[j+28]; // правая половина ключа end;
if i in[1,2,9,16] then begin // Для 1,2,9,16 циклов – влево сдвиг на 1 бит
A:= C28[1]; B:= D28[1];//запоминание двух битов For j:=1 to 27 do begin
C28[j]:=c28[j+1]; // Сдвиг на 1 бит влево
164
D28[j]:=D28[j+1]; // Сдвиг на 1 бит влево end;
C28[28]:=A; D28[28]:=B; // добавление справа 1 левого бита end else begin
A:= C28[1]; B:= C28[2]; // для остальных сессий сдвиг влево на 2 бита
C:= D28[1]; D:= D28[2]; For j:=1 to 26 do begin C28[j]:=c28[j+2] ; D28[j]:=D28[j+2] ; end; C28[28]:=A; C28[27]:=B; D28[28]:=C; D28[27]:=D; end; // end Else
// Сборка ключа в 56 бит
For j:=1 to 28 Do begin KL56[j]:= C28[j]; Kl56[j+28]:=D28[j]; enD; For j:=1 to 48 do
Kil[i,j]:= Kl56[PC_2[j]]; //Заполнение ключа с перестановкой по [PC_2[j]] end;
Form2.Memo1.Lines.Add('Сессионные ключи 16 ключей'); For i:=1 to 16 do begin
st:=' ';
For j:=1 to 48 do st:=st+ inttostr(Kil[i,j]);
Form2.Memo1.Lines.Add(st); end; //Шифрование текста
begin
//Вводится строка, переводится в массив кодов
//формируется переменная длиной Int64 Data.
//в которую помещается 8 байт слов
//переменная Data переводится в двоичный массив b64 St8:='Текст для шифрования'; Form2.memo1.lines.add(st8);
St8:='axfgnaqc'; st:=' '; Form2.memo1.lines.add(st8); data0:=0; Data:=0;
For j:=1 to 8 do begin
165
B16[j]:=ord(st8[j]); // заполнение массива кодом
data0:= B16[j]; // формирование промежуточной перемен-
ной
st:=st+' '+inttostr(b16[j]); // формирование строки Data1:=(data0 and $FF) shl (64-8*j); // сдвиг влево побайтно
Data:=data or Data1; // Формирование общей строки end;
Form2.memo1.lines.add('Числа Для шифрования= '+st); Form2.memo1.lines.add('Десятичное Знач.= '+inttostr(data)); St:='Двоичное зн. ';Wr(St); st:=' ';
For j:=0 to 63 do begin
Bit:=(data shl j) shr (63);//Выделение бита, начиная со стар-
шего
s1:=chr(ord('0')+bit); //занесение бита в строку St:=St+s1;
b64[j+1]:=strtoint(s1);
if ((j+1) mod 8 = 0)then begin // выводбитов по 8 битв строке
//шифруемого текста
Form2.Memo1.Lines.Add(St); St:=' '; end;end;
//Перестановка битов шифруемого текста
//производится перестановка битов согласно массиву Ip[j] For j:=1 to 64 Do
b641[j]:=b64[Ip[j]];//перестановка согласно массиву IP St:=' ';Wr(St);
St:='1- перестановка '; wr(st); Wr4(64,b641);end;
//Деление вектора 64 бит на 2 по 32 бит / после перестановки 64 бит вектор в 64 бит
//делится на 2 по 32 бит
For j:=1 to 64 Do
if j<=32 then B32L[j]:=b641[j] Else B32R[j-32]:=b641[j];
//Цикловое шифрование begin
For i:=1 to 16 do begin//выполняется 16 циклов
166
For j:=1 to 48 do// копируется 48 бит каждого сессионного ключа
Kl48[j]:= Kil[i,j]; //Вызов ключа
F(B32R,Kl48,Swap32); //48 вектор разбивается на 8 групп по 6 бит
//после разбивки формируется вектор в 32 бит из 48 бит
For j:=1 to 32 Do B32[j]:=Swap32[j] Xor B32L[j];//сложение по модулю 2
B32L:=B32R; // правая часть помещается в левую B32R:=B32; // полученный вектор помещается в правую
половину
end;end;
// Получение слова в 64 бит из двух по 32 бит
begin
For j:=1 to 64 Do //собирается 2 полуслова в 32 бит в слово 64 бит
if j<=32 then b64[j]:=B32R[j] // правая часть else B64[j]:=B32L[j-32]; // левая часть
St:=' ';Wr(St);
St:='После кодирования. '; wr(st); Wr4(64,b64); // Вывод
For j:=1 to 64 Do //перестановка битов b641[j]:=b64[InvIp[j]];
St:=' ';wr(St); St:='Таблица 2 ';wr(st);
wr4(64,b641); // вывод результатов end;
//Символьный шифр текста data:=0;
For i:=1 to 8 do begin // перебор элементов массива
For j:=1 to 8 do begin
bit1:= B64[j+8*(i-1)]; // помещение бита bit:= bit1 and $FF; // Выделение байта Data1:= (bit shl (8-j));// Сдвиг влево Data:=data xor Data1; // Сборка слова data1:=0; end;
167
st:=st+Chr(data); end; form2.Memo1.Lines.Add('Шифр_текст= '+st);
//Дешифрование
For j:=1 to 64 Do
b64[j]:=b641[Ip[j]]; // первичная перестановка
For j:=1 to 64 Do Begin //сборка вектора 64 бит из 2 векто-
ров по 32 бит
if j<=32 then B32R[j]:=b64[j] Else B32L[j-32]:=b64[j]; End;
For i:=16 Downto 1 do begin // цикловая обработка наоборот
For j:=1 to 48 do
Kl48[j]:= Kil[i,j]; // выбор сессионного ключа
F(B32L,Kl48,Swap32); // Sboxex обработка
For j:=1 to 32 Do B32[j]:=Swap32[j] Xor B32R[j];// + по мо-
дулю 2
B32R:=B32L; // смена левой и правой части B32L:=B32; // результат обработки в левую часть
For j:=1 to 64 Do
if j<=32 then b64[j]:=B32L[j] // сборка 2 векторов по 32 бит в 64 бит
else B64[j]:=B32R[j-32]; For j:=1 to 64 Do
b641[j]:=b64[InvIp[j]]; // обратная перестановка end; St:=' ';wr(St);
St:='Результат расшифрования Двоичный код';wr(St); St:=' ';wr(St);
wr4(64,b641); // вывод двоичного кода результата st1:=' '; form2.Memo1.Lines.Add('Шифр_текст= '+st1);
For j:=1 to 64 do // перебор элементов массива st1:=st1+inttostr(B641[j]); // символьная строка битов
168
Form2.memo1.lines.add(st1);// вывод символьной строки би-
тов
data:=0;st1:=' '; s1:=' ';
For i:=1 to 8 do begin // перебор элементов массива по 8 групп
a:=0;
For j:=1 to 8 do // выбор 8 бит в группе b[9-j]:= b641[j+8*(i-1)];
For j:=0 to 7 do // формирование числа из 8 бит
A:=A + b[j+1]* round(exp(j*ln(2)));
s1:=s1+chr(a); //преобразование кода в строку символов st1:=st1+' '+inttostr(a); // строка кодов end; Form2.Memo1.Lines.Add(st1);// Вывод строки кодов Form2.Memo1.Lines.Add(s1); // Вывод строки символов
7.3. Хэш-функция SHA-1
Hash – хэшированием называется преобразование (рис. 7.3) строки произвольной длины в битовую последовательность фиксированной длины. При этом по hash-значению практически невозможно восстановить исходное сообщение или изменить его так, чтобы hash-значение осталось прежним. При соблюдении этих условий hash-значение служит компактным цифровым отпечатком (message digest) сообщения. Популярные алгоритмы хэширования – MD-5 и SHA (Secure Hash Algorithm). Данная функция используется для решения двух задач, а именно доказательства подлинности авторства передаваемого текста и неизменности полученного.
Безопасный хэш-алгоритм (Secure Hash Algorithm) был разработан национальным институтом стандартов и технологии (NIST) и опубликован в качестве федерального информационно-
го стандарта (FIPS PUB 180) в 1993 г. SHA-1, как и MD5, осно-
ван на алгоритме MD4.
169
Логика выполнения SHA-1. Алгоритм получает на входе сообщение максимальной длины 512 бит и создает в качестве выхода дайджест сообщения длиной 160 бит. Следующая порция в 512 бит преобразует полученный вектор в 160 бит снова во вновь преобразованный вектор 160 бит.
//Алгоритм Хэш-функция SHA-1
Рис. 7.3. Логика выполнения SHA-1
Шаг 1: добавление недостающих битов Сообщение добавляется таким образом, чтобы его длина
была кратна 448 по модулю 512 (длина 448 mod 512). Добавление осуществляется всегда, даже если сообщение уже имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512. Добавление состоит из единицы, за которой следует необходимое количество нулей.
Шаг 2: добавление длины К сообщению добавляется блок из 64 бит. Этот блок трак-
туется как беззнаковое 64-битное целое и содержит длину исходного сообщения до добавления. Результатом первых двух шагов является сообщение, длина которого кратна 512 бит. Расширенное сообщение может быть представлено как последовательность 512-битных блоков Y0, Y1, . . . , YL-1, так что общая длина расширенного сообщения есть L * 512 бит. Таким образом, результат кратен шестнадцати 32-битным словам.
Шаг 3: инициализация SHA-1 буфера
170