2 INTERNET-DRAFT ECC Keys in the DNS
3 Expires: January 2006 July 2005
7 Elliptic Curve KEYs in the DNS
8 -------- ----- ---- -- --- ---
9 <draft-ietf-dnsext-ecc-key-07.txt>
15 Status of This Document
17 By submitting this Internet-Draft, each author represents that any
18 applicable patent or other IPR claims of which he or she is aware
19 have been or will be disclosed, and any of which he or she becomes
20 aware will be disclosed, in accordance with Section 6 of BCP 79.
22 This draft is intended to be become a Proposed Standard RFC.
23 Distribution of this document is unlimited. Comments should be sent
24 to the DNS mailing list <namedroppers@ops.ietf.org>.
26 Internet-Drafts are working documents of the Internet Engineering
27 Task Force (IETF), its areas, and its working groups. Note that
28 other groups may also distribute working documents as Internet-
31 Internet-Drafts are draft documents valid for a maximum of six months
32 and may be updated, replaced, or obsoleted by other documents at any
33 time. It is inappropriate to use Internet-Drafts as reference
34 material or to cite them other than a "work in progress."
36 The list of current Internet-Drafts can be accessed at
37 http://www.ietf.org/1id-abstracts.html
39 The list of Internet-Draft Shadow Directories can be accessed at
40 http://www.ietf.org/shadow.html
45 The standard method for storing elliptic curve cryptographic keys and
46 signatures in the Domain Name System is specified.
51 Copyright (C) The Internet Society (2005). All Rights Reserved.
57 R. Schroeppel, et al [Page 1]
60 INTERNET-DRAFT ECC Keys in the DNS
65 The assistance of Hilarie K. Orman in the production of this document
66 is greatfully acknowledged.
72 Status of This Document....................................1
73 Abstract...................................................1
74 Copyright Notice...........................................1
76 Acknowledgement............................................2
77 Table of Contents..........................................2
79 1. Introduction............................................3
80 2. Elliptic Curve Data in Resource Records.................3
81 3. The Elliptic Curve Equation.............................9
82 4. How do I Compute Q, G, and Y?..........................10
83 5. Elliptic Curve SIG Resource Records....................11
84 6. Performance Considerations.............................13
85 7. Security Considerations................................13
86 8. IANA Considerations....................................13
87 Copyright and Disclaimer..................................14
89 Informational References..................................15
90 Normative Refrences.......................................15
92 Author's Addresses........................................16
93 Expiration and File Name..................................16
115 R. Schroeppel, et al [Page 2]
118 INTERNET-DRAFT ECC Keys in the DNS
123 The Domain Name System (DNS) is the global hierarchical replicated
124 distributed database system for Internet addressing, mail proxy, and
125 other information. The DNS has been extended to include digital
126 signatures and cryptographic keys as described in [RFC 4033, 4034,
129 This document describes how to store elliptic curve cryptographic
130 (ECC) keys and signatures in the DNS so they can be used for a
131 variety of security purposes. Familiarity with ECC cryptography is
134 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
135 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
136 document are to be interpreted as described in [RFC 2119].
140 2. Elliptic Curve Data in Resource Records
142 Elliptic curve public keys are stored in the DNS within the RDATA
143 portions of key RRs, such as RRKEY and KEY [RFC 4034] RRs, with the
144 structure shown below.
146 The research world continues to work on the issue of which is the
147 best elliptic curve system, which finite field to use, and how to
148 best represent elements in the field. So, representations are
149 defined for every type of finite field, and every type of elliptic
150 curve. The reader should be aware that there is a unique finite
151 field with a particular number of elements, but many possible
152 representations of that field and its elements. If two different
153 representations of a field are given, they are interconvertible with
154 a tedious but practical precomputation, followed by a fast
155 computation for each field element to be converted. It is perfectly
156 reasonable for an algorithm to work internally with one field
157 representation, and convert to and from a different external
173 R. Schroeppel, et al [Page 3]
176 INTERNET-DRAFT ECC Keys in the DNS
179 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3
180 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
181 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
185 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
186 | P (length determined from LP) .../
187 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
189 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
190 | F (length determined from LF) .../
191 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
193 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
195 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
197 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
199 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
201 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
203 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
204 | H (length determined from LH) .../
205 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
207 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
208 | K (length determined from LK) .../
209 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
211 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
212 | Q (length determined from LQ) .../
213 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
215 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
216 | A (length determined from LA) .../
217 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
219 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
221 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
222 | B (length determined from LB) .../
223 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
225 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
226 | C (length determined from LC) .../
227 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
231 R. Schroeppel, et al [Page 4]
234 INTERNET-DRAFT ECC Keys in the DNS
237 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
238 | G (length determined from LG) .../
239 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
241 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
242 | Y (length determined from LY) .../
243 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
245 SMFMTABZ is a flags octet as follows:
247 S = 1 indicates that the remaining 7 bits of the octet selects
248 one of 128 predefined choices of finite field, element
249 representation, elliptic curve, and signature parameters.
250 MFMTABZ are omitted, as are all parameters from LP through G.
251 LY and Y are retained.
253 If S = 0, the remaining parameters are as in the picture and
256 M determines the type of field underlying the elliptic curve.
258 M = 0 if the field is a GF[2^N] field;
260 M = 1 if the field is a (mod P) or GF[P^D] field with P>2.
262 FMT is a three bit field describing the format of the field
265 FMT = 0 for a (mod P) field.
266 > 0 for an extension field, either GF[2^D] or GF[P^D].
267 The degree D of the extension, and the field polynomial
268 must be specified. The field polynomial is always monic
269 (leading coefficient 1.)
271 FMT = 1 The field polynomial is given explicitly; D is implied.
273 If FMT >=2, the degree D is given explicitly.
275 = 2 The field polynomial is implicit.
276 = 3 The field polynomial is a binomial. P>2.
277 = 4 The field polynomial is a trinomial.
278 = 5 The field polynomial is the quotient of a trinomial by a
279 short polynomial. P=2.
280 = 6 The field polynomial is a pentanomial. P=2.
282 Flags A and B apply to the elliptic curve parameters.
289 R. Schroeppel, et al [Page 5]
292 INTERNET-DRAFT ECC Keys in the DNS
295 A = 1 When P>=5, the curve parameter A is negated. If P=2, then
296 A=1 indicates that the A parameter is special. See the
297 ALTA parameter below, following A. The combination A=1,
300 B = 1 When P>=5, the curve parameter B is negated. If P=2 or 3,
301 then B=1 indicates an alternate elliptic curve equation is
302 used. When P=2 and B=1, an additional curve parameter C
305 The Z bit SHOULD be set to zero on creation of an RR and MUST be
306 ignored when processing an RR (when S=0).
308 Most of the remaining parameters are present in some formats and
309 absent in others. The presence or absence of a parameter is
310 determined entirely by the flags. When a parameter occurs, it is in
311 the order defined by the picture.
313 Of the remaining parameters, PFHKQABCGY are variable length. When
314 present, each is preceded by a one-octet length field as shown in the
315 diagram above. The length field does not include itself. The length
316 field may have values from 0 through 110. The parameter length in
317 octets is determined by a conditional formula: If LL<=64, the
318 parameter length is LL. If LL>64, the parameter length is 16 times
319 (LL-60). In some cases, a parameter value of 0 is sensible, and MAY
320 be represented by an LL value of 0, with the data field omitted. A
321 length value of 0 represents a parameter value of 0, not an absent
322 parameter. (The data portion occupies 0 space.) There is no
323 requirement that a parameter be represented in the minimum number of
324 octets; high-order 0 octets are allowed at the front end. Parameters
325 are always right adjusted, in a field of length defined by LL. The
326 octet-order is always most-significant first, least-significant last.
327 The parameters H and K may have an optional sign bit stored in the
328 unused high-order bit of their length fields.
330 LP defines the length of the prime P. P must be an odd prime. The
331 parameters LP,P are present if and only if the flag M=1. If M=0, the
334 LF,F define an explicit field polynomial. This parameter pair is
335 present only when FMT = 1. The length of a polynomial coefficient is
336 ceiling(log2 P) bits. Coefficients are in the numerical range
337 [0,P-1]. The coefficients are packed into fixed-width fields, from
338 higher order to lower order. All coefficients must be present,
339 including any 0s and also the leading coefficient (which is required
340 to be 1). The coefficients are right justified into the octet string
341 of length specified by LF, with the low-order "constant" coefficient
342 at the right end. As a concession to storage efficiency, the higher
343 order bits of the leading coefficient may be elided, discarding high-
344 order 0 octets and reducing LF. The degree is calculated by
347 R. Schroeppel, et al [Page 6]
350 INTERNET-DRAFT ECC Keys in the DNS
353 determining the bit position of the left most 1-bit in the F data
354 (counting the right most bit as position 0), and dividing by
355 ceiling(log2 P). The division must be exact, with no remainder. In
356 this format, all of the other degree and field parameters are
357 omitted. The next parameters will be LQ,Q.
359 If FMT>=2, the degree of the field extension is specified explicitly,
360 usually along with other parameters to define the field polynomial.
362 DEG is a two octet field that defines the degree of the field
363 extension. The finite field will have P^DEG elements. DEG is
366 When FMT=2, the field polynomial is specified implicitly. No other
367 parameters are required to define the field; the next parameters
368 present will be the LQ,Q pair. The implicit field poynomial is the
369 lexicographically smallest irreducible (mod P) polynomial of the
370 correct degree. The ordering of polynomials is by highest-degree
371 coefficients first -- the leading coefficient 1 is most important,
372 and the constant term is least important. Coefficients are ordered
373 by sign-magnitude: 0 < 1 < -1 < 2 < -2 < ... The first polynomial of
374 degree D is X^D (which is not irreducible). The next is X^D+1, which
375 is sometimes irreducible, followed by X^D-1, which isn't. Assuming
376 odd P, this series continues to X^D - (P-1)/2, and then goes to X^D +
377 X, X^D + X + 1, X^D + X - 1, etc.
379 When FMT=3, the field polynomial is a binomial, X^DEG + K. P must be
380 odd. The polynomial is determined by the degree and the low order
381 term K. Of all the field parameters, only the LK,K parameters are
382 present. The high-order bit of the LK octet stores on optional sign
383 for K; if the sign bit is present, the field polynomial is X^DEG - K.
385 When FMT=4, the field polynomial is a trinomial, X^DEG + H*X^DEGH +
386 K. When P=2, the H and K parameters are implicitly 1, and are
387 omitted from the representation. Only DEG and DEGH are present; the
388 next parameters are LQ,Q. When P>2, then LH,H and LK,K are
389 specified. Either or both of LH, LK may contain a sign bit for its
392 When FMT=5, then P=2 (only). The field polynomial is the exact
393 quotient of a trinomial divided by a small polynomial, the trinomial
394 divisor. The small polynomial is right-adjusted in the two octet
395 field TRDV. DEG specifies the degree of the field. The degree of
396 TRDV is calculated from the position of the high-order 1 bit. The
397 trinomial to be divided is X^(DEG+degree(TRDV)) + X^DEGH + 1. If
398 DEGH is 0, the middle term is omitted from the trinomial. The
399 quotient must be exact, with no remainder.
401 When FMT=6, then P=2 (only). The field polynomial is a pentanomial,
402 with the degrees of the middle terms given by the three 2-octet
405 R. Schroeppel, et al [Page 7]
408 INTERNET-DRAFT ECC Keys in the DNS
411 values DEGH, DEGI, DEGJ. The polynomial is X^DEG + X^DEGH + X^DEGI +
412 X^DEGJ + 1. The values must satisfy the inequality DEG > DEGH > DEGI
415 DEGH, DEGI, DEGJ are two-octet fields that define the degree of
416 a term in a field polynomial. DEGH is present when FMT = 4,
417 5, or 6. DEGI and DEGJ are present only when FMT = 6.
419 TRDV is a two-octet right-adjusted binary polynomial of degree <
420 16. It is present only for FMT=5.
422 LH and H define the H parameter, present only when FMT=4 and P
423 is odd. The high bit of LH is an optional sign bit for H.
425 LK and K define the K parameter, present when FMT = 3 or 4, and
426 P is odd. The high bit of LK is an optional sign bit for K.
428 The remaining parameters are concerned with the elliptic curve and
429 the signature algorithm.
431 LQ defines the length of the prime Q. Q is a prime > 2^159.
433 In all 5 of the parameter pairs LA+A,LB+B,LC+C,LG+G,LY+Y, the data
434 member of the pair is an element from the finite field defined
435 earlier. The length field defines a long octet string. Field
436 elements are represented as (mod P) polynomials of degree < DEG, with
437 DEG or fewer coefficients. The coefficients are stored from left to
438 right, higher degree to lower, with the constant term last. The
439 coefficients are represented as integers in the range [0,P-1]. Each
440 coefficient is allocated an area of ceiling(log2 P) bits. The field
441 representation is right-justified; the "constant term" of the field
442 element ends at the right most bit. The coefficients are fitted
443 adjacently without regard for octet boundaries. (Example: if P=5,
444 three bits are used for each coefficient. If the field is GF[5^75],
445 then 225 bits are required for the coefficients, and as many as 29
446 octets may be needed in the data area. Fewer octets may be used if
447 some high-order coefficients are 0.) If a flag requires a field
448 element to be negated, each non-zero coefficient K is replaced with
449 P-K. To save space, 0 bits may be removed from the left end of the
450 element representation, and the length field reduced appropriately.
451 This would normally only happen with A,B,C, because the designer
452 chose curve parameters with some high-order 0 coefficients or bits.
454 If the finite field is simply (mod P), then the field elements are
455 simply numbers (mod P), in the usual right-justified notation. If
456 the finite field is GF[2^D], the field elements are the usual right-
457 justified polynomial basis representation.
463 R. Schroeppel, et al [Page 8]
466 INTERNET-DRAFT ECC Keys in the DNS
469 LA,A is the first parameter of the elliptic curve equation.
470 When P>=5, the flag A = 1 indicates A should be negated (mod
471 P). When P=2 (indicated by the flag M=0), the flag A = 1
472 indicates that the parameter pair LA,A is replaced by the two
473 octet parameter ALTA. In this case, the parameter A in the
474 curve equation is x^ALTA, where x is the field generator.
475 Parameter A often has the value 0, which may be indicated by
476 LA=0 (with no A data field), and sometimes A is 1, which may
477 be represented with LA=1 and a data field of 1, or by setting
478 the A flag and using an ALTA value of 0.
480 LB,B is the second parameter of the elliptic curve equation.
481 When P>=5, the flag B = 1 indicates B should be negated (mod
482 P). When P=2 or 3, the flag B selects an alternate curve
485 LC,C is the third parameter of the elliptic curve equation,
486 present only when P=2 (indicated by flag M=0) and flag B=1.
488 LG,G defines a point on the curve, of order Q. The W-coordinate
489 of the curve point is given explicitly; the Z-coordinate is
492 LY,Y is the user's public signing key, another curve point of
493 order Q. The W-coordinate is given explicitly; the Z-
494 coordinate is implicit. The LY,Y parameter pair is always
499 3. The Elliptic Curve Equation
501 (The coordinates of an elliptic curve point are named W,Z instead of
502 the more usual X,Y to avoid confusion with the Y parameter of the
505 The elliptic curve equation is determined by the flag octet, together
506 with information about the prime P. The primes 2 and 3 are special;
507 all other primes are treated identically.
509 If M=1, the (mod P) or GF[P^D] case, the curve equation is Z^2 = W^3
510 + A*W + B. Z,W,A,B are all numbers (mod P) or elements of GF[P^D].
511 If A and/or B is negative (i.e., in the range from P/2 to P), and
512 P>=5, space may be saved by putting the sign bit(s) in the A and B
513 bits of the flags octet, and the magnitude(s) in the parameter
516 If M=1 and P=3, the B flag has a different meaning: it specifies an
517 alternate curve equation, Z^2 = W^3 + A*W^2 + B. The middle term of
518 the right-hand-side is different. When P=3, this equation is more
521 R. Schroeppel, et al [Page 9]
524 INTERNET-DRAFT ECC Keys in the DNS
529 If M=0, the GF[2^N] case, the curve equation is Z^2 + W*Z = W^3 +
530 A*W^2 + B. Z,W,A,B are all elements of the field GF[2^N]. The A
531 parameter can often be 0 or 1, or be chosen as a single-1-bit value.
532 The flag B is used to select an alternate curve equation, Z^2 + C*Z =
533 W^3 + A*W + B. This is the only time that the C parameter is used.
537 4. How do I Compute Q, G, and Y?
539 The number of points on the curve is the number of solutions to the
540 curve equation, + 1 (for the "point at infinity"). The prime Q must
541 divide the number of points. Usually the curve is chosen first, then
542 the number of points is determined with Schoof's algorithm. This
543 number is factored, and if it has a large prime divisor, that number
546 G must be a point of order Q on the curve, satisfying the equation
548 Q * G = the point at infinity (on the elliptic curve)
550 G may be chosen by selecting a random [RFC 1750] curve point, and
551 multiplying it by (number-of-points-on-curve/Q). G must not itself
552 be the "point at infinity"; in this astronomically unlikely event, a
553 new random curve point is recalculated.
555 G is specified by giving its W-coordinate. The Z-coordinate is
556 calculated from the curve equation. In general, there will be two
557 possible Z values. The rule is to choose the "positive" value.
559 In the (mod P) case, the two possible Z values sum to P. The smaller
560 value is less than P/2; it is used in subsequent calculations. In
561 GF[P^D] fields, the highest-degree non-zero coefficient of the field
562 element Z is used; it is chosen to be less than P/2.
564 In the GF[2^N] case, the two possible Z values xor to W (or to the
565 parameter C with the alternate curve equation). The numerically
566 smaller Z value (the one which does not contain the highest-order 1
567 bit of W (or C)) is used in subsequent calculations.
569 Y is specified by giving the W-coordinate of the user's public
570 signature key. The Z-coordinate value is determined from the curve
571 equation. As with G, there are two possible Z values; the same rule
572 is followed for choosing which Z to use.
579 R. Schroeppel, et al [Page 10]
582 INTERNET-DRAFT ECC Keys in the DNS
585 During the key generation process, a random [RFC 1750] number X must
586 be generated such that 1 <= X <= Q-1. X is the private key and is
587 used in the final step of public key generation where Y is computed
590 Y = X * G (as points on the elliptic curve)
592 If the Z-coordinate of the computed point Y is wrong (i.e., Z > P/2
593 in the (mod P) case, or the high-order non-zero coefficient of Z >
594 P/2 in the GF[P^D] case, or Z sharing a high bit with W(C) in the
595 GF[2^N] case), then X must be replaced with Q-X. This will
596 correspond to the correct Z-coordinate.
600 5. Elliptic Curve SIG Resource Records
602 The signature portion of an RR RDATA area when using the EC
603 algorithm, for example in the RRSIG and SIG [RFC records] RRs is
606 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3
607 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
608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
609 | R, (length determined from LQ) .../
610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
611 | S, (length determined from LQ) .../
612 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
614 R and S are integers (mod Q). Their length is specified by the LQ
615 field of the corresponding KEY RR and can also be calculated from the
616 SIG RR's RDLENGTH. They are right justified, high-order-octet first.
617 The same conditional formula for calculating the length from LQ is
618 used as for all the other length fields above.
620 The data signed is determined as specified in [RFC 2535]. Then the
621 following steps are taken where Q, P, G, and Y are as specified in
622 the public key [Schneier]:
624 hash = SHA-1 ( data )
626 Generate random [RFC 4086] K such that 0 < K < Q. (Never sign two
627 different messages with the same K. K should be chosen from a
628 very large space: If an opponent learns a K value for a single
629 signature, the user's signing key is compromised, and a forger
630 can sign arbitrary messages. There is no harm in signing the
631 same message multiple times with the same key or different
634 R = (the W-coordinate of ( K*G on the elliptic curve )) interpreted
637 R. Schroeppel, et al [Page 11]
640 INTERNET-DRAFT ECC Keys in the DNS
643 as an integer, and reduced (mod Q). (R must not be 0. In
644 this astronomically unlikely event, generate a new random K
647 S = ( K^(-1) * (hash + X*R) ) mod Q.
649 S must not be 0. In this astronomically unlikely event, generate a
650 new random K and recalculate R and S.
652 If S > Q/2, set S = Q - S.
654 The pair (R,S) is the signature.
656 Another party verifies the signature as follows:
658 Check that 0 < R < Q and 0 < S < Q/2. If not, it can not be a
661 hash = SHA-1 ( data )
665 U1 = (hash * Sinv) mod Q.
667 U2 = (R * Sinv) mod Q.
669 (U1 * G + U2 * Y) is computed on the elliptic curve.
671 V = (the W-coordinate of this point) interpreted as an integer
674 The signature is valid if V = R.
676 The reason for requiring S < Q/2 is that, otherwise, both (R,S) and
677 (R,Q-S) would be valid signatures for the same data. Note that a
678 signature that is valid for hash(data) is also valid for
679 hash(data)+Q or hash(data)-Q, if these happen to fall in the range
680 [0,2^160-1]. It's believed to be computationally infeasible to
681 find data that hashes to an assigned value, so this is only a
682 cosmetic blemish. The blemish can be eliminated by using Q >
683 2^160, at the cost of having slightly longer signatures, 42 octets
686 We must specify how a field-element E ("the W-coordinate") is to be
687 interpreted as an integer. The field-element E is regarded as a
688 radix-P integer, with the digits being the coefficients in the
689 polynomial basis representation of E. The digits are in the ragne
690 [0,P-1]. In the two most common cases, this reduces to "the
691 obvious thing". In the (mod P) case, E is simply a residue mod P,
692 and is taken as an integer in the range [0,P-1]. In the GF[2^D]
695 R. Schroeppel, et al [Page 12]
698 INTERNET-DRAFT ECC Keys in the DNS
701 case, E is in the D-bit polynomial basis representation, and is
702 simply taken as an integer in the range [0,(2^D)-1]. For other
703 fields GF[P^D], it's necessary to do some radix conversion
708 6. Performance Considerations
710 Elliptic curve signatures use smaller moduli or field sizes than
711 RSA and DSA. Creation of a curve is slow, but not done very often.
712 Key generation is faster than RSA or DSA.
714 DNS implementations have been optimized for small transfers,
715 typically less than 512 octets including DNS overhead. Larger
716 transfers will perform correctly and and extensions have been
717 standardized to make larger transfers more efficient [RFC 2671].
718 However, it is still advisable at this time to make reasonable
719 efforts to minimize the size of RR sets stored within the DNS
720 consistent with adequate security.
724 7. Security Considerations
726 Keys retrieved from the DNS should not be trusted unless (1) they
727 have been securely obtained from a secure resolver or independently
728 verified by the user and (2) this secure resolver and secure
729 obtainment or independent verification conform to security policies
730 acceptable to the user. As with all cryptographic algorithms,
731 evaluating the necessary strength of the key is essential and
732 dependent on local policy.
734 Some specific key generation considerations are given in the body
739 8. IANA Considerations
741 The key and signature data structures defined herein correspond to
742 the value 4 in the Algorithm number field of the IANA registry
744 Assignment of meaning to the remaining ECC data flag bits or to
745 values of ECC fields outside the ranges for which meaning in
746 defined in this document requires an IETF consensus as defined in
753 R. Schroeppel, et al [Page 13]
756 INTERNET-DRAFT ECC Keys in the DNS
759 Copyright and Disclaimer
761 Copyright (C) The Internet Society 2005. This document is subject
762 to the rights, licenses and restrictions contained in BCP 78, and
763 except as set forth therein, the authors retain all their rights.
766 This document and the information contained herein are provided on
767 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
768 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND
769 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES,
770 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT
771 THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR
772 ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
811 R. Schroeppel, et al [Page 14]
814 INTERNET-DRAFT ECC Keys in the DNS
817 Informational References
819 [RFC 1034] - P. Mockapetris, "Domain names - concepts and
820 facilities", 11/01/1987.
822 [RFC 1035] - P. Mockapetris, "Domain names - implementation and
823 specification", 11/01/1987.
825 [RFC 2671] - P. Vixie, "Extension Mechanisms for DNS (EDNS0)",
828 [RFC 4033] - Arends, R., Austein, R., Larson, M., Massey, D., and
829 S. Rose, "DNS Security Introduction and Requirements", RFC 4033,
832 [RFC 4035] - Arends, R., Austein, R., Larson, M., Massey, D., and
833 S. Rose, "Protocol Modifications for the DNS Security Extensions",
834 RFC 4035, March 2005.
836 [RFC 4086] - Eastlake, D., 3rd, Schiller, J., and S. Crocker,
837 "Randomness Requirements for Security", BCP 106, RFC 4086, June
840 [Schneier] - Bruce Schneier, "Applied Cryptography: Protocols,
841 Algorithms, and Source Code in C", 1996, John Wiley and Sons
843 [Menezes] - Alfred Menezes, "Elliptic Curve Public Key
844 Cryptosystems", 1993 Kluwer.
846 [Silverman] - Joseph Silverman, "The Arithmetic of Elliptic
847 Curves", 1986, Springer Graduate Texts in mathematics #106.
853 [RFC 2119] - S. Bradner, "Key words for use in RFCs to Indicate
854 Requirement Levels", March 1997.
856 [RFC 2434] - T. Narten, H. Alvestrand, "Guidelines for Writing an
857 IANA Considerations Section in RFCs", October 1998.
859 [RFC 4034] - Arends, R., Austein, R., Larson, M., Massey, D., and
860 S. Rose, "Resource Records for the DNS Security Extensions", RFC
869 R. Schroeppel, et al [Page 15]
872 INTERNET-DRAFT ECC Keys in the DNS
879 Woodland Hills, UT 84653 USA
881 Telephone: +1-505-844-9079(w)
882 Email: rschroe@sandia.gov
885 Donald E. Eastlake 3rd
886 Motorola Laboratories
888 Milford, MA 01757 USA
890 Telephone: +1 508-786-7554 (w)
891 EMail: Donald.Eastlake@motorola.com
895 Expiration and File Name
897 This draft expires in January 2006.
899 Its file name is draft-ietf-dnsext-ecc-key-07.txt.
927 R. Schroeppel, et al [Page 16]
projects / FreeBSD / releng / 7.2.git / blob