0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ What is the signature you produced, and what is the private key ($x$)? $\endgroup$
    – B-Con
    Oct 16, 2013 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$
    – user8339
    Oct 16, 2013 at 7:24

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • $\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$
    – user8339
    Oct 16, 2013 at 9:01
  • $\begingroup$ Then you should point out that the worksheet is buggy ;) $\endgroup$
    – DrLecter
    Oct 16, 2013 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$
    – user8339
    Oct 16, 2013 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, 2013 at 9:54
  • $\begingroup$ sorry but... how do you get $6$ from $2^{-1}$?? $\endgroup$
    – user8339
    Oct 16, 2013 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.