#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為大素數(shù)*/
unsigned char text_8[100];  /*存放用戶輸入的明文(每8bit一存儲)*/
unsigned text_16[100],secu_16[100];  /*分別存放用戶輸入的明文(每16bit一存儲),和分組密文(每16bit一存儲)*/
void public_key_product();           /*計算共鑰中的e,并產(chǎn)生大素數(shù)p和q,以及n,顯示e,n*/
void person_key_product();           /*計算私鑰中的d*/
int gcd(unsigned long,unsigned long); /*此函數(shù)判斷a和b是否互素(利用歐幾里得輾轉(zhuǎn)相除)*/
unsigned power(unsigned,unsigned,unsigned long); /*此函數(shù)計算"a的b次方對c求余"*/
void convert_16_to_8(unsigned a[100]);
 /*此函數(shù)的作用是將明文每16bit一存儲還原為每8bit一存儲,變化后的結(jié)果存放在text_8[],即將結(jié)果還原為char型*/
void convert_8_to_16(); /*此函數(shù)的作用是將明文每8bit一存儲變?yōu)槊?6bit一存儲,變化后的結(jié)果存放在text_16[]*/ 
void coder();       /*加密*/
void decoder();     /*解密*/
void get();          /*此函數(shù)獲取用戶輸入的明文*/





main()
{

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

  printf("Please enter your text to coded:\n");
  get();    /*獲取用戶輸入的明文*/
  public_key_product();    /*計算共鑰中的e,并產(chǎn)生大素數(shù)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()
{
 /*此函數(shù)獲取用戶輸入的明文*/
 printf("Enter the text('e' to exit):\n");
 scanf("%s",text_8);
}







int gcd(unsigned long a,unsigned long b)
{
 /*此函數(shù)判斷a和b是否互素(利用歐幾里得輾轉(zhuǎn)相除)*/
 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,并產(chǎn)生大素數(shù)p和q,以及n,顯示e,n*/

 srand(time(NULL));    /*隨機函數(shù)*/

 e=3;  /*初始化共鑰中的e*/
 p=2*(rand()%50000)+1+30000; /*根據(jù)RSA算法要求,此處隨機產(chǎn)生的p一定是奇數(shù)*/
 while(!is_number(p)&&p<65536); /*如果p不是素數(shù)且沒有越界,則取比p大且離p最近的奇數(shù)p+2繼續(xù)測素*/
 {
  p+=2;
 }
 q=2*(rand()%10000)+1+30000; /*此處用random(10000),是為了保證p和q大小上有一定差距,使加密算法安全*/
 while(!is_number(q)&&q<65536);/*根據(jù)RSA算法要求,此處隨機產(chǎn)生的q一定是奇數(shù)*/
 {                              /*如果q不是素數(shù)且沒有越界,則取比q大且離q最近的奇數(shù)q+2繼續(xù)測素*/
  q+=2;
 }
 n=(unsigned long )p*(unsigned long)q;  /*求出n*/
 while(!gcd((unsigned long )(p-1)*(unsigned long )(q-1),e))  /*找出與n的歐拉函數(shù)值互素的e*/
 e++;
 printf("\nThe public key is: (e=%d,n=%lu)",e,n);  /*e和n共同作為共鑰*/
}




void person_key_product()        
{
 /*此函數(shù)求出私鑰中的d*/
 int i=1;
 while((((p-1)*(q-1)*i+1)%e)&&i>0)  
    i++;                             
 d=((p-1)*(q-1)*i+1)/e;
  /*設(shè)n的歐拉函數(shù)為a(n),則a(n)=(p-1)*(q-1). 當a(n)+1=k*e(k為某個整數(shù))時,退出循環(huán)*/
  /*此時,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)
{
  /*此函數(shù)對傳入的n進行素性檢驗*/
  /*傳入的n一定是奇數(shù),但不一定是素數(shù)*/

 unsigned m=1,b=0,a,j=n-1,i,z;
  while(!j%2)  /* !的優(yōu)先級高于%, 所以只有當j=0即n=1時,才進這個循環(huán)*/
   {
    m*=2;
    b++;
    j/=2;
   }
   m=(n-1)/m;         /*j!=0時(這是大多數(shù)情況),經(jīng)過此步后，m=n-1，b=0*/
   a=random(n-1);     /*a小于等于n-1*/
   for(j=0;j<1000;j++)  /*用作測試的數(shù)a只有取夠一定數(shù)量，才可說明n是素數(shù) */
   {
    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不是素數(shù)*/
         return 0;           /*此處判斷z與p-1的關(guān)系是為了下面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)
{
 /*此函數(shù)計算"a的b次方對c求余"*/

 unsigned long z=1,t;
 for(t=a;b>0;b>>=1)
 {
  /*每輪循環(huán)b右移1位是為了控制循環(huán)次數(shù),可如下等價理解:*/
  /*將b寫成二進制形式:m_k,m_k-1,m_k-2------m_0.其中k就是循環(huán)次數(shù)*/

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

  /* 此函數(shù)的原理是:*/
  /* 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是奇數(shù).當b是奇數(shù)時,b的二進制表示的最低位是1.又因為每次循環(huán)b*/
   /* 都右移1位,因此此時b的最低位其實是傳入此函數(shù)的b的二進制表示的第j位*/
   /* j表示當前的循環(huán)次數(shù),從0開始,二進制表示的位數(shù)從0開始. */

   /*對于傳入此函數(shù)的b, 若其二進制表示第j位為1,即mj=1,則根據(jù)上面提到的此函數(shù)的*/
   /*原理,應(yīng)將mj,mj-1,mj-2-------m0表示的十進制數(shù)(即[(a(mj))(2(j))])累乘到z中*/
   /*而[(a(mj))(2(j))]就是t*/

   t=(t*t)%c;

   /* 此函數(shù)實際操作時:*/
   /* t存放當前"a的i次方"的值(i=1,2,3----k)*/
   /* [(a(m))(2(i))]的值*/

  }
  return z;
 }



void convert_8_to_16()
{
  /*此函數(shù)的作用是將明文每8bit一存儲變?yōu)槊?6bit一存儲,變化后的結(jié)果存放在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型數(shù)組,因此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])
{
   /*此函數(shù)的作用是將明文每16bit一存儲還原為每8bit一存儲,變化后的結(jié)果存放在text_8[],即將結(jié)果還原為char型*/
   /*這主要是為了用戶察看加密和解密結(jié)果的方便,因為char會對應(yīng)某一個字符*/
  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++;
  }

  /*這個函數(shù)是convert_8_to_16函數(shù)的逆變換*/
  /*由函數(shù)convert_8_to_16可知,a[i]=text_8[2*i]*256+text_8[2*i+1]. 由整數(shù)的相關(guān)定理可得:若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()
{
 /*此函數(shù)為加密過程*/
 int i;
 i=0;
 convert_8_to_16();     /*詳見convert_8_to_16函數(shù)體說明*/
 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函數(shù)體說明*/
}

void decoder()
{
 /*此函數(shù)為解密過程*/
 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函數(shù)體說明*/
}