基于Python 的RSA 密碼算法的設(shè)計(jì)與實(shí)現(xiàn)

白永祥，何 林，陳逸懷

（1.天津職業(yè)技術(shù)師范大學(xué)自動(dòng)化與電氣工程學(xué)院，天津 300222；2.天津市信息傳感與智能控制重點(diǎn)實(shí)驗(yàn)室，天津 300222；3.渭南職業(yè)技術(shù)學(xué)院，陜西 渭南 714000）

現(xiàn)代密碼學(xué)體系加密算法一般分為兩種：對(duì)稱加密算法和非對(duì)稱加密算法（亦稱公鑰加密算法）。所謂對(duì)稱加密就是通信雙方加密和解密消息時(shí)使用相同的密鑰，對(duì)稱密碼算法的優(yōu)點(diǎn)是加解密運(yùn)算速度較快，適用于處理大批量消息處理，缺點(diǎn)是很難解決密鑰分發(fā)的安全性和數(shù)字簽名等問題。在非對(duì)稱加密算法中，發(fā)送方和接收方使用不同的密鑰，發(fā)送方使用接收方的公鑰對(duì)明文進(jìn)行加密，接收方使用自己的私鑰對(duì)密文進(jìn)行解密，從而獲得明文內(nèi)容，因公鑰密碼算法運(yùn)算速度較慢，所以適用于處理密鑰分發(fā)和數(shù)字簽名等問題，一般在實(shí)際應(yīng)用中，往往會(huì)將兩者結(jié)合起來(lái)使用，即混合密碼算法，使用非對(duì)稱加密算法對(duì)密鑰進(jìn)行加密，對(duì)稱加密算法加密內(nèi)容較多的明文。

RSA 密碼體制是目前較流行的一種公鑰密碼算法。1977 年由Rivest、Shamir、和Adleman 3 位專家提出并于1978 年首次發(fā)表的算法，人們習(xí)慣稱其為RSA 密碼算法[1]。RSA 算法自誕生之日起就受到廣泛使用，早期的RSA 算法采用C、C++或者JAVA 實(shí)現(xiàn)，實(shí)現(xiàn)起來(lái)比較繁瑣。近來(lái)年，隨著Python 語(yǔ)言的盛行，尤其是大量開發(fā)軟件包的出現(xiàn)，使得Python 語(yǔ)言應(yīng)用領(lǐng)域不斷擴(kuò)大。Python 是上世紀(jì)80 年代末由Guido van Rossum 創(chuàng)建的，它是一種解釋性的高級(jí)通用編程語(yǔ)言，具有動(dòng)態(tài)類型系統(tǒng)和自動(dòng)內(nèi)存管理功能，并支持多種編程范例，包括面向?qū)ο蟆⒚钍健⒑瘮?shù)式和過(guò)程式，擁有一個(gè)大型的標(biāo)準(zhǔn)庫(kù)。目前，Python 3.X 是主流版本，PyCrypto 是Python 下的一個(gè)密碼軟件包，但已經(jīng)超過(guò)3 年無(wú)人維護(hù)，因此Github上的開發(fā)者們呼吁不要再使用PyCrypto，而應(yīng)該使用PyCryptodome 代 替PyCrypto。PyCryptodome 是 一個(gè)包含低級(jí)密碼原語(yǔ)的自包含包，對(duì)于要使用Python 加密庫(kù)的新項(xiàng)目，建議開發(fā)者使用PyCryptodome 或者Cryptography。該文正是基于此軟件包，針對(duì)RSA 密碼體制進(jìn)行了設(shè)計(jì)和實(shí)現(xiàn)。

1 公鑰密碼算法理論

公鑰密碼學(xué)的提出是為了解決對(duì)稱密碼學(xué)中密鑰分配和數(shù)字簽名兩個(gè)難題。1976 年Diffe 和Hellman 首次公開提出了公鑰密碼學(xué)的概念[2]，并設(shè)計(jì)了在不安全公共網(wǎng)絡(luò)上進(jìn)行安全傳輸密鑰的協(xié)議問題。公鑰密碼學(xué)系統(tǒng)的安全性是基于單向陷門函數(shù)的安全性,所謂單向陷門函數(shù)就是正向計(jì)算函數(shù)值很容易，在缺少附加信息時(shí)計(jì)算函數(shù)的逆是不可行的，一般滿足下列條件[3]：

1）若k和X已知，則可計(jì)算Y=fk(X)；

2）若k和Y已知，則可計(jì)算X=fk(Y)；

3）若Y已知，但k未知，則計(jì)算出不可行。

1.1 公鑰密碼體系的實(shí)現(xiàn)過(guò)程

從集合論角度看，一個(gè)公鑰密碼系統(tǒng)可以定義為一個(gè)九元組集合：

1）M為明文集合，或稱作明文空間；

2）C為密文集合，或稱作密文空間；

3）K為密鑰集合，或稱作密鑰空間；

4）m∈M，是明文集合的一個(gè)子集；

5）X∈C，是密文集合的一個(gè)子集；

6）e為公鑰，d為私鑰，(e,d)∈K，且e≠d；

7）E為加密函數(shù)，D為解密函數(shù)；

由于m∈M，X∈C，使用公鑰ek，加密如下：

8）D為解密函數(shù)，則：

公鑰密碼系統(tǒng)工作原理如圖1 所示[4]。

圖1 公鑰密碼系統(tǒng)工作原理

1.2 公鑰密碼體制的應(yīng)用

1）加密與解密

公鑰密碼系統(tǒng)使用一對(duì)配對(duì)的密鑰實(shí)施加密和解密，由于公鑰密碼系統(tǒng)運(yùn)算量大，加密和解密速度慢，使用混合加密方法，即使用對(duì)稱密碼算法對(duì)消息進(jìn)行加密和解密，使用公鑰密碼算法對(duì)會(huì)話密鑰進(jìn)行分發(fā)。

2）數(shù)字簽名

當(dāng)在法律文件、合同書或私人信件上簽名時(shí)，是通過(guò)手寫簽名來(lái)證明自己的身份。有時(shí)為了防止犯罪分子偽造簽名，還需要一些驗(yàn)證程序，例如，銷售人員通過(guò)與信用卡本身的簽名進(jìn)行比較來(lái)驗(yàn)證信用卡上的簽名。在這里可以看到的是兩個(gè)階段的簽名和驗(yàn)證過(guò)程，數(shù)字簽名也是如此，它是通過(guò)網(wǎng)絡(luò)進(jìn)行加密的一種電子簽名[5]。

通常數(shù)字簽名方案必須滿足兩個(gè)安全標(biāo)準(zhǔn)：如果Alice 用Sigk(m)來(lái)簽署一條消息m，那么接收方檢索這對(duì)(m,Sigk(m))在計(jì)算上一定是不可行的；其次，如果Bob 從Alice 那里收到Sigk(m)=c，那 么Bob 必須能夠使用Verk(c)來(lái)驗(yàn)證這是Alice 的簽名，稱為可信屬性[6]。數(shù)字簽名方案還需要滿足另外兩個(gè)屬性：第一，消息被傳送后，Bob 和Darth都不能改變m，稱為不可改變屬性；第二，Bob 必須能夠立即檢測(cè)到m是否被重新發(fā)送，稱為不可重用性[7]。

2 RSA密碼算法理論

RSA 密碼體制屬于分組密碼，是目前最流行、應(yīng)用最廣泛的公鑰密碼系統(tǒng)。假設(shè)Bob 向Alice 發(fā)送消息，RSA 公鑰密碼系統(tǒng)工作流程如圖2 所示[4]。

圖2 RSA公鑰密碼算法工作流程

RSA 密碼算法可以假設(shè)為一個(gè)八元組[8-9]：{M，C，K，e，d，N，E，D}；1）M為明文空間；2）C為密文空間；3）K為密鑰空間；4）e為公鑰，d為私鑰；5）E為加密函數(shù)；6）D為解密函數(shù)；7）N為p和q兩個(gè)大素?cái)?shù)之積，且p、q位數(shù)不小于100，{(e,N),(d,N)}∈K且e≠d，同時(shí)滿足ed≡1(modφ(N))，φ(N)=(p-1)(q-1)。

2.1 RSA密鑰對(duì)生成

1）Bob 隨機(jī)生成兩個(gè)大小相當(dāng)?shù)拇笏財(cái)?shù)p和q，且p≠q；

2）計(jì)算n=pq，φ(n)=(p-1)(q-1)，這里的整數(shù)n是RSA 算法的模；

3）Bob 再選擇一個(gè)隨機(jī)數(shù)e∈N，這樣1

4）使用擴(kuò)展歐幾里德算法，計(jì)算出d∈N,且1

5）Bob 在一些公共數(shù)據(jù)庫(kù)中發(fā)布(n,e)，但不發(fā)布d、p、q和φ(n)，因此，Bob 的公鑰為(n,e)，私鑰為d,或者被稱為它的解密指數(shù)。

2.2 RSA加密算法

假設(shè)明文消息m∈M是數(shù)值形式，且m

1）Bob 通過(guò)公共數(shù)據(jù)庫(kù)獲得Alice 的公鑰(n,e)；

2）Bob 通過(guò)加密算法對(duì)消息m進(jìn)行加密，c≡me(modn)；

3）Bob 發(fā)送c∈X給Alice。

2.3 RSA解密算法

當(dāng)Alice 接收到加密消息c時(shí)，使用m≡cd(modn)進(jìn)行計(jì)算。

2.4 RSA數(shù)字簽名算法

RSA 的主要應(yīng)用之一是數(shù)字簽名，在這里，數(shù)字簽名是一種將信息綁定到實(shí)體的機(jī)制，并且包含一個(gè)驗(yàn)證過(guò)程[9]。討論的第一個(gè)簽名方案是消息恢復(fù)方案，這意味著發(fā)送的消息不需要作為驗(yàn)證算法的輸入，在這種情況下，原始消息可以從簽名本身恢復(fù)[10]。

1）初始化階段

Alice 發(fā)送消息給Bob，從RSA 密鑰空間k={n,p,q,e,d}選擇簽名所需要的各種參數(shù)。

2）簽 名

Alice 的私有數(shù)字簽名Sigk由下式生成：

Verk是它的公共驗(yàn)證算法，然后它發(fā)送(m,c)給Bob。

3）驗(yàn) 證

Bob 獲得Alice 的公鑰及簽名信息(e,Verk)，計(jì)算Verk(m,c)，當(dāng)m≡ce(modn)時(shí)，Verk(m,c)正好是1，在這種情況下，Bob 接受簽名，否則拒絕它。

3 基于PyCryptodome的RSA設(shè)計(jì)與實(shí)現(xiàn)

PyCryptodome 是一個(gè)包含底層密碼原語(yǔ)的Python 包，該文基于Python3.7 以及PyCryptodome 密碼包,軟件環(huán)境為Win7、Pycharm。

3.1 PyCryptodome庫(kù)相關(guān)函數(shù)

1）Cryptodome.Cipher：包含保護(hù)數(shù)據(jù)機(jī)密性的算法，有3 種加密算法：對(duì)稱加密、非對(duì)稱加密和混合加密[11]；

2）Cryptodome.Random：返回長(zhǎng)度為N的隨機(jī)字節(jié)字符串；

3）Cryptodome.PublicKey：系統(tǒng)定義了一個(gè)密鑰對(duì)，其中一個(gè)是機(jī)密的(私鑰)，另一個(gè)是可以公開的（公鑰）；

4）Cryptodome.Hash：哈希函數(shù)，以任意二進(jìn)制字符串為輸入，生成隨機(jī)的固定長(zhǎng)度輸出，又稱為消息指紋或哈希值[12]；

5）Cryptodome.Signature：數(shù)字簽名的算法，用于保證完整性和不可否認(rèn)性。

3.2 RSA加密算法設(shè)計(jì)

3.2.1 生成密鑰對(duì)

使用非對(duì)稱密碼算法時(shí)，Bob 首先要隨機(jī)生成一對(duì)密鑰，下面代碼是Python 的RSA 密鑰對(duì)生成過(guò)程，公鑰存儲(chǔ)在文件Bob_public_key.pem 中，私鑰存儲(chǔ)在文件Bob_private_key.pem 中，程序代碼如下：

3.2.2 RSA數(shù)據(jù)加密

Alice要向Bob發(fā)送加密的數(shù)據(jù)，假設(shè)Alice已經(jīng)獲得Bob的公鑰，且存儲(chǔ)在一個(gè)名為Bob_public_key.pem的文件中。因?yàn)橄Ｍ軌蚣用苋我忾L(zhǎng)度的數(shù)據(jù)，一般使用混合加密方法，即使用AES 加密消息明文，再用RSA 加密隨機(jī)生成的會(huì)話密鑰，使用EAX 模式[13]來(lái)檢測(cè)未經(jīng)授權(quán)的修改。過(guò)程如下：

3.2.3 RSA解密算法

Bob 首先使用自己的私鑰解密，獲取會(huì)話密鑰，然后進(jìn)行密文解密。具體算法如下：

3.2.4 RSA數(shù)據(jù)簽名

發(fā)送者Bob 使用自己的私鑰對(duì)消息進(jìn)行簽名,接收者Alice 使用Bob 的公鑰對(duì)簽名信息和完整性進(jìn)行解密及真實(shí)性驗(yàn)證[5]。

3.3 消息內(nèi)容的AES加密與解密

假設(shè)明文為：

同理，接收方首先使用自己的私鑰解密并獲得對(duì)稱密鑰key，然后對(duì)密文Encrypt_text 解密獲得明文Message，這里不再贅述。

4 RSA算法安全性分析

無(wú)論設(shè)計(jì)的算法有多安全，攻擊者總會(huì)想辦法破解或繞過(guò)它們，每種算法都有其局限性，加密和破解永遠(yuǎn)是一對(duì)矛盾。RSA 當(dāng)然也不例外，有其弱點(diǎn)，從以下幾個(gè)方面對(duì)其安全性進(jìn)行分析。

4.1 大整數(shù)因子分解攻擊

RSA 密碼算法的安全性是基于大整數(shù)因子分解難題[14](The Integer Factorization Problem，IFP)，其中，p和q是兩個(gè)不同的大質(zhì)數(shù)，如果求出p和q，那么就可以通過(guò)ed≡1、φ(N)=(p-1)(q-1)等計(jì)算出私鑰d。也就是說(shuō)，任何能夠因式分解N的人員都可以通過(guò)計(jì)算C=Me的逆M≡C1/e(mod(p-1)(q-1))(modN)來(lái)破解RSA 密碼算法，即如果給出N的質(zhì)因數(shù)分解，那么RSA 算法問題可以在多項(xiàng)式時(shí)間內(nèi)求解。因子分解問題的進(jìn)展情況如表1 所示。

表1 因子分解問題的進(jìn)展情況[3]

最近的研究表明，破壞RSA 可能比分解更容易，但也有證據(jù)表明，破壞RSA 可能與分解一樣困難，因此，破壞RSA 最直接的方法是因式分解RSA 模數(shù)N，常見的關(guān)于RSA 整數(shù)因子分解的方法有費(fèi)爾馬因子分解、二次篩攻擊等。

4.2 離散對(duì)數(shù)攻擊法

美國(guó)普渡大學(xué)計(jì)算機(jī)科學(xué)教授Samuel 說(shuō)：“如果能很快地計(jì)算出離散對(duì)數(shù)，也就是說(shuō)，如果能在一個(gè)很大的有限域中解出方程ax=b，許多密碼系統(tǒng)就能被破解”[15]。離散對(duì)數(shù)計(jì)算問題[16]（Discrete Logarithm Problem，DLP）是計(jì)算數(shù)論、代數(shù)的基礎(chǔ)，也是公鑰密碼學(xué)研究的重要問題。一個(gè)離散對(duì)數(shù)問題符合式子[4]：

現(xiàn)代數(shù)學(xué)證明，DLP 在計(jì)算上是難以處理的，常見的密碼系統(tǒng)，如Diffie-Hellman 密鑰交換方案、ElGmmal 密碼系統(tǒng)[6]和數(shù)字簽名算法DSA 的安全性是基于DLP 的難處理性。因此，對(duì)于RSA 的因式攻擊來(lái)說(shuō)，離散對(duì)數(shù)攻擊也是所有基于DLP 密碼系統(tǒng)中最直接的攻擊。RSA 密碼系統(tǒng)是基于大整數(shù)因子分解的密碼系統(tǒng)，離散對(duì)數(shù)攻擊也是最直接的威脅。如果攻擊者掌握了一種有效的大整數(shù)因子分解方法，就能夠在多項(xiàng)式時(shí)間內(nèi)分解N=pq，并且計(jì)算d≡1/emod((p-1)(q-1))，從而計(jì)算C≡Md(modN)。

4.3 量子計(jì)算機(jī)攻擊

隨著量子計(jì)算的出現(xiàn)，計(jì)算機(jī)運(yùn)算速度得到了幾何級(jí)增長(zhǎng)，因此破解現(xiàn)代密碼體系也不是不可能，據(jù)估計(jì)，這類計(jì)算機(jī)的誕生還需要10 年甚至更長(zhǎng)時(shí)間[6]。2015 年8 月，美國(guó)國(guó)家安全局宣布，計(jì)劃在“不久的將來(lái)”過(guò)渡到一種新的密碼套件，可以抵抗量子攻擊[4]。

值得注意的是，以上所有的操作都可以由量子算法在量子計(jì)算機(jī)上有效執(zhí)行，而經(jīng)典算法不能在目前的電子計(jì)算機(jī)上有效執(zhí)行。在量子計(jì)算機(jī)上可以在多項(xiàng)式時(shí)間內(nèi)完全破解RSA，也可以在多項(xiàng)式時(shí)間內(nèi)完成IFP、DLP、ECDLP等問題的快速求解[17]。

4.4 中間人攻擊

以上針對(duì)RSA 攻擊的一個(gè)共同特點(diǎn)是它們都直接針對(duì)RSA 算法的弱點(diǎn)，然而，有大量的攻擊并不直接針對(duì)RSA 算法，也就是說(shuō)，不嘗試因式分解模N，這些攻擊稱為間接算法攻擊。比如中間人攻擊[4]，假設(shè)Bob 想和Alice 交流，但間諜Eve 截獲了它,然后，他可以用自己的公鑰替換附加在電子郵件中Bob 的公鑰，然后把它發(fā)給Alice。當(dāng)Alice 用假的公鑰加密回復(fù)郵件時(shí)，Eve 又會(huì)截獲消息并解密(因?yàn)锳lice 用間諜Eve 的公鑰加密了信息，而不是Bob 的公鑰)閱讀，然后Eve 用Bob 的實(shí)際公鑰對(duì)回復(fù)郵件重新加密并發(fā)送給Bob。同理，Eve 對(duì)Alice 發(fā)送給Bob 的任何信息也可做同樣的處理。

5 結(jié)束語(yǔ)

RSA 是目前使用廣泛的一種公鑰密碼系統(tǒng)，它的安全性基于大整數(shù)因子分解難題[8]。該算法已經(jīng)受了30 多年的攻擊，且生成密鑰長(zhǎng)度由以前的1 024位發(fā)展到現(xiàn)在的2 048 位和3 072 位[9]，因此對(duì)于當(dāng)前信息安全保密程序設(shè)計(jì)來(lái)說(shuō)，它被認(rèn)為是相當(dāng)安全的[18]。RSA 密碼系統(tǒng)可用于機(jī)密性(加密)和身份驗(yàn)證(數(shù)字簽名)，由于簽名和解密要比驗(yàn)證和加密慢得多，密碼強(qiáng)度主要與RSA 模數(shù)N的長(zhǎng)度有關(guān)，目前長(zhǎng)度是2 048 位，即256 字節(jié)，相當(dāng)安全。近年來(lái)，計(jì)算機(jī)語(yǔ)言發(fā)展很快，目前較流行的編程語(yǔ)言有C/C++、java、Go 及.NET 等。RSA 密碼算法都可以在這些語(yǔ)言環(huán)境中得到實(shí)現(xiàn)，2019 年11 月，編程語(yǔ)言流行指數(shù)（Popularity of Programming Language，PYPL）11 月份榜單發(fā)布，Python語(yǔ)言排名第一，首次超Java 語(yǔ)言[19]，這個(gè)當(dāng)然不是偶然的，主要是因?yàn)镻ython 語(yǔ)言簡(jiǎn)單易學(xué)，具有豐富的資源庫(kù)開源軟件，還有其他語(yǔ)言沒有的“粘合力”，尤其是與大數(shù)據(jù)、人工智能等的無(wú)縫結(jié)合[20]，所以，在Python 語(yǔ)言環(huán)境中實(shí)現(xiàn)密碼學(xué)編程是大勢(shì)所趨。