Допустим, вы хотите, чтобы «n» было 2048 бит (RSA 2048). Тогда «p» и «q» будут равны 1024 битам.
Компьютер генерирует случайное 1024-битное число (почти мгновенно) и проверяет его на простоту. Существуют различные виды тесты на простоту, большинство из них статистические. Они очень быстрые (я знаю, что это не поддается количественной оценке, но я работаю на встроенных микроконтроллерах, работающих на частоте 100 МГц без кэша, поэтому я понятия не имею о скорости на рабочем столе).
Таким образом, сгенерировав кучу 1024-битных чисел, вы, наконец, наткнетесь на то, которое проходит несколько итераций тестов на простоту. (не вдаваясь здесь в подробности о статистике и о том, что "достаточно хорошо", это все достаточно легко найти). Сделайте то же самое, чтобы получить свой «q», умножьте их, у вас есть модуль «n». «n» плюс ваш «e» (вероятно, 65537) — ваш открытый ключ.
Как вы понимаете, плотность простых чисел уменьшается по мере увеличения чисел; есть способы оценка простой плотности в зависимости от размера простого числа, которое вы пытаетесь сгенерировать. 40% чисел до 10 являются простыми, но только 25% плотности для чисел до 100 и еще меньше для 1024-битных чисел. Если я правильно помню, в среднем, вам придется попробовать цикл проверки генерации/простоты примерно 360 раз, чтобы найти 1024-битное число, которое проверяется как простое. Это не тысячи и не миллионы. А для 512-битных чисел это, вероятно, менее 100 попыток.
Поскольку числовое пространство 2^1024 такой огромный, маловероятно, что ваши p&q совпадут с чьими-либо еще. На самом деле каждая из этих 1024-битных строк, вероятно, никогда не существовала ни на одном компьютере в истории Земли.
Надеюсь, это дало вам достаточное представление о том, как это работает. Это в основном так просто. Я опустил некоторые детали, обсуждение сильных простых чисел и т. д., потому что они затрагивают детали, выходящие за рамки вашего вопроса.
