唐 蓉，周瑜平，葉小鶯，戴辛玥

（1.重慶市疾病預(yù)防控制中心科技信息處，重慶 400042；2.廣東東軟學(xué)院計算機學(xué)院，廣東佛山 528225）

科技進步改變了人們的生活，使人們對通信網(wǎng)絡(luò)的依賴越來越強。通信網(wǎng)絡(luò)極大地縮短了溝通距離，也大幅提升了信息溝通的便捷性。然而，這種便捷性也衍生了一系列安全性問題，劉俊杰等[1]認(rèn)為隨著無線通信的快速發(fā)展和普及，通信的安全問題成為該領(lǐng)域的研究重點。季佳華等[2]認(rèn)為對通信網(wǎng)絡(luò)信息進行加密操作可以更好地防范網(wǎng)絡(luò)入侵和攻擊。以傳染病防控領(lǐng)域為例，隨著我國各地智慧化預(yù)警多點觸發(fā)機制和多渠道監(jiān)測預(yù)警機制的建立，此類信息系統(tǒng)包含了大量的隱私數(shù)據(jù)、敏感信息的應(yīng)用場景，并由原來的醫(yī)療機構(gòu)及管理部門轉(zhuǎn)向科學(xué)研究、互聯(lián)互通、數(shù)據(jù)匯聚、移動應(yīng)用等領(lǐng)域，擴大了個人隱私信息類型、分布場景及泄露渠道[3]，給現(xiàn)行加密系統(tǒng)帶來較大挑戰(zhàn)，亟需更加可靠的技術(shù)手段實現(xiàn)健康數(shù)據(jù)的安全和保密[4-5]。RSA 算法作為當(dāng)前非對稱密碼領(lǐng)域最為重要的算法之一，其安全性基礎(chǔ)與極大整數(shù)做因數(shù)分解的難度密切相關(guān)[6]，被ISO 推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)，廣泛應(yīng)用于醫(yī)療健康[7]、電子商務(wù)[8-9]、金融[10]、公共服務(wù)[11-12]等領(lǐng)域。其因易于理解和操作，能同時用于加密和數(shù)字簽名，被普遍認(rèn)為是最優(yōu)秀的公鑰方案之一。但是，隨著硬件、軟件技術(shù)的進步和計算能力的大幅提升，RSA 算法真如大家所說的那樣安全嗎？是否隱藏著潛在風(fēng)險？基于此，該文從RSA 算法特性研究視角出發(fā)，探討了RSA 算法的安全性問題。

1 RSA算法回顧

在RSA 算法[13-14]中，要求任意選擇兩個不同的質(zhì)數(shù)p和q，然后構(gòu)成一個合成數(shù)n，這個合成數(shù)就是p與q的乘積。當(dāng)給定一個合成數(shù)后，驗證特定質(zhì)數(shù)是否是該合成數(shù)的因數(shù)是輕而易舉的，然而如何將該合成數(shù)分解成特定的因數(shù)，則是一個非常困難的問題。隨著質(zhì)數(shù)的增大，質(zhì)數(shù)的乘積也隨之增大，同時分解該合成數(shù)為質(zhì)數(shù)的難度也增加。從理論和實踐證明，將大數(shù)分解為因數(shù)的方法通常都需要指數(shù)級時間。但是，當(dāng)前計算機技術(shù)的高速發(fā)展，對不少加密系統(tǒng)造成了較大威脅，另一方面在數(shù)學(xué)研究領(lǐng)域所取得的突破，越來越多的密碼分析工具相繼問世，無疑對信息安全的防護更是雪上加霜。

作為非對稱公開加密體制的代表，該文研究證實，RSA 算法存在一定缺陷，對于RSA 系統(tǒng)的解密過程，解密密鑰實際上是冗余的。簡而言之，加密和解密過程只需要加密密鑰來完成，而不是單獨一組不同的加密密鑰和解密密鑰?；诖藛栴}，該系統(tǒng)明顯不符合非對稱密鑰體制的基本要求；且只由加密密鑰即可完成加密、解密過程，而加密密鑰又是公開的，這樣將破壞整個系統(tǒng)的可靠性與安全性。另外，系統(tǒng)公開加密算法解密密鑰原理是唯一的，該研究指出RSA 系統(tǒng)也不符合了這一基本要求。非線性特性要求，任意一個公開加密算法系統(tǒng)需要構(gòu)建在非線性變換的基礎(chǔ)上，意味著除了加、解密的過程需要是非線性外，對相應(yīng)變換結(jié)果也需要達到非線性要求。雖然RSA 使用了大質(zhì)數(shù)運算，整體效果是非線性的，實際上對于單一的加密算法具有線性特征。

1.1 RSA加密與解密算法的步驟

RSA 算法流程描述如下：

步驟1：首先產(chǎn)生兩個大質(zhì)數(shù)p及q，建議p或q的長度至少為1 024 比特以上。

步驟2：計算n=pq，公開參數(shù)n，不可公開p及q。

步驟3：計算歐拉函數(shù)φ(n)=(p-1)(q-1)。

步驟4：隨機選擇一個整數(shù)e，需滿足條件(e,φ(n))=1。

步驟5：求得整數(shù)d，使：

整數(shù)d存在，因此e與φ(n)互質(zhì)。

步驟6：公布n和e，但是d需要保密。

只要n足夠大，即使已知n和e，卻很難從中得知p和q，因此d就無法逆推得到。

加密階段：

解密階段：

1.2 RSA算法的證明

1）若(m,n)=1，則(m,p)=1 且(m,q)=1，由步驟4 和步驟5 計算，存在一個整數(shù)b，使

若mp-1≡1(modp) 且mq-1≡1(modq)，則(p,q)=1，故得cd≡m(modn)。

2）若(m,n)≠1，因m＜n，使p|m且q|m（或q|m且p|m），

因q|(med-m)，從p|m求得p|med-m，使其n|(med-m)。

因此，cd≡m(modn)。

同理可證如q|m且p|m仍有cd≡m(modn)。

2 RSA算法特性分析

知曉RSA 加密系統(tǒng)的學(xué)者，無不認(rèn)為將大數(shù)合成進行因數(shù)分解[15]才是唯一破解的途徑，卻不知該系統(tǒng)所存在的缺陷，進行密碼分析也是另一種破密方案。從數(shù)學(xué)發(fā)展的角度來看，因數(shù)分解具有NP 特性。如果因數(shù)分解技術(shù)有突破性進展，除直接對RSA 造成嚴(yán)重性威脅外，更可能導(dǎo)致該系統(tǒng)的整體瓦解。

符號表示如下：

m：message，亦即明文（Plaintext）

d：私鑰（Private Key）

e：公鑰（Public Key）

n：模數(shù)，即p與q的乘積

c：密文（Cipher），加密后的結(jié)果

令m=3 803，e=29，d=2 869，n=5 353(p×q=101×53)，則c=2 955。

加密階段：

解密階段：

由表1 可知，明文經(jīng)由公開密鑰加密后，即為密文。公開密鑰和密文是網(wǎng)絡(luò)上公開易得知的參數(shù)，由密文逆向推導(dǎo)為明文，很難直接計算求得私鑰。然而將密文重復(fù)加密數(shù)次之后，又回到原點，此一特性突顯解密私鑰是冗余的，另一方面，顯示加密至解密之間的過程具有線性特征。由表2 可見解密至加密的過程，實際上是加密的逆序，因此，該系統(tǒng)確實存在明文密文之間的遞歸關(guān)系。

由方程式（7）和（8），以及表1 和表2 不難觀察到，明文3 803 只要連序加密30 次，便能返回原本的值；反之，密文2 955 也是連續(xù)解密30 次便還原成為初始的數(shù)值，代表明文與密文之間存在一對一的映射關(guān)系，公鑰e與私鑰d雖然是配對關(guān)系，縱使沒有密鑰，密文連續(xù)加密k次后，也能還原成明文，所以不論是明文空間或是密文空間，這兩者都是封閉的空間。封閉的空間即代表有限的元素，有限的周期，簡言之，即多項式時間內(nèi)的求解問題。

表1 加密階段過程表

表2 解密階段過程表

圖1 明文密文映射關(guān)系圖

Simmons 及Norris[16]首先證明RSA 算法p-1 和q-1 的最大公因數(shù)很小時，即不需要因數(shù)分解情況下容易被破解。該研究加密與解密階段通過過程分析，直接觀察明文和密文彼此變換的情形。

3 算法分析與破密方法

該文已探討了明文和密文之間的聯(lián)系是映射封閉空間的，現(xiàn)在將用逆推法，進行因數(shù)分解，以求得質(zhì)數(shù)p和q的值。其步驟如下：

m：明文或未加密的信息。

n：模數(shù)為兩質(zhì)數(shù)p和q的乘積（p和q不公開）。

y：等同于φ(n)的值，目的在計算循環(huán)周期。

F：代表模數(shù)n除以y值后，取整數(shù)的值：

φ(r)∶φ(r)=(F·y)

步驟1：計算y值，并滿足方程式（8）的條件，即：

因mφ(n)=m(p-1)(q-1)≡1(modn)，若my≡1(modn)，則有φ(n)|y的關(guān)系。

步驟2：計算F值，F(xiàn)=(ny)，模數(shù)n整除y后所獲得的數(shù)據(jù)，也可表示為F=。

步驟3：計算φ(r)=(F·y)，φ(r)為兩數(shù)及y的乘積。

步驟4：比較φ(r)=φ(n)，若φ(r)=φ(n)，則進行φ(r)之因數(shù)分解，若φ(r)≠φ(n)，則調(diào)整F值（上下加減一以計算φ(r)）。

例：假設(shè)m=184 且n=50 621，計算y,184y=1(mod 50 621)，得y=678。

計算F，F(xiàn)=(50 621/678)=74。

求φ(r)，φ(r)=74×678=50 172。

比較φ(r) 是否等于φ(n)，通過方程式（1）及（2）得知，mφ(n)≡1(modn)。

再驗證方程式（10）φ(r)的計算結(jié)果，18450172mod 50 621=1。

已知φ(r)為50 172，分解其因數(shù)φ(r)得結(jié)果，即50 172=22×3×37×113。

再由方程式φ(n)=(p-1)(q-1)推論，便能獲得p=(2×113+1)=227 和q=(2×3×37)+1=223，此處容易驗證227×223=50 621 便是RSA 模數(shù)n。

方程式（9）以費馬小定理為基礎(chǔ)，目的著重于解離散對數(shù)的問題，將方程式φ(r)=(F·y)所計算的值進行分解，即為因數(shù)分解。該節(jié)取樣148 932 個數(shù)據(jù)，質(zhì)數(shù)選定（2＜p，q＜1 999 979）區(qū)間，正確數(shù)為148 907 個，錯誤數(shù)為25 個，正確率為99.983 1%。實驗數(shù)據(jù)見表3。

表3 實驗數(shù)據(jù)表

4 結(jié)論

該文通過將密文重復(fù)加密數(shù)次之后，顯示明文與密文之間的映射關(guān)系，即解密實際上是加密的逆序。經(jīng)過實驗論證，該系統(tǒng)確實存在明文密文之間的遞歸關(guān)系，又通過逆推法，進行因數(shù)分解，正確率達99.983 1%，指出當(dāng)前RSA 密碼系統(tǒng)所存在的安全隱患。

研究初步采用軟件計算的模式，用時間換取成本，在有效時間內(nèi)達到解離散對數(shù)與因數(shù)分解的雙重效果。另一方面，雖然采用簡易的個人電腦實現(xiàn)了高位數(shù)的計算能力，然而當(dāng)前樣本數(shù)量仍然不足，希望增加樣本數(shù)量，獲得更加準(zhǔn)確的數(shù)值。下一步將以數(shù)論作為基礎(chǔ)，來完成相應(yīng)的演算論證。