Пароли
СЕКРЕТHЫЙ пароль - число x из Z*(p).
ОТКРЫТЫЙ пароль (y) вычисляем в два шага.
Сначала находим z=v0x (mod 2p), z принадлежит группе Z*(2p).
Hаконец вычисляем сам открытый пароль y = wz (mod 2p+1), y принадлежит группе Z*(2p+1).
Теорема. При любом выборе секретного пароля (x) открытый пароль (y) будет являться образующей мультипликативной группы Z*(2p+1). Другими словами, сравнение ya = b (mod 2p+1) разрешимо относительно a при любом b.
Доказательство. Число w^z будет образующей группы Z*(2p+1) iff числа z и 2p взаимно просты. Hо z = v0x (mod 2p), где v0 - образующая группы Z*(2p).
Электронная подпись
Пусть s - число (информация), к которому надо найти электронную подпись, s принадлежит группе Z(2p). Для этого выбираем случайное число r из группы Z*(2p), изоморфной Z*(p), и в качестве подписи выдаем пару чисел (a,b), где
a = a(r,s) = z-1*r*s = v0(-x)*r*s (mod 2p);
b = b(r,s) = wr (mod 2p+1).
Так как
Z*(2p) = Z*(p)+Z*(2) = Z*(p) = Z(p-1),
то
1/z = z-1 = v0-x = v0(p-1-x).
Таким образом, для составления подписи требуется знать секретный пароль (x), точнее говоря z=v0x.
Для проверки подлинности подписи можно воспользоваться равенством
ya = bs (mod 2p+1).
В самом деле,
ya = (wz)^(z-1*r*s) = w^(z*z-1*r*s) = wrs = (wr)^s = bs (mod 2p+1)
Следовательно, для проверки подлинности подписи достаточно знать только открытый пароль (y).
При вычислении подписи число s(файл) находится с помощью однонаправленной хэш-функции (аналог MD4, но другое).
Итак:
Обозначения.
p, 2p+1 - простые числа,
v, w - образующие групп Z*(p) и Z*(2p+1) соответсвенно,
v0 = p + (p+1)v - образующая Z*(2p),
x - секретный пароль, число из Z(p-1),
z - промежуточное выражение из Z(2p),
y - открытий пароль, число из Z*(2p+1),
s - информационное число,
r - случайное число из Z(2p),
(a,b) - электронная подпись,
a из Z(2p),
b из Z*(2p+1),
(c,d) - зашифрованное сообщение,
c из Z*(2p+1),
d из Z*(2p+1),
e - промежуточное выражение из Z*(2p+1).
Hахождение открытого ключа по секретному. x =>y
v0 = p + (p+1)*v (mod 2p)
z = v0x (mod 2p)
y = wz (mod 2p+1)
Электронная подпись x, s, r =>a, b (r - случайное)
v0 = p + (p+1)*v (mod 2p)
a = v0(p-1-x)*r*s (mod 2p)
b = ws (mod 2p+1)
Проверка подписи y, s, a, b =>y/n
ya == bs (mod 2p+1)
Шифрование y, s, r =>c, d
e = yr (mod 2p+1)
c = wr (mod 2p+1)
d = s*e (mod 2p+1)
Расшифровка x, c, d =>s
v0 = p + (p+1)*v (mod 2p)
z = v0x (mod 2p)
1/e = c2p-z (mod 2p+1)
s = d/e (mod 2p+1)
8 8 8
| |
*
Обратная связь