Зламано 764 бітний ключ криптографічного стандарту RSA

Поки всі пили та гуляли, відзначаючи Новий Рік та Різдво (кожен в своїй послідовності) групі інженерів з Японії, Швейцарії, Нідерландів і США вдалося успішно обчислити дані, зашифровані за допомогою криптографічного ключа стандарту RSA довжиною 768 біт.

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

Зламати систему шифрування групі вдалося на початку грудня, однак наукову доповідь на цю тему вони представили лише 7 січня 2010 року. Самі автори методу кажуть, що їхні роботи можуть бути визначені як незаконні в деяких країнах, так як алгоритм RSA багато де використовується для державних і військових потреб, проте дослідники говорять, що їхня робота - це суто академічний інтерес і жодного реального ключа, що знаходиться в використанні вони не зламали. Хоча зробити це було б можливо.

Як випливає з опису роботи, обчислення значень ключа інженери проводили методом факторизації модульних чисел. Заснований метод на порівняно простих арифметичних діях, правда об'єднаних в досить складні формули.

Для своїх дослідів вчені використовували звичайне апаратне забезпечення, яке доступне для покупки кожному.

Першим кроком у зломі системи стало обчислення відповідних простих множників. Якщо б цей процес проводився базовим методом перебору, то на процесорі AMD Opteron 2.2 ГГц він би зайняв близько 1500 років і близько 5 терабайт даних. Проте дослідники вирішили використовувати багатовимірні математичні матриці.

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

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

Деталі дослідження.