bignum.c 54.8 KB
Newer Older
1 2 3
/*
 *  Multi-precision integer library
 *
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
4
 *  Copyright (C) 2006-2014, ARM Limited, All Rights Reserved
Paul Bakker's avatar
Paul Bakker committed
5
 *
6
 *  This file is part of mbed TLS (https://tls.mbed.org)
Paul Bakker's avatar
Paul Bakker committed
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.
 */
/*
 *  This MPI implementation is based on:
 *
 *  http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
26
 *  http://www.stillhq.com/extracted/gnupg-api/mbedtls_mpi/
27 28 29
 *  http://math.libtomcrypt.com/files/tommath.pdf
 */

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
30
#if !defined(MBEDTLS_CONFIG_FILE)
31
#include "mbedtls/config.h"
32
#else
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
33
#include MBEDTLS_CONFIG_FILE
34
#endif
35

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
36
#if defined(MBEDTLS_BIGNUM_C)
37

38 39
#include "mbedtls/bignum.h"
#include "mbedtls/bn_mul.h"
40

41 42
#include <string.h>

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
43
#if defined(MBEDTLS_PLATFORM_C)
44
#include "mbedtls/platform.h"
45
#else
46 47
#include <stdio.h>
#include <stdlib.h>
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
48
#define mbedtls_printf     printf
49
#define mbedtls_calloc    calloc
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
50
#define mbedtls_free       free
51
#endif
52

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

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
58
#define ciL    (sizeof(mbedtls_mpi_uint))         /* chars in limb  */
59 60 61 62 63 64 65 66 67 68
#define biL    (ciL << 3)               /* bits  in limb  */
#define biH    (ciL << 2)               /* half limb size */

/*
 * Convert between bits/chars and number of limbs
 */
#define BITS_TO_LIMBS(i)  (((i) + biL - 1) / biL)
#define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)

/*
69
 * Initialize one MPI
70
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
71
void mbedtls_mpi_init( mbedtls_mpi *X )
72
{
73 74
    if( X == NULL )
        return;
75

76 77 78
    X->s = 1;
    X->n = 0;
    X->p = NULL;
79 80 81
}

/*
82
 * Unallocate one MPI
83
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
84
void mbedtls_mpi_free( mbedtls_mpi *X )
85
{
86 87
    if( X == NULL )
        return;
88

89
    if( X->p != NULL )
90
    {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
91 92
        mbedtls_zeroize( X->p, X->n * ciL );
        mbedtls_free( X->p );
93 94
    }

95 96 97
    X->s = 1;
    X->n = 0;
    X->p = NULL;
98 99 100 101 102
}

/*
 * Enlarge to the specified number of limbs
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
103
int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
104
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
105
    mbedtls_mpi_uint *p;
106

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
107
    if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
108
        return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
109

110 111
    if( X->n < nblimbs )
    {
112
        if( ( p = mbedtls_calloc( nblimbs, ciL ) ) == NULL )
113
            return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
114 115 116 117

        if( X->p != NULL )
        {
            memcpy( p, X->p, X->n * ciL );
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
118 119
            mbedtls_zeroize( X->p, X->n * ciL );
            mbedtls_free( X->p );
120 121 122 123 124 125 126 127 128
        }

        X->n = nblimbs;
        X->p = p;
    }

    return( 0 );
}

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
129 130 131 132
/*
 * Resize down as much as possible,
 * while keeping at least the specified number of limbs
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
133
int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
134
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
135
    mbedtls_mpi_uint *p;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
136 137 138 139
    size_t i;

    /* Actually resize up in this case */
    if( X->n <= nblimbs )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
140
        return( mbedtls_mpi_grow( X, nblimbs ) );
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
141 142 143 144 145 146 147 148 149

    for( i = X->n - 1; i > 0; i-- )
        if( X->p[i] != 0 )
            break;
    i++;

    if( i < nblimbs )
        i = nblimbs;

150
    if( ( p = mbedtls_calloc( i, ciL ) ) == NULL )
151
        return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
152 153 154 155

    if( X->p != NULL )
    {
        memcpy( p, X->p, i * ciL );
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
156 157
        mbedtls_zeroize( X->p, X->n * ciL );
        mbedtls_free( X->p );
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
158 159 160 161 162 163 164 165
    }

    X->n = i;
    X->p = p;

    return( 0 );
}

166 167 168
/*
 * Copy the contents of Y into X
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
169
int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
170
{
171 172
    int ret;
    size_t i;
173 174 175 176

    if( X == Y )
        return( 0 );

177 178
    if( Y->p == NULL )
    {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
179
        mbedtls_mpi_free( X );
180 181 182
        return( 0 );
    }

183 184 185 186 187 188 189
    for( i = Y->n - 1; i > 0; i-- )
        if( Y->p[i] != 0 )
            break;
    i++;

    X->s = Y->s;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
190
    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
191 192 193 194 195 196 197 198 199 200 201 202

    memset( X->p, 0, X->n * ciL );
    memcpy( X->p, Y->p, i * ciL );

cleanup:

    return( ret );
}

/*
 * Swap the contents of X and Y
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
203
void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
204
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
205
    mbedtls_mpi T;
206

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
207 208 209
    memcpy( &T,  X, sizeof( mbedtls_mpi ) );
    memcpy(  X,  Y, sizeof( mbedtls_mpi ) );
    memcpy(  Y, &T, sizeof( mbedtls_mpi ) );
210 211
}

212 213
/*
 * Conditionally assign X = Y, without leaking information
214 215
 * about whether the assignment was made or not.
 * (Leaking information about the respective sizes of X and Y is ok however.)
216
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
217
int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign )
218 219 220 221
{
    int ret = 0;
    size_t i;

222 223
    /* make sure assign is 0 or 1 in a time-constant manner */
    assign = (assign | (unsigned char)-assign) >> 7;
224

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
225
    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
226

227
    X->s = X->s * ( 1 - assign ) + Y->s * assign;
228

229
    for( i = 0; i < Y->n; i++ )
230
        X->p[i] = X->p[i] * ( 1 - assign ) + Y->p[i] * assign;
231

232
    for( ; i < X->n; i++ )
233
        X->p[i] *= ( 1 - assign );
234 235 236 237 238

cleanup:
    return( ret );
}

239 240 241 242 243 244
/*
 * Conditionally swap X and Y, without leaking information
 * about whether the swap was made or not.
 * Here it is not ok to simply swap the pointers, which whould lead to
 * different memory access patterns when X and Y are used afterwards.
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
245
int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap )
246 247 248
{
    int ret, s;
    size_t i;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
249
    mbedtls_mpi_uint tmp;
250 251 252 253

    if( X == Y )
        return( 0 );

254 255
    /* make sure swap is 0 or 1 in a time-constant manner */
    swap = (swap | (unsigned char)-swap) >> 7;
256

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
257 258
    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
259 260

    s = X->s;
261 262
    X->s = X->s * ( 1 - swap ) + Y->s * swap;
    Y->s = Y->s * ( 1 - swap ) +    s * swap;
263 264 265 266 267


    for( i = 0; i < X->n; i++ )
    {
        tmp = X->p[i];
268 269
        X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap;
        Y->p[i] = Y->p[i] * ( 1 - swap ) +     tmp * swap;
270 271 272 273 274 275
    }

cleanup:
    return( ret );
}

276 277 278
/*
 * Set value from integer
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
279
int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
280 281 282
{
    int ret;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
283
    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
284 285 286 287 288 289 290 291 292 293
    memset( X->p, 0, X->n * ciL );

    X->p[0] = ( z < 0 ) ? -z : z;
    X->s    = ( z < 0 ) ? -1 : 1;

cleanup:

    return( ret );
}

294 295 296
/*
 * Get a specific bit
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
297
int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
298 299 300 301
{
    if( X->n * biL <= pos )
        return( 0 );

302
    return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
303 304 305 306 307
}

/*
 * Set a bit to a specific value of 0 or 1
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
308
int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
309 310 311 312 313 314
{
    int ret = 0;
    size_t off = pos / biL;
    size_t idx = pos % biL;

    if( val != 0 && val != 1 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
315
        return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
316

317 318 319
    if( X->n * biL <= pos )
    {
        if( val == 0 )
320
            return( 0 );
321

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
322
        MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
323 324
    }

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
325 326
    X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
    X->p[off] |= (mbedtls_mpi_uint) val << idx;
327 328

cleanup:
329

330 331 332
    return( ret );
}

333
/*
334
 * Return the number of less significant zero-bits
335
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
336
size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
337
{
338
    size_t i, j, count = 0;
339 340

    for( i = 0; i < X->n; i++ )
341
        for( j = 0; j < biL; j++, count++ )
342 343 344 345 346 347 348
            if( ( ( X->p[i] >> j ) & 1 ) != 0 )
                return( count );

    return( 0 );
}

/*
349
 * Return the number of bits
350
 */
351
size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
352
{
353
    size_t i, j;
354

355 356 357
    if( X->n == 0 )
        return( 0 );

358 359 360 361
    for( i = X->n - 1; i > 0; i-- )
        if( X->p[i] != 0 )
            break;

362 363
    for( j = biL; j > 0; j-- )
        if( ( ( X->p[i] >> ( j - 1 ) ) & 1 ) != 0 )
364 365
            break;

366
    return( ( i * biL ) + j );
367 368 369 370 371
}

/*
 * Return the total size in bytes
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
372
size_t mbedtls_mpi_size( const mbedtls_mpi *X )
373
{
374
    return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
375 376 377 378 379
}

/*
 * Convert an ASCII character to digit value
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
380
static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
381 382 383 384 385 386 387
{
    *d = 255;

    if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
    if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
    if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
388 389
    if( *d >= (mbedtls_mpi_uint) radix )
        return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
390 391 392 393 394 395 396

    return( 0 );
}

/*
 * Import from an ASCII string
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
397
int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
398
{
399 400
    int ret;
    size_t i, j, slen, n;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
401 402
    mbedtls_mpi_uint d;
    mbedtls_mpi T;
403 404

    if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
405
        return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
406

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
407
    mbedtls_mpi_init( &T );
408

409 410
    slen = strlen( s );

411 412
    if( radix == 16 )
    {
413
        n = BITS_TO_LIMBS( slen << 2 );
414

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
415 416
        MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
        MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
417

418
        for( i = slen, j = 0; i > 0; i--, j++ )
419
        {
420
            if( i == 1 && s[i - 1] == '-' )
421 422 423 424 425
            {
                X->s = -1;
                break;
            }

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
426
            MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
427
            X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
428 429 430 431
        }
    }
    else
    {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
432
        MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
433

434
        for( i = 0; i < slen; i++ )
435 436 437 438 439 440 441
        {
            if( i == 0 && s[i] == '-' )
            {
                X->s = -1;
                continue;
            }

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
442 443
            MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
            MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
444 445 446

            if( X->s == 1 )
            {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
447
                MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
448 449 450
            }
            else
            {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
451
                MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) );
452
            }
453 454 455 456 457
        }
    }

cleanup:

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
458
    mbedtls_mpi_free( &T );
459 460 461 462 463 464 465

    return( ret );
}

/*
 * Helper to write the digits high-order first
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
466
static int mpi_write_hlp( mbedtls_mpi *X, int radix, char **p )
467 468
{
    int ret;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
469
    mbedtls_mpi_uint r;
470 471

    if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
472
        return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
473

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
474 475
    MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
476

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
477 478
    if( mbedtls_mpi_cmp_int( X, 0 ) != 0 )
        MBEDTLS_MPI_CHK( mpi_write_hlp( X, radix, p ) );
479 480 481 482 483 484 485 486 487 488 489 490 491 492

    if( r < 10 )
        *(*p)++ = (char)( r + 0x30 );
    else
        *(*p)++ = (char)( r + 0x37 );

cleanup:

    return( ret );
}

/*
 * Export into an ASCII string
 */
493 494
int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
                              char *buf, size_t buflen, size_t *olen )
495
{
496 497
    int ret = 0;
    size_t n;
498
    char *p;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
499
    mbedtls_mpi T;
500 501

    if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
502
        return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
503

504
    n = mbedtls_mpi_bitlen( X );
505 506 507 508
    if( radix >=  4 ) n >>= 1;
    if( radix >= 16 ) n >>= 1;
    n += 3;

509
    if( buflen < n )
510
    {
511
        *olen = n;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
512
        return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
513 514
    }

515
    p = buf;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
516
    mbedtls_mpi_init( &T );
517 518 519 520 521 522

    if( X->s == -1 )
        *p++ = '-';

    if( radix == 16 )
    {
523 524
        int c;
        size_t i, j, k;
525

526
        for( i = X->n, k = 0; i > 0; i-- )
527
        {
528
            for( j = ciL; j > 0; j-- )
529
            {
530
                c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
531

532
                if( c == 0 && k == 0 && ( i + j ) != 2 )
533 534
                    continue;

535
                *(p++) = "0123456789ABCDEF" [c / 16];
Paul Bakker's avatar
Paul Bakker committed
536
                *(p++) = "0123456789ABCDEF" [c % 16];
537 538 539 540 541 542
                k = 1;
            }
        }
    }
    else
    {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
543
        MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
544 545 546 547

        if( T.s == -1 )
            T.s = 1;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
548
        MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
549 550 551
    }

    *p++ = '\0';
552
    *olen = p - buf;
553 554 555

cleanup:

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
556
    mbedtls_mpi_free( &T );
557 558 559 560

    return( ret );
}

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
561
#if defined(MBEDTLS_FS_IO)
562 563 564
/*
 * Read X from an opened file
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
565
int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
566
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
567
    mbedtls_mpi_uint d;
568
    size_t slen;
569
    char *p;
570
    /*
571 572
     * Buffer should have space for (short) label and decimal formatted MPI,
     * newline characters and '\0'
573
     */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
574
    char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
575 576 577

    memset( s, 0, sizeof( s ) );
    if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
578
        return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
579 580

    slen = strlen( s );
581
    if( slen == sizeof( s ) - 2 )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
582
        return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
583

584 585 586 587 588 589 590 591
    if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
    if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }

    p = s + slen;
    while( --p >= s )
        if( mpi_get_digit( &d, radix, *p ) != 0 )
            break;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
592
    return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
593 594 595 596 597
}

/*
 * Write X into an opened file (or stdout if fout == NULL)
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
598
int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
599
{
600 601
    int ret;
    size_t n, slen, plen;
602
    /*
603 604
     * Buffer should have space for (short) label and decimal formatted MPI,
     * newline characters and '\0'
605
     */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
606
    char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
607

608
    memset( s, 0, sizeof( s ) );
609

610
    MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
611 612 613 614 615 616 617 618 619 620 621 622

    if( p == NULL ) p = "";

    plen = strlen( p );
    slen = strlen( s );
    s[slen++] = '\r';
    s[slen++] = '\n';

    if( fout != NULL )
    {
        if( fwrite( p, 1, plen, fout ) != plen ||
            fwrite( s, 1, slen, fout ) != slen )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
623
            return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
624 625
    }
    else
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
626
        mbedtls_printf( "%s%s", p, s );
627 628 629 630 631

cleanup:

    return( ret );
}
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
632
#endif /* MBEDTLS_FS_IO */
633 634 635 636

/*
 * Import X from unsigned binary data, big endian
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
637
int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
638
{
639 640
    int ret;
    size_t i, j, n;
641 642 643 644 645

    for( n = 0; n < buflen; n++ )
        if( buf[n] != 0 )
            break;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
646 647
    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
648

649
    for( i = buflen, j = 0; i > n; i--, j++ )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
650
        X->p[j / ciL] |= ((mbedtls_mpi_uint) buf[i - 1]) << ((j % ciL) << 3);
651 652 653 654 655 656 657 658 659

cleanup:

    return( ret );
}

/*
 * Export X into unsigned binary data, big endian
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
660
int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen )
661
{
662
    size_t i, j, n;
663

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
664
    n = mbedtls_mpi_size( X );
665 666

    if( buflen < n )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
667
        return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
668 669 670 671 672 673 674 675 676 677 678 679

    memset( buf, 0, buflen );

    for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
        buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );

    return( 0 );
}

/*
 * Left-shift: X <<= count
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
680
int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
681
{
682 683
    int ret;
    size_t i, v0, t1;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
684
    mbedtls_mpi_uint r0 = 0, r1;
685 686 687 688

    v0 = count / (biL    );
    t1 = count & (biL - 1);

689
    i = mbedtls_mpi_bitlen( X ) + count;
690

691
    if( X->n * biL < i )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
692
        MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
693 694 695 696 697 698 699 700

    ret = 0;

    /*
     * shift by count / limb_size
     */
    if( v0 > 0 )
    {
701 702
        for( i = X->n; i > v0; i-- )
            X->p[i - 1] = X->p[i - v0 - 1];
703

704 705
        for( ; i > 0; i-- )
            X->p[i - 1] = 0;
706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729
    }

    /*
     * shift by count % limb_size
     */
    if( t1 > 0 )
    {
        for( i = v0; i < X->n; i++ )
        {
            r1 = X->p[i] >> (biL - t1);
            X->p[i] <<= t1;
            X->p[i] |= r0;
            r0 = r1;
        }
    }

cleanup:

    return( ret );
}

/*
 * Right-shift: X >>= count
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
730
int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
731
{
732
    size_t i, v0, v1;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
733
    mbedtls_mpi_uint r0 = 0, r1;
734 735 736 737

    v0 = count /  biL;
    v1 = count & (biL - 1);

738
    if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
739
        return mbedtls_mpi_lset( X, 0 );
740

741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757
    /*
     * shift by count / limb_size
     */
    if( v0 > 0 )
    {
        for( i = 0; i < X->n - v0; i++ )
            X->p[i] = X->p[i + v0];

        for( ; i < X->n; i++ )
            X->p[i] = 0;
    }

    /*
     * shift by count % limb_size
     */
    if( v1 > 0 )
    {
758
        for( i = X->n; i > 0; i-- )
759
        {
760 761 762
            r1 = X->p[i - 1] << (biL - v1);
            X->p[i - 1] >>= v1;
            X->p[i - 1] |= r0;
763 764 765 766 767 768 769 770 771 772
            r0 = r1;
        }
    }

    return( 0 );
}

/*
 * Compare unsigned values
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
773
int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
774
{
775
    size_t i, j;
776

777 778
    for( i = X->n; i > 0; i-- )
        if( X->p[i - 1] != 0 )
779 780
            break;

781 782
    for( j = Y->n; j > 0; j-- )
        if( Y->p[j - 1] != 0 )
783 784
            break;

785
    if( i == 0 && j == 0 )
786 787 788 789 790
        return( 0 );

    if( i > j ) return(  1 );
    if( j > i ) return( -1 );

791
    for( ; i > 0; i-- )
792
    {
793 794
        if( X->p[i - 1] > Y->p[i - 1] ) return(  1 );
        if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
795 796 797 798 799 800 801 802
    }

    return( 0 );
}

/*
 * Compare signed values
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
803
int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
804
{
805
    size_t i, j;
806

807 808
    for( i = X->n; i > 0; i-- )
        if( X->p[i - 1] != 0 )
809 810
            break;

811 812
    for( j = Y->n; j > 0; j-- )
        if( Y->p[j - 1] != 0 )
813 814
            break;

815
    if( i == 0 && j == 0 )
816 817 818
        return( 0 );

    if( i > j ) return(  X->s );
819
    if( j > i ) return( -Y->s );
820 821 822 823

    if( X->s > 0 && Y->s < 0 ) return(  1 );
    if( Y->s > 0 && X->s < 0 ) return( -1 );

824
    for( ; i > 0; i-- )
825
    {
826 827
        if( X->p[i - 1] > Y->p[i - 1] ) return(  X->s );
        if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
828 829 830 831 832 833 834 835
    }

    return( 0 );
}

/*
 * Compare signed values
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
836
int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
837
{
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
838 839
    mbedtls_mpi Y;
    mbedtls_mpi_uint p[1];
840 841 842 843 844 845

    *p  = ( z < 0 ) ? -z : z;
    Y.s = ( z < 0 ) ? -1 : 1;
    Y.n = 1;
    Y.p = p;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
846
    return( mbedtls_mpi_cmp_mpi( X, &Y ) );
847 848 849 850 851
}

/*
 * Unsigned addition: X = |A| + |B|  (HAC 14.7)
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
852
int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
853
{
854 855
    int ret;
    size_t i, j;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
856
    mbedtls_mpi_uint *o, *p, c;
857 858 859

    if( X == B )
    {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
860
        const mbedtls_mpi *T = A; A = X; B = T;
861 862 863
    }

    if( X != A )
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
864
        MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
865

866 867 868 869
    /*
     * X should always be positive as a result of unsigned additions.
     */
    X->s = 1;
870

871 872
    for( j = B->n; j > 0; j-- )
        if( B->p[j - 1] != 0 )
873 874
            break;

Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
875
    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
876 877 878

    o = B->p; p = X->p; c = 0;

879
    for( i = 0; i < j; i++, o++, p++ )
880 881 882 883 884 885 886 887 888
    {
        *p +=  c; c  = ( *p <  c );
        *p += *o; c += ( *p < *o );
    }

    while( c != 0 )
    {
        if( i >= X->n )
        {
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
889
            MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
890 891 892
            p = X->p + i;
        }

893
        *p += c; c = ( *p < c ); i++; p++;
894 895 896 897 898 899 900 901
    }

cleanup:

    return( ret );
}

/*
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
902
 * Helper for mbedtls_mpi subtraction
903
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
904
static void mpi_sub_hlp( size_t n, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d )
905
{
906
    size_t i;
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
907
    mbedtls_mpi_uint c, z;
908 909 910 911 912 913 914 915 916 917 918 919 920 921 922

    for( i = c = 0; i < n; i++, s++, d++ )
    {
        z = ( *d <  c );     *d -=  c;
        c = ( *d < *s ) + z; *d -= *s;
    }

    while( c != 0 )
    {
        z = ( *d < c ); *d -= c;
        c = z; i++; d++;
    }
}

/*
923
 * Unsigned subtraction: X = |A| - |B|  (HAC 14.9)
924
 */
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
925
int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
926
{
Manuel Pégourié-Gonnard's avatar