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