基于DELPHI的大素數(shù)MILLER-RABIN檢測方法的實現(xiàn)

李創(chuàng)成 陳文慶

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

基于DELPHI的大素數(shù)MILLER-RABIN檢測方法的實現(xiàn)

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

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

論文介紹了利用動態(tài)數(shù)組對大整數(shù)的存儲，把大整數(shù)的計算轉(zhuǎn)化為數(shù)組元素的運算，并在 Delphi中實現(xiàn)了大素數(shù)Miller-Rabin檢測。

大素數(shù)；動態(tài)數(shù)組；存儲；檢測

0 引 言

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

1 Delphi整型數(shù)據(jù)類型和大整數(shù)的存儲

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

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

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

TSign=(negative,positive);

TFGInt=Record

Sign:TSign;

Number:Array Of Int64;

End;

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

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

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

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

2 素數(shù)的檢測方法

大素數(shù)的選取是構造RSA密鑰的關鍵。因此大素數(shù)的產(chǎn)生與檢測在密碼學領域成為一個重要課題。檢測素數(shù)的一般方法可以分為兩類：即確定性素數(shù)產(chǎn)生方法和概率性素數(shù)產(chǎn)生方法。

2.1 素數(shù)檢測方法的分類

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

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

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

2.2 Miller-Rabin素數(shù)檢測算法的基本原理

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

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

Miller Rabin測試算法的具體如下：

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

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

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

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

3、計算y←ar(mod n)

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

5、j=1

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

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

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

9、返回“素數(shù)”。

3 大素數(shù)Miller-Rabin檢測程序的實現(xiàn)

大素數(shù)Miller-Rabin檢測方法的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);//隨機產(chǎn)生一整數(shù)a

FGInt Mont Gomery Mod Exp(a,m,n,y);//利用MontGomery算法計算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é)束語

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

[1]王寶杏等.RSA中大素數(shù)的快速生成方法研究[J].長沙通信職業(yè)技術學院學報,2008,(1):56-59．

[2]謝日敏.素數(shù)判定設計與實現(xiàn)[J].福建商業(yè)高等?？茖W校學報,2007,(5):120-123.

[3]葉建龍.RSA加密中大素數(shù)的生成方法及其改進[J].廊坊師范學院學報,2010,(2):55-57.

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

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

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

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

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

TP301.6

A

1673-2219（2011）12-0067-03

2011－10－10

湛江師范學院重點科研資助項目(項目編號W0832)。

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

（責任編校：張京華，何俊華）