值i-=aroodn称为除法的余数,因此,对于任意整数,可表示为:
a=[a/n]+(amodn)(2.1)
且有(a*b)modc=((amodc)*(bmodc))modc(2.2)
费马定理和欧拉定理在公钥密码学中有重要的作用。
2.1.2费马小定理
如果P是素数,a是不能被P整除的正整数,贝9:
apl=lmodp(2.3)
2.1.3欧拉定理
对于任何互质的整数a和n,有在数论中,欧拉定理,(也称费马-欧拉定理)是一个关于同余的性质。
欧拉定理表明,若n,d为正整数,且n,d互质,cp(n)在1到n中为与n互质的数的个数,贝I」:
a'(o)=1modn(2.4)
欧拉定理证明:
将1〜n中与11互质的数按顺序排布:
xl,x2x(p(n)(显然,共有
我们考虑这么一些数:
ml=a*xl;m2=a*x2;m3=a*x3m(p(n)=a*xcp(n)
1)这些数中的任意两个都不模n同余,因为如果有mS三mR(modn)(这里假定mS更大一些),就有:
mS-niR=a(xS-xR)=qn,即n能整除a(xS-xR)o但是a与n互质,a与n的最大公因子是1,而xS-xRVn,因而左式不可能被n整除。
也就是说这些数中的任意两个都不模n同余,
2)这些数除n的余数都与n互质,因为如果余数与n有公因子r,那么a*xi=pn+qi-=r(......),a*xi与n不互质,而这是不可能的。
那么这些数除n的余数,都在xl,x2/3......xcp(n)中,因为这是1〜n中与n互质的所有数,而余数乂小于n.
由1)和2)可知,数mI,m2,m3……m
故得出:
ml*m2*m3mq)(n)三xl*x2*x3x(p(n)(modn)
或者说aA[(p(n)]*(xl*x2*x3x(p(n))三xI*x2*x3xcp(n)
或者为了方便:
K{aA[(p(n)]-l}=0(modn)这里K=xl*x2*x3xcp(n)。
以上定理是我们证明RSA算法可行性的基础Hl。
2.2RSA算法的过程
N=p*q,其中p和q是素数,L为(p-1)和(q-1)的公倍数,L=lcm((p-1),(q-1))(由欧拉函数得出)。
E为与L互质的随机数,D是使得(D*E)modL=1的数。
M为明文,E为加密后的密文,{E,N}为公钥,可以公开,{D,N}为私钥由自己保管。
甲向乙发送自己的公钥,乙用公钥加密后,将密文发送给屮,甲用私钥解密,得到密文。
加密算法为:
E=MEmodNo
解密算法为:
M=EDmodNo
其中有M与E小于N,均大于Oo
2.3RSA算法的可行性
RSA算法的可逆性表明其理论上的可行性,要证明可逆性即证明:
M=CD=(ME)D=Me*dmodn
因为E*D=lmodL,这说明存在E*D=t*L+l,其中t为正整数且有t>=l。
所以:
ME*D=Mt*L~1modN=((Mt,LmodN)(MmodN))modN
因此可以通过证明Mt*L=imodN成立来证明。
欧拉定理证明有『=1modn,所以:
MtJlmodN
从理论上证明算法可逆,
第3章RSA算法的演示
在编写程序之前先理清思路,设计关键的函数的入口、出口、功能、编写出伪代码。
之后,便是进行函数编写、调试阶段。
最后,便将函数组合在一起,使之成为一个完整的程序。
3.1RSA程序的设计
程序中有判断是否为质数、求两个数的公倍数、判断是否互质、求最大互质数、山E和L求出密钥D、加密算法和解密算法。
各函数算法见附录Ao
3.2RSA算法的实现
RSA加密产生公钥和密钥过程可分为以下四步:
(1)得出公钥中的N:
随机取两个不同的素数,p和q,N=p*qo
(2)求出L:
L的值为(p-1)和(q-1)的最小公倍数,L=lcm((p-l),(q-l))o
(3)求出一个随机的公钥E:
求出一个与L互质的数E,有gcd(E,L)=lo
(4)求出一个随钥D:
密钥D应满足(D*E)modL=l;
主函数的代码如下:
iiitmain()
{
longintp,q,E,D,N,L,ming,mi;
display();
srand(time(NULL));
do
{
p=rand()%500;
}
while(p<100||!
(iszs(p)));
do
q=rand()%500;
}
while(!
(iszs(q))|p==q);
N=p*q;
L=lcm(p-hq-l);
E=gcd(L);
D=qiuD(E,L);
if(D<=0||E<=0)return0;
priiitf("p=%ldq=%ldN=%ldL=%ldE=%ldD=%ld\n",p,q,N,L,E,D);
printf(n{E=%ld,N=%ld},{D=%ld,N=%ld}\n",E,N,D,N);
printfC'Lefsdoit!
\nM);
do
{
do
{
printf(“请输入一个小于N=%ld的正整数:
”,N);scanf("%ld",&ming);
getchar();
}
while(miiig>N||ming<=0);
mi=Enciyption(E,N,ming);
miiig=Deciyption(D,N,mi);
printf(u公钥:
E=%ldN=%ld密文:
%ld\n密钥:
D=%ldN=%ld明文:
%ld\n",E,N,mi,D,N,ming);
printfC还想再来一次吗?
[y/n]:
”);
}
while(Fy,=getcharO);
printf(HSeeyou!
\iiH);
return0;
3.3RSA算法的演示
完成编程后,便做了一次测试,测试结果如图3-1所示。
图3-1命令行中运行结果
第4章结果分析与讨论
RSA密码体制安全性
任何密码都没有绝对的安全性,RSA密码体制同样如此,但RSA密码经过了20年的考验,可以说,迄今为止,没有一种相对有效的方法去由公钥破解私钥,由公钥破解私钥等价于将公钥{E,N}中的N,分解为两个质数的积,从而算岀私钥{D.N}。
将一个数有效分解为两个因子之积是数学上的一大难题,当N增大一位时,时间复杂度呈倍增长。
无论N有多长,总有一天能被质因数分解,1999年,512比特的整数由292台计算机花费5.2个月才完成。
RSA密码的优点与缺点
RSA算法理论非常简单,应用的数学原理,非常巧妙,但是其实现性不如对称密码容易。
RSA算法在实际过程中需要找到合适的P和q,得到一个合适的N,实际过程中,N有100位之多,甚至有1024位,但是如此之大的数给加密,解密都带来一泄的困难,算法没有对称密码加密快⑸。
尽管如此但是由于其相对较高的安全性使得其应用非常广泛。
于是出现了用硬件进行RSA算法计算,加快了处理速度⑹。
第5章结论
RSA密码算法在现在来说还是相当可靠的,因为迄今没有一个相当好的算法来分解一个大的整数。
此外,RSA算法可以和其他加密算法一起使用,或者用于数字签名。
通过不断的学习RSA算法的相关知识,完成了这篇论文,自身的知识有了很大的提高,了解了RSA算法的基本容后,对其进行编程测试,自身的能力也有所提高。
致
数学文化课的学习即将结束,在此,我要感费祥历老师的教育之恩。
本文离不开梁玉环老师在C语言课程中的教育,在此表示忠心的感。
参考文献
[1][日]结城浩,.图解密码技术[M].人民邮电,2015.1.
[2]周升力.RSA密码算法的研究与快速实现[J].
[3]XX百科.RSA算法—XX百科.baike.baidu./liiik?
uil=Dplx6jG5wOijYLjKRn_eu_fSuONliGYMa-lQS5UnsC30mdDcJ105jwkDFYnij-UxFdl5PtUF3TxQh4T76^j6tWupv-bp-a7mOOKC9wcHO1ZDQUQ5luG8J2qrY\-BZAZPbM
[4]白度白科.欧拉圮理一XX百科
baike.baidu./link?
url=swLTW'rWnjw4a^PFie6_Jsd9MquijKXeiifLyq6tjlmlniR.SsqImRSTqDHf6i6GJpRTRWzlDU9Ot44EdLgLU3vNlui60ye6W06oB3miIoPBdYrU5STBo3C2jU4vbM3kFKfQq
[5][日]结城浩.图解密码技术[M].人民邮电,2015.1.
[6]嘉勇.应用密码学.[M].清华大学.
附录A相关函数
/*判断是否为质数*/
longintiszs(longinta)
{
/*函数入口检查*/
longintb=0;
if(a<=l)
{
retiini0;
}
for(b=sqrt(a)+l;b>=l;b~)
{
if(0=a%b)break;
}if(l=b)
{
return1;
}
else
{
return0;
}
}
/*求两个数的公倍数L*/
longintlcm(intp,iiitq)
{
longinta=l,b=Lall=l;
if(q>0&&p>0)
a=q;
}
else
{
a=p;
}
for(b=a;b>=2;b—)
{
if(p%b==O&&q%b==O){
p=p/b;
q=q/b;all=all*b;
}
}
all=all*p*q;
returnall;
}
else
{
printf("ERRORinlcm!
\n'r);return0;
}
}
/*判断是否互质*/
longintishz(intp,intq)
longintc;
if(p>l&&q>l)
do
{
c=p%q;
p=q;q=c;
}while(c>l);if(q=l)
{
return1;
}
else
{
return0;
}
}
else
{
return0;
}
}
/*求最互质数E*/longintgcd(intL){
longinta=2;
do
a++;
}
while(!
(1=ishz(L,a)));
returna;
}
/*由E和L求出密钥D*/
longintqiuD(iiitE,intL)
{
longintD;
for(D=l;D<1000000;D++){
if((D*E)%L==l)
{
returnD;
}
}
retiini-1;
}
/*加密算法5«7
longintEncryptioii(loiigintEJongintN,longintming){
longintmi=ming;
iiiti;
for(i=l;ireturnnii;
/*解密算法匕
longintDeci^ption(longintDjongiiitNJongintmi){
longintming=mi;
longinti;
for(i=l;i{
}
returnniing;
对数学文化课程的建议
我对老师印象非常好,不过我自己认为数学之美的容偏少,可以增加一些,让同学们了解更多数学美的涵,并运用计算机技术发掘数学的美。
另外,可以线上线下同时学习,不过课时可能会增长很多,学生压力会增加。