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