PolarSSL v1.3.7
ecp.c
Go to the documentation of this file.
1 /*
2  * Elliptic curves over GF(p): generic functions
3  *
4  * Copyright (C) 2006-2014, 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  * [M255] http://cr.yp.to/ecdh/curve25519-20060209.pdf
35  *
36  * [2] CORON, Jean-Sébastien. Resistance against differential power analysis
37  * for elliptic curve cryptosystems. In : Cryptographic Hardware and
38  * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
39  * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
40  *
41  * [3] HEDABOU, Mustapha, PINEL, Pierre, et BÉNÉTEAU, Lucien. A comb method to
42  * render ECC resistant against Side Channel Attacks. IACR Cryptology
43  * ePrint Archive, 2004, vol. 2004, p. 342.
44  * <http://eprint.iacr.org/2004/342.pdf>
45  */
46 
47 #if !defined(POLARSSL_CONFIG_FILE)
48 #include "polarssl/config.h"
49 #else
50 #include POLARSSL_CONFIG_FILE
51 #endif
52 
53 #if defined(POLARSSL_ECP_C)
54 
55 #include "polarssl/ecp.h"
56 
57 #if defined(POLARSSL_PLATFORM_C)
58 #include "polarssl/platform.h"
59 #else
60 #define polarssl_printf printf
61 #define polarssl_malloc malloc
62 #define polarssl_free free
63 #endif
64 
65 #include <stdlib.h>
66 
67 #if defined(_MSC_VER) && !defined strcasecmp && !defined(EFIX64) && \
68  !defined(EFI32)
69 #define strcasecmp _stricmp
70 #endif
71 
72 #if defined(_MSC_VER) && !defined(inline)
73 #define inline _inline
74 #else
75 #if defined(__ARMCC_VERSION) && !defined(inline)
76 #define inline __inline
77 #endif /* __ARMCC_VERSION */
78 #endif /*_MSC_VER */
79 
80 #if defined(POLARSSL_SELF_TEST)
81 /*
82  * Counts of point addition and doubling, and field multiplications.
83  * Used to test resistance of point multiplication to simple timing attacks.
84  */
85 static unsigned long add_count, dbl_count, mul_count;
86 #endif
87 
88 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED) || \
89  defined(POLARSSL_ECP_DP_SECP224R1_ENABLED) || \
90  defined(POLARSSL_ECP_DP_SECP256R1_ENABLED) || \
91  defined(POLARSSL_ECP_DP_SECP384R1_ENABLED) || \
92  defined(POLARSSL_ECP_DP_SECP521R1_ENABLED) || \
93  defined(POLARSSL_ECP_DP_BP256R1_ENABLED) || \
94  defined(POLARSSL_ECP_DP_BP384R1_ENABLED) || \
95  defined(POLARSSL_ECP_DP_BP512R1_ENABLED) || \
96  defined(POLARSSL_ECP_DP_SECP192K1_ENABLED) || \
97  defined(POLARSSL_ECP_DP_SECP224K1_ENABLED) || \
98  defined(POLARSSL_ECP_DP_SECP256K1_ENABLED)
99 #define POLARSSL_ECP_SHORT_WEIERSTRASS
100 #endif
101 
102 #if defined(POLARSSL_ECP_DP_M221_ENABLED) || \
103  defined(POLARSSL_ECP_DP_M255_ENABLED) || \
104  defined(POLARSSL_ECP_DP_M383_ENABLED) || \
105  defined(POLARSSL_ECP_DP_M511_ENABLED)
106 #define POLARSSL_ECP_MONTGOMERY
107 #endif
108 
109 /*
110  * Curve types: internal for now, might be exposed later
111  */
112 typedef enum
113 {
114  POLARSSL_ECP_TYPE_NONE = 0,
115  POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */
116  POLARSSL_ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */
117 } ecp_curve_type;
118 
119 /*
120  * List of supported curves:
121  * - internal ID
122  * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
123  * - size in bits
124  * - readable name
125  *
126  * Curves are listed in order: largest curves first, and for a given size,
127  * fastest curves first. This provides the default order for the SSL module.
128  */
129 static const ecp_curve_info ecp_supported_curves[POLARSSL_ECP_DP_MAX] =
130 {
131 #if defined(POLARSSL_ECP_DP_SECP521R1_ENABLED)
132  { POLARSSL_ECP_DP_SECP521R1, 25, 521, "secp521r1" },
133 #endif
134 #if defined(POLARSSL_ECP_DP_BP512R1_ENABLED)
135  { POLARSSL_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" },
136 #endif
137 #if defined(POLARSSL_ECP_DP_SECP384R1_ENABLED)
138  { POLARSSL_ECP_DP_SECP384R1, 24, 384, "secp384r1" },
139 #endif
140 #if defined(POLARSSL_ECP_DP_BP384R1_ENABLED)
141  { POLARSSL_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" },
142 #endif
143 #if defined(POLARSSL_ECP_DP_SECP256R1_ENABLED)
144  { POLARSSL_ECP_DP_SECP256R1, 23, 256, "secp256r1" },
145 #endif
146 #if defined(POLARSSL_ECP_DP_SECP256K1_ENABLED)
147  { POLARSSL_ECP_DP_SECP256K1, 22, 256, "secp256k1" },
148 #endif
149 #if defined(POLARSSL_ECP_DP_BP256R1_ENABLED)
150  { POLARSSL_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" },
151 #endif
152 #if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED)
153  { POLARSSL_ECP_DP_SECP224R1, 21, 224, "secp224r1" },
154 #endif
155 #if defined(POLARSSL_ECP_DP_SECP224K1_ENABLED)
156  { POLARSSL_ECP_DP_SECP224K1, 20, 224, "secp224k1" },
157 #endif
158 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
159  { POLARSSL_ECP_DP_SECP192R1, 19, 192, "secp192r1" },
160 #endif
161 #if defined(POLARSSL_ECP_DP_SECP192K1_ENABLED)
162  { POLARSSL_ECP_DP_SECP192K1, 18, 192, "secp192k1" },
163 #endif
164  { POLARSSL_ECP_DP_NONE, 0, 0, NULL },
165 };
166 
167 static ecp_group_id ecp_supported_grp_id[POLARSSL_ECP_DP_MAX];
168 
169 /*
170  * List of supported curves and associated info
171  */
172 const ecp_curve_info *ecp_curve_list( void )
173 {
174  return ecp_supported_curves;
175 }
176 
177 /*
178  * List of supported curves, group ID only
179  */
180 const ecp_group_id *ecp_grp_id_list( void )
181 {
182  static int init_done = 0;
183 
184  if( ! init_done )
185  {
186  size_t i = 0;
187  const ecp_curve_info *curve_info;
188 
189  for( curve_info = ecp_curve_list();
190  curve_info->grp_id != POLARSSL_ECP_DP_NONE;
191  curve_info++ )
192  {
193  ecp_supported_grp_id[i++] = curve_info->grp_id;
194  }
195  ecp_supported_grp_id[i] = POLARSSL_ECP_DP_NONE;
196 
197  init_done = 1;
198  }
199 
200  return ecp_supported_grp_id;
201 }
202 
203 /*
204  * Get the curve info for the internal identifier
205  */
207 {
208  const ecp_curve_info *curve_info;
209 
210  for( curve_info = ecp_curve_list();
211  curve_info->grp_id != POLARSSL_ECP_DP_NONE;
212  curve_info++ )
213  {
214  if( curve_info->grp_id == grp_id )
215  return( curve_info );
216  }
217 
218  return( NULL );
219 }
220 
221 /*
222  * Get the curve info from the TLS identifier
223  */
224 const ecp_curve_info *ecp_curve_info_from_tls_id( uint16_t tls_id )
225 {
226  const ecp_curve_info *curve_info;
227 
228  for( curve_info = ecp_curve_list();
229  curve_info->grp_id != POLARSSL_ECP_DP_NONE;
230  curve_info++ )
231  {
232  if( curve_info->tls_id == tls_id )
233  return( curve_info );
234  }
235 
236  return( NULL );
237 }
238 
239 /*
240  * Get the curve info from the name
241  */
242 const ecp_curve_info *ecp_curve_info_from_name( const char *name )
243 {
244  const ecp_curve_info *curve_info;
245 
246  for( curve_info = ecp_curve_list();
247  curve_info->grp_id != POLARSSL_ECP_DP_NONE;
248  curve_info++ )
249  {
250  if( strcasecmp( curve_info->name, name ) == 0 )
251  return( curve_info );
252  }
253 
254  return( NULL );
255 }
256 
257 /*
258  * Get the type of a curve
259  */
260 static inline ecp_curve_type ecp_get_type( const ecp_group *grp )
261 {
262  if( grp->G.X.p == NULL )
263  return( POLARSSL_ECP_TYPE_NONE );
264 
265  if( grp->G.Y.p == NULL )
266  return( POLARSSL_ECP_TYPE_MONTGOMERY );
267  else
268  return( POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS );
269 }
270 
271 /*
272  * Initialize (the components of) a point
273  */
274 void ecp_point_init( ecp_point *pt )
275 {
276  if( pt == NULL )
277  return;
278 
279  mpi_init( &pt->X );
280  mpi_init( &pt->Y );
281  mpi_init( &pt->Z );
282 }
283 
284 /*
285  * Initialize (the components of) a group
286  */
287 void ecp_group_init( ecp_group *grp )
288 {
289  if( grp == NULL )
290  return;
291 
292  memset( grp, 0, sizeof( ecp_group ) );
293 }
294 
295 /*
296  * Initialize (the components of) a key pair
297  */
298 void ecp_keypair_init( ecp_keypair *key )
299 {
300  if ( key == NULL )
301  return;
302 
303  ecp_group_init( &key->grp );
304  mpi_init( &key->d );
305  ecp_point_init( &key->Q );
306 }
307 
308 /*
309  * Unallocate (the components of) a point
310  */
311 void ecp_point_free( ecp_point *pt )
312 {
313  if( pt == NULL )
314  return;
315 
316  mpi_free( &( pt->X ) );
317  mpi_free( &( pt->Y ) );
318  mpi_free( &( pt->Z ) );
319 }
320 
321 /*
322  * Unallocate (the components of) a group
323  */
324 void ecp_group_free( ecp_group *grp )
325 {
326  size_t i;
327 
328  if( grp == NULL )
329  return;
330 
331  if( grp->h != 1 )
332  {
333  mpi_free( &grp->P );
334  mpi_free( &grp->A );
335  mpi_free( &grp->B );
336  ecp_point_free( &grp->G );
337  mpi_free( &grp->N );
338  }
339 
340  if( grp->T != NULL )
341  {
342  for( i = 0; i < grp->T_size; i++ )
343  ecp_point_free( &grp->T[i] );
344  polarssl_free( grp->T );
345  }
346 
347  memset( grp, 0, sizeof( ecp_group ) );
348 }
349 
350 /*
351  * Unallocate (the components of) a key pair
352  */
353 void ecp_keypair_free( ecp_keypair *key )
354 {
355  if ( key == NULL )
356  return;
357 
358  ecp_group_free( &key->grp );
359  mpi_free( &key->d );
360  ecp_point_free( &key->Q );
361 }
362 
363 /*
364  * Copy the contents of a point
365  */
366 int ecp_copy( ecp_point *P, const ecp_point *Q )
367 {
368  int ret;
369 
370  MPI_CHK( mpi_copy( &P->X, &Q->X ) );
371  MPI_CHK( mpi_copy( &P->Y, &Q->Y ) );
372  MPI_CHK( mpi_copy( &P->Z, &Q->Z ) );
373 
374 cleanup:
375  return( ret );
376 }
377 
378 /*
379  * Copy the contents of a group object
380  */
381 int ecp_group_copy( ecp_group *dst, const ecp_group *src )
382 {
383  return ecp_use_known_dp( dst, src->id );
384 }
385 
386 /*
387  * Set point to zero
388  */
389 int ecp_set_zero( ecp_point *pt )
390 {
391  int ret;
392 
393  MPI_CHK( mpi_lset( &pt->X , 1 ) );
394  MPI_CHK( mpi_lset( &pt->Y , 1 ) );
395  MPI_CHK( mpi_lset( &pt->Z , 0 ) );
396 
397 cleanup:
398  return( ret );
399 }
400 
401 /*
402  * Tell if a point is zero
403  */
404 int ecp_is_zero( ecp_point *pt )
405 {
406  return( mpi_cmp_int( &pt->Z, 0 ) == 0 );
407 }
408 
409 /*
410  * Import a non-zero point from ASCII strings
411  */
412 int ecp_point_read_string( ecp_point *P, int radix,
413  const char *x, const char *y )
414 {
415  int ret;
416 
417  MPI_CHK( mpi_read_string( &P->X, radix, x ) );
418  MPI_CHK( mpi_read_string( &P->Y, radix, y ) );
419  MPI_CHK( mpi_lset( &P->Z, 1 ) );
420 
421 cleanup:
422  return( ret );
423 }
424 
425 /*
426  * Export a point into unsigned binary data (SEC1 2.3.3)
427  */
428 int ecp_point_write_binary( const ecp_group *grp, const ecp_point *P,
429  int format, size_t *olen,
430  unsigned char *buf, size_t buflen )
431 {
432  int ret = 0;
433  size_t plen;
434 
435  if( format != POLARSSL_ECP_PF_UNCOMPRESSED &&
436  format != POLARSSL_ECP_PF_COMPRESSED )
438 
439  /*
440  * Common case: P == 0
441  */
442  if( mpi_cmp_int( &P->Z, 0 ) == 0 )
443  {
444  if( buflen < 1 )
446 
447  buf[0] = 0x00;
448  *olen = 1;
449 
450  return( 0 );
451  }
452 
453  plen = mpi_size( &grp->P );
454 
455  if( format == POLARSSL_ECP_PF_UNCOMPRESSED )
456  {
457  *olen = 2 * plen + 1;
458 
459  if( buflen < *olen )
461 
462  buf[0] = 0x04;
463  MPI_CHK( mpi_write_binary( &P->X, buf + 1, plen ) );
464  MPI_CHK( mpi_write_binary( &P->Y, buf + 1 + plen, plen ) );
465  }
466  else if( format == POLARSSL_ECP_PF_COMPRESSED )
467  {
468  *olen = plen + 1;
469 
470  if( buflen < *olen )
472 
473  buf[0] = 0x02 + mpi_get_bit( &P->Y, 0 );
474  MPI_CHK( mpi_write_binary( &P->X, buf + 1, plen ) );
475  }
476 
477 cleanup:
478  return( ret );
479 }
480 
481 /*
482  * Import a point from unsigned binary data (SEC1 2.3.4)
483  */
484 int ecp_point_read_binary( const ecp_group *grp, ecp_point *pt,
485  const unsigned char *buf, size_t ilen )
486 {
487  int ret;
488  size_t plen;
489 
490  if( buf[0] == 0x00 )
491  {
492  if( ilen == 1 )
493  return( ecp_set_zero( pt ) );
494  else
496  }
497 
498  plen = mpi_size( &grp->P );
499 
500  if( buf[0] != 0x04 )
502 
503  if( ilen != 2 * plen + 1 )
505 
506  MPI_CHK( mpi_read_binary( &pt->X, buf + 1, plen ) );
507  MPI_CHK( mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) );
508  MPI_CHK( mpi_lset( &pt->Z, 1 ) );
509 
510 cleanup:
511  return( ret );
512 }
513 
514 /*
515  * Import a point from a TLS ECPoint record (RFC 4492)
516  * struct {
517  * opaque point <1..2^8-1>;
518  * } ECPoint;
519  */
520 int ecp_tls_read_point( const ecp_group *grp, ecp_point *pt,
521  const unsigned char **buf, size_t buf_len )
522 {
523  unsigned char data_len;
524  const unsigned char *buf_start;
525 
526  /*
527  * We must have at least two bytes (1 for length, at least of for data)
528  */
529  if( buf_len < 2 )
531 
532  data_len = *(*buf)++;
533  if( data_len < 1 || data_len > buf_len - 1 )
535 
536  /*
537  * Save buffer start for read_binary and update buf
538  */
539  buf_start = *buf;
540  *buf += data_len;
541 
542  return ecp_point_read_binary( grp, pt, buf_start, data_len );
543 }
544 
545 /*
546  * Export a point as a TLS ECPoint record (RFC 4492)
547  * struct {
548  * opaque point <1..2^8-1>;
549  * } ECPoint;
550  */
551 int ecp_tls_write_point( const ecp_group *grp, const ecp_point *pt,
552  int format, size_t *olen,
553  unsigned char *buf, size_t blen )
554 {
555  int ret;
556 
557  /*
558  * buffer length must be at least one, for our length byte
559  */
560  if( blen < 1 )
562 
563  if( ( ret = ecp_point_write_binary( grp, pt, format,
564  olen, buf + 1, blen - 1) ) != 0 )
565  return( ret );
566 
567  /*
568  * write length to the first byte and update total length
569  */
570  buf[0] = (unsigned char) *olen;
571  ++*olen;
572 
573  return 0;
574 }
575 
576 /*
577  * Import an ECP group from ASCII strings, case A == -3
578  */
579 int ecp_group_read_string( ecp_group *grp, int radix,
580  const char *p, const char *b,
581  const char *gx, const char *gy, const char *n)
582 {
583  int ret;
584 
585  MPI_CHK( mpi_read_string( &grp->P, radix, p ) );
586  MPI_CHK( mpi_read_string( &grp->B, radix, b ) );
587  MPI_CHK( ecp_point_read_string( &grp->G, radix, gx, gy ) );
588  MPI_CHK( mpi_read_string( &grp->N, radix, n ) );
589 
590  grp->pbits = mpi_msb( &grp->P );
591  grp->nbits = mpi_msb( &grp->N );
592 
593 cleanup:
594  if( ret != 0 )
595  ecp_group_free( grp );
596 
597  return( ret );
598 }
599 
600 /*
601  * Set a group from an ECParameters record (RFC 4492)
602  */
603 int ecp_tls_read_group( ecp_group *grp, const unsigned char **buf, size_t len )
604 {
605  uint16_t tls_id;
606  const ecp_curve_info *curve_info;
607 
608  /*
609  * We expect at least three bytes (see below)
610  */
611  if( len < 3 )
613 
614  /*
615  * First byte is curve_type; only named_curve is handled
616  */
617  if( *(*buf)++ != POLARSSL_ECP_TLS_NAMED_CURVE )
619 
620  /*
621  * Next two bytes are the namedcurve value
622  */
623  tls_id = *(*buf)++;
624  tls_id <<= 8;
625  tls_id |= *(*buf)++;
626 
627  if( ( curve_info = ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
629 
630  return ecp_use_known_dp( grp, curve_info->grp_id );
631 }
632 
633 /*
634  * Write the ECParameters record corresponding to a group (RFC 4492)
635  */
636 int ecp_tls_write_group( const ecp_group *grp, size_t *olen,
637  unsigned char *buf, size_t blen )
638 {
639  const ecp_curve_info *curve_info;
640 
641  if( ( curve_info = ecp_curve_info_from_grp_id( grp->id ) ) == NULL )
643 
644  /*
645  * We are going to write 3 bytes (see below)
646  */
647  *olen = 3;
648  if( blen < *olen )
650 
651  /*
652  * First byte is curve_type, always named_curve
653  */
655 
656  /*
657  * Next two bytes are the namedcurve value
658  */
659  buf[0] = curve_info->tls_id >> 8;
660  buf[1] = curve_info->tls_id & 0xFF;
661 
662  return 0;
663 }
664 
665 /*
666  * Wrapper around fast quasi-modp functions, with fall-back to mpi_mod_mpi.
667  * See the documentation of struct ecp_group.
668  *
669  * This function is in the critial loop for ecp_mul, so pay attention to perf.
670  */
671 static int ecp_modp( mpi *N, const ecp_group *grp )
672 {
673  int ret;
674 
675  if( grp->modp == NULL )
676  return( mpi_mod_mpi( N, N, &grp->P ) );
677 
678  /* N->s < 0 is a much faster test, which fails only if N is 0 */
679  if( ( N->s < 0 && mpi_cmp_int( N, 0 ) != 0 ) ||
680  mpi_msb( N ) > 2 * grp->pbits )
681  {
683  }
684 
685  MPI_CHK( grp->modp( N ) );
686 
687  /* N->s < 0 is a much faster test, which fails only if N is 0 */
688  while( N->s < 0 && mpi_cmp_int( N, 0 ) != 0 )
689  MPI_CHK( mpi_add_mpi( N, N, &grp->P ) );
690 
691  while( mpi_cmp_mpi( N, &grp->P ) >= 0 )
692  /* we known P, N and the result are positive */
693  MPI_CHK( mpi_sub_abs( N, N, &grp->P ) );
694 
695 cleanup:
696  return( ret );
697 }
698 
699 /*
700  * Fast mod-p functions expect their argument to be in the 0..p^2 range.
701  *
702  * In order to guarantee that, we need to ensure that operands of
703  * mpi_mul_mpi are in the 0..p range. So, after each operation we will
704  * bring the result back to this range.
705  *
706  * The following macros are shortcuts for doing that.
707  */
708 
709 /*
710  * Reduce a mpi mod p in-place, general case, to use after mpi_mul_mpi
711  */
712 #if defined(POLARSSL_SELF_TEST)
713 #define INC_MUL_COUNT mul_count++;
714 #else
715 #define INC_MUL_COUNT
716 #endif
717 
718 #define MOD_MUL( N ) do { MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
719  while( 0 )
720 
721 /*
722  * Reduce a mpi mod p in-place, to use after mpi_sub_mpi
723  * N->s < 0 is a very fast test, which fails only if N is 0
724  */
725 #define MOD_SUB( N ) \
726  while( N.s < 0 && mpi_cmp_int( &N, 0 ) != 0 ) \
727  MPI_CHK( mpi_add_mpi( &N, &N, &grp->P ) )
728 
729 /*
730  * Reduce a mpi mod p in-place, to use after mpi_add_mpi and mpi_mul_int.
731  * We known P, N and the result are positive, so sub_abs is correct, and
732  * a bit faster.
733  */
734 #define MOD_ADD( N ) \
735  while( mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
736  MPI_CHK( mpi_sub_abs( &N, &N, &grp->P ) )
737 
738 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
739 /*
740  * For curves in short Weierstrass form, we do all the internal operations in
741  * Jacobian coordinates.
742  *
743  * For multiplication, we'll use a comb method with coutermeasueres against
744  * SPA, hence timing attacks.
745  */
746 
747 /*
748  * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1)
749  * Cost: 1N := 1I + 3M + 1S
750  */
751 static int ecp_normalize_jac( const ecp_group *grp, ecp_point *pt )
752 {
753  int ret;
754  mpi Zi, ZZi;
755 
756  if( mpi_cmp_int( &pt->Z, 0 ) == 0 )
757  return( 0 );
758 
759  mpi_init( &Zi ); mpi_init( &ZZi );
760 
761  /*
762  * X = X / Z^2 mod p
763  */
764  MPI_CHK( mpi_inv_mod( &Zi, &pt->Z, &grp->P ) );
765  MPI_CHK( mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
766  MPI_CHK( mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X );
767 
768  /*
769  * Y = Y / Z^3 mod p
770  */
771  MPI_CHK( mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y );
772  MPI_CHK( mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y );
773 
774  /*
775  * Z = 1
776  */
777  MPI_CHK( mpi_lset( &pt->Z, 1 ) );
778 
779 cleanup:
780 
781  mpi_free( &Zi ); mpi_free( &ZZi );
782 
783  return( ret );
784 }
785 
786 /*
787  * Normalize jacobian coordinates of an array of (pointers to) points,
788  * using Montgomery's trick to perform only one inversion mod P.
789  * (See for example Cohen's "A Course in Computational Algebraic Number
790  * Theory", Algorithm 10.3.4.)
791  *
792  * Warning: fails (returning an error) if one of the points is zero!
793  * This should never happen, see choice of w in ecp_mul_comb().
794  *
795  * Cost: 1N(t) := 1I + (6t - 3)M + 1S
796  */
797 static int ecp_normalize_jac_many( const ecp_group *grp,
798  ecp_point *T[], size_t t_len )
799 {
800  int ret;
801  size_t i;
802  mpi *c, u, Zi, ZZi;
803 
804  if( t_len < 2 )
805  return( ecp_normalize_jac( grp, *T ) );
806 
807  if( ( c = (mpi *) polarssl_malloc( t_len * sizeof( mpi ) ) ) == NULL )
809 
810  mpi_init( &u ); mpi_init( &Zi ); mpi_init( &ZZi );
811  for( i = 0; i < t_len; i++ )
812  mpi_init( &c[i] );
813 
814  /*
815  * c[i] = Z_0 * ... * Z_i
816  */
817  MPI_CHK( mpi_copy( &c[0], &T[0]->Z ) );
818  for( i = 1; i < t_len; i++ )
819  {
820  MPI_CHK( mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );
821  MOD_MUL( c[i] );
822  }
823 
824  /*
825  * u = 1 / (Z_0 * ... * Z_n) mod P
826  */
827  MPI_CHK( mpi_inv_mod( &u, &c[t_len-1], &grp->P ) );
828 
829  for( i = t_len - 1; ; i-- )
830  {
831  /*
832  * Zi = 1 / Z_i mod p
833  * u = 1 / (Z_0 * ... * Z_i) mod P
834  */
835  if( i == 0 ) {
836  MPI_CHK( mpi_copy( &Zi, &u ) );
837  }
838  else
839  {
840  MPI_CHK( mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi );
841  MPI_CHK( mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u );
842  }
843 
844  /*
845  * proceed as in normalize()
846  */
847  MPI_CHK( mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
848  MPI_CHK( mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X );
849  MPI_CHK( mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y );
850  MPI_CHK( mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y );
851 
852  /*
853  * Post-precessing: reclaim some memory by shrinking coordinates
854  * - not storing Z (always 1)
855  * - shrinking other coordinates, but still keeping the same number of
856  * limbs as P, as otherwise it will too likely be regrown too fast.
857  */
858  MPI_CHK( mpi_shrink( &T[i]->X, grp->P.n ) );
859  MPI_CHK( mpi_shrink( &T[i]->Y, grp->P.n ) );
860  mpi_free( &T[i]->Z );
861 
862  if( i == 0 )
863  break;
864  }
865 
866 cleanup:
867 
868  mpi_free( &u ); mpi_free( &Zi ); mpi_free( &ZZi );
869  for( i = 0; i < t_len; i++ )
870  mpi_free( &c[i] );
871  polarssl_free( c );
872 
873  return( ret );
874 }
875 
876 /*
877  * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
878  * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
879  */
880 static int ecp_safe_invert_jac( const ecp_group *grp,
881  ecp_point *Q,
882  unsigned char inv )
883 {
884  int ret;
885  unsigned char nonzero;
886  mpi mQY;
887 
888  mpi_init( &mQY );
889 
890  /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
891  MPI_CHK( mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) );
892  nonzero = mpi_cmp_int( &Q->Y, 0 ) != 0;
893  MPI_CHK( mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) );
894 
895 cleanup:
896  mpi_free( &mQY );
897 
898  return( ret );
899 }
900 
901 /*
902  * Point doubling R = 2 P, Jacobian coordinates
903  *
904  * http://www.hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian/doubling/dbl-2007-bl.op3
905  * with heavy variable renaming, some reordering and one minor modification
906  * (a = 2 * b, c = d - 2a replaced with c = d, c = c - b, c = c - b)
907  * in order to use a lot less intermediate variables (6 vs 25).
908  *
909  * Cost: 1D := 2M + 8S
910  */
911 static int ecp_double_jac( const ecp_group *grp, ecp_point *R,
912  const ecp_point *P )
913 {
914  int ret;
915  mpi T1, T2, T3, X3, Y3, Z3;
916 
917 #if defined(POLARSSL_SELF_TEST)
918  dbl_count++;
919 #endif
920 
921  mpi_init( &T1 ); mpi_init( &T2 ); mpi_init( &T3 );
922  mpi_init( &X3 ); mpi_init( &Y3 ); mpi_init( &Z3 );
923 
924  MPI_CHK( mpi_mul_mpi( &T3, &P->X, &P->X ) ); MOD_MUL( T3 );
925  MPI_CHK( mpi_mul_mpi( &T2, &P->Y, &P->Y ) ); MOD_MUL( T2 );
926  MPI_CHK( mpi_mul_mpi( &Y3, &T2, &T2 ) ); MOD_MUL( Y3 );
927  MPI_CHK( mpi_add_mpi( &X3, &P->X, &T2 ) ); MOD_ADD( X3 );
928  MPI_CHK( mpi_mul_mpi( &X3, &X3, &X3 ) ); MOD_MUL( X3 );
929  MPI_CHK( mpi_sub_mpi( &X3, &X3, &Y3 ) ); MOD_SUB( X3 );
930  MPI_CHK( mpi_sub_mpi( &X3, &X3, &T3 ) ); MOD_SUB( X3 );
931  MPI_CHK( mpi_mul_int( &T1, &X3, 2 ) ); MOD_ADD( T1 );
932  MPI_CHK( mpi_mul_mpi( &Z3, &P->Z, &P->Z ) ); MOD_MUL( Z3 );
933  MPI_CHK( mpi_mul_mpi( &X3, &Z3, &Z3 ) ); MOD_MUL( X3 );
934  MPI_CHK( mpi_mul_int( &T3, &T3, 3 ) ); MOD_ADD( T3 );
935 
936  /* Special case for A = -3 */
937  if( grp->A.p == NULL )
938  {
939  MPI_CHK( mpi_mul_int( &X3, &X3, 3 ) );
940  X3.s = -1; /* mpi_mul_int doesn't handle negative numbers */
941  MOD_SUB( X3 );
942  }
943  else
944  MPI_CHK( mpi_mul_mpi( &X3, &X3, &grp->A ) ); MOD_MUL( X3 );
945 
946  MPI_CHK( mpi_add_mpi( &T3, &T3, &X3 ) ); MOD_ADD( T3 );
947  MPI_CHK( mpi_mul_mpi( &X3, &T3, &T3 ) ); MOD_MUL( X3 );
948  MPI_CHK( mpi_sub_mpi( &X3, &X3, &T1 ) ); MOD_SUB( X3 );
949  MPI_CHK( mpi_sub_mpi( &X3, &X3, &T1 ) ); MOD_SUB( X3 );
950  MPI_CHK( mpi_sub_mpi( &T1, &T1, &X3 ) ); MOD_SUB( T1 );
951  MPI_CHK( mpi_mul_mpi( &T1, &T3, &T1 ) ); MOD_MUL( T1 );
952  MPI_CHK( mpi_mul_int( &T3, &Y3, 8 ) ); MOD_ADD( T3 );
953  MPI_CHK( mpi_sub_mpi( &Y3, &T1, &T3 ) ); MOD_SUB( Y3 );
954  MPI_CHK( mpi_add_mpi( &T1, &P->Y, &P->Z ) ); MOD_ADD( T1 );
955  MPI_CHK( mpi_mul_mpi( &T1, &T1, &T1 ) ); MOD_MUL( T1 );
956  MPI_CHK( mpi_sub_mpi( &T1, &T1, &T2 ) ); MOD_SUB( T1 );
957  MPI_CHK( mpi_sub_mpi( &Z3, &T1, &Z3 ) ); MOD_SUB( Z3 );
958 
959  MPI_CHK( mpi_copy( &R->X, &X3 ) );
960  MPI_CHK( mpi_copy( &R->Y, &Y3 ) );
961  MPI_CHK( mpi_copy( &R->Z, &Z3 ) );
962 
963 cleanup:
964  mpi_free( &T1 ); mpi_free( &T2 ); mpi_free( &T3 );
965  mpi_free( &X3 ); mpi_free( &Y3 ); mpi_free( &Z3 );
966 
967  return( ret );
968 }
969 
970 /*
971  * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
972  *
973  * The coordinates of Q must be normalized (= affine),
974  * but those of P don't need to. R is not normalized.
975  *
976  * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
977  * None of these cases can happen as intermediate step in ecp_mul_comb():
978  * - at each step, P, Q and R are multiples of the base point, the factor
979  * being less than its order, so none of them is zero;
980  * - Q is an odd multiple of the base point, P an even multiple,
981  * due to the choice of precomputed points in the modified comb method.
982  * So branches for these cases do not leak secret information.
983  *
984  * We accept Q->Z being unset (saving memory in tables) as meaning 1.
985  *
986  * Cost: 1A := 8M + 3S
987  */
988 static int ecp_add_mixed( const ecp_group *grp, ecp_point *R,
989  const ecp_point *P, const ecp_point *Q )
990 {
991  int ret;
992  mpi T1, T2, T3, T4, X, Y, Z;
993 
994 #if defined(POLARSSL_SELF_TEST)
995  add_count++;
996 #endif
997 
998  /*
999  * Trivial cases: P == 0 or Q == 0 (case 1)
1000  */
1001  if( mpi_cmp_int( &P->Z, 0 ) == 0 )
1002  return( ecp_copy( R, Q ) );
1003 
1004  if( Q->Z.p != NULL && mpi_cmp_int( &Q->Z, 0 ) == 0 )
1005  return( ecp_copy( R, P ) );
1006 
1007  /*
1008  * Make sure Q coordinates are normalized
1009  */
1010  if( Q->Z.p != NULL && mpi_cmp_int( &Q->Z, 1 ) != 0 )
1012 
1013  mpi_init( &T1 ); mpi_init( &T2 ); mpi_init( &T3 ); mpi_init( &T4 );
1014  mpi_init( &X ); mpi_init( &Y ); mpi_init( &Z );
1015 
1016  MPI_CHK( mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 );
1017  MPI_CHK( mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 );
1018  MPI_CHK( mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 );
1019  MPI_CHK( mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 );
1020  MPI_CHK( mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 );
1021  MPI_CHK( mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 );
1022 
1023  /* Special cases (2) and (3) */
1024  if( mpi_cmp_int( &T1, 0 ) == 0 )
1025  {
1026  if( mpi_cmp_int( &T2, 0 ) == 0 )
1027  {
1028  ret = ecp_double_jac( grp, R, P );
1029  goto cleanup;
1030  }
1031  else
1032  {
1033  ret = ecp_set_zero( R );
1034  goto cleanup;
1035  }
1036  }
1037 
1038  MPI_CHK( mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z );
1039  MPI_CHK( mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 );
1040  MPI_CHK( mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 );
1041  MPI_CHK( mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 );
1042  MPI_CHK( mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 );
1043  MPI_CHK( mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X );
1044  MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X );
1045  MPI_CHK( mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X );
1046  MPI_CHK( mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 );
1047  MPI_CHK( mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 );
1048  MPI_CHK( mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 );
1049  MPI_CHK( mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y );
1050 
1051  MPI_CHK( mpi_copy( &R->X, &X ) );
1052  MPI_CHK( mpi_copy( &R->Y, &Y ) );
1053  MPI_CHK( mpi_copy( &R->Z, &Z ) );
1054 
1055 cleanup:
1056 
1057  mpi_free( &T1 ); mpi_free( &T2 ); mpi_free( &T3 ); mpi_free( &T4 );
1058  mpi_free( &X ); mpi_free( &Y ); mpi_free( &Z );
1059 
1060  return( ret );
1061 }
1062 
1063 /*
1064  * Addition: R = P + Q, result's coordinates normalized
1065  */
1066 int ecp_add( const ecp_group *grp, ecp_point *R,
1067  const ecp_point *P, const ecp_point *Q )
1068 {
1069  int ret;
1070 
1071  if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1073 
1074  MPI_CHK( ecp_add_mixed( grp, R, P, Q ) );
1075  MPI_CHK( ecp_normalize_jac( grp, R ) );
1076 
1077 cleanup:
1078  return( ret );
1079 }
1080 
1081 /*
1082  * Subtraction: R = P - Q, result's coordinates normalized
1083  */
1084 int ecp_sub( const ecp_group *grp, ecp_point *R,
1085  const ecp_point *P, const ecp_point *Q )
1086 {
1087  int ret;
1088  ecp_point mQ;
1089 
1090  ecp_point_init( &mQ );
1091 
1092  if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1094 
1095  /* mQ = - Q */
1096  MPI_CHK( ecp_copy( &mQ, Q ) );
1097  if( mpi_cmp_int( &mQ.Y, 0 ) != 0 )
1098  MPI_CHK( mpi_sub_mpi( &mQ.Y, &grp->P, &mQ.Y ) );
1099 
1100  MPI_CHK( ecp_add_mixed( grp, R, P, &mQ ) );
1101  MPI_CHK( ecp_normalize_jac( grp, R ) );
1102 
1103 cleanup:
1104  ecp_point_free( &mQ );
1105 
1106  return( ret );
1107 }
1108 
1109 /*
1110  * Randomize jacobian coordinates:
1111  * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
1112  * This is sort of the reverse operation of ecp_normalize_jac().
1113  *
1114  * This countermeasure was first suggested in [2].
1115  */
1116 static int ecp_randomize_jac( const ecp_group *grp, ecp_point *pt,
1117  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1118 {
1119  int ret;
1120  mpi l, ll;
1121  size_t p_size = (grp->pbits + 7) / 8;
1122  int count = 0;
1123 
1124  mpi_init( &l ); mpi_init( &ll );
1125 
1126  /* Generate l such that 1 < l < p */
1127  do
1128  {
1129  mpi_fill_random( &l, p_size, f_rng, p_rng );
1130 
1131  while( mpi_cmp_mpi( &l, &grp->P ) >= 0 )
1132  MPI_CHK( mpi_shift_r( &l, 1 ) );
1133 
1134  if( count++ > 10 )
1136  }
1137  while( mpi_cmp_int( &l, 1 ) <= 0 );
1138 
1139  /* Z = l * Z */
1140  MPI_CHK( mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z );
1141 
1142  /* X = l^2 * X */
1143  MPI_CHK( mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll );
1144  MPI_CHK( mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X );
1145 
1146  /* Y = l^3 * Y */
1147  MPI_CHK( mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll );
1148  MPI_CHK( mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y );
1149 
1150 cleanup:
1151  mpi_free( &l ); mpi_free( &ll );
1152 
1153  return( ret );
1154 }
1155 
1156 /*
1157  * Check and define parameters used by the comb method (see below for details)
1158  */
1159 #if POLARSSL_ECP_WINDOW_SIZE < 2 || POLARSSL_ECP_WINDOW_SIZE > 7
1160 #error "POLARSSL_ECP_WINDOW_SIZE out of bounds"
1161 #endif
1162 
1163 /* d = ceil( n / w ) */
1164 #define COMB_MAX_D ( POLARSSL_ECP_MAX_BITS + 1 ) / 2
1165 
1166 /* number of precomputed points */
1167 #define COMB_MAX_PRE ( 1 << ( POLARSSL_ECP_WINDOW_SIZE - 1 ) )
1168 
1169 /*
1170  * Compute the representation of m that will be used with our comb method.
1171  *
1172  * The basic comb method is described in GECC 3.44 for example. We use a
1173  * modified version that provides resistance to SPA by avoiding zero
1174  * digits in the representation as in [3]. We modify the method further by
1175  * requiring that all K_i be odd, which has the small cost that our
1176  * representation uses one more K_i, due to carries.
1177  *
1178  * Also, for the sake of compactness, only the seven low-order bits of x[i]
1179  * are used to represent K_i, and the msb of x[i] encodes the the sign (s_i in
1180  * the paper): it is set if and only if if s_i == -1;
1181  *
1182  * Calling conventions:
1183  * - x is an array of size d + 1
1184  * - w is the size, ie number of teeth, of the comb, and must be between
1185  * 2 and 7 (in practice, between 2 and POLARSSL_ECP_WINDOW_SIZE)
1186  * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d
1187  * (the result will be incorrect if these assumptions are not satisfied)
1188  */
1189 static void ecp_comb_fixed( unsigned char x[], size_t d,
1190  unsigned char w, const mpi *m )
1191 {
1192  size_t i, j;
1193  unsigned char c, cc, adjust;
1194 
1195  memset( x, 0, d+1 );
1196 
1197  /* First get the classical comb values (except for x_d = 0) */
1198  for( i = 0; i < d; i++ )
1199  for( j = 0; j < w; j++ )
1200  x[i] |= mpi_get_bit( m, i + d * j ) << j;
1201 
1202  /* Now make sure x_1 .. x_d are odd */
1203  c = 0;
1204  for( i = 1; i <= d; i++ )
1205  {
1206  /* Add carry and update it */
1207  cc = x[i] & c;
1208  x[i] = x[i] ^ c;
1209  c = cc;
1210 
1211  /* Adjust if needed, avoiding branches */
1212  adjust = 1 - ( x[i] & 0x01 );
1213  c |= x[i] & ( x[i-1] * adjust );
1214  x[i] = x[i] ^ ( x[i-1] * adjust );
1215  x[i-1] |= adjust << 7;
1216  }
1217 }
1218 
1219 /*
1220  * Precompute points for the comb method
1221  *
1222  * If i = i_{w-1} ... i_1 is the binary representation of i, then
1223  * T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P
1224  *
1225  * T must be able to hold 2^{w - 1} elements
1226  *
1227  * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
1228  */
1229 static int ecp_precompute_comb( const ecp_group *grp,
1230  ecp_point T[], const ecp_point *P,
1231  unsigned char w, size_t d )
1232 {
1233  int ret;
1234  unsigned char i, k;
1235  size_t j;
1236  ecp_point *cur, *TT[COMB_MAX_PRE - 1];
1237 
1238  /*
1239  * Set T[0] = P and
1240  * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
1241  */
1242  MPI_CHK( ecp_copy( &T[0], P ) );
1243 
1244  k = 0;
1245  for( i = 1; i < ( 1U << (w-1) ); i <<= 1 )
1246  {
1247  cur = T + i;
1248  MPI_CHK( ecp_copy( cur, T + ( i >> 1 ) ) );
1249  for( j = 0; j < d; j++ )
1250  MPI_CHK( ecp_double_jac( grp, cur, cur ) );
1251 
1252  TT[k++] = cur;
1253  }
1254 
1255  MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1256 
1257  /*
1258  * Compute the remaining ones using the minimal number of additions
1259  * Be careful to update T[2^l] only after using it!
1260  */
1261  k = 0;
1262  for( i = 1; i < ( 1U << (w-1) ); i <<= 1 )
1263  {
1264  j = i;
1265  while( j-- )
1266  {
1267  MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
1268  TT[k++] = &T[i + j];
1269  }
1270  }
1271 
1272  MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1273 
1274 cleanup:
1275  return( ret );
1276 }
1277 
1278 /*
1279  * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
1280  */
1281 static int ecp_select_comb( const ecp_group *grp, ecp_point *R,
1282  const ecp_point T[], unsigned char t_len,
1283  unsigned char i )
1284 {
1285  int ret;
1286  unsigned char ii, j;
1287 
1288  /* Ignore the "sign" bit and scale down */
1289  ii = ( i & 0x7Fu ) >> 1;
1290 
1291  /* Read the whole table to thwart cache-based timing attacks */
1292  for( j = 0; j < t_len; j++ )
1293  {
1294  MPI_CHK( mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) );
1295  MPI_CHK( mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) );
1296  }
1297 
1298  /* Safely invert result if i is "negative" */
1299  MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
1300 
1301 cleanup:
1302  return( ret );
1303 }
1304 
1305 /*
1306  * Core multiplication algorithm for the (modified) comb method.
1307  * This part is actually common with the basic comb method (GECC 3.44)
1308  *
1309  * Cost: d A + d D + 1 R
1310  */
1311 static int ecp_mul_comb_core( const ecp_group *grp, ecp_point *R,
1312  const ecp_point T[], unsigned char t_len,
1313  const unsigned char x[], size_t d,
1314  int (*f_rng)(void *, unsigned char *, size_t),
1315  void *p_rng )
1316 {
1317  int ret;
1318  ecp_point Txi;
1319  size_t i;
1320 
1321  ecp_point_init( &Txi );
1322 
1323  /* Start with a non-zero point and randomize its coordinates */
1324  i = d;
1325  MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) );
1326  MPI_CHK( mpi_lset( &R->Z, 1 ) );
1327  if( f_rng != 0 )
1328  MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
1329 
1330  while( i-- != 0 )
1331  {
1332  MPI_CHK( ecp_double_jac( grp, R, R ) );
1333  MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) );
1334  MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
1335  }
1336 
1337 cleanup:
1338  ecp_point_free( &Txi );
1339 
1340  return( ret );
1341 }
1342 
1343 /*
1344  * Multiplication using the comb method,
1345  * for curves in short Weierstrass form
1346  */
1347 static int ecp_mul_comb( ecp_group *grp, ecp_point *R,
1348  const mpi *m, const ecp_point *P,
1349  int (*f_rng)(void *, unsigned char *, size_t),
1350  void *p_rng )
1351 {
1352  int ret;
1353  unsigned char w, m_is_odd, p_eq_g, pre_len, i;
1354  size_t d;
1355  unsigned char k[COMB_MAX_D + 1];
1356  ecp_point *T;
1357  mpi M, mm;
1358 
1359  mpi_init( &M );
1360  mpi_init( &mm );
1361 
1362  /* we need N to be odd to trnaform m in an odd number, check now */
1363  if( mpi_get_bit( &grp->N, 0 ) != 1 )
1365 
1366  /*
1367  * Minimize the number of multiplications, that is minimize
1368  * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
1369  * (see costs of the various parts, with 1S = 1M)
1370  */
1371  w = grp->nbits >= 384 ? 5 : 4;
1372 
1373  /*
1374  * If P == G, pre-compute a bit more, since this may be re-used later.
1375  * Just adding one avoids upping the cost of the first mul too much,
1376  * and the memory cost too.
1377  */
1378 #if POLARSSL_ECP_FIXED_POINT_OPTIM == 1
1379  p_eq_g = ( mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&
1380  mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 );
1381  if( p_eq_g )
1382  w++;
1383 #else
1384  p_eq_g = 0;
1385 #endif
1386 
1387  /*
1388  * Make sure w is within bounds.
1389  * (The last test is useful only for very small curves in the test suite.)
1390  */
1391  if( w > POLARSSL_ECP_WINDOW_SIZE )
1393  if( w >= grp->nbits )
1394  w = 2;
1395 
1396  /* Other sizes that depend on w */
1397  pre_len = 1U << ( w - 1 );
1398  d = ( grp->nbits + w - 1 ) / w;
1399 
1400  /*
1401  * Prepare precomputed points: if P == G we want to
1402  * use grp->T if already initialized, or initialize it.
1403  */
1404  T = p_eq_g ? grp->T : NULL;
1405 
1406  if( T == NULL )
1407  {
1408  T = (ecp_point *) polarssl_malloc( pre_len * sizeof( ecp_point ) );
1409  if( T == NULL )
1410  {
1412  goto cleanup;
1413  }
1414 
1415  for( i = 0; i < pre_len; i++ )
1416  ecp_point_init( &T[i] );
1417 
1418  MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) );
1419 
1420  if( p_eq_g )
1421  {
1422  grp->T = T;
1423  grp->T_size = pre_len;
1424  }
1425  }
1426 
1427  /*
1428  * Make sure M is odd (M = m or M = N - m, since N is odd)
1429  * using the fact that m * P = - (N - m) * P
1430  */
1431  m_is_odd = ( mpi_get_bit( m, 0 ) == 1 );
1432  MPI_CHK( mpi_copy( &M, m ) );
1433  MPI_CHK( mpi_sub_mpi( &mm, &grp->N, m ) );
1434  MPI_CHK( mpi_safe_cond_assign( &M, &mm, ! m_is_odd ) );
1435 
1436  /*
1437  * Go for comb multiplication, R = M * P
1438  */
1439  ecp_comb_fixed( k, d, w, &M );
1440  MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) );
1441 
1442  /*
1443  * Now get m * P from M * P and normalize it
1444  */
1445  MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) );
1446  MPI_CHK( ecp_normalize_jac( grp, R ) );
1447 
1448 cleanup:
1449 
1450  if( T != NULL && ! p_eq_g )
1451  {
1452  for( i = 0; i < pre_len; i++ )
1453  ecp_point_free( &T[i] );
1454  polarssl_free( T );
1455  }
1456 
1457  mpi_free( &M );
1458  mpi_free( &mm );
1459 
1460  if( ret != 0 )
1461  ecp_point_free( R );
1462 
1463  return( ret );
1464 }
1465 
1466 #endif /* POLARSSL_ECP_SHORT_WEIERSTRASS */
1467 
1468 #if defined(POLARSSL_ECP_MONTGOMERY)
1469 /*
1470  * For Montgomery curves, we do all the internal arithmetic in projective
1471  * coordinates. Import/export of points uses only the x coordinates, which is
1472  * internaly represented as X / Z.
1473  *
1474  * For scalar multiplication, we'll use a Montgomery ladder.
1475  */
1476 
1477 /*
1478  * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
1479  * Cost: 1M + 1I
1480  */
1481 static int ecp_normalize_mxz( const ecp_group *grp, ecp_point *P )
1482 {
1483  int ret;
1484 
1485  MPI_CHK( mpi_inv_mod( &P->Z, &P->Z, &grp->P ) );
1486  MPI_CHK( mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X );
1487  MPI_CHK( mpi_lset( &P->Z, 1 ) );
1488 
1489 cleanup:
1490  return( ret );
1491 }
1492 
1493 /*
1494  * Randomize projective x/z coordinates:
1495  * (X, Z) -> (l X, l Z) for random l
1496  * This is sort of the reverse operation of ecp_normalize_mxz().
1497  *
1498  * This countermeasure was first suggested in [2].
1499  * Cost: 2M
1500  */
1501 static int ecp_randomize_mxz( const ecp_group *grp, ecp_point *P,
1502  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1503 {
1504  int ret;
1505  mpi l;
1506  size_t p_size = (grp->pbits + 7) / 8;
1507  int count = 0;
1508 
1509  mpi_init( &l );
1510 
1511  /* Generate l such that 1 < l < p */
1512  do
1513  {
1514  mpi_fill_random( &l, p_size, f_rng, p_rng );
1515 
1516  while( mpi_cmp_mpi( &l, &grp->P ) >= 0 )
1517  MPI_CHK( mpi_shift_r( &l, 1 ) );
1518 
1519  if( count++ > 10 )
1521  }
1522  while( mpi_cmp_int( &l, 1 ) <= 0 );
1523 
1524  MPI_CHK( mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X );
1525  MPI_CHK( mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z );
1526 
1527 cleanup:
1528  mpi_free( &l );
1529 
1530  return( ret );
1531 }
1532 
1533 /*
1534  * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
1535  * for Montgomery curves in x/z coordinates.
1536  *
1537  * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
1538  * with
1539  * d = X1
1540  * P = (X2, Z2)
1541  * Q = (X3, Z3)
1542  * R = (X4, Z4)
1543  * S = (X5, Z5)
1544  * and eliminating temporary variables tO, ..., t4.
1545  *
1546  * Cost: 5M + 4S
1547  */
1548 static int ecp_double_add_mxz( const ecp_group *grp,
1549  ecp_point *R, ecp_point *S,
1550  const ecp_point *P, const ecp_point *Q,
1551  const mpi *d )
1552 {
1553  int ret;
1554  mpi A, AA, B, BB, E, C, D, DA, CB;
1555 
1556  mpi_init( &A ); mpi_init( &AA ); mpi_init( &B );
1557  mpi_init( &BB ); mpi_init( &E ); mpi_init( &C );
1558  mpi_init( &D ); mpi_init( &DA ); mpi_init( &CB );
1559 
1560  MPI_CHK( mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A );
1561  MPI_CHK( mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA );
1562  MPI_CHK( mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B );
1563  MPI_CHK( mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB );
1564  MPI_CHK( mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E );
1565  MPI_CHK( mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C );
1566  MPI_CHK( mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D );
1567  MPI_CHK( mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA );
1568  MPI_CHK( mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB );
1569  MPI_CHK( mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X );
1570  MPI_CHK( mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X );
1571  MPI_CHK( mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z );
1572  MPI_CHK( mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z );
1573  MPI_CHK( mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z );
1574  MPI_CHK( mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X );
1575  MPI_CHK( mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z );
1576  MPI_CHK( mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z );
1577  MPI_CHK( mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z );
1578 
1579 cleanup:
1580  mpi_free( &A ); mpi_free( &AA ); mpi_free( &B );
1581  mpi_free( &BB ); mpi_free( &E ); mpi_free( &C );
1582  mpi_free( &D ); mpi_free( &DA ); mpi_free( &CB );
1583 
1584  return( ret );
1585 }
1586 
1587 /*
1588  * Multiplication with Montgomery ladder in x/z coordinates,
1589  * for curves in Montgomery form
1590  */
1591 static int ecp_mul_mxz( ecp_group *grp, ecp_point *R,
1592  const mpi *m, const ecp_point *P,
1593  int (*f_rng)(void *, unsigned char *, size_t),
1594  void *p_rng )
1595 {
1596  int ret;
1597  size_t i;
1598  unsigned char b;
1599  ecp_point RP;
1600  mpi PX;
1601 
1602  ecp_point_init( &RP ); mpi_init( &PX );
1603 
1604  /* Save PX and read from P before writing to R, in case P == R */
1605  MPI_CHK( mpi_copy( &PX, &P->X ) );
1606  MPI_CHK( ecp_copy( &RP, P ) );
1607 
1608  /* Set R to zero in modified x/z coordinates */
1609  MPI_CHK( mpi_lset( &R->X, 1 ) );
1610  MPI_CHK( mpi_lset( &R->Z, 0 ) );
1611  mpi_free( &R->Y );
1612 
1613  /* RP.X might be sligtly larger than P, so reduce it */
1614  MOD_ADD( RP.X );
1615 
1616  /* Randomize coordinates of the starting point */
1617  if( f_rng != NULL )
1618  MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
1619 
1620  /* Loop invariant: R = result so far, RP = R + P */
1621  i = mpi_msb( m ); /* one past the (zero-based) most significant bit */
1622  while( i-- > 0 )
1623  {
1624  b = mpi_get_bit( m, i );
1625  /*
1626  * if (b) R = 2R + P else R = 2R,
1627  * which is:
1628  * if (b) double_add( RP, R, RP, R )
1629  * else double_add( R, RP, R, RP )
1630  * but using safe conditional swaps to avoid leaks
1631  */
1632  MPI_CHK( mpi_safe_cond_swap( &R->X, &RP.X, b ) );
1633  MPI_CHK( mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
1634  MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
1635  MPI_CHK( mpi_safe_cond_swap( &R->X, &RP.X, b ) );
1636  MPI_CHK( mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
1637  }
1638 
1639  MPI_CHK( ecp_normalize_mxz( grp, R ) );
1640 
1641 cleanup:
1642  ecp_point_free( &RP ); mpi_free( &PX );
1643 
1644  return( ret );
1645 }
1646 
1647 #endif /* POLARSSL_ECP_MONTGOMERY */
1648 
1649 /*
1650  * Multiplication R = m * P
1651  */
1652 int ecp_mul( ecp_group *grp, ecp_point *R,
1653  const mpi *m, const ecp_point *P,
1654  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1655 {
1656  int ret;
1657 
1658  /* Common sanity checks */
1659  if( mpi_cmp_int( &P->Z, 1 ) != 0 )
1661 
1662  if( ( ret = ecp_check_privkey( grp, m ) ) != 0 ||
1663  ( ret = ecp_check_pubkey( grp, P ) ) != 0 )
1664  return( ret );
1665 
1666 #if defined(POLARSSL_ECP_MONTGOMERY)
1667  if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1668  return( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) );
1669 #endif
1670 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1671  if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1672  return( ecp_mul_comb( grp, R, m, P, f_rng, p_rng ) );
1673 #endif
1675 }
1676 
1677 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1678 /*
1679  * Check that an affine point is valid as a public key,
1680  * short weierstrass curves (SEC1 3.2.3.1)
1681  */
1682 static int ecp_check_pubkey_sw( const ecp_group *grp, const ecp_point *pt )
1683 {
1684  int ret;
1685  mpi YY, RHS;
1686 
1687  /* pt coordinates must be normalized for our checks */
1688  if( mpi_cmp_int( &pt->X, 0 ) < 0 ||
1689  mpi_cmp_int( &pt->Y, 0 ) < 0 ||
1690  mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 ||
1691  mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 )
1692  return( POLARSSL_ERR_ECP_INVALID_KEY );
1693 
1694  mpi_init( &YY ); mpi_init( &RHS );
1695 
1696  /*
1697  * YY = Y^2
1698  * RHS = X (X^2 + A) + B = X^3 + A X + B
1699  */
1700  MPI_CHK( mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY );
1701  MPI_CHK( mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS );
1702 
1703  /* Special case for A = -3 */
1704  if( grp->A.p == NULL )
1705  {
1706  MPI_CHK( mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS );
1707  }
1708  else
1709  {
1710  MPI_CHK( mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS );
1711  }
1712 
1713  MPI_CHK( mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS );
1714  MPI_CHK( mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS );
1715 
1716  if( mpi_cmp_mpi( &YY, &RHS ) != 0 )
1718 
1719 cleanup:
1720 
1721  mpi_free( &YY ); mpi_free( &RHS );
1722 
1723  return( ret );
1724 }
1725 #endif /* POLARSSL_ECP_SHORT_WEIERSTRASS */
1726 
1727 
1728 #if defined(POLARSSL_ECP_MONTGOMERY)
1729 /*
1730  * Check validity of a public key for Montgomery curves with x-only schemes
1731  */
1732 static int ecp_check_pubkey_mx( const ecp_group *grp, const ecp_point *pt )
1733 {
1734  /* [M255 p. 5] Just check X is the correct number of bytes */
1735  if( mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 )
1736  return( POLARSSL_ERR_ECP_INVALID_KEY );
1737 
1738  return( 0 );
1739 }
1740 #endif /* POLARSSL_ECP_MONTGOMERY */
1741 
1742 /*
1743  * Check that a point is valid as a public key
1744  */
1745 int ecp_check_pubkey( const ecp_group *grp, const ecp_point *pt )
1746 {
1747  /* Must use affine coordinates */
1748  if( mpi_cmp_int( &pt->Z, 1 ) != 0 )
1749  return( POLARSSL_ERR_ECP_INVALID_KEY );
1750 
1751 #if defined(POLARSSL_ECP_MONTGOMERY)
1752  if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1753  return( ecp_check_pubkey_mx( grp, pt ) );
1754 #endif
1755 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1756  if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1757  return( ecp_check_pubkey_sw( grp, pt ) );
1758 #endif
1760 }
1761 
1762 /*
1763  * Check that an mpi is valid as a private key
1764  */
1765 int ecp_check_privkey( const ecp_group *grp, const mpi *d )
1766 {
1767 #if defined(POLARSSL_ECP_MONTGOMERY)
1768  if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1769  {
1770  /* see [M255] page 5 */
1771  if( mpi_get_bit( d, 0 ) != 0 ||
1772  mpi_get_bit( d, 1 ) != 0 ||
1773  mpi_get_bit( d, 2 ) != 0 ||
1774  mpi_msb( d ) - 1 != grp->nbits ) /* mpi_msb is one-based! */
1775  return( POLARSSL_ERR_ECP_INVALID_KEY );
1776  else
1777  return( 0 );
1778  }
1779 #endif /* POLARSSL_ECP_MONTGOMERY */
1780 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1781  if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1782  {
1783  /* see SEC1 3.2 */
1784  if( mpi_cmp_int( d, 1 ) < 0 ||
1785  mpi_cmp_mpi( d, &grp->N ) >= 0 )
1786  return( POLARSSL_ERR_ECP_INVALID_KEY );
1787  else
1788  return( 0 );
1789  }
1790 #endif /* POLARSSL_ECP_SHORT_WEIERSTRASS */
1791 
1793 }
1794 
1795 /*
1796  * Generate a keypair
1797  */
1798 int ecp_gen_keypair( ecp_group *grp, mpi *d, ecp_point *Q,
1799  int (*f_rng)(void *, unsigned char *, size_t),
1800  void *p_rng )
1801 {
1802  int ret;
1803  size_t n_size = (grp->nbits + 7) / 8;
1804 
1805 #if defined(POLARSSL_ECP_MONTGOMERY)
1806  if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1807  {
1808  /* [M225] page 5 */
1809  size_t b;
1810 
1811  MPI_CHK( mpi_fill_random( d, n_size, f_rng, p_rng ) );
1812 
1813  /* Make sure the most significant bit is nbits */
1814  b = mpi_msb( d ) - 1; /* mpi_msb is one-based */
1815  if( b > grp->nbits )
1816  MPI_CHK( mpi_shift_r( d, b - grp->nbits ) );
1817  else
1818  MPI_CHK( mpi_set_bit( d, grp->nbits, 1 ) );
1819 
1820  /* Make sure the last three bits are unset */
1821  MPI_CHK( mpi_set_bit( d, 0, 0 ) );
1822  MPI_CHK( mpi_set_bit( d, 1, 0 ) );
1823  MPI_CHK( mpi_set_bit( d, 2, 0 ) );
1824  }
1825  else
1826 #endif /* POLARSSL_ECP_MONTGOMERY */
1827 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1828  if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1829  {
1830  /* SEC1 3.2.1: Generate d such that 1 <= n < N */
1831  int count = 0;
1832  unsigned char rnd[POLARSSL_ECP_MAX_BYTES];
1833 
1834  /*
1835  * Match the procedure given in RFC 6979 (deterministic ECDSA):
1836  * - use the same byte ordering;
1837  * - keep the leftmost nbits bits of the generated octet string;
1838  * - try until result is in the desired range.
1839  * This also avoids any biais, which is especially important for ECDSA.
1840  */
1841  do
1842  {
1843  MPI_CHK( f_rng( p_rng, rnd, n_size ) );
1844  MPI_CHK( mpi_read_binary( d, rnd, n_size ) );
1845  MPI_CHK( mpi_shift_r( d, 8 * n_size - grp->nbits ) );
1846 
1847  /*
1848  * Each try has at worst a probability 1/2 of failing (the msb has
1849  * a probability 1/2 of being 0, and then the result will be < N),
1850  * so after 30 tries failure probability is a most 2**(-30).
1851  *
1852  * For most curves, 1 try is enough with overwhelming probability,
1853  * since N starts with a lot of 1s in binary, but some curves
1854  * such as secp224k1 are actually very close to the worst case.
1855  */
1856  if( ++count > 30 )
1858  }
1859  while( mpi_cmp_int( d, 1 ) < 0 ||
1860  mpi_cmp_mpi( d, &grp->N ) >= 0 );
1861  }
1862  else
1863 #endif /* POLARSSL_ECP_SHORT_WEIERSTRASS */
1865 
1866 cleanup:
1867  if( ret != 0 )
1868  return( ret );
1869 
1870  return( ecp_mul( grp, Q, d, &grp->G, f_rng, p_rng ) );
1871 }
1872 
1873 /*
1874  * Generate a keypair, prettier wrapper
1875  */
1876 int ecp_gen_key( ecp_group_id grp_id, ecp_keypair *key,
1877  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1878 {
1879  int ret;
1880 
1881  if( ( ret = ecp_use_known_dp( &key->grp, grp_id ) ) != 0 )
1882  return( ret );
1883 
1884  return( ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) );
1885 }
1886 
1887 #if defined(POLARSSL_SELF_TEST)
1888 
1889 /*
1890  * Checkup routine
1891  */
1892 int ecp_self_test( int verbose )
1893 {
1894  int ret;
1895  size_t i;
1896  ecp_group grp;
1897  ecp_point R, P;
1898  mpi m;
1899  unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
1900  /* exponents especially adapted for secp192r1 */
1901  const char *exponents[] =
1902  {
1903  "000000000000000000000000000000000000000000000001", /* one */
1904  "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */
1905  "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
1906  "400000000000000000000000000000000000000000000000", /* one and zeros */
1907  "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
1908  "555555555555555555555555555555555555555555555555", /* 101010... */
1909  };
1910 
1911  ecp_group_init( &grp );
1912  ecp_point_init( &R );
1913  ecp_point_init( &P );
1914  mpi_init( &m );
1915 
1916  /* Use secp192r1 if available, or any available curve */
1917 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
1919 #else
1920  MPI_CHK( ecp_use_known_dp( &grp, ecp_curve_list()->grp_id ) );
1921 #endif
1922 
1923  if( verbose != 0 )
1924  polarssl_printf( " ECP test #1 (constant op_count, base point G): " );
1925 
1926  /* Do a dummy multiplication first to trigger precomputation */
1927  MPI_CHK( mpi_lset( &m, 2 ) );
1928  MPI_CHK( ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) );
1929 
1930  add_count = 0;
1931  dbl_count = 0;
1932  mul_count = 0;
1933  MPI_CHK( mpi_read_string( &m, 16, exponents[0] ) );
1934  MPI_CHK( ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
1935 
1936  for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
1937  {
1938  add_c_prev = add_count;
1939  dbl_c_prev = dbl_count;
1940  mul_c_prev = mul_count;
1941  add_count = 0;
1942  dbl_count = 0;
1943  mul_count = 0;
1944 
1945  MPI_CHK( mpi_read_string( &m, 16, exponents[i] ) );
1946  MPI_CHK( ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
1947 
1948  if( add_count != add_c_prev ||
1949  dbl_count != dbl_c_prev ||
1950  mul_count != mul_c_prev )
1951  {
1952  if( verbose != 0 )
1953  polarssl_printf( "failed (%u)\n", (unsigned int) i );
1954 
1955  ret = 1;
1956  goto cleanup;
1957  }
1958  }
1959 
1960  if( verbose != 0 )
1961  polarssl_printf( "passed\n" );
1962 
1963  if( verbose != 0 )
1964  polarssl_printf( " ECP test #2 (constant op_count, other point): " );
1965  /* We computed P = 2G last time, use it */
1966 
1967  add_count = 0;
1968  dbl_count = 0;
1969  mul_count = 0;
1970  MPI_CHK( mpi_read_string( &m, 16, exponents[0] ) );
1971  MPI_CHK( ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
1972 
1973  for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
1974  {
1975  add_c_prev = add_count;
1976  dbl_c_prev = dbl_count;
1977  mul_c_prev = mul_count;
1978  add_count = 0;
1979  dbl_count = 0;
1980  mul_count = 0;
1981 
1982  MPI_CHK( mpi_read_string( &m, 16, exponents[i] ) );
1983  MPI_CHK( ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
1984 
1985  if( add_count != add_c_prev ||
1986  dbl_count != dbl_c_prev ||
1987  mul_count != mul_c_prev )
1988  {
1989  if( verbose != 0 )
1990  polarssl_printf( "failed (%u)\n", (unsigned int) i );
1991 
1992  ret = 1;
1993  goto cleanup;
1994  }
1995  }
1996 
1997  if( verbose != 0 )
1998  polarssl_printf( "passed\n" );
1999 
2000 cleanup:
2001 
2002  if( ret < 0 && verbose != 0 )
2003  polarssl_printf( "Unexpected error, return code = %08X\n", ret );
2004 
2005  ecp_group_free( &grp );
2006  ecp_point_free( &R );
2007  ecp_point_free( &P );
2008  mpi_free( &m );
2009 
2010  if( verbose != 0 )
2011  polarssl_printf( "\n" );
2012 
2013  return( ret );
2014 }
2015 
2016 #endif /* POLARSSL_SELF_TEST */
2017 
2018 #endif /* POLARSSL_ECP_C */
int mpi_cmp_int(const mpi *X, t_sint z)
Compare signed values.
size_t pbits
Definition: ecp.h:144
#define POLARSSL_ECP_TLS_NAMED_CURVE
ECCurveType&#39;s named_curve.
Definition: ecp.h:239
int mpi_shrink(mpi *X, size_t nblimbs)
Resize down, keeping at least the specified number of limbs.
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.
int mpi_safe_cond_assign(mpi *X, const mpi *Y, unsigned char assign)
Safe conditional assignement X = Y if assign is 1.
#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.
ecp_group_id grp_id
Definition: ecp.h:89
#define POLARSSL_ECP_PF_COMPRESSED
Compressed point format.
Definition: ecp.h:234
const ecp_curve_info * ecp_curve_list(void)
Get the list of supported curves in order of preferrence (full information)
const char * name
Definition: ecp.h:92
int ecp_self_test(int verbose)
Checkup routine.
Elliptic curves over GF(p)
int s
Definition: bignum.h:183
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:139
ecp_group grp
Definition: ecp.h:165
#define POLARSSL_ERR_ECP_MALLOC_FAILED
Memory allocation failed.
Definition: ecp.h:39
int(* modp)(mpi *)
Definition: ecp.h:147
#define polarssl_free
Definition: platform.h:91
#define POLARSSL_ECP_PF_UNCOMPRESSED
Uncompressed point format.
Definition: ecp.h:233
ECP group structure.
Definition: ecp.h:136
Configuration options (set of defines)
unsigned int h
Definition: ecp.h:146
ECP key pair structure.
Definition: ecp.h:163
mpi d
Definition: ecp.h:166
int mpi_lset(mpi *X, t_sint z)
Set value from integer.
MPI structure.
Definition: bignum.h:181
PolarSSL Platform abstraction layer.
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:106
int mpi_cmp_mpi(const mpi *X, const mpi *Y)
Compare signed values.
#define POLARSSL_ECP_WINDOW_SIZE
Maximum window size used.
Definition: ecp.h:210
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
#define POLARSSL_ECP_DP_MAX
Number of supported curves (plus one for NONE).
Definition: ecp.h:82
int mpi_add_mpi(mpi *X, const mpi *A, const mpi *B)
Signed addition: X = A + B.
int ecp_gen_key(ecp_group_id grp_id, ecp_keypair *key, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Generate a keypair.
ecp_point G
Definition: ecp.h:142
ecp_group_id id
Definition: ecp.h:138
ECP point structure (jacobian coordinates)
Definition: ecp.h:104
size_t T_size
Definition: ecp.h:152
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:141
mpi N
Definition: ecp.h:143
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: despite the functon signature, b is treated as a t_uint...
void ecp_group_free(ecp_group *grp)
Free the components of an ECP group.
Curve information for use by other modules.
Definition: ecp.h:87
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.
#define POLARSSL_ECP_MAX_BYTES
Definition: ecp.h:186
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_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:185
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:140
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:57
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:145
#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:107
int mpi_copy(mpi *X, const mpi *Y)
Copy the contents of Y into X.
size_t n
Definition: bignum.h:184
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.
#define polarssl_printf
Definition: platform.h:109
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:167
mpi Z
Definition: ecp.h:108
uint16_t tls_id
Definition: ecp.h:90
int mpi_safe_cond_swap(mpi *X, mpi *Y, unsigned char assign)
Safe conditional swap X &lt;-&gt; Y if swap is 1.
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.
const ecp_curve_info * ecp_curve_info_from_name(const char *name)
Get curve information from a human-readable name.
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.
#define polarssl_malloc
Definition: platform.h:90
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.
int mpi_set_bit(mpi *X, size_t pos, unsigned char val)
Set a bit of X to a specific value of 0 or 1.
ecp_point * T
Definition: ecp.h:151
int mpi_sub_int(mpi *X, const mpi *A, t_sint b)
Signed subtraction: X = A - b.
#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.
const ecp_group_id * ecp_grp_id_list(void)
Get the list of supported curves in order of preferrence (grp_id only)
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:65
void ecp_point_free(ecp_point *pt)
Free the components of a point.