00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #include "polarssl/config.h"
00034
00035 #if defined(POLARSSL_BIGNUM_C)
00036
00037 #include "polarssl/bignum.h"
00038 #include "polarssl/bn_mul.h"
00039
00040 #if defined(POLARSSL_MEMORY_C)
00041 #include "polarssl/memory.h"
00042 #else
00043 #define polarssl_malloc malloc
00044 #define polarssl_free free
00045 #endif
00046
00047 #include <stdlib.h>
00048
00049 #define ciL (sizeof(t_uint))
00050 #define biL (ciL << 3)
00051 #define biH (ciL << 2)
00052
00053
00054
00055
00056 #define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL)
00057 #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
00058
00059
00060
00061
00062 void mpi_init( mpi *X )
00063 {
00064 if( X == NULL )
00065 return;
00066
00067 X->s = 1;
00068 X->n = 0;
00069 X->p = NULL;
00070 }
00071
00072
00073
00074
00075 void mpi_free( mpi *X )
00076 {
00077 if( X == NULL )
00078 return;
00079
00080 if( X->p != NULL )
00081 {
00082 memset( X->p, 0, X->n * ciL );
00083 polarssl_free( X->p );
00084 }
00085
00086 X->s = 1;
00087 X->n = 0;
00088 X->p = NULL;
00089 }
00090
00091
00092
00093
00094 int mpi_grow( mpi *X, size_t nblimbs )
00095 {
00096 t_uint *p;
00097
00098 if( nblimbs > POLARSSL_MPI_MAX_LIMBS )
00099 return( POLARSSL_ERR_MPI_MALLOC_FAILED );
00100
00101 if( X->n < nblimbs )
00102 {
00103 if( ( p = (t_uint *) polarssl_malloc( nblimbs * ciL ) ) == NULL )
00104 return( POLARSSL_ERR_MPI_MALLOC_FAILED );
00105
00106 memset( p, 0, nblimbs * ciL );
00107
00108 if( X->p != NULL )
00109 {
00110 memcpy( p, X->p, X->n * ciL );
00111 memset( X->p, 0, X->n * ciL );
00112 polarssl_free( X->p );
00113 }
00114
00115 X->n = nblimbs;
00116 X->p = p;
00117 }
00118
00119 return( 0 );
00120 }
00121
00122
00123
00124
00125 int mpi_copy( mpi *X, const mpi *Y )
00126 {
00127 int ret;
00128 size_t i;
00129
00130 if( X == Y )
00131 return( 0 );
00132
00133 if( Y->p == NULL )
00134 {
00135 mpi_free( X );
00136 return( 0 );
00137 }
00138
00139 for( i = Y->n - 1; i > 0; i-- )
00140 if( Y->p[i] != 0 )
00141 break;
00142 i++;
00143
00144 X->s = Y->s;
00145
00146 MPI_CHK( mpi_grow( X, i ) );
00147
00148 memset( X->p, 0, X->n * ciL );
00149 memcpy( X->p, Y->p, i * ciL );
00150
00151 cleanup:
00152
00153 return( ret );
00154 }
00155
00156
00157
00158
00159 void mpi_swap( mpi *X, mpi *Y )
00160 {
00161 mpi T;
00162
00163 memcpy( &T, X, sizeof( mpi ) );
00164 memcpy( X, Y, sizeof( mpi ) );
00165 memcpy( Y, &T, sizeof( mpi ) );
00166 }
00167
00168
00169
00170
00171 int mpi_lset( mpi *X, t_sint z )
00172 {
00173 int ret;
00174
00175 MPI_CHK( mpi_grow( X, 1 ) );
00176 memset( X->p, 0, X->n * ciL );
00177
00178 X->p[0] = ( z < 0 ) ? -z : z;
00179 X->s = ( z < 0 ) ? -1 : 1;
00180
00181 cleanup:
00182
00183 return( ret );
00184 }
00185
00186
00187
00188
00189 int mpi_get_bit( const mpi *X, size_t pos )
00190 {
00191 if( X->n * biL <= pos )
00192 return( 0 );
00193
00194 return ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01;
00195 }
00196
00197
00198
00199
00200 int mpi_set_bit( mpi *X, size_t pos, unsigned char val )
00201 {
00202 int ret = 0;
00203 size_t off = pos / biL;
00204 size_t idx = pos % biL;
00205
00206 if( val != 0 && val != 1 )
00207 return POLARSSL_ERR_MPI_BAD_INPUT_DATA;
00208
00209 if( X->n * biL <= pos )
00210 {
00211 if( val == 0 )
00212 return ( 0 );
00213
00214 MPI_CHK( mpi_grow( X, off + 1 ) );
00215 }
00216
00217 X->p[off] = ( X->p[off] & ~( 0x01 << idx ) ) | ( val << idx );
00218
00219 cleanup:
00220
00221 return( ret );
00222 }
00223
00224
00225
00226
00227 size_t mpi_lsb( const mpi *X )
00228 {
00229 size_t i, j, count = 0;
00230
00231 for( i = 0; i < X->n; i++ )
00232 for( j = 0; j < biL; j++, count++ )
00233 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
00234 return( count );
00235
00236 return( 0 );
00237 }
00238
00239
00240
00241
00242 size_t mpi_msb( const mpi *X )
00243 {
00244 size_t i, j;
00245
00246 for( i = X->n - 1; i > 0; i-- )
00247 if( X->p[i] != 0 )
00248 break;
00249
00250 for( j = biL; j > 0; j-- )
00251 if( ( ( X->p[i] >> ( j - 1 ) ) & 1 ) != 0 )
00252 break;
00253
00254 return( ( i * biL ) + j );
00255 }
00256
00257
00258
00259
00260 size_t mpi_size( const mpi *X )
00261 {
00262 return( ( mpi_msb( X ) + 7 ) >> 3 );
00263 }
00264
00265
00266
00267
00268 static int mpi_get_digit( t_uint *d, int radix, char c )
00269 {
00270 *d = 255;
00271
00272 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
00273 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
00274 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
00275
00276 if( *d >= (t_uint) radix )
00277 return( POLARSSL_ERR_MPI_INVALID_CHARACTER );
00278
00279 return( 0 );
00280 }
00281
00282
00283
00284
00285 int mpi_read_string( mpi *X, int radix, const char *s )
00286 {
00287 int ret;
00288 size_t i, j, slen, n;
00289 t_uint d;
00290 mpi T;
00291
00292 if( radix < 2 || radix > 16 )
00293 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
00294
00295 mpi_init( &T );
00296
00297 slen = strlen( s );
00298
00299 if( radix == 16 )
00300 {
00301 n = BITS_TO_LIMBS( slen << 2 );
00302
00303 MPI_CHK( mpi_grow( X, n ) );
00304 MPI_CHK( mpi_lset( X, 0 ) );
00305
00306 for( i = slen, j = 0; i > 0; i--, j++ )
00307 {
00308 if( i == 1 && s[i - 1] == '-' )
00309 {
00310 X->s = -1;
00311 break;
00312 }
00313
00314 MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
00315 X->p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 );
00316 }
00317 }
00318 else
00319 {
00320 MPI_CHK( mpi_lset( X, 0 ) );
00321
00322 for( i = 0; i < slen; i++ )
00323 {
00324 if( i == 0 && s[i] == '-' )
00325 {
00326 X->s = -1;
00327 continue;
00328 }
00329
00330 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
00331 MPI_CHK( mpi_mul_int( &T, X, radix ) );
00332
00333 if( X->s == 1 )
00334 {
00335 MPI_CHK( mpi_add_int( X, &T, d ) );
00336 }
00337 else
00338 {
00339 MPI_CHK( mpi_sub_int( X, &T, d ) );
00340 }
00341 }
00342 }
00343
00344 cleanup:
00345
00346 mpi_free( &T );
00347
00348 return( ret );
00349 }
00350
00351
00352
00353
00354 static int mpi_write_hlp( mpi *X, int radix, char **p )
00355 {
00356 int ret;
00357 t_uint r;
00358
00359 if( radix < 2 || radix > 16 )
00360 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
00361
00362 MPI_CHK( mpi_mod_int( &r, X, radix ) );
00363 MPI_CHK( mpi_div_int( X, NULL, X, radix ) );
00364
00365 if( mpi_cmp_int( X, 0 ) != 0 )
00366 MPI_CHK( mpi_write_hlp( X, radix, p ) );
00367
00368 if( r < 10 )
00369 *(*p)++ = (char)( r + 0x30 );
00370 else
00371 *(*p)++ = (char)( r + 0x37 );
00372
00373 cleanup:
00374
00375 return( ret );
00376 }
00377
00378
00379
00380
00381 int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen )
00382 {
00383 int ret = 0;
00384 size_t n;
00385 char *p;
00386 mpi T;
00387
00388 if( radix < 2 || radix > 16 )
00389 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
00390
00391 n = mpi_msb( X );
00392 if( radix >= 4 ) n >>= 1;
00393 if( radix >= 16 ) n >>= 1;
00394 n += 3;
00395
00396 if( *slen < n )
00397 {
00398 *slen = n;
00399 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
00400 }
00401
00402 p = s;
00403 mpi_init( &T );
00404
00405 if( X->s == -1 )
00406 *p++ = '-';
00407
00408 if( radix == 16 )
00409 {
00410 int c;
00411 size_t i, j, k;
00412
00413 for( i = X->n, k = 0; i > 0; i-- )
00414 {
00415 for( j = ciL; j > 0; j-- )
00416 {
00417 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
00418
00419 if( c == 0 && k == 0 && ( i + j + 3 ) != 0 )
00420 continue;
00421
00422 *(p++) = "0123456789ABCDEF" [c / 16];
00423 *(p++) = "0123456789ABCDEF" [c % 16];
00424 k = 1;
00425 }
00426 }
00427 }
00428 else
00429 {
00430 MPI_CHK( mpi_copy( &T, X ) );
00431
00432 if( T.s == -1 )
00433 T.s = 1;
00434
00435 MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
00436 }
00437
00438 *p++ = '\0';
00439 *slen = p - s;
00440
00441 cleanup:
00442
00443 mpi_free( &T );
00444
00445 return( ret );
00446 }
00447
00448 #if defined(POLARSSL_FS_IO)
00449
00450
00451
00452 int mpi_read_file( mpi *X, int radix, FILE *fin )
00453 {
00454 t_uint d;
00455 size_t slen;
00456 char *p;
00457
00458
00459
00460
00461 char s[ POLARSSL_MPI_RW_BUFFER_SIZE ];
00462
00463 memset( s, 0, sizeof( s ) );
00464 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
00465 return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
00466
00467 slen = strlen( s );
00468 if( slen == sizeof( s ) - 2 )
00469 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
00470
00471 if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
00472 if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
00473
00474 p = s + slen;
00475 while( --p >= s )
00476 if( mpi_get_digit( &d, radix, *p ) != 0 )
00477 break;
00478
00479 return( mpi_read_string( X, radix, p + 1 ) );
00480 }
00481
00482
00483
00484
00485 int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout )
00486 {
00487 int ret;
00488 size_t n, slen, plen;
00489
00490
00491
00492
00493 char s[ POLARSSL_MPI_RW_BUFFER_SIZE ];
00494
00495 n = sizeof( s );
00496 memset( s, 0, n );
00497 n -= 2;
00498
00499 MPI_CHK( mpi_write_string( X, radix, s, (size_t *) &n ) );
00500
00501 if( p == NULL ) p = "";
00502
00503 plen = strlen( p );
00504 slen = strlen( s );
00505 s[slen++] = '\r';
00506 s[slen++] = '\n';
00507
00508 if( fout != NULL )
00509 {
00510 if( fwrite( p, 1, plen, fout ) != plen ||
00511 fwrite( s, 1, slen, fout ) != slen )
00512 return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
00513 }
00514 else
00515 printf( "%s%s", p, s );
00516
00517 cleanup:
00518
00519 return( ret );
00520 }
00521 #endif
00522
00523
00524
00525
00526 int mpi_read_binary( mpi *X, const unsigned char *buf, size_t buflen )
00527 {
00528 int ret;
00529 size_t i, j, n;
00530
00531 for( n = 0; n < buflen; n++ )
00532 if( buf[n] != 0 )
00533 break;
00534
00535 MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );
00536 MPI_CHK( mpi_lset( X, 0 ) );
00537
00538 for( i = buflen, j = 0; i > n; i--, j++ )
00539 X->p[j / ciL] |= ((t_uint) buf[i - 1]) << ((j % ciL) << 3);
00540
00541 cleanup:
00542
00543 return( ret );
00544 }
00545
00546
00547
00548
00549 int mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen )
00550 {
00551 size_t i, j, n;
00552
00553 n = mpi_size( X );
00554
00555 if( buflen < n )
00556 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
00557
00558 memset( buf, 0, buflen );
00559
00560 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
00561 buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
00562
00563 return( 0 );
00564 }
00565
00566
00567
00568
00569 int mpi_shift_l( mpi *X, size_t count )
00570 {
00571 int ret;
00572 size_t i, v0, t1;
00573 t_uint r0 = 0, r1;
00574
00575 v0 = count / (biL );
00576 t1 = count & (biL - 1);
00577
00578 i = mpi_msb( X ) + count;
00579
00580 if( X->n * biL < i )
00581 MPI_CHK( mpi_grow( X, BITS_TO_LIMBS( i ) ) );
00582
00583 ret = 0;
00584
00585
00586
00587
00588 if( v0 > 0 )
00589 {
00590 for( i = X->n; i > v0; i-- )
00591 X->p[i - 1] = X->p[i - v0 - 1];
00592
00593 for( ; i > 0; i-- )
00594 X->p[i - 1] = 0;
00595 }
00596
00597
00598
00599
00600 if( t1 > 0 )
00601 {
00602 for( i = v0; i < X->n; i++ )
00603 {
00604 r1 = X->p[i] >> (biL - t1);
00605 X->p[i] <<= t1;
00606 X->p[i] |= r0;
00607 r0 = r1;
00608 }
00609 }
00610
00611 cleanup:
00612
00613 return( ret );
00614 }
00615
00616
00617
00618
00619 int mpi_shift_r( mpi *X, size_t count )
00620 {
00621 size_t i, v0, v1;
00622 t_uint r0 = 0, r1;
00623
00624 v0 = count / biL;
00625 v1 = count & (biL - 1);
00626
00627 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
00628 return mpi_lset( X, 0 );
00629
00630
00631
00632
00633 if( v0 > 0 )
00634 {
00635 for( i = 0; i < X->n - v0; i++ )
00636 X->p[i] = X->p[i + v0];
00637
00638 for( ; i < X->n; i++ )
00639 X->p[i] = 0;
00640 }
00641
00642
00643
00644
00645 if( v1 > 0 )
00646 {
00647 for( i = X->n; i > 0; i-- )
00648 {
00649 r1 = X->p[i - 1] << (biL - v1);
00650 X->p[i - 1] >>= v1;
00651 X->p[i - 1] |= r0;
00652 r0 = r1;
00653 }
00654 }
00655
00656 return( 0 );
00657 }
00658
00659
00660
00661
00662 int mpi_cmp_abs( const mpi *X, const mpi *Y )
00663 {
00664 size_t i, j;
00665
00666 for( i = X->n; i > 0; i-- )
00667 if( X->p[i - 1] != 0 )
00668 break;
00669
00670 for( j = Y->n; j > 0; j-- )
00671 if( Y->p[j - 1] != 0 )
00672 break;
00673
00674 if( i == 0 && j == 0 )
00675 return( 0 );
00676
00677 if( i > j ) return( 1 );
00678 if( j > i ) return( -1 );
00679
00680 for( ; i > 0; i-- )
00681 {
00682 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
00683 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
00684 }
00685
00686 return( 0 );
00687 }
00688
00689
00690
00691
00692 int mpi_cmp_mpi( const mpi *X, const mpi *Y )
00693 {
00694 size_t i, j;
00695
00696 for( i = X->n; i > 0; i-- )
00697 if( X->p[i - 1] != 0 )
00698 break;
00699
00700 for( j = Y->n; j > 0; j-- )
00701 if( Y->p[j - 1] != 0 )
00702 break;
00703
00704 if( i == 0 && j == 0 )
00705 return( 0 );
00706
00707 if( i > j ) return( X->s );
00708 if( j > i ) return( -Y->s );
00709
00710 if( X->s > 0 && Y->s < 0 ) return( 1 );
00711 if( Y->s > 0 && X->s < 0 ) return( -1 );
00712
00713 for( ; i > 0; i-- )
00714 {
00715 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
00716 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
00717 }
00718
00719 return( 0 );
00720 }
00721
00722
00723
00724
00725 int mpi_cmp_int( const mpi *X, t_sint z )
00726 {
00727 mpi Y;
00728 t_uint p[1];
00729
00730 *p = ( z < 0 ) ? -z : z;
00731 Y.s = ( z < 0 ) ? -1 : 1;
00732 Y.n = 1;
00733 Y.p = p;
00734
00735 return( mpi_cmp_mpi( X, &Y ) );
00736 }
00737
00738
00739
00740
00741 int mpi_add_abs( mpi *X, const mpi *A, const mpi *B )
00742 {
00743 int ret;
00744 size_t i, j;
00745 t_uint *o, *p, c;
00746
00747 if( X == B )
00748 {
00749 const mpi *T = A; A = X; B = T;
00750 }
00751
00752 if( X != A )
00753 MPI_CHK( mpi_copy( X, A ) );
00754
00755
00756
00757
00758 X->s = 1;
00759
00760 for( j = B->n; j > 0; j-- )
00761 if( B->p[j - 1] != 0 )
00762 break;
00763
00764 MPI_CHK( mpi_grow( X, j ) );
00765
00766 o = B->p; p = X->p; c = 0;
00767
00768 for( i = 0; i < j; i++, o++, p++ )
00769 {
00770 *p += c; c = ( *p < c );
00771 *p += *o; c += ( *p < *o );
00772 }
00773
00774 while( c != 0 )
00775 {
00776 if( i >= X->n )
00777 {
00778 MPI_CHK( mpi_grow( X, i + 1 ) );
00779 p = X->p + i;
00780 }
00781
00782 *p += c; c = ( *p < c ); i++; p++;
00783 }
00784
00785 cleanup:
00786
00787 return( ret );
00788 }
00789
00790
00791
00792
00793 static void mpi_sub_hlp( size_t n, t_uint *s, t_uint *d )
00794 {
00795 size_t i;
00796 t_uint c, z;
00797
00798 for( i = c = 0; i < n; i++, s++, d++ )
00799 {
00800 z = ( *d < c ); *d -= c;
00801 c = ( *d < *s ) + z; *d -= *s;
00802 }
00803
00804 while( c != 0 )
00805 {
00806 z = ( *d < c ); *d -= c;
00807 c = z; i++; d++;
00808 }
00809 }
00810
00811
00812
00813
00814 int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B )
00815 {
00816 mpi TB;
00817 int ret;
00818 size_t n;
00819
00820 if( mpi_cmp_abs( A, B ) < 0 )
00821 return( POLARSSL_ERR_MPI_NEGATIVE_VALUE );
00822
00823 mpi_init( &TB );
00824
00825 if( X == B )
00826 {
00827 MPI_CHK( mpi_copy( &TB, B ) );
00828 B = &TB;
00829 }
00830
00831 if( X != A )
00832 MPI_CHK( mpi_copy( X, A ) );
00833
00834
00835
00836
00837 X->s = 1;
00838
00839 ret = 0;
00840
00841 for( n = B->n; n > 0; n-- )
00842 if( B->p[n - 1] != 0 )
00843 break;
00844
00845 mpi_sub_hlp( n, B->p, X->p );
00846
00847 cleanup:
00848
00849 mpi_free( &TB );
00850
00851 return( ret );
00852 }
00853
00854
00855
00856
00857 int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B )
00858 {
00859 int ret, s = A->s;
00860
00861 if( A->s * B->s < 0 )
00862 {
00863 if( mpi_cmp_abs( A, B ) >= 0 )
00864 {
00865 MPI_CHK( mpi_sub_abs( X, A, B ) );
00866 X->s = s;
00867 }
00868 else
00869 {
00870 MPI_CHK( mpi_sub_abs( X, B, A ) );
00871 X->s = -s;
00872 }
00873 }
00874 else
00875 {
00876 MPI_CHK( mpi_add_abs( X, A, B ) );
00877 X->s = s;
00878 }
00879
00880 cleanup:
00881
00882 return( ret );
00883 }
00884
00885
00886
00887
00888 int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B )
00889 {
00890 int ret, s = A->s;
00891
00892 if( A->s * B->s > 0 )
00893 {
00894 if( mpi_cmp_abs( A, B ) >= 0 )
00895 {
00896 MPI_CHK( mpi_sub_abs( X, A, B ) );
00897 X->s = s;
00898 }
00899 else
00900 {
00901 MPI_CHK( mpi_sub_abs( X, B, A ) );
00902 X->s = -s;
00903 }
00904 }
00905 else
00906 {
00907 MPI_CHK( mpi_add_abs( X, A, B ) );
00908 X->s = s;
00909 }
00910
00911 cleanup:
00912
00913 return( ret );
00914 }
00915
00916
00917
00918
00919 int mpi_add_int( mpi *X, const mpi *A, t_sint b )
00920 {
00921 mpi _B;
00922 t_uint p[1];
00923
00924 p[0] = ( b < 0 ) ? -b : b;
00925 _B.s = ( b < 0 ) ? -1 : 1;
00926 _B.n = 1;
00927 _B.p = p;
00928
00929 return( mpi_add_mpi( X, A, &_B ) );
00930 }
00931
00932
00933
00934
00935 int mpi_sub_int( mpi *X, const mpi *A, t_sint b )
00936 {
00937 mpi _B;
00938 t_uint p[1];
00939
00940 p[0] = ( b < 0 ) ? -b : b;
00941 _B.s = ( b < 0 ) ? -1 : 1;
00942 _B.n = 1;
00943 _B.p = p;
00944
00945 return( mpi_sub_mpi( X, A, &_B ) );
00946 }
00947
00948
00949
00950
00951 static
00952 #if defined(__APPLE__) && defined(__arm__)
00953
00954
00955
00956
00957 __attribute__ ((noinline))
00958 #endif
00959 void mpi_mul_hlp( size_t i, t_uint *s, t_uint *d, t_uint b )
00960 {
00961 t_uint c = 0, t = 0;
00962
00963 #if defined(MULADDC_HUIT)
00964 for( ; i >= 8; i -= 8 )
00965 {
00966 MULADDC_INIT
00967 MULADDC_HUIT
00968 MULADDC_STOP
00969 }
00970
00971 for( ; i > 0; i-- )
00972 {
00973 MULADDC_INIT
00974 MULADDC_CORE
00975 MULADDC_STOP
00976 }
00977 #else
00978 for( ; i >= 16; i -= 16 )
00979 {
00980 MULADDC_INIT
00981 MULADDC_CORE MULADDC_CORE
00982 MULADDC_CORE MULADDC_CORE
00983 MULADDC_CORE MULADDC_CORE
00984 MULADDC_CORE MULADDC_CORE
00985
00986 MULADDC_CORE MULADDC_CORE
00987 MULADDC_CORE MULADDC_CORE
00988 MULADDC_CORE MULADDC_CORE
00989 MULADDC_CORE MULADDC_CORE
00990 MULADDC_STOP
00991 }
00992
00993 for( ; i >= 8; i -= 8 )
00994 {
00995 MULADDC_INIT
00996 MULADDC_CORE MULADDC_CORE
00997 MULADDC_CORE MULADDC_CORE
00998
00999 MULADDC_CORE MULADDC_CORE
01000 MULADDC_CORE MULADDC_CORE
01001 MULADDC_STOP
01002 }
01003
01004 for( ; i > 0; i-- )
01005 {
01006 MULADDC_INIT
01007 MULADDC_CORE
01008 MULADDC_STOP
01009 }
01010 #endif
01011
01012 t++;
01013
01014 do {
01015 *d += c; c = ( *d < c ); d++;
01016 }
01017 while( c != 0 );
01018 }
01019
01020
01021
01022
01023 int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B )
01024 {
01025 int ret;
01026 size_t i, j;
01027 mpi TA, TB;
01028
01029 mpi_init( &TA ); mpi_init( &TB );
01030
01031 if( X == A ) { MPI_CHK( mpi_copy( &TA, A ) ); A = &TA; }
01032 if( X == B ) { MPI_CHK( mpi_copy( &TB, B ) ); B = &TB; }
01033
01034 for( i = A->n; i > 0; i-- )
01035 if( A->p[i - 1] != 0 )
01036 break;
01037
01038 for( j = B->n; j > 0; j-- )
01039 if( B->p[j - 1] != 0 )
01040 break;
01041
01042 MPI_CHK( mpi_grow( X, i + j ) );
01043 MPI_CHK( mpi_lset( X, 0 ) );
01044
01045 for( i++; j > 0; j-- )
01046 mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] );
01047
01048 X->s = A->s * B->s;
01049
01050 cleanup:
01051
01052 mpi_free( &TB ); mpi_free( &TA );
01053
01054 return( ret );
01055 }
01056
01057
01058
01059
01060 int mpi_mul_int( mpi *X, const mpi *A, t_sint b )
01061 {
01062 mpi _B;
01063 t_uint p[1];
01064
01065 _B.s = 1;
01066 _B.n = 1;
01067 _B.p = p;
01068 p[0] = b;
01069
01070 return( mpi_mul_mpi( X, A, &_B ) );
01071 }
01072
01073
01074
01075
01076 int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B )
01077 {
01078 int ret;
01079 size_t i, n, t, k;
01080 mpi X, Y, Z, T1, T2;
01081
01082 if( mpi_cmp_int( B, 0 ) == 0 )
01083 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
01084
01085 mpi_init( &X ); mpi_init( &Y ); mpi_init( &Z );
01086 mpi_init( &T1 ); mpi_init( &T2 );
01087
01088 if( mpi_cmp_abs( A, B ) < 0 )
01089 {
01090 if( Q != NULL ) MPI_CHK( mpi_lset( Q, 0 ) );
01091 if( R != NULL ) MPI_CHK( mpi_copy( R, A ) );
01092 return( 0 );
01093 }
01094
01095 MPI_CHK( mpi_copy( &X, A ) );
01096 MPI_CHK( mpi_copy( &Y, B ) );
01097 X.s = Y.s = 1;
01098
01099 MPI_CHK( mpi_grow( &Z, A->n + 2 ) );
01100 MPI_CHK( mpi_lset( &Z, 0 ) );
01101 MPI_CHK( mpi_grow( &T1, 2 ) );
01102 MPI_CHK( mpi_grow( &T2, 3 ) );
01103
01104 k = mpi_msb( &Y ) % biL;
01105 if( k < biL - 1 )
01106 {
01107 k = biL - 1 - k;
01108 MPI_CHK( mpi_shift_l( &X, k ) );
01109 MPI_CHK( mpi_shift_l( &Y, k ) );
01110 }
01111 else k = 0;
01112
01113 n = X.n - 1;
01114 t = Y.n - 1;
01115 MPI_CHK( mpi_shift_l( &Y, biL * (n - t) ) );
01116
01117 while( mpi_cmp_mpi( &X, &Y ) >= 0 )
01118 {
01119 Z.p[n - t]++;
01120 mpi_sub_mpi( &X, &X, &Y );
01121 }
01122 mpi_shift_r( &Y, biL * (n - t) );
01123
01124 for( i = n; i > t ; i-- )
01125 {
01126 if( X.p[i] >= Y.p[t] )
01127 Z.p[i - t - 1] = ~0;
01128 else
01129 {
01130 #if defined(POLARSSL_HAVE_UDBL)
01131 t_udbl r;
01132
01133 r = (t_udbl) X.p[i] << biL;
01134 r |= (t_udbl) X.p[i - 1];
01135 r /= Y.p[t];
01136 if( r > ((t_udbl) 1 << biL) - 1)
01137 r = ((t_udbl) 1 << biL) - 1;
01138
01139 Z.p[i - t - 1] = (t_uint) r;
01140 #else
01141
01142
01143
01144 t_uint q0, q1, r0, r1;
01145 t_uint d0, d1, d, m;
01146
01147 d = Y.p[t];
01148 d0 = ( d << biH ) >> biH;
01149 d1 = ( d >> biH );
01150
01151 q1 = X.p[i] / d1;
01152 r1 = X.p[i] - d1 * q1;
01153 r1 <<= biH;
01154 r1 |= ( X.p[i - 1] >> biH );
01155
01156 m = q1 * d0;
01157 if( r1 < m )
01158 {
01159 q1--, r1 += d;
01160 while( r1 >= d && r1 < m )
01161 q1--, r1 += d;
01162 }
01163 r1 -= m;
01164
01165 q0 = r1 / d1;
01166 r0 = r1 - d1 * q0;
01167 r0 <<= biH;
01168 r0 |= ( X.p[i - 1] << biH ) >> biH;
01169
01170 m = q0 * d0;
01171 if( r0 < m )
01172 {
01173 q0--, r0 += d;
01174 while( r0 >= d && r0 < m )
01175 q0--, r0 += d;
01176 }
01177 r0 -= m;
01178
01179 Z.p[i - t - 1] = ( q1 << biH ) | q0;
01180 #endif
01181 }
01182
01183 Z.p[i - t - 1]++;
01184 do
01185 {
01186 Z.p[i - t - 1]--;
01187
01188 MPI_CHK( mpi_lset( &T1, 0 ) );
01189 T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
01190 T1.p[1] = Y.p[t];
01191 MPI_CHK( mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
01192
01193 MPI_CHK( mpi_lset( &T2, 0 ) );
01194 T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
01195 T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
01196 T2.p[2] = X.p[i];
01197 }
01198 while( mpi_cmp_mpi( &T1, &T2 ) > 0 );
01199
01200 MPI_CHK( mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
01201 MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
01202 MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) );
01203
01204 if( mpi_cmp_int( &X, 0 ) < 0 )
01205 {
01206 MPI_CHK( mpi_copy( &T1, &Y ) );
01207 MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
01208 MPI_CHK( mpi_add_mpi( &X, &X, &T1 ) );
01209 Z.p[i - t - 1]--;
01210 }
01211 }
01212
01213 if( Q != NULL )
01214 {
01215 mpi_copy( Q, &Z );
01216 Q->s = A->s * B->s;
01217 }
01218
01219 if( R != NULL )
01220 {
01221 mpi_shift_r( &X, k );
01222 X.s = A->s;
01223 mpi_copy( R, &X );
01224
01225 if( mpi_cmp_int( R, 0 ) == 0 )
01226 R->s = 1;
01227 }
01228
01229 cleanup:
01230
01231 mpi_free( &X ); mpi_free( &Y ); mpi_free( &Z );
01232 mpi_free( &T1 ); mpi_free( &T2 );
01233
01234 return( ret );
01235 }
01236
01237
01238
01239
01240 int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b )
01241 {
01242 mpi _B;
01243 t_uint p[1];
01244
01245 p[0] = ( b < 0 ) ? -b : b;
01246 _B.s = ( b < 0 ) ? -1 : 1;
01247 _B.n = 1;
01248 _B.p = p;
01249
01250 return( mpi_div_mpi( Q, R, A, &_B ) );
01251 }
01252
01253
01254
01255
01256 int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B )
01257 {
01258 int ret;
01259
01260 if( mpi_cmp_int( B, 0 ) < 0 )
01261 return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
01262
01263 MPI_CHK( mpi_div_mpi( NULL, R, A, B ) );
01264
01265 while( mpi_cmp_int( R, 0 ) < 0 )
01266 MPI_CHK( mpi_add_mpi( R, R, B ) );
01267
01268 while( mpi_cmp_mpi( R, B ) >= 0 )
01269 MPI_CHK( mpi_sub_mpi( R, R, B ) );
01270
01271 cleanup:
01272
01273 return( ret );
01274 }
01275
01276
01277
01278
01279 int mpi_mod_int( t_uint *r, const mpi *A, t_sint b )
01280 {
01281 size_t i;
01282 t_uint x, y, z;
01283
01284 if( b == 0 )
01285 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
01286
01287 if( b < 0 )
01288 return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
01289
01290
01291
01292
01293 if( b == 1 )
01294 {
01295 *r = 0;
01296 return( 0 );
01297 }
01298
01299 if( b == 2 )
01300 {
01301 *r = A->p[0] & 1;
01302 return( 0 );
01303 }
01304
01305
01306
01307
01308 for( i = A->n, y = 0; i > 0; i-- )
01309 {
01310 x = A->p[i - 1];
01311 y = ( y << biH ) | ( x >> biH );
01312 z = y / b;
01313 y -= z * b;
01314
01315 x <<= biH;
01316 y = ( y << biH ) | ( x >> biH );
01317 z = y / b;
01318 y -= z * b;
01319 }
01320
01321
01322
01323
01324
01325 if( A->s < 0 && y != 0 )
01326 y = b - y;
01327
01328 *r = y;
01329
01330 return( 0 );
01331 }
01332
01333
01334
01335
01336 static void mpi_montg_init( t_uint *mm, const mpi *N )
01337 {
01338 t_uint x, m0 = N->p[0];
01339
01340 x = m0;
01341 x += ( ( m0 + 2 ) & 4 ) << 1;
01342 x *= ( 2 - ( m0 * x ) );
01343
01344 if( biL >= 16 ) x *= ( 2 - ( m0 * x ) );
01345 if( biL >= 32 ) x *= ( 2 - ( m0 * x ) );
01346 if( biL >= 64 ) x *= ( 2 - ( m0 * x ) );
01347
01348 *mm = ~x + 1;
01349 }
01350
01351
01352
01353
01354 static void mpi_montmul( mpi *A, const mpi *B, const mpi *N, t_uint mm, const mpi *T )
01355 {
01356 size_t i, n, m;
01357 t_uint u0, u1, *d;
01358
01359 memset( T->p, 0, T->n * ciL );
01360
01361 d = T->p;
01362 n = N->n;
01363 m = ( B->n < n ) ? B->n : n;
01364
01365 for( i = 0; i < n; i++ )
01366 {
01367
01368
01369
01370 u0 = A->p[i];
01371 u1 = ( d[0] + u0 * B->p[0] ) * mm;
01372
01373 mpi_mul_hlp( m, B->p, d, u0 );
01374 mpi_mul_hlp( n, N->p, d, u1 );
01375
01376 *d++ = u0; d[n + 1] = 0;
01377 }
01378
01379 memcpy( A->p, d, (n + 1) * ciL );
01380
01381 if( mpi_cmp_abs( A, N ) >= 0 )
01382 mpi_sub_hlp( n, N->p, A->p );
01383 else
01384
01385 mpi_sub_hlp( n, A->p, T->p );
01386 }
01387
01388
01389
01390
01391 static void mpi_montred( mpi *A, const mpi *N, t_uint mm, const mpi *T )
01392 {
01393 t_uint z = 1;
01394 mpi U;
01395
01396 U.n = U.s = (int) z;
01397 U.p = &z;
01398
01399 mpi_montmul( A, &U, N, mm, T );
01400 }
01401
01402
01403
01404
01405 int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR )
01406 {
01407 int ret;
01408 size_t wbits, wsize, one = 1;
01409 size_t i, j, nblimbs;
01410 size_t bufsize, nbits;
01411 t_uint ei, mm, state;
01412 mpi RR, T, W[ 2 << POLARSSL_MPI_WINDOW_SIZE ], Apos;
01413 int neg;
01414
01415 if( mpi_cmp_int( N, 0 ) < 0 || ( N->p[0] & 1 ) == 0 )
01416 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
01417
01418 if( mpi_cmp_int( E, 0 ) < 0 )
01419 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
01420
01421
01422
01423
01424 mpi_montg_init( &mm, N );
01425 mpi_init( &RR ); mpi_init( &T );
01426 memset( W, 0, sizeof( W ) );
01427
01428 i = mpi_msb( E );
01429
01430 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
01431 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
01432
01433 if( wsize > POLARSSL_MPI_WINDOW_SIZE )
01434 wsize = POLARSSL_MPI_WINDOW_SIZE;
01435
01436 j = N->n + 1;
01437 MPI_CHK( mpi_grow( X, j ) );
01438 MPI_CHK( mpi_grow( &W[1], j ) );
01439 MPI_CHK( mpi_grow( &T, j * 2 ) );
01440
01441
01442
01443
01444 neg = ( A->s == -1 );
01445
01446 mpi_init( &Apos );
01447 if( neg )
01448 {
01449 MPI_CHK( mpi_copy( &Apos, A ) );
01450 Apos.s = 1;
01451 A = &Apos;
01452 }
01453
01454
01455
01456
01457 if( _RR == NULL || _RR->p == NULL )
01458 {
01459 MPI_CHK( mpi_lset( &RR, 1 ) );
01460 MPI_CHK( mpi_shift_l( &RR, N->n * 2 * biL ) );
01461 MPI_CHK( mpi_mod_mpi( &RR, &RR, N ) );
01462
01463 if( _RR != NULL )
01464 memcpy( _RR, &RR, sizeof( mpi ) );
01465 }
01466 else
01467 memcpy( &RR, _RR, sizeof( mpi ) );
01468
01469
01470
01471
01472 if( mpi_cmp_mpi( A, N ) >= 0 )
01473 mpi_mod_mpi( &W[1], A, N );
01474 else mpi_copy( &W[1], A );
01475
01476 mpi_montmul( &W[1], &RR, N, mm, &T );
01477
01478
01479
01480
01481 MPI_CHK( mpi_copy( X, &RR ) );
01482 mpi_montred( X, N, mm, &T );
01483
01484 if( wsize > 1 )
01485 {
01486
01487
01488
01489 j = one << (wsize - 1);
01490
01491 MPI_CHK( mpi_grow( &W[j], N->n + 1 ) );
01492 MPI_CHK( mpi_copy( &W[j], &W[1] ) );
01493
01494 for( i = 0; i < wsize - 1; i++ )
01495 mpi_montmul( &W[j], &W[j], N, mm, &T );
01496
01497
01498
01499
01500 for( i = j + 1; i < (one << wsize); i++ )
01501 {
01502 MPI_CHK( mpi_grow( &W[i], N->n + 1 ) );
01503 MPI_CHK( mpi_copy( &W[i], &W[i - 1] ) );
01504
01505 mpi_montmul( &W[i], &W[1], N, mm, &T );
01506 }
01507 }
01508
01509 nblimbs = E->n;
01510 bufsize = 0;
01511 nbits = 0;
01512 wbits = 0;
01513 state = 0;
01514
01515 while( 1 )
01516 {
01517 if( bufsize == 0 )
01518 {
01519 if( nblimbs == 0 )
01520 break;
01521
01522 nblimbs--;
01523
01524 bufsize = sizeof( t_uint ) << 3;
01525 }
01526
01527 bufsize--;
01528
01529 ei = (E->p[nblimbs] >> bufsize) & 1;
01530
01531
01532
01533
01534 if( ei == 0 && state == 0 )
01535 continue;
01536
01537 if( ei == 0 && state == 1 )
01538 {
01539
01540
01541
01542 mpi_montmul( X, X, N, mm, &T );
01543 continue;
01544 }
01545
01546
01547
01548
01549 state = 2;
01550
01551 nbits++;
01552 wbits |= (ei << (wsize - nbits));
01553
01554 if( nbits == wsize )
01555 {
01556
01557
01558
01559 for( i = 0; i < wsize; i++ )
01560 mpi_montmul( X, X, N, mm, &T );
01561
01562
01563
01564
01565 mpi_montmul( X, &W[wbits], N, mm, &T );
01566
01567 state--;
01568 nbits = 0;
01569 wbits = 0;
01570 }
01571 }
01572
01573
01574
01575
01576 for( i = 0; i < nbits; i++ )
01577 {
01578 mpi_montmul( X, X, N, mm, &T );
01579
01580 wbits <<= 1;
01581
01582 if( (wbits & (one << wsize)) != 0 )
01583 mpi_montmul( X, &W[1], N, mm, &T );
01584 }
01585
01586
01587
01588
01589 mpi_montred( X, N, mm, &T );
01590
01591 if( neg )
01592 {
01593 X->s = -1;
01594 mpi_add_mpi( X, N, X );
01595 }
01596
01597 cleanup:
01598
01599 for( i = (one << (wsize - 1)); i < (one << wsize); i++ )
01600 mpi_free( &W[i] );
01601
01602 mpi_free( &W[1] ); mpi_free( &T ); mpi_free( &Apos );
01603
01604 if( _RR == NULL )
01605 mpi_free( &RR );
01606
01607 return( ret );
01608 }
01609
01610
01611
01612
01613 int mpi_gcd( mpi *G, const mpi *A, const mpi *B )
01614 {
01615 int ret;
01616 size_t lz, lzt;
01617 mpi TG, TA, TB;
01618
01619 mpi_init( &TG ); mpi_init( &TA ); mpi_init( &TB );
01620
01621 MPI_CHK( mpi_copy( &TA, A ) );
01622 MPI_CHK( mpi_copy( &TB, B ) );
01623
01624 lz = mpi_lsb( &TA );
01625 lzt = mpi_lsb( &TB );
01626
01627 if ( lzt < lz )
01628 lz = lzt;
01629
01630 MPI_CHK( mpi_shift_r( &TA, lz ) );
01631 MPI_CHK( mpi_shift_r( &TB, lz ) );
01632
01633 TA.s = TB.s = 1;
01634
01635 while( mpi_cmp_int( &TA, 0 ) != 0 )
01636 {
01637 MPI_CHK( mpi_shift_r( &TA, mpi_lsb( &TA ) ) );
01638 MPI_CHK( mpi_shift_r( &TB, mpi_lsb( &TB ) ) );
01639
01640 if( mpi_cmp_mpi( &TA, &TB ) >= 0 )
01641 {
01642 MPI_CHK( mpi_sub_abs( &TA, &TA, &TB ) );
01643 MPI_CHK( mpi_shift_r( &TA, 1 ) );
01644 }
01645 else
01646 {
01647 MPI_CHK( mpi_sub_abs( &TB, &TB, &TA ) );
01648 MPI_CHK( mpi_shift_r( &TB, 1 ) );
01649 }
01650 }
01651
01652 MPI_CHK( mpi_shift_l( &TB, lz ) );
01653 MPI_CHK( mpi_copy( G, &TB ) );
01654
01655 cleanup:
01656
01657 mpi_free( &TG ); mpi_free( &TA ); mpi_free( &TB );
01658
01659 return( ret );
01660 }
01661
01662 int mpi_fill_random( mpi *X, size_t size,
01663 int (*f_rng)(void *, unsigned char *, size_t),
01664 void *p_rng )
01665 {
01666 int ret;
01667
01668 MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( size ) ) );
01669 MPI_CHK( mpi_lset( X, 0 ) );
01670
01671 MPI_CHK( f_rng( p_rng, (unsigned char *) X->p, size ) );
01672
01673 cleanup:
01674 return( ret );
01675 }
01676
01677
01678
01679
01680 int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N )
01681 {
01682 int ret;
01683 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
01684
01685 if( mpi_cmp_int( N, 0 ) <= 0 )
01686 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
01687
01688 mpi_init( &TA ); mpi_init( &TU ); mpi_init( &U1 ); mpi_init( &U2 );
01689 mpi_init( &G ); mpi_init( &TB ); mpi_init( &TV );
01690 mpi_init( &V1 ); mpi_init( &V2 );
01691
01692 MPI_CHK( mpi_gcd( &G, A, N ) );
01693
01694 if( mpi_cmp_int( &G, 1 ) != 0 )
01695 {
01696 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
01697 goto cleanup;
01698 }
01699
01700 MPI_CHK( mpi_mod_mpi( &TA, A, N ) );
01701 MPI_CHK( mpi_copy( &TU, &TA ) );
01702 MPI_CHK( mpi_copy( &TB, N ) );
01703 MPI_CHK( mpi_copy( &TV, N ) );
01704
01705 MPI_CHK( mpi_lset( &U1, 1 ) );
01706 MPI_CHK( mpi_lset( &U2, 0 ) );
01707 MPI_CHK( mpi_lset( &V1, 0 ) );
01708 MPI_CHK( mpi_lset( &V2, 1 ) );
01709
01710 do
01711 {
01712 while( ( TU.p[0] & 1 ) == 0 )
01713 {
01714 MPI_CHK( mpi_shift_r( &TU, 1 ) );
01715
01716 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
01717 {
01718 MPI_CHK( mpi_add_mpi( &U1, &U1, &TB ) );
01719 MPI_CHK( mpi_sub_mpi( &U2, &U2, &TA ) );
01720 }
01721
01722 MPI_CHK( mpi_shift_r( &U1, 1 ) );
01723 MPI_CHK( mpi_shift_r( &U2, 1 ) );
01724 }
01725
01726 while( ( TV.p[0] & 1 ) == 0 )
01727 {
01728 MPI_CHK( mpi_shift_r( &TV, 1 ) );
01729
01730 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
01731 {
01732 MPI_CHK( mpi_add_mpi( &V1, &V1, &TB ) );
01733 MPI_CHK( mpi_sub_mpi( &V2, &V2, &TA ) );
01734 }
01735
01736 MPI_CHK( mpi_shift_r( &V1, 1 ) );
01737 MPI_CHK( mpi_shift_r( &V2, 1 ) );
01738 }
01739
01740 if( mpi_cmp_mpi( &TU, &TV ) >= 0 )
01741 {
01742 MPI_CHK( mpi_sub_mpi( &TU, &TU, &TV ) );
01743 MPI_CHK( mpi_sub_mpi( &U1, &U1, &V1 ) );
01744 MPI_CHK( mpi_sub_mpi( &U2, &U2, &V2 ) );
01745 }
01746 else
01747 {
01748 MPI_CHK( mpi_sub_mpi( &TV, &TV, &TU ) );
01749 MPI_CHK( mpi_sub_mpi( &V1, &V1, &U1 ) );
01750 MPI_CHK( mpi_sub_mpi( &V2, &V2, &U2 ) );
01751 }
01752 }
01753 while( mpi_cmp_int( &TU, 0 ) != 0 );
01754
01755 while( mpi_cmp_int( &V1, 0 ) < 0 )
01756 MPI_CHK( mpi_add_mpi( &V1, &V1, N ) );
01757
01758 while( mpi_cmp_mpi( &V1, N ) >= 0 )
01759 MPI_CHK( mpi_sub_mpi( &V1, &V1, N ) );
01760
01761 MPI_CHK( mpi_copy( X, &V1 ) );
01762
01763 cleanup:
01764
01765 mpi_free( &TA ); mpi_free( &TU ); mpi_free( &U1 ); mpi_free( &U2 );
01766 mpi_free( &G ); mpi_free( &TB ); mpi_free( &TV );
01767 mpi_free( &V1 ); mpi_free( &V2 );
01768
01769 return( ret );
01770 }
01771
01772 #if defined(POLARSSL_GENPRIME)
01773
01774 static const int small_prime[] =
01775 {
01776 3, 5, 7, 11, 13, 17, 19, 23,
01777 29, 31, 37, 41, 43, 47, 53, 59,
01778 61, 67, 71, 73, 79, 83, 89, 97,
01779 101, 103, 107, 109, 113, 127, 131, 137,
01780 139, 149, 151, 157, 163, 167, 173, 179,
01781 181, 191, 193, 197, 199, 211, 223, 227,
01782 229, 233, 239, 241, 251, 257, 263, 269,
01783 271, 277, 281, 283, 293, 307, 311, 313,
01784 317, 331, 337, 347, 349, 353, 359, 367,
01785 373, 379, 383, 389, 397, 401, 409, 419,
01786 421, 431, 433, 439, 443, 449, 457, 461,
01787 463, 467, 479, 487, 491, 499, 503, 509,
01788 521, 523, 541, 547, 557, 563, 569, 571,
01789 577, 587, 593, 599, 601, 607, 613, 617,
01790 619, 631, 641, 643, 647, 653, 659, 661,
01791 673, 677, 683, 691, 701, 709, 719, 727,
01792 733, 739, 743, 751, 757, 761, 769, 773,
01793 787, 797, 809, 811, 821, 823, 827, 829,
01794 839, 853, 857, 859, 863, 877, 881, 883,
01795 887, 907, 911, 919, 929, 937, 941, 947,
01796 953, 967, 971, 977, 983, 991, 997, -103
01797 };
01798
01799
01800
01801
01802 int mpi_is_prime( mpi *X,
01803 int (*f_rng)(void *, unsigned char *, size_t),
01804 void *p_rng )
01805 {
01806 int ret, xs;
01807 size_t i, j, n, s;
01808 mpi W, R, T, A, RR;
01809
01810 if( mpi_cmp_int( X, 0 ) == 0 ||
01811 mpi_cmp_int( X, 1 ) == 0 )
01812 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
01813
01814 if( mpi_cmp_int( X, 2 ) == 0 )
01815 return( 0 );
01816
01817 mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A );
01818 mpi_init( &RR );
01819
01820 xs = X->s; X->s = 1;
01821
01822
01823
01824
01825 if( ( X->p[0] & 1 ) == 0 )
01826 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
01827
01828 for( i = 0; small_prime[i] > 0; i++ )
01829 {
01830 t_uint r;
01831
01832 if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
01833 return( 0 );
01834
01835 MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) );
01836
01837 if( r == 0 )
01838 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
01839 }
01840
01841
01842
01843
01844
01845 MPI_CHK( mpi_sub_int( &W, X, 1 ) );
01846 s = mpi_lsb( &W );
01847 MPI_CHK( mpi_copy( &R, &W ) );
01848 MPI_CHK( mpi_shift_r( &R, s ) );
01849
01850 i = mpi_msb( X );
01851
01852
01853
01854 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
01855 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
01856 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
01857
01858 for( i = 0; i < n; i++ )
01859 {
01860
01861
01862
01863 MPI_CHK( mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
01864
01865 if( mpi_cmp_mpi( &A, &W ) >= 0 )
01866 {
01867 j = mpi_msb( &A ) - mpi_msb( &W );
01868 MPI_CHK( mpi_shift_r( &A, j + 1 ) );
01869 }
01870 A.p[0] |= 3;
01871
01872
01873
01874
01875 MPI_CHK( mpi_exp_mod( &A, &A, &R, X, &RR ) );
01876
01877 if( mpi_cmp_mpi( &A, &W ) == 0 ||
01878 mpi_cmp_int( &A, 1 ) == 0 )
01879 continue;
01880
01881 j = 1;
01882 while( j < s && mpi_cmp_mpi( &A, &W ) != 0 )
01883 {
01884
01885
01886
01887 MPI_CHK( mpi_mul_mpi( &T, &A, &A ) );
01888 MPI_CHK( mpi_mod_mpi( &A, &T, X ) );
01889
01890 if( mpi_cmp_int( &A, 1 ) == 0 )
01891 break;
01892
01893 j++;
01894 }
01895
01896
01897
01898
01899 if( mpi_cmp_mpi( &A, &W ) != 0 ||
01900 mpi_cmp_int( &A, 1 ) == 0 )
01901 {
01902 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
01903 break;
01904 }
01905 }
01906
01907 cleanup:
01908
01909 X->s = xs;
01910
01911 mpi_free( &W ); mpi_free( &R ); mpi_free( &T ); mpi_free( &A );
01912 mpi_free( &RR );
01913
01914 return( ret );
01915 }
01916
01917
01918
01919
01920 int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
01921 int (*f_rng)(void *, unsigned char *, size_t),
01922 void *p_rng )
01923 {
01924 int ret;
01925 size_t k, n;
01926 mpi Y;
01927
01928 if( nbits < 3 || nbits > POLARSSL_MPI_MAX_BITS )
01929 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
01930
01931 mpi_init( &Y );
01932
01933 n = BITS_TO_LIMBS( nbits );
01934
01935 MPI_CHK( mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
01936
01937 k = mpi_msb( X );
01938 if( k < nbits ) MPI_CHK( mpi_shift_l( X, nbits - k ) );
01939 if( k > nbits ) MPI_CHK( mpi_shift_r( X, k - nbits ) );
01940
01941 X->p[0] |= 3;
01942
01943 if( dh_flag == 0 )
01944 {
01945 while( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
01946 {
01947 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
01948 goto cleanup;
01949
01950 MPI_CHK( mpi_add_int( X, X, 2 ) );
01951 }
01952 }
01953 else
01954 {
01955 MPI_CHK( mpi_sub_int( &Y, X, 1 ) );
01956 MPI_CHK( mpi_shift_r( &Y, 1 ) );
01957
01958 while( 1 )
01959 {
01960 if( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) == 0 )
01961 {
01962 if( ( ret = mpi_is_prime( &Y, f_rng, p_rng ) ) == 0 )
01963 break;
01964
01965 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
01966 goto cleanup;
01967 }
01968
01969 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
01970 goto cleanup;
01971
01972 MPI_CHK( mpi_add_int( &Y, X, 1 ) );
01973 MPI_CHK( mpi_add_int( X, X, 2 ) );
01974 MPI_CHK( mpi_shift_r( &Y, 1 ) );
01975 }
01976 }
01977
01978 cleanup:
01979
01980 mpi_free( &Y );
01981
01982 return( ret );
01983 }
01984
01985 #endif
01986
01987 #if defined(POLARSSL_SELF_TEST)
01988
01989 #define GCD_PAIR_COUNT 3
01990
01991 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
01992 {
01993 { 693, 609, 21 },
01994 { 1764, 868, 28 },
01995 { 768454923, 542167814, 1 }
01996 };
01997
01998
01999
02000
02001 int mpi_self_test( int verbose )
02002 {
02003 int ret, i;
02004 mpi A, E, N, X, Y, U, V;
02005
02006 mpi_init( &A ); mpi_init( &E ); mpi_init( &N ); mpi_init( &X );
02007 mpi_init( &Y ); mpi_init( &U ); mpi_init( &V );
02008
02009 MPI_CHK( mpi_read_string( &A, 16,
02010 "EFE021C2645FD1DC586E69184AF4A31E" \
02011 "D5F53E93B5F123FA41680867BA110131" \
02012 "944FE7952E2517337780CB0DB80E61AA" \
02013 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
02014
02015 MPI_CHK( mpi_read_string( &E, 16,
02016 "B2E7EFD37075B9F03FF989C7C5051C20" \
02017 "34D2A323810251127E7BF8625A4F49A5" \
02018 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
02019 "5B5C25763222FEFCCFC38B832366C29E" ) );
02020
02021 MPI_CHK( mpi_read_string( &N, 16,
02022 "0066A198186C18C10B2F5ED9B522752A" \
02023 "9830B69916E535C8F047518A889A43A5" \
02024 "94B6BED27A168D31D4A52F88925AA8F5" ) );
02025
02026 MPI_CHK( mpi_mul_mpi( &X, &A, &N ) );
02027
02028 MPI_CHK( mpi_read_string( &U, 16,
02029 "602AB7ECA597A3D6B56FF9829A5E8B85" \
02030 "9E857EA95A03512E2BAE7391688D264A" \
02031 "A5663B0341DB9CCFD2C4C5F421FEC814" \
02032 "8001B72E848A38CAE1C65F78E56ABDEF" \
02033 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
02034 "ECF677152EF804370C1A305CAF3B5BF1" \
02035 "30879B56C61DE584A0F53A2447A51E" ) );
02036
02037 if( verbose != 0 )
02038 printf( " MPI test #1 (mul_mpi): " );
02039
02040 if( mpi_cmp_mpi( &X, &U ) != 0 )
02041 {
02042 if( verbose != 0 )
02043 printf( "failed\n" );
02044
02045 return( 1 );
02046 }
02047
02048 if( verbose != 0 )
02049 printf( "passed\n" );
02050
02051 MPI_CHK( mpi_div_mpi( &X, &Y, &A, &N ) );
02052
02053 MPI_CHK( mpi_read_string( &U, 16,
02054 "256567336059E52CAE22925474705F39A94" ) );
02055
02056 MPI_CHK( mpi_read_string( &V, 16,
02057 "6613F26162223DF488E9CD48CC132C7A" \
02058 "0AC93C701B001B092E4E5B9F73BCD27B" \
02059 "9EE50D0657C77F374E903CDFA4C642" ) );
02060
02061 if( verbose != 0 )
02062 printf( " MPI test #2 (div_mpi): " );
02063
02064 if( mpi_cmp_mpi( &X, &U ) != 0 ||
02065 mpi_cmp_mpi( &Y, &V ) != 0 )
02066 {
02067 if( verbose != 0 )
02068 printf( "failed\n" );
02069
02070 return( 1 );
02071 }
02072
02073 if( verbose != 0 )
02074 printf( "passed\n" );
02075
02076 MPI_CHK( mpi_exp_mod( &X, &A, &E, &N, NULL ) );
02077
02078 MPI_CHK( mpi_read_string( &U, 16,
02079 "36E139AEA55215609D2816998ED020BB" \
02080 "BD96C37890F65171D948E9BC7CBAA4D9" \
02081 "325D24D6A3C12710F10A09FA08AB87" ) );
02082
02083 if( verbose != 0 )
02084 printf( " MPI test #3 (exp_mod): " );
02085
02086 if( mpi_cmp_mpi( &X, &U ) != 0 )
02087 {
02088 if( verbose != 0 )
02089 printf( "failed\n" );
02090
02091 return( 1 );
02092 }
02093
02094 if( verbose != 0 )
02095 printf( "passed\n" );
02096
02097 MPI_CHK( mpi_inv_mod( &X, &A, &N ) );
02098
02099 MPI_CHK( mpi_read_string( &U, 16,
02100 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
02101 "C3DBA76456363A10869622EAC2DD84EC" \
02102 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
02103
02104 if( verbose != 0 )
02105 printf( " MPI test #4 (inv_mod): " );
02106
02107 if( mpi_cmp_mpi( &X, &U ) != 0 )
02108 {
02109 if( verbose != 0 )
02110 printf( "failed\n" );
02111
02112 return( 1 );
02113 }
02114
02115 if( verbose != 0 )
02116 printf( "passed\n" );
02117
02118 if( verbose != 0 )
02119 printf( " MPI test #5 (simple gcd): " );
02120
02121 for ( i = 0; i < GCD_PAIR_COUNT; i++)
02122 {
02123 MPI_CHK( mpi_lset( &X, gcd_pairs[i][0] ) );
02124 MPI_CHK( mpi_lset( &Y, gcd_pairs[i][1] ) );
02125
02126 MPI_CHK( mpi_gcd( &A, &X, &Y ) );
02127
02128 if( mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
02129 {
02130 if( verbose != 0 )
02131 printf( "failed at %d\n", i );
02132
02133 return( 1 );
02134 }
02135 }
02136
02137 if( verbose != 0 )
02138 printf( "passed\n" );
02139
02140 cleanup:
02141
02142 if( ret != 0 && verbose != 0 )
02143 printf( "Unexpected error, return code = %08X\n", ret );
02144
02145 mpi_free( &A ); mpi_free( &E ); mpi_free( &N ); mpi_free( &X );
02146 mpi_free( &Y ); mpi_free( &U ); mpi_free( &V );
02147
02148 if( verbose != 0 )
02149 printf( "\n" );
02150
02151 return( ret );
02152 }
02153
02154 #endif
02155
02156 #endif