RSA算法 1978年就出现了这种算法,它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作,也很流行。算法的名字以发明者的名字命名:Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。 RSA的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大素数(大于100个十进制位)的函数。据猜测,从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 密钥对的产生。选择两个大素数,p 和q 。计算:n = p * q 然后随机选择加密密钥e,要求e 和( p - 1 ) * ( q - 1 )互质。最后,利用Euclid 算法计算解密密钥d, 满足e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )其中n和d也要互质。数e和n是公钥,d是私钥。两个素数p和q 不再需要,应该丢弃,不要让任何人知道。加密信息m(二进制表示)时,首先把m分成等长数据块m1 ,m2,..., mi ,块长s,其中2^s <= n, s 尽可能的大。对应的密文是:ci = mi^e ( mod n ) ( a ) 解密时作如下计算:mi = ci^d ( mod n ) ( b ) RSA 可用于数字签名,方案是用( a ) 式签名,( b )式验证。具体操作时考虑到安全性和m信息量较大等因素,一般是先作HASH 运算。RSA 的安全性。RSA的安全性依赖于大数分解,但是否等同于大数分解一直未能得到理论上的证明,因为没有证明破解RSA 就一定需要作大数分解。假设存在一种无须分解大数的算法,那它肯定可以修改成为大数分解算法。目前,RSA的一些变种算法已被证明等价于大数分解。不管怎样,分解n是最显然的攻击方法。现在,人们已能分解140多个十进制位的大素数。因此,模数n必须选大一些,因具体适用情况而定。 由于进行的都是大数计算,使得RSA最快的情况也比DES慢上100倍,无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。 */ #include
非对称加密实验 【实验环境】 ISES客户端 Microsoft CLR Debugger 2005或其它调试器 【实验内容】 通过运算器工具实现RSA和ElGamal算法的加解密计算 手工计算RSA密钥并检验,将其应用于签名中并验证 对RSA密钥生成、RSA密钥加密、ElGamal参数生成、ElGamal密钥生成和ElGamal加密进行算法跟踪 非对称加密实验 【实验原理】 非对称密码体制又称为公钥密码体制,加解密使用公私钥密钥对,私钥由密钥拥有者保管,公钥可以公开,基于公开渠道进行分发,解决了对称密钥体制中密钥管理、分发和数字签名等难题。 一、 RSA算法 RSA公钥算法由Rivest、Shamir、Adleman于1978年提出的,是目前公钥密码的国际标准。算法的数学基础是Euler定理,是基于Deffie-Hellman的单项陷门函数的定义而给出的第一个公钥密码的实际实现,其安全性建立在大整数因子分解的困难性之上。 RSA算法的明文空间M=密文空间C=Z整数,其算法描述如下: n (1) 密钥生成 随机选择两个大素数p和q,计算n=p?q,;选择一个随机整数e<,满足,计算整数;公开公钥(n,e),安全的销毁p、q和,并保留(d,n)作为私钥。
(2) 加密 (3) 解密 使用中国剩余定理可以加速RSA密码算法的实现。 二、 ElGamal算法 ElGamal算法是Deffie-Hellman单项陷门函数的一个成功应用,把函数转化为公钥加密体制,其安全性建立在有限域上的离散对数问题。 ElGamal算法的描述如下: (1) 密钥生成 随机选择一个素数p,计算p个元素的有限域的乘法群的一个随机乘法生成元g;均匀随机地在模p-1的整数集合中选取x,计算;把(p,g,y)作为公钥公开,把(p,g,x)作为私钥。 (2) 加密 均匀随机地在模p-1的整数集合中选取k,消息m
RSA加密解密的设计与实现
上海电力学院 《应用密码学》课程设计 题目: RSA加密解密的设计与实现 院系:计算机科学与技术学院 专业年级:级 学生姓名:李正熹学号: 3273 指导教师:田秀霞 1月 8日 目录
目录 1.设计要求 2.开发环境与工具 3.设计原理(算法工作原理) 4.系统功能描述与软件模块划分 5.设计核心代码 6.参考文献 7. 设计结果及验证 8. 软件使用说明 9. 设计体会 附录 1.设计要求
1 随机搜索大素数,随机生成公钥和私钥 2 用公钥对任意长度的明文加密 3 用私钥对密文解密 4 界面简洁、交互操作性强 2.开发环境与工具 Windows XP操作系统 Microsoft Visual C++ 6.0 1.创立rsa工程
2.在rsa工程中创立 3273 李正熹cpp文件 3.设计原理 RSA算法简介 公开密码算法与其它密码学完全不同,它是基于数学函数而不是基于替换或置换。与使用一个密钥的对称算法不同,公开密钥算法是非对称的,而且它使用的是两个密钥,包括用于加密的公钥和用于解密的私钥。公开密钥算法有RSA、Elgamal等。 RSA公钥密码算法是由美国麻省理工学院(MIT)的Rivest,Shamir和Adleman在1978年提出来的,并以她们的名字的有字母命名的。RSA是第一个安全、实用的公钥密码算法,已经成为公钥密码的国际标准,是当前应用广泛的公钥密码体制。
RSA的基础是数论的Euler定理,其安全性基于二大整数因子分解问题的困难性,公私钥是一对大素数的函数。而且该算法已经经受住了多年深入的密码分析,虽然密码分析者既不能证明也不能否定RSA的安全性,但这不恰恰说明该算法有其一定的可信度。 4.系统功能描述与软件模块划分 功能:
RSA加密算法的基本原理 1978年RSA加密算法是最常用的非对称加密算法,CFCA 在证书服务中离不了它。但是有不少新来的同事对它不太了解,恰好看到一本书中作者用实例对它进行了简化而生动的描述,使得高深的数学理论能够被容易地理解。我们经过整理和改写特别推荐给大家阅读,希望能够对时间紧张但是又想了解它的同事有所帮助。 RSA是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名。RSA以它的三个发明者Ron Rivest,Adi Shamir,Leonard Adleman的名字首字母命名,这个算法经受住了多年深入的密码分析,虽然密码分析者既不能证明也不能否定RSA的安全性,但这恰恰说明该算法有一定的可信性,目前它已经成为最流行的公开密钥算法。 RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数(100到200位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于分解两个大素数之积(这是公认的数学难题)。 RSA的公钥、私钥的组成,以及加密、解密的公式可见于下表: 可能各位同事好久没有接触数学了,看了这些公式不免一头雾水。别急,在没有正式讲解RSA加密算法以前,让我们先复习一下数学上的几个基本概念,它们在后面的介绍中要用到: 一、什么是“素数”? 素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如,15=3*5,所以15不是素数;又如,12=6*2=4*3,所以12也不是素数。另一方面,13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”(或“互素数”)? 小学数学教材对互质数是这样定义的:“公约数只有1的两个数,叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种(不限于此): (1)两个质数一定是互质数。例如,2与7、13与19。 (2)一个质数如果不能整除另一个合数,这两个数为互质数。例如,3与10、5与26。(3)1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。(4)相邻的两个自然数是互质数。如15与16。 (5)相邻的两个奇数是互质数。如49与51。 (6)大数是质数的两个数是互质数。如97与88。 (7)小数是质数,大数不是小数的倍数的两个数是互质数。如7和16。 (8)两个数都是合数(二数差又较大),小数所有的质因数,都不是大数的约数,这两个数是互质数。如357与715,357=3×7×17,而3、7和17都不是715的约数,
RSA加密算法加密与解密过程解析 1.加密算法概述 加密算法根据内容是否可以还原分为可逆加密和非可逆加密。 可逆加密根据其加密解密是否使用的同一个密钥而可以分为对称加密和非对称加密。 所谓对称加密即是指在加密和解密时使用的是同一个密钥:举个简单的例子,对一个字符串C做简单的加密处理,对于每个字符都和A做异或,形成密文S。 解密的时候再用密文S和密钥A做异或,还原为原来的字符串C。这种加密方式有一个很大的缺点就是不安全,因为一旦加密用的密钥泄露了之后,就可以用这个密钥破解其他所有的密文。 非对称加密在加密和解密过程中使用不同的密钥,即公钥和私钥。公钥用于加密,所有人都可见,私钥用于解密,只有解密者持有。就算在一次加密过程中原文和密文发生泄漏,破解者在知道原文、密文和公钥的情况下无法推理出私钥,很大程度上保证了数据的安全性。 此处,我们介绍一种非常具有代表性的非对称加密算法,RSA加密算法。RSA 算法是1977年发明的,全称是RSA Public Key System,这个Public Key 就是指的公共密钥。 2.密钥的计算获取过程 密钥的计算过程为:首先选择两个质数p和q,令n=p*q。 令k=?(n)=(p?1)(q?1),原理见4的分析 选择任意整数d,保证其与k互质 取整数e,使得[de]k=[1]k。也就是说de=kt+1,t为某一整数。
3.RSA加密算法的使用过程 同样以一个字符串来进行举例,例如要对字符串the art of programming 进行加密,RSA算法会提供两个公钥e和n,其值为两个正整数,解密方持有一个私钥d,然后开始加密解密过程过程。 1. 首先根据一定的规整将字符串转换为正整数z,例如对应为0到36,转化后形成了一个整数序列。 2. 对于每个字符对应的正整数映射值z,计算其加密值M=(N^e)%n. 其中N^e表示N的e次方。 3. 解密方收到密文后开始解密,计算解密后的值为(M^d)%n,可在此得到正整数z。 4. 根据开始设定的公共转化规则,即可将z转化为对应的字符,获得明文。 4.RSA加密算法原理解析 下面分析其内在的数学原理,说到RSA加密算法就不得不说到欧拉定理。 欧拉定理(Euler’s theorem)是欧拉在证明费马小定理的过程中,发现的一个适用性更广的定理。 首先定义一个函数,叫做欧拉Phi函数,即?(n),其中,n是一个正整数。?(n)=总数(从1到n?1,与n互质整数) 比如5,那么1,2,3,4,都与5互质。与5互质的数有4个。?(5)=4再比如6,与1,5互质,与2,3,4并不互质。因此,?(6)=2
一、RSA加密算法的原理 (1)、RSA算法描述 RSA公钥密码体制的基本原理:根据数论,寻求两个大素数比较简单,而将他们的乘积分解开则极为困难。 (2)、RSA算法密钥计算过程: 1.用户秘密选取两个大素数p 和q,计算n=pq,n称为 RSA算法的模数,公开。 2.计算出n的欧拉函数Φ(n) = (p-1)×(q-1),保密。 3.从(1, Φ(n))中随机地选择一个与Φ(n)互素的数e作为加 密密钥,公开。 4.计算出满足下式的d 作为解密密钥,保密。 ed=1 mod Φ(n) (3)、RSA算法密钥: 加密密钥PK = |e, n| 公开 解密密钥SK = |d, n| 保密 (4)、RSA算法加密解密过程: RSA算法属于分组密码,明文在加密前要进行分组,分组 的值m 要满足:0 < m < n 加密算法:C = E(m) ≡me mod n 解密算法:m = D(c) ≡cd mod n (5)、RSA算法的几点说明: 1.对于RSA算法,相同的明文映射出相同的密文。
2.RSA算法的密钥长度:是指模数n的长度,即n的二进 制位数,而不是e或d的长度。 3.RSA的保密性基于大数进行因式分解很花时间,因此, 进行RSA加密时,应选足够长的密钥。512bit已被证明 不安全,1024bit也不保险。 4.RSA最快情况也比DES慢100倍,仅适合少量数据的加 密。公钥e取较小值的方案不安全。 二.RSA公钥加密算法的编程实现 以下程序是java编写的实现RSA加密及解密的算法 import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.NoSuchAlgorithmException; import java.security.SecureRandom; import java.security.interfaces.RSAPrivateKey; import java.security.interfaces.RSAPublicKey; import javax.crypto.Cipher; //RSATest类即为测试类 public class RSATest { //主函数 public static void main(String[] args) { try { RSATest encrypt = new RSATest(); String encryptText = "encryptText";//输入的明文 KeyPair keyPair = encrypt.generateKey();//调用函数生成密钥对,函数见下 RSAPrivateKey privateKey = (RSAPrivateKey) keyPair.getPrivate(); RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic(); byte[] e = encrypt.encrypt(publicKey, encryptText.getBytes()); //调用自己编写的encrypt函数实现加密, byte[] de = encrypt.decrypt(privateKey, e); //调用自己编写的decrypt函数实现解密, System.out.println(toHexString(e)); //输出结果,采用ASSIC码形式
<2> 非对称密钥加密又叫作公开密钥加密算法。在非对称加密体系中,密钥被分解为一对(即一把公开密钥或加密密钥和一把私有密钥或解密密钥)。这对密钥中的任何一把都可作为公开密钥(加密密钥)通过非保密方式向他人公开,而另一把则作为私有密钥(解密密钥)加以保存。公开密钥用于对机密性信息的加密,私有密钥则用于对加密信息的解密。私有密钥只能由生成密钥对的用户掌握,公开密钥可广泛发布,但它只对应于生成该密钥的用户。公开密钥加密技术解决了密钥的发布和管理问题,是目前商业密码的核心。使用公开密钥技术,数据通信的双方可以安全的确认对方的身份和公开密钥。非对称密钥加密算法主要有RSA、PGP等。 ----数据加密技术可以分为三类,即对称型加密、不对称型加密和不可逆加密。 ----对称型加密使用单个密钥对数据进行加密或解密,其特点是计算量小、加密效率高。但是此类算法在分布式系统上使用较为困难,主要是密钥管理困难,使用成本较高,保安性能也不易保证。这类算法的代表是在计算机专网系统中广泛使用的DES(Digital Encryption Standard)算法。 ----不对称型加密算法也称公用密钥算法,其特点是有二个密钥(即公用密钥和私有密钥),只有二者搭配使用才能完成加密和解密的全过程。由于不对称算法拥有两个密钥,它特别适用于分布式系统中的数据加密,在Internet中得到了广泛应用。其中公用密钥在网上公布,为数据源对数据加密使用,而用于解密的相应私有密钥则由数据的收信方妥善保管。 ----不对称加密的另一用法称为“数字签名(Digital signature)”,即数据源使用其密钥对数据的校验和(Check Sum)或其他与数据内容有关的变量进行加密,而数据接收方则用相应的公用密钥解读“数字签名”,并将解读结果用于对数据完整性的检验。在网络系统中得到应用的不对称加密算法有RSA算法和美国国家标准局提出的DSA算法(Digital Signature Algorithm)。不对称加密法在分布式系统中应用时需注意的问题是如何管理和确认公用密钥的合法性。 2、对称性加密和非对称性加密 根据密钥技术的不同,可分为对称加密和非对称加密两种方法;对称加密是指用单一的密钥对明文进行加密,同时必须用该密钥对密文进行解密,加密和解密双方必须知道该密钥。非对称加密技术又称公共密钥技术,密钥成对存在,分别称为私有密钥(private key)和公共密钥(public key);在加密过程采用公共密钥,在解密过程采用私有密钥。 由此可以看出,非对称性加密技术使密钥更加安全,一般用于对密钥进行管理;但是非对称加密技术速度很慢,在数据传输过程中的加密一般采用对称加密算法。 对于VPN网关产品来说,因为非对称加密算法太慢,所以一般采用对称加密算法进行数据传输加密。 3、数据加密强度和加密算法
实验四 RSA加解密算法的实现 一.实验目的 1、对算法描述可进行充分理解,精确理解算法的各个步骤。 2、完成RSA软件算法的详细设计。 3、用C++完成算法的设计模块。 4、编制测试代码。 二.实验内容 1.实验原理及基本技术路线图(方框原理图) 加密过程: 第一步,用户首先输入两个素数p和q,并求出 n = p*q,然后再求出n的欧拉函数值phi。 第二步,在[e,phi]中选出一个与phi互素的整数e,并根据e*d ≡1(mod phi),求出e的乘法逆元。至此我们已经得到了公开密钥{e,n}和秘密密钥{d,n}。 第三步,让用户输入要进行加密的小于n一组正整数(个数不超过MAXLENGTH=500),输入以-1为结束标志,实际个数存入size中,正整数以clear[MAXLENGTH]保存。 第四步,对第三步所得的明文clear[MAXLENGTH]进行加密。遍历clear[size],对每一个整数用以下算法进行加密,并将加密后的密文保存在Ciphertext[MAXLENGTH]中。 注意:此处不能用m2[j] = clear[j] ^ e整数的幂,因为当e和clear[j]较大时,会发生溢出,至使出现无法预料的结果。 第五步,输出加密后的密文。 解密过程: 第一步,根据在以上算法中求出的解密密钥[d,phi],对加密后的密文Ciphertext[MAXLENGTH]进行解密,结果保存在DecryptionText[MAXLENGTH]中,算法如下: 第二步,输出对加密前的明文和加密并解密后的密文进行比较,判断两个数组是否一致,从而得知算法是否正确。
2.所用仪器、材料(设备名称、型号、规格等) 计算机一台、vc6.0 3.实验方法、步骤 #include
密码学课程报告《RSA加密解密算法》 专业:信息工程(信息安全) 班级:1132102 学号:201130210214 姓名:周林 指导老师:阳红星 时间:2014年1月10号
一、课程设计的目的 当前最著名、应用最广泛的公钥系统RSA是在1978年,由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。 RSA算法是第一个既能用于数据加密也能用于数字签名的算法,因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥,其中之一是保密密钥,由用户保存;另一个为公开密钥,可对外公开,甚至可在网络服务器中注册,人们用公钥加密文件发送给个人,个人就可以用私钥解密接受。为提高保密强度,RSA密钥至少为500位长,一般推荐使用1024位。 公钥加密算法中使用最广的是RSA。RSA算法研制的最初理念与目标是努力使互联网安全可靠,旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题;还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖;同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改,以保护数据信息的完整性。此外,RSA加密系统还可应用于智能IC卡和网络安全产品。 二、RSA算法的编程思路 1.确定密钥的宽度。 2.随机选择两个不同的素数p与q,它们的宽度是密钥宽度的1/2。 3.计算出p和q的乘积n 。 4.在2和Φ(n)之间随机选择一个数e , e 必须和Φ(n)互素,整数e 用做加密密钥(其中Φ(n)=(p-1)*(q-1))。 5.从公式ed ≡ 1 mod Φ(n)中求出解密密钥d 。 6.得公钥(e ,n ), 私钥 (d , n) 。 7.公开公钥,但不公开私钥。 8.将明文P (假设P是一个小于n的整数)加密为密文C,计算方法为: C = Pe mod n 9.将密文C解密为明文P,计算方法为:P = Cd mod n 然而只根据n和e(不是p和q)要计算出d是不可能的。因此,任何人都可对明文进行加密,但只有授权用户(知道d)才可对密文解密 三、程序实现流程图: 1、密钥产生模块:
可能各位同事好久没有接触数学了,看了这些公式不免一头雾水。别急,在没有正式讲解RSA加密算法以前,让我们先复习一下数学上的几个基本概念,它们在后面的介绍中要用到: 一、什么是“素数”? 素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如,15=3*5,所以15不是素数;又如,12=6*2=4*3,所以12也不是素数。另一方面,13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”(或“互素数”)? 小学数学教材对互质数是这样定义的:“公约数只有1的两个数,叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种(不限于此): (1)两个质数一定是互质数。例如,2与7、13与19。 (2)一个质数如果不能整除另一个合数,这两个数为互质数。例如,3与10、5与26。(3)1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。(4)相邻的两个自然数是互质数。如15与16。 (5)相邻的两个奇数是互质数。如49与51。 (6)大数是质数的两个数是互质数。如97与88。 (7)小数是质数,大数不是小数的倍数的两个数是互质数。如7和16。 (8)两个数都是合数(二数差又较大),小数所有的质因数,都不是大数的约数,这两个数是互质数。如357与715,357=3×7×17,而3、7和17都不是715的约数,这两个数为互质数。等等。 三、什么是模指数运算? 指数运算谁都懂,不必说了,先说说模运算。模运算是整数运算,有一个整数m,以n 为模做模运算,即m mod n。怎样做呢?让m去被n整除,只取所得的余数作为结果,就
对称密钥与非对称密钥的区别 一、对称加密(Symmetric Cryptography) 对称密钥加密,又称私钥加密,即信息的发送方和接收方用同一个密钥去加密和解密 数据。它的最大优势是加/解密速度快,适合于对大数据量进行加密,对称加密的一大缺点是密钥的管理与分配,换句话说,如何把密钥发送到需要解密你的消息的人的手里是一个 问题。在发送密钥的过程中,密钥有很大的风险会被黑客们拦截。现实中通常的做法是将对称加密的密钥进行非对称加密,然后传送给需要它的人。 对称加密通常使用的是相对较小的密钥,一般小于256 bit。因为密钥越大,加密越强,但加密与解密的过程越慢。如果你只用1 bit来做这个密钥,那黑客们可以先试着用0来解密,不行的话就再用1解;但如果你的密钥有1 MB大,黑客们可能永远也无法破解,但加密和解密的过程要花费很长的时间。密钥的大小既要照顾到安全性,也要照顾到效率,是一个trade-off。 二、非对称加密(Asymmetric Cryptography) 非对称密钥加密系统,又称公钥密钥加密。非对称加密为数据的加密与解密提供了一 个非常安全的方法,它使用了一对密钥,公钥(public key)和私钥(private key)。私钥只能由一方安全保管,不能外泄,而公钥则可以发给任何请求它的人。非对称加密使用 这对密钥中的一个进行加密,而解密则需要另一个密钥。比如,你向银行请求公钥,银行将公钥发给你,你使用公钥对消息加密,那么只有私钥的持有人--银行才能对你的消息解密。与对称加密不同的是,银行不需要将私钥通过网络发送出去,因此安全性大大提高。
目前最常用的非对称加密算法是RSA算法。公钥机制灵活,但加密和解密速度却比对称密钥加密慢得多。 虽然非对称加密很安全,但是和对称加密比起来,它非常的慢,所以我们还是要用对称加密来传送消息,但对称加密所使用的密钥我们可以通过非对称加密的方式发送出去。为了解释这个过程,请看下面的例子: (1) Alice需要在银行的网站做一笔交易,她的浏览器首先生成了一个随机数作为对称密钥。 (2) Alice的浏览器向银行的网站请求公钥。 (3)银行将公钥发送给Alice。 (4) Alice的浏览器使用银行的公钥将自己的对称密钥加密。 (5) Alice的浏览器将加密后的对称密钥发送给银行。 (6)银行使用私钥解密得到Alice浏览器的对称密钥。 (7) Alice与银行可以使用对称密钥来对沟通的内容进行加密与解密了。 三、总结 (1)对称密钥加密与解密使用的是同样的密钥,所以速度快,但由于需要将密钥在