PolarSSL v1.3.2
ecp.c
Go to the documentation of this file.
1 /*
2  * Elliptic curves over GF(p)
3  *
4  * Copyright (C) 2006-2013, Brainspark B.V.
5  *
6  * This file is part of PolarSSL (http://www.polarssl.org)
7  * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
8  *
9  * All rights reserved.
10  *
11  * This program is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation; either version 2 of the License, or
14  * (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License along
22  * with this program; if not, write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24  */
25 
26 /*
27  * References:
28  *
29  * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
30  * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
31  * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
32  * RFC 4492 for the related TLS structures and constants
33  *
34  * [1] OKEYA, Katsuyuki and TAKAGI, Tsuyoshi. The width-w NAF method provides
35  * small memory and fast elliptic scalar multiplications secure against
36  * side channel attacks. In : Topics in Cryptology—CT-RSA 2003. Springer
37  * Berlin Heidelberg, 2003. p. 328-343.
38  * <http://rd.springer.com/chapter/10.1007/3-540-36563-X_23>.
39  *
40  * [2] CORON, Jean-Sébastien. Resistance against differential power analysis
41  * for elliptic curve cryptosystems. In : Cryptographic Hardware and
42  * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
43  * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
44  */
45 
46 #include "polarssl/config.h"
47 
48 #if defined(POLARSSL_ECP_C)
49 
50 #include "polarssl/ecp.h"
51 
52 #if defined(POLARSSL_MEMORY_C)
53 #include "polarssl/memory.h"
54 #else
55 #define polarssl_malloc malloc
56 #define polarssl_free free
57 #endif
58 
59 #include <limits.h>
60 #include <stdlib.h>
61 
62 #if defined(_MSC_VER) && !defined(inline)
63 #define inline _inline
64 #else
65 #if defined(__ARMCC_VERSION) && !defined(inline)
66 #define inline __inline
67 #endif /* __ARMCC_VERSION */
68 #endif /*_MSC_VER */
69 
70 #if defined(POLARSSL_SELF_TEST)
71 /*
72  * Counts of point addition and doubling operations.
73  * Used to test resistance of point multiplication to simple timing attacks.
74  */
75 unsigned long add_count, dbl_count;
76 #endif
77 
78 /*
79  * List of supported curves:
80  * - internal ID
81  * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
82  * - size in bits
83  * - readable name
84  */
85 const ecp_curve_info ecp_supported_curves[] =
86 {
87 #if defined(POLARSSL_ECP_DP_BP512R1_ENABLED)
88  { POLARSSL_ECP_DP_BP512R1, 28, 512, "brainpool512r1" },
89 #endif
90 #if defined(POLARSSL_ECP_DP_BP384R1_ENABLED)
91  { POLARSSL_ECP_DP_BP384R1, 27, 384, "brainpool384r1" },
92 #endif
93 #if defined(POLARSSL_ECP_DP_BP256R1_ENABLED)
94  { POLARSSL_ECP_DP_BP256R1, 26, 256, "brainpool256r1" },
95 #endif
96 #if defined(POLARSSL_ECP_DP_SECP521R1_ENABLED)
97  { POLARSSL_ECP_DP_SECP521R1, 25, 521, "secp521r1" },
98 #endif
99 #if defined(POLARSSL_ECP_DP_SECP384R1_ENABLED)
100  { POLARSSL_ECP_DP_SECP384R1, 24, 384, "secp384r1" },
101 #endif
102 #if defined(POLARSSL_ECP_DP_SECP256R1_ENABLED)
103  { POLARSSL_ECP_DP_SECP256R1, 23, 256, "secp256r1" },
104 #endif
105 #if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED)
106  { POLARSSL_ECP_DP_SECP224R1, 21, 224, "secp224r1" },
107 #endif
108 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
109  { POLARSSL_ECP_DP_SECP192R1, 19, 192, "secp192r1" },
110 #endif
111  { POLARSSL_ECP_DP_NONE, 0, 0, NULL },
112 };
113 
114 /*
115  * List of supported curves and associated info
116  */
117 const ecp_curve_info *ecp_curve_list( void )
118 {
119  return ecp_supported_curves;
120 }
121 
122 /*
123  * Get the curve info for the internal identifer
124  */
126 {
127  const ecp_curve_info *curve_info;
128 
129  for( curve_info = ecp_curve_list();
130  curve_info->grp_id != POLARSSL_ECP_DP_NONE;
131  curve_info++ )
132  {
133  if( curve_info->grp_id == grp_id )
134  return( curve_info );
135  }
136 
137  return( NULL );
138 }
139 
140 /*
141  * Get the curve info from the TLS identifier
142  */
143 const ecp_curve_info *ecp_curve_info_from_tls_id( uint16_t tls_id )
144 {
145  const ecp_curve_info *curve_info;
146 
147  for( curve_info = ecp_curve_list();
148  curve_info->grp_id != POLARSSL_ECP_DP_NONE;
149  curve_info++ )
150  {
151  if( curve_info->tls_id == tls_id )
152  return( curve_info );
153  }
154 
155  return( NULL );
156 }
157 
158 /*
159  * Initialize (the components of) a point
160  */
161 void ecp_point_init( ecp_point *pt )
162 {
163  if( pt == NULL )
164  return;
165 
166  mpi_init( &pt->X );
167  mpi_init( &pt->Y );
168  mpi_init( &pt->Z );
169 }
170 
171 /*
172  * Initialize (the components of) a group
173  */
174 void ecp_group_init( ecp_group *grp )
175 {
176  if( grp == NULL )
177  return;
178 
179  memset( grp, 0, sizeof( ecp_group ) );
180 }
181 
182 /*
183  * Initialize (the components of) a key pair
184  */
185 void ecp_keypair_init( ecp_keypair *key )
186 {
187  if ( key == NULL )
188  return;
189 
190  ecp_group_init( &key->grp );
191  mpi_init( &key->d );
192  ecp_point_init( &key->Q );
193 }
194 
195 /*
196  * Unallocate (the components of) a point
197  */
198 void ecp_point_free( ecp_point *pt )
199 {
200  if( pt == NULL )
201  return;
202 
203  mpi_free( &( pt->X ) );
204  mpi_free( &( pt->Y ) );
205  mpi_free( &( pt->Z ) );
206 }
207 
208 /*
209  * Unallocate (the components of) a group
210  */
211 void ecp_group_free( ecp_group *grp )
212 {
213  size_t i;
214 
215  if( grp == NULL )
216  return;
217 
218  mpi_free( &grp->P );
219  mpi_free( &grp->A );
220  mpi_free( &grp->B );
221  ecp_point_free( &grp->G );
222  mpi_free( &grp->N );
223 
224  if( grp->T != NULL )
225  {
226  for( i = 0; i < grp->T_size; i++ )
227  ecp_point_free( &grp->T[i] );
228  polarssl_free( grp->T );
229  }
230 
231  memset( grp, 0, sizeof( ecp_group ) );
232 }
233 
234 /*
235  * Unallocate (the components of) a key pair
236  */
237 void ecp_keypair_free( ecp_keypair *key )
238 {
239  if ( key == NULL )
240  return;
241 
242  ecp_group_free( &key->grp );
243  mpi_free( &key->d );
244  ecp_point_free( &key->Q );
245 }
246 
247 /*
248  * Copy the contents of a point
249  */
250 int ecp_copy( ecp_point *P, const ecp_point *Q )
251 {
252  int ret;
253 
254  MPI_CHK( mpi_copy( &P->X, &Q->X ) );
255  MPI_CHK( mpi_copy( &P->Y, &Q->Y ) );
256  MPI_CHK( mpi_copy( &P->Z, &Q->Z ) );
257 
258 cleanup:
259  return( ret );
260 }
261 
262 /*
263  * Copy the contents of a group object
264  */
265 int ecp_group_copy( ecp_group *dst, const ecp_group *src )
266 {
267  return ecp_use_known_dp( dst, src->id );
268 }
269 
270 /*
271  * Set point to zero
272  */
273 int ecp_set_zero( ecp_point *pt )
274 {
275  int ret;
276 
277  MPI_CHK( mpi_lset( &pt->X , 1 ) );
278  MPI_CHK( mpi_lset( &pt->Y , 1 ) );
279  MPI_CHK( mpi_lset( &pt->Z , 0 ) );
280 
281 cleanup:
282  return( ret );
283 }
284 
285 /*
286  * Tell if a point is zero
287  */
288 int ecp_is_zero( ecp_point *pt )
289 {
290  return( mpi_cmp_int( &pt->Z, 0 ) == 0 );
291 }
292 
293 /*
294  * Import a non-zero point from ASCII strings
295  */
296 int ecp_point_read_string( ecp_point *P, int radix,
297  const char *x, const char *y )
298 {
299  int ret;
300 
301  MPI_CHK( mpi_read_string( &P->X, radix, x ) );
302  MPI_CHK( mpi_read_string( &P->Y, radix, y ) );
303  MPI_CHK( mpi_lset( &P->Z, 1 ) );
304 
305 cleanup:
306  return( ret );
307 }
308 
309 /*
310  * Export a point into unsigned binary data (SEC1 2.3.3)
311  */
312 int ecp_point_write_binary( const ecp_group *grp, const ecp_point *P,
313  int format, size_t *olen,
314  unsigned char *buf, size_t buflen )
315 {
316  int ret = 0;
317  size_t plen;
318 
319  if( format != POLARSSL_ECP_PF_UNCOMPRESSED &&
320  format != POLARSSL_ECP_PF_COMPRESSED )
322 
323  /*
324  * Common case: P == 0
325  */
326  if( mpi_cmp_int( &P->Z, 0 ) == 0 )
327  {
328  if( buflen < 1 )
330 
331  buf[0] = 0x00;
332  *olen = 1;
333 
334  return( 0 );
335  }
336 
337  plen = mpi_size( &grp->P );
338 
339  if( format == POLARSSL_ECP_PF_UNCOMPRESSED )
340  {
341  *olen = 2 * plen + 1;
342 
343  if( buflen < *olen )
345 
346  buf[0] = 0x04;
347  MPI_CHK( mpi_write_binary( &P->X, buf + 1, plen ) );
348  MPI_CHK( mpi_write_binary( &P->Y, buf + 1 + plen, plen ) );
349  }
350  else if( format == POLARSSL_ECP_PF_COMPRESSED )
351  {
352  *olen = plen + 1;
353 
354  if( buflen < *olen )
356 
357  buf[0] = 0x02 + mpi_get_bit( &P->Y, 0 );
358  MPI_CHK( mpi_write_binary( &P->X, buf + 1, plen ) );
359  }
360 
361 cleanup:
362  return( ret );
363 }
364 
365 /*
366  * Import a point from unsigned binary data (SEC1 2.3.4)
367  */
368 int ecp_point_read_binary( const ecp_group *grp, ecp_point *pt,
369  const unsigned char *buf, size_t ilen ) {
370  int ret;
371  size_t plen;
372 
373  if( ilen == 1 && buf[0] == 0x00 )
374  return( ecp_set_zero( pt ) );
375 
376  plen = mpi_size( &grp->P );
377 
378  if( ilen != 2 * plen + 1 || buf[0] != 0x04 )
380 
381  MPI_CHK( mpi_read_binary( &pt->X, buf + 1, plen ) );
382  MPI_CHK( mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) );
383  MPI_CHK( mpi_lset( &pt->Z, 1 ) );
384 
385 cleanup:
386  return( ret );
387 }
388 
389 /*
390  * Import a point from a TLS ECPoint record (RFC 4492)
391  * struct {
392  * opaque point <1..2^8-1>;
393  * } ECPoint;
394  */
395 int ecp_tls_read_point( const ecp_group *grp, ecp_point *pt,
396  const unsigned char **buf, size_t buf_len )
397 {
398  unsigned char data_len;
399  const unsigned char *buf_start;
400 
401  /*
402  * We must have at least two bytes (1 for length, at least of for data)
403  */
404  if( buf_len < 2 )
406 
407  data_len = *(*buf)++;
408  if( data_len < 1 || data_len > buf_len - 1 )
410 
411  /*
412  * Save buffer start for read_binary and update buf
413  */
414  buf_start = *buf;
415  *buf += data_len;
416 
417  return ecp_point_read_binary( grp, pt, buf_start, data_len );
418 }
419 
420 /*
421  * Export a point as a TLS ECPoint record (RFC 4492)
422  * struct {
423  * opaque point <1..2^8-1>;
424  * } ECPoint;
425  */
426 int ecp_tls_write_point( const ecp_group *grp, const ecp_point *pt,
427  int format, size_t *olen,
428  unsigned char *buf, size_t blen )
429 {
430  int ret;
431 
432  /*
433  * buffer length must be at least one, for our length byte
434  */
435  if( blen < 1 )
437 
438  if( ( ret = ecp_point_write_binary( grp, pt, format,
439  olen, buf + 1, blen - 1) ) != 0 )
440  return( ret );
441 
442  /*
443  * write length to the first byte and update total length
444  */
445  buf[0] = (unsigned char) *olen;
446  ++*olen;
447 
448  return 0;
449 }
450 
451 /*
452  * Import an ECP group from ASCII strings, general case (A used)
453  */
454 static int ecp_group_read_string_gen( ecp_group *grp, int radix,
455  const char *p, const char *a, const char *b,
456  const char *gx, const char *gy, const char *n)
457 {
458  int ret;
459 
460  MPI_CHK( mpi_read_string( &grp->P, radix, p ) );
461  MPI_CHK( mpi_read_string( &grp->A, radix, a ) );
462  MPI_CHK( mpi_read_string( &grp->B, radix, b ) );
463  MPI_CHK( ecp_point_read_string( &grp->G, radix, gx, gy ) );
464  MPI_CHK( mpi_read_string( &grp->N, radix, n ) );
465 
466  grp->pbits = mpi_msb( &grp->P );
467  grp->nbits = mpi_msb( &grp->N );
468 
469 cleanup:
470  if( ret != 0 )
471  ecp_group_free( grp );
472 
473  return( ret );
474 }
475 
476 /*
477  * Import an ECP group from ASCII strings, case A == -3
478  */
479 int ecp_group_read_string( ecp_group *grp, int radix,
480  const char *p, const char *b,
481  const char *gx, const char *gy, const char *n)
482 {
483  int ret;
484 
485  MPI_CHK( ecp_group_read_string_gen( grp, radix, p, "00", b, gx, gy, n ) );
486  MPI_CHK( mpi_add_int( &grp->A, &grp->P, -3 ) );
487 
488 cleanup:
489  if( ret != 0 )
490  ecp_group_free( grp );
491 
492  return( ret );
493 }
494 
495 /*
496  * Domain parameters for secp192r1
497  */
498 #define SECP192R1_P \
499  "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF"
500 #define SECP192R1_B \
501  "64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1"
502 #define SECP192R1_GX \
503  "188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012"
504 #define SECP192R1_GY \
505  "07192B95FFC8DA78631011ED6B24CDD573F977A11E794811"
506 #define SECP192R1_N \
507  "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831"
508 
509 /*
510  * Domain parameters for secp224r1
511  */
512 #define SECP224R1_P \
513  "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001"
514 #define SECP224R1_B \
515  "B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4"
516 #define SECP224R1_GX \
517  "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21"
518 #define SECP224R1_GY \
519  "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34"
520 #define SECP224R1_N \
521  "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D"
522 
523 /*
524  * Domain parameters for secp256r1
525  */
526 #define SECP256R1_P \
527  "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF"
528 #define SECP256R1_B \
529  "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B"
530 #define SECP256R1_GX \
531  "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296"
532 #define SECP256R1_GY \
533  "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5"
534 #define SECP256R1_N \
535  "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551"
536 
537 /*
538  * Domain parameters for secp384r1
539  */
540 #define SECP384R1_P \
541  "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" \
542  "FFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF"
543 #define SECP384R1_B \
544  "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE814112" \
545  "0314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF"
546 #define SECP384R1_GX \
547  "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B98" \
548  "59F741E082542A385502F25DBF55296C3A545E3872760AB7"
549 #define SECP384R1_GY \
550  "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147C" \
551  "E9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F"
552 #define SECP384R1_N \
553  "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" \
554  "C7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973"
555 
556 /*
557  * Domain parameters for secp521r1
558  */
559 #define SECP521R1_P \
560  "000001FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" \
561  "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" \
562  "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
563 #define SECP521R1_B \
564  "00000051953EB9618E1C9A1F929A21A0B68540EEA2DA725B" \
565  "99B315F3B8B489918EF109E156193951EC7E937B1652C0BD" \
566  "3BB1BF073573DF883D2C34F1EF451FD46B503F00"
567 #define SECP521R1_GX \
568  "000000C6858E06B70404E9CD9E3ECB662395B4429C648139" \
569  "053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127" \
570  "A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66"
571 #define SECP521R1_GY \
572  "0000011839296A789A3BC0045C8A5FB42C7D1BD998F54449" \
573  "579B446817AFBD17273E662C97EE72995EF42640C550B901" \
574  "3FAD0761353C7086A272C24088BE94769FD16650"
575 #define SECP521R1_N \
576  "000001FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" \
577  "FFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148" \
578  "F709A5D03BB5C9B8899C47AEBB6FB71E91386409"
579 
580 /*
581  * Domain parameters for brainpoolP256r1 (RFC 5639 3.4)
582  */
583 #define BP256R1_P \
584  "A9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377"
585 #define BP256R1_A \
586  "7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9"
587 #define BP256R1_B \
588  "26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6"
589 #define BP256R1_GX \
590  "8BD2AEB9CB7E57CB2C4B482FFC81B7AFB9DE27E1E3BD23C23A4453BD9ACE3262"
591 #define BP256R1_GY \
592  "547EF835C3DAC4FD97F8461A14611DC9C27745132DED8E545C1D54C72F046997"
593 #define BP256R1_N \
594  "A9FB57DBA1EEA9BC3E660A909D838D718C397AA3B561A6F7901E0E82974856A7"
595 
596 /*
597  * Domain parameters for brainpoolP384r1 (RFC 5639 3.6)
598  */
599 #define BP384R1_P \
600  "8CB91E82A3386D280F5D6F7E50E641DF152F7109ED5456B412B1DA197FB711" \
601  "23ACD3A729901D1A71874700133107EC53"
602 #define BP384R1_A \
603  "7BC382C63D8C150C3C72080ACE05AFA0C2BEA28E4FB22787139165EFBA91F9" \
604  "0F8AA5814A503AD4EB04A8C7DD22CE2826"
605 #define BP384R1_B \
606  "04A8C7DD22CE28268B39B55416F0447C2FB77DE107DCD2A62E880EA53EEB62" \
607  "D57CB4390295DBC9943AB78696FA504C11"
608 #define BP384R1_GX \
609  "1D1C64F068CF45FFA2A63A81B7C13F6B8847A3E77EF14FE3DB7FCAFE0CBD10" \
610  "E8E826E03436D646AAEF87B2E247D4AF1E"
611 #define BP384R1_GY \
612  "8ABE1D7520F9C2A45CB1EB8E95CFD55262B70B29FEEC5864E19C054FF99129" \
613  "280E4646217791811142820341263C5315"
614 #define BP384R1_N \
615  "8CB91E82A3386D280F5D6F7E50E641DF152F7109ED5456B31F166E6CAC0425" \
616  "A7CF3AB6AF6B7FC3103B883202E9046565"
617 
618 /*
619  * Domain parameters for brainpoolP512r1 (RFC 5639 3.7)
620  */
621 #define BP512R1_P \
622  "AADD9DB8DBE9C48B3FD4E6AE33C9FC07CB308DB3B3C9D20ED6639CCA703308" \
623  "717D4D9B009BC66842AECDA12AE6A380E62881FF2F2D82C68528AA6056583A48F3"
624 #define BP512R1_A \
625  "7830A3318B603B89E2327145AC234CC594CBDD8D3DF91610A83441CAEA9863" \
626  "BC2DED5D5AA8253AA10A2EF1C98B9AC8B57F1117A72BF2C7B9E7C1AC4D77FC94CA"
627 #define BP512R1_B \
628  "3DF91610A83441CAEA9863BC2DED5D5AA8253AA10A2EF1C98B9AC8B57F1117" \
629  "A72BF2C7B9E7C1AC4D77FC94CADC083E67984050B75EBAE5DD2809BD638016F723"
630 #define BP512R1_GX \
631  "81AEE4BDD82ED9645A21322E9C4C6A9385ED9F70B5D916C1B43B62EEF4D009" \
632  "8EFF3B1F78E2D0D48D50D1687B93B97D5F7C6D5047406A5E688B352209BCB9F822"
633 #define BP512R1_GY \
634  "7DDE385D566332ECC0EABFA9CF7822FDF209F70024A57B1AA000C55B881F81" \
635  "11B2DCDE494A5F485E5BCA4BD88A2763AED1CA2B2FA8F0540678CD1E0F3AD80892"
636 #define BP512R1_N \
637  "AADD9DB8DBE9C48B3FD4E6AE33C9FC07CB308DB3B3C9D20ED6639CCA703308" \
638  "70553E5C414CA92619418661197FAC10471DB1D381085DDADDB58796829CA90069"
639 
640 #if defined(POLARSSL_ECP_NIST_OPTIM)
641 /* Forward declarations */
642 static int ecp_mod_p192( mpi * );
643 static int ecp_mod_p224( mpi * );
644 static int ecp_mod_p256( mpi * );
645 static int ecp_mod_p384( mpi * );
646 static int ecp_mod_p521( mpi * );
647 #endif
648 
649 /*
650  * Set a group using well-known domain parameters
651  */
653 {
654  grp->id = id;
655 
656  switch( id )
657  {
658 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
660 #if defined(POLARSSL_ECP_NIST_OPTIM)
661  grp->modp = ecp_mod_p192;
662 #endif
663  return( ecp_group_read_string( grp, 16,
664  SECP192R1_P, SECP192R1_B,
665  SECP192R1_GX, SECP192R1_GY, SECP192R1_N ) );
666 #endif /* POLARSSL_ECP_DP_SECP192R1_ENABLED */
667 
668 #if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED)
670 #if defined(POLARSSL_ECP_NIST_OPTIM)
671  grp->modp = ecp_mod_p224;
672 #endif
673  return( ecp_group_read_string( grp, 16,
674  SECP224R1_P, SECP224R1_B,
675  SECP224R1_GX, SECP224R1_GY, SECP224R1_N ) );
676 #endif /* POLARSSL_ECP_DP_SECP224R1_ENABLED */
677 
678 #if defined(POLARSSL_ECP_DP_SECP256R1_ENABLED)
680 #if defined(POLARSSL_ECP_NIST_OPTIM)
681  grp->modp = ecp_mod_p256;
682 #endif
683  return( ecp_group_read_string( grp, 16,
684  SECP256R1_P, SECP256R1_B,
685  SECP256R1_GX, SECP256R1_GY, SECP256R1_N ) );
686 #endif /* POLARSSL_ECP_DP_SECP256R1_ENABLED */
687 
688 #if defined(POLARSSL_ECP_DP_SECP384R1_ENABLED)
690 #if defined(POLARSSL_ECP_NIST_OPTIM)
691  grp->modp = ecp_mod_p384;
692 #endif
693  return( ecp_group_read_string( grp, 16,
694  SECP384R1_P, SECP384R1_B,
695  SECP384R1_GX, SECP384R1_GY, SECP384R1_N ) );
696 #endif /* POLARSSL_ECP_DP_SECP384R1_ENABLED */
697 
698 #if defined(POLARSSL_ECP_DP_SECP521R1_ENABLED)
700 #if defined(POLARSSL_ECP_NIST_OPTIM)
701  grp->modp = ecp_mod_p521;
702 #endif
703  return( ecp_group_read_string( grp, 16,
704  SECP521R1_P, SECP521R1_B,
705  SECP521R1_GX, SECP521R1_GY, SECP521R1_N ) );
706 #endif /* POLARSSL_ECP_DP_SECP521R1_ENABLED */
707 
708 #if defined(POLARSSL_ECP_DP_BP256R1_ENABLED)
710  return( ecp_group_read_string_gen( grp, 16,
711  BP256R1_P, BP256R1_A, BP256R1_B,
712  BP256R1_GX, BP256R1_GY, BP256R1_N ) );
713 #endif /* POLARSSL_ECP_DP_BP256R1_ENABLED */
714 
715 #if defined(POLARSSL_ECP_DP_BP384R1_ENABLED)
717  return( ecp_group_read_string_gen( grp, 16,
718  BP384R1_P, BP384R1_A, BP384R1_B,
719  BP384R1_GX, BP384R1_GY, BP384R1_N ) );
720 #endif /* POLARSSL_ECP_DP_BP384R1_ENABLED */
721 
722 #if defined(POLARSSL_ECP_DP_BP512R1_ENABLED)
724  return( ecp_group_read_string_gen( grp, 16,
725  BP512R1_P, BP512R1_A, BP512R1_B,
726  BP512R1_GX, BP512R1_GY, BP512R1_N ) );
727 #endif /* POLARSSL_ECP_DP_BP512R1_ENABLED */
728 
729  default:
730  ecp_group_free( grp );
732  }
733 }
734 
735 /*
736  * Set a group from an ECParameters record (RFC 4492)
737  */
738 int ecp_tls_read_group( ecp_group *grp, const unsigned char **buf, size_t len )
739 {
740  uint16_t tls_id;
741  const ecp_curve_info *curve_info;
742 
743  /*
744  * We expect at least three bytes (see below)
745  */
746  if( len < 3 )
748 
749  /*
750  * First byte is curve_type; only named_curve is handled
751  */
752  if( *(*buf)++ != POLARSSL_ECP_TLS_NAMED_CURVE )
754 
755  /*
756  * Next two bytes are the namedcurve value
757  */
758  tls_id = *(*buf)++;
759  tls_id <<= 8;
760  tls_id |= *(*buf)++;
761 
762  if( ( curve_info = ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
764 
765  return ecp_use_known_dp( grp, curve_info->grp_id );
766 }
767 
768 /*
769  * Write the ECParameters record corresponding to a group (RFC 4492)
770  */
771 int ecp_tls_write_group( const ecp_group *grp, size_t *olen,
772  unsigned char *buf, size_t blen )
773 {
774  const ecp_curve_info *curve_info;
775 
776  if( ( curve_info = ecp_curve_info_from_grp_id( grp->id ) ) == NULL )
778 
779  /*
780  * We are going to write 3 bytes (see below)
781  */
782  *olen = 3;
783  if( blen < *olen )
785 
786  /*
787  * First byte is curve_type, always named_curve
788  */
790 
791  /*
792  * Next two bytes are the namedcurve value
793  */
794  buf[0] = curve_info->tls_id >> 8;
795  buf[1] = curve_info->tls_id & 0xFF;
796 
797  return 0;
798 }
799 
800 /*
801  * Wrapper around fast quasi-modp functions, with fall-back to mpi_mod_mpi.
802  * See the documentation of struct ecp_group.
803  *
804  * This function is in the critial loop for ecp_mul, so pay attention to perf.
805  */
806 static int ecp_modp( mpi *N, const ecp_group *grp )
807 {
808  int ret;
809 
810  if( grp->modp == NULL )
811  return( mpi_mod_mpi( N, N, &grp->P ) );
812 
813  /* N->s < 0 is a much faster test, which fails only if N is 0 */
814  if( ( N->s < 0 && mpi_cmp_int( N, 0 ) != 0 ) ||
815  mpi_msb( N ) > 2 * grp->pbits )
816  {
818  }
819 
820  MPI_CHK( grp->modp( N ) );
821 
822  /* N->s < 0 is a much faster test, which fails only if N is 0 */
823  while( N->s < 0 && mpi_cmp_int( N, 0 ) != 0 )
824  MPI_CHK( mpi_add_mpi( N, N, &grp->P ) );
825 
826  while( mpi_cmp_mpi( N, &grp->P ) >= 0 )
827  /* we known P, N and the result are positive */
828  MPI_CHK( mpi_sub_abs( N, N, &grp->P ) );
829 
830 cleanup:
831  return( ret );
832 }
833 
834 /*
835  * Fast mod-p functions expect their argument to be in the 0..p^2 range.
836  *
837  * In order to guarantee that, we need to ensure that operands of
838  * mpi_mul_mpi are in the 0..p range. So, after each operation we will
839  * bring the result back to this range.
840  *
841  * The following macros are shortcuts for doing that.
842  */
843 
844 /*
845  * Reduce a mpi mod p in-place, general case, to use after mpi_mul_mpi
846  */
847 #define MOD_MUL( N ) MPI_CHK( ecp_modp( &N, grp ) )
848 
849 /*
850  * Reduce a mpi mod p in-place, to use after mpi_sub_mpi
851  * N->s < 0 is a very fast test, which fails only if N is 0
852  */
853 #define MOD_SUB( N ) \
854  while( N.s < 0 && mpi_cmp_int( &N, 0 ) != 0 ) \
855  MPI_CHK( mpi_add_mpi( &N, &N, &grp->P ) )
856 
857 /*
858  * Reduce a mpi mod p in-place, to use after mpi_add_mpi and mpi_mul_int.
859  * We known P, N and the result are positive, so sub_abs is correct, and
860  * a bit faster.
861  */
862 #define MOD_ADD( N ) \
863  while( mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
864  MPI_CHK( mpi_sub_abs( &N, &N, &grp->P ) )
865 
866 /*
867  * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1)
868  */
869 static int ecp_normalize( const ecp_group *grp, ecp_point *pt )
870 {
871  int ret;
872  mpi Zi, ZZi;
873 
874  if( mpi_cmp_int( &pt->Z, 0 ) == 0 )
875  return( 0 );
876 
877  mpi_init( &Zi ); mpi_init( &ZZi );
878 
879  /*
880  * X = X / Z^2 mod p
881  */
882  MPI_CHK( mpi_inv_mod( &Zi, &pt->Z, &grp->P ) );
883  MPI_CHK( mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
884  MPI_CHK( mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X );
885 
886  /*
887  * Y = Y / Z^3 mod p
888  */
889  MPI_CHK( mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y );
890  MPI_CHK( mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y );
891 
892  /*
893  * Z = 1
894  */
895  MPI_CHK( mpi_lset( &pt->Z, 1 ) );
896 
897 cleanup:
898 
899  mpi_free( &Zi ); mpi_free( &ZZi );
900 
901  return( ret );
902 }
903 
904 /*
905  * Normalize jacobian coordinates of an array of points,
906  * using Montgomery's trick to perform only one inversion mod P.
907  * (See for example Cohen's "A Course in Computational Algebraic Number
908  * Theory", Algorithm 10.3.4.)
909  *
910  * Warning: fails (returning an error) if one of the points is zero!
911  * This should never happen, see choice of w in ecp_mul().
912  */
913 static int ecp_normalize_many( const ecp_group *grp,
914  ecp_point T[], size_t t_len )
915 {
916  int ret;
917  size_t i;
918  mpi *c, u, Zi, ZZi;
919 
920  if( t_len < 2 )
921  return( ecp_normalize( grp, T ) );
922 
923  if( ( c = (mpi *) polarssl_malloc( t_len * sizeof( mpi ) ) ) == NULL )
925 
926  mpi_init( &u ); mpi_init( &Zi ); mpi_init( &ZZi );
927  for( i = 0; i < t_len; i++ )
928  mpi_init( &c[i] );
929 
930  /*
931  * c[i] = Z_0 * ... * Z_i
932  */
933  MPI_CHK( mpi_copy( &c[0], &T[0].Z ) );
934  for( i = 1; i < t_len; i++ )
935  {
936  MPI_CHK( mpi_mul_mpi( &c[i], &c[i-1], &T[i].Z ) );
937  MOD_MUL( c[i] );
938  }
939 
940  /*
941  * u = 1 / (Z_0 * ... * Z_n) mod P
942  */
943  MPI_CHK( mpi_inv_mod( &u, &c[t_len-1], &grp->P ) );
944 
945  for( i = t_len - 1; ; i-- )
946  {
947  /*
948  * Zi = 1 / Z_i mod p
949  * u = 1 / (Z_0 * ... * Z_i) mod P
950  */
951  if( i == 0 ) {
952  MPI_CHK( mpi_copy( &Zi, &u ) );
953  }
954  else
955  {
956  MPI_CHK( mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi );
957  MPI_CHK( mpi_mul_mpi( &u, &u, &T[i].Z ) ); MOD_MUL( u );
958  }
959 
960  /*
961  * proceed as in normalize()
962  */
963  MPI_CHK( mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
964  MPI_CHK( mpi_mul_mpi( &T[i].X, &T[i].X, &ZZi ) ); MOD_MUL( T[i].X );
965  MPI_CHK( mpi_mul_mpi( &T[i].Y, &T[i].Y, &ZZi ) ); MOD_MUL( T[i].Y );
966  MPI_CHK( mpi_mul_mpi( &T[i].Y, &T[i].Y, &Zi ) ); MOD_MUL( T[i].Y );
967  MPI_CHK( mpi_lset( &T[i].Z, 1 ) );
968 
969  if( i == 0 )
970  break;
971  }
972 
973 cleanup:
974 
975  mpi_free( &u ); mpi_free( &Zi ); mpi_free( &ZZi );
976  for( i = 0; i < t_len; i++ )
977  mpi_free( &c[i] );
978  polarssl_free( c );
979 
980  return( ret );
981 }
982 
983 /*
984  * Point doubling R = 2 P, Jacobian coordinates
985  *
986  * http://www.hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian/doubling/dbl-2007-bl.op3
987  * with heavy variable renaming, some reordering and one minor modification
988  * (a = 2 * b, c = d - 2a replaced with c = d, c = c - b, c = c - b)
989  * in order to use a lot less intermediate variables (6 vs 25).
990  */
991 static int ecp_double_jac( const ecp_group *grp, ecp_point *R,
992  const ecp_point *P )
993 {
994  int ret;
995  mpi T1, T2, T3, X3, Y3, Z3;
996 
997 #if defined(POLARSSL_SELF_TEST)
998  dbl_count++;
999 #endif
1000 
1001  mpi_init( &T1 ); mpi_init( &T2 ); mpi_init( &T3 );
1002  mpi_init( &X3 ); mpi_init( &Y3 ); mpi_init( &Z3 );
1003 
1004  MPI_CHK( mpi_mul_mpi( &T3, &P->X, &P->X ) ); MOD_MUL( T3 );
1005  MPI_CHK( mpi_mul_mpi( &T2, &P->Y, &P->Y ) ); MOD_MUL( T2 );
1006  MPI_CHK( mpi_mul_mpi( &Y3, &T2, &T2 ) ); MOD_MUL( Y3 );
1007  MPI_CHK( mpi_add_mpi( &X3, &P->X, &T2 ) ); MOD_ADD( X3 );
1008  MPI_CHK( mpi_mul_mpi( &X3, &X3, &X3 ) ); MOD_MUL( X3 );
1009  MPI_CHK( mpi_sub_mpi( &X3, &X3, &Y3 ) ); MOD_SUB( X3 );
1010  MPI_CHK( mpi_sub_mpi( &X3, &X3, &T3 ) ); MOD_SUB( X3 );
1011  MPI_CHK( mpi_mul_int( &T1, &X3, 2 ) ); MOD_ADD( T1 );
1012  MPI_CHK( mpi_mul_mpi( &Z3, &P->Z, &P->Z ) ); MOD_MUL( Z3 );
1013  MPI_CHK( mpi_mul_mpi( &X3, &Z3, &Z3 ) ); MOD_MUL( X3 );
1014  MPI_CHK( mpi_mul_int( &T3, &T3, 3 ) ); MOD_ADD( T3 );
1015  MPI_CHK( mpi_mul_mpi( &X3, &X3, &grp->A ) ); MOD_MUL( X3 );
1016  MPI_CHK( mpi_add_mpi( &T3, &T3, &X3 ) ); MOD_ADD( T3 );
1017  MPI_CHK( mpi_mul_mpi( &X3, &T3, &T3 ) ); MOD_MUL( X3 );
1018  MPI_CHK( mpi_sub_mpi( &X3, &X3, &T1 ) ); MOD_SUB( X3 );
1019  MPI_CHK( mpi_sub_mpi( &X3, &X3, &T1 ) ); MOD_SUB( X3 );
1020  MPI_CHK( mpi_sub_mpi( &T1, &T1, &X3 ) ); MOD_SUB( T1 );
1021  MPI_CHK( mpi_mul_mpi( &T1, &T3, &T1 ) ); MOD_MUL( T1 );
1022  MPI_CHK( mpi_mul_int( &T3, &Y3, 8 ) ); MOD_ADD( T3 );
1023  MPI_CHK( mpi_sub_mpi( &Y3, &T1, &T3 ) ); MOD_SUB( Y3 );
1024  MPI_CHK( mpi_add_mpi( &T1, &P->Y, &P->Z ) ); MOD_ADD( T1 );
1025  MPI_CHK( mpi_mul_mpi( &T1, &T1, &T1 ) ); MOD_MUL( T1 );
1026  MPI_CHK( mpi_sub_mpi( &T1, &T1, &T2 ) ); MOD_SUB( T1 );
1027  MPI_CHK( mpi_sub_mpi( &Z3, &T1, &Z3 ) ); MOD_SUB( Z3 );
1028 
1029  MPI_CHK( mpi_copy( &R->X, &X3 ) );
1030  MPI_CHK( mpi_copy( &R->Y, &Y3 ) );
1031  MPI_CHK( mpi_copy( &R->Z, &Z3 ) );
1032 
1033 cleanup:
1034  mpi_free( &T1 ); mpi_free( &T2 ); mpi_free( &T3 );
1035  mpi_free( &X3 ); mpi_free( &Y3 ); mpi_free( &Z3 );
1036 
1037  return( ret );
1038 }
1039 
1040 /*
1041  * Addition or subtraction: R = P + Q or R = P - Q,
1042  * mixed affine-Jacobian coordinates (GECC 3.22)
1043  *
1044  * The coordinates of Q must be normalized (= affine),
1045  * but those of P don't need to. R is not normalized.
1046  *
1047  * If sign >= 0, perform addition, otherwise perform subtraction,
1048  * taking advantage of the fact that, for Q != 0, we have
1049  * -Q = (Q.X, -Q.Y, Q.Z)
1050  */
1051 static int ecp_add_mixed( const ecp_group *grp, ecp_point *R,
1052  const ecp_point *P, const ecp_point *Q,
1053  signed char sign )
1054 {
1055  int ret;
1056  mpi T1, T2, T3, T4, X, Y, Z;
1057 
1058 #if defined(POLARSSL_SELF_TEST)
1059  add_count++;
1060 #endif
1061 
1062  /*
1063  * Trivial cases: P == 0 or Q == 0
1064  * (Check Q first, so that we know Q != 0 when we compute -Q.)
1065  */
1066  if( mpi_cmp_int( &Q->Z, 0 ) == 0 )
1067  return( ecp_copy( R, P ) );
1068 
1069  if( mpi_cmp_int( &P->Z, 0 ) == 0 )
1070  {
1071  ret = ecp_copy( R, Q );
1072 
1073  /*
1074  * -R.Y mod P = P - R.Y unless R.Y == 0
1075  */
1076  if( ret == 0 && sign < 0)
1077  if( mpi_cmp_int( &R->Y, 0 ) != 0 )
1078  ret = mpi_sub_mpi( &R->Y, &grp->P, &R->Y );
1079 
1080  return( ret );
1081  }
1082 
1083  /*
1084  * Make sure Q coordinates are normalized
1085  */
1086  if( mpi_cmp_int( &Q->Z, 1 ) != 0 )
1088 
1089  mpi_init( &T1 ); mpi_init( &T2 ); mpi_init( &T3 ); mpi_init( &T4 );
1090  mpi_init( &X ); mpi_init( &Y ); mpi_init( &Z );
1091 
1092  MPI_CHK( mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 );
1093  MPI_CHK( mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 );
1094  MPI_CHK( mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 );
1095  MPI_CHK( mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 );
1096 
1097  /*
1098  * For subtraction, -Q.Y should have been used instead of Q.Y,
1099  * so we replace T2 by -T2, which is P - T2 mod P
1100  */
1101  if( sign < 0 )
1102  {
1103  MPI_CHK( mpi_sub_mpi( &T2, &grp->P, &T2 ) );
1104  MOD_SUB( T2 );
1105  }
1106 
1107  MPI_CHK( mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 );
1108  MPI_CHK( mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 );
1109 
1110  if( mpi_cmp_int( &T1, 0 ) == 0 )
1111  {
1112  if( mpi_cmp_int( &T2, 0 ) == 0 )
1113  {
1114  ret = ecp_double_jac( grp, R, P );
1115  goto cleanup;
1116  }
1117  else
1118  {
1119  ret = ecp_set_zero( R );
1120  goto cleanup;
1121  }
1122  }
1123 
1124  MPI_CHK( mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z );
1125  MPI_CHK( mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 );
1126  MPI_CHK( mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 );
1127  MPI_CHK( mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 );
1128  MPI_CHK( mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 );
1129  MPI_CHK( mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X );
1130  MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X );
1131  MPI_CHK( mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X );
1132  MPI_CHK( mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 );
1133  MPI_CHK( mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 );
1134  MPI_CHK( mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 );
1135  MPI_CHK( mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y );
1136 
1137  MPI_CHK( mpi_copy( &R->X, &X ) );
1138  MPI_CHK( mpi_copy( &R->Y, &Y ) );
1139  MPI_CHK( mpi_copy( &R->Z, &Z ) );
1140 
1141 cleanup:
1142 
1143  mpi_free( &T1 ); mpi_free( &T2 ); mpi_free( &T3 ); mpi_free( &T4 );
1144  mpi_free( &X ); mpi_free( &Y ); mpi_free( &Z );
1145 
1146  return( ret );
1147 }
1148 
1149 /*
1150  * Addition: R = P + Q, result's coordinates normalized
1151  */
1152 int ecp_add( const ecp_group *grp, ecp_point *R,
1153  const ecp_point *P, const ecp_point *Q )
1154 {
1155  int ret;
1156 
1157  MPI_CHK( ecp_add_mixed( grp, R, P, Q , 1 ) );
1158  MPI_CHK( ecp_normalize( grp, R ) );
1159 
1160 cleanup:
1161  return( ret );
1162 }
1163 
1164 /*
1165  * Subtraction: R = P - Q, result's coordinates normalized
1166  */
1167 int ecp_sub( const ecp_group *grp, ecp_point *R,
1168  const ecp_point *P, const ecp_point *Q )
1169 {
1170  int ret;
1171 
1172  MPI_CHK( ecp_add_mixed( grp, R, P, Q, -1 ) );
1173  MPI_CHK( ecp_normalize( grp, R ) );
1174 
1175 cleanup:
1176  return( ret );
1177 }
1178 
1179 /*
1180  * Compute a modified width-w non-adjacent form (NAF) of a number,
1181  * with a fixed pattern for resistance to simple timing attacks (even SPA),
1182  * see [1]. (The resulting multiplication algorithm can also been seen as a
1183  * modification of 2^w-ary multiplication, with signed coefficients, all of
1184  * them odd.)
1185  *
1186  * Input:
1187  * m must be an odd positive mpi less than w * k bits long
1188  * x must be an array of k elements
1189  * w must be less than a certain maximum (currently 8)
1190  *
1191  * The result is a sequence x[0], ..., x[k-1] with x[i] in the range
1192  * - 2^(width - 1) .. 2^(width - 1) - 1 such that
1193  * m = (2 * x[0] + 1) + 2^width * (2 * x[1] + 1) + ...
1194  * + 2^((k-1) * width) * (2 * x[k-1] + 1)
1195  *
1196  * Compared to "Algorithm SPA-resistant Width-w NAF with Odd Scalar"
1197  * p. 335 of the cited reference, here we return only u, not d_w since
1198  * it is known that the other d_w[j] will be 0. Moreover, the returned
1199  * string doesn't actually store u_i but x_i = u_i / 2 since it is known
1200  * that u_i is odd. Also, since we always select a positive value for d
1201  * mod 2^w, we don't need to check the sign of u[i-1] when the reference
1202  * does. Finally, there is an off-by-one error in the reference: the
1203  * last index should be k-1, not k.
1204  */
1205 static int ecp_w_naf_fixed( signed char x[], size_t k,
1206  unsigned char w, const mpi *m )
1207 {
1208  int ret;
1209  unsigned int i, u, mask, carry;
1210  mpi M;
1211 
1212  mpi_init( &M );
1213 
1214  MPI_CHK( mpi_copy( &M, m ) );
1215  mask = ( 1 << w ) - 1;
1216  carry = 1 << ( w - 1 );
1217 
1218  for( i = 0; i < k; i++ )
1219  {
1220  u = M.p[0] & mask;
1221 
1222  if( ( u & 1 ) == 0 && i > 0 )
1223  x[i - 1] -= carry;
1224 
1225  x[i] = u >> 1;
1226  mpi_shift_r( &M, w );
1227  }
1228 
1229  /*
1230  * We should have consumed all bits, unless the input value was too big
1231  */
1232  if( mpi_cmp_int( &M, 0 ) != 0 )
1234 
1235 cleanup:
1236 
1237  mpi_free( &M );
1238 
1239  return( ret );
1240 }
1241 
1242 /*
1243  * Precompute odd multiples of P up to (2 * t_len - 1) P.
1244  * The table is filled with T[i] = (2 * i + 1) P.
1245  */
1246 static int ecp_precompute( const ecp_group *grp,
1247  ecp_point T[], size_t t_len,
1248  const ecp_point *P )
1249 {
1250  int ret;
1251  size_t i;
1252  ecp_point PP;
1253 
1254  ecp_point_init( &PP );
1255 
1256  MPI_CHK( ecp_add( grp, &PP, P, P ) );
1257 
1258  MPI_CHK( ecp_copy( &T[0], P ) );
1259 
1260  for( i = 1; i < t_len; i++ )
1261  MPI_CHK( ecp_add_mixed( grp, &T[i], &T[i-1], &PP, +1 ) );
1262 
1263  /*
1264  * T[0] = P already has normalized coordinates
1265  */
1266  MPI_CHK( ecp_normalize_many( grp, T + 1, t_len - 1 ) );
1267 
1268 cleanup:
1269 
1270  ecp_point_free( &PP );
1271 
1272  return( ret );
1273 }
1274 
1275 /*
1276  * Randomize jacobian coordinates:
1277  * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
1278  * This is sort of the reverse operation of ecp_normalize().
1279  */
1280 static int ecp_randomize_coordinates( const ecp_group *grp, ecp_point *pt,
1281  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1282 {
1283  int ret;
1284  mpi l, ll;
1285  size_t p_size = (grp->pbits + 7) / 8;
1286  int count = 0;
1287 
1288  mpi_init( &l ); mpi_init( &ll );
1289 
1290  /* Generate l such that 1 < l < p */
1291  do
1292  {
1293  mpi_fill_random( &l, p_size, f_rng, p_rng );
1294 
1295  while( mpi_cmp_mpi( &l, &grp->P ) >= 0 )
1296  mpi_shift_r( &l, 1 );
1297 
1298  if( count++ > 10 )
1300  }
1301  while( mpi_cmp_int( &l, 1 ) <= 0 );
1302 
1303  /* Z = l * Z */
1304  MPI_CHK( mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z );
1305 
1306  /* X = l^2 * X */
1307  MPI_CHK( mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll );
1308  MPI_CHK( mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X );
1309 
1310  /* Y = l^3 * Y */
1311  MPI_CHK( mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll );
1312  MPI_CHK( mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y );
1313 
1314 cleanup:
1315  mpi_free( &l ); mpi_free( &ll );
1316 
1317  return( ret );
1318 }
1319 
1320 /*
1321  * Maximum length of the precomputed table
1322  */
1323 #define MAX_PRE_LEN ( 1 << (POLARSSL_ECP_WINDOW_SIZE - 1) )
1324 
1325 /*
1326  * Maximum length of the NAF: ceil( grp->nbits + 1 ) / w
1327  * (that is: grp->nbits / w + 1)
1328  * Allow p_bits + 1 bits in case M = grp->N + 1 is one bit longer than N.
1329  */
1330 #define MAX_NAF_LEN ( POLARSSL_ECP_MAX_BITS / 2 + 1 )
1331 
1332 /*
1333  * Integer multiplication: R = m * P
1334  *
1335  * Based on fixed-pattern width-w NAF, see comments of ecp_w_naf_fixed().
1336  *
1337  * This function executes a fixed number of operations for
1338  * random m in the range 0 .. 2^nbits - 1.
1339  *
1340  * As an additional countermeasure against potential timing attacks,
1341  * we randomize coordinates before each addition. This was suggested as a
1342  * countermeasure against DPA in 5.3 of [2] (with the obvious adaptation that
1343  * we use jacobian coordinates, not standard projective coordinates).
1344  */
1345 int ecp_mul( ecp_group *grp, ecp_point *R,
1346  const mpi *m, const ecp_point *P,
1347  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1348 {
1349  int ret;
1350  unsigned char w, m_is_odd, p_eq_g;
1351  size_t pre_len = 1, naf_len, i, j;
1352  signed char naf[ MAX_NAF_LEN ];
1353  ecp_point Q, *T = NULL, S[2];
1354  mpi M;
1355 
1356  if( mpi_cmp_int( m, 0 ) < 0 || mpi_msb( m ) > grp->nbits )
1358 
1359  mpi_init( &M );
1360  ecp_point_init( &Q );
1361  ecp_point_init( &S[0] );
1362  ecp_point_init( &S[1] );
1363 
1364  /*
1365  * Check if P == G
1366  */
1367  p_eq_g = ( mpi_cmp_int( &P->Z, 1 ) == 0 &&
1368  mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&
1369  mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 );
1370 
1371  /*
1372  * If P == G, pre-compute a lot of points: this will be re-used later,
1373  * otherwise, choose window size depending on curve size
1374  */
1375  if( p_eq_g )
1377  else
1378  w = grp->nbits >= 512 ? 6 :
1379  grp->nbits >= 224 ? 5 :
1380  4;
1381 
1382  /*
1383  * Make sure w is within the limits.
1384  * The last test ensures that none of the precomputed points is zero,
1385  * which wouldn't be handled correctly by ecp_normalize_many().
1386  * It is only useful for very small curves as used in the test suite.
1387  */
1388  if( w > POLARSSL_ECP_WINDOW_SIZE )
1390  if( w < 2 || w >= grp->nbits )
1391  w = 2;
1392 
1393  pre_len <<= ( w - 1 );
1394  naf_len = grp->nbits / w + 1;
1395 
1396  /*
1397  * Prepare precomputed points: if P == G we want to
1398  * use grp->T if already initialized, or initiliaze it.
1399  */
1400  if( ! p_eq_g || grp->T == NULL )
1401  {
1402  T = (ecp_point *) polarssl_malloc( pre_len * sizeof( ecp_point ) );
1403  if( T == NULL )
1404  {
1406  goto cleanup;
1407  }
1408 
1409  for( i = 0; i < pre_len; i++ )
1410  ecp_point_init( &T[i] );
1411 
1412  MPI_CHK( ecp_precompute( grp, T, pre_len, P ) );
1413 
1414  if( p_eq_g )
1415  {
1416  grp->T = T;
1417  grp->T_size = pre_len;
1418  }
1419  }
1420  else
1421  {
1422  T = grp->T;
1423 
1424  /* Should never happen, but we want to be extra sure */
1425  if( pre_len != grp->T_size )
1426  {
1428  goto cleanup;
1429  }
1430  }
1431 
1432  /*
1433  * Make sure M is odd (M = m + 1 or M = m + 2)
1434  * later we'll get m * P by subtracting P or 2 * P to M * P.
1435  */
1436  m_is_odd = ( mpi_get_bit( m, 0 ) == 1 );
1437 
1438  MPI_CHK( mpi_copy( &M, m ) );
1439  MPI_CHK( mpi_add_int( &M, &M, 1 + m_is_odd ) );
1440 
1441  /*
1442  * Compute the fixed-pattern NAF of M
1443  */
1444  MPI_CHK( ecp_w_naf_fixed( naf, naf_len, w, &M ) );
1445 
1446  /*
1447  * Compute M * P, using a variant of left-to-right 2^w-ary multiplication:
1448  * at each step we add (2 * naf[i] + 1) P, then multiply by 2^w.
1449  *
1450  * If naf[i] >= 0, we have (2 * naf[i] + 1) P == T[ naf[i] ]
1451  * Otherwise, (2 * naf[i] + 1) P == - ( 2 * ( - naf[i] - 1 ) + 1) P
1452  * == T[ - naf[i] - 1 ]
1453  */
1454  MPI_CHK( ecp_set_zero( &Q ) );
1455  i = naf_len - 1;
1456  while( 1 )
1457  {
1458  /* Countermeasure (see comments above) */
1459  if( f_rng != NULL )
1460  ecp_randomize_coordinates( grp, &Q, f_rng, p_rng );
1461 
1462  if( naf[i] < 0 )
1463  {
1464  MPI_CHK( ecp_add_mixed( grp, &Q, &Q, &T[ - naf[i] - 1 ], -1 ) );
1465  }
1466  else
1467  {
1468  MPI_CHK( ecp_add_mixed( grp, &Q, &Q, &T[ naf[i] ], +1 ) );
1469  }
1470 
1471  if( i == 0 )
1472  break;
1473  i--;
1474 
1475  for( j = 0; j < w; j++ )
1476  {
1477  MPI_CHK( ecp_double_jac( grp, &Q, &Q ) );
1478  }
1479  }
1480 
1481  /*
1482  * Now get m * P from M * P
1483  */
1484  MPI_CHK( ecp_copy( &S[0], P ) );
1485  MPI_CHK( ecp_add( grp, &S[1], P, P ) );
1486  MPI_CHK( ecp_sub( grp, R, &Q, &S[m_is_odd] ) );
1487 
1488 
1489 cleanup:
1490 
1491  if( T != NULL && ! p_eq_g )
1492  {
1493  for( i = 0; i < pre_len; i++ )
1494  ecp_point_free( &T[i] );
1495  polarssl_free( T );
1496  }
1497 
1498  ecp_point_free( &S[1] );
1499  ecp_point_free( &S[0] );
1500  ecp_point_free( &Q );
1501  mpi_free( &M );
1502 
1503  return( ret );
1504 }
1505 
1506 /*
1507  * Check that a point is valid as a public key (SEC1 3.2.3.1)
1508  */
1509 int ecp_check_pubkey( const ecp_group *grp, const ecp_point *pt )
1510 {
1511  int ret;
1512  mpi YY, RHS;
1513 
1514  if( mpi_cmp_int( &pt->Z, 0 ) == 0 )
1515  return( POLARSSL_ERR_ECP_INVALID_KEY );
1516 
1517  /*
1518  * pt coordinates must be normalized for our checks
1519  */
1520  if( mpi_cmp_int( &pt->Z, 1 ) != 0 )
1521  return( POLARSSL_ERR_ECP_INVALID_KEY );
1522 
1523  if( mpi_cmp_int( &pt->X, 0 ) < 0 ||
1524  mpi_cmp_int( &pt->Y, 0 ) < 0 ||
1525  mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 ||
1526  mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 )
1527  return( POLARSSL_ERR_ECP_INVALID_KEY );
1528 
1529  mpi_init( &YY ); mpi_init( &RHS );
1530 
1531  /*
1532  * YY = Y^2
1533  * RHS = X (X^2 + A) + B = X^3 + A X + B
1534  */
1535  MPI_CHK( mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY );
1536  MPI_CHK( mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS );
1537  MPI_CHK( mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS );
1538  MPI_CHK( mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS );
1539  MPI_CHK( mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS );
1540 
1541  if( mpi_cmp_mpi( &YY, &RHS ) != 0 )
1543 
1544 cleanup:
1545 
1546  mpi_free( &YY ); mpi_free( &RHS );
1547 
1548  return( ret );
1549 }
1550 
1551 /*
1552  * Check that an mpi is valid as a private key (SEC1 3.2)
1553  */
1554 int ecp_check_privkey( const ecp_group *grp, const mpi *d )
1555 {
1556  /* We want 1 <= d <= N-1 */
1557  if ( mpi_cmp_int( d, 1 ) < 0 || mpi_cmp_mpi( d, &grp->N ) >= 0 )
1558  return( POLARSSL_ERR_ECP_INVALID_KEY );
1559 
1560  return( 0 );
1561 }
1562 
1563 /*
1564  * Generate a keypair (SEC1 3.2.1)
1565  */
1566 int ecp_gen_keypair( ecp_group *grp, mpi *d, ecp_point *Q,
1567  int (*f_rng)(void *, unsigned char *, size_t),
1568  void *p_rng )
1569 {
1570  int count = 0;
1571  size_t n_size = (grp->nbits + 7) / 8;
1572 
1573  /*
1574  * Generate d such that 1 <= n < N
1575  */
1576  do
1577  {
1578  mpi_fill_random( d, n_size, f_rng, p_rng );
1579 
1580  while( mpi_cmp_mpi( d, &grp->N ) >= 0 )
1581  mpi_shift_r( d, 1 );
1582 
1583  if( count++ > 10 )
1585  }
1586  while( mpi_cmp_int( d, 1 ) < 0 );
1587 
1588  return( ecp_mul( grp, Q, d, &grp->G, f_rng, p_rng ) );
1589 }
1590 
1591 #if defined(POLARSSL_ECP_NIST_OPTIM)
1592 /*
1593  * Fast reduction modulo the primes used by the NIST curves.
1594  *
1595  * These functions are: critical for speed, but not need for correct
1596  * operations. So, we make the choice to heavily rely on the internals of our
1597  * bignum library, which creates a tight coupling between these functions and
1598  * our MPI implementation. However, the coupling between the ECP module and
1599  * MPI remains loose, since these functions can be deactivated at will.
1600  */
1601 
1602 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
1603 /*
1604  * Compared to the way things are presented in FIPS 186-3 D.2,
1605  * we proceed in columns, from right (least significant chunk) to left,
1606  * adding chunks to N in place, and keeping a carry for the next chunk.
1607  * This avoids moving things around in memory, and uselessly adding zeros,
1608  * compared to the more straightforward, line-oriented approach.
1609  *
1610  * For this prime we need to handle data in chunks of 64 bits.
1611  * Since this is always a multiple of our basic t_uint, we can
1612  * use a t_uint * to designate such a chunk, and small loops to handle it.
1613  */
1614 
1615 /* Add 64-bit chunks (dst += src) and update carry */
1616 static inline void add64( t_uint *dst, t_uint *src, t_uint *carry )
1617 {
1618  unsigned char i;
1619  t_uint c = 0;
1620  for( i = 0; i < 8 / sizeof( t_uint ); i++, dst++, src++ )
1621  {
1622  *dst += c; c = ( *dst < c );
1623  *dst += *src; c += ( *dst < *src );
1624  }
1625  *carry += c;
1626 }
1627 
1628 /* Add carry to a 64-bit chunk and update carry */
1629 static inline void carry64( t_uint *dst, t_uint *carry )
1630 {
1631  unsigned char i;
1632  for( i = 0; i < 8 / sizeof( t_uint ); i++, dst++ )
1633  {
1634  *dst += *carry;
1635  *carry = ( *dst < *carry );
1636  }
1637 }
1638 
1639 #define WIDTH 8 / sizeof( t_uint )
1640 #define A( i ) N->p + i * WIDTH
1641 #define ADD( i ) add64( p, A( i ), &c )
1642 #define NEXT p += WIDTH; carry64( p, &c )
1643 #define LAST p += WIDTH; *p = c; while( ++p < end ) *p = 0
1644 
1645 /*
1646  * Fast quasi-reduction modulo p192 (FIPS 186-3 D.2.1)
1647  */
1648 static int ecp_mod_p192( mpi *N )
1649 {
1650  int ret;
1651  t_uint c = 0;
1652  t_uint *p, *end;
1653 
1654  /* Make sure we have enough blocks so that A(5) is legal */
1655  MPI_CHK( mpi_grow( N, 6 * WIDTH ) );
1656 
1657  p = N->p;
1658  end = p + N->n;
1659 
1660  ADD( 3 ); ADD( 5 ); NEXT; // A0 += A3 + A5
1661  ADD( 3 ); ADD( 4 ); ADD( 5 ); NEXT; // A1 += A3 + A4 + A5
1662  ADD( 4 ); ADD( 5 ); LAST; // A2 += A4 + A5
1663 
1664 cleanup:
1665  return( ret );
1666 }
1667 
1668 #undef WIDTH
1669 #undef A
1670 #undef ADD
1671 #undef NEXT
1672 #undef LAST
1673 #endif /* POLARSSL_ECP_DP_SECP192R1_ENABLED */
1674 
1675 #if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED) || \
1676  defined(POLARSSL_ECP_DP_SECP256R1_ENABLED) || \
1677  defined(POLARSSL_ECP_DP_SECP384R1_ENABLED)
1678 /*
1679  * The reader is advised to first understand ecp_mod_p192() since the same
1680  * general structure is used here, but with additional complications:
1681  * (1) chunks of 32 bits, and (2) subtractions.
1682  */
1683 
1684 /*
1685  * For these primes, we need to handle data in chunks of 32 bits.
1686  * This makes it more complicated if we use 64 bits limbs in MPI,
1687  * which prevents us from using a uniform access method as for p192.
1688  *
1689  * So, we define a mini abstraction layer to access 32 bit chunks,
1690  * load them in 'cur' for work, and store them back from 'cur' when done.
1691  *
1692  * While at it, also define the size of N in terms of 32-bit chunks.
1693  */
1694 #define LOAD32 cur = A( i );
1695 
1696 #if defined(POLARSSL_HAVE_INT8) /* 8 bit */
1697 
1698 #define MAX32 N->n / 4
1699 #define A( j ) (uint32_t)( N->p[4*j+0] ) | \
1700  ( N->p[4*j+1] << 8 ) | \
1701  ( N->p[4*j+2] << 16 ) | \
1702  ( N->p[4*j+3] << 24 )
1703 #define STORE32 N->p[4*i+0] = (uint8_t)( cur ); \
1704  N->p[4*i+1] = (uint8_t)( cur >> 8 ); \
1705  N->p[4*i+2] = (uint8_t)( cur >> 16 ); \
1706  N->p[4*i+3] = (uint8_t)( cur >> 24 );
1707 
1708 #elif defined(POLARSSL_HAVE_INT16) /* 16 bit */
1709 
1710 #define MAX32 N->n / 2
1711 #define A( j ) (uint32_t)( N->p[2*j] ) | ( N->p[2*j+1] << 16 )
1712 #define STORE32 N->p[2*i+0] = (uint16_t)( cur ); \
1713  N->p[2*i+1] = (uint16_t)( cur >> 16 );
1714 
1715 #elif defined(POLARSSL_HAVE_INT32) /* 32 bit */
1716 
1717 #define MAX32 N->n
1718 #define A( j ) N->p[j]
1719 #define STORE32 N->p[i] = cur;
1720 
1721 #else /* 64-bit */
1722 
1723 #define MAX32 N->n * 2
1724 #define A( j ) j % 2 ? (uint32_t)( N->p[j/2] >> 32 ) : (uint32_t)( N->p[j/2] )
1725 #define STORE32 \
1726  if( i % 2 ) { \
1727  N->p[i/2] &= 0x00000000FFFFFFFF; \
1728  N->p[i/2] |= ((uint64_t) cur) << 32; \
1729  } else { \
1730  N->p[i/2] &= 0xFFFFFFFF00000000; \
1731  N->p[i/2] |= (uint64_t) cur; \
1732  }
1733 
1734 #endif /* sizeof( t_uint ) */
1735 
1736 /*
1737  * Helpers for addition and subtraction of chunks, with signed carry.
1738  */
1739 static inline void add32( uint32_t *dst, uint32_t src, signed char *carry )
1740 {
1741  *dst += src;
1742  *carry += ( *dst < src );
1743 }
1744 
1745 static inline void sub32( uint32_t *dst, uint32_t src, signed char *carry )
1746 {
1747  *carry -= ( *dst < src );
1748  *dst -= src;
1749 }
1750 
1751 #define ADD( j ) add32( &cur, A( j ), &c );
1752 #define SUB( j ) sub32( &cur, A( j ), &c );
1753 
1754 /*
1755  * Helpers for the main 'loop'
1756  * (see fix_negative for the motivation of C)
1757  */
1758 #define INIT( b ) \
1759  int ret; \
1760  signed char c = 0, cc; \
1761  uint32_t cur; \
1762  size_t i = 0, bits = b; \
1763  mpi C; \
1764  t_uint Cp[ b / 8 / sizeof( t_uint) + 1 ]; \
1765  \
1766  C.s = 1; \
1767  C.n = b / 8 / sizeof( t_uint) + 1; \
1768  C.p = Cp; \
1769  memset( Cp, 0, C.n * sizeof( t_uint ) ); \
1770  \
1771  MPI_CHK( mpi_grow( N, b * 2 / 8 / sizeof( t_uint ) ) ); \
1772  LOAD32;
1773 
1774 #define NEXT \
1775  STORE32; i++; LOAD32; \
1776  cc = c; c = 0; \
1777  if( cc < 0 ) \
1778  sub32( &cur, -cc, &c ); \
1779  else \
1780  add32( &cur, cc, &c ); \
1781 
1782 #define LAST \
1783  STORE32; i++; \
1784  cur = c > 0 ? c : 0; STORE32; \
1785  cur = 0; while( ++i < MAX32 ) { STORE32; } \
1786  if( c < 0 ) fix_negative( N, c, &C, bits );
1787 
1788 /*
1789  * If the result is negative, we get it in the form
1790  * c * 2^(bits + 32) + N, with c negative and N positive shorter than 'bits'
1791  */
1792 static inline int fix_negative( mpi *N, signed char c, mpi *C, size_t bits )
1793 {
1794  int ret;
1795 
1796  /* C = - c * 2^(bits + 32) */
1797 #if !defined(POLARSSL_HAVE_INT64)
1798  ((void) bits);
1799 #else
1800  if( bits == 224 )
1801  C->p[ C->n - 1 ] = ((t_uint) -c) << 32;
1802  else
1803 #endif
1804  C->p[ C->n - 1 ] = (t_uint) -c;
1805 
1806  /* N = - ( C - N ) */
1807  MPI_CHK( mpi_sub_abs( N, C, N ) );
1808  N->s = -1;
1809 
1810 cleanup:
1811 
1812  return( ret );
1813 }
1814 
1815 #if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED)
1816 /*
1817  * Fast quasi-reduction modulo p224 (FIPS 186-3 D.2.2)
1818  */
1819 static int ecp_mod_p224( mpi *N )
1820 {
1821  INIT( 224 );
1822 
1823  SUB( 7 ); SUB( 11 ); NEXT; // A0 += -A7 - A11
1824  SUB( 8 ); SUB( 12 ); NEXT; // A1 += -A8 - A12
1825  SUB( 9 ); SUB( 13 ); NEXT; // A2 += -A9 - A13
1826  SUB( 10 ); ADD( 7 ); ADD( 11 ); NEXT; // A3 += -A10 + A7 + A11
1827  SUB( 11 ); ADD( 8 ); ADD( 12 ); NEXT; // A4 += -A11 + A8 + A12
1828  SUB( 12 ); ADD( 9 ); ADD( 13 ); NEXT; // A5 += -A12 + A9 + A13
1829  SUB( 13 ); ADD( 10 ); LAST; // A6 += -A13 + A10
1830 
1831 cleanup:
1832  return( ret );
1833 }
1834 #endif /* POLARSSL_ECP_DP_SECP224R1_ENABLED */
1835 
1836 #if defined(POLARSSL_ECP_DP_SECP256R1_ENABLED)
1837 /*
1838  * Fast quasi-reduction modulo p256 (FIPS 186-3 D.2.3)
1839  */
1840 static int ecp_mod_p256( mpi *N )
1841 {
1842  INIT( 256 );
1843 
1844  ADD( 8 ); ADD( 9 );
1845  SUB( 11 ); SUB( 12 ); SUB( 13 ); SUB( 14 ); NEXT; // A0
1846 
1847  ADD( 9 ); ADD( 10 );
1848  SUB( 12 ); SUB( 13 ); SUB( 14 ); SUB( 15 ); NEXT; // A1
1849 
1850  ADD( 10 ); ADD( 11 );
1851  SUB( 13 ); SUB( 14 ); SUB( 15 ); NEXT; // A2
1852 
1853  ADD( 11 ); ADD( 11 ); ADD( 12 ); ADD( 12 ); ADD( 13 );
1854  SUB( 15 ); SUB( 8 ); SUB( 9 ); NEXT; // A3
1855 
1856  ADD( 12 ); ADD( 12 ); ADD( 13 ); ADD( 13 ); ADD( 14 );
1857  SUB( 9 ); SUB( 10 ); NEXT; // A4
1858 
1859  ADD( 13 ); ADD( 13 ); ADD( 14 ); ADD( 14 ); ADD( 15 );
1860  SUB( 10 ); SUB( 11 ); NEXT; // A5
1861 
1862  ADD( 14 ); ADD( 14 ); ADD( 15 ); ADD( 15 ); ADD( 14 ); ADD( 13 );
1863  SUB( 8 ); SUB( 9 ); NEXT; // A6
1864 
1865  ADD( 15 ); ADD( 15 ); ADD( 15 ); ADD( 8 );
1866  SUB( 10 ); SUB( 11 ); SUB( 12 ); SUB( 13 ); LAST; // A7
1867 
1868 cleanup:
1869  return( ret );
1870 }
1871 #endif /* POLARSSL_ECP_DP_SECP256R1_ENABLED */
1872 
1873 #if defined(POLARSSL_ECP_DP_SECP384R1_ENABLED)
1874 /*
1875  * Fast quasi-reduction modulo p384 (FIPS 186-3 D.2.4)
1876  */
1877 static int ecp_mod_p384( mpi *N )
1878 {
1879  INIT( 384 );
1880 
1881  ADD( 12 ); ADD( 21 ); ADD( 20 );
1882  SUB( 23 ); NEXT; // A0
1883 
1884  ADD( 13 ); ADD( 22 ); ADD( 23 );
1885  SUB( 12 ); SUB( 20 ); NEXT; // A2
1886 
1887  ADD( 14 ); ADD( 23 );
1888  SUB( 13 ); SUB( 21 ); NEXT; // A2
1889 
1890  ADD( 15 ); ADD( 12 ); ADD( 20 ); ADD( 21 );
1891  SUB( 14 ); SUB( 22 ); SUB( 23 ); NEXT; // A3
1892 
1893  ADD( 21 ); ADD( 21 ); ADD( 16 ); ADD( 13 ); ADD( 12 ); ADD( 20 ); ADD( 22 );
1894  SUB( 15 ); SUB( 23 ); SUB( 23 ); NEXT; // A4
1895 
1896  ADD( 22 ); ADD( 22 ); ADD( 17 ); ADD( 14 ); ADD( 13 ); ADD( 21 ); ADD( 23 );
1897  SUB( 16 ); NEXT; // A5
1898 
1899  ADD( 23 ); ADD( 23 ); ADD( 18 ); ADD( 15 ); ADD( 14 ); ADD( 22 );
1900  SUB( 17 ); NEXT; // A6
1901 
1902  ADD( 19 ); ADD( 16 ); ADD( 15 ); ADD( 23 );
1903  SUB( 18 ); NEXT; // A7
1904 
1905  ADD( 20 ); ADD( 17 ); ADD( 16 );
1906  SUB( 19 ); NEXT; // A8
1907 
1908  ADD( 21 ); ADD( 18 ); ADD( 17 );
1909  SUB( 20 ); NEXT; // A9
1910 
1911  ADD( 22 ); ADD( 19 ); ADD( 18 );
1912  SUB( 21 ); NEXT; // A10
1913 
1914  ADD( 23 ); ADD( 20 ); ADD( 19 );
1915  SUB( 22 ); LAST; // A11
1916 
1917 cleanup:
1918  return( ret );
1919 }
1920 #endif /* POLARSSL_ECP_DP_SECP384R1_ENABLED */
1921 
1922 #undef A
1923 #undef LOAD32
1924 #undef STORE32
1925 #undef MAX32
1926 #undef INIT
1927 #undef NEXT
1928 #undef LAST
1929 
1930 #endif /* POLARSSL_ECP_DP_SECP224R1_ENABLED ||
1931  POLARSSL_ECP_DP_SECP256R1_ENABLED ||
1932  POLARSSL_ECP_DP_SECP384R1_ENABLED */
1933 
1934 #if defined(POLARSSL_ECP_DP_SECP521R1_ENABLED)
1935 /*
1936  * Here we have an actual Mersenne prime, so things are more straightforward.
1937  * However, chunks are aligned on a 'weird' boundary (521 bits).
1938  */
1939 
1940 /* Size of p521 in terms of t_uint */
1941 #define P521_WIDTH ( 521 / 8 / sizeof( t_uint ) + 1 )
1942 
1943 /* Bits to keep in the most significant t_uint */
1944 #if defined(POLARSSL_HAVE_INT8)
1945 #define P521_MASK 0x01
1946 #else
1947 #define P521_MASK 0x01FF
1948 #endif
1949 
1950 /*
1951  * Fast quasi-reduction modulo p521 (FIPS 186-3 D.2.5)
1952  * Write N as A1 + 2^521 A0, return A0 + A1
1953  */
1954 static int ecp_mod_p521( mpi *N )
1955 {
1956  int ret;
1957  size_t i;
1958  mpi M;
1959  t_uint Mp[P521_WIDTH + 1];
1960  /* Worst case for the size of M is when t_uint is 16 bits:
1961  * we need to hold bits 513 to 1056, which is 34 limbs, that is
1962  * P521_WIDTH + 1. Otherwise P521_WIDTH is enough. */
1963 
1964  if( N->n < P521_WIDTH )
1965  return( 0 );
1966 
1967  /* M = A1 */
1968  M.s = 1;
1969  M.n = N->n - ( P521_WIDTH - 1 );
1970  if( M.n > P521_WIDTH + 1 )
1971  M.n = P521_WIDTH + 1;
1972  M.p = Mp;
1973  memcpy( Mp, N->p + P521_WIDTH - 1, M.n * sizeof( t_uint ) );
1974  MPI_CHK( mpi_shift_r( &M, 521 % ( 8 * sizeof( t_uint ) ) ) );
1975 
1976  /* N = A0 */
1977  N->p[P521_WIDTH - 1] &= P521_MASK;
1978  for( i = P521_WIDTH; i < N->n; i++ )
1979  N->p[i] = 0;
1980 
1981  /* N = A0 + A1 */
1982  MPI_CHK( mpi_add_abs( N, N, &M ) );
1983 
1984 cleanup:
1985  return( ret );
1986 }
1987 
1988 #undef P521_WIDTH
1989 #undef P521_MASK
1990 #endif /* POLARSSL_ECP_DP_SECP521R1_ENABLED */
1991 
1992 #endif /* POLARSSL_ECP_NIST_OPTIM */
1993 
1994 #if defined(POLARSSL_SELF_TEST)
1995 
1996 /*
1997  * Checkup routine
1998  */
1999 int ecp_self_test( int verbose )
2000 {
2001  int ret;
2002  size_t i;
2003  ecp_group grp;
2004  ecp_point R, P;
2005  mpi m;
2006  unsigned long add_c_prev, dbl_c_prev;
2007  /* exponents especially adapted for secp192r1 */
2008  const char *exponents[] =
2009  {
2010  "000000000000000000000000000000000000000000000000", /* zero */
2011  "000000000000000000000000000000000000000000000001", /* one */
2012  "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831", /* N */
2013  "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
2014  "400000000000000000000000000000000000000000000000",
2015  "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
2016  "555555555555555555555555555555555555555555555555",
2017  };
2018 
2019  ecp_group_init( &grp );
2020  ecp_point_init( &R );
2021  ecp_point_init( &P );
2022  mpi_init( &m );
2023 
2024  /* Use secp192r1 if available, or any available curve */
2025 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
2027 #else
2028  MPI_CHK( ecp_use_known_dp( &grp, ecp_curve_list()->grp_id ) );
2029 #endif
2030 
2031  if( verbose != 0 )
2032  printf( " ECP test #1 (constant op_count, base point G): " );
2033 
2034  /* Do a dummy multiplication first to trigger precomputation */
2035  MPI_CHK( mpi_lset( &m, 2 ) );
2036  MPI_CHK( ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) );
2037 
2038  add_count = 0;
2039  dbl_count = 0;
2040  MPI_CHK( mpi_read_string( &m, 16, exponents[0] ) );
2041  MPI_CHK( ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
2042 
2043  for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
2044  {
2045  add_c_prev = add_count;
2046  dbl_c_prev = dbl_count;
2047  add_count = 0;
2048  dbl_count = 0;
2049 
2050  MPI_CHK( mpi_read_string( &m, 16, exponents[i] ) );
2051  MPI_CHK( ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
2052 
2053  if( add_count != add_c_prev || dbl_count != dbl_c_prev )
2054  {
2055  if( verbose != 0 )
2056  printf( "failed (%zu)\n", i );
2057 
2058  ret = 1;
2059  goto cleanup;
2060  }
2061  }
2062 
2063  if( verbose != 0 )
2064  printf( "passed\n" );
2065 
2066  if( verbose != 0 )
2067  printf( " ECP test #2 (constant op_count, other point): " );
2068  /* We computed P = 2G last time, use it */
2069 
2070  add_count = 0;
2071  dbl_count = 0;
2072  MPI_CHK( mpi_read_string( &m, 16, exponents[0] ) );
2073  MPI_CHK( ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
2074 
2075  for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
2076  {
2077  add_c_prev = add_count;
2078  dbl_c_prev = dbl_count;
2079  add_count = 0;
2080  dbl_count = 0;
2081 
2082  MPI_CHK( mpi_read_string( &m, 16, exponents[i] ) );
2083  MPI_CHK( ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
2084 
2085  if( add_count != add_c_prev || dbl_count != dbl_c_prev )
2086  {
2087  if( verbose != 0 )
2088  printf( "failed (%zu)\n", i );
2089 
2090  ret = 1;
2091  goto cleanup;
2092  }
2093  }
2094 
2095  if( verbose != 0 )
2096  printf( "passed\n" );
2097 
2098 cleanup:
2099 
2100  if( ret < 0 && verbose != 0 )
2101  printf( "Unexpected error, return code = %08X\n", ret );
2102 
2103  ecp_group_free( &grp );
2104  ecp_point_free( &R );
2105  ecp_point_free( &P );
2106  mpi_free( &m );
2107 
2108  if( verbose != 0 )
2109  printf( "\n" );
2110 
2111  return( ret );
2112 }
2113 
2114 #endif
2115 
2116 #endif
int mpi_cmp_int(const mpi *X, t_sint z)
Compare signed values.
size_t pbits
Definition: ecp.h:125
#define POLARSSL_ECP_TLS_NAMED_CURVE
ECCurveType&#39;s named_curve.
Definition: ecp.h:180
int ecp_sub(const ecp_group *grp, ecp_point *R, const ecp_point *P, const ecp_point *Q)
Subtraction: R = P - Q.
int ecp_check_privkey(const ecp_group *grp, const mpi *d)
Check that an mpi is a valid private key for this curve.
#define POLARSSL_ERR_ECP_BAD_INPUT_DATA
Bad input parameters to function.
Definition: ecp.h:35
void ecp_keypair_init(ecp_keypair *key)
Initialize a key pair (as an invalid one)
int ecp_group_copy(ecp_group *dst, const ecp_group *src)
Copy the contents of a group object.
Memory allocation layer.
ecp_group_id grp_id
Definition: ecp.h:79
void *(* polarssl_malloc)(size_t len)
#define POLARSSL_ECP_PF_COMPRESSED
Compressed point format.
Definition: ecp.h:175
uint32_t t_uint
Definition: bignum.h:149
const ecp_curve_info * ecp_curve_list(void)
Return the list of supported curves with associated info.
int ecp_self_test(int verbose)
Checkup routine.
Elliptic curves over GF(p)
int s
Definition: bignum.h:173
int mpi_fill_random(mpi *X, size_t size, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Fill an MPI X with size bytes of random.
int mpi_sub_abs(mpi *X, const mpi *A, const mpi *B)
Unsigned subtraction: X = |A| - |B|.
mpi P
Definition: ecp.h:120
ecp_group grp
Definition: ecp.h:146
#define POLARSSL_ERR_ECP_MALLOC_FAILED
Memory allocation failed.
Definition: ecp.h:39
int(* modp)(mpi *)
Definition: ecp.h:128
#define POLARSSL_ECP_PF_UNCOMPRESSED
Uncompressed point format.
Definition: ecp.h:174
ECP group structure.
Definition: ecp.h:117
Configuration options (set of defines)
int mpi_add_int(mpi *X, const mpi *A, t_sint b)
Signed addition: X = A + b.
ECP key pair structure.
Definition: ecp.h:144
mpi d
Definition: ecp.h:147
int mpi_lset(mpi *X, t_sint z)
Set value from integer.
MPI structure.
Definition: bignum.h:171
int ecp_mul(ecp_group *grp, ecp_point *R, const mpi *m, const ecp_point *P, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Multiplication by an integer: R = m * P (Not thread-safe to use same group in multiple threads) ...
int ecp_point_read_binary(const ecp_group *grp, ecp_point *P, const unsigned char *buf, size_t ilen)
Import a point from unsigned binary data.
#define POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE
Requested curve not available.
Definition: ecp.h:37
void mpi_init(mpi *X)
Initialize one MPI.
mpi X
Definition: ecp.h:96
int mpi_cmp_mpi(const mpi *X, const mpi *Y)
Compare signed values.
#define POLARSSL_ECP_WINDOW_SIZE
Maximum NAF width used.
Definition: ecp.h:169
int mpi_shift_r(mpi *X, size_t count)
Right-shift: X &gt;&gt;= count.
#define POLARSSL_ERR_ECP_BUFFER_TOO_SMALL
The buffer is too small to write to.
Definition: ecp.h:36
int mpi_add_mpi(mpi *X, const mpi *A, const mpi *B)
Signed addition: X = A + B.
ecp_point G
Definition: ecp.h:123
ecp_group_id id
Definition: ecp.h:119
ECP point structure (jacobian coordinates)
Definition: ecp.h:94
size_t T_size
Definition: ecp.h:133
int ecp_is_zero(ecp_point *pt)
Tell if a point is zero.
void ecp_point_init(ecp_point *pt)
Initialize a point (as zero)
mpi B
Definition: ecp.h:122
mpi N
Definition: ecp.h:124
void(* polarssl_free)(void *ptr)
const ecp_curve_info * ecp_curve_info_from_grp_id(ecp_group_id grp_id)
Get curve information from an internal group identifier.
int mpi_inv_mod(mpi *X, const mpi *A, const mpi *N)
Modular inverse: X = A^-1 mod N.
int ecp_point_read_string(ecp_point *P, int radix, const char *x, const char *y)
Import a non-zero point from two ASCII strings.
void mpi_free(mpi *X)
Unallocate one MPI.
int mpi_mul_int(mpi *X, const mpi *A, t_sint b)
Baseline multiplication: X = A * b Note: b is an unsigned integer type, thus Negative values of b are...
void ecp_group_free(ecp_group *grp)
Free the components of an ECP group.
int mpi_grow(mpi *X, size_t nblimbs)
Enlarge to the specified number of limbs.
Curve information for use by other modules.
Definition: ecp.h:77
int ecp_tls_write_point(const ecp_group *grp, const ecp_point *pt, int format, size_t *olen, unsigned char *buf, size_t blen)
Export a point as a TLS ECPoint record.
int ecp_gen_keypair(ecp_group *grp, mpi *d, ecp_point *Q, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Generate a keypair.
size_t mpi_msb(const mpi *X)
Return the number of bits up to and including the most significant &#39;1&#39; bit&#39;.
int ecp_use_known_dp(ecp_group *grp, ecp_group_id index)
Set a group using well-known domain parameters.
int mpi_add_abs(mpi *X, const mpi *A, const mpi *B)
Unsigned addition: X = |A| + |B|.
int mpi_read_string(mpi *X, int radix, const char *s)
Import from an ASCII string.
int ecp_copy(ecp_point *P, const ecp_point *Q)
Copy the contents of point Q into P.
t_uint * p
Definition: bignum.h:175
int mpi_read_binary(mpi *X, const unsigned char *buf, size_t buflen)
Import X from unsigned binary data, big endian.
mpi A
Definition: ecp.h:121
int ecp_tls_write_group(const ecp_group *grp, size_t *olen, unsigned char *buf, size_t blen)
Write the TLS ECParameters record for a group.
ecp_group_id
Domain parameters (curve, subgroup and generator) identifiers.
Definition: ecp.h:56
int ecp_point_write_binary(const ecp_group *grp, const ecp_point *P, int format, size_t *olen, unsigned char *buf, size_t buflen)
Export a point into unsigned binary data.
void ecp_group_init(ecp_group *grp)
Initialize a group (to something meaningless)
size_t nbits
Definition: ecp.h:126
#define POLARSSL_ERR_ECP_RANDOM_FAILED
Generation of random value, such as (ephemeral) key, failed.
Definition: ecp.h:40
size_t mpi_size(const mpi *X)
Return the total size in bytes.
mpi Y
Definition: ecp.h:97
int mpi_copy(mpi *X, const mpi *Y)
Copy the contents of Y into X.
size_t n
Definition: bignum.h:174
int mpi_mod_mpi(mpi *R, const mpi *A, const mpi *B)
Modulo: R = A mod B.
int mpi_get_bit(const mpi *X, size_t pos)
Get a specific bit from X.
int mpi_write_binary(const mpi *X, unsigned char *buf, size_t buflen)
Export X into unsigned binary data, big endian.
int ecp_tls_read_group(ecp_group *grp, const unsigned char **buf, size_t len)
Set a group from a TLS ECParameters record.
ecp_point Q
Definition: ecp.h:148
mpi Z
Definition: ecp.h:98
uint16_t tls_id
Definition: ecp.h:80
int ecp_check_pubkey(const ecp_group *grp, const ecp_point *pt)
Check that a point is a valid public key on this curve.
const ecp_curve_info * ecp_curve_info_from_tls_id(uint16_t tls_id)
Get curve information from a TLS NamedCurve value.
int ecp_add(const ecp_group *grp, ecp_point *R, const ecp_point *P, const ecp_point *Q)
Addition: R = P + Q.
int mpi_mul_mpi(mpi *X, const mpi *A, const mpi *B)
Baseline multiplication: X = A * B.
int ecp_set_zero(ecp_point *pt)
Set a point to zero.
int mpi_sub_mpi(mpi *X, const mpi *A, const mpi *B)
Signed subtraction: X = A - B.
ecp_point * T
Definition: ecp.h:132
#define POLARSSL_ERR_ECP_INVALID_KEY
Invalid private or public key.
Definition: ecp.h:41
void ecp_keypair_free(ecp_keypair *key)
Free the components of a key pair.
int ecp_tls_read_point(const ecp_group *grp, ecp_point *pt, const unsigned char **buf, size_t len)
Import a point from a TLS ECPoint record.
int ecp_group_read_string(ecp_group *grp, int radix, const char *p, const char *b, const char *gx, const char *gy, const char *n)
Import an ECP group from null-terminated ASCII strings.
#define MPI_CHK(f)
Definition: bignum.h:61
void ecp_point_free(ecp_point *pt)
Free the components of a point.