密碼學(xué)是在編碼與破譯的斗爭實(shí)踐中逐步發(fā)展起來的,并隨著先進(jìn)科學(xué)技術(shù)的應(yīng)用，已成為一門綜合性的尖端技術(shù)科學(xué)。
密碼學(xué)發(fā)展史
在說RSA加密算法之前， 先說下密碼學(xué)的發(fā)展史晰房。其實(shí)密碼學(xué)的誕生，就是為了運(yùn)用在戰(zhàn)場射沟，在公元前殊者，戰(zhàn)爭之中出現(xiàn)了秘密書信。在中國歷史上最早的加密算法的記載出自于周朝兵書《六韜.龍韜》中的《陰符》和《陰書》验夯。在遙遠(yuǎn)的西方猖吴，在希羅多德（Herodotus）的《歷史》中記載了公元前五世紀(jì)，希臘城邦和波斯帝國的戰(zhàn)爭中挥转，廣泛使用了移位法進(jìn)行加密處理戰(zhàn)爭通訊信息距误。
相傳凱撒大帝為了防止敵人竊取信息簸搞，就使用加密的方式傳遞信息。那么當(dāng)時(shí)的加密方式非常的簡單准潭，就是對(duì)二十幾個(gè)羅馬字母建立一張對(duì)照表趁俊，將明文對(duì)應(yīng)成為密文。那么這種方式其實(shí)持續(xù)了很久刑然。甚至在二戰(zhàn)時(shí)期寺擂，日本的電報(bào)加密就是采用的這種原始加密方式。
早期的密碼學(xué)一直沒有什么改進(jìn)泼掠，幾乎都是根據(jù)經(jīng)驗(yàn)慢慢發(fā)展的怔软。直到20世紀(jì)中葉，由香農(nóng)發(fā)表的《秘密體制的通信理論》一文择镇，標(biāo)志著加密算法的重心轉(zhuǎn)移往應(yīng)用數(shù)學(xué)上的轉(zhuǎn)移挡逼。于是，逐漸衍生出了當(dāng)今重要的三類加密算法：非對(duì)稱加密腻豌、對(duì)稱加密以及哈希算法（HASH嚴(yán)格說不是加密算法家坎，但由于其不可逆性，已成為加密算法中的一個(gè)重要構(gòu)成部分）吝梅。
1976年以前虱疏，所有的加密方法都是同一種模式：加密和解密使用同樣規(guī)則（簡稱"密鑰"），這被稱為"對(duì)稱加密算法"苏携，使用相同的密鑰做瞪，兩次連續(xù)的對(duì)等加密運(yùn)算后會(huì)恢復(fù)原始文字，也有很大的安全隱患右冻。
1976年装蓬，兩位美國計(jì)算機(jī)學(xué)家Whitfield Diffie 和 Martin Hellman，提出了一種嶄新構(gòu)思纱扭，可以在不直接傳遞密鑰的情況下矛物，完成解密。這被稱為"Diffie-Hellman密鑰交換算法"跪但。也正是因?yàn)檫@個(gè)算法的產(chǎn)生，人類終于可以實(shí)現(xiàn)非對(duì)稱加密了：A給B發(fā)送信息
- B要先生成兩把密鑰（公鑰和私鑰）峦萎。公鑰是公開的屡久，任何人都可以獲得，私鑰則是保密的爱榔。
- A獲取B的公鑰被环，然后用它對(duì)信息加密。
- B得到加密后的信息详幽，用私鑰解密筛欢。
理論上如果公鑰加密的信息只有私鑰解得開浸锨，那么只要私鑰不泄漏，通信就是安全的版姑。
1977年柱搜，三位數(shù)學(xué)家Rivest、Shamir 和 Adleman 設(shè)計(jì)了一種算法剥险，可以實(shí)現(xiàn)非對(duì)稱加密聪蘸。這種算法用他們?nèi)齻€(gè)人的名字命名，叫做RSA算法表制。從那時(shí)直到現(xiàn)在健爬，RSA算法一直是最廣為使用的"非對(duì)稱加密算法"。毫不夸張地說么介，只要有計(jì)算機(jī)網(wǎng)絡(luò)的地方娜遵，就有RSA算法。這種算法非橙蓝蹋可靠设拟，密鑰越長，它就越難破解鸽扁。根據(jù)已經(jīng)披露的文獻(xiàn)蒜绽，目前被破解的最長RSA密鑰是232個(gè)十進(jìn)制位，也就是768個(gè)二進(jìn)制位桶现，因此可以認(rèn)為躲雅，1024位的RSA密鑰基本安全，2048位的密鑰極其安全骡和，當(dāng)然量子計(jì)算機(jī)除外相赁。
RSA算法的原理
下面進(jìn)入正題，解釋RSA算法的原理慰于，其實(shí)RSA算法并不難钮科，只需要一點(diǎn)數(shù)論知識(shí)就可以理解。
- 素?cái)?shù)：又稱質(zhì)數(shù)婆赠，指在一個(gè)大于1的自然數(shù)中绵脯，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)休里。
- 互質(zhì)蛆挫，又稱互素。若N個(gè)整數(shù)的最大公因子是1妙黍，則稱這N個(gè)整數(shù)互質(zhì)悴侵。
- 模運(yùn)算即求余運(yùn)算∈眉蓿“目擅猓”是“Mod”的音譯抓于。和模運(yùn)算緊密相關(guān)的一個(gè)概念是“同余”。數(shù)學(xué)上浇借，當(dāng)兩個(gè)整數(shù)除以同一個(gè)正整數(shù)捉撮，若得相同余數(shù)烁兰，則二整數(shù)同余谁尸。
歐拉函數(shù)
任意給定正整數(shù)n荞下，請(qǐng)問在小于等于n的正整數(shù)之中境蔼，有多少個(gè)與n構(gòu)成互質(zhì)關(guān)系物咳？（比如抡句，在1到8之中牡肉，有多少個(gè)數(shù)與8構(gòu)成互質(zhì)關(guān)系巢掺？）計(jì)算這個(gè)值的方法就叫做歐拉函數(shù)睬愤，以φ(n)表示片仿。
- 計(jì)算8的歐拉函數(shù)，和8互質(zhì)的 1尤辱、2砂豌、3、4光督、5阳距、6、7结借、8
φ(8) = 4
如果n是質(zhì)數(shù)的某一個(gè)次方筐摘，即 n = p^k (p為質(zhì)數(shù)，k為大于等于1的整數(shù))船老，則φ(n) = φ(p^k) = p^k - p^(k-1)咖熟。也就是φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4 - 計(jì)算7的歐拉函數(shù)，和7互質(zhì)的 1柳畔、2馍管、3、4薪韩、5确沸、6、7
φ(7) = 6
如果n是質(zhì)數(shù)俘陷，則 φ(n)=n-1 罗捎。因?yàn)橘|(zhì)數(shù)與小于它的每一個(gè)數(shù)，都構(gòu)成互質(zhì)關(guān)系岭洲。比如5與1、2坎匿、3盾剩、4都構(gòu)成互質(zhì)關(guān)系雷激。 - 計(jì)算56的歐拉函數(shù)
φ(56) = φ(8) * φ(7) = 4 * 6 = 24
如果n可以分解成兩個(gè)互質(zhì)的整數(shù)之積，即 n = p * k 告私，則φ(n) = φ(p * k) = φ(p1)*φ(p2)
歐拉定理：如果兩個(gè)正整數(shù)m和n互質(zhì)屎暇，那么m的φ(n)次方減去1，可以被n整除驻粟。
歐拉定理.png
費(fèi)馬小定理：歐拉定理的特殊情況根悼，如果兩個(gè)正整數(shù)m和n互質(zhì)，而且n為質(zhì)數(shù)蜀撑！那么φ(n)結(jié)果就是n-1挤巡。
費(fèi)馬小定理.png
模反元素
還剩下最后一個(gè)概念，模反元素：如果兩個(gè)正整數(shù)e和x互質(zhì)酷麦，那么一定可以找到整數(shù)d矿卑，使得 ed-1 被x整除，或者說ed被x除的余數(shù)是1沃饶。
那么d就是e相對(duì)于x的模反元素母廷。
等式轉(zhuǎn)換
-
根據(jù)歐拉定理
等式轉(zhuǎn)換1 -
由于1^k ≡ 1，等號(hào)左右兩邊都來個(gè)k次方
等式轉(zhuǎn)換 -
由于1* m ≡ m糊肤，等號(hào)左右兩邊都乘上m
等式轉(zhuǎn)換3.png
根據(jù)模反元素琴昆，因?yàn)閑*d 一定是x的倍數(shù)加1。所以如下：
通過多次的等式轉(zhuǎn)換馆揉。終于可以將這兩個(gè)等式進(jìn)行合并了业舍！如下：
這個(gè)等式成立有一個(gè)前提！就是關(guān)于模反元素的把介，就是當(dāng)整數(shù)e和φ(n)互質(zhì)勤讽！一定有一個(gè)整數(shù)d是e相對(duì)于φ(n)的模反元素。
我們可以測試一下拗踢。
m取值為4
n取值為15
φ(n)取值為8
e 如果取值為3
d 可以為 11脚牍、19...(模反元素很明顯不止一個(gè)，其實(shí)就是解二元一次方程)
如果你測試了巢墅，那么你可以改變m的值試一下诸狭，其實(shí)這個(gè)等式不需要m和n 互質(zhì)。只要m小于n 等式依然成立君纫。
這里需要注意的是驯遇，我們可以看做 m 通過一系列運(yùn)算得到結(jié)果仍然是 m。這一系列運(yùn)算中蓄髓，分別出現(xiàn)了多個(gè)參數(shù)n叉庐、φ(n)、e還有d会喝。
m 的 e乘上d 次方為加密運(yùn)算陡叠，得到結(jié)果 c
c 模以 n 為解密運(yùn)算玩郊，得到結(jié)果 m
這似乎可以用于加密和解密。但這樣枉阵，加密的結(jié)果會(huì)非常大译红。明文數(shù)據(jù)將非常小（雖然RSA用于加密的數(shù)據(jù)也很小兴溜，但是沒這么大懸殊）侦厚，真正的RSA要更加強(qiáng)大，那么RSA是怎么演變來的呢拙徽？刨沦？
早期很多數(shù)學(xué)家也停留在了這一步！直到1967年迪菲赫爾曼密鑰交換打破了僵局斋攀！
迪菲赫爾曼密鑰交換
這個(gè)密鑰交換當(dāng)時(shí)轟動(dòng)了整個(gè)數(shù)學(xué)界已卷！而且對(duì)人類密碼學(xué)的發(fā)展非常重要，因?yàn)檫@個(gè)偉大的算法能夠拆分剛才的等式淳蔼。當(dāng)非對(duì)稱加密算法沒有出現(xiàn)以前侧蘸，人類都是用的對(duì)稱加密。所以密鑰的傳遞鹉梨，就必須要非常小心讳癌。
迪菲赫爾曼密鑰交換 就是解決了密鑰傳遞的保密性，我們來看一下
假設(shè)一個(gè)傳遞密鑰的場景存皂。算法就是用3 的次方去模以17晌坤。 三個(gè)角色
- 服務(wù)器 隨機(jī)數(shù) 15
這個(gè)15只有服務(wù)器才知道。通過算法得到結(jié)果 6 因?yàn)?3的15次方 mod 17 = 6 旦袋。然后將結(jié)果 6 公開發(fā)送出去骤菠，拿到客戶端的 12 ，然后用12^15 mod 17 得到結(jié)果10(10就是交換得到的密鑰) - 客戶端 隨機(jī)數(shù)13
客戶端用3 的 13次方 mod 17 = 12 然后將得到的結(jié)果12公布出去疤孕。
拿到服務(wù)器的 6 商乎，然后用6^13 mod 17 得到結(jié)果10(10就是交換得到的密鑰) - 第三者
第三者只能拿到6 和 12 ，因?yàn)闆]有私密數(shù)據(jù)13祭阀、15鹉戚，所以它沒法得到結(jié)果10。
為什么 6的13次方會(huì)和12的15次方得到一樣的結(jié)果呢?因?yàn)檫@就是規(guī)律专控，我們可以用小一點(diǎn)的數(shù)字測試一下3^3 mod 17 = 10和10 ^ 2 mod 17 抹凳； 3 ^ 2 mod 17 = 9和9^3 mod 17結(jié)果都是15。迪菲赫爾曼密鑰交換最核心的地方就在于這個(gè)規(guī)律
RSA的誕生
現(xiàn)在我們知道了m^e % n = c是加密伦腐，c^d % n = m是解密赢底，m就是原始數(shù)據(jù)，c是密文，公鑰是n和e幸冻，私鑰是n和d嗅剖，所以只有n和e是公開的。加密時(shí)我們也要知道φ(n)的值嘁扼，最簡單的方式是用兩個(gè)質(zhì)數(shù)之積得到，別人想破解RSA也要知道φ(n)的值黔攒，只能對(duì)n進(jìn)行因數(shù)分解趁啸，那么我們不想m被破解，n的值就要非常大督惰，就是我們之前說的不傅，長度一般為1024個(gè)二進(jìn)制位，這樣就很安全了赏胚。但是據(jù)說量子計(jì)算機(jī)(用于科研访娶，尚未普及)可以破解，理論上量子計(jì)算機(jī)的運(yùn)行速度無窮快觉阅，大家可以了解一下崖疤。
以上就是RSA的數(shù)學(xué)原理
檢驗(yàn)RSA加密算法
我們用終端命令演示下這個(gè)加密、解密過程典勇。
假設(shè)m = 12(隨便取值劫哼，只要比n小就OK)，n = 15(還是隨機(jī)取一個(gè)值)割笙，φ(n) = 8权烧，e = 3(只要和φ(n)互質(zhì)就可以)，d = 19（3d - 1 = 8伤溉，d也可以為3,11等等般码，也就是d = (8k + 1)/3 ）
終端分別以m=12，7輸入結(jié)果
OpenSSL進(jìn)行RSA的命令運(yùn)行
Mac可以直接使用OpenSSL乱顾，首先進(jìn)入相應(yīng)文件夾
- 生成公私鑰
// 生成RSA私鑰板祝，文件名為private.pem，長度為1024bit
openssl genrsa -out private.pem 1024
// 從私鑰中提取公鑰
openssl rsa -in private.pem -pubout -out publick.pem
// 查看剛剛生成好的私鑰
cat private.pem
// 查看剛剛生成好的公鑰
cat publick.pem
我們可以看到base64編碼糯耍，明顯私鑰二進(jìn)制很大扔字，公鑰就小了很多。
這時(shí)候我們的文件夾內(nèi)已經(jīng)多了剛剛生成好的公私鑰文件了
// 將私鑰轉(zhuǎn)換為明文
openssl rsa -in private.pem -text -out private.txt
里面就是P1温技、P2還有KEY等信息革为。
- 對(duì)文件進(jìn)行加密、解密
// 編輯文件message內(nèi)容為hello Vincent!!!
// 剛剛的public.pem寫成了publick.pem(哎舵鳞。震檩。。)
$ vi message.txt
$ cat message.txt
hello Vincent!!!
// 通過公鑰加密數(shù)據(jù)時(shí)，使用encrypt對(duì)文件進(jìn)行加密
$ openssl rsautl -encrypt -in message.txt -inkey publick.pem -pubin -out enc.txt
// 此時(shí)查看該文件內(nèi)容為亂碼
$ cat enc.txt
j??E]?a??d?kUE?&<
??I*??V/??pL[???ˋ?O?+?-?M??K???&??O??2???o34?:?$???6??C?L??,b?'M?S?k?0???A??3%?[I???1?????ps"%
// 通過私鑰解密數(shù)據(jù)
$ openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
// 已成功解密抛虏，正確顯示文件內(nèi)容
$ cat dec.txt
hello Vincent!!!
// 通過私鑰加密數(shù)據(jù)時(shí)博其，要使用sign對(duì)文件進(jìn)行重簽名
$ openssl rsautl -sign -in message.txt -inkey private.pem -out enc.bin
// 此時(shí)查看該文件內(nèi)容同樣為亂碼
$ cat enc.bin
{???Ew?3?1E??,8-OA2?Is?:???:??@MU?????
?i1B???#??6????m?D(?t#/??? ??????????>(?>?^@?C??3??MQт?O%
// 通過公鑰解密數(shù)據(jù)
$ openssl rsautl -verify -in enc.bin -inkey publick.pem -pubin -out dec.bin
// 已成功解密，正確顯示文件內(nèi)容
$ cat dec.bin
hello Vincent!!!
RSA用途及特點(diǎn)
到這里迂猴，大家都知道RSA相對(duì)比較安全慕淡，但是通過數(shù)學(xué)算法來加密和解密，效率比較低沸毁，所以一般RSA的主戰(zhàn)場是加密比較小的數(shù)據(jù)峰髓，比如對(duì)大數(shù)據(jù)進(jìn)行對(duì)稱加密，再用RSA給對(duì)稱加密的KEY進(jìn)行加密息尺，或者加密Hash值携兵，也就是數(shù)字簽名。
關(guān)于RSA數(shù)字簽名后面再慢慢闡述搂誉。該文章為記錄本人的學(xué)習(xí)路程徐紧，希望能夠幫助大家，也歡迎大家點(diǎn)贊留言交流Ｌ堪谩２⒓丁！http://www.reibang.com/p/ad3d1dea63af
