機演算法分解素因數

Ⅰ 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 以上，使運算代價很高，尤其是速度較慢，。

Ⅱ 用C語言編1到100之間的素數程序

程序及解釋如下：

首先判斷素數的演算法：用一個數分別去除以2到sqrt(這個數)，如果能被整除， 則表明此數不是素數，反之是素數。

則有如下程序

{ int m,k,i;

for(m=1;m<=100;m=m+2) //m=m+2,因為偶數都不是素數,不用考慮,所以每次m+2.

{ k=sqrt(m） //先求這個數的平方跟

for(i=2;i<=k;i++) //然後用i(從2到k,即m的平方跟)去除m,

if(m%i==0) break; //如果能被整除， 則不是素數,break

if(i>=k+1) pritnf("%d",m); //如果i>k+1,則說明沒有數能整除m.則m是素數

}
}

(2)機演算法分解素因數擴展閱讀：

素數被利用在密碼學上，所謂的公鑰就是將想要傳遞的信息在編碼時加入質數，編碼之後傳送給收信人，任何人收到此信息後，若沒有此收信人所擁有的密鑰，則解密的過程中（實為尋找素數的過程），將會因為找質數的過程（分解質因數）過久，使即使取得信息也會無意義。

在汽車變速箱齒輪的設計上，相鄰的兩個大小齒輪齒數設計成質數，以增加兩齒輪內兩個相同的齒相遇嚙合次數的最小公倍數，可增強耐用度減少故障。

在害蟲的生物生長周期與殺蟲劑使用之間的關繫上，殺蟲劑的質數次數的使用也得到了證明。實驗表明，質數次數地使用殺蟲劑是最合理的：都是使用在害蟲繁殖的高潮期，而且害蟲很難產生抗葯性。

以質數形式無規律變化的導彈和魚雷可以使敵人不易攔截。

多數生物的生命周期也是質數（單位為年），這樣可以最大程度地減少碰見天敵的機會。

參考資料：網路 素數

Ⅲ Hello，密碼學：第三部分，公鑰密碼（非對稱密碼）演算法

在 《Hello，密碼學：第二部分，對稱密碼演算法》 中講述了對稱密碼的概念，以及DES和AES兩種經典的對稱密碼演算法原理。既然有對稱密碼的說法，自然也就有非對稱密碼，也叫做公鑰密碼演算法。 對稱密碼和非對稱密碼兩種演算法的本質區別在於，加密密鑰和解密密鑰是否相同 ：

公鑰密碼產生的初衷就是為了解決 密鑰配送 的問題。

Alice 給遠方的 Bob 寫了一封情意慢慢的信，並使用強悍的 AES-256 進行了加密，但她很快就意識到，光加密內容不行，必須要想一個安全的方法將加密密鑰告訴 Bob，如果將密鑰也通過網路發送，很可能被技術高手+偷窺癖的 Eve 竊聽到。

既要發送密鑰，又不能發送密鑰，這就是對稱密碼演算法下的「密鑰配送問題」 。

解決密鑰配送問題可能有這樣幾種方法：

這種方法比較高效，但有局限性：

與方法一不同，密鑰不再由通信個體來保存，而由密鑰分配中心（KDC）負責統一的管理和分配。 雙方需要加密通信時，由 KDC 生成一個用於本次通信的通信密鑰交由雙方，通信雙方只要與 KDC 事先共享密鑰即可 。這樣就大大減少密鑰的存儲和管理問題。

因此，KDC 涉及兩類密鑰：

領略下 KDC 的過程：

KDC 通過中心化的手段，確實能夠有效的解決方法一的密鑰管理和分配問題，安全性也還不錯。但也存在兩個顯著的問題：

使用公鑰密睜衡碼，加密密鑰和解密密鑰不同，只要擁有加密密鑰，所有人都能進行加密，但只有擁有解密密鑰的人才能進行解密。於是就出現了這個過程：

密鑰配送的問題天然被解決了。當然，解密密鑰丟失而導致信息泄密，這不枯脊屬於密鑰配送的問題。

下面，再詳細看下這個過程。

公鑰沒早滲密碼流程的核心，可以用如下四句話來概述：

既然加密密鑰是公開的，因此也叫做 「公鑰（Public Key）」 。
既然解密密鑰是私有的，因此也叫做 「私鑰（Private Key） 。

公鑰和私鑰是一一對應的，稱為 「密鑰對」 ，他們好比相互糾纏的量子對， 彼此之間通過嚴密的數學計算關系進行關聯 ，不能分別單獨生成。

在公鑰密碼體系下，再看看 Alice 如何同 Bob 進行通信。

在公鑰密碼體系下，通信過程是由 Bob 開始啟動的：

過程看起來非常簡單，但為什麼即使公鑰被竊取也沒有關系？這就涉及了上文提到的嚴密的數學計算關系了。如果上一篇文章對稱密鑰的 DES 和 AES 演算法進行概述，下面一節也會對公鑰體系的數學原理進行簡要說明。

自從 Diffie 和 Hellman 在1976年提出公鑰密碼的設計思想後，1978年，Ron Rivest、Adi Shamir 和 Reonard Adleman 共同發表了一種公鑰密碼演算法，就是大名鼎鼎的 RSA，這也是當今公鑰密碼演算法事實上的標准。其實，公鑰密碼演算法還包括ElGamal、Rabin、橢圓曲線等多種演算法，這一節主要講述 RSA 演算法的基本數學原理。

一堆符號，解釋下，E 代表 Encryption，D 代表 Decryption，N 代表 Number。

從公式種能夠看出來，RSA的加解密數學公式非常簡單（即非常美妙）。 RSA 最復雜的並非加解密運算，而是如何生成密鑰對 ，這和對稱密鑰演算法是不太一樣的。 而所謂的嚴密的數學計算關系，就是指 E 和 D 不是隨便選擇的 。

密鑰對的生成，是 RSA 最核心的問題，RSA 的美妙與奧秘也藏在這裡面。

1. 求N

求 N 公式：N = p × q

其中， p 和 q 是兩個質數 ，而且應該是很大又不是極大的質數。如果太小的話，密碼就容易被破解；如果極大的話，計算時間就會很長。比如 512 比特的長度（155 位的十進制數字）就比較合適。

這樣的質數是如何找出來的呢？ 需要通過 「偽隨機數生成器（PRNG）」 進行生成，然後再判斷其是否為質數 。如果不是，就需要重新生成，重新判斷。

2. 求L

求 L 公式：L = lcm(p-1, q-1)

lcm 代表 「最小公倍數（least common multiple）」 。注意，L 在加解密時都不需要， 僅出現在生成密鑰對的過程中 。

3. 求E

E 要滿足兩個條件：
1）1 < E < L
2）gcd(E,L) = 1

gcd 代表 「最大公約數（greatest common divisor）」 。gcd(E,L) = 1 就代表 「E 和 L 的最大公約數為1，也就是說， E 和 L 互質 」。

L 在第二步已經計算出來，而為了找到滿足條件的 E， 第二次用到 「偽隨機數生成器（PRNG）」 ，在 1 和 L 之間生成 E 的候選，判斷其是否滿足 「gcd(E,L) = 1」 的條件。

經過前三步，已經能夠得到密鑰對種的 「公鑰：{E, N}」 了。

4. 求D

D 要滿足兩個條件：
1）1 < D < L
2）E × D mod L = 1

只要 D 滿足上面的兩個條件，使用 {E, N} 進行加密的報文，就能夠使用 {D, N} 進行解密。

至此，N、L、E、D 都已經計算出來，再整理一下

模擬實踐的過程包括兩部分，第一部分是生成密鑰對，第二部分是對數據進行加解密。為了方便計算，都使用了較小的數字。

第一部分：生成密鑰對

1. 求N
准備兩個質數，p = 5，q = 7，N = 5 × 7 = 35

2. 求L
L = lcm(p-1, q-1) = lcm (4, 6) = 12

3. 求E
gcd(E, L) = 1，即 E 和 L 互質，而且 1 < E < L，滿足條件的 E 有多個備選：5、7、11，選擇最小的 5 即可。於是，公鑰 = {E, N} = {5, 35}

4. 求D
E × D mod L = 1，即 5 × D mod 12 = 1，滿足條件的 D 也有多個備選：5、17、41，選擇 17 作為 D（如果選擇 5 恰好公私鑰一致了，這樣不太直觀），於是，私鑰 = {D, N} = {17, 35}

至此，我們得到了公私鑰對：

第二部分：模擬加解密

明文我們也使用一個比較小的數字 -- 4，利用 RSA 的加密公式：

密文 = 明文 ^ E mod N = 4 ^ 5 mod 35 = 9
明文 = 密文 ^ D mod N = 9 ^ 17 mod 35 = 4

從這個模擬的小例子能夠看出，即使我們用了很小的數字，計算的中間結果也是超級大。如果再加上偽隨機數生成器生成一個數字，判斷其是否為質數等，這個過程想想腦仁兒就疼。還好，現代晶元技術，讓計算機有了足夠的運算速度。然而，相對於普通的邏輯運算，這類數學運算仍然是相當緩慢的。這也是一些非對稱密碼卡/套件中，很關鍵的性能規格就是密鑰對的生成速度

公鑰密碼體系中，用公鑰加密，用私鑰解密，公鑰公開，私鑰隱藏。因此：

加密公式為：密文 = 明文 ^ E mod N

破譯的過程就是對該公式進行逆運算。由於除了對明文進行冪次運算外， 還加上了「模運算」 ，因此在數學上， 該逆運算就不再是簡單的對數問題，而是求離散對數問題，目前已經在數學領域達成共識，尚未發現求離散對數的高效演算法 。

暴力破解的本質就是逐個嘗試。當前主流的 RSA 演算法中，使用的 p 和 q 都是 1024 位以上，這樣 N 的長度就是 2048 位以上。而 E 和 D 的長度和 N 差不多，因此要找出 D，就需要進行 2048 位以上的暴力破解。即使上文那個簡單的例子，算出（ 蒙出 ） 「9 ^ D mod 35 = 4」 中的 D 也要好久吧。

因為 E 和 N 是已知的，而 D 和 E 在數學上又緊密相關（通過中間數 L），能否通過一種反向的演算法來求解 D 呢？

從這個地方能夠看出，p 和 q 是極為關鍵的，這兩個數字不泄密，幾乎無法通過公式反向計算出 D。也就是說， 對於 RSA 演算法，質數 p 和 q 絕不能被黑客獲取，否則等價於交出私鑰 。

既然不能靠搶，N = p × q，N是已知的，能不能通過 「質因數分解」 來推導 p 和 q 呢？或者說， 一旦找到一種高效的 「質因數分解」 演算法，就能夠破解 RSA 演算法了 。

幸運的是，這和上述的「離散對數求解」一樣，當下在數學上還沒有找到這種演算法，當然，也無法證明「質因數分解」是否真的是一個困難問題 。因此只能靠硬算，只是當前的算力無法在可現實的時間內完成。 這也是很多人都提到過的，「量子時代來臨，當前的加密體系就會崩潰」，從算力的角度看，或許如此吧 。

既不能搶，也不能算，能不能猜呢？也就是通過 「推測 p 和 q 進行破解」 。

p 和 q 是通過 PRNG（偽隨機數生成器）生成的，於是，又一個關鍵因素，就是採用的 偽隨機數生成器演算法要足夠隨機 。

隨機數對於密碼學極為重要，後面會專門寫一篇筆記 。

前三種攻擊方式，都是基於 「硬碰硬」 的思路，而 「中間人攻擊」 則換了一種迂迴的思路，不去嘗試破解密碼演算法，而是欺騙通信雙方，從而獲取明文。具體來說，就是： 主動攻擊者 Mallory 混入發送者和接收者之間，面對發送者偽裝成接收者，面對接收者偽裝成發送者。

這個過程可以重復多次。需要注意的是，中間人攻擊方式不僅能夠針對 RSA，還可以針對任何公鑰密碼。能夠看到，整個過程中，公鑰密碼並沒有被破譯，密碼體系也在正常運轉，但機密性卻出現了問題，即 Alice 和 Bob 之間失去了機密性，卻在 Alice 和 Mallory 以及 Mallory 和 Bob 之間保持了機密性。即使公鑰密碼強度再強大 N 倍也無濟於事。也就是說，僅僅依靠密碼演算法本身，無法防禦中間人攻擊 。

而能夠抵禦中間人攻擊的，就需要用到密碼工具箱的另一種武器 -- 認證 。在下面一篇筆記中，就將涉及這個話題。

好了，以上就是公鑰密碼的基本知識了。

公鑰密碼體系能夠完美的解決對稱密碼體系中 「密鑰配送」 這個關鍵問題，但是拋開 「中間人攻擊」 問題不談，公鑰密碼自己也有個嚴重的問題：

公鑰密碼處理速度遠遠低於對稱密碼。不僅體現在密鑰對的生成上，也體現在加解密運算處理上。

因此，在實際應用場景下，往往會將對稱密碼和公鑰密碼的優勢相結合，構建一個 「混合密碼體系」 。簡單來說： 首先用相對高效的對稱密碼對消息進行加密，保證消息的機密性；然後用公鑰密碼加密對稱密碼的密鑰，保證密鑰的機密性。

下面是混合密碼體系的加解密流程圖。整個體系分為左右兩個部分：左半部分加密會話密鑰的過程，右半部分是加密原始消息的過程。原始消息一般較長，使用對稱密碼演算法會比較高效；會話密鑰一般比較短（十幾個到幾十個位元組），即使公鑰密碼演算法運算效率較低，對會話密鑰的加解密處理也不會非常耗時。

著名的密碼軟體 PGP、SSL/TLS、視頻監控公共聯網安全建設規范（GB35114） 等應用，都運用了混合密碼系統。

好了，以上就是公鑰密碼演算法的全部內容了，拖更了很久，以後還要更加勤奮一些。

為了避免被傻啦吧唧的審核機器人處理，後面就不再附漂亮姑娘的照片（也是為了你們的健康），改成我的攝影作品，希望不要對收視率產生影響，雖然很多小伙兒就是沖著姑娘來的。

就從喀納斯之旅開始吧。