Як вчені зламали складний криптографічний код: новий рекорд

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

Хоч вирішений алгоритм і слабкіше практичний криптографії, яку в наші дні використовують для забезпечення безпеки даних, проте навіть таке досягнення стало для сучасної обчислювальної техніки досить видатним. Загалом системі знадобилося 35 000 000 обчислювальних годин, які вдалося стиснути в прийнятний часовий проміжок завдяки великій мережі.

Криптографія - це, по суті, математична і комп'ютерна гонка на кмітливість. Метод шифрування, який вчені використовували для створення завдання, називається алгоритмом RSA. У цьому алгоритмі дві сторони шифрують інформацію, використовуючи неймовірно велике число, отримане множенням двох простих чисел.

Як багато хто знає, в математиці існують прості трюки, які дозволять вам відразу сказати, чи ділиться число на 9 або 11. Але як дізнатися, чи ділиться воно на 17? А на 19? Які прості числа треба перемножити, щоб отримати 667? Погодьтеся, чим більше число - тим менш очевидною стає відповідь.

Інша особливість шифрування простих чисел полягає в тому, що їх твір утворює унікальний клас т. зв. «напівпростих» чисел. Самі по собі вони вже не «прості» (оскільки є результатом множення двох факторів), але при цьому не діляться ні як які складові числа. У складових чисел є зачіпки і підказки, які дозволяють ділити їх на частини, а у великих непарних напівпростих чисел такої зачіпки просто немає.

Спробуйте розбити 667 на два простих числа. Перш ніж ви дійдете до єдиного правильного варіанту (23 і 29), ви повинні перепробувати всі однозначні числа, а потім 11, 13, 17 і 19. Однак числа, які дослідники використовували для злому глобальних багатопоточних обчислень, були довжиною до 240 цифр!

Комп'ютери вирішують подібні головоломки методом автопідбору, і чим вище обчислювальна потужність - тим швидше буде виконуватися операція. Проблема в тому, що кожна додана до результату цифра збільшує загальний пул можливих варіантів на порядок (тобто в 10 разів), що істотно ускладнює роботу.

У підсумку французькі вчені побили попередній рекорд як за складністю, так і за часом, вирішивши завдання з 240 цифр за менший час, ніж інша команда вирішила її для 232 цифр. Однак навіть це гігантське число з криптографічним ключем довжиною 795 біт становить трохи більше третини від 2048-бітного шифрування, що використовується більшістю комп'ютерів. Втім, легко зрозуміти, чому криптографія - це гонка, що дозволяє випередити ті самі комп'ютери, які можуть запускати ці алгоритми і зламувати їх при наявності достатнього часу.