rsa simple.c

这是RSA加密算法的简单实现

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

#define MAX 65535
#define LEN sizeof(struct slink) 
struct slink
{ 
//	int num;
	unsigned long  cinto;
	unsigned char sstring;
    struct slink *next;
};


unsigned long p,q,n;

 struct slink *creat(void)
{   
  struct  slink *head;
  struct  slink *p1,*p2;
     n=0;
	p1=p2=(struct slink * )malloc(LEN);
	scanf("%c",&p1->sstring);
	head=NULL;
while(p1->sstring!='\n')
   {
	p1->cinto=p1->sstring;
	n=n+1;
	if(n==1)
		head=p1;
	else p2->next=p1;
	p2=p1;
    p1=(struct slink * )malloc(LEN);
	scanf("%c",&p1->sstring);
	}
    p2->next=NULL;   
	return(head);
}

 void print(struct slink *head)
 {
	 struct slink *p;
     p=head;
   if(head!=NULL)
	do 
	{
	printf("%c",p->sstring);

    p=p->next;
	}while(p!=NULL);
    printf("\n\n");

 }

 void printnum(struct slink *head)
 {
	 struct slink *p;
     p=head;
   if(head!=NULL)
	do 
	{
	printf("%d",p->cinto);
    p=p->next;
	}
	while(p!=NULL);
    printf("\n");
 }




/* prints a random number in the range 0 to 99 */  
int isPrime(unsigned long n) /*/判断是否为素数*/
{ 
unsigned long i=0,k=2; 


k=(unsigned long)sqrt(n); 
for(i=2;i<=k;i++) 
{ 
if(n%i==0) 
break; 
} 

if(i>k) 
return 1; 
else 
return 0; 

} 

//求解密密钥d的函数(根据Euclid算法)
unsigned long  rsa(unsigned long p,unsigned long q,unsigned long e)  //求解密密钥d的函数(根据Euclid算法)
{
unsigned long g,k,r,n1,n2,t;
unsigned long b1=0,b2=1;

 g=(p-1)*(q-1);
 n1=g;
 n2=e;
    
    while(1)
 {
        k=n1/n2;
        r=n1-k*n2;
  if(r!=0)
  {
           n1=n2;
     n2=r;
     t=b2;
     b2=b1-k*b2;
     b1=t;
  }

  else
  {
   break;
  }

 }

    return (g+b2)%g;

}

/*/生成随机数 2~max 用来生成e和P,Q， */
unsigned long rnd(unsigned long max) /*/生成随机数 2~max 用来生成e和P,Q， */
{ /*/取系统时间做随机数种子                       */
unsigned long range,n;
unsigned long min=100,flag=0; 
time_t t; 
double j; 



range=max-min; 
t=time(NULL); 
srand((unsigned long)t); //初始化随机数发生器 以t为种子

n=rand(); //随机数发生器

j=((double)n/(double)RAND_MAX); //计算J为概率0.01~0.99
//在stdlib.h中已经定义了RAND_MAX=0x7FFF 

n=(int)(j*(double)range); 
n+=min; //保证了n>min

return n; 


}

int co_prime(unsigned long a ,unsigned long b) /*/ 求互质*/
{
unsigned long c;
do
{
if(b==1)
return 1;
c=a%b;
a=b;
b=c;

}while(c!=0);
return 0;
}


void sushu()
{  
   
   //printf("Random number in the 0-99 range: %d\n", random (100));  
	printf("随机产生的素数如下：\n");
srand(MAX);
while (!isPrime(p=rand()%MAX)||p<100 )  //p=rnd(256)
{
	p=rand()%MAX;
    //p=rnd(500);  
}
	printf("P : %d \n", p);
while (!isPrime (q=rand()%MAX)||q<100 )//q=rnd(256)
{
    //q=rnd(256);
    q=rand()%MAX;
}
    printf("q : %d \n", q);

return ;
} 
 
//////////======加密函数======/////////
struct slink *jiami(unsigned long  a,unsigned long  n,struct  slink *head)
{
     unsigned __int64  b,temp,k;
	 struct slink *p;
	 struct  slink *h;
     struct  slink *p1,*p2;
     unsigned long m=0;
	p1=p2=(struct slink* )malloc(LEN);
	h=NULL;
    p=head;
   if(head!=NULL)
	do 
	{
		b=a;
		temp=1;
        k=p->cinto;
   while(b!=1)
	{
     if(b%2==1) temp=(temp*k)%n;//temp*k 我感觉此处到最后的相乘有大数之间的问题109985585*112
       b=b/2;
       k=k*k%n;
	}

    k=temp*k%n;
	p1->cinto=k;
		m=m+1;
	if(m==1)
		h=p1;
	else p2->next=p1;
	p2=p1;
    p1=(struct slink * )malloc(LEN);
    p=p->next;//将结构体中的cinto加密为一个头指针为H的新链表中Cinto
//v1.push_back(k); // insert element into vector 
//v2.push_back(unsigned char(k));

	}	while(p!=NULL);
	p2->next=NULL;   
     p=h;
    printf("\n");
	// printnum(h);
	return(h);
    
}
//////////======解密函数======/////////
void jiemi(unsigned long a,unsigned long n,struct  slink *h)
{
unsigned long  b,temp,k;
	 struct slink *p;
	 p=h;
	 if(h!=NULL)
		do 
	{
		b=a;
		temp=1;
        k=p->cinto;
   while(b!=1)
	{
     if(b%2==1) 
		 temp=((temp%n)*k)%n;//temp*k 我感觉此处到最后的相乘有大数之间的问题109985585*112
       b=b/2;
       k=k*k%n;//K*k 我感觉此处到最后的相乘有大数之间的问题109985585*112
	}

    k=temp*k%n;
	p->sstring=k;
	p=p->next;
	}while (p!=NULL);

	print(h);
}



void main()
 {
	 struct slink *head;
	 struct slink *h;
     unsigned long a,n,m,e;
     sushu();
	 n=p*q;
	 m=(p-1)*(q-1);
     printf("nn  is :  %d \n m  is  :  %d\n",n,m);
	 e=rand()%m;
	 //e=rnd(m);
	while(!co_prime(m,e))
	{    e=rand()%m;
		//e=rnd(m);

	}
	printf("e  is :  %d\n",e);
	for(a=1;a<=m;a++) /////======for循环算出a============////
	{
    if(a*e%m==1)
	{
     printf("由(q-1)*(p-1)的值算出d为： %d\n",a);
     break;
	}
    //printf("go on……\n");
    a++;//其中的A一定为奇数，所以a=a+2;
	}
	// nn=11413;
	// a=3533;
	// b=6597;
     head=creat();
	 printf("明文的内容显示如下：\n");
     print(head);
	 printf("明文转化为数字如下：\n");
	 printnum(head);
	 h=jiami(e, n,head);
	 printf("加密以后的密文如下：\n");
     printnum(h);
     jiemi( a, n, h);
	 printf("\n The Program is finished!\n");

 }