基于RSA 算法特性的安全性研究

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

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

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

1 RSA算法回顧

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

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

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

RSA 算法流程描述如下：

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

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

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

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

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

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

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

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

加密階段：

解密階段：

1.2 RSA算法的證明

1）若(m,n)=1，則(m,p)=1 且(m,q)=1，由步驟4 和步驟5 計(jì)算，存在一個(gè)整數(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é)者，無(wú)不認(rèn)為將大數(shù)合成進(jìn)行因數(shù)分解[15]才是唯一破解的途徑，卻不知該系統(tǒng)所存在的缺陷，進(jìn)行密碼分析也是另一種破密方案。從數(shù)學(xué)發(fā)展的角度來(lái)看，因數(shù)分解具有NP 特性。如果因數(shù)分解技術(shù)有突破性進(jìn)展，除直接對(duì)RSA 造成嚴(yán)重性威脅外，更可能導(dǎo)致該系統(tǒng)的整體瓦解。

符號(hào)表示如下：

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

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

表1 加密階段過(guò)程表

表2 解密階段過(guò)程表

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

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

3 算法分析與破密方法

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

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

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

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

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

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

步驟1：計(jì)算y值，并滿(mǎn)足方程式（8）的條件，即：

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

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

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

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

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

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

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

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

再驗(yàn)證方程式（10）φ(r)的計(jì)算結(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，此處容易驗(yàn)證227×223=50 621 便是RSA 模數(shù)n。

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

表3 實(shí)驗(yàn)數(shù)據(jù)表

4 結(jié)論

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

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