C++实现Rabin加密解密算法

Rabin加密算法是一种非对称加密算法，它可以用于加密和解密数据。下面是一个示例代码，演示了如何在C++中实现Rabin加密和解密算法。

#include <iostream>
#include <cmath>

// 快速幂模运算
long long mod_pow(long long base, long long exponent, long long modulus) {
    if (modulus == 1) {
        return 0;
    }
    long long result = 1;
    base = base % modulus;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

// Rabin加密函数
long long rabin_encrypt(long long message, long long p, long long q) {
    long long n = p * q;
    return mod_pow(message, 2, n);
}

// Rabin解密函数
long long rabin_decrypt(long long encrypted_message, long long p, long long q) {
    long long n = p * q;
    long long mp = mod_pow(encrypted_message, (p + 1) / 4, p);
    long long mq = mod_pow(encrypted_message, (q + 1) / 4, q);

    long long yp = mod_pow(p, (q - 1) / 2, q);
    long long yq = mod_pow(q, (p - 1) / 2, p);

    long long r = (mp * q * yq + mq * p * yp) % n;
    long long s = (mp * q * yq - mq * p * yp) % n;

    if (r < 0) {
        r += n;
    }
    if (s < 0) {
        s += n;
    }

    return r;
}

int main() {
    long long message = 123456;  // 要加密的消息
    long long p = 11;            // Rabin算法的第一个大素数
    long long q = 13;            // Rabin算法的第二个大素数

    // 加密
    long long encrypted_message = rabin_encrypt(message, p, q);
    std::cout << "加密后的消息: " << encrypted_message << std::endl;

    // 解密
    long long decrypted_message = rabin_decrypt(encrypted_message, p, q);
    std::cout << "解密后的消息: " << decrypted_message << std::endl;

    return 0;
}

上述代码中，rabin_encrypt函数用于加密消息，接受要加密的消息、两个大素数p和q作为输入，并返回加密后的结果。rabin_decrypt函数用于解密消息，接受加密后的消息、两个大素数p和q作为输入，并返回解密后的结果。

在主函数中，我们定义了要加密的消息message以及两个大素数p和q。然后，我们使用rabin_encrypt函数对消息进行加密，并将结果打印输出。接下来，我们使用rabin_decrypt函数对加密后的消息进行解密，并将解密后的结果打印输出。

请注意，Rabin加密算法对于加密和解密使用的素数p和q有一些特定的要求。在实际使用中，你需要选择足够大的素数，并确保它们满足算法的要求，以获得安全性和正确性。