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

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

Надежность алгоритма основывается на трудности факторизации больших чисел в произведение простых множителей. В криптосистеме RSA открытый ключ Кв, секретный ключ kв, сообщение М и криптограмма С принадлежат множеству целых чисел Z_N = {0, 1, 2, ..., N – 1}, где N – модуль N = PQ. Здесь P и Q – случайные большие простые числа. Для обеспечения максимальной безопасности выбирают P и Q равной длины и хранят в секрете. Открытый ключ Кв выбирают случайным образом так, чтобы выполнялись условия: 1 < Кв £ j(N), НОД(Кв, j (N)) = 1, j(N) = (P – 1) (Q – 1), где j(N) – функция Эйлера. Второе из указанных выше условий означает, что открытый ключ Кв и значение функции Эйлера j(N) должны быть взаимно простыми. Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ kв, такой, что

kв = Кв–1 [mod(P – 1)(Q – 1)]. (6.1)

Это можно осуществить, так как при известной паре простых чисел (P, Q) можно легко найти j(N). Заметим, что kв и N должны быть взаимно простыми. Открытый ключ Кв используют для шифрования данных, а секретный ключ kв – для расшифрования.

Преобразование шифрования определяет криптограмму С через пару «открытый ключ Кв, сообщение М» в соответствии со следующей формулой:

C = (mod N). (6.2)

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

М = (mod N). (6.3)

Таким образом, получатель, который создает криптосистему, защищает два параметра: секретный ключ kв и пару чисел (P, Q), произведение которых дает значение модуля N. С другой стороны, отправителю известны значения модуля N и открытого ключа Кв. Противнику известны лишь значения Кв и N. Если бы он смог разложить число N на множители P и Q, то он узнал бы тройку чисел {P, Q, Кв}, вычислил бы значение функции Эйлера j(N) = (P –1)(Q – 1) и определил значение секретного ключа kв.

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

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

Для того чтобы генерировать пару ключей (открытый ключ – секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G < P. Числа Р и G могут быть распространены среди группы пользователей. Затем выбирают ключ X – случайное целое число, причем X < P. Число X является секретным ключом и должно храниться в секрете. Далее вычисляют Y = G^X mod P. Число Y является открытым ключом.

Для того чтобы зашифровать сообщение M, выбирают случайное целое число 1 < K< P – 1, такое, что числа К и (Р – 1) являются взаимно простыми. Затем вычисляют числа a = G^K mod P, b = Y^K M mod P. Пара чисел (a, b) является шифротекстом. Длина шифротекста вдвое больше длины исходного открытого текста М.

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

M = b/a^X mod P. (6.4)

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

- генерация новых секретных и открытых ключей основана на генерации новых больших простых чисел, а проверка простоты чисел занимает много процессорного времени;

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

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

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

Если пользователь А хочет передать зашифрованное комбинированным методом сообщение М пользователю В, то порядок его действий будет таков:

1 Создать (например, сгенерировать случайным образом) симметричный ключ, называемый в этом методе сеансовым ключом Кс.

2 Зашифровать сообщение М на сеансовом ключе Кс.

3 Зашифровать сеансовый ключ Кс на открытом ключе Кв пользователя В.

4 Передать по открытому каналу связи в адрес пользователя В зашифрованное сообщение вместе с зашифрованным сеансовым ключом.

Действия пользователя В при получении зашифрованного сообщения и зашифрованного сеансового ключа должны быть обратными:

5 Расшифровать на своем секретном ключе kв сеансовый ключ Кс.

6 С помощью полученного сеансового ключа Кс расшифровать и прочитать сообщение М.

При использовании комбинированного метода шифрования можно быть уверенным в том, что только пользователь В сможет правильно расшифровать ключ Кс и прочитать сообщение М.

Комбинированный метод шифрования является наиболее рациональным, объединяя в себе высокое быстродействие симметричного шифрования и высокую криптостойкость, гарантируемую системами с открытым ключом.