A Digital Signature Algorithm example
Math 202 Cryptography
November 14, 2018

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, and verify that q divides p-1.

PrimeQ[p]
IntegerLength[p,2]
PrimeQ[q]
IntegerLength[q,2]
Mod[p-1,q]

Verify that α has order q in (SuperStar[(Subscript[Z, p])]) 
	Pro-tip: You can get α by typing the sequence ESC a ESC
	Note: MultiplicativeOrder[α,p] may not work!

MultiplicativeOrder[α,p]

PowerMod[α,q,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”]

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

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]
v==r