4.3.2. Схема Asokan - Slioup - Waidner

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

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

алгоритма генерации ключей: (pk,sk)<— genmc (і);

алгоритма зашифровки Е\ = E(pk,t,m)> где t - случайный двоичный вектор, m - открытый текст;

4. Криптографические протоколы а электрошюй коммерции и в документообороте 253

3) алгоритма расшифровки D\ т = D(sk,y/);

причем для любых t,m должно быть выполнено условие D(sk,E(pk,t,m)) = т/" Error".

Всем этим условиям удовлетворяют, например, известная схема открытого шифрования ОАЕР (Optimal Asymmetric Encryption Pad-ding) и схема Крамера - Шупа (Cramer - Shoup).

Тогда схема сервиса депонирования будет выглядеть так:

алгоритм генерации ключей сервисом Т: (pk, sk) <— genenc (/);

алгоритм зашифровки Е: у = где t - слу-чайный двоичный вектор, m - открытый текст; К - условие рас-шифровки (произвольная двоичная строка);

алгоритм расшифровки D: m - D{sk, (ty/, Н(к))).

Причем для любых t, m, к должно быть выполнено условие: D(sk, E(pkb t, т,к\к)=тГ Error".

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

Еще один необходимый элемент схемы честного обмена цифро-выми подписями - схема проверяемого депонирования.

Пусть d: G, —» G2 - сюръективное (т. е. Im# = G2) отображение гомоморфизма между двумя коммутативными группами, d Є G2 - общеизвестно, se й-1 (d) - сеіфетно. Мы хотим депонировать s при

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

вычисление se fT1 («і). Как и в обычной схеме, ке {ОД}* - условия

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

К схеме предъявляются следующие требования по безопасности.

Полнота. Если Р и V- честные, то для Vs,d,K:®(s) = d про-веряющий V принимает доказательство.

Корректность. Пусть противник взаимодействует с честным проверяющим V, имеет доступ к алгоритму расшифровки D и может выбирать d я к . Тогда вероятность того, что V примет доказательство и получит открытый текст а:ф(?>(ос,к)) Ф d , исчезающе мала.

Нулевое разглашение знания. В процессе выполнения доказа-тельства знания между Р и К нечестный участник не увеличит своего знания об s.

Рассмотрим способ реализации схемы проверяемого депонирования. Пусть имеется схема, реализующая обычный сервис депони-рования. Пусть, кроме того, есть хеш-функции //] и Нъ такие, что:

Ни re {0,1}' —> (г,/)є {0,1}* xGt, а Н2 сжимает длинные строки

произвольной длины в строки фиксированной длины.

Чтобы превратить описанную ранее схему сервиса депонирования в схему проверяемого депонирования, ее необходимо дополнить протоколом доказательства, показанным в табл. 4.2 (/V - параметр безопасности). Алгоритм расшифровки D необходимо модифицировать так, чтобы он по входным параметрам a,K,sk выдавал набор

?

величин {s-},l< і< N , а затем выполнял бы проверку: -б¦(s"-s/i)=d для всех 1 < і < N .

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

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

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

Таблица 4.2. Протокол доказательства для схемы проверяемого депонирования Доказывающий ( s Є б-1 (d) ~ секретная величина) Общедост. величины:

de G2,

к Є {ОД}*,

pk - откр. ключ центра доверия Проверяющий 1 For (1 V, к); h = Hi(h\,...,hN) 2 где s"= s' + s)

Окончание табл. 4.2

Доказывающий ( s Є О-1 (rf) - секретная величина) Общедост. величины:

deG2>

к Є {0,1}*,

pk - откр. ключ центра доверия Проверяющий 4 For (l) = #,(/;.), r; = v, If (bi= 1) then

, sf) = v;}, вычисляет h = H2 ), проверяет

h=h ив случае положительного результата принимает доказательство, затем вычисляет

lПусть Е - схема цифровой подписи.

Алгоритм редукции reduce принимает в качестве входных пара-метров: рк - открытый ключ схемы цифровой подписи X, т - подпи-сываемое сообщение, сг - подпись сообщения т на секретном ключе sk схемы цифровой подписи X. Результатами работы алгоритма являются: эффективно вычислимое преобразование 6: Gl —> G2 (включая описание групп Gb G2)> элемент dt G2, двоичная строка с є {0,1}*- дополнительная информация, используемая алгоритмами проверки и восстановления, и элемент

Алгоритм проверки verify берет в качестве входных параметров определенные выше величины pk, /и, 0, d, с и выдает решение о принятии как корректного либо отклонении как несовместного набора значений этих величин: {accept/ reject}.

Алгоритму восстановления recover передаются величины pk, т, в, с, s Є G,, по которым он выдает величину сг.

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

Начнем со схемы цифровой подписи Шнорра. Алгоритм редукции reduce для схемы Шнорра принимает в качестве входных пара-метров набор величин (p,q,g,h), т, (r,s) и выдает набор величин и = - gz, с, z = loggu. Последняя из них и является искомым прообразом. Алгоритм проверки verify берет в качестве входных параметров

і

(p,q,g,h), т, и, с, проверяет с~ н{иЬГс,т) и выдает решение {accept /reject}. Алгоритму восстановления recover передаются величины (P,q,g,h), т, с, z, по которым он выдает (с, z) = а .

Для схемы цифровой подписи DSS также выбираются два больших простых числа p,q, таких, что q\p-l, \q\ = 160 бит, g Є G(j ~ об-разующий элемент подгруппы Z* порядка q. Случайное число ХЄ Zq— секретный ключ схемы цифровой подписи, набор чисел (p,q,g,h), где h = gx - открытый ключ схемы. М - подписываемое со-общение. Подписывающий выбирает к є R Z*, вычисляет

r = (?*)modg и s = k~x(H(m) + xr),s ФО (здесь Н(т)є Zq), и по-сылает [m,r,s\ проверяющему. Проверяющий должен предварительно вычислить ul=H(m)s~l и u2 = rs~\ а затем сравнить:

?

r=g"lh"2 mod q.

Тогда алгоритм редукции reduce для схемы DSS принимает в качестве входных параметров набор величин (p,q,g,h), т, (r,s) и вы- дает набор величин а = g"'lh- є Z*, р = gH{in)hr є Z*pS s = loga (3. Алгоритм проверки verify берет в качестве входных параметров (p,q,g,h),

т, а, вычисляет г = a mod q , $ = gH{m)l% , затем проверяет aq =1,

(.УФІ (т. е. а = gk для &Є Z*), (3^1 (т. е. s Ф 0) и выдает решение

{accept/reject}. Алгоритму восстановления recover передаются ве-личины (p,q,g,h), т, ос, s, по которым он выдает (r,j), где. г = a mod q.

Наконец, для схемы цифровой подписи RSA прообраз совпадает

с самой подписью: s = фЦт) • (modп).

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

Пусть применяются схема цифровой подписи DSS и схема от-крытого шифрования ОАЕР. Тогда G{ - аддитивная группа ZfJ, G2 -

подгруппа порядка q в Z*, g Є G2 - образующий элемент, 0: а є Zq —> ga. Если положить = 1024 бита, \q\ = 160 бит, |Я2(х)| =

= 160 бит, |/| = 160 бит, Л^ = 40, количество передаваемых данных будет составлять 3...4 Кбайт, доказывающий и проверяющий выпол-няют сорок 160-битовых экспоненцирований в Z* по основанию g,

что эквивалентно приблизительно 2 000 модульных умножений.

Пусть используется схема цифровой подписи RSA и схема от-крытого шифрования RSA. Тогда Gl-G2=Z*n, 6(я) = ас. Если е =

= 3 или е = 21б+1, то количество передаваемых данных составляет 6...7 Кбайт, доказывающий и проверяющий выполняют не более 160 модульных умножений для е = 3 и не более 800 модульных ум-ножений для е = 216+1.

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

А направляет В свою депонированную подпись (обычный сервис депонирования). Условие, которое А прикрепляет к нему, описывает подпись, которую В предположительно должен дать А.

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

А получает и проверяет проверяемо-депонированную подпись от В. Если эта проверка успешна, А посылает В свою подпись. В противном случае А связывается с Тя выполняет протокол преры-вания транзакции (abort(A7)), после чего завершает протокол.

В получает и проверяет подпись от А. Если эта проверка успешна, В посылает А свою подпись, выдает подпись А и завершает протокол. В противном случае В связывается с Т и требует разреше-ния этой транзакции (протокол B-resolve(5,7)), после чего завершает протокол.

А получает и проверяет подпись от В. Если эта проверка успешна, А выдает подпись В и завершает протокол. В противном случае А связывается с Г и требует разрешения этой транзакции (протокол A-resolve(A,7)), после чего завершает протокол.

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

Протокол abort(/4,7). А требует, чтобы Г блокировал любые тре-бования от В разрешить транзакцию, которые могут поступить от него в будущем. Но если В уже разрешил транзакцию, А получит подпись, которую он желает, так как она депонирована у Г во время выполнения протокола B-resolve(5,7). Чтобы гарантировать чест-ность, протокол abort(А, 7) блокирует любые попытки разрешить протокол со стороны А и наоборот. Однако реализация должна га-рантировать, что только А может запрашивать выполнение этого протокола (для этого Т поддерживает множество записей S формы (no-abort, v) или (abort, v), соответственно разрешающих либо за-прещающих транзакцию).

Протокол В-resolve^, 7). В требует, чтобы Т расшифровал де-понированную подпись, которую В получил на шаге 2. При выпол-нении этого протокола В должен депонировать подпись, описанную

в условии этого депонента. Так как это обычная, а не проверяемо- депонированная подпись, то нет гарантий, что содержание депонента корректно. В этом случае попытка разрешения протокола со сто-роны В окончится неудачей, но и любая попытка А разрешить про-токол также будет неудачна. Если А выполнил протокол abort(A, Т) раньше того, как В попытался разрешить транзакцию, то попытка В также окончится неудачей.

Протокол A-resolve(A,7). А требует, чтобы Г расшифровал про-веряемо-депонированную подпись, которую А получил на шаге 3. До того, как это сделать, Т проверяет, что депонированная подпись, которую А послал В на шаге 1, была корректна. Он делает это, ис-пользуя условие, присоединенное к проверяемо-депонированной подписи. Также реализация схемы честного обмена должна гаранти-ровать, что только А может выполнять этот протокол с Т.

На рис. 4.15 показано, как из описанных выше элементарных крип-тографических конструкций «собирается» схема честного обмена. Схема честного обмена (fair exchange) Алгоритм генерации ключей Протокол честного обмена Е Протокол прерывания честного обмена abort Протокол разрешения для

участника В B-resolve Протокол разрешения

для

¦ участника^ A-resolve

Схема

Алгоритм генерации ключей Б Протокол док-ва D у «ч

Схема «cqjBiica депонирования» Алгоритм генерации ключей Е D

Схема редукции Алгоритм редукции reduce Алгоритм проверки verify Алгоритм восст-ния recover

Схема открытого шифрования Алгоритм генерации ключей Е D

Схема цифровой подписи Алгоритм генерации ключей S V

Рис. 4.15. Использование криптографических конструкций в схеме честного обмена цифровыми подписями

4. Криптографические протоколы в олектротюй коммерции и в документообороте 261

В табл. 4.3.^4.6 приводятся спецификации основного и вспомо-гательных протоколов схемы честного обмена цифровыми подпися-ми Asokan - Shoup - Waidner.

Таблица 4.3. Протокол Е(А,В) А

тЛ,аЛ- откр. величины, skA - секретный ключ f— однонаправл. функция, pkA, pka

pk-Г, ркГ В

mD,oB - откр. величины, skji - секр. ключ 1 <-[QB,dll,cB] reduce(pkB,mB, аИ) = = (9Д 4B,CB,SB) 2 ver\ty(pkB, тв, SB,dB,cB) = = {accept/reject} [f (accept)

then { reK Domain(f), v =/(U

a = E(pkA,t,(oA,K)),

где К = (v,pkA,mA,QB,dB)} else {quit} 3 Выполняют протокол проверяемого депонирования: А в роли доказы-вающего Р, В в роли проверяющего V. В результате А получает проверяемо депонированную величину: d = Р, sB = В-' [d^,

К = (v, a, pkA, тА, 0fl, dB ) . В случае неудачи В подает команду (quit) 4 If {(accept) док-во шага 3 и получает величину (3 }

then отправляет (5Л else {abort(A,T), quit} Юл]"» 5 VERIFYPkB (Тл^Л) = {accept/reject} If (accept)

then {отправляет sB,

выдает Oa , quit }

else { B-resolve(5,7>, quit}

262 Запечников С. В. Криптографические протоколы и их применение

Окончание табл. 4.3

А

тЛ,аЛ - откр. величины, skA - секретный ключ /- однонанравл. функция, pkM pk&

PKc > р/с'Г в

mH, Gn - откр. вели- чиныу skB - секр„ ключ 6 Venfy^bB{sa)=dB J =

= {accept/reject}, If (accept) then {recover (pkB,mB, Qd,CB,SB), quit } else { A-resolvefA Д quit }

Таблица 4.4. Протокол abort(A,T)

А Т МвЛ] V =f(r), If (deposit, v, 0Д ,dB,sB)e S (для некоторого sB) then [ід] else If (no-abort, v)e S then [««error»] else {add(abort,v)->S, [«exchange aborted»]} Таблица 4.5. Протокол B-resolve(B,T) в T [v,a,pkA>mA,BB,sB] dB 4- If (abort, v) €E S then V. [««exchange aborted»] else{ \|/ = D (a, skr, к = (v, pkA, mA ,QB,dB)) Verifyркл = ? If not then [«error»] else { add (deposit^, 8B ,dB,sB)->S, tV"3 }}

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