RSA是第一個(gè)比較完善的公開(kāi)密鑰算法，它既能用于加密，也能用于數(shù)字簽名。RSA以它的三個(gè)發(fā)明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名，這個(gè)算法經(jīng)受住了多年深入的密碼分析，雖然密碼分析者既不能證明也不能否定RSA的安全性，但這恰恰說(shuō)明該算法有一定的可信性，目前它已經(jīng)成為最流行的公開(kāi)密鑰算法。
RSA的安全基于大數(shù)分解的難度。其公鑰和私鑰是一對(duì)大素?cái)?shù)（100到200位十進(jìn)制數(shù)或更大）的函數(shù)。從一個(gè)公鑰和密文恢復(fù)出明文的難度，等價(jià)于分解兩個(gè)大素?cái)?shù)之積（這是公認(rèn)的數(shù)學(xué)難題）。
RSA的公鑰、私鑰的組成，以及加密、解密的公式可見(jiàn)于下表：
| Table | Are |
|---|---|
| 公鑰 KU | n:兩素?cái)?shù)p和q的乘積（p和q必須保密） e:與（p-1）(q-1)互質(zhì) |
| 私鑰 KR | d: $e^{-1}(mod(p-1)(q-1))$ |
| 加密 | $C ≡ m^e \quad mod \quad n$ |
| 解密 | $m ≡ c^d \quad mod \quad n$ |
一、 什么是“素?cái)?shù)”？
素?cái)?shù)是這樣的整數(shù)，它除了能表示為它自己和1的乘積以外，不能表示為任何其它兩個(gè)整數(shù)的乘積。例如，15＝3＊5，所以15不是素?cái)?shù)；又如，12＝6＊2＝4＊3，所以12也不是素?cái)?shù)。另一方面，13除了等于13＊1以外，不能表示為其它任何兩個(gè)整數(shù)的乘積，所以13是一個(gè)素?cái)?shù)。素?cái)?shù)也稱為“質(zhì)數(shù)”。
二、什么是“互質(zhì)數(shù)”（或“互素?cái)?shù)”）？
小學(xué)數(shù)學(xué)教材對(duì)互質(zhì)數(shù)是這樣定義的：“公約數(shù)只有1的兩個(gè)數(shù)，叫做互質(zhì)數(shù)?！边@里所說(shuō)的“兩個(gè)數(shù)”是指自然數(shù)。
判別方法主要有以下幾種（不限于此）：
（1）兩個(gè)質(zhì)數(shù)一定是互質(zhì)數(shù)。例如，2與7、13與19。
（2）一個(gè)質(zhì)數(shù)如果不能整除另一個(gè)合數(shù)，這兩個(gè)數(shù)為互質(zhì)數(shù)。例如，3與10、5與 26。
（3）1不是質(zhì)數(shù)也不是合數(shù)，它和任何一個(gè)自然數(shù)在一起都是互質(zhì)數(shù)。如1和9908。
（4）相鄰的兩個(gè)自然數(shù)是互質(zhì)數(shù)。如 15與 16。
（5）相鄰的兩個(gè)奇數(shù)是互質(zhì)數(shù)。如 49與 51。
（6）大數(shù)是質(zhì)數(shù)的兩個(gè)數(shù)是互質(zhì)數(shù)。如97與88。
（7）小數(shù)是質(zhì)數(shù)，大數(shù)不是小數(shù)的倍數(shù)的兩個(gè)數(shù)是互質(zhì)數(shù)。如 7和 16。
（8）兩個(gè)數(shù)都是合數(shù)（二數(shù)差又較大），小數(shù)所有的質(zhì)因數(shù)，都不是大數(shù)的約數(shù)，這兩個(gè)數(shù)是互質(zhì)數(shù)。如357與715，357=3×7×17，而3、7和17都不是715的約數(shù)，這兩個(gè)數(shù)為互質(zhì)數(shù)。等等。
三、什么是模指數(shù)運(yùn)算？
指數(shù)運(yùn)算誰(shuí)都懂，不必說(shuō)了，先說(shuō)說(shuō)模運(yùn)算。模運(yùn)算是整數(shù)運(yùn)算，有一個(gè)整數(shù)m，以n為模做模運(yùn)算，即m mod n。怎樣做呢？讓m去被n整除，只取所得的余數(shù)作為結(jié)果，就叫做模運(yùn)算。例如，10 mod 3=1；26 mod 6=2；28 mod 2 =0等等。
模指數(shù)運(yùn)算就是先做指數(shù)運(yùn)算，取其結(jié)果再做模運(yùn)算。如 $5^3 mod \ 7 = 125 \ mod \ 7 = 6 $
好，現(xiàn)在開(kāi)始正式講解RSA加密算法。
算法描述：
（1）選擇一對(duì)不同的、足夠大的素?cái)?shù)p，q。
（2）計(jì)算n=pq。
（3）計(jì)算 f(n) = (p-1)(q-1)，同時(shí)對(duì)p, q嚴(yán)加保密，不讓任何人知道。
（4）找一個(gè)與 f(n) 互質(zhì)的數(shù) e，且1 < e < f(n)。
（5）計(jì)算d，使得 d*e ≡ 1 mod f(n)。這個(gè)公式也可以表達(dá)為d ≡ e-1 mod f(n)
這里要解釋一下，≡是數(shù)論中表示同余的符號(hào)。公式中，≡符號(hào)的左邊必須和符號(hào)右邊同余，也就是兩邊模運(yùn)算結(jié)果相同。顯而易見(jiàn)，不管f(n)取什么值，符號(hào)右邊1 mod f(n)的結(jié)果都等于1；符號(hào)的左邊d與e的乘積做模運(yùn)算后的結(jié)果也必須等于1。這就需要計(jì)算出d的值，讓這個(gè)同余等式能夠成立。
（6）公鑰KU=(e,n)，私鑰KR=(d,n)。
（7）加密時(shí)，先將明文變換成0至n-1的一個(gè)整數(shù)M。若明文較長(zhǎng)，可先分割成適當(dāng)?shù)慕M，然后再進(jìn)行交換。設(shè)密文為C，則加密過(guò)程為：$ C ≡ M^e (mod \ n)$。
（8）解密過(guò)程為：$M ≡ C^d (mod \ n)$。
實(shí)例描述
我們可以通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)理解RSA的工作原理。為了便于計(jì)算。在以下實(shí)例中只選取小數(shù)值的素?cái)?shù)p,q,以及e，假設(shè)用戶A需要將明文“key”通過(guò)RSA加密后傳遞給用戶B，過(guò)程如下：
（1）設(shè)計(jì)公私密鑰(e,n)和(d,n)。
令p=3，q=11，得出n=pq= 311 = 33；f(n) = (p-1)(q-1) = 2×10 =20；取e=3，（3與20互質(zhì)）則ed ≡ 1 mod f(n)，即3d ≡ 1 mod 20。
d怎樣取值呢？可以用試算的辦法來(lái)尋找。(d的取值使 3*d mod 20 = 1)試算結(jié)果見(jiàn)下表：
| d | ed = 3d | (ed) mod (p-1)(q-1) = (3d) mod 20 |
|---|---|---|
| 1 | 3 | 3 |
| 2 | 6 | 6 |
| 3 | 9 | 9 |
| 4 | 12 | 12 |
| 5 | 15 | 15 |
| 6 | 18 | 18 |
| 7 | 21 | 1 |
| 8 | 24 | 3 |
通過(guò)試算我們找到，當(dāng)d=7時(shí)，e×d≡1 mod f(n)同余等式成立。因此，可令d=7。從而我們可以設(shè)計(jì)出一對(duì)公私密鑰，加密密鑰（公鑰）為：KU =(e,n)=(3,33)，解密密鑰（私鑰）為：KR =(d,n)=(7,33)。
（2）英文數(shù)字化。
將明文信息數(shù)字化，并將每塊兩個(gè)數(shù)字分組。假定明文英文字母編碼表為按字母順序排列數(shù)值，即：
（3）明文加密
用戶加密密鑰(3,33) 將數(shù)字化明文分組信息加密成密文。由C≡Me(mod n)得：
11^3 mod 33 = 11;
5^3 mod 33 = 26;
25^3 mod 33 = 16;
因此，得到相應(yīng)的密文信息為：11，26，16。
例如:用RSA算法加密時(shí),已知公鑰是（e=7,n=20）,私鑰是（d=3,n=20）用公鑰對(duì)消息M=3加密,則加密解密計(jì)算:
要加密或解密的數(shù)字做e次方或d次方,得到的數(shù)字再和n進(jìn)行模運(yùn)算,模運(yùn)算就是求余數(shù),拿題目中數(shù)據(jù)來(lái)算的話就是
3的7次方等于2187,2187除以20等于109,余數(shù)是7，所以得到的密文就是7。
解密就是算7的3次方343,343除以20等于340余數(shù)3,于是我們又得回原來(lái)的明文3了
（4）密文解密。
用戶B收到密文，若將其解密，只需要計(jì)算 $M ≡ C^d (mod \ n)$，即：
11^7 mod 33 = 11;
26^7 mod 33 = 5;
16^7 mod 33 = 25;
用戶B得到明文信息為：11，05，25。根據(jù)上面的編碼表將其轉(zhuǎn)換為英文，我們又得到了恢復(fù)后的原文“key”。
當(dāng)然，實(shí)際運(yùn)用要比這復(fù)雜得多，由于RSA算法的公鑰私鑰的長(zhǎng)度（模長(zhǎng)度）要到1024位甚至2048位才能保證安全，因此，p、q、e的選取、公鑰私鑰的生成，加密解密模指數(shù)運(yùn)算都有一定的計(jì)算程序，需要仰仗計(jì)算機(jī)高速完成。
最后簡(jiǎn)單談?wù)凴SA的安全性
首先，我們來(lái)探討為什么RSA密碼難于破解?
當(dāng)p和q是一個(gè)大素?cái)?shù)的時(shí)候，從它們的積pq去分解因子p和q，這是一個(gè)公認(rèn)的數(shù)學(xué)難題。比如當(dāng)pq大到1024位時(shí)，迄今為止還沒(méi)有人能夠利用任何計(jì)算工具去完成分解因子的任務(wù)。因此，RSA從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。
然而，雖然RSA的安全性依賴于大數(shù)的因子分解，但并沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)。即RSA的重大缺陷是無(wú)法從理論上把握它的保密性能如何。
此外，RSA的缺點(diǎn)還有：A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長(zhǎng)度太大，為保證安全性，n 至少也要 600 bits 以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí)；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長(zhǎng)度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。因此，使用RSA只能加密少量數(shù)據(jù)，大量的數(shù)據(jù)加密還要靠對(duì)稱密碼算法。
