RSA加密解密算法C语言代码.docx
《RSA加密解密算法C语言代码.docx》由会员分享，可在线阅读，更多相关《RSA加密解密算法C语言代码.docx（46页珍藏版）》请在冰点文库上搜索。
RSA加密解密算法C语言代码
#include
#include
#include
#include
#include
#include
#defineMAX100
#defineLENsizeof（structslink）
voidsub（inta[MAX],intb[MAX],intc[MAX]）;
structslink
{
intbignum[MAX];
/*bignum[98]用来标记正负号，1正，0负bignum[99]来标记实际长度*/
structslink*next;
};
/*/--------------------------------------自己建立的大数运算库-------------------------------------*/
voidprint（inta[MAX]）
{
inti;
for（i=0;iprintf（"%d",a[a[99]-i-1]）;
printf（"\n\n"）;
return;
}
intcmp（inta1[MAX],inta2[MAX]）
{intl1,l2;
inti;
l1=a1[99];
l2=a2[99];
if（l1>l2）
return1;
if（l1return-1;
for（i=（l1-1）;i>=0;i--）
{
if（a1[i]>a2[i]）
return1;
if（a1[i]return-1;
}
return0;
}
voidmov（inta[MAX],int*b）
{
intj;
for（j=0;jb[j]=a[j];
return;
}
voidmul（inta1[MAX],inta2[MAX],int*c）
{
inti,j;
inty;
intx;
intz;
intw;
intl1,l2;
l1=a1[MAX-1];
l2=a2[MAX-1];
if（a1[MAX-2]=='-'&&a2[MAX-2]=='-'）
c[MAX-2]=0;
elseif（a1[MAX-2]=='-'）
c[MAX-2]='-';
elseif（a2[MAX-2]=='-'）
c[MAX-2]='-';
for（i=0;i{
for（j=0;j{
x=a1[i]*a2[j];
y=x/10;
z=x%10;
w=i+j;
c[w]=c[w]+z;
c[w+1]=c[w+1]+y+c[w]/10;
c[w]=c[w]%10;
}
}
w=l1+l2;
if（c[w-1]==0）w=w-1;
c[MAX-1]=w;
return;
}
voidadd（inta1[MAX],inta2[MAX],int*c）
{
inti,l1,l2;
intlen,temp[MAX];
intk=0;
l1=a1[MAX-1];
l2=a2[MAX-1];
if（（a1[MAX-2]=='-'）&&（a2[MAX-2]=='-'））
{
c[MAX-2]='-';
}
elseif（a1[MAX-2]=='-'）
{
mov（a1,temp）;
temp[MAX-2]=0;
sub（a2,temp,c）;
return;
}
elseif（a2[MAX-2]=='-'）
{
mov（a2,temp）;
temp[98]=0;
sub（a1,temp,c）;
return;
}
if（l1elselen=l2;
for（i=0;i{
c[i]=（a1[i]+a2[i]+k）%10;
k=（a1[i]+a2[i]+k）/10;
}
if（l1>len）
{
for（i=len;i{
c[i]=（a1[i]+k）%10;
k=（a1[i]+k）/10;
}
if（k!
=0）
{
c[l1]=k;
len=l1+1;
}
elselen=l1;
}
else
{
for（i=len;i{
c[i]=（a2[i]+k）%10;
k=（a2[i]+k）/10;
}
if（k!
=0）
{
c[l2]=k;
len=l2+1;
}
elselen=l2;
}
c[99]=len;
return;
}
voidsub（inta1[MAX],inta2[MAX],int*c）
{
inti,l1,l2;
intlen,t1[MAX],t2[MAX];
intk=0;
l1=a1[MAX-1];
l2=a2[MAX-1];
if（（a1[MAX-2]=='-'）&&（a2[MAX-2]=='-'））
{
mov（a1,t1）;
mov（a2,t2）;
t1[MAX-2]=0;
t2[MAX-2]=0;
sub（t2,t1,c）;
return;
}
elseif（a2[MAX-2]=='-'）
{
mov（a2,t2）;
t2[MAX-2]=0;
add（a1,t2,c）;
return;
}
elseif（a1[MAX-2]=='-'）
{
mov（a2,t2）;
t2[MAX-2]='-';
add（a1,t2,c）;
return;
}
if（cmp（a1,a2）==1）
{
len=l2;
for（i=0;i{
if（（a1[i]-k-a2[i]）<0）
{
c[i]=（a1[i]-a2[i]-k+10）%10;
k=1;
}
else
{
c[i]=（a1[i]-a2[i]-k）%10;
k=0;
}
}
for（i=len;i{
if（（a1[i]-k）<0）
{
c[i]=（a1[i]-k+10）%10;
k=1;
}
else
{
c[i]=（a1[i]-k）%10;
k=0;
}
}
if（c[l1-1]==0）/*使得数组C中的前面所以0字符不显示了，如1000-20=0980--->显示为980了*/
{
len=l1-1;
i=2;
while（c[l1-i]==0）/*111456-111450=00006，消除0后变成了6；*/
{
len=l1-i;
i++;
}
}
else
{
len=l1;
}
}
else
if（cmp（a1,a2）==（-1））
{
c[MAX-2]='-';
len=l1;
for（i=0;i{
if（（a2[i]-k-a1[i]）<0）
{
c[i]=（a2[i]-a1[i]-k+10）%10;
k=1;
}
else
{
c[i]=（a2[i]-a1[i]-k）%10;
k=0;
}
}
for（i=len;i{
if（（a2[i]-k）<0）
{
c[i]=（a2[i]-k+10）%10;
k=1;
}
else
{
c[i]=（a2[i]-k）%10;
k=0;
}
}
if（c[l2-1]==0）
{
len=l2-1;
i=2;
while（c[l1-i]==0）
{
len=l1-i;
i++;
}
}
elselen=l2;
}
elseif（cmp（a1,a2）==0）
{
len=1;
c[len-1]=0;
}
c[MAX-1]=len;
return;
}
voidmod（inta[MAX],intb[MAX],int*c）/*/c=amodb//注意：
经检验知道此处A和C的数组都改变了。
*/
{intd[MAX];
mov（a,d）;
while（cmp（d,b）!
=（-1））/*/c=a-b-b-b-b-b.......until（c{
sub（d,b,c）;
mov（c,d）;/*/c复制给a*/
}
return;
}
voiddivt（intt[MAX],intb[MAX],int*c,int*w）/*//试商法//调用以后w为amodb,C为adivb;*/
{
inta1,b1,i,j,m;/*w用于暂时保存数据*/
intd[MAX],e[MAX],f[MAX],g[MAX],a[MAX];
mov（t,a）;
for（i=0;ie[i]=0;
for（i=0;id[i]=0;
for（i=0;ia1=a[MAX-1];
b1=b[MAX-1];
if（cmp（a,b）==（-1））
{
c[0]=0;
c[MAX-1]=1;
mov（t,w）;
return;
}
elseif（cmp（a,b）==0）
{
c[0]=1;
c[MAX-1]=1;
w[0]=0;
w[MAX-1]=1;
return;
}
m=（a1-b1）;
for（i=m;i>=0;i--）/*341245/3=341245-300000*1--->41245-30000*1--->11245-3000*3--->2245-300*7--->145-30*4=25--->25-3*8=1*/
{
for（j=0;jd[j]=0;
d[i]=1;
d[MAX-1]=i+1;
mov（b,g）;
mul（g,d,e）;
while（cmp（a,e）!
=（-1））
{
c[i]++;
sub（a,e,f）;
mov（f,a）;/*f复制给g*/
}
for（j=i;je[j]=0;
}
mov（a,w）;
if（c[m]==0）c[MAX-1]=m;
elsec[MAX-1]=m+1;
return;
}
voidmulmod（inta[MAX],intb[MAX],intn[MAX],int*m）/*解决了m=a*bmodn;*/
{
intc[MAX],d[MAX];
inti;
for（i=0;id[i]=c[i]=0;
mul（a,b,c）;
divt（c,n,d,m）;
for（i=0;iprintf（"%d",m[m[MAX-1]-i-1]）;
printf（"\nmlengthis:
%d\n",m[MAX-1]）;
}
/*接下来的重点任务是要着手解决m=a^pmodn的函数问题。
*/
voidexpmod（inta[MAX],intp[MAX],intn[MAX],int*m）
{
intt[MAX],l[MAX],temp[MAX];/*/t放入2，l放入1；*/
intw[MAX],s[MAX],c[MAX],b[MAX],i;
for（i=0;ib[i]=l[i]=t[i]=w[i]=0;
t[0]=2;t[MAX-1]=1;
l[0]=1;l[MAX-1]=1;
mov（l,temp）;
mov（a,m）;
mov（p,b）;
while（cmp（b,l）!
=0）
{
for（i=0;iw[i]=c[i]=0;
divt（b,t,w,c）;/*//c=pmod2w=p/2*/
mov（w,b）;/*//p=p/2*/
if（cmp（c,l）==0）/*/余数c==1*/
{
for（i=0;iw[i]=0;
mul（temp,m,w）;
mov（w,temp）;
for（i=0;iw[i]=c[i]=0;
divt（temp,n,w,c）;/*/c为余c=temp%n，w为商w=temp/n*/
mov（c,temp）;
}
for（i=0;is[i]=0;
mul（m,m,s）;//s=a*a
for（i=0;ic[i]=0;
divt（s,n,w,c）;/*/w=s/n;c=smodn*/
mov（c,m）;
}
for（i=0;is[i]=0;
mul（m,temp,s）;
for（i=0;ic[i]=0;
divt（s,n,w,c）;
mov（c,m）;/*余数s给m*/
m[MAX-2]=a[MAX-2];/*为后面的汉字显示需要，用第99位做为标记*/
return;
/*/k=temp*k%n;*/
}
intis_prime_san（intp[MAX]）
{
inti,a[MAX],t[MAX],s[MAX],o[MAX];
for（i=0;is[i]=o[i]=a[i]=t[i]=0;
t[0]=1;
t[MAX-1]=1;
a[0]=2;//{2,3,5,7}
a[MAX-1]=1;
sub（p,t,s）;
expmod（a,s,p,o）;
if（cmp（o,t）!
=0）
{
return0;
}
a[0]=3;
for（i=0;iexpmod（a,s,p,o）;
if（cmp（o,t）!
=0）
{
return0;
}
a[0]=5;
for（i=0;iexpmod（a,s,p,o）;
if（cmp（o,t）!
=0）
{
return0;
}
a[0]=7;
for（i=0;iexpmod（a,s,p,o）;
if（cmp（o,t）!
=0）
{
return0;
}
return1;
}
intcoprime（inte[MAX],ints[MAX]）/*////求两个大数之间是否互质////*/
{
inta[MAX],b[MAX],c[MAX],d[MAX],o[MAX],l[MAX];
inti;
for（i=0;il[i]=o[i]=c[i]=d[i]=0;
o[0]=0;o[MAX-1]=1;
l[0]=1;l[MAX-1]=1;
mov（e,b）;
mov（s,a）;
do
{
if（cmp（b,l）==0）
{
return1;
}
for（i=0;ic[i]=0;
divt（a,b,d,c）;
mov（b,a）;/*b--->a*/
mov（c,b）;/*c--->b*/
}while（cmp（c,o）!
=0）;
/*printf（"Iheyarenotcoprime!
\n"）;*/
return0;
}
voidprime_random（int*p,int*q）
{
inti,k;
time_tt;
p[0]=1;
q[0]=3;
//p[19]=1;
//q[18]=2;
p[MAX-1]=10;
q[MAX-1]=11;
do
{
t=time（NULL）;
srand（（unsignedlong）t）;
for（i=1;i{
k=rand（）%10;
p[i]=k;
}
k=rand（）%10;
while（k==0）
{
k=rand（）%10;
}
p[p[MAX-1]-1]=k;
}while（（is_prime_san（p））!
=1）;
printf（"素数p为:
"）;
for（i=0;i{
printf（"%d",p[p[MAX-1]-i-1]）;
}
printf（"\n\n"）;
do
{
t=time（NULL）;
srand（（unsignedlong）t）;
for（i=1;i{
k=rand（）%10;
q[i]=k;
}
}while（（is_prime_san（q））!
=1）;
printf（"素数q为:
"）;
for（i=0;i{
printf（"%d",q[q[MAX-1]-i-1]）;
}
printf（"\n\n"）;
return;
}
voiderand（inte[MAX],intm[MAX]）
{
inti,k;
time_tt;
e[MAX-1]=5;
printf（"随机产生一个与（p-1）*（q-1）互素的e:
"）;
do
{
t=time（NULL）;
srand（（unsignedlong）t）;
for（i=0;i{
k=rand（）%10;
e[i]=k;
}
while（（k=rand（）%10）==0）
k=rand（）%10;
e[e[MAX-1]-1]=k;
}while（coprime（e,m）!
=1）;
for（i=0;i{
printf（"%d",e[e[MAX-1]-i-1]）;
}
printf（"\n\n"）;
return;
}
voidrsad（inte[MAX],intg[MAX],int*d）
{
intr[MAX],n1[MAX],n2[MAX],k[MAX],w[MAX];
inti,t[MAX],b1[MAX],b2[MAX],temp[MAX];
mov（g,n1）;
mov（e,n2）;
for（i=0;ik[i]=w[i]=r[i]=temp[i]=b1[i]=b2[i]=t[i]=0;
b1[MAX-1]=0;b1[0]=0;/*/b1=0;*/
b2[MAX-1]=1;b2[0]=1;/*/b2=1;*/
while
（1）
{
for（i=0;ik[i]=w[i]=0;
divt（n1,n2,k,w）;/*/k=n1/n2;*/
for（i=0;itemp[i]=0;
mul（k,n2,temp）;/*/temp=k*n2;*/
for（i=0;ir[i]=0;
sub（n1,temp,r）;
if（（r[MAX-1]==1）&&（r[0]==0））/*/r=0*/
{
break;
}
else
{
mov（n2,n1）;/*/n1=n2;*/
mov（r,n2）;/*/n2=r;*/
mov（b2,t）;/*/t=b2;*/
for（i=0;itemp[i]=0;
mul（k,b2,temp）;/*/b2=b1-k*b2;*/
for（i=0;ib2[i]=0;
sub（b1,temp,b2）;
mov（t,b1）;
}
}
for（i=0;it[i]=0;
add（b2,g,t）;
for（i=0;itemp[i]=d[i]=0;
divt（t,g,temp,d）;
printf（"由以上的（p-1）*（q-1）和e计算得出的d:
"）;
for（i=0;iprintf（"%d",d[d[MAX-1]-i-1]）;
printf（"\n\n"）;
}
unsignedlongrsa（unsignedlongp,unsignedlongq,unsignedlonge）/*/求解密密钥d的函数（根据Euclid算法）*/
{
unsignedlongg,k,r,n1,n2,t;
unsignedlongb1=0,b2=1;
g=（p-1）*（q-1）;
n1=g;
n2=e;
while
（1）
{
k=n1/n2;
r=n1-k*n2;
if（r!
=0）
{
n1=n2;
n2=r;
t=b2;
b2=b1-k*b2;
b1=t;
}
else
{
break;
}
}
return（g+b2）%g;
}
/*/------------------------------------------导入导出公钥和私钥------------------------------------/*/
voidloadpkey（inte[MAX],intn[MAX]）//导入公钥
{
FILE*fp;
charfilename[25],str[MAX],ch;
inti,k;
for（i=0;ie[i]=n[i]=0;
while
（1）
{
printf（"\n"）;
printf（"为导入（e,n），请输入加密密钥对文件路径:
\n"）;
scanf（"%s"
升级会员 