rsaprime.c

很有意思得加密解密算法

/* RSAPRIME.C - primality-testing routines
 */

#include "global.h"
#include "rsaref.h"
#include "nn.h"
#include "rsaprime.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "math.h"

static unsigned int Log2(unsigned int);
static int          ProbablePrime(NN_DIGIT *, unsigned int);
static int          PrimeTest(NN_DIGIT *, unsigned int, NN_DIGIT *,
										unsigned int, unsigned int, int);
static int          RelativePrime(NN_DIGIT *, NN_DIGIT *, unsigned int);
static void         GenerateRandomNumber(NN_DIGIT *, unsigned int);

static NN_DIGIT     w[MAX_NN_DIGITS], v[MAX_NN_DIGITS];

void FindStrongRSAPrime (a, aBits, exponent, printMsg)
NN_DIGIT     *a;
unsigned int aBits;
NN_DIGIT     *exponent;
const char   *printMsg[];
{
	NN_DIGIT     r[MAX_NN_DIGITS], s[MAX_NN_DIGITS];
	NN_DIGIT     A[MAX_NN_DIGITS], B[MAX_NN_DIGITS];
	NN_DIGIT     rs[MAX_NN_DIGITS], r_1[MAX_NN_DIGITS],
					 s_1[MAX_NN_DIGITS], b[MAX_NN_DIGITS];
	unsigned int rDigits, sDigits;
	unsigned int rBits, sBits, checkBits, i = 0;
	static int   numbr = 0;

	NN_AssignZero(r, MAX_NN_DIGITS);
	NN_AssignZero(s, MAX_NN_DIGITS);
	NN_AssignZero(w, MAX_NN_DIGITS);
	NN_AssignZero(v, MAX_NN_DIGITS);

   rBits = (aBits - (Log2(aBits) + 2)) / 2;
   sBits = rBits - Log2(rBits);

												 /* Doing step 1.2 & 1.3 */
	sDigits = (sBits + NN_DIGIT_BITS - 1) / NN_DIGIT_BITS;

	NN_ASSIGN_DIGIT(w, 2, sDigits);
	NN_ASSIGN_DIGIT(v, 1, sDigits);
	randomize();
	printf("%s", printMsg[i++]);
	GenerateRandomNumber(s, sBits);
	while (ProbablePrime(s, sDigits) != 0)
		NN_Add(s, s, w, sDigits);
	printf("%s", printMsg[i++]);
	NN_Mult(s, s, w, sDigits);
   sDigits = NN_Digits(s, MAX_NN_DIGITS);
	NN_Add(r, s, v, sDigits);       /* Compute r */
	while(ProbablePrime(r, sDigits) != 0)
		NN_Add(r, r, s, sDigits);

	rBits = NN_bits(r, MAX_NN_DIGITS);
	sBits = aBits - (Log2(aBits) + 2) - rBits;
	sDigits = (sBits + NN_DIGIT_BITS - 1) / NN_DIGIT_BITS;
	do
	{
		NN_AssignZero(s, MAX_NN_DIGITS);
		NN_AssignZero(a, MAX_NN_DIGITS);
		NN_AssignZero(A, MAX_NN_DIGITS);
		NN_AssignZero(B, MAX_NN_DIGITS);
		NN_AssignZero(rs, MAX_NN_DIGITS);
		NN_AssignZero(r_1, MAX_NN_DIGITS);
		NN_AssignZero(s_1, MAX_NN_DIGITS);
		NN_AssignZero(b, MAX_NN_DIGITS);
		printf("%s", printMsg[i]);
		GenerateRandomNumber(s, sBits);
		while (ProbablePrime(s, sDigits) != 0)
			NN_Add(s, s, w, sDigits);
		printf("%s", printMsg[i + 1]);
		rDigits = (rBits + NN_DIGIT_BITS - 1) / NN_DIGIT_BITS;
		if (sDigits < rDigits)
			sDigits = rDigits;
		NN_Sub(r_1, r, v, sDigits);
		NN_Sub(s_1, s, v, sDigits);
		NN_Mult(rs, r, s, sDigits);
		rDigits = NN_Digits(rs, MAX_NN_DIGITS);
		NN_ModExp(A, s, r_1, sDigits, rs, rDigits);
		NN_ModExp(B, r, s_1, sDigits, rs, rDigits);
		if (NN_Cmp(A, B, rDigits) < 0)
			NN_Add(A, A, rs, rDigits);
		NN_Sub(A, A, B, rDigits);
		if (NN_EVEN(A, rDigits) == 1)
			NN_Add(A, A, rs, rDigits);
		NN_Mult(rs, rs, w, rDigits);
      rDigits = NN_Digits(rs, MAX_NN_DIGITS);
		NN_Assign2Exp(a, aBits - 1, rDigits);
		NN_Sub(a, a, A, rDigits);
		NN_AssignZero(s, MAX_NN_DIGITS);
		NN_Div(s, b, a, rDigits, rs, rDigits);
		if (NN_Zero(b, rDigits) == 0)
			NN_Add(s, s, v, rDigits);
		NN_Mult(s, s, rs, rDigits);
      rDigits = NN_Digits(s, MAX_NN_DIGITS);
		NN_Add(a, A, s, rDigits);
		while ((checkBits = NN_bits(a, MAX_NN_DIGITS)) < aBits)
			NN_Add(a, a, rs, rDigits);
		NN_Sub(b, a, v, rDigits);
		while(((checkBits = NN_bits(a, MAX_NN_DIGITS)) <= aBits) &&
				((RelativePrime(b, exponent, rDigits) != 0) ||
				(ProbablePrime(a, rDigits) != 0)))
		{
			NN_Add(a, a, rs, rDigits);
			NN_Sub(b, a, v, rDigits);
		}
	}
	while (checkBits != aBits);
	printf("%s", printMsg[i + 2]);
	numbr += 3;
} /* FindStrongRSAPrime */

static unsigned int Log2(unsigned int value)
{
	unsigned int   result, Bits;

	for (result = 0, Bits = 1; Bits <= value; result++)
		Bits = Bits << 1;

	return (result);
} /* Log2 funstion */

int ProbablePrime(c, cDigits)
NN_DIGIT     *c;
unsigned int cDigits;
{
	unsigned int   qDigits;
	unsigned int   k;
	NN_DIGIT       q[MAX_NN_DIGITS], u[MAX_NN_DIGITS];

	NN_AssignZero(q, MAX_NN_DIGITS);
	NN_AssignZero(u, MAX_NN_DIGITS);
	NN_Sub(q, c, v, cDigits);
	for(k = 0; NN_EVEN(q, cDigits) != 0; k++)
		NN_Div(q, u, q, cDigits, w, cDigits);
	qDigits = NN_Digits(q, MAX_NN_DIGITS);
     return(PrimeTest(c, cDigits, q, qDigits, k, 15));
} /* ProbablePrime */

static int PrimeTest(n, nDigits, p, pDigits, k, timesTest)
NN_DIGIT     *n, *p;
unsigned int pDigits, nDigits;
unsigned int k;
int          timesTest;
{
	NN_DIGIT      y[MAX_NN_DIGITS], m[MAX_NN_DIGITS];
	NN_DIGIT      x[MAX_NN_DIGITS];
	unsigned int   j, xBits, nBits;

	NN_AssignZero(y, MAX_NN_DIGITS);
	NN_AssignZero(m, MAX_NN_DIGITS);

	j = 0;
	nBits = NN_bits(n, nDigits);
	NN_Sub(m, n, v, nDigits);
	while (timesTest > 0)
	{
	   NN_AssignZero(x, MAX_NN_DIGITS);
      while (((xBits = random(nBits)) == 1) || (xBits == 0));
		GenerateRandomNumber(x, xBits);
		NN_ModExp(y, x, p, pDigits, n, nDigits);
		for (j  = 0;
            (((j != 0) || ((xBits = NN_Cmp(y, v, nDigits)) != 0)) &&
			 (NN_Cmp(y, m, nDigits) != 0));)
            if ((j + 1 >= k) || ((j++ > 0) && (xBits == 0)))
				return (timesTest);
			else
					NN_ModExp(y, y, w, nDigits, n, nDigits);
		timesTest--;
	}
	return (timesTest);
} /* PrimeTest */

static void GenerateRandomNumber(rnd, rndBits)
NN_DIGIT     *rnd;
unsigned int rndBits;
{
	unsigned char   T[MAX_RSA_MODULUS_LEN];
	unsigned char   randNumber;
	unsigned int    bitsGen, j;

	for (bitsGen = 0, j = (rndBits + 7) / 8; bitsGen < rndBits; bitsGen += 8)
	{
		if (bitsGen == 0)
			while (!((randNumber = random(256)) % 2))
			;
		else
			randNumber = random(256);
		if ((bitsGen + 8) >= rndBits)
		{
			randNumber = randNumber & 0xBF;
			randNumber = randNumber | 0x80;
		}
		if ((bitsGen + 8) > rndBits)
			randNumber = randNumber >> ((bitsGen + 8)  - rndBits);
		T[--j] = randNumber;
	}
	NN_Decode(rnd, (rndBits + NN_DIGIT_BITS - 1) / NN_DIGIT_BITS,
               T, (rndBits + 7) / 8);
} /* GenerateRandomNumber */

static RelativePrime(p_1, e, eDigits)
NN_DIGIT     *e, *p_1;
unsigned int eDigits;
{
   NN_DIGIT   result[MAX_NN_DIGITS];

   NN_AssignZero(result, MAX_NN_DIGITS);
   if (NN_Cmp(p_1, e, eDigits) >= 0)
      NN_Gcd(result, p_1, e, eDigits);
   else
      NN_Gcd(result, e, p_1, eDigits);
   return (NN_Cmp(result, v, eDigits));
}

void ConvertTime(unsigned long   period, unsigned int *usedTime)
{
   unsigned long   a;

   usedTime[0] += period / 3600;
   a = period % 3600;
   usedTime[1] += a / 60;
   usedTime[2] += a % 60;
   if (usedTime[2] >= 60)
   {
      usedTime[2] = usedTime[2] - 60;
      usedTime[1] += 1;
   }
   if (usedTime[1] >= 60)
   {
      usedTime[1] = usedTime[1] - 60;
      usedTime[0] += 1;
   }
}