АлгоритмRsa

Криптосистема RSA на каждом такте шифрования преобразует двоичный блок открытого текста mдлиныsize(n), рассматриваемый как целое число, в соответствии с формулой:c = m^e(mod n).

При этом n = pq,гдеpиq— случайные простые числа большой разрядности, которые уничтожаются после формирования модуля и ключей. Открытый ключ состоит из пары чиселeиn.Подключeвыбирается как достаточно большое число из диапазона1 < e < φ(n), с условием:НОД(e, (n)) = 1, где(n)— наименьшее общее кратное чиселp–1иq–1.Далее, решая в целых числахx,yуравнениеxe + yφ(n) = 1, полагаетсяd = х, т.е.ed = 1((n)). При этом для всехmвыполняется соотношениеm^ed = m(n),поэтому знаниеdпозволяет расшифровывать криптограммы.

Чтобы гарантировать надежную защиту информации, к системам с открытым ключом предъявляются два следующих требования.

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⁷= 2187 = 9(mod33);RSA(A) =RSA(1) = 1⁷= 1(mod33);RSA(B) =RSA(1) = 2⁷= 128 = 29(mod33).

Получив зашифрованное сообщение (9, 1, 29), мы сможем его расшифровать на основе секретного ключа(d, n) = (3, 33), возводя каждый блок в степеньd = 3:

9³= 729 = 3(mоd33); 1³= 1(mоd33); 29³= 24389 = 2(mоd33).

Для нашего примера легко найти секретный ключ перебором. На практике это невозможно, т.к. для использования на практике рекомендуются в настоящее время следующие значения size(n):

• 512–768 бит — для частных лиц;

• 1024 бит — для коммерческой информации;

• 2048 бит — для секретной информации.

Пример реализации алгоритма RSAпредставлен в листингах 18.1 и 18.2 (компиляторы —Delphi,FreePascal).

Листинг 18.1.Пример реализации алгоритмаRSAна языкеPascal

programRsa; {$APPTYPECONSOLE} {$IFDEFFPC} {$MODEDELPHI} {$ENDIF}usesSysUtils,uBigNumber; //Генератор случайных чисел

vart:array[0..255]ofByte;varpos:Integer;varcbox:array[0..255]ofByte= (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);procedureInicMyRandom;vari:Integer;vars:string;beginWriteLn('Введите какой-либо текст для инициализации генератора случайных чисел (до 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; 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; 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); 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); 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 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; 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 = ( 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; 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 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]<b[i]) then Result := -1; end;

procedure BN_a_add_b(var a,b,res: TBigNum); begin asm pushad mov esi,[a] mov edi,[b] mov ebx,[res] mov ecx,BIGNUM_DWORD mov eax,[esi] add eax,[edi] pushfd mov [ebx],eax add esi,4 add edi,4 add ebx,4 @_add_1: mov eax,[esi] popfd adc eax,[edi] pushfd 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;

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 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; 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); 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; 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 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;

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 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.