文档介绍：网络安全与保密作业题目 RSA算法的介绍与实现学院电子工程学院专业信息对抗(02X31班)学生姓名郝志嬪(02X3098)、产生背景1976年以前,所有的加密方法都是同一种模式:(1)甲方选择某一种加密规则,对信息进行加密;(2)乙方使用同一种规则,对信息进行解密。由于加密和解密使用同样的规则(简称“密钥”),这被称为”对称加密算法“。这种加密模式有一个最大弱点:甲方必须把加密规则告诉乙方,否则无法解密。因此,保存和传递密钥,就成了最头疼的问题。1976年,两位美国计算机学家WhitfieldDiffie和MartinHellman,提出了一种崭新构思,可以在不直接传递密钥的情况下,完成解密。这被称为HDiffie-Hellman密钥交换算法寫这个算法启发了其他科学家。人们认识到,加密和解密可以使用不同的规则,只要这两种规则之间存在某种对应关系即可,这样就避免了直接传递密钥。这种新的加密模式被称为”非对称加密算法”,是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。(1)乙方生成两把密钥(公钥和私钥)o公钥是公开的,任何人都可以获得,私钥则是保密的。(2)甲方获取乙方的公钥,然后用它对信息加密。((3)乙方得到加密后的信息,用私钥解密。如果公钥加密的信息只有私钥解得开,那么只要私钥不泄漏,通信就是安全的。、RSA概述RSA是在1978年,由美国麻省理工学院(MIT)《获得数字签名和公开钥密码系统的方法》的论文中提出的。RSA算法是第一个既能用于数据加密也能用于数字签名的算法,因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA密钥,其中之一是保密密钥,由用户保存;另一个为公开密钥,可对外公开,甚至可在网络服务器中注册,人们用公钥加密文件发送给个人,个人就可以用私钥解密接受。这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是768个二进制位。也就是说,长度超过768位的密钥,还无法破解(至少没人公开宣布b因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。公钥加密算法中使用最广的是RSAoRSA算法研制的最初理念与目标是努力使互联网安全可靠,旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题;还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖;同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改,以保护数据信息的完整性。此外,RSA加密系统还可应用于智能IC卡和网络安全产品。三、数论知识互质关系如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime\比如,15和32没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。关于互质关系,不难得到以下结论:任意两个质数构成互质关系,比如13和61。一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如3和10o如果两个数之中,较大的那个数是质数,则两者构成互质关系,比如97和57O1和任意一个自然数是都是互质关系,比如1和99。p是大于1的整数,则p和p-1构成互质关系,比如57和56Op是大于1的奇数,则p和p-2构成互质关系,比如仃和15。欧拉函数请思考以下问题:任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)计算这个值的方法就叫做欧拉函数,以(p(n)表示。在1到8之中与8形成互质关系的是1、3、5、7,所以(p(n)=4O(p(n)的计算方法并不复杂,但是为了得到最后那个公式,需要—步步讨论。第一种情况如果n=1,则(p(1)=1o因为1与任何数(包括自身)都构成互质关系。第二种情况如果n是质数,则(p(n)=n-1。因为质数与小于它的每一个数,都构成互质关系。比如5与1、2、3、4都构成互质关系。第三种情况如果n是质数的某一个次方,即n二pAk(p为质数,k为大于等于1的整数),则如)=八严。比如(p(8)=(p(2A3)=2A3-2A2=8-4=4O这是因为只有当一个数不包含质数p,才可能与n互质。而包含质数p的数一共有pA(k-1)个,、3xp、…、pA(k-1)xp,把它们去除,剩下的就是与n互质的数。上面的式子还可以写成下面的形式:=Pk可以看出,上面的第二种情况是k=1种情况如果n可以分解成两个互质的整数之积,n=p1xp2则0仏)=0(plp2)=0(pl)0(#2)即积的欧拉函