1. 數(shù)學(xué)之美和密碼學(xué)

前陣子閑來(lái)無(wú)事看了會(huì)兒《數(shù)學(xué)之美》，其中第17章講述了由電視劇《暗算》展開的密碼學(xué)背后的一些數(shù)學(xué)原理。

書中從凱撒密碼到二戰(zhàn)盟軍和日軍，講到密碼學(xué)中均勻分布&統(tǒng)計(jì)獨(dú)立的基礎(chǔ)理論，看得我津津有味，但是其中一些細(xì)節(jié)沒(méi)有整明白，于是決定搞篇文章。

2. 加密算法的一點(diǎn)歷史

我們知道常見(jiàn)的加密算法有：對(duì)稱加密和非對(duì)稱加密，非對(duì)稱加密是我們今天的主角。

非對(duì)稱加密不是一蹴而就的，它是1976年之后才出現(xiàn)的，可以說(shuō)非對(duì)稱加密是對(duì)稱加密的優(yōu)化。

2.1 對(duì)稱加密的缺點(diǎn)

所謂對(duì)稱加密是指：發(fā)送方使用一種規(guī)則對(duì)信息進(jìn)行處理，接收方需要使用相同的規(guī)則對(duì)信息進(jìn)行逆向處理。

對(duì)稱加密要求通信雙方使用相同的規(guī)則和密鑰進(jìn)行加解密，這樣如何妥善保管密鑰和規(guī)則就非常重要了。

如果密鑰泄露那么再?gòu)?qiáng)大的對(duì)稱加密算法也是徒勞的，所以如何安全地交換對(duì)稱加密的規(guī)則和密鑰是短板。

如何安全地交換密鑰呢？讓人頭疼。

2.2 密鑰交換算法

1976年兩位美國(guó)計(jì)算機(jī)學(xué)家 Whitfield Diffie 和 Martin Hellman，提出了一種嶄新構(gòu)思，可以在不傳遞密鑰的情況下，完成解密，聽著很厲害的樣子，這難道就是江湖上傳說(shuō)的隔空打牛？

其實(shí)這是被稱為 Diffie-Hellman 迪菲-赫爾曼密鑰交換算法，來(lái)看看維基百科上兩位大神的簡(jiǎn)介：

這兩位大神是密碼學(xué)的先驅(qū)，為非對(duì)稱加密算法指出了明路：雙方不一定要直接交換密鑰。

迪菲-赫爾曼密鑰交換算法中通信雙方并沒(méi)有真正交換密鑰，而是通過(guò)計(jì)算生成出一個(gè)相同的共享密鑰，具體的過(guò)程還是比較復(fù)雜，在此不展開了。

非對(duì)稱加密算法RSA借鑒了這種思想，使用公鑰和私鑰來(lái)完成加解密，但是又避免了密鑰傳輸，RSA算法的公鑰是公開的，使用公鑰加密的信息，必須使用對(duì)應(yīng)的私鑰才能解密。

3. RSA算法

RSA算法可以說(shuō)是地球上最重要的算法之一，是數(shù)據(jù)通信和網(wǎng)絡(luò)安全的基石。

3.1 算法作者

RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。

當(dāng)時(shí)他們?nèi)硕荚诼槭±砉W(xué)院工作，RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的。

RSA算法密鑰越長(zhǎng)越難破解，根據(jù)相關(guān)文獻(xiàn)，目前被破解的最長(zhǎng)RSA密鑰是768個(gè)二進(jìn)制位。一般認(rèn)為，1024位的RSA密鑰基本安全，2048位的密鑰極其安全，RSA算法目前支持4096位長(zhǎng)度。

密鑰長(zhǎng)度和加解密的時(shí)間是成正比的，因此我們需要根據(jù)自己的場(chǎng)景來(lái)選擇密鑰長(zhǎng)度，不必追求一味長(zhǎng)密鑰。

3.2 算法過(guò)程

RSA算法的本質(zhì)就是數(shù)學(xué)，公鑰和私鑰是數(shù)學(xué)上關(guān)聯(lián)的，無(wú)須直接傳遞。

算法過(guò)程包括：密鑰生成、密鑰加解密。

3.2.1 密鑰生成

RSA算法的密鑰是成對(duì)的，公鑰加密私鑰解密，來(lái)看下這對(duì)密鑰是如何被計(jì)算出來(lái)的。

• 1.隨機(jī)選擇兩個(gè)質(zhì)數(shù)P和Q

我們選擇P=61，Q=53，計(jì)算PQ的乘積N=PQ=61*53=3233，將N轉(zhuǎn)換為二進(jìn)制:110010100001，N的二進(jìn)制長(zhǎng)度是12，也就是密鑰長(zhǎng)度為12。

本文只是闡述算法原理，在實(shí)際中密鑰長(zhǎng)度在1024位以上才安全，12位基本上就是個(gè)演示。

• 2.求N的歐拉函數(shù)值M

歐拉函數(shù)的定義：任意給定正整數(shù)n，請(qǐng)問(wèn)在小于等于n的正整數(shù)之中，有多少個(gè)與n構(gòu)成互質(zhì)關(guān)系？

歐拉函數(shù)有個(gè)通用的計(jì)算公式：

要證明歐拉函數(shù)需要分為很多種情況，特別地，當(dāng)n是質(zhì)數(shù)時(shí)會(huì)出現(xiàn)一些特殊的情況。

直接來(lái)個(gè)結(jié)論:

a. 如果k是質(zhì)數(shù)，則φ(k) = k-1;
b.如果 n = P * Q，P 與 Q 均為質(zhì)數(shù)，則 φ(n) = φ(P * Q)= φ(P)φ(Q) = (P - 1)(Q - 1) 。

P=61、Q=53 則N=3233，那么N的歐拉函數(shù)記為M=(P-1)*(N-1) = 60*52=3120

• 3.找一個(gè)與M互素的整數(shù)E
  M和E之間除了1以外沒(méi)有公約數(shù)(互質(zhì))且E<M，我們隨機(jī)選擇E為17。

• 4.找一個(gè)整數(shù)D，滿足如下關(guān)系：
  (E*D) mod M = 1，換句話說(shuō)E和D的乘積除以M的余數(shù)為1，這里有一個(gè)術(shù)語(yǔ)-模逆元，也就是指有一個(gè)整數(shù)d，可以使得ed被φ(n)除的余數(shù)為1。
  等價(jià)于 如下計(jì)算過(guò)程：

當(dāng)E=17，M=3120，K=1，2，3...時(shí)，
17*D - K*M = 1，求解這個(gè)方程找到一組滿足關(guān)系的D和K即可，可證其中一組為(D,K)=(2753,15)。

綜上所述，我們找到了通過(guò)隨機(jī)選擇的互質(zhì)的P和Q計(jì)算得到N、M、E、D，我們把這些數(shù)字分為兩組：(E,N)和(D,N)分別為公鑰組和私鑰組，E是公鑰、D是私鑰。

在本例中公鑰組為(E,N)=(17,3233)，私鑰組(D,N)=(2753,3233)，接下來(lái)我們將使用這對(duì)密鑰進(jìn)行加解密。

3.2.1 加密過(guò)程

由于RSA算法本質(zhì)是數(shù)字的運(yùn)算，因此我們?cè)趯?duì)字符串進(jìn)行加密時(shí)需要先將字符串?dāng)?shù)值化，可以借助ascii碼、unicode編碼、utf-8編碼等將字符串轉(zhuǎn)換為數(shù)字。

需要特別注意轉(zhuǎn)換后的數(shù)字X需要小于密鑰組中的N，如果字符串轉(zhuǎn)換后的數(shù)字大于N則需要進(jìn)行拆分，這可能也是在數(shù)據(jù)量大時(shí)我們使用對(duì)稱加密算法來(lái)加密內(nèi)容，用非對(duì)稱加密算法來(lái)加密密鑰的原因吧。

加密過(guò)程滿足：

X^E mod N = Y
其中X為明文，E為公鑰，N為大整數(shù)，Y為密文，mod取余運(yùn)算。

3.2.3 解密過(guò)程

我們獲得密文Y后，開始解密，過(guò)程滿足：

Y^D mod N = X
其中Y為密文，D為私鑰，N為大整數(shù)，X為明文，mod取余運(yùn)算。

上述的加密和解密過(guò)程涉及到了費(fèi)爾馬小定理。

3.2.4 歐拉定理和費(fèi)爾馬小定理

這塊有點(diǎn)晦澀，但是確實(shí)RSA算法的核心部分，簡(jiǎn)單看下吧：

費(fèi)爾馬小定理給出了素?cái)?shù)檢測(cè)性質(zhì)，歐拉對(duì)其進(jìn)行了證明，也就是費(fèi)馬-歐拉定理。

3.3 RSA算法可靠性分析

經(jīng)過(guò)上面的密鑰生成、加解密過(guò)程，我們難免要問(wèn)：RSA算法可靠嗎？通過(guò)公鑰組(E,N)能否推導(dǎo)出私鑰D呢？

來(lái)梳理一下：

• 由于ed≡1 (mod φ(N))，只有知道e和φ(N)，才能算出d，e是公鑰匙，所以需要知道φ(N)就可以。

• 根據(jù)歐拉函數(shù) φ(N)=(P-1)(Q-1)，只有知道P和Q，才能算出φ(N)。

• N=pq，只有將N進(jìn)行因數(shù)分解，才能算出P和Q。

所以，如果大數(shù)N可以被因數(shù)分解，私鑰D就可以算出，從而破解密文。

3.5 大整數(shù)因數(shù)分解

大整數(shù)的因數(shù)分解是極其困難的，屬于NPC問(wèn)題，除了暴力破解沒(méi)有很好的解決方案，目前人類分解的最大長(zhǎng)度的二進(jìn)制數(shù)為768位，1024位的長(zhǎng)度目前尚未破解，因此1024長(zhǎng)度的二進(jìn)制密鑰是安全的。

所以RSA算法的安全性取決于大整數(shù)分解的難度，目前RSA算法可以支持4096位密鑰長(zhǎng)度，分解難度超乎想象，即使借助于量子計(jì)算機(jī)難度和時(shí)間都是非常非常大的。

4. 總結(jié)

本文從對(duì)稱加密算法傳遞密鑰安全性為起點(diǎn)，說(shuō)到迪菲-赫爾曼算法進(jìn)行密鑰交換協(xié)商，該算法為RSA算法的公鑰和私鑰提供了靈感。

麻省理工的三位數(shù)學(xué)家在歐拉定理&費(fèi)爾馬定理等等一些數(shù)學(xué)定理的基礎(chǔ)上創(chuàng)造了偉大的RSA非對(duì)稱加密算法。

RSA算法的安全性取決于大數(shù)質(zhì)因數(shù)分解的難度，目前而言1024位二進(jìn)制長(zhǎng)度的密鑰人類都沒(méi)有破解，為了安全性考慮可使用2048位長(zhǎng)度的RSA密鑰進(jìn)行加密。

確實(shí)是燒腦的硬核內(nèi)容啊，不由得感嘆素?cái)?shù)真是個(gè)神奇的東西，段位有限只能拋磚引玉，到此為止啦！

感謝各位的傾情閱讀，如果有問(wèn)題請(qǐng)?zhí)砑哟蟀孜⑿牛?span style="color: rgb(255, 76, 65);">baymax9901