K3RN3L CTF 2021 WriteUps

發表於 分類於

這個 CTF 我是只有在有空的時候才去解點 Crypto 題目的，因為有不少有趣的題目所以還是紀錄一下。這次用的隊伍名是 peko，31 名。

Pryby

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
from Crypto.Util.number import bytes_to_long 
def f(n):
    q=[True]*(n + 1)
    r=2
    while r**2<=n:
        if q[r]:
            for i in range(r**2,n+1,r):q[i] = False
        r += 1
    return [p for p in range(2,n+1) if q[p]]
class G:
    def __init__(self, f):
        self.f = f
        self.state = 1
    def move(self):
        q=1
        for p in self.f:
            if self.state%p!=0:
                self.state=self.state*p//q
                return
            q*=p
flag = open('flag.txt','r').read().strip().encode()
flag=bytes_to_long(flag)
gen = G(f(pow(10,6)))
for _ in range(flag):gen.move()
print('enc =',gen.state)
# enc = 31101348141812078335833805605789286074261282187811930228543150731391596197753398457711668323158766354340973336627910072170464704090430596544129356812212375629361633100544710283538309695623654512578122336072914796577236081667423970014267246553110800667267853616970529812738203125516169205531952973978205310

可以看出它是拿質數作為 binary 表示，所以就分解開然後恢復 bits 得到 flag:

1
2
3
4
5
6
7
8
fs = [
    a
    for a, b in factor(
        31101348141812078335833805605789286074261282187811930228543150731391596197753398457711668323158766354340973336627910072170464704090430596544129356812212375629361633100544710283538309695623654512578122336072914796577236081667423970014267246553110800667267853616970529812738203125516169205531952973978205310
    )
]
ps = list(primes(1500))
print(int(sum([1 << ps.index(x) for x in fs])).to_bytes(100, "big"))

Pascal RSA

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
triangle =[[1]]
flag = open('flag.txt','rb').read()

from Crypto.Util.number import getPrime,bytes_to_long
from math import gcd
p = getPrime(20)
while len(triangle[-1]) <= p:
    r = [1]
    for i in range(len(triangle[-1]) - 1):
        r.append(triangle[-1][i] + triangle[-1][i+1])
    r.append(1)
    triangle.append(r)
code = ''
for x in triangle[-1]:
    code+=str(x%2)
d = int(code,2)
while True:
    P = getPrime(512)
    Q = getPrime(512)
    if gcd(d, (P-1)*(Q-1)) == 1:
        N = P*Q
        e = pow(d,-1,(P-1)*(Q-1))
        break
enc = pow(bytes_to_long(flag), e, N)
file = open('challenge.txt','w')
file.write(f'p = {p}\nenc = {enc}\nN = {N}')

這題 RSA 的 是使用一個帕斯卡三角形的第 層模 2 之後的 binary representation 所得到的，查一下相關資訊可以找到 Sierpiński's triangle，而它轉換為數字的數列在 OEIS 上也有: A001317

所以用它裡面給的通項公式求出 之後就有 flag 了:

1
2
3
4
5
6
7
8
9
10
# https://oeis.org/A001317
p = 751921
d = 1
for _ in range(p):
    d ^= 2 * d

c = 9820620269072860401665805101881284961421302475382405373888746780467409082575009633494008131637326951607592072546997831382261451919226781535697132306297667495663005072695351430953630099751335020192098397722937812151774786232707555386479774460529133941848677746581256792960571286418291329780280128419358700449
n = 84317137476812805534382776304205215410373527909056058618583365618383741423290821410270929574317899945862949829480082811084554009265439540307568537940249227388935154641779863441301292378975855625325375299980291629608995049742243591901547177853086110999523167557589597375590016312480342995048934488540440868447
m = pow(c, d, n)
print(m.to_bytes(128, "big"))

Poly Expo go BRRRRR

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
#!/usr/bin/env sage
#
# Polymero
#

from Crypto.Util.number import getPrime

with open('flag.txt','rb') as f:
    FLAG = f.read()
    f.close()

n = getPrime(512) * getPrime(512)
e = 0x10001

P.<x> = PolynomialRing(GF(2))
N = sum([int(j)*x**i for i,j in enumerate('{:0{bl}b}'.format(n,bl=n.bit_length()))])
Q.<x> = P.quotient(N)

def encrypt(msg):
    if type(msg) == bytes:
        msg = int.from_bytes(msg,'big')
    msg = sum([int(j)*x**i for i,j in enumerate('{:0{bl}b}'.format(msg,bl=n.bit_length()-1))])
    cip = Q(msg)**e
    cip = int(''.join([str(i) for i in list(cip)]),2)
    return cip

c = encrypt(FLAG)

print('n =',n)
print('e =',e)
print('c =',c)

assert solve()

#
# n = 119688104315557021890936576297322528053073582644938225605833562855944546643311189725353580415278613605803528999976536949698525581164157480218289586687945087549976509446759942778609918817975151644563678567137671925049937536315926169828583738712154203276012477308556625213229949900385215601055758028238785190211
# e = 65537
#
# c = 59180475538014020769986137847579404920412136380976726613826924727288568855214946199702335444771145318394201684142700441287649150098774979773106915707593238156979003572684188994666984941867671144226245449471326607224512384706414018555885923177955268177207582929765645093722741174664225408159262482249199006862
#

這題看起來像是 RSA，只是 被轉換到 的一個多項式 ，之後的運算都在 下運算。flag 本身也是轉換到那個 ring 之下的多項式之後開 次方加密後再轉回數字。

可以發現 本身是可以分解的，所以要找個方法求出它的 order 後拿到 解密即可。查一下資料可以在這邊找到公式。

對於 底下 degree 的 irreducible polynomial 來說

然後還有對於任意多項式都有

有兩個關係之後就足夠計算出 ，之後再求 即可解密。

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
n = 119688104315557021890936576297322528053073582644938225605833562855944546643311189725353580415278613605803528999976536949698525581164157480218289586687945087549976509446759942778609918817975151644563678567137671925049937536315926169828583738712154203276012477308556625213229949900385215601055758028238785190211
e = 65537
c = 59180475538014020769986137847579404920412136380976726613826924727288568855214946199702335444771145318394201684142700441287649150098774979773106915707593238156979003572684188994666984941867671144226245449471326607224512384706414018555885923177955268177207582929765645093722741174664225408159262482249199006862

P.<x> = PolynomialRing(GF(2))
N = sum(
    [
        int(j) * x ** i
        for i, j in enumerate("{:0{bl}b}".format(n, bl=int(n).bit_length()))
    ]
)
Q.<x> = P.quotient(N)

# https://pointloma.whdl.org/sites/default/files/Freed-RSA%20Encryption%20Using%20Polynomial%20Rings-HP.pdf
# 4.5
# For a irreducible polynomial f(x) over F_p
# phi(f(x)^n)=p^((deg f(x))*n)-p^((deg(f(x)))*(n-1))
# phi(f(x)*g(x))=phi(f(x))*phi(g(x)) holds too
phi = product(
    [2 ** (poly.degree() * n) - 2 ** (poly.degree() * (n - 1)) for poly, n in N.factor()]
)
d = inverse_mod(e, phi)
c = sum(int(a) * x ^ i for i, a in enumerate(bin(c)[2:]))
m = c ^ d
print(int("".join([str(i) for i in list(m)]), 2).to_bytes(100, "big"))

1-800-758-6237

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
#!/usr/bin/env python3
#
# Polymero
#

# Imports
from Crypto.Cipher import AES
import os, time, random

# Local imports
with open('flag.txt', 'rb') as f:
	FLAG = f.read()
	f.close()


def leak(drip):
	rinds = sorted(random.sample(range(len(drip)+1), 16))

	for i in range(len(rinds)):
		ind  = rinds[i] + i*len(b'*drip*')
		drip = drip[:ind] + b'*drip*' + drip[ind:]

	aes = AES.new(key=server_key, mode=AES.MODE_CTR, nonce=b'NEEDaPLUMBER')
	return aes.encrypt(drip).hex()


server_key = os.urandom(16)

while True:

	print(leak(FLAG))

	time.sleep(1)

很明顯的是 AES-CTR nonce reuse，代表所有的 message 都是 xor 某個相同的 key stream 加密的。首先可以先存個大概 100 筆 ciphertext 下來比較好處理。

leak 函數就是在你的 flag 的一些任意 index 插入 *drip* 這個字串，所以明文中肯定也有許多的 *drip* 出現。

所以先假設說其中至少有一筆 ciphertext 的明文是 flag{ 開頭，由此可以還原出 key stream 的前面五個 bytes。(會有多個 candidates)

之後對於剩下的部分就利用 *drip 後面一定是 * 和 *dri 後面是 p 這兩個去一個一個把剩下的 key stream 還原即可。

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 itertools import combinations
import string


def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))


data = []
with open("output.txt") as f:
    for line in f:
        data.append(bytes.fromhex(line))

good = set(map(ord, string.ascii_letters + string.digits + " {}_*:!"))

kss = set()
flag = b"flag{"
dt = {}
for a, b in combinations(data, r=2):
    tmp = xor(xor(a, b), flag)
    if all(x in good for x in tmp) and xor(a, flag) == xor(b, flag):
        kss.add(xor(a, flag))

for k in kss:
    for _ in range(200):
        for i, ct in enumerate(data):
            pt = xor(k, ct)
            r = pt.replace(b"*drip*", b"")
            if pt.endswith(b"*drip"):
                k = xor(pt + b"*", ct)
                break
            if pt.endswith(b"*dri"):
                k = xor(pt + b"p", ct)
                break
        else:
            break
        if not all(x in good for x in r):
            break
        print(r)

# flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}

Poly-Proof

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
#!/usr/bin/env python3
#
# Polymero
#

# Imports
import os

# Local imports
with open('flag.txt','rb') as f:
    FLAG = f.read()
    f.close()

HDR = r"""|
|    ________  ________  ___           ___    ___      ________  ________  ________  ________  ________ 
|   |\   __  \|\   __  \|\  \         |\  \  /  /|    |\   __  \|\   __  \|\   __  \|\   __  \|\  _____\
|   \ \  \|\  \ \  \|\  \ \  \        \ \  \/  / /    \ \  \|\  \ \  \|\  \ \  \|\  \ \  \|\  \ \  \__/ 
|    \ \   ____\ \  \\\  \ \  \        \ \    / /      \ \   ____\ \   _  _\ \  \\\  \ \  \\\  \ \   __\
|     \ \  \___|\ \  \\\  \ \  \____    \/  /  /        \ \  \___|\ \  \\  \\ \  \\\  \ \  \\\  \ \  \_|
|      \ \__\    \ \_______\ \_______\__/  / /           \ \__\    \ \__\\ _\\ \_______\ \_______\ \__\ 
|       \|__|     \|_______|\|_______|\___/ /             \|__|     \|__|\|__|\|_______|\|_______|\|__| 
|                                    \|___|/                                
|"""

class Server:
    def __init__(self, difficulty):
        self.difficulty = difficulty
        self.coefficients = None
        self.limit = 8
        self.i = 0
        self.set_up()
        
    def _eval_poly(self, x):
        return sum([ self.coefficients[i] * x**i for i in range(len(self.coefficients)) ])
    
    def _prod(self, intlst):
        ret = 1
        for i in intlst:
            ret *= i
        return ret
        
    def set_up(self, verbose=False):
        print(HDR)
        print("|  To prove to you that I own the flag, I used it to make a polynomial. Challenge me all you want!")
        noise = [ self._prod(list(os.urandom(self.difficulty))) for i in range(len(FLAG)) ]
        self.coefficients = [ noise[i] * FLAG[i] for i in range(len(FLAG)) ]
        
    def accept_challenge(self):
        print("|\n|  Name your challenge (as ASCII string):")
        try:
            user_input = int.from_bytes(str(input("|   >> ")).encode(),'big')
        except ValueError:
            print("|\n|  ERROR - That ain't working... s m h ")
            return
        if user_input == 0:
            print("|\n|  ERROR - You clearly don't know what ZERO-KNOWLEDGE means eh?")
            return
        if user_input <= 0:
            print("|\n|  ERROR - Your clever tricks will not work here, understood?")
            return
        print("|\n|  Here's my commitment: {}".format(self._eval_poly(user_input)))
        self.i += 1
        
    def run(self):
        while self.i < self.limit:
            try:
                self.accept_challenge()
            except:
                break
        if self.i >= self.limit:
            print("|\n|   Are you trying to steal my polynomial or something?")
            print("|   I think I have proven enough to you...")
        print("|\n|\n|  ~ See you back in polynomial time! o/ \n|")


S = Server(15)
S.run()

這題會先把 flag 的每個字元乘上一些 noise 得到多項式係數 。然後你可以輸入 去得到 ，重複 8 次。

第一個目標是要還原出多項式係數，一個最簡單的做法就是取 ，然後把 以 進位表示出來就能拿到 。

不過我當時卻沒想到這個，反而用了一個複雜很多的作法:

取一個夠大的常數 之後做 LLL 可以找到一個短向量 獲得多項式的係數。

取得多項式係數後也沒辦法直接拿到 flag，但是因為 ，其中的 和 分別是 noise 和 flag。所以就拿多組的 之後取 gcd 就有機會拿到 。

不過實際上只能拿到 的倍數，非常難以得到真正的 ，所以這邊需要利用 flag 本身可能的字元範圍去猜可能的 ，之後再 guess flag 是什麼東西。因為 flag 本身是 leetspeak 所以有點難猜...

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
from pwn import remote, process
import string
import random


def get_pair(io):
    r = "".join(random.sample(string.ascii_letters, 16)).encode()
    io.sendlineafter(b"|   >> ", r)
    r = int.from_bytes(r, "big")
    io.recvuntil(b"commitment: ")
    fr = int(io.recvlineS().strip())
    return r, fr


def get_params():
    io = remote("ctf.k3rn3l4rmy.com", 2232)
    pairs = [get_pair(io) for _ in range(8)]
    io.close()
    rs, frs = zip(*pairs)
    return rs, frs


def solve_coefs(rs, frs, n):
    assert len(rs) == 8
    M = matrix([[r ^ i for i in range(n)] for r in rs]).T
    M = M.augment(matrix.identity(n))
    M = matrix([-fr for fr in frs] + [0] * n).stack(M)
    M[:, :8] *= 2 ^ 128

    for row in M.LLL():
        if all(x == 0 for x in row[:8]):
            return row[8:]


def find_possible(x):
    flagchrs = ("{_}" + string.ascii_lowercase + string.digits).encode()
    return [y for y in flagchrs if x % y == 0]


n = 101  # flag length
# flag = [0] * n
# fmt: off
flag = [408, 648, 776, 206, 984, 872, 416, 484, 1176, 204, 1520, 792, 968, 396, 432, 204, 380, 968, 192, 234, 2736, 190, 460, 408, 1584, 456, 204, 232, 920, 380, 104, 220, 800, 190, 920, 52, 220, 196, 464, 588, 488, 408, 1140, 484, 96, 234, 1368, 760, 196, 220, 448, 936, 464, 920, 190, 96, 5472, 2280, 832, 832, 460, 380, 464, 832, 196, 460, 380, 448, 2496, 1320, 800, 204, 436, 196, 396, 760, 880, 192, 928, 760, 464, 208, 936, 412, 416, 464, 190, 968, 192, 936, 380, 208, 440, 242, 1392, 2496, 294, 880, 2472, 500, 240]
# fmt: on
while True:
    rs, frs = get_params()
    noiseflag = solve_coefs(rs, frs, n)
    for i in range(n):
        flag[i] = gcd(flag[i], noiseflag[i])
    print(flag)
    fflag = [
        "".join(map(chr, p)) if len((p := find_possible(x))) <= 5 else x for x in flag
    ]
    print(fflag)
    if all(0 <= x < 256 for x in flag):
        print(bytes(flag))
        break

# by guessing leetspeak...
# flag{m4yb3_cycl3_y0ur_s3cr3ts_4nd_s4n1t1z3_y0ur_1nputs_0r_h4s_th1s_p4nd3m1c_n0t_t4ught_y0u_4nyth1ng}

Non-Square Freedom 1

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
#!/usr/bin/env python3
#
# Polymero
#

# Imports
from Crypto.Util.number import getPrime
import os

# Local imports
with open('flag.txt','rb') as f:
    FLAG = f.read()
    f.close()

# Key gen
P = getPrime(512//8)
Q = getPrime(256)
R = getPrime(256)
N = P**8 * Q * R
E = 0x10001

def pad_easy(m):
    m <<= (512//8)
    m += (-(m % (P**2)) % P)
    return m

# Pad FLAG
M = pad_easy(int.from_bytes(FLAG,'big'))
print('M < N    :',M < N)
print('M < P**8 :',M < (P**8))
print('M < Q*R  :',M < (Q*R))

# Encrypt FLAG
C = pow(M,E,N)
print('\nn =',N)
print('e =',E)
print('c =',C)

# Hint
F = P**7 * (P-1) * (Q-1) * (R-1)
D = inverse(E,F)
print('\nD(C) =',pow(C,D,N))

#----------------------------------------------------
#                       Output
#----------------------------------------------------
# M < N    : True
# M < P**8 : True
# M < Q*R  : True
#
# n = 68410735253478047532669195609897926895002715632943461448660159313126496660033080937734557748701577020593482441014012783126085444004682764336220752851098517881202476417639649807333810261708210761333918442034275018088771547499619393557995773550772279857842207065696251926349053195423917250334982174308578108707
# e = 65537
# c = 4776006201999857533937746330553026200220638488579394063956998522022062232921285860886801454955588545654394710104334517021340109545003304904641820637316671869512340501549190724859489875329025743780939742424765825407663239591228764211985406490810832049380427145964590612241379808722737688823830921988891019862
#
# D(C) = 58324527381741086207181449678831242444903897671571344216578285287377618832939516678686212825798172668450906644065483369735063383237979049248667084304630968896854046853486000780081390375682767386163384705607552367796490630893227401487357088304270489873369870382871693215188248166759293149916320915248800905458
#

一個奇怪的 RSA，令 D(C) 為 之後可以知道 ，但是 。

可以從 padding 函數觀察到 ，所以從 會拿到 ，之後可以拿到 。把 模 之後就很神奇的得到的我們要的 。

其實我也不太清楚這題究竟是怎麼回事...。詳細的解釋可以看作者的 WriteUp。

Tick Tock

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#!/usr/bin/env python3
#
# Polymero
#

# Imports
from Crypto.Util.number import getPrime, isPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from random import randint
from hashlib import sha256


# Local imports
with open('flag.txt','rb') as f:
    FLAG = f.read()
    f.close()

assert len(FLAG) % 8 == 0


# Helper functions
def legendre_symbol(a, p):
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls

def modular_sqrt(a, p):
    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return p
    elif p % 4 == 3:
        return pow(a, (p + 1) // 4, p)
    s = p - 1
    e = 0
    while s % 2 == 0:
        s //= 2
        e += 1
    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1
    x = pow(a, (s + 1) // 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e
    while True:
        t = b
        m = 0
        for m in range(r):
            if t == 1:
                break
            t = pow(t, 2, p)
        if m == 0:
            return x
        gs = pow(g, 2 ** (r - m - 1), p)
        g = (gs * gs) % p
        x = (x * gs) % p
        b = (b * g) % p
        r = m


# TickTock class
class TickTock:
    def __init__(self, x, y, P):
        self.x = x
        self.y = y
        self.P = P
        assert self.is_on_curve()
        
    def __repr__(self):
        return '({}, {}) over {}'.format(self.x, self.y, self.P)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y and self.P == other.P
        
    def is_on_curve(self):
        return (self.x*self.x + self.y*self.y) % self.P == 1
    
    def add(self, other):
        assert self.P == other.P
        x3 = (self.x * other.y + self.y * other.x) % self.P
        y3 = (self.y * other.y - self.x * other.x) % self.P
        return self.__class__(x3, y3, self.P)
    
    def mult(self, k):
        ret = self.__class__(0, 1, self.P)
        base = self.__class__(self.x, self.y, self.P)
        while k:
            if k & 1:
                ret = ret.add(base)
            base = base.add(base)
            k >>= 1
        return ret

def lift_x(x, P, ybit=0):
    y = modular_sqrt((1 - x*x) % P, P)
    if ybit:
        y = (-y) % P
    return TickTock(x, y, P)

def domain_gen(bits):
    while True:
        q = getPrime(bits)
        if isPrime(4*q + 1):
            P = 4*q + 1
            break
    while True:
        i = randint(2, P)
        try:
            G = lift_x(i, P)
            G = G.mult(4)
            break
        except: continue
    return P, G

def key_gen():
    sk = randint(2, P-1)
    pk = G.mult(sk)
    return sk, pk

def key_derivation(point):
    dig1 = sha256(b'x::' + str(point).encode()).digest() 
    dig2 = sha256(b'y::' + str(point).encode()).digest() 
    return sha256(dig1 + dig2 + b'::key_derivation').digest()


# Challenge
flagbits = [FLAG[i:i+len(FLAG)//8] for i in range(0,len(FLAG),len(FLAG)//8)]

for i in range(8):

    print('# Exchange {}:'.format(i+1))

    P, G = domain_gen(48)

    print('\nP =', P)
    print('G = ({}, {})'.format(G.x, G.y))

    alice_sk, alice_pk = key_gen()
    bobby_sk, bobby_pk = key_gen()

    assert alice_pk.mult(bobby_sk) == bobby_pk.mult(alice_sk)

    print('\nA_pk = ({}, {})'.format(alice_pk.x, alice_pk.y))
    print('B_pk = ({}, {})'.format(bobby_pk.x, bobby_pk.y))

    key = key_derivation(alice_pk.mult(bobby_sk))
    cip = AES.new(key=key, mode=AES.MODE_CBC)
    enc = cip.iv + cip.encrypt(pad(flagbits[i], 16))

    print('\nflagbit_{} = "{}"'.format(i+1, enc.hex()))
    print('\n\n\n')

這題有個在一個特殊 group 上的 diffie hellman，需要解開上面的 DLP 才能拿到 key 去解密 flag。

此題因為是在 writeup submission 的範圍中，大概 11/17 的時候我才能公開這題的解法。

*MathyOracle

比賽中沒解，後來看到解法覺得值得解

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
print('Find my number N, and I will give you the flag.')
def f(N,k):
    while min(N,k)>0:
        if k>N: N,k = k,N
        N%=k
    return max(N,k)
import random
N = random.getrandbits(512)
for i in range(600):
    print(f"Try #{i+1}: ")
    k = input(f'Enter k: ')
    l = input(f'Enter l: ')
    try:
        k= int(k)
        assert 0<k<pow(10,500)
        l= int(l)
        assert 0<l<pow(10,500)
    except:
        print('Invalid input. Exiting...')
        quit()
    print(f'f(N+l,k) = {f(int(N+l),k)}\n')
guess = input('What is N?')
if str(N)==guess:
    print(open('flag.txt').read().strip())
else:
    print('Wrong answer. The number was '+str(N))

簡單來說有個 ，然後你可以指定任意 讓它計算 ，目標要在 600 次的 query 內把 還原才行。

如果可以 的話那麼一次就能取得 ，因為 。

這題的題目介紹有說 My friend told me I need LSB to solve this, but I don't do drugs! Can you solve it for me instead?，關鍵在於 LSB 的部份。

的時候可以知道 的 parity，也就是能拿到 的 LSB。有 LSB 的時候可以透過改 把 的已知部分都清成 ，然後 就能取得第二個 bit，這樣以此類推即可。

只是這個方法會遇到的問題是 ，不過只要把方法稍微小改一下即可。假設目前已知 的底下 個 bits ，目前想知道的是第 bits，那取 的話 的第 就會被 flip。

假設原本第 個 bits 是 ，那麼 的 lowest bits 都會是 0，反之只有 bits 是 0。所以取 時如果 就代表 bit 是 1，反之為 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from pwn import process

io = process(["python", "main.py"])


def get(k, l):
    io.sendlineafter(b"k: ", str(k).encode())
    io.sendlineafter(b"l: ", str(l).encode())
    io.recvuntil(b"= ")
    return int(io.recvlineS().strip())


n = 0
for i in range(600):
    l = (1 << i) - n
    k = 1 << (i + 1)
    if get(k, l) == k:
        n += 1 << i
    print(n)

io.sendlineafter(b"N?", str(n).encode())
print(io.recvlineS())

另解

這個是在 Discord 中看到的不同作法，取 ，然後對於 到 都計算 。如果 可以被某個質數 整除的話就知道 ，蒐集到很多的等式之後 CRT 求出答案。