Python实现RSA加密算法的步骤解析

RSA加密算法是一种非对称加密算法，主要用于数据的加密和解密。它是由三位数学家（Rivest、Shamir和Adleman）于1977年提出的，其安全性基于大数分解的困难性。

RSA算法的主要步骤如下：

1. 选择两个素数p和q：

随机选择两个大素数p和q，确保p不等于q。

2. 计算n和φ(n)：

计算n=p*q，然后计算φ(n)=(p-1)*(q-1)。

3. 选择公钥e：

选择一个公钥e，它满足1<e<φ(n)，且e和φ(n)互质。

4. 计算私钥d：

使用扩展欧几里得算法计算私钥d，使得(e*d)mod φ(n)=1。

5. 加密：

将明文m转化为整数M，然后使用公钥e对其进行加密，得到密文C：C=M^e mod n。

6. 解密：

使用私钥d对密文C进行解密，得到明文m：m=C^d mod n。

下面是使用Python实现RSA加密算法的例子：

import random
import math

# 选择两个素数
def choose_prime_number():
    primes = []
    for i in range(2, 100):
        is_prime = True
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
    p = random.choice(primes)
    primes.remove(p)
    q = random.choice(primes)
    return p, q

# 计算n和φ(n)
def compute_n_phi(p, q):
    n = p * q
    phi_n = (p - 1) * (q - 1)
    return n, phi_n

# 选择公钥e
def choose_public_key(phi_n):
    e = random.randint(2, phi_n - 1)
    while math.gcd(e, phi_n) != 1:
        e = random.randint(2, phi_n - 1)
    return e

# 扩展欧几里得算法计算私钥d
def compute_private_key(e, phi_n):
    x, y, gcd = extended_gcd(e, phi_n)
    if x < 0:
        x += phi_n
    return x

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

# 加密
def encrypt(m, e, n):
    return pow(m, e, n)

# 解密
def decrypt(c, d, n):
    return pow(c, d, n)

# 测试
def main():
    p, q = choose_prime_number()
    n, phi_n = compute_n_phi(p, q)
    e = choose_public_key(phi_n)
    d = compute_private_key(e, phi_n)
    m = random.randint(1, n - 1)
    c = encrypt(m, e, n)
    decrypted_m = decrypt(c, d, n)
    print("原始消息: ", m)
    print("加密后的消息: ", c)
    print("解密后的消息: ", decrypted_m)

if __name__ == '__main__':
    main()

以上代码实现了RSA加密算法的全部步骤。在主函数中，我们首先选择了两个素数p和q；然后计算了n和φ(n)；选择了公钥e，并计算了私钥d；接下来，我们随机生成一个明文m，并使用公钥e对其进行加密，得到密文c；最后，使用私钥d对密文c进行解密，得到了解密后的明文decrypted_m。