R
RRRRS
SSSSA
AAAA算法的
C
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<stdio.h>
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)
//公钥
e与
t的互素判断
{
int
t;
while(y)
{
t=x;
x=y;
y=t%y;
}
if(x
==
1)
return
0;
//x与
y互素时返回
0
else
return
1;
//x与
y不互素时返回
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);
//求
n的欧拉数
printf("计算得
t为
%3d\n",t);
printf("请输入公钥
e:
");
scanf("%d",&e);
if(e<1||e>t||fun(e,t))
{
printf("e不合要求，请重新输入
:
");
//e<1或
e>t或
e与
t不互素时，重新输入
scanf("%d",&e);
}
d=1;
while(((e*d)%t)!=1)
d++;
//由公钥
e求出私钥
d
printf("经计算
d为
%d\n",d);
printf("加密请输入
1\n");
//加密或解密选择
printf("解密请输入
2\n");
scanf("%d",&r);
switch(r)
{
case1:
printf("请输入明文
m:
");
//输入要加密的明文数字
scanf("%d",&m);
c=candp(m,e,n);
printf("密文为
%d\n",c);break;
case2:
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算法的入门，无
法实现达到安全要求的数据位数。
评论0