bignum.c 54.8 KB
Newer Older
1 2 3
/*
 *  Multi-precision integer library
 *
4
 *  Copyright (C) 2006-2015, 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.
 */
/*
 *  This MPI implementation is based on:
 *
 *  http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
26
 *  http://www.stillhq.com/extracted/gnupg-api/mbedtls_mpi/
27 28 29
 *  http://math.libtomcrypt.com/files/tommath.pdf
 */

30
#if !defined(MBEDTLS_CONFIG_FILE)
31
#include "mbedtls/config.h"
32
#else
33
#include MBEDTLS_CONFIG_FILE
34
#endif
35

36
#if defined(MBEDTLS_BIGNUM_C)
37

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

41 42
#include <string.h>

43
#if defined(MBEDTLS_PLATFORM_C)
44
#include "mbedtls/platform.h"
45
#else
46 47
#include <stdio.h>
#include <stdlib.h>
48
#define mbedtls_printf     printf
49
#define mbedtls_calloc    calloc
50
#define mbedtls_free       free
51
#endif
52

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

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
 */
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
 */
84
void mbedtls_mpi_free( mbedtls_mpi *X )
85
{
86 87
    if( X == NULL )
        return;
88

89
    if( X->p != NULL )
90
    {
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
 */
103
int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
104
{
105
    mbedtls_mpi_uint *p;
106

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 );
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 );
}

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

    /* Actually resize up in this case */
    if( X->n <= nblimbs )
140
        return( mbedtls_mpi_grow( X, nblimbs ) );
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 );
152 153 154 155

    if( X->p != NULL )
    {
        memcpy( p, X->p, i * ciL );
156 157
        mbedtls_zeroize( X->p, X->n * ciL );
        mbedtls_free( X->p );
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
 */
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 )
    {
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;

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
 */
203
void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
204
{
205
    mbedtls_mpi T;
206

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
 */
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

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.
 */
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;
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

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
 */
279
int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
280 281 282
{
    int ret;

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
 */
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
 */
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 )
315
        return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
316

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

322
        MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
323 324
    }

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
 */
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
 */
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
 */
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;

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
 */
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;
401 402
    mbedtls_mpi_uint d;
    mbedtls_mpi T;
403 404

    if( radix < 2 || radix > 16 )
405
        return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
406

407
    mbedtls_mpi_init( &T );
408

409 410
    slen = strlen( s );

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

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;
            }

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
    {
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;
            }

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 )
            {
447
                MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
448 449 450
            }
            else
            {
451
                MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) );
452
            }
453 454 455 456 457
        }
    }

cleanup:

458
    mbedtls_mpi_free( &T );
459 460 461 462 463 464 465

    return( ret );
}

/*
 * Helper to write the digits high-order first
 */
466
static int mpi_write_hlp( mbedtls_mpi *X, int radix, char **p )
467 468
{
    int ret;
469
    mbedtls_mpi_uint r;
470 471

    if( radix < 2 || radix > 16 )
472
        return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
473

474 475
    MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
476

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;
499
    mbedtls_mpi T;
500 501

    if( radix < 2 || radix > 16 )
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;
512
        return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
513 514
    }

515
    p = buf;
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
    {
543
        MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
544 545 546 547

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

548
        MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
549 550 551
    }

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

cleanup:

556
    mbedtls_mpi_free( &T );
557 558 559 560

    return( ret );
}

561
#if defined(MBEDTLS_FS_IO)
562 563 564
/*
 * Read X from an opened file
 */
565
int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
566
{
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
     */
574
    char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
575 576 577

    memset( s, 0, sizeof( s ) );
    if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
578
        return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
579 580

    slen = strlen( s );
581
    if( slen == sizeof( s ) - 2 )
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;

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)
 */
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
     */
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 )
623
            return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
624 625
    }
    else
626
        mbedtls_printf( "%s%s", p, s );
627 628 629 630 631

cleanup:

    return( ret );
}
632
#endif /* MBEDTLS_FS_IO */
633 634 635 636

/*
 * Import X from unsigned binary data, big endian
 */
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;

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++ )
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
 */
660
int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen )
661
{
662
    size_t i, j, n;
663

664
    n = mbedtls_mpi_size( X );
665 666

    if( buflen < n )
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
 */
680
int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
681
{
682 683
    int ret;
    size_t i, v0, t1;
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 )
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
 */
730
int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
731
{
732
    size_t i, v0, v1;
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 ) )
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
 */
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
 */
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
 */
836
int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
837
{
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;

846
    return( mbedtls_mpi_cmp_mpi( X, &Y ) );
847 848 849 850 851
}

/*
 * Unsigned addition: X = |A| + |B|  (HAC 14.7)
 */
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;
856
    mbedtls_mpi_uint *o, *p, c;
857 858 859

    if( X == B )
    {
860
        const mbedtls_mpi *T = A; A = X; B = T;
861 862 863
    }

    if( X != A )
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;

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 )
        {
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 );
}

/*
902
 * Helper for mbedtls_mpi subtraction
903
 */
904
static void mpi_sub_hlp( size_t n, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d )
905
{
906
    size_t i;
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
 */
925
int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
926
{
927
    mbedtls_mpi TB;
928 929
    int ret;
    size_t n;
930

931 932
    if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
        return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
933

934
    mbedtls_mpi_init( &TB );
935 936 937

    if( X == B )
    {
938
        MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
939 940 941 942
        B = &TB;
    }

    if( X != A )
943
        MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
944

945
    /*
946
     * X should always be positive as a result of unsigned subtractions.
947 948 949
     */
    X->s = 1;

950 951
    ret = 0;

952 953
    for( n = B->n; n > 0; n-- )
        if( B->p[n - 1] != 0 )
954 955
            break;

956
    mpi_sub_hlp( n, B->p, X->p );
957 958 959

cleanup:

960
    mbedtls_mpi_free( &TB );
961 962 963 964 965 966 967

    return( ret );
}

/*
 * Signed addition: X = A + B
 */
968
int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
969 970 971 972 973
{
    int ret, s = A->s;

    if( A->s * B->s < 0 )
    {
974
        if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
975
        {
976
            MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
977 978 979 980
            X->s =  s;
        }
        else
        {
981
            MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
982 983 984 985 986
            X->s = -s;
        }
    }
    else
    {
987
        MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
988 989 990 991 992 993 994 995 996
        X->s = s;
    }

cleanup:

    return( ret );
}

/*
997
 * Signed subtraction: X = A - B
998
 */
999
int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1000 1001 1002 1003 1004
{
    int ret, s = A->s;

    if( A->s * B->s > 0 )
    {
1005
        if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
1006
        {
1007
            MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
1008 1009 1010 1011
            X->s =  s;
        }
        else
        {
1012
            MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
1013 1014 1015 1016 1017
            X->s = -s;
        }
    }
    else
    {
1018
        MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029
        X->s = s;
    }

cleanup:

    return( ret );
}

/*
 * Signed addition: X = A + b
 */
1030
int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1031
{
1032 1033
    mbedtls_mpi _B;
    mbedtls_mpi_uint p[1];
1034 1035 1036 1037 1038 1039

    p[0] = ( b < 0 ) ? -b : b;
    _B.s = ( b < 0 ) ? -1 : 1;
    _B.n = 1;
    _B.p = p;

1040
    return( mbedtls_mpi_add_mpi( X, A, &_B ) );
1041 1042 1043
}

/*
1044
 * Signed subtraction: X = A - b
1045
 */
1046
int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1047
{
1048 1049
    mbedtls_mpi _B;
    mbedtls_mpi_uint p[1];
1050 1051 1052 1053 1054 1055

    p[0] = ( b < 0 ) ? -b : b;
    _B.s = ( b < 0 ) ? -1 : 1;
    _B.n = 1;
    _B.p = p;

1056
    return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
1057 1058 1059
}

/*
1060
 * Helper for mbedtls_mpi multiplication
1061 1062 1063 1064 1065 1066 1067 1068 1069
 */
static
#if defined(__APPLE__) && defined(__arm__)
/*
 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
 * appears to need this to prevent bad ARM code generation at -O3.
 */
__attribute__ ((noinline))
#endif
1070
void mpi_mul_hlp( size_t i, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d, mbedtls_mpi_uint b )
1071
{
1072
    mbedtls_mpi_uint c = 0, t = 0;
1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087

#if defined(MULADDC_HUIT)
    for( ; i >= 8; i -= 8 )
    {
        MULADDC_INIT
        MULADDC_HUIT
        MULADDC_STOP
    }

    for( ; i > 0; i-- )
    {
        MULADDC_INIT
        MULADDC_CORE
        MULADDC_STOP
    }
1088
#else /* MULADDC_HUIT */
1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120
    for( ; i >= 16; i -= 16 )
    {
        MULADDC_INIT
        MULADDC_CORE   MULADDC_CORE
        MULADDC_CORE   MULADDC_CORE
        MULADDC_CORE   MULADDC_CORE
        MULADDC_CORE   MULADDC_CORE

        MULADDC_CORE   MULADDC_CORE
        MULADDC_CORE   MULADDC_CORE
        MULADDC_CORE   MULADDC_CORE
        MULADDC_CORE   MULADDC_CORE
        MULADDC_STOP
    }

    for( ; i >= 8; i -= 8 )
    {
        MULADDC_INIT
        MULADDC_CORE   MULADDC_CORE
        MULADDC_CORE   MULADDC_CORE

        MULADDC_CORE   MULADDC_CORE
        MULADDC_CORE   MULADDC_CORE
        MULADDC_STOP
    }

    for( ; i > 0; i-- )
    {
        MULADDC_INIT
        MULADDC_CORE
        MULADDC_STOP
    }
1121
#endif /* MULADDC_HUIT */
1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133

    t++;

    do {
        *d += c; c = ( *d < c ); d++;
    }
    while( c != 0 );
}

/*
 * Baseline multiplication: X = A * B  (HAC 14.12)
 */
1134
int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1135
{
1136 1137
    int ret;
    size_t i, j;
1138
    mbedtls_mpi TA, TB;
1139

1140
    mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
1141

1142 1143
    if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
    if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
1144

1145 1146
    for( i = A->n; i > 0; i-- )
        if( A->p[i - 1] != 0 )
1147 1148
            break;

1149 1150
    for( j = B->n; j > 0; j-- )
        if( B->p[j - 1] != 0 )
1151 1152
            break;

1153 1154
    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
1155

1156 1157
    for( i++; j > 0; j-- )
        mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] );
1158 1159 1160 1161 1162

    X->s = A->s * B->s;

cleanup:

1163
    mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
1164 1165 1166 1167 1168 1169 1170

    return( ret );
}

/*
 * Baseline multiplication: X = A * b
 */
1171
int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
1172
{
1173 1174
    mbedtls_mpi _B;
    mbedtls_mpi_uint p[1];
1175 1176 1177 1178 1179 1180

    _B.s = 1;
    _B.n = 1;
    _B.p = p;
    p[0] = b;

1181
    return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
1182 1183 1184
}

/*
1185
 * Division by mbedtls_mpi: A = Q * B + R  (HAC 14.20)
1186
 */
1187
int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
1188
{
1189 1190
    int ret;
    size_t i, n, t, k;
1191
    mbedtls_mpi X, Y, Z, T1, T2;
1192

1193 1194
    if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
        return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1195

1196 1197
    mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
    mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 );
1198

1199
    if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
1200
    {
1201 1202
        if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
        if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
1203 1204 1205
        return( 0 );
    }

1206 1207
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
1208 1209
    X.s = Y.s = 1;

1210 1211 1212 1213
    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z,  0 ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) );
1214

1215
    k = mbedtls_mpi_bitlen( &Y ) % biL;
1216
    if( k < biL - 1 )
1217 1218
    {
        k = biL - 1 - k;
1219 1220
        MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
        MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
1221 1222 1223 1224 1225
    }
    else k = 0;

    n = X.n - 1;
    t = Y.n - 1;
1226
    MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
1227

1228
    while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
1229 1230
    {
        Z.p[n - t]++;