Network Working Group D. Scherkl Internet-Draft Biodata Application Security AG Expires November 2001 May 2001 Updates: RFC 2440 OpenPGP Elliptic Curve Algorithm Formats Status of this Memo This document is an Internet-Draft. 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." To view the entire list of current Internet-Drafts, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). Abstract This document defines which algorithm specific parameters are needed for elliptic curve encryption (ECC) and elliptic curve digital signature algorithm (ECDSA) and how they have to be stored in openPGP keyrings. 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 at IEEE P1363 [1] for example. Scherkl Informational [Page 1] Internet-Draft OpenPGP ECC Formats May 2001 Table of Contents Status of this Memo 1 Abstract 1 Table of Contents 2 1. Introduction 2 2. Elliptic Curve Domain 3 3. Basis Representations 3 3.1. Prime Field 4 3.2. Polynomial Bases 4 3.3. Gaussian Normal Bases 5 3.4. Optimal Extension Fields 5 4. Parameter Format 5 4.1. Zero MPI 5 4.2. Curve Points 5 4.3. Field Descriptor 6 5. Algorithm Specific Fields for ECC and ECDSA Public Keys 6 6. Algorithm Specific Fields for ECC and ECDSA Secret Keys 7 7. Named Curves 7 7.1. Adding Own Named Curves 12 8. Secutity Cosiderations 13 9. References 13 1. Introduction 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 and some special cases that provides 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. Scherkl Informational [Page 2] Internet-Draft OpenPGP ECC Formats May 2001 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 koordinates 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, - G lies on the curve and is not 0, - 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 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 [2] MUST be true (that is: small powers of the field order MUST NOT be equivalent to 1 modulo the point order), - the exponent m SHOULD be prime or at least have no very small divisors (a very new condition that may be not hold for some existing keys and is still not prooven to be a weakness). An EC domain that is verified can be given a name. A named curve is nothing else than the EC domain assigned to that name. Each implementation SHOULD provide the named curves mentioned in section 7. 3. Basis Representations Any finite field can be represented by three values: a prime p, an exponent m and a monic irreducible polynomial f of degree m. But special representations allow us to shrink the storage need: For F(2^m) p=2, so we can ommit it. For F(p) m=1 and we need no polynomial (using x+1 as reduction polynomial is what we call the "standard modulo 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 existing irreducible polynomials with only three (trinomial bases - not always) or five set bits (pentanomial bases). Scherkl Informational [Page 3] Internet-Draft OpenPGP ECC Formats May 2001 - 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 than the general case. For F(2^m) although 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 and therefore many implementations especialy on smartcards use this representation. (This rely also on an irreducible polynomial, but it is not needed for most arithmetic and for T>2 it is complicated to calculate it). In the following text all parameters are shortened by the same letters as metioned 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). 3.2. Polynomial Bases 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, m+1 bit long polynomial f as parameter. Implementations SHOULD avoid arbitrary polynomial bases. Scherkl Informational [Page 4] Internet-Draft OpenPGP ECC Formats May 2001 3.3. Gaussian Normal Bases Gaussian bases are completely defined by 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". We need this type as additional parameter, but only for T>2. This standard does not support arbitrary (non-gaussian) normal bases. Implementations SHOULD avoid non-optimal normal bases. 3.4. Optimal 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). 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". 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 Field elements are stored in the MPI format defined in RFC2440 without changes. But some parameters requires new semantics: 4.1. Zero MPI Sometimes it is nessessary to store the value 0, which may legaly occure (RFC 2440 allowes this only implicit). 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. Curve Points Points on an elliptic curve consists of two koordinates. But to any given x-koordinate there are maximal two possible y-koordinates. So it suffices to store only one bit y0 of y to make the decision. This is called the point compression. Either (or both) of the coordinates may be zero - therefore the zero-MPI is nessessary. So curve points are stored as a Byte flag and depending on it's value no, one or two following MPI's: Scherkl Informational [Page 5] Internet-Draft OpenPGP ECC Formats May 2001 flag = 0: the point at infinity (no following MPI's) flag = 2: compressed point with y0 = 0 (followed by the MPI x) flag = 3: compressed point with y0 = 1 (followed by the MPI x) flag = 4: uncompressed point (followed by the MPI's x and y) flag = 6: hybrid point with y0 = 0 (followed by the MPI's x and y) flag = 7: hybrid point with y0 = 1 (followed by the MPI's x and y) Other values of flag are prohibited. To check a point to lie on the curve E, for compressed points it suffices that the decompression succeeds (otherwise the point is not on E). For the hybrid form y0 MUST fit y and an implementation MUST check this. Implementations SHOULD store points compressed. 4.3. Field Descriptor We distinguish between several kinds of field representations that require different parameters. This is determined by a single Byte D, the field descriptor. Implementations SHOULD store the informations always in the best fitting form, because D is also an optimization hint. D may take the following values: 0: Named curve (followed by string curve_name) 1: Type-I-ONB of F(2^m) (followed by integer m) 2: Type-II-ONB of F(2^m) (followed by integer m) 3: Gaussian normal base of F(2^m) (followed by integers m and T) 4: Circular dual base of F(2^m) (followed by integer m) 5: Trinomial base of F(2^m) (followed by integers m and k) 6: Pentanomial base of F(2^m) (followed by integers m, k1, k2, k3) 7: Polynomial base of F(2^m) (followed by integer m and MPI f) 8: Prime field F(p) (followed by MPI p) 9: Pseudo mersenne prime field F(p) (followed by integers c, r. p = 2^r + c) 10: Type-I extension field F(p^m) (followed by integers m, c, r and MPI f. p = 2^r + c) 11: Type-II extension field F(p^m) (followed by integers m, w and MPI p. f(t) = t^m - w) 12: Type-I&II extension field F(p^m) (followed by integers m, c, r and w. p = 2^r + c, f(t) = t^m - w) 13: Extension field F(p^m) (followed by integer m and MPI's p, f) Other values of D are reserved. 5. Algorithm Specific Fields for ECC and ECDSA Public Keys - Byte D, the field descriptor (allowed values are 0 to 13) - String curve_name (for D = 0) - Integer m (for D not 0, 8 or 9) - Integer T (for D = 3) - Integer k (for D = 5) - Integers k1, k2, k3 (for D = 6) - Integers c, r (for D = 9, 10 or 12), c may be negative! - Integer w (for D = 11 or 12) Scherkl Informational [Page 6] Internet-Draft OpenPGP ECC Formats May 2001 - MPI p (for D = 8, 11 or 13) - MPI f (for D = 7, 10 or 13) - MPI's a, b, n (for D not 0) - Integer h (for D not 0) - Point G (for D not 0) - 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 point Q = d*G. 7. Named Curves Known curve names are the following (as defined in X9.63-1998 [3]). Implementations MOST NOT use the curves defined here with even exponent m for key generation! c2pnb163v1: F(2^163) with pentanomial basis (k1=1, k2=2, k3=8), a = 0x72546B5435234A422E0789675F432C89435DE5242, b = 0xC9517D06D5240D3CFF38C74B20B6CD4D6F9DD4D9, G = 0x307AF69989546103D79329FCC3D74880F33BBE803CB, n = 0x400000000000000000001E60FC8821CC74DAEAFC1, h = 2. c2pnb163v2: F(2^163) with pentanomial basis (k1=1, k2=2, k3=8), a = 0x108B39E77C4B108BED981ED0E890E117C511CF072, b = 0x667ACEB38AF4E488C407433FFAE4F1C811638DF20, G = 0x30024266E4EB5106D0A964D92C4860E2671DB9B6CC5, n = 0x3FFFFFFFFFFFFFFFFFFFDF64DE1151ADBB78F10A7, h = 2. c2pnb163v3: F(2^163) with pentanomial basis (k1=1, k2=2, k3=8), a = 0x7A526C63D3E25A256A007699F5447E32AE456B50E, b = 0x3F7061798EB99E238FD6F1BF95B48FEEB4854252B, G = 0x202F9F87B7C574D0BDECF8A22E6524775F98CDEBDCB, n = 0x3FFFFFFFFFFFFFFFFFFFE1AEE140F110AFF961309, h = 2. c2pnb176w1: F(2^176) with pentanomial basis (k1=1, k2=2, k3=43), a = 0xE4E6DB2995065C407D9D39B8D0967B96704BA8E9C90B, b = 0x5DDA470ABE6414DE8EC133AE28E9BBD7FCEC0AE0FFF2, G = 0x38D16C2866798B600F9F08BB4A8E860F3298CE04A5798, n = 0x10092537397ECA4F6145799D62B0A19CE06FE26AD, h = 0xFF6E. Scherkl Informational [Page 7] Internet-Draft OpenPGP ECC Formats May 2001 c2tnb191v1: F(2^191) with trinomial basis (k=9), a = 0x2866537B676752636A68F56554E12640276B649EF7526267, b = 0x2E45EF571F00786F67B0081B9495A3D95462F5DE0AA185EC, G = 0x236B3DAF8A23206F9C4F299D7B21A9C369137F2C84AE1AA0D, n = 0x40000000000000000000000004A20E90C39067C893BBB9A5, h = 2. c2tnb191v2: F(2^191) with trinomial basis (k=9), a = 0x401028774D7777C7B7666D1366EA432071274F89FF01E718, b = 0x620048D28BCBD03B6249C99182B7C8CD19700C362C46A01, G = 0x23809B2B7CC1B28CC5A87926AAD83FD28789E81E2C9E3BF10, n = 0x20000000000000000000000050508CB89F652824E06B8173, h = 4. c2tnb191v3: F(2^191) with trinomial basis (k=9), a = 0x6C01074756099122221056911C77D77E77A777E7E7E77FCB, b = 0x71FE1AF926CF847989EFEF8DB459F66394D90F32AD3F15E8, G = 0x3375D4CE24FDE434489DE8746E71786015009E66E38A926DD, n = 0x155555555555555555555555610C0B196812BFB6288A3EA3, h = 6. c2onb191v4: F(2^191) with type-II optimal normal basis, a = 0x65903E04E1E4924253E26A3C9AC28C758BD8184A3FB680E8, b = 0x54678621B190CFCE282ADE219D5B3A065E3F4B3FFDEBB29B, G = 0x25A2C69A32E8638E51CCEFAAD05350A978457CB5FB6DF994A, n = 0x4000000000000000000000009CF2D6E3901DAC4C32EEC65D, h = 2. c2onb191v5: F(2^191) with type-II optimal normal basis, a = 0x25F8D06C97C822536D469CD5170CDD7BB9F500BD6DB110FB, b = 0x75FF570E35CA94FB3780C2619D081C17AA59FBD5E591C1C4, G = 0x32A16910E8F6C4B199BE24213857ABC9C992EDFB2471F3C68, n = 0xFFFFFFFFFFFFFFFFFFFFFFFEEB354B7270B2992B7818627, h = 8. c2pnb208w1: F(2^208) with pentanomial basis (k1=1, k2=2, k3=83), a = 0, b = 0xC8619ED45A62E6212E1160349E2BFA844439FAFC2A3FD1638F9E, G = 0x289FDFBE4ABE193DF9559ECF07AC0CE78554E2784EB8C1ED1A57A, n = 0x101BAF95C9723C57B6C21DA2EFF2D5ED588BDD5717E212F9D, h = 0xFE48. c2tnb239v1: F(2^239) with trinomial basis (k=36), a = 0x32010857077C5431123A46B8089067 56F543423E8D27877578125778AC76, Scherkl Informational [Page 8] Internet-Draft OpenPGP ECC Formats May 2001 b = 0x790408F2EEDAF392B012EDEFB3392F 30F4327C0CA3F31FC383C422AA8C16, G = 0x257927098FA932E7C0A96D3FD5B706 EF7E5F5C156E16B7E7C86038552E91D, n = 0x200000000000000000000000000000 0F4D42FFE1492A4993F1CAD666E447, h = 4. c2tnb239v2: F(2^239) with trinomial basis (k=36), a = 0x4230017757A767FAE42398569B7463 25D45313AF0766266479B75654E65F, b = 0x5037EA654196CFF0CD82B2C14A2FCF 2E3FF8775285B545722F03EACDB74B, G = 0x228F9D04E900069C8DC47A08534FE7 6D2B900B7D7EF31F5709F200C4CA205, n = 0x155555555555555555555555555555 3C6F2885259C31E3FCDF154624522D, h = 6. c2tnb239v3: F(2^239) with trinomial basis (k=36), a = 0x1238774666A67766D6676F778E676B 66999176666E687666D8766C66A9F, b = 0x6A941977BA9F6A435199ACFC51067E D587F519C5ECB541B8E44111DE1D40, G = 0x370F6E9D04D289C4E89913CE3530BF DE903977D42B146D539BF1BDE4E9C92, n = 0xCCCCCCCCCCCCCCCCCCCCCCCCCCCCCA C4912D2D9DF903EF9888B8A0E4CFF, h = 10. c2onb239v4: F(2^239) with type-II optimal normal basis, a = 0x182DD45F5D470239B8983FEA47B8B2 92641C57F9BF84BAECDE8BB3ADCE30, b = 0x147A9C1D4C2CE9BE5D34EC02797F76 667EBAD5A3F93FA2A524BFDE91EF28, G = 0x34912AD657F1D1C6B32EDB9942C95E 226B06FB012CD40FDEA0D72197C8104, n = 0x200000000000000000000000000000 474F7E69F42FE430931D0B455AAE8B, h = 4. c2onb239v5: F(2^239) with type-II optimal normal basis, a = 0x1ECF1B9D28D8017505E17475D3DF29 82E243CA5CB5E9F94A3F36124A486E, b = 0x3EE257250D1A2E66CEF23AA0F25B12 388DE8A10FF9554F90AFBAA9A08B6D, G = 0x2193279FC543E9F5F7119189785B9C 60B249BE4820BAF6C24BDFA2813F8B8, Scherkl Informational [Page 9] Internet-Draft OpenPGP ECC Formats May 2001 n = 0x155555555555555555555555555555 8CF77A5D0589D2A9340D963B7AD703, h = 6. c2pnb272w1: F(2^272) with pentanomial basis (k1=1, k2=3, k3=56), a = 0x91A091F03B5FBA4AB2CCF49C4EDD220FB0 28712D42BE752B2C40094DBACDB586FB20, b = 0x7167EFC92BB2E3CE7C8AAAFF34E12A9C55 7003D7C73A6FAF003F99F6CC8482E540F7, G = 0x26108BABB2CEEBCF787058A056CBE0CFE6 22D7723A289E08A07AE13EF0D10D171DD8D, n = 0x100FAF51354E0E39E4892DF6E319C72C81 61603FA45AA7B998A167B8F1E629521, h = 0xFF06. c2pnb304w1: F(2^304) with pentanomial basis (k1=1, k2=2, k3=11), a = 0xFD0D693149A118F651E6DCE6802085377E5F88 2D1B510B44160074C1288078365A0396C8E681, b = 0xBDDB97E555A50A908E43B01C798EA5DAA6788F 1EA2794EFCF57166B8C14039601E55827340BE, G = 0x2197B07845E9BE2D96ADB0F5F3C7F2CFFBD7A3 EB8B6FEC35C7FD67F26DDF6285A644F740A2614, n = 0x101D556572AABAC800101D556572AABAC80010 22D5C91DD173F8FB561DA6899164443051D, h = 0xFE2E. c2tnb359v1: F(2^359) with trinomial basis (k=68), a = 0x5667676A654B20754F356EA92017D946567C46675556F 19556A04616B567D223A5E05656FB549016A96656A557, b = 0x2472E2D0197C49363F1FE7F5B6DB075D52B6947D135D8 CA445805D39BC345626089687742B6329E70680231988, G = 0x33C258EF3047767E7EDE0F1FDAA79DAEE3841366A132E 163ACED4ED2401DF9C6BDCDE98E8E707C07A2239B1B097, n = 0x1AF286BCA1AF286BCA1AF286BCA1AF286BCA1AF286BC9 FB8F6B85C556892C20A7EB964FE7719E74F490758D3B, h = 0x4C. c2pnb368w1: F(2^368) with pentanomial basis (k1=1, k2=2, k3=85), a = 0xE0D2EE25095206F5E2A4F9ED229F1F256E79A0E2B45597 0D8D0D865BD94778C576D62F0AB7519CCD2A1A906AE30D, b = 0xFC1217D4320A90452C760A58EDCD30C8DD069B3C344538 37A34ED50CB54917E1C2112D84D164F444F8F74786046A, G = 0x21085E2755381DCCCE3C1557AFA10C2F0C0C2825646C5B 34A394CBCFA8BC16B22E7E789E927BE216F02E1FB136A5F, n = 0x10090512DA9AF72B08349D98A5DD4C7B0532ECA51CE03E 2D10F3B7AC579BD87E909AE40A6F131E9CFCE5BD967, h = 0xFF70. Scherkl Informational [Page 10] Internet-Draft OpenPGP ECC Formats May 2001 c2tnb431r1: F(2^431) with trinomial basis (k=120), a = 0x1A827EF00DD6FC0E234CAF046C6A5D8A85395B236CC4AD2CF32A0C ADBDC9DDF620B0EB9906D0957F6C6FEACD615468DF104DE296CD8F, b = 0x10D9B4A3D9047D8B154359ABFB1B7F5485B04CEB868237DDC9DEDA 982A679A5A919B626D4E50A8DD731B107A9962381FB5D807BF2618, G = 0x2120FC05D3C67A99DE161D2F4092622FECA701BE4F50F4758714E8A 87BBF2A658EF8C21E7C5EFE965361F6C2999C0C247B0DBD70CE6B7, n = 0x340340340340340340340340340340340340340340340340340340 323C313FAB50589703B5EC68D3587FEC60D161CC149C1AD4A91, h = 0x2760. prime192v1: F(p) with p = 6277101735386680763835789423207666416083908700390324961279, a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC, b = 0x64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1, G = 0x3188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012, n = 0xFFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831, h = 1. prime192v2: F(p) with p = 6277101735386680763835789423207666416083908700390324961279, a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC, b = 0xCC22D6DFB95C6B25E49C0D6364A4E5980C393AA21668D953, G = 0x3EEA2BAE7E1497842F2DE7769CFE9C989C072AD696F48034A, n = 0xFFFFFFFFFFFFFFFFFFFFFFFE5FB1A724DC80418648D8DD31, h = 1; prime192v3: F(p) with p = 6277101735386680763835789423207666416083908700390324961279, a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC, b = 0x22123DC2395A05CAA7423DAECCC94760A7D462256BD56916, G = 0x27D29778100C65A1DA1783716588DCE2B8B4AEE8E228F1896, n = 0xFFFFFFFFFFFFFFFFFFFFFFFF7A62D031C83F4294F640EC13, h = 1; prime239v1: F(p) with p = 883423532389192164791648750360308885 314476597252960362792450860609699839, a = 0x7FFFFFFFFFFFFFFFFFFFFFFF7FFFFF FFFFFF8000000000007FFFFFFFFFFC, b = 0x6B016C3BDCF18941D0D654921475CA 71A9DB2FB27D1D37796185C2942C0A, G = 0x20FFA963CDCA8816CCC33B8642BEDF 905C3D358573D3F27FBBD3B3CB9AAAF, n = 0x7FFFFFFFFFFFFFFFFFFFFFFF7FFFFF 9E5E9A9F5D9071FBD1522688909D0B, h = 1; Scherkl Informational [Page 11] Internet-Draft OpenPGP ECC Formats May 2001 prime239v2: F(p) with p = 883423532389192164791648750360308885 314476597252960362792450860609699839, a = 0x7FFFFFFFFFFFFFFFFFFFFFFF7FFFFF FFFFFF8000000000007FFFFFFFFFFC, b = 0x617FAB6832576CBBFED50D99F0249C 3FEE58B94BA0038C7AE84C8C832F2C, G = 0x238AF09D98727705120C921BB5E9E2 6296A3CDCF2F35757A0EAFD87B830E7, n = 0x7FFFFFFFFFFFFFFFFFFFFFFF800000 CFA7E8594377D414C03821BC582063, h = 1; prime239v3: F(p) with p = 883423532389192164791648750360308885 314476597252960362792450860609699839, a = 0x7FFFFFFFFFFFFFFFFFFFFFFF7FFFFF FFFFFF8000000000007FFFFFFFFFFC, b = 0x255705FA2A306654B1F4CB03D6A750 A30C250102D4988717D9BA15AB6D3E, G = 0x36768AE8E18BB92CFCF005C949AA2C 6D94853D0E660BBF854B1C9505FE95A, n = 0x7FFFFFFFFFFFFFFFFFFFFFFF7FFFFF 975DEB41B3A6057C3C432146526551, h = 1; prime256v1: F(p) with p = 115792089210356248762697446949407573530 086143415290314195533631308867097853951, a = 0xFFFFFFFF000000010000000000000000 00000000FFFFFFFFFFFFFFFFFFFFFFFC, b = 0x5AC635D8AA3A93E7B3EBBD55769886BC 651D06B0CC53B0F63BCE3C3E27D2604B, G = 0x36B17D1F2E12C4247F8BCE6E563A440F 277037D812DEB33A0F4A13945D898C296, n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFF BCE6FAADA7179E84F3B9CAC2FC632551, h = 1. 7.1. 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. Scherkl Informational [Page 12] Internet-Draft OpenPGP ECC Formats May 2001 8. Secutity Cosiderations Using ECDSA seems to be more secure than using El Gamal DSA. 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. How ever, this is a problem independent to factorizing numbers, so if either of the two algorithms is broken, the other may still considered secure. This indeed IS an improvement in security. Another problem of elliptic curves is that in the past weak curves have been developed (leeding to conditions like MOV) and it is not sure that e.g. the here given named curves will be strong enough in the future (e.g. even exponents m are now to be excluded). But that may only lead to additional checks that can be added to implementations without changing this standard. An implementation MUST warn if a curve is used that is deemed weak for future conditions. It MUST NOT use such a curve for key generation. 9. References [1] IEEE P1363/D13 Standard Specifications for Public Key Cryptography, November 1999. [2] A. Menezes, T. Okamoto and S. Vanstone: Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory, 39 (1993), 1639-1646. [3] Working Draft ANSI X9.63 - Public Key Cryptography For The Financial Services Industry, January 1999. Author Dominikus Scherkl Biodata Application Security AG dscherkl(_at_)biodata(_dot_)com Scherkl Informational [Page 13]