- •Оглавление
- •1. Введение
- •3. Требования к криптосистемам
- •4. Краткая история. Традиционные симметричные криптосистемы
- •5. Классификация современных криптографических систем
- •Шифратор
- •Дешифратор
- •Шифратор
- •Дешифратор
- •6. Симметричные Системы с закрытым (секретным) ключом
- •6.1 Алгоритмы des и Тройной des
- •6.2 Алгоритм idea
- •6.3 Алгоритм гост 28147-89
- •6.4 Новый американский стандарт aes
- •7. Асимметричные Системы с открытым ключом
- •7.1 Математические основы шифрования с открытым ключом
- •7.2 Алгоритм rsa (Rivest, Shamir, Adleman)
- •7.3 Алгоритм Эль Гамаля
- •7.4 Алгоритм pgp (Pretty Good Privacy)
- •8. Электронная подпись
- •8.1 Электронная подпись на основе алгоритма rsa
- •8.2 Цифровая сигнатура
- •9. Управление ключами
- •9.2 Накопление ключей
- •9.4 Алгоритм Диффи-Хеллмана
- •10. Проблемы и перспективы криптографических систем
- •10.1 Шифрование больших сообщений и потоков данных
- •10.2 Использование “блуждающих ключей”
- •11. Основные типы криптоаналитических атак
7.2 Алгоритм rsa (Rivest, Shamir, Adleman)
Алгоритм RSA является одним из первых алгоритмов шифрования с открытым ключом, который нашел практическое применение. Он был предложен в 1978 г. тремя авторами Рональдом Райвестом (Ronald Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлерманом (Leonard M. Adlerman) и получил название по первым буквам их фамилий.
Алгоритм RSA использует факт, что нахождение больших (например, 100-битных) простых чисел в вычислительном отношении осуществляется легко, однако разложение на множители произведения двух таких чисел в вычислительном отношении представляется невыполнимым.
Алгоритм RSA принят в качестве следующих международных стандартов: ISO/IEC/DIS 9594-8 и X.509. В настоящее время Международная сеть электронного перечисления платежей SWIFT требует от банковских учреждений, пользующихся ее услугами, применения именно этого алгоритма криптографического преобразования информации.
Алгоритм работает так 10.2.2:
Отправитель выбирает два очень больших простых числа P и Q и вычисляет два произведения N = PQ и M = (P-1)(Q-1).
Затем он выбирает случайное целое число D, взаимно простое с M, и вычисляет E, удовлетворяющее условию DE = 1 mod M.
После этого он публикует D и N как свой открытый ключ шифрования, сохраняя E как закрытый ключ.
Если S - сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале (1, N), то оно превращается в шифровку возведением в степень D по модулю N и отправляется получателю S1 = SD mod N.
Получатель сообщения расшифровывает его, возводя в степень E по модулю N, так как S = S1E mod N = SDE mod N.
Таким образом, открытым ключом служит пара чисел N и D, а секретным ключом число E.Смысл этой системы шифрования основан на так называемой малой теореме Ферма, которая утверждает, что при простом числе P и любом целом числе K, которое меньше P, справедливо тождество KP-1 = 1 mod P. Эта теорема позволяет определить, является ли какое-либо число простым или составным.
7.3 Алгоритм Эль Гамаля
Другим известным методом является предложенный в 1985 г. Тахером Эль Гамалем (Taher El Gamal) алгоритм Эль Гамаля, положенный в основу стандарта NIST (National Institute of Standards and Technology)4 - MD 20899.
Алгоритм основан на возведении в степень по модулю большого простого числа. Для этого задается большое простое число P. Сообщения представляются целыми числами S из интервала (1, P). Оригинальный протокол передачи сообщения S выглядит в варианте А.Шамира так 10.2.2:
Отправитель А и получатель В знают лишь P. А генерирует случайное число X из интервала (1, P) и В тоже генерирует случайное число Y из того же интервала.
А шифрует сообщение S1 = SX mod P и посылает В.
В шифрует его своим ключом S2 = S1Y mod P и посылает S2 к А.
А “снимает” свой ключ S3 = S2-X mod P и возвращает S3 к В.
Получатель В расшифровывает сообщение S = S3-Y mod P.
С точки зрения практической реализации, как программным, так и аппаратным способом ощутимой разницы между алгоритмами Эль Гамаля и RSA нет. Однако в криптостойкости они заметно различаются.
У алгоритма Эль Гамаля большая степень защиты, чем у алгоритма RSA достигается с тем же по размеру N, что позволяет на порядок увеличить скорость шифрования и расшифрования. Она основана на том факте, что трудно найти показатель степени, в которую нужно возвести заданное число, чтобы получить другое, тоже заданное. В общем случае эта задача дискретного логарифмирования является более трудной, чем разложение больших чисел на простые множители.Если рассматривать задачу разложения произвольного целого числа длиной 512 бит на простые множители и задачу логарифмирования целых чисел по 512 бит, вторая задача, по оценкам математиков, несравненно сложнее первой.
Однако есть одна особенность. Если в системе, построенной с помощью алгоритма RSA, криптоаналитику удалось разложить открытый ключ N одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. В случае системы, построенной с помощью алгоритма Эль Гамаля, угрозе раскрытия подвергнутся все абоненты криптографической сети.