Иванов М.А. КМЗИ сети

последовательного возведения в квадрат, т.е. после каждого возведения в квадрат результат берется по модулю r. При этом ни-

когда не возникают числа большие n2 [3].

5.7. Криптосистема Эль-Гамаля

Криптосистема Эль-Гамаля – асимметричная криптографическая схема шифрования, предложенная Тахиром Эль-Гамалем в

1984 г. (Taher ElGamal, «A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms», IEEE Transactions on Information Theory, v. IT-31, n. 4, 1985, pp. 469–472).

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

Алгоритм генерации ключей:

1)породить мультипликативную циклическую группу G степени q с образующей g:

выбрать простое число q – степень криптосистемы; сформировать случайное g, g < q;

2)выбрать случайное x, x < q;

3)вычислить h = gx mod q.

Открытый ключ = (h, g, q). Закрытый ключ = x. Алгоритм зашифрования:

1)подготовить шифруемое сообщение m, m < q;

2)выбрать случайное y, y < q;

3)вычислить с1 = gx mod q, c2 = m h y mod q.

Криптограмма – (с1, с2). Алгоритм расшифрования:

Расшифрование будет верным, поскольку

171

Криптостойкость системы Эль-Гамаля зависит от свойств группы G и особенностей конкретной реализации. Схема уязвима к атакам с подобранным шифротекстом. К примеру, имея криптограмму (с1, с2) некоторого (возможно, неизвестного) сообщения m, легко создать криптограмму (с1, 2с2) сообщения 2m.

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

5.8. Гибридные криптосистемы

Несмотря на все преимущества криптосистем с открытым ключом, ни одна из известных на сегодняшний день их реализаций не может конкурировать по быстродействию с криптосистемами с секретным ключом. Так, например, быстродействие системы RSA в тысячи раз ниже быстродействия DES. В результате при шифровании длинных информационных последовательностей может случиться так, что применение асимметричного алгоритма недопустимо снижает скорость информационного обмена, а применение симметричного невозможно из-за отсутствия общего секретного ключа у участников этого обмена или по каким-то другим причинам. Выходом из этой ситуации является использование гибридной криптосистемы (рис. 5.6, 5.7).

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

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

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

k public и закрытого k secret . Рассмотрим процесс пересылки не-

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

172

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

Рис. 5.6. Первый вариант схемы гибридного шифрования

173

5.9. Генераторы ПСЧ на основе односторонних функций с секретом

Криптографически стойкие генераторы ПСЧ могут быть построены на основе односторонних функций с секретом. М. Блюм и С. Микали для обозначения основного требования к криптостойкому генератору ПСЧ ввели понятие непредсказуе-

мость (unpredictable) или непредикативность влево – криптоа-

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

Справедливы следующие утверждения [3, 4]:

непредикативный влево генератор является криптографически сильным; криптографически сильные генераторы существуют то-

гда и только тогда, когда существуют односторонние функции.

Рассмотрим, например, так называемый ВВS-генератор, получивший свое название в честь авторов Э. Блюм, М. Блюма и М. Шуба, основанный на криптосистеме Блюма.

Пусть p и q – два больших простых числа примерно одинакового размера, причем

p { mod 4, q { mod 4.

~*

Тогда число n = pq называется целым числом Блюма. Пусть Zn

– множество целых положительных чисел, меньших n, которые

~*

не делятся ни на p, ни на q. Пусть QRn – подмножество Zn , со-

стоящее из квадратичных вычетов по модулю n. Число элемен-

~*

тов множества Zn равно (p – 1)(q – 1), причем в точности чет-

вертую их часть составляют элементы подмножества QRn.Каждый элемент QRn имеет ровно четыре различных квадратных

~*

корня в Zn , из них лишь один, называемый примитивным, принадлежит QRn.

175

133 19 7 Z437,135 Z437,139 Z437;

кроме того, учитывая, что не существует такого целого числа a, что

a2 { 35 mod 437,

а

242 { 39 mod 437,

можно записать

135 QR437,139 QR437.

Квадратными корнями из 139 по модулю 437 являются числа 24, 185, 252 и 413, при этом 24 – примитивный квадратный корень, так как

472 24 mod 437.

Задача определения примитивных квадратных корней по модулю числа n вычислительно эквивалентна задаче разложения этого числа на множители. Таким образом, получаем кан-

дидата на одностороннюю функцию с секретом, поскольку функция

f x x2 mod n

эффективно вычисляется, а произвести обратное преобразование может лишь тот, кто знает секрет – разложение n на множители.

Пусть n – целое число Блюма.

Генератор Э. Блюм–М. Блюма–Шуба

1.Выберем в качестве инициализирующего вектора слу-

чайное число x0 QRn. Для этого возьмем такое случайное число x, что x, n 1, и вычислим

x0 x2 mod n.

2.Искомой последовательностью бит длиной m будет последовательность

BBSn, m x0 b0b1b2 ... bi ... bm 1, i 0, m 1 ,

где bi – младший бит числа xi ,

176

Важным достоинством этого генератора является то, что при знании разложения n на множители он допускает прямое определение отдельных бит, которые в нем вырабатываются. Имеем

По теореме Эйлера

x p 1 q 1 {1 mod n,

а значит,

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

жет быть найдено исходя лишь из начального вектора x0 и

индекса i.

Аналогичным образом можно построить генератор ПСЧ на основе другой односторонней функции с секретом, например лежащей в основе криптосистемы RSA, т.е. на основе функции

f x xe mod n.

Генератор RSA

1.Выберем в качестве инициализирующего вектора случайное число x0 Zn*.

2.Искомой последовательностью бит длиной m будет являться последовательность

RSAn, m x0 b0 b1 b2 ... bi ... bm 1, i 0, m 1 ,

где bi – младший бит числа xi ,

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

177

Пусть исходное сообшение M суть m-разрядная битовая последовательность, x0 – случайный квадратичный вычет по мо-

дулю n. Функция зашифрования по схеме Гольдвассер–Микали имеет вид

c xm, M BBSn, m x0 ,

при этом xm включается в шифротекст для того, чтобы закон-

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

xi xi 1 mod n,

а затем получении исходного текста по формуле

M c BBSn, m x0 .

Знание множителей p и q позволяет законному получателю сразу из xm получить x0 , а затем формировать ПСП точно так

же, как это делал отправитель.

Алгоритм вычисления x0 из xm

1. С помощью обобщенного алгоритма Евклида вычисляем такие целые числа a и b, что

ap bq 1. 2. Вычисляем

Таким образом, эффективность рассмотренной схемы выше эффективности схемы RSA. Более того, тщательный анализ BBS-генератора показал, что после каждой операции модуль-

178

ного возведения в квадрат можно использовать приблизительно log2 L младших битов числа xi , где L – разрядность модуля n [3].

Контрольные вопросы

1.Кто инициатор создания двухключевой криптосистемы: отправитель или получатель?

2.Назовите два принципиальных недостатка двухключевых криптосистем.

3.Что такое односторонняя функция? Приведите пример.

4.Что такое односторонняя функция с секретом? Приведите пример.

5.На чем основана стойкость криптосистемы RSA?

6.Приведите пример создания криптосистемы RSA.

7.На чем основана стойкость ранцевой криптосистемы?

8.На чем основана стойкость криптосистемы Эль-Гамаля?

9.Приведите пример создания криптосистемы Эль-Гамаля.

179

ГЛАВА 6. КРИПТОГРАФИЧЕСКИЕ ПРОТОКОЛЫ

Успешное решение задачи открытого распределения ключей, создание практических схем цифровой подписи способствовали возникновению нового направления криптографии – теории

криптографических протоколов. Для современных информаци-

онных систем характерен перевод всего документооборота в электронную форму. Возникающие при этом проблемы чаще всего могут быть решены только с использованием возможностей криптографии. Типичный пример: взаимодействуют два удаленных абонента А (клиент банка) и В (банк). Абонент А хочет доказать абоненту В, что он тот, за кого себя выдает, а не злоумышленник. Для решения этой задачи требуется протокол аутентификации абонента. В каждом конкретном случае для решения некой задачи, связанной с обеспечением безопасности пересылаемых электронных документов, требуется использование соответствующих криптографических протоколов, которые за последние годы превратились в основной объект исследований криптографии. Материал данной главы в значительной степени основывается на работе [4].

6.1. Основные понятия

Объект изучения теории криптографических протоколов – удаленные абоненты, взаимодействующие по открытым каналам связи. Цель взаимодействия – решение какой-либо практической задачи. Модель предусматривает наличие противника, преследующего собственные цели. Противник может выдавать себя за законного субъекта взаимодействия, вмешиваться в информационный обмен между абонентами и т.п. Участники протокола в общем случае не доверяют друг другу, иначе говоря, некоторые протоколы должны быть рассчитаны на ситуацию, когда противником может оказаться даже один из абонентов или несколько абонентов, вступивших в сговор. В настоящее время известно несколько десятков различных типов протоколов. Все эти типы можно разделить на две группы:

180