rsa演算法的理論基礎

① rsa加密和解密的理論依據是什麼

以前也接觸過RSA加密演算法，感覺這個東西太神秘了，是數學家的事，和我無關。但是，看了很多關於RSA加密演算法原理的資料之後，我發現其實原理並不是我們想像中那麼復雜，弄懂之後發現原來就只是這樣而已..
學過演算法的朋友都知道，計算機中的演算法其實就是數學運算。所以，再講解RSA加密演算法之前，有必要了解一下一些必備的數學知識。我們就從數學知識開始講解。
必備數學知識
RSA加密演算法中，只用到素數、互質數、指數運算、模運算等幾個簡單的數學知識。所以，我們也需要了解這幾個概念即可。
素數
素數又稱質數，指在一個大於1的自然數中，除了1和此整數自身外，不能被其他自然數整除的數。這個概念，我們在上初中，甚至小學的時候都學過了，這里就不再過多解釋了。
互質數
網路上的解釋是：公因數只有1的兩個數，叫做互質數。；維基網路上的解釋是：互質，又稱互素。若N個整數的最大公因子是1，則稱這N個整數互質。
常見的互質數判斷方法主要有以下幾種：
兩個不同的質數一定是互質數。例如，2與7、13與19。
一個質數，另一個不為它的倍數，這兩個數為互質數。例如，3與10、5與 26。
相鄰的兩個自然數是互質數。如 15與 16。
相鄰的兩個奇數是互質數。如 49與 51。
較大數是質數的兩個數是互質數。如97與88。
小數是質數，大數不是小數的倍數的兩個數是互質數。例如 7和 16。
2和任何奇數是互質數。例如2和87。
1不是質數也不是合數，它和任何一個自然數在一起都是互質數。如1和9908。
輾轉相除法。
指數運算
指數運算又稱乘方計算，計算結果稱為冪。nm指將n自乘m次。把nm看作乘方的結果，叫做」n的m次冪」或」n的m次方」。其中，n稱為「底數」，m稱為「指數」。
模運算
模運算即求余運算。「模」是「Mod」的音譯。和模運算緊密相關的一個概念是「同餘」。數學上，當兩個整數除以同一個正整數，若得相同餘數，則二整數同餘。
兩個整數a，b，若它們除以正整數m所得的余數相等，則稱a，b對於模m同餘，記作: a ≡ b (mod m)；讀作：a同餘於b模m，或者，a與b關於模m同餘。例如：26 ≡ 14 (mod 12)。
RSA加密演算法
RSA加密演算法簡史
RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。
公鑰與密鑰的產生
假設Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰：
隨意選擇兩個大的質數p和q，p不等於q，計算N=pq。
根據歐拉函數，求得r = (p-1)(q-1)
選擇一個小於 r 的整數 e，求得 e 關於模 r 的模反元素，命名為d。（模反元素存在，當且僅當e與r互質）
將 p 和 q 的記錄銷毀。
(N,e)是公鑰，(N,d)是私鑰。Alice將她的公鑰(N,e)傳給Bob，而將她的私鑰(N,d)藏起來。
加密消息
假設Bob想給Alice送一個消息m，他知道Alice產生的N和e。他使用起先與Alice約好的格式將m轉換為一個小於N的整數n，比如他可以將每一個字轉換為這個字的Unicode碼，然後將這些數字連在一起組成一個數字。假如他的信息非常長的話，他可以將這個信息分為幾段，然後將每一段轉換為n。用下面這個公式他可以將n加密為c：

ne ≡ c (mod N)
計算c並不復雜。Bob算出c後就可以將它傳遞給Alice。
解密消息
Alice得到Bob的消息c後就可以利用她的密鑰d來解碼。她可以用以下這個公式來將c轉換為n：
cd ≡ n (mod N)
得到n後，她可以將原來的信息m重新復原。
解碼的原理是：
cd ≡ n e·d(mod N)
以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。由費馬小定理可證明（因為p和q是質數）
n e·d ≡ n (mod p) 和 n e·d ≡ n (mod q)
這說明（因為p和q是不同的質數，所以p和q互質）
n e·d ≡ n (mod pq)
簽名消息
RSA也可以用來為一個消息署名。假如甲想給乙傳遞一個署名的消息的話，那麼她可以為她的消息計算一個散列值(Message digest)，然後用她的密鑰(private key)加密這個散列值並將這個「署名」加在消息的後面。這個消息只有用她的公鑰才能被解密。乙獲得這個消息後可以用甲的公鑰解密這個散列值，然後將這個數據與他自己為這個消息計算的散列值相比較。假如兩者相符的話，那麼他就可以知道發信人持有甲的密鑰，以及這個消息在傳播路徑上沒有被篡改過。

RSA加密演算法的安全性

當p和q是一個大素數的時候，從它們的積pq去分解因子p和q，這是一個公認的數學難題。然而，雖然RSA的安全性依賴於大數的因子分解，但並沒有從理論上證明破譯RSA的難度與大數分解難度等價。
1994年彼得·秀爾（Peter Shor）證明一台量子計算機可以在多項式時間內進行因數分解。假如量子計算機有朝一日可以成為一種可行的技術的話，那麼秀爾的演算法可以淘汰RSA和相關的衍生演算法。（即依賴於分解大整數困難性的加密演算法）
另外，假如N的長度小於或等於256位，那麼用一台個人電腦在幾個小時內就可以分解它的因子了。1999年，數百台電腦合作分解了一個512位長的N。1997年後開發的系統，用戶應使用1024位密鑰，證書認證機構應用2048位或以上。
RSA加密演算法的缺點

雖然RSA加密演算法作為目前最優秀的公鑰方案之一，在發表三十多年的時間里，經歷了各種攻擊的考驗，逐漸為人們接受。但是，也不是說RSA沒有任何缺點。由於沒有從理論上證明破譯RSA的難度與大數分解難度的等價性。所以，RSA的重大缺陷是無法從理論上把握它的保密性能如何。在實踐上，RSA也有一些缺點：
產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密；
分組長度太大，為保證安全性，n 至少也要 600 bits 以上，使運算代價很高，尤其是速度較慢，。

② 密碼學基礎（三）：非對稱加密（RSA演算法原理）

加密和解密使用的是兩個不同的秘鑰，這種演算法叫做非對稱加密。非對稱加密又稱為公鑰加密，RSA只是公鑰加密的一種。

現實生活中有簽名，互聯網中也存在簽名。簽名的作用有兩個，一個是身份驗證，一個是數據完整性驗證。數字簽名通過摘要演算法來確保接收到的數據沒有被篡改，再通過簽名者的私鑰加密，只能使用對應的公鑰解密，以此來保證身份的一致性。

數字證書是將個人信息和數字簽名放到一起，經由CA機構的私鑰加密之後生成。當然，不經過CA機構，由自己完成簽名的證書稱為自簽名證書。CA機構作為互聯網密碼體系中的基礎機構，擁有相當高級的安全防範能力，所有的證書體系中的基本假設或者前提就是CA機構的私鑰不被竊取，一旦 CA J機構出事，整個信息鏈將不再安全。

CA證書的生成過程如下：

證書參與信息傳遞完成加密和解密的過程如下：

互質關系：互質是公約數只有1的兩個整數，1和1互質，13和13就不互質了。
歐拉函數：表示任意給定正整數 n，在小於等於n的正整數之中，有多少個與 n 構成互質關系，其表達式為：

其中，若P為質數，則其表達式可以簡寫為：

情況一：φ(1)=1
1和任何數都互質，所以φ(1)=1；

情況二：n 是質數， φ(n)=n-1
因為 n 是質數，所以和小於自己的所有數都是互質關系，所以φ(n)=n-1；

情況三：如果 n 是質數的某一個次方，即 n = p^k ( p 為質數，k 為大於等於1的整數)，則φ(n)=(p-1)p^(k-1)
因為 p 為質數，所以除了 p 的倍數之外，小於 n 的所有數都是 n 的質數；

情況四：如果 n 可以分解成兩個互質的整數之積，n = p1 × p2，則φ(n) = φ(p1p2) = φ(p1)φ(p2)

情況五：基於情況四，如果 p1 和 p2 都是質數，且 n=p1 × p2，則φ(n) = φ(p1p2) = φ(p1)φ(p2)=(p1-1)(p2-1)

而 RSA 演算法的基本原理就是歐拉函數中的第五種情況，即： φ(n)=(p1-1)(p2-1);

如果兩個正整數 a 和 n 互質，那麼一定可以找到整數 b，使得 ab-1 被 n 整除，或者說ab被n除的余數是1。這時，b就叫做a的「模反元素」。歐拉定理可以用來證明模反元素必然存在。

可以看到，a的 φ(n)-1 次方，就是a對模數n的模反元素。

n=p x q = 3233，3233寫成二進制是110010100001，一共有12位，所以這個密鑰就是12位。

在實際使用中，一般場景下選擇1024位長度的數字，更高安全要求的場景下，選擇2048位的數字，這里作為演示，選取p=61和q=53；

因為n、p、q都為質數，所以φ(n) = (p-1)(q-1)=60×52= 3120

注意，這里是和φ(n) 互互質而不是n！假設選擇的值是17，即 e=17；

模反元素就是指有一個整數 d，可以使得 ed 被 φ(n) 除的余數為1。表示為：(ed-1)=φ(n) y --> 17d=3120y+1，算出一組解為(2753,15)，即 d=2753，y=-15，也就是(17 2753-1)/3120=15。

注意，這里不能選擇3119，否則公私鑰相同？？

公鑰：(n,e)=(3233,2753)
私鑰：(n,d)=(3233,17)

公鑰是公開的，也就是說m=p*q=3233是公開的，那麼怎麼求e被？e是通過模反函數求得，17d=3120y+1，e是公開的等於17，這時候想要求d就要知道3120，也就是φ(n)，也就是φ(3233)，說白了，3233是公開的，你能對3233進行因數分解，你就能知道d，也就能破解私鑰。

正常情況下，3233我們可以因數分解為61*53，但是對於很大的數字，人類只能通過枚舉的方法來因數分解，所以RSA安全性的本質就是：對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA演算法愈可靠。

人類已經分解的最大整數是：

這個人類已經分解的最大整數為232個十進制位，768個二進制位，比它更大的因數分解，還沒有被報道過，因此目前被破解的最長RSA密鑰就是768位。所以實際使用中的1024位秘鑰基本安全，2048位秘鑰絕對安全。

網上有個段子：

已經得出公私鑰的組成：
公鑰：(n,e)=(3233,2753)
私鑰：(n,d)=(3233,17)
加密的過程就是

解密過程如下：

其中 m 是要被加密的數字，c 是加密之後輸出的結果，且 m < n ，其中解密過程一定成立可以證明的，這里省略證明過程。

總而言之，RSA的加密就是使用模反函數對數字進行加密和求解過程，在實際使用中因為 m < n必須成立，所以就有兩種加密方法：

對稱加密存在雖然快速，但是存在致命的缺點就是秘鑰需要傳遞。非對稱加密雖然不需要傳遞秘鑰就可以完成加密和解密，但是其致命缺點是速度不夠快，不能用於高頻率，高容量的加密場景。所以才有了兩者的互補關系，在傳遞對稱加密的秘鑰時採用非對稱加密，完成秘鑰傳送之後採用對稱加密，如此就可以完美互補。

③ 密碼學基礎1：RSA演算法原理全面解析

本節內容中可能用到的符號說明如下：

質數和合數： 質數是指除了平凡約數1和自身之外，沒有其他約數的大於1的正整數。大於1的正整數中不是素數的則為合數。如 7、11 是質數，而 4、9 是合數。在 RSA 演算法中主要用到了質數相關性質，質數可能是上帝留給人類的一把鑰匙，許多數學定理和猜想都跟質數有關。

[定理1] 除法定理： 對任意整數 a 和 任意正整數 n，存在唯一的整數 q 和 r，滿足 。其中， 稱為除法的商，而 稱為除法的余數。

整除： 在除法定理中，當余數 時，表示 a 能被 n 整除，或者說 a 是 n 的倍數，用符號 表示。

約數和倍數 ： 對於整數 d 和 a，如果 ，且 ，則我們說 d 是 a 的約數，a 是 d 的倍數。

公約數： 對於整數 d，a，b，如果 d 是 a 的約數且 d 也是 b 的約數，則 d 是 a 和 b 的公約數。如 30 的約數有 1，2，3，5，6，10，15，30，而 24 的約數有 1，2，3，4，6，8，12，24，則 30 和 24 的公約數有 1，2，3，6。其中 1 是任意兩個整數的公約數。

公約數的性質：

最大公約數： 兩個整數最大的公約數稱為最大公約數，用 來表示，如 30 和 24 的最大公約數是 6。 有一些顯而易見的性質：

[定理2] 最大公約數定理： 如果 a 和 b 是不為0的整數，則 是 a 和 b 的線性組合集合 中的最小正元素。

由定理2可以得到一個推論：

[推論1] 對任意整數 a 和 b，如果 且 ，則 。

互質數： 如果兩個整數 a 和 b 只有公因數 1，即 ，則我們就稱這兩個數是互質數(coprime）。比如 4 和 9 是互質數，但是 15 和 25 不是互質數。

互質數的性質：

歐幾里得演算法分為樸素歐幾里得演算法和擴展歐幾里得演算法，樸素法用於求兩個數的最大公約數，而擴展的歐幾里得演算法則有更多廣泛應用，如後面要提到的求一個數對特定模數的模逆元素等。

求兩個非負整數的最大公約數最有名的是 輾轉相除法，最早出現在偉大的數學家歐幾里得在他的經典巨作《幾何原本》中。輾轉相除法演算法求兩個非負整數的最大公約數描述如下：

例如， ，在求解過程中，較大的數縮小，持續進行同樣的計算可以不斷縮小這兩個數直至其中一個變成零。

歐幾里得演算法的python實現如下：

擴展歐幾里得演算法在 RSA 演算法中求模反元素有很重要的應用，定義如下：

定義： 對於不全為 0 的非負整數 ，則必然存在整數對 ，使得

例如，a 為 3，b 為 8，則 。那麼，必然存在整數對 ，滿足 。簡單計算可以得到 滿足要求。

擴展歐幾里得演算法的python實現如下：

同餘： 對於正整數 n 和 整數 a，b，如果滿足 ，即 a-b 是 n 的倍數，則我們稱 a 和 b 對模 n 同餘，記號如下： 例如，因為 ，於是有 。
對於正整數 n，整數 ，如果 則我們可以得到如下性質：

譬如，因為 ，則可以推出 。

另外，若 p 和 q 互質，且 ，則可推出：

此外，模的四則運算還有如下一些性質，證明也比較簡單，略去。

模逆元素： 對整數 a 和正整數 n，a 對模數 n 的模逆元素是指滿足以下條件的整數 b。 a 對 模數 n 的 模逆元素不一定存在，a 對 模數 n 的模逆元素存在的充分必要條件是 a 和 n 互質，這個在後面我們會有證明。若模逆元素存在，也不是唯一的。例如 a=3，n=4，則 a 對模數 n 的模逆元素為 7 + 4k，即 7，11，15，...都是整數 3 對模數 4 的模逆元素。如果 a 和 n 不互質，如 a = 2，n = 4，則不存在模逆元素。

[推論2] 模逆元素存在的充分必要條件是整數 a 和 模數 n 互質。

[定理3] 唯一質數分解定理： 任何一個大於1的正整數 n 都可以 唯一分解 為一組質數的乘積，其中 都是自然數(包括0)。比如 6000 可以唯一分解為 。

由質數唯一分解定理可以得到一個推論： 質數有無窮多個 。

[定理4] 中國剩餘定理(Chinese remainder theorem，CRT) ，最早見於《孫子算經》(中國南北朝數學著作，公元420-589年)，叫物不知數問題，也叫韓信點兵問題。

翻譯過來就是已知一個一元線性同餘方程組求 x 的解：

宋朝著名數學家秦九韶在他的著作中給出了物不知數問題的解法，明朝的數學家程大位甚至編了一個《孫子歌訣》：

意思就是：將除以 3 的余數 2 乘以 70，將除以 5 的余數 3 乘以 21，將除以 7 的余數 2 乘以 15，最終將這三個數相加得到 。再將 233 除以 3，5，7 的最小公倍數 105 得到的余數 ，即為符合要求的最小正整數，實際上， 都符合要求。

物不知數問題解法本質

求解通項公式

中國剩餘定理相當於給出了以下的一元線性同餘方程組的有解的判定條件，並用構造法給出了解的具體形式。

模數 兩兩互質 ，則對任意的整數： ，方程組 有解，且解可以由如下構造方法得到：

並設 是除 以外的其他 個模數的乘積。

中國剩餘定理通項公式證明

④ RSA演算法建立的理論基礎是()

RSA演算法建立的理論基礎是大數分解和素數檢測 。

RSA是1977年由羅納德·李維斯特、阿迪·薩莫爾和倫納德·阿德曼一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

RSA公開密鑰密碼體制是一種使用不同的加密密鑰與解密密鑰，「由已知加密密鑰推導出解密密鑰在計算上是不可行的」密碼體制。

(4)rsa演算法的理論基礎擴展閱讀：

在公開密鑰密碼體制中，加密密鑰（即公開密鑰）PK是公開信息，而解密密鑰（即秘密密鑰）SK是需要保密的。加密演算法E和解密演算法D也都是公開的。雖然解密密鑰SK是由公開密鑰PK決定的，但卻不能根據PK計算出SK。

正是基於這種理論，1978年出現了著名的RSA演算法，它通常是先生成一對RSA密鑰，其中之一是保密密鑰，由用戶保存；另一個為公開密鑰，可對外公開，甚至可在網路伺服器中注冊。

為提高保密強度，RSA密鑰至少為500位長，一般推薦使用1024位。這就使加密的計算量很大。為減少計算量，在傳送信息時，常採用傳統加密方法與公開密鑰加密方法相結合的方式。