A toy Digital Signature Algorithm example
Math 202 Cryptography
November 12, 2018

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Verify p=823, q=137, α=729 are valid choices for a small example

p=823;
q=137;
α=729;

First verify q divides p-1 by checking (p-1) mod q = 0

Mod[p-1,q]

Now check that ord(α)=q

MultiplicativeOrder[α, p]

Use d=97 to compute Alice’s β

d=97;
β=PowerMod[α,d,p]

Sign x=”If all porkchops were perfect, there wouldn’t be hotdogs.”
using k_E=46

x="If all porkchops were perfect, there wouldn't be hotdogs.";
kE=46;
Hash[x,"SHA"]

For this toy example, we need to reduce mod q
Also calculate (k_E)^-1 mod q

shaModq=Mod[Hash[x,"SHA"],q]
kEinv=PowerMod[kE,-1,q]

Now calculate r and s

r=Mod[ PowerMod[α,kE,p], q]
s=Mod[ (shaModq + d*r)*kEinv, q]

Alice will send (“If all porkchops were perfect, there wouldn’t be hotdogs.”, (71,49) )

Let’s verify the signature:
We get w=14, u1=75, u2=35

w=PowerMod[s,-1,q]
u1 = Mod[ w*Hash[x,"SHA"], q]
u2 = Mod[w*r,q]
v=Mod[Mod[  α^u1 * β^u2, p], q]

Does v=r?

v==r