ecp.c 61.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
 *
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
 * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf
32
 *
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
 */

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
44
#if !defined(MBEDTLS_CONFIG_FILE)
45
#include "mbedtls/config.h"
46
#else
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
47
#include MBEDTLS_CONFIG_FILE
48
#endif
49

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
50
#if defined(MBEDTLS_ECP_C)
51

52
#include "mbedtls/ecp.h"
53

54 55
#include <string.h>

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
56
#if defined(MBEDTLS_PLATFORM_C)
57
#include "mbedtls/platform.h"
58
#else
59
#include <stdlib.h>
60
#include <stdio.h>
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
61
#define mbedtls_printf     printf
62
#define mbedtls_calloc    calloc
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
63
#define mbedtls_free       free
64 65
#endif

66 67 68 69
#if defined(__ARMCC_VERSION) && !defined(inline)
#define inline __inline
#endif /* __ARMCC_VERSION */

70
/* Implementation that should never be optimized out by the compiler */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
71
static void mbedtls_zeroize( void *v, size_t n ) {
72 73 74
    volatile unsigned char *p = v; while( n-- ) *p++ = 0;
}

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
75
#if defined(MBEDTLS_SELF_TEST)
76
/*
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
#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)
94
#define ECP_SHORTWEIERSTRASS
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
95 96
#endif

97
#if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED)
98
#define ECP_MONTGOMERY
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
99 100 101 102 103 104 105
#endif

/*
 * Curve types: internal for now, might be exposed later
 */
typedef enum
{
106 107 108
    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
109 110
} 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 119
 * 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.
120 121
 *
 * Reminder: update profiles in x509_crt.c when adding a new curves!
122
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
123
static const mbedtls_ecp_curve_info ecp_supported_curves[] =
124
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
125 126
#if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED)
    { MBEDTLS_ECP_DP_SECP521R1,    25,     521,    "secp521r1"         },
127
#endif
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
128 129
#if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED)
    { MBEDTLS_ECP_DP_BP512R1,      28,     512,    "brainpoolP512r1"   },
130
#endif
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
131 132
#if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED)
    { MBEDTLS_ECP_DP_SECP384R1,    24,     384,    "secp384r1"         },
133
#endif
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
134 135
#if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED)
    { MBEDTLS_ECP_DP_BP384R1,      27,     384,    "brainpoolP384r1"   },
136
#endif
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
137 138
#if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED)
    { MBEDTLS_ECP_DP_SECP256R1,    23,     256,    "secp256r1"         },
139
#endif
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
140 141
#if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED)
    { MBEDTLS_ECP_DP_SECP256K1,    22,     256,    "secp256k1"         },
142
#endif
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
143 144
#if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED)
    { MBEDTLS_ECP_DP_BP256R1,      26,     256,    "brainpoolP256r1"   },
145
#endif
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
146 147
#if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED)
    { MBEDTLS_ECP_DP_SECP224R1,    21,     224,    "secp224r1"         },
148
#endif
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
149 150
#if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED)
    { MBEDTLS_ECP_DP_SECP224K1,    20,     224,    "secp224k1"         },
151
#endif
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
152 153
#if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED)
    { MBEDTLS_ECP_DP_SECP192R1,    19,     192,    "secp192r1"         },
154
#endif
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
155 156
#if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED)
    { MBEDTLS_ECP_DP_SECP192K1,    18,     192,    "secp192k1"         },
157
#endif
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
158
    { MBEDTLS_ECP_DP_NONE,          0,     0,      NULL                },
159
};
160

161 162 163
#define ECP_NB_CURVES   sizeof( ecp_supported_curves ) /    \
                        sizeof( ecp_supported_curves[0] )

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
164
static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
165

166 167 168
/*
 * List of supported curves and associated info
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
169
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list( void )
170
{
171
    return( ecp_supported_curves );
172 173
}

174
/*
175 176
 * List of supported curves, group ID only
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
177
const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list( void )
178 179 180 181 182 183
{
    static int init_done = 0;

    if( ! init_done )
    {
        size_t i = 0;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
184
        const mbedtls_ecp_curve_info *curve_info;
185

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
186 187
        for( curve_info = mbedtls_ecp_curve_list();
             curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
188 189 190 191
             curve_info++ )
        {
            ecp_supported_grp_id[i++] = curve_info->grp_id;
        }
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
192
        ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE;
193 194 195 196

        init_done = 1;
    }

197
    return( ecp_supported_grp_id );
198 199 200 201
}

/*
 * Get the curve info for the internal identifier
202
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
203
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id( mbedtls_ecp_group_id grp_id )
204
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
205
    const mbedtls_ecp_curve_info *curve_info;
206

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
207 208
    for( curve_info = mbedtls_ecp_curve_list();
         curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
209 210 211 212 213 214 215 216 217 218 219 220
         curve_info++ )
    {
        if( curve_info->grp_id == grp_id )
            return( curve_info );
    }

    return( NULL );
}

/*
 * Get the curve info from the TLS identifier
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
221
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id( uint16_t tls_id )
222
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
223
    const mbedtls_ecp_curve_info *curve_info;
224

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
225 226
    for( curve_info = mbedtls_ecp_curve_list();
         curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
227 228 229 230 231 232 233 234 235
         curve_info++ )
    {
        if( curve_info->tls_id == tls_id )
            return( curve_info );
    }

    return( NULL );
}

236 237 238
/*
 * Get the curve info from the name
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
239
const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name( const char *name )
240
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
241
    const mbedtls_ecp_curve_info *curve_info;
242

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
243 244
    for( curve_info = mbedtls_ecp_curve_list();
         curve_info->grp_id != MBEDTLS_ECP_DP_NONE;
245 246
         curve_info++ )
    {
247
        if( strcmp( curve_info->name, name ) == 0 )
248 249 250 251 252 253
            return( curve_info );
    }

    return( NULL );
}

254
/*
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
255
 * Get the type of a curve
256
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
257
static inline ecp_curve_type ecp_get_type( const mbedtls_ecp_group *grp )
258
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
259
    if( grp->G.X.p == NULL )
260
        return( ECP_TYPE_NONE );
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
261 262

    if( grp->G.Y.p == NULL )
263
        return( ECP_TYPE_MONTGOMERY );
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
264
    else
265
        return( ECP_TYPE_SHORT_WEIERSTRASS );
266 267
}

268
/*
269
 * Initialize (the components of) a point
270
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
271
void mbedtls_ecp_point_init( mbedtls_ecp_point *pt )
272 273 274 275
{
    if( pt == NULL )
        return;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
276 277 278
    mbedtls_mpi_init( &pt->X );
    mbedtls_mpi_init( &pt->Y );
    mbedtls_mpi_init( &pt->Z );
279 280 281 282 283
}

/*
 * Initialize (the components of) a group
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
284
void mbedtls_ecp_group_init( mbedtls_ecp_group *grp )
285 286 287 288
{
    if( grp == NULL )
        return;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
289
    memset( grp, 0, sizeof( mbedtls_ecp_group ) );
290 291
}

292 293 294
/*
 * Initialize (the components of) a key pair
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
295
void mbedtls_ecp_keypair_init( mbedtls_ecp_keypair *key )
296
{
297
    if( key == NULL )
298 299
        return;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
300 301 302
    mbedtls_ecp_group_init( &key->grp );
    mbedtls_mpi_init( &key->d );
    mbedtls_ecp_point_init( &key->Q );
303 304
}

305 306 307
/*
 * Unallocate (the components of) a point
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
308
void mbedtls_ecp_point_free( mbedtls_ecp_point *pt )
309 310 311 312
{
    if( pt == NULL )
        return;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
313 314 315
    mbedtls_mpi_free( &( pt->X ) );
    mbedtls_mpi_free( &( pt->Y ) );
    mbedtls_mpi_free( &( pt->Z ) );
316 317 318 319 320
}

/*
 * Unallocate (the components of) a group
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
321
void mbedtls_ecp_group_free( mbedtls_ecp_group *grp )
322
{
323 324
    size_t i;

325 326 327
    if( grp == NULL )
        return;

328 329
    if( grp->h != 1 )
    {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
330 331 332 333 334
        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 );
335
    }
336

337 338 339
    if( grp->T != NULL )
    {
        for( i = 0; i < grp->T_size; i++ )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
340 341
            mbedtls_ecp_point_free( &grp->T[i] );
        mbedtls_free( grp->T );
342 343
    }

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
344
    mbedtls_zeroize( grp, sizeof( mbedtls_ecp_group ) );
345
}
346

347 348 349
/*
 * Unallocate (the components of) a key pair
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
350
void mbedtls_ecp_keypair_free( mbedtls_ecp_keypair *key )
351
{
352
    if( key == NULL )
353 354
        return;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
355 356 357
    mbedtls_ecp_group_free( &key->grp );
    mbedtls_mpi_free( &key->d );
    mbedtls_ecp_point_free( &key->Q );
358 359
}

360
/*
361
 * Copy the contents of a point
362
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
363
int mbedtls_ecp_copy( mbedtls_ecp_point *P, const mbedtls_ecp_point *Q )
364
{
365
    int ret;
366

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
367 368 369
    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 ) );
370 371 372 373

cleanup:
    return( ret );
}
374

375 376 377
/*
 * Copy the contents of a group object
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
378
int mbedtls_ecp_group_copy( mbedtls_ecp_group *dst, const mbedtls_ecp_group *src )
379
{
380
    return mbedtls_ecp_group_load( dst, src->id );
381 382
}

383
/*
384
 * Set point to zero
385
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
386
int mbedtls_ecp_set_zero( mbedtls_ecp_point *pt )
387
{
388
    int ret;
389

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
390 391 392
    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 ) );
393 394 395 396 397 398

cleanup:
    return( ret );
}

/*
399
 * Tell if a point is zero
400
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
401
int mbedtls_ecp_is_zero( mbedtls_ecp_point *pt )
402
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
403
    return( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 );
404 405 406
}

/*
407
 * Import a non-zero point from ASCII strings
408
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
409
int mbedtls_ecp_point_read_string( mbedtls_ecp_point *P, int radix,
410
                           const char *x, const char *y )
411
{
412
    int ret;
413

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
414 415 416
    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 ) );
417 418

cleanup:
419 420 421
    return( ret );
}

422
/*
423
 * Export a point into unsigned binary data (SEC1 2.3.3)
424
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
425
int mbedtls_ecp_point_write_binary( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *P,
426
                            int format, size_t *olen,
427
                            unsigned char *buf, size_t buflen )
428
{
429
    int ret = 0;
430 431
    size_t plen;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
432 433 434
    if( format != MBEDTLS_ECP_PF_UNCOMPRESSED &&
        format != MBEDTLS_ECP_PF_COMPRESSED )
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
435

436
    /*
437
     * Common case: P == 0
438
     */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
439
    if( mbedtls_mpi_cmp_int( &P->Z, 0 ) == 0 )
440 441
    {
        if( buflen < 1 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
442
            return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
443 444 445 446 447 448 449

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

        return( 0 );
    }

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
450
    plen = mbedtls_mpi_size( &grp->P );
451

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
452
    if( format == MBEDTLS_ECP_PF_UNCOMPRESSED )
453 454 455 456
    {
        *olen = 2 * plen + 1;

        if( buflen < *olen )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
457
            return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
458

459
        buf[0] = 0x04;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
460 461
        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 ) );
462
    }
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
463
    else if( format == MBEDTLS_ECP_PF_COMPRESSED )
464 465 466 467
    {
        *olen = plen + 1;

        if( buflen < *olen )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
468
            return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
469

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
470 471
        buf[0] = 0x02 + mbedtls_mpi_get_bit( &P->Y, 0 );
        MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &P->X, buf + 1, plen ) );
472
    }
473 474 475 476 477

cleanup:
    return( ret );
}

478 479 480
/*
 * Import a point from unsigned binary data (SEC1 2.3.4)
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
481
int mbedtls_ecp_point_read_binary( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
482 483
                           const unsigned char *buf, size_t ilen )
{
484 485 486
    int ret;
    size_t plen;

Paul Bakker's avatar
Paul Bakker committed
487
    if( ilen < 1 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
488
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
489

490 491 492
    if( buf[0] == 0x00 )
    {
        if( ilen == 1 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
493
            return( mbedtls_ecp_set_zero( pt ) );
494
        else
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
495
            return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
496
    }
497

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
498
    plen = mbedtls_mpi_size( &grp->P );
499

500
    if( buf[0] != 0x04 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
501
        return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
502 503

    if( ilen != 2 * plen + 1 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
504
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
505

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
506 507 508
    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 ) );
509 510 511 512 513

cleanup:
    return( ret );
}

514 515 516 517 518 519
/*
 * Import a point from a TLS ECPoint record (RFC 4492)
 *      struct {
 *          opaque point <1..2^8-1>;
 *      } ECPoint;
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
520
int mbedtls_ecp_tls_read_point( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt,
521
                        const unsigned char **buf, size_t buf_len )
522 523
{
    unsigned char data_len;
524
    const unsigned char *buf_start;
525 526

    /*
527
     * We must have at least two bytes (1 for length, at least one for data)
528 529
     */
    if( buf_len < 2 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
530
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
531

532
    data_len = *(*buf)++;
533
    if( data_len < 1 || data_len > buf_len - 1 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
534
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
535

536 537 538 539 540 541
    /*
     * Save buffer start for read_binary and update buf
     */
    buf_start = *buf;
    *buf += data_len;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
542
    return mbedtls_ecp_point_read_binary( grp, pt, buf_start, data_len );
543 544 545 546 547 548 549 550
}

/*
 * Export a point as a TLS ECPoint record (RFC 4492)
 *      struct {
 *          opaque point <1..2^8-1>;
 *      } ECPoint;
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
551
int mbedtls_ecp_tls_write_point( const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt,
552 553
                         int format, size_t *olen,
                         unsigned char *buf, size_t blen )
554
{
555 556
    int ret;

557
    /*
558
     * buffer length must be at least one, for our length byte
559
     */
560
    if( blen < 1 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
561
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
562

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
563
    if( ( ret = mbedtls_ecp_point_write_binary( grp, pt, format,
564 565 566 567 568 569
                    olen, buf + 1, blen - 1) ) != 0 )
        return( ret );

    /*
     * write length to the first byte and update total length
     */
570
    buf[0] = (unsigned char) *olen;
571 572
    ++*olen;

573
    return( 0 );
574 575
}

576 577 578
/*
 * Set a group from an ECParameters record (RFC 4492)
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
579
int mbedtls_ecp_tls_read_group( mbedtls_ecp_group *grp, const unsigned char **buf, size_t len )
580 581
{
    uint16_t tls_id;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
582
    const mbedtls_ecp_curve_info *curve_info;
583 584 585 586 587

    /*
     * We expect at least three bytes (see below)
     */
    if( len < 3 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
588
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
589 590 591 592

    /*
     * First byte is curve_type; only named_curve is handled
     */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
593 594
    if( *(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE )
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
595 596 597 598 599 600 601 602

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

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
603 604
    if( ( curve_info = mbedtls_ecp_curve_info_from_tls_id( tls_id ) ) == NULL )
        return( MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE );
605

606
    return mbedtls_ecp_group_load( grp, curve_info->grp_id );
607 608 609 610 611
}

/*
 * Write the ECParameters record corresponding to a group (RFC 4492)
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
612
int mbedtls_ecp_tls_write_group( const mbedtls_ecp_group *grp, size_t *olen,
613 614
                         unsigned char *buf, size_t blen )
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
615
    const mbedtls_ecp_curve_info *curve_info;
616

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
617 618
    if( ( curve_info = mbedtls_ecp_curve_info_from_grp_id( grp->id ) ) == NULL )
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
619 620 621 622 623 624

    /*
     * We are going to write 3 bytes (see below)
     */
    *olen = 3;
    if( blen < *olen )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
625
        return( MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL );
626 627 628 629

    /*
     * First byte is curve_type, always named_curve
     */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
630
    *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE;
631 632 633 634 635 636 637

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

638
    return( 0 );
639 640 641
}

/*
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
642 643
 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi.
 * See the documentation of struct mbedtls_ecp_group.
644
 *
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
645
 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf.
646
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
647
static int ecp_modp( mbedtls_mpi *N, const mbedtls_ecp_group *grp )
648 649 650 651
{
    int ret;

    if( grp->modp == NULL )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
652
        return( mbedtls_mpi_mod_mpi( N, N, &grp->P ) );
653 654

    /* N->s < 0 is a much faster test, which fails only if N is 0 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
655
    if( ( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 ) ||
656
        mbedtls_mpi_bitlen( N ) > 2 * grp->pbits )
657
    {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
658
        return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
659 660
    }

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
661
    MBEDTLS_MPI_CHK( grp->modp( N ) );
662 663

    /* N->s < 0 is a much faster test, which fails only if N is 0 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
664 665
    while( N->s < 0 && mbedtls_mpi_cmp_int( N, 0 ) != 0 )
        MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( N, N, &grp->P ) );
666

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
667
    while( mbedtls_mpi_cmp_mpi( N, &grp->P ) >= 0 )
668
        /* we known P, N and the result are positive */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
669
        MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( N, N, &grp->P ) );
670 671 672 673 674 675 676 677 678

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
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
679
 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will
680 681 682 683 684 685
 * bring the result back to this range.
 *
 * The following macros are shortcuts for doing that.
 */

/*
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
686
 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi
687
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
688
#if defined(MBEDTLS_SELF_TEST)
689 690 691 692 693
#define INC_MUL_COUNT   mul_count++;
#else
#define INC_MUL_COUNT
#endif

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
694
#define MOD_MUL( N )    do { MBEDTLS_MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
695
                        while( 0 )
696 697

/*
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
698
 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi
699 700 701
 * N->s < 0 is a very fast test, which fails only if N is 0
 */
#define MOD_SUB( N )                                \
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
702 703
    while( N.s < 0 && mbedtls_mpi_cmp_int( &N, 0 ) != 0 )   \
        MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &N, &N, &grp->P ) )
704 705

/*
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
706
 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int.
707 708 709 710
 * We known P, N and the result are positive, so sub_abs is correct, and
 * a bit faster.
 */
#define MOD_ADD( N )                                \
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
711 712
    while( mbedtls_mpi_cmp_mpi( &N, &grp->P ) >= 0 )        \
        MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &N, &N, &grp->P ) )
713

714
#if defined(ECP_SHORTWEIERSTRASS)
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
715 716 717 718 719 720 721 722
/*
 * 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.
 */

723 724
/*
 * Normalize jacobian coordinates so that Z == 0 || Z == 1  (GECC 3.2.1)
725
 * Cost: 1N := 1I + 3M + 1S
726
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
727
static int ecp_normalize_jac( const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt )
728 729
{
    int ret;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
730
    mbedtls_mpi Zi, ZZi;
731

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
732
    if( mbedtls_mpi_cmp_int( &pt->Z, 0 ) == 0 )
733 734
        return( 0 );

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
735
    mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
736 737 738 739

    /*
     * X = X / Z^2  mod p
     */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
740 741 742
    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 );
743 744 745 746

    /*
     * Y = Y / Z^3  mod p
     */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
747 748
    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 );
749 750 751 752

    /*
     * Z = 1
     */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
753
    MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &pt->Z, 1 ) );
754 755 756

cleanup:

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
757
    mbedtls_mpi_free( &Zi ); mbedtls_mpi_free( &ZZi );
758 759 760 761

    return( ret );
}

762
/*
763
 * Normalize jacobian coordinates of an array of (pointers to) points,
764 765 766 767 768
 * 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
769
 * This should never happen, see choice of w in ecp_mul_comb().
770 771
 *
 * Cost: 1N(t) := 1I + (6t - 3)M + 1S
772
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
773 774
static int ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
                                   mbedtls_ecp_point *T[], size_t t_len )
775
{
776 777
    int ret;
    size_t i;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
778
    mbedtls_mpi *c, u, Zi, ZZi;
779

780
    if( t_len < 2 )
781
        return( ecp_normalize_jac( grp, *T ) );
782

783
    if( ( c = mbedtls_calloc( t_len, sizeof( mbedtls_mpi ) ) ) == NULL )
784
        return( MBEDTLS_ERR_ECP_ALLOC_FAILED );
785

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
786
    mbedtls_mpi_init( &u ); mbedtls_mpi_init( &Zi ); mbedtls_mpi_init( &ZZi );
787 788 789 790

    /*
     * c[i] = Z_0 * ... * Z_i
     */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
791
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &c[0], &T[0]->Z ) );
792
    for( i = 1; i < t_len; i++ )
793
    {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
794
        MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) );
795 796
        MOD_MUL( c[i] );
    }
797

798 799 800
    /*
     * u = 1 / (Z_0 * ... * Z_n) mod P
     */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
801
    MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &u, &c[t_len-1], &grp->P ) );
802

803 804 805 806 807 808 809
    for( i = t_len - 1; ; i-- )
    {
        /*
         * Zi = 1 / Z_i mod p
         * u = 1 / (Z_0 * ... * Z_i) mod P
         */
        if( i == 0 ) {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
810
            MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Zi, &u ) );
811 812 813
        }
        else
        {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
814 815
            MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &Zi, &