Составители:
Для начала генерируется число n как произведение двух больших
чисел. Затем выбирается K различных чисел V
1
, V
2
…, V
K
, где
каждое V
i
является квадратичным вычетом по модулю n, для того,
чтобы сгенерировать открытый и секретный ключи. V выбирают
таким, что сравнение
x
2
≡ V
i
mod n
имеет решение и существует V
i
-1
mod n. Открытым ключом
является полученная строка V
1
, V
2
, …,V
K
.
После этого вычисляют наименьшие значения S такие, что
S
i
= sqrt (V
i
-1
) mod n.
Строка S
1
, S
2
,…,S
K
является секретным ключом.
Далее приступают к выполнению протокола идентификации:
1. Пользователь А выбирает случайное число r, r < n, вычисляет
x = r
2
mod n
и посылает х пользователю В.
2. Пользователь В отправляет пользователю А случайную
двоичную строку из K бит: b
1
, b
2
,…,b
K
.
3. Пользователь А вычисляет
y = r ⋅ (S
1
b
1
⋅ S
2
b
2
⋅…⋅ S
k
b
K
) mod n.
Перемножаются только те значения S
i
, для которых b
i
= 1, если
b
i
= 0, то сомножитель S
i
не входит в произведение. Вычисленное
значение y отправляется пользователю В.
4. Пользователь В проверяет, что
x = y
2
⋅
(V
1
b
1
⋅
V
2
b
2
⋅
…
⋅
V
K
b
K
) mod n.
Пользователь В перемножает только те значения V
i
, для которых
b
i
= 1. Оба пользователя повторяют этот протокол t раз, пока В не
убедится, что А знает S
1
, S
2
, …, S
K
. Вероятность того, что
пользователь А может обмануть В, равна (1/2)
K
t
.
Рекомендуется в
качестве контрольного значения брать вероятность обмана
пользователя В равной (1/2)
20
при K = 5 и t = 4.
83
Страницы
- « первая
- ‹ предыдущая
- …
- 79
- 80
- 81
- 82
- 83
- …
- следующая ›
- последняя »
