CONFidence CTF 2019 Teaser|Bro, do you even lift?

lift.sageとout.txtが与えられる。

flag = int(open('flag.txt','r').read().encode("hex"),16)
ranges = int(log(flag,2))
p = next_prime(ZZ.random_element(2^15, 2^16))
k = 100
N = p^k
d = 5
P.<x> = PolynomialRing(Zmod(N), implementation='NTL')
pol = 0

for c in range(d):
    pol += ZZ.random_element(2^ranges, 2^(ranges+1))*x^c


remainder = pol(flag)
pol = pol - remainder
assert pol(flag) == 0

print(p)
print(pol)

35671
12172655049735206766902704703038559858384636896299329359049381021748*x^4 + 11349632906292428218038992315252727065628405382223597973250830870345*x^3 + 9188725924715231519926481580171897766710554662167067944757835186451*x^2 + 8640134917502441100824547249422817926745071806483482930174015978801*x + 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728

問題としては与えられた多項式 $a_4x^4 + a_3x^3 + a_2x^2 + a_1^x + a_0 \equiv 0 \mod 35671^{100}$ の解を求めろということになる

問題名もヒントにしてpolynomial modular root liftとかで調べるとHensel's lemmaというのが出てくる。雑にここなどを読むと#### mod p での因数分解を利用して mod p^k での因数分解ができる的な定理に見える。実装するのは面倒なのでsageに任せたらなんとかならないだろうかこことかできそうに見える

できなかった。p4は激つよなのでライブラリにして持ってるらしい。幸いにもwriteupを見つけた。fには多項式を、dfにはその微分を、pにはpを、kにはkをbase_solutionにはmod pでの根を与える。

fがややこしい多項式なのでpythonでは力不足だと思いsageに移植して頑張った。結局wikipediaみながらやった。

def hensels_lifting(f, p, k):
    df = f.derivative()

    # convert function on GF(p)
    R.<y> = PolynomialRing(GF(p), "y")
    f2 = R(f.list())
    base = Integer(f2.roots()[0][0])

    prev_r = base
    for i in range(2, k+1):
        pi = p ^ i
        r = prev_r
        fr = f(r)
        dfr = df(r)
        s = Integer( r - fr * inverse_mod(Integer(dfr), pi) )
        prev_r = Integer(Mod(s, pi))

        # very slow
        # R.<z> = PolynomialRing(GF(pi), "z")
        # f3 = R(f.list())
        # assert f3(s) == 0
    return prev_r


x = polygen(QQ, 'x')
f = (
    12172655049735206766902704703038559858384636896299329359049381021748 * x
    ^ 4 + 11349632906292428218038992315252727065628405382223597973250830870345 * x
    ^ 3 + 9188725924715231519926481580171897766710554662167067944757835186451 * x
    ^ 2
    + 8640134917502441100824547249422817926745071806483482930174015978801 * x
    + 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728
)
p = 35671
k = 100

from Crypto.Util.number import long_to_bytes
print(long_to_bytes(hensels_lifting(f, p, k)))

p4{Th4t5_50m3_h34vy_l1ft1n9}