CTF101课程遗留问题探索

重温lab1,2剩余章节

crypto lab 1: 消息加密和数字签名 - CTF101-Labs-2025

这个lab之前我只完成了DSA部分（而且DSA_Revenge也做不出来)，学习一下剩余的知识点.

古典密码的拓展 (60%)

希尔密码是古典密码学与线性代数的结合，通过希尔密码的破解，也可以初步感受现代密码学的特点：以数学为基础的算法构建和破解。

本 Challenge 需要完成 ZJU School-Bus 上的 HSC 一题，在实验报告中简单描述这道题的做法。

这里首先先让同学们学习一下 sagemath 的使用方法，对完成本题或者之后专题的学习有较大的帮助。

• 对题目中的 MT 矩阵进行随机赋值，使其可逆，使用 sage 求出它的逆矩阵，分值 10 分
• 随机设置 flag 生成 FT，计算 RT，再通过 RT 和 MT 求出 FT 的值，与原 FT 进行比对，分值 10 分

如果后续没有选择密码学专题的打算，上述复现可以使用在线环境。

HSC 题目分值 40 分，加上 sage 复现部分本 Challenge 共 60 分，同样，如果没法完整做出，也可以叙述自己的思路和解题过程，会根据完成情况给分。

资料：Linear Algebra - Tutorial

参考Writeup: CTF/2023-2024暑短学期/Lab1-Crypto Report.md · BruceJqs

题干：

MT = matrix(Zmod(256), [[?, ?, ?], [?, ?, ?], [?, ?, ?]]) # ? means unknown number
assert MT.is_invertible()
flag = "AAA{?????????????????????????}" # ? means unknown printable char
FT = matrix(Zmod(256), 3, 10)
for i in range(3):
    for j in range(10):
        FT[i, j] = ord(flag[i + j * 3])
RT = MT * FT
result = b''
for i in range(10):
    for j in range(3):
        result += bytes([RT[j, i]])
print(result)
# b'\xfc\xf2\x1dE\xf7\xd8\xf7\x1e\xed\xccQ\x8b9:z\xb5\xc7\xca\xea\xcd\xb4b\xdd\xcb\xf2\x939\x0b\xec\xf2'

暴力破解跑不动睡不着觉啊睡不着觉，深夜起来问队友有没有当时基础周做这个的，结果得到了上面那个writeup.

于是看了一下代码，还真是只能暴力破，估计自己搓的代码问题很大于是学习一下：

def check(matrix):
    for i in range(3):
        for j in range(10):
            if matrix[i,j] < 32 or matrix[i,j] 126:
                return False
    return True
# 检查3×10矩阵中的所有元素是否都在ASCII可打印字符范围内(32-126)，这样解密后的结果可读

encoded = b'\xfc\xf2\x1dE\xf7\xd8\xf7\x1e\xed\xccQ\x8b9:z\xb5\xc7\xca\xea\xcd\xb4b\xdd\xcb\xf2\x939\x0b\xec\xf2'
encoded_iter = iter(encoded)

RT = matrix(Zmod(256), [[0 for i in range(10)] for j in range(3)])
i = 0

for element in encoded_iter:
    RT[i % 3, i // 3] = element
    i += 1
# 填充RT矩阵 ###############################################################

line1 = []
line2 = []
line3 = []

a1 = RT[0,0]
a2 = RT[1,0]
a3 = RT[2,0]
b1 = RT[0,1]
b2 = RT[1,1]
b3 = RT[2,1]
c1 = RT[0,9]
c2 = RT[1,9]
c3 = RT[2,9]

for i in range(256):
    for j in range(256):
        for k in range(256):
            if (a1 * i + a2 * j + a3 * k) % 256 == 65:
                if (32 <= (247 * i + 30 * j + 237 * k) % 256 <= 126 and 32 <= (204 * i+81 * j+139 * k) % 256 <= 126 and 32 <= (57 * i + 58 * j + 122 * k) % 256 <= 126):
                    if (b1 * i + b2 * j + b3 * k) % 256 == 123:
                        line1.append([i, j, k])
                    elif (c1 * i + c2 * j + c3 * k) % 256 == 125:
                        line3.append([i, j, k])
                    else:
                        line2.append([i, j, k])
print(line1)

########################## 极为暴力的纯破解方法 #########################

total = 0
MTN = matrix(Zmod(256), [[0,0,0],[0,0,0],[0,0,0]])
for i in line1:
    for j in line2:
        for k in line3:
            for l in range(3):
                MTN[0,l] = i[l]
                MTN[1,l] = j[l]
                MTN[2,l] = k[l]
            if MTN.is_invertible():
                FT_cal = MTN * RT
                if check(FT_cal):
                    total += 1
                    print("Case "+str(total)+":")
                    print(FT_cal)
                    print("\n")

RSA 的密钥格式解析

RSA 密钥的格式有很多种，常见的有 PEM、DER 等格式。PEM 格式的密钥是 Base64 编码的 DER 格式密钥，DER 格式的密钥是 ASN.1 编码的二进制格式。

你可能需要参考包括但不限于 此博客 来了解 RSA 密钥的具体格式和结构。

本 Challenge 需要完成比赛平台上的 Leaked RSA Key 一题，在实验报告中描述这道题的做法。

• 解析 DER 格式的 RSA 密钥，解释各个字段的含义，分值 30 分
• 使用 factordb 或者 yafu 等其他工具分解 RSA 模数解出明文，分值 10 分
• ( 慎选 ) 解析不出意外的话，你会发现私钥只有前半部分。你可以尝试使用 RSA 已知私钥高位攻击来恢复后半部分，仅使用网络上的脚本只能获得 15 分，如果能够在报告中详细解释攻击过程和原理，可以获得 35 分。

如果没法完整做出，也可以叙述自己的思路和解题过程，会根据完成情况给分。

记录一下这个博客的知识点：

RSA的常用密钥格式

工具：

• 解析ASN.1格式下的密钥构成：ASN.1 Parser | phpseclib 以及 ASN.1结构解析器

知识点：

• DER (Distinguished Encoding Rules)格式

  是密钥在ASN.1 format下二进制表述格式.

• PEM (Privacy-Enhanced Mail)格式：是对DER的base64编码

  Each object is delimited by lines similar to "-----BEGIN ...-----" and "-----END ...-----". Data that is not between such lines is ignored, and is sometimes used for comments, or for a human-readable dump of the encoded data.

• PKCS #1

  长这个样子：

  -----BEGIN RSA PUBLIC KEY-----
  BASE64 ENCODED DATA
  -----END RSA PUBLIC KEY-----
  

再看一下Leaked RSA Key这道题：

雨夜，卢浮宫地下的羊皮纸霉味与血腥气在档案库里缠绵，首席修复师艾琳·德·维特倒在文艺复兴的尘埃中，她的指尖凝固在键盘"RSA-PKCS#1"的凹痕上，烧焦的屏幕幽幽浮出半截密钥——

-----BEGIN RSA PRIVATE KEY-----
MIGrAgEAAiEAwmNq5cPY5D/7l6sJAo8arGwL9s09cOvKKBv/6X++MN0CAwEAAQIgGAZ5m9RM5kkSK3i0MGDHhvi3f7FZPghC2gY...

如同被撕碎的魔法契约，那些省略号里沉睡着达芬奇《机械天使的密语》手稿的终极秘密。她染血的掌心紧攥的便签上，十六进制密文1c194cd4f48d77b2e14cace43869bea17615ab23da0ef63b7bf56116ad3ac93b像一串冰冷的诅咒，这是凶手盗取末日兵器蓝图时被监控拍下的罪证视频，却被封存在RSA的数学牢笼中。

我在现场拾起她未写完的笔记："他们以为密钥只是数字...却不知PKCS#1的ASN.1结构是唤醒机械天使的祷文..."，血渍晕染了后半句。此刻，残缺的PEM文件在证物台上泛着冷光，头部清晰的模数n与指数e是达芬奇留下的密码锁齿，而消逝在省略号中的素数p和q，正是凶手刻意抹去的钥匙齿痕。十六进制密文在投影仪上投出诡谲的波纹，仿佛五百年前的机械齿轮在黑暗中重新啮合——只有让破碎的DER编码重生，让PKCS#1的骨架从PEM残片中完整站起，才能听见素数的低语破译密文，让视频里的凶手在蓝光中显形，让吞噬光的机械在《启示录》坐标前停止心跳...

雨点敲打彩绘玻璃，像倒计时的秒针。卢浮宫穹顶的鸽群突然惊飞，散落的羽毛在密钥片段旁排成一行隐形的警告：当模数在标准格式中复活时，真相将刺穿所有阴影。

题干提到了PKCS#1的ASN.1结构，需要还原“破碎的DER编码”.

对于RSA私钥，其ASN.1结构如下：

RSAPrivateKey ::= SEQUENCE {
    version           Version,
    modulus           INTEGER,  -- n
    publicExponent    INTEGER,  -- e
    privateExponent   INTEGER,  -- d
    prime1            INTEGER,  -- p
    prime2            INTEGER,  -- q
    exponent1         INTEGER,  -- d mod (p-1)
    exponent2         INTEGER,  -- d mod (q-1)
    coefficient       INTEGER,  -- (inverse of q) mod p
}

（现在知道之前赶出来的报告里面对这部分的理解有多荒谬了）

使用ufreetools解出来\(e= 65537\)，\(n\)的值通过拼接ufreetools给出的hex然后转成10进制得出，为87924348264132406875276140514499937145050893665602592992418171647042491658461

使用yafu分解之后得到：

p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239

于是很自然地得到了flag：AAA{N3veR_Le4k_PR1va7eK3y_Ag41N}

随机数的预测 (50%+15%)

随机数在密码学中起着重要的作用，尤其是在密钥生成和加密算法中。

在课上我们主要介绍了随机数的生成和预测方法，以及相关的攻击方式，你可以尝试实现一些简单的随机数预测攻击。

本 Challenge 需要完成 ZJU School-Bus 上的 PRNG Study1 一题，在实验报告中简单描述这道题的做法。完成本题可以获得 50 分。

• 如果想要获得额外的 15 分奖励，你可以再选择任意一种语言的随机数生成器进行分析并阐述攻击的思路。

如果没法完整做出，也可以叙述自己的思路和解题过程，会根据完成情况给分。

（慎选）哈希函数的扩展攻击 (60%)

哈希函数是现代密码学中重要的组成部分，广泛应用于数字签名、消息认证等场景。在课上我们介绍了哈希函数的基本原理和常见的攻击方式。

本 Challenge 需要完成 ZJU School-Bus 上的 treasurebank 一题，在实验报告中简单描述这道题的做法。

• 你可能需要注意 mdx 并非 md5，以及本题目需要 python2 环境。

如果没法完整做出，也可以叙述自己的思路和解题过程，会根据完成情况给分。

EZDLP

DLP（离散对数问题）

给定 \(g^x \equiv y (\operatorname{mod} p)\) 中的 \(g,y,p\)，其中 \(p\)为大素数，求解 \(x\).

• 这是一个困难问题，目前无法多项式复杂度时间内解决（NP）.

Diffie-Hellman密钥交换协议：

• 首先由参与方A,B公开参数\(g,p\)，并分别随机生成\(x_A,x_B\)，

• 接着分别计算各自的公钥：\(y_A = g^{x_A} (\operatorname{mod} p), y_B = g^{x_B} (\operatorname{mod} q)\)

• 最后是确认：协商密钥为\(y_B^{x_A} \equiv y_A^{x_B} \equiv g^{x_Ax_B} (\operatorname{mod} p)\)

攻击方法：

• cado-nfs工具求解
• 大步小步算法（BSGS算法）
• Pohlig-Hellman算法

BSGS算法：

• 对于 \(g^x \equiv y (\operatorname{mod} p), 0<x\leq m\) 的DLP 问题，可在\(O(\sqrt{m})\)的时间复杂度和\(O(\sqrt{m})\)的空间复杂度内求解

• 流程：

  1. 设\(x = \sqrt{m}x_0+x_1(0\leq x_0,x_1\leq \sqrt{m}) \Longrightarrow g^{\sqrt{m}x_0+x_1} \equiv y (\operatorname{mod} p)\Longrightarrow g^{\sqrt{m}x_0} \equiv yg^{-x_1} (\operatorname{mod} p)\)

  2. 两边分别去计算并存储所有\(x_0,x_1\)代入后的值并进行比较，如果有一项对应相等就破解出了\(x_0,x_1\)，从而得出\(x\).

Pohlig-Hellman算法流程：（适用于\(p-1\)是光滑的情况，即\(p-1 = \Pi^{k}_{i=1} p_i^{\alpha_i}\)，其中的\(p_i\)都很小）

1. \(p-1 = \Pi^{k}_{i=1} p_i^{\alpha_i}\)，并且对每个\(p_i\)，求出\(x_i = x (\operatorname{mod} p_i^{\alpha_i})\)；

2. 逐位恢复\(x_i\)，即计算\(x_i = \sum\limits_{k = 0}^{\alpha_i-1}x_{ik}p_i^{k}\)式子中的每项\(x_{ik}\)：

3. \(g^{x_i} \equiv b (\operatorname{mod} p )\Longrightarrow g^{\frac{p-1}{p_i^t}\cdot x_i} \equiv b^{\frac{p-1}{p_i^t}}(\operatorname{mod} p )\)，其中\(0<t<\alpha_i\).

   记\(A = g^{\frac{p-1}{p_i^t}}, B = b^{\frac{p-1}{p_i^t}}\)，则\(A^{x_i}\equiv B(\operatorname{mod} p )\)；

4. 由于对每个\(t\)，都有\(A^{p_i^t}\equiv 1(\operatorname{mod} p ) \Longrightarrow A^{\sum\limits_{j=0}^{t-1}x_{ij}*p_i^j}\equiv B(\operatorname{mod} p )\)，所以考虑从\(t=1\)开始到\(\alpha_i\)，通过先前计算出的每一个\(x_{ij}\)，带入得出\(x_i (\operatorname{mod} p_i^{\alpha_i})\)的值，用这些值构造CRT求解即可得到\(x(\operatorname{mod} p-1)\)的值.

先看题目源码：

题干

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from secret import flag

def pad(x, length):
    return x + (length - len(x) % length) * b'\x00'

p = 960494008017250155494739990397196249930200062145145133132556398221074529657304218221253517153928380265486339083177542201148993799925721673833333778621388110957986908045712612233794551809
x = getPrime(500)
g = 3
c = pow(g, x, p)

aes = AES.new(key = md5(str(x).encode()).digest(), mode = AES.MODE_ECB)
ct = aes.encrypt(pad(flag, 16))
print(f"c = {c}")
print(f"ct = {ct}")

'''
c = 505527904713564983625416248872210831215228354175257237841602581321675204643681129570897695080321118656513647239718859773976453054734892142640867733520305568808093022238369199760987416665
ct = b'qBS\x84\xfc"\xee$\xb2d\xba\xeb\x00\xf7\xf4\xa4\x91\x90<N\x1a\xb0\xa5>\xdc^\xe3I\xc3\xecc\x1e'
'''

因为x = getPrime(500)，所以不方便使用BSGS，时间复杂度过于高了.

\(p-1 = 2^{518}*1119326809698249181662206673457\)

用了yafu发现是个大素数，有点难办. 所以试一下Pohlig-Hellman攻击.

接下来手搓一下这个代码：

p = # 略
n = p - 1
g = 3
h = #略
ct = b'qBS\x84\xfc"\xee$\xb2d\xba\xeb\x00\xf7\xf4\xa4\x91\x90<N\x1a\xb0\xa5>\xdc^\xe3I\xc3\xecc\x1e'

# 计算 x mod 2^518
x = 0  # 累计值
gamma = pow(g, n // 2, p)  # γ = g^(n/2) mod p，阶为2

for k in range(518):
    exponent = n // (2 ** (k + 1))  # 整数除法
    h_k = (h * pow(g, -x, p)) % p  # 调整 h
    temp = pow(h_k, exponent, p)
    if temp == 1:
        x_k = 0
    elif temp == gamma:
        x_k = 1
    else:
        print(f"Error at k={k}")
        x_k = 0
    x += x_k * (2 ** k)

print(f"x = {x}")
assert (pow(g,x,p) == h)

key = hashlib.md5(str(x).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
decrypted = cipher.decrypt(ct) # 解密
flag = decrypted.rstrip(b'\x00')  # 去除填充的空字节

print(f"Flag: {flag.decode()}")

Flag: AAA{W31c0m3_T0_CT4_lo1_c0urs3!}