I am supposed to implement ECC over binary field (in C++) for equations of the type - $y^2 + xy = x^3 + ax + b$, as my project. I wish to include the following features :
- The user will enter a prime number $m$, which will serve as the order of the binary field as $2^m$.
- For the given $m$, the irreducible polynomial will be generated.
Q1. AFAIK, there is no method to efficiently find a random irreducible polynomial. The only way is to pick a random polynomial and check whether it is irreducible or not. (The polynomial can be no more than pentanomial, and trinomial in some cases) Am I thinking the right way?
- The coefficients $a$ and $b$ will be generated.
Q2. Can I use random number generator (with appropriate constraints) to generate $a$ and $b$ instead of producing it from a Seed $S$ ? Also, I have seen both Seed $S$ and the parameter $b$ being mentioned. What is the purpose to write both the things when $S$ is sufficient to generate $b$ ?
- Various points that lie on the curve will be listed.
Q3. To generate all the points, put $x=0, 1, 2 ...m-1$ and solve for $y$ for equations of the type : $y^2 + ky = l$. How to find the square root in such a scenario? Is there any better way to generate all the points?
- Schoof's algorithm and the likes will be demonstrated to count all the points lying on the elliptic curve. (Though all the points have already been generated, but presenting an algorithm will be an added advantage)
- A suitable base point $P$ will be chosen such that it has reasonably low cofactor.
Q4. To find such a point, the order of each and every point should be found out. The only way that I can think of is : Pick a point $Q$. Find $2Q, 3Q$ until the points start repeating. Hence, one gets the order. Do so for all the points while maintaining the maximum order. Is there any better way to achieve it?
- Finally an El-Gamal and/or Diffie Hellman analogous of ECC over binary field will be presented.
I would like to get clarification on above questions based on the mentioned scenarios. As of now, I don't have sufficient knowledge of ECC so it is pretty much possible that I have asked some nonsensical questions and I am really very sorry for it. Please feel free to share your ideas on these/any other features so as to make the project more worthy.