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

Тема в разделе "Delphi - FAQ", создана пользователем 1nsane, 25 дек 2006.

  1. 1nsane

    1nsane Гость

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

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

    //при вызове возвращает случайное значение в диапазоне 1..(k-1)
    Код (Text):
    function rand(k:integer):integer;
    begin
    Randomize;
    result:=Random(k-1)+1;
    end;

    //возвращает случайное значение e<n и удовлетворяющее условию НОД(e,phi)=1
    Код (Text):
    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
    Код (Text):
    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%). Знаю что, что-то с циклами а может проверкой НОД но исправить к сожалению не могу. :)

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

    zugr Гость

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

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

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

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

Поделиться этой страницей