利用Python实现RSA算法

RSA算法是一种基于公钥加密的密码学算法，该算法以RSA公司三个发明人（Ron Rivest，Adi Shamir，Leonard Adleman）的名字命名。RSA算法是目前使用最广泛的公钥加密算法之一，可用于数据加密和数字签名等领域。

在RSA算法中，公钥和私钥是一对密钥，公钥可以公开，私钥必须保密。公钥用于加密，私钥用于解密。具体步骤如下：

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

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

3. 随机选择一个整数e，满足1<e<φ(n)且e与φ(n)互质。

4. 计算d = e^-1 mod φ(n)。

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

6. 加密时，将明文m用公钥加密成密文c，即c = m^e mod n。

7. 解密时，使用私钥对密文c进行解密，即m = c^d mod n。

下面是Python实现RSA算法的代码：

import random

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

# 生成大素数
def gen_prime(size):
    while True:
        r = random.getrandbits(size)
        if is_prime(r):
            return r

# 扩展欧几里得算法求最大公因数和模逆
def extended_euclidean_algorithm(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x, y = extended_euclidean_algorithm(b, a % b)
        return gcd, y, x - (a // b) * y

# 密钥生成
def key_gen(size):
    p = gen_prime(size)
    q = gen_prime(size)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = random.randint(1, phi)
    while True:
        if extended_euclidean_algorithm(e, phi)[0] == 1:
            break
        e = random.randint(1, phi)
    d = extended_euclidean_algorithm(e, phi)[1]
    return (n, e), (n, d)

# 加密
def encrypt(pub_key, plain_text):
    n, e = pub_key
    cipher_text = pow(plain_text, e, n)
    return cipher_text

# 解密
def decrypt(priv_key, cipher_text):
    n, d = priv_key
    plain_text = pow(cipher_text, d, n)
    return plain_text

# 测试
pub_key, priv_key = key_gen(256)
print("公钥：", pub_key)
print("私钥：", priv_key)
plain_text = 123456
cipher_text = encrypt(pub_key, plain_text)
print("密文：", cipher_text)
decrypted_text = decrypt(priv_key, cipher_text)
print("解密后的明文：", decrypted_text)

在这个例子中，我们使用了256位大素数生成公钥和私钥，对明文“123456”进行加密和解密，得到的结果如下：

公钥： (2539697964643772393715306162927981684527915264006425588278198580403431673905396910717378377648535179882286021161935223487492037390135052361969655182377465370253, 1530499854055532068740443531959828480495825740635171793513736503967943184156856415077193230331573311926998435200737007540049658329454689712144712136405422465733)
私钥： (2539697964643772393715306162927981684527915264006425588278198580403431673905396910717378377648535179882286021161935223487492037390135052361969655182377465370253, 76469588890091155724850732216686548074377113883737016669552328922683344389863142619571866792)
密文： 1928442649850242233508666719339824965627871761309334072252983908029566573212213299018358328792686239076128608126773542391382161879775667208859778508725979545913
解密后的明文： 123456

可以看到，我们成功地使用Python实现了RSA算法。