Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Общие вопросы > Алгоритм шифрования RSA

Автор: 1nsane 25.12.2006, 07:48

Помогите пожалуйста оптимизировать функции, кот ишут ключи для 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(n) и rand(phi) соответственно

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

Кратко алгоритм можно описать следующим образом:
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) - закрытый.