基于DELPHI的大素數MILLER-RABIN檢測方法的實現

李創成 陳文慶

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

基于DELPHI的大素數MILLER-RABIN檢測方法的實現

李創成1陳文慶2

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

論文介紹了利用動態數組對大整數的存儲，把大整數的計算轉化為數組元素的運算，并在 Delphi中實現了大素數Miller-Rabin檢測。

大素數；動態數組；存儲；檢測

0 引 言

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

1 Delphi整型數據類型和大整數的存儲

在Delphi中整型數據類型有9種，它們的性質和表示范圍如表1所示。

表1.Delphi整型數據類型的性質及取值范圍

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

TSign=(negative,positive);

TFGInt=Record

Sign:TSign;

Number:Array Of Int64;

End;

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

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

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

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

2 素數的檢測方法

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

2.1 素數檢測方法的分類

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

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

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

2.2 Miller-Rabin素數檢測算法的基本原理

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

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

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

輸入數據：大于3待測試奇整數n。

輸出數據：返回n是否為素數。

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

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

3、計算y←ar(mod n)

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

5、j=1

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

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

8、如果y≠n-1則返回“合數”,算法結束。

9、返回“素數”。

3 大素數Miller-Rabin檢測程序的實現

大素數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”轉為大整數形式

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

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

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

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

s:=0;

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

Begin

s:=s+1;

FGIntShiftRight(temp1);

End;

r:=temp1;

ok:=true;

Randomize;

Base10 String To FGInt(inttostr(Primes[Random(1227)+1]),a);//隨機產生一整數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 結束語

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

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

[2]謝日敏.素數判定設計與實現[J].福建商業高等專科學校學報,2007,(5):120-123.

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

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

[5]飛思科技產品研發中心．Delphi分布式開發[M].北京:電子工業出版社,2002．

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

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

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

TP301.6

A

1673-2219（2011）12-0067-03

2011－10－10

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

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

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