KRY-0x04/Rsa.cs

using System;
using System.Drawing;
using System.Numerics;
using System.Security.Cryptography;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.Threading;
using System.Text.RegularExpressions;
using System.IO;

namespace KRY_0x04
{
	class Rsa
	{
		private RandomNumberGenerator rng = new RNGCryptoServiceProvider();
		private static int block_size = ((Convert.ToInt32(key_size.b1024) * 2) / 8) - 1;
		private static int b1024 = Convert.ToInt32(key_size.b1024); //512b primes
		private static int b2048 = Convert.ToInt32(key_size.b2048);
		private static int b3072 = Convert.ToInt32(key_size.b3072);
		private static int b4096 = Convert.ToInt32(key_size.b4096);
		private static int randbytesize = 0;
		private static BigInteger P = 0;
		private static BigInteger Q = 0;
		private static BigInteger E = 0;
		private static BigInteger D = 0;
		private static BigInteger N = 0;
		private static bool isprime_p, isprime_q;
		private static int candidates_tried;
		private static DateTime gp_start, gp_finish;
		private static int numThreads = 3;
		private int custom_threads = 0;

		enum key_size : uint
		{
			b1024 = 512,
			b2048 = 1024,
			b3072 = 1536,
			b4096 = 2048,
		}

		private void gen_primes()
		{
			if (randbytesize == 0)
			{
				randbytesize = b1024; // default to something
			}

			int min_checks = mr_min_checks(randbytesize * 2);
			byte[] random = new byte[randbytesize];
			BigInteger rand_int = 0;
			candidates_tried = 0;
			isprime_p = false;
			isprime_q = false;

			while (!isprime_p || !isprime_q)
			{
				/* P(isprime(2^randbytesize)) == 2/(randbytesize*ln(2)) */
				candidates_tried++;
				rng.GetBytes(random);
				rand_int = new BigInteger(random);
				if (rand_int.IsEven || rand_int < 2) { continue; }
				if (!is_huge_prime(rand_int, min_checks))
				{
					Console.WriteLine($"[*] rand_int is not a_prime! (tried: {candidates_tried}:\n{rand_int})");
					continue;
				}
				Console.WriteLine($"[*] rand_int: {rand_int} \tis a prime!\n");
				if (P != 0)
				{
					if (rand_int != P)
					{
						Rsa qq = new Rsa();
						lock (qq)
						{
							Q = rand_int;
							isprime_q = true;
						}
						Console.WriteLine("[*] found q!\n");
						break;
					}
					Console.WriteLine("\n[!] q cannot equal p");
					continue;
				}

				Rsa pp = new Rsa();
				lock (pp)
				{
					P = rand_int;
					isprime_p = true;
				}
				Console.WriteLine("[*] found p!\n");
			}
		}

		private static int mr_min_checks(int bits)
		{
			if (bits > 2048)
				return 128;
			return 64;
		}

		private static int[] low_primes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
				101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
				181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269,
				271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367,
				373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461,
				463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571,
				577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,
				673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773,
				787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,
				887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};

		private bool is_huge_prime(BigInteger source, int mr_min_rounds)
		{
			for (int i = 0; i < low_primes.Length; i++)
			{
				if (source % low_primes[i] == 0)
				{
					return false;
				}
			}

			BigInteger r = source - BigInteger.One;
			int s = 0;

			//while (r % 2 == BigInteger.Zero)
			while (0 == (r & 1))
			{
				r /= 2;
				s += 1;
			}

			byte[] bytes = new byte[source.ToByteArray().LongLength];
			BigInteger a = BigInteger.Zero;

			/* Miller–Rabin test composite detection probability: 75% (each round)
			 * i.e. test false negative probability: 4^-n per round
			 * 64 rounds --> undetected composite probability: 2^-128
			 */
			for (int i = 0; i < mr_min_rounds; i++)
			{
				while (a < 2 || a >= source - 2)
				{
					rng.GetBytes(bytes);
					a = new BigInteger(bytes);
				}

				BigInteger x = BigInteger.ModPow(a, r, source);
				if (x != BigInteger.One)
				{
					int xy = 0;
					while (x != source - 1)
					{
						if (xy == s - 1)
						{
							return false;
						}
						xy++;
						x = BigInteger.ModPow(x, 2, source);
						//if (x == BigInteger.One) return false;
						continue;
					}
				}
			}
			/* probably prime */
			return true;
		}

		private BigInteger mmi(BigInteger a, BigInteger nn)
		{
			BigInteger i = nn, v = BigInteger.Zero, d = BigInteger.One;
			while (a > BigInteger.Zero)
			{
				BigInteger t = i / a, x = a;
				a = i % x;
				i = x;
				x = d;
				d = v - t * x;
				v = x;
			}
			v %= nn;
			if (v < BigInteger.Zero) v = (v + nn) % nn;
			return v;
		}


		internal void genprimes_handler(TextBox threadsbox, Label threads_warning, string path)
		{
			string privkeypath = Path.Combine(path, "privkey-" + DateTime.Now.ToString("yyyyMMddTHHmmss") + ".pri");
			string pubkeypath = Path.Combine(path, "pubkey-" + DateTime.Now.ToString("yyyyMMddTHHmmss") + ".pub");
			string privkey = "";
			string pubkey = "";

			ManualResetEvent resetEvent = new ManualResetEvent(false);
			int toProcess = 0;
			tb_check(threadsbox, threads_warning);
			bool is_invalid = Regex.IsMatch(threadsbox.Text, @"^\D+$");
			if (is_invalid)
			{
				toProcess = numThreads;
				tb_check(threadsbox, threads_warning);
				return;
			}

			if (threads_valid(threadsbox.Text) == 1 || threads_valid(threadsbox.Text) == 2)
			{
				tb_check(threadsbox, threads_warning);
				MessageBox.Show("threads number needs to be 0 < n < 4", "check your numbah");
				return;
			}
			else if (threads_valid(threadsbox.Text) == 0)
			{
				bool is_whitespace = Regex.IsMatch(threadsbox.Text, @"\s+$");
				if (is_whitespace)
				{
					toProcess = numThreads;
				}
				else if (threadsbox.Text == "")
				{
					toProcess = numThreads;
				}
				else
				{
					custom_threads = Convert.ToInt32(threadsbox.Text);
				}
			}
			if (custom_threads != 0)
			{
				numThreads = custom_threads;
			}

			/* Start workers. */
			gp_start = DateTime.Now;
			Console.WriteLine($"\n[*] spawning genprimes threads \t({gp_start})");
			Parallel.For(0, numThreads, i =>
			{
				gen_primes();
			});
			gp_finish = DateTime.Now;
			Console.WriteLine($"[*] genprimes finished.\t({gp_finish})\n");

			Console.WriteLine($"[*] p:\n{P}");
			Console.WriteLine($"[*] q:\n{Q}\n");

			N = P * Q;
			Console.WriteLine($"[*] n:\n{N}\n");

			Console.WriteLine("[*] eulerFunction = (p - 1) * (q - 1)");
			BigInteger eulerFunction = (P - 1) * (Q - 1);
			Console.WriteLine($"[*] eulerFunction:\n{eulerFunction}\n");

			do
			{
				using (RNGCryptoServiceProvider rg = new RNGCryptoServiceProvider())
				{
					byte[] random = new byte[block_size];
					rg.GetBytes(random);
					E = new BigInteger(random);
					E = BigInteger.Abs(E);
				}
			} while (!(E > 1) || !(E < eulerFunction) || !(BigInteger.GreatestCommonDivisor(E, eulerFunction) == 1));

			Console.WriteLine($"[*] gcd(e, eulerFunction) = {BigInteger.GreatestCommonDivisor(E, eulerFunction)}");
			Console.WriteLine($"[*] e:\n{E}\n");

			Console.WriteLine($"d = e exp -1");
			D = mmi(E, eulerFunction);
			Console.WriteLine($"[*] d:\n{D}\n");

			Console.WriteLine("[*] check inverse: e * d mod eulerFunction = 1");
			Console.WriteLine($"{E} * {D} mod {eulerFunction} = {(E * D) % eulerFunction}\n");

			Console.WriteLine("***********\n* summary *\n***********");
			Console.WriteLine($"[*] p size: {P.ToString().Length} bits");
			Console.WriteLine($"[*] q size: {Q.ToString().Length} bits");
			Console.WriteLine($"[*] n size: {N.ToString().Length} bits");
			Console.WriteLine($"[*] e size: {E.ToString().Length} bits");
			Console.WriteLine($"[*] d size: {D.ToString().Length} bits");
			Console.WriteLine($"[*] tried primes: {candidates_tried}");
			Console.WriteLine($"[*] gp_start: {gp_start}");
			Console.WriteLine($"[*] gp_finish: {gp_finish}");
			Console.WriteLine($"[*] generating primes took: {gp_finish - gp_start}");
			Console.WriteLine("\n");

			privkey = string.Join(" ", N, D);
			pubkey = string.Join(" ", N, E);
			write_keys(privkey, privkeypath, pubkey, pubkeypath);

			MessageBox.Show("got primes y'all", "info");
		}

		private void write_keys(string privkey, string privkeypath, string pubkey, string pubkeypath)
		{
			File.WriteAllText(privkeypath, privkey);
			File.WriteAllText(pubkeypath, pubkey);
		}

		private int threads_valid(string input)
		{
			int returnme = 0;
			bool is_whitespace = Regex.IsMatch(input, @"\s");
			bool is_invalid = Regex.IsMatch(input, @"\D");
			bool has_num = Regex.IsMatch(input, @"\d");
			if (input == "" || is_whitespace)
			{
				returnme = 0;
			}
			if (is_invalid)
			{
				returnme = 2;
			}
			else if (is_invalid)
			{
				if (has_num)
				{
					returnme = 1;
				}
				else if (Convert.ToInt32(input) <= 0 || Convert.ToInt32(input) > 3)
				{
					returnme = 1;
				}
			}
			else if (has_num)
			{
				if (is_invalid)
				{
					returnme = 2;
				}
				else if (Convert.ToInt32(input) <= 0 || Convert.ToInt32(input) > 3)
				{
					returnme = 1;
				}
			}

			return returnme;
		}

		private void tb_invalid_input(TextBox tb)
		{
			tb.BackColor = Color.PaleVioletRed;
		}
		private void tb_valid_input(TextBox tb)
		{
			tb.BackColor = Color.White;
		}
		internal void tb_check(TextBox tb, Label threads_warning)
		{
			if (threads_valid(tb.Text) == 0)
			{
				tb_valid_input(tb);
				threads_warning.Text = "";
				threads_warning.Enabled = false;
			}
			else if (threads_valid(tb.Text) == 1)
			{
				tb_invalid_input(tb);
				threads_warning.Enabled = true;
				threads_warning.Text = "needs to be 0 < n < 4";
				return;
			}
			else if (threads_valid(tb.Text) == 2)
			{
				tb_invalid_input(tb);
				threads_warning.Enabled = true;
				threads_warning.Text = "needs to be a number";
				return;
			}
		}


		internal void keysize_handler(Button keysizebutton)
		{
			if (keysizebutton.Text == "1024b")
			{
				keysizebutton.Text = "2048b";
				randbytesize = b2048;
				block_size = ((Convert.ToInt32(key_size.b2048) * 2) / 8) - 1;
			}
			else if (keysizebutton.Text == "2048b")
			{
				keysizebutton.Text = "3072b";
				randbytesize = b3072;
				block_size = ((Convert.ToInt32(key_size.b3072) * 2) / 8) - 1;
				MessageBox.Show("gen_primes will likely take some time", "caution");
			}
			else if (keysizebutton.Text == "3072b")
			{
				keysizebutton.Text = "4096b";
				randbytesize = b4096;
				block_size = ((Convert.ToInt32(key_size.b4096) * 2) / 8) - 1;
				MessageBox.Show("gen_primes will likely take some time", "cautioncautioncautioncautioncaution");
			}
			else
			{
				keysizebutton.Text = "1024b";
				randbytesize = b1024;
				block_size = ((Convert.ToInt32(key_size.b1024) * 2) / 8) - 1;
			}
		}
	}
}