簡介

RSA公開密鑰密碼體制於1978年提出，名字來源於提出者名字縮寫。這種密碼體制由數論構造，是迄今為止理論上最為成熟完善的密碼體制，安全性能目前看來依然良好，並且應用十分廣泛。密碼體制一般基於數學難題，RSA也不例外。
RSA是基於大整數分解的難題。給定整數e和c，尋找滿足條件的m，使得c = m^e mod N。

基礎知識

RSA基於以下數論內容

• 歐拉函數
• 同餘
• 擴展歐幾裡德算法
• 一次同餘式及其求解
• 費馬小定理（或歐拉定理）

算法

求最大公約數（Greatest Common Divisor）

通過類輾轉相除法

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

快速指數算法

由模運算性質

[(a mod n) + (b mod n)] mod n = (a + b) mod n
[(a mod n) × (b mod n)] mod n = (a × b) mod n

可以簡化運算。

例如求 3^19 mod 7
= 3×3^18 mod 7
= 3×(3^2)^9 mod 7
= 3×(9 mod 7)^9 mod 7
= 3×2^9 mod 7
= 6×2^8 mod 7
= 6×4^4 mod 7
= 6×(16 mod 7)^2 mod 7
...
= 3

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;
        }
        else if(power % 2 != 0){
            power -= 1;
            temp = temp * base % model;
        }
    }
    result = temp * base % model;
    if (result <= 0){
        result += model;
    }
    return (long int)result;
}

計算乘法逆元（解一次同餘式）

已知a，n，ax ≡ 1 (mod n)，求x。
①定義X1，X2，X3，Y1，Y2，Y3。令（X1，X2，X3）=（1，0，n）；（Y1，Y2，Y3）=（0，1，a）。
②令Q = X3/Y3（不留小數點）
③令（T1，T2，T3）=（X1-Q×Y1，X2-Q×Y2，X3-Q×Y3）；（X1，X2，X3）=（Y1，Y2，Y3）；（Y1，Y2，Y3）=（T1，T2，T3）
④迴圈這一步，直到Y3 = 1或0。如果為0，則無解；如果為1，則解為Y2。

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;
    }
}

偽素數的生成

RSA加密需要生成大素數作為初始的n的來源。我們不可能用每個數字進行素數判斷。
由費馬小定理可知，a^(p - 1) ≡ 1 (mod p)。如果一個數為素數，那麼它一定滿足這個條件。這是一個數為素數的必要條件但非充分條件。但是，如果先用這種方法將其他無用的數排除，將縮短尋找大素數消耗的時間。我們將a設為2進行搜索。

long int ranFakePrime(){
    long int t;
    srand(unsigned(time(0)));
    do{
        t = random(10, 233);
    }
    while( fastModel(2, t-1, t) != 1 );
    return t;
}
double random(double start, double end){
    return start+(end-start)*rand()/(RAND_MAX + 1.0);
}

Miller-Rabin素性測試演算法

生成偽素數之後，下一步就是判斷這個素數是否為真實的素數。畢竟如果只令a = 2，前10億個自然數中共有50847534個素數，而滿足2^(n-1) mod n = 1的合數n有5597個。這樣算法出錯概率有0.011%。如果令a = 3呢？前10億個自然數中同時以2和3為底的偽素數只有1272個，這個數目不到剛才的1/4。雖然可以再次排除一些偽素數，但結果有些不盡人意。這是Fermat素性測試，原理是隨機選擇若干個小於待測數的正整數作為a進行若干次測試，只要有一次沒有通過測試就立即把這個將這個數標記為合數。但是仍然存在十分頑強的合數，可以繞過這種檢查方式，被稱作Carmichael數。例如最小的這個數，只有561。

這時候就需要Miller-Rabin素性測試算法。該算法詳細介紹見
https://zh.wikipedia.org/wiki/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E6%A3%80%E9%AA%8C

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;
            if (fastModel(2, d, t) != 1){
               if (fastModel(2, d, t) != t-1){
                   return false;
               }
               else{
                   return true;
               }
            } 
        }
        while( d % 2 == 0 );
    }
    return true;
}