#include <iostream> #include <cmath> using namespace std; int gcd(int a, int b) { if (a == 0) { return b; } return gcd(b % a, a); } int main() { int p, q, n, e, d, phi, m, c, decrypted_msg; cout << "Enter two prime numbers p and q: "; cin >> p >> q; n = p * q; phi = (p - 1) * (q - 1); cout << "Enter a value for e such that gcd(e, phi(n)) = 1: "; cin >> e; while (gcd(e, phi) != 1) { cout << "Invalid value for e. Enter another value: "; cin >> e; } // Calculate the value of d d = 0; for (int i = 1; i <= phi; i++) { if (((i * e) % phi) == 1) { d = i; break; } } cout << "Public key: (" << n << ", " << e << ")" << endl; cout << "Private key: (" << n << ", " << d << ")" << endl; cout << "Enter a message to encrypt: "; cin >> m; c = pow(m, e); c %= n; cout << "Encrypted message: " << c << endl; decrypted_msg = pow(c, d); decrypted_msg %= n; cout << "Decrypted message: " << decrypted_msg << endl; return 0; }python实现

这是一个用 C++ 编写的 RSA 加密算法的程序，可以实现输入两个质数 p 和 q，然后根据这两个质数计算出公钥和私钥，最后对输入的消息进行加密和解密。

以下是 Python 实现的代码：

import math

def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)

p = int(input("Enter the first prime number p: "))
q = int(input("Enter the second prime number q: "))

n = p * q
phi = (p - 1) * (q - 1)

e = int(input("Enter a value for e such that gcd(e, phi(n)) = 1: "))
while gcd(e, phi) != 1:
    e = int(input("Invalid value for e. Enter another value: "))

d = 0
for i in range(1, phi+1):
    if (i * e) % phi == 1:
        d = i
        break

print("Public key: ({}, {})".format(n, e))
print("Private key: ({}, {})".format(n, d))

m = int(input("Enter a message to encrypt: "))
c = pow(m, e) % n
print("Encrypted message: {}".format(c))

decrypted_msg = pow(c, d) % n
print("Decrypted message: {}".format(decrypted_msg))

注意，在 Python 中，求幂的方法使用 `pow(base, exponent, modulus)`，其中 `modulus` 是求幂的模数。