第二章 如何實(shí)現(xiàn)應(yīng)用RSA算法

趁著白天在自家店里的閑暇時(shí)間來寫寫第二章了，假設(shè)記住了第一章的各種定理之后，我們又該如何實(shí)現(xiàn)RSA密碼的加密解密呢？也懶得廢話了，直接進(jìn)入正題吧。
先回顧幾個(gè)知識(shí)點(diǎn)：

1.模運(yùn)算的性質(zhì)：

結(jié)合律：(a % p * b) % p = (a * b) % p 
可知當(dāng)a == b時(shí)，(a % p * a) % p = (a * a) % p

2.歐拉定理

a^φ(n) ≡ 1 (mod n)

3.乘法逆元性質(zhì)

e * d ≡ 1 (mod n)  => e * d ≡ 1   k * n(k為任意整數(shù)）
注：且當(dāng)a與n互質(zhì)時(shí)b有解。
注：如何去除帶(mod)式子，令k = 0，即忽略其他同余式。 

接著我們要證明一種現(xiàn)象，根據(jù)歐拉定理與乘法逆元性質(zhì)外帶一點(diǎn)模運(yùn)算的結(jié)合律運(yùn)算列出如下算式：
M ^ (e * d) = M ^ (1 k * φ(n)) = M * M ^ (φ(n) * k) ≡ M * (1) ^ k ≡ M (mod n)
由此可知 M ^ (e * d) ≡ M (mod n)
注：M ^ φ(n) ≡ 1 (mod n)（歐拉定理）

基于上述請(qǐng)諸位看以下算式：

C ≡ M ^ e (mod n) ①
M ≡ C ^ d (mod n) ②

于是我們這樣做，將①代入②可得：M ≡ M ^ (e * d) (mod n) ，是不是和上述的現(xiàn)象的結(jié)果一致呢？
至此我們也可以看出，其實(shí)C就是一個(gè)中間密文。
那么我們來看看RSA運(yùn)作流程：
假如A和B兩人各自拿著e與d。
首先A要給B解密用的密鑰d時(shí)必然得滿足乘法逆元性質(zhì)e和n要互質(zhì)，否則得不到d。
其次對(duì)于A要加密一個(gè)B可以解開的密文必然滿足M < n，否則M不滿足②式也就不唯一了，同樣B也要滿足C < n，否則A也解不對(duì)B的數(shù)據(jù)。
最后利用①與②算式分別生成中間密文交由對(duì)方來還原數(shù)據(jù)。
綜上所述，RSA算法描述就到此結(jié)束了。

以下是算法實(shí)現(xiàn)過程：

一.算法所需參數(shù)

1.密文數(shù)據(jù)規(guī)模 n = φ(n)
2.生成兩把密鑰 e 與 d

二.算法實(shí)現(xiàn)代碼

一開始想著分C 和C版本代碼，后來一想，既然都寫了C代碼何必浪費(fèi)時(shí)間去寫吃力不討好的C 呢？= -=
于是現(xiàn)在直接給出完整的C代碼了，因?yàn)榈谌孪牖诘诙碌拇a部分進(jìn)行講解，尤其是一些可以優(yōu)化本質(zhì)的代碼（即不在語法上改進(jìn)），說不定出了第二章后就不想寫第三章了，所以把代碼放出來是為了以后好找理由偷懶吧（“都把代碼給你了你怎么還要我來講解（說笑的= -=）”）
事不宜遲貼代碼吧！建議想學(xué)習(xí)的同學(xué)復(fù)制后拿到自己的編譯器里運(yùn)行測(cè)試一下~

#ifndef RSA
#define RSA
// 歐拉函數(shù)：φ(x) = x ∏ (1-1/p)（P是數(shù)N的質(zhì)因數(shù)）
int Eular(int n)
{
    int ret = 1, i;
    for(i = 2; i*i <= n; i  )
    {
        if(0 == n%i)
        {
            n /= i, ret *= i-1;
            while(0 == n%i)
                n /= i, ret *= i;
        }
    }
    if(n > 1)
        ret *= n-1;
    return ret;
}
// 歐幾里何函數(shù)：Gcd(a, b）= Gcd(b, a%b)
int Gcd(int a, int b)
{
    return 0 == b ? a : Gcd(b, a%b);
}
// 拓展歐幾里何函數(shù)：a*x   b*y = gcd(a, b)
//      gcd(a, b) = gcd(b, a%b)
//    a%b = a-(a/b)*b
//    a*x   b*y = gcd(a, b) = gcd(b, a%b) = b*x1   (a-(a/b)*b)*y1
//        = b*x1   a*y1–(a/b)*b*y1
//        = a*y1   b*(x1–a/b*y1)
int Egcd(int a, int b, int *x, int *y)
{
    int result, t;
    // 遞歸終止條件
    if (0 == b)
    {
        *x = 1, *y = 0;
        return a;
    }
    result = Egcd(b, a%b, x, y);
    t = *x, *x = *y, *y = t-a/b*(*y);
    return result;
}
// 求解乘法逆元函數(shù) b * (return value) ≡ 1 (mod a)
int Inverse(int a, int b)
{
    int x = 0, y = 0;
    if (Egcd(a, b, &x, &y) != 1)
        return -1;
    // 確保余數(shù)與被除數(shù)符號(hào)一致
    if (b < 0)
        a = -a;
    if ((y %= a) <= 0)
        y  = a;
    return y;
}
// 冪模運(yùn)算a^b%k
// 通常思維暴力求解版本
unsigned PowMod(unsigned a, unsigned b, unsigned c)
{
    unsigned ans = a;
    while(b--)
        ans *= a;
    return ans % c;
}
// 冪模運(yùn)算a^b%k
// 遞歸版本 a ^ b (mod c)
// 模運(yùn)算結(jié)合律：(a * a) mod c =( (a mod c) * a ) mod c
// C 語言表達(dá)：((a * b) % p = (a % p * b) % p)
unsigned RecursionPowMod(unsigned a, unsigned b, unsigned c)
{
    return b ? a * RecursionPowMod(a, b - 1, c) % c : 1;
}
// 冪模運(yùn)算a^b%k
// Montgomery 版本
unsigned FastPowMod(unsigned a, unsigned b, unsigned c)
{
    unsigned ans;
    for (ans = 1; b; a = a*a%c, b >>= 1)
        if (b & 1)
            ans = ans*a%c;// LSB位為 1
    return ans;
}
#endif // RSA

#include "stdio.h"
#include "stdlib.h"
int main()
{
    // N 數(shù)據(jù)規(guī)模， En = φ(N)（歐拉函數(shù)結(jié)果）， Encrypt 與 Decrypt 分別為兩把密鑰
    int N = 0x1F, En = Eular(N), Encrypt = 2, Decrypt;
    // 生成RSA參數(shù)
    do
    {
        // 選取 Encrypt 與 En 互質(zhì)的數(shù)
        while(1 != Gcd(En, Encrypt))
            Encrypt  ;
        // 求解其乘法逆元，若 Decrypt == -1 則表示 En 與 Encrypt 不互質(zhì)
        Decrypt = Inverse(En, Encrypt);
    }while(-1 == Decrypt);
    // 預(yù)覽 RSA 參數(shù)
    printf("En:M\tE:M\tD:M\n", En, Encrypt, Decrypt);
    // 功能測(cè)試, 若陷入死循環(huán)必然是因?yàn)闆]能還原回原數(shù)據(jù)導(dǎo)致無法進(jìn)入下一索引(  )，可自行測(cè)試大于N的數(shù)據(jù)規(guī)模
    puts("Test Encrypt Key");
    for(int src = 0, goal; src < N; src  )
    {
        printf("src: M\t", src);
        goal = RecursionPowMod(src, Encrypt, N);
        printf("goal: M\t", goal);
        src = RecursionPowMod(goal, Decrypt, N);
        printf("src: M\n", src);
    }
    puts("Test Decrypt Key");
    for(int src = 0, goal; src < N; src  )
    {
        printf("src: M\t", src);
        goal = RecursionPowMod(src, Decrypt, N);
        printf("goal: M\t", goal);
        src = RecursionPowMod(goal, Encrypt, N);
        printf("src: M\n", src);
    }
    return 0;
}

順便也貼一下運(yùn)行結(jié)果= -=~標(biāo)題就是我的IDE路徑，采用32位mingw編譯器

最后的最后，這章也沒什么好談的了，代碼說明了一切，看一句代碼比廢話十句更有效吧我認(rèn)為~
如果有疑問或想要進(jìn)一步學(xué)習(xí)的同學(xué)可以私聊我=- = 反正我晚上一直都很有空（偶爾會(huì)跑去打魔獸吧~）

現(xiàn)在代碼放在我的 Github 了，我翻翻 CryptFunction ，包含 ECC 算法的實(shí)現(xiàn)（好像）。