import java.math.BigInteger;
import java.util.Random;

public class RSA{
    public static void main(String[] args){
	BigInteger M, X, e, d, p, q, n, phi, XX;
	BigInteger ONE = BigInteger.ONE; // We'll use it a lot

	p = new BigInteger(5, 10, new Random());
	q = new BigInteger(6, 10, new Random());
	
	M = new BigInteger("27");
	
	n = p.multiply(q);
	
	phi = p.subtract(ONE).multiply(q.subtract(ONE));
	
	System.out.println("p = " + p + ", q = " + q + ", phi = " + phi);

	System.out.println("Message = " + M);

	// Now we find e, relatively prime to phi
	e = new BigInteger("2");
	while(phi.gcd(e).compareTo(ONE) != 0)
	    e = e.add(ONE);
	// Fortunately, finding inverses is built in
	d = e.modInverse(phi);

	System.out.println("e = " + e + " and d = " + d + ".  ed mod phi = " + e.multiply(d).mod(phi));

	// Encrypt
	X = M.modPow(e, n);
	System.out.println("Encrypted value = " + X);

	// Decrypt
	XX = X.modPow(d, n);
	System.out.println("Decrypted value = " + XX);

    }
}