2024数信杯决赛的DDLLPP

如题，挺有意思的一BSGS

线下断网做了大半天，赛后才知道是群友@等风的题，好家伙

题目：DDLLPP.zip

Part.1 审题·

看题，首先$p$和$g$都是钦定的，而且factor(order-1)居然可以跑出来，就说明它是Smooth的，不妨先跑一下

p = 156115360763408463288966087959515407156846780488826750491921450156778549686830192729652167507054847091579757631324431846770595853060183819226167
g = 16112732773996424707

order = GF(p)(g).multiplicative_order()
fac = factor(order-1)
print(fac)
# 2 * 630764016613 * 636284201767 * 666116332547 * 680344318523 * 684825194551 * 719482804681 * 741454555679 * 761339535743 * 864242985583 * 885840248239 * 925948879099 * 1088296917251

为了方便，不妨令order为

$$q = \frac{p - 1}{2}$$

且令$q-1$的第$i$个因子为$q_i$，观察可得$q_i$都为$40$比特，显然的特殊构造

order = GF(p)(g).multiplicative_order()
q = (p-1) // 2
assert order == q

接下来对于每个$q_i$（除了小因子$2$），都生成了

$$\begin{aligned} x_i &= \frac{q - 1}{q_i} r_i \\ c_i &\equiv g^{m^{x_i} \pmod q} \pmod p \end{aligned}$$

其中$r_i$为$300$比特的未知随机素数，现知道每一组的$x_i$和$c_i$，求$m$

关系有点复杂，先来化简一下，令

$$\begin{aligned} Q_i &= \frac{q-1}{q_i} \\ y_i &\equiv m^{x_i} \pmod q \ \end{aligned}$$

则（注意$q$是模$p$的乘法阶）

$$\begin{aligned} x_i &= Q_i r_i \\ c_i &\equiv g^{y_i} \pmod p \end{aligned}$$

Part.2 DLP爆破·

首先，$m$隐藏在$y_i$中，所以肯定要先把$y_i$解出来

而$c_i$、$g$和$p$都是已知，所以就是一个经典的DLP问题

但直接解肯定是解不出来的，因为Pohlig-Hellman算法需要群阶$q$是Smooth，但这里的$q$是一个大素数

所以继续分析，由于

$$y_i \equiv m^{x_i} \equiv m^{Q_i r_i} \pmod q$$

所以

$$y_i^{q_i} \equiv m^{q_i Q_i r_i} \equiv m^{q_i \frac{q-1}{q_i} r_i} \equiv m^{(q-1) r_i} \equiv 1\pmod q$$

即$y_i$的阶为$q_i$，可以根据这个这个特性修改Pohlig-Hellman算法进行爆破

先改一下$c_i$，得（同样注意$q$是模$p$的乘法阶）

$$\begin{aligned} c_i \equiv g^{y_i} \equiv g^{m^{x_i}} \equiv g^{m^{Q_i r_i}} \equiv g^{(m^{Q_i})^{r_i} \pmod q} \pmod p \end{aligned}$$

不妨令

$$h_i \equiv g^{Q_i} \pmod q$$

这一步是为了找到一个和$m^{Q_i} \pmod q$在同一个（群阶为$q_i$的）子群的群元，为下一步遍历整个子群得到$m^{Q_i r_i} \pmod q$做准备

PS：底数我偷懒就直接拿$g$，实际操作的时候不一定要取$g$，确保是生成元就好

那么接下来就是

$$\begin{aligned} c_i \equiv g^{h_i^{r_i \pmod {q_i}} \pmod q} \pmod p \end{aligned}$$

虽然$r_i$是$300$比特，但$q_i$是$40$比特，而且$h_i$已知，所以实际需要枚举的是$40$比特的$r_i \pmod {q_i}$

枚举时判断$c_i$是否在模$p$下与$g^{h_i^{r_i \pmod {q_i}}}$相等，如果相等的话就可以得到

$$m^{x_i} \equiv h_i^{r_i \pmod {q_i}} \pmod q$$

Part.3 BSGS加速·

理论说的都对，但要枚举$40$比特是不可能在比赛时间内完成的

而根据经验，$40$比特刚好是$2*20$比特，是一个提醒用BSGS大步小步（或者叫MIM中间人攻击）的神奇数字

BSGS算法就不多说了，可以自己查一下相关知识

因为枚举的是$r_i \pmod {q_i}$，所以要先把$r_i$拆解为

$$r_i \pmod {q_i} = \lceil\ \sqrt{q_i}\ \rceil j + k$$

其中

$$0 \le j, k \le \lceil\ \sqrt{q_i}\ \rceil$$

从结论上来说，只需要枚举$20$比特的$\lceil\ \sqrt{q_i}\ \rceil$就好了，是个可以完成的任务

继续拆解，现在可以得到

$$\begin{aligned} c_i &\equiv g^{h_i^{r_i \pmod {q_i}} \pmod q} \\ &\equiv g^{h_i^{\lceil\ \sqrt{q_i}\ \rceil j + k} \pmod q} \\ &\equiv g^{h_i^{\lceil\ \sqrt{q_i}\ \rceil j} h_i^{k} \pmod q} \pmod p \end{aligned}$$

左右做$(h_i^{\lceil\ \sqrt{q_i}\ \rceil j})^{-1} \pmod q$次方，就是

$$\begin{aligned} c_i ^ {(h_i^{\lceil\ \sqrt{q_i}\ \rceil j})^{-1} \pmod q} &\equiv (g^{h_i^{\lceil\ \sqrt{q_i}\ \rceil j} h_i^{k} \pmod q}) ^ {(h_i^{\lceil\ \sqrt{q_i}\ \rceil j})^{-1} \pmod q} \\ &\equiv g^{(h_i^{\lceil\ \sqrt{q_i}\ \rceil j})^{-1} h_i^{\lceil\ \sqrt{q_i}\ \rceil j} h_i^{k} \pmod q} \\ &\equiv g^{h_i^{k} \pmod q} \pmod p \end{aligned}$$

设m = g单测一波

from tqdm import tqdm
from Crypto.Util.number import *

p = 156115360763408463288966087959515407156846780488826750491921450156778549686830192729652167507054847091579757631324431846770595853060183819226167
g = 16112732773996424707
m = g

order = GF(p)(g).multiplicative_order()
q = (p-1) // 2
assert order == q

fac = factor(q-1)
qs = [_[0] for _ in fac[1:]]
assert (q - 1) // 2 == product(qs)

i = 1
ri = getPrime(300)
xi = (order - 1) // (fac[1][0]) * ri
ci = pow(g, pow(m, xi, order), p)

qi = fac[i][0]
Qi = (q - 1) // qi
assert pow(m, xi, q) == pow(m, Qi * ri, q)

c = pow(g, pow(pow(m, Qi, q), ri, q), p)
assert ci == c

qi2 = ceil(sqrt(qi))
ri = ri % qi
j = ri // qi2
k = ri % qi2
assert ri == j * qi2 + k

# when m = g
hi = pow(g, Qi, q)
assert ci == pow(g, pow(hi, qi2*j, q) * pow(hi, k, q), p)
assert pow(ci, pow(hi, qi2*j, q).inverse_mod(q), p) == pow(g, pow(hi, k, q), p)

Hi = pow(hi, -qi2, q)
assert pow(ci, pow(Hi, j, q), p) == pow(g, pow(hi, k, q), p)

然后就可以怼BSGS了

参考代码

from tqdm import tqdm

p = 156115360763408463288966087959515407156846780488826750491921450156778549686830192729652167507054847091579757631324431846770595853060183819226167
g = 16112732773996424707
x = [147649922240733214931938382533299162852239348315322202024816012220190164990577812905694252095760624439151794000123677274895623809190076928245613944439873573607452325298515467162143645462260131175628858455059408827679537866, 147644772650912060216213753348015513337396934565568307574474899641595228671372662635514128646171206026764270327456729799219586211940162384548230502304807283182736386643239100082734250340169696323090999431454785416052449822, 149269411636750703984577479205935816470190760232375388500570098501093159023749275406514479882987042162341103784724354021794002113424056019424236318901646922511135094047290597218316029950824101156465015382592106764226689366, 196150287310738275233976490100915145314242181250918121143881580393441675718040839096578059550733453877149829142446637258193486806259462575641487682725874844491268829888969640104850204930171839770385340396857083270374650086, 176349489748321571272565603934309732142460694086037582675840150899116324432891582015400827333320599715498609930517259021459948220481490102455623631080293179908366540916891458823890009104176809973215536171814869981029570622, 149605686008934472603553678282301090511189963461227603575425242179942083535824047539877995667786104909758015530206013788550584344630984369586721092949558231023248318500741255737481332399584789444750486399094957601650804226, 167090950560844022360160199561741977922499930289466557020320597983114664988151509771708026839823381777607944610693749808422555004194841221065937445184133790727920860624921174387660725583778620218002895521279169556687637458, 172050836264264531258995087363702968248917626047934042630528415155132231140508644029599127244879051539267358002191035421289125204823940752365920253806252280135208982388638638499493964850701542139656158750314341254497187842, 171940203480163609379955377980802940579133331691907105899695838468763589198624951628796073230487728578449404061809128906749299219776549427144505908935772797140694656690672598481007142599063775428416387593447970673282632558, 103219291391536095878880034390346953422786271761523298742391169540330754898330394255571346430660715071684164206474477771947648781967064107154643784549798248272157384762664350763722568774041179922240639096353451631378825726, 117056923364128416359225652777713478574064992861948997533153939432247506685002462469811749968546913699301322755483896459497141460002559118995887988073505736811451551865962302723189596066237079194160774624115297268028146222, 75988171484629553691726063948676260814799772175458832559939830959325834682356888352022448666576264219187808584376882565208027267132917947746488916430085062850228779315594314788358632633193395144020398274344181485674509442]
c = [89211588565232244243020044137513332743269967718877480628261718818351757152813010119069284596895225619225592906209397263094049572230279934266154, 105084158613940886109463172309553111555022087987329070889082019479640792410344881505566965101618478019481030407710176448598323171652419554631833, 106157114923928357578300476119375630224120567854699215551331601909290668630663627567930632807187355693727678752488106832973553103202592938942770, 80557564606220145949033391807467833274034216235778526123196512291405199108579104993671137966232164373337992822860664213094236154838829017972325, 39446948431345684527354210960423038896776791694000880147447072994325975700250899240792675465525991887150481970007736257124244137651624443394152, 119520811258897734242352491410708211023486196867717958794495866712623086226488074898297344260921581145340120126196702495352001228111155023751961, 1342770054334431658111079092718547092324646823520496933189758128906340841380811640267019361812318970025491217723403645803306128707939373166022, 117034748679632935974190191234946643889177466547301929478348628684004040210858236619532197365526820452011678286033898345399811113759206056247927, 142937859112056225912918426292604754870431374511209971957972472983061236076109506454150799842170514956334060919400188570742007461222222639963317, 126864447414128885965807626174194404848334608319577370194369994669518133538013998460358715002795480252978924576799926533593892178036375932388876, 22493364980376274642444643759903756666977805851594216444500605030927010663223507136840503959343412921823289896945796358190298587692628276796010, 115905066506480181865265402577373138871074064300913852519921798659037386902047909009848923352447322605148929915853806888695212542107641045508495]

q = (p - 1) // 2
assert is_pseudoprime(q)

fac = factor(q-1)
qs = [_[0] for _ in fac[1:]]
assert (q - 1) // 2 == product(qs)

def bsgs(g, qi, ci):
  Qi = (q - 1) // qi
  hi = pow(g, Qi, q)
  ghik = set()
  ghiktok = {}

  q2i = ceil(sqrt(qi))
  hik = 1
  for k in tqdm(range(q2i+1)):
    tmp = pow(g, hik, p)
    ghik.add(tmp)
    hik = hik * hi % q
    ghiktok[tmp] = k


  H = pow(hi, -q2i, q)
  Hi = 1
  for j in tqdm(range(q2i+1)):
    tmp = pow(ci, Hi, p)
    if tmp in ghik:
      k = ghiktok[tmp]
      ri = q2i * j + k
      mxiq = pow(g, Qi*ri, q)
      return mxiq
    Hi = Hi * H % q
  return None

mxiq = []
for i in range(len(qs)):
  qi = qs[i]
  ci = c[i]
  xi = bsgs(g, qi, ci)
  mxiq += [xi]
  print(xi)

print('mxiq = %s' % mxiq)

Part.4 共模攻击·

到这里已经知道了各组的

$$m^{x_i} \pmod q$$

现在知道$x_i$和$q$需要求$m$

直观来看只需要做RSA解密就行了，但实际上肯定是不行的

因为

$$x_i = Q_i r_i = \frac{q - 1}{q_i} r_i$$

所以

$$gcd(\varphi(q), x_i) = \frac{q - 1}{q_i} \ne 1$$

就是说并不能求$x_i$的逆

换个思路，现在每一组的模数都是$q$，明文也都是$m$，这不就是共模攻击吗

算一下指数的gcd

assert gcd(x) == 2

即用共模攻击可以解出$m^2 \pmod q$

最后用nth_root开方即可

参考代码

mxiq = [39936014870545142091175714571062824994752492235422647311766010156779896234645534180128238581588631359852188614866069717372898051666957007739049, 52068835286739015717960196448939957872280590350761327672136705373518077924113015170184967086694781662677493227621869974521732648994038887160594, 21039155482723537736312453361822793233960186866597936421194600254287186040767911728280645375779176287933582886243136356291660623398398151030682, 41093028093976451231010245237705431226335728437836088533194774238717851348035756412357062945084131063654328571274303500209731506214343153110644, 40910411569511405291274159499092244380602111760967228199010278602628151744745888173918065885903159639282088602152451151498597445423551427526161, 21393147874920880561322627822765785477802600734911546230086749471275221203885433191033196809126776319555028858469440689886364626130187807187222, 56235416122436942162826302341609219021294806651212995822084672632721872249365257878023931129137402466342215488419593560772040633228068595969705, 11435324193933032987160911861171921893855468657650408649581249264392958245357666961412607684602331129429021919781940558757531277627093622160945, 71019891556729788922079584248619829310928532462680759696498070818494061855597376476133364050968206053689806243797089677564075690880719352714872, 24893898581847147349758742621234115151003775457045295539656475495452307707220584146607157843523547090966139542914583485894088721664233932753992, 65453941737172131359344923334593170460671561439865056763742321047512792017144931597509242445609117497394466523562683827353712449401632042239859, 6819793785647242602610121185872168820617604068913938685355222285637341779572544747413532806194323438255708478892541564142897462349996519769202]

a = xgcd(x)
assert a[0] == 2
a = a[1:]
m2 = product([pow(mxiq[i], a[i], q) for i in range(len(qs))]) % q
ms = GF(q)(m2).nth_root(2, all=True)
print(ms)

for m in ms:
  try:
    flag = bytes.fromhex(Integer(m).hex())
    print(flag)
  except:
    pass

总结·

最后还被添腹亿饼的 @沛公 拿走了一血

真是被1997群友折磨的半天（x