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

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

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

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

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

В этой криптосистеме применяют два различных ключа: К_B - открытый ключ получателя В, которым будет шифровать отправитель A; k_В - секретный ключ получателя В. Генератор ключей целесообразно располагать на стороне получателя В (чтобы не пересылать секретный ключ К_В по незащищенному каналу). Значения ключей К_В и k_В зависят от начального состояния генератора ключей.

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

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

1. Открытый ключ К_В и криптограмма С могут быть отправлены по незащищенным каналам, т.е. противнику известны К_В и С.
2. Алгоритмы шифрования и расшифрования Е_В: М → С, D_В: C → M являются открытыми.

Защита информации в асимметричной криптосистеме основана на секретности ключа К_В. У. Диффи и М. Хеллман сформулировали требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы:

1. Вычисление пары ключей (К_В, k_В) получателем В на основе начального условия должно быть простым.
2. Отправитель А, зная открытый ключ К_В и сообщение М, может легко вычислить криптограмму С=Е_КB(М)=Е_В(М).
3. Получатель В, используя секретный ключ k_В и криптограмму С, может легко восстановить исходное сообщение М=D_kВ(С)=D_B(C)=D_B[E_B(M)].
4. Противник, зная открытый ключ К_В, при попытке вычислить секретный ключ k_В наталкивается на непреодолимую вычислительную проблему.
5. Противник, зная пару (К_В, С), при попытке вычислить исходное сообщение М наталкивается на непреодолимую вычислительную проблему.

Концепция асимметричных криптографических систем с открытым ключом основана на применении однонаправленных функций. Неформально однонаправленную функцию можно определить следующим образом. Пусть Х и Y - некоторые произвольные множества. Функция

f: X → Y

является однонаправленной, если для всех х  Х можно легко вычислить функцию

y=f(x), где y Y.

И в то же время для большинства y Y достаточно сложно получить значение х Х, такое, что f(x)=y (при этом полагают, что существует по крайней мере одно такое значение х).

Основным критерием отнесения функции f к классу однонаправленных функций является отсутствие эффективных алгоритмов обратного преобразования Y → X.

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

N = P * Q,

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

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

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

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

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

,

где x - целое число, 1≤ x≤ N-1.

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

Если , то естественно записать .

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

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

                                                                                                              

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

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

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

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

f: X → Y

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

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

Алгоритм RSA

Алгоритм RSA предложили в 1977г. три автора Р. Райвест (Rivest), А. Шамир (Shamir) и А. Адлеман (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов. Алгоритм RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.

Надежность алгоритма основывается на трудности факторизации больших чисел и трудности вычисления дискретных логарифмов.

В криптосистеме RSA открытый ключ К_В, секретный ключ k_B, сообщение М и криптограмма С принадлежат множеству целых чисел

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

где N - модуль: N = P*Q.

Здесь Р и Q - случайные большие простые числа. Для обеспечения максимальной безопасности выбирают Р и Q равной длины и хранят в секрете.

Множество Z_N с операциями сложения и умножения по модулю N образует арифметику по модулю N.

Открытый ключ К_В выбирают случайным образом так, чтобы выполнялись условия:

,

,

где  - функция Эйлера.

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

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

Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ k_B, такой, что

k_B * К_B = 1 (mod()

или

k_B=K_B^-1(mod(P-1)(Q-1)).

Это можно осуществить, так как получатель В знает пару простых чисел (P,Q) и может легко найти .

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

,

В качестве алгоритма быстрого вычисления значения С используют ряд последовательных возведений в квадрат целого М и умножений на М с приведением по модулю N.

Обращение функции , т.е. определение значения М по известным значениям С, К_B и N практически неосуществимо при N ≈ 2⁵¹².

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

.

Процесс расшифрования можно записать так:

D_B(Е_B (М)) = М.

Подставляя в D_B(Е_B (М)) = М значения  и , получаем:

Или

Таким образом, если криптограмму

возвести в степень k_B, то в результате восстанавливается исходный открытый текст М, так как

. (15)

Таким образом, получатель В, который создает криптосистему, защищает два параметра: секретный ключ k_B и пару чисел (P,Q), произведение которых дает значение модуля N. С другой стороны, получатель В открывает значение модуля N и открытый ключ К_B.

Противнику известны лишь значения К_B и N. Если бы он смог разложить число N на множители Р и Q, то узнал бы "потайной ход" - тройку чисел {Р,Q, k_B}, вычислил значение функции Эйлера

. (16)

и определил значение секретного ключа k_B.

Однако, как уже отмечалось, разложение очень большого N на множители вычислительно неосуществимо (при условии, что длины выбранных Р и Q составляют не менее 100 десятичных знаков).