RSA密码体制的设计及MATLAB语言下的实现论文

四川理工学院毕业论文

RSA密码体制的设计及MATLAB语言下的实现

学 生：XXX

学 号：06121020230

专 业：数学与应用数学

班 级：2006.2

指导教师：张金山

四川理工学院理学院

二O一O年六月

RSA密码体制的设计及MATLAB语言下的实现论文

四 川 理 工 学 院

毕业论文任务书

论文题目： RSA密码体制的设计及MATLAB语言下的实现

二级学院： 理学院 专业：数学与应用数学 班级： 2006级2班 学号： 06121020230 学生： XXX 指导教师： 张金山

接受任务时间： 2010年3月10日

（系）教研室主任 （签名） 理学院院长 （签名）

1．毕业论文的主要内容及基本要求

主要内容：从RSA的产生背景入手，熟悉RSA在信息安全方面的应用，对其数学基础，数学原理，算法设计进行了详细的介绍，并给出其在MATLAB应用软件上的实现，同时，对RSA的安全性，参数选择进行了分析。

基本要求：在明确了主要任务上做到（1）查阅文献资料，了解课题前沿，确定课题研究思路

（2）理清论文思路，安排论文内容（3）撰写出思路清晰，逻辑合理的论文。

2．指定查阅的主要参考文献及说明

[1]杨晓元，魏立线.计算机密码学[M].西安，西安交通大学出版社

[2]朱文余，孙琦.计算机密码应用基础[M].北京，科学出版社

[3]闵嗣鹤，严士健.初等数论[M].北京，高等教育出版社

[4]李海涛，邓樱，MATLAB6.1基础及应用技巧[M].北京，国防工业出版社

[5]李晓辉.公钥密码体制与RSA算法[J].福建电脑.2009

[6]刘栋梁，陈艳萍.RSA密码体制在电子商务中的安全应用[J].大众科技.2005

[7]段晓萍，李燕华.非对称密码体制RSA的原理与实现[J].内蒙古大学学报.2009

RSA密码体制的设计及MATLAB语言下的实现论文

摘 要

RSA算法是一个能同时用于加密和数字签名的算法，易于理解和操作，有较高的安全性，因此有着广泛的运用。本文首先论述了RSA的基本运用途径，RSA的数学原理，其加密解密的具体算法，并给出了其在MATLAB应用软件上的实现，然后，对RSA的安全性进行了一定的分析，包括其可能存在的攻击和对参数的选择，以便对其有更深的了解。

关键词：RSA 公钥密码体制 加密 解密 MATLAB 安全性

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 purpose, 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.

Keywords : RSA public key cryptography encryption decrypt MATLAB

security

RSA密码体制的设计及MATLAB语言下的实现论文

目 录

前 言 ............................................................................................................................................................ 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

4.2 RSA的参数选择 ............................................................................................................................. 15

结束语 .......................................................................................................................................................... 16

参考文献 ...................................................................................................................................................... 17

致 谢 .......................................................................................................................................................... 18

RSA密码体制的设计及MATLAB语言下的实现论文

RSA密码体制的设计及MATLAB语言下的实现论文

前 言

随着计算机通信技术的迅速发展，在计算机网络和通信的众多领域中，信息的安全性越来越受到人们的重视，于是，密码技术应运而生，目前计算机网络主要采用两种密码体制，即公钥密码体制和私钥密码体制，作为公钥密码体制的重要技术的RSA，主要用于数字加密和数字签名，由于其很好的安全性，可以保证网络中重要数据的安全性，因此有广泛的应用。

RSA于1978年由美国麻省理工大学的三位数学家提出，经过三十多年的发展，人们对它的研究也逐渐广泛，它是第一个能用于数据加密和数字签名的算法，其安全性依赖于大数的因子分解，因此，具有较高的安全性，有时也用于密钥的管理。

本文较为详细的介绍了密码体制的相关内容，包括RSA的主要应用及其在计算机网络中的重要性。列举了RSA算法的数学基础，即数论知识。对其数学原理进行了简单的说明，详细介绍了其具体算法。为了便于理解，笔者还举了一个简单的加密解密实例，然后给出了其在MATLAB上的算法实现，最后，就其安全性进行了较为简单的讨论。

由于时间关系，再加上笔者的能力有限，本文中尚有许多不足之处，敬请读者批评指正。

RSA密码体制的设计及MATLAB语言下的实现论文

第1章 RSA简介

1.1 密码体制简介

随着Internet的广泛应用，电子商务和电子政务得到的迅速的发展，越来越多的个人信息需要严格保密，因此，密码学成了必不可少的一门学科。密码技术是密码学的重要内容，它是集数学，计算机科学，电子与通信等诸多学科于一身的的交叉学科，它不仅能够保证机密信息的加密，而且能够实现数字签名，身份验证，系统安全等功能。

目前计算机网络主要采用两种密码体制，对称密码体制和非对称密码体制。

对称密钥体制的加密密钥和解密密钥是相同的，只要知道加密密钥，就能推出解密密钥，通信双方分别持有加密密钥和解密密钥，需要定期更新密钥。使用对称密码体制进行保密通信时，通信双方要事先通过秘密的信道传递密钥，而秘密信道时不易获得的。很久以来，密钥分发的问题一直困扰着密码专家，随着计算机网络的逐渐扩大，密钥分配所造成的时间延迟和费用问题日益凸显出来。对称密码还有一个缺点，就是密钥量太

2大，在有n个用户的通信网络中，系统的总密钥量将达到Cn，这样大的密钥量在保存，

传递，使用和销毁的各个环节中都会有不安全因素存在。此外，在一些需要验证消息的真实性和消息发送方身份的场合，或在进行电子交易时，必须有手写签名的数字形式即数字签名来确认身份，这是对称密码无法实现的。

非对称密钥体制不能从加密密钥推出解密密钥，加密和解密是采用一对不同的密钥进行的，公钥（加密密钥）公开，私钥（解密密钥）保密。例如，甲将他的加密密钥公开，任何想与甲通信的都可以采用这个加密密钥把要传送的信息（明文）加密成密文发送给甲，只有甲知道解密密钥，能够将密文还原为明文，而任何第三方即使截获到密文也不能知道密文所传递的信息。非对称密码体制最有影响的典型算法是RSA，于1978年有美国麻省理工学院的三位数学家瑞弗斯特（Rob Rivest），沙米尔（Adi Shamir）和阿德来门（Len Adleeman）提出，RSA算法既可用于数据加密，又可用于数字签名，安全性良好，易于实现和理解。

1.2 RSA的简介

RSA是目前最为流行的公钥密码体制之一 ，其安全性是基于分解大素数的困难性，由于其加密函数是一个单向函数，所以对第三方而言，试图在有效的时间内在计算

RSA密码体制的设计及MATLAB语言下的实现论文

机上非法解密密文是不可能的。由于RSA能实现信息的加密，解密和数字签名，较好的满足计算机网络应用的需求，因此得到了广泛的应用，主要用于保证以下几点：

（1）数据的机密性：预防非法的信息存取和信息在传输过程中被非法窃取。

（2）数据完整性：保证通信中的信息不会被非法篡改，入侵者不能利用其他假消息替换原始消息。

（3）身份认证：保证对方属于所称实体，是依靠数字签名实现的。

（4）不可抵赖性：发送者无法事后否认其发送过消息，消息的接收者可以像中立的第三方CA证实所指的发送者确实发出了消息。

由于公钥密码体制中通信双方的公钥可以公开，以及其的较好的安全性，该种加密方式及其相关系统在密钥管理，电子商务中都有着广泛的应用。

RSA密码体制的设计及MATLAB语言下的实现论文

第2章 相关数论知识

2.1整除与互素

定义2.1：设a为b是整数，b 0，如果存在c Z，使得a bc，则称b整除a，记为b|a，并且称b是a的一个因子，而a为b的倍数，若不存在c Z使得a bc，则称b不整除a，记作b |a。

定义2.2：一个大于1的整数，如果它的正因数只有1和它本身，则该数称为素数，否则叫做合数。

定理2.1：（带余除法）设a,b Z,b 0，则存在唯一确定的整数q和r，使得： a qb r，0 r b

定义2.3：设a,b是不全为0的整数，a和b的最大公因数是指满足下述条件的整数d，

（1）d为a和b的公因数，即d|a，且d|b。

（2）d为a和b的所有公因数中最大的，即对 c Z，若c|a，且c|b，则c d。 记作 d (a,b)，如果a,b Z,(a,b) 1，则称a和b互素。

定理2.2：设任一大于1的整数a都能表示成素数的乘积，即

1 2p2 pt t. a p1

其中pi是素数， i 0，（1 i t），并且，若不考虑pi的排列顺序，则这种表示方法是唯一的。

2.2 费马定理和欧拉定理

定理2.3：（费马小定理）若p是素数，p |a，则ap 1 1modp.

费马定理的等价形式：ap amodp.

定义2.4：设n为正整数，欧拉函数 (n)定义为满足条件：0 b n且(b,n) 1的整数b的个数。

(n)具有如下性质：

（1）当n是素数时， (n) n 1；

（2）若n 2k，k为正整数，则 (n) 2k 1；

RSA密码体制的设计及MATLAB语言下的实现论文

（3）若n pq，且(p,q) 1，则 (n) (p 1)(q 1)；

1 2p2 pt t，pi(1 i t)为素数，则： （4）若n p1

1 (n) p1p212 1 pt t 1(p1 1)(p2 1) (pt 1).

定理3.4：（欧拉定理）对于任意整数a,n，当(a,n) 1时，有a (n) 1modn.

证明： 设小于n且与n互素的正整数集合为{x1,x2, x (n)}，

由于(a,n) 1,(xi,n) 1，故对1 i (n)，axi仍与n互素。因此

ax1,ax2, ax (n)构成 (n)个与n互素的数，且两两不同余。这是因为，若有xi,xj，使得axi axjmodn,则由于(a,n) 1，可以消去a，从而xi xjmodn

所以{ax1,ax2, ,ax (n)}与{x1,x2, ,x (n)}在modn的意义上是两个相同的集合，分别计算两个集合中各元素的乘积，有

ax1 ax2 ax (n) x1 x2 x (n)modn

由于x1,x2, x (n)与n互素，故a (n) 1mod (n).

推论3.1 a (n) 1 amodn

2.3 中国剩余定理

中国剩余定理是解一次同余方程组最有效的算法。

首先，我们写出一次同余方程组的一般形式：

x a1modm1 x amodm 22 x akmodmk

如果对任意1 i,j k,i j，有(mi,mj) 1，即m1,m2, ,mk两两互素，则有以下固定算法：

（1） 计算M m1m2 mk，及Mi M； mi

（2） 求出各Mi模mi的逆，即求Mi 1，满足MiMi 1 1modmi；

（3） 计算x M1M1 1a1 MkMk 1akmodM，x即为方程组的一个解.

例2.1：求相邻的四个整数，依次可被22,32,52,72整除.

解： 设四个整数为x 1,x,x 1,x 2，则有

RSA密码体制的设计及MATLAB语言下的实现论文

x 1mod4

x 0mod9

x 1mod25

x 2mod49

计算

M 4 9 25 49

M1 9 25 49，M2 4 25 49,M3 4 9 49,M4 4 9 25

M 1 1.M 1 1

12 7,M 1

3 9,M4 30

最终求得 x 29349mod44100

RSA密码体制的设计及MATLAB语言下的实现论文

第3章 RSA的数学原理及其算法实现

3.1 RSA的数学原理

RSA算法基于下面的两个事实，保证RSA算法的安全有效性：

1）已有确定一个数是不是素数的快速算法；

2）尚未找到确定一个合数的质因子的快速算法：

RSA算法的工作原理

（1）任意选取两个不同的大质数p和q，计算乘积n p q， (n) (p 1) (q 1)；

（2）任意选取一个大整数e，e与(p 1) (q 1)互素，整数e用做加密密钥，（注意：e的选取是很容易的，例如，所有大于p和q的质数都可用）

（3）确定解密密钥d：d e 1mod(p 1)(q 1)，根据e，p，q，可以容易的计算出d；

（4）公开整数n和e，将d保密；

（5）将明文p（假设p是一个小于n的整数）加密为密文c，计算方法为：

c pemodn

（6） 将密文c解密为明文p，计算方法为：

p cdmodn

然而，只根据n和e（不是p和q），要计算出d是不可能的，因此，任何人都可以对明文进行加密，但只有授权用户（知道d）才可以对密文进行解密。

例如：向用户A发送加密信息时，利用A的公开密钥nA，eA,计算

c E(m) meAmodnA

求出的整数c即为密文，

当A受到c后，利用自己的解密密钥dA，计算

nA m D(c) cdAmod

由欧拉定理，这里计算出的D(c)恰好等于加密前的明文m.

事实上，由于eAdA 1mod (nA)

(nA)|eAdA 1.

设eAdA t (nA) 1，t Z，当 (m, (nA)) 1时，有：

m (m) 1modnA

RSA密码体制的设计及MATLAB语言下的实现论文

于是： D(c) meAdA mT (nA) 1 (m (nA))t m mmodnA

这时，对于每一个明文分组m，要求其与模数n互素.

3.2 RSA的算法设计

RSA加密算法和解密算法的具体步骤：

（1）RSA算法的初始化，系统产生2个大素数p和q（保密）.计算n p q，（n公开），

，满足e（公开）和 (n) (n) (p 1) (q 1)，令随机选取整数e作为公钥（加密密钥）

互质，计算私钥d（解密密钥），满足e d 1mod (n).销毁p，q及 (n).

（2）RSA加密解密变换，首先将明文分块并数字化，然后将明文分成若干段，使每个数字化的明文段的值小于n，长度不大于log2n，然后对每个明文块m依次进行加密，解密变换.

加密变换：分别使用公钥e和明文m，得密文c E(m) memodn

解密变换：分别使用私钥d和密文c，得明文m D(c) cdmodn

例3.1：RSA公钥密码加密解密算法实例

选p 53，q 41，n p q 2173， (n) 2080，选择e 31，计算出d 671. 将n，e公开，d保密，

设明文m为374，对其加密，得到密文：

c m31 446mod2173.

解密时，计算 c671 374mod217，恢复出明文3374.

RSA的加密解密过程是一个模n的指数运算，计算memodn这个运算有一个快速实现的算法如下：

首先，将e表示为二进制形式：

e a0 2a1 4a2 2r 1ar 1，r [log2e]，ai {0,1}

然后计算出：m1 m2modn

n m4modn m2 m1mod2

…

n m2modn mr 1 mr 2mod2r 1

其中，0 mi n 1，1 i r 1，

由于：me ma0 2a1 2

r 1ar 1 ma0 (m2)a1 (m2)ar 1. r 1

RSA密码体制的设计及MATLAB语言下的实现论文

1,ai 0而：(m) 2i m,ai 12iai

对于给定的e，只需根据其二进制表示，取出ai 1的m2相乘即可，由于其中间结果均为小于n的整数，从而使运算量大大减小.

例3.2：计算37431mod2173

作预计算：

3742 139876 804mod217 3

3744 8042 103m5od217 3

3748 10325 210m9od217 3

16 374 21029 192m3od217 3i

由于 31 1 2 4 8 16

31所以 374 192 3210 9103 5804 374 446mod217 3

例3.3：一个简单的RSA加密解密算法

取p 43，q 59.则n 43 59 2537 (n) 42 58 2436，e 13.

设明文段 m 2106

则对于密文c 210613mod2537.

做计算 13 1 4 8

2106 431mod2537

21062 ( 431)2 560mod2537

2 2104 6 560 988mod2537

)2 601mod2537 21086 ( 988

210613 ( 431) ( 988) ( 601) 2321mod2537

得密文为2321

现在将其恢复为明文：做计算

d e 1mod (n).其中e 13， (n) 2436

即： (n)|d e 1， x,y，使得：e x y (n) 1，(d x).即：x的值，因此，用辗转相除法：

a b q1 r1 0 r1 b

b r1 q2 r2 0 r2 r1

…….

rn 2 rn 1 qn rn 0 rn rn 1

RSA密码体制的设计及MATLAB语言下的实现论文

rn 1 rn qn 1

其中：Q0 0,Q1 1,Qk qk Qk 1 Qk 2，得x ( 1)n 1Qn

代入数据得：d x 937

则明文m 2321937mod2537

又 937 1 8 32 128 256 512

计算：2321 216mod2537

23212 ( 216)2 990mod2537

23214 9902 818mod2537

23281 8182 644mod2537

232161 ( 644)2 120m5od253 7

232321 12025 861mod253 7

232164 8612 517mod2537

2321281 5172 904mod2537

2322561 9042 302mod253 7

2321512 3022 128mod253 7

2321937 ( 216) ( 644) 861 904 302 ( 128) 2106mod2537

得明文为：2106

3.3 RSA的MATLAB实现

1. 模n求逆函数

function [d]=moni(u,n)

n1=n;

n2=u;

b1=0;

b2=1;

for i=0:1000

q=floor(n1/n2);

r=n1-q*n2;

i=i+1;

if r~=0