RSA加密解密算法示例：详解步骤与过程

本文将以p=5，q=11为例，详细介绍RSA加密解密算法的步骤，包括密钥生成、分组加密、密文解密，并附带代码示例，帮助读者深入理解RSA算法原理。

1. 密钥生成

1.1 计算n与p(n)的值：

n = p * q = 5 * 11 = 55 p(n) = (p-1) * (q-1) = 4 * 10 = 40

1.2 计算解密指数d的值：

根据扩展欧几里得算法，找到满足 e * d ≡ 1 (mod p(n)) 的 d 值。 40 * 1 + 7 * (-5) = 1，所以 d = -5，但为了保证 d 为正数，我们可以加上 p(n) 得到最小正整数解。 d = -5 + 40 = 35

2. 分组加密

2.1 将消息 m 分组，每个分组小于 n。 m = 531953，分组为 {53, 19, 53}。

2.2 加密过程：密文 c = m^e (mod n) c1 = 53^7 (mod 55) = 46 c2 = 19^7 (mod 55) = 14 c3 = 53^7 (mod 55) = 46

加密后的密文为 {46, 14, 46}。

3. 恢复明文

3.1 明文 m = c^d (mod n) m1 = 46^35 (mod 55) = 53 m2 = 14^35 (mod 55) = 19 m3 = 46^35 (mod 55) = 53

3.2 恢复的明文为 {53, 19, 53}，即原始消息 m = 531953。

代码示例

p = 5
q = 11
e = 7

n = p * q
pn = (p-1) * (q-1)

# 计算解密指数d
d = pow(e, -1, pn)

# 分组加密
m = 531953
message_groups = [int(str(m)[i:i+2]) for i in range(0, len(str(m)), 2)]
ciphertext = [pow(group, e, n) for group in message_groups]

# 恢复明文
plaintext = [pow(c, d, n) for c in ciphertext]

print(f'密文：{ciphertext}')
print(f'明文：{plaintext}')

总结

本文以一个简单的例子详细介绍了RSA加密解密算法的步骤，包括密钥生成、分组加密、密文解密，并附带代码示例。读者可以通过本文深入理解RSA算法原理，并将其应用于实际的加密场景中。