Я ошибаюсь, думая, что безопасность шифрования RSA в общем случае ограничена количеством известных простых чисел?
Чтобы взломать (или создать) закрытый ключ, нужно совместить правую пару простых чисел.
Невозможно ли опубликовать список всех простых чисел в диапазоне, используемом RSA? Или этот список достаточно велик, чтобы сделать эту грубую силовую атаку маловероятной? Разве не было бы "часто используемых" простых чисел?
RSA не выбирает из списка известных простых чисел: он генерирует новое очень большое число, затем применяет алгоритм для нахождения близлежащего числа, которое почти наверняка является простым. См. это полезное описание большого простого поколения):
Стандартный способ генерации больших простых чисел состоит в том, чтобы взять предварительно выбранное случайное число требуемой длины, применить тест Fermat (лучше всего с базой 2, поскольку он может быть оптимизирован для скорости), а затем применить определенное количество Miller -Rabin (в зависимости от длины и допустимой частоты ошибок, например, 2-100), чтобы получить число, которое, вероятно, является простым числом.
(Вы можете спросить, почему в этом случае мы не используем этот подход, когда пытаемся найти большие и большие простые числа. Ответ заключается в том, что наибольшее известное простое имеет более 17 миллионов цифр - далеко за пределами даже очень больших чисел, обычно используемых в криптографии).
Что касается возможных столкновений - современные размеры ключей (в зависимости от требуемой безопасности) варьируются от 1024 до 4096, что означает, что простые числа варьируются от 512 до 2048 бит. Это означает, что ваши простые числа имеют порядок 2 ^ 512: более 150 цифр.
Мы можем очень грубо оценить плотность простых чисел, используя 1 / ln(n) (см. здесь). Это означает, что среди этих чисел 10^150 существует приблизительно 10^150/ln(10^150) простых чисел, которые выходят на 2.8x10^147 простых чисел, чтобы выбрать из них, конечно, больше, чем вы могли бы вписаться в любой список!
Итак, да - число простых чисел в этом диапазоне огромно огромно, и столкновения фактически невозможны. (Даже если вы создали триллион возможных простых чисел, образуя семитипные комбинации, вероятность того, что любые два из них будут тем же самым простым числом, будет 10^-123).
По мере того как новое исследование выходит, ответ на ваш вопрос становится более интересным. В недавней статье "Несовершенная передовая тайна: как Диффи-Хеллман не срабатывает на практике" Дэвида Адриана и все найдено @https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf, доступ к которому 10/16/2015 исследователи показывают, что хотя, вероятно, имеется достаточное количество простых чисел, доступных для набора ключей RSA 1024 бит, есть группы ключей внутри всего набора, которые, скорее всего, будут использоваться из-за реализации.
Мы оцениваем, что даже в 1024-битном случае вычисления правдоподобных данных национальных ресурсов. Небольшое количество фиксированных или стандартизированные группы используются миллионами серверов; выполнение предварительная компиляция для одной 1024-битной группы позволила бы использовать пассивную подслушивание на 18% популярных HTTPS-сайтов, а вторая группа разрешить дешифрование трафика до 66% IPsec VPN и 26% SSH сервера. Тщательное прочтение опубликованных утечек NSA показывает, что атаки agencys на виртуальные частные сети согласуются с тем, что ломать. Мы заключаем, что переход к более сильным методам обмена ключами должен быть приоритетом для интернет-сообщества.
Исследование также показывает недостаток в TLS, который может позволить злоумышленнику "человек в середине" понизить шифрование до 512 бит.
Таким образом, в ответ на ваш вопрос, вероятно, имеется достаточное количество простых чисел в шифровании RSA на бумаге, но на практике возникает проблема безопасности, если вы скрываетесь от национального государства.
Простые числа, которые будут использоваться в RSA, не просто большие. Он должен быть десятизначным или может быть 100-значным. Я имею в виду не миллиарды или триллионы, а нечто, что трудно выразить или даже представить.
Итак, чтобы ответить на вопрос, такие числа не могут быть известны простые числа.