Криптографический алгоритм RSA уничтожен? Такими заголовками пестрит сегодня крипто-твиттерПользователь zorinaq опубликовал твиттер-тред, чем может обернуться теоретическая работа Клауса Питера Шнорра:
https://twitter.com/zorinaq/status/1367227971912704001Немного теории:
RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.
Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других.
«Если это правда, это открытие сломало бы большинство криптосистем. RSA распространен во многих отраслях: безопасное подключение к (многим) веб-сайтам, подпись кода, чипы кредитных карт и т. д.
Подобные открытия происходят не чаще, чем раз в 2-3 десятилетия.
Шнорр утверждает, что 400-битное число может быть разложено на множители с помощью существующих алгоритмов (QS) за 1,415 × 10 ^ 17 арифметических операций.
Его новая атака довела его до 4,2 × 10 ^ 9 операций.
Что в 34 миллиона раз быстрее
Работа по подбору, которая раньше занимала 92000 лет, теперь может быть выполнена за 1 день!
Улучшение факторизации числа, вдвое большего (800-битного), еще больше:
Существующий алгоритм (NFS): 2,81 × 10 ^ 23 операций
Новая атака Шнорра: 8,4 × 10 ^ 10 операций
Так что в 3300 миллиардов раз быстрее
Неясно, как атака масштабируется с типичным модулем RSA (2048 или 4096 бит).
Как было сказано, вполне вероятно(IMHO) что у атаки есть пробелы или изъяны:
- Шнорр не реализовал алгоритм. Пример факторизованного числа не приводится. Это все теоретически.»
По словам big brain девелопера Антона Букова из 1инч - данное теоретическое исследование не затрагивает разделы эллиптической криптографии, к которым относятся BTC, ETH и т д.
*Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день не известно существование субэкспоненциальных алгоритмов решения задачи дискретного логарифмирования.