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

public class Practical10_crack {

	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 phi(BigInteger b) {
		
		BigInteger result = new BigInteger("1");
		BigInteger sum = new BigInteger("1");
		BigInteger phi_value = new BigInteger("1");
		
		for (Enumeration el=Practical10_crack.factors(b).elements(); el.hasMoreElements(); ) {
			
			BigInteger next_elm = new BigInteger("0");
			next_elm = (BigInteger)el.nextElement();

			sum = sum.multiply(next_elm);
			
			if (b.compareTo(next_elm) == 0) {
			
				result = b.subtract(BigInteger.ONE);
			
			} else {
				
				result = result.multiply(next_elm.subtract(BigInteger.ONE));
				
			}
				
		}

		return result;
		
	}	
		
	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 rsaDec(BigInteger n, BigInteger d, BigInteger c) {
		
		BigInteger rsaEnc_result = new BigInteger("0");
		
		rsaEnc_result = Practical10_crack.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] = Practical10_crack.rsaDec(n,decryption_exponent,ciphertext[ctr]);
			ctr++;
			
		}
		
		plaintext = intToString(Practical10_crack.combine(n,ciphertext));
		return plaintext;
		
	}
	
	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;
		
	}

	public static String crack(BigInteger modulus, BigInteger encryption_exponent, BigInteger ciphertext[]) {

		BigInteger d = new BigInteger("0");
		BigInteger phi_n = Practical10_crack.phi(modulus);
		String solution = new String();
		
		for (Enumeration el=Practical10_crack.factors(modulus).elements();el.hasMoreElements();) {
			
			System.out.println("Next element: "+el.nextElement());
			
		}
		
		System.out.println("Phi("+modulus+"): "+phi_n);
		
		try {
			
			d = Practical10_crack.invm(encryption_exponent,phi_n);
			System.out.println("d: "+d);
			
		} catch (Exception err) {
			
			System.out.println(err.toString());
			
		}
		
		solution = rsaDecString(modulus,d,ciphertext);
		
		return solution;
				
	}
	
	public static void main(String[] args) {

		/* 
		
		Example #1: Easy to crack
		
		n = 8362439
		e = 1671331
		Ciphertext = 
		     [6217797,2206158,423354,2665956,5598523,5217530,1127520,2506531,7248519,382110,5321279,
		        2149406,507477,4898734,2048783,5120500,3940266,1319683,1856979,1927864,5266180,6801466]
		
		*/
		
		BigInteger modulus_n = new BigInteger("8362439");
		BigInteger encryption_exponent_e = new BigInteger("1671331");
		BigInteger ciphertexts[] = new BigInteger[]{BigInteger.valueOf(6217797),BigInteger.valueOf(2206158),BigInteger.valueOf(423354),BigInteger.valueOf(2665956),BigInteger.valueOf(5598523),BigInteger.valueOf(5217530),BigInteger.valueOf(1127520),BigInteger.valueOf(2506531),BigInteger.valueOf(7248519),BigInteger.valueOf(382110),BigInteger.valueOf(5321279),BigInteger.valueOf(2149406),BigInteger.valueOf(507477),BigInteger.valueOf(4898734),BigInteger.valueOf(2048783),BigInteger.valueOf(5120500),BigInteger.valueOf(3940266),BigInteger.valueOf(1319683),BigInteger.valueOf(1856979),BigInteger.valueOf(1927864),BigInteger.valueOf(5266180),BigInteger.valueOf(6801466)};

		/*
		 
		 Example #1: Hard to crack 
		    
         n = 64672532814626273
         e = 12934505012034817
         Ciphertext = 
         [56144801887478888,61097986519868295,6780549238735883,60586531897247565,
         57788659969954080,18315856717632076,23449925800511814,145]
		
		BigInteger modulus_n = new BigInteger("64672532814626273");
		BigInteger encryption_exponent_e = new BigInteger("12934505012034817");
		BigInteger ciphertexts[] = new BigInteger[]{new BigInteger("56144801887478888"),new BigInteger("61097986519868295"),new BigInteger("6780549238735883"),new BigInteger("60586531897247565"),new BigInteger("57788659969954080"),new BigInteger("18315856717632076"),new BigInteger("23449925800511814"),new BigInteger("145")};		

		*/

		System.out.println("Cracking: "+Practical10_crack.crack(modulus_n,encryption_exponent_e,ciphertexts));
		
	}
	
	
}