ReactOS 0.4.15-dev-8219-ge8b88cf
ecp.c
Go to the documentation of this file.
1/*
2 * Elliptic curves over GF(p): generic functions
3 *
4 * Copyright The Mbed TLS Contributors
5 * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
6 *
7 * This file is provided under the Apache License 2.0, or the
8 * GNU General Public License v2.0 or later.
9 *
10 * **********
11 * Apache License 2.0:
12 *
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
16 *
17 * http://www.apache.org/licenses/LICENSE-2.0
18 *
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.
24 *
25 * **********
26 *
27 * **********
28 * GNU General Public License v2.0 or later:
29 *
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.
34 *
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.
39 *
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.
43 *
44 * **********
45 */
46
47/*
48 * References:
49 *
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
55 *
56 * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf
57 *
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>
62 *
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>
67 */
68
69#if !defined(MBEDTLS_CONFIG_FILE)
70#include "mbedtls/config.h"
71#else
72#include MBEDTLS_CONFIG_FILE
73#endif
74
101#if defined(MBEDTLS_ECP_INTERNAL_ALT)
102#endif
103
104#if defined(MBEDTLS_ECP_C)
105
106#include "mbedtls/ecp.h"
107#include "mbedtls/threading.h"
109#include "mbedtls/bn_mul.h"
110
111#include <string.h>
112
113#if !defined(MBEDTLS_ECP_ALT)
114
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 )
120
121#if defined(MBEDTLS_PLATFORM_C)
122#include "mbedtls/platform.h"
123#else
124#include <stdlib.h>
125#include <stdio.h>
126#define mbedtls_printf printf
127#define mbedtls_calloc calloc
128#define mbedtls_free free
129#endif
130
131#include "mbedtls/ecp_internal.h"
132
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"
142#else
143#error "Invalid configuration detected. Include check_config.h to ensure that the configuration is valid."
144#endif
145#endif /* MBEDTLS_ECP_NO_INTERNAL_RNG */
146
147#if ( defined(__ARMCC_VERSION) || defined(_MSC_VER) ) && \
148 !defined(inline) && !defined(__cplusplus)
149#define inline __inline
150#endif
151
152#if defined(MBEDTLS_SELF_TEST)
153/*
154 * Counts of point addition and doubling, and field multiplications.
155 * Used to test resistance of point multiplication to simple timing attacks.
156 */
157static unsigned long add_count, dbl_count, mul_count;
158#endif
159
160#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
161/*
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.
167 *
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.
171 *
172 * Unfortunately those would break compatibility. So what we do instead is
173 * have our own internal DRBG instance, seeded from the secret scalar.
174 *
175 * The following is a light-weight abstraction layer for doing that with
176 * HMAC_DRBG (first choice) or CTR_DRBG.
177 */
178
179#if defined(MBEDTLS_HMAC_DRBG_C)
180
181/* DRBG context type */
182typedef mbedtls_hmac_drbg_context ecp_drbg_context;
183
184/* DRBG context init */
185static inline void ecp_drbg_init( ecp_drbg_context *ctx )
186{
188}
189
190/* DRBG context free */
191static inline void ecp_drbg_free( ecp_drbg_context *ctx )
192{
194}
195
196/* DRBG function */
197static inline int ecp_drbg_random( void *p_rng,
198 unsigned char *output, size_t output_len )
199{
200 return( mbedtls_hmac_drbg_random( p_rng, output, output_len ) );
201}
202
203/* DRBG context seeding */
204static int ecp_drbg_seed( ecp_drbg_context *ctx,
205 const mbedtls_mpi *secret, size_t secret_len )
206{
207 int ret;
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 );
212
214 secret_bytes, secret_len ) );
215
216 ret = mbedtls_hmac_drbg_seed_buf( ctx, md_info, secret_bytes, secret_len );
217
218cleanup:
219 mbedtls_platform_zeroize( secret_bytes, secret_len );
220
221 return( ret );
222}
223
224#elif defined(MBEDTLS_CTR_DRBG_C)
225
226/* DRBG context type */
227typedef mbedtls_ctr_drbg_context ecp_drbg_context;
228
229/* DRBG context init */
230static inline void ecp_drbg_init( ecp_drbg_context *ctx )
231{
233}
234
235/* DRBG context free */
236static inline void ecp_drbg_free( ecp_drbg_context *ctx )
237{
239}
240
241/* DRBG function */
242static inline int ecp_drbg_random( void *p_rng,
243 unsigned char *output, size_t output_len )
244{
245 return( mbedtls_ctr_drbg_random( p_rng, output, output_len ) );
246}
247
248/*
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.)
254 */
255static int ecp_ctr_drbg_null_entropy(void *ctx, unsigned char *out, size_t len)
256{
257 (void) ctx;
258 memset( out, 0, len );
259 return( 0 );
260}
261
262/* DRBG context seeding */
263static int ecp_drbg_seed( ecp_drbg_context *ctx,
264 const mbedtls_mpi *secret, size_t secret_len )
265{
266 int ret;
267 unsigned char secret_bytes[MBEDTLS_ECP_MAX_BYTES];
268
270 secret_bytes, secret_len ) );
271
272 ret = mbedtls_ctr_drbg_seed( ctx, ecp_ctr_drbg_null_entropy, NULL,
273 secret_bytes, secret_len );
274
275cleanup:
276 mbedtls_platform_zeroize( secret_bytes, secret_len );
277
278 return( ret );
279}
280
281#elif defined(MBEDTLS_SHA512_C) || defined(MBEDTLS_SHA256_C)
282
283/* This will be used in the self-test function */
284#define ECP_ONE_STEP_KDF
285
286/*
287 * We need to expand secret data (the scalar) into a longer stream of bytes.
288 *
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.)
292 *
293 * We need a basic hash abstraction layer to use whatever SHA-2 is available.
294 */
295#if defined(MBEDTLS_SHA512_C)
296
297#define HASH_FUNC( in, ilen, out ) mbedtls_sha512_ret( in, ilen, out, 0 );
298#define HASH_BLOCK_BYTES ( 512 / 8 )
299
300#elif defined(MBEDTLS_SHA256_C)
301
302#define HASH_FUNC( in, ilen, out ) mbedtls_sha256_ret( in, ilen, out, 0 );
303#define HASH_BLOCK_BYTES ( 256 / 8 )
304
305#endif /* SHA512/SHA256 abstraction */
306
307/*
308 * State consists of a 32-bit counter plus the secret value.
309 *
310 * We stored them concatenated in a single buffer as that's what will get
311 * passed to the hash function.
312 */
313typedef struct {
314 size_t total_len;
316} ecp_drbg_context;
317
318static void ecp_drbg_init( ecp_drbg_context *ctx )
319{
320 memset( ctx, 0, sizeof( ecp_drbg_context ) );
321}
322
323static void ecp_drbg_free( ecp_drbg_context *ctx )
324{
325 mbedtls_platform_zeroize( ctx, sizeof( ecp_drbg_context ) );
326}
327
328static int ecp_drbg_seed( ecp_drbg_context *ctx,
329 const mbedtls_mpi *secret, size_t secret_len )
330{
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 ) );
334}
335
336static int ecp_drbg_random( void *p_rng, unsigned char *output, size_t output_len )
337{
338 ecp_drbg_context *ctx = p_rng;
339 int ret;
340 size_t len_done = 0;
341 uint8_t tmp[HASH_BLOCK_BYTES];
342
343 while( len_done < output_len )
344 {
345 uint8_t use_len;
346
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.
351 *
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.
355 *
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.
359 */
360 ctx->buf[3] += 1;
361 if( ctx->buf[3] == 0 )
363
364 ret = HASH_FUNC( ctx->buf, ctx->total_len, tmp );
365 if( ret != 0 )
366 return( ret );
367
368 if( output_len - len_done > HASH_BLOCK_BYTES )
369 use_len = HASH_BLOCK_BYTES;
370 else
371 use_len = output_len - len_done;
372
373 memcpy( output + len_done, tmp, use_len );
374 len_done += use_len;
375 }
376
377 mbedtls_platform_zeroize( tmp, sizeof( tmp ) );
378
379 return( 0 );
380}
381
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 */
386
387#if defined(MBEDTLS_ECP_RESTARTABLE)
388/*
389 * Maximum number of "basic operations" to be done in a row.
390 *
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.
394 *
395 * Setting ecp_max_ops=1 can be suitable for testing purposes
396 * as it will interrupt computation at all possible points.
397 */
398static unsigned ecp_max_ops = 0;
399
400/*
401 * Set ecp_max_ops
402 */
403void mbedtls_ecp_set_max_ops( unsigned max_ops )
404{
405 ecp_max_ops = max_ops;
406}
407
408/*
409 * Check if restart is enabled
410 */
411int mbedtls_ecp_restart_is_enabled( void )
412{
413 return( ecp_max_ops != 0 );
414}
415
416/*
417 * Restart sub-context for ecp_mul_comb()
418 */
419struct mbedtls_ecp_restart_mul
420{
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 */
433 } state;
434#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
435 ecp_drbg_context drbg_ctx;
436 unsigned char drbg_seeded;
437#endif
438};
439
440/*
441 * Init restart_mul sub-context
442 */
443static void ecp_restart_rsm_init( mbedtls_ecp_restart_mul_ctx *ctx )
444{
446 ctx->i = 0;
447 ctx->T = NULL;
448 ctx->T_size = 0;
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;
453#endif
454}
455
456/*
457 * Free the components of a restart_mul sub-context
458 */
459static void ecp_restart_rsm_free( mbedtls_ecp_restart_mul_ctx *ctx )
460{
461 unsigned char i;
462
463 if( ctx == NULL )
464 return;
465
467
468 if( ctx->T != NULL )
469 {
470 for( i = 0; i < ctx->T_size; i++ )
472 mbedtls_free( ctx->T );
473 }
474
475#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
476 ecp_drbg_free( &ctx->drbg_ctx );
477#endif
478
479 ecp_restart_rsm_init( ctx );
480}
481
482/*
483 * Restart context for ecp_muladd()
484 */
485struct mbedtls_ecp_restart_muladd
486{
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 */
494 } state;
495};
496
497/*
498 * Init restart_muladd sub-context
499 */
500static void ecp_restart_ma_init( mbedtls_ecp_restart_muladd_ctx *ctx )
501{
504 ctx->state = ecp_rsma_mul1;
505}
506
507/*
508 * Free the components of a restart_muladd sub-context
509 */
510static void ecp_restart_ma_free( mbedtls_ecp_restart_muladd_ctx *ctx )
511{
512 if( ctx == NULL )
513 return;
514
517
518 ecp_restart_ma_init( ctx );
519}
520
521/*
522 * Initialize a restart context
523 */
524void mbedtls_ecp_restart_init( mbedtls_ecp_restart_ctx *ctx )
525{
526 ECP_VALIDATE( ctx != NULL );
527 ctx->ops_done = 0;
528 ctx->depth = 0;
529 ctx->rsm = NULL;
530 ctx->ma = NULL;
531}
532
533/*
534 * Free the components of a restart context
535 */
536void mbedtls_ecp_restart_free( mbedtls_ecp_restart_ctx *ctx )
537{
538 if( ctx == NULL )
539 return;
540
541 ecp_restart_rsm_free( ctx->rsm );
542 mbedtls_free( ctx->rsm );
543
544 ecp_restart_ma_free( ctx->ma );
545 mbedtls_free( ctx->ma );
546
547 mbedtls_ecp_restart_init( ctx );
548}
549
550/*
551 * Check if we can do the next step
552 */
553int mbedtls_ecp_check_budget( const mbedtls_ecp_group *grp,
555 unsigned ops )
556{
557 ECP_VALIDATE_RET( grp != NULL );
558
559 if( rs_ctx != NULL && ecp_max_ops != 0 )
560 {
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 )
564 ops *= 4;
565 else if( grp->pbits >= 384 )
566 ops *= 2;
567
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 ) )
575 {
577 }
578
579 /* update running count */
580 rs_ctx->ops_done += ops;
581 }
582
583 return( 0 );
584}
585
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; \
591 \
592 /* set up our own sub-context if needed */ \
593 if( mbedtls_ecp_restart_is_enabled() && \
594 rs_ctx != NULL && rs_ctx->SUB == NULL ) \
595 { \
596 rs_ctx->SUB = mbedtls_calloc( 1, sizeof( *rs_ctx->SUB ) ); \
597 if( rs_ctx->SUB == NULL ) \
598 return( MBEDTLS_ERR_ECP_ALLOC_FAILED ); \
599 \
600 ecp_restart_## SUB ##_init( rs_ctx->SUB ); \
601 } \
602} while( 0 )
603
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 ) \
609 { \
610 ecp_restart_## SUB ##_free( rs_ctx->SUB ); \
611 mbedtls_free( rs_ctx->SUB ); \
612 rs_ctx->SUB = NULL; \
613 } \
614 \
615 if( rs_ctx != NULL ) \
616 rs_ctx->depth--; \
617} while( 0 )
618
619#else /* MBEDTLS_ECP_RESTARTABLE */
620
621#define ECP_RS_ENTER( sub ) (void) rs_ctx;
622#define ECP_RS_LEAVE( sub ) (void) rs_ctx;
623
624#endif /* MBEDTLS_ECP_RESTARTABLE */
625
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
638#endif
639
640#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) || \
641 defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
642#define ECP_MONTGOMERY
643#endif
644
645/*
646 * Curve types: internal for now, might be exposed later
647 */
648typedef enum
649{
650 ECP_TYPE_NONE = 0,
651 ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */
652 ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */
653} ecp_curve_type;
654
655/*
656 * List of supported curves:
657 * - internal ID
658 * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
659 * - size in bits
660 * - readable name
661 *
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.
664 *
665 * Reminder: update profiles in x509_crt.c when adding a new curves!
666 */
667static const mbedtls_ecp_curve_info ecp_supported_curves[] =
668{
669#if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
670 { MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" },
671#endif
672#if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
673 { MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" },
674#endif
675#if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
676 { MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" },
677#endif
678#if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
679 { MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" },
680#endif
681#if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
682 { MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" },
683#endif
684#if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
685 { MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" },
686#endif
687#if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
688 { MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" },
689#endif
690#if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
691 { MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" },
692#endif
693#if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
694 { MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" },
695#endif
696#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
697 { MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" },
698#endif
699#if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
700 { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" },
701#endif
702 { MBEDTLS_ECP_DP_NONE, 0, 0, NULL },
703};
704
705#define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \
706 sizeof( ecp_supported_curves[0] )
707
708static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
709
710/*
711 * List of supported curves and associated info
712 */
714{
715 return( ecp_supported_curves );
716}
717
718/*
719 * List of supported curves, group ID only
720 */
722{
723 static int init_done = 0;
724
725 if( ! init_done )
726 {
727 size_t i = 0;
728 const mbedtls_ecp_curve_info *curve_info;
729
730 for( curve_info = mbedtls_ecp_curve_list();
731 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
732 curve_info++ )
733 {
734 ecp_supported_grp_id[i++] = curve_info->grp_id;
735 }
736 ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
737
738 init_done = 1;
739 }
740
741 return( ecp_supported_grp_id );
742}
743
744/*
745 * Get the curve info for the internal identifier
746 */
748{
749 const mbedtls_ecp_curve_info *curve_info;
750
751 for( curve_info = mbedtls_ecp_curve_list();
752 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
753 curve_info++ )
754 {
755 if( curve_info->grp_id == grp_id )
756 return( curve_info );
757 }
758
759 return( NULL );
760}
761
762/*
763 * Get the curve info from the TLS identifier
764 */
766{
767 const mbedtls_ecp_curve_info *curve_info;
768
769 for( curve_info = mbedtls_ecp_curve_list();
770 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
771 curve_info++ )
772 {
773 if( curve_info->tls_id == tls_id )
774 return( curve_info );
775 }
776
777 return( NULL );
778}
779
780/*
781 * Get the curve info from the name
782 */
784{
785 const mbedtls_ecp_curve_info *curve_info;
786
787 if( name == NULL )
788 return( NULL );
789
790 for( curve_info = mbedtls_ecp_curve_list();
791 curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
792 curve_info++ )
793 {
794 if( strcmp( curve_info->name, name ) == 0 )
795 return( curve_info );
796 }
797
798 return( NULL );
799}
800
801/*
802 * Get the type of a curve
803 */
804static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp )
805{
806 if( grp->G.X.p == NULL )
807 return( ECP_TYPE_NONE );
808
809 if( grp->G.Y.p == NULL )
810 return( ECP_TYPE_MONTGOMERY );
811 else
812 return( ECP_TYPE_SHORT_WEIERSTRASS );
813}
814
815/*
816 * Initialize (the components of) a point
817 */
819{
820 ECP_VALIDATE( pt != NULL );
821
822 mbedtls_mpi_init( &pt->X );
823 mbedtls_mpi_init( &pt->Y );
824 mbedtls_mpi_init( &pt->Z );
825}
826
827/*
828 * Initialize (the components of) a group
829 */
831{
832 ECP_VALIDATE( grp != NULL );
833
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 );
840 grp->pbits = 0;
841 grp->nbits = 0;
842 grp->h = 0;
843 grp->modp = NULL;
844 grp->t_pre = NULL;
845 grp->t_post = NULL;
846 grp->t_data = NULL;
847 grp->T = NULL;
848 grp->T_size = 0;
849}
850
851/*
852 * Initialize (the components of) a key pair
853 */
855{
856 ECP_VALIDATE( key != NULL );
857
859 mbedtls_mpi_init( &key->d );
861}
862
863/*
864 * Unallocate (the components of) a point
865 */
867{
868 if( pt == NULL )
869 return;
870
871 mbedtls_mpi_free( &( pt->X ) );
872 mbedtls_mpi_free( &( pt->Y ) );
873 mbedtls_mpi_free( &( pt->Z ) );
874}
875
876/*
877 * Unallocate (the components of) a group
878 */
880{
881 size_t i;
882
883 if( grp == NULL )
884 return;
885
886 if( grp->h != 1 )
887 {
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 );
893 }
894
895 if( grp->T != NULL )
896 {
897 for( i = 0; i < grp->T_size; i++ )
898 mbedtls_ecp_point_free( &grp->T[i] );
899 mbedtls_free( grp->T );
900 }
901
903}
904
905/*
906 * Unallocate (the components of) a key pair
907 */
909{
910 if( key == NULL )
911 return;
912
914 mbedtls_mpi_free( &key->d );
916}
917
918/*
919 * Copy the contents of a point
920 */
922{
923 int ret;
924 ECP_VALIDATE_RET( P != NULL );
925 ECP_VALIDATE_RET( Q != NULL );
926
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 ) );
930
931cleanup:
932 return( ret );
933}
934
935/*
936 * Copy the contents of a group object
937 */
939{
940 ECP_VALIDATE_RET( dst != NULL );
941 ECP_VALIDATE_RET( src != NULL );
942
943 return( mbedtls_ecp_group_load( dst, src->id ) );
944}
945
946/*
947 * Set point to zero
948 */
950{
951 int ret;
952 ECP_VALIDATE_RET( pt != NULL );
953
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 ) );
957
958cleanup:
959 return( ret );
960}
961
962/*
963 * Tell if a point is zero
964 */
966{
967 ECP_VALIDATE_RET( pt != NULL );
968
969 return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 );
970}
971
972/*
973 * Compare two points lazily
974 */
976 const mbedtls_ecp_point *Q )
977{
978 ECP_VALIDATE_RET( P != NULL );
979 ECP_VALIDATE_RET( Q != NULL );
980
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 )
984 {
985 return( 0 );
986 }
987
989}
990
991/*
992 * Import a non-zero point from ASCII strings
993 */
995 const char *x, const char *y )
996{
997 int ret;
998 ECP_VALIDATE_RET( P != NULL );
999 ECP_VALIDATE_RET( x != NULL );
1000 ECP_VALIDATE_RET( y != NULL );
1001
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 ) );
1005
1006cleanup:
1007 return( ret );
1008}
1009
1010/*
1011 * Export a point into unsigned binary data (SEC1 2.3.3)
1012 */
1014 const mbedtls_ecp_point *P,
1015 int format, size_t *olen,
1016 unsigned char *buf, size_t buflen )
1017{
1018 int ret = 0;
1019 size_t plen;
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 ||
1026
1027 /*
1028 * Common case: P == 0
1029 */
1030 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
1031 {
1032 if( buflen < 1 )
1034
1035 buf[0] = 0x00;
1036 *olen = 1;
1037
1038 return( 0 );
1039 }
1040
1041 plen = mbedtls_mpi_size( &grp->P );
1042
1044 {
1045 *olen = 2 * plen + 1;
1046
1047 if( buflen < *olen )
1049
1050 buf[0] = 0x04;
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 ) );
1053 }
1054 else if( format == MBEDTLS_ECP_PF_COMPRESSED )
1055 {
1056 *olen = plen + 1;
1057
1058 if( buflen < *olen )
1060
1061 buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 );
1062 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
1063 }
1064
1065cleanup:
1066 return( ret );
1067}
1068
1069/*
1070 * Import a point from unsigned binary data (SEC1 2.3.4)
1071 */
1074 const unsigned char *buf, size_t ilen )
1075{
1076 int ret;
1077 size_t plen;
1078 ECP_VALIDATE_RET( grp != NULL );
1079 ECP_VALIDATE_RET( pt != NULL );
1080 ECP_VALIDATE_RET( buf != NULL );
1081
1082 if( ilen < 1 )
1084
1085 if( buf[0] == 0x00 )
1086 {
1087 if( ilen == 1 )
1088 return( mbedtls_ecp_set_zero( pt ) );
1089 else
1091 }
1092
1093 plen = mbedtls_mpi_size( &grp->P );
1094
1095 if( buf[0] != 0x04 )
1097
1098 if( ilen != 2 * plen + 1 )
1100
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 ) );
1104
1105cleanup:
1106 return( ret );
1107}
1108
1109/*
1110 * Import a point from a TLS ECPoint record (RFC 4492)
1111 * struct {
1112 * opaque point <1..2^8-1>;
1113 * } ECPoint;
1114 */
1117 const unsigned char **buf, size_t buf_len )
1118{
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 );
1125
1126 /*
1127 * We must have at least two bytes (1 for length, at least one for data)
1128 */
1129 if( buf_len < 2 )
1131
1132 data_len = *(*buf)++;
1133 if( data_len < 1 || data_len > buf_len - 1 )
1135
1136 /*
1137 * Save buffer start for read_binary and update buf
1138 */
1139 buf_start = *buf;
1140 *buf += data_len;
1141
1142 return( mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len ) );
1143}
1144
1145/*
1146 * Export a point as a TLS ECPoint record (RFC 4492)
1147 * struct {
1148 * opaque point <1..2^8-1>;
1149 * } ECPoint;
1150 */
1152 int format, size_t *olen,
1153 unsigned char *buf, size_t blen )
1154{
1155 int ret;
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 ||
1162
1163 /*
1164 * buffer length must be at least one, for our length byte
1165 */
1166 if( blen < 1 )
1168
1170 olen, buf + 1, blen - 1) ) != 0 )
1171 return( ret );
1172
1173 /*
1174 * write length to the first byte and update total length
1175 */
1176 buf[0] = (unsigned char) *olen;
1177 ++*olen;
1178
1179 return( 0 );
1180}
1181
1182/*
1183 * Set a group from an ECParameters record (RFC 4492)
1184 */
1186 const unsigned char **buf, size_t len )
1187{
1188 int ret;
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 );
1193
1194 if( ( ret = mbedtls_ecp_tls_read_group_id( &grp_id, buf, len ) ) != 0 )
1195 return( ret );
1196
1197 return( mbedtls_ecp_group_load( grp, grp_id ) );
1198}
1199
1200/*
1201 * Read a group id from an ECParameters record (RFC 4492) and convert it to
1202 * mbedtls_ecp_group_id.
1203 */
1205 const unsigned char **buf, size_t len )
1206{
1207 uint16_t tls_id;
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 );
1212
1213 /*
1214 * We expect at least three bytes (see below)
1215 */
1216 if( len < 3 )
1218
1219 /*
1220 * First byte is curve_type; only named_curve is handled
1221 */
1222 if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE )
1224
1225 /*
1226 * Next two bytes are the namedcurve value
1227 */
1228 tls_id = *(*buf)++;
1229 tls_id <<= 8;
1230 tls_id |= *(*buf)++;
1231
1232 if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
1234
1235 *grp = curve_info->grp_id;
1236
1237 return( 0 );
1238}
1239
1240/*
1241 * Write the ECParameters record corresponding to a group (RFC 4492)
1242 */
1243int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen,
1244 unsigned char *buf, size_t blen )
1245{
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 );
1250
1251 if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL )
1253
1254 /*
1255 * We are going to write 3 bytes (see below)
1256 */
1257 *olen = 3;
1258 if( blen < *olen )
1260
1261 /*
1262 * First byte is curve_type, always named_curve
1263 */
1265
1266 /*
1267 * Next two bytes are the namedcurve value
1268 */
1269 buf[0] = curve_info->tls_id >> 8;
1270 buf[1] = curve_info->tls_id & 0xFF;
1271
1272 return( 0 );
1273}
1274
1275/*
1276 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
1277 * See the documentation of struct mbedtls_ecp_group.
1278 *
1279 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
1280 */
1281static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp )
1282{
1283 int ret;
1284
1285 if( grp->modp == NULL )
1286 return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) );
1287
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 )
1291 {
1293 }
1294
1295 MBEDTLS_MPI_CHK( grp->modp( N ) );
1296
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 ) );
1300
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 ) );
1304
1305cleanup:
1306 return( ret );
1307}
1308
1309/*
1310 * Fast mod-p functions expect their argument to be in the 0..p^2 range.
1311 *
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.
1315 *
1316 * The following macros are shortcuts for doing that.
1317 */
1318
1319/*
1320 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
1321 */
1322#if defined(MBEDTLS_SELF_TEST)
1323#define INC_MUL_COUNT mul_count++;
1324#else
1325#define INC_MUL_COUNT
1326#endif
1327
1328#define MOD_MUL( N ) \
1329 do \
1330 { \
1331 MBEDTLS_MPI_CHK( ecp_modp( &(N), grp ) ); \
1332 INC_MUL_COUNT \
1333 } while( 0 )
1334
1335/*
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
1338 */
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 ) )
1342
1343/*
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
1346 * a bit faster.
1347 */
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 ) )
1351
1352#if defined(ECP_SHORTWEIERSTRASS)
1353/*
1354 * For curves in short Weierstrass form, we do all the internal operations in
1355 * Jacobian coordinates.
1356 *
1357 * For multiplication, we'll use a comb method with coutermeasueres against
1358 * SPA, hence timing attacks.
1359 */
1360
1361/*
1362 * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1)
1363 * Cost: 1N := 1I + 3M + 1S
1364 */
1365static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt )
1366{
1367 int ret;
1368 mbedtls_mpi Zi, ZZi;
1369
1370 if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 )
1371 return( 0 );
1372
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 */
1377
1378 mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
1379
1380 /*
1381 * X = X / Z^2 mod p
1382 */
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 );
1386
1387 /*
1388 * Y = Y / Z^3 mod p
1389 */
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 );
1392
1393 /*
1394 * Z = 1
1395 */
1396 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
1397
1398cleanup:
1399
1400 mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
1401
1402 return( ret );
1403}
1404
1405/*
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.)
1410 *
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().
1413 *
1414 * Cost: 1N(t) := 1I + (6t - 3)M + 1S
1415 */
1416static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
1417 mbedtls_ecp_point *T[], size_t T_size )
1418{
1419 int ret;
1420 size_t i;
1421 mbedtls_mpi *c, u, Zi, ZZi;
1422
1423 if( T_size < 2 )
1424 return( ecp_normalize_jac( grp, *T ) );
1425
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 ) );
1429#endif
1430
1431 if( ( c = mbedtls_calloc( T_size, sizeof( mbedtls_mpi ) ) ) == NULL )
1433
1434 for( i = 0; i < T_size; i++ )
1435 mbedtls_mpi_init( &c[i] );
1436
1438
1439 /*
1440 * c[i] = Z_0 * ... * Z_i
1441 */
1442 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) );
1443 for( i = 1; i < T_size; i++ )
1444 {
1445 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );
1446 MOD_MUL( c[i] );
1447 }
1448
1449 /*
1450 * u = 1 / (Z_0 * ... * Z_n) mod P
1451 */
1452 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[T_size-1], &grp->P ) );
1453
1454 for( i = T_size - 1; ; i-- )
1455 {
1456 /*
1457 * Zi = 1 / Z_i mod p
1458 * u = 1 / (Z_0 * ... * Z_i) mod P
1459 */
1460 if( i == 0 ) {
1462 }
1463 else
1464 {
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 );
1467 }
1468
1469 /*
1470 * proceed as in normalize()
1471 */
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 );
1476
1477 /*
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.
1482 */
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 );
1486
1487 if( i == 0 )
1488 break;
1489 }
1490
1491cleanup:
1492
1494 for( i = 0; i < T_size; i++ )
1495 mbedtls_mpi_free( &c[i] );
1496 mbedtls_free( c );
1497
1498 return( ret );
1499}
1500
1501/*
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
1504 */
1505static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp,
1507 unsigned char inv )
1508{
1509 int ret;
1510 unsigned char nonzero;
1511 mbedtls_mpi mQY;
1512
1513 mbedtls_mpi_init( &mQY );
1514
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 ) );
1519
1520cleanup:
1521 mbedtls_mpi_free( &mQY );
1522
1523 return( ret );
1524}
1525
1526/*
1527 * Point doubling R = 2 P, Jacobian coordinates
1528 *
1529 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
1530 *
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.
1533 *
1534 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
1535 *
1536 * Cost: 1D := 3M + 4S (A == 0)
1537 * 4M + 4S (A == -3)
1538 * 3M + 6S + 1a otherwise
1539 */
1540static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1541 const mbedtls_ecp_point *P )
1542{
1543 int ret;
1544 mbedtls_mpi M, S, T, U;
1545
1546#if defined(MBEDTLS_SELF_TEST)
1547 dbl_count++;
1548#endif
1549
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 */
1554
1556
1557 /* Special case for A = -3 */
1558 if( grp->A.p == NULL )
1559 {
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 );
1566 }
1567 else
1568 {
1569 /* M = 3.X^2 */
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 );
1572
1573 /* Optimize away for "koblitz" curves with A = 0 */
1574 if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 )
1575 {
1576 /* M += A.Z^4 */
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 );
1581 }
1582 }
1583
1584 /* S = 4.X.Y^2 */
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 );
1589
1590 /* U = 8.Y^4 */
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 );
1593
1594 /* T = M^2 - 2.S */
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 );
1598
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 );
1603
1604 /* U = 2.Y.Z */
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 );
1607
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 ) );
1611
1612cleanup:
1614
1615 return( ret );
1616}
1617
1618/*
1619 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
1620 *
1621 * The coordinates of Q must be normalized (= affine),
1622 * but those of P don't need to. R is not normalized.
1623 *
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.
1631 *
1632 * We accept Q->Z being unset (saving memory in tables) as meaning 1.
1633 *
1634 * Cost: 1A := 8M + 3S
1635 */
1636static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1637 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
1638{
1639 int ret;
1640 mbedtls_mpi T1, T2, T3, T4, X, Y, Z;
1641
1642#if defined(MBEDTLS_SELF_TEST)
1643 add_count++;
1644#endif
1645
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 */
1650
1651 /*
1652 * Trivial cases: P == 0 or Q == 0 (case 1)
1653 */
1654 if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
1655 return( mbedtls_ecp_copy( R, Q ) );
1656
1657 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 )
1658 return( mbedtls_ecp_copy( R, P ) );
1659
1660 /*
1661 * Make sure Q coordinates are normalized
1662 */
1663 if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 )
1665
1668
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 );
1675
1676 /* Special cases (2) and (3) */
1677 if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 )
1678 {
1679 if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 )
1680 {
1681 ret = ecp_double_jac( grp, R, P );
1682 goto cleanup;
1683 }
1684 else
1685 {
1687 goto cleanup;
1688 }
1689 }
1690
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 );
1703
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 ) );
1707
1708cleanup:
1709
1712
1713 return( ret );
1714}
1715
1716/*
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().
1720 *
1721 * This countermeasure was first suggested in [2].
1722 */
1723static 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 )
1725{
1726 int ret;
1727 mbedtls_mpi l, ll;
1728 size_t p_size;
1729 int count = 0;
1730
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 */
1735
1736 p_size = ( grp->pbits + 7 ) / 8;
1738
1739 /* Generate l such that 1 < l < p */
1740 do
1741 {
1742 if( count++ > 30 )
1743 {
1745 goto cleanup;
1746 }
1747
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 ) );
1750 }
1751 while( ( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ) ||
1752 ( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) );
1753
1754 /* Z = l * Z */
1755 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z );
1756
1757 /* X = l^2 * X */
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 );
1760
1761 /* Y = l^3 * Y */
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 );
1764
1765cleanup:
1767
1768 return( ret );
1769}
1770
1771/*
1772 * Check and define parameters used by the comb method (see below for details)
1773 */
1774#if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7
1775#error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"
1776#endif
1777
1778/* d = ceil( n / w ) */
1779#define COMB_MAX_D ( MBEDTLS_ECP_MAX_BITS + 1 ) / 2
1780
1781/* number of precomputed points */
1782#define COMB_MAX_PRE ( 1 << ( MBEDTLS_ECP_WINDOW_SIZE - 1 ) )
1783
1784/*
1785 * Compute the representation of m that will be used with our comb method.
1786 *
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.
1793 *
1794 * Summary of the comb method and its modifications:
1795 *
1796 * - The goal is to compute m*P for some w*d-bit integer m.
1797 *
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.
1803 *
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].
1808 *
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.
1818 *
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
1822 * if s_i == -1;
1823 *
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)
1830 */
1831static void ecp_comb_recode_core( unsigned char x[], size_t d,
1832 unsigned char w, const mbedtls_mpi *m )
1833{
1834 size_t i, j;
1835 unsigned char c, cc, adjust;
1836
1837 memset( x, 0, d+1 );
1838
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;
1843
1844 /* Now make sure x_1 .. x_d are odd */
1845 c = 0;
1846 for( i = 1; i <= d; i++ )
1847 {
1848 /* Add carry and update it */
1849 cc = x[i] & c;
1850 x[i] = x[i] ^ c;
1851 c = cc;
1852
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;
1858 }
1859}
1860
1861/*
1862 * Precompute points for the adapted comb method
1863 *
1864 * Assumption: T must be able to hold 2^{w - 1} elements.
1865 *
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.
1868 *
1869 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
1870 *
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().
1874 *
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]
1880 *
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:
1884 *
1885 * step (2) (3) (4)
1886 * w = 5 142 165 208
1887 * w = 4 136 77 160
1888 * w = 3 130 33 136
1889 * w = 2 124 11 124
1890 *
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.
1894 */
1895static int ecp_precompute_comb( const mbedtls_ecp_group *grp,
1897 unsigned char w, size_t d,
1898 mbedtls_ecp_restart_ctx *rs_ctx )
1899{
1900 int ret;
1901 unsigned char i;
1902 size_t j = 0;
1903 const unsigned char T_size = 1U << ( w - 1 );
1904 mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1];
1905
1906#if defined(MBEDTLS_ECP_RESTARTABLE)
1907 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
1908 {
1909 if( rs_ctx->rsm->state == ecp_rsm_pre_dbl )
1910 goto dbl;
1911 if( rs_ctx->rsm->state == ecp_rsm_pre_norm_dbl )
1912 goto norm_dbl;
1913 if( rs_ctx->rsm->state == ecp_rsm_pre_add )
1914 goto add;
1915 if( rs_ctx->rsm->state == ecp_rsm_pre_norm_add )
1916 goto norm_add;
1917 }
1918#else
1919 (void) rs_ctx;
1920#endif
1921
1922#if defined(MBEDTLS_ECP_RESTARTABLE)
1923 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
1924 {
1925 rs_ctx->rsm->state = ecp_rsm_pre_dbl;
1926
1927 /* initial state for the loop */
1928 rs_ctx->rsm->i = 0;
1929 }
1930
1931dbl:
1932#endif
1933 /*
1934 * Set T[0] = P and
1935 * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
1936 */
1938
1939#if defined(MBEDTLS_ECP_RESTARTABLE)
1940 if( rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0 )
1941 j = rs_ctx->rsm->i;
1942 else
1943#endif
1944 j = 0;
1945
1946 for( ; j < d * ( w - 1 ); j++ )
1947 {
1948 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL );
1949
1950 i = 1U << ( j / d );
1951 cur = T + i;
1952
1953 if( j % d == 0 )
1954 MBEDTLS_MPI_CHK( mbedtls_ecp_copy( cur, T + ( i >> 1 ) ) );
1955
1956 MBEDTLS_MPI_CHK( ecp_double_jac( grp, cur, cur ) );
1957 }
1958
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;
1962
1963norm_dbl:
1964#endif
1965 /*
1966 * Normalize current elements in T. As T has holes,
1967 * use an auxiliary array of pointers to elements in T.
1968 */
1969 j = 0;
1970 for( i = 1; i < T_size; i <<= 1 )
1971 TT[j++] = T + i;
1972
1973 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 );
1974
1975 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) );
1976
1977#if defined(MBEDTLS_ECP_RESTARTABLE)
1978 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
1979 rs_ctx->rsm->state = ecp_rsm_pre_add;
1980
1981add:
1982#endif
1983 /*
1984 * Compute the remaining ones using the minimal number of additions
1985 * Be careful to update T[2^l] only after using it!
1986 */
1987 MBEDTLS_ECP_BUDGET( ( T_size - 1 ) * MBEDTLS_ECP_OPS_ADD );
1988
1989 for( i = 1; i < T_size; i <<= 1 )
1990 {
1991 j = i;
1992 while( j-- )
1993 MBEDTLS_MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
1994 }
1995
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;
1999
2000norm_add:
2001#endif
2002 /*
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.
2006 */
2007 for( j = 0; j + 1 < T_size; j++ )
2008 TT[j] = T + j + 1;
2009
2010 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV + 6 * j - 2 );
2011
2012 MBEDTLS_MPI_CHK( ecp_normalize_jac_many( grp, TT, j ) );
2013
2014cleanup:
2015#if defined(MBEDTLS_ECP_RESTARTABLE)
2016 if( rs_ctx != NULL && rs_ctx->rsm != NULL &&
2018 {
2019 if( rs_ctx->rsm->state == ecp_rsm_pre_dbl )
2020 rs_ctx->rsm->i = j;
2021 }
2022#endif
2023
2024 return( ret );
2025}
2026
2027/*
2028 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
2029 *
2030 * See ecp_comb_recode_core() for background
2031 */
2032static int ecp_select_comb( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2033 const mbedtls_ecp_point T[], unsigned char T_size,
2034 unsigned char i )
2035{
2036 int ret;
2037 unsigned char ii, j;
2038
2039 /* Ignore the "sign" bit and scale down */
2040 ii = ( i & 0x7Fu ) >> 1;
2041
2042 /* Read the whole table to thwart cache-based timing attacks */
2043 for( j = 0; j < T_size; j++ )
2044 {
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 ) );
2047 }
2048
2049 /* Safely invert result if i is "negative" */
2050 MBEDTLS_MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
2051
2052cleanup:
2053 return( ret );
2054}
2055
2056/*
2057 * Core multiplication algorithm for the (modified) comb method.
2058 * This part is actually common with the basic comb method (GECC 3.44)
2059 *
2060 * Cost: d A + d D + 1 R
2061 */
2062static 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),
2066 void *p_rng,
2067 mbedtls_ecp_restart_ctx *rs_ctx )
2068{
2069 int ret;
2071 size_t i;
2072
2073 mbedtls_ecp_point_init( &Txi );
2074
2075#if !defined(MBEDTLS_ECP_RESTARTABLE)
2076 (void) rs_ctx;
2077#endif
2078
2079#if defined(MBEDTLS_ECP_RESTARTABLE)
2080 if( rs_ctx != NULL && rs_ctx->rsm != NULL &&
2081 rs_ctx->rsm->state != ecp_rsm_comb_core )
2082 {
2083 rs_ctx->rsm->i = 0;
2084 rs_ctx->rsm->state = ecp_rsm_comb_core;
2085 }
2086
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 )
2089 {
2090 /* restore current index (R already pointing to rs_ctx->rsm->R) */
2091 i = rs_ctx->rsm->i;
2092 }
2093 else
2094#endif
2095 {
2096 /* Start with a non-zero point and randomize its coordinates */
2097 i = d;
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)
2101 if( f_rng != 0 )
2102#endif
2103 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
2104 }
2105
2106 while( i != 0 )
2107 {
2108 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD );
2109 --i;
2110
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 ) );
2114 }
2115
2116cleanup:
2117
2118 mbedtls_ecp_point_free( &Txi );
2119
2120#if defined(MBEDTLS_ECP_RESTARTABLE)
2121 if( rs_ctx != NULL && rs_ctx->rsm != NULL &&
2123 {
2124 rs_ctx->rsm->i = i;
2125 /* no need to save R, already pointing to rs_ctx->rsm->R */
2126 }
2127#endif
2128
2129 return( ret );
2130}
2131
2132/*
2133 * Recode the scalar to get constant-time comb multiplication
2134 *
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.
2138 *
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.
2141 *
2142 * See ecp_comb_recode_core() for background.
2143 */
2144static int ecp_comb_recode_scalar( const mbedtls_ecp_group *grp,
2145 const mbedtls_mpi *m,
2146 unsigned char k[COMB_MAX_D + 1],
2147 size_t d,
2148 unsigned char w,
2149 unsigned char *parity_trick )
2150{
2151 int ret;
2152 mbedtls_mpi M, mm;
2153
2154 mbedtls_mpi_init( &M );
2155 mbedtls_mpi_init( &mm );
2156
2157 /* N is always odd (see above), just make extra sure */
2158 if( mbedtls_mpi_get_bit( &grp->N, 0 ) != 1 )
2160
2161 /* do we need the parity trick? */
2162 *parity_trick = ( mbedtls_mpi_get_bit( m, 0 ) == 0 );
2163
2164 /* execute parity fix in constant time */
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 ) );
2168
2169 /* actual scalar recoding */
2170 ecp_comb_recode_core( k, d, w, &M );
2171
2172cleanup:
2173 mbedtls_mpi_free( &mm );
2174 mbedtls_mpi_free( &M );
2175
2176 return( ret );
2177}
2178
2179/*
2180 * Perform comb multiplication (for short Weierstrass curves)
2181 * once the auxiliary table has been pre-computed.
2182 *
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.
2185 */
2186static int ecp_mul_comb_after_precomp( const mbedtls_ecp_group *grp,
2188 const mbedtls_mpi *m,
2189 const mbedtls_ecp_point *T,
2190 unsigned char T_size,
2191 unsigned char w,
2192 size_t d,
2193 int (*f_rng)(void *, unsigned char *, size_t),
2194 void *p_rng,
2195 mbedtls_ecp_restart_ctx *rs_ctx )
2196{
2197 int ret;
2198 unsigned char parity_trick;
2199 unsigned char k[COMB_MAX_D + 1];
2200 mbedtls_ecp_point *RR = R;
2201
2202#if defined(MBEDTLS_ECP_RESTARTABLE)
2203 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
2204 {
2205 RR = &rs_ctx->rsm->R;
2206
2207 if( rs_ctx->rsm->state == ecp_rsm_final_norm )
2208 goto final_norm;
2209 }
2210#endif
2211
2212 MBEDTLS_MPI_CHK( ecp_comb_recode_scalar( grp, m, k, d, w,
2213 &parity_trick ) );
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 ) );
2217
2218#if defined(MBEDTLS_ECP_RESTARTABLE)
2219 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
2220 rs_ctx->rsm->state = ecp_rsm_final_norm;
2221
2222final_norm:
2223 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV );
2224#endif
2225 /*
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].
2230 *
2231 * [1] https://eprint.iacr.org/2003/191
2232 * [2] https://eprint.iacr.org/2020/055
2233 *
2234 * Avoid the leak by randomizing coordinates before we normalize them.
2235 */
2236#if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2237 if( f_rng != 0 )
2238#endif
2239 MBEDTLS_MPI_CHK( ecp_randomize_jac( grp, RR, f_rng, p_rng ) );
2240
2241 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, RR ) );
2242
2243#if defined(MBEDTLS_ECP_RESTARTABLE)
2244 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
2246#endif
2247
2248cleanup:
2249 return( ret );
2250}
2251
2252/*
2253 * Pick window size based on curve size and whether we optimize for base point
2254 */
2255static unsigned char ecp_pick_window_size( const mbedtls_ecp_group *grp,
2256 unsigned char p_eq_g )
2257{
2258 unsigned char w;
2259
2260 /*
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)
2264 */
2265 w = grp->nbits >= 384 ? 5 : 4;
2266
2267 /*
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.
2271 */
2272 if( p_eq_g )
2273 w++;
2274
2275 /*
2276 * Make sure w is within bounds.
2277 * (The last test is useful only for very small curves in the test suite.)
2278 */
2281 if( w >= grp->nbits )
2282 w = 2;
2283
2284 return( w );
2285}
2286
2287/*
2288 * Multiplication using the comb method - for curves in short Weierstrass form
2289 *
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.
2294 *
2295 * It delegates the actual arithmetic work to:
2296 * ecp_precompute_comb() and ecp_mul_comb_with_precomp()
2297 *
2298 * See comments on ecp_comb_recode_core() regarding the computation strategy.
2299 */
2300static 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),
2303 void *p_rng,
2304 mbedtls_ecp_restart_ctx *rs_ctx )
2305{
2306 int ret;
2307 unsigned char w, p_eq_g, i;
2308 size_t d;
2309 unsigned char T_size = 0, T_ok = 0;
2311#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2312 ecp_drbg_context drbg_ctx;
2313
2314 ecp_drbg_init( &drbg_ctx );
2315#endif
2316
2317 ECP_RS_ENTER( rsm );
2318
2319#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2320 if( f_rng == NULL )
2321 {
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;
2327 else
2328#endif
2329 p_rng = &drbg_ctx;
2330
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 )
2335#endif
2336 {
2337 const size_t m_len = ( grp->nbits + 7 ) / 8;
2338 MBEDTLS_MPI_CHK( ecp_drbg_seed( p_rng, m, m_len ) );
2339 }
2340#if defined(MBEDTLS_ECP_RESTARTABLE)
2341 if( rs_ctx != NULL && rs_ctx->rsm != NULL )
2342 rs_ctx->rsm->drbg_seeded = 1;
2343#endif
2344 }
2345#endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */
2346
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 );
2351#else
2352 p_eq_g = 0;
2353#endif
2354
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;
2359
2360 /* Pre-computed table: do we have it already for the base point? */
2361 if( p_eq_g && grp->T != NULL )
2362 {
2363 /* second pointer to the same table, will be deleted on exit */
2364 T = grp->T;
2365 T_ok = 1;
2366 }
2367 else
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 )
2371 {
2372 /* transfer ownership of T from rsm to local function */
2373 T = rs_ctx->rsm->T;
2374 rs_ctx->rsm->T = NULL;
2375 rs_ctx->rsm->T_size = 0;
2376
2377 /* This effectively jumps to the call to mul_comb_after_precomp() */
2378 T_ok = rs_ctx->rsm->state >= ecp_rsm_comb_core;
2379 }
2380 else
2381#endif
2382 /* Allocate table if we didn't have any */
2383 {
2384 T = mbedtls_calloc( T_size, sizeof( mbedtls_ecp_point ) );
2385 if( T == NULL )
2386 {
2388 goto cleanup;
2389 }
2390
2391 for( i = 0; i < T_size; i++ )
2393
2394 T_ok = 0;
2395 }
2396
2397 /* Compute table (or finish computing it) if not done already */
2398 if( !T_ok )
2399 {
2400 MBEDTLS_MPI_CHK( ecp_precompute_comb( grp, T, P, w, d, rs_ctx ) );
2401
2402 if( p_eq_g )
2403 {
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 */
2406 grp->T = T;
2407 grp->T_size = T_size;
2408 }
2409 }
2410
2411 /* Actual comb multiplication using precomputed points */
2412 MBEDTLS_MPI_CHK( ecp_mul_comb_after_precomp( grp, R, m,
2413 T, T_size, w, d,
2414 f_rng, p_rng, rs_ctx ) );
2415
2416cleanup:
2417
2418#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2419 ecp_drbg_free( &drbg_ctx );
2420#endif
2421
2422 /* does T belong to the group? */
2423 if( T == grp->T )
2424 T = NULL;
2425
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 )
2429 {
2430 /* transfer ownership of T from local function to rsm */
2431 rs_ctx->rsm->T_size = T_size;
2432 rs_ctx->rsm->T = T;
2433 T = NULL;
2434 }
2435#endif
2436
2437 /* did T belong to us? then let's destroy it! */
2438 if( T != NULL )
2439 {
2440 for( i = 0; i < T_size; i++ )
2442 mbedtls_free( T );
2443 }
2444
2445 /* don't free R while in progress in case R == P */
2446#if defined(MBEDTLS_ECP_RESTARTABLE)
2448#endif
2449 /* prevent caller from using invalid value */
2450 if( ret != 0 )
2452
2453 ECP_RS_LEAVE( rsm );
2454
2455 return( ret );
2456}
2457
2458#endif /* ECP_SHORTWEIERSTRASS */
2459
2460#if defined(ECP_MONTGOMERY)
2461/*
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.
2465 *
2466 * For scalar multiplication, we'll use a Montgomery ladder.
2467 */
2468
2469/*
2470 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
2471 * Cost: 1M + 1I
2472 */
2473static int ecp_normalize_mxz( const mbedtls_ecp_group *grp, mbedtls_ecp_point *P )
2474{
2475 int ret;
2476
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 */
2481
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 ) );
2485
2486cleanup:
2487 return( ret );
2488}
2489
2490/*
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().
2494 *
2495 * This countermeasure was first suggested in [2].
2496 * Cost: 2M
2497 */
2498static 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 )
2500{
2501 int ret;
2502 mbedtls_mpi l;
2503 size_t p_size;
2504 int count = 0;
2505
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 */
2510
2511 p_size = ( grp->pbits + 7 ) / 8;
2512 mbedtls_mpi_init( &l );
2513
2514 /* Generate l such that 1 < l < p */
2515 do
2516 {
2517 if( count++ > 30 )
2518 {
2520 goto cleanup;
2521 }
2522
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 ) );
2525 }
2526 while( ( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 ) ||
2527 ( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 ) );
2528
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 );
2531
2532cleanup:
2533 mbedtls_mpi_free( &l );
2534
2535 return( ret );
2536}
2537
2538/*
2539 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
2540 * for Montgomery curves in x/z coordinates.
2541 *
2542 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
2543 * with
2544 * d = X1
2545 * P = (X2, Z2)
2546 * Q = (X3, Z3)
2547 * R = (X4, Z4)
2548 * S = (X5, Z5)
2549 * and eliminating temporary variables tO, ..., t4.
2550 *
2551 * Cost: 5M + 4S
2552 */
2553static int ecp_double_add_mxz( const mbedtls_ecp_group *grp,
2555 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q,
2556 const mbedtls_mpi *d )
2557{
2558 int ret;
2559 mbedtls_mpi A, AA, B, BB, E, C, D, DA, CB;
2560
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 */
2565
2569
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 );
2588
2589cleanup:
2593
2594 return( ret );
2595}
2596
2597/*
2598 * Multiplication with Montgomery ladder in x/z coordinates,
2599 * for curves in Montgomery form
2600 */
2601static 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),
2604 void *p_rng )
2605{
2606 int ret;
2607 size_t i;
2608 unsigned char b;
2610 mbedtls_mpi PX;
2611#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2612 ecp_drbg_context drbg_ctx;
2613
2614 ecp_drbg_init( &drbg_ctx );
2615#endif
2617
2618#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2619 if( f_rng == NULL )
2620 {
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;
2624 p_rng = &drbg_ctx;
2625 }
2626#endif /* !MBEDTLS_ECP_NO_INTERNAL_RNG */
2627
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 ) );
2631
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 );
2636
2637 /* RP.X might be sligtly larger than P, so reduce it */
2638 MOD_ADD( RP.X );
2639
2640 /* Randomize coordinates of the starting point */
2641#if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2642 if( f_rng != NULL )
2643#endif
2644 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
2645
2646 /* Loop invariant: R = result so far, RP = R + P */
2647 i = mbedtls_mpi_bitlen( m ); /* one past the (zero-based) most significant bit */
2648 while( i-- > 0 )
2649 {
2650 b = mbedtls_mpi_get_bit( m, i );
2651 /*
2652 * if (b) R = 2R + P else R = 2R,
2653 * which is:
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
2657 */
2660 MBEDTLS_MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
2663 }
2664
2665 /*
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].
2670 *
2671 * [1] https://eprint.iacr.org/2003/191
2672 * [2] https://eprint.iacr.org/2020/055
2673 *
2674 * Avoid the leak by randomizing coordinates before we normalize them.
2675 */
2676#if defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2677 if( f_rng != NULL )
2678#endif
2679 MBEDTLS_MPI_CHK( ecp_randomize_mxz( grp, R, f_rng, p_rng ) );
2680
2681 MBEDTLS_MPI_CHK( ecp_normalize_mxz( grp, R ) );
2682
2683cleanup:
2684#if !defined(MBEDTLS_ECP_NO_INTERNAL_RNG)
2685 ecp_drbg_free( &drbg_ctx );
2686#endif
2687
2689
2690 return( ret );
2691}
2692
2693#endif /* ECP_MONTGOMERY */
2694
2695/*
2696 * Restartable multiplication R = m * P
2697 */
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 )
2702{
2704#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2705 char is_grp_capable = 0;
2706#endif
2707 ECP_VALIDATE_RET( grp != NULL );
2708 ECP_VALIDATE_RET( R != NULL );
2709 ECP_VALIDATE_RET( m != NULL );
2710 ECP_VALIDATE_RET( P != NULL );
2711
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;
2716#endif
2717
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 */
2722
2723#if defined(MBEDTLS_ECP_RESTARTABLE)
2724 /* skip argument check when restarting */
2725 if( rs_ctx == NULL || rs_ctx->rsm == NULL )
2726#endif
2727 {
2728 /* check_privkey is free */
2729 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_CHK );
2730
2731 /* Common sanity checks */
2734 }
2735
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 ) );
2740#endif
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 ) );
2744#endif
2745
2746cleanup:
2747
2748#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2749 if( is_grp_capable )
2750 mbedtls_internal_ecp_free( grp );
2751#endif /* MBEDTLS_ECP_INTERNAL_ALT */
2752
2753#if defined(MBEDTLS_ECP_RESTARTABLE)
2754 if( rs_ctx != NULL )
2755 rs_ctx->depth--;
2756#endif
2757
2758 return( ret );
2759}
2760
2761/*
2762 * Multiplication R = m * P
2763 */
2765 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2766 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
2767{
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 ) );
2773}
2774
2775#if defined(ECP_SHORTWEIERSTRASS)
2776/*
2777 * Check that an affine point is valid as a public key,
2778 * short weierstrass curves (SEC1 3.2.3.1)
2779 */
2780static int ecp_check_pubkey_sw( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
2781{
2782 int ret;
2783 mbedtls_mpi YY, RHS;
2784
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 )
2791
2793
2794 /*
2795 * YY = Y^2
2796 * RHS = X (X^2 + A) + B = X^3 + A X + B
2797 */
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 );
2800
2801 /* Special case for A = -3 */
2802 if( grp->A.p == NULL )
2803 {
2804 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS );
2805 }
2806 else
2807 {
2808 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS );
2809 }
2810
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 );
2813
2814 if( mbedtls_mpi_cmp_mpi( &YY, &RHS ) != 0 )
2816
2817cleanup:
2818
2820
2821 return( ret );
2822}
2823#endif /* ECP_SHORTWEIERSTRASS */
2824
2825/*
2826 * R = m * P with shortcuts for m == 1 and m == -1
2827 * NOT constant-time - ONLY for short Weierstrass!
2828 */
2829static int mbedtls_ecp_mul_shortcuts( mbedtls_ecp_group *grp,
2831 const mbedtls_mpi *m,
2832 const mbedtls_ecp_point *P,
2833 mbedtls_ecp_restart_ctx *rs_ctx )
2834{
2835 int ret;
2836
2837 if( mbedtls_mpi_cmp_int( m, 1 ) == 0 )
2838 {
2840 }
2841 else if( mbedtls_mpi_cmp_int( m, -1 ) == 0 )
2842 {
2844 if( mbedtls_mpi_cmp_int( &R->Y, 0 ) != 0 )
2845 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &R->Y, &grp->P, &R->Y ) );
2846 }
2847 else
2848 {
2850 NULL, NULL, rs_ctx ) );
2851 }
2852
2853cleanup:
2854 return( ret );
2855}
2856
2857/*
2858 * Restartable linear combination
2859 * NOT constant-time
2860 */
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 )
2866{
2867 int ret;
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;
2873#endif
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 );
2880
2881 if( ecp_get_type( grp ) != ECP_TYPE_SHORT_WEIERSTRASS )
2883
2885
2886 ECP_RS_ENTER( ma );
2887
2888#if defined(MBEDTLS_ECP_RESTARTABLE)
2889 if( rs_ctx != NULL && rs_ctx->ma != NULL )
2890 {
2891 /* redirect intermediate results to restart context */
2892 pmP = &rs_ctx->ma->mP;
2893 pR = &rs_ctx->ma->R;
2894
2895 /* jump to next operation */
2896 if( rs_ctx->ma->state == ecp_rsma_mul2 )
2897 goto mul2;
2898 if( rs_ctx->ma->state == ecp_rsma_add )
2899 goto add;
2900 if( rs_ctx->ma->state == ecp_rsma_norm )
2901 goto norm;
2902 }
2903#endif /* MBEDTLS_ECP_RESTARTABLE */
2904
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;
2909
2910mul2:
2911#endif
2912 MBEDTLS_MPI_CHK( mbedtls_ecp_mul_shortcuts( grp, pR, n, Q, rs_ctx ) );
2913
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 */
2918
2919#if defined(MBEDTLS_ECP_RESTARTABLE)
2920 if( rs_ctx != NULL && rs_ctx->ma != NULL )
2921 rs_ctx->ma->state = ecp_rsma_add;
2922
2923add:
2924#endif
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;
2930
2931norm:
2932#endif
2933 MBEDTLS_ECP_BUDGET( MBEDTLS_ECP_OPS_INV );
2934 MBEDTLS_MPI_CHK( ecp_normalize_jac( grp, pR ) );
2935
2936#if defined(MBEDTLS_ECP_RESTARTABLE)
2937 if( rs_ctx != NULL && rs_ctx->ma != NULL )
2939#endif
2940
2941cleanup:
2942#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2943 if( is_grp_capable )
2944 mbedtls_internal_ecp_free( grp );
2945#endif /* MBEDTLS_ECP_INTERNAL_ALT */
2946
2948
2949 ECP_RS_LEAVE( ma );
2950
2951 return( ret );
2952}
2953
2954/*
2955 * Linear combination
2956 * NOT constant-time
2957 */
2959 const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2960 const mbedtls_mpi *n, const mbedtls_ecp_point *Q )
2961{
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 ) );
2969}
2970
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)
2976/*
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().
2980 */
2981static 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 ),
2986};
2987static 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 ),
2992};
2993static const mbedtls_mpi ecp_x25519_bad_point_1 = ECP_MPI_INIT_ARRAY(
2994 x25519_bad_point_1 );
2995static const mbedtls_mpi ecp_x25519_bad_point_2 = ECP_MPI_INIT_ARRAY(
2996 x25519_bad_point_2 );
2997#endif /* MBEDTLS_ECP_DP_CURVE25519_ENABLED */
2998
2999/*
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.
3004 */
3005static int ecp_check_bad_points_mx( const mbedtls_mpi *X, const mbedtls_mpi *P,
3006 const mbedtls_ecp_group_id grp_id )
3007{
3008 int ret;
3009 mbedtls_mpi XmP;
3010
3011 mbedtls_mpi_init( &XmP );
3012
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. */
3016 while( mbedtls_mpi_cmp_mpi( &XmP, P ) >= 0 )
3017 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &XmP, &XmP, P ) );
3018
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 */
3023 {
3025 goto cleanup;
3026 }
3027
3028#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
3029 if( grp_id == MBEDTLS_ECP_DP_CURVE25519 )
3030 {
3031 if( mbedtls_mpi_cmp_mpi( &XmP, &ecp_x25519_bad_point_1 ) == 0 )
3032 {
3034 goto cleanup;
3035 }
3036
3037 if( mbedtls_mpi_cmp_mpi( &XmP, &ecp_x25519_bad_point_2 ) == 0 )
3038 {
3040 goto cleanup;
3041 }
3042 }
3043#else
3044 (void) grp_id;
3045#endif
3046
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 )
3050 {
3052 goto cleanup;
3053 }
3054
3055 ret = 0;
3056
3057cleanup:
3058 mbedtls_mpi_free( &XmP );
3059
3060 return( ret );
3061}
3062
3063/*
3064 * Check validity of a public key for Montgomery curves with x-only schemes
3065 */
3066static int ecp_check_pubkey_mx( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt )
3067{
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 )
3073
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 )
3079
3080 return( ecp_check_bad_points_mx( &pt->X, &grp->P, grp->id ) );
3081}
3082#endif /* ECP_MONTGOMERY */
3083
3084/*
3085 * Check that a point is valid as a public key
3086 */
3088 const mbedtls_ecp_point *pt )
3089{
3090 ECP_VALIDATE_RET( grp != NULL );
3091 ECP_VALIDATE_RET( pt != NULL );
3092
3093 /* Must use affine coordinates */
3094 if( mbedtls_mpi_cmp_int( &pt->Z, 1 ) != 0 )
3096
3097#if defined(ECP_MONTGOMERY)
3098 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
3099 return( ecp_check_pubkey_mx( grp, pt ) );
3100#endif
3101#if defined(ECP_SHORTWEIERSTRASS)
3102 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
3103 return( ecp_check_pubkey_sw( grp, pt ) );
3104#endif
3106}
3107
3108/*
3109 * Check that an mbedtls_mpi is valid as a private key
3110 */
3112 const mbedtls_mpi *d )
3113{
3114 ECP_VALIDATE_RET( grp != NULL );
3115 ECP_VALIDATE_RET( d != NULL );
3116
3117#if defined(ECP_MONTGOMERY)
3118 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
3119 {
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! */
3125
3126 /* see [Curve25519] page 5 */
3127 if( grp->nbits == 254 && mbedtls_mpi_get_bit( d, 2 ) != 0 )
3129
3130 return( 0 );
3131 }
3132#endif /* ECP_MONTGOMERY */
3133#if defined(ECP_SHORTWEIERSTRASS)
3134 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
3135 {
3136 /* see SEC1 3.2 */
3137 if( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
3138 mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 )
3140 else
3141 return( 0 );
3142 }
3143#endif /* ECP_SHORTWEIERSTRASS */
3144
3146}
3147
3148/*
3149 * Generate a private key
3150 */
3152 mbedtls_mpi *d,
3153 int (*f_rng)(void *, unsigned char *, size_t),
3154 void *p_rng )
3155{
3157 size_t n_size;
3158#if defined(ECP_SHORTWEIERSTRASS)
3160
3162#endif
3163
3164 ECP_VALIDATE_RET( grp != NULL );
3165 ECP_VALIDATE_RET( d != NULL );
3166 ECP_VALIDATE_RET( f_rng != NULL );
3167
3168 n_size = ( grp->nbits + 7 ) / 8;
3169
3170#if defined(ECP_MONTGOMERY)
3171 if( ecp_get_type( grp ) == ECP_TYPE_MONTGOMERY )
3172 {
3173 /* [M225] page 5 */
3174 size_t b;
3175
3176 do {
3177 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_size, f_rng, p_rng ) );
3178 } while( mbedtls_mpi_bitlen( d ) == 0);
3179
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 )
3184 else
3186
3187 /* Make sure the last two bits are unset for Curve448, three bits for
3188 Curve25519 */
3191 if( grp->nbits == 254 )
3192 {
3194 }
3195 }
3196#endif /* ECP_MONTGOMERY */
3197
3198#if defined(ECP_SHORTWEIERSTRASS)
3199 if( ecp_get_type( grp ) == ECP_TYPE_SHORT_WEIERSTRASS )
3200 {
3201 /* SEC1 3.2.1: Generate d such that 1 <= n < N */
3202 int count = 0;
3203 unsigned lt_lower = 1, lt_upper = 0;
3204
3205 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &one, grp->N.n ) );
3207
3208 /*
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.
3214 */
3215 do
3216 {
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 ) );
3219
3220 /*
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).
3224 *
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.
3228 */
3229 if( ++count > 30 )
3230 {
3232 goto cleanup;
3233 }
3234
3235 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( d, &grp->N, &lt_upper ) );
3236 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( d, &one, &lt_lower ) );
3237 }
3238 while( lt_lower != 0 || lt_upper == 0 );
3239 }
3240#endif /* ECP_SHORTWEIERSTRASS */
3241
3242cleanup:
3243#if defined(ECP_SHORTWEIERSTRASS)
3245#endif
3246 return( ret );
3247}
3248
3249/*
3250 * Generate a keypair with configurable base point
3251 */
3253 const mbedtls_ecp_point *G,
3255 int (*f_rng)(void *, unsigned char *, size_t),
3256 void *p_rng )
3257{
3258 int ret;
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 );
3264
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 ) );
3267
3268cleanup:
3269 return( ret );
3270}
3271
3272/*
3273 * Generate key pair, wrapper for conventional base point
3274 */
3277 int (*f_rng)(void *, unsigned char *, size_t),
3278 void *p_rng )
3279{
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 );
3284
3285 return( mbedtls_ecp_gen_keypair_base( grp, &grp->G, d, Q, f_rng, p_rng ) );
3286}
3287
3288/*
3289 * Generate a keypair, prettier wrapper
3290 */
3292 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
3293{
3294 int ret;
3295 ECP_VALIDATE_RET( key != NULL );
3296 ECP_VALIDATE_RET( f_rng != NULL );
3297
3298 if( ( ret = mbedtls_ecp_group_load( &key->grp, grp_id ) ) != 0 )
3299 return( ret );
3300
3301 return( mbedtls_ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) );
3302}
3303
3304/*
3305 * Check a public-private key pair
3306 */
3308{
3309 int ret;
3312 ECP_VALIDATE_RET( pub != NULL );
3313 ECP_VALIDATE_RET( prv != NULL );
3314
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 ) )
3320 {
3322 }
3323
3325 mbedtls_ecp_group_init( &grp );
3326
3327 /* mbedtls_ecp_mul() needs a non-const group... */
3328 mbedtls_ecp_group_copy( &grp, &prv->grp );
3329
3330 /* Also checks d is valid */
3331 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) );
3332
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 ) )
3336 {
3338 goto cleanup;
3339 }
3340
3341cleanup:
3343 mbedtls_ecp_group_free( &grp );
3344
3345 return( ret );
3346}
3347
3348#if defined(MBEDTLS_SELF_TEST)
3349
3350#if defined(ECP_ONE_STEP_KDF)
3351/*
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
3355 *
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).
3359 */
3360#if defined(MBEDTLS_SHA512_C)
3361
3362static 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,
3365};
3366static 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,
3372};
3373
3374#elif defined(MBEDTLS_SHA256_C)
3375
3376static 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,
3379};
3380static 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,
3386};
3387
3388#endif
3389
3390static int ecp_kdf_self_test( void )
3391{
3392 int ret;
3393 ecp_drbg_context kdf_ctx;
3394 mbedtls_mpi scalar;
3395 uint8_t out[sizeof( test_kdf_out )];
3396
3397 ecp_drbg_init( &kdf_ctx );
3398 mbedtls_mpi_init( &scalar );
3399 memset( out, 0, sizeof( out ) );
3400
3402 test_kdf_z, sizeof( test_kdf_z ) ) );
3403
3404 MBEDTLS_MPI_CHK( ecp_drbg_seed( &kdf_ctx,
3405 &scalar, sizeof( test_kdf_z ) ) );
3406
3407 MBEDTLS_MPI_CHK( ecp_drbg_random( &kdf_ctx, out, sizeof( out ) ) );
3408
3409 if( memcmp( out, test_kdf_out, sizeof( out ) ) != 0 )
3410 ret = -1;
3411
3412cleanup:
3413 ecp_drbg_free( &kdf_ctx );
3414 mbedtls_mpi_free( &scalar );
3415
3416 return( ret );
3417}
3418#endif /* ECP_ONE_STEP_KDF */
3419
3420/*
3421 * Checkup routine
3422 */
3423int mbedtls_ecp_self_test( int verbose )
3424{
3425 int ret;
3426 size_t i;
3429 mbedtls_mpi m;
3430 unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
3431 /* exponents especially adapted for secp192r1 */
3432 const char *exponents[] =
3433 {
3434 "000000000000000000000000000000000000000000000001", /* one */
3435 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */
3436 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
3437 "400000000000000000000000000000000000000000000000", /* one and zeros */
3438 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
3439 "555555555555555555555555555555555555555555555555", /* 101010... */
3440 };
3441
3442 mbedtls_ecp_group_init( &grp );
3445 mbedtls_mpi_init( &m );
3446
3447 /* Use secp192r1 if available, or any available curve */
3448#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
3450#else
3452#endif
3453
3454 if( verbose != 0 )
3455 mbedtls_printf( " ECP test #1 (constant op_count, base point G): " );
3456
3457 /* Do a dummy multiplication first to trigger precomputation */
3459 MBEDTLS_MPI_CHK( mbedtls_ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) );
3460
3461 add_count = 0;
3462 dbl_count = 0;
3463 mul_count = 0;
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 ) );
3466
3467 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
3468 {
3469 add_c_prev = add_count;
3470 dbl_c_prev = dbl_count;
3471 mul_c_prev = mul_count;
3472 add_count = 0;
3473 dbl_count = 0;
3474 mul_count = 0;
3475
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 ) );
3478
3479 if( add_count != add_c_prev ||
3480 dbl_count != dbl_c_prev ||
3481 mul_count != mul_c_prev )
3482 {
3483 if( verbose != 0 )
3484 mbedtls_printf( "failed (%u)\n", (unsigned int) i );
3485
3486 ret = 1;
3487 goto cleanup;
3488 }
3489 }
3490
3491 if( verbose != 0 )
3492 mbedtls_printf( "passed\n" );
3493
3494 if( verbose != 0 )
3495 mbedtls_printf( " ECP test #2 (constant op_count, other point): " );
3496 /* We computed P = 2G last time, use it */
3497
3498 add_count = 0;
3499 dbl_count = 0;
3500 mul_count = 0;
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 ) );
3503
3504 for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ )
3505 {
3506 add_c_prev = add_count;
3507 dbl_c_prev = dbl_count;
3508 mul_c_prev = mul_count;
3509 add_count = 0;
3510 dbl_count = 0;
3511 mul_count = 0;
3512
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 ) );
3515
3516 if( add_count != add_c_prev ||
3517 dbl_count != dbl_c_prev ||
3518 mul_count != mul_c_prev )
3519 {
3520 if( verbose != 0 )
3521 mbedtls_printf( "failed (%u)\n", (unsigned int) i );
3522
3523 ret = 1;
3524 goto cleanup;
3525 }
3526 }
3527
3528 if( verbose != 0 )
3529 mbedtls_printf( "passed\n" );
3530
3531#if defined(ECP_ONE_STEP_KDF)
3532 if( verbose != 0 )
3533 mbedtls_printf( " ECP test #3 (internal KDF): " );
3534
3535 ret = ecp_kdf_self_test();
3536 if( ret != 0 )
3537 {
3538 if( verbose != 0 )
3539 mbedtls_printf( "failed\n" );
3540
3541 ret = 1;
3542 goto cleanup;
3543 }
3544
3545 if( verbose != 0 )
3546 mbedtls_printf( "passed\n" );
3547#endif /* ECP_ONE_STEP_KDF */
3548
3549cleanup:
3550
3551 if( ret < 0 && verbose != 0 )
3552 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
3553
3554 mbedtls_ecp_group_free( &grp );
3557 mbedtls_mpi_free( &m );
3558
3559 if( verbose != 0 )
3560 mbedtls_printf( "\n" );
3561
3562 return( ret );
3563}
3564
3565#endif /* MBEDTLS_SELF_TEST */
3566
3567#endif /* !MBEDTLS_ECP_ALT */
3568
3569#endif /* MBEDTLS_ECP_C */
#define N
Definition: crc32.c:57
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
int strcmp(const char *String1, const char *String2)
Definition: utclib.c:469
int memcmp(void *Buffer1, void *Buffer2, ACPI_SIZE Count)
Definition: utclib.c:112
unsigned short int uint16_t
Definition: acefiex.h:54
static int state
Definition: maze.c:121
#define U(x)
Definition: wordpad.c:45
int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s)
Import an MPI from an ASCII string.
int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a signed subtraction of MPIs: X = A - B.
int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Perform a signed subtraction of an MPI and an integer: X = A - b.
int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Perform a signed addition of an MPI and an integer: X = A + b.
int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs)
Enlarge an MPI to the specified number of limbs.
int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y)
Make a copy of an MPI.
int mbedtls_mpi_set_bit(mbedtls_mpi *X, size_t pos, unsigned char val)
Modify a specific bit in an MPI.
size_t mbedtls_mpi_size(const mbedtls_mpi *X)
Return the total size of an MPI value in bytes.
int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a signed addition of MPIs: X = A + B.
int mbedtls_mpi_safe_cond_assign(mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign)
Perform a safe conditional copy of MPI which doesn't reveal whether the condition was true or not.
int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z)
Store integer value in MPI.
size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X)
Return the number of bits up to and including the most significant bit of value 1.
int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen)
Import an MPI from unsigned big endian binary data.
int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y)
Compare two MPIs.
int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a modular reduction. R = A mod B.
int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Fill an MPI with a number of random bytes.
int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count)
Perform a left-shift on an MPI: X <<= count.
int mbedtls_mpi_safe_cond_swap(mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char assign)
Perform a safe conditional swap which doesn't reveal whether the condition was true or not.
void mbedtls_mpi_init(mbedtls_mpi *X)
Initialize an MPI context.
int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform a multiplication of two MPIs: X = A * B.
#define MBEDTLS_MPI_CHK(f)
Definition: bignum.h:74
int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs)
This function resizes an MPI downwards, keeping at least the specified number of limbs.
int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N)
Compute the modular inverse: X = A^-1 mod N.
int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
Get a specific bit from an MPI.
void mbedtls_mpi_free(mbedtls_mpi *X)
This function frees the components of an MPI context.
int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b)
Perform a multiplication of an MPI with an unsigned integer: X = A * b.
int mbedtls_mpi_lt_mpi_ct(const mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned *ret)
Check if an MPI is less than the other in constant time.
int mbedtls_mpi_write_binary(const mbedtls_mpi *X, unsigned char *buf, size_t buflen)
Export an MPI into unsigned big endian binary data of fixed size.
int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z)
Compare an MPI with an integer.
int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Perform an unsigned subtraction of MPIs: X = |A| - |B|.
uint32_t mbedtls_mpi_uint
Definition: bignum.h:196
int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
Perform a right-shift on an MPI: X >>= count.
#define G(r, i, a, b, c, d)
Definition: blake2b-ref.c:117
Multi-precision integer library.
#define MBEDTLS_BYTES_TO_T_UINT_8(a, b, c, d, e, f, g, h)
Definition: bn_mul.h:90
#define D(d)
Definition: builtin.c:4557
#define C(c)
Definition: builtin.c:4556
w ll
Definition: byte_order.h:167
r l[0]
Definition: byte_order.h:168
Definition: ehthrow.cxx:93
Definition: ehthrow.cxx:54
Definition: terminate.cpp:24
This file contains definitions and functions for the CTR_DRBG pseudorandom generator.
#define NULL
Definition: types.h:112
#define Z(I)
#define Y(I)
#define P(row, col)
#define A(row, col)
#define B(row, col)
#define M(row, col)
static const WCHAR E[]
Definition: oid.c:1253
static void cleanup(void)
Definition: main.c:1335
unsigned char
Definition: typeof.h:29
#define pt(x, y)
Definition: drawing.c:79
This file provides an API for Elliptic Curves over GF(P) (ECP).
#define MBEDTLS_ERR_ECP_ALLOC_FAILED
Definition: ecp.h:79
void mbedtls_ecp_keypair_free(mbedtls_ecp_keypair *key)
This function frees the components of a key pair.
#define MBEDTLS_ECP_PF_UNCOMPRESSED
Definition: ecp.h:408
int mbedtls_ecp_point_read_binary(const mbedtls_ecp_group *grp, mbedtls_ecp_point *P, const unsigned char *buf, size_t ilen)
This function imports a point from unsigned binary data.
int mbedtls_ecp_muladd(mbedtls_ecp_group *grp, mbedtls_ecp_point *R, const mbedtls_mpi *m, const mbedtls_ecp_point *P, const mbedtls_mpi *n, const mbedtls_ecp_point *Q)
This function performs multiplication and addition of two points by integers: R = m * P + n * Q.
int mbedtls_ecp_gen_key(mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
This function generates an ECP key.
#define MBEDTLS_ECP_WINDOW_SIZE
Definition: ecp.h:301
#define MBEDTLS_ECP_BUDGET(ops)
Definition: ecp.h:382
int mbedtls_ecp_is_zero(mbedtls_ecp_point *pt)
This function checks if a point is the point at infinity.
#define MBEDTLS_ERR_ECP_INVALID_KEY
Definition: ecp.h:81
int mbedtls_ecp_tls_write_group(const mbedtls_ecp_group *grp, size_t *olen, unsigned char *buf, size_t blen)
This function exports an elliptic curve as a TLS ECParameters record as defined in RFC 4492,...
int mbedtls_ecp_group_copy(mbedtls_ecp_group *dst, const mbedtls_ecp_group *src)
This function copies the contents of group src into group dst.
#define MBEDTLS_ECP_PF_COMPRESSED
Definition: ecp.h:409
#define MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL
Definition: ecp.h:76
#define MBEDTLS_ERR_ECP_RANDOM_FAILED
Definition: ecp.h:80
int mbedtls_ecp_mul(mbedtls_ecp_group *grp, mbedtls_ecp_point *R, const mbedtls_mpi *m, const mbedtls_ecp_point *P, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
This function performs a scalar multiplication of a point by an integer: R = m * P.
const mbedtls_ecp_group_id * mbedtls_ecp_grp_id_list(void)
This function retrieves the list of internal group identifiers of all supported curves in the order o...
void mbedtls_ecp_group_init(mbedtls_ecp_group *grp)
This function initializes an ECP group context without loading any domain parameters.
int mbedtls_ecp_gen_keypair_base(mbedtls_ecp_group *grp, const mbedtls_ecp_point *G, mbedtls_mpi *d, mbedtls_ecp_point *Q, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
This function generates a keypair with a configurable base point.
int mbedtls_ecp_check_pub_priv(const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv)
This function checks that the keypair objects pub and prv have the same group and the same public poi...
#define MBEDTLS_ECP_TLS_NAMED_CURVE
Definition: ecp.h:414
int mbedtls_ecp_mul_restartable(mbedtls_ecp_group *grp, mbedtls_ecp_point *R, const mbedtls_mpi *m, const mbedtls_ecp_point *P, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng, mbedtls_ecp_restart_ctx *rs_ctx)
This function performs multiplication of a point by an integer: R = m * P in a restartable way.
int mbedtls_ecp_point_cmp(const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q)
This function compares two points.
int mbedtls_ecp_check_privkey(const mbedtls_ecp_group *grp, const mbedtls_mpi *d)
This function checks that an mbedtls_mpi is a valid private key for this curve.
int mbedtls_ecp_point_read_string(mbedtls_ecp_point *P, int radix, const char *x, const char *y)
This function imports a non-zero point from two ASCII strings.
int mbedtls_ecp_group_load(mbedtls_ecp_group *grp, mbedtls_ecp_group_id id)
This function sets up an ECP group context from a standardized set of domain parameters.
#define MBEDTLS_ERR_ECP_IN_PROGRESS
Definition: ecp.h:87
void mbedtls_ecp_keypair_init(mbedtls_ecp_keypair *key)
This function initializes a key pair as an invalid one.
int mbedtls_ecp_tls_read_group_id(mbedtls_ecp_group_id *grp, const unsigned char **buf, size_t len)
This function extracts an elliptic curve group ID from a TLS ECParameters record as defined in RFC 44...
const mbedtls_ecp_curve_info * mbedtls_ecp_curve_info_from_name(const char *name)
This function retrieves curve information from a human-readable name.
void mbedtls_ecp_point_free(mbedtls_ecp_point *pt)
This function frees the components of a point.
int mbedtls_ecp_tls_read_point(const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, const unsigned char **buf, size_t len)
This function imports a point from a TLS ECPoint record.
void mbedtls_ecp_group_free(mbedtls_ecp_group *grp)
This function frees the components of an ECP group.
int mbedtls_ecp_copy(mbedtls_ecp_point *P, const mbedtls_ecp_point *Q)
This function copies the contents of point Q into point P.
int mbedtls_ecp_muladd_restartable(mbedtls_ecp_group *grp, mbedtls_ecp_point *R, const mbedtls_mpi *m, const mbedtls_ecp_point *P, const mbedtls_mpi *n, const mbedtls_ecp_point *Q, mbedtls_ecp_restart_ctx *rs_ctx)
This function performs multiplication and addition of two points by integers: R = m * P + n * Q in a ...
int mbedtls_ecp_gen_privkey(const mbedtls_ecp_group *grp, mbedtls_mpi *d, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
This function generates a private key.
#define MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE
Definition: ecp.h:77
int mbedtls_ecp_gen_keypair(mbedtls_ecp_group *grp, mbedtls_mpi *d, mbedtls_ecp_point *Q, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
This function generates an ECP keypair.
int mbedtls_ecp_tls_write_point(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt, int format, size_t *olen, unsigned char *buf, size_t blen)
This function exports a point as a TLS ECPoint record defined in RFC 4492, Section 5....
const mbedtls_ecp_curve_info * mbedtls_ecp_curve_info_from_grp_id(mbedtls_ecp_group_id grp_id)
This function retrieves curve information from an internal group identifier.
#define MBEDTLS_ECP_MAX_BYTES
Definition: ecp.h:278
#define MBEDTLS_ERR_ECP_BAD_INPUT_DATA
Definition: ecp.h:75
int mbedtls_ecp_set_zero(mbedtls_ecp_point *pt)
This function sets a point to the point at infinity.
int mbedtls_ecp_tls_read_group(mbedtls_ecp_group *grp, const unsigned char **buf, size_t len)
This function sets up an ECP group context from a TLS ECParameters record as defined in RFC 4492,...
const mbedtls_ecp_curve_info * mbedtls_ecp_curve_list(void)
This function retrieves the information defined in mbedtls_ecp_curve_info() for all supported curves ...
void mbedtls_ecp_point_init(mbedtls_ecp_point *pt)
This function initializes a point as zero.
int mbedtls_ecp_check_pubkey(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt)
This function checks that a point is a valid public key on this curve.
mbedtls_ecp_group_id
Definition: ecp.h:103
@ MBEDTLS_ECP_DP_SECP192K1
Definition: ecp.h:114
@ MBEDTLS_ECP_DP_SECP384R1
Definition: ecp.h:108
@ MBEDTLS_ECP_DP_CURVE25519
Definition: ecp.h:113
@ MBEDTLS_ECP_DP_NONE
Definition: ecp.h:104
@ MBEDTLS_ECP_DP_SECP256K1
Definition: ecp.h:116
@ MBEDTLS_ECP_DP_BP512R1
Definition: ecp.h:112
@ MBEDTLS_ECP_DP_SECP224R1
Definition: ecp.h:106
@ MBEDTLS_ECP_DP_SECP521R1
Definition: ecp.h:109
@ MBEDTLS_ECP_DP_BP384R1
Definition: ecp.h:111
@ MBEDTLS_ECP_DP_SECP224K1
Definition: ecp.h:115
@ MBEDTLS_ECP_DP_BP256R1
Definition: ecp.h:110
@ MBEDTLS_ECP_DP_SECP192R1
Definition: ecp.h:105
@ MBEDTLS_ECP_DP_SECP256R1
Definition: ecp.h:107
int mbedtls_ecp_point_write_binary(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *P, int format, size_t *olen, unsigned char *buf, size_t buflen)
This function exports a point into unsigned binary data.
const mbedtls_ecp_curve_info * mbedtls_ecp_curve_info_from_tls_id(uint16_t tls_id)
This function retrieves curve information from a TLS NamedCurve value.
Function declarations for alternative implementation of elliptic curve point arithmetic.
FxCollectionEntry * cur
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLint GLint GLsizei GLsizei GLsizei GLint GLenum format
Definition: gl.h:1546
GLdouble n
Definition: glext.h:7729
GLenum src
Definition: glext.h:6340
const GLubyte * c
Definition: glext.h:8905
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
GLenum GLenum dst
Definition: glext.h:6340
GLenum GLsizei len
Definition: glext.h:6722
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
const GLfloat * m
Definition: glext.h:10848
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
#define X(b, s)
The HMAC_DRBG pseudorandom generator.
void mbedtls_hmac_drbg_init(mbedtls_hmac_drbg_context *ctx)
HMAC_DRBG context initialization.
void mbedtls_hmac_drbg_free(mbedtls_hmac_drbg_context *ctx)
This function resets HMAC_DRBG context to the state immediately after initial call of mbedtls_hmac_dr...
int mbedtls_hmac_drbg_seed_buf(mbedtls_hmac_drbg_context *ctx, const mbedtls_md_info_t *md_info, const unsigned char *data, size_t data_len)
Initilisation of simpified HMAC_DRBG (never reseeds).
int mbedtls_hmac_drbg_random(void *p_rng, unsigned char *output, size_t out_len)
This function uses HMAC_DRBG to generate random data.
uint32_t cc
Definition: isohybrid.c:75
#define d
Definition: ke_i.h:81
#define c
Definition: ke_i.h:80
#define b
Definition: ke_i.h:79
#define T
Definition: mbstring.h:31
#define AA(_h, _w, _x, _y, _z)
const int * mbedtls_md_list(void)
This function returns the list of digests supported by the generic digest module.
mbedtls_md_type_t
Supported message digests.
Definition: md.h:83
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
static DATA_BLOB CRYPTPROTECT_PROMPTSTRUCT DATA_BLOB *static LPWSTR DATA_BLOB CRYPTPROTECT_PROMPTSTRUCT DATA_BLOB *static char secret[]
Definition: protectdata.c:33
int k
Definition: mpi.c:3369
BYTE uint8_t
Definition: msvideo1.c:66
void mbedtls_platform_zeroize(void *buf, size_t len)
Securely zeroize a buffer.
Definition: platform_util.c:98
Common and shared functions used by multiple modules in the Mbed TLS library.
static FILE * out
Definition: regtests2xml.c:44
#define verbose
Definition: rosglue.h:36
#define mbedtls_md_info_from_type
#define mbedtls_ctr_drbg_seed
#define mbedtls_ctr_drbg_random
#define mbedtls_ctr_drbg_init
#define mbedtls_ctr_drbg_free
Configuration options (set of defines)
This file contains the definitions and functions of the Mbed TLS platform abstraction layer.
#define mbedtls_free
Definition: platform.h:168
#define mbedtls_calloc
Definition: platform.h:169
#define S(x)
Definition: test.h:220
#define memset(x, y, z)
Definition: compat.h:39
int one
Definition: sehframes.cpp:28
This file contains SHA-224 and SHA-256 definitions and functions.
#define R(b, x)
Definition: sha2.c:134
This file contains SHA-384 and SHA-512 definitions and functions.
Definition: movable.cpp:9
Definition: DrawText.c:11
Definition: copy.c:22
The CTR_DRBG context structure.
Definition: ctr_drbg.h:195
const char * name
Definition: ecp.h:135
mbedtls_ecp_group_id grp_id
Definition: ecp.h:132
uint16_t tls_id
Definition: ecp.h:133
The ECP group structure.
Definition: ecp.h:233
size_t pbits
Definition: ecp.h:242
int(* t_pre)(mbedtls_ecp_point *, void *)
Definition: ecp.h:249
unsigned int h
Definition: ecp.h:246
mbedtls_ecp_group_id id
Definition: ecp.h:234
size_t T_size
Definition: ecp.h:253
mbedtls_ecp_point * T
Definition: ecp.h:252
mbedtls_mpi N
Definition: ecp.h:241
void * t_data
Definition: ecp.h:251
mbedtls_ecp_point G
Definition: ecp.h:240
int(* t_post)(mbedtls_ecp_point *, void *)
Definition: ecp.h:250
mbedtls_mpi B
Definition: ecp.h:238
int(* modp)(mbedtls_mpi *)
Definition: ecp.h:247
mbedtls_mpi P
Definition: ecp.h:235
size_t nbits
Definition: ecp.h:243
mbedtls_mpi A
Definition: ecp.h:236
The ECP key-pair structure.
Definition: ecp.h:398
mbedtls_ecp_point Q
Definition: ecp.h:401
mbedtls_mpi d
Definition: ecp.h:400
mbedtls_ecp_group grp
Definition: ecp.h:399
The ECP point structure, in Jacobian coordinates.
Definition: ecp.h:150
mbedtls_mpi Z
Definition: ecp.h:153
mbedtls_mpi X
Definition: ecp.h:151
mbedtls_mpi Y
Definition: ecp.h:152
MPI structure.
Definition: bignum.h:211
size_t n
Definition: bignum.h:213
mbedtls_mpi_uint * p
Definition: bignum.h:214
Definition: name.c:39
Threading abstraction layer.
#define mbedtls_printf
Definition: timing.c:57
int ret