35 #if defined(POLARSSL_BIGNUM_C)
42 #define ciL (sizeof(t_uint))
43 #define biL (ciL << 3)
44 #define biH (ciL << 2)
49 #define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL)
50 #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
75 memset( X->
p, 0, X->
n * ciL );
96 if( ( p = (
t_uint *) malloc( nblimbs * ciL ) ) == NULL )
99 memset( p, 0, nblimbs * ciL );
103 memcpy( p, X->
p, X->
n * ciL );
104 memset( X->
p, 0, X->
n * ciL );
126 for( i = Y->
n - 1; i > 0; i-- )
135 memset( X->
p, 0, X->
n * ciL );
136 memcpy( X->
p, Y->
p, i * ciL );
150 memcpy( &T, X,
sizeof(
mpi ) );
151 memcpy( X, Y,
sizeof(
mpi ) );
152 memcpy( Y, &T,
sizeof(
mpi ) );
163 memset( X->
p, 0, X->
n * ciL );
165 X->
p[0] = ( z < 0 ) ? -z : z;
166 X->
s = ( z < 0 ) ? -1 : 1;
178 if( X->
n * biL <= pos )
181 return ( X->
p[pos / biL] >> ( pos % biL ) ) & 0x01;
190 size_t off = pos / biL;
191 size_t idx = pos % biL;
193 if( val != 0 && val != 1 )
196 if( X->
n * biL <= pos )
204 X->
p[off] = ( X->
p[off] & ~( 0x01 << idx ) ) | ( val << idx );
216 size_t i, j, count = 0;
218 for( i = 0; i < X->
n; i++ )
219 for( j = 0; j < biL; j++, count++ )
220 if( ( ( X->
p[i] >> j ) & 1 ) != 0 )
233 for( i = X->
n - 1; i > 0; i-- )
237 for( j = biL; j > 0; j-- )
238 if( ( ( X->
p[i] >> ( j - 1 ) ) & 1 ) != 0 )
241 return( ( i * biL ) + j );
249 return( (
mpi_msb( X ) + 7 ) >> 3 );
255 static int mpi_get_digit(
t_uint *d,
int radix,
char c )
259 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
260 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
261 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
263 if( *d >= (
t_uint) radix )
275 size_t i, j, slen, n;
279 if( radix < 2 || radix > 16 )
288 n = BITS_TO_LIMBS( slen << 2 );
293 for( i = slen, j = 0; i > 0; i--, j++ )
295 if( i == 1 && s[i - 1] ==
'-' )
301 MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
302 X->
p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 );
309 for( i = 0; i < slen; i++ )
311 if( i == 0 && s[i] ==
'-' )
317 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
341 static int mpi_write_hlp(
mpi *X,
int radix,
char **p )
346 if( radix < 2 || radix > 16 )
353 MPI_CHK( mpi_write_hlp( X, radix, p ) );
356 *(*p)++ = (char)( r + 0x30 );
358 *(*p)++ = (char)( r + 0x37 );
375 if( radix < 2 || radix > 16 )
379 if( radix >= 4 ) n >>= 1;
380 if( radix >= 16 ) n >>= 1;
400 for( i = X->
n, k = 0; i > 0; i-- )
402 for( j = ciL; j > 0; j-- )
404 c = ( X->
p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
406 if( c == 0 && k == 0 && ( i + j + 3 ) != 0 )
409 p += sprintf( p,
"%02X", c );
421 MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
434 #if defined(POLARSSL_FS_IO)
449 memset( s, 0,
sizeof( s ) );
450 if( fgets( s,
sizeof( s ) - 1, fin ) == NULL )
454 if( slen ==
sizeof( s ) - 2 )
457 if( s[slen - 1] ==
'\n' ) { slen--; s[slen] =
'\0'; }
458 if( s[slen - 1] ==
'\r' ) { slen--; s[slen] =
'\0'; }
462 if( mpi_get_digit( &d, radix, *p ) != 0 )
474 size_t n, slen, plen;
486 if( p == NULL ) p =
"";
495 if( fwrite( p, 1, plen, fout ) != plen ||
496 fwrite( s, 1, slen, fout ) != slen )
500 printf(
"%s%s", p, s );
516 for( n = 0; n < buflen; n++ )
523 for( i = buflen, j = 0; i > n; i--, j++ )
524 X->
p[j / ciL] |= ((
t_uint) buf[i - 1]) << ((j % ciL) << 3);
543 memset( buf, 0, buflen );
545 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
546 buf[i] = (
unsigned char)( X->
p[j / ciL] >> ((j % ciL) << 3) );
561 t1 = count & (biL - 1);
575 for( i = X->
n; i > v0; i-- )
576 X->
p[i - 1] = X->
p[i - v0 - 1];
587 for( i = v0; i < X->
n; i++ )
589 r1 = X->
p[i] >> (biL - t1);
610 v1 = count & (biL - 1);
617 for( i = 0; i < X->
n - v0; i++ )
618 X->
p[i] = X->
p[i + v0];
620 for( ; i < X->n; i++ )
629 for( i = X->
n; i > 0; i-- )
631 r1 = X->
p[i - 1] << (biL - v1);
648 for( i = X->
n; i > 0; i-- )
649 if( X->
p[i - 1] != 0 )
652 for( j = Y->
n; j > 0; j-- )
653 if( Y->
p[j - 1] != 0 )
656 if( i == 0 && j == 0 )
659 if( i > j )
return( 1 );
660 if( j > i )
return( -1 );
664 if( X->
p[i - 1] > Y->
p[i - 1] )
return( 1 );
665 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -1 );
678 for( i = X->
n; i > 0; i-- )
679 if( X->
p[i - 1] != 0 )
682 for( j = Y->
n; j > 0; j-- )
683 if( Y->
p[j - 1] != 0 )
686 if( i == 0 && j == 0 )
689 if( i > j )
return( X->
s );
690 if( j > i )
return( -Y->
s );
692 if( X->
s > 0 && Y->
s < 0 )
return( 1 );
693 if( Y->
s > 0 && X->
s < 0 )
return( -1 );
697 if( X->
p[i - 1] > Y->
p[i - 1] )
return( X->
s );
698 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -X->
s );
712 *p = ( z < 0 ) ? -z : z;
713 Y.
s = ( z < 0 ) ? -1 : 1;
731 const mpi *T = A; A = X; B = T;
742 for( j = B->
n; j > 0; j-- )
743 if( B->
p[j - 1] != 0 )
748 o = B->
p; p = X->
p; c = 0;
750 for( i = 0; i < j; i++, o++, p++ )
752 *p += c; c = ( *p < c );
753 *p += *o; c += ( *p < *o );
764 *p += c; c = ( *p < c ); i++;
775 static void mpi_sub_hlp(
size_t n,
t_uint *s,
t_uint *d )
780 for( i = c = 0; i < n; i++, s++, d++ )
782 z = ( *d < c ); *d -= c;
783 c = ( *d < *s ) + z; *d -= *s;
788 z = ( *d < c ); *d -= c;
823 for( n = B->
n; n > 0; n-- )
824 if( B->
p[n - 1] != 0 )
827 mpi_sub_hlp( n, B->
p, X->
p );
843 if( A->
s * B->
s < 0 )
874 if( A->
s * B->
s > 0 )
906 p[0] = ( b < 0 ) ? -b : b;
907 _B.
s = ( b < 0 ) ? -1 : 1;
922 p[0] = ( b < 0 ) ? -b : b;
923 _B.
s = ( b < 0 ) ? -1 : 1;
937 #if defined(MULADDC_HUIT)
938 for( ; i >= 8; i -= 8 )
952 for( ; i >= 16; i -= 16 )
967 for( ; i >= 8; i -= 8 )
989 *d += c; c = ( *d < c ); d++;
1008 for( i = A->
n; i > 0; i-- )
1009 if( A->
p[i - 1] != 0 )
1012 for( j = B->
n; j > 0; j-- )
1013 if( B->
p[j - 1] != 0 )
1019 for( i++; j > 0; j-- )
1020 mpi_mul_hlp( i - 1, A->
p, X->
p + j - 1, B->
p[j - 1] );
1054 mpi X, Y, Z, T1, T2;
1098 for( i = n; i > t ; i-- )
1100 if( X.
p[i] >= Y.
p[t] )
1101 Z.
p[i - t - 1] = ~0;
1104 #if defined(POLARSSL_HAVE_LONGLONG)
1107 r = (t_udbl) X.
p[i] << biL;
1108 r |= (t_udbl) X.
p[i - 1];
1110 if( r > ((t_udbl) 1 << biL) - 1)
1111 r = ((t_udbl) 1 << biL) - 1;
1122 d0 = ( d << biH ) >> biH;
1126 r1 = X.
p[i] - d1 * q1;
1128 r1 |= ( X.
p[i - 1] >> biH );
1134 while( r1 >= d && r1 < m )
1142 r0 |= ( X.
p[i - 1] << biH ) >> biH;
1148 while( r0 >= d && r0 < m )
1153 Z.
p[i - t - 1] = ( q1 << biH ) | q0;
1163 T1.
p[0] = (t < 1) ? 0 : Y.
p[t - 1];
1168 T2.
p[0] = (i < 2) ? 0 : X.
p[i - 2];
1169 T2.
p[1] = (i < 1) ? 0 : X.
p[i - 1];
1223 p[0] = ( b < 0 ) ? -b : b;
1224 _B.
s = ( b < 0 ) ? -1 : 1;
1286 for( i = A->
n, y = 0; i > 0; i-- )
1289 y = ( y << biH ) | ( x >> biH );
1294 y = ( y << biH ) | ( x >> biH );
1303 if( A->
s < 0 && y != 0 )
1314 static void mpi_montg_init(
t_uint *mm,
const mpi *N )
1319 x += ( ( m0 + 2 ) & 4 ) << 1;
1320 x *= ( 2 - ( m0 * x ) );
1322 if( biL >= 16 ) x *= ( 2 - ( m0 * x ) );
1323 if( biL >= 32 ) x *= ( 2 - ( m0 * x ) );
1324 if( biL >= 64 ) x *= ( 2 - ( m0 * x ) );
1332 static void mpi_montmul(
mpi *A,
const mpi *B,
const mpi *N,
t_uint mm,
const mpi *T )
1337 memset( T->
p, 0, T->
n * ciL );
1341 m = ( B->
n < n ) ? B->
n : n;
1343 for( i = 0; i < n; i++ )
1349 u1 = ( d[0] + u0 * B->
p[0] ) * mm;
1351 mpi_mul_hlp( m, B->
p, d, u0 );
1352 mpi_mul_hlp( n, N->
p, d, u1 );
1354 *d++ = u0; d[n + 1] = 0;
1357 memcpy( A->
p, d, (n + 1) * ciL );
1360 mpi_sub_hlp( n, N->
p, A->
p );
1363 mpi_sub_hlp( n, A->
p, T->
p );
1369 static void mpi_montred(
mpi *A,
const mpi *N,
t_uint mm,
const mpi *T )
1377 mpi_montmul( A, &U, N, mm, T );
1386 size_t wbits, wsize, one = 1;
1387 size_t i, j, nblimbs;
1388 size_t bufsize, nbits;
1398 mpi_montg_init( &mm, N );
1400 memset( W, 0,
sizeof( W ) );
1404 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1405 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1418 if( _RR == NULL || _RR->
p == NULL )
1425 memcpy( _RR, &RR,
sizeof(
mpi ) );
1428 memcpy( &RR, _RR,
sizeof(
mpi ) );
1437 mpi_montmul( &W[1], &RR, N, mm, &T );
1443 mpi_montred( X, N, mm, &T );
1450 j = one << (wsize - 1);
1455 for( i = 0; i < wsize - 1; i++ )
1456 mpi_montmul( &W[j], &W[j], N, mm, &T );
1461 for( i = j + 1; i < (one << wsize); i++ )
1466 mpi_montmul( &W[i], &W[1], N, mm, &T );
1480 if( nblimbs-- == 0 )
1483 bufsize =
sizeof(
t_uint ) << 3;
1488 ei = (E->
p[nblimbs] >> bufsize) & 1;
1493 if( ei == 0 && state == 0 )
1496 if( ei == 0 && state == 1 )
1501 mpi_montmul( X, X, N, mm, &T );
1511 wbits |= (ei << (wsize - nbits));
1513 if( nbits == wsize )
1518 for( i = 0; i < wsize; i++ )
1519 mpi_montmul( X, X, N, mm, &T );
1524 mpi_montmul( X, &W[wbits], N, mm, &T );
1535 for( i = 0; i < nbits; i++ )
1537 mpi_montmul( X, X, N, mm, &T );
1541 if( (wbits & (one << wsize)) != 0 )
1542 mpi_montmul( X, &W[1], N, mm, &T );
1548 mpi_montred( X, N, mm, &T );
1552 for( i = (one << (wsize - 1)); i < (one << wsize); i++ )
1616 int (*f_rng)(
void *,
unsigned char *,
size_t),
1624 MPI_CHK( f_rng( p_rng, (
unsigned char *) X->
p, size ) );
1630 #if defined(POLARSSL_GENPRIME)
1638 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1667 while( ( TU.
p[0] & 1 ) == 0 )
1671 if( ( U1.
p[0] & 1 ) != 0 || ( U2.
p[0] & 1 ) != 0 )
1681 while( ( TV.
p[0] & 1 ) == 0 )
1685 if( ( V1.
p[0] & 1 ) != 0 || ( V2.
p[0] & 1 ) != 0 )
1727 static const int small_prime[] =
1729 3, 5, 7, 11, 13, 17, 19, 23,
1730 29, 31, 37, 41, 43, 47, 53, 59,
1731 61, 67, 71, 73, 79, 83, 89, 97,
1732 101, 103, 107, 109, 113, 127, 131, 137,
1733 139, 149, 151, 157, 163, 167, 173, 179,
1734 181, 191, 193, 197, 199, 211, 223, 227,
1735 229, 233, 239, 241, 251, 257, 263, 269,
1736 271, 277, 281, 283, 293, 307, 311, 313,
1737 317, 331, 337, 347, 349, 353, 359, 367,
1738 373, 379, 383, 389, 397, 401, 409, 419,
1739 421, 431, 433, 439, 443, 449, 457, 461,
1740 463, 467, 479, 487, 491, 499, 503, 509,
1741 521, 523, 541, 547, 557, 563, 569, 571,
1742 577, 587, 593, 599, 601, 607, 613, 617,
1743 619, 631, 641, 643, 647, 653, 659, 661,
1744 673, 677, 683, 691, 701, 709, 719, 727,
1745 733, 739, 743, 751, 757, 761, 769, 773,
1746 787, 797, 809, 811, 821, 823, 827, 829,
1747 839, 853, 857, 859, 863, 877, 881, 883,
1748 887, 907, 911, 919, 929, 937, 941, 947,
1749 953, 967, 971, 977, 983, 991, 997, -103
1756 int (*f_rng)(
void *,
unsigned char *,
size_t),
1773 xs = X->
s; X->
s = 1;
1778 if( ( X->
p[0] & 1 ) == 0 )
1781 for( i = 0; small_prime[i] > 0; i++ )
1807 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1808 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1809 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1811 for( i = 0; i < n; i++ )
1874 int (*f_rng)(
void *,
unsigned char *,
size_t),
1886 n = BITS_TO_LIMBS( nbits );
1898 while( ( ret =
mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
1940 #if defined(POLARSSL_SELF_TEST)
1942 #define GCD_PAIR_COUNT 3
1944 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
1948 { 768454923, 542167814, 1 }
1957 mpi A, E, N, X, Y, U, V;
1963 "EFE021C2645FD1DC586E69184AF4A31E" \
1964 "D5F53E93B5F123FA41680867BA110131" \
1965 "944FE7952E2517337780CB0DB80E61AA" \
1966 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
1969 "B2E7EFD37075B9F03FF989C7C5051C20" \
1970 "34D2A323810251127E7BF8625A4F49A5" \
1971 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
1972 "5B5C25763222FEFCCFC38B832366C29E" ) );
1975 "0066A198186C18C10B2F5ED9B522752A" \
1976 "9830B69916E535C8F047518A889A43A5" \
1977 "94B6BED27A168D31D4A52F88925AA8F5" ) );
1982 "602AB7ECA597A3D6B56FF9829A5E8B85" \
1983 "9E857EA95A03512E2BAE7391688D264A" \
1984 "A5663B0341DB9CCFD2C4C5F421FEC814" \
1985 "8001B72E848A38CAE1C65F78E56ABDEF" \
1986 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
1987 "ECF677152EF804370C1A305CAF3B5BF1" \
1988 "30879B56C61DE584A0F53A2447A51E" ) );
1991 printf(
" MPI test #1 (mul_mpi): " );
1996 printf(
"failed\n" );
2002 printf(
"passed\n" );
2007 "256567336059E52CAE22925474705F39A94" ) );
2010 "6613F26162223DF488E9CD48CC132C7A" \
2011 "0AC93C701B001B092E4E5B9F73BCD27B" \
2012 "9EE50D0657C77F374E903CDFA4C642" ) );
2015 printf(
" MPI test #2 (div_mpi): " );
2021 printf(
"failed\n" );
2027 printf(
"passed\n" );
2032 "36E139AEA55215609D2816998ED020BB" \
2033 "BD96C37890F65171D948E9BC7CBAA4D9" \
2034 "325D24D6A3C12710F10A09FA08AB87" ) );
2037 printf(
" MPI test #3 (exp_mod): " );
2042 printf(
"failed\n" );
2048 printf(
"passed\n" );
2050 #if defined(POLARSSL_GENPRIME)
2054 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2055 "C3DBA76456363A10869622EAC2DD84EC" \
2056 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2059 printf(
" MPI test #4 (inv_mod): " );
2064 printf(
"failed\n" );
2070 printf(
"passed\n" );
2074 printf(
" MPI test #5 (simple gcd): " );
2076 for ( i = 0; i < GCD_PAIR_COUNT; i++)
2086 printf(
"failed at %d\n", i );
2093 printf(
"passed\n" );
2097 if( ret != 0 && verbose != 0 )
2098 printf(
"Unexpected error, return code = %08X\n", ret );