rsa.c

加密解密现代密码学的内容c语言编写uoto

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
unsigned long  n;    /* n=p*q ,n为公钥和私钥的一部分*/
int e,d;             /*e为公钥的一部分,d为私钥的一部分*/
unsigned p,q;        /*p,q为大素数*/
unsigned char text_8[100];  /*存放用户输入的明文(每8bit一存储)*/
unsigned text_16[100],secu_16[100];  /*分别存放用户输入的明文(每16bit一存储),和分组密文(每16bit一存储)*/
void public_key_product();           /*计算共钥中的e,并产生大素数p和q,以及n,显示e,n*/
void person_key_product();           /*计算私钥中的d*/
int gcd(unsigned long,unsigned long); /*此函数判断a和b是否互素(利用欧几里得辗转相除)*/
unsigned power(unsigned,unsigned,unsigned long); /*此函数计算"a的b次方对c求余"*/
void convert_16_to_8(unsigned a[100]);
 /*此函数的作用是将明文每16bit一存储还原为每8bit一存储,变化后的结果存放在text_8[],即将结果还原为char型*/
void convert_8_to_16(); /*此函数的作用是将明文每8bit一存储变为每16bit一存储,变化后的结果存放在text_16[]*/ 
void coder();       /*加密*/
void decoder();     /*解密*/
void get();          /*此函数获取用户输入的明文*/





main()
{

 while(getch()!='e')
 {
  clrscr();

  printf("Please enter your text to coded:\n");
  get();    /*获取用户输入的明文*/
  public_key_product();    /*计算共钥中的e,并产生大素数p和q,以及n,显示e,n*/
  person_key_product();    /*计算私钥中的d*/
  coder();                 /*加密*/
  printf("\n\nThe text after code is:\n%s",text_8); /*显示密文*/
  printf("\n\np is: %lu\n",p);
  printf("\n\nq is: %lu\n",q);
  printf("\nThe private key is: (d=%d,n=%lu)",d,n);    /*显示d和n*/
  decoder();               /*解密*/
  printf("\n\nThe plaintext after decode is\n%s",text_8);
  getch();

 }
}



void get()
{
 /*此函数获取用户输入的明文*/
 printf("Enter the text('e' to exit):\n");
 scanf("%s",text_8);
}







int gcd(unsigned long a,unsigned long b)
{
 /*此函数判断a和b是否互素(利用欧几里得辗转相除)*/
 unsigned long c;
 if(a>=b)
 {
  c=a%b;
  if(c==0)
       return 0;    /*a和b不互素*/
    else if (c==1)
       return 1;    /*a和b互素*/
  else gcd(b,c);
  }
  else gcd(b,a);
}




void public_key_product()         
{
 /*计算共钥中的e,并产生大素数p和q,以及n,显示e,n*/

 srand(time(NULL));    /*随机函数*/

 e=3;  /*初始化共钥中的e*/
 p=2*(rand()%50000)+1+30000; /*根据RSA算法要求,此处随机产生的p一定是奇数*/
 while(!is_number(p)&&p<65536); /*如果p不是素数且没有越界,则取比p大且离p最近的奇数p+2继续测素*/
 {
  p+=2;
 }
 q=2*(rand()%10000)+1+30000; /*此处用random(10000),是为了保证p和q大小上有一定差距,使加密算法安全*/
 while(!is_number(q)&&q<65536);/*根据RSA算法要求,此处随机产生的q一定是奇数*/
 {                              /*如果q不是素数且没有越界,则取比q大且离q最近的奇数q+2继续测素*/
  q+=2;
 }
 n=(unsigned long )p*(unsigned long)q;  /*求出n*/
 while(!gcd((unsigned long )(p-1)*(unsigned long )(q-1),e))  /*找出与n的欧拉函数值互素的e*/
 e++;
 printf("\nThe public key is: (e=%d,n=%lu)",e,n);  /*e和n共同作为共钥*/
}




void person_key_product()        
{
 /*此函数求出私钥中的d*/
 int i=1;
 while((((p-1)*(q-1)*i+1)%e)&&i>0)  
    i++;                             
 d=((p-1)*(q-1)*i+1)/e;
  /*设n的欧拉函数为a(n),则a(n)=(p-1)*(q-1). 当a(n)+1=k*e(k为某个整数)时,退出循环*/
  /*此时,a(n)+1=k*e,即k*e=1*a(n)+1.所以在模a(n)条件下,k*e与1同余,这其中k就是所求的*/
  /*私钥中的d. d=(k*e)/e=(a(n)+1)/e=((p-1)*(q-1)*i+1)/e   */
}







int is_number(unsigned n)
{
  /*此函数对传入的n进行素性检验*/
  /*传入的n一定是奇数,但不一定是素数*/

 unsigned m=1,b=0,a,j=n-1,i,z;
  while(!j%2)  /* !的优先级高于%, 所以只有当j=0即n=1时,才进这个循环*/
   {
    m*=2;
    b++;
    j/=2;
   }
   m=(n-1)/m;         /*j!=0时(这是大多数情况),经过此步后，m=n-1，b=0*/
   a=random(n-1);     /*a小于等于n-1*/
   for(j=0;j<1000;j++)  /*用作测试的数a只有取够一定数量，才可说明n是素数 */
   {
    a+=2;
    if(a>2)
    {
     i=0;
     z=power(a,m,n); /*求"a的m次方对n求余"的值(j!=0时,m=n-1)*/
     if((z!=1)&&(z!=(p-1)))  /*由Fermat定理知,z!=1说明n不是素数*/
         return 0;           /*此处判断z与p-1的关系是为了下面j=0时的特别处理*/

      while((i<b)&&(z!=(p-1)))  /*对j=0的情况特别处理(一般用不到)*/
      {

       if((i>0)&&(z==1))
          return 0;
         z=power(z,2,p);
         i+=1;
       }
      if(z!=(p-1))return 0;
     }
     return 1;
   }

}






unsigned power(unsigned a,unsigned b,unsigned long c)
{
 /*此函数计算"a的b次方对c求余"*/

 unsigned long z=1,t;
 for(t=a;b>0;b>>=1)
 {
  /*每轮循环b右移1位是为了控制循环次数,可如下等价理解:*/
  /*将b写成二进制形式:m_k,m_k-1,m_k-2------m_0.其中k就是循环次数*/

  /* 在以下的注释中: "a(mk)"代表"a的mk次方","(a)(b)"代表"a的b次方",*/
  /* "[a]*[b]"代表"a*b"*/

  /* 此函数的原理是:*/
  /* b写成二进制形式后,"a的b次方"=a(b)=[(a(m_k))(2(k))]*[(a(m_k-1))(2(k-1))]*   */
  /* [(a(m_k-2))(2(k-2))]----*[(a(m_0))(2(0))].由此可见m_i=0的项的值=1,因此这一项*/
  /* 不用累乘到"a的b次方"中,只有当m_i=1时,才将[(a(mi))(2(i))]累乘到"a的b次方"中*/

   if(b%2==1)z=(z*t)%c;  /*z用来存放当前的"a的b次方"*/

   /* "b%2==1"说明b是奇数.当b是奇数时,b的二进制表示的最低位是1.又因为每次循环b*/
   /* 都右移1位,因此此时b的最低位其实是传入此函数的b的二进制表示的第j位*/
   /* j表示当前的循环次数,从0开始,二进制表示的位数从0开始. */

   /*对于传入此函数的b, 若其二进制表示第j位为1,即mj=1,则根据上面提到的此函数的*/
   /*原理,应将mj,mj-1,mj-2-------m0表示的十进制数(即[(a(mj))(2(j))])累乘到z中*/
   /*而[(a(mj))(2(j))]就是t*/

   t=(t*t)%c;

   /* 此函数实际操作时:*/
   /* t存放当前"a的i次方"的值(i=1,2,3----k)*/
   /* [(a(m))(2(i))]的值*/

  }
  return z;
 }



void convert_8_to_16()
{
  /*此函数的作用是将明文每8bit一存储变为每16bit一存储,变化后的结果存放在text_16[]*/ 
  /*这样做可以使加密的分组减少*/
 int i;
 for(i=0;i<100;i++)
  text_16[i]=text_8[2*i]*256+text_8[2*i+1]; 
 
  /*text_8[]是char型数组,因此text_8[i]为8bit*/
  /*所以text_8[2*i]+text_8[2*i+1]为16bit*/
  /*text_8[2*i]*256只是做了一个简单的线性变换,不影响加密*/
}

void convert_16_to_8(unsigned a[100])
{
   /*此函数的作用是将明文每16bit一存储还原为每8bit一存储,变化后的结果存放在text_8[],即将结果还原为char型*/
   /*这主要是为了用户察看加密和解密结果的方便,因为char会对应某一个字符*/
  int i=0,flag=0;
  unsigned temp;
  while(i<200&&flag<100)
  {
   temp=a[flag]/256;  
   text_8[i]=temp;
   text_8[i+1]=a[flag]%256;
   i+=2;
   flag++;
  }

  /*这个函数是convert_8_to_16函数的逆变换*/
  /*由函数convert_8_to_16可知,a[i]=text_8[2*i]*256+text_8[2*i+1]. 由整数的相关定理可得:若a=k*b+c,则有 */
  /* a/k=b, a%k=c .所以,text_8[i]=a[flag]/256 , text_8[i+1]=a[flag]%256.  */
 
}



void coder()
{
 /*此函数为加密过程*/
 int i;
 i=0;
 convert_8_to_16();     /*详见convert_8_to_16函数体说明*/
 while(text_16[i]!=0)
 {
 secu_16[i]=power(text_16[i],e,n); /*每16bit分组一加密,分组密文存放在secu_16[i]中*/
 i++;
 }
 convert_16_to_8(secu_16);   /*详见convert_16_to_8函数体说明*/
}

void decoder()
{
 /*此函数为解密过程*/
 int i;
 i=0;
 while(secu_16[i]!=0)
 {
 text_16[i]=power(secu_16[i],d,n);   /*每16bit分组一解密,分组明文存放在text_16[i]中*/
 i++;
 }
 convert_16_to_8(text_16);     /*详见convert_16_to_8函数体说明*/
}