Хотя информация об открытом ключе не является секретной, ее нужно защищать от подлогов, чтобы злоумышленник под именем легального пользователя не навязал свой открытый ключ, после чего с помощью своего закрытого ключа он сможет расшифровывать все сообщения, посылаемые легальному пользователю, и отправлять свои сообщения от его имени. Проще всего было бы распространять списки, связывающие имена пользователей с их открытыми ключами, широковещательно путем публикаций в средствах массовой информации (бюллетени, специализированные журналы и т. п.). Однако при таком подходе мы снова, как и в случае с паролями, сталкиваемся с плохой масштабируемостью. Решением проблемы является технология цифровых сертификатов — электронных документов, которые связывают конкретных пользователей с конкретными открытыми ключами.
Алгоритм RSA
В настоящее время одним из наиболее популярных криптоалгоритмов с открытым ключом является криптоалгоритм RSA.
В 1978 году трое ученых (Ривест, Шамир и Адлеман) разработали систему шифрования с открытыми ключами RSA (Rivest, Shamir, Adleman), полностью отвечающую всем принципам Диффи—Хеллмана. Этот метод состоит в следующем.
1. Случайно выбираются два очень больших простых числа р и q.
Вычисляются два произведения п = р х q и т = (р - 1) х (q - 1).
3. Выбирается случайное целое число Е, не имеющееюбщих сомножителей с т.
4. Находится D такое, что DE = 1 по модулю т.
5. Исходный текст ^разбивается на блоки таким образом, чтобы 0 < Х< п.
6. Для шифрования сообщения необходимо вычислить С = X>е по модулю п.
7. Для дешифрирования вычисляется X = C>D по модулю п.
Таким образом, чтобы зашифровать сообщение, необходимо знать пару чисел (£, и), а чтобы расшифровать — пару чисел (Д п). Первая пара — это открытый ключ, а вторая — закрытый.
Зная открытый ключ (£, п), можно вычислить значение закрытого ключа D. Необходимым промежуточным действием в этом преобразовании является нахождение чисел р и q, для чего нужно разложить на простые множители очень большое число и, а на это требуется
очень много времени. Именно с огромной вычислительной сложностью разложения большого числа на простые множители связана высокая криптостойкость алгоритма RSA. В некоторых публикациях приводятся следующие оценки: для того чтобы найти разложение 200-значного числа, понадобится 4 миллиарда лет работы компьютера с быстродействием миллион операций в секунду. Однако следует учесть, что в настоящее время активно ведутся работы по совершенствованию методов разложения больших чисел, поэтому в алгоритме RSA стараются применять числа длиной более 200 десятичных разрядов.