buu [WUSTCTF2020]dp_leaking_1s_very_d@angerous 1

题目描述：

e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825

题目分析：

• 首先我们先看下解题脚本，再进行分析：

e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825
for i in range(1,65535):p = (dp*e-1)//i+1if n%p == 0:q = n//pbreak
# print(p)
# print(q)
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
flag = libnum.n2s(int(m)).decode()
print(flag)

• 主要还是这串代码—>有点不太理解，那下面具体来分析这串代码的由来

已知：

c = m^e mod n
m = c^d mod n
ϕ(n)=(p−1)*(q−1)
d∗e ≡ 1 mod ϕ(n)
dp = d mod (p−1)

由上式可以得到

dpe≡de mod (p−1)

因此可以得到

式1：d∗e=k∗(p−1)+dp∗e
式2：d∗e≡1 mod ϕ(n)

式1带入式2

=> k∗(p−1)+dp∗e ≡1 mod ϕ(n)

=> k∗(p−1)+dp∗e ≡1 mod (p−1)∗(q−1)

=> k1∗(p−1)+dp∗e = k2*(p−1)∗(q−1)+1

=> dp * e = k2*(p−1)∗(q−1)+1-k1∗(p−1)+dp∗e

=> dp * e = (p-1)[k2(p-1)-k1]+1

因dp<p−1（dp是d//（p-1）的取整，dp<p−1）

所以e > k2∗(q−1)−k1

再次回到

dp * e = (p-1) * [k2*(p-1)-k1]+1

假设 x=k2∗(q−1)−k1

那么x的范围为 (0,e)

x∗(p−1)+1=dp∗e

枚举 x 求出p-1，即遍历(0,e)的范围，其中肯定有一个p可以被n整除，那么求出p和q

• 最终运行代码得到 flag{dp_leaking_1s_very_d@angerous} (嚯！原来题目就是答案啊！)

收获与体会：

• 知道了求dp泄露的题
• 理解了原理