整數分解與RSA的安全性

任彥冰

（西安電子科技大學網絡與信息安全學院，陜西 西安 710071）

整數分解與RSA的安全性

任彥冰

（西安電子科技大學網絡與信息安全學院，陜西 西安 710071）

提出了3種大整數因數分解的方法，并通過這些方法對RSA密碼算法的安全性做出了界定。根據分析得知，如果不考慮RSA中生成密鑰的2個素數之間的差值，單純地增加2個素數的取值對提高安全性很可能是無效的。最后，給出了兩則在 RSA密碼算法下要想產生能提供足夠安全強度的密鑰應該遵守的建議。

大整數；因數分解；RSA；密鑰長度；安全性

1 引言

RSA密碼算法的安全基于大整數分解的困難性[1]。公認的能夠破解RSA密碼算法的方法是實現大整數的有效分解[2,3]，即將一個大整數 n分解為p1 × p2（p1、p2為大素數）。到目前為止，人們依然無法快速分解大整數，但隨著計算能力的不斷提高，要想取得同等強度的安全性，RSA的密鑰長度也需要逐漸地增加[4～6]。但是密鑰增加到多少位才可以說是安全的？對這個問題業界并沒有一個嚴格的界定。一般的觀點是密鑰長度以待加密內容的密級而定[7,8]，但這種說法依然十分模糊。例如，一個以RSA算法提供HTTPS連接的網站可能會選擇2 048 bit的RSA密鑰，這足夠安全，但卻浪費了服務器的大量計算資源，因為對于一般的民用網絡來說，1 024 bit的RSA密鑰就足夠。因此，本文的主要目的是為解決上述問題提供一種思路。本文試圖用3種方式完成整數的因數分解，并根據對這一問題的探討給出2種RSA密鑰參數的選取策略，依據該策略用戶可以生成相對安全的RSA密鑰。但需要注意的是，這種安全是基于本文所討論的對因數分解這一問題的解決方案。

2 RSA密碼算法簡述

其中e滿足(e,?( n) )≡ 1(modn)；再求出d作為私鑰，其中d滿足 ed ≡ 1(modn)。

2) 將明文M加密：C ≡Me(modn)，其中M滿足M

3) 將密文C解密[9]：M ≡Cd(modn)，其中C滿足C < n。

3 整數因數分解方法介紹

3.1 方法一

3.1.1 綜述

注意到2個大素數一定都是奇數[10]，則它們一定滿足關系式(p1 + p2)mod2 =0，這個式子的意義是 p1與 p2之間一定存在一個唯一的中間值且如3 × 7 = 21，3與7的中間值是3與17的中間值是10。

如果能夠較快地找到 p1與 p2的中間值，那么從這一點同時向左右兩邊遍歷就能夠找到 p1、p2，至此實現了大整數 n = p1 × p2的分解。

3.1.2 進一步探討

圖1中的x軸與y軸分別表示 p1、 p2，z軸表示 p3 ? sqrt。可以看出，p3 ? sqrt的值隨著p1與 p2之間差值的增大而增大；當 p1與 p2之間非常接近時，p 3? sqrt的值隨之減小，即 p3與 sqrt之間的接近程度與 p1與 p2之間的接近程度呈正相關。

圖1 p3?sqrt隨p1、p2的變化趨勢

成立。事實上，對于任何整數 a，有(a ? i)× (a + i) = a2? i2≤ a2，其中i可取任何整數。因此，選擇 sqrtbelow作為中間值的嘗試是沒有必要的，因為從 sqrtbelow出發向兩邊取值的乘積永遠不會等于n。基于此，可以選擇 sqrtabove作為中間值 p3的候選值。

以 sqrtabove為出發點向兩邊取值，并求乘積的過程是可行的，原因是 sqrtabove2≥ n，且隨著i的增大， (s qrtabove?i) × (s qrtabove+i)的值逐漸減小，并在當i增大到某個值時有 (sqrtabove? i)× (sqrtabove+ i) = n或前一種情況表示已經找到了 p1、 p 2滿足n = p1 × p2，即完成了大整數的分解；后一種情況說明 sqrtabove依然不等于中間值 p3，需要繼續設定 p3的候選值，并以同樣的方法尋找 p1、p 2。為此，將 sqrtabove+1設置為新的 p3候選值，并以它為基點向兩邊尋找，依次類推。

3.1.3 優化方案

顯然大素數都應該是奇數，因此在確定了中間值的探測值Test以后，可以在以此為中點向左右兩邊探測的過程中跳過2個偶數相乘的情況，只對2個奇數相乘的情況進行計算比對。

3.1.4 算法

設已知大整數n是由2個素數相乘得到，有n = p1 × p2，且n已知，p1、 p2未知，則對于給定的大整數n，欲求 p1、 p2，有以下算法。

2) 定義變量Test，令其初值為 sqrtabove，轉第3)步。

3) 判斷Test的奇偶性，若為奇數，設i = 0；若為偶數，設i = 1，轉第4)步。

4) 計算 Result = (T est ?i) × (T est +i)，轉第5)步。

5) 若Result == n，則令 p1 = Test ?i， p2= Test+i，算法結束；否則，轉第6)步。

6) 若Result > n，計算 i =i+ 2，轉第4)步；否則，轉第7)步。

7) 若Result < n，計算 Test = Test+ 1，轉第3)步。

3.1.5 效率

該算法其實分為2個維度：第一個維度是尋找p1與 p 2的中間值實際操作是從sqrtabove出發，并不斷地對這個值進行加 1操作使其最終等于 p3 ，因此這個維度可以用來衡量；第二個維度是從所選擇的中間值Test開始，不斷地比較(T est?i) × (T est +i)是否等于n來判斷(T est? i)與(T est+ i)是否分別等于p1與 p 2(i = 1,2,3,?)，這個維度的計算次數隨著Test的增大而增大（線性增大），具體值取決于使 Test2? i2< n中i的大小。因此，整個算法的總計算次數可以看成是這2個維度的計算次數構成的三角形的面積，這個三角形的高是長是因此總的基本計算次數約等于可以看到用這種算法的計算次數與n無關，只與 p1、 p2以及有關，但的數量級是級別，的數量級也是級別，因此，整個算法的時間復雜度是 O(n)。

3.1.6 進一步優化

在上述討論的算法中，當出現(T est? i)× (T est+ i) < n時，將Test自增1，并讓i回到0，重新遍歷所有可能的取值。事實上這是不需要的，只需要在時將Test自增1，同時令i在當前值對的基礎上繼續增大即可。之所以可以這樣，是因為注意到則如果當前的i值滿足且則必有因此不必讓i回復到 0重新遍歷，而只需讓它繼續增大即可。

舉例說明此問題，假設現已知 n= 57，要求2個素數 p1、 p2使

根據算法，此時有Test的初值為8，i的初值為0。算法執行過程如下所示。

為方便理解，此算法依然沿用了每次觸發判斷條件時將i恢復成1，但從中也可以看出，更有效率的做法是在時不回置i，而是讓它繼續增大。

3.1.7 新算法

3) 判斷Test的奇偶性，若為奇數，設i = 0；若為偶數，設i = 1，轉第4)步。

5) 若Result == n，則令 p1 = Test?i，p 2= Test +i，算法結束；否則，轉第6)步。

6) 若Result > n，計算 i =i+ 2，轉第4)步；否則，轉第7)步。

7) 若Result < n，計算 Test = Test+ 1，i = i+ 1，轉第4)步。

3.1.8 改進后的效率

改進后的算法避免了對i的重復取值，將算法的整體復雜度從二維降到了一維。算法仍需要Test進行猜測性遍歷，對Test的遍歷其實是測試大于 sqrtabove、小于 p3的全部整數，總的測試次數是時間復雜度是

3.2 方法二

3.2.1 綜述

繼續討論 n = p1 × p2，在方法一的討論中已經知道， (s qrtabove?i) × (s qrtabove+i)隨著i的增大會越來越小，因此，如果假設已經找到了那么在i增大的過程中，(p3 ? i)× (p3 + i)會逐漸減小，并在i取到某一個特定的值時滿足(p 3 ? i)(p3 + i)=n，以下用實例來說明。

如果對這個例子進行進一步的研究，求出它們相鄰項數之差，即有下面各式。

可以看到，隨著i的增大，相鄰的(p 3 ? i)?(p3 + i)之差構成了一個公差是2的等差數列。事實上，并不只有某些特定的數字符合這種情況，對于所有非零整數k，都有的值構成1,3,5,7,9,11,…的等差數列（r=0,1,2,3,…）。

作為測試，隨機選取2個素數p1=1 033與p2= 1 997，它們的中值為1 515。繪制出當i取 0,1,2,3,…時，取值的圖形，如圖2所示。可以看出，相鄰

圖2 相鄰兩項之差構成等差數列

3.2.2 算法

3.2.3 改進

以上算法雖然可以完成大整數分解的任務，但是它相當于遍歷了從n到 (p 3)2的所有奇數，而隨著n的增大，這個算法的計算量也是巨大的，因此需要對這個算法進行改進。

注意到 3.2.2節算法是在已知n的基礎上累加一個等差數列的各項，直到求和的結果能夠被開根號為整數為止，這個算法能夠被優化是因為在之前的討論中并沒有對等差數列的特性進行討論，而當對等差數列本身加以關注，并引入等差數列的求和公式后，此算法的時間復雜性會有一個數量級的改進。

等差數列求和公式如下[14,15]

其中， a1是首項，d是公差，k是項數， Sk是各項之和。

在已知 a1與d的情況下，給出任何一個數字Sk，都能夠求出是否存在唯一的正整數k滿足式(2)，在 a1=1， d= 2的情況下，式(2)變為

此時，便不需要用n依次加上 1,3,5,7,9,…去判斷結果能否整開根號，只需要迅速找到一個可能有用的值Test，然后計算Test? n是否能使式(3)成立，即Test ? n是否能被整開方即可。如果Test能夠滿足上述條件，那么即為 p1與 p2的中值。

按照原始算法的思路，需要計算77+1+3+…，直到計算結果可以被開根號為整數為止，事實上，這需要進行2次比對，即先計算不是整數，再計算是一個整數，因此即為生成該整數的2個素數的中值。改進后的算法首先計算然后計算計算結果為4，因為4滿足首項為1、公差為2的等差數列的求和公式，于是即為所求，然后令9分別減去與加上即為素數7與11的數值。相比于原算法，改進算法只運行了一輪基本步驟就求得了結果。

3.2.4 改進后的算法

3.2.5 效率分析

3.3 方法三

3.3.1 綜述

注意到任何2個正整數的乘積都可以表示為一個等差數列逐項求和，其中等差數列的公差是2。因為2個正整數相乘總可以表示為，其中k與a + k分別為乘數與被乘數。如果將它們分別減去 k? 1，乘式變為1× (a + 1)，此時，令其中，于是有

此時，n滿足首項為 a+1，公差為 2，項數為k的等差數列的通項求和公式。

1) 初始時設 k= 3，轉步驟2)。

3) 判斷k能否整除Test，若可以，轉步驟5)；反之，轉步驟4)。

4) 令 k = k+ 2，轉步驟2)。

3.3.3 效率

4 進一步探討

眾所周知，公鑰密碼體系RSA密碼算法的安全性是基于整數分解問題的困難性的，但是RSA密碼算法的挑戰在于隨著計算機計算能力的增大，必須選取更加大的素數相乘作為密鑰。但是如果不考慮2個數字之間的關系，只是單純地選取更大的數字，有可能并不能起到預想的安全效果。本文討論的算法為這種安全性做了一個界定。由方法一與方法二可知，如果想讓 RSA密碼加密文件更安全，就需要在生成公私鑰時選擇相距盡可能遠的素數，因為只有這樣，的值才會大到攻擊者無法采用窮舉方式進行破解；而方法三與傳統意義上的簡單暴力破解則指出，令RSA密碼算法安全的必要條件是 p1與 p2中較小的一個min(p1,p 2)足夠大，以至于攻擊者無法通過枚舉所有自然數的方式解決問題。

因為在方法的實現中，min(p1,p 2)相對容易確定且這也是大多數用戶首先考慮到的安全指標[16]，故而選擇對δ做進一步探討。

首先做一個實驗，令 p1取為常數3，通過 p2的變化來觀察δ的變化如圖3所示。

但是差值到底要選為多大才算是真的安全，這又是一個相對的概念[17]。如果用戶選擇一個非常大的差值并將它運用在所有 p1與 p2的參數對中，這也是不可取的。因此，可以做另一個實驗，令 p1與 p2之間的差值固定，此處固定為 100，然后同步增大 p1與 p2，得到如圖4所示的δ關于 p1的圖形。

圖4 固定 p1與 p2之間差值后δ的變化趨勢

從圖4中可以看出，隨著 p1與 p2的增大，由這2個參數構成算法的安全性呈指數級減少。因此，僅確保將 p1與 p2之間的差值設定為一個固定的數值（或數量級）是不安全的，因為隨著 p1與 p2的增大，δ的值（或數量級）會隨著圖 4中曲線所展示的方式趨于減小，這讓分解整數n的因數變得簡單。

5 RSA中密鑰選取

5.1 策略一

該策略可以簡單描述如下。

1) 確認系統需要的安全級別，判斷需要選取

通過以上的分析，給出2種RSA中初始參數多少位的十進制數來作為自己的安全閾值。

2) 假設在步驟1)中，確認至少需要k位的十進制數來阻止攻擊者的計算攻擊，那么在這一步中，首先選擇第一個素數 p1，且 p1滿足 p1> 10k。

3) 選擇 p2，要求 p 2 > p1，且如果要在k位十進制整數中選擇 p 2，則 p 2必須滿足（即 δ> 10k）；當然，也可以在任何l位整數中選取參數 p2，l滿足l> k。

5.2 策略二

根據上文論述，依然取ζ作為衡量RSA的安全參數，并選取η作為用戶能夠接受的安全閾值。其中η是用戶認定的安全計算次數，即用戶認定攻擊者無法承受η次的計算來破譯密碼。顯然，算法參數的選取應該滿足ζ≥ η 。

根據上文的敘述，ζ為 p1、 p2與δ當中的較小者，不妨設 p 2 > p1，即算法參數的選取應該滿足使 p1與δ均不小于η。又因為δ=且當 n? 1時，有所以在 n?1時有

即

計算可知方程有解，選取方程解中較大的一個即為應該選取的 p2的最小取值。

6 結束語

本文從整數的因數分解問題入手，提出了 3種能夠完成因數分解問題的方法，并對這些方法的效率做了簡要的分析與度量。另外，在本文的方法三中簡要討論了2個數的乘積與等差數列求和之間的關系問題。第4節對提出的算法所定義的RSA安全性做了進一步的討論，并在第5節給出了2種RSA密鑰參數的選取策略，以確保用戶生成的整數n在因數分解問題上的困難性。

[1] 陳恭亮. 信息安全數學基礎[M]. 北京：清華大學出版社, 2014.

CHEN G L. Mathematical basis of information security [M]. Beijing:Tsinghua University Press, 2014.

[2] STAILINGS W. Cryptography and network security: principles and practice[C]//Prentice Hall. 2010.

[3] STINSON D R. Cryptography: theory and practice[M]. Boca Raton: CRC Press, 2005.

[4] 胡向東, 魏琴芳. 應用密碼學教程[M]. 北京：電子工業出版社, 2005.

HU X D, WEI Q F. Applied cryptography tutorial[M]. Beijing: Electronic Industry Press, 2005

[5] BRENNER A E. Moore's law[J]. Science, 1997, 275(5306): 1551-1551.

[6] ROMANELLI A. Intel extends moore's law[J]. Electronic News, 2002, 48(8):1.

[7] 王恒青, 宋如敏. 公開密鑰密碼體制的安全取決于密鑰的長度[J]. 科技信息:學術研究, 2008(34):214-216.

WANG H Q, SONG R M. The security of public key cryptosystem depends on the length of the key[J]. Science And Technology Information: Academic Research, 2008 (34): 214-216.

[8] 王恒青, 宋如敏. 密鑰的長度影響著 RSA體制的安全程度[J].電腦知識與技術, 2011, 7(10): 7104-7105.

WANG H Q, SONG R M. The length of the key affects the security of the RSA system [J]. Computer Knowledge and Technology, 2011, 7 (10): 7104-7105.

[9] RIVEST R L, SHAMIR A, ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1983, 26(2):96-99.

[10] RIBENBOIM P. The book of prime number records[J]. Mathematical Gazette, 1988, 73(465):663-665.

[11] 姜建國, 臧明相. 數論算法[M]. 西安：西安電子科技大學出版社, 2014.

JIANG J G, ZANG M X. Number theoretic algorithm[M]. Xi’an: Xidian University Press, 2014.

[12] BECKETT R, HURT J. Numerical calculations and algorithms[J]. Mathematics of Computation, 1968, 22(102): 266-269.

[13] HUANG Y L. Square root algorithm: US20070112903[P]. 2007.

[14] HONG S. Application of functions to get the sum and product of partial sequencing items in series of equal difference and proportion[J]. Journal of Nanyang Normal University, 2006, 26(5): 159-171.

[15] KOTZ S, NADARAJAH S. Arithmetic progression[M]//Encyclopedia of Statistical Sciences. John Wiley & Sons, Inc., 2006:141.

[16] KAHNEMAN D. Thinking, fast and slow[M]// Thinking, Fast and Slow. Farrar, Straus and Giroux, 2011:501-502.

[17] SYNGE J L. Relativity: the general theory[J]. Physics Today, 2009, 14(10):50-52.

Factorization of big integer and the security of RSA

REN Yan-bing

(School of Cyber Engineering, Xidian University, Xi’an 710071, China)

Three kinds of methods for integer factorization were proposed and the security of RSA was demarcated. RSA is a well-known cryptographic algorithm, using the analysis result of those methods. Through the work, readers could easily realize that if merely enlarged two prime numbers but lost attention of the relevance of them, the security of this algorithm might been missed. In the end, two recommended tactics to choose prime numbers as key of this algorithm were given.

integer, factorization, RSA, key size, security

TN918.1

A

10.11959/j.issn.2096-109x.2017.00166

2017-02-08；

2017-03-25。通信作者：任彥冰，395436700@qq.com

任彥冰（1993-），男，甘肅武威人，西安電子科技大學碩士生，主要研究方向為網絡與信息安全。