RSA公钥加密算法安全性讨论
RSA公钥加密算法安全性讨论
(RSA algorithm for public-key encryption and the security)
摘要(Abstract)：RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，公钥和私钥都是两个大素数（大于100个十进制位）的函数。但在分布式计算技术和量子计算机理论快速发展的今天，RSA加密安全性受到了挑战。RSA algorithm is the first one can be used for both encryption and digital signature algorithms, but also easy to understand and operate. RSA is the most widely studied public key algorithm, first put forward nearly two decades now, has undergone the test of various attacks, gradually accepted, widely considered the most outstanding public key options. RSA's security depends on a large integer factorization problem, public key and private key are two large prime numbers (greater than 100 decimal digits) of the function. However, in distributed the rapid development of computing technology and the theory of quantum computers today, RSA encryption security has been challenged.
关键字(keywords):RSA，公钥(public key) ，加密(encryption)，安全性(security) 1.学习心得：
21世纪是信息时代，信息在社会中的地位和作用越来越重要，已成为社会发展的重要战略资源，信息技术改变着人们的生活和工作方式，信息产业已成为新的经济增长点，社会的信息化已成为当今世界发展的潮流和核心，而信息安全在信息社会中将扮演极为重要的角色，它直接关系到国家安全、企业经营和人们的日常生活。密码技术中的加密方法包括对称密码体制和非对称密码体制。而RSA公钥体制便为非对称密钥体制，也叫做公开密钥体系。
安全的问题是永恒的，现在信息安全领域对密码算法的需求远远大于研究。因为信息交换的数量是很大的，但是我们没有足够的安全手段去保证所有通信的安全，没有一劳永逸的工具供我们使用；同时如果我们想要做一个好的信息安全的产品，必须有密码学与信息安全专家参与，假如有些密码算法的隐患你不知道，那就很难保证你使用的是安全的情形，可能正好是不安全的情形；突破性的发展必须依赖于突破性的理论工作，IT行业不景气，很大程度上不景气的原因，决定于密码学研究的相对滞后，很多需要的密码理论成果没有，比如说现在移动通信网络的安全问题，它需要算法数据量小，还要安全性好，需要加密认证，因为手机和一台电脑是不可比的，不论是存储数量和速度，所以需要研究适合于各种场合使用的密码算法，这就需要大家共同去努力。总之，通信的安全是今后时刻要考虑的问题，是我们大家都要重视的问题，而学习《通信网的安全与保密》这门课程是一次让我们了解这些问题的很好的机会。
2.RSA算法简介：
RSA加密演算法是一种非对称加密演算法，在公钥加密标准和电子商业中RSA被广泛使用。 RSA加密算法是Ron Rivest、Adi Shamirh和Len Adleman于1977年在美国麻省理工学院开发出来的，次年首次对外公开宣布，是第一个既能用于数据加密也能用于数字签名的算法。RSA就是他们三人姓氏开头字母拼在一起组成的，他们在题为《获得数字签名和公开钥密码系统的方法》的论文中提出了基于数论的非对称(公钥)密码体制，称为RSA密码体制，RSA是建立在“大整数的素因子分解是困难问题”基础上的，其安全性取决于大数分解，也就是大数分解质因数的困难性。换言之，对一极大整数做因式分解愈困难，RSA演算法愈可靠。假如有人找到一种快速因式分解的演算法的话，那么用RSA加密的信息的可靠性肯定会急剧下降，但找到这样的演算法的可能性是非常小的，今天只有短的RSA密钥才可能以暴力方式解破。
2.1 RSA公钥体制算法
（1）选两个保密的大素数p和q。
（2）计算n=p×q。
（3）计算f(n)=(p-1)(q-1)，同时对p, q严加保密，不让任何人知道。
（4）找一个与f(n)互质的数e，且1 （5）计算d，使得d·e≡1 mod f(n)。这个公式也可以表达为d ≡e-1 mod f(n) （6）以{e，n}为公钥，{d，n}为私钥。 （7）加密时，先将明文变换成0至n-1的一个整数M。若明文较长，可先分割成适当的组，然后再进行交换。设密文为c，则加密过程为：c≡m e (mod n) （8）解密过程为 m≡c d(mod n) 由算法可知：如果第三者进行窃听，他会得到m，n(p×q)，b这几个数，如果想要解码，必须想办法得到e，所以，他必须先对 n作质因数分解，要防止他分解，最有效的方法是找两个非常的大质数 p和q，使第三者分解时发生困难。 2.2 RSA共模攻击 在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加密密钥不同，但这样是非常危险的。最直接的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那么该信息无需私钥就可得到恢复。 设两个用户的公开钥分别为e1 和e2 ，且e1 和e2互素（一般情况都成立），明文消息是m，密文分别是 C1≡m e1(mod n) C2≡m e2(mod n) 当敌人截获c1和c2后，可如下恢复m。用推广的Euclid算法求出满足 re1 + se2 = 1 的两个整数r和s，其中一个为负，设为r。再次用推广的Euclid算法求出c1-1，由此得(c1-1)-r c2s≡m（mod n）。除此之外，还有其它一些利用公共模数攻击的方法。解决办法只有一个，那就是不要共享模数n。 2.3 RSA的优缺点 RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048bits长的密钥，其他实体使用1024比特的密钥。C)RSA 密钥长度随着保密级别提高，增加很快。 3.RSA公钥密码体制的安全性分析： 实际上，RSA的安全性是基于分解大整数的困难性假定，之所以为假定是因为至今还未有人在数学上证明从c和e计算m需要对n进行因式分解，也许有尚未发现的多项式时间分解算法。 3.1大数因子分解的难度 著名数学家费马(1601-1665)和勒让德(1752-1833)都研究过分解因子的算法，现代某些更好的算法是勒让德方法的扩展。其中R. Schroeppel算法是一类较好的算法，用此法分解 因子仍然需要大约e次运算, 其中ln表示自然对数，可见分解n所需的运算次数与密钥的长度有关,随着密钥长度的增加，分解所需的时间会成指数倍增加。 若用1台1s能进行1亿次因子分解的高速计算机来计算，分解十进制长度为200位的n，其所需时间为3 800 000年。由此可见，对于RSA系统，如果用一个长度为200位(十进制)的n，认为它是比较安全的。n的长度越长，因子分解越困难，密码就越难以破译,加密强度就越高。一般来说，每增加10位二进制数，分解的时间就要加长1倍。 不过随着计算机运算速度的提高和并行计算的发展，破解的速度也会同步提高，这时可能要求使用更长的密钥。1993年，一个国际研究小组决定对RSA-129发出挑战。他们之所以敢于这样做，主要因为近20年来，计算机运算速度有了突飞猛进的提高，在大数分解理论上也有新的突破。该小组在国际互联网上集合来自世界各地的志愿参加者，向他们分发因数分解软件。每个参加者都领取了不同的因数分解任务，在自己的计算机上独立运算，然后把计算结果寄回MIT总部，列表归纳。到1994年4月，共有600余名志愿者参加了这项破译活动。他们总共动用了1600多台工作站、大型机和超级计算机，花费了8个月的时间，终于分解了RSA-129的公开钥匙。不过破解的难度随着n长度而不断增加，因此可以根据被加密文件的重要程度及对加密时间的要求这2个因素来选择n的长度，这种选择密钥长度的灵活性(密钥长度决定保密的等级)是许多密码系统所没有的，是RSA算法的一个特点。 3.2计算能力与算法的进步 到目前为止，世界上还没有任何可靠的攻击RSA演算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在量子计算机理论日趋成熟的今天，RSA 加密安全性受到了挑战。 量子分解算法是1995年美国科学家Peter Shor提出的，是迄今量子计算领域最著名的算法。它利用量子计算的并行性，可以快速分解出大数的质因子，将使量子计算机很容易破解目前广泛使用的密码如RSA公钥加密系统，严重威胁到银行、网络和电子商务等的信息安全以及国家安全。因此Shor算法的提出迅速引起了世界各国对量子计算研究的高度关注。 Shor算法在量子计算机上的实验实现一直是国际公认的难题。2008年伊始，中国科学院公布，中国科技大学教授潘建伟和他的同事杨涛、陆朝阳等，与英国牛津大学的研究人员合作，在国际上首次利用光量子计算机实现了Shor量子分解算法，研究成果发表在当年1月出版的美国权威物理学期刊《物理评论快报》上，标志着我国光学量子计算研究达到了国际领先水平。 对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。分解算法过去都采用二次筛法，如对RSA-129的分解。而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA-130时所做的计算仅比分解RSA-129多10%。将来也可能还有更好的分解算法，因此在使用RSA算法时对其密钥的选取要特别注意其大小。就目前的计算机水平用1024位二进制(约340位十进制)的密钥是安全的, 2048位是绝对安全的。随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解，最近，768比特的RSA挑战数宣告被分解，其算法的复杂度相当于分解512比特的RSA挑战数的上千倍。同时密码学家建议1024比特的RSA在三到四年内停止使用,为保证安全可以使用比特数为1536比特，甚至2048比特的RSA模。 参考文献： 【1】现代密码学.杨波编著.——北京：清华大学出版社,2003 【2】RSA算法——https://www.wendangku.net/doc/e211181151.html,/view/7520.htm#sub10613 【3】RSA加密算法的安全性分析.向进——吉首大学学报，2011.1 【4】量子分解算法——https://www.wendangku.net/doc/e211181151.html,/view/1347838.htm#sub1347838 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 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公钥加密算法及其安全性讨论 RSA algorithm for public-key encryption and its security 摘要：RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。但是，RSA的安全性依赖于大数的因子分解，却并没有从理论上证明破译RSA的难度与大数分解难度等价，即RSA的重大缺陷是无法从理论上把握它的保密性能到底如何。随着计算能力的不断进步和各种攻击方法的出现，RSA算法是否真的安全。 关键词：RSA，公钥，加密，大数分解，攻击，安全性 1 RSA加密算法 1.1公钥简介 密码体制按密钥类型分为对称密钥和不对称密钥。对称密钥即加密、解密用的是同一个密钥，又称为私钥。不对称密钥即公钥加密，加密、解密用的是不同的密钥，一个密钥“公开”，即公钥，另一个自己秘密持有，即私钥，加密方用公钥加密，只有用私钥才能解密——史称公钥加密体系：PKI。 1.2 RSA算法简介 RSA加密算法是一种非对称加密算法。RSA加密算法是Ron Rivest、Adi Shamirh和Len Adleman于1977年在美国麻省理工学院开发出来的，次年首次对外公开宣布，是第一个既能用于数据加密也能用于数字签名的算法。RSA就是他们三人姓氏开头字母拼在一起组成的。RSA是建立在“大整数的素因子分解是困难问题”基础上的，其安全性取决于大数分解，也就是大数分解质因数的困难性。换言之，对一极大整数做因式分解愈困难，RSA演算法愈可靠。假如有人找到一种快速因式分解的演算法的话，那么用RSA加密的信息的可靠性肯定会急剧下降，但找到这样的演算法的可能性是非常小的，今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。 1.3 RSA算法 1.3.1公钥和私钥的产生 假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥： （1）选两个保密的足够大的素数p和q。同时对p, q严加保密，不让任何人知道。 （2）计算N=p×q。 （3）计算f(n)=(p-1)(q-1)。 （4）找一个与f(n)互质的数e，且1 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公钥密码 实验目的： 熟练掌握RSA公钥密码算法原理及实现。 实验内容： 1、写出RSA公钥密码算法及其实现。 2、当取两素数分别为17、23，加密密钥为35时，写出其明文空间，并求出下列明文的密 文：1、15、17、23、48、235。 3、当取两素数分别为17、23，加密密钥为35时，求相应的解密密钥。 实验结果： 1.算法： Step1：选取两个大素数p和q，p和q保密 Step2：计算n=pq，f（n）=（p-1）（q-1），n公开，f（n）保密 Step3：随机选取正整数1 n=p*q; t=(p-1)*(q-1); cout<<"请输入加密密钥e:"; cin>>e; cout<<"输入明文M:"; cin>>M; C=1; for(i=0;i 一、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码形式 实验四 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 常见公钥加密算法有哪些 什么是公钥加密公钥加密，也叫非对称（密钥）加密（public key encrypTIon），属于通信科技下的网络安全二级学科，指的是由对应的一对唯一性密钥（即公开密钥和私有密钥）组成的加密方法。它解决了密钥的发布和管理问题，是目前商业密码的核心。在公钥加密体制中，没有公开的是私钥，公开的是公钥。 常见算法RSA、ElGamal、背包算法、Rabin（Rabin的加密法可以说是RSA方法的特例）、Diffie-Hellman （D-H）密钥交换协议中的公钥加密算法、EllipTIc Curve Cryptography （ECC，椭圆曲线加密算法）。使用最广泛的是RSA算法（由发明者Rivest、Shmir和Adleman 姓氏首字母缩写而来）是著名的公开金钥加密算法，ElGamal是另一种常用的非对称加密算法。 非对称是指一对加密密钥与解密密钥，这两个密钥是数学相关，用某用户密钥加密后所得的信息，只能用该用户的解密密钥才能解密。如果知道了其中一个，并不能计算出另外一个。因此如果公开了一对密钥中的一个，并不会危害到另外一个的秘密性质。称公开的密钥为公钥；不公开的密钥为私钥。 如果加密密钥是公开的，这用于客户给私钥所有者上传加密的数据，这被称作为公开密钥加密（狭义）。例如，网络银行的客户发给银行网站的账户操作的加密数据。 如果解密密钥是公开的，用私钥加密的信息，可以用公钥对其解密，用于客户验证持有私钥一方发布的数据或文件是完整准确的，接收者由此可知这条信息确实来自于拥有私钥的某人，这被称作数字签名，公钥的形式就是数字证书。例如，从网上下载的安装程序，一般都带有程序制作者的数字签名，可以证明该程序的确是该作者（公司）发布的而不是第三方伪造的且未被篡改过（身份认证/验证）。 对称密钥密码体制 所谓对称密钥密码体制，即加密密钥与解密密钥是相同的密码体制。 数据加密标准DES属于对称密钥密码体制。它是由IBM公司研制出，于1977年被美国 密码学课程报告《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整除，只取所得的余数作为结果，就 #include 数学文化课程报告题目：RSA公钥加密算法及实现 RSA公钥加密算法及实现 摘要 公钥密码是密码学界的一项重要发明，现代计算机与互联网中所使用的密码技术都得益于公钥密码。公钥密码是基于数学的上的困难问题来保证其性。其中RSA加密算法是一项重要的密码算法，RSA利用大整数的质数分解的困难性，从而保证了其相对安全性。但如果发现了一种快速进行质数分解的算法，则RSA算法便会失效。本文利用C 语言编程技术进行了RSA算法的演示[1]。 关键词：C语言编程、RSA算法、应用数学。 RSA public key encryption algorithm Abstract Public key cryptography is an important invention in cryptography, thanks to public key cryptography, and it is used in modern computer and Internet password technology. Public key cryptography is based on the mathematics difficult problem to ensure its confidentiality. The RSA public key encryption algorithm is an important cryptographic algorithm, RSA using the difficulty that large integer is hard to be factorized into prime Numbers to ensure it safety. But if you can find a kind of fast algorithm to do the factorization, RSA algorithm will be failure. In this paper we used C language programming technology to demonstrate the RSA algorithm. Keywords：C language programming、RSA algorithm、Applied mathematics 实验五公钥加密算法—RSA 一、实验目的 通过使用RSA算法对实验数据进行加密和解密，掌握公钥加密算法的基本原理，熟练掌握RSA算法各功能模块的工作原理和具体运算过程。 二、实验原理 RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。 1. RSA的密钥生成 RSA的算法涉及三个参数，n、e、d。 其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。鉴于现代对于大整数分解的水平不断增强，一般P、Q的取值都要求在1024位以上。 e和d是一对相关的值，e可以任意取，但要求e与(p-1)*(q-1)互质；再选择d，要求： (e*d)mod((p-1)*(q-1))=1。 RSA加密算法 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的约数，这两个数为互质数。等等。 苏州科技学院 实验报告 实验四 学生姓名：学号：指导教师： 实验地点：计算机学院大楼东309 实验时间：4.21 一、实验室名称：软件实验室 二、实验项目名称：RSA加密解密 三、实验学时：4学时 四、实验原理： 加密过程： 第一步，用户首先输入两个素数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]中，算法如下： 第二步，输出对加密前的明文和加密并解密后的密文进行比较，判断两个数组是否一致，从而得知算法是否正确。 五、实验目的： 1、对算法描述可进行充分理解，精确理解算法的各个步骤。 2、完成RSA软件算法设计。 3、用C++完成算法的设计模块。 六、实验内容： 通过编写的程序完成RSA加密解密功能 七、实验器材（设备、元器件）： （1）个人计算机 （2） Windows 7系统平台 （3） C++开发环境 八、实验数据及结果分析： #include 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的约数，这两个数为互质数。等等。 三、什么是模指数运算？ 指数运算谁都懂，不必说了，先说说模运算。模运算是整数运算，有一个整数m，以n为模做模运算，即m mod n。怎样做呢？让m去被n整除，只取所得的余数作为结果，就叫做模运算。例如，10 mod 3=1； 26 mod 6=2；28 mod 2 =0等等。RSA加密算法_源代码__C语言实现
RSA加密解密的设计与实现
RSA公钥加密算法及其安全性讨论
RSA加密算法的基本原理
RSA加密算法加密与解密过程解析
密码学实验-RSA公钥密码
RSA加密算法java编程实现
实验四RSA加解密算法的实现
常见公钥加密算法有哪些
密码学-RSA加密解密算法的实现课程设计报告
用实例讲解RSA加密算法(精)
RSA加解密算法C语言的实现
RSA加密算法及实现
公钥加密算法
RSA加密算法
RSA加密解密
用实例给新手讲解RSA加密算法