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:


h(x) = 17,kE = 25
h(x) = 2,kE = 13
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:


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 



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 



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.