idnits 2.17.1 draft-ietf-dnsext-ecc-key-06.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3667, Section 5.1 on line 17. -- Found old boilerplate from RFC 3978, Section 5.5 on line 606. ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure Acknowledgement -- however, there's a paragraph with a matching beginning. Boilerplate error? ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** The document seems to lack an RFC 3978 Section 5.4 Reference to BCP 78 -- however, there's a paragraph with a matching beginning. Boilerplate error? ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. ** The document seems to lack an RFC 3979 Section 5, para. 1 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 2 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 3 IPR Disclosure Invitation. ** The document uses RFC 3667 boilerplate or RFC 3978-like boilerplate instead of verbatim RFC 3978 boilerplate. After 6 May 2005, submission of drafts without verbatim RFC 3978 boilerplate is not accepted. The following non-3978 patterns matched text found in the document. That text should be removed or replaced: By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. (A line matching the expected section header was found, but with an unexpected indentation: ' 7. Security Considerations' ) ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) (A line matching the expected section header was found, but with an unexpected indentation: ' 8. IANA Considerations' ) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (December 2004) is 7072 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '0' on line 550 == Missing Reference: 'P-1' is mentioned on line 550, but not defined == Missing Reference: 'RFC 2535' is mentioned on line 486, but not defined ** Obsolete undefined reference: RFC 2535 (Obsoleted by RFC 4033, RFC 4034, RFC 4035) == Unused Reference: 'RFC 1034' is defined on line 610, but no explicit reference was found in the text == Unused Reference: 'RFC 1035' is defined on line 613, but no explicit reference was found in the text == Unused Reference: 'Silverman' is defined on line 636, but no explicit reference was found in the text -- Obsolete informational reference (is this intentional?): RFC 1750 (Obsoleted by RFC 4086) -- Obsolete informational reference (is this intentional?): RFC 2671 (Obsoleted by RFC 6891) -- Obsolete informational reference (is this intentional?): RFC 2434 (Obsoleted by RFC 5226) Summary: 13 errors (**), 0 flaws (~~), 7 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT ECC Keys in the DNS 3 Expires: June 2005 December 2004 5 Elliptic Curve KEYs in the DNS 6 -------- ----- ---- -- --- --- 7 9 Richard C. Schroeppel 10 Donald Eastlake 3rd 12 Status of This Document 14 By submitting this Internet-Draft, I certify that any applicable 15 patent or other IPR claims of which I am aware have been disclosed, 16 or will be disclosed, and any of which I become aware will be 17 disclosed, in accordance with RFC 3668. 19 This draft is intended to be become a Proposed Standard RFC. 20 Distribution of this document is unlimited. Comments should be sent 21 to the DNS mailing list . 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF), its areas, and its working groups. Note that 25 other groups may also distribute working documents as Internet- 26 Drafts. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than a "work in progress." 33 The list of current Internet-Drafts can be accessed at 34 http://www.ietf.org/1id-abstracts.html 36 The list of Internet-Draft Shadow Directories can be accessed at 37 http://www.ietf.org/shadow.html 39 Abstract 41 The standard method for storing elliptic curve cryptographic keys and 42 signatures in the Domain Name System is specified. 44 Copyright Notice 46 Copyright (C) The Internet Society. All Rights Reserved. 48 Acknowledgement 50 The assistance of Hilarie K. Orman in the production of this document 51 is greatfully acknowledged. 53 Table of Contents 55 Status of This Document....................................1 56 Abstract...................................................1 57 Copyright Notice...........................................1 59 Acknowledgement............................................2 60 Table of Contents..........................................2 62 1. Introduction............................................3 63 2. Elliptic Curve Data in Resource Records.................3 64 3. The Elliptic Curve Equation.............................9 65 4. How do I Compute Q, G, and Y?..........................10 66 5. Elliptic Curve SIG Resource Records....................11 67 6. Performance Considerations.............................13 68 7. Security Considerations................................13 69 8. IANA Considerations....................................13 70 Copyright and Disclaimer..................................14 72 Informational References..................................15 73 Normative Refrences.......................................15 75 Author's Addresses........................................16 76 Expiration and File Name..................................16 78 1. Introduction 80 The Domain Name System (DNS) is the global hierarchical replicated 81 distributed database system for Internet addressing, mail proxy, and 82 other information. The DNS has been extended to include digital 83 signatures and cryptographic keys as described in [RFC intro, 84 protocol, records]. 86 This document describes how to store elliptic curve cryptographic 87 (ECC) keys and signatures in the DNS so they can be used for a 88 variety of security purposes. Familiarity with ECC cryptography is 89 assumed [Menezes]. 91 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 92 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 93 document are to be interpreted as described in [RFC 2119]. 95 2. Elliptic Curve Data in Resource Records 97 Elliptic curve public keys are stored in the DNS within the RDATA 98 portions of key RRs, such as RRKEY and KEY [RFC records] RRs, with 99 the structure shown below. 101 The research world continues to work on the issue of which is the 102 best elliptic curve system, which finite field to use, and how to 103 best represent elements in the field. So, representations are 104 defined for every type of finite field, and every type of elliptic 105 curve. The reader should be aware that there is a unique finite 106 field with a particular number of elements, but many possible 107 representations of that field and its elements. If two different 108 representations of a field are given, they are interconvertible with 109 a tedious but practical precomputation, followed by a fast 110 computation for each field element to be converted. It is perfectly 111 reasonable for an algorithm to work internally with one field 112 representation, and convert to and from a different external 113 representation. 115 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 116 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 117 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 118 |S M -FMT- A B Z| 119 +-+-+-+-+-+-+-+-+ 120 | LP | 121 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 122 | P (length determined from LP) .../ 123 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 124 | LF | 125 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 126 | F (length determined from LF) .../ 127 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 128 | DEG | 129 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 130 | DEGH | 131 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 132 | DEGI | 133 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 134 | DEGJ | 135 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 136 | TRDV | 137 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 138 |S| LH | 139 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 140 | H (length determined from LH) .../ 141 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 142 |S| LK | 143 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 144 | K (length determined from LK) .../ 145 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 146 | LQ | 147 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 148 | Q (length determined from LQ) .../ 149 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 150 | LA | 151 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 152 | A (length determined from LA) .../ 153 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 154 | ALTA | 155 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 156 | LB | 157 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 158 | B (length determined from LB) .../ 159 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 160 | LC | 161 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 162 | C (length determined from LC) .../ 163 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 164 | LG | 165 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 166 | G (length determined from LG) .../ 167 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 168 | LY | 169 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 170 | Y (length determined from LY) .../ 171 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 173 SMFMTABZ is a flags octet as follows: 175 S = 1 indicates that the remaining 7 bits of the octet selects 176 one of 128 predefined choices of finite field, element 177 representation, elliptic curve, and signature parameters. 178 MFMTABZ are omitted, as are all parameters from LP through G. 179 LY and Y are retained. 181 If S = 0, the remaining parameters are as in the picture and 182 described below. 184 M determines the type of field underlying the elliptic curve. 186 M = 0 if the field is a GF[2^N] field; 188 M = 1 if the field is a (mod P) or GF[P^D] field with P>2. 190 FMT is a three bit field describing the format of the field 191 representation. 193 FMT = 0 for a (mod P) field. 194 > 0 for an extension field, either GF[2^D] or GF[P^D]. 195 The degree D of the extension, and the field polynomial 196 must be specified. The field polynomial is always monic 197 (leading coefficient 1.) 199 FMT = 1 The field polynomial is given explicitly; D is implied. 201 If FMT >=2, the degree D is given explicitly. 203 = 2 The field polynomial is implicit. 204 = 3 The field polynomial is a binomial. P>2. 205 = 4 The field polynomial is a trinomial. 206 = 5 The field polynomial is the quotient of a trinomial by a 207 short polynomial. P=2. 208 = 6 The field polynomial is a pentanomial. P=2. 210 Flags A and B apply to the elliptic curve parameters. 212 A = 1 When P>=5, the curve parameter A is negated. If P=2, then 213 A=1 indicates that the A parameter is special. See the 214 ALTA parameter below, following A. The combination A=1, 215 P=3 is forbidden. 217 B = 1 When P>=5, the curve parameter B is negated. If P=2 or 3, 218 then B=1 indicates an alternate elliptic curve equation is 219 used. When P=2 and B=1, an additional curve parameter C 220 is present. 222 The Z bit SHOULD be set to zero on creation of an RR and MUST be 223 ignored when processing an RR (when S=0). 225 Most of the remaining parameters are present in some formats and 226 absent in others. The presence or absence of a parameter is 227 determined entirely by the flags. When a parameter occurs, it is in 228 the order defined by the picture. 230 Of the remaining parameters, PFHKQABCGY are variable length. When 231 present, each is preceded by a one-octet length field as shown in the 232 diagram above. The length field does not include itself. The length 233 field may have values from 0 through 110. The parameter length in 234 octets is determined by a conditional formula: If LL<=64, the 235 parameter length is LL. If LL>64, the parameter length is 16 times 236 (LL-60). In some cases, a parameter value of 0 is sensible, and MAY 237 be represented by an LL value of 0, with the data field omitted. A 238 length value of 0 represents a parameter value of 0, not an absent 239 parameter. (The data portion occupies 0 space.) There is no 240 requirement that a parameter be represented in the minimum number of 241 octets; high-order 0 octets are allowed at the front end. Parameters 242 are always right adjusted, in a field of length defined by LL. The 243 octet-order is always most-significant first, least-significant last. 244 The parameters H and K may have an optional sign bit stored in the 245 unused high-order bit of their length fields. 247 LP defines the length of the prime P. P must be an odd prime. The 248 parameters LP,P are present if and only if the flag M=1. If M=0, the 249 prime is 2. 251 LF,F define an explicit field polynomial. This parameter pair is 252 present only when FMT = 1. The length of a polynomial coefficient is 253 ceiling(log2 P) bits. Coefficients are in the numerical range 254 [0,P-1]. The coefficients are packed into fixed-width fields, from 255 higher order to lower order. All coefficients must be present, 256 including any 0s and also the leading coefficient (which is required 257 to be 1). The coefficients are right justified into the octet string 258 of length specified by LF, with the low-order "constant" coefficient 259 at the right end. As a concession to storage efficiency, the higher 260 order bits of the leading coefficient may be elided, discarding high- 261 order 0 octets and reducing LF. The degree is calculated by 262 determining the bit position of the left most 1-bit in the F data 263 (counting the right most bit as position 0), and dividing by 264 ceiling(log2 P). The division must be exact, with no remainder. In 265 this format, all of the other degree and field parameters are 266 omitted. The next parameters will be LQ,Q. 268 If FMT>=2, the degree of the field extension is specified explicitly, 269 usually along with other parameters to define the field polynomial. 271 DEG is a two octet field that defines the degree of the field 272 extension. The finite field will have P^DEG elements. DEG is 273 present when FMT>=2. 275 When FMT=2, the field polynomial is specified implicitly. No other 276 parameters are required to define the field; the next parameters 277 present will be the LQ,Q pair. The implicit field poynomial is the 278 lexicographically smallest irreducible (mod P) polynomial of the 279 correct degree. The ordering of polynomials is by highest-degree 280 coefficients first -- the leading coefficient 1 is most important, 281 and the constant term is least important. Coefficients are ordered 282 by sign-magnitude: 0 < 1 < -1 < 2 < -2 < ... The first polynomial of 283 degree D is X^D (which is not irreducible). The next is X^D+1, which 284 is sometimes irreducible, followed by X^D-1, which isn't. Assuming 285 odd P, this series continues to X^D - (P-1)/2, and then goes to X^D + 286 X, X^D + X + 1, X^D + X - 1, etc. 288 When FMT=3, the field polynomial is a binomial, X^DEG + K. P must be 289 odd. The polynomial is determined by the degree and the low order 290 term K. Of all the field parameters, only the LK,K parameters are 291 present. The high-order bit of the LK octet stores on optional sign 292 for K; if the sign bit is present, the field polynomial is X^DEG - K. 294 When FMT=4, the field polynomial is a trinomial, X^DEG + H*X^DEGH + 295 K. When P=2, the H and K parameters are implicitly 1, and are 296 omitted from the representation. Only DEG and DEGH are present; the 297 next parameters are LQ,Q. When P>2, then LH,H and LK,K are 298 specified. Either or both of LH, LK may contain a sign bit for its 299 parameter. 301 When FMT=5, then P=2 (only). The field polynomial is the exact 302 quotient of a trinomial divided by a small polynomial, the trinomial 303 divisor. The small polynomial is right-adjusted in the two octet 304 field TRDV. DEG specifies the degree of the field. The degree of 305 TRDV is calculated from the position of the high-order 1 bit. The 306 trinomial to be divided is X^(DEG+degree(TRDV)) + X^DEGH + 1. If 307 DEGH is 0, the middle term is omitted from the trinomial. The 308 quotient must be exact, with no remainder. 310 When FMT=6, then P=2 (only). The field polynomial is a pentanomial, 311 with the degrees of the middle terms given by the three 2-octet 312 values DEGH, DEGI, DEGJ. The polynomial is X^DEG + X^DEGH + X^DEGI + 313 X^DEGJ + 1. The values must satisfy the inequality DEG > DEGH > DEGI 314 > DEGJ > 0. 316 DEGH, DEGI, DEGJ are two-octet fields that define the degree of 317 a term in a field polynomial. DEGH is present when FMT = 4, 318 5, or 6. DEGI and DEGJ are present only when FMT = 6. 320 TRDV is a two-octet right-adjusted binary polynomial of degree < 321 16. It is present only for FMT=5. 323 LH and H define the H parameter, present only when FMT=4 and P 324 is odd. The high bit of LH is an optional sign bit for H. 326 LK and K define the K parameter, present when FMT = 3 or 4, and 327 P is odd. The high bit of LK is an optional sign bit for K. 329 The remaining parameters are concerned with the elliptic curve and 330 the signature algorithm. 332 LQ defines the length of the prime Q. Q is a prime > 2^159. 334 In all 5 of the parameter pairs LA+A,LB+B,LC+C,LG+G,LY+Y, the data 335 member of the pair is an element from the finite field defined 336 earlier. The length field defines a long octet string. Field 337 elements are represented as (mod P) polynomials of degree < DEG, with 338 DEG or fewer coefficients. The coefficients are stored from left to 339 right, higher degree to lower, with the constant term last. The 340 coefficients are represented as integers in the range [0,P-1]. Each 341 coefficient is allocated an area of ceiling(log2 P) bits. The field 342 representation is right-justified; the "constant term" of the field 343 element ends at the right most bit. The coefficients are fitted 344 adjacently without regard for octet boundaries. (Example: if P=5, 345 three bits are used for each coefficient. If the field is GF[5^75], 346 then 225 bits are required for the coefficients, and as many as 29 347 octets may be needed in the data area. Fewer octets may be used if 348 some high-order coefficients are 0.) If a flag requires a field 349 element to be negated, each non-zero coefficient K is replaced with 350 P-K. To save space, 0 bits may be removed from the left end of the 351 element representation, and the length field reduced appropriately. 352 This would normally only happen with A,B,C, because the designer 353 chose curve parameters with some high-order 0 coefficients or bits. 355 If the finite field is simply (mod P), then the field elements are 356 simply numbers (mod P), in the usual right-justified notation. If 357 the finite field is GF[2^D], the field elements are the usual right- 358 justified polynomial basis representation. 360 LA,A is the first parameter of the elliptic curve equation. 361 When P>=5, the flag A = 1 indicates A should be negated (mod 362 P). When P=2 (indicated by the flag M=0), the flag A = 1 363 indicates that the parameter pair LA,A is replaced by the two 364 octet parameter ALTA. In this case, the parameter A in the 365 curve equation is x^ALTA, where x is the field generator. 366 Parameter A often has the value 0, which may be indicated by 367 LA=0 (with no A data field), and sometimes A is 1, which may 368 be represented with LA=1 and a data field of 1, or by setting 369 the A flag and using an ALTA value of 0. 371 LB,B is the second parameter of the elliptic curve equation. 372 When P>=5, the flag B = 1 indicates B should be negated (mod 373 P). When P=2 or 3, the flag B selects an alternate curve 374 equation. 376 LC,C is the third parameter of the elliptic curve equation, 377 present only when P=2 (indicated by flag M=0) and flag B=1. 379 LG,G defines a point on the curve, of order Q. The W-coordinate 380 of the curve point is given explicitly; the Z-coordinate is 381 implicit. 383 LY,Y is the user's public signing key, another curve point of 384 order Q. The W-coordinate is given explicitly; the Z- 385 coordinate is implicit. The LY,Y parameter pair is always 386 present. 388 3. The Elliptic Curve Equation 390 (The coordinates of an elliptic curve point are named W,Z instead of 391 the more usual X,Y to avoid confusion with the Y parameter of the 392 signing key.) 394 The elliptic curve equation is determined by the flag octet, together 395 with information about the prime P. The primes 2 and 3 are special; 396 all other primes are treated identically. 398 If M=1, the (mod P) or GF[P^D] case, the curve equation is Z^2 = W^3 399 + A*W + B. Z,W,A,B are all numbers (mod P) or elements of GF[P^D]. 400 If A and/or B is negative (i.e., in the range from P/2 to P), and 401 P>=5, space may be saved by putting the sign bit(s) in the A and B 402 bits of the flags octet, and the magnitude(s) in the parameter 403 fields. 405 If M=1 and P=3, the B flag has a different meaning: it specifies an 406 alternate curve equation, Z^2 = W^3 + A*W^2 + B. The middle term of 407 the right-hand-side is different. When P=3, this equation is more 408 commonly used. 410 If M=0, the GF[2^N] case, the curve equation is Z^2 + W*Z = W^3 + 411 A*W^2 + B. Z,W,A,B are all elements of the field GF[2^N]. The A 412 parameter can often be 0 or 1, or be chosen as a single-1-bit value. 413 The flag B is used to select an alternate curve equation, Z^2 + C*Z = 414 W^3 + A*W + B. This is the only time that the C parameter is used. 416 4. How do I Compute Q, G, and Y? 418 The number of points on the curve is the number of solutions to the 419 curve equation, + 1 (for the "point at infinity"). The prime Q must 420 divide the number of points. Usually the curve is chosen first, then 421 the number of points is determined with Schoof's algorithm. This 422 number is factored, and if it has a large prime divisor, that number 423 is taken as Q. 425 G must be a point of order Q on the curve, satisfying the equation 427 Q * G = the point at infinity (on the elliptic curve) 429 G may be chosen by selecting a random [RFC 1750] curve point, and 430 multiplying it by (number-of-points-on-curve/Q). G must not itself 431 be the "point at infinity"; in this astronomically unlikely event, a 432 new random curve point is recalculated. 434 G is specified by giving its W-coordinate. The Z-coordinate is 435 calculated from the curve equation. In general, there will be two 436 possible Z values. The rule is to choose the "positive" value. 438 In the (mod P) case, the two possible Z values sum to P. The smaller 439 value is less than P/2; it is used in subsequent calculations. In 440 GF[P^D] fields, the highest-degree non-zero coefficient of the field 441 element Z is used; it is chosen to be less than P/2. 443 In the GF[2^N] case, the two possible Z values xor to W (or to the 444 parameter C with the alternate curve equation). The numerically 445 smaller Z value (the one which does not contain the highest-order 1 446 bit of W (or C)) is used in subsequent calculations. 448 Y is specified by giving the W-coordinate of the user's public 449 signature key. The Z-coordinate value is determined from the curve 450 equation. As with G, there are two possible Z values; the same rule 451 is followed for choosing which Z to use. 453 During the key generation process, a random [RFC 1750] number X must 454 be generated such that 1 <= X <= Q-1. X is the private key and is 455 used in the final step of public key generation where Y is computed 456 as 458 Y = X * G (as points on the elliptic curve) 460 If the Z-coordinate of the computed point Y is wrong (i.e., Z > P/2 461 in the (mod P) case, or the high-order non-zero coefficient of Z > 462 P/2 in the GF[P^D] case, or Z sharing a high bit with W(C) in the 463 GF[2^N] case), then X must be replaced with Q-X. This will 464 correspond to the correct Z-coordinate. 466 5. Elliptic Curve SIG Resource Records 468 The signature portion of an RR RDATA area when using the EC 469 algorithm, for example in the RRSIG and SIG [RFC records] RRs is 470 shown below. 472 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 473 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 474 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 475 | R, (length determined from LQ) .../ 476 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 477 | S, (length determined from LQ) .../ 478 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 480 R and S are integers (mod Q). Their length is specified by the LQ 481 field of the corresponding KEY RR and can also be calculated from the 482 SIG RR's RDLENGTH. They are right justified, high-order-octet first. 483 The same conditional formula for calculating the length from LQ is 484 used as for all the other length fields above. 486 The data signed is determined as specified in [RFC 2535]. Then the 487 following steps are taken where Q, P, G, and Y are as specified in 488 the public key [Schneier]: 490 hash = SHA-1 ( data ) 492 Generate random [RFC 1750] K such that 0 < K < Q. (Never sign two 493 different messages with the same K. K should be chosen from a 494 very large space: If an opponent learns a K value for a single 495 signature, the user's signing key is compromised, and a forger 496 can sign arbitrary messages. There is no harm in signing the 497 same message multiple times with the same key or different 498 keys.) 500 R = (the W-coordinate of ( K*G on the elliptic curve )) interpreted 501 as an integer, and reduced (mod Q). (R must not be 0. In 502 this astronomically unlikely event, generate a new random K 503 and recalculate R.) 505 S = ( K^(-1) * (hash + X*R) ) mod Q. 507 S must not be 0. In this astronomically unlikely event, generate a 508 new random K and recalculate R and S. 510 If S > Q/2, set S = Q - S. 512 The pair (R,S) is the signature. 514 Another party verifies the signature as follows: 516 Check that 0 < R < Q and 0 < S < Q/2. If not, it can not be a 517 valid EC sigature. 519 hash = SHA-1 ( data ) 521 Sinv = S^(-1) mod Q. 523 U1 = (hash * Sinv) mod Q. 525 U2 = (R * Sinv) mod Q. 527 (U1 * G + U2 * Y) is computed on the elliptic curve. 529 V = (the W-coordinate of this point) interpreted as an integer 530 and reduced (mod Q). 532 The signature is valid if V = R. 534 The reason for requiring S < Q/2 is that, otherwise, both (R,S) and 535 (R,Q-S) would be valid signatures for the same data. Note that a 536 signature that is valid for hash(data) is also valid for 537 hash(data)+Q or hash(data)-Q, if these happen to fall in the range 538 [0,2^160-1]. It's believed to be computationally infeasible to 539 find data that hashes to an assigned value, so this is only a 540 cosmetic blemish. The blemish can be eliminated by using Q > 541 2^160, at the cost of having slightly longer signatures, 42 octets 542 instead of 40. 544 We must specify how a field-element E ("the W-coordinate") is to be 545 interpreted as an integer. The field-element E is regarded as a 546 radix-P integer, with the digits being the coefficients in the 547 polynomial basis representation of E. The digits are in the ragne 548 [0,P-1]. In the two most common cases, this reduces to "the 549 obvious thing". In the (mod P) case, E is simply a residue mod P, 550 and is taken as an integer in the range [0,P-1]. In the GF[2^D] 551 case, E is in the D-bit polynomial basis representation, and is 552 simply taken as an integer in the range [0,(2^D)-1]. For other 553 fields GF[P^D], it's necessary to do some radix conversion 554 arithmetic. 556 6. Performance Considerations 558 Elliptic curve signatures use smaller moduli or field sizes than 559 RSA and DSA. Creation of a curve is slow, but not done very often. 560 Key generation is faster than RSA or DSA. 562 DNS implementations have been optimized for small transfers, 563 typically less than 512 octets including DNS overhead. Larger 564 transfers will perform correctly and and extensions have been 565 standardized to make larger transfers more efficient [RFC 2671]. 566 However, it is still advisable at this time to make reasonable 567 efforts to minimize the size of RR sets stored within the DNS 568 consistent with adequate security. 570 7. Security Considerations 572 Keys retrieved from the DNS should not be trusted unless (1) they 573 have been securely obtained from a secure resolver or independently 574 verified by the user and (2) this secure resolver and secure 575 obtainment or independent verification conform to security policies 576 acceptable to the user. As with all cryptographic algorithms, 577 evaluating the necessary strength of the key is essential and 578 dependent on local policy. 580 Some specific key generation considerations are given in the body 581 of this document. 583 8. IANA Considerations 585 The key and signature data structures defined herein correspond to 586 the value 4 in the Algorithm number field of the IANA registry 588 Assignment of meaning to the remaining ECC data flag bits or to 589 values of ECC fields outside the ranges for which meaning in 590 defined in this document requires an IETF consensus as defined in 591 [RFC 2434]. 593 Copyright and Disclaimer 595 Copyright (C) The Internet Society 2004. This document is subject 596 to the rights, licenses and restrictions contained in BCP 78 and 597 except as set forth therein, the authors retain all their rights. 599 This document and the information contained herein are provided on 600 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 601 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND 602 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, 603 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT 604 THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR 605 ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A 606 PARTICULAR PURPOSE. 608 Informational References 610 [RFC 1034] - P. Mockapetris, "Domain names - concepts and 611 facilities", 11/01/1987. 613 [RFC 1035] - P. Mockapetris, "Domain names - implementation and 614 specification", 11/01/1987. 616 [RFC 1750] - D. Eastlake, S. Crocker, J. Schiller, "Randomness 617 Recommendations for Security", 12/29/1994. 619 [RFC intro] - "DNS Security Introduction and Requirements", R. 620 Arends, M. Larson, R. Austein, D. Massey, S. Rose, work in 621 progress, draft-ietf-dnsext-dnssec-intro-*.txt. 623 [RFC protocol] - "Protocol Modifications for the DNS Security 624 Extensions", R. Arends, M. Larson, R. Austein, D. Massey, S. Rose, 625 work in progress, draft-ietf-dnsext-dnssec-protocol-*.txt. 627 [RFC 2671] - P. Vixie, "Extension Mechanisms for DNS (EDNS0)", 628 August 1999. 630 [Schneier] - Bruce Schneier, "Applied Cryptography: Protocols, 631 Algorithms, and Source Code in C", 1996, John Wiley and Sons 633 [Menezes] - Alfred Menezes, "Elliptic Curve Public Key 634 Cryptosystems", 1993 Kluwer. 636 [Silverman] - Joseph Silverman, "The Arithmetic of Elliptic 637 Curves", 1986, Springer Graduate Texts in mathematics #106. 639 Normative Refrences 641 [RFC 2119] - S. Bradner, "Key words for use in RFCs to Indicate 642 Requirement Levels", March 1997. 644 [RFC 2434] - T. Narten, H. Alvestrand, "Guidelines for Writing an 645 IANA Considerations Section in RFCs", October 1998. 647 [RFC records] - "Resource Records for the DNS Security Extensions", 648 R. Arends, R. Austein, M. Larson, D. Massey, S. Rose, work in 649 progress, draft-ietf-dnsext-dnssec-records- *.txt. 651 Author's Addresses 653 Rich Schroeppel 654 500 S. Maple Drive 655 Woodland Hills, UT 84653 USA 657 Telephone: +1-505-844-9079(w) 658 +1-801-423-7998(h) 659 Email: rschroe@sandia.gov 661 Donald E. Eastlake 3rd 662 Motorola Laboratories 663 155 Beaver Street 664 Milford, MA 01757 USA 666 Telephone: +1 508-786-7554 (w) 667 +1 508-634-2066 (h) 668 EMail: Donald.Eastlake@motorola.com 670 Expiration and File Name 672 This draft expires in June 2004. 674 Its file name is draft-ietf-dnsext-ecc-key-06.txt.