projects / reactos.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
[MBEDTLS] Update to version 2.7.9. CORE-15280
[reactos.git] / dll / 3rdparty / mbedtls / ecp.c
1 /*
2 * Elliptic curves over GF(p): generic functions
3 *
4 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
5 * SPDX-License-Identifier: GPL-2.0
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License along
18 * with this program; if not, write to the Free Software Foundation, Inc.,
19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * This file is part of mbed TLS (https://tls.mbed.org)
22 */
23
24 /*
25 * References:
26 *
27 * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
28 * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
29 * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
30 * RFC 4492 for the related TLS structures and constants
31 *
32 * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf
33 *
34 * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
35 * for elliptic curve cryptosystems. In : Cryptographic Hardware and
36 * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
37 * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
38 *
39 * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
40 * render ECC resistant against Side Channel Attacks. IACR Cryptology
41 * ePrint Archive, 2004, vol. 2004, p. 342.
42 * <http://eprint.iacr.org/2004/342.pdf>
43 */
44
45 #if !defined(MBEDTLS_CONFIG_FILE)
46 #include "mbedtls/config.h"
47 #else
48 #include MBEDTLS_CONFIG_FILE
49 #endif
50
51 #if defined(MBEDTLS_ECP_C)
52
53 #include "mbedtls/ecp.h"
54 #include "mbedtls/threading.h"
55
56 #include <string.h>
57
58 #if !defined(MBEDTLS_ECP_ALT)
59
60 #if defined(MBEDTLS_PLATFORM_C)
61 #include "mbedtls/platform.h"
62 #else
63 #include <stdlib.h>
64 #include <stdio.h>
65 #define mbedtls_printf printf
66 #define mbedtls_calloc calloc
67 #define mbedtls_free free
68 #endif
69
70 #include "mbedtls/ecp_internal.h"
71
72 #if ( defined(__ARMCC_VERSION) || defined(_MSC_VER) ) && \
73 !defined(inline) && !defined(__cplusplus)
74 #define inline __inline
75 #endif
76
77 /* Implementation that should never be optimized out by the compiler */
78 static void mbedtls_zeroize( void *v, size_t n ) {
79 volatile unsigned char *p = v; while( n-- ) *p++ = 0;
80 }
81
82 #if defined(MBEDTLS_SELF_TEST)
83 /*
84 * Counts of point addition and doubling, and field multiplications.
85 * Used to test resistance of point multiplication to simple timing attacks.
86 */
87 static unsigned long add_count, dbl_count, mul_count;
88 #endif
89
90 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) || \
91 defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) || \
92 defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) || \
93 defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) || \
94 defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) || \
95 defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) || \
96 defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) || \
97 defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) || \
98 defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) || \
99 defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) || \
100 defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
101 #define ECP_SHORTWEIERSTRASS
102 #endif
103
104 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
105 #define ECP_MONTGOMERY
106 #endif
107
108 /*
109 * Curve types: internal for now, might be exposed later
110 */
111 typedef enum
112 {
113 ECP_TYPE_NONE = 0,
114 ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */
115 ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */
116 } ecp_curve_type;
117
118 /*
119 * List of supported curves:
120 * - internal ID
121 * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
122 * - size in bits
123 * - readable name
124 *
125 * Curves are listed in order: largest curves first, and for a given size,
126 * fastest curves first. This provides the default order for the SSL module.
127 *
128 * Reminder: update profiles in x509_crt.c when adding a new curves!
129 */
130 static const mbedtls_ecp_curve_info ecp_supported_curves[] =
131 {
132 #if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
133 { MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" },
134 #endif
135 #if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
136 { MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" },
137 #endif
138 #if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
139 { MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" },
140 #endif
141 #if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
142 { MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" },
143 #endif
144 #if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
145 { MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" },
146 #endif
147 #if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
148 { MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" },
149 #endif
150 #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
151 { MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" },
152 #endif
153 #if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
154 { MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" },
155 #endif
156 #if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
157 { MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" },
158 #endif
159 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
160 { MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" },
161 #endif
162 #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
163 { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" },
164 #endif
165 { MBEDTLS_ECP_DP_NONE, 0, 0, NULL },
166 };
167
168 #define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \
169 sizeof( ecp_supported_curves[0] )
170
171 static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
172
173 /*
174 * List of supported curves and associated info
175 */
176 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void )
177 {
178 return( ecp_supported_curves );
179 }
180
181 /*
182 * List of supported curves, group ID only
183 */
184 const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void )
185 {
186 static int init_done = 0;
187
188 if( ! init_done )
189 {
190 size_t i = 0;
191 const mbedtls_ecp_curve_info *curve_info;
192
193 for( curve_info = mbedtls_ecp_curve_list();
194 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
195 curve_info++ )
196 {
197 ecp_supported_grp_id[i++] = curve_info->grp_id;
198 }
199 ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
200
201 init_done = 1;
202 }
203
204 return( ecp_supported_grp_id );
205 }
206
207 /*
208 * Get the curve info for the internal identifier
209 */
210 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id )
211 {
212 const mbedtls_ecp_curve_info *curve_info;
213
214 for( curve_info = mbedtls_ecp_curve_list();
215 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
216 curve_info++ )
217 {
218 if( curve_info->grp_id == grp_id )
219 return( curve_info );
220 }
221
222 return( NULL );
223 }
224
225 /*
226 * Get the curve info from the TLS identifier
227 */
228 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id )
229 {
230 const mbedtls_ecp_curve_info *curve_info;
231
232 for( curve_info = mbedtls_ecp_curve_list();
233 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
234 curve_info++ )
235 {
236 if( curve_info->tls_id == tls_id )
237 return( curve_info );
238 }
239
240 return( NULL );
241 }
242
243 /*
244 * Get the curve info from the name
245 */
246 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name )
247 {
248 const mbedtls_ecp_curve_info *curve_info;
249
250 for( curve_info = mbedtls_ecp_curve_list();
251 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
252 curve_info++ )
253 {
254 if( strcmp( curve_info->name, name ) == 0 )
255 return( curve_info );
256 }
257
258 return( NULL );
259 }
260
261 /*
262 * Get the type of a curve
263 */
264 static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp )
265 {
266 if( grp->G.X.p == NULL )
267 return( ECP_TYPE_NONE );
268
269 if( grp->G.Y.p == NULL )
270 return( ECP_TYPE_MONTGOMERY );
271 else
272 return( ECP_TYPE_SHORT_WEIERSTRASS );
273 }
274
275 /*
276 * Initialize (the components of) a point
277 */
278 void mbedtls_ecp_point_init( mbedtls_ecp_point *pt )
279 {
280 if( pt == NULL )
281 return;
282
283 mbedtls_mpi_init( &pt->X );
284 mbedtls_mpi_init( &pt->Y );
285 mbedtls_mpi_init( &pt->Z );
286 }
287
288 /*
289 * Initialize (the components of) a group
290 */
291 void mbedtls_ecp_group_init( mbedtls_ecp_group *grp )
292 {
293 if( grp == NULL )
294 return;
295
296 memset( grp, 0, sizeof( mbedtls_ecp_group ) );
297 }
298
299 /*
300 * Initialize (the components of) a key pair
301 */
302 void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key )
303 {
304 if( key == NULL )
305 return;
306
307 mbedtls_ecp_group_init( &key->grp );
308 mbedtls_mpi_init( &key->d );
309 mbedtls_ecp_point_init( &key->Q );
310 }
311
312 /*
313 * Unallocate (the components of) a point
314 */
315 void mbedtls_ecp_point_free( mbedtls_ecp_point *pt )
316 {
317 if( pt == NULL )
318 return;
319
320 mbedtls_mpi_free( &( pt->X ) );
321 mbedtls_mpi_free( &( pt->Y ) );
322 mbedtls_mpi_free( &( pt->Z ) );
323 }
324
325 /*
326 * Unallocate (the components of) a group
327 */
328 void mbedtls_ecp_group_free( mbedtls_ecp_group *grp )
329 {
330 size_t i;
331
332 if( grp == NULL )
333 return;
334
335 if( grp->h != 1 )
336 {
337 mbedtls_mpi_free( &grp->P );
338 mbedtls_mpi_free( &grp->A );
339 mbedtls_mpi_free( &grp->B );
340 mbedtls_ecp_point_free( &grp->G );
341 mbedtls_mpi_free( &grp->N );
342 }
343
344 if( grp->T != NULL )
345 {
346 for( i = 0; i < grp->T_size; i++ )
347 mbedtls_ecp_point_free( &grp->T[i] );
348 mbedtls_free( grp->T );
349 }
350
351 mbedtls_zeroize( grp, sizeof( mbedtls_ecp_group ) );
352 }
353
354 /*
355 * Unallocate (the components of) a key pair
356 */
357 void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key )
358 {
359 if( key == NULL )
360 return;
361
362 mbedtls_ecp_group_free( &key->grp );
363 mbedtls_mpi_free( &key->d );
364 mbedtls_ecp_point_free( &key->Q );
365 }
366
367 /*
368 * Copy the contents of a point
369 */
370 int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
371 {
372 int ret;
373
374 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X, &Q->X ) );
375 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y, &Q->Y ) );
376 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z, &Q->Z ) );
377
378 cleanup:
379 return( ret );
380 }
381
382 /*
383 * Copy the contents of a group object
384 */
385 int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src )
386 {
387 return mbedtls_ecp_group_load( dst, src->id );
388 }
389
390 /*
391 * Set point to zero
392 */
393 int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt )
394 {
395 int ret;
396
397 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) );
398 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y , 1 ) );
399 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 0 ) );
400
401 cleanup:
402 return( ret );
403 }
404
405 /*
406 * Tell if a point is zero
407 */
408 int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt )
409 {
410 return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 );
411 }
412
413 /*
414 * Compare two points lazily
415 */
416 int mbedtls_ecp_point_cmp( const mbedtls_ecp_point *P,
417 const mbedtls_ecp_point *Q )
418 {
419 if( mbedtls_mpi_cmp_mpi( &P->X, &Q->X ) == 0 &&
420 mbedtls_mpi_cmp_mpi( &P->Y, &Q->Y ) == 0 &&
421 mbedtls_mpi_cmp_mpi( &P->Z, &Q->Z ) == 0 )
422 {
423 return( 0 );
424 }
425
426 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
427 }
428
429 /*
430 * Import a non-zero point from ASCII strings
431 */
432 int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix,
433 const char *x, const char *y )
434 {
435 int ret;
436
437 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X, radix, x ) );
438 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y, radix, y ) );
439 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
440
441 cleanup:
442 return( ret );
443 }
444
445 /*
446 * Export a point into unsigned binary data (SEC1 2.3.3)
447 */
448 int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *P,
449 int format, size_t *olen,
450 unsigned char *buf, size_t buflen )
451 {
452 int ret = 0;
453 size_t plen;
454
455 if( format != MBEDTLS_ECP_PF_UNCOMPRESSED &&
456 format != MBEDTLS_ECP_PF_COMPRESSED )
457 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
458
459 /*
460 * Common case: P == 0
461 */
462 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
463 {
464 if( buflen < 1 )
465 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
466
467 buf[0] = 0x00;
468 *olen = 1;
469
470 return( 0 );
471 }
472
473 plen = mbedtls_mpi_size( &grp->P );
474
475 if( format == MBEDTLS_ECP_PF_UNCOMPRESSED )
476 {
477 *olen = 2 * plen + 1;
478
479 if( buflen < *olen )
480 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
481
482 buf[0] = 0x04;
483 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
484 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) );
485 }
486 else if( format == MBEDTLS_ECP_PF_COMPRESSED )
487 {
488 *olen = plen + 1;
489
490 if( buflen < *olen )
491 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
492
493 buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 );
494 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
495 }
496
497 cleanup:
498 return( ret );
499 }
500
501 /*
502 * Import a point from unsigned binary data (SEC1 2.3.4)
503 */
504 int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
505 const unsigned char *buf, size_t ilen )
506 {
507 int ret;
508 size_t plen;
509
510 if( ilen < 1 )
511 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
512
513 if( buf[0] == 0x00 )
514 {
515 if( ilen == 1 )
516 return( mbedtls_ecp_set_zero( pt ) );
517 else
518 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
519 }
520
521 plen = mbedtls_mpi_size( &grp->P );
522
523 if( buf[0] != 0x04 )
524 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
525
526 if( ilen != 2 * plen + 1 )
527 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
528
529 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) );
530 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) );
531 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
532
533 cleanup:
534 return( ret );
535 }
536
537 /*
538 * Import a point from a TLS ECPoint record (RFC 4492)
539 * struct {
540 * opaque point <1..2^8-1>;
541 * } ECPoint;
542 */
543 int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
544 const unsigned char **buf, size_t buf_len )
545 {
546 unsigned char data_len;
547 const unsigned char *buf_start;
548
549 /*
550 * We must have at least two bytes (1 for length, at least one for data)
551 */
552 if( buf_len < 2 )
553 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
554
555 data_len = *(*buf)++;
556 if( data_len < 1 || data_len > buf_len - 1 )
557 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
558
559 /*
560 * Save buffer start for read_binary and update buf
561 */
562 buf_start = *buf;
563 *buf += data_len;
564
565 return mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len );
566 }
567
568 /*
569 * Export a point as a TLS ECPoint record (RFC 4492)
570 * struct {
571 * opaque point <1..2^8-1>;
572 * } ECPoint;
573 */
574 int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt,
575 int format, size_t *olen,
576 unsigned char *buf, size_t blen )
577 {
578 int ret;
579
580 /*
581 * buffer length must be at least one, for our length byte
582 */
583 if( blen < 1 )
584 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
585
586 if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format,
587 olen, buf + 1, blen - 1) ) != 0 )
588 return( ret );
589
590 /*
591 * write length to the first byte and update total length
592 */
593 buf[0] = (unsigned char) *olen;
594 ++*olen;
595
596 return( 0 );
597 }
598
599 /*
600 * Set a group from an ECParameters record (RFC 4492)
601 */
602 int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp, const unsigned char **buf, size_t len )
603 {
604 uint16_t tls_id;
605 const mbedtls_ecp_curve_info *curve_info;
606
607 /*
608 * We expect at least three bytes (see below)
609 */
610 if( len < 3 )
611 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
612
613 /*
614 * First byte is curve_type; only named_curve is handled
615 */
616 if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE )
617 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
618
619 /*
620 * Next two bytes are the namedcurve value
621 */
622 tls_id = *(*buf)++;
623 tls_id <<= 8;
624 tls_id |= *(*buf)++;
625
626 if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
627 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
628
629 return mbedtls_ecp_group_load( grp, curve_info->grp_id );
630 }
631
632 /*
633 * Write the ECParameters record corresponding to a group (RFC 4492)
634 */
635 int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen,
636 unsigned char *buf, size_t blen )
637 {
638 const mbedtls_ecp_curve_info *curve_info;
639
640 if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL )
641 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
642
643 /*
644 * We are going to write 3 bytes (see below)
645 */
646 *olen = 3;
647 if( blen < *olen )
648 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
649
650 /*
651 * First byte is curve_type, always named_curve
652 */
653 *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
654
655 /*
656 * Next two bytes are the namedcurve value
657 */
658 buf[0] = curve_info->tls_id >> 8;
659 buf[1] = curve_info->tls_id & 0xFF;
660
661 return( 0 );
662 }
663
664 /*
665 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
666 * See the documentation of struct mbedtls_ecp_group.
667 *
668 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
669 */
670 static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp )
671 {
672 int ret;
673
674 if( grp->modp == NULL )
675 return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) );
676
677 /* N->s < 0 is a much faster test, which fails only if N is 0 */
678 if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) ||
679 mbedtls_mpi_bitlen( N ) > 2 * grp->pbits )
680 {
681 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
682 }
683
684 MBEDTLS_MPI_CHK( grp->modp( N ) );
685
686 /* N->s < 0 is a much faster test, which fails only if N is 0 */
687 while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 )
688 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) );
689
690 while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 )
691 /* we known P, N and the result are positive */
692 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) );
693
694 cleanup:
695 return( ret );
696 }
697
698 /*
699 * Fast mod-p functions expect their argument to be in the 0..p^2 range.
700 *
701 * In order to guarantee that, we need to ensure that operands of
702 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
703 * bring the result back to this range.
704 *
705 * The following macros are shortcuts for doing that.
706 */
707
708 /*
709 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
710 */
711 #if defined(MBEDTLS_SELF_TEST)
712 #define INC_MUL_COUNT mul_count++;
713 #else
714 #define INC_MUL_COUNT
715 #endif
716
717 #define MOD_MUL( N ) do { MBEDTLS_MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
718 while( 0 )
719
720 /*
721 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
722 * N->s < 0 is a very fast test, which fails only if N is 0
723 */
724 #define MOD_SUB( N ) \
725 while( N.s < 0 && mbedtls_mpi_cmp_int( &N, 0 ) != 0 ) \
726 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &N, &N, &grp->P ) )
727
728 /*
729 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
730 * We known P, N and the result are positive, so sub_abs is correct, and
731 * a bit faster.
732 */
733 #define MOD_ADD( N ) \
734 while( mbedtls_mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
735 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &N, &N, &grp->P ) )
736
737 #if defined(ECP_SHORTWEIERSTRASS)
738 /*
739 * For curves in short Weierstrass form, we do all the internal operations in
740 * Jacobian coordinates.
741 *
742 * For multiplication, we'll use a comb method with coutermeasueres against
743 * SPA, hence timing attacks.
744 */
745
746 /*
747 * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1)
748 * Cost: 1N := 1I + 3M + 1S
749 */
750 static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt )
751 {
752 int ret;
753 mbedtls_mpi Zi, ZZi;
754
755 if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 )
756 return( 0 );
757
758 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
759 if ( mbedtls_internal_ecp_grp_capable( grp ) )
760 {
761 return mbedtls_internal_ecp_normalize_jac( grp, pt );
762 }
763 #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */
764 mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
765
766 /*
767 * X = X / Z^2 mod p
768 */
769 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi, &pt->Z, &grp->P ) );
770 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
771 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X );
772
773 /*
774 * Y = Y / Z^3 mod p
775 */
776 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y );
777 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y );
778
779 /*
780 * Z = 1
781 */
782 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
783
784 cleanup:
785
786 mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
787
788 return( ret );
789 }
790
791 /*
792 * Normalize jacobian coordinates of an array of (pointers to) points,
793 * using Montgomery's trick to perform only one inversion mod P.
794 * (See for example Cohen's "A Course in Computational Algebraic Number
795 * Theory", Algorithm 10.3.4.)
796 *
797 * Warning: fails (returning an error) if one of the points is zero!
798 * This should never happen, see choice of w in ecp_mul_comb().
799 *
800 * Cost: 1N(t) := 1I + (6t - 3)M + 1S
801 */
802 static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
803 mbedtls_ecp_point *T[], size_t t_len )
804 {
805 int ret;
806 size_t i;
807 mbedtls_mpi *c, u, Zi, ZZi;
808
809 if( t_len < 2 )
810 return( ecp_normalize_jac( grp, *T ) );
811
812 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
813 if ( mbedtls_internal_ecp_grp_capable( grp ) )
814 {
815 return mbedtls_internal_ecp_normalize_jac_many(grp, T, t_len);
816 }
817 #endif
818
819 if( ( c = mbedtls_calloc( t_len, sizeof( mbedtls_mpi ) ) ) == NULL )
820 return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
821
822 mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
823
824 /*
825 * c[i] = Z_0 * ... * Z_i
826 */
827 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) );
828 for( i = 1; i < t_len; i++ )
829 {
830 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );
831 MOD_MUL( c[i] );
832 }
833
834 /*
835 * u = 1 / (Z_0 * ... * Z_n) mod P
836 */
837 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[t_len-1], &grp->P ) );
838
839 for( i = t_len - 1; ; i-- )
840 {
841 /*
842 * Zi = 1 / Z_i mod p
843 * u = 1 / (Z_0 * ... * Z_i) mod P
844 */
845 if( i == 0 ) {
846 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) );
847 }
848 else
849 {
850 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi );
851 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u );
852 }
853
854 /*
855 * proceed as in normalize()
856 */
857 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi );
858 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X );
859 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y );
860 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y );
861
862 /*
863 * Post-precessing: reclaim some memory by shrinking coordinates
864 * - not storing Z (always 1)
865 * - shrinking other coordinates, but still keeping the same number of
866 * limbs as P, as otherwise it will too likely be regrown too fast.
867 */
868 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) );
869 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) );
870 mbedtls_mpi_free( &T[i]->Z );
871
872 if( i == 0 )
873 break;
874 }
875
876 cleanup:
877
878 mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
879 for( i = 0; i < t_len; i++ )
880 mbedtls_mpi_free( &c[i] );
881 mbedtls_free( c );
882
883 return( ret );
884 }
885
886 /*
887 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
888 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
889 */
890 static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp,
891 mbedtls_ecp_point *Q,
892 unsigned char inv )
893 {
894 int ret;
895 unsigned char nonzero;
896 mbedtls_mpi mQY;
897
898 mbedtls_mpi_init( &mQY );
899
900 /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
901 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) );
902 nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0;
903 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) );
904
905 cleanup:
906 mbedtls_mpi_free( &mQY );
907
908 return( ret );
909 }
910
911 /*
912 * Point doubling R = 2 P, Jacobian coordinates
913 *
914 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
915 *
916 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR
917 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.
918 *
919 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
920 *
921 * Cost: 1D := 3M + 4S (A == 0)
922 * 4M + 4S (A == -3)
923 * 3M + 6S + 1a otherwise
924 */
925 static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
926 const mbedtls_ecp_point *P )
927 {
928 int ret;
929 mbedtls_mpi M, S, T, U;
930
931 #if defined(MBEDTLS_SELF_TEST)
932 dbl_count++;
933 #endif
934
935 #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
936 if ( mbedtls_internal_ecp_grp_capable( grp ) )
937 {
938 return mbedtls_internal_ecp_double_jac( grp, R, P );
939 }
940 #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */
941
942 mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U );
943
944 /* Special case for A = -3 */
945 if( grp->A.p == NULL )
946 {
947 /* M = 3(X + Z^2)(X - Z^2) */
948 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S );
949 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T, &P->X, &S ) ); MOD_ADD( T );
950 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U, &P->X, &S ) ); MOD_SUB( U );
951 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &U ) ); MOD_MUL( S );
952 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
953 }
954 else
955 {
956 /* M = 3.X^2 */
957 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &P->X ) ); MOD_MUL( S );
958 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M );
959
960 /* Optimize away for "koblitz" curves with A = 0 */
961 if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 )
962 {
963 /* M += A.Z^4 */
964 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S );
965 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &S, &S ) ); MOD_MUL( T );
966 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &T, &grp->A ) ); MOD_MUL( S );
967 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M, &M, &S ) ); MOD_ADD( M );
968 }
969 }
970
971 /* S = 4.X.Y^2 */
972 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &P->Y, &P->Y ) ); MOD_MUL( T );
973 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T, 1 ) ); MOD_ADD( T );
974 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &P->X, &T ) ); MOD_MUL( S );
975 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S, 1 ) ); MOD_ADD( S );
976
977 /* U = 8.Y^4 */
978 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &T, &T ) ); MOD_MUL( U );
979 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U );
980
981 /* T = M^2 - 2.S */
982 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &M, &M ) ); MOD_MUL( T );
983 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T );
984 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T );
985
986 /* S = M(S - T) - U */
987 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &T ) ); MOD_SUB( S );
988 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S, &S, &M ) ); MOD_MUL( S );
989 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S, &S, &U ) ); MOD_SUB( S );
990
991 /* U = 2.Y.Z */
992 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U, &P->Y, &P->Z ) ); MOD_MUL( U );
993 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U, 1 ) ); MOD_ADD( U );
994
995 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) );
996 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) );
997 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) );
998
999 cleanup:
1000 mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U );
1001
1002 return( ret );
1003 }
1004
1005 /*
1006 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
1007 *
1008 * The coordinates of Q must be normalized (= affine),
1009 * but those of P don't need to. R is not normalized.
1010 *
1011 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
1012 * None of these cases can happen as intermediate step in ecp_mul_comb():
1013 * - at each step, P, Q and R are multiples of the base point, the factor
1014 * being less than its order, so none of them is zero;
1015 * - Q is an odd multiple of the base point, P an even multiple,
1016 * due to the choice of precomputed points in the modified comb method.
1017 * So branches for these cases do not leak secret information.
1018 *
1019 * We accept Q->Z being unset (saving memory in tables) as meaning 1.
1020 *
1021 * Cost: 1A := 8M + 3S
1022 */
1023 static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1024 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
1025 {
1026 int ret;
1027 mbedtls_mpi T1, T2, T3, T4, X, Y, Z;
1028
1029 #if defined(MBEDTLS_SELF_TEST)
1030 add_count++;
1031 #endif
1032
1033 #if defined(MBEDTLS_ECP_ADD_MIXED_ALT)
1034 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1035 {
1036 return mbedtls_internal_ecp_add_mixed( grp, R, P, Q );
1037 }
1038 #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */
1039
1040 /*
1041 * Trivial cases: P == 0 or Q == 0 (case 1)
1042 */
1043 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
1044 return( mbedtls_ecp_copy( R, Q ) );
1045
1046 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 )
1047 return( mbedtls_ecp_copy( R, P ) );
1048
1049 /*
1050 * Make sure Q coordinates are normalized
1051 */
1052 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 )
1053 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1054
1055 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 );
1056 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1057
1058 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 );
1059 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 );
1060 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 );
1061 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 );
1062 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 );
1063 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 );
1064
1065 /* Special cases (2) and (3) */
1066 if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 )
1067 {
1068 if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 )
1069 {
1070 ret = ecp_double_jac( grp, R, P );
1071 goto cleanup;
1072 }
1073 else
1074 {
1075 ret = mbedtls_ecp_set_zero( R );
1076 goto cleanup;
1077 }
1078 }
1079
1080 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z );
1081 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 );
1082 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 );
1083 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 );
1084 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 );
1085 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X );
1086 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X );
1087 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X );
1088 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 );
1089 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 );
1090 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 );
1091 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y );
1092
1093 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) );
1094 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) );
1095 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) );
1096
1097 cleanup:
1098
1099 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 );
1100 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1101
1102 return( ret );
1103 }
1104
1105 /*
1106 * Randomize jacobian coordinates:
1107 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
1108 * This is sort of the reverse operation of ecp_normalize_jac().
1109 *
1110 * This countermeasure was first suggested in [2].
1111 */
1112 static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
1113 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1114 {
1115 int ret;
1116 mbedtls_mpi l, ll;
1117 size_t p_size;
1118 int count = 0;
1119
1120 #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
1121 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1122 {
1123 return mbedtls_internal_ecp_randomize_jac( grp, pt, f_rng, p_rng );
1124 }
1125 #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */
1126
1127 p_size = ( grp->pbits + 7 ) / 8;
1128 mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll );
1129
1130 /* Generate l such that 1 < l < p */
1131 do
1132 {
1133 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
1134
1135 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
1136 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
1137
1138 if( count++ > 10 )
1139 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
1140 }
1141 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
1142
1143 /* Z = l * Z */
1144 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z );
1145
1146 /* X = l^2 * X */
1147 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll );
1148 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X );
1149
1150 /* Y = l^3 * Y */
1151 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll );
1152 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y );
1153
1154 cleanup:
1155 mbedtls_mpi_free( &l ); mbedtls_mpi_free( &ll );
1156
1157 return( ret );
1158 }
1159
1160 /*
1161 * Check and define parameters used by the comb method (see below for details)
1162 */
1163 #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7
1164 #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"
1165 #endif
1166
1167 /* d = ceil( n / w ) */
1168 #define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2
1169
1170 /* number of precomputed points */
1171 #define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) )
1172
1173 /*
1174 * Compute the representation of m that will be used with our comb method.
1175 *
1176 * The basic comb method is described in GECC 3.44 for example. We use a
1177 * modified version that provides resistance to SPA by avoiding zero
1178 * digits in the representation as in [3]. We modify the method further by
1179 * requiring that all K_i be odd, which has the small cost that our
1180 * representation uses one more K_i, due to carries.
1181 *
1182 * Also, for the sake of compactness, only the seven low-order bits of x[i]
1183 * are used to represent K_i, and the msb of x[i] encodes the the sign (s_i in
1184 * the paper): it is set if and only if if s_i == -1;
1185 *
1186 * Calling conventions:
1187 * - x is an array of size d + 1
1188 * - w is the size, ie number of teeth, of the comb, and must be between
1189 * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE)
1190 * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d
1191 * (the result will be incorrect if these assumptions are not satisfied)
1192 */
1193 static void ecp_comb_fixed( unsigned char x[], size_t d,
1194 unsigned char w, const mbedtls_mpi *m )
1195 {
1196 size_t i, j;
1197 unsigned char c, cc, adjust;
1198
1199 memset( x, 0, d+1 );
1200
1201 /* First get the classical comb values (except for x_d = 0) */
1202 for( i = 0; i < d; i++ )
1203 for( j = 0; j < w; j++ )
1204 x[i] |= mbedtls_mpi_get_bit( m, i + d * j ) << j;
1205
1206 /* Now make sure x_1 .. x_d are odd */
1207 c = 0;
1208 for( i = 1; i <= d; i++ )
1209 {
1210 /* Add carry and update it */
1211 cc = x[i] & c;
1212 x[i] = x[i] ^ c;
1213 c = cc;
1214
1215 /* Adjust if needed, avoiding branches */
1216 adjust = 1 - ( x[i] & 0x01 );
1217 c |= x[i] & ( x[i-1] * adjust );
1218 x[i] = x[i] ^ ( x[i-1] * adjust );
1219 x[i-1] |= adjust << 7;
1220 }
1221 }
1222
1223 /*
1224 * Precompute points for the comb method
1225 *
1226 * If i = i_{w-1} ... i_1 is the binary representation of i, then
1227 * T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P
1228 *
1229 * T must be able to hold 2^{w - 1} elements
1230 *
1231 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
1232 */
1233 static int ecp_precompute_comb( const mbedtls_ecp_group *grp,
1234 mbedtls_ecp_point T[], const mbedtls_ecp_point *P,
1235 unsigned char w, size_t d )
1236 {
1237 int ret;
1238 unsigned char i, k;
1239 size_t j;
1240 mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1];
1241
1242 /*
1243 * Set T[0] = P and
1244 * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
1245 */
1246 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T[0], P ) );
1247
1248 k = 0;
1249 for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 )
1250 {
1251 cur = T + i;
1252 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) );
1253 for( j = 0; j < d; j++ )
1254 MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) );
1255
1256 TT[k++] = cur;
1257 }
1258
1259 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1260
1261 /*
1262 * Compute the remaining ones using the minimal number of additions
1263 * Be careful to update T[2^l] only after using it!
1264 */
1265 k = 0;
1266 for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 )
1267 {
1268 j = i;
1269 while( j-- )
1270 {
1271 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
1272 TT[k++] = &T[i + j];
1273 }
1274 }
1275
1276 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1277
1278 cleanup:
1279
1280 return( ret );
1281 }
1282
1283 /*
1284 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
1285 */
1286 static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1287 const mbedtls_ecp_point T[], unsigned char t_len,
1288 unsigned char i )
1289 {
1290 int ret;
1291 unsigned char ii, j;
1292
1293 /* Ignore the "sign" bit and scale down */
1294 ii = ( i & 0x7Fu ) >> 1;
1295
1296 /* Read the whole table to thwart cache-based timing attacks */
1297 for( j = 0; j < t_len; j++ )
1298 {
1299 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) );
1300 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) );
1301 }
1302
1303 /* Safely invert result if i is "negative" */
1304 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
1305
1306 cleanup:
1307 return( ret );
1308 }
1309
1310 /*
1311 * Core multiplication algorithm for the (modified) comb method.
1312 * This part is actually common with the basic comb method (GECC 3.44)
1313 *
1314 * Cost: d A + d D + 1 R
1315 */
1316 static int ecp_mul_comb_core( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1317 const mbedtls_ecp_point T[], unsigned char t_len,
1318 const unsigned char x[], size_t d,
1319 int (*f_rng)(void *, unsigned char *, size_t),
1320 void *p_rng )
1321 {
1322 int ret;
1323 mbedtls_ecp_point Txi;
1324 size_t i;
1325
1326 mbedtls_ecp_point_init( &Txi );
1327
1328 /* Start with a non-zero point and randomize its coordinates */
1329 i = d;
1330 MBEDTLS_MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) );
1331 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 1 ) );
1332 if( f_rng != 0 )
1333 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
1334
1335 while( i-- != 0 )
1336 {
1337 MBEDTLS_MPI_CHK( ecp_double_jac( grp, R, R ) );
1338 MBEDTLS_MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) );
1339 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
1340 }
1341
1342 cleanup:
1343
1344 mbedtls_ecp_point_free( &Txi );
1345
1346 return( ret );
1347 }
1348
1349 /*
1350 * Multiplication using the comb method,
1351 * for curves in short Weierstrass form
1352 */
1353 static int ecp_mul_comb( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1354 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
1355 int (*f_rng)(void *, unsigned char *, size_t),
1356 void *p_rng )
1357 {
1358 int ret;
1359 unsigned char w, m_is_odd, p_eq_g, pre_len, i;
1360 size_t d;
1361 unsigned char k[COMB_MAX_D + 1];
1362 mbedtls_ecp_point *T;
1363 mbedtls_mpi M, mm;
1364
1365 mbedtls_mpi_init( &M );
1366 mbedtls_mpi_init( &mm );
1367
1368 /* we need N to be odd to trnaform m in an odd number, check now */
1369 if( mbedtls_mpi_get_bit( &grp->N, 0 ) != 1 )
1370 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1371
1372 /*
1373 * Minimize the number of multiplications, that is minimize
1374 * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
1375 * (see costs of the various parts, with 1S = 1M)
1376 */
1377 w = grp->nbits >= 384 ? 5 : 4;
1378
1379 /*
1380 * If P == G, pre-compute a bit more, since this may be re-used later.
1381 * Just adding one avoids upping the cost of the first mul too much,
1382 * and the memory cost too.
1383 */
1384 #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
1385 p_eq_g = ( mbedtls_mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&
1386 mbedtls_mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 );
1387 if( p_eq_g )
1388 w++;
1389 #else
1390 p_eq_g = 0;
1391 #endif
1392
1393 /*
1394 * Make sure w is within bounds.
1395 * (The last test is useful only for very small curves in the test suite.)
1396 */
1397 if( w > MBEDTLS_ECP_WINDOW_SIZE )
1398 w = MBEDTLS_ECP_WINDOW_SIZE;
1399 if( w >= grp->nbits )
1400 w = 2;
1401
1402 /* Other sizes that depend on w */
1403 pre_len = 1U << ( w - 1 );
1404 d = ( grp->nbits + w - 1 ) / w;
1405
1406 /*
1407 * Prepare precomputed points: if P == G we want to
1408 * use grp->T if already initialized, or initialize it.
1409 */
1410 T = p_eq_g ? grp->T : NULL;
1411
1412 if( T == NULL )
1413 {
1414 T = mbedtls_calloc( pre_len, sizeof( mbedtls_ecp_point ) );
1415 if( T == NULL )
1416 {
1417 ret = MBEDTLS_ERR_ECP_ALLOC_FAILED;
1418 goto cleanup;
1419 }
1420
1421 MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) );
1422
1423 if( p_eq_g )
1424 {
1425 grp->T = T;
1426 grp->T_size = pre_len;
1427 }
1428 }
1429
1430 /*
1431 * Make sure M is odd (M = m or M = N - m, since N is odd)
1432 * using the fact that m * P = - (N - m) * P
1433 */
1434 m_is_odd = ( mbedtls_mpi_get_bit( m, 0 ) == 1 );
1435 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M, m ) );
1436 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm, &grp->N, m ) );
1437 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M, &mm, ! m_is_odd ) );
1438
1439 /*
1440 * Go for comb multiplication, R = M * P
1441 */
1442 ecp_comb_fixed( k, d, w, &M );
1443 MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) );
1444
1445 /*
1446 * Now get m * P from M * P and normalize it
1447 */
1448 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) );
1449 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) );
1450
1451 cleanup:
1452
1453 /* There are two cases where T is not stored in grp:
1454 * - P != G
1455 * - An intermediate operation failed before setting grp->T
1456 * In either case, T must be freed.
1457 */
1458 if( T != NULL && T != grp->T )
1459 {
1460 for( i = 0; i < pre_len; i++ )
1461 mbedtls_ecp_point_free( &T[i] );
1462 mbedtls_free( T );
1463 }
1464
1465 mbedtls_mpi_free( &M );
1466 mbedtls_mpi_free( &mm );
1467
1468 if( ret != 0 )
1469 mbedtls_ecp_point_free( R );
1470
1471 return( ret );
1472 }
1473
1474 #endif /* ECP_SHORTWEIERSTRASS */
1475
1476 #if defined(ECP_MONTGOMERY)
1477 /*
1478 * For Montgomery curves, we do all the internal arithmetic in projective
1479 * coordinates. Import/export of points uses only the x coordinates, which is
1480 * internaly represented as X / Z.
1481 *
1482 * For scalar multiplication, we'll use a Montgomery ladder.
1483 */
1484
1485 /*
1486 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
1487 * Cost: 1M + 1I
1488 */
1489 static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P )
1490 {
1491 int ret;
1492
1493 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
1494 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1495 {
1496 return mbedtls_internal_ecp_normalize_mxz( grp, P );
1497 }
1498 #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */
1499
1500 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P->Z, &P->Z, &grp->P ) );
1501 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X );
1502 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
1503
1504 cleanup:
1505 return( ret );
1506 }
1507
1508 /*
1509 * Randomize projective x/z coordinates:
1510 * (X, Z) -> (l X, l Z) for random l
1511 * This is sort of the reverse operation of ecp_normalize_mxz().
1512 *
1513 * This countermeasure was first suggested in [2].
1514 * Cost: 2M
1515 */
1516 static int ecp_randomize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P,
1517 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1518 {
1519 int ret;
1520 mbedtls_mpi l;
1521 size_t p_size;
1522 int count = 0;
1523
1524 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
1525 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1526 {
1527 return mbedtls_internal_ecp_randomize_mxz( grp, P, f_rng, p_rng );
1528 }
1529 #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */
1530
1531 p_size = ( grp->pbits + 7 ) / 8;
1532 mbedtls_mpi_init( &l );
1533
1534 /* Generate l such that 1 < l < p */
1535 do
1536 {
1537 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng ) );
1538
1539 while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
1540 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
1541
1542 if( count++ > 10 )
1543 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
1544 }
1545 while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
1546
1547 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X );
1548 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z );
1549
1550 cleanup:
1551 mbedtls_mpi_free( &l );
1552
1553 return( ret );
1554 }
1555
1556 /*
1557 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
1558 * for Montgomery curves in x/z coordinates.
1559 *
1560 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
1561 * with
1562 * d = X1
1563 * P = (X2, Z2)
1564 * Q = (X3, Z3)
1565 * R = (X4, Z4)
1566 * S = (X5, Z5)
1567 * and eliminating temporary variables tO, ..., t4.
1568 *
1569 * Cost: 5M + 4S
1570 */
1571 static int ecp_double_add_mxz( const mbedtls_ecp_group *grp,
1572 mbedtls_ecp_point *R, mbedtls_ecp_point *S,
1573 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q,
1574 const mbedtls_mpi *d )
1575 {
1576 int ret;
1577 mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB;
1578
1579 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
1580 if ( mbedtls_internal_ecp_grp_capable( grp ) )
1581 {
1582 return mbedtls_internal_ecp_double_add_mxz( grp, R, S, P, Q, d );
1583 }
1584 #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */
1585
1586 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &AA ); mbedtls_mpi_init( &B );
1587 mbedtls_mpi_init( &BB ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &C );
1588 mbedtls_mpi_init( &D ); mbedtls_mpi_init( &DA ); mbedtls_mpi_init( &CB );
1589
1590 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A );
1591 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA );
1592 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B );
1593 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB );
1594 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E );
1595 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C );
1596 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D );
1597 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA );
1598 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB );
1599 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X );
1600 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X );
1601 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z );
1602 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z );
1603 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z );
1604 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X );
1605 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z );
1606 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z );
1607 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z );
1608
1609 cleanup:
1610 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &AA ); mbedtls_mpi_free( &B );
1611 mbedtls_mpi_free( &BB ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &C );
1612 mbedtls_mpi_free( &D ); mbedtls_mpi_free( &DA ); mbedtls_mpi_free( &CB );
1613
1614 return( ret );
1615 }
1616
1617 /*
1618 * Multiplication with Montgomery ladder in x/z coordinates,
1619 * for curves in Montgomery form
1620 */
1621 static int ecp_mul_mxz( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1622 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
1623 int (*f_rng)(void *, unsigned char *, size_t),
1624 void *p_rng )
1625 {
1626 int ret;
1627 size_t i;
1628 unsigned char b;
1629 mbedtls_ecp_point RP;
1630 mbedtls_mpi PX;
1631
1632 mbedtls_ecp_point_init( &RP ); mbedtls_mpi_init( &PX );
1633
1634 /* Save PX and read from P before writing to R, in case P == R */
1635 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX, &P->X ) );
1636 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP, P ) );
1637
1638 /* Set R to zero in modified x/z coordinates */
1639 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->X, 1 ) );
1640 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R->Z, 0 ) );
1641 mbedtls_mpi_free( &R->Y );
1642
1643 /* RP.X might be sligtly larger than P, so reduce it */
1644 MOD_ADD( RP.X );
1645
1646 /* Randomize coordinates of the starting point */
1647 if( f_rng != NULL )
1648 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
1649
1650 /* Loop invariant: R = result so far, RP = R + P */
1651 i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */
1652 while( i-- > 0 )
1653 {
1654 b = mbedtls_mpi_get_bit( m, i );
1655 /*
1656 * if (b) R = 2R + P else R = 2R,
1657 * which is:
1658 * if (b) double_add( RP, R, RP, R )
1659 * else double_add( R, RP, R, RP )
1660 * but using safe conditional swaps to avoid leaks
1661 */
1662 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );
1663 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
1664 MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
1665 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->X, &RP.X, b ) );
1666 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
1667 }
1668
1669 MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) );
1670
1671 cleanup:
1672 mbedtls_ecp_point_free( &RP ); mbedtls_mpi_free( &PX );
1673
1674 return( ret );
1675 }
1676
1677 #endif /* ECP_MONTGOMERY */
1678
1679 /*
1680 * Multiplication R = m * P
1681 */
1682 int mbedtls_ecp_mul( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1683 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
1684 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1685 {
1686 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1687 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
1688 char is_grp_capable = 0;
1689 #endif
1690
1691 /* Common sanity checks */
1692 if( mbedtls_mpi_cmp_int( &P->Z, 1 ) != 0 )
1693 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1694
1695 if( ( ret = mbedtls_ecp_check_privkey( grp, m ) ) != 0 ||
1696 ( ret = mbedtls_ecp_check_pubkey( grp, P ) ) != 0 )
1697 return( ret );
1698
1699 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
1700 if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) )
1701 {
1702 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );
1703 }
1704
1705 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
1706 #if defined(ECP_MONTGOMERY)
1707 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
1708 ret = ecp_mul_mxz( grp, R, m, P, f_rng, p_rng );
1709
1710 #endif
1711 #if defined(ECP_SHORTWEIERSTRASS)
1712 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
1713 ret = ecp_mul_comb( grp, R, m, P, f_rng, p_rng );
1714
1715 #endif
1716 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
1717 cleanup:
1718
1719 if ( is_grp_capable )
1720 {
1721 mbedtls_internal_ecp_free( grp );
1722 }
1723
1724 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
1725 return( ret );
1726 }
1727
1728 #if defined(ECP_SHORTWEIERSTRASS)
1729 /*
1730 * Check that an affine point is valid as a public key,
1731 * short weierstrass curves (SEC1 3.2.3.1)
1732 */
1733 static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
1734 {
1735 int ret;
1736 mbedtls_mpi YY, RHS;
1737
1738 /* pt coordinates must be normalized for our checks */
1739 if( mbedtls_mpi_cmp_int( &pt->X, 0 ) < 0 ||
1740 mbedtls_mpi_cmp_int( &pt->Y, 0 ) < 0 ||
1741 mbedtls_mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 ||
1742 mbedtls_mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 )
1743 return( MBEDTLS_ERR_ECP_INVALID_KEY );
1744
1745 mbedtls_mpi_init( &YY ); mbedtls_mpi_init( &RHS );
1746
1747 /*
1748 * YY = Y^2
1749 * RHS = X (X^2 + A) + B = X^3 + A X + B
1750 */
1751 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY );
1752 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS );
1753
1754 /* Special case for A = -3 */
1755 if( grp->A.p == NULL )
1756 {
1757 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS );
1758 }
1759 else
1760 {
1761 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS );
1762 }
1763
1764 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS );
1765 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS );
1766
1767 if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 )
1768 ret = MBEDTLS_ERR_ECP_INVALID_KEY;
1769
1770 cleanup:
1771
1772 mbedtls_mpi_free( &YY ); mbedtls_mpi_free( &RHS );
1773
1774 return( ret );
1775 }
1776 #endif /* ECP_SHORTWEIERSTRASS */
1777
1778 /*
1779 * R = m * P with shortcuts for m == 1 and m == -1
1780 * NOT constant-time - ONLY for short Weierstrass!
1781 */
1782 static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp,
1783 mbedtls_ecp_point *R,
1784 const mbedtls_mpi *m,
1785 const mbedtls_ecp_point *P )
1786 {
1787 int ret;
1788
1789 if( mbedtls_mpi_cmp_int( m, 1 ) == 0 )
1790 {
1791 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
1792 }
1793 else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 )
1794 {
1795 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R, P ) );
1796 if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 )
1797 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) );
1798 }
1799 else
1800 {
1801 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp, R, m, P, NULL, NULL ) );
1802 }
1803
1804 cleanup:
1805 return( ret );
1806 }
1807
1808 /*
1809 * Linear combination
1810 * NOT constant-time
1811 */
1812 int mbedtls_ecp_muladd( mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1813 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
1814 const mbedtls_mpi *n, const mbedtls_ecp_point *Q )
1815 {
1816 int ret;
1817 mbedtls_ecp_point mP;
1818 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
1819 char is_grp_capable = 0;
1820 #endif
1821
1822 if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS )
1823 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
1824
1825 mbedtls_ecp_point_init( &mP );
1826
1827 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, &mP, m, P ) );
1828 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, R, n, Q ) );
1829
1830 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
1831 if ( is_grp_capable = mbedtls_internal_ecp_grp_capable( grp ) )
1832 {
1833 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp ) );
1834 }
1835
1836 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
1837 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, R, &mP, R ) );
1838 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, R ) );
1839
1840 cleanup:
1841
1842 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
1843 if ( is_grp_capable )
1844 {
1845 mbedtls_internal_ecp_free( grp );
1846 }
1847
1848 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
1849 mbedtls_ecp_point_free( &mP );
1850
1851 return( ret );
1852 }
1853
1854
1855 #if defined(ECP_MONTGOMERY)
1856 /*
1857 * Check validity of a public key for Montgomery curves with x-only schemes
1858 */
1859 static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
1860 {
1861 /* [Curve25519 p. 5] Just check X is the correct number of bytes */
1862 if( mbedtls_mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 )
1863 return( MBEDTLS_ERR_ECP_INVALID_KEY );
1864
1865 return( 0 );
1866 }
1867 #endif /* ECP_MONTGOMERY */
1868
1869 /*
1870 * Check that a point is valid as a public key
1871 */
1872 int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
1873 {
1874 /* Must use affine coordinates */
1875 if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 )
1876 return( MBEDTLS_ERR_ECP_INVALID_KEY );
1877
1878 #if defined(ECP_MONTGOMERY)
1879 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
1880 return( ecp_check_pubkey_mx( grp, pt ) );
1881 #endif
1882 #if defined(ECP_SHORTWEIERSTRASS)
1883 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
1884 return( ecp_check_pubkey_sw( grp, pt ) );
1885 #endif
1886 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1887 }
1888
1889 /*
1890 * Check that an mbedtls_mpi is valid as a private key
1891 */
1892 int mbedtls_ecp_check_privkey( const mbedtls_ecp_group *grp, const mbedtls_mpi *d )
1893 {
1894 #if defined(ECP_MONTGOMERY)
1895 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
1896 {
1897 /* see [Curve25519] page 5 */
1898 if( mbedtls_mpi_get_bit( d, 0 ) != 0 ||
1899 mbedtls_mpi_get_bit( d, 1 ) != 0 ||
1900 mbedtls_mpi_get_bit( d, 2 ) != 0 ||
1901 mbedtls_mpi_bitlen( d ) - 1 != grp->nbits ) /* mbedtls_mpi_bitlen is one-based! */
1902 return( MBEDTLS_ERR_ECP_INVALID_KEY );
1903 else
1904 return( 0 );
1905 }
1906 #endif /* ECP_MONTGOMERY */
1907 #if defined(ECP_SHORTWEIERSTRASS)
1908 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
1909 {
1910 /* see SEC1 3.2 */
1911 if( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
1912 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 )
1913 return( MBEDTLS_ERR_ECP_INVALID_KEY );
1914 else
1915 return( 0 );
1916 }
1917 #endif /* ECP_SHORTWEIERSTRASS */
1918
1919 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1920 }
1921
1922 /*
1923 * Generate a keypair with configurable base point
1924 */
1925 int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group *grp,
1926 const mbedtls_ecp_point *G,
1927 mbedtls_mpi *d, mbedtls_ecp_point *Q,
1928 int (*f_rng)(void *, unsigned char *, size_t),
1929 void *p_rng )
1930 {
1931 int ret;
1932 size_t n_size = ( grp->nbits + 7 ) / 8;
1933
1934 #if defined(ECP_MONTGOMERY)
1935 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
1936 {
1937 /* [M225] page 5 */
1938 size_t b;
1939
1940 do {
1941 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
1942 } while( mbedtls_mpi_bitlen( d ) == 0);
1943
1944 /* Make sure the most significant bit is nbits */
1945 b = mbedtls_mpi_bitlen( d ) - 1; /* mbedtls_mpi_bitlen is one-based */
1946 if( b > grp->nbits )
1947 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - grp->nbits ) );
1948 else
1949 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, grp->nbits, 1 ) );
1950
1951 /* Make sure the last three bits are unset */
1952 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 0, 0 ) );
1953 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 1, 0 ) );
1954 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, 2, 0 ) );
1955 }
1956 else
1957 #endif /* ECP_MONTGOMERY */
1958 #if defined(ECP_SHORTWEIERSTRASS)
1959 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
1960 {
1961 /* SEC1 3.2.1: Generate d such that 1 <= n < N */
1962 int count = 0;
1963
1964 /*
1965 * Match the procedure given in RFC 6979 (deterministic ECDSA):
1966 * - use the same byte ordering;
1967 * - keep the leftmost nbits bits of the generated octet string;
1968 * - try until result is in the desired range.
1969 * This also avoids any biais, which is especially important for ECDSA.
1970 */
1971 do
1972 {
1973 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
1974 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_size - grp->nbits ) );
1975
1976 /*
1977 * Each try has at worst a probability 1/2 of failing (the msb has
1978 * a probability 1/2 of being 0, and then the result will be < N),
1979 * so after 30 tries failure probability is a most 2**(-30).
1980 *
1981 * For most curves, 1 try is enough with overwhelming probability,
1982 * since N starts with a lot of 1s in binary, but some curves
1983 * such as secp224k1 are actually very close to the worst case.
1984 */
1985 if( ++count > 30 )
1986 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
1987 }
1988 while( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
1989 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 );
1990 }
1991 else
1992 #endif /* ECP_SHORTWEIERSTRASS */
1993 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1994
1995 cleanup:
1996 if( ret != 0 )
1997 return( ret );
1998
1999 return( mbedtls_ecp_mul( grp, Q, d, G, f_rng, p_rng ) );
2000 }
2001
2002 /*
2003 * Generate key pair, wrapper for conventional base point
2004 */
2005 int mbedtls_ecp_gen_keypair( mbedtls_ecp_group *grp,
2006 mbedtls_mpi *d, mbedtls_ecp_point *Q,
2007 int (*f_rng)(void *, unsigned char *, size_t),
2008 void *p_rng )
2009 {
2010 return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) );
2011 }
2012
2013 /*
2014 * Generate a keypair, prettier wrapper
2015 */
2016 int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
2017 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
2018 {
2019 int ret;
2020
2021 if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 )
2022 return( ret );
2023
2024 return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) );
2025 }
2026
2027 /*
2028 * Check a public-private key pair
2029 */
2030 int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv )
2031 {
2032 int ret;
2033 mbedtls_ecp_point Q;
2034 mbedtls_ecp_group grp;
2035
2036 if( pub->grp.id == MBEDTLS_ECP_DP_NONE ||
2037 pub->grp.id != prv->grp.id ||
2038 mbedtls_mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) ||
2039 mbedtls_mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) ||
2040 mbedtls_mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) )
2041 {
2042 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
2043 }
2044
2045 mbedtls_ecp_point_init( &Q );
2046 mbedtls_ecp_group_init( &grp );
2047
2048 /* mbedtls_ecp_mul() needs a non-const group... */
2049 mbedtls_ecp_group_copy( &grp, &prv->grp );
2050
2051 /* Also checks d is valid */
2052 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) );
2053
2054 if( mbedtls_mpi_cmp_mpi( &Q.X, &prv->Q.X ) ||
2055 mbedtls_mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) ||
2056 mbedtls_mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) )
2057 {
2058 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
2059 goto cleanup;
2060 }
2061
2062 cleanup:
2063 mbedtls_ecp_point_free( &Q );
2064 mbedtls_ecp_group_free( &grp );
2065
2066 return( ret );
2067 }
2068
2069 #if defined(MBEDTLS_SELF_TEST)
2070
2071 /*
2072 * Checkup routine
2073 */
2074 int mbedtls_ecp_self_test( int verbose )
2075 {
2076 int ret;
2077 size_t i;
2078 mbedtls_ecp_group grp;
2079 mbedtls_ecp_point R, P;
2080 mbedtls_mpi m;
2081 unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
2082 /* exponents especially adapted for secp192r1 */
2083 const char *exponents[] =
2084 {
2085 "000000000000000000000000000000000000000000000001", /* one */
2086 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */
2087 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
2088 "400000000000000000000000000000000000000000000000", /* one and zeros */
2089 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
2090 "555555555555555555555555555555555555555555555555", /* 101010... */
2091 };
2092
2093 mbedtls_ecp_group_init( &grp );
2094 mbedtls_ecp_point_init( &R );
2095 mbedtls_ecp_point_init( &P );
2096 mbedtls_mpi_init( &m );
2097
2098 /* Use secp192r1 if available, or any available curve */
2099 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
2100 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, MBEDTLS_ECP_DP_SECP192R1 ) );
2101 #else
2102 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp, mbedtls_ecp_curve_list()->grp_id ) );
2103 #endif
2104
2105 if( verbose != 0 )
2106 mbedtls_printf( " ECP test #1 (constant op_count, base point G): " );
2107
2108 /* Do a dummy multiplication first to trigger precomputation */
2109 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m, 2 ) );
2110 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) );
2111
2112 add_count = 0;
2113 dbl_count = 0;
2114 mul_count = 0;
2115 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
2116 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
2117
2118 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
2119 {
2120 add_c_prev = add_count;
2121 dbl_c_prev = dbl_count;
2122 mul_c_prev = mul_count;
2123 add_count = 0;
2124 dbl_count = 0;
2125 mul_count = 0;
2126
2127 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
2128 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) );
2129
2130 if( add_count != add_c_prev ||
2131 dbl_count != dbl_c_prev ||
2132 mul_count != mul_c_prev )
2133 {
2134 if( verbose != 0 )
2135 mbedtls_printf( "failed (%u)\n", (unsigned int) i );
2136
2137 ret = 1;
2138 goto cleanup;
2139 }
2140 }
2141
2142 if( verbose != 0 )
2143 mbedtls_printf( "passed\n" );
2144
2145 if( verbose != 0 )
2146 mbedtls_printf( " ECP test #2 (constant op_count, other point): " );
2147 /* We computed P = 2G last time, use it */
2148
2149 add_count = 0;
2150 dbl_count = 0;
2151 mul_count = 0;
2152 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[0] ) );
2153 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
2154
2155 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
2156 {
2157 add_c_prev = add_count;
2158 dbl_c_prev = dbl_count;
2159 mul_c_prev = mul_count;
2160 add_count = 0;
2161 dbl_count = 0;
2162 mul_count = 0;
2163
2164 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m, 16, exponents[i] ) );
2165 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &R, &m, &P, NULL, NULL ) );
2166
2167 if( add_count != add_c_prev ||
2168 dbl_count != dbl_c_prev ||
2169 mul_count != mul_c_prev )
2170 {
2171 if( verbose != 0 )
2172 mbedtls_printf( "failed (%u)\n", (unsigned int) i );
2173
2174 ret = 1;
2175 goto cleanup;
2176 }
2177 }
2178
2179 if( verbose != 0 )
2180 mbedtls_printf( "passed\n" );
2181
2182 cleanup:
2183
2184 if( ret < 0 && verbose != 0 )
2185 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
2186
2187 mbedtls_ecp_group_free( &grp );
2188 mbedtls_ecp_point_free( &R );
2189 mbedtls_ecp_point_free( &P );
2190 mbedtls_mpi_free( &m );
2191
2192 if( verbose != 0 )
2193 mbedtls_printf( "\n" );
2194
2195 return( ret );
2196 }
2197
2198 #endif /* MBEDTLS_SELF_TEST */
2199
2200 #endif /* !MBEDTLS_ECP_ALT */
2201
2202 #endif /* MBEDTLS_ECP_C */
A free Windows-compatible Operating System