<< Предыдущая

стр. 42
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Для проверки подписи (Д, S) на сообщении М, осуществляют
следующую процедуру:
10,4- Алгоритмы цифровой подписи

- Вычисляют хэш-значение Н — h{M).
- Определяют А = ^ (mod Q)
- иВ = § (modQ).
- Находят У = F(G^y^), где Y — открытый ключ подписавшего
сообщение.
- Подпись считается корректной, если V = R.
Стоит сравнить эти процедуры генерирования и проверки под­
писи с теми, что осуш;ествляются в алгоритме DSA^ и найти, в чем
они отличаются. Заметим, что обычно все операции в алгоритмах
EC-DSA записываются аддитивно, т.е. через знак «+», а мы оста­
вили мультипликативную запись, чтобы удобнее было сравнивать
две версии схемы.
Разберем «игрушечный» пример работы алгоритма EC-DSA^ взяв
за основу эллиптическую кривую над полем F199 вида
Е: Г^ = Х^ + X + 3.
Число ее элементов равно Q = 197, т. е. является простым. Поэтому
соответствующая группа — циклическая, а координаты ее образу­
ющей Р — (1,76). Выберем ж = 29 в качестве секретного ключа.
Тогда соответствующий открытый ключ будет равен
Y = [х]Р = [29](1,76) - (113,191).
Предположим, что владелец секретного ключа намерен подписать
сообщение с хэш-значением Н{М) = 68. Тогда ему нужно произ­
вести эфемерный ключ, который мы выберем равным А = 153, и
;
вычислить
R = x-KOopfl,.{[k]P) = ж-коорд.([153](1,76)) =
-а;-коорд.((185,35)) = 185.
Далее он находит
S = ЩМ) + X . R)/k (mod Q) =
= (68 + 29 .185)/153 (mod 197) = 78.
Подпись, которую он посылает вместе с сообщением, — это пара
(Д,5) = (185,78).
Чтобы проверить подпись, мы вычисляем
А = h{M)/S (modg) = 68/78 (mod 197) = 112,
В = R/S (modQ) = 185/78 (mod 197) = 15.
276 Глава 10. Распределение ключей, схемы подписей и хэш-функции

После этого определяем
Z = [А]Р + B[Y] = [112](1,76) + [15](113,191) =
= (111,60) + (122,140) = (185,35).
Подпись оказалась верной, поскольку
R = 185 = д:-коорд.(^).

10.5. Подпись Шнорра
Множество вариантов схем подписей основывается на дискретных
логарифмах. С практической точки зрения интересен алгоритм, но­
сящий название подписи Шнорра. Расскажем об этом алгоритме в
его оригинальном виде, оставив читателю разбираться самостоя­
тельно с его обобщением на эллиптические кривые.
Пусть А — открытая конечная абелева группа, порожденная эле­
ментом G простого порядка Q. Ключевая пара в алгоритме подписи
Шнорра совпадает с такой же парой в DSA^ а именно, секретным
ключом служит целое число х из интервала (О, Q), а открытый ключ
определяется формулой Y = G^. Чтобы подписать сообщение, в ал­
горитме Шнорра поступают следующим образом:
- Выбирают эфемерный ключ к из промежутка (0,(5).
- Вычисляют соответствующий открытый ключ R — G^.
- Находят Е — /г(М||Л). Обратите внимание на то, что значение
хэш-функции зависит как от сообщения, так и от эфемерного
открытого ключа.
- Вычисляют S = к -h X • Е (mod Q).
Полученная таким образом пара (??, S) является искомой подписью.
Проверка подписи довольно проста: вычисляют R = G^Y˜^ и
h{M\\R), Подпись корректна, если верно равенство Е — h{M\\R).
Для примера выберем следующие параметры домена:
Q = 101, Р = 607 и G = 601.
Чтобы зафиксировать ключевую пару, положим х = 3 и
У = G'' (modP) - 3 9 1 .
Затем генерируем эфемерный ключ /с — 65 и вычисляем
R = G^ (modp) = 223.
Теперь находим хэш-значение Е = h{M\\R) (modQ). Допустим, что
при этом получилось Е = 93, Тогда вторая компонента подписи
10.5, Подпись Шнорра

выглядит как
S = k-\-x-E (modQ) = 6 5 + 3-93 (mod 101) - 4 1 .
В следующих главах мы увидим, что можно доказать криптостой-
кость алгоритма подписи Шнорра в предположении о труднораз-
решимости задачи дискретного логарифмирования, в то время как
никакого доказательства криптостойкости DSA пока не найдено.
Алгоритм подписи Шнорра был предложен к эксплуатации в
процедурах запрос-ответ идентификации кредитных карточек, по­
скольку «отвечающая» часть подписи (значение S) легко проверя­
ется, так как д,ля этого нужно всего лишь одно умножение и одно
сложение в конечном поле. Независимо от того, в какой группе мы
работаем, эта заключительная стадия требует только арифметики
по модулю относительно небольшого простого числа.
Чтобы увидеть, как работает алгоритм подписи при процедуре
аутентификации, приведем следующий сценарий. Допустим, Вы хо­
тите с помощью смарт-карты^ подтвердить свою подлинность при
проходе в какое-то закрытое помещение или при обращении к тор­
говому автомату. Считыватель карты обладает копией Вашего от­
крытого ключа У, в то время как в карточке записан Ваш секрет­
ный ключ гг. Пока Вы носите карточку в кармане, она генериру­
ет некие обращения, которые фактически являются эфемерным от­
крытым ключом вида R = G^. Когда Вы помещаете смарт-карту
в считывающее устройство, она передает тому одно из этих зара­
нее вычисленных обращений. Считыватель выдает запрашивающее
сообщение Е. После чего Вашей карточке остается лишь найти
S = к-\-хЕ (modQ)
и передать результат считывателю, который проверит «подпись»
вычислением G^ — RY^. Обратите внимание, что все требуемые
вычисления при этом крайне просты для реализации.
Более подробно, если обозначить через К смарт-карту, а через
А — читающий ее автомат, то
К Л : Л = G^,
А К : Е,
К ^ А: S^k + xE (modQ).
Таким образом, этот протокол состоит из трех фаз
обращение • запрос
^Кредитная карточка с микропроцессором. — Прим. перев.
278 Глава 10. Распределение ключей, схемы подписей и хэш-функции

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


10.6. Подпись Ниберга-Руппеля
Может оказаться, что подпись на коротком сообщении будет более
длинной, чем его основное содержание. Напомним, что RSA мож­
но использовать и как схему подписи с приложением, и как схему
подписи с восстановлением сообщения. Пока ни один из описанных
нами алгоритмов подписи, основанный на дискретном логарифми­
ровании, нельзя использовать в виде схемы с восстановлением сооб­
щения. Сейчас мы приведем пример схемы подписи с восстановлени­
ем сообщения, называемый алгоритмом подписи Ниберга-Руппеля,
основанный на вычислении логарифмов в открытой конечной абе-
левой группе А.
Все схемы подписи с восстановлением сообщения используют от­
крытую функцию избыточности / . Функция / преобразует фак­
тическое сообщение в данные, которые затем подписываются. Это
действие напоминает то, что делает хэш-функция в схемах подписи
с приложением. Однако в отличие от хэш-функции функция избы­
точности должна быть легко обратимой. В качестве простого при­
мера можно взять

—• {одг,
|-> т\\т.
Мы предполагаем, что множество значений функции / может быть
вложено в группу А. В нашем описании мы будем использовать це­
лые числа по модулю Р , т.е. А — Fp и, как обычно, будем считать,
что большое простое число Q делит Р — 1, а G — образующая под­
группы в А порядка Q. Ключевая пара выбирается стандартным
способом ^\ля систем, основанных на дискретном логарифмировании:
{Y = G\x).
Алгоритм подписи Ниберга-Руппеля состоит в следующем:
1. Берут случайное число к G Ъ/Q'L и вычисляют R = G^ (mod Р).
2. Находят Е =- f{M) • R (modP).
3. Определяют S = х • Е -\- к (mod Q).
Подпись представляет собой пару (E^S). Исходя из этой пары и
целого числа по модулю Q, нам нужно
10.6. Подпись Ниберга-Руппеля

- убедиться в том, что подпись принадлежит пользователю с
открытым ключом Y;
- восстановить сообщение М.
В процедуре проверки подписи Ниберга-Руппеля по паре (J5, S) и
открытому ключу отправителя Y — G^ вычисляют
Ui - G^Y-^ = G^-^^ = G^ (modP),

C/2-^(modP).

После этого убеждаются, что С/2 является значением функции избы­
точности, т.е. в справедливости равенства С/2 — f{M) = М\\М. Ес­
ли это равенство ложно, то подпись отклоняют. В противном случае
восстанавливают сообщение по правилу М = /˜^(С/2) и принимают
подпись.
Пример. Выберем параметры домена:
Q = 101, Р = 607, и G = 601.
Пусть ключевая пара имеет вид: ж = 3, У = G^ (modP) = 391.
Чтобы подписать сообщение М = 12 (в нашем маленьком при­
мере М должно лежать на отрезке [0,15]), вычисляем эфемерный
ключ к = 45 и
R = G^ (modP) = 143.
Допустим, / ( М ) = М Н- 2^ • М. Тогда / ( М ) = 204 и
Е=^ f{M)'R (modP) = 3 6 ,
S = X'E-hk (modQ) = 52.
Итак, наша подпись — это пара {E^S) = (36,52). Покажем теперь,
как проверяется подпись и восстанавливается сообщение. Все начи­
нается с вычисления
C/i = G^Y-^ = 143.
Обратите внимание на то, что полученное проверяющим значение
C/i, совпадает со значением Я, найденным лицом, подписывающим
сообщение. Далее проверяющий находит
U2 = E/Ui (modP) = 204.
Теперь необходимо убедиться в том, что найденное число С/2 пред-
ставимо в виде М + 2^М для некоторого целого числа М G [0,15].
Мы видим, что С/2 действительно так представляется, поэтому под­
пись корректна. Сообщение М = 12 восстанавливается как решение
уравнения
М + 2^М = 204.
Глава 10. Распределение ключей, схемы подписей и хэш-функции

10.7. Соглашение об аутентифицированном ключе
Теперь мы знаем, как реализовать цифровые подписи, с помощью
которых можно решить проблему, возникавшую в протоколе Диф-
фи-Хеллмана распределения ключей. Напомним, что атака «чело­
век посередине» достигала успеха потому, что каждая из сторон не
знала, кто с ней обменивался сообш;ениями. Теперь мы в состоянии
идентифицировать любую из сторон, обязав их подписывать свои
послания.
Мы получим прогрессивную секретность, поскольку долговре­
менный ключ для подписи используется лишь для установления под­
линности сообп];ений и никак не задействован в передаче ключей.
Кроме того, мы можем выбрать одну из версий протокола Диф-
фи-Хеллмана. Первая из них основывается на дискретном лога­
рифмировании в конечных полях {DH)^ а другая берет за основу
эллиптическую кривую (EC-DH). Существует по крайней мере три
возможных варианта алгоритма подписания документов: RSA^ DSA
и EC-DSA. Считая, что р,ля обеспечения криптостойкости необхо­
димо выбирать в RSA модуль шифрования порядка 1024 битов, про­
стое число в DSA около 2^^^^, а порядок группы как в DSE^ так и в
EC-DSA приблизительно равен 2^^^, мы получим следующий размер
подписанных сообщений в протоколе Диффи - Хеллмана:

Таблица 10.2. Размер сообщений в протоколе Диффи - Хеллмана
Алгоритм Размер подписи
Размер сообщения Общий размер
DH4-DSA 1024 1344
320
1024
DH-hRSA 1024 2048
EC-DH+RSA 1024 1184
160
EC-DH4-EC-DSA 160 320 480


Видно, что при этом получаются слишком большие накладные
расходы, а нам нужно всего лишь договориться об использовании
сеансового ключа, размер которого может быть всего 128 битов.
Для уменьшения объема сообш;ения Менезис, Кью и Ванстоун
разработали протокол, названный протоколом MQV. Он основы­
вается на задаче дискретного логарифмирования в группе А, по­
рожденной элементом G. Его можно использовать как в конечном
поле, так и на эллиптических кривых для обмена аутентифициро-
ванным ключом, причем размер сообш;ений дается таблицей 10.3.
Таким образом, MQV-протокол дает нам значительную эконо­
мию в размере передаваемых данных. Протокол работает в предпо-
10.7. Соглашение об аутентифицир о ванном ключе

ложении, что Алиса и Боб имеют долговременную ключевую пару,
состоящую из открытого и секретного ключей, которые мы обозначим


Будем предполагать следующее: Боб знает, что А — аутентифика-
ционный открытый ключ Алисы, а Алиса уверена, что В — ключ
с теми же свойствами, принадлежащий Бобу. Установление подлин­
ности открытых ключей может быть обеспечено применением неко­
торой формы сертификатов открытых ключей, о которых пойдет
речь в следующих главах.

Таблица 10.3. Размер сообщений в протоколе MQV
Протокол Размер сообщения
DL-MQV 1024
EC-MQV 160

Предположим, что Боб с Алисой намерены достигнуть соглаше­
ния о секретном сеансовом ключе. При этом они генерируют уни­
кальные случайные вставки, обеспечивающие стойкость протокола
и означающие, что ни одна из договаривающихся сторон не обя­
зана доверять другой в выборе сеансового ключа. Алиса с Бобом
производят свою эфемерную ключевую пару
C={G\j) и (D = G',6)
И обмениваются информацией
Алиса • Боб: G'^,

<< Предыдущая

стр. 42
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>