Network Working Group D. Scherkl Internet-Draft Biodata Application Security AG Expires February 2002 August 2001 Updates: RFC 2440 OpenPGP Elliptic Curve Algorithm Formats Status of this Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC2026 [8]. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." You can get this document at http://download.biodata.com/documents/ draft-scherkl-openpgp-ecc-00.txt The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Abstract This document defines which algorithm specific parameters are needed for elliptic curve cipher (ECC) and elliptic curve digital signature algorithm (ECDSA) and how they have to be stored in openPGP packets. Therefore it is an supplement to the openPGP message format [1]. It also defines which checks are needed to validate ECC and ECDSA keys and which "top-level" operations must be performed for encryption/decryption and signing/signature verification. But it gives no advices how to implement these checks and operations, nor the underlying mathematics. To do this, look for example at IEEE P1363 [2]. Scherkl Standards Track [Page 1] Internet-Draft OpenPGP ECC Formats August 2001 Table of Contents Status of this Memo 1 Abstract 1 Table of Contents 2 1. Introduction 3 1.1. Terms 3 2. Elliptic Curve Domain 3 3. Basis Representations 4 3.1. Prime Fields 5 3.2. Polynomial Bases of Char-2 Fields 5 3.3. Gaussian Normal Bases of Char-2 Fields 5 3.4. Odd Extension Fields 6 4. Parameter Format 6 4.1. Zero MPI 6 4.2. Names 6 4.3. Curve Points 6 4.4. Field Descriptor 7 5. Algorithm Specific Fields for ECC and ECDSA Public Keys 8 6. Algorithm Specific Fields for ECC and ECDSA Secret Keys 8 7. ECC 8 7.1. ECC Encryption 8 7.2. ECC Decryption 8 7.3. Algorithm Specific Fields for ECC Encryption 9 8. ECDSA 9 8.1. ECDSA Signature Generation 9 8.2. ECDSA Signature Verification 9 8.3. Algorithm Specific Fields for ECDSA Signatures 9 9. Named Curves 9 9.1. Curves over Char-2 Fields 9 9.2. Curves over Prime Fields 15 9.3. Curves over Odd Extension Fields 18 9.4. Adding Own Named Curves 19 9.5. Revoced Curves 19 10. Secutity Considerations 19 11. References 20 12. Authors Addresses 20 Scherkl Standards Track [Page 2] Internet-Draft OpenPGP ECC Formats August 2001 1. Introduction The openPGP message format [1] reserved IDs for elliptic curve algorithms. This document now defines their storage format. Elliptic curves can be defined over any numberfield (finite or infinite), and the more complicated the field is, the more different "handy" basis representations of it can be defined, for cases of special interest. This draft defines representations for all finite fields plus optimized forms for some special cases that provide fast arithmetic. On elliptic curves a scalar-multiplication can be defined (that is: multiples of points), and it's behavior over finite fields is erratic enough to take it as public key encryption: you can multiply points, but you can't say the multiple of which point you got without checking each point (this is called the "elliptic curve discrete logarithm problem" or EC/DL-problem). The adventage of this multiplication is, that it's much more erratic than RSA exponentiation, which allowes to take shorter keys without loss of security. Another adventage is the high performance if special fields are used. A kind of disadventage is the much more complex mathematics needed, especialy for generating EC domains. Also the high performance is lost if an implementation is not optimized for the field used by a communication partner. 1.1. Terms This document uses the terms "MUST", "SHOULD" and "MAY" as defined in RFC 2119 [9], along with the negated forms of those terms. In the whole document the symbol ^ is used as the exponentiation operator. E.g. 2^7-1 means 127 (one below the seventh power of two). 2. Elliptic Curve Domain There is a set of parameters that may be common not only to one but for many (or even all) keys, which we call the EC domain. It consists of - some finite field F (defined by it's order p^m and it's arithmetic e.g. reduction polynomial or multiplication type - see below), - an elliptic curve E defined by two elements a, b of F, - a point G on E defined by it's coordinates x, y elements of F, - a prime number n with n*G = 0 (the order of G) and - a cofactor h with only small prime factors and h*n is the number of points on E (the order of E). All mentioned conditions MUST be tested, that is: - the groundfield order p is prime and the polynomial is irreducible, - a and b defining a curve over F, Scherkl Standards Track [Page 3] Internet-Draft OpenPGP ECC Formats August 2001 - G lies on the curve and is not 0 (the point at infinity), - n is prime and n*G is 0 (that takes time!) and - n*h is the curve order. Additional there are some security conditions the domain MUST satisfy: - The curve order MUST NOT equal the field order, - The exponent m (extension degree) SHOULD be prime [7] (or m=1), - the point order MUST be greater than 2^160 and it's square MUST be greater than four times the field order (it's bitlen must be at least two bit longer than half the field bitlen), - The MOV condition [3] MUST be true (that is: small powers of the field order MUST NOT be equivalent to 1 modulo the point order), - Further conditions may be added here if more weak curves are discovered. An EC domain that is verified can be given a name. A named curve is simply the EC domain assigned to that name. Implementations SHOULD provide the named curves mentioned in section 9. 3. Basis Representations Any finite field can be represented by three values: a prime p, an exponent m (called the extension degree) and a monic irreducible polynomial f of degree m. But special representations allow us to shrink the storage need: For char-2 fields F(2^m) p=2, so we can ommit it. For prime fields F(p) m=1 and we need no polynomial (using x as reduction polynomial is what we call the ordinary "modulo arithmetic" - using x+1 would lead to a different arithmetic). Also there are more not as obvious special cases: - If p is near some twopower it can be stored as 2^r + c with small integers r and c (c can be negative!!). - For p=2 exists irreducible polynomials with only three (trinomial bases - not always) or five set bits (pentanomial bases). - For some 2^m the all-one polynomial is irreducibe (circular dual basis). - For many p^m exists irreducible binomials f(t) = t^m - w with small w (optimal extension fields). All of these representations not only require less space to store but mainly provide (much) faster arithmetic as the general case. For F(2^m) also one completely different approach is common: Take m as the dimension of a vector space, so that each element can be represented as linear combination of m "independent" basis elements. If each basis element is the square of some other basis element this is called a "normal" basis. If additionaly this basis provides a special multiplication formula of type T, it is called a "gaussian" normal basis. This is supported, because it is very fast in hardware Scherkl Standards Track [Page 4] Internet-Draft OpenPGP ECC Formats August 2001 and therefore many implementations especialy on smartcards use this representation. (These bases rely also on an irreducible polynomial f, but it is not needed for most arithmetic and for T>2 it is complicated to calculate f). In the following text all parameters are shortened by the same letters as mentioned above. 3.1. Prime Fields No parameters except the prime itself are required for prime fields. Standard modulo arithmetic is used. If p is near some twopower p = 2^r + c, the integers r and c are stored instead of p (pseudo mersenne prime field). The sign of c is indicated by different field descriptors (see section 4.4). This is nessessary because the MPI format can't store negative numbers. 3.2. Polynomial Bases of Char-2 Fields For any representation of F(2^m) the parameter m is needed. Each irreducible polynomial has the highest and lowest bit set and the number of set bits is always odd. Using the all-one polynomial is called the "circular dual basis" or "CDB". It requires no further parameters. Using a trinomial is called "trinomial basis" or "TPB". We need to know the positions of the three bits. That are 0, m and some other bit k. Therefore the bit-position k is required as parameter. Using a pentanomial ("pentanomial basis" or "PPB") requires three parameters k1, k2, k3. Using an arbitrary irreducible polynomial ("polynomial basis" or "PB") requires that complete polynomial f as parameter (the highest coefficient t^m which is always 1 may be ommited). Implementations SHOULD avoid arbitrary polynomial bases. 3.3. Gaussian Normal Bases of Char-2 Fields Gaussian bases are completely defined by the extension degree m and the type T of their multiplication. Bases with T=1 or T=2 are called "optimal normal bases", or "type-I ONB" and "type-II ONB". The optimal cases are coded in the field descriptor (see section 4.4), for T>2 this type is needed as additional parameter. This standard does not support arbitrary (non-gaussian) normal bases. Implementations SHOULD avoid non-optimal normal bases. Scherkl Standards Track [Page 5] Internet-Draft OpenPGP ECC Formats August 2001 3.4. Odd Extension Fields Odd extension fields F(p^m) with p>2 and m>1 requires the parameters p, m and f. Their elements are best represented as polynomials of degree < m with coefficients in F(p). However, they are stored as integers i = c0 + c1*p + c2*p^2 + ... + c(m-1)*p^(m-1) (p-adic). The highest coefficient of f is always 1 and may be ommited. That is very storage efficient if the next few coefficients are zero. If p is near some twopower p = 2^r + c, the integers r and c are stored instead of p (type-I extension field). If c is 1 or -1, F is called a type-I "optimal extension field" or "OEF". The sign of c is indicated by different field descriptors (see section 4.4). If F(p^m) has an irreducible binomial f(t) = t^m - w, only w is stored instead of f (type-II extension field). If w = 2, F is called a type-II "optimal extension field" or "OEF". A field can be type-I and type-II optimal at the same time. 4. Parameter Format The algorithm-specific fields all ought to be MPI's. But some of them are data containers instead of numbers. The following sections defines how they must be interpreted: 4.1. Zero MPI Sometimes it is necessary to store the value 0, which may legaly occure (RFC 2440 allowes this only implicit [1]). The value 0 is formed by the string of octets [00 00]. No additional zeros may be inserted. Rational: there is no other way to determine where the MPI should end because no non-zero octet is required to occure. 4.2. Names To store a string in an MPI it is simply prefixed by it's bitlength (without terminating zero-octet). That is: octets*8 minus leading zero bits in the first octet (for ascii names that will be 1 or 2). Rational: There is no need to allow other data types like strings in the algorithm specific fields, only to get an octet length instead of a bitlegth. 4.3. Curve Points Points on an elliptic curve consists of two coordinates. But to any given x-coordinate there are maximal two possible y-coordinates. So it suffices to store only one significant bit v of y to make the decision. This is called the compressed form. Scherkl Standards Track [Page 6] Internet-Draft OpenPGP ECC Formats August 2001 Therefore Points are stored as a single MPI. The contained number is interpreted in the following way: It's highest octet is a bit flag: 00000ucv If c=1, v is the compressed y, else v MUST be 0. If u=1, both x and y are contained uncompressed, else only x. If both coordinates are contained, they MUST have the same number of octets (pad with leading zeros if they don't). y is stored behind x. It's allowed that both c and u are set (in that case v MUST fit y). If neither c nor u is set, the entire value MUST be 0 (the point at infinity). Implementations SHOULD store points compressed. Rational: This format is choosen for compatibility with other actual standards like X9.62 [4], X9.63 [5] and SEC 2 [6]. 4.4. Field Descriptor We distinguish between several kinds of field representations that require different parameters. This is determined by a field descriptor D. Implementations SHOULD store the information always in the best fitting form, because D is also an optimization hint. D may take the following values: 0: Named curve (followed by curve_name) 1: Pseudo mersenne prime field F(p) (followed by r and c. p = 2^r - c, "below some twopower") 2: Pseudo mersenne prime field F(p) (followed by r and c. p = 2^r + c, "above some twopower") 3: Prime field F(p) (followed by p) 4: Type-I&II extension field F(p^m) (followed by r, c, m and w. p = 2^r - c, "below some twopower", f(t) = t^m - w) 5: Type-I&II extension field F(p^m) (followed by r, c, m and w. p = 2^r + c, "above some twopower", f(t) = t^m - w) 6: Type-II extension field F(p^m) (followed by p, m and w. f(t) = t^m - w) 7: Type-I extension field F(p^m) (followed by r, c, m and f. p = 2^r - c, "below some twopower") 8: Type-I extension field F(p^m) (followed by r, c, m and f. p = 2^r + c, "above some twopower") 9: Odd extension field F(p^m) (followed by p, m and f) 10: Circular dual basis of F(2^m) (followed by m) 11: Trinomial basis of F(2^m) (followed by m and k) 12: Pentanomial basis of F(2^m) (followed by m, k1, k2 and k3) 13: Polynomial basis of F(2^m) (followed by m and f) 14: Type-I-ONB of F(2^m) (followed by m) 15: Type-II-ONB of F(2^m) (followed by m) 16: Gaussian normal basis of F(2^m) (followed by m and T) Other values of D are reserved. To comply with the standard D is stored as an MPI, although a single byte would be enough. Scherkl Standards Track [Page 7] Internet-Draft OpenPGP ECC Formats August 2001 5. Algorithm Specific Fields for ECC and ECDSA Public Keys - Field descriptor D (allowed values are 0 to 16) - Name curve_name (for D = 0) - MPI r, -c (for D = 1, 4 or 7) - MPI r, +c (for D = 2, 5 or 8) - MPI p (for D = 3, 6 or 9) - MPI m (for D > 3) - MPI w (for D = 4, 5 or 6) - MPI k (for D = 11) - MPI k1, k2, k3 (for D = 12) - MPI f (for D = 7, 8, 9 or 13) - MPI T (for D = 16) - MPI a, b (for D not 0) - Curve Point G (for D not 0) - MPI n, h (for D not 0) - Curve Point Q, the essential of the public key. Q is the result of multiplying the base point G with the secret number d. 6. Algorithm Specific Fields for ECC and ECDSA Secret Keys - MPI d, the essential of the secret key. d is a random number 1 < d < n, which produces the public curve point Q = d*G. 7. ECC The elliptic curve cipher algorithm (ID 18) requires a hash-algorithm as for signatures to calculate some mask. This mask is calculated the following way: Some data DH plus a four octet counter (big endian) is hashed repeatedly. The counter starts with the value 0 and is incremented in each step. The resulting hash values are concatenated until their length equals that of the message - if it's too long the last octets are cut. This concatenated string is the mask. For symmetric session keys typicaly used today only one or two hashes are needed (see IEEE P1363 [2] for details). The complete cipher requires the following steps: 7.1. ECC Encryption 1. Generate a temporary random keypair (td, tQ) to the same EC domain as the receivers public key parameter Q, 2. calculate a shared secret DH = x-coordinate of the curve point h*td*Q, 3. calculate a Mask M to the session key e out of DH, 4. store (tQ, e xor M) in the encrypted session key packet. 7.2. ECC Decryption 1. Get (tQ', e') from the encrypted session key packet, Scherkl Standards Track [Page 8] Internet-Draft OpenPGP ECC Formats August 2001 2. calculate DH' = x-coordinate of the curve point h*d*tQ', using the receivers secret key parameter d, 3. calculate the Mask M' to e' out of DH', 4. use (e' xor M') as decrypted session key. 7.3. Algorithm Specific Fields for ECC Encryption - One-octet hash-algorithm, - MPI of tQ (a temporary public curve point), - MPI of (e xor M) (the encrypted session key material) 8. ECDSA The elliptic curve digital signature algorithm (ID 19) requires the following steps to be done: 8.1. Sign with ECDSA 1. Choose a random number i < n, 2. calculate t = x-coordinate of i*G mod n, 3. calculate s = (e + d*t)/i mod n, where e is the message hash, 4. store (t, s) in the signature packet. 8.2. ECDSA Signature Verification 1. Get (t', s') from the signature packed and calculate the hash e' of the received message, 2. calculate u1 = e'/s' mod n and u2 = t'/s' mod n, 3. calculate t = x-coordiante of (u1*G + u2*Q) mod n, 4. if t = t', than take the message to be authentic. 8.3. Algorithm Specific Fields for ECDSA Signatures - MPI t (reduced x-coordiante of some curve point) - MPI s (generated from secret and message specific information) 9. Named Curves Known curve names are the following (as defined in X9.62-1998 [4] and SEC 2 [6] - curves over fields which are too small or having small subfields are ommited for enhanced security), the curve point G is always presented in compressed form: 9.1. Curves over Char-2-Fields c2pnb163v1: F(2^163) with pentanomial basis (k = 1, 2, 8), a = 0x07 2546B543 5234A422 E0789675 F432C894 35DE5242, b = 0xC9517D06 D5240D3C FF38C74B 20B6CD4D 6F9DD4D9, G = 0x0307 AF699895 46103D79 329FCC3D 74880F33 BBE803CB, n = 0x04 00000000 00000000 0001E60F C8821CC7 4DAEAFC1, h = 2. Scherkl Standards Track [Page 9] Internet-Draft OpenPGP ECC Formats August 2001 c2pnb163v2: F(2^163) with pentanomial basis (k = 1, 2, 8), a = 0x01 08B39E77 C4B108BE D981ED0E 890E117C 511CF072, b = 0x06 67ACEB38 AF4E488C 407433FF AE4F1C81 1638DF20, G = 0x0300 24266E4E B5106D0A 964D92C4 860E2671 DB9B6CC5, n = 0x03 FFFFFFFF FFFFFFFF FFFDF64D E1151ADB B78F10A7, h = 2. c2pnb163v3: F(2^163) with pentanomial basis (k = 1, 2, 8), a = 0x07 A526C63D 3E25A256 A007699F 5447E32A E456B50E, b = 0x03 F7061798 EB99E238 FD6F1BF9 5B48FEEB 4854252B, G = 0x0202 F9F87B7C 574D0BDE CF8A22E6 524775F9 8CDEBDCB, n = 0x03 FFFFFFFF FFFFFFFF FFFE1AEE 140F110A FF961309, h = 2. sect163k1: F(2^163) with pentanomial basis (k = 3, 6, 7), a = 1, b = 1, G = 0x0302 FE13C053 7BBC11AC AA07D793 DE4E6D5E 5C94EEE8, n = 0x04 00000000 00000000 00020108 A2E0CC0D 99F8A5EF, h = 2. sect163r1: F(2^163) with pentanomial basis (k = 3, 6, 7), a = 07 B6882CAA EFA84F95 54FF8428 BD88E246 D2782AE2, b = 07 13612DCD DCB40AAB 946BDA29 CA91F73A F958AFD9, G = 0303 69979697 AB438977 89566789 567F787A 7876A654, n = 03 FFFFFFFF FFFFFFFF FFFF48AA B689C29C A710279B, h = 2. sect163r2: F(2^163) with pentanomial basis (k = 3, 6, 7), a = 1, b = 0x02 0A601907 B8C953CA 1481EB10 512F7874 4A3205FD, G = 0x0303 F0EBA162 86A2D57E A0991168 D4994637 E8343E36, n = 0x04 00000000 00000000 000292FE 77E70C12 A4234C33, h = 2. c2tnb191v1: F(2^191) with trinomial basis (k = 9), a = 0x2866537B 67675263 6A68F565 54E12640 276B649E F7526267, b = 0x2E45EF57 1F00786F 67B0081B 9495A3D9 5462F5DE 0AA185EC, G = 0x02 36B3DAF8 A23206F9 C4F299D7 B21A9C36 9137F2C8 4AE1AA0D, n = 0x40000000 00000000 00000000 04A20E90 C39067C8 93BBB9A5, h = 2. c2tnb191v2: F(2^191) with trinomial basis (k = 9), a = 0x40102877 4D7777C7 B7666D13 66EA4320 71274F89 FF01E718, b = 0x0620048D 28BCBD03 B6249C99 182B7C8C D19700C3 62C46A01, Scherkl Standards Track [Page 10] Internet-Draft OpenPGP ECC Formats August 2001 G = 0x02 3809B2B7 CC1B28CC 5A87926A AD83FD28 789E81E2 C9E3BF10, n = 0x20000000 00000000 00000000 50508CB8 9F652824 E06B8173, h = 4. c2tnb191v3: F(2^191) with trinomial basis (k = 9), a = 0x6C010747 56099122 22105691 1C77D77E 77A777E7 E7E77FCB, b = 0x71FE1AF9 26CF8479 89EFEF8D B459F663 94D90F32 AD3F15E8, G = 0x03 375D4CE2 4FDE4344 89DE8746 E7178601 5009E66E 38A926DD, n = 0x15555555 55555555 55555555 610C0B19 6812BFB6 288A3EA3, h = 6. c2onb191v4: F(2^191) with type-II optimal normal basis, a = 0x65903E04 E1E49242 53E26A3C 9AC28C75 8BD8184A 3FB680E8, b = 0x54678621 B190CFCE 282ADE21 9D5B3A06 5E3F4B3F FDEBB29B, G = 0x02 5A2C69A3 2E8638E5 1CCEFAAD 05350A97 8457CB5F B6DF994A, n = 0x40000000 00000000 00000000 9CF2D6E3 901DAC4C 32EEC65D, h = 2. c2onb191v5: F(2^191) with type-II optimal normal basis, a = 0x25F8D06C 97C82253 6D469CD5 170CDD7B B9F500BD 6DB110FB, b = 0x75FF570E 35CA94FB 3780C261 9D081C17 AA59FBD5 E591C1C4, G = 0x03 2A16910E 8F6C4B19 9BE24213 857ABC9C 992EDFB2 471F3C68, n = 0x0FFFFFFF FFFFFFFF FFFFFFFF EEB354B7 270B2992 B7818627, h = 8. sect193r1: F(2^193) with trinomial basis (k = 15), a = 0x00 17858FEB 7A989751 69E171F7 7B4087DE 098AC8A9 11DF7B01, b = 0x00 FDFB49BF E6C3A89F ACADAA7A 1E5BBC7C C1C2E5D8 31478814, G = 0x0301 F481BC5F 0FF84A74 AD6CDF6F DEF4BF61 79625372 D8C0C5E1, n = 0x01 00000000 00000000 00000000 C7F34A77 8F443ACC 920EBA49, h = 2. sect193r2: F(2^193) with trinomial basis (k = 15), a = 0x01 63F35A51 37C2CE3E A6ED8667 190B0BC4 3ECD6997 7702709B, b = 0x00 C9BB9E89 27D4D64C 377E2AB2 856A5B16 E3EFB7F6 1D4316AE, G = 0x0300 D9B67D19 2E0367C8 03F39E1A 7E82CA14 A651350A AE617E8F, n = 0x01 00000000 00000000 00000001 5AAB561B 005413CC D4EE99D5, h = 2. sect233k1: F(2^233) with trinomial basis (k = 74), a = 0, b = 1, G = 0x020172 32BA853A 7E731AF1 29F22FF4 149563A4 19C26BF5 0A4C9D6E EFAD6126, n = 0x80 00000000 00000000 00000000 00069D5B B915BCD4 6EFB1AD5 F173ABDF, Scherkl Standards Track [Page 11] Internet-Draft OpenPGP ECC Formats August 2001 h = 4. sect233r1: F(2^233) with trinomial basis (k = 74), a = 1, b = 0x0066 647EDE6C 332C7F8C 0923BB58 213B333B 20E9CE42 81FE115F 7D8F90AD, G = 0x0300FA C9DFCBAC 8313BB21 39F1BB75 5FEF65BC 391F8B36 F8F8EB73 71FD558B, n = 0x0100 00000000 00000000 00000000 0013E974 E72F8A69 22031D26 03CFE0D7, h = 2. sect239k1: F(2^239) with trinomial basis (k = 158), a = 0, b = 1, G = 0x0329A0 B6A887A9 83E97309 88A68727 A8B2D126 C44CC2CC 7B2A6555 193035DC, n = 0x2000 00000000 00000000 00000000 005A79FE C67CB6E9 1F1C1DA8 00E478A5, h = 4. c2tnb239v1: F(2^239) with trinomial basis (k = 36), a = 0x3201 0857077C 5431123A 46B80890 6756F543 423E8D27 87757812 5778AC76, b = 0x7904 08F2EEDA F392B012 EDEFB339 2F30F432 7C0CA3F3 1FC383C4 22AA8C16, G = 0x025792 7098FA93 2E7C0A96 D3FD5B70 6EF7E5F5 C156E16B 7E7C8603 8552E91D, n = 0x2000 00000000 00000000 00000000 000F4D42 FFE1492A 4993F1CA D666E447, h = 4. c2tnb239v2: F(2^239) with trinomial basis (k = 36), a = 0x4230 017757A7 67FAE423 98569B74 6325D453 13AF0766 266479B7 5654E65F, b = 0x5037 EA654196 CFF0CD82 B2C14A2F CF2E3FF8 775285B5 45722F03 EACDB74B, G = 0x0228F9 D04E9000 69C8DC47 A08534FE 76D2B900 B7D7EF31 F5709F20 0C4CA205, n = 0x1555 55555555 55555555 55555555 553C6F28 85259C31 E3FCDF15 4624522D, h = 6. c2tnb239v3: F(2^239) with trinomial basis (k = 36), a = 0x0123 8774666A 67766D66 76F778E6 76B66999 176666E6 87666D87 66C66A9F, b = 0x6A94 1977BA9F 6A435199 ACFC5106 Scherkl Standards Track [Page 12] Internet-Draft OpenPGP ECC Formats August 2001 7ED587F5 19C5ECB5 41B8E441 11DE1D40, G = 0x0370F6 E9D04D28 9C4E8991 3CE3530B FDE90397 7D42B146 D539BF1B DE4E9C92, n = 0x0CCC CCCCCCCC CCCCCCCC CCCCCCCC CCAC4912 D2D9DF90 3EF9888B 8A0E4CFF, h = 10. c2onb239v4: F(2^239) with type-II optimal normal basis, a = 0x182D D45F5D47 0239B898 3FEA47B8 B292641C 57F9BF84 BAECDE8B B3ADCE30, b = 0x147A 9C1D4C2C E9BE5D34 EC02797F 76667EBA D5A3F93F A2A524BF DE91EF28, G = 0x034912 AD657F1D 1C6B32ED B9942C95 E226B06F B012CD40 FDEA0D72 197C8104, n = 0x2000 00000000 00000000 00000000 00474F7E 69F42FE4 30931D0B 455AAE8B, h = 4. c2onb239v5: F(2^239) with type-II optimal normal basis, a = 0x1ECF 1B9D28D8 017505E1 7475D3DF 2982E243 CA5CB5E9 F94A3F36 124A486E, b = 0x3EE2 57250D1A 2E66CEF2 3AA0F25B 12388DE8 A10FF955 4F90AFBA A9A08B6D, G = 0x021932 79FC543E 9F5F7119 189785B9 C60B249B E4820BAF 6C24BDFA 2813F8B8, n = 0x1555 55555555 55555555 55555555 558CF77A 5D0589D2 A9340D96 3B7AD703, h = 6. sect283k1: F(2^283) with pentanomial basis (k = 5, 7, 12), a = 0, b = 1, G = 0x02 0503213F 78CA4488 3F1A3B81 62F188E5 53CD265F 23C1567A 16876913 B0C2AC24 58492836, n = 0x01FFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFE9AE 2ED07577 265DFF7F 94451E06 1E163C61, h = 4. sect283r1: F(2^283) with pentanomial basis (k = 5, 7, 12), a = 1, b = 0x027B680A C8B8596D A5A4AF8A 19A0303F CA97FD76 45309FA2 A581485A F6263E31 3B79A2F5, G = 0x03 05F93925 8DB7DD90 E1934F8C 70B0DFEC 2EED25B8 557EAC9C 80E2E198 F8CDBECD 86B12053, n = 0x03FFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFEF90 399660FC 938A9016 5B042A7C EFADB307, h = 2. Scherkl Standards Track [Page 13] Internet-Draft OpenPGP ECC Formats August 2001 c2tnb359v1: F(2^359) with trinomial basis (k=68), a = 0x56 67676A65 4B20754F 356EA920 17D94656 7C466755 56F19556 A04616B5 67D223A5 E05656FB 549016A9 6656A557, b = 0x24 72E2D019 7C49363F 1FE7F5B6 DB075D52 B6947D13 5D8CA445 805D39BC 34562608 9687742B 6329E706 80231988, G = 0x033C 258EF304 7767E7ED E0F1FDAA 79DAEE38 41366A13 2E163ACE D4ED2401 DF9C6BDC DE98E8E7 07C07A22 39B1B097, n = 0x01 AF286BCA 1AF286BC A1AF286B CA1AF286 BCA1AF28 6BC9FB8F 6B85C556 892C20A7 EB964FE7 719E74F4 90758D3B, h = 0x4C. sect409k1: F(2^409) with trinomial basis (k = 87), a = 0, b = 1, G = 0x03 0060F05F 658F49C1 AD3AB189 0F718421 0EFD0987 E307C84C 27ACCFB8 F9F67CC2 C460189E B5AAAA62 EE222EB1 B35540CF E9023746, n = 0x7FFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFE5F 83B2D4EA 20400EC4 557D5ED3 E3E7CA5B 4B5C83B8 E01E5FCF, h = 4. sect409r1: F(2^409) with trinomial basis (k = 87), a = 1, b = 0x0021A5C2 C8EE9FEB 5C4B9A75 3B7B476B 7FD6422E F1F3DD67 4761FA99 D6AC27C8 A9A197B2 72822F6C D57A55AA 4F50AE31 7B13545F, G = 0x03 015D4860 D088DDB3 496B0C60 64756260 441CDE4A F1771D4D B01FFE5B 34E59703 DC255A86 8A118051 5603AEAB 60794E54 BB7996A7, n = 0x01000000 00000000 00000000 00000000 00000000 00000000 000001E2 AAD6A612 F33307BE 5FA47C3C 9E052F83 8164CD37 D9A21173, h = 2. c2tnb431r1: F(2^431) with trinomial basis (k=120), a = 0x1A827EF00DD6FC0E234CAF046C6A5D8A85395B236CC4AD2CF32A0C ADBDC9DDF620B0EB9906D0957F6C6FEACD615468DF104DE296CD8F, b = 0x10D9B4A3D9047D8B154359ABFB1B7F5485B04CEB868237DDC9DEDA 982A679A5A919B626D4E50A8DD731B107A9962381FB5D807BF2618, G = 0x2120FC05D3C67A99DE161D2F4092622FECA701BE4F50F4758714E8A 87BBF2A658EF8C21E7C5EFE965361F6C2999C0C247B0DBD70CE6B7, n = 0x03403403403403403403403403403403403403403403403403403 40323C313FAB50589703B5EC68D3587FEC60D161CC149C1AD4A91, h = 0x2760. sect571k1: F(2^571) with pentanomial basis (k = 2, 5, 10), a = 0, b = 1, G = 0x02 026EB7A8 59923FBC 82189631 F8103FE4 AC9CA297 0012D5D4 60248048 01841CA4 43709584 93B205E6 47DA304D B4CEB08C BBD1BA39 494776FB 988B4717 4DCA88C7 E2945283 A01C8972, Scherkl Standards Track [Page 14] Internet-Draft OpenPGP ECC Formats August 2001 n = 0x02000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 131850E1 F19A63E4 B391A8DB 917F4138 B630D84B E5D63938 1E91DEB4 5CFE778F 637C1001, h = 4. sect571r1: F(2^571) with pentanomial basis (k = 2, 5, 10), a = 1, b = 0x02F40E7E 2221F295 DE297117 B7F3D62F 5C6A97FF CB8CEFF1 CD6BA8CE 4A9A18AD 84FFABBD 8EFA5933 2BE7AD67 56A66E29 4AFD185A 78FF12AA 520E4DE7 39BACA0C 7FFEFF7F 2955727A, G = 0x03 0303001D 34B85629 6C16C0D4 0D3CD775 0A93D1D2 955FA80A A5F40FC8 DB7B2ABD BDE53950 F4C0D293 CDD711A3 5B67FB14 99AE6003 8614F139 4ABFA3B4 C850D927 E1E7769C 8EEC2D19, n = 0x03FFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF E661CE18 FF559873 08059B18 6823851E C7DD9CA1 161DE93D 5174D66E 8382E9BB 2FE84E47, h = 2. 9.2. Curves over Prime-Fields secp160k1 F(p) with p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFAC73, a = 0, b = 7, G = 02 3B4C382C E37AA192 A4019E76 3036F4F5 DD4D7EBB, n = 01 00000000 00000000 0001B8FA 16DFAB9A CA16B6B3, h = 01. secp160r1 F(p) with p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 7FFFFFFF, a = p-3, b = 1C97BEFC 54BD7A8B 65ACF89F 81D4D4AD C565FA45, G = 02 4A96B568 8EF57328 46646989 68C38BB9 13CBFC82, n = 01 00000000 00000000 0001F4C8 F927AED3 CA752257, h = 01. secp160r2 F(p) with p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFAC73, a = p-3, b = B4E134D3 FB59EB8B AB572749 04664D5A F50388BA, G = 02 52DCB034 293A117E 1F4FF11B 30F7199D 3144CE6D, n = 01 00000000 00000000 0000351E E786A818 F3A1A16B, h = 01. secp192k1: F(p) with p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFEE37, a = 0, Scherkl Standards Track [Page 15] Internet-Draft OpenPGP ECC Formats August 2001 b = 3, G = 0x03 DB4FF10E C057E9AE 26B07D02 80B7F434 1DA5D1B1 EAE06C7D, n = 0xFFFFFFFF FFFFFFFF FFFFFFFE 26F2FC17 0F69466A 74DEFD8D, h = 1. prime192v1 / secp192r1: F(p) with p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF FFFFFFFF, a = p-3, b = 0x64210519 E59C80E7 0FA7E9AB 72243049 FEB8DEEC C146B9B1, G = 0x03 188DA80E B03090F6 7CBF20EB 43A18800 F4FF0AFD 82FF1012, n = 0xFFFFFFFF FFFFFFFF FFFFFFFF 99DEF836 146BC9B1 B4D22831, h = 1. prime192v2: F(p) with p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF FFFFFFFF, a = p-3, b = 0xCC22D6DF B95C6B25 E49C0D63 64A4E598 0C393AA2 1668D953, G = 0x03 EEA2BAE7 E1497842 F2DE7769 CFE9C989 C072AD69 6F48034A, n = 0xFFFFFFFF FFFFFFFF FFFFFFFE 5FB1A724 DC804186 48D8DD31, h = 1. prime192v3: F(p) with p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF FFFFFFFF, a = p-3, b = 0x22123DC2 395A05CA A7423DAE CCC94760 A7D46225 6BD56916, G = 0x02 7D297781 00C65A1D A1783716 588DCE2B 8B4AEE8E 228F1896, n = 0xFFFFFFFF FFFFFFFF FFFFFFFF 7A62D031 C83F4294 F640EC13, h = 1. secp224k1: F(p) with p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFE56D, a = 0, b = 5, G = 0x03 A1455B33 4DF099DF 30FC28A1 69A467E9 E47075A9 0F7E650E B6B7A45C, n = 0x01 00000000 00000000 00000000 0001DCE8 D2EC6184 CAF0A971 769FB1F7, h = 1. secp224r1: F(p) with p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 00000000 00000001, a = p-3, b = 0xB4050A85 0C04B3AB F5413256 5044B0B7 D7BFD8BA 270B3943 2355FFB4, G = 0x02 B70E0CBD 6BB4BF7F 321390B9 Scherkl Standards Track [Page 16] Internet-Draft OpenPGP ECC Formats August 2001 4A03C1D3 56C21122 343280D6 115C1D21, n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFF16A2 E0B8F03E 13DD2945 5C5C2A3D, h = 1. prime239v1: F(p) with p = 0x7FFF FFFFFFFF FFFFFFFF FFFF7FFF FFFFFFFF 80000000 00007FFF FFFFFFFF, a = p-3, b = 0x6B01 6C3BDCF1 8941D0D6 54921475 CA71A9DB 2FB27D1D 37796185 C2942C0A, G = 0x020FFA 963CDCA8 816CCC33 B8642BED F905C3D3 58573D3F 27FBBD3B 3CB9AAAF, n = 0x7FFF FFFFFFFF FFFFFFFF FFFF7FFF FF9E5E9A 9F5D9071 FBD15226 88909D0B, h = 1. prime239v2: F(p) with p = 0x7FFF FFFFFFFF FFFFFFFF FFFF7FFF FFFFFFFF 80000000 00007FFF FFFFFFFF, a = p-3, b = 0x617F AB683257 6CBBFED5 0D99F024 9C3FEE58 B94BA003 8C7AE84C 8C832F2C, G = 0x0238AF 09D98727 705120C9 21BB5E9E 26296A3C DCF2F357 57A0EAFD 87B830E7, n = 0x7FFF FFFFFFFF FFFFFFFF FFFF8000 00CFA7E8 594377D4 14C03821 BC582063, h = 1. prime239v3: F(p) with p = 0x7FFF FFFFFFFF FFFFFFFF FFFF7FFF FFFFFFFF 80000000 00007FFF FFFFFFFF, a = p-3, b = 0x2557 05FA2A30 6654B1F4 CB03D6A7 50A30C25 0102D498 8717D9BA 15AB6D3E, G = 0x036768 AE8E18BB 92CFCF00 5C949AA2 C6D94853 D0E660BB F854B1C9 505FE95A, n = 0x7FFF FFFFFFFF FFFFFFFF FFFF7FFF FF975DEB 41B3A605 7C3C4321 46526551, h = 1; secp256k1 F(p) with p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F, a = 0, b = 7, G = 0x02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798, Scherkl Standards Track [Page 17] Internet-Draft OpenPGP ECC Formats August 2001 n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141, h = 1. prime256v1 / secp256r1: F(p) with p = 0xFFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF, a = p-3, b = 0x5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B, G = 0x03 6B17D1F2 E12C4247F 8BCE6E5 63A440F2 77037D81 2DEB33A0F 4A13945 D898C296, n = 0xFFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551, h = 1. secp384r1: F(p) with p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF 00000000 00000000 FFFFFFFF, a = p-3, b = 0xB3312FA7 E23EE7E4 988E056B E3F82D19 181D9C6E FE814112 0314088F 5013875A C656398D 8A2ED19D 2A85C8ED D3EC2AEF, G = 0x03 AA87CA22 BE8B0537 8EB1C71E F320AD74 6E1D3B62 8BA79B98 59F741E0 82542A38 5502F25D BF55296C 3A545E38 72760AB7, n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF C7634D81 F4372DDF 581A0DB2 48B0A77A ECEC196A CCC52973, h = 1. secp521r1: F(p) with p = 0x01FF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF = 2^521-1, a = p-3, b = 0x0051 953EB961 8E1C9A1F 929A21A0 B68540EE A2DA725B 99B315F3 B8B48991 8EF109E1 56193951 EC7E937B 1652C0BD 3BB1BF07 3573DF88 3D2C34F1 EF451FD4 6B503F00, G = 0x0200C6 858E06B7 0404E9CD 9E3ECB66 2395B442 9C648139 053FB521 F828AF60 6B4D3DBA A14B5E77 EFE75928 FE1DC127 A2FFA8DE 3348B3C1 856A429B F97E7E31 C2E5BD66, n = 0x01FF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFA 51868783 BF2F966B 7FCC0148 F709A5D0 3BB5C9B8 899C47AE BB6FB71E 91386409, h = 1. 9.3. Curves over Odd Extension Fields Curves of this type will be added in the future. Scherkl Standards Track [Page 18] Internet-Draft OpenPGP ECC Formats August 2001 9.4. Adding Own Named Curves To store self created named curves, implementations SHOULD use the same format as for public keys, with the following changes: - the field descriptor D MUST NOT have the value 0, - no public point Q is contained. Own named curves SHOULD be signed like public keys to ensure their validity. Implementations MAY additionaly validate them once they receive them. 9.5. Revoced Curves It may occure that for some named curves already in use weaknesses will be discovered. These curves are mentioned in this section and they SHOULD not be used for key generation any further! (This first draft includes no curves for which weaknesses are known.) 10. Secutity Considerations Using ECC provides shorter keys at the same security level as RSA, but it's still not sure that there will be no fast point-division algorithm in the future. However, this is a problem independent to factorizing numbers, so if either of the two algorithms is broken, the other may still be considered secure. This indeed IS an improvement in security. Some of the number fields used for elliptic curve cryptography have been analyzed less than others. Especialy odd extension fields be a very new research topic, although they are presently considered strong. Another problem of elliptic curves is, that in the past weak curves have been developed (leading to conditions like MOV) and it is not sure that e.g. the here given named curves will be strong enough in the future. Of course, as an update of RFC 2440 [1], most security considerations mentioned there also apply to this document. That is: check the latest litarature for newly found attacks; always keep in mind that a secret key may not be controlled by the proper patry; security depends highly on the randomness of certain parameters. Also it is possible that users generate their own curves without verifying them against all known attacks. Therefore implementations need to verify them on their own, which takes time (and like anything that seems to be obsolete many implementations won't do it - as seen with other algorithms too). Scherkl Standards Track [Page 19] Internet-Draft OpenPGP ECC Formats August 2001 11. References [1] J. Callas, L. Donnerhacke, H. Finney and R. Thayer: "OpenPGP Message Format", Network Working Group Request for Comments 2440, November 1998. [2] IEEE P1363/D13, "Standard Specifications for Public Key Cryptography", Institute of Electrical and Electronics Engineers, November 1999. [3] A. Menezes, T. Okamoto and S. Vanstone: "Reducing elliptic curve logarithms to logarithms in a finite field", IEEE Transactions on Information Theory 39 pp. 1639-1646, 1993. [4] ANSI X9.62-1999, "Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)", American National Standards Institute, 1998. [5] Working Draft ANSI X9.63, "Public Key Cryptography For The Financial Services Industry: Key Agreement and Key Transport using Elliptic Curve Cryptograpy (ECC)", ANSI, January 1999. [6] SEC 2, "Recommended Elliptic Curve Domain Parameters", Standards for Efficient Cryptography Group, 2000. [7] Nigel Smart, Florian Hess, Pierrick Gaudry: "Constructive and Destructive Facets of Weil Descent on Elliptic Curves", Trusted e-Services at HP Laboratories Bristol, January 2000. [8] S. Bradner: "The Internet Standards Process - Revision 3", Network Working Group RFC 2026, October 1996. [9] S. Bradner: "Key words for use in RFCs to Indicate Requirement Levels", Network Working Group RFC 2119, March 1997. 12. Authors Dominikus Scherkl Biodata Application Security AG Christian-Pless-Str. 11-13 63069 Offenbach, Germany EMail: dominikus.scherkl@biodata.com Phone: +49 (0) 69 / 800 706 - 0 Co-Author: Christoph Fausak Biodata Application Security AG EMail: christoph.fausak@biodata.com Scherkl Standards Track [Page 20]