t_sprsa.c

大数的计算包括加减乘除

/* t_spRSA.c */

/******************* SHORT COPYRIGHT NOTICE*************************
This source code is part of the BigDigits multiple-precision
arithmetic library Version 1.0 originally written by David Ireland,
copyright (c) 2001 D.I. Management Services Pty Limited, all rights
reserved. It is provided "as is" with no warranties. You may use
this software under the terms of the full copyright notice
"bigdigitsCopyright.txt" that should have been included with
this library. To obtain a copy send an email to
<[e-mail]> or visit <www.di-mgt.com.au/crypto.html>.
This notice must be retained in any copy.
****************** END OF COPYRIGHT NOTICE*************************/

/*	Carry out tests on RSA mathematics using single digit numbers
	WARNING: this procedure is NOT cryptographically secure
	because the random numbers aren't.
*/

#include <stdio.h>
#include <assert.h>
#include "bigdigits.h"


/* RSA keys */
DIGIT_T n, e, d;

HALF_DIGIT_T spGenRsaPrime(void);
int spGenerateRSAKeys(DIGIT_T *n, DIGIT_T *e, DIGIT_T *d, int f);


int main()
{
	DIGIT_T m, c, m1;

	/*	Force linker to include copyright notice in 
		executable object image */
	copyright_notice();
		
	/* Generate a new set of keys */
	spGenerateRSAKeys(&n, &e, &d, 2);

	/* Create a random test message m < n */
	m = spPseudoRand(0, n - 1);

	printf("Test random message:\nm = %08lx\n", m);

	/* Encrypt with public key, c = m^e mod n */
	spModExp(&c, m, e, n);

	printf("c = %08lx\n", c);

	/* Decrypt with private key m = c^d mod n */
	spModExp(&m1, c, d, n);

	printf("m'= %08lx", m1);

	/* Check that we got back where we started */
	if (m1 != m) 
		printf(" <= ERROR - no match\n");
	else
		printf(" <= OK\n");

	return 0;
}

int spGenerateRSAKeys(DIGIT_T *n, DIGIT_T *e, DIGIT_T *d, int f)
{
	/* Generate an RSA key pair (n, e), (d) */
	DIGIT_T p, q;
	DIGIT_T L, g, t;
	DIGIT_T FermatNumber[] = { 0x3, 0x5, 0x11, 0x101, 0x10001 };

	/* Set e */
	*e = FermatNumber[f];

	/* Generate random prime p, ~ half length of modulus */
	do
	{
		p = spGenRsaPrime();

		/* Make sure gcd(p-1, e) = 1 */
		g = spGcd(p-1, *e);

		printf("g=%lx\n", g);

	} while (g != 1);
	
	printf("Final p=%08lx\n", p);

	/* And random prime q for balance of modulus length */
	do
	{
		q = spGenRsaPrime();

		/* Make sure gcd(p-1, e) = 1 */
		g = spGcd(q-1, *e);

		printf("g = %08lx\n", g);

	} while (g != 1 && p != q);

	printf("Final q=%08lx\n", q);
	printf("Final p=%08lx\n", p);
	
	/* Calculate modulus, n = pq */
	*n = p * q;
	/* and phi */
	L = (p-1) * (q-1);

	printf("n=p * q=%08lx\n", *n);
	printf("e=%08lx\n", *e);

	/* Calculate private key, d = e^-1 mod L */
	spModInv(d, *e, L);

	printf("d=e^-1 mod (p-1)(q-1)=%08lx\n", *d);

	/* Clear up */
	p = q = 0;
	g = t = L = 0;
	
	return 0;
}

HALF_DIGIT_T spGenRsaPrime(void)
{
	/* WARNING: This is not cryptographically secure */
	HALF_DIGIT_T p;
	DIGIT_T mask;

	/* Pick a random number half a digit long */
	p = (HALF_DIGIT_T)spPseudoRand(0, MAX_HALF_DIGIT);

	printf("p=%08x\n", p);

	/* Make sure highest and lowest bits are set */
	mask = HIBITMASK >> (BITS_PER_DIGIT / 2);
	p |= mask;
	p |= 0x1;

	printf("p=%08x\n", p);

	/* Check if prime */
	while (!spIsPrime(p, 50))
	{
		p += 2;

		printf("p=%08x\n", p);

		/* Check for overflow */
		if (!(p & mask))
			return 0;	/* Failed to find a prime */
	}

	return p;
}