DragonKnight CTF 2024 Writeup

在Del0n1x里打的一场比赛，把Crypto方向的全解了——当然，主要是得益于题目的idea大部分都是借鉴的，所以只要检索能力强基本就能AK。

Crypto

Crypto_签到

Python
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
from Crypto.Util.number import *

m = b'flag{********}'
a =  getPrime(247)
b =  getPrime(247)
n =  getPrime(247)

seed = bytes_to_long(m)

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed  
        self.a = a  
        self.b = b  
        self.m = m  

    def generate(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed

seed = bytes_to_long(m)

output = LCG(seed,a,b,n)

for i in range(getPrime(16)):
    output.generate()

print(output.generate())
print(output.generate())
print(output.generate())
print(output.generate())
print(output.generate())

'''
5944442525761903973219225838876172353829065175803203250803344015146870499
141002272698398325287408425994092371191022957387708398440724215884974524650
42216026849704835847606250691811468183437263898865832489347515649912153042
67696624031762373831757634064133996220332196053248058707361437259689848885
19724224939085795542564952999993739673429585489399516522926780014664745253
'''

每次输出更新两次内部状态的LCG。看成一个新的系数分别为\(a'=a^{2}, b'=(a+1)b\)的LCG就好。

Python
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
from Crypto.Util.number import *
import gmpy2

output = [5944442525761903973219225838876172353829065175803203250803344015146870499,141002272698398325287408425994092371191022957387708398440724215884974524650,42216026849704835847606250691811468183437263898865832489347515649912153042,67696624031762373831757634064133996220332196053248058707361437259689848885,19724224939085795542564952999993739673429585489399516522926780014664745253]
t = []
for i in range(1,len(output)):
    t.append(output[i]-output[i-1])

T = []
for i in range(1,len(t)-1):
    T.append(t[i+1]*t[i-1] - t[i]**2)

m = []
for i in range(len(T)-1):
    mm = gmpy2.gcd(T[i],T[i+1])
    if isPrime(mm):
        m.append(int(mm))
    else:
        for i in range(1,100):
            if isPrime(mm // i):
                mm = mm // i
                m.append(int(mm))
                break
    
for i in m:
    a = gmpy2.invert(t[0],i) * t[1] % i
    b = output[1] - a*output[0] % i
    a_ = gmpy2.invert(a,i)

    seed = a_ * (output[0]-b) % i
    for _ in range(2**16):
        seed = a_ * (seed - b) % i
        flag = long_to_bytes(seed)
        if b'flag' in flag:
            print(flag)

MatrixRSA_Revenge

Python
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
# Sage
from Crypto.Util.number import *
import os

flag = b"DRKCTF{??????????????}" + os.urandom(212)

p = getPrime(120)
q = getPrime(120)
print(f"p = {p}")
print(f"q = {q}")

part = [bytes_to_long(flag[16*i:16*(i+1)]) for i in range(16)]

M = Matrix(Zmod(n),[
    [part[4*i+j] for j in range(4)] for i in range(4)
])

e = 65537
C = M ** e

print(f"C = {list(C)}")

"""
p = 724011645798721468405549293573288113   
q = 712853480230590736297703668944546433
C = [(354904294318305224658454053059339790915904962123902870614765704810196137, 307912599668649689143528844269686459695648563337814923172488152872006235, 143644686443811064172873392982322248654471792394264352463341325181752577, 22995887787365556743279529792687264972121816670422146768160153217903088), (111349308911096779758451570594323566987628804920420784718347230085486245, 370237591900013263581099395076767089468466012835217658851568690263421449, 305451886364184428434479088589515273362629589399867618474106045683764897, 454103583344277343974714791669312753685583930212748198341578178464249150), (168497521640129742759262423369385500102664740971338844248603058993335309, 228941893018899960301839898935872289351667488000643221589230804176281482, 340080333594340128998141220817079770261711483018587969623825086357581002, 122922413789905368029659916865893297311475500951645918611759627764993518), (10332477229415731242316540110058798318207430965033579181240340751539101, 238172263316130590821973648893483382211906906298557131324791759298887701, 487586702165464601760230182019344052665496627253691596871783460314632260, 12238020921585443139790088280608644406695242899000592355653073240122626)]
"""

加密过程就是在\(Z/nZ\)上对明文矩阵做了幂运算。一个直观的思路是把C分别放在模p和模q下去考虑，因为我们知道一般线性群\(GL_4(F_p)\)是有限群，所以在这个群上面\(M^{n}=M^{n\ mod\ od}\)，\(od\)为群阶。

order的计算方法可以参考这里

\(C=M^{e}\)，所以我们只要恰当选取指数就可以让模p和模q下的C经过幂运算之后得到模p和模q的\(M\)，接下来CRT组合回去就好。

Python
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
# Sage
from Crypto.Util.number import *
C = [[354904294318305224658454053059339790915904962123902870614765704810196137, 307912599668649689143528844269686459695648563337814923172488152872006235, 143644686443811064172873392982322248654471792394264352463341325181752577, 22995887787365556743279529792687264972121816670422146768160153217903088], [111349308911096779758451570594323566987628804920420784718347230085486245, 370237591900013263581099395076767089468466012835217658851568690263421449, 305451886364184428434479088589515273362629589399867618474106045683764897, 454103583344277343974714791669312753685583930212748198341578178464249150], [168497521640129742759262423369385500102664740971338844248603058993335309, 228941893018899960301839898935872289351667488000643221589230804176281482, 340080333594340128998141220817079770261711483018587969623825086357581002, 122922413789905368029659916865893297311475500951645918611759627764993518], [10332477229415731242316540110058798318207430965033579181240340751539101, 238172263316130590821973648893483382211906906298557131324791759298887701, 487586702165464601760230182019344052665496627253691596871783460314632260, 12238020921585443139790088280608644406695242899000592355653073240122626]]

p = 724011645798721468405549293573288113
q = 712853480230590736297703668944546433
e = 65537
G1 = matrix(GF(p), 4, 4, C)
G2 = matrix(GF(q), 4, 4, C)
# 分别考虑mod p和mod q的finite field情况
od_p = product([p ^ 4 - p ^ i for i in range(4)])
od_q = product([q ^ 4 - q ^ i for i in range(4)])
# 有限群，适当选取指数使得运算结果为自身
inv_p = inverse(e, od_p)
inv_q = inverse(e, od_q)
dic1 = list((G1^inv_p)[0])
dic2 = list((G2^inv_q)[0])

# CRT组合回去
p = 724011645798721468405549293573288113
q = 712853480230590736297703668944546433
for mp, mq in zip(dic1,dic2):
	m = crt([ZZ(mp), ZZ(mq)], [p, q])
	res = long_to_bytes(m)
	print(res)

# b'DRKCTF{a58986e7-'
# b'33e5-4f65-8c22-b'
# b'8a5e620752d}V%\x17\xf1'
# b'K\xe0d\x0e\xde\xc2\xd1\xf1\xc0\xa4v\xe7\xcb\x13\x9c\x13'

EzDES

加密用的DES弱密钥，直接解密。

Python
1
2
3
4
5
6
7
8
9
10
11
from Crypto.Cipher import DES
from Crypto.Util.Padding import pad, unpad

key = b'\x01\x01\x01\x01\x01\x01\x01\x01'
des = DES.new(key, DES.MODE_ECB)
enc = b't\xe4f\x19\xc6\xef\xaaL\xc3R}\x08;K\xc9\x88\xa6|\nF\xc3\x12h\xcd\xd3x\xc3(\x91\x08\x841\xca\x8b\xc1\x94\xb5\x9f[\xcd\xc6\x9f\xf9\xf6\xca\xf5\x1a\xda\x16\xcf\x89\x154\xa1\xfe\xc5\x16\xcf\x89\x154\xa1\xfe\xc5'

dec = des.decrypt(enc)
print(dec)

# DRKCTF{We4k_K3y_1s_V3ry_D4nger0us_In_DES}

MidRSA

Python
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
from Crypto.Util.number import *
from secret import flag
import random
import gmpy2

def generate_Key1(ebits):
    e = [getPrime(ebits) for _ in range(4)]
    return e

def encrypt1(message,e):
    n = gmpy2.next_prime(bytes_to_long(message) << 300)
    m = getPrime(256)
    c = [int(pow(m,e[i],n)) for i in range(len(e))]
    return c

def generate_Key2(nbits):
    p = getPrime(nbits // 2)
    q = getPrime(nbits // 2)
    n = p*q
    e = [random.getrandbits(nbits // 4) for _ in range(3)]
    return n,e

def encrypt2(message,e,n):
    m = bytes_to_long(message)
    c = [int(pow(m,e[i],n)) for i in range(len(e))]
    return c
    
assert flag.startswith(b"DRKCTF{")

flag1 = flag[:len(flag)//2]
flag2 = flag[len(flag)//2:]

ebits = 7
e1 = generate_Key1(ebits)
cipher1 = encrypt1(flag1,e1)
print("e1 =",e1)
print("cipher1 =",cipher1)

nbits = 1024
n,e2 = generate_Key2(nbits)
cipher2 = encrypt2(flag2,e2,n)
print("e2 =",e2)
print("cipher2 =",cipher2)
print("n =",n)

"""
e1 = [109, 71, 109, 73]
cipher1 = [36272047346364825234770733058042613197790911431212158822254782055957208837848605160852567043492625692783344073921185227328379941291979083011033, 13421582077901767047291741873622169312010984740586925881415103229648835151589774736786336965745532072099996467445790339749720696886313635920080, 36272047346364825234770733058042613197790911431212158822254782055957208837848605160852567043492625692783344073921185227328379941291979083011033, 41425183140413487232780768389488969603566343428250573532166425276868000949579663990819005141199597640625439816343697426958648927294289659127871]
e2 = [79572758141493570128961125255246129069540961757778793209698370333142346488381, 80555585862127636800866563977080055603517001358195529410497461746213789997225, 44651921320695090688745333790065512192118202496468714141526113242887125432380]
cipher2 = [58600444300331800249882073146233995912287198739549440714207984476331259754331716531491187240053630185776787152600165426285021284302994699108557023545574315706006132536588848833818758624067461985444940651823107522770906474037882323326792755635934081822967331031854184791299228513024491344725765476710816941057, 16511944800191885973496391252612222059697387587833308714567450121364756390806094606646424594583975159634952911600665271092389815248477961923357683297311169260578508157717777465241680062644118354471550223231057620392252324514411927096940875466794869671163453991620492008856178108060167556176019729800517994337, 80885008609388989196377721090246742575908473911131498982960117640742106565184297197238656375198284856442596226398287448931285735903463892735111244609358611618958293002176923706195402338331128766464276441210238388187625107435781170368017908610916585774514676482124401329575553658828115269495158818527164441546]
n = 93468142044831350317940409833603031534515663349871776634867176846669780024082517910566484997161088199091160371537367121403194814422867749777235397168852158723228851090445429617275680206703935781244466363279841409768649097588586494453125840436600639420286950914680651600232197982546122764845043227394567787283
"""

encrypt1一眼LLL+GCD求解，思路参考maple佬的这道题目，encrypt2直接共模攻击。

注意打的时候去掉encrypt1里重复的一组e和c。

(其实encrypt1就是抄的maple的这道题吧...)

Python
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
# Sage
from Crypto.Util.number import *

exec(open("output.txt").read())

L = matrix(es).T.augment(matrix.identity(len(es)))
L[:, 0] *= 2 ^ 2048
L = L.LLL()
print(L[0][1:])
print(L[1][1:])
xx = product([ZZ(y) ^ x for x, y in zip(L[0][1:], cs)])
yy = product([ZZ(y) ^ x for x, y in zip(L[1][1:], cs)])
n = gcd(xx.numer() - xx.denom(), yy.numer() - yy.denom())
print(n)
print(long_to_bytes(n>>300))

# Python
import gmpy2 as gp
def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

n = 93468142044831350317940409833603031534515663349871776634867176846669780024082517910566484997161088199091160371537367121403194814422867749777235397168852158723228851090445429617275680206703935781244466363279841409768649097588586494453125840436600639420286950914680651600232197982546122764845043227394567787283
c1 = 58600444300331800249882073146233995912287198739549440714207984476331259754331716531491187240053630185776787152600165426285021284302994699108557023545574315706006132536588848833818758624067461985444940651823107522770906474037882323326792755635934081822967331031854184791299228513024491344725765476710816941057
c2 = 16511944800191885973496391252612222059697387587833308714567450121364756390806094606646424594583975159634952911600665271092389815248477961923357683297311169260578508157717777465241680062644118354471550223231057620392252324514411927096940875466794869671163453991620492008856178108060167556176019729800517994337
e1 = 79572758141493570128961125255246129069540961757778793209698370333142346488381
e2 = 80555585862127636800866563977080055603517001358195529410497461746213789997225
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
if s1<0:
	s1 = - s1
	c1 = gp.invert(c1, n)
elif s2<0:
	s2 = - s2
	c2 = gp.invert(c2, n)

m = pow(c1,s1,n)*pow(c2,s2,n) % n
print(hex(m)[2:])
print(bytes.fromhex(hex(m)[2:]))


# DRKCTF{5d0b96e8-e069-4378-82e7-120e4b761a0b}

MyEncrypto

Python
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
from Crypto.Util.number import *
from secret import flag      
import random

def getMyPrime():              
    while True:              
        r = random.getrandbits(64)              
        _p = r**6 -3*r**5 - r**4 + r**2 - r - 6
        _q = r**7 + 2*r**6 + r**5 + 4*r**4 + 7*r**2 + r + 4653
        if isPrime(_p) and isPrime(_q):              
            return _p, _q
                      
def enc(m, n):                        
    return pow(m, 65537, n)              

def LCG(s,a,b,n):
    return (a*s + b) % n


seed = bytes_to_long(flag)
P = getPrime(512)
a = random.randrange(0,P)
b = random.randrange(0,P)

def Roll():
    global seed
    seed = LCG(seed,a,b,P)
    return seed % 2**16

p, q = getMyPrime()
n = p * q              
enc_P = enc(P, n)
print(f"n = {n}")              
print(f"enc_P = {enc_P}")

out = []
for _ in range(40):
    out.append(Roll())

print(f"a = {a}")
print(f"b = {b}")
print(f"out = {out}")
"""
r = 1248775963213848425
P = 10679387699123200522776360035184725927822172255453595568464894884736102462568579313264894449779104030120028056158023524486966766295648236135714849745610937
n = 17959692613208124553115435318871530105762927141420294800783695207170608966804977782615874404539156257549097962410144332053383210075663138848832474791712256427111304125146378883542387121684653496644116081809328796925343393644118376497507
enc_P = 17215745298239635988196009014709535403293865406390546681749129213899045156482782458937447412919331336842808052179915132663427715069134196783415529688715962754860563850858056507148936427379551986735103284388996678146580229028006898491552
a = 2759277675743644814124420138047586760905070650864591936190199977578763421196999718749092450720072564786874114432179104175692800471519816376692104515142375
b = 8111240578821759579875175166986910195923820191652867334412871591814076020421468033017946066268237980082938735686222173713853299600396887041341974719819186
out = [39566, 15295, 19818, 55685, 49100, 6517, 2675, 9567, 37243, 40312, 42906, 35874, 44178, 1256, 40298, 29149, 35721, 19886, 63020, 50116, 6844, 39897, 16134, 50218, 44609, 46188, 52712, 49903, 20933, 5441, 19411, 8330, 6904, 39350, 60853, 43446, 35910, 43728, 61533, 13757]
"""

核心idea抄了osu!gaming CTF 2024的lucky-roll-gaming，拿现成的exp直接打就行。

多项式求根就能分解n然后拿到P。

Python
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
# Sage

# R = PolynomialRing(QQ, 'r')
# f = r^13 - r^12 - 6*r^11 - r^10 - 12*r^9 + 4*r^8 - 27*r^7 + 4634*r^6 - 13970*r^5 - 4670*r^4 - 6*r^3 + 4610*r^2 - 4659*r - 27918 - 17959692613208124553115435318871530105762927141420294800783695207170608966804977782615874404539156257549097962410144332053383210075663138848832474791712256427111304125146378883542387121684653496644116081809328796925343393644118376497507
# print(f.roots())

from Crypto.Util.number import *
p = 10679387699123200522776360035184725927822172255453595568464894884736102462568579313264894449779104030120028056158023524486966766295648236135714849745610937
a = 2759277675743644814124420138047586760905070650864591936190199977578763421196999718749092450720072564786874114432179104175692800471519816376692104515142375
b = 8111240578821759579875175166986910195923820191652867334412871591814076020421468033017946066268237980082938735686222173713853299600396887041341974719819186
out = [39566, 15295, 19818, 55685, 49100, 6517, 2675, 9567, 37243, 40312, 42906, 35874, 44178, 1256, 40298, 29149, 35721, 19886, 63020, 50116, 6844, 39897, 16134, 50218, 44609, 46188, 52712, 49903, 20933, 5441, 19411, 8330, 6904, 39350, 60853, 43446, 35910, 43728, 61533, 13757]

l = out
def lcg(s, a, b, p):
    return (a * s + b) % p
def get_roll():
    global seed
    seed = lcg(seed, a, b, p)
    return seed % (2**16)
n = len(out)
A = [[0 for _ in range(n+1)] for _ in range(n+1)] 
inv100 = pow((2**16),-1,p)
for i in range(n-1):
    A[i][i] = p
    A[n-1][i] = a**(i+1)%p
    A[n][i] = (a*l[0]+b-l[1])*inv100%p if i==0 else (a*A[n][i-1] + (a*l[i]+b-l[i+1])*inv100)%p
A[n-1][n-1] = 1
A[n][n] = p//(2**15)
A = Matrix(A)
B = A.LLL()
h0 = B[0][-2]
s0 = h0*(2**16)+l[0]
print(s0)
# s0-b = 1483033737693873089096042460610839746772642846474405267737556964198658333296466607424613619372059057716295177556213725041644228019066398600830469791395036
message = ((s0-b)*inverse(a,p))%p
print(long_to_bytes(message))

# b'DRKCTF{a57b63a6-ecf5-46d3-a501-2d359a4fd168}'

花絮：赛场上自己吭哧吭哧造了个格，结果p只要大一点就不能正常工作，一度以为这一题卡界了...最后拿别人的exp一遍过，还好没有错过一血😇

Misc

func_pixels

唉唉，二次元

拿到图片发现左上有一些异常像素，结合题目的func考虑flag像素的分布应该类似函数图像，脚本提取\(y=x^2\)和\(y=x^3\)的像素值，两个融合起来就是flag。

Python
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
from PIL import Image

image_path = 'LEIMU_encoded.png'
image = Image.open(image_path)

str1 = ""
str2 = ""
for i in range(10):
    pixel_value = image.getpixel((i, i**2))
    for j in range(3):
        if (chr(pixel_value[j]).isascii()):
            str1 += chr(pixel_value[j])
        else:
            str1 += " "
print(str1)
# for i in range(10):
#     pixel_value = image.getpixel((i, i))
#     print(f'Linear: {chr(pixel_value[0]), chr(pixel_value[1]), chr(pixel_value[2])}')
for i in range(10):
    pixel_value = image.getpixel((i, i**3))
    for j in range(3):
        if (chr(pixel_value[j]).isascii()):
            str2 += chr(pixel_value[j])
        else:
            str2 += " "
print(str2)

# DRKCTF{H HA AH _L iM Is oC te 
# DRKCTF{ AH HA A_ ei uI So ut }
Writeups
#CTF #Crypto
DragonKnight CTF 2024 Writeup
https://eupho.me/19d8fa37.html
作者
Lambert Swizzer
发布于
2024年5月26日
许可协议