1
$\begingroup$

I am new to ECC. I have just read about the elliptic curve $y^2=x^3-x+1$. I am copying the exact line

The elliptic curve is super-singular $E:y^2=x^3-x+1$ in affine coordinates defined over a Galois field $GF(3^m)$, $m=97$, whose irreducible polynomial is $x^{97}+x^{12}+2$.

Now I have three questions.

  1. How is this curve different from than ordinary elliptic curve $(GF (2^m))$?
  2. Can this graph be used to implement ECDH?
  3. How secure is this curve compared to NIST's recommended curve parameters?

Thank you in advance for your help.

$\endgroup$
0
1
$\begingroup$

Let see the details of the curve; Let $K = \operatorname{GF}(3^m)$ and the curve be defined by the equation $$E(K):y^2 = x^3 + 2x + 1 \quad\quad ;-1 \equiv 2 \bmod 3$$

  1. Yes, it is supersingular

  2. The group of rational points has order $$n = 19088056323407827075424725586944833310200239047$$ The order has two factors; $7 \cdot 2726865189058261010774960798134976187171462721$.

    The second factor ( large one) is $\approx$ 150-bit number.

  3. The generic DLog attack requires $\sqrt{n}$-time, so the security of the curve cannot be larger than $2^{75}$. Therefore cannot be used securely for ECDH.

    In today's standards, we at least require 128-bit security. That is why the Curve25519 is preferable, with some other properties like twist security

  4. It has no twist security at all. The twist has an order $19088056323407827075424246988286372075141058881$ and it has two large factors $(9594160501626613625431,1989549405617260510054951)$, (approx each is a 73-bit number) therefore no twist security.

  5. Curve that uses binary extension field $\operatorname{GF}(2^m)$ are effective in the calculation, however, some binary extension has no longer secure effective sizes. Using 3 as a base field is harder to use a large field like Curve25519.

  6. According to the current NIST curves, it has lower security, though some of them don't twist security.

  7. Super Singular curves have been avoided for a long time. None of the standard curves are supersingular curve.


SageMath code

K = GF(3^97)
print(K)
E = EllipticCurve(K,[0,0,0,-1,1])
print(E)
print("Supersingular? : ", E.is_supersingular())
print("Order of E : ",E.order())
print("Factors of ord(E) : ", factor(E.order()))
E2 = E.quadratic_twist()
print("Quadratic Twist of E :",E2)
print("Order of Quadratic Twist :", E2.order() )
print("Factors of the order of Quadratic Twist :", factor(E2.order()) )
$\endgroup$
1
  • $\begingroup$ Note: The MOV attack on supersingular curves requires fields with characteristics larger than 3. I couldn't find one that can be applied to fields with characteristic 3. If you know, please inform. $\endgroup$
    – kelalaka
    Jan 16 at 14:02
2
$\begingroup$

This curve is thoroughly insecure. These researchers performed a computation to break discrete log on this exact curve.

All small characteristic pairing-friendly curves are insecure under modern knowledge. Here is another paper breaking discrete log on a curve over $\operatorname{GF}(3^{6\cdot 509})$ -- note that this field size is much bigger than your curve.

$\endgroup$
2
  • $\begingroup$ Addition:it follows that ECDH on this curve is breakable. The general wisdom is to avoid super-singular Elliptic Curves for "standard" ECC uses, including ECDH, Schnorr signature, Pedersen Commitment, ElGmal encryption, ECIES, ECDSA. Being super-singular is the most important difference with standard curves. Using a field of characteristic 3 rather than 2, or a large prime, is comparatively minor. $\endgroup$
    – fgrieu
    Jan 16 at 16:12
  • $\begingroup$ No English version of the first paper? $\endgroup$
    – kelalaka
    Jan 16 at 16:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.