Методы и средства защиты информации. Внимание!!! В книге могут встречаться существенные ошибки (в рисунках и формулах). Они не связаны ни со
 Скачать 4.86 Mb.
|
|
Глава 18. Криптографическая защита Чтобы гарантировать надежную защиту информации , к системам с открытым ключом предъявляются два следующих требования 1. Преобразование исходного текста должно исключать его восстановление на основе открытого ключа 2. Определение закрытого ключа на основе открытого также должно быть вы - числительно нереализуемым При этом желательна точная нижняя оценка сложности ( количества операций ) раскрытия шифра Алгоритмы шифрования с открытым ключом получили широкое распростра - нение в современных информационных системах Рассмотрим построение криптосистемы RSA на простом примере 1. Выберем p = 3 и q = 11 2. Определим n = 3 · 11 = 33 3. Найдем ϕ (n) = (p – 1)(q – 1) = 20 4. Выберем e , взаимно простое с 20 , например , e = 7 5. Выберем число d , удовлетворяющее 7d = 1(mоd 20) Легко увидеть , что d = 3(mоd 20) Представим шифруемое сообщение как последовательность целых чисел с помощью соответствия : А = 1 , B = 2 , С = 3 , ..., Z = 26 Поскольку size(n) = 6 , то наша криптосистема в состоянии зашифровывать буквы латинского алфавита , рассматриваемые как блоки , Опубликуем открытый ключ (e, n) = (7, 33) и пред - ложим прочим участникам системы секретной связи зашифровывать с его по - мощью сообщения , направляемые в наш адрес Пусть таким сообщением будет CAB , которое в выбранном нами кодировке принимает вид (3, 1, 2) Отправитель должен зашифровать каждый блок и отправить зашифрованное сообщение в наш адрес : RSA(C) = RSA(3) = 3 7 = 2187 = 9(mod 33); RSA(A) = RSA(1) = 1 7 = 1(mod 33); RSA(B) = RSA(1) = 2 7 = 128 = 29(mod 33). Получив зашифрованное сообщение (9, 1, 29) , мы сможем его расшифровать на основе секретного ключа (d, n) = (3, 33) , возводя каждый блок в степень d = 3 : 9 3 = 729 = 3(m о d 33); 1 3 = 1(m о d 33); 29 3 = 24389 = 2(m о d 33). Для нашего примера легко найти секретный ключ перебором На практике это невозможно , т к для использования на практике рекомендуются в настоящее время следующие значения size(n) : • 512–768 бит — для частных лиц ; • 1024 бит — для коммерческой информации ; Криптографическая система RSA 391 • 2048 бит — для секретной информации Пример реализации алгоритма RSA представлен в листингах 18.1 и 18.2 ( компиляторы — Delphi, FreePascal). Листинг 18.1. Пример реализации алгоритма RSA на языке Pascal program Rsa; {$APPTYPE CONSOLE} {$IFDEF FPC} {$MODE DELPHI} {$ENDIF} uses SysUtils, uBigNumber; // Генератор случайных чисел var t: array[0..255] of Byte; var pos: Integer; var cbox: array[0..255] of Byte = (237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176); procedure InicMyRandom; var i: Integer; var s: string; begin WriteLn(' Введите какой - либо текст для инициализации генератора 392 Глава 18. Криптографическая защита случайных чисел ( до 256 символов ):'); ReadLn(s); i := 1; while (i<=255) and (i<=Length(s)) do Продолжение листинга 18.1 begin t[i] := Ord(s[i]); Inc(i); end; pos := 0; WriteLn('OK'); WriteLn; end; function MyRandom: Cardinal; var i: Integer; var l: Cardinal; begin if (pos = 0) then begin for i := 1 to 255 do t[i] := cbox[(t[i-1]+t[i]) and 255]; for i := 254 downto 0 do t[i] := cbox[(t[i]+t[i+1]) and 255]; end; l := 0; for i := 0 to 3 do l := l shl 8 + Cardinal(t[pos+i]); Result := l; pos := (pos+4) and 255; end; //------------------------------------------------------------- // Главная программа var i,j: Integer; var maxbit: Integer; var none,ntwo: TBigNum; var n1,n2: TBigNum; var p,q,z: TBigNum; var n,e,d: TBigNum; var s1,s2: string; begin WriteLn; Криптографическая система RSA 393 InicMyRandom(); repeat Write(' Введите максимальный размер простых чисел (p и q) в битах (8-257): '); ReadLn(maxbit); Продолжение листинга 18.1 until (maxbit>=8) and (maxbit<=257); //p WriteLn(' Введите большое десятичное значение , которое будет использовано в качестве первого простого числа (Enter -> генерируется программой ): '); ReadLn(s1); BN_dec_to_bignum(s1,p); BN_bignum_to_dec(p,s2); if (s1<>s2) then begin if (s1<>'') then WriteLn(' Число задано неверно !'); s1 := '0'; BN_dec_to_bignum(s1,p); for i := 0 to BIGNUM_DWORD do n1[i] := MyRandom(); BN_a_shr_k(n1,(BIGNUM_DWORD+1)*32-maxbit,p); BN_bignum_to_dec(p,s2); WriteLn(' Сгенерированное число : ',s2); end; WriteLn(' Поиск первого простого числа Ждите ...'); p[0] := p[0] or 1; s1 := '2'; BN_dec_to_bignum(s1,ntwo); j := 0; while (BN_PrimeTest(p)=0) and (j<8192) do begin BN_a_add_b(p,ntwo,n1); Move(n1,p,sizeof(n1)); Inc(j); Write('.'); end; WriteLn; if (j>=8192) then begin WriteLn(' К сожалению , простое число не найдено !'); WriteLn(' Нажмите Enter для выхода .'); ReadLn; Halt(1); end; 394 Глава 18. Криптографическая защита BN_bignum_to_dec(p,s1); WriteLn(' Первое простое число p = ',s1); //q WriteLn(' Введите большое десятичное значение , которое будет использовано в качестве второго простого числа (Enter -> генерируется программой ): '); Продолжение листинга 18.1 ReadLn(s1); BN_dec_to_bignum(s1,q); BN_bignum_to_dec(q,s2); if (s1<>s2) then begin if (s1<>'') then WriteLn(' Число задано неверно !'); s1 := '0'; BN_dec_to_bignum(s1,q); for i := 0 to BIGNUM_DWORD do n1[i] := MyRandom(); BN_a_shr_k(n1,(BIGNUM_DWORD+1)*32-maxbit,q); BN_bignum_to_dec(q,s2); WriteLn(' Сгенерированное число : ',s2); end; WriteLn(' Поиск первого простого числа Ждите ...'); q[0] := q[0] or 1; s1 := '2'; BN_dec_to_bignum(s1,ntwo); j := 0; while (BN_PrimeTest(q)=0) and (j<8192) do begin BN_a_add_b(q,ntwo,n1); Move(n1,q,sizeof(n1)); Write('.'); end; WriteLn; if (j>=8192) then begin WriteLn(' К сожалению , простое число не найдено !'); WriteLn(' Нажмите Enter для выхода .'); ReadLn; end; BN_bignum_to_dec(q,s1); WriteLn(' Второе простое число q = ',s1); WriteLn; //n = p*q BN_a_mul_b(p,q,n); BN_a_div_b(n,q,n1); Криптографическая система RSA 395 if (BN_a_cmp_b(p,n1)<>0) then begin WriteLn(' К сожалению , результат умножения p*q слишком велик !'); WriteLn(' Нажмите Enter для выхода .'); ReadLn; Halt(1); end; BN_bignum_to_dec(n,s1); Продолжение листинга 18.1 WriteLn('n = p*q = ',s1); // z =(p-1)*(q-1) s1 := '1'; BN_dec_to_bignum(s1,none); BN_a_sub_b(p,none,n1); BN_a_sub_b(q,none,n2); BN_a_mul_b(n1,n2,z); BN_bignum_to_dec(z,s1); WriteLn('z = (p-1)*(q-1) = ',s1); // d WriteLn(' Введите большое десятичное значение , которое будет использовано в качестве открытого ключа (Enter -> генерируется программой ): '); ReadLn(s1); BN_dec_to_bignum(s1,d); BN_bignum_to_dec(d,s2); if (s1<>s2) then begin if (s1<>'') then WriteLn(' Число задано неверно !'); s1 := '0'; BN_dec_to_bignum(s1,n1); for i := 0 to BIGNUM_DWORD do n1[i] := MyRandom(); BN_a_mod_b(n1,z,d); BN_bignum_to_dec(d,s2); WriteLn(' Сгенерированное число : ',s2); end; WriteLn(' Поиск открытого ключа Ждите ...'); d[0] := d[0] or 1; s1 := '1'; BN_dec_to_bignum(s1,none); s1 := '2'; BN_dec_to_bignum(s1,ntwo); j := 1; BN_ab_GCD(d,z,n1); while (BN_a_cmp_b(n1,none)<>0) and (j<1000) do begin BN_a_add_b(d,ntwo,n1); 396 Глава 18. Криптографическая защита Move(n1,d,sizeof(n1)); BN_ab_GCD(d,z,n1); j := j+1; end; BN_ab_GCD(d,z,n1); if (BN_a_cmp_b(n1,none)<>0) then begin WriteLn(' К сожалению , подходящего простого числа не найдено !'); Продолжение листинга 18.1 WriteLn(' Нажмите Enter для выхода .'); ReadLn; Halt(1); end; WriteLn; BN_bignum_to_dec(d,s1); WriteLn(' Открытый ключ d = ',s1); WriteLn; // e WriteLn(' Вычисление секретного ключа ...'); BN_a_modinv_b(d,z,e); BN_bignum_to_dec(e,s1); WriteLn(' Секретный ключ e = ',s1); WriteLn; //e*d mod z = 1 ? BN_a_mul_b(e,d,n1); BN_a_mod_b(n1,z,n2); if (BN_a_cmp_b(n2,none)<>0) then begin WriteLn(' СБОЙ : e*d mod z <> 1!'); WriteLn(' Нажмите Enter для выхода .'); ReadLn; Halt(1); end; WriteLn('e*d mod z = 1'); WriteLn; // Проверка ключей WriteLn(' Введите большое значение для проверки ключей (Enter -> генерируется программой ):'); ReadLn(s1); BN_dec_to_bignum(s1,n1); BN_bignum_to_dec(n1,s2); if (s1<>s2) then Криптографическая система RSA 397 begin if (s1<>'') then WriteLn(' Число задано неверно !'); s1 := '0'; BN_dec_to_bignum(s1,n1); for i := 0 to BIGNUM_DWORD do n1[i] := MyRandom(); end; n1[7] := 0; BN_a_mod_b(n1,n,n2); BN_bignum_to_hex(n2,s2); Окончание листинга 18.1 WriteLn(' Исходное значение = 0x',s2); BN_a_exp_b_mod_c(n2,e,n,n1); BN_bignum_to_hex(n1,s1); WriteLn(' Зашифрованное значение = 0x',s1); BN_a_exp_b_mod_c(n1,d,n,n2); BN_bignum_to_hex(n2,s1); WriteLn(' Расшифрованное значение = 0x',s1); if (s1<>s2) then begin WriteLn(' СБОЙ : расшифрованное значение не совпадает с исходным !'); WriteLn(' Нажмите Enter для выхода .'); ReadLn; Halt(1); end; WriteLn('OK'); WriteLn; // Техническая информация WriteLn('--------------------------------------------------'); BN_bignum_to_hex(e,s1); WriteLn(' e = 0x',s1,' (',BN_a_upbit(e),'bit)'); BN_bignum_to_hex(d,s1); WriteLn(' d = 0x',s1,' (',BN_a_upbit(d),'bit)'); BN_bignum_to_hex(n,s1); WriteLn(' n = 0x',s1,' (',BN_a_upbit(n),'bit)'); WriteLn('--------------------------------------------------'); WriteLn; WriteLn(' Размер блока исходного текста : ',IntToStr(BN_a_upbit(n)-1),' бит '); WriteLn(' Размер блока зашифрованного текста : ',IntToStr(BN_a_upbit(n)),' bit'); WriteLn; 398 Глава 18. Криптографическая защита WriteLn(' Нажмите Enter для выхода .'); ReadLn; end. Листинг 18.2. Вспомогательный модуль uBigNumber unit uBigNumber; {$IFDEF FPC} {$MODE DELPHI} {$ASMMODE INTEL} {$ENDIF} Продолжение листинга 18.2 interface const BIGNUM_DWORD = 31; type TBigNum = array[0..BIGNUM_DWORD] of Cardinal; procedure BN_bignum_to_hex(var a: TBigNum; var s: string); procedure BN_hex_to_bignum(var s: string; var a: TBigNum); procedure BN_bignum_to_dec(var a: TBigNum; var s: string); procedure BN_dec_to_bignum(var s: string; var a: TBigNum); function BN_a_cmp_b(var a,b: TBigNum): Integer; procedure BN_a_add_b(var a,b,res: TBigNum); procedure BN_a_sub_b(var a,b,res: TBigNum); procedure BN_a_mul_b(var a,b,res: TBigNum); procedure BN_a_shl_k(var a: TBigNum; k: Integer; var res: TBigNum); procedure BN_a_shr_k(var a: TBigNum; k: Integer; var res: TBigNum); function BN_a_upbit(var a: TBigNum): Integer; procedure BN_a_setbit_k(var a: TBigNum; k: Integer); procedure BN_a_mod_b(var a,b,res: TBigNum); procedure BN_a_div_b(var a,b,res: TBigNum); procedure BN_a_exp_b_mod_c(var a,b,c,res: TBigNum); procedure BN_ab_GCD(var a,b,res: TBigNum); procedure BN_a_modinv_b(var a,b,res: TBigNum); function BN_PrimeTest(var a: TBigNum): Integer; implementation uses SysUtils; var primes: array[0..53] of Integer = Криптографическая система RSA 399 ( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251); procedure BN_bignum_to_hex(var a: TBigNum; var s: string); var i: Integer; begin i := BIGNUM_DWORD; while (i>=0) and (a[i]=0) do Dec(i); Продолжение листинга 18.2 s := '0'; if (i<0) then Exit; s := ''; while (i>=0) do begin s := s + IntToHex(a[i],8); Dec(i); end; while (Length(s)>1) and (s[1]='0') do Delete(s,1,1); end; procedure BN_hex_to_bignum(var s: string; var a: TBigNum); var i,j,l: Integer; var n1,n2,n3,n4: TBigNum; var n16: TBigNum; begin for i := 0 to BIGNUM_DWORD do a[i] := 0; for i := 0 to BIGNUM_DWORD do n16[i] := 0; n16[0] := 16; for i := 0 to BIGNUM_DWORD do n1[i] := 0; n1[0] := 1; for i := 0 to BIGNUM_DWORD do n2[i] := 0; l := Length(s); for i := l downto 1 do begin j := Ord(UpCase(s[i])); case j of Ord('0')..Ord('9'): j := j - Ord('0'); Ord('A')..Ord('F'): j := j - Ord('A') + 10; else Exit; end; 400 Глава 18. Криптографическая защита n2[0] := Cardinal(j); BN_a_mul_b(n1,n2,n3); BN_a_add_b(a,n3,n4); Move(n4,a,sizeof(n4)); BN_a_mul_b(n1,n16,n3); Move(n3,n1,sizeof(n3)); end; end; procedure BN_bignum_to_dec(var a: TBigNum; var s: string); var i: Integer; var n1,n2: TBigNum; Продолжение листинга 18.2 var nzero,nten: TBigNum; begin for i := 0 to BIGNUM_DWORD do nzero[i] := 0; for i := 0 to BIGNUM_DWORD do nten[i] := 0; nten[0] := 10; s := '0'; if (BN_a_cmp_b(a,nzero)=0) then Exit; Move(a,n1,sizeof(a)); s := ''; repeat BN_a_mod_b(n1,nten,n2); s := Chr(n2[0]+48)+s; BN_a_div_b(n1,nten,n2); Move(n2,n1,sizeof(n2)); until (BN_a_cmp_b(n1,nzero)=0); while (Length(s)>1) and (s[1]='0') do Delete(s,1,1); end; procedure BN_dec_to_bignum(var s: string; var a: TBigNum); var i,j,l: Integer; var n1,n2,n3,n4: TBigNum; var nten: TBigNum; begin for i := 0 to BIGNUM_DWORD do a[i] := 0; for i := 0 to BIGNUM_DWORD do nten[i] := 0; nten[0] := 10; for i := 0 to BIGNUM_DWORD do n1[i] := 0; n1[0] := 1; for i := 0 to BIGNUM_DWORD do n2[i] := 0; l := Length(s); for i := l downto 1 do begin Криптографическая система RSA 401 j := Ord(s[i])-48; if (j<0) or (j>9) then Exit; n2[0] := Cardinal(j); BN_a_mul_b(n1,n2,n3); BN_a_add_b(a,n3,n4); Move(n4,a,sizeof(n4)); BN_a_mul_b(n1,nten,n3); Move(n3,n1,sizeof(n3)); end; end; function BN_a_cmp_b(var a,b: TBigNum): Integer; var i: Integer; Продолжение листинга 18.2 begin i := BIGNUM_DWORD; while (i>=0) and (a[i]=b[i]) do Dec(i); Result := 0; if (i>=0) and (a[i]>b[i]) then Result := 1; if (i>=0) and (a[i] 402 Глава 18. Криптографическая защита mov [ebx],eax add esi,4 add edi,4 add ebx,4 loop @_add_1 @_add_2: popfd popad end; end; procedure BN_a_sub_b(var a,b,res: TBigNum); begin asm Продолжение листинга 18.2 pushad mov esi,[a] mov edi,[b] mov ebx,[res] mov ecx,BIGNUM_DWORD mov eax,[esi] sub eax,[edi] pushfd mov [ebx],eax add esi,4 add edi,4 add ebx,4 @_sub_1: mov eax,[esi] popfd sbb eax,[edi] pushfd mov [ebx],eax add esi,4 add edi,4 add ebx,4 loop @_sub_1 @_sub_2: popfd popad end; end; Криптографическая система RSA 403 procedure BN_a_mul_b(var a,b,res: TBigNum); var i,j: Integer; begin for j := 0 to BIGNUM_DWORD do res[j] := 0; for i := 0 to BIGNUM_DWORD do begin j := i*4; asm pushad mov esi,[a] mov edi,[b] add edi,[j] mov ebx,[res] Продолжение листинга 18.2 add ebx,[j] mov ecx,BIGNUM_DWORD sub ecx,[i] cmp ecx,0 je @_mul_2 @_mul_1: mov eax,[esi] mov edx,[edi] mul edx add [ebx],eax adc [ebx+4],edx pushfd cmp ecx,1 je @_mul_1_1 popfd adc dword ptr[ebx+8],0 pushfd @_mul_1_1: popfd add esi,4 add ebx,4 loop @_mul_1 @_mul_2: mov eax,[esi] mov edx,[edi] mul edx add [ebx],eax |