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