A Digital Signature Algorithm Example

Math 202 Cryptography, November 16, 2016
T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Key Generation

p=
q=1331985975749110751467452671644594430583873510479
α = 
d=178482584654999441663585665066279244253783610235

Use the commands PrimeQ[p] and IntegerLength[p,2] to verify that p is prime and of the correct size. Do the same for q.

PrimeQ[p]

IntegerLength[p,2]

PrimeQ[q]

IntegerLength[q,2]

Verify that α has order q in (SuperStar[(Subscript[ℤ, p])])

MultiplicativeOrder[α,p]

Oops. This takes too long for Mathematica to calculate.

PowerMod[α,q,p]

Since q is prime, α ≢1 mod p, and (α^q)≡ 1 mod p, this shows that α has order q in (SuperStar[(Subscript[ℤ, p])])

Compute β

β=PowerMod[α,d,p]

Sign the message

x="You keep using that word,I do not think it means what you think it means."
kE = 758579245332948359575909007264541594859712766065

Determine the signature (r,s).
You will need to find ((Subscript[k, E])^(-1)) mod q and use the command Hash[x, “SHA”]

kEinv=PowerMod[kE,-1,q]

r=Mod[ PowerMod[α,kE,p],q]
s=Mod[ (Hash[x,"SHA"]+d*r)*kEinv, q]

Send (x, (r,s)) = 
(“You keep using that word,I do not think it means what you think it means.”, 60499814692998234849886716143041098598111013629, 498003204580276251886417025817521043707741125106)

Verify the signature

w=PowerMod[s,-1,q]
u1=Mod[ w*Hash[x,"SHA"],q]
u2=Mod[w*r,q]

v=Mod[Mod[ PowerMod[α,u1,p]*PowerMod[β,u2,p], p], q]

And v=r as it should!