异或的密件 - Writeup by AI题目信息来源: BugKu类别: Crypto (RSA)考点: RSA、数论、位运算、逐位恢复攻击题目分析给定信息题目提供了以下代码和数据fromCrypto.Util.numberimport*fromsecretimportflag p,q,egetPrime(512),getPrime(512),65537np*qprint(n)print(pow(bytes_to_long(flag),e,n))print(p^q)输出数据n: 1024 位 RSA 模数c: 加密后的密文p ^ q: p 和 q 的异或值关键泄露问题难点标准的 RSA 加密但额外泄露了p ^ q。通常 RSA 的安全性依赖于大整数分解的困难性但这里泄露了 p 和 q 的异或值这足以让我们分解 n。解题思路方法一代数方法效率较低利用以下关系np×qn p \times qnp×qp⊕qkp \oplus q kp⊕qk(已知)pq(p⊕q)2(p∧q)k2tp q (p \oplus q) 2(p \land q) k 2tpq(p⊕q)2(p∧q)k2t通过二次方程判别式搜索但计算量巨大。方法二逐位恢复攻击本题解法⭐核心思想从最低位到最高位逐位确定 p 和 q 的每一位。数学原理对于第 i 位设pip_ipi和qiq_iqi分别为 p 和 q 的第 i 位已知(p⊕q)iki(p \oplus q)_i k_i(p⊕q)iki则qipi⊕kiq_i p_i \oplus k_iqipi⊕ki因此对于每一位只有 2 种可能(pi,qi)∈{(0,ki),(1,1−ki)}(p_i, q_i) \in \{(0, k_i), (1, 1-k_i)\}(pi,qi)∈{(0,ki),(1,1−ki)}利用乘法的低位性质n mod 2i1(p×q) mod 2i1n \bmod 2^{i1} (p \times q) \bmod 2^{i1}nmod2i1(p×q)mod2i1如果已知 p 和 q 的低 i 位可以验证第 i 位的哪种选择满足上述等式。算法步骤初始化: 候选对列表candidates [(0, 0)]逐位迭代(i 从 0 到 n.bit_length()-1):读取ki(p⊕q)i1k_i (p \oplus q) i \ 1ki(p⊕q)i1对于每个候选对(plow,qlow)(p_{low}, q_{low})(plow,qlow):尝试pi0p_i 0pi0和pi1p_i 1pi1计算对应的qipi⊕kiq_i p_i \oplus k_iqipi⊕ki构建新的低位值并验证乘法保留满足条件的候选对去重最终验证: 检查找到的候选对是否满足p×qnp \times q np×qn和p⊕qkp \oplus q kp⊕qk复杂度分析理论上每增加一位候选数可能翻倍但实际上由于乘法约束候选数增长缓慢通常保持在几百个总复杂度约为O(bits×avg_candidates)O(\text{bits} \times \text{avg\_candidates})O(bits×avg_candidates)远优于暴力分解完整代码fromCrypto.Util.numberimport*importgmpy2# 题目数据n95562862201427823336067582946015664592322094165595564734633544688981046852555011419775655956374062008786746746891813021004709042123448569672651054374497117781385077761604798008040559786965945283482187568723860843102761550095675462113034490834106391146206127719571788775471987423072874061061356320902761206747c58018864342175249049694134001884226579642875631182782878281354592254157977954421579318472108713919321974874420722899431290670929852819379385452970688029168700791027405141925684477493483887731431031816527384418626561771300298831874904373607310738053244602209907791201121366196248860844889191791822466040121521pxorq222698508797767721110391484298656215822060469539734106657369897669776822548641301202460186331633383845935831146767129439812408208215003896191936416553098e65537defsolve_bit_by_bit(n,pxorq):逐位恢复 p 和 qprint([*] 使用逐位恢复方法求解...)candidates[(0,0)]foriinrange(n.bit_length()):new_candidates[]pxorq_bit(pxorqi)1n_lown((1(i1))-1)forp_low,q_lowincandidates:forp_bitin[0,1]:q_bitp_bit^pxorq_bit new_pp_low|(p_biti)new_qq_low|(q_biti)if(new_p*new_q)((1(i1))-1)n_low:new_candidates.append((new_p,new_q))new_candidateslist(set(new_candidates))candidatesnew_candidatesifi%500:print(f[*] 处理到第{i}位候选数{len(candidates)})# 验证forp_low,q_lowincandidates:ifp_low*q_lownand(p_low^q_low)pxorq:returnp_low,q_lowreturnNone# 主程序p,qsolve_bit_by_bit(n,pxorq)print(f[] p {p})print(f[] q {q})# RSA 解密phi(p-1)*(q-1)dgmpy2.invert(e,phi)mpow(c,d,n)flaglong_to_bytes(m)print(f\n[] Flag:{flag.decode()})运行结果[*] 使用逐位恢复方法求解... [*] n 的位数1024 [*] 处理到第 0 位候选数1 [*] 处理到第 50 位候选数240 ... [*] 处理到第 1000 位候选数848 [] 找到因子 [*] p 9887505052686473792161003994931717181923561259381054161766485392846667186932172561131205613433805623242663298666671415728947348813673255436356622476741456377 [*] q 9665012729926547034857639298119117556730083767461462520975993442411138448829909219957347658311550667318937998931339938018539711143025090110126244259916605811 [] 验证p * q True [] 验证p ^ q True [] Flag: NUAACTF{XXX}
