ASCIS Finals 2023 - Crypto Gym writeup

Today, suddenly I found that I still saved the code for a Crypto challenge in ASCIS Finals 2023. Welp, during the competition, it was a crisis that this challenge is actually revealed the flag in the source code given to the teams… :)

from Crypto.Util.number import *

flag = b"ASCIS{W3llDone_hitting_the_crypto_gym}"
p = random_prime(2^64,False,2^63)
k = 100
N = p^k
R.<x> = PolynomialRing(Zmod(N), implementation="NTL")

pol = R([getrandbits(303) for _ in range(8)])
flag_bytes = bytes_to_long(flag)
rem = pol(bytes_to_long(flag))
pol2 = pol - rem

print(p)
print(pol2)

Well, but I think the challenge is still interesting, and worth for a formal writeup. So here we go! (Btw I am learning to prepare next year ASCIS too :))

Description

As you see from the source code, the challenge gives us two things:

A prime 64-bit prime $p$ , and $k = 100$ . The purpose is to make a $\mathbb{Z}_{p^k}$ ring.
A polynomial $pol2$ over $\mathbb{Z}_{p^k}$ , where $pol2(x) = f(x) - f(F)$ and F = bytes_to_long(flag). These two polynomials share their coefficients, which are random 303-bit integers. (Of course, except the last coefficient, which is $a_8-F$ )

Solution

As we have:

f(x) = a_1x^7 + a_2x^6 + a_3x^5 + a_4x^4 + a_5x^3 + a_6x^2 + a_7x + a_8

And,

f(F) = a_1F^7 + a_2F^6 + a_3F^5 + a_4F^4 + a_5F^3 + a_6F^2 + a_7F + a_8

Therefore,

pol2(x) = f(x) - f(F) = a_1(x^7 - F^7) + a_2(x^6 - F^6) + \ldots + a_6(x^2 - F^2) + a_7(x - F)

Therefore, $F$ is a trivial root of $pol2$ ! The only thing we need to do is to find the root of $pol2$ in $\mathbb{Z}_{p^k}$ , where fortunately we are given $p$ and $k$ . To this point, you can either using Hensel’s Lifting or working with p-adics. However, Hensel’s Lifting seems not to be good, as it needs to iterate from 0 -> p for each lifting (lmao I am so weak can’t afford this), so I decided to use p-adics instead. Luckily, there is a writeup for a challenge that looks a little bit alike this one (lmao I think they copycat this challenge as the challenge of RLWE), so I do a little bit modification on it only.

from sage.all import *
from Crypto.Util.number import long_to_bytes
# import 
p = 15697216611780965563
pol2(x) = 12023973299112282354847247311595151246059950849465485547761083151511373348323400539249511160*x^7 + 7827276000117772240603169279186631773459312835793913201750366028269292683313625178240610162*x^6 + 10800708287956322840772410643716054760075048515917772405947154907357520908462344713628534422*x^5 + 14451676860682350406257134424230649806106670133576506487079014541794347120063322120662083042*x^4 + 4128110086030624553163025712963598271434826216504612714797472907728136494806826882874482767*x^3 + 1703541058662269174571613670615320905587542708659883299753415183565032033473295760324994742*x^2 + 7000189347261314193584759857035153781039491479909082869050210631613808217099939789590533769*x + 382177513631940973013976289117577048197714132228530595454612103364274214085256641041729890036607378710673055646003757541145414603248673424579782863925079219529752138774551431306402346164927517694677083049940503420806360811931278017804023976111750083892292338604749286979020965304413958750136657385724632869149632155674563808310640985948855589624801498977526749711671821251108926582907329949821007021691996333564806599544398776037442637945995503770200916944234740758330037001338940530200889870404586370798388622200846130341211802936510184026957826690554952124099349760221072714445927944521585439046223790557668284724568882867131045932394966552102334251822659472233602290162515858535834326701102881801784355957015447831897981330269422668111274176555322369846811104175978302654602190936068832076301656372274375467328131527760655857740978030422057892677274629988474217174467567424007708551295701573705538887038827810794260386420420374955925486839427271997151137156049045384473447702134495482553080383258837811987952430315075790378813635476341639927629722743309986131474758156233339406833298484218871634933235471061879585822286139920353709724351868423708985248045649761040061544250618761731285998107197221451537540851413971092198037331064223982107423679464698108098890969441962443398617561162466621326993036533490727107422478050853567047999843409916577195918102652663501663591818818346746533927868199708067533408882068639456240894033434758591943626080483800894539471037424730464957793427471209040564839982178249800277962390521025977242928488385444409171005651575606798227205765188560831758884123019548278086765149000683500083400505149502353541881347570310673449252157657911045262547323439163961105410045993078467263448263872751803298659294897961773701828016236839805837893309071433904100598992913878208029042291610967332038779858037903854040370520693934755449412187698671837288834123644841266834387235352210102986988327049313
w = Integer(p)

# step 1: find roots of pol2 over Zp 
R.<x> = PolynomialRing(Zmod(p), implementation="NTL")
roots = [x[0] for x in R(pol2).monic().roots()]
print("roots: ", roots)

def p_adics_solver(root):
    global k, p, pol2
    F0 = pol2.diff(0)
    F1 = pol2.diff(1)
    r0 = Integer(root)
    f0r0 = F0(x=r0)
    f1r0 = F1(x=r0)
    print(f"Is {r0} one local solution? {Mod(f0r0, w) == 0 and Mod(f1r0, w) != 0}")

    # Get one new local solution from older one at each step of loop
    rk = r0
    wk = Integer(1)
    power = 100
    for i in range(power - 1):
        wk = w * wk
        f0rk = Integer(F0(x=rk)) ;# print 'F0(rk) = ', f0rk 
        f1rk = Integer(F1(x=rk)) ;# print 'F1(rk) = ', f1rk 

        # Most important part: 
        #  - f0rk / wk is "Integer" division, removing the w^k factor
        #  - negative (-), multiply and inverse_mod operation in ring R
        t = Integer(f0rk / wk) * inverse_mod(-f1rk,w)
        # print(t)
        rk = rk + Integer(t*wk)
        # print(rk)
        rk = Integer(Mod(rk, wk*w)) # ADDED MODULO
    return rk

results = []
for root in roots: 
    results.append(p_adics_solver(root))

for result in results: 
    # print(result)
    print(long_to_bytes(int(result)))