RSA 算法不适用于某些数字

Question

我有一个家庭作业，包括处理用户登录和注册。为此，老师告诉我们使用RSA算法来加密用户的密码。我的问题是RSA。我正在尝试编写它以仅加密 1 个整数，然后我将编写一个加密字符串的新方法。所以此时此刻，我的代码适用于某些整数，而对于其他整数，它失败得很厉害。这是头文件

#ifndef _RSA_
#define _RSA_

#include <cmath>
#include <string>

// A class that defines the RSA algorithm
class RSA {
    private:
        int p, q, n, z, d = 0, e;

    public:
        RSA();
        int gcd(int a, int b);
        int encrypt(int m);
        int decrypt(int c);
    
};

#endif

这是我实现这些功能的文件。

#include "./RSA.h"

RSA::RSA() {
    this->p = 3;
    this->q = 11;
    this->z = (this->p - 1) * (this->q - 1);
    this->n = this->p * this->q;

    for (this->e = 2; this->e < this->z; this->e++) {
        if (this->gcd(this->e, this->z) == 1) {
            break;
        }
    }

    for (int i = 0; i <= 9; ++i) {
        int x = (i * this->z) + 1;
        if (x % this->e == 0) {
            this->d = x / this->e;
            break;
        }
    }
}

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

int RSA::encrypt(int m) {
    return (int)pow(m, e) % this->n;
}

int RSA::decrypt(int c) {
    return (int)pow(c, d) % this->n;
}

现在我将为您提供一些有效的数字和一些无效的数字。说这些数字有效我的意思是在我解密加密方法的结果后我得到了初始数字。它适用于 1,2,6,7,8,9,10（它 returns 10 用于加密部分，10 用于解密），11（与 10 相同），12（与 11 相同），13, 14 , 15, 16。我测试了 [1, 17] 范围内的数字，但 3,4,5,17 失败了。它 returns 这 4 个数字完全随机。另外，我在其他数字范围上试过，结果是一样的。

Answer 1

即使是这样的小数字，也很容易超过 int 的取幂限制。如果你自己制作 pow，它应该在每一步之后应用模数：

// computes x**y % n
int custom_pow(int x, int y, int n) {
    int res = 1;
    for(;y;y--) {
        res = (res*x) % n;
    }
    return res;
}

RSA 算法不适用于某些数字

RSA Algorithm is not working for certain numbers

c++

encryption

rsa