2.1.5RSA算法中的计算问题
1.RSA的加密与解密过程
RSA的加密、解密过程都为求一个整数的整数次幂,再取模。
如果按其含义直接计算,则中间结果非常大,有可能超出计算机所允许的整数取值范围。
如上例中解密运算6677mod119,先求6677再取模,则中间结果就已远远超出了计算机允许的整数取值范围。
而用模运算的性质:
(a×b)modn=[(amodn)×(bmodn)]modn
就可减小中间结果再者,考虑如何提高加、解密运算中指数运算的有效性。
例如求x16,直接计算的话需做15次乘法。
然而如果重复对每个部分结果做平方运算即求x,x2,x4,x8,x16则只需4次乘法。
2.RSA密钥的产生
产生密钥时,需要考虑两个大素数p、q的选取,以及e的选取和d的计算。
因为n=pq在体制中是公开的,因此为了防止敌手通过穷搜索发现p、q,这两个素数应是在一个足够大的整数集合中选取的大数。
如果选取p和q为10100左右的大素数,那么n的阶为10200,每个明文分组可以含有664位(10200≈2664),即83个8比特字节,这比DES的数据分组(8个8比特字节)大得多,这时就能看出RSA算法的优越性了。
因此如何有效地寻找大素数是第一个需要解决的问题。
寻找大素数时一般是先随机选取一个大的奇数(例如用伪随机数产生器),然后用素性检验算法检验这一奇数是否为素数,如果不是则选取另一大奇数,重复这一过程,直到找到素数为止。
素性检验算法通常都是概率性的,但如果算法被多次重复执行,每次执行时输入不同的参数,算法的检验结果都认为被检验的数是素数,那么就可以比较有把握地认为被检验的数是素数。
2.1.6公钥密码体制的基本概念
在公钥密码体制以前的整个密码学史中,所有的密码算法,包括原始手工计算的、由机械设备实现的以及由计算机实现的,都是基于代换和置换这两个基本工具。
而公钥密码体制则为密码学的发展提供了新的理论和技术基础,一方面公钥密码算法的基本工具不再是代换和置换,而是数学函数;另一方面公钥密码算法是以非对称的形式使用两个密钥,两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。
可以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。
公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的,这两个问题是密钥分配和数字签字。
单钥密码体制在进行密钥分配时(看第5章),要求通信双方或者已经有一个共享的密钥,或者可籍助于一个密钥分配中心。
对第一个要求,常常可用人工方式传送双方最初共享的密钥,这种方法成本很高,而且还完全依赖信使的可靠性。
第二个要求则完全依赖于密钥分配中心的可靠性。
第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。
1976年W.Diffie和M.Hellman对解决上述两个问题有了突破,从而提出了公钥密码体制。
2.2总体方案
要实现生成公钥和密钥的功能,必须先生成两个大素数。
方法是先设定随机种子为系统当前时间,然后随即生成两个100以内的随机数,并判断其是否为素数,取出这两个素数。
然后通过调用函数生成公钥对和密钥对,同时显示出结果到屏幕上。
随后可以用公钥对明文进行加密,将加密后的秘闻显示出来。
然后可以演示用密钥对密文进行解密,并将结果显示到屏幕上。
2.3功能模块
本系统含有两个功能模块:
(1)公钥和密钥生成模块:
可以生成个100以内的素数p和q,以及n、e、d;
(2)加密和解密模块:
可以显示加密后的数据,点击解密可显示解密后数据。
系统功能界面图如下:
图2-1系统功能界面图
3系统设计
3.1算法描述
RSA算法描述:
(1)密钥的产生
①选两个保密的大素数p和q。
②计算n=p×q,φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。
③选一整数e,满足1④计算d,满足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元,因e与φ(n)互素,由模运算可知,它的乘法逆元一定存在。
⑤以{e,n}为公开钥,{d,n}为秘密钥。
(2)加密
加密时首先将明文比特串分组,使得每个分组对应的十进制数小于n,即分组长度小于log2n。
然后对每个明文分组m,作加密运算:
c≡memodn
(3)解密
对密文分组的解密运算为:
m≡cdmodn
下面证明RSA算法中解密过程的正确性。
证明:
由加密过程知c≡memodn,所以
cdmodn≡medmodn≡m1modφ(n)modn≡mkφ(n)+1modn
要获得两个随机的小于100的素数,可以首先将系统当前时间设置为随机数种子,然后对生成的随机数取100模,然后调用判断素数的函数。
要判断一个属实否为素数,可以判断数n从2到n的开方,是否能整除n。
伪代码如下:
for(i从2到n的开方;i++)
{
if(n被i整除)
则n不是素数终止循环;
if(i>n的开方)
返回n为宿舍;
}
求最大公因子的算法:
Euclid算法就是用这种方法,因gcd(a,b)=gcd(|a|,|b|),因此可假定算法的输入是两个正整数,设为d,f,并设f>d。
Euclid(f,d)
①X←f;Y←d;
②ifY=0thenreturnX=gcd(f,d);
③R=XmodY;
④X=Y;
⑤Y=R;
⑥goto②。
求乘法逆元:
推广的Euclid算法先求出gcd(a,b),当gcd(a,b)=1时,则返回b的逆元。
ExtendedEuclid(f,d)(设f>d)
①(X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d);
②ifY3=0thenreturnX3=gcd(f,d);noinverse;
③ifY3=1thenreturnY3=gcd(f,d);Y2=d-1modf;
④Q=X3Y3;
⑤(T1,T2,T3)←(X1-QY1,X2-QY2,X3-QY3);
⑥(X1,X2,X3)←(Y1,Y2,Y3);
⑦(Y1,Y2,Y3)←(T1,T2,T3);
⑧goto②。
处理明文:
将明文的每个字符提取出来将其装换为数字。
进行加密处理,将处理后的数字字符用“+”号相连。
其中加密的算法为:
求am可如下进行,其中a,m是正整数:
将m表示为二进制形式bkbk-1…b0,即
m=bk2k+bk-12k-1+…+b12+b0
因此:
例如:
19=1×24+0×23+0×22+1×21+1×20,所以
a19=((((a1)2a0)2a0)2a1)2a1
从而可得以下快速指数算法:
c=0;d=1;
Fori=kdownto0d0{
c=2×c;
d=(d×d)modn;
ifbi=1then {
c=c+1;
d=(d×a)modn
}
}
returnd.
其中d是中间结果,d的终值即为所求结果。
c在这里的作用是表示指数的部分结果,其终值即为指数m,c对计算结果无任何贡献,算法中完全可将之去掉。
解密过程:
将“+”连接的数字字符转换为数字并相加,用密钥做与加密相同的算法,即可得出明文。
3.2流程图
开始
产生素数p和q
p,q<100且为素数
N=(p-1)*(q-1)
找出e
e为素数与n互素
求出d
结束
是
是
否
否
图3-1生成公钥和私钥流程图开始
明文不为空
将明文转换为数字加密
结束
取得明文
是
否
图3-2明文加密流程图
开始
密文不为空
将密文转换为明文
结束
取得密文
是
否
图3-3密文解密流程图
4代码编写
在RSADlg.h中声明成员变量:
int m_p;
int m_q;
int m_n;
int m_code;
int m_decode;
CString m_dtxt;
CString m_etxt;
CString m_ptxt;
1.产生公钥和密钥:
voidCRSADlg:
:
OnButtonProduce()//产生公钥和密钥函数
{
UpdateData(true);
while(true)
{
srand(time(0));
m_p=rand()%100;
m_q=rand()%100;
if(isPrime(m_p)&&isPrime(m_q))
break;
}
m_n=m_p*m_q;
intfiN=(m_p-1)*(m_q-1);
//inte;
for(inti=3;i {
if(isPrime(i)&&gcd(fiN,i)==1)
{
m_code=i;
break;
}
}
Euler(m_code,fiN);
UpdateData(false);
}
代码分析:
首先设置系统的当前时间为随机种子,循环找出p和q并且调用判断素数的函数isPrime(int)使p,q都为小于100的素数,然后fiN=(m_p-1)*(m_q-1)产生fiN,产生m_n=m_p*m_q,通过调用gcd(fiN,i)找出与fiN互素的数m_code,调用uler(m_code,fiN)找出m_decode,最后UpdateData(false)刷新文本框显示出结果。
2.加密明文:
voidCRSADlg:
:
OnCode()//加密函数
{
CStringtemp;
UpdateData(true);
CStringencSt="";
CStringe2st="";
if(m_ptxt.IsEmpty())
return;
for(inti=0;i {
temp=encSt;
encSt.Format("%s%d%s",temp,power((int)m_ptxt.GetAt(i),m_code,m_n),"+");
}
m_etxt=encSt;
UpdateData(false);
}
代码分析:
首先判断明文文本框是否为空,若为空则返回。
取出明文的每个字符,将其装换为数字,通过加密函数power转换后,生成的数字字符用“+”号相连,即为密文。
调用UpdateData(false)刷新文本框,显示加密后的结果。
3.解密密文
voidCRSADlg:
:
OnDecode()//解密函数
{
intptr;
inttok;
CStringtemp="";
UpdateData(true);
CStringDecSt="";
//intt=m_etxt.GetLength();
for(inti=0;i {
ptr=m_etxt.Find("+",i);
tok=atoi(m_etxt.Mid(i,ptr-i));
temp=DecSt;
DecSt.Format("%s%c",temp,char(power(tok,m_decode,m_n)));
i=i+num(tok)+1;
}
m_dtxt=DecSt;
UpdateData(false);
}
代码分析:
计算出密文字符串的长度,循环寻找以字符“+”分隔得数字字符串,并将其转换问数字,然后调用power函数处理,将得出的数字转换为字符,将得出的字符连接起来就解密出了明文,最后调用UpdateData(false)刷新文本框,显示出解密出的结果。
4.其他函数:
intCRSADlg:
:
power(inta,intn,intm)//求出a的n次方模m的值
{
intz=1,t;
for(t=a;n>0;n>>=1)
{
if(n%2==1)z=(z*t)%m;
t=(t*t)%m;
}
return(z);
}
BOOLCRSADlg:
:
isPrime(intx)//判断整数i是否为素数
{
inti;
for(i=2;i<=(int)sqrt(x);i++)
{
if(x%i==0)
break;
}
if(i>(int)sqrt(x))
returntrue;
returnfalse;
}
intCRSADlg:
:
gcd(inta,intb)//求出a与b的公因子
{
if(a==0)
{
returnb;
}
else
{
returngcd(b%a,a);
}
}
voidCRSADlg:
:
Euler(inte,intfin)//求出e相对模fin的乘法逆元
{
intu1=1;
intu2=0;
intu3=fin;
intv1=0;
intv2=1;
intv3=e;
intv=1;
intt1,t2,t3;
intq;
intuu,vv;
intinverse,z;
while(v3!
=0)
{
q=(int)(u3/v3);
t1=u1-q*v1;
t2=u2-q*v2;
t3=u3-q*v3;
u1=v1;
u2=v2;
u3=v3;
v1=t1;
v2=t2;
v3=t3;
z=1;
}
uu=u1;
vv=u2;
if(vv<0)
inverse=vv+fin;
else
inverse=vv;
m_decode=inverse;
}
5运行与测试
5.1产生公钥和密钥
点击密钥生成,运行效果如下图:
图5-1产生公钥和密钥效果图
5.2加密与解密
1.点击加密,运行效果如下图:
图5-2加密效果图
2.点击解密,运行效果如下图:
图5-3解密效果图
总结
通过这次课程设计,我对RSA加密体制有了更进一步的了解。
遇到的主要问题是如何将明文按照比特分组并对其实现RSA加密,以及对大素数的处理。
最终大素数的处理得以实现,但明文分组并没有找到合适的方法,这就要求我在课程设计后去学习怎样为明文分组机密。
要想学好现代密码学不仅要学习好密码学相关知识,还要有很好的数学基础,还有很强的编程能力,这个课程设计是用MicrosoftVisualC++6.0的开发环境写的,这对编程要求很高,不仅要会密码学中RSA的加密机制,算法还要熟知VC++的编程方法,要对微软的MFC的基本编程方法要熟悉。
课程设计时对学生个人综合能力的检验。
任何知识和技术都不是孤立的。
要学习好密码学要牵扯到线性代数,离散数学,概率统计等数学知识,为了验证加密解密算法的正确性,还要动手编制程序,这就要求学生要对至少一种编程技术有所熟知。
对RSA加密体制还可以运用到手机等终端设备的加密,也可嵌入到其他小型化的设备中去,下一步我们讲进一步对这些方向进行研究。
致谢
感谢老师给了这次机会给我们做这次课程设计,让我们能够把平时所学的东西用上,不至于让我们觉得平时学的东西没什么用,在这短短的时间里完成了本次课程设计,要感谢朋友们的帮忙,在我困惑的时候要不是你们,我可能早就放弃了,因为你们的帮忙,我才能顺利的完成这次系统。
其实最辛苦的还是老师,请允许我向你们说声谢谢,感谢你们对我们的教诲。
在这次课程设计的过程中,我觉得我真的是获得了很多的东西,不仅仅是动手能力及编程能力得到了很大的提高,也不仅仅是在修改程序错误方面,主要是在程序编写过程中获得了大量的宝贵的经验。
此外,在这次实践过程中发现数据库是一门十分实用的课程,也体会到学好数据库对我们以后的学习,工作是十分重要的。
因而在此,我要感谢那些在实践过程中给过我帮助和鼓励的人。
最后对所有在课程设计中帮助过我的老师和同学说一声谢谢。
参考文献
1杨波.现代密码学.第2