import java.math.BigInteger;
import java.util.Enumeration;
import java.security.*;
import java.util.Vector;

public class Practical9_RSA {

	public static Vector factors(BigInteger a) {
		
		BigInteger ctr = new BigInteger("2");
		BigInteger two = new BigInteger("2");
		
		Vector myfactors = new Vector();
		
		// -1 numerisch kleiner, 0 gleich, 1 groesser
		while (ctr.compareTo(a) <= 0) {

			//System.out.print(" Ctr: "+ctr);
			//System.out.print(" a: "+a);
			//System.out.println(" a mod ctr: "+a.mod(ctr));
			
			if (a.mod(ctr).compareTo(BigInteger.ZERO) == 0) {
				
				a = a.divide(ctr);
				myfactors.add(ctr);
				ctr = two;
				
			} else {
				
				ctr = ctr.add(BigInteger.ONE);
				
			}
			
			
						
		}		
			
		return myfactors;
				
	}
	
	public static BigInteger genprime(int size) {

		BigInteger number = new BigInteger(size,new SecureRandom());
		
		BigInteger x = (BigInteger)Practical9_RSA.factors(number).elementAt(0);
		
		if (number.compareTo(x) == 1) {
					
			return Practical9_RSA.genprime(size);
					
		}
				
		return number;

	}

	public static BigInteger gcd(BigInteger a, BigInteger b) {
		
			BigInteger c = new BigInteger("0");
			BigInteger d = new BigInteger("0");
			BigInteger gcd_a_b = new BigInteger("0");
		
			BigInteger q = new BigInteger("0");
			BigInteger r = new BigInteger("0");
			BigInteger s = new BigInteger("0");
			BigInteger t = new BigInteger("0");

			BigInteger previous_q = new BigInteger("0");
			BigInteger previous_s = new BigInteger("0");
			BigInteger previous_previous_s = new BigInteger("0");
			BigInteger previous_t = new BigInteger("0");
			BigInteger previous_previous_t = new BigInteger("0");
			BigInteger minus_one = new BigInteger("-1");
			
			BigInteger mr_x = new BigInteger("0");
			BigInteger mr_y = new BigInteger("0");
			
			int ctr = 0;
			
			do {
				
				if (ctr == 0) {
					
					s = BigInteger.ONE;
					t = BigInteger.ZERO;
				
				}

				if (ctr == 1) {
					
					s = BigInteger.ZERO;
					t = BigInteger.ONE;
				
				}
				
				if (ctr > 1) {
					
					s = minus_one.multiply(previous_q);
					s = s.multiply(previous_s);
					s = s.add(previous_previous_s);

					t = minus_one.multiply(previous_q);
					t = t.multiply(previous_t);
					t = t.add(previous_previous_t);

				}

				q = c;
							
				c = a.divide(b);
				d = a.subtract(b.multiply(c));

				r = a;
				
				a = b;
				b = d;
				ctr++;
				previous_q = q;
				previous_previous_s = previous_s;
				previous_s = s;
				previous_previous_t = previous_t;
				previous_t = t;

			} while (d.compareTo(BigInteger.ZERO) == 1);
			
			gcd_a_b = a;

			//System.out.println("gcd: "+gcd_a_b);
			
			return gcd_a_b;
					
			
	}
	
	public static BigInteger gen_e(int size,BigInteger phi_n) {

		BigInteger e = new BigInteger("0");
			
		e = Practical9_RSA.genprime(size);
		
		//System.out.println("E: "+e);
		
		if (e.compareTo(phi_n) > -1) {
					
			return Practical9_RSA.gen_e(size,phi_n);
					
		}
		
		// 1 < e < phi(n)
		
		if (Practical9_RSA.gcd(e,phi_n).compareTo(BigInteger.ONE) != 0) {
			
			return Practical9_RSA.gen_e(size,phi_n);
			
		}
		
		// 1 < e < phi(n) && gcd(e,phi_n) = 1
		
		return e;

	}
	
	public static BigInteger invm(BigInteger a, BigInteger modulus) throws Exception {
		
		BigInteger b = new BigInteger("0");
		BigInteger c = new BigInteger("0");
		BigInteger d = new BigInteger("0");

		BigInteger q = new BigInteger("0");
		BigInteger r = new BigInteger("0");
		BigInteger s = new BigInteger("0");
		BigInteger t = new BigInteger("0");

		BigInteger initial_a = new BigInteger("0");
		BigInteger initial_modulus = new BigInteger("0");
	
		BigInteger inverse = new BigInteger("0");
	
		BigInteger previous_d = new BigInteger("0");
		BigInteger previous_previous_d = new BigInteger("0");

		BigInteger previous_c = new BigInteger("0");
		BigInteger previous_q = new BigInteger("0");
		
		BigInteger previous_s = new BigInteger("0");
		BigInteger previous_previous_s = new BigInteger("0");

		BigInteger previous_t = new BigInteger("0");
		BigInteger previous_previous_t = new BigInteger("0");
		
		BigInteger minus_one = new BigInteger("-1");
		
		BigInteger result = new BigInteger("0");
		
		initial_a = a;
		initial_modulus = modulus;

		int ctr = 0;

		b = modulus;
		
		//System.out.println("a	b	c	d	q	r	s	t");
		
		do {
			
			if (ctr == 0) {

				// Output a,b
				//	System.out.print(b);
				//System.out.print("	");
				//	System.out.print(a);
				//System.out.print("	");

				c = b.divide(a);
				d = b.subtract(a.multiply(c));
				b = d;
		
				q = BigInteger.ZERO;
				r = modulus;
				s = BigInteger.ONE;
				t = BigInteger.ZERO;
				
				previous_c = c;
				previous_s = s;
				previous_previous_s = previous_s;

				previous_t = t;
				previous_previous_t = previous_t;

			} 
			
			if (ctr == 1) { 
				
				// Output a,b
				//System.out.print(a);
				//System.out.print("	");
				//System.out.print(b);
				//System.out.print("	");
				s = BigInteger.ZERO;
				t = BigInteger.ONE;

				r = a;
				
				c = a.divide(b);
				d = a.subtract(b.multiply(c));
				a = b;
				b = d;
				
				q = previous_c;
				
				previous_d = d;
				previous_previous_d = previous_d;

				previous_c = c;
				previous_previous_s = previous_s;
				previous_s = s;

				previous_previous_t = previous_t;
				previous_t = t;
				previous_q = q;
				
			}
			
			if (ctr > 1) {

				// Output a,b
				//System.out.print(a);
				//System.out.print("	");
				//System.out.print(b);
				//System.out.print("	");

				r = a;

				previous_d = d;
				previous_previous_d = previous_d;
					
				c = a.divide(b);
				d = a.subtract(b.multiply(c));
				a = b;
				b = d;

				q = previous_c;
				
				s = minus_one.multiply(previous_q).multiply(previous_s).add(previous_previous_s);
				t = minus_one.multiply(previous_q).multiply(previous_t).add(previous_previous_t);
				previous_q = q;
				previous_previous_s = previous_s;
				previous_s = s;
				previous_previous_t = previous_t;
				previous_t = t;
				previous_c = c;
				
			}
			
			// Output c,d
			//	System.out.print(c);
			//System.out.print("	");
			//System.out.print(d);
			//System.out.print("	");

			// Output q,r,s,t
			//System.out.print(q);
			//System.out.print("	");
			//System.out.print(r);
			//System.out.print("	");
			//System.out.print(s);
			//System.out.print("	");
			//	System.out.print(t);
			//System.out.println("	");

			ctr++;
			
		} while (d.compareTo(BigInteger.ZERO) == 1);

		q = previous_d;
		r = BigInteger.ZERO;
		
		s = minus_one.multiply(previous_q).multiply(previous_s).add(previous_previous_s);
		t = minus_one.multiply(previous_q).multiply(previous_t).add(previous_previous_t);
				
		// Output q,r,s,t
		//System.out.print(" 				");
		//System.out.print(q);
		//System.out.print("	");
		//System.out.print(r);
		//System.out.print("	");
		//System.out.print(s);
		//System.out.print("	");
		//System.out.print(t);
		//System.out.println("	");

		// Is s<0 ?
		while (s.compareTo(BigInteger.ZERO) == -1) {
			
			s = s.add(initial_modulus);
						
		}
		
		// Is t<0 ?
		while (t.compareTo(BigInteger.ZERO) == -1) {
			
			t = t.add(initial_modulus);
						
		}
		
		if (s.multiply(initial_a).mod(initial_modulus).compareTo(BigInteger.ONE) == 0) {
			
			result = s; 
		
		}
		
		if (t.multiply(initial_a).mod(initial_modulus).compareTo(BigInteger.ONE) == 0) {
			
			result = t; 
		
		}
		
		return result;
		
	}
	
	// 	rsakey(p,q) -> e,d (e = public key, d = private)
	// public key = (n,e)
	// private key = (n,d)
	
	//public static BigInteger[] rsakey(BigInteger p, BigInteger q) {
	public static Vector rsakey(BigInteger p, BigInteger q) {
	
		int size = 8;
		
		Vector rsakey_result = new Vector();
		BigInteger n = new BigInteger("0");
		BigInteger phi_n = new BigInteger("0");
		BigInteger e = new BigInteger("0");
		BigInteger d = new BigInteger("0");
		
		n = p.multiply(q);

		phi_n = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
		
		System.out.println("Phi_n (rsakey): "+phi_n);
		
		e = gen_e(size+4,phi_n);
	
		System.out.println("e (rsakey): "+e);
				
		try {
			
			d = Practical9_RSA.invm(e,phi_n);
			
		} catch (Exception err) {
			
			System.out.println(err.toString());
			
		}
		
		rsakey_result.add(e);
		rsakey_result.add(d);
		
		return rsakey_result;
		//return (BigInteger[]) rsakey_result.toArray(new BigInteger[] {});
		
	}
	
	public static BigInteger expm(BigInteger m, BigInteger a, BigInteger b) {

		BigInteger result = new BigInteger("1");
		BigInteger zwei = new BigInteger("2");
		BigInteger base = new BigInteger("0");
		
		base = a;
		
		while (b.compareTo(BigInteger.ONE) == 1) {
			
			if (b.mod(zwei).compareTo(BigInteger.ONE) == 0) {
				
				result = result.multiply(base);
				base = base.multiply(base).mod(m);
				
			} else {

				base = base.multiply(base).mod(m);
				
			}
			
			b = b.divide(zwei); 
						
		}
		
		if (b.mod(zwei).compareTo(BigInteger.ONE) == 0) {
			
			//result = result.multiply(base);
			result = result.multiply(base).mod(m);
			base = base.multiply(base).mod(m);
			
		} else {

			base = base.multiply(base).mod(m);
			
		}

		return result;
			
	}
	
	public static BigInteger rsaEnc(BigInteger n, BigInteger e, BigInteger m) {
		
		BigInteger rsaEnc_result = new BigInteger("0");
		
		rsaEnc_result = Practical9_RSA.expm(n,m,e);
		
		return rsaEnc_result;
		
	}

	public static BigInteger rsaDec(BigInteger n, BigInteger d, BigInteger c) {
		
		BigInteger rsaEnc_result = new BigInteger("0");
		
		rsaEnc_result = Practical9_RSA.expm(n,c,d);
		
		return rsaEnc_result;
		
	}

	public static BigInteger stringToInt(String str) { 
		
		BigInteger retvalint = new BigInteger(str.getBytes()); 
        return retvalint;
   
	}

	public static String intToString(BigInteger bi) {
    
		String retvalstr = new String(bi.toByteArray());
		return retvalstr;
   
	}
	
	public static BigInteger combine(BigInteger m, BigInteger[] x) {
		
		BigInteger result = new BigInteger("0");
		
		for (int i=x.length-1; i >= 0; i--) {
			
			result = result.multiply(m).add(x[i]); 
						
		}
		
		return result;
		
	}
	
	public static String rsaDecString(BigInteger n,BigInteger decryption_exponent,BigInteger ciphertext[]) {
		
		String plaintext = new String();
		int ctr = 0;
		
		while (ctr < ciphertext.length) {
			
			ciphertext[ctr] = Practical9_RSA.rsaDec(n,decryption_exponent,ciphertext[ctr]);
			ctr++;
			
		}
		
		plaintext = intToString(Practical9_RSA.combine(n,ciphertext));
		return plaintext;
		
	}
	
	public static Vector split(BigInteger m, BigInteger x) {
		
		Vector myvector = new Vector();
		
		while (x.compareTo(m) >= 0) {
				
			myvector.add(x.mod(m));
			
			x = x.divide(m);
		
		}
		
		myvector.add(x);

		return myvector;
				
	}
	
	//public static BigInteger[] rsaEncString(BigInteger n,BigInteger encryption_exponent,String message) {
	public static Vector rsaEncString(BigInteger n,BigInteger encryption_exponent,String message) {
	
		Vector ciphertext_in = Practical9_RSA.split(n,stringToInt(message));
		Vector ciphertext_out = new Vector();

		for (Enumeration el=ciphertext_in.elements(); el.hasMoreElements(); ) {
			
			ciphertext_out.add(rsaEnc(n,encryption_exponent,(BigInteger)el.nextElement()));
			
		}
			
		return ciphertext_out;
		//return (BigInteger[]) ciphertext_out.toArray(new BigInteger[] {});
		
	}
	
	private static String formatArray(BigInteger x[]) { 
        String retval = ""; 
    
	    for (int i = 0; i < x.length; i++) {
	    	
             if (i > 0) retval += ", ";
             retval += x[i].toString();
        
	    }
        
	    return "[" + retval + "]";
   
	}
	
	public static void main(String[] args) {

		int size = 8;
		
		/*
		BigInteger p = genprime(size);
		BigInteger q = genprime(size);
		BigInteger n = new BigInteger("0");
		BigInteger phi_n = new BigInteger("0");
		BigInteger e = new BigInteger("0");
		BigInteger d = new BigInteger("0");
		
		BigInteger m = new BigInteger("5000");
		*/		
			
		// D. Gray's test cases
		
		// #1
		// Assuming that rsaKey(27941,22283) yields (e,d), then e*d mod 622559080 should equal 1
		BigInteger val1 = new BigInteger("27941");
		BigInteger val2 = new BigInteger("22283");
		BigInteger modulus = new BigInteger("622559080");
		
		BigInteger rsakey_result1 = new BigInteger("0");
		BigInteger rsakey_result2 = new BigInteger("0");
		
		Vector x = Practical9_RSA.rsakey(val1,val2);
		rsakey_result1 = (BigInteger)x.get(0); 
		rsakey_result2 = (BigInteger)x.get(1);
		
		BigInteger testcase1_result = new BigInteger("0");
		
		testcase1_result = rsakey_result1.multiply(rsakey_result2);
		testcase1_result = testcase1_result.mod(modulus);
		
		System.out.println("rsakey(27941,22283): "+rsakey_result1+" "+rsakey_result2);
		System.out.println("rsakey(27941,22283) mod "+modulus+": "+testcase1_result);
		// Test #1 works!
		
		System.out.println("-------------------------------------------------");
				
		// Test # 2
		// rsaEnc(622609303,3,543) = 160103007
		// rsaEnc(BigInteger n, BigInteger e, BigInteger m)
		BigInteger testcase2_n = new BigInteger("622609303");
		BigInteger testcase2_e = new BigInteger("3");
		BigInteger testcase2_m = new BigInteger("543");
		System.out.println("rsaEnc(622609303,3,543): "+Practical9_RSA.rsaEnc(testcase2_n,testcase2_e,testcase2_m));
		// Test #2 works!
		
		System.out.println("-------------------------------------------------");
		
		// Test # 3
		// rsaDec(622609303,415039387,160103007) = 543
		// rsaDec(BigInteger n, BigInteger d, BigInteger c)
		BigInteger testcase3_n = new BigInteger("622609303");
		BigInteger testcase3_d = new BigInteger("415039387");
		BigInteger testcase3_c = new BigInteger("160103007");
		System.out.println("rsaDec(622609303,415039387,160103007): "+Practical9_RSA.rsaDec(testcase3_n,testcase3_d,testcase3_c));
		// Test #3 works!

		System.out.println("-------------------------------------------------");
		
 		// Test # 4
		// rsaEncString(622609303,3,"Hello.") = [560315684,483365789]
		// rsaEncString(BigInteger n,BigInteger encryption_exponent,String message)
		BigInteger testcase4_n = new BigInteger("622609303");
		BigInteger testcase4_e = new BigInteger("3");
		String testcase4_c = new String("Hello.");
		System.out.println("rsaEncString(622609303,3,\"Hello.\"): "+Practical9_RSA.rsaEncString(testcase4_n,testcase4_e,testcase4_c));
		// Test #4 works!
		
		System.out.println("-------------------------------------------------");
		
		// Test # 5
		// rsaDecString(622609303,415039387,[560315684,483365789]) = "Hello."
		// rsaDecString(BigInteger n,BigInteger decryption_exponent,BigInteger ciphertext[]) 
		BigInteger testcase5_n = new BigInteger("622609303");
		BigInteger testcase5_d = new BigInteger("415039387");
		BigInteger testcase5_c[] = new BigInteger[] {BigInteger.valueOf(560315684),BigInteger.valueOf(483365789)};
		System.out.println("rsaDecString(622609303,415039387,[560315684,483365789]): "+Practical9_RSA.rsaDecString(testcase5_n,testcase5_d,testcase5_c));
		// Test #5 works!
		
		System.out.println("-------------------------------------------------");
		
		// Test # 6
		// rsaDecString(622609303,415039387,[244753217,613613369,415120695,355142652,134856040,478060706,331972076,532347366,600207262]) = "The camera is a kind of licence."
		// rsaDecString(BigInteger n,BigInteger decryption_exponent,BigInteger ciphertext[]) 
		BigInteger testcase6_n = new BigInteger("622609303");
		BigInteger testcase6_d = new BigInteger("415039387");
		BigInteger testcase6_c[] = new BigInteger[] {BigInteger.valueOf(244753217),BigInteger.valueOf(613613369),BigInteger.valueOf(415120695),BigInteger.valueOf(355142652),BigInteger.valueOf(134856040),BigInteger.valueOf(478060706),BigInteger.valueOf(331972076),BigInteger.valueOf(532347366),BigInteger.valueOf(600207262)};
		System.out.println("rsaDecString(622609303,415039387,[244753217,613613369,415120695,355142652,134856040,478060706,331972076,532347366,600207262]): "+Practical9_RSA.rsaDecString(testcase6_n,testcase6_d,testcase6_c));
		// Test #6 works!
		
	}

}