加解密模式分析 - RSA 加密算法 | Alice and Bobの神秘小屋

RSA 加密算法，作为非对称加密的代表作之一，已经成为现代密码学中不可或缺的基石。它不仅在数据加密、数字签名等领域发挥着重要作用，还在互联网安全、电子商务等实际应用中得到了广泛的应用。

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

RSA 加密过程 😁

一天，Alice 想要向 Bob 发送一条秘密消息。为了确保消息的安全性，Alice 决定使用 RSA 加密算法。

首先，Bob 先选取两个大素数 $p$ 和 $q$，并计算它们的乘积 $n = p \times q$。
接着，Bob 计算 $\phi(n) = (p-1)(q-1)$，并选择一个整数 $e$，满足 $1 < e < \phi(n)$ 且 $\gcd(e, \phi(n)) = 1$。
最后，Bob 计算 $d$，使得 $d \equiv e^{-1} \mod \phi(n)$。
Bob 将公钥 $(e, n)$ 发送给 Alice，而私钥 $d$ 则被 Bob 保密。

当 Alice 收到 Bob 的公钥后，她可以使用 RSA 加密算法将消息 $M$ 加密成密文 $C$，计算公式如下：

$C \equiv M^e \mod n$

然后，Alice 将密文 $C$ 发送给 Bob。

Bob 收到密文后，可以使用 RSA 解密算法将其解密回原始消息 $M$，计算公式如下：

$C^d \equiv M^{ed} \equiv M \mod n$

RSA 加密数学原理 😇

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

在 RSA 加密过程中，选择合适的 $e$ 和 $d$ 是至关重要的。通常，$e$ 被选择为一个小的奇数（如 65537），以提高加密效率。而 $d$ 则通过扩展欧几里得算法计算得出，确保满足 RSA 的数学要求。

最后解密的原理是依据欧拉定理：对于任意与 $n$ 互质的整数 $a$，有 $a^{\phi(n)} \equiv 1 \mod n$。
由于 $ed \equiv 1 \mod \phi(n)$，因此

$M^{ed} \equiv M^{k \phi(n)+1} \equiv M^{k \phi} \cdot M \equiv 1^k \cdot M \equiv M \mod n$

其中 $k$ 是某个整数。

RSA 加密算法实现 🥰

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

from sage.all import random_prime, inverse_mod

# 这里是Bob生成公钥和私钥的过程
bits = 256 # 设置好的位数，生成足够大的素数
upper = pow(2,bits) # 上界
lower = pow(2,bits - 1) # 下界
p = random_prime(upper, lbound = lower)
q = random_prime(upper, lbound = lower)
n = p * q
phi_n = (p - 1) * (q - 1)
e = 65537 # 常用的公钥指数
d = inverse_mod(e, phi_n) # 计算私钥指数
public_key = (e, n)

# 这里是Alice加密消息的过程
M = "hello_Bob" # 待加密的消息
long_M = int.from_bytes(M.encode(), 'big') # 将消息转换为整数
C = pow(long_M, e, n) # 加密消息

# 这里是Bob解密消息的过程
decrypted_long_M = pow(C, d, n) # 解密消息
# 计算所需字节数
byte_len = (decrypted_long_M.bit_length() + 7) // 8
# 由于python和sage的整数类型不同，所以需要转换一下
M = int(decrypted_long_M)
flag = int.to_bytes(M, length=byte_len, byteorder='big').decode()
print(flag) # 输出解密后的消息

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

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

p = getPrime(256) # 生成256位的素数
q = getPrime(256) # 生成256位的素数
n = p * q
phi_n = (p - 1) * (q - 1)
e = 65537 # 常用的公钥指数
d = inverse(e, phi_n) # 计算私钥指数
public_key = (e, n)

M = "hello_Bob" # 待加密的消息
long_M = bytes_to_long(M.encode()) # 将消息转换为整数
C = pow(long_M, e, n) # 加密消息

decrypted_long_M = pow(C, d, n) # 解密消息
flag = long_to_bytes(decrypted_long_M).decode() # 将解密后的整数转换回字符串
print(flag)