33 #if !defined(POLARSSL_CONFIG_FILE)
36 #include POLARSSL_CONFIG_FILE
39 #if defined(POLARSSL_BIGNUM_C)
44 #if defined(POLARSSL_PLATFORM_C)
47 #define polarssl_printf printf
48 #define polarssl_malloc malloc
49 #define polarssl_free free
55 static void polarssl_zeroize(
void *v,
size_t n ) {
56 volatile unsigned char *p = v;
while( n-- ) *p++ = 0;
59 #define ciL (sizeof(t_uint))
60 #define biL (ciL << 3)
61 #define biH (ciL << 2)
66 #define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL)
67 #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
92 polarssl_zeroize( X->
p, X->
n * ciL );
116 memset( p, 0, nblimbs * ciL );
120 memcpy( p, X->
p, X->
n * ciL );
121 polarssl_zeroize( X->
p, X->
n * ciL );
142 if( X->
n <= nblimbs )
145 for( i = X->
n - 1; i > 0; i-- )
156 memset( p, 0, i * ciL );
160 memcpy( p, X->
p, i * ciL );
161 polarssl_zeroize( X->
p, X->
n * ciL );
188 for( i = Y->
n - 1; i > 0; i-- )
197 memset( X->
p, 0, X->
n * ciL );
198 memcpy( X->
p, Y->
p, i * ciL );
212 memcpy( &T, X,
sizeof(
mpi ) );
213 memcpy( X, Y,
sizeof(
mpi ) );
214 memcpy( Y, &T,
sizeof(
mpi ) );
228 assign = ( assign != 0 );
232 X->
s = X->
s * ( 1 - assign ) + Y->
s * assign;
234 for( i = 0; i < Y->n; i++ )
235 X->
p[i] = X->
p[i] * ( 1 - assign ) + Y->
p[i] * assign;
237 for( ; i < X->n; i++ )
238 X->
p[i] *= ( 1 - assign );
260 swap = ( swap != 0 );
266 X->
s = X->
s * ( 1 - swap ) + Y->
s * swap;
267 Y->
s = Y->
s * ( 1 - swap ) + s * swap;
270 for( i = 0; i < X->
n; i++ )
273 X->
p[i] = X->
p[i] * ( 1 - swap ) + Y->
p[i] * swap;
274 Y->
p[i] = Y->
p[i] * ( 1 - swap ) + tmp * swap;
289 memset( X->
p, 0, X->
n * ciL );
291 X->
p[0] = ( z < 0 ) ? -z : z;
292 X->
s = ( z < 0 ) ? -1 : 1;
304 if( X->
n * biL <= pos )
307 return( ( X->
p[pos / biL] >> ( pos % biL ) ) & 0x01 );
316 size_t off = pos / biL;
317 size_t idx = pos % biL;
319 if( val != 0 && val != 1 )
322 if( X->
n * biL <= pos )
330 X->
p[off] &= ~( (
t_uint) 0x01 << idx );
331 X->
p[off] |= (
t_uint) val << idx;
343 size_t i, j, count = 0;
345 for( i = 0; i < X->
n; i++ )
346 for( j = 0; j < biL; j++, count++ )
347 if( ( ( X->
p[i] >> j ) & 1 ) != 0 )
360 for( i = X->
n - 1; i > 0; i-- )
364 for( j = biL; j > 0; j-- )
365 if( ( ( X->
p[i] >> ( j - 1 ) ) & 1 ) != 0 )
368 return( ( i * biL ) + j );
376 return( (
mpi_msb( X ) + 7 ) >> 3 );
382 static int mpi_get_digit(
t_uint *d,
int radix,
char c )
386 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
387 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
388 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
390 if( *d >= (
t_uint) radix )
402 size_t i, j, slen, n;
406 if( radix < 2 || radix > 16 )
415 n = BITS_TO_LIMBS( slen << 2 );
420 for( i = slen, j = 0; i > 0; i--, j++ )
422 if( i == 1 && s[i - 1] ==
'-' )
428 MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
429 X->
p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
436 for( i = 0; i < slen; i++ )
438 if( i == 0 && s[i] ==
'-' )
444 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
468 static int mpi_write_hlp(
mpi *X,
int radix,
char **p )
473 if( radix < 2 || radix > 16 )
480 MPI_CHK( mpi_write_hlp( X, radix, p ) );
483 *(*p)++ = (char)( r + 0x30 );
485 *(*p)++ = (char)( r + 0x37 );
502 if( radix < 2 || radix > 16 )
506 if( radix >= 4 ) n >>= 1;
507 if( radix >= 16 ) n >>= 1;
527 for( i = X->
n, k = 0; i > 0; i-- )
529 for( j = ciL; j > 0; j-- )
531 c = ( X->
p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
533 if( c == 0 && k == 0 && ( i + j ) != 2 )
536 *(p++) =
"0123456789ABCDEF" [c / 16];
537 *(p++) =
"0123456789ABCDEF" [c % 16];
549 MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
562 #if defined(POLARSSL_FS_IO)
577 memset( s, 0,
sizeof( s ) );
578 if( fgets( s,
sizeof( s ) - 1, fin ) == NULL )
582 if( slen ==
sizeof( s ) - 2 )
585 if( s[slen - 1] ==
'\n' ) { slen--; s[slen] =
'\0'; }
586 if( s[slen - 1] ==
'\r' ) { slen--; s[slen] =
'\0'; }
590 if( mpi_get_digit( &d, radix, *p ) != 0 )
602 size_t n, slen, plen;
615 if( p == NULL ) p =
"";
624 if( fwrite( p, 1, plen, fout ) != plen ||
625 fwrite( s, 1, slen, fout ) != slen )
645 for( n = 0; n < buflen; n++ )
652 for( i = buflen, j = 0; i > n; i--, j++ )
653 X->
p[j / ciL] |= ((
t_uint) buf[i - 1]) << ((j % ciL) << 3);
672 memset( buf, 0, buflen );
674 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
675 buf[i] = (
unsigned char)( X->
p[j / ciL] >> ((j % ciL) << 3) );
690 t1 = count & (biL - 1);
704 for( i = X->
n; i > v0; i-- )
705 X->
p[i - 1] = X->
p[i - v0 - 1];
716 for( i = v0; i < X->
n; i++ )
718 r1 = X->
p[i] >> (biL - t1);
739 v1 = count & (biL - 1);
741 if( v0 > X->
n || ( v0 == X->
n && v1 > 0 ) )
749 for( i = 0; i < X->
n - v0; i++ )
750 X->
p[i] = X->
p[i + v0];
752 for( ; i < X->n; i++ )
761 for( i = X->
n; i > 0; i-- )
763 r1 = X->
p[i - 1] << (biL - v1);
780 for( i = X->
n; i > 0; i-- )
781 if( X->
p[i - 1] != 0 )
784 for( j = Y->
n; j > 0; j-- )
785 if( Y->
p[j - 1] != 0 )
788 if( i == 0 && j == 0 )
791 if( i > j )
return( 1 );
792 if( j > i )
return( -1 );
796 if( X->
p[i - 1] > Y->
p[i - 1] )
return( 1 );
797 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -1 );
810 for( i = X->
n; i > 0; i-- )
811 if( X->
p[i - 1] != 0 )
814 for( j = Y->
n; j > 0; j-- )
815 if( Y->
p[j - 1] != 0 )
818 if( i == 0 && j == 0 )
821 if( i > j )
return( X->
s );
822 if( j > i )
return( -Y->
s );
824 if( X->
s > 0 && Y->
s < 0 )
return( 1 );
825 if( Y->
s > 0 && X->
s < 0 )
return( -1 );
829 if( X->
p[i - 1] > Y->
p[i - 1] )
return( X->
s );
830 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -X->
s );
844 *p = ( z < 0 ) ? -z : z;
845 Y.
s = ( z < 0 ) ? -1 : 1;
863 const mpi *T = A; A = X; B = T;
874 for( j = B->
n; j > 0; j-- )
875 if( B->
p[j - 1] != 0 )
880 o = B->
p; p = X->
p; c = 0;
882 for( i = 0; i < j; i++, o++, p++ )
884 *p += c; c = ( *p < c );
885 *p += *o; c += ( *p < *o );
896 *p += c; c = ( *p < c ); i++; p++;
907 static void mpi_sub_hlp(
size_t n,
t_uint *s,
t_uint *d )
912 for( i = c = 0; i < n; i++, s++, d++ )
914 z = ( *d < c ); *d -= c;
915 c = ( *d < *s ) + z; *d -= *s;
920 z = ( *d < c ); *d -= c;
955 for( n = B->
n; n > 0; n-- )
956 if( B->
p[n - 1] != 0 )
959 mpi_sub_hlp( n, B->
p, X->
p );
975 if( A->
s * B->
s < 0 )
1006 if( A->
s * B->
s > 0 )
1038 p[0] = ( b < 0 ) ? -b : b;
1039 _B.
s = ( b < 0 ) ? -1 : 1;
1054 p[0] = ( b < 0 ) ? -b : b;
1055 _B.
s = ( b < 0 ) ? -1 : 1;
1066 #if defined(__APPLE__) && defined(__arm__)
1071 __attribute__ ((noinline))
1077 #if defined(MULADDC_HUIT)
1078 for( ; i >= 8; i -= 8 )
1092 for( ; i >= 16; i -= 16 )
1107 for( ; i >= 8; i -= 8 )
1129 *d += c; c = ( *d < c ); d++;
1148 for( i = A->
n; i > 0; i-- )
1149 if( A->
p[i - 1] != 0 )
1152 for( j = B->
n; j > 0; j-- )
1153 if( B->
p[j - 1] != 0 )
1159 for( i++; j > 0; j-- )
1160 mpi_mul_hlp( i - 1, A->
p, X->
p + j - 1, B->
p[j - 1] );
1194 mpi X, Y, Z, T1, T2;
1238 for( i = n; i > t ; i-- )
1240 if( X.
p[i] >= Y.
p[t] )
1241 Z.
p[i - t - 1] = ~0;
1251 #if defined(POLARSSL_HAVE_UDBL) && \
1252 ! ( defined(__x86_64__) && defined(__APPLE__) && \
1253 defined(__clang_major__) && __clang_major__ == 5 && \
1254 defined(__clang_minor__) && __clang_minor__ == 0 )
1260 if( r > ( (
t_udbl) 1 << biL ) - 1 )
1261 r = ( (
t_udbl) 1 << biL ) - 1;
1272 d0 = ( d << biH ) >> biH;
1276 r1 = X.
p[i] - d1 * q1;
1278 r1 |= ( X.
p[i - 1] >> biH );
1284 while( r1 >= d && r1 < m )
1292 r0 |= ( X.
p[i - 1] << biH ) >> biH;
1298 while( r0 >= d && r0 < m )
1303 Z.
p[i - t - 1] = ( q1 << biH ) | q0;
1313 T1.
p[0] = ( t < 1 ) ? 0 : Y.
p[t - 1];
1318 T2.
p[0] = ( i < 2 ) ? 0 : X.
p[i - 2];
1319 T2.
p[1] = ( i < 1 ) ? 0 : X.
p[i - 1];
1369 p[0] = ( b < 0 ) ? -b : b;
1370 _B.
s = ( b < 0 ) ? -1 : 1;
1432 for( i = A->
n, y = 0; i > 0; i-- )
1435 y = ( y << biH ) | ( x >> biH );
1440 y = ( y << biH ) | ( x >> biH );
1449 if( A->
s < 0 && y != 0 )
1460 static void mpi_montg_init(
t_uint *mm,
const mpi *N )
1466 x += ( ( m0 + 2 ) & 4 ) << 1;
1468 for( i = biL; i >= 8; i /= 2 )
1469 x *= ( 2 - ( m0 * x ) );
1477 static void mpi_montmul(
mpi *A,
const mpi *B,
const mpi *N,
t_uint mm,
1483 memset( T->
p, 0, T->
n * ciL );
1487 m = ( B->
n < n ) ? B->
n : n;
1489 for( i = 0; i < n; i++ )
1495 u1 = ( d[0] + u0 * B->
p[0] ) * mm;
1497 mpi_mul_hlp( m, B->
p, d, u0 );
1498 mpi_mul_hlp( n, N->
p, d, u1 );
1500 *d++ = u0; d[n + 1] = 0;
1503 memcpy( A->
p, d, ( n + 1 ) * ciL );
1506 mpi_sub_hlp( n, N->
p, A->
p );
1509 mpi_sub_hlp( n, A->
p, T->
p );
1515 static void mpi_montred(
mpi *A,
const mpi *N,
t_uint mm,
const mpi *T )
1520 U.
n = U.
s = (int) z;
1523 mpi_montmul( A, &U, N, mm, T );
1532 size_t wbits, wsize, one = 1;
1533 size_t i, j, nblimbs;
1534 size_t bufsize, nbits;
1548 mpi_montg_init( &mm, N );
1551 memset( W, 0,
sizeof( W ) );
1555 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1556 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1569 neg = ( A->
s == -1 );
1580 if( _RR == NULL || _RR->
p == NULL )
1587 memcpy( _RR, &RR,
sizeof(
mpi ) );
1590 memcpy( &RR, _RR,
sizeof(
mpi ) );
1600 mpi_montmul( &W[1], &RR, N, mm, &T );
1606 mpi_montred( X, N, mm, &T );
1613 j = one << ( wsize - 1 );
1618 for( i = 0; i < wsize - 1; i++ )
1619 mpi_montmul( &W[j], &W[j], N, mm, &T );
1624 for( i = j + 1; i < ( one << wsize ); i++ )
1629 mpi_montmul( &W[i], &W[1], N, mm, &T );
1648 bufsize =
sizeof(
t_uint ) << 3;
1653 ei = (E->
p[nblimbs] >> bufsize) & 1;
1658 if( ei == 0 && state == 0 )
1661 if( ei == 0 && state == 1 )
1666 mpi_montmul( X, X, N, mm, &T );
1676 wbits |= ( ei << ( wsize - nbits ) );
1678 if( nbits == wsize )
1683 for( i = 0; i < wsize; i++ )
1684 mpi_montmul( X, X, N, mm, &T );
1689 mpi_montmul( X, &W[wbits], N, mm, &T );
1700 for( i = 0; i < nbits; i++ )
1702 mpi_montmul( X, X, N, mm, &T );
1706 if( ( wbits & ( one << wsize ) ) != 0 )
1707 mpi_montmul( X, &W[1], N, mm, &T );
1713 mpi_montred( X, N, mm, &T );
1723 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
1728 if( _RR == NULL || _RR->
p == NULL )
1794 int (*f_rng)(
void *,
unsigned char *,
size_t),
1803 MPI_CHK( f_rng( p_rng, buf, size ) );
1816 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1845 while( ( TU.
p[0] & 1 ) == 0 )
1849 if( ( U1.
p[0] & 1 ) != 0 || ( U2.
p[0] & 1 ) != 0 )
1859 while( ( TV.
p[0] & 1 ) == 0 )
1863 if( ( V1.
p[0] & 1 ) != 0 || ( V2.
p[0] & 1 ) != 0 )
1905 #if defined(POLARSSL_GENPRIME)
1907 static const int small_prime[] =
1909 3, 5, 7, 11, 13, 17, 19, 23,
1910 29, 31, 37, 41, 43, 47, 53, 59,
1911 61, 67, 71, 73, 79, 83, 89, 97,
1912 101, 103, 107, 109, 113, 127, 131, 137,
1913 139, 149, 151, 157, 163, 167, 173, 179,
1914 181, 191, 193, 197, 199, 211, 223, 227,
1915 229, 233, 239, 241, 251, 257, 263, 269,
1916 271, 277, 281, 283, 293, 307, 311, 313,
1917 317, 331, 337, 347, 349, 353, 359, 367,
1918 373, 379, 383, 389, 397, 401, 409, 419,
1919 421, 431, 433, 439, 443, 449, 457, 461,
1920 463, 467, 479, 487, 491, 499, 503, 509,
1921 521, 523, 541, 547, 557, 563, 569, 571,
1922 577, 587, 593, 599, 601, 607, 613, 617,
1923 619, 631, 641, 643, 647, 653, 659, 661,
1924 673, 677, 683, 691, 701, 709, 719, 727,
1925 733, 739, 743, 751, 757, 761, 769, 773,
1926 787, 797, 809, 811, 821, 823, 827, 829,
1927 839, 853, 857, 859, 863, 877, 881, 883,
1928 887, 907, 911, 919, 929, 937, 941, 947,
1929 953, 967, 971, 977, 983, 991, 997, -103
1941 static int mpi_check_small_factors(
const mpi *X )
1947 if( ( X->
p[0] & 1 ) == 0 )
1950 for( i = 0; small_prime[i] > 0; i++ )
1968 static int mpi_miller_rabin(
const mpi *X,
1969 int (*f_rng)(
void *,
unsigned char *,
size_t),
1992 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1993 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1994 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1996 for( i = 0; i < n; i++ )
2056 int (*f_rng)(
void *,
unsigned char *,
size_t),
2060 const mpi XX = { 1, X->
n, X->
p };
2069 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2077 return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
2084 int (*f_rng)(
void *,
unsigned char *,
size_t),
2097 n = BITS_TO_LIMBS( nbits );
2109 while( ( ret =
mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
2140 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2141 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
2142 ( ret = mpi_miller_rabin( X, f_rng, p_rng ) ) == 0 &&
2143 ( ret = mpi_miller_rabin( &Y, f_rng, p_rng ) ) == 0 )
2170 #if defined(POLARSSL_SELF_TEST)
2172 #define GCD_PAIR_COUNT 3
2174 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2178 { 768454923, 542167814, 1 }
2187 mpi A, E, N, X, Y, U, V;
2193 "EFE021C2645FD1DC586E69184AF4A31E" \
2194 "D5F53E93B5F123FA41680867BA110131" \
2195 "944FE7952E2517337780CB0DB80E61AA" \
2196 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2199 "B2E7EFD37075B9F03FF989C7C5051C20" \
2200 "34D2A323810251127E7BF8625A4F49A5" \
2201 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2202 "5B5C25763222FEFCCFC38B832366C29E" ) );
2205 "0066A198186C18C10B2F5ED9B522752A" \
2206 "9830B69916E535C8F047518A889A43A5" \
2207 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2212 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2213 "9E857EA95A03512E2BAE7391688D264A" \
2214 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2215 "8001B72E848A38CAE1C65F78E56ABDEF" \
2216 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2217 "ECF677152EF804370C1A305CAF3B5BF1" \
2218 "30879B56C61DE584A0F53A2447A51E" ) );
2238 "256567336059E52CAE22925474705F39A94" ) );
2241 "6613F26162223DF488E9CD48CC132C7A" \
2242 "0AC93C701B001B092E4E5B9F73BCD27B" \
2243 "9EE50D0657C77F374E903CDFA4C642" ) );
2264 "36E139AEA55215609D2816998ED020BB" \
2265 "BD96C37890F65171D948E9BC7CBAA4D9" \
2266 "325D24D6A3C12710F10A09FA08AB87" ) );
2286 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2287 "C3DBA76456363A10869622EAC2DD84EC" \
2288 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2308 for( i = 0; i < GCD_PAIR_COUNT; i++ )
2330 if( ret != 0 && verbose != 0 )