基于RSA算法的分析和研究

王方鑫

摘要：RSA算法是世界上目前應(yīng)用范圍最為廣泛的公鑰加密體制。它的安全性基于大素?cái)?shù)分解的困難性。該文對RSA算法中密鑰的生成及其加密解密的原理進(jìn)行了分析和討論。

關(guān)鍵詞：RSA；公鑰加密體制；加密；解密

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）26-0030-02

隨著科學(xué)技術(shù)的進(jìn)步和發(fā)展，信息保密和存儲安全問題越來越重要。無論是個(gè)人信息的保密還是網(wǎng)絡(luò)信息存儲的安全，都依賴于信息安全技術(shù)。其中，信息安全技術(shù)的核心又是密碼學(xué)技術(shù)，它是現(xiàn)代化發(fā)展的重要環(huán)節(jié)。

本文對RSA算法進(jìn)行了簡單的介紹，給出了RSA算法加密、解密、密鑰生成的流程，并對RSA的安全性進(jìn)行了分析。

1 RSA算法簡介

1976年，兩名美國的計(jì)算機(jī)學(xué)家提出Diffie和Hellman提出公鑰密碼體制的設(shè)想，可以在不直接傳遞密鑰的情況下，實(shí)現(xiàn)解密。隨后在1977年，三位美國的數(shù)學(xué)家Rivest、Shamir和Adleman聯(lián)合提出了RSA公鑰加密體制。

RSA算法是世界上第一個(gè)實(shí)用的公開密鑰的算法。它的安全性依賴于大整數(shù)因子分解的困難性，大整數(shù)因子分解問題是世界性的數(shù)學(xué)難題，一直到現(xiàn)在都沒有解決方案，也因此保證了RSA算法的安全性。目前而言，密鑰長度為1024位的RSA算法被認(rèn)為是安全的。

2 RSA算法步驟

2.1 RSA密鑰生成算法

1） 選取兩個(gè)大素?cái)?shù)[r]和[q]

2） 計(jì)算[n=p·q] ，[?n=p-1?q-1]

3） 隨機(jī)選取整數(shù)[e]，滿足[gcd（e，?（n））]=1

4） 計(jì)算[d]，滿足[d*e=1mod ?n] ，其中[e]和[n]是公鑰，[d]是私鑰

2.2 加密算法和解密算法

加密算法：[c=Em=memod n]

解密算法：[m=Dc=cdmod n]

2.3 RSA密碼體制總結(jié)

表1為RSA密碼體制。

3 [RSA]算法的安全性

3.1 針對[n] 分解的攻擊

這種攻擊理論的原理在于，若p 和q 已知，則[?n=p-1q-1]就可以計(jì)算出來。而同時(shí)公鑰d和私鑰e滿足[d*e=1mod ?n]，于是可以求出私鑰d。從中我們可以看出，RSA算法的安全性依賴于大整數(shù)分解的困難性，而大整數(shù)分解至今為止都沒有很好的解決辦法。因此我們認(rèn)為密鑰長度大于1024位比特的RSA算法是安全的。

3.2 二次篩因子分解法

這種攻擊理論的原理基于著名的費(fèi)馬因子分解：找出正整數(shù)[x、y]，使得 [x2≡y2]，即存在整數(shù)c滿足[cn=x2-y2=x-yx+y]，并且滿足[x≠±ymod n]，因此[n]是數(shù)[x2-y2=x-yx+y] 的因子，故[gcdx+y，n]或者[gcdx-y，n]均為n的因子，于是可以將n分解。

隨著近些年科學(xué)技術(shù)的發(fā)展，尤其是網(wǎng)絡(luò)上的分布式計(jì)算加快了因子分解的速度，表2給出近些年來實(shí)現(xiàn)的因子分解位數(shù)的記錄。

3.3 側(cè)信道攻擊

這種攻擊方式主要是通過對信息的加密、解密軟件進(jìn)行分析，通過收集和分析加密和解密的時(shí)間，電源的消耗，發(fā)出的噪聲，發(fā)出的熱量等來對數(shù)據(jù)進(jìn)行推測，來分析出算法的執(zhí)行流程和步驟，從而攻克該密碼體制。這種攻擊方法所需要的設(shè)備成本低、攻擊效果顯著，嚴(yán)重威脅了密碼設(shè)備的安全性。

4 RSA算法的優(yōu)缺點(diǎn)

4.1 RSA算法的優(yōu)點(diǎn)

1） RSA 是高強(qiáng)度非對稱加密系統(tǒng)，密鑰長度少則512位，多則2048位，非常難破解，至今尚未有人能破解超過1024位以上的RSA。

2） RSA算法實(shí)現(xiàn)比較簡單，易于理解和接受。

4.2 RSA算法的缺點(diǎn)

1） 產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。

2） 安全性， RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)，而且密碼學(xué)界多數(shù)人士傾向于因子分解不是NPC問題。目前，人們已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)，這就要求使用更長的密鑰，速度更慢；另外，目前人們正在積極尋找攻擊RSA的方法，如選擇密文攻擊，一般攻擊者是將某一信息作一下偽裝（Blind），讓擁有私鑰的實(shí)體簽署。然后，經(jīng)過計(jì)算就可得到它所想要的信息。

3） 速度太慢，由于RSA 的分組長度太大，為保證安全性，n 至少也要 600 bits以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對稱密碼算法慢幾個(gè)數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。SET（Secure Electronic Transaction）協(xié)議中要求CA采用2048比特長的密鑰，其他實(shí)體使用1024比特的密鑰。

5 結(jié)束語

RSA算法是一種安全性非常高的算法，人們對RSA算法進(jìn)行了很長時(shí)間的研究，卻依舊很難完全攻克RSA算法，這也從側(cè)面證實(shí)了其安全性。與此同時(shí)，RSA算法易于理解并且方便硬件的實(shí)現(xiàn)，隨著時(shí)間的推移，逐步被人們認(rèn)可和接受，也被很多人推崇為最優(yōu)秀的公鑰算法之一。但是，RSA算法也存在著一定的缺陷，它的運(yùn)行速度比較慢。RSA算法和一些對稱密碼算法相比，運(yùn)行的速度誤差了幾個(gè)數(shù)量級。并且隨著人們對大數(shù)分解問題研究的逐步深入，RSA算法的分組長度和密鑰長度很有可能會繼續(xù)的增加，從而更加影響它的運(yùn)行性能。因此，對RSA的進(jìn)一步研究和分析是很有意義的，RSA算法具有良好的應(yīng)用背景和發(fā)展前途。

參考文獻(xiàn)：

[1] 谷利澤，鄭世慧，楊義先.現(xiàn)代密碼學(xué)教程[M].北京郵電大學(xué)出版社，2009.

[2] 盧開澄.計(jì)算機(jī)密碼學(xué)[M].北京：清華大學(xué)出版社，2003.

[3] 楊曉元.現(xiàn)代密碼學(xué)[M].西安：西安電子科技大學(xué)出版社，2009.

[4] 楊波.現(xiàn)代密碼學(xué)：第二版[M].北京：清華大學(xué)出版社，2007.

[通聯(lián)編輯：代影]