密码学-RSA加密解密算法的实现课程设计报告

密码学课程报告

《RSA加密解密算法》

专业：信息工程（信息安全）

班级：1132102

学号：201130210214

姓名：周林

指导老师：阳红星

时间：2014年1月10号

1

一、课程设计的目的

当前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。

RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。 公钥加密算法中使用最广的是RSA。RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。此外，RSA加密系统还可应用于智能IC卡和网络安全产品。

二、RSA算法的编程思路

确定密钥的宽度。

随机选择两个不同的素数p与q，它们的宽度是密钥宽度的1/2。 计算出p和q的乘积n 。

在2和Φ(n)之间随机选择一个数e , e 必须和Φ(n)互素，整数e用做加密密钥（其中Φ(n)=(p-1)*(q-1)）。

5. 从公式ed ≡ 1 mod Φ(n)中求出解密密钥d 。 6. 得公钥（e ，n ）, 私钥 (d , n) 。 7. 公开公钥，但不公开私钥。

8. 将明文P (假设P是一个小于n的整数)加密为密文C，计算方法为： C = Pe mod n

9.将密文C解密为明文P，计算方法为：P = Cd mod n

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

1. 2. 3. 4.

三、程序实现流程图： 1、密钥产生模块：

2

2、解加密流程模块：

3

四、部分算法代码

判定一个数是否为素数

bool test_prime(Elemtype m) { if (m <= 1) { return false; }

else if (m == 2) { return true; }

else {

for(int i=2; i<=sqrt(m); i++) { if((m % i) == 0) { return false; break; } }

return true; } }

求最大公约数

Elemtype gcd(Elemtype a, Elemtype b) { order(a,b); int r;

if(b == 0) { return a; }

else {

while(true) { r = a % b; a = b; b = r;

if (b == 0) { return a; break;}

用扩展的欧几里得算法求乘法逆元

Elemtype extend_euclid(Elemtype m, Elemtype bin) { order(m,bin);

Elemtype a[3],b[3],t[3];

a[0] = 1, a[1] = 0, a[2] = m; b[0] = 0, b[1] = 1, b[2] = bin; if (b[2] == 0) {

4

return a[2] = gcd(m, bin); }

if (b[2] ==1) {

return b[2] = gcd(m, bin); }

while(true) {

if (b[2] ==1) { return b[1]; break; }

int q = a[2] / b[2];

for(int i=0; i<3; i++) { t[i] = a[i] - q * b[i]; a[i] = b[i];

b[i] = t[i]; }}} 加密

void encrypt() { if(flag == 0) {

cout<<\ produce_key(); }

label3:

cout<<\cin>>m;

while (!cin) {

cin.clear();

char a; cin>>a;

cout<<\goto label3; }

c = modular_multiplication(m,pu.e,pu.n); cout<<\解密

void decrypt() { if(flag == 0) {

cout<<\ produce_key(); }

label4:

cout<<\cin>>c;

5

while (!cin) {

cin.clear(); char a; cin>>a;

cout<<\goto label4; }

m = modular_multiplication(c,pr.d,pr.n); cout<<\

五、部分截图

6

7

六、程序代码

#include #include #include #include #include int go(int k,char bk[16]);

int Transform(int m,int k,int n); int gcd(int a,int b); int IsPrime(int a);

go(int k,char bk[16]) {

int n = 0;

while( k > 0) { bk[n] = k % 2; n++; k/= 2; }

return k; }

int Transform(int m,int k,int n) {

long int r=1; char bk[16]; go(k,bk);

for(int i=15; i>=0; i--) {

r=(r*r)%n; if (bk[i] ==1) {

r=(r*m)%n; } }

return r; }

int gcd(int a,int b) {

for(int i=2;i <=sqrt(a

8

return 1; }

int IsPrime(int a) {

for(int i=2;i <=sqrt(a);i++) if(a%i==0) return 0; return 1; }

void main() {

int c,e,d,m,n,z,p,q;

cout << \简单RSA加密解密算法***********\\n\\n \ cout <<\请输入 p: \ cin>> p;

while(!IsPrime(p)) {

cout << \您输入的p不是素数，请重新输入: \ cin>> p; }

cout << \请输入q: \ cin>> q;

while(!IsPrime(q)) {

cout << \您输入的q不是素数，请重新输入: \ cin>> q; }

cout << \由p和q求得n和ф(n) \ n=p*q;

z=(p-1)*(q-1);

cout << \ and \<> e;

while (!gcd(e,z)) {

cout << \应该和ф(n)互素: \ cin>> e; }

cout << \求得解密密钥\ d=1;

while (((e*d)%z)!=1) d++;

9

cout << \ << d << endl; cout <> m;

while (m>=n||m<=0) {

cout << \请重新输入明文m（0> m; }

cout << \求得密文为：\ c=Transform(m,e,n);

cout << \

cout <> c;

cout << \求得明文为：\ m=Transform(c,d,n);

cout << \ getch(); }

七、 心得体会

通过做此次课程设计，对RSA加密解密算法有了更近一步的了解。RSA通过使用公钥加密、私钥解密，完成了乙方到甲方的一次数据传递，通过私钥加密、公钥解密，同时通过私钥签名、公钥验证签名，完成了一次甲方到乙方的数据传递与验证，两次数据传递完成一整套的数据交互！掌握了RSA算法的基本原理、体验应用效果，以及如何判断一个数是否为素数，以及用扩展的欧几里得算法求乘法逆元问题，以及解密和加密算法。虽然中间遇到了一些难题，但是在老师及同学的帮助下，顺利完成此次课程设计。

10

本文来源：https://www.bwwdw.com/article/7vnr.html