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 += sprintf( p,
"%02X", c );
421 MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
434 #if defined(POLARSSL_FS_IO)
449 memset( s, 0,
sizeof( s ) );
450 if( fgets( s,
sizeof( s ) - 1, fin ) == NULL )
454 if( slen ==
sizeof( s ) - 2 )
457 if( s[slen - 1] ==
'\n' ) { slen--; s[slen] =
'\0'; }
458 if( s[slen - 1] ==
'\r' ) { slen--; s[slen] =
'\0'; }
462 if( mpi_get_digit( &d, radix, *p ) != 0 )
474 size_t n, slen, plen;
486 if( p == NULL ) p =
"";
495 if( fwrite( p, 1, plen, fout ) != plen ||
496 fwrite( s, 1, slen, fout ) != slen )
500 printf(
"%s%s", p, s );
516 for( n = 0; n < buflen; n++ )
523 for( i = buflen, j = 0; i > n; i--, j++ )
524 X->
p[j / ciL] |= ((
t_uint) buf[i - 1]) << ((j % ciL) << 3);
543 memset( buf, 0, buflen );
545 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
546 buf[i] = (
unsigned char)( X->
p[j / ciL] >> ((j % ciL) << 3) );
561 t1 = count & (biL - 1);
575 for( i = X->
n; i > v0; i-- )
576 X->
p[i - 1] = X->
p[i - v0 - 1];
587 for( i = v0; i < X->
n; i++ )
589 r1 = X->
p[i] >> (biL - t1);
610 v1 = count & (biL - 1);
612 if( v0 > X->
n || ( v0 == X->
n && v1 > 0 ) )
620 for( i = 0; i < X->
n - v0; i++ )
621 X->
p[i] = X->
p[i + v0];
623 for( ; i < X->n; i++ )
632 for( i = X->
n; i > 0; i-- )
634 r1 = X->
p[i - 1] << (biL - v1);
651 for( i = X->
n; i > 0; i-- )
652 if( X->
p[i - 1] != 0 )
655 for( j = Y->
n; j > 0; j-- )
656 if( Y->
p[j - 1] != 0 )
659 if( i == 0 && j == 0 )
662 if( i > j )
return( 1 );
663 if( j > i )
return( -1 );
667 if( X->
p[i - 1] > Y->
p[i - 1] )
return( 1 );
668 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -1 );
681 for( i = X->
n; i > 0; i-- )
682 if( X->
p[i - 1] != 0 )
685 for( j = Y->
n; j > 0; j-- )
686 if( Y->
p[j - 1] != 0 )
689 if( i == 0 && j == 0 )
692 if( i > j )
return( X->
s );
693 if( j > i )
return( -Y->
s );
695 if( X->
s > 0 && Y->
s < 0 )
return( 1 );
696 if( Y->
s > 0 && X->
s < 0 )
return( -1 );
700 if( X->
p[i - 1] > Y->
p[i - 1] )
return( X->
s );
701 if( X->
p[i - 1] < Y->
p[i - 1] )
return( -X->
s );
715 *p = ( z < 0 ) ? -z : z;
716 Y.
s = ( z < 0 ) ? -1 : 1;
734 const mpi *T = A; A = X; B = T;
745 for( j = B->
n; j > 0; j-- )
746 if( B->
p[j - 1] != 0 )
751 o = B->
p; p = X->
p; c = 0;
753 for( i = 0; i < j; i++, o++, p++ )
755 *p += c; c = ( *p < c );
756 *p += *o; c += ( *p < *o );
767 *p += c; c = ( *p < c ); i++; p++;
778 static void mpi_sub_hlp(
size_t n,
t_uint *s,
t_uint *d )
783 for( i = c = 0; i < n; i++, s++, d++ )
785 z = ( *d < c ); *d -= c;
786 c = ( *d < *s ) + z; *d -= *s;
791 z = ( *d < c ); *d -= c;
826 for( n = B->
n; n > 0; n-- )
827 if( B->
p[n - 1] != 0 )
830 mpi_sub_hlp( n, B->
p, X->
p );
846 if( A->
s * B->
s < 0 )
877 if( A->
s * B->
s > 0 )
909 p[0] = ( b < 0 ) ? -b : b;
910 _B.
s = ( b < 0 ) ? -1 : 1;
925 p[0] = ( b < 0 ) ? -b : b;
926 _B.
s = ( b < 0 ) ? -1 : 1;
940 #if defined(MULADDC_HUIT)
941 for( ; i >= 8; i -= 8 )
955 for( ; i >= 16; i -= 16 )
970 for( ; i >= 8; i -= 8 )
992 *d += c; c = ( *d < c ); d++;
1011 for( i = A->
n; i > 0; i-- )
1012 if( A->
p[i - 1] != 0 )
1015 for( j = B->
n; j > 0; j-- )
1016 if( B->
p[j - 1] != 0 )
1022 for( i++; j > 0; j-- )
1023 mpi_mul_hlp( i - 1, A->
p, X->
p + j - 1, B->
p[j - 1] );
1057 mpi X, Y, Z, T1, T2;
1101 for( i = n; i > t ; i-- )
1103 if( X.
p[i] >= Y.
p[t] )
1104 Z.
p[i - t - 1] = ~0;
1107 #if defined(POLARSSL_HAVE_LONGLONG)
1110 r = (t_udbl) X.
p[i] << biL;
1111 r |= (t_udbl) X.
p[i - 1];
1113 if( r > ((t_udbl) 1 << biL) - 1)
1114 r = ((t_udbl) 1 << biL) - 1;
1125 d0 = ( d << biH ) >> biH;
1129 r1 = X.
p[i] - d1 * q1;
1131 r1 |= ( X.
p[i - 1] >> biH );
1137 while( r1 >= d && r1 < m )
1145 r0 |= ( X.
p[i - 1] << biH ) >> biH;
1151 while( r0 >= d && r0 < m )
1156 Z.
p[i - t - 1] = ( q1 << biH ) | q0;
1166 T1.
p[0] = (t < 1) ? 0 : Y.
p[t - 1];
1171 T2.
p[0] = (i < 2) ? 0 : X.
p[i - 2];
1172 T2.
p[1] = (i < 1) ? 0 : X.
p[i - 1];
1222 p[0] = ( b < 0 ) ? -b : b;
1223 _B.
s = ( b < 0 ) ? -1 : 1;
1285 for( i = A->
n, y = 0; i > 0; i-- )
1288 y = ( y << biH ) | ( x >> biH );
1293 y = ( y << biH ) | ( x >> biH );
1302 if( A->
s < 0 && y != 0 )
1313 static void mpi_montg_init(
t_uint *mm,
const mpi *N )
1318 x += ( ( m0 + 2 ) & 4 ) << 1;
1319 x *= ( 2 - ( m0 * x ) );
1321 if( biL >= 16 ) x *= ( 2 - ( m0 * x ) );
1322 if( biL >= 32 ) x *= ( 2 - ( m0 * x ) );
1323 if( biL >= 64 ) x *= ( 2 - ( m0 * x ) );
1331 static void mpi_montmul(
mpi *A,
const mpi *B,
const mpi *N,
t_uint mm,
const mpi *T )
1336 memset( T->
p, 0, T->
n * ciL );
1340 m = ( B->
n < n ) ? B->
n : n;
1342 for( i = 0; i < n; i++ )
1348 u1 = ( d[0] + u0 * B->
p[0] ) * mm;
1350 mpi_mul_hlp( m, B->
p, d, u0 );
1351 mpi_mul_hlp( n, N->
p, d, u1 );
1353 *d++ = u0; d[n + 1] = 0;
1356 memcpy( A->
p, d, (n + 1) * ciL );
1359 mpi_sub_hlp( n, N->
p, A->
p );
1362 mpi_sub_hlp( n, A->
p, T->
p );
1368 static void mpi_montred(
mpi *A,
const mpi *N,
t_uint mm,
const mpi *T )
1376 mpi_montmul( A, &U, N, mm, T );
1385 size_t wbits, wsize, one = 1;
1386 size_t i, j, nblimbs;
1387 size_t bufsize, nbits;
1401 mpi_montg_init( &mm, N );
1403 memset( W, 0,
sizeof( W ) );
1407 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1408 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1421 neg = ( A->
s == -1 );
1434 if( _RR == NULL || _RR->
p == NULL )
1441 memcpy( _RR, &RR,
sizeof(
mpi ) );
1444 memcpy( &RR, _RR,
sizeof(
mpi ) );
1453 mpi_montmul( &W[1], &RR, N, mm, &T );
1459 mpi_montred( X, N, mm, &T );
1466 j = one << (wsize - 1);
1471 for( i = 0; i < wsize - 1; i++ )
1472 mpi_montmul( &W[j], &W[j], N, mm, &T );
1477 for( i = j + 1; i < (one << wsize); i++ )
1482 mpi_montmul( &W[i], &W[1], N, mm, &T );
1496 if( nblimbs-- == 0 )
1499 bufsize =
sizeof(
t_uint ) << 3;
1504 ei = (E->
p[nblimbs] >> bufsize) & 1;
1509 if( ei == 0 && state == 0 )
1512 if( ei == 0 && state == 1 )
1517 mpi_montmul( X, X, N, mm, &T );
1527 wbits |= (ei << (wsize - nbits));
1529 if( nbits == wsize )
1534 for( i = 0; i < wsize; i++ )
1535 mpi_montmul( X, X, N, mm, &T );
1540 mpi_montmul( X, &W[wbits], N, mm, &T );
1551 for( i = 0; i < nbits; i++ )
1553 mpi_montmul( X, X, N, mm, &T );
1557 if( (wbits & (one << wsize)) != 0 )
1558 mpi_montmul( X, &W[1], N, mm, &T );
1564 mpi_montred( X, N, mm, &T );
1574 for( i = (one << (wsize - 1)); i < (one << wsize); i++ )
1638 int (*f_rng)(
void *,
unsigned char *,
size_t),
1646 MPI_CHK( f_rng( p_rng, (
unsigned char *) X->
p, size ) );
1658 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1687 while( ( TU.
p[0] & 1 ) == 0 )
1691 if( ( U1.
p[0] & 1 ) != 0 || ( U2.
p[0] & 1 ) != 0 )
1701 while( ( TV.
p[0] & 1 ) == 0 )
1705 if( ( V1.
p[0] & 1 ) != 0 || ( V2.
p[0] & 1 ) != 0 )
1747 #if defined(POLARSSL_GENPRIME)
1749 static const int small_prime[] =
1751 3, 5, 7, 11, 13, 17, 19, 23,
1752 29, 31, 37, 41, 43, 47, 53, 59,
1753 61, 67, 71, 73, 79, 83, 89, 97,
1754 101, 103, 107, 109, 113, 127, 131, 137,
1755 139, 149, 151, 157, 163, 167, 173, 179,
1756 181, 191, 193, 197, 199, 211, 223, 227,
1757 229, 233, 239, 241, 251, 257, 263, 269,
1758 271, 277, 281, 283, 293, 307, 311, 313,
1759 317, 331, 337, 347, 349, 353, 359, 367,
1760 373, 379, 383, 389, 397, 401, 409, 419,
1761 421, 431, 433, 439, 443, 449, 457, 461,
1762 463, 467, 479, 487, 491, 499, 503, 509,
1763 521, 523, 541, 547, 557, 563, 569, 571,
1764 577, 587, 593, 599, 601, 607, 613, 617,
1765 619, 631, 641, 643, 647, 653, 659, 661,
1766 673, 677, 683, 691, 701, 709, 719, 727,
1767 733, 739, 743, 751, 757, 761, 769, 773,
1768 787, 797, 809, 811, 821, 823, 827, 829,
1769 839, 853, 857, 859, 863, 877, 881, 883,
1770 887, 907, 911, 919, 929, 937, 941, 947,
1771 953, 967, 971, 977, 983, 991, 997, -103
1778 int (*f_rng)(
void *,
unsigned char *,
size_t),
1795 xs = X->
s; X->
s = 1;
1800 if( ( X->
p[0] & 1 ) == 0 )
1803 for( i = 0; small_prime[i] > 0; i++ )
1829 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1830 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1831 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1833 for( i = 0; i < n; i++ )
1896 int (*f_rng)(
void *,
unsigned char *,
size_t),
1908 n = BITS_TO_LIMBS( nbits );
1920 while( ( ret =
mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
1962 #if defined(POLARSSL_SELF_TEST)
1964 #define GCD_PAIR_COUNT 3
1966 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
1970 { 768454923, 542167814, 1 }
1979 mpi A, E, N, X, Y, U, V;
1985 "EFE021C2645FD1DC586E69184AF4A31E" \
1986 "D5F53E93B5F123FA41680867BA110131" \
1987 "944FE7952E2517337780CB0DB80E61AA" \
1988 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
1991 "B2E7EFD37075B9F03FF989C7C5051C20" \
1992 "34D2A323810251127E7BF8625A4F49A5" \
1993 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
1994 "5B5C25763222FEFCCFC38B832366C29E" ) );
1997 "0066A198186C18C10B2F5ED9B522752A" \
1998 "9830B69916E535C8F047518A889A43A5" \
1999 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2004 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2005 "9E857EA95A03512E2BAE7391688D264A" \
2006 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2007 "8001B72E848A38CAE1C65F78E56ABDEF" \
2008 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2009 "ECF677152EF804370C1A305CAF3B5BF1" \
2010 "30879B56C61DE584A0F53A2447A51E" ) );
2013 printf(
" MPI test #1 (mul_mpi): " );
2018 printf(
"failed\n" );
2024 printf(
"passed\n" );
2029 "256567336059E52CAE22925474705F39A94" ) );
2032 "6613F26162223DF488E9CD48CC132C7A" \
2033 "0AC93C701B001B092E4E5B9F73BCD27B" \
2034 "9EE50D0657C77F374E903CDFA4C642" ) );
2037 printf(
" MPI test #2 (div_mpi): " );
2043 printf(
"failed\n" );
2049 printf(
"passed\n" );
2054 "36E139AEA55215609D2816998ED020BB" \
2055 "BD96C37890F65171D948E9BC7CBAA4D9" \
2056 "325D24D6A3C12710F10A09FA08AB87" ) );
2059 printf(
" MPI test #3 (exp_mod): " );
2064 printf(
"failed\n" );
2070 printf(
"passed\n" );
2072 #if defined(POLARSSL_GENPRIME)
2076 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2077 "C3DBA76456363A10869622EAC2DD84EC" \
2078 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2081 printf(
" MPI test #4 (inv_mod): " );
2086 printf(
"failed\n" );
2092 printf(
"passed\n" );
2096 printf(
" MPI test #5 (simple gcd): " );
2098 for ( i = 0; i < GCD_PAIR_COUNT; i++)
2108 printf(
"failed at %d\n", i );
2115 printf(
"passed\n" );
2119 if( ret != 0 && verbose != 0 )
2120 printf(
"Unexpected error, return code = %08X\n", ret );