使用RSA公开密p=2,q=3求公钥和私钥

RSA加密算法是一种非对称加密技术，其安全性基于大数分解难题。对于给定的大素数p = 2和q = 3，我们可以按照以下步骤计算公钥和私钥：

1. **质因子乘积** (n): 公钥和私钥的基础是两个大素数的乘积，即 n = p * q = 2 * 3 = 6。

2. **欧拉函数 φ(n) (欧拉 totient 函数)**: 这是用来计算模n下可以整除的数的数量减去1，即 φ(n) = (p - 1) * (q - 1) = (2 - 1) * (3 - 1) = 2.

3. **欧拉 Totient 算法的倒数 e (公钥指数)**: 选择一个与 φ(n) 互质（最大公约数为1）的整数e，通常选择2到φ(n)之间的任何一个数，例如 e = 5（因为5和φ(6)=2互质）。然后找到e关于φ(n)的逆元d (私钥指数)，即 d * e ≡ 1 mod φ(n)。

4. **私钥 d (秘密指数)**: 计算d的具体值，这通常需要借助扩展欧几里得算法或者更复杂的数学工具，如中国剩余定理。

由于这里手动计算可能会很复杂，实际应用中会利用编程库来进行，例如Python的`cryptography`库。以下是简化的步骤展示：

import math

# 定义公钥参数
n = 6
phi_n = math.prod([p - 1, q - 1])  # 求欧拉函数
e = 5  # 公钥指数

# 找到私钥指数d
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = egcd(b % a, a)
        return gcd, y - (b // a) * x, x

d, _, _ = egcd(e, phi_n)
d %= phi_n  # 如果d太大，取余以保持在[0, phi_n)

# 公钥 (n, e)
public_key = (n, e)
# 私钥 (n, d)
private_key = (n, d)