Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Signature

I can't seem to verify this signature scheme.

Taking this as an example: $p = 23$, $g = 7$, Private Key : $(12$, $20$, $3$, $18)$, $y = 16$ and $q = 2$

This will give me:

$y_1 = 7$12$*16$20 $= 13 (mod23)$

$y_2 = 7$3$*16$18 $= 10 (mod23)$

Now signing a message $m = 13$:

$output1 = 12(13) + 3 = 1 (mod 2)$

$output2 = 20(13) + 18 = 0 (mod 2)$

Verifying gives me:

Equation 1 = $13$13$*10$$ = 11 (mod 23)$

Equation 2 = $7$1$*16$0$ = 7 (mod 23)$

As you can see from the above equation, 11 is not equal to 7 and I cannot verify it.

I suspect the problem lies with using the wrong $q$. Should the value of q exclude 1 and 2?

Any idea which step I go wrong?

share|improve this question

1 Answer 1

The text you quoted appears to be incorrect; as specified, it doesn't always work (as you found out).

$y_1^m y_2 = g^{\sigma_1} y^{\sigma_2}$ will hold in general if both of the following are true:

$$a_1 m + b_1 \equiv \sigma_1 \pmod{p-1}$$

$$a_2 m + b_2 \equiv \sigma_2 \pmod{Order(y)}$$

Note: it is possible for the equation to hold in other conditions, but because $y$ has no known relationship with $g$, it would be infeasible to find other solutions for non-toy instances of this problem, even for the valid signer.

However, the text specifies that $\sigma_1$ and $\sigma_2$ are computed modulo $q$; if $q < p-1$, then neither of these equations are guaranteed to hold.

I can see two obvious ways to fix up this method:

  • Specify $q = p-1$; then both $\sigma_1$ and $\sigma_2$ will satistfy the above conditions (N.B.: all possible values of $y$ have an order that is a divisor of $p-1$)

  • Allow any $q | p-1$; however, specify that both $g$ and $y$ must be of order q.

Also, as specified, this scheme would appear to be insecure as a signature scheme; with two valid signatures, an attacker should be able to recover $a_1, a_2, b_1, b_2$, which is the private key.

share|improve this answer
    
Thanks for the clarification!! May I know what does it mean by $g$ and $y$ must be of order $q$? Any examples? –  Calvin Peh Nov 8 at 16:27
    
$g$ is of order $q$ if $g^q \equiv 1$ (and if there is no smaller $q > 0$ where this holds; although that's actually not important in this case). In your example, $g$ is of order 22. An alternative value with order 11 would be $g=2$ –  poncho Nov 8 at 17:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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