draft-ietf-dnsext-ecc-key-03.txt

bind-3.2.

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. 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 KEY RR sets stored within the DNS
   consistent with adequate security.  Keep in mind that in a secure
   zone, an authenticating SIG RRset will also be returned.



6. Security Considerations

   Many of the general security consideration in [RFC 2535] apply.  Some
   specific key generation considerations are given above.  Of course,
   the elliptic curve key stored in the DNS for an entity should not be
   trusted unless it has been obtain via a trusted DNS resolver that
   vouches for its security or unless the application using the key has
   done a similar authentication.



7. IANA Considerations

   Assignment of meaning to the remaining ECC KEY 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].

   This specification uses algorithm number 4 for DNS elliptic curve KEY


R. Schroeppel, et al                                           [Page 11]


INTERNET-DRAFT                                       ECC Keys in the DNS


   RRs that was reserved for this purpose in [RFC 2535].  An elliptic
   curve (algorithm = 4) SIG RR is not defined. Assignment of a meaning
   to it requires an IETF Standards action.

















































R. Schroeppel, et al                                           [Page 12]


INTERNET-DRAFT                                       ECC Keys in the DNS


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 1750] - D. Eastlake, S. Crocker, J. Schiller, "Randomness
   Recommendations for Security", 12/29/1994.

   [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 2535] -  D. Eastlake,"Domain Name System Security Extensions",
   March 1999.

   [RFC 2671] - P. Vixie, "Extension Mechanisms for DNS (EDNS0)", August
   1999.

   [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.





















R. Schroeppel, et al                                           [Page 13]


INTERNET-DRAFT                                       ECC Keys in the DNS


Authors' Addresses

   Rich Schroeppel
   500 S. Maple Drive
   Woodland Hills, UT 84653 USA

   Telephone:   [phone](h)
                1-505-844-9079(w)
   Email:       [e-mail]
                [e-mail]


   Donald E. Eastlake 3rd
   Motorola
   155 Beaver Street
   Milford, MA 01757 USA

   Telephone:   [phone] (h)
                [phone] (w)
   FAX:         [phone] (w)
   EMail:       [e-mail]



Expiration and File Name

   This draft expires in June 2003.

   Its file name is draft-ietf-dnsext-ecc-key-03.txt.























R. Schroeppel, et al                                           [Page 14]