密碼學(xué)發(fā)展史
討論RSA原理之前，我們先了解一下密碼學(xué)的發(fā)展史。因?yàn)镽SA最終形成的數(shù)學(xué)算法，也是不斷演變而來(lái)的。
歷史上最早的加密算法
- 中國(guó)
話說(shuō)歷史上最早的加密算法的記載出自于周朝兵書(shū)《六韜.龍韜》中的《陰符》和《陰書(shū)》。其原理是使用文字拆分和符號(hào)代替等方式來(lái)加密數(shù)據(jù)。其實(shí)密碼學(xué)的誕生，就是為了運(yùn)用在戰(zhàn)場(chǎng)。 - 西方
無(wú)獨(dú)有偶，在遙遠(yuǎn)的西方加密算法也大規(guī)模使用于戰(zhàn)爭(zhēng)之中。在希羅多德（Herodotus）的《歷史》中記載了公元前五世紀(jì)，希臘城邦和波斯帝國(guó)的戰(zhàn)爭(zhēng)中，廣泛使用了移位法進(jìn)行加密處理戰(zhàn)爭(zhēng)通訊信息。
凱撒密碼
由古代密碼演變而來(lái)的凱撒密碼。相傳凱撒大帝為了防止敵人竊取信息，就使用加密的方式傳遞信息。那么當(dāng)時(shí)的加密方式非常的簡(jiǎn)單，就是對(duì)二十幾個(gè)羅馬字母建立一張對(duì)照表，將明文對(duì)應(yīng)成為密文。那么這種方式其實(shí)持續(xù)了很久。甚至在二戰(zhàn)時(shí)期，日本的電報(bào)加密就是采用的這種原始加密方式。（更多內(nèi)容推薦大家閱讀吳軍老師《數(shù)學(xué)之美》）
早期的密碼學(xué)一直沒(méi)有什么改進(jìn)，幾乎都是根據(jù)經(jīng)驗(yàn)慢慢發(fā)展的。直到20世紀(jì)中葉，密碼學(xué)的發(fā)展進(jìn)入了”快車(chē)道“。由香農(nóng)發(fā)表的《秘密體制的通信理論》一文，標(biāo)志著加密算法的重心轉(zhuǎn)移往應(yīng)用數(shù)學(xué)上的轉(zhuǎn)移。于是，逐漸衍生出了當(dāng)今重要的三類(lèi)加密算法：非對(duì)稱(chēng)加密、對(duì)稱(chēng)加密以及哈希算法（當(dāng)然HASH嚴(yán)格說(shuō)不是加密算法，但由于其不可逆性，已成為加密算法中的一個(gè)重要構(gòu)成部分）。
1976年前
這段時(shí)間，所有的加密方式都是同一種模式：加密、解密使用同一種算法。加密和解密的規(guī)則（密鑰）必須雙方都知道。那么它的傳遞就成為了最大的隱患。這種加密方式被稱(chēng)為對(duì)稱(chēng)加密算法。
1976年
正是因?yàn)閷?duì)稱(chēng)加密算法盛行（非對(duì)稱(chēng)那個(gè)時(shí)候還沒(méi)有出現(xiàn)，但有些瘋狂的數(shù)學(xué)家已經(jīng)開(kāi)始構(gòu)思這種方案，但并未成功）。人們?yōu)榱烁玫谋Ｗo(hù)密鑰而絞盡腦汁。直到1976年，兩位美國(guó)計(jì)算機(jī)學(xué)家。迪菲（W.Diffie）、赫爾曼（ M.Hellman ） 提出了一種嶄新構(gòu)思，可以在不直接傳遞密鑰的情況下，完成密鑰交換。這被稱(chēng)為“迪菲赫爾曼密鑰交換”算法。也正是因?yàn)檫@個(gè)算法的產(chǎn)生！人類(lèi)終于可以實(shí)現(xiàn)非對(duì)稱(chēng)加密了。那么我們一起來(lái)看看這個(gè)算法的數(shù)學(xué)原理。
由歐拉函數(shù)開(kāi)始
在討論迪菲赫爾曼密鑰交換算法之前，我們先了解幾個(gè)數(shù)學(xué)知識(shí)。并做一些公式的轉(zhuǎn)換。這樣你才能更好的體會(huì)到迪菲赫爾曼密鑰交換算法它到底能發(fā)揮多么神奇的作用。
歐拉函數(shù)
什么是歐拉函數(shù)？先思考下面的問(wèn)題。
思考
任意給定正整數(shù)n，請(qǐng)問(wèn)在小于等于n的正整數(shù)之中，有多少個(gè)與n構(gòu)成互質(zhì)關(guān)系？
關(guān)于互質(zhì)關(guān)系
如果兩個(gè)正整數(shù)，除了1以外，沒(méi)有其他公因數(shù)，我們就稱(chēng)這兩個(gè)數(shù)是互質(zhì)關(guān)系（coprime）。
計(jì)算這個(gè)值的方式叫做歐拉函數(shù)，使用：Φ(n)表示
如:
- 計(jì)算8的歐拉函數(shù)，和8互質(zhì)的 1、2、3、4、5、6、7、8
φ(8) = 4 - 計(jì)算7的歐拉函數(shù)，和7互質(zhì)的 1、2、3、4、5、6、7
φ(7) = 6 - 計(jì)算56的歐拉函數(shù)
φ(56) = φ(8) * φ(7) = 4 * 6 = 24
現(xiàn)在你會(huì)發(fā)現(xiàn)，并不是所有的歐拉函數(shù)都可以口算出來(lái)，有些甚至計(jì)算機(jī)都算不出來(lái)。當(dāng)然你也發(fā)現(xiàn)了φ(56)似乎有些特殊。對(duì)了！歐拉函數(shù)有些特點(diǎn)是必須要知道的！
歐拉函數(shù)特點(diǎn)
- 當(dāng)n是質(zhì)數(shù)的時(shí)候，φ(n)=n-1。
- 如果n可以分解成兩個(gè)互質(zhì)的整數(shù)之積，如n=AB則：
φ(AB)=φ(A)* φ(B) - 根據(jù)以上兩點(diǎn)得到：
如果N是兩個(gè)質(zhì)數(shù)P1 和 P2的乘積則
φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)
歐拉定理
了解了歐拉函數(shù)，接下來(lái)需要知道一個(gè)定理。既然是定理，就是恒古不變的，已經(jīng)被數(shù)學(xué)家們證明過(guò)的，所以建議讀者可以驗(yàn)證，但最好不要試圖去證明，這個(gè)比較耗時(shí)（主要是耗腦，別玩著玩著懷疑智商了...）
歐拉定理
如果兩個(gè)正整數(shù)m和n互質(zhì)，那么m的φ(n)次方減去1，可以被n整除。
說(shuō)白了就是：
費(fèi)馬小定理
歐拉定理的特殊情況：如果兩個(gè)正整數(shù)m和n互質(zhì)，而且n為質(zhì)數(shù)！那么φ(n)結(jié)果就是n-1。
那么也就是：
等式轉(zhuǎn)換
1、根據(jù)歐拉定理
2、由于1^k ≡ 1，等號(hào)左右兩邊都來(lái)個(gè)k次方
3、由于1* m ≡ m，等號(hào)左右兩邊都乘上m
接下來(lái)，我們還需要進(jìn)行等式轉(zhuǎn)換。那么等式轉(zhuǎn)換4的前提是 模反元素
模反元素
如果兩個(gè)正整數(shù)e和x互質(zhì)，那么一定可以找到整數(shù)d，使得 ed-1 被x整除。
那么d就是e對(duì)于x的模反元素
說(shuō)白了就是
這個(gè)模反元素的等式也可以進(jìn)一步轉(zhuǎn)換，因?yàn)閑*d 一定是x的倍數(shù)加1。所以如下：
那么千辛萬(wàn)苦！我們通過(guò)多次的等式轉(zhuǎn)換。終于可以將這兩個(gè)等式進(jìn)行合并了！如下：
這個(gè)等式成立有一個(gè)前提！就是關(guān)于模反元素的。說(shuō)白了就是當(dāng)整數(shù)e和φ(n)互質(zhì)！一定有一個(gè)整數(shù)d是e相對(duì)于φ(n)的模反元素。
我們可以測(cè)試一下。
m 4
n 15
φ(n) 8
e 如果取值為3
d 可以為 11、19...(模反元素很明顯不止一個(gè)，其實(shí)就是解二元一次方程)
如果你測(cè)試了，那么你可以改變m的值試一下。其實(shí)這個(gè)等式不需要m和n 互質(zhì)。只要m小于n 等式依然成立。
這里需要注意的是，我們可以看做 m 通過(guò)一系列運(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ù)將非常?。m然RSA用于加密的數(shù)據(jù)也很小，但是沒(méi)這么大懸殊）
真正的RSA要更加強(qiáng)大，那么RSA是怎么演變來(lái)的呢？？
早期很多數(shù)學(xué)家也停留在了這一步！直到1967年迪菲赫爾曼密鑰交換打破了僵局！
迪菲赫爾曼密鑰交換
那么為什么說(shuō) 這個(gè)密鑰交換當(dāng)時(shí)轟動(dòng)了整個(gè)數(shù)學(xué)界！而且對(duì)人類(lèi)密碼學(xué)的發(fā)展非常重要呢？因?yàn)檫@個(gè)偉大的算法！能夠拆分剛才的等式。
當(dāng)非對(duì)稱(chēng)加密算法沒(méi)有出現(xiàn)以前，人類(lèi)都是用的對(duì)稱(chēng)加密。
所以密鑰的傳遞，就必須要非常小心。
迪菲赫爾曼密鑰交換 就是解決了 密鑰傳遞 的保密性?。∥覀儊?lái)看一下
們來(lái)假設(shè)一個(gè)傳遞密鑰的場(chǎng)景。算法就是用3 的次方 去模以17。 三個(gè)角色
-
服務(wù)器 隨機(jī)數(shù) 15
- 這個(gè)15只有服務(wù)器才知道。通過(guò)算法!! 得到結(jié)果 6 因?yàn)?3的15次方 mod 17 = 6 。然后將結(jié)果 6 公開(kāi)發(fā)送出去!!
- 拿到客戶端的 6 ，然后用6^15 mod 17 得到結(jié)果10(10就是交換得到的密鑰)
-
客戶端 隨機(jī)數(shù)13
- 得到結(jié)果 3 的 13次方 mod 17 = 12 然后將12公布出去。
- 拿到服務(wù)器的 12 ，然后用12^13 mod 17 得到結(jié)果10(10就是交換得到的密鑰)
-
黑客
它只能拿到6 和 12 。因?yàn)闆](méi)有私密數(shù)據(jù)13、15所以它沒(méi)法得到結(jié)果10.
那么這里可能一眼看過(guò)去不好理解!對(duì)吧!!
為什么 6的13次方會(huì)和12的15次方得到一樣的結(jié)果呢?
因?yàn)檫@就是規(guī)律!! 可以用小一點(diǎn)的數(shù)字測(cè)試一下!!
3^3 mod 17 = 10
10 ^ 2 mod 17 = 3 ^ 3 ^ 2 mod 17 結(jié)果都是15 !!
迪菲赫爾曼密鑰交換最核心的地方就在于這個(gè)規(guī)律！
RSA的誕生
以上就是RSA的數(shù)學(xué)原理，關(guān)于RSA的運(yùn)用后面再慢慢闡述。本人才疏學(xué)淺，如果有地方寫(xiě)得不對(duì)，請(qǐng)留言指出。也歡迎大家留言交流。
