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