Реализация алгоритма шифрования RSA на C#

О шифровании с открытым ключом многие уже слышали и читали, и одним из самых популярных и известных является алгоритм RSA. Rivest, Shamir и Adleman в 1977 году опубликовали свою статью о данном алгоритме. Основывается он на факторизации простых довольно больших чисел. Пример реализации алгоритма описан
Такие большие числа порядка 10²⁰ в C# реализуются при помощи подключаемой библиотеки Sustem.Numerics и класса BigInteger.

Для шифрования и дешифрирования сообщений используется следующий класс:

class RSA
        {
            private BigInteger d, e, fi, n;
            public BigInteger D { get { return d; } }
            public BigInteger E { get { return e; } }
            public BigInteger Fi { get { return fi; } }
            public BigInteger N { get { return n; } }
            public BigInteger m1, m2;

            public RSA(BigInteger p, BigInteger q, BigInteger m, Primes pr)
            {
                if (pr.IsPrime(p, q))
                {
                    this.n = p * q;
                    this.fi = (p - 1) * (q - 1);
                    this.e = OpenKey();
                    this.d = modInverse(this.e, this.Fi);
                    this.m1 = BigInteger.ModPow(m, this.E, this.N);
                    this.m2 = BigInteger.ModPow(m1, d, this.N);
                }
            }
            public RSA(BigInteger p, BigInteger q, BigInteger m)
            {
                if (new Primes(3000000).IsPrime(p, q))
                {
                    this.fi = (p - 1) * (q - 1);
                    this.e = OpenKey();
                    this.d = modInverse(this.e, this.Fi);
                    this.m1 = BigInteger.ModPow(m, this.E, this.N);
                    this.m2 = BigInteger.ModPow(m1, d, this.N);
                }
            }
            private BigInteger OpenKey()
            {
                bool b = true;
                BigInteger i = (BigInteger)Math.Truncate((decimal)Math.Sqrt((ulong)this.Fi));
                while (b)
                {
                    if (BigInteger.GreatestCommonDivisor(fi, i) != 1)
                        i--;
                    else { b = false; }
                }
                return i;
            }
            public static BigInteger modInverse(BigInteger e, BigInteger fhi)
            {
                BigInteger i = fhi, v = 0, d = 1;
                while (e > 0)
                {
                    BigInteger t = i / e, x = e;
                    e = i % x;
                    i = x;
                    x = d;
                    d = v - t * x;
                    v = x;
                }
                v %= fhi;
                if (v < 0) v = (v + fhi) % fhi;
                return v;
            }
        }

Для проверки на простоту чисел, передаваемых в качестве аргументов в перегрузки конструктора используется класс Primes:

        class Primes
        {
            private BigInteger[] primeArray;
            public BigInteger[] PRIMEARRAY { get { return primeArray; } }

            public Primes(BigInteger k)
            {
                this.primeArray = Eratosfen(k);
            }

            public BigInteger PrimeNumber()
            {
                BigInteger p = PRIMEARRAY[new Random().Next(10, PRIMEARRAY.Length)];
                return p;
            }

            public bool IsPrime(BigInteger p, BigInteger q)
            {
                if (!this.PRIMEARRAY.Contains(p)) { Console.WriteLine("p isn't prime"); return false; }
                if (!this.PRIMEARRAY.Contains(q)) { Console.WriteLine("q isn't prime"); return false; }
                return true;
            }

            private BigInteger[] Eratosfen(BigInteger k)
            {
                bool[] table = new bool[(ulong)k];
                List<BigInteger> primearray = new List<BigInteger>();
                for (BigInteger i = 0; i < k; i++)
                    table[(ulong)i] = true;
                for (BigInteger i = 2; i * i < k; i++)
                    if (table[(ulong)i])
                        for (var j = 2 * i; j < k; j += i)
                            table[(ulong)j] = false;
                for (BigInteger i = 1; i < k; i++)
                {
                    if (table[(ulong)i])
                    {
                        primearray.Add(i);
                    }
                }
                return primearray.ToArray();
            }

В классе реализовано решето Эратосфена и несколько методов, позволяющих получить случайное простое число и собственно проверить два числа на простоту. При использовании решета Эратосфена, к сожалению, мы не можем получить достаточно большие числа, которые в действительности стали бы хорошим фундаментом для ключа. Но это уже другой вопрос. (В последующем думаю над реализацией теста на простоту, и скорее всего это будет тест Миллера-Рабина, но если кто-нибудь мне может помочь с реализацией AKS был бы очень признателен).

Возвращаясь к классу RSA, я бы хотел пояснить метод OpenKey. Он нужен для генерирования открытого ключа, который должен быть меньше, чем значение функции Эйлера и взаимно-просто с ним. Остальные методы и операции являются достаточно очевидными.

Автор: andrey207

Источник