Алгоритм RSA
Криптосистема RSA на каждом такте шифрования преобразует двоичный блок открытого текста m длины size(n), рассматриваемый как целое число, в соответствии с формулой: c = me(mod n).
При этом n = pq, где p и q — случайные простые числа большой разрядности, которые уничтожаются после формирования модуля и ключей. Открытый ключ состоит из пары чисел e и n. Подключ e выбирается как достаточно большое число из диапазона 1 < e < ?(n), с условием: НОД(e, j(n)) = 1, где j(n) — наименьшее общее кратное чисел p–1 и q–1.
Далее, решая в целых числах x, y уравнение xe + y?(n) = 1, полагается d = х, т.е. ed = 1(j(n)). При этом для всех m выполняется соотношение med
= m(n), поэтому знание d позволяет расшифровывать криптограммы.
Чтобы гарантировать надежную защиту информации, к системам с открытым ключом предъявляются два следующих требования.
1. Преобразование исходного текста должно исключать его восстановление на основе открытого ключа.
2. Определение закрытого ключа на основе открытого также должно быть вычислительно нереализуемым. При этом желательна точная нижняя оценка сложности (количества операций) раскрытия шифра.
Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах.
Рассмотрим построение криптосистемы RSA на простом примере.
1. Выберем p = 3 и q = 11.
2. Определим n = 3 • 11 = 33.
3. Найдем j(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) = 37 = 2187 = 9(mod 33);
RSA(A) = RSA(1) = 17 = 1(mod 33);
RSA(B) = RSA(1) = 27 = 128 = 29(mod 33).
Получив зашифрованное сообщение (9, 1, 29), мы сможем его расшифровать на основе секретного ключа (d, n) = (3, 33), возводя каждый блок в степень d = 3:
93 = 729 = 3(mоd 33);
13 = 1(mоd 33);
293 = 24389 = 2(mоd 33).
Для нашего примера легко найти секретный ключ перебором. На практике это невозможно, т.к. для использования на практике рекомендуются в настоящее время следующие значения size(n):
- 512–768 бит — для частных лиц;
- 1024 бит — для коммерческой информации;
- 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('Введите какой- либо текст для инициализации генератора
случайных чисел (до 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.
