ecp.c 53 KB
Newer Older
1
/*
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
2
 *  Elliptic curves over GF(p): generic functions
3
 *
Paul Bakker's avatar
Paul Bakker committed
4
 *  Copyright (C) 2006-2013, Brainspark B.V.
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
 *
 *  This file is part of PolarSSL (http://www.polarssl.org)
 *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
 *
 *  All rights reserved.
 *
 *  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:
 *
29
 * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
30
 * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone
31
 * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
32
 * RFC 4492 for the related TLS structures and constants
33
 *
34 35
 * [M255] http://cr.yp.to/ecdh/curve25519-20060209.pdf
 *
36 37 38 39
 * [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>
40 41 42 43 44
 *
 * [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>
45 46 47 48 49 50 51
 */

#include "polarssl/config.h"

#if defined(POLARSSL_ECP_C)

#include "polarssl/ecp.h"
52 53 54 55 56 57 58 59

#if defined(POLARSSL_MEMORY_C)
#include "polarssl/memory.h"
#else
#define polarssl_malloc     malloc
#define polarssl_free       free
#endif

60
#include <stdlib.h>
61

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

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

75 76
#if defined(POLARSSL_SELF_TEST)
/*
77
 * Counts of point addition and doubling, and field multiplications.
78
 * Used to test resistance of point multiplication to simple timing attacks.
79
 */
80
static unsigned long add_count, dbl_count, mul_count;
81 82
#endif

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
#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)   ||   \
    defined(POLARSSL_ECP_DP_BP512R1_ENABLED)
#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;

111 112 113
/*
 * List of supported curves:
 *  - internal ID
114
 *  - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2)
115
 *  - size in bits
116
 *  - readable name
117
 */
118
static const ecp_curve_info ecp_supported_curves[] =
119
{
120
#if defined(POLARSSL_ECP_DP_BP512R1_ENABLED)
121
    { POLARSSL_ECP_DP_BP512R1,      28,     512,    "brainpoolP512r1"   },
122 123
#endif
#if defined(POLARSSL_ECP_DP_BP384R1_ENABLED)
124
    { POLARSSL_ECP_DP_BP384R1,      27,     384,    "brainpoolP384r1"   },
125 126
#endif
#if defined(POLARSSL_ECP_DP_BP256R1_ENABLED)
127
    { POLARSSL_ECP_DP_BP256R1,      26,     256,    "brainpoolP256r1"   },
128
#endif
129
#if defined(POLARSSL_ECP_DP_SECP521R1_ENABLED)
130
    { POLARSSL_ECP_DP_SECP521R1,    25,     521,    "secp521r1"         },
131 132
#endif
#if defined(POLARSSL_ECP_DP_SECP384R1_ENABLED)
133
    { POLARSSL_ECP_DP_SECP384R1,    24,     384,    "secp384r1"         },
134 135
#endif
#if defined(POLARSSL_ECP_DP_SECP256R1_ENABLED)
136
    { POLARSSL_ECP_DP_SECP256R1,    23,     256,    "secp256r1"         },
137 138
#endif
#if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED)
139
    { POLARSSL_ECP_DP_SECP224R1,    21,     224,    "secp224r1"         },
140 141
#endif
#if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
142
    { POLARSSL_ECP_DP_SECP192R1,    19,     192,    "secp192r1"         },
143
#endif
144
    { POLARSSL_ECP_DP_NONE,          0,     0,      NULL                },
145 146
};

147 148 149 150 151 152 153 154
/*
 * List of supported curves and associated info
 */
const ecp_curve_info *ecp_curve_list( void )
{
    return ecp_supported_curves;
}

155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
/*
 * Get the curve info for the internal identifer
 */
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 );
}

191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208
/*
 * 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 );
}

209
/*
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
210
 * Get the type of a curve
211
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
212
static inline ecp_curve_type ecp_get_type( const ecp_group *grp )
213
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
214 215 216 217 218 219 220
    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 );
221 222
}

223
/*
224
 * Initialize (the components of) a point
225 226 227 228 229 230
 */
void ecp_point_init( ecp_point *pt )
{
    if( pt == NULL )
        return;

231 232
    mpi_init( &pt->X );
    mpi_init( &pt->Y );
233
    mpi_init( &pt->Z );
234 235 236 237 238 239 240 241 242 243
}

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

244
    memset( grp, 0, sizeof( ecp_group ) );
245 246
}

247 248 249 250 251 252 253 254 255 256 257 258 259
/*
 * Initialize (the components of) a key pair
 */
void ecp_keypair_init( ecp_keypair *key )
{
    if ( key == NULL )
        return;

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

260 261 262 263 264 265 266 267 268 269
/*
 * 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 ) );
270
    mpi_free( &( pt->Z ) );
271 272 273 274 275 276 277
}

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

280 281 282
    if( grp == NULL )
        return;

283 284 285 286 287 288 289 290
    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 );
    }
291

292 293 294 295 296 297 298
    if( grp->T != NULL )
    {
        for( i = 0; i < grp->T_size; i++ )
            ecp_point_free( &grp->T[i] );
        polarssl_free( grp->T );
    }

299
    memset( grp, 0, sizeof( ecp_group ) );
300
}
301

302 303 304 305 306 307 308 309 310 311 312 313 314
/*
 * Unallocate (the components of) a key pair
 */
void ecp_keypair_free( ecp_keypair *key )
{
    if ( key == NULL )
        return;

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

315
/*
316
 * Copy the contents of a point
317 318 319
 */
int ecp_copy( ecp_point *P, const ecp_point *Q )
{
320
    int ret;
321 322 323

    MPI_CHK( mpi_copy( &P->X, &Q->X ) );
    MPI_CHK( mpi_copy( &P->Y, &Q->Y ) );
324
    MPI_CHK( mpi_copy( &P->Z, &Q->Z ) );
325 326 327 328

cleanup:
    return( ret );
}
329

330 331 332 333 334 335 336 337
/*
 * 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 );
}

338
/*
339
 * Set point to zero
340
 */
341
int ecp_set_zero( ecp_point *pt )
342
{
343
    int ret;
344

345 346 347
    MPI_CHK( mpi_lset( &pt->X , 1 ) );
    MPI_CHK( mpi_lset( &pt->Y , 1 ) );
    MPI_CHK( mpi_lset( &pt->Z , 0 ) );
348 349 350 351 352 353

cleanup:
    return( ret );
}

/*
354
 * Tell if a point is zero
355
 */
356
int ecp_is_zero( ecp_point *pt )
357
{
358
    return( mpi_cmp_int( &pt->Z, 0 ) == 0 );
359 360 361
}

/*
362
 * Import a non-zero point from ASCII strings
363
 */
364 365
int ecp_point_read_string( ecp_point *P, int radix,
                           const char *x, const char *y )
366
{
367
    int ret;
368

369 370 371
    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 ) );
372 373

cleanup:
374 375 376
    return( ret );
}

377
/*
378
 * Export a point into unsigned binary data (SEC1 2.3.3)
379
 */
380
int ecp_point_write_binary( const ecp_group *grp, const ecp_point *P,
381
                            int format, size_t *olen,
382
                            unsigned char *buf, size_t buflen )
383
{
384
    int ret = 0;
385 386
    size_t plen;

387 388
    if( format != POLARSSL_ECP_PF_UNCOMPRESSED &&
        format != POLARSSL_ECP_PF_COMPRESSED )
389
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
390

391
    /*
392
     * Common case: P == 0
393 394 395 396
     */
    if( mpi_cmp_int( &P->Z, 0 ) == 0 )
    {
        if( buflen < 1 )
397
            return( POLARSSL_ERR_ECP_BUFFER_TOO_SMALL );
398 399 400 401 402 403 404 405 406

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

        return( 0 );
    }

    plen = mpi_size( &grp->P );

407 408 409 410 411
    if( format == POLARSSL_ECP_PF_UNCOMPRESSED )
    {
        *olen = 2 * plen + 1;

        if( buflen < *olen )
412
            return( POLARSSL_ERR_ECP_BUFFER_TOO_SMALL );
413

414 415 416 417 418 419 420 421 422
        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 )
423
            return( POLARSSL_ERR_ECP_BUFFER_TOO_SMALL );
424 425 426 427

        buf[0] = 0x02 + mpi_get_bit( &P->Y, 0 );
        MPI_CHK( mpi_write_binary( &P->X, buf + 1, plen ) );
    }
428 429 430 431 432

cleanup:
    return( ret );
}

433 434 435
/*
 * Import a point from unsigned binary data (SEC1 2.3.4)
 */
436 437
int ecp_point_read_binary( const ecp_group *grp, ecp_point *pt,
                           const unsigned char *buf, size_t ilen ) {
438 439 440 441
    int ret;
    size_t plen;

    if( ilen == 1 && buf[0] == 0x00 )
442
        return( ecp_set_zero( pt ) );
443

444
    plen = mpi_size( &grp->P );
445 446

    if( ilen != 2 * plen + 1 || buf[0] != 0x04 )
447
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
448

449 450 451
    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 ) );
452 453 454 455 456

cleanup:
    return( ret );
}

457 458 459 460 461 462 463
/*
 * 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,
464
                        const unsigned char **buf, size_t buf_len )
465 466
{
    unsigned char data_len;
467
    const unsigned char *buf_start;
468 469 470 471 472 473 474

    /*
     * We must have at least two bytes (1 for length, at least of for data)
     */
    if( buf_len < 2 )
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );

475
    data_len = *(*buf)++;
476 477 478
    if( data_len < 1 || data_len > buf_len - 1 )
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );

479 480 481 482 483 484 485
    /*
     * 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 );
486 487 488 489 490 491 492 493 494
}

/*
 * 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,
495 496
                         int format, size_t *olen,
                         unsigned char *buf, size_t blen )
497
{
498 499
    int ret;

500
    /*
501
     * buffer length must be at least one, for our length byte
502
     */
503
    if( blen < 1 )
504 505
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );

506 507 508 509 510 511 512
    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
     */
513
    buf[0] = (unsigned char) *olen;
514 515 516
    ++*olen;

    return 0;
517 518
}

519
/*
520
 * Import an ECP group from ASCII strings, case A == -3
521
 */
522 523
int ecp_group_read_string( ecp_group *grp, int radix,
                           const char *p, const char *b,
524
                           const char *gx, const char *gy, const char *n)
525
{
526
    int ret;
527

528 529 530 531
    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 ) );
532

533 534
    grp->pbits = mpi_msb( &grp->P );
    grp->nbits = mpi_msb( &grp->N );
535 536

cleanup:
537 538
    if( ret != 0 )
        ecp_group_free( grp );
539

540
    return( ret );
541 542
}

543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 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
/*
 * 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;

    return 0;
}

/*
 * 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
 */
655 656 657 658 659 660 661 662
#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 )
663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680

/*
 * 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
681 682 683 684 685 686 687 688 689
#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.
 */

690 691
/*
 * Normalize jacobian coordinates so that Z == 0 || Z == 1  (GECC 3.2.1)
692
 * Cost: 1N := 1I + 3M + 1S
693
 */
694
static int ecp_normalize_jac( const ecp_group *grp, ecp_point *pt )
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 720 721 722 723 724 725 726 727 728
{
    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 );
}

729
/*
730
 * Normalize jacobian coordinates of an array of (pointers to) points,
731 732 733 734 735
 * 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
736
 * This should never happen, see choice of w in ecp_mul_comb().
737 738
 *
 * Cost: 1N(t) := 1I + (6t - 3)M + 1S
739
 */
740
static int ecp_normalize_jac_many( const ecp_group *grp,
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
741
                                   ecp_point *T[], size_t t_len )
742
{
743 744 745
    int ret;
    size_t i;
    mpi *c, u, Zi, ZZi;
746

747
    if( t_len < 2 )
748
        return( ecp_normalize_jac( grp, *T ) );
749 750 751 752 753 754 755 756 757 758 759

    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
     */
760
    MPI_CHK( mpi_copy( &c[0], &T[0]->Z ) );
761
    for( i = 1; i < t_len; i++ )
762
    {
763
        MPI_CHK( mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );
764 765
        MOD_MUL( c[i] );
    }
766

767 768 769 770
    /*
     * u = 1 / (Z_0 * ... * Z_n) mod P
     */
    MPI_CHK( mpi_inv_mod( &u, &c[t_len-1], &grp->P ) );
771

772 773 774 775 776 777 778 779 780 781 782
    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
        {
783 784
            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 );
785
        }
786

787 788 789
        /*
         * proceed as in normalize()
         */
790 791 792 793 794
        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 );
        MPI_CHK( mpi_lset( &T[i]->Z, 1 ) );
795

796 797 798 799 800 801 802 803 804 805 806 807 808 809
        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 );
}

810 811 812 813
/*
 * 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
 */
814
static int ecp_safe_invert_jac( const ecp_group *grp,
815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834
                            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 );
}

835 836 837 838 839 840 841
/*
 * 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).
842 843
 *
 * Cost: 1D := 2M + 8S
844 845 846 847 848 849 850 851 852
 */
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++;
853
#endif
854

855 856
    mpi_init( &T1 ); mpi_init( &T2 ); mpi_init( &T3 );
    mpi_init( &X3 ); mpi_init( &Y3 ); mpi_init( &Z3 );
857

858 859 860 861 862 863 864 865 866 867 868
    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 );
869 870 871 872 873 874 875 876 877 878 879

    /* 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
        MPI_CHK( mpi_mul_mpi( &X3,  &X3,    &grp->A ) ); MOD_MUL( X3 );

880 881 882 883 884 885 886 887 888 889 890 891
    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 );
892

893 894 895
    MPI_CHK( mpi_copy( &R->X, &X3 ) );
    MPI_CHK( mpi_copy( &R->Y, &Y3 ) );
    MPI_CHK( mpi_copy( &R->Z, &Z3 ) );
896

897 898 899 900 901
cleanup:
    mpi_free( &T1 ); mpi_free( &T2 ); mpi_free( &T3 );
    mpi_free( &X3 ); mpi_free( &Y3 ); mpi_free( &Z3 );

    return( ret );
902 903 904
}

/*
905
 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
906 907 908 909
 *
 * The coordinates of Q must be normalized (= affine),
 * but those of P don't need to. R is not normalized.
 *
910
 * 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
911
 * None of these cases can happen as intermediate step in ecp_mul_comb():
912 913 914 915 916 917
 * - 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.
 *
918
 * Cost: 1A := 8M + 3S
919
 */
920
static int ecp_add_mixed( const ecp_group *grp, ecp_point *R,
921
                          const ecp_point *P, const ecp_point *Q )
922
{
923 924 925 926 927 928
    int ret;
    mpi T1, T2, T3, T4, X, Y, Z;

#if defined(POLARSSL_SELF_TEST)
    add_count++;
#endif
929 930

    /*
931
     * Trivial cases: P == 0 or Q == 0 (case 1)
932
     */
933
    if( mpi_cmp_int( &P->Z, 0 ) == 0 )
934
        return( ecp_copy( R, Q ) );
935

936 937
    if( mpi_cmp_int( &Q->Z, 0 ) == 0 )
        return( ecp_copy( R, P ) );
938 939

    /*
940
     * Make sure Q coordinates are normalized
941
     */
942
    if( mpi_cmp_int( &Q->Z, 1 ) != 0 )
943 944
        return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );

945 946 947 948 949 950 951 952 953
    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 );
954

955
    /* Special cases (2) and (3) */
956 957 958 959 960 961 962 963 964 965 966 967 968
    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;
        }
    }
969

970 971 972 973 974 975 976 977 978 979 980 981
    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  );
982

983 984 985
    MPI_CHK( mpi_copy( &R->X, &X ) );
    MPI_CHK( mpi_copy( &R->Y, &Y ) );
    MPI_CHK( mpi_copy( &R->Z, &Z ) );
986

987
cleanup:
988

989 990
    mpi_free( &T1 ); mpi_free( &T2 ); mpi_free( &T3 ); mpi_free( &T4 );
    mpi_free( &X ); mpi_free( &Y ); mpi_free( &Z );
991

992
    return( ret );
993
}
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
994

995
/*
996
 * Addition: R = P + Q, result's coordinates normalized
997
 */
998 999
int ecp_add( const ecp_group *grp, ecp_point *R,
             const ecp_point *P, const ecp_point *Q )
1000
{
1001
    int ret;
1002

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
1003
    if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1004 1005
        return( POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE );

1006
    MPI_CHK( ecp_add_mixed( grp, R, P, Q ) );
1007
    MPI_CHK( ecp_normalize_jac( grp, R ) );
1008

1009 1010
cleanup:
    return( ret );
1011 1012
}

1013
/*
1014
 * Subtraction: R = P - Q, result's coordinates normalized
1015
 */
1016 1017
int ecp_sub( const ecp_group *grp, ecp_point *R,
             const ecp_point *P, const ecp_point *Q )
1018
{
1019
    int ret;
1020 1021 1022
    ecp_point mQ;

    ecp_point_init( &mQ );
1023

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
1024
    if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1025 1026
        return( POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE );

1027 1028 1029 1030 1031 1032
    /* mQ = - Q */
    ecp_copy( &mQ, Q );
    if( mpi_cmp_int( &mQ.Y, 0 ) != 0 )
        MPI_CHK( mpi_sub_mpi( &mQ.Y, &grp->P, &mQ.Y ) );

    MPI_CHK( ecp_add_mixed( grp, R, P, &mQ ) );
1033
    MPI_CHK( ecp_normalize_jac( grp, R ) );
1034

1035
cleanup:
1036 1037
    ecp_point_free( &mQ );

1038
    return( ret );
1039
}
1040

1041
/*
1042 1043
 * Randomize jacobian coordinates:
 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
1044
 * This is sort of the reverse operation of ecp_normalize_jac().
1045 1046
 *
 * This countermeasure was first suggested in [2].
1047
 */
1048
static int ecp_randomize_jac( const ecp_group *grp, ecp_point *pt,
1049
                int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1050 1051
{
    int ret;
1052 1053 1054
    mpi l, ll;
    size_t p_size = (grp->pbits + 7) / 8;
    int count = 0;