1976 год считается годом рождения несимметричной криптографии. В этом году американскими математиками Вайтфилдом Диффи, Мартином Хеллманом и Ральфом Меркле была представлена идеология криптосистемы с открытым ключом.

Кардинальное отличие криптосистемы с открытым ключом (по другой терминологии, несимметричной системы) от симметричной системы состоит в том, что в криптосистемах с открытым ключом процедура зашифровывания становится общедоступной. Это, однако, не означает как в традиционных системах шифрования, что общедоступной является и процедура расшифровывания. Понятие ключа разбивается на две части (включает теперь два понятия): ключ открытый, и ключ тайный. Общедоступный открытый ключ используется для зашифровывания, но расшифровывание может осуществить только тот, кто владеет тайным ключом.

Именно как раз в допущении того, что нахождение ключа расшифровывания по известному ключу зашифровывания может быть сложно-вычислимой задачей, и заключается идея, которая определила дальнейшее направление развития криптографии.

В настоящее время в несимметричной криптографии наиболее широкое распространение получили системы RSA, Эль-Гамаля и Эль-Гамаля на эллиптических кривых.

RSA-система

RSA – криптографическая система открытого ключа, обеспечивающая такие механизмы защиты как шифрование и цифровая подпись (аутентификация – установление подлинности). Криптосистема RSA разработана в 1977 году и названа в честь ее разработчиков Ronald Rivest, Adi Shamir и Leonard Adleman.

Алгоритм RSA работает следующим образом: берутся два достаточно больших простых числа p и q и вычисляется их произведение n = p*q; n называется модулем.

Затем выбирается число e, удовлетворяющее условию 1< e < (p - 1)*(q - 1) и не имеющее общих делителей кроме 1 (взаимно простое) с числом (p - 1)*(q - 1).

Затем вычисляется число d таким образом, что (e*d - 1) делится на (p - 1)*(q – 1), где

e – открытый (public) показатель

d – секретный (private) показатель.

(n; e) – открытый (public) ключ

(n; d) – секретный (private) ключ.

Делители (факторы) p и q можно либо уничтожить либо сохранить вместе с секретным (private) ключом.

Если бы существовали эффективные методы разложения на сомножители (факторинга), то, разложив n на сомножители (факторы) p и q, можно было бы получить секретный (private) ключ d. Таким образом надежность криптосистемы RSA основана на трудноразрешимой – практически неразрешимой – задаче разложения n на сомножители (то есть на невозможности факторинга n) так как в настоящее время эффективного способа поиска сомножителей не существует.

Ниже описывается использование системы RSA для шифрования информации (отметим, что создание цифровых подписей на основе RSA несколько отличается; о создании цифровых подписей на основе RSA можно прочесть на странице «Цифровая подпись» текущего раздела).

Предположим, Корреспондент 1 хочет послать Корреспонденту 2 сообщение M. Для этого Корреспондент 1 создает зашифрованный текст С, возводя сообщение M в степень e и умножая на модуль n: C = M**e* (mod n), где e и n – открытый (public) ключ Корреспондента 2. Затем Корреспондент 1 посылает С (зашифрованный текст) Корреспонденту 2. Чтобы расшифровать полученный текст, Корреспондент 2 возводит полученный зашифрованный текст C в степень d и умножает на модуль n: M = c**d*(mod n); зависимость между e и d гарантирует, что Корреспондент 2 вычислит M верно. Поскольку только Корреспондент 2 знает d, то только он имеет возможность расшифровать полученное сообщение.

Система Эль-Гамаля

Схема Эль-Гамаля, предложенная в 1985 г., может быть использована как для шифрования, так и для цифровой подпии. Безопасность схемы Эль-Гамаля обусловлена сложностью вычисления дискретных логарифмов в конечном поле.

Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G < Р. Числа Р и G могут быть распространены среди группы пользователей.

Затем выбирают случайное целое число X, причем Х<Р. Число Х является секретным ключом и должно храниться в секрете.

Далее вычисляют Y = GX mod P. Число Y является открытым ключом.

Для того чтобы зашифровать сообщение М, выбирают случайное целое число К, 1<К<Р -1, такое, что числа К и (Р-1) являются взаимно простыми.

Затем вычисляют числа:

a = G^K (mod P),

b = Y^K М (mod P).

Пара чисел (а,b) является шифртекстом. Заметим, что длина шифртекста вдвое больше длины исходного открытого текста М.

Для того чтобы расшифровать шифртекст (а,b), вычисляют

М = b / a^X (mod Р). (*)

Поскольку

b / a^X = Y^K M / a^X = G^KX M / G^KX = M (mod P),

то соотношение (*) справедливо.

В реальных схемах шифрования необходимо использовать в качестве модуля Р большое целое простое число, имеющее в двоичном представлении длину 512 - 1024 бит.