Новый подход к проблеме RSA


Опубликована работа, по которой был доклад на Crypto2004:
Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring
Alexander May

Авторы претендуют на открытие первого алгоритма нахождения секретного
ключа за "детерминированное полиномиальное" время.
http://eprint.iacr.org/2004/208


Комментарии
— SATtva (25/08/2004 19:34)   
Работа довольно сложна, но, чтобы не пугать людей не сведущих, стоит оговориться: авторы предлагают алгоритм факторизации [за полиномиальное время] модуля n на сомножители p и q при наличии открытой и закрытой экспонент e и d и при условии, что ed < N^2. Хотя работа представляет исключительный теоретический интерес, для практических атак новый алгоритм применим едва ли. Впрочем, дальнейший прогресс в работе над RSA на лицо.
Гость (07/09/2004 22:22)   
Это канешно совсем не новая инфа но насколько эфективны методы атаки которые аписаны там ?
http://www.stophack.ru/spec/rsa.shtml
Гость (08/09/2004 09:14)   


Инфа дествительно не новая, об этом было известно годов этак с семидесятых.
Атаки действительно эффективны, именно поэтому RSA "в чистом виде" для шифрования не используется, а только в составе более сложных протоколов. В правильной реализации его используют для передачи симметричного ключа, например.
В нормально реализованных протоколах эти пути атак закрыты.
Гость (03/02/2006 16:05)   
Данная работa нe ослабевает, а наоборот, добавляет доверие к RSA, так как доказывает что проблема RSA не легче проблемы факторизации. Это как раз очень здорово, что наконец доказали то, что давно предпологалось.
— RElf (10/03/2006 09:28)   
Кстати, ключевое слово там – Deterministic, потому как вероятностные алгоритмы разложения давно известны. Вот хотя бы[link1].

Ссылки
[link1] http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=70334