周五剛好在俞研的網(wǎng)絡(luò)安全課上學(xué)了RSA，回來(lái)想實(shí)現(xiàn)以下，由于以前數(shù)論方面的積累還算比較深厚，很快就過(guò)了這一題，呵呵:-)
總結(jié)一下吧，這題可以說(shuō)是數(shù)論部分的一個(gè)大綜合題，因?yàn)樗鼘⑺惴▽?dǎo)論上數(shù)論這部分的知識(shí)點(diǎn)全部包含了進(jìn)來(lái)，包括gcd,擴(kuò)展gcd,模線性方程，a^b mod c(還是比較難的那種，相關(guān)題目可以看一下FOZ上面的2道題),miller-rabin素?cái)?shù)測(cè)試，pollard_rho質(zhì)因數(shù)分解等等，把這題搞定了說(shuō)明你對(duì)算法導(dǎo)論的數(shù)論部分已經(jīng)可以做到熟練掌握了，相當(dāng)于<算法導(dǎo)論>數(shù)論部分的期末測(cè)試，呵呵^_^。
下面簡(jiǎn)要的說(shuō)一下這題的做法，首先簡(jiǎn)要介紹一下RSA算法加密解密的過(guò)程：
我們首先生成兩個(gè)大的素?cái)?shù)P,Q,乘起來(lái)得
N=P*Q.然后算出N的歐拉函數(shù)
Phi(N)=(P-1)*(Q-1).(什么是歐拉函數(shù)？這個(gè)世界上有一種東西叫做百度...）,然后我們?nèi)∫粋€(gè)范圍在
[1,phi(N)]中且與phi(N)互質(zhì)的正整數(shù)E.它就是所謂的公鑰。得到公鑰之后，我們?cè)偎愠鯡關(guān)于
phi(N)的逆元D,即E*D mod phi(N)=1.這個(gè)D就是私鑰。在得到這些數(shù)據(jù)以后，P,Q被丟棄，E,N做為公鑰被公開(kāi)，D做為私鑰被解密人私人保存。
好了，下面看一下如何用公鑰和私鑰對(duì)數(shù)據(jù)進(jìn)行加密解密。
假設(shè)有一個(gè)明文M,那么它所對(duì)應(yīng)的密文就是
C=M^E mod N.如果我們現(xiàn)在得到一個(gè)密文C,那么它所對(duì)應(yīng)的明文就是
M=C^D mod N也就是說(shuō)，任何人都可以用公鑰對(duì)數(shù)據(jù)進(jìn)行加密，但是只有擁有私鑰的人才可以對(duì)數(shù)據(jù)進(jìn)行解密。
那么RSA算法為什么不易被破解呢？從解密的過(guò)程來(lái)看如果你能夠知道D那么你就能解密數(shù)據(jù)。而E,D是逆元關(guān)系，要求出D,需要知道phi(N)，由于N非常之大，普通的做法是從1開(kāi)始枚舉到N-1，計(jì)算和N互質(zhì)的元素個(gè)數(shù)。可是N可以是幾百位到上千位的數(shù)字，普通的計(jì)算機(jī)只能在1s內(nèi)算到10^8量級(jí)，顯然是不可能破解的。唯一有可能的方法基于大素?cái)?shù)分解，如果你能將N分解成P*Q的乘積。那么就可以直接利用公式phi(N)=(P-1)*(Q-1)繞開(kāi)暴力求解歐拉函數(shù)的過(guò)程，從而實(shí)現(xiàn)RSA的破解。
這道題就是模擬這個(gè)破解過(guò)程，下面來(lái)說(shuō)說(shuō)具體的做法：
1.首先用miller-rabin,pollard_rho做大整數(shù)的質(zhì)因數(shù)分解，得到兩個(gè)素?cái)?shù)P,Q，pollard_rho的復(fù)雜度在N^0.25次方，那么一個(gè)64位的整數(shù) 要計(jì)算的次數(shù)為 2^64^0.25=2^16 =65536次，可以瞬間出解。
2.求出phi(N)=(P-1)*(Q-1)
3.然后用ext_gcd求出E關(guān)于phi(N)的逆元。
4.用得到的私鑰對(duì)數(shù)據(jù)C進(jìn)行解密即可。
PS:對(duì)這題而言，僅僅完成上述步驟還是不夠的。因?yàn)镹達(dá)到2^62次方，即使是使用無(wú)符號(hào)long long ,也很容易因?yàn)槌龀朔ú僮鞫绯觥＿@也是網(wǎng)上說(shuō)要避免使用擴(kuò)展歐幾里德的原因。其實(shí)實(shí)現(xiàn)的時(shí)候，我們可以自己寫(xiě)一個(gè)特殊的乘法（內(nèi)部用加法實(shí)現(xiàn)），由于使用的無(wú)符號(hào)的long long ，第64位剛好可以用來(lái)保存兩個(gè)數(shù)加過(guò)之后的進(jìn)位位，再模除又可以保證其在2^62范圍內(nèi)，即可避免溢出。