Python实现一个简单的RSA，对密文进行加密与解密

RSA加密算法是一种非对称加密算法，常用于数据加密和数字签名。下面是一个简单的RSA实现，包括密钥生成、加密和解密三个步骤。

1. 密钥生成

RSA算法需要一对公私钥对，公钥可以公开，私钥必须保密。下面是一个简单的密钥生成过程：

import random

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

def gen_key(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = random.randrange(1, phi)
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)
    d = pow(e, -1, phi)
    return ((e, n), (d, n))

其中，p和q是两个随机的质数，n=p*q是公钥的一部分，phi=(p-1)*(q-1)是欧拉函数的值，e是公钥的另一部分，要求1<e<phi且gcd(e,phi)=1，d是私钥，满足d*e=1 mod phi。

2. 加密

假设要加密的明文M是一个整数，公钥是(e,n)，则密文C=M^e mod n。

def encrypt(msg, public_key):
    e, n = public_key
    return pow(msg, e, n)

3. 解密

密文C经过私钥(d,n)解密，得到明文M=C^d mod n。

def decrypt(cipher, private_key):
    d, n = private_key
    return pow(cipher, d, n)

完整代码如下：

import random

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

def gen_key(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = random.randrange(1, phi)
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)
    d = pow(e, -1, phi)
    return ((e, n), (d, n))

def encrypt(msg, public_key):
    e, n = public_key
    return pow(msg, e, n)

def decrypt(cipher, private_key):
    d, n = private_key
    return pow(cipher, d, n)

if __name__ == '__main__':
    p = 61
    q = 53
    public_key, private_key = gen_key(p, q)
    print('公钥：', public_key)
    print('私钥：', private_key)
    msg = 123456
    cipher = encrypt(msg, public_key)
    print('密文：', cipher)
    plain = decrypt(cipher, private_key)
    print('明文：', plain)

注意，该代码实现仅供学习参考，不建议在实际情况下使用，因为RSA实现要考虑到更多的安全性问题。