当前位置：文档之家 › RSA算法分析和实现

RSA算法分析和实现

  • 格式：doc
  • 大小：47.50 KB
  • 文档页数：4

1 《应用密码学》实验报告

实验序号：03 实验项目名称：RSA密码技术

学 号 姓 名 专业、班

实验地点 指导教师 实验时间

一、实验目的及要求

实验目的：

1． 深入理解RSA原理，特别是大数分解难题的原理

2． 明确选择RSA的参数p、q、e、d的条件，以及明文分段的条件

3． 掌握求逆元素和求高次幂的计算方法

4． 了解寻找素数的方法

5． 了解素数、同余类、欧拉函数、费马定理、欧拉定理

要求：

1. 要求实验前做好准备，熟悉实验相关的技术和原理，制定实验方案，编写相关的程序或文档；实验独立完成，认真观察与思考；实验后进行分析小结，写出实验报告。

2. 用C语言实现

3. 撰写实验报告

二、实验设备（环境）及要求

微机、C语言

环境：Microsoft Visual C++ 6.0

用C语言实现选定的加密算法和相应的解密算法

三、实验内容与步骤

RSA实验原理和数据模型

首先, 找出三个数, p, q, r,

其中 p, q 是两个相异的质数, r 是与 (p-1)(q-1) 互质的数，

p, q, r 这三个数便是 private key 。

接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1).....

这个 m 一定存在, 因为 r 与 (p-1)(q-1) 互质, 用辗转相除法就可以得到 2 了。

再来, 计算 n = pq ，

m, n 这两个数便是 public key 。

编码过程是, 若资料为 a, 将其看成是一个大整数, 假设 a < n....

如果 a >= n 的话, 就将 a 表成 s 进位 (s <= n, 通常取 s = 2^t),

则每一位数均小於 n, 然後分段编码......

接下来, 计算 b == a^m mod n, (0 <= b < n),

b 就是编码後的资料

解码的过程是, 计算 c == b^r mod pq (0 <= c < pq),

於是乎, 解码完毕...... 等会会证明 c 和 a 其实是相等的:)

如果第三者进行窃听时, 他会得到几个数: m, n(=pq), b

他如果要解码的话, 必须想办法得到 r......

所以, 他必须先对 n 作质因数分解.........

要防止他分解, 最有效的方法是找两个非常的大质数 p, q,

使第三者作因数分解时发生困难。

<定理>

若 p, q 是相异质数, rm == 1 mod (p-1)(q-1),

a 是任意一个正整数, b == a^m mod pq, c == b^r mod pq,

则 c == a mod pq

证明的过程, 会用到费马小定理, 叙述如下:

m 是任一质数, n 是任一整数, 则 n^m == n mod m

(换另一句话说, 如果 n 和 m 互质, 则 n^(m-1) == 1 mod m)

运用一些基本的群论的知识, 就可以很容易地证出费马小定理的。

<证明> 3 因为 rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整数

因为在 modulo 中是 preserve 乘法的

(x == y mod z and u == v mod z => xu == yv mod z),

所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq

1. 如果 a 不是 p 的倍数, 也不是 q 的倍数时则 a^(p-1) == 1 mod p (费马小定理) => a^(k(p-1)(q-1)) == 1 mod p

a^(q-1) == 1 mod q (费马小定理) => a^(k(p-1)(q-1)) == 1 mod q ，

所以p, q 均能整除

a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1

即a^(k(p-1)(q-1)) == 1 mod pq => c== a^(k(p-1)(q-1)+1) == a mod pq

2. 如果 a 是 p 的倍数, 但不是 q 的倍数时,

则 a^(q-1) == 1 mod q (费马小定理)

=> a^(k(p-1)(q-1)) == 1 mod q

=> c == a^(k(p-1)(q-1)+1) == a mod q

=> q | c - a

因 p | a

=> c == a^(k(p-1)(q-1)+1) == 0 mod p

=> p | c - a

所以, pq | c - a => c == a mod pq

3. 如果 a 是 q 的倍数, 但不是 p 的倍数时, 证明同上

4. 如果 a 同时是 p 和 q 的倍数时,

则 pq | a

=> c == a^(k(p-1)(q-1)+1) == 0 mod pq

=> pq | c - a

=> c == a mod pq

这个定理说明a经过编码为b在经过解码为C时，a==c mod n （n=pq） 4 但我们在做编码解码时, 限制 0 <= a < n, 0 <= c < n,

所以这就是说 a 等於 c, 所以这个过程确实能做到编码解码的功能。

四、实验结果与数据处理

五、总结

通过对RSA公钥密码体制进行了分析与研究，了解了怎样的密码体制才能充分发挥RSA的安全作用。分析了RSA加密解密的安全性，以及如何选取RSA密钥长度的问题。同时我们考虑到在实际的应用过程中，在满足安全性前提下应当降低计算的复杂度，提高信息加、解密的速度。便于降低成本，利于推广应用等因素，目前国内外对RSA算法实现的研究大多是在运算速度很高的计算机上，在硬件上也主要采用串行处理，为了提高速度，安全性就必然很差，相反，为提高安全强度，则运算处理速度又会降低。在RSA算法中，最基本的算法主要包括模加、模乘、模逆和模幂运算。大数运算很费时间，尤其是大整数的模逆和模幂运算。为了得到较快的加/解密速度，本程序进行了深层次的优化，主要采用移位的方法，大大提高了RSA算法实际应用的运算速度和执行效率。

总之，随着密码技术的进一步发展，以及计算机安全研究的技术人员的不断努力，我相信具有更高性能、更高效率的密码加密体制将会诞生。

六、教师评语

签名：

日期： 成绩

合集下载

(完整版)公开密钥加密算法RSA的Matlab实现本科毕业设计

(完整版)公开密钥加密算法RSA的Matlab实现本科毕业设计

公开密钥加密算法RSA的Matlab实现

[摘要]RSA算法是基于数论的公开密钥加密算法，它已经成为现在最流行的公钥加密算法和数字签名算法之一。其算法的安全性基于数论中大素数分解的困难性，所以RSA公钥密码体制算法的关键是如何产生大素数和进行大指数模幂运算。本文首先介绍了RSA 公开密钥加密算法的数学原理，并介绍了几种流行的产生大素数的算法。然后用matlab具体实现公钥加密算法RSA的加密和解密，从而实现了数据的安全传输。

[关键词] RSA算法；加密；素数

The Realization of RSA Algorithm for Public Key

Encryption Based on Matlab

(Grade 07,Class 3,Major electronics and information engineering ，Communication

engineering Dept.， Tutor:

[abstract] :The algorithm is based on the theory of RSA public key encryption

algorithm, it has become the most popular public key encryption algorithm

and digital signature algorithm of one. The safety of the algorithm based

on number theory cuhk the difficulty of prime decomposition, so the RSA public

key cryptography algorithms is key to how to produce large prime Numbers DaZhi

and transmit power operation. This paper first introduced the RSA public key

RSA加密算法(C语言实现)

RSA加密算法(C语言实现)

RSA加密算法（C语言实现）

RSA（Rivest-Shamir-Adleman）算法是一种非对称加密算法，它是目前应用最广泛的加密算法之一、RSA算法基于两个大素数之间的乘积很难分解的特性，并使用公钥和私钥进行加密和解密。

在C语言中实现RSA算法需要进行以下步骤：

1.生成大素数p和q：选择两个大素数p和q，它们需要满足p≠q。这样选取p和q是为了使得计算n=p*q变得困难，保护私钥。

2.计算n：计算n=p*q，n即为公钥和私钥的参数之一

3.计算欧拉函数φ(n)：计算欧拉函数φ(n)=(p-1)*(q-1)。

4.选择e：选择一个与φ(n)互质且小于φ(n)的整数e作为加密指数，e即为公钥的参数。

5. 计算d：计算d = e^(-1) mod φ(n)，d即为私钥的参数。可以使用扩展欧几里得算法来计算d。

6. 加密：将明文M转换为整数m，加密后的密文C = m^e mod n。

7. 解密：解密密文C得到明文M = C^d mod n。

以下是C语言实现RSA加密算法的代码示例：

```c

#include

int gcd(int a, int b)

if(b == 0) return a;

}

return gcd(b, a % b);

int extendedGcd(int a, int b, int *x, int *y)

if(a == 0)

*x=0;

*y=1;

return b;

}

int x1, y1;

int gcd = extendedGcd(b % a, a, &x1, &y1);

*x=y1-(b/a)*x1;

*y=x1;

return gcd;

int modInverse(int a, int m)

int x, y;

int gcd = extendedGcd(a, m, &x, &y);

if(gcd != 1)

printf("Inverse doesn't exist\n"); return -1;

简述rsa加密算法原理

简述rsa加密算法原理

简述rsa加密算法原理

RSA加密算法原理

RSA加密算法是一种非对称加密算法，由三位数学家Rivest、Shamir和Adleman于1977年提出。它的安全性基于大数分解的困难性，可以用于数字签名、密钥交换等领域。下面将从以下几个方面详细介绍RSA加密算法原理。

1. 公钥密码学

公钥密码学是一种密码学技术，它采用两个不同但相关的密钥：一个公钥和一个私钥。公钥可以自由地分发给任何人，而私钥则只能由其拥有者保管。使用公钥加密的数据只能使用相应的私钥进行解密，反之亦然。公钥密码学具有高度的安全性和灵活性，可以广泛应用于数据传输、数字签名等方面。

2. RSA算法生成密钥对

RSA算法生成密钥对的过程如下：

（1）选择两个大质数p和q，并计算它们的乘积n=pq。

（2）计算欧拉函数φ(n)=(p-1)(q-1)。

（3）选择一个整数e(1

（4）计算d=d^-1(mod φ(n))，其中d满足de≡1(mod φ(n))。

（5）公钥为(n,e)，私钥为(n,d)。

其中，p和q是足够大的质数，n是它们的乘积，φ(n)是n的欧拉函数，e是一个与φ(n)互质的整数，d是e在模φ(n)意义下的逆元。

3. RSA算法加密过程

RSA算法加密过程如下：

（1）将明文转换成整数m(0<=m

（2）计算密文c≡m^e(mod n)，其中e为公钥中的指数。

（3）将密文c发送给接收者。

其中，m是明文，n和e是接收者的公钥，c是密文。

4. RSA算法解密过程

RSA算法解密过程如下：

（1）接收到密文c。

（2）计算明文m≡c^d(mod n)，其中d为私钥中的指数。

其中，c是密文，n和d是接收者的私钥，m是明文。

5. RSA算法安全性分析

RSA算法安全性基于大数分解的困难性。即如果能够快速地分解出p和q，则可以轻松地计算出d，并从而破解RSA加密。但目前尚未发现快速分解大整数的有效方法。因此，在足够长的密钥长度下，RSA加密被认为具有高度的安全性。

RSA公钥密码算法的研究与实现

RSA公钥密码算法的研究与实现

第２２卷第２期　２００６年４月　忻州师范学院学报　ＪＯＵＲＮＡＬ　ＯＦ　ＸＩＮＺＨＯＵ　ＴＥＡＣＨＥＲＳ　ＵＮＩＶＥＲＳＩＴＹ　ＶｏＩ．２２　Ｎｏ．２　Ａｐｒ．２００６　

ＲＳＡ公钥密码算法的研究与实现　

冯素琴　

（忻州师范学院，山西忻州０３４０００）　

摘要：ＲＳＡ公钥密码算法的基础是欧拉定理，它的安全性依赖于大素数因式分解的困　

难性。ＲＳＡ算法通常是先生成一对密钥。文章对生成密钥过程中所需参数进行分析和讨论，　

并结合实例对ＲＳＡ公钥密码算法进行了实现。　

关键词：公钥密码；ＲＳＡ算法；欧拉定理　

中图分类号：ＴＰ３９３　文献标识码：Ａ　文章编号：１６７１—１４９１（２００６）０２—００４７—０４　

０引言　随着计算机联网的逐步实现，全球正在进入信息经济时　代。无论是个人信息通信还是电子商务，都需要保证网上信　息传输的安全、保密、真实和完整。信息安全的核心是密码　

技术，密码技术是集数学、计算机科学、电子与通信等诸多学　科于一身的交叉学科，它不仅能够保证机密性信息的加密，　

而且能够实现数字签名、身份验证、系统安全等功能。当前　最著名、应用最广泛的公钥系统ＲＳＡ是一个基于数论的非　对称密码体制，是一种分组密码体制。它的安全性是基于大　素数因子分解的困难性，而大素数因子分解问题是数学上的　

著名难题，至今没有有效的方法予以解决，因此可以确保　ＲＳＡ算法的安全性。　

１　ＲＳＡ公钥密码算法原理　ＲＳＡ算法是根据寻求两个大素数比较简单，而将它们　

的乘积分解开则极其困难的原理来设计的。．为提高保密强　度，ＲＳＡ密钥至少为５００位长，一般推荐使用１０２４位。表１　给出了在计算机每一微秒做一次操作的假定下，分解不同大　

小的Ｎ所需要的时间。　表ｌ大素数分解用时统计裹　

Ｎ的十进位数　５０　７５　１ｏｏ　２００　

时间　３．９时　１０４天　７４年　３．８Ｘ１０１５年　

具体步骤：　

（１）选取两个大素数Ｐ和ｑ。为了获得最大的安全性，　

两个素数的长度一样。并计算乘积Ｎ（Ｎ＝Ｐｑ）。　（２）计算出Ｎ的欧拉函数币（Ｎ）＝（Ｐ一１）（ｑ—１），币　（』、，）定义为不超过』、，并与』、，互素的数的个数。　（３）从Ｅ０，西（Ｎ）一１］中随机选取加密密钥ｅ，使得ｅ和