Вычисление pow (a, b) mod n

Я хочу рассчитать b mod n для использования в расшифровке RSA. Мой код (ниже) возвращает неверные ответы. Что с ним не так?

unsigned long int decrypt2(int a,int b,int n)
{
    unsigned long int res = 1;

    for (int i = 0; i < (b / 2); i++)
    {
        res *= ((a * a) % n);
        res %= n;
    }

    if (b % n == 1)
        res *=a;

    res %=n;
    return res;
}

Ответы

Ответ 1

Вы можете попробовать этот код C++. Я использовал его с 32 и 64-битными целыми числами. Я уверен, что получил это от SO.

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}

Вы можете найти этот алгоритм и соответствующее обсуждение в литературе на стр. 244 из

Шнайер, Брюс (1996). Прикладная криптография: протоколы, алгоритмы и исходный код в C, второе издание (2-е изд.). Wiley. ISBN 978-0-471-11709-4.

Обратите внимание, что result * base умножения result * base и base * base подвержена переполнению в этой упрощенной версии. Если модуль превышает половину ширины T (т.е. Больше, чем квадратный корень из максимального значения T), то вместо этого следует использовать подходящий алгоритм модульного умножения - см. Ответы на пути к способу умножения по модулю с примитивными типами.

Ответ 2

Чтобы вычислить pow(a,b) % n который будет использоваться для расшифровки RSA, лучшим алгоритмом, с которым я столкнулся, является Primality Testing 1), который выглядит следующим образом:

 int modulo(int a, int b, int n){
    long long x=1, y=a; 
    while (b > 0) {
        if (b%2 == 1) {
            x = (x*y) % n; // multiplying with base
        }
        y = (y*y) % n; // squaring the base
        b /= 2;
    }
    return x % n;
}

Подробнее см. Ниже.

1)Испытание первичности: Недетерминированные алгоритмы - topcoder

Ответ 3

Обычно это что-то вроде этого:

while (b)
{
    if (b % 2) { res = (res * a) % n; }

    a = (a * a) % n;
    b /= 2;
}

return res;

Ответ 4

Единственная фактическая логическая ошибка, которую я вижу, - это строка:

if (b % n == 1)

который должен быть следующим:

if (b % 2 == 1)

Но ваш общий дизайн проблематичен: ваша функция выполняет операции умножения и модуля O (b), но использование b / 2 и a * a подразумевает, что вы стремились выполнять операции O (log b) (что обычно как выполняется модульное возведение в степень).

Ответ 5

Выполнение операции необработанной мощности очень дорогостоящее, поэтому вы можете применить следующую логику для упрощения дешифрования.

Из здесь,

Теперь скажем, что мы хотим зашифровать сообщение m = 7, c = m ^ e mod n = 7 ^ 3 mod 33 = 343 mod 33 = 13.
Следовательно, зашифрованный текст c = 13.

Чтобы проверить дешифрование, мы вычислим m '= c ^ d mod n = 13 ^ 7 mod 33 = 7.
Примечание что нам не нужно вычислять полное значение 13 для мощности 7 Вот. Мы можем воспользоваться тем, что a = bc mod n = (b mod n). (C mod n) mod n, чтобы мы могли разложить потенциально большое число в его компонентов и объединить результаты более простых, меньших вычислений с вычислить окончательное значение.

Один из способов вычисления m 'заключается в следующем: -
Обратите внимание, что любое число может быть выраженная в виде суммы степеней 2. Итак, сначала вычислим значения | 13 ^ 2, 13 ^ 4, 13 ^ 8,... путем многократного возведения в квадрат последовательных значений по модулю 33. 13 ^ 2 = 169 ≡ 4, 13 ^ 4 = 4.4 = 16, 13 ^ 8 = 16.16 = 256 ≡ 25. Затем, поскольку 7 = 4 + 2 + 1, имеем m '= 13 ^ 7 = 13 ^ (4 + 2 + 1) = 13 ^ 4.13 ^ 2.13 ^ 1
≡ 16 x 4 x 13 = 832 ≡ 7 mod 33

Ответ 6

Вы пытаетесь вычислить (a^b)%n или a^(b%n)?

Если вы хотите первый, то ваш код работает только тогда, когда b является четным числом из-за этого b/2. "if b%n==1" неверен, потому что здесь вас не волнует b%n, а скорее b%2.

Если вы хотите второй, тогда цикл неверен, потому что вы повторяете b/2, а не (b% n)/2 раза.

В любом случае, ваша функция излишне сложна. Почему вы зацикливаетесь до b/2 и пытаетесь размножаться в 2 раза каждый раз? Почему бы просто не зациклиться до b и mulitply в один раз каждый раз. Это устранит много ненужной сложности и, таким образом, устранит потенциальные ошибки. Вы думаете, что быстрее сделаете программу быстрее, сократив количество циклов в два раза? Честно говоря, это плохая практика программирования: микро-оптимизация. Это не очень помогает: вы все еще умножаетесь на одно и то же количество раз, все, что вы делаете, сокращается на количество раз, проверяя цикл. Если b обычно мал (например, одна или две цифры), это не стоит проблем. Если b велико - если оно может быть в миллионах - тогда этого недостаточно, вам нужна гораздо более радикальная оптимизация.

Также, почему %n каждый раз через цикл? Почему бы просто не сделать это один раз в конце?

Ответ 7

Вычисление pow (a, b) mod n

  1. Ключевой проблемой с кодом OP является a * a. Это int overflow (неопределенное поведение), когда a достаточно велико. Тип res имеет значения при умножении a * a.

    Решение состоит в том, чтобы обеспечить:

    • умножение выполняется с использованием 2x широкой математики или
    • с модулем n, n*n <= type_MAX + 1

  2. Нет причин возвращать более широкий тип, чем тип модуля, поскольку результат всегда представляет этот тип.

    // unsigned long int decrypt2(int a,int b,int n)
int decrypt2(int a,int b,int n)

  3. Использование unsigned math, безусловно, более подходит для целей OP RSA.

// (a^b)%n
// n != 0

// Test if unsigned long long at least 2x values bits as unsigned
#if ULLONG_MAX/UINT_MAX  - 1 > UINT_MAX
unsigned decrypt2(unsigned a, unsigned b, unsigned n) {
  unsigned long long result = 1u % n;  // Insure result < n, even when n==1
  while (b > 0) {
    if (b & 1) result = (result * a) % n;
    a = (1ULL * a * a) %n;
    b >>= 1;
  }
  return (unsigned) result;
}

#else
unsigned decrypt2(unsigned a, unsigned b, unsigned n) {
  // Detect if  UINT_MAX + 1 < n*n
  if (UINT_MAX/n < n-1) {
    return TBD_code_with_wider_math(a,b,n);
  }
  a %= n;
  unsigned result = 1u % n;
  while (b > 0) {
    if (b & 1) result = (result * a) % n;
    a = (a * a) % n;
    b >>= 1;
  }
  return result;
}

#endif

Ответ 8

int, как правило, недостаточно для RSA (если вы не имеете дело с небольшими упрощенными примерами)

вам нужен тип данных, который может хранить целые числа до 2 256 (для 256-разрядных ключей RSA) или 2 512 для 512-битных ключей и т.д.

Ответ 9

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

Здесь рекурсивная версия, которая работает для нескольких примеров, которые я нашел в Интернете.

unsigned long int decrypt2(int a,int b,int n)
{
unsigned long int res;

if (b == 0) {
  res = 1;
} else if (b % 2 == 1) {
  res = a * decrypt2( a, b-1, n );
} else {
  res = decrypt2( a, b/2, n );
  res = (res*res)%n;
}

Ответ 10

Это (шифрование) является скорее проблемой проектирования алгоритма, чем программирующей. Важной недостающей частью является знакомство с современной алгеброй. Я предлагаю вам искать огромный оптимизатор в теории групп и теории чисел. Если n - простое число, pow(a,n-1)%n==1 (предполагая бесконечные цифровые целые числа). Поэтому в основном вам нужно вычислить pow(a,b%(n-1))%n; Согласно теории групп, вы можете найти такое e, что любое другое число эквивалентно степени e по модулю n. Поэтому диапазон [1..n-1] можно представить в виде перестановки на степенях e. Учитывая алгоритм, чтобы найти e для n и логарифмом a базовой e, расчеты могут быть значительно упрощены. Криптография требует тон математического фона; Я предпочел бы покинуть эту землю без достаточного фона.

Ответ 11

используйте быструю экспонентуцию, возможно,..... дает такой же o (log n), что и этот шаблон выше

    int power(int base, int exp,int mod)
{
    if(exp == 0)
     return 1;

    int p=power(base, exp/2,mod);
    p=(p*p)% mod;
    return (exp%2 == 0)?p:(base * p)%mod;
}

Ответ 12

#include <cmath>
...
static_cast<int>(std::pow(a,b))%n

но лучше всего, если вы переполняете int (IE: число двух больших для int) на мощности у меня была такая же проблема, создавая ту же самую функцию.

Ответ 13

Я использую эту функцию:

int CalculateMod(int base, int exp ,int mod){
    int result;
    result = (int) pow(base,exp);
    result = result % mod;
    return result;
}

Я анализирую результат переменной, потому что pow возвращает вам двойное значение, и для использования мода вам нужны две переменные типа int, так или иначе, в расшифровке RSA, вы должны просто использовать целые числа.