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++) =
"0123456789ABCDEF" [c / 16];
410 *(p++) =
"0123456789ABCDEF" [c % 16];
422 MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
435 #if defined(POLARSSL_FS_IO)
450 memset( s, 0,
sizeof( s ) );
451 if( fgets( s,
sizeof( s ) - 1, fin ) == NULL )
455 if( slen ==
sizeof( s ) - 2 )
458 if( s[slen - 1] ==
'\n' ) { slen--; s[slen] =
'\0'; }
459 if( s[slen - 1] ==
'\r' ) { slen--; s[slen] =
'\0'; }
463 if( mpi_get_digit( &d, radix, *p ) != 0 )
475 size_t n, slen, plen;
488 if( p == NULL ) p =
"";
497 if( fwrite( p, 1, plen, fout ) != plen ||
498 fwrite( s, 1, slen, fout ) != slen )
502 printf(
"%s%s", p, s );
518 for( n = 0; n < buflen; n++ )
525 for( i = buflen, j = 0; i > n; i--, j++ )
526 X->
p[j / ciL] |= ((
t_uint) buf[i - 1]) << ((j % ciL) << 3);
545 memset( buf, 0, buflen );
547 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
548 buf[i] = (
unsigned char)( X->
p[j / ciL] >> ((j % ciL) << 3) );
563 t1 = count & (biL - 1);
577 for( i = X->
n; i > v0; i-- )
578 X->
p[i - 1] = X->
p[i - v0 - 1];
589 for( i = v0; i < X->
n; i++ )
591 r1 = X->
p[i] >> (biL - t1);
612 v1 = count & (biL - 1);
614 if( v0 > X->
n || ( v0 == X->
n && v1 > 0 ) )
622 for( i = 0; i < X->
n - v0; i++ )
623 X->
p[i] = X->
p[i + v0];
625 for( ; i < X->n; i++ )
634 for( i = X->
n; i > 0; i-- )
636 r1 = X->
p[i - 1] << (biL - v1);
653 for( i = X->
n; i > 0; i-- )
654 if( X->
p[i - 1] != 0 )
657 for( j = Y->
n; j > 0; j-- )
658 if( Y->
p[j - 1] != 0 )
661 if( i == 0 && j == 0 )
664 if( i > j )
return( 1 );
665 if( j > i )
return( -1 );
669 if( X->
p[i - 1] > Y->
p[i - 1] )
return( 1 );
670 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -1 );
683 for( i = X->
n; i > 0; i-- )
684 if( X->
p[i - 1] != 0 )
687 for( j = Y->
n; j > 0; j-- )
688 if( Y->
p[j - 1] != 0 )
691 if( i == 0 && j == 0 )
694 if( i > j )
return( X->
s );
695 if( j > i )
return( -Y->
s );
697 if( X->
s > 0 && Y->
s < 0 )
return( 1 );
698 if( Y->
s > 0 && X->
s < 0 )
return( -1 );
702 if( X->
p[i - 1] > Y->
p[i - 1] )
return( X->
s );
703 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -X->
s );
717 *p = ( z < 0 ) ? -z : z;
718 Y.
s = ( z < 0 ) ? -1 : 1;
736 const mpi *T = A; A = X; B = T;
747 for( j = B->
n; j > 0; j-- )
748 if( B->
p[j - 1] != 0 )
753 o = B->
p; p = X->
p; c = 0;
755 for( i = 0; i < j; i++, o++, p++ )
757 *p += c; c = ( *p < c );
758 *p += *o; c += ( *p < *o );
769 *p += c; c = ( *p < c ); i++; p++;
780 static void mpi_sub_hlp(
size_t n,
t_uint *s,
t_uint *d )
785 for( i = c = 0; i < n; i++, s++, d++ )
787 z = ( *d < c ); *d -= c;
788 c = ( *d < *s ) + z; *d -= *s;
793 z = ( *d < c ); *d -= c;
828 for( n = B->
n; n > 0; n-- )
829 if( B->
p[n - 1] != 0 )
832 mpi_sub_hlp( n, B->
p, X->
p );
848 if( A->
s * B->
s < 0 )
879 if( A->
s * B->
s > 0 )
911 p[0] = ( b < 0 ) ? -b : b;
912 _B.
s = ( b < 0 ) ? -1 : 1;
927 p[0] = ( b < 0 ) ? -b : b;
928 _B.
s = ( b < 0 ) ? -1 : 1;
939 #if defined(__APPLE__) && defined(__arm__)
944 __attribute__ ((noinline))
950 #if defined(MULADDC_HUIT)
951 for( ; i >= 8; i -= 8 )
965 for( ; i >= 16; i -= 16 )
980 for( ; i >= 8; i -= 8 )
1002 *d += c; c = ( *d < c ); d++;
1021 for( i = A->
n; i > 0; i-- )
1022 if( A->
p[i - 1] != 0 )
1025 for( j = B->
n; j > 0; j-- )
1026 if( B->
p[j - 1] != 0 )
1032 for( i++; j > 0; j-- )
1033 mpi_mul_hlp( i - 1, A->
p, X->
p + j - 1, B->
p[j - 1] );
1067 mpi X, Y, Z, T1, T2;
1111 for( i = n; i > t ; i-- )
1113 if( X.
p[i] >= Y.
p[t] )
1114 Z.
p[i - t - 1] = ~0;
1117 #if defined(POLARSSL_HAVE_UDBL)
1123 if( r > ((
t_udbl) 1 << biL) - 1)
1124 r = ((
t_udbl) 1 << biL) - 1;
1135 d0 = ( d << biH ) >> biH;
1139 r1 = X.
p[i] - d1 * q1;
1141 r1 |= ( X.
p[i - 1] >> biH );
1147 while( r1 >= d && r1 < m )
1155 r0 |= ( X.
p[i - 1] << biH ) >> biH;
1161 while( r0 >= d && r0 < m )
1166 Z.
p[i - t - 1] = ( q1 << biH ) | q0;
1176 T1.
p[0] = (t < 1) ? 0 : Y.
p[t - 1];
1181 T2.
p[0] = (i < 2) ? 0 : X.
p[i - 2];
1182 T2.
p[1] = (i < 1) ? 0 : X.
p[i - 1];
1232 p[0] = ( b < 0 ) ? -b : b;
1233 _B.
s = ( b < 0 ) ? -1 : 1;
1295 for( i = A->
n, y = 0; i > 0; i-- )
1298 y = ( y << biH ) | ( x >> biH );
1303 y = ( y << biH ) | ( x >> biH );
1312 if( A->
s < 0 && y != 0 )
1323 static void mpi_montg_init(
t_uint *mm,
const mpi *N )
1328 x += ( ( m0 + 2 ) & 4 ) << 1;
1329 x *= ( 2 - ( m0 * x ) );
1331 if( biL >= 16 ) x *= ( 2 - ( m0 * x ) );
1332 if( biL >= 32 ) x *= ( 2 - ( m0 * x ) );
1333 if( biL >= 64 ) x *= ( 2 - ( m0 * x ) );
1341 static void mpi_montmul(
mpi *A,
const mpi *B,
const mpi *N,
t_uint mm,
const mpi *T )
1346 memset( T->
p, 0, T->
n * ciL );
1350 m = ( B->
n < n ) ? B->
n : n;
1352 for( i = 0; i < n; i++ )
1358 u1 = ( d[0] + u0 * B->
p[0] ) * mm;
1360 mpi_mul_hlp( m, B->
p, d, u0 );
1361 mpi_mul_hlp( n, N->
p, d, u1 );
1363 *d++ = u0; d[n + 1] = 0;
1366 memcpy( A->
p, d, (n + 1) * ciL );
1369 mpi_sub_hlp( n, N->
p, A->
p );
1372 mpi_sub_hlp( n, A->
p, T->
p );
1378 static void mpi_montred(
mpi *A,
const mpi *N,
t_uint mm,
const mpi *T )
1383 U.
n = U.
s = (int) z;
1386 mpi_montmul( A, &U, N, mm, T );
1395 size_t wbits, wsize, one = 1;
1396 size_t i, j, nblimbs;
1397 size_t bufsize, nbits;
1411 mpi_montg_init( &mm, N );
1413 memset( W, 0,
sizeof( W ) );
1417 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1418 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1431 neg = ( A->
s == -1 );
1444 if( _RR == NULL || _RR->
p == NULL )
1451 memcpy( _RR, &RR,
sizeof(
mpi ) );
1454 memcpy( &RR, _RR,
sizeof(
mpi ) );
1463 mpi_montmul( &W[1], &RR, N, mm, &T );
1469 mpi_montred( X, N, mm, &T );
1476 j = one << (wsize - 1);
1481 for( i = 0; i < wsize - 1; i++ )
1482 mpi_montmul( &W[j], &W[j], N, mm, &T );
1487 for( i = j + 1; i < (one << wsize); i++ )
1492 mpi_montmul( &W[i], &W[1], N, mm, &T );
1506 if( nblimbs-- == 0 )
1509 bufsize =
sizeof(
t_uint ) << 3;
1514 ei = (E->
p[nblimbs] >> bufsize) & 1;
1519 if( ei == 0 && state == 0 )
1522 if( ei == 0 && state == 1 )
1527 mpi_montmul( X, X, N, mm, &T );
1537 wbits |= (ei << (wsize - nbits));
1539 if( nbits == wsize )
1544 for( i = 0; i < wsize; i++ )
1545 mpi_montmul( X, X, N, mm, &T );
1550 mpi_montmul( X, &W[wbits], N, mm, &T );
1561 for( i = 0; i < nbits; i++ )
1563 mpi_montmul( X, X, N, mm, &T );
1567 if( (wbits & (one << wsize)) != 0 )
1568 mpi_montmul( X, &W[1], N, mm, &T );
1574 mpi_montred( X, N, mm, &T );
1584 for( i = (one << (wsize - 1)); i < (one << wsize); i++ )
1648 int (*f_rng)(
void *,
unsigned char *,
size_t),
1656 MPI_CHK( f_rng( p_rng, (
unsigned char *) X->
p, size ) );
1668 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1697 while( ( TU.
p[0] & 1 ) == 0 )
1701 if( ( U1.
p[0] & 1 ) != 0 || ( U2.
p[0] & 1 ) != 0 )
1711 while( ( TV.
p[0] & 1 ) == 0 )
1715 if( ( V1.
p[0] & 1 ) != 0 || ( V2.
p[0] & 1 ) != 0 )
1757 #if defined(POLARSSL_GENPRIME)
1759 static const int small_prime[] =
1761 3, 5, 7, 11, 13, 17, 19, 23,
1762 29, 31, 37, 41, 43, 47, 53, 59,
1763 61, 67, 71, 73, 79, 83, 89, 97,
1764 101, 103, 107, 109, 113, 127, 131, 137,
1765 139, 149, 151, 157, 163, 167, 173, 179,
1766 181, 191, 193, 197, 199, 211, 223, 227,
1767 229, 233, 239, 241, 251, 257, 263, 269,
1768 271, 277, 281, 283, 293, 307, 311, 313,
1769 317, 331, 337, 347, 349, 353, 359, 367,
1770 373, 379, 383, 389, 397, 401, 409, 419,
1771 421, 431, 433, 439, 443, 449, 457, 461,
1772 463, 467, 479, 487, 491, 499, 503, 509,
1773 521, 523, 541, 547, 557, 563, 569, 571,
1774 577, 587, 593, 599, 601, 607, 613, 617,
1775 619, 631, 641, 643, 647, 653, 659, 661,
1776 673, 677, 683, 691, 701, 709, 719, 727,
1777 733, 739, 743, 751, 757, 761, 769, 773,
1778 787, 797, 809, 811, 821, 823, 827, 829,
1779 839, 853, 857, 859, 863, 877, 881, 883,
1780 887, 907, 911, 919, 929, 937, 941, 947,
1781 953, 967, 971, 977, 983, 991, 997, -103
1788 int (*f_rng)(
void *,
unsigned char *,
size_t),
1805 xs = X->
s; X->
s = 1;
1810 if( ( X->
p[0] & 1 ) == 0 )
1813 for( i = 0; small_prime[i] > 0; i++ )
1839 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1840 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1841 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1843 for( i = 0; i < n; i++ )
1906 int (*f_rng)(
void *,
unsigned char *,
size_t),
1918 n = BITS_TO_LIMBS( nbits );
1930 while( ( ret =
mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
1972 #if defined(POLARSSL_SELF_TEST)
1974 #define GCD_PAIR_COUNT 3
1976 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
1980 { 768454923, 542167814, 1 }
1989 mpi A, E, N, X, Y, U, V;
1995 "EFE021C2645FD1DC586E69184AF4A31E" \
1996 "D5F53E93B5F123FA41680867BA110131" \
1997 "944FE7952E2517337780CB0DB80E61AA" \
1998 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2001 "B2E7EFD37075B9F03FF989C7C5051C20" \
2002 "34D2A323810251127E7BF8625A4F49A5" \
2003 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2004 "5B5C25763222FEFCCFC38B832366C29E" ) );
2007 "0066A198186C18C10B2F5ED9B522752A" \
2008 "9830B69916E535C8F047518A889A43A5" \
2009 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2014 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2015 "9E857EA95A03512E2BAE7391688D264A" \
2016 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2017 "8001B72E848A38CAE1C65F78E56ABDEF" \
2018 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2019 "ECF677152EF804370C1A305CAF3B5BF1" \
2020 "30879B56C61DE584A0F53A2447A51E" ) );
2023 printf(
" MPI test #1 (mul_mpi): " );
2028 printf(
"failed\n" );
2034 printf(
"passed\n" );
2039 "256567336059E52CAE22925474705F39A94" ) );
2042 "6613F26162223DF488E9CD48CC132C7A" \
2043 "0AC93C701B001B092E4E5B9F73BCD27B" \
2044 "9EE50D0657C77F374E903CDFA4C642" ) );
2047 printf(
" MPI test #2 (div_mpi): " );
2053 printf(
"failed\n" );
2059 printf(
"passed\n" );
2064 "36E139AEA55215609D2816998ED020BB" \
2065 "BD96C37890F65171D948E9BC7CBAA4D9" \
2066 "325D24D6A3C12710F10A09FA08AB87" ) );
2069 printf(
" MPI test #3 (exp_mod): " );
2074 printf(
"failed\n" );
2080 printf(
"passed\n" );
2082 #if defined(POLARSSL_GENPRIME)
2086 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2087 "C3DBA76456363A10869622EAC2DD84EC" \
2088 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2091 printf(
" MPI test #4 (inv_mod): " );
2096 printf(
"failed\n" );
2102 printf(
"passed\n" );
2106 printf(
" MPI test #5 (simple gcd): " );
2108 for ( i = 0; i < GCD_PAIR_COUNT; i++)
2118 printf(
"failed at %d\n", i );
2125 printf(
"passed\n" );
2129 if( ret != 0 && verbose != 0 )
2130 printf(
"Unexpected error, return code = %08X\n", ret );