白永祥，何 林，陳逸懷

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

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

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

1 公鑰密碼算法理論

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

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

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

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

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

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

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

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

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

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

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

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)使用一對配對的密鑰實施加密和解密，由于公鑰密碼系統(tǒng)運算量大，加密和解密速度慢，使用混合加密方法，即使用對稱密碼算法對消息進行加密和解密，使用公鑰密碼算法對會話密鑰進行分發(fā)。

2）數(shù)字簽名

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

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

2 RSA密碼算法理論

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

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

RSA 密碼算法可以假設(shè)為一個八元組[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兩個大素數(shù)之積，且p、q位數(shù)不小于100，{(e,N),(d,N)}∈K且e≠d，同時滿足ed≡1(modφ(N))，φ(N)=(p-1)(q-1)。

2.1 RSA密鑰對生成

1）Bob 隨機生成兩個大小相當?shù)拇笏財?shù)p和q，且p≠q；

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

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

4）使用擴展歐幾里德算法，計算出d∈N,且1

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

2.2 RSA加密算法

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

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

2）Bob 通過加密算法對消息m進行加密，c≡me(modn)；

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

2.3 RSA解密算法

當Alice 接收到加密消息c時，使用m≡cd(modn)進行計算。

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

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

1）初始化階段

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

2）簽 名

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

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

3）驗 證

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

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

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

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

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

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

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

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

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

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

3.2.1 生成密鑰對

使用非對稱密碼算法時，Bob 首先要隨機生成一對密鑰，下面代碼是Python 的RSA 密鑰對生成過程，公鑰存儲在文件Bob_public_key.pem 中，私鑰存儲在文件Bob_private_key.pem 中，程序代碼如下：

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

Alice要向Bob發(fā)送加密的數(shù)據(jù)，假設(shè)Alice已經(jīng)獲得Bob的公鑰，且存儲在一個名為Bob_public_key.pem的文件中。因為希望能夠加密任意長度的數(shù)據(jù)，一般使用混合加密方法，即使用AES 加密消息明文，再用RSA 加密隨機生成的會話密鑰，使用EAX 模式[13]來檢測未經(jīng)授權(quán)的修改。過程如下：

3.2.3 RSA解密算法

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

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

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

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

假設(shè)明文為：

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

4 RSA算法安全性分析

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

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

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

表1 因子分解問題的進展情況[3]

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

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

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

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

4.3 量子計算機攻擊

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

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

4.4 中間人攻擊

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

5 結(jié)束語

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