學(xué)過(guò)算法的朋友都知道划栓，計(jì)算機(jī)中的算法其實(shí)就是數(shù)學(xué)運(yùn)算忠荞。所以，再講解RSA加密算法之前碧绞，有必要了解一下一些必備的數(shù)學(xué)知識(shí)头遭。我們就從數(shù)學(xué)知識(shí)開始講解。
RSA加密算法中鲫惶，只用到素?cái)?shù)欠母、互質(zhì)數(shù)、指數(shù)運(yùn)算六水、模運(yùn)算等幾個(gè)簡(jiǎn)單的數(shù)學(xué)知識(shí)掷贾。所以场靴，我們也需要了解這幾個(gè)概念即可旨剥。
素?cái)?shù)又稱質(zhì)數(shù)泞边，指在一個(gè)大于1的自然數(shù)中，除了1和此整數(shù)自身外烟具，不能被其他自然數(shù)整除的數(shù)。這個(gè)概念冀痕，我們?cè)谏铣踔醒陨撸踔列W(xué)的時(shí)候都學(xué)過(guò)了，這里就不再過(guò)多解釋了婿斥。
百度百科上的解釋是：公因數(shù)只有1的兩個(gè)數(shù)民宿，叫做互質(zhì)數(shù)活鹰。蕊蝗；維基百科上的解釋是：互質(zhì)，又稱互素子漩。若N個(gè)整數(shù)的最大公因子是1幢泼，則稱這N個(gè)整數(shù)互質(zhì)。
常見的互質(zhì)數(shù)判斷方法主要有以下幾種：
兩個(gè)不同的質(zhì)數(shù)一定是互質(zhì)數(shù)。例如别厘，2與7触趴、13與19。
一個(gè)質(zhì)數(shù)批狐，另一個(gè)不為它的倍數(shù)，這兩個(gè)數(shù)為互質(zhì)數(shù)食零。例如娜搂，3與10百宇、5與 26携御。
相鄰的兩個(gè)自然數(shù)是互質(zhì)數(shù)。如 15與 16誓军。
相鄰的兩個(gè)奇數(shù)是互質(zhì)數(shù)。如 49與 51债查。
較大數(shù)是質(zhì)數(shù)的兩個(gè)數(shù)是互質(zhì)數(shù)征绸。如97與88管怠。
小數(shù)是質(zhì)數(shù)祝拯，大數(shù)不是小數(shù)的倍數(shù)的兩個(gè)數(shù)是互質(zhì)數(shù)。例如 7和 16康嘉。
2和任何奇數(shù)是互質(zhì)數(shù)敷钾。例如2和87阻荒。
1不是質(zhì)數(shù)也不是合數(shù)，它和任何一個(gè)自然數(shù)在一起都是互質(zhì)數(shù)。如1和9908舶掖。
輾轉(zhuǎn)相除法。
指數(shù)運(yùn)算又稱乘方計(jì)算鲫售，計(jì)算結(jié)果稱為冪。nm指將n自乘m次秦效。把nm看作乘方的結(jié)果，叫做”n的m次冪”或”n的m次方”。其中夜惭，n稱為“底數(shù)”，m稱為“指數(shù)”若皱。
模運(yùn)算即求余運(yùn)算晦譬。“南穹”是“Mod”的音譯。和模運(yùn)算緊密相關(guān)的一個(gè)概念是“同余”。數(shù)學(xué)上柔纵，當(dāng)兩個(gè)整數(shù)除以同一個(gè)正整數(shù)，若得相同余數(shù)进苍，則二整數(shù)同余加缘。
兩個(gè)整數(shù)a，b觉啊，若它們除以正整數(shù)m所得的余數(shù)相等，則稱a沈贝，b對(duì)于模m同余，記作:?a ≡ b (mod m)宋下；讀作：a同余于b模m嗡善，或者，a與b關(guān)于模m同余学歧。例如：26 ≡ 14 (mod 12)罩引。
RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的枝笨。當(dāng)時(shí)他們?nèi)硕荚诼槭±砉W(xué)院工作袁铐。RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的揭蜒。
假設(shè)Alice想要通過(guò)一個(gè)不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來(lái)產(chǎn)生一個(gè)公鑰和一個(gè)私鑰：
隨意選擇兩個(gè)大的質(zhì)數(shù)p和q剔桨，p不等于q屉更，計(jì)算N=pq。
根據(jù)歐拉函數(shù)洒缀，求得r = (p-1)(q-1)
選擇一個(gè)小于 r 的整數(shù)?e瑰谜，求得 e 關(guān)于模 r 的模反元素，命名為d树绩。（模反元素存在萨脑，當(dāng)且僅當(dāng)e與r互質(zhì)）
將?p?和?q?的記錄銷毀。
(N,e)是公鑰饺饭，(N,d)是私鑰渤早。Alice將她的公鑰(N,e)傳給Bob，而將她的私鑰(N,d)藏起來(lái)砰奕。
假設(shè)Bob想給Alice送一個(gè)消息m蛛芥，他知道Alice產(chǎn)生的N和e。他使用起先與Alice約好的格式將m轉(zhuǎn)換為一個(gè)小于N的整數(shù)n军援，比如他可以將每一個(gè)字轉(zhuǎn)換為這個(gè)字的Unicode碼仅淑，然后將這些數(shù)字連在一起組成一個(gè)數(shù)字。假如他的信息非常長(zhǎng)的話胸哥，他可以將這個(gè)信息分為幾段涯竟，然后將每一段轉(zhuǎn)換為n。用下面這個(gè)公式他可以將n加密為c：
ne≡ c (mod N)
計(jì)算c并不復(fù)雜空厌。Bob算出c后就可以將它傳遞給Alice庐船。
Alice得到Bob的消息c后就可以利用她的密鑰d來(lái)解碼。她可以用以下這個(gè)公式來(lái)將c轉(zhuǎn)換為n：
cd≡ n (mod N)
得到n后嘲更，她可以將原來(lái)的信息m重新復(fù)原筐钟。
解碼的原理是：
cd≡ ne·d(mod N)
以及ed≡ 1 (modp-1)和ed≡ 1 (modq-1)。由費(fèi)馬小定理可證明（因?yàn)?i>p和q是質(zhì)數(shù)）
ne·d≡ n (mod p)? 和? ne·d≡ n (mod q)
這說(shuō)明（因?yàn)?i>p和q是不同的質(zhì)數(shù)赋朦，所以p和q互質(zhì)）
ne·d≡ n (mod pq)
RSA也可以用來(lái)為一個(gè)消息署名篓冲。假如甲想給乙傳遞一個(gè)署名的消息的話，那么她可以為她的消息計(jì)算一個(gè)散列值(Message digest)宠哄，然后用她的密鑰(private key)加密這個(gè)散列值并將這個(gè)“署名”加在消息的后面壹将。這個(gè)消息只有用她的公鑰才能被解密。乙獲得這個(gè)消息后可以用甲的公鑰解密這個(gè)散列值毛嫉，然后將這個(gè)數(shù)據(jù)與他自己為這個(gè)消息計(jì)算的散列值相比較诽俯。假如兩者相符的話，那么他就可以知道發(fā)信人持有甲的密鑰承粤，以及這個(gè)消息在傳播路徑上沒(méi)有被篡改過(guò)暴区。
下面闯团，開始我們的重點(diǎn)環(huán)節(jié)：編程實(shí)踐。在開始編程前颜启，我們通過(guò)計(jì)算偷俭，來(lái)確定公鑰和密鑰。
假設(shè)p = 3缰盏、q = 11（p涌萤，q都是素?cái)?shù)即可。）口猜，則N = pq = 33负溪；
r = (p-1)(q-1) = (3-1)(11-1) = 20；
根據(jù)模反元素的計(jì)算公式济炎，我們可以得出川抡，e·d ≡ 1 (mod 20),即e·d = 20n+1 (n為正整數(shù))；我們假設(shè)n=1须尚，則e·d = 21崖堤。e、d為正整數(shù)耐床，并且e與r互質(zhì)密幔，則e = 3，d = 7撩轰。（兩個(gè)數(shù)交換一下也可以胯甩。）
到這里，公鑰和密鑰已經(jīng)確定堪嫂。公鑰為(N, e) = (33, 3)偎箫，密鑰為(N, d) = (33, 7)。
下面我們使用Java來(lái)實(shí)現(xiàn)一下加密和解密的過(guò)程皆串。具體代碼如下：
RSA算法實(shí)現(xiàn)：
[java]?view plain?copy
package?security.rsa;????public?class?RSA?{????????????/**??????*??加密淹办、解密算法??????*?@param?key?公鑰或密鑰??????*?@param?message?數(shù)據(jù)??????*?@return??????*/??????public?static?long?rsa(int?baseNum,?int?key,?long?message){??????????if(baseNum?<?1?||?key?<?1){??????????????return?0L;??????????}??????????//加密或者解密之后的數(shù)據(jù)??????????long?rsaMessage?=?0L;????????????????????//加密核心算法??????????rsaMessage?=?Math.round(Math.pow(message,?key))?%?baseNum;??????????return?rsaMessage;??????}????????????????????????public?static?void?main(String[]?args){??????????//基數(shù)??????????int?baseNum?=?3?*?11;??????????//公鑰??????????int?keyE?=?3;??????????//密鑰??????????int?keyD?=?7;??????????//未加密的數(shù)據(jù)??????????long?msg?=?24L;??????????//加密后的數(shù)據(jù)??????????long?encodeMsg?=?rsa(baseNum,?keyE,?msg);??????????//解密后的數(shù)據(jù)??????????long?decodeMsg?=?rsa(baseNum,?keyD,?encodeMsg);????????????????????System.out.println("加密前："?+?msg);??????????System.out.println("加密后："?+?encodeMsg);??????????System.out.println("解密后："?+?decodeMsg);????????????????}??????????????}??
RSA算法結(jié)果：
加密前：24
加密后：30
解密后：24
（看程序最清楚了，對(duì)于要加密的數(shù)字m, m^e%N=c, c就是加密之后的密文恶复。c^d%N=m, 就能解密得到m）
當(dāng)p和q是一個(gè)大素?cái)?shù)的時(shí)候娇唯，從它們的積pq去分解因子p和q，這是一個(gè)公認(rèn)的數(shù)學(xué)難題寂玲。然而，雖然RSA的安全性依賴于大數(shù)的因子分解梗摇，但并沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)拓哟。
1994年彼得·秀爾（Peter Shor）證明一臺(tái)量子計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行因數(shù)分解。假如量子計(jì)算機(jī)有朝一日可以成為一種可行的技術(shù)的話伶授，那么秀爾的算法可以淘汰RSA和相關(guān)的衍生算法断序。（即依賴于分解大整數(shù)困難性的加密算法）
另外流纹，假如N的長(zhǎng)度小于或等于256位，那么用一臺(tái)個(gè)人電腦在幾個(gè)小時(shí)內(nèi)就可以分解它的因子了汛蝙。1999年瘦癌，數(shù)百臺(tái)電腦合作分解了一個(gè)512位長(zhǎng)的N誓沸。1997年后開發(fā)的系統(tǒng)，用戶應(yīng)使用1024位密鑰茸炒，證書認(rèn)證機(jī)構(gòu)應(yīng)用2048位或以上。
雖然RSA加密算法作為目前最優(yōu)秀的公鑰方案之一阵苇，在發(fā)表三十多年的時(shí)間里壁公，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受绅项。但是紊册，也不是說(shuō)RSA沒(méi)有任何缺點(diǎn)。由于沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度的等價(jià)性快耿。所以囊陡，RSA的重大缺陷是無(wú)法從理論上把握它的保密性能如何。在實(shí)踐上掀亥，RSA也有一些缺點(diǎn)：
產(chǎn)生密鑰很麻煩撞反，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密铺浇；
分組長(zhǎng)度太大痢畜，為保證安全性，n 至少也要 600 bits 以上鳍侣，使運(yùn)算代價(jià)很高丁稀，尤其是速度較慢，倚聚。
