Пособие «Защита информации» (МФТИ)

Сообщение 3.2 зашифровано ключом AS и, следовательно, не может дешифровано А. Субъект А шлет документ субъекту В с блоком подписи, следующим за текстом. При получении В сначала дешифрует текст и вычисляет дайджест документа CD, затем посылает блок подписи в AS для дешифровки.

B→ AS:		B, {A, D}KAS

Сервер дешифрует блок подписи и возвращает результат В:

AS→ B:		{A, D}KB

Если возвращенный дайджест D соответствует CD, тогда субъект, упомянутый в 3.4, является отправителем подписанного текста. Если соответствия нет, это означает, что на этапах 3.1 –3.4 произошло искажение блока подписи или самого текста.

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

A→ B: { (текст)SKA }PKB

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

60

Протокол Диффи-Хеллмана

Проблема дискретного логарифма

Проблема дискретного логарифма — одна из таких задач. Пусть Zp = {0,1,…,p-1} —

поле классов вычетов по простому	модулю р,		Z *p	= U(Zp) = {1,2,…,р-1}			—
мультипликативная группа поля Zp.	Для	фиксированного а Z *p			и	заданного
произвольного у Z *p проблема дискретного		алгоритма	по	основанию	а	состоит	в

нахождении такого натурального х, что у≡ ах(mod p).

Протокол Диффи-Хеллмана открытого обмена ключей

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

1)согласовывают открыто большое простое число р и основание а Z *p (т.о., р и а известны противнику С);

2)каждый в отдельности А и В секретно выбирают достаточно большие числа хА и хВ;

3)А посылает В по открытому каналу число уА = a xА (mod p) , аналогично В посылает А

число уВ = a xВ (mod р) ;
4) получив	уВ,	А	возводит	его	в	степень	хА	и	получает
N = yВxА (mod p) = (a xВ ) хA (mod p) = a xВxA (mod p) Z *p ;
аналогично поступает В и получает число
N = yВxВ (mod p) = (a xА ) хВ (mod p) = a xАxВ (mod p) .
Это число N и является их общим секретным ключом.
Противник С знает р, а, yА = a xA ,				yВ = ахВ , передававшиеся по открытому каналу

связи. Для нахождения N = ахАхВ (все вычисления проводятся в поле Zp) С должен решить проблему Диффи-Хеллмана — по известным р, а, ахА , ахВ в поле Zp найти ахАхВ . Зная

решение проблемы дискретного логарифма (т.е. вычислив xA и хВ), легко найти N = ахАхВ . Решить проблему Диффи-Хеллмана, не прибегая к нахождению дискретного логарифма (xA, хВ), пока не удалось. Есть основания полагать, что эти проблемы эквивалентны 1

На сложности проблемы дискретного логарифма базируется безопасность алгоритма цифровой подписи (DSA — Digital Signature Algorithm), на котором основан стандарт цифровой подписи (DSS), предложенный Американским национальным институтом стандартов и технологии (NIST), в 1991г.

1 D.Boneh, R.Lipton. Algorithms for black-box fields and their applications to cryptography. Advances in Ctyptology-Crypto*’96. Springer-Verlag, 283-297.

61

Глава 22 Алгоритмы обмена ключами

22.1 DIFFIE-HELLMAN

Diffie-Hellman, первый в истории алгоритм с открытым ключом, был изобретен 1976 году [496]. Его безопасность опирается на трудность вычисления дискретных логарифмов в конечном поле (в сравнении с легк о- стью возведения в степень в том же самом поле . Diffie-Hellman может быть использован для распределения ключей - Алиса и Боб могут воспользоваться этим алгоритмом для генерации секретного ключа - но его нельзя использовать для шифрования и дешифрирования сообщений .

Математика несложна. Сначала Алиса и Боб вместе выбирают большие простые числа n и g так, чтобы g было примитивом mod n. Эти два целых числа хранить в секрете необязательно, Алиса и Боб могут договориться об из использовании по несекретному каналу . Эти числа даже могут совместно использоваться группой пол ь- зователей. Без разницы. Затем выполняется следующий протокол:

(1)Алиса выбирает случайное большое целое число x и посылает Бобу X = gx mod n

(2)Боб выбирает случайное большое целое число y и посылает Алисе Y = gy mod n

(3)Алиса вычисляет k = Yx mod n

(4)Боб вычисляет

k' = Xy mod n

И k, и k' равны gxy mod n. Никто из подслушивающих этот канал не сможет вычислить это значение, им и з- вестно только n, g, X и Y. Пока они не смогут вычислить дискретный логарифм и раскрыть x или y, они не смогут решить проблему. Поэтому, k - это секретный ключ, который Алиса и Боб вычисляют независимо .

Выбор g и n может заметно влиять на безопасность системы . Число (n-1)/2 также должно быть простым [1253]. И, самое главное, n должно быть большим: безопасность системы основана на сложности разложения на множители чисел того же размера, что и n. Можно выбирать любое g, которое является примитивом mod n; нет причин, по которым нельзя было бы выбрать наименьшее возможное g - обычно одноразрядное число. (К тому же, на самом деле, g не должно даже быть примитивом, оно только должно генерировать достаточно большую подгруппу мультипликативной группы mod n.)

Diffie-Hellman с тремя и более участниками *

Протокол обмена ключами Diffie-Hellman легко можно расширить на случай с тремя и более участниками . В приводимом примере Алиса, Боб и Кэрол вместе генерируют секретный ключ.

(1)Алиса выбирает случайное большое целое число x и вычисляет X = gx mod n

(2)Боб выбирает случайное большое целое число y и посылает Кэрол Y = gy mod n

(3)Кэрол выбирает случайное большое целое число z и посылает Алисе Z = gz mod n

(4)Алиса посылает Бобу

Z'=Zx mod n

(5)Боб посылает Кэрол *

X'=Xy mod n

(6)Кэрол посылает Алисе

Y'=Yzmod n

(7)Алиса вычисляет k = Y'x mod n

62

(8)Боб вычисляет k = Z'y mod n

(9)Кэрол вычисляет

k = :'z mod n

Секретный ключ k равен gxyz mod n, и никто из подслушивающих каналы связи не сможет вычислить это значение. Протокол можно легко расширить для четверых и более участников, просто добавляются участники и этапы вычислений.

Расширенный Diffie-Hellman

Diffie-Hellman также работает в коммутативных кольцах [1253]. З. Шмули (Z. Shmuley) и Кевин МакКерли (Kevin McCurley) изучили вариант алгоритма, в котором модуль является составным числом [1441, 1038]. В.С. Миллер (V. S. Miller) и Нил Коблиц (Neal Koblitz) расширили этот алгоритм, используя эллиптические кривые [1095, 867]. Тахер ЭльДжамаль (Taher ElGamal) использовал основополагающую идею для разработки алг о- ритма шифрования и цифровой подписи (см. раздел 19.6).

Этот алгоритм также работает в поле Галуа GF(2k) [1442, 1038]. В ряде реализаций используется именно этот подход [884, 1631, 1632], так как вычисления выполняются намного быстрее . Но и криптоаналитические вычисления выполняются намного быстрее , поэтому важно тщательно выбирать поле, достаточно большое, чтобы обеспечить нужную безопасность .

Hughes

Этот вариант алгоритма Diffie-Hellman позволяет Алисе генерировать ключ и послать его Бобу [745].

(1)Алиса выбирает случайное большое целое число x и генерирует k = gx mod n

(2)Боб выбирает случайное большое целое число y и посылает Алисе Y = gy mod n

(3)Алиса посылает Бобу X = Yx mod n

(4)Боб вычисляет z = y-1

k' = Xz mod n

Если все выполнено правильно, k = k'.

Преимуществом этого протокола над Diffie-Hellman состоит в том, что k можно вычислить заранее, до взаимодействия, и Алиса может шифровать сообщения с помощью k задолго до установления соединения с Бобом. Она может послать сообщение сразу множеству людей, а передать ключ позднее каждому по отдельности .

Обмен ключом без обмена ключом

Если у вас сообщество пользователей, каждый может опубликовать открытый ключ , X = gx mod n, в общей базе данных. Если Алиса захочет установить связь с Бобом, ей понадобится только получить открытый ключ Боба и генерировать их общий секретный ключ . Она может зашифровать сообщение этим ключом и послать его Бобу. Боб извлечет открытый ключ Алисы и вычислит общий секретный ключ .

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

Патенты

Алгоритм обмена ключами Diffie-Hellman запатентован в Соединенных Штатах [718] и Канаде [719]. Группа, называющаяся Public Key Partners (PKP, Партнеры по открытым ключам), получила вместе с другими патентами в области криптографии с открытыми ключами получила лицензию на этот патент (см. раздел 25.5). Срок действия патента США истекает 29 апреля 1997 года .

63

Распространение ключей. Протокол MTI(Мацумото Такашима Имаи).

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

begin

A:(p,g,ga) – открытые числа, a – секретное число

B:(p,g,gb) – открытые числа, b – секретное число

A --> B: gx mod p, x -- другое секретное число, выработанное A

B --> A: gy mod p, y -- другое секретное число, выработанное B

Aвычисляет: Ka = (gy)a*(gb)x mod p = gay+bx mod p

Bвычисляет: Kb = (ga)y*(gx)b mod p = gay+bx mod p

end

K = gay+bx mod p и есть ключ, совместно выработанный A и B.

Этот протокол противостоит активному криптоаналитику, что есть хорошо. Протокол не содержит аутенификации сторон, что плохо.

64

65

66

Распространение ключей. Протокол Жиро(Girault)

Т – надежный центр.

n = p*q; p, q, n – большие числа, не являются секретными. d – личный ключ надежного центра Т.

e – открытый ключ Т;

А и В хотят общаться и выбирают большие числа p и g.

Затем А выбирает секретное число a и вычисляет g a mod p . Далее: A->T: g a mod p .

Т->A: ID(A), PA = (g a mod p − ID(A))d mod n , т.е. Т шифрует разность принятого от А числа и ID(A) своим личным ключом d.

A->T: g b mod p .

T->B: ID(B), PB = (g b mod p − ID(B))d mod n , аналогично предыдущему. Остальные пользователи (если таковые имеются) поступают аналогично.

Затем:

А->B: ID(A), PA, g a mod p B->A: ID(B), PB, g b mod p

A и В вычисляют ключи KA, KB:

A:K A = (g b mod p)a mod p = g ab mod p

B:K B = (g a mod p)b mod p = g ab mod p

Чтобы исключить влияние на ключи «человека посередине», делается следующая проверка:

A: 1). Вычисляет PBe mod n , т.е. расшифровывает разность g b mod p − ID(B) открытым ключом надежного центра;

2). Получив от В числа ID(B) и g b mod p , A вычисляет их разность и сравнивает их с расшифрованным значением.

В: поступает аналогично.

67

Шамир и Блом

Схема Блома(Blom).

T – это некий центр, надежный.

Пусть существует n участников u1 ,...,un .

1.Инсталяция

Что делает T:

1) Выбирает случайно многочлен от двух переменных:

	k	k
	F(x, y) = ∑ ∑aijxi yj		;
	j=0	i=0
	где aij , x, y, Z p (поле целых чисел по модулю p, где p - простое)
	aij Z p ; aij = a ji ← случайны.
2) Выбирает открытые ключи r ,..., r , r Z						p	i ≠ j	r	≠ r .
			1	n	i			i	j
	Далее T отправляет всем ui :
		k	k
	y Fq1 (x) = F(x, r1 ) = ∑ ∑aij xi r1 j				- отправляется к u1 .
		j=0	i=0
	y ………………………………………………
		k	k
	y Fn (x) = F(x, rn ) = ∑ ∑aij xi rn j				- отправляется к un .
		j=0 i=0
		2.Рабочий режим
Пусть us	и um хотят выработать общий ключ.
			k	k
yus вычисляет ksm		= Fs (rm ) = ∑ ∑aij rmi rs j mod p
			j =0	i =0
			k	k
yum вычисляет kms		= Fmm (rs ) = ∑ ∑aij rs i rm j mod p
			j =0	i =0
В итоге,	kms = ksm - общий ключ для дальнейшей работы, так как aij = aji .
				3.Атака
Если ua	пытается выдать себя за us , то есть найти

x0 : Fa (x0 ) = ksm - решается перебором (иногда такого x0 вообще не существует).

68

Глава 23 Специальные алгоритмы для протоколов

23.1 Криптография с несколькими открытыми ключами

Это обобщение RSA (см. раздел 19.3) [217, 212]. Модуль n является произведением двух простых чисел p и q. Однако вместо e и d, для которых ed ≡ 1 mod ((p-1)(q-1)), выбирается t ключей Ki, для которых выполняется

K1* K2*. . . *Kt ≡ 1 mod ((p-1)(q-1)) Òàê êàê

M K1*K2 *...*Kt = M

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

Если, например, используется пять ключей, то сообщение, зашифрованное ключами K3 è K5, может быть расшифровано с помощью K1, K2 è K4.

C = M K3 *K5 mod n

M = C K1*K2 *K4 mod n

Одним из применений этой схемы является подписание документа несколькими людьми . Представим ситуацию, когда для того, чтобы документ был действителен, он должен быть подписан и Алисой, и Бобом . Используются три ключа: K1, K2 è K3. Алиса и Боб получают по одному ключу из первых двух , а третий опубликовывается.

(1)Сначала Алиса подписывает M и посылает его Бобу.

M' = M K1 mod n

(2)Боб может восстановить M по M'.

M = M 'K3*K5 mod n

(3)Он может также добавить свою подпись .

M'' = M 'K2 mod n

(4)Проверить подписи можно при помощи открытого ключа K3.

M = M ' 'K3 mod n

Обратите внимание, что для работоспособности этой системы нужна заслуживающая доверия сторона, кот о- рая установила бы систему и выдала ключи Алисе и Бобу . Та же проблема существует и в схеме [484]. Более тонкая схема описана в [695, 830, 700], Но усилия, предпринимаемые для проверки, пропорциональны колич е- ству подписывающих. Новые схемы [220, 1200], основанные на схемах идентификации с нулевым знанием, преодолевают эти недостатки предшествующих си стем.

23.2 Алгоритмы разделения секрета

В разделе 3.7 я рассматривал идею, используемую в схемах разделения секрета . Четыре приведенных ниже различных алгоритма представляют собой частные случаи общего теоретического подхода [883].

Схема интерполяционных многочленов Лагранжа

Для создания пороговой схема Ади Шамир воспользовался уравнениями для многочленов в конечном поле [1414]. Выберем простое число p, которое больше количества возможных теней и больше самого большого из возможных секретов. Чтобы сделать секрет общим, сгенерируем произвольный многочлен степени m-1. Например, если нужно создать пороговую схему (3,n) (для восстановления M потребуется три тени), генерируется квадратичный многочлен

(ax2 + bx + M) mod p

где p - это случайное простое число, большее любого из коэффициентов . Коэффициенты a и b выбираются случайным образом, они хранятся в тайне и отбрасываются после того, как распределяются тени . M - это сообщение. Простое число должно быть опубликовано . Тени получаются с помощью вычисления многочлена в n различных точках:

69