Асимметричные криптографические системы

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

Для расшифрования данных получатель зашифрованной информации использует второй ключ, который является секрет­ным. Разумеется, ключ расшифрования не может быть определен из ключа зашифрования.

Обобщенная схема асимметричной криптосистемы с от­крытым ключом показана на рис. 26.

Рис. 26. Обобщенная схема асимметричной криптосистемы

с открытым ключом

В этой криптосистеме приме­няют два различных ключа: Кв - открытый ключ отправителя А; k_B -секретный ключ получателя В. Генератор ключей целесообразно располагать на стороне получателя В (чтобы не пересылать сек­ретный ключ k_B по незащищенному каналу). Значения ключей Кв и kв зависят от начального состояния генератора ключей.

Раскрытие секретного ключа kB по известному открытому ключу Кв должно быть вычислительно неразрешимой задачей.

Характерные особенности асимметричных криптосистем:

1. Открытый ключ Кв и криптограмма С могут быть отправ­лены по незащищенным каналам, т.е. противнику известны Кв и С.

2. Алгоритмы шифрования и расшифрования являются открытыми.

E_B: M → C,

D_B: C → M

Защита информации в асимметричной криптосистеме ос­нована на секретности ключа k_B.

У. Диффи и М. Хеллман сформулировали требования, вы­полнение которых обеспечивает безопасность асимметричной криптосистемы:

1. Вычисление пары ключей (Кв, k_B) получателем В на осно­ве начального условия должно быть простым.

2. Отправитель А, зная открытый ключ Кв и сообщение М, может легко вычислить криптограмму

С = Е_Кв(М) = Е_B(М).

3. Получатель В, используя секретный ключ k_B и криптограмму С, может легко восстановить исходное сообщение

М = D_kB (С) = D_B(C) = DB [E_B(M)].

4. Противник, зная открытый ключ Кв, при попытке вычис­лить секретный ключ k_B наталкивается на непреодолимую вычис­лительную проблему.

5. Противник, зная пару (Кв, С), при попытке вычислить ис­ходное сообщение М наталкивается на непреодолимую вычисли­тельную проблему

Однонаправленные функции. В основе асимметричных криптографических систем лежит понятие однонаправленной функции f, обладающей свойствами:

простое (не требующее больших ресурсов) вычисление значения функции y=f(x);

существование обратной функции f^-1;

сложное (требующее ресурсов за пределами возможностей современных компьютеров) вычисление значения обратной функции x=f^-1(y).

Фактически в асимметричной криптографии используется подкласс однонаправленных функций – однонаправленные функции с обходными путями, для которых обратная функция может быть вычислена так же просто, как и прямая, только если известна специальная информация об обходных путях. Эта специальная информация исполняет роль секретного ключа.

В качестве первого примера однонаправленной функции рассмотрим целочисленное умножение. Прямая задача - вычис­ление произведения двух очень больших целых чисел Р и Q, т.е. нахождение значения

N = P*Q,

является относительно несложной задачей для ЭВМ.

Обратная задача - разложение на множители большого целого числа, т.е. нахождение делителей Р и Q большого целого числа N = P*Q, является практически неразрешимой задачей при достаточно больших значениях N. По современным оценкам тео­рии чисел при целом N ≈ 2⁶⁶⁴ и P ≈ Q для разложения числа N по­требуется около 10²³ операций, т.е. задача практически неразре­шима на современных ЭВМ.

Следующий характерный пример однонаправленной функ­ции - это модульная экспонента с фиксированными основанием и модулем. Пусть А и N - целые числа, такие, что 1 ≤ А < N. Опре­делим множество Zn:

Z_N = {0,1,2,…, N-1}.

Тогда модульная экспонента с основанием А по модулю N представляет собой функцию

f_A,N : Z_N → Z_N,

f_AN (x) = A^x (mod N),

где Х - целое число, 1 ≤ х ≥ N-1.

Существуют эффективные алгоритмы, позволяющие дос­таточно быстро вычислить значения функции f_A,N (x).

Если у = А^х, то естественно записать х = log_A (у).

Поэтому задачу обращения функции f_A,N(X) называют зада­чей нахождения дискретного логарифма или задачей дискретного логарифмирования.

Задача дискретного логарифмирования формулируется следующим образом. Для известных целых A, N, у найти целое число х, такое, что

А^х mod N = у.

Алгоритм вычисления дискретного логарифма за приемле­мое время пока не найден. Поэтому модульная экспонента счита­ется однонаправленной функцией.

По современным оценкам теории чисел при целых числах А ≈ 2⁶⁶⁴ и N≈ 2⁶⁶⁴ решение задачи дискретного логарифмирова­ния (нахождение показателя степени х для известного у) потре­бует около 10²⁶ операций, т.е. эта задача имеет в 10³ раз большую вычислительную сложность, чем задача разложения на множите­ли. При увеличении длины чисел разница в оценках сложности за­дач возрастает.

Следует отметить, что пока не удалось доказать, что не существует эффективного алгоритма вычисления дискретного ло­гарифма за приемлемое время. Исходя из этого, модульная экспо­нента отнесена к однонаправленным функциям условно, что, од­нако, не мешает с успехом применять ее на практике.

Вторым важным классом функций, используемых при по­строении криптосистем с открытым ключом, являются так назы­ваемые однонаправленные функции с "потайным ходом" (с лазей­кой). Дадим неформальное определение такой функции. Функция

f: X → Y

относится к классу однонаправленных функций с "потайным хо­дом" в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление обратной функции, если известен "потайной ход" (секретное число, строка или другая ин­формация, ассоциирующаяся с данной функцией).

В качестве примера однонаправленной функции с "потай­ным ходом" можно указать используемую в криптосистеме RSA модульную экспоненту с фиксированными модулем и показателем степени. Переменное основание модульной экспоненты использу­ется для указания числового значения сообщения М либо крипто­граммы С.

Области применения. К основным применениям асимметричных криптосистем относятся:

передача ключа симметричного шифрования по открытой сети (отправитель зашифровывает этот ключ с помощью открытого ключа получателя, который только и сможет расшифровать полученное сообщение с помощью своего секретного ключа);

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

В отличие от классической симметричной криптографии криптография с открытым ключом появилась сравнительно недавно – во второй половине ХХ в. К особенностям современных асимметричных криптосистем, которые не позволяют им полностью заменить симметричные криптосистемы, относятся:

большая продолжительность процедур шифрования и расшифрования (примерно в 1000 раз больше);

необходимость использования существенно более длинного ключа шифрования для обеспечения той же криптостойкости шифра (например, симметричному ключу длиной 56 бит будет соответствовать асимметричный ключ длиной 384 бита, а симметричному ключу длиной 112 бит – асимметричный ключ длиной 1792 бита).

К наиболее известным асимметричным криптографическим системам относятся RSA, Диффи-Хеллмана, Эль-Гамаля и криптосистема на основе эллиптических кривых.