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.系统功能描述与软件模块划分
功能:
1.进行加密
加密
第一步,随机两个素数p和q,并求出n = p*q,然后再求出n 的欧拉函数值phi。
第二步,在[e,phi]中选出一个与phi互素的整数e,并根据e*d ≡1(mod phi),求出e的乘法逆元。至此我们已经得到了公开密钥{e,n}和秘密密钥{d,n}。
第三步,让用户输入要进行加密的小于n一组正整数(个数不超过MAXLENGTH),输入以-1为结束标志,实际个数存入size 中,正整数以clear[MAXLENGTH]保存。
第四步,对第三步所得的明文clear[MAXLENGTH]进行加密。遍历clear[size],对每一个整数用以下算法进行加密,并将加密后的密文保存在Ciphertext[MAXLENGTH]中。
第五步,输出密文Ciphertext[MAXLENGTH]
2.进行解密
第一步,输入加密后的密文Ciphertext1[MAXLENGTH],输入以-1为结束标志
第二步,输入解密密钥[d,phi],对密文进行解密,结果保存在DecryptionText[MAXLENGTH]中。
第三步,输出解密后明文DecryptionText[MAXLENGTH]
生成随机素数:先生成一个随机数然后判断它是否为素数从而输出
unsigned long foo() //生成随机数
int panduan(unsigned long b) //判断是否为素数
unsigned long tiqu(unsigned long &p,unsigned long &q) //从随机素数中选取两个为p和q
求e时需要用到e与phi的互逆因此在随机产生e的同时需要作互逆判断若互逆则输出随机e 否则重新生成e
int gcd(int x,int y) //判断两数是否为互素
在p、q、e都准备就绪的时候就能够进行加解密的运算因为考虑到溢出因此3个一组进行加解密
void Encryption() //加密算法
void Decryption() //解密算法
5.设计核心代码
unsigned long foo()
{
unsigned long random = 0;
srand((int)time(0));
random = rand() % 300;
return random;
}
srand函数是随机数发生器的初始化函数
需要提供一个种子这里使用time来获取系统当前时间
rand() % 300是随机0-299的整数
//以下为加密算法
void Encryption()
{//加密算法
cout << "随机生成两个较大的素数:"< tiqu(p,q); n = p * q;//求解 n, phi = (p - 1) * ( q - 1 );//求解 n 的欧拉函数值 cout << " n = " << n << ", phi = " << phi << endl; cout << " 请从[0," << phi - 1 << "]中选择一个与 " << phi << " 随机生成互素的数 e:"; while(1) { e=foo(); if(gcd(e,phi)==1&&e>=100&&e<=300&&e!=q&&e!=p) break; } cout< float d0; for( int i = 1; ; i++) {///求解乘法逆元 e * d ≡ 1 (mod phi) d0 = (float)(phi*i+1) / e; if( d0 - (int)d0 == 0 ) break; } d = (int)d0; cout << endl; cout << " e = " << e << ", d = " << d << endl; cout << " 公开密钥 Pk = {e,n} = {" << e << "," << n << "}" << endl; cout << " 秘密密钥 Sk = {d,n} = {" << d << "," << n << "}" <<"记录私钥"<< endl; cout << endl; cout << " 请3位一组输入要加密的正整数(以-1结束):" << endl; cout << " 加密前的明文为:"; for( i = 0; i < MAXLENGTH; i++) Ciphertext[i] = 1; int count; for(int j = 0; j { cin >> clear[j]; if( clear[j] == -1 ) break; count = e; while(count > 0) {//对明文进行加密 Ciphertext =(clear)^ e mod n Ciphertext[j] = (Ciphertext[j] * clear[j]) % n; //加密算法 count-- ; } } cout << " 密文为:" ; size = j;//实际密文长度 for(int k=0; k cout << Ciphertext[k] << " "; cout << endl ; } //以下为解密算法 void Decryption() {//解密算法 int pp,kk; for(int i = 0; i < MAXLENGTH; i++) DecryptionText[i] = 1; int count; cout<<"请输入要解密的密文(以-1结束):"< for(int u = 0; u { cin >> Ciphertext1[u]; if( Ciphertext1[u] == -1 ) break; } cout<<"输入密钥解密(d,n)"< cin>>pp>>kk; for(int j = 0; j < size; j++) { count = pp; while(count > 0) {//对密文进行解密 DecryptionText =(Ciphertext) ^ d (mod n) DecryptionText[j] = ((DecryptionText[j] * Ciphertext1[j]) %kk); count-- ; } } cout << " 解密后的明文为:"; for( int k = 0; k < size; k ++) cout << DecryptionText[k] << " "; cout << endl ; } 6.参考文献 [1]赛迪网.RSA :云安全需急迫解决的安全隐患.旧金山:赛迪网, . [2]赛迪网.RSA主席认为云安全成安全领域趋势.旧金山:赛迪网, . [3]魏晨. 安全风向标:品味RSA 信息安全大会.旧金山:赛迪网, . [4]四夕.新的安全威胁而前需要新的安全架构.旧金山:赛迪网, . [5]王茜.倪建伟,一种基于RSA的加密算法. 重庆大学学报, , 28 (1):68-72. [6]周升力.RSA密码算法的研究与改进实现.现代计算机,:51-53. [7]管占明. 邓亚娟.RSA加密算法的研究及应用. 科技广场,:98- 99. [8]胡向东,魏琴芳等.应用密码学.北京市:电子工业出版社, : 114-119. [9]卢开澄.计算机密码学.北京市:清华大学出版社, : 73-77 [10]史予荣.软件加密技术从入门到精通,北京市:清华大学出版社. : 74-77. 7.设计结果及验证 进行加密 得到公钥(113,11021)和私钥(2105,11021) 加密明文123 587 114 56 18 9 得到密文1453 385 7882 6329 4873 2744 输入密文解密 得到先前加密的明文123 587 114 56 18 9 8.软件使用说明 1.选择RSA加解密系统功能 1为加密 2为解密 0为退出输入其它错误重新输入 2.输入1 进行加密过程 输入需要加密的明文 3个一组空格空开 -1结束 生成密文而且返回主界面2.输入2进行解密 输入加密好的密文 -1结束 输入密钥 d n 解密得到加密前明文解密成功返回主界面 9.设计体会 RSA课程设计中,包含了加解密的过程,刚开始对做设计的时候,觉得对于RSA的加解密只要套用公式就能够很方便地进行,实现并不是非常困难。可是在真正实现的时候还是碰到了不少的问题,在随机产生素数的时候,不同的实现方法会具有不同的复杂度,从而使得时间效率也有所不同,若直接生成素数,系统需要很长一段时间来生成,而随机生成一个数后再判断是否为素数能够减少很多时间,效率也就提高了。 在加解密的时候,起初使用的是int型的整形变量,可是发现int型只有4位长度8字节,因此在计算时,数字一大就会产生溢出,因此使用了数组进行了加解密。而在大素数生成时,能够生成非常大的素数,可是在加密时,因为程序效率过于低以至于一天都没有算出结果,因此在实现时使用了可进行运算和实现较大的素数而并不是大素数。随机大素数进行RSA加解密的程序还需要时间进行进一步改进。需要进一步调用大整数的加减乘除算法,素数明文密文密钥公钥都要使用数组才能加以实现,在此暂时保留这个程序,将用更充分的时间来实现。 总结这次课程设计,不可否定又是一次对于自己编程能力的提升以及团队合作的加深,自己动手编程真的是一种成就感,然而在这以外,我还发现了自己会有一些突发奇想的思路,会发现和挖掘实现实验时某些过程的优化,而这些思路又能够帮助自己来 完成程序。这次课程设计的不足是还没有完全完成课程设计所需要的任务要求,写的程序还是略微有点简单化了,可能自己能力还是有限,在静候的时间里还需要更加的磨练才行。 附录 #include #include #include #include using namespace std; #define MAXLENGTH 500 //明文最大长度,即所允许最大整数个数 int size = 0;//保存要进行加密的正整数的个数 unsigned long p, q; //两个大素数 int n, phi; //n = p * q,phi = (p-1) * (q-1) 是n的欧拉函数值 int e; //{e, n}为公开密钥 int d; //{d, n}为秘密密钥 long clear[MAXLENGTH], Ciphertext[MAXLENGTH],Ciphertext1[MAXLENGTH];//分别用于存放加//密前的明//文和加密后的密文 long DecryptionText[MAXLENGTH];//存放解密后的明文 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加密算法加密与解密过程解析 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、对算法描述可进行充分理解,精确理解算法的各个步骤。 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加密算法的基本原理 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加密解密的设计与实现
RSA加密算法加密与解密过程解析
实验四RSA加解密算法的实现
RSA加密算法的基本原理
RSA加解密算法C语言的实现