ecp.c 61.7 KB
Newer Older
1
/*
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
2
 *  Elliptic curves over GF(p): generic functions
3
 *
4
 *  Copyright (C) 2006-2014, ARM Limited, All Rights Reserved
5
 *
6
 *  This file is part of mbed TLS (https://tls.mbed.org)
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

/*
 * References:
 *
26
 * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
27
 * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
28
 * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
29
 * RFC 4492 for the related TLS structures and constants
30
 *
31 32
 * [M255] http://cr.yp.to/ecdh/curve25519-20060209.pdf
 *
33
 * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
34 35 36
 *     for elliptic curve cryptosystems. In : Cryptographic Hardware and
 *     Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
 *     <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
37
 *
38
 * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
39 40 41
 *     render ECC resistant against Side Channel Attacks. IACR Cryptology
 *     ePrint Archive, 2004, vol. 2004, p. 342.
 *     <http://eprint.iacr.org/2004/342.pdf>
42 43
 */

44
#if !defined(MBEDTLS_CONFIG_FILE)
45
#include "mbedtls/config.h"
46
#else
47
#include MBEDTLS_CONFIG_FILE
48
#endif
49

50
#if defined(MBEDTLS_ECP_C)
51

52
#include "mbedtls/ecp.h"
53

54 55
#include <string.h>

56
#if defined(MBEDTLS_PLATFORM_C)
57
#include "mbedtls/platform.h"
58
#else
59
#include <stdlib.h>
60
#include <stdio.h>
61
#define mbedtls_printf     printf
62
#define mbedtls_calloc    calloc
63
#define mbedtls_free       free
64 65
#endif

66 67 68 69 70 71 72 73
#if defined(_MSC_VER) && !defined(inline)
#define inline _inline
#else
#if defined(__ARMCC_VERSION) && !defined(inline)
#define inline __inline
#endif /* __ARMCC_VERSION */
#endif /*_MSC_VER */

74
/* Implementation that should never be optimized out by the compiler */
75
static void mbedtls_zeroize( void *v, size_t n ) {
76 77 78
    volatile unsigned char *p = v; while( n-- ) *p++ = 0;
}

79
#if defined(MBEDTLS_SELF_TEST)
80
/*
81
 * Counts of point addition and doubling, and field multiplications.
82
 * Used to test resistance of point multiplication to simple timing attacks.
83
 */
84
static unsigned long add_count, dbl_count, mul_count;
85 86
#endif

87 88 89 90 91 92 93 94 95 96 97
#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) ||   \
    defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) ||   \
    defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) ||   \
    defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) ||   \
    defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) ||   \
    defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)   ||   \
    defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)   ||   \
    defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)   ||   \
    defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) ||   \
    defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) ||   \
    defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
98
#define ECP_SHORTWEIERSTRASS
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
99 100
#endif

101 102 103 104
#if defined(MBEDTLS_ECP_DP_M221_ENABLED) ||   \
    defined(MBEDTLS_ECP_DP_M255_ENABLED) ||   \
    defined(MBEDTLS_ECP_DP_M383_ENABLED) ||   \
    defined(MBEDTLS_ECP_DP_M511_ENABLED)
105
#define ECP_MONTGOMERY
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
106 107 108 109 110 111 112
#endif

/*
 * Curve types: internal for now, might be exposed later
 */
typedef enum
{
113 114 115
    ECP_TYPE_NONE = 0,
    ECP_TYPE_SHORT_WEIERSTRASS,    /* y^2 = x^3 + a x + b      */
    ECP_TYPE_MONTGOMERY,           /* y^2 = x^3 + a x^2 + x    */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
116 117
} ecp_curve_type;

118 119 120
/*
 * List of supported curves:
 *  - internal ID
121
 *  - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
122
 *  - size in bits
123
 *  - readable name
124
 *
125 126
 * Curves are listed in order: largest curves first, and for a given size,
 * fastest curves first. This provides the default order for the SSL module.
127 128
 *
 * Reminder: update profiles in x509_crt.c when adding a new curves!
129
 */
130
static const mbedtls_ecp_curve_info ecp_supported_curves[] =
131
{
132 133
#if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
    { MBEDTLS_ECP_DP_SECP521R1,    25,     521,    "secp521r1"         },
134
#endif
135 136
#if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
    { MBEDTLS_ECP_DP_BP512R1,      28,     512,    "brainpoolP512r1"   },
137
#endif
138 139
#if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
    { MBEDTLS_ECP_DP_SECP384R1,    24,     384,    "secp384r1"         },
140
#endif
141 142
#if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
    { MBEDTLS_ECP_DP_BP384R1,      27,     384,    "brainpoolP384r1"   },
143
#endif
144 145
#if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
    { MBEDTLS_ECP_DP_SECP256R1,    23,     256,    "secp256r1"         },
146
#endif
147 148
#if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
    { MBEDTLS_ECP_DP_SECP256K1,    22,     256,    "secp256k1"         },
149
#endif
150 151
#if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
    { MBEDTLS_ECP_DP_BP256R1,      26,     256,    "brainpoolP256r1"   },
152
#endif
153 154
#if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
    { MBEDTLS_ECP_DP_SECP224R1,    21,     224,    "secp224r1"         },
155
#endif
156 157
#if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
    { MBEDTLS_ECP_DP_SECP224K1,    20,     224,    "secp224k1"         },
158
#endif
159 160
#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
    { MBEDTLS_ECP_DP_SECP192R1,    19,     192,    "secp192r1"         },
161
#endif
162 163
#if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
    { MBEDTLS_ECP_DP_SECP192K1,    18,     192,    "secp192k1"         },
164
#endif
165
    { MBEDTLS_ECP_DP_NONE,          0,     0,      NULL                },
166
};
167

168 169 170
#define ECP_NB_CURVES   sizeof( ecp_supported_curves ) /    \
                        sizeof( ecp_supported_curves[0] )

171
static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
172

173 174 175
/*
 * List of supported curves and associated info
 */
176
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void )
177
{
178
    return( ecp_supported_curves );
179 180
}

181
/*
182 183
 * List of supported curves, group ID only
 */
184
const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void )
185 186 187 188 189 190
{
    static int init_done = 0;

    if( ! init_done )
    {
        size_t i = 0;
191
        const mbedtls_ecp_curve_info *curve_info;
192

193 194
        for( curve_info = mbedtls_ecp_curve_list();
             curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
195 196 197 198
             curve_info++ )
        {
            ecp_supported_grp_id[i++] = curve_info->grp_id;
        }
199
        ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
200 201 202 203

        init_done = 1;
    }

204
    return( ecp_supported_grp_id );
205 206 207 208
}

/*
 * Get the curve info for the internal identifier
209
 */
210
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id )
211
{
212
    const mbedtls_ecp_curve_info *curve_info;
213

214 215
    for( curve_info = mbedtls_ecp_curve_list();
         curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
216 217 218 219 220 221 222 223 224 225 226 227
         curve_info++ )
    {
        if( curve_info->grp_id == grp_id )
            return( curve_info );
    }

    return( NULL );
}

/*
 * Get the curve info from the TLS identifier
 */
228
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id )
229
{
230
    const mbedtls_ecp_curve_info *curve_info;
231

232 233
    for( curve_info = mbedtls_ecp_curve_list();
         curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
234 235 236 237 238 239 240 241 242
         curve_info++ )
    {
        if( curve_info->tls_id == tls_id )
            return( curve_info );
    }

    return( NULL );
}

243 244 245
/*
 * Get the curve info from the name
 */
246
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name )
247
{
248
    const mbedtls_ecp_curve_info *curve_info;
249

250 251
    for( curve_info = mbedtls_ecp_curve_list();
         curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
252 253
         curve_info++ )
    {
254
        if( strcmp( curve_info->name, name ) == 0 )
255 256 257 258 259 260
            return( curve_info );
    }

    return( NULL );
}

261
/*
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
262
 * Get the type of a curve
263
 */
264
static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp )
265
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
266
    if( grp->G.X.p == NULL )
267
        return( ECP_TYPE_NONE );
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
268 269

    if( grp->G.Y.p == NULL )
270
        return( ECP_TYPE_MONTGOMERY );
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
271
    else
272
        return( ECP_TYPE_SHORT_WEIERSTRASS );
273 274
}

275
/*
276
 * Initialize (the components of) a point
277
 */
278
void mbedtls_ecp_point_init( mbedtls_ecp_point *pt )
279 280 281 282
{
    if( pt == NULL )
        return;

283 284 285
    mbedtls_mpi_init( &pt->X );
    mbedtls_mpi_init( &pt->Y );
    mbedtls_mpi_init( &pt->Z );
286 287 288 289 290
}

/*
 * Initialize (the components of) a group
 */
291
void mbedtls_ecp_group_init( mbedtls_ecp_group *grp )
292 293 294 295
{
    if( grp == NULL )
        return;

296
    memset( grp, 0, sizeof( mbedtls_ecp_group ) );
297 298
}

299 300 301
/*
 * Initialize (the components of) a key pair
 */
302
void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key )
303
{
304
    if( key == NULL )
305 306
        return;

307 308 309
    mbedtls_ecp_group_init( &key->grp );
    mbedtls_mpi_init( &key->d );
    mbedtls_ecp_point_init( &key->Q );
310 311
}

312 313 314
/*
 * Unallocate (the components of) a point
 */
315
void mbedtls_ecp_point_free( mbedtls_ecp_point *pt )
316 317 318 319
{
    if( pt == NULL )
        return;

320 321 322
    mbedtls_mpi_free( &( pt->X ) );
    mbedtls_mpi_free( &( pt->Y ) );
    mbedtls_mpi_free( &( pt->Z ) );
323 324 325 326 327
}

/*
 * Unallocate (the components of) a group
 */
328
void mbedtls_ecp_group_free( mbedtls_ecp_group *grp )
329
{
330 331
    size_t i;

332 333 334
    if( grp == NULL )
        return;

335 336
    if( grp->h != 1 )
    {
337 338 339 340 341
        mbedtls_mpi_free( &grp->P );
        mbedtls_mpi_free( &grp->A );
        mbedtls_mpi_free( &grp->B );
        mbedtls_ecp_point_free( &grp->G );
        mbedtls_mpi_free( &grp->N );
342
    }
343

344 345 346
    if( grp->T != NULL )
    {
        for( i = 0; i < grp->T_size; i++ )
347 348
            mbedtls_ecp_point_free( &grp->T[i] );
        mbedtls_free( grp->T );
349 350
    }

351
    mbedtls_zeroize( grp, sizeof( mbedtls_ecp_group ) );
352
}
353

354 355 356
/*
 * Unallocate (the components of) a key pair
 */
357
void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key )
358
{
359
    if( key == NULL )
360 361
        return;

362 363 364
    mbedtls_ecp_group_free( &key->grp );
    mbedtls_mpi_free( &key->d );
    mbedtls_ecp_point_free( &key->Q );
365 366
}

367
/*
368
 * Copy the contents of a point
369
 */
370
int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
371
{
372
    int ret;
373

374 375 376
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->X, &Q->X ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Y, &Q->Y ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &P->Z, &Q->Z ) );
377 378 379 380

cleanup:
    return( ret );
}
381

382 383 384
/*
 * Copy the contents of a group object
 */
385
int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src )
386
{
387
    return mbedtls_ecp_group_load( dst, src->id );
388 389
}

390
/*
391
 * Set point to zero
392
 */
393
int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt )
394
{
395
    int ret;
396

397 398 399
    MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->X , 1 ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Y , 1 ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z , 0 ) );
400 401 402 403 404 405

cleanup:
    return( ret );
}

/*
406
 * Tell if a point is zero
407
 */
408
int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt )
409
{
410
    return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 );
411 412 413
}

/*
414
 * Import a non-zero point from ASCII strings
415
 */
416
int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix,
417
                           const char *x, const char *y )
418
{
419
    int ret;
420

421 422 423
    MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->X, radix, x ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &P->Y, radix, y ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &P->Z, 1 ) );
424 425

cleanup:
426 427 428
    return( ret );
}

429
/*
430
 * Export a point into unsigned binary data (SEC1 2.3.3)
431
 */
432
int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *P,
433
                            int format, size_t *olen,
434
                            unsigned char *buf, size_t buflen )
435
{
436
    int ret = 0;
437 438
    size_t plen;

439 440 441
    if( format != MBEDTLS_ECP_PF_UNCOMPRESSED &&
        format != MBEDTLS_ECP_PF_COMPRESSED )
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
442

443
    /*
444
     * Common case: P == 0
445
     */
446
    if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
447 448
    {
        if( buflen < 1 )
449
            return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
450 451 452 453 454 455 456

        buf[0] = 0x00;
        *olen = 1;

        return( 0 );
    }

457
    plen = mbedtls_mpi_size( &grp->P );
458

459
    if( format == MBEDTLS_ECP_PF_UNCOMPRESSED )
460 461 462 463
    {
        *olen = 2 * plen + 1;

        if( buflen < *olen )
464
            return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
465

466
        buf[0] = 0x04;
467 468
        MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
        MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->Y, buf + 1 + plen, plen ) );
469
    }
470
    else if( format == MBEDTLS_ECP_PF_COMPRESSED )
471 472 473 474
    {
        *olen = plen + 1;

        if( buflen < *olen )
475
            return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
476

477 478
        buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 );
        MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
479
    }
480 481 482 483 484

cleanup:
    return( ret );
}

485 486 487
/*
 * Import a point from unsigned binary data (SEC1 2.3.4)
 */
488
int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
489 490
                           const unsigned char *buf, size_t ilen )
{
491 492 493
    int ret;
    size_t plen;

Paul Bakker's avatar
Paul Bakker committed
494
    if( ilen < 1 )
495
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
496

497 498 499
    if( buf[0] == 0x00 )
    {
        if( ilen == 1 )
500
            return( mbedtls_ecp_set_zero( pt ) );
501
        else
502
            return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
503
    }
504

505
    plen = mbedtls_mpi_size( &grp->P );
506

507
    if( buf[0] != 0x04 )
508
        return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
509 510

    if( ilen != 2 * plen + 1 )
511
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
512

513 514 515
    MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->X, buf + 1, plen ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
516 517 518 519 520

cleanup:
    return( ret );
}

521 522 523 524 525 526
/*
 * Import a point from a TLS ECPoint record (RFC 4492)
 *      struct {
 *          opaque point <1..2^8-1>;
 *      } ECPoint;
 */
527
int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
528
                        const unsigned char **buf, size_t buf_len )
529 530
{
    unsigned char data_len;
531
    const unsigned char *buf_start;
532 533

    /*
534
     * We must have at least two bytes (1 for length, at least one for data)
535 536
     */
    if( buf_len < 2 )
537
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
538

539
    data_len = *(*buf)++;
540
    if( data_len < 1 || data_len > buf_len - 1 )
541
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
542

543 544 545 546 547 548
    /*
     * Save buffer start for read_binary and update buf
     */
    buf_start = *buf;
    *buf += data_len;

549
    return mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len );
550 551 552 553 554 555 556 557
}

/*
 * Export a point as a TLS ECPoint record (RFC 4492)
 *      struct {
 *          opaque point <1..2^8-1>;
 *      } ECPoint;
 */
558
int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt,
559 560
                         int format, size_t *olen,
                         unsigned char *buf, size_t blen )
561
{
562 563
    int ret;

564
    /*
565
     * buffer length must be at least one, for our length byte
566
     */
567
    if( blen < 1 )
568
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
569

570
    if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format,
571 572 573 574 575 576
                    olen, buf + 1, blen - 1) ) != 0 )
        return( ret );

    /*
     * write length to the first byte and update total length
     */
577
    buf[0] = (unsigned char) *olen;
578 579
    ++*olen;

580
    return( 0 );
581 582
}

583 584 585
/*
 * Set a group from an ECParameters record (RFC 4492)
 */
586
int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp, const unsigned char **buf, size_t len )
587 588
{
    uint16_t tls_id;
589
    const mbedtls_ecp_curve_info *curve_info;
590 591 592 593 594

    /*
     * We expect at least three bytes (see below)
     */
    if( len < 3 )
595
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
596 597 598 599

    /*
     * First byte is curve_type; only named_curve is handled
     */
600 601
    if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE )
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
602 603 604 605 606 607 608 609

    /*
     * Next two bytes are the namedcurve value
     */
    tls_id = *(*buf)++;
    tls_id <<= 8;
    tls_id |= *(*buf)++;

610 611
    if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
        return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
612

613
    return mbedtls_ecp_group_load( grp, curve_info->grp_id );
614 615 616 617 618
}

/*
 * Write the ECParameters record corresponding to a group (RFC 4492)
 */
619
int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen,
620 621
                         unsigned char *buf, size_t blen )
{
622
    const mbedtls_ecp_curve_info *curve_info;
623

624 625
    if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL )
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
626 627 628 629 630 631

    /*
     * We are going to write 3 bytes (see below)
     */
    *olen = 3;
    if( blen < *olen )
632
        return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
633 634 635 636

    /*
     * First byte is curve_type, always named_curve
     */
637
    *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
638 639 640 641 642 643 644

    /*
     * Next two bytes are the namedcurve value
     */
    buf[0] = curve_info->tls_id >> 8;
    buf[1] = curve_info->tls_id & 0xFF;

645
    return( 0 );
646 647 648
}

/*
649 650
 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
 * See the documentation of struct mbedtls_ecp_group.
651
 *
652
 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
653
 */
654
static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp )
655 656 657 658
{
    int ret;

    if( grp->modp == NULL )
659
        return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) );
660 661

    /* N->s < 0 is a much faster test, which fails only if N is 0 */
662
    if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) ||
663
        mbedtls_mpi_bitlen( N ) > 2 * grp->pbits )
664
    {
665
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
666 667
    }

668
    MBEDTLS_MPI_CHK( grp->modp( N ) );
669 670

    /* N->s < 0 is a much faster test, which fails only if N is 0 */
671 672
    while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 )
        MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) );
673

674
    while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 )
675
        /* we known P, N and the result are positive */
676
        MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) );
677 678 679 680 681 682 683 684 685

cleanup:
    return( ret );
}

/*
 * Fast mod-p functions expect their argument to be in the 0..p^2 range.
 *
 * In order to guarantee that, we need to ensure that operands of
686
 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
687 688 689 690 691 692
 * bring the result back to this range.
 *
 * The following macros are shortcuts for doing that.
 */

/*
693
 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
694
 */
695
#if defined(MBEDTLS_SELF_TEST)
696 697 698 699 700
#define INC_MUL_COUNT   mul_count++;
#else
#define INC_MUL_COUNT
#endif

701
#define MOD_MUL( N )    do { MBEDTLS_MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
702
                        while( 0 )
703 704

/*
705
 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
706 707 708
 * N->s < 0 is a very fast test, which fails only if N is 0
 */
#define MOD_SUB( N )                                \
709 710
    while( N.s < 0 && mbedtls_mpi_cmp_int( &N, 0 ) != 0 )   \
        MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &N, &N, &grp->P ) )
711 712

/*
713
 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
714 715 716 717
 * We known P, N and the result are positive, so sub_abs is correct, and
 * a bit faster.
 */
#define MOD_ADD( N )                                \
718 719
    while( mbedtls_mpi_cmp_mpi( &N, &grp->P ) >= 0 )        \
        MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &N, &N, &grp->P ) )
720

721
#if defined(ECP_SHORTWEIERSTRASS)
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
722 723 724 725 726 727 728 729
/*
 * For curves in short Weierstrass form, we do all the internal operations in
 * Jacobian coordinates.
 *
 * For multiplication, we'll use a comb method with coutermeasueres against
 * SPA, hence timing attacks.
 */

730 731
/*
 * Normalize jacobian coordinates so that Z == 0 || Z == 1  (GECC 3.2.1)
732
 * Cost: 1N := 1I + 3M + 1S
733
 */
734
static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt )
735 736
{
    int ret;
737
    mbedtls_mpi Zi, ZZi;
738

739
    if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 )
740 741
        return( 0 );

742
    mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
743 744 745 746

    /*
     * X = X / Z^2  mod p
     */
747 748 749
    MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &Zi,      &pt->Z,     &grp->P ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi,     &Zi,        &Zi     ) ); MOD_MUL( ZZi );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->X,   &pt->X,     &ZZi    ) ); MOD_MUL( pt->X );
750 751 752 753

    /*
     * Y = Y / Z^3  mod p
     */
754 755
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y,   &pt->Y,     &ZZi    ) ); MOD_MUL( pt->Y );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &pt->Y,   &pt->Y,     &Zi     ) ); MOD_MUL( pt->Y );
756 757 758 759

    /*
     * Z = 1
     */
760
    MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
761 762 763

cleanup:

764
    mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
765 766 767 768

    return( ret );
}

769
/*
770
 * Normalize jacobian coordinates of an array of (pointers to) points,
771 772 773 774 775
 * using Montgomery's trick to perform only one inversion mod P.
 * (See for example Cohen's "A Course in Computational Algebraic Number
 * Theory", Algorithm 10.3.4.)
 *
 * Warning: fails (returning an error) if one of the points is zero!
776
 * This should never happen, see choice of w in ecp_mul_comb().
777 778
 *
 * Cost: 1N(t) := 1I + (6t - 3)M + 1S
779
 */
780 781
static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
                                   mbedtls_ecp_point *T[], size_t t_len )
782
{
783 784
    int ret;
    size_t i;
785
    mbedtls_mpi *c, u, Zi, ZZi;
786

787
    if( t_len < 2 )
788
        return( ecp_normalize_jac( grp, *T ) );
789

790
    if( ( c = mbedtls_calloc( t_len, sizeof( mbedtls_mpi ) ) ) == NULL )
791
        return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
792

793
    mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
794 795 796 797

    /*
     * c[i] = Z_0 * ... * Z_i
     */
798
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) );
799
    for( i = 1; i < t_len; i++ )
800
    {
801
        MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );
802 803
        MOD_MUL( c[i] );
    }
804

805 806 807
    /*
     * u = 1 / (Z_0 * ... * Z_n) mod P
     */
808
    MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[t_len-1], &grp->P ) );
809

810 811 812 813 814 815 816
    for( i = t_len - 1; ; i-- )
    {
        /*
         * Zi = 1 / Z_i mod p
         * u = 1 / (Z_0 * ... * Z_i) mod P
         */
        if( i == 0 ) {
817
            MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) );
818 819 820
        }
        else
        {
821 822
            MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &u, &c[i-1]  ) ); MOD_MUL( Zi );
            MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u,  &u, &T[i]->Z ) ); MOD_MUL( u );
823
        }
824

825 826 827
        /*
         * proceed as in normalize()
         */
828 829 830 831
        MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ZZi,     &Zi,      &Zi  ) ); MOD_MUL( ZZi );
        MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X );
        MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y );
        MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi  ) ); MOD_MUL( T[i]->Y );
832 833 834 835 836 837 838

        /*
         * Post-precessing: reclaim some memory by shrinking coordinates
         * - not storing Z (always 1)
         * - shrinking other coordinates, but still keeping the same number of
         *   limbs as P, as otherwise it will too likely be regrown too fast.
         */
839 840 841
        MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->X, grp->P.n ) );
        MBEDTLS_MPI_CHK( mbedtls_mpi_shrink( &T[i]->Y, grp->P.n ) );
        mbedtls_mpi_free( &T[i]->Z );
842

843 844 845 846 847 848
        if( i == 0 )
            break;
    }

cleanup:

849
    mbedtls_mpi_free( &u ); mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
850
    for( i = 0; i < t_len; i++ )
851 852
        mbedtls_mpi_free( &c[i] );
    mbedtls_free( c );
853 854 855 856

    return( ret );
}

857 858 859 860
/*
 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
 */
861 862
static int ecp_safe_invert_jac( const mbedtls_ecp_group *grp,
                            mbedtls_ecp_point *Q,
863 864 865 866
                            unsigned char inv )
{
    int ret;
    unsigned char nonzero;
867
    mbedtls_mpi mQY;
868

869
    mbedtls_mpi_init( &mQY );
870 871

    /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
872 873 874
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) );
    nonzero = mbedtls_mpi_cmp_int( &Q->Y, 0 ) != 0;
    MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) );
875 876

cleanup:
877
    mbedtls_mpi_free( &mQY );
878 879 880 881

    return( ret );
}

882 883 884
/*
 * Point doubling R = 2 P, Jacobian coordinates
 *
885
 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 .
886
 *
887 888 889 890 891 892 893 894
 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR
 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.
 *
 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }.
 *
 * Cost: 1D := 3M + 4S          (A ==  0)
 *             4M + 4S          (A == -3)
 *             3M + 6S + 1a     otherwise
895
 */
896 897
static int ecp_double_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
                           const mbedtls_ecp_point *P )
898 899
{
    int ret;
900
    mbedtls_mpi M, S, T, U;
901

902
#if defined(MBEDTLS_SELF_TEST)
903
    dbl_count++;
904
#endif
905

906
    mbedtls_mpi_init( &M ); mbedtls_mpi_init( &S ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &U );
907 908 909 910

    /* Special case for A = -3 */
    if( grp->A.p == NULL )
    {
911
        /* M = 3(X + Z^2)(X - Z^2) */
912 913 914 915 916
        MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &P->Z,  &P->Z   ) ); MOD_MUL( S );
        MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &T,  &P->X,  &S      ) ); MOD_ADD( T );
        MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U,  &P->X,  &S      ) ); MOD_SUB( U );
        MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &T,     &U      ) ); MOD_MUL( S );
        MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M,  &S,     3       ) ); MOD_ADD( M );
917 918
    }
    else
919
    {
920
        /* M = 3.X^2 */
921 922
        MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &P->X,  &P->X   ) ); MOD_MUL( S );
        MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &M,  &S,     3       ) ); MOD_ADD( M );
923 924

        /* Optimize away for "koblitz" curves with A = 0 */
925
        if( mbedtls_mpi_cmp_int( &grp->A, 0 ) != 0 )
926 927
        {
            /* M += A.Z^4 */
928 929 930 931
            MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &P->Z,  &P->Z   ) ); MOD_MUL( S );
            MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T,  &S,     &S      ) ); MOD_MUL( T );
            MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &T,     &grp->A ) ); MOD_MUL( S );
            MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &M,  &M,     &S      ) ); MOD_ADD( M );
932
        }
933
    }
934

935
    /* S = 4.X.Y^2 */
936 937 938 939
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T,  &P->Y,  &P->Y   ) ); MOD_MUL( T );
    MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T,  1               ) ); MOD_ADD( T );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &P->X,  &T      ) ); MOD_MUL( S );
    MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &S,  1               ) ); MOD_ADD( S );
940 941

    /* U = 8.Y^4 */
942 943
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U,  &T,     &T      ) ); MOD_MUL( U );
    MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U,  1               ) ); MOD_ADD( U );
944 945

    /* T = M^2 - 2.S */
946 947 948
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T,  &M,     &M      ) ); MOD_MUL( T );
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T,  &T,     &S      ) ); MOD_SUB( T );
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T,  &T,     &S      ) ); MOD_SUB( T );
949 950

    /* S = M(S - T) - U */
951 952 953
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S,  &S,     &T      ) ); MOD_SUB( S );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &S,  &S,     &M      ) ); MOD_MUL( S );
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &S,  &S,     &U      ) ); MOD_SUB( S );
954 955

    /* U = 2.Y.Z */
956 957
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &U,  &P->Y,  &P->Z   ) ); MOD_MUL( U );
    MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &U,  1               ) ); MOD_ADD( U );
958

959 960 961
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &T ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &S ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &U ) );
962

963
cleanup:
964
    mbedtls_mpi_free( &M ); mbedtls_mpi_free( &S ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &U );
965 966

    return( ret );
967 968 969
}

/*
970
 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
971 972 973 974
 *
 * The coordinates of Q must be normalized (= affine),
 * but those of P don't need to. R is not normalized.
 *
975
 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
976
 * None of these cases can happen as intermediate step in ecp_mul_comb():
977 978 979 980 981 982
 * - at each step, P, Q and R are multiples of the base point, the factor
 *   being less than its order, so none of them is zero;
 * - Q is an odd multiple of the base point, P an even multiple,
 *   due to the choice of precomputed points in the modified comb method.
 * So branches for these cases do not leak secret information.
 *
983 984
 * We accept Q->Z being unset (saving memory in tables) as meaning 1.
 *
985
 * Cost: 1A := 8M + 3S
986
 */
987 988
static int ecp_add_mixed( const mbedtls_ecp_group *grp, mbedtls_ecp_point *R,
                          const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
989
{
990
    int ret;
991
    mbedtls_mpi T1, T2, T3, T4, X, Y, Z;
992

993
#if defined(MBEDTLS_SELF_TEST)
994 995
    add_count++;
#endif
996 997

    /*
998
     * Trivial cases: P == 0 or Q == 0 (case 1)
999
     */
1000 1001
    if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
        return( mbedtls_ecp_copy( R, Q ) );
1002

1003 1004
    if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 0 ) == 0 )
        return( mbedtls_ecp_copy( R, P ) );
1005 1006

    /*
1007
     * Make sure Q coordinates are normalized
1008
     */
1009 1010
    if( Q->Z.p != NULL && mbedtls_mpi_cmp_int( &Q->Z, 1 ) != 0 )
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
1011

1012 1013
    mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 ); mbedtls_mpi_init( &T3 ); mbedtls_mpi_init( &T4 );
    mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1014

1015 1016 1017 1018 1019 1020
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1,  &P->Z,  &P->Z ) );  MOD_MUL( T1 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2,  &T1,    &P->Z ) );  MOD_MUL( T2 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T1,  &T1,    &Q->X ) );  MOD_MUL( T1 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T2,  &T2,    &Q->Y ) );  MOD_MUL( T2 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T1,  &T1,    &P->X ) );  MOD_SUB( T1 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T2,  &T2,    &P->Y ) );  MOD_SUB( T2 );
1021

1022
    /* Special cases (2) and (3) */
1023
    if( mbedtls_mpi_cmp_int( &T1, 0 ) == 0 )
1024
    {
1025
        if( mbedtls_mpi_cmp_int( &T2, 0 ) == 0 )
1026 1027 1028 1029 1030 1031
        {
            ret = ecp_double_jac( grp, R, P );
            goto cleanup;
        }
        else
        {
1032
            ret = mbedtls_ecp_set_zero( R );
1033 1034 1035
            goto cleanup;
        }
    }
1036

1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Z,   &P->Z,  &T1   ) );  MOD_MUL( Z  );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3,  &T1,    &T1   ) );  MOD_MUL( T3 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4,  &T3,    &T1   ) );  MOD_MUL( T4 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3,  &T3,    &P->X ) );  MOD_MUL( T3 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1,  &T3,    2     ) );  MOD_ADD( T1 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X,   &T2,    &T2   ) );  MOD_MUL( X  );
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X,   &X,     &T1   ) );  MOD_SUB( X  );
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X,   &X,     &T4   ) );  MOD_SUB( X  );
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &T3,  &T3,    &X    ) );  MOD_SUB( T3 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T3,  &T3,    &T2   ) );  MOD_MUL( T3 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T4,  &T4,    &P->Y ) );  MOD_MUL( T4 );
    MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &Y,   &T3,    &T4   ) );  MOD_SUB( Y  );

    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->X, &X ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Y, &Y ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R->Z, &Z ) );
1053

1054
cleanup:
1055

1056 1057
    mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); mbedtls_mpi_free( &T3 ); mbedtls_mpi_free( &T4 );
    mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1058

1059
    return( ret );
1060
}
1061

1062
/*
1063 1064
 * Randomize jacobian coordinates:
 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
1065
 * This is sort of the reverse operation of ecp_normalize_jac().
1066 1067
 *
 * This countermeasure was first suggested in [2].
1068
 */
1069
static int ecp_randomize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
1070
                int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1071 1072
{
    int ret;
1073
    mbedtls_mpi l, ll;
1074
    size_t p_size = ( grp->pbits + 7 ) / 8;
1075
    int count = 0;
1076

1077
    mbedtls_mpi_init( &l ); mbedtls_mpi_init( &ll );
1078

1079 1080 1081
    /* Generate l such that 1 < l < p */
    do
    {
1082
        mbedtls_mpi_fill_random( &l, p_size, f_rng, p_rng );
1083

1084 1085
        while( mbedtls_mpi_cmp_mpi( &l, &grp->P ) >= 0 )
            MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &l, 1 ) );
1086

1087
        if( count++ > 10 )
1088
            return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
1089
    }
1090
    while( mbedtls_mpi_cmp_int( &l, 1 ) <= 0 );
Manuel Pégourié-Gonnard's avatar