实验二rsa公钥加密技术

RSA 公钥加密技术是一种非对称加密算法，由三个部分组成：密钥生成、加密和解密。

密钥生成：
1. 随机选择两个大质数 p 和 q。
2. 计算 n = p * q。
3. 计算欧拉函数 φ(n) = (p - 1) * (q - 1)。
4. 随机选择一个整数 e，1 < e < φ(n)，且 e 和 φ(n) 互质。
5. 计算整数 d，满足 (d * e) % φ(n) = 1。即 d 是 e 在模 φ(n) 意义下的逆元。
6. 公钥为 (n, e)，私钥为 (n, d)。

加密：
1. 将明文 M 转换为整数 m，0 <= m < n。
2. 计算密文 C = m^e % n。

解密：
1. 计算明文 M = C^d % n。

下面是 Python 实现：

import random

def generate_key(p, q):
    n = p * q
    phi_n = (p - 1) * (q - 1)
    e = random.randint(2, phi_n - 1)
    while gcd(e, phi_n) != 1:
        e = random.randint(2, phi_n - 1)
    d = modinv(e, phi_n)
    public_key = (n, e)
    private_key = (n, d)
    return public_key, private_key

def encrypt(public_key, m):
    n, e = public_key
    c = pow(m, e, n)
    return c

def decrypt(private_key, c):
    n, d = private_key
    m = pow(c, d, n)
    return m

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError('Modular inverse does not exist')
    return x % m

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        g, x, y = extended_gcd(b, a % b)
        return g, y, x - (a // b) * y

# 选择两个大质数
p = 997
q = 991
public_key, private_key = generate_key(p, q)

# 加密
m = 123456789
c = encrypt(public_key, m)
print('密文:', c)

# 解密
m = decrypt(private_key, c)
print('明文:', m)

注意，这里使用了扩展欧几里得算法来计算模反元素。同时，由于 RSA 加密算法使用的是大整数计算，因此需要使用 Python 中的 pow() 函数来计算幂取模。