rsagen.cpp

RSA算法的VC源码

/*	rsagen.c - C source code for RSA public-key key generation routines.

	RSA-specific routines follow.  These are the only functions that
	are specific to the RSA public key cryptosystem.  The other
	multiprecision integer math functions may be used for non-RSA
	applications.  Without these functions that follow, the rest of
	the software cannot perform the RSA public key algorithm.
*/
#include "stdafx.h"
#include "genprime.h"
#include "rsagen.h"
#include "mpilib.h"
/* ZHAO YONG #include "random.h" */

void derive_rsakeys(unsigned short* n,unsigned short* e,unsigned short* d,
	unsigned short* p,unsigned short* q,unsigned short* u,short ebits);
	/* Given primes p and q, derive RSA key components n, e, d, and u. */


/* Define some error status returns for RSA keygen... */
#define KEYFAILED -15		/* key failed final test */


#define swap(p,q)  { unsigned short* t; t = p;  p = q;  q = t; }


void derive_rsakeys(unsigned short* n, unsigned short* e, unsigned short* d,
	unsigned short* p, unsigned short* q, unsigned short* u, short ebits)
/*
 * Given primes p and q, derive RSA key components n, e, d, and u.
 * The global_precision must have already been set large enough for n.
 * Note that p must be < q.
 * Primes p and q must have been previously generated elsewhere.
 * The bit precision of e will be >= ebits.  The search for a usable
 * exponent e will begin with an ebits-sized number.  The recommended
 * value for ebits is 5, for efficiency's sake.  This could yield
 * an e as small as 17.
 */
{
	unsigned short  F[MAX_UNIT_PRECISION];
	unitptr ptemp, qtemp, phi, G; 	/* scratchpads */

	/*	For strong prime generation only, latitude is the amount
		which the modulus may differ from the desired bit precision.
		It must be big enough to allow primes to be generated by
		goodprime reasonably fast.
	*/
#define latitude(bits) (max(min(bits/16,12),4))	/* between 4 and 12 bits */

	ptemp = d;	/* use d for temporary scratchpad array */
	qtemp = u;	/* use u for temporary scratchpad array */
	phi = n;	/* use n for temporary scratchpad array */
	G = F;		/* use F for both G and F */
	
	if (mp_compare(p,q) >= 0)	/* ensure that p<q for computing u */
		swap(p,q);		/* swap the pointers p and q */

	/*	phi(n) is the Euler totient function of n, or the number of
		positive integers less than n that are relatively prime to n.
		G is the number of "spare key sets" for a given modulus n. 
		The smaller G is, the better.  The smallest G can get is 2. 
	*/
	mp_move(ptemp,p); mp_move(qtemp,q);
	mp_dec(ptemp); mp_dec(qtemp);
	mp_mult(phi,ptemp,qtemp);	/*  phi(n) = (p-1)*(q-1)  */
	mp_gcd(G,ptemp,qtemp);		/*  G(n) = gcd(p-1,q-1)  */
#ifdef DEBUG
	if (countbits(G) > 12)		/* G shouldn't get really big. */
		mp_display("\007G = ",G);	/* Worry the user. */
#endif /* DEBUG */
	mp_udiv(ptemp,qtemp,phi,G);	/* F(n) = phi(n)/G(n)  */
	mp_move(F,qtemp);

	/*
	 * We now have phi and F.  Next, compute e...
	 * Strictly speaking, we might get slightly faster results by
	 * testing all small prime e's greater than 2 until we hit a 
	 * good e.  But we can do just about as well by testing all
	 * odd e's greater than 2.
	 * We could begin searching for a candidate e anywhere, perhaps
	 * using a random 16-bit starting point value for e, or even
	 * larger values.  But the most efficient value for e would be 3, 
	 * if it satisfied the gcd test with phi.
	 * Parameter ebits specifies the number of significant bits e
	 * should have to begin search for a workable e.
	 * Make e at least 2 bits long, and no longer than one bit 
	 * shorter than the length of phi.
	 */
//	ebits = min(ebits,countbits(phi)-1);
//	if (ebits==0) ebits=5;	/* default is 5 bits long */
//	ebits = max(ebits,2);
//	mp_init(e,0);
//	mp_setbit(e,ebits-1);
//	lsunit(e) |= 1;		/* set e candidate's lsb - make it odd */
//	mp_dec(e);  mp_dec(e); /* precompensate for preincrements of e */
//	do 
//	{
//		mp_inc(e); mp_inc(e);	/* try odd e's until we get it. */
//		mp_gcd(ptemp,e,phi);    /* look for e such that gcd(e,phi(n)) = 1 */
//	} while (testne(ptemp,1));

	/*	Now we have e.  Next, compute d, then u, then n.
		d is the multiplicative inverse of e, mod F(n).
		u is the multiplicative inverse of p, mod q, if p<q.
		n is the public modulus p*q.
	*/
	int temp=65537;				//lzh 1.6 e=65537 
	memcpy(e,&temp,4);

	mp_inv(d,e,F);	/* compute d such that (e*d) mod F(n) = 1 */
	//mp_inv(d,e,phi);//lzh 1.27
	mp_inv(u,q,p);	/* (p*u) mod q = 1, assuming p<q */

	mp_mult(n,p,q);	/*  n = p*q  */
}	/* derive_rsakeys */

/* ZHAO YONG this function rsa_keygen() not use at all by me !!!  */