Generating one's own elliptic curve. posted July 2016

Dear Mr.DAVID
I am learning about generating an elliptic curves cryptography , in your notes I find:-
JPF: Many people don’t trust NIST curves. How many people verified the curve generation? Open source tools would be nice.
Flori: people don't trust NIST curves anymore, surely for good reasons, so if we do new curves we should make them trustable. Did anyone here tried generating nist, dan, brainpool etc...? (3 people raised their hands).
Would you give me some reasons for generating our own curves? what are the good reasons that some people do not trust on NIST CURVES?
your sincerely
hager

Hello Mr. HAGER

Well, the history of how standard curves were generated has been pretty chaotic, and djb has shown that this might be a bad thing for us in his Bada55 paper.

NIST says that they generated their curves out of the hash of a sentence that is unknown and lost. The german Brainpool curves seem to ignore their own standards on how to generate secure curves.

one of the standard Brainpool curves below 512 bits were generated by the standard Brainpool curve-generation procedure

So how bad is it? We know that choosing random parameters for your crypto algorithms can lead to unsecure or even backdoored constructions. See how to choose Sboxes in DES, how to choose nothing-up-my-sleeve numbers for hash functions, how to choose secure parameters for Diffie-Hellman, how Dual EC is backdoored if you know how the main points P and Q were generated, ...

Well, so far we don't really know. The fact that we haven't been able to crack any of the curves we use is "reassuring". I like to look at bitcoin as a proof that at least one of them hasn't been broken :) But as many researchers suspect, the NSA might be years ahead of us in cryptanalysis. So it is possible that they might have found one (or more) issues with elliptic curve cryptography, and that they generated "weak" curves before publishing them through NIST's standards.

So far, there hasn't been enough advances in ECC (a relatively old field in cryptography) to make you worried enough to generate your own curves. Some people do that though, but they know what they're doing. They even released a paper on how to generate safe curves using nothing-up-my-sleeves parameters. Like that, you can review the generation process and see that nothing was done to harm you.

Some people also worry about sparse primes, and that's one more paranoid reason to use random curves as above.

But seriously, if you don't want to go through all the trouble, you should probably start using one of the curve specified in this RFC: Curve 25519 or Curve 448. They use state-of-the-art research, reproducible generation and have been vetted by many people.