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