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

public class Practical15_ecrack {

	//	 f(x) = x^2+y (y is some random small integer) 
	public static BigInteger function_x(BigInteger initval, BigInteger modulus) {
		
		int size = 4;
		//BigInteger rand_y = new BigInteger(size, new SecureRandom());
		BigInteger result = new BigInteger("0");
		BigInteger rand_y = new BigInteger("23");
		
		//System.out.println("Y: "+rand_y);
		result = initval.multiply(initval).add(rand_y).mod(modulus);
			
		return result;
		
	}

	// This method actually implements the extended gcd but we just gonna
	// use its first return value which is the gcd(a,b)
	public static BigInteger[] gcd(BigInteger a, BigInteger b) {
	
			Vector myvector = new Vector();
			
			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;
			
			if (b.compareTo(BigInteger.ZERO) >= 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;
				
				q = c;
				r = a;
	
				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);
				
				mr_x = s;
				mr_y = t;
				
			} else {
				
				myvector.add(BigInteger.ONE);
				myvector.add(BigInteger.ZERO);
				myvector.add(BigInteger.ZERO);
				
			}
			
			myvector.add(gcd_a_b);
			myvector.add(mr_x);
			myvector.add(mr_y);
		
			//return myvector;
			return (BigInteger[]) myvector.toArray(new BigInteger[] {});		
			
	}
	
	//public static BigInteger[] efactors(BigInteger number) {
	public static Vector efactors(BigInteger number) {
		
		BigInteger startval = new BigInteger(number.bitLength(), new SecureRandom());
		Vector myvector = new Vector();
		BigInteger a = new BigInteger("0");
		BigInteger b = new BigInteger("0");
		BigInteger result = new BigInteger("0");
		BigInteger z = new BigInteger("431");
		boolean has_factors = false;
		
		if (startval.equals(BigInteger.ZERO)) return Practical15_ecrack.efactors(number);

		a = Practical15_ecrack.function_x(startval,number);
		b = Practical15_ecrack.function_x(startval,number);
		b = Practical15_ecrack.function_x(b,number).mod(number);

		//System.out.println("startval: "+startval);
		//System.out.println("a : "+a);
		//System.out.println("b : "+b);
		//System.out.println("gcd(a-b,n): "+Practical15_ecrack.gcd(number,a.subtract(b))[0]);
		//System.out.println("--------------------------------------------------------------");
		
		while (Practical15_ecrack.gcd(number,a.subtract(b))[0].compareTo(BigInteger.ONE) == 0) {
		
			a = Practical15_ecrack.function_x(a,number);
			b = Practical15_ecrack.function_x(b,number);
			b = Practical15_ecrack.function_x(b,number).mod(number);
			//System.out.println("startval: "+startval);
			//System.out.println("a : "+a);
			//System.out.println("b : "+b);
			//System.out.println("gcd("+number+","+a+"-"+b+"): "+Practical15_ecrack.gcd(number,a.subtract(b))[0]);
			//System.out.println("--------------------------------------------------------------");

		}	
			
		myvector.add(Practical15_ecrack.gcd(number,a.subtract(b))[0]);
		myvector.add(number.divide(Practical15_ecrack.gcd(number,a.subtract(b))[0]));
		
		return myvector;
		
	}
	
	
	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=Practical15_ecrack.efactors(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 = Practical15_ecrack.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] = Practical15_ecrack.rsaDec(n,decryption_exponent,ciphertext[ctr]);
				ctr++;
				
			}
			
			plaintext = intToString(Practical15_ecrack.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 ecrack(BigInteger modulus, BigInteger encryption_exponent, BigInteger ciphertext[]) {

			BigInteger d = new BigInteger("0");
			BigInteger phi_n = Practical15_ecrack.phi(modulus);
			String solution = new String();
			
			for (Enumeration el=Practical15_ecrack.efactors(modulus).elements();el.hasMoreElements();) {
				
				System.out.println("Next element: "+el.nextElement());
				
			}
			
			System.out.println("Phi("+modulus+"): "+phi_n);
			
			try {
				
				d = Practical15_ecrack.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) {

		BigInteger n = new BigInteger("54975961");
		BigInteger e = new BigInteger("5");
		BigInteger ciphertext[] = new BigInteger[]{new BigInteger("22433065"),new BigInteger("53691448"),new BigInteger("52735311"),new BigInteger("14193623"),new BigInteger("47110365"),new BigInteger("6155548"),new BigInteger("11408900"),new BigInteger("14065766"),new BigInteger("13766275"),new BigInteger("14779769"),new BigInteger("25149546"),new BigInteger("26261783"),new BigInteger("49285203"),new BigInteger("16585668"),new BigInteger("10368039"),new BigInteger("19137335"),new BigInteger("47975194"),new BigInteger("39458087"),new BigInteger("43918933")};

		System.out.println("Cracking: "+Practical15_ecrack.ecrack(n,e,ciphertext));
		
	}

}