src/libpolarssl/bignum.c

   1 /*
   2  *  Multi-precision integer library
   3  *
   4  *  Copyright (C) 2006-2014, Brainspark B.V.
   5  *
   6  *  This file is part of PolarSSL (http://www.polarssl.org)
   7  *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
   8  *
   9  *  All rights reserved.
  10  *
  11  *  This program is free software; you can redistribute it and/or modify
  12  *  it under the terms of the GNU General Public License as published by
  13  *  the Free Software Foundation; either version 2 of the License, or
  14  *  (at your option) any later version.
  15  *
  16  *  This program is distributed in the hope that it will be useful,
  17  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  *  GNU General Public License for more details.
  20  *
  21  *  You should have received a copy of the GNU General Public License along
  22  *  with this program; if not, write to the Free Software Foundation, Inc.,
  23  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  24  */
  25 /*
  26  *  This MPI implementation is based on:
  27  *
  28  *  http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
  29  *  http://www.stillhq.com/extracted/gnupg-api/mpi/
  30  *  http://math.libtomcrypt.com/files/tommath.pdf
  31  */
  32
  33 #if !defined(POLARSSL_CONFIG_FILE)
  34 #include "config.h"
  35 #else
  36 #include POLARSSL_CONFIG_FILE
  37 #endif
  38
  39 #if defined(POLARSSL_BIGNUM_C)
  40
  41 #include "bignum.h"
  42 #include "bn_mul.h"
  43
  44 #if defined(POLARSSL_PLATFORM_C)
  45 #include "platform.h"
  46 #else
  47 #define polarssl_printf     printf
  48 #define polarssl_malloc     malloc
  49 #define polarssl_free       free
  50 #endif
  51
  52 #include <stdlib.h>
  53
  54 #define ciL    (sizeof(t_uint))         /* chars in limb  */
  55 #define biL    (ciL << 3)               /* bits  in limb  */
  56 #define biH    (ciL << 2)               /* half limb size */
  57
  58 /*
  59  * Convert between bits/chars and number of limbs
  60  */
  61 #define BITS_TO_LIMBS(i)  (((i) + biL - 1) / biL)
  62 #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
  63
  64 /*
  65  * Initialize one MPI
  66  */
  67 void mpi_init( mpi *X )
  68 {
  69     if( X == NULL )
  70         return;
  71
  72     X->s = 1;
  73     X->n = 0;
  74     X->p = NULL;
  75 }
  76
  77 /*
  78  * Unallocate one MPI
  79  */
  80 void mpi_free( mpi *X )
  81 {
  82     if( X == NULL )
  83         return;
  84
  85     if( X->p != NULL )
  86     {
  87         memset( X->p, 0, X->n * ciL );
  88         polarssl_free( X->p );
  89     }
  90
  91     X->s = 1;
  92     X->n = 0;
  93     X->p = NULL;
  94 }
  95
  96 /*
  97  * Enlarge to the specified number of limbs
  98  */
  99 int mpi_grow( mpi *X, size_t nblimbs )
 100 {
 101     t_uint *p;
 102
 103     if( nblimbs > POLARSSL_MPI_MAX_LIMBS )
 104         return( POLARSSL_ERR_MPI_MALLOC_FAILED );
 105
 106     if( X->n < nblimbs )
 107     {
 108         if( ( p = (t_uint *) polarssl_malloc( nblimbs * ciL ) ) == NULL )
 109             return( POLARSSL_ERR_MPI_MALLOC_FAILED );
 110
 111         memset( p, 0, nblimbs * ciL );
 112
 113         if( X->p != NULL )
 114         {
 115             memcpy( p, X->p, X->n * ciL );
 116             memset( X->p, 0, X->n * ciL );
 117             polarssl_free( X->p );
 118         }
 119
 120         X->n = nblimbs;
 121         X->p = p;
 122     }
 123
 124     return( 0 );
 125 }
 126
 127 /*
 128  * Resize down as much as possible,
 129  * while keeping at least the specified number of limbs
 130  */
 131 int mpi_shrink( mpi *X, size_t nblimbs )
 132 {
 133     t_uint *p;
 134     size_t i;
 135
 136     /* Actually resize up in this case */
 137     if( X->n <= nblimbs )
 138         return( mpi_grow( X, nblimbs ) );
 139
 140     for( i = X->n - 1; i > 0; i-- )
 141         if( X->p[i] != 0 )
 142             break;
 143     i++;
 144
 145     if( i < nblimbs )
 146         i = nblimbs;
 147
 148     if( ( p = (t_uint *) polarssl_malloc( i * ciL ) ) == NULL )
 149         return( POLARSSL_ERR_MPI_MALLOC_FAILED );
 150
 151     memset( p, 0, i * ciL );
 152
 153     if( X->p != NULL )
 154     {
 155         memcpy( p, X->p, i * ciL );
 156         memset( X->p, 0, X->n * ciL );
 157         polarssl_free( X->p );
 158     }
 159
 160     X->n = i;
 161     X->p = p;
 162
 163     return( 0 );
 164 }
 165
 166 /*
 167  * Copy the contents of Y into X
 168  */
 169 int mpi_copy( mpi *X, const mpi *Y )
 170 {
 171     int ret;
 172     size_t i;
 173
 174     if( X == Y )
 175         return( 0 );
 176
 177     if( Y->p == NULL )
 178     {
 179         mpi_free( X );
 180         return( 0 );
 181     }
 182
 183     for( i = Y->n - 1; i > 0; i-- )
 184         if( Y->p[i] != 0 )
 185             break;
 186     i++;
 187
 188     X->s = Y->s;
 189
 190     MPI_CHK( mpi_grow( X, i ) );
 191
 192     memset( X->p, 0, X->n * ciL );
 193     memcpy( X->p, Y->p, i * ciL );
 194
 195 cleanup:
 196
 197     return( ret );
 198 }
 199
 200 /*
 201  * Swap the contents of X and Y
 202  */
 203 void mpi_swap( mpi *X, mpi *Y )
 204 {
 205     mpi T;
 206
 207     memcpy( &T,  X, sizeof( mpi ) );
 208     memcpy(  X,  Y, sizeof( mpi ) );
 209     memcpy(  Y, &T, sizeof( mpi ) );
 210 }
 211
 212 /*
 213  * Conditionally assign X = Y, without leaking information
 214  * about whether the assignment was made or not.
 215  * (Leaking information about the respective sizes of X and Y is ok however.)
 216  */
 217 int mpi_safe_cond_assign( mpi *X, const mpi *Y, unsigned char assign )
 218 {
 219     int ret = 0;
 220     size_t i;
 221
 222     /* make sure assign is 0 or 1 */
 223     assign = ( assign != 0 );
 224
 225     MPI_CHK( 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 cleanup:
 236     return( ret );
 237 }
 238
 239 /*
 240  * Conditionally swap X and Y, without leaking information
 241  * about whether the swap was made or not.
 242  * Here it is not ok to simply swap the pointers, which whould lead to
 243  * different memory access patterns when X and Y are used afterwards.
 244  */
 245 int mpi_safe_cond_swap( mpi *X, mpi *Y, unsigned char swap )
 246 {
 247     int ret, s;
 248     size_t i;
 249     t_uint tmp;
 250
 251     if( X == Y )
 252         return( 0 );
 253
 254     /* make sure swap is 0 or 1 */
 255     swap = ( swap != 0 );
 256
 257     MPI_CHK( mpi_grow( X, Y->n ) );
 258     MPI_CHK( mpi_grow( Y, X->n ) );
 259
 260     s = X->s;
 261     X->s = X->s * (1 - swap) + Y->s * swap;
 262     Y->s = Y->s * (1 - swap) +    s * swap;
 263
 264
 265     for( i = 0; i < X->n; i++ )
 266     {
 267         tmp = X->p[i];
 268         X->p[i] = X->p[i] * (1 - swap) + Y->p[i] * swap;
 269         Y->p[i] = Y->p[i] * (1 - swap) +     tmp * swap;
 270     }
 271
 272 cleanup:
 273     return( ret );
 274 }
 275
 276 /*
 277  * Set value from integer
 278  */
 279 int mpi_lset( mpi *X, t_sint z )
 280 {
 281     int ret;
 282
 283     MPI_CHK( mpi_grow( X, 1 ) );
 284     memset( X->p, 0, X->n * ciL );
 285
 286     X->p[0] = ( z < 0 ) ? -z : z;
 287     X->s    = ( z < 0 ) ? -1 : 1;
 288
 289 cleanup:
 290
 291     return( ret );
 292 }
 293
 294 /*
 295  * Get a specific bit
 296  */
 297 int mpi_get_bit( const mpi *X, size_t pos )
 298 {
 299     if( X->n * biL <= pos )
 300         return( 0 );
 301
 302     return ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01;
 303 }
 304
 305 /*
 306  * Set a bit to a specific value of 0 or 1
 307  */
 308 int mpi_set_bit( mpi *X, size_t pos, unsigned char val )
 309 {
 310     int ret = 0;
 311     size_t off = pos / biL;
 312     size_t idx = pos % biL;
 313
 314     if( val != 0 && val != 1 )
 315         return POLARSSL_ERR_MPI_BAD_INPUT_DATA;
 316
 317     if( X->n * biL <= pos )
 318     {
 319         if( val == 0 )
 320             return ( 0 );
 321
 322         MPI_CHK( mpi_grow( X, off + 1 ) );
 323     }
 324
 325     X->p[off] &= ~( (t_uint) 0x01 << idx );
 326     X->p[off] |= (t_uint) val << idx;
 327
 328 cleanup:
 329
 330     return( ret );
 331 }
 332
 333 /*
 334  * Return the number of least significant bits
 335  */
 336 size_t mpi_lsb( const 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             if( ( ( X->p[i] >> j ) & 1 ) != 0 )
 343                 return( count );
 344
 345     return( 0 );
 346 }
 347
 348 /*
 349  * Return the number of most significant bits
 350  */
 351 size_t mpi_msb( const mpi *X )
 352 {
 353     size_t i, j;
 354
 355     for( i = X->n - 1; i > 0; i-- )
 356         if( X->p[i] != 0 )
 357             break;
 358
 359     for( j = biL; j > 0; j-- )
 360         if( ( ( X->p[i] >> ( j - 1 ) ) & 1 ) != 0 )
 361             break;
 362
 363     return( ( i * biL ) + j );
 364 }
 365
 366 /*
 367  * Return the total size in bytes
 368  */
 369 size_t mpi_size( const mpi *X )
 370 {
 371     return( ( mpi_msb( X ) + 7 ) >> 3 );
 372 }
 373
 374 /*
 375  * Convert an ASCII character to digit value
 376  */
 377 static int mpi_get_digit( t_uint *d, int radix, char c )
 378 {
 379     *d = 255;
 380
 381     if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
 382     if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
 383     if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
 384
 385     if( *d >= (t_uint) radix )
 386         return( POLARSSL_ERR_MPI_INVALID_CHARACTER );
 387
 388     return( 0 );
 389 }
 390
 391 /*
 392  * Import from an ASCII string
 393  */
 394 int mpi_read_string( mpi *X, int radix, const char *s )
 395 {
 396     int ret;
 397     size_t i, j, slen, n;
 398     t_uint d;
 399     mpi T;
 400
 401     if( radix < 2 || radix > 16 )
 402         return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
 403
 404     mpi_init( &T );
 405
 406     slen = strlen( s );
 407
 408     if( radix == 16 )
 409     {
 410         n = BITS_TO_LIMBS( slen << 2 );
 411
 412         MPI_CHK( mpi_grow( X, n ) );
 413         MPI_CHK( mpi_lset( X, 0 ) );
 414
 415         for( i = slen, j = 0; i > 0; i--, j++ )
 416         {
 417             if( i == 1 && s[i - 1] == '-' )
 418             {
 419                 X->s = -1;
 420                 break;
 421             }
 422
 423             MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
 424             X->p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 );
 425         }
 426     }
 427     else
 428     {
 429         MPI_CHK( mpi_lset( X, 0 ) );
 430
 431         for( i = 0; i < slen; i++ )
 432         {
 433             if( i == 0 && s[i] == '-' )
 434             {
 435                 X->s = -1;
 436                 continue;
 437             }
 438
 439             MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
 440             MPI_CHK( mpi_mul_int( &T, X, radix ) );
 441
 442             if( X->s == 1 )
 443             {
 444                 MPI_CHK( mpi_add_int( X, &T, d ) );
 445             }
 446             else
 447             {
 448                 MPI_CHK( mpi_sub_int( X, &T, d ) );
 449             }
 450         }
 451     }
 452
 453 cleanup:
 454
 455     mpi_free( &T );
 456
 457     return( ret );
 458 }
 459
 460 /*
 461  * Helper to write the digits high-order first
 462  */
 463 static int mpi_write_hlp( mpi *X, int radix, char **p )
 464 {
 465     int ret;
 466     t_uint r;
 467
 468     if( radix < 2 || radix > 16 )
 469         return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
 470
 471     MPI_CHK( mpi_mod_int( &r, X, radix ) );
 472     MPI_CHK( mpi_div_int( X, NULL, X, radix ) );
 473
 474     if( mpi_cmp_int( X, 0 ) != 0 )
 475         MPI_CHK( mpi_write_hlp( X, radix, p ) );
 476
 477     if( r < 10 )
 478         *(*p)++ = (char)( r + 0x30 );
 479     else
 480         *(*p)++ = (char)( r + 0x37 );
 481
 482 cleanup:
 483
 484     return( ret );
 485 }
 486
 487 /*
 488  * Export into an ASCII string
 489  */
 490 int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen )
 491 {
 492     int ret = 0;
 493     size_t n;
 494     char *p;
 495     mpi T;
 496
 497     if( radix < 2 || radix > 16 )
 498         return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
 499
 500     n = mpi_msb( X );
 501     if( radix >=  4 ) n >>= 1;
 502     if( radix >= 16 ) n >>= 1;
 503     n += 3;
 504
 505     if( *slen < n )
 506     {
 507         *slen = n;
 508         return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
 509     }
 510
 511     p = s;
 512     mpi_init( &T );
 513
 514     if( X->s == -1 )
 515         *p++ = '-';
 516
 517     if( radix == 16 )
 518     {
 519         int c;
 520         size_t i, j, k;
 521
 522         for( i = X->n, k = 0; i > 0; i-- )
 523         {
 524             for( j = ciL; j > 0; j-- )
 525             {
 526                 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
 527
 528                 if( c == 0 && k == 0 && ( i + j + 3 ) != 0 )
 529                     continue;
 530
 531                 *(p++) = "0123456789ABCDEF" [c / 16];
 532                 *(p++) = "0123456789ABCDEF" [c % 16];
 533                 k = 1;
 534             }
 535         }
 536     }
 537     else
 538     {
 539         MPI_CHK( mpi_copy( &T, X ) );
 540
 541         if( T.s == -1 )
 542             T.s = 1;
 543
 544         MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
 545     }
 546
 547     *p++ = '\0';
 548     *slen = p - s;
 549
 550 cleanup:
 551
 552     mpi_free( &T );
 553
 554     return( ret );
 555 }
 556
 557 #if defined(POLARSSL_FS_IO)
 558 /*
 559  * Read X from an opened file
 560  */
 561 int mpi_read_file( mpi *X, int radix, FILE *fin )
 562 {
 563     t_uint d;
 564     size_t slen;
 565     char *p;
 566     /*
 567      * Buffer should have space for (short) label and decimal formatted MPI,
 568      * newline characters and '\0'
 569      */
 570     char s[ POLARSSL_MPI_RW_BUFFER_SIZE ];
 571
 572     memset( s, 0, sizeof( s ) );
 573     if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
 574         return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
 575
 576     slen = strlen( s );
 577     if( slen == sizeof( s ) - 2 )
 578         return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
 579
 580     if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
 581     if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
 582
 583     p = s + slen;
 584     while( --p >= s )
 585         if( mpi_get_digit( &d, radix, *p ) != 0 )
 586             break;
 587
 588     return( mpi_read_string( X, radix, p + 1 ) );
 589 }
 590
 591 /*
 592  * Write X into an opened file (or stdout if fout == NULL)
 593  */
 594 int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout )
 595 {
 596     int ret;
 597     size_t n, slen, plen;
 598     /*
 599      * Buffer should have space for (short) label and decimal formatted MPI,
 600      * newline characters and '\0'
 601      */
 602     char s[ POLARSSL_MPI_RW_BUFFER_SIZE ];
 603
 604     n = sizeof( s );
 605     memset( s, 0, n );
 606     n -= 2;
 607
 608     MPI_CHK( mpi_write_string( X, radix, s, (size_t *) &n ) );
 609
 610     if( p == NULL ) p = "";
 611
 612     plen = strlen( p );
 613     slen = strlen( s );
 614     s[slen++] = '\r';
 615     s[slen++] = '\n';
 616
 617     if( fout != NULL )
 618     {
 619         if( fwrite( p, 1, plen, fout ) != plen ||
 620             fwrite( s, 1, slen, fout ) != slen )
 621             return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
 622     }
 623     else
 624         polarssl_printf( "%s%s", p, s );
 625
 626 cleanup:
 627
 628     return( ret );
 629 }
 630 #endif /* POLARSSL_FS_IO */
 631
 632 /*
 633  * Import X from unsigned binary data, big endian
 634  */
 635 int mpi_read_binary( mpi *X, const unsigned char *buf, size_t buflen )
 636 {
 637     int ret;
 638     size_t i, j, n;
 639
 640     for( n = 0; n < buflen; n++ )
 641         if( buf[n] != 0 )
 642             break;
 643
 644     MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );
 645     MPI_CHK( mpi_lset( X, 0 ) );
 646
 647     for( i = buflen, j = 0; i > n; i--, j++ )
 648         X->p[j / ciL] |= ((t_uint) buf[i - 1]) << ((j % ciL) << 3);
 649
 650 cleanup:
 651
 652     return( ret );
 653 }
 654
 655 /*
 656  * Export X into unsigned binary data, big endian
 657  */
 658 int mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen )
 659 {
 660     size_t i, j, n;
 661
 662     n = mpi_size( X );
 663
 664     if( buflen < n )
 665         return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
 666
 667     memset( buf, 0, buflen );
 668
 669     for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
 670         buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
 671
 672     return( 0 );
 673 }
 674
 675 /*
 676  * Left-shift: X <<= count
 677  */
 678 int mpi_shift_l( mpi *X, size_t count )
 679 {
 680     int ret;
 681     size_t i, v0, t1;
 682     t_uint r0 = 0, r1;
 683
 684     v0 = count / (biL    );
 685     t1 = count & (biL - 1);
 686
 687     i = mpi_msb( X ) + count;
 688
 689     if( X->n * biL < i )
 690         MPI_CHK( mpi_grow( X, BITS_TO_LIMBS( i ) ) );
 691
 692     ret = 0;
 693
 694     /*
 695      * shift by count / limb_size
 696      */
 697     if( v0 > 0 )
 698     {
 699         for( i = X->n; i > v0; i-- )
 700             X->p[i - 1] = X->p[i - v0 - 1];
 701
 702         for( ; i > 0; i-- )
 703             X->p[i - 1] = 0;
 704     }
 705
 706     /*
 707      * shift by count % limb_size
 708      */
 709     if( t1 > 0 )
 710     {
 711         for( i = v0; i < X->n; i++ )
 712         {
 713             r1 = X->p[i] >> (biL - t1);
 714             X->p[i] <<= t1;
 715             X->p[i] |= r0;
 716             r0 = r1;
 717         }
 718     }
 719
 720 cleanup:
 721
 722     return( ret );
 723 }
 724
 725 /*
 726  * Right-shift: X >>= count
 727  */
 728 int mpi_shift_r( mpi *X, size_t count )
 729 {
 730     size_t i, v0, v1;
 731     t_uint r0 = 0, r1;
 732
 733     v0 = count /  biL;
 734     v1 = count & (biL - 1);
 735
 736     if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
 737         return mpi_lset( X, 0 );
 738
 739     /*
 740      * shift by count / limb_size
 741      */
 742     if( v0 > 0 )
 743     {
 744         for( i = 0; i < X->n - v0; i++ )
 745             X->p[i] = X->p[i + v0];
 746
 747         for( ; i < X->n; i++ )
 748             X->p[i] = 0;
 749     }
 750
 751     /*
 752      * shift by count % limb_size
 753      */
 754     if( v1 > 0 )
 755     {
 756         for( i = X->n; i > 0; i-- )
 757         {
 758             r1 = X->p[i - 1] << (biL - v1);
 759             X->p[i - 1] >>= v1;
 760             X->p[i - 1] |= r0;
 761             r0 = r1;
 762         }
 763     }
 764
 765     return( 0 );
 766 }
 767
 768 /*
 769  * Compare unsigned values
 770  */
 771 int mpi_cmp_abs( const mpi *X, const mpi *Y )
 772 {
 773     size_t i, j;
 774
 775     for( i = X->n; i > 0; i-- )
 776         if( X->p[i - 1] != 0 )
 777             break;
 778
 779     for( j = Y->n; j > 0; j-- )
 780         if( Y->p[j - 1] != 0 )
 781             break;
 782
 783     if( i == 0 && j == 0 )
 784         return( 0 );
 785
 786     if( i > j ) return(  1 );
 787     if( j > i ) return( -1 );
 788
 789     for( ; i > 0; i-- )
 790     {
 791         if( X->p[i - 1] > Y->p[i - 1] ) return(  1 );
 792         if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
 793     }
 794
 795     return( 0 );
 796 }
 797
 798 /*
 799  * Compare signed values
 800  */
 801 int mpi_cmp_mpi( const mpi *X, const mpi *Y )
 802 {
 803     size_t i, j;
 804
 805     for( i = X->n; i > 0; i-- )
 806         if( X->p[i - 1] != 0 )
 807             break;
 808
 809     for( j = Y->n; j > 0; j-- )
 810         if( Y->p[j - 1] != 0 )
 811             break;
 812
 813     if( i == 0 && j == 0 )
 814         return( 0 );
 815
 816     if( i > j ) return(  X->s );
 817     if( j > i ) return( -Y->s );
 818
 819     if( X->s > 0 && Y->s < 0 ) return(  1 );
 820     if( Y->s > 0 && X->s < 0 ) return( -1 );
 821
 822     for( ; i > 0; i-- )
 823     {
 824         if( X->p[i - 1] > Y->p[i - 1] ) return(  X->s );
 825         if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
 826     }
 827
 828     return( 0 );
 829 }
 830
 831 /*
 832  * Compare signed values
 833  */
 834 int mpi_cmp_int( const mpi *X, t_sint z )
 835 {
 836     mpi Y;
 837     t_uint p[1];
 838
 839     *p  = ( z < 0 ) ? -z : z;
 840     Y.s = ( z < 0 ) ? -1 : 1;
 841     Y.n = 1;
 842     Y.p = p;
 843
 844     return( mpi_cmp_mpi( X, &Y ) );
 845 }
 846
 847 /*
 848  * Unsigned addition: X = |A| + |B|  (HAC 14.7)
 849  */
 850 int mpi_add_abs( mpi *X, const mpi *A, const mpi *B )
 851 {
 852     int ret;
 853     size_t i, j;
 854     t_uint *o, *p, c;
 855
 856     if( X == B )
 857     {
 858         const mpi *T = A; A = X; B = T;
 859     }
 860
 861     if( X != A )
 862         MPI_CHK( mpi_copy( X, A ) );
 863
 864     /*
 865      * X should always be positive as a result of unsigned additions.
 866      */
 867     X->s = 1;
 868
 869     for( j = B->n; j > 0; j-- )
 870         if( B->p[j - 1] != 0 )
 871             break;
 872
 873     MPI_CHK( mpi_grow( X, j ) );
 874
 875     o = B->p; p = X->p; c = 0;
 876
 877     for( i = 0; i < j; i++, o++, p++ )
 878     {
 879         *p +=  c; c  = ( *p <  c );
 880         *p += *o; c += ( *p < *o );
 881     }
 882
 883     while( c != 0 )
 884     {
 885         if( i >= X->n )
 886         {
 887             MPI_CHK( mpi_grow( X, i + 1 ) );
 888             p = X->p + i;
 889         }
 890
 891         *p += c; c = ( *p < c ); i++; p++;
 892     }
 893
 894 cleanup:
 895
 896     return( ret );
 897 }
 898
 899 /*
 900  * Helper for mpi subtraction
 901  */
 902 static void mpi_sub_hlp( size_t n, t_uint *s, t_uint *d )
 903 {
 904     size_t i;
 905     t_uint c, z;
 906
 907     for( i = c = 0; i < n; i++, s++, d++ )
 908     {
 909         z = ( *d <  c );     *d -=  c;
 910         c = ( *d < *s ) + z; *d -= *s;
 911     }
 912
 913     while( c != 0 )
 914     {
 915         z = ( *d < c ); *d -= c;
 916         c = z; i++; d++;
 917     }
 918 }
 919
 920 /*
 921  * Unsigned subtraction: X = |A| - |B|  (HAC 14.9)
 922  */
 923 int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B )
 924 {
 925     mpi TB;
 926     int ret;
 927     size_t n;
 928
 929     if( mpi_cmp_abs( A, B ) < 0 )
 930         return( POLARSSL_ERR_MPI_NEGATIVE_VALUE );
 931
 932     mpi_init( &TB );
 933
 934     if( X == B )
 935     {
 936         MPI_CHK( mpi_copy( &TB, B ) );
 937         B = &TB;
 938     }
 939
 940     if( X != A )
 941         MPI_CHK( mpi_copy( X, A ) );
 942
 943     /*
 944      * X should always be positive as a result of unsigned subtractions.
 945      */
 946     X->s = 1;
 947
 948     ret = 0;
 949
 950     for( n = B->n; n > 0; n-- )
 951         if( B->p[n - 1] != 0 )
 952             break;
 953
 954     mpi_sub_hlp( n, B->p, X->p );
 955
 956 cleanup:
 957
 958     mpi_free( &TB );
 959
 960     return( ret );
 961 }
 962
 963 /*
 964  * Signed addition: X = A + B
 965  */
 966 int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B )
 967 {
 968     int ret, s = A->s;
 969
 970     if( A->s * B->s < 0 )
 971     {
 972         if( mpi_cmp_abs( A, B ) >= 0 )
 973         {
 974             MPI_CHK( mpi_sub_abs( X, A, B ) );
 975             X->s =  s;
 976         }
 977         else
 978         {
 979             MPI_CHK( mpi_sub_abs( X, B, A ) );
 980             X->s = -s;
 981         }
 982     }
 983     else
 984     {
 985         MPI_CHK( mpi_add_abs( X, A, B ) );
 986         X->s = s;
 987     }
 988
 989 cleanup:
 990
 991     return( ret );
 992 }
 993
 994 /*
 995  * Signed subtraction: X = A - B
 996  */
 997 int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B )
 998 {
 999     int ret, s = A->s;
1000
1001     if( A->s * B->s > 0 )
1002     {
1003         if( mpi_cmp_abs( A, B ) >= 0 )
1004         {
1005             MPI_CHK( mpi_sub_abs( X, A, B ) );
1006             X->s =  s;
1007         }
1008         else
1009         {
1010             MPI_CHK( mpi_sub_abs( X, B, A ) );
1011             X->s = -s;
1012         }
1013     }
1014     else
1015     {
1016         MPI_CHK( mpi_add_abs( X, A, B ) );
1017         X->s = s;
1018     }
1019
1020 cleanup:
1021
1022     return( ret );
1023 }
1024
1025 /*
1026  * Signed addition: X = A + b
1027  */
1028 int mpi_add_int( mpi *X, const mpi *A, t_sint b )
1029 {
1030     mpi _B;
1031     t_uint p[1];
1032
1033     p[0] = ( b < 0 ) ? -b : b;
1034     _B.s = ( b < 0 ) ? -1 : 1;
1035     _B.n = 1;
1036     _B.p = p;
1037
1038     return( mpi_add_mpi( X, A, &_B ) );
1039 }
1040
1041 /*
1042  * Signed subtraction: X = A - b
1043  */
1044 int mpi_sub_int( mpi *X, const mpi *A, t_sint b )
1045 {
1046     mpi _B;
1047     t_uint p[1];
1048
1049     p[0] = ( b < 0 ) ? -b : b;
1050     _B.s = ( b < 0 ) ? -1 : 1;
1051     _B.n = 1;
1052     _B.p = p;
1053
1054     return( mpi_sub_mpi( X, A, &_B ) );
1055 }
1056
1057 /*
1058  * Helper for mpi multiplication
1059  */
1060 static
1061 #if defined(__APPLE__) && defined(__arm__)
1062 /*
1063  * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1064  * appears to need this to prevent bad ARM code generation at -O3.
1065  */
1066 __attribute__ ((noinline))
1067 #endif
1068 void mpi_mul_hlp( size_t i, t_uint *s, t_uint *d, t_uint b )
1069 {
1070     t_uint c = 0, t = 0;
1071
1072 #if defined(MULADDC_HUIT)
1073     for( ; i >= 8; i -= 8 )
1074     {
1075         MULADDC_INIT
1076         MULADDC_HUIT
1077         MULADDC_STOP
1078     }
1079
1080     for( ; i > 0; i-- )
1081     {
1082         MULADDC_INIT
1083         MULADDC_CORE
1084         MULADDC_STOP
1085     }
1086 #else /* MULADDC_HUIT */
1087     for( ; i >= 16; i -= 16 )
1088     {
1089         MULADDC_INIT
1090         MULADDC_CORE   MULADDC_CORE
1091         MULADDC_CORE   MULADDC_CORE
1092         MULADDC_CORE   MULADDC_CORE
1093         MULADDC_CORE   MULADDC_CORE
1094
1095         MULADDC_CORE   MULADDC_CORE
1096         MULADDC_CORE   MULADDC_CORE
1097         MULADDC_CORE   MULADDC_CORE
1098         MULADDC_CORE   MULADDC_CORE
1099         MULADDC_STOP
1100     }
1101
1102     for( ; i >= 8; i -= 8 )
1103     {
1104         MULADDC_INIT
1105         MULADDC_CORE   MULADDC_CORE
1106         MULADDC_CORE   MULADDC_CORE
1107
1108         MULADDC_CORE   MULADDC_CORE
1109         MULADDC_CORE   MULADDC_CORE
1110         MULADDC_STOP
1111     }
1112
1113     for( ; i > 0; i-- )
1114     {
1115         MULADDC_INIT
1116         MULADDC_CORE
1117         MULADDC_STOP
1118     }
1119 #endif /* MULADDC_HUIT */
1120
1121     t++;
1122
1123     do {
1124         *d += c; c = ( *d < c ); d++;
1125     }
1126     while( c != 0 );
1127 }
1128
1129 /*
1130  * Baseline multiplication: X = A * B  (HAC 14.12)
1131  */
1132 int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B )
1133 {
1134     int ret;
1135     size_t i, j;
1136     mpi TA, TB;
1137
1138     mpi_init( &TA ); mpi_init( &TB );
1139
1140     if( X == A ) { MPI_CHK( mpi_copy( &TA, A ) ); A = &TA; }
1141     if( X == B ) { MPI_CHK( mpi_copy( &TB, B ) ); B = &TB; }
1142
1143     for( i = A->n; i > 0; i-- )
1144         if( A->p[i - 1] != 0 )
1145             break;
1146
1147     for( j = B->n; j > 0; j-- )
1148         if( B->p[j - 1] != 0 )
1149             break;
1150
1151     MPI_CHK( mpi_grow( X, i + j ) );
1152     MPI_CHK( mpi_lset( X, 0 ) );
1153
1154     for( i++; j > 0; j-- )
1155         mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] );
1156
1157     X->s = A->s * B->s;
1158
1159 cleanup:
1160
1161     mpi_free( &TB ); mpi_free( &TA );
1162
1163     return( ret );
1164 }
1165
1166 /*
1167  * Baseline multiplication: X = A * b
1168  */
1169 int mpi_mul_int( mpi *X, const mpi *A, t_sint b )
1170 {
1171     mpi _B;
1172     t_uint p[1];
1173
1174     _B.s = 1;
1175     _B.n = 1;
1176     _B.p = p;
1177     p[0] = b;
1178
1179     return( mpi_mul_mpi( X, A, &_B ) );
1180 }
1181
1182 /*
1183  * Division by mpi: A = Q * B + R  (HAC 14.20)
1184  */
1185 int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B )
1186 {
1187     int ret;
1188     size_t i, n, t, k;
1189     mpi X, Y, Z, T1, T2;
1190
1191     if( mpi_cmp_int( B, 0 ) == 0 )
1192         return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
1193
1194     mpi_init( &X ); mpi_init( &Y ); mpi_init( &Z );
1195     mpi_init( &T1 ); mpi_init( &T2 );
1196
1197     if( mpi_cmp_abs( A, B ) < 0 )
1198     {
1199         if( Q != NULL ) MPI_CHK( mpi_lset( Q, 0 ) );
1200         if( R != NULL ) MPI_CHK( mpi_copy( R, A ) );
1201         return( 0 );
1202     }
1203
1204     MPI_CHK( mpi_copy( &X, A ) );
1205     MPI_CHK( mpi_copy( &Y, B ) );
1206     X.s = Y.s = 1;
1207
1208     MPI_CHK( mpi_grow( &Z, A->n + 2 ) );
1209     MPI_CHK( mpi_lset( &Z,  0 ) );
1210     MPI_CHK( mpi_grow( &T1, 2 ) );
1211     MPI_CHK( mpi_grow( &T2, 3 ) );
1212
1213     k = mpi_msb( &Y ) % biL;
1214     if( k < biL - 1 )
1215     {
1216         k = biL - 1 - k;
1217         MPI_CHK( mpi_shift_l( &X, k ) );
1218         MPI_CHK( mpi_shift_l( &Y, k ) );
1219     }
1220     else k = 0;
1221
1222     n = X.n - 1;
1223     t = Y.n - 1;
1224     MPI_CHK( mpi_shift_l( &Y, biL * (n - t) ) );
1225
1226     while( mpi_cmp_mpi( &X, &Y ) >= 0 )
1227     {
1228         Z.p[n - t]++;
1229         MPI_CHK( mpi_sub_mpi( &X, &X, &Y ) );
1230     }
1231     MPI_CHK( mpi_shift_r( &Y, biL * (n - t) ) );
1232
1233     for( i = n; i > t ; i-- )
1234     {
1235         if( X.p[i] >= Y.p[t] )
1236             Z.p[i - t - 1] = ~0;
1237         else
1238         {
1239             /*
1240              * The version of Clang shipped by Apple with Mavericks around
1241              * 2014-03 can't handle 128-bit division properly. Disable
1242              * 128-bits division for this version. Let's be optimistic and
1243              * assume it'll be fixed in the next minor version (next
1244              * patchlevel is probably a bit too optimistic).
1245              */
1246 #if defined(POLARSSL_HAVE_UDBL) &&                          \
1247     ! ( defined(__x86_64__) && defined(__APPLE__) &&        \
1248         defined(__clang_major__) && __clang_major__ == 5 && \
1249         defined(__clang_minor__) && __clang_minor__ == 0 )
1250             t_udbl r;
1251
1252             r  = (t_udbl) X.p[i] << biL;
1253             r |= (t_udbl) X.p[i - 1];
1254             r /= Y.p[t];
1255             if( r > ((t_udbl) 1 << biL) - 1)
1256                 r = ((t_udbl) 1 << biL) - 1;
1257
1258             Z.p[i - t - 1] = (t_uint) r;
1259 #else
1260             /*
1261              * __udiv_qrnnd_c, from gmp/longlong.h
1262              */
1263             t_uint q0, q1, r0, r1;
1264             t_uint d0, d1, d, m;
1265
1266             d  = Y.p[t];
1267             d0 = ( d << biH ) >> biH;
1268             d1 = ( d >> biH );
1269
1270             q1 = X.p[i] / d1;
1271             r1 = X.p[i] - d1 * q1;
1272             r1 <<= biH;
1273             r1 |= ( X.p[i - 1] >> biH );
1274
1275             m = q1 * d0;
1276             if( r1 < m )
1277             {
1278                 q1--, r1 += d;
1279                 while( r1 >= d && r1 < m )
1280                     q1--, r1 += d;
1281             }
1282             r1 -= m;
1283
1284             q0 = r1 / d1;
1285             r0 = r1 - d1 * q0;
1286             r0 <<= biH;
1287             r0 |= ( X.p[i - 1] << biH ) >> biH;
1288
1289             m = q0 * d0;
1290             if( r0 < m )
1291             {
1292                 q0--, r0 += d;
1293                 while( r0 >= d && r0 < m )
1294                     q0--, r0 += d;
1295             }
1296             r0 -= m;
1297
1298             Z.p[i - t - 1] = ( q1 << biH ) | q0;
1299 #endif
1300         }
1301
1302         Z.p[i - t - 1]++;
1303         do
1304         {
1305             Z.p[i - t - 1]--;
1306
1307             MPI_CHK( mpi_lset( &T1, 0 ) );
1308             T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
1309             T1.p[1] = Y.p[t];
1310             MPI_CHK( mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
1311
1312             MPI_CHK( mpi_lset( &T2, 0 ) );
1313             T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
1314             T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
1315             T2.p[2] = X.p[i];
1316         }
1317         while( mpi_cmp_mpi( &T1, &T2 ) > 0 );
1318
1319         MPI_CHK( mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1320         MPI_CHK( mpi_shift_l( &T1,  biL * (i - t - 1) ) );
1321         MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) );
1322
1323         if( mpi_cmp_int( &X, 0 ) < 0 )
1324         {
1325             MPI_CHK( mpi_copy( &T1, &Y ) );
1326             MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
1327             MPI_CHK( mpi_add_mpi( &X, &X, &T1 ) );
1328             Z.p[i - t - 1]--;
1329         }
1330     }
1331
1332     if( Q != NULL )
1333     {
1334         MPI_CHK( mpi_copy( Q, &Z ) );
1335         Q->s = A->s * B->s;
1336     }
1337
1338     if( R != NULL )
1339     {
1340         MPI_CHK( mpi_shift_r( &X, k ) );
1341         X.s = A->s;
1342         MPI_CHK( mpi_copy( R, &X ) );
1343
1344         if( mpi_cmp_int( R, 0 ) == 0 )
1345             R->s = 1;
1346     }
1347
1348 cleanup:
1349
1350     mpi_free( &X ); mpi_free( &Y ); mpi_free( &Z );
1351     mpi_free( &T1 ); mpi_free( &T2 );
1352
1353     return( ret );
1354 }
1355
1356 /*
1357  * Division by int: A = Q * b + R
1358  */
1359 int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b )
1360 {
1361     mpi _B;
1362     t_uint p[1];
1363
1364     p[0] = ( b < 0 ) ? -b : b;
1365     _B.s = ( b < 0 ) ? -1 : 1;
1366     _B.n = 1;
1367     _B.p = p;
1368
1369     return( mpi_div_mpi( Q, R, A, &_B ) );
1370 }
1371
1372 /*
1373  * Modulo: R = A mod B
1374  */
1375 int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B )
1376 {
1377     int ret;
1378
1379     if( mpi_cmp_int( B, 0 ) < 0 )
1380         return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
1381
1382     MPI_CHK( mpi_div_mpi( NULL, R, A, B ) );
1383
1384     while( mpi_cmp_int( R, 0 ) < 0 )
1385       MPI_CHK( mpi_add_mpi( R, R, B ) );
1386
1387     while( mpi_cmp_mpi( R, B ) >= 0 )
1388       MPI_CHK( mpi_sub_mpi( R, R, B ) );
1389
1390 cleanup:
1391
1392     return( ret );
1393 }
1394
1395 /*
1396  * Modulo: r = A mod b
1397  */
1398 int mpi_mod_int( t_uint *r, const mpi *A, t_sint b )
1399 {
1400     size_t i;
1401     t_uint x, y, z;
1402
1403     if( b == 0 )
1404         return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
1405
1406     if( b < 0 )
1407         return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
1408
1409     /*
1410      * handle trivial cases
1411      */
1412     if( b == 1 )
1413     {
1414         *r = 0;
1415         return( 0 );
1416     }
1417
1418     if( b == 2 )
1419     {
1420         *r = A->p[0] & 1;
1421         return( 0 );
1422     }
1423
1424     /*
1425      * general case
1426      */
1427     for( i = A->n, y = 0; i > 0; i-- )
1428     {
1429         x  = A->p[i - 1];
1430         y  = ( y << biH ) | ( x >> biH );
1431         z  = y / b;
1432         y -= z * b;
1433
1434         x <<= biH;
1435         y  = ( y << biH ) | ( x >> biH );
1436         z  = y / b;
1437         y -= z * b;
1438     }
1439
1440     /*
1441      * If A is negative, then the current y represents a negative value.
1442      * Flipping it to the positive side.
1443      */
1444     if( A->s < 0 && y != 0 )
1445         y = b - y;
1446
1447     *r = y;
1448
1449     return( 0 );
1450 }
1451
1452 /*
1453  * Fast Montgomery initialization (thanks to Tom St Denis)
1454  */
1455 static void mpi_montg_init( t_uint *mm, const mpi *N )
1456 {
1457     t_uint x, m0 = N->p[0];
1458     unsigned int i;
1459
1460     x  = m0;
1461     x += ( ( m0 + 2 ) & 4 ) << 1;
1462
1463     for( i = biL; i >= 8; i /= 2 )
1464         x *= ( 2 - ( m0 * x ) );
1465
1466     *mm = ~x + 1;
1467 }
1468
1469 /*
1470  * Montgomery multiplication: A = A * B * R^-1 mod N  (HAC 14.36)
1471  */
1472 static void mpi_montmul( mpi *A, const mpi *B, const mpi *N, t_uint mm,
1473                          const mpi *T )
1474 {
1475     size_t i, n, m;
1476     t_uint u0, u1, *d;
1477
1478     memset( T->p, 0, T->n * ciL );
1479
1480     d = T->p;
1481     n = N->n;
1482     m = ( B->n < n ) ? B->n : n;
1483
1484     for( i = 0; i < n; i++ )
1485     {
1486         /*
1487          * T = (T + u0*B + u1*N) / 2^biL
1488          */
1489         u0 = A->p[i];
1490         u1 = ( d[0] + u0 * B->p[0] ) * mm;
1491
1492         mpi_mul_hlp( m, B->p, d, u0 );
1493         mpi_mul_hlp( n, N->p, d, u1 );
1494
1495         *d++ = u0; d[n + 1] = 0;
1496     }
1497
1498     memcpy( A->p, d, (n + 1) * ciL );
1499
1500     if( mpi_cmp_abs( A, N ) >= 0 )
1501         mpi_sub_hlp( n, N->p, A->p );
1502     else
1503         /* prevent timing attacks */
1504         mpi_sub_hlp( n, A->p, T->p );
1505 }
1506
1507 /*
1508  * Montgomery reduction: A = A * R^-1 mod N
1509  */
1510 static void mpi_montred( mpi *A, const mpi *N, t_uint mm, const mpi *T )
1511 {
1512     t_uint z = 1;
1513     mpi U;
1514
1515     U.n = U.s = (int) z;
1516     U.p = &z;
1517
1518     mpi_montmul( A, &U, N, mm, T );
1519 }
1520
1521 /*
1522  * Sliding-window exponentiation: X = A^E mod N  (HAC 14.85)
1523  */
1524 int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR )
1525 {
1526     int ret;
1527     size_t wbits, wsize, one = 1;
1528     size_t i, j, nblimbs;
1529     size_t bufsize, nbits;
1530     t_uint ei, mm, state;
1531     mpi RR, T, W[ 2 << POLARSSL_MPI_WINDOW_SIZE ], Apos;
1532     int neg;
1533
1534     if( mpi_cmp_int( N, 0 ) < 0 || ( N->p[0] & 1 ) == 0 )
1535         return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1536
1537     if( mpi_cmp_int( E, 0 ) < 0 )
1538         return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1539
1540     /*
1541      * Init temps and window size
1542      */
1543     mpi_montg_init( &mm, N );
1544     mpi_init( &RR ); mpi_init( &T );
1545     mpi_init( &Apos );
1546     memset( W, 0, sizeof( W ) );
1547
1548     i = mpi_msb( E );
1549
1550     wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1551             ( i >  79 ) ? 4 : ( i >  23 ) ? 3 : 1;
1552
1553     if( wsize > POLARSSL_MPI_WINDOW_SIZE )
1554         wsize = POLARSSL_MPI_WINDOW_SIZE;
1555
1556     j = N->n + 1;
1557     MPI_CHK( mpi_grow( X, j ) );
1558     MPI_CHK( mpi_grow( &W[1],  j ) );
1559     MPI_CHK( mpi_grow( &T, j * 2 ) );
1560
1561     /*
1562      * Compensate for negative A (and correct at the end)
1563      */
1564     neg = ( A->s == -1 );
1565     if( neg )
1566     {
1567         MPI_CHK( mpi_copy( &Apos, A ) );
1568         Apos.s = 1;
1569         A = &Apos;
1570     }
1571
1572     /*
1573      * If 1st call, pre-compute R^2 mod N
1574      */
1575     if( _RR == NULL || _RR->p == NULL )
1576     {
1577         MPI_CHK( mpi_lset( &RR, 1 ) );
1578         MPI_CHK( mpi_shift_l( &RR, N->n * 2 * biL ) );
1579         MPI_CHK( mpi_mod_mpi( &RR, &RR, N ) );
1580
1581         if( _RR != NULL )
1582             memcpy( _RR, &RR, sizeof( mpi ) );
1583     }
1584     else
1585         memcpy( &RR, _RR, sizeof( mpi ) );
1586
1587     /*
1588      * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1589      */
1590     if( mpi_cmp_mpi( A, N ) >= 0 )
1591         MPI_CHK( mpi_mod_mpi( &W[1], A, N ) );
1592     else
1593         MPI_CHK( mpi_copy( &W[1], A ) );
1594
1595     mpi_montmul( &W[1], &RR, N, mm, &T );
1596
1597     /*
1598      * X = R^2 * R^-1 mod N = R mod N
1599      */
1600     MPI_CHK( mpi_copy( X, &RR ) );
1601     mpi_montred( X, N, mm, &T );
1602
1603     if( wsize > 1 )
1604     {
1605         /*
1606          * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1607          */
1608         j =  one << (wsize - 1);
1609
1610         MPI_CHK( mpi_grow( &W[j], N->n + 1 ) );
1611         MPI_CHK( mpi_copy( &W[j], &W[1]    ) );
1612
1613         for( i = 0; i < wsize - 1; i++ )
1614             mpi_montmul( &W[j], &W[j], N, mm, &T );
1615
1616         /*
1617          * W[i] = W[i - 1] * W[1]
1618          */
1619         for( i = j + 1; i < (one << wsize); i++ )
1620         {
1621             MPI_CHK( mpi_grow( &W[i], N->n + 1 ) );
1622             MPI_CHK( mpi_copy( &W[i], &W[i - 1] ) );
1623
1624             mpi_montmul( &W[i], &W[1], N, mm, &T );
1625         }
1626     }
1627
1628     nblimbs = E->n;
1629     bufsize = 0;
1630     nbits   = 0;
1631     wbits   = 0;
1632     state   = 0;
1633
1634     while( 1 )
1635     {
1636         if( bufsize == 0 )
1637         {
1638             if( nblimbs == 0 )
1639                 break;
1640
1641             nblimbs--;
1642
1643             bufsize = sizeof( t_uint ) << 3;
1644         }
1645
1646         bufsize--;
1647
1648         ei = (E->p[nblimbs] >> bufsize) & 1;
1649
1650         /*
1651          * skip leading 0s
1652          */
1653         if( ei == 0 && state == 0 )
1654             continue;
1655
1656         if( ei == 0 && state == 1 )
1657         {
1658             /*
1659              * out of window, square X
1660              */
1661             mpi_montmul( X, X, N, mm, &T );
1662             continue;
1663         }
1664
1665         /*
1666          * add ei to current window
1667          */
1668         state = 2;
1669
1670         nbits++;
1671         wbits |= (ei << (wsize - nbits));
1672
1673         if( nbits == wsize )
1674         {
1675             /*
1676              * X = X^wsize R^-1 mod N
1677              */
1678             for( i = 0; i < wsize; i++ )
1679                 mpi_montmul( X, X, N, mm, &T );
1680
1681             /*
1682              * X = X * W[wbits] R^-1 mod N
1683              */
1684             mpi_montmul( X, &W[wbits], N, mm, &T );
1685
1686             state--;
1687             nbits = 0;
1688             wbits = 0;
1689         }
1690     }
1691
1692     /*
1693      * process the remaining bits
1694      */
1695     for( i = 0; i < nbits; i++ )
1696     {
1697         mpi_montmul( X, X, N, mm, &T );
1698
1699         wbits <<= 1;
1700
1701         if( (wbits & (one << wsize)) != 0 )
1702             mpi_montmul( X, &W[1], N, mm, &T );
1703     }
1704
1705     /*
1706      * X = A^E * R * R^-1 mod N = A^E mod N
1707      */
1708     mpi_montred( X, N, mm, &T );
1709
1710     if( neg )
1711     {
1712         X->s = -1;
1713         MPI_CHK( mpi_add_mpi( X, N, X ) );
1714     }
1715
1716 cleanup:
1717
1718     for( i = (one << (wsize - 1)); i < (one << wsize); i++ )
1719         mpi_free( &W[i] );
1720
1721     mpi_free( &W[1] ); mpi_free( &T ); mpi_free( &Apos );
1722
1723     if( _RR == NULL || _RR->p == NULL )
1724         mpi_free( &RR );
1725
1726     return( ret );
1727 }
1728
1729 /*
1730  * Greatest common divisor: G = gcd(A, B)  (HAC 14.54)
1731  */
1732 int mpi_gcd( mpi *G, const mpi *A, const mpi *B )
1733 {
1734     int ret;
1735     size_t lz, lzt;
1736     mpi TG, TA, TB;
1737
1738     mpi_init( &TG ); mpi_init( &TA ); mpi_init( &TB );
1739
1740     MPI_CHK( mpi_copy( &TA, A ) );
1741     MPI_CHK( mpi_copy( &TB, B ) );
1742
1743     lz = mpi_lsb( &TA );
1744     lzt = mpi_lsb( &TB );
1745
1746     if ( lzt < lz )
1747         lz = lzt;
1748
1749     MPI_CHK( mpi_shift_r( &TA, lz ) );
1750     MPI_CHK( mpi_shift_r( &TB, lz ) );
1751
1752     TA.s = TB.s = 1;
1753
1754     while( mpi_cmp_int( &TA, 0 ) != 0 )
1755     {
1756         MPI_CHK( mpi_shift_r( &TA, mpi_lsb( &TA ) ) );
1757         MPI_CHK( mpi_shift_r( &TB, mpi_lsb( &TB ) ) );
1758
1759         if( mpi_cmp_mpi( &TA, &TB ) >= 0 )
1760         {
1761             MPI_CHK( mpi_sub_abs( &TA, &TA, &TB ) );
1762             MPI_CHK( mpi_shift_r( &TA, 1 ) );
1763         }
1764         else
1765         {
1766             MPI_CHK( mpi_sub_abs( &TB, &TB, &TA ) );
1767             MPI_CHK( mpi_shift_r( &TB, 1 ) );
1768         }
1769     }
1770
1771     MPI_CHK( mpi_shift_l( &TB, lz ) );
1772     MPI_CHK( mpi_copy( G, &TB ) );
1773
1774 cleanup:
1775
1776     mpi_free( &TG ); mpi_free( &TA ); mpi_free( &TB );
1777
1778     return( ret );
1779 }
1780
1781 /*
1782  * Fill X with size bytes of random.
1783  *
1784  * Use a temporary bytes representation to make sure the result is the same
1785  * regardless of the platform endianness (useful when f_rng is actually
1786  * deterministic, eg for tests).
1787  */
1788 int mpi_fill_random( mpi *X, size_t size,
1789                      int (*f_rng)(void *, unsigned char *, size_t),
1790                      void *p_rng )
1791 {
1792     int ret;
1793     unsigned char buf[POLARSSL_MPI_MAX_SIZE];
1794
1795     if( size > POLARSSL_MPI_MAX_SIZE )
1796         return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1797
1798     MPI_CHK( f_rng( p_rng, buf, size ) );
1799     MPI_CHK( mpi_read_binary( X, buf, size ) );
1800
1801 cleanup:
1802     return( ret );
1803 }
1804
1805 /*
1806  * Modular inverse: X = A^-1 mod N  (HAC 14.61 / 14.64)
1807  */
1808 int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N )
1809 {
1810     int ret;
1811     mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1812
1813     if( mpi_cmp_int( N, 0 ) <= 0 )
1814         return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
1815
1816     mpi_init( &TA ); mpi_init( &TU ); mpi_init( &U1 ); mpi_init( &U2 );
1817     mpi_init( &G ); mpi_init( &TB ); mpi_init( &TV );
1818     mpi_init( &V1 ); mpi_init( &V2 );
1819
1820     MPI_CHK( mpi_gcd( &G, A, N ) );
1821
1822     if( mpi_cmp_int( &G, 1 ) != 0 )
1823     {
1824         ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
1825         goto cleanup;
1826     }
1827
1828     MPI_CHK( mpi_mod_mpi( &TA, A, N ) );
1829     MPI_CHK( mpi_copy( &TU, &TA ) );
1830     MPI_CHK( mpi_copy( &TB, N ) );
1831     MPI_CHK( mpi_copy( &TV, N ) );
1832
1833     MPI_CHK( mpi_lset( &U1, 1 ) );
1834     MPI_CHK( mpi_lset( &U2, 0 ) );
1835     MPI_CHK( mpi_lset( &V1, 0 ) );
1836     MPI_CHK( mpi_lset( &V2, 1 ) );
1837
1838     do
1839     {
1840         while( ( TU.p[0] & 1 ) == 0 )
1841         {
1842             MPI_CHK( mpi_shift_r( &TU, 1 ) );
1843
1844             if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
1845             {
1846                 MPI_CHK( mpi_add_mpi( &U1, &U1, &TB ) );
1847                 MPI_CHK( mpi_sub_mpi( &U2, &U2, &TA ) );
1848             }
1849
1850             MPI_CHK( mpi_shift_r( &U1, 1 ) );
1851             MPI_CHK( mpi_shift_r( &U2, 1 ) );
1852         }
1853
1854         while( ( TV.p[0] & 1 ) == 0 )
1855         {
1856             MPI_CHK( mpi_shift_r( &TV, 1 ) );
1857
1858             if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
1859             {
1860                 MPI_CHK( mpi_add_mpi( &V1, &V1, &TB ) );
1861                 MPI_CHK( mpi_sub_mpi( &V2, &V2, &TA ) );
1862             }
1863
1864             MPI_CHK( mpi_shift_r( &V1, 1 ) );
1865             MPI_CHK( mpi_shift_r( &V2, 1 ) );
1866         }
1867
1868         if( mpi_cmp_mpi( &TU, &TV ) >= 0 )
1869         {
1870             MPI_CHK( mpi_sub_mpi( &TU, &TU, &TV ) );
1871             MPI_CHK( mpi_sub_mpi( &U1, &U1, &V1 ) );
1872             MPI_CHK( mpi_sub_mpi( &U2, &U2, &V2 ) );
1873         }
1874         else
1875         {
1876             MPI_CHK( mpi_sub_mpi( &TV, &TV, &TU ) );
1877             MPI_CHK( mpi_sub_mpi( &V1, &V1, &U1 ) );
1878             MPI_CHK( mpi_sub_mpi( &V2, &V2, &U2 ) );
1879         }
1880     }
1881     while( mpi_cmp_int( &TU, 0 ) != 0 );
1882
1883     while( mpi_cmp_int( &V1, 0 ) < 0 )
1884         MPI_CHK( mpi_add_mpi( &V1, &V1, N ) );
1885
1886     while( mpi_cmp_mpi( &V1, N ) >= 0 )
1887         MPI_CHK( mpi_sub_mpi( &V1, &V1, N ) );
1888
1889     MPI_CHK( mpi_copy( X, &V1 ) );
1890
1891 cleanup:
1892
1893     mpi_free( &TA ); mpi_free( &TU ); mpi_free( &U1 ); mpi_free( &U2 );
1894     mpi_free( &G ); mpi_free( &TB ); mpi_free( &TV );
1895     mpi_free( &V1 ); mpi_free( &V2 );
1896
1897     return( ret );
1898 }
1899
1900 #if defined(POLARSSL_GENPRIME)
1901
1902 static const int small_prime[] =
1903 {
1904         3,    5,    7,   11,   13,   17,   19,   23,
1905        29,   31,   37,   41,   43,   47,   53,   59,
1906        61,   67,   71,   73,   79,   83,   89,   97,
1907       101,  103,  107,  109,  113,  127,  131,  137,
1908       139,  149,  151,  157,  163,  167,  173,  179,
1909       181,  191,  193,  197,  199,  211,  223,  227,
1910       229,  233,  239,  241,  251,  257,  263,  269,
1911       271,  277,  281,  283,  293,  307,  311,  313,
1912       317,  331,  337,  347,  349,  353,  359,  367,
1913       373,  379,  383,  389,  397,  401,  409,  419,
1914       421,  431,  433,  439,  443,  449,  457,  461,
1915       463,  467,  479,  487,  491,  499,  503,  509,
1916       521,  523,  541,  547,  557,  563,  569,  571,
1917       577,  587,  593,  599,  601,  607,  613,  617,
1918       619,  631,  641,  643,  647,  653,  659,  661,
1919       673,  677,  683,  691,  701,  709,  719,  727,
1920       733,  739,  743,  751,  757,  761,  769,  773,
1921       787,  797,  809,  811,  821,  823,  827,  829,
1922       839,  853,  857,  859,  863,  877,  881,  883,
1923       887,  907,  911,  919,  929,  937,  941,  947,
1924       953,  967,  971,  977,  983,  991,  997, -103
1925 };
1926
1927 /*
1928  * Small divisors test (X must be positive)
1929  *
1930  * Return values:
1931  * 0: no small factor (possible prime, more tests needed)
1932  * 1: certain prime
1933  * POLARSSL_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
1934  * other negative: error
1935  */
1936 static int mpi_check_small_factors( const mpi *X )
1937 {
1938     int ret = 0;
1939     size_t i;
1940     t_uint r;
1941
1942     if( ( X->p[0] & 1 ) == 0 )
1943         return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
1944
1945     for( i = 0; small_prime[i] > 0; i++ )
1946     {
1947         if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
1948             return( 1 );
1949
1950         MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) );
1951
1952         if( r == 0 )
1953             return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
1954     }
1955
1956 cleanup:
1957     return( ret );
1958 }
1959
1960 /*
1961  * Miller-Rabin pseudo-primality test  (HAC 4.24)
1962  */
1963 static int mpi_miller_rabin( const mpi *X,
1964                              int (*f_rng)(void *, unsigned char *, size_t),
1965                              void *p_rng )
1966 {
1967     int ret;
1968     size_t i, j, n, s;
1969     mpi W, R, T, A, RR;
1970
1971     mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A );
1972     mpi_init( &RR );
1973
1974     /*
1975      * W = |X| - 1
1976      * R = W >> lsb( W )
1977      */
1978     MPI_CHK( mpi_sub_int( &W, X, 1 ) );
1979     s = mpi_lsb( &W );
1980     MPI_CHK( mpi_copy( &R, &W ) );
1981     MPI_CHK( mpi_shift_r( &R, s ) );
1982
1983     i = mpi_msb( X );
1984     /*
1985      * HAC, table 4.4
1986      */
1987     n = ( ( i >= 1300 ) ?  2 : ( i >=  850 ) ?  3 :
1988           ( i >=  650 ) ?  4 : ( i >=  350 ) ?  8 :
1989           ( i >=  250 ) ? 12 : ( i >=  150 ) ? 18 : 27 );
1990
1991     for( i = 0; i < n; i++ )
1992     {
1993         /*
1994          * pick a random A, 1 < A < |X| - 1
1995          */
1996         MPI_CHK( mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
1997
1998         if( mpi_cmp_mpi( &A, &W ) >= 0 )
1999         {
2000             j = mpi_msb( &A ) - mpi_msb( &W );
2001             MPI_CHK( mpi_shift_r( &A, j + 1 ) );
2002         }
2003         A.p[0] |= 3;
2004
2005         /*
2006          * A = A^R mod |X|
2007          */
2008         MPI_CHK( mpi_exp_mod( &A, &A, &R, X, &RR ) );
2009
2010         if( mpi_cmp_mpi( &A, &W ) == 0 ||
2011             mpi_cmp_int( &A,  1 ) == 0 )
2012             continue;
2013
2014         j = 1;
2015         while( j < s && mpi_cmp_mpi( &A, &W ) != 0 )
2016         {
2017             /*
2018              * A = A * A mod |X|
2019              */
2020             MPI_CHK( mpi_mul_mpi( &T, &A, &A ) );
2021             MPI_CHK( mpi_mod_mpi( &A, &T, X  ) );
2022
2023             if( mpi_cmp_int( &A, 1 ) == 0 )
2024                 break;
2025
2026             j++;
2027         }
2028
2029         /*
2030          * not prime if A != |X| - 1 or A == 1
2031          */
2032         if( mpi_cmp_mpi( &A, &W ) != 0 ||
2033             mpi_cmp_int( &A,  1 ) == 0 )
2034         {
2035             ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
2036             break;
2037         }
2038     }
2039
2040 cleanup:
2041     mpi_free( &W ); mpi_free( &R ); mpi_free( &T ); mpi_free( &A );
2042     mpi_free( &RR );
2043
2044     return( ret );
2045 }
2046
2047 /*
2048  * Pseudo-primality test: small factors, then Miller-Rabin
2049  */
2050 int mpi_is_prime( mpi *X,
2051                   int (*f_rng)(void *, unsigned char *, size_t),
2052                   void *p_rng )
2053 {
2054     int ret;
2055     const mpi XX = { 1, X->n, X->p }; /* Abs(X) */
2056
2057     if( mpi_cmp_int( &XX, 0 ) == 0 ||
2058         mpi_cmp_int( &XX, 1 ) == 0 )
2059         return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
2060
2061     if( mpi_cmp_int( &XX, 2 ) == 0 )
2062         return( 0 );
2063
2064     if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2065     {
2066         if( ret == 1 )
2067             return( 0 );
2068
2069         return( ret );
2070     }
2071
2072     return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
2073 }
2074
2075 /*
2076  * Prime number generation
2077  */
2078 int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
2079                    int (*f_rng)(void *, unsigned char *, size_t),
2080                    void *p_rng )
2081 {
2082     int ret;
2083     size_t k, n;
2084     t_uint r;
2085     mpi Y;
2086
2087     if( nbits < 3 || nbits > POLARSSL_MPI_MAX_BITS )
2088         return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
2089
2090     mpi_init( &Y );
2091
2092     n = BITS_TO_LIMBS( nbits );
2093
2094     MPI_CHK( mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2095
2096     k = mpi_msb( X );
2097     if( k < nbits ) MPI_CHK( mpi_shift_l( X, nbits - k ) );
2098     if( k > nbits ) MPI_CHK( mpi_shift_r( X, k - nbits ) );
2099
2100     X->p[0] |= 3;
2101
2102     if( dh_flag == 0 )
2103     {
2104         while( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
2105         {
2106             if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
2107                 goto cleanup;
2108
2109             MPI_CHK( mpi_add_int( X, X, 2 ) );
2110         }
2111     }
2112     else
2113     {
2114         /*
2115          * An necessary condition for Y and X = 2Y + 1 to be prime
2116          * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2117          * Make sure it is satisfied, while keeping X = 3 mod 4
2118          */
2119         MPI_CHK( mpi_mod_int( &r, X, 3 ) );
2120         if( r == 0 )
2121             MPI_CHK( mpi_add_int( X, X, 8 ) );
2122         else if( r == 1 )
2123             MPI_CHK( mpi_add_int( X, X, 4 ) );
2124
2125         /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2126         MPI_CHK( mpi_copy( &Y, X ) );
2127         MPI_CHK( mpi_shift_r( &Y, 1 ) );
2128
2129         while( 1 )
2130         {
2131             /*
2132              * First, check small factors for X and Y
2133              * before doing Miller-Rabin on any of them
2134              */
2135             if( ( ret = mpi_check_small_factors(  X         ) ) == 0 &&
2136                 ( ret = mpi_check_small_factors( &Y         ) ) == 0 &&
2137                 ( ret = mpi_miller_rabin(  X, f_rng, p_rng  ) ) == 0 &&
2138                 ( ret = mpi_miller_rabin( &Y, f_rng, p_rng  ) ) == 0 )
2139             {
2140                 break;
2141             }
2142
2143             if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
2144                 goto cleanup;
2145
2146             /*
2147              * Next candidates. We want to preserve Y = (X-1) / 2 and
2148              * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2149              * so up Y by 6 and X by 12.
2150              */
2151             MPI_CHK( mpi_add_int(  X,  X, 12 ) );
2152             MPI_CHK( mpi_add_int( &Y, &Y, 6  ) );
2153         }
2154     }
2155
2156 cleanup:
2157
2158     mpi_free( &Y );
2159
2160     return( ret );
2161 }
2162
2163 #endif /* POLARSSL_GENPRIME */
2164
2165 #if defined(POLARSSL_SELF_TEST)
2166
2167 #define GCD_PAIR_COUNT  3
2168
2169 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2170 {
2171     { 693, 609, 21 },
2172     { 1764, 868, 28 },
2173     { 768454923, 542167814, 1 }
2174 };
2175
2176 /*
2177  * Checkup routine
2178  */
2179 int mpi_self_test( int verbose )
2180 {
2181     int ret, i;
2182     mpi A, E, N, X, Y, U, V;
2183
2184     mpi_init( &A ); mpi_init( &E ); mpi_init( &N ); mpi_init( &X );
2185     mpi_init( &Y ); mpi_init( &U ); mpi_init( &V );
2186
2187     MPI_CHK( mpi_read_string( &A, 16,
2188         "EFE021C2645FD1DC586E69184AF4A31E" \
2189         "D5F53E93B5F123FA41680867BA110131" \
2190         "944FE7952E2517337780CB0DB80E61AA" \
2191         "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2192
2193     MPI_CHK( mpi_read_string( &E, 16,
2194         "B2E7EFD37075B9F03FF989C7C5051C20" \
2195         "34D2A323810251127E7BF8625A4F49A5" \
2196         "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2197         "5B5C25763222FEFCCFC38B832366C29E" ) );
2198
2199     MPI_CHK( mpi_read_string( &N, 16,
2200         "0066A198186C18C10B2F5ED9B522752A" \
2201         "9830B69916E535C8F047518A889A43A5" \
2202         "94B6BED27A168D31D4A52F88925AA8F5" ) );
2203
2204     MPI_CHK( mpi_mul_mpi( &X, &A, &N ) );
2205
2206     MPI_CHK( mpi_read_string( &U, 16,
2207         "602AB7ECA597A3D6B56FF9829A5E8B85" \
2208         "9E857EA95A03512E2BAE7391688D264A" \
2209         "A5663B0341DB9CCFD2C4C5F421FEC814" \
2210         "8001B72E848A38CAE1C65F78E56ABDEF" \
2211         "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2212         "ECF677152EF804370C1A305CAF3B5BF1" \
2213         "30879B56C61DE584A0F53A2447A51E" ) );
2214
2215     if( verbose != 0 )
2216         polarssl_printf( "  MPI test #1 (mul_mpi): " );
2217
2218     if( mpi_cmp_mpi( &X, &U ) != 0 )
2219     {
2220         if( verbose != 0 )
2221             polarssl_printf( "failed\n" );
2222
2223         ret = 1;
2224         goto cleanup;
2225     }
2226
2227     if( verbose != 0 )
2228         polarssl_printf( "passed\n" );
2229
2230     MPI_CHK( mpi_div_mpi( &X, &Y, &A, &N ) );
2231
2232     MPI_CHK( mpi_read_string( &U, 16,
2233         "256567336059E52CAE22925474705F39A94" ) );
2234
2235     MPI_CHK( mpi_read_string( &V, 16,
2236         "6613F26162223DF488E9CD48CC132C7A" \
2237         "0AC93C701B001B092E4E5B9F73BCD27B" \
2238         "9EE50D0657C77F374E903CDFA4C642" ) );
2239
2240     if( verbose != 0 )
2241         polarssl_printf( "  MPI test #2 (div_mpi): " );
2242
2243     if( mpi_cmp_mpi( &X, &U ) != 0 ||
2244         mpi_cmp_mpi( &Y, &V ) != 0 )
2245     {
2246         if( verbose != 0 )
2247             polarssl_printf( "failed\n" );
2248
2249         ret = 1;
2250         goto cleanup;
2251     }
2252
2253     if( verbose != 0 )
2254         polarssl_printf( "passed\n" );
2255
2256     MPI_CHK( mpi_exp_mod( &X, &A, &E, &N, NULL ) );
2257
2258     MPI_CHK( mpi_read_string( &U, 16,
2259         "36E139AEA55215609D2816998ED020BB" \
2260         "BD96C37890F65171D948E9BC7CBAA4D9" \
2261         "325D24D6A3C12710F10A09FA08AB87" ) );
2262
2263     if( verbose != 0 )
2264         polarssl_printf( "  MPI test #3 (exp_mod): " );
2265
2266     if( mpi_cmp_mpi( &X, &U ) != 0 )
2267     {
2268         if( verbose != 0 )
2269             polarssl_printf( "failed\n" );
2270
2271         ret = 1;
2272         goto cleanup;
2273     }
2274
2275     if( verbose != 0 )
2276         polarssl_printf( "passed\n" );
2277
2278     MPI_CHK( mpi_inv_mod( &X, &A, &N ) );
2279
2280     MPI_CHK( mpi_read_string( &U, 16,
2281         "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2282         "C3DBA76456363A10869622EAC2DD84EC" \
2283         "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2284
2285     if( verbose != 0 )
2286         polarssl_printf( "  MPI test #4 (inv_mod): " );
2287
2288     if( mpi_cmp_mpi( &X, &U ) != 0 )
2289     {
2290         if( verbose != 0 )
2291             polarssl_printf( "failed\n" );
2292
2293         ret = 1;
2294         goto cleanup;
2295     }
2296
2297     if( verbose != 0 )
2298         polarssl_printf( "passed\n" );
2299
2300     if( verbose != 0 )
2301         polarssl_printf( "  MPI test #5 (simple gcd): " );
2302
2303     for ( i = 0; i < GCD_PAIR_COUNT; i++)
2304     {
2305         MPI_CHK( mpi_lset( &X, gcd_pairs[i][0] ) );
2306         MPI_CHK( mpi_lset( &Y, gcd_pairs[i][1] ) );
2307
2308         MPI_CHK( mpi_gcd( &A, &X, &Y ) );
2309
2310         if( mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
2311         {
2312             if( verbose != 0 )
2313                 polarssl_printf( "failed at %d\n", i );
2314
2315             ret = 1;
2316             goto cleanup;
2317         }
2318     }
2319
2320     if( verbose != 0 )
2321         polarssl_printf( "passed\n" );
2322
2323 cleanup:
2324
2325     if( ret != 0 && verbose != 0 )
2326         polarssl_printf( "Unexpected error, return code = %08X\n", ret );
2327
2328     mpi_free( &A ); mpi_free( &E ); mpi_free( &N ); mpi_free( &X );
2329     mpi_free( &Y ); mpi_free( &U ); mpi_free( &V );
2330
2331     if( verbose != 0 )
2332         polarssl_printf( "\n" );
2333
2334     return( ret );
2335 }
2336
2337 #endif /* POLARSSL_SELF_TEST */
2338
2339 #endif /* POLARSSL_BIGNUM_C */