RSARSARSARSA 算法的 CCCC 语言实现
一、RSA 算法的描述
1、选取长度相等的两个大素数 p 和 q,计算其乘积:
n = pq
然后随机选取加密密钥 e,使 e 和(p–1)(q–1)互素。
最后用欧几里德扩展算法计算解密密钥 d,以满足
ed = 1(mod(p–1) ( q–1))
d = e–1 mod((p–1)(q–1))
即
e 和 n 是公钥,d 是私钥
2、加密公式如下:
ci = mi^e(mod n)
3、解密时,取每一密文分组 ci 并计算:
mi = ci^d(mod n)
Ci^d =(mi^e)^d = mi^(ed) = mi^[k(p–1)(q–1)+1 ]
= mi mi^[k(p–1)(q–1)] = mi *1 = mi
4、消息也可以用 d 加密用 e 解密
二、C 源程序
//RSA 算法的 C 程序实现
#include
int candp(int a,int b,int c)
{ int r=1;
b=b+1;
while(b!=1)
{
r=r*a;
r=r%c;
b--;
}
printf("%d\n",r);
return r;
}
int fun(int x,int y)
{
int t;
while(y)
{
t=x;
//数据处理函数,实现幂的取余运算
//公钥 e 与 t 的互素判断
x=y;
y=t%y;
}
if(x == 1)
return 0;
else
return 1;
}
void main()
{
int p,q,e,d,m,n,t,c,r;
printf("请输入两个素数 p,q: ");
scanf("%d%d",&p,&q);
n=p*q;
printf("计算得 n 为 %3d\n",n);
t=(p-1)*(q-1);
printf("计算得 t 为 %3d\n",t);
printf("请输入公钥 e: ");
scanf("%d",&e);
if(e<1||e>t||fun(e,t))
{
//x 与 y 互素时返回 0
//x 与 y 不互素时返回 1
//求 n 的欧拉数
printf("e 不合要求,请重新输入: ");
scanf("%d",&e);
//e<1 或 e>t 或 e 与 t 不互素时,重新输入
d++;
}
d=1;
while(((e*d)%t)!=1)
printf("经计算 d 为 %d\n",d);
printf("加密请输入 1\n");
printf("解密请输入 2\n");
scanf("%d",&r);
switch(r)
{
//由公钥 e 求出私钥 d
//加密或解密选择
case 1: printf("请输入明文 m: ");
//输入要加密的明文数字
scanf("%d",&m);
c=candp(m,e,n);
printf("密文为 %d\n",c);break;
case 2: printf("请输入密文 c: ");
//输入要解密的密文数字
scanf("%d",&c);
m=candp(c,d,n);
printf("明文为 %d\n",m);break;
}
}
三、程序运行结果及相关说明
主函数实现求 N 的欧拉数、由公钥求解私钥、加密解密选择以及相应的密文明文输出。
子函数 candp 实现加密解密时的求幂取余运算,fun 实现 e 与 t 的互素判断,已验证 e 是否
符合要求。程序主体参考了网上的相关 RSA 算法程序,我对其中 e 的合法性判断、主函数
实现的顺序以及相关提示信息做了补充与修改并加上了注释,这样程序可读性更强,运行时
更容易操作,思路也更加严密。
当 P=43, q=59 时,对 134 进行加密,运行结果如下:
第一次取 e 为 15,与 t 不互素,提示需重新输入,输入 13 后,便可以进行正确操作。
由于 int 型变量为十六位,因此 n 最大只能小于 65536,此程序只是对 RSA 算法的入门,无
法实现达到安全要求的数据位数。