摘要：背景不對(duì)稱加密算法可是算是世界上最重要的加密算法，其中包括我們熟悉的的加密。現(xiàn)在我們分步來看，這個(gè)全球最重要的加密算法，都需要哪些數(shù)學(xué)知識(shí)。我們常說的算法中的多少位，就是用二進(jìn)制表示后的位數(shù)，在我們例子就是位。其中表示兩個(gè)數(shù)的最大公約數(shù)。

RSA不對(duì)稱加密算法可是算是世界上最重要的加密算法，其中包括我們熟悉的https的加密。為了完全弄明白他的實(shí)現(xiàn)原理，我們需要對(duì)數(shù)論這門學(xué)科，有一定的了解。現(xiàn)在我們分步來看，這個(gè)全球最重要的加密算法，都需要哪些數(shù)學(xué)知識(shí)。

數(shù)學(xué)知識(shí)：質(zhì)數(shù)

質(zhì)數(shù)又稱素?cái)?shù)，在自然數(shù)中，除了1和自身外，不能被其他自然數(shù)整除。比如10以內(nèi)的質(zhì)數(shù)有：1，2，3，5，7。那么在程序中，我們?nèi)绾闻袛嘁粋€(gè)數(shù)是不是質(zhì)數(shù)呢？
方案一：

function isPrimeNum() {
    let n = 7
    for (let i = 2; i < n; i++) {
        if (n % i === 0) {
            return false
        }
    }
    return true
}

這種方案是最直觀的，也是效率最低的，因?yàn)橐袛鄋是不是質(zhì)數(shù)，我們需要運(yùn)算n-2次
方案二：

...
    for (let i = 2; i < n / 2; i++)
...

我們把for循環(huán)中的n改成n/2，這樣運(yùn)算量上能減少一半(因?yàn)? frac n2 $后一半的數(shù)都可以通過$ frac n2 $前一半的數(shù)$ imes 2$得到，所以沒必要參加運(yùn)算）
方案三：

...
    for (let i = 2; i < Math.sqrt(n); i++)
...

我們把$ frac n2 $改成 $ sqrt n $之后，我們的運(yùn)算量就不是減少一半了，而是減少一個(gè)數(shù)量級(jí)，數(shù)字越大，效果越明顯。我們以1萬為例，使用此方案只需要計(jì)算98次即可。

ts實(shí)現(xiàn)-有詳細(xì)注釋：是否為質(zhì)數(shù)

我們常說的RSA算法中的多少位，就是n用二進(jìn)制表示后的位數(shù)，在我們例子就是12位。目前商用中一般都是2048位，比如我們的segmentfault

數(shù)學(xué)知識(shí)1：互質(zhì)

如果兩個(gè)數(shù)的最大公約數(shù)為1，那么我們說這兩個(gè)數(shù)互質(zhì)，記：GCD(a,b)=1。其中GCD表示兩個(gè)數(shù)的最大公約數(shù)。
我們來看幾組互質(zhì)的例子：13、14 | 7、9 | 4、7 | 6、35 | ...
我們可以得到如下結(jié)論：如果兩個(gè)數(shù)是質(zhì)數(shù)，那么這兩個(gè)數(shù)肯定互質(zhì)；兩個(gè)數(shù)如果互質(zhì)，那么這兩個(gè)數(shù)不一定是質(zhì)數(shù)。比如：6和35都不是質(zhì)數(shù)，但是他們互質(zhì)。

ts實(shí)現(xiàn)-有詳細(xì)注釋：取互質(zhì)元素

數(shù)學(xué)知識(shí)2：歐拉函數(shù)

我們要計(jì)算10以內(nèi)有多少與10互質(zhì)呢，我們可以得到：1、3、7、9這4個(gè)數(shù)。如果是一個(gè)大數(shù)，我們用腦子想可能就想不出來了，所以我們需要使用歐拉函數(shù)來算出來，記作φ(n)。
歐拉函數(shù)分為幾種情況：

情況1：如果n=1，那么與n互質(zhì)的自然數(shù)只有1

$$ φ(n)=1 $$

情況2：如果n是質(zhì)數(shù)，那么與n互質(zhì)的自然數(shù)有n-1個(gè)，

$$ φ(n)=n-1 $$
$$ 例：φ(7)=6 $$

情況3：如果n可以因式分解為兩個(gè)互質(zhì)數(shù)的乘積，則

$$ φ(n)=φ(p) imes φ(q)=(p-1) imes (q-1)$$
$$ 例：φ(56)=φ(7)*φ(8) = 6 * 7 = 42 $$

情況4：如果n可以寫成某個(gè)數(shù)的質(zhì)數(shù)次冪(其中k為質(zhì)數(shù))，則

$$ φ(n)=φ(p^k)=p^k-p^{k-1}=p^k(1-frac 1p) $$
$$ 例：φ(49)=φ(7^2)=7^2 - 7^1 = 42 $$

情況5：根據(jù)以上規(guī)律，總結(jié)出一個(gè)通用的公式：

$ qquad n=p_1^{k^1} imes p_2^{k^2} ldots p_r^{k^r} quad 注：任意一個(gè)整數(shù)，都可以寫成兩個(gè)質(zhì)數(shù)的乘積$
$ qquad Downarrow $
$ qquad φ(n)=φ(p_1^{k^1}) imes φ(p_2^{k^2})ldots φ(p_r^{k^r})$
$ qquad Downarrow $
$ qquad φ(n)= p_1^{k^1}(1- frac 1p_1) imes p_2^{k^2}(1- frac 1p_2) ldots p_r^{k^r}(1- frac 1p_r)$
$ qquad Downarrow $
$ qquad φ(n)=p_1^{k^1} imes p_2^{k^2}ldots p_r^{k^r} imes (1- frac 1p_1) imes(1- frac 1p_2)ldots(1- frac 1p_n) $
$ qquad Downarrow $
$ qquad φ(n)=n imes(1- frac 1p_1) imes(1- frac 1p_2)ldots(1- frac 1p_n) $

總結(jié)：通過歐拉函數(shù)最后的通式，我們發(fā)現(xiàn)最后的結(jié)果只和n和p有關(guān)，和p的冪無關(guān)，這點(diǎn)很重要，在我們用程序?qū)崿F(xiàn)時(shí)，能夠大大的簡化我們的邏輯代碼。

回到算法中，我們需要計(jì)算與n互質(zhì)的個(gè)數(shù)，也就是求φ(n)，根據(jù)歐拉函數(shù)，計(jì)算過程如下：
$$ φ(n)=φ(3233)=φ(61) imes φ(53)=60 imes52=3120 $$

ts實(shí)現(xiàn)-有詳細(xì)注釋：歐拉函數(shù)

數(shù)學(xué)知識(shí)1：使用輾轉(zhuǎn)相除法求最大公約數(shù)

我們先看兩個(gè)例子，
例1：求47和30的最大公約數(shù)：
$ 47 = 30 imes 1 + 17 $
$ 30 = 17 imes 1 + 13 $
$ 17 = 13 imes 1 + 4 $
$ 13 = 4 imes 3 + 1 $
$ 4 = 1 imes 4 + 0 $

我們得到：GCD(47, 30) = 1

例2：求50和35的最大公約數(shù)：
$ 50 = 35 imes 1 + 15 $
$ 35 = 15 imes 2 + 5 $
$ 15 = 5 imes 3 + 0 $

我們得到：GCD(50, 35) = 5

聰明的你看完這兩個(gè)例子可以知道如何計(jì)算了吧。通俗的講，如果最后的多項(xiàng)式可以寫成：a = bx + c。 當(dāng)c=0時(shí)，b就是兩數(shù)的最大公約數(shù)。

ts實(shí)現(xiàn)-有詳細(xì)注釋：求最大公約數(shù)

數(shù)學(xué)知識(shí)2：模反元素

定義：如果兩個(gè)正整數(shù)a和n互質(zhì)，那么一定可以找到整數(shù)b，使得a*b與n相除，余數(shù)為1，記作：$ (a imes b) \% n = 1 Rightarrow frac {(a imes b) - 1} n = 1 $

例：求3和11的模反元素
$$ frac {(3 imes b) - 1} {11} = 1 $$

心算我們可以算出來其中一個(gè)值： $ b=4 $

數(shù)學(xué)知識(shí)3：裴蜀定理

通過上面的運(yùn)算，我們可以算出一些簡單數(shù)的模反元素，對(duì)于較大的數(shù)來說，我們需要引入新的計(jì)算工具：裴蜀定理，通過它，我們可以通過一個(gè)二元一次方程來得出模反元素

定義：如果a與b互質(zhì)，即GCD(a, b) = 1，二元一次方程$ ax + by = 1 $有一對(duì)正整數(shù)解，其中x即為a、b的模反元素。同理，上面的例子我們可以化簡成這樣：3x + 11y = 1

疑惑：對(duì)于二元一次方程，好像不可解（也可以說有無窮多個(gè)解），我們之前都是解方程組。即然定理已經(jīng)解決，兩個(gè)互素（質(zhì)）數(shù)組成的二元一次方程有一對(duì)整數(shù)解，那肯定是能解，解法我們需要引入另一個(gè)數(shù)學(xué)工具：擴(kuò)展歐幾里得算法

數(shù)學(xué)知識(shí)4：擴(kuò)展歐幾里得算法

這個(gè)算法其實(shí)就是上面我們求最大公約數(shù)時(shí)，用到的輾轉(zhuǎn)相除法+它的逆運(yùn)算，我們看個(gè)例子就明白是什么意思了

例1：求$ 47x + 30y = 1 $的解
解：使用輾轉(zhuǎn)相除法，我們可以得到：
$ 47 = 30 imes 1 + 17 $
$ 30 = 17 imes 1 + 13 $
$ 17 = 13 imes 1 + 4 $
$ 13 = 4 imes 3 + 1 $
對(duì)最后一行，我們移項(xiàng)處理：
$ 1 = 13 - 4 imes 3 $
$ 4 = 17 - 13 imes 1 $
$ 13 = 30 - 17 imes 1 $
$ 17 = 47 - 30 imes 1 $
我們把第二行代入第一行中：
$ 1 = 13 - overbrace{(17 - 13 imes 1)}^4 imes 3 $
$ Downarrow $
$ 1 = 4 imes 13 - 3 imes 17 $
$ Downarrow $
$ 1 = 4 imes overbrace{(30 - 17)}^{13} - 3 imes s17 $
$ Downarrow $
$ ldots $
$ 1 = (-7) imes 47 + 11 imes 30 $

$ 解得：x=-7(即為我們要求的模反元素d) quad y = 11 $

回到算法中，我們根據(jù)e=17和φ(n)=3120，得到一個(gè)二元一次方程：$ 17x + 3120y = 1 $，再根據(jù)擴(kuò)展歐幾里得算法，我們可以得到方程的解：$x = 2753 quad 即：d = 2753$

ts實(shí)現(xiàn)-有詳細(xì)注釋：擴(kuò)展歐幾里德算法求方程的解

公鑰：$ (3233, 17) $

私鑰：$ (3233, 2753) $

總結(jié)：RSA加密算法，雖說是一個(gè)程序問題，但終歸還是一個(gè)數(shù)學(xué)問題！

查看所有函數(shù)的運(yùn)行效果，點(diǎn)我點(diǎn)我！