RSA密钥生成与使用的Python实现

RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，它是通过两个不同的密钥进行加解密的。

RSA密钥生成的步骤如下：

1. 选择两个不同的质数p和q，计算它们的乘积n=p*q。

2. 计算n的欧拉函数φ(n)=(p-1)*(q-1)。

3. 选择一个整数e，使得1< e < φ(n)，并且e与φ(n)互质。

4. 计算d，使得(d * e) mod φ(n) = 1。

5. 公钥为(n,e)，私钥为(n,d)。

下面是一个Python实现RSA密钥生成的例子：

import random

def check_prime(n):
    """
    判断一个数是否为质数
    """
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def generate_prime(bits):
    """
    生成一个指定位数的质数
    """
    while True:
        p = random.getrandbits(bits)
        if check_prime(p):
            return p

def gcd(a, b):
    """
    求两个数的最大公约数
    """
    while b != 0:
        a, b = b, a % b
    return a

def mod_inverse(a, m):
    """
    求a的模反元素，即a关于模m的乘法逆元
    """
    if gcd(a, m) != 1:
        return None
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m

def generate_keypair(bits):
    """
    生成RSA密钥对
    """
    p = generate_prime(bits // 2)
    q = generate_prime(bits // 2)
    n = p * q
    phi_n = (p - 1) * (q - 1)
    e = random.randint(1, phi_n)
    while gcd(e, phi_n) != 1:
        e = random.randint(1, phi_n)
    d = mod_inverse(e, phi_n)
    return (n, e), (n, d)

下面是一个使用生成的RSA密钥对进行加解密的例子：

def encrypt(plaintext, public_key):
    """
    使用公钥加密明文
    """
    n, e = public_key
    ciphertext = [pow(ord(char), e, n) for char in plaintext]
    return ciphertext

def decrypt(ciphertext, private_key):
    """
    使用私钥解密密文
    """
    n, d = private_key
    plaintext = ''.join([chr(pow(char, d, n)) for char in ciphertext])
    return plaintext

# 生成RSA密钥对
public_key, private_key = generate_keypair(1024)

# 加密明文
plaintext = "Hello, RSA!"
ciphertext = encrypt(plaintext, public_key)
print("Ciphertext:", ciphertext)

# 解密密文
decrypted_plaintext = decrypt(ciphertext, private_key)
print("Decrypted Plaintext:", decrypted_plaintext)

这个例子演示了RSA密钥的生成过程和使用生成的密钥对进行加解密的过程。首先使用 generate_keypair 函数生成RSA密钥对，然后使用生成的公钥对明文进行加密得到密文，使用私钥对密文进行解密得到明文。