Алгоритм шифрования Rsa

[1nsane]

Помогите пожалуйста оптимизировать функции, кот ишут ключи для RSA

Сразу скажу, работает только с небольшими числами...

//при вызове возвращает случайное значение в диапазоне 1..(k-1)

function rand(k:integer):integer;
begin
Randomize;
result:=Random(k-1)+1;
end;

//возвращает случайное значение e<n и удовлетворяющее условию НОД(e,phi)=1

function Gen_e(phi:integer;n:integer):integer;
var nod,e,e1:integer;
begin
e:=rand(n);
while (nod<>1) do
begin
e:=rand(n);
e1:=e;
while e1*phi<>0 do
if e1>phi then e1:=e1 mod phi else phi:=phi mod e1;
nod:=e1+phi;
end;
result:=e;
end;

//находит такое значение d<phi при котором выполняется условие e*d mod phi=1

function Poisk_d(e:integer;phi:integer):integer;
begin
d:=rand(phi);
while ((e*d) mod phi)<>1 do d:=rand(phi);
result:=d;
end;

Условия e<n и d<phi достигабтся с помощью функций rand и rand(phi) соответственно

Выполнение данных функций частенько вызывает зависание программы(бесконечный цикл-CPU загружен на 100%). Знаю что, что-то с циклами а может проверкой НОД но исправить к сожалению не могу.

Кратко алгоритм можно описать следующим образом:
1. Выбираются два больших простых числа p и q.
2. Вычисляется их произведение (открытая компонента ключа) n=p*q
3. Находится функция Эйлера по формуле phi=(p-1)(q-1)
4. Выбирается большое простое число e (e<n), такое что НОД(e,phi)=1, т.е. e является взаимно простым со значением phi.
5. Определяется число d, удовлетворяющее условию e*d mod phi=1
Два числа (e,n) – открытый ключ, (d,n) - закрытый.

 

[zugr]

function rand(k:integer):integer;
begin
Randomize;
result:=Random(k-1)+1;
end;

Не надо каждый раз вызывать Randomize, достаточно один раз в самом начале программы.

function Gen_e(phi:integer;n:integer):integer;
var nod,e,e1:integer;
begin
e:=rand(n);
while (nod<>1) do

А откуда стало известно что nod<>1 ? Наверно здесь можем поскочить цикл (хоть вероятность и невелика, но есть)

	if e1>phi then e1:=e1 mod phi else phi:=phi mod e1;

К томуже во внутреннем цикле изменяется phi, соответственно при последующих итерациях внешнего phi может стать другим, и тогда не ясно что проверяем вообще. (Наверно здесь и зацикливемся.)

Видимо, НОД() лучше оформить отдельной функцией.