class Program
{
    static Random random = new Random();

    static void Main(string[] args)
    {
        {
            // 0
            byte[] primes = GetNotDivideable();
            byte p = primes[random.Next(0, primes.Length)], q = primes[random.Next(0, primes.Length)];    
                             
            // 1                                                                                                                                                                                           
            ushort n = (ushort)(p*q);

            // 2
            ushort phi = (ushort)((p - 1)*(q - 1));

            // 3
            List<ushort> possibleE = GetAllPossibleE(phi);
            ushort e;
            int d;
            do
            {
                e = possibleE[random.Next(0, possibleE.Count)];

                // 4
                d = ExtendedEuclidean(e % phi, phi).u1;
            } while (d < 0);

            // 5
            Console.WriteLine("Public  key: ({0},{1})",n,e);
            Console.WriteLine("Private key: ({0},{1})",n,d);

            Console.WriteLine();
            Console.Write("Enter value [0,255] to encode: ");
            byte value = Convert.ToByte(Console.ReadLine());

            Console.WriteLine();
            Console.WriteLine();

            // enc
            int encryptedValue = ModuloPow(value,e,n);

            // dec
            byte decryptedValue = (byte)ModuloPow(encryptedValue, d, n);

            // print
            Console.WriteLine("Value = {0}", value);
            Console.WriteLine("Encrypted value = {0}", encryptedValue);
            Console.WriteLine("Decrypted value = {0}", decryptedValue);
            Console.ReadKey();
        }
    }

    static int ModuloPow(int value, int pow, int modulo)
    {
        int result = value;
        for (int i = 0; i < pow-1; i++)
        {
            result = (result*value)%modulo;
        }
        return result;
    }

    /// <returns>All possible values ​​for the variable e</returns>
    static List<ushort> GetAllPossibleE(ushort phi)
    {
        List<ushort> result = new List<ushort>();

        for (ushort i = 2; i < phi; i++)
        {
            if (ExtendedEuclidean(i, phi).gcd == 1)
            {
                result.Add(i);
            }
        }

        return result;
    }

    /// <summary>
    /// u1 * a + u2 * b = u3
    /// </summary>
    /// <param name="a">first number</param>
    /// <param name="b">second number</param>
    private static ExtendedEuclideanResult ExtendedEuclidean(int a, int b)
    {
        int u1 = 1;
        int u3 = a;
        int v1 = 0;
        int v3 = b;

        while (v3 > 0)
        {
            int q0 = u3/v3;
            int q1 = u3%v3;

            int tmp = v1*q0;
            int tn = u1-tmp;
            u1 = v1;
            v1 = tn;

            u3 = v3;
            v3 = q1;
        }

        int tmp2 = u1 * (a);
        tmp2 = u3 - (tmp2);
        int res = tmp2 / (b);

        ExtendedEuclideanResult result = new ExtendedEuclideanResult()
                                                {
                                                    u1 = u1,
                                                    u2 = res,
                                                    gcd = u3
                                                };

        return result;
    }

    private struct ExtendedEuclideanResult
    {
        public int u1;
        public int u2;
        public int gcd;
    }

    static private byte[] GetNotDivideable()
    {
        List<byte> notDivideable = new List<byte>();

         
        for (int x = 2; x < 256; x++)
        {
            int n=0;
            for (int y = 1; y <= x; y++)
            {
                if (x % y == 0)
                    n++;
            }

            if (n <= 2)
                notDivideable.Add((byte)x);
        }
        return notDivideable.ToArray();
    }
}