COSC3325              Program-2A                  	
		     RSA CryptoSystem Implementation     	Due: 4/19/2007
	Task:

	Write a program to implement the RSA Public-Key algorithm.
	The algorithm is described below with some requirements included:
	a. Choose two primes p and q
	   let p=503 and q=997
	   So, n = p*q = 503*997
	b. Calculate a number e (public key) less than n that is relatively 
	   prime to Totient(n) which is (p-1)*(q-1) = 502*996
	c. Calculate a number d (private key) less than n which is the multiplicative
	   inverse of e (mod-Totient(n)). 
	   For this you can use the function GCDExt() given in the following suggestions.  
	d. Apply the public key followed by applying the private key to
	   the following four messages (whose value each is less than n):
		1000
		2000
		3000
		4000
		
	Output requirements:
	Your program outputs should include:
	1. The public key and the private key calculated.
	2. For each message of the four above:
		the original plaintext and the ciphertext and the decrypted ciphertext
		(which must be the same as the original plaintext)

	Suggestions:
	Use the following two functions:
	//////////////////////////////////////////////////////
	int GCDExt (long n, long m, long& inv)
	/* This function 
	   1. returns GCD(n,m) as its own value (where n>=m>1) and
	   2. computes and returns the multiplicative inverse of m (mod n)
	      via the third parameter. It will be zero when it does not exist
	      And, it does not exist if GCD(n,m)>1
	*/
	{  long x1,x2,x3, y1,y2,y3, r1,r2,r3,  quo;
	   x1 = 1; x2 = 0; x3 = n;
	   y1 = 0; y2 = 1; y3 = m;
	   /* Note (1) initially, x1*n+x2*m=x3 and
	                          y1*n+y2*m=y3, and
	           (2) throughout the following computations, these relationships
	               will hold.
	           (3) Hence, when y3 becomes 1, y2 is what we are looking for, namely
	               the Multiplicative Inverse of m (mod n).
	               Of course, when x3 becomes 1, x2 will also be what we are looking for.
	               But, y3 will become 1 before x3 becomes 1.
	  */
	   while (1)	// infinite loop
	   {
	   	if (y3==0)	//no inverse
		{  inv=0;
		   return x3;
		}
		if (y3==1)	//inverse found
		{  inv=y2;
		   return y3;
		}	// else not done yet.
		quo = x3/y3; 
		r1 = x1 - quo*y1;
		r2 = x2 - quo*y2;
		r3 = x3 - quo*y3;
		x1 = y1;  y1 = r1;
		x2 = y2;  y2 = r2;
		x3 = y3;  y3 = r3; 
	    }
	}	// end of GCDExt()
	
	Testing above function:
	  Suppose that n=32 and m=9 (They are Relatively Prime, i.e., their GCD is 1)
		x1	x2	x3	y1	y2	y3	quo
		---------------------------------------------------
		1	0	32	0	1	9	3
		0	1	9	1	-3	5	1
		1	-3	5	-1	4	4	1
		-1	4	4	2	-7	1	x
		Y3 is now 1 and hence y2=-7 is the M.I.
		But, using the next functionm, FirstPos(), we will get
		-7+32 which is 25 as the M.I. we are looking for.
		And, indeed 9 and 25 are M.I. (mod 32) as 9*25=225=1 (mod 32)

	long FirstPos (long inv, long n)
	// This function return the smallest positive integer k
	// such that k = inv + m * n where m>0.
	{
	  int k = inv;
	  while (k<=0)
		k = k+n;
	  return k;
	}	// end of FirstPos()