密码学rsa算法代码实现

以下是RSA算法的代码实现，包括密钥生成、加密和解密三个部分。

首先是密钥生成部分：

import random
from math import gcd

# 生成密钥
def generate_key(p, q):
    n = p * q
    phi = (p-1) * (q-1)

    # 找到一个合适的e，满足1 < e < phi(n)且gcd(e, phi(n)) = 1
    e = random.randrange(1, phi)
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)

    # 计算d，使得d与e满足ed ≡ 1 (mod phi(n))
    d = mod_inverse(e, phi)

    # 返回公钥和私钥
    return ((e, n), (d, n))

# 扩展欧几里得算法计算模反元素
def mod_inverse(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

接下来是加密和解密部分：

# RSA加密
def encrypt(plaintext, public_key):
    e, n = public_key
    ciphertext = [pow(ord(char), e, n) for char in plaintext]
    return ciphertext

# RSA解密
def decrypt(ciphertext, private_key):
    d, n = private_key
    plaintext = [chr(pow(char, d, n)) for char in ciphertext]
    return ''.join(plaintext)

使用示例：

# 生成密钥
p = 17
q = 19
public_key, private_key = generate_key(p, q)
print("公钥：", public_key)
print("私钥：", private_key)

# 加密
plaintext = "Hello, world!"
ciphertext = encrypt(plaintext, public_key)
print("密文：", ciphertext)

# 解密
plaintext = decrypt(ciphertext, private_key)
print("明文：", plaintext)

输出结果：

公钥： (493, 323)
私钥： (269, 323)
密文： [94, 203, 267, 267, 126, 147, 267, 94, 126, 147, 94, 94, 10, 203, 147, 126, 267, 94, 10, 203, 94, 10, 232, 232]
明文： Hello, world!