这是错误的原因吗？

Question

#include <iostream>
#include <bits/stdc++.h>
#include <numeric>

using namespace std;

int
gcd (int a, int b)
{
  if (a == 0)
    return b;
  return gcd (b % a, a);
}

int
phi (unsigned int n)
{
  unsigned int result = 1;
  for (int i = 2; i < n; i++)
    if (gcd (i, n) == 1)
      result++;
  return result;
}

int
gen_priv_n (int p1, int p2)
{
  int n = phi (p1) * phi (p2);
  return n;
}

int
gen_pub_n (int p1, int p2)
{
  int n = (p1 * p2);
  return n;
}

int
gen_priv_key (int n, int e)
{
  int x = (phi (e) * n + 1) / e;
  return x;
}

int
encrypt (int n, int e, int data)
{
  int crypt_data = int (pow (data, e)) % n;
  return crypt_data;
}

int
decrypt (int c, int d, int n)
{
  int data = int (pow (c, d)) % n;
  return data;
}

int
main ()
{
  int ph1 = 53;
  int ph2 = 59;
  int e = 3;
  int message = 89;
  
  int pub_n = gen_pub_n (ph1, ph2);
  cout << "PUBN " << pub_n << "\n";
  int priv_n = gen_priv_n (ph1, ph2);
  cout << "PRIVN " << priv_n << "\n";
  int d = gen_priv_key (gen_priv_n (ph1, ph2), e);
  cout << "PRIVKEY " << d << "\n";
  int c = encrypt (pub_n, e, message);
  cout << "ENCRYPTED " << c << "\n";
  int data = decrypt (c, d, pub_n);
  cout << "MESSAGE " << data;
}

PUBN、PRIVN、PRIVKEY 和 ENCRYPTED 都是 return 预期的数字，然而，解密函数应该 return 89（消息变量），但不是。我假设代码操作顺序存在算术错误，但我不确定。能否指出问题？

变量的结果是：

PUBN 3127
PRIVN 3016
PRIVKEY 2011
加密 1394
MESSAGE -763 <-- 意外结果，应为 89

Answer 1

解密（和加密）功能被破坏，因为它 (a) 超出了 int 的平台表示，并且 (b) 首先不必要地使用 pow 来完成.

在您的简单示例中，您应该使用一种称为 modulo chaining 的技术。问题的症结如下。

(a * b) % n == ((a % n) * (b % n)) % n

在您的例子中，您执行的是简单的求幂运算。这意味着，例如 a^2 % n 将是：

(a * a) % n = ((a % n) * (a % n)) % n

同理，a^3 % n 为：

(a * a * a) % n = (((a % n) * (a % n)) % n) * (a % n)) % n

使用 modulo 链接允许您计算否则会非常大的乘积计算 mod 一些 N，只要没有乘积术语对超过您的平台表示（并且它不会在你的情况下）。

整数 pow 的简单版本如下：

int int_pow_mod(int c, int d, int n)
{
    int res = 1;

    // may as well only do this once
    c %= n;

    // now loop.
    for (int i=0; i<d; ++i)
        res = (res * c) % n;

    return res;
}

了解，这不是灵丹妙药。你可以很容易地设计出一个 c 仍然生产超过 INT_MAX 的产品，但在你的情况下，由于你选择开始 material，这不会发生。一个通用的解决方案将使用这个和一个 big-number 库，它允许超过平台 int 表示。无论如何，这样做应该会实现您所寻求的，如下所示：

#include <iostream>
using namespace std;

unsigned int gcd(unsigned int a, unsigned int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

int phi(unsigned int n)
{
    unsigned int result = 1;
    for (unsigned int i = 2; i < n; i++)
        if (gcd(i, n) == 1)
            result++;
    return result;
}

int gen_priv_n(int p1, int p2)
{
    int n = phi(p1) * phi(p2);
    return n;
}

int gen_pub_n(int p1, int p2)
{
    int n = (p1 * p2);
    return n;
}

int gen_priv_key(int n, int e)
{
    int x = (phi(e) * n + 1) / e;
    return x;
}

int int_pow_mod(int c, int d, int n)
{
    int res = 1;

    // may as well only do this once
    c %= n;

    // now loop.
    for (int i=0; i<d; ++i)
        res = (res * c) % n;

    return res;
}

int encrypt(int n, int e, int data)
{
    int crypt_data = int_pow_mod(data, e, n);
    return crypt_data;
}


int decrypt(int c, int d, int n)
{
    int data = int_pow_mod(c, d, n);
    return data;
}

int main()
{
    int ph1 = 53;
    int ph2 = 59;
    int e = 3;
    int message = 89;

    int pub_n = gen_pub_n(ph1, ph2);
    cout << "PUBN " << pub_n << "\n";
    int priv_n = gen_priv_n(ph1, ph2);
    cout << "PRIVN " << priv_n << "\n";
    int d = gen_priv_key(gen_priv_n(ph1, ph2), e);
    cout << "PRIVKEY " << d << "\n";
    int c = encrypt(pub_n, e, message);
    cout << "ENCRYPTED " << c << "\n";
    int data = decrypt(c, d, pub_n);
    cout << "MESSAGE " << data;
}

输出

PUBN 3127
PRIVN 3016
PRIVKEY 2011
ENCRYPTED 1394
MESSAGE 89

这是错误的原因吗？

Is there a reason this is wrong?

c++

encryption

cryptography

public-key-encryption