Криптографические протоколы - Lection

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

Будем полагать, что участники A и B обладают некоторой общей числовой функцией z = f(x, y), x, y, z X, X {Zp, F, Zn, . . .}.

Протокол 3 .

1.B формирует rB R X и посылает rB участнику A.

2.A вырабатывает rA R X, KA R K, формирует набор wA = (KA, rA, rB, idB), шифрует его: mA = EKAB (wA) и пару (rA, mA) посылает B.

3.B расшифровывает mA, по параметру rB аутентифицирует участника A, вырабатывает KB R K, формирует набор wB = (KB, rA, rB, idA), шифрует его и величину mB = EKAB (wB) посылает A.

4.A расшифровывает mB и по параметру rA аутентифицирует участника B.

При успешной взаимной аутентификации участники A и B, используя общую функцию f(x, y), смогут выработать общий сеансовый ключ K = f(KA, KB).

Замечание. Параметры rA и rB несекретные и необходимы для взаимной аутентификации участников A и B. Параметры KA и KB секретные и служат для выработки общего секретного ключа.

Следующий протокол представляет собой “бесключевой” протокол передачи секретного ключа. Предполагается, что A и B обладают шифровальными алгоритмами (функциями): (EA, DA) и (EB, DB). Эти функции должны удовлетворять следующим условиям:

a)область определения и область значений каждой функции совпадают и эта область общая для всех функций;

b)EAEB = EBEA, DAEB = EBDA, DBEA = EADB.

Протокол 4 .

1.A вырабатывает K R K и yA = EA(K) посылает B.

2.B вычисляет величину zB = EB(yA) и посылает её A.

3.A вычисляет величину wA = DA(zB) = EB(K) и посылает её B.

4.B вычисляет общий сеансовый секретный ключ K = DA(wA).

Замечание. Стойкость протокола 4 зависит от выбора криптосистем. Например, если EA = DA и EB = DB функции, реализующие алгоритмы бинарного гаммирования, то

yA = A K,

zB	=	B K A,
wA	=	B K.

Поэтому злоумышленник сможет вычислить секретный ключ K = yA zB wA.

41

Трёхсторонние протоколы

В этих протоколах предполагается наличие доверенного центра S. Центр хранит секретные ключи всех участников данного информационного взаимодействия.

Будем предполагать, что каждый из участников A и B имеет долговременные секретные ключи для обмена конфиденциальной информацией с центром S KAS и KBS соответственно.

Протокол Нидхема-Шрёдера. (R.M. Needham, M.D. Schroeder)

1.A вырабатывает rA R X, формирует запрос mA = (idA, idB, rA) и посылает его центру S.

2.Центр S вырабатывает сеансовый секретный ключ K R K, формирует набор mS = (rA, idB, K, EKBS (K, idA)), шифрует его: wS = EKAS (ms) и посылает wS участнику A.

3.A расшифровывает ws, проводит аутентификацию центра S по параметру rA и yB = EKBS (K, idA) посылает B.

4.B расшифровывает yB, вырабатывает параметр rB R X, шифрует его на ключе K : wB = EK (rB) и посылает wB участнику A.

5. A расшифровывает	wB на ключе K, определяет rB, вычисляет величину
zA = ψ(rB), где ψ	некоторая заранее выбранная числовая функция, шиф-

рует zA и wA = EK (zA) посылает B.

6.B расшифровывает wA, вычисляет ψ(rB) и сравнивает ψ(rB) с zA, тем самым аутентифицируя участника A.

Замечание. Если происходит компрометация сеансового ключа K, то противник C может осуществить следующую атаку:

1.На шаге 3 противник C повторно посылает B сообщение yB.

2.На шаге 4 противник C перехватывает wb и на шаге 5, зная K и ψ, аутентифицируется под видом A.

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

Этот недостаток устранён в протоколе Kerberos.

Базовый протокол Kerberos

Протокол Kerberos является протоколом проверки подлинности с доверенным центром для сетей TCP/IP. Kerberos был разработан в MIT для проекта Athena и основан на протоколе Нидхема-Шрёдера.

A. Предварительные условия.

42

1.Существует доверенный центр S 0 . Центр регистрирует всех участников информационного взаимодействия и выдаёт им идентификаторы.

2.Центр выдаёт каждому участнику A долговременный секретный ключ KAS для конфиденциального взаимодействия с центром.

3.Каждый участник имеет генератор случайных чисел из некоторого множества X.

B. Описание базового протокола.

1.A вырабатывает rA R X, формирует запрос mA = (idA, idB, rA) на получение “мандата” (credentials) для информационного взаимодействия с участником B и посылает его в центр S 0 .

2. S 0 генерирует секретный сеансовый ключ K R K, вычисляет “билет” (ticket) yB = EKBS (K, idA, T ) для участника A на информационное взаимодействие с B и вычисляет мандат mS = EKAS (K, rA, T, yB). Здесь T время действия мандата. Затем mS посылается участнику A.

3.A расшифровывает mS, аутентифицирует центр S 0 по параметру rA , вырабатывает KA R K и вычисляет аутентификатор Aut = Ek(idA, t, KA). Затем пара (Aut, yB) посылается участнику B.

4.B из билета yB определяет сеаносвый секретный ключ K. Затем из аутентификатора Aut определяет параметры KA, idA, и t и тем самым, в частности, аутентифицирует A по параметру idA. После этого B вырабатывает KB R K и mB = EK (t, KB) посылает участнику A.

5.A расшифровывает mB и по параметру t аутентифицирует B. Кроме того, на основе KA и KB участники A и B могут самостоятельно выработать общий секретный ключ KAB = f(KA, KB).

Замечание. В описанном базовом протоколе Kerberos к центром S 0 обращается участник A инициатор информационного взаимодействия с участником B. Этот протокол можно модифицировать для случая, когда обмениваться информацией с центром S 0 предпочтительнее участнику B.

С. Описание модифицированного базового протокола.

1.	A вырабатывает rA, r R X, вычисляет xA	=	EKAS (rA, r, idA, idB)	и запрос
	mA = (r, idA, idB, xA) посылает B.
2.	B вырабатывает rB R X, вычисляет xB	=	EKBS (rB, r, idA, idB)	и запрос
	mB = (r, idA, idB, xA, xB) посылает центру S 0 .

3.S 0 расшифровывает xA и xB, проводит аутентификацию участников A и B по параметрам idA и idB и аутентифицирует сеанс связи по параметру r ( r мо-

жет быть меткой времени). Затем S 0 вырабатывает сеансовый секретный ключ

K R K, вычисляет величины yA = EKAS (rA, K) и yB = EKBS (rB, K) и посылает их B.

43

4. B расшифровывает yB и по параметру rB аутентифицирует центр S 0 . После этого yA он посылает A.

5.A расшифровывает yA, аутентифицирует S 0 по параметру rA и получает сеансовый ключ K.

Этот протокол можно несколько модифицировать, что позволит провести взаимную аутентификацию участников A и B.

Для этого на шаге 4 участник B вырабатывает rB R X и посылает A пару (yA, zB = EK (r, rB)). На шаге 5 участник A расшифровывает yA, расшифровывает на секретном ключе K сообщение zB и по параметру r аутентифицирует участника B. Затем A вычисляет величину zA = EK (r) и посылает её B. Кроме этого, к протоколу добавляется шаг

6. B расшифровывает zA и аутентифицирует участника A по параметру r.

Полный протокол Kerberos

Предполагается, что в информационной структуре имеется S0 главный сервер (доверенный центр, сервер аутентификации (authentication server)). На этом сервере хранятся долговременные ключи пользователей участников информационного взаимодействия. Кроме того, имеются вспомогательные серверы S1, . . . , Sk, k > 1. На этих серверах вырабатываются сеансовые ключи. Эти ключи могут быть разделены на классы (realms), соответствующие подсетям или различным сетевым ресурсам. Серверы S1, . . . , Sk “серверы выдачи билетов” для доступа к сетевым ресурсам и обращений к другим пользователем.

Описание полного протокола Kerberos для двух серверов S0 и S1.

1.A вырабатывает rA R X и формирует запрос mA = (rA, idA, idS1, idB) к серверу S0 на получения сеансового ключа K для конфиденциального взаимодействия

с участником B.

2.S0, получив запрос, проверяет легальность пользователей idA и idB и с помощью ключей KAS1 , KBS1 , KS0S1 вычисляет величины

xA = EKAS0 (KAS1 , rA, T1, idS1), yA = EKS0S1 (KAS1 , KBS1 , rA, T1), xB = EKBS1 (KBS1 , idA, rA, idS1).

Здесь T1 время действия ключей KAS1 и KBS1 . Величины xA, yA посылаются участнику A, а величина xB участнику B.

3.A расшифровывает xA, аутентифицирует сервер S0 по параметру rA и на осно-

ве KAS1 вычисляет аутентификатор Aut1 = EKAS1 (idA, T 1). После этого пара (Aut1, yA) посылается серверу S1.

44

4. Сервер S1 на основе ключа KS0S1 расшифровывает yA, получает ключ KAS1 и на основе этого ключа расшифровывает Aut1 и по параметру idA аутентифици-

рует участника A. Затем S1	генерирует сеансовый ключ K R K и вычисляет
величины
zA	=	EKAS1		(K, rA, T2, idB),
zB	=	EKBS		(K, T2, idA, idS1).
			1

Здесь T2 время действия сеаносового ключа. Пара (zA, zB) посылается A.

5.A расшифровывает zA и аутентифицирует сервер S1 по параметру rA. Затем A вырабатывает KA R K и вычисляет аутентификатор Aut2 = EK (idA, T2, KA). Пара (Aut2, zB) посылается B.

6.B расшифровывает xB и определяет ключ KBS1 и idS1. Затем он расшифровывает zB и по параметру idS1 аутентифицирует сервер S1. После этого B расшифровывает Aut2 и по параметрам idA и T2 аутентифицирует участника A. Далее B вырабатывает KB R K и величину yB = EK (T1, KB, KA) посылает A.

7.A расшифровывает yB и по параметрам T2 и KA аутентифицирует участника B.

Замечание. После выполнения этого протокола участники A и B получают секретный сеансовый ключ K и, кроме того, у каждого из них есть секретная пара (KA, KB). На основе этой пары они могут самостоятельно выработать дополнительный секретный ключ (не обращаясь при этом к S0 и S1 ).

Депонирование ключей и возможность контроля информационного взаимодействия

Рассмотрим следующую вполне реальную проблему, возникающую при информационном взаимодействии. В различных ситуациях государственным (судебным) органам может потребоваться конфиденциальная (зашифрованная) информация участника A информационного взаимодействия, передаваемая и получаемая им в процессе этого взаимодействия. Такую проблему можно решить с помощью протокола, предложенного Микали (S. Micali). Этот протокол предполагает наличие центра C распределения ключей (ЦРК), который хранит и распределяет открытые ключи, и группы доверенных пользователей D1, D2, . . . , Dn. Введение этой группы позволяет решить поставленную проблему.

Описание протокола депонирования ключей

Все вычисления проводятся в некоторой циклической группе G порядка n; g образующий элемент этой группы. Параметры G и g общедоступны.

1.A выбирает x1, x2, . . . , xn R Zn и вычисляет k = x1 + x2 + · · · + xn. k это секретный ключ A. Затем A вычисляет

y = gk, yi = gxi, i = 1, n.

45

Величины (yi, xi) по закрытому каналу передаются доверенным участникам Di,

а величина y по открытому каналу передаётся центру C.

2.Каждый из участников Di проверяет “честность” участника A, а именно прове-

ряет истинность соотношения yi = gxi. После этого Di пересылает yi центру C.

	n
3. Центр C проверяет “честность” A, сравнивая величины y и	Q
	yi. Если проверка
	i=1

прошла успешно, то центр депонирует открытый ключ y участника A и записывает его в базу данных.

В результате выполнения этого протокола ни C, ни любые n − 1 (или менее) доверенных участников не могут вычислить секретный ключ участника A. Только все доверенные участники на основе своих частичных секретов могут определить ключ k.

Протоколы голосования

Требования к протоколам голосования

1.Голосование должно быть тайным для всех участников, кроме доверенного центра.

2.Должна обеспечиваться правильность подсчёта голосов, то есть каждый голосовавший может всегда убедиться в правильности подсчёта голосов.

Модель протокола с одним доверенным центром

Предварительные условия

Все вычисления проводятся в некоторой циклической группе G порядка n, g и h два различных образующих этой группы. Центр выбирает секретный параметр (ключ) x R Zn и вычисляет открытый ключ y = gx. Величины h, g, y публикуются.

Голосование и подсчёт голосов

Пусть A1, A2, . . . , AN участники голосования. Участник Ai выбирает секретный параметр αi R Zn, принимает решение "да"( bi = 1 ) или "нет"( bi = −1 ), вычисляет величины gαi и yαihbi и результат голосования заполненный бюллетень (gαi, yαihbi) посылает в центр по отрытому каналу связи.

Для каждого i = 1, N центр вычисляет дешифрующий множитель Ti = (gαi)−x и определяет элемент hbi = (yαihbi)Ti, тем самым определяя результат голосования

величины	N	N	N	N	n
					iP
участника Ai. Затем центр подсчитывает результат голосования z =					bi и вычисляет
	=1 gαi, W = i=1 yαihbi =		i=1 yαi!	i=1 hbi!.	=1
V =
Yi		Y	Y	Y

46

При правильном подсчёте голосов имеем

	N
N	Yi
hz = hPi=1 bi = H, W = U·H, U = yαi.
	=1

Величины H, U могут быть опубликованы или предоставлены по требованию участников голосования.

Проверка честности центра

Центр может заменить U на U0 и H на H0 так, что будет выполняться условие

W 0 = H0U0.

Каждый участник Ai знает только свой секретный параметр αi и поэтому не сможет вычислить U. Но из вышеизложенного следует, что V x = U. С другой стороны y = gx. Это означает, что

logV U = logg y.

(1)

Следовательно, для доказательства правильности подсчёта голосов, центр должен убедить каждого участника голосования в истинности равенства (1). Это можно сделать с помощью протокола Шаума-Педерсона.

Протокол Шаума-Педерсона

1. Центр вырабатывает секретный параметр k R Zn, вычисляет величины gk, V k

ипосылает их участнику Ai.

2.Ai вырабатывает параметр l R Zn и посылает его в центр.

3.Центр вычисляет величину s = k + lx и посылает её Ai.

4.Ai вычисляет величины a = gs, b = yl, c = vs, d = Ul и проверяет истинность

следующих соотношений:

a = gkb, c = V kd.

(2)

Если эти соотношения выполнены, то можно считать, что результаты голосования не подменены.

Проверим корректность вычислений в формулах ния y и s и соотношения U = V x имеем:

gkb = gkglx = gk+lx = gs

V kd = V kUl = V kV xl = V k+lx

(2). Действительно, из определе-

=a,

=V s = c.

Протокол проверки честности центра можно сделать неинтерактивным. Для этого можно использовать надёжную хэш-функцию h.

47

Неинтерактивный протокол Шаума-Педерсона

1. Центр вырабатывает k R Zn и последовательно вычисляет величины

gk, V k, l = h(gk, V k), s = k + lx

ипару (s, l) посылает Ai.

2.Ai последовательно вычисляет величины

a= gsy−l, b = V sU−l, c = h(a, b)

ипроверяет истинность соотношения l = c. Если оно выполняется, то результаты голосования подсчитаны верно.

Проверим корректность вычислений. В самом деле,

a = gk+lxg−xl = gk, b = V k+lxV −lx = V k, c = h(gk, V k).

Следовательно, c = l.

Протокол голосования с несколькими центрами

Пусть имеются m доверенных центров C1, C2, . . . , Cm, из которых более t являются “гарантированно честными”. Протокол голосования в этом случае можно организовать следующим образом.

1. Все вычисления, как и в предыдущем протоколе, проводятся в некоторой циклической группе G порядка n. Центры совместно вырабатывают случайным образом три образующих g, y, h группы G. При этом будем предполагать, что задача дискретного логарифмирования для любой пары выбранных элементов является вычислительно сложной, то есть вычислительно сложно решение следующих уравнений в группе G :

zx = u, z 6= u, z, u {g, y, h}.

(1)

Параметры g, h, y публикуются.

2. Процедура голосования проходит следующим образом.

Каждый участник голосования Ai вырабатывает секретный параметр αi R Zn и делает свой выбор bi {−1, 1}. Затем он вычисляет величины gαi, yαihbi и бюллетеньi = (gαi, yαihbi) посылает в центры Cj, j = 1, m. Каждый из центров на основе i

NN

вычисляет величины Q gαi и Q yαihbi. В отличие от предыдущего протокола ни один

i=1 i=1

из центров не сможет расшифровать бюллетени без знания αi.

3. Для того, чтобы центры смогли расшифровать бюллетени и произвести подсчёт голосов, осуществляется следующая процедура.

48

Каждый участник голосования Ai применяя (N, t) -схему разделения секрета “делит” свой секретный параметр на части αi1 , αi2 , . . . , αim и по закрытому каналу отправляет их центрам. Честные центры, объединив все частные секреты, полученные от всех участников голосования, вычисляют все секретные параметры αi, i = 1, N. Затем они

N

P

вычисляют величину δ = αi и смогут осуществить проверку правильности вычис-

i=1

лений, сравнив величины gδ и QNi=1 gαi. При успешной проверке центры публикуют число δ.

Покажем, что знание δ достаточно для определения результатов голосования каждым из участников голосования. Действительно, на основе бюллетеней i и δ каждый участник голосования может вычислить величины

!

N N

YY

A =	yαihbi y−δ и B = hbi = hz, где z результат голосования.
i=1	i=1

Из равенства A = hz каждый участник перебором ( N значительно меньше порядка группы G ) определит z.

Протоколы подбрасывания монеты по телефону

Постановка задачи

Два удалённых абонента A (подбрасывающший) и B (угадывающий) решают проблему жребия или совместной выработки случайного бита.

Требования к протоколу

(I)Вероятность изменения результата подбрасывания участником A, после того как B сообщил ему свою догадку, должна быть практически равна нулю.

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

(III)Вероятность выбора каждого бита равна 1/2.

Формальная модель протокола подбрасывания монеты

Участники протокола A и B выбирают однонаправленную функцию f: X → Y, X, Y N, удовлетворяющую условиям:

(1)если f(x1) = f(x2), то x1 ≡ x2 (mod 2);

(2)по известному y Y вычислительно сложно определить x, удовлетворяющий уравнению f(x) = y;

(3)X = X1 X2, |X1| = |X2|, X1 чётные, X2 нечётные.

49

Описание протокола

1. A вырабатывает x R X, вычисляет y = f(x) и y посылает B.

2.B выбирает σ R {0, 1} и σ посылает A. Тем самым он указывает предполагаемую чётность числа x.

3.A посылает x участнику B, B проверяет честность A.

Из (1)–(3) следует, что протокол удовлетворяет требованиям (I)–(III).

Экспоненциальный протокол совместной выработки случайного бита

Все вычисления проводятся в циклической группе G = hgi порядка n.

Описание протокола

1. A вырабатывает x R Z, вычисляет y = gx и y посылает B.

2. B выбирает β R {0, 1}, k R Zn, вычисляет r = yβgk и r посылает A.

3.A выбирает α R {0, 1} и посылает α участнику B.

4.B посылает A пару (β, k).

5.A вычисляет r0 = yβgk и сравнивает r и r0. Если r = r0, то γ = α β общий случайный бит A и B.

Обоснование корректности протокола

Участник A не сможет получить информацию о бите β из r, так как, во-первых, k выбрано случайно и, во-вторых, он не сможет определить k в предположении экспоненциальной сложности задачи дискретного логарифмирования в группе G.

Аналогично, при этом предположении участник B на шаге 4 не сможет заменить бит β на β. Действительно, для этого он должен найти такое k0 Zn, чтобы выпол-

нялось соотношение

r = yβgk = yβgk0 .

Отсюда, учитывая, что y = gx, получим:

gβx+k = gβx+k0

Следовательно, k0 = (β − β)x + k (mod n), β − β = ±1. Таким образом, для подбора k0 участник B должен уметь вычислять x, то есть решать задачу дискретного логарифмирования в группе G.

50