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