Всем доброе утро!
Уже несколько дней пытаюсь найти ответ на вопрос по системе шифрования с использованием открытых ключей, а именно RSA. Кажется, именно этот алгоритм используется в платежных системах.
Кто разбирается, то должен быть в курсе, что вся эта защита основана на том, что еще нет быстрого способа разложения числа на множители. В RSA используются 2 простых числа и результат их умножения, который может быть перехвачен, но требуется очень длительное время, чтобы суметь разложить его на 2 множителя, которые и есть ключи к расшифровке. В настоящее время появились ключи длиной 1024 бита, если не больше!
Вроде бы, все понятно, только один момент я никак не могу понять. Как определяют такие огромные простые числа? Как проверяют, что они действительно простые?
Ведь, чтобы проверить это, необходимо попытаться разложить его на множители, а это, как утверждает описание самой защиты RSA, требует миллионы лет.
Помогите разобраться, пожалуйста.