Rabin 加密算法是一种基于大数分解问题的非对称加密算法。它由 Michael O. Rabin 在 1979 年提出，具有与 RSA 类似的安全性，但在某些方面具有更高的效率。

在本章中，我们将深入分析 Rabin 加密算法的核心原理和实现细节。我们将从 Rabin 的数学基础开始，逐步揭示其加密和解密过程中的关键步骤。通过对 Rabin 算法的详细解析，你将能够理解它是如何利用大数分解的困难性来确保数据安全的。

Rabin 加密过程 😁

Rabin 加密算法的加密过程与 RSA 类似，甚至我们可以将其视为 RSA 的一个特例。

既然前面已经介绍了 RSA 的加密过程，我们直接点明 Rabin 加密算法的加密不同之处：

在选择公钥时，Rabin 加密算法选择 $e = 2$，而不是 RSA 中常用的 $e = 65537$。

因此，Rabin 的加密公式如下：

其中 $n = p \times q$，$p$ 和 $q$ 是两个大素数。

Rabin 加密数学原理 😇

Rabin 加密算法的安全性同样基于大数分解的困难性。对于一个足够大的 $n$，分解 $n$ 成其素因数 $p$ 和 $q$ 是非常困难的。这意味着攻击者无法轻易地从公钥 $(2, n)$ 中推断出私钥，从而无法解密密文。

Rabin 加密算法的解密过程相较于 RSA 更为复杂，因为平方根的计算比指数运算更为困难。具体来说，解密过程需要计算 $C$ 的平方根，这涉及到求解二次剩余问题。

而且，Rabin 加密算法的解密结果经过中国剩余定理（CRT）合并后有四个不同的平方根，因此需要额外的信息来确定正确的解密结果，当然一般情况下直接将所有结果都输出就行。

我们可以直接使用 Tonelli-Shanks 算法 来计算平方根，或者在选择 $p$ 和 $q$ 时满足 $p \equiv 3 \mod 4$ 和 $q \equiv 3 \mod 4$，这样可以简化平方根的计算过程。

Rabin 加密算法实现 🥰

下面是一个简单的 Rabin 加密算法的 Python 实现示例：

from sage.all import random_prime, crt

#  Bob 密钥生成阶段
bits = 256
upper = pow(2, bits)
lower = pow(2, bits - 1)
# 生成满足 p ≡ 3 mod 4, q ≡ 3 mod 4 的素数，简化平方根计算
while True:
    p = random_prime(upper, lbound=lower)
    if p % 4 == 3:
        break
while True:
    q = random_prime(upper, lbound=lower)
    if q % 4 == 3 and q != p:
        break
n = p * q
e = 2
public_key = (e, n)
private_key = (p, q)

# Alice 加密阶段
M = "hello_Bob"
long_M = int.from_bytes(M.encode(), 'big')
C = pow(long_M, e, n)

#  Bob 解密阶段 
# 1. 计算模p和模q下的所有平方根（共2×2=4种组合）
# 因为 p, q ≡ 3 mod 4，直接用公式计算平方根
mp1 = pow(C, (p + 1) // 4, p)
mp2 = p - mp1
mq1 = pow(C, (q + 1) // 4, q)
mq2 = q - mq1
print(f"模p的平方根: {mp1}, {mp2}")
print(f"模q的平方根: {mq1}, {mq2}")

# 2. 用CRT合并4种组合，得到4个候选明文
candidates = [
    crt([mp1, mq1], [p, q]),
    crt([mp1, mq2], [p, q]),
    crt([mp2, mq1], [p, q]),
    crt([mp2, mq2], [p, q])
]

# 3. 遍历候选值，还原出正确的明文
for candidate in candidates:
    # 转换为 Python 原生 int 后再转 bytes
    cand_int = int(candidate)
    candidate_bytes = cand_int.to_bytes((cand_int.bit_length() + 7) // 8, byteorder='big')
    try:
        # 尝试用 utf-8 解码
        flag = candidate_bytes.decode()
        print(flag)
    except UnicodeDecodeError:
        # 解码失败时跳过这个候选值
        continue

实际上由于 sage 中的整数类型和 python 中的整数类型不同，所以在非必要情况下不要纯使用sage函数进行算法实现，可以多使用python的密码学库使用。
以下是一个实现：

from Crypto.Util.number import getPrime, inverse, long_to_bytes, bytes_to_long

# Bob 密钥生成阶段
p = getPrime(256)
while p % 4 != 3:
    p = getPrime(256)
q = getPrime(256)
while q % 4 != 3 or q == p:
    q = getPrime(256)
n = p * q
e = 2
public_key = (e, n)
private_key = (p, q)

# Alice 加密阶段
M = "hello_Bob"
long_M = bytes_to_long(M.encode())
# 重要：确保明文的平方小于n，否则加密会出错
C = pow(long_M, e, n)

# Bob 解密阶段
mp1 = pow(C, (p + 1) // 4, p)
mp2 = (p - mp1) % p
mq1 = pow(C, (q + 1) // 4, q)
mq2 = (q - mq1) % q

# 修复CRT计算逻辑
inv_q_mod_p = inverse(q, p)  # q在模p下的逆元
inv_p_mod_q = inverse(p, q)  # p在模q下的逆元

candidates = [
    (mp1 * q * inv_q_mod_p + mq1 * p * inv_p_mod_q) % n,
    (mp1 * q * inv_q_mod_p + mq2 * p * inv_p_mod_q) % n,
    (mp2 * q * inv_q_mod_p + mq1 * p * inv_p_mod_q) % n,
    (mp2 * q * inv_q_mod_p + mq2 * p * inv_p_mod_q) % n,
]

# 遍历候选值，还原出正确的明文
flag = None  # 初始化flag
for idx, candidate in enumerate(candidates):
    try:
        # 尝试解码
        decoded_str = long_to_bytes(candidate).decode()
        # 只有成功解码的才赋值给flag
        flag = decoded_str
        print(flag)
    except (UnicodeDecodeError, ValueError):
        continue

上一章：加解密模式分析 - RSA 加密算法 👈
下一章：加解密模式分析 - ElGamal 加密算法 👈
回到开始：关于我 👈

相关链接：
密码学数学基础 - 同余关系与模运算 👈
密码学数学基础 - 二次剩余 👈
密码学算法 - 中国剩余定理CRT 👈
密码学算法 - Tonelli-Shanks算法 👈