1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
1
$\begingroup$

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.
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.