创建公钥和私钥

公钥和私钥的生成依赖于模算术和互质数的数学性质。以下是如何创建公钥和私钥的步骤：

选择两个素数：为了生成公私钥对，必须选择两个不同的素数。例如，我们选择 p = 17 和 q = 23。
计算 n：计算这两个素数的乘积，n = p * q = 17 * 23 = 391。
计算 φ(n)：计算 n 的欧拉函数（φ(n)），它表示小于 n 且与 n 互质的正整数的个数。φ(n) = (p - 1) * (q - 1) = 16 * 22 = 352。
选择一个互质数 e：选择一个与 φ(n) 互质的数字 e。也就是说，e 与 φ(n) 的最大公约数应为 1。例如，选择 e = 5。
计算私钥 d：计算私钥 d，它是 e 对 φ(n) 的模逆（即 d * e ≡ 1 (mod φ(n))）。在本例中，d = 141。
生成公钥和私钥对：公钥为 (n, e)，私钥为 (n, d)。

加密和解密过程

1. 加密：要使用公钥 (n, e) 加密消息 m，我们首先将消息转换为数字 m。然后，应用加密函数生成加密后的消息 C。
2. 解密：使用私钥 (n, d) 解密加密消息 C，我们应用解密函数来恢复原始消息 m。

例如，假设我们要使用公钥 (391, 5) 加密消息 M = HELLO。首先，将消息转换为数字 m = 72736576（通过 ASCII 编码）。然后应用加密函数。最后，使用私钥 (391, 141) 解密，得到原始消息 HELLO。

代码实现

以下是实现公钥和私钥生成，以及加密和解密过程的 Python 代码示例。

这个实现使用了上面提到的步骤：

# 导入必要的库
import random

# 辅助函数：扩展欧几里得算法，用来计算模逆
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y

# 辅助函数：计算模逆
def mod_inverse(e, phi):
    gcd, x, y = extended_gcd(e, phi)
    if gcd != 1:
        raise ValueError("e 和 φ(n)不互质，无法计算模逆")
    return x % phi

# 步骤1: 选择两个素数 p 和 q
p = 17
q = 23

# 步骤2: 计算 n
n = p * q  # n = p * q
print(f"n = {n}")

# 步骤3: 计算 φ(n)
phi_n = (p - 1) * (q - 1)  # φ(n) = (p - 1) * (q - 1)
print(f"φ(n) = {phi_n}")

# 步骤4: 选择一个互质数 e，通常选择较小的素数
e = 5
print(f"选择 e = {e}")

# 步骤5: 计算私钥 d，d 是 e 对 φ(n) 的模逆
d = mod_inverse(e, phi_n)
print(f"计算私钥 d = {d}")

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

print(f"公钥: {public_key}")
print(f"私钥: {private_key}")

# 加密函数
def encrypt(message, public_key):
    n, e = public_key
    encrypted_message = [pow(ord(char), e, n) for char in message]  # 使用 pow 来计算 m^e % n
    return encrypted_message

# 解密函数
def decrypt(encrypted_message, private_key):
    n, d = private_key
    decrypted_message = ''.join([chr(pow(char, d, n)) for char in encrypted_message])  # 使用 pow 来计算 C^d % n
    return decrypted_message

# 测试加密解密过程
message = "HELLO，DHub"
print(f"原始消息: {message}")

# 加密
encrypted_message = encrypt(message, public_key)
print(f"加密后的消息: {encrypted_message}")

# 解密
decrypted_message = decrypt(encrypted_message, private_key)
print(f"解密后的消息: {decrypted_message}")

代码解释

展欧几里得算法 (extended_gcd)：用来计算两个数的最大公约数 (GCD)，以及计算模逆。
生成公钥和私钥：首先选择两个素数 p 和 q，然后计算它们的乘积 n 和欧拉函数 φ(n)，接着选择一个和 φ(n) 互质的数 e，最后计算私钥 d。
加密和解密过程：通过加密函数将消息的每个字符转换为数字，然后通过公钥进行加密；解密时通过私钥恢复原始的消息。

输出

说明

加密：我们将消息 HELLO 转换为 ASCII 码，然后对每个字符使用 m^e % n 进行加密。
解密：通过私钥 d 使用 C^d % n 进行解密，恢复出原始消息 HELLO。

数学原理如何确保安全

为什么使用素数？

公钥密码学中使用素数是因为将大数字分解为其素因数非常困难。即使对于非常大的素数，计算其因数的代价也很高。这个性质保证了加密算法的安全性。

什么是互质数？

如果两个正整数除了 1 之外没有其他共同因数，那么它们是互质的。例如，2 和 3 是互质的，因为它们的唯一公因数是 1，而 4 和 6 不是互质的，因为它们有公因数 2。

乘法逆元与模逆元是什么？

乘法逆元是指与一个数字相乘得到 1 的数字。例如，2 的乘法逆元是 12，因为 2 乘以 12 等于 1。在模运算中，乘法逆元是指满足的数字 d。

为什么使用欧拉的 Totient 函数（）？

表示小于 n 且与 n 互质的正整数的个数。欧拉定理指出，如果 p 和 q 是互质数，那么 q 的次幂对 n 取模的结果等于 1。这个定理为公钥密码学提供了数学基础，确保了加密和解密过程的可行性。

欧拉定理的应用

欧拉定理提供了一种巧妙的方法来“撤销”加密过程。当有人使用公钥加密消息时，他们会将消息的数字形式提高到公钥的幂，然后对 n 取模。解密时，接收者将加密后的消息提高到私钥的幂，再对 n 取模，恢复原始消息。欧拉定理保证了这一过程能够准确还原原始消息。

总结

公钥密码学依赖于欧拉定理和相关的数学原理，确保了在现代数字通信中可以安全地加密和解密信息。

通过公钥和私钥的密切关联，我们可以保证只有特定的接收者能解密信息，而不会被第三方破解。

这些数学机制的应用使得现代数据安全技术能够发挥作用，为网络安全提供坚实的保障。

四时宝库

程序员的知识宝库

公钥密码学中的数学原理:模运算与互质概念