PiMaker · January 31, 2019 11:39
diff --git a/RSA.cs b/RSA.cs
 /*
    A simple, well-documented implementation of the RSA asymmetric crypto scheme.
    Uses fixed initialization primes and only supports 32-bit numbers.
    
    This file is in the public domain.
 */

 using System;
 using System.Collections;

 namespace RSA
 {
    class Program
    {
        // Not crypto-secure! Don't use this algorithm (or .NET Random in general) for real-world applications!
        private static Random rand = new Random();

        static void Main(string[] args)
        {
            const int count = 1000;
            var correct = 0;

            // Iterate count times, print results, and check for correctness
            for (int i = 0; i < count; i++)
            {
                // Generate keys
                (var sk, var pk, var N) = Gen();
                Console.WriteLine($"Gen() = (sk={sk}, pk={pk}, N={N})");

                // Generate random message
                var m = rand.Next(2, N);
                Console.WriteLine($"m = {m}");

                // Encrypt
                var c = Enc(m, pk, N);
                Console.WriteLine($"Enc(m) = c = {c}");

                // Decrypt
                var m2 = Dec(c, sk, N);
                Console.WriteLine($"Dec(c) = {m2}");

                // Check for errors
                if (m == m2)
                {
                    correct++;
                    Console.WriteLine("Correct, Dec(Enc(m)) = m");
                }
                else
                {
                    Console.WriteLine("Wrong, m != Dec(c). Press any key to continue...");
                    Console.ReadKey(true);
                }

                Console.WriteLine();
            }

            // Tell the user if the algorithm worked
            Console.WriteLine($"Correct: {correct} of {count}");
            Console.ReadKey(true);
        }

        // Generate an RSA tuple consisting of a secret key sk, a public key pk, and a modulus N
        private static (int sk, int pk, int N) Gen()
        {
            var p = 89; // Prime
            var q = 181; // Prime
            var N = p * q; // Modulus

            // φ(N) = φ(pq) = φ(p)*φ(q)
            var phiN = PhiForPrimes(p, q);

            // Exponent = private key; must be smaller than and coprime φ(N) for the euclidian alg. below to work
            var e = RandomNextCoprime(2, phiN, phiN);

            // e^(-1), to satisfy (m^e)^d = m
            (_, var sk, _) = ExtendedEuclidian(e, phiN);

            // Make sure sk is not negative
            // Note, that a^b mod m is equal to a^((k*m)+b) mod m for all integer k
            while (sk < 0)
            {
                sk += phiN;
            }

            return (sk, e, N);
        }

        // Calculate euler-phi (number of integers k coprime to N with 0<k<N and N=p*q)
        // This uses a shortcut only available if p and q are prime
        // (Note, that this shortcut is what makes this function useful for RSA in the first place)
        private static int PhiForPrimes(int p, int q) => (p - 1) * (q - 1);

        // Generate a random number and ensure it is coprime to n
        private static int RandomNextCoprime(int min, int max, int n)
        {
            int retval, gcd;
            do
            {
                // Sample-and-retry is fine,
                // see https://stackoverflow.com/questions/17969423/finding-any-coprime-number
                retval = rand.Next(min, max);
                (gcd, _, _) = ExtendedEuclidian(retval, n);
            } while (gcd != 1); // Retry until number coprime n is found

            return retval;
        }

        // Extended euclidian algorithm
        private static (int gcd, int s, int t) ExtendedEuclidian(int a, int b)
        {
            // Must satisfy b >= a
            if (b < a)
            {
                (a, b) = (b, a);
            }

            // Extended euclidian algorithm
            var s_prev = 0; // s for a
            var s = 1;
            var t_prev = 1; // t for b
            var t = 0;

            while (true)
            {
                // N = a*q+r
                var q = b / a; // Quotient
                var r = b % a; // Remainder

                // Next step ("shift numbers left and down", if working with pen and paper)
                (a, b) = (r, a);

                // Terminate
                if (a == 0)
                {
                    break;
                }

                // Forward pass for extended algorithm
                // s_new = s_prev - s*q (and similar for t)
                (s, s_prev) = (s_prev - s * q, s);
                (t, t_prev) = (t_prev - t * q, t);
            }

            // b == gcd(a, b) == a*s + b*t
            return (b, s, t);
        }

        // Encrypt a value given a secret key and a modulus
        private static int Enc(int m, int pk, int N)
        {
            return FastPowN(m, pk, N);
        }

        // Decrypt a value given a secret key and a modulus
        private static int Dec(int c, int sk, int N)
        {
            return FastPowN(c, sk, N);
        }

        // Split number into powers of two and multiply each power seperately, doubling for each step
        // This allows constant time calculation of any power (modulo n)
        private static int FastPowN(int x, int exp, int n)
        {
            var nbits = new BitArray(new[] { exp });
            var t = 1L; // Long, to avoid over-/underflow on intermediate calculation value below
            
            // Iterate to 32 (bitsize of an integer)
            for (int i = 0; i < 32; i++)
            {
                t = ((t * t) * (nbits[nbits.Length - i - 1] ? x : 1))%n;
            }

            // Casting is safe, since last operation is mod n, and n is int
            return (int)t;
        }
    }
 }
	/*
	A simple, well-documented implementation of the RSA asymmetric crypto scheme.
	Uses fixed initialization primes and only supports 32-bit numbers.

	This file is in the public domain.
	*/

	using System;
	using System.Collections;

	namespace RSA
	{
	class Program
	{
	// Not crypto-secure! Don't use this algorithm (or .NET Random in general) for real-world applications!
	private static Random rand = new Random();

	static void Main(string[] args)
	{
	const int count = 1000;
	var correct = 0;

	// Iterate count times, print results, and check for correctness
	for (int i = 0; i < count; i++)
	{
	// Generate keys
	(var sk, var pk, var N) = Gen();
	Console.WriteLine($"Gen() = (sk={sk}, pk={pk}, N={N})");

	// Generate random message
	var m = rand.Next(2, N);
	Console.WriteLine($"m = {m}");

	// Encrypt
	var c = Enc(m, pk, N);
	Console.WriteLine($"Enc(m) = c = {c}");

	// Decrypt
	var m2 = Dec(c, sk, N);
	Console.WriteLine($"Dec(c) = {m2}");

	// Check for errors
	if (m == m2)
	{
	correct++;
	Console.WriteLine("Correct, Dec(Enc(m)) = m");
	}
	else
	{
	Console.WriteLine("Wrong, m != Dec(c). Press any key to continue...");
	Console.ReadKey(true);
	}

	Console.WriteLine();
	}

	// Tell the user if the algorithm worked
	Console.WriteLine($"Correct: {correct} of {count}");
	Console.ReadKey(true);
	}

	// Generate an RSA tuple consisting of a secret key sk, a public key pk, and a modulus N
	private static (int sk, int pk, int N) Gen()
	{
	var p = 89; // Prime
	var q = 181; // Prime
	var N = p * q; // Modulus

	// φ(N) = φ(pq) = φ(p)*φ(q)
	var phiN = PhiForPrimes(p, q);

	// Exponent = private key; must be smaller than and coprime φ(N) for the euclidian alg. below to work
	var e = RandomNextCoprime(2, phiN, phiN);

	// e^(-1), to satisfy (m^e)^d = m
	(_, var sk, _) = ExtendedEuclidian(e, phiN);

	// Make sure sk is not negative
	// Note, that a^b mod m is equal to a^((k*m)+b) mod m for all integer k
	while (sk < 0)
	{
	sk += phiN;
	}

	return (sk, e, N);
	}

	// Calculate euler-phi (number of integers k coprime to N with 0<k<N and N=p*q)
	// This uses a shortcut only available if p and q are prime
	// (Note, that this shortcut is what makes this function useful for RSA in the first place)
	private static int PhiForPrimes(int p, int q) => (p - 1) * (q - 1);

	// Generate a random number and ensure it is coprime to n
	private static int RandomNextCoprime(int min, int max, int n)
	{
	int retval, gcd;
	do
	{
	// Sample-and-retry is fine,
	// see https://stackoverflow.com/questions/17969423/finding-any-coprime-number
	retval = rand.Next(min, max);
	(gcd, _, _) = ExtendedEuclidian(retval, n);
	} while (gcd != 1); // Retry until number coprime n is found

	return retval;
	}

	// Extended euclidian algorithm
	private static (int gcd, int s, int t) ExtendedEuclidian(int a, int b)
	{
	// Must satisfy b >= a
	if (b < a)
	{
	(a, b) = (b, a);
	}

	// Extended euclidian algorithm
	var s_prev = 0; // s for a
	var s = 1;
	var t_prev = 1; // t for b
	var t = 0;

	while (true)
	{
	// N = a*q+r
	var q = b / a; // Quotient
	var r = b % a; // Remainder

	// Next step ("shift numbers left and down", if working with pen and paper)
	(a, b) = (r, a);

	// Terminate
	if (a == 0)
	{
	break;
	}

	// Forward pass for extended algorithm
	// s_new = s_prev - s*q (and similar for t)
	(s, s_prev) = (s_prev - s * q, s);
	(t, t_prev) = (t_prev - t * q, t);
	}

	// b == gcd(a, b) == as + bt
	return (b, s, t);
	}

	// Encrypt a value given a secret key and a modulus
	private static int Enc(int m, int pk, int N)
	{
	return FastPowN(m, pk, N);
	}

	// Decrypt a value given a secret key and a modulus
	private static int Dec(int c, int sk, int N)
	{
	return FastPowN(c, sk, N);
	}

	// Split number into powers of two and multiply each power seperately, doubling for each step
	// This allows constant time calculation of any power (modulo n)
	private static int FastPowN(int x, int exp, int n)
	{
	var nbits = new BitArray(new[] { exp });
	var t = 1L; // Long, to avoid over-/underflow on intermediate calculation value below

	// Iterate to 32 (bitsize of an integer)
	for (int i = 0; i < 32; i++)
	{
	t = ((t * t) * (nbits[nbits.Length - i - 1] ? x : 1))%n;
	}

	// Casting is safe, since last operation is mod n, and n is int
	return (int)t;
	}
	}
	}