# DSA generate signature and verify

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.

• What is the signature you produced, and what is the private key ($x$)? – B-Con Oct 16 '13 at 4:51
• @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. – user8339 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.

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.

• 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. – user8339 Oct 16 '13 at 9:01
• Then you should point out that the worksheet is buggy ;) – DrLecter Oct 16 '13 at 9:07
• 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? – user8339 Oct 16 '13 at 9:28
• You are right, I thought this would be the mistake. But actually, I think you may make some errors when computing multiplicative inverses? – DrLecter Oct 16 '13 at 9:54
• sorry but... how do you get $6$ from $2^{-1}$?? – user8339 Oct 16 '13 at 9:58