RSA加密算法是最常用的非對稱加密算法疯坤，它既能用于加密，也能用于數(shù)字簽名伤塌。RSA以它的三個發(fā)明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名领猾，這個算法經(jīng)受住了多年深入的密碼分析蕉鸳，雖然密碼分析者既不能證明也不能否定RSA的安全性，但這恰恰說明該算法有一定的可信性尉剩，目前它已經(jīng)成為最流行的公開密鑰算法真慢。
RSA的安全基于大數(shù)分解的難度。其公鑰和私鑰是一對大素?cái)?shù)（100到200位十進(jìn)制數(shù)或更大）的函數(shù)理茎。從一個公鑰和密文恢復(fù)出明文的難度晤碘，等價于分解兩個大素?cái)?shù)之積（這是公認(rèn)的數(shù)學(xué)難題）。
讓我們先復(fù)習(xí)一下數(shù)學(xué)上的幾個基本概念式撼，它們在后面的介紹中要用到：
一童社、 什么是“素?cái)?shù)”？ 素?cái)?shù)是這樣的整數(shù)著隆，它除了能表示為它自己和1的乘積以外扰楼，不能表示為任何其它兩個整數(shù)的乘積。例如美浦，15＝3＊5弦赖，所以15不是素?cái)?shù)；又如浦辨，12＝6＊2＝4＊3蹬竖，所以12也不是素?cái)?shù)。另一方面，13除了等于13＊1以外币厕，不能表示為其它任何兩個整數(shù)的乘積列另，所以13是一個素?cái)?shù)。素?cái)?shù)也稱為“質(zhì)數(shù)”旦装。
二页衙、什么是“互質(zhì)數(shù)”（或“互素?cái)?shù)”）？ 小學(xué)數(shù)學(xué)教材對互質(zhì)數(shù)是這樣定義的：“公約數(shù)只有1的兩個數(shù)阴绢，叫做互質(zhì)數(shù)店乐。”這里所說的“兩個數(shù)”是指自然數(shù)呻袭。
判別方法主要有以下幾種（不限于此）：
（1）兩個質(zhì)數(shù)一定是互質(zhì)數(shù)响巢。例如，2與7、13與19。
（2）一個質(zhì)數(shù)如果不能整除另一個合數(shù)尿招，這兩個數(shù)為互質(zhì)數(shù)。例如伏穆，3與10、5與 26纷纫。
（3）1不是質(zhì)數(shù)也不是合數(shù)枕扫，它和任何一個自然數(shù)在一起都是互質(zhì)數(shù)。如1和9908辱魁。
（4）相鄰的兩個自然數(shù)是互質(zhì)數(shù)烟瞧。如 15與 16。
（5）相鄰的兩個奇數(shù)是互質(zhì)數(shù)染簇。如 49與 51参滴。
（6）大數(shù)是質(zhì)數(shù)的兩個數(shù)是互質(zhì)數(shù)。如97與88锻弓。
（7）小數(shù)是質(zhì)數(shù)砾赔，大數(shù)不是小數(shù)的倍數(shù)的兩個數(shù)是互質(zhì)數(shù)。如 7和 16青灼。
（8）兩個數(shù)都是合數(shù)（二數(shù)差又較大）暴心，小數(shù)所有的質(zhì)因數(shù)，都不是大數(shù)的約數(shù)杂拨，這兩個數(shù)是互質(zhì)數(shù)专普。如357與715，357=3×7×17弹沽，而3檀夹、7和17都不是715的約數(shù)筋粗，這兩個數(shù)為互質(zhì)數(shù)。等等击胜。
三亏狰、什么是模指數(shù)運(yùn)算役纹？
指數(shù)運(yùn)算誰都懂偶摔，不必說了，先說說模運(yùn)算促脉。模運(yùn)算是整數(shù)運(yùn)算辰斋，有一個整數(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)算。如
好炫加，現(xiàn)在開始正式講解RSA加密算法瑰煎。
算法描述：
（1）選擇一對不同的、足夠大的素?cái)?shù)p俗孝，q酒甸。
（2）計(jì)算n=pq。
（3）計(jì)算f(n)=(p-1)(q-1)赋铝，同時對p, q嚴(yán)加保密烘挫，不讓任何人知道。
（4）找一個與f(n)互質(zhì)的數(shù)e柬甥，且1<e<f(n)饮六。
（5）計(jì)算d，使得de≡1 mod f(n)苛蒲。這個公式也可以表達(dá)為d ≡e-1 mod f(n)
這里要解釋一下卤橄，≡是數(shù)論中表示同余的符號。公式中臂外，≡符號的左邊必須和符號右邊同余窟扑，也就是兩邊模運(yùn)算結(jié)果相同喇颁。顯而易見，不管f(n)取什么值嚎货，符號右邊1 mod f(n)的結(jié)果都等于1橘霎；符號的左邊d與e的乘積做模運(yùn)算后的結(jié)果也必須等于1。這就需要計(jì)算出d的值殖属，讓這個同余等式能夠成立姐叁。
（6）公鑰KU=(e,n)，私鑰KR=(d,n)洗显。
（7）加密時外潜，先將明文變換成0至n-1的一個整數(shù)M。若明文較長挠唆，可先分割成適當(dāng)?shù)慕M处窥，然后再進(jìn)行交換。設(shè)密文為C玄组，則加密過程為：
實(shí)例描述： 在這篇科普小文章里滔驾，不可能對RSA算法的正確性作嚴(yán)格的數(shù)學(xué)證明，但我們可以通過一個簡單的例子來理解RSA的工作原理俄讹。為了便于計(jì)算哆致。在以下實(shí)例中只選取小數(shù)值的素?cái)?shù)p,q,以及e，假設(shè)用戶A需要將明文“key”通過RSA加密后傳遞給用戶B颅悉，過程如下：
（1）設(shè)計(jì)公私密鑰(e,n)和(d,n)沽瞭。
令p=3，q=11剩瓶，得出n=p×q=3×11=33驹溃；f(n)=(p-1)(q-1)=2×10=20；取e=3延曙，（3與20互質(zhì)）則e×d≡1 mod f(n)豌鹤，即3×d≡1 mod 20。
d怎樣取值呢枝缔？可以用試算的辦法來尋找布疙。試算結(jié)果見下表：
通過試算我們找到，當(dāng)d=7時愿卸，e×d≡1 mod f(n)同余等式成立灵临。因此，可令d=7趴荸。從而我們可以設(shè)計(jì)出一對公私密鑰儒溉，加密密鑰（公鑰）為：KU =(e,n)=(3,33)，解密密鑰（私鑰）為：KR =(d,n)=(7,33)发钝。
（2）英文數(shù)字化顿涣。 將明文信息數(shù)字化波闹，并將每塊兩個數(shù)字分組。假定明文英文字母編碼表為按字母順序排列數(shù)值涛碑，即：
則得到分組后的key的明文信息為：11精堕，05，25蒲障。
（3）明文加密
用戶加密密鑰(3,33) 將數(shù)字化明文分組信息加密成密文歹篓。由C≡Me(mod n)得：
因此，得到相應(yīng)的密文信息為：11晌涕，31滋捶，16痛悯。
（4）密文解密余黎。
用戶B收到密文，若將其解密载萌，只需要計(jì)算
惧财，即：
用戶B得到明文信息為：11，05扭仁，25垮衷。根據(jù)上面的編碼表將其轉(zhuǎn)換為英文，我們又得到了恢復(fù)后的原文“key”乖坠。
你看搀突，它的原理就可以這么簡單地解釋！
當(dāng)然熊泵，實(shí)際運(yùn)用要比這復(fù)雜得多仰迁，由于RSA算法的公鑰私鑰的長度（模長度）要到1024位甚至2048位才能保證安全，因此顽分，p徐许、q、e的選取卒蘸、公鑰私鑰的生成雌隅，加密解密模指數(shù)運(yùn)算都有一定的計(jì)算程序，需要仰仗計(jì)算機(jī)高速完成缸沃。
最后簡單談?wù)凴SA的安全性
首先恰起，我們來探討為什么RSA密碼難于破解？
在RSA密碼應(yīng)用中趾牧，公鑰KU是被公開的检盼，即e和n的數(shù)值可以被第三方竊聽者得到。破解RSA密碼的問題就是從已知的e和n的數(shù)值（n等于pq）武氓，想法求出d的數(shù)值梯皿，這樣就可以得到私鑰來破解密文仇箱。從上文中的公式：d ≡e-1 (mod((p-1)(q-1)))或de≡1 (mod((p-1)(q-1))) 我們可以看出。密碼破解的實(shí)質(zhì)問題是：從Pq的數(shù)值东羹，去求出(p-1)和(q-1)剂桥。換句話說，只要求出p和q的值属提，我們就能求出d的值而得到私鑰权逗。
當(dāng)p和q是一個大素?cái)?shù)的時候，從它們的積pq去分解因子p和q冤议，這是一個公認(rèn)的數(shù)學(xué)難題斟薇。比如當(dāng)pq大到1024位時，迄今為止還沒有人能夠利用任何計(jì)算工具去完成分解因子的任務(wù)恕酸。因此堪滨，RSA從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗(yàn)蕊温，逐漸為人們接受袱箱，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。
然而义矛，雖然RSA的安全性依賴于大數(shù)的因子分解发笔，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何凉翻。
此外了讨，RSA的缺點(diǎn)還有：A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制制轰，因而難以做到一次一密前计。B)分組長度太大，為保證安全性艇挨，n 至少也要 600 bits 以上残炮，使運(yùn)算代價很高，尤其是速度較慢缩滨，較對稱密碼算法慢幾個數(shù)量級势就；且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加脉漏，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化苞冯。因此，使用RSA只能加密少量數(shù)據(jù)侧巨，大量的數(shù)據(jù)加密還要靠對稱密碼算法舅锄。
用公鑰加密時，私鑰可以解密司忱。反之亦然皇忿，私鑰加密后的信息用公鑰可以解密畴蹭。
Linux 下通過 OpenSSL 生成 RSA 公鑰和私鑰
需要提前在 Linux 上安裝 OpenSSL，默認(rèn)生成在當(dāng)前用戶家目錄下：
[root@VM_120_242_centos ~]# openssl
OpenSSL> genrsa -out app_private_key.pem 1024 # 生成私鑰
Generating RSA private key, 1024 bit long modulus
.++++++
........++++++
e is 65537 (0x10001)
OpenSSL> rsa -in app_private_key.pem -pubout -out app_public_key.pem # 生成公鑰
writing RSA key
OpenSSL> exit
對于 PHP 可以直接使用上面生成的原始私鑰鳍烁。但是 Java 需要將私鑰轉(zhuǎn)換成 PKCS8 格式叨襟，然后將生成的 PKCS8 格式的私鑰去除頭尾、換行和空格幔荒，作為私鑰字符串填入代碼中：
OpenSSL> pkcs8 -topk8 -inform PEM -in app_private_key.pem -outform PEM -nocrypt -out app_private_key_pkcs8.pem # 私鑰轉(zhuǎn)成 PKCS8 格式
查看生成的文件：
[root@VM_120_242_centos ~]# ll
總用量 1064
-rw-r--r-- 1 root root 887 6月 14 11:25 app_private_key.pem
-rw-r--r-- 1 root root 272 6月 14 11:25 app_public_key.pem
查看公鑰：
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC3//sR2tXw0wrC2DySx8vNGlqt
3Y7ldU9+LBLI6e1KS5lfc5jlTGF7KBTSkCHBM3ouEHWqp1ZJ85iJe59aF5gIB2kl
Bd6h4wrbbHA2XE1sq21ykja/Gqx7/IRia3zQfxGv/qEkyGOx+XALVoOlZqDwh76o
2n1vP1D+tD3amHsK7QIDAQAB
-----END PUBLIC KEY-----
轉(zhuǎn)成 PKCS8 格式的公鑰字符串為：
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC3//sR2tXw0wrC2DySx8vNGlqt3Y7ldU9+LBLI6e1KS5lfc5jlTGF7KBTSkCHBM3ouEHWqp1ZJ85iJe59aF5gIB2klBd6h4wrbbHA2XE1sq21ykja/Gqx7/IRia3zQfxGv/qEkyGOx+XALVoOlZqDwh76o2n1vP1D+tD3amHsK7QIDAQAB
查看私鑰：
-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQC3//sR2tXw0wrC2DySx8vNGlqt3Y7ldU9+LBLI6e1KS5lfc5jl
TGF7KBTSkCHBM3ouEHWqp1ZJ85iJe59aF5gIB2klBd6h4wrbbHA2XE1sq21ykja/
Gqx7/IRia3zQfxGv/qEkyGOx+XALVoOlZqDwh76o2n1vP1D+tD3amHsK7QIDAQAB
AoGBAKH14bMitESqD4PYwODWmy7rrrvyFPEnJJTECLjvKB7IkrVxVDkp1XiJnGKH
2h5syHQ5qslPSGYJ1M/XkDnGINwaLVHVD3BoKKgKg1bZn7ao5pXT+herqxaVwWs6
ga63yVSIC8jcODxiuvxJnUMQRLaqoF6aUb/2VWc2T5MDmxLhAkEA3pwGpvXgLiWL
3h7QLYZLrLrbFRuRN4CYl4UYaAKokkAvZly04Glle8ycgOc2DzL4eiL4l/+x/gaq
deJU/cHLRQJBANOZY0mEoVkwhU4bScSdnfM6usQowYBEwHYYh/OTv1a3SqcCE1f+
qbAclCqeNiHajCcDmgYJ53LfIgyv0wCS54kCQAXaPkaHclRkQlAdqUV5IWYyJ25f
oiq+Y8SgCCs73qixrU1YpJy9yKA/meG9smsl4Oh9IOIGI+zUygh9YdSmEq0CQQC2
4G3IP2G3lNDRdZIm5NZ7PfnmyRabxk/UgVUWdk47IwTZHFkdhxKfC8QepUhBsAHL
QjifGXY4eJKUBm3FpDGJAkAFwUxYssiJjvrHwnHFbg0rFkvvY63OSmnRxiL4X6EY
yI9lblCsyfpl25l7l5zmJrAHn45zAiOoBrWqpM5edu7c
-----END RSA PRIVATE KEY-----
參考：
1. RSA - 原理糊闽、特點(diǎn)（加解密及簽名驗(yàn)簽）及公鑰和私鑰的生成
2. 用實(shí)例給新手講解RSA加密算法
