idnits 2.17.1 draft-ietf-dnsext-ecc-key-09.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 3978, Section 5.1 on line 17. -- Found old boilerplate from RFC 3978, Section 5.5 on line 604. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 613. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 620. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 626. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** 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. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. 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 (April 2006) is 6558 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: '1035' on line 83 -- Looks like a reference, but probably isn't: '0' on line 552 == Missing Reference: 'P-1' is mentioned on line 552, but not defined == Missing Reference: 'RFC 1750' is mentioned on line 454, but not defined ** Obsolete undefined reference: RFC 1750 (Obsoleted by RFC 4086) == Missing Reference: 'RFC 4304' is mentioned on line 470, but not defined == Missing Reference: 'RFC 2535' is mentioned on line 487, but not defined ** Obsolete undefined reference: RFC 2535 (Obsoleted by RFC 4033, RFC 4034, RFC 4035) == Unused Reference: 'RFC 1035' is defined on line 633, but no explicit reference was found in the text == Unused Reference: 'RFC 4033' is defined on line 642, but no explicit reference was found in the text == Unused Reference: 'RFC 4035' is defined on line 646, but no explicit reference was found in the text == Unused Reference: 'Silverman' is defined on line 659, but no explicit reference was found in the text -- 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: 5 errors (**), 0 flaws (~~), 10 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT Richard C. Schroeppel 2 Donald E. Eastlake 3rd 3 Expires: October 2006 April 2006 5 Elliptic Curve Keys and Signatures in the Domain Name System (DNS) 6 -------- ----- ---- --- ---------- -- --- ------ ---- ------ ----- 7 9 Richard C. Schroeppel 10 Donald Eastlake 3rd 12 Status of This Document 14 By submitting this Internet-Draft, each author represents that any 15 applicable patent or other IPR claims of which he or she is aware 16 have been or will be disclosed, and any of which he or she becomes 17 aware will be disclosed, in accordance with Section 6 of BCP 79. 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 as "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 format for storing elliptic curve cryptographic keys and 42 elliptic curve SHA-1 based signatures in the Domain Name System (DNS) 43 is specified. 45 Copyright Notice 47 Copyright (C) The Internet Society (2006). 49 Acknowledgement 51 The assistance of Hilarie K. Orman in the production of this document 52 is greatfully acknowledged. 54 Table of Contents 56 Status of This Document....................................1 57 Abstract...................................................1 58 Copyright Notice...........................................1 60 Acknowledgement............................................2 61 Table of Contents..........................................2 63 1. Introduction............................................3 64 2. Elliptic Curve Keys in Resource Records.................3 65 3. The Elliptic Curve Equation.............................9 66 4. How do I Compute Q, G, and Y?..........................10 67 5. Elliptic Curve Signatures..............................11 68 6. Performance Considerations.............................13 69 7. Security Considerations................................13 70 8. IANA Considerations....................................13 71 Copyright, Disclaimer, and Additional IPR Provisions......13 73 Informational References..................................15 74 Normative Refrences.......................................15 76 Author's Addresses........................................16 77 Expiration and File Name..................................16 79 1. Introduction 81 The Domain Name System (DNS) is the global hierarchical replicated 82 distributed database system for Internet addressing, mail proxy, and 83 other information. [RFC 1034, 1035] The DNS stores data in resource 84 records and has been extended to include digital signatures and 85 cryptographic keys in some of these resource records. 87 This document describes how to format elliptic curve cryptographic 88 (ECC) key and signature data in the DNS so they can be used for a 89 variety of purposes. The signatures use the SHA-1 eigest algorithm 90 [RFC 3174]. Familiarity with ECC cryptography is assumed [Menezes]. 92 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 93 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 94 document are to be interpreted as described in [RFC 2119]. 96 2. Elliptic Curve Keys in Resource Records 98 Elliptic curve public keys are stored, using the structure described 99 below, in the DNS within the RDATA portions of key RRs, such as RRKEY 100 [RFC 4034] and IPSECKEY [RFC 4025] RRs. 102 The research world continues to work on the issue of which is the 103 best elliptic curve system, which finite field to use, and how to 104 best represent elements in the field. So, representations are 105 defined for every type of finite field, and every type of elliptic 106 curve. The reader should be aware that there is a unique finite 107 field with a particular number of elements, but many possible 108 representations of that field and its elements. If two different 109 representations of a field are given, they are interconvertible with 110 a tedious but practical precomputation, followed by a fast 111 computation for each field element to be converted. It is perfectly 112 reasonable for an algorithm to work internally with one field 113 representation, and convert to and from a different external 114 representation. 116 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 117 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 118 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 119 |S M -FMT- A B Z| 120 +-+-+-+-+-+-+-+-+ 121 | LP | 122 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 123 | P (length determined from LP) .../ 124 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 125 | LF | 126 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 127 | F (length determined from LF) .../ 128 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 129 | DEG | 130 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 131 | DEGH | 132 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 133 | DEGI | 134 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 135 | DEGJ | 136 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 137 | TRDV | 138 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 139 |S| LH | 140 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 141 | H (length determined from LH) .../ 142 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 143 |S| LK | 144 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 145 | K (length determined from LK) .../ 146 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 147 | LQ | 148 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 149 | Q (length determined from LQ) .../ 150 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 151 | LA | 152 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 153 | A (length determined from LA) .../ 154 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 155 | ALTA | 156 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 157 | LB | 158 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 159 | B (length determined from LB) .../ 160 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 161 | LC | 162 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 163 | C (length determined from LC) .../ 164 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 165 | LG | 166 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 167 | G (length determined from LG) .../ 168 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 169 | LY | 170 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 171 | Y (length determined from LY) .../ 172 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 174 SMFMTABZ is a flags octet as follows: 176 S = 1 indicates that the remaining 7 bits of the octet selects 177 one of 128 predefined choices of finite field, element 178 representation, elliptic curve, and signature parameters. 179 MFMTABZ are omitted, as are all parameters from LP through G. 180 LY and Y are retained. 182 If S = 0, the remaining parameters are as in the picture and 183 described below. 185 M determines the type of field underlying the elliptic curve. 187 M = 0 if the field is a GF[2^N] field; 189 M = 1 if the field is a (mod P) or GF[P^D] field with P>2. 191 FMT is a three bit field describing the format of the field 192 representation. 194 FMT = 0 for a (mod P) field. 195 > 0 for an extension field, either GF[2^D] or GF[P^D]. 196 The degree D of the extension, and the field polynomial 197 must be specified. The field polynomial is always monic 198 (leading coefficient 1.) 200 FMT = 1 The field polynomial is given explicitly; D is implied. 202 If FMT >=2, the degree D is given explicitly. 204 = 2 The field polynomial is implicit. 205 = 3 The field polynomial is a binomial. P>2. 206 = 4 The field polynomial is a trinomial. 207 = 5 The field polynomial is the quotient of a trinomial by a 208 short polynomial. P=2. 209 = 6 The field polynomial is a pentanomial. P=2. 211 Flags A and B apply to the elliptic curve parameters. 213 A = 1 When P>=5, the curve parameter A is negated. If P=2, then 214 A=1 indicates that the A parameter is special. See the 215 ALTA parameter below, following A. The combination A=1, 216 P=3 is forbidden. 218 B = 1 When P>=5, the curve parameter B is negated. If P=2 or 3, 219 then B=1 indicates an alternate elliptic curve equation is 220 used. When P=2 and B=1, an additional curve parameter C 221 is present. 223 The Z bit SHOULD be set to zero on creation of an RR and MUST be 224 ignored when processing an RR (when S=0). 226 Most of the remaining parameters are present in some formats and 227 absent in others. The presence or absence of a parameter is 228 determined entirely by the flags. When a parameter occurs, it is in 229 the order defined by the picture. 231 Of the remaining parameters, PFHKQABCGY are variable length. When 232 present, each is preceded by a one-octet length field as shown in the 233 diagram above. The length field does not include itself. The length 234 field may have values from 0 through 110. The parameter length in 235 octets is determined by a conditional formula: If LL<=64, the 236 parameter length is LL. If LL>64, the parameter length is 16 times 237 (LL-60). In some cases, a parameter value of 0 is sensible, and MAY 238 be represented by an LL value of 0, with the data field omitted. A 239 length value of 0 represents a parameter value of 0, not an absent 240 parameter. (The data portion occupies 0 space.) There is no 241 requirement that a parameter be represented in the minimum number of 242 octets; high-order 0 octets are allowed at the front end. Parameters 243 are always right adjusted, in a field of length defined by LL. The 244 octet-order is always most-significant first, least-significant last. 245 The parameters H and K may have an optional sign bit stored in the 246 unused high-order bit of their length fields. 248 LP defines the length of the prime P. P must be an odd prime. The 249 parameters LP,P are present if and only if the flag M=1. If M=0, the 250 prime is 2. 252 LF,F define an explicit field polynomial. This parameter pair is 253 present only when FMT = 1. The length of a polynomial coefficient is 254 ceiling(log2 P) bits. Coefficients are in the numerical range 255 [0,P-1]. The coefficients are packed into fixed-width fields, from 256 higher order to lower order. All coefficients must be present, 257 including any 0s and also the leading coefficient (which is required 258 to be 1). The coefficients are right justified into the octet string 259 of length specified by LF, with the low-order "constant" coefficient 260 at the right end. As a concession to storage efficiency, the higher 261 order bits of the leading coefficient may be elided, discarding high- 262 order 0 octets and reducing LF. The degree is calculated by 263 determining the bit position of the left most 1-bit in the F data 264 (counting the right most bit as position 0), and dividing by 265 ceiling(log2 P). The division must be exact, with no remainder. In 266 this format, all of the other degree and field parameters are 267 omitted. The next parameters will be LQ,Q. 269 If FMT>=2, the degree of the field extension is specified explicitly, 270 usually along with other parameters to define the field polynomial. 272 DEG is a two octet field that defines the degree of the field 273 extension. The finite field will have P^DEG elements. DEG is 274 present when FMT>=2. 276 When FMT=2, the field polynomial is specified implicitly. No other 277 parameters are required to define the field; the next parameters 278 present will be the LQ,Q pair. The implicit field poynomial is the 279 lexicographically smallest irreducible (mod P) polynomial of the 280 correct degree. The ordering of polynomials is by highest-degree 281 coefficients first -- the leading coefficient 1 is most important, 282 and the constant term is least important. Coefficients are ordered 283 by sign-magnitude: 0 < 1 < -1 < 2 < -2 < ... The first polynomial of 284 degree D is X^D (which is not irreducible). The next is X^D+1, which 285 is sometimes irreducible, followed by X^D-1, which isn't. Assuming 286 odd P, this series continues to X^D - (P-1)/2, and then goes to X^D + 287 X, X^D + X + 1, X^D + X - 1, etc. 289 When FMT=3, the field polynomial is a binomial, X^DEG + K. P must be 290 odd. The polynomial is determined by the degree and the low order 291 term K. Of all the field parameters, only the LK,K parameters are 292 present. The high-order bit of the LK octet stores on optional sign 293 for K; if the sign bit is present, the field polynomial is X^DEG - K. 295 When FMT=4, the field polynomial is a trinomial, X^DEG + H*X^DEGH + 296 K. When P=2, the H and K parameters are implicitly 1, and are 297 omitted from the representation. Only DEG and DEGH are present; the 298 next parameters are LQ,Q. When P>2, then LH,H and LK,K are 299 specified. Either or both of LH, LK may contain a sign bit for its 300 parameter. 302 When FMT=5, then P=2 (only). The field polynomial is the exact 303 quotient of a trinomial divided by a small polynomial, the trinomial 304 divisor. The small polynomial is right-adjusted in the two octet 305 field TRDV. DEG specifies the degree of the field. The degree of 306 TRDV is calculated from the position of the high-order 1 bit. The 307 trinomial to be divided is X^(DEG+degree(TRDV)) + X^DEGH + 1. If 308 DEGH is 0, the middle term is omitted from the trinomial. The 309 quotient must be exact, with no remainder. 311 When FMT=6, then P=2 (only). The field polynomial is a pentanomial, 312 with the degrees of the middle terms given by the three 2-octet 313 values DEGH, DEGI, DEGJ. The polynomial is X^DEG + X^DEGH + X^DEGI + 314 X^DEGJ + 1. The values must satisfy the inequality DEG > DEGH > DEGI 315 > DEGJ > 0. 317 DEGH, DEGI, DEGJ are two-octet fields that define the degree of 318 a term in a field polynomial. DEGH is present when FMT = 4, 319 5, or 6. DEGI and DEGJ are present only when FMT = 6. 321 TRDV is a two-octet right-adjusted binary polynomial of degree < 322 16. It is present only for FMT=5. 324 LH and H define the H parameter, present only when FMT=4 and P 325 is odd. The high bit of LH is an optional sign bit for H. 327 LK and K define the K parameter, present when FMT = 3 or 4, and 328 P is odd. The high bit of LK is an optional sign bit for K. 330 The remaining parameters are concerned with the elliptic curve and 331 the signature algorithm. 333 LQ defines the length of the prime Q. Q is a prime > 2^159. 335 In all 5 of the parameter pairs LA+A,LB+B,LC+C,LG+G,LY+Y, the data 336 member of the pair is an element from the finite field defined 337 earlier. The length field defines a long octet string. Field 338 elements are represented as (mod P) polynomials of degree < DEG, with 339 DEG or fewer coefficients. The coefficients are stored from left to 340 right, higher degree to lower, with the constant term last. The 341 coefficients are represented as integers in the range [0,P-1]. Each 342 coefficient is allocated an area of ceiling(log2 P) bits. The field 343 representation is right-justified; the "constant term" of the field 344 element ends at the right most bit. The coefficients are fitted 345 adjacently without regard for octet boundaries. (Example: if P=5, 346 three bits are used for each coefficient. If the field is GF[5^75], 347 then 225 bits are required for the coefficients, and as many as 29 348 octets may be needed in the data area. Fewer octets may be used if 349 some high-order coefficients are 0.) If a flag requires a field 350 element to be negated, each non-zero coefficient K is replaced with 351 P-K. To save space, 0 bits may be removed from the left end of the 352 element representation, and the length field reduced appropriately. 353 This would normally only happen with A,B,C, because the designer 354 chose curve parameters with some high-order 0 coefficients or bits. 356 If the finite field is simply (mod P), then the field elements are 357 simply numbers (mod P), in the usual right-justified notation. If 358 the finite field is GF[2^D], the field elements are the usual right- 359 justified polynomial basis representation. 361 LA,A is the first parameter of the elliptic curve equation. 362 When P>=5, the flag A = 1 indicates A should be negated (mod 363 P). When P=2 (indicated by the flag M=0), the flag A = 1 364 indicates that the parameter pair LA,A is replaced by the two 365 octet parameter ALTA. In this case, the parameter A in the 366 curve equation is x^ALTA, where x is the field generator. 367 Parameter A often has the value 0, which may be indicated by 368 LA=0 (with no A data field), and sometimes A is 1, which may 369 be represented with LA=1 and a data field of 1, or by setting 370 the A flag and using an ALTA value of 0. 372 LB,B is the second parameter of the elliptic curve equation. 373 When P>=5, the flag B = 1 indicates B should be negated (mod 374 P). When P=2 or 3, the flag B selects an alternate curve 375 equation. 377 LC,C is the third parameter of the elliptic curve equation, 378 present only when P=2 (indicated by flag M=0) and flag B=1. 380 LG,G defines a point on the curve, of order Q. The W-coordinate 381 of the curve point is given explicitly; the Z-coordinate is 382 implicit. 384 LY,Y is the user's public signing key, another curve point of 385 order Q. The W-coordinate is given explicitly; the Z- 386 coordinate is implicit. The LY,Y parameter pair is always 387 present. 389 3. The Elliptic Curve Equation 391 (The coordinates of an elliptic curve point are named W,Z instead of 392 the more usual X,Y to avoid confusion with the Y parameter of the 393 signing key.) 395 The elliptic curve equation is determined by the flag octet, together 396 with information about the prime P. The primes 2 and 3 are special; 397 all other primes are treated identically. 399 If M=1, the (mod P) or GF[P^D] case, the curve equation is Z^2 = W^3 400 + A*W + B. Z,W,A,B are all numbers (mod P) or elements of GF[P^D]. 401 If A and/or B is negative (i.e., in the range from P/2 to P), and 402 P>=5, space may be saved by putting the sign bit(s) in the A and B 403 bits of the flags octet, and the magnitude(s) in the parameter 404 fields. 406 If M=1 and P=3, the B flag has a different meaning: it specifies an 407 alternate curve equation, Z^2 = W^3 + A*W^2 + B. The middle term of 408 the right-hand-side is different. When P=3, this equation is more 409 commonly used. 411 If M=0, the GF[2^N] case, the curve equation is Z^2 + W*Z = W^3 + 412 A*W^2 + B. Z,W,A,B are all elements of the field GF[2^N]. The A 413 parameter can often be 0 or 1, or be chosen as a single-1-bit value. 414 The flag B is used to select an alternate curve equation, Z^2 + C*Z = 415 W^3 + A*W + B. This is the only time that the C parameter is used. 417 4. How do I Compute Q, G, and Y? 419 The number of points on the curve is the number of solutions to the 420 curve equation, + 1 (for the "point at infinity"). The prime Q must 421 divide the number of points. Usually the curve is chosen first, then 422 the number of points is determined with Schoof's algorithm. This 423 number is factored, and if it has a large prime divisor, that number 424 is taken as Q. 426 G must be a point of order Q on the curve, satisfying the equation 428 Q * G = the point at infinity (on the elliptic curve) 430 G may be chosen by selecting a random [RFC 1750] curve point, and 431 multiplying it by (number-of-points-on-curve/Q). G must not itself 432 be the "point at infinity"; in this astronomically unlikely event, a 433 new random curve point is recalculated. 435 G is specified by giving its W-coordinate. The Z-coordinate is 436 calculated from the curve equation. In general, there will be two 437 possible Z values. The rule is to choose the "positive" value. 439 In the (mod P) case, the two possible Z values sum to P. The smaller 440 value is less than P/2; it is used in subsequent calculations. In 441 GF[P^D] fields, the highest-degree non-zero coefficient of the field 442 element Z is used; it is chosen to be less than P/2. 444 In the GF[2^N] case, the two possible Z values xor to W (or to the 445 parameter C with the alternate curve equation). The numerically 446 smaller Z value (the one which does not contain the highest-order 1 447 bit of W (or C)) is used in subsequent calculations. 449 Y is specified by giving the W-coordinate of the user's public 450 signature key. The Z-coordinate value is determined from the curve 451 equation. As with G, there are two possible Z values; the same rule 452 is followed for choosing which Z to use. 454 During the key generation process, a random [RFC 1750] number X must 455 be generated such that 1 <= X <= Q-1. X is the private key and is 456 used in the final step of public key generation where Y is computed 457 as 459 Y = X * G (as points on the elliptic curve) 461 If the Z-coordinate of the computed point Y is wrong (i.e., Z > P/2 462 in the (mod P) case, or the high-order non-zero coefficient of Z > 463 P/2 in the GF[P^D] case, or Z sharing a high bit with W(C) in the 464 GF[2^N] case), then X must be replaced with Q-X. This will 465 correspond to the correct Z-coordinate. 467 5. Elliptic Curve Signatures 469 The signature portion of an RR RDATA area when using the ECC 470 algorithm, for example in the SIG and RRSIG [RFC 4304] RRs is shown 471 below. 473 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 474 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 475 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 476 | R, (length determined from LQ) .../ 477 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 478 | S, (length determined from LQ) .../ 479 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 481 R and S are integers (mod Q). Their length is specified by the LQ 482 field of the corresponding KEY RR and can also be calculated from the 483 SIG RR's RDLENGTH. They are right justified, high-order-octet first. 484 The same conditional formula for calculating the length from LQ is 485 used as for all the other length fields above. 487 The data signed is determined as specified in [RFC 2535]. Then the 488 following steps are taken where Q, P, G, and Y are as specified in 489 the public key [Schneier]. For further information on SHA-1, see [RFC 490 3174]. 492 hash = SHA-1 ( data ) 494 Generate random [RFC 4086] K such that 0 < K < Q. (Never sign 495 two different messages with the same K. K should be chosen 496 from a very large space: If an opponent learns a K value 497 for a single signature, the user's signing key is 498 compromised, and a forger can sign arbitrary messages. 499 There is no harm in signing the same message multiple times 500 with the same key or different keys.) 502 R = (the W-coordinate of ( K*G on the elliptic curve )) 503 interpreted as an integer, and reduced (mod Q). (R must 504 not be 0. In this astronomically unlikely event, generate 505 a new random K and recalculate R.) 507 S = ( K^(-1) * (hash + X*R) ) mod Q. 509 S must not be 0. In this astronomically unlikely event, 510 generate a new random K and recalculate R and S. 512 If S > Q/2, set S = Q - S. 514 The pair (R,S) is the signature. 516 Another party verifies the signature as follows. For further 517 information on SHA-1, see [RFC 3174]. 519 Check that 0 < R < Q and 0 < S < Q/2. If not, it can not be a 520 valid EC sigature. 522 hash = SHA-1 ( data ) 524 Sinv = S^(-1) mod Q. 526 U1 = (hash * Sinv) mod Q. 528 U2 = (R * Sinv) mod Q. 530 (U1 * G + U2 * Y) is computed on the elliptic curve. 532 V = (the W-coordinate of this point) interpreted as an integer 533 and reduced (mod Q). 535 The signature is valid if V = R. 537 The reason for requiring S < Q/2 is that, otherwise, both (R,S) and 538 (R,Q-S) would be valid signatures for the same data. Note that a 539 signature that is valid for hash(data) is also valid for hash(data)+Q 540 or hash(data)-Q, if these happen to fall in the range [0,2^160-1]. 541 It's believed to be computationally infeasible to find data that 542 hashes to an assigned value, so this is only a cosmetic blemish. The 543 blemish can be eliminated by using Q > 2^160, at the cost of having 544 slightly longer signatures, 42 octets instead of 40. 546 We must specify how a field-element E ("the W-coordinate") is to be 547 interpreted as an integer. The field-element E is regarded as a 548 radix-P integer, with the digits being the coefficients in the 549 polynomial basis representation of E. The digits are in the ragne 550 [0,P-1]. In the two most common cases, this reduces to "the obvious 551 thing". In the (mod P) case, E is simply a residue mod P, and is 552 taken as an integer in the range [0,P-1]. In the GF[2^D] case, E is 553 in the D-bit polynomial basis representation, and is simply taken as 554 an integer in the range [0,(2^D)-1]. For other fields GF[P^D], it's 555 necessary to do some radix conversion arithmetic. 557 6. Performance Considerations 559 Elliptic curve signatures use smaller moduli or field sizes than RSA 560 and DSA. Creation of a curve is slow, but not done very often. Key 561 generation is faster than RSA or DSA. 563 DNS implementations have been optimized for small transfers, 564 typically less than 512 octets including DNS overhead. Larger 565 transfers will perform correctly and and extensions have been 566 standardized to make larger transfers more efficient [RFC 2671]. 567 However, it is still advisable at this time to make reasonable 568 efforts to minimize the size of RR sets stored within the DNS 569 consistent with adequate security. 571 7. Security Considerations 573 Keys retrieved from the DNS should not be trusted unless (1) they 574 have been securely obtained from a secure resolver or independently 575 verified by the user and (2) this secure resolver and secure 576 obtainment or independent verification conform to security policies 577 acceptable to the user. As with all cryptographic algorithms, 578 evaluating the necessary strength of the key is essential and 579 dependent on local policy. 581 Some specific key generation considerations are given in the body of 582 this document. 584 8. IANA Considerations 586 Assignment of meaning to the remaining ECC data flag bits or to 587 values of ECC fields outside the ranges for which meaning in defined 588 in this document requires an IETF consensus as defined in [RFC 2434]. 590 Copyright, Disclaimer, and Additional IPR Provisions 592 Copyright (C) The Internet Society 2006. 594 This document is subject to the rights, licenses and restrictions 595 contained in BCP 78, and except as set forth therein, the authors 596 retain all their rights. 598 This document and the information contained herein are provided on an 599 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 600 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 601 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 602 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 603 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 604 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 606 The IETF takes no position regarding the validity or scope of any 607 Intellectual Property Rights or other rights that might be claimed to 608 pertain to the implementation or use of the technology described in 609 this document or the extent to which any license under such rights 610 might or might not be available; nor does it represent that it has 611 made any independent effort to identify any such rights. Information 612 on the procedures with respect to rights in RFC documents can be 613 found in BCP 78 and BCP 79. 615 Copies of IPR disclosures made to the IETF Secretariat and any 616 assurances of licenses to be made available, or the result of an 617 attempt made to obtain a general license or permission for the use of 618 such proprietary rights by implementers or users of this 619 specification can be obtained from the IETF on-line IPR repository at 620 http://www.ietf.org/ipr. 622 The IETF invites any interested party to bring to its attention any 623 copyrights, patents or patent applications, or other proprietary 624 rights that may cover technology that may be required to implement 625 this standard. Please address the information to the IETF at ietf- 626 ipr@ietf.org. 628 Informational References 630 [RFC 1034] - P. Mockapetris, "Domain names - concepts and 631 facilities", 11/01/1987. 633 [RFC 1035] - P. Mockapetris, "Domain names - implementation and 634 specification", 11/01/1987. 636 [RFC 2671] - P. Vixie, "Extension Mechanisms for DNS (EDNS0)", August 637 1999. 639 [RFC 4025] - M. Richardson, "A Method for Storing IPsec Keying 640 Material in DNS", February 2005. 642 [RFC 4033] - Arends, R., Austein, R., Larson, M., Massey, D., and S. 643 Rose, "DNS Security Introduction and Requirements", RFC 4033, March 644 2005. 646 [RFC 4035] - Arends, R., Austein, R., Larson, M., Massey, D., and S. 647 Rose, "Protocol Modifications for the DNS Security Extensions", RFC 648 4035, March 2005. 650 [RFC 4086] - Eastlake, D., 3rd, Schiller, J., and S. Crocker, 651 "Randomness Requirements for Security", BCP 106, RFC 4086, June 2005. 653 [Schneier] - Bruce Schneier, "Applied Cryptography: Protocols, 654 Algorithms, and Source Code in C", 1996, John Wiley and Sons 656 [Menezes] - Alfred Menezes, "Elliptic Curve Public Key 657 Cryptosystems", 1993 Kluwer. 659 [Silverman] - Joseph Silverman, "The Arithmetic of Elliptic Curves", 660 1986, Springer Graduate Texts in mathematics #106. 662 Normative Refrences 664 [RFC 2119] - S. Bradner, "Key words for use in RFCs to Indicate 665 Requirement Levels", March 1997. 667 [RFC 2434] - T. Narten, H. Alvestrand, "Guidelines for Writing an 668 IANA Considerations Section in RFCs", October 1998. 670 [RFC 3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm 671 1 (SHA1)", RFC 3174, September 2001. 673 [RFC 4034] - Arends, R., Austein, R., Larson, M., Massey, D., and S. 674 Rose, "Resource Records for the DNS Security Extensions", RFC 4034, 675 March 2005. 677 Author's Addresses 679 Rich Schroeppel 680 500 S. Maple Drive 681 Woodland Hills, UT 84653 USA 683 Telephone: +1-505-844-9079(w) 684 Email: rschroe@sandia.gov 686 Donald E. Eastlake 3rd 687 Motorola Laboratories 688 155 Beaver Street 689 Milford, MA 01757 USA 691 Telephone: +1 508-786-7554 (w) 692 EMail: Donald.Eastlake@motorola.com 694 Expiration and File Name 696 This draft expires in October 2006. 698 Its file name is draft-ietf-dnsext-ecc-key-09.txt.