Разбиха най-сложния алгоритъм за шифроване

Учени от Националния институт по информация и автоматика на Франция са успели да разбият криптиращия ключ RSA-240 с дължина 240 десетични разряда или 795 бита. Той е сочен най-сложен света, като се счита че за разшифровката му са нужни 35 млн. изчислителни години (core years). Групата е изчислила и логаритъм със същата дължина.

Специалистите обаче са успели да постигнат целта си за значително по-малко време – 4 хил. изчислителни години. По техни думи ръстът не е поради увеличаващата се производителност на компютрите. Вместо това е заложено на подобрени алгоритми на разлагане на голямо количество числа на прости множители и усъвършенствани методи за изчисление на дискретни логаритми.

Интересно е да се отбележи, че дискретния логаритъм за RSA-232 ключа с 768-битова разредност бе изчислен едва през 20216 г. макар че бе разбит още през 2010-та.

За да постигнат целта си френските учени са използвали няколко изчислителни клъстера. Те са се състояли от процесори Intel Xeon Gold 6130 с тактова честота до 3,7 Ghz, които са на пазара от 2017 г. Те съдържат 16 ядра (32 нишки) и 22 MB кеш памет от трето ниво. Бързото приключване на изчисленията се дължи най-вече на обновената софтуерна съставяща. Използван е методът NFS (Number Field Sieving).

Редно е да се допълни, че споменатите изчислителни години представляват общото време, използвано за четири изчисления на ключа. При използване на метода NFS са били необходими 800 от тях, а за матричния метод за били необходими още 100. Изчисляването на логаритъма DLP-240 по NFS е отнело 2400 години, а по матричния – 700.