一 ， 概述
在現(xiàn)代密碼學(xué)誕生以前，就已經(jīng)有很多的加密方法了。例如，最古老的斯巴達(dá)加密棒，廣泛應(yīng)用于公元前7世紀(jì)的古希臘。16世紀(jì)意大利數(shù)學(xué)家卡爾達(dá)諾發(fā)明的柵格密碼，基于單表代換的凱撒密碼、豬圈密碼，基于多表代換的維吉尼亞密碼，二戰(zhàn)中德軍廣泛使用的恩格瑪加密機(jī)…但最終都找到了有效的破解算法。
現(xiàn)代密碼學(xué)的誕生標(biāo)志是1977年1月由美國(guó)國(guó)家標(biāo)準(zhǔn)局公布的數(shù)據(jù)加密標(biāo)準(zhǔn)(Data Encryption Standard，DES)。
在經(jīng)過(guò)20多年之后，為適應(yīng)現(xiàn)代的安全要求，2000年美國(guó)國(guó)家和標(biāo)準(zhǔn)技術(shù)協(xié)會(huì)篩選和評(píng)測(cè)出了被稱為AES(Advanced Encryption Standard)的加密算法作為新的加密標(biāo)準(zhǔn)。目前，AES已被廣泛使用，且未發(fā)現(xiàn)致命缺陷。到目前為止，AES是一個(gè)安全的加密算法。
然而，在加密算法之外，面臨一個(gè)問(wèn)題，那就是：秘鑰的分發(fā)。就是說(shuō)，解密方如何獲得加密方的秘鑰呢？ 從而出現(xiàn)了：對(duì)稱加密和非對(duì)稱加密。
二，對(duì)稱加密和非對(duì)稱加密
1. 對(duì)稱加密
對(duì)稱加密指的就是加密和解密使用同一個(gè)秘鑰，所以叫做對(duì)稱加密。對(duì)稱加密只有一個(gè)秘鑰，作為私鑰。
常見(jiàn)的對(duì)稱加密算法：DES，AES，3DES等等。
2. 非對(duì)稱加密
非對(duì)稱加密指的是：加密和解密使用不同的秘鑰，一把作為公開(kāi)的公鑰，另一把作為私鑰。公鑰加密的信息，只有私鑰才能解密。私鑰加密的信息，只有公鑰才能解密。
常見(jiàn)的非對(duì)稱加密算法：RSA，ECC
3. 區(qū)別
對(duì)稱加密算法相比非對(duì)稱加密算法來(lái)說(shuō)，加解密的效率要高得多。但是缺陷在于對(duì)于秘鑰的管理上，以及在非安全信道中通訊時(shí)，密鑰交換的安全性不能保障。所以在實(shí)際的網(wǎng)絡(luò)環(huán)境中，會(huì)將兩者混合使用.
例如針對(duì)C/S模型，
服務(wù)端計(jì)算出一對(duì)秘鑰pub/pri。將私鑰保密，將公鑰公開(kāi)。
客戶端請(qǐng)求服務(wù)端時(shí)，拿到服務(wù)端的公鑰pub。
客戶端通過(guò)AES計(jì)算出一個(gè)對(duì)稱加密的秘鑰X。 然后使用pub將X進(jìn)行加密。
客戶端將加密后的密文發(fā)送給服務(wù)端。服務(wù)端通過(guò)pri解密獲得X。
然后兩邊的通訊內(nèi)容就通過(guò)對(duì)稱密鑰X以對(duì)稱加密算法來(lái)加解密。
三，RSA原理
我們先來(lái)看這樣一些基礎(chǔ)知識(shí)，并且以下我們討論全都是整數(shù)：
整數(shù)運(yùn)算
在整數(shù)運(yùn)算中 我們定義一個(gè)整數(shù)x，那么他的負(fù)數(shù)為-x，并且有x+(-x)=0；
他的倒數(shù)為x?1 , 并且有x×x?1 =1;
同余運(yùn)算
有整數(shù)a，b，正整數(shù)m。 假如a除以m余b。我們稱為a模m同余b，模數(shù)為m。并且記為a≡b(modm) ,例如10除以3余1
我們稱10模3同余1，記為10≡1(mod3) 。
我們分別討論模數(shù)為合數(shù)和質(zhì)數(shù)情況下，基于同余運(yùn)算的負(fù)數(shù)和倒數(shù)。
1. 當(dāng)模數(shù)為合數(shù)n時(shí)
簡(jiǎn)單起見(jiàn)，我們討論當(dāng)n為10的情況,10是兩個(gè)質(zhì)數(shù)乘積
當(dāng)模數(shù)為10的時(shí)候，參與運(yùn)算的都是小于10的數(shù)。因?yàn)榇笥?0的數(shù)除模取余之后都會(huì)小于10，所以只需要考慮小于模的數(shù)。
那么在同余運(yùn)算中
一個(gè)小于10的數(shù)a，他的負(fù)數(shù)x是什么？ 也就是說(shuō)使得(a+x)≡0(mod10) ; 那就是n?a,即x=n?a。這里的x就像是常規(guī)運(yùn)算下的-a。常規(guī)運(yùn)算下a+(?a)=0,我們說(shuō)?a是a的負(fù)數(shù)，這里(a+x)≡0(mod10)，我們說(shuō)x是a的負(fù)數(shù)。;
有a+(n?a)=a+(?a)+n=n≡0(modn) 。 當(dāng)n=10的時(shí)候 ，有如下表
| a | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| x | 0 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
那么，a的倒數(shù)a?1是什么呢？ 它要使得a×a?1在模數(shù)為n的情況下等于1，即a×a?1≡1(modn)
當(dāng)n=10的時(shí)候我們會(huì)發(fā)現(xiàn)，對(duì)于有的數(shù)我們可以找到它的倒數(shù)，有的數(shù)卻找不到
例如當(dāng)a=3，我們可以找到7，使得$3\times7= 21 \equiv 1\pmod {10} $ ;
而當(dāng)a=4的時(shí)候，我們有4×0=0，4×1=4，4×2=8，4×3=12，4×4=16，4×5=20，4×6=24，4×7=28，4×8=32，4×9=36，在模10的情況下，都不會(huì)等于1。
我們對(duì)于所有小于10的a都找他的倒數(shù)a?1，有下表
| a | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| a?1 | 1 | 不存在 | 7 | 不存在 | 不存在 | 不存在 | 3 | 不存在 | 9 |
有什么規(guī)律呢？
數(shù)學(xué)界已證明：當(dāng)a<n時(shí)，只有當(dāng)a和n互質(zhì)才能找到a?1。 同時(shí)還有以下結(jié)論，當(dāng)n=p×q ,且p和q都為質(zhì)數(shù)時(shí)，所有小于n的數(shù)中，能找到倒數(shù)的個(gè)數(shù)為(p?1)×(q?1)個(gè)。如果n有更多的質(zhì)因子，那么計(jì)算會(huì)更復(fù)雜點(diǎn)。
我們把所有小于n，并且能和n互質(zhì)的數(shù)的總個(gè)數(shù)記為一個(gè)函數(shù)φ(n) ，這個(gè)函數(shù)叫做歐拉函數(shù)。例
即當(dāng)n=p×q ,且p和q都為質(zhì)數(shù)時(shí)，有φ(n)=(p?1)×(q?1), 那么就有φ(10)=(2?1)×(5?1)=4
同時(shí)這些數(shù)還有以下兩個(gè)有趣的情況
這些數(shù)之間進(jìn)行互乘的同余運(yùn)算，結(jié)果還是這些數(shù)。
例如對(duì)于1：1×1≡1(mod10), 1×3≡3(mod10), 1×7≡7(mod10), 1×9≡9(mod10)
對(duì)于3：3×1≡3(mod10), 3×3≡9(mod10), 3×7≡1(mod10), 3×9≡7(mod10)
對(duì)于7：7×1≡7(mod10),7×3≡1(mod10),7×7≡9(mod10),7×9≡3(mod10)
對(duì)于9：9×1≡9(mod10),9×3≡7(mod10),9×7≡3(mod10),9×9≡1(mod10)
如果一些數(shù)在互相運(yùn)算之后，得到的結(jié)果還是這些數(shù)中，我們稱這些數(shù)在這個(gè)運(yùn)算條件下具有封閉性。
對(duì)這些數(shù)進(jìn)行求冪運(yùn)算，并且再模10，結(jié)果如下表
a 1 3 7 9 a0 1 1 1 1 a1 1 3 7 9 a2 1×1=1 3×3=9 7×7=9 9×9=1 a3 1×1×1=1 3×3×3=7 7×7×7=3 9×9×9=9 a4 1×1×1×1=1 3×3×3×3=1 7×7×7×7=1 1×1×1×1=1 其中，
在模n的情況下一定能找到一個(gè)數(shù)g,使得g0、g1、g2、…gφ(n)?1剛好把所有與n互質(zhì)并且小于n的數(shù)各得到一遍。我們把滿足這種條件的數(shù)稱為 生成元。
我們規(guī)定a0≡1(mod10)
所有aφ(10)的結(jié)果都為1,即有aφ(n)≡1(mod10)。(根據(jù)前面的介紹可知這里的φ(10)=(2?1)×(5?1)=4)
對(duì)于3和7來(lái)說(shuō)，他們的a0、a1、a2、a3剛好把1,3,7,9各得到了一遍。到a4時(shí)剛好又回到了1，如果大于4之后，又會(huì)開(kāi)始循環(huán)
2. 當(dāng)模數(shù)為質(zhì)數(shù)p的時(shí)候
當(dāng)模p為質(zhì)數(shù)的時(shí)候，我們假設(shè)p=7時(shí)。
同樣求小于 p 的數(shù) a 的負(fù)數(shù) x 使得(a+x)≡0(mod10)有如下表
| a | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| x | 6 | 5 | 4 | 3 | 2 | 1 |
而求a的倒數(shù)時(shí)，因?yàn)閜是質(zhì)數(shù)，所有小于p的數(shù)都和它互質(zhì)。所以，所有小于p的數(shù)a都能找到它的倒數(shù)?a。它的歐拉函數(shù)φ(n)=p?1。
如下表
| a | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| a?1 | 1 | 4 | 5 | 2 | 3 | 6 |
它同樣有模數(shù)為合數(shù)n時(shí)的性質(zhì)
這些數(shù)在同余運(yùn)算規(guī)則下進(jìn)行乘法運(yùn)算，同樣具有封閉性
任意的a求冪依然滿足aφ(n)=1的規(guī)則，且同樣有生成元
3. 離散對(duì)數(shù)問(wèn)題
前面我們得到了有這么一個(gè)結(jié)論:
在模n的情況下一定能找到一個(gè)數(shù)g,使得g0, g1 ,g2、…gφ(n)?1剛好把所有與n互質(zhì)并且小于n的數(shù)各得到一遍。我們把滿足這種條件的數(shù)稱為 生成元。
那么，在模n的條件下，給定它的生成元g,以及一個(gè)小于n的正整數(shù)a。通過(guò)一個(gè)叫做同余冪的算法能夠快速的算出ga的值,我們把算得的結(jié)果記為b。 即我們?cè)谀?span style="position: relative;">n的條件下，能夠快速的算出b=ga的值。
由于生成元的特性，我們知道，在模n的條件下，給定生成元g，以及b的值，一定存在一個(gè)小于n的正整數(shù)a，使得b=ga。那么如何求a的值？
我們發(fā)現(xiàn)，這個(gè)問(wèn)題沒(méi)有任何規(guī)律。例如，當(dāng)n=11，g=2時(shí)，有如下表
| g | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| b=ga | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 1 |
| a | 0 | 1 | 8 | 2 | 4 | 9 | 7 | 3 | 6 | 5 | 10 |
在實(shí)數(shù)計(jì)算中，我們知道當(dāng)b=ga時(shí)，$a=log_bg 。然而這個(gè)計(jì)算在模n的條件下非常困難。這樣一個(gè)問(wèn)題被稱為離散對(duì)數(shù)問(wèn)題。在目前的技術(shù)條件下，這是一個(gè)極為困難的計(jì)算。當(dāng)這個(gè)n$值達(dá)到十進(jìn)制兩三百位時(shí)，即便是有大型計(jì)算機(jī)的情況下，所要花費(fèi)的時(shí)間依然是個(gè)天文數(shù)字。
4.RSA原理
當(dāng)n=p×q，p與q是兩個(gè)大質(zhì)數(shù)。只知道n的值，想要計(jì)算p和q，這是一個(gè)世界性的極為困難的數(shù)學(xué)難題。RSA的基礎(chǔ)就是基于的n的兩個(gè)質(zhì)數(shù)分解難題。
具體過(guò)程如下：
Alice選擇兩個(gè)大質(zhì)數(shù)p和q，求得n=p×q。計(jì)算φ(n)=(p?1)×(q?1)，接下來(lái)，Alice選擇一個(gè)與φ(n)互質(zhì)的數(shù)e，并計(jì)算$ e^{-1}在模為\varphi(n)下的值，將計(jì)算出的值記為s$。
我們知道，e與φ(n)互質(zhì)，所以一定存在e?1, 這一步，service 就算出了公鑰和私鑰，其中，公鑰為(e，n),私鑰為(s，n)
接下來(lái)，Bob可以在非安全信道請(qǐng)求Alice獲得公鑰。Evl通過(guò)中間攻擊，只能獲得(e,n),以及密文D。假定Bob需要發(fā)送的內(nèi)容為m，計(jì)算D=me(modn),然后把D發(fā)送給Alice
Alice收到D之后，計(jì)算me(e?1)(modn)=me×e?1(modn)≡m(modn).
其中，在不安全信道中傳輸?shù)氖?span style="position: relative;">n和e。然而，p和q只有Alice才知道，即便Eval獲得了n，基于質(zhì)數(shù)分解難題，他無(wú)法算出p和q，也就無(wú)法算出私鑰s來(lái)揭秘被加密的消息。
且，m不能是大于n的數(shù)，當(dāng)m大于n時(shí)可以拆分之后分段加密。
舉個(gè)例子吧
假設(shè)取兩個(gè)質(zhì)數(shù)p=11, q=13,那么n=143.
φ(n)=(p?1)×(q?1)=120。
隨意選取一個(gè)和φ(n)互質(zhì)的數(shù)e，假定這個(gè)數(shù)字為7,即e=7，
那么e?1=103,使得e×e?1再模φ(n)等于1,即e×e?1≡1(modφ(n))，即7×103=721≡1(mod120).公鑰為(e，n),即(7，143)。
私鑰為(s，n)， 即(103，143)。
要加密的原始數(shù)據(jù)為m，假設(shè)m=13。(計(jì)算機(jī)中任何數(shù)據(jù)，最后傳輸或者保存都會(huì)轉(zhuǎn)換成二進(jìn)制的數(shù)據(jù))加密過(guò)程：Bob請(qǐng)求Alice，獲得公鑰，密文為D, D=137(mod143)=117。 Bob將D傳輸出去。
Evl通過(guò)中間攻擊，只能獲得(e,n),以及密文D
解密過(guò)程：Alice獲得D，通過(guò)只有Alice才有的私鑰進(jìn)行解密。117103(mod143)=13,獲得了原始數(shù)據(jù)。
這里的11和13比較小，知道公鑰為(7,143)之后，容易將143做因式分解求的11與13,從而可以獲得120這個(gè)值，從而再算出e?1。但是當(dāng)p和q是兩個(gè)非常大的的質(zhì)數(shù)的時(shí)候，就很難將其分解出來(lái)。 這樣，就無(wú)法算出e?1。從而不能從密文中獲得原始數(shù)據(jù)。
