毕业论文-RSA密码体制的设计及MATLAB语言下的实现15105.doc
《毕业论文-RSA密码体制的设计及MATLAB语言下的实现15105.doc》由会员分享,可在线阅读,更多相关《毕业论文-RSA密码体制的设计及MATLAB语言下的实现15105.doc(25页珍藏版)》请在三一文库上搜索。
1、 四川理工学院毕业论文四川理工学院毕业论文 RSARSA 密码体制的设计及密码体制的设计及 MATLABMATLAB 语言下的实现语言下的实现 学 生:XXX 学 号:06121020230 专 业:数学与应用数学 班 级:2006.2 指导教师:张金山 四川理工学院理学院 二 O 一 O 年六月 摘摘 要要 RSA 算法是一个能同时用于加密和数字签名的算法,易于理解和操作,有较高的 安全性,因此有着广泛的运用。本文首先论述了 RSA 的基本运用途径,RSA 的数学原 理,其加密解密的具体算法,并给出了其在 MATLAB 应用软件上的实现,然后,对 RSA 的安全性进行了一定的分析,包括其可能
2、存在的攻击和对参数的选择,以便对其 有更深的了解。 关键词:RSA 公钥密码体制 加密 解密 MATLAB 安全性 ABSTRACT RSA is an algorithm which can be used for both encryption and digital signature. It is easy to understand as well as to operate, and has an upper security which makes it popular. This paper firstly delivers information on the basic p
3、urpose, the mathematic principle and the specific arithmetic of RSA. Then it presents an implementation of RSA on the application software MATLAB. After that, this article also analyzes the security of RSA, including its potential leaks, parameter options, which helps us to know further of RSA. Keyw
4、ords : RSA public key cryptography encryption decrypt MATLAB security 目 录 前 言1 第 1 章 RSA 简介 .2 1.1 密码体制简介 .2 1.2 RSA 的简介 .2 第 2 章 相关数论知识4 2.1 整除与互素4 2.2 费马定理和欧拉定理 .4 2.3 中国剩余定理 .5 第 3 章 RSA 的数学原理及其算法实现 .7 3.1 RSA 的数学原理.7 3.2 RSA 的算法设计.8 3.3 RSA 的 MATLAB 实现10 第 4 章 RSA 的安全性分析 .14 4.1 对 RSA 常见的攻击方法14
5、4.2 RSA 的参数选择.15 结束语16 参考文献17 致 谢18 四川理工学院毕业论文 1 前前 言言 随着计算机通信技术的迅速发展,在计算机网络和通信的众多领域中,信息的安 全性越来越受到人们的重视,于是,密码技术应运而生,目前计算机网络主要采用两 种密码体制,即公钥密码体制和私钥密码体制,作为公钥密码体制的重要技术的 RSA,主要用于数字加密和数字签名,由于其很好的安全性,可以保证网络中重要数 据的安全性,因此有广泛的应用。 RSA 于 1978 年由美国麻省理工大学的三位数学家提出,经过三十多年的发展,人 们对它的研究也逐渐广泛,它是第一个能用于数据加密和数字签名的算法,其安全性
6、依赖于大数的因子分解,因此,具有较高的安全性,有时也用于密钥的管理。 本文较为详细的介绍了密码体制的相关内容,包括 RSA 的主要应用及其在计算机 网络中的重要性。列举了 RSA 算法的数学基础,即数论知识。对其数学原理进行了简 单的说明,详细介绍了其具体算法。为了便于理解,笔者还举了一个简单的加密解密 实例,然后给出了其在 MATLAB 上的算法实现,最后,就其安全性进行了较为简单的 讨论。 由于时间关系,再加上笔者的能力有限,本文中尚有许多不足之处,敬请读者批 评指正。 第 1 章 RSA 简介 2 第 1 章 RSA 简介 1.1 密码体制简介密码体制简介 随着 Internet 的广泛
7、应用,电子商务和电子政务得到的迅速的发展,越来越多的个 人信息需要严格保密,因此,密码学成了必不可少的一门学科。密码技术是密码学的 重要内容,它是集数学,计算机科学,电子与通信等诸多学科于一身的的交叉学科, 它不仅能够保证机密信息的加密,而且能够实现数字签名,身份验证,系统安全等功 能。 目前计算机网络主要采用两种密码体制,对称密码体制和非对称密码体制。 对称密钥体制的加密密钥和解密密钥是相同的,只要知道加密密钥,就能推出解 密密钥,通信双方分别持有加密密钥和解密密钥,需要定期更新密钥。使用对称密码 体制进行保密通信时,通信双方要事先通过秘密的信道传递密钥,而秘密信道时不易 获得的。很久以来,
8、密钥分发的问题一直困扰着密码专家,随着计算机网络的逐渐扩 大,密钥分配所造成的时间延迟和费用问题日益凸显出来。对称密码还有一个缺点, 就是密钥量太大,在有n个用户的通信网络中,系统的总密钥量将达到 2 n C ,这样大的 密钥量在保存,传递,使用和销毁的各个环节中都会有不安全因素存在。此外,在一 些需要验证消息的真实性和消息发送方身份的场合,或在进行电子交易时,必须有手 写签名的数字形式即数字签名来确认身份,这是对称密码无法实现的。 非对称密钥体制不能从加密密钥推出解密密钥,加密和解密是采用一对不同的密 钥进行的,公钥(加密密钥)公开,私钥(解密密钥)保密。例如,甲将他的加密密 钥公开,任何想
9、与甲通信的都可以采用这个加密密钥把要传送的信息(明文)加密成 密文发送给甲,只有甲知道解密密钥,能够将密文还原为明文,而任何第三方即使截 获到密文也不能知道密文所传递的信息。非对称密码体制最有影响的典型算法是 RSA,于 1978 年有美国麻省理工学院的三位数学家瑞弗斯特(Rob Rivest) ,沙米尔 (Adi Shamir)和阿德来门(Len Adleeman)提出,RSA 算法既可用于数据加密,又可 用于数字签名,安全性良好,易于实现和理解。 1.2 RSA 的简介的简介 RSA 是目前最为流行的公钥密码体制之一 ,其安全性是基于分解大素数的困难 四川理工学院毕业论文 3 性,由于其加
10、密函数是一个单向函数,所以对第三方而言,试图在有效的时间内在计 算机上非法解密密文是不可能的。由于 RSA 能实现信息的加密,解密和数字签名,较 好的满足计算机网络应用的需求,因此得到了广泛的应用,主要用于保证以下几点: (1)数据的机密性:预防非法的信息存取和信息在传输过程中被非法窃取。 (2)数据完整性:保证通信中的信息不会被非法篡改,入侵者不能利用其他假消息 替换原始消息。 (3)身份认证:保证对方属于所称实体,是依靠数字签名实现的。 (4)不可抵赖性:发送者无法事后否认其发送过消息,消息的接收者可以像中立的 第三方 CA 证实所指的发送者确实发出了消息。 由于公钥密码体制中通信双方的公
11、钥可以公开,以及其的较好的安全性,该种加 密方式及其相关系统在密钥管理,电子商务中都有着广泛的应用。 第 2 章 相关数论知识 4 第第 2 章章 相关数论知识相关数论知识 2.1 整除与互素整除与互素 定义定义 2.1:设a为b是整数,0b,如果存在Zc,使得bca ,则称b整除a, 记为ab |,并且称b是a的一个因子,而a为b的倍数,若不存在Zc使得bca ,则 称b不整除a,记作a b | 。 定义定义 2.2:一个大于 1 的整数,如果它的正因数只有 1 和它本身,则该数称为素数, 否则叫做合数。 定理定理 2.1:(带余除法)设0,bZba,则存在唯一确定的整数q和r ,使得: r
12、qba,br 0 定义定义 2.3:设ba, 是不全为0的整数,a和b的最大公因数是指满足下述条件的整数 d, (1)d为a和b的公因数,即ad |,且bd |。 (2)d为a和b的所有公因数中最大的,即对Zc,若ac |,且bc |,则dc 。 记作 ),(bad ,如果1),( ,baZba,则称a和b互素。 定理定理 2.2:设任一大于 1 的整数a都能表示成素数的乘积,即 t t pppa 21 21 . 其中 i p是素数,0 i , (ti 1) ,并且,若不考虑 i p的排列顺序,则这种表示方法 是唯一的。 2.2 费马定理和欧拉定理费马定理和欧拉定理 定理定理 2.3:(费马小
13、定理)若p是素数,a p | ,则pa p mod1 1 . 费马定理的等价形式:paa p mod. 定义定义 2.4:设n为正整数,欧拉函数)(n定义为满足条件:nb 0且1),(nb的 整数b的个数。 )(n具有如下性质: (1)当n是素数时,1)( nn; (2)若 k n2,k为正整数,则 1 2)( k n; 四川理工学院毕业论文 5 (3)若pqn ,且1),(qp,则) 1)(1()(qpn; (4)若 t t pppn 21 21 ,)1 (tipi为素数,则: ) 1() 1)(1()( 21 11 2 1 1 21 tt ppppppn t . 定理定理 3.4:(欧拉定
14、理)对于任意整数na,,当1),(na时,有na n mod1 )( . 证明:证明: 设小于n且与n互素的正整数集合为, )(21n xxx , 由于1),( , 1),(nxna i ,故对)(1ni, i ax 仍与n互素。因此 )(21 , n axaxax 构成)(n个与n互素的数,且两两不同余。这是因为,若有 ji xx ,,使 得,modnaxax ji 则由于1),(na,可以消去a,从而nxx ji mod 所以, )(21n axaxax 与, )(21n xxx 在nmod的意义上是两个相同的集合,分别计 算两个集合中各元素的乘积,有 nxxxaxaxax nn mod
15、)(21)(21 由于 )(21 , n xxx 与n互素,故)(mod1 )( na n . 推论推论 3.1 naa n mod 1)( 2.3 中国剩余定理中国剩余定理 中国剩余定理是解一次同余方程组最有效的算法。 首先,我们写出一次同余方程组的一般形式: kk max max max mod mod mod 22 11 如果对任意jikji,1,有1),( ji mm,即 k mmm, 21 两两互素,则有以下固定 算法: (1) 计算 k mmmM 21 ,及 i i m M M ; (2) 求出各 i M 模 i m的逆,即求 1 i M,满足 iii mMMmod1 1 ; (3
16、) 计算MaMMaMMx kkk mod 1 1 1 11 ,x即为方程组的一个解. 例例 2.12.1:求相邻的四个整数,依次可被 2222 7 , 5 ,3 ,2整除. 解解: 设四个整数为2, 1, 1xxxx,则有 第 2 章 相关数论知识 6 49mod2 25mod1 9mod0 4mod1 x x x x 计算 492594M 49259 1 M,2594,4994,49254 432 MMM 30, 9 , 7 . 1 1 4 1 3 1 2 1 1 MMMM 最终求得 44100mod29349x 四川理工学院毕业论文 7 第 3 章 RSA 的数学原理及其算法实现 3.1
17、RSA 的数学原理的数学原理 RSA 算法基于下面的两个事实,保证 RSA 算法的安全有效性: 1)已有确定一个数是不是素数的快速算法; 2)尚未找到确定一个合数的质因子的快速算法: RSA 算法的工作原理 (1)任意选取两个不同的大质数p和q,计算乘积qpn, ) 1() 1()(qpn; (2)任意选取一个大整数e,e与) 1() 1(qp互素,整数 e 用做加密密钥, (注意: e的选取是很容易的,例如,所有大于p和q的质数都可用) (3)确定解密密钥d:) 1)(1mod(1qped,根据e,p,q,可以容易的计算 出d; (4)公开整数n和e,将d保密; (5)将明文p(假设p是一个
18、小于n的整数)加密为密文c,计算方法为: npc e mod (6) 将密文 c 解密为明文 p,计算方法为: ncp d mod 然而,只根据n和e(不是p和q) ,要计算出d是不可能的,因此,任何人都可 以对明文进行加密,但只有授权用户(知道d)才可以对密文进行解密。 例如:向用户 A 发送加密信息时,利用 A 的公开密钥 A n, A e,计算 A e nmmEc A mod)( 求出的整数c即为密文, 当 A 受到c后,利用自己的解密密钥 A d ,计算 A d nccDm A mod)( 由欧拉定理,这里计算出的)(cD恰好等于加密前的明文m. 事实上,由于)(mod1 AAA nd
19、e 1| )( AAA den. 设1)( AAA ntde,Zt ,当 1)(,( A nm时,有: 第 3 章 RSA 的数学原理及其算法设计 8 A m nmmod1 )( 于是: A tnnTde nmmmmmcD AAAA mod)()( )(1)( 这时,对于每一个明文分组m,要求其与模数n互素. 3.2 RSA 的算法设计的算法设计 RSA 加密算法和解密算法的具体步骤: (1)RSA 算法的初始化,系统产生 2 个大素数p和q(保密).计算qpn, (n公开) , ) 1() 1()(qpn,令随机选取整数e作为公钥(加密密钥) ,满足e(公开)和 )(n互质,计算私钥d(解密
20、密钥) ,满足)(mod1nde.销毁p,q及)(n. (2)RSA 加密解密变换,首先将明文分块并数字化,然后将明文分成若干段,使每 个数字化的明文段的值小于n,长度不大于n 2 log,然后对每个明文块m依次进行加密, 解密变换. 加密变换:分别使用公钥e和明文m,得密文nmmEc e mod)( 解密变换:分别使用私钥d和密文c,得明文nccDm d mod)( 例例 3.1:RSA 公钥密码加密解密算法实例 选53p,41q,2173qpn,2080)(n,选择31e,计算出671d. 将n,e公开,d保密, 设明文m为374,对其加密,得到密文: 2173mod446 31 mc.
21、解密时,计算 2173mod374 671 c,恢复出明文374. RSA 的加密解密过程是一个模n的指数运算,计算nmemod这个运算有一个快速 实现的算法如下: 首先,将e表示为二进制形式: 1 1 210 242 r r aaaae,log2er ,1 , 0 i a 然后计算出:nmmmod 2 1 nmnmmmodmod 4 2 12 nmnmm r rr modmod 1 2 2 21 其中,10nmi,11ri, 四川理工学院毕业论文 9 由于: 1 1 101 1 10 )()( 2222 r r r r aaaaaae mmmmm . 而: 1, 0, 1 )( 2 2 i
22、i a am a m i i i 对于给定的e,只需根据其二进制表示,取出1 i a的 i m2相乘即可,由于其中间 结果均为小于n的整数,从而使运算量大大减小. 例例 3.2:计算2173mod37431 作预计算: 2173mod8041398763742 2173mod1035804374 24 2173mod21091035374 28 2173mod19232109374 216 由于 16842131 所以 2173mod44637480410352109192337431 例例 3.3:一个简单的 RSA 加密解密算法 取43p,59q.则25375943n 24365842)(
23、n,13e. 设明文段 2106m 则对于密文2537mod210613c. 做计算 84113 2537mod4312106 2537mod560)431(2106 22 2537mod9885602106 24 2537mod601)988(2106 28 2537mod2321)601()988()431(210613 得密文为2321 现在将其恢复为明文:做计算 )(mod1ned.其中13e,2436)(n 即:1| )(edn,yx,,使得:1)(nyxe,)(xd .即:x的值,因此,用 辗转相除法: 11 rqba br 1 0 221 rqrb 12 0rr . 第 3 章
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 毕业论文 RSA 密码 体制 设计 MATLAB 语言 实现 15105
链接地址:https://www.31doc.com/p-3939326.html