1. 项目概述与密码学入门

如果你对编程和网络安全感兴趣，那么“TheAlgorithms-Python”这个仓库绝对是个宝库。它用Python实现了从古至今、从简单到复杂的各种算法，而其中的密码学部分，更是理解现代数字安全基石的一扇绝佳窗口。今天，我们不谈枯燥的理论，就从最经典的凯撒密码出发，一路拆解到支撑起互联网信任体系的RSA非对称加密，看看如何用Python亲手实现它们。这不仅是编程练习，更是理解我们每天使用的HTTPS、SSH、数字签名背后逻辑的绝佳途径。

密码学远不止于“加密解密”四个字。它是一门关于秘密通信的艺术与科学，核心目标是在不安全的信道上实现安全的信息传递。TheAlgorithms-Python中的实现，为我们提供了从古典密码的直观体验到现代密码数学美的完整学习路径。无论你是准备参加CTF（夺旗赛）的学生，还是希望夯实基础的开发者，或是单纯对“加密”感到好奇的爱好者，跟着这些代码走一遍，都能获得远超API调用的深刻理解。我们将重点关注算法原理、Python实现的关键细节，以及在实际编码中容易踩到的“坑”。

2. 古典密码基石：凯撒密码的Python实现与深度解析

凯撒密码堪称密码学的“Hello World”。其原理简单到极致：将明文中的每个字母按照字母表顺序偏移一个固定的位数，生成密文。例如，偏移3位时，A变成D，B变成E，以此类推，Z之后循环回A。

2.1 核心算法实现与代码精读

在TheAlgorithms-Python中，凯撒密码的实现通常干净利落。我们先来看一个典型的实现框架，并逐行解析其背后的设计考量。

def caesar_cipher(text: str, shift: int, mode: str = ‘encrypt’) -> str:
    “””
    实现凯撒密码的加密或解密。
    
    参数:
        text: 待处理的文本（明文或密文）。
        shift: 偏移量，应为整数。
        mode: ‘encrypt’ 或 ‘decrypt’。
    
    返回:
        处理后的字符串。
    “””
    if not isinstance(shift, int):
        raise TypeError(“偏移量必须为整数”)
    
    # 解密本质上是反向加密
    if mode == ‘decrypt’:
        shift = -shift
    
    result = []
    for char in text:
        if char.isupper():
            # 处理大写字母：A的ASCII码是65
            new_char = chr((ord(char) - 65 + shift) % 26 + 65)
            result.append(new_char)
        elif char.islower():
            # 处理小写字母：a的ASCII码是97
            new_char = chr((ord(char) - 97 + shift) % 26 + 97)
            result.append(new_char)
        else:
            # 非字母字符原样保留
            result.append(char)
    return ‘’.join(result)

这段代码虽然简短，但蕴含了几个关键的设计点：

  1. 函数签名清晰 ：使用类型注解（ text: str ）提高了代码可读性。 mode 参数用一个字符串控制加密解密，比定义两个函数更简洁。
  2. 偏移量校验 ：检查 shift 是否为整数，防止因传入浮点数或其他类型导致的意外错误。
  3. 加解密的统一 ：这是最巧妙的一点。解密操作被简化为“反向偏移”（ shift = -shift ）。这意味着加密和解密的逻辑核心是完全相同的，只是方向相反，极大地减少了代码重复，也符合数学本质。
  4. 字符处理逻辑 ：核心在于 (ord(char) - base + shift) % 26 + base 这个公式。
    • ord(char) 获取字符的ASCII码。
    • - base （65或97）将字母映射到0-25的范围（A/a->0, B/b->1, …）。
    • + shift 进行偏移。
    • % 26 取模运算确保了偏移是循环的，即Z之后回到A。这是实现“循环移位”的关键，没有它，偏移超出Z的字符就会变成非字母符号。
    • + base 将数字重新映射回ASCII码的字母区间。
  5. 非字母保留 ：对于空格、标点、数字，代码选择原样保留。这在古典密码模拟中是合理的，因为凯撒当年也只处理字母。但在现代加密中，这通常是一个安全隐患，因为它保留了明文的结构信息。

注意 ：这里的 % （取模）运算符在Python中对负数也能正确工作，例如 -3 % 26 的结果是 23 。这保证了当 shift 为负数（解密模式）时，计算依然能正确循环。

2.2 安全缺陷分析与实战演练

凯撒密码的安全性几乎为零，但它是一个完美的教学工具，用于理解密码分析的基本概念。

1. 唯密文攻击与暴力破解： 由于密钥空间极小（只有25种可能的非零偏移量），攻击者可以轻松地尝试所有可能的偏移量，这个过程称为“暴力破解”或“穷举攻击”。一个简单的破解程序可以在毫秒级内完成。

def brute_force_caesar(ciphertext: str):
    “””尝试所有可能的偏移量来破解凯撒密码。“””
    original_text = ciphertext  # 保留一份原始密文用于显示
    # 移除非字母字符，只分析字母部分，更清晰
    letters_only = ‘’.join(filter(str.isalpha, ciphertext)).lower()
    
    print(f“密文: {original_text}”)
    print(“尝试所有偏移量:”)
    for shift in range(1, 26):
        # 复用加密函数，偏移量为负shift即为解密尝试
        attempted_plaintext = caesar_cipher(ciphertext, shift, mode=‘decrypt’)
        # 简单评估：如果解密结果包含常见单词，则高亮显示
        common_words = [‘the’, ‘and’, ‘is’, ‘in’, ‘to’, ‘of’]
        score = sum(1 for word in common_words if word in attempted_plaintext.lower())
        indicator = ‘ <-- 可能正确！‘ if score > 2 else ‘’ # 简单启发式判断
        print(f“Shift {shift:2d}: {attempted_plaintext}{indicator}”)

2. 频率分析攻击： 这是更高级、更有效的攻击方法。在足够长的英文文本中，字母的出现频率有稳定的统计规律（例如，e通常是最常见的字母）。攻击者分析密文中各字母的频率，将其与标准频率分布对比，就能推测出偏移量。实现一个简单的频率分析器能让你直观感受这种攻击的威力。

from collections import Counter

def frequency_analysis(ciphertext: str):
    “””对密文进行简单的字母频率分析。“””
    # 只统计字母，忽略大小写
    letters = [ch.lower() for ch in ciphertext if ch.isalpha()]
    if not letters:
        print(“密文中无字母可分析。”)
        return
    
    total = len(letters)
    freq = Counter(letters)
    
    print(“字母频率统计（百分比）:”)
    # 按频率降序排列
    for letter, count in freq.most_common():
        percentage = (count / total) * 100
        print(f“  {letter}: {percentage:5.2f}% ({count}次)”)
    
    # 英文中最常见的字母通常是‘e’
    most_common_letter = freq.most_common(1)[0][0]
    # 假设密文中最常见的字母对应明文‘e’ (ASCII 101)
    assumed_shift = (ord(most_common_letter) - ord(‘e’)) % 26
    print(f“\n基于‘e’是英文最常见字母的假设:”)
    print(f“  密文最常见字母‘{most_common_letter}’可能对应明文‘e’。”)
    print(f“  推测偏移量 shift = {assumed_shift} 或 {assumed_shift-26}”)
    print(f“  尝试解密: {caesar_cipher(ciphertext, assumed_shift, ‘decrypt’)}”)

实操心得：

  • 教学价值大于实用价值 ：实现凯撒密码的重点不在于其安全性，而在于理解“密钥”、“加密算法”、“解密算法”、“密码分析”这些基本概念。
  • 编码陷阱 ：在实现取模循环时，务必注意编程语言中取模运算对负数的处理方式。Python的 % 是“地板除模”，能直接得到我们想要的结果，但某些语言（如C/C++）的 % 对负数处理不同，需要额外调整。
  • 扩展练习 ：可以尝试实现“维吉尼亚密码”，它是凯撒密码的升级版，使用一个关键词作为密钥，进行多表替换，安全性显著提高，是通向现代密码学的重要一步。

3. 现代密码学核心：深入拆解RSA算法原理与实现

从凯撒密码到RSA，我们跨越了从“艺术”到“科学”的鸿沟。RSA的安全性不再依赖于算法的保密，而是基于一个公认的数学难题——大整数分解的困难性。它的非对称特性（公钥加密，私钥解密）彻底改变了密钥分发的模式。

3.1 RSA算法原理分步详解

RSA的整个过程可以分解为以下几个关键步骤，理解每一步的“为什么”至关重要。

步骤一：密钥生成——构建数学锁具 这是最核心的一步，生成的公私钥对具有独特的数学关系。

  1. 选择两个大质数p和q ：这是安全的基础。p和q必须足够大（如今至少1024位，推荐2048位或以上），并且随机、独立。它们的乘积n的长度决定了密钥的强度。
    • 为什么是质数？ 为了确保φ(n)的计算简单，且增加分解n的难度。
  2. 计算模数n ： n = p * q 。n是公钥的一部分，也是加密解密运算的模数。它的长度（比特数）就是常说的“RSA-2048”中的2048。
  3. 计算欧拉函数φ(n) ： φ(n) = (p-1) * (q-1) 。这个值必须保密，它描述了在小于n的正整数中，与n互质的数的个数。它是选择公钥指数e的约束条件。
  4. 选择公钥指数e ：选择一个整数e，满足 1 < e < φ(n) ，且 e 与 φ(n) 互质 （最大公约数为1）。通常选择65537 (0x10001)。这是一个广泛采用的固定值，因为它二进制表示中只有两个1，计算效率高，且安全性经过充分验证。
    • 为什么常用65537？ 它是一个费马数（2^16+1），素数，且二进制形式为10000000000000001，在模幂运算中可以通过快速算法优化，平衡了安全与效率。
  5. 计算私钥指数d ：d是e关于模φ(n)的 模逆元 。即满足 (d * e) % φ(n) == 1 。d是私钥的核心部分，必须严格保密。
    • 如何计算？ 通常使用扩展欧几里得算法。这个算法不仅能求出最大公约数，还能找到满足 d*e + k*φ(n) = 1 的系数d和k，其中的d模φ(n)后就是我们要的模逆元。

步骤二：加密过程——用公钥上锁 加密方持有公钥 (n, e) 和明文 m （明文需要先转换为一个小于n的整数）。 加密运算： c ≡ m^e (mod n) 。计算结果c就是密文。

  • 直观理解 ：将明文数字m，自乘e次，然后取除以n的余数。由于n极大，直接计算 m^e 是不可能的，必须使用 快速模幂算法 。

步骤三：解密过程——用私钥开锁 解密方持有私钥 (n, d) 和密文 c 。 解密运算： m ≡ c^d (mod n) 。计算结果m还原为明文。

  • 为什么这样能解密？ 这是RSA的魔法所在，其正确性依赖于欧拉定理。因为 c^d ≡ (m^e)^d ≡ m^(e*d) (mod n) ，而根据密钥生成过程 e*d ≡ 1 (mod φ(n)) ，即 e*d = 1 + k*φ(n) 。根据欧拉定理，如果m与n互质，则 m^(φ(n)) ≡ 1 (mod n) ，所以 m^(e*d) ≡ m^(1 + k*φ(n)) ≡ m * (m^(φ(n)))^k ≡ m * 1^k ≡ m (mod n) 。即使m与n不互质，运用中国剩余定理也能证明解密依然成立。

3.2 Python实现RSA：从理论到代码

在TheAlgorithms-Python中，RSA的实现会涉及大数运算、质数生成和模逆计算。我们来看一个简化但完整的教育性实现，并讨论其中的关键点。

import random
from math import gcd

def is_prime_miller_rabin(n: int, k: int = 5) -> bool:
    “””使用Miller-Rabin素性测试判断一个大整数是否为质数。
    这是一个概率性测试，但k足够大时（如40），错误概率极低。
    “””
    if n < 2:
        return False
    # 处理小质数
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    if n in small_primes:
        return True
    for p in small_primes:
        if n % p == 0:
            return False
    
    # 将 n-1 写成 d * 2^r 的形式
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    # 进行k轮测试
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)  # 快速模幂计算 a^d % n
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # 一定是合数
    return True  # 很可能是质数

def generate_large_prime(bit_length: int = 512) -> int:
    “””生成一个指定位数的大质数。“””
    while True:
        # 生成一个奇数。确保最高位是1以保证位数，最低位是1以保证是奇数。
        candidate = random.getrandbits(bit_length) | (1 << (bit_length - 1)) | 1
        if is_prime_miller_rabin(candidate):
            return candidate

def extended_gcd(a: int, b: int):
    “””扩展欧几里得算法，返回 (gcd, x, y) 使得 a*x + b*y = gcd(a, b)“””
    if a == 0:
        return b, 0, 1
    gcd_val, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd_val, x, y

def mod_inverse(e: int, phi: int) -> int:
    “””计算e模phi的模逆元d，即 (d * e) % phi == 1“””
    g, x, _ = extended_gcd(e, phi)
    if g != 1:
        raise ValueError(‘e 和 φ(n) 必须互质，无法计算模逆元’)
    return x % phi

def rsa_key_generation(bit_length: int = 1024):
    “””生成RSA公私钥对。“””
    # 1. 生成两个大质数
    p = generate_large_prime(bit_length // 2)
    q = generate_large_prime(bit_length // 2)
    # 确保p和q不同
    while p == q:
        q = generate_large_prime(bit_length // 2)
    
    # 2. 计算n和φ(n)
    n = p * q
    phi_n = (p - 1) * (q - 1)
    
    # 3. 选择公钥指数e
    e = 65537  # 行业标准
    # 确保e与φ(n)互质（对于标准e和大的φ(n)，几乎总是成立）
    if gcd(e, phi_n) != 1:
        # 极罕见情况，需要重新生成密钥或选择其他e
        raise RuntimeError(‘e 与 φ(n) 不互质，请重试’)
    
    # 4. 计算私钥指数d
    d = mod_inverse(e, phi_n)
    
    # 公钥: (n, e), 私钥: (n, d)
    public_key = (n, e)
    private_key = (n, d)
    # 在实际应用中，私钥通常还包含p, q, dmp1, dmq1, iqmp等用于CRT加速的参数
    return public_key, private_key, p, q

def rsa_encrypt(plaintext_int: int, public_key):
    “””使用公钥加密整数。“””
    n, e = public_key
    if plaintext_int >= n:
        raise ValueError(“明文整数必须小于模数n”)
    # 使用内置pow函数进行快速模幂运算，它比 (plaintext_int ** e) % n 高效无数倍
    ciphertext_int = pow(plaintext_int, e, n)
    return ciphertext_int

def rsa_decrypt(ciphertext_int: int, private_key):
    “””使用私钥解密密文整数。“””
    n, d = private_key
    plaintext_int = pow(ciphertext_int, d, n)
    return plaintext_int

# 示例：加密一个短消息
if __name__ == “__main__”:
    print(“生成RSA密钥对 (教育用途，位数较低)...“)
    public_key, private_key, p, q = rsa_key_generation(bit_length=256) # 教育演示用256位，实际请用2048+
    n, e = public_key
    _, d = private_key
    print(f“公钥 (n, e): n={hex(n)[:30]}..., e={e}”)
    print(f“私钥指数 d: {hex(d)[:30]}...”)
    print(f“(内部) p: {hex(p)}, q: {hex(q)}”)
    
    # 明文（需要转换为整数）
    message = “Hello RSA!”
    message_bytes = message.encode(‘utf-8’)
    message_int = int.from_bytes(message_bytes, byteorder=‘big’)
    print(f“\n明文: ‘{message}’”)
    print(f“明文(整数): {message_int}”)
    
    # 检查明文是否小于n
    if message_int >= n:
        print(“错误：明文过长，需要分块或使用混合加密。”)
    else:
        # 加密
        cipher_int = rsa_encrypt(message_int, public_key)
        print(f“密文(整数): {cipher_int}”)
        
        # 解密
        decrypted_int = rsa_decrypt(cipher_int, private_key)
        decrypted_bytes = decrypted_int.to_bytes((decrypted_int.bit_length() + 7) // 8, byteorder=‘big’)
        decrypted_message = decrypted_bytes.decode(‘utf-8’)
        print(f“解密后明文: ‘{decrypted_message}’”)

代码解析与关键点：

  1. 质数生成 ： generate_large_prime 函数是安全的关键。它使用 random.getrandbits 生成随机大数，并通过Miller-Rabin测试进行素性检测。这是一个概率测试，但通过足够多的迭代（参数 k ），可以将错误概率降到极低。
  2. 扩展欧几里得算法 ： mod_inverse 函数的核心。它高效地计算了私钥指数 d 。理解这个算法对于明白“模逆元”如何求解至关重要。
  3. 快速模幂运算 ：加密解密函数 rsa_encrypt 和 rsa_decrypt 中，我们使用了Python内置的 pow(x, y, z) 函数，它直接计算 x^y mod z ，并且使用了平方乘法等优化算法，效率极高。 绝对不要 用 (x ** y) % z ，因为 x**y 会先计算一个天文数字般大的中间结果，导致内存溢出和极慢的速度。
  4. 明文处理 ：示例中将字符串直接转换为整数进行加密。这仅适用于非常短的明文，因为RSA能加密的明文大小受限于模数 n 。对于长文本，标准做法是：
    • 分块加密 ：将明文分成小于 n 的块，分别加密（效率低，不推荐）。
    • 混合加密 （实际标准）：使用RSA加密一个随机的对称密钥（如AES密钥），然后用这个对称密钥加密实际的大段数据。这就是TLS/SSL等协议的工作方式。

4. 从理论到实践：RSA应用场景、填充方案与安全要点

理解了基础RSA，我们还需要知道它在现实中如何被安全地使用。直接使用教科书式的RSA（即上述实现，又称“裸RSA”或“教科书RSA”）存在严重的安全漏洞。

4.1 为什么需要填充？——对抗攻击

裸RSA是确定性的：同样的明文，同样的公钥，永远产生同样的密文。这会导致多种攻击：

  • 语义安全性缺失 ：攻击者能判断两次加密的是否是同一消息。
  • 小明文攻击 ：如果明文是一个很小的数字（比如密钥 m=1 ），那么密文 c = 1^e mod n = 1 ，直接暴露。
  • 共模攻击 ：如果同一明文用不同的公钥但相同的 n 加密，可能被破解。
  • 选择密文攻击 ：攻击者可以利用解密Oracle（一个能对任意密文解密的设备，但不直接给出私钥）来解密其他密文。

为了解决这些问题， 填充方案 被引入。它在加密前，将明文用特定格式的随机数据填充到与模数 n 比特长度相近，然后再进行RSA运算。

主流填充方案：

  • PKCS#1 v1.5 Padding ：曾经最广泛使用的方案。它在明文前添加特定格式的字节串。虽然历史上发现了一些边信道攻击，但在正确实现下仍被认为安全，且兼容性极好。
  • OAEP (Optimal Asymmetric Encryption Padding) ：目前 推荐 的方案。它使用随机数和哈希函数，提供了“概率加密”的特性，即使同一明文每次加密也会得到不同的密文，并且可证明安全（在随机预言机模型下）。现代标准（如RSAES-OAEP）都要求使用它。

在Python中，我们不应自己实现填充，而应使用成熟的密码学库，如 cryptography 。

# 使用 cryptography 库进行安全的RSA操作（示例）
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.serialization import Encoding, PublicFormat, PrivateFormat, NoEncryption

# 生成密钥对（库函数更安全高效）
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()

# 加密（使用OAEP填充）
message = b“Secret Message”
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

# 解密
decrypted_message = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)
print(decrypted_message == message)  # 输出: True

4.2 RSA的典型应用场景

  1. 密钥交换 ：在TLS/SSL协议中，客户端生成一个随机的对称密钥（如AES密钥），用服务器的RSA公钥加密后发送给对方。服务器用私钥解密获得对称密钥，后续通信使用对称加密。这是RSA最常见的用途。
  2. 数字签名 ：过程与加密相反。发送者用 私钥 对消息的哈希值进行“签名”（即加密哈希值），接收者用 公钥 “验证”（即解密签名，与重新计算的哈希值对比）。这证明了消息的来源和完整性。例如，软件发布者用私钥签名安装包，用户用公钥验证其未被篡改。
  3. 小数据加密 ：直接加密密码、PIN码等非常短的数据。

4.3 安全实践与注意事项

1. 密钥长度：

  • 绝对不要 在真实环境中使用低于2048位的RSA密钥。1024位密钥已被认为不安全，能够被专业机构破解。
  • 当前推荐使用 2048位 作为安全基线，对长期保密要求高的数据应考虑 3072位或4096位 。
  • TheAlgorithms-Python中的示例为了快速运行，可能使用小密钥， 切记这只是为了教学演示 。

2. 质数生成：

  • 必须使用密码学安全的随机数生成器（CSPRNG），如Python的 secrets 模块或 random.SystemRandom 。示例中的 random.getrandbits 在大多数情况下是安全的，但 secrets 模块是更明确的选择。
  • 质数检测必须使用Miller-Rabin等可靠的测试，并进行足够多次迭代。

3. 侧信道攻击防御：

  • 计时攻击：通过测量解密操作所花费的时间来推断私钥信息。安全的实现（如 cryptography 库）会使用常数时间算法来防御。
  • 故障攻击：诱导设备在计算中出错来分析结果。这通常需要硬件级防护。
  • 对于绝大多数开发者，防御侧信道攻击的最佳实践就是：不要自己实现核心加密运算，使用经过严格审计的权威库。

4. 密钥管理：

  • 私钥必须绝对保密 ，并存储在安全的地方（如硬件安全模块HSM、加密的密钥库）。
  • 公钥可以公开分发。
  • 定期更换密钥对是良好的安全习惯。

5. 常见问题、调试技巧与算法扩展

在学习和实现这些密码学算法时，你一定会遇到各种问题。这里记录一些典型的坑和解决思路。

5.1 问题排查速查表

问题现象 可能原因 解决方案与排查步骤
凯撒密码解密结果乱码 1. 偏移量 shift 非整数或为0。
2. 文本包含非字母字符，处理逻辑有误。
3. 加解密模式 mode 参数传错。		 1. 打印并检查 shift 值，确保是1-25的整数。
2. 检查代码中 isupper() 和 islower() 的判断分支，确保非字母字符被正确旁路（ else 分支）。
3. 确认调用函数时 mode 参数是 ’encrypt’ 或 ’decrypt’ 。
RSA加密时提示“明文过长” 明文整数 m >= n 。RSA算法要求待加密的整数必须小于模数 n 。 1. 分块 ：将明文分成小于 n 的块（需处理填充，复杂）。
2. 改用混合加密 ：用RSA加密一个随机生成的AES密钥，再用AES加密实际数据。这是标准做法。
RSA解密结果错误或无法解码 1. 公私钥不匹配。
2. 明文到整数的编码（如UTF-8）与解密后整数到字节的解码方式不一致。
3. 使用了“裸RSA”且明文过小，遭受了某种攻击（虽然演示中概率低）。
4. 快速模幂运算 pow(c, d, n) 计算错误（极罕见）。		 1. 核对密钥 ：确保解密使用的私钥 (n,d) 与加密使用的公钥 (n,e) 来自同一对。
2. 检查编解码 ：在加密端，记录 message_int 的值；在解密端，解密后得到 decrypted_int ，对比两者是否一致。确保 to_bytes 和 from_bytes 使用的 byteorder 参数相同（通常为 ’big’ ）。
3. 使用填充 ：在生产环境中务必使用OAEP等填充方案。
Miller-Rabin测试将合数误判为质数 迭代次数 k 太小。Miller-Rabin是概率测试，存在错误概率。 增加参数 k 。对于密码学用途，通常 k=40 到 k=64 就足以将错误概率降到远低于硬件故障率的水平。也可以结合其他测试（如Baillie-PSW）。
计算模逆元时抛出异常“e和φ(n)必须互质” 选择的公钥指数 e 与 φ(n) 不互质。当 e 为固定值65537且 p,q 为大质数时，这 极其罕见 ，但理论上可能。 1. 捕获异常，然后重新生成密钥对。
2. 或者，在生成 e 后检查 gcd(e, phi_n)==1 ，如果不成立，则选择另一个 e （如另一个素数）。
算法运行极其缓慢 1. 密钥长度过大（如演示中用了4096位）。
2. 使用了 (m ** e) % n 而不是 pow(m, e, n) 。
3. 质数生成算法效率低。		 1. 演示时使用1024或2048位即可。
2. 务必使用 pow(m, e, n) ，这是内置的优化函数。
3. 使用高效的素性测试算法，如Miller-Rabin。

5.2 算法扩展与深入学习方向

TheAlgorithms-Python仓库通常不止包含凯撒和RSA。沿着这个路径，你可以继续探索：

  1. 对称加密算法 ：

    • AES (Advanced Encryption Standard) ：当前对称加密的全球标准。理解其SPN结构、轮密钥加、字节代换、行移位、列混淆等步骤。尝试实现一个简化版本（如AES-128）。
    • DES / 3DES ：了解其Feistel网络结构，虽然已过时，但对理解分组密码设计很有帮助。

  2. 哈希函数 ：

    • SHA-256 ：属于SHA-2家族，广泛用于区块链、数字签名。理解其压缩函数、消息填充、循环移位等操作。
    • MD5, SHA-1 ：了解它们的历史作用以及为何因碰撞攻击而被淘汰。

  3. 其他非对称算法 ：

    • Diffie-Hellman 密钥交换 ：理解基于离散对数问题的密钥协商原理。
    • 椭圆曲线密码学 (ECC) ：了解如何在椭圆曲线群上构建更高效（更短的密钥实现相同强度）的密码体系，如ECDSA签名、ECDH密钥交换。

  4. 密码分析实践 ：

    • 尝试对简单的替换密码、维吉尼亚密码编写自动破解程序。
    • 在CTF题目中练习针对弱RSA实现的各种攻击（如因式分解n、共模攻击、低指数攻击、维纳攻击等）。

实现这些算法最大的收获，不是让你去写一个用于生产环境的加密库，而是 建立对密码学核心概念的直觉理解 。当你再看到“证书”、“签名”、“非对称加密”这些词时，脑子里浮现的不再是黑盒，而是清晰的数学过程和代码逻辑。这种理解，是安全地使用密码学API、诊断安全问题、乃至进行更高级安全研究的坚实基础。

最后，记住密码学第一原则： 不要自己发明加密算法，也不要盲目自己实现加密算法用于生产环境 。学习实现是为了理解，实际应用请务必使用像 cryptography (Python)、 OpenSSL (C)、 Bouncy Castle (Java) 这样经过全球密码学家和开发者多年审计、测试的成熟库。

# 密码学
Logo
亚马逊云科技技术品牌专区