keygen.c

十六位的RSA加解密程序。程序中包括生成公钥和私钥的生成

#include "keygen.h"

int main()
{
	unsigned long a,b,c,p,q,n,fn,e,d;
	FILE *pf;

	printf("Please input a rand number(101~250) a:");
	scanf("%d",&a);				//第一个随机数
	printf("Please input another rand number(101~250) b:");
	scanf("%d",&b);				//第二个随机数
	printf("Please input another rand number(101~250) c:");
	scanf("%d",&c);				//第三个随机数

	p=getPrime(a);				//由第一个随机数求得素数
	q=getPrime(b);				//由第二个随机数求得素数
	n=p*q;
	fn=(p-1)*(q-1);

	for (e=c;;)					//求得公钥e
	{
		e=getPrime(e+1);
		if (gcd(e,fn)==1)		//是否和fn互质
			break;
	}
	d=Euclid(e,fn);				//求得私钥
	
	pf=fopen("PK.bin","w");		//保存公钥
	fprintf(pf,"%X-%X",n,e);
	fclose(pf);
	pf=fopen("SK.bin","w");		//保存私钥
	fprintf(pf,"%X-%X",n,d);
	fclose(pf);

	printf("	p=%d	q=%d	q-p=%d \n	n=%d	fn=%d	e=%d	d=%d\n	"
				,p,q,q-p,n,fn,e,d);
	
	return 0;
}

unsigned long getPrime(unsigned long a)
//计算大于a的第一个素数
{
	unsigned long i=9;
	unsigned long j=0;
	
	if (a%2==0)
		a++;

	for(i=a;;i+=2)
	{
		for (j=0;j<24;j++)			//先用小素数表检验
		{
			if (i%PrimeTable[j]==0)
				break;
		}
		if (j<24) continue;

		for(j=101;j<=i/10;j+=2)		//通过小素数表检验后，以步长2逐个检查，一直到i/10;
		{							//实际应该到sqrt(i),因sqrt()计算复杂，而i>100,10<sqrt(i),故取10
			if (i%j==0)
				break;
		}

		if(j>i/10)
			return i;
	}
}

unsigned long gcd(unsigned long a,unsigned long b)
//stein算法
{
	unsigned long temp;
	if(a<b)
	{
		temp = a;
		a = b;
		b=temp;
	}

	if(0==b)
		return a;
	if(a%2==0 && b%2 ==0)
		return 2*gcd(a/2,b/2);
	if ( a%2 == 0)
		return gcd(a/2,b);
	if ( b%2==0 )
		return gcd(a,b/2);
	return gcd((a+b)/2,(a-b)/2);
}


unsigned long Euclid(unsigned long x, unsigned y)
//扩展欧基里德算法
{
	int n = 2;
	
	unsigned long r[3] = {0,0,0};
	unsigned long q[3] = {0,0,0};
	long u[3] = {0,0,0};
	long v[3] = {0,0,0};
	long result=0;
	
	r[0] = x;
	r[1] = y;
	u[0] = 1;
	v[0] = 0;
	u[1] = 0;
	v[1] = 1;
	
	while (r[(n-1)%3]!=0) 
	{
		q[n%3] = r[(n-2)%3]/r[(n-1)%3];
		r[n%3] = r[(n-2)%3]-q[n%3]*r[(n-1)%3];
		u[n%3] = u[(n-2)%3]-q[n%3]*u[(n-1)%3];
		v[n%3] = v[(n-2)%3]-q[n%3]*v[(n-1)%3];
		n++;
	}
	result = u[(n-2)%3];
	if (result<0)
		result+=y;

	return result;
}