RSA實現步驟

選擇大素數

任意選擇兩個素數p q，這兩個素數應是保密的。一般情況下選擇100~200位的十進制數。令n = p×q，再計算n的歐拉函數ψ(n)=(p-1)×(q-1)。這幾個數中，n可以公開。

生成公鑰私鑰密鑰對

隨機選擇一個與ψ(n)互素的整數e作為公鑰(Public key)，再根據算式e × d = 1 (mod ψ(n))，計算出d作為私鑰(Private key)。這是一個求乘法逆元的過程。私鑰是保密的，公鑰是公開的。

發佈密鑰

私鑰(d, n)保密，公鑰(e, n)公開即可。

加密與解密

加密時，先將明文比特串分組，使每個分組的十進制數小於n（即比特串分組長度小於log2(n)），然後對每個明文分組m加密運算：

c = m^e mod n

解密同理，對密文分組進行解密運算：

m = c^d mod n

數學證明

∵c = m^e mod n
∴c^d mod n = m^(ed) mod n
∵ed = 1 (mod ψ(n))
∴ed = kψ(n) + 1
∴c^d mod n = m^(kψ(n) + 1) mod n

①当m n互素時

由歐拉定理可得：
m^(ψ(n)) mod n = 1
∴m^(kψ(n)) mod n = 1
∴m^(kψ(n) + 1) mod n = m
即m^(ed) mod n = m
得證

②当m n不互素情況概率小於1/p + 1/q，故可以不做考慮。（本身也可以證明，不過較為繁瑣）

演示代碼

寫了一個不好看的C++演示代码，有興趣的可以試試看

#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<windows.h>
#include<sstream>
#include<string>
using namespace std;

long int gcd(long int a, long int b){
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

double random(double start, double end){
    return start+(end-start)*rand()/(RAND_MAX + 1.0);
}

long int fastModel(long int base, long int power, long int model){
    long int temp = 1;
    long int result = 0;

    while(power != 1){
        if(power % 2 == 0){
            power /= 2;
            base = base*base % model;
            //cout<<"/2\n"<<base<<" "<<power<<" "<<model<<" "<<"\n";
        }
        else if(power % 2 != 0){
            power -= 1;
            temp = temp*base % model;
            //cout<<"-1\n"<<base<<" "<<power<<" "<<model<<" "<<"\n";
        }
    }
    result = temp * base % model;
    if (result <= 0){
        result += model;
    }
    return (long int)result;
}

bool isPrime(long int t){
    long int r = 0;
    long int d = t-1;
    if(t%2 == 0 and t != 2){
        return false;
    }
    else if(t == 2){
        return true;
    } 
    else{
        do{
            r++;
            d /= 2;
            //cout<<d<<"\n";
            if (fastModel(2, d, t) != 1){
               if (fastModel(2, d, t) != t-1){
                   return false;
               }
               else{
                   return true;
               }
            } 
        }
        while( d % 2 == 0);
    }
    return true;
}

long int ranFakePrime(){
    long int t;
    srand(unsigned(time(0)));
    do{
        t = random(10, 150);
    }
    while( fastModel(2, t-1, t) != 1 );
    return t;
}

long int generatePrime(){

    long int t;
    do{
        t = ranFakePrime();
    }
    while( !isPrime(t) );
    return t;
}

long int getOpposite(long int a, long int n){
    long int Q, X1, X2, X3, Y1, Y2, Y3, T1, T2, T3;
    X1=1;X2=0;X3=n;Y1=0;Y2=1;Y3=a;
    while(Y3 != 0 and Y3 != 1){
        Q = X3/Y3;
        T1 = X1 - Q * Y1;
        T2 = X2 - Q * Y2;
        T3 = X3 - Q * Y3;
        X1 = Y1; X2 = Y2; X3 = Y3;
        Y1 = T1; Y2 = T2; Y3 = T3;
    }
    if (Y3 == 1){
        if (Y2 < 0){
            return n + Y2;
        }
        else{
            return Y2;
        }
    }
    else{
        return 0;
    }
}

string rsaEncrypt(string ori_str, long int en_key, long int n){
    stringstream en_str;
    long int t;
    for (int i = 0; i!= ori_str.length(); i++){
        t = fastModel(int(ori_str[i]), en_key, n);
        //cout<<"...";
        en_str<<t<<"_";
    }
    return en_str.str();
}

string rsaDecrypt(string ori_str, long int de_key, long int n){
    stringstream de_str, tstr;
    long int t;
    for (int i = 0; i!= ori_str.length(); i++){ 
        if(ori_str[i] == '_'){
            tstr>>t;
            de_str<<char(fastModel(t, de_key, n));
            tstr.str("");
            tstr.clear();
        }
        else{
            tstr<<ori_str[i];
        } 
    }
    return de_str.str();
}

int main(){
    long int p, q, n, fn, pub, pri;
    p = generatePrime();
    Sleep(1000);
    q = generatePrime();
    n = p*q;
    fn = (p-1)*(q-1);

    //Print primes
    cout<<"p = "<<p<<" "<<"q = "<<q<<"\n";
    cout<<"n = "<<n<<" "<<"fn = "<<fn<<"\n\n";

    //Generate public key
    do{
        pub = random(p,n);
    } 
    while(gcd(pub, fn) != 1);
    //Generate private key
    pri = getOpposite(pub, fn);
    //Print keys
    cout<<"pub-key = "<<pub<<" "<<"pri-key = "<<pri<<"\n\n";

    string ori_str, en_str, de_str;
    char method_str;
    bool ex = true;
    int method;
    do{
        cin>>method_str;
        method = int(method_str);
        switch(method){
            case 'e':
                cin>>ori_str;
                cout<<rsaEncrypt(ori_str, pub, n)<<"\n";
                break;
            case 'd':
                cin>>ori_str;
                cout<<rsaDecrypt(ori_str, pri, n)<<"\n";
                break;
            default:
                ex = false;
                break;
        }
    } 
    while(ex);

    return 0;
}