import java.math.*;
import java.util.*;

public class MyRSA {

    private static Random aRand;
    private static BigInteger n;
    private static BigInteger pn;
    private static BigInteger e;
    private static BigInteger d;
    private static BigInteger IV;
    private static BigInteger p, q;
  
    private static final int MAX_BIT = 1024;
    private static final int MAX_TRY = 5;
    private static final int CHR_SIZE = 8;
    private static final BigInteger ONE = BigInteger.valueOf(1);
  
    private static int blocLength;
    private static int ZN = 256;
  
    private static String myPadding = "The wolrd wonders";
  
    public MyRSA(Random aRandom) {
      
        aRand = aRandom;
        generatePQ(aRand);
        findED();      
    }
  
    public BigInteger getN() {
        return n;
    }

    public BigInteger getE() {
        return e;
    }

    public BigInteger getD() {
        return d;
    }
  
    public static BigInteger RSAEncrypt(BigInteger m) {
        return m.modPow(e, n);
    }

    public static BigInteger RSADecrypt(BigInteger c) {      
        return c.modPow(d, n);      
    }
  
  
    public static BigInteger RSAEncrypt(BigInteger am, BigInteger an, BigInteger ae) {
        return am.modPow(ae, an);
    }
  
    public static BigInteger RSADecrypt(BigInteger ac, BigInteger an, BigInteger ad) {      
        return ac.modPow(ad, an);      
    }
  
    public String RSAEncryptBloc(String aString) {
        String result = "";
        Vector<String> aVectorMStr = new Vector<String>();
        Vector<String> aVectorCStr = new Vector<String>();
        Vector<BigInteger> aVectorMInt = new Vector<BigInteger>();
        Vector<BigInteger> aVectorCInt = new Vector<BigInteger>();
        blocLength = findBlocLength();
        genIV(blocLength);
        aVectorMStr = chopStringToAsciiBlocs(aString, blocLength, true);
        aVectorMInt = getBigIntVector(aVectorMStr);
        for (int i = 0; i < aVectorMInt.size(); i++) {          
            if (i == 0) {
                aVectorCInt.add(RSAEncrypt(aVectorMInt.elementAt(0).xor(IV)));
            } else {
                aVectorCInt.add(RSAEncrypt(aVectorMInt.elementAt(i).xor(aVectorCInt.elementAt(i - 1))));
            }          
        }
      
        aVectorCStr = getAsciiVector(aVectorCInt);
      
        for(int i = 0; i < aVectorCStr.size(); i++) {
            result += aVectorCStr.elementAt(i);
          
        }      
      
        return result;
    }
  
  
    public String RSADecryptBloc(String aString) {

        String result = "";
        Vector<String> aVectorCStr = new Vector<String>();
        Vector<String> aVectorMStr = new Vector<String>();
        Vector<BigInteger> aVectorCInt = new Vector<BigInteger>();
        Vector<BigInteger> aVectorMInt = new Vector<BigInteger>();
      
        aVectorCStr = chopStringToAsciiBlocs(aString, blocLength + 1, false);
        aVectorCInt = getBigIntVector(aVectorCStr);
        for (int i = 0; i < aVectorCInt.size(); i++) {
            if (i == 0) {
                aVectorMInt.add(RSADecrypt(aVectorCInt.elementAt(0)).xor(IV));
            } else {
                aVectorMInt.add(RSADecrypt(aVectorCInt.elementAt(i)).xor(aVectorCInt.elementAt(i - 1)) );
            }          
        }
        aVectorMStr = getAsciiVector(aVectorMInt);
        for (int i = 0; i < aVectorMStr.size(); i++) {      
            result += aVectorMStr.elementAt(i);
        }
        result = removePadding(result);
        return result;
    }
  
    public static Vector<String> getAsciiVector(Vector<BigInteger> aVectorInt) {
        Vector<String> aVectorStr = new Vector<String>();
        for (int i = 0; i < aVectorInt.size(); i++) {
            aVectorStr.add(convertBigIntegerToAsciiBlocBaseN(aVectorInt.elementAt(i)));
        }
      
        return aVectorStr;
    }
  
    public static String convertBigIntegerToAsciiBlocBaseN(BigInteger aBigInt) {
        String result = "";
        int t;
        Vector<Character> aCharVector = new Vector<Character>();
        BigInteger m = aBigInt;
      
        do {          
            t = m.mod(BigInteger.valueOf(ZN)).intValue();          
            m = m.divide(BigInteger.valueOf(ZN));
            char c = (char)t;          
            aCharVector.add(new Character(c));          
        }while (m.compareTo(BigInteger.ZERO) > 0);

        for (int i = 0; i < aCharVector.size(); i++ ) {
            result += aCharVector.elementAt(i);          
        }
        return result;
    }
  
    public static Vector<BigInteger> getBigIntVector(Vector<String> aVectorStr) {
        Vector<BigInteger> aVectorBigInt = new Vector<BigInteger>();
        for (int i = 0; i < aVectorStr.size(); i++) {
            aVectorBigInt.add(convertAsciiBloctToBigIntegerBaseN(aVectorStr.elementAt(i)));          
        }
        return aVectorBigInt;
    }
  
    public static BigInteger convertAsciiBloctToBigIntegerBaseN(String aString) {
        BigInteger result = BigInteger.ZERO;
        for (int i = 0; i < aString.length(); i++) {
            int n = (char)aString.charAt(i);
            result = result.add(BigInteger.valueOf(ZN).pow(i).multiply(BigInteger.valueOf(n)));
        }
        return result;
    }
  
  
    public static int findBlocLength() {
        int l = 0;
        BigInteger t = n;
      
        while(t.compareTo(BigInteger.valueOf(ZN)) > 0) {          
            t = t.subtract(t.remainder(BigInteger.valueOf(ZN)));
            t = t.divide(BigInteger.valueOf(ZN));              
            l++;          
        }
      
        return l;
    }  

  
    private static void generatePQ(Random aRand) {
        p = new BigInteger(MAX_BIT, MAX_TRY, aRand);
        do {
            q = new BigInteger(MAX_BIT, MAX_TRY, aRand);
        } while (q.compareTo(p) == 0);
        n = p.multiply(q);
        pn = (p.subtract(ONE)).multiply(q.subtract(ONE));
        //System.out.println("p: " + p.toString());  
        //System.out.println("q: " + q.toString());
        //System.out.println("n: " + n.toString());
        //System.out.println("pn: " + pn.toString());
    }
  
    private static void findED() {
        BigInteger aGCD;
        do {
            e = myBigRanNum(MAX_BIT);
            if (e.compareTo(pn) >= 0) e = e.mod(pn);
            aGCD = gcd(e, pn);
            //System.out.println("e: " + e.toString());          
        } while (e.compareTo(BigInteger.ZERO) == 0 || e.compareTo(BigInteger.ONE) == 0 || aGCD.compareTo(BigInteger.ONE) != 0);
        //System.out.println("e: " + e.toString());          

        d = ModInverse(e, pn);
        //d = e.modInverse(pn);
        //System.out.println("d: " + d.toString());
      
    }
  
    public static void genIV(int blocLength) {
        IV = new BigInteger(blocLength * CHR_SIZE, aRand);
    }  
  
  
      
    public static Vector<String> chopStringToAsciiBlocs(String aString, int blocLength, boolean padding) {
        Vector<String> aVectorStr = new Vector<String>();
        String tmp = aString;
        do {
            if (tmp.length() > blocLength) {
                String m = tmp.substring(0, blocLength);
                tmp = tmp.substring(blocLength);
                aVectorStr.add(m);
                //System.out.println("chop  > : " + m);
            } else if (tmp.length() == blocLength) {
                aVectorStr.add(tmp);
                //System.out.println("chop  = : " + tmp);
                if (padding) aVectorStr.add(addPadding("", blocLength));
                break;
            } else {
                //System.out.println("chop  < : " + tmp);
                if (padding) aVectorStr.add(addPadding(tmp, blocLength));
                break;
            }          
        } while (true);

        return aVectorStr;
    }
  
  

  
    public static String addPadding(String m, int l) {
        String result = m;
        int i = 0;
        do {
            result = result + myPadding.charAt(i);
            i++;
            if (i >= myPadding.length()) {
                i = 0;
            }
        } while (result.length() < l);
      
        return result;
    }  

    public static String removePadding(String aString) {
        String result = aString;
        String tmp = "";
        for (int i = 0; i < myPadding.length(); i++) {          
            tmp = myPadding.substring(0, myPadding.length() - 1 -i );          
            if (result.endsWith(tmp)) {              
                result = result.substring(0, result.indexOf(tmp));
                break;
            }
        }      
        return result;
    }
  
    public static BigInteger gcd(BigInteger x, BigInteger y) {
        BigInteger a = x;
        BigInteger b = y;
        while (b.compareTo(BigInteger.ZERO) != 0) {
            BigInteger t = b;
            b = a.mod(b);
            a = t;
        }
        return a;
    }
  
    public static BigInteger ModInverse(BigInteger mx, BigInteger my) {
        BigInteger a = mx;
        BigInteger b = my;      
        BigInteger x = BigInteger.ZERO;
        BigInteger y = BigInteger.ONE;
        BigInteger lx = BigInteger.ONE;
        BigInteger ly = BigInteger.ZERO;
      
        while (b.compareTo(BigInteger.ZERO) != 0) {
            //System.out.print(a.toString() + " " + b.toString() + " ");
            BigInteger t = b;          
            b = a.mod(b);
            BigInteger q = (a.subtract(b)).divide(t);
            //System.out.println(q.toString());
            a = t;
          
            t = x;
            x = lx.subtract(q.multiply(x));
            lx = t;
          
            t = y;
            y = ly.subtract(q.multiply(y));
            ly = t;
        }
        if (lx.compareTo(BigInteger.ZERO) < 0) lx = lx.add(my);
        return lx;
      
    }
  

 

    public static BigInteger myBigRanNum(int numBits) {
      
        //We only deal with positive number

    
        BigInteger aBigInterger = new BigInteger(numBits, aRand);
        aBigInterger = aBigInterger.abs();
        return aBigInterger;
    }



}