rsa.c

完成RSA算法的加密解密

#include<stdlib.h> 
#include<time.h> 
#include<stdio.h>
#include <math.h>
#define VLONG    unsigned long
#define TRUE 1   
#define FALSE 0





//模幂算法，素数的米勒-勒宾(MIller-Rabin)概率测试法，p151
//输入:被 b要检测的数字,n素数产生的范围满足:(2<=b<n-1)
int TestPrimeNum(VLONG b,VLONG n)
{
	VLONG m=1;
	VLONG l=0;
	VLONG V;
	VLONG i;
	while (m<(n-1))
	{m=m*2;l++;}
	if ((b<2)||(b>=(n-1))) return (FALSE);
	V=MONmod(b,m,n);
	if (V==1) return (TRUE);
	i=1;
	do
	{
		if (V==(n-1)) return (TRUE);
		if (i==l) return (FALSE);
		V=MONmod(V,2,n);
		i++;
	}
	while (1);
	return(FALSE);
}

//VLONG  Random(VLONG x,VLONG y) 
//{ 
//VLONG i,range,n1,a[2]; 
//VLONG min,max,flag=0; 
//VLONG t; 
//VLONG j; 
//min=x; 
//max=y; 
//range=max-min; 
//srand((VLONG)time(&t)); /* 首先给srand()提供一个种子，它是一个unsigned VLONG类型；*/ 
//for(i=0;i<2;)
//{n1=rand(); 
//j=((VLONG)n1/(VLONG)RAND_MAX); /*把随机数除以RAND_MAX，从而产生一个在0到1之间的校正值；*/ 

//n1=(VLONG)(j*(VLONG)range); /*把校正值乘以所需要的范围值(即500-50)从而产生一个在0到43之间的值*/ 
//n1+=min; /*把该值和所要求的最小值相加，从而使该值最终落在正确的取值范围----1到44之间。*/ 
//if(TestPrimeNum((VLONG) n1,(VLONG) max)==1)
//{a[i]=n1;i++;}
//else continue;
//} 
//p=a[0];q=a[1];
//}
//模幂算法，快速计算：x^r(mod p)，p76
VLONG MONmod(VLONG x,VLONG r,VLONG p)
{
	VLONG a,b,c;
	a=x;
	b=r;
	c=1;
	while (b!=0)
	{
		if ((b&0x01)==0)
		{
			b=b/2;
			a=(a*a)%p;
		}
		else
		{
			b=b-1;
			c=(a*c)%p;
		}
	}
	return c;
}



//参考书：《计算机密码学》（第二版）卢开澄 清华大学出版社
//求u mod m的逆元素算法，快速计算：gcd{u,m}=au+bm=1，p136(替换getD)
VLONG Reciprocal_u(VLONG /*mod*/ m,VLONG u)
{
	VLONG n1=m;
	VLONG n2=u;
	VLONG b1=0;
	VLONG b2=1;
	VLONG t;
	VLONG q;
	VLONG r;
	do
	{
		q=n1/n2;
		r=n1-q*n2;
		if (r==0) break;
		n1=n2;
		n2=r;
		t=b2;
		b2=b1-q*b2;
		b1=t;
	}
	while (1);

	if (n2!=1)
		return (0);   //不存在
	if (b2<0)
		return (b2+m);
	else
		return (b2);
}
//解密

VLONG decrypt(VLONG c,VLONG n, VLONG d1)
{
	VLONG i,g,f;
	if (d1%2==0) g=1; else g=c;
	for (i=1;i<=d1/2;i++)
	{
		f=c*c % n;
		g=f*g % n;
	}
	return(g);
}


VLONG main()
{ VLONG a,b,n,e,PHI,m,k[100],j,m1,i,str1[100],str2[100],str3[100],m2,m3,p,q,m4,m5;
  char str[100],str4[100],c;
  VLONG str5[100];
  VLONG d=65537;
  //printf("请输入p，q的范围的最小值a和最大值b\n");
  //scanf("a=%ldb=%ld",&a,&b);
  //a=1000;b=10000;
  //Random(a,b);
  p=2357;q=2551;
  printf("p=%ld\nq=%ld\n",p,q);
  n=p*q;
  PHI=(p-1)*(q-1);
  e=Reciprocal_u(PHI,d);
  printf("n=%ld\nPHI=%ld\ne=%ld\n",n,PHI,e);
  printf("请输入要加密的明文，请用小写字母组成，中间请勿留空格\n");
  gets(str);
  puts(str);
  for(i=0;(c=str[i])!='\0';i++)
	 {if(str[i]>='a' && str[i]<='z')
  {str[i]=str[i]-86;m=i;
  printf("%ld\n",str[i]);}}
  if(m%2==0) str[++m]=10;
  printf("m=%ld\n",m);
  for(i=0,j=0;i<m;i=i+2,j++)
  {str1[j]=str[i]*100+str[i+1];
  printf("%ld\n",str1[j]);}
  m1=j;
  for(i=0;i<m1;i++)
{str2[i]=MONmod(str1[i],d,n);
  printf("%ld\n",str2[i]);}
  printf("%\n");
  m2=MONmod(500,65537,n);
  m3=MONmod(111,13,2537);
  m4=MONmod(1520,13,2537);
  m5=MONmod(m4,937,2537);
  printf("m2=%ld\nm3=%ld\nm4=%ld\nm5=%ld\n",m2,m3,m4,m5);
   printf("%\n");
for(i=0;i<m1;i++)
{str3[i]=decrypt(str2[i],n,e);
  printf("%ld\n",str3[i]);}
  /*for(i=0;i<5;i++)
  printf("%ld",str1[i]);
  for(i=0;i<m1;i++)
  {str2[i]=MONmod(str1[i],d,n);}
  for(i=0,j=0;i<m1;i++,j=j+2)
  {str4[j]=(VLONG)str2[i]/100;str4[j+1]=str2[i]-str4[j]*100;}
  for(i=0;i<m;i++)
  printf("%ld",str4[i]);
  }*/

  
}