实验4 非对称密码算法RSA
时间：2025-03-17
实验4 非对称密码算法RSA（验证型）
一、 实验目的
通过实际编程了解非对称密码算法RSA的加密和解密过程，加深对非对称密码算法的认识。
二、 实验原理
对称密码算法要求通信双方通过交换密钥实现使用同一个密钥，这在密钥的管理、发布和安全性方面存在很多问题，而非对称密码算法解决了这个问题。加密密钥和解密密钥是不同的，其中加密密钥是可以公开的，解密密钥是要求保密的，并且不能用其中的一个推导出另一个。它的安全性是建立在“大数分解和素性检测”这个数论难题的基础上，即将两个大素数相乘在计算上容易实现，而将该乘积分解为两个大素数因子的计算量相当大。虽然它的安全性还未能得到理论证明，但经过30年的密码分析和攻击，迄今仍然被实践证明是安全的。
三、 实验环境
运行Windows或者Linux操作系统的PC机，具有gcc（Linux）、VC（Windows）等C语言编译环境。
四、 实验内容和步骤
1、为了加深对RSA算法的了解，根据已知参数：p 3,q 11,M 2，手工计算公私钥，并对明文进行加密，然后对密文进行解密。
2、编写RSA程序，加密一段文字，了解RSA算法原理。尝试加密一大段文字，记录程序的运行时间。使用DES算法加密相同的文字，比较两种算法加密的速度。
3、编写一个程序，随机选择3个 较大的数x,e,n ，计算xemodn ，记录 程序运行时间。
查阅资料给出简单说明大数在计算机上是如何表示，如何进行运算。
4、查阅资料，找出目前实际可行的素数判定法则，并比较各自的优缺点。 五、实验步骤
1、p=3，q=11 则n=pq=33,f(n)=20，选择e=7,则d=3
那么加密得c=29 解密得m=2
2、打开VC++，编写程序如下：
#include<stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
//using namespace std;
typedef struct RSA_PARAM_Tag
{ //64 位数
unsigned __int64 p, q; //两个素数，不参与加密解密运算
unsigned __int64 f; //f=(p-1)*(q-1)，不参与加密解密运算
unsigned __int64 n, e; //公匙，n=p*q，gcd(e,f)=1
unsigned __int64 d; //私匙，e*d=1 (mod f)，gcd(n,d)=1
unsigned __int64 s; //块长，满足2^s<=n的最大的s，即log2(n) } RSA_PARAM;//小素数表,用于素性测试前,用小素数来初步筛选素数.
const static unsigned __int64 g_PrimeTable[]=
{
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97
};
const static long g_PrimeCount=sizeof(g_PrimeTable) / sizeof(long); //乘数
const unsigned __int64 multiplier=12747293821;
// 加数
const unsigned __int64 adder=1343545677842234541;
//随机数类
class RandNumber
{
private:
unsigned __int64 randSeed;/* */
public:
RandNumber(unsigned __int64 s=0);
unsigned __int64 Random(unsigned __int64 n);
};/* */
RandNumber::RandNumber(unsigned __int64 s)
{
if(!s)
{
randSeed= (unsigned __int64)time(NULL);
}
else
{
randSeed=s;
}
}/* 一个简单的随机数产生算法*/
unsigned __int64 RandNumber::Random(unsigned __int64 n)
{
randSeed=multiplier*randSeed+adder;
return randSeed%n;
}
//定义了一个静态的类对象
static RandNumber g_Rnd;/*
模乘运算，返回值 x=a*b mod n
*/
inline unsigned __int64 MulMod(unsigned __int64 a, unsigned __int64 b, unsigned __int64 n)
{
return a * b % n;
}/*
模幂运算，返回值 x=base^pow mod n
*/
unsigned __int64 PowMod(unsigned __int64 base, unsigned __int64 pow, unsigned __int64 n)
{
unsigned __int64 r=1; pow=pow+1; while(pow!=1) { //循环结果为pow(a,b)%c
}
/* r=r*base; r=r%n; pow--; } return r;
{ unsigned __int64 a=base, b=pow, c=1;
while(b)
{
while(!(b & 1))
{
b>>=1; //a=a * a % n; //函数看起来可以处理64位的整数，但由于这里a*a在a>=2^32时已经造成了溢出，因此实际处理范围没有64位
a=MulMod(a, a, n);
}
b--; //c=a * c % n; //这里也会溢出，若把64位整数拆为两个32位整数不知是否可以解决这个问题。
c=MulMod(a, c, n);
}
}/*
Rabin-Miller素数测试，通过测试返回1，否则返回0。
n是待测素数。
注意：通过测试并不一定就是素数，非素数通过测试的概率是1/4
*/
long RabinMillerKnl(unsigned __int64 &n)
{
unsigned __int64 b, m, s, z, r; return c;
m=n - 1;
s=0; //0、先计算出m、s，使得n-1=m*2^s，其中m是正奇数，s是非负整数
while(!(m & 1))
{
++s;
m>>=1;
}
//1、随机取一个b，2<=b<n-1
b=2 + g_Rnd.Random(n - 3);
//2、计算z=b^m mod n
z=PowMod(b, m, n);
//3、如果z==1，通过测试
if(z == 1)
{
return 1;
}
//4、令r=0
r=0;
//5、如果z=n-1，通过测试
while(z != n - 1)
{
//6、如果i==l，非素数，结束
if(r == (s-1))
{
return 0;
}
//7、z=z^2 mod n，i=i+1
z=PowMod(z,2,n);
++r;
//8、循环到5
}
}/*
Rabin-Miller素数测试，循环调用核心l …… 此处隐藏：5542字，全部文档内容请下载后查看。喜欢就下载吧 ……
实验4 非对称密码算法RSA.doc
将本文的Word文档下载到电脑
下一篇：二年级两位数加减两位数口算练习题
