[Перевод] Атака Ферма на RSA

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

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

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

Я применил метод факторизации Ферма к большим наборам открытых ключей RSA. И я смог обнаружить небольшое количество уязвимых ключей, которые принадлежали принтерам Canon и Fujifilm (первоначально выпускавшихся под маркой Fuji Xerox). В этих устройствах используется криптографический модуль от компании Rambus.
Читать дальше →

Источник: Хабрахабр