RSA 实现未正确解密

Question

我喜欢学习，今天我决定最终自己实现 RSA。基本上，据我所知，我的代码应该有效，而且在一定程度上确实有效。

然而，即使（根据 Internet 学习资源）计算并正确使用了正确的密钥，我仍然得到奇怪的输出。我查了也没找到问题出在哪里，因为手工计算的结果是一样的...

是的，这是我的 cryptography.cpp-文件：

#include "cryptography.h"

bool prime(const unsigned long long n) {
    //max of sqrt(n)
    unsigned long long m = 0.5 * n;

    for(unsigned int i = 2; i <= m; i++) //check every possible divisor
        if(n % i == 0)  //wheter it goes in to n perfectly
            return false;   //n is not prime if such divisor is found

    //if no divisor found
    return true;
}

bool coprime(unsigned long long p, unsigned long long q) {
    //p >= q
    if(q > p) {
        long long t = p;
        p = q;
        q = t;
    }

    //subtract smaller from bigger, keeping gcd
    while(q != 0) {
        unsigned long long r = p % q;
        p = q;
        q = r;
    }

    //gdc == 1
    return p == 1;
}

/**
 * Finds d for:
 * 1 = (d * e) % m
*/
unsigned long long modularInverse(const unsigned long long e, const unsigned long long m) {
    unsigned long long d = 1;
    while(d * e % m != 1)
        d++;
    return d;
}

unsigned long long pow(const unsigned long long base, const unsigned long long exponent) {
    unsigned long long result = 1;
    for(long long i = 0; i < exponent; i++)
        result *= base;
    return result;
}

bool RSA::generateKeys(const unsigned long long p, const unsigned long long q, unsigned long long& n, unsigned long long& d, unsigned long long& e) {
    //p & q have to be primes
    if(!(prime(p) && prime(q)) || p == q)
        return false;

    //n defined as p * q
    n = p * q;

    unsigned long long m = (p - 1) * (q - 1);

    //find e where e and (p - 1)(q - 1) are coprime
    e = 7;
    while(!coprime(m, e))
        e++;

    //1 = (d * e) % (p - 1)(q - 1)
    d = modularInverse(e, m);

    //everything worked
    return true;
}

unsigned long long RSA::encrypt(const unsigned long long message, const unsigned long long e, const unsigned long long n) {
    return pow(message, e) % n;
}

unsigned long long RSA::decrypt(const unsigned long long encryptedMessage, const unsigned long long d, const unsigned long long n) {
    return pow(encryptedMessage, d) % n;
}

只是为了确定它在 main.cpp 中的使用方式：

#include <iostream>
#include "cryptography.h"

int main(int argc, char const *argv[]) {
    unsigned long long n, d, e;
    if(!RSA::generateKeys(7, 13, n, d, e))
        return -1;
    std::cout << "n: " << n << std::endl;
    std::cout << "d: " << d << std::endl;
    std::cout << "e: " << e << std::endl;
    std::cout << std::endl;
    unsigned long long message;
    std::cin >> message;
    std::cout << "Message: " << message << std::endl;
    unsigned long long encryptedMessage = RSA::encrypt(message, e, n);
    std::cout << "Encrypted Message: " << encryptedMessage << std::endl;
    unsigned long long decryptedMessage = RSA::decrypt(encryptedMessage, d, n);
    std::cout << "Decrypted Message: " << decryptedMessage << std::endl;
}

Answer 1

正如@President James K. Polk 正确地猜到问题是无声的整数溢出。对于坚持这一点的任何人：太高的加密数据整数很容易导致小素数问题。

我使用 this 来替换 encrypt & decrypt 方法中的 pow(a, b) % c 调用 modularPow(a, b, c):

unsigned long long modularPow(const unsigned long long base, const unsigned long long exponent, const unsigned long long modulus) {
    unsigned long long result = 1;
    for(unsigned long long i = 0; i < exponent; i++) {
        result *= base;
        result %= modulus;
    }
    return result;
}

RSA 实现未正确解密

RSA-Implementation isn't decrypting correctly

c++

encryption

rsa

encryption-asymmetric