ВУЗ:
Составители:
Рубрика:
115
АЛГОРИТМ ПРОВЕРКИ ПОДПИСИ К СООБЩЕНИЮ М
По полученным данным
M, r, S и имеющемуся у получате-
ля открытому ключу отправителя
y
A
вычисляются величины
)(mod pa
M
и ).(mod pry
S
r
A
⋅ В случае выполнения равенства
)(mod)(mod prypa
S
r
A
M
⋅=
считается, что подпись верная.
Поясним работу алгоритмов. Рассмотрим проверяемое ра-
венство )(mod)(mod prypa
S
r
A
M
⋅= или сравнение
),(mod prya
S
r
A
M
⋅≡ решением которого и является числа r и s.
После подстановки
y
A
и r оно примет вид
).(mod paaa
SKrX
M
AA
⋅≡
⋅
Учитывая свойства сравнений (теорема Эйлера - Ферма),
последнее эквивалентно сравнение по модулю
(Р – 1) вида:
).1(mod
−
+
≡
pSKrXM
AA
Именно из этого сравнения подписывающий пользователь
вычисляет величину
).1(mod][
1
−⋅−=
−
pKrXMS
AA
Особенностью алгоритмов цифровой подписи является на-
личие у подписывающего абонента секретного ключа
),(
AA
xK .
При этом, в случае проверки, он предъявляет контролеру не сам
секретный элемент, а некоторые значение функции, вычисляе-
мое с помощью секретного ключа по случайному запросу кон-
тролера, доказывая тем самым, что он обладает секретом, путем
его косвенной демонстрации, путем вычислений. Именно отсю-
да появилось название «доказательство при нулевом знании»,
которое
получил протокол общения абонентов, когда абонент
доказывает, что он обладает секретом, не раскрывая самого сек-
рета. Алгоритмы «доказательства при нулевом знании» не явля-
ются собственно криптографическими, т.к. они служат для пере-
дачи сообщений типа « я знаю эту информацию». Однако, такие
алгоритмы совместно с алгоритмами цифровой подписи, шиф-
рования с открытым
ключом и открытого распределения ключей
позволяют организовывать более совершенные протоколы взаи-
116
модействия пользователей криптографической сети, которые
реализуют одновременно и подтверждение подлинности доку-
ментов и доказательство при нулевом знании.
Общая идея алгоритмов доказательства при нулевом зна-
нии состоит в том, что он может вычислять некоторую функ-
цию, зависящую от секретного
ключа и от аргументов, задавае-
мых проверяющим. Проверяющий, даже зная эти аргументы, не
может по данному ему значению функции восстановить секрет-
ный ключ. При этом функция должна быть такой, чтобы прове-
ряющий мог удостовериться в правильности ее вычисления, на-
пример, эта функция может представлять собой цифровую под-
пись выбранных им аргументов
.
Рассмотрим алгоритм доказательства при нулевом знании,
в основе которого лежит описанный ранее алгоритм
RSA:
1. Доказывающий
А и контролер В, оба знают идентифика-
тор
I и открытый ключ n, e, но А, кроме того, знает еще секрет-
ное число )(mod nIS
d
= , сформированное по секретному ключу
d. Сначала А генерирует случайное число Х и вычисляет
)(mod nXy
e
= . Затем он отсылает I,y к B.
2. После этого
В генерирует и передает А случайное число
V.
3. Затем
А вычисляет и передает В число
).(mod nyxW
v
⋅=
4. Контролер В проверяет принадлежность идентификатора
I к А путем проверки тождества
).(mod nyIW
ve
=
