Rabin演算法的攻擊方法

1. 有關Miller-Rabin演算法

在《現代密碼學-原理與協議》這本書里看到過類似結論的證明. （7.38）

不過這個1/2不是針對1~n-1的整數集，而是針對1~n-1中元素構成的模n的乘法群Zn*，這個群中僅有那些滿足gcd(a, n) = 1這個條件的元素a。另外，需假設n若n為合數，則至少有一個證據證明它是合數。

需要一點群論的知識

1. 若G為有限群，假設H含有G的「1」(幺元)，且對於H中任意的a、b恆有ab屬於H，則H是G的子群

2. 若H為有限群G的真子群，則|H| <= |G/2|. （| |代表元素數)

證明：

定義Bad為乘法群Zn*中，不是"n為合數"的證據的元素的集合。（即滿足 a^(n-1) = 1 mod n）

顯然，1 屬於 Bad。

若a,b屬於Bad, 則 (ab) ^ (n-1) = a^(n-1) * b^(n-1)= 1*1 mod n =1 mod n

所以 ab 也屬於 Bad

由 1 可得 (Bad, *)是Zn*的一個子群

而因為若n為合數，則至少有一個1~n-1中的數使a^(n-1) 不等於 1 mod n，因此Bad為Zn*的真子群

再由2可得 Bad中元素數小於等於Zn*元素數的一半

那麼，反過來，Zn*中可以成為證據的元素至少佔Zn*中全體元素的1/2

維基網路Miller-Rabin的英文詞條下面的參考文獻中，他們的原始論文里有完整的對於n為奇合數的判定成功概率的完整證明

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） 等應用，都運用了混合密碼系統。

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

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

就從喀納斯之旅開始吧。

3. Miller Rabin演算法的優化實現

Miller-Rabin演算法最為耗時的步驟在2.2模冪操作和2.3.2 循環。對演算法的優化實現主要集中在對這兩部分運算的優 化。對模冪操作的優化有兩種途徑：減少模冪演算法中的模乘 操作和優化模乘操作。在求模冪的過程中不能先求冪最後一次求模，這樣會產生一個十分巨大的中間結果，造成實際的 不可操作，所以在求模冪的演算法中用模乘代替乘法，使得中 間結果的長度不超過模的長度。對模冪演算法的優化，我們使 用改進的滑動窗口演算法結合Montgomery模乘和模平方演算法。表1給出模冪演算法的比較。 模冪演算法 預先計算 模平方 模乘法 模平方 模乘法 最壞情況 平均情況 平方乘演算法滑動窗口類演算法 改進的滑動窗口演算法 011 02k -32k-1-1 tt-(k-1)≤次數≤t t-(k-1)≤次數≤t t (t/k)-1 (t/k)-1 t/2 t/k(2k-1)/ 2kk≤t/k(2 -1)/ * 模冪演算法比較，其中k是窗口大小，根據情況 選擇以達到最優，t是指數的二進制位數。 優化的模冪演算法描述：輸入： x，e=(e tet-1?e1e0)2，其中et=1，k≥1( 窗口大小)輸出： xe mod n1、預計算1.1、x1← MontMul(x， R2，n)，x2←MontSqu(x 1， n)1.2、對i 從1 到2k-1-1計算x2i+1←MontMul(x2i-1， x2，n)2、A←R，i ←t3、 當i≥ 0時作下面的操作： 3.1、如果ei=0，A←MontSqu(A ，n)，i← i-13.2、否則找到最長的位串eiei-1?es使得i-s+1≤k並且es=1,計算3.2.1、A <－A2i-s+1 ， (利 用MontSqu函數計算)3.2.2、A <－A*X(ee ...e )2 ，(利 用MontMul函數計算)3.2.3、i ←s-14、A←MontMul(A ，1 ，n)5、返回A其中MontMul(x,y,n) 是Montgomery模乘函數，函數輸出 結果為x*y*R-1 mod n，MontSqu(x,n) 是Montgomery模平方函 數，輸出結果為x2R-1 mod n。模乘演算法如果採用大整數乘法 和除法求模乘，因為涉及耗時的除法操作，所以要相對較 慢，結合大整數乘法和Barrett求模演算法可以用2(n2+3n+1) 步 單精度乘法完成。使用Montgomery求模演算法結合大整數乘法 演算法，可以 在 2n(n+1) 步單精度乘法內完成演算法。 Montgomery模平方的操作可以在3n(n+1) /2步單精度乘法內 完成，而Barrett模平方需要(3n(n+3)/2+1) 步單精度乘法。結 合改進的滑動窗口演算法和Montgomery類演算法，可以得到目前 非特殊情況下的最優的模冪演算法。在Miller-Rabin演算法的2.3.2循環中的模平方操作我們沒有 使用Montgomery模平方演算法，因為該演算法給出的結果帶有R-1這個參數，在2.3.2循環中處理掉這個參數將占整個循環運 行時間中的很大部分，尤其是在循環的控制參數s 相對較小的時候。我們在這里使用大整數平方演算法結合Barrett求模算 法，2.3.2的循環最壞情況需要(s-1)(3n(n+3)/2+1)步單精度乘法。

4. C語言 設計並實現一種大素數隨機生成方法； 實現一種快速判定任意一個大數是否是素數方法 跪求啊

Rabin -Miller演算法是典型的驗證一個數字是否為素數的方法。判斷素數的方法是Rabin-Miller概率測試，那麼他具體的流程是什麼呢。假設我們要判斷n是不是素數，首先我們必須保證n 是個奇數，那麼我們就可以把n 表示為 n = (2^r)*s+1,注意s 也必須是一個奇數。然後我們就要選擇一個隨機的整數a (1<=a<=n-1)，接下來我們就是要判斷 a^s=1 (mod n) 或a^((2^j)*s)= -1（mod n）(0<=j如果任意一式成立，我們就說n通過了測試，但是有可能不是素數也能通過測試。所以我們通常要做多次這樣的測試，以確保我們得到的是一個素數。（DDS的標準是要經過50次測試）
採用Rabin-Miller演算法進行驗算
首先選擇一個代測的隨機數p，計算b，b是2整除p-1的次數。然後計算m，使得n=1+(2^b)m。
（1） 選擇一個小於p的隨機數a。
（2） 設j=0且z=a^m mod p
（3） 如果z=1或z=p-1，那麽p通過測試，可能使素數
（4） 如果j>0且z=1, 那麽p不是素數
（5） 設j=j+1。如果j且z<>p-1,設z=z^2 mod p，然後回到(4)。如果z=p-1，那麽p通過測試，可能為素數。
（6） 如果j=b 且z<>p-1，不是素數

#include<iostream.h>
#include<time.h>
#include<stdlib.h>

//隨機數產生器
//產生m~n之間的一個隨機數
unsigned long random(unsigned long m,unsigned long n)
{
srand((unsigned long)time(NULL));
return(unsigned long)(m+rand()%n);
}
//模冪函數
//返回X^YmodN
long PowMod(long x,long y,long n)
{
long s,t,u;

s=1;t=x;u=y;
while(u){
if(u&1)s=(s*t)%n;
u>>=1;
t=(t*t)%n;
}
return s;
}

//Rabin-Miller素數測試，通過測試返回1，否則返回0。
//n是待測素數。
//注意：通過測試並不一定就是素數，非素數通過測試的概率是1/4

int RabinMillerKnl(unsigned long n)
{
unsigned long b,m,j,v,i;
//先計算出m、j，使得n-1=m*2^j，其中m是正奇數，j是非負整數
m=n-1;
j=0;
while(!(m&1))
{
++j;
m>>=1;
}
//隨機取一個b，2<=b<n-1
b=random(2,m);
//計算v=b^mmodn
v=PowMod(b,m,n);
//如果v==1，通過測試
if(v==1)
{
return 1;
}

i=1;
//如果v=n-1，通過測試
while(v!=n-1)
{
//如果i==l，非素數，結束
if(i==j)
{
return 0;
}
//v=v^2modn，i=i+1
v=PowMod(v,2,n);
i++;
}
return 1;
}
intmain()
{
unsigned long p;
int count=0;
cout<<"請輸入一個數字"<<endl;
cin>>p;
for(int temp=0;temp<5;temp++)
{
if(RabinMillerKnl(p))
{
count++;
}
else
break;

}

if(count==5)
cout<<"一共通過5次測試，是素數！"<<endl;
else
cout<<"不是素數"<<endl;
return 0;
}

5. Miller Rabin演算法的在應用中的考慮

(i)(ii)p k ,1pk , tk 2 4 2k 3 / 2 2 tkfor k 2t 1 / 2 4 2 tk(iii) p 7 k 2 5t k , t201 k15 / 4 27k / 2 2 t12 k 2k / 4 3tfor k / 9(iv) pk , tt k / 4, k1 k15 / 4 2721k / 22t for tk / 4, k 21Miller-Rabin演算法的應用主要集中在構建密碼安全體系的素數生成模塊中，當輸入的待測數n是很大(例如： 1024bits)的隨機數的時候，演算法的誤判概率遠遠小於上面給出的理論 上的誤判概率上界。設Pk,t 代表(k=log2 n，t是測試的輪數)在 素數生成演算法中應用t輪Miller-Rabin 演算法給出錯誤結果的概 率，則有如上所示的誤判概率公式。在一般的密碼安全體系中，誤判概率小於 (1/2)就可以滿足安全需求。表2給出了當p(k,t) ≤ (1/2)80的時候對應的k和t的值。
表2 k,t對應值 k 100 150 200 25 300 350 400 450 550 650 850 1300 t 27 18 15 12 9 8 7 6 5 4 3 2 在基底的選擇上，因為以2作為基底可以剔除很大部分 合數，並且對以2為底的模冪的運算很快，所以可以考慮在 應用中固定使用基底2，其它基底隨機選擇，這樣的改進可 以提高演算法的運行速度。