Методы и средства защиты информации. Внимание!!! В книге могут встречаться существенные ошибки (в рисунках и формулах). Они не связаны ни со
 Скачать 4.86 Mb.
|
|
Глава 18. Криптографическая защита popad end; end; end; procedure BN_a_shl_k(var a: TBigNum; k: Integer; var res: TBigNum); var i,j: Integer; var d,u: Cardinal; begin for j := 0 to BIGNUM_DWORD do res[j] := a[j]; if (k<=0) then Exit; for j := 0 to BIGNUM_DWORD do res[j] := 0; i := k div 32; Продолжение листинга 18.2 if (i>BIGNUM_DWORD) then Exit; for j := i to BIGNUM_DWORD do res[j] := a[j-i]; i := k mod 32; if (i=0) then Exit; d := 0; for j := 0 to BIGNUM_DWORD do begin u := res[j] shr (32-i); res[j] := (res[j] shl i) + d; d := u; end; end; procedure BN_a_shr_k(var a: TBigNum; k: Integer; var res: TBigNum); var i,j: Integer; var d,u: Cardinal; begin for j := 0 to BIGNUM_DWORD do res[j] := a[j]; if (k<=0) then Exit; for j := 0 to BIGNUM_DWORD do res[j] := 0; i := k div 32; if (i>BIGNUM_DWORD) then Exit; for j := i to BIGNUM_DWORD do res[j-i] := a[j]; i := k mod 32; Криптографическая система RSA 405 if (i=0) then Exit; u := 0; for j := BIGNUM_DWORD downto 0 do begin d := res[j] shl (32-i); res[j] := (res[j] shr i) + u; u := d; end; end; function BN_a_upbit(var a: TBigNum): Integer; var i,j: Integer; begin i := BIGNUM_DWORD; while (i>=0) and (a[i]=0) do Dec(i); Продолжение листинга 18.2 Result := 0; if (i<0) then Exit; j := 31; while (j>0) and (a[i] and (1 shl j) = 0) do Dec(j); Result := i*32 + j + 1; end; procedure BN_a_setbit_k(var a: TBigNum; k: Integer); begin if (k<0) or (k>32*BIGNUM_DWORD-1) then begin Exit; end; a[k shr 5] := a[k shr 5] or (1 shl (k and 31)); end; procedure BN_a_mod_b(var a,b,res: TBigNum); var k: Integer; var n1,n2,n3: TBigNum; begin FillChar(n3,sizeof(n3),0); if (BN_a_cmp_b(b,n3)=0) then Exit; Move(a,n1,sizeof(a)); while (BN_a_cmp_b(n1,b)>=0) do begin k := BN_a_upbit(n1) - BN_a_upbit(b); BN_a_shl_k(b,k,n2); 406 Глава 18. Криптографическая защита if (BN_a_cmp_b(n2,n1)>0) then begin BN_a_shr_k(n2,1,n3); Move(n3,n2,sizeof(n3)); end; BN_a_sub_b(n1,n2,n3); Move(n3,n1,sizeof(n3)); end; Move(n1,res,sizeof(n1)); end; procedure BN_a_div_b(var a,b,res: TBigNum); var k: Integer; var n1,n2,n3: TBigNum; begin Продолжение листинга 18.2 FillChar(res,sizeof(res),0); FillChar(n3,sizeof(n3),0); if (BN_a_cmp_b(b,n3)=0) then Exit; Move(a,n1,sizeof(a)); while (BN_a_cmp_b(n1,b)>=0) do begin k := BN_a_upbit(n1) - BN_a_upbit(b); BN_a_shl_k(b,k,n2); if (BN_a_cmp_b(n2,n1)>0) then begin BN_a_shr_k(n2,1,n3); Move(n3,n2,sizeof(n3)); Dec(k); end; BN_a_sub_b(n1,n2,n3); Move(n3,n1,sizeof(n3)); BN_a_setbit_k(res,k); end; end; procedure BN_a_exp_b_mod_c(var a,b,c,res: TBigNum); var i,n: Integer; var n1,n2,n3: TBigNum; begin FillChar(n3,sizeof(n3),0); if (BN_a_cmp_b(c,n3)=0) then Exit; Криптографическая система RSA 407 for i := 0 to BIGNUM_DWORD do res[i] := 0; if (BN_a_cmp_b(b,n3)=0) then begin res[0] := 1; Exit; end; Move(a,n1,sizeof(a)); for i := 0 to BIGNUM_DWORD do n2[i] := 0; n2[0] := 1; n := BN_a_upbit(b)-1; i := 0; while (i<=n) do begin if ( (b[i shr 5] shr (i and 31)) and 1 = 1 ) then begin Продолжение листинга 18.2 BN_a_mul_b(n2,n1,n3); BN_a_mod_b(n3,c,n2); end; BN_a_mul_b(n1,n1,n3); BN_a_mod_b(n3,c,n1); Inc(i); end; Move(n2,res,sizeof(n2)); end; procedure BN_ab_GCD(var a,b,res: TBigNum); var i: Integer; var n1,n2,n3,nzero: TBigNum; begin res[0] := 1; for i := 1 to BIGNUM_DWORD do res[i] := 0; for i := 0 to BIGNUM_DWORD do nzero[i] := 0; if (BN_a_cmp_b(a,nzero)=0) or (BN_a_cmp_b(b,nzero)=0) then Exit; if (BN_a_cmp_b(a,b)>0) then begin Move(a,n1,sizeof(a)); Move(b,n2,sizeof(a)); end else begin 408 Глава 18. Криптографическая защита Move(b,n1,sizeof(a)); Move(a,n2,sizeof(a)); end; while (BN_a_cmp_b(n2,nzero)<>0) do begin BN_a_mod_b(n1,n2,n3); Move(n2,n1,sizeof(n1)); Move(n3,n2,sizeof(n3)); end; Move(n1,res,sizeof(n1)); end; procedure BN_a_modinv_b(var a,b,res: TBigNum); var i: Integer; var n1,n2,n3,n4,n5,n6,n7: TBigNum; var nzero,none: TBigNum; Продолжение листинга 18.2 begin for i := 0 to BIGNUM_DWORD do res[i] := 0; for i := 0 to BIGNUM_DWORD do nzero[i] := 0; for i := 0 to BIGNUM_DWORD do none[i] := 0; none[0] := 1; BN_ab_GCD(a,b,n4); if (BN_a_cmp_b(n4,none)<>0) then Exit; Move(b,n1,sizeof(a)); Move(a,n2,sizeof(a)); Move(none,n7,sizeof(a)); repeat BN_a_div_b(n1,n2,n3); BN_a_mod_b(n1,n2,n4); Move(n2,n1,sizeof(n2)); Move(n4,n2,sizeof(n2)); BN_a_mul_b(n3,n7,n5); BN_a_sub_b(res,n5,n6); Move(n7,res,sizeof(n7)); Move(n6,n7,sizeof(n6)); until (BN_a_cmp_b(n4,nzero)=0); if (res[BIGNUM_DWORD] and $80000000 <> 0) then begin BN_a_add_b(res,b,n7); Move(n7,res,sizeof(n6)); end; end; Криптографическая система RSA 409 function BN_PrimeTest(var a: TBigNum): Integer; var i,j: Integer; var oldseed: LongInt; var nzero,none,nn: TBigNum; var n1,n2,n3,n4: TBigNum; begin Result := 0; for i := 0 to BIGNUM_DWORD do nzero[i] := 0; for i := 0 to BIGNUM_DWORD do none[i] := 0; none[0] := 1; for i := 0 to BIGNUM_DWORD do nn[i] := 0; nn[0] := 256; if (BN_a_cmp_b(a,nzero)=0) then Exit; if (BN_a_cmp_b(a,none)=0) then begin Result := 1; Exit; end; if (BN_a_cmp_b(a,nn)<=0) then begin i := 0; Продолжение листинга 18.2 while (i<=53) and (Cardinal(primes[i])<>a[0]) do Inc(i); if (i>53) then Exit; Result := 1; Exit; end; Move(nzero,n1,sizeof(nzero)); i := 0; n1[0] := primes[i]; BN_a_mod_b(a,n1,n2); while (i<=53) and (BN_a_cmp_b(n2,nzero)>0) do begin Inc(i); if (i>53) then Break; n1[0] := primes[i]; BN_a_mod_b(a,n1,n2); end; if (i<=53) then Exit; Move(nzero,n1,sizeof(nzero)); BN_a_sub_b(a,none,n2); i := 0; n1[0] := primes[i]; BN_a_exp_b_mod_c(n1,n2,a,n3); BN_a_sub_b(n3,none,n4); BN_a_mod_b(n4,a,n3); while (i<=50) and (BN_a_cmp_b(n3,nzero)=0) do 410 Глава 18. Криптографическая защита begin Inc(i); if (i>50) then Break; n1[0] := primes[i]; BN_a_exp_b_mod_c(n1,n2,a,n3); BN_a_sub_b(n3,none,n4); BN_a_mod_b(n4,a,n3); end; if (i<=50) then Exit; BN_a_sub_b(a,none,n2); i := 0; oldseed := RandSeed; for j := 0 to BIGNUM_DWORD do begin n4[j] := Random(2); Окончание листинга 18.2 n4[j] := Cardinal(RandSeed); end; BN_a_mod_b(n4,a,n1); BN_a_exp_b_mod_c(n1,n2,a,n3); BN_a_sub_b(n3,none,n4); BN_a_mod_b(n4,a,n3); while (i<=50) and (BN_a_cmp_b(n3,nzero)=0) do begin Inc(i); if (i>50) then Break; for j := 0 to BIGNUM_DWORD do begin n4[j] := Random(2); n4[j] := Cardinal(RandSeed); end; BN_a_mod_b(n4,a,n1); BN_a_exp_b_mod_c(n1,n2,a,n3); BN_a_sub_b(n3,none,n4); BN_a_mod_b(n4,a,n3); end; RandSeed := oldseed; if (i<=50) then Exit; Result := 1; end; end. Стандарт шифрования данных DES 411 Цифровая ( электронная ) подпись на основе криптосистемы RSA Асимметричная криптография позволяет принципиально решить задачу под - тверждения истинности электронного документа Эта возможность основана на том , что зашифровать данные , используя секретный ключ d вместо открытого ключа e может только тот , кому секретный ключ известен При этом существует возможность проверки применения секретного ключа к данным без его раскры - тия Действительно , пусть нам необходимо заверить блок m открытого текста Сам открытый текст не является секретным Зашифруем m используя d вместо e : с = m d (mоd n) Отправим сообщение двойной длины вида m||c Получатель имеет возможность проверить нашу подпись , поскольку после возведения c в степень e должно получаться значение s = m ( при истинной подписи ) и значение s ≠ m в противном случае Для нашего примера m =(3, 1, 2) , c = (27, 1, 8) , m || с = (3, 1, 2, 27, 1, 8) На практике удвоение длины сообщения , очевидно , является нежелатель - ным Это является одной из причин , по которым вместо c = m d (mod n) исполь - зуются данные вида c = (h(m)) d (mod n) Здесь функция h , называемая хеш - функцией , отображает сообщения произвольной длины в короткие блоки фикси - рованной длины , причем так , что кроме блока m подобрать другой блок z со свойством h(m) = h(z) практически невозможно Стандарт шифрования данных DES Стандарт шифрования данных (DES — Data Encryption Standard) принят в США в 1977 году в качестве федерального В стандарт входит описание блочно - го шифра типа шифра Файстеля , а также различных режимов его работы , как со - ставной части нескольких процедур криптографического преобразования дан - ных Обычно под аббревиатурой DES понимается именно блочный шифр , кото - рый в стандарте соответствует процедуре шифрования в режиме электронной кодовой книги (ECB — Е 1 ес tr о nic Со d е b оо k Мо d е ). Название вызвано тем , что любой блочный шифр является простым подстановочным шифром и в этом от - ношении подобен кодовой книге Принцип работы блочного шифра Рассмотрим принцип работы блочного шифра Входом в блочный шифр и ре - зультатом его работы является блок длины n — последовательность , состоящая из n бит Число n постоянно При необходимости шифрования сообщения дли - ной , большей n , оно разбивается на блоки , каждый из которых шифруется от - дельно Различные режимы работы связаны с дополнительными усложнениями блочного шифра при переходах от блока к блоку В стандарте DES длина блока n = 64 412 Глава 18. Криптографическая защита В режиме ECB шифрование блока открытого текста В производится за 16 од - нотипных итераций , именуемых циклами Схема преобразования приведена на рис . 18.7. Блок рассматривается как конкатенация ( сцепление ) двух подблоков равной длины : B = (L , R) На каждом цикле применяется свой ключ ( X i ), обычно вырабатываемый из некоторого основного ключа ( X ). Ключи , используемые в циклах , называются подключами Основным элементом шифра является несекретная цикловая функция вида Y = f(R,X) Входом в цикл является выход из предыдущего цикла Если упомя - нутый вход имеет вид (L, R) , то выход имеет вид (R, L ⊕ f(R, X)) , где ⊕ — по - разрядное сложение по модулю 2. Например , для выхода цикла с номером i это означает : R i = L i-1 ⊕ f(R i-1 , X i ), L i = R i-1 (i = 1,…,16) В режиме ЕСВ алгоритм DES зашифровывает 64- битовый блок за 16 циклов Биты входного блока перед первым циклом переставляются в соответствии с табл . 18.1 в ходе так называемой начальной перестановки ( IP — initial permutation). После выхода из последнего цикла L и R переставляются местами , после чего соединяются в блок Биты полученного блока снова переставляются в соответствии с перестановкой IP -1 , обратной начальной Результат принимает - ся в качестве блока шифртекста Стандарт шифрования данных DES 413 Рис . 18.7. Блок - схема работы алгоритма DES Таблица 18.1. Начальная перестановка IP 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 Процедура формирования подключей 414 Глава 18. Криптографическая защита На каждом цикле ( рис . 18.8) из ключа X длиной 56 бит формируется ключ X i размером 48 бит Сам ключ X размещается в восьмибайтовом сло - ве , причем восьмые разряды каждого байта являются контрольными и в ключ не входят Перед шифрованием , в соответствии с процедурой выбора PC1 ( табл . 18.2), из X выбираются 56 бит , которыми заполняются два реги - стра ( C и D ) длиной 28 бит каждый В дальнейшем , при входе в очередной цикл с номером i , регистры сдвигают - ся циклически влево Величина сдвига зависит от номера цикла , но является фиксированной и заранее известна После сдвига оба подблока объеди - няются в порядке ( C , D ). Затем , в со - ответствии с функцией выбора PC2 ( табл . 18.3), из них выбираются 48 бит под - ключа Xi Шифрование и расшифровывание отличаются направлением сдвигов ( табл . 18.4). Таблица 18.2. Преобразование PC1 Заполнение С Заполнение D 57 49 41 33 25 17 9 63 55 47 39 31 23 15 1 58 50 42 34 26 18 7 62 54 46 38 30 22 10 2 59 51 43 35 27 14 6 61 53 45 37 29 19 11 3 60 52 44 36 21 13 5 28 20 12 4 Таблица 18.3. Преобразование PC2 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 Выбор битов по таблицам 18.2–18.4 из соответствующих блоков производится следующим образом Таблица рассматривается как последовательность ее строк , записанных друг за другом , начиная с первой строки Биты блока данных соответ - ствующей длины нумеруются слева направо , начиная с единицы Каждый элемент Рис . 18.8. Формирование подключей Стандарт шифрования данных DES 415 s таблицы рассматривается , как номер бита b s в блоке данных Преобразование заключается в замене всех элементов s на биты b s . Таблица 18.4. Соответствие сдвигов номерам циклов DES Номер цикла 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Сдвиг влево ( шифрование ) 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 Сдвиг вправо ( расшифровывание ) 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 Цикловая функция производит следующие действия 1. Расширение блока R i-1 до 48 бит за счет повторения битов блока с помощью функции расширения EP ( табл . 18.5). 2. Поразрядное сложение результата с ключом X i 3. Преобразование полученной суммы с помощью замены ( используя так назы - ваемые S- блоки ), в результате которого получается блок длиной 32 бит 4. Применение перестановки P ( табл . 18.6), что дает значение функции Y = f(R,X) . Таблица 18.5. Преобразование EP Таблица 18.6. Перестановка P 32 1 2 3 4 5 16 7 20 21 29 12 28 17 4 5 6 7 8 9 1 15 23 26 5 18 31 10 8 9 10 11 12 13 2 8 24 14 32 27 3 9 12 13 14 15 16 17 19 13 30 6 22 11 4 25 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 Механизм действия S- блоков Преобразование , с помощью которого 48- разрядный блок преобразуется в 32- разрядный , сводится к выборке восьми тетрад из 8 таблиц (S- блоков ) размером 4 × 16 ( табл . 18.7). Из каждого S- блока выбирается одна тетрада Для этого 48- разрядный блок делится последовательно на 8 комбинаций по 6 бит каждая Пер - вая комбинация ( слева ) является входом в первый S- блок , вторая — во второй и т д При этом первый и последний биты комбинации задают номер строки , а ос - тальные 4 бита — номер столбца S- блока , на пересечении которых расположена соответствующая тетрада Конкретные значения S i ( i = 1, …, 8 ) представлены в табл . 18.7. Таблица 18.7. Таблицы S - блоков для DES |