Challenge:

from Crypto.Util.number import getPrime, bytes_to_long
from random import getrandbits
from decimal import Decimal, getcontext
from secret import FLAG

N = 3
MSIZE = 64
PSIZE = 128

getcontext().prec = 2024

def chunk(inp: bytes, n: int) -> list[bytes]:
    return [inp[i:i + n] for i in range(0, len(inp), n)]

def generate() -> list[int]:
    return sorted(getPrime(PSIZE) for _ in range(N))

def otp(data: int) -> list[int]:
    key = [getrandbits(MSIZE) for _ in range(N - 1)]

    # Apply multiple times for extra security! ;)
    for k in key:
        data ^= k

    return key + [data]

def enc(data: int, key: list[int]) -> Decimal:
    return sum(a * Decimal(p).sqrt() for a, p in zip(otp(data), key))

def encrypt(plaintext: bytes, key: list[int]) -> Decimal:
    out = []
    for pt in chunk(plaintext, MSIZE // 8):
        out.append(enc(bytes_to_long(pt), key))

    return out

def main() -> None:
    key = generate()
    ct = encrypt(FLAG, key)

    print(ct)

if __name__ == "__main__":
    main()



[Decimal('613865483278018068252699664344014709603.51690674693116605142775061636120046870769083140402021865687508441855022441399605307934286489840179576316516207824661811160477759304066064291205730622145206447227404607082151753919361349868545307462428210932437992623119255718054243534096986413211959304171135887211540587436459888779324151143025499619973135708235491605216411394962317959813656209629567607308778163987166821943423002154894970121188451784354115735408809579052563235078363998602200794840158081619720701643652284259066561050115602486569569690456649269369511972329349611423116985630502303784458447333880791258687570760036481989066910025496948546865951981177430643941260666483918647746947170525925083317666875914436471646901318749705595856856883346891726769074746650987330068104292614480104709810601198864073890537548001433033723615776224146304045036932985711688197452123005099236554526727107165691391180111605054039864164377438525310672107170437281478322426514683178129245151967154583110424925964982504343607726182942419964058684010006450471850408468724523024702559055514056791838218373955386876710426728739081458827252802226359687030921900842002785720726229892098824084346436742345912593840934579190526250607721076769764172513184565791506300616867803697312829413891917781663107526096475492046133891964020871514785931302212911910422061349227840920633130097807344731335384126657969326959305179863489255473137828869343169464391631468853227921632272791516165605848151467308601405844760824881338357444888188035204000407673339331919346899410420054651077086850532999310419256243385542853597931278472451318309939063364567112084455650629429599265528219435289213175349567467961574398181095962343974433190931067322110878499680729907288265465620467270493396020598011075090015918395921964211257921275263305336676548841001128867189130080538627211844161021733430009452985356108168888790283056201446152044771750329866340679923824523137794621308627512829896733426062792367679307468573465298446962647695970868442917945963296248995830871462803'), Decimal('245036407881857959287329830175942706463.41676802782442994887934627742200369945701412601647195354905097451178257098540606801565385675107318120460650888047274089786443222032370562593772359240722830861471549006005870906901656856743873456596259047367300567575908527230366385292440919562964298317812232800102576149495809413427952810634193186781922614214268017709482845572771078220390794231892763512491653218636267112852524278614145782738125962122310806946368712582799445479001874840170209715004731276988049273955290890839588161009103614134479683822558461311134193156291806539774288015592213012944114677791107334704048050248067790961044976635609645113466054839476916586971455181287563116833537875679872852426596500045916084590678852453213603747411621009244578584574321606967288315507350789499360210767971560504476491167021056575773203913674206412928683729647182751865762672106362511792516860263344700590671316013798899626125150168033775577935989491544189330151349377248071416776567110915867894841003988715963213282301539772548019203054604324657682585086974883293993693364621477765424253486620846417121914627069652179323747638053294808478946841684842391124370675090921956558456987438962361101647423473932215595029566302891192438202103166531605890363352381011015329475002801933772777494625189852526005526409489415563470356698119177369784245367090617016832725703245455210343971981483284742666226075984764682029024194412093587469973865623264825887838718407665448451327538641035583414835042280186524871430174844859199371418365330179156143049238655596474961217964906635309020982967098088279871772621354935094165104148277851308675528401723829872589324051699054275878133606165491429811386740566384976019587172015296076695877847670182335353621529186538640618471230538158759335554894682026973199860563823746052413212330496106907455577991532192244914548792485371507973770044500533179391911148716837049004674981572325374669719464763272448641196278444851808838959425053174592256179039838611577554410785172685506776747109456418706054407235309341'), Decimal('137345167246666152708695783992412451677.21558050568623481295196376367975242130555102201515580316330966697148890411534221923225952905285897183010922406175094262069208074739275097805536185634560982617648832780575658021059502299936366800046975825224832714908010519763833830348421655509168881358855533351044140363192436142763626456404652383592376546952793513967937938636543810723145564947948780573116974908526774605955951469943187865644596524139107481653386681950240101520692953876806620084423038367388560905871875836530739404184303742718262418117805718036122357051928716596276399762849629107495322882675719409051073299089695124393278836941013272789785477953131515760862594743832917404252472431732912434480355250761546326425334589230931109133966112698705631064298540629644087174339495451233415165784208154862632994746999100506080852291240231466075807689137982406781289386109243195384399444517321654449447540787541127685794368775611662723601685545144635953407926414192981817325925467123186823453700610674338813375219959042008201960857405988222431762449068615565770592161380029925528004633925411749903272512805896758350376028759094075163759541252996218647962921737695225607000672827355712319484834139082006323871120783473891599300315829557138141744616522321981481762618665822002496867084381222827633659627360022043393386819320488647893458122132426243653269827396864109912568570075611460793016682214280860824555257535036669613199445516497725227349649115460430628789851678786053832488469704975290639037623666238775508475503615248256142687325810589424170821237702234472583990907852983428072024771329547328770035145579513303770469872758505372515800860236159229593770017270383301142993264982903473737872532789578999358701823743117676045641159467315897055924399632998579024195194906804156820621748747515175782908138772828776041903750590418332731770693214602115172315637279313855936478443754676804416808777432960976763034716998360016818363826448918529745873789717604991019505220078545941396511331142324037841720139678985890298577830351331'), Decimal('248598813941244564314190366976956238846.21287154177193010973910605580779261210365984174749796180419923931211513873961571752231238459134695223104083276961569452018392982079324317136535206452261881826873414602629594471707660157457896214988591398626491707261264840694400878016171848489165321633160306766022332706508213328119352706170273262931280561423851178335709726505935522918272264480451898981178517451201483151591554008657960692345350455891365321593940275460890295306738282405071381298895783171740603832308867778448785711118127825021180253182388515151158156028351993831870085534975634188825697876813579914222802552156594566015228528827397850794636185597567790199750813063356917626291927109597628605896564415404785475255907843090500284371578116809505806089285850503289523274957689703557226650819188753255887580294403919233020671057076485044952433816771965385673494711771474126428651980119604119559562596188714862777544919355156232243652718517709528203262205358442941280815388198987743628689516005444663613668047007886122931571139930784688640045996582570962554713967405406762001906063378302125401898155550603489814135391137430186059041384496922239998747587303366147421038091369722510204804734395780572006815615350115111367222110517089689188974108653902029376056551397900019653419884380778042660817204485470749571339982927039079734483080043934563757326484950182811230031559346385457298240850154178951900739178353564235216322232791700369486112525607172179782914690610012323349746725297341069764127541218762893367556754429312136345943483494236203659704464226488931565438262759788872114208783818792121079840366002113316654063450919686404664767226446116187197107156555434824485171863955895656710114494285915504850382199832564322800850387423097212704670656698969249945269974571051395109564672354772654744585684053379753599154369914818372119637829894516195738013893515476266773802929361065238109305019468285763072333229080155510459572404321239788374283507107268753407976278020430629150787678790300001623259645896920037795093793915002')]


Solve:

We essentially have the following system of equations:

o1 = x1 *p1 + x2 *p2 + x3 *p3
o2 = x4 *p1 + x5 *p2 + x6 *p3
o3 = x7 *p1 + x8 *p2 + x9 *p3
o4 = x10*p1 + x11*p2 + x12*p3

There is some resemblance to the Nguyen-Stern algorithm except over integers, or also this chall.

Let’s do a test:

x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, p1, p2, p3 = [randint(0, 2**64) for _ in range(15)]

o1 = x1 *p1 + x2 *p2 + x3 *p3
o2 = x4 *p1 + x5 *p2 + x6 *p3
o3 = x7 *p1 + x8 *p2 + x9 *p3
o4 = x10*p1 + x11*p2 + x12*p3


Small combination:

M = Matrix([
    [o1, 1, 0, 0, 0],
    [o2, 0, 1, 0, 0],
    [o3, 0, 0, 1, 0],
    [o4, 0, 0, 0, 1]
])
W = diagonal_matrix([2**1000, 1, 1, 1, 1])
u1, u2, u3, u4 = ((M*W).LLL() / W)[0][1:] 
assert u1*o1 + u2*o2 + u3*o3 + u4*o4 == 0


However… now let’s test with some irrational p’s:

from decimal import Decimal, getcontext
getcontext().prec = int(2024)

x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12 = [randint(0, 2**64) for _ in range(12)]
p1, p2, p3 = [Decimal(int(random_prime(2**128))).sqrt() for _ in range(3)]
#print(x1, x2, x3)
#print(x4, x5, x6)
#print(x7, x8, x9)
#print(x10, x11, x12)


R = RealField(10_000)
o1 = R(x1 *p1 + x2 *p2 + x3 *p3)
o2 = R(x4 *p1 + x5 *p2 + x6 *p3)
o3 = R(x7 *p1 + x8 *p2 + x9 *p3)
o4 = R(x10*p1 + x11*p2 + x12*p3)

M = Matrix(QQ, [
    [o1, 1, 0, 0, 0],
    [o2, 0, 1, 0, 0],
    [o3, 0, 0, 1, 0],
    [o4, 0, 0, 0, 1]
])
W = diagonal_matrix([2**1000, 1, 1, 1, 1])
u1, u2, u3, u4 = ((M*W).LLL() / W)[0][1:] 
print(u1*o1 + u2*o2 + u3*o3 + u4*o4 == 0)

print(u1*x1 + u2*x4 + u3*x7 + u4*x10 == 0)
print(u1*x2 + u2*x5 + u3*x8 + u4*x11 == 0)
print(u1*x3 + u2*x6 + u3*x9 + u4*x12 == 0)

False
True
True
True

You can see that, introducing the irrational p’s means

that u1*o1 + u2*o2 + u3*o3 + u4*o4 == 0 has no integer combination, and LLL instead finds us integer combinations of

u1*x1 + u2*x4 + u3*x7 + u4*x10 == 0
u1*x2 + u2*x5 + u3*x8 + u4*x11 == 0
u1*x3 + u2*x6 + u3*x9 + u4*x12 == 0

which is more useful for us in this chall :)

It’s quite interesting… the first time I’ve seen LLL be used like this.

Now we can just solve u1*? + u2*? + u3*? + u4*? == 0 to find all the x’s.

To get more solutions we can use LLL enumeration.

from decimal import Decimal, getcontext
getcontext().prec = int(2024)

x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12 = [randint(0, 2**64) for _ in range(12)]
p1, p2, p3 = [Decimal(int(random_prime(2**128))).sqrt() for _ in range(3)]

R = RealField(10_000)
o1 = R(x1 *p1 + x2 *p2 + x3 *p3)
o2 = R(x4 *p1 + x5 *p2 + x6 *p3)
o3 = R(x7 *p1 + x8 *p2 + x9 *p3)
o4 = R(x10*p1 + x11*p2 + x12*p3)

M = Matrix(QQ, [
    [o1, 1, 0, 0, 0],
    [o2, 0, 1, 0, 0],
    [o3, 0, 0, 1, 0],
    [o4, 0, 0, 0, 1]
])
W = diagonal_matrix([2**1000, 1, 1, 1, 1])
u1, u2, u3, u4 = ((M*W).LLL() / W)[0][1:] 

def lattice_enumeration(M, W, bound, enum):
    from itertools import product
    from tqdm import tqdm
    M = (M*W).LLL() / W
    for coord in tqdm(product(range(-enum, enum), repeat=M.nrows())):
        v = vector(ZZ, coord) * M
        if all([abs(i)<bound for i in v]):
            yield v

M = Matrix(ZZ, [
    [u1, 1, 0, 0, 0],
    [u2, 0, 1, 0, 0],
    [u3, 0, 0, 1, 0],
    [u4, 0, 0, 0, 1]
])
W = diagonal_matrix([2**1000, 1, 1, 1, 1])

poss_sols = []
for row in lattice_enumeration(M, W, bound=2**64, enum=6):
    if row[0] == 0:
        poss_sols.append(row[1:])

sol1 = vector([x1, x4, x7, x10])
sol2 = vector([x2, x5, x8, x11])
sol3 = vector([x3, x6, x9, x12])
print(sol1 in poss_sols or -sol1 in poss_sols)
print(sol2 in poss_sols or -sol2 in poss_sols)
print(sol3 in poss_sols or -sol3 in poss_sols)

True
True
True