/*
首先来解释一下RSA算法的实现过程
1.生成密钥
(1)选择p、q,要求p、q均为素数且互素,计算他们的乘积n作为作为加密和解密时的模
(2)计算n的欧拉函数值&n,&n表示小于n且与n互素的正整数的个数(&n=(p-1)*(q-1))
(3)选择e,e为与&n互素的整数且e小于&n
(4)计算d,ed mod &n = 1
(5)得到公钥KU={e,n}
(6)得到私钥KR={d,n}
2.加密时,密文块C=M^e(mod n)
3.解密时,明文块M=C^d(mod n)
然后本次实验的相关要求;
(1)对大整数进行操作
(2)加密文件而非字符串
(3)明文大于1000时可操作
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define N 100000
/*
*该函数筛选出1000~100000内的素数并存储在数组num内
*传入参数为整形数组,存储筛选出的素数
*返回值为筛选出的素数个数
*/
int prime_num(int num[N])
{
int len=0;
int j,k,flag;
for(j=10001;j<=99999;j+=2)
{
flag = 0;
for(k=2;k<=(sqrt(j));k++)
{
if(j % k == 0)
{
flag = 1;
break;
}
else
continue;
}
if(flag == 0)
num[len++]=j;
else
continue;
}
return len;
}
/*
*该函数随机在num数组内选取一个素数并返回
*传入参数为筛选出的素数数组及数组长度
*/
int random_num(int num[N],int len)
{
int x;
x = rand()%len;
return num[x];
}
/*
*该函数为扩展欧几里得算法,传入四个参数分别对应:
*数a,模b及两个临时变量
*返回值为a的模反元素即在模f下a的乘法逆元
*/
long long int gcd(long long int a,long long int b,long long int* x,long long int* y){
if (b==0){
*x=1;
*y=0;
return a;
}
long long int q = gcd(b,a%b,x,y);
long long int t = *x;
*x = *y;
*y = t - (a/b)* *y;
return q;
}
/*
*该函数实现快速幂取模算法,主要用于加密和解密的实现
*三个参数分别为底数、幂、模值
*返回值为幂取模的结果
*/
long long int Mod(long long int a,long long int b,long long int n)
{
long long int res=1;
while(b>0)
{
if(b&1)
res=res*a%n;
b=b>>1;
a=a*a%n;
}
return res;
}
int main()
{
long long int p,q,e;
long long int f,n;
long long int i=0,j=0;
int k;
char code[26] = "abcdefghijklmnopqrstuvwxyz";
long long int code_en[26];
//需要查看样例定值测试输出结果时,删去下方注释符号即可
/*
p = 54013;
q = 47129;
f =(p-1)*(q-1);
n =p*q;
e = 11743;
*/
//需要查看样例定值测试输出结果时,从这里开始注释
int len;
int num[N];
srand(time(0));
len = prime_num(num);
p = random_num(num,len);
do{
q = random_num(num,len);
}while(p == q);
f =(p-1)*(q-1);
n =p*q;
do{
e = random_num(num,len);
}while(p == e || q == e || e >= f);
//需要查看样例定值测试输出结果时,到这里结束注释
gcd(e,f,&i,&j);
if (i < 0) i+=f;
printf("p=%lld\nq=%lld\nf=(p-1)(q-1)=%lld\n",p,q,f);
printf("n=p*q=%lld\ne=%lld\nd=%lld\n",n,e,i);
printf("Source:\n");
for(k=0;k<=25;k++)
{
printf("%c",code[k]);
}
printf("\nEncode:\n");
for(k=0;k<=25;k++)
{
printf("%x ",Mod(code[k],e,n));
code_en[k]=Mod(code[k],e,n);
}
printf("\nDecode:\n");
for(k=0;k<=25;k++)
{
printf("%x ",Mod(code_en[k],i,n));
}
printf("\n\nDecryption:\n");
for(k=0;k<=25;k++)
{
printf("%c",(char)Mod(code_en[k],i,n));
}
return 0;
}