• Introduction

In August 1991, NIST (Nation Institute of Standards and Technology) proposed a digital signature algorithm (DSA) for use in their digital signature standard (DSS)
[/list]

But NIST’s announcement has caused a lot of condemnation, and these condemnations are more political than academic. Many large software companies that have obtained the RSA algorithm patent license have also against DSS. They have invested a lot of money to implement the RSA algorithm. Of course, they do not want these funds to be lost in vain.

This is a more advanced method of verification, not only public key, private key, but also digital signature. The private key is encrypted to generate a digital signature, and the public key verifies the data and signature. If the data and the signature do not match, the verification fails. The function of digital signature is to verify that data is not modified during transmission. Digital signature is an upgrade of one-way encryption.

• process

• Mathematical logic

1.The public key y consists of 4 parameters
y ：y= g^x mod p
p：512~1024 bit prime number
q：160 bits and a factor that is relatively prime to p-1
g：g=h^(p-1)/q mod p, where h is less than p-1，h^(p-1)/q mod p> 1
The public key is (p, q, g, y)

2.Private key x in DSA signature:
x：x<q

3Message digest h(m)

4.The signature process in the DSA signature algorithm:
r：r (signature) = (g^k mod p) mod q
s：s(signature) = (k^-1 (H(m)+xr )) mod q
The signature is (m, r, s)

5.The verification process in the DSA signature algorithm:
Verification: (m₂, r₂, s₂）=(m, r, s)
v = (( g^u1 * y^u2 ) mod p ) mod q
w = s^-1 mod q
u1 = （H(m)×w）mod q
u2 = ( r w ) mod q

If v=r, the signature is verified

• example

(1) Alice generates a random number k, k<q.

(2) Alice produces:
r = (g^k mod p) mod q
s = (k^-1 (H(m)+xr )) mod q
Among them, r and s are her signatures, and she sends them to Bob.

(3) Bob verifies the signature by calculation:
w = s^-1 mod q
u₁ = (H(m)×w) mod q
u₂ = (rw) mod q
v = ((g^u1 × y^u2) mod p) mod q

If v=r, the signature is valid.

[/list]