idnits 2.17.1 

draft-jivsov-ecc-compact-00.txt:

  Checking boilerplate required by RFC 5378 and the IETF Trust (see
  https://trustee.ietf.org/license-info):
  ----------------------------------------------------------------------------

     No issues found here.

  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 and authors Copyright Line does not
     match the current year

  -- The document date (December 10, 2012) is 4154 days in the past.  Is this
     intentional?


  Checking references for intended status: Informational
  ----------------------------------------------------------------------------

     No issues found here.

     Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--).

     Run idnits with the --verbose option for more detailed information about
     the items above.
--------------------------------------------------------------------------------


2	Network Workign Group                                          A. Jivsov
3	Internet-Draft                                      Symantec Corporation
4	Intended status: Informational                         December 10, 2012
5	Expires: June 13, 2013

7	           Compact representation of an elliptic curve point
8	                      draft-jivsov-ecc-compact-00

10	Abstract

12	   This document defines a format for efficient storage representation
13	   of an elliptic curve point over prime fields, suitable for use with
14	   any IETF format or protocol.

16	Status of this Memo

18	   This Internet-Draft is submitted in full conformance with the
19	   provisions of BCP 78 and BCP 79.

21	   Internet-Drafts are working documents of the Internet Engineering
22	   Task Force (IETF).  Note that other groups may also distribute
23	   working documents as Internet-Drafts.  The list of current Internet-
24	   Drafts is at http://datatracker.ietf.org/drafts/current/.

26	   Internet-Drafts are draft documents valid for a maximum of six months
27	   and may be updated, replaced, or obsoleted by other documents at any
28	   time.  It is inappropriate to use Internet-Drafts as reference
29	   material or to cite them other than as "work in progress."

31	   This Internet-Draft will expire on June 13, 2013.

33	Copyright Notice

35	   Copyright (c) 2012 IETF Trust and the persons identified as the
36	   document authors.  All rights reserved.

38	   This document is subject to BCP 78 and the IETF Trust's Legal
39	   Provisions Relating to IETF Documents
40	   (http://trustee.ietf.org/license-info) in effect on the date of
41	   publication of this document.  Please review these documents
42	   carefully, as they describe your rights and restrictions with respect
43	   to this document.  Code Components extracted from this document must
44	   include Simplified BSD License text as described in Section 4.e of
45	   the Trust Legal Provisions and are provided without warranty as
46	   described in the Simplified BSD License.

48	Table of Contents

50	   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
51	   2.  Conventions used in this document  . . . . . . . . . . . . . .  3
52	   3.  Overview of the compact representation in IETF protocols . . .  3
53	   4.  The definition of the compact representation . . . . . . . . .  4
54	     4.1.  Encoding and decoding of an elliptic curve point . . . . .  5
55	     4.2.  The algorithms to generate a key pair  . . . . . . . . . .  5
56	       4.2.1.  The black box key generation algorithm . . . . . . . .  6
57	       4.2.2.  The deterministic key generation algorithm . . . . . .  6
58	     4.3.  The efficient square root algorithm for p=4*k+3  . . . . .  7
59	   5.  Interoperability considerations  . . . . . . . . . . . . . . .  7
60	   6.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . .  8
61	   7.  Security Considerations  . . . . . . . . . . . . . . . . . . .  8
62	   8.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
63	     8.1.  Normative References . . . . . . . . . . . . . . . . . . . 10
64	     8.2.  Informative References . . . . . . . . . . . . . . . . . . 10
65	   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 11

67	1.  Introduction

69	   The National Security Agency (NSA) of the United States specifies
70	   elliptic curve cryptography (ECC) for use in its [SuiteB] set of
71	   algorithms.  The NIST elliptic curves over the prime fields
72	   [FIPS-186], which include [SuiteB] curves, or the Brainpool curves
73	   [RFC5639] are the examples of curves over prime fields.

75	   This document provides an efficient format for compact representation
76	   of a point on an elliptic curve over a prime field.  It is intended
77	   as an open format that other IETF protocols can rely on to minimize
78	   space required to store an ECC point.  This document complements the
79	   [RFC6090] with the on-the-wire definition of an ECC point.

81	   One of the benefits of the ECC is the small size of field elements.
82	   The compact representation reduces the encoded size of an ECC element
83	   in half, which can be a substantial saving in cases such as
84	   encryption of a short message sent to multiple recipients.

86	2.  Conventions used in this document

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	3.  Overview of the compact representation in IETF protocols

94	   IETF protocols often use the [SEC1] representation of a point on an
95	   elliptic curve, which is a sequence of the following fields:

97	   Field  Description
98	   ------ --------------------------------------------------------------
99	   B0     {02, 03, 04}, where 02 or 03 represent a compressed point (x
100	          only), while 04 represents a complete point (x,y)
101	   X      x coordinate of a point
102	   Y      y coordinate of a point, optional (present only for B0=04)

104	                         SEC1 point representation

106	   The [SEC1] is an example of a general-purpose elliptic curve point
107	   compression.  The idea behind these methods is the following:

109	   o  For the given point P=(x,y) the y coordinate can be derived from x
110	      by solving the corresponding equation of the ECC.

112	   o  There are two possible y coordinates for any x of a given P

114	   o  The either of the two possibilities for y is encoded in some way
115	      in the compressed representation

117	   There are a few undesirable properties of the above representation:

119	   o  The requirement to store one bit to identify the 'y' means that
120	      the whole byte is required.

122	   o  For most well-known elliptic curves the extra byte removes the
123	      power of two alignment for the encoded point.

125	   o  The requirement for the balanced security calls for the ECC curve
126	      size to be equal the hash output size, yet the storage length of
127	      the ECC point is equal to the hash output size + 1.

129	   o  The encoded point is not a multi-precision integer, but a
130	      structured sequence of bytes.  For example, special wording is
131	      required to define the encoding of the [FIPS-186] P-521 to clarify
132	      how odd number of bits for x and y, or a bit representing y, are
133	      packed into bytes.

135	   o  Some protocols, such as ECDH, don't depend on the exact value of
136	      the y.  It is unnecessary to track the precise point P=(x,y) in
137	      such protocols.

139	4.  The definition of the compact representation

141	   This document is an improvement to the idea by [Miller] to not
142	   transmit the y coordinate of an ECC point in the elliptic curve
143	   Diffie-Hellman (ECDH) protocol.

145	   We will use the following notations for the ECC point Q and the
146	   features of the corresponding elliptic curve:

148	      Q = k*G, where

150	      Q = (x,y) is the point on an elliptic curve (the canonical
151	      represenation)

153	      k - the private key (a scalar)

155	      G - the elliptic curve generator point

157	      y^2 = x^3 + a*x + b is the standard Weierstrass equation linking x
158	      and y
159	      p - the order of the underlying finite field to which x and y
160	      belong

162	      Ord - the order of the elliptic curve field, i.e. the number of
163	      points on the curve ( Ord*G = O, where O is the identity element )

165	   Q is a point that we need to represent in the compact form.  The
166	   integer operations considered in this document are performed modulo
167	   prime p and "(mod p)" is assumed in every formula with x and y.

169	   The steps to create and interpret the compact representation of a
170	   point are described next.  A special key generation algorithm is
171	   needed to make them possible, defined later in Section 4.2.

173	4.1.  Encoding and decoding of an elliptic curve point

175	   Encoding:  Given the canonical representation of Q=(x,y), return the
176	        x as the compact representation.

178	   Decoding:  Given the compact representation of Q, return canonical
179	        representation of Q=(x,y) as follows:

181	        1.   y' = sqrt( x^3 + a*x + b ), where y'>0

183	        2.   y = min(y',p-y')

185	        3.   Q=(x,y) is the canonical representation of the point

187	   Recall that the x is an integer in the underlying finite field.  Its
188	   precise encoding SHOULD be consistent with encoding of other multi-
189	   precision integers in the application, for example, it would be the
190	   same encoding as used for the r or s integer that is a part of the
191	   DSA signature and it is typically a sequence of big-endian bytes.

193	   The efficient algorithm to recover y for [SuiteB] or the Brainpool
194	   curves [RFC5639], among others, is given in Section 4.3.

196	   min(y,p-y) can be calculated with the help of the pre-calculated
197	   value p2=(p-1)/2. min(y,p-y) is y if y<p2 and p-y otherwise.

199	   The efficient encoding and decoding algorithms are possible with the
200	   special key generation algorithm, defined next.

202	4.2.  The algorithms to generate a key pair

204	   This document specifies two algorithms, called the "black box" and
205	   the "deterministic" key generation algorithms, to generate a key pair
206	   {k, Q=k*G=(x,y)}, where k is the private key and Q=(x,y) is the
207	   public key.  A key pair generated according to the requirements in
208	   this section is called a compliant key pair, and the public key of
209	   such a key pair -- a compliant public key.  A compliant public key
210	   Q=(x,y) allows compact representation as x, as defined in
211	   Section 4.1.

213	   Both key generation algorithms can be built with any general purpose
214	   key generation algorithm which would be needed in any ECC
215	   implementation that generates keys, regardless of the support for any
216	   method defined in this document.  Such a general purpose key
217	   generation algorithm is referred in this section as "KG".

219	   The black box algorithm works in scenarios when the KG doesn't allow
220	   any adjustments to the private key.  The disadvantage of this
221	   algorithm is that multiple KGs may be needed to generate a single key
222	   pair {k, Q}.  The deterministic algorithm is similar, except that it
223	   is allowed to perform a simple and fast modification to the private
224	   key after the KG.  The advantage of the second algorithm is
225	   performance, in particular, the guarantee that only a single KG is
226	   needed.

228	4.2.1.  The black box key generation algorithm

230	   The following algorithm calculates a key pair {k, Q=k*G=(x,y)}, where
231	   k is the private key and Q=(x,y) is the public key.

233	   Black box generation:

235	        1.   Generate a key pair {k, Q=k*G=(x,y)} with KG

237	        2.   if( y != min(y,p-y) ) goto step 1

239	        3.   output {k, Q=(x,y)} as a key pair

241	   Note that the step 1 is a general purpose key generation algorithm,
242	   such as an algorithm compliant with [NIST-SP800-133].  Step 1 assumes
243	   neither changes to existing key generation methods nor access to the
244	   private key in clear.

246	   The expected number of iterations in the loop in the above algorithm
247	   is 2.  The step 2 is not needed for the ECDH keys.

249	4.2.2.  The deterministic key generation algorithm

251	   The following algorithm calculates a key pair {k, Q=k*G=(x,y)}, where
252	   k is the private key and Q=(x,y) is the public key.

254	   Deterministic generation:

256	        1.   Generate a key pair {k, Q=k*G=(x,y)} with KG

258	        2.   if( y != min(y,p-y) ) k = Ord - k

260	        3.   output {k, Q=(x,y)} as a key pair

262	   The step 2 is not needed for the ECDH keys.

264	4.3.  The efficient square root algorithm for p=4*k+3

266	   When p = 4*k+3, as is the case of [SuiteB] the Brainpool curves
267	   [RFC5639], there is an efficient square root algorithm to recover the
268	   y, as follows:

270	      Given the compact representation of Q as x,

272	      y2 = x^3 + a*x + b

274	      y' = y2^((p+1)/4)

276	      y = min(y',p-y')

278	      Q=(x,y) is the canonical representation of the point

280	   See [Lehmer] for details.

282	5.  Interoperability considerations

284	   The compact representation described in this document allows two-
285	   phase introduction.

287	   First, key pairs must be generated as defined in Section 4.2 to allow
288	   compact representation.  However, no changes to existing systems are
289	   needed to use these keys.  This allows safe deployment of the new key
290	   generation and decoding of compact representation.

292	   Finally, the encoding of public keys in the new compact
293	   representation format can be enabled after there is confidence in the
294	   universal support of new compact representation.  This event would
295	   not need to change any private key material, only public key
296	   representation.

298	   The above two phases can be implemented at once for new formats.

300	   Most ECC cryptographic protocols, such as ECDH [NIST-SP800-56A] or
301	   ECDSA [FIPS-186], are intended to work with persistently stored
302	   public keys that are generated as fresh key pairs, as opposed to some
303	   derivation function that transforms an ECC point.  The algorithm
304	   described in Section 4.2 is possible in all these cases.  In
305	   particular, the algorithm in Section 4.2 will even work for secure
306	   devices that never reveal the private key, such as smartcards or
307	   Hardware Security Modules.  A public key that is generated according
308	   to the Section 4.2 can be used without limitations in existing
309	   protocols that use ECC points encoded in other ways, such as [SEC1],
310	   with compression or not, with the added advantage that the keys
311	   generated according to the method in Section 4.2 will allow the
312	   Section 4.1 encoding.

314	6.  IANA Considerations

316	   This document defines the low-level format that may be suitable for a
317	   wide range of applications.  However, it is responsibility of the
318	   application that adopts this format to define the IDs that will
319	   enable the ECC compact point representation in that application.

321	   A new ID may not be always necessary.  For example, an application
322	   that currently allows the [SEC1] encoding may allow the compact
323	   representation defined in this document as an extension to the [SEC1]
324	   as follows.  Consider the encoding of a compressed [FIPS-186] P-256
325	   point, for example.  The [SEC1] compressed representation of a P-256
326	   point will always occupy exactly 33 bytes.  On the other hand, the
327	   compact representation defined in this document will never exceed 32
328	   bytes (it may occupy fewer that 32 bytes when the most significant
329	   byte has happened to be zero).  This size will allow reliable
330	   discrimination between two encoding formats.

332	7.  Security Considerations

334	   The key pair generation process in Section 4.2 excludes exactly half
335	   of the points on the elliptic curve.  What is left is the subset of
336	   points suitable for compact representation.  The filtering of points
337	   is based on a public criteria that are applied to the public output
338	   of the ECC one-way function.

340	   The set of Ord points on the elliptic curve can be subdivided as
341	   follows.  First, remove the point O, which leaves Ord-1 points.  Of
342	   these points there are exactly (Ord-1)/2 points that have unique x
343	   coordinate.  This document specifies a method to form the (Ord-1)/2
344	   of points, each having a unique x coordinate.  These points are
345	   called compliant public keys in Section 4.2.

347	   For any two public keys P=(x,y) and P=(x,y') there is up to one bit
348	   of entropy in y' v.s. y and this information is public.  This bit of
349	   entropy doesn't contribute to the difficulty of the underlying hard
350	   problem of the ECC: the elliptic curve discrete logarithm problem
351	   (ECDLP).

353	   It will be shown next that breaking the ECDLP with a key generated
354	   according to Section 4.2 is not easier than breaking the ECDLP with a
355	   key obtained through a standard key generation algorithm, referred to
356	   as the KG algorithm in the Section 4.2.

358	   Let us assume that there is an algorithm A that solves the ECDLP for
359	   the KG.  The algorithm A can be transformed into the algorithm A' as
360	   follows.

362	   o  If P=(x,y) is a compliant public key, the ECDLP is solved with A
363	      for the point (x,y): the result is k, such that k*G=(x,y)

365	   o  If P=(x,y) is not a compliant public key, the ECDLP is solved with
366	      A for the point (x,p-y); assuming the result produced by A is k,
367	      the result produced by A' is set to (Ord-k).  Note that (Ord-k)*G
368	      = (x,p).

370	   A' is equivalent to A. The complexity of one additional substraction
371	   in the prime field is negligible even to the complexity of a single
372	   elliptic curve addition.  Observe that A' works on all public keys by
373	   performing the actual work only on compliant public keys.

375	   If we now consider only the compliant public keys, which cuts the
376	   number of points in half, we observe that the ECDLP solving algorithm
377	   A' doesn't get to break fewer public keys.  This concludes the proof.

379	   The same result can be observed based on the details of the current
380	   state of the art attacks on the ECDLP.  These attacks use Pollard's
381	   rho algorithm, which uses the collision search in the sequence(s) of
382	   generated points with the goal to produce the points P1=(x1,y1) and
383	   P2=(x2,y2), such that x1=x2 and y1=y2.  The match in the x coordinate
384	   is the sufficient event for the successful attack.  After this event
385	   has ocurred, the sequence(s) that led to x1=x2 collision can be
386	   adjusted in a constant number of steps to ensure that y1=y2, if this
387	   is not already the case.  Furthermore, collision search requires the
388	   storage of candidates for the collision.  It's wasteful to store
389	   (x,y) v.s. storing x and only calculating y when the collision in x
390	   is detected.  Thus, the ECDLP attack does not benefit from the
391	   unpredictability of the y.

393	   Finally, note that a common design feature of an ECDH-based system is
394	   not to depend on the y coordinate, such as the one defined in the

396	   [NIST-SP800-56A].  Thus, the security of the system is unaffected if
397	   we fix either of the two possibilities for the point with the given x
398	   coordinate.

400	8.  References

402	8.1.  Normative References

404	   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
405	              Requirement Levels", BCP 14, RFC 2119, March 1997.

407	8.2.  Informative References

409	   [FIPS-186]
410	              National Institute of Standards and Technology, "Digital
411	              Signature Standard (DSS)", FIPS 186-3, June 2009,
412	              <http://csrc.nist.gov/publications/PubsSPs.html>.

414	   [Lehmer]   Lehmer, D., "Computer technology applied to the theory of
415	              numbers", 1969.

417	   [Miller]   Miller, V., "Use of elliptic curves in cryptography",
418	              Proceedings Lecture notes in computer sciences; 218 on
419	              Advances in cryptology -- CRYPTO 85, June 1986.

421	   [NIST-SP800-133]
422	              National Institute of Standards and Technology,
423	              "Recommendation for Cryptographic Key Generation", SP 800-
424	              133, November 2012,
425	              <http://csrc.nist.gov/publications/PubsSPs.html>.

427	   [NIST-SP800-56A]
428	              National Institute of Standards and Technology,
429	              "Recommendation for Pair-Wise Key Establishment Schemes
430	              Using Discrete Logarithm Cryptography", SP 800-56A
431	              Revision 1, March 2007,
432	              <http://csrc.nist.gov/publications/PubsSPs.html>.

434	   [RFC5639]  Lochter, M. and J. Merkle, "Elliptic Curve Cryptography
435	              (ECC) Brainpool Standard Curves and Curve Generation",
436	              RFC 5639, March 2010.

438	   [RFC6090]  McGrew, D., Igoe, K., and M. Salter, "Fundamental Elliptic
439	              Curve Cryptography Algorithms", RFC 6090, February 2011.

441	   [SEC1]     STANDARDS FOR EFFICIENT CRYPTOGRAPHY, "SEC 1: Elliptic
442	              Curve Cryptography", September 2000, <www.secg.org/
443	              collateral/sec1_final.pdf>.

445	   [SuiteB]   National Security Agency, "NSA Suite B Cryptography",
446	              March 2010,
447	              <http://www.nsa.gov/ia/programs/suiteb_cryptography/>.

449	Author's Address

451	   Andrey Jivsov
452	   Symantec Corporation

454	   Email: openpgp@brainhub.org