Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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.) – K.G. Nov 7 '13 at 10:04
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. – K.G. Nov 7 '13 at 10:06
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. – DrLecter Nov 7 '13 at 12:30

Your Answer


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

Browse other questions tagged or ask your own question.