RSA公钥密码体制中的素性检测问题

RSA公钥密码体制中的素性检测问题

赵文科

(天水师范学院数学与统计学院甘肃天水 741000) 摘要：RSA公钥密码体制的安全性是基于具有两个素因子的大数分解难题,生成两个安全大素数是保密系统安全的保证,目前要确定生成一个安全大素数是很难的,通常采用的方法是,生成随机数,再对其作素性检测.本文首先介绍了几种主要的素性检测算法,在分析其优缺点的基础上提出了一种生成安全大素数的新方法,分析表明,新方法更适合于实际应用.

关键词：大素数, 素性检测, RSA公钥密码

The Primality Testing Problem of the RSA Public Key Cryptosystem

Zhao W enke

(School of Mathematics and statistics Tianshui Normal University,

Tianshui Gansu 741000)

Abstract：The safety of the RSA public key cryptography system is based on the two element factor decomposition of large problem,generating two safety big prime is the safety guarantee of secret system . At present,it is very difficulty in generating a safety big prime, The actual method is that generating random numbers and then detecting primality in general.The paper introduces several main primality testing algorithm and puts forward a new method of generating safety big prime,based on the analysis of their advantages and disadvan- tages. The analysis shows that the new method is more suitable for the prac tical application.

Key words：big prime ,primality test ,RSA public-key cryptosystem

1引言

密码学是一门研究加密与解密技术的科学,也是一门既古老又年轻的学科,其研究可

以追溯到几千年以前战争出现的时候.古典的密码技术主要应用于政治、军事以及外交等领域,随着全球信息基础设施和各个国家信息基础的逐渐形成,计算机网络已经成为信息化社会发展的重要保证,大量的敏感信息常通过公共通信设施或计算机网络进行交换,或以数字的形式存放在计算机系统里.现代密码技术作为实现网络信息安全的核心技术,是保护数据安全的最重要工具之一,其社会价值和商用价值已经得到了充分的肯定.

公钥密码[]1是产生于20世纪70年代的一类新的密码体制.A 和B 要进行保密通信,A

使用B 的公钥将明文加密后得到的密文发送给B,B 使用自己的私钥将密文解成明文的过程即为一次基于公钥密码技术的保密通信,在这个过程中,通信信道是可以公开的.计算机网络的高速发展,为公钥密码的发展提供了很好的环境,公钥密码学诞生30余年来,在众多的公钥密码体制中,基于RSA []2算法的公钥密码体制是唯一被广泛接受并技术实现的公钥密码体制,目前已成为公钥密码的国际标准]3[.RSA 公钥密码体制具有密钥管理方便、破译难度大等优点,其公钥和私钥是一对足够大的素数.RSA 公钥密码体制的算法可以描述为:

(1)生成一对安全大素数q p ,(保密)

(2)计算q p n ?=(公开),依据Euler 定理]4[得到()()()11--=q p n ?(保密)

(3)随机生成正整数,e 满足()()n e ?,gcd 1=,e 是公开的加密密钥

(4)计算,d 满足()(),mod n e d ?≡?是d 解密密钥

对明文C 和密文P ,加密算法和解密算法分别为:

加密算法:对明文C ,密文为()n C P e mod =

解密算法:对密文P ,明文为()n P C d mod =

RSA 算法的数学基础是数论中的Euler 定理,其安全性]5[极大地依赖于模数n 的素因

子分解难度,如果n 被成功分解为q 和p 的乘积,那么就能计算出()()(),11--=q p n ?也就是说任何人都可以根据公钥e 计算出私钥,d 这就要求q p n ?=必须要足够大,使得n 在有效时间内不可分解.所以只有选择合适的安全大素数因子q 和p ,才能保证密码系统的

安全,因此RSA 公钥密码的发展离不开对素数的研究.而素数研究的一个基本问题就是如何快速有效地判别一个整数是否是素数,即素性检测问题.因此,本文将主要讨论RSA 公钥密码体制中的素性检测问题,在研究几主要的素性检测算法优缺点的基础上,提出一种新的素数生成方法,即以Miller-Rabin 算法为基础算法,在将待测数送入检测程序之前先对其作预处理生成伪素数,通过Miller-Rabin 检测算法生成强伪素数,最后采用Pocklington 定理]6[对生成的强伪素数进行确定性验证,新的素数生成方法对提高RSA 密钥的产生速度具有现实意义.

2素数定理

素数,就是除了1和它自身以外再不能被其它数整除的数.素数在整数中的分布]7[是

极不规律的,素数越大,其分布越稀疏.

定理1 素数的个数是无限的

证明 假设正整数中只k 有个素数,,,,,21k p p p 121+=k p p p n 令,1>n 则.n 若为素

数,n 则与k p p p ,,,21 与都不相等,这与只k 有个素数的假设相矛盾.n 若不是素数,n 则一定存在一个素数因子p ,k i p p i ,2,1,=≠且,否则由k p p p p 21|于,以及n |p 及,所1|p 以,

这p 与是素数相矛盾,p 故k p p p ,,21与都不相等,这与只k 有个素数的假设相矛盾.

因此,存在无穷多个素数,即素数的个数是无限的.

尽管素数的分布极不规律,但素数分布函数却有着如下的良好性质.

定义1 x 设是大于1的正整数,是p 素数,则称

()∑≤=x

p x 1π (1)

为素数分布函数.

依据定义1可知,()是x π不大于正整数x 的所有素数的个数,通过()x π对的渐进性研

究,得到如下定理:

定理2(素数定理)素数分布函数()是x π的x x

ln 渐进,即

()1ln lim =∞→x

x x x π (2) 依据定理2,当x 足够大时,()x x

x ln ≈π有.

定理3 大于1的正整数n 是素数的充分必要条件是:

()()11+≡+n n x x ()n mod (3)

在整系数多项式[]x Z 集合中成立.由[]x Z 于是个环,故(3)式也可表示为:

()()()()[]x x q x nq x x n n Z ∈=+-+,11 (4)

证明 必要性:2≥n 设,且n 是一个素数,由二项式定理得

()1!!!)1(1

1+-+=+--=∑r n n r n n x

r n r n x x (5)

因()11≥-n 为,所以(5)式中()r n n r x r n r n --=∑

-11

!!!的不会缺项,且各项系数均为正整数.又由于n 是素数,所以在系数 ()()()

!11!!!

r r n n n r n r n +--=-

中,必有()()11!|+--r n n r ,从而上式可写r nC 为,,Z ∈r C 因此,式(5)可写为:

()()()[]x x q x nq x x n n

Z ∈++=+,11. (6)

故必要性得证. 充分性:n 设是一个合数,存n 在的一个幂k 为的素数因p 子,其1≥k 中,.1>p 取出式(5)右端的一项

()()

p

n x p p n n n -+--!11

1,,1+--p n n 因为除以时p ,余数分别为,1,,1 -p 所以n 的素因子分解中只能出现1-k p 而不能n 被整除.从而它不能[]x Z 在()n mod 中为0,又因为式(5)右端各项对x 的幂不同且不能相消,所以

()()011≡+-+n n

x x ()n mod

[]x Z 在中不能成立.故充分性得证. 3素性检测算法

由于目前的水平在有效时间]8[内确定地生成符合RSA 算法要求的安全大素数是不

可实现的,因此实际应用中都是对生成的随机大整数进行素性检测确定安全大素数的.目前的素数生成流程图可以表示为如图1.其关键环节就是快速有效地判断一个随机生成的整数n 是否是素数,即素性检测过程.

图1

一般地,素性检测算法可分为两类,即确定性素性检测算法和概率性素性检测算法;确

定性素性检测算法的判断精度很高,但算法的执行效率很低;概率性素性检测算法的执行效率比较高,但是存在着将一部分合数误判为素数的风险.

3.1确定性素性检测算法

确定性素性检测]9[算法总是能输出一个素数,但生成素数的效率很低,一般认为此算

法在有效时间内生成满足RSA 算法要求的大素数是不可能的.

3.1.1 试除法

试除法是素性检测算法最原始的方法,假设n 是待检测数,算法过程如下:

(1)从2开始试除n ,若2|n ,则n 不是素数,否则转(2)

(2)用3试除n ,若3|n ,则n 不是素数,否则转(3)

(3)用4试除n ,若4|n ,则n 不是素数,否则转(4)

(4)

(k )p 用试除n ,,n p >且,|n p 若则n 不是素数,否则n 是素数;退出检测

虽然这种算法可以通过只检测奇数,或者通过运用一个从n 2到之间的素数表得到

改进,但是其计算复杂度???

? ??22n

O 仍然是指数增长的,也就是说,如果n 非常大,此算法在有效时间内是不可能实现的.

3.1.2 Lucus 素性检测法

N n ∈设,存在一个正整数,a ,1n a <<且(),mod 11n a n ≡-若对的1-n 每一个素数因子

随机整数n

n 是否是素数？ 是

输出n

否

p 都有()

(),1mod 1≠-n a p n 这样的是n 素数.

此算法需要知道的1-n 所有素因子,因此算法执行效率也很低.

3.2概率性素性检测算法

概率性素性检测]10[算法生成的数是素数的概率为,1ε-其中ε为素性检测方法中可

控制的任意小但不为0的数.在RSA 公钥密码体制中,合数被误判为素数实施加密和解密时,对数据的安全性威胁是可以接受的,因此当前广泛采用并被深入研究的是概率性素性检测算法.

3.2.1 Solovag-Strassen 算法

生成随机整数a ,使得,0n a ≤≤若(),1,gcd ≠n a 则n 不是素数;否则计算(),,]4[n a J 若

()()

(),mod ,21n a n a J n -≡则n 通过检测,可能是素数;否则n 不是素数.当通过t 次检测后,被检测数是合数的概率不超过.21

t 因此,这个算法的正确性至少为,21当t 足够大时,是t 21

一个

很小的数.此算法的时间复杂度]11[()()32log n O 为.

3.2.2 Miller -Rabin 素性检测算法

设待检测数为,p 计算b (b 是2整除1-p 的最大次数),然后由m p b ?+=21公式计算

出.m 进入检测

(1)输入:一个小p 于且大于1的随机a 数

输出:p 是素数或p 不是素数

(2)设,0=j ()p a z m mod =计算

(3)若z 与11-p 或同余,p 则通过检测,可能是素数

(4)0>j 若且1=z ,则p 不是素数

(5)令,1+=j j b j <如果且z 1-p 与不同余,则计算(),mod 2p z z =然后回到步骤(4).如

果z 1-p 与同余,p 则通过检测,可能是素数

(6)b j =若且z 与1-p 不同余,则p 不是素数

(7)退出

该检测算法是一个多项式时间算法,执行效率较高,当被检测数通过t 次检测时,被检

测数不是素数的概率不超过.41

t 当通过检测的次数t 足够大时,n 不是素数是一件小概率

事件,此算法的算法复杂度和Solovag-Strassen 算法一样为()(),log 32n O 但其每次检测过程中的误判率仅41

为.

4生成素数的新方法

在传统的试除法、Lucas 算法、Miller —Rabin 算法和Solovag-Strassen 算法的基础上,

本文提出了一种新的素数生成、检测方法.先对随机产生的大整数用素数筛法进行预处理生成伪素数,再用基于Miller —Rabin 检测算法的优化算法进行多次检测生成强伪素数,最后将生成的强伪素数用Pocklington 定理进行素数确定性验证,通过这样的确定性验证的强伪素数必定是素数.

4.1预处理生成伪素数

对随机产生的大整数,如果直接进入后面的素性检测会比较耗时,所以在把大整数送

入到素性检测程序前,先将其中的合数和以5为个位的数过滤掉.然后再选取一组小素数,采用素数筛选的方法生成伪素数s ,算法为:

(1)输入:随机产生预处理后的大整数n

输出:伪素数s

(2)选取一组小素[]i a 数

(3)0=i

(4)[]()i a n y mod =计算

(5)若,0≠y 则n 可能是素数,,1+=i i 转至(4);否则,转至(6)

(6)n 若通过所有[]i a 的筛选,则n 是伪素数;否则,,2+=n n 转至(1)

4.2强伪素数的生成

对于4.1节中生成的伪素数,可以根据下面的基于Miller —Rabin 检测算法的优化算

法生成强伪素数p ,算法如下:

(1)输入:4.1节中生成的伪素数s

输出:强伪素数

p

(2)12-=s r

(3)将r 进入Miller —Rabin 检测,若r 能通过()20>K K 次检测,则r 是伪素数,转至(6)

(4)s r r 2+=

(5)若r 的二进制长度大于要生成的素数p 的二进制长度,则r 是伪素数,转至(1);否则,

转至(3)

(6)12+=r p

(7)p 若能通过()20>K K 次Miller —Rabin 检测,p 则是强伪素数;否则,转至(1)

(8)退出

4.3素数的确定性验证

这里采用Pocklington 定理对4.2节生成的强伪素数进行验证,由于基于Pocklington

定理的素数生成方法是确定性素数生成方法,所以通过验证的强伪素数必定是素数,但是验证中需要已知1-p 的部分素数因子.算法如下:

(1)输入:1-p

输出:安全大素数q

(2)分解,1-p 使得F R p ?=-1,其中-

>p F

(3)分解,F 使得∏==

r j j x F 1,其()r j x j ,,2,1 =中为不同的素数

(4)1=a

(5)1+=a a (6)若()()1mod 1=-p a p ,则转至(8)

(7)转至(5);否则p 可能不是素数,转至(9)

(8)若对任意的(),,,2,1r j j =,1),1gcd(1

=--p a

j q p 则p 是素数,否则转至(5)

(9)退出 在生成安全大素数的新方法中,由于预处理阶段只是选用了一部分小素数进行过滤

筛选,因此不能说未被这些小素数整除的就一定是素数,因而应继续执行接下来的Miller —Rabin 检测,这种算法效率的提高完全依赖于小素数对大部分合数的过滤作用,但对于不含有小素数组中素因子的素数来说,过滤是一种浪费,因此总的来说速度的提升与小素

数组元素的个数成正相关,但当元素个数达到某个值的时候,也就是小素数组因子的过滤效果达到最佳状态的时候,再增加元素个数,就只能使检测时间增加.

5结束语

大素数的生成是构造RSA密钥的关键,因此大素数的生成和检测一直都是公钥密码学中的一个重要领域.本文主要探讨了RSA公钥密码体制中安全大素数的生成和检测的基本原理及其算法,在分析传统检测算法的优缺点的基础之上,提出了一种新的素数生成方法,为安全大素数的产生提供了一条新的途径,强化了素性检测算法的预处理过程之后,使用基于Miller-Rabin的优化算法进行素性检测,最后,为生成确定性安全大素数,又对生成的强伪素数作了基于Pocklington定理的素数确定性验证,新的素数生成、检测方法为RSA公钥密码体制的加密技术提供了新的素材,具有一定的实际应用价值.

在提高素性检测速度及效率方面还有很多问题需要在接下来的工作中研究:

(1)大数的存储问题,由于待检测和要生成的数都很大,如果采用数组存储的方式会使得内存开销很大,可以考虑采用其他存储形式.

(2)可以考虑将Miller-Rabin算法改成更加先进的算法,从而加快素数检测算法的执行效率.

参考文献

[1] Diffie W,Hellman M.A new direction in cryptography[J].IEEE TransonInfotheory,1976,

22(6):644-654.

[2] Rivest RI,Shamir A,Adleman L.A method for obtaining digital signatures and public-key

Crypto system[J].Comm ACM,1978,21(2):120-126.

[3] 陈少真.密码学基础[M].北京:科学出版社,2008:177-184.

[4] 颜松远.计算数论[M].北京:清华大学出版社,2008:121-125.

[5] 孙淑玲.应用密码学[M].北京:清华大学出版社,2004:46-48.

[6] 陈鲁生,沈世镒.现代密码学[M].北京:科学出版社,2002:87-90.

[7] 刘学军.Miller-Rabin素性检测优化算法研究与实现[J].信息技术,2008,12:141-147.

[8]王萍,廖芳燕.RSA算法中快速生成大素数方法的改进[J].重庆文理学院学报(自然科学

版),2009,6:9-11.

[9] 雷文,邱玲,张弘.一种大素数快速生成算法设计与实现[J].四川理工学院学报(自然科学

版),2011,6:313-316.

[10] 李彪,左黎明,谢环.素数确定性算法分析[J].计算机技术与发展,2011,8:26-29.

[11] 刘明华,余启港.RSA公钥密码算法中大素数的生成及素性检测[J].中南民族大学学报(自然

科学版),2004,12:94-96.

致谢

在经过将近半年的努力后,本毕业论文即将告以尾声,本文从选题到资料的收集以及撰写过程都经过精心地考虑、仔细地查阅和细心的修改.在此,我首先要感谢我的指导教师左为平老师,不管是论文的选题还是撰写,以及资料的查阅等方面,他都给了我莫大的帮助与启发,尤其是在论文的几次修改过程中,左老师以他广博的学识、严谨的治学精神和耐心的指导态度才使我的论文顺利完成.再次谨向左老师致以诚挚的谢意和崇高的敬意.

同时,我要对编撰本论文参考文献的所有学术专家和老师致以真挚的谢意,是他们出版的书籍与发表的学术论文给了我很大的启示与指导,才将论文完成.

其次,我在即将毕业之前要感谢数学与统计学院所有的老师四年来对我的细心教育与培养,让我在四年的学习生涯中不仅学到了扎实的专业知识,而且他们的言传身教使我受益非浅,他们严谨的治学态度和耐心教导学生的精神也是我永远学习的榜样,并将积极影响着我今后的学习和工作.

最后我还要感谢我的学校——天水师范学院四年来对我的栽培.