RSA
Материал из Википедии — свободной энциклопедии
RSA — система ассиметричного шифрования, в которой для кодирования сообщения используется один ключ, а для расшифровки другой.
Названа в честь математиков-криптологов Рона Ривеста (Rivest), Ади Шамира (Shamir) и Лена Адельмана (Adelman) из Масачуссетского Технологического Института, разработавших алгоритм в 1977 году.
Система RSA основана на трудности задачи разложения на множители. Для её использования нужно сгенерировать два больших простых числа p и q, а затем найти N = pq. Потом нужно выбрать не очень большое e (порядка 10 000), взаимно простое с φ(N) = (p − 1)(q − 1) и сгенерировать d, такое, что ed = 1 (mod φ(N)). Далее e и N публикуются (открытый ключ), а числа d, p и q держатся в секрете (секретный ключ). Тот, кто хочет зашифровать сообщение, вычисляет y = xe (mod N) (где x — исходное сообщение) и посылает его владельцу секретного ключа. Тот расшифровывает сообщение по формуле x = yd (mod N).
Содержание |
[править] Способы выбора p и q
Для обеспечения стойкости системы RSA (p − 1) и (q − 1) не должны разлагаться лишь на маленькие простые множители. Обычно выбирают p = rs + 1, где r — другое большое простое число. Кроме того, есть более простые способы проверки на простоту числа p в этом случае.
[править] Длина ключа
Число N должно иметь размер не меньше 512 бит. В настоящий момент (2006 год) система шифрования на основе RSA считается надёжной, начиная с размера N в 1024 бит.
[править] Применение RSA
Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи. Также она используется в открытой системе шифрования PGP.
Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ.
