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