ImaginaryCTF 12月练习赛Crypto题解教学文档

1. Analyze (50pts)

题目描述：
通过字母替换加密的密文（如所有'a'替换为'b'，'b'替换为'c'等）。已知明文为一段天气描述，需恢复密文。

解题步骤：

1. 频率分析：统计密文中字母频率，匹配英文常见字母频率（如'e'最高）。
2. 已知明文攻击：利用题目提供的明文片段（如"The weather..."）对齐密文，推导替换规则。
3. 手动调整：根据部分匹配结果修正替换表，最终解密flag。

关键点：

• 密文与明文长度一致，直接逐字符映射。
• Flag格式为ictf{...}，可验证替换正确性。

示例：

密文: "Fka gavfkas..." → 明文: "The weather..."
映射: F→T, k→h, a→e, g→w, v→a, ...
Flag密文: "nrfl{rkvfYEF...}" → "ictf{chatGPT...}"

2. Affine Padding (75pts)

题目描述：
RSA低指数攻击（e=3），消息填充为a*M + b，已知N, a, b, c = (a*M + b)^3 mod N。

解题步骤：

1. 构造多项式：

   • 设flag已知部分为m_high，剩余未知部分为x（27字节）。
   • 多项式：f = (a*(m_high + x) + b)^3 - c，在模N下求小根。

2. Coppersmith攻击：

   • 使用Sage的small_roots求解x，参数X=256^27（未知部分范围）。

关键代码：

R.<x> = PolynomialRing(Zmod(N))
f = (a * (mhigh + x*256) + b)^3 - C
x = f.monic().small_roots(X=256^27, beta=0.4)

关键点：

• 填充形式导致多项式可解。
• 小根条件：x < N^(1/e)（e=3时需x足够小）。

3. RS-Survey (125pts)

题目描述：
分阶段恢复RSA私钥：

1. 阶段1：已知p的高384位和低384位，中间256位未知，用Coppersmith恢复p。
2. 阶段2：已知p中间768位，使用二元Coppersmith（需自定义二元多项式求解）。
3. 阶段3：p被分为5段（3段64位未知），需三元Coppersmith。

解题步骤：

1. 阶段1：

   • 多项式：f = p_high + x*2^384 + p_low，求小根x。

2. 阶段2：

   • 二元多项式：f = x*2^(1024-128) + p_mid*2^128 + y，使用bivariate函数求解。

3. 阶段3：

   • 三元Coppersmith，需调整多项式生成和求解逻辑（参考demo10）。

关键代码：

# 阶段1
p_h = a >> (1024-384) << (1024-384)
p_l = a % 2^384
f = p_h + x*2^384 + p_l
p = p_h + int(x[0])*2^384 + p_l

# 阶段3
f = x*2^960 + y*2^480 + z + a  # 三元变量

关键点：

• 分阶段逐步缩小未知位范围。
• 多元Coppersmith需精确构造多项式。

4. Cold Case (75pts)

题目描述：
Diffie-Hellman密钥交换，Bob的私钥部分比特已知（含?位），需恢复完整私钥。

解题步骤：

1. 分治攻击：

   • 将私钥分为高半和低半，分别枚举?的可能值（0或1）。
   • 使用中间相遇攻击：建表存储高半结果，匹配低半计算结果。

2. 恢复共享密钥：

   • 通过匹配结果恢复完整私钥，计算共享密钥解密AES。

关键代码：

# 分半枚举
for i in product(['0','1'], repeat=unknown//2):
    aa = a + int(i[k])*2^idx[k]  # 高半
    table[g^aa mod p] = i

for j in product(['0','1'], repeat=unknown//2):
    bb = b + int(j[k])*2^idx[k]  # 低半
    if (g^bb mod p) in table:
        secret = 合并高低半结果

关键点：

• 分治降低计算复杂度（O(2^{n/2})）。
• 确保AES解密结果包含ictf验证正确性。

5. Soup or Salad (65pts)

题目描述：
密文为垂直读取的文本（非左到右），需按列读取后凯撒移位。

解题步骤：

1. 垂直读取：

   • 将密文按列重新排列（如第1列所有行字符，第2列所有行字符...）。

2. 凯撒解密：

   • 尝试移位15（因明文开头为ictfCaesar...）。

关键代码：

for i in range(col):
    for j in range(row):
        message += data[j][i]

关键点：

• 识别密文排列方式。
• 已知明文确定移位量。

6. RSARSA (100pts)

题目描述：
双重RSA，已知n=p*q、c=m^3 mod n，以及C=p^3*q mod N。

解题步骤：

1. 数学推导：

   • C ≡ p^3*q ≡ n*p^2 mod N → p^2 ≡ C*n^{-1} mod N。
   • 直接开平方得p（因p^2 < N）。

2. 解密RSA：

   • 从p计算q = n/p，解密c得到m。

关键代码：

D = C * inverse(n, N) % N
p = iroot(D, 2)[0]
q = n // p
m = pow(c, d, n)

关键点：

• 利用p的边界条件（1001位）绕过模运算。
• 小指数（e=3）直接开方。

总结

• 频率分析：适用于简单替换密码。
• Coppersmith：核心在多项式构造和小根条件。
• 分治/中间相遇：减少暴力枚举复杂度。
• 垂直读取：注意密文排列方式。
• 数学推导：利用模运算性质简化问题。