一个RSA加密算法。

andalousie

这个算法参考了多个资源。还有自己的改变。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 that  a 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;
}

游客，如果您要查看本帖隐藏内容请回复

RSA方法源于Mark Allen Weiss的实现。

183560656

看看，呃呃呃

andalousie

由于发帖字数限制，完全的源代码只有回复下载了才能看到。这里可以提供运行过后的一个截图。很成功的~

bulangzhe

支持楼主  这个挺好 研究研究

2014On_The_Way

hhhhhhhhh呵呵呵

黑暗漩涡

回帖是一种美德

黑暗漩涡

回帖是一种美德

章伯魂

这东西不错呀，非常感谢楼主分享。。。！

irvine726

谢谢分享

jsqking99

感谢楼主无私分享！！！！！

irvine726

谢谢分享~

郭兴华

顶顶顶顶顶顶顶

wyds591101

一句话，支持你，支持开源，支持原创。

王虬鹏

很好噶

jsqking99

感谢楼主无私分享！！

xykj2011

看看。。。。。。。。。。。。。。。

OSKer

学习一下。。。

dAb

四处找资料，，恶补知识

fabuer

谢谢分享，辛苦了

我是桃川人

谢谢分享！学习它。