SEC-T CTF 2019 | Trivial rsa - crypto-writeup-public

Juggling with some algebra!

cloud_download Download: trivial_rsa.tar.gz

sage: n1
16665162598091416675035243372929255215330237988600063606115453406246759269279788760269977993441302227754535063989940158801403082299136924692382379772238783511717805089453627769958409474798262234585212880036578100065244955419654350030210214612873050000707217728997449651244785327256673209001617229204596903739745000294771409411741050416912250410842101344110865361910624576900847453308353320549785990249062848385268654951594713494728031930339317011245422247813046177464952338694367015023462166849724348822067012372916419798329882575892837697474973759070677459272935998500533063881083981623170007582400032456357369057331
sage: n2
12327967666608400089684292637697723886692743047311943117634453297696672596602132832770180763706410481136385428797064430470744303260875130025364968184033440278168149230015012651339700361911455246276535179299003908649820055478166532502332896978314839548456221498409689020137730201961802661796522959185289676293168958100994789278927928614060667061494784764996405812503722093377901735054396731379083755482112808051044511509930814761992548239396939638987562480503407989092943629763956630828533555667490559450650474172687439499014071217245302164885369990725379389835929411041979972161099398047802667999958241746711037377019
sage: (p1 - p2) % (q1 - q2)
651462892194717457221755220174856890047929116650078860763950453454949587828096234616831315488704251531401792609600066162972268247282594239275742779598127716518383086923760296725577120504817396207799394031948181614036825015620143890966541423830037471615505961486852765107641800802598611031433822941186606730
sage: (q1 - q2) % (p1 - p2)
442296418993240063675266142454740191465599525570774611710139968474930425844945295951472133337584882919079119792948035796322583493017921438477858246253211352232247225094327539626813294415765610979636199753519138117254187197466480294243789769005210602152862859358315543589192060482998253522480707816974954144
sage: pow(m, 65537, n1)
7899134322955645246464106475661567371519411492907819361218537936109003314263398594946847506479710018156056516572597388680265129465680577498126784603599657304217232946737359907830193767343579320119617475061103397775839997585822041520474984253434505877605909867411822079954503549880731554010164405517963598831678530319685550356656748243909520671642189043288332595811057445820791781035731118992393238366930032136586970961554635691292784903624264141333213116074342104788426932419021114413087179933685563867060402709899375500659953038354210747849030819495299042436380277429490866466199179979698665821921998413237763283416

$(p1-p2) \mod (q1-q2)$ と $(q1- q2) \mod (p1-p2)$ が与えられるのでなんとかしろという問題。

とりあえず

$k1 = (p1 - p2) \mod (q1 - q2)$

$k2 = (q1 - q2) \mod (p1 - p2)$

で、 $k1 > k2$ なので $p1 - p2 < q1 - q2$ ということがわかる。

modでreductionされずに残って $k1 = p1 - p2$

一方k2は適当な正整数 $i$ を持ってきて

$p1 - p2 = k1$

$q1 - q2 = k2 + i(p1 - p2) = k2 + ik1$

$n1 = p1q1 = (p2 + k1)*(q2 + k2 + ik1) = (p2 + k1)*(n2/p2 + k2 + ik1)$

$n1p2 = (p2 + k1)*(n2 + (k2 + ik1)*p2)$

これで $p2$ を探索してみたいところだけど、よく考えると $p2$ を求めても仕方がなくて、どうせなら $p1$ がほしい。

$n2 = p2q2 = (p1 - k1) * (q1 - k2 - ik1) = (p1 - k1) * (n1/p1 - k2 - ik1)$

$n2p1 = (p1 - k1)*(n1 - (k2 + ik1)p1)$

こんかいもsympyを使って解いてみる

from sympy import symbols, Eq
from sympy.solvers import solve
from Crypto.Util.number import *

n1 = 16665162598091416675035243372929255215330237988600063606115453406246759269279788760269977993441302227754535063989940158801403082299136924692382379772238783511717805089453627769958409474798262234585212880036578100065244955419654350030210214612873050000707217728997449651244785327256673209001617229204596903739745000294771409411741050416912250410842101344110865361910624576900847453308353320549785990249062848385268654951594713494728031930339317011245422247813046177464952338694367015023462166849724348822067012372916419798329882575892837697474973759070677459272935998500533063881083981623170007582400032456357369057331
n2 = 12327967666608400089684292637697723886692743047311943117634453297696672596602132832770180763706410481136385428797064430470744303260875130025364968184033440278168149230015012651339700361911455246276535179299003908649820055478166532502332896978314839548456221498409689020137730201961802661796522959185289676293168958100994789278927928614060667061494784764996405812503722093377901735054396731379083755482112808051044511509930814761992548239396939638987562480503407989092943629763956630828533555667490559450650474172687439499014071217245302164885369990725379389835929411041979972161099398047802667999958241746711037377019
k1 = 651462892194717457221755220174856890047929116650078860763950453454949587828096234616831315488704251531401792609600066162972268247282594239275742779598127716518383086923760296725577120504817396207799394031948181614036825015620143890966541423830037471615505961486852765107641800802598611031433822941186606730
k2 = 442296418993240063675266142454740191465599525570774611710139968474930425844945295951472133337584882919079119792948035796322583493017921438477858246253211352232247225094327539626813294415765610979636199753519138117254187197466480294243789769005210602152862859358315543589192060482998253522480707816974954144
e = 65537
c = 7899134322955645246464106475661567371519411492907819361218537936109003314263398594946847506479710018156056516572597388680265129465680577498126784603599657304217232946737359907830193767343579320119617475061103397775839997585822041520474984253434505877605909867411822079954503549880731554010164405517963598831678530319685550356656748243909520671642189043288332595811057445820791781035731118992393238366930032136586970961554635691292784903624264141333213116074342104788426932419021114413087179933685563867060402709899375500659953038354210747849030819495299042436380277429490866466199179979698665821921998413237763283416

p1 = symbols("p1", integer=True)
for i in range(10000):
    print(i)
    ans = solve([Eq(n2 * p1, (p1 - k1) * (n1 - p1 * (k2 + i * k1)))])
    for a in ans:
        p1_ = int(a[p1])
        if p1_ <= 1 or p1_ == n1 or n1 % p1_ != 0:
            continue
        q1 = n1 // p1_
        phi = (p1_ - 1) * (q1 - 1)
        d = inverse(e, phi)
        m = pow(c, d, n1)
        print(long_to_bytes(m))

i = 63のときに解けた。

b'SECT{ju99lin_w1d_d3m_alg3br0s}\x03\xeepuXY&\xc3\xb3f\x9fT6\x06\xb5\x80\xcf\xab\xb0AS\xd7v\xac\x95\xe4}\xcd\x7fv\x8eS\xfe\xa9.,\x14\x1d\x9b\x1f\xad?\xff\xf8\x8e\xda\x04G\xd1\xaeSHS\x91Ht2\x1e\xac6\xa0T-\x11\x117\x12&\x84c\xd1\t\xf6\tK\xd5G\xcbE\xda\xe6\xf3\xa8\x96\x16\xd3\xe6;}\x15\xe4\xc2\x145]\x82\x0cS'