0
$\begingroup$

There is an elliptic curve El Gamal digital signature scheme. Alice fixes an elliptic curve $E$, a prime $p$, a point $A$ on $E$, a secret integer $a$, and computes $B = aA$. She makes $(E, p, A, B)$ public. To sign a message m (which is an integer), she computes a point $R = (x, y)$ on $E$ and an integer $s$, and sends $(m, R, s)$. The verification is $xB + sR = mA$. Eve chooses $R1 = B − A = (x1, y1)$.

How do I find an integer $s1$ and message $m1$ so that $(m1, R1, s1)$ is a valid signature?

I referred to this to relate the normal El Gamal to the one on the Elliptic curve, but am not able to do so. Also, why is hashing required in such situations to prevent such forgery?

$\endgroup$
1
$\begingroup$

As a more generic answer than poncho's, which works on all curves and not just those with a point of order 2: we can simply compute $$ x_1 B + s_1 R_1 = x_1 B + s_1 (B-A) = (x_1+s_1) B - s_1 A. $$ Therefore, picking $s_1 = -x_1$ and $m = -s_1 = x_1$ gives a forgery.

So the scheme “without a hash function” is clearly insecure. But even “with a hash function”, it's probably not possible to write a clean security proof for this kind of unreasonable construction (similar to what happens with ECDSA). Let's use Schnorr, please.

$\endgroup$
0
$\begingroup$

Well, one obvious method (which assumes that either there's a point on the elliptic curve with $x=0$, or the verifier doesn't check if $R$ is on the curve) is:

$$m1 = 0$$ $$R1 = (0, y)$$ $$s1 = 0$$

This satisfies the verification equation...

$\endgroup$

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.