IJCTF | MSB - crypto-writeup-public

#!/usr/bin/sage
from sage.all import random_prime
from Crypto.Util.number import *

flag = "CENSORED!!!"
m = bytes_to_long(flag)
e = 65537
ROUND = 4

p_0 = Integer(getPrime(2048))
print "p_0 = ", p_0
print "p_0.nbits() =", p_0.nbits()
# p_0.nbits() = 2048

for i in range(ROUND):
    p = random_prime(p_0 + 2 ** 669, False, p_0)
    q = random_prime(2 ** 1024, False, 2 ** 1023)
    n = p * q
    c = pow(m, e, n)
    print((e, n, c))

# (65537, 2973274209501776201691519888042319471199570472002963581448442038174303775105245314381574957363420798823459109272033582880093544342097416632789301922536002306527567182062581755622427896176805222031127741901295996406407655159580761870799686589902586048531977772470949726487847609592273113113509360393565486981495691414280115488377036658862455270185918144232474278411028478744709705654418813265142448659819518373755286746077156428562009550423949053466765672350304371480685305236056948120315511581481937808877476017304234481709539887420959566635934196020993167440107233603930680205275988663922482219038154002189670456657490447904915677803635085896488516276652038398387670281017889578744546845516879561935267220220496067322815871953476187719320544305216370338724577613427031660334003670927940108336778128777129814482506102904120782261936405200583575045525662493621014910391546113422892875342648897533678582176837917306298616481373, 1916345795411046972738375754819683681926423961399114792801269957801977163440602821055072484406992244815036855918088798499938879791907505191972460922704580149221312157070181525428881682778778310135284898956613383004949065300186549316143621436988329137694532615825599098702201181789276122598515513994795338977977995789035323656172979381490017651005294884962515131736627554492930527900022854579639316928920418329929263046559349572706217880922083227295928053260088769281560143630321922294473582768062401570120887222514628086875048086383584075269304995537313637821427082672614650052048489417189826582021790156211244215713287597531449357470185779377001362125826126061066645860764220869216915972902761526341461419527244572704333420781898107551051196349501951094294927899571823039077487599286047323754104166237131284435653841620198169983977387345450646656267145362264437160529566744868352738337614347580596445231221837741213899194343)
# (65537, 3251902782032245789047244373568418513398699501042390125582854604850409980025770075450715911787445447521622218140215334557095399706072352867343808784990523236458770502408745674483759470273023405191394278952651887691658796200123075893310880484047881686981490079465719251437675137685366637455718736167852758693446054836510298483278836803321808484256895651671009286866206609106195207341954297584749240651733183589964137622276798390574442735236357896976689865537006076691770565982325476739464122514349746931384285281663137634844542581653666782790132692715898744258444677647182810520302200972112293388358388223088570201049829327536931873736003576119203091174357031887835756398363014044213876462726121357257124857714844995939275360401292114685493742117741807725904271233047819844418317309151563996814147674222205025657406854179970261054167763553714096062720190375110424034962653825267605345186966196242170924880263420113533093715233, 2645105824316761856124611403529474032897871399099086739785911359639324649626203162885283567586022229861301735006440596348053983575953324837669531268307236650876788658742634018986121195360525078585951680722653955109490765803142278516842919967774058241575867037360155509753525871368490216345612777138271085151680565738347241852968378151128155252723519489832135758176714879839498202356305063958146872126315274549080519237066575231741658093231788555026645342223200956846897402350699153724073886155363115019558535701761185775754760703163263101758115464361290468916490533144001847751718653814236067866679823003882144107463800665057941738902543788190538270759171905715286265872339501553383466521258775375934479156016133247473991683928096526535802235568785344321662091218052479088650747090003721541102251528357299792976274068429901594666322831281875867032130376202846886741330595638742261098701069282133593876198771110138810629014048)
# (65537, 3319581693166965854156546341702871085866516484417065133102957669783301767124305139148241445171965157251584901630940509466918383746093571883915961138469590579904855662075039603814193052482648861790005837152499623628933003722223942748425087238428768644059616855971746263587030015997518015844693570238168960001236591860478015490454825814441652717357954231754190147707664516755381474477091485840498429348559495172163679635558297040958809235154959039890002943586754687708419307944576976342602536633100445400214666233092453616500867884214942494273581939754962360296519390972480570607826327574222675233233204129014053970935585649161741415313714333739158739575683840949478335750767497914631684789124737756077755619214595149000678108003092984694154462094053762230044505613861154667951960453842346217765321466714384322427236290201201749533875696605496322060048560493782437879730028566779588369102443815552624843364723864437585102785841, 2943451957210492298496885223197100961845212671896602031550943800350428428123174494669323188832875449943547361144896991502861406116064231597068700557777295261541156809725117754190651940361398157964771934671024702595572108218896423235737211714711312713846025368403347585637081443069105434308848984548422943795568577176237177385420571933766958405703918471946014551997933749740379394808464940723379105448176765471045306779331131976331555629517414945551330514298384538582478282882886878656891788871327430466906699709381899210876610915746530638043565491444399479489008191974508924613673497978184489338997566380461405141200374868605220263648935812821167995643466498900400945995664432964793684941691096800450324029693106531076749593907564059344853798368146133652110394433813783639369276334464054680367005405580121802175949167469507213842588923766711774822306696268733825271037343939987496588240504866624971179860083343793998700244102)
# (65537, 3623027672825570027751905799087856250704364673219621733695608778498876374831468190295671406108813898622110856070362351202666715910157337713651450563139743656276618574488571861325300807768638051262028939850502191925048933459640263459899860587432858065361150546224650437409072567077419033994230255886523594885378258120983525249076049297579507914373981430056882696563001548545648806920587530226042146743848583834214566739577582905827450902524112644006302123901273189894141533305574615678484147600815608055941349174922284976582534946728583640560253903585715415485123700103842858923437775229668552580692343997833070023359560455050458268772296895514484239824212138823140238571743690643212480973800020565951870579891389546329093851128538448181474331412847283334553031842616446827659687270890242373017860663315628129723352199179773131554695072711474852201115894168202572204470148970446464032655855883263323237191326685502550928150611, 94839190735195981419390998576998479069048095156505276922707357120624200650556381825510515647294881460171680780289141443080976487647081044557036343721158654087135177976323578915000677785092996378127465455666202819840737713948438469972972920830867277953150770191586729208540222514171662995897725951268468447486687845425719169883467402267251938604360707451533643487152015550139958014451023302275855514680596474831108019277653091993514694277190609850063014988800034387469548670718900241551737161094481627181586669063127806555738281879742151138194035542674733125969172408024196269602502719514755543101406558012244788034245904399393539438138331897168560503726258345731177616080055166114081199471797706933780780147130267681791934219272182878562081998958968931952256775498302670036421087525087104533437058176733702916578897021290734236950105361760026362464093540283552476672440563085580956149222859054705438153201634114339732503863)

2048bitの $p_0$ を作っておいて

$n_1 = p_1 * q_1$ から $n_4 = p_4 * q_4$ まであり、 $p_i = p_0 + \alpha_i$ で $\alpha_i$ は670bitくらい

これは tetctf 2020 | commonfactorとほとんど同じ。Approximate GCD Problemとしてそのままとける

from sage.all import *
from Crypto.Util.number import *
C1 = 1916345795411046972738375754819683681926423961399114792801269957801977163440602821055072484406992244815036855918088798499938879791907505191972460922704580149221312157070181525428881682778778310135284898956613383004949065300186549316143621436988329137694532615825599098702201181789276122598515513994795338977977995789035323656172979381490017651005294884962515131736627554492930527900022854579639316928920418329929263046559349572706217880922083227295928053260088769281560143630321922294473582768062401570120887222514628086875048086383584075269304995537313637821427082672614650052048489417189826582021790156211244215713287597531449357470185779377001362125826126061066645860764220869216915972902761526341461419527244572704333420781898107551051196349501951094294927899571823039077487599286047323754104166237131284435653841620198169983977387345450646656267145362264437160529566744868352738337614347580596445231221837741213899194343
N1 =  2973274209501776201691519888042319471199570472002963581448442038174303775105245314381574957363420798823459109272033582880093544342097416632789301922536002306527567182062581755622427896176805222031127741901295996406407655159580761870799686589902586048531977772470949726487847609592273113113509360393565486981495691414280115488377036658862455270185918144232474278411028478744709705654418813265142448659819518373755286746077156428562009550423949053466765672350304371480685305236056948120315511581481937808877476017304234481709539887420959566635934196020993167440107233603930680205275988663922482219038154002189670456657490447904915677803635085896488516276652038398387670281017889578744546845516879561935267220220496067322815871953476187719320544305216370338724577613427031660334003670927940108336778128777129814482506102904120782261936405200583575045525662493621014910391546113422892875342648897533678582176837917306298616481373
N2 =  3251902782032245789047244373568418513398699501042390125582854604850409980025770075450715911787445447521622218140215334557095399706072352867343808784990523236458770502408745674483759470273023405191394278952651887691658796200123075893310880484047881686981490079465719251437675137685366637455718736167852758693446054836510298483278836803321808484256895651671009286866206609106195207341954297584749240651733183589964137622276798390574442735236357896976689865537006076691770565982325476739464122514349746931384285281663137634844542581653666782790132692715898744258444677647182810520302200972112293388358388223088570201049829327536931873736003576119203091174357031887835756398363014044213876462726121357257124857714844995939275360401292114685493742117741807725904271233047819844418317309151563996814147674222205025657406854179970261054167763553714096062720190375110424034962653825267605345186966196242170924880263420113533093715233
N3 =  3319581693166965854156546341702871085866516484417065133102957669783301767124305139148241445171965157251584901630940509466918383746093571883915961138469590579904855662075039603814193052482648861790005837152499623628933003722223942748425087238428768644059616855971746263587030015997518015844693570238168960001236591860478015490454825814441652717357954231754190147707664516755381474477091485840498429348559495172163679635558297040958809235154959039890002943586754687708419307944576976342602536633100445400214666233092453616500867884214942494273581939754962360296519390972480570607826327574222675233233204129014053970935585649161741415313714333739158739575683840949478335750767497914631684789124737756077755619214595149000678108003092984694154462094053762230044505613861154667951960453842346217765321466714384322427236290201201749533875696605496322060048560493782437879730028566779588369102443815552624843364723864437585102785841
N4 =  3623027672825570027751905799087856250704364673219621733695608778498876374831468190295671406108813898622110856070362351202666715910157337713651450563139743656276618574488571861325300807768638051262028939850502191925048933459640263459899860587432858065361150546224650437409072567077419033994230255886523594885378258120983525249076049297579507914373981430056882696563001548545648806920587530226042146743848583834214566739577582905827450902524112644006302123901273189894141533305574615678484147600815608055941349174922284976582534946728583640560253903585715415485123700103842858923437775229668552580692343997833070023359560455050458268772296895514484239824212138823140238571743690643212480973800020565951870579891389546329093851128538448181474331412847283334553031842616446827659687270890242373017860663315628129723352199179773131554695072711474852201115894168202572204470148970446464032655855883263323237191326685502550928150611
K = 2**1693
M = [
    [K, 0, 0, 0, N2, N3, N4, 0, 0, 0],
    [0, K, 0, 0, -N1, 0, 0, N3, N4, 0],
    [0, 0, K, 0, 0, -N1, 0, -N2, 0, N4],
    [0, 0, 0, K, 0, 0, -N1, 0, -N2, -N3],
]
M = Matrix(ZZ, M)
for line in M:
    print([x.nbits() for x in line])
M = M.LLL()
print("----")
for line in M:
    print([x.nbits() for x in line])
q1 = abs(M[0][0] // K)
print(N1 % q1)
p1 = N1 // q1
e = 65537
d = inverse(e, int((q1-1)*(p1-1)))
m = pow(C1, d, N1)
print(long_to_bytes(m))