本人以前對非對稱加密有一些了解，但是對非對稱加密為啥是安全的一直不是很清楚，所以今天打算弄懂這個問題。
一，對稱加密和非對稱加密
1. 對稱加密
對稱加密指的就是加密和解密使用同一個秘鑰，所以叫做對稱加密。對稱加密只有一個秘鑰，作為私鑰。
常見的對稱加密算法：DES，AES，3DES等等。
2. 非對稱加密
非對稱加密指的是：加密和解密使用不同的秘鑰，一把作為公開的公鑰，另一把作為私鑰。公鑰加密的信息，只有私鑰才能解密。私鑰加密的信息，只有公鑰才能解密。
常見的非對稱加密算法：RSA，ECC
3. 區(qū)別
對稱加密算法相比非對稱加密算法來說，加解密的效率要高得多。但是缺陷在于對于秘鑰的管理上，以及在非安全信道中通訊時，密鑰交換的安全性不能保障。所以在實(shí)際的網(wǎng)絡(luò)環(huán)境中，會將兩者混合使用.
例如針對C/S模型
- 服務(wù)端計算出一對秘鑰pub/pri。將私鑰保密，將公鑰公開。
- 客戶端請求服務(wù)端時，拿到服務(wù)端的公鑰pub。
- 客戶端通過AES計算出一個對稱加密的秘鑰X。 然后使用pub將X進(jìn)行加密。
- 客戶端將加密后的密文發(fā)送給服務(wù)端。服務(wù)端通過pri解密獲得X。
- 然后兩邊的通訊內(nèi)容就通過對稱密鑰X以對稱加密算法來加解密
二，RSA原理
我們先來看這樣一些基礎(chǔ)知識，并且以下我們討論全都是整數(shù)：
整數(shù)運(yùn)算
在整數(shù)運(yùn)算中 我們定義一個整數(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時
簡單起見，我們討論當(dāng)n為10的情況,10是兩個質(zhì)數(shù)乘積
當(dāng)模數(shù)為10的時候，參與運(yùn)算的都是小于10的數(shù)。因?yàn)榇笥?0的數(shù)除模取余之后都會小于10，所以只需要考慮小于模的數(shù)。
那么在同余運(yùn)算中，一個小于10的數(shù)a，他的負(fù)數(shù)x是什么？ 也就是說使得(a+x)≡0(mod10); 那就是n?a,即x=n?a。這里的x就像是常規(guī)運(yùn)算下的-a。常規(guī)運(yùn)算下a+(?a)=0,我們說?a是a的負(fù)數(shù)，這里(a+x)≡0(mod10)，我們說x是a的負(fù)數(shù)。
有a+(n?a)=a+(?a)+n=n≡0(modn)。 當(dāng)n=10的時候 ，有如下表
| 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的時候我們會發(fā)現(xiàn)，對于有的數(shù)我們可以找到它的倒數(shù)，有的數(shù)卻找不到。例如當(dāng)a=3，我們可以找到7，使得3×7=21≡1(mod10) ;而當(dāng)a=4的時候，我們有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的情況下，都不會等于1。
我們對于所有小于10的a都找他的倒數(shù)a^(?1)，有下表
| a | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| x | 1 | 不存在 | 7 | 不存在 | 不存在 | 不存在 | 3 | 不存在 | 9 |
有什么規(guī)律呢？
數(shù)學(xué)界已證明：當(dāng)a<n時，只有當(dāng)a和n互質(zhì)才能找到a^(?1)。 同時還有以下結(jié)論，當(dāng)n=p×q,且p和q都為質(zhì)數(shù)時，所有小于n的數(shù)中，能找到倒數(shù)的個數(shù)為(p?1)×(q?1)個。如果n有更多的質(zhì)因子，那么計算會更復(fù)雜點(diǎn)。
我們把所有小于n，并且能和n互質(zhì)的數(shù)的總個數(shù)記為一個函數(shù)φ(n)
，這個函數(shù)叫做歐拉函數(shù)。例即當(dāng)n=p×q ,且p和q都為質(zhì)數(shù)時，有φ(n)=(p?1)×(q?1), 那么就有φ(10)=(2?1)×(5?1)=4 。
同時這些數(shù)還有以下兩個有趣的情況
1.這些數(shù)之間進(jìn)行互乘的同余運(yùn)算，結(jié)果還是這些數(shù)。
例如
對于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)
如果一些數(shù)在互相運(yùn)算之后，得到的結(jié)果還是這些數(shù)中，我們稱這些數(shù)在這個運(yùn)算條件下具有封閉性。
2.對這些數(shù)進(jìn)行求冪運(yùn)算，并且再模10，結(jié)果如下表
| a | 1 | 3 | 7 | 9 |
|---|---|---|---|---|
| a^0 | 1 | 1 | 1 | 1 |
| a^1 | 1 | 3 | 7 | 9 |
| a^2 | 1×1=1 | 3×3=9 | 7×7=9 | 9×9=1 |
| a^3 | 1×1×1=1 | 3×3×3=7 | 7×7×7=3 | 9×9×9=9 |
| a^4 | 1×1×1×1=1 | 3×3×3×3=1 | 7×7×7×7=1 | 1×1×1×1=1 |
其中，
- 我們規(guī)定a0≡1(mod10)
- 所有a^(φ(10)) 的結(jié)果都為1,即有a^(φ(n))≡1(mod10)。(根據(jù)前面的介紹可知這里的φ(10)=(2?1)×(5?1)=4)
- 對于3和7來說，他們的a^0 、a^1 、a^2 、a^3 剛好把1,3,7,9各得到了一遍。到a^4時剛好又回到了1，如果大于4之后，又會開始循環(huán)
在模n的情況下一定能找到一個數(shù)g,使得g^0 、g^1 、g^2 、……g^(φ(n)?1)
剛好把所有與n互質(zhì)并且小于n的數(shù)各得到一遍。我們把滿足這種條件的數(shù)稱為 生成元。
2. 當(dāng)模數(shù)為質(zhì)數(shù)p的時候
當(dāng)模p為質(zhì)數(shù)的時候，我們假設(shè)p=7時。
同樣求小于 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ù)時，因?yàn)閜是質(zhì)數(shù)，所有小于p的數(shù)都和它互質(zhì)。所以，所有小于p
的數(shù)a都能找到它的倒數(shù)a^(?1)。它的歐拉函數(shù)φ(n)=p?1。
| a | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| a^(-1) | 1 | 4 | 5 | 2 | 3 | 6 |
它同樣有模數(shù)為合數(shù)n時的性質(zhì)
1.這些數(shù)在同余運(yùn)算規(guī)則下進(jìn)行乘法運(yùn)算，同樣具有封閉性
2.任意的a求冪依然滿足aφ(n)=1的規(guī)則，且同樣有生成元
3. 離散對數(shù)問題
前面我們得到了有這么一個結(jié)論:
在模n的情況下一定能找到一個數(shù)g,使得g^0, g^1 ,g^2 、……g^(φ(n)?1)剛好把所有與n互質(zhì)并且小于n的數(shù)各得到一遍。我們把滿足這種條件的數(shù)稱為生成元
那么，在模n的條件下，給定它的生成元g,以及一個小于n的正整數(shù)a。通過一個叫做同余冪的算法能夠快速的算出g^a的值,我們把算得的結(jié)果記為b。 即我們在模n的條件下，能夠快速的算出b=g^a的值。
由于生成元的特性，我們知道，在模n的條件下，給定生成元g，以及b的值，一定存在一個小于n的正整數(shù)a，使得b=g^a。那么如何求a的值？
我們發(fā)現(xiàn)，這個問題沒有任何規(guī)律。例如，當(dāng)n=11，g=2時，有如下表
| g | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| b=g^a | 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ù)計算中，我們知道當(dāng)b=g^a時，a=logbg
。然而這個計算在模n的條件下非常困難。這樣一個問題被稱為離散對數(shù)問題。在目前的技術(shù)條件下，這是一個極為困難的計算。當(dāng)這個n值達(dá)到十進(jìn)制兩三百位時，即便是有大型計算機(jī)的情況下，所要花費(fèi)的時間依然是個天文數(shù)字
4.RSA原理
當(dāng)n=p×q，p與q是兩個大質(zhì)數(shù)。只知道n的值，想要計算p和q，這是一個世界性的極為困難的數(shù)學(xué)難題。RSA的基礎(chǔ)就是基于的n的兩個質(zhì)數(shù)分解難題。
具體過程如下：
- Alice選擇兩個大質(zhì)數(shù)p和q，求得n=p×q。計算φ(n)=(p?1)×(q?1)，接下來，Alice選擇一個與φ(n)互質(zhì)的數(shù)e，并計算e^(?1)在模為φ(n)下的值，將計算出的值記為s。
我們知道，e與φ(n)互質(zhì)，所以一定存在e^(?1), 這一步，service 就算出了公鑰和私鑰，其中，公鑰為(e，n),私鑰為(s，n) - 接下來，Bob可以在非安全信道請求Alice獲得公鑰。Evl通過中間攻擊，只能獲得(e,n),以及密文D。假定Bob需要發(fā)送的內(nèi)容為m，計算D=m^e(modn),然后把D發(fā)送給Alice
- Alice收到D之后，計算m^ (e ^ (1/e))(modn)=m^ (e×1/e)(mod n)≡m(modn)
其中，在不安全信道中傳輸?shù)氖莕和e。然而，p和q只有Alice才知道，即便Eval獲得了n，基于質(zhì)數(shù)分解難題，他無法算出p和q，也就無法算出私鑰s來揭秘被加密的消息。
且，m不能是大于n的數(shù)，當(dāng)m大于n時可以拆分之后分段加密。
舉個例子吧
- 假設(shè)取兩個質(zhì)數(shù)p=11, q=13,那么n=143. φ(n)=(p?1)×(q?1)=120。 隨意選取一個和φ(n)互質(zhì)的數(shù)e，假定這個數(shù)字為7,即e=7， 那么e(?1)=63,使得e×e(?1)再模φ(n)等于1,即e×e^(?1)≡1(modφ(n))，即7×63=441≡1(mod120).
- 公鑰為(e，n),即(7，143)。 私鑰為(s，n)， 即(63，143)。 要加密的原始數(shù)據(jù)為m，假設(shè)m=13。(計算機(jī)中任何數(shù)據(jù)，最后傳輸或者保存都會轉(zhuǎn)換成二進(jìn)制的數(shù)據(jù))
- 加密過程：Bob請求Alice，獲得公鑰，密文為D, D=13^7(mod143)=117。 Bob將D傳輸出去
- Evl通過中間攻擊，只能獲得(e,n),以及密文 D
- 解密過程：Alice獲得D，通過只有Alice才有的私鑰進(jìn)行解密。117^63(mod143)=13,獲得了原始數(shù)據(jù)。
這里的11和13比較小，知道公鑰為(7,143)之后，容易將143做因式分解求的11與13,從而可以算出e^(?1)。但是當(dāng)p和q是兩個非常大的的質(zhì)數(shù)的時候，就很難將其分解出來。 這樣，就無法算出e^(?1)。從而不能從密文中獲得原始數(shù)據(jù)。
