Метод факторизации Ферма стал угрозой для RSA — спустя почти 400 лет после изобретения

Вряд ли кому-то интересно содержимое моей налоговой декларации — в ней нет ничего захватывающего. И это, пожалуй, к лучшему, учитывая, что злоумышленник вполне мог перехватить зашифрованную передачу между моим ноутбуком и принтером в последние годы, когда я её распечатывал.

В начале 2022 года специалист по информационной безопасности Ханно Бёк обнаружил, что некоторые методы шифрования можно взломать. Позже он описал этот способ в предпринте 2023 года , опубликованном в архиве Cryptology ePrint Международной ассоциации криптологических исследований. Интересно, что корни этого метода уходят к работам французского учёного Пьера Ферма из XVII века.

Ферма наиболее известен своей загадочной «последней теоремой», которая долгое время ставила в тупик математиков. Но за свою жизнь он оставил множество полезных открытий — заложил основы теории вероятностей, активно работал с простыми числами, то есть такими, которые делятся только на 1 и самих себя.

Математики уже давно подозревали, что идеи Ферма можно применить для взлома шифров, и Бёк продемонстрировал, как это работает на практике.

Современные системы шифрования основаны на сложных математических задачах. По сути, они похожи на замок: без ключа «открыть» его невозможно. Один из распространённых методов — криптография RSA, которая опирается на свойства простых чисел. Разложение большого числа на простые множители — задача непростая, именно поэтому такие числа хорошо подходят в качестве ключей.

Простые числа часто называют атомами теории чисел — из них «строятся» все остальные натуральные числа. Любое число можно представить как уникальное произведение простых: например, 15 = 3 × 5, а 20 = 2 × 2 × 5. Для небольших чисел это легко, но попробуйте разложить, скажем, 7 327 328 314 — и быстро выяснится, что ни одна программа не справится с этим за приемлемое время.

Именно на этом ограничении и строится RSA. Чтобы понять, как это работает, представим простой пример. Допустим, кто-то хочет зашифровать слово SCIENCE, состоящее из семи букв. Он берёт семизначное число, например 6 743 214, и сдвигает каждую букву слова на соответствующее количество позиций: S сдвигается на 6 и превращается в Y, C — на 7 и становится J, и так далее. В результате получается слово CJMHPDI. Его можно отправить адресату — никто по пути не поймёт, что это SCIENCE.

Однако получатель должен иметь возможность расшифровать исходное сообщение. Для этого ему нужен либо сам ключ (6 743 214), либо возможность его восстановить. Передача ключа напрямую — рискованное дело: злоумышленник может его перехватить. Поэтому в RSA ключ создаётся из общедоступной информации: отправитель и получатель по отдельности используют два больших простых числа, перемножают их и обмениваются только результатом. Без знания исходных простых чисел ключ не получится, а разложить произведение на множители — слишком сложная задача. (Реальный алгоритм RSA сложнее, но принцип примерно такой.)

Почти 400 лет назад Ферма уже размышлял над разложением чисел на простые множители — тогда исключительно из интереса, ведь криптографии ещё не существовало.

И он действительно нашёл способ раскладывать большие числа, состоящие из двух простых множителей. Метод несложный — с ним справится даже калькулятор (которого у Ферма, разумеется, не было). Чтобы произвести впечатление на современников, Ферма использовал число n = 2 027 651 281.

Суть метода: берём число n и извлекаем из него корень. Обычно это нецелое число — в данном случае √2 027 651 281 ≈ 45 029,45. Округляем вверх до 45 030, возводим в квадрат и вычитаем n: 45 030² – 2 027 651 281 = 49 619. Проверяем, является ли это квадратом — нет.

Значит, пробуем дальше: берём 45 030 + 1, возводим в квадрат, вычитаем n: 45 031² – 2 027 651 281 = 139 680. Снова не квадрат. И так далее.

Ферма, видимо, был терпелив. В его примере нужно повторить процедуру 12 раз, пока не получится: 45 041² – 2 027 651 281 = 1 040 400 = 1 020².

Что это даёт? Получаем два квадрата: 45 041² и 1 020², разность которых равна n. Это соответствует формуле: y² – x² = n, или (y – x)·(y + x) = n. А это уже факторизация: n раскладывается на (45 041 – 1 020) = 44 021 и (45 041 + 1 020) = 46 061. Обе величины — простые числа.

Формально, этот метод работает для любого нечётного n. Но есть нюанс: компьютеры справляются с факторизацией быстро только в тех случаях, когда два простых множителя близки по значению. Именно на этом слабом месте и сыграл Бёк: в одной из популярных библиотек, используемой различными компаниями, простые числа генерировались неслучайным образом — зачастую они оказывались слишком близки друг к другу. А значит, метод Ферма подходит для взлома.

Бёк выяснил, что у некоторых производителей принтеров шифрование работает именно так. Например, для защиты документов, отправляемых на печать по сети, использовалась RSA — но с уязвимыми ключами. После открытия в 2022 году производители выпустили предупреждения , разъяснения и обновления для устранения проблемы. Остаётся надеяться, что и другие компании устранили подобные дыры.

В любом случае, в ближайшие годы многим придётся пересмотреть свои подходы к шифрованию. Даже если обычные компьютеры не справляются с факторизацией больших чисел, то квантовые — справятся. Ферма вряд ли мог представить, что спустя почти 400 лет его идея пригодится в мире, где вычисления ведутся с помощью квантовой механики.