Проверка подписи

Подписывание

Случайное число, уникальное для каждой подписи.

Открытый ключ отправителя

Закрытый ключ отправителя

Общие компоненты группы пользователей

Алгоритм цифровой подписи

DSS основан на трудности вычисления дискретных логарифмов и базируется на схеме, первоначально представленной ElGamal и Schnorr.

Существует три параметра, которые являются открытыми и могут быть общими для большой группы пользователей.

160-битное простое число q, т.е. 2¹⁵⁹ < q < 2¹⁶⁰.

Простое число р длиной между 512 и 1024 битами должно быть таким, чтобы q было делителем (р - 1), т.е. 2^L-1 < p < 2^L, где 512 < L < 1024 и (p-1)/q является целым.

g = h^(p-1)/q mod p, где h является целым между 1 и (р-1) и g должно быть больше, чем 1,10.

Зная эти числа, каждый пользователь выбирает закрытый ключ и создает открытый ключ.

Закрытый ключ х должен быть числом между 1 и (q-1) и должен быть выбран случайно или псевдослучайно.

x - случайное или псевдослучайное целое,0 < x < q,

Открытый ключ вычисляется из закрытого ключа как у = g^x mod p. Вычислить у по известному х довольно просто. Однако, имея открытый ключ у, вычислительно невозможно определить х, который является дискретным логарифмом у по основанию g.

y = g^x mod p

k - случайное или псевдослучайное целое, 0 < k < q, уникальное для каждого подписывания.

Для создания подписи отправитель вычисляет две величины, r и s, которые являются функцией от компонент открытого ключа (p, q, g), закрытого ключа пользователя (х), хэш-кода сообщения Н (М) и целого k, которое должно быть создано случайно или псевдослучайно и должно быть уникальным при каждом подписывании.

r = (g^k mod p) mod qs = [ k^-1 (H (M) + xr) ] mod qПодпись = (r, s)

Получатель выполняет проверку подписи с использованием следующих формул. Он создает величину v, которая является функцией от компонент общего открытого ключа, открытого ключа отправителя и хэш-кода полученного сообщения. Если эта величина равна компоненте r в подписи, то подпись считается действительной.

w = s^-1 mod qu₁ = [ H (M) w ] mod qu₂ = r w mod qv = [ (g^u1 y^u2) mod p ] mod qподпись корректна, если v = r

Докажем, что v = r в случае корректной подписи.

Лемма 1. Для любого целого t, если

g = h^(p-1)/q mod pто g^t mod p = g^{t mod q} mod p

По теореме Ферма, так как h является взаимнопростым с p, то h^p-1 mod p = 1. Следовательно, для любого неотрицательного целого n

g^nq mod p	= (h(^p-1)/q mod p)^nq mod p
	= h^((p-1)/q) nq mod p
	= h^(p-1)n mod p
	= ((h^(p-1) mod p)^n) mod p
	= 1^n mod p = 1

Таким образом, для неотрицательных целых n и z мы имеем

g^nq+z mod p	= (g^nq g^z) mod p
	= ((g^nq mod p) (g^z mod p)) mod p
	= g^z mod p

Любое неотрицательное целое t может быть представлено единственным образом как t = nq + z, где n и z являются неотрицательными целыми и 0 < z < q. Таким образом z = t mod q.

Лемма 2. Для неотрицательных чисел a и b: g^{(a mod q + b mod q)} mod p = g^{(a+b) mod q} mod p.

По лемме 1 мы имеем

g^{(a mod q + b mod q)} mod p= g^{(a mod q + b mod q) mod q} mod p = g^{(a + b) mod q} mod p

Лемма 3. y^{(rw) mod q} mod p = g^{(xrw) mod q} mod p

По определению y = g^x mod p. Тогда:

y^{(rw) mod q} mod p = (g^x mod p)^{(rw) mod q} mod p по правилам = g^{x ((rw) mod q)} mod p модульной арифметики = g^{(x ((rw mod q))) mod q} mod p по лемме 1 = g^{(xrw) mod q} mod p

Лемма 4. ((H(M) + xr) w) mod q = k

По определению s = (k^-1 (H(M) + xr)) mod q. Кроме того, так как q является простым, любое неотрицательное целое меньшее q имеет мультипликативную инверсию. Т.е. (k k^-1) mod q = 1. Тогда:

(ks) mod q = (k((k^-1(H(M) + xr)) mod q)) mod q = (k (k^-1(H(M) + xr))) mod q = ((k^k-1) mod q) ((H(M) + xr) mod q) mod q = (H(M) + xr) mod q

По определению w = s^-1 mod q, следовательно, (ws) mod q = 1. Следовательно:

((H(M) + xr) w) mod q = (((H(M) + xr) mod q) (w mod q)) mod q = (((ks) mod q) (w mod q)) mod q = (kws) mod q = (k mod q) ((ws) mod q)) mod q = k mod q

Так как 0 < k < q, то k mod q = k.

Теорема. Используя определения для v и r, докажем, что v=r.

v = ((g^u1 y^u2) mod p) mod q = ((g^{(H(M) w) mod q} y^{(rw) mod q)} mod p) mod q = ((g^{(H(M) w) mod q} g^{(xrw) mod q)} mod p) mod q = ((g^{(H(M) w) mod q + (xrw) mod q)} mod p) mod q = ((g^{(H(M) w + xrw) mod q)} mod p) mod q = ((g^{w (H(M) + xr) mod q)} mod p) mod q = (g^{k mod p)} mod q = r

Дата добавления: 2014-12-23