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

public class RSA {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        RSA rsa = new RSA(256);
        System.out.println("generating codes ...");
        rsa.generateCodes();
        BigInteger encres = rsa.encryptBigInteger(new BigInteger("12345"));
        System.out.println("Encrypted: " + encres.toString());
        BigInteger decres = rsa.decryptBigInteger(encres);
        System.out.println("Decrypted: " + decres.toString());
        // rsa.extended_euclid(new BigInteger("834"), new BigInteger("543"));
        // rsa.extended_euclid(new BigInteger("253"), new BigInteger("220"));
        // BigInteger a = rsa.bigIntExpMod(new BigInteger("23456"), new
        // BigInteger("1235"), new BigInteger("8326363"));
        // System.out.println(a.toString());

    }

    private BigInteger d, e, p, n, phi, q;
    private int bitsize;

    public RSA(int bitsize) {
        this.bitsize = bitsize;
        generateCodes();
    }

    /*
     * Choose D depending on E and phi E * D - 1 is evenly divisible by (p -1) *
     * (q - 1)
     */
    private BigInteger chooseD(BigInteger phi, BigInteger e) {
        System.out.println("choosing d...");
        BigInteger[] result = extended_euclid(e, phi);
        BigInteger res = result[1].abs();
        boolean check = e.multiply(res).subtract(BigInteger.ONE).mod(phi)
                .equals(BigInteger.ZERO);
        if (check) {
            return result[1];
        } else
            return null;
    }

    /*
     * Choose E depending on phi p,q are primes E < n E is Relatively Prime to
     * (p - 1) * (q - 1)=phi This means that E and (p - 1) * (q - 1) have no
     * common factors except 1
     */
    private BigInteger chooseE(BigInteger phi) {
        BigInteger two = new BigInteger("2");
        BigInteger three = new BigInteger("3");
        for (BigInteger i = three; (i.compareTo(phi) < 0); i = i.add(two)) {
            if (extended_euclid(i, phi)[0].equals(BigInteger.ONE)) {
                return i;
            }
        }
        return new BigInteger("-1");
    }

    /*
     * a recursive implementation of the extended euclidian algorithm
     */
    private BigInteger[] extended_euclid(BigInteger a, BigInteger b) {
        BigInteger[] result = new BigInteger[3];
        if (b.equals(BigInteger.ZERO)) {
            result[0] = a;
            result[1] = BigInteger.ONE;
            result[2] = BigInteger.ZERO;
        } else {
            BigInteger[] recres = extended_euclid(b, a.mod(b));
            result[0] = recres[0];
            result[1] = recres[2];
            result[2] = recres[1].subtract(a.divide(b).multiply(recres[2]));
        }
        return result;
    }
    /*
     * Generate codes e and d
     */
    public void generateCodes() {
        do {
            p = BigInteger.probablePrime(bitsize, new Random());
            q = BigInteger.probablePrime(bitsize, new Random());
            n = p.multiply(q);
            phi = q.subtract(BigInteger.ONE).multiply(
                    p.subtract(BigInteger.ONE));
            e = chooseE(phi);
            d = chooseD(phi, e);
        } while (d == null);

        System.out.println("p: " + p.toString() + " q: " + q.toString()
                + " e: " + e.toString() + " d: " + d.toString() + " phi: "
                + phi.toString() + " n: " + n);
    }
    /*
     * encrypt
     */
    private BigInteger encryptBigInteger(BigInteger msg) {
        return bigIntExpMod(msg, e, n);
    }
    /*
     * decrypt
     */
    private BigInteger decryptBigInteger(BigInteger msg) {
        return bigIntExpMod(msg, d, n);
    }
    /*
     * Exponentation
     */
    private BigInteger bigIntExpMod(BigInteger base, BigInteger exponent,
            BigInteger m) {
        BigInteger result = BigInteger.ONE;
        BigInteger two = new BigInteger("2");
        while (!(e.equals(BigInteger.ZERO))) {
            if (e.mod(two).equals(BigInteger.ZERO)) {
                base = base.multiply(base).mod(m);
                e = e.divide(two);
            } else {
                result = base.multiply(result).mod(m);
                e = e.subtract(BigInteger.ONE);
            }
        }
        return result;
    }

}