Как факторизация Ферма ломает RSA

RSA — это криптографический алгоритм с открытым ключом. Его стойкость обусловлена вычислительной сложностью решения задачи факторизации (разложения) большого числа на два простых сомножителя.

Однако если криптоключ удовлетворяет определенному условию, его легко взломает алгоритм факторизации, изложенный Пьером Ферма в письме от 1643 года.

Подробности представлены на слайдах.

Письмо Ферма доступно в сборнике "Oeuvres de Fermat" на стр. 256.

https://archive.org/details/oeuvresdefermat02ferm/page/n7/mode/2up

О взломе RSA при помощи факторизации Ферма написал Ханно Бёк в препринте 2023 года:

Hanno B?ck (2023) Fermat Factorization in the Wild.

https://eprint.iacr.org/2023/026

Бёк нашел, что принтеры некоторых фирм генерируют RSA криптоключи из последовательных (или близких) простых чисел, поэтому их можно легко взломать изложенным алгоримом.

Однако Бёк не был первым, кто догадался о такой возможности. О ней упоминали и раньше на Стакэксчендже:

2011. Factoring n, where n=pq and p and q are consecutive primes.

https://math.stackexchange.com/questions/71122/factoring-n-where-n-pq-and-p-and-q-are-consecutive-primes

2020. Explain why we should not choose primes p and q that are too close together to form the modulus n in RSA cryptosystem.

https://math.stackexchange.com/questions/3754984/explain-why-we-should-not-choose-primes-p-and-q-that-are-too-close-together-to-f

Про RSA читайте у Вики)

https://ru.wikipedia.org/wiki/RSA

или на Хабре

https://habr.com/ru/articles/745820/

Получается, что распространенный алгоритм шифрования при неправильно выбранных начальных данных можно легко взломать при помощи метода, описанного более 350 лет назад!

Будьте криптостойкими, читайте Ёжика и лайкайте посты!

Источник: habr.com

Комментарии: