CTF密码学实战：用Python自动化破解30种加密算法

引言：当Python遇见密码学

第一次参加CTF比赛时，我看着那些加密的字符串完全不知所措。直到一位前辈告诉我："密码学不是数学考试，而是编程挑战。"这句话彻底改变了我学习密码学的方式——从死记硬背算法原理转向用代码实现自动化破解。本文将分享如何用Python这把"瑞士军刀"破解CTF中常见的30类密码学题目，每个技巧都经过实战检验。

1. 古典密码：从凯撒到维吉尼亚

1.1 凯撒密码的暴力破解

凯撒密码作为最古老的加密方式，其核心是字母表的固定位移。在CTF中，题目往往不会告诉你位移量，这时就需要暴力破解：

def caesar_bruteforce(ciphertext):
    for shift in range(26):
        plaintext = ""
        for char in ciphertext:
            if char.isalpha():
                ascii_offset = 65 if char.isupper() else 97
                decrypted_char = chr((ord(char) - ascii_offset - shift) % 26 + ascii_offset)
                plaintext += decrypted_char
            else:
                plaintext += char
        print(f"Shift {shift}: {plaintext}")

# 示例用法
caesar_bruteforce("khoor zruog")

实用技巧 ：

• 英文文本中空格通常保留，可以作为定位标志
• 单字母单词只有"A"和"I"两种可能
• 高频字母分析（E、T、A出现频率最高）

1.2 维吉尼亚密码的密钥推测

维吉尼亚密码作为多表替换密码，破解关键在于确定密钥长度。Kasiski测试法可以通过重复片段间距推测密钥长度：

from collections import defaultdict
import math

def find_repeats(ciphertext, min_len=3):
    repeats = defaultdict(list)
    for i in range(len(ciphertext) - min_len + 1):
        segment = ciphertext[i:i+min_len]
        repeats[segment].append(i)
    return {k:v for k,v in repeats.items() if len(v) > 1}

def guess_key_length(ciphertext):
    repeats = find_repeats(ciphertext)
    distances = []
    for seg, positions in repeats.items():
        for i in range(1, len(positions)):
            distances.append(positions[i] - positions[0])
    
    # 计算所有间距的最大公约数
    if distances:
        gcd = distances[0]
        for d in distances[1:]:
            gcd = math.gcd(gcd, d)
        return gcd
    return None

2. 现代对称加密：AES实战

2.1 AES-ECB模式的弱点利用

电子密码本(ECB)模式会将相同明文块加密为相同密文块，这个特性可以通过"字节翻转攻击"利用：

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

def ecb_byte_flipping(original, desired, block_size=16):
    # 计算需要修改的字节位置
    diff = [o ^ d for o, d in zip(original.encode(), desired.encode())]
    
    # 生成恶意密文
    fake_cipher = bytearray()
    for i in range(len(diff)):
        if diff[i] != 0:
            fake_cipher.append(diff[i] ^ original_cipher[i])
        else:
            fake_cipher.append(original_cipher[i])
    
    return bytes(fake_cipher)

2.2 CBC模式的填充预言攻击

密码分组链接(CBC)模式容易受到填充预言(Padding Oracle)攻击，以下是用Python模拟的攻击过程：

def padding_oracle_attack(ciphertext, oracle, block_size=16):
    plaintext = b''
    iv = ciphertext[:block_size]
    blocks = [ciphertext[i:i+block_size] 
              for i in range(block_size, len(ciphertext), block_size)]
    
    for block in blocks:
        decrypted = b''
        intermediate = bytearray(block_size)
        
        for byte_pos in range(block_size-1, -1, -1):
            padding_value = block_size - byte_pos
            
            # 构造恶意IV
            malicious_iv = bytearray([0] * block_size)
            for i in range(byte_pos + 1, block_size):
                malicious_iv[i] = intermediate[i] ^ padding_value
                
            # 暴力破解当前字节
            for guess in range(256):
                malicious_iv[byte_pos] = guess
                if oracle(bytes(malicious_iv) + block):
                    intermediate[byte_pos] = guess ^ padding_value
                    decrypted = bytes([intermediate[byte_pos] ^ iv[byte_pos]]) + decrypted
                    break
        
        plaintext += decrypted
        iv = block
    
    return unpad(plaintext, block_size)

3. 非对称加密：RSA的多种攻击方式

3.1 小指数攻击与广播攻击

当相同的明文用多个小公钥指数(e)加密时，可以使用中国剩余定理恢复明文：

from Crypto.Util.number import inverse
from functools import reduce

def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda x, y: x*y, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * inverse(p, n_i) * p
    return sum % prod

def broadcast_attack(ciphertexts, moduli, e=3):
    m_e = chinese_remainder(moduli, ciphertexts)
    m = round(m_e ** (1/e))
    return m

3.2 Wiener攻击破解小私钥

当私钥d较小时，可以通过连分数展开快速破解：

from fractions import Fraction

def wiener_attack(e, n):
    # 将e/n展开为连分数
    def continued_fractions(e, n):
        while n:
            q = e // n
            yield q
            e, n = n, e % n
    
    # 计算渐进分数
    def convergents(cf):
        p_prev, q_prev = 1, 0
        p_curr, q_curr = 0, 1
        
        for q in cf:
            p_next = q * p_curr + p_prev
            q_next = q * q_curr + q_prev
            yield p_next, q_next
            p_prev, q_prev = p_curr, q_curr
            p_curr, q_curr = p_next, q_next
    
    # 尝试可能的k/d
    for k, d in convergents(continued_fractions(e, n)):
        if k == 0:
            continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        # 解方程x^2 - (n - phi + 1)x + n = 0
        a = 1
        b = n - phi + 1
        c = n
        discriminant = b * b - 4 * a * c
        if discriminant < 0:
            continue
        sqrt_discriminant = int(discriminant ** 0.5)
        if sqrt_discriminant * sqrt_discriminant != discriminant:
            continue
        if (b + sqrt_discriminant) % 2 != 0:
            continue
        return d
    return None

4. 综合实战：CTF典型题目解析

4.1 混合加密系统分析

很多CTF题目会组合多种加密方式，比如先用RSA加密AES密钥，再用AES加密数据。下面是一个典型解决方案：

def solve_hybrid_encryption(rsa_encrypted_key, aes_encrypted_data, rsa_private_key):
    # 用RSA私钥解密AES密钥
    from Crypto.PublicKey import RSA
    from Crypto.Cipher import PKCS1_OAEP, AES
    
    rsa_key = RSA.import_key(rsa_private_key)
    cipher_rsa = PKCS1_OAEP.new(rsa_key)
    aes_key = cipher_rsa.decrypt(rsa_encrypted_key)
    
    # 用AES密钥解密数据
    iv = aes_encrypted_data[:16]
    ciphertext = aes_encrypted_data[16:]
    cipher_aes = AES.new(aes_key, AES.MODE_CBC, iv)
    plaintext = cipher_aes.decrypt(ciphertext)
    
    return plaintext

4.2 隐写术与密码学结合

CTF中经常需要从图片、音频等载体中提取隐藏信息。以下是PNG图片中LSB隐写的提取方法：

from PIL import Image
import numpy as np

def extract_lsb_png(image_path):
    img = Image.open(image_path)
    pixels = np.array(img)
    
    # 提取每个像素最低有效位
    binary_data = []
    for row in pixels:
        for pixel in row:
            for channel in range(3):  # RGB三个通道
                binary_data.append(str(pixel[channel] & 1))
    
    # 将二进制数据转换为字节
    message = []
    for i in range(0, len(binary_data), 8):
        byte = binary_data[i:i+8]
        if len(byte) < 8:
            break
        message.append(chr(int(''.join(byte), 2)))
    
    return ''.join(message)

在CTF赛场上，真正的挑战往往不是算法本身，而是如何将这些技术组合应用。记得在一次比赛中，我们遇到了一个用栅栏密码混淆后又经过Base64编码的字符串，最后还藏在图片的EXIF信息中。这种多层次挑战正是CTF密码学的魅力所在。