3.5.3. СЭП Брандса
В СЭП Брандса используется следующее свойство схемы аутен-тификации Шнорра: если доказывающий Р может успешно пройти аутентификацию с вероятностью, существенно отличающейся от нуля, тогда он должен знать величину л;.
Для схемы цифровой подписи Шнорра выбираются два больших простых числа p,q, таких, что q\p~\., g є Gn - образующий элемент
подгруппы Z* порядка q. Случайное число хе Zq - секретный
ключ схемы цифровой подписи. Открытый ключ схемы - набор чи-сел (p,q,g,h), где h = gx\ т - подписываемое сообщение. Подписывающий выбирает и>ЄЛ Zq, вычисляет с = Н (т,а)е Zq, г = w+cx и посылает [т,с,г] проверяющему. Последний должен сравнить:
7
gr =ahc mod р. В случае положительного результата он принимает подпись, в противном случае - отвергает.
Таблица 3.1. Схема цифровой подписи Шнорра Предварительный этап Р Центр доверия V h = gx mod p p,q - простые числа, q\p-l, geZp:g"^l(modp) P, Q, R, h Генерация подписи Р V 1 weKZQ,a = gw 2 т - подписываемое сообщение, с = hash(m,a) 3 Г = VV+CJC [>П, С, Г ]-> Проверка подписи 4 gr -ahc mod p
На основе схемы цифровой подписи Шнорра легко строится ин терактивная схема цифровой подписи Шаума - Педерсена с сокры тием подписанного сообщения (табл.
3.2).Таблица 3.2. Схема цифровой подписи Шаума - Педерсена с сокрытием подписанного сообщения
Предварительный этап
P Центр доверия V
XEK {I,...,?}, h = gxmodp p,q- простые числа, q\p~l, geZp:g"^l(modp)
P, Q, g, h
Генерация подписи
Р V
0. Сокрытие подписи т, z- тх [m,z]-»
1. Выбор случай-ного варианта а = я", Ь = mw
2. Запрос На шаге (1) выбирается величина w, которая носит название слу-чайного варианта величины х. Так как здесь есть дополнительная открытая величина z-> основанная на х, есть и такая же величина b, основанная на w. Шаг (2) представляет собою обычный случайный запрос проверяющего подписывающему. На шаге (3) проверка ответа выполняется по основанию g и по основанию т в отдельности. Эта схема является примером интерактивных схем цифровой подписи, в которых подписание текста происходит при участии (бу-дущего) проверяющего, в то время как традиционная схема предпо-лагает совершенно независимую генерацию и проверку подписей. Схема затемненной подписи Шаума - Педерсена (табл. 3.3) строится на базе предыдущей. Для этого добавляем в нее шаги, где проверяющий (получатель) трансформирует подпись. Таблица 3.3. Схема затемненной подписи Шаума - Педерсена
Предварительный этап
Р Центр доверия V
хєк {X—>п [ m, z]-> s,ttu>veK Zq,s± 0; ' SI. ' s 1 1 m=mg ; z = zh
I. Выбор случайного варианта а = gw,b~ mw [а,ЬП a' = a"gv \ b' = blua'u (mj
Предварительный этап
Генерация подписи
Р V
2.Запрос <г[с) с - hash (in, za,b'),
3. r = ur + V
В этой схеме сообщение т будет соответствовать «белой» форме монеты, изображенной на рис. 3.3-3.6, а т - «штрихованной» ее форме. Затемненной подписью является набор величин G = (z,a,b,c,r), пересылаемых от подписывающего к проверяющему; обычной подписью (подписью со снятым затемнением) - набор величин су' = (z\a',b',c,r). Особенность, которая делает только «штрихованную» монету пригодной для оплаты, заключается в том, что только в этой форме имеет место равенство c=hash(m, / / > Л. z,a,b). Величины (s,t,u,v) называются затемняющими факторами. Для СЭП Брандса мы всегда будем полагать t = 0, но в общем случае в схеме Шаума - Педерсена возможно t ф 0. Продемонстрируем корректность этой схемы цифровой подписи, а именно покажем, что результат о' - корректная подпись Шаума - Педерсена для т алгоритмически точно такая же, как и в предыдущей схеме подписи. Очевидно, что по конструкции схемы выполняется равенство с = hash(m ,z ,а',Ь'). Мы должны проверить, что g/=a'-hr и (in У -b'-(z')c. Это можно сделать, просто под-ставляя уравнения одно в другое. Но идея подписи станет еще по-нятнее, если мы покажем, что все величины в левой части уравнений имеют ту же структуру, что и справа. В самом деле, z' = zs -ЇЇ =mxs ¦ gxt = (in*gl = (m)x - точно так и должно быть. Далее: а = gwu+v. Здесь wm+v играет ту же роль для а , 206 Запечников С. В. Криптографические протоколы и их применение что и w для а, и мы обозначим ее w = wu + v. Далее покажем, что Ъ' = (тУ: = (myu+v ={m')v\ Наконец, / = иг + v = u(w + сх)+v = (wu + v) + исх = w + с'х , что тоже соответствует исходной схеме Шаума - Педерсена. Следо-вательно, мы можем быть уверены, что в силу хсорректности обычной схемы подписи Шаума - Педерсена данная цифровая подпись тоже удовлетворит проверочным уравнениям. Более того, можно доказать, что каждому сообщению с действи-тельной подписью (т',о ) может с равной вероятностью соответствовать любая из пар (ш, о) , которые могут получаться в протоколе затемненной подписи, что демонстрирует наличие у схемы свойства затемнения подписи. Эти пары связаны между собой четверкой за-темняющих факторов (s,t,u,v\ причем для каждой пары ((/я'.ст'^т.а)) существует точно q четверок затемняющих факторов, преобразующих (ш,а) в (т',а').