♧ Godown 安全知识树

RSA 共享素数 + 已知明密文对恢复小 e:gcd(n1,n2) 分解后遍历 e 匹配 pow(294,e,n)

crypto/rsa · verified

一句话结论

题目给出两组 (c, n)、断言 e < 100000,并额外给出 pow(294, e, n) 时:先用 gcd(n1, n2) 求得共享素因子分解两个模数,再以“已知明文 294 的密文”为 oracle 遍历 e < 100000 匹配 pow(294, e, n1) == c294,得到 e 后标准解密即可(原文 BJD{p_is_common_divisor})。

原理

  • 共享素数:两个模数若由同一随机源生成,可能共享一个素因子;gcd(n1,n2)=p 即可同时分解 n1、n2,得到各自的 q。
  • e 的已知明密文 oracle:RSA 是确定性函数,294^e mod n 对每个 e 都有唯一结果;题目把 pow(294,e,n) 的数值直接给出,等于提供了一个“用 294 试 e”的验证接口。遍历 e 的 10 万种取值,只有正确的 e 会让等式成立。
  • 为什么不用分解 φ 后直接求 e:e 与 φ(n) 无直接等式可解;e 是从明文-密文对中恢复的指数,属于离散对数问题,但 e 范围小(<100000)使暴力可行。
  • 解密:d = e⁻¹ mod φ(n1)、m = c1^d mod n1,long_to_bytes 即得明文。
  • 边界:若 e 范围很大,枚举不可行,需要其他信息(如已知 e 的位长、e 与 φ 的关系);若 n1/n2 不共享素因子,本卡退化为普通“已知 e 求 d”。

触发条件

  • 题目给出多组 (c,n),且 n 之间可能共享素因子(同源随机数/批量生成)。
  • e 很小或有限范围(题干常写 assert e < 100000)。
  • 额外给出某个已知明文的加密结果(如 pow(294,e,n)),或可自行构造已知明文查询。
  • 能运行 gcd 与大整数模幂。

利用步骤

  1. p = gcd(n1, n2);若非 1,q1 = n1//p、q2 = n2//p,验证 p*q == n。
  2. phi = (p-1)*(q-1)(对应被解的那组模数)。
  3. 遍历 e in range(100000):若 pow(294, e, n1) == c294 则记录 e。
  4. d = gmpy2.invert(e, phi),m = pow(c1, d, n1),libnum.n2s(int(m))。
  5. 用 pow(m, e, n1) == c1 回环验证。

PoC

import gmpy2, libnum

c1 = 12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
n1 = 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037

c2 = 979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721
n2 = 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047

c294 = 381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018

p = gmpy2.gcd(n1, n2)
q1 = n1 // p
phi = (p - 1) * (q1 - 1)

e = next(i for i in range(100000) if pow(294, i, n1) == c294)
d = gmpy2.invert(e, phi)
m = pow(c1, d, n1)
print(libnum.n2s(int(m)))   # b'BJD{p_is_common_divisor}'

变体与关联

  • 变体:若题目不给 pow(294,e,n),可尝试常见 e(3/17/65537)或小范围枚举并用明文格式过滤(见 [[ctf-crypto-rsa-unknown-e-rail-fence-filter]])。
  • 变体:多组模数批量 gcd 找共享素因子(见 [[ctf-crypto-rsa-shared-prime-batch-gcd]]);共享素数后 e 已知则直接解密。
  • 变体:已知明文对不同(不是 294),公式相同;也可用多组已知对交叉验证 e。
  • 边界:e 范围大或 gcd 全 1 时此方法失效;此时考虑低加密指数、Wiener、Coppersmith 等。

检测与防御

  • 题目识别:题干出现 assert e<100000、pow(294,e,n) 或多组 (c,n) 并列——优先跑 gcd 与 e 枚举。
  • 真实系统防御:密钥生成必须使用高质量随机源,避免跨密钥共享素因子;RSA 模数 ≥2048 位;不要把已知明文的加密结果暴露给攻击者作为 e 的 oracle。
  • 加固:定期对批量密钥做 gcd 自检(PSA 类检测),发现共享因子立即轮换。