CISCN 2021华南 matryoshka

题目

from os import urandom
from Crypto.Util.number import *
from secret import flag

KEY_SIZE = 1024

def genkey(size, t):
    assert 0 < t < 4
    p = getPrime(size)
    q = getPrime(size)
    N = p * q
    e = 0x10001
    d = inverse(e, (p - 1) * (q - 1))
    if t == 1:
        hint = (pow(2020 * p + q, 114514, N), pow(2021 * p + 1919810, q, N))
    elif t == 2:
        hint = (pow(2020 * p + 2021 * q, 114514, N), pow(2021 * p + 2020 * q, 1919810, N))
    else:
        hint = (2020 * p + 2021 * q) * (114514 * p ^ 1919810 * q)
    return (N, e), d, (t, hint)

def enc(pub, m):
    assert m.bit_length() < 2 * KEY_SIZE
    N, e = pub
    return pow(m, e, N)

flag = urandom(KEY_SIZE // 4 - len(flag) - 1) + flag
rsa = sorted([genkey(KEY_SIZE, i + 1) for i in range(3)])  #sorted() 函数对所有可迭代的对象进行排序操作
flag_enc = bytes_to_long(flag)
with open('data.txt', 'wb') as f:
    for i in rsa:
        flag_enc = enc(i[0], flag_enc)
        f.write(str(i[0]).encode() + b'\n')
        f.write(str(i[2]).encode() + b'\n')
    f.write(str(flag_enc).encode())


pub1 = (24456175739252870981581304595776265527580789354213705889514952622571517606615114014188604745480170064884744121665565461123709681135639261156228877797071437235270313935911710221224013214915625521692560168949226457147281956984016511425475569268340377366044912267078389493114774100457759766335494350723513026446153945967724342242760621535317132948637634137447086603157015714032353577491928694502480219162762778796278713726251839741877316320235482409453804557071811850426024239156530979675855531682790219949292249941429289527189548079020217829644155388264712919506101927204762836581916556029054227410446755012434149523907, 65537)
hint1 = (11194465651039338849668860869391382916187008521235968873517376368240647328279131694653159098981230189704943450639829474437841557500486114536592080297683997535761940313989700600817228546006587472449457304552982786077160967073392582663936582588118937240188929199967250897282390048562161876751613871197407166477824543070810778252591137875016328367811716543410776297999072466559766190913915977401225038801060442468940698866837193956782386171511951931682053791362247163079318658714261330160865206450361831549706202639425780809540915268985715250365703973111554668392956698101729371088903902815510126969270813545846688878436, 17575070452074464968464685888900584354082785587206854480058886334188834706711415687264090704483844609219317713370414939396981502545596215072289555215091489192108532218049617347807551176215194871046323246728002191092916073981616822792354983756933224599484679560364811927584511005706319025781495049828339597673027877101791731056858973125008661282473657841024159863183351507673377590268873433502386113510478904860352139244577603001748728561603049367350110219194912719879634057029598389600256986603045226717856411851889319411855611708924815208140438436916832300183220697580376028000547937684072248421737385425073258720879)

pub2 = (13352993434427612839250316087785373276111208822469810289866230193050170450794518181524598596966732188313549407048113550870223210852868050710461561040494395497666484751449645654832663242629975744541261760904104435281673411928307820840973290405335643983719305080838974901164831483267113861801494547226604608135486183955701869196416917286071817136304800254632296106100074356642224268864874382078852593360452317741619723807878207224194923792068333599501962967884857831789945522028206464288781915473239132326142121842810669566524661433159250738510228607082295815009339289374198865356079365915953452551403546701744884064031, 65537)
hint2 = (12890454835618057216693283154646295256547993419556349278949288547311899373637190048162618130021278574478039832361601927559315546568221037567751487507728339403821182254910702454208494226298434503487024254131784176237935900995801007317666642180650429259314744306390330668165601734196955036118294838073626269485626603885590730480357754106581924490566571344879282982046951044765811976989875623163040628948409259410684423744057580350283369203075946877294024798358704270660191627929717423150978437710495236596009273495917723464083875298899299815030715084594745073018225744460660615583487132081494166204388641238149852094282, 5892408960381393528929593894651709615387581968353636159772633906426675297650446939320873266449295420205620763150305529063257622079310711487381382868719233236245025724747453509230625510620424980310897414070432626951515255232242771606639145042677799112785849387727676897186903325574833200683661029697944196376539651575260283766098453523648743118163620885932748072014281721761491193499807903263636079336252182167396970170725734497688434577734178943260300047959649325673029043456664907935333740888039464474939932273320942354044042704907294868361621446456851700392150350003616197937536799424476834000764643527704625551853)

pub3 = (17177053664151806966121535982668901650446682095529000259014198321136965019483091916429100475246231867407340941754503516531164820854385489464670165994696842071709734917114309259104249964267442714558765555584583520230752931342668691556368988933368994298297834977992320617384955207871810834341958411445188648501483054131597044846869875850883593132672192435646701163895505576384723670421411576000182052110843472310892999443824985303491836371881071964076722792533675980383851694245221642510740670849302644321865778633169382807278959043510095767110855843398842297006177198956163900617493945356507206065454258413827755371801, 65537)
hint3 =  147564891156965292570696641342786452967360558121846098369357496719617601560966075535844427511017634445477003040401277027744788338595455729157718988227300863747068990924632491626486738327303794592458847930011281160213485429927564274159502656423511772354731728435252276421509371486371394150666126917491611566956437946526209935472892335326237922914832796135688923286993574647671267302996798652989809515575022082187659205790764278843387967061089270632617702993227950803598681057112120714439423855370869638071696031110503568236428236133214903903157588140761228266767061485354562520190608269059861310771018326290187980067226585095472

enc = 20818657741891295009893467743486158046601577833299329286355550851753497934767078082575000447225431087153800273576479954045498696738072232128407856203084431844186969858378450688523614741895535502018303247701703926903139480866938097432973872747078712177106506261992487913959871048823244157318990793901548356586648331630170444584271860937814077903454713790143481303987556135668221166092998434608685761181886184919877083574064873239648350240049295532703196970506874978843404737444703538215594641220650638006499013356385328001373661638736451619668301281773633736621211207476777867400720407439055814403559159725102449059529

题解

t=1时

hint = (pow(2020 * p + q, 114514, N), pow(2021 * p + 1919810, q, N))

wp

#t=1
i0=inverse(2021,n1)
t=(hint1[1]-1919810)*2020*i0
tmp1 = t**114514 - hint1[0]
q1 = gmpy2.gcd(tmp1,n1)
p1 = n1//q1
print(q1)
print(p1)
#158348905332839544537711729673813168060148142971293394847528702305103458737666052305025004146307872508261327535984723739882900675282993365832627641052404279861076243876879878646665656512157785200009289041769333736566118405957398721081293470314871018967687104420488820993734108473323238868133844546572769659889
#154444867729571679389153556486323157532577140978675777090725819427023455964213236152863764917732765288319002449639337160459966528167327386280914152445216627323877725305237304184435638084496987554404675517581531918827703768948170867363598114384956129368042904041453530044545354299811120395452716027640392658163

t=2时

hint = (pow(2020 * p + 2021 * q, 114514, N), pow(2021 * p + 2020 * q, 1919810, N))

k1=114514
k2=1919810
k3=k1*k2
h20=pow(hint2[0],k2,n2)
h21=pow(hint2[1],k1,n2)
i1=inverse(pow(2020,k3,n2),n2)
i2=inverse(pow(2021,k3,n2),n2)
q2=gmpy2.gcd(i1*h20-i2*h21,n2)
p2=n2//q2
assert n2==q2*p2
print(q2)
print(p2)
#112604275612978513523046704848333944070992858909556102508088764902051807456644170969755495753526047899334730561715084535572080520587727995337341854710655940152119853594124610045727830917583423202302459516112564428465023407102998406867458207348578682338765328787788350735172686643863312802511262283233941256539
#118583360727099931616143038309774420557484849452296151604423754672864299487877418075351113083763032866802950509787266656232869620846778204490228723176260335624995933128686816247048065363288322570474202424232531677079833785557213104207891923750312645124476628650891498347399714297641990551124186174929796159629

t=3时

hint = (2020 * p + 2021 * q) * (114514 * p ^ 1919810 * q)

爆破p,q

import itertools
from tqdm import tqdm
n3 = 17177053664151806966121535982668901650446682095529000259014198321136965019483091916429100475246231867407340941754503516531164820854385489464670165994696842071709734917114309259104249964267442714558765555584583520230752931342668691556368988933368994298297834977992320617384955207871810834341958411445188648501483054131597044846869875850883593132672192435646701163895505576384723670421411576000182052110843472310892999443824985303491836371881071964076722792533675980383851694245221642510740670849302644321865778633169382807278959043510095767110855843398842297006177198956163900617493945356507206065454258413827755371801
x3 = 147564891156965292570696641342786452967360558121846098369357496719617601560966075535844427511017634445477003040401277027744788338595455729157718988227300863747068990924632491626486738327303794592458847930011281160213485429927564274159502656423511772354731728435252276421509371486371394150666126917491611566956437946526209935472892335326237922914832796135688923286993574647671267302996798652989809515575022082187659205790764278843387967061089270632617702993227950803598681057112120714439423855370869638071696031110503568236428236133214903903157588140761228266767061485354562520190608269059861310771018326290187980067226585095472

a_list, b_list = [0], [0]

cur_mod = 1
for i in tqdm(range(1024)):
    cur_mod *= 2
    nxt_as, nxt_bs = [], []
    for al, bl in zip(a_list, b_list):
        for ah, bh in itertools.product([0, 1], repeat=2):
            aa, bb = ah * (cur_mod // 2) + al, bh * (cur_mod // 2) + bl
            if ((aa * bb % cur_mod == n3 % cur_mod) and ((114514*aa ^ 1919810*bb)*(2020*aa+2021*bb) %cur_mod == x3 % cur_mod)):
                nxt_as.append(aa)
                nxt_bs.append(bb)

    a_list, b_list = nxt_as, nxt_bs

for a, b in zip(a_list, b_list):
    if (a * b == n3):
        break

print(a)
print(b)
print(a * b - n3)
print(((114514*a ^ 1919810*b)*(2020*a+2021*b)) - x3)