Наткнулся на довольно мощную работу DeepMind: человек вместе с AI-агентами занимался криптоанализом и обнаружил две слабости в старой версии RSA с ключом 1024 бита.
Первая касается подписей. В сценарии PKCS#1 v1.5, когда атакующий может контролировать большую часть содержимого подписи, заполнение почти перестаёт создавать дополнительные трудности; теоретическая стоимость подделки короткого дайджеста тоже существенно снизилась (по официальной оценке — примерно в 1600 раз; это оценка, а не результат сквозного практического теста). На практике два взаимодействующих агента менее чем за четыре дня воспроизвели и успешно реализовали атаку на известный экземпляр RSA с ключом 1024 бита. На это ушло около 391 ядро-года — примерно в 3,5 раза быстрее, чем в исходном отчёте.
Вторая касается массовой факторизации. Так называемые fan factories: после предварительных вычислений, примерно эквивалентных одной факторизации, можно разложить ещё один модуль того же размера — предельная стоимость составит лишь около 1/58 от стоимости традиционного NFS, а по сравнению с основным этапом MNFS Копперсмита 1993 года это примерно в 30 раз дешевле. Алгебраические тождества проверены в Lean 4, но всю систему фабрик ещё не реализовали на практике.
В статье ясно сказано: распространённые сегодня RSA-ключи длиной 2048 бит и более не входят в область угрозы. Отказаться всё же стоит от старых ключей на 1024 бита, которые до сих пор используются.
#DeepMind #RSA #AI
Первая касается подписей. В сценарии PKCS#1 v1.5, когда атакующий может контролировать большую часть содержимого подписи, заполнение почти перестаёт создавать дополнительные трудности; теоретическая стоимость подделки короткого дайджеста тоже существенно снизилась (по официальной оценке — примерно в 1600 раз; это оценка, а не результат сквозного практического теста). На практике два взаимодействующих агента менее чем за четыре дня воспроизвели и успешно реализовали атаку на известный экземпляр RSA с ключом 1024 бита. На это ушло около 391 ядро-года — примерно в 3,5 раза быстрее, чем в исходном отчёте.
Вторая касается массовой факторизации. Так называемые fan factories: после предварительных вычислений, примерно эквивалентных одной факторизации, можно разложить ещё один модуль того же размера — предельная стоимость составит лишь около 1/58 от стоимости традиционного NFS, а по сравнению с основным этапом MNFS Копперсмита 1993 года это примерно в 30 раз дешевле. Алгебраические тождества проверены в Lean 4, но всю систему фабрик ещё не реализовали на практике.
В статье ясно сказано: распространённые сегодня RSA-ключи длиной 2048 бит и более не входят в область угрозы. Отказаться всё же стоит от старых ключей на 1024 бита, которые до сих пор используются.
#DeepMind #RSA #AI
