CTF导航 CTF导航

zer0pts 2023 writeup

WriteUp 1年前 (2023) admin
243 0 0

zer0ptsCTF

久しぶりに長時間参加した気がする…

前置き　

Project Sekaiで参加してました。結果は18位なのでomgって感じですね。。。

実際参加してる人が少なかった＋メインの人がほぼいなかったのも大きいんですかね…

代わりにMr godがいましてrevを爆速で全部終わらしてました(強すぎる)

残りは、upsolveしたら追加します。。。

SquareRNG [crypto 54 solve ] (30 minuts)

chall

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

#!/usr/bin/env python3
import os
from Crypto.Util.number import getPrime, getRandomRange

def isSquare(a, p):
    return pow(a, (p-1)//2, p) != p-1

class SquareRNG(object):
    def __init__(self, p, sa, sb):
        assert sa != 0 and sb != 0
        (self.p, self.sa, self.sb) = (p, sa, sb)
        self.x = 0

    def int(self, nbits):
        v, s = 0, 1
        for _ in range(nbits):
            self.x = (self.x + 1) % p
            s += pow(self.sa, self.x, self.p) * pow(self.sb, self.x, self.p)
            s %= self.p
            v = (v << 1) | int(isSquare(s, self.p))
        return v

    def bool(self):
        self.x = (self.x + 1) % self.p
        t = (pow(self.sa, self.x, self.p) + pow(self.sb, self.x, self.p))
        t %= self.p
        return isSquare(t, self.p)

p = getPrime(256)

sb1 = int(input("Bob's seed 1: ")) % p
sb2 = int(input("Bob's seed 2: ")) % p
for _ in range(77):
    sa = getRandomRange(1, p)
    r1 = SquareRNG(p, sa, sb1)
    print("Random 1:", hex(r1.int(32)))
    r2 = SquareRNG(p, sa, sb2)
    print("Random 2:", hex(r2.int(32)))

    guess = int(input("Guess next bool [0 or 1]: "))
    if guess == int(r1.bool()):
        print("OK!")
    else:
        print("NG...")
        break
else:
    print("Congratz!")
    print(os.getenv("FLAG", "nek0pts{*** REDACTED ***}"))

solve

LCG��≡∑�=1�(���∗���)+1mod�の出力に関して(��/�)のルジャンドル記号の値が��が2回入力できることから2つ得られるので、そこから(��33+��33/�)のルジャンドル記号の出力を当てろっていう感じみたいです。

そもそも、ルジャンドル記号はその数�がある素数�において�≡�2mod�となるような�の存在の判定するものです。

ルジャンドル記号には平方剰余の相互法則という(�/�)∗(�/�)=(��/�)があるのでこれを使えたらなーという気持ちで男は黙って因数分解します。

ここで、��33+��33を因数分解しちゃって、��33+��33=(��+��)∗(��2−��∗��+��2)∗(��10−��9∗��+��8∗��2−��7∗��3+��6∗��4−��5∗��5+��4∗��6−��3∗��7+��2∗��8−��∗��9+��10)∗(��20+��19∗��−��17∗��3−��16∗��4+��14∗��6+��13∗��7−��11∗��9−��10∗��10−��9∗��11+��7∗��13+��6∗��14−��4∗��16−��3∗��17+��∗��19+��20)ってなります。めでたく因数分解できた(てか対称式なので当たり前)ので、さっき貰った出力に置き換えていきます。

ここで、最初の項以外をかけわせてしまえば、��32−��31∗��+��30∗��2−��29∗��3+��28∗��4−��27∗��5+��26∗��6−��25∗��7+��24∗��8−��23∗��9+��22∗��10−��21∗��11+��20∗��12−��19∗��13+��18∗��14−��17∗��15+��16∗��16−��15∗��17+��14∗��18−��13∗��19+��12∗��20−��11∗��21+��10∗��22−��9∗��23+��8∗��24−��7∗��25+��6∗��26−��5∗��27+��4∗��28−��3∗��29+��2∗��30−��∗��31+��32=∑�=1�(���+(−��)�)+1

��に−��を代入したときに得られた項の最終項と一致します。さらに残りの��+��は仮に��=1とすると？��+1となりこれは、�1≡��+1mod�と同値なので、��1=1,��2=−1を代入します。そこから結果の1bitを掛け算すると答えが出ます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

from Crypto.Util.number import getPrime, getRandomRange
from pwn import *

io = remote("crypto.2023.zer0pts.com","10666")

io.sendlineafter(b": ",b"1")
io.sendlineafter(b": ",b"-1")
for i in range(77):
    ct1 = eval(io.recvline().decode().split(" ")[-1])
    ct2 = eval(io.recvline().decode().split(" ")[-1])
    ct1 = bin(ct1)[2:].zfill(32)
    ct2 = bin(ct2)[2:].zfill(32)

    ans = (1-(int(ct2[-1])^int(ct1[0])))%2
    io.sendlineafter(b": ",str(int(ans)).encode())
    print(io.recvline())
io.interactive()

# zer0pts{L(a)L(b)=L(ab)}

easy_factoring (coworker solved) [crypto 95 solve ] (?? minuts)

chall

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

import os
import signal
from Crypto.Util.number import *

flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")

def main():
    p = getPrime(128)
    q = getPrime(128)
    n = p * q

    N = pow(p, 2) + pow(q, 2)

    print("Let's factoring !")
    print("N:", N)

    p = int(input("p: "))
    q = int(input("q: "))

    if isPrime(p) and isPrime(q) and n == p * q:
        print("yey!")
        print("Here you are")
        print(flag)
    else:
        print("omg")

def timeout(signum, frame):
    print("Timed out...")
    signal.alarm(0)
    exit(0)

if __name__ == "__main__":
    signal.signal(signal.SIGALRM, timeout)
    signal.alarm(30)
    main()
    signal.alarm(0)

solve???

さっきのLCG解いて休憩したらsahuangパイセンとquasarさんが爆速で解いてました(多分unintend)ので、また今度のupsolveってことで….

�=�2+�2の�,�を求めよということですが、なんということでしょうディオファントス問題(だよね??)

まぁOTOKO HA DAMATTE INSUUBUNKAI �=(�+��)∗(�−��)って感じですね。んで、複素数体自体はUFDだけどその(�+��)自体がさらに因数を持つ可能性があるので因数の積で出るのかなぁ？(知らない)

elliptic_ring_rsa [crypto 27 solve ] (2 hour)

chall

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

import string
import random
import os

flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")

class EllipticRingElement:
	point = None
	def __init__(self, point):
		self.point = point
	
	def __add__(self, other):
		if self.point == dict():
			return other
		if other.point == dict():
			return self
		res = self.point.copy()
		for k in other.point.keys():
			if k in res:
				res[k] += other.point[k]
				if res[k] == 0:
					res.pop(k)
			else:
				res[k] = other.point[k]
				if res[k] == 0:
					res.pop(k)
		return EllipticRingElement(res)
	
	def __mul__(self, other):
		if self.point == dict() or other.point == dict():
			return self.point()
		res = dict()
		for k1 in other.point.keys():
			for k2 in self.point.keys():
				E = k1 + k2
				k = other.point[k1] * self.point[k2]
				if E in res:
					res[E] += k
					if res[E] == 0:
						res.pop(E)
				else:
					res[E] = k
					if res[E] == 0:
						res.pop(E)
		return EllipticRingElement(res)
	
	def __repr__(self):
		st = ""
		for k in self.point.keys():
			st += f"{self.point[k]}*({k[0]}, {k[1]}) + "
		return st[:-3]
	
class EllipticRing:
	E = None
	Base = None
	def __init__(self, E):
		self.E = E
		self.Base = E.base()

	def __call__(self, pt):
		for P in pt:
			pt[P] = self.Base(pt[P])
		return EllipticRingElement(pt)
	
	def zero(self):
		return EllipticRingElement(dict())
	
	def one(self):
		return EllipticRingElement({E(0): self.Base(1)})
	
	def pow(self, x, n):
		res = self.one()
		while n:
			if (n & 1):
				res = res * x
			x = x * x
			n >>= 1
		return res
	
	def encode(self, m, length):
		left = random.randint(0, length - len(m))
		pad1 = "".join(random.choices(string.ascii_letters, k=left)).encode("utf-8")
		pad2 = "".join(random.choices(string.ascii_letters, k=length-len(m)-left)).encode("utf-8")
		m = pad1 + m + pad2

		Ps = []
		while len(Ps) < length:
			PP = self.E.random_element()
			if PP not in Ps:
				Ps.append(PP)
		Ps = sorted(Ps)

		M = dict()
		for coef, pt in zip(m, Ps):
			M[pt] = self.Base(coef)
		return EllipticRingElement(M)
	
def random_prime_bits(nbits):
	return random_prime(2^nbits-1, false, 2^(nbits-1))

nbits = 8
p = random_prime_bits(nbits)
Fp = GF(p)

a = Fp.random_element()
b = Fp.random_element()
E = EllipticCurve(Fp, [a, b])

ER = EllipticRing(E)

P = ER.encode(flag, 30)

e = 13
C = ER.pow(P, e)

print(f"p: {p}")
print(f"C: {C}")
print(f"a: {a}")
print(f"b: {b}")
print(f"e: {e}")

solve

とりあえず楕円は楕円だけど演算が..?て感じなので見ていきます。

なんか�′=�0∗�0+�2∗�2+…+��−1∗��−1って感じの元に見えますねこれ。

掛け算は、多項式の掛け算と同じで�′∗�′=∑�=0�−1∑�=0�−1((��+��)∗��+�)って感じですね。

足し算も、多項式の掛け算と同じで�′+�′=∑�=0�−1(��+��)∗��)って感じ。

乗算における逆元は….�=(1+�1)等が存在しないはず！(理由は後程)

てな感じで多項式環に準同型写像出来そうですねこれ！！

ならこの元全体の集合を�、写像先の集合を�とすると、�:�→�:��↦��っていう多項式への写像を構成することにします。

ここで、�の世界で行われていたことを考えてみると、�という元を構築し、��しているだけです。

ってことで�→rsaのような逆演算→�^ で元に戻ります。

STEP1 写像の作成

とりあえず基準となる�∈�を探します(位数は最大のもの)、それを使って写像します。

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

def plus2dict(_C):
    cc = dict()
    _C = _C.split(" + ")
    for c in _C:
        if c.split("*")[1] == "(0, 1)":
            cc[E(0)] = c.split("*")[0]
        else:
            cc[E(eval(c.split("*")[1]))] = c.split("*")[0]
    _C = cc
    return _C

PR.<x> = PolynomialRing(GF(p))
gen = x^192-1
QR.<x> = QuotientRing(PR, gen)

while True:
    g = E.random_element()
    if g.order() == r:
        break
    
def ec2vec(g,_C):
    vec = 0
    for i in range(0,r):
        try:
            vec += (int(_C[g*i])*x^i)
        except KeyError as e:
            continue
    return vec

C = plus2dict(C)
C = ec2vec(g,C)

これでおしまい。

PART2 rsa likeな復号

�′∈�から�″∈�に写像できたので、�について考えます。

��[�]/(�192−1)という群構造を持ちます。ここで、�192−1は因数分解できてしまい、規約多項式にはなりませんので拡大体にはならないのですべての元が乗法での逆元を持ちません。((�+1)|�192−1より逆元を持たない、かつさっきの写像を考えると…)

よって、�は多項式環になるので多項式環のrsaの復号を考えます。

略しますが、位数は��−1の約数なことが知られていています。ここで、Men must keep their mouths shut and factorizeすると�|��−1といういやーな感じですが、位数的には�″��−1//�≡1mod�で問題なかったのでよしとします。

よって、通常のRSAっぽく�=�−1mod(��−1)//�として、�″≡�″�mod�で最終的に復号できます。

1
2
3

d = int(pow(13,-1,(p^192-1)//13))
print((C^d))
m = str(C^d)

PART3 逆写像

最後に逆写像して終わりです。

最初に求めた�を基準にして逆写像していきます。

1
2
3
4
5
6

ms = []
ps = []
for i in m.split(" + ")[:-1]:
    g_tmp = g*int(i.split("^")[1])
    ms.append([g_tmp,chr(int(i.split("*")[0]))])
    ps.append(g_tmp)

これで、最後にソートして順に係数を文字に起こしてやるとflagが求まります。

写像考えるのまじで楽しかったです。あと、これはそれなりに実行速度早いはず..??(知らんけど)

ってことで、これの想定解が気になるところ…??

1
2
3
4
5
6
7
8

ps_ori = str([i.xy() for i in ps])
ps_sort = sorted(ps)
print(ps_ori)
ps_ori = [E(i) for i in eval(ps_ori)]
for i in range(len(ps_sort)):
    num = ps_ori.index(ps_sort[i])
    print(ms[num][1],end="")
# zer0pts{Gr0up_r1ng_meow!!}


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

C = "182*(91, 45) + 147*(3, 164) + 85*(62, 60) + 53*(77, 59) + 99*(77, 152) + 18*(137, 59) + 106*(169, 101) + 147*(127, 127) + 154*(152, 163) + 121*(43, 73) + 155*(110, 160) + 202*(116, 45) + 195*(1, 84) + 106*(71, 162) + 33*(209, 122) + 112*(134, 164) + 186*(1, 127) + 72*(183, 116) + 141*(141, 39) + 72*(83, 127) + 157*(197, 175) + 6*(178, 24) + 106*(71, 49) + 114*(57, 201) + 95*(181, 58) + 1*(174, 44) + 193*(202, 27) + 182*(121, 95) + 52*(167, 179) + 109*(184, 177) + 110*(21, 162) + 101*(126, 170) + 208*(47, 102) + 168*(129, 105) + 209*(179, 123) + 210*(160, 70) + 10*(13, 103) + 159*(76, 55) + 165*(31, 26) + 31*(44, 119) + 47*(6, 70) + 150*(74, 47) + 117*(30, 65) + 3*(108, 69) + 61*(43, 138) + 151*(72, 209) + 122*(110, 51) + 127*(44, 92) + 64*(191, 113) + 61*(45, 70) + 155*(91, 166) + 175*(95, 194) + 97*(21, 49) + 210*(66, 191) + 129*(129, 106) + 210*(80, 7) + 157*(174, 167) + 45*(141, 172) + 189*(155, 78) + 160*(194, 1) + 209*(82, 28) + 142*(164, 136) + 135*(199, 155) + 166*(118, 95) + 100*(123, 14) + 203*(121, 116) + 22*(36, 20) + 33*(65, 58) + 196*(189, 60) + 75*(137, 152) + 22*(125, 4) + 45*(119, 162) + 59*(47, 109) + 102*(177, 157) + 196*(109, 20) + 112*(192, 94) + 97*(209, 89) + 67*(95, 17) + 129*(75, 55) + 34*(134, 47) + 156*(60, 156) + 135*(127, 84) + 11*(148, 147) + 194*(202, 184) + 27*(45, 141) + 131*(4, 166) + 166*(148, 64) + 183*(164, 75) + 177*(130, 145) + 128*(107, 8) + 204*(156, 40) + 131*(17, 25) + 99*(177, 54) + 122*(82, 183) + 52*(178, 187) + 130*(168, 19) + 14*(150, 150) + 173*(167, 32) + 82*(184, 34) + 172*(72, 2) + 144*(169, 110) + 7*(118, 116) + 96*(181, 153) + 34*(133, 5) + 97*(207, 17) + 24*(78, 161) + 54*(57, 10) + 90*(143, 188) + 172*(130, 66) + 179*(146, 65) + 38*(55, 202) + 170*(63, 31) + 99*(35, 65) + 162*(150, 61) + 56*(74, 164) + 146*(144, 85) + 196*(133, 206) + 164*(152, 48) + 139*(176, 153) + 92*(125, 207) + 124*(31, 185) + 136*(0, 1) + 118*(107, 203) + 28*(24, 56) + 66*(171, 151) + 127*(76, 156) + 63*(208, 59) + 187*(146, 146) + 138*(85, 0) + 195*(19, 190) + 115*(60, 55) + 87*(171, 60) + 194*(17, 186) + 79*(75, 156) + 181*(27, 37) + 38*(192, 117) + 168*(13, 108) + 41*(143, 23) + 167*(199, 56) + 177*(86, 71) + 160*(35, 146) + 165*(189, 151) + 130*(32, 30) + 39*(108, 142) + 197*(36, 191) + 176*(120, 17) + 180*(194, 210) + 204*(19, 21) + 160*(6, 141) + 195*(109, 191) + 194*(155, 133) + 62*(65, 153) + 6*(138, 107) + 12*(201, 62) + 43*(180, 43) + 178*(208, 152) + 86*(180, 168) + 135*(55, 9) + 5*(138, 104) + 118*(207, 194) + 58*(160, 141) + 173*(66, 20) + 16*(179, 88) + 181*(61, 131) + 3*(80, 204) + 137*(119, 49) + 106*(126, 41) + 127*(176, 58) + 64*(144, 126) + 96*(30, 146) + 165*(168, 192) + 104*(27, 174) + 64*(63, 180) + 35*(123, 197) + 111*(86, 140) + 141*(197, 36) + 83*(116, 166) + 159*(4, 45) + 165*(62, 151) + 94*(183, 95) + 133*(3, 47) + 58*(83, 84) + 149*(201, 149) + 96*(20, 112) + 141*(191, 98) + 113*(24, 155) + 139*(61, 80) + 73*(120, 194) + 116*(78, 50) + 68*(156, 171) + 31*(32, 181)"
p = 211
a = 201
b = 102
e = 13
r = 192 # E.order()
E = EllipticCurve(GF(p),[a,b])

def plus2dict(_C):
    cc = dict()
    _C = _C.split(" + ")
    for c in _C:
        if c.split("*")[1] == "(0, 1)":
            cc[E(0)] = c.split("*")[0]
        else:
            cc[E(eval(c.split("*")[1]))] = c.split("*")[0]
    _C = cc
    return _C

PR.<x> = PolynomialRing(GF(p))
gen = x^192-1
QR.<x> = QuotientRing(PR, gen)

while True:
    g = E.random_element()
    if g.order() == r:
        break
print("[+] REFERNCE POINT",g)
    
def ec2vec(g,_C):
    vec = 0
    for i in range(0,r):
        try:
            vec += (int(_C[g*i])*x^i)
        except KeyError as e:
            continue
    return vec

C = plus2dict(C)
C = ec2vec(g,C)
d = int(pow(13,-1,(p^192-1)//13))
print("[+] AFTER DECRYPT",C^d)
m = str(C^d)

ms = []
ps = []
for i in m.split(" + ")[:-1]:
    g_tmp = g*int(i.split("^")[1])
    ms.append([g_tmp,chr(int(i.split("*")[0]))])
    ps.append(g_tmp)
    
print("[+] AFTER INVERSE MAPPING",ps)

ps_ori = str([i.xy() for i in ps])
ps_sort = sorted(ps)
ps_ori = [E(i) for i in eval(ps_ori)]
print("[+] FLAG : ",end="")
for i in range(len(ps_sort)):
    num = ps_ori.index(ps_sort[i])
    print(ms[num][1],end="")

# zer0pts{Gr0up_r1ng_meow!!}

 

原文始发于kanon：zer0pts 2023 writeup

版权声明：admin 发表于 2023年7月25日 上午9:13。
转载请注明：zer0pts 2023 writeup | CTF导航

相关文章

paradigm 2022 ctf ——Rescue
admin
50
【WriteUP·上篇】2024WIDC世界智能驾驶挑战赛“天融信杯”信息安全攻防赛
admin
56
【2024春节】解题领红包之web题writeup
admin
55
伽玛实验场 | PDC面壁计划管理系统-出题人视角
admin
1,116
RWCTF 5th ShellFind Write-up
admin
539
第七届蓝帽杯全国大学生网络安全技能大赛初赛Writeup
admin
396

暂无评论

您必须登录才能参与评论！
立即登录
暂无评论...

相关文章

Intigriti CTF 2024 by Mini-Venom
0
N1CTF24 PHP Master Writeup
0
网鼎杯青龙组的 PWN03 Jerryscript 题目
0
2024 网鼎杯 青龙&白虎
0
2024鹏程杯 writeup by Mini-Venom
0
关于40小时做出prpr而强网杯32小时这件事
0
web选手入门pwn(22) ——网鼎杯PWN02(vfork)
0
2024第四届“网鼎杯”玄武组 writeup
0
2024龙信杯电子数据取证竞赛-计算机取证题目Writeup
0
2024第四届“网鼎杯”朱雀组 writeup
0