RSA算法
當(dāng)前最著名、應(yīng)用最廣泛的公鑰系統(tǒng)RSA是在1978年，由美國麻省理工學(xué)院(MIT)的Ron Rivest, Adi Shamir 和Leonard Adleman在題為《獲得數(shù)字簽名和公開鑰密碼系統(tǒng)的方法》的論文中提出的。它是一個(gè)基于數(shù)論的非對(duì)稱(公開鑰)密碼體制，是一種分組密碼體制。其名稱來自于三個(gè)發(fā)明者的姓名首字母。 它的安全性是基于大整數(shù)素因子分解的困難性，而大整數(shù)因子分解問題是數(shù)學(xué)上的著名難題，至今沒有有效的方法予以解決，因此可以確保RSA算法的安全性。RSA系統(tǒng)是公鑰系統(tǒng)的最具有典型意義的方法，大多數(shù)使用公鑰密碼進(jìn)行加密和數(shù)字簽名的產(chǎn)品和標(biāo)準(zhǔn)使用的都是RSA算法。
RSA算法是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，因此它為公用網(wǎng)絡(luò)上信息的加密和鑒別提供了一種基本的方法。它通常是先生成一對(duì)RSA 密鑰，其中之一是保密密鑰，由用戶保存；另一個(gè)為公開密鑰，可對(duì)外公開，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊(cè)，人們用公鑰加密文件發(fā)送給個(gè)人，個(gè)人就可以用私鑰解密接受。為提高保密強(qiáng)度，RSA密鑰至少為500位長，一般推薦使用1024位。
該算法基于下面的兩個(gè)事實(shí),這些事實(shí)保證了RSA算法的安全有效性：
1.已有確定一個(gè)數(shù)是不是質(zhì)數(shù)的快速算法；
2. 尚未找到確定一個(gè)合數(shù)的質(zhì)因子的快速算法。
工作原理
1) 任意選取兩個(gè)不同的大質(zhì)數(shù)p和q，計(jì)算乘積r=p*q；
2) 任意選取一個(gè)大整數(shù)e，e與(p-1)*(q-1)互質(zhì)，整數(shù)e用做加密密鑰。注意：e的選取是很容易的，例如，所有大于p和q的質(zhì)數(shù)都可用。
3) 確定解密密鑰d： d * e = 1 modulo（p - 1）*（q - 1） 根據(jù)e、p和q可以容易地計(jì)算出d。
4) 公開整數(shù)r和e，但是不公開d；
5) 將明文P (假設(shè)P是一個(gè)小于r的整數(shù))加密為密文C，計(jì)算方法為：
C = Pe modulo r
6) 將密文C解密為明文P，計(jì)算方法為：
P = Cd modulo r
然而只根據(jù)r和e（不是p和q）要計(jì)算出d是不可能的。因此，任何人都可對(duì)明文進(jìn)行加密，但只有授權(quán)用戶（知道d）才可對(duì)密文解密。
數(shù)學(xué)原理
定理
若 p, q 是相異質(zhì)數(shù), rm == 1 mod (p-1)(q-1),
a 是任意一個(gè)正整數(shù), b == a^m mod pq, c == b^r mod pq,
則 c == a mod pq
證明的過程, 會(huì)用到費(fèi)馬小定理, 敘述如下:
m 是任一質(zhì)數(shù), n 是任一整數(shù), 則 n^m == n mod m
(換另一句話說, 如果 n 和 m 互質(zhì), 則 n^(m-1) == 1 mod m)
運(yùn)用一些基本的群論的知識(shí), 就可以很容易地證出費(fèi)馬小定理的........
證明
因?yàn)?rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整數(shù)
因?yàn)樵?modulo 中是 preserve 乘法的
(x == y mod z and u == v mod z => xu == yv mod z),
所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq
1. 如果 a 不是 p 的倍數(shù), 也不是 q 的倍數(shù)時(shí),
則 a^(p-1) == 1 mod p (費(fèi)馬小定理) => a^(k(p-1)(q-1)) == 1 mod p
a^(q-1) == 1 mod q (費(fèi)馬小定理) => a^(k(p-1)(q-1)) == 1 mod q
所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1
即 a^(k(p-1)(q-1)) == 1 mod pq
=> c == a^(k(p-1)(q-1)+1) == a mod pq
2. 如果 a 是 p 的倍數(shù), 但不是 q 的倍數(shù)時(shí),
則 a^(q-1) == 1 mod q (費(fèi)馬小定理)
=> a^(k(p-1)(q-1)) == 1 mod q
=> c == a^(k(p-1)(q-1)+1) == a mod q
=> q | c - a
因 p | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod p
=> p | c - a
所以, pq | c - a => c == a mod pq
3. 如果 a 是 q 的倍數(shù), 但不是 p 的倍數(shù)時(shí), 證明同上
4. 如果 a 同時(shí)是 p 和 q 的倍數(shù)時(shí),
則 pq | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod pq
=> pq | c - a
=> c == a mod pq
Q.E.D.
這個(gè)定理說明 a 經(jīng)過編碼為 b 再經(jīng)過解碼為 c 時(shí), a == c mod n (n = pq)....
但我們?cè)谧鼍幋a解碼時(shí), 限制 0 <= a < n, 0 <= c < n,
所以這就是說 a 等於 c, 所以這個(gè)過程確實(shí)能做到編碼解碼的功能.....
為了說明該算法的工作過程,我們下面給出一個(gè)簡單例子,顯然我們?cè)谶@只能取很小的數(shù)字，但是如上所述，為了保證安全，在實(shí)際應(yīng)用上我們所用的數(shù)字要大的多得多。
例：選取p=3, q=5，則r=15，（p-1）*（q-1）=8。選取e=11（大于p和q的質(zhì)數(shù)），通過d * 11 = 1 modulo 8，計(jì)算出d =3。
假定明文為整數(shù)13。則密文C為
C = Pe modulo r
= 1311 modulo 15
= 1,792,160,394,037 modulo 15
= 7
復(fù)原明文P為：
P = Cd modulo r
= 73 modulo 15
= 343 modulo 15
= 13
因?yàn)閑和d互逆，公開密鑰加密方法也允許采用這樣的方式對(duì)加密信息進(jìn)行"簽名"，以便接收方能確定簽名不是偽造的。
兩個(gè)在不安全信道中通信的人，假設(shè)為Alice（收信者）和Bob（發(fā)信者），他們希望能夠安全的通信而不被他們的敵手Oscar破壞。Alice 想到了一種辦法，她使用了一種鎖（相當(dāng)于公鑰），這種鎖任何人只要輕輕一按就可以鎖上，但是只有Alice的鑰匙（相當(dāng)于私鑰）才能夠打開。然后 Alice 對(duì)外發(fā)送無數(shù)把這樣的鎖，任何人比如Bob想給她寄信時(shí)，只需找到一個(gè)箱子，然后用一把Alice的鎖將其鎖上再寄給Alice，這時(shí)候任何人（包括 Bob自己）除了擁有鑰匙的Alice，都不能再打開箱子，這樣即使Oscar能找到Alice的鎖，即使Oscar能在通信過程中截獲這個(gè)箱子，沒有 Alice的鑰匙他也不可能打開箱子，而Alice的鑰匙并不需要分發(fā)，這樣 Oscar也就無法得到這把“私人密鑰”。
優(yōu)點(diǎn)
RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。該算法的加密密鑰和加密算法分開，使得密鑰分配更為方便。它特別符合計(jì)算機(jī)網(wǎng)絡(luò)環(huán)境。對(duì)于 網(wǎng)上的大量用戶，可以將加密密鑰用電話簿的方式印出。如果某用戶想與另一用戶進(jìn)行保密通信，只需從公鑰簿上查出對(duì)方的加密密鑰，用它對(duì)所傳送的信息加密發(fā)出即可。對(duì)方收到信息后，用僅為自己所知的解密密鑰將信息脫密，了解報(bào)文的內(nèi)容。由此可看出，RSA算法解決了大量網(wǎng)絡(luò)用戶密鑰管理的難題，這是公鑰密碼系統(tǒng)相對(duì)于對(duì)稱密碼系統(tǒng)最突出的優(yōu)點(diǎn)。
缺點(diǎn)
1)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。
2)安全性, RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)，而且密碼學(xué)界多數(shù)人士傾向于因子分解不是NPC問題。目前，人們已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)，這就要求使用更長的密鑰，速度更慢；另外，目前人們正在積極尋找攻擊RSA的方法，如選擇密文攻擊，一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實(shí)體簽署。然后，經(jīng)過計(jì)算就可得到它所想要的信息。實(shí)際上，攻擊利用的都是同一個(gè)弱點(diǎn)，即存在這樣一個(gè)事實(shí)：乘冪保留了輸入的乘法結(jié)構(gòu)：
( XM )d = Xd *Md mod n
前面已經(jīng)提到，這個(gè)固有的問題來自于公鑰密碼系統(tǒng)的最有用的特征--每個(gè)人都能使用公鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是采用好的公鑰協(xié)議，保證工作過程中實(shí)體不對(duì)其他實(shí)體任意產(chǎn)生的信息解密，不對(duì)自己一無所知的信息簽名；另一條是決不對(duì)陌生人送來的隨機(jī)文檔簽名，簽名時(shí)首先使用One-Way Hash Function對(duì)文檔作HASH處理，或同時(shí)使用不同的簽名算法。除了利用公共模數(shù)，人們還嘗試一些利用解密指數(shù)或φ（n）等等攻擊.
3)速度太慢,由于RSA 的分組長度太大，為保證安全性，n 至少也要 600 bitx以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí)；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。目前，SET(Secure Electronic Transaction)協(xié)議中要求CA采用2048比特長的密鑰，其他實(shí)體使用1024比特的密鑰。為了速度問題,目前人們廣泛使用單,公鑰密碼結(jié)合使用的方法,優(yōu)缺點(diǎn)互補(bǔ):單鑰密碼加密速度快,人們用它來加密較長的文件,然后用RSA來給文件密鑰加密,極好的解決了單鑰密碼的密鑰分發(fā)問題。
公鑰加密算法中使用最廣的是RSA。RSA算法研制的最初理念與目標(biāo)是努力使互聯(lián)網(wǎng)安全可靠，旨在解決DES算法秘密密鑰的利用公開信道傳輸分發(fā)的難題。而實(shí)際結(jié)果不但很好地解決了這個(gè)難題；還可利用RSA來完成對(duì)電文的數(shù)字簽名以抗對(duì)電文的否認(rèn)與抵賴；同時(shí)還可以利用數(shù)字簽名較容易地發(fā)現(xiàn)攻擊者對(duì)電文的非法篡改，以保護(hù)數(shù)據(jù)信息的完整性。目前為止，很多種加密技術(shù)采用了RSA算法，該算法也已經(jīng)在互聯(lián)網(wǎng)的許多方面得以廣泛應(yīng)用，包括在安全接口層（SSL）標(biāo)準(zhǔn)（該標(biāo)準(zhǔn)是網(wǎng)絡(luò)瀏覽器建立安全的互聯(lián)網(wǎng)連接時(shí)必須用到的）方面的應(yīng)用。此外，RSA加密系統(tǒng)還可應(yīng)用于智能IC卡和網(wǎng)絡(luò)安全產(chǎn)品。
但目前RSA算法的專利期限即將結(jié)束，取而代之的是基于橢圓曲線的密碼方案（ECC算法）。較之于RSA算法，ECC有其相對(duì)優(yōu)點(diǎn)，這使得ECC的特性更適合當(dāng)今電子商務(wù)需要快速反應(yīng)的發(fā)展潮流。此外，一種全新的量子密碼也正在發(fā)展中。
