rsa.cpp

RSA C++源代码DEMO,附加DESMD5等众多算法

/*************************************************************************
**                                                                      **
**  rsa.cxx                                                             **
**                                                                      **
**  RIVEST CIPHER FOUR (RC4) RANDOM NUMBER GENERATOR AND STREAM CIPHER  **
**                                                                      **
**  Copyright (c)1996 Markku-Juhani O. Saarinen <[e-mail]>      **
**                                                                      **
*************************************************************************/
// Header File

#include "rsa.h"
#include "rc4.h"

//   b 
//  a mod n = ?

kbn& modexp (kbn a, kbn b, kbn n)
{
    static kbn r;
    int i, explen;
    
    r = 1;  
    explen = b.log2();
    
    for(i=0; i<=explen; i++)
    { 
        if ( b.testbit(i) )
            r = (r*a) % n;
        a = a.sqr() % n;
    }
    return r;
}

//  Greatest Common Divisor

kbn& gcd(kbn a, kbn b)
{
    static kbn g0, g1, g2, zero; 

    g0 = a;
    g1 = b;
    zero = 0;
    
    while ( g1 != zero )
    { 
        g2 = g0 % g1;
        g0 = g1;
        g1 = g2; 
    }
    
    return g0;
}

//  ab mod n = 1 ===> b=?

kbn& inverse (kbn a, kbn n)
{
    static kbn u1, u3, v1, v3, t1, t3, q, w, zero;
    int sign;

    zero = 0;

    u1 = 1;
    u3 = a;
    v1 = 0;
    v3 = n;
    
    sign = 0;

    while( v3 != zero )
    {       
        q = u3 / v3;
        t3 = u3 % v3;
        w = q * v1;
        t1 = u1 + w;
        u1 = v1;
        v1 = t1;
        u3 = v3;
        v3 = t3;
        
        sign = !sign;
    }
        
    if (sign)
        u1 = n - u1;
        
    return u1;
}

//  random(0 ~ max-1)

kbn& rc4rand(kbn *max)
{
    static TRC4 r;
    unsigned char p[1024];
    static kbn x;
    int len;

    len = (max->log2() >> 3) + 1;
    r.rand(p, len);
    x.load(p, len);
    vbzero(p, len);          // vektori nollataan, jotta muistiin ei j鋓si
    x %= *max;

    return x;
}

//  test whether n is prime

int prob_primetest (kbn *n)
{
    static kbn q, y, one;
    int j, k;
         
    one = 1;
    j = 0;
   
    //     k
    //  2 q + 1 = n, q mod 2 = 1 ===> q = ?
    for(k=1; !(n->testbit(k)); k++);
    q = *n >> k;
    
    y = rc4rand( n );                   // y satunnaisluku v鋖ill