Новый подход к проблеме RSA
Опубликована работа, по которой был доклад на Crypto2004:
Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring
Alexander May
Авторы претендуют на открытие первого алгоритма нахождения секретного
ключа за "детерминированное полиномиальное" время.
http://eprint.iacr.org/2004/208
Ссылки
[link1] http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=70334
Работа довольно сложна, но, чтобы не пугать людей не сведущих, стоит оговориться: авторы предлагают алгоритм факторизации [за полиномиальное время] модуля n на сомножители p и q при наличии открытой и закрытой экспонент e и d и при условии, что ed < N^2. Хотя работа представляет исключительный теоретический интерес, для практических атак новый алгоритм применим едва ли. Впрочем, дальнейший прогресс в работе над RSA на лицо.
Это канешно совсем не новая инфа но насколько эфективны методы атаки которые аписаны там ?
http://www.stophack.ru/spec/rsa.shtml
Инфа дествительно не новая, об этом было известно годов этак с семидесятых.
Атаки действительно эффективны, именно поэтому RSA "в чистом виде" для шифрования не используется, а только в составе более сложных протоколов. В правильной реализации его используют для передачи симметричного ключа, например.
В нормально реализованных протоколах эти пути атак закрыты.
Данная работa нe ослабевает, а наоборот, добавляет доверие к RSA, так как доказывает что проблема RSA не легче проблемы факторизации. Это как раз очень здорово, что наконец доказали то, что давно предпологалось.
Кстати, ключевое слово там – Deterministic, потому как вероятностные алгоритмы разложения давно известны. Вот хотя бы[link1].