一个RSA加密算法。
这个算法参考了多个资源。还有自己的改变。RSA.cpp#include <iostream>
#include <ctime>
#include "HugeInt.h"
#include "Random.h"
// Compute x^n ( mod p ).
// HugeInt: must have copy constructor, operator=,
// conversion from int, *, /, %, ==, and !=
// Assumes that p is not zero and power( 0, 0, p ) is 1
HugeInt power( const HugeInt & x, const HugeInt & n , const HugeInt & p )
{
if( n == 0 )
return 1;
HugeInt tmp = power( ( x * x ) % p, n / 2, p );
if( n % 2 != 0 )
tmp = ( tmp * x ) % p;
return tmp;
}
// Probabilistic primality testing routine.
// If witness does not return 1, n is definitely composite.
// Do this by computing a^i ( mod n ) and looking for
// non-trivial square roots of 1 along the way.
// HugeInt: must have copy constructor, operator=,
// conversion from int, *, /, -, %, ==, and !=
HugeInt witness( const HugeInt & a, const HugeInt & i, const HugeInt & n )
{
if( i == 0 )
return 1;
HugeInt x = witness( a, i / 2, n );
if( x == 0 ) // If n is recursively composite, stop
return 0;
// n is not prime if we find a nontrivial square root of 1
HugeInt y = ( x * x ) % n;
if( y == 1 && x != 1 && x != n - 1 )
return 0;
if( i % 2 == 1 )
y = ( a * y ) % n;
return y;
}
// Make NUM_TRIALS calls to witness to check if n is prime.
bool isPrime( const HugeInt & n )
{
const int NUM_TRIALS = 5;
Random rnd;
for( int counter = 0; counter < NUM_TRIALS; counter++ )
if( witness( rnd.randomInt( 2, n ) , n - 1, n ) != 1 )
return false;
return true;
}
// Returns the greatest common divisor of a and b.
HugeInt gcd( const HugeInt & a, const HugeInt & b )
{
if( b == 0 )
return a;
else
return gcd( b, a % b );
}
// Given a and b, assume gcd( a, b ) = 1.
// Find x and y such thata x + b y = 1.
// HugeInt: must have copy constructor,
// zero-parameter constructor, operator=,
// conversion from int, *, /, +, -, %, ==, and >
void fullGcd( const HugeInt & a, const HugeInt & b,
HugeInt & x, HugeInt & y )
{
HugeInt x1, y1;
if( b == 0 )
{
x = 1; // If a != 1, there is no inverse
y = 0; // We omit this check
}
else
{
fullGcd( b, a % b, x1, y1 );
x = y1;
y = x1 - ( a / b ) * y1;
}
}
// GetPrime randomly picks a large, odd number until it gets
// one that is prime. It uses is_prime to check for primality.
// The more failed primes that occur, the larger the N becomes.
HugeInt GetPrime( )
{
Random rnd(time(0));
HugeInt N = rnd.randomInt( 1000000000, INT_MAX );
HugeInt NN = rnd.randomInt( 1000000000, INT_MAX );
HugeInt multiplier(1314521);
N = N * NN * N * multiplier;
HugeInt Odd = 2;
if ( N % 2 == 0 )
N = N+1;
while ( !isPrime( N )){
N = N + Odd;
}
return N;
}
// Solve a x == 1 ( mod n ).
// Assume that gcd( a, n ) = 1.
HugeInt inverse( const HugeInt & a, const HugeInt & n )
{
HugeInt x, y;
fullGcd( a, n, x, y );
return x > 0 ? x : x + n;
}
// Illustrate an RSA computation
int main( )
{
// Sample of how RSA works.
HugeInt p = GetPrime();
HugeInt q = GetPrime();
HugeInt message, code, decode;
HugeInt n, nPrime, e, d;
std::string myletter = "For my friends!";
message.rsa(myletter);
std::cout <<"p: " << p << std::endl;
std::cout <<"q: " << q << std::endl;
n = p * q;
std::cout <<"n: " << n << std::endl;
nPrime = ( p - 1 ) * ( q - 1 );
std::cout <<"nprime: " << nPrime << std::endl;
for( e = nPrime/521; gcd( e, nPrime ) != 1; e++ );
std::cout <<"e: " << e << std::endl;
d = inverse( e, nPrime );
std::cout <<"d: " << d << std::endl;
std::cout << "Verify inverse: " << ( e * d % ( nPrime ) ) << std::endl;
std::cout << "message: " << myletter << std::endl;
code = power( message, e, n );
decode = power( code, d, n );
std::cout << "Code: " << code << std::endl;
std::cout << "Decode: " << decode.asr() << std::endl;
if( message != decode )
std::cout << "OOPS: " << std::endl;
else
std::cout << "Success!!!!" << std::endl;
return 0;
}**** Hidden Message *****
RSA方法源于Mark Allen Weiss的实现。
看看，呃呃呃 由于发帖字数限制，完全的源代码只有回复下载了才能看到。这里可以提供运行过后的一个截图。很成功的~
支持楼主这个挺好 研究研究 hhhhhhhhh呵呵呵 回帖是一种美德 回帖是一种美德 这东西不错呀，非常感谢楼主分享。。。！ 谢谢分享 感谢楼主无私分享！！！！！ 谢谢分享~ 顶顶顶顶顶顶顶 一句话，支持你，支持开源，支持原创。 很好噶 感谢楼主无私分享！！ 看看。。。。。。。。。。。。。。。 学习一下。。。 四处找资料，，恶补知识 谢谢分享，辛苦了 谢谢分享！学习它。
页:
[1]
2