I can't seem to verify the signature scheme described below.

Key Generation

Public Key: $$y_1=g^{a_1}y^{a_2} \pmod p$$ $$y_2=g^{b_1}y^{b_2} \pmod p$$ $g$ denotes a generator of $Z_p^*$ and $y$ is a random element from $Z_p^*$. The private key is $(a_1,a_2,b_1,b_2)$.

Signing $$\sigma_1=a_1m+b_1 \pmod q$$ $$\sigma_2=a_2m+b_2 \pmod q$$ where $q\mid p-1$. The signature on $m$ is $(\sigma_1,\sigma_2)$.

Verification. To verify $(m,\sigma_1,\sigma_2)$ one does the following. $$y_1^my_2 \overset{?}{=} g^{\sigma_1}y^{\sigma_2}\pmod p$$

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} \cdot 16^{20} = 13 \pmod{23}$$ $$y_2 = 7^{3}\cdot 16^{18} = 10 \pmod{23}$$

Now signing a message $m = 13$:

$$\text{output}_1 = 12(13) + 3 = 1 \pmod 2$$ $$\text{output}_2 = 20(13) + 18 = 0 \pmod 2$$

Verifying gives me:

Equation 1 = $13^{13} \cdot 10 = 11 \pmod {23}$

Equation 2 = $7^1\cdot 16^0 = 7 \pmod {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 at which step I go wrong?


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.

| improve this answer | |
  • $\begingroup$ Thanks for the clarification!! May I know what does it mean by $g$ and $y$ must be of order $q$? Any examples? $\endgroup$ – Calvin Peh Nov 8 '14 at 16:27
  • $\begingroup$ $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$ $\endgroup$ – poncho Nov 8 '14 at 17:10

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.