rsa密码体制之c语言模拟.txt

c语言的一些常见的算法以及思考和改进的文章,写的很不错,花费了很大的精力从网络了搜罗的,希望大家喜欢.

RSA密码体制之C语言模拟[原创] 
/*
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
*/

＃i nclude <math.h>

int IsPrime(long n)
{
  long i;
  for(i=2;i<n;i++)
    if(n%i==0)
      break;
  if(i<n)
    return 0;
  else
    return 1;
}

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

long gcd(long m,long n)
{
  long r;
  while((r=m%n)!=0)
  {
     m=n;
     n=r;
  }
  return n;
}

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

long modone(long m,long n)
{
  long i=n;
  while((i*m)%n!=1)
    i++;
  return i;
}

void rsacreate(long p,long q,long *n,long *e,long *d)
{
  *n=p*q;
  *d=husu((p-1)*(q-1));
  *e=modone(*d,(p-1)*(q-1));
}

long rsa(long m,long e,long n)
{
  long t=1;
  long i;
  for(i=1;i<=e;i++)
  {
      t*=m;
      t=t%n;
  }
  return t%n;
}

void main()
{
  long m,c,p,q,d,e,n,t;
  p=NextPrime(30);
  q=NextPrime(40);
  rsacreate(p,q,&n,&e,&d);
  clrscr();
  printf("\np=%ld,q=%ld\n",p,q);
  printf("\nThe opened key is:%ld&%ld\n",n,e);
  printf("\nThe private key is:%ld&%ld\n",n,d);
  printf("\nInput a number to encrypt:\n");
  scanf("%ld",&m);
  c=rsa(m,e,n);
  printf("\nThe encrypted number is:\n%ld",c);
  t=rsa(c,d,n);
  printf("\nThe restored number is:\n%ld",t);
  if(t==m)
    printf("OK,RIGHT");
  else
    printf("ERROR");
  }
代码有点罗嗦，我把每一个功能都用了独立函数来写，并且没有真
正随机选取d和e，部分术语也不太准确，大家应该能看明白，呵呵。