📄 mpi.cpp
字号:
}
/*
* process the remaining bits
*/
for( i = 0; i < nbits; i++ )
{
CHK( mpi_montgomery( &T, &S, &S, N, &Z, mm ) );
CHK( mpi_copy( &S, &T ) );
wbits <<= 1;
if( (wbits & (1 << wsize)) != 0 )
{
CHK( mpi_montgomery( &T, &S, &W[1], N, &Z, mm ) );
CHK( mpi_copy( &S, &T ) );
}
}
/*
* X = A^E * R * R^-1 mod N = A^E mod N
*/
CHK( mpi_montgomery( &T, &S, NULL, N, &Z, mm ) );
CHK( mpi_copy( X, &T ) );
if( wsize > 1 )
for( i = (1 << (wsize - 1));
i < (1 << wsize); i++ )
mpi_free( &W[i], NULL );
cleanup:
mpi_free( &Z, &W[1], &R, &S, &T, NULL );
return( ret );
}
/*
* Greatest common divisor (HAC 14.54)
*
* Returns 0 if successful
* 1 if memory allocation failed
*/
int mpi_gcd( mpi *G, mpi *A, mpi *B )
{
int ret;
uint count;
mpi TG, TA, TB;
mpi_init( &TG, &TA, &TB, NULL );
CHK( mpi_lset( &TG, 1 ) );
CHK( mpi_copy( &TA, A ) );
CHK( mpi_copy( &TB, B ) );
TA.s = TB.s = 1;
count = ( mpi_lsb( &TA ) < mpi_lsb( &TB ) )
? mpi_lsb( &TA ) : mpi_lsb( &TB );
CHK( mpi_shift_l( &TG, count ) );
CHK( mpi_shift_r( &TA, count ) );
CHK( mpi_shift_r( &TB, count ) );
while( mpi_cmp_int( &TA, 0 ) != 0 )
{
while( ( TA.p[0] & 1 ) == 0 ) CHK( mpi_shift_r( &TA, 1 ) );
while( ( TB.p[0] & 1 ) == 0 ) CHK( mpi_shift_r( &TB, 1 ) );
if( mpi_cmp_mpi( &TA, &TB ) >= 0 )
{
CHK( mpi_sub_abs( &TA, &TA, &TB ) );
CHK( mpi_shift_r( &TA, 1 ) );
}
else
{
CHK( mpi_sub_abs( &TB, &TB, &TA ) );
CHK( mpi_shift_r( &TB, 1 ) );
}
}
CHK( mpi_mul_mpi( G, &TG, &TB ) );
cleanup:
mpi_free( &TB, &TA, &TG, NULL );
return( ret );
}
/*
* Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
*
* Returns 0 if successful
* 1 if memory allocation failed
* ERR_MPI_INVALID_PARAMETER if N is negative or nil
* ERR_MPI_NOT_INVERTIBLE if A has no inverse mod N
*/
int mpi_inv_mod( mpi *X, mpi *A, mpi *N )
{
int ret;
mpi TA, TU, U1, U2, TB, TV, V1, V2;
if( mpi_cmp_int( N, 0 ) <= 0 )
return( ERR_MPI_INVALID_PARAMETER );
if( ( A->p[0] & 1 ) == 0 &&
( N->p[0] & 1 ) == 0 )
return( ERR_MPI_NOT_INVERTIBLE );
mpi_init( &TA, &TU, &U1, &U2,
&TB, &TV, &V1, &V2, NULL );
CHK( mpi_mod_mpi( &TA, A, N ) );
CHK( mpi_copy( &TU, &TA ) );
CHK( mpi_copy( &TB, N ) );
CHK( mpi_copy( &TV, N ) );
CHK( mpi_lset( &U1, 1 ) );
CHK( mpi_lset( &U2, 0 ) );
CHK( mpi_lset( &V1, 0 ) );
CHK( mpi_lset( &V2, 1 ) );
do
{
while( ( TU.p[0] & 1 ) == 0 )
{
CHK( mpi_shift_r( &TU, 1 ) );
if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
{
CHK( mpi_add_mpi( &U1, &U1, &TB ) );
CHK( mpi_sub_mpi( &U2, &U2, &TA ) );
}
CHK( mpi_shift_r( &U1, 1 ) );
CHK( mpi_shift_r( &U2, 1 ) );
}
while( ( TV.p[0] & 1 ) == 0 )
{
CHK( mpi_shift_r( &TV, 1 ) );
if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
{
CHK( mpi_add_mpi( &V1, &V1, &TB ) );
CHK( mpi_sub_mpi( &V2, &V2, &TA ) );
}
CHK( mpi_shift_r( &V1, 1 ) );
CHK( mpi_shift_r( &V2, 1 ) );
}
if( mpi_cmp_mpi( &TU, &TV ) >= 0 )
{
CHK( mpi_sub_mpi( &TU, &TU, &TV ) );
CHK( mpi_sub_mpi( &U1, &U1, &V1 ) );
CHK( mpi_sub_mpi( &U2, &U2, &V2 ) );
}
else
{
CHK( mpi_sub_mpi( &TV, &TV, &TU ) );
CHK( mpi_sub_mpi( &V1, &V1, &U1 ) );
CHK( mpi_sub_mpi( &V2, &V2, &U2 ) );
}
}
while( mpi_cmp_int( &TU, 0 ) != 0 );
if( mpi_cmp_int( &TV, 1 ) == 0 )
{
while( mpi_cmp_int( &V1, 0 ) < 0 )
CHK( mpi_add_mpi( &V1, &V1, N ) );
while( mpi_cmp_mpi( &V1, N ) >= 0 )
CHK( mpi_sub_mpi( &V1, &V1, N ) );
CHK( mpi_copy( X, &V1 ) );
}
else
ret = ERR_MPI_NOT_INVERTIBLE;
cleanup:
mpi_free( &V2, &V1, &TV, &TB,
&U2, &U1, &TU, &TA, NULL );
return( ret );
}
int small_prime[] = {
3, 113, 271, 443, 619, 821, 1013, 1213, 1429, 1609, 1831,
5, 127, 277, 449, 631, 823, 1019, 1217, 1433, 1613, 1847,
7, 131, 281, 457, 641, 827, 1021, 1223, 1439, 1619, 1861,
11, 137, 283, 461, 643, 829, 1031, 1229, 1447, 1621, 1867,
13, 139, 293, 463, 647, 839, 1033, 1231, 1451, 1627, 1871,
17, 149, 307, 467, 653, 853, 1039, 1237, 1453, 1637, 1873,
19, 151, 311, 479, 659, 857, 1049, 1249, 1459, 1657, 1877,
23, 157, 313, 487, 661, 859, 1051, 1259, 1471, 1663, 1879,
29, 163, 317, 491, 673, 863, 1061, 1277, 1481, 1667, 1889,
31, 167, 331, 499, 677, 877, 1063, 1279, 1483, 1669, 1901,
37, 173, 337, 503, 683, 881, 1069, 1283, 1487, 1693, 1907,
41, 179, 347, 509, 691, 883, 1087, 1289, 1489, 1697, 1913,
43, 181, 349, 521, 701, 887, 1091, 1291, 1493, 1699, 1931,
47, 191, 353, 523, 709, 907, 1093, 1297, 1499, 1709, 1933,
53, 193, 359, 541, 719, 911, 1097, 1301, 1511, 1721, 1949,
59, 197, 367, 547, 727, 919, 1103, 1303, 1523, 1723, 1951,
61, 199, 373, 557, 733, 929, 1109, 1307, 1531, 1733, 1973,
67, 211, 379, 563, 739, 937, 1117, 1319, 1543, 1741, 1979,
71, 223, 383, 569, 743, 941, 1123, 1321, 1549, 1747, 1987,
73, 227, 389, 571, 751, 947, 1129, 1327, 1553, 1753, 1993,
79, 229, 397, 577, 757, 953, 1151, 1361, 1559, 1759, 1997,
83, 233, 401, 587, 761, 967, 1153, 1367, 1567, 1777, 1999,
89, 239, 409, 593, 769, 971, 1163, 1373, 1571, 1783, 2003,
97, 241, 419, 599, 773, 977, 1171, 1381, 1579, 1787, 2011,
101, 251, 421, 601, 787, 983, 1181, 1399, 1583, 1789, 2017,
103, 257, 431, 607, 797, 991, 1187, 1409, 1597, 1801, 2027,
107, 263, 433, 613, 809, 997, 1193, 1423, 1601, 1811, 2029,
109, 269, 439, 617, 811, 1009, 1201, 1427, 1607, 1823, -5 };
/*
* Miller-Rabin primality test (HAC 4.24)
*
* Returns 0 if probably prime
* 1 if memory allocation failed
* ERR_MPI_IS_COMPOSITE if X is not prime
*/
int mpi_is_prime( mpi *X )
{
int ret, i, j, s, xs;
mpi W, R, T, A;
if( mpi_cmp_int( X, 0 ) == 0 )
return( 0 );
mpi_init( &W, &R, &T, &A, NULL );
xs = X->s; X->s = 1;
/*
* test trivial factors first
*/
if( ( X->p[0] & 1 ) == 0 )
return( ERR_MPI_IS_COMPOSITE );
for( i = 0; small_prime[i] > 0; i++ )
{
t_int r;
if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
return( 0 );
CHK( mpi_mod_int( &r, X, small_prime[i] ) );
if( r == 0 )
return( ERR_MPI_IS_COMPOSITE );
}
/*
* W = |X| - 1
* R = W >> lsb( W )
*/
CHK( mpi_sub_int( &W, X, 1 ) );
CHK( mpi_copy( &R, &W ) );
CHK( mpi_shift_r( &R, s = mpi_lsb( &W ) ) );
for( i = 0; i < 8; i++ )
{
/*
* pick a random A, 1 < A < |X| - 1
*/
CHK( mpi_grow( &A, X->n ) );
for( j = 0; j < A.n; j++ )
A.p[j] = (t_int) rand() * rand();
CHK( mpi_shift_r( &A, mpi_size( &A ) -
mpi_size( &W ) + 1 ) );
A.p[0] |= 3;
/*
* A = A^R mod |X|
*/
CHK( mpi_exp_mod( &A, &A, &R, X ) );
if( mpi_cmp_mpi( &A, &W ) == 0 ||
mpi_cmp_int( &A, 1 ) == 0 )
continue;
j = 1;
while( j < s && mpi_cmp_mpi( &A, &W ) != 0 )
{
/*
* A = A * A mod |X|
*/
CHK( mpi_mul_mpi( &T, &A, &A ) );
CHK( mpi_mod_mpi( &A, &T, X ) );
if( mpi_cmp_int( &A, 1 ) == 0 )
break;
j++;
}
/*
* not prime if A != |X| - 1 or A == 1
*/
if( mpi_cmp_mpi( &A, &W ) != 0 || j < s )
{
ret = ERR_MPI_IS_COMPOSITE;
break;
}
}
cleanup:
X->s = xs;
mpi_free( &A, &T, &R, &W, NULL );
return( ret );
}
/*
* Generate a prime number of nbits in size -- set
* need_dh_prime to 1 if (X-1)/2 must also be prime.
*
* Function "rng_func" takes one argument (rng_state)
* and should return a random unsigned long.
*
* Returns 0 if generation was successful
* 1 if memory allocation failed
* ERR_MPI_INVALID_PARAMETER if nbits is < 3
*/
int mpi_gen_prime( mpi *X, uint nbits, int need_dh_prime,
ulong (*rng_func)(void *), void *rng_state )
{
int ret;
uint k, n;
mpi Y;
if( nbits < 3 )
return( ERR_MPI_INVALID_PARAMETER );
mpi_init( &Y, NULL );
n = BITS_TO_LIMBS( nbits );
CHK( mpi_grow( X, n ) );
CHK( mpi_lset( X, 0 ) );
for( k = 0; k < n; k++ )
X->p[k] = rng_func( rng_state )
* rng_func( rng_state );
k = mpi_size( X );
if( k < nbits ) CHK( mpi_shift_l( X, nbits - k ) );
if( k > nbits ) CHK( mpi_shift_r( X, k - nbits ) );
X->p[0] |= 3;
if( need_dh_prime == 0 )
{
while( ( ret = mpi_is_prime( X ) ) != 0 )
{
if( ret != ERR_MPI_IS_COMPOSITE )
goto cleanup;
CHK( mpi_add_int( X, X, 2 ) );
}
}
else
{
CHK( mpi_sub_int( &Y, X, 1 ) );
CHK( mpi_shift_r( &Y, 1 ) );
while( 1 )
{
if( ( ret = mpi_is_prime( X ) ) == 0 )
{
if( ( ret = mpi_is_prime( &Y ) ) == 0 )
break;
if( ret != ERR_MPI_IS_COMPOSITE )
goto cleanup;
}
if( ret != ERR_MPI_IS_COMPOSITE )
goto cleanup;
CHK( mpi_add_int( &Y, X, 1 ) );
CHK( mpi_add_int( X, X, 2 ) );
CHK( mpi_shift_r( &Y, 1 ) );
}
}
cleanup:
mpi_free( &Y, NULL );
return( ret );
}
#ifdef SELF_TEST
/*
* Checkup routine
*/
int mpi_self_test( void )
{
int ret;
mpi A, E, N, X, Y, U, V;
mpi_init( &A, &E, &N, &X, &Y, &U, &V, NULL );
CHK( mpi_read( &A, "EFE021C2645FD1DC586E69184AF4A31E" \
"D5F53E93B5F123FA41680867BA110131" \
"944FE7952E2517337780CB0DB80E61AA" \
"E7C8DDC6C5C6AADEB34EB38A2F40D5E6", 16 ) );
CHK( mpi_read( &E, "B2E7EFD37075B9F03FF989C7C5051C20" \
"34D2A323810251127E7BF8625A4F49A5" \
"F3E27F4DA8BD59C47D6DAABA4C8127BD" \
"5B5C25763222FEFCCFC38B832366C29E", 16 ) );
CHK( mpi_read( &N, "0066A198186C18C10B2F5ED9B522752A" \
"9830B69916E535C8F047518A889A43A5" \
"94B6BED27A168D31D4A52F88925AA8F5", 16 ) );
CHK( mpi_mul_mpi( &X, &A, &N ) );
CHK( mpi_read( &U, "602AB7ECA597A3D6B56FF9829A5E8B85" \
"9E857EA95A03512E2BAE7391688D264A" \
"A5663B0341DB9CCFD2C4C5F421FEC814" \
"8001B72E848A38CAE1C65F78E56ABDEF" \
"E12D3C039B8A02D6BE593F0BBBDA56F1" \
"ECF677152EF804370C1A305CAF3B5BF1" \
"30879B56C61DE584A0F53A2447A51E", 16 ) );
printf( " MPI test #1 (mul_mpi): " );
if( mpi_cmp_mpi( &X, &U ) != 0 )
{
mpi_show( "X", &X, 16 );
mpi_show( "U", &U, 16 );
printf( "failed\n" );
return( 1 );
}
printf( "passed\n" );
CHK( mpi_div_mpi( &X, &Y, &A, &N ) );
CHK( mpi_read( &U, "256567336059E52CAE22925474705F39A94", 16 ) );
CHK( mpi_read( &V, "6613F26162223DF488E9CD48CC132C7A" \
"0AC93C701B001B092E4E5B9F73BCD27B" \
"9EE50D0657C77F374E903CDFA4C642", 16 ) );
printf( " MPI test #2 (div_mpi): " );
if( mpi_cmp_mpi( &X, &U ) != 0 ||
mpi_cmp_mpi( &Y, &V ) != 0 )
{
printf( "failed\n" );
return( 1 );
}
printf( "passed\n" );
CHK( mpi_exp_mod( &X, &A, &E, &N ) );
CHK( mpi_read( &U, "36E139AEA55215609D2816998ED020BB" \
"BD96C37890F65171D948E9BC7CBAA4D9" \
"325D24D6A3C12710F10A09FA08AB87", 16 ) );
printf( " MPI test #3 (exp_mod): " );
if( mpi_cmp_mpi( &X, &U ) != 0 )
{
printf( "failed\n" );
return( 1 );
}
printf( "passed\n" );
CHK( mpi_inv_mod( &X, &A, &N ) );
CHK( mpi_read( &U, "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
"C3DBA76456363A10869622EAC2DD84EC" \
"C5B8A74DAC4D09E03B5E0BE779F2DF61", 16 ) );
printf( " MPI test #4 (inv_mod): " );
if( mpi_cmp_mpi( &X, &U ) != 0 )
{
printf( "failed\n" );
return( 1 );
}
printf( "passed\n" );
cleanup:
if( ret != 0 )
printf( "Unexpected error, return code = %d\n", ret );
mpi_free( &V, &U, &Y, &X, &N, &E, &A, NULL );
printf( "\n" );
return( 0 );
}
#else
int mpi_self_test( void )
{
printf( "MPI self-test not available\n\n" );
return( 1 );
}
#endif
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -