Python中RSA加密算法的原理及实现步骤详细解析

RSA加密算法是一种非对称加密算法，常用于数据加密和数字签名。

原理：

1. 选择两个不同的大素数p和q，并计算它们的乘积n=p*q，作为RSA加密算法的模数。

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

3. 选择一个大于1且小于φ(n)的整数e作为公钥指数，确保e与φ(n)互质。

4. 计算d，使得(e*d) % φ(n) = 1，d作为私钥指数。

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

6. 加密消息m时，计算密文c = (m^e) % n。

7. 解密密文c时，计算明文m = (c^d) % n。

实现步骤：

1. 生成两个随机的大素数p和q。

2. 计算n=p*q，以及φ(n)=(p-1)*(q-1)。

3. 选择一个满足条件的公钥指数e，可以使用常见的指数值如65537。

4. 使用扩展欧几里德算法，计算私钥指数d。

5. 加密消息时，将消息转换成数值m，并计算密文c = (m^e) % n。

6. 解密密文时，计算明文m = (c^d) % n，并将数值m转换成原始消息。

例子：

import random

# 判断是否为素数
def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

# 生成大素数
def generate_prime():
    while True:
        num = random.randint(2**10, 2**11)  # 生成10-11位的随机数
        if is_prime(num):
            return num

# 扩展欧几里德算法
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    gcd, x, y = extended_gcd(b, a % b)
    return gcd, y, x - (a // b) * y

# 选择e
def choose_e(phi):
    e = random.randint(2, phi)  # 选择一个介于2到phi之间的随机数
    while math.gcd(e, phi) != 1:  # 要求e与phi互质
        e = random.randint(2, phi)
    return e

# RSA加密过程
def rsa_encrypt(message, public_key):
    e, n = public_key
    cipher = [pow(ord(char), e, n) for char in message]
    return cipher

# RSA解密过程
def rsa_decrypt(cipher, private_key):
    d, n = private_key
    message = ''.join([chr(pow(char, d, n)) for char in cipher])
    return message

# 生成RSA密钥对
def generate_rsa_key_pair():
    p = generate_prime()
    q = generate_prime()
    n = p * q
    phi = (p - 1) * (q - 1)
    e = choose_e(phi)
    gcd, d, _ = extended_gcd(e, phi)  # 计算私钥指数
    if d < 0:
        d += phi
    public_key = (e, n)
    private_key = (d, n)
    return public_key, private_key

# 示例
message = "Hello, world!"
public_key, private_key = generate_rsa_key_pair()
cipher = rsa_encrypt(message, public_key)
decrypted_message = rsa_decrypt(cipher, private_key)
print(decrypted_message)  # 输出：Hello, world!

在上述示例中，我们首先生成两个随机的素数p和q，并计算n和φ(n)。然后选择一个满足条件的公钥指数e，并使用扩展欧几里德算法计算私钥指数d。接下来，我们使用公钥对消息进行加密，并使用私钥对密文进行解密，最后还原出原始的消息。