A simple, well-documented implementation of the RSA asymmetric crypto scheme.

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;
        }
    }
}