/* $Id: t_bdRsaFactorN.c $ */

/* 
	This code uses the free BIGDIGITS library version 2.3 available from
	http://di-mgt.com.au/bigdigits.html
	to show how to factor the RSA modulus n given the secret exponent d
	Copyright (C) 2012 DI Management Services Pty Ltd. All rights reserved.
*/

/*
	Last updated:
	$Date: 2012-12-24 16:13 $
	$Revision: 1.0.1 $
	$Author: dai $
*/

#include <stdio.h>
#include "bigd.h"

int debug = 1;
#define DBDPRINT(pre, x, post) if(debug)bdPrintDecimal((pre),(x),(post))

const int primes[] = {
	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
	31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
	73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 
	127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 
	179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 
	233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 
};
#define NPRIMES (sizeof(primes)/sizeof(primes[0]))

int find_factors_of_n(BIGD p, BIGD q, BIGD n, BIGD e, BIGD d)
{
	BIGD k, t, g, x, y, r;
	int i, isdone;
	k = bdNew();
	t = bdNew();
	g = bdNew();
	x = bdNew();
	y = bdNew();
	r = bdNew();

	bdSetZero(p);
	bdSetZero(q);

	/* 1. [Initialize] Set k <-- de - 1 */
	bdMultiply(k, d, e);
	bdDecrement(k);
	DBDPRINT("k=de-1=", k, "\n");

	/* 2. [Try a random g] Choose g at random from {2, ..., N-1} */
	/*    (we cheat a bit here and just try the first primes in order) */
	for (isdone = 0, i = 0; !isdone && i < NPRIMES; i++)
	{
		bdSetShort(g, primes[i]);
		DBDPRINT("Trying g=", g, "\n");
		/* Set t <-- k */
		bdSetEqual(t, k);
		/* 3. [Next t] If t is divisible by 2 ... */
		while (bdIsEven(t))
		{
			/* Set t <-- t / 2 */
			bdShiftRight(t, t, 1);
			DBDPRINT("t=", t, "\n");
			/* Set x = g^t mod N */
			bdModExp(x, g, t, n);
			DBDPRINT("x=g^t mod N=", x, "\n");
			/* 4. [Finished?] If x > 1 and y = gcd(x-1, N) 
			      then set p <-- y and q <-- N/y, output (p,q) and stop.
			*/
			if (bdShortCmp(x, 1) > 0)
			{
				bdDecrement(x);
				bdGcd(y, x, n);
				DBDPRINT("y=gcd(x-1,N)=", y, "\n");
				if (bdShortCmp(y, 1) > 0)
				{	/* We have it */
					bdSetEqual(p, y);
					bdDivide(q, r, n, y);
					isdone = 1;
					break;
				}
			}
		} /* 4a. ... otherwise go to step 3. */
	}	/* 3a. ... otherwise go to step 2. */
	/* Finally, to be consistent with convention, we make sure p > q */
	if (isdone && bdCompare(p, q) < 0)
	{
		bdSetEqual(r, p);
		bdSetEqual(p, q);
		bdSetEqual(q, r);
	}

	bdFree(&k);
	bdFree(&t);
	bdFree(&g);
	bdFree(&x);
	bdFree(&y);
	bdFree(&r);

	return isdone;
}

void test_simple(void)
{
	BIGD n, e, d, p, q;
	n = bdNew();
	e = bdNew();
	d = bdNew();
	p = bdNew();
	q = bdNew();

	bdSetShort(n, 25777);
	bdSetShort(e, 3);
	bdSetShort(d, 16971);
	
	printf("Input:\n");
	bdPrintDecimal("n=", n, "\n");
	bdPrintDecimal("e=", e, "\n");
	bdPrintDecimal("d=", d, "\n");

	find_factors_of_n(p, q, n, e, d);

	printf("Output:\n");
	bdPrintDecimal("p=", p, "\n");
	bdPrintDecimal("q=", q, "\n");

//clean_up:
	bdFree(&n);
	bdFree(&e);
	bdFree(&d);
	bdFree(&p);
	bdFree(&q);
}

void test_508(void)
{
	BIGD n, e, d, p, q;
	n = bdNew();
	e = bdNew();
	d = bdNew();
	p = bdNew();
	q = bdNew();
	/*
	Using 508-bit RSA key from 
	"Some Examples of the PKCS Standards"
	An RSA Laboratories Technical Note,
	Burton S. Kaliski Jr., November 1, 1993

	p = 33 d4 84 45 c8 59 e5 23 40 de 70 4b cd da 06 5f bb 40 58
	d7 40 bd 1d 67 d2 9e 9c 14 6c 11 cf 61
	q = 33 5e 84 08 86 6b 0f d3 8d c7 00 2d 3f 97 2c 67 38 9a 65
	d5 d8 30 65 66 d5 c4 f2 a5 aa 52 62 8b
	*/

	bdConvFromHex(n, "0a66791dc6988168de7ab77419bb7fb0c001c62710270075142942e19a8d8c51d053b3e3782a1de5dc5af4ebe99468170114a1dfe67cdc9a9af55d655620bbab");
	bdConvFromHex(e, "010001");
	bdConvFromHex(d, "0123c5b61ba36edb1d3679904199a89ea80c09b9122e1400c09adcf7784676d01d23356a7d44d6bd8bd50e94bfc723fa87d8862b75177691c11d757692df8881");
	
	printf("Input:\n");
	bdPrintHex("n=", n, "\n");
	bdPrintHex("e=", e, "\n");
	bdPrintHex("d=", d, "\n");

	find_factors_of_n(p, q, n, e, d);

	printf("Output:\n");
	bdPrintHex("p=", p, "\n");
	bdPrintHex("q=", q, "\n");

//clean_up:
	bdFree(&n);
	bdFree(&e);
	bdFree(&d);
	bdFree(&p);
	bdFree(&q);
}

void test_alice1024(void)
{
	BIGD n, e, d, p, q;
	n = bdNew();
	e = bdNew();
	d = bdNew();
	p = bdNew();
	q = bdNew();
	/*
	Using Alice's 1024-bit RSA key from [RFC4134]:
	Hoffman, P., Ed., "Examples of S/MIME Messages", RFC 4134, July 2005.
	*/

	bdConvFromHex(n, "E08973398DD8F5F5E88776397F4EB005BB5383DE0FB7ABDC7DC775290D052E6D12DFA68626D4D26FAA5829FC97ECFA82510F3080BEB1509E4644F12CBBD832CFC6686F07D9B060ACBEEE34096A13F5F7050593DF5EBA3556D961FF197FC981E6F86CEA874070EFAC6D2C749F2DFA553AB9997702A648528C4EF357385774575F");
	bdConvFromHex(e, "010001");
	bdConvFromHex(d, "A403C327477634346CA686B57949014B2E8AD2C862B2C7D748096A8B91F736F275D6E8CD15906027314735644D95CD6763CEB49F56AC2F376E1CEE0EBF282DF439906F34D86E085BD5656AD841F313D72D395EFE33CBFF29E4030B3D05A28FB7F18EA27637B07957D32F2BDE8706227D04665EC91BAF8B1AC3EC9144AB7F21");
	// p = F6D6E022214C5F0A70FF27FCE5B3506A9DE50FB58596C640FAA80AB49B9B0C55C2011DF937828A14C8F2930E92CDA56621B93CD206BFB45531C9DCADCA982DD1
	// q = E8DEB0112509D2025101DE8AE89850F5777761A445936B085596735DF4C85B129322738B7FD3707FF5A4AABB74FD3C226ADA38912A865B6C14E8AE4C9EFA8E2F
	printf("Input:\n");
	bdPrintHex("n=", n, "\n");
	bdPrintHex("e=", e, "\n");
	bdPrintHex("d=", d, "\n");

	find_factors_of_n(p, q, n, e, d);

	printf("Output:\n");
	bdPrintHex("p=", p, "\n");
	bdPrintHex("q=", q, "\n");

//clean_up:
	bdFree(&n);
	bdFree(&e);
	bdFree(&d);
	bdFree(&p);
	bdFree(&q);
}



int main(void)
{
	test_simple();
	test_508();
	//test_alice1024();

	return 0;
}