In Elliptic Curve ElGamal, why are a=b=1 always legal for
primes whose lengths are no shorter than 11(2) bits long?

Is there any reason why the Point at Infinity can always be encoded as (0,0)?

Lastly, why unlike basic ElGamal, is (O,O) a legal message, where O is point at infinity?

I'm stuck with proving them. If you have any idea, please let me know it.

  • $\begingroup$ I'm assuming your first question is: When the prime field is large enough, why is $Y^2 = X^3 + X + 1$ an elliptic curve? You should compute $\Delta$, and your textbook will have a nice formula for that. Second, how to represent the point at infinity? If you want to represent it as a pair, that pair cannot also represent a point on the curve. Now check if (0,0) is on the curve you are considering. (This isn't true for general elliptic curves.) $\endgroup$ – K.G. Nov 7 '13 at 10:04
  • $\begingroup$ The third question seems a bit silly. Some people like excluding $0$ both as a secret key and as the random number used during encryption. Other people don't. I cannot understand why you would exclude it for ElGamal over a finite field, but not for ElGamal over elliptic curves. $\endgroup$ – K.G. Nov 7 '13 at 10:06
  • $\begingroup$ For the third point the question is what is meant by "legal message". In any variant of ElGamal you can encrypt $m$ being the identity element ($O$ in the Elliptic curve setting and $1$ in the prime field setting). Actually, this is quite useful, since it allows re-randomization of ElGamal ciphertexts without changing the message. $\endgroup$ – DrLecter Nov 7 '13 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.