ecp.c 57.5 KB
Newer Older
1
/*
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
2
 *  Elliptic curves over GF(p): generic functions
3
 *
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
4
 *  Copyright (C) 2006-2014, ARM Limited, All Rights Reserved
5
 *
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
6
 *  This file is part of mbed TLS (https://polarssl.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 34 35 36
 * [2] CORON, Jean-Sébastien. Resistance against differential power analysis
 *     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 39 40 41
 *
 * [3] HEDABOU, Mustapha, PINEL, Pierre, et BÉNÉTEAU, Lucien. A comb method to
 *     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(POLARSSL_CONFIG_FILE)
45
#include "polarssl/config.h"
46 47 48
#else
#include POLARSSL_CONFIG_FILE
#endif
49 50 51 52

#if defined(POLARSSL_ECP_C)

#include "polarssl/ecp.h"
53

54 55
#if defined(POLARSSL_PLATFORM_C)
#include "polarssl/platform.h"
56
#else
57
#define polarssl_printf     printf
58 59 60 61
#define polarssl_malloc     malloc
#define polarssl_free       free
#endif

62
#include <stdlib.h>
63

64 65 66 67 68
#if defined(_MSC_VER) && !defined strcasecmp && !defined(EFIX64) && \
    !defined(EFI32)
#define strcasecmp _stricmp
#endif

69 70 71 72 73 74 75 76
#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 */

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

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

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
90 91 92 93 94 95 96
#if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED) ||   \
    defined(POLARSSL_ECP_DP_SECP224R1_ENABLED) ||   \
    defined(POLARSSL_ECP_DP_SECP256R1_ENABLED) ||   \
    defined(POLARSSL_ECP_DP_SECP384R1_ENABLED) ||   \
    defined(POLARSSL_ECP_DP_SECP521R1_ENABLED) ||   \
    defined(POLARSSL_ECP_DP_BP256R1_ENABLED)   ||   \
    defined(POLARSSL_ECP_DP_BP384R1_ENABLED)   ||   \
97 98 99 100
    defined(POLARSSL_ECP_DP_BP512R1_ENABLED)   ||   \
    defined(POLARSSL_ECP_DP_SECP192K1_ENABLED) ||   \
    defined(POLARSSL_ECP_DP_SECP224K1_ENABLED) ||   \
    defined(POLARSSL_ECP_DP_SECP256K1_ENABLED)
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
#define POLARSSL_ECP_SHORT_WEIERSTRASS
#endif

#if defined(POLARSSL_ECP_DP_M221_ENABLED) ||   \
    defined(POLARSSL_ECP_DP_M255_ENABLED) ||   \
    defined(POLARSSL_ECP_DP_M383_ENABLED) ||   \
    defined(POLARSSL_ECP_DP_M511_ENABLED)
#define POLARSSL_ECP_MONTGOMERY
#endif

/*
 * Curve types: internal for now, might be exposed later
 */
typedef enum
{
    POLARSSL_ECP_TYPE_NONE = 0,
    POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS,    /* y^2 = x^3 + a x + b      */
    POLARSSL_ECP_TYPE_MONTGOMERY,           /* y^2 = x^3 + a x^2 + x    */
} ecp_curve_type;

121 122 123
/*
 * List of supported curves:
 *  - internal ID
124
 *  - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
125
 *  - size in bits
126
 *  - readable name
127
 *
128 129
 * 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.
130
 */
131
static const ecp_curve_info ecp_supported_curves[] =
132 133
{
#if defined(POLARSSL_ECP_DP_SECP521R1_ENABLED)
134
    { POLARSSL_ECP_DP_SECP521R1,    25,     521,    "secp521r1"         },
135
#endif
136 137 138
#if defined(POLARSSL_ECP_DP_BP512R1_ENABLED)
    { POLARSSL_ECP_DP_BP512R1,      28,     512,    "brainpoolP512r1"   },
#endif
139
#if defined(POLARSSL_ECP_DP_SECP384R1_ENABLED)
140
    { POLARSSL_ECP_DP_SECP384R1,    24,     384,    "secp384r1"         },
141
#endif
142 143 144
#if defined(POLARSSL_ECP_DP_BP384R1_ENABLED)
    { POLARSSL_ECP_DP_BP384R1,      27,     384,    "brainpoolP384r1"   },
#endif
145
#if defined(POLARSSL_ECP_DP_SECP256R1_ENABLED)
146
    { POLARSSL_ECP_DP_SECP256R1,    23,     256,    "secp256r1"         },
147
#endif
148 149 150
#if defined(POLARSSL_ECP_DP_SECP256K1_ENABLED)
    { POLARSSL_ECP_DP_SECP256K1,    22,     256,    "secp256k1"         },
#endif
151 152 153
#if defined(POLARSSL_ECP_DP_BP256R1_ENABLED)
    { POLARSSL_ECP_DP_BP256R1,      26,     256,    "brainpoolP256r1"   },
#endif
154
#if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED)
155
    { POLARSSL_ECP_DP_SECP224R1,    21,     224,    "secp224r1"         },
156
#endif
157 158 159
#if defined(POLARSSL_ECP_DP_SECP224K1_ENABLED)
    { POLARSSL_ECP_DP_SECP224K1,    20,     224,    "secp224k1"         },
#endif
160 161 162
#if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
    { POLARSSL_ECP_DP_SECP192R1,    19,     192,    "secp192r1"         },
#endif
163 164
#if defined(POLARSSL_ECP_DP_SECP192K1_ENABLED)
    { POLARSSL_ECP_DP_SECP192K1,    18,     192,    "secp192k1"         },
165
#endif
166
    { POLARSSL_ECP_DP_NONE,          0,     0,      NULL                },
167
};
168

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

static ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
173

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

182
/*
183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204
 * List of supported curves, group ID only
 */
const ecp_group_id *ecp_grp_id_list( void )
{
    static int init_done = 0;

    if( ! init_done )
    {
        size_t i = 0;
        const ecp_curve_info *curve_info;

        for( curve_info = ecp_curve_list();
             curve_info->grp_id != POLARSSL_ECP_DP_NONE;
             curve_info++ )
        {
            ecp_supported_grp_id[i++] = curve_info->grp_id;
        }
        ecp_supported_grp_id[i] = POLARSSL_ECP_DP_NONE;

        init_done = 1;
    }

205
    return( ecp_supported_grp_id );
206 207 208 209
}

/*
 * Get the curve info for the internal identifier
210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243
 */
const ecp_curve_info *ecp_curve_info_from_grp_id( ecp_group_id grp_id )
{
    const ecp_curve_info *curve_info;

    for( curve_info = ecp_curve_list();
         curve_info->grp_id != POLARSSL_ECP_DP_NONE;
         curve_info++ )
    {
        if( curve_info->grp_id == grp_id )
            return( curve_info );
    }

    return( NULL );
}

/*
 * Get the curve info from the TLS identifier
 */
const ecp_curve_info *ecp_curve_info_from_tls_id( uint16_t tls_id )
{
    const ecp_curve_info *curve_info;

    for( curve_info = ecp_curve_list();
         curve_info->grp_id != POLARSSL_ECP_DP_NONE;
         curve_info++ )
    {
        if( curve_info->tls_id == tls_id )
            return( curve_info );
    }

    return( NULL );
}

244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261
/*
 * Get the curve info from the name
 */
const ecp_curve_info *ecp_curve_info_from_name( const char *name )
{
    const ecp_curve_info *curve_info;

    for( curve_info = ecp_curve_list();
         curve_info->grp_id != POLARSSL_ECP_DP_NONE;
         curve_info++ )
    {
        if( strcasecmp( curve_info->name, name ) == 0 )
            return( curve_info );
    }

    return( NULL );
}

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

    if( grp->G.Y.p == NULL )
        return( POLARSSL_ECP_TYPE_MONTGOMERY );
    else
        return( POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS );
274 275
}

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

284 285
    mpi_init( &pt->X );
    mpi_init( &pt->Y );
286
    mpi_init( &pt->Z );
287 288 289 290 291 292 293 294 295 296
}

/*
 * Initialize (the components of) a group
 */
void ecp_group_init( ecp_group *grp )
{
    if( grp == NULL )
        return;

297
    memset( grp, 0, sizeof( ecp_group ) );
298 299
}

300 301 302 303 304
/*
 * Initialize (the components of) a key pair
 */
void ecp_keypair_init( ecp_keypair *key )
{
305
    if( key == NULL )
306 307 308 309 310 311 312
        return;

    ecp_group_init( &key->grp );
    mpi_init( &key->d );
    ecp_point_init( &key->Q );
}

313 314 315 316 317 318 319 320 321 322
/*
 * Unallocate (the components of) a point
 */
void ecp_point_free( ecp_point *pt )
{
    if( pt == NULL )
        return;

    mpi_free( &( pt->X ) );
    mpi_free( &( pt->Y ) );
323
    mpi_free( &( pt->Z ) );
324 325 326 327 328 329 330
}

/*
 * Unallocate (the components of) a group
 */
void ecp_group_free( ecp_group *grp )
{
331 332
    size_t i;

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

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

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

352
    polarssl_zeroize( grp, sizeof( ecp_group ) );
353
}
354

355 356 357 358 359
/*
 * Unallocate (the components of) a key pair
 */
void ecp_keypair_free( ecp_keypair *key )
{
360
    if( key == NULL )
361 362 363 364 365 366 367
        return;

    ecp_group_free( &key->grp );
    mpi_free( &key->d );
    ecp_point_free( &key->Q );
}

368
/*
369
 * Copy the contents of a point
370 371 372
 */
int ecp_copy( ecp_point *P, const ecp_point *Q )
{
373
    int ret;
374 375 376

    MPI_CHK( mpi_copy( &P->X, &Q->X ) );
    MPI_CHK( mpi_copy( &P->Y, &Q->Y ) );
377
    MPI_CHK( mpi_copy( &P->Z, &Q->Z ) );
378 379 380 381

cleanup:
    return( ret );
}
382

383 384 385 386 387 388 389 390
/*
 * Copy the contents of a group object
 */
int ecp_group_copy( ecp_group *dst, const ecp_group *src )
{
    return ecp_use_known_dp( dst, src->id );
}

391
/*
392
 * Set point to zero
393
 */
394
int ecp_set_zero( ecp_point *pt )
395
{
396
    int ret;
397

398 399 400
    MPI_CHK( mpi_lset( &pt->X , 1 ) );
    MPI_CHK( mpi_lset( &pt->Y , 1 ) );
    MPI_CHK( mpi_lset( &pt->Z , 0 ) );
401 402 403 404 405 406

cleanup:
    return( ret );
}

/*
407
 * Tell if a point is zero
408
 */
409
int ecp_is_zero( ecp_point *pt )
410
{
411
    return( mpi_cmp_int( &pt->Z, 0 ) == 0 );
412 413 414
}

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

422 423 424
    MPI_CHK( mpi_read_string( &P->X, radix, x ) );
    MPI_CHK( mpi_read_string( &P->Y, radix, y ) );
    MPI_CHK( mpi_lset( &P->Z, 1 ) );
425 426

cleanup:
427 428 429
    return( ret );
}

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

440 441
    if( format != POLARSSL_ECP_PF_UNCOMPRESSED &&
        format != POLARSSL_ECP_PF_COMPRESSED )
442
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
443

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

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

        return( 0 );
    }

    plen = mpi_size( &grp->P );

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

        if( buflen < *olen )
465
            return( POLARSSL_ERR_ECP_BUFFER_TOO_SMALL );
466

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

        if( buflen < *olen )
476
            return( POLARSSL_ERR_ECP_BUFFER_TOO_SMALL );
477 478 479 480

        buf[0] = 0x02 + mpi_get_bit( &P->Y, 0 );
        MPI_CHK( mpi_write_binary( &P->X, buf + 1, plen ) );
    }
481 482 483 484 485

cleanup:
    return( ret );
}

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

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

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

506
    plen = mpi_size( &grp->P );
507

508 509 510 511
    if( buf[0] != 0x04 )
        return( POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE );

    if( ilen != 2 * plen + 1 )
512
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
513

514 515 516
    MPI_CHK( mpi_read_binary( &pt->X, buf + 1, plen ) );
    MPI_CHK( mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) );
    MPI_CHK( mpi_lset( &pt->Z, 1 ) );
517 518 519 520 521

cleanup:
    return( ret );
}

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

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

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

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

    return ecp_point_read_binary( grp, pt, buf_start, data_len );
551 552 553 554 555 556 557 558 559
}

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

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

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

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

581
    return( 0 );
582 583
}

584
/*
585
 * Import an ECP group from ASCII strings, case A == -3
586
 */
587 588
int ecp_group_read_string( ecp_group *grp, int radix,
                           const char *p, const char *b,
589
                           const char *gx, const char *gy, const char *n)
590
{
591
    int ret;
592

593 594 595 596
    MPI_CHK( mpi_read_string( &grp->P, radix, p ) );
    MPI_CHK( mpi_read_string( &grp->B, radix, b ) );
    MPI_CHK( ecp_point_read_string( &grp->G, radix, gx, gy ) );
    MPI_CHK( mpi_read_string( &grp->N, radix, n ) );
597

598 599
    grp->pbits = mpi_msb( &grp->P );
    grp->nbits = mpi_msb( &grp->N );
600 601

cleanup:
602 603
    if( ret != 0 )
        ecp_group_free( grp );
604

605
    return( ret );
606 607
}

608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669
/*
 * Set a group from an ECParameters record (RFC 4492)
 */
int ecp_tls_read_group( ecp_group *grp, const unsigned char **buf, size_t len )
{
    uint16_t tls_id;
    const ecp_curve_info *curve_info;

    /*
     * We expect at least three bytes (see below)
     */
    if( len < 3 )
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );

    /*
     * First byte is curve_type; only named_curve is handled
     */
    if( *(*buf)++ != POLARSSL_ECP_TLS_NAMED_CURVE )
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );

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

    if( ( curve_info = ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
        return( POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE );

    return ecp_use_known_dp( grp, curve_info->grp_id );
}

/*
 * Write the ECParameters record corresponding to a group (RFC 4492)
 */
int ecp_tls_write_group( const ecp_group *grp, size_t *olen,
                         unsigned char *buf, size_t blen )
{
    const ecp_curve_info *curve_info;

    if( ( curve_info = ecp_curve_info_from_grp_id( grp->id ) ) == NULL )
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );

    /*
     * We are going to write 3 bytes (see below)
     */
    *olen = 3;
    if( blen < *olen )
        return( POLARSSL_ERR_ECP_BUFFER_TOO_SMALL );

    /*
     * First byte is curve_type, always named_curve
     */
    *buf++ = POLARSSL_ECP_TLS_NAMED_CURVE;

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

670
    return( 0 );
671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719
}

/*
 * Wrapper around fast quasi-modp functions, with fall-back to mpi_mod_mpi.
 * See the documentation of struct ecp_group.
 *
 * This function is in the critial loop for ecp_mul, so pay attention to perf.
 */
static int ecp_modp( mpi *N, const ecp_group *grp )
{
    int ret;

    if( grp->modp == NULL )
        return( mpi_mod_mpi( N, N, &grp->P ) );

    /* N->s < 0 is a much faster test, which fails only if N is 0 */
    if( ( N->s < 0 && mpi_cmp_int( N, 0 ) != 0 ) ||
        mpi_msb( N ) > 2 * grp->pbits )
    {
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
    }

    MPI_CHK( grp->modp( N ) );

    /* N->s < 0 is a much faster test, which fails only if N is 0 */
    while( N->s < 0 && mpi_cmp_int( N, 0 ) != 0 )
        MPI_CHK( mpi_add_mpi( N, N, &grp->P ) );

    while( mpi_cmp_mpi( N, &grp->P ) >= 0 )
        /* we known P, N and the result are positive */
        MPI_CHK( mpi_sub_abs( N, N, &grp->P ) );

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
 * mpi_mul_mpi are in the 0..p range. So, after each operation we will
 * bring the result back to this range.
 *
 * The following macros are shortcuts for doing that.
 */

/*
 * Reduce a mpi mod p in-place, general case, to use after mpi_mul_mpi
 */
720 721 722 723 724 725 726 727
#if defined(POLARSSL_SELF_TEST)
#define INC_MUL_COUNT   mul_count++;
#else
#define INC_MUL_COUNT
#endif

#define MOD_MUL( N )    do { MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
                        while( 0 )
728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745

/*
 * Reduce a mpi mod p in-place, to use after mpi_sub_mpi
 * N->s < 0 is a very fast test, which fails only if N is 0
 */
#define MOD_SUB( N )                                \
    while( N.s < 0 && mpi_cmp_int( &N, 0 ) != 0 )   \
        MPI_CHK( mpi_add_mpi( &N, &N, &grp->P ) )

/*
 * Reduce a mpi mod p in-place, to use after mpi_add_mpi and mpi_mul_int.
 * We known P, N and the result are positive, so sub_abs is correct, and
 * a bit faster.
 */
#define MOD_ADD( N )                                \
    while( mpi_cmp_mpi( &N, &grp->P ) >= 0 )        \
        MPI_CHK( mpi_sub_abs( &N, &N, &grp->P ) )

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
746 747 748 749 750 751 752 753 754
#if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
/*
 * 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.
 */

755 756
/*
 * Normalize jacobian coordinates so that Z == 0 || Z == 1  (GECC 3.2.1)
757
 * Cost: 1N := 1I + 3M + 1S
758
 */
759
static int ecp_normalize_jac( const ecp_group *grp, ecp_point *pt )
760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793
{
    int ret;
    mpi Zi, ZZi;

    if( mpi_cmp_int( &pt->Z, 0 ) == 0 )
        return( 0 );

    mpi_init( &Zi ); mpi_init( &ZZi );

    /*
     * X = X / Z^2  mod p
     */
    MPI_CHK( mpi_inv_mod( &Zi,      &pt->Z,     &grp->P ) );
    MPI_CHK( mpi_mul_mpi( &ZZi,     &Zi,        &Zi     ) ); MOD_MUL( ZZi );
    MPI_CHK( mpi_mul_mpi( &pt->X,   &pt->X,     &ZZi    ) ); MOD_MUL( pt->X );

    /*
     * Y = Y / Z^3  mod p
     */
    MPI_CHK( mpi_mul_mpi( &pt->Y,   &pt->Y,     &ZZi    ) ); MOD_MUL( pt->Y );
    MPI_CHK( mpi_mul_mpi( &pt->Y,   &pt->Y,     &Zi     ) ); MOD_MUL( pt->Y );

    /*
     * Z = 1
     */
    MPI_CHK( mpi_lset( &pt->Z, 1 ) );

cleanup:

    mpi_free( &Zi ); mpi_free( &ZZi );

    return( ret );
}

794
/*
795
 * Normalize jacobian coordinates of an array of (pointers to) points,
796 797 798 799 800
 * 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!
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
801
 * This should never happen, see choice of w in ecp_mul_comb().
802 803
 *
 * Cost: 1N(t) := 1I + (6t - 3)M + 1S
804
 */
805
static int ecp_normalize_jac_many( const ecp_group *grp,
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
806
                                   ecp_point *T[], size_t t_len )
807
{
808 809 810
    int ret;
    size_t i;
    mpi *c, u, Zi, ZZi;
811

812
    if( t_len < 2 )
813
        return( ecp_normalize_jac( grp, *T ) );
814 815 816 817 818 819 820 821 822 823 824

    if( ( c = (mpi *) polarssl_malloc( t_len * sizeof( mpi ) ) ) == NULL )
        return( POLARSSL_ERR_ECP_MALLOC_FAILED );

    mpi_init( &u ); mpi_init( &Zi ); mpi_init( &ZZi );
    for( i = 0; i < t_len; i++ )
        mpi_init( &c[i] );

    /*
     * c[i] = Z_0 * ... * Z_i
     */
825
    MPI_CHK( mpi_copy( &c[0], &T[0]->Z ) );
826
    for( i = 1; i < t_len; i++ )
827
    {
828
        MPI_CHK( mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );
829 830
        MOD_MUL( c[i] );
    }
831

832 833 834 835
    /*
     * u = 1 / (Z_0 * ... * Z_n) mod P
     */
    MPI_CHK( mpi_inv_mod( &u, &c[t_len-1], &grp->P ) );
836

837 838 839 840 841 842 843 844 845 846 847
    for( i = t_len - 1; ; i-- )
    {
        /*
         * Zi = 1 / Z_i mod p
         * u = 1 / (Z_0 * ... * Z_i) mod P
         */
        if( i == 0 ) {
            MPI_CHK( mpi_copy( &Zi, &u ) );
        }
        else
        {
848 849
            MPI_CHK( mpi_mul_mpi( &Zi, &u, &c[i-1]  ) ); MOD_MUL( Zi );
            MPI_CHK( mpi_mul_mpi( &u,  &u, &T[i]->Z ) ); MOD_MUL( u );
850
        }
851

852 853 854
        /*
         * proceed as in normalize()
         */
855 856 857 858
        MPI_CHK( mpi_mul_mpi( &ZZi,     &Zi,      &Zi  ) ); MOD_MUL( ZZi );
        MPI_CHK( mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X );
        MPI_CHK( mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y );
        MPI_CHK( mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi  ) ); MOD_MUL( T[i]->Y );
859 860 861 862 863 864 865

        /*
         * 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.
         */
866 867
        MPI_CHK( mpi_shrink( &T[i]->X, grp->P.n ) );
        MPI_CHK( mpi_shrink( &T[i]->Y, grp->P.n ) );
868
        mpi_free( &T[i]->Z );
869

870 871 872 873 874 875 876 877 878 879 880 881 882 883
        if( i == 0 )
            break;
    }

cleanup:

    mpi_free( &u ); mpi_free( &Zi ); mpi_free( &ZZi );
    for( i = 0; i < t_len; i++ )
        mpi_free( &c[i] );
    polarssl_free( c );

    return( ret );
}

884 885 886 887
/*
 * 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
 */
888
static int ecp_safe_invert_jac( const ecp_group *grp,
889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908
                            ecp_point *Q,
                            unsigned char inv )
{
    int ret;
    unsigned char nonzero;
    mpi mQY;

    mpi_init( &mQY );

    /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */
    MPI_CHK( mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) );
    nonzero = mpi_cmp_int( &Q->Y, 0 ) != 0;
    MPI_CHK( mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) );

cleanup:
    mpi_free( &mQY );

    return( ret );
}

909 910 911 912 913 914 915
/*
 * Point doubling R = 2 P, Jacobian coordinates
 *
 * http://www.hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian/doubling/dbl-2007-bl.op3
 * with heavy variable renaming, some reordering and one minor modification
 * (a = 2 * b, c = d - 2a replaced with c = d, c = c - b, c = c - b)
 * in order to use a lot less intermediate variables (6 vs 25).
916 917
 *
 * Cost: 1D := 2M + 8S
918 919 920 921 922 923 924 925 926
 */
static int ecp_double_jac( const ecp_group *grp, ecp_point *R,
                           const ecp_point *P )
{
    int ret;
    mpi T1, T2, T3, X3, Y3, Z3;

#if defined(POLARSSL_SELF_TEST)
    dbl_count++;
927
#endif
928

929 930
    mpi_init( &T1 ); mpi_init( &T2 ); mpi_init( &T3 );
    mpi_init( &X3 ); mpi_init( &Y3 ); mpi_init( &Z3 );
931

932 933 934 935 936 937 938 939 940 941 942
    MPI_CHK( mpi_mul_mpi( &T3,  &P->X,  &P->X   ) ); MOD_MUL( T3 );
    MPI_CHK( mpi_mul_mpi( &T2,  &P->Y,  &P->Y   ) ); MOD_MUL( T2 );
    MPI_CHK( mpi_mul_mpi( &Y3,  &T2,    &T2     ) ); MOD_MUL( Y3 );
    MPI_CHK( mpi_add_mpi( &X3,  &P->X,  &T2     ) ); MOD_ADD( X3 );
    MPI_CHK( mpi_mul_mpi( &X3,  &X3,    &X3     ) ); MOD_MUL( X3 );
    MPI_CHK( mpi_sub_mpi( &X3,  &X3,    &Y3     ) ); MOD_SUB( X3 );
    MPI_CHK( mpi_sub_mpi( &X3,  &X3,    &T3     ) ); MOD_SUB( X3 );
    MPI_CHK( mpi_mul_int( &T1,  &X3,    2       ) ); MOD_ADD( T1 );
    MPI_CHK( mpi_mul_mpi( &Z3,  &P->Z,  &P->Z   ) ); MOD_MUL( Z3 );
    MPI_CHK( mpi_mul_mpi( &X3,  &Z3,    &Z3     ) ); MOD_MUL( X3 );
    MPI_CHK( mpi_mul_int( &T3,  &T3,    3       ) ); MOD_ADD( T3 );
943 944 945 946 947 948 949 950 951

    /* Special case for A = -3 */
    if( grp->A.p == NULL )
    {
        MPI_CHK( mpi_mul_int( &X3, &X3, 3 ) );
        X3.s = -1; /* mpi_mul_int doesn't handle negative numbers */
        MOD_SUB( X3 );
    }
    else
Peter Vaskovic's avatar
Peter Vaskovic committed
952
    {
953
        MPI_CHK( mpi_mul_mpi( &X3,  &X3,    &grp->A ) ); MOD_MUL( X3 );
Peter Vaskovic's avatar
Peter Vaskovic committed
954
    }
955

956 957 958 959 960 961 962 963 964 965 966 967
    MPI_CHK( mpi_add_mpi( &T3,  &T3,    &X3     ) ); MOD_ADD( T3 );
    MPI_CHK( mpi_mul_mpi( &X3,  &T3,    &T3     ) ); MOD_MUL( X3 );
    MPI_CHK( mpi_sub_mpi( &X3,  &X3,    &T1     ) ); MOD_SUB( X3 );
    MPI_CHK( mpi_sub_mpi( &X3,  &X3,    &T1     ) ); MOD_SUB( X3 );
    MPI_CHK( mpi_sub_mpi( &T1,  &T1,    &X3     ) ); MOD_SUB( T1 );
    MPI_CHK( mpi_mul_mpi( &T1,  &T3,    &T1     ) ); MOD_MUL( T1 );
    MPI_CHK( mpi_mul_int( &T3,  &Y3,    8       ) ); MOD_ADD( T3 );
    MPI_CHK( mpi_sub_mpi( &Y3,  &T1,    &T3     ) ); MOD_SUB( Y3 );
    MPI_CHK( mpi_add_mpi( &T1,  &P->Y,  &P->Z   ) ); MOD_ADD( T1 );
    MPI_CHK( mpi_mul_mpi( &T1,  &T1,    &T1     ) ); MOD_MUL( T1 );
    MPI_CHK( mpi_sub_mpi( &T1,  &T1,    &T2     ) ); MOD_SUB( T1 );
    MPI_CHK( mpi_sub_mpi( &Z3,  &T1,    &Z3     ) ); MOD_SUB( Z3 );
968

969 970 971
    MPI_CHK( mpi_copy( &R->X, &X3 ) );
    MPI_CHK( mpi_copy( &R->Y, &Y3 ) );
    MPI_CHK( mpi_copy( &R->Z, &Z3 ) );
972

973 974 975 976 977
cleanup:
    mpi_free( &T1 ); mpi_free( &T2 ); mpi_free( &T3 );
    mpi_free( &X3 ); mpi_free( &Y3 ); mpi_free( &Z3 );

    return( ret );
978 979 980
}

/*
981
 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
982 983 984 985
 *
 * The coordinates of Q must be normalized (= affine),
 * but those of P don't need to. R is not normalized.
 *
986
 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
987
 * None of these cases can happen as intermediate step in ecp_mul_comb():
988 989 990 991 992 993
 * - 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.
 *
994 995
 * We accept Q->Z being unset (saving memory in tables) as meaning 1.
 *
996
 * Cost: 1A := 8M + 3S
997
 */
998
static int ecp_add_mixed( const ecp_group *grp, ecp_point *R,
999
                          const ecp_point *P, const ecp_point *Q )
1000
{
1001 1002 1003 1004 1005 1006
    int ret;
    mpi T1, T2, T3, T4, X, Y, Z;

#if defined(POLARSSL_SELF_TEST)
    add_count++;
#endif
1007 1008

    /*
1009
     * Trivial cases: P == 0 or Q == 0 (case 1)
1010
     */
1011
    if( mpi_cmp_int( &P->Z, 0 ) == 0 )
1012
        return( ecp_copy( R, Q ) );
1013

1014
    if( Q->Z.p != NULL && mpi_cmp_int( &Q->Z, 0 ) == 0 )
1015
        return( ecp_copy( R, P ) );
1016 1017

    /*
1018
     * Make sure Q coordinates are normalized
1019
     */
1020
    if( Q->Z.p != NULL && mpi_cmp_int( &Q->Z, 1 ) != 0 )
1021 1022
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );

1023 1024 1025 1026 1027 1028 1029 1030 1031
    mpi_init( &T1 ); mpi_init( &T2 ); mpi_init( &T3 ); mpi_init( &T4 );
    mpi_init( &X ); mpi_init( &Y ); mpi_init( &Z );

    MPI_CHK( mpi_mul_mpi( &T1,  &P->Z,  &P->Z ) );  MOD_MUL( T1 );
    MPI_CHK( mpi_mul_mpi( &T2,  &T1,    &P->Z ) );  MOD_MUL( T2 );
    MPI_CHK( mpi_mul_mpi( &T1,  &T1,    &Q->X ) );  MOD_MUL( T1 );
    MPI_CHK( mpi_mul_mpi( &T2,  &T2,    &Q->Y ) );  MOD_MUL( T2 );
    MPI_CHK( mpi_sub_mpi( &T1,  &T1,    &P->X ) );  MOD_SUB( T1 );
    MPI_CHK( mpi_sub_mpi( &T2,  &T2,    &P->Y ) );  MOD_SUB( T2 );
1032

1033
    /* Special cases (2) and (3) */
1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046
    if( mpi_cmp_int( &T1, 0 ) == 0 )
    {
        if( mpi_cmp_int( &T2, 0 ) == 0 )
        {
            ret = ecp_double_jac( grp, R, P );
            goto cleanup;
        }
        else
        {
            ret = ecp_set_zero( R );
            goto cleanup;
        }
    }
1047

1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059
    MPI_CHK( mpi_mul_mpi( &Z,   &P->Z,  &T1   ) );  MOD_MUL( Z  );
    MPI_CHK( mpi_mul_mpi( &T3,  &T1,    &T1   ) );  MOD_MUL( T3 );
    MPI_CHK( mpi_mul_mpi( &T4,  &T3,    &T1   ) );  MOD_MUL( T4 );
    MPI_CHK( mpi_mul_mpi( &T3,  &T3,    &P->X ) );  MOD_MUL( T3 );
    MPI_CHK( mpi_mul_int( &T1,  &T3,    2     ) );  MOD_ADD( T1 );
    MPI_CHK( mpi_mul_mpi( &X,   &T2,    &T2   ) );  MOD_MUL( X  );
    MPI_CHK( mpi_sub_mpi( &X,   &X,     &T1   ) );  MOD_SUB( X  );
    MPI_CHK( mpi_sub_mpi( &X,   &X,     &T4   ) );  MOD_SUB( X  );
    MPI_CHK( mpi_sub_mpi( &T3,  &T3,    &X    ) );  MOD_SUB( T3 );
    MPI_CHK( mpi_mul_mpi( &T3,  &T3,    &T2   ) );  MOD_MUL( T3 );
    MPI_CHK( mpi_mul_mpi( &T4,  &T4,    &P->Y ) );  MOD_MUL( T4 );
    MPI_CHK( mpi_sub_mpi( &Y,   &T3,    &T4   ) );  MOD_SUB( Y  );
1060

1061 1062 1063
    MPI_CHK( mpi_copy( &R->X, &X ) );
    MPI_CHK( mpi_copy( &R->Y, &Y ) );
    MPI_CHK( mpi_copy( &R->Z, &Z ) );