idnits 2.17.1 draft-ietf-dnsext-ecc-key-08.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 612. ** 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. ** 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. 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 : ---------------------------------------------------------------------------- ** 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 (October 2005) is 6767 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 554 == Missing Reference: 'P-1' is mentioned on line 554, but not defined == Missing Reference: 'RFC 1750' is mentioned on line 455, but not defined ** Obsolete undefined reference: RFC 1750 (Obsoleted by RFC 4086) == Missing Reference: 'RFC 2535' is mentioned on line 488, but not defined ** Obsolete undefined reference: RFC 2535 (Obsoleted by RFC 4033, RFC 4034, RFC 4035) == Unused Reference: 'RFC 1034' is defined on line 616, but no explicit reference was found in the text == Unused Reference: 'RFC 1035' is defined on line 619, but no explicit reference was found in the text == Unused Reference: 'RFC 4033' is defined on line 625, but no explicit reference was found in the text == Unused Reference: 'RFC 4035' is defined on line 629, but no explicit reference was found in the text == Unused Reference: 'Silverman' is defined on line 643, 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: 10 errors (**), 0 flaws (~~), 10 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT Richard C. Schroeppel 2 Donald Eastlake 3rd 3 Expires: April 2006 October 2005 5 Elliptic Curve Keys and Signatures in the 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 method for storing elliptic curve cryptographic keys and 42 elliptic curve SHA-1 based signatures in the Domain Name System is 43 specified. 45 Copyright Notice 47 Copyright (C) The Internet Society (2005). 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 Signature Resource Records..............11 68 6. Performance Considerations.............................13 69 7. Security Considerations................................13 70 8. IANA Considerations....................................13 71 Copyright and Disclaimer..................................14 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. The DNS has been extended to include digital 84 signatures and cryptographic keys as described in [RFC 4033, 4034, 85 4035]. 87 This document describes how to store elliptic curve cryptographic 88 (ECC) keys and signatures in the DNS so they can be used for a 89 variety of security purposes. The signatures use the SHA-1 eigest 90 algorithm [RFC 3174]. Familiarity with ECC cryptography is assumed 91 [Menezes]. 93 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 94 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 95 document are to be interpreted as described in [RFC 2119]. 97 2. Elliptic Curve Keys in Resource Records 99 Elliptic curve public keys are stored in the DNS within the RDATA 100 portions of key RRs, such as RRKEY and KEY [RFC 4034] RRs, with the 101 structure shown below. 103 The research world continues to work on the issue of which is the 104 best elliptic curve system, which finite field to use, and how to 105 best represent elements in the field. So, representations are 106 defined for every type of finite field, and every type of elliptic 107 curve. The reader should be aware that there is a unique finite 108 field with a particular number of elements, but many possible 109 representations of that field and its elements. If two different 110 representations of a field are given, they are interconvertible with 111 a tedious but practical precomputation, followed by a fast 112 computation for each field element to be converted. It is perfectly 113 reasonable for an algorithm to work internally with one field 114 representation, and convert to and from a different external 115 representation. 117 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 118 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 119 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 120 |S M -FMT- A B Z| 121 +-+-+-+-+-+-+-+-+ 122 | LP | 123 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 124 | P (length determined from LP) .../ 125 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 126 | LF | 127 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 128 | F (length determined from LF) .../ 129 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 130 | DEG | 131 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 132 | DEGH | 133 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 134 | DEGI | 135 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 136 | DEGJ | 137 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 138 | TRDV | 139 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 140 |S| LH | 141 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 142 | H (length determined from LH) .../ 143 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 144 |S| LK | 145 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 146 | K (length determined from LK) .../ 147 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 148 | LQ | 149 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 150 | Q (length determined from LQ) .../ 151 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 152 | LA | 153 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 154 | A (length determined from LA) .../ 155 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 156 | ALTA | 157 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 158 | LB | 159 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 160 | B (length determined from LB) .../ 161 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 162 | LC | 163 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 164 | C (length determined from LC) .../ 165 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 166 | LG | 167 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 168 | G (length determined from LG) .../ 169 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 170 | LY | 171 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 172 | Y (length determined from LY) .../ 173 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 175 SMFMTABZ is a flags octet as follows: 177 S = 1 indicates that the remaining 7 bits of the octet selects 178 one of 128 predefined choices of finite field, element 179 representation, elliptic curve, and signature parameters. 180 MFMTABZ are omitted, as are all parameters from LP through G. 181 LY and Y are retained. 183 If S = 0, the remaining parameters are as in the picture and 184 described below. 186 M determines the type of field underlying the elliptic curve. 188 M = 0 if the field is a GF[2^N] field; 190 M = 1 if the field is a (mod P) or GF[P^D] field with P>2. 192 FMT is a three bit field describing the format of the field 193 representation. 195 FMT = 0 for a (mod P) field. 196 > 0 for an extension field, either GF[2^D] or GF[P^D]. 197 The degree D of the extension, and the field polynomial 198 must be specified. The field polynomial is always monic 199 (leading coefficient 1.) 201 FMT = 1 The field polynomial is given explicitly; D is implied. 203 If FMT >=2, the degree D is given explicitly. 205 = 2 The field polynomial is implicit. 206 = 3 The field polynomial is a binomial. P>2. 207 = 4 The field polynomial is a trinomial. 208 = 5 The field polynomial is the quotient of a trinomial by a 209 short polynomial. P=2. 210 = 6 The field polynomial is a pentanomial. P=2. 212 Flags A and B apply to the elliptic curve parameters. 214 A = 1 When P>=5, the curve parameter A is negated. If P=2, then 215 A=1 indicates that the A parameter is special. See the 216 ALTA parameter below, following A. The combination A=1, 217 P=3 is forbidden. 219 B = 1 When P>=5, the curve parameter B is negated. If P=2 or 3, 220 then B=1 indicates an alternate elliptic curve equation is 221 used. When P=2 and B=1, an additional curve parameter C 222 is present. 224 The Z bit SHOULD be set to zero on creation of an RR and MUST be 225 ignored when processing an RR (when S=0). 227 Most of the remaining parameters are present in some formats and 228 absent in others. The presence or absence of a parameter is 229 determined entirely by the flags. When a parameter occurs, it is in 230 the order defined by the picture. 232 Of the remaining parameters, PFHKQABCGY are variable length. When 233 present, each is preceded by a one-octet length field as shown in the 234 diagram above. The length field does not include itself. The length 235 field may have values from 0 through 110. The parameter length in 236 octets is determined by a conditional formula: If LL<=64, the 237 parameter length is LL. If LL>64, the parameter length is 16 times 238 (LL-60). In some cases, a parameter value of 0 is sensible, and MAY 239 be represented by an LL value of 0, with the data field omitted. A 240 length value of 0 represents a parameter value of 0, not an absent 241 parameter. (The data portion occupies 0 space.) There is no 242 requirement that a parameter be represented in the minimum number of 243 octets; high-order 0 octets are allowed at the front end. Parameters 244 are always right adjusted, in a field of length defined by LL. The 245 octet-order is always most-significant first, least-significant last. 246 The parameters H and K may have an optional sign bit stored in the 247 unused high-order bit of their length fields. 249 LP defines the length of the prime P. P must be an odd prime. The 250 parameters LP,P are present if and only if the flag M=1. If M=0, the 251 prime is 2. 253 LF,F define an explicit field polynomial. This parameter pair is 254 present only when FMT = 1. The length of a polynomial coefficient is 255 ceiling(log2 P) bits. Coefficients are in the numerical range 256 [0,P-1]. The coefficients are packed into fixed-width fields, from 257 higher order to lower order. All coefficients must be present, 258 including any 0s and also the leading coefficient (which is required 259 to be 1). The coefficients are right justified into the octet string 260 of length specified by LF, with the low-order "constant" coefficient 261 at the right end. As a concession to storage efficiency, the higher 262 order bits of the leading coefficient may be elided, discarding high- 263 order 0 octets and reducing LF. The degree is calculated by 264 determining the bit position of the left most 1-bit in the F data 265 (counting the right most bit as position 0), and dividing by 266 ceiling(log2 P). The division must be exact, with no remainder. In 267 this format, all of the other degree and field parameters are 268 omitted. The next parameters will be LQ,Q. 270 If FMT>=2, the degree of the field extension is specified explicitly, 271 usually along with other parameters to define the field polynomial. 273 DEG is a two octet field that defines the degree of the field 274 extension. The finite field will have P^DEG elements. DEG is 275 present when FMT>=2. 277 When FMT=2, the field polynomial is specified implicitly. No other 278 parameters are required to define the field; the next parameters 279 present will be the LQ,Q pair. The implicit field poynomial is the 280 lexicographically smallest irreducible (mod P) polynomial of the 281 correct degree. The ordering of polynomials is by highest-degree 282 coefficients first -- the leading coefficient 1 is most important, 283 and the constant term is least important. Coefficients are ordered 284 by sign-magnitude: 0 < 1 < -1 < 2 < -2 < ... The first polynomial of 285 degree D is X^D (which is not irreducible). The next is X^D+1, which 286 is sometimes irreducible, followed by X^D-1, which isn't. Assuming 287 odd P, this series continues to X^D - (P-1)/2, and then goes to X^D + 288 X, X^D + X + 1, X^D + X - 1, etc. 290 When FMT=3, the field polynomial is a binomial, X^DEG + K. P must be 291 odd. The polynomial is determined by the degree and the low order 292 term K. Of all the field parameters, only the LK,K parameters are 293 present. The high-order bit of the LK octet stores on optional sign 294 for K; if the sign bit is present, the field polynomial is X^DEG - K. 296 When FMT=4, the field polynomial is a trinomial, X^DEG + H*X^DEGH + 297 K. When P=2, the H and K parameters are implicitly 1, and are 298 omitted from the representation. Only DEG and DEGH are present; the 299 next parameters are LQ,Q. When P>2, then LH,H and LK,K are 300 specified. Either or both of LH, LK may contain a sign bit for its 301 parameter. 303 When FMT=5, then P=2 (only). The field polynomial is the exact 304 quotient of a trinomial divided by a small polynomial, the trinomial 305 divisor. The small polynomial is right-adjusted in the two octet 306 field TRDV. DEG specifies the degree of the field. The degree of 307 TRDV is calculated from the position of the high-order 1 bit. The 308 trinomial to be divided is X^(DEG+degree(TRDV)) + X^DEGH + 1. If 309 DEGH is 0, the middle term is omitted from the trinomial. The 310 quotient must be exact, with no remainder. 312 When FMT=6, then P=2 (only). The field polynomial is a pentanomial, 313 with the degrees of the middle terms given by the three 2-octet 314 values DEGH, DEGI, DEGJ. The polynomial is X^DEG + X^DEGH + X^DEGI + 315 X^DEGJ + 1. The values must satisfy the inequality DEG > DEGH > DEGI 316 > DEGJ > 0. 318 DEGH, DEGI, DEGJ are two-octet fields that define the degree of 319 a term in a field polynomial. DEGH is present when FMT = 4, 320 5, or 6. DEGI and DEGJ are present only when FMT = 6. 322 TRDV is a two-octet right-adjusted binary polynomial of degree < 323 16. It is present only for FMT=5. 325 LH and H define the H parameter, present only when FMT=4 and P 326 is odd. The high bit of LH is an optional sign bit for H. 328 LK and K define the K parameter, present when FMT = 3 or 4, and 329 P is odd. The high bit of LK is an optional sign bit for K. 331 The remaining parameters are concerned with the elliptic curve and 332 the signature algorithm. 334 LQ defines the length of the prime Q. Q is a prime > 2^159. 336 In all 5 of the parameter pairs LA+A,LB+B,LC+C,LG+G,LY+Y, the data 337 member of the pair is an element from the finite field defined 338 earlier. The length field defines a long octet string. Field 339 elements are represented as (mod P) polynomials of degree < DEG, with 340 DEG or fewer coefficients. The coefficients are stored from left to 341 right, higher degree to lower, with the constant term last. The 342 coefficients are represented as integers in the range [0,P-1]. Each 343 coefficient is allocated an area of ceiling(log2 P) bits. The field 344 representation is right-justified; the "constant term" of the field 345 element ends at the right most bit. The coefficients are fitted 346 adjacently without regard for octet boundaries. (Example: if P=5, 347 three bits are used for each coefficient. If the field is GF[5^75], 348 then 225 bits are required for the coefficients, and as many as 29 349 octets may be needed in the data area. Fewer octets may be used if 350 some high-order coefficients are 0.) If a flag requires a field 351 element to be negated, each non-zero coefficient K is replaced with 352 P-K. To save space, 0 bits may be removed from the left end of the 353 element representation, and the length field reduced appropriately. 354 This would normally only happen with A,B,C, because the designer 355 chose curve parameters with some high-order 0 coefficients or bits. 357 If the finite field is simply (mod P), then the field elements are 358 simply numbers (mod P), in the usual right-justified notation. If 359 the finite field is GF[2^D], the field elements are the usual right- 360 justified polynomial basis representation. 362 LA,A is the first parameter of the elliptic curve equation. 363 When P>=5, the flag A = 1 indicates A should be negated (mod 364 P). When P=2 (indicated by the flag M=0), the flag A = 1 365 indicates that the parameter pair LA,A is replaced by the two 366 octet parameter ALTA. In this case, the parameter A in the 367 curve equation is x^ALTA, where x is the field generator. 368 Parameter A often has the value 0, which may be indicated by 369 LA=0 (with no A data field), and sometimes A is 1, which may 370 be represented with LA=1 and a data field of 1, or by setting 371 the A flag and using an ALTA value of 0. 373 LB,B is the second parameter of the elliptic curve equation. 374 When P>=5, the flag B = 1 indicates B should be negated (mod 375 P). When P=2 or 3, the flag B selects an alternate curve 376 equation. 378 LC,C is the third parameter of the elliptic curve equation, 379 present only when P=2 (indicated by flag M=0) and flag B=1. 381 LG,G defines a point on the curve, of order Q. The W-coordinate 382 of the curve point is given explicitly; the Z-coordinate is 383 implicit. 385 LY,Y is the user's public signing key, another curve point of 386 order Q. The W-coordinate is given explicitly; the Z- 387 coordinate is implicit. The LY,Y parameter pair is always 388 present. 390 3. The Elliptic Curve Equation 392 (The coordinates of an elliptic curve point are named W,Z instead of 393 the more usual X,Y to avoid confusion with the Y parameter of the 394 signing key.) 396 The elliptic curve equation is determined by the flag octet, together 397 with information about the prime P. The primes 2 and 3 are special; 398 all other primes are treated identically. 400 If M=1, the (mod P) or GF[P^D] case, the curve equation is Z^2 = W^3 401 + A*W + B. Z,W,A,B are all numbers (mod P) or elements of GF[P^D]. 402 If A and/or B is negative (i.e., in the range from P/2 to P), and 403 P>=5, space may be saved by putting the sign bit(s) in the A and B 404 bits of the flags octet, and the magnitude(s) in the parameter 405 fields. 407 If M=1 and P=3, the B flag has a different meaning: it specifies an 408 alternate curve equation, Z^2 = W^3 + A*W^2 + B. The middle term of 409 the right-hand-side is different. When P=3, this equation is more 410 commonly used. 412 If M=0, the GF[2^N] case, the curve equation is Z^2 + W*Z = W^3 + 413 A*W^2 + B. Z,W,A,B are all elements of the field GF[2^N]. The A 414 parameter can often be 0 or 1, or be chosen as a single-1-bit value. 415 The flag B is used to select an alternate curve equation, Z^2 + C*Z = 416 W^3 + A*W + B. This is the only time that the C parameter is used. 418 4. How do I Compute Q, G, and Y? 420 The number of points on the curve is the number of solutions to the 421 curve equation, + 1 (for the "point at infinity"). The prime Q must 422 divide the number of points. Usually the curve is chosen first, then 423 the number of points is determined with Schoof's algorithm. This 424 number is factored, and if it has a large prime divisor, that number 425 is taken as Q. 427 G must be a point of order Q on the curve, satisfying the equation 429 Q * G = the point at infinity (on the elliptic curve) 431 G may be chosen by selecting a random [RFC 1750] curve point, and 432 multiplying it by (number-of-points-on-curve/Q). G must not itself 433 be the "point at infinity"; in this astronomically unlikely event, a 434 new random curve point is recalculated. 436 G is specified by giving its W-coordinate. The Z-coordinate is 437 calculated from the curve equation. In general, there will be two 438 possible Z values. The rule is to choose the "positive" value. 440 In the (mod P) case, the two possible Z values sum to P. The smaller 441 value is less than P/2; it is used in subsequent calculations. In 442 GF[P^D] fields, the highest-degree non-zero coefficient of the field 443 element Z is used; it is chosen to be less than P/2. 445 In the GF[2^N] case, the two possible Z values xor to W (or to the 446 parameter C with the alternate curve equation). The numerically 447 smaller Z value (the one which does not contain the highest-order 1 448 bit of W (or C)) is used in subsequent calculations. 450 Y is specified by giving the W-coordinate of the user's public 451 signature key. The Z-coordinate value is determined from the curve 452 equation. As with G, there are two possible Z values; the same rule 453 is followed for choosing which Z to use. 455 During the key generation process, a random [RFC 1750] number X must 456 be generated such that 1 <= X <= Q-1. X is the private key and is 457 used in the final step of public key generation where Y is computed 458 as 460 Y = X * G (as points on the elliptic curve) 462 If the Z-coordinate of the computed point Y is wrong (i.e., Z > P/2 463 in the (mod P) case, or the high-order non-zero coefficient of Z > 464 P/2 in the GF[P^D] case, or Z sharing a high bit with W(C) in the 465 GF[2^N] case), then X must be replaced with Q-X. This will 466 correspond to the correct Z-coordinate. 468 5. Elliptic Curve Signature Resource Records 470 The signature portion of an RR RDATA area when using the EC 471 algorithm, for example in the RRSIG and SIG [RFC records] RRs is 472 shown below. 474 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 475 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 476 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 477 | R, (length determined from LQ) .../ 478 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 479 | S, (length determined from LQ) .../ 480 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 482 R and S are integers (mod Q). Their length is specified by the LQ 483 field of the corresponding KEY RR and can also be calculated from the 484 SIG RR's RDLENGTH. They are right justified, high-order-octet first. 485 The same conditional formula for calculating the length from LQ is 486 used as for all the other length fields above. 488 The data signed is determined as specified in [RFC 2535]. Then the 489 following steps are taken where Q, P, G, and Y are as specified in 490 the public key [Schneier]. For further information on SHA-1, see [RFC 491 3174]. 493 hash = SHA-1 ( data ) 495 Generate random [RFC 4086] K such that 0 < K < Q. (Never sign two 496 different messages with the same K. K should be chosen from a 497 very large space: If an opponent learns a K value for a single 498 signature, the user's signing key is compromised, and a forger 499 can sign arbitrary messages. There is no harm in signing the 500 same message multiple times with the same key or different 501 keys.) 503 R = (the W-coordinate of ( K*G on the elliptic curve )) interpreted 504 as an integer, and reduced (mod Q). (R must not be 0. In 505 this astronomically unlikely event, generate a new random K 506 and recalculate R.) 508 S = ( K^(-1) * (hash + X*R) ) mod Q. 510 S must not be 0. In this astronomically unlikely event, generate a 511 new random K and recalculate R and S. 513 If S > Q/2, set S = Q - S. 515 The pair (R,S) is the signature. 517 Another party verifies the signature as follows. For further 518 information on SHA-1, see [RFC 3174]. 520 Check that 0 < R < Q and 0 < S < Q/2. If not, it can not be a 521 valid EC sigature. 523 hash = SHA-1 ( data ) 525 Sinv = S^(-1) mod Q. 527 U1 = (hash * Sinv) mod Q. 529 U2 = (R * Sinv) mod Q. 531 (U1 * G + U2 * Y) is computed on the elliptic curve. 533 V = (the W-coordinate of this point) interpreted as an integer 534 and reduced (mod Q). 536 The signature is valid if V = R. 538 The reason for requiring S < Q/2 is that, otherwise, both (R,S) and 539 (R,Q-S) would be valid signatures for the same data. Note that a 540 signature that is valid for hash(data) is also valid for 541 hash(data)+Q or hash(data)-Q, if these happen to fall in the range 542 [0,2^160-1]. It's believed to be computationally infeasible to 543 find data that hashes to an assigned value, so this is only a 544 cosmetic blemish. The blemish can be eliminated by using Q > 545 2^160, at the cost of having slightly longer signatures, 42 octets 546 instead of 40. 548 We must specify how a field-element E ("the W-coordinate") is to be 549 interpreted as an integer. The field-element E is regarded as a 550 radix-P integer, with the digits being the coefficients in the 551 polynomial basis representation of E. The digits are in the ragne 552 [0,P-1]. In the two most common cases, this reduces to "the 553 obvious thing". In the (mod P) case, E is simply a residue mod P, 554 and is taken as an integer in the range [0,P-1]. In the GF[2^D] 555 case, E is in the D-bit polynomial basis representation, and is 556 simply taken as an integer in the range [0,(2^D)-1]. For other 557 fields GF[P^D], it's necessary to do some radix conversion 558 arithmetic. 560 6. Performance Considerations 562 Elliptic curve signatures use smaller moduli or field sizes than 563 RSA and DSA. Creation of a curve is slow, but not done very often. 564 Key generation is faster than RSA or DSA. 566 DNS implementations have been optimized for small transfers, 567 typically less than 512 octets including DNS overhead. Larger 568 transfers will perform correctly and and extensions have been 569 standardized to make larger transfers more efficient [RFC 2671]. 570 However, it is still advisable at this time to make reasonable 571 efforts to minimize the size of RR sets stored within the DNS 572 consistent with adequate security. 574 7. Security Considerations 576 Keys retrieved from the DNS should not be trusted unless (1) they 577 have been securely obtained from a secure resolver or independently 578 verified by the user and (2) this secure resolver and secure 579 obtainment or independent verification conform to security policies 580 acceptable to the user. As with all cryptographic algorithms, 581 evaluating the necessary strength of the key is essential and 582 dependent on local policy. 584 Some specific key generation considerations are given in the body 585 of this document. 587 8. IANA Considerations 589 The key and signature data structures defined herein correspond to 590 the value 4 in the Algorithm number field of the IANA registry 592 Assignment of meaning to the remaining ECC data flag bits or to 593 values of ECC fields outside the ranges for which meaning in 594 defined in this document requires an IETF consensus as defined in 595 [RFC 2434]. 597 Copyright and Disclaimer 599 Copyright (C) The Internet Society 2005. 601 This document is subject to the rights, licenses and restrictions 602 contained in BCP 78, and except as set forth therein, the authors 603 retain all their rights. 605 This document and the information contained herein are provided on 606 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 607 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND 608 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, 609 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT 610 THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR 611 ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A 612 PARTICULAR PURPOSE. 614 Informational References 616 [RFC 1034] - P. Mockapetris, "Domain names - concepts and 617 facilities", 11/01/1987. 619 [RFC 1035] - P. Mockapetris, "Domain names - implementation and 620 specification", 11/01/1987. 622 [RFC 2671] - P. Vixie, "Extension Mechanisms for DNS (EDNS0)", 623 August 1999. 625 [RFC 4033] - Arends, R., Austein, R., Larson, M., Massey, D., and 626 S. Rose, "DNS Security Introduction and Requirements", RFC 4033, 627 March 2005. 629 [RFC 4035] - Arends, R., Austein, R., Larson, M., Massey, D., and 630 S. Rose, "Protocol Modifications for the DNS Security Extensions", 631 RFC 4035, March 2005. 633 [RFC 4086] - Eastlake, D., 3rd, Schiller, J., and S. Crocker, 634 "Randomness Requirements for Security", BCP 106, RFC 4086, June 635 2005. 637 [Schneier] - Bruce Schneier, "Applied Cryptography: Protocols, 638 Algorithms, and Source Code in C", 1996, John Wiley and Sons 640 [Menezes] - Alfred Menezes, "Elliptic Curve Public Key 641 Cryptosystems", 1993 Kluwer. 643 [Silverman] - Joseph Silverman, "The Arithmetic of Elliptic 644 Curves", 1986, Springer Graduate Texts in mathematics #106. 646 Normative Refrences 648 [RFC 2119] - S. Bradner, "Key words for use in RFCs to Indicate 649 Requirement Levels", March 1997. 651 [RFC 2434] - T. Narten, H. Alvestrand, "Guidelines for Writing an 652 IANA Considerations Section in RFCs", October 1998. 654 [RFC 3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash 655 Algorithm 1 (SHA1)", RFC 3174, September 2001. 657 [RFC 4034] - Arends, R., Austein, R., Larson, M., Massey, D., and 658 S. Rose, "Resource Records for the DNS Security Extensions", RFC 659 4034, March 2005. 661 Author's Addresses 663 Rich Schroeppel 664 500 S. Maple Drive 665 Woodland Hills, UT 84653 USA 667 Telephone: +1-505-844-9079(w) 668 Email: rschroe@sandia.gov 670 Donald E. Eastlake 3rd 671 Motorola Laboratories 672 155 Beaver Street 673 Milford, MA 01757 USA 675 Telephone: +1 508-786-7554 (w) 676 EMail: Donald.Eastlake@motorola.com 678 Expiration and File Name 680 This draft expires in April 2006. 682 Its file name is draft-ietf-dnsext-ecc-key-08.txt.