########################
# SCRIPT: dsa_test.txt #
########################
# EXAMPLE OF THE DSA from APPENDIX 5 FIPS PUB 186-2 
# "DIGITAL SIGNATURE STANDARD (DSS)", 27 January 2000

puts "EXAMPLE OF THE DSA from APPENDIX 5 FIPS PUB 186-2"
puts "INPUT..."
p = 0x8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291
printf("p=%x\n",p)
q = 0xc773218c737ec8ee993b4f2ded30f48edace915f
printf("q=%x\n",q)
g = 0x626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
printf("g=%x\n",g)
x = 0x2070b3223dba372fde1c0ffc7b2e3b498b260614
printf("x=%x\n",x)
k = 0x358dad571462710f50e254cf1a376b2bdeaadfbf
printf("k=%x\n",k)
# h = SHA-1("abc")
h = 0xa9993e364706816aba3e25717850c26c9cd0d89d
puts 'M="abc"=0x616263'
printf("SHA-1(M)=%x\n",h)

puts "------------------------"
puts "COMPUTATION BY SIGNER..."
# COMPUTATION BY SIGNER 
# (p, q, g) are public, common values
#    x is signer's private key
#    k is a random integer 0 < k < q
#    Keep (x, k) secret
#
# Compute k' = k^{-1} mod q 
L = modinv(k, q)
printf("1/k mod q=%x\n", L)

# Compute y = g^x mod p
y = modexp(g,x,p)
printf("y=%x\n",y)
# Compute r = (g^k mod p) mod q
r = modexp(g,k,p) mod q
printf("r=%x\n",r)
# Compute s = (k^-1(SHA-1(M) + xr)) mod q 
s = (L * (h + x * r)) mod q
printf("s=%x\n",s)
puts "(r,s) = signature(M)"
puts "--------------------"

puts "VERIFICATION BY RECEIVER..."
# VERIFICATION BY RECEIVER 
# (p, q, g) are public, common values
#    y is signer's public key
#    (r,s) = signature(M)
#    Receiver receives (M', r', s').
#    Receiver recomputes SHA-1(M') for received message M'

# Check 0 < r' < q and 0 < s' < q
assert(q > r)
assert(q > s)
# Compute w = s^-1 mod q
w = modinv(s, q)
printf("w=%x\n",w)
# Compute u1 = ((SHA-1(M'))w) mod q
A = modmul(h, w, q)
printf("u1=%x\n", A)
# Compute u2 = ((r')w) mod q
B = modmul(r, w, q)
printf("u2=%x\n", B)

# Compute g^u1 mod p
# Compute y^u2 mod p
# Compute v = (((g^u1)(y^u2)) mod p) mod q
v = modmul(modexp(g,A,p), modexp(y,B,p), p) mod q
printf("v=%x\n", v)

# Verify that v = r'
puts "Check that v == r"
if (v == r) then puts "Signature verified OK" else puts "Signature verification FAILED!" fi
assert(v == r)