Challenge files

Challenge

from morfarshatt import flagga

g = lambda k: random_prime(2^k) * random_prime(2^k)
r = lambda m: randint(1, m)

n1 = g(512)
n2 = g(512)
n3 = g(512)

m = min(n1, n2, n3)
a, b = r(m), r(m)
c, d = r(m), r(m)

x = int.from_bytes(flagga, byteorder='big')
assert(x < m)

c1 = pow(x, 3, n1)
c2 = pow(a*x + b, 3, n2)
c3 = pow(c*x + d, 3, n3)

print(f'n1, n2, n3 = {n1}, {n2}, {n3}')
print(f'a, b, c, d = {a}, {b}, {c}, {d}')
print(f'c1, c2, c3 = {c1}, {c2}, {c3}')
print(f'{len(flagga)}')

Output:

n1, n2, n3 = 1401319611347356773887154859254297488587748916167528411781955161070771235056492239930915055430725842906735678800721088435590827145380843922331596331217195998289782451691023636938672246577057750538399961569425132775422780215874173061239620286809361247476788799084351705535705191719741473638161177830819062913, 93929270671640676038272300621577590050388546365573376058848268755586443513273392470288465422034947305882115935273812814090585070611845743805708732148965001758685938419891262987151989750411904643337379571106949332912476594370786031126592832074202606178259666176275819642895388993805423801590346121886463154493, 16942255048162971761210283484837728649885892177575028340105590631533021846865838703837850496337964481215216748513001294835312645433010478899804925326573174869703026494395537885248285153728354458825455324651596388723156984568435202926704664556435326575519823264262426064534649720827701655074670423046369428487
a, b, c, d = 816707757334025955873551300291115957244929178359163189898836703794096446035376642681339350269646402403623381300867313940921411937931855866555460115147443198624007849492344102900953388236705014598317668063410070421658320251867938311242756954445599777691127340178194758168120083391846957297043258538971682656, 745711826496100756612627309746963018286384869064570930929420181315701128858481411996420808944706255787336734726114648250308181091719587312246849339268467320198235168275114019618372903191004050047010404038580467357659473336645389978388162270444112395481987515683470136265832310695565656316066649488457251542, 457113559991336310217047954994454259015470269139045253465880453115425882867168371751366860291496286988706829825972982124718895516194348207894013000632929345548822790821065845244320278540909961203024618547366059145546677151699090715138478903903713059476077714630963005563020709732576278095273999695170245879, 509199941399276795750649828994710794297214191656907620132065560140027602600782775401578085170024829709169889862887726457343903644876293675737086407127920668618215833854745693576935098817794913606783358855099827179163328860990718950946614721022541431359002875691363746468433769282630310194268851308235950929
c1, c2, c3 = 1268196573919981524276949967801999986488529166073152640081117541596594438854836034605091034310174116029963325447867011142758840266458010604314712206281207486042576686131112279236592688360682514879866358817285786950878940051455988959409256539680442525853200118747541970284236278058810272505720905257745240883, 64208823083728071837064999419452205104115247850043866522128501646834783777966548620165452087334309723488367313973950057214802570403789761738914272552005923211386317615619928040804318066050436314100228196466534901781541660761105159754722013559344265999734902281442779083683166805632208178603445218079969320285, 8509227949500504626057408247321015695521219754070289890807066036172664538036554468734653260395519871677018843271256389298835987869898579912928540836245194980365843079281083074016559389213798536654944263567871852040147199080662496995097561192482940890984303786845410433468150776276754709196911737317257395314
127


Solve


m is encrypted 3 times:

\(c_1\) = \(m^3 \ \ \ \ \ \ \ \ \ \ \ \ \ \ (mod \ n_1)\)
\(c_2\) = \((am + b)^3 \ \ (mod \ n_2)\)
\(c_3\) = \((cm + d)^3 \ \ (mod \ n_3)\)

We can use the flag format (k), splitting m into k and x.
len(m) = 127 and len(k) = 8, so len(x) = 127-8 = 119.

k = bytes_to_long(b'SECFEST{')
m = k * 2**(8*119) + x


Now we need to solve for x. First we must use CRT to combine the three functions:

Z1 = crt([1, 0, 0], [n1, n2, n3]) 
Z2 = crt([0, 1, 0], [n1, n2, n3]) 
Z3 = crt([0, 0, 1], [n1, n2, n3]) 

PR.<x> = PolynomialRing(Zmod(n1 * n2 * n3))

f1 = m**3 - c1
f2 = (a*m+b)**3 - c2
f3 = (c*m+d)**3 - c3
f = f1*Z1 + f2*Z2 + f3*Z3


Now we can use small_roots on f. The maximum value x could be is \(2^{8 \cdot 119}\).
The default calculation for m timed out so I decreased it.

from Crypto.Util.number import *

def small_roots(f, X, beta=1.0, m=None):
    N = f.parent().characteristic()
    delta = f.degree()
    if m is None:
        epsilon = RR(beta^2/f.degree() - log(2*X, N))
        m = max(beta**2/(delta * epsilon), 7*beta/delta).ceil()
    t = int((delta*m*(1/beta - 1)).floor())
    print(f"m = {m}")
    
    f = f.monic().change_ring(ZZ)
    P,(x,) = f.parent().objgens()
    g  = [x**j * N**(m-i) * f**i for i in range(m) for j in range(delta)]
    g.extend([x**i * f**m for i in range(t)]) 
    B = Matrix(ZZ, len(g), delta*m + max(delta,t))

    for i in range(B.nrows()):
        for j in range(g[i].degree()+1):
            B[i,j] = g[i][j]*X**j

    B =  B.LLL()
    f = sum([ZZ(B[0,i]//X**i)*x**i for i in range(B.ncols())])
    roots = set([f.base_ring()(r) for r,m in f.roots() if abs(r) <= X])
    return [root for root in roots if N.gcd(ZZ(f(root))) >= N**beta]


n1, n2, n3 = 1401319611347356773887154859254297488587748916167528411781955161070771235056492239930915055430725842906735678800721088435590827145380843922331596331217195998289782451691023636938672246577057750538399961569425132775422780215874173061239620286809361247476788799084351705535705191719741473638161177830819062913, 93929270671640676038272300621577590050388546365573376058848268755586443513273392470288465422034947305882115935273812814090585070611845743805708732148965001758685938419891262987151989750411904643337379571106949332912476594370786031126592832074202606178259666176275819642895388993805423801590346121886463154493, 16942255048162971761210283484837728649885892177575028340105590631533021846865838703837850496337964481215216748513001294835312645433010478899804925326573174869703026494395537885248285153728354458825455324651596388723156984568435202926704664556435326575519823264262426064534649720827701655074670423046369428487
a, b, c, d = 816707757334025955873551300291115957244929178359163189898836703794096446035376642681339350269646402403623381300867313940921411937931855866555460115147443198624007849492344102900953388236705014598317668063410070421658320251867938311242756954445599777691127340178194758168120083391846957297043258538971682656, 745711826496100756612627309746963018286384869064570930929420181315701128858481411996420808944706255787336734726114648250308181091719587312246849339268467320198235168275114019618372903191004050047010404038580467357659473336645389978388162270444112395481987515683470136265832310695565656316066649488457251542, 457113559991336310217047954994454259015470269139045253465880453115425882867168371751366860291496286988706829825972982124718895516194348207894013000632929345548822790821065845244320278540909961203024618547366059145546677151699090715138478903903713059476077714630963005563020709732576278095273999695170245879, 509199941399276795750649828994710794297214191656907620132065560140027602600782775401578085170024829709169889862887726457343903644876293675737086407127920668618215833854745693576935098817794913606783358855099827179163328860990718950946614721022541431359002875691363746468433769282630310194268851308235950929
c1, c2, c3 = 1268196573919981524276949967801999986488529166073152640081117541596594438854836034605091034310174116029963325447867011142758840266458010604314712206281207486042576686131112279236592688360682514879866358817285786950878940051455988959409256539680442525853200118747541970284236278058810272505720905257745240883, 64208823083728071837064999419452205104115247850043866522128501646834783777966548620165452087334309723488367313973950057214802570403789761738914272552005923211386317615619928040804318066050436314100228196466534901781541660761105159754722013559344265999734902281442779083683166805632208178603445218079969320285, 8509227949500504626057408247321015695521219754070289890807066036172664538036554468734653260395519871677018843271256389298835987869898579912928540836245194980365843079281083074016559389213798536654944263567871852040147199080662496995097561192482940890984303786845410433468150776276754709196911737317257395314

Z1 = crt([1, 0, 0], [n1, n2, n3]) 
Z2 = crt([0, 1, 0], [n1, n2, n3]) 
Z3 = crt([0, 0, 1], [n1, n2, n3]) 

PR.<x> = PolynomialRing(Zmod(n1 * n2 * n3))

k = bytes_to_long(b'SECFEST{')
m = k * 2**(8*119) + x

f1 = m**3 - c1
f2 = (a*m+b)**3 - c2
f3 = (c*m+d)**3 - c3
f = f1*Z1 + f2*Z2 + f3*Z3

m = small_roots(f, X=2**(8*119), m=11)[0]
print(b'SECFEST{' + long_to_bytes(int(m)))
#SECFEST{0xlol}