Coverage Report

Created: 2024-11-21 07:03

/src/mbedtls/library/ecp.c
Line
Count
Source (jump to first uncovered line)
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
8
/*
9
 * References:
10
 *
11
 * SEC1 https://www.secg.org/sec1-v2.pdf
12
 * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
13
 * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
14
 * RFC 4492 for the related TLS structures and constants
15
 * - https://www.rfc-editor.org/rfc/rfc4492
16
 * RFC 7748 for the Curve448 and Curve25519 curve definitions
17
 * - https://www.rfc-editor.org/rfc/rfc7748
18
 *
19
 * [Curve25519] https://cr.yp.to/ecdh/curve25519-20060209.pdf
20
 *
21
 * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
22
 *     for elliptic curve cryptosystems. In : Cryptographic Hardware and
23
 *     Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
24
 *     <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
25
 *
26
 * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
27
 *     render ECC resistant against Side Channel Attacks. IACR Cryptology
28
 *     ePrint Archive, 2004, vol. 2004, p. 342.
29
 *     <http://eprint.iacr.org/2004/342.pdf>
30
 */
31
32
#include "common.h"
33
34
/**
35
 * \brief Function level alternative implementation.
36
 *
37
 * The MBEDTLS_ECP_INTERNAL_ALT macro enables alternative implementations to
38
 * replace certain functions in this module. The alternative implementations are
39
 * typically hardware accelerators and need to activate the hardware before the
40
 * computation starts and deactivate it after it finishes. The
41
 * mbedtls_internal_ecp_init() and mbedtls_internal_ecp_free() functions serve
42
 * this purpose.
43
 *
44
 * To preserve the correct functionality the following conditions must hold:
45
 *
46
 * - The alternative implementation must be activated by
47
 *   mbedtls_internal_ecp_init() before any of the replaceable functions is
48
 *   called.
49
 * - mbedtls_internal_ecp_free() must \b only be called when the alternative
50
 *   implementation is activated.
51
 * - mbedtls_internal_ecp_init() must \b not be called when the alternative
52
 *   implementation is activated.
53
 * - Public functions must not return while the alternative implementation is
54
 *   activated.
55
 * - Replaceable functions are guarded by \c MBEDTLS_ECP_XXX_ALT macros and
56
 *   before calling them an \code if( mbedtls_internal_ecp_grp_capable( grp ) )
57
 *   \endcode ensures that the alternative implementation supports the current
58
 *   group.
59
 */
60
#if defined(MBEDTLS_ECP_INTERNAL_ALT)
61
#endif
62
63
#if defined(MBEDTLS_ECP_LIGHT)
64
65
#include "mbedtls/ecp.h"
66
#include "mbedtls/threading.h"
67
#include "mbedtls/platform_util.h"
68
#include "mbedtls/error.h"
69
70
#include "bn_mul.h"
71
#include "ecp_invasive.h"
72
73
#include <string.h>
74
75
#if !defined(MBEDTLS_ECP_ALT)
76
77
#include "mbedtls/platform.h"
78
79
#include "ecp_internal_alt.h"
80
81
#if defined(MBEDTLS_SELF_TEST)
82
/*
83
 * Counts of point addition and doubling, and field multiplications.
84
 * Used to test resistance of point multiplication to simple timing attacks.
85
 */
86
#if defined(MBEDTLS_ECP_C)
87
static unsigned long add_count, dbl_count;
88
#endif /* MBEDTLS_ECP_C */
89
static unsigned long mul_count;
90
#endif
91
92
#if defined(MBEDTLS_ECP_RESTARTABLE)
93
/*
94
 * Maximum number of "basic operations" to be done in a row.
95
 *
96
 * Default value 0 means that ECC operations will not yield.
97
 * Note that regardless of the value of ecp_max_ops, always at
98
 * least one step is performed before yielding.
99
 *
100
 * Setting ecp_max_ops=1 can be suitable for testing purposes
101
 * as it will interrupt computation at all possible points.
102
 */
103
static unsigned ecp_max_ops = 0;
104
105
/*
106
 * Set ecp_max_ops
107
 */
108
void mbedtls_ecp_set_max_ops(unsigned max_ops)
109
{
110
    ecp_max_ops = max_ops;
111
}
112
113
/*
114
 * Check if restart is enabled
115
 */
116
int mbedtls_ecp_restart_is_enabled(void)
117
{
118
    return ecp_max_ops != 0;
119
}
120
121
/*
122
 * Restart sub-context for ecp_mul_comb()
123
 */
124
struct mbedtls_ecp_restart_mul {
125
    mbedtls_ecp_point R;    /* current intermediate result                  */
126
    size_t i;               /* current index in various loops, 0 outside    */
127
    mbedtls_ecp_point *T;   /* table for precomputed points                 */
128
    unsigned char T_size;   /* number of points in table T                  */
129
    enum {                  /* what were we doing last time we returned?    */
130
        ecp_rsm_init = 0,       /* nothing so far, dummy initial state      */
131
        ecp_rsm_pre_dbl,        /* precompute 2^n multiples                 */
132
        ecp_rsm_pre_norm_dbl,   /* normalize precomputed 2^n multiples      */
133
        ecp_rsm_pre_add,        /* precompute remaining points by adding    */
134
        ecp_rsm_pre_norm_add,   /* normalize all precomputed points         */
135
        ecp_rsm_comb_core,      /* ecp_mul_comb_core()                      */
136
        ecp_rsm_final_norm,     /* do the final normalization               */
137
    } state;
138
};
139
140
/*
141
 * Init restart_mul sub-context
142
 */
143
static void ecp_restart_rsm_init(mbedtls_ecp_restart_mul_ctx *ctx)
144
{
145
    mbedtls_ecp_point_init(&ctx->R);
146
    ctx->i = 0;
147
    ctx->T = NULL;
148
    ctx->T_size = 0;
149
    ctx->state = ecp_rsm_init;
150
}
151
152
/*
153
 * Free the components of a restart_mul sub-context
154
 */
155
static void ecp_restart_rsm_free(mbedtls_ecp_restart_mul_ctx *ctx)
156
{
157
    unsigned char i;
158
159
    if (ctx == NULL) {
160
        return;
161
    }
162
163
    mbedtls_ecp_point_free(&ctx->R);
164
165
    if (ctx->T != NULL) {
166
        for (i = 0; i < ctx->T_size; i++) {
167
            mbedtls_ecp_point_free(ctx->T + i);
168
        }
169
        mbedtls_free(ctx->T);
170
    }
171
172
    ecp_restart_rsm_init(ctx);
173
}
174
175
/*
176
 * Restart context for ecp_muladd()
177
 */
178
struct mbedtls_ecp_restart_muladd {
179
    mbedtls_ecp_point mP;       /* mP value                             */
180
    mbedtls_ecp_point R;        /* R intermediate result                */
181
    enum {                      /* what should we do next?              */
182
        ecp_rsma_mul1 = 0,      /* first multiplication                 */
183
        ecp_rsma_mul2,          /* second multiplication                */
184
        ecp_rsma_add,           /* addition                             */
185
        ecp_rsma_norm,          /* normalization                        */
186
    } state;
187
};
188
189
/*
190
 * Init restart_muladd sub-context
191
 */
192
static void ecp_restart_ma_init(mbedtls_ecp_restart_muladd_ctx *ctx)
193
{
194
    mbedtls_ecp_point_init(&ctx->mP);
195
    mbedtls_ecp_point_init(&ctx->R);
196
    ctx->state = ecp_rsma_mul1;
197
}
198
199
/*
200
 * Free the components of a restart_muladd sub-context
201
 */
202
static void ecp_restart_ma_free(mbedtls_ecp_restart_muladd_ctx *ctx)
203
{
204
    if (ctx == NULL) {
205
        return;
206
    }
207
208
    mbedtls_ecp_point_free(&ctx->mP);
209
    mbedtls_ecp_point_free(&ctx->R);
210
211
    ecp_restart_ma_init(ctx);
212
}
213
214
/*
215
 * Initialize a restart context
216
 */
217
void mbedtls_ecp_restart_init(mbedtls_ecp_restart_ctx *ctx)
218
{
219
    ctx->ops_done = 0;
220
    ctx->depth = 0;
221
    ctx->rsm = NULL;
222
    ctx->ma = NULL;
223
}
224
225
/*
226
 * Free the components of a restart context
227
 */
228
void mbedtls_ecp_restart_free(mbedtls_ecp_restart_ctx *ctx)
229
{
230
    if (ctx == NULL) {
231
        return;
232
    }
233
234
    ecp_restart_rsm_free(ctx->rsm);
235
    mbedtls_free(ctx->rsm);
236
237
    ecp_restart_ma_free(ctx->ma);
238
    mbedtls_free(ctx->ma);
239
240
    mbedtls_ecp_restart_init(ctx);
241
}
242
243
/*
244
 * Check if we can do the next step
245
 */
246
int mbedtls_ecp_check_budget(const mbedtls_ecp_group *grp,
247
                             mbedtls_ecp_restart_ctx *rs_ctx,
248
                             unsigned ops)
249
{
250
    if (rs_ctx != NULL && ecp_max_ops != 0) {
251
        /* scale depending on curve size: the chosen reference is 256-bit,
252
         * and multiplication is quadratic. Round to the closest integer. */
253
        if (grp->pbits >= 512) {
254
            ops *= 4;
255
        } else if (grp->pbits >= 384) {
256
            ops *= 2;
257
        }
258
259
        /* Avoid infinite loops: always allow first step.
260
         * Because of that, however, it's not generally true
261
         * that ops_done <= ecp_max_ops, so the check
262
         * ops_done > ecp_max_ops below is mandatory. */
263
        if ((rs_ctx->ops_done != 0) &&
264
            (rs_ctx->ops_done > ecp_max_ops ||
265
             ops > ecp_max_ops - rs_ctx->ops_done)) {
266
            return MBEDTLS_ERR_ECP_IN_PROGRESS;
267
        }
268
269
        /* update running count */
270
        rs_ctx->ops_done += ops;
271
    }
272
273
    return 0;
274
}
275
276
/* Call this when entering a function that needs its own sub-context */
277
#define ECP_RS_ENTER(SUB)   do {                                      \
278
        /* reset ops count for this call if top-level */                    \
279
        if (rs_ctx != NULL && rs_ctx->depth++ == 0)                        \
280
        rs_ctx->ops_done = 0;                                           \
281
                                                                        \
282
        /* set up our own sub-context if needed */                          \
283
        if (mbedtls_ecp_restart_is_enabled() &&                             \
284
            rs_ctx != NULL && rs_ctx->SUB == NULL)                         \
285
        {                                                                   \
286
            rs_ctx->SUB = mbedtls_calloc(1, sizeof(*rs_ctx->SUB));      \
287
            if (rs_ctx->SUB == NULL)                                       \
288
            return MBEDTLS_ERR_ECP_ALLOC_FAILED;                     \
289
                                                                      \
290
            ecp_restart_## SUB ##_init(rs_ctx->SUB);                      \
291
        }                                                                   \
292
} while (0)
293
294
/* Call this when leaving a function that needs its own sub-context */
295
#define ECP_RS_LEAVE(SUB)   do {                                      \
296
        /* clear our sub-context when not in progress (done or error) */    \
297
        if (rs_ctx != NULL && rs_ctx->SUB != NULL &&                        \
298
            ret != MBEDTLS_ERR_ECP_IN_PROGRESS)                            \
299
        {                                                                   \
300
            ecp_restart_## SUB ##_free(rs_ctx->SUB);                      \
301
            mbedtls_free(rs_ctx->SUB);                                    \
302
            rs_ctx->SUB = NULL;                                             \
303
        }                                                                   \
304
                                                                        \
305
        if (rs_ctx != NULL)                                                \
306
        rs_ctx->depth--;                                                \
307
} while (0)
308
309
#else /* MBEDTLS_ECP_RESTARTABLE */
310
311
2.63k
#define ECP_RS_ENTER(sub)     (void) rs_ctx;
312
2.63k
#define ECP_RS_LEAVE(sub)     (void) rs_ctx;
313
314
#endif /* MBEDTLS_ECP_RESTARTABLE */
315
316
#if defined(MBEDTLS_ECP_C)
317
static void mpi_init_many(mbedtls_mpi *arr, size_t size)
318
4.17k
{
319
21.8k
    while (size--) {
320
17.7k
        mbedtls_mpi_init(arr++);
321
17.7k
    }
322
4.17k
}
323
324
static void mpi_free_many(mbedtls_mpi *arr, size_t size)
325
4.17k
{
326
21.8k
    while (size--) {
327
17.7k
        mbedtls_mpi_free(arr++);
328
17.7k
    }
329
4.17k
}
330
#endif /* MBEDTLS_ECP_C */
331
332
/*
333
 * List of supported curves:
334
 *  - internal ID
335
 *  - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2, RFC 8446 sec. 4.2.7)
336
 *  - size in bits
337
 *  - readable name
338
 *
339
 * Curves are listed in order: largest curves first, and for a given size,
340
 * fastest curves first.
341
 *
342
 * Reminder: update profiles in x509_crt.c and ssl_tls.c when adding a new curve!
343
 */
344
static const mbedtls_ecp_curve_info ecp_supported_curves[] =
345
{
346
#if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
347
    { MBEDTLS_ECP_DP_SECP521R1,    25,     521,    "secp521r1"         },
348
#endif
349
#if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
350
    { MBEDTLS_ECP_DP_BP512R1,      28,     512,    "brainpoolP512r1"   },
351
#endif
352
#if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
353
    { MBEDTLS_ECP_DP_SECP384R1,    24,     384,    "secp384r1"         },
354
#endif
355
#if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
356
    { MBEDTLS_ECP_DP_BP384R1,      27,     384,    "brainpoolP384r1"   },
357
#endif
358
#if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
359
    { MBEDTLS_ECP_DP_SECP256R1,    23,     256,    "secp256r1"         },
360
#endif
361
#if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
362
    { MBEDTLS_ECP_DP_SECP256K1,    22,     256,    "secp256k1"         },
363
#endif
364
#if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
365
    { MBEDTLS_ECP_DP_BP256R1,      26,     256,    "brainpoolP256r1"   },
366
#endif
367
#if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
368
    { MBEDTLS_ECP_DP_SECP224R1,    21,     224,    "secp224r1"         },
369
#endif
370
#if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
371
    { MBEDTLS_ECP_DP_SECP224K1,    20,     224,    "secp224k1"         },
372
#endif
373
#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
374
    { MBEDTLS_ECP_DP_SECP192R1,    19,     192,    "secp192r1"         },
375
#endif
376
#if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
377
    { MBEDTLS_ECP_DP_SECP192K1,    18,     192,    "secp192k1"         },
378
#endif
379
#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
380
    { MBEDTLS_ECP_DP_CURVE25519,   29,     256,    "x25519"            },
381
#endif
382
#if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
383
    { MBEDTLS_ECP_DP_CURVE448,     30,     448,    "x448"              },
384
#endif
385
    { MBEDTLS_ECP_DP_NONE,          0,     0,      NULL                },
386
};
387
388
#define ECP_NB_CURVES   sizeof(ecp_supported_curves) /    \
389
    sizeof(ecp_supported_curves[0])
390
391
static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
392
393
/*
394
 * List of supported curves and associated info
395
 */
396
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list(void)
397
2.51k
{
398
2.51k
    return ecp_supported_curves;
399
2.51k
}
400
401
/*
402
 * List of supported curves, group ID only
403
 */
404
const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list(void)
405
0
{
406
0
    static int init_done = 0;
407
408
0
    if (!init_done) {
409
0
        size_t i = 0;
410
0
        const mbedtls_ecp_curve_info *curve_info;
411
412
0
        for (curve_info = mbedtls_ecp_curve_list();
413
0
             curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
414
0
             curve_info++) {
415
0
            ecp_supported_grp_id[i++] = curve_info->grp_id;
416
0
        }
417
0
        ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
418
419
0
        init_done = 1;
420
0
    }
421
422
0
    return ecp_supported_grp_id;
423
0
}
424
425
/*
426
 * Get the curve info for the internal identifier
427
 */
428
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id(mbedtls_ecp_group_id grp_id)
429
0
{
430
0
    const mbedtls_ecp_curve_info *curve_info;
431
432
0
    for (curve_info = mbedtls_ecp_curve_list();
433
0
         curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
434
0
         curve_info++) {
435
0
        if (curve_info->grp_id == grp_id) {
436
0
            return curve_info;
437
0
        }
438
0
    }
439
440
0
    return NULL;
441
0
}
442
443
/*
444
 * Get the curve info from the TLS identifier
445
 */
446
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id(uint16_t tls_id)
447
2.51k
{
448
2.51k
    const mbedtls_ecp_curve_info *curve_info;
449
450
2.51k
    for (curve_info = mbedtls_ecp_curve_list();
451
11.8k
         curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
452
11.8k
         curve_info++) {
453
11.8k
        if (curve_info->tls_id == tls_id) {
454
2.51k
            return curve_info;
455
2.51k
        }
456
11.8k
    }
457
458
0
    return NULL;
459
2.51k
}
460
461
/*
462
 * Get the curve info from the name
463
 */
464
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name(const char *name)
465
0
{
466
0
    const mbedtls_ecp_curve_info *curve_info;
467
468
0
    if (name == NULL) {
469
0
        return NULL;
470
0
    }
471
472
0
    for (curve_info = mbedtls_ecp_curve_list();
473
0
         curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
474
0
         curve_info++) {
475
0
        if (strcmp(curve_info->name, name) == 0) {
476
0
            return curve_info;
477
0
        }
478
0
    }
479
480
0
    return NULL;
481
0
}
482
483
/*
484
 * Get the type of a curve
485
 */
486
mbedtls_ecp_curve_type mbedtls_ecp_get_type(const mbedtls_ecp_group *grp)
487
15.0k
{
488
15.0k
    if (grp->G.X.p == NULL) {
489
0
        return MBEDTLS_ECP_TYPE_NONE;
490
0
    }
491
492
15.0k
    if (grp->G.Y.p == NULL) {
493
0
        return MBEDTLS_ECP_TYPE_MONTGOMERY;
494
15.0k
    } else {
495
15.0k
        return MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS;
496
15.0k
    }
497
15.0k
}
498
499
/*
500
 * Initialize (the components of) a point
501
 */
502
void mbedtls_ecp_point_init(mbedtls_ecp_point *pt)
503
18.5k
{
504
18.5k
    mbedtls_mpi_init(&pt->X);
505
18.5k
    mbedtls_mpi_init(&pt->Y);
506
18.5k
    mbedtls_mpi_init(&pt->Z);
507
18.5k
}
508
509
/*
510
 * Initialize (the components of) a group
511
 */
512
void mbedtls_ecp_group_init(mbedtls_ecp_group *grp)
513
5.80k
{
514
5.80k
    grp->id = MBEDTLS_ECP_DP_NONE;
515
5.80k
    mbedtls_mpi_init(&grp->P);
516
5.80k
    mbedtls_mpi_init(&grp->A);
517
5.80k
    mbedtls_mpi_init(&grp->B);
518
5.80k
    mbedtls_ecp_point_init(&grp->G);
519
5.80k
    mbedtls_mpi_init(&grp->N);
520
5.80k
    grp->pbits = 0;
521
5.80k
    grp->nbits = 0;
522
5.80k
    grp->h = 0;
523
5.80k
    grp->modp = NULL;
524
5.80k
    grp->t_pre = NULL;
525
5.80k
    grp->t_post = NULL;
526
5.80k
    grp->t_data = NULL;
527
5.80k
    grp->T = NULL;
528
5.80k
    grp->T_size = 0;
529
5.80k
}
530
531
/*
532
 * Initialize (the components of) a key pair
533
 */
534
void mbedtls_ecp_keypair_init(mbedtls_ecp_keypair *key)
535
1.63k
{
536
1.63k
    mbedtls_ecp_group_init(&key->grp);
537
1.63k
    mbedtls_mpi_init(&key->d);
538
1.63k
    mbedtls_ecp_point_init(&key->Q);
539
1.63k
}
540
541
/*
542
 * Unallocate (the components of) a point
543
 */
544
void mbedtls_ecp_point_free(mbedtls_ecp_point *pt)
545
16.3k
{
546
16.3k
    if (pt == NULL) {
547
0
        return;
548
0
    }
549
550
16.3k
    mbedtls_mpi_free(&(pt->X));
551
16.3k
    mbedtls_mpi_free(&(pt->Y));
552
16.3k
    mbedtls_mpi_free(&(pt->Z));
553
16.3k
}
554
555
/*
556
 * Check that the comb table (grp->T) is static initialized.
557
 */
558
static int ecp_group_is_static_comb_table(const mbedtls_ecp_group *grp)
559
7.02k
{
560
7.02k
#if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
561
7.02k
    return grp->T != NULL && grp->T_size == 0;
562
#else
563
    (void) grp;
564
    return 0;
565
#endif
566
7.02k
}
567
568
/*
569
 * Unallocate (the components of) a group
570
 */
571
void mbedtls_ecp_group_free(mbedtls_ecp_group *grp)
572
5.80k
{
573
5.80k
    size_t i;
574
575
5.80k
    if (grp == NULL) {
576
0
        return;
577
0
    }
578
579
5.80k
    if (grp->h != 1) {
580
3.29k
        mbedtls_mpi_free(&grp->A);
581
3.29k
        mbedtls_mpi_free(&grp->B);
582
3.29k
        mbedtls_ecp_point_free(&grp->G);
583
584
3.29k
#if !defined(MBEDTLS_ECP_WITH_MPI_UINT)
585
3.29k
        mbedtls_mpi_free(&grp->N);
586
3.29k
        mbedtls_mpi_free(&grp->P);
587
3.29k
#endif
588
3.29k
    }
589
590
5.80k
    if (!ecp_group_is_static_comb_table(grp) && grp->T != NULL) {
591
0
        for (i = 0; i < grp->T_size; i++) {
592
0
            mbedtls_ecp_point_free(&grp->T[i]);
593
0
        }
594
0
        mbedtls_free(grp->T);
595
0
    }
596
597
5.80k
    mbedtls_platform_zeroize(grp, sizeof(mbedtls_ecp_group));
598
5.80k
}
599
600
/*
601
 * Unallocate (the components of) a key pair
602
 */
603
void mbedtls_ecp_keypair_free(mbedtls_ecp_keypair *key)
604
1.63k
{
605
1.63k
    if (key == NULL) {
606
0
        return;
607
0
    }
608
609
1.63k
    mbedtls_ecp_group_free(&key->grp);
610
1.63k
    mbedtls_mpi_free(&key->d);
611
1.63k
    mbedtls_ecp_point_free(&key->Q);
612
1.63k
}
613
614
/*
615
 * Copy the contents of a point
616
 */
617
int mbedtls_ecp_copy(mbedtls_ecp_point *P, const mbedtls_ecp_point *Q)
618
2.22k
{
619
2.22k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
620
2.22k
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->X, &Q->X));
621
2.22k
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->Y, &Q->Y));
622
2.22k
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->Z, &Q->Z));
623
624
2.22k
cleanup:
625
2.22k
    return ret;
626
2.22k
}
627
628
/*
629
 * Copy the contents of a group object
630
 */
631
int mbedtls_ecp_group_copy(mbedtls_ecp_group *dst, const mbedtls_ecp_group *src)
632
0
{
633
0
    return mbedtls_ecp_group_load(dst, src->id);
634
0
}
635
636
/*
637
 * Set point to zero
638
 */
639
int mbedtls_ecp_set_zero(mbedtls_ecp_point *pt)
640
6
{
641
6
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
642
6
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->X, 1));
643
6
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Y, 1));
644
6
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 0));
645
646
6
cleanup:
647
6
    return ret;
648
6
}
649
650
/*
651
 * Tell if a point is zero
652
 */
653
int mbedtls_ecp_is_zero(mbedtls_ecp_point *pt)
654
331
{
655
331
    return mbedtls_mpi_cmp_int(&pt->Z, 0) == 0;
656
331
}
657
658
/*
659
 * Compare two points lazily
660
 */
661
int mbedtls_ecp_point_cmp(const mbedtls_ecp_point *P,
662
                          const mbedtls_ecp_point *Q)
663
0
{
664
0
    if (mbedtls_mpi_cmp_mpi(&P->X, &Q->X) == 0 &&
665
0
        mbedtls_mpi_cmp_mpi(&P->Y, &Q->Y) == 0 &&
666
0
        mbedtls_mpi_cmp_mpi(&P->Z, &Q->Z) == 0) {
667
0
        return 0;
668
0
    }
669
670
0
    return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
671
0
}
672
673
/*
674
 * Import a non-zero point from ASCII strings
675
 */
676
int mbedtls_ecp_point_read_string(mbedtls_ecp_point *P, int radix,
677
                                  const char *x, const char *y)
678
0
{
679
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
680
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&P->X, radix, x));
681
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&P->Y, radix, y));
682
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&P->Z, 1));
683
684
0
cleanup:
685
0
    return ret;
686
0
}
687
688
/*
689
 * Export a point into unsigned binary data (SEC1 2.3.3 and RFC7748)
690
 */
691
int mbedtls_ecp_point_write_binary(const mbedtls_ecp_group *grp,
692
                                   const mbedtls_ecp_point *P,
693
                                   int format, size_t *olen,
694
                                   unsigned char *buf, size_t buflen)
695
0
{
696
0
    int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
697
0
    size_t plen;
698
0
    if (format != MBEDTLS_ECP_PF_UNCOMPRESSED &&
699
0
        format != MBEDTLS_ECP_PF_COMPRESSED) {
700
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
701
0
    }
702
703
0
    plen = mbedtls_mpi_size(&grp->P);
704
705
0
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
706
0
    (void) format; /* Montgomery curves always use the same point format */
707
0
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
708
0
        *olen = plen;
709
0
        if (buflen < *olen) {
710
0
            return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
711
0
        }
712
713
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary_le(&P->X, buf, plen));
714
0
    }
715
0
#endif
716
0
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
717
0
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
718
        /*
719
         * Common case: P == 0
720
         */
721
0
        if (mbedtls_mpi_cmp_int(&P->Z, 0) == 0) {
722
0
            if (buflen < 1) {
723
0
                return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
724
0
            }
725
726
0
            buf[0] = 0x00;
727
0
            *olen = 1;
728
729
0
            return 0;
730
0
        }
731
732
0
        if (format == MBEDTLS_ECP_PF_UNCOMPRESSED) {
733
0
            *olen = 2 * plen + 1;
734
735
0
            if (buflen < *olen) {
736
0
                return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
737
0
            }
738
739
0
            buf[0] = 0x04;
740
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->X, buf + 1, plen));
741
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->Y, buf + 1 + plen, plen));
742
0
        } else if (format == MBEDTLS_ECP_PF_COMPRESSED) {
743
0
            *olen = plen + 1;
744
745
0
            if (buflen < *olen) {
746
0
                return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
747
0
            }
748
749
0
            buf[0] = 0x02 + mbedtls_mpi_get_bit(&P->Y, 0);
750
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->X, buf + 1, plen));
751
0
        }
752
0
    }
753
0
#endif
754
755
0
cleanup:
756
0
    return ret;
757
0
}
758
759
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
760
static int mbedtls_ecp_sw_derive_y(const mbedtls_ecp_group *grp,
761
                                   const mbedtls_mpi *X,
762
                                   mbedtls_mpi *Y,
763
                                   int parity_bit);
764
#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
765
766
/*
767
 * Import a point from unsigned binary data (SEC1 2.3.4 and RFC7748)
768
 */
769
int mbedtls_ecp_point_read_binary(const mbedtls_ecp_group *grp,
770
                                  mbedtls_ecp_point *pt,
771
                                  const unsigned char *buf, size_t ilen)
772
0
{
773
0
    int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
774
0
    size_t plen;
775
0
    if (ilen < 1) {
776
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
777
0
    }
778
779
0
    plen = mbedtls_mpi_size(&grp->P);
780
781
0
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
782
0
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
783
0
        if (plen != ilen) {
784
0
            return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
785
0
        }
786
787
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary_le(&pt->X, buf, plen));
788
0
        mbedtls_mpi_free(&pt->Y);
789
790
0
        if (grp->id == MBEDTLS_ECP_DP_CURVE25519) {
791
            /* Set most significant bit to 0 as prescribed in RFC7748 §5 */
792
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&pt->X, plen * 8 - 1, 0));
793
0
        }
794
795
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 1));
796
0
    }
797
0
#endif
798
0
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
799
0
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
800
0
        if (buf[0] == 0x00) {
801
0
            if (ilen == 1) {
802
0
                return mbedtls_ecp_set_zero(pt);
803
0
            } else {
804
0
                return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
805
0
            }
806
0
        }
807
808
0
        if (ilen < 1 + plen) {
809
0
            return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
810
0
        }
811
812
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(&pt->X, buf + 1, plen));
813
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 1));
814
815
0
        if (buf[0] == 0x04) {
816
            /* format == MBEDTLS_ECP_PF_UNCOMPRESSED */
817
0
            if (ilen != 1 + plen * 2) {
818
0
                return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
819
0
            }
820
0
            return mbedtls_mpi_read_binary(&pt->Y, buf + 1 + plen, plen);
821
0
        } else if (buf[0] == 0x02 || buf[0] == 0x03) {
822
            /* format == MBEDTLS_ECP_PF_COMPRESSED */
823
0
            if (ilen != 1 + plen) {
824
0
                return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
825
0
            }
826
0
            return mbedtls_ecp_sw_derive_y(grp, &pt->X, &pt->Y,
827
0
                                           (buf[0] & 1));
828
0
        } else {
829
0
            return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
830
0
        }
831
0
    }
832
0
#endif
833
834
0
cleanup:
835
0
    return ret;
836
0
}
837
838
/*
839
 * Import a point from a TLS ECPoint record (RFC 4492)
840
 *      struct {
841
 *          opaque point <1..2^8-1>;
842
 *      } ECPoint;
843
 */
844
int mbedtls_ecp_tls_read_point(const mbedtls_ecp_group *grp,
845
                               mbedtls_ecp_point *pt,
846
                               const unsigned char **buf, size_t buf_len)
847
0
{
848
0
    unsigned char data_len;
849
0
    const unsigned char *buf_start;
850
    /*
851
     * We must have at least two bytes (1 for length, at least one for data)
852
     */
853
0
    if (buf_len < 2) {
854
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
855
0
    }
856
857
0
    data_len = *(*buf)++;
858
0
    if (data_len < 1 || data_len > buf_len - 1) {
859
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
860
0
    }
861
862
    /*
863
     * Save buffer start for read_binary and update buf
864
     */
865
0
    buf_start = *buf;
866
0
    *buf += data_len;
867
868
0
    return mbedtls_ecp_point_read_binary(grp, pt, buf_start, data_len);
869
0
}
870
871
/*
872
 * Export a point as a TLS ECPoint record (RFC 4492)
873
 *      struct {
874
 *          opaque point <1..2^8-1>;
875
 *      } ECPoint;
876
 */
877
int mbedtls_ecp_tls_write_point(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt,
878
                                int format, size_t *olen,
879
                                unsigned char *buf, size_t blen)
880
0
{
881
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
882
0
    if (format != MBEDTLS_ECP_PF_UNCOMPRESSED &&
883
0
        format != MBEDTLS_ECP_PF_COMPRESSED) {
884
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
885
0
    }
886
887
    /*
888
     * buffer length must be at least one, for our length byte
889
     */
890
0
    if (blen < 1) {
891
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
892
0
    }
893
894
0
    if ((ret = mbedtls_ecp_point_write_binary(grp, pt, format,
895
0
                                              olen, buf + 1, blen - 1)) != 0) {
896
0
        return ret;
897
0
    }
898
899
    /*
900
     * write length to the first byte and update total length
901
     */
902
0
    buf[0] = (unsigned char) *olen;
903
0
    ++*olen;
904
905
0
    return 0;
906
0
}
907
908
/*
909
 * Set a group from an ECParameters record (RFC 4492)
910
 */
911
int mbedtls_ecp_tls_read_group(mbedtls_ecp_group *grp,
912
                               const unsigned char **buf, size_t len)
913
0
{
914
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
915
0
    mbedtls_ecp_group_id grp_id;
916
0
    if ((ret = mbedtls_ecp_tls_read_group_id(&grp_id, buf, len)) != 0) {
917
0
        return ret;
918
0
    }
919
920
0
    return mbedtls_ecp_group_load(grp, grp_id);
921
0
}
922
923
/*
924
 * Read a group id from an ECParameters record (RFC 4492) and convert it to
925
 * mbedtls_ecp_group_id.
926
 */
927
int mbedtls_ecp_tls_read_group_id(mbedtls_ecp_group_id *grp,
928
                                  const unsigned char **buf, size_t len)
929
0
{
930
0
    uint16_t tls_id;
931
0
    const mbedtls_ecp_curve_info *curve_info;
932
    /*
933
     * We expect at least three bytes (see below)
934
     */
935
0
    if (len < 3) {
936
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
937
0
    }
938
939
    /*
940
     * First byte is curve_type; only named_curve is handled
941
     */
942
0
    if (*(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE) {
943
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
944
0
    }
945
946
    /*
947
     * Next two bytes are the namedcurve value
948
     */
949
0
    tls_id = MBEDTLS_GET_UINT16_BE(*buf, 0);
950
0
    *buf += 2;
951
952
0
    if ((curve_info = mbedtls_ecp_curve_info_from_tls_id(tls_id)) == NULL) {
953
0
        return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
954
0
    }
955
956
0
    *grp = curve_info->grp_id;
957
958
0
    return 0;
959
0
}
960
961
/*
962
 * Write the ECParameters record corresponding to a group (RFC 4492)
963
 */
964
int mbedtls_ecp_tls_write_group(const mbedtls_ecp_group *grp, size_t *olen,
965
                                unsigned char *buf, size_t blen)
966
0
{
967
0
    const mbedtls_ecp_curve_info *curve_info;
968
0
    if ((curve_info = mbedtls_ecp_curve_info_from_grp_id(grp->id)) == NULL) {
969
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
970
0
    }
971
972
    /*
973
     * We are going to write 3 bytes (see below)
974
     */
975
0
    *olen = 3;
976
0
    if (blen < *olen) {
977
0
        return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
978
0
    }
979
980
    /*
981
     * First byte is curve_type, always named_curve
982
     */
983
0
    *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
984
985
    /*
986
     * Next two bytes are the namedcurve value
987
     */
988
0
    MBEDTLS_PUT_UINT16_BE(curve_info->tls_id, buf, 0);
989
990
0
    return 0;
991
0
}
992
993
/*
994
 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
995
 * See the documentation of struct mbedtls_ecp_group.
996
 *
997
 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
998
 */
999
static int ecp_modp(mbedtls_mpi *N, const mbedtls_ecp_group *grp)
1000
2.87M
{
1001
2.87M
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1002
1003
2.87M
    if (grp->modp == NULL) {
1004
278k
        return mbedtls_mpi_mod_mpi(N, N, &grp->P);
1005
278k
    }
1006
1007
    /* N->s < 0 is a much faster test, which fails only if N is 0 */
1008
2.60M
    if ((N->s < 0 && mbedtls_mpi_cmp_int(N, 0) != 0) ||
1009
2.60M
        mbedtls_mpi_bitlen(N) > 2 * grp->pbits) {
1010
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1011
0
    }
1012
1013
2.60M
    MBEDTLS_MPI_CHK(grp->modp(N));
1014
1015
    /* N->s < 0 is a much faster test, which fails only if N is 0 */
1016
3.53M
    while (N->s < 0 && mbedtls_mpi_cmp_int(N, 0) != 0) {
1017
933k
        MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(N, N, &grp->P));
1018
933k
    }
1019
1020
3.67M
    while (mbedtls_mpi_cmp_mpi(N, &grp->P) >= 0) {
1021
        /* we known P, N and the result are positive */
1022
1.07M
        MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(N, N, &grp->P));
1023
1.07M
    }
1024
1025
2.60M
cleanup:
1026
2.60M
    return ret;
1027
2.60M
}
1028
1029
/*
1030
 * Fast mod-p functions expect their argument to be in the 0..p^2 range.
1031
 *
1032
 * In order to guarantee that, we need to ensure that operands of
1033
 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
1034
 * bring the result back to this range.
1035
 *
1036
 * The following macros are shortcuts for doing that.
1037
 */
1038
1039
/*
1040
 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
1041
 */
1042
#if defined(MBEDTLS_SELF_TEST)
1043
2.87M
#define INC_MUL_COUNT   mul_count++;
1044
#else
1045
#define INC_MUL_COUNT
1046
#endif
1047
1048
#define MOD_MUL(N)                                                    \
1049
2.87M
    do                                                                  \
1050
2.87M
    {                                                                   \
1051
2.87M
        MBEDTLS_MPI_CHK(ecp_modp(&(N), grp));                       \
1052
2.87M
        INC_MUL_COUNT                                                   \
1053
2.87M
    } while (0)
1054
1055
static inline int mbedtls_mpi_mul_mod(const mbedtls_ecp_group *grp,
1056
                                      mbedtls_mpi *X,
1057
                                      const mbedtls_mpi *A,
1058
                                      const mbedtls_mpi *B)
1059
2.87M
{
1060
2.87M
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1061
2.87M
    MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(X, A, B));
1062
2.87M
    MOD_MUL(*X);
1063
2.87M
cleanup:
1064
2.87M
    return ret;
1065
2.87M
}
1066
1067
/*
1068
 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
1069
 * N->s < 0 is a very fast test, which fails only if N is 0
1070
 */
1071
#define MOD_SUB(N)                                                          \
1072
1.63M
    do {                                                                      \
1073
2.45M
        while ((N)->s < 0 && mbedtls_mpi_cmp_int((N), 0) != 0)             \
1074
1.63M
        MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi((N), (N), &grp->P));      \
1075
1.63M
    } while (0)
1076
1077
MBEDTLS_MAYBE_UNUSED
1078
static inline int mbedtls_mpi_sub_mod(const mbedtls_ecp_group *grp,
1079
                                      mbedtls_mpi *X,
1080
                                      const mbedtls_mpi *A,
1081
                                      const mbedtls_mpi *B)
1082
1.63M
{
1083
1.63M
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1084
1.63M
    MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(X, A, B));
1085
1.63M
    MOD_SUB(X);
1086
1.63M
cleanup:
1087
1.63M
    return ret;
1088
1.63M
}
1089
1090
/*
1091
 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
1092
 * We known P, N and the result are positive, so sub_abs is correct, and
1093
 * a bit faster.
1094
 */
1095
#define MOD_ADD(N)                                                   \
1096
2.16M
    while (mbedtls_mpi_cmp_mpi((N), &grp->P) >= 0)                  \
1097
1.37M
    MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs((N), (N), &grp->P))
1098
1099
static inline int mbedtls_mpi_add_mod(const mbedtls_ecp_group *grp,
1100
                                      mbedtls_mpi *X,
1101
                                      const mbedtls_mpi *A,
1102
                                      const mbedtls_mpi *B)
1103
202k
{
1104
202k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1105
202k
    MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, A, B));
1106
202k
    MOD_ADD(X);
1107
202k
cleanup:
1108
202k
    return ret;
1109
202k
}
1110
1111
MBEDTLS_MAYBE_UNUSED
1112
static inline int mbedtls_mpi_mul_int_mod(const mbedtls_ecp_group *grp,
1113
                                          mbedtls_mpi *X,
1114
                                          const mbedtls_mpi *A,
1115
                                          mbedtls_mpi_uint c)
1116
214k
{
1117
214k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1118
1119
214k
    MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(X, A, c));
1120
214k
    MOD_ADD(X);
1121
214k
cleanup:
1122
214k
    return ret;
1123
214k
}
1124
1125
MBEDTLS_MAYBE_UNUSED
1126
static inline int mbedtls_mpi_sub_int_mod(const mbedtls_ecp_group *grp,
1127
                                          mbedtls_mpi *X,
1128
                                          const mbedtls_mpi *A,
1129
                                          mbedtls_mpi_uint c)
1130
2.26k
{
1131
2.26k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1132
1133
2.26k
    MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(X, A, c));
1134
2.26k
    MOD_SUB(X);
1135
2.26k
cleanup:
1136
2.26k
    return ret;
1137
2.26k
}
1138
1139
#define MPI_ECP_SUB_INT(X, A, c)             \
1140
2.26k
    MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int_mod(grp, X, A, c))
1141
1142
MBEDTLS_MAYBE_UNUSED
1143
static inline int mbedtls_mpi_shift_l_mod(const mbedtls_ecp_group *grp,
1144
                                          mbedtls_mpi *X,
1145
                                          size_t count)
1146
957k
{
1147
957k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1148
957k
    MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(X, count));
1149
957k
    MOD_ADD(X);
1150
957k
cleanup:
1151
957k
    return ret;
1152
957k
}
1153
1154
/*
1155
 * Macro wrappers around ECP modular arithmetic
1156
 *
1157
 * Currently, these wrappers are defined via the bignum module.
1158
 */
1159
1160
#define MPI_ECP_ADD(X, A, B)                                                  \
1161
202k
    MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, X, A, B))
1162
1163
#define MPI_ECP_SUB(X, A, B)                                                  \
1164
1.63M
    MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, X, A, B))
1165
1166
#define MPI_ECP_MUL(X, A, B)                                                  \
1167
1.67M
    MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, X, A, B))
1168
1169
#define MPI_ECP_SQR(X, A)                                                     \
1170
1.20M
    MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, X, A, A))
1171
1172
#define MPI_ECP_MUL_INT(X, A, c)                                              \
1173
214k
    MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int_mod(grp, X, A, c))
1174
1175
#define MPI_ECP_INV(dst, src)                                                 \
1176
2.75k
    MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod((dst), (src), &grp->P))
1177
1178
#define MPI_ECP_MOV(X, A)                                                     \
1179
744k
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A))
1180
1181
#define MPI_ECP_SHIFT_L(X, count)                                             \
1182
957k
    MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, X, count))
1183
1184
#define MPI_ECP_LSET(X, c)                                                    \
1185
103k
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, c))
1186
1187
#define MPI_ECP_CMP_INT(X, c)                                                 \
1188
430k
    mbedtls_mpi_cmp_int(X, c)
1189
1190
#define MPI_ECP_CMP(X, Y)                                                     \
1191
5.75k
    mbedtls_mpi_cmp_mpi(X, Y)
1192
1193
/* Needs f_rng, p_rng to be defined. */
1194
#define MPI_ECP_RAND(X)                                                       \
1195
1.92k
    MBEDTLS_MPI_CHK(mbedtls_mpi_random((X), 2, &grp->P, f_rng, p_rng))
1196
1197
/* Conditional negation
1198
 * Needs grp and a temporary MPI tmp to be defined. */
1199
#define MPI_ECP_COND_NEG(X, cond)                                        \
1200
98.1k
    do                                                                     \
1201
98.1k
    {                                                                      \
1202
98.1k
        unsigned char nonzero = mbedtls_mpi_cmp_int((X), 0) != 0;        \
1203
98.1k
        MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&tmp, &grp->P, (X)));      \
1204
98.1k
        MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign((X), &tmp,          \
1205
98.1k
                                                     nonzero & cond)); \
1206
98.1k
    } while (0)
1207
1208
0
#define MPI_ECP_NEG(X) MPI_ECP_COND_NEG((X), 1)
1209
1210
#define MPI_ECP_VALID(X)                      \
1211
98.8k
    ((X)->p != NULL)
1212
1213
#define MPI_ECP_COND_ASSIGN(X, Y, cond)       \
1214
3.38M
    MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign((X), (Y), (cond)))
1215
1216
#define MPI_ECP_COND_SWAP(X, Y, cond)       \
1217
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_swap((X), (Y), (cond)))
1218
1219
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
1220
1221
/*
1222
 * Computes the right-hand side of the Short Weierstrass equation
1223
 * RHS = X^3 + A X + B
1224
 */
1225
static int ecp_sw_rhs(const mbedtls_ecp_group *grp,
1226
                      mbedtls_mpi *rhs,
1227
                      const mbedtls_mpi *X)
1228
2.81k
{
1229
2.81k
    int ret;
1230
1231
    /* Compute X^3 + A X + B as X (X^2 + A) + B */
1232
2.81k
    MPI_ECP_SQR(rhs, X);
1233
1234
    /* Special case for A = -3 */
1235
2.81k
    if (mbedtls_ecp_group_a_is_minus_3(grp)) {
1236
2.26k
        MPI_ECP_SUB_INT(rhs, rhs, 3);
1237
2.26k
    } else {
1238
551
        MPI_ECP_ADD(rhs, rhs, &grp->A);
1239
551
    }
1240
1241
2.81k
    MPI_ECP_MUL(rhs, rhs, X);
1242
2.81k
    MPI_ECP_ADD(rhs, rhs, &grp->B);
1243
1244
2.81k
cleanup:
1245
2.81k
    return ret;
1246
2.81k
}
1247
1248
/*
1249
 * Derive Y from X and a parity bit
1250
 */
1251
static int mbedtls_ecp_sw_derive_y(const mbedtls_ecp_group *grp,
1252
                                   const mbedtls_mpi *X,
1253
                                   mbedtls_mpi *Y,
1254
                                   int parity_bit)
1255
0
{
1256
    /* w = y^2 = x^3 + ax + b
1257
     * y = sqrt(w) = w^((p+1)/4) mod p   (for prime p where p = 3 mod 4)
1258
     *
1259
     * Note: this method for extracting square root does not validate that w
1260
     * was indeed a square so this function will return garbage in Y if X
1261
     * does not correspond to a point on the curve.
1262
     */
1263
1264
    /* Check prerequisite p = 3 mod 4 */
1265
0
    if (mbedtls_mpi_get_bit(&grp->P, 0) != 1 ||
1266
0
        mbedtls_mpi_get_bit(&grp->P, 1) != 1) {
1267
0
        return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1268
0
    }
1269
1270
0
    int ret;
1271
0
    mbedtls_mpi exp;
1272
0
    mbedtls_mpi_init(&exp);
1273
1274
    /* use Y to store intermediate result, actually w above */
1275
0
    MBEDTLS_MPI_CHK(ecp_sw_rhs(grp, Y, X));
1276
1277
    /* w = y^2 */ /* Y contains y^2 intermediate result */
1278
    /* exp = ((p+1)/4) */
1279
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&exp, &grp->P, 1));
1280
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&exp, 2));
1281
    /* sqrt(w) = w^((p+1)/4) mod p   (for prime p where p = 3 mod 4) */
1282
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(Y, Y /*y^2*/, &exp, &grp->P, NULL));
1283
1284
    /* check parity bit match or else invert Y */
1285
    /* This quick inversion implementation is valid because Y != 0 for all
1286
     * Short Weierstrass curves supported by mbedtls, as each supported curve
1287
     * has an order that is a large prime, so each supported curve does not
1288
     * have any point of order 2, and a point with Y == 0 would be of order 2 */
1289
0
    if (mbedtls_mpi_get_bit(Y, 0) != parity_bit) {
1290
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(Y, &grp->P, Y));
1291
0
    }
1292
1293
0
cleanup:
1294
1295
0
    mbedtls_mpi_free(&exp);
1296
0
    return ret;
1297
0
}
1298
#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
1299
1300
#if defined(MBEDTLS_ECP_C)
1301
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
1302
/*
1303
 * For curves in short Weierstrass form, we do all the internal operations in
1304
 * Jacobian coordinates.
1305
 *
1306
 * For multiplication, we'll use a comb method with countermeasures against
1307
 * SPA, hence timing attacks.
1308
 */
1309
1310
/*
1311
 * Normalize jacobian coordinates so that Z == 0 || Z == 1  (GECC 3.2.1)
1312
 * Cost: 1N := 1I + 3M + 1S
1313
 */
1314
static int ecp_normalize_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt)
1315
1.72k
{
1316
1.72k
    if (MPI_ECP_CMP_INT(&pt->Z, 0) == 0) {
1317
0
        return 0;
1318
0
    }
1319
1320
#if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
1321
    if (mbedtls_internal_ecp_grp_capable(grp)) {
1322
        return mbedtls_internal_ecp_normalize_jac(grp, pt);
1323
    }
1324
#endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */
1325
1326
#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
1327
    return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1328
#else
1329
1.72k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1330
1.72k
    mbedtls_mpi T;
1331
1.72k
    mbedtls_mpi_init(&T);
1332
1333
1.72k
    MPI_ECP_INV(&T,       &pt->Z);            /* T   <-          1 / Z   */
1334
1.72k
    MPI_ECP_MUL(&pt->Y,   &pt->Y,     &T);    /* Y'  <- Y*T    = Y / Z   */
1335
1.72k
    MPI_ECP_SQR(&T,       &T);                /* T   <- T^2    = 1 / Z^2 */
1336
1.72k
    MPI_ECP_MUL(&pt->X,   &pt->X,     &T);    /* X   <- X  * T = X / Z^2 */
1337
1.72k
    MPI_ECP_MUL(&pt->Y,   &pt->Y,     &T);    /* Y'' <- Y' * T = Y / Z^3 */
1338
1339
1.72k
    MPI_ECP_LSET(&pt->Z, 1);
1340
1341
1.72k
cleanup:
1342
1343
1.72k
    mbedtls_mpi_free(&T);
1344
1345
1.72k
    return ret;
1346
1.72k
#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) */
1347
1.72k
}
1348
1349
/*
1350
 * Normalize jacobian coordinates of an array of (pointers to) points,
1351
 * using Montgomery's trick to perform only one inversion mod P.
1352
 * (See for example Cohen's "A Course in Computational Algebraic Number
1353
 * Theory", Algorithm 10.3.4.)
1354
 *
1355
 * Warning: fails (returning an error) if one of the points is zero!
1356
 * This should never happen, see choice of w in ecp_mul_comb().
1357
 *
1358
 * Cost: 1N(t) := 1I + (6t - 3)M + 1S
1359
 */
1360
static int ecp_normalize_jac_many(const mbedtls_ecp_group *grp,
1361
                                  mbedtls_ecp_point *T[], size_t T_size)
1362
1.02k
{
1363
1.02k
    if (T_size < 2) {
1364
0
        return ecp_normalize_jac(grp, *T);
1365
0
    }
1366
1367
#if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
1368
    if (mbedtls_internal_ecp_grp_capable(grp)) {
1369
        return mbedtls_internal_ecp_normalize_jac_many(grp, T, T_size);
1370
    }
1371
#endif
1372
1373
#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
1374
    return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1375
#else
1376
1.02k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1377
1.02k
    size_t i;
1378
1.02k
    mbedtls_mpi *c, t;
1379
1380
1.02k
    if ((c = mbedtls_calloc(T_size, sizeof(mbedtls_mpi))) == NULL) {
1381
0
        return MBEDTLS_ERR_ECP_ALLOC_FAILED;
1382
0
    }
1383
1384
1.02k
    mbedtls_mpi_init(&t);
1385
1386
1.02k
    mpi_init_many(c, T_size);
1387
    /*
1388
     * c[i] = Z_0 * ... * Z_i,   i = 0,..,n := T_size-1
1389
     */
1390
1.02k
    MPI_ECP_MOV(&c[0], &T[0]->Z);
1391
5.13k
    for (i = 1; i < T_size; i++) {
1392
4.10k
        MPI_ECP_MUL(&c[i], &c[i-1], &T[i]->Z);
1393
4.10k
    }
1394
1395
    /*
1396
     * c[n] = 1 / (Z_0 * ... * Z_n) mod P
1397
     */
1398
1.02k
    MPI_ECP_INV(&c[T_size-1], &c[T_size-1]);
1399
1400
5.13k
    for (i = T_size - 1;; i--) {
1401
        /* At the start of iteration i (note that i decrements), we have
1402
         * - c[j] = Z_0 * .... * Z_j        for j  < i,
1403
         * - c[j] = 1 / (Z_0 * .... * Z_j)  for j == i,
1404
         *
1405
         * This is maintained via
1406
         * - c[i-1] <- c[i] * Z_i
1407
         *
1408
         * We also derive 1/Z_i = c[i] * c[i-1] for i>0 and use that
1409
         * to do the actual normalization. For i==0, we already have
1410
         * c[0] = 1 / Z_0.
1411
         */
1412
1413
5.13k
        if (i > 0) {
1414
            /* Compute 1/Z_i and establish invariant for the next iteration. */
1415
4.10k
            MPI_ECP_MUL(&t,      &c[i], &c[i-1]);
1416
4.10k
            MPI_ECP_MUL(&c[i-1], &c[i], &T[i]->Z);
1417
4.10k
        } else {
1418
1.02k
            MPI_ECP_MOV(&t, &c[0]);
1419
1.02k
        }
1420
1421
        /* Now t holds 1 / Z_i; normalize as in ecp_normalize_jac() */
1422
5.13k
        MPI_ECP_MUL(&T[i]->Y, &T[i]->Y, &t);
1423
5.13k
        MPI_ECP_SQR(&t,       &t);
1424
5.13k
        MPI_ECP_MUL(&T[i]->X, &T[i]->X, &t);
1425
5.13k
        MPI_ECP_MUL(&T[i]->Y, &T[i]->Y, &t);
1426
1427
        /*
1428
         * Post-precessing: reclaim some memory by shrinking coordinates
1429
         * - not storing Z (always 1)
1430
         * - shrinking other coordinates, but still keeping the same number of
1431
         *   limbs as P, as otherwise it will too likely be regrown too fast.
1432
         */
1433
5.13k
        MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(&T[i]->X, grp->P.n));
1434
5.13k
        MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(&T[i]->Y, grp->P.n));
1435
1436
5.13k
        MPI_ECP_LSET(&T[i]->Z, 1);
1437
1438
5.13k
        if (i == 0) {
1439
1.02k
            break;
1440
1.02k
        }
1441
5.13k
    }
1442
1443
1.02k
cleanup:
1444
1445
1.02k
    mbedtls_mpi_free(&t);
1446
1.02k
    mpi_free_many(c, T_size);
1447
1.02k
    mbedtls_free(c);
1448
1449
1.02k
    return ret;
1450
1.02k
#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) */
1451
1.02k
}
1452
1453
/*
1454
 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
1455
 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
1456
 */
1457
static int ecp_safe_invert_jac(const mbedtls_ecp_group *grp,
1458
                               mbedtls_ecp_point *Q,
1459
                               unsigned char inv)
1460
98.1k
{
1461
98.1k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1462
98.1k
    mbedtls_mpi tmp;
1463
98.1k
    mbedtls_mpi_init(&tmp);
1464
1465
98.1k
    MPI_ECP_COND_NEG(&Q->Y, inv);
1466
1467
98.1k
cleanup:
1468
98.1k
    mbedtls_mpi_free(&tmp);
1469
98.1k
    return ret;
1470
98.1k
}
1471
1472
/*
1473
 * Point doubling R = 2 P, Jacobian coordinates
1474
 *
1475
 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
1476
 *
1477
 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR
1478
 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.
1479
 *
1480
 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
1481
 *
1482
 * Cost: 1D := 3M + 4S          (A ==  0)
1483
 *             4M + 4S          (A == -3)
1484
 *             3M + 6S + 1a     otherwise
1485
 */
1486
static int ecp_double_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1487
                          const mbedtls_ecp_point *P,
1488
                          mbedtls_mpi tmp[4])
1489
214k
{
1490
214k
#if defined(MBEDTLS_SELF_TEST)
1491
214k
    dbl_count++;
1492
214k
#endif
1493
1494
#if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
1495
    if (mbedtls_internal_ecp_grp_capable(grp)) {
1496
        return mbedtls_internal_ecp_double_jac(grp, R, P);
1497
    }
1498
#endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */
1499
1500
#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
1501
    return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1502
#else
1503
214k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1504
1505
    /* Special case for A = -3 */
1506
214k
    if (mbedtls_ecp_group_a_is_minus_3(grp)) {
1507
        /* tmp[0] <- M = 3(X + Z^2)(X - Z^2) */
1508
181k
        MPI_ECP_SQR(&tmp[1],  &P->Z);
1509
181k
        MPI_ECP_ADD(&tmp[2],  &P->X,  &tmp[1]);
1510
181k
        MPI_ECP_SUB(&tmp[3],  &P->X,  &tmp[1]);
1511
181k
        MPI_ECP_MUL(&tmp[1],  &tmp[2],     &tmp[3]);
1512
181k
        MPI_ECP_MUL_INT(&tmp[0],  &tmp[1],     3);
1513
181k
    } else {
1514
        /* tmp[0] <- M = 3.X^2 + A.Z^4 */
1515
33.1k
        MPI_ECP_SQR(&tmp[1],  &P->X);
1516
33.1k
        MPI_ECP_MUL_INT(&tmp[0],  &tmp[1],  3);
1517
1518
        /* Optimize away for "koblitz" curves with A = 0 */
1519
33.1k
        if (MPI_ECP_CMP_INT(&grp->A, 0) != 0) {
1520
            /* M += A.Z^4 */
1521
17.6k
            MPI_ECP_SQR(&tmp[1],  &P->Z);
1522
17.6k
            MPI_ECP_SQR(&tmp[2],  &tmp[1]);
1523
17.6k
            MPI_ECP_MUL(&tmp[1],  &tmp[2],     &grp->A);
1524
17.6k
            MPI_ECP_ADD(&tmp[0],  &tmp[0],     &tmp[1]);
1525
17.6k
        }
1526
33.1k
    }
1527
1528
    /* tmp[1] <- S = 4.X.Y^2 */
1529
214k
    MPI_ECP_SQR(&tmp[2],  &P->Y);
1530
214k
    MPI_ECP_SHIFT_L(&tmp[2],  1);
1531
214k
    MPI_ECP_MUL(&tmp[1],  &P->X, &tmp[2]);
1532
214k
    MPI_ECP_SHIFT_L(&tmp[1],  1);
1533
1534
    /* tmp[3] <- U = 8.Y^4 */
1535
214k
    MPI_ECP_SQR(&tmp[3],  &tmp[2]);
1536
214k
    MPI_ECP_SHIFT_L(&tmp[3],  1);
1537
1538
    /* tmp[2] <- T = M^2 - 2.S */
1539
214k
    MPI_ECP_SQR(&tmp[2],  &tmp[0]);
1540
214k
    MPI_ECP_SUB(&tmp[2],  &tmp[2], &tmp[1]);
1541
214k
    MPI_ECP_SUB(&tmp[2],  &tmp[2], &tmp[1]);
1542
1543
    /* tmp[1] <- S = M(S - T) - U */
1544
214k
    MPI_ECP_SUB(&tmp[1],  &tmp[1],     &tmp[2]);
1545
214k
    MPI_ECP_MUL(&tmp[1],  &tmp[1],     &tmp[0]);
1546
214k
    MPI_ECP_SUB(&tmp[1],  &tmp[1],     &tmp[3]);
1547
1548
    /* tmp[3] <- U = 2.Y.Z */
1549
214k
    MPI_ECP_MUL(&tmp[3],  &P->Y,  &P->Z);
1550
214k
    MPI_ECP_SHIFT_L(&tmp[3],  1);
1551
1552
    /* Store results */
1553
214k
    MPI_ECP_MOV(&R->X, &tmp[2]);
1554
214k
    MPI_ECP_MOV(&R->Y, &tmp[1]);
1555
214k
    MPI_ECP_MOV(&R->Z, &tmp[3]);
1556
1557
214k
cleanup:
1558
1559
214k
    return ret;
1560
214k
#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) */
1561
214k
}
1562
1563
/*
1564
 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
1565
 *
1566
 * The coordinates of Q must be normalized (= affine),
1567
 * but those of P don't need to. R is not normalized.
1568
 *
1569
 * P,Q,R may alias, but only at the level of EC points: they must be either
1570
 * equal as pointers, or disjoint (including the coordinate data buffers).
1571
 * Fine-grained aliasing at the level of coordinates is not supported.
1572
 *
1573
 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
1574
 * None of these cases can happen as intermediate step in ecp_mul_comb():
1575
 * - at each step, P, Q and R are multiples of the base point, the factor
1576
 *   being less than its order, so none of them is zero;
1577
 * - Q is an odd multiple of the base point, P an even multiple,
1578
 *   due to the choice of precomputed points in the modified comb method.
1579
 * So branches for these cases do not leak secret information.
1580
 *
1581
 * Cost: 1A := 8M + 3S
1582
 */
1583
static int ecp_add_mixed(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
1584
                         const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q,
1585
                         mbedtls_mpi tmp[4])
1586
98.8k
{
1587
98.8k
#if defined(MBEDTLS_SELF_TEST)
1588
98.8k
    add_count++;
1589
98.8k
#endif
1590
1591
#if defined(MBEDTLS_ECP_ADD_MIXED_ALT)
1592
    if (mbedtls_internal_ecp_grp_capable(grp)) {
1593
        return mbedtls_internal_ecp_add_mixed(grp, R, P, Q);
1594
    }
1595
#endif /* MBEDTLS_ECP_ADD_MIXED_ALT */
1596
1597
#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_ADD_MIXED_ALT)
1598
    return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1599
#else
1600
98.8k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1601
1602
    /* NOTE: Aliasing between input and output is allowed, so one has to make
1603
     *       sure that at the point X,Y,Z are written, {P,Q}->{X,Y,Z} are no
1604
     *       longer read from. */
1605
98.8k
    mbedtls_mpi * const X = &R->X;
1606
98.8k
    mbedtls_mpi * const Y = &R->Y;
1607
98.8k
    mbedtls_mpi * const Z = &R->Z;
1608
1609
98.8k
    if (!MPI_ECP_VALID(&Q->Z)) {
1610
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1611
0
    }
1612
1613
    /*
1614
     * Trivial cases: P == 0 or Q == 0 (case 1)
1615
     */
1616
98.8k
    if (MPI_ECP_CMP_INT(&P->Z, 0) == 0) {
1617
6
        return mbedtls_ecp_copy(R, Q);
1618
6
    }
1619
1620
98.8k
    if (MPI_ECP_CMP_INT(&Q->Z, 0) == 0) {
1621
0
        return mbedtls_ecp_copy(R, P);
1622
0
    }
1623
1624
    /*
1625
     * Make sure Q coordinates are normalized
1626
     */
1627
98.8k
    if (MPI_ECP_CMP_INT(&Q->Z, 1) != 0) {
1628
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
1629
0
    }
1630
1631
98.8k
    MPI_ECP_SQR(&tmp[0], &P->Z);
1632
98.8k
    MPI_ECP_MUL(&tmp[1], &tmp[0], &P->Z);
1633
98.8k
    MPI_ECP_MUL(&tmp[0], &tmp[0], &Q->X);
1634
98.8k
    MPI_ECP_MUL(&tmp[1], &tmp[1], &Q->Y);
1635
98.8k
    MPI_ECP_SUB(&tmp[0], &tmp[0], &P->X);
1636
98.8k
    MPI_ECP_SUB(&tmp[1], &tmp[1], &P->Y);
1637
1638
    /* Special cases (2) and (3) */
1639
98.8k
    if (MPI_ECP_CMP_INT(&tmp[0], 0) == 0) {
1640
13
        if (MPI_ECP_CMP_INT(&tmp[1], 0) == 0) {
1641
13
            ret = ecp_double_jac(grp, R, P, tmp);
1642
13
            goto cleanup;
1643
13
        } else {
1644
0
            ret = mbedtls_ecp_set_zero(R);
1645
0
            goto cleanup;
1646
0
        }
1647
13
    }
1648
1649
    /* {P,Q}->Z no longer used, so OK to write to Z even if there's aliasing. */
1650
98.8k
    MPI_ECP_MUL(Z,        &P->Z,    &tmp[0]);
1651
98.8k
    MPI_ECP_SQR(&tmp[2],  &tmp[0]);
1652
98.8k
    MPI_ECP_MUL(&tmp[3],  &tmp[2],  &tmp[0]);
1653
98.8k
    MPI_ECP_MUL(&tmp[2],  &tmp[2],  &P->X);
1654
1655
98.8k
    MPI_ECP_MOV(&tmp[0], &tmp[2]);
1656
98.8k
    MPI_ECP_SHIFT_L(&tmp[0], 1);
1657
1658
    /* {P,Q}->X no longer used, so OK to write to X even if there's aliasing. */
1659
98.8k
    MPI_ECP_SQR(X,        &tmp[1]);
1660
98.8k
    MPI_ECP_SUB(X,        X,        &tmp[0]);
1661
98.8k
    MPI_ECP_SUB(X,        X,        &tmp[3]);
1662
98.8k
    MPI_ECP_SUB(&tmp[2],  &tmp[2],  X);
1663
98.8k
    MPI_ECP_MUL(&tmp[2],  &tmp[2],  &tmp[1]);
1664
98.8k
    MPI_ECP_MUL(&tmp[3],  &tmp[3],  &P->Y);
1665
    /* {P,Q}->Y no longer used, so OK to write to Y even if there's aliasing. */
1666
98.8k
    MPI_ECP_SUB(Y,     &tmp[2],     &tmp[3]);
1667
1668
98.8k
cleanup:
1669
1670
98.8k
    return ret;
1671
98.8k
#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_ADD_MIXED_ALT) */
1672
98.8k
}
1673
1674
/*
1675
 * Randomize jacobian coordinates:
1676
 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
1677
 * This is sort of the reverse operation of ecp_normalize_jac().
1678
 *
1679
 * This countermeasure was first suggested in [2].
1680
 */
1681
static int ecp_randomize_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
1682
                             int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
1683
1.92k
{
1684
#if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
1685
    if (mbedtls_internal_ecp_grp_capable(grp)) {
1686
        return mbedtls_internal_ecp_randomize_jac(grp, pt, f_rng, p_rng);
1687
    }
1688
#endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */
1689
1690
#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
1691
    return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
1692
#else
1693
1.92k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1694
1.92k
    mbedtls_mpi l;
1695
1696
1.92k
    mbedtls_mpi_init(&l);
1697
1698
    /* Generate l such that 1 < l < p */
1699
1.92k
    MPI_ECP_RAND(&l);
1700
1701
    /* Z' = l * Z */
1702
1.56k
    MPI_ECP_MUL(&pt->Z,   &pt->Z,     &l);
1703
1704
    /* Y' = l * Y */
1705
1.56k
    MPI_ECP_MUL(&pt->Y,   &pt->Y,     &l);
1706
1707
    /* X' = l^2 * X */
1708
1.56k
    MPI_ECP_SQR(&l,       &l);
1709
1.56k
    MPI_ECP_MUL(&pt->X,   &pt->X,     &l);
1710
1711
    /* Y'' = l^2 * Y' = l^3 * Y */
1712
1.56k
    MPI_ECP_MUL(&pt->Y,   &pt->Y,     &l);
1713
1714
1.92k
cleanup:
1715
1.92k
    mbedtls_mpi_free(&l);
1716
1717
1.92k
    if (ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
1718
0
        ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
1719
0
    }
1720
1.92k
    return ret;
1721
1.56k
#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) */
1722
1.56k
}
1723
1724
/*
1725
 * Check and define parameters used by the comb method (see below for details)
1726
 */
1727
#if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7
1728
#error "MBEDTLS_ECP_WINDOW_SIZE out of bounds"
1729
#endif
1730
1731
/* d = ceil( n / w ) */
1732
#define COMB_MAX_D      (MBEDTLS_ECP_MAX_BITS + 1) / 2
1733
1734
/* number of precomputed points */
1735
#define COMB_MAX_PRE    (1 << (MBEDTLS_ECP_WINDOW_SIZE - 1))
1736
1737
/*
1738
 * Compute the representation of m that will be used with our comb method.
1739
 *
1740
 * The basic comb method is described in GECC 3.44 for example. We use a
1741
 * modified version that provides resistance to SPA by avoiding zero
1742
 * digits in the representation as in [3]. We modify the method further by
1743
 * requiring that all K_i be odd, which has the small cost that our
1744
 * representation uses one more K_i, due to carries, but saves on the size of
1745
 * the precomputed table.
1746
 *
1747
 * Summary of the comb method and its modifications:
1748
 *
1749
 * - The goal is to compute m*P for some w*d-bit integer m.
1750
 *
1751
 * - The basic comb method splits m into the w-bit integers
1752
 *   x[0] .. x[d-1] where x[i] consists of the bits in m whose
1753
 *   index has residue i modulo d, and computes m * P as
1754
 *   S[x[0]] + 2 * S[x[1]] + .. + 2^(d-1) S[x[d-1]], where
1755
 *   S[i_{w-1} .. i_0] := i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + i_0 P.
1756
 *
1757
 * - If it happens that, say, x[i+1]=0 (=> S[x[i+1]]=0), one can replace the sum by
1758
 *    .. + 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]] ..,
1759
 *   thereby successively converting it into a form where all summands
1760
 *   are nonzero, at the cost of negative summands. This is the basic idea of [3].
1761
 *
1762
 * - More generally, even if x[i+1] != 0, we can first transform the sum as
1763
 *   .. - 2^i S[x[i]] + 2^{i+1} ( S[x[i]] + S[x[i+1]] ) + 2^{i+2} S[x[i+2]] ..,
1764
 *   and then replace S[x[i]] + S[x[i+1]] = S[x[i] ^ x[i+1]] + 2 S[x[i] & x[i+1]].
1765
 *   Performing and iterating this procedure for those x[i] that are even
1766
 *   (keeping track of carry), we can transform the original sum into one of the form
1767
 *   S[x'[0]] +- 2 S[x'[1]] +- .. +- 2^{d-1} S[x'[d-1]] + 2^d S[x'[d]]
1768
 *   with all x'[i] odd. It is therefore only necessary to know S at odd indices,
1769
 *   which is why we are only computing half of it in the first place in
1770
 *   ecp_precompute_comb and accessing it with index abs(i) / 2 in ecp_select_comb.
1771
 *
1772
 * - For the sake of compactness, only the seven low-order bits of x[i]
1773
 *   are used to represent its absolute value (K_i in the paper), and the msb
1774
 *   of x[i] encodes the sign (s_i in the paper): it is set if and only if
1775
 *   if s_i == -1;
1776
 *
1777
 * Calling conventions:
1778
 * - x is an array of size d + 1
1779
 * - w is the size, ie number of teeth, of the comb, and must be between
1780
 *   2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE)
1781
 * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d
1782
 *   (the result will be incorrect if these assumptions are not satisfied)
1783
 */
1784
static void ecp_comb_recode_core(unsigned char x[], size_t d,
1785
                                 unsigned char w, const mbedtls_mpi *m)
1786
1.72k
{
1787
1.72k
    size_t i, j;
1788
1.72k
    unsigned char c, cc, adjust;
1789
1790
1.72k
    memset(x, 0, d+1);
1791
1792
    /* First get the classical comb values (except for x_d = 0) */
1793
111k
    for (i = 0; i < d; i++) {
1794
654k
        for (j = 0; j < w; j++) {
1795
544k
            x[i] |= mbedtls_mpi_get_bit(m, i + d * j) << j;
1796
544k
        }
1797
110k
    }
1798
1799
    /* Now make sure x_1 .. x_d are odd */
1800
1.72k
    c = 0;
1801
111k
    for (i = 1; i <= d; i++) {
1802
        /* Add carry and update it */
1803
110k
        cc   = x[i] & c;
1804
110k
        x[i] = x[i] ^ c;
1805
110k
        c = cc;
1806
1807
        /* Adjust if needed, avoiding branches */
1808
110k
        adjust = 1 - (x[i] & 0x01);
1809
110k
        c   |= x[i] & (x[i-1] * adjust);
1810
110k
        x[i] = x[i] ^ (x[i-1] * adjust);
1811
110k
        x[i-1] |= adjust << 7;
1812
110k
    }
1813
1.72k
}
1814
1815
/*
1816
 * Precompute points for the adapted comb method
1817
 *
1818
 * Assumption: T must be able to hold 2^{w - 1} elements.
1819
 *
1820
 * Operation: If i = i_{w-1} ... i_1 is the binary representation of i,
1821
 *            sets T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P.
1822
 *
1823
 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)
1824
 *
1825
 * Note: Even comb values (those where P would be omitted from the
1826
 *       sum defining T[i] above) are not needed in our adaption
1827
 *       the comb method. See ecp_comb_recode_core().
1828
 *
1829
 * This function currently works in four steps:
1830
 * (1) [dbl]      Computation of intermediate T[i] for 2-power values of i
1831
 * (2) [norm_dbl] Normalization of coordinates of these T[i]
1832
 * (3) [add]      Computation of all T[i]
1833
 * (4) [norm_add] Normalization of all T[i]
1834
 *
1835
 * Step 1 can be interrupted but not the others; together with the final
1836
 * coordinate normalization they are the largest steps done at once, depending
1837
 * on the window size. Here are operation counts for P-256:
1838
 *
1839
 * step     (2)     (3)     (4)
1840
 * w = 5    142     165     208
1841
 * w = 4    136      77     160
1842
 * w = 3    130      33     136
1843
 * w = 2    124      11     124
1844
 *
1845
 * So if ECC operations are blocking for too long even with a low max_ops
1846
 * value, it's useful to set MBEDTLS_ECP_WINDOW_SIZE to a lower value in order
1847
 * to minimize maximum blocking time.
1848
 */
1849
static int ecp_precompute_comb(const mbedtls_ecp_group *grp,
1850
                               mbedtls_ecp_point T[], const mbedtls_ecp_point *P,
1851
                               unsigned char w, size_t d,
1852
                               mbedtls_ecp_restart_ctx *rs_ctx)
1853
513
{
1854
513
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1855
513
    unsigned char i;
1856
513
    size_t j = 0;
1857
513
    const unsigned char T_size = 1U << (w - 1);
1858
513
    mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1] = { NULL };
1859
1860
513
    mbedtls_mpi tmp[4];
1861
1862
513
    mpi_init_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi));
1863
1864
#if defined(MBEDTLS_ECP_RESTARTABLE)
1865
    if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
1866
        if (rs_ctx->rsm->state == ecp_rsm_pre_dbl) {
1867
            goto dbl;
1868
        }
1869
        if (rs_ctx->rsm->state == ecp_rsm_pre_norm_dbl) {
1870
            goto norm_dbl;
1871
        }
1872
        if (rs_ctx->rsm->state == ecp_rsm_pre_add) {
1873
            goto add;
1874
        }
1875
        if (rs_ctx->rsm->state == ecp_rsm_pre_norm_add) {
1876
            goto norm_add;
1877
        }
1878
    }
1879
#else
1880
513
    (void) rs_ctx;
1881
513
#endif
1882
1883
#if defined(MBEDTLS_ECP_RESTARTABLE)
1884
    if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
1885
        rs_ctx->rsm->state = ecp_rsm_pre_dbl;
1886
1887
        /* initial state for the loop */
1888
        rs_ctx->rsm->i = 0;
1889
    }
1890
1891
dbl:
1892
#endif
1893
    /*
1894
     * Set T[0] = P and
1895
     * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value)
1896
     */
1897
513
    MBEDTLS_MPI_CHK(mbedtls_ecp_copy(&T[0], P));
1898
1899
#if defined(MBEDTLS_ECP_RESTARTABLE)
1900
    if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0) {
1901
        j = rs_ctx->rsm->i;
1902
    } else
1903
#endif
1904
513
    j = 0;
1905
1906
120k
    for (; j < d * (w - 1); j++) {
1907
119k
        MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_DBL);
1908
1909
119k
        i = 1U << (j / d);
1910
119k
        cur = T + i;
1911
1912
119k
        if (j % d == 0) {
1913
1.53k
            MBEDTLS_MPI_CHK(mbedtls_ecp_copy(cur, T + (i >> 1)));
1914
1.53k
        }
1915
1916
119k
        MBEDTLS_MPI_CHK(ecp_double_jac(grp, cur, cur, tmp));
1917
119k
    }
1918
1919
#if defined(MBEDTLS_ECP_RESTARTABLE)
1920
    if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
1921
        rs_ctx->rsm->state = ecp_rsm_pre_norm_dbl;
1922
    }
1923
1924
norm_dbl:
1925
#endif
1926
    /*
1927
     * Normalize current elements in T to allow them to be used in
1928
     * ecp_add_mixed() below, which requires one normalized input.
1929
     *
1930
     * As T has holes, use an auxiliary array of pointers to elements in T.
1931
     *
1932
     */
1933
513
    j = 0;
1934
2.05k
    for (i = 1; i < T_size; i <<= 1) {
1935
1.53k
        TT[j++] = T + i;
1936
1.53k
    }
1937
1938
513
    MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV + 6 * j - 2);
1939
1940
513
    MBEDTLS_MPI_CHK(ecp_normalize_jac_many(grp, TT, j));
1941
1942
#if defined(MBEDTLS_ECP_RESTARTABLE)
1943
    if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
1944
        rs_ctx->rsm->state = ecp_rsm_pre_add;
1945
    }
1946
1947
add:
1948
#endif
1949
    /*
1950
     * Compute the remaining ones using the minimal number of additions
1951
     * Be careful to update T[2^l] only after using it!
1952
     */
1953
513
    MBEDTLS_ECP_BUDGET((T_size - 1) * MBEDTLS_ECP_OPS_ADD);
1954
1955
2.05k
    for (i = 1; i < T_size; i <<= 1) {
1956
1.53k
        j = i;
1957
5.13k
        while (j--) {
1958
3.59k
            MBEDTLS_MPI_CHK(ecp_add_mixed(grp, &T[i + j], &T[j], &T[i], tmp));
1959
3.59k
        }
1960
1.53k
    }
1961
1962
#if defined(MBEDTLS_ECP_RESTARTABLE)
1963
    if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
1964
        rs_ctx->rsm->state = ecp_rsm_pre_norm_add;
1965
    }
1966
1967
norm_add:
1968
#endif
1969
    /*
1970
     * Normalize final elements in T. Even though there are no holes now, we
1971
     * still need the auxiliary array for homogeneity with the previous
1972
     * call. Also, skip T[0] which is already normalised, being a copy of P.
1973
     */
1974
4.10k
    for (j = 0; j + 1 < T_size; j++) {
1975
3.59k
        TT[j] = T + j + 1;
1976
3.59k
    }
1977
1978
513
    MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV + 6 * j - 2);
1979
1980
513
    MBEDTLS_MPI_CHK(ecp_normalize_jac_many(grp, TT, j));
1981
1982
    /* Free Z coordinate (=1 after normalization) to save RAM.
1983
     * This makes T[i] invalid as mbedtls_ecp_points, but this is OK
1984
     * since from this point onwards, they are only accessed indirectly
1985
     * via the getter function ecp_select_comb() which does set the
1986
     * target's Z coordinate to 1. */
1987
4.61k
    for (i = 0; i < T_size; i++) {
1988
4.10k
        mbedtls_mpi_free(&T[i].Z);
1989
4.10k
    }
1990
1991
513
cleanup:
1992
1993
513
    mpi_free_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi));
1994
1995
#if defined(MBEDTLS_ECP_RESTARTABLE)
1996
    if (rs_ctx != NULL && rs_ctx->rsm != NULL &&
1997
        ret == MBEDTLS_ERR_ECP_IN_PROGRESS) {
1998
        if (rs_ctx->rsm->state == ecp_rsm_pre_dbl) {
1999
            rs_ctx->rsm->i = j;
2000
        }
2001
    }
2002
#endif
2003
2004
513
    return ret;
2005
513
}
2006
2007
/*
2008
 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ]
2009
 *
2010
 * See ecp_comb_recode_core() for background
2011
 */
2012
static int ecp_select_comb(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2013
                           const mbedtls_ecp_point T[], unsigned char T_size,
2014
                           unsigned char i)
2015
96.6k
{
2016
96.6k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2017
96.6k
    unsigned char ii, j;
2018
2019
    /* Ignore the "sign" bit and scale down */
2020
96.6k
    ii =  (i & 0x7Fu) >> 1;
2021
2022
    /* Read the whole table to thwart cache-based timing attacks */
2023
1.78M
    for (j = 0; j < T_size; j++) {
2024
1.69M
        MPI_ECP_COND_ASSIGN(&R->X, &T[j].X, j == ii);
2025
1.69M
        MPI_ECP_COND_ASSIGN(&R->Y, &T[j].Y, j == ii);
2026
1.69M
    }
2027
2028
    /* Safely invert result if i is "negative" */
2029
96.6k
    MBEDTLS_MPI_CHK(ecp_safe_invert_jac(grp, R, i >> 7));
2030
2031
96.6k
    MPI_ECP_LSET(&R->Z, 1);
2032
2033
96.6k
cleanup:
2034
96.6k
    return ret;
2035
96.6k
}
2036
2037
/*
2038
 * Core multiplication algorithm for the (modified) comb method.
2039
 * This part is actually common with the basic comb method (GECC 3.44)
2040
 *
2041
 * Cost: d A + d D + 1 R
2042
 */
2043
static int ecp_mul_comb_core(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2044
                             const mbedtls_ecp_point T[], unsigned char T_size,
2045
                             const unsigned char x[], size_t d,
2046
                             int (*f_rng)(void *, unsigned char *, size_t),
2047
                             void *p_rng,
2048
                             mbedtls_ecp_restart_ctx *rs_ctx)
2049
1.72k
{
2050
1.72k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2051
1.72k
    mbedtls_ecp_point Txi;
2052
1.72k
    mbedtls_mpi tmp[4];
2053
1.72k
    size_t i;
2054
2055
1.72k
    mbedtls_ecp_point_init(&Txi);
2056
1.72k
    mpi_init_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi));
2057
2058
1.72k
#if !defined(MBEDTLS_ECP_RESTARTABLE)
2059
1.72k
    (void) rs_ctx;
2060
1.72k
#endif
2061
2062
#if defined(MBEDTLS_ECP_RESTARTABLE)
2063
    if (rs_ctx != NULL && rs_ctx->rsm != NULL &&
2064
        rs_ctx->rsm->state != ecp_rsm_comb_core) {
2065
        rs_ctx->rsm->i = 0;
2066
        rs_ctx->rsm->state = ecp_rsm_comb_core;
2067
    }
2068
2069
    /* new 'if' instead of nested for the sake of the 'else' branch */
2070
    if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0) {
2071
        /* restore current index (R already pointing to rs_ctx->rsm->R) */
2072
        i = rs_ctx->rsm->i;
2073
    } else
2074
#endif
2075
1.72k
    {
2076
        /* Start with a non-zero point and randomize its coordinates */
2077
1.72k
        i = d;
2078
1.72k
        MBEDTLS_MPI_CHK(ecp_select_comb(grp, R, T, T_size, x[i]));
2079
1.72k
        if (f_rng != 0) {
2080
1.07k
            MBEDTLS_MPI_CHK(ecp_randomize_jac(grp, R, f_rng, p_rng));
2081
1.07k
        }
2082
1.72k
    }
2083
2084
96.4k
    while (i != 0) {
2085
94.9k
        MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD);
2086
94.9k
        --i;
2087
2088
94.9k
        MBEDTLS_MPI_CHK(ecp_double_jac(grp, R, R, tmp));
2089
94.9k
        MBEDTLS_MPI_CHK(ecp_select_comb(grp, &Txi, T, T_size, x[i]));
2090
94.9k
        MBEDTLS_MPI_CHK(ecp_add_mixed(grp, R, R, &Txi, tmp));
2091
94.9k
    }
2092
2093
1.72k
cleanup:
2094
2095
1.72k
    mbedtls_ecp_point_free(&Txi);
2096
1.72k
    mpi_free_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi));
2097
2098
#if defined(MBEDTLS_ECP_RESTARTABLE)
2099
    if (rs_ctx != NULL && rs_ctx->rsm != NULL &&
2100
        ret == MBEDTLS_ERR_ECP_IN_PROGRESS) {
2101
        rs_ctx->rsm->i = i;
2102
        /* no need to save R, already pointing to rs_ctx->rsm->R */
2103
    }
2104
#endif
2105
2106
1.72k
    return ret;
2107
1.51k
}
2108
2109
/*
2110
 * Recode the scalar to get constant-time comb multiplication
2111
 *
2112
 * As the actual scalar recoding needs an odd scalar as a starting point,
2113
 * this wrapper ensures that by replacing m by N - m if necessary, and
2114
 * informs the caller that the result of multiplication will be negated.
2115
 *
2116
 * This works because we only support large prime order for Short Weierstrass
2117
 * curves, so N is always odd hence either m or N - m is.
2118
 *
2119
 * See ecp_comb_recode_core() for background.
2120
 */
2121
static int ecp_comb_recode_scalar(const mbedtls_ecp_group *grp,
2122
                                  const mbedtls_mpi *m,
2123
                                  unsigned char k[COMB_MAX_D + 1],
2124
                                  size_t d,
2125
                                  unsigned char w,
2126
                                  unsigned char *parity_trick)
2127
1.72k
{
2128
1.72k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2129
1.72k
    mbedtls_mpi M, mm;
2130
2131
1.72k
    mbedtls_mpi_init(&M);
2132
1.72k
    mbedtls_mpi_init(&mm);
2133
2134
    /* N is always odd (see above), just make extra sure */
2135
1.72k
    if (mbedtls_mpi_get_bit(&grp->N, 0) != 1) {
2136
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
2137
0
    }
2138
2139
    /* do we need the parity trick? */
2140
1.72k
    *parity_trick = (mbedtls_mpi_get_bit(m, 0) == 0);
2141
2142
    /* execute parity fix in constant time */
2143
1.72k
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&M, m));
2144
1.72k
    MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&mm, &grp->N, m));
2145
1.72k
    MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(&M, &mm, *parity_trick));
2146
2147
    /* actual scalar recoding */
2148
1.72k
    ecp_comb_recode_core(k, d, w, &M);
2149
2150
1.72k
cleanup:
2151
1.72k
    mbedtls_mpi_free(&mm);
2152
1.72k
    mbedtls_mpi_free(&M);
2153
2154
1.72k
    return ret;
2155
1.72k
}
2156
2157
/*
2158
 * Perform comb multiplication (for short Weierstrass curves)
2159
 * once the auxiliary table has been pre-computed.
2160
 *
2161
 * Scalar recoding may use a parity trick that makes us compute -m * P,
2162
 * if that is the case we'll need to recover m * P at the end.
2163
 */
2164
static int ecp_mul_comb_after_precomp(const mbedtls_ecp_group *grp,
2165
                                      mbedtls_ecp_point *R,
2166
                                      const mbedtls_mpi *m,
2167
                                      const mbedtls_ecp_point *T,
2168
                                      unsigned char T_size,
2169
                                      unsigned char w,
2170
                                      size_t d,
2171
                                      int (*f_rng)(void *, unsigned char *, size_t),
2172
                                      void *p_rng,
2173
                                      mbedtls_ecp_restart_ctx *rs_ctx)
2174
1.72k
{
2175
1.72k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2176
1.72k
    unsigned char parity_trick;
2177
1.72k
    unsigned char k[COMB_MAX_D + 1];
2178
1.72k
    mbedtls_ecp_point *RR = R;
2179
2180
#if defined(MBEDTLS_ECP_RESTARTABLE)
2181
    if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
2182
        RR = &rs_ctx->rsm->R;
2183
2184
        if (rs_ctx->rsm->state == ecp_rsm_final_norm) {
2185
            goto final_norm;
2186
        }
2187
    }
2188
#endif
2189
2190
1.72k
    MBEDTLS_MPI_CHK(ecp_comb_recode_scalar(grp, m, k, d, w,
2191
1.72k
                                           &parity_trick));
2192
1.72k
    MBEDTLS_MPI_CHK(ecp_mul_comb_core(grp, RR, T, T_size, k, d,
2193
1.72k
                                      f_rng, p_rng, rs_ctx));
2194
1.51k
    MBEDTLS_MPI_CHK(ecp_safe_invert_jac(grp, RR, parity_trick));
2195
2196
#if defined(MBEDTLS_ECP_RESTARTABLE)
2197
    if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
2198
        rs_ctx->rsm->state = ecp_rsm_final_norm;
2199
    }
2200
2201
final_norm:
2202
    MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV);
2203
#endif
2204
    /*
2205
     * Knowledge of the jacobian coordinates may leak the last few bits of the
2206
     * scalar [1], and since our MPI implementation isn't constant-flow,
2207
     * inversion (used for coordinate normalization) may leak the full value
2208
     * of its input via side-channels [2].
2209
     *
2210
     * [1] https://eprint.iacr.org/2003/191
2211
     * [2] https://eprint.iacr.org/2020/055
2212
     *
2213
     * Avoid the leak by randomizing coordinates before we normalize them.
2214
     */
2215
1.51k
    if (f_rng != 0) {
2216
856
        MBEDTLS_MPI_CHK(ecp_randomize_jac(grp, RR, f_rng, p_rng));
2217
856
    }
2218
2219
1.36k
    MBEDTLS_MPI_CHK(ecp_normalize_jac(grp, RR));
2220
2221
#if defined(MBEDTLS_ECP_RESTARTABLE)
2222
    if (rs_ctx != NULL && rs_ctx->rsm != NULL) {
2223
        MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, RR));
2224
    }
2225
#endif
2226
2227
1.72k
cleanup:
2228
1.72k
    return ret;
2229
1.36k
}
2230
2231
/*
2232
 * Pick window size based on curve size and whether we optimize for base point
2233
 */
2234
static unsigned char ecp_pick_window_size(const mbedtls_ecp_group *grp,
2235
                                          unsigned char p_eq_g)
2236
1.72k
{
2237
1.72k
    unsigned char w;
2238
2239
    /*
2240
     * Minimize the number of multiplications, that is minimize
2241
     * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
2242
     * (see costs of the various parts, with 1S = 1M)
2243
     */
2244
1.72k
    w = grp->nbits >= 384 ? 5 : 4;
2245
2246
    /*
2247
     * If P == G, pre-compute a bit more, since this may be re-used later.
2248
     * Just adding one avoids upping the cost of the first mul too much,
2249
     * and the memory cost too.
2250
     */
2251
1.72k
    if (p_eq_g) {
2252
1.21k
        w++;
2253
1.21k
    }
2254
2255
    /*
2256
     * If static comb table may not be used (!p_eq_g) or static comb table does
2257
     * not exists, make sure w is within bounds.
2258
     * (The last test is useful only for very small curves in the test suite.)
2259
     *
2260
     * The user reduces MBEDTLS_ECP_WINDOW_SIZE does not changes the size of
2261
     * static comb table, because the size of static comb table is fixed when
2262
     * it is generated.
2263
     */
2264
1.72k
#if (MBEDTLS_ECP_WINDOW_SIZE < 6)
2265
1.72k
    if ((!p_eq_g || !ecp_group_is_static_comb_table(grp)) && w > MBEDTLS_ECP_WINDOW_SIZE) {
2266
189
        w = MBEDTLS_ECP_WINDOW_SIZE;
2267
189
    }
2268
1.72k
#endif
2269
1.72k
    if (w >= grp->nbits) {
2270
0
        w = 2;
2271
0
    }
2272
2273
1.72k
    return w;
2274
1.72k
}
2275
2276
/*
2277
 * Multiplication using the comb method - for curves in short Weierstrass form
2278
 *
2279
 * This function is mainly responsible for administrative work:
2280
 * - managing the restart context if enabled
2281
 * - managing the table of precomputed points (passed between the below two
2282
 *   functions): allocation, computation, ownership transfer, freeing.
2283
 *
2284
 * It delegates the actual arithmetic work to:
2285
 *      ecp_precompute_comb() and ecp_mul_comb_with_precomp()
2286
 *
2287
 * See comments on ecp_comb_recode_core() regarding the computation strategy.
2288
 */
2289
static int ecp_mul_comb(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2290
                        const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2291
                        int (*f_rng)(void *, unsigned char *, size_t),
2292
                        void *p_rng,
2293
                        mbedtls_ecp_restart_ctx *rs_ctx)
2294
1.72k
{
2295
1.72k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2296
1.72k
    unsigned char w, p_eq_g, i;
2297
1.72k
    size_t d;
2298
1.72k
    unsigned char T_size = 0, T_ok = 0;
2299
1.72k
    mbedtls_ecp_point *T = NULL;
2300
2301
1.72k
    ECP_RS_ENTER(rsm);
2302
2303
    /* Is P the base point ? */
2304
1.72k
#if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1
2305
1.72k
    p_eq_g = (MPI_ECP_CMP(&P->Y, &grp->G.Y) == 0 &&
2306
1.72k
              MPI_ECP_CMP(&P->X, &grp->G.X) == 0);
2307
#else
2308
    p_eq_g = 0;
2309
#endif
2310
2311
    /* Pick window size and deduce related sizes */
2312
1.72k
    w = ecp_pick_window_size(grp, p_eq_g);
2313
1.72k
    T_size = 1U << (w - 1);
2314
1.72k
    d = (grp->nbits + w - 1) / w;
2315
2316
    /* Pre-computed table: do we have it already for the base point? */
2317
1.72k
    if (p_eq_g && grp->T != NULL) {
2318
        /* second pointer to the same table, will be deleted on exit */
2319
1.21k
        T = grp->T;
2320
1.21k
        T_ok = 1;
2321
1.21k
    } else
2322
#if defined(MBEDTLS_ECP_RESTARTABLE)
2323
    /* Pre-computed table: do we have one in progress? complete? */
2324
    if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->T != NULL) {
2325
        /* transfer ownership of T from rsm to local function */
2326
        T = rs_ctx->rsm->T;
2327
        rs_ctx->rsm->T = NULL;
2328
        rs_ctx->rsm->T_size = 0;
2329
2330
        /* This effectively jumps to the call to mul_comb_after_precomp() */
2331
        T_ok = rs_ctx->rsm->state >= ecp_rsm_comb_core;
2332
    } else
2333
#endif
2334
    /* Allocate table if we didn't have any */
2335
513
    {
2336
513
        T = mbedtls_calloc(T_size, sizeof(mbedtls_ecp_point));
2337
513
        if (T == NULL) {
2338
0
            ret = MBEDTLS_ERR_ECP_ALLOC_FAILED;
2339
0
            goto cleanup;
2340
0
        }
2341
2342
4.61k
        for (i = 0; i < T_size; i++) {
2343
4.10k
            mbedtls_ecp_point_init(&T[i]);
2344
4.10k
        }
2345
2346
513
        T_ok = 0;
2347
513
    }
2348
2349
    /* Compute table (or finish computing it) if not done already */
2350
1.72k
    if (!T_ok) {
2351
513
        MBEDTLS_MPI_CHK(ecp_precompute_comb(grp, T, P, w, d, rs_ctx));
2352
2353
513
        if (p_eq_g) {
2354
            /* almost transfer ownership of T to the group, but keep a copy of
2355
             * the pointer to use for calling the next function more easily */
2356
0
            grp->T = T;
2357
0
            grp->T_size = T_size;
2358
0
        }
2359
513
    }
2360
2361
    /* Actual comb multiplication using precomputed points */
2362
1.72k
    MBEDTLS_MPI_CHK(ecp_mul_comb_after_precomp(grp, R, m,
2363
1.72k
                                               T, T_size, w, d,
2364
1.72k
                                               f_rng, p_rng, rs_ctx));
2365
2366
1.72k
cleanup:
2367
2368
    /* does T belong to the group? */
2369
1.72k
    if (T == grp->T) {
2370
1.21k
        T = NULL;
2371
1.21k
    }
2372
2373
    /* does T belong to the restart context? */
2374
#if defined(MBEDTLS_ECP_RESTARTABLE)
2375
    if (rs_ctx != NULL && rs_ctx->rsm != NULL && ret == MBEDTLS_ERR_ECP_IN_PROGRESS && T != NULL) {
2376
        /* transfer ownership of T from local function to rsm */
2377
        rs_ctx->rsm->T_size = T_size;
2378
        rs_ctx->rsm->T = T;
2379
        T = NULL;
2380
    }
2381
#endif
2382
2383
    /* did T belong to us? then let's destroy it! */
2384
1.72k
    if (T != NULL) {
2385
4.61k
        for (i = 0; i < T_size; i++) {
2386
4.10k
            mbedtls_ecp_point_free(&T[i]);
2387
4.10k
        }
2388
513
        mbedtls_free(T);
2389
513
    }
2390
2391
    /* prevent caller from using invalid value */
2392
1.72k
    int should_free_R = (ret != 0);
2393
#if defined(MBEDTLS_ECP_RESTARTABLE)
2394
    /* don't free R while in progress in case R == P */
2395
    if (ret == MBEDTLS_ERR_ECP_IN_PROGRESS) {
2396
        should_free_R = 0;
2397
    }
2398
#endif
2399
1.72k
    if (should_free_R) {
2400
359
        mbedtls_ecp_point_free(R);
2401
359
    }
2402
2403
1.72k
    ECP_RS_LEAVE(rsm);
2404
2405
1.72k
    return ret;
2406
1.72k
}
2407
2408
#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
2409
2410
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
2411
/*
2412
 * For Montgomery curves, we do all the internal arithmetic in projective
2413
 * coordinates. Import/export of points uses only the x coordinates, which is
2414
 * internally represented as X / Z.
2415
 *
2416
 * For scalar multiplication, we'll use a Montgomery ladder.
2417
 */
2418
2419
/*
2420
 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
2421
 * Cost: 1M + 1I
2422
 */
2423
static int ecp_normalize_mxz(const mbedtls_ecp_group *grp, mbedtls_ecp_point *P)
2424
0
{
2425
#if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
2426
    if (mbedtls_internal_ecp_grp_capable(grp)) {
2427
        return mbedtls_internal_ecp_normalize_mxz(grp, P);
2428
    }
2429
#endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */
2430
2431
#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
2432
    return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
2433
#else
2434
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2435
0
    MPI_ECP_INV(&P->Z, &P->Z);
2436
0
    MPI_ECP_MUL(&P->X, &P->X, &P->Z);
2437
0
    MPI_ECP_LSET(&P->Z, 1);
2438
2439
0
cleanup:
2440
0
    return ret;
2441
0
#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) */
2442
0
}
2443
2444
/*
2445
 * Randomize projective x/z coordinates:
2446
 * (X, Z) -> (l X, l Z) for random l
2447
 * This is sort of the reverse operation of ecp_normalize_mxz().
2448
 *
2449
 * This countermeasure was first suggested in [2].
2450
 * Cost: 2M
2451
 */
2452
static int ecp_randomize_mxz(const mbedtls_ecp_group *grp, mbedtls_ecp_point *P,
2453
                             int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
2454
0
{
2455
#if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
2456
    if (mbedtls_internal_ecp_grp_capable(grp)) {
2457
        return mbedtls_internal_ecp_randomize_mxz(grp, P, f_rng, p_rng);
2458
    }
2459
#endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */
2460
2461
#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
2462
    return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
2463
#else
2464
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2465
0
    mbedtls_mpi l;
2466
0
    mbedtls_mpi_init(&l);
2467
2468
    /* Generate l such that 1 < l < p */
2469
0
    MPI_ECP_RAND(&l);
2470
2471
0
    MPI_ECP_MUL(&P->X, &P->X, &l);
2472
0
    MPI_ECP_MUL(&P->Z, &P->Z, &l);
2473
2474
0
cleanup:
2475
0
    mbedtls_mpi_free(&l);
2476
2477
0
    if (ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
2478
0
        ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
2479
0
    }
2480
0
    return ret;
2481
0
#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) */
2482
0
}
2483
2484
/*
2485
 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
2486
 * for Montgomery curves in x/z coordinates.
2487
 *
2488
 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
2489
 * with
2490
 * d =  X1
2491
 * P = (X2, Z2)
2492
 * Q = (X3, Z3)
2493
 * R = (X4, Z4)
2494
 * S = (X5, Z5)
2495
 * and eliminating temporary variables tO, ..., t4.
2496
 *
2497
 * Cost: 5M + 4S
2498
 */
2499
static int ecp_double_add_mxz(const mbedtls_ecp_group *grp,
2500
                              mbedtls_ecp_point *R, mbedtls_ecp_point *S,
2501
                              const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q,
2502
                              const mbedtls_mpi *d,
2503
                              mbedtls_mpi T[4])
2504
0
{
2505
#if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
2506
    if (mbedtls_internal_ecp_grp_capable(grp)) {
2507
        return mbedtls_internal_ecp_double_add_mxz(grp, R, S, P, Q, d);
2508
    }
2509
#endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */
2510
2511
#if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
2512
    return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
2513
#else
2514
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2515
2516
0
    MPI_ECP_ADD(&T[0], &P->X,   &P->Z);   /* Pp := PX + PZ                    */
2517
0
    MPI_ECP_SUB(&T[1], &P->X,   &P->Z);   /* Pm := PX - PZ                    */
2518
0
    MPI_ECP_ADD(&T[2], &Q->X,   &Q->Z);   /* Qp := QX + XZ                    */
2519
0
    MPI_ECP_SUB(&T[3], &Q->X,   &Q->Z);   /* Qm := QX - QZ                    */
2520
0
    MPI_ECP_MUL(&T[3], &T[3],   &T[0]);   /* Qm * Pp                          */
2521
0
    MPI_ECP_MUL(&T[2], &T[2],   &T[1]);   /* Qp * Pm                          */
2522
0
    MPI_ECP_SQR(&T[0], &T[0]);            /* Pp^2                             */
2523
0
    MPI_ECP_SQR(&T[1], &T[1]);            /* Pm^2                             */
2524
0
    MPI_ECP_MUL(&R->X, &T[0],   &T[1]);   /* Pp^2 * Pm^2                      */
2525
0
    MPI_ECP_SUB(&T[0], &T[0],   &T[1]);   /* Pp^2 - Pm^2                      */
2526
0
    MPI_ECP_MUL(&R->Z, &grp->A, &T[0]);   /* A * (Pp^2 - Pm^2)                */
2527
0
    MPI_ECP_ADD(&R->Z, &T[1],   &R->Z);   /* [ A * (Pp^2-Pm^2) ] + Pm^2       */
2528
0
    MPI_ECP_ADD(&S->X, &T[3],   &T[2]);   /* Qm*Pp + Qp*Pm                    */
2529
0
    MPI_ECP_SQR(&S->X, &S->X);            /* (Qm*Pp + Qp*Pm)^2                */
2530
0
    MPI_ECP_SUB(&S->Z, &T[3],   &T[2]);   /* Qm*Pp - Qp*Pm                    */
2531
0
    MPI_ECP_SQR(&S->Z, &S->Z);            /* (Qm*Pp - Qp*Pm)^2                */
2532
0
    MPI_ECP_MUL(&S->Z, d,       &S->Z);   /* d * ( Qm*Pp - Qp*Pm )^2          */
2533
0
    MPI_ECP_MUL(&R->Z, &T[0],   &R->Z);   /* [A*(Pp^2-Pm^2)+Pm^2]*(Pp^2-Pm^2) */
2534
2535
0
cleanup:
2536
2537
0
    return ret;
2538
0
#endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) */
2539
0
}
2540
2541
/*
2542
 * Multiplication with Montgomery ladder in x/z coordinates,
2543
 * for curves in Montgomery form
2544
 */
2545
static int ecp_mul_mxz(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2546
                       const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2547
                       int (*f_rng)(void *, unsigned char *, size_t),
2548
                       void *p_rng)
2549
0
{
2550
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2551
0
    size_t i;
2552
0
    unsigned char b;
2553
0
    mbedtls_ecp_point RP;
2554
0
    mbedtls_mpi PX;
2555
0
    mbedtls_mpi tmp[4];
2556
0
    mbedtls_ecp_point_init(&RP); mbedtls_mpi_init(&PX);
2557
2558
0
    mpi_init_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi));
2559
2560
0
    if (f_rng == NULL) {
2561
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
2562
0
    }
2563
2564
    /* Save PX and read from P before writing to R, in case P == R */
2565
0
    MPI_ECP_MOV(&PX, &P->X);
2566
0
    MBEDTLS_MPI_CHK(mbedtls_ecp_copy(&RP, P));
2567
2568
    /* Set R to zero in modified x/z coordinates */
2569
0
    MPI_ECP_LSET(&R->X, 1);
2570
0
    MPI_ECP_LSET(&R->Z, 0);
2571
0
    mbedtls_mpi_free(&R->Y);
2572
2573
    /* RP.X might be slightly larger than P, so reduce it */
2574
0
    MOD_ADD(&RP.X);
2575
2576
    /* Randomize coordinates of the starting point */
2577
0
    MBEDTLS_MPI_CHK(ecp_randomize_mxz(grp, &RP, f_rng, p_rng));
2578
2579
    /* Loop invariant: R = result so far, RP = R + P */
2580
0
    i = grp->nbits + 1; /* one past the (zero-based) required msb for private keys */
2581
0
    while (i-- > 0) {
2582
0
        b = mbedtls_mpi_get_bit(m, i);
2583
        /*
2584
         *  if (b) R = 2R + P else R = 2R,
2585
         * which is:
2586
         *  if (b) double_add( RP, R, RP, R )
2587
         *  else   double_add( R, RP, R, RP )
2588
         * but using safe conditional swaps to avoid leaks
2589
         */
2590
0
        MPI_ECP_COND_SWAP(&R->X, &RP.X, b);
2591
0
        MPI_ECP_COND_SWAP(&R->Z, &RP.Z, b);
2592
0
        MBEDTLS_MPI_CHK(ecp_double_add_mxz(grp, R, &RP, R, &RP, &PX, tmp));
2593
0
        MPI_ECP_COND_SWAP(&R->X, &RP.X, b);
2594
0
        MPI_ECP_COND_SWAP(&R->Z, &RP.Z, b);
2595
0
    }
2596
2597
    /*
2598
     * Knowledge of the projective coordinates may leak the last few bits of the
2599
     * scalar [1], and since our MPI implementation isn't constant-flow,
2600
     * inversion (used for coordinate normalization) may leak the full value
2601
     * of its input via side-channels [2].
2602
     *
2603
     * [1] https://eprint.iacr.org/2003/191
2604
     * [2] https://eprint.iacr.org/2020/055
2605
     *
2606
     * Avoid the leak by randomizing coordinates before we normalize them.
2607
     */
2608
0
    MBEDTLS_MPI_CHK(ecp_randomize_mxz(grp, R, f_rng, p_rng));
2609
0
    MBEDTLS_MPI_CHK(ecp_normalize_mxz(grp, R));
2610
2611
0
cleanup:
2612
0
    mbedtls_ecp_point_free(&RP); mbedtls_mpi_free(&PX);
2613
2614
0
    mpi_free_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi));
2615
0
    return ret;
2616
0
}
2617
2618
#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
2619
2620
/*
2621
 * Restartable multiplication R = m * P
2622
 *
2623
 * This internal function can be called without an RNG in case where we know
2624
 * the inputs are not sensitive.
2625
 */
2626
static int ecp_mul_restartable_internal(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2627
                                        const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2628
                                        int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,
2629
                                        mbedtls_ecp_restart_ctx *rs_ctx)
2630
2.12k
{
2631
2.12k
    int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
2632
#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2633
    char is_grp_capable = 0;
2634
#endif
2635
2636
#if defined(MBEDTLS_ECP_RESTARTABLE)
2637
    /* reset ops count for this call if top-level */
2638
    if (rs_ctx != NULL && rs_ctx->depth++ == 0) {
2639
        rs_ctx->ops_done = 0;
2640
    }
2641
#else
2642
2.12k
    (void) rs_ctx;
2643
2.12k
#endif
2644
2645
#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2646
    if ((is_grp_capable = mbedtls_internal_ecp_grp_capable(grp))) {
2647
        MBEDTLS_MPI_CHK(mbedtls_internal_ecp_init(grp));
2648
    }
2649
#endif /* MBEDTLS_ECP_INTERNAL_ALT */
2650
2651
2.12k
    int restarting = 0;
2652
#if defined(MBEDTLS_ECP_RESTARTABLE)
2653
    restarting = (rs_ctx != NULL && rs_ctx->rsm != NULL);
2654
#endif
2655
    /* skip argument check when restarting */
2656
2.12k
    if (!restarting) {
2657
        /* check_privkey is free */
2658
2.12k
        MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_CHK);
2659
2660
        /* Common sanity checks */
2661
2.12k
        MBEDTLS_MPI_CHK(mbedtls_ecp_check_privkey(grp, m));
2662
1.87k
        MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
2663
1.87k
    }
2664
2665
1.72k
    ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
2666
1.72k
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
2667
1.72k
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
2668
0
        MBEDTLS_MPI_CHK(ecp_mul_mxz(grp, R, m, P, f_rng, p_rng));
2669
0
    }
2670
1.72k
#endif
2671
1.72k
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
2672
1.72k
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
2673
1.72k
        MBEDTLS_MPI_CHK(ecp_mul_comb(grp, R, m, P, f_rng, p_rng, rs_ctx));
2674
1.72k
    }
2675
1.36k
#endif
2676
2677
2.12k
cleanup:
2678
2679
#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2680
    if (is_grp_capable) {
2681
        mbedtls_internal_ecp_free(grp);
2682
    }
2683
#endif /* MBEDTLS_ECP_INTERNAL_ALT */
2684
2685
#if defined(MBEDTLS_ECP_RESTARTABLE)
2686
    if (rs_ctx != NULL) {
2687
        rs_ctx->depth--;
2688
    }
2689
#endif
2690
2691
2.12k
    return ret;
2692
1.72k
}
2693
2694
/*
2695
 * Restartable multiplication R = m * P
2696
 */
2697
int mbedtls_ecp_mul_restartable(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2698
                                const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2699
                                int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,
2700
                                mbedtls_ecp_restart_ctx *rs_ctx)
2701
1.47k
{
2702
1.47k
    if (f_rng == NULL) {
2703
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
2704
0
    }
2705
2706
1.47k
    return ecp_mul_restartable_internal(grp, R, m, P, f_rng, p_rng, rs_ctx);
2707
1.47k
}
2708
2709
/*
2710
 * Multiplication R = m * P
2711
 */
2712
int mbedtls_ecp_mul(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2713
                    const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2714
                    int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
2715
1.32k
{
2716
1.32k
    return mbedtls_ecp_mul_restartable(grp, R, m, P, f_rng, p_rng, NULL);
2717
1.32k
}
2718
#endif /* MBEDTLS_ECP_C */
2719
2720
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
2721
/*
2722
 * Check that an affine point is valid as a public key,
2723
 * short weierstrass curves (SEC1 3.2.3.1)
2724
 */
2725
static int ecp_check_pubkey_sw(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt)
2726
2.87k
{
2727
2.87k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2728
2.87k
    mbedtls_mpi YY, RHS;
2729
2730
    /* pt coordinates must be normalized for our checks */
2731
2.87k
    if (mbedtls_mpi_cmp_int(&pt->X, 0) < 0 ||
2732
2.87k
        mbedtls_mpi_cmp_int(&pt->Y, 0) < 0 ||
2733
2.87k
        mbedtls_mpi_cmp_mpi(&pt->X, &grp->P) >= 0 ||
2734
2.87k
        mbedtls_mpi_cmp_mpi(&pt->Y, &grp->P) >= 0) {
2735
52
        return MBEDTLS_ERR_ECP_INVALID_KEY;
2736
52
    }
2737
2738
2.81k
    mbedtls_mpi_init(&YY); mbedtls_mpi_init(&RHS);
2739
2740
    /*
2741
     * YY = Y^2
2742
     * RHS = X^3 + A X + B
2743
     */
2744
2.81k
    MPI_ECP_SQR(&YY,  &pt->Y);
2745
2.81k
    MBEDTLS_MPI_CHK(ecp_sw_rhs(grp, &RHS, &pt->X));
2746
2747
2.81k
    if (MPI_ECP_CMP(&YY, &RHS) != 0) {
2748
487
        ret = MBEDTLS_ERR_ECP_INVALID_KEY;
2749
487
    }
2750
2751
2.81k
cleanup:
2752
2753
2.81k
    mbedtls_mpi_free(&YY); mbedtls_mpi_free(&RHS);
2754
2755
2.81k
    return ret;
2756
2.81k
}
2757
#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
2758
2759
#if defined(MBEDTLS_ECP_C)
2760
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
2761
/*
2762
 * R = m * P with shortcuts for m == 0, m == 1 and m == -1
2763
 * NOT constant-time - ONLY for short Weierstrass!
2764
 */
2765
static int mbedtls_ecp_mul_shortcuts(mbedtls_ecp_group *grp,
2766
                                     mbedtls_ecp_point *R,
2767
                                     const mbedtls_mpi *m,
2768
                                     const mbedtls_ecp_point *P,
2769
                                     mbedtls_ecp_restart_ctx *rs_ctx)
2770
1.37k
{
2771
1.37k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2772
1.37k
    mbedtls_mpi tmp;
2773
1.37k
    mbedtls_mpi_init(&tmp);
2774
2775
1.37k
    if (mbedtls_mpi_cmp_int(m, 0) == 0) {
2776
6
        MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
2777
6
        MBEDTLS_MPI_CHK(mbedtls_ecp_set_zero(R));
2778
1.37k
    } else if (mbedtls_mpi_cmp_int(m, 1) == 0) {
2779
716
        MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
2780
169
        MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, P));
2781
656
    } else if (mbedtls_mpi_cmp_int(m, -1) == 0) {
2782
0
        MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P));
2783
0
        MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, P));
2784
0
        MPI_ECP_NEG(&R->Y);
2785
656
    } else {
2786
656
        MBEDTLS_MPI_CHK(ecp_mul_restartable_internal(grp, R, m, P,
2787
656
                                                     NULL, NULL, rs_ctx));
2788
656
    }
2789
2790
1.37k
cleanup:
2791
1.37k
    mbedtls_mpi_free(&tmp);
2792
2793
1.37k
    return ret;
2794
1.37k
}
2795
2796
/*
2797
 * Restartable linear combination
2798
 * NOT constant-time
2799
 */
2800
int mbedtls_ecp_muladd_restartable(
2801
    mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2802
    const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2803
    const mbedtls_mpi *n, const mbedtls_ecp_point *Q,
2804
    mbedtls_ecp_restart_ctx *rs_ctx)
2805
905
{
2806
905
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2807
905
    mbedtls_ecp_point mP;
2808
905
    mbedtls_ecp_point *pmP = &mP;
2809
905
    mbedtls_ecp_point *pR = R;
2810
905
    mbedtls_mpi tmp[4];
2811
#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2812
    char is_grp_capable = 0;
2813
#endif
2814
905
    if (mbedtls_ecp_get_type(grp) != MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
2815
0
        return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
2816
0
    }
2817
2818
905
    mbedtls_ecp_point_init(&mP);
2819
905
    mpi_init_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi));
2820
2821
905
    ECP_RS_ENTER(ma);
2822
2823
#if defined(MBEDTLS_ECP_RESTARTABLE)
2824
    if (rs_ctx != NULL && rs_ctx->ma != NULL) {
2825
        /* redirect intermediate results to restart context */
2826
        pmP = &rs_ctx->ma->mP;
2827
        pR  = &rs_ctx->ma->R;
2828
2829
        /* jump to next operation */
2830
        if (rs_ctx->ma->state == ecp_rsma_mul2) {
2831
            goto mul2;
2832
        }
2833
        if (rs_ctx->ma->state == ecp_rsma_add) {
2834
            goto add;
2835
        }
2836
        if (rs_ctx->ma->state == ecp_rsma_norm) {
2837
            goto norm;
2838
        }
2839
    }
2840
#endif /* MBEDTLS_ECP_RESTARTABLE */
2841
2842
905
    MBEDTLS_MPI_CHK(mbedtls_ecp_mul_shortcuts(grp, pmP, m, P, rs_ctx));
2843
#if defined(MBEDTLS_ECP_RESTARTABLE)
2844
    if (rs_ctx != NULL && rs_ctx->ma != NULL) {
2845
        rs_ctx->ma->state = ecp_rsma_mul2;
2846
    }
2847
2848
mul2:
2849
#endif
2850
473
    MBEDTLS_MPI_CHK(mbedtls_ecp_mul_shortcuts(grp, pR,  n, Q, rs_ctx));
2851
2852
#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2853
    if ((is_grp_capable = mbedtls_internal_ecp_grp_capable(grp))) {
2854
        MBEDTLS_MPI_CHK(mbedtls_internal_ecp_init(grp));
2855
    }
2856
#endif /* MBEDTLS_ECP_INTERNAL_ALT */
2857
2858
#if defined(MBEDTLS_ECP_RESTARTABLE)
2859
    if (rs_ctx != NULL && rs_ctx->ma != NULL) {
2860
        rs_ctx->ma->state = ecp_rsma_add;
2861
    }
2862
2863
add:
2864
#endif
2865
358
    MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_ADD);
2866
358
    MBEDTLS_MPI_CHK(ecp_add_mixed(grp, pR, pmP, pR, tmp));
2867
#if defined(MBEDTLS_ECP_RESTARTABLE)
2868
    if (rs_ctx != NULL && rs_ctx->ma != NULL) {
2869
        rs_ctx->ma->state = ecp_rsma_norm;
2870
    }
2871
2872
norm:
2873
#endif
2874
358
    MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV);
2875
358
    MBEDTLS_MPI_CHK(ecp_normalize_jac(grp, pR));
2876
2877
#if defined(MBEDTLS_ECP_RESTARTABLE)
2878
    if (rs_ctx != NULL && rs_ctx->ma != NULL) {
2879
        MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, pR));
2880
    }
2881
#endif
2882
2883
905
cleanup:
2884
2885
905
    mpi_free_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi));
2886
2887
#if defined(MBEDTLS_ECP_INTERNAL_ALT)
2888
    if (is_grp_capable) {
2889
        mbedtls_internal_ecp_free(grp);
2890
    }
2891
#endif /* MBEDTLS_ECP_INTERNAL_ALT */
2892
2893
905
    mbedtls_ecp_point_free(&mP);
2894
2895
905
    ECP_RS_LEAVE(ma);
2896
2897
905
    return ret;
2898
358
}
2899
2900
/*
2901
 * Linear combination
2902
 * NOT constant-time
2903
 */
2904
int mbedtls_ecp_muladd(mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
2905
                       const mbedtls_mpi *m, const mbedtls_ecp_point *P,
2906
                       const mbedtls_mpi *n, const mbedtls_ecp_point *Q)
2907
574
{
2908
574
    return mbedtls_ecp_muladd_restartable(grp, R, m, P, n, Q, NULL);
2909
574
}
2910
#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
2911
#endif /* MBEDTLS_ECP_C */
2912
2913
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
2914
#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
2915
#define ECP_MPI_INIT(_p, _n) { .p = (mbedtls_mpi_uint *) (_p), .s = 1, .n = (_n) }
2916
#define ECP_MPI_INIT_ARRAY(x)   \
2917
    ECP_MPI_INIT(x, sizeof(x) / sizeof(mbedtls_mpi_uint))
2918
/*
2919
 * Constants for the two points other than 0, 1, -1 (mod p) in
2920
 * https://cr.yp.to/ecdh.html#validate
2921
 * See ecp_check_pubkey_x25519().
2922
 */
2923
static const mbedtls_mpi_uint x25519_bad_point_1[] = {
2924
    MBEDTLS_BYTES_TO_T_UINT_8(0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae),
2925
    MBEDTLS_BYTES_TO_T_UINT_8(0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a),
2926
    MBEDTLS_BYTES_TO_T_UINT_8(0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd),
2927
    MBEDTLS_BYTES_TO_T_UINT_8(0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00),
2928
};
2929
static const mbedtls_mpi_uint x25519_bad_point_2[] = {
2930
    MBEDTLS_BYTES_TO_T_UINT_8(0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24),
2931
    MBEDTLS_BYTES_TO_T_UINT_8(0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b),
2932
    MBEDTLS_BYTES_TO_T_UINT_8(0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86),
2933
    MBEDTLS_BYTES_TO_T_UINT_8(0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57),
2934
};
2935
static const mbedtls_mpi ecp_x25519_bad_point_1 = ECP_MPI_INIT_ARRAY(
2936
    x25519_bad_point_1);
2937
static const mbedtls_mpi ecp_x25519_bad_point_2 = ECP_MPI_INIT_ARRAY(
2938
    x25519_bad_point_2);
2939
#endif /* MBEDTLS_ECP_DP_CURVE25519_ENABLED */
2940
2941
/*
2942
 * Check that the input point is not one of the low-order points.
2943
 * This is recommended by the "May the Fourth" paper:
2944
 * https://eprint.iacr.org/2017/806.pdf
2945
 * Those points are never sent by an honest peer.
2946
 */
2947
static int ecp_check_bad_points_mx(const mbedtls_mpi *X, const mbedtls_mpi *P,
2948
                                   const mbedtls_ecp_group_id grp_id)
2949
0
{
2950
0
    int ret;
2951
0
    mbedtls_mpi XmP;
2952
2953
0
    mbedtls_mpi_init(&XmP);
2954
2955
    /* Reduce X mod P so that we only need to check values less than P.
2956
     * We know X < 2^256 so we can proceed by subtraction. */
2957
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&XmP, X));
2958
0
    while (mbedtls_mpi_cmp_mpi(&XmP, P) >= 0) {
2959
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&XmP, &XmP, P));
2960
0
    }
2961
2962
    /* Check against the known bad values that are less than P. For Curve448
2963
     * these are 0, 1 and -1. For Curve25519 we check the values less than P
2964
     * from the following list: https://cr.yp.to/ecdh.html#validate */
2965
0
    if (mbedtls_mpi_cmp_int(&XmP, 1) <= 0) {  /* takes care of 0 and 1 */
2966
0
        ret = MBEDTLS_ERR_ECP_INVALID_KEY;
2967
0
        goto cleanup;
2968
0
    }
2969
2970
0
#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
2971
0
    if (grp_id == MBEDTLS_ECP_DP_CURVE25519) {
2972
0
        if (mbedtls_mpi_cmp_mpi(&XmP, &ecp_x25519_bad_point_1) == 0) {
2973
0
            ret = MBEDTLS_ERR_ECP_INVALID_KEY;
2974
0
            goto cleanup;
2975
0
        }
2976
2977
0
        if (mbedtls_mpi_cmp_mpi(&XmP, &ecp_x25519_bad_point_2) == 0) {
2978
0
            ret = MBEDTLS_ERR_ECP_INVALID_KEY;
2979
0
            goto cleanup;
2980
0
        }
2981
0
    }
2982
#else
2983
    (void) grp_id;
2984
#endif
2985
2986
    /* Final check: check if XmP + 1 is P (final because it changes XmP!) */
2987
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&XmP, &XmP, 1));
2988
0
    if (mbedtls_mpi_cmp_mpi(&XmP, P) == 0) {
2989
0
        ret = MBEDTLS_ERR_ECP_INVALID_KEY;
2990
0
        goto cleanup;
2991
0
    }
2992
2993
0
    ret = 0;
2994
2995
0
cleanup:
2996
0
    mbedtls_mpi_free(&XmP);
2997
2998
0
    return ret;
2999
0
}
3000
3001
/*
3002
 * Check validity of a public key for Montgomery curves with x-only schemes
3003
 */
3004
static int ecp_check_pubkey_mx(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt)
3005
0
{
3006
    /* [Curve25519 p. 5] Just check X is the correct number of bytes */
3007
    /* Allow any public value, if it's too big then we'll just reduce it mod p
3008
     * (RFC 7748 sec. 5 para. 3). */
3009
0
    if (mbedtls_mpi_size(&pt->X) > (grp->nbits + 7) / 8) {
3010
0
        return MBEDTLS_ERR_ECP_INVALID_KEY;
3011
0
    }
3012
3013
    /* Implicit in all standards (as they don't consider negative numbers):
3014
     * X must be non-negative. This is normally ensured by the way it's
3015
     * encoded for transmission, but let's be extra sure. */
3016
0
    if (mbedtls_mpi_cmp_int(&pt->X, 0) < 0) {
3017
0
        return MBEDTLS_ERR_ECP_INVALID_KEY;
3018
0
    }
3019
3020
0
    return ecp_check_bad_points_mx(&pt->X, &grp->P, grp->id);
3021
0
}
3022
#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3023
3024
/*
3025
 * Check that a point is valid as a public key
3026
 */
3027
int mbedtls_ecp_check_pubkey(const mbedtls_ecp_group *grp,
3028
                             const mbedtls_ecp_point *pt)
3029
3.19k
{
3030
    /* Must use affine coordinates */
3031
3.19k
    if (mbedtls_mpi_cmp_int(&pt->Z, 1) != 0) {
3032
329
        return MBEDTLS_ERR_ECP_INVALID_KEY;
3033
329
    }
3034
3035
2.87k
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3036
2.87k
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
3037
0
        return ecp_check_pubkey_mx(grp, pt);
3038
0
    }
3039
2.87k
#endif
3040
2.87k
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3041
2.87k
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
3042
2.87k
        return ecp_check_pubkey_sw(grp, pt);
3043
2.87k
    }
3044
0
#endif
3045
0
    return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3046
2.87k
}
3047
3048
/*
3049
 * Check that an mbedtls_mpi is valid as a private key
3050
 */
3051
int mbedtls_ecp_check_privkey(const mbedtls_ecp_group *grp,
3052
                              const mbedtls_mpi *d)
3053
2.12k
{
3054
2.12k
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3055
2.12k
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
3056
        /* see RFC 7748 sec. 5 para. 5 */
3057
0
        if (mbedtls_mpi_get_bit(d, 0) != 0 ||
3058
0
            mbedtls_mpi_get_bit(d, 1) != 0 ||
3059
0
            mbedtls_mpi_bitlen(d) - 1 != grp->nbits) {  /* mbedtls_mpi_bitlen is one-based! */
3060
0
            return MBEDTLS_ERR_ECP_INVALID_KEY;
3061
0
        }
3062
3063
        /* see [Curve25519] page 5 */
3064
0
        if (grp->nbits == 254 && mbedtls_mpi_get_bit(d, 2) != 0) {
3065
0
            return MBEDTLS_ERR_ECP_INVALID_KEY;
3066
0
        }
3067
3068
0
        return 0;
3069
0
    }
3070
2.12k
#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3071
2.12k
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3072
2.12k
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
3073
        /* see SEC1 3.2 */
3074
2.12k
        if (mbedtls_mpi_cmp_int(d, 1) < 0 ||
3075
2.12k
            mbedtls_mpi_cmp_mpi(d, &grp->N) >= 0) {
3076
249
            return MBEDTLS_ERR_ECP_INVALID_KEY;
3077
1.87k
        } else {
3078
1.87k
            return 0;
3079
1.87k
        }
3080
2.12k
    }
3081
0
#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
3082
3083
0
    return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3084
2.12k
}
3085
3086
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3087
MBEDTLS_STATIC_TESTABLE
3088
int mbedtls_ecp_gen_privkey_mx(size_t high_bit,
3089
                               mbedtls_mpi *d,
3090
                               int (*f_rng)(void *, unsigned char *, size_t),
3091
                               void *p_rng)
3092
0
{
3093
0
    int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3094
0
    size_t n_random_bytes = high_bit / 8 + 1;
3095
3096
    /* [Curve25519] page 5 */
3097
    /* Generate a (high_bit+1)-bit random number by generating just enough
3098
     * random bytes, then shifting out extra bits from the top (necessary
3099
     * when (high_bit+1) is not a multiple of 8). */
3100
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(d, n_random_bytes,
3101
0
                                            f_rng, p_rng));
3102
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(d, 8 * n_random_bytes - high_bit - 1));
3103
3104
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, high_bit, 1));
3105
3106
    /* Make sure the last two bits are unset for Curve448, three bits for
3107
       Curve25519 */
3108
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 0, 0));
3109
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 1, 0));
3110
0
    if (high_bit == 254) {
3111
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 2, 0));
3112
0
    }
3113
3114
0
cleanup:
3115
0
    return ret;
3116
0
}
3117
#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3118
3119
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3120
static int mbedtls_ecp_gen_privkey_sw(
3121
    const mbedtls_mpi *N, mbedtls_mpi *d,
3122
    int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
3123
339
{
3124
339
    int ret = mbedtls_mpi_random(d, 1, N, f_rng, p_rng);
3125
339
    switch (ret) {
3126
0
        case MBEDTLS_ERR_MPI_NOT_ACCEPTABLE:
3127
0
            return MBEDTLS_ERR_ECP_RANDOM_FAILED;
3128
339
        default:
3129
339
            return ret;
3130
339
    }
3131
339
}
3132
#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
3133
3134
/*
3135
 * Generate a private key
3136
 */
3137
int mbedtls_ecp_gen_privkey(const mbedtls_ecp_group *grp,
3138
                            mbedtls_mpi *d,
3139
                            int (*f_rng)(void *, unsigned char *, size_t),
3140
                            void *p_rng)
3141
339
{
3142
339
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3143
339
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
3144
0
        return mbedtls_ecp_gen_privkey_mx(grp->nbits, d, f_rng, p_rng);
3145
0
    }
3146
339
#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3147
3148
339
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3149
339
    if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
3150
339
        return mbedtls_ecp_gen_privkey_sw(&grp->N, d, f_rng, p_rng);
3151
339
    }
3152
0
#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
3153
3154
0
    return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3155
339
}
3156
3157
#if defined(MBEDTLS_ECP_C)
3158
/*
3159
 * Generate a keypair with configurable base point
3160
 */
3161
int mbedtls_ecp_gen_keypair_base(mbedtls_ecp_group *grp,
3162
                                 const mbedtls_ecp_point *G,
3163
                                 mbedtls_mpi *d, mbedtls_ecp_point *Q,
3164
                                 int (*f_rng)(void *, unsigned char *, size_t),
3165
                                 void *p_rng)
3166
0
{
3167
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3168
0
    MBEDTLS_MPI_CHK(mbedtls_ecp_gen_privkey(grp, d, f_rng, p_rng));
3169
0
    MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, Q, d, G, f_rng, p_rng));
3170
3171
0
cleanup:
3172
0
    return ret;
3173
0
}
3174
3175
/*
3176
 * Generate key pair, wrapper for conventional base point
3177
 */
3178
int mbedtls_ecp_gen_keypair(mbedtls_ecp_group *grp,
3179
                            mbedtls_mpi *d, mbedtls_ecp_point *Q,
3180
                            int (*f_rng)(void *, unsigned char *, size_t),
3181
                            void *p_rng)
3182
0
{
3183
0
    return mbedtls_ecp_gen_keypair_base(grp, &grp->G, d, Q, f_rng, p_rng);
3184
0
}
3185
3186
/*
3187
 * Generate a keypair, prettier wrapper
3188
 */
3189
int mbedtls_ecp_gen_key(mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
3190
                        int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
3191
0
{
3192
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3193
0
    if ((ret = mbedtls_ecp_group_load(&key->grp, grp_id)) != 0) {
3194
0
        return ret;
3195
0
    }
3196
3197
0
    return mbedtls_ecp_gen_keypair(&key->grp, &key->d, &key->Q, f_rng, p_rng);
3198
0
}
3199
#endif /* MBEDTLS_ECP_C */
3200
3201
int mbedtls_ecp_set_public_key(mbedtls_ecp_group_id grp_id,
3202
                               mbedtls_ecp_keypair *key,
3203
                               const mbedtls_ecp_point *Q)
3204
0
{
3205
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3206
3207
0
    if (key->grp.id == MBEDTLS_ECP_DP_NONE) {
3208
        /* Group not set yet */
3209
0
        if ((ret = mbedtls_ecp_group_load(&key->grp, grp_id)) != 0) {
3210
0
            return ret;
3211
0
        }
3212
0
    } else if (key->grp.id != grp_id) {
3213
        /* Group mismatch */
3214
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3215
0
    }
3216
0
    return mbedtls_ecp_copy(&key->Q, Q);
3217
0
}
3218
3219
3220
0
#define ECP_CURVE25519_KEY_SIZE 32
3221
0
#define ECP_CURVE448_KEY_SIZE   56
3222
/*
3223
 * Read a private key.
3224
 */
3225
int mbedtls_ecp_read_key(mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key,
3226
                         const unsigned char *buf, size_t buflen)
3227
0
{
3228
0
    int ret = 0;
3229
3230
0
    if ((ret = mbedtls_ecp_group_load(&key->grp, grp_id)) != 0) {
3231
0
        return ret;
3232
0
    }
3233
3234
0
    ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE;
3235
3236
0
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3237
0
    if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
3238
        /*
3239
         * Mask the key as mandated by RFC7748 for Curve25519 and Curve448.
3240
         */
3241
0
        if (grp_id == MBEDTLS_ECP_DP_CURVE25519) {
3242
0
            if (buflen != ECP_CURVE25519_KEY_SIZE) {
3243
0
                return MBEDTLS_ERR_ECP_INVALID_KEY;
3244
0
            }
3245
3246
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary_le(&key->d, buf, buflen));
3247
3248
            /* Set the three least significant bits to 0 */
3249
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 0, 0));
3250
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 1, 0));
3251
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 2, 0));
3252
3253
            /* Set the most significant bit to 0 */
3254
0
            MBEDTLS_MPI_CHK(
3255
0
                mbedtls_mpi_set_bit(&key->d,
3256
0
                                    ECP_CURVE25519_KEY_SIZE * 8 - 1, 0)
3257
0
                );
3258
3259
            /* Set the second most significant bit to 1 */
3260
0
            MBEDTLS_MPI_CHK(
3261
0
                mbedtls_mpi_set_bit(&key->d,
3262
0
                                    ECP_CURVE25519_KEY_SIZE * 8 - 2, 1)
3263
0
                );
3264
0
        } else if (grp_id == MBEDTLS_ECP_DP_CURVE448) {
3265
0
            if (buflen != ECP_CURVE448_KEY_SIZE) {
3266
0
                return MBEDTLS_ERR_ECP_INVALID_KEY;
3267
0
            }
3268
3269
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary_le(&key->d, buf, buflen));
3270
3271
            /* Set the two least significant bits to 0 */
3272
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 0, 0));
3273
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 1, 0));
3274
3275
            /* Set the most significant bit to 1 */
3276
0
            MBEDTLS_MPI_CHK(
3277
0
                mbedtls_mpi_set_bit(&key->d,
3278
0
                                    ECP_CURVE448_KEY_SIZE * 8 - 1, 1)
3279
0
                );
3280
0
        }
3281
0
    }
3282
0
#endif
3283
0
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3284
0
    if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
3285
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(&key->d, buf, buflen));
3286
0
    }
3287
0
#endif
3288
3289
0
    if (ret == 0) {
3290
0
        MBEDTLS_MPI_CHK(mbedtls_ecp_check_privkey(&key->grp, &key->d));
3291
0
    }
3292
3293
0
cleanup:
3294
3295
0
    if (ret != 0) {
3296
0
        mbedtls_mpi_free(&key->d);
3297
0
    }
3298
3299
0
    return ret;
3300
0
}
3301
3302
/*
3303
 * Write a private key.
3304
 */
3305
#if !defined MBEDTLS_DEPRECATED_REMOVED
3306
int mbedtls_ecp_write_key(mbedtls_ecp_keypair *key,
3307
                          unsigned char *buf, size_t buflen)
3308
0
{
3309
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3310
3311
0
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3312
0
    if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
3313
0
        if (key->grp.id == MBEDTLS_ECP_DP_CURVE25519) {
3314
0
            if (buflen < ECP_CURVE25519_KEY_SIZE) {
3315
0
                return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
3316
0
            }
3317
3318
0
        } else if (key->grp.id == MBEDTLS_ECP_DP_CURVE448) {
3319
0
            if (buflen < ECP_CURVE448_KEY_SIZE) {
3320
0
                return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
3321
0
            }
3322
0
        }
3323
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary_le(&key->d, buf, buflen));
3324
0
    }
3325
0
#endif
3326
0
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3327
0
    if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
3328
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&key->d, buf, buflen));
3329
0
    }
3330
3331
0
#endif
3332
0
cleanup:
3333
3334
0
    return ret;
3335
0
}
3336
#endif /* MBEDTLS_DEPRECATED_REMOVED */
3337
3338
int mbedtls_ecp_write_key_ext(const mbedtls_ecp_keypair *key,
3339
                              size_t *olen, unsigned char *buf, size_t buflen)
3340
0
{
3341
0
    size_t len = (key->grp.nbits + 7) / 8;
3342
0
    if (len > buflen) {
3343
        /* For robustness, ensure *olen <= buflen even on error. */
3344
0
        *olen = 0;
3345
0
        return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL;
3346
0
    }
3347
0
    *olen = len;
3348
3349
    /* Private key not set */
3350
0
    if (key->d.n == 0) {
3351
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3352
0
    }
3353
3354
0
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3355
0
    if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) {
3356
0
        return mbedtls_mpi_write_binary_le(&key->d, buf, len);
3357
0
    }
3358
0
#endif
3359
3360
0
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3361
0
    if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) {
3362
0
        return mbedtls_mpi_write_binary(&key->d, buf, len);
3363
0
    }
3364
0
#endif
3365
3366
    /* Private key set but no recognized curve type? This shouldn't happen. */
3367
0
    return MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3368
0
}
3369
3370
/*
3371
 * Write a public key.
3372
 */
3373
int mbedtls_ecp_write_public_key(const mbedtls_ecp_keypair *key,
3374
                                 int format, size_t *olen,
3375
                                 unsigned char *buf, size_t buflen)
3376
0
{
3377
0
    return mbedtls_ecp_point_write_binary(&key->grp, &key->Q,
3378
0
                                          format, olen, buf, buflen);
3379
0
}
3380
3381
3382
#if defined(MBEDTLS_ECP_C)
3383
/*
3384
 * Check a public-private key pair
3385
 */
3386
int mbedtls_ecp_check_pub_priv(
3387
    const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv,
3388
    int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
3389
0
{
3390
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3391
0
    mbedtls_ecp_point Q;
3392
0
    mbedtls_ecp_group grp;
3393
0
    if (pub->grp.id == MBEDTLS_ECP_DP_NONE ||
3394
0
        pub->grp.id != prv->grp.id ||
3395
0
        mbedtls_mpi_cmp_mpi(&pub->Q.X, &prv->Q.X) ||
3396
0
        mbedtls_mpi_cmp_mpi(&pub->Q.Y, &prv->Q.Y) ||
3397
0
        mbedtls_mpi_cmp_mpi(&pub->Q.Z, &prv->Q.Z)) {
3398
0
        return MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3399
0
    }
3400
3401
0
    mbedtls_ecp_point_init(&Q);
3402
0
    mbedtls_ecp_group_init(&grp);
3403
3404
    /* mbedtls_ecp_mul() needs a non-const group... */
3405
0
    mbedtls_ecp_group_copy(&grp, &prv->grp);
3406
3407
    /* Also checks d is valid */
3408
0
    MBEDTLS_MPI_CHK(mbedtls_ecp_mul(&grp, &Q, &prv->d, &prv->grp.G, f_rng, p_rng));
3409
3410
0
    if (mbedtls_mpi_cmp_mpi(&Q.X, &prv->Q.X) ||
3411
0
        mbedtls_mpi_cmp_mpi(&Q.Y, &prv->Q.Y) ||
3412
0
        mbedtls_mpi_cmp_mpi(&Q.Z, &prv->Q.Z)) {
3413
0
        ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
3414
0
        goto cleanup;
3415
0
    }
3416
3417
0
cleanup:
3418
0
    mbedtls_ecp_point_free(&Q);
3419
0
    mbedtls_ecp_group_free(&grp);
3420
3421
0
    return ret;
3422
0
}
3423
3424
int mbedtls_ecp_keypair_calc_public(mbedtls_ecp_keypair *key,
3425
                                    int (*f_rng)(void *, unsigned char *, size_t),
3426
                                    void *p_rng)
3427
0
{
3428
0
    return mbedtls_ecp_mul(&key->grp, &key->Q, &key->d, &key->grp.G,
3429
0
                           f_rng, p_rng);
3430
0
}
3431
#endif /* MBEDTLS_ECP_C */
3432
3433
mbedtls_ecp_group_id mbedtls_ecp_keypair_get_group_id(
3434
    const mbedtls_ecp_keypair *key)
3435
0
{
3436
0
    return key->grp.id;
3437
0
}
3438
3439
/*
3440
 * Export generic key-pair parameters.
3441
 */
3442
int mbedtls_ecp_export(const mbedtls_ecp_keypair *key, mbedtls_ecp_group *grp,
3443
                       mbedtls_mpi *d, mbedtls_ecp_point *Q)
3444
0
{
3445
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3446
3447
0
    if (grp != NULL && (ret = mbedtls_ecp_group_copy(grp, &key->grp)) != 0) {
3448
0
        return ret;
3449
0
    }
3450
3451
0
    if (d != NULL && (ret = mbedtls_mpi_copy(d, &key->d)) != 0) {
3452
0
        return ret;
3453
0
    }
3454
3455
0
    if (Q != NULL && (ret = mbedtls_ecp_copy(Q, &key->Q)) != 0) {
3456
0
        return ret;
3457
0
    }
3458
3459
0
    return 0;
3460
0
}
3461
3462
#if defined(MBEDTLS_SELF_TEST)
3463
3464
#if defined(MBEDTLS_ECP_C)
3465
/*
3466
 * PRNG for test - !!!INSECURE NEVER USE IN PRODUCTION!!!
3467
 *
3468
 * This is the linear congruential generator from numerical recipes,
3469
 * except we only use the low byte as the output. See
3470
 * https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use
3471
 */
3472
static int self_test_rng(void *ctx, unsigned char *out, size_t len)
3473
0
{
3474
0
    static uint32_t state = 42;
3475
3476
0
    (void) ctx;
3477
3478
0
    for (size_t i = 0; i < len; i++) {
3479
0
        state = state * 1664525u + 1013904223u;
3480
0
        out[i] = (unsigned char) state;
3481
0
    }
3482
3483
0
    return 0;
3484
0
}
3485
3486
/* Adjust the exponent to be a valid private point for the specified curve.
3487
 * This is sometimes necessary because we use a single set of exponents
3488
 * for all curves but the validity of values depends on the curve. */
3489
static int self_test_adjust_exponent(const mbedtls_ecp_group *grp,
3490
                                     mbedtls_mpi *m)
3491
0
{
3492
0
    int ret = 0;
3493
0
    switch (grp->id) {
3494
    /* If Curve25519 is available, then that's what we use for the
3495
     * Montgomery test, so we don't need the adjustment code. */
3496
#if !defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
3497
#if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
3498
        case MBEDTLS_ECP_DP_CURVE448:
3499
            /* Move highest bit from 254 to N-1. Setting bit N-1 is
3500
             * necessary to enforce the highest-bit-set constraint. */
3501
            MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(m, 254, 0));
3502
            MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(m, grp->nbits, 1));
3503
            /* Copy second-highest bit from 253 to N-2. This is not
3504
             * necessary but improves the test variety a bit. */
3505
            MBEDTLS_MPI_CHK(
3506
                mbedtls_mpi_set_bit(m, grp->nbits - 1,
3507
                                    mbedtls_mpi_get_bit(m, 253)));
3508
            break;
3509
#endif
3510
#endif /* ! defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) */
3511
0
        default:
3512
            /* Non-Montgomery curves and Curve25519 need no adjustment. */
3513
0
            (void) grp;
3514
0
            (void) m;
3515
0
            goto cleanup;
3516
0
    }
3517
0
cleanup:
3518
0
    return ret;
3519
0
}
3520
3521
/* Calculate R = m.P for each m in exponents. Check that the number of
3522
 * basic operations doesn't depend on the value of m. */
3523
static int self_test_point(int verbose,
3524
                           mbedtls_ecp_group *grp,
3525
                           mbedtls_ecp_point *R,
3526
                           mbedtls_mpi *m,
3527
                           const mbedtls_ecp_point *P,
3528
                           const char *const *exponents,
3529
                           size_t n_exponents)
3530
0
{
3531
0
    int ret = 0;
3532
0
    size_t i = 0;
3533
0
    unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
3534
0
    add_count = 0;
3535
0
    dbl_count = 0;
3536
0
    mul_count = 0;
3537
3538
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(m, 16, exponents[0]));
3539
0
    MBEDTLS_MPI_CHK(self_test_adjust_exponent(grp, m));
3540
0
    MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, R, m, P, self_test_rng, NULL));
3541
3542
0
    for (i = 1; i < n_exponents; i++) {
3543
0
        add_c_prev = add_count;
3544
0
        dbl_c_prev = dbl_count;
3545
0
        mul_c_prev = mul_count;
3546
0
        add_count = 0;
3547
0
        dbl_count = 0;
3548
0
        mul_count = 0;
3549
3550
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(m, 16, exponents[i]));
3551
0
        MBEDTLS_MPI_CHK(self_test_adjust_exponent(grp, m));
3552
0
        MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, R, m, P, self_test_rng, NULL));
3553
3554
0
        if (add_count != add_c_prev ||
3555
0
            dbl_count != dbl_c_prev ||
3556
0
            mul_count != mul_c_prev) {
3557
0
            ret = 1;
3558
0
            break;
3559
0
        }
3560
0
    }
3561
3562
0
cleanup:
3563
0
    if (verbose != 0) {
3564
0
        if (ret != 0) {
3565
0
            mbedtls_printf("failed (%u)\n", (unsigned int) i);
3566
0
        } else {
3567
0
            mbedtls_printf("passed\n");
3568
0
        }
3569
0
    }
3570
0
    return ret;
3571
0
}
3572
#endif /* MBEDTLS_ECP_C */
3573
3574
/*
3575
 * Checkup routine
3576
 */
3577
int mbedtls_ecp_self_test(int verbose)
3578
0
{
3579
0
#if defined(MBEDTLS_ECP_C)
3580
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
3581
0
    mbedtls_ecp_group grp;
3582
0
    mbedtls_ecp_point R, P;
3583
0
    mbedtls_mpi m;
3584
3585
0
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3586
    /* Exponents especially adapted for secp192k1, which has the lowest
3587
     * order n of all supported curves (secp192r1 is in a slightly larger
3588
     * field but the order of its base point is slightly smaller). */
3589
0
    const char *sw_exponents[] =
3590
0
    {
3591
0
        "000000000000000000000000000000000000000000000001", /* one */
3592
0
        "FFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8C", /* n - 1 */
3593
0
        "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */
3594
0
        "400000000000000000000000000000000000000000000000", /* one and zeros */
3595
0
        "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */
3596
0
        "555555555555555555555555555555555555555555555555", /* 101010... */
3597
0
    };
3598
0
#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
3599
0
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3600
0
    const char *m_exponents[] =
3601
0
    {
3602
        /* Valid private values for Curve25519. In a build with Curve448
3603
         * but not Curve25519, they will be adjusted in
3604
         * self_test_adjust_exponent(). */
3605
0
        "4000000000000000000000000000000000000000000000000000000000000000",
3606
0
        "5C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C30",
3607
0
        "5715ECCE24583F7A7023C24164390586842E816D7280A49EF6DF4EAE6B280BF8",
3608
0
        "41A2B017516F6D254E1F002BCCBADD54BE30F8CEC737A0E912B4963B6BA74460",
3609
0
        "5555555555555555555555555555555555555555555555555555555555555550",
3610
0
        "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8",
3611
0
    };
3612
0
#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3613
3614
0
    mbedtls_ecp_group_init(&grp);
3615
0
    mbedtls_ecp_point_init(&R);
3616
0
    mbedtls_ecp_point_init(&P);
3617
0
    mbedtls_mpi_init(&m);
3618
3619
0
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
3620
    /* Use secp192r1 if available, or any available curve */
3621
0
#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
3622
0
    MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_SECP192R1));
3623
#else
3624
    MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, mbedtls_ecp_curve_list()->grp_id));
3625
#endif
3626
3627
0
    if (verbose != 0) {
3628
0
        mbedtls_printf("  ECP SW test #1 (constant op_count, base point G): ");
3629
0
    }
3630
    /* Do a dummy multiplication first to trigger precomputation */
3631
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&m, 2));
3632
0
    MBEDTLS_MPI_CHK(mbedtls_ecp_mul(&grp, &P, &m, &grp.G, self_test_rng, NULL));
3633
0
    ret = self_test_point(verbose,
3634
0
                          &grp, &R, &m, &grp.G,
3635
0
                          sw_exponents,
3636
0
                          sizeof(sw_exponents) / sizeof(sw_exponents[0]));
3637
0
    if (ret != 0) {
3638
0
        goto cleanup;
3639
0
    }
3640
3641
0
    if (verbose != 0) {
3642
0
        mbedtls_printf("  ECP SW test #2 (constant op_count, other point): ");
3643
0
    }
3644
    /* We computed P = 2G last time, use it */
3645
0
    ret = self_test_point(verbose,
3646
0
                          &grp, &R, &m, &P,
3647
0
                          sw_exponents,
3648
0
                          sizeof(sw_exponents) / sizeof(sw_exponents[0]));
3649
0
    if (ret != 0) {
3650
0
        goto cleanup;
3651
0
    }
3652
3653
0
    mbedtls_ecp_group_free(&grp);
3654
0
    mbedtls_ecp_point_free(&R);
3655
0
#endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */
3656
3657
0
#if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED)
3658
0
    if (verbose != 0) {
3659
0
        mbedtls_printf("  ECP Montgomery test (constant op_count): ");
3660
0
    }
3661
0
#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
3662
0
    MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_CURVE25519));
3663
#elif defined(MBEDTLS_ECP_DP_CURVE448_ENABLED)
3664
    MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_CURVE448));
3665
#else
3666
#error "MBEDTLS_ECP_MONTGOMERY_ENABLED is defined, but no curve is supported for self-test"
3667
#endif
3668
0
    ret = self_test_point(verbose,
3669
0
                          &grp, &R, &m, &grp.G,
3670
0
                          m_exponents,
3671
0
                          sizeof(m_exponents) / sizeof(m_exponents[0]));
3672
0
    if (ret != 0) {
3673
0
        goto cleanup;
3674
0
    }
3675
0
#endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */
3676
3677
0
cleanup:
3678
3679
0
    if (ret < 0 && verbose != 0) {
3680
0
        mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret);
3681
0
    }
3682
3683
0
    mbedtls_ecp_group_free(&grp);
3684
0
    mbedtls_ecp_point_free(&R);
3685
0
    mbedtls_ecp_point_free(&P);
3686
0
    mbedtls_mpi_free(&m);
3687
3688
0
    if (verbose != 0) {
3689
0
        mbedtls_printf("\n");
3690
0
    }
3691
3692
0
    return ret;
3693
#else /* MBEDTLS_ECP_C */
3694
    (void) verbose;
3695
    return 0;
3696
#endif /* MBEDTLS_ECP_C */
3697
0
}
3698
3699
#endif /* MBEDTLS_SELF_TEST */
3700
3701
#endif /* !MBEDTLS_ECP_ALT */
3702
3703
#endif /* MBEDTLS_ECP_LIGHT */