Schnorr signature

Schnorr signature scheme — was invented by Claus Schnorr in 1989/91.

Keys

P - prime number ~ 1024 bits
Q - prime number ~  160 bits
P = Q*R + 1
  - Q must be a divisor of P-1
h - any number < (P - 1) for calculate generator G of subgroup of order Q
G - generator
G = h^( (P - 1) / Q ) = h ^ R ≢ 1 (mod P)
G ^ Q ≡ 1 (mod P) - (test) Q must be multiplicative order

X - secret key < Q, random number
Y - public key
Y = G ^ (Q-X) (mod Q)
Start by finding the prime number Q. Enter any number — Try the numbers until you find a prime number Similarly, find the prime number P. — This search is a bit more complicated, as it requires the condition P - 1 = Q * R Base number for searching the group generator 1 < h < p

Signing

M  - message
Ns - Nonsense, random choice.
Vs = G ^ Ns (mod P)
Ms = M ∥ Vs concatenation Message and subgroup element
S  = Ns + X * Ms (mod Q)
(Ms, S) - signature pair

Sn - You cannot use the same number for different messages.
The same public and private keys can be used to sign different messages, with the number Sn being selected anew for each message.

- Combining message and point (*)

Verifying

Vv = G^S * Y^Ms (mod P)
Mv = M ∥ Vv
- reCombining message and point (*)

If Ev = Es then the signature is verified.

(*) The combination of messages and points can be accomplished in various ways: XOR (exclusive or) operation, multiplication and exponentiation.

In practice, Es and Ev are obtained by hashing the concatenation of the point Vs(v) and the message.

Subskribita.net