2 * Elliptic curves over GF(p): generic functions
4 * Copyright The Mbed TLS Contributors
5 * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
7 * This file is provided under the Apache License 2.0, or the
8 * GNU General Public License v2.0 or later.
13 * Licensed under the Apache License, Version 2.0 (the "License"); you may
14 * not use this file except in compliance with the License.
15 * You may obtain a copy of the License at
17 * http://www.apache.org/licenses/LICENSE-2.0
19 * Unless required by applicable law or agreed to in writing, software
20 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
21 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
22 * See the License for the specific language governing permissions and
23 * limitations under the License.
28 * GNU General Public License v2.0 or later:
30 * This program is free software; you can redistribute it and/or modify
31 * it under the terms of the GNU General Public License as published by
32 * the Free Software Foundation; either version 2 of the License, or
33 * (at your option) any later version.
35 * This program is distributed in the hope that it will be useful,
36 * but WITHOUT ANY WARRANTY; without even the implied warranty of
37 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
38 * GNU General Public License for more details.
40 * You should have received a copy of the GNU General Public License along
41 * with this program; if not, write to the Free Software Foundation, Inc.,
42 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
50 * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
51 * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
52 * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
53 * RFC 4492 for the related TLS structures and constants
54 * RFC 7748 for the Curve448 and Curve25519 curve definitions
56 * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf
58 * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
59 * for elliptic curve cryptosystems. In : Cryptographic Hardware and
60 * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
61 * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
63 * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
64 * render ECC resistant against Side Channel Attacks. IACR Cryptology
65 * ePrint Archive, 2004, vol. 2004, p. 342.
66 * <http://eprint.iacr.org/2004/342.pdf>
69 #if !defined(MBEDTLS_CONFIG_FILE)
70 #include "mbedtls/config.h"
72 #include MBEDTLS_CONFIG_FILE
76 * \brief Function level alternative implementation.
78 * The MBEDTLS_ECP_INTERNAL_ALT macro enables alternative implementations to
79 * replace certain functions in this module. The alternative implementations are
80 * typically hardware accelerators and need to activate the hardware before the
81 * computation starts and deactivate it after it finishes. The
82 * mbedtls_internal_ecp_init() and mbedtls_internal_ecp_free() functions serve
85 * To preserve the correct functionality the following conditions must hold:
87 * - The alternative implementation must be activated by
88 * mbedtls_internal_ecp_init() before any of the replaceable functions is
90 * - mbedtls_internal_ecp_free() must \b only be called when the alternative
91 * implementation is activated.
92 * - mbedtls_internal_ecp_init() must \b not be called when the alternative
93 * implementation is activated.
94 * - Public functions must not return while the alternative implementation is
96 * - Replaceable functions are guarded by \c MBEDTLS_ECP_XXX_ALT macros and
97 * before calling them an \code if( mbedtls_internal_ecp_grp_capable( grp ) )
98 * \endcode ensures that the alternative implementation supports the current
101 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
104 #if defined(MBEDTLS_ECP_C)
106 #include "mbedtls/ecp.h"
107 #include "mbedtls/threading.h"
108 #include "mbedtls/platform_util.h"
109 #include "mbedtls/bn_mul.h"
113 #if !defined(MBEDTLS_ECP_ALT)
115 /* Parameter validation macros based on platform_util.h */
116 #define ECP_VALIDATE_RET( cond ) \
117 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_ECP_BAD_INPUT_DATA )
118 #define ECP_VALIDATE( cond ) \
119 MBEDTLS_INTERNAL_VALIDATE( cond )
121 #if defined(MBEDTLS_PLATFORM_C)
122 #include "mbedtls/platform.h"
126 #define mbedtls_printf printf
127 #define mbedtls_calloc calloc
128 #define mbedtls_free free
131 #include "mbedtls/ecp_internal.h"
133 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
134 #if defined(MBEDTLS_HMAC_DRBG_C)
135 #include "mbedtls/hmac_drbg.h"
136 #elif defined(MBEDTLS_CTR_DRBG_C)
137 #include "mbedtls/ctr_drbg.h"
138 #elif defined(MBEDTLS_SHA512_C)
139 #include "mbedtls/sha512.h"
140 #elif defined(MBEDTLS_SHA256_C)
141 #include "mbedtls/sha256.h"
143 #error "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid."
145 #endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */
147 #if ( defined(__ARMCC_VERSION) || defined(_MSC_VER) ) && \
148 !defined(inline) && !defined(__cplusplus)
149 #define inline __inline
152 #if defined(MBEDTLS_SELF_TEST)
154 * Counts of point addition and doubling, and field multiplications.
155 * Used to test resistance of point multiplication to simple timing attacks.
157 static unsigned long add_count
, dbl_count
, mul_count
;
160 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
162 * Currently ecp_mul() takes a RNG function as an argument, used for
163 * side-channel protection, but it can be NULL. The initial reasoning was
164 * that people will pass non-NULL RNG when they care about side-channels, but
165 * unfortunately we have some APIs that call ecp_mul() with a NULL RNG, with
166 * no opportunity for the user to do anything about it.
168 * The obvious strategies for addressing that include:
169 * - change those APIs so that they take RNG arguments;
170 * - require a global RNG to be available to all crypto modules.
172 * Unfortunately those would break compatibility. So what we do instead is
173 * have our own internal DRBG instance, seeded from the secret scalar.
175 * The following is a light-weight abstraction layer for doing that with
176 * HMAC_DRBG (first choice) or CTR_DRBG.
179 #if defined(MBEDTLS_HMAC_DRBG_C)
181 /* DRBG context type */
182 typedef mbedtls_hmac_drbg_context ecp_drbg_context
;
184 /* DRBG context init */
185 static inline void ecp_drbg_init( ecp_drbg_context
*ctx
)
187 mbedtls_hmac_drbg_init( ctx
);
190 /* DRBG context free */
191 static inline void ecp_drbg_free( ecp_drbg_context
*ctx
)
193 mbedtls_hmac_drbg_free( ctx
);
197 static inline int ecp_drbg_random( void *p_rng
,
198 unsigned char *output
, size_t output_len
)
200 return( mbedtls_hmac_drbg_random( p_rng
, output
, output_len
) );
203 /* DRBG context seeding */
204 static int ecp_drbg_seed( ecp_drbg_context
*ctx
,
205 const mbedtls_mpi
*secret
, size_t secret_len
)
208 unsigned char secret_bytes
[MBEDTLS_ECP_MAX_BYTES
];
209 /* The list starts with strong hashes */
210 const mbedtls_md_type_t md_type
= mbedtls_md_list()[0];
211 const mbedtls_md_info_t
*md_info
= mbedtls_md_info_from_type( md_type
);
213 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( secret
,
214 secret_bytes
, secret_len
) );
216 ret
= mbedtls_hmac_drbg_seed_buf( ctx
, md_info
, secret_bytes
, secret_len
);
219 mbedtls_platform_zeroize( secret_bytes
, secret_len
);
224 #elif defined(MBEDTLS_CTR_DRBG_C)
226 /* DRBG context type */
227 typedef mbedtls_ctr_drbg_context ecp_drbg_context
;
229 /* DRBG context init */
230 static inline void ecp_drbg_init( ecp_drbg_context
*ctx
)
232 mbedtls_ctr_drbg_init( ctx
);
235 /* DRBG context free */
236 static inline void ecp_drbg_free( ecp_drbg_context
*ctx
)
238 mbedtls_ctr_drbg_free( ctx
);
242 static inline int ecp_drbg_random( void *p_rng
,
243 unsigned char *output
, size_t output_len
)
245 return( mbedtls_ctr_drbg_random( p_rng
, output
, output_len
) );
249 * Since CTR_DRBG doesn't have a seed_buf() function the way HMAC_DRBG does,
250 * we need to pass an entropy function when seeding. So we use a dummy
251 * function for that, and pass the actual entropy as customisation string.
252 * (During seeding of CTR_DRBG the entropy input and customisation string are
253 * concatenated before being used to update the secret state.)
255 static int ecp_ctr_drbg_null_entropy(void *ctx
, unsigned char *out
, size_t len
)
258 memset( out
, 0, len
);
262 /* DRBG context seeding */
263 static int ecp_drbg_seed( ecp_drbg_context
*ctx
,
264 const mbedtls_mpi
*secret
, size_t secret_len
)
267 unsigned char secret_bytes
[MBEDTLS_ECP_MAX_BYTES
];
269 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( secret
,
270 secret_bytes
, secret_len
) );
272 ret
= mbedtls_ctr_drbg_seed( ctx
, ecp_ctr_drbg_null_entropy
, NULL
,
273 secret_bytes
, secret_len
);
276 mbedtls_platform_zeroize( secret_bytes
, secret_len
);
281 #elif defined(MBEDTLS_SHA512_C) || defined(MBEDTLS_SHA256_C)
283 /* This will be used in the self-test function */
284 #define ECP_ONE_STEP_KDF
287 * We need to expand secret data (the scalar) into a longer stream of bytes.
289 * We'll use the One-Step KDF from NIST SP 800-56C, with option 1 (H is a hash
290 * function) and empty FixedInfo. (Though we'll make it fit the DRBG API for
291 * convenience, this is not a full-fledged DRBG, but we don't need one here.)
293 * We need a basic hash abstraction layer to use whatever SHA-2 is available.
295 #if defined(MBEDTLS_SHA512_C)
297 #define HASH_FUNC( in, ilen, out ) mbedtls_sha512_ret( in, ilen, out, 0 );
298 #define HASH_BLOCK_BYTES ( 512 / 8 )
300 #elif defined(MBEDTLS_SHA256_C)
302 #define HASH_FUNC( in, ilen, out ) mbedtls_sha256_ret( in, ilen, out, 0 );
303 #define HASH_BLOCK_BYTES ( 256 / 8 )
305 #endif /* SHA512/SHA256 abstraction */
308 * State consists of a 32-bit counter plus the secret value.
310 * We stored them concatenated in a single buffer as that's what will get
311 * passed to the hash function.
315 uint8_t buf
[4 + MBEDTLS_ECP_MAX_BYTES
];
318 static void ecp_drbg_init( ecp_drbg_context
*ctx
)
320 memset( ctx
, 0, sizeof( ecp_drbg_context
) );
323 static void ecp_drbg_free( ecp_drbg_context
*ctx
)
325 mbedtls_platform_zeroize( ctx
, sizeof( ecp_drbg_context
) );
328 static int ecp_drbg_seed( ecp_drbg_context
*ctx
,
329 const mbedtls_mpi
*secret
, size_t secret_len
)
331 ctx
->total_len
= 4 + secret_len
;
332 memset( ctx
->buf
, 0, 4);
333 return( mbedtls_mpi_write_binary( secret
, ctx
->buf
+ 4, secret_len
) );
336 static int ecp_drbg_random( void *p_rng
, unsigned char *output
, size_t output_len
)
338 ecp_drbg_context
*ctx
= p_rng
;
341 uint8_t tmp
[HASH_BLOCK_BYTES
];
343 while( len_done
< output_len
)
347 /* This function is only called for coordinate randomisation, which
348 * happens only twice in a scalar multiplication. Each time needs a
349 * random value in the range [2, p-1], and gets it by drawing len(p)
350 * bytes from this function, and retrying up to 10 times if unlucky.
352 * So for the largest curve, each scalar multiplication draws at most
353 * 20 * 66 bytes. The minimum block size is 32 (SHA-256), so with
354 * rounding that means a most 20 * 3 blocks.
356 * Since we don't need to draw more that 255 blocks, don't bother
357 * with carry propagation and just return an error instead. We can
358 * change that it we even need to draw more blinding values.
361 if( ctx
->buf
[3] == 0 )
362 return( MBEDTLS_ERR_ECP_RANDOM_FAILED
);
364 ret
= HASH_FUNC( ctx
->buf
, ctx
->total_len
, tmp
);
368 if( output_len
- len_done
> HASH_BLOCK_BYTES
)
369 use_len
= HASH_BLOCK_BYTES
;
371 use_len
= output_len
- len_done
;
373 memcpy( output
+ len_done
, tmp
, use_len
);
377 mbedtls_platform_zeroize( tmp
, sizeof( tmp
) );
382 #else /* DRBG/SHA modules */
383 #error "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid."
384 #endif /* DRBG/SHA modules */
385 #endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */
387 #if defined(MBEDTLS_ECP_RESTARTABLE)
389 * Maximum number of "basic operations" to be done in a row.
391 * Default value 0 means that ECC operations will not yield.
392 * Note that regardless of the value of ecp_max_ops, always at
393 * least one step is performed before yielding.
395 * Setting ecp_max_ops=1 can be suitable for testing purposes
396 * as it will interrupt computation at all possible points.
398 static unsigned ecp_max_ops
= 0;
403 void mbedtls_ecp_set_max_ops( unsigned max_ops
)
405 ecp_max_ops
= max_ops
;
409 * Check if restart is enabled
411 int mbedtls_ecp_restart_is_enabled( void )
413 return( ecp_max_ops
!= 0 );
417 * Restart sub-context for ecp_mul_comb()
419 struct mbedtls_ecp_restart_mul
421 mbedtls_ecp_point R
; /* current intermediate result */
422 size_t i
; /* current index in various loops, 0 outside */
423 mbedtls_ecp_point
*T
; /* table for precomputed points */
424 unsigned char T_size
; /* number of points in table T */
425 enum { /* what were we doing last time we returned? */
426 ecp_rsm_init
= 0, /* nothing so far, dummy initial state */
427 ecp_rsm_pre_dbl
, /* precompute 2^n multiples */
428 ecp_rsm_pre_norm_dbl
, /* normalize precomputed 2^n multiples */
429 ecp_rsm_pre_add
, /* precompute remaining points by adding */
430 ecp_rsm_pre_norm_add
, /* normalize all precomputed points */
431 ecp_rsm_comb_core
, /* ecp_mul_comb_core() */
432 ecp_rsm_final_norm
, /* do the final normalization */
434 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
435 ecp_drbg_context drbg_ctx
;
436 unsigned char drbg_seeded
;
441 * Init restart_mul sub-context
443 static void ecp_restart_rsm_init( mbedtls_ecp_restart_mul_ctx
*ctx
)
445 mbedtls_ecp_point_init( &ctx
->R
);
449 ctx
->state
= ecp_rsm_init
;
450 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
451 ecp_drbg_init( &ctx
->drbg_ctx
);
452 ctx
->drbg_seeded
= 0;
457 * Free the components of a restart_mul sub-context
459 static void ecp_restart_rsm_free( mbedtls_ecp_restart_mul_ctx
*ctx
)
466 mbedtls_ecp_point_free( &ctx
->R
);
470 for( i
= 0; i
< ctx
->T_size
; i
++ )
471 mbedtls_ecp_point_free( ctx
->T
+ i
);
472 mbedtls_free( ctx
->T
);
475 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
476 ecp_drbg_free( &ctx
->drbg_ctx
);
479 ecp_restart_rsm_init( ctx
);
483 * Restart context for ecp_muladd()
485 struct mbedtls_ecp_restart_muladd
487 mbedtls_ecp_point mP
; /* mP value */
488 mbedtls_ecp_point R
; /* R intermediate result */
489 enum { /* what should we do next? */
490 ecp_rsma_mul1
= 0, /* first multiplication */
491 ecp_rsma_mul2
, /* second multiplication */
492 ecp_rsma_add
, /* addition */
493 ecp_rsma_norm
, /* normalization */
498 * Init restart_muladd sub-context
500 static void ecp_restart_ma_init( mbedtls_ecp_restart_muladd_ctx
*ctx
)
502 mbedtls_ecp_point_init( &ctx
->mP
);
503 mbedtls_ecp_point_init( &ctx
->R
);
504 ctx
->state
= ecp_rsma_mul1
;
508 * Free the components of a restart_muladd sub-context
510 static void ecp_restart_ma_free( mbedtls_ecp_restart_muladd_ctx
*ctx
)
515 mbedtls_ecp_point_free( &ctx
->mP
);
516 mbedtls_ecp_point_free( &ctx
->R
);
518 ecp_restart_ma_init( ctx
);
522 * Initialize a restart context
524 void mbedtls_ecp_restart_init( mbedtls_ecp_restart_ctx
*ctx
)
526 ECP_VALIDATE( ctx
!= NULL
);
534 * Free the components of a restart context
536 void mbedtls_ecp_restart_free( mbedtls_ecp_restart_ctx
*ctx
)
541 ecp_restart_rsm_free( ctx
->rsm
);
542 mbedtls_free( ctx
->rsm
);
544 ecp_restart_ma_free( ctx
->ma
);
545 mbedtls_free( ctx
->ma
);
547 mbedtls_ecp_restart_init( ctx
);
551 * Check if we can do the next step
553 int mbedtls_ecp_check_budget( const mbedtls_ecp_group
*grp
,
554 mbedtls_ecp_restart_ctx
*rs_ctx
,
557 ECP_VALIDATE_RET( grp
!= NULL
);
559 if( rs_ctx
!= NULL
&& ecp_max_ops
!= 0 )
561 /* scale depending on curve size: the chosen reference is 256-bit,
562 * and multiplication is quadratic. Round to the closest integer. */
563 if( grp
->pbits
>= 512 )
565 else if( grp
->pbits
>= 384 )
568 /* Avoid infinite loops: always allow first step.
569 * Because of that, however, it's not generally true
570 * that ops_done <= ecp_max_ops, so the check
571 * ops_done > ecp_max_ops below is mandatory. */
572 if( ( rs_ctx
->ops_done
!= 0 ) &&
573 ( rs_ctx
->ops_done
> ecp_max_ops
||
574 ops
> ecp_max_ops
- rs_ctx
->ops_done
) )
576 return( MBEDTLS_ERR_ECP_IN_PROGRESS
);
579 /* update running count */
580 rs_ctx
->ops_done
+= ops
;
586 /* Call this when entering a function that needs its own sub-context */
587 #define ECP_RS_ENTER( SUB ) do { \
588 /* reset ops count for this call if top-level */ \
589 if( rs_ctx != NULL && rs_ctx->depth++ == 0 ) \
590 rs_ctx->ops_done = 0; \
592 /* set up our own sub-context if needed */ \
593 if( mbedtls_ecp_restart_is_enabled() && \
594 rs_ctx != NULL && rs_ctx->SUB == NULL ) \
596 rs_ctx->SUB = mbedtls_calloc( 1, sizeof( *rs_ctx->SUB ) ); \
597 if( rs_ctx->SUB == NULL ) \
598 return( MBEDTLS_ERR_ECP_ALLOC_FAILED ); \
600 ecp_restart_## SUB ##_init( rs_ctx->SUB ); \
604 /* Call this when leaving a function that needs its own sub-context */
605 #define ECP_RS_LEAVE( SUB ) do { \
606 /* clear our sub-context when not in progress (done or error) */ \
607 if( rs_ctx != NULL && rs_ctx->SUB != NULL && \
608 ret != MBEDTLS_ERR_ECP_IN_PROGRESS ) \
610 ecp_restart_## SUB ##_free( rs_ctx->SUB ); \
611 mbedtls_free( rs_ctx->SUB ); \
612 rs_ctx->SUB = NULL; \
615 if( rs_ctx != NULL ) \
619 #else /* MBEDTLS_ECP_RESTARTABLE */
621 #define ECP_RS_ENTER( sub ) (void) rs_ctx;
622 #define ECP_RS_LEAVE( sub ) (void) rs_ctx;
624 #endif /* MBEDTLS_ECP_RESTARTABLE */
626 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) || \
627 defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) || \
628 defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) || \
629 defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) || \
630 defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) || \
631 defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) || \
632 defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) || \
633 defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) || \
634 defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) || \
635 defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) || \
636 defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
637 #define ECP_SHORTWEIERSTRASS
640 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) || \
641 defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
642 #define ECP_MONTGOMERY
646 * Curve types: internal for now, might be exposed later
651 ECP_TYPE_SHORT_WEIERSTRASS
, /* y^2 = x^3 + a x + b */
652 ECP_TYPE_MONTGOMERY
, /* y^2 = x^3 + a x^2 + x */
656 * List of supported curves:
658 * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
662 * Curves are listed in order: largest curves first, and for a given size,
663 * fastest curves first. This provides the default order for the SSL module.
665 * Reminder: update profiles in x509_crt.c when adding a new curves!
667 static const mbedtls_ecp_curve_info ecp_supported_curves
[] =
669 #if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
670 { MBEDTLS_ECP_DP_SECP521R1
, 25, 521, "secp521r1" },
672 #if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
673 { MBEDTLS_ECP_DP_BP512R1
, 28, 512, "brainpoolP512r1" },
675 #if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
676 { MBEDTLS_ECP_DP_SECP384R1
, 24, 384, "secp384r1" },
678 #if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
679 { MBEDTLS_ECP_DP_BP384R1
, 27, 384, "brainpoolP384r1" },
681 #if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
682 { MBEDTLS_ECP_DP_SECP256R1
, 23, 256, "secp256r1" },
684 #if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
685 { MBEDTLS_ECP_DP_SECP256K1
, 22, 256, "secp256k1" },
687 #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
688 { MBEDTLS_ECP_DP_BP256R1
, 26, 256, "brainpoolP256r1" },
690 #if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
691 { MBEDTLS_ECP_DP_SECP224R1
, 21, 224, "secp224r1" },
693 #if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
694 { MBEDTLS_ECP_DP_SECP224K1
, 20, 224, "secp224k1" },
696 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
697 { MBEDTLS_ECP_DP_SECP192R1
, 19, 192, "secp192r1" },
699 #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
700 { MBEDTLS_ECP_DP_SECP192K1
, 18, 192, "secp192k1" },
702 { MBEDTLS_ECP_DP_NONE
, 0, 0, NULL
},
705 #define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \
706 sizeof( ecp_supported_curves[0] )
708 static mbedtls_ecp_group_id ecp_supported_grp_id
[ECP_NB_CURVES
];
711 * List of supported curves and associated info
713 const mbedtls_ecp_curve_info
*mbedtls_ecp_curve_list( void )
715 return( ecp_supported_curves
);
719 * List of supported curves, group ID only
721 const mbedtls_ecp_group_id
*mbedtls_ecp_grp_id_list( void )
723 static int init_done
= 0;
728 const mbedtls_ecp_curve_info
*curve_info
;
730 for( curve_info
= mbedtls_ecp_curve_list();
731 curve_info
->grp_id
!= MBEDTLS_ECP_DP_NONE
;
734 ecp_supported_grp_id
[i
++] = curve_info
->grp_id
;
736 ecp_supported_grp_id
[i
] = MBEDTLS_ECP_DP_NONE
;
741 return( ecp_supported_grp_id
);
745 * Get the curve info for the internal identifier
747 const mbedtls_ecp_curve_info
*mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id
)
749 const mbedtls_ecp_curve_info
*curve_info
;
751 for( curve_info
= mbedtls_ecp_curve_list();
752 curve_info
->grp_id
!= MBEDTLS_ECP_DP_NONE
;
755 if( curve_info
->grp_id
== grp_id
)
756 return( curve_info
);
763 * Get the curve info from the TLS identifier
765 const mbedtls_ecp_curve_info
*mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id
)
767 const mbedtls_ecp_curve_info
*curve_info
;
769 for( curve_info
= mbedtls_ecp_curve_list();
770 curve_info
->grp_id
!= MBEDTLS_ECP_DP_NONE
;
773 if( curve_info
->tls_id
== tls_id
)
774 return( curve_info
);
781 * Get the curve info from the name
783 const mbedtls_ecp_curve_info
*mbedtls_ecp_curve_info_from_name( const char *name
)
785 const mbedtls_ecp_curve_info
*curve_info
;
790 for( curve_info
= mbedtls_ecp_curve_list();
791 curve_info
->grp_id
!= MBEDTLS_ECP_DP_NONE
;
794 if( strcmp( curve_info
->name
, name
) == 0 )
795 return( curve_info
);
802 * Get the type of a curve
804 static inline ecp_curve_type
ecp_get_type( const mbedtls_ecp_group
*grp
)
806 if( grp
->G
.X
.p
== NULL
)
807 return( ECP_TYPE_NONE
);
809 if( grp
->G
.Y
.p
== NULL
)
810 return( ECP_TYPE_MONTGOMERY
);
812 return( ECP_TYPE_SHORT_WEIERSTRASS
);
816 * Initialize (the components of) a point
818 void mbedtls_ecp_point_init( mbedtls_ecp_point
*pt
)
820 ECP_VALIDATE( pt
!= NULL
);
822 mbedtls_mpi_init( &pt
->X
);
823 mbedtls_mpi_init( &pt
->Y
);
824 mbedtls_mpi_init( &pt
->Z
);
828 * Initialize (the components of) a group
830 void mbedtls_ecp_group_init( mbedtls_ecp_group
*grp
)
832 ECP_VALIDATE( grp
!= NULL
);
834 grp
->id
= MBEDTLS_ECP_DP_NONE
;
835 mbedtls_mpi_init( &grp
->P
);
836 mbedtls_mpi_init( &grp
->A
);
837 mbedtls_mpi_init( &grp
->B
);
838 mbedtls_ecp_point_init( &grp
->G
);
839 mbedtls_mpi_init( &grp
->N
);
852 * Initialize (the components of) a key pair
854 void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair
*key
)
856 ECP_VALIDATE( key
!= NULL
);
858 mbedtls_ecp_group_init( &key
->grp
);
859 mbedtls_mpi_init( &key
->d
);
860 mbedtls_ecp_point_init( &key
->Q
);
864 * Unallocate (the components of) a point
866 void mbedtls_ecp_point_free( mbedtls_ecp_point
*pt
)
871 mbedtls_mpi_free( &( pt
->X
) );
872 mbedtls_mpi_free( &( pt
->Y
) );
873 mbedtls_mpi_free( &( pt
->Z
) );
877 * Unallocate (the components of) a group
879 void mbedtls_ecp_group_free( mbedtls_ecp_group
*grp
)
888 mbedtls_mpi_free( &grp
->P
);
889 mbedtls_mpi_free( &grp
->A
);
890 mbedtls_mpi_free( &grp
->B
);
891 mbedtls_ecp_point_free( &grp
->G
);
892 mbedtls_mpi_free( &grp
->N
);
897 for( i
= 0; i
< grp
->T_size
; i
++ )
898 mbedtls_ecp_point_free( &grp
->T
[i
] );
899 mbedtls_free( grp
->T
);
902 mbedtls_platform_zeroize( grp
, sizeof( mbedtls_ecp_group
) );
906 * Unallocate (the components of) a key pair
908 void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair
*key
)
913 mbedtls_ecp_group_free( &key
->grp
);
914 mbedtls_mpi_free( &key
->d
);
915 mbedtls_ecp_point_free( &key
->Q
);
919 * Copy the contents of a point
921 int mbedtls_ecp_copy( mbedtls_ecp_point
*P
, const mbedtls_ecp_point
*Q
)
924 ECP_VALIDATE_RET( P
!= NULL
);
925 ECP_VALIDATE_RET( Q
!= NULL
);
927 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P
->X
, &Q
->X
) );
928 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P
->Y
, &Q
->Y
) );
929 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P
->Z
, &Q
->Z
) );
936 * Copy the contents of a group object
938 int mbedtls_ecp_group_copy( mbedtls_ecp_group
*dst
, const mbedtls_ecp_group
*src
)
940 ECP_VALIDATE_RET( dst
!= NULL
);
941 ECP_VALIDATE_RET( src
!= NULL
);
943 return( mbedtls_ecp_group_load( dst
, src
->id
) );
949 int mbedtls_ecp_set_zero( mbedtls_ecp_point
*pt
)
952 ECP_VALIDATE_RET( pt
!= NULL
);
954 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt
->X
, 1 ) );
955 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt
->Y
, 1 ) );
956 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt
->Z
, 0 ) );
963 * Tell if a point is zero
965 int mbedtls_ecp_is_zero( mbedtls_ecp_point
*pt
)
967 ECP_VALIDATE_RET( pt
!= NULL
);
969 return( mbedtls_mpi_cmp_int( &pt
->Z
, 0 ) == 0 );
973 * Compare two points lazily
975 int mbedtls_ecp_point_cmp( const mbedtls_ecp_point
*P
,
976 const mbedtls_ecp_point
*Q
)
978 ECP_VALIDATE_RET( P
!= NULL
);
979 ECP_VALIDATE_RET( Q
!= NULL
);
981 if( mbedtls_mpi_cmp_mpi( &P
->X
, &Q
->X
) == 0 &&
982 mbedtls_mpi_cmp_mpi( &P
->Y
, &Q
->Y
) == 0 &&
983 mbedtls_mpi_cmp_mpi( &P
->Z
, &Q
->Z
) == 0 )
988 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
992 * Import a non-zero point from ASCII strings
994 int mbedtls_ecp_point_read_string( mbedtls_ecp_point
*P
, int radix
,
995 const char *x
, const char *y
)
998 ECP_VALIDATE_RET( P
!= NULL
);
999 ECP_VALIDATE_RET( x
!= NULL
);
1000 ECP_VALIDATE_RET( y
!= NULL
);
1002 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P
->X
, radix
, x
) );
1003 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P
->Y
, radix
, y
) );
1004 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P
->Z
, 1 ) );
1011 * Export a point into unsigned binary data (SEC1 2.3.3)
1013 int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group
*grp
,
1014 const mbedtls_ecp_point
*P
,
1015 int format
, size_t *olen
,
1016 unsigned char *buf
, size_t buflen
)
1020 ECP_VALIDATE_RET( grp
!= NULL
);
1021 ECP_VALIDATE_RET( P
!= NULL
);
1022 ECP_VALIDATE_RET( olen
!= NULL
);
1023 ECP_VALIDATE_RET( buf
!= NULL
);
1024 ECP_VALIDATE_RET( format
== MBEDTLS_ECP_PF_UNCOMPRESSED
||
1025 format
== MBEDTLS_ECP_PF_COMPRESSED
);
1028 * Common case: P == 0
1030 if( mbedtls_mpi_cmp_int( &P
->Z
, 0 ) == 0 )
1033 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL
);
1041 plen
= mbedtls_mpi_size( &grp
->P
);
1043 if( format
== MBEDTLS_ECP_PF_UNCOMPRESSED
)
1045 *olen
= 2 * plen
+ 1;
1047 if( buflen
< *olen
)
1048 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL
);
1051 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P
->X
, buf
+ 1, plen
) );
1052 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P
->Y
, buf
+ 1 + plen
, plen
) );
1054 else if( format
== MBEDTLS_ECP_PF_COMPRESSED
)
1058 if( buflen
< *olen
)
1059 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL
);
1061 buf
[0] = 0x02 + mbedtls_mpi_get_bit( &P
->Y
, 0 );
1062 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P
->X
, buf
+ 1, plen
) );
1070 * Import a point from unsigned binary data (SEC1 2.3.4)
1072 int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group
*grp
,
1073 mbedtls_ecp_point
*pt
,
1074 const unsigned char *buf
, size_t ilen
)
1078 ECP_VALIDATE_RET( grp
!= NULL
);
1079 ECP_VALIDATE_RET( pt
!= NULL
);
1080 ECP_VALIDATE_RET( buf
!= NULL
);
1083 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
1085 if( buf
[0] == 0x00 )
1088 return( mbedtls_ecp_set_zero( pt
) );
1090 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
1093 plen
= mbedtls_mpi_size( &grp
->P
);
1095 if( buf
[0] != 0x04 )
1096 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE
);
1098 if( ilen
!= 2 * plen
+ 1 )
1099 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
1101 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt
->X
, buf
+ 1, plen
) );
1102 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt
->Y
, buf
+ 1 + plen
, plen
) );
1103 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt
->Z
, 1 ) );
1110 * Import a point from a TLS ECPoint record (RFC 4492)
1112 * opaque point <1..2^8-1>;
1115 int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group
*grp
,
1116 mbedtls_ecp_point
*pt
,
1117 const unsigned char **buf
, size_t buf_len
)
1119 unsigned char data_len
;
1120 const unsigned char *buf_start
;
1121 ECP_VALIDATE_RET( grp
!= NULL
);
1122 ECP_VALIDATE_RET( pt
!= NULL
);
1123 ECP_VALIDATE_RET( buf
!= NULL
);
1124 ECP_VALIDATE_RET( *buf
!= NULL
);
1127 * We must have at least two bytes (1 for length, at least one for data)
1130 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
1132 data_len
= *(*buf
)++;
1133 if( data_len
< 1 || data_len
> buf_len
- 1 )
1134 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
1137 * Save buffer start for read_binary and update buf
1142 return( mbedtls_ecp_point_read_binary( grp
, pt
, buf_start
, data_len
) );
1146 * Export a point as a TLS ECPoint record (RFC 4492)
1148 * opaque point <1..2^8-1>;
1151 int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group
*grp
, const mbedtls_ecp_point
*pt
,
1152 int format
, size_t *olen
,
1153 unsigned char *buf
, size_t blen
)
1156 ECP_VALIDATE_RET( grp
!= NULL
);
1157 ECP_VALIDATE_RET( pt
!= NULL
);
1158 ECP_VALIDATE_RET( olen
!= NULL
);
1159 ECP_VALIDATE_RET( buf
!= NULL
);
1160 ECP_VALIDATE_RET( format
== MBEDTLS_ECP_PF_UNCOMPRESSED
||
1161 format
== MBEDTLS_ECP_PF_COMPRESSED
);
1164 * buffer length must be at least one, for our length byte
1167 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
1169 if( ( ret
= mbedtls_ecp_point_write_binary( grp
, pt
, format
,
1170 olen
, buf
+ 1, blen
- 1) ) != 0 )
1174 * write length to the first byte and update total length
1176 buf
[0] = (unsigned char) *olen
;
1183 * Set a group from an ECParameters record (RFC 4492)
1185 int mbedtls_ecp_tls_read_group( mbedtls_ecp_group
*grp
,
1186 const unsigned char **buf
, size_t len
)
1189 mbedtls_ecp_group_id grp_id
;
1190 ECP_VALIDATE_RET( grp
!= NULL
);
1191 ECP_VALIDATE_RET( buf
!= NULL
);
1192 ECP_VALIDATE_RET( *buf
!= NULL
);
1194 if( ( ret
= mbedtls_ecp_tls_read_group_id( &grp_id
, buf
, len
) ) != 0 )
1197 return( mbedtls_ecp_group_load( grp
, grp_id
) );
1201 * Read a group id from an ECParameters record (RFC 4492) and convert it to
1202 * mbedtls_ecp_group_id.
1204 int mbedtls_ecp_tls_read_group_id( mbedtls_ecp_group_id
*grp
,
1205 const unsigned char **buf
, size_t len
)
1208 const mbedtls_ecp_curve_info
*curve_info
;
1209 ECP_VALIDATE_RET( grp
!= NULL
);
1210 ECP_VALIDATE_RET( buf
!= NULL
);
1211 ECP_VALIDATE_RET( *buf
!= NULL
);
1214 * We expect at least three bytes (see below)
1217 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
1220 * First byte is curve_type; only named_curve is handled
1222 if( *(*buf
)++ != MBEDTLS_ECP_TLS_NAMED_CURVE
)
1223 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
1226 * Next two bytes are the namedcurve value
1230 tls_id
|= *(*buf
)++;
1232 if( ( curve_info
= mbedtls_ecp_curve_info_from_tls_id( tls_id
) ) == NULL
)
1233 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE
);
1235 *grp
= curve_info
->grp_id
;
1241 * Write the ECParameters record corresponding to a group (RFC 4492)
1243 int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group
*grp
, size_t *olen
,
1244 unsigned char *buf
, size_t blen
)
1246 const mbedtls_ecp_curve_info
*curve_info
;
1247 ECP_VALIDATE_RET( grp
!= NULL
);
1248 ECP_VALIDATE_RET( buf
!= NULL
);
1249 ECP_VALIDATE_RET( olen
!= NULL
);
1251 if( ( curve_info
= mbedtls_ecp_curve_info_from_grp_id( grp
->id
) ) == NULL
)
1252 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
1255 * We are going to write 3 bytes (see below)
1259 return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL
);
1262 * First byte is curve_type, always named_curve
1264 *buf
++ = MBEDTLS_ECP_TLS_NAMED_CURVE
;
1267 * Next two bytes are the namedcurve value
1269 buf
[0] = curve_info
->tls_id
>> 8;
1270 buf
[1] = curve_info
->tls_id
& 0xFF;
1276 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
1277 * See the documentation of struct mbedtls_ecp_group.
1279 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
1281 static int ecp_modp( mbedtls_mpi
*N
, const mbedtls_ecp_group
*grp
)
1285 if( grp
->modp
== NULL
)
1286 return( mbedtls_mpi_mod_mpi( N
, N
, &grp
->P
) );
1288 /* N->s < 0 is a much faster test, which fails only if N is 0 */
1289 if( ( N
->s
< 0 && mbedtls_mpi_cmp_int( N
, 0 ) != 0 ) ||
1290 mbedtls_mpi_bitlen( N
) > 2 * grp
->pbits
)
1292 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
1295 MBEDTLS_MPI_CHK( grp
->modp( N
) );
1297 /* N->s < 0 is a much faster test, which fails only if N is 0 */
1298 while( N
->s
< 0 && mbedtls_mpi_cmp_int( N
, 0 ) != 0 )
1299 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N
, N
, &grp
->P
) );
1301 while( mbedtls_mpi_cmp_mpi( N
, &grp
->P
) >= 0 )
1302 /* we known P, N and the result are positive */
1303 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N
, N
, &grp
->P
) );
1310 * Fast mod-p functions expect their argument to be in the 0..p^2 range.
1312 * In order to guarantee that, we need to ensure that operands of
1313 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
1314 * bring the result back to this range.
1316 * The following macros are shortcuts for doing that.
1320 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
1322 #if defined(MBEDTLS_SELF_TEST)
1323 #define INC_MUL_COUNT mul_count++;
1325 #define INC_MUL_COUNT
1328 #define MOD_MUL( N ) \
1331 MBEDTLS_MPI_CHK( ecp_modp( &(N), grp ) ); \
1336 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
1337 * N->s < 0 is a very fast test, which fails only if N is 0
1339 #define MOD_SUB( N ) \
1340 while( (N).s < 0 && mbedtls_mpi_cmp_int( &(N), 0 ) != 0 ) \
1341 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &(N), &(N), &grp->P ) )
1344 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
1345 * We known P, N and the result are positive, so sub_abs is correct, and
1348 #define MOD_ADD( N ) \
1349 while( mbedtls_mpi_cmp_mpi( &(N), &grp->P ) >= 0 ) \
1350 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &(N), &(N), &grp->P ) )
1352 #if defined(ECP_SHORTWEIERSTRASS)
1354 * For curves in short Weierstrass form, we do all the internal operations in
1355 * Jacobian coordinates.
1357 * For multiplication, we'll use a comb method with coutermeasueres against
1358 * SPA, hence timing attacks.
1362 * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1)
1363 * Cost: 1N := 1I + 3M + 1S
1365 static int ecp_normalize_jac( const mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*pt
)
1368 mbedtls_mpi Zi
, ZZi
;
1370 if( mbedtls_mpi_cmp_int( &pt
->Z
, 0 ) == 0 )
1373 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
1374 if( mbedtls_internal_ecp_grp_capable( grp
) )
1375 return( mbedtls_internal_ecp_normalize_jac( grp
, pt
) );
1376 #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */
1378 mbedtls_mpi_init( &Zi
); mbedtls_mpi_init( &ZZi
);
1383 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi
, &pt
->Z
, &grp
->P
) );
1384 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi
, &Zi
, &Zi
) ); MOD_MUL( ZZi
);
1385 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt
->X
, &pt
->X
, &ZZi
) ); MOD_MUL( pt
->X
);
1390 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt
->Y
, &pt
->Y
, &ZZi
) ); MOD_MUL( pt
->Y
);
1391 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt
->Y
, &pt
->Y
, &Zi
) ); MOD_MUL( pt
->Y
);
1396 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt
->Z
, 1 ) );
1400 mbedtls_mpi_free( &Zi
); mbedtls_mpi_free( &ZZi
);
1406 * Normalize jacobian coordinates of an array of (pointers to) points,
1407 * using Montgomery's trick to perform only one inversion mod P.
1408 * (See for example Cohen's "A Course in Computational Algebraic Number
1409 * Theory", Algorithm 10.3.4.)
1411 * Warning: fails (returning an error) if one of the points is zero!
1412 * This should never happen, see choice of w in ecp_mul_comb().
1414 * Cost: 1N(t) := 1I + (6t - 3)M + 1S
1416 static int ecp_normalize_jac_many( const mbedtls_ecp_group
*grp
,
1417 mbedtls_ecp_point
*T
[], size_t T_size
)
1421 mbedtls_mpi
*c
, u
, Zi
, ZZi
;
1424 return( ecp_normalize_jac( grp
, *T
) );
1426 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
1427 if( mbedtls_internal_ecp_grp_capable( grp
) )
1428 return( mbedtls_internal_ecp_normalize_jac_many( grp
, T
, T_size
) );
1431 if( ( c
= mbedtls_calloc( T_size
, sizeof( mbedtls_mpi
) ) ) == NULL
)
1432 return( MBEDTLS_ERR_ECP_ALLOC_FAILED
);
1434 for( i
= 0; i
< T_size
; i
++ )
1435 mbedtls_mpi_init( &c
[i
] );
1437 mbedtls_mpi_init( &u
); mbedtls_mpi_init( &Zi
); mbedtls_mpi_init( &ZZi
);
1440 * c[i] = Z_0 * ... * Z_i
1442 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c
[0], &T
[0]->Z
) );
1443 for( i
= 1; i
< T_size
; i
++ )
1445 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c
[i
], &c
[i
-1], &T
[i
]->Z
) );
1450 * u = 1 / (Z_0 * ... * Z_n) mod P
1452 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u
, &c
[T_size
-1], &grp
->P
) );
1454 for( i
= T_size
- 1; ; i
-- )
1457 * Zi = 1 / Z_i mod p
1458 * u = 1 / (Z_0 * ... * Z_i) mod P
1461 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi
, &u
) );
1465 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi
, &u
, &c
[i
-1] ) ); MOD_MUL( Zi
);
1466 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u
, &u
, &T
[i
]->Z
) ); MOD_MUL( u
);
1470 * proceed as in normalize()
1472 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi
, &Zi
, &Zi
) ); MOD_MUL( ZZi
);
1473 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T
[i
]->X
, &T
[i
]->X
, &ZZi
) ); MOD_MUL( T
[i
]->X
);
1474 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T
[i
]->Y
, &T
[i
]->Y
, &ZZi
) ); MOD_MUL( T
[i
]->Y
);
1475 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T
[i
]->Y
, &T
[i
]->Y
, &Zi
) ); MOD_MUL( T
[i
]->Y
);
1478 * Post-precessing: reclaim some memory by shrinking coordinates
1479 * - not storing Z (always 1)
1480 * - shrinking other coordinates, but still keeping the same number of
1481 * limbs as P, as otherwise it will too likely be regrown too fast.
1483 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T
[i
]->X
, grp
->P
.n
) );
1484 MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T
[i
]->Y
, grp
->P
.n
) );
1485 mbedtls_mpi_free( &T
[i
]->Z
);
1493 mbedtls_mpi_free( &u
); mbedtls_mpi_free( &Zi
); mbedtls_mpi_free( &ZZi
);
1494 for( i
= 0; i
< T_size
; i
++ )
1495 mbedtls_mpi_free( &c
[i
] );
1502 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
1503 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
1505 static int ecp_safe_invert_jac( const mbedtls_ecp_group
*grp
,
1506 mbedtls_ecp_point
*Q
,
1510 unsigned char nonzero
;
1513 mbedtls_mpi_init( &mQY
);
1515 /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
1516 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY
, &grp
->P
, &Q
->Y
) );
1517 nonzero
= mbedtls_mpi_cmp_int( &Q
->Y
, 0 ) != 0;
1518 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q
->Y
, &mQY
, inv
& nonzero
) );
1521 mbedtls_mpi_free( &mQY
);
1527 * Point doubling R = 2 P, Jacobian coordinates
1529 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
1531 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR
1532 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.
1534 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
1536 * Cost: 1D := 3M + 4S (A == 0)
1538 * 3M + 6S + 1a otherwise
1540 static int ecp_double_jac( const mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*R
,
1541 const mbedtls_ecp_point
*P
)
1544 mbedtls_mpi M
, S
, T
, U
;
1546 #if defined(MBEDTLS_SELF_TEST)
1550 #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
1551 if( mbedtls_internal_ecp_grp_capable( grp
) )
1552 return( mbedtls_internal_ecp_double_jac( grp
, R
, P
) );
1553 #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */
1555 mbedtls_mpi_init( &M
); mbedtls_mpi_init( &S
); mbedtls_mpi_init( &T
); mbedtls_mpi_init( &U
);
1557 /* Special case for A = -3 */
1558 if( grp
->A
.p
== NULL
)
1560 /* M = 3(X + Z^2)(X - Z^2) */
1561 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S
, &P
->Z
, &P
->Z
) ); MOD_MUL( S
);
1562 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T
, &P
->X
, &S
) ); MOD_ADD( T
);
1563 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U
, &P
->X
, &S
) ); MOD_SUB( U
);
1564 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S
, &T
, &U
) ); MOD_MUL( S
);
1565 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M
, &S
, 3 ) ); MOD_ADD( M
);
1570 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S
, &P
->X
, &P
->X
) ); MOD_MUL( S
);
1571 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M
, &S
, 3 ) ); MOD_ADD( M
);
1573 /* Optimize away for "koblitz" curves with A = 0 */
1574 if( mbedtls_mpi_cmp_int( &grp
->A
, 0 ) != 0 )
1577 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S
, &P
->Z
, &P
->Z
) ); MOD_MUL( S
);
1578 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T
, &S
, &S
) ); MOD_MUL( T
);
1579 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S
, &T
, &grp
->A
) ); MOD_MUL( S
);
1580 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M
, &M
, &S
) ); MOD_ADD( M
);
1585 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T
, &P
->Y
, &P
->Y
) ); MOD_MUL( T
);
1586 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T
, 1 ) ); MOD_ADD( T
);
1587 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S
, &P
->X
, &T
) ); MOD_MUL( S
);
1588 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S
, 1 ) ); MOD_ADD( S
);
1591 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U
, &T
, &T
) ); MOD_MUL( U
);
1592 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U
, 1 ) ); MOD_ADD( U
);
1595 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T
, &M
, &M
) ); MOD_MUL( T
);
1596 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T
, &T
, &S
) ); MOD_SUB( T
);
1597 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T
, &T
, &S
) ); MOD_SUB( T
);
1599 /* S = M(S - T) - U */
1600 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S
, &S
, &T
) ); MOD_SUB( S
);
1601 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S
, &S
, &M
) ); MOD_MUL( S
);
1602 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S
, &S
, &U
) ); MOD_SUB( S
);
1605 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U
, &P
->Y
, &P
->Z
) ); MOD_MUL( U
);
1606 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U
, 1 ) ); MOD_ADD( U
);
1608 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R
->X
, &T
) );
1609 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R
->Y
, &S
) );
1610 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R
->Z
, &U
) );
1613 mbedtls_mpi_free( &M
); mbedtls_mpi_free( &S
); mbedtls_mpi_free( &T
); mbedtls_mpi_free( &U
);
1619 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
1621 * The coordinates of Q must be normalized (= affine),
1622 * but those of P don't need to. R is not normalized.
1624 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
1625 * None of these cases can happen as intermediate step in ecp_mul_comb():
1626 * - at each step, P, Q and R are multiples of the base point, the factor
1627 * being less than its order, so none of them is zero;
1628 * - Q is an odd multiple of the base point, P an even multiple,
1629 * due to the choice of precomputed points in the modified comb method.
1630 * So branches for these cases do not leak secret information.
1632 * We accept Q->Z being unset (saving memory in tables) as meaning 1.
1634 * Cost: 1A := 8M + 3S
1636 static int ecp_add_mixed( const mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*R
,
1637 const mbedtls_ecp_point
*P
, const mbedtls_ecp_point
*Q
)
1640 mbedtls_mpi T1
, T2
, T3
, T4
, X
, Y
, Z
;
1642 #if defined(MBEDTLS_SELF_TEST)
1646 #if defined(MBEDTLS_ECP_ADD_MIXED_ALT)
1647 if( mbedtls_internal_ecp_grp_capable( grp
) )
1648 return( mbedtls_internal_ecp_add_mixed( grp
, R
, P
, Q
) );
1649 #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */
1652 * Trivial cases: P == 0 or Q == 0 (case 1)
1654 if( mbedtls_mpi_cmp_int( &P
->Z
, 0 ) == 0 )
1655 return( mbedtls_ecp_copy( R
, Q
) );
1657 if( Q
->Z
.p
!= NULL
&& mbedtls_mpi_cmp_int( &Q
->Z
, 0 ) == 0 )
1658 return( mbedtls_ecp_copy( R
, P
) );
1661 * Make sure Q coordinates are normalized
1663 if( Q
->Z
.p
!= NULL
&& mbedtls_mpi_cmp_int( &Q
->Z
, 1 ) != 0 )
1664 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
1666 mbedtls_mpi_init( &T1
); mbedtls_mpi_init( &T2
); mbedtls_mpi_init( &T3
); mbedtls_mpi_init( &T4
);
1667 mbedtls_mpi_init( &X
); mbedtls_mpi_init( &Y
); mbedtls_mpi_init( &Z
);
1669 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1
, &P
->Z
, &P
->Z
) ); MOD_MUL( T1
);
1670 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2
, &T1
, &P
->Z
) ); MOD_MUL( T2
);
1671 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1
, &T1
, &Q
->X
) ); MOD_MUL( T1
);
1672 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2
, &T2
, &Q
->Y
) ); MOD_MUL( T2
);
1673 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1
, &T1
, &P
->X
) ); MOD_SUB( T1
);
1674 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2
, &T2
, &P
->Y
) ); MOD_SUB( T2
);
1676 /* Special cases (2) and (3) */
1677 if( mbedtls_mpi_cmp_int( &T1
, 0 ) == 0 )
1679 if( mbedtls_mpi_cmp_int( &T2
, 0 ) == 0 )
1681 ret
= ecp_double_jac( grp
, R
, P
);
1686 ret
= mbedtls_ecp_set_zero( R
);
1691 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z
, &P
->Z
, &T1
) ); MOD_MUL( Z
);
1692 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3
, &T1
, &T1
) ); MOD_MUL( T3
);
1693 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4
, &T3
, &T1
) ); MOD_MUL( T4
);
1694 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3
, &T3
, &P
->X
) ); MOD_MUL( T3
);
1695 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1
, &T3
, 2 ) ); MOD_ADD( T1
);
1696 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X
, &T2
, &T2
) ); MOD_MUL( X
);
1697 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X
, &X
, &T1
) ); MOD_SUB( X
);
1698 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X
, &X
, &T4
) ); MOD_SUB( X
);
1699 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3
, &T3
, &X
) ); MOD_SUB( T3
);
1700 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3
, &T3
, &T2
) ); MOD_MUL( T3
);
1701 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4
, &T4
, &P
->Y
) ); MOD_MUL( T4
);
1702 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y
, &T3
, &T4
) ); MOD_SUB( Y
);
1704 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R
->X
, &X
) );
1705 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R
->Y
, &Y
) );
1706 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R
->Z
, &Z
) );
1710 mbedtls_mpi_free( &T1
); mbedtls_mpi_free( &T2
); mbedtls_mpi_free( &T3
); mbedtls_mpi_free( &T4
);
1711 mbedtls_mpi_free( &X
); mbedtls_mpi_free( &Y
); mbedtls_mpi_free( &Z
);
1717 * Randomize jacobian coordinates:
1718 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
1719 * This is sort of the reverse operation of ecp_normalize_jac().
1721 * This countermeasure was first suggested in [2].
1723 static int ecp_randomize_jac( const mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*pt
,
1724 int (*f_rng
)(void *, unsigned char *, size_t), void *p_rng
)
1731 #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
1732 if( mbedtls_internal_ecp_grp_capable( grp
) )
1733 return( mbedtls_internal_ecp_randomize_jac( grp
, pt
, f_rng
, p_rng
) );
1734 #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */
1736 p_size
= ( grp
->pbits
+ 7 ) / 8;
1737 mbedtls_mpi_init( &l
); mbedtls_mpi_init( &ll
);
1739 /* Generate l such that 1 < l < p */
1744 ret
= MBEDTLS_ERR_ECP_RANDOM_FAILED
;
1748 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l
, p_size
, f_rng
, p_rng
) );
1749 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l
, ( p_size
* 8 ) - grp
->pbits
) );
1751 while( ( mbedtls_mpi_cmp_int( &l
, 1 ) <= 0 ) ||
1752 ( mbedtls_mpi_cmp_mpi( &l
, &grp
->P
) >= 0 ) );
1755 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt
->Z
, &pt
->Z
, &l
) ); MOD_MUL( pt
->Z
);
1758 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll
, &l
, &l
) ); MOD_MUL( ll
);
1759 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt
->X
, &pt
->X
, &ll
) ); MOD_MUL( pt
->X
);
1762 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ll
, &ll
, &l
) ); MOD_MUL( ll
);
1763 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt
->Y
, &pt
->Y
, &ll
) ); MOD_MUL( pt
->Y
);
1766 mbedtls_mpi_free( &l
); mbedtls_mpi_free( &ll
);
1772 * Check and define parameters used by the comb method (see below for details)
1774 #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7
1775 #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"
1778 /* d = ceil( n / w ) */
1779 #define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2
1781 /* number of precomputed points */
1782 #define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) )
1785 * Compute the representation of m that will be used with our comb method.
1787 * The basic comb method is described in GECC 3.44 for example. We use a
1788 * modified version that provides resistance to SPA by avoiding zero
1789 * digits in the representation as in [3]. We modify the method further by
1790 * requiring that all K_i be odd, which has the small cost that our
1791 * representation uses one more K_i, due to carries, but saves on the size of
1792 * the precomputed table.
1794 * Summary of the comb method and its modifications:
1796 * - The goal is to compute m*P for some w*d-bit integer m.
1798 * - The basic comb method splits m into the w-bit integers
1799 * x[0] .. x[d-1] where x[i] consists of the bits in m whose
1800 * index has residue i modulo d, and computes m * P as
1801 * S[x[0]] + 2 * S[x[1]] + .. + 2^(d-1) S[x[d-1]], where
1802 * S[i_{w-1} .. i_0] := i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + i_0 P.
1804 * - If it happens that, say, x[i+1]=0 (=> S[x[i+1]]=0), one can replace the sum by
1805 * .. + 2^{i-1} S[x[i-1]] - 2^i S[x[i]] + 2^{i+1} S[x[i]] + 2^{i+2} S[x[i+2]] ..,
1806 * thereby successively converting it into a form where all summands
1807 * are nonzero, at the cost of negative summands. This is the basic idea of [3].
1809 * - More generally, even if x[i+1] != 0, we can first transform the sum as
1810 * .. - 2^i S[x[i]] + 2^{i+1} ( S[x[i]] + S[x[i+1]] ) + 2^{i+2} S[x[i+2]] ..,
1811 * and then replace S[x[i]] + S[x[i+1]] = S[x[i] ^ x[i+1]] + 2 S[x[i] & x[i+1]].
1812 * Performing and iterating this procedure for those x[i] that are even
1813 * (keeping track of carry), we can transform the original sum into one of the form
1814 * S[x'[0]] +- 2 S[x'[1]] +- .. +- 2^{d-1} S[x'[d-1]] + 2^d S[x'[d]]
1815 * with all x'[i] odd. It is therefore only necessary to know S at odd indices,
1816 * which is why we are only computing half of it in the first place in
1817 * ecp_precompute_comb and accessing it with index abs(i) / 2 in ecp_select_comb.
1819 * - For the sake of compactness, only the seven low-order bits of x[i]
1820 * are used to represent its absolute value (K_i in the paper), and the msb
1821 * of x[i] encodes the sign (s_i in the paper): it is set if and only if
1824 * Calling conventions:
1825 * - x is an array of size d + 1
1826 * - w is the size, ie number of teeth, of the comb, and must be between
1827 * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE)
1828 * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d
1829 * (the result will be incorrect if these assumptions are not satisfied)
1831 static void ecp_comb_recode_core( unsigned char x
[], size_t d
,
1832 unsigned char w
, const mbedtls_mpi
*m
)
1835 unsigned char c
, cc
, adjust
;
1837 memset( x
, 0, d
+1 );
1839 /* First get the classical comb values (except for x_d = 0) */
1840 for( i
= 0; i
< d
; i
++ )
1841 for( j
= 0; j
< w
; j
++ )
1842 x
[i
] |= mbedtls_mpi_get_bit( m
, i
+ d
* j
) << j
;
1844 /* Now make sure x_1 .. x_d are odd */
1846 for( i
= 1; i
<= d
; i
++ )
1848 /* Add carry and update it */
1853 /* Adjust if needed, avoiding branches */
1854 adjust
= 1 - ( x
[i
] & 0x01 );
1855 c
|= x
[i
] & ( x
[i
-1] * adjust
);
1856 x
[i
] = x
[i
] ^ ( x
[i
-1] * adjust
);
1857 x
[i
-1] |= adjust
<< 7;
1862 * Precompute points for the adapted comb method
1864 * Assumption: T must be able to hold 2^{w - 1} elements.
1866 * Operation: If i = i_{w-1} ... i_1 is the binary representation of i,
1867 * sets T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P.
1869 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
1871 * Note: Even comb values (those where P would be omitted from the
1872 * sum defining T[i] above) are not needed in our adaption
1873 * the comb method. See ecp_comb_recode_core().
1875 * This function currently works in four steps:
1876 * (1) [dbl] Computation of intermediate T[i] for 2-power values of i
1877 * (2) [norm_dbl] Normalization of coordinates of these T[i]
1878 * (3) [add] Computation of all T[i]
1879 * (4) [norm_add] Normalization of all T[i]
1881 * Step 1 can be interrupted but not the others; together with the final
1882 * coordinate normalization they are the largest steps done at once, depending
1883 * on the window size. Here are operation counts for P-256:
1891 * So if ECC operations are blocking for too long even with a low max_ops
1892 * value, it's useful to set MBEDTLS_ECP_WINDOW_SIZE to a lower value in order
1893 * to minimize maximum blocking time.
1895 static int ecp_precompute_comb( const mbedtls_ecp_group
*grp
,
1896 mbedtls_ecp_point T
[], const mbedtls_ecp_point
*P
,
1897 unsigned char w
, size_t d
,
1898 mbedtls_ecp_restart_ctx
*rs_ctx
)
1903 const unsigned char T_size
= 1U << ( w
- 1 );
1904 mbedtls_ecp_point
*cur
, *TT
[COMB_MAX_PRE
- 1];
1906 #if defined(MBEDTLS_ECP_RESTARTABLE)
1907 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
)
1909 if( rs_ctx
->rsm
->state
== ecp_rsm_pre_dbl
)
1911 if( rs_ctx
->rsm
->state
== ecp_rsm_pre_norm_dbl
)
1913 if( rs_ctx
->rsm
->state
== ecp_rsm_pre_add
)
1915 if( rs_ctx
->rsm
->state
== ecp_rsm_pre_norm_add
)
1922 #if defined(MBEDTLS_ECP_RESTARTABLE)
1923 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
)
1925 rs_ctx
->rsm
->state
= ecp_rsm_pre_dbl
;
1927 /* initial state for the loop */
1935 * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
1937 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &T
[0], P
) );
1939 #if defined(MBEDTLS_ECP_RESTARTABLE)
1940 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
&& rs_ctx
->rsm
->i
!= 0 )
1946 for( ; j
< d
* ( w
- 1 ); j
++ )
1948 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL
);
1950 i
= 1U << ( j
/ d
);
1954 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur
, T
+ ( i
>> 1 ) ) );
1956 MBEDTLS_MPI_CHK( ecp_double_jac( grp
, cur
, cur
) );
1959 #if defined(MBEDTLS_ECP_RESTARTABLE)
1960 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
)
1961 rs_ctx
->rsm
->state
= ecp_rsm_pre_norm_dbl
;
1966 * Normalize current elements in T. As T has holes,
1967 * use an auxiliary array of pointers to elements in T.
1970 for( i
= 1; i
< T_size
; i
<<= 1 )
1973 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV
+ 6 * j
- 2 );
1975 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp
, TT
, j
) );
1977 #if defined(MBEDTLS_ECP_RESTARTABLE)
1978 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
)
1979 rs_ctx
->rsm
->state
= ecp_rsm_pre_add
;
1984 * Compute the remaining ones using the minimal number of additions
1985 * Be careful to update T[2^l] only after using it!
1987 MBEDTLS_ECP_BUDGET( ( T_size
- 1 ) * MBEDTLS_ECP_OPS_ADD
);
1989 for( i
= 1; i
< T_size
; i
<<= 1 )
1993 MBEDTLS_MPI_CHK( ecp_add_mixed( grp
, &T
[i
+ j
], &T
[j
], &T
[i
] ) );
1996 #if defined(MBEDTLS_ECP_RESTARTABLE)
1997 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
)
1998 rs_ctx
->rsm
->state
= ecp_rsm_pre_norm_add
;
2003 * Normalize final elements in T. Even though there are no holes now, we
2004 * still need the auxiliary array for homogeneity with the previous
2005 * call. Also, skip T[0] which is already normalised, being a copy of P.
2007 for( j
= 0; j
+ 1 < T_size
; j
++ )
2010 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV
+ 6 * j
- 2 );
2012 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp
, TT
, j
) );
2015 #if defined(MBEDTLS_ECP_RESTARTABLE)
2016 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
&&
2017 ret
== MBEDTLS_ERR_ECP_IN_PROGRESS
)
2019 if( rs_ctx
->rsm
->state
== ecp_rsm_pre_dbl
)
2028 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
2030 * See ecp_comb_recode_core() for background
2032 static int ecp_select_comb( const mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*R
,
2033 const mbedtls_ecp_point T
[], unsigned char T_size
,
2037 unsigned char ii
, j
;
2039 /* Ignore the "sign" bit and scale down */
2040 ii
= ( i
& 0x7Fu
) >> 1;
2042 /* Read the whole table to thwart cache-based timing attacks */
2043 for( j
= 0; j
< T_size
; j
++ )
2045 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R
->X
, &T
[j
].X
, j
== ii
) );
2046 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &R
->Y
, &T
[j
].Y
, j
== ii
) );
2049 /* Safely invert result if i is "negative" */
2050 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp
, R
, i
>> 7 ) );
2057 * Core multiplication algorithm for the (modified) comb method.
2058 * This part is actually common with the basic comb method (GECC 3.44)
2060 * Cost: d A + d D + 1 R
2062 static int ecp_mul_comb_core( const mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*R
,
2063 const mbedtls_ecp_point T
[], unsigned char T_size
,
2064 const unsigned char x
[], size_t d
,
2065 int (*f_rng
)(void *, unsigned char *, size_t),
2067 mbedtls_ecp_restart_ctx
*rs_ctx
)
2070 mbedtls_ecp_point Txi
;
2073 mbedtls_ecp_point_init( &Txi
);
2075 #if !defined(MBEDTLS_ECP_RESTARTABLE)
2079 #if defined(MBEDTLS_ECP_RESTARTABLE)
2080 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
&&
2081 rs_ctx
->rsm
->state
!= ecp_rsm_comb_core
)
2084 rs_ctx
->rsm
->state
= ecp_rsm_comb_core
;
2087 /* new 'if' instead of nested for the sake of the 'else' branch */
2088 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
&& rs_ctx
->rsm
->i
!= 0 )
2090 /* restore current index (R already pointing to rs_ctx->rsm->R) */
2096 /* Start with a non-zero point and randomize its coordinates */
2098 MBEDTLS_MPI_CHK( ecp_select_comb( grp
, R
, T
, T_size
, x
[i
] ) );
2099 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R
->Z
, 1 ) );
2100 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2103 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp
, R
, f_rng
, p_rng
) );
2108 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL
+ MBEDTLS_ECP_OPS_ADD
);
2111 MBEDTLS_MPI_CHK( ecp_double_jac( grp
, R
, R
) );
2112 MBEDTLS_MPI_CHK( ecp_select_comb( grp
, &Txi
, T
, T_size
, x
[i
] ) );
2113 MBEDTLS_MPI_CHK( ecp_add_mixed( grp
, R
, R
, &Txi
) );
2118 mbedtls_ecp_point_free( &Txi
);
2120 #if defined(MBEDTLS_ECP_RESTARTABLE)
2121 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
&&
2122 ret
== MBEDTLS_ERR_ECP_IN_PROGRESS
)
2125 /* no need to save R, already pointing to rs_ctx->rsm->R */
2133 * Recode the scalar to get constant-time comb multiplication
2135 * As the actual scalar recoding needs an odd scalar as a starting point,
2136 * this wrapper ensures that by replacing m by N - m if necessary, and
2137 * informs the caller that the result of multiplication will be negated.
2139 * This works because we only support large prime order for Short Weierstrass
2140 * curves, so N is always odd hence either m or N - m is.
2142 * See ecp_comb_recode_core() for background.
2144 static int ecp_comb_recode_scalar( const mbedtls_ecp_group
*grp
,
2145 const mbedtls_mpi
*m
,
2146 unsigned char k
[COMB_MAX_D
+ 1],
2149 unsigned char *parity_trick
)
2154 mbedtls_mpi_init( &M
);
2155 mbedtls_mpi_init( &mm
);
2157 /* N is always odd (see above), just make extra sure */
2158 if( mbedtls_mpi_get_bit( &grp
->N
, 0 ) != 1 )
2159 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
2161 /* do we need the parity trick? */
2162 *parity_trick
= ( mbedtls_mpi_get_bit( m
, 0 ) == 0 );
2164 /* execute parity fix in constant time */
2165 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &M
, m
) );
2166 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mm
, &grp
->N
, m
) );
2167 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &M
, &mm
, *parity_trick
) );
2169 /* actual scalar recoding */
2170 ecp_comb_recode_core( k
, d
, w
, &M
);
2173 mbedtls_mpi_free( &mm
);
2174 mbedtls_mpi_free( &M
);
2180 * Perform comb multiplication (for short Weierstrass curves)
2181 * once the auxiliary table has been pre-computed.
2183 * Scalar recoding may use a parity trick that makes us compute -m * P,
2184 * if that is the case we'll need to recover m * P at the end.
2186 static int ecp_mul_comb_after_precomp( const mbedtls_ecp_group
*grp
,
2187 mbedtls_ecp_point
*R
,
2188 const mbedtls_mpi
*m
,
2189 const mbedtls_ecp_point
*T
,
2190 unsigned char T_size
,
2193 int (*f_rng
)(void *, unsigned char *, size_t),
2195 mbedtls_ecp_restart_ctx
*rs_ctx
)
2198 unsigned char parity_trick
;
2199 unsigned char k
[COMB_MAX_D
+ 1];
2200 mbedtls_ecp_point
*RR
= R
;
2202 #if defined(MBEDTLS_ECP_RESTARTABLE)
2203 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
)
2205 RR
= &rs_ctx
->rsm
->R
;
2207 if( rs_ctx
->rsm
->state
== ecp_rsm_final_norm
)
2212 MBEDTLS_MPI_CHK( ecp_comb_recode_scalar( grp
, m
, k
, d
, w
,
2214 MBEDTLS_MPI_CHK( ecp_mul_comb_core( grp
, RR
, T
, T_size
, k
, d
,
2215 f_rng
, p_rng
, rs_ctx
) );
2216 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp
, RR
, parity_trick
) );
2218 #if defined(MBEDTLS_ECP_RESTARTABLE)
2219 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
)
2220 rs_ctx
->rsm
->state
= ecp_rsm_final_norm
;
2223 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV
);
2226 * Knowledge of the jacobian coordinates may leak the last few bits of the
2227 * scalar [1], and since our MPI implementation isn't constant-flow,
2228 * inversion (used for coordinate normalization) may leak the full value
2229 * of its input via side-channels [2].
2231 * [1] https://eprint.iacr.org/2003/191
2232 * [2] https://eprint.iacr.org/2020/055
2234 * Avoid the leak by randomizing coordinates before we normalize them.
2236 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2239 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp
, RR
, f_rng
, p_rng
) );
2241 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp
, RR
) );
2243 #if defined(MBEDTLS_ECP_RESTARTABLE)
2244 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
)
2245 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R
, RR
) );
2253 * Pick window size based on curve size and whether we optimize for base point
2255 static unsigned char ecp_pick_window_size( const mbedtls_ecp_group
*grp
,
2256 unsigned char p_eq_g
)
2261 * Minimize the number of multiplications, that is minimize
2262 * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
2263 * (see costs of the various parts, with 1S = 1M)
2265 w
= grp
->nbits
>= 384 ? 5 : 4;
2268 * If P == G, pre-compute a bit more, since this may be re-used later.
2269 * Just adding one avoids upping the cost of the first mul too much,
2270 * and the memory cost too.
2276 * Make sure w is within bounds.
2277 * (The last test is useful only for very small curves in the test suite.)
2279 if( w
> MBEDTLS_ECP_WINDOW_SIZE
)
2280 w
= MBEDTLS_ECP_WINDOW_SIZE
;
2281 if( w
>= grp
->nbits
)
2288 * Multiplication using the comb method - for curves in short Weierstrass form
2290 * This function is mainly responsible for administrative work:
2291 * - managing the restart context if enabled
2292 * - managing the table of precomputed points (passed between the below two
2293 * functions): allocation, computation, ownership tranfer, freeing.
2295 * It delegates the actual arithmetic work to:
2296 * ecp_precompute_comb() and ecp_mul_comb_with_precomp()
2298 * See comments on ecp_comb_recode_core() regarding the computation strategy.
2300 static int ecp_mul_comb( mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*R
,
2301 const mbedtls_mpi
*m
, const mbedtls_ecp_point
*P
,
2302 int (*f_rng
)(void *, unsigned char *, size_t),
2304 mbedtls_ecp_restart_ctx
*rs_ctx
)
2307 unsigned char w
, p_eq_g
, i
;
2309 unsigned char T_size
= 0, T_ok
= 0;
2310 mbedtls_ecp_point
*T
= NULL
;
2311 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2312 ecp_drbg_context drbg_ctx
;
2314 ecp_drbg_init( &drbg_ctx
);
2317 ECP_RS_ENTER( rsm
);
2319 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2322 /* Adjust pointers */
2323 f_rng
= &ecp_drbg_random
;
2324 #if defined(MBEDTLS_ECP_RESTARTABLE)
2325 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
)
2326 p_rng
= &rs_ctx
->rsm
->drbg_ctx
;
2331 /* Initialize internal DRBG if necessary */
2332 #if defined(MBEDTLS_ECP_RESTARTABLE)
2333 if( rs_ctx
== NULL
|| rs_ctx
->rsm
== NULL
||
2334 rs_ctx
->rsm
->drbg_seeded
== 0 )
2337 const size_t m_len
= ( grp
->nbits
+ 7 ) / 8;
2338 MBEDTLS_MPI_CHK( ecp_drbg_seed( p_rng
, m
, m_len
) );
2340 #if defined(MBEDTLS_ECP_RESTARTABLE)
2341 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
)
2342 rs_ctx
->rsm
->drbg_seeded
= 1;
2345 #endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */
2347 /* Is P the base point ? */
2348 #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
2349 p_eq_g
= ( mbedtls_mpi_cmp_mpi( &P
->Y
, &grp
->G
.Y
) == 0 &&
2350 mbedtls_mpi_cmp_mpi( &P
->X
, &grp
->G
.X
) == 0 );
2355 /* Pick window size and deduce related sizes */
2356 w
= ecp_pick_window_size( grp
, p_eq_g
);
2357 T_size
= 1U << ( w
- 1 );
2358 d
= ( grp
->nbits
+ w
- 1 ) / w
;
2360 /* Pre-computed table: do we have it already for the base point? */
2361 if( p_eq_g
&& grp
->T
!= NULL
)
2363 /* second pointer to the same table, will be deleted on exit */
2368 #if defined(MBEDTLS_ECP_RESTARTABLE)
2369 /* Pre-computed table: do we have one in progress? complete? */
2370 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
&& rs_ctx
->rsm
->T
!= NULL
)
2372 /* transfer ownership of T from rsm to local function */
2374 rs_ctx
->rsm
->T
= NULL
;
2375 rs_ctx
->rsm
->T_size
= 0;
2377 /* This effectively jumps to the call to mul_comb_after_precomp() */
2378 T_ok
= rs_ctx
->rsm
->state
>= ecp_rsm_comb_core
;
2382 /* Allocate table if we didn't have any */
2384 T
= mbedtls_calloc( T_size
, sizeof( mbedtls_ecp_point
) );
2387 ret
= MBEDTLS_ERR_ECP_ALLOC_FAILED
;
2391 for( i
= 0; i
< T_size
; i
++ )
2392 mbedtls_ecp_point_init( &T
[i
] );
2397 /* Compute table (or finish computing it) if not done already */
2400 MBEDTLS_MPI_CHK( ecp_precompute_comb( grp
, T
, P
, w
, d
, rs_ctx
) );
2404 /* almost transfer ownership of T to the group, but keep a copy of
2405 * the pointer to use for calling the next function more easily */
2407 grp
->T_size
= T_size
;
2411 /* Actual comb multiplication using precomputed points */
2412 MBEDTLS_MPI_CHK( ecp_mul_comb_after_precomp( grp
, R
, m
,
2414 f_rng
, p_rng
, rs_ctx
) );
2418 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2419 ecp_drbg_free( &drbg_ctx
);
2422 /* does T belong to the group? */
2426 /* does T belong to the restart context? */
2427 #if defined(MBEDTLS_ECP_RESTARTABLE)
2428 if( rs_ctx
!= NULL
&& rs_ctx
->rsm
!= NULL
&& ret
== MBEDTLS_ERR_ECP_IN_PROGRESS
&& T
!= NULL
)
2430 /* transfer ownership of T from local function to rsm */
2431 rs_ctx
->rsm
->T_size
= T_size
;
2437 /* did T belong to us? then let's destroy it! */
2440 for( i
= 0; i
< T_size
; i
++ )
2441 mbedtls_ecp_point_free( &T
[i
] );
2445 /* don't free R while in progress in case R == P */
2446 #if defined(MBEDTLS_ECP_RESTARTABLE)
2447 if( ret
!= MBEDTLS_ERR_ECP_IN_PROGRESS
)
2449 /* prevent caller from using invalid value */
2451 mbedtls_ecp_point_free( R
);
2453 ECP_RS_LEAVE( rsm
);
2458 #endif /* ECP_SHORTWEIERSTRASS */
2460 #if defined(ECP_MONTGOMERY)
2462 * For Montgomery curves, we do all the internal arithmetic in projective
2463 * coordinates. Import/export of points uses only the x coordinates, which is
2464 * internaly represented as X / Z.
2466 * For scalar multiplication, we'll use a Montgomery ladder.
2470 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
2473 static int ecp_normalize_mxz( const mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*P
)
2477 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
2478 if( mbedtls_internal_ecp_grp_capable( grp
) )
2479 return( mbedtls_internal_ecp_normalize_mxz( grp
, P
) );
2480 #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */
2482 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &P
->Z
, &P
->Z
, &grp
->P
) );
2483 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P
->X
, &P
->X
, &P
->Z
) ); MOD_MUL( P
->X
);
2484 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P
->Z
, 1 ) );
2491 * Randomize projective x/z coordinates:
2492 * (X, Z) -> (l X, l Z) for random l
2493 * This is sort of the reverse operation of ecp_normalize_mxz().
2495 * This countermeasure was first suggested in [2].
2498 static int ecp_randomize_mxz( const mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*P
,
2499 int (*f_rng
)(void *, unsigned char *, size_t), void *p_rng
)
2506 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
2507 if( mbedtls_internal_ecp_grp_capable( grp
) )
2508 return( mbedtls_internal_ecp_randomize_mxz( grp
, P
, f_rng
, p_rng
) );
2509 #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */
2511 p_size
= ( grp
->pbits
+ 7 ) / 8;
2512 mbedtls_mpi_init( &l
);
2514 /* Generate l such that 1 < l < p */
2519 ret
= MBEDTLS_ERR_ECP_RANDOM_FAILED
;
2523 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &l
, p_size
, f_rng
, p_rng
) );
2524 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l
, ( p_size
* 8 ) - grp
->pbits
) );
2526 while( ( mbedtls_mpi_cmp_int( &l
, 1 ) <= 0 ) ||
2527 ( mbedtls_mpi_cmp_mpi( &l
, &grp
->P
) >= 0 ) );
2529 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P
->X
, &P
->X
, &l
) ); MOD_MUL( P
->X
);
2530 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &P
->Z
, &P
->Z
, &l
) ); MOD_MUL( P
->Z
);
2533 mbedtls_mpi_free( &l
);
2539 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
2540 * for Montgomery curves in x/z coordinates.
2542 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
2549 * and eliminating temporary variables tO, ..., t4.
2553 static int ecp_double_add_mxz( const mbedtls_ecp_group
*grp
,
2554 mbedtls_ecp_point
*R
, mbedtls_ecp_point
*S
,
2555 const mbedtls_ecp_point
*P
, const mbedtls_ecp_point
*Q
,
2556 const mbedtls_mpi
*d
)
2559 mbedtls_mpi A
, AA
, B
, BB
, E
, C
, D
, DA
, CB
;
2561 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
2562 if( mbedtls_internal_ecp_grp_capable( grp
) )
2563 return( mbedtls_internal_ecp_double_add_mxz( grp
, R
, S
, P
, Q
, d
) );
2564 #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */
2566 mbedtls_mpi_init( &A
); mbedtls_mpi_init( &AA
); mbedtls_mpi_init( &B
);
2567 mbedtls_mpi_init( &BB
); mbedtls_mpi_init( &E
); mbedtls_mpi_init( &C
);
2568 mbedtls_mpi_init( &D
); mbedtls_mpi_init( &DA
); mbedtls_mpi_init( &CB
);
2570 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &A
, &P
->X
, &P
->Z
) ); MOD_ADD( A
);
2571 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &AA
, &A
, &A
) ); MOD_MUL( AA
);
2572 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &B
, &P
->X
, &P
->Z
) ); MOD_SUB( B
);
2573 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &BB
, &B
, &B
) ); MOD_MUL( BB
);
2574 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &E
, &AA
, &BB
) ); MOD_SUB( E
);
2575 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &C
, &Q
->X
, &Q
->Z
) ); MOD_ADD( C
);
2576 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &D
, &Q
->X
, &Q
->Z
) ); MOD_SUB( D
);
2577 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &DA
, &D
, &A
) ); MOD_MUL( DA
);
2578 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &CB
, &C
, &B
) ); MOD_MUL( CB
);
2579 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &S
->X
, &DA
, &CB
) ); MOD_MUL( S
->X
);
2580 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S
->X
, &S
->X
, &S
->X
) ); MOD_MUL( S
->X
);
2581 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S
->Z
, &DA
, &CB
) ); MOD_SUB( S
->Z
);
2582 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S
->Z
, &S
->Z
, &S
->Z
) ); MOD_MUL( S
->Z
);
2583 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S
->Z
, d
, &S
->Z
) ); MOD_MUL( S
->Z
);
2584 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R
->X
, &AA
, &BB
) ); MOD_MUL( R
->X
);
2585 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R
->Z
, &grp
->A
, &E
) ); MOD_MUL( R
->Z
);
2586 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &R
->Z
, &BB
, &R
->Z
) ); MOD_ADD( R
->Z
);
2587 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &R
->Z
, &E
, &R
->Z
) ); MOD_MUL( R
->Z
);
2590 mbedtls_mpi_free( &A
); mbedtls_mpi_free( &AA
); mbedtls_mpi_free( &B
);
2591 mbedtls_mpi_free( &BB
); mbedtls_mpi_free( &E
); mbedtls_mpi_free( &C
);
2592 mbedtls_mpi_free( &D
); mbedtls_mpi_free( &DA
); mbedtls_mpi_free( &CB
);
2598 * Multiplication with Montgomery ladder in x/z coordinates,
2599 * for curves in Montgomery form
2601 static int ecp_mul_mxz( mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*R
,
2602 const mbedtls_mpi
*m
, const mbedtls_ecp_point
*P
,
2603 int (*f_rng
)(void *, unsigned char *, size_t),
2609 mbedtls_ecp_point RP
;
2611 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2612 ecp_drbg_context drbg_ctx
;
2614 ecp_drbg_init( &drbg_ctx
);
2616 mbedtls_ecp_point_init( &RP
); mbedtls_mpi_init( &PX
);
2618 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2621 const size_t m_len
= ( grp
->nbits
+ 7 ) / 8;
2622 MBEDTLS_MPI_CHK( ecp_drbg_seed( &drbg_ctx
, m
, m_len
) );
2623 f_rng
= &ecp_drbg_random
;
2626 #endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */
2628 /* Save PX and read from P before writing to R, in case P == R */
2629 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &PX
, &P
->X
) );
2630 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( &RP
, P
) );
2632 /* Set R to zero in modified x/z coordinates */
2633 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R
->X
, 1 ) );
2634 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &R
->Z
, 0 ) );
2635 mbedtls_mpi_free( &R
->Y
);
2637 /* RP.X might be sligtly larger than P, so reduce it */
2640 /* Randomize coordinates of the starting point */
2641 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2644 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp
, &RP
, f_rng
, p_rng
) );
2646 /* Loop invariant: R = result so far, RP = R + P */
2647 i
= mbedtls_mpi_bitlen( m
); /* one past the (zero-based) most significant bit */
2650 b
= mbedtls_mpi_get_bit( m
, i
);
2652 * if (b) R = 2R + P else R = 2R,
2654 * if (b) double_add( RP, R, RP, R )
2655 * else double_add( R, RP, R, RP )
2656 * but using safe conditional swaps to avoid leaks
2658 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R
->X
, &RP
.X
, b
) );
2659 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R
->Z
, &RP
.Z
, b
) );
2660 MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp
, R
, &RP
, R
, &RP
, &PX
) );
2661 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R
->X
, &RP
.X
, b
) );
2662 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_swap( &R
->Z
, &RP
.Z
, b
) );
2666 * Knowledge of the projective coordinates may leak the last few bits of the
2667 * scalar [1], and since our MPI implementation isn't constant-flow,
2668 * inversion (used for coordinate normalization) may leak the full value
2669 * of its input via side-channels [2].
2671 * [1] https://eprint.iacr.org/2003/191
2672 * [2] https://eprint.iacr.org/2020/055
2674 * Avoid the leak by randomizing coordinates before we normalize them.
2676 #if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2679 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp
, R
, f_rng
, p_rng
) );
2681 MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp
, R
) );
2684 #if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2685 ecp_drbg_free( &drbg_ctx
);
2688 mbedtls_ecp_point_free( &RP
); mbedtls_mpi_free( &PX
);
2693 #endif /* ECP_MONTGOMERY */
2696 * Restartable multiplication R = m * P
2698 int mbedtls_ecp_mul_restartable( mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*R
,
2699 const mbedtls_mpi
*m
, const mbedtls_ecp_point
*P
,
2700 int (*f_rng
)(void *, unsigned char *, size_t), void *p_rng
,
2701 mbedtls_ecp_restart_ctx
*rs_ctx
)
2703 int ret
= MBEDTLS_ERR_ECP_BAD_INPUT_DATA
;
2704 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2705 char is_grp_capable
= 0;
2707 ECP_VALIDATE_RET( grp
!= NULL
);
2708 ECP_VALIDATE_RET( R
!= NULL
);
2709 ECP_VALIDATE_RET( m
!= NULL
);
2710 ECP_VALIDATE_RET( P
!= NULL
);
2712 #if defined(MBEDTLS_ECP_RESTARTABLE)
2713 /* reset ops count for this call if top-level */
2714 if( rs_ctx
!= NULL
&& rs_ctx
->depth
++ == 0 )
2715 rs_ctx
->ops_done
= 0;
2718 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2719 if( ( is_grp_capable
= mbedtls_internal_ecp_grp_capable( grp
) ) )
2720 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp
) );
2721 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
2723 #if defined(MBEDTLS_ECP_RESTARTABLE)
2724 /* skip argument check when restarting */
2725 if( rs_ctx
== NULL
|| rs_ctx
->rsm
== NULL
)
2728 /* check_privkey is free */
2729 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_CHK
);
2731 /* Common sanity checks */
2732 MBEDTLS_MPI_CHK( mbedtls_ecp_check_privkey( grp
, m
) );
2733 MBEDTLS_MPI_CHK( mbedtls_ecp_check_pubkey( grp
, P
) );
2736 ret
= MBEDTLS_ERR_ECP_BAD_INPUT_DATA
;
2737 #if defined(ECP_MONTGOMERY)
2738 if( ecp_get_type( grp
) == ECP_TYPE_MONTGOMERY
)
2739 MBEDTLS_MPI_CHK( ecp_mul_mxz( grp
, R
, m
, P
, f_rng
, p_rng
) );
2741 #if defined(ECP_SHORTWEIERSTRASS)
2742 if( ecp_get_type( grp
) == ECP_TYPE_SHORT_WEIERSTRASS
)
2743 MBEDTLS_MPI_CHK( ecp_mul_comb( grp
, R
, m
, P
, f_rng
, p_rng
, rs_ctx
) );
2748 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2749 if( is_grp_capable
)
2750 mbedtls_internal_ecp_free( grp
);
2751 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
2753 #if defined(MBEDTLS_ECP_RESTARTABLE)
2754 if( rs_ctx
!= NULL
)
2762 * Multiplication R = m * P
2764 int mbedtls_ecp_mul( mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*R
,
2765 const mbedtls_mpi
*m
, const mbedtls_ecp_point
*P
,
2766 int (*f_rng
)(void *, unsigned char *, size_t), void *p_rng
)
2768 ECP_VALIDATE_RET( grp
!= NULL
);
2769 ECP_VALIDATE_RET( R
!= NULL
);
2770 ECP_VALIDATE_RET( m
!= NULL
);
2771 ECP_VALIDATE_RET( P
!= NULL
);
2772 return( mbedtls_ecp_mul_restartable( grp
, R
, m
, P
, f_rng
, p_rng
, NULL
) );
2775 #if defined(ECP_SHORTWEIERSTRASS)
2777 * Check that an affine point is valid as a public key,
2778 * short weierstrass curves (SEC1 3.2.3.1)
2780 static int ecp_check_pubkey_sw( const mbedtls_ecp_group
*grp
, const mbedtls_ecp_point
*pt
)
2783 mbedtls_mpi YY
, RHS
;
2785 /* pt coordinates must be normalized for our checks */
2786 if( mbedtls_mpi_cmp_int( &pt
->X
, 0 ) < 0 ||
2787 mbedtls_mpi_cmp_int( &pt
->Y
, 0 ) < 0 ||
2788 mbedtls_mpi_cmp_mpi( &pt
->X
, &grp
->P
) >= 0 ||
2789 mbedtls_mpi_cmp_mpi( &pt
->Y
, &grp
->P
) >= 0 )
2790 return( MBEDTLS_ERR_ECP_INVALID_KEY
);
2792 mbedtls_mpi_init( &YY
); mbedtls_mpi_init( &RHS
);
2796 * RHS = X (X^2 + A) + B = X^3 + A X + B
2798 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &YY
, &pt
->Y
, &pt
->Y
) ); MOD_MUL( YY
);
2799 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS
, &pt
->X
, &pt
->X
) ); MOD_MUL( RHS
);
2801 /* Special case for A = -3 */
2802 if( grp
->A
.p
== NULL
)
2804 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS
, &RHS
, 3 ) ); MOD_SUB( RHS
);
2808 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS
, &RHS
, &grp
->A
) ); MOD_ADD( RHS
);
2811 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &RHS
, &RHS
, &pt
->X
) ); MOD_MUL( RHS
);
2812 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS
, &RHS
, &grp
->B
) ); MOD_ADD( RHS
);
2814 if( mbedtls_mpi_cmp_mpi( &YY
, &RHS
) != 0 )
2815 ret
= MBEDTLS_ERR_ECP_INVALID_KEY
;
2819 mbedtls_mpi_free( &YY
); mbedtls_mpi_free( &RHS
);
2823 #endif /* ECP_SHORTWEIERSTRASS */
2826 * R = m * P with shortcuts for m == 1 and m == -1
2827 * NOT constant-time - ONLY for short Weierstrass!
2829 static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group
*grp
,
2830 mbedtls_ecp_point
*R
,
2831 const mbedtls_mpi
*m
,
2832 const mbedtls_ecp_point
*P
,
2833 mbedtls_ecp_restart_ctx
*rs_ctx
)
2837 if( mbedtls_mpi_cmp_int( m
, 1 ) == 0 )
2839 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R
, P
) );
2841 else if( mbedtls_mpi_cmp_int( m
, -1 ) == 0 )
2843 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R
, P
) );
2844 if( mbedtls_mpi_cmp_int( &R
->Y
, 0 ) != 0 )
2845 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R
->Y
, &grp
->P
, &R
->Y
) );
2849 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_restartable( grp
, R
, m
, P
,
2850 NULL
, NULL
, rs_ctx
) );
2858 * Restartable linear combination
2861 int mbedtls_ecp_muladd_restartable(
2862 mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*R
,
2863 const mbedtls_mpi
*m
, const mbedtls_ecp_point
*P
,
2864 const mbedtls_mpi
*n
, const mbedtls_ecp_point
*Q
,
2865 mbedtls_ecp_restart_ctx
*rs_ctx
)
2868 mbedtls_ecp_point mP
;
2869 mbedtls_ecp_point
*pmP
= &mP
;
2870 mbedtls_ecp_point
*pR
= R
;
2871 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2872 char is_grp_capable
= 0;
2874 ECP_VALIDATE_RET( grp
!= NULL
);
2875 ECP_VALIDATE_RET( R
!= NULL
);
2876 ECP_VALIDATE_RET( m
!= NULL
);
2877 ECP_VALIDATE_RET( P
!= NULL
);
2878 ECP_VALIDATE_RET( n
!= NULL
);
2879 ECP_VALIDATE_RET( Q
!= NULL
);
2881 if( ecp_get_type( grp
) != ECP_TYPE_SHORT_WEIERSTRASS
)
2882 return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE
);
2884 mbedtls_ecp_point_init( &mP
);
2888 #if defined(MBEDTLS_ECP_RESTARTABLE)
2889 if( rs_ctx
!= NULL
&& rs_ctx
->ma
!= NULL
)
2891 /* redirect intermediate results to restart context */
2892 pmP
= &rs_ctx
->ma
->mP
;
2893 pR
= &rs_ctx
->ma
->R
;
2895 /* jump to next operation */
2896 if( rs_ctx
->ma
->state
== ecp_rsma_mul2
)
2898 if( rs_ctx
->ma
->state
== ecp_rsma_add
)
2900 if( rs_ctx
->ma
->state
== ecp_rsma_norm
)
2903 #endif /* MBEDTLS_ECP_RESTARTABLE */
2905 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp
, pmP
, m
, P
, rs_ctx
) );
2906 #if defined(MBEDTLS_ECP_RESTARTABLE)
2907 if( rs_ctx
!= NULL
&& rs_ctx
->ma
!= NULL
)
2908 rs_ctx
->ma
->state
= ecp_rsma_mul2
;
2912 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp
, pR
, n
, Q
, rs_ctx
) );
2914 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2915 if( ( is_grp_capable
= mbedtls_internal_ecp_grp_capable( grp
) ) )
2916 MBEDTLS_MPI_CHK( mbedtls_internal_ecp_init( grp
) );
2917 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
2919 #if defined(MBEDTLS_ECP_RESTARTABLE)
2920 if( rs_ctx
!= NULL
&& rs_ctx
->ma
!= NULL
)
2921 rs_ctx
->ma
->state
= ecp_rsma_add
;
2925 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_ADD
);
2926 MBEDTLS_MPI_CHK( ecp_add_mixed( grp
, pR
, pmP
, pR
) );
2927 #if defined(MBEDTLS_ECP_RESTARTABLE)
2928 if( rs_ctx
!= NULL
&& rs_ctx
->ma
!= NULL
)
2929 rs_ctx
->ma
->state
= ecp_rsma_norm
;
2933 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV
);
2934 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp
, pR
) );
2936 #if defined(MBEDTLS_ECP_RESTARTABLE)
2937 if( rs_ctx
!= NULL
&& rs_ctx
->ma
!= NULL
)
2938 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( R
, pR
) );
2942 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
2943 if( is_grp_capable
)
2944 mbedtls_internal_ecp_free( grp
);
2945 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
2947 mbedtls_ecp_point_free( &mP
);
2955 * Linear combination
2958 int mbedtls_ecp_muladd( mbedtls_ecp_group
*grp
, mbedtls_ecp_point
*R
,
2959 const mbedtls_mpi
*m
, const mbedtls_ecp_point
*P
,
2960 const mbedtls_mpi
*n
, const mbedtls_ecp_point
*Q
)
2962 ECP_VALIDATE_RET( grp
!= NULL
);
2963 ECP_VALIDATE_RET( R
!= NULL
);
2964 ECP_VALIDATE_RET( m
!= NULL
);
2965 ECP_VALIDATE_RET( P
!= NULL
);
2966 ECP_VALIDATE_RET( n
!= NULL
);
2967 ECP_VALIDATE_RET( Q
!= NULL
);
2968 return( mbedtls_ecp_muladd_restartable( grp
, R
, m
, P
, n
, Q
, NULL
) );
2971 #if defined(ECP_MONTGOMERY)
2972 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
2973 #define ECP_MPI_INIT(s, n, p) {s, (n), (mbedtls_mpi_uint *)(p)}
2974 #define ECP_MPI_INIT_ARRAY(x) \
2975 ECP_MPI_INIT(1, sizeof(x) / sizeof(mbedtls_mpi_uint), x)
2977 * Constants for the two points other than 0, 1, -1 (mod p) in
2978 * https://cr.yp.to/ecdh.html#validate
2979 * See ecp_check_pubkey_x25519().
2981 static const mbedtls_mpi_uint x25519_bad_point_1
[] = {
2982 MBEDTLS_BYTES_TO_T_UINT_8( 0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae ),
2983 MBEDTLS_BYTES_TO_T_UINT_8( 0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a ),
2984 MBEDTLS_BYTES_TO_T_UINT_8( 0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd ),
2985 MBEDTLS_BYTES_TO_T_UINT_8( 0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00 ),
2987 static const mbedtls_mpi_uint x25519_bad_point_2
[] = {
2988 MBEDTLS_BYTES_TO_T_UINT_8( 0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24 ),
2989 MBEDTLS_BYTES_TO_T_UINT_8( 0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b ),
2990 MBEDTLS_BYTES_TO_T_UINT_8( 0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86 ),
2991 MBEDTLS_BYTES_TO_T_UINT_8( 0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57 ),
2993 static const mbedtls_mpi ecp_x25519_bad_point_1
= ECP_MPI_INIT_ARRAY(
2994 x25519_bad_point_1
);
2995 static const mbedtls_mpi ecp_x25519_bad_point_2
= ECP_MPI_INIT_ARRAY(
2996 x25519_bad_point_2
);
2997 #endif /* MBEDTLS_ECP_DP_CURVE25519_ENABLED */
3000 * Check that the input point is not one of the low-order points.
3001 * This is recommended by the "May the Fourth" paper:
3002 * https://eprint.iacr.org/2017/806.pdf
3003 * Those points are never sent by an honest peer.
3005 static int ecp_check_bad_points_mx( const mbedtls_mpi
*X
, const mbedtls_mpi
*P
,
3006 const mbedtls_ecp_group_id grp_id
)
3011 mbedtls_mpi_init( &XmP
);
3013 /* Reduce X mod P so that we only need to check values less than P.
3014 * We know X < 2^256 so we can proceed by subtraction. */
3015 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &XmP
, X
) );
3016 while( mbedtls_mpi_cmp_mpi( &XmP
, P
) >= 0 )
3017 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &XmP
, &XmP
, P
) );
3019 /* Check against the known bad values that are less than P. For Curve448
3020 * these are 0, 1 and -1. For Curve25519 we check the values less than P
3021 * from the following list: https://cr.yp.to/ecdh.html#validate */
3022 if( mbedtls_mpi_cmp_int( &XmP
, 1 ) <= 0 ) /* takes care of 0 and 1 */
3024 ret
= MBEDTLS_ERR_ECP_INVALID_KEY
;
3028 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
3029 if( grp_id
== MBEDTLS_ECP_DP_CURVE25519
)
3031 if( mbedtls_mpi_cmp_mpi( &XmP
, &ecp_x25519_bad_point_1
) == 0 )
3033 ret
= MBEDTLS_ERR_ECP_INVALID_KEY
;
3037 if( mbedtls_mpi_cmp_mpi( &XmP
, &ecp_x25519_bad_point_2
) == 0 )
3039 ret
= MBEDTLS_ERR_ECP_INVALID_KEY
;
3047 /* Final check: check if XmP + 1 is P (final because it changes XmP!) */
3048 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &XmP
, &XmP
, 1 ) );
3049 if( mbedtls_mpi_cmp_mpi( &XmP
, P
) == 0 )
3051 ret
= MBEDTLS_ERR_ECP_INVALID_KEY
;
3058 mbedtls_mpi_free( &XmP
);
3064 * Check validity of a public key for Montgomery curves with x-only schemes
3066 static int ecp_check_pubkey_mx( const mbedtls_ecp_group
*grp
, const mbedtls_ecp_point
*pt
)
3068 /* [Curve25519 p. 5] Just check X is the correct number of bytes */
3069 /* Allow any public value, if it's too big then we'll just reduce it mod p
3070 * (RFC 7748 sec. 5 para. 3). */
3071 if( mbedtls_mpi_size( &pt
->X
) > ( grp
->nbits
+ 7 ) / 8 )
3072 return( MBEDTLS_ERR_ECP_INVALID_KEY
);
3074 /* Implicit in all standards (as they don't consider negative numbers):
3075 * X must be non-negative. This is normally ensured by the way it's
3076 * encoded for transmission, but let's be extra sure. */
3077 if( mbedtls_mpi_cmp_int( &pt
->X
, 0 ) < 0 )
3078 return( MBEDTLS_ERR_ECP_INVALID_KEY
);
3080 return( ecp_check_bad_points_mx( &pt
->X
, &grp
->P
, grp
->id
) );
3082 #endif /* ECP_MONTGOMERY */
3085 * Check that a point is valid as a public key
3087 int mbedtls_ecp_check_pubkey( const mbedtls_ecp_group
*grp
,
3088 const mbedtls_ecp_point
*pt
)
3090 ECP_VALIDATE_RET( grp
!= NULL
);
3091 ECP_VALIDATE_RET( pt
!= NULL
);
3093 /* Must use affine coordinates */
3094 if( mbedtls_mpi_cmp_int( &pt
->Z
, 1 ) != 0 )
3095 return( MBEDTLS_ERR_ECP_INVALID_KEY
);
3097 #if defined(ECP_MONTGOMERY)
3098 if( ecp_get_type( grp
) == ECP_TYPE_MONTGOMERY
)
3099 return( ecp_check_pubkey_mx( grp
, pt
) );
3101 #if defined(ECP_SHORTWEIERSTRASS)
3102 if( ecp_get_type( grp
) == ECP_TYPE_SHORT_WEIERSTRASS
)
3103 return( ecp_check_pubkey_sw( grp
, pt
) );
3105 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
3109 * Check that an mbedtls_mpi is valid as a private key
3111 int mbedtls_ecp_check_privkey( const mbedtls_ecp_group
*grp
,
3112 const mbedtls_mpi
*d
)
3114 ECP_VALIDATE_RET( grp
!= NULL
);
3115 ECP_VALIDATE_RET( d
!= NULL
);
3117 #if defined(ECP_MONTGOMERY)
3118 if( ecp_get_type( grp
) == ECP_TYPE_MONTGOMERY
)
3120 /* see RFC 7748 sec. 5 para. 5 */
3121 if( mbedtls_mpi_get_bit( d
, 0 ) != 0 ||
3122 mbedtls_mpi_get_bit( d
, 1 ) != 0 ||
3123 mbedtls_mpi_bitlen( d
) - 1 != grp
->nbits
) /* mbedtls_mpi_bitlen is one-based! */
3124 return( MBEDTLS_ERR_ECP_INVALID_KEY
);
3126 /* see [Curve25519] page 5 */
3127 if( grp
->nbits
== 254 && mbedtls_mpi_get_bit( d
, 2 ) != 0 )
3128 return( MBEDTLS_ERR_ECP_INVALID_KEY
);
3132 #endif /* ECP_MONTGOMERY */
3133 #if defined(ECP_SHORTWEIERSTRASS)
3134 if( ecp_get_type( grp
) == ECP_TYPE_SHORT_WEIERSTRASS
)
3137 if( mbedtls_mpi_cmp_int( d
, 1 ) < 0 ||
3138 mbedtls_mpi_cmp_mpi( d
, &grp
->N
) >= 0 )
3139 return( MBEDTLS_ERR_ECP_INVALID_KEY
);
3143 #endif /* ECP_SHORTWEIERSTRASS */
3145 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
3149 * Generate a private key
3151 int mbedtls_ecp_gen_privkey( const mbedtls_ecp_group
*grp
,
3153 int (*f_rng
)(void *, unsigned char *, size_t),
3156 int ret
= MBEDTLS_ERR_ECP_BAD_INPUT_DATA
;
3158 #if defined(ECP_SHORTWEIERSTRASS)
3161 mbedtls_mpi_init( &one
);
3164 ECP_VALIDATE_RET( grp
!= NULL
);
3165 ECP_VALIDATE_RET( d
!= NULL
);
3166 ECP_VALIDATE_RET( f_rng
!= NULL
);
3168 n_size
= ( grp
->nbits
+ 7 ) / 8;
3170 #if defined(ECP_MONTGOMERY)
3171 if( ecp_get_type( grp
) == ECP_TYPE_MONTGOMERY
)
3177 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d
, n_size
, f_rng
, p_rng
) );
3178 } while( mbedtls_mpi_bitlen( d
) == 0);
3180 /* Make sure the most significant bit is nbits */
3181 b
= mbedtls_mpi_bitlen( d
) - 1; /* mbedtls_mpi_bitlen is one-based */
3182 if( b
> grp
->nbits
)
3183 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d
, b
- grp
->nbits
) );
3185 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d
, grp
->nbits
, 1 ) );
3187 /* Make sure the last two bits are unset for Curve448, three bits for
3189 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d
, 0, 0 ) );
3190 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d
, 1, 0 ) );
3191 if( grp
->nbits
== 254 )
3193 MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d
, 2, 0 ) );
3196 #endif /* ECP_MONTGOMERY */
3198 #if defined(ECP_SHORTWEIERSTRASS)
3199 if( ecp_get_type( grp
) == ECP_TYPE_SHORT_WEIERSTRASS
)
3201 /* SEC1 3.2.1: Generate d such that 1 <= n < N */
3203 unsigned lt_lower
= 1, lt_upper
= 0;
3205 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &one
, grp
->N
.n
) );
3206 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &one
, 1 ) );
3209 * Match the procedure given in RFC 6979 (deterministic ECDSA):
3210 * - use the same byte ordering;
3211 * - keep the leftmost nbits bits of the generated octet string;
3212 * - try until result is in the desired range.
3213 * This also avoids any biais, which is especially important for ECDSA.
3217 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d
, n_size
, f_rng
, p_rng
) );
3218 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d
, 8 * n_size
- grp
->nbits
) );
3221 * Each try has at worst a probability 1/2 of failing (the msb has
3222 * a probability 1/2 of being 0, and then the result will be < N),
3223 * so after 30 tries failure probability is a most 2**(-30).
3225 * For most curves, 1 try is enough with overwhelming probability,
3226 * since N starts with a lot of 1s in binary, but some curves
3227 * such as secp224k1 are actually very close to the worst case.
3231 ret
= MBEDTLS_ERR_ECP_RANDOM_FAILED
;
3235 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( d
, &grp
->N
, <_upper
) );
3236 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( d
, &one
, <_lower
) );
3238 while( lt_lower
!= 0 || lt_upper
== 0 );
3240 #endif /* ECP_SHORTWEIERSTRASS */
3243 #if defined(ECP_SHORTWEIERSTRASS)
3244 mbedtls_mpi_free( &one
);
3250 * Generate a keypair with configurable base point
3252 int mbedtls_ecp_gen_keypair_base( mbedtls_ecp_group
*grp
,
3253 const mbedtls_ecp_point
*G
,
3254 mbedtls_mpi
*d
, mbedtls_ecp_point
*Q
,
3255 int (*f_rng
)(void *, unsigned char *, size_t),
3259 ECP_VALIDATE_RET( grp
!= NULL
);
3260 ECP_VALIDATE_RET( d
!= NULL
);
3261 ECP_VALIDATE_RET( G
!= NULL
);
3262 ECP_VALIDATE_RET( Q
!= NULL
);
3263 ECP_VALIDATE_RET( f_rng
!= NULL
);
3265 MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp
, d
, f_rng
, p_rng
) );
3266 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( grp
, Q
, d
, G
, f_rng
, p_rng
) );
3273 * Generate key pair, wrapper for conventional base point
3275 int mbedtls_ecp_gen_keypair( mbedtls_ecp_group
*grp
,
3276 mbedtls_mpi
*d
, mbedtls_ecp_point
*Q
,
3277 int (*f_rng
)(void *, unsigned char *, size_t),
3280 ECP_VALIDATE_RET( grp
!= NULL
);
3281 ECP_VALIDATE_RET( d
!= NULL
);
3282 ECP_VALIDATE_RET( Q
!= NULL
);
3283 ECP_VALIDATE_RET( f_rng
!= NULL
);
3285 return( mbedtls_ecp_gen_keypair_base( grp
, &grp
->G
, d
, Q
, f_rng
, p_rng
) );
3289 * Generate a keypair, prettier wrapper
3291 int mbedtls_ecp_gen_key( mbedtls_ecp_group_id grp_id
, mbedtls_ecp_keypair
*key
,
3292 int (*f_rng
)(void *, unsigned char *, size_t), void *p_rng
)
3295 ECP_VALIDATE_RET( key
!= NULL
);
3296 ECP_VALIDATE_RET( f_rng
!= NULL
);
3298 if( ( ret
= mbedtls_ecp_group_load( &key
->grp
, grp_id
) ) != 0 )
3301 return( mbedtls_ecp_gen_keypair( &key
->grp
, &key
->d
, &key
->Q
, f_rng
, p_rng
) );
3305 * Check a public-private key pair
3307 int mbedtls_ecp_check_pub_priv( const mbedtls_ecp_keypair
*pub
, const mbedtls_ecp_keypair
*prv
)
3310 mbedtls_ecp_point Q
;
3311 mbedtls_ecp_group grp
;
3312 ECP_VALIDATE_RET( pub
!= NULL
);
3313 ECP_VALIDATE_RET( prv
!= NULL
);
3315 if( pub
->grp
.id
== MBEDTLS_ECP_DP_NONE
||
3316 pub
->grp
.id
!= prv
->grp
.id
||
3317 mbedtls_mpi_cmp_mpi( &pub
->Q
.X
, &prv
->Q
.X
) ||
3318 mbedtls_mpi_cmp_mpi( &pub
->Q
.Y
, &prv
->Q
.Y
) ||
3319 mbedtls_mpi_cmp_mpi( &pub
->Q
.Z
, &prv
->Q
.Z
) )
3321 return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA
);
3324 mbedtls_ecp_point_init( &Q
);
3325 mbedtls_ecp_group_init( &grp
);
3327 /* mbedtls_ecp_mul() needs a non-const group... */
3328 mbedtls_ecp_group_copy( &grp
, &prv
->grp
);
3330 /* Also checks d is valid */
3331 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp
, &Q
, &prv
->d
, &prv
->grp
.G
, NULL
, NULL
) );
3333 if( mbedtls_mpi_cmp_mpi( &Q
.X
, &prv
->Q
.X
) ||
3334 mbedtls_mpi_cmp_mpi( &Q
.Y
, &prv
->Q
.Y
) ||
3335 mbedtls_mpi_cmp_mpi( &Q
.Z
, &prv
->Q
.Z
) )
3337 ret
= MBEDTLS_ERR_ECP_BAD_INPUT_DATA
;
3342 mbedtls_ecp_point_free( &Q
);
3343 mbedtls_ecp_group_free( &grp
);
3348 #if defined(MBEDTLS_SELF_TEST)
3350 #if defined(ECP_ONE_STEP_KDF)
3352 * There are no test vectors from NIST for the One-Step KDF in SP 800-56C,
3353 * but unofficial ones can be found at:
3354 * https://github.com/patrickfav/singlestep-kdf/wiki/NIST-SP-800-56C-Rev1:-Non-Official-Test-Vectors
3356 * We only use the ones with empty fixedInfo, and for brevity's sake, only
3357 * 40-bytes output (with SHA-256 that's more than one block, and with SHA-512
3358 * less than one block).
3360 #if defined(MBEDTLS_SHA512_C)
3362 static const uint8_t test_kdf_z
[16] = {
3363 0x3b, 0xa9, 0x79, 0xe9, 0xbc, 0x5e, 0x3e, 0xc7,
3364 0x61, 0x30, 0x36, 0xb6, 0xf5, 0x1c, 0xd5, 0xaa,
3366 static const uint8_t test_kdf_out
[40] = {
3367 0x3e, 0xf6, 0xda, 0xf9, 0x51, 0x60, 0x70, 0x5f,
3368 0xdf, 0x21, 0xcd, 0xab, 0xac, 0x25, 0x7b, 0x05,
3369 0xfe, 0xc1, 0xab, 0x7c, 0xc9, 0x68, 0x43, 0x25,
3370 0x8a, 0xfc, 0x40, 0x6e, 0x5b, 0xf7, 0x98, 0x27,
3371 0x10, 0xfa, 0x7b, 0x93, 0x52, 0xd4, 0x16, 0xaa,
3374 #elif defined(MBEDTLS_SHA256_C)
3376 static const uint8_t test_kdf_z
[16] = {
3377 0xc8, 0x3e, 0x35, 0x8e, 0x99, 0xa6, 0x89, 0xc6,
3378 0x7d, 0xb4, 0xfe, 0x39, 0xcf, 0x8f, 0x26, 0xe1,
3380 static const uint8_t test_kdf_out
[40] = {
3381 0x7d, 0xf6, 0x41, 0xf8, 0x3c, 0x47, 0xdc, 0x28,
3382 0x5f, 0x7f, 0xaa, 0xde, 0x05, 0x64, 0xd6, 0x25,
3383 0x00, 0x6a, 0x47, 0xd9, 0x1e, 0xa4, 0xa0, 0x8c,
3384 0xd7, 0xf7, 0x0c, 0x99, 0xaa, 0xa0, 0x72, 0x66,
3385 0x69, 0x0e, 0x25, 0xaa, 0xa1, 0x63, 0x14, 0x79,
3390 static int ecp_kdf_self_test( void )
3393 ecp_drbg_context kdf_ctx
;
3395 uint8_t out
[sizeof( test_kdf_out
)];
3397 ecp_drbg_init( &kdf_ctx
);
3398 mbedtls_mpi_init( &scalar
);
3399 memset( out
, 0, sizeof( out
) );
3401 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &scalar
,
3402 test_kdf_z
, sizeof( test_kdf_z
) ) );
3404 MBEDTLS_MPI_CHK( ecp_drbg_seed( &kdf_ctx
,
3405 &scalar
, sizeof( test_kdf_z
) ) );
3407 MBEDTLS_MPI_CHK( ecp_drbg_random( &kdf_ctx
, out
, sizeof( out
) ) );
3409 if( memcmp( out
, test_kdf_out
, sizeof( out
) ) != 0 )
3413 ecp_drbg_free( &kdf_ctx
);
3414 mbedtls_mpi_free( &scalar
);
3418 #endif /* ECP_ONE_STEP_KDF */
3423 int mbedtls_ecp_self_test( int verbose
)
3427 mbedtls_ecp_group grp
;
3428 mbedtls_ecp_point R
, P
;
3430 unsigned long add_c_prev
, dbl_c_prev
, mul_c_prev
;
3431 /* exponents especially adapted for secp192r1 */
3432 const char *exponents
[] =
3434 "000000000000000000000000000000000000000000000001", /* one */
3435 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */
3436 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
3437 "400000000000000000000000000000000000000000000000", /* one and zeros */
3438 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
3439 "555555555555555555555555555555555555555555555555", /* 101010... */
3442 mbedtls_ecp_group_init( &grp
);
3443 mbedtls_ecp_point_init( &R
);
3444 mbedtls_ecp_point_init( &P
);
3445 mbedtls_mpi_init( &m
);
3447 /* Use secp192r1 if available, or any available curve */
3448 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
3449 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp
, MBEDTLS_ECP_DP_SECP192R1
) );
3451 MBEDTLS_MPI_CHK( mbedtls_ecp_group_load( &grp
, mbedtls_ecp_curve_list()->grp_id
) );
3455 mbedtls_printf( " ECP test #1 (constant op_count, base point G): " );
3457 /* Do a dummy multiplication first to trigger precomputation */
3458 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &m
, 2 ) );
3459 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp
, &P
, &m
, &grp
.G
, NULL
, NULL
) );
3464 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m
, 16, exponents
[0] ) );
3465 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp
, &R
, &m
, &grp
.G
, NULL
, NULL
) );
3467 for( i
= 1; i
< sizeof( exponents
) / sizeof( exponents
[0] ); i
++ )
3469 add_c_prev
= add_count
;
3470 dbl_c_prev
= dbl_count
;
3471 mul_c_prev
= mul_count
;
3476 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m
, 16, exponents
[i
] ) );
3477 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp
, &R
, &m
, &grp
.G
, NULL
, NULL
) );
3479 if( add_count
!= add_c_prev
||
3480 dbl_count
!= dbl_c_prev
||
3481 mul_count
!= mul_c_prev
)
3484 mbedtls_printf( "failed (%u)\n", (unsigned int) i
);
3492 mbedtls_printf( "passed\n" );
3495 mbedtls_printf( " ECP test #2 (constant op_count, other point): " );
3496 /* We computed P = 2G last time, use it */
3501 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m
, 16, exponents
[0] ) );
3502 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp
, &R
, &m
, &P
, NULL
, NULL
) );
3504 for( i
= 1; i
< sizeof( exponents
) / sizeof( exponents
[0] ); i
++ )
3506 add_c_prev
= add_count
;
3507 dbl_c_prev
= dbl_count
;
3508 mul_c_prev
= mul_count
;
3513 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &m
, 16, exponents
[i
] ) );
3514 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp
, &R
, &m
, &P
, NULL
, NULL
) );
3516 if( add_count
!= add_c_prev
||
3517 dbl_count
!= dbl_c_prev
||
3518 mul_count
!= mul_c_prev
)
3521 mbedtls_printf( "failed (%u)\n", (unsigned int) i
);
3529 mbedtls_printf( "passed\n" );
3531 #if defined(ECP_ONE_STEP_KDF)
3533 mbedtls_printf( " ECP test #3 (internal KDF): " );
3535 ret
= ecp_kdf_self_test();
3539 mbedtls_printf( "failed\n" );
3546 mbedtls_printf( "passed\n" );
3547 #endif /* ECP_ONE_STEP_KDF */
3551 if( ret
< 0 && verbose
!= 0 )
3552 mbedtls_printf( "Unexpected error, return code = %08X\n", ret
);
3554 mbedtls_ecp_group_free( &grp
);
3555 mbedtls_ecp_point_free( &R
);
3556 mbedtls_ecp_point_free( &P
);
3557 mbedtls_mpi_free( &m
);
3560 mbedtls_printf( "\n" );
3565 #endif /* MBEDTLS_SELF_TEST */
3567 #endif /* !MBEDTLS_ECP_ALT */
3569 #endif /* MBEDTLS_ECP_C */