c++ - 我的 RSA 加密每次生成 2^64 (C++)

Question

我尝试编写了自己的 RSA 算法，但是当我使用相当大的数字(与应该用于 RSA 的大小完全不同)时，加密部分无法正常工作，我不确定为什么。

它的工作方式如下:

输入是一个字符列表，例如“abc”

这被转换为一个数组:[10,11,12]。 (我为小写字母选择了 10 - 35，这样它们都是 2 位数字，只是为了更容易)

数字组合形成 121110(使用 12*100^2 + 11*100^1 + 10*100^0)

应用算法:m^e (mod n) 这是使用 a^b (mod n) = a^c (mod n) * a^d (mod n) 简化的

这适用于小值，因为它可以使用我编写的解密程序进行解密。

当使用较大的值时，输出总是 1844674407188030241，通过一些研究我发现这大约是 2^64(对于 10 位有效数字，已经指出奇数不能是 2 的幂，哎呀)。我确信我忽略了一些事情，我很抱歉(我真的希望)这将是一个简单答案的微不足道的问题。为什么输出值总是 2^64，我可以更改什么来修复它？非常感谢您的帮助，这是我的代码:

#include <iostream>
#include <string>
#include <math.h>

int returnVal (char x)
{
    return (int) x;
}

unsigned long long modExp(unsigned long long b, unsigned long long e, unsigned long long m)
{
unsigned long long remainder;
int x = 1;

while (e != 0)
{
remainder = e % 2;
e= e/2;

if (remainder == 1)
x = (x * b) % m;
b= (b * b) % m;
}
return x;
}

unsigned mysteryFunction(const std::string& input)
{
  unsigned result = 0;
  unsigned factor = 1;

  for (size_t i = 0; i < input.size(); ++i)
  {
    result += factor * (input[i] - 87);
    factor *= 100;
  }

  return result;
}

int main()
{
    unsigned long long p = 70021;
    unsigned long long q = 80001;
    int e = 7;
    unsigned long long n = p * q;
    std::string foo = "ab";
    for (int i = 0; i < foo.length(); i++);

    {
        std::cout << modExp (mysteryFunction(foo), e, n);
    }
}

Answer 1

您的代码有几个问题。

问题 1:unsigned long long 的使用不一致。

int x = 1;

将 modExp 中的声明更改为 unsigned long long 会使程序给出看起来更合理的结果。我不知道它是否是正确的 结果，但它至少小于n。我仍然不确定错误的确切机制是什么。我可以看到它会把事情搞砸的方式，但没有一种会导致输出 1844674407188030241。

问题 2:复合“素数”。

对于 RSA，p 和 q 都需要是素数。 p 和 q 在您的代码中都不是素数。

70021 = 7^2 * 1429
80001 = 3^2 * 2963