RSA-详解dp泄漏

原理：

0.基本数学公式

$a=kb+p$

$amodb=p$

1.RSA的基本公式

$c\equiv m^{e}modn$ $m\equiv c^{d}modn$ $\varphi (n)=(p-1)\times (q-1)$ $d\times e\equiv 1mod\varphi (n)$

2.dp是什么

$dp\equiv dmod(p-1)$

3.推导过程

将该公式变形：

$dp\equiv dmod(p-1)$ $\Rightarrow$ $dp\times e$ $\equiv$ $d\times emod(p-1)$ $\Rightarrow$ $d\times e\equiv k\times (p-1)+dp\times e$

变形后的公式与下式结合

$d\times e\equiv 1mod\varphi (n)$

因为：

$\varphi (n)=(p-1)\times (q-1)$

所以我们可以进行变形：

$\Rightarrow$$d\times e\equiv 1mod(p-1)\times (q-1)$

得到：

$k\times (p-1)+dp\times e=1mod\varphi (n)$

再次变形：

$k_1\times (p-1)+dp\times e=1mod(p-1)\times (q-1)$

结合：

$k_1\times (p-1)+dp\times e=k_2\times (p-1)\times (q-1)+1$

$\Rightarrow$ $dp\times e$= $[k_2\times (p-1)\times (q-1)+1]-[k_1\times (p-1)]$

$\Rightarrow$ $dp\times e$= $[k_2\times (q-1)-k_1]\times (p-1)+1$

$设：X=k_2\times (q-1)-k_1$

$\Rightarrow$ $dp\times e=$$X\times (p-1)+1$

$\Rightarrow$ $dp<p-1$ $\Rightarrow$ $X<e$ $\Rightarrow$$X\in (0,e)$

4.求p

遍历$X$（65537种可能）,求出$(p-1)$,得到$p$且能被$n$整除；接下来就是常规RSA的解法

for i in range(1,65538): if (dp*e-1)%i == 0: if n%(((dp*e-1)/i)+1)==0: p=((dp*e-1)/i)+1 q=n/(((dp*e-1)/i)+1) phi = (p-1)*(q-1) d = gmpy2.invert(e,phi)%phi

例题：

[WUSTCTF2020]dp_leaking_1s_very_d@angerous

题目：

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

解密脚本：

import gmpy2 e = 65537 n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847 c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869 dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825 for x in range(1, e): if(e*dp%x==1): p=(e*dp-1)//x+1 if(n%p!=0): continue q=n//p phin=(p-1)*(q-1) d=invert(e, phin) m=powmod(c, d, n) if(len(hex(m)[2:])%2==1): continue print("m:",m) #print(hex(m)[2:]) print("flag:",bytes.fromhex(hex(m)[2:]))