Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Not all elliptic curves are safe to use for cryptography, especially from an ECC safety perspective. The site http://safecurves.cr.yp.to/index.html shows that two tested Brainpool curves, brainpoolP256t1 and brainpoolP384t1, are not ECC security safe even though they are ECDLP safe. Not all the Brainpool curves were evaluated however.

I am curious if the 320-bit curves brainpoolP320r1 and brainpoolP320t1 pass these safety tests. These curves are defined in RFC5639.

I see the Sage verification script is provided, http://safecurves.cr.yp.to/verify.html. It requires many parameters to set it up for testing these curves, such as a list of all the prime divisors of q-1 for each q in the list. I'm not sure how to correctly do this.

Has any crypto experts or enthusiast verified 320-bit curves or is there an easier way to to perform the testing (such a a program that does not require so much complex setup)?

Alternatively could some help explain how to correctly setup the parameters for the Sage script to test these curves (or any curves in general).

The instructions are: Each directory contains the following files:

p: the field prime, in decimal.
l: the prime order of the base point, in decimal.
x1: the x-coordinate of the base point.
y1: the y-coordinate of the base point.
x0: the x-coordinate of a point generating the entire curve.
y0: the y-coordinate of a point generating the entire curve.
shape: the curve shape, either shortw or montgomery or edwards.
a and b, if the curve shape is shortw: the coefficients in the short Weierstrass equation.
A and B, if the curve shape is montgomery: the coefficients in the Montgomery equation.
d, if the curve shape is edwards: the coefficient in the Edwards equation.
primes: all prime divisors of of p, the curve order p+1-t, the twist order p+1+t, and t^2-4p; and, recursively, all prime divisors of q-1 for each q in the list.

And the curves are defined as: -

Curve-ID: brainpoolP320r1

  p = D35E472036BC4FB7E13C785ED201E065F98FCFA6F6F40DEF4F92B9EC7893EC
  28FCD412B1F1B32E27

  A = 3EE30B568FBAB0F883CCEBD46D3F3BB8A2A73513F5EB79DA66190EB085FFA9
  F492F375A97D860EB4

  B = 520883949DFDBC42D3AD198640688A6FE13F41349554B49ACC31DCCD884539
  816F5EB4AC8FB1F1A6

  x = 43BD7E9AFB53D8B85289BCC48EE5BFE6F20137D10A087EB6E7871E2A10A599
  C710AF8D0D39E20611

  y = 14FDD05545EC1CC8AB4093247F77275E0743FFED117182EAA9C77877AAAC6A
  C7D35245D1692E8EE1

  q = D35E472036BC4FB7E13C785ED201E065F98FCFA5B68F12A32D482EC7EE8658
  E98691555B44C59311

  h = 1

Curve-ID: brainpoolP320t1 #Twisted curve

  Z = 15F75CAF668077F7E85B42EB01F0A81FF56ECD6191D55CB82B7D861458A18F
  EFC3E5AB7496F3C7B1

  A = D35E472036BC4FB7E13C785ED201E065F98FCFA6F6F40DEF4F92B9EC7893EC
  28FCD412B1F1B32E24

  B = A7F561E038EB1ED560B3D147DB782013064C19F27ED27C6780AAF77FB8A547
  CEB5B4FEF422340353

  x = 925BE9FB01AFC6FB4D3E7D4990010F813408AB106C4F09CB7EE07868CC136F
  FF3357F624A21BED52

  y = 63BA3A7A27483EBF6671DBEF7ABB30EBEE084E58A0B077AD42A5A0989D1EE7
  1B1B9BC0455FB0D2C3

  q = D35E472036BC4FB7E13C785ED201E065F98FCFA5B68F12A32D482EC7EE8658
  E98691555B44C59311

  h = 1

Where:

  p is the prime specifying the base field.

  A and B are the coefficients of the equation y^2 = x^3 + A*x + B
  mod p defining the elliptic curve.

  G = (x,y) is the base point, i.e., a point in E of prime order,
  with x and y being its x- and y-coordinates, respectively.

  q is the prime order of the group generated by G.

  h is the cofactor of G in E, i.e., #E(GF(p))/q.

  For the twisted curve, we also give the coefficient Z that defines
  the isomorphism F (see requirement 3 in Section 2.2).

So for verify.sage (LHS is files for verify sage, RHS is from RFC):

  p = int(p)
  l = int(q)   # I think, IIUC
  x1 = int(x)
  y1 = int(y)
  x0 = ???
  y0 = ???
  shape = ??   # for brainpoolP320r1 either "shortw" or "montgomery"? For brainpoolP320t1  "edwards"?
  a = A
  b = B
  A = A
  B = B
  d = int(Z)   # for brainpoolP320t1 only
  primes = ???

Note: where I say int(x) it's to convert for hexadecimal representation to decimal. The result is what would be saved in the text file for verify.sage to use.

I'm afraid I understand ECC, EC, and maths too little to be able to do this.

I will be grateful if someone would kindly help me.


Edit: I think, because this question was migrated, it does not show up in my profile as a question I asked, even though I can edit the question. I also cannot accept the answer below that clearly states neither are safe curves. If possible can a mod either permit me to accept the answer or accept it on my behalf?

share|improve this question

migrated from security.stackexchange.com Jun 19 at 9:32

This question came from our site for Information security professionals.

    
There's enough of an "applied security" aspect to it that this question also fits here. –  Mark Jun 19 at 8:25

1 Answer 1

A curve with cofactor 1, like all Brainpool curves, cannot possibly satisfy the SafeCurves criteria, so the answer to your question is no.

Whether that means that they are actually "unsafe" for use in practice is debatable. I think it would be fair to say that implementing such curves in a secure way is perfectly doable in practice, but it's trickier to do so than with one of the SafeCurves, and performance will suffer as a result.

share|improve this answer
1  
The generation of the parameters is not fully according to SafeCurve standards either. It's considered better than the (completely unspecified) method that NIST / Certicom curves have used to generate the curves, but it cannot be verified that there was no attempt to steer the values one way or another - it's just likely that they haven't been tampered with. –  Maarten Bodewes - owlstead Jun 22 at 16:47

Your Answer

 
discard

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