text2.c

des和rsa加密解密算法的程序源代码

/*
RSA算法模拟。
1）选取两个大素数p，q
2）求出n=p*q，以及f(n)=(p-1)*(q-1)
3）随机选取整数d，使得d与f(n)互素
4）选取整数e，使得(e*d)%f(n)==1
5）公钥为n和e，私钥为n和d
加密算法：c=me mod n
解密算法：m=cd mod n
*/

#include <math.h>

#define TRUE 1
#define FALSE 0
#define vlong unsigned long 
int IsPrime(vlong n)
{
  vlong i;
  for(i=2;i<n;i++)
    if(n%i==0)
      break;
  if(i<n)
    return 0;
  else
    return 1;
}

long NextPrime(vlong n)
{
  while(IsPrime(n)==0)
    n++;
  return n;
}

vlong gcd(vlong m,vlong n)//求两数最大公约数
{
  vlong r;
  while((r=m%n)!=0)
  {
     m=n;
     n=r;
  }
  return n;
}

vlong husu(vlong n)
{
   vlong i=n-1;
   while(gcd(n,i)!=1)
     i++;
   return i;
}

vlong modone(vlong m,vlong n)//求m mod n的值
{
  vlong i=n;
  while((i*m)%n!=1)
    i++;
  return i;
}

vlong getE( vlong PHI)
{
	vlong great=0, e=2;
	while (great!=1)
	{
		e=e+1;
		great = gcd(e,PHI);
	}
	return(e);
}

vlong rsa(vlong m,vlong e,vlong n)//c=m^e mod n
{
  vlong t=1;
  vlong i;
  for(i=1;i<=e;i++)
  {
      t*=m;
      t=t%n;
  }
  return t%n;
}

void get_prime(vlong *val)
{
	#define NO_PRIMES 39
	vlong primes[NO_PRIMES]={3,5,7,11,13,
		                     17,19,23,29,31,
							 37,41,43,53,59,
							 61,67,71,101,103,97,
							 107,109,113,127,131,
							 137,139,149,151,157,
							 163,167,173,179,181,
							 191,193,197};
	vlong prime,i;
	
	do
	{
		prime=FALSE;
		printf("Enter a prime number >> ");
		scanf("%ld",val);
		for (i=0;i<NO_PRIMES;i++)
			if (*val==primes[i]) 
				prime=TRUE;
	} 
	while (prime==FALSE);
}

void main()
{
  vlong m,c,p,q,d,e,n,t,PHI;
  get_prime(&p);
  get_prime(&q);
  n=p*q;
  PHI=(p-1)*(q-1);
  e=getE(PHI);
  d=modone(e,(p-1)*(q-1));
  printf("The opened key is:%ld&%ld\n",n,e);
  printf("The private key is:%ld&%ld\n",n,d);
  printf("Enter input value >> "); 
  scanf("%ld",&m);
  c=rsa(m,e,n);
  printf("The encrypted number is:\n%ld",c);
  t=rsa(c,d,n);
  printf("\nThe restored number is:\n%ld",t);
  if(t==m)
    printf("\nOK,RIGHT!\n");
  else
    printf("\nERROR!!!");
 }