NewStar CTF 2024 Crypto 部分题解（W3-W5）#

1. 故事新编 1（W3，维吉尼亚变体）#

密文是英文诗体，加密前把明文 .upper() 后做维吉尼亚加密。破解流程：

1. Kasiski/IC 求 key 长：IC 峰值在 11（及 22）→ key 长 11，平均 IC≈0.0732（远高于随机英文 0.0385）。
2. 频率/逐链恢复 key：SUBTITUTION。
3. 识别诗歌：《The Zen of Python》（Python 之禅），且出题人在 “SPARSE IS BETTER THAN DENSE.” 与 “READABILITY COUNTS.” 之间硬插了一行提示 FLAGA IS VEGENERE（即 hint：flag is Vigenere）。
4. 明文还原后用”重加密 == 给定密文”逐字母验证通过；flag = md5(zen1)。

注意：维吉尼亚加密前 .upper() 抹掉了原始大小写，而 md5(zen) 对大小写敏感。最终 flag 由出题人/社区截图确认： flag{bda2bcf1eaeff7754a6483e74e70a937}（另备全大写/全小写等候选，见 solve 脚本注释）。

2. 故事新编 2（W3，Autokey 维吉尼亚）#

Autokey：key 为”初始 key + 明文”拼接，随明文增长。破解同故事新编 1：

• 初始 key 长 16，初始 key：SUPERSUBTITUTION（还原得分 -403 vs 次优 -627）。
• 诗歌为《The Zen of Python》后半段（第 12-19 行：IN THE FACE OF AMBIGUITY … IT MAY BE A GOOD IDEA）。
• 重加密验证通过，flag = md5(zen2)。

同样受 .upper() 大小写歧义影响，最终 flag 由出题人/社区截图确认： flag{8bc383165248f2e45a6910960a61e6a8}。

3. 没 e 这能玩？（W3）#

题目给出关于 p,q,r 的线性组合 h1,h2,h3：

1
h1 = p + q + r
2
h2 = 2p + 3q + 3r
3
h3 = 9p + 9q + 6r

1. 解线性方程组（Gauss-Jordan 精确有理数消元）→ 三个 512 位素数 p,q,r。
2. 求离散对数 e：hint = big^e mod 2^512。(Z/2^512)* 是 2-群（元素阶为 2 的幂，最大 2^510），对 p=2 做 Pohlig-Hellman 的逐位提升：先算 ord(big)=2^d，再用 big^(2^(d-1)) 这个阶 2 的”符号”元素逐位确定 e 的每个比特 → e=18344052974846453963（64 位素数）。
3. 常规 RSA 解密：n=pqr, φ=(p-1)(q-1)(r-1), d=e^-1 mod φ, m=c^d mod n。

Flag: flag{th1s_2s_A_rea119_f34ggg}

4. 两个黄鹂鸣翠柳（W3，Franklin-Reiter + Half-GCD）#

1
m1 = m + t1·δ,  m2 = m + t2·δ,  e = 683,  t1,t2 ∈ [0,255]
2
c1 = m1^e mod N,  c2 = m2^e mod N

对正确的 k = t2-t1 ∈ [-255,255]，(x + kδ)^e - c2 与 x^e - c1 在 Z_N[x] 上共享根 m1（关联消息攻击）。

• 683 次多项式用普通欧几里得 gcd 太慢 → 用 Half-GCD（分治快速 gcd）。
• 爆破 k（8 个后台任务并行分段扫描），k=74 命中：gcd 为线性 (x - m1)，取根 m1，再爆破 t1 还原 m。

Flag: flag{V_me_the_flag}

5. 俱以我之名（W4，Wiener 攻击）#

本地附件 InName.zip 为 0 字节损坏文件，从官方归档（github.com/pj-newstar/newstar-ctf-2024 release）补回完整数据后独立解出。

题目泄漏结构（“俱以我之名” = 明日方舟角色”维娜”→ Wiener）：

1
y / x ≈ k / Golden_Oath,  Golden_Oath = (p−114)(p−514)(p+114)(p+514)(q−1919)(q−810)(q+1919)(q+810) ≈ n^4

• 设 X = p²，用 n=pq 消去 q，得到关于 X 的四次方程，其整数根 X=p²。
• 或用 y 与 n^4 的连分数展开（Wiener）恢复 x/d，再解 Golden_Oath。
• 开方得 p、q = n/p，d = e^-1 mod φ 后 RSA 解密。

Flag: flag{rE@L_d@m@9e_15_7h3_mo5t_au7hEn7ic_dam49E}

6. RSA? cmd5!（W5，MD5 签名）#

Bob 用 RSA 对 md5(m).hexdigest()（转成整数）做”签名”：s = md5_hex_int^d mod n，其中 m 是 7 字符密码。

由 e·d ≡ 1 mod φ：s^e mod n = md5(m).hexdigest() 的整数形式 → 直接还原出 md5 hexdigest，无需私钥。再用 cmd5.com 查表/爆破得到 m = adm0n12（md5 = 86133884de98baada58a8c4de66e15b8）。

flag 格式：flag{th1s_1s_my_k3y:<m>0x<sha256(m)>}

Flag: flag{th1s_1s_my_k3y:adm0n120xbfab06114aa460b85135659e359fe443f9d91950ca95cbb2cbd6f88453e2b08b}

7. 没 e 也能玩（W5，e=3 相关消息攻击）#

e=3，三个相关消息 m1,m2,m3 加密（含已知 gift），构造三个多项式，在 Z_N[x] 上求 gcd 得公共根（Franklin-Reiter 套路）。

Flag: flag{No_course_e_can_play}

8. 学以致用（W5，Franklin-Reiter）#

e=3，flag 分两半 m1,m2（各自 pad）加密得 c1,c2，另有 c3=(m1+m2+gift)^3。

• 已知 m2 与 m1 的线性关系（gift 公开）→ Franklin-Reiter 相关消息攻击，多项式 gcd 分别解出 m1,m2。
• 去掉 pad 后拼接两半明文得 flag。

Flag: flag{W1Sh_you_Bec0me_an_excelL3nt_crypt0G2@pher}

9. 格格你好棒（W5，二维格恢复 p,q）#

泄漏关系：(p+2r)·3a + q ≡ s (mod b)，其中 0 ≤ s < 70、r∈[256,511]、a 1024 位、b 1536 位，目标是恢复 512 位的 p,q。

• 令 A = 3a，写成 A·(p+2r) + q - s = k·b。
• 向量 (X,Y) = (p+2r, q-s) 落在二维格 L = {(u,v): A·u+v ≡ 0 (mod b)}（基底 (1,-A)、(0,b)）。
• 量级：A~2^1025、b~2^1535，Gauss 启发最短向量约 √b~2^767，而目标向量只有约 2^511.5——异常短，二维 Gauss/Lagrange 归约直接返回它。
• 枚举小未知元 r,s，保留使 p,q 为 512 位素数的候选，RSA 解密（e=0x10001）即可。

Flag: flag{u_are_@_master_of_latt1ce_Crypt0gr@phy}

（easy_ecc 与 圣石匕首 待补：easy_ecc 附件数据内部不一致——文件内 k 与密文不匹配，官方 WP 同数据也解不出有效 flag，官方归档 zip 与本地一致；圣石匕首为 Boneh-Durfee 格攻击，本地用 fpylll 移植中。）