I'm trying to generate a signature for DSA with the following parameters:

$p = 23$ , $q = 11$ , $g = 3$ , $H(m) = 8$ , $x = 5$

for the life of me, I cannot choose a random $k$ ($0 > k > q$) that will give me $r$ , $s$ that 'add up' when calculating $w$, $u1$, $u2$, and verifying.

I don't know if I'm just doing my maths wrong, but I've tried every possible $k$ between $0$ and $11$ and I just can't get $v = r$ at the end of verification.

can someone please please help and show your working out if possible?

  • 2
    $\begingroup$ What is the signature you produced, and what is the private key ($x$)? $\endgroup$ – B-Con Oct 16 '13 at 4:51
  • $\begingroup$ @B-Con oops I forgot to give the private key. x=5. as for the signature - I have produced multiple ones while attempting to find a value of k that 'adds up' when calculating v. I think I may be doing something wrong in the calculations because surely at least one value > 0 < 11 must work. $\endgroup$ – zer0 Oct 16 '13 at 7:24

Ok, back to my initial answer (which I edited to the last version, thinking that you did not choose an appropriate generator):

I now think that you may calculate the inverses wrongly:

I tried it with $k=2$ and get:

$r=9,k^{-1}=6, s=10, w=10, u_1=3, u_2=2$ which works out.

Just as an additional comment:

Choosing a generator

Since the order $11$ is prime, you can simply choose an arbitrary element of $Z_{23}^*$, say $h$, and then compute your $g$ as $g=h^{22/11} \pmod{23}$, i.e., every element that lies in this subgroup is a generator of this subgroup.

Take for instance $h=2$ and compute $g=h^{2}\pmod{23}=4$ (in your case, $3$ is also fine).

General case: For the general case $Z_p^*$ with $p$ being prime, an element $g$ is a generator if it holds that all for all prime divisors of the order $p-1$ the following holds:

$g^{(p-1)/q_i}\neq 1 \pmod{p}$.

Typically, you construct $p$ as a safe prime, i.e. choosing prime $q$ and set $p=2q+1$ as, then you know the prime divisors $2$ and $q$ by construction.

  • $\begingroup$ hi! thank you so much for answering. I see what you're saying and I had not thought of it before. HOWEVER, this is revision I am doing and the question is on a worksheet given to the class. I didn't choose g... they gave us the value for g, p, q, x and H(m). That's why I said I couldn't come up with a suitable value for k... the only value they didn't specify in the question. $\endgroup$ – zer0 Oct 16 '13 at 9:01
  • $\begingroup$ Then you should point out that the worksheet is buggy ;) $\endgroup$ – DrLecter Oct 16 '13 at 9:07
  • $\begingroup$ are you sure?? I mean, the very first question in this set is to show that g has order q as required. our lectures say to calculate this by showing that: $g^q$ mod $p$ = $1$ . which it does... $3^1$$^1$ mod $23$ = $1$ . So how can it be wrong? $\endgroup$ – zer0 Oct 16 '13 at 9:28
  • $\begingroup$ You are right, I thought this would be the mistake. But actually, I think you may make some errors when computing multiplicative inverses? $\endgroup$ – DrLecter Oct 16 '13 at 9:54
  • $\begingroup$ sorry but... how do you get $6$ from $2^{-1}$?? $\endgroup$ – zer0 Oct 16 '13 at 9:58

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.