// Arup Guha
// Written 7/29/06, edited on 8/2/06 for BHCSI Cryptography Course
// The purpose of this program is to illustrate the mechanics of RSA.
// Since this example only uses ints, it can't be used to illustrate
// the strength of RSA. Overflows may occur if the product of the 
// primes chosen exceeds the square root of 2^31-1, or about 46,340. 
import java.util.*;
public class RSA {
	
	
	public static void main(String[] args) {
		
		int p, q, n, phi, e=3, d;
		Scanner stdin = new Scanner(System.in);
		
		// Read in the two secret keys, p and q.
		// We assume they are prime without checking to simplify
		// this demonstration.
		System.out.println("Enter a prime p.");
		p = stdin.nextInt();
		
		System.out.println("Enter a prime q.");
		q = stdin.nextInt();
		
		// Calculate the public key n.
		n = p*q;
		
		// Calculate phi of n, which is secret information.
		phi = (p-1)*(q-1);
		
		// Try random values of e until one works.
		boolean done = false;
		while (!done) {
			
			System.out.println("Enter e.");
			e = stdin.nextInt();
			
			// e must be relatively prime to the phi of n. 
			// Checl that here, otherwise ask for another e.
			// When e is set, it will the other public key.
			if (gcd(e, phi) == 1)
				done = true;
			else
				System.out.println("Your e is not relatively prime with phi.");	
		}
		
		// Calculate the secret key d. This can be done only with
		// knowledge of phi of n.
		d = modInv(e, phi);
		
		// Try out a test message.
		System.out.println("Enter your message, in between 1 and "+(n-1));
		int m = stdin.nextInt();
		
		// Calculate the corresponding ciphertext.
		int c = modexp(m, e, n);
		System.out.println("Ciphertext is "+c);
		
		// Recover the plaintext as the message recipient would.
		int mback = modexp(c, d, n);
		System.out.println("orig m is "+mback);
		
	}
	
	// Recursive GCD function determines the greatest common divisor
	// of a and b.
	public static int gcd(int a, int b) {
		
		// Make the first parameter greater than or equal to the second.
		if (a < b) return gcd(b,a);
		
		// A base case.
		if (b == 0) return a;
		
		// Another base case.
		if (a%b == 0) return b;
		
		// Here's the recursive calculation.
		return gcd(b, a%b);
	}
	
	// This is a very, very slow modular inverse method. This will work
	// fine for the small numbers allowed in this demonstration. It just
	// does a brute force check for through all possible inverse values.
	// It's goal is to find an integer x such that x*val is equivalent to
	// 1 mod modulus. If no such inverse exists, -1 is returned.
	public static int modInv(int val, int modulus) {
		
		// Check each value.
		for (int i=1; i<modulus; i++)
		
			// Return it if we found one that works.
			if (val*i%modulus == 1)
				return i;
				
		// Never found an inverse.
		return -1;
	}
	
	// This is also very slow compared to the typical efficient method of
	// modular exponentiation. Again, it will work just fine for this
	// small demonstration.
	public static int modexp(int base, int exp, int modulus) {
		int ans = 1;
		
		// Multiply base exactly exp number of times, intermittently
		// modding so the intermediate result doesn't get too large.
		for (int i=0; i<exp; i++)
		
			// Since each of ans and base could be as large as modulus,
			// we could get an overflow with the multiplication if that
			// product exceeds the positive capacity of an int.
			ans = (ans*base)%modulus;
			
		// Return the answer.
		return ans; 
	}
}