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