NewStarCTF校外赛道

题目还是有点东西的，只记录解比较少的。

week1

chaos

纸老虎，一般代码越复杂，逻辑越简单(论文题除外)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def LC(key, x, times, flags):
    (k1, k2) = key
    xn = []
    xn.append(x)
    if flags:
        xn.append(1 - 2 * xn[0]**2)
    else:
        xn.append(k2 * xn[0]**3 + (1 - k2)*xn[0])
    for i in range(times):
        assert xn[i]>=-1 and xn[i]<=1 and xn[i+1]>=-1 and xn[i+1]<=1
        if flags:
            xn.append((1 - 2 * xn[i]**2)*(k1 * xn[i+1]**3 + (1 - k1)*xn[i+1]))
        else:
            xn.append((k2 * xn[i]**3 + (1 - k2)*xn[i])*(1 - 2 * xn[i+1]**2))
    return xn[times + 1]

# 首先恢复data和key，这部分不用逆，直接带参数求
k1, k2 = 3.967139695598587, 3.7926025078694305
k = [107, 99, 55, 198, 210, 56, 137, 44, 127, 25, 150, 113, 75, 215, 187, 132]

sum, r = 0, 1

for i in range(16):
    sum += k[i]
    r ^= k[i]
a_1 = (sum / 256) % 1
timea1 = 3 + int(1000 * a_1) % 30
b_1 = (r / 256)
timeb1 = 3 + int(1000 * b_1) % 30
xc_1 = a_1 * b_1
yc_1 = (a_1 + b_1) % 1

key = (k1,k2)
data = (a_1, timea1, b_1, timeb1, xc_1, yc_1)
#print(data)

# 逆一下异或还原flag
c = [23, 84, 105, 111, 230, 105, 97, 50, 58, 61, 25, 97, 57, 21, 175, 77, 102, 138, 120, 17, 66, 172, 52, 178, 101, 221, 109, 126, 71, 149, 63, 32, 56, 6, 134, 255, 110, 57, 15, 20, 116]
miu, omiga = [], []
ta = timea1
tb = timeb1
flag = []
for tmp in c:
    mi = tmp
    miu.append(LC(key, a_1, ta, 1))
    omiga.append(LC(key, b_1, tb, 0))
    flag.append(((int(miu[-1] * 1000) + int(omiga[-1] * 1000)) ^ mi) % 256)
    #print(flag)
    delta = tmp / 256
    for i in range(3):
        y = (yc_1 + delta) % 1
        y = k1 * y ** 3 + (1 - k1) * y
        x = xc_1
        x = k2 * x ** 3 + (1 - k2) * x
    ta = 3 + int(1000 * x) % 30
    tb = 3 + int(1000 * y) % 30

print(bytes(flag))

week2

ezPRNG

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 无模数lcg
from gmpy2 import *
from Crypto.Util.number import *

r = [32579077549265101609729134002322479188058664203229584246639330306875565342934, 30627296760863751873213598737521260410801961411772904859782399797798775242121, 59045755507520598673072877669036271379314362490837080079400207813316110037822, 29714794521560972198312794885289362350476307292503308718904661896314434077717, 3378007627369454232183998646610752441039379051735310926898417029172995488622, 35893579613746468714922176435597562302206699188445795487657524606666534642489]
t1 = r[1] - r[0]
t2 = r[2] - r[1]
t3 = r[3] - r[2]
t4 = r[4] - r[3]
t5 = r[5] - r[4]

tt1 = t3 * t1 - t2*t2
tt2 = t4 * t2 - t3*t3
p = gcd(tt1,tt2)
# print(p)
a = t2 * invert(t1,p) % p
b = (r[1] - a * r[0]) % p

seed = (r[0] - b) * invert(a,p) % p
print(long_to_bytes(seed))

ezRabin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import gmpy2
from Crypto.Util.number import *

p=10522889477508921233145726452630168129218487981917965097647277937267556441871668611904567713868254050044587941828674788953975031679913879970887998582514571
q=11287822338267163056031463255265099337492571870189068887689824393221951058498526362126606231275830844407608185240702408947800715624427717739233431252556379
n=p*q
e=2
c=59087040011818617875466940950576089096932769518087477304162753047334728508009365510335057824251636964132317478310267427589970177277870220660958570994888152191522928881774614096675980017700457666192609573774572571582962861504174396725705862549311100229145101667835438230371282904888448863223898642183925834109
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)

def de_rabin(c):
    mp = pow(c, (p+1) // 4, p)
    mq = pow(c, (q+1) // 4, q)
    a = (inv_p * p * mq + inv_q * q * mp) % n
    b = n-int(a)
    c = (inv_p * p * mq - inv_q * q * mp) % n
    d = n-int(c)
    return [a,b,c,d]

'''e=4的解密，就是做两次e=2的rabin解密，
第一次得到4个解，将4个解作为新的c分别再做一次e=2的rabin解密
'''

result=de_rabin(c)
r1=de_rabin(result[0])
r2=de_rabin(result[1])
r3=de_rabin(result[2])
r4=de_rabin(result[3])

l = r1 + r2 + r3 + r4
for ll in l:
    print(long_to_bytes(ll>>300))

week3

keyExchange

1
2
3
4
5
6
7
8
9
10
11
12
13
from hashlib import *
from Crypto.Cipher import AES
import base64

gb = 89434791765835058026108803508194156525355359465406829253856379139334424137549915669535243140614128105195584073112084994777148895681804127886440617684648237403345873311011154293855911891719204975035914932661810961867593769891076834656437254428353814290948181922438812745384577094827728409350756648446941874382
b = 141940531741414073502483547551457269459744373002985569536254444581939073930343975447649087549033350166772929396986965301002444997704537487577508504709368627174241095027876996113941220579274986994026832534664179333669861059196192190040046004398523932288881838011696679341328520530265002776147308306715042734185
p = 133448764119399847876731592238604881175769007976799828874328988761588128500145459082023001027383524831194316266946485380737147372837136403065060245135035225976604193830121124575947440188318348815263642243784574567832213775382081426762862856428888257126982268557543952549848053225651398101391048467656128070913
shared = pow(gb,b,p)
key = md5(str(shared).encode()).digest()

cipher = AES.new(key, AES.MODE_ECB)
ptext = cipher.decrypt(base64.b64decode('w8OCrexPPqnv2hR+xKeHhXIp0Blp1DYCV4LeZeeLpv5MzUL71raTOeOs4SQBySHH'))
print(ptext)

Prof. Shamir’s Secret

1
2
3
4
5
6
7
8
9
# modp下的拉格朗日插值 sagemath
p = 31332583438236375592937719796184754941510418106758544436807128579095975774977164550965999210436423180868482749439792419270701760326867558983833590368116755394302102816558834270767750410927007254951332459412016857259923960095221831744199277859298274645778838122123090174549834537459028702418645316659860963695912411044490603690484176741018002722235584411422885336520840416125528921196994346534698226763483608314982898155320734426983215291745003213365884087604024203316024824786079501166114638727651689476288442288919373885358425210859822108037791909364199015379638899887715692181883916583183449343868694265742569597579
R.<x> = Zmod(p)[] 
a = (107156592202708719207677242145785380370925248573491581679548864240229105117413, 130345771647598884054430192964980389494531690916321281560051538057910945565624075918097771618618910263287152864051564635195578796179646674192491555857366963976329072793625649841007238934532144994966695961491116944111900519450656607199501654544809304677384301432194356761274376314501143216649135187625964931902)
b = (100626477579781167218124067468465940736522526684796828200460725563611057086831, 107938673826832098883774065383352754899611421173786919174851524067358319831595518533880365335333592351382030254987030861475878447430100862628809476494215295084769705787398168068863060859122952000010558086859754975554734850230223040925027217057055876423229204027280075168615462165634569977166298865366648414270)
c = (90629424458637844580841178302065768114471702341586161908858665404968070428143, 78858394764644720845979385422903377630845158220853604360871859882044655577246282808874532941560824773914594412415345616068416548364923695233972936176087206729847544516343237888024173952758718279163069742944961359652574962129434781851767007643037433981750489254639449637677610354746497770492254725894119193662)
d = (93935717805931479760310332373603550626215862380271563609987050092246456803681, 87807687834883656794449107852803757931909462710953942209358337840912886376275257864214018767300085688088981183791568376874906785193974861264511995029891797395218085734556515485224508250678274640400740193260888803386269425525930551167801371074041851406813322268615707951973495879968706624649318162995708734670)
f = R.lagrange_polynomial([a,b,c,d])
print(f)

One Time Pad

MTP而已。首先利用出题人给的kasiski_test计算key的长度，然后参考这位爷的博客，按照MTP的攻击方式改一下脚本即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
from libnum import *
import string
from pwn import *
import binascii

def kasiski_test(file, length=3):

    with open(file,'rb') as f:
        ciphretext = f.read()
    f.close()
    dup_sturct = []
    for i in range(len(ciphretext) - 3):
        sub_struct = ciphretext[i:i+length]
        if ciphretext.count(sub_struct) >= 2:
            dup_sturct.append(sub_struct)
    possible_range = set()
    for d in dup_sturct:
        start = []
        i = 0
        while i+length < len(ciphretext):
            if d == ciphretext[i:i+length]:
                start.append(i)
            i += 1
        diff = []
        for i in range(len(start) - 1):
            diff.append(start[i+1] - start[i])
        possible_range.add(gcd(*diff))
    gcd_list = []
    for i in product(possible_range, repeat=2):
        gcd_list.append(gcd(i[0],i[1]))
    gcd_elem = set(gcd_list)
    pre_sort = []
    width = 0
    for i in gcd_elem:
        pre_sort.append((i, gcd_list.count(i) / len(gcd_list)))
        width = max(width, len(str(i)))
    pre_sort.sort(key = lambda t:t[1])
    for t in pre_sort[::-1]:
        print(f'key length: {str(t[0]).rjust(width, " ")} with probability {t[1]}')
    return pre_sort[-1][0]

filename = 'encrypted_book'
keylen = int(kasiski_test(filename))
print(f"key 长度为:{keylen}")


# ff = open('encrypted_book','rb')
# l = []
# cipher = ff.read().strip()
# print(cipher)
# f1 = open('Problem.txt','w')
# for i in range(0,len(cipher),5):
#     tmp = str(binascii.b2a_hex(cipher[i:i+5]))[2:-1]
#     f1.write(tmp+'\n')
# f1.close()

import Crypto.Util.strxor as xo
import libnum, codecs, numpy as np

def isChr(x):
    if ord('a') <= x and x <= ord('z'): return True
    if ord('A') <= x and x <= ord('Z'): return True
    return False

def infer(index, pos):
    if msg[index, pos] != 0:
        return
    msg[index, pos] = ord(' ')
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(' ')

dat = []

def getSpace():
    for index, x in enumerate(c):
        res = [xo.strxor(x, y) for y in c if x!=y]
        f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
        cnt = [f(pos) for pos in range(len(x))]
        for pos in range(len(x)):
            dat.append((f(pos), index, pos))

c = []
for x in open('Problem.txt', 'r').readlines():
    x = str(x.encode()[:-1])[2:-1]
    tmp = binascii.a2b_hex(x)
    c.append(tmp)
    print(tmp)
print(c)
c = c[:-1]
msg = np.zeros([len(c), len(c[0])], dtype=int)

getSpace()

dat = sorted(dat)[::-1]
for w, index, pos in dat:
    infer(index, pos)

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))

AES？

AES解密，然后拿去恢复mt19937，要用MT19937Predictor这个轮子，randcrack需要32bit伪随机数，不太好分割。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from Crypto.Cipher import AES
from binascii import a2b_hex
from mt19937predictor import MT19937Predictor

f = open("msg.txt", 'rb')
old_key = b'73E5602B54FE63A5'
old_iv = b'B435AE462FBAA662'

random_64 = []
random_32 = []
for i in range(208):
    aes = AES.new(old_key,AES.MODE_CBC,old_iv)
    c_tmp = f.readline()[:-2]
    c_tmp = a2b_hex(c_tmp)
    #print(c_tmp)
    m_tmp = aes.decrypt(c_tmp)
    m_hex = m_tmp.strip(b'\x00')
    if len(m_hex) == 24:
        random_64.append(int(m_hex[:16],16))
        random_32.append(int(m_hex[16:],16))
    else:
        random_64.append(int(m_hex[:15],16))
        random_32.append(int(m_hex[15:],16))

Pre = MT19937Predictor()
for i in range(208):
    Pre.setrandbits(random_64[i],64)
    Pre.setrandbits(random_32[i],32)

c = a2b_hex('c82dc20b7512d03f1a0982eb8a6e855db20f6fe3ff8d202a6fb74c6522fa6e623c6abe6725cafe78f9624ad59f3e90af6f985f38f75ec4d62ff7e02bd7c2f051')

salt = "{:X}".format(Pre.getrandbits(32)).encode('utf-8')
#print(salt)
key = "{:X}".format(Pre.getrandbits(64)).encode('utf-8')
iv = "{:X}".format(Pre.getrandbits(64)).encode('utf-8')
print(key,iv)
dec = AES.new(key,AES.MODE_CBC,iv)
print(dec.decrypt(c))

week4

LCG Revenge

三阶而已，类似普通lcg逆推十次：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from gmpy2 import *
a = 18038175596386287827
b = 15503291946093443851
c = 17270168560153510007
p = 307956849617421078439840909609638388517
r = [255290883651191064919890629542861653873, 221128501895959214555166046983862519384, 108104020183858879999084358722168548984]

for i in range(10):
    tmp = (r[-1] - c * r[-2] - b * r[-3]) * invert(a, p) % p
    r = [tmp] + r[:-1]
for i in range(3):
    print(long_to_bytes(r[i]))

代数关系

理论上，用$k\cdot phi$求逆解rsa结果也是一样的，故只要得到$phi$的倍数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from gmpy2 import *

n = 714592173868259951547903824656567142382519201815807137392662736000480461106944240411907971077744283561181468187349950157770542641452016168710768060100431878635594871092115167496636869765435245733216244455291669985854820686150487479060100362374214950338593785006799039892489525125499595277195821419495485780569578409849268011672935670978669183434574625404664252352238179018153026065565737180327403650490113961989352069795255693066847568569258596045200617988242378417608661573561288798387013713959291514998718810340095720086582431808535500784877130015856483311803720730193251968718389940211890886176473856457082812043712013634688479195044004890584238387779313840532514565194377261080408568578839974414957533288241409106206637332990105576057838430267703746376981194305776942499262213827373958311438790046259142383469934115411137484269094594634801601455381187640866738280586324069047262621776502056490534194678730988305691412586133810702956723819024793893235153104715079346666767828770304227597496868066084967074574249861996861449220457370695654952738759446674531850565616794250604969906523629086439326216263355721761747979532714573810102811235244618245569028203230483116293028005467298691574981713677092048315265963514382056811642161463
e1 = 42407
e2 = 42299
e3 = 64279
c1 = 147746559360802924168767659277705450630485609696398746571701418818848770182885487620535212747337538428905143459150636194921920646777706320249140903061217676389530668645622949973659702291367297066656754690100263868506461956113055815101461657779702873682097533482492493899104205046186278766341878854368500917007433940486307279045874511368494257897755625125620904196433190777249505786257092826031743302124873284619940344765699423310728402472381757497703327215054987663079091464775324695334786123993004899881875932719629531115443494782427464033199136840262965875592542948702903121840007890458510167896574258848373182376940828605330277069434815885568024582498080844909563591272397488770838751339866638704837915487427276557777372613819511517108295620835412232055690690331814390700825513053666493393942792555525632325524757429986865995789852014588602452362551730826736918369894537815766447265166762601145909581089407049818337486974627574263275878986623999208215467068257094963543761810512552366121738916812287617877452022267220425292446818899145860109087267084524150679796547645233300059224249369109340663349590685107672065377058337980842108933489505620025066451603214522163014130542079244955200533246817511795384645564870718654306017093880
c2 = 337796038485337223816475984950456810748129968181260652436798659350041388661303298381024293567858637131784295193867689006379455173201801538614335070721020735891108350570605513554850505589909457080361317990263630725721623909042708574097188905696426452814443072330582517110013425687309570310925148848467651593011914844474279987415423796247841257536637823609202705263533635281512231854231077727153008468034663708367221732104195468247696442441086937944990689793952230215990824397909249441015759060017517894957594510803336664512608128010545289784049784177611524398804382654716236024276493647659224649016999444437679713035528891917192417814659613017511330578462974624880551299057883811283033946146889355467779050967361027087080352841747836678980418533840472145655131425703508683270849398801701504340623072029235085830962038699908963834215641154556517289466852886243166207700576530398250363365976100132377349909530093158372007815925018963904011651612576427055409180229217198739845333777332027781322479300353269326257620342214186859996302004152073249996007973827806898128006273636862496964659067036495886736584255338505886284353124133030688669501417184690143652760207937780991619589875885728364937580912382631625198455389969845802240231827163
c3 = 424077500283538548695429029734927642518438524525805172568745880982861798954369892065855075306396658578715593140988681322211943800827469098807795208943724228288132152970084568728843669855312178059145983168245747282178118927927118026053179993918910256713266934916520151359475678446638810022833365506023312578408649890108868706577071610442415250434663703848788000124360027832658586954993369200881819393055860013390887044444898844318376925700215369036711799193621862491000483927756231147580685621531144248717419030824674055599055717010063636336702022163459269369324701987636772581709509640297923613071083421937504088720011643179567005037514310053762735787172663099935520119785909997287518567706508640150762285653766660798661964916169965639164375045609322144422628622388969490052285300841751657575450486389268063959043056821417358486314747981330380819421643688151487077209015995287339609841113765813462834471270766622938036101602597257457988755053683191621395473412095142041134027974560324126052952093513827172817662085883985649068515306916979488707694772473239863027480932340145990906115024722682989661592015805559935349596282010900810573490368602483785908673810154811269934225750196861258621132739166572297393817253205915435333491161203
gift_from_fallwind = 436057126906623515829218011238744316017674469205661117597268470150957758251976942445150879861108983042930734360653000973980600283904101499137333865224021780243160123582776537464659885717072177232387979780155820186376822704547514869653697300455384885557911728798950305201936973078685581794365075352341541134238714464727825137128067542739078985472265837037034067906587445615146595102552611894550913742780821268889878629177560903295511218320565910385133911886947889495561650713735268032963799756628442264275798506978864616008762967965435601210553178014009864471368535327898667309420704800396343299194692424445757081230545316510925050736165766681764700768348825662815908360495749201689747586178884303154943439689695756080847567228630187446741488386672483582019385735879376786013583105010830909520853067056907311999554079858869757789193026155282645740531423042696088661716948429683650063340097187696375083991311139748519133745606598795309849873485013934772051034350080361176801194568727665884824462291930504184029406404464952205159309484625000859491407470043008763418189126078287693565790619787102318883565462574011050013632489624673181763059753755492153825048101618871500056894854231049792292739927027237110872703608633932490764567008732
# 也就是这里可以求出kphi
kphi = (e1*e2*gift_from_fallwind +e2 - e1)
print(kphi)
d1 = invert(e1,kphi)
d2 = invert(e2,kphi)
d3 = invert(e3,kphi)
m1 = long_to_bytes(pow(c1,d1,n))
m2 = long_to_bytes(pow(c2,d2,n))
m3 = long_to_bytes(pow(c3,d3,n))
print(m1+m2+m3)

week4

An der schönen Elliptische Kurve

简单ecdh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Cipher import AES
from hashlib import md5
from binascii import a2b_hex

a = 14489
b = 10289
p = 7486573182795736771889604737751889118967735916352298289975055815020934891723453392369540853603360270847848895677903334441530052977221688450741083448029661

F = GF(p)
E = EllipticCurve(F, [a, b])
Pub = (1285788649714386836892440333012889444698233333809489364474616947934542770724999997145538088456652601147045234490019282952264340541239682982255115303711207,1081635450946385063319483423983665253792071829707039194609541132041775615770167048603029155228167113450196436786905820356216200242445665942628721193713459)
Pub = E(Pub)
Private = 2549545681219766023689977461986014915946503806253877534915175093306317852773
c = '2f65ff4a97e0e05c06eab06b58ea38a3d5b6d2a65ea4907bc46493b30081a211d7cffc872a23dbd565ef307f9492bb23'
iv = 'd151c04c645c3e2a8d3f1ae44589ef20'
c = a2b_hex(c)
iv = a2b_hex(iv)
shared = Private*Pub
key = md5(str(int(shared.xy()[0])).encode()).digest()

cipher = AES.new(key, AES.MODE_CBC, iv)
m = cipher.decrypt(c)
print(m)

flip-flop

简单的字节翻转，因为iv可控所以可操作。

1
2
3
4
5
6
7
8
9
10
11
12
import binascii
from pwn import xor

admin = b'AdminAdmin______'
guest = b'NewStarCTFer____'
c_hex = '3ba7d4c8d162c6d8fbb5f403f90e7d5456a955c7a7b10aa05be8234d97ba079f'
iv = binascii.a2b_hex(c_hex[:32])
c = c_hex[32:]

fake_iv = xor(admin,guest)
fake_iv = xor(fake_iv,iv)
print(str(binascii.b2a_hex(fake_iv))[2:-1]+c)

扫一扫，分享到微信

微信分享二维码
本站总访问量： 总访客次数：

tag:

梦想是成为全栈佬并养一只猫