In this CTF challenge we are given the following encryption script:
from Crypto.Util.number import *
p = getPrime(1024)
q = getPrime(1024)
N = p*q
e = 0x10001
z = 768
flag = b"DREAM{???????????????????}"
c = pow(bytes_to_long(flag), e, N)
d = pow(e,-1,(p-1)*(q-1))
dinv = pow(d,-1,N)
hint1 = dinv>>z
hint2 = d>>z
hint3 = (d+dinv) % 2^z
print(f"{c = }")
print(f"{N = }")
print(f"{hint1 = }")
print(f"{hint2 = }")
print(f"{hint3 = }")
as well as the output:
# c = 22157594335444536824539804957503224316011530105000213270082208221066593944954014666682649028694133674560156641233395573360668940167815220144267273966287820743390179842825813921564442940898448403649268126138366346541999383516847671392288475450503228921663055710261222736364832390636399799464290497677394001206519642230355468553180304124754273599272037090190669770012042290863893500557064375980418378974146770317534675349918371288413139540568026717131002910661522889107223072629684473816850628927719500755853803826053326864257172197282550241873511858288263828888477514571946188043879000715780664003346592804294011506971
# N = 25959541354095379330014211523736588310397407563027174748207817754002783083191533477890701227080867897432606754059572855046962831514143019657762820875501757389522439963278185424652050988351722479628525750386024849935812556785023617595192645219002837901875925863581668399339831969660066794677364550759132546080418952727814971975516789298857515890709426151641917337099113196461301621097058914304208257653769808452628154352488765790619868730683895851799316355220677011268783490458072512607009187871657751973095691749268293154373565622703034299847474396773677657530377712298202962607412888316384251050171382195892089032357
# hint1 = 15464998351280885049978241250677908550052088921543412055926782552569730114201666247473246055105315399223369010505411177494944031761554111167815968593847467862816540005306296674691731101951155559188695276576391852694850824877331682887724674655622324597900452774223029587809308492341771478213616624501365158861467752871506595868846315715135486074129927582766119159732319777572491731729171
# hint2 = 7029540180149905451539102727640301157454585448744864593652215724504532500936678968396248056235311937620576932024119332483872809008873452228603492327252210340060398181762267906930140059244295569523008698632999425529950595502067137205887611567798060711937625579291545624591051982915725104082620929153365192057370102698459062120006997479591134423962335183745677834764356654024492868260852
# hint3 = 190722270955073623160671606729858536606154237775586896348182992398405372984126236409160453609793655987256674610721019302148710014962419023950073167692224689931891238034456934018927853575507080194214703887834623936620950946151655803
We are given three hints about the RSA private key d.
Challenges involving partial information leaks are often solved by using coppersmith’s small roots method. The information given in this challenge is:
We can set up equations for these hints with the unknowns:
\[\large \begin{align} \nonumber d &= 2^{768} \cdot \text{hint2} + x \\ \nonumber d^{-1} &= 2^{768} \cdot \text{hint1} + y \\ \nonumber x+y &= \text{hint3} \end{align}\]We can utilize $hint_{3}$ to eliminate the variable $y$:
\[\large \begin{align} \nonumber d^{-1} &= 2^{768} \cdot \text{hint1} + y \\ \nonumber d^{-1} &= 2^{768} \cdot \text{hint1} + \text{hint3} - x \end{align}\]However, we must take into consideration that $hint_{3} \equiv d+d^{-1} \bmod 2^{768}$. There may be an extra $2^{768}$ term in $d^{-1}$ depending on the carry bit. In the case of the handout, this term is present:
\[\large d^{-1} = 2^{768} \cdot \text{hint1} + \text{hint3} - x\]With an expression for $d$ and $d^{-1}$ in terms of $x$, we can set up the following univariate polynomial:
\[\large d \cdot d^{-1} - 1\equiv 0 \mod N\]The root $x$ has an upper bound of $2^{768}$. This univariate case can easily be solved in SageMath:
z = 768
R.<x> = PolynomialRing(Zmod(N))
d = (hint2<<z) + x
dinv = (hint1<<z) + (hint3-x+2^z)
f = d*dinv-1
roots = f.monic().small_roots(X=2^z)
And with the root recovered, $d$ can be reconstructed, letting us decrypt the ciphertext:
d = (hint2<<z) + roots[0]
print(long_to_bytes(pow(c,d,N)))
# b'DREAM{sm4ll_r00ts_2_sm4ll}'
from Crypto.Util.number import *
c = 22157594335444536824539804957503224316011530105000213270082208221066593944954014666682649028694133674560156641233395573360668940167815220144267273966287820743390179842825813921564442940898448403649268126138366346541999383516847671392288475450503228921663055710261222736364832390636399799464290497677394001206519642230355468553180304124754273599272037090190669770012042290863893500557064375980418378974146770317534675349918371288413139540568026717131002910661522889107223072629684473816850628927719500755853803826053326864257172197282550241873511858288263828888477514571946188043879000715780664003346592804294011506971
N = 25959541354095379330014211523736588310397407563027174748207817754002783083191533477890701227080867897432606754059572855046962831514143019657762820875501757389522439963278185424652050988351722479628525750386024849935812556785023617595192645219002837901875925863581668399339831969660066794677364550759132546080418952727814971975516789298857515890709426151641917337099113196461301621097058914304208257653769808452628154352488765790619868730683895851799316355220677011268783490458072512607009187871657751973095691749268293154373565622703034299847474396773677657530377712298202962607412888316384251050171382195892089032357
hint1 = 15464998351280885049978241250677908550052088921543412055926782552569730114201666247473246055105315399223369010505411177494944031761554111167815968593847467862816540005306296674691731101951155559188695276576391852694850824877331682887724674655622324597900452774223029587809308492341771478213616624501365158861467752871506595868846315715135486074129927582766119159732319777572491731729171
hint2 = 7029540180149905451539102727640301157454585448744864593652215724504532500936678968396248056235311937620576932024119332483872809008873452228603492327252210340060398181762267906930140059244295569523008698632999425529950595502067137205887611567798060711937625579291545624591051982915725104082620929153365192057370102698459062120006997479591134423962335183745677834764356654024492868260852
hint3 = 190722270955073623160671606729858536606154237775586896348182992398405372984126236409160453609793655987256674610721019302148710014962419023950073167692224689931891238034456934018927853575507080194214703887834623936620950946151655803
z = 768
R.<x> = PolynomialRing(Zmod(N))
d = (hint2<<z) + x
dinv = (hint1<<z) + (hint3-x+2^z)
f = d*dinv-1
roots = f.monic().small_roots(X=2^z)
d = (hint2<<z) + roots[0]
print(long_to_bytes(pow(c,d,N)))