RSA算法是一种基于大数分解困难性的非对称加密算法，其安全性依赖于大整数素因子分解的数学难题。下面详细解析其原理、密钥生成及加解密的每一个步骤。

一、 RSA算法核心原理与数学基础

RSA的核心在于利用模幂运算的单向性：已知公钥(E, N)和明文M，计算密文C = M^E mod N是容易的；但反过来，仅已知C、E、N，想反推出明文M则极其困难，除非知道私钥D。其数学基础主要依赖于欧拉定理：若正整数a与n互质，则 a^(φ(n)) ≡ 1 (mod n)，其中φ(n)是欧拉函数，表示小于n且与n互质的正整数的个数。

对于一个由两个不同质数p和q相乘得到的大整数N = p * q，其欧拉函数值φ(N) = (p-1)*(q-1)。

二、 密钥生成步骤详解

密钥生成是RSA算法的起点，直接决定了后续加解密能否正确进行。

1. 选择两个大质数 p 和 q

   • 要求：p 和 q 必须足够大、随机且不同，以保障安全性。通常使用安全素数或通过概率性素数测试（如Miller-Rabin）生成。
   • 示例：为便于演示，选取 p = 61, q = 53。

2. 计算模数 N

   • 公式：N = p * q
   • 作用：N 是公钥和私钥共有的部分，其长度（比特数）即为密钥长度（如2048位）。
   • 示例计算：N = 61 * 53 = 3233。

3. 计算欧拉函数 φ(N)

   • 公式：φ(N) = (p-1) * (q-1)
   • 作用：用于后续计算私钥指数D。
   • 示例计算：φ(3233) = (61-1) * (53-1) = 60 * 52 = 3120。

4. 选择公钥指数 E

   • 要求：
     1. 1 < E < φ(N)
     2. E 与 φ(N) 必须互质（即 gcd(E, φ(N)) = 1）。
   • 常见取值：为便于计算，常取 E = 65537 (0x10001)，这是一个素数，且在二进制表示中只有两个1，能有效加速模幂运算。
   • 示例选择：选取 E = 17（因为17与3120互质）。

5. 计算私钥指数 D

   • 要求：D 是 E 对于模 φ(N) 的模反元素（或模逆元）。即满足：(E * D) mod φ(N) = 1。
   • 计算方法：通常使用扩展欧几里得算法求解。该算法能找到整数 D 和 k，使得 E*D + k*φ(N) = 1，从而 D 即为 E mod φ(N) 的逆元。
   • 示例计算：已知 E=17, φ(N)=3120，求解 17*D mod 3120 = 1。通过计算可得 D = 2753（因为 17 * 2753 = 46801, 46801 mod 3120 = 1）。

至此，密钥对生成完毕：

• 公钥 (Public Key)：由 (E, N) 组成，即 (17, 3233)。
• 私钥 (Private Key)：由 (D, N) 组成，即 (2753, 3233)。必须严格保密的 p, q, φ(N) 在生成D后应被安全销毁。

三、 加密与解密步骤详解

假设发送方Alice想给拥有上述公钥的Bob发送一条消息M。

1. 加密过程 (由发送方执行)

• 输入：明文 M，接收方的公钥 (E, N)。
• 要求：明文 M 必须是整数，且满足 0 ≤ M < N。如果M是文本或数据，需先通过编码（如OAEP填充）转换为满足条件的整数。
• 操作：计算密文 C = M^E mod N。这是一个模幂运算。
• 输出：密文 C。

# RSA 加密函数示例 (仅演示核心运算，未包含填充)
def rsa_encrypt(M, E, N):
    """
    使用公钥(E, N)加密明文M
    :param M: 明文整数
    :param E: 公钥指数
    :param N: 模数
    :return: 密文整数C
    """
    # 使用内置的pow函数进行模幂运算，效率高于 (M**E) % N
    C = pow(M, E, N)
    return C

# 示例：使用上述生成的公钥(17, 3233)加密明文M=65
public_key_E = 17
public_key_N = 3233
plaintext_M = 65

ciphertext_C = rsa_encrypt(plaintext_M, public_key_E, public_key_N)
print(f"明文 M = {plaintext_M}")
print(f"加密后密文 C = {ciphertext_C}")  # 输出应为 2790

参考计算： 65^17 mod 3233 = 2790。

2. 解密过程 (由接收方执行)

• 输入：密文 C，自己的私钥 (D, N)。
• 操作：计算明文 M' = C^D mod N。这同样是一个模幂运算。
• 输出：恢复的明文 M'。理论上 M' 应等于原始的 M。
• 数学原理：根据加密公式 C ≡ M^E (mod N)，解密时 C^D ≡ (M^E)^D ≡ M^(E*D) (mod N)。由于 E*D ≡ 1 (mod φ(N))，即 E*D = k*φ(N) + 1，根据欧拉定理，若 M 与 N 互质，则 M^(φ(N)) ≡ 1 (mod N)，因此 M^(E*D) ≡ M^(k*φ(N)+1) ≡ (M^(φ(N)))^k * M ≡ 1^k * M ≡ M (mod N)。即使 M 与 N 不互质，该结论依然成立。

# RSA 解密函数示例
def rsa_decrypt(C, D, N):
    """
    使用私钥(D, N)解密密文C
    :param C: 密文整数
    :param D: 私钥指数
    :param N: 模数
    :return: 明文整数M
    """
    M = pow(C, D, N)
    return M

# 示例：使用私钥(2753, 3233)解密密文C=2790
private_key_D = 2753
private_key_N = 3233 # 与公钥N相同
ciphertext_C = 2790

decrypted_M = rsa_decrypt(ciphertext_C, private_key_D, private_key_N)
print(f"密文 C = {ciphertext_C}")
print(f"解密后明文 M' = {decrypted_M}")  # 输出应为 65，与原始明文一致

四、 关键特性与注意事项

综上所述，RSA算法通过巧妙的数论构造，实现了公钥加密和私钥解密的非对称过程。其安全性根植于大数分解的困难性，而加解密的核心操作是高效的模幂运算。在实际应用中，必须结合安全的填充方案和足够长的密钥来保障其安全性。

参考来源

• RSA加密算法详解及例题
• RSA加密算法原理
• RSA公钥密码算法的原理及实现(一)
• RSA非对称加密算法详解
• 带你彻底理解RSA算法原理
• RSA公钥密码算法的原理及实现(一)