diff options
Diffstat (limited to 'doc/draft/draft-ietf-dnsext-ecc-key-07.txt')
-rw-r--r-- | doc/draft/draft-ietf-dnsext-ecc-key-07.txt | 928 |
1 files changed, 928 insertions, 0 deletions
diff --git a/doc/draft/draft-ietf-dnsext-ecc-key-07.txt b/doc/draft/draft-ietf-dnsext-ecc-key-07.txt new file mode 100644 index 0000000..2cdcdb1 --- /dev/null +++ b/doc/draft/draft-ietf-dnsext-ecc-key-07.txt @@ -0,0 +1,928 @@ + +INTERNET-DRAFT ECC Keys in the DNS +Expires: January 2006 July 2005 + + + + Elliptic Curve KEYs in the DNS + -------- ----- ---- -- --- --- + <draft-ietf-dnsext-ecc-key-07.txt> + + Richard C. Schroeppel + Donald Eastlake 3rd + + +Status of This Document + + By submitting this Internet-Draft, each author represents that any + applicable patent or other IPR claims of which he or she is aware + have been or will be disclosed, and any of which he or she becomes + aware will be disclosed, in accordance with Section 6 of BCP 79. + + This draft is intended to be become a Proposed Standard RFC. + Distribution of this document is unlimited. Comments should be sent + to the DNS mailing list <namedroppers@ops.ietf.org>. + + Internet-Drafts are working documents of the Internet Engineering + Task Force (IETF), its areas, and its working groups. Note that + other groups may also distribute working documents as Internet- + Drafts. + + Internet-Drafts are draft documents valid for a maximum of six months + and may be updated, replaced, or obsoleted by other documents at any + time. It is inappropriate to use Internet-Drafts as reference + material or to cite them other than a "work in progress." + + The list of current Internet-Drafts can be accessed at + http://www.ietf.org/1id-abstracts.html + + The list of Internet-Draft Shadow Directories can be accessed at + http://www.ietf.org/shadow.html + + +Abstract + + The standard method for storing elliptic curve cryptographic keys and + signatures in the Domain Name System is specified. + + +Copyright Notice + + Copyright (C) The Internet Society (2005). All Rights Reserved. + + + + + +R. Schroeppel, et al [Page 1] + + +INTERNET-DRAFT ECC Keys in the DNS + + +Acknowledgement + + The assistance of Hilarie K. Orman in the production of this document + is greatfully acknowledged. + + + +Table of Contents + + Status of This Document....................................1 + Abstract...................................................1 + Copyright Notice...........................................1 + + Acknowledgement............................................2 + Table of Contents..........................................2 + + 1. Introduction............................................3 + 2. Elliptic Curve Data in Resource Records.................3 + 3. The Elliptic Curve Equation.............................9 + 4. How do I Compute Q, G, and Y?..........................10 + 5. Elliptic Curve SIG Resource Records....................11 + 6. Performance Considerations.............................13 + 7. Security Considerations................................13 + 8. IANA Considerations....................................13 + Copyright and Disclaimer..................................14 + + Informational References..................................15 + Normative Refrences.......................................15 + + Author's Addresses........................................16 + Expiration and File Name..................................16 + + + + + + + + + + + + + + + + + + + + + +R. Schroeppel, et al [Page 2] + + +INTERNET-DRAFT ECC Keys in the DNS + + +1. Introduction + + The Domain Name System (DNS) is the global hierarchical replicated + distributed database system for Internet addressing, mail proxy, and + other information. The DNS has been extended to include digital + signatures and cryptographic keys as described in [RFC 4033, 4034, + 4035]. + + This document describes how to store elliptic curve cryptographic + (ECC) keys and signatures in the DNS so they can be used for a + variety of security purposes. Familiarity with ECC cryptography is + assumed [Menezes]. + + The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", + "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this + document are to be interpreted as described in [RFC 2119]. + + + +2. Elliptic Curve Data in Resource Records + + Elliptic curve public keys are stored in the DNS within the RDATA + portions of key RRs, such as RRKEY and KEY [RFC 4034] RRs, with the + structure shown below. + + The research world continues to work on the issue of which is the + best elliptic curve system, which finite field to use, and how to + best represent elements in the field. So, representations are + defined for every type of finite field, and every type of elliptic + curve. The reader should be aware that there is a unique finite + field with a particular number of elements, but many possible + representations of that field and its elements. If two different + representations of a field are given, they are interconvertible with + a tedious but practical precomputation, followed by a fast + computation for each field element to be converted. It is perfectly + reasonable for an algorithm to work internally with one field + representation, and convert to and from a different external + representation. + + + + + + + + + + + + + + +R. Schroeppel, et al [Page 3] + + +INTERNET-DRAFT ECC Keys in the DNS + + + 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 + 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 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + |S M -FMT- A B Z| + +-+-+-+-+-+-+-+-+ + | LP | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | P (length determined from LP) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | LF | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | F (length determined from LF) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | DEG | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | DEGH | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | DEGI | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | DEGJ | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | TRDV | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + |S| LH | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | H (length determined from LH) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + |S| LK | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | K (length determined from LK) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | LQ | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Q (length determined from LQ) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | LA | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | A (length determined from LA) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | ALTA | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | LB | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | B (length determined from LB) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | LC | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | C (length determined from LC) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | LG | + + +R. Schroeppel, et al [Page 4] + + +INTERNET-DRAFT ECC Keys in the DNS + + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | G (length determined from LG) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | LY | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Y (length determined from LY) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + SMFMTABZ is a flags octet as follows: + + S = 1 indicates that the remaining 7 bits of the octet selects + one of 128 predefined choices of finite field, element + representation, elliptic curve, and signature parameters. + MFMTABZ are omitted, as are all parameters from LP through G. + LY and Y are retained. + + If S = 0, the remaining parameters are as in the picture and + described below. + + M determines the type of field underlying the elliptic curve. + + M = 0 if the field is a GF[2^N] field; + + M = 1 if the field is a (mod P) or GF[P^D] field with P>2. + + FMT is a three bit field describing the format of the field + representation. + + FMT = 0 for a (mod P) field. + > 0 for an extension field, either GF[2^D] or GF[P^D]. + The degree D of the extension, and the field polynomial + must be specified. The field polynomial is always monic + (leading coefficient 1.) + + FMT = 1 The field polynomial is given explicitly; D is implied. + + If FMT >=2, the degree D is given explicitly. + + = 2 The field polynomial is implicit. + = 3 The field polynomial is a binomial. P>2. + = 4 The field polynomial is a trinomial. + = 5 The field polynomial is the quotient of a trinomial by a + short polynomial. P=2. + = 6 The field polynomial is a pentanomial. P=2. + + Flags A and B apply to the elliptic curve parameters. + + + + + + +R. Schroeppel, et al [Page 5] + + +INTERNET-DRAFT ECC Keys in the DNS + + + A = 1 When P>=5, the curve parameter A is negated. If P=2, then + A=1 indicates that the A parameter is special. See the + ALTA parameter below, following A. The combination A=1, + P=3 is forbidden. + + B = 1 When P>=5, the curve parameter B is negated. If P=2 or 3, + then B=1 indicates an alternate elliptic curve equation is + used. When P=2 and B=1, an additional curve parameter C + is present. + + The Z bit SHOULD be set to zero on creation of an RR and MUST be + ignored when processing an RR (when S=0). + + Most of the remaining parameters are present in some formats and + absent in others. The presence or absence of a parameter is + determined entirely by the flags. When a parameter occurs, it is in + the order defined by the picture. + + Of the remaining parameters, PFHKQABCGY are variable length. When + present, each is preceded by a one-octet length field as shown in the + diagram above. The length field does not include itself. The length + field may have values from 0 through 110. The parameter length in + octets is determined by a conditional formula: If LL<=64, the + parameter length is LL. If LL>64, the parameter length is 16 times + (LL-60). In some cases, a parameter value of 0 is sensible, and MAY + be represented by an LL value of 0, with the data field omitted. A + length value of 0 represents a parameter value of 0, not an absent + parameter. (The data portion occupies 0 space.) There is no + requirement that a parameter be represented in the minimum number of + octets; high-order 0 octets are allowed at the front end. Parameters + are always right adjusted, in a field of length defined by LL. The + octet-order is always most-significant first, least-significant last. + The parameters H and K may have an optional sign bit stored in the + unused high-order bit of their length fields. + + LP defines the length of the prime P. P must be an odd prime. The + parameters LP,P are present if and only if the flag M=1. If M=0, the + prime is 2. + + LF,F define an explicit field polynomial. This parameter pair is + present only when FMT = 1. The length of a polynomial coefficient is + ceiling(log2 P) bits. Coefficients are in the numerical range + [0,P-1]. The coefficients are packed into fixed-width fields, from + higher order to lower order. All coefficients must be present, + including any 0s and also the leading coefficient (which is required + to be 1). The coefficients are right justified into the octet string + of length specified by LF, with the low-order "constant" coefficient + at the right end. As a concession to storage efficiency, the higher + order bits of the leading coefficient may be elided, discarding high- + order 0 octets and reducing LF. The degree is calculated by + + +R. Schroeppel, et al [Page 6] + + +INTERNET-DRAFT ECC Keys in the DNS + + + determining the bit position of the left most 1-bit in the F data + (counting the right most bit as position 0), and dividing by + ceiling(log2 P). The division must be exact, with no remainder. In + this format, all of the other degree and field parameters are + omitted. The next parameters will be LQ,Q. + + If FMT>=2, the degree of the field extension is specified explicitly, + usually along with other parameters to define the field polynomial. + + DEG is a two octet field that defines the degree of the field + extension. The finite field will have P^DEG elements. DEG is + present when FMT>=2. + + When FMT=2, the field polynomial is specified implicitly. No other + parameters are required to define the field; the next parameters + present will be the LQ,Q pair. The implicit field poynomial is the + lexicographically smallest irreducible (mod P) polynomial of the + correct degree. The ordering of polynomials is by highest-degree + coefficients first -- the leading coefficient 1 is most important, + and the constant term is least important. Coefficients are ordered + by sign-magnitude: 0 < 1 < -1 < 2 < -2 < ... The first polynomial of + degree D is X^D (which is not irreducible). The next is X^D+1, which + is sometimes irreducible, followed by X^D-1, which isn't. Assuming + odd P, this series continues to X^D - (P-1)/2, and then goes to X^D + + X, X^D + X + 1, X^D + X - 1, etc. + + When FMT=3, the field polynomial is a binomial, X^DEG + K. P must be + odd. The polynomial is determined by the degree and the low order + term K. Of all the field parameters, only the LK,K parameters are + present. The high-order bit of the LK octet stores on optional sign + for K; if the sign bit is present, the field polynomial is X^DEG - K. + + When FMT=4, the field polynomial is a trinomial, X^DEG + H*X^DEGH + + K. When P=2, the H and K parameters are implicitly 1, and are + omitted from the representation. Only DEG and DEGH are present; the + next parameters are LQ,Q. When P>2, then LH,H and LK,K are + specified. Either or both of LH, LK may contain a sign bit for its + parameter. + + When FMT=5, then P=2 (only). The field polynomial is the exact + quotient of a trinomial divided by a small polynomial, the trinomial + divisor. The small polynomial is right-adjusted in the two octet + field TRDV. DEG specifies the degree of the field. The degree of + TRDV is calculated from the position of the high-order 1 bit. The + trinomial to be divided is X^(DEG+degree(TRDV)) + X^DEGH + 1. If + DEGH is 0, the middle term is omitted from the trinomial. The + quotient must be exact, with no remainder. + + When FMT=6, then P=2 (only). The field polynomial is a pentanomial, + with the degrees of the middle terms given by the three 2-octet + + +R. Schroeppel, et al [Page 7] + + +INTERNET-DRAFT ECC Keys in the DNS + + + values DEGH, DEGI, DEGJ. The polynomial is X^DEG + X^DEGH + X^DEGI + + X^DEGJ + 1. The values must satisfy the inequality DEG > DEGH > DEGI + > DEGJ > 0. + + DEGH, DEGI, DEGJ are two-octet fields that define the degree of + a term in a field polynomial. DEGH is present when FMT = 4, + 5, or 6. DEGI and DEGJ are present only when FMT = 6. + + TRDV is a two-octet right-adjusted binary polynomial of degree < + 16. It is present only for FMT=5. + + LH and H define the H parameter, present only when FMT=4 and P + is odd. The high bit of LH is an optional sign bit for H. + + LK and K define the K parameter, present when FMT = 3 or 4, and + P is odd. The high bit of LK is an optional sign bit for K. + + The remaining parameters are concerned with the elliptic curve and + the signature algorithm. + + LQ defines the length of the prime Q. Q is a prime > 2^159. + + In all 5 of the parameter pairs LA+A,LB+B,LC+C,LG+G,LY+Y, the data + member of the pair is an element from the finite field defined + earlier. The length field defines a long octet string. Field + elements are represented as (mod P) polynomials of degree < DEG, with + DEG or fewer coefficients. The coefficients are stored from left to + right, higher degree to lower, with the constant term last. The + coefficients are represented as integers in the range [0,P-1]. Each + coefficient is allocated an area of ceiling(log2 P) bits. The field + representation is right-justified; the "constant term" of the field + element ends at the right most bit. The coefficients are fitted + adjacently without regard for octet boundaries. (Example: if P=5, + three bits are used for each coefficient. If the field is GF[5^75], + then 225 bits are required for the coefficients, and as many as 29 + octets may be needed in the data area. Fewer octets may be used if + some high-order coefficients are 0.) If a flag requires a field + element to be negated, each non-zero coefficient K is replaced with + P-K. To save space, 0 bits may be removed from the left end of the + element representation, and the length field reduced appropriately. + This would normally only happen with A,B,C, because the designer + chose curve parameters with some high-order 0 coefficients or bits. + + If the finite field is simply (mod P), then the field elements are + simply numbers (mod P), in the usual right-justified notation. If + the finite field is GF[2^D], the field elements are the usual right- + justified polynomial basis representation. + + + + + +R. Schroeppel, et al [Page 8] + + +INTERNET-DRAFT ECC Keys in the DNS + + + LA,A is the first parameter of the elliptic curve equation. + When P>=5, the flag A = 1 indicates A should be negated (mod + P). When P=2 (indicated by the flag M=0), the flag A = 1 + indicates that the parameter pair LA,A is replaced by the two + octet parameter ALTA. In this case, the parameter A in the + curve equation is x^ALTA, where x is the field generator. + Parameter A often has the value 0, which may be indicated by + LA=0 (with no A data field), and sometimes A is 1, which may + be represented with LA=1 and a data field of 1, or by setting + the A flag and using an ALTA value of 0. + + LB,B is the second parameter of the elliptic curve equation. + When P>=5, the flag B = 1 indicates B should be negated (mod + P). When P=2 or 3, the flag B selects an alternate curve + equation. + + LC,C is the third parameter of the elliptic curve equation, + present only when P=2 (indicated by flag M=0) and flag B=1. + + LG,G defines a point on the curve, of order Q. The W-coordinate + of the curve point is given explicitly; the Z-coordinate is + implicit. + + LY,Y is the user's public signing key, another curve point of + order Q. The W-coordinate is given explicitly; the Z- + coordinate is implicit. The LY,Y parameter pair is always + present. + + + +3. The Elliptic Curve Equation + + (The coordinates of an elliptic curve point are named W,Z instead of + the more usual X,Y to avoid confusion with the Y parameter of the + signing key.) + + The elliptic curve equation is determined by the flag octet, together + with information about the prime P. The primes 2 and 3 are special; + all other primes are treated identically. + + If M=1, the (mod P) or GF[P^D] case, the curve equation is Z^2 = W^3 + + A*W + B. Z,W,A,B are all numbers (mod P) or elements of GF[P^D]. + If A and/or B is negative (i.e., in the range from P/2 to P), and + P>=5, space may be saved by putting the sign bit(s) in the A and B + bits of the flags octet, and the magnitude(s) in the parameter + fields. + + If M=1 and P=3, the B flag has a different meaning: it specifies an + alternate curve equation, Z^2 = W^3 + A*W^2 + B. The middle term of + the right-hand-side is different. When P=3, this equation is more + + +R. Schroeppel, et al [Page 9] + + +INTERNET-DRAFT ECC Keys in the DNS + + + commonly used. + + If M=0, the GF[2^N] case, the curve equation is Z^2 + W*Z = W^3 + + A*W^2 + B. Z,W,A,B are all elements of the field GF[2^N]. The A + parameter can often be 0 or 1, or be chosen as a single-1-bit value. + The flag B is used to select an alternate curve equation, Z^2 + C*Z = + W^3 + A*W + B. This is the only time that the C parameter is used. + + + +4. How do I Compute Q, G, and Y? + + The number of points on the curve is the number of solutions to the + curve equation, + 1 (for the "point at infinity"). The prime Q must + divide the number of points. Usually the curve is chosen first, then + the number of points is determined with Schoof's algorithm. This + number is factored, and if it has a large prime divisor, that number + is taken as Q. + + G must be a point of order Q on the curve, satisfying the equation + + Q * G = the point at infinity (on the elliptic curve) + + G may be chosen by selecting a random [RFC 1750] curve point, and + multiplying it by (number-of-points-on-curve/Q). G must not itself + be the "point at infinity"; in this astronomically unlikely event, a + new random curve point is recalculated. + + G is specified by giving its W-coordinate. The Z-coordinate is + calculated from the curve equation. In general, there will be two + possible Z values. The rule is to choose the "positive" value. + + In the (mod P) case, the two possible Z values sum to P. The smaller + value is less than P/2; it is used in subsequent calculations. In + GF[P^D] fields, the highest-degree non-zero coefficient of the field + element Z is used; it is chosen to be less than P/2. + + In the GF[2^N] case, the two possible Z values xor to W (or to the + parameter C with the alternate curve equation). The numerically + smaller Z value (the one which does not contain the highest-order 1 + bit of W (or C)) is used in subsequent calculations. + + Y is specified by giving the W-coordinate of the user's public + signature key. The Z-coordinate value is determined from the curve + equation. As with G, there are two possible Z values; the same rule + is followed for choosing which Z to use. + + + + + + +R. Schroeppel, et al [Page 10] + + +INTERNET-DRAFT ECC Keys in the DNS + + + During the key generation process, a random [RFC 1750] number X must + be generated such that 1 <= X <= Q-1. X is the private key and is + used in the final step of public key generation where Y is computed + as + + Y = X * G (as points on the elliptic curve) + + If the Z-coordinate of the computed point Y is wrong (i.e., Z > P/2 + in the (mod P) case, or the high-order non-zero coefficient of Z > + P/2 in the GF[P^D] case, or Z sharing a high bit with W(C) in the + GF[2^N] case), then X must be replaced with Q-X. This will + correspond to the correct Z-coordinate. + + + +5. Elliptic Curve SIG Resource Records + + The signature portion of an RR RDATA area when using the EC + algorithm, for example in the RRSIG and SIG [RFC records] RRs is + shown below. + + 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 + 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 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | R, (length determined from LQ) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | S, (length determined from LQ) .../ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + R and S are integers (mod Q). Their length is specified by the LQ + field of the corresponding KEY RR and can also be calculated from the + SIG RR's RDLENGTH. They are right justified, high-order-octet first. + The same conditional formula for calculating the length from LQ is + used as for all the other length fields above. + + The data signed is determined as specified in [RFC 2535]. Then the + following steps are taken where Q, P, G, and Y are as specified in + the public key [Schneier]: + + hash = SHA-1 ( data ) + + Generate random [RFC 4086] K such that 0 < K < Q. (Never sign two + different messages with the same K. K should be chosen from a + very large space: If an opponent learns a K value for a single + signature, the user's signing key is compromised, and a forger + can sign arbitrary messages. There is no harm in signing the + same message multiple times with the same key or different + keys.) + + R = (the W-coordinate of ( K*G on the elliptic curve )) interpreted + + +R. Schroeppel, et al [Page 11] + + +INTERNET-DRAFT ECC Keys in the DNS + + + as an integer, and reduced (mod Q). (R must not be 0. In + this astronomically unlikely event, generate a new random K + and recalculate R.) + + S = ( K^(-1) * (hash + X*R) ) mod Q. + + S must not be 0. In this astronomically unlikely event, generate a + new random K and recalculate R and S. + + If S > Q/2, set S = Q - S. + + The pair (R,S) is the signature. + + Another party verifies the signature as follows: + + Check that 0 < R < Q and 0 < S < Q/2. If not, it can not be a + valid EC sigature. + + hash = SHA-1 ( data ) + + Sinv = S^(-1) mod Q. + + U1 = (hash * Sinv) mod Q. + + U2 = (R * Sinv) mod Q. + + (U1 * G + U2 * Y) is computed on the elliptic curve. + + V = (the W-coordinate of this point) interpreted as an integer + and reduced (mod Q). + + The signature is valid if V = R. + + The reason for requiring S < Q/2 is that, otherwise, both (R,S) and + (R,Q-S) would be valid signatures for the same data. Note that a + signature that is valid for hash(data) is also valid for + hash(data)+Q or hash(data)-Q, if these happen to fall in the range + [0,2^160-1]. It's believed to be computationally infeasible to + find data that hashes to an assigned value, so this is only a + cosmetic blemish. The blemish can be eliminated by using Q > + 2^160, at the cost of having slightly longer signatures, 42 octets + instead of 40. + + We must specify how a field-element E ("the W-coordinate") is to be + interpreted as an integer. The field-element E is regarded as a + radix-P integer, with the digits being the coefficients in the + polynomial basis representation of E. The digits are in the ragne + [0,P-1]. In the two most common cases, this reduces to "the + obvious thing". In the (mod P) case, E is simply a residue mod P, + and is taken as an integer in the range [0,P-1]. In the GF[2^D] + + +R. Schroeppel, et al [Page 12] + + +INTERNET-DRAFT ECC Keys in the DNS + + + case, E is in the D-bit polynomial basis representation, and is + simply taken as an integer in the range [0,(2^D)-1]. For other + fields GF[P^D], it's necessary to do some radix conversion + arithmetic. + + + + 6. Performance Considerations + + Elliptic curve signatures use smaller moduli or field sizes than + RSA and DSA. Creation of a curve is slow, but not done very often. + Key generation is faster than RSA or DSA. + + DNS implementations have been optimized for small transfers, + typically less than 512 octets including DNS overhead. Larger + transfers will perform correctly and and extensions have been + standardized to make larger transfers more efficient [RFC 2671]. + However, it is still advisable at this time to make reasonable + efforts to minimize the size of RR sets stored within the DNS + consistent with adequate security. + + + + 7. Security Considerations + + Keys retrieved from the DNS should not be trusted unless (1) they + have been securely obtained from a secure resolver or independently + verified by the user and (2) this secure resolver and secure + obtainment or independent verification conform to security policies + acceptable to the user. As with all cryptographic algorithms, + evaluating the necessary strength of the key is essential and + dependent on local policy. + + Some specific key generation considerations are given in the body + of this document. + + + + 8. IANA Considerations + + The key and signature data structures defined herein correspond to + the value 4 in the Algorithm number field of the IANA registry + + Assignment of meaning to the remaining ECC data flag bits or to + values of ECC fields outside the ranges for which meaning in + defined in this document requires an IETF consensus as defined in + [RFC 2434]. + + + + + +R. Schroeppel, et al [Page 13] + + +INTERNET-DRAFT ECC Keys in the DNS + + + Copyright and Disclaimer + + Copyright (C) The Internet Society 2005. This document is subject + to the rights, licenses and restrictions contained in BCP 78, and + except as set forth therein, the authors retain all their rights. + + + This document and the information contained herein are provided on + an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE + REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND + THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT + THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR + ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A + PARTICULAR PURPOSE. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +R. Schroeppel, et al [Page 14] + + +INTERNET-DRAFT ECC Keys in the DNS + + + Informational References + + [RFC 1034] - P. Mockapetris, "Domain names - concepts and + facilities", 11/01/1987. + + [RFC 1035] - P. Mockapetris, "Domain names - implementation and + specification", 11/01/1987. + + [RFC 2671] - P. Vixie, "Extension Mechanisms for DNS (EDNS0)", + August 1999. + + [RFC 4033] - Arends, R., Austein, R., Larson, M., Massey, D., and + S. Rose, "DNS Security Introduction and Requirements", RFC 4033, + March 2005. + + [RFC 4035] - Arends, R., Austein, R., Larson, M., Massey, D., and + S. Rose, "Protocol Modifications for the DNS Security Extensions", + RFC 4035, March 2005. + + [RFC 4086] - Eastlake, D., 3rd, Schiller, J., and S. Crocker, + "Randomness Requirements for Security", BCP 106, RFC 4086, June + 2005. + + [Schneier] - Bruce Schneier, "Applied Cryptography: Protocols, + Algorithms, and Source Code in C", 1996, John Wiley and Sons + + [Menezes] - Alfred Menezes, "Elliptic Curve Public Key + Cryptosystems", 1993 Kluwer. + + [Silverman] - Joseph Silverman, "The Arithmetic of Elliptic + Curves", 1986, Springer Graduate Texts in mathematics #106. + + + + Normative Refrences + + [RFC 2119] - S. Bradner, "Key words for use in RFCs to Indicate + Requirement Levels", March 1997. + + [RFC 2434] - T. Narten, H. Alvestrand, "Guidelines for Writing an + IANA Considerations Section in RFCs", October 1998. + + [RFC 4034] - Arends, R., Austein, R., Larson, M., Massey, D., and + S. Rose, "Resource Records for the DNS Security Extensions", RFC + 4034, March 2005. + + + + + + + +R. Schroeppel, et al [Page 15] + + +INTERNET-DRAFT ECC Keys in the DNS + + + Author's Addresses + + Rich Schroeppel + 500 S. Maple Drive + Woodland Hills, UT 84653 USA + + Telephone: +1-505-844-9079(w) + Email: rschroe@sandia.gov + + + Donald E. Eastlake 3rd + Motorola Laboratories + 155 Beaver Street + Milford, MA 01757 USA + + Telephone: +1 508-786-7554 (w) + EMail: Donald.Eastlake@motorola.com + + + + Expiration and File Name + + This draft expires in January 2006. + + Its file name is draft-ietf-dnsext-ecc-key-07.txt. + + + + + + + + + + + + + + + + + + + + + + + + + + + +R. Schroeppel, et al [Page 16] + |