前言这两题都是Crypto类型的题目所以有些地方是要添加原理的可能会稍有遗漏请各位见谅文章一些内容来自其它博主的内容(已标注来处)。这是第一次写Crypto的WP可能有点不足No.1 Pollard题干内容:在数字王国的边境矗立着一座被称为平滑之塔的古老要塞。这座要塞由一代数学匠人建造他们用无数小素数砖块堆砌而成却忽视了一个致命的弱点——塔的根基并不牢固。要塞中守护着一份加密的宝藏其安全性建立在两个巨大的素数 p 和 q 之上。建造者自信地宣称即使是最强大的军队也无法在有限时间内分解这 1024 位的模数 n。然而一位名叫 John Pollard 的流浪数学家发现了要塞的秘密。他注意到建造者在选择素数时犯了一个错误——他们没有使用强素数。p-1 和 q-1 都是由小素数相乘构成的平滑数就像用沙子建成的城墙。Pollard 留下了一句神秘的咒语当 p-1 的所有素因子都小于某个界限 B 时费马小定理会化作破城的利剑。只需计算 a^(B!) mod n再取 gcd(a^(B!) - 1, n)便能找到那把通往宝藏的钥匙。现在要塞的守军截获了一段加密的密文。他们只知道- 公钥 (n, e)- 密文 c传说中宝藏的 flag 就藏在这段密文之中。你能否效仿 Pollard 的智慧找到平滑之塔的弱点破解这份密文文件内容:n1547123205152469900670291140464357983440657686397398020791378018592221189414958470887124869602680127663490071604573315531598471623481806416433878081253985917567191216004800496089483625842197538355476893539753920543663146702250872800341451384267180648302354892966467116510056517637279674865199044303447590682411e65537c1336776732886162082917083736943232676342276913207072829943901249686321234577101464922485823839454810426498084037324101030907812803468006107855790364948921331639294591836318211995015874371455282657768356332217894096800901067178070074815121709048488233025620240176083082010944844746904040860837630433703858702823类型:本题是一道经典的Pollard p-1 平滑数攻击。原理原理可以用一句话概括当 RSA 的素数 p 满足p-1 是 B-smooth所有素因子 ≤ B时费马小定理会把 p 这个因子暴露出来用一次 gcd 就能提取。对应到题目则是它的防御方式:生成 RSA 素数时使用强素数strong prime要求 p-1 有一个大素因子 r且 r-1 也有大素因子使得 p-1 不可能是 B-smooth 的。现代 RSA 库如 OpenSSL默认就会做这个检查。它的具体原理可以分为5步:① 费马小定理基石对任意素数 p 和不被 p 整除的 aap−1≡1(modp)ap−1≡1(modp)即a^(p-1) - 1是 p 的倍数。这是整个攻击的出发点。② B-平滑假设要塞的弱点如果 p-1 的所有素因子都不超过某个界限 Bp−1q1a1⋅q2a2⋯qkak,∀qi≤Bp−1q1a1​​⋅q2a2​​⋯qkak​​,∀qi​≤B那么B! 1×2×3×…×B一定包含 p-1 的所有素因子含足够的幂次所以(p−1)∣B!(p−1)∣B!即 B! 是 p-1 的整数倍。这就是平滑数的致命之处——阶乘天然吞掉了所有小素因子。③ 构造 M B!利用费马定理设 M B! k·(p-1)那么aMak(p−1)(ap−1)k≡1k1(modp)aMak(p−1)(ap−1)k≡1k1(modp)所以p 整除 a^M - 1。④ 取 gcd 提取因子n p × q。我们知道了p | (a^M - 1)那直接算ggcd⁡(aM−1, n)ggcd(aM−1,n)三种可能g 的值含义对策g p成功分解q n / pg 1B 太小p-1 和 q-1 都没被整除增大 B 重试g n过冲p-1 和 q-1 都被整除了回退或用 stage 2⑤ 为什么通常只提取 p 而不是整个 n关键在于非对称性题目说 p-1 是平滑的但 q-1 通常不是两个都平滑的概率极低。所以a^M ≡ 1 (mod p)但a^M ≢ 1 (mod q)gcd 恰好给出 p 而不是 n。在实际操作中的技巧(这里以python代码为准)a 2 for i in range(2, B1): a pow(a, i, n) # a 2^(2·3·4·...·B) mod n 2^(B!) mod n g gcd(a - 1, n)每一步aa^i mod n等价于在指数上再乘一个 i最终a2^(B!) mod n但中间结果始终n永不溢出。具体原理可以参考TLSN博主写的文章https://www.cnblogs.com/lordtianqiyi/articles/17069448.html解题步骤OK回到题目我们已经知道了这个原理之后(其实不怎么知道也行)开始解题。step-1从文件中我们可以知道一下信息:参数值n1028 bit 模数e65537c密文step-2运行 Pollard p-1 攻击运行我们上文给出的代码(核心循环)。a 2 for i in range(2, B1): a pow(a, i, n) # 等价于 a 2^(B!) mod n g gcd(a - 1, n)每次循环的数据:Bgcd(a-1, n)状态501无因子继续1001无因子继续2001无因子继续5001无因子继续7501无因子继续1000 pOKstep-3分解结果验证p*qnstep-4RSA 标准解密phi(n) (p-1)(q-1) d e⁻¹ mod phi(n) m c^d mod nstep-5明文还原m(hex)666c61677b736d303074685f7072316d335f70306c6c3472645f705f6d316e75735f315f6d346731637d m (utf-8) flag{sm00th_pr1m3_p0ll4rd_p_m1nus_1_m4g1c}注释:flag 含义拆解smooth prime Pollard p-1 minus 1 magic—— 正是因为 p-1 和 q-1 都由小素数构成平滑数Pollard 的 p-1 算法才能在 B1000 时轻松攻破 1028 位的模数。而恰好 B1000 处在一个甜点区间p-1 的阶乘覆盖刚好满足223⁴ 需要且仅需要 4 个 223但 q-1 的 277⁴ 还差一个形成了非对称暴露。结果flag:flag{sm00th_pr1m3_p0ll4rd_p_m1nus_1_m4g1c}No.2 来自幽灵的密信题干内容:深夜城市的灯火渐渐熄灭但网络安全中心的警报却突然响起。代号幽灵的黑客组织入侵了政府机构的加密通信系统窃取了一份机密文件。调查员你被紧急召回任务是破解这份加密通信日志。通过线人你获得了幽灵组织的加密通信记录。这份记录是用古老的 RC4 流密码加密的——一种由 Ron Rivest 在 1987 年设计的加密算法。幽灵组织自诩 cryptography 大师在通信中引用了一句密码学经典格言Cryptography is the practice and study of secure communication.幸运的是他们犯了一个致命的错误——为了节省密钥分发成本他们使用同一个 RC4 密钥加密了所有消息包括那句格言和藏有 flag 的机密文件。线人留下一句神秘的提示流密码的命门在于密钥流的复用。当同一个密钥流被使用两次整个加密体系就像纸糊的一般脆弱。文件内容:Phantom Hacker Encrypted Communications Log[Known Plaintext]Cryptography is the practice and study of secure communication.[Ciphertext of Known Plaintext (hex)]3c2ca4e08c1ea6426dacf6a9ba07f8464c82f4d00190f0fca713a179626c8b8801f7874bec6be9c3263a85159984e0bf061d35f99ac2034dcf85f6a79ac886[Ciphertext of Flag (hex)]1932bcf7832382045397f0e0ed00d43654dea09e05d1e9eb8c4bb143063ed1884dfdac0afb4dbdc47345a4449893a3ae5b------------------------------------------------------------Note: Both messages were encrypted with the SAME RC4 key.Recover the flag.类型:流密码密钥流复用(对称密码)流密码是RC4(文件中提示了)。原理:(原理就很复杂光一个流密码密钥流复用就有很多种因此就结合题目的RC4说了单纯写内容太多了介绍可以看Shi-p博主写的文章密码学系列四——对称密码2_rc4密钥-CSDN博客)加密过程本质上是密文明文XOR密钥流。密钥流由 RC4 算法根据密钥生成同一个密钥永远产生同一条密钥流 K。题目中幽灵组织用同一个 RC4 密钥加密了两条消息C1 P1 XOR K 已知明文的密文 C2 P2 XOR K flag的密文因为 P1已知明文和 C1 都已知可以直接反推出密钥流K C1 XOR P1然后用恢复出的 K 解密 flagP2 C2 XOR K C2 XOR C1 XOR P1全程不需要知道 RC4 密钥本身(密钥流一旦泄露密钥就没有意义了)。解题步骤:Step 1依旧看一下给出的数据梳理一下信息。数据长度已知明文 P1 Cryptography is the practice and study of secure communication.63 bytesC1P1 的密文 hex63 bytesC2flag 的密文 hex49 bytesC2 比 C1 短所以取 K 的前 49 字节即可。Step 2恢复一下密钥流(已知 P1 和 C1 → 反推 K P1 XOR C1)K bytes(C1[i] ^ P1[i] for i in range(len(P1)))得到 K63 字节7f5edd90f871c130...ce482cef5a6a8Step 3解出flag。(P2 C2 XOR K)flag bytes(C2[i] ^ K[i] for i in range(len(C2)))结果flag{RC4_Kn0wn_Pl41nt3xt_1s_D34dly_4s_th3_R4bb1t}结语由于作者忙于学业所以只能在暑假或者寒假才能写几篇文章而且也不能太长(/(ㄒoㄒ)/~~)。所以像之前写的题目WP合集只能给大家告一段落了当然像这种单题或双题的WP还是可以更新的。而且质量也不会有所下降。私信里也有一些人问“会不会在未来将文章设定为VIP可见”我认为是不会的毕竟我的文章还达不到那种水平...希望大家多多支持点赞、收藏让我们下一个WP见!!!。各位Goodbye!