李創(chuàng)成 陳文慶

(1.湛江師范學(xué)院 基礎(chǔ)教育學(xué)院，廣東 湛江524037；2.湛江師范學(xué)院教務(wù)處,廣東 湛江524048)

基于DELPHI的大素?cái)?shù)MILLER-RABIN檢測(cè)方法的實(shí)現(xiàn)

李創(chuàng)成1陳文慶2

(1.湛江師范學(xué)院 基礎(chǔ)教育學(xué)院，廣東 湛江524037；2.湛江師范學(xué)院教務(wù)處,廣東 湛江524048)

論文介紹了利用動(dòng)態(tài)數(shù)組對(duì)大整數(shù)的存儲(chǔ)，把大整數(shù)的計(jì)算轉(zhuǎn)化為數(shù)組元素的運(yùn)算，并在 Delphi中實(shí)現(xiàn)了大素?cái)?shù)Miller-Rabin檢測(cè)。

大素?cái)?shù)；動(dòng)態(tài)數(shù)組；存儲(chǔ)；檢測(cè)

0 引 言

隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)越來(lái)越來(lái)越普及，計(jì)算機(jī)的信息安全不僅是關(guān)系到軍事和政府部門(mén)，而且關(guān)系到所有計(jì)算機(jī)用戶(hù)。密碼學(xué)是網(wǎng)絡(luò)信息安全的基礎(chǔ)，而公鑰密碼體制是密碼學(xué)的重要組成部分，其中RSA算法作為公鑰密碼體制中較為完善的算法之一，具有較高的安全性，被廣泛應(yīng)用于數(shù)據(jù)加、解密和數(shù)字簽名技術(shù)中。但RSA算法的公開(kāi)密鑰和私有密鑰是一對(duì)大素?cái)?shù)。因此，對(duì)RSA算法的發(fā)展離不開(kāi)對(duì)大素?cái)?shù)的研究，Rabin-Miller算法是完成素?cái)?shù)測(cè)試的最佳選擇[1～4][7～8]。而Delphi作為一種面向?qū)ο蟮目梢暬幊坦ぞ?，具有功能?qiáng)大、運(yùn)行速度快、易于學(xué)習(xí)和使用以及開(kāi)發(fā)效率高等特點(diǎn)，特別適合分布式系統(tǒng)的開(kāi)發(fā)[5]。但該語(yǔ)言沒(méi)有直接提供大整數(shù)的存儲(chǔ)和運(yùn)算功能，這樣就給在實(shí)際應(yīng)用系統(tǒng)開(kāi)發(fā)中加密和解密數(shù)據(jù)時(shí)帶來(lái)了不便。

1 Delphi整型數(shù)據(jù)類(lèi)型和大整數(shù)的存儲(chǔ)

在Delphi中整型數(shù)據(jù)類(lèi)型有9種，它們的性質(zhì)和表示范圍如表1所示。

表1.Delphi整型數(shù)據(jù)類(lèi)型的性質(zhì)及取值范圍

由表1可以看出，Delphi7.0中最大整型數(shù)據(jù)類(lèi)型是Int64整型，其絕對(duì)值最大是38位整數(shù)，這樣的有效位數(shù)的整數(shù)遠(yuǎn)遠(yuǎn)不能滿(mǎn)足RSA加密密鑰的需要，而超過(guò)這個(gè)范圍的整數(shù)Delphi是不能使用現(xiàn)有的數(shù)據(jù)類(lèi)型直接存儲(chǔ)和運(yùn)算。為了在Delphi中可以實(shí)現(xiàn)大整數(shù)存儲(chǔ)和運(yùn)算，采用動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)大整數(shù)，具體的數(shù)據(jù)結(jié)構(gòu)定義如下：

TSign=(negative,positive);

TFGInt=Record

Sign:TSign;

Number:Array Of Int64;

End;

從理論上說(shuō)，采用這種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，可以實(shí)現(xiàn)非常大的整數(shù)運(yùn)算和存儲(chǔ)。數(shù)組中每個(gè)元素存放8字節(jié)整數(shù)，也是就是說(shuō)每個(gè)數(shù)組元素就可能存放一個(gè)38位的整數(shù)，這樣就大大地?cái)U(kuò)展了計(jì)算機(jī)內(nèi)整數(shù)的表示范圍。用數(shù)組來(lái)存儲(chǔ)大整數(shù)有兩種方式：

(1)大整數(shù)的低位存放在數(shù)組下標(biāo)最小(為了程序處理方便，本文約定數(shù)組的長(zhǎng)度存放在數(shù)組下標(biāo)為零的元素中)的元素中。

(2)大整數(shù)的高位存放在數(shù)組下標(biāo)最小的元素中。

不管那種方法存儲(chǔ)的數(shù)據(jù)，其實(shí)質(zhì)是一樣的，只是在處理方法上有些差異而已。

2 素?cái)?shù)的檢測(cè)方法

大素?cái)?shù)的選取是構(gòu)造RSA密鑰的關(guān)鍵。因此大素?cái)?shù)的產(chǎn)生與檢測(cè)在密碼學(xué)領(lǐng)域成為一個(gè)重要課題。檢測(cè)素?cái)?shù)的一般方法可以分為兩類(lèi)：即確定性素?cái)?shù)產(chǎn)生方法和概率性素?cái)?shù)產(chǎn)生方法。

2.1 素?cái)?shù)檢測(cè)方法的分類(lèi)

目前，檢測(cè)素?cái)?shù)的一般方法可以分為兩類(lèi)：即確定性素?cái)?shù)檢測(cè)方法和概率性素?cái)?shù)檢測(cè)方法。

確定性素?cái)?shù)檢測(cè)方法檢測(cè)產(chǎn)生的數(shù)必然是素?cái)?shù)。確定性素?cái)?shù)方法的優(yōu)點(diǎn)在于產(chǎn)生的數(shù)一定是素?cái)?shù)；缺點(diǎn)是生成的素?cái)?shù)帶有一定的限制。若算法設(shè)計(jì)不當(dāng)，很容易構(gòu)造出的有規(guī)律的素?cái)?shù)，致使密碼分析者很容易地分析到素?cái)?shù)的變化，直接猜測(cè)到密碼系統(tǒng)所使用的素?cái)?shù)。此類(lèi)方法主要有兩類(lèi)，即基于Lucas定理和基于Pocklington定理的確定性素?cái)?shù)檢測(cè)方法[3]。較常用的檢測(cè)方法有Pock lington方法、Dem ytko方法和ASK算法。

概率性方法是目前檢測(cè)素?cái)?shù)的主要算法。該方的優(yōu)點(diǎn)是：檢測(cè)偽素?cái)?shù)速度較快、原理簡(jiǎn)單、易于編程實(shí)現(xiàn)，構(gòu)造的偽素?cái)?shù)沒(méi)有規(guī)律性，其缺點(diǎn)是其檢測(cè)的數(shù)具有一定的誤判，所以稱(chēng)為偽素?cái)?shù)。其中較為著名的算法有Solovay—Strassen檢測(cè)法、Lehman檢測(cè)法和Miller-Rabin檢測(cè)法[1][3][6]。本文主要僅介紹Miller-Rabin素?cái)?shù)檢測(cè)方法的原理和Delphi環(huán)境下的實(shí)現(xiàn)。

2.2 Miller-Rabin素?cái)?shù)檢測(cè)算法的基本原理

MillerRabin算法是Fermat算法的一個(gè)變形改進(jìn)，它的理論基礎(chǔ)是Fermat定理引申而來(lái)。Fermat定理：n是一個(gè)奇素?cái)?shù)，a 是任何整數(shù)(1≤a≤n-1)，則 an-1≡l(mod n)。

Miller-Rabin算法的理論基礎(chǔ)是：如果n是一個(gè)奇素?cái)?shù)，將n-l表示成2s*r形式(r是奇數(shù))，a是和n互素的任何整數(shù)，那么 ar≡l(mod n)或者對(duì)某個(gè) j(0≤j≤s-1，j∈z)等式≡l(mod n)成立[6]。

Miller Rabin測(cè)試算法的具體如下：

輸入數(shù)據(jù)：大于3待測(cè)試奇整數(shù)n。

輸出數(shù)據(jù)：返回n是否為素?cái)?shù)。

1、將待測(cè)試數(shù)據(jù)n-1表示成2s*r(其中r是奇數(shù))。

2、選擇一個(gè)隨機(jī)整數(shù)a(2≤a≤n-2)

3、計(jì)算y←ar(mod n)

4、如果y=1或y=n-1，返回素?cái)?shù)，算法結(jié)束。否則繼續(xù)下面的操作：

5、j=1

6、當(dāng)j≤s-1并且y≠n-1循環(huán)作下面操作，否則轉(zhuǎn)8。

7、計(jì)算y←y2(mod n)，如果y=1返回“合數(shù)”，算法結(jié)束，否則j=j+1，轉(zhuǎn)步聚6。

8、如果y≠n-1則返回“合數(shù)”,算法結(jié)束。

9、返回“素?cái)?shù)”。

3 大素?cái)?shù)Miller-Rabin檢測(cè)程序的實(shí)現(xiàn)

大素?cái)?shù)Miller-Rabin檢測(cè)方法的Delphi具體程序如下：

Procedure FGIntRabinMiller(Var n:TFGInt;Var ok:boolean);

Var

j,b:LongWord;

m,y,temp1,temp2,temp3,zero,one,two,pmin1:TFGInt;

ok1,ok2:boolean;

Begin

randomize;

j:=0;

Base10StringToFGInt('0',zero);//將字符“0”轉(zhuǎn)為大整數(shù)形式

Base10StringToFGInt('1',one);//將字符“1”轉(zhuǎn)為大整數(shù)形式

Base10StringToFGInt('2',two);//將字符“2”轉(zhuǎn)為大整數(shù)形式

FGIntsub(n,one,temp1);//兩大整數(shù)相減temp1=n-1

FGIntsub(n,one,pmin1);//兩大整數(shù)相減pmin1=n-1

s:=0;

While(temp1.Number[1]Mod 2)= 0 Do//將大整數(shù)temp1轉(zhuǎn)為2s*r形式

Begin

s:=s+1;

FGIntShiftRight(temp1);

End;

r:=temp1;

ok:=true;

Randomize;

Base10 String To FGInt(inttostr(Primes[Random(1227)+1]),a);//隨機(jī)產(chǎn)生一整數(shù)a

FGInt Mont Gomery Mod Exp(a,m,n,y);//利用MontGomery算法計(jì)算y=ar(mod n)

FGInt Destroy(a);

ok1:=(FGIntCompareAbs(y,one)=Eq);//y是否等于1

ok2:=(FGIntCompareAbs(y,pmin1)=Eq);//y是否等于n-1

If Not(ok1 Or ok2)Then

Begin

While j

Begin

If (j>0) And ok1 Then ok:=false

Else

Begin

j:=j+1;

If (j

Begin

FGIntSquaremod(y,n,temp3);//temp3=y2(mod n)

FGIntCopy(temp3,z);//z=temp3

ok1:=(FGIntCompareAbs(z,one)=Eq);//是否z=1

ok2:=(FGIntCompareAbs(z,pmin1)=Eq);//是否z=n-1

If ok2 Then j:=b;

End;

Else If (Not ok2) And(j>=b)Then ok:=false;

End;

End;

End;

End;

End;

4 結(jié)束語(yǔ)

本文探討了在Delphi環(huán)境下實(shí)現(xiàn)是大素?cái)?shù)Miller-Rabin檢測(cè)的基本方法。本程序只給出了Miller-Rabin大素?cái)?shù)檢測(cè)方法主要程序，在該程序還使用到幾個(gè)有關(guān)大整數(shù)運(yùn)算的過(guò)程和函數(shù)，由于篇幅所限，本文不再詳細(xì)給出。本文所述大素?cái)?shù)Miller-Rabin檢測(cè)程序解決了應(yīng)用Delphi開(kāi)發(fā)系統(tǒng)時(shí)信息加密和解密的大素?cái)?shù)檢測(cè)問(wèn)題。

[1]王寶杏等.RSA中大素?cái)?shù)的快速生成方法研究[J].長(zhǎng)沙通信職業(yè)技術(shù)學(xué)院學(xué)報(bào),2008,(1):56-59．

[2]謝日敏.素?cái)?shù)判定設(shè)計(jì)與實(shí)現(xiàn)[J].福建商業(yè)高等專(zhuān)科學(xué)校學(xué)報(bào),2007,(5):120-123.

[3]葉建龍.RSA加密中大素?cái)?shù)的生成方法及其改進(jìn)[J].廊坊師范學(xué)院學(xué)報(bào),2010,(2):55-57.

[4]游新娥,田華娟.一種快速的強(qiáng)素?cái)?shù)生成方法[J].通信技術(shù),2009,(2):323-325.

[5]飛思科技產(chǎn)品研發(fā)中心．Delphi分布式開(kāi)發(fā)[M].北京:電子工業(yè)出版社,2002．

[6]秦曉東等.Miller-Rabin算法研究與優(yōu)化實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2002,(10):55-57.

[7]符茂勝,孔敏,王長(zhǎng)明.GF(2m)域上橢圓曲線密碼系統(tǒng)的整體算法設(shè)計(jì)與實(shí)現(xiàn)[J].皖西學(xué)院學(xué)報(bào),2008,(2):3-5.

[8]劉學(xué)軍,邢玲玲,林和平,粟浩然.Miller-Rabin素?cái)?shù)檢測(cè)優(yōu)化算法研究與實(shí)現(xiàn)[J].信息技術(shù),2008,(12):41-147.

TP301.6

A

1673-2219（2011）12-0067-03

2011－10－10

湛江師范學(xué)院重點(diǎn)科研資助項(xiàng)目(項(xiàng)目編號(hào)W0832)。

李創(chuàng)成(1978－)，男，廣東高州人，湛江師范學(xué)院基礎(chǔ)教學(xué)學(xué)院計(jì)算機(jī)科學(xué)系助理實(shí)驗(yàn)師，碩士，從事計(jì)算機(jī)輔助教學(xué)、管理、人工智能理論研究。

（責(zé)任編校：張京華，何俊華）