密码学实验4
- 格式：doc
- 大小：94.03 KB
- 文档页数：11
实验4 非对称密码算法RSA
一、 实验目的
二、 通过实际编程了解非对称密码算法RSA的加密和解密过程, 加深对非对称密码算法的认识。
三、 实验原理
1、算法原理
步骤如下（这里设B为是实现者）
（1）B寻找出两个大素数p和q。
（2）B计算出n=p*q和（n）=）（p-1）*（q-1）。
（3）B选择一个随机数e（0
（4）B使用欧几里得算法计算e的模余（n）的乘法逆元素d。
B在目录中公开n和e作为他的公开密钥, 保密p、q和d。
加密时, 对每一明文m计算密文
cΞme（modn）
解密时, 对每一密文c计算明文
mΞcd（modn）
四、 实验环境
五、 运行Windows或者Linux操作系统的PC机, 具有gcc（Linux）、VC（Windows）等C语言编译环境。
六、 实验内容
1.为了加深对 算法的了解, 根据输入的参数p, q, M, 手工计算公私钥, 并对明文进行加密, 然后对密文进行解密。
2.编写 程序, 加密一段文字, 了解 算法原理。尝试加密一大段文字, 记录程序的运行时间。使用DES算法加密相同的文字, 比较两种算法加密的速度。
3.编写一个程序, 随机选择3个 较大的数 , 计算 , 记录 程序运行时间。
查阅资料给出简单说明大数在计算机上是如何表示, 如何进行运算。 4、查阅资料, 找出目前实际可行的素数判定法则, 并比较各自的优缺点。
五、实验步骤
1.主要函数说明
（1）判断一个数是否为素数函数
bool prime(int n)
{
int m=sqrt(n);
for(int i=2;i
{
if(n%i==0)
break;
}
if(i>=m)
return 1;
else return 0;
}
（2）模幂算法 (这里以明文m为一个为例)
①令f=1；
②用for循环遍历从i=1到i=b, 令f=(f*a)%n
③输出f, f的值即为模幂的结果。
int multiplication(int a,int b,int n)
{
int f=1;
for(int i=1;i<=b;i++)
{
f=(f*a)%n;
}
return f;
}
（3）扩展欧几里得算法
由扩展欧几里得算法可以计算整数s和t , 使得s*e+t*N=（e,N）=1,则e的乘法逆元等价于s
mod N。
①定义变量 x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
②令 x1 = y2 = 1; x2 = y1 = 0;
③计算q = x3/y3; t1 = x1 - q*y1;
t2 = x2 - q*y2; t3 = x3 - q*y3; ④ x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3;
⑤当 y3 =1时, *result = y2; result 的结果即为所求乘法逆元；如果y3 ！ =1, 则返回顺序执行③、④步直到满足 y3 =1
int ExtendedEuclid( int f,int d ,int *result)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
x1 = y2 = 1;
x2 = y1 = 0;
if(f>=d)
{
x3=f;
y3=d;
}
else
{
x3=d;
y3=f;
}
while( 1 )
{
if ( y3 == 1 )
{
*result = y2; /* 两个数互素则resutl为其乘法逆元, 此时返回值为1 */
return 1;
}
q = x3/y3;
t1 = x1 - q*y1;
t2 = x2 - q*y2;
t3 = x3 - q*y3;
x1 = y1;
x2 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
}
（4）主函数
①输入两个数字判断是否为素数, 当不为素数时重新输入。如输入 17 11
②输入e, 得到公钥。如输入e为7
③调用ExtendedEuclid(e,N,&d)函数, 得到d, 和私钥。如d=23 ④输入明文长度。如输入 5 如输入明文为 56 88 78 12 23
⑤开始加密, 调用加密函数 Encryption()。 则输入密文为 78 11 56 177 133
⑥开始解密, 调用解密函数 Decipher()。 则解密后明文为 56 88 78 12 23
2、打开VC++, 编写程序如下：
#include
#include
int p,q,n,e,d,N,m1[100],m2[100],len;
//判断一个数是否为素数, 为素数返回1, 否则返回0
bool prime(int n)
{
int m=sqrt(n);
for(int i=2;i
{
if(n%i==0)
break;
}
if(i>=m)
return 1;
else return 0;
}
//扩展欧几里得算法求乘法逆元,两数互素返回1
int ExtendedEuclid( int f,int d ,int *result)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;
x1 = y2 = 1;
x2 = y1 = 0;
if(f>=d)
{
x3=f;
y3=d;
}
else
{
x3=d;
y3=f;
}
while( 1 )
{
if ( y3 == 1 )
{
*result = y2; /* 两个数互素则resutl为其乘法逆元, 此时返回值为1 */ return 1;
}
q = x3/y3;
t1 = x1 - q*y1;
t2 = x2 - q*y2;
t3 = x3 - q*y3;
x1 = y1;
x2 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
}
//将十进制数据转化为二进制数组
void to_bit(int b,int bit[32])
{
int n=0;
while(b>0)
{
bit[n]=b%2;
n++;
b/=2;
}
}
//模幂算法
int multiplication(int a,int b,int n)
{
int f=1;
for(int i=1;i<=b;i++)
{
f=(f*a)%n;
}
return f;
}
//加密函数
void Encryption()
{ cout<<"******************开始加密*****************"<
int i;
cout<<"请输入明文: ";
for(i=0;i
cin>>m1[i];
for(i=0;i
m2[i]=multiplication(m1[i],e,n);
cout<<"加密后的密文为: ";
for(i=0;i
cout<
cout<
}
//解密函数
void Decipher()
{
int i;
cout<<"*************开始解密*************"<
for(i=0;i
m2[i]=multiplication(m2[i],d,n);
cout<<"解密后的明文为: ";
for(i=0;i
cout<
cout<
}
void main()
{
cout<<"输入两个素数p和q:\n";
while(1)
{
cin>>p;
if(prime(p))
{
cout<
break;
}
else
{
cout<
continue;
}
}
