35 #if defined(POLARSSL_BIGNUM_C)
43 static void polarssl_zeroize(
void *v,
size_t n ) {
44 volatile unsigned char *p = v;
while( n-- ) *p++ = 0;
47 #define ciL (sizeof(t_uint))
48 #define biL (ciL << 3)
49 #define biH (ciL << 2)
54 #define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL)
55 #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
80 polarssl_zeroize( X->
p, X->
n * ciL );
101 if( ( p = (
t_uint *) malloc( nblimbs * ciL ) ) == NULL )
104 memset( p, 0, nblimbs * ciL );
108 memcpy( p, X->
p, X->
n * ciL );
109 polarssl_zeroize( X->
p, X->
n * ciL );
131 for( i = Y->
n - 1; i > 0; i-- )
140 memset( X->
p, 0, X->
n * ciL );
141 memcpy( X->
p, Y->
p, i * ciL );
155 memcpy( &T, X,
sizeof(
mpi ) );
156 memcpy( X, Y,
sizeof(
mpi ) );
157 memcpy( Y, &T,
sizeof(
mpi ) );
168 memset( X->
p, 0, X->
n * ciL );
170 X->
p[0] = ( z < 0 ) ? -z : z;
171 X->
s = ( z < 0 ) ? -1 : 1;
183 if( X->
n * biL <= pos )
186 return ( X->
p[pos / biL] >> ( pos % biL ) ) & 0x01;
195 size_t off = pos / biL;
196 size_t idx = pos % biL;
198 if( val != 0 && val != 1 )
201 if( X->
n * biL <= pos )
209 X->
p[off] = ( X->
p[off] & ~( 0x01 << idx ) ) | ( val << idx );
221 size_t i, j, count = 0;
223 for( i = 0; i < X->
n; i++ )
224 for( j = 0; j < biL; j++, count++ )
225 if( ( ( X->
p[i] >> j ) & 1 ) != 0 )
238 for( i = X->
n - 1; i > 0; i-- )
242 for( j = biL; j > 0; j-- )
243 if( ( ( X->
p[i] >> ( j - 1 ) ) & 1 ) != 0 )
246 return( ( i * biL ) + j );
254 return( (
mpi_msb( X ) + 7 ) >> 3 );
260 static int mpi_get_digit(
t_uint *d,
int radix,
char c )
264 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
265 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
266 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
268 if( *d >= (
t_uint) radix )
280 size_t i, j, slen, n;
284 if( radix < 2 || radix > 16 )
293 n = BITS_TO_LIMBS( slen << 2 );
298 for( i = slen, j = 0; i > 0; i--, j++ )
300 if( i == 1 && s[i - 1] ==
'-' )
306 MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
307 X->
p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 );
314 for( i = 0; i < slen; i++ )
316 if( i == 0 && s[i] ==
'-' )
322 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
346 static int mpi_write_hlp(
mpi *X,
int radix,
char **p )
351 if( radix < 2 || radix > 16 )
358 MPI_CHK( mpi_write_hlp( X, radix, p ) );
361 *(*p)++ = (char)( r + 0x30 );
363 *(*p)++ = (char)( r + 0x37 );
380 if( radix < 2 || radix > 16 )
384 if( radix >= 4 ) n >>= 1;
385 if( radix >= 16 ) n >>= 1;
405 for( i = X->
n, k = 0; i > 0; i-- )
407 for( j = ciL; j > 0; j-- )
409 c = ( X->
p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
411 if( c == 0 && k == 0 && ( i + j + 3 ) != 0 )
414 *(p++) =
"0123456789ABCDEF" [c / 16];
415 *(p++) =
"0123456789ABCDEF" [c % 16];
427 MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
440 #if defined(POLARSSL_FS_IO)
455 memset( s, 0,
sizeof( s ) );
456 if( fgets( s,
sizeof( s ) - 1, fin ) == NULL )
460 if( slen ==
sizeof( s ) - 2 )
463 if( s[slen - 1] ==
'\n' ) { slen--; s[slen] =
'\0'; }
464 if( s[slen - 1] ==
'\r' ) { slen--; s[slen] =
'\0'; }
468 if( mpi_get_digit( &d, radix, *p ) != 0 )
480 size_t n, slen, plen;
493 if( p == NULL ) p =
"";
502 if( fwrite( p, 1, plen, fout ) != plen ||
503 fwrite( s, 1, slen, fout ) != slen )
507 printf(
"%s%s", p, s );
523 for( n = 0; n < buflen; n++ )
530 for( i = buflen, j = 0; i > n; i--, j++ )
531 X->
p[j / ciL] |= ((
t_uint) buf[i - 1]) << ((j % ciL) << 3);
550 memset( buf, 0, buflen );
552 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
553 buf[i] = (
unsigned char)( X->
p[j / ciL] >> ((j % ciL) << 3) );
568 t1 = count & (biL - 1);
582 for( i = X->
n; i > v0; i-- )
583 X->
p[i - 1] = X->
p[i - v0 - 1];
594 for( i = v0; i < X->
n; i++ )
596 r1 = X->
p[i] >> (biL - t1);
617 v1 = count & (biL - 1);
619 if( v0 > X->
n || ( v0 == X->
n && v1 > 0 ) )
627 for( i = 0; i < X->
n - v0; i++ )
628 X->
p[i] = X->
p[i + v0];
630 for( ; i < X->n; i++ )
639 for( i = X->
n; i > 0; i-- )
641 r1 = X->
p[i - 1] << (biL - v1);
658 for( i = X->
n; i > 0; i-- )
659 if( X->
p[i - 1] != 0 )
662 for( j = Y->
n; j > 0; j-- )
663 if( Y->
p[j - 1] != 0 )
666 if( i == 0 && j == 0 )
669 if( i > j )
return( 1 );
670 if( j > i )
return( -1 );
674 if( X->
p[i - 1] > Y->
p[i - 1] )
return( 1 );
675 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -1 );
688 for( i = X->
n; i > 0; i-- )
689 if( X->
p[i - 1] != 0 )
692 for( j = Y->
n; j > 0; j-- )
693 if( Y->
p[j - 1] != 0 )
696 if( i == 0 && j == 0 )
699 if( i > j )
return( X->
s );
700 if( j > i )
return( -Y->
s );
702 if( X->
s > 0 && Y->
s < 0 )
return( 1 );
703 if( Y->
s > 0 && X->
s < 0 )
return( -1 );
707 if( X->
p[i - 1] > Y->
p[i - 1] )
return( X->
s );
708 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -X->
s );
722 *p = ( z < 0 ) ? -z : z;
723 Y.
s = ( z < 0 ) ? -1 : 1;
741 const mpi *T = A; A = X; B = T;
752 for( j = B->
n; j > 0; j-- )
753 if( B->
p[j - 1] != 0 )
758 o = B->
p; p = X->
p; c = 0;
760 for( i = 0; i < j; i++, o++, p++ )
762 *p += c; c = ( *p < c );
763 *p += *o; c += ( *p < *o );
774 *p += c; c = ( *p < c ); i++; p++;
785 static void mpi_sub_hlp(
size_t n,
t_uint *s,
t_uint *d )
790 for( i = c = 0; i < n; i++, s++, d++ )
792 z = ( *d < c ); *d -= c;
793 c = ( *d < *s ) + z; *d -= *s;
798 z = ( *d < c ); *d -= c;
833 for( n = B->
n; n > 0; n-- )
834 if( B->
p[n - 1] != 0 )
837 mpi_sub_hlp( n, B->
p, X->
p );
853 if( A->
s * B->
s < 0 )
884 if( A->
s * B->
s > 0 )
916 p[0] = ( b < 0 ) ? -b : b;
917 _B.
s = ( b < 0 ) ? -1 : 1;
932 p[0] = ( b < 0 ) ? -b : b;
933 _B.
s = ( b < 0 ) ? -1 : 1;
944 #if defined(__APPLE__) && defined(__arm__)
949 __attribute__ ((noinline))
955 #if defined(MULADDC_HUIT)
956 for( ; i >= 8; i -= 8 )
970 for( ; i >= 16; i -= 16 )
985 for( ; i >= 8; i -= 8 )
1007 *d += c; c = ( *d < c ); d++;
1026 for( i = A->
n; i > 0; i-- )
1027 if( A->
p[i - 1] != 0 )
1030 for( j = B->
n; j > 0; j-- )
1031 if( B->
p[j - 1] != 0 )
1037 for( i++; j > 0; j-- )
1038 mpi_mul_hlp( i - 1, A->
p, X->
p + j - 1, B->
p[j - 1] );
1072 mpi X, Y, Z, T1, T2;
1116 for( i = n; i > t ; i-- )
1118 if( X.
p[i] >= Y.
p[t] )
1119 Z.
p[i - t - 1] = ~0;
1129 #if defined(POLARSSL_HAVE_UDBL) && \
1130 ! ( defined(__x86_64__) && defined(__APPLE__) && \
1131 defined(__clang_major__) && __clang_major__ == 5 && \
1132 defined(__clang_minor__) && __clang_minor__ == 0 )
1138 if( r > ((
t_udbl) 1 << biL) - 1)
1139 r = ((
t_udbl) 1 << biL) - 1;
1150 d0 = ( d << biH ) >> biH;
1154 r1 = X.
p[i] - d1 * q1;
1156 r1 |= ( X.
p[i - 1] >> biH );
1162 while( r1 >= d && r1 < m )
1170 r0 |= ( X.
p[i - 1] << biH ) >> biH;
1176 while( r0 >= d && r0 < m )
1181 Z.
p[i - t - 1] = ( q1 << biH ) | q0;
1191 T1.
p[0] = (t < 1) ? 0 : Y.
p[t - 1];
1196 T2.
p[0] = (i < 2) ? 0 : X.
p[i - 2];
1197 T2.
p[1] = (i < 1) ? 0 : X.
p[i - 1];
1247 p[0] = ( b < 0 ) ? -b : b;
1248 _B.
s = ( b < 0 ) ? -1 : 1;
1310 for( i = A->
n, y = 0; i > 0; i-- )
1313 y = ( y << biH ) | ( x >> biH );
1318 y = ( y << biH ) | ( x >> biH );
1327 if( A->
s < 0 && y != 0 )
1338 static void mpi_montg_init(
t_uint *mm,
const mpi *N )
1344 x += ( ( m0 + 2 ) & 4 ) << 1;
1346 for( i = biL; i >= 8; i /= 2 )
1347 x *= ( 2 - ( m0 * x ) );
1355 static void mpi_montmul(
mpi *A,
const mpi *B,
const mpi *N,
t_uint mm,
const mpi *T )
1360 memset( T->
p, 0, T->
n * ciL );
1364 m = ( B->
n < n ) ? B->
n : n;
1366 for( i = 0; i < n; i++ )
1372 u1 = ( d[0] + u0 * B->
p[0] ) * mm;
1374 mpi_mul_hlp( m, B->
p, d, u0 );
1375 mpi_mul_hlp( n, N->
p, d, u1 );
1377 *d++ = u0; d[n + 1] = 0;
1380 memcpy( A->
p, d, (n + 1) * ciL );
1383 mpi_sub_hlp( n, N->
p, A->
p );
1386 mpi_sub_hlp( n, A->
p, T->
p );
1392 static void mpi_montred(
mpi *A,
const mpi *N,
t_uint mm,
const mpi *T )
1397 U.
n = U.
s = (int) z;
1400 mpi_montmul( A, &U, N, mm, T );
1409 size_t wbits, wsize, one = 1;
1410 size_t i, j, nblimbs;
1411 size_t bufsize, nbits;
1425 mpi_montg_init( &mm, N );
1428 memset( W, 0,
sizeof( W ) );
1432 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1433 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1446 neg = ( A->
s == -1 );
1457 if( _RR == NULL || _RR->
p == NULL )
1464 memcpy( _RR, &RR,
sizeof(
mpi ) );
1467 memcpy( &RR, _RR,
sizeof(
mpi ) );
1479 mpi_montmul( &W[1], &RR, N, mm, &T );
1485 mpi_montred( X, N, mm, &T );
1492 j = one << (wsize - 1);
1497 for( i = 0; i < wsize - 1; i++ )
1498 mpi_montmul( &W[j], &W[j], N, mm, &T );
1503 for( i = j + 1; i < (one << wsize); i++ )
1508 mpi_montmul( &W[i], &W[1], N, mm, &T );
1527 bufsize =
sizeof(
t_uint ) << 3;
1532 ei = (E->
p[nblimbs] >> bufsize) & 1;
1537 if( ei == 0 && state == 0 )
1540 if( ei == 0 && state == 1 )
1545 mpi_montmul( X, X, N, mm, &T );
1555 wbits |= (ei << (wsize - nbits));
1557 if( nbits == wsize )
1562 for( i = 0; i < wsize; i++ )
1563 mpi_montmul( X, X, N, mm, &T );
1568 mpi_montmul( X, &W[wbits], N, mm, &T );
1579 for( i = 0; i < nbits; i++ )
1581 mpi_montmul( X, X, N, mm, &T );
1585 if( (wbits & (one << wsize)) != 0 )
1586 mpi_montmul( X, &W[1], N, mm, &T );
1592 mpi_montred( X, N, mm, &T );
1602 for( i = (one << (wsize - 1)); i < (one << wsize); i++ )
1607 if( _RR == NULL || _RR->
p == NULL )
1673 int (*f_rng)(
void *,
unsigned char *,
size_t),
1685 MPI_CHK( f_rng( p_rng, buf, size ) );
1698 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1727 while( ( TU.
p[0] & 1 ) == 0 )
1731 if( ( U1.
p[0] & 1 ) != 0 || ( U2.
p[0] & 1 ) != 0 )
1741 while( ( TV.
p[0] & 1 ) == 0 )
1745 if( ( V1.
p[0] & 1 ) != 0 || ( V2.
p[0] & 1 ) != 0 )
1787 #if defined(POLARSSL_GENPRIME)
1789 static const int small_prime[] =
1791 3, 5, 7, 11, 13, 17, 19, 23,
1792 29, 31, 37, 41, 43, 47, 53, 59,
1793 61, 67, 71, 73, 79, 83, 89, 97,
1794 101, 103, 107, 109, 113, 127, 131, 137,
1795 139, 149, 151, 157, 163, 167, 173, 179,
1796 181, 191, 193, 197, 199, 211, 223, 227,
1797 229, 233, 239, 241, 251, 257, 263, 269,
1798 271, 277, 281, 283, 293, 307, 311, 313,
1799 317, 331, 337, 347, 349, 353, 359, 367,
1800 373, 379, 383, 389, 397, 401, 409, 419,
1801 421, 431, 433, 439, 443, 449, 457, 461,
1802 463, 467, 479, 487, 491, 499, 503, 509,
1803 521, 523, 541, 547, 557, 563, 569, 571,
1804 577, 587, 593, 599, 601, 607, 613, 617,
1805 619, 631, 641, 643, 647, 653, 659, 661,
1806 673, 677, 683, 691, 701, 709, 719, 727,
1807 733, 739, 743, 751, 757, 761, 769, 773,
1808 787, 797, 809, 811, 821, 823, 827, 829,
1809 839, 853, 857, 859, 863, 877, 881, 883,
1810 887, 907, 911, 919, 929, 937, 941, 947,
1811 953, 967, 971, 977, 983, 991, 997, -103
1818 int (*f_rng)(
void *,
unsigned char *,
size_t),
1835 xs = X->
s; X->
s = 1;
1840 if( ( X->
p[0] & 1 ) == 0 )
1843 for( i = 0; small_prime[i] > 0; i++ )
1869 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1870 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1871 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1873 for( i = 0; i < n; i++ )
1936 int (*f_rng)(
void *,
unsigned char *,
size_t),
1948 n = BITS_TO_LIMBS( nbits );
1960 while( ( ret =
mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
2002 #if defined(POLARSSL_SELF_TEST)
2004 #define GCD_PAIR_COUNT 3
2006 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2010 { 768454923, 542167814, 1 }
2019 mpi A, E, N, X, Y, U, V;
2025 "EFE021C2645FD1DC586E69184AF4A31E" \
2026 "D5F53E93B5F123FA41680867BA110131" \
2027 "944FE7952E2517337780CB0DB80E61AA" \
2028 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2031 "B2E7EFD37075B9F03FF989C7C5051C20" \
2032 "34D2A323810251127E7BF8625A4F49A5" \
2033 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2034 "5B5C25763222FEFCCFC38B832366C29E" ) );
2037 "0066A198186C18C10B2F5ED9B522752A" \
2038 "9830B69916E535C8F047518A889A43A5" \
2039 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2044 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2045 "9E857EA95A03512E2BAE7391688D264A" \
2046 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2047 "8001B72E848A38CAE1C65F78E56ABDEF" \
2048 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2049 "ECF677152EF804370C1A305CAF3B5BF1" \
2050 "30879B56C61DE584A0F53A2447A51E" ) );
2053 printf(
" MPI test #1 (mul_mpi): " );
2058 printf(
"failed\n" );
2065 printf(
"passed\n" );
2070 "256567336059E52CAE22925474705F39A94" ) );
2073 "6613F26162223DF488E9CD48CC132C7A" \
2074 "0AC93C701B001B092E4E5B9F73BCD27B" \
2075 "9EE50D0657C77F374E903CDFA4C642" ) );
2078 printf(
" MPI test #2 (div_mpi): " );
2084 printf(
"failed\n" );
2091 printf(
"passed\n" );
2096 "36E139AEA55215609D2816998ED020BB" \
2097 "BD96C37890F65171D948E9BC7CBAA4D9" \
2098 "325D24D6A3C12710F10A09FA08AB87" ) );
2101 printf(
" MPI test #3 (exp_mod): " );
2106 printf(
"failed\n" );
2113 printf(
"passed\n" );
2115 #if defined(POLARSSL_GENPRIME)
2119 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2120 "C3DBA76456363A10869622EAC2DD84EC" \
2121 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2124 printf(
" MPI test #4 (inv_mod): " );
2129 printf(
"failed\n" );
2136 printf(
"passed\n" );
2140 printf(
" MPI test #5 (simple gcd): " );
2142 for ( i = 0; i < GCD_PAIR_COUNT; i++)
2152 printf(
"failed at %d\n", i );
2160 printf(
"passed\n" );
2164 if( ret != 0 && verbose != 0 )
2165 printf(
"Unexpected error, return code = %08X\n", ret );