📄 rsa.cpp
字号:
// RSA1.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
//#include <fstream.h>
#define MAX 200
#define GREAT 1
#define EQUAL 0
#define LOW -1
#define PL 8
typedef struct
{
int length;
unsigned int n[MAX];
} Lint;
Lint ZERO,ONE,TWO;
int Init_Lint(Lint *a, int n,unsigned int value)
{
int i;
if (a==NULL)
return (0);
else
{
a->length=0;
for (i=0;i<MAX;i++)
a->n[i]=0;
for (i=0;i<n;i++)
a->n[i]=value;
a->length=n;
return (1);
}
}
void Set_Lint(Lint* a,int n,unsigned int value)
{
if (a->length < n)
a->length =n;
a->n[n-1]=value;
}
int Cpy_Lint(Lint * a,Lint* b)
{
int i;
if (a==NULL||b==NULL) return 0;
if(b->length==0)
{Init_Lint(a,0,0);
return 1;
}
for(i=0;i<MAX;i++)
a->n[i]=b->n[i];
a->length=b->length;
return 1;
}
int Cpyblock_Lint(Lint * a,int p1, Lint* b,int p2, int n)
{
int i;
if ((a==NULL||b==NULL)||((p2+n-1)>(b->length))||((p1+n-1)>=MAX)) return 0;
for(i=p1;i<p1+n;i++)
a->n[i]=b->n[p2+i-p1];
return 1;
}
int Split_Lint(Lint * a,Lint* b,int n1,int n2)
{
int i;
if(n1<1||n2>b->length) return 0;
for (i=n1-1;i<n2;i++)
a->n[i-n1+1]=b->n[i];
a->length=n2-n1+1;
return 1;
}
int Cmp_Lint(Lint a,Lint b)
{
int i;
i=a.length;
while(1)
{
if ((a.n[i-1]==0 )&&(a.length>1))
a.length-=1;
else
break;
i--;
}
i=b.length;
while(1)
{ if ((b.n[i-1]==0 )&&(b.length>1))
b.length-=1;
else
break;
i--;
}
if (a.length > b.length )
return GREAT;
if (a.length < b.length )
return LOW;
i=a.length-1;
while(i>=0)
{
if(a.n[i]>b.n[i]) return GREAT;
if(a.n[i]<b.n[i]) return LOW;
i--;
}
if (i<0) return EQUAL;
}
void Lint_Add(Lint *a,Lint *b,Lint *c)
{
unsigned long temp=0;
int i=0,carry=0;
Init_Lint(c,0,0);
while((i<a->length)&&(i<b->length))
{
temp=a->n[i]+b->n[i]+carry;
c->n[i]=temp%65536;
carry=temp/65536;
i++;
c->length=i;
}
while (i<a->length)
{
temp=a->n[i]+carry;
c->n[i]=temp%65536;
carry=temp/65536;
i++;
c->length=i;
}
while (i<b->length)
{
temp=b->n[i]+carry;
c->n[i]=temp%65536;
carry=temp/65536;
i++;
c->length=i;
}
if(carry>0)
{
c->n[i]=carry;
c->length=i+1;
}
}
int Lint_Sub(Lint *a,Lint *b,Lint *c)
{
unsigned long temp=0;
int i=0,carry=1;
Init_Lint(c,0,0);
if (Cmp_Lint(*a,*b)==LOW)
return 0;
while(i<b->length)
{
if(carry==1)
temp=a->n[i]-b->n[i]+65536;
else
temp=a->n[i]-b->n[i]+65535;
c->n[i]=temp%65536;
carry=temp/65536;
i++;
c->length=i;
}
while (i<a->length)
{
if(carry==1)
temp=a->n[i]+65536;
else
temp=a->n[i]+65535;
c->n[i]=temp%65536;
carry=temp/65536;
i++;
c->length=i;
}
while(1)
{ if ((c->n[i-1]==0 )&&(c->length>1))
c->length-=1;
else
break;
i--;
}
return 1;
}
void Lint_Mul(Lint *l1,Lint *l2,Lint *c)
{
int i,j;
unsigned long temp1=0,temp2=0,carry=0,m,n;
Lint *a,*b,a1,b1;
Cpy_Lint(&a1,l1);
Cpy_Lint(&b1,l2);
Init_Lint(c,0,0);
if (Cmp_Lint(a1,b1)>0)
{
a=&b1;
b=&a1;
}
else
{
a=&a1;
b=&b1;
}
for(i=0;i<a->length;i++)
{
for(j=0,carry=0;j<b->length;j++)
{
temp1=a->n[i]*b->n[j]+c->n[i+j]+carry;
c->n[i+j]=temp1%65536;
carry=temp1/65536;
}
if(carry>0)
{
c->n[i+b->length]=carry;
}
}
c->length=a->length+b->length;
i=c->length;
while(1)
{ if ((c->n[i-1]==0 )&&(c->length>1))
c->length-=1;
else
break;
i--;
}
}
int Lint_Div(Lint *a,Lint *b,Lint *q,Lint* r)
{
Lint R1,R2,B1,B2,temp_Lint0,temp_Lint1,temp_Lint2,Q1,Q_Lint,SubB,SubR,d;
unsigned int i,j,n,Q,k;
int flag1,flag2;
unsigned long temp ;
Init_Lint(&d,0,0);
Init_Lint(&R1,0,0);
Init_Lint(&R2,0,0);
Init_Lint(&Q1,0,0);
Init_Lint(&B1,0,0);
Init_Lint(&B2,0,0);
Init_Lint(&temp_Lint0,0,0);
Init_Lint(&temp_Lint1,0,0);
Init_Lint(&temp_Lint2,0,0);
Init_Lint(&Q_Lint,0,0);
Init_Lint(&SubB,0,0);
Init_Lint(&SubR,0,0);
Init_Lint(q,0,0);
Init_Lint(r,0,0);
j=a->length-b->length;
Cpy_Lint(&R1,a);
Set_Lint(&R1,a->length+1,0);
Cpy_Lint(&B1,b);
Cpy_Lint(&B2,b);
Set_Lint(&d,1,1);
Set_Lint(&d,1,1);
i=R1.length-1;
n=B1.length;
flag1=Cmp_Lint(*b,ZERO);
if(a==NULL||b==NULL||flag1==0) return 0;
if(Cmp_Lint(B1,ZERO)==0) return 0;
if(Cmp_Lint(R1,B1)<0)
{
Cpy_Lint(q,&ZERO);
Cpy_Lint(r,a);
return 1;
}
if(Cmp_Lint(R1,B1)==0)
{
Cpy_Lint(q,&ONE);
Cpy_Lint(r,&ZERO);
return 1;
}
while (i>=n)
{
if(Cmp_Lint(R1,B1)<=0)
{
Q=0;
}
else
{
temp=(R1.n[i]*65536+R1.n[i-1])/B1.n[n-1];
temp=(temp<65535)?temp:65535;
if (n==1)
{
Split_Lint(&SubB,&B1,1,1);
Split_Lint(&SubR,&R1,i,i+1);
}
else
{
Split_Lint(&SubB,&B1,n-1,n);
Split_Lint(&SubR,&R1,i-1,i+1);
}
//Q++;
do
{
//Q--;
Set_Lint( &Q_Lint,1,temp);
Lint_Mul(&SubB,&Q_Lint,&temp_Lint1);
//Lint_Sub(&SubR,&temp_Lint1,&temp_Lint2);
flag1=Cmp_Lint(SubR,temp_Lint1);
Set_Lint( &Q_Lint,1,temp+1);
Lint_Mul(&SubB,&Q_Lint,&temp_Lint1);
// Lint_Sub(&SubR,&temp_Lint1,&temp_Lint2);
flag2=Cmp_Lint(SubR,temp_Lint1);
if(flag1==0) {Q=temp;break;}
if(flag2==0) {Q=temp+1;break;}
if(flag1<0&&flag2<0) temp--;
if(flag1>0&&flag2<0) {Q=temp;break;}
if(flag1>0&&flag2>0) temp++;
}
while(1);
Set_Lint( &Q_Lint,1,Q);
Split_Lint(&SubR,&R1,i-n+1,i+1);
Lint_Mul(&B1,&Q_Lint,&temp_Lint2);
// Lint_Sub(&SubR,&temp_Lint2,&temp_Lint0);
Lint_Sub(&SubR,&temp_Lint2,&temp_Lint0);
// Cpyblock_Lint(&R1,i-n,&temp_Lint0,1,n+1);
for(k=0;k<=n;k++)
R1.n[i-n+k]=temp_Lint0.n[k];
}
///////////////////////////////////////////////////
Set_Lint(&Q1,j+1,Q);
i--;
j--;
}
i=R1.length;
while(1)
{ if ((R1.n[i-1]==0 )&&(R1.length>1))
R1.length-=1;
else
break;
i--;
}
i=Q1.length;
while(1)
{ if ((Q1.n[i-1]==0 )&&(Q1.length>1))
Q1.length-=1;
else
break;
i--;
}
Cpy_Lint(r,&R1);
Cpy_Lint(q,&Q1);
return 1;
}
int Mod_Sub(Lint a, Lint b,Lint *c, Lint *m)
{
Lint temp0,temp1;
if (Cmp_Lint(a,b)>=0)
{
Lint_Sub(&a,&b,&temp0);
Lint_Div(&temp0,m,&a,c);
}
else
{
Lint_Sub(&b,&a,&temp0);
Lint_Div(&temp0,m,&a,&temp1);
if (Cmp_Lint(temp1,ZERO)>0)
Lint_Sub(m,&temp1,c);
else
Cpy_Lint(c,&ZERO);
}
return 1;
}
int Euclid1(long n,long a,long* v)
{
long u=1,g,v1=0,v3,q,t1=1,t3;
g=a;
v3=n;
if (v3==0) return 0;
while (v3>0)
{
q=g/v3;
t3=g%v3;
t1=(u-q*v1%n);
u=v1;
v1=t1;
g=v3;
v3=t3;
}
*v=u;
return 1;
}
int Euclid(Lint n,Lint a,Lint *v,Lint *gcd)
{
Lint u,g,v1,v3,q,t1,t3,temp1,temp2,temp3;
int i;
Cpy_Lint(&u,&ONE);
Cpy_Lint(&t1,&ONE);
Cpy_Lint(&v1,&ZERO);
Cpy_Lint(&g,&a);
Cpy_Lint(&v3,&n);
i=Cmp_Lint(v3,ZERO);
if (i==0) return 0;
while (i>0)
{
Lint_Div(&g,&v3,&q,&t3);
Lint_Mul(&q,&v1,&temp1);
Lint_Div(&temp1,&n,&temp3,&temp2);
Mod_Sub(u,temp2, &t1, &n);
Cpy_Lint(&u,&v1);
Cpy_Lint(&v1,&t1);
Cpy_Lint(&g,&v3);
Cpy_Lint(&v3,&t3);
i=Cmp_Lint(v3,ZERO);
}
Cpy_Lint(v,&u);
Cpy_Lint(gcd,&g);
return 1;
}
int Mexp_Lint(Lint a,Lint e,Lint* p,Lint m)
{
unsigned int r,bit[]={1,2,4,8,16,32,64,128,256,512,1024,
2048,4096,8192,16384,32768};
int i,n,s,t;
Lint temp0,temp1,temp2;
Init_Lint(&temp0,0,0);
Init_Lint(&temp1,0,0);
Init_Lint(&temp2,0,0);
if(Cmp_Lint(m,ZERO)==0) return 0;
if(Cmp_Lint(m,ONE)==0)
{
Cpy_Lint(p,&ZERO);
return 1;
}
else if (Cmp_Lint(a,ZERO)==0)
{
if(Cmp_Lint(e,ZERO)==0)
{Cpy_Lint(p,&ONE);
return 1;
}
if(Cmp_Lint(e,ZERO)>0)
{Cpy_Lint(p,&ZERO);
return 1;
}
}
n=e.length*16;
r=e.n[e.length-1]&bit[15];
if (r>0)
Cpy_Lint(p,&a);
else
Cpy_Lint(p,&ONE);
i=n-2;
while(i>=0)
{
Lint_Mul(p,p,&temp1);
Lint_Div(&temp1,&m,&temp0,p);
s=(i)/16;
t=(i)%16;
r=e.n[s]&bit[t];
if(r>0)
{
Lint_Mul(p,&a,&temp0);
Lint_Div(&temp0,&m,&temp1,p);
}
i--;
}
return 1;
}
int Rand_Lint(Lint *p , int n)
{
int i;
unsigned long a = 65539,b = 65539,seed1,seed0;
unsigned long temp;
unsigned long m = 65536;
seed1=rand();
seed0=rand();
for(i=0;i<n;i++)
{
temp= (a * seed1 + b * seed0 ) % m;
Set_Lint(p,i+1,(unsigned short)temp);
seed1 = rand();
seed0 = temp;
}
return 1;
}
int Isprime(Lint n)
{
int x[4]={2,3,4,5},i;
Lint temp0,temp1,temp2;
Init_Lint(&temp0,0,0);
Init_Lint(&temp1,0,0);
Init_Lint(&temp2,0,0);
for(i=0;i<4;i++)
{
Lint_Sub(&n,&ONE, &temp0);
Set_Lint(&temp2,1,x[i]);
Mexp_Lint( temp2,temp0, &temp1,n);
if(Cmp_Lint(temp1,ONE)!=0)
return 0;
}
return 1;
}
int genprime(Lint *p , int n)
{
int i,flage;
unsigned int primelist[64]={2
,3,5,7,11,13,17,19,23,29,31,37,41,43,
47,53,59,61,67,71,73,79,83,89,97,101,
103,107,109,113,127,131,137,139,149,151,
157,163,167,173,179,181,191,193,197,199,
211,223,227,229,233,239,241,251,257,263,
269,271,277,281,283,293,307,311};
Lint temp0,temp1,temp2,temp3;
Init_Lint(&temp0,0,0);
Init_Lint(&temp1,0,0);
Init_Lint(&temp2,0,0);
Init_Lint(&temp3,0,0);
Rand_Lint(&temp0 , n);
temp0.n[0]=temp0.n[0]|1;
i=0;
while(1)
{
do
{
flage =0;
for(i=0;i<64;i++)
{
Set_Lint(&temp1,1,primelist[i]);
Lint_Div(&temp0,&temp1,&temp2,&temp3);
if(Cmp_Lint(temp3,ZERO)==0)
{
flage=1;
break;
}
}
if(flage==1)
{
Lint_Add(&temp0,&TWO,&temp1);
Cpy_Lint(&temp0,&temp1);
}
}
while(flage==1);
if (Isprime(temp0)==1)
{
Cpy_Lint(p,&temp0);
return 1;
}
else
{
Lint_Add(&temp0,&TWO,&temp1);
Cpy_Lint(&temp0,&temp1);
}
}
}
int reset()
{
Init_Lint(&ZERO,1,0);
Init_Lint(&ONE,1,1);
Init_Lint(&TWO,1,2);
srand(time(NULL) );
return 1;
}
int Encrypt(Lint M,Lint e,Lint n,Lint *C)
{
Mexp_Lint(M,e,C,n);
return 1;
}
int Decrypt(Lint C,Lint d,Lint n,Lint *M)
{
Mexp_Lint(C,d,M,n);
return 1;
}
int genKey(Lint p,Lint q,Lint e,Lint *d,Lint *n)
{
Lint z,temp;
Init_Lint(&z,0,0);
Init_Lint(&temp,0,0);
Lint_Mul(&p,&q,n);
Lint_Sub(&p,&ONE,&temp);
Cpy_Lint(&p,&temp);
Lint_Sub(&q,&ONE,&temp);
Cpy_Lint(&q,&temp);
Lint_Mul(&p,&q,&z);
Euclid( z, e,d,&temp);
if (temp.n[0]!=1)
return 0;
return 1;
}
int _tmain(int argc, _TCHAR* argv[])
{
int i,j,k,fp1,fp2,fp3;
unsigned short num1[42]={30175,45566,1776,26384,23087,7624,28551,
30659,46466,9427,58089,53094,2259,16793,
13415,46155,6723,42095,29884,52304,26502,
44170,12295,52805,33766,5299,60285,1067,
45930,63331,18966,57389,58627,31623,34817,
32671,14731,57228,59797,65085,39474,54895},
num2[41]={16411,62909,61525,55893,16713,24008,39148,
14226,21974,56825,39555,33826,38231,17968,
20573,24545,33370,3478,34856,38695,50224,
24246,61805,65476,49626,19533,16354,50271,
34533,59318,26418,40454,3469,46800,58921,
59791,4907,25757,28309,19696,12074};
Lint C,M,temp,T,t1,t2,t3;
Lint e,z,d,p,q,n;
Init_Lint(&C,0,0);
Init_Lint(&M,0,0);
Init_Lint(&temp,0,0);
Init_Lint(&e,0,0);
Init_Lint(&z,0,0);
Init_Lint(&d,0,0);
Init_Lint(&p,0,0);
Init_Lint(&q,0,0);
Init_Lint(&n,0,0);
char str[400],select;
union
{
char ch[2*(PL-1)+1];
unsigned short l[PL-1];
} num,buffer;
char *filename1="M:\\wp1",*filename2="M:\\wp2",
*filename3="M:\\wp3";
reset();
if((fp1=open( filename1,0))==-1)
{
printf("不能打开文件\n");
return 0;
}
if((fp2=open( filename2,2))==-1)
{
printf("不能打开文件\n");
return 0;
}
if((fp3=open( filename3,2))==-1)
{
printf("不能打开文件\n");
return 0;
}
Set_Lint(&e,1,1);
Set_Lint(&e,2,1);
printf("\n****************************************************\n");
printf("** **\n");
printf("** 1.使用已经生成的密钥进行加解密 **\n");
printf("** 2.重新生成密钥进行加解密（需要很长时间） **\n");
printf("** 3.退出该程序 **\n");
printf("****************************************************\n");
printf("请选择（1、2或3）：");
while(1)
{
select=getch();
printf("%c",select);
if(select=='1')
{
for(i=0;i<42;i++)
Set_Lint(&p,i+1,num1[i]);
for(i=0;i<41;i++)
Set_Lint(&q,i+1,num2[i]);
goto ll;
}
else if (select=='2')
{
genprime(&p ,PL);
genprime(&q ,PL-1);
genprime(&e ,2);
goto ll;
}
else if (select=='3')
{
return 1;
}
else
{
printf("\n没有此项！重新选择。");
printf("请选择（1、2或3）：");
}
}
ll:
genKey(p,q,e,&d,&n);
while(1)
{
for(i=0;i<=2*PL-2;i++)
num.ch[i]='\0';
j=read(fp1,num.ch,2*(PL-1));
if(j==-1||j==0)
break;
k=0;
while(num.ch[k]!='\0')
k++;
for (j=k;j<2*(PL-1)+1;j++)
num.ch[j]='\0';
Init_Lint(&M,0,0);
for(i=0;i<(k+1)/2;i++)
Set_Lint(&M,i+1,num.l[i]);
Encrypt(M,e,n,&C);
Decrypt(C,d,n,&M);
for(i=0;i<M.length;i++)
buffer.l[i]=M.n[i];
buffer.ch[2*M.length]='\0';
write(fp2,buffer.ch,2*M.length);
printf("%s",buffer.ch);
}
return 1;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -