RSA與背包公鑰密碼算法的安全性分析.pdf

1、隨著計算機和網(wǎng)絡(luò)通信的快速發(fā)展,人們開始重視個人數(shù)字信息保護和各種服務(wù)的安全性,如保護個人秘密信息,防止消息篡改,保證通信雙方的公平性等。密碼學為這些服務(wù)的安全性提供了技術(shù),特別是公鑰密碼學,已成為當今社會信息安全技術(shù)的核心。
　　 1976年Diffie和Hellman在發(fā)表的論文《密碼學的新方向》中首次提出公鑰加密概念,是密碼學方向的一個重要里程碑,開啟了密碼學的新紀元。麻省理工學院的Rivest,Shamir和Adlema

2、n設(shè)計出第一個實際的公鑰密碼體制,稱為RSA算法,是迄今為止最著名的公鑰密碼算法之一,它可以同時用于數(shù)據(jù)加密和數(shù)字簽名。1978年,Merkle和Hellman提出了基于子集和問題的背包公鑰密碼算法-Merkle-Hellman密碼體制。此后,又有許多重要的公鑰密碼算法相繼被提出,如McEliece加密算法,Rabin加密算法,ElGamal加密與簽名算法,橢圓曲線密碼(ECC)算法,Goldwasser-Micali概率加密算法等。<

3、br>　　 目前,RSA加密與簽名算法,ElGamal簽名算法的變型(DSA)已成為國際上著名的加密簽名標準,這些密碼算法被廣泛應(yīng)用于網(wǎng)絡(luò)安全領(lǐng)域和銀行系統(tǒng),為交互雙方安全通信提供了保障和技術(shù)。因此,對公鑰密碼算法的安全性進行分析具有重要的理論意義和實際的應(yīng)用價值。自從公鑰密碼學提出以來,密碼學家一直致力于密碼算法的安全性研究。
　　 本文針對RSA和背包兩種公鑰密碼體制的安全性做了一些研究。我們的主要工作集中在中國剩余定理表

4、示的RSA密碼系統(tǒng)和RSA模特殊素因子的安全性分析,同時針對抵抗Shamir攻擊和低密度攻擊的兩種新背包型密碼算法,分別給出有效的破解算法。
　　 1.基于中國剩余定理表示(CRT)RSA密碼系統(tǒng)小解密指數(shù)的攻擊分析
　　 簡單版本的RSA算法描述如下,首先選取比特長度相同的兩個大素數(shù)p與q,它們的乘積N被稱為RSA模。除此之外,另兩個重要的參數(shù)是加密指數(shù)e和解密指數(shù)d,其中e與N的歐拉函數(shù)φ(N):=(p-1)(q-1

5、)互素,且滿足RSA方程ed=1 modφ(N).RSA加密算法加密消息m時,計算C=me mod N,發(fā)送密文C給用戶。用戶收到密文C后,進行解密運算Cd mod N,由歐拉定理知cd=med=m mod N,從而得到消息m。
　　 RSA的安全性基于求解模N的e次根的困難性。破解RSA公鑰密碼體制直接有效的方法是分解RSA模N。目前分解整數(shù)的方法有連分數(shù)方法,Pollardp-1方法,二次篩法,橢圓曲線方法,數(shù)域篩法等,其中

6、分解RSA模最快的方法是數(shù)域篩法,其時間和空間復(fù)雜度都是亞指數(shù)的。最近,768比特的RSA挑戰(zhàn)數(shù)宣告被分解,其算法的復(fù)雜度相當于分解512比特的RSA挑戰(zhàn)數(shù)的上千倍。同時密碼學家建議1024比特的RSA在三到四年內(nèi)停止使用,為保證安全可以使用比特數(shù)為1536比特,甚至2048比特的RSA模。Shor1992年在假設(shè)量子計算機模型存在的情況下,給出了分解整數(shù)的多項式時間算法,然而能否研究出多量子位的量子計算機還是一個未知數(shù)。
　　

7、 1982年A.Lenstra,H.Lenstra和L.Lovász提出計算格中近似短向量的多項式時間算法,并用此算法解決了有理系數(shù)多項式的分解問題。人們以三人姓氏的首字母命名此算法為LLL算法。LLL算法在RSA密碼算法及其他公鑰密碼體制的安全性分析中有廣泛的應(yīng)用。最著名的是,Coppersmith利用LLL算法在多項式時間內(nèi)求解單變量的模N方程fN(x)=0 mod N的小根x0,其中N是分解未知的合數(shù),和計算兩個變量的整系數(shù)方程f

8、(x,y)=0的小根。此后,許多RSA的攻擊結(jié)果都是基于Coppersmith的格構(gòu)造技術(shù)和近似短向量求解算法-LLL算法,如小加密指數(shù)攻擊,小解密指數(shù)攻擊,密鑰泄露攻擊等。對于小解密指數(shù)攻擊,Wiener在1990年提出當d

9、SA方程ed=kφ(N)+1,利用Coppersmith的格構(gòu)造技術(shù)構(gòu)造格,然后使用格歸約算法找到格中的較短向量,最后求解短向量所表示的二元方程的根。
　　 為了抵抗上述小解密指數(shù)攻擊,Wiener指出使用中國剩余定理(CRT)表示私鑰d來進行解密或簽名是一種非常有效的方法,并且可以選取小的CRT解密指數(shù)代替小的解密指數(shù)使解密過程更加有效快速。這種表示形式最早是由Quisquater和Couvreur提出的。具體地,RSA密碼算

10、法的解密指數(shù)d由CRT解密指數(shù)dp和dq表示,且滿足滿足下面關(guān)系
　　 dp≡d mod(p-1),dq≡d mod(q-1),
　　 當解密密文c=me mod N時,不是計算m=cd mod N,而是mp=cdpmod p和mq=cdq mod q,然后通過中國剩余定理計算出明文m?？梢钥闯?使用CRT解密指數(shù)dp和dq進行解密比標準RSA解密過程一般快四倍。Galbraith,Heneghan,Mckee[110]

11、和Sun,Wu[110]基于素數(shù)分布理論分別設(shè)計了快速加密和解密的CRT-RSA密碼體制,其密鑰生成方法是,首先選取小的公鑰指數(shù)e和私鑰指數(shù)dp,dq,然后檢測所得的p和q是否為素數(shù)。
　　 Bleichenbacher和May[3]分析了文獻[40,110]設(shè)計的CRT-RSA密碼體制的安全性,指出當CRT解密指數(shù)dp和dq滿足
　　 攻擊者可以在多項式時間內(nèi)有效分解RSA模Ⅳ。其攻擊方法是巧妙地利用CRT-RSA方程

12、得到一個關(guān)于四個變元的線性方程,然后構(gòu)造一個特殊的三維格,把分解RSA模問題轉(zhuǎn)化成求解此三維格中的最短向量問題。LLL算法在三維格中可以找到最短向量,因此利用LLL算法就可以解決上述問題。
　　 文獻[3]指出,假設(shè)所構(gòu)造三維格中長度小于Minkowski界的短向量是唯一的,從而可以分解此向量所對應(yīng)的多項式,得到CRT-RSA的私鑰指數(shù)dp,dq。本文第三章指出此唯一性假設(shè)在一般情況下不成立,證明文獻[3]中構(gòu)造的格中長度小于M

13、inkowski界的短向量是不唯一的,也就說明存在多個小于Minkowski界的短向量,并給出了反例。同時討論能否改進格的構(gòu)造使得文獻[3]的攻擊方法還可以有效,我們給出了否定的答案,并指出了因為。同時,我們對上述攻擊進行了改進和完善,即在一般情況下可以求解此問題。特別地,對于P　　 2.特殊素因子的RSA密碼系體制的安全性分析
　　 記R

14、SA模N的兩個素因子p和q的差p-q為人,稱為RSA模N的素因子差。記ip-jq為∧1,其中i,j是小整數(shù),稱為N的素因子組合差。de Weger研究分析了人比較小的這種情況,且要求p和q的比特長度相同,給出了弱密鑰解密指數(shù)d的界與∧之間的關(guān)系。指出當N的素因子差很小時,分別利用連分數(shù)方法和格基歸約方法可以提高Wiener和Boneh,Durfee的弱密鑰解密指數(shù)d的界。Bl(o)mer和May通過對等式ex+y≡0 modφ(N)進行

15、分析,給出了新的弱密鑰估計,同時也提出弱密鑰的范圍隨著素因子差∧變小而增大。最近,Maitra和Sarkar考慮了2q-p的情況,本質(zhì)上是Weger分析結(jié)果的補充。
　　 如果p和q的比特數(shù)不同,上述攻擊分析方法是不成立的。因此,本文就此情況展開討論,即允許p和q是不同比特的素數(shù),分析N的素因子組合差∧1=ip-jq與解密指數(shù)d之間的聯(lián)系。首先,利用Fermat的分解方法,證明當∧1≤(log N)u(｜ij｜N)1/4,可以在

16、多項式時間內(nèi)計算出RSA模N的素因子p和q。其次,當∧1≥(｜ij｜N)1/4,利用連分數(shù)攻擊方法分析∧1與d之間的關(guān)系,并給出當解密指數(shù)d滿足條件d0,RSA密碼算法是不安全的。進一步,通過格歸約分析方法,討論RSA模N的素因子組合差∧1與弱密鑰解密指數(shù)d的關(guān)系。以上情況下,當d>N0.292且p,q不同比特時,文獻[9,72,116,117]中的攻擊方法是不成功的,并給出了實例論證。同時,分

17、析擴展了Bl(o)mer,May的攻擊結(jié)果,得到更多新的弱密鑰。
　　 3.兩種背包型公鑰密碼算法的安全性分析
　　 背包加密算法是基于子集和問題的困難性設(shè)計的,該問題已被證明是NP完全問題。也就是說,不存在多項式時間算法求解子集和問題。Merkle和Hellman設(shè)計了第一個基于子集和問題的密碼算法,具有重要的歷史意義。隨后人們提出了許多Merkle-Hellman背包算法的變體,其中大多數(shù)變體(包括原始方案)已被證明

18、是不安全的。Shamir第一個提出了針對基本的Merkle-Hellman背包方案的多項式時間攻擊,這種攻擊利用H.Lenstra的整數(shù)規(guī)劃算法,當變量的數(shù)目固定時,該算法是多項式時間的,但在實際中效率很低。Adleman指出Merkle-Hellman背包算法的分析也可以看成格基歸約問題,利用LLL算法更簡潔有效的破解Merkle-Hellman體制。Logarias和Brickell,以及Coster等人利用格基歸約方法針對背包密碼