論Miller-Rabin算法預(yù)處理的局限性*

王景中，周 靖

(北方工業(yè)大學(xué) 信息與通信工程學(xué)院，北京100144)

論Miller-Rabin算法預(yù)處理的局限性*

王景中，周 靖

(北方工業(yè)大學(xué) 信息與通信工程學(xué)院，北京100144)

信息安全領(lǐng)域中極為重要的公鑰密碼體制的關(guān)鍵在于生成兩個(gè)大素?cái)?shù)，目前雖已有多項(xiàng)式運(yùn)行時(shí)間的確定性素性檢測(cè)算法AKS算法，可惜運(yùn)行時(shí)間還達(dá)不到實(shí)用要求，故還是快速實(shí)用的概率性素性檢測(cè)算法Miller-Rabin算法為主流，但其有一點(diǎn)一直被忽略——Miller-Rabin算法直接控制的其實(shí)是誤判率而不是出錯(cuò)率，而后者才是真正需要降低的。對(duì)此做了詳細(xì)分析，同時(shí)考察一些利用素?cái)?shù)分布特性的預(yù)處理措施在降低出錯(cuò)率方面的效果，并分析了這一類(lèi)優(yōu)化的效果極限,否定了其必要性，相比之下，針對(duì)算法底層的優(yōu)化更為直接有效。

素性檢測(cè);Miller-Rabin算法;誤判率與出錯(cuò)率;素?cái)?shù)分布;預(yù)處理的局限性;算法底層優(yōu)化

0 引 言

目前，信息化已經(jīng)成為社會(huì)發(fā)展的核心和潮流，信息是社會(huì)發(fā)展的一種非常重要的戰(zhàn)略資源。因特網(wǎng)的發(fā)展，打破了傳統(tǒng)的空間和地域的觀念，從而實(shí)現(xiàn)了真正的全球信息化，然而由于網(wǎng)絡(luò)的互聯(lián)性、共享性和開(kāi)發(fā)性，使得網(wǎng)絡(luò)面臨著信息的假冒、篡改和泄露等威脅。因此，隨著互聯(lián)網(wǎng)應(yīng)用的不斷廣泛和深入的發(fā)展，信息安全的重要性亦越發(fā)凸顯。

信息加密技術(shù)是保證網(wǎng)絡(luò)中數(shù)據(jù)安全的最主要同時(shí)也是最基本的措施。在很多情況下，對(duì)網(wǎng)絡(luò)中的數(shù)據(jù)進(jìn)行加密是保證數(shù)據(jù)通信安全的唯一方法。在數(shù)據(jù)的加密過(guò)程中，需要使用各種加密算法來(lái)實(shí)現(xiàn)。另外，由于傳輸過(guò)程中存在數(shù)據(jù)被通信雙方之外的第三方偽造或篡改的可能，通信雙方無(wú)法驗(yàn)證數(shù)據(jù)來(lái)源，就很有可能出現(xiàn)一方抵賴(lài)的情況，此時(shí)就要求保證傳輸信息的不可否認(rèn)性，數(shù)字簽名就是通信雙方在網(wǎng)上交換信息時(shí)，防止偽造和欺騙的一種身份認(rèn)證技術(shù)。而公鑰密碼體制無(wú)論是在保密性還是鑒權(quán)認(rèn)證方面都十分的實(shí)用和可靠，因而得到廣泛的認(rèn)同和應(yīng)用。RSA目前已成為公鑰密碼的國(guó)際標(biāo)準(zhǔn)，其理論基礎(chǔ)是數(shù)論中的一條重要論斷：求兩個(gè)大素?cái)?shù)之積是容易的，而將一個(gè)具有大素?cái)?shù)因子的合數(shù)進(jìn)行分解卻是非常困難的。顯然大素?cái)?shù)的選取是構(gòu)造RSA密鑰的關(guān)鍵[1-3]，為了保證安全性，一般產(chǎn)生素?cái)?shù)是生成隨機(jī)數(shù)然后對(duì)其進(jìn)行素性檢測(cè)，分為兩類(lèi)：確定性素性檢測(cè)算法和概率性素性檢測(cè)算法，前者不存在誤判，但是運(yùn)行都很慢，如AKS算法和APRCL算法[4-6]；后者存在一定的誤判率，但可以被有效地控制到足夠小，且運(yùn)行速度較快，如Solovay-Strassen算法和Miller-Rabin算法[7-12]，其中Miller-Rabin算法更實(shí)用，但其有一點(diǎn)一直被忽略——Miller-Rabin算法直接控制的其實(shí)是誤判率而不是出錯(cuò)率，以下將首先對(duì)此算法進(jìn)行詳細(xì)分析。

1 Miller-Rabin算法分析

為了后續(xù)的推導(dǎo)，首先不加證明地介紹如下4個(gè)引理及1個(gè)推論[7-9,13]：

引理1(Fermat小定理)：若n為大于2的素?cái)?shù)，a為小于n的正整數(shù)，則an-1≡1(modn)。

引理2：若n為大于2的素?cái)?shù)，則x2≡1(modn)的解滿(mǎn)足x≡±1(modn)。

引理1、2推論：若n為大于2的素?cái)?shù)，可令n-1=2sr，其中r為奇數(shù)，s為正整數(shù)，a為小于n的正整數(shù)，j為正整數(shù)且j≤s-1，則有ar≡1(modn)或存在j使得a2jr≡-1(modn)。

引理3：若n為大于2的素?cái)?shù)，p,q為正整數(shù),則xq-1≡1(modnp)的模n相異解的個(gè)數(shù)為gcd(q-1,(n-1)np-1)。

對(duì)模M有唯一解，且a1,a2,…,ak不完全相同時(shí)，解模M相異。

得證。

2 算法指標(biāo)分析

出錯(cuò)率與誤判率其實(shí)是先驗(yàn)概率、后驗(yàn)概率的關(guān)系，這兩者與隨機(jī)選取數(shù)時(shí)選到一個(gè)素?cái)?shù)的概率有關(guān)，不妨設(shè)其為p素，稍加分析可知：

展開(kāi)為級(jí)數(shù)得：

于是可以看出，要達(dá)到我們測(cè)試的真正目的，即降低p錯(cuò)，有兩個(gè)方向：一是降低p誤，簡(jiǎn)單地增加測(cè)試輪數(shù)即可；二是提高p素，這需要在隨機(jī)抽取數(shù)n時(shí)采取一些策略，即預(yù)處理，根據(jù)素?cái)?shù)分布特性，數(shù)越大素?cái)?shù)越稀疏，因此合數(shù)擁有小素?cái)?shù)因子的概率較大，故預(yù)處理時(shí)用一些小素?cái)?shù)篩一下能較有效的濾除大部分合數(shù)，另外可采用遞增隨機(jī)法取數(shù)，即在一個(gè)大隨機(jī)數(shù)的基礎(chǔ)上，每次遞增lnn附近的一個(gè)隨機(jī)數(shù)的增量，因?yàn)檫@是素?cái)?shù)的平均間距，從而更有可能選取到素?cái)?shù)。然而這里仔細(xì)計(jì)算一下可以發(fā)現(xiàn)，明確了降低p錯(cuò)的目標(biāo)之后，若以抵消掉p素的影響為要求，用第一種方法，只需要增加3、4輪測(cè)試即可達(dá)到要求，時(shí)間消耗增加約為7%，當(dāng)然p素、p誤的實(shí)際數(shù)值會(huì)影響這數(shù)據(jù)，但實(shí)際上，隨著被測(cè)試數(shù)的增大，p素的減小十分緩慢，幾乎不怎么需要額外增加測(cè)試輪數(shù)，例如被測(cè)試數(shù)從128位增加到256位后，還不需要增加額外的測(cè)試輪數(shù)，同時(shí)隨著被測(cè)試數(shù)的增大，測(cè)試的標(biāo)準(zhǔn)輪數(shù)亦會(huì)相應(yīng)增大，因此增加的時(shí)間消耗可能還會(huì)更低，不妨粗略定其為10%。再考慮預(yù)處理措施，無(wú)論如何p素是不可能被提高到1的，提高10倍幾乎是其極限了，也就相當(dāng)于額外增加1、2輪測(cè)試的效果，其時(shí)間額外消耗一般與額外測(cè)試輪數(shù)大致相當(dāng)，至少節(jié)省的時(shí)間及其有限，然而算法的復(fù)雜性卻提高了，帶來(lái)了新的安全隱患。

相比之下，若對(duì)算法底層運(yùn)算過(guò)程進(jìn)行優(yōu)化，不像預(yù)處理措施那樣有理論上的很有限的優(yōu)化效果上限，底層優(yōu)化能夠在效果不變時(shí)帶來(lái)較大的時(shí)間節(jié)省，那么若利用節(jié)省的時(shí)間來(lái)增加測(cè)試輪數(shù)的話，就能在時(shí)間消耗不變的情況下，較大幅度的降低p誤從而降低p錯(cuò)。至于算法底層優(yōu)化則有較多方式，考慮到Miller-Rabin算法最為耗時(shí)的步驟在模冪操作和循環(huán)，常見(jiàn)的對(duì)算法的優(yōu)化實(shí)現(xiàn)主要集中在對(duì)這兩部分運(yùn)算的優(yōu)化。例如對(duì)模冪操作的優(yōu)化可以使用改進(jìn)的滑動(dòng)窗口算法結(jié)合Montgomery模乘和模平方算法來(lái)改進(jìn)其中的模乘操作，其中模乘算法如果采用大整數(shù)乘法和除法求模乘，因?yàn)樯婕昂臅r(shí)的除法操作，所以要相對(duì)較慢，結(jié)合大整數(shù)乘法和Barrett求模算法可以用2(n2+3n+1)步單精度乘法完成。使用Montgomery求模算法結(jié)合大整數(shù)乘法算法，可以在2n(n+1)步單精度乘法內(nèi)完成算法。Montgomery模平方的操作可以在3n(n+1)/2步單精度乘法內(nèi)完成，而B(niǎo)arrett模平方需要(3n(n+3)/2+1)步單精度乘法。結(jié)合改進(jìn)的滑動(dòng)窗口算法和Montgomery類(lèi)算法，可以得到目前非特殊情況下的較優(yōu)的模冪算法。

表1給出模冪算法的比較，其中k是窗口大小，根據(jù)情況選擇以達(dá)到最優(yōu)，t是指數(shù)的二進(jìn)制位數(shù)。

表1 模冪算法比較表

3 結(jié) 語(yǔ)

通過(guò)對(duì)Miller-Rabin算法的理論和性能的詳細(xì)研究，發(fā)現(xiàn)若明確了降低p錯(cuò)的這個(gè)目標(biāo)，則算法的預(yù)處理的優(yōu)化效果還不如直接增加測(cè)試輪數(shù)，同時(shí)算法的復(fù)雜性提高帶來(lái)了新的安全隱患，因此對(duì)Miller-Rabin算法的優(yōu)化研究不應(yīng)該再關(guān)注這一方面，相比之下，應(yīng)該考慮算法底層實(shí)現(xiàn)過(guò)程中的優(yōu)化，如針對(duì)其中模冪算法的優(yōu)化，后者更為直接有效。

[1] 李榮森， 秦杰， 竇文華. RSA系列算法在工程中的應(yīng)用研究[J]. 計(jì)算機(jī)科學(xué)，2007(34)： 86-90. LI Rong-sen, QIN Jie, DOU Wen-hua. Study on Implementing RSA Algorithm in Actual Project[J]. Computer Science, 2007( 34): 86-90.

[2] 陳作新. 一種基于AES和三素?cái)?shù)RPrime RSA認(rèn)證加密方案[J].計(jì)算機(jī)應(yīng)用， 2008(28)： 3199-3201. CHEN Zuo-xin. New Authentication Encryption Schemebased on AES and Three-Prime RPrime RSA[J]. Journal of Computer Applications. 2008, 28: 3199-3201.

[3] 肖振久， 胡馳， 陳虹.四素?cái)?shù)RSA數(shù)字簽名算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用， 2013(33):1374-1377. XIAO Zhenjiu, HU Chi, CHEN Hong. Research and Implementation of Four-Prime RSA Digital Signature Algorithm[J]. Journal of Computer Applications. 2013(33):1374-1377.

[4] MANINDRA AGRAWAL, NEERAJ KAYAL, NITIN SAXENA. Primes is in P[J]. Annals of Math. 2004(160): 781-793.

[5] BERRIZBEITIA P． Sharpening “Primes is in P”for a large family of numbers[J]. Math. Comp. 2005, 74(252): 2043-2059.

[6] 劉永亮， 姚鴻勛， 高文. AKS算法對(duì)現(xiàn)代密碼學(xué)的影響[J].計(jì)算機(jī)工程與應(yīng)用， 2003(11)： 0001-0003. LIU Yong-liang,YAO Hong-xun, GAO Wen. The Effect of AKS Algorithm on Modern Cryptography[J]. Computer Engineering and Applications, 2003(11):0001-03.

[7] YAN SONG YUAN. Number Theory for Computing[M].Berlin: Springer-Verlag, 2002.

[8] RABIN MICHAEL. Probabilistic Algorithmsfor Testing primality[J]. Journal of Number Theory. 1980(12):128-138.

[9] MONIER LOUIS. Evaluation and comparison of two efficient probabilistic primality testing algorithms[J]. TheoreticalComputer Science. 1980(12):97-108.

[10] BERNSTEIN J ．Proving Primality in Essentially Quartic Random Time[J]. Math. Comp. 2007, 76(257): 389-403.

[11] 楊波. 現(xiàn)代密碼學(xué)[M]. 北京: 清華大學(xué)出版社, 2007. YANG Bo. Modern Cryptography[M].Beijing: Tsinghua University Press, 2007.

[12] 秦曉東, 辛運(yùn)幃, 盧桂章. Miller_Rabin算法研究與優(yōu)化實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程, 2002(28): 55-57. QIN Xiao-dong, XIN Yun-wei, LU Guizhang. Research and Efficient Implementation of Miller-Rabin algorithm[J]. Computer Engineering, 2002,28: 55-57.

[13] RICHARD COURANT, HERBERT ROBBINS. What is Mathematics[M].London: Oxford University Press,2009.

National Natural Science Foundation Project(No.61371142)、Beijing innovation team building promotion plan(ID HT20130502)

Preprocessing Limit of Miller-Rabin Test

WANG Jing-zhong， ZHOU Jing

(Department of Information and Communication Engineering,North China University of Technology,Beijing 100144,China)

Public key cryptosystem is an extremely important part in information security field, and its key lies in generating two big primes. Nowadays, although there is polynomial-time definitive primality detecting algorithm, such as AKS algorithm, unfortunately its running time could not meet the practical demands, therefore, the fast and practical probabilistic primality testing algorithm, Miller-Rabin test, becomes the main algorithm. However, some detail of Miller-Rabin test is always ignored: it is misjudgment probability not error probability that is directly controlled by the test, while the latter is what indeed needs to decrease. Detailed analysis of this point is given, and meanwahile, the effects of some preprocessing methods with distribution features of primes to decrease error probability are tested. Finally, the optimized result limit is analyzed and its necessity negated. Comparison indicates that, the underlying optimization of algorithm is more effective.

primality test; Miller-Rabin test; misjudge probability and error probability; prime distribution; preprocessing limit; underlying optimization of algorithm

date:2014-10-05；Revised date：2015-02-27

國(guó)家自然基金項(xiàng)目(No.61371142)、北京市創(chuàng)新團(tuán)隊(duì)建設(shè)提升計(jì)劃(No.ID HT20130502)

TP301.6

A

1002-0802(2015)04-0469-04

王景中(1962—)，男，碩士，教授，主要研究方向?yàn)閿?shù)字圖像處理及其應(yīng)用、網(wǎng)絡(luò)與信息安全；

周 靖(1990—)，男，碩士研究生，助研，主要研究方向?yàn)閿?shù)字圖像處理及其應(yīng)用、網(wǎng)絡(luò)與信息安全。

10.3969/j.issn.1002-0802.2015.04.017

2014-10-05；

2015-02-27