RSA加密算法中的數學

?xiaoxiao, 發布于2019-08-21 17:53 / 1325人閱讀

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

背景

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

第一步：獲取兩個不相等的質數，p=61和q=53

數學知識：質數

質數又稱素數，在自然數中，除了1和自身外，不能被其他自然數整除。比如10以內的質數有：1，2，3，5，7。那么在程序中，我們如何判斷一個數是不是質數呢？
方案一：

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

這種方案是最直觀的，也是效率最低的，因為要判斷n是不是質數，我們需要運算n-2次
方案二：

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

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

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

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

ts實現-有詳細注釋：是否為質數

第二步：把p和q相乘，得到n。其中n=61*53=3233，用二進制表示為：110010100001。

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

第三步：計算出小于n的自然數中，有多少數與n互質

數學知識1：互質

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

ts實現-有詳細注釋：取互質元素

數學知識2：歐拉函數

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

情況1：如果n=1，那么與n互質的自然數只有1

$$ φ(n)=1 $$

情況2：如果n是質數，那么與n互質的自然數有n-1個，

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

情況3：如果n可以因式分解為兩個互質數的乘積，則

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

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

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

情況5：根據以上規律，總結出一個通用的公式：

$ qquad n=p_1^{k^1} imes p_2^{k^2} ldots p_r^{k^r} quad 注：任意一個整數，都可以寫成兩個質數的乘積$
$ 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) $

總結：通過歐拉函數最后的通式，我們發現最后的結果只和n和p有關，和p的冪無關，這點很重要，在我們用程序實現時，能夠大大的簡化我們的邏輯代碼。

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

ts實現-有詳細注釋：歐拉函數

第四步：在1和φ(n)之間，選取一個隨機質數e，即在1~3120中選取e=17 第五步：求e和φ(n)的模反元素d

數學知識1：使用輾轉相除法求最大公約數

我們先看兩個例子，
例1：求47和30的最大公約數：
$ 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的最大公約數：
$ 50 = 35 imes 1 + 15 $
$ 35 = 15 imes 2 + 5 $
$ 15 = 5 imes 3 + 0 $

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

聰明的你看完這兩個例子可以知道如何計算了吧。通俗的講，如果最后的多項式可以寫成：a = bx + c。當c=0時，b就是兩數的最大公約數。

ts實現-有詳細注釋：求最大公約數

數學知識2：模反元素

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

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

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

數學知識3：裴蜀定理

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

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

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

數學知識4：擴展歐幾里得算法

這個算法其實就是上面我們求最大公約數時，用到的輾轉相除法+它的逆運算，我們看個例子就明白是什么意思了

例1：求$ 47x + 30y = 1 $的解
解：使用輾轉相除法，我們可以得到：
$ 47 = 30 imes 1 + 17 $
$ 30 = 17 imes 1 + 13 $
$ 17 = 13 imes 1 + 4 $
$ 13 = 4 imes 3 + 1 $
對最后一行，我們移項處理：
$ 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 $

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

ts實現-有詳細注釋：擴展歐幾里德算法求方程的解

第六步：我們把n和e封裝成公鑰，n和d封裝成私鑰

公鑰：$ (3233, 17) $

私鑰：$ (3233, 2753) $

到此，我們的公私鑰分配成功！

總結：RSA加密算法，雖說是一個程序問題，但終歸還是一個數學問題！

查看所有函數的運行效果，點我點我！

GPU云服務器云服務器 rsa加密算法加密rsa rsa非對稱加密 rsa加密庫 php

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/90170.html

非對稱加密技術- RSA算法數學原理分析

摘要：本文首發于深入淺出區塊鏈社區原文鏈接非對稱加密技術算法數學原理分析原文已更新，請讀者前往原文閱讀非對稱加密技術，在現在網絡中，有非常廣泛應用。加密技術更是數字貨幣的基礎。本文首發于深入淺出區塊鏈社區原文鏈接:非對稱加密技術 - RSA算法數學原理分析原文已更新，請讀者前往原文閱讀非對稱加密技術，在現在網絡中，有非常廣泛應用。加密技術更是數字貨幣的基礎。所謂非對稱，就是指該算法需要一...

maxmin 2019-06-27 18:24 評論0 收藏0
區塊鏈之非對稱加密算法

摘要：二如何理解公鑰和私鑰非對稱加密算法需要兩個密鑰公開密鑰和私有密鑰。因為加密和解密使用的是兩個不同的密鑰，所以這種算法叫作非對稱加密算法。三非對稱加密解密原理非對稱加密算法中，常用的就是算法了，以下就以算法為例來講解非對稱加密算法的實現原理。非對稱加密，在現在網絡應用中，有這非常廣泛的場景，更是加密貨幣的基礎。本文主要介紹非對稱加密、解密的原理和過程，以及在區塊鏈中的使用。一、非對稱...

mcterry 2019-06-27 18:41 評論0 收藏0
漫談 | “黎曼猜想”和區塊鏈加密算法到底有什么關系？

摘要：假如黎曼猜想被證實，區塊鏈將毀滅近日，黎曼猜想四個字瘋狂刷屏。黎曼猜想由數學家波恩哈德黎曼于年提出。因此，黎曼猜想一旦被證明，則意味著素數之密被解開，算法也就將被攻破了。而大多數區塊鏈所用的加密算法不是，而是橢圓曲線加密算法。瑪麗女王的密碼之生死命懸一線 showImg(https://segmentfault.com/img/bVbhD7s?w=740&h=876); 16世紀伊麗...

tracymac7 2019-06-27 18:47 評論0 收藏0
沒那么淺地談談HTTP與HTTPS【三】

摘要：公開密鑰加密的出現大大減輕了交換對稱密鑰的困難，公鑰可以公開透過不安全可被竊聽的渠道發送，用以加密明文。當與配合使用，稱之為，與配合則稱為，以此類推。這步沒有簽名，服務端收到數據后不會發現被篡改。對于認證機構，一旦私鑰外泄，將可能導致整未濟，亨。小狐汔濟，濡其尾，無攸利。——《易》六、密鑰管理當不再擔心身份會被冒充、篡改之后，我們再來詳細談談網絡通信中對于加密算法的密鑰管理。在密鑰被簽發后，...

Tecode 2022-06-28 18:59 評論0 收藏0
非對稱加密算法-RSA

摘要：非對稱加密，加密與解密使用的密鑰不是同一密鑰，對中一個對外公開，稱為公鑰，另一個只有所有者知道，稱為私鑰。對稱加密算法不能實現簽名，因此簽名只能非對稱算法。正因為，這種加密是單向的，所以被稱為非對稱加密算法。非對稱加密，加密與解密使用的密鑰不是同一密鑰，對中一個對外公開，稱為公鑰，另一個只有所有者知道，稱為私鑰。用公鑰加密的信息只有私鑰才能解開，反之，用私鑰加密的信息只有公鑰才能解開...

gggggggbong 2019-08-16 10:40 評論0 收藏0