35 #if defined(POLARSSL_BIGNUM_C)
40 #if defined(POLARSSL_MEMORY_C)
43 #define polarssl_malloc malloc
44 #define polarssl_free free
49 #define ciL (sizeof(t_uint))
50 #define biL (ciL << 3)
51 #define biH (ciL << 2)
56 #define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL)
57 #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
82 memset( X->
p, 0, X->
n * ciL );
106 memset( p, 0, nblimbs * ciL );
110 memcpy( p, X->
p, X->
n * ciL );
111 memset( X->
p, 0, X->
n * ciL );
139 for( i = Y->
n - 1; i > 0; i-- )
148 memset( X->
p, 0, X->
n * ciL );
149 memcpy( X->
p, Y->
p, i * ciL );
163 memcpy( &T, X,
sizeof(
mpi ) );
164 memcpy( X, Y,
sizeof(
mpi ) );
165 memcpy( Y, &T,
sizeof(
mpi ) );
176 memset( X->
p, 0, X->
n * ciL );
178 X->
p[0] = ( z < 0 ) ? -z : z;
179 X->
s = ( z < 0 ) ? -1 : 1;
191 if( X->
n * biL <= pos )
194 return ( X->
p[pos / biL] >> ( pos % biL ) ) & 0x01;
203 size_t off = pos / biL;
204 size_t idx = pos % biL;
206 if( val != 0 && val != 1 )
209 if( X->
n * biL <= pos )
217 X->
p[off] = ( X->
p[off] & ~( 0x01 << idx ) ) | ( val << idx );
229 size_t i, j, count = 0;
231 for( i = 0; i < X->
n; i++ )
232 for( j = 0; j < biL; j++, count++ )
233 if( ( ( X->
p[i] >> j ) & 1 ) != 0 )
246 for( i = X->
n - 1; i > 0; i-- )
250 for( j = biL; j > 0; j-- )
251 if( ( ( X->
p[i] >> ( j - 1 ) ) & 1 ) != 0 )
254 return( ( i * biL ) + j );
262 return( (
mpi_msb( X ) + 7 ) >> 3 );
268 static int mpi_get_digit(
t_uint *d,
int radix,
char c )
272 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
273 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
274 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
276 if( *d >= (
t_uint) radix )
288 size_t i, j, slen, n;
292 if( radix < 2 || radix > 16 )
301 n = BITS_TO_LIMBS( slen << 2 );
306 for( i = slen, j = 0; i > 0; i--, j++ )
308 if( i == 1 && s[i - 1] ==
'-' )
314 MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
315 X->
p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 );
322 for( i = 0; i < slen; i++ )
324 if( i == 0 && s[i] ==
'-' )
330 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
354 static int mpi_write_hlp(
mpi *X,
int radix,
char **p )
359 if( radix < 2 || radix > 16 )
366 MPI_CHK( mpi_write_hlp( X, radix, p ) );
369 *(*p)++ = (char)( r + 0x30 );
371 *(*p)++ = (char)( r + 0x37 );
388 if( radix < 2 || radix > 16 )
392 if( radix >= 4 ) n >>= 1;
393 if( radix >= 16 ) n >>= 1;
413 for( i = X->
n, k = 0; i > 0; i-- )
415 for( j = ciL; j > 0; j-- )
417 c = ( X->
p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
419 if( c == 0 && k == 0 && ( i + j + 3 ) != 0 )
422 *(p++) =
"0123456789ABCDEF" [c / 16];
423 *(p++) =
"0123456789ABCDEF" [c % 16];
435 MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
448 #if defined(POLARSSL_FS_IO)
463 memset( s, 0,
sizeof( s ) );
464 if( fgets( s,
sizeof( s ) - 1, fin ) == NULL )
468 if( slen ==
sizeof( s ) - 2 )
471 if( s[slen - 1] ==
'\n' ) { slen--; s[slen] =
'\0'; }
472 if( s[slen - 1] ==
'\r' ) { slen--; s[slen] =
'\0'; }
476 if( mpi_get_digit( &d, radix, *p ) != 0 )
488 size_t n, slen, plen;
501 if( p == NULL ) p =
"";
510 if( fwrite( p, 1, plen, fout ) != plen ||
511 fwrite( s, 1, slen, fout ) != slen )
515 printf(
"%s%s", p, s );
531 for( n = 0; n < buflen; n++ )
538 for( i = buflen, j = 0; i > n; i--, j++ )
539 X->
p[j / ciL] |= ((
t_uint) buf[i - 1]) << ((j % ciL) << 3);
558 memset( buf, 0, buflen );
560 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
561 buf[i] = (
unsigned char)( X->
p[j / ciL] >> ((j % ciL) << 3) );
576 t1 = count & (biL - 1);
590 for( i = X->
n; i > v0; i-- )
591 X->
p[i - 1] = X->
p[i - v0 - 1];
602 for( i = v0; i < X->
n; i++ )
604 r1 = X->
p[i] >> (biL - t1);
625 v1 = count & (biL - 1);
627 if( v0 > X->
n || ( v0 == X->
n && v1 > 0 ) )
635 for( i = 0; i < X->
n - v0; i++ )
636 X->
p[i] = X->
p[i + v0];
638 for( ; i < X->n; i++ )
647 for( i = X->
n; i > 0; i-- )
649 r1 = X->
p[i - 1] << (biL - v1);
666 for( i = X->
n; i > 0; i-- )
667 if( X->
p[i - 1] != 0 )
670 for( j = Y->
n; j > 0; j-- )
671 if( Y->
p[j - 1] != 0 )
674 if( i == 0 && j == 0 )
677 if( i > j )
return( 1 );
678 if( j > i )
return( -1 );
682 if( X->
p[i - 1] > Y->
p[i - 1] )
return( 1 );
683 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -1 );
696 for( i = X->
n; i > 0; i-- )
697 if( X->
p[i - 1] != 0 )
700 for( j = Y->
n; j > 0; j-- )
701 if( Y->
p[j - 1] != 0 )
704 if( i == 0 && j == 0 )
707 if( i > j )
return( X->
s );
708 if( j > i )
return( -Y->
s );
710 if( X->
s > 0 && Y->
s < 0 )
return( 1 );
711 if( Y->
s > 0 && X->
s < 0 )
return( -1 );
715 if( X->
p[i - 1] > Y->
p[i - 1] )
return( X->
s );
716 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -X->
s );
730 *p = ( z < 0 ) ? -z : z;
731 Y.
s = ( z < 0 ) ? -1 : 1;
749 const mpi *T = A; A = X; B = T;
760 for( j = B->
n; j > 0; j-- )
761 if( B->
p[j - 1] != 0 )
766 o = B->
p; p = X->
p; c = 0;
768 for( i = 0; i < j; i++, o++, p++ )
770 *p += c; c = ( *p < c );
771 *p += *o; c += ( *p < *o );
782 *p += c; c = ( *p < c ); i++; p++;
793 static void mpi_sub_hlp(
size_t n,
t_uint *s,
t_uint *d )
798 for( i = c = 0; i < n; i++, s++, d++ )
800 z = ( *d < c ); *d -= c;
801 c = ( *d < *s ) + z; *d -= *s;
806 z = ( *d < c ); *d -= c;
841 for( n = B->
n; n > 0; n-- )
842 if( B->
p[n - 1] != 0 )
845 mpi_sub_hlp( n, B->
p, X->
p );
861 if( A->
s * B->
s < 0 )
892 if( A->
s * B->
s > 0 )
924 p[0] = ( b < 0 ) ? -b : b;
925 _B.
s = ( b < 0 ) ? -1 : 1;
940 p[0] = ( b < 0 ) ? -b : b;
941 _B.
s = ( b < 0 ) ? -1 : 1;
952 #if defined(__APPLE__) && defined(__arm__)
957 __attribute__ ((noinline))
963 #if defined(MULADDC_HUIT)
964 for( ; i >= 8; i -= 8 )
978 for( ; i >= 16; i -= 16 )
993 for( ; i >= 8; i -= 8 )
1015 *d += c; c = ( *d < c ); d++;
1034 for( i = A->
n; i > 0; i-- )
1035 if( A->
p[i - 1] != 0 )
1038 for( j = B->
n; j > 0; j-- )
1039 if( B->
p[j - 1] != 0 )
1045 for( i++; j > 0; j-- )
1046 mpi_mul_hlp( i - 1, A->
p, X->
p + j - 1, B->
p[j - 1] );
1080 mpi X, Y, Z, T1, T2;
1124 for( i = n; i > t ; i-- )
1126 if( X.
p[i] >= Y.
p[t] )
1127 Z.
p[i - t - 1] = ~0;
1130 #if defined(POLARSSL_HAVE_UDBL)
1136 if( r > ((
t_udbl) 1 << biL) - 1)
1137 r = ((
t_udbl) 1 << biL) - 1;
1148 d0 = ( d << biH ) >> biH;
1152 r1 = X.
p[i] - d1 * q1;
1154 r1 |= ( X.
p[i - 1] >> biH );
1160 while( r1 >= d && r1 < m )
1168 r0 |= ( X.
p[i - 1] << biH ) >> biH;
1174 while( r0 >= d && r0 < m )
1179 Z.
p[i - t - 1] = ( q1 << biH ) | q0;
1189 T1.
p[0] = (t < 1) ? 0 : Y.
p[t - 1];
1194 T2.
p[0] = (i < 2) ? 0 : X.
p[i - 2];
1195 T2.
p[1] = (i < 1) ? 0 : X.
p[i - 1];
1245 p[0] = ( b < 0 ) ? -b : b;
1246 _B.
s = ( b < 0 ) ? -1 : 1;
1308 for( i = A->
n, y = 0; i > 0; i-- )
1311 y = ( y << biH ) | ( x >> biH );
1316 y = ( y << biH ) | ( x >> biH );
1325 if( A->
s < 0 && y != 0 )
1336 static void mpi_montg_init(
t_uint *mm,
const mpi *N )
1341 x += ( ( m0 + 2 ) & 4 ) << 1;
1342 x *= ( 2 - ( m0 * x ) );
1344 if( biL >= 16 ) x *= ( 2 - ( m0 * x ) );
1345 if( biL >= 32 ) x *= ( 2 - ( m0 * x ) );
1346 if( biL >= 64 ) x *= ( 2 - ( m0 * x ) );
1354 static void mpi_montmul(
mpi *A,
const mpi *B,
const mpi *N,
t_uint mm,
const mpi *T )
1359 memset( T->
p, 0, T->
n * ciL );
1363 m = ( B->
n < n ) ? B->
n : n;
1365 for( i = 0; i < n; i++ )
1371 u1 = ( d[0] + u0 * B->
p[0] ) * mm;
1373 mpi_mul_hlp( m, B->
p, d, u0 );
1374 mpi_mul_hlp( n, N->
p, d, u1 );
1376 *d++ = u0; d[n + 1] = 0;
1379 memcpy( A->
p, d, (n + 1) * ciL );
1382 mpi_sub_hlp( n, N->
p, A->
p );
1385 mpi_sub_hlp( n, A->
p, T->
p );
1391 static void mpi_montred(
mpi *A,
const mpi *N,
t_uint mm,
const mpi *T )
1396 U.
n = U.
s = (int) z;
1399 mpi_montmul( A, &U, N, mm, T );
1408 size_t wbits, wsize, one = 1;
1409 size_t i, j, nblimbs;
1410 size_t bufsize, nbits;
1424 mpi_montg_init( &mm, N );
1426 memset( W, 0,
sizeof( W ) );
1430 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1431 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1444 neg = ( A->
s == -1 );
1457 if( _RR == NULL || _RR->
p == NULL )
1464 memcpy( _RR, &RR,
sizeof(
mpi ) );
1467 memcpy( &RR, _RR,
sizeof(
mpi ) );
1476 mpi_montmul( &W[1], &RR, N, mm, &T );
1482 mpi_montred( X, N, mm, &T );
1489 j = one << (wsize - 1);
1494 for( i = 0; i < wsize - 1; i++ )
1495 mpi_montmul( &W[j], &W[j], N, mm, &T );
1500 for( i = j + 1; i < (one << wsize); i++ )
1505 mpi_montmul( &W[i], &W[1], N, mm, &T );
1519 if( nblimbs-- == 0 )
1522 bufsize =
sizeof(
t_uint ) << 3;
1527 ei = (E->
p[nblimbs] >> bufsize) & 1;
1532 if( ei == 0 && state == 0 )
1535 if( ei == 0 && state == 1 )
1540 mpi_montmul( X, X, N, mm, &T );
1550 wbits |= (ei << (wsize - nbits));
1552 if( nbits == wsize )
1557 for( i = 0; i < wsize; i++ )
1558 mpi_montmul( X, X, N, mm, &T );
1563 mpi_montmul( X, &W[wbits], N, mm, &T );
1574 for( i = 0; i < nbits; i++ )
1576 mpi_montmul( X, X, N, mm, &T );
1580 if( (wbits & (one << wsize)) != 0 )
1581 mpi_montmul( X, &W[1], N, mm, &T );
1587 mpi_montred( X, N, mm, &T );
1597 for( i = (one << (wsize - 1)); i < (one << wsize); i++ )
1661 int (*f_rng)(
void *,
unsigned char *,
size_t),
1669 MPI_CHK( f_rng( p_rng, (
unsigned char *) X->
p, size ) );
1681 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1710 while( ( TU.
p[0] & 1 ) == 0 )
1714 if( ( U1.
p[0] & 1 ) != 0 || ( U2.
p[0] & 1 ) != 0 )
1724 while( ( TV.
p[0] & 1 ) == 0 )
1728 if( ( V1.
p[0] & 1 ) != 0 || ( V2.
p[0] & 1 ) != 0 )
1770 #if defined(POLARSSL_GENPRIME)
1772 static const int small_prime[] =
1774 3, 5, 7, 11, 13, 17, 19, 23,
1775 29, 31, 37, 41, 43, 47, 53, 59,
1776 61, 67, 71, 73, 79, 83, 89, 97,
1777 101, 103, 107, 109, 113, 127, 131, 137,
1778 139, 149, 151, 157, 163, 167, 173, 179,
1779 181, 191, 193, 197, 199, 211, 223, 227,
1780 229, 233, 239, 241, 251, 257, 263, 269,
1781 271, 277, 281, 283, 293, 307, 311, 313,
1782 317, 331, 337, 347, 349, 353, 359, 367,
1783 373, 379, 383, 389, 397, 401, 409, 419,
1784 421, 431, 433, 439, 443, 449, 457, 461,
1785 463, 467, 479, 487, 491, 499, 503, 509,
1786 521, 523, 541, 547, 557, 563, 569, 571,
1787 577, 587, 593, 599, 601, 607, 613, 617,
1788 619, 631, 641, 643, 647, 653, 659, 661,
1789 673, 677, 683, 691, 701, 709, 719, 727,
1790 733, 739, 743, 751, 757, 761, 769, 773,
1791 787, 797, 809, 811, 821, 823, 827, 829,
1792 839, 853, 857, 859, 863, 877, 881, 883,
1793 887, 907, 911, 919, 929, 937, 941, 947,
1794 953, 967, 971, 977, 983, 991, 997, -103
1801 int (*f_rng)(
void *,
unsigned char *,
size_t),
1818 xs = X->
s; X->
s = 1;
1823 if( ( X->
p[0] & 1 ) == 0 )
1826 for( i = 0; small_prime[i] > 0; i++ )
1852 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1853 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1854 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1856 for( i = 0; i < n; i++ )
1919 int (*f_rng)(
void *,
unsigned char *,
size_t),
1931 n = BITS_TO_LIMBS( nbits );
1943 while( ( ret =
mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
1985 #if defined(POLARSSL_SELF_TEST)
1987 #define GCD_PAIR_COUNT 3
1989 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
1993 { 768454923, 542167814, 1 }
2002 mpi A, E, N, X, Y, U, V;
2008 "EFE021C2645FD1DC586E69184AF4A31E" \
2009 "D5F53E93B5F123FA41680867BA110131" \
2010 "944FE7952E2517337780CB0DB80E61AA" \
2011 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2014 "B2E7EFD37075B9F03FF989C7C5051C20" \
2015 "34D2A323810251127E7BF8625A4F49A5" \
2016 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2017 "5B5C25763222FEFCCFC38B832366C29E" ) );
2020 "0066A198186C18C10B2F5ED9B522752A" \
2021 "9830B69916E535C8F047518A889A43A5" \
2022 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2027 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2028 "9E857EA95A03512E2BAE7391688D264A" \
2029 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2030 "8001B72E848A38CAE1C65F78E56ABDEF" \
2031 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2032 "ECF677152EF804370C1A305CAF3B5BF1" \
2033 "30879B56C61DE584A0F53A2447A51E" ) );
2036 printf(
" MPI test #1 (mul_mpi): " );
2041 printf(
"failed\n" );
2047 printf(
"passed\n" );
2052 "256567336059E52CAE22925474705F39A94" ) );
2055 "6613F26162223DF488E9CD48CC132C7A" \
2056 "0AC93C701B001B092E4E5B9F73BCD27B" \
2057 "9EE50D0657C77F374E903CDFA4C642" ) );
2060 printf(
" MPI test #2 (div_mpi): " );
2066 printf(
"failed\n" );
2072 printf(
"passed\n" );
2077 "36E139AEA55215609D2816998ED020BB" \
2078 "BD96C37890F65171D948E9BC7CBAA4D9" \
2079 "325D24D6A3C12710F10A09FA08AB87" ) );
2082 printf(
" MPI test #3 (exp_mod): " );
2087 printf(
"failed\n" );
2093 printf(
"passed\n" );
2098 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2099 "C3DBA76456363A10869622EAC2DD84EC" \
2100 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2103 printf(
" MPI test #4 (inv_mod): " );
2108 printf(
"failed\n" );
2114 printf(
"passed\n" );
2117 printf(
" MPI test #5 (simple gcd): " );
2119 for ( i = 0; i < GCD_PAIR_COUNT; i++)
2129 printf(
"failed at %d\n", i );
2136 printf(
"passed\n" );
2140 if( ret != 0 && verbose != 0 )
2141 printf(
"Unexpected error, return code = %08X\n", ret );