Computer Security and Cryptography

15.7 SUPERSINGULAR ELLIPTIC CURVES

The strength that cryptographic systems derive from elliptic curves depends on the difficulty of solving the elliptic curve discrete logarithm problem (ECDLP) and factorization in an elliptic curve: given x = pq, find p and q. It is believed that factorization algorithms have exponential execution times.

Are there bad elliptic curves? More precisely, are there some elliptic curves in which the factorization problem is not as hard?

If the order q of _p(a, b) were p or a divisor of p^m − 1 for some m, then bad news. Menezes et al. [1991] give a subexponential algorithm for the supersingular elliptic curves.

The National Institute of Standards [NIST, 2000, NIST186-2] has given its Good Crypto seal of approval to several elliptic groups; in each example, the coordinates (G_x, G_y) of the base point P and its order r are given. One of these groups, designated by NIST as P192, is based on the 192-bit prime p = 2¹⁹² − 2⁶⁴ + 1.

Say you are not satisfied – well, then try P521:

There are elliptic curves over binary fields; for example

• K163 is generated by the polynomial p(x) = 1 + x³ + x⁶ + x⁷ + x¹⁶³, and
• K571 is generated by the polynomial p(x) = 1 + x² + ...