Функция повторного возведения в квадрат при написании алгоритма rsa

Question

Нужно написать функцию, которая вычисляет C из формулы выше. С задачей я справился, хоть данная функция откровенно - говнокод:

    public static long reSquaring(long m, long e, long n)//c=m^e(mod n)
        {
            long E = e;

            int i;
            for (i = 1; E != 1; i++)//Проверка количества элементов
                E = E / 2;

            long[] bynaryN = new long[i];

            E = e;
            for (int j = 0; j < i; j++)//Степень в бинарном представлении
            {
                bynaryN[j] = E % 2;
                E = E / 2;
            }

            long b = m % n;
            for (int j = 1; j < i; j++)//Возведение в степень
            {
                b = (long)Math.Pow(b, 2) % n;
                if (bynaryN[j] == 1)
                    m = (m * b) % n;
            }
            return m;
        }
        static void Main(string[] args)
        {
            Console.WriteLine(reSquaring(1324473530, 2731525513, 2110818553));
        }

При формировании зашифрованного сообщения всё работает нормально, но при ключах p = 36563,q = 57731, e = 17 вычисления получаются не верными. Ведь значения при таких p и q получаются, как передаваемые значения в методе main. Но при дешифровании получаются огромнейшие числа. Приведу в пример из консоли: При ключах p = 7, q = 11, e = 17 получается дешифровать данные(Последняя строка): При ключах p = 36563, q = 57731, e = 17 по заданию. Получаю(последняя строка): Почему? и как исправить? За основу брал объяснение из методички:

Answer 1

Попробуйте заменить long на BigInteger и используй BigInteger.ModPow

В приведенном вами примере получил ответ 15

using System.Numerics;


 public static BigInteger reSquaring(BigInteger m, BigInteger e, BigInteger n)//c=m^e(mod n)
    {
        BigInteger E = e;

        int i;
        for (i = 1; E != 1; i++)//Проверка количества элементов
            E = E / 2;

        BigInteger[] bynaryN = new BigInteger[i];

        E = e;
        for (int j = 0; j < i; j++)//Степень в бинарном представлении
        {
            bynaryN[j] = E % 2;
            E = E / 2;
        }

        BigInteger b = m % n;
        for (int j = 1; j < i; j++)//Возведение в степень
        {
            b = BigInteger.ModPow(b, 2, n); 
            if (bynaryN[j] == 1)
                m = (m * b) % n;
        }
        return m;
    }
    static void Main(string[] args)
    {
        Console.WriteLine(reSquaring(1324473530, 2731525513, 2110818553));
    }

БЛОГ НА HUSL

Функция повторного возведения в квадрат при написании алгоритма rsa

Ответы (1 шт):