RSA算法的C实现专业课程设计方案报告.doc
《RSA算法的C实现专业课程设计方案报告.doc》由会员分享,可在线阅读,更多相关《RSA算法的C实现专业课程设计方案报告.doc(25页珍藏版)》请在咨信网上搜索。
1、 课程设计汇报-RSA算法实现院 (系): 专 业:班 级: 学 生:学 号: 指导老师:10月10日 目 录1. RSA算法介绍和应用现.32. 算法原理.33. RSA算法数论基础.43.1.单向和陷门单向函数.43.2.同余及模运算.43.3.欧拉函数、欧拉定理和费尔马定理.53.4.乘法逆元及其求法.5.4. RSA算法各步骤.64.1.RSA公钥加密解密概述.64.2. RSA署名算法64.3.大数运算处理.74.4.大素数产生.85. RSA安全性.86. 代码实现:.107. RSA算法结果分析.157.1.主界面初始化157.2.设置密钥.157.3.对明文加密167.4.对密
2、文解密178. 总结和展望.179. 参考文件181.RSA算法介绍和应用现实状况RSA公开密钥加密算法自20世纪70年代提出以来,已经得到了广泛认可和应用。发展至今,电子安全领域各方面已经形成了较为完备国际规范。RSA作为最关键公开密钥算法,在各领域应用数不胜数。RSA在硬件方面,以技术成熟IC应用于多种消费类电子产品。RSA在软件方面应用,关键集中在Internet上。加密连接、数字署名和数字证书关键算法广泛使用RSA。日常应用中,有比较著名工具包Open SSL(SSL,Security Socket Layer,是一个安全传输协议,在Internet上进行数据保护和身份确定。Open
3、SSL是一个开放源代码实现了SSL及相关加密技术软件包,由加拿大Eric Yang等提议编写。Open SSL应用RSA实现署名和密钥交换,已经在多种操作系统得到很广泛应用。另外,家喻户晓IE浏览器,自然也实现了SSL协议,集成了使用RSA技术加密功效,结合MD5和SHA1,关键用于数字证书和数字署名,对于习惯于使用网上购物和网上银行用户来说,几乎天天全部在使用RSA技术。RSA更出现在要求高度安全稳定企业级商务应用中。在当今企业级商务应用中,不得不提及使用最广泛平台j2ee。实际上,在j2se标准库中,就为安全和加密服务提供了两组API:JCA和JCE。 JCA (Java Cryptogr
4、aphy Architecture)提供基础加密框架,如证书、数字署名、报文摘要和密钥对产生器; JCA由多个实现了基础加密技术功效类和接口组成,其中最关键是java.security包,此软件包包含是一组关键类和接口,Java中数字署名方法就集中在此软件包中。JCE(Java Cryptography Extension) 在JCA基础上作了扩展,JCE也是由多个软件包组成,其中最关键是javax.crypto包,此软件包提供了JCE加密技术操作API。javax.crypto中Cipher类用于具体加密和解密。在上述软件包实现中,集成了应用RSA算法多种数据加密规范(RSA算法应用规范介绍
5、参见: ,这些API内部支持算法不仅仅只有RSA,不过RSA是数字署名和证书中最常见),用户程序能够直接使用java标准库中提供API进行数字署名和证书多种操作。单机应用程序使用RSA加密尚比较少见,比如使用RSA加密任意一个文件。RSA算法能够简单叙述以下:取素数p,q,令n=pq.取和(p-1)(q-1)互素整数e,由方程de=1 (mod (p-1)(q-1)解出d,二元组(e,n)作为公开密钥,二元组(d,n)作为私有密钥b=ae mod n,c=bd mod n.2.算法原理1选择两个不一样大素数p、q (现在两个数长度全部靠近512bit是安全);2. 计算n = p*q。 3.
6、计算n欧拉函数 t=(p-1)(q-1)。4. 选择整数e作为公钥,使e和t互素,且1e t。5. 用欧几里得算法计算d作为私钥,使d*e=1 mod t。6. 加密:C=Me mod n7. 解密:MCd mod n=(Me)d mod n= Med mod n。3.RSA算法数论基础RSA算法数学理论基础在密码学中需要使用到很多数学理论,比如数论、信息论、复杂度理论等, 它们是设计密码系统及协议不可或缺工具,其中数论是密码学中(尤其是公开密钥密码系统中)最关键数学基础,所以有必需对相关数论理论做一介绍。下面介绍RSA算法数学基础知识。3.1单向和陷门单向函数RSA安全性关键取决于结构其加密
7、算法数学函数求逆困难性,这同大多数公钥密码系统一样(譬如EIGamal算法就是基于离散对数问题困难性),我们称这么函数为单向函数。单向函数不能直接用作密码体制,因为假如用单向函数对明文进行加密,即使是正当接收者也不能还原出明文,因为单向函数逆运算是困难。和密码体制关系更为亲密陷门单向函数,即函数及其逆函数计算全部存在有效算法,而且能够将计算函数方法公开。单向和陷门单向函数概念是公钥密码学关键,它对公钥密码系统结构很关键,甚至能够说公钥密码体制设计就是陷门单向函数设计。定义2. 1:令函数f是集合A到集合B映射,以f:AB表示。若对任意x1x2,x1,x2A,有f(x1)f(x2),则称f为1一
8、l映射,或可逆函数。定义2. 2:一个可逆函数厂,若它满足: 1对全部XA,易于计算f(x); 2对“几乎全部xA,由f(x)求x“极为困难”,以至于实际上不可能做到。则称f为单向函数 (One-way function) 上述定义中“极为困难”是对现有计算机能力和算法而言,Massey称此为视在困难性,对应函数称之为视在单向函数。以此来和本质上困难性相区分。现在,还没有些人能够从理论上证实单向函数是存在。3.2同余及模运算同余:假定有三个整数a,b,n(n0),当我们称a在模n时和b同余,是指当且仅当a和b差为n整数倍,即a-b=kn,其中k为任一整数。若a和b在模n中同余, 我们可写为a
9、b(mod n)或n l(a-b)。剩下类(Residue Class):很显著地,利用同余概念,全部整数在模n中被分成n个不一样剩下类;为n所整除数(即余数为0)为一剩下类,被n所除余数为1数为另一剩下类,余2数又为一剩下类,以这类推。完全剩下系(Complete Set of Residues):若将每一剩下类中取一数为代表,形成一个集合,则此集合称为模n完全剩下系,以Zn表示。很显著地,集合(0,l, 2,n-1为模n一完全剩下系。从0到n-1整数组成集合组成了模n“完全剩下系”。这意味着,对每一个整数a,它模n剩下是从0到n-1之间某个整数。所谓运算a mod n表示求a被n除余数,成
10、为模运算。既约剩下系(Reduced Set of Residues):在模n完全剩下系中,若将全部和n 互素剩下类形成一个集合,则称此集合为模n既约剩下系,以Zn表示。比如n=10时,0,1,2,3,4,5,6,7,8,9)为模10完全剩下系;而1,3,7,9)为模10既约剩下系。3.3欧拉函数、欧拉定理和费尔马定理欧拉函数(n):是一个定义在正整数上函数,其值等于序列0,1,2,3, n-1 中和n互素数个数。即fn为模n既约剩下系中全部元素个数。由定义知,当P是素数时, (p)=P-1。定理21欧拉定理:若m,a为正整数,有g c d(a,m)=l(g c d,Greatest Comm
11、on Divisor,最大条约数),则a(m) (mod m)。其中m称为欧拉函数,它是比m小但和m互素正整数个数。欧拉定理也有一个等价形式:a(m)+1 =a(mod m)。 定理22设P和q是两个不一样素数,n=pq,则(n)=(p-1)(q-1),对任意xZn及任意非负整数k,有x k(n)+1x (mod n)。定理3费尔马定理:假如P是素数,且g c d(m ,p)=l(可表示为(m , p)=1), 则mp-1l(mod p),费尔马定理还存在另一个等价形式:假如P是素数,m是任意正整数,则mpm(mod p)。对于素数P来说, (p)=p-1,所以费尔马定理实际是欧拉定理一个推论
12、。费尔马定理和欧拉定理及其推论在组成了RSA算法关键理论基础。3.4乘法逆元及其求法乘法逆元定义:若a bl(mod n),则称b为a在模n乘法逆元,b可表示为a-1。利用Euclid(欧几里德)算法(辗转相除法)求乘法逆元:己知a及n且(a ,n) =1,求a a l=1(mod n)。欧几里德算法是古希腊数学家欧几里德给出求两个自然数最大条约数方法,假如(a,n)=1,则b一定存在。首先介绍利用欧几里德算法求g c d(a,n)方法,再介绍求乘法逆元方法。令r0=n,r l=a,an,利用辗转相除法可得r0=r1+g1+r2 0r2 r l r1=r2g2+r3 0r3r 2 : :rj-
13、2=r j-l g j-1+rj 0r jr j-1 rm-3=rm-2 gm-2+rm-1 0rm-1rm-2 rm-2=rm-1 gm-1+rm 0r mrm-1 rm-1= r m gm 则r m为a及n最大公因子。(欧几里德算法求g c d关键概念在于:若c=d g + r, 则(c,d)=(d,r)。所以在上述算法中,(a,n)=(r0,r1) =(r l,r2)= (r(m-1),r m)=(r m,o)=r m。能够经过举例说明利用欧几里德算法求逆元方法,如:求1001b=lmod 3837, b是1001相关模3837乘法逆元。因为(1001,3837)=l,而3837=310
14、01+834 1001=1834+1 67 834=4167+166 167=1 166+1所以l=167166=167-(834-4167)=5167834 =5(1001834)一834 =51001-6834 =51001-6(383731001) =23 1001-63837 所以231001l(mod 3837),故1001相关模3837乘法逆元为23。通常求乘法逆元以欧几里德算法为佳。4.RSA算法各步骤RSA算法是1978年由R.L.Rivest,A.Shamir和L.Adleman提出一个用数论结构、也是迄今为止理论上最为成熟完善公钥密码体制。RSA理论基础是数论中欧拉定理,它
15、安全性依靠于大数因子分解,但并没有从理论上证实破译RSA难度和大数分解难度等价。4.1 RSA公钥加密解密概述RSA算法采取下述加密/解密变换。1密钥产生选择两个保密大素数P和q。计算N=p q,(N) =(p-1)(g-1),其中(N)是N欧拉函数值。选择一个整数e,满足le(N),且g c d(N),e)1。计算私钥d(解密密钥),满足e dl(mod(N),d是e在模(N)下乘法逆元。 以(e, n)为公钥,(d ,N)为密钥,销毁p,q,(N)。2加密加密时首先将明文比特串进行分组,使得每个分组对应得串在数值上小于N, 即分组二进制长度小于l092N。然后,对每个明文分组M,作加密运算
16、: C=E k(M)=M e mod N 3解密对密文分组解密运算为:M=D k (C) =C d mod N 由定理1和定理2能够证实解密运算能恢复明文M 4.2 RSA署名算法并非全部公开密钥系统,均可同时达成秘密性和数字署名功效。通常而言, 一公开密钥系统若作为密码系统,则无法作为数字署名,反之亦然。只有极少数系统可同时作为密码系统和数字署名,如本文讨论RSA系统。RSA署名算法以下: 设N=p q,且p和q是两个大素数,e和d满足e dl(mod (N)。公开密钥:N,e 私有密钥:d 署名过程:发送方使用自己私钥d对明文m进行数字署名变换: y=x d mod N:并将加密后消息和署
17、名y发送给接收方; 验证过程:接收方使用发送方公钥e对收到消息y进行数字署名验证变换x=ye mod N,并使用发送方密钥解密恢复消息x,比较x和x,假如x=x则证实发送方身份正当。这么,用户A若想用RSA署名方案对消息x署名,她只需公开她公钥N和e,因为署名算法是保密,所以A是唯一能产生署名人,任何要验证用户A 署名用户只需查到A公钥即可验证署名。对于实现署名和公钥加密组合,常见方法是:假定通信双方为A和B。对于明文x,A计算她署名y=x d mod N,然后利用B公开加密函数EB对信息对(x, y)加密得到Z,将密文Z传送给B,当B收到密文Z后,她首先用她解密函数DB来解密得到(x,y)=
18、DB (Z)= DB (EB(x,y),然后利用A验证算法来检验x=x=y e mod N是否成立。4.3 大数运算处理 RSA依靠大数运算,现在主流RSA算法全部建立在1024位大数运算之上。而大多数编译器只能支持到64位整数运算,即我们在运算中所使用整数必需小于等于64位,即:0xffffffffffffffff也就是,这远远达不到RSA需要,于是需要专门建立大数运算库来处理这一问题。最简单措施是将大数看成数组进行处理,数组各元素也就是大数每一位上数字,通常采取最轻易了解十进制数字09。然后对“数字数组”编写加减乘除函数。不过这么做效率很低,因为二进制为1024位大数在十进制下也有三百多位
19、,对于任何一个运算,全部需要在两个有数百个元素数组空间上数次重循环,还需要很多额外空间存放计算进退位标志及中间结果。另外,对于一些特殊运算而言, 采取二进制会使计算过程大大简化,而这种大数表示方法转化成二进制显然很麻烦,所以在一些实例中则干脆采取了二进制数组方法来统计大数,当然这么效率就更低了。一个有效改善方法是将大数表示为一个n进制数组,对于现在32位系统而言n能够取值为232次方,即0x,假如将一个二进制为1024位大数转化成0x10000000进制,就变成了32位,而每一位取值范围不再是二进制0 1或十进制09,而是00xffffffff我们恰好能够用一个32位DWORD(如:无符号长整
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- RSA 算法 实现 专业课程 设计方案 报告
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。