Solver of Google CTF 2019 Quals "reality" (solved after the competition)

solve.py

from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
import base64

E = 226611012014558802453288800032037813546
key = long_to_bytes(E)
IV = b'\x00' * 16
ciphertext = base64.b32decode("YQLAC5DCJR57PYVUBQ4PXMH47IO5IETPUI7EDFUR7JWTNIHNTEAA====")

print([AES.new(key, AES.MODE_CBC, IV=IV).decrypt(ciphertext)])

solve.sage

from sage.all import *
import itertools

# display matrix picture with 0 and X
# references: https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage
def matrix_overview(BB):
  for ii in range(BB.dimensions()[0]):
    a = ('%02d ' % ii)
    for jj in range(BB.dimensions()[1]):
      if BB[ii,jj] == 0:
        a += ' ' 
      elif BB[ii,jj] == 1:
        a += '1'
      else:
        a += 'X'
      if BB.dimensions()[0] < 60:
        a += ' '
    print a

RRo = RR
RR = RealField(4096)
### YQLAC5DCJR57PYVUBQ4PXMH47IO5IETPUI7EDFUR7JWTNIHNTEAA====
x1  = RR("1.1523683371067123349656382131317521483572497142298337343260320993424398216178709236539938709110452634807784715262138995755342817993685509357712770340229750497263666806472679182677446813307514752989998709851733038910120353481027193255623282195303273679305610332766192092795306395336470967297906833935279894252616095703554546236457175492266398641941143086328952666283556115648410157333967927769488481273065721795561095918412150012421542250430997607592179132116258276065709318979773496974099022073099502")
y1 = RR("785701515561796928936294283336388546237.76198513405518052745128365573717412032431857838308609736805706641397119523106356273567386950051527641654288830128296680222705035406388428925103738738880089143710871996591308092142413410462799119104211628940723436162204485785271731710389128475080795001712865906678930222773707391836436633044651508284465733937444061563710525469368853621204597936989528982407800283786961077055617880725523871857845636253399548919606316914163179078711224606329197843485595974741371")
x2 = RR("1.9788681780306785745156989575455836997628595976195551967457035744531437329843012720941996363829938236558497904581798051243772329161582321879360660717582006051876040760971474767304024929464189882580767726915416095996327004491382227802281015240630789402853666506660443130218440489869153208264839264361191403711079005451092879896580775565516043311227204323256062060636302634873383609155444647328923902763251787493352130750547736994397271532409511747826853294706030568422435743878427864639456394057079862")
y2 = RR("2800780348429075081385422902824585625983.9718926020338437020050029020823624261231050171252891745710847437841708047345973255413221720133608100491056729443460854596666227899379299259825534978829077355033242582097430638128055602755533412987750066891446221229772669000110400372735908811477249717115822683690394865669693744895646210678759522710089141476167873126736495304431404870994048252140031420103893970444269041047766479070093625398030832513319343802074702488746482787664792595305879288767850463661089")
x3 = RR("1.1670934471504288389286699040597145166483859406607818722290870762005830879563520820444583769798094486100304620471097338034767093997643829487907758687772023239707260734472162763033737562629817749955408516815773124364141649872257509424163110108092639724918657438264373626094282680210615254900773574389965613279176813046462954963793860609569983518700922195346251798337750431074023542866696934221388642181566976684008412054371564255018302161417018138623829465811427229918451188130718662890832098982222125")
y3 = RR("802707509246523948167720804790529379981.65200627237446296237041791338739143005671462858728927775450751967070365345683907995507470923968298285874283562502374335568470739347447815600897365404905225832360747786484781020758259038661605921813716501226097097691811131220851765551439580788138654797589031081162956293274990820524344279481532872541315373551218364140305887507030965924866440561850791854542913794394621606495561223518482006711916111610968280784647353332520349002673666762620118053665941771430482")

L = 10^200
L2 = 1
K = 1

x1, x2, x3 = map(lambda x: x.exact_rational(), [x1, x2, x3])
y1, y2, y3 = map(lambda x: x.exact_rational(), [y1, y2, y3])

xs = [x1, x2, x3]
ys = [y1, y2, y3]

# x1.denominator()
# x1.numerator()

M = []

for i in xrange(6):
  t = []
  t += [0] * i + [L2] + [0] * (5 - i)
  if i < 5:
    for j in xrange(3):
      t += [L*xs[j]^(4-i)]
    print "i: deg {}".format(4-i)
  elif i == 5:
    for j in xrange(3):
      t += [L*-ys[j]]
    print "i: y"
  M += [t]

print

M = Matrix(QQ, M) * K
matrix_overview(M)

print

B = M.LLL()

matrix_overview(B)

XX = var("x")

for x in B:
  x /= K
  a, b = x[:6], x[6:]
  x = vector(map(RR, list(a / L2) + list(b / L)))
  A, B, C, D, E, k = a
  if k == 1:
    print "Norm: {}".format(RR(x.norm()).str(no_sci=2, skip_zeroes=True).rstrip("."))
    print "(" + ', '.join(map(lambda t: t.str(no_sci=2, skip_zeroes=True).rstrip("."), x)) + ")"
    # f = A * XX^4 + B * XX^3 + C * XX^2 + D * XX^1 + E
    print E

solve_log

Mon Jun 24 10:52:33 JST 2019 ~/Downloads/googlectf/reality 100%
> time sage solve.sage
i: deg 4
i: deg 3
i: deg 2
i: deg 1
i: deg 0
i: y

00 1           X X X 
01   1         X X X 
02     1       X X X 
03       1     X X X 
04         1   X X X 
05           1 X X X 

00 X X X X X 1 X X X 
01 X X X X X X X X X 
02 X X X X X X X X X 
03 X X X X X X X X X 
04 X X X X X X X X X 
05 X X X X X X X X X 
Norm: 333887481774127793798922224558149580011.63595001716382370971829116832631473687062922275265785542610639226856094643032321076234889290918461420467327770445636850218633658431267673605245913997671393240075693432906662936191804867861263593932708228759595175685303346946312645609801669678531784199538208683333836972515260416050465791640379551457772474574808529277530863930290847867158915878205443896760421365570957366401798463622210212895194287735769295458858547407945768503158182204014430837483341578493446163734113151158394517660667574861425949731645476484203183033765451039340883068373508631938591576301332855913100050870148698560250665190428641853367064101651298263313104896777175995986770385493379039854656252723295060381854521422006456697788815641143225692287820562065980047092060293595349262030579211585383581196856191498227936619965599889405955910236683640575160632657060460391736954554102207048648694015718490522317538327407846269613310951448466433268194367600285261180408355232282214087239761910111097082818050394348715153690867755294686688589392373248760903340244370381130562549210242643189143050028459437919232768224859187620241489250685636703273011228520751688995240062433615722544258846886884961420192650045909678485204897613
(116425376680422759481302499800717965898, 8379539703713581435227054912547636586, 84635027784184601854329254241670042777, 198343456585670771838628393857796908615, 226611012014558802453288800032037813546, 1, -0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000065659757906960341368999558584202585540771311835659947059290973190927460114851424254625362541377736712055609609260999077836263764357726506351963544188544919261223266862292550541765415647493597051945911356763611256822250985035535452711319882525873311859772985192429343386338557795942972383027731241107778206354788458700724989165881464016254309041326702296731159623890358877238844497474284746707231426423742928093869598852425535128021359760360999645964497065673270992441736714329915844470158063189932233518905730827107084905695536900421880515715442206520303462928069526226268316687547240101166532614532218248089873577297952677871918613297282399354744626573954647309410285692073026320742325813940008663156908741394007678344211761560035407167523280885591844851281504276001135828798290402472410677060319368092029210957239636692522605625930382796321457260771385245404612602245791899928779295183702929421761417560764601032436559691320998356134146596107506734424852059116073713755218186319058384397191745367737246628711750986910955916666337175706679774384390549409003914351987122106412168308130601929483802668232446730796387945941558867191578742547705320018272334505809542483188568208351127825132070717486955225689901309832172721971900848049, -0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000040580301128057139810397447968363453487006104981098920014203927091859901674006145723279804739311031257725892488631557343384562381718285474357937189096429283077485839605254047004656299720481588781014594657177681888647326494351628453467496574598950966181761698186105211577732610322906121637381271365317620113265379875607252451348895727164426864325825501985467425492424968146828808713663768393287725186568796821560249203711514025104204766548725268413260522706421271537796690232571229340052655738788557159028227061555789257829906712597041137883212162906832083949858588000877327491194155979869204413091385245618990724900953477392983809108484130328668762924111319748602222428539569073609923875355152779126882968785322954902650730955147269526903712866850165682783862343153336286630229413635444834305468253283953312155189202554694211059205077629944155228123390319193972672059412396324314643323966611539253013786910866538378872950701917988004517558070175811023027129881870616081090483592777858709669371042790868676054533024742576714656448303920453043388426987852959155597478997472268394815302766618968382693063273612892469463392177642225787357853906509985667504458928310600683464289075481981886213211970730197007340042774185010880423310079935, -0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000037239107671593695783646755485808349739510052148647181606025681524233485438526920762408549586505558406975461161811327839435092074028927995694262537910077239310662163030537251118757783141306299728883463743746496974270651981218772981481677618889648657262541990986870680382470965458610891987870939081460111672882571583875326444028160933720935217367608677213945509007416951953752374552053899699546971677757115811600264476005561690034372268433070008724643296014830562672251271550268889883086452203299763391376528092225796683092096847994096360799862217777234901444691175556010520962493393312314729982739436647256318105420412006732262963690772091194811132790399930683228395411794386434057573246356110291406494341818991730194811091113273101732826584180768919443102407277649510952066485698712131188716692130036354590496131353833730228146392494195200571307129744814310799393567596961130719287177630654911484350991944534946889594074666927703512828187302871064224780158133419744516214938102904563936417893687378412899347330751512127598975721636798332359321107347895009634982291258990525969034622626907125634112857469890015351082088754081925088249779552301127933870415055889517760439318011154321492054861146774674736013558130088850865396180162368)
226611012014558802453288800032037813546

real    0m1.332s
user    0m1.108s
sys     0m0.199s
Mon Jun 24 10:52:39 JST 2019 ~/Downloads/googlectf/reality 100%
> time python solve.py 
[b'CTF{h0w-r3al-is-y0ur-Re4l-4Real}']

real    0m0.094s
user    0m0.083s
sys     0m0.017s

Writeup: https://elliptic-shiho.github.io/ctf-writeups/#!ctf/2019/Google%20CTF/cr279-reality/README.md