How to properly sign and verify using DSA? Can anyone spot my mistake?

The question that I am trying to answer is as follows:

10.14. The parameters of DSA are given by p = 59,q = 29,α = 3, and Bob’s private key is d = 23. Show the process of signing (Bob) and verification (Alice) for following hash values h(x) and ephemeral keys kE:

1. h(x) = 17,kE = 25

2. h(x) = 2,kE = 13

3. h(x) = 21,kE = 8

I managed to figure out part 1 correctly and then modeled the other two parts after part 1, but the problem is that both part 2 and part 3 came out to be invalid in the verification stage, and I am pretty sure that they were supposed to be valid. Here is my work:

1. h(x) = 17,kE = 25

Generation(Bob):

Chooses values p=59, q=29, α=3, d=23
Computes β = αd = 323 mod 59= 45 mod 59
sends (p, q, α, β)= (59, 29, 3, 45)
Actual signature generation:
compute hash message of h(x)= 17
1. choose enphemeral key kE = 25
2. r=(α^kE mod p) = 3^25 mod 59 = 51 mod 59
3. s= (h(x)+d*r)*α= (17+23*51)*3= 3,570 mod 59= 30 mod 59

sends (x,(r,s))= (x,(51, 30))


Verification(Alice):

1. w= r^(-1) mod q = 51^(-1) mod 29= 22^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm)
29= 22(1)+7
22= 7(3)+1
-----------
1= 22+ 7(-3)            //Set equal to 1
= 22+ (29+22(-1))(-3) //Substitute
=29(-3)+ 22(4)        //Distribute
22^(-1) mod 29 = 4 mod 29
2. u1= w*h(x) mod q = 4*17 = 68 mod 29 = 10 mod 29
3. u2= w*r mod q = 4*51= 204 mod 29= 1 mod 29
4. v = (α^(u1) * β^(u2) mod p)mod q
= (3^(10)*45^(1)) mod 59) mod 29
= (59,049*45 mod 59)mod 29
=(2,657,205 mod 59)mod 29
=  22 mod 29
5. v=22,
r mod q= 51 mod 29 = 22 mod 29
v = r mod q → Valid signature

1. h(x) = 2,kE = 13

Generation(Bob):

Chooses values p=59, q=29, α=3. d=23
Computes β = αd = 323 mod 59= 45 mod 59
sends (p, q, α, β)= (59, 29, 3, 45)

Actual signature generation
compute hash message of h(x)= 2
1. choose enphemeral key kE = 13
2. r=(α^(kE) mod p) = 3^(13) mod 59 = 1,594,323 mod 59 = 25 mod 59
3. s= (h(x)+d*r)*α= (2+23*25)*3= 1,731 mod 59= 20 mod 59
sends (x,(r,s))= (x,(25, 20))


Verification(Alice):

1. w= r^(-1) mod q = 25^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm)
29= 25(1)+4
25= 4(6)+1
--------------------
1= 25+ 4(-6)             //Set equal to 1
= 25+ (29+25(-1))(-6)  //Substitute
=29(-6)+ 25(7)         //Distribute
25^(-1) mod 29 = 7 mod 29
2. u1= w*h(x) mod q = 7*2 = 14 mod 29
3. u2= w*r mod q = 7*25= 175 mod 29= 1 mod 29
4. v = (α^(u1) * β^(u2) mod p)mod q
= (3^(14)*45^(1) mod 59) mod 29
= (4,782,969*45 mod 59)mod 29
=(215,233,605 mod 59)mod 29
=  12 mod 29
5. v=12, r mod q= 25 mod 29
v ≠ r mod q → Invalid signature

1. h(x) = 21,kE = 8

Generation(Bob):

Chooses values p=59, q=29, α=3. d=23
Computes β = αd = 323 mod 59= 45 mod 59
sends (p, q, α, β)= (59, 29, 3, 45)

Actual signature generation
compute hash message of h(x)= 21
1. choose enphemeral key kE = 8
2. r=(α^(kE) mod p) = 3^(8) mod 59 = 6,561 mod 59 = 12 mod 59
3. s= (h(x)+d*r)*α= (21+23*12)*3= 891 mod 59= 6 mod 59
sends (x,(r,s))= (x,(12, 6))


Verification(Alice):

1. w= r-1 mod q = 12^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm)
29= 12(2)+5
12= 5(2)+2
5= 2(2)+1
------------------
1= 5+2(-2)                  //Set equal to 1
= 5+(12+5(-2))(-2)        //Substitute
=12(-2)+ 5(5)             //Distribute
= 12(-2)+(29+12(-2))(5)   //Substitute
=29(5)+ 12(-12)           //Distribute
12^(-1) mod 29 =-12 mod 29
w= 17 mod 29
2. u1= w*h(x) mod q = 17*21 = 357 mod 29= 9 mod 29
3. u2= w*r mod q = 17*12= 204 mod 29= 1 mod 29
4. v = (α^(u1) * β^(u2) mod p)mod q
= (3^(9)*45^(1) mod 59) mod 29
= (19,683*45 mod 59)mod 29
=(885,735 mod 59)mod 29
=  27 mod 29
5. v=27, r mod q= 12 mod 29
v ≠ r mod q → Invalid signature


I have no idea what I did wrong. I checked my answers several times, so if someone could point out the mistake that I made that I cannot see, I would appreciate it!

Keeping your notation, signature generation in DSA is the following:

• $$r = (\alpha^{kE} \bmod p) \bmod q$$
• $$s = kEinv \times (h(x) + d\times r) \bmod q$$

where $$kEinv$$ is the modular inverse of $$kE$$ modulo $$q$$.

But you actually did was using the formula $$s= (h(x)+d\times r) \times \alpha \bmod q$$, and you forgot to reduce $$r$$ modulo $$q$$. You can take a look at the wikipedia page.

Among errors:

• In proper DSA, $$s=\left({k_E}^{-1}\right)\,\left(h(x)+d\,r\right)\bmod q$$, not $$s=\left(h(x)+d\,r\right)\,α\bmod p$$ as in the question.
That computation (including the missing modular inverse) must be performed $$\bmod q$$; and $$α$$ is unwanted. That's mostly what prevents some examples from working.
• In proper DSA, $$r=\left(α^{k_E}\bmod p\right)\bmod q$$, not $$r=\left(α^{k_E}\bmod p\right)$$ as in the question.
Removing the final $$\bmod q$$ is non-standard, and prevents standard-compliant DSA from accepting some of the signatures, since $$r$$ should be checked to be in range $$(0,q)$$ as a preliminary step of signature verification. However it does not interfere with the rest of signature generation or verification, which manipulates $$r$$ molulo $$q$$; and is not too dangerous since the quantity $$α^{k_E}\bmod p$$ is recomputed (albeit differently) as part of the signature verification process. Still, the scheme looses strong unforgettability.
• There are missing exponent signs and typos, for example β = αd = 323 mod 59= 45 mod 59 should be $$β=α^d\bmod p=3^{23}\bmod59=45$$.
• The question often adds extra mod that obscure the intended meaning. Example beside the above: there is 68 mod 29 = 10 mod 29 when 68 mod 29 = 10 is the proper statement that the result is 10, rather than 68 or 39.
Remember that $$u\bmod n$$ is the uniquely defined integer $$v$$ in range $$[0,n)$$ with $$u-v$$ multiple of $$n$$, rather than (a member of) the set of integers with $$u-v$$ multiple of $$n$$, that is $$v\equiv u\pmod n$$.
The distinction is often important in crypto. For example, the incorrect $$r=\left(α^{k_E}\bmod p\right)$$ of the question does verify $$r\equiv\left(α^{k_E}\bmod p\right)\pmod q$$, which is why it works from the standpoint of making verifiable signature; but often it does not verify $$r=\left(α^{k_E}\bmod p\right)\bmod q$$, as required for conformance and perhaps security.