RSA algorithm in C# using Mpit.NET

Program.cs

// Based on https://gist.github.com/akosma/865b887f993de462369a04f4e81596b8

using System;
using System.Diagnostics;

using Mpir.NET;

namespace RSA
{
	class Program
	{
		private static (mpz_t n, mpz_t d) RsaKeys(mpz_t p, mpz_t q, mpz_t e)
		{
			var n = p * q;

			var lambda = mpz_t.Lcm(p - 1, q - 1);

			Console.WriteLine($"lambda = {lambda}");

			// e must be bigger than 1
			Debug.Assert(e > 1);

			// e must be smaller than lambda
			Debug.Assert(e < lambda);

			// GCD(e, lambda) must be 1
			var gcd = mpz_t.Gcd(e, lambda);
			Debug.Assert(gcd == 1);

			var d = e.InvertMod(lambda);

			// e * d MOD lambda must be 1
			var mod = (e * d).Mod(lambda);
			Debug.Assert(mod == 1);

			return (n, d);
		}

		private static mpz_t Encrypt(mpz_t message, mpz_t e, mpz_t n)
		{
			return message.PowerMod(e, n);
		}

		private static mpz_t Decrypt(mpz_t encrypted, mpz_t d, mpz_t n)
		{
			return encrypted.PowerMod(d, n);
		}

		private static void DisplayGmp(mpz_t message, mpz_t n, mpz_t e, mpz_t d)
		{
			var encrypted = Encrypt(message, e, n);
			var decrypted = Decrypt(encrypted, d, n);

			// The decrypted message must be equal to the original
			Debug.Assert(message == decrypted);

			Console.WriteLine($"Public key = (e: {e}, n: {n}");
			Console.WriteLine($"Private key = (d: {d}, n: {n}");
			Console.WriteLine($"Original message: {message}");
			Console.WriteLine($"Encrypted message: {encrypted}");
			Console.WriteLine($"Decrypted message: {decrypted}");
		}

		private static void DisplayNum(int msg, int pi, int qi, int ei)
		{
			Console.WriteLine($"Initializing with p = {pi}, q = {qi}, e = {ei}");

			var keys = RsaKeys(pi, qi, ei);

			DisplayGmp(msg, keys.n, ei, keys.d);
		}

		private static void DisplayStr(string msg, string pi, string qi, string ei)
		{
			var original = new mpz_t(msg, 10);
			var p = new mpz_t(pi, 10);
			var q = new mpz_t(qi, 10);
			var e = new mpz_t(ei, 10);

			var keys = RsaKeys(p, q, e);

			DisplayGmp(original, keys.n, e, keys.d);
		}

		static void Main(string[] args)
		{
			// Example taken from Wikipedia
			// https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation
			DisplayNum(65, 61, 53, 17);

			// Example from Twitter
			// https://twitter.com/kosamari/status/838738015010848769
			DisplayGmp(123, 323, 5, 29);

			// Very small prime numbers
			DisplayNum(123, 13, 19, 17);

			// With some prime numbers from
			// http://www.bigprimes.net/
			DisplayNum(67890, 541, 461, 107);
			DisplayNum(123456, 1181, 929, 173);

			// The PHP version takes around 10 seconds on a MacBook Air
			DisplayNum(123456, 1181, 929, 1987);

			// The PHP takes around 40 seconds in a MacBook Air
			DisplayNum(123456, 1181, 929, 17);

			// Very big numbers; using Mersenne primes,
			// something impossible in the PHP version
			DisplayStr("1111119999999999911111111",
				"162259276829213363391578010288127",
				"618970019642690137449562111",
				"170141183460469231731687303715884105727");
		}
	}
}

Nice! 👍