论文部分内容阅读
随着经济的发展和计算机的进步,人们对信息安全的关注越来越大.1949年,Shannon发表了“保密系统的通信理论”揭开了现代密码学的神秘面纱.1976年Diffie和Hellman在“密码学新方向”中首次提出了公钥密码体制的概念,开创了公钥密码学的新纪元.1978年,密码学家Rivest.Shamir和Adleman提出了第一个具体的基于大整数素因数分解困难性的公钥密码体制—RSA密码体制.随后一系列的公钥密码体制相继诞生,如1985年ELGamal提出的基于有限域上离散对数困难问题的ELGamal公钥密码;1986年Miller提出的基于椭圆曲线上的离散对数困难问题的椭圆曲线密码体制;2000年Lenstra和Verheul提出的基于有限域的乘法群子群的迹表示的XTR密码体制(其安全性也是基于有限域上离散对数困难问题)；基于格(1attice)中困难问题的密码体制Ajtai-Dworkls、GGH和NTRU;基于辫群(braid group)的公钥体制;以及基于纠错码的McEliece公钥体制等.另一方面,密码学家也在对已有的RSA公钥密码体制进行改进.1991年Kayama、Maurer、Okamoto和、anstone提出的环Zn上椭圆曲线RSA型公钥密码体制,即所谓的KMOV公钥密码体制.2005年,孙琦等人提出了环Zn上圆锥曲线RSA型公钥密码体制.2007年,孙琦等人又提出了环Zn上的广义圆锥曲线RSA型公钥密码体制.本文将这些对RSA改进的密码体制统称为RSA型公钥密码体制,在RSA型公钥密码体制中加密指数e和解密指数d满足条件ed≡1(mod Nn)其中Nn=1cm{p±1.q±1}.对RSA公钥密码,有很多的攻击方法,具体可以参见相关的参考文献.本文主要将对RSA的解密指数攻击的两种方法(连分数攻击以及格攻击)扩展到对整个RSA型公钥密码体制上,得到一些相应的结果如下：(1)关于RSA型公钥密码体制的连分数攻击扩展.ed≡1(mod Nn),当Nn分别为(p+1)(q+1)/2,(p+1)(q-1)/2,(p-1)(q+1)/2和(p-1)(q-1)/2四种情况时,对应的解密指数d的界分别为(?)N184,(?)/2N1/4,1/2N1/4和(?)N1/4；当Nn分别为1cm{p+1,q+1},1cm{p+1,q-1},1cm{p-1,q十1}和1cm{p-1,q-1}四种情况时,对应的解密指数d的界分别为(?)N1/4,1/(?)N1/4,1/(2(?))N1/4和(?)N1/4.亦即当解密指数d小于上述界时.可以通过公钥(N.e)来解得私钥(d.p,q),从而破解此时的密码系统.(2)本文还提出可以利用引理2来对RSA型公钥密码体制的解密指数d的界进行改进,其中引引理2.设α是一个实数,a和b为互素的正整数,且k≥1/2.若有|α-a/b|＜k/(b2)成立.则a/b为α的连分数展开式中某个渐进分数(pm)/(qm),或者是下列情况之一：(a)a/b=(spm+tpm-1)/(sqm+tqm-1),其中st<2k;(b)a/b=(spm-tpm-1)/(sqm-tqm-1),其中st<2k;(c)a/b=(spm+1+tpm-1)/(sqm+1+tqm-1),其中st<k.其中(pm,qm)=1,s,t为止整数.(3)对于RSA型公钥密码体制的格攻击.Boneh和Durfee给出了当加密指数e和解密指数d满足ed≡1(mod((p-1)(q-1))/2)的情况,本文补充了e和d满足ed≡1(mod((p+1)(q+1))/2)以及满足ed≡1(mod lcm{p-1.q-1})时的两种情况,分别得到当解密指数d<N0.292以及d<1/4(5-(?)-8γ)(其中gcd(p-1.q-1)=N(?),e=N(?)故γ为很小的正数,α为接近1的数)时,能用格攻击的方法来破解此时的密码系统.至于RSA型公钥密码体制的其他情况,可以类似的得到相应的结果.