在對(duì)稱密碼中，由于加密和解密的密鑰是相同的，因此必須向接收者配送密鑰。用于解密的密鑰必須被配送給接收者，這一問(wèn)題稱為密鑰配送問(wèn)題，如果使用公鑰密碼，則無(wú)需向接收者配送用于解密的密鑰，這樣就解決了密鑰配送問(wèn)題?？梢哉f(shuō)公鑰密碼是密碼學(xué)歷史上最偉大的發(fā)明。

密鑰配送問(wèn)題

解決密鑰配送問(wèn)題的方法

• 通過(guò)事先共享密鑰來(lái)解決
• 通過(guò)密鑰分配中心來(lái)解決
• 通過(guò)Diffic-Hellman密鑰交換來(lái)解決
• 通過(guò)公鑰密碼來(lái)解決

通過(guò)事先共享密鑰來(lái)解決

在人數(shù)很多的情況下，通信所需要的密鑰數(shù)量會(huì)增大，例如：1000名員工中每一個(gè)人都可以和另外999個(gè)進(jìn)行通信，則每個(gè)人需要999個(gè)通信密鑰，整個(gè)密鑰數(shù)量：
1000 x 999 ÷ 2 = 499500
很不現(xiàn)實(shí)，因此此方法有一定的局限性

通過(guò)密鑰分配中心來(lái)解決

• 密鑰分配中心雖然能解決上述密鑰數(shù)量過(guò)多的限制，但是隨著員工數(shù)量的增多，密鑰分配中心的負(fù)荷也會(huì)隨之增加，如果密鑰分配中心計(jì)算機(jī)發(fā)生故障，全公司加密通信就會(huì)癱瘓，
• 此外主動(dòng)攻擊者也可能針對(duì)密鑰分配中心下手
  這是密鑰分配中心所面臨的問(wèn)題。

通過(guò)Diffic-Hellman密鑰交換來(lái)解決

在Diffic-Hellman密鑰交換中，進(jìn)行加密通信的雙方需要交換一些信息，而這些信息即便被竊聽(tīng)者竊聽(tīng)到也沒(méi)有問(wèn)題（后續(xù)文章會(huì)進(jìn)行詳解）。

通過(guò)公鑰密碼來(lái)解決

在對(duì)稱密碼中，加密密鑰和解密密鑰是相同的，但公鑰密碼中，加密密鑰和解密密鑰卻是不同的。只要擁有加密密鑰，任何人都可以加密，但沒(méi)有解密密鑰是無(wú)法解密的。

公鑰密碼

公鑰密碼中，密鑰分為加密密鑰（公鑰）和解密密鑰（私鑰）兩種。

• 發(fā)送者只需要加密密鑰
• 接收者知悉要解密密鑰
• 解密密鑰不可以被竊聽(tīng)者獲取
• 加密密鑰被竊聽(tīng)者獲取也沒(méi)有問(wèn)題

公鑰和私鑰是一一對(duì)應(yīng)的，一對(duì)公鑰和私鑰統(tǒng)稱為密鑰對(duì)，由公鑰進(jìn)行加密的密文，必須使用與該公鑰配對(duì)的私鑰才能夠解密。密鑰對(duì)中的兩個(gè)密鑰之間具有非常密切的關(guān)系——數(shù)學(xué)上的關(guān)系——因此公鑰和私鑰是不能分別單獨(dú)生成的。

公鑰通信的流程

發(fā)送者：Alice ???? 接收者：Bob ???? 竊聽(tīng)者：Eve
通信過(guò)程是由接收者Bob來(lái)啟動(dòng)的

1. • Bob生成密鑰對(duì)，私鑰自己來(lái)妥善保管
2. • Bob將自己的公鑰發(fā)送給Alice。
   • Bob的公鑰被Eve截獲也沒(méi)有關(guān)系。
   • 公鑰發(fā)送給Alice，表示Bob請(qǐng)Alice用這個(gè)公鑰對(duì)消息進(jìn)行加密并發(fā)送給他。
3. • Alice用Bob的公鑰對(duì)消息進(jìn)行加密。
   • 加密后的消息只有用Bob的私鑰才能夠解密
   • 雖然Alice擁有Bob的公鑰，但是Bob的公鑰是無(wú)法對(duì)密文進(jìn)行解密的
4. • Alice將密文發(fā)給Bob
   • 密文被Eve截獲也沒(méi)關(guān)系，Eve可能擁有Bob的公鑰，但是無(wú)法進(jìn)行解密

5. • Bob用自己的私鑰對(duì)密文進(jìn)行解密

     
     
     image.png

公鑰密碼無(wú)法解決的問(wèn)題

公鑰密碼解決了密鑰配送的問(wèn)題，但依然面臨著下面的問(wèn)題

• 判斷所得到的公鑰是否正確合法，被稱為公鑰認(rèn)證問(wèn)題（后面會(huì)通過(guò)中間人攻擊來(lái)探討這個(gè)問(wèn)題）
• 公鑰密碼的處理速度只有對(duì)稱密碼的幾百分之一。

RSA

什么是RSA

RSA是目前使用最廣泛的公鑰密碼算法，名字是由它的三位開(kāi)發(fā)者，即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母組成的（Rivest-Shamir-Adleman）。RSA可以被使用公鑰密碼和數(shù)字簽名（此文只針對(duì)公鑰密碼進(jìn)行探討，數(shù)字簽名后續(xù)文章敬請(qǐng)期待）1983年在美國(guó)取得了專利，但現(xiàn)在該專利已經(jīng)過(guò)期。

RSA加密

在RSA中，明文、密鑰和密文都是數(shù)字，RSA加密過(guò)程可以用下列公式來(lái)表達(dá)

密文 = 明文^E mod N

注意 mod運(yùn)算講解在這里

簡(jiǎn)單的來(lái)說(shuō)，RSA的密文是對(duì)代表明文的數(shù)字的 E 次方求mod N 的結(jié)果，換句話說(shuō)：將明文和自己做 E 次乘法，然后將結(jié)果除以 N 求余數(shù)，這個(gè)余數(shù)就是密文。

從上面公式中可以看出，只要知道 E 和 N 這兩個(gè)數(shù)，任何人都可以完成加密的運(yùn)算。所以說(shuō) E 和 N 是RSA加密的密鑰，即 E 和 N 的組合就是公鑰 ，一般寫成 “公鑰是(E,N) ” 或者 “公鑰是{E,N}”

RSA解密

RSA解密過(guò)程可以用下列公式來(lái)表達(dá)

明文 = 密文^D mod N
對(duì)表示密文的數(shù)字的 D 次方求mod N 就可以得到明文，換句話說(shuō)：將密文和自己做 D 次乘法，在對(duì)其結(jié)果除以 N 求余數(shù)，就可以得到明文
此時(shí)使用的數(shù)字 N 和加密時(shí)使用的數(shù)字 N 是相同的，數(shù) D 和數(shù) N 組合起來(lái)就是RSA的解密密鑰，因此 D 和 N 的組合就是私鑰。只要知道 D 和 N 兩個(gè)數(shù)的人才能夠完成解密的運(yùn)算

由于 N 是公鑰的一部分，使公開(kāi)的，因此單獨(dú)將 D 成為私鑰也是可以的

RSA的加密和解密

RSA的加密和解密

生成密鑰對(duì)

根據(jù)加密和解密的公式可以看出，需要用到三個(gè)數(shù)—— E、D 和 N 求這三個(gè)數(shù)就是生成密鑰對(duì)，RSA密鑰對(duì)的生成步驟如下：

• 求 N
• 求 L (L 是僅在生成密鑰對(duì)的過(guò)程中使用的數(shù))
• 求 E
• 求 D

1、求 N

準(zhǔn)備兩個(gè)很大的質(zhì)數(shù) p 和 q ，將這兩個(gè)數(shù)相乘，結(jié)果就是 N
N = p x q

2、求 L

L 是 p-1 和 q-1 的最小公倍數(shù)，如果用lcm( X , Y )來(lái)表示 “X 和 Y 的最小公倍數(shù)” 則L可以寫成下列形式
L = lcm ( p - 1，q - 1)

3、求 E

E 是一個(gè)比1大、比 L 小的數(shù)。 E 和 L的最大公約數(shù)必須為1，如果用gcd(X , Y)來(lái)表示 X 和 Y 的最大公約數(shù)，則 E 和 L之間存在下列關(guān)系：
1 < E < L
gcd(E , L) = 1 （是為了保證一定存在解密時(shí)需要使用的數(shù) D ）

4、求 D

1 < D < L
E x D mod L = 1

RSA中密鑰對(duì)的生成

RSA密鑰對(duì)

來(lái)個(gè)具體的例子

密鑰對(duì)生成

1、求 N

p = 17
q = 19
N = p x q = 17 x 19 = 323

2、求 L

L = lcm ( p - 1，q - 1) = lcm (16,18) = 144

3、求 E

gcd(E , L) = 1
滿足條件的 E 有很多：5，7，11，13，17，19，23，25，29，31...
這里選擇5來(lái)作為E,到這里我們已經(jīng)知道E = 5 ?? N = 323 這就是公鑰

4、求 D

E x D mod L = 1
D = 29 可以滿足上面的條件，因此：
公鑰：E = 5 ??? N = 323
私鑰：D = 29 ?? N = 323

5、加密

要加密的明文必須是小于 N 的數(shù)，這是因?yàn)樵诩用苓\(yùn)算中需要求 mod N 假設(shè)加密的明文是123
明文^E mod N = 123⁵ mod 323 = 225（密文）

6、解密

對(duì)密文225進(jìn)行解密
密文^D mod N = 225²⁹ mod 323 = 225¹⁰ x 225¹⁰ x 225⁹ mod 323 = (225¹⁰ mod 323) x (225¹⁰ mod 323) x (225⁹ mod 323) = 16 x 16 x 191 mod 323 = 48896 mod 323 = 123（明文）

對(duì)RSA的攻擊

1、通過(guò)密文來(lái)求得明文

如果沒(méi)有mod N 的話，即：

明文 = 密文^D mod N

通過(guò)密文求明文的難度不大，因?yàn)檫@可以看作是一個(gè)求對(duì)數(shù)的問(wèn)題。
但是，加上mod N 之后，求明文就變成了求離散對(duì)數(shù)的問(wèn)題，這是非常困難的，因?yàn)槿祟愡€沒(méi)有發(fā)現(xiàn)求離散對(duì)數(shù)的高效算法。

2、通過(guò)暴力破解來(lái)找出 D

只要知道 D，就能夠?qū)γ芪倪M(jìn)行解密，逐一嘗試 D 來(lái)暴力破譯RSA，暴力破解的難度會(huì)隨著D的長(zhǎng)度增加而加大，當(dāng) D 足夠長(zhǎng)時(shí)，就不能再現(xiàn)實(shí)的時(shí)間內(nèi)通過(guò)暴力破解找出數(shù) D

目前，RSA中所使用的 p 和 q 的長(zhǎng)度都是1024比特以上，N 的長(zhǎng)度為2048比特以上，由于 E 和 D 的長(zhǎng)度可以和N差不多，因此要找出 D ，就需要進(jìn)行2048比特以上的暴力破解。這樣的長(zhǎng)度下暴力破解找出 D 是極其困難的

3、通過(guò) E 和 N 求出 D

E x D mod L = 1 ???? ???? L = lcm ( p - 1，q - 1)
由 E 計(jì)算 D 需要使用 p 和 q ，但是密碼破譯者并不知道 p 和 q

對(duì)于RSA來(lái)說(shuō)，有一點(diǎn)非常重要，那就是質(zhì)數(shù) p 和 q 不能被密碼破譯這知道。把 p 和 q 交給密碼破譯者與把私鑰交給密碼破譯者是等價(jià)的。

p 和 q 不能被密碼破譯者知道，但是 N = p x q 而且 N 是公開(kāi)的， p 和 q 都是質(zhì)數(shù)，因此由 N 求 p 和 q 只能通過(guò)將 N 進(jìn)行質(zhì)因數(shù)分解，所以說(shuō)：
一旦發(fā)現(xiàn)了對(duì)大整數(shù)進(jìn)行質(zhì)因數(shù)分解的高效算法，RSA就能夠被破譯

4、中間人攻擊

這種方法雖然不能破譯RSA，但卻是一種針對(duì)機(jī)密性的有效攻擊。

所謂中間人攻擊，就是主動(dòng)攻擊者M(jìn)allory混入發(fā)送者和接收者的中間，對(duì)發(fā)送者偽裝成接收者，對(duì)接收者偽裝成發(fā)送者的攻擊，在這里，Mallory就是“中間人”

中間人攻擊

注意：在這個(gè)過(guò)程中，Alice所持有的公鑰并非是Bob的，而是Mallory的，所以發(fā)送的內(nèi)容被Mallory攔截以后，Mallory可以通過(guò)自己的私鑰解密，而Mallory還持有Bob的公鑰，所以可以篡改信息，然后發(fā)送給Bob。

這種攻擊不僅針對(duì)RSA，而是可以針對(duì)任何公鑰密碼。在這個(gè)過(guò)程中，公鑰密碼并沒(méi)有被破譯，所有的密碼算法也都正常工作并確保了機(jī)密性。然而，所謂的機(jī)密性并非在Alice和Bob之間，而是在Alice和Mallory之間，以及Mallory和Bob之間成立的。僅靠公鑰密碼本身，是無(wú)法防御中間人攻擊的。

要防御中間人攻擊，還需要一種手段來(lái)確認(rèn)所收到的公鑰是否真的屬于Bob，這種手段稱為認(rèn)證。在這種情況下，我們可以使用公鑰的證書(后面會(huì)陸續(xù)更新文章來(lái)進(jìn)行探討)

5、選擇密文攻擊

網(wǎng)絡(luò)上很多服務(wù)器在收到格式不正確的數(shù)據(jù)時(shí)都會(huì)向通信對(duì)象返回錯(cuò)誤消息，并提示“這里的數(shù)據(jù)有問(wèn)題”，然而，這種看似很貼心的設(shè)計(jì)卻會(huì)讓攻擊者有機(jī)可乘。攻擊者可以向服務(wù)器反復(fù)發(fā)送自己生成的偽造密文，然后分析返回的錯(cuò)誤消息和響應(yīng)時(shí)間獲得一些關(guān)于密鑰和明文的信息。

為了抵御這種攻擊，可以對(duì)密文進(jìn)行“認(rèn)證”，RSA-OAEP(最優(yōu)非對(duì)稱加密填充)正是基于這種思路設(shè)計(jì)的一種RSA改良算法。

RSA-OAEP在加密時(shí)會(huì)在明文前面填充一些認(rèn)證信息，包括明文的散列值以及一定數(shù)量的0，然后用RSA進(jìn)行加密，在解密的過(guò)程中，如果解密后的數(shù)據(jù)的開(kāi)頭沒(méi)有找到正確的認(rèn)證信息，則可以判定有問(wèn)題，并返回固定的錯(cuò)誤消息（重點(diǎn)是，不能將具體的錯(cuò)誤內(nèi)容告知開(kāi)發(fā)者）
RSA-OAEP在實(shí)際應(yīng)用中，還會(huì)通過(guò)隨機(jī)數(shù)使得每次生成的密文呈現(xiàn)不同的排列方式，從而進(jìn)一步提高安全性。

隨著計(jì)算機(jī)技術(shù)的進(jìn)步等，以前被認(rèn)為是安全的密碼會(huì)被破譯，這一現(xiàn)象稱為密碼劣化，針對(duì)這一點(diǎn)：

• 1024比特的RSA不應(yīng)被用于新的用途
• 2048比特的RSA可在2030年之前被用于新的用途
• 4096比特的RSA在2031年之后仍可被用于新的用途