import static java.lang.Math.*;
import java.util.Random;
import java.io.Console;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
import java.math.*;
import java.math.BigInteger;
public class RSA3
{
	//String in ein char array
	static char[]  auslesen(String str)
	{
		char temp [] = new char[str.length()];
		for(int i = str.length()-1; i >= 0; --i)
		{
			temp[i] = str.charAt(i);
		}
		return temp;
	}

	// groesster gemeinsamer Teiler
	public static BigInteger gcd(BigInteger a, BigInteger b)
	{
		if (a.compareTo(b) < 0)
		{
			BigInteger tmp = a;
			a=b;
			b=tmp;
		}

		BigInteger r = a.mod(b);

		while (r.compareTo(new BigInteger("0")) != 0)
		{
			a=b;
			b=r;
			r = a.mod(b);
		}
		return b;
	}

	// Erzeugt eine "große" Primezahl  die 200 steht fuer die bitlaenge
	static BigInteger PrimezahlGenerator()
	{
		BigInteger maxP = BigInteger.probablePrime(1500, new Random());
		return maxP;
	}

	static BigInteger BestimmungVon_E(BigInteger n)
	{
		BigInteger temp = new BigInteger("0");
		BigInteger tempres = new BigInteger("0");
		BigInteger i = new BigInteger("2");
		boolean isPrime = false;
		while(i.compareTo(n) < 0)
		{
			isPrime = i.isProbablePrime(1);
			tempres = n.remainder(i);
			if(tempres.compareTo(temp) != 0 && isPrime)
			{
				return i;
			}
			i = i.add(new BigInteger("1"));
		}
		return new BigInteger("1");
	}

	static BigInteger CharinInt(char[] text)
	{
		BigInteger wert = new BigInteger("0");
		char arrAlp[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
		for(int i = 0; i < text.length; ++i)
		{
			for(int k = 0; k < arrAlp.length; ++k)
			{
				if(Character.compare(text[i], arrAlp[k]) == 0)
				{
					if(i == 0)
					{
						BigInteger temp = BigInteger.valueOf(k);
						wert = wert.add(new BigInteger("1").add(temp));
					}
					else
					{
						BigInteger temp = BigInteger.valueOf(k);
						temp = temp.add(new BigInteger("1"));
						wert = wert.add(temp.multiply(new BigInteger("26").pow(i)));
					}
				}
			}
		}
		return wert;
	}

	static char intToChar(BigInteger n)
	{
		int temp = n.intValue();
		char arrAlp[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
		return arrAlp[temp];
	}

	static char[] UmwandlerOhneLaenge(BigInteger Eingabe)
	{
		List<BigInteger> Umw = new ArrayList<BigInteger>();
		int i = 0;
		while(true)
		{
			BigInteger Rest = Eingabe.mod(new BigInteger("26"));;
			Eingabe= Eingabe.subtract(Rest);
			Eingabe = Eingabe.divide(new BigInteger("26"));
			Umw.add(i, Rest);
			++i;
			if(Eingabe.mod(new BigInteger("26")).compareTo(new BigInteger("0")) == 0) //  Eingabe % 26 == 0
			{
				Umw.add(i, Eingabe.mod(new BigInteger("26")));
				break;
			}
		}
		char temp[] = new char [Umw.size()];

		for(int k = 0; k < temp.length-1; ++k)
		{
			temp[k] = intToChar((Umw.get(k)).subtract(new BigInteger("1")));
		}
		return temp;
	}

	static BigInteger SMohneAusgabe(BigInteger base, BigInteger exp, BigInteger mod)
	{
		BigInteger a = base;

		BigInteger n = mod;

		BigInteger z = new BigInteger("0");

		BigInteger temp = new BigInteger("2");

		BigInteger[] b = intToBinaryRightOrder(exp);
		int len = b.length;
		if(b[len - 1].compareTo(new BigInteger("1")) == 0)
			z = a.mod(n);
		else
			z = BigInteger.valueOf(1);
		for(int i = b.length-2; i >= 0; --i)
		{
			a = a.modPow(temp, n);
			if(b[i].compareTo(new BigInteger("1")) == 0)
			{
				z = z.multiply(a);
				z = z.mod(n);
			}
		}
		return z;
	}

	static BigInteger[] intToBinaryRightOrder(BigInteger num)
	{
		List<BigInteger> arr = new ArrayList<BigInteger>();
		while(num.compareTo(new BigInteger("0")) > 0)
		{
			arr.add(num.mod(new BigInteger("2")));
			num = num.divide(new BigInteger("2"));
		}
		Collections.reverse(arr);
		BigInteger res[] = new BigInteger[arr.size()];
		for(int i = 0; i < res.length; ++i)
		{
			res[i] = arr.get(i);
		}
		return res;
	}

	static BigInteger[] intToBinary(BigInteger num)
	{
		List<BigInteger> arr = new ArrayList<BigInteger>();
		while(num.compareTo(new BigInteger("0")) > 0)
		{
			arr.add(num.mod(new BigInteger("2")));
			num = num.divide(new BigInteger("2"));
		}
		BigInteger res[] = new BigInteger[arr.size()];
		for(int i = 0; i < res.length; ++i)
		{
			res[i] = arr.get(i);
		}
		return res;
	}

	static BigInteger[] RSA_public()
	{
		BigInteger[] arr = new BigInteger[3];
		BigInteger temp = new BigInteger("1");
		BigInteger p = PrimezahlGenerator();
		BigInteger q = PrimezahlGenerator();
		BigInteger N = p.multiply(q);
		BigInteger N_0 = (p.subtract(temp)).multiply((q.subtract(temp)));
		BigInteger e = BestimmungVon_E(N_0);
		arr[0] = e;
		arr[1] = N;
		arr[2] = N_0;
		System.out.println("p:"+ p);
		System.out.println("q:" + q);
		System.out.println("n:" + N);
		System.out.println("e:" + e);
		System.out.println("phiN:" + N_0);
		return arr;
	}

	static BigInteger RSA_private(BigInteger phiN, BigInteger e)
	{
		BigInteger a,b,q,s,r,t,u,v,d;
		a = phiN;
		b = e;
		u = BigInteger.valueOf(1);
		t = BigInteger.valueOf(1);
		v = BigInteger.valueOf(0);
		s = BigInteger.valueOf(0);
		while(b.compareTo(new BigInteger("0"))>0)
		{
			q = a.divide(b);
			r = a.mod(b);
			a = b;
			b = r;

			r = u.subtract(q.multiply(s));
			u = s;
			s = r;

			r = v.subtract(q.multiply(t));
			v = t;
			t = r;
		}

		if(v.compareTo(new BigInteger("0")) < 0)
		{
			v = v.add(phiN);
		}
		d = v;
		return d;
	}

	static BigInteger verschlusseln(char[] Nachricht, BigInteger[] publicKey)
	{
		BigInteger x = CharinInt(Nachricht);
		BigInteger y = SMohneAusgabe(x, publicKey[0], publicKey[1]);
		System.out.println("Verschlusselt  : " + y);
		return y;
	}
	static BigInteger test;
	static char[] entschlusseln(BigInteger y, BigInteger[] privateKey)
	{
		BigInteger x = SMohneAusgabe(y, privateKey[0], privateKey[1]);
		test = x;
		System.out.println("Entschluesselt  : " + x);
		char text[] = UmwandlerOhneLaenge(x);
		return text;
	}

	static String start(String Nachricht)
	{
		BigInteger[] test2 = new BigInteger[2];
		char nachricht[] = auslesen(Nachricht);
		BigInteger publicKey[] = RSA_public(); // return Werte =>  e ,   N ,   N_0(phiN)  // [0] = e, [1] = N, [2] = phiN
		BigInteger privateKey[] = new BigInteger[2]; // [0] = d,  [1] = N
		privateKey[0] = RSA_private(publicKey[2], publicKey[0]);
		privateKey[1] = publicKey[1];
		// Beide Keys fertig und Nachricht in einem Char array

		BigInteger geheimText = verschlusseln(nachricht, publicKey);
		test2[0] = geheimText;
		char[] klarText = entschlusseln(geheimText, privateKey);
		test2[1] = test;
		String KlarTextString = new String(klarText);
		System.out.println("Entschlusselter Text " + KlarTextString);
		if(test2[0].compareTo(test2[1]) == 0)
		{
			System.out.println("true");
		}
		return KlarTextString;
	}

	static String Texter(int max)
	{
		Random rnd = new Random();
		char temp[] = new char[max];
		char arrAlp[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
		for(int i = 0; i < max; ++i)
		{
			int asd = 1 + rnd.nextInt(26);
			temp[i] = arrAlp[asd-1];
		}
		String wort = new String(temp);
		return wort;
	}

	public static void main(String[] args)
	{
		start("abcdefghijklmnopqrstuvwxy");
	}
}