In this CTF challenge, we are given the following python source code:
from Crypto.Util.number import *
from secret import flag
z = 567
p = getPrime(1024)
q = getPrime(1024)
n = p*q
c = pow(bytes_to_long(flag), 65537, n)
tot = (p-1) * (q-1)
d = int(pow(65537, -1, tot))
dinv = int(pow(d, -1, n))
h = int(dinv >> z)
hpq = (int((p+q)>> z))
with open('out.txt', 'w+') as f:
f.write(f'{n=}\n')
f.write(f'{h=}\n')
f.write(f'{hpq=}\n')
f.write(f'{c=}\n')
as well as the file out.txt We are given the typical n, e and c parameters, as well as two hints h and hpq.
We are given two hints for this RSA challenge; h and hpq.
h is the most significant bits of dinv where dinv is equal to $d^{-1} \mod N$
hpq is the most significant bits of the sum of the modulus factors $p+q$
These kinds of challenges can usually be solved using coppersmith lattice attacks. We have to derive some function $f$ that contains the hints with roots $x, y$. Solving for the roots, we can recover $d^{-1}\mod N$ and $p+q$.
for hpq, we can expand $\varphi(N)$ in the following equation:
Here we can see the term $p+q$ appear after expanding $\varphi(N)$. We also find an equation for $d$. We can then substitute $d$ into the following equation:
\[\large\begin{aligned} d \cdot d^{-1} &\equiv 1 \mod N \\ d^{-1} \cdot d - 1 &\equiv 0 \mod N \\ d^{-1} \cdot\frac{1 + k \cdot (N + 1 - (p+q))}{e} - 1 &\equiv 0 \mod N \\ d^{-1} \cdot (1 + k \cdot (N + 1 - (p+q))) - e &\equiv 0 \mod N \end{aligned}\]We can now substitute $p+q$ and $d^{-1}$ for our hints:
\[\large\begin{aligned} d^{-1} \cdot (1 + k \cdot (N + 1 - (p+q))) - e &\equiv 0 \mod N \\ ((h<<z) + x) \cdot (1 + k \cdot (N + 1 - ((hpq<<z)+y))) - e &\equiv 0 \mod N \end{aligned}\]We can use this as our function $f$ and solve for the roots. We have the roots $k,x,y$ so we will have to use multivariate coppersmith.
For the bounds, we know $x$ and $y$ are both upper bounded by $2^z$, but $k$ is different. We can take into consideration this equation:
\[\large\begin{aligned} e \cdot d & \equiv1 \quad(\bmod \varphi(N)) \\ \Longrightarrow e \cdot d & =1 + k \cdot \varphi(N) \\ \Longrightarrow e \cdot d &\approx k \cdot \varphi(N) \end{aligned}\]Since $d$ and $\varphi(N)$ have almost the same bit-size, it must mean that $e$ and $k$ also have almost the same bit-size. We can use $e$ as the upper bound for $k$.
Since this is a multivariate coppersmith problem, I will take in use the useful scripts from kiona’s git repo. Specifically, I will use the coppersmith_multivariate_heuristic function.
load('~/tools/coppersmith/kiona/coppersmith_multivariate_heuristic.py')
We can load in our values
n=13986357905153484822874300783445968480194277882812317554826224241536479785567487956712558237728345348661360577246137576216953724039680969623887884690471844396542763308129517234365819619617071449273126659007918716307793788623728052337632935762139796688014791419718949572448772521789488223910450877828732015095423443037519388747356327730350934152781671783952028215703864406564741666179193772037496984854699143314813242721157017296866888522135989818414587193505121794302821401677072507471357592358012342178011963104524959087968374300060349343826214249928530346877968114749229074874962737714935221065368318487049394644831
h=10474216468878927114435400909130676124750910912012236182806861194655854223324539867768381265996955193355030239325750528328250897464859373863289680002879536341349759323910048168674147097644573874679268018966497862685092382336865554114348153248267599439087357199554652601126191061921516650448119261614064051599968120061991607030873881013657693987836636730528537557619595799676312850875727477092697270452300532360780188724484703363561848754770976459
hpq=492124417091708682668644108145880307537308922842816506360717440112116492381514432506339907757228214359689270777951081610062506962769167209
c=4715651972688371479449666526727240348158670108161494767004202259402013317642418593561463200947908841531208327599049414587586292570298317049448560403558027904798159589477994992384199008976859139072407664659830448866472863679123027179516506312536814186903687358198847465706108667279355674105689763404474207340186200156662095468249081142604074167178023479657021133754055107459927667597604156397468414872149353231061997958301747136265344906296373544580143870450924707559398134384774201700278038470171319329716930036843839101955981274793386611943442507144153946307781795085665793554799349509983282980591388585613674226899
e = 65537
z = 567
and set up our function $f$ with roots $k,x,y$:
P.<k, x, y> = PolynomialRing(Zmod(n))
f = (1 + k*(n+1-((hpq<<z)+y)))*((h<<z)+x)-e
Using kiona’s multivariate heuristic function, we can recover the roots:
roots = coppersmith_multivariate_heuristic(f, (e, 2**z, 2**z), 1.0)
And lastly, we can take the modular inverse $d^{-1}$ to derive the private key $d$ and decrypt the ciphertext $c$
d = pow(((h<<z)+ roots[0][1]), -1, n)
print(bytes.fromhex(f'{pow(c, d, n):x}').decode())
This gives us our flag: TCP1P{AmEeeeeEE33333eeee333_T_T_8883938ef7571cc2}
load('~/tools/coppersmith/kiona/coppersmith_multivariate_heuristic.py')
n=13986357905153484822874300783445968480194277882812317554826224241536479785567487956712558237728345348661360577246137576216953724039680969623887884690471844396542763308129517234365819619617071449273126659007918716307793788623728052337632935762139796688014791419718949572448772521789488223910450877828732015095423443037519388747356327730350934152781671783952028215703864406564741666179193772037496984854699143314813242721157017296866888522135989818414587193505121794302821401677072507471357592358012342178011963104524959087968374300060349343826214249928530346877968114749229074874962737714935221065368318487049394644831
h=10474216468878927114435400909130676124750910912012236182806861194655854223324539867768381265996955193355030239325750528328250897464859373863289680002879536341349759323910048168674147097644573874679268018966497862685092382336865554114348153248267599439087357199554652601126191061921516650448119261614064051599968120061991607030873881013657693987836636730528537557619595799676312850875727477092697270452300532360780188724484703363561848754770976459
hpq=492124417091708682668644108145880307537308922842816506360717440112116492381514432506339907757228214359689270777951081610062506962769167209
c=4715651972688371479449666526727240348158670108161494767004202259402013317642418593561463200947908841531208327599049414587586292570298317049448560403558027904798159589477994992384199008976859139072407664659830448866472863679123027179516506312536814186903687358198847465706108667279355674105689763404474207340186200156662095468249081142604074167178023479657021133754055107459927667597604156397468414872149353231061997958301747136265344906296373544580143870450924707559398134384774201700278038470171319329716930036843839101955981274793386611943442507144153946307781795085665793554799349509983282980591388585613674226899
e = 65537
z = 567
P.<k, x, y> = PolynomialRing(Zmod(n))
f = (1 + k*(n+1-((hpq<<z)+y)))*((h<<z)+x)-e
roots = coppersmith_multivariate_heuristic(f, (e, 2**z, 2**z), 1.0)
d = pow(((h<<z)+ roots[0][1]), -1, n)
print(bytes.fromhex(f'{pow(c, d, n):x}').decode())