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;
942 #if defined(MULADDC_HUIT)
943 for( ; i >= 8; i -= 8 )
957 for( ; i >= 16; i -= 16 )
972 for( ; i >= 8; i -= 8 )
994 *d += c; c = ( *d < c ); d++;
1013 for( i = A->
n; i > 0; i-- )
1014 if( A->
p[i - 1] != 0 )
1017 for( j = B->
n; j > 0; j-- )
1018 if( B->
p[j - 1] != 0 )
1024 for( i++; j > 0; j-- )
1025 mpi_mul_hlp( i - 1, A->
p, X->
p + j - 1, B->
p[j - 1] );
1059 mpi X, Y, Z, T1, T2;
1103 for( i = n; i > t ; i-- )
1105 if( X.
p[i] >= Y.
p[t] )
1106 Z.
p[i - t - 1] = ~0;
1109 #if defined(POLARSSL_HAVE_UDBL)
1115 if( r > ((
t_udbl) 1 << biL) - 1)
1116 r = ((
t_udbl) 1 << biL) - 1;
1127 d0 = ( d << biH ) >> biH;
1131 r1 = X.
p[i] - d1 * q1;
1133 r1 |= ( X.
p[i - 1] >> biH );
1139 while( r1 >= d && r1 < m )
1147 r0 |= ( X.
p[i - 1] << biH ) >> biH;
1153 while( r0 >= d && r0 < m )
1158 Z.
p[i - t - 1] = ( q1 << biH ) | q0;
1168 T1.
p[0] = (t < 1) ? 0 : Y.
p[t - 1];
1173 T2.
p[0] = (i < 2) ? 0 : X.
p[i - 2];
1174 T2.
p[1] = (i < 1) ? 0 : X.
p[i - 1];
1224 p[0] = ( b < 0 ) ? -b : b;
1225 _B.
s = ( b < 0 ) ? -1 : 1;
1287 for( i = A->
n, y = 0; i > 0; i-- )
1290 y = ( y << biH ) | ( x >> biH );
1295 y = ( y << biH ) | ( x >> biH );
1304 if( A->
s < 0 && y != 0 )
1315 static void mpi_montg_init(
t_uint *mm,
const mpi *N )
1320 x += ( ( m0 + 2 ) & 4 ) << 1;
1321 x *= ( 2 - ( m0 * x ) );
1323 if( biL >= 16 ) x *= ( 2 - ( m0 * x ) );
1324 if( biL >= 32 ) x *= ( 2 - ( m0 * x ) );
1325 if( biL >= 64 ) x *= ( 2 - ( m0 * x ) );
1333 static void mpi_montmul(
mpi *A,
const mpi *B,
const mpi *N,
t_uint mm,
const mpi *T )
1338 memset( T->
p, 0, T->
n * ciL );
1342 m = ( B->
n < n ) ? B->
n : n;
1344 for( i = 0; i < n; i++ )
1350 u1 = ( d[0] + u0 * B->
p[0] ) * mm;
1352 mpi_mul_hlp( m, B->
p, d, u0 );
1353 mpi_mul_hlp( n, N->
p, d, u1 );
1355 *d++ = u0; d[n + 1] = 0;
1358 memcpy( A->
p, d, (n + 1) * ciL );
1361 mpi_sub_hlp( n, N->
p, A->
p );
1364 mpi_sub_hlp( n, A->
p, T->
p );
1370 static void mpi_montred(
mpi *A,
const mpi *N,
t_uint mm,
const mpi *T )
1378 mpi_montmul( A, &U, N, mm, T );
1387 size_t wbits, wsize, one = 1;
1388 size_t i, j, nblimbs;
1389 size_t bufsize, nbits;
1403 mpi_montg_init( &mm, N );
1405 memset( W, 0,
sizeof( W ) );
1409 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1410 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1423 neg = ( A->
s == -1 );
1436 if( _RR == NULL || _RR->
p == NULL )
1443 memcpy( _RR, &RR,
sizeof(
mpi ) );
1446 memcpy( &RR, _RR,
sizeof(
mpi ) );
1455 mpi_montmul( &W[1], &RR, N, mm, &T );
1461 mpi_montred( X, N, mm, &T );
1468 j = one << (wsize - 1);
1473 for( i = 0; i < wsize - 1; i++ )
1474 mpi_montmul( &W[j], &W[j], N, mm, &T );
1479 for( i = j + 1; i < (one << wsize); i++ )
1484 mpi_montmul( &W[i], &W[1], N, mm, &T );
1498 if( nblimbs-- == 0 )
1501 bufsize =
sizeof(
t_uint ) << 3;
1506 ei = (E->
p[nblimbs] >> bufsize) & 1;
1511 if( ei == 0 && state == 0 )
1514 if( ei == 0 && state == 1 )
1519 mpi_montmul( X, X, N, mm, &T );
1529 wbits |= (ei << (wsize - nbits));
1531 if( nbits == wsize )
1536 for( i = 0; i < wsize; i++ )
1537 mpi_montmul( X, X, N, mm, &T );
1542 mpi_montmul( X, &W[wbits], N, mm, &T );
1553 for( i = 0; i < nbits; i++ )
1555 mpi_montmul( X, X, N, mm, &T );
1559 if( (wbits & (one << wsize)) != 0 )
1560 mpi_montmul( X, &W[1], N, mm, &T );
1566 mpi_montred( X, N, mm, &T );
1576 for( i = (one << (wsize - 1)); i < (one << wsize); i++ )
1640 int (*f_rng)(
void *,
unsigned char *,
size_t),
1648 MPI_CHK( f_rng( p_rng, (
unsigned char *) X->
p, size ) );
1660 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1689 while( ( TU.
p[0] & 1 ) == 0 )
1693 if( ( U1.
p[0] & 1 ) != 0 || ( U2.
p[0] & 1 ) != 0 )
1703 while( ( TV.
p[0] & 1 ) == 0 )
1707 if( ( V1.
p[0] & 1 ) != 0 || ( V2.
p[0] & 1 ) != 0 )
1749 #if defined(POLARSSL_GENPRIME)
1751 static const int small_prime[] =
1753 3, 5, 7, 11, 13, 17, 19, 23,
1754 29, 31, 37, 41, 43, 47, 53, 59,
1755 61, 67, 71, 73, 79, 83, 89, 97,
1756 101, 103, 107, 109, 113, 127, 131, 137,
1757 139, 149, 151, 157, 163, 167, 173, 179,
1758 181, 191, 193, 197, 199, 211, 223, 227,
1759 229, 233, 239, 241, 251, 257, 263, 269,
1760 271, 277, 281, 283, 293, 307, 311, 313,
1761 317, 331, 337, 347, 349, 353, 359, 367,
1762 373, 379, 383, 389, 397, 401, 409, 419,
1763 421, 431, 433, 439, 443, 449, 457, 461,
1764 463, 467, 479, 487, 491, 499, 503, 509,
1765 521, 523, 541, 547, 557, 563, 569, 571,
1766 577, 587, 593, 599, 601, 607, 613, 617,
1767 619, 631, 641, 643, 647, 653, 659, 661,
1768 673, 677, 683, 691, 701, 709, 719, 727,
1769 733, 739, 743, 751, 757, 761, 769, 773,
1770 787, 797, 809, 811, 821, 823, 827, 829,
1771 839, 853, 857, 859, 863, 877, 881, 883,
1772 887, 907, 911, 919, 929, 937, 941, 947,
1773 953, 967, 971, 977, 983, 991, 997, -103
1780 int (*f_rng)(
void *,
unsigned char *,
size_t),
1797 xs = X->
s; X->
s = 1;
1802 if( ( X->
p[0] & 1 ) == 0 )
1805 for( i = 0; small_prime[i] > 0; i++ )
1831 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1832 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1833 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1835 for( i = 0; i < n; i++ )
1898 int (*f_rng)(
void *,
unsigned char *,
size_t),
1910 n = BITS_TO_LIMBS( nbits );
1922 while( ( ret =
mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
1964 #if defined(POLARSSL_SELF_TEST)
1966 #define GCD_PAIR_COUNT 3
1968 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
1972 { 768454923, 542167814, 1 }
1981 mpi A, E, N, X, Y, U, V;
1987 "EFE021C2645FD1DC586E69184AF4A31E" \
1988 "D5F53E93B5F123FA41680867BA110131" \
1989 "944FE7952E2517337780CB0DB80E61AA" \
1990 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
1993 "B2E7EFD37075B9F03FF989C7C5051C20" \
1994 "34D2A323810251127E7BF8625A4F49A5" \
1995 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
1996 "5B5C25763222FEFCCFC38B832366C29E" ) );
1999 "0066A198186C18C10B2F5ED9B522752A" \
2000 "9830B69916E535C8F047518A889A43A5" \
2001 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2006 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2007 "9E857EA95A03512E2BAE7391688D264A" \
2008 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2009 "8001B72E848A38CAE1C65F78E56ABDEF" \
2010 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2011 "ECF677152EF804370C1A305CAF3B5BF1" \
2012 "30879B56C61DE584A0F53A2447A51E" ) );
2015 printf(
" MPI test #1 (mul_mpi): " );
2020 printf(
"failed\n" );
2026 printf(
"passed\n" );
2031 "256567336059E52CAE22925474705F39A94" ) );
2034 "6613F26162223DF488E9CD48CC132C7A" \
2035 "0AC93C701B001B092E4E5B9F73BCD27B" \
2036 "9EE50D0657C77F374E903CDFA4C642" ) );
2039 printf(
" MPI test #2 (div_mpi): " );
2045 printf(
"failed\n" );
2051 printf(
"passed\n" );
2056 "36E139AEA55215609D2816998ED020BB" \
2057 "BD96C37890F65171D948E9BC7CBAA4D9" \
2058 "325D24D6A3C12710F10A09FA08AB87" ) );
2061 printf(
" MPI test #3 (exp_mod): " );
2066 printf(
"failed\n" );
2072 printf(
"passed\n" );
2074 #if defined(POLARSSL_GENPRIME)
2078 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2079 "C3DBA76456363A10869622EAC2DD84EC" \
2080 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2083 printf(
" MPI test #4 (inv_mod): " );
2088 printf(
"failed\n" );
2094 printf(
"passed\n" );
2098 printf(
" MPI test #5 (simple gcd): " );
2100 for ( i = 0; i < GCD_PAIR_COUNT; i++)
2110 printf(
"failed at %d\n", i );
2117 printf(
"passed\n" );
2121 if( ret != 0 && verbose != 0 )
2122 printf(
"Unexpected error, return code = %08X\n", ret );