Недостатки реализации RSA
Недостатки реализации криптографического алгоритма шифрования RSA на практике делают его менее безопасным, чем говорилось в теории.
Шифрование RSA зависит от 5 чисел:
Большие простые числа p и q
Модуль выражения n = pq
Ключ шифрования e
Ключ дешифрования d
Числа p, q и d засекречиваются, а числа e и n становятся открытыми. Метод шифрования основывается на предположении, что на практике нельзя разделить n на p и q.
Все пять номеров должны быть выбраны заново для каждого сертификата [1], но на практике номера иногда используются повторно.
Дублирование простых чисел
Числа p и q должны быть уникальными для каждого использования метода, но на практике встречались случаи дублирования простых чисел, когда два экземпляра могут иметь одно из двух общих простых чисел, что позволяет вам вычислять модуль, используя евклидов алгоритм.
Дублирующиеся ключи шифрования
Ключ шифрования e не обязательно должен быть уникальным, как мы всегда думали. На практике показатель шифрования e обычно равен 65537, то есть 216 + 1, это ускоряет реализацию. К тому-же исследование показало, что этот показатель использовался в 99,5% случаев. Однако это позволяет взламывать RSA шифрование, если любой из битов p или q может быть восстановлен из памяти компьютера. Подробнее об этом здесь.
Дублирующиеся модули
Автор этого поста обнаружил несколько экземпляров сертификатов с общими модулями. Это может произойти, если центр сертификации работает небрежно и повторно использует p, q и n, генерируя только новые пары e и d для каждого пользователя. Если вы и кто-то еще совместно используете модуль n, вы можете использовать свою пару (e, d) для фактора n, и, зная их открытый ключ e, имеете возможность восстановить их закрытый ключ d.
Дублирование модулей не может произойти случайно. Как описано здесь, вероятность иметь одно общее простое число из-за случайного выбора примерно равна вероятности выиграть джекпот Powerball 40 раз подряд. Вероятность наличия двух общих простых чисел из-за случайной выборки невероятно мала.
