main.c

RSA的C语言实现 gcc 3.4.2编译通过

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const prime[7]={2,3,5,7,11,13,17};

int gen_prime_num();
char is_prime_num(int prime_num);
int gcd(int a , int b);
void gen_p_q(int *p, int *q);
void gen_e_d(int * e, int *d , int * omiga_n );
void gen_key(int * p, int *q , int * e , int * d ,int * n , int * omiga_n);
int gen_d(int a ,int b);
int plain2pl(char * trans , int len);
int cipher(int plain , int n ,char b[17] );
int mo(int a , int b , int n);



int gcd(int a , int b)
{
    if(a==b) return a;
    if(a>b)  return gcd(a-b,b);
    else     return gcd(a,b-a);
}

/*产生100-200间的素数*/
int gen_prime_num()
{
    srand((unsigned)time(NULL));
    int prime_num;
    do{
            prime_num=(rand()%100)+100;
    }    while(!is_prime_num(prime_num));
    return prime_num;
}

char is_prime_num(int num)
{
     int i;
     for(i=0;i!=7;i++)
        if(!(num%prime[i])) return 0;
     return 1;
}

void gen_p_q(int * p, int * q)
{
     char choice;
     printf("请选择手动输入素数(h)或自动生成(a)\n");
     choice=getchar();
     do{
        if(choice=='h'||choice=='a') break;
        printf("选择错误，请重新选择(h/a)\n");
        getchar();
        choice=getchar();
      }while(1);
     getchar();       
     switch(choice)
     { 
        case 'a' : 
          *p=gen_prime_num();
          *q=gen_prime_num();  
          while(*p==*q){ *q=gen_prime_num(); }
          break;
        case 'h' : 
          printf("p: ");
          scanf("%d",p);
          getchar();
          printf("q: ");
          scanf("%d",q);
          getchar();
          break;
     }
     
 }

void gen_key(int * p, int *q , int * e , int * d ,int * n , int * omiga_n)
{
     gen_p_q(p,q); /*产生大素数P、Q*/
     *n=*p**q;
     *omiga_n=(*p-1)*(*q-1);
     gen_e_d( e , d , omiga_n);
     
 }
 
void gen_e_d(int * e, int *d , int * omiga_n)
{
     char choice;
     printf("请选择手动输入密钥(h)或自动生成(a)\n");
     choice=getchar();
     do{
        if(choice=='h'||choice=='a') break;
        printf("选择错误，请重新选择(h/a)\n");
        getchar();
        choice=getchar();
      }while(1); 
     getchar(); 
     switch(choice){
      case 'h':
          printf("e: ");
          scanf("%d",e);
          getchar();
          break;
      case 'a':
           srand((unsigned)time(NULL));  
          do{
              *e=rand()%(*omiga_n);
           }while(gcd(*e,*omiga_n)!=1);
          break;
     }
     *d=gen_d(*e,*omiga_n);
     if(*d<0) *d=*d+*omiga_n;
}

int gen_d (int a , int b)
{
    int s0=1,s1=0,s2,q,t;
    while(b>0)
    {
        q=a/b;
        s2=s0-q*s1;
        s0=s1;
        s1=s2;
        t=b;
        b=a%b;
        a=t;
    }
    if(a==1) return s0;
    else return 0;
}

int plain2pl(char * trans , int len)
{
    int i,j;
    for(i=0,j=0;i!=len;i++)
     j=j*10+trans[i]-'0';
    return j;
}

int cipher(int a , int n ,char b[17] )
{
    int A=1,i;
    for(i=0;i!=17;i++)
    {
      if(b[i]==1) A=mo(A,a,n);
      a=mo(a,a,n);
    }
    return A;
}

int mo(int a , int b , int n)
{
    int c;
    c=a*b;
    while(c>n) {
      c-=n; }
    return c;
}

int main(int argc, char *argv[])
{
  int p,q,n,omiga_n,e=0,d=0;
  gen_key(&p,&q,&e,&d,&n,&omiga_n);
  printf("p: %d\t\tq: %d\nn: %d\tomiga_n: %d\ne: %d\nd: %d\n",p,q,n,omiga_n,e,d);
  int i,j;
  
  char d_2[17]={0};
  char e_2[17]={0};
  for(i=0;i!=17;i++)
  {
     e_2[i]=(e>>i)&1;
     d_2[i]=(d>>i)&1;
  }
  
  
  char plain[25]={'B','O','X','U','E','E','R','D','U','Z','H','I','Q','I','E','W','E','N','E','R','J','I','N','S','I'};
  char trans[50]={0};

  for(i=0;i!=25;i++)
  sprintf(trans+2*i,"%2d",(char)plain[i]);
  int pl[17]={0};
  int ciph[17]={0};
  int cc[17]={0};
  for(i=0;i!=16;i++)
  {
      pl[i]=plain2pl(trans+3*i,3);      
  }
  pl[16]=plain2pl(trans+48,2);
  for(i=0;i!=17;i++)
    ciph[i]=cipher(pl[i],n,e_2);
  for(i=0;i!=17;i++)
    cc[i]=cipher(ciph[i],n,d_2);
  
  for(i=0;i!=17;i++)
  {  printf("code[%d] %6d\t",i,ciph[i]);
                    }
  printf("\n\n\n");
  for(i=0;i!=17;i++)
    printf("plain[%d] %d\t",i,cc[i]);
  
  
  printf("\n");
  system("PAUSE");	
  return 0;
}