Криптоаналіз RSA

На 2009 рік система шифрування на основі RSA вважається надійною, починаючи з розміру в 1024 біта.

Групі вчених з Швейцарії, Японії, Франції, Нідерландів, Німеччини та США вдалося успішно вирахувати дані, зашифровані за допомогою криптографічного ключа стандарту RSA довжиною 768 біт. [6] За словами дослідників, після їх роботи в якості надійної системи шифрування можна розглядати тільки RSA- ключі довжиною 1024 біта і більше. Причому від шифрування ключем довжиною в 1024 біт варто відмовитися в найближчі три-чотири роки.

Як випливає з опису роботи, обчислення значень ключа здійснювалося загальним методом решета числового поля.

На перший крок (вибір пари поліномів ступеня 6 і 1) було витрачено близько півроку обчислень на 80 процесорах, що склало близько 3% часу, витраченого на головний етап алгоритму (просіювання), який виконувався на сотнях комп'ютерів протягом майже двох років. Якщо інтерполювати цей час на роботу одного процесора AMD Opteron 2.2ГГц з 2Гб пам'яті, то вийшло б близько 1500 років. Обробка даних після просіювання для наступного ресурсоемкого кроку (лінійної алгебри) знадобилося кілька тижнів на малій кількості процесорів. Заключний крок після знаходження нетривіальних рішень ослу зайняв не більше 12 годин.

Рішення ослу проводилося за допомогою методу Відемана на декількох роздільних кластерах і тривало трохи менше 4 місяців. При цьому розмір розрідженої матриці склав 192 796 550х192 795 550 за наявності 27795115920 ненульових елементів (тобто в середньому 144 ненульових елементів на рядок). Для зберігання матриці на жорсткому диску знадобилося близько 105 гігабайт. У той же час знадобилося близько 5 терабайт стиснених даних для побудови даної матриці.

У підсумку групі вдалося обчислити 232-цифровий ключ, що відкриває доступ до зашифрованих даних.

Дослідники впевнені, що використовуючи їх метод факторизації, зламати 1024-бітний RSA-ключ буде можливо протягом наступної декади.