Генерация закрытого ключа в RSA

[artem611]

Всем привет.
Занялся реализацией шифрования RSA, но тут же появилась проблема. Что бы найти закрытый ключ d в источниках сказано применять расширенный алгоритм Евклида. Т.е. нам надо найти НОД(e, phi(n)), где е - это открытая экспонента, а фи - функция Эйлера(если кто не знал).
А проблема в следующем: алгортим работает, но на первом же тестовом примере(брал с википедии) d у меня получилась отрицательная.
Что делать?

[VIK_aka_TOR]

собственно вы взяли слишком больше числа на p и q... после чего произошло переполнение типа и выползли отрицательные значения... уменьшите диапазон p и q...
+ чую что возникнут у вас проблемы с шифрованием... так же весьма большие цифры... в свое время колдовал с этим...

вот как я вычислял d в своей программе... учтены конечно не все результаты... но выдает верные значения...

  //***** вычисление d
  boolean flag;
  flag=true;
  int pn=(p-1)*(q-1);
  while (flag==true)
  {
        d=mas[rand()%10+20];
        if (( d%pn != 0 ) && ( pn%d !=0 ))
          flag=false;
  }

[artem611]

Сообщение от VIK_aka_TOR

собственно вы взяли слишком больше числа на p и q... после чего произошло переполнение типа и выползли отрицательные значения... уменьшите диапазон p и q...
+ чую что возникнут у вас проблемы с шифрованием... так же весьма большие цифры... в свое время колдовал с этим...

вот как я вычислял d в своей программе... учтены конечно не все результаты... но выдает верные значения...

  //***** вычисление d
  boolean flag;
  flag=true;
  int pn=(p-1)*(q-1);
  while (flag==true)
  {
        d=mas[rand()%10+20];
        if (( d%pn != 0 ) && ( pn%d !=0 ))
          flag=false;
  }

Спасибо за Ваш код. Попробую его. Но дело все в том, что числа p и q предполагаются большими. За счет этого как раз и достигается криптостойкость алгоритма.

[Serge_Bliznykov]

помню, кто-то на форуме разбирался с этим самым алгоритмом.
и помню разобрался. И ссылки полезные давал. но вот найти я не смог

посмотрите, вот может эта ссылочка Вам прояснит что-то - RSA для программиста

p.s. я сам "плаваю" в этих вопросах...

[VIK_aka_TOR]

Сообщение от artem611

Спасибо за Ваш код. Попробую его. Но дело все в том, что числа p и q предполагаются большими. За счет этого как раз и достигается криптостойкость алгоритма.

так то оно да... у меня они в диапазое от 100 до 1000 примерно... в mas содержатся простые числа... ну... если хотите оперировать с ольшими числами тогда длинная арифметика вам в помощь... или же ограничиться значениями из диапазона допустимых типами... собственно в архиве моя реализация RSA на Builder С++...
p.s. он работает с русским алфавитом...
p.s.s пересобрал проект... должно запуститься сейчас...

[artem611]

Спасибо за Вашу программу, Вик. Постараюсь в ней разобраться.(с С++ я не очень дружу)
По поводу больших чисел. Да, действительно, мне нужна длинная арифметика и я ей пользуюсь(заставили написать самому, хотя в Java есть встроенный класс BigInteger).

UPD: Ваша программа не запускается. Говорит, что нет vcl60.bpt. Попробую пока вашу реализацию, написанную выше. Может она будет достойно работать)