Illustration of DSA Algorithm: p,q=7,3

Cryptography Tutorials - Herong's Tutorial Examples

∟Introduction of DSA (Digital Signature Algorithm)

∟Illustration of DSA Algorithm: p,q=7,3

This section provides a tutorial example to illustrate how DSA digital signature algorithm works with small prime modulus p=7 and prime divisor q=3.

To demonstrate the DSA digital signature algorithm, let's try it with a smaller prime divisor q=3 and prime modulus p=7.

The process of generating the public key and private key can be illustrated as:

q = 3      # selected prime divisor
p = 7      # computed prime modulus: (p-1) mod q = 0
g = 4      # computed: 1 < g < p, g**q mod p = 1 
           #           and g = h**((p–1)/q) mod p
           #           4**3 mod 7 = 1: 64 mod 7 = 1
x = 5      # selected: 0 < x < q
y = 2      # computed: y = g**x mod p = 4**5 mod 7
{7,3,4,2}  # the public key: {p,q,g,y}
{7,3,4,5}  # the private key: {p,q,g,x}

With the private key {p,q,g,x}={7,3,4,5}, the process of generating a digital signature out a message hash value of h=3 can be illustrated as:

h = 3      # the hash value as the message digest
k = 2      # selected: 0 < k < q
r = 2      # computed: r = (g**k mod p) mod q = (4**2 mod 7) mod 3
i = 5      # computed: k*i mod q = 1: 2*i mod 3 = 1
s = 2      # computed: s = i*(h+r*x) mod q = 5*(3+2*5) mod 3
{2,2}      # the digital signature

The process of verifying the digital signature {r,s}={2,2} with the public key {p,q,g,y}={7,3,4,2} can be illustrated as:

h = 3      # the hash value as the message digest
w = 5      # computed: s*w mod q = 1: 2*w mod 3 = 1
u1 = 0     # computed: u1 = h*w mod q = 3*5 mod 3 = 0
u2 = 1     # computed: u2 = r*w mod q = 2*5 mod 3 = 1
v = 2      # computed: v = (((g**u1)*(y**u2)) mod p) mod q
           #             = (((4**0)*(2**1)) mod 7) mod 3 = 2
v == r     # verification passed