Множество простых чисел для криптосистемы RSA

Как доказано Эвклидом более двух тысяч лет назад, существует бесконечное множество простых чисел. Поскольку алгоритм RSA оперирует с ключами определенной длины, то количество возможных простых чисел конечно, хотя тем не менее очень велико. По теореме о Простых Числах количество простых чисел меньших некоторого n асимптотически приближается к n = ln (n). Следовательно, количество простых чисел для ключа длиной 512 битов или меньше приблизительно составляет 10¹⁵⁰. Это больше, чем количество атомов в известной Вселенной.

Применение алгоритма RSA на практике

На практике криптосистема RSA часто используется вместе с криптографической системой секретного ключа типа DES для зашифровывания сообщения ключом RSA посредством цифрового конверта. Предположим, что Алиса посылает зашифрованное сообщение Бобу. Сначала она шифрует сообщение по алгоритму DES, используя случайно выбранный ключ DES и затем шифрует ключ DES открытым (public) ключом RSA Боба. Сообщение зашифрованное ключом DES и ключ DES зашифрованный в свою очередь ключом RSA вместе формируют цифровой конверт RSA и отсылаются Бобу. Получив цифровой конверт, Боб расшифровывает ключ DES с помощью своего частного (private) ключа, а затем использует ключ DES, чтобы расшифровать само сообщение.

На практике такая схема реализована в оборудовании THALES (Racal), осуществляющем обмен шифрованной информацией по открытым каналам. При начале новой сессии связи два устройства THALES (Racal) DataCryptor 2000 сначала обмениваются ключами DES для этой сессии, шифруя их по алгоритму RSA, а затем шифруют передаваемую информацию ключами DES. Такой метод позволяет объединить преимущества высокой скорости алгоритма DES с надёжностью системы RSA.