SafeCurves: 

BADA55 elliptic curvesThis page has been superseded by bada55.cr.yp.to. You will be redirected there in 10 seconds. This page introduces four elliptic curves at three different security/performance levels:
BADA55VRVerifiably random parameters offer some additional conservative features. These parameters are chosen from a seed using SHA1 as specified in ANSI X9.62 [X9.62]. This process ensures that the parameters cannot be predetermined. The parameters are therefore extremely unlikely to be susceptible to future specialpurpose attacks, and no trapdoors can have been placed in the parameters during their generation. —Certicom SEC 2 2.0 (2010) Several standards, including Certicom SEC 2 1.0 (2000), IEEE Std 1363 (2000), ANSI X9.63 (2001), and Certicom SEC 2 2.0 (2010), recommend "verifiably random" elliptic curves, where "verifiably random" means that the curve coefficients are hashes of a public seed. The NIST elliptic curves are "verifiably random". The BADA55VR curves are also "verifiably random". They are designed to address the following concerns regarding the NIST elliptic curves:
The BADA55VR curves are "verifiably random" using the SHA3 competition winner Keccak rather than SHA1. They are twistsecure, with cofactor 1 and twist cofactor 1. They use the same primes as the NIST curves, and the same curve shape x^3−3x+B; there are no known ways for discretelogarithm attacks to exploit those primes. BADA55VR256BADA55VR256 uses Keccak with 256bit output (keccakc512). The BADA55VR256 curve x^3−3x+B is defined from a seed S by the formula B=H(S), where H is the hash function. New seeds were generated until a curve was found meeting all security criteria. The following Sage script includes the seed S and verifies that x^3−3x+B passes the standard security criteria (with cofactor 1), plus twistsecurity (with cofactor 1): S = 0x3ADCC48E36F1D1926701417F101A75F000118A739D4686E77278325A825AA3C6 B = 0xBADA55ECD8BBEAD3ADD6C534F92197DEB47FCEB9BE7E0E702A8D1DD56B5D0B0C # not verified in this script: B is keccakc512 hash of S p = 2^256  2^224 + 2^192 + 2^96  1 k = GF(p) E = EllipticCurve([3,k(B)]) n = E.cardinality() print n != p print n.is_prime() print (2*p+2n).is_prime() print Integers(n)(p).multiplicative_order() * 100 >= n1 print Integers(2*p+2n)(p).multiplicative_order() * 100 >= 2*p+2n1 cmdisc = ((p+1n)^24*p).squarefree_part() if cmdisc % 4 != 1: cmdisc *= 4 print cmdisc > 2^100 BADA55VR224BADA55VR224 uses the same hash function as BADA55VR256 but uses a smaller prime; of course, B is implicitly reduced modulo the prime. Sage script: S = 0x3CC520E9434349DF680A8F4BCADDA648D693B2907B216EE55CB4853DB68F9165 B = 0xBADA55ECFD9CA54C0738B8A6FB8CF4CCF84E916D83D6DA1B78B622351E11AB4E # not verified in this script: B is keccakc512 hash of S p = 2^224  2^96 + 1 k = GF(p) E = EllipticCurve([3,k(B)]) n = E.cardinality() print n != p print n.is_prime() print (2*p+2n).is_prime() print Integers(n)(p).multiplicative_order() * 100 >= n1 print Integers(2*p+2n)(p).multiplicative_order() * 100 >= 2*p+2n1 cmdisc = ((p+1n)^24*p).squarefree_part() if cmdisc % 4 != 1: cmdisc *= 4 print cmdisc > 2^100 BADA55VR384BADA55VR384 is similar to BADA55VR256 but uses a larger prime. 256bit output is not long enough so BADA55VR384 instead uses Keccak with 384bit output (keccakc768). Sage script: S = 0xCA9EBD338A9EE0E6862FD329062ABC06A793575A1C744F0EC24503A525F5D06E B = 0xBADA55EC3BE2AD1F9EEEA5881ECF95BBF3AC392526F01D4CD13E684C63A17CC4D5F271642AD83899113817A61006413D # not verified in this script: B is keccakc768 hash of S p = 2^384  2^128  2^96 + 2^32  1 k = GF(p) E = EllipticCurve([3,k(B)]) n = E.cardinality() print n != p print n.is_prime() print (2*p+2n).is_prime() print Integers(n)(p).multiplicative_order() * 100 >= n1 print Integers(2*p+2n)(p).multiplicative_order() * 100 >= 2*p+2n1 cmdisc = ((p+1n)^24*p).squarefree_part() if cmdisc % 4 != 1: cmdisc *= 4 print cmdisc > 2^100 BADA55VPRThe choice of the seeds from which the [NIST] curve parameters have been derived is not motivated leaving an essential part of the security analysis open. ... Verifiably pseudorandom. The [Brainpool] curves shall be generated in a pseudorandom manner using seeds that are generated in a systematic and comprehensive way. Our method of construction is explained in Section 5. —Brainpool standard (2005) The Brainpool standard criticizes the NIST curves for the non"motivated" choice of seeds and instead recommends "verifiably pseudorandom" curves using "systematic" choices of seeds. The standard specifies various curves x^3+Ax+B mod p where A and B are generated as hashes of seeds derived from e = exp(1), the base of natural logarithms, and p is generated as a hash of a seed derived from π. However, the method used to generate the Brainpool curves has come into question, as illustrated by the obviously nonrandom overlap of digits between the following coefficients A and B (underlines added): CurveID: brainpoolP256r1 p: A9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377 A: 7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9 B: 26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6 Here is how this overlap was produced. Brainpool uses SHA1, which generates only 160 bits, so Brainpool concatenates multiple SHA1 outputs to obtain A, and concatenates multiple SHA1 outputs to obtain B. Brainpool uses a single seedincrement function to search for the first secure curve, to move from the first part of A to the second part of A, and to move from A to B. (The complete procedure is more complicated and does not always produce the same type of overlap; see the Brainpool standard for full details.) Johannes Merkle, lead author of the Brainpool TLS RFC, writes "I admit that this is unfortunate." The BADA55VPR curves are "verifiably pseudorandom" curves as recommended by Brainpool, with "systematic and comprehensive" explanations for their seeds. The BADA55VPR curves are designed to address the following concerns regarding the Brainpool curves:
The BADA55VPR curves use maximumsecurity fulllength SHA3512 (adequate for any reasonable prime size without concatenation), and complement the A seed to obtain a B seed that is guaranteed to be different. BADA55VPR224Brainpool already uses exp(1) = e and arctan(1) = π/4 (π and π/4 are equivalent here since bits are taken starting from the most significant), and MD5 already uses sin(1), so BADA55VPR224 uses cos(1). BADA55VPR224 generates the full 160bit seed as a 32bit counter followed by cos(1). It uses the first counter value that produces a secure curve. Sage script: cos1 = 0x8A51407DA8345C91C2466D976871BD2A print cos1 == Integer(RealField(128)(cos(1))*2^128) S = 0x000000B88A51407DA8345C91C2466D976871BD2A print S == 184*2^128 + cos1 # not verified by this script: 184 is first counter giving secure curve T = 0xFFFFFF4775AEBF8257CBA36E3DB99268978E42D5 print S+T == 2^1601 A = 0x7144BA12CE8A0C3BEFA053EDBADA555A42391FC64F052376E041C7D4AF23195EBD8D83625321D452E8A0C3BB0A048A26115704E45DCEB346A9F4BD9741D14D49 # not verified in this script: A is hash of S B = 0x5C32EC7FC48CE1802D9B70DBC3FA574EAF015FCE4E99B43EBE3468D6EFB2276BA3669AFF6FFC0F4C6AE4AE2E5D74C3C0AF97DCE17147688DDA89E734B56944A2 # not verified in this script: B is hash of T p = 2^224  2^96 + 1 k = GF(p) E = EllipticCurve([k(A),k(B)]) n = E.cardinality() print n != p print n.is_prime() print (2*p+2n).is_prime() print Integers(n)(p).multiplicative_order() * 100 >= n1 print Integers(2*p+2n)(p).multiplicative_order() * 100 >= 2*p+2n1 cmdisc = ((p+1n)^24*p).squarefree_part() if cmdisc % 4 != 1: cmdisc *= 4 print cmdisc > 2^100 Notes on terminology and securityThe name "BADA55" (pronounced "badass") is explained by the appearance of the string BADA55 near the beginning of each BADA55 curve. This string is underlined in the Sage scripts above. We actually chose this string in advance and then manipulated the curve choices to produce this string. The BADA55VR curves illustrate the fact that, as pointed out by Scott in 1999, "verifiably random" curves do not stop the attacker from generating a curve with a oneinamillion weakness. The BADA55VPR curves illustrate the fact that "verifiably pseudorandom" curves with "systematic" seeds generated from "nothingupmysleeve numbers" also do not stop the attacker from generating a curve with a oneinamillion weakness. We do not assert that the presence of the string BADA55 is a weakness. However, with a similar computation we could have selected a oneinamillion weakness and produced curves with that weakness. Suppose, for example, that twist attacks were not publicly known but were known to us; a random 224bit curve has one chance in a million of being extremely twistinsecure (attack cost below 2^30), and we could have generated a curve with this property, while pretending that this was a "verifiable" curve generated for maximum security. We view the terminology "verifiably random" as deceptive. The claimed randomness (a uniform distribution) is not being verified; what is being verified is merely a hash computation. We similarly view the terminology "verifiably pseudorandom" and "nothing up my sleeves" as deceptive. ContributorsBADA55 is joint work by the following authors (alphabetical order):
SlidesThe following presentation was given by Bernstein and Lange at the Eurocrypt 2014 rump session: (PDF) Papers[bada55] 18pp. (PDF) Daniel J. Bernstein, Tung Chou, Chitchanok Chuengsatiansup, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Christine van Vredendaal. How to manipulate curve standards: a white paper for the black hat. Document ID: bada55ecd325c5bfeaf442a8fd008c54. URL: http://cr.yp.to/papers.html#bada55. Date: 2014.07.22. AcknowledgmentsThis work was supported by the U.S. National Science Foundation under grant 1018836. "Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation." This work was supported by the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005. This work was supported by the European Commission under Contract INFSOICT284833 PUFFIN. Calculations were carried out on two GPU clusters:
Version: This is version 2015.09.27 of the bada55.html web page. 