基于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－)，男，广东高州人，湛江师范学院基础教学学院计算机科学系助理实验师，硕士，从事计算机辅助教学、管理、人工智能理论研究。

（责任编校：张京华，何俊华）