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

Открытый ключ вычисляется из закрытого ключа как у = 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 q

s = [ k^-1 (H (M) + xr) ] mod q

Подпись = (r, s)

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

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

w = s^-1 mod q

u₁ = [ H (M) w ] mod q

u₂ = r w mod q

v = [ (g^u1 y^u2) mod p ] mod q

подпись корректна, если v = r