rsa公钥密码的实现,这个实现的目的是展示SystemC的任意精度类型的用法。SystemC中的数据类型可以用于实现关于任意精度整数的算法示例。这里使用的算法不是最有效的，仅仅是用于解释目的。
SystemC自带example的系列:
SystemC自带example的pipe研习
SystemC自带example的pkt_switch研习
SystemC自带example的simple_perf研习
————————————————
1 rsa背景知识RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
即：素数p>1是一个只有两个除数的整数，1和p本身。例如，2、3、5、7和11都是素数。如果p不是质数，则称为复合数。
如果给定两个素数p和q，很容易找到它们的乘积p*q；然而，如果给我们一个数m，它恰好是我们不知道的两个素数p和q的乘积，如果m很大，就很难找到p和q，也就是说，很难计算m的因子。下面是百科中有关算法的具体描述：
rsa算法描述
2 任意精度整数任意精度整数类型sc_bigint<NBITS>，位宽任意-精度可达任意的整数类型。函数inline void rand_bitstr( char *str, int nbits )即是产生一个大于0的nbits位宽的整数。将char *str的值直接赋值给bigint定义的变量即可。
#define DEBUG_SYSTEMC // #undef this to disable assertions.
#define NBITS 300
#define HALF_NBITS ( NBITS / 2 )
#define STR_SIZE ( NBITS 2 )
#define HALF_STR_SIZE ( HALF_NBITS 2 )
typedef sc_bigint<NBITS> bigint;
// Generate "111..111" with nbits bits for masking.
// str has a length of nbits 1.
inline void max_bitstr( char *str, int nbits )
{
assert( nbits >= 4 );
str[ 0 ] = '0';
str[ 1 ] = 'b';
str[ 2 ] = '0'; // Sign for positive numbers.
for ( int i = 3; i < nbits; i )
str[ i ] = '1';
str[ nbits ] = '\0';
}
// 随机产生一个任意nbits位宽的整数
inline bool flip( double p )
{
const int MAX_VAL = ( 1 << 15 );
return ( rand() < ( int ) ( p * MAX_VAL ) );
}
inline void rand_bitstr( char *str, int nbits )
{
assert( nbits >= 4 );
str[ 0 ] = '0';
str[ 1 ] = 'b';
str[ 2 ] = '0'; // Sign for positive numbers.
for ( int i = 3; i < nbits; i )
str[ i ] = ( flip( 0.5 ) == true ? '1' : '0' );
str[ nbits ] = '\0';
}
看看是如何寻找一个大素数的：随机的生成一个大数，然后使用米勒-拉宾素性测试在其附近寻找一个素数。
inline bool witness( const bigint& a, const bigint& n )
{
bigint n_minus1 = n - 1;
bigint x;
bigint d = 1;
// Compute d = a^( n-1 ) % n.
for ( int i = n.length() - 1; i >= 0; --i )
{
if(d<0)
{
x = -d;
assert(x==-d);
}
else
{
x = d;
assert(x==d);
}
d = ( d * d ) % n;
// x is a nontrivial square root of 1 modulo n ==> n is composite.
if ( ( abs_val( d ) == 1 ) && ( x != 1 ) && ( x != n_minus1 ) )
return true;
if ( n_minus1[ i ] )
d = ( d * a ) % n;
}
// d = a^( n-1 ) % n != 1 ==> n is composite.
if ( abs_val( d ) != 1 )
return true;
return false;
}
inline bool div_test( const bigint& n )
{
int limit;
if ( n < 1023 )
limit = n.to_int() - 2;
else
limit = 1023;
for ( int i = 3; i <= limit; i = 2 ) {
if ( n % i == 0 )
return false; // n is composite.
}
return true; // n may be prime.
}
inline bool miller_rabin( const bigint& n )
{
if ( n <= 2 )
return false;
if ( ! div_test( n ) )
return false;
char str[ STR_SIZE 1 ];
int s = 50;
for ( int j = 1; j <= s; j ) {
// Choose a random number.
rand_bitstr( str, STR_SIZE );
// Set a to the chosen number.
bigint a = str;
// Make sure that a is in [ 1, n - 1 ].
a = ( a % ( n - 1 ) ) 1;
// Check to see if a is a witness.
if ( witness( a, n ) )
return false; // n is definitely composite.
}
return true; // n is almost surely prime.
}
inline bigint find_prime( const bigint& r )
{
char p_str[ HALF_STR_SIZE 1 ];
rand_bitstr( p_str, HALF_STR_SIZE );
p_str[ HALF_STR_SIZE - 1 ] = '1'; // Force p to be an odd number.
bigint p = p_str;
#ifdef DEBUG_SYSTEMC
assert( ( p > 0 ) && ( p % 2 == 1 ) );
#endif
#ifdef DEBUG_SYSTEMC
// A very large counter to check against infinite loops.
sc_bigint<NBITS> niter = 0;
#endif
while ( ! miller_rabin( p ) ) {
p = ( p 2 ) % r;
#ifdef DEBUG_SYSTEMC
assert( niter > 0 );
#endif
}
return p;
}
任意选取两个不同的大素数p和q。并且计算n和m。
// Find two large primes p and q.
bigint p = find_prime( r );
bigint q = find_prime( r );
// Compute n and ( p - 1 ) * ( q - 1 ) = m.
bigint n = p * q;
bigint m = ( p - 1 ) * ( q - 1 );
任意选取一个大整数e，整数e用作加密钥，e的选取是很容易的所有大于p和q的素数都可用。
bigint gcd( const bigint& a, const bigint& b )
{
if ( b == 0 )
return a;
return gcd( b, a % b );
}
inline bigint find_rel_prime( const bigint& n )
{
bigint a = 3;
while ( true ) {
if ( gcd( a, n ) == 1 )
break;
a = 2;
#ifdef DEBUG_SYSTEMC
assert( a < n );
#endif
}
return a;
}
// Find a small odd integer e that is relatively prime to m.
bigint e = find_rel_prime( m );
确定解密密钥d，e的逆乘再模上m即可。
void euclid( const bigint& a, const bigint& b, bigint& d, bigint& x, bigint& y )
{
if ( b != 0 ) {
euclid( b, a % b, d, x, y );
bigint tmp = x;
x = y;
y = tmp - ( a / b ) * y;
}
else {
d = a;
x = 1;
y = 0;
}
}
// Return a positive remainder.
inline bigint ret_pos( const bigint& x, const bigint& n )
{
if ( x < 0 )
return x n;
return x;
}
inline bigint inverse( const bigint& a, const bigint& n )
{
bigint d, x, y;
euclid( a, n, d, x, y );
assert( d == 1 );
x %= n;
return ret_pos( x, n );
}
// Find the multiplicative inverse d of e, modulo m.
bigint d = inverse( e, m );
公开整数n和e，秘密保存d。加密明文直接使用明文的e次幂mod n即可。
// Return d = a^b % n, where ^ represents exponentiation.
inline bigint modular_exp( const bigint& a, const bigint& b, const bigint& n )
{
bigint d = 1;
for ( int i = b.length() - 1; i >= 0; --i )
{
d = ( d * d ) % n;
if ( b[ i ] )
d = ( d * a ) % n;
}
return ret_pos( d, n );
}
// Encode or cipher the message in msg using the RSA public key P=( e, n ).
inline bigint cipher( const bigint& msg, const bigint& e, const bigint& n )
{
return modular_exp( msg, e, n );
}
// Cipher and decipher a randomly generated message msg.
char msg_str[ STR_SIZE 1 ];
rand_bitstr( msg_str, STR_SIZE );
bigint msg = msg_str;
cout << "Message to be ciphered = " << endl;
cout << msg << endl;
bigint msg2 = cipher( msg, e, n );
解密直接使用秘文的d次幂mod n即可。
// Dencode or decipher the message in msg using the RSA secret key S=( d, n ).
inline bigint decipher( const bigint& msg, const bigint& d, const bigint& n )
{
return modular_exp( msg, d, n );
}
msg2 = decipher( msg2, d, n );
示例过程较为清晰，使用的算法也不是最有效的，这里仅仅用于解释SystemC中的数据类型可以用于实现关于任意精度整数的算法示例。
,
