前言
感觉这是打的最有意思的一次比赛了，当时在火车站打开电脑写的，秒了一题，然后上火车了，一路很颠就没有再写了，复现一下前三题
题目
complex_enc
task
from Crypto.Util.number import *
import random
from secret import flag
def GET_KEY(n):
sum=2
key=[1]
for i in range(n):
r=random.randint(0,1)
x=sum+random.randint(0,n)*r
key.append(x)
sum+=x
return key
def enc(m,k):
cipher_list = []
for i in range(len(m)):
if m[i] == 1:
cipher_list.append(m[i] * k[i])
cipher = sum(cipher_list)
return cipher
m=bytes_to_long(flag)
m = [int(bit) for byte in flag for bit in format(byte, '08b')]
key=GET_KEY(len(m))
c=enc(m,key)
with open('output.txt', 'w') as f:
f.write(str(c))
f.write(str(key))output
287687761937146187597379915545639385740275457170939564210821293233370716878150576
[1, 2, 87, 99, 190, 380, 760, 1702, 3350, 6712, 13302, 26669, 53257, 106512, 213212, 426262, 852583, 1705083, 3410164, 6820581, 13640909, 27281818, 54563749, 109127508, 218254958, 436509851, 873019897, 1746039768, 3492079367, 6984158992, 13968317822, 27936635563, 55873271257, 111746542368, 223493084736, 446986169472, 893972338944, 1787944677888, 3575889355776, 7151778711750, 14303557423366, 28607114846668, 57214229693336, 114428459386792, 228856918773559, 457713837547023, 915427675094046, 1830855350188252, 3661710700376344, 7323421400752912, 14646842801505675, 29293685603011275, 58587371206022773, 117174742412045483, 234349484824090806, 468698969648181659, 937397939296363271, 1874795878592726601, 3749591757185453143, 7499183514370906547, 14998367028741812852, 29996734057483625898, 59993468114967251756, 119986936229934503501, 239973872459869007099, 479947744919738013939, 959895489839476027878, 1919790979678952055983, 3839581959357904111739, 7679163918715808223719, 15358327837431616447319, 30716655674863232894717, 61433311349726465789458, 122866622699452931578804, 245733245398905863157495, 491466490797811726314990, 982932981595623452629980, 1965865963191246905260222, 3931731926382493810520182, 7863463852764987621040623, 15726927705529975242080987, 31453855411059950484161974, 62907710822119900968323970, 125815421644239801936647918, 251630843288479603873295836, 503261686576959207746591710, 1006523373153918415493183613, 2013046746307836830986367190, 4026093492615673661972734253, 8052186985231347323945468456, 16104373970462694647890936894, 32208747940925389295781874025, 64417495881850778591563748059, 128834991763701557183127495888, 257669983527403114366254991760, 515339967054806228732509983520, 1030679934109612457465019967093, 2061359868219224914930039934133, 4122719736438449829860079868450, 8245439472876899659720159736935, 16490878945753799319440319473651, 32981757891507598638880638947330, 65963515783015197277761277894728, 131927031566030394555522555789579, 263854063132060789111045111579109, 527708126264121578222090223158048, 1055416252528243156444180446316096, 2110832505056486312888360892632193, 4221665010112972625776721785264450, 8443330020225945251553443570528835, 16886660040451890503106887141057670, 33773320080903781006213774282115477, 67546640161807562012427548564230882, 135093280323615124024855097128461699, 270186560647230248049710194256923398, 540373121294460496099420388513846796, 1080746242588920992198840777027693592, 2161492485177841984397681554055387246, 4322984970355683968795363108110774528, 8645969940711367937590726216221549105, 17291939881422735875181452432443098117, 34583879762845471750362904864886196180, 69167759525690943500725809729772392360, 138335519051381887001451619459544784838, 276671038102763774002903238919089569616, 553342076205527548005806477838179139174, 1106684152411055096011612955676358278348, 2213368304822110192023225911352716556750, 4426736609644220384046451822705433113446, 8853473219288440768092903645410866226907, 17706946438576881536185807290821732453830, 35413892877153763072371614581643464907890, 70827785754307526144743229163286929815519, 141655571508615052289486458326573859631099, 283311143017230104578972916653147719262229, 566622286034460209157945833306295438524626, 1133244572068920418315891666612590877049074, 2266489144137840836631783333225181754098066, 4532978288275681673263566666450363508196132, 9065956576551363346527133332900727016392264, 18131913153102726693054266665801454032784553, 36263826306205453386108533331602908065569081, 72527652612410906772217066663205816131138180, 145055305224821813544434133326411632262276342, 290110610449643627088868266652823264524552684, 580221220899287254177736533305646529049105368, 1160442441798574508355473066611293058098210736, 2320884883597149016710946133222586116196421472, 4641769767194298033421892266445172232392842944, 9283539534388596066843784532890344464785686063, 18567079068777192133687569065780688929571371951, 37134158137554384267375138131561377859142743902, 74268316275108768534750276263122755718285487804, 148536632550217537069500552526245511436570975608, 297073265100435074139001105052491022873141951360, 594146530200870148278002210104982045746283902576, 1188293060401740296556004420209964091492567805360, 2376586120803480593112008840419928182985135610512, 4753172241606961186224017680839856365970271221024, 9506344483213922372448035361679712731940542442048, 19012688966427844744896070723359425463881084884096, 38025377932855689489792141446718850927762169768220, 76050755865711378979584282893437701855524339536412, 152101511731422757959168565786875403711048679072824, 304203023462845515918337131573750807422097358145648, 608406046925691031836674263147501614844194716291296, 1216812093851382063673348526295003229688389432582797, 2433624187702764127346697052590006459376778865165617, 4867248375405528254693394105180012918753557730331006, 9734496750811056509386788210360025837507115460662129, 19468993501622113018773576420720051675014230921324265, 38937987003244226037547152841440103350028461842648406, 77875974006488452075094305682880206700056923685296910, 155751948012976904150188611365760413400113847370593722, 311503896025953808300377222731520826800227694741187444, 623007792051907616600754445463041653600455389482374933, 1246015584103815233201508890926083307200910778964749821, 2492031168207630466403017781852166614401821557929499642, 4984062336415260932806035563704333228803643115858999284, 9968124672830521865612071127408666457607286231717998666, 19936249345661043731224142254817332915214572463435997301, 39872498691322087462448284509634665830429144926871994535, 79744997382644174924896569019269331660858289853743989190, 159489994765288349849793138038538663321716579707487978260, 318979989530576699699586276077077326643433159414975956596, 637959979061153399399172552154154653286866318829951913129, 1275919958122306798798345104308309306573732637659903826311, 2551839916244613597596690208616618613147465275319807652591, 5103679832489227195193380417233237226294930550639615305147, 10207359664978454390386760834466474452589861101279230610294, 20414719329956908780773521668932948905179722202558461220588, 40829438659913817561547043337865897810359444405116922441176, 81658877319827635123094086675731795620718888810233844882508, 163317754639655270246188173351463591241437777620467689764860, 326635509279310540492376346702927182482875555240935379529854, 653271018558621080984752693405854364965751110481870759059704, 1306542037117242161969505386811708729931502220963741518119363, 2613084074234484323939010773623417459863004441927483036238705, 5226168148468968647878021547246834919726008883854966072477346, 10452336296937937295756043094493669839452017767709932144954692, 20904672593875874591512086188987339678904035535419864289909384, 41809345187751749183024172377974679357808071070839728579818768, 83618690375503498366048344755949358715616142141679457159637536, 167237380751006996732096689511898717431232284283358914319275072, 334474761502013993464193379023797434862464568566717828638550144, 668949523004027986928386758047594869724929137133435657277100288, 1337899046008055973856773516095189739449858274266871314554200576, 2675798092016111947713547032190379478899716548533742629108401375, 5351596184032223895427094064380758957799433097067485258216802527, 10703192368064447790854188128761517915598866194134970516433605054, 21406384736128895581708376257523035831197732388269941032867210108, 42812769472257791163416752515046071662395464776539882065734420216, 85625538944515582326833505030092143324790929553079764131468840607, 171251077889031164653667010060184286649581859106159528262937681073, 342502155778062329307334020120368573299163718212319056525875362112, 685004311556124658614668040240737146598327436424638113051750724224, 1370008623112249317229336080481474293196654872849276226103501448448, 2740017246224498634458672160962948586393309745698552452207002896896, 5480034492448997268917344321925897172786619491397104904414005793914, 10960068984897994537834688643851794345573238982794209808828011587706, 21920137969795989075669377287703588691146477965588419617656023175412, 43840275939591978151338754575407177382292955931176839235312046350824, 87680551879183956302677509150814354764585911862353678470624092701691, 175361103758367912605355018301628709529171823724707356941248185403485, 350722207516735825210710036603257419058343647449414713882496370806824, 701444415033471650421420073206514838116687294898829427764992741613648, 1402888830066943300842840146413029676233374589797658855529985483227499, 2805777660133886601685680292826059352466749179595317711059970966454839, 5611555320267773203371360585652118704933498359190635422119941932909634, 11223110640535546406742721171304237409866996718381270844239883865819325, 22446221281071092813485442342608474819733993436762541688479767731638735, 44892442562142185626970884685216949639467986873525083376959535463277328, 89784885124284371253941769370433899278935973747050166753919070926554729, 179569770248568742507883538740867798557871947494100333507838141853109648, 359139540497137485015767077481735597115743894988200667015676283706219166, 718279080994274970031534154963471194231487789976401334031352567412438331, 1436558161988549940063068309926942388462975579952802668062705134824876530, 2873116323977099880126136619853884776925951159905605336125410269649753060, 5746232647954199760252273239707769553851902319811210672250820539299506381, 11492465295908399520504546479415539107703804639622421344501641078599012695, 22984930591816799041009092958831078215407609279244842689003282157198025444, 45969861183633598082018185917662156430815218558489685378006564314396050678, 91939722367267196164036371835324312861630437116979370756013128628792101318, 183879444734534392328072743670648625723260874233958741512026257257584202636, 367758889469068784656145487341297251446521748467917483024052514515168405272, 735517778938137569312290974682594502893043496935834966048105029030336810544, 1471035557876275138624581949365189005786086993871669932096210058060673621088, 2942071115752550277249163898730378011572173987743339864192420116121347242216, 5884142231505100554498327797460756023144347975486679728384840232242694484649, 11768284463010201108996655594921512046288695950973359456769680464485388969041, 23536568926020402217993311189843024092577391901946718913539360928970777938082, 47073137852040804435986622379686048185154783803893437827078721857941555876305, 94146275704081608871973244759372096370309567607786875654157443715883111752579, 188292551408163217743946489518744192740619135215573751308314887431766223505070, 376585102816326435487892979037488385481238270431147502616629774863532447010118, 753170205632652870975785958074976770962476540862295005233259549727064894020344, 1506340411265305741951571916149953541924953081724590010466519099454129788040580, 3012680822530611483903143832299907083849906163449180020933038198908259576081160, 6025361645061222967806287664599814167699812326898360041866076397816519152162452, 12050723290122445935612575329199628335399624653796720083732152795633038304324883, 24101446580244891871225150658399256670799249307593440167464305591266076608649853, 48202893160489783742450301316798513341598498615186880334928611182532153217299508, 96405786320979567484900602633597026683196997230373760669857222365064306434599262, 192811572641959134969801205267194053366393994460747521339714444730128612869198530, 385623145283918269939602410534388106732787988921495042679428889460257225738396863]
思路
很典型的超递增序列，应该是01背包，当时在火车站忘记怎么写了，就手搓了一个麻烦的方法
exp
from Crypto.Util.number import *
import random
# 解析key
def parse_key(key_str):
key = key_str.strip('[]').split(',')
key = [int(k.strip()) for k in key]
return key
# 超级递增序列的解密过程
def decrypt(cipher, key):
key = sorted(key, reverse=True) # 按降序排列key
m_bits = []
for k in key:
if cipher >= k:
m_bits.append(1)
cipher -= k
else:
m_bits.append(0)
m_bits.reverse()
return m_bits
# 将比特序列转换回字节和字符串
def bits_to_bytes(bits):
byte_list = []
for i in range(0, len(bits), 8):
byte = bits[i:i+8]
byte_str = ''.join(map(str, byte))
byte_list.append(int(byte_str, 2))
return bytes(byte_list)
cipher=
key=[]
m_bits = decrypt(cipher, key)
flag = bits_to_bytes(m_bits)
print(flag)01背包exp
flag = ""
for i in range(len(c)):
if(sum >= c[len(c)-i-1]):
flag += "1"
sum -= c[len(c)-i-1]
else:
flag += "0"
assert sum == 0
print(long_to_bytes(int(flag[1:][::-1],2)))1z_RSA
task
from Crypto.Util.number import *
from sympy import *
import os
from secrets import flag
nbit =130
e = 3
l = getPrime(505)
m = bytes_to_long(flag + os.urandom(64))
assert len(flag) == 29
while True:
p, q = getPrime(nbit), getPrime(nbit)
PQ = int(str(p<<120)+str(q))
QP = int(str(q<<120)+str(p))
if isPrime(PQ) and isPrime(QP):
break
n = PQ * QP
PP = nextprime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = nextprime((QP >> 190) * (PQ & (2 ** 190 - 1)))
N = PP * QQ
M = pow(m,1,l)
c = pow(m,e,N)
print('n =', n)
print('M =', M)
print('l =', l)
print('c =', c)
'''
n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691
M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
'''思路
当时的想法是想起来了一个很类似的题，叫做[EIS 2019]rsa1，然后发现不一样，草了，
$$
n=PQ QP
=(p\times2^{120}\times10^{39}+q)\times (q\times2^{120}\times10^{39}+p)
=p \times q \times 2^{240} \times 10^{392} +p^2 \times 2^{120} \times 10^{39}+q^2 \times 2^{120} \times 10^{39}+p \times q
$$
所以pq低位就是$$ n \bmod 2^{120} \times 10^{39} $$
高位是$$ \frac{n}{2^{360} 10^{39\times3}} $$
因为p，q有大小误差，再除以个10左右，之后就是常见的e,phi不互素，然后crt
from Crypto.Util.number import *
import sympy
from sympy.abc import x, y, z
n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691
M = 362082814233552186049901906240295847474479864.
56188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
p_q_l = n % (2**120 * 10**39)
p_q_h = n // (2**360 * 10 ** (39 * 3)) // 10
pq = p_q_h * (2**120 * 10**39) + p_q_l
a = sympy.solve(
[x * y - pq, (x * 2**120 * 10**40 + y) * (y * 2**120 * 10**39 + x) - n], [x, y]
)
p, q = a[1]
print(p)
print(q)#sage
from Crypto.Util.number import *
p=855604426214387476576649090490109822073
q=1213149261930568621267125437333569321667
PQ = int(str(p<<120)+str(q))
QP = int(str(q<<120)+str(p))
PP = next_prime((PQ >> 190) * (QP & (2**190 - 1)))
QQ = next_prime((QP >> 190) * (PQ & (2**190 - 1)))
for mp in GF(PP)(c).nth_root(3, all=True):
for mq in GF(QQ)(c).nth_root(3, all=True):
m = crt([ZZ(mp), ZZ(mq)], [PP, QQ])
mm = crt([m,M],[PP*QQ,l])
print(long_to_bytes(int(mm)))
#b'DASCTF{Ar3_Y0u_Su93_Abt139??}'found
task
from Crypto.Util.number import *
from random import *
from secret import flag
from sympy import *
bits = 1024
l = 138833858362699289505402947409766595473722379891580589518174731439613184249727659678966809301611194545239974736175752769503863392697421092435438747741790652435801956708356186578269272819715592752821497122516109657809748674185639254430403157877064556216401002688452227124543508128414591884297632663910714681207
assert isPrime(l)
def generate_prime(bits):
return randprime(2**(bits-1), 2**bits)
def fun(data,y,n):
return sum([data[i] * pow(y,i,n) for i in range(len(data))]) % n
def gen(x, y, z, w, n):
data = [randint(n // 4, n) for _ in range(10)]
leak1 = pow(x + pow(y, z, n), w, n)
leak2 = fun(data, y, n)
return data, leak1, leak2
def encrypt(l,m,n):
mm = bin(m)[2:].zfill((m.bit_length() // 8 + 1) * 8)
length = len(mm)
c = []
s = []
for i in range(length):
a = randint(1, n)
s.append(pow(a, length, n))
for j in range(length):
c.append(pow(l,int(mm[j]),n) * s[j] % n)
return c
p, q = [generate_prime(bits) for _ in range(2)]
r = generate_prime(bits // 4)
n = p ** 2 * q * r
e1 = generate_prime(128)
e2 = generate_prime(128)
phi1 = p * (p - 1) * (q - 1) * (r - 1)
phi2 = (p - 1) * (p - 2) * (q - 2) * (r - 2)
d1 = inverse(e1, phi1)
d2 = inverse(e2, phi2)
t = getRandomRange(n // 4, n)
data, leak1, leak2 = gen(r, t, e1, d1, n)
m = bytes_to_long(flag)
c = encrypt(l, m, n)
with open('output.txt','w') as f:
f.write(f'n = {n}\n')
f.write(f'e1 = {e1}\n')
f.write(f'ed = {e2 * d2}\n')
f.write(f'data = {data}\n')
f.write(f'leak1 = {leak1}\n')
f.write(f'leak2 = {leak2}\n')
f.write(f'c = {c}')output
太长了，不放这里思路
求解p
代码又臭又长，观察代码可以发现$$ e_2和phi_2 $$可以直接用来求解。
$$ e_2d_2=1+(p-1)(p-2)(q-2)(r-2)$$
有$$ e_2d_2-1=k(p-1) $$
再$$ 2^{e_2d_2}-2 \equiv 2^{k(p-1)} \bmod p $$
那么就可以通过费马小定理和gcd求解p
即$$ p=\gcd(2^{e_2d_2}-2 \bmod n,2) $$
即$$ p=\gcd(pow(2,e_2d_2-1,n)-1,n) $$
求解flag
mm就是m转成二进制，长度是length（用t表示），生成了一个随机列表s，
$$s=a^t ，a为随机数$$,然后在逐位加密，若为0，则为s，否则为ls，其中l是一个固定数字，且不是mod p情况下的二次剩余，但是t为偶数，那么s为二次剩余，所以每一位去还原判断是否为二次剩余即可
exp
from Crypto.Util.number import *
#数据
p = GCD(pow(2,ed-1,n)-1,n)
flag = ""
for i in range(len(c)):
if(pow(c[i],(p-1)//2,p) == 1):
flag += "0"
else:
flag += "1"
print(long_to_bytes(int(flag,2)))总结
最后两道题都是格了，是我的未知领域，就不写了，看别人的wp也是一脸懵逼，自己还是需要努力追赶别人的步伐，不能被落下太多。