Протокол Диффи-Хеллмана не работает при некоторых значениях

#cpp #криптография

Почему при 


  p = 23, g = 5, a = 6, b = 15


ba равен ab, но при


  p = 23, g = 5, a = 116, b = 15


уже нет?

Какие типы, числа и диапазоны чисел должны быть для этого протокола?

#include  
#include  

int main() {
  unsigned long long int p = 23;
  unsigned long long int g = 5;
  unsigned long long int a = 6;
  unsigned long long int b = 15;
  unsigned long long int A = std::fmod(pow(g, a), p);
  unsigned long long int B = std::fmod(pow(g, b), p);
  unsigned long long int ba = std::fmod(pow(B, a), p);
  unsigned long long int ab = std::fmod(pow(A, b), p);
  return 1;
} 

    

Ответы

Ответ 1

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

Во-вторых, ваша последовательность действий описывает процесс формирования общего
ключа после выбора секретных ключей a и b. В протоколе Диффи-Хеллмана секретные ключи
a и b выбираются из мультипликативной группы по модулю p, то есть в вашем примере для
p = 23 это должны быть значения в диапазоне [1, 22]. При чем здесь ваше 116, откуда
вы его взяли и чего от него ожидали - не ясно.

(Как правильно заметил @Zergatul в комментариях, при p = 23 протокол будет правильно
работать и для a = 116. Но нет никакого смысла в том, чтобы выбирать число за пределами
диапазона [1, 22]. В вашем случае это лишь привело к потере точности.)


Ответ 2

Никто так не считает остаток от деления после возведения в степень. Самая простая
оптимизация выглядит так:

int modpow(int a, int b, int m) // a^b % m
{
    int result = 1;
    // 31 - для упрощения кода, на самом деле нужно брать длину числа в битах
    for (int i = 31; i >= 0; i--)
    {
        result = result * result % m;
        if (b & (1 << i))
            result = result * a % m;
    }
    return result;
}


В реальных библиотеках для длинных чисел и криптографии дополнительно используют
алгоритм Монтгомери.