Crypto CTF 2021 WriteUps

發表於 分類於

這次在 AIS3 還在進行的期間中參加了 Crypto CTF 2021 拿了第 19 名，比賽時間也只有 24hr 所以也只解掉了其中中等難度以下的題目而已。不過就算時間再給多一點，我可能頂多再多解個 1~2 題而已。

題目名稱上有 * 的題目代表是我賽後才解的。

easy

Farm

他的 key 是 中的任意 14 個元素相乘而出的結果，然後加密的部分是先把 flag 用 base64 encode 之後轉換為 的元素，然後把每個元素都和 key 相乘之後再 轉換回 base64 的字元成為密文。

解法其實就爆破 64 個 key，看哪一個 key 可以轉換回正常的 base64。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import string, base64

ALPHABET = string.printable[:62] + "\\="
F = list(GF(64))

enc = "805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj"

for key in F[1:]:
    flag = ""
    for c in enc:
        i = ALPHABET.index(c)
        ii = F.index(F[i] / key)
        flag += ALPHABET[ii]
    if flag.endswith("=="):
        print(base64.b64decode(flag))
        break

其實就如 flag 所說的，這個也只是 substitution cipher，只是是在 finite field 中的版本而已。

KeyBase

這題是個 AES-CBC 的題目。首先題目會給你用一組固定 key 和 IV 加密的 flag，然後還有個 oracle 可以讓你提供任意 32 bytes 的明文去用同一組 key 和 IV 加密。用 oracle 加密完後他會給你 key 的前面 14 bytes，以及 ciphertext 的第二個 block (後 16 bytes)。

首先是 key 的前 14 bytes 是已知的，所以只要暴力 65536 種組合就有一個是 key，所以可把 key 當成已知的，不過題目關鍵在於我們並不知道 IV。獲得 IV 的方法是透過 oracle 去加密已知明文，然後爆破 key 去解密密文的第二個 block，之後和明文的第二個 block xor 之後會得到第一個 block 的密文。一樣，有第一個 block 的明文和密文結合爆破 key 可以逆推出 IV，然後有 IV 和 key 就可以解 flag 了。

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
from Crypto.Cipher import AES
import string

enc_flag = bytes.fromhex(
    "96bacca946f4b43a9c1ea88f7213ff002ada02e260b4378b983f312aa451fe36"
)
key_prefix = bytes.fromhex("c006db7407cb60af7d599a85bb8e")
pt = b"aaaabbbbaaaabbbb"
ct = bytes.fromhex("6f380eea6c17a694780bf694ac8341b3")


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


def encrypt(msg, iv, key):
    aes = AES.new(key, AES.MODE_CBC, iv)
    return aes.encrypt(msg)


def decrypt(enc, iv, key):
    aes = AES.new(key, AES.MODE_CBC, iv)
    return aes.decrypt(enc)


def decrypt_ecb(enc, key):
    aes = AES.new(key, AES.MODE_ECB)
    return aes.decrypt(enc)


for a in range(256):
    for b in range(256):
        key = key_prefix + bytes([a, b])
        xpt = decrypt_ecb(ct, key)
        enc1 = xor(xpt, pt)
        iv = xor(decrypt_ecb(enc1, key), pt)
        flag = decrypt(enc_flag, iv, key)
        if all(20 <= x < 127 for x in flag):
            print(flag)

Symbols

這題只給了你一個圖片，裡面有很多數學符號，看起來像是 substitution cipher。

我的解法是用 Detexify 去查 symbol 的 LaTeX command，然後可以注意到 command 的第一個字元應該就是 flag 的字元，所以最後找出了 CCTF{Play_with_LaTeX}。

medium-easy

Rima

這題是把 flag 變為 0 1 陣列，然後做一些移位的加法去 encode，不過他的程式碼很難讀所以我也放棄去理解那個 code，直接上 z3 就能解了。

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
from Crypto.Util.number import *
from sage.all import Integer, next_prime
from z3 import *

with open("g.enc", "rb") as f:
    g = bytes_to_long(f.read())

with open("h.enc", "rb") as f:
    h = bytes_to_long(f.read())

gg = list(map(int, Integer(g).digits(5)))
hh = list(map(int, Integer(h).digits(5)))

f = [Int(f"f_{i}") for i in range(8 * 32 - 1)]
f0 = list(f)

f.insert(0, 0)
for i in range(len(f) - 1):
    f[i] += f[i + 1]

a = next_prime(len(f))
b = next_prime(a)

g, h = [[_ for i in range(x) for _ in f] for x in [a, b]]

c = next_prime(len(f) >> 2)

for _ in [g, h]:
    for __ in range(c):
        _.insert(0, 0)
    for i in range(len(_) - c):
        _[i] += _[i + c]


sol = Solver()
for x in f0:
    sol.add(Or(x == 0, x == 1))
sol.add(And([x == y for x, y in zip(g, gg)]))
sol.add(And([x == y for x, y in zip(h, hh)]))
assert sol.check() == sat
m = sol.model()
f = [m.eval(x).as_long() for x in f0]
f = int("".join(map(str, f))[::-1], 2)
print(long_to_bytes(f))

Hyper Normal

這題會先把 flag encode 成一個 的矩陣 然後打亂，假設 flag 的字元是 ，那麼矩陣 會先變為:

然後再把 rows 隨機 shuffle。

接下來它會進迴圈 ，產生一個向量 ，然後計算:

其中 和 都是指 和 矩陣的第 個 row vector。這樣生成完 之後把 再次 shuffle rows 之後輸出成為加密的 flag。

我的解法是利用他 的性質，可以用暴力去算出 的可能值的集合，利用他的多個 rows 之後取交集之後就能知道 ，然後由此解回 flag。

不過可能我的解法有點小問題，取某些集合的交集所弄出來的 flag 怪怪的，要稍微改一下要取哪幾個集合去聯集才行。

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
# fmt: off
W = [] # fill this
# fmt: on

from sage.all import *
from functools import reduce
from operator import and_
import random

p = 8443


def transpose(x):
    result = [[x[j][i] for j in range(len(x))] for i in range(len(x[0]))]
    return result


def vsum(u, v):
    assert len(u) == len(v)
    l, w = len(u), []
    for i in range(l):
        w += [(u[i] + v[i]) % p]
    return w


def sprod(a, u):
    w = []
    for i in range(len(u)):
        w += [a * u[i] % p]
    return w


def encrypt(msg):
    l = len(msg)
    hyper = [ord(m) * (i + 1) for (m, i) in zip(list(msg), range(l))]
    V, W = [], []
    for i in range(l):
        v = [0] * i + [hyper[i]] + [0] * (l - i - 1)
        V.append(v)
    random.shuffle(V)
    # V = [V[1],V[0],V[3],V[2]]
    print(V)
    for _ in range(l):
        R, v = [random.randint(0, 126) for _ in range(l)], [0] * l
        for j in range(l):
            v = vsum(v, sprod(R[j], V[j]))
        W.append(v)
        print(R, v)
    random.shuffle(transpose(W))
    return W


l = len(W)
Z = GF(p)
W = Matrix(Z, W)

ccand = []
for k in range(l):
    cand = [set() for _ in range(l)]
    for i in range(1, 126):
        v = vector(x / i for x in W[k])
        for j in range(len(v)):
            cand[j].add(v[j])
    ccand.append(cand)

# print(ccand[0][0] & ccand[1][0] & ccand[2][0])
# print(ccand[0][1] & ccand[1][1] & ccand[2][1])
# print(ccand[0][2] & ccand[1][2] & ccand[2][2])
# print(ccand[0][3] & ccand[1][3] & ccand[2][3])

tccand = transpose(ccand)
flag = ""
for i in range(l):
    # tccand[i] = tccand[i][1::2]
    # without this line: CCTF{0w_f1Nd_th3_4lL_3I9EnV4Lu35_iN_FiN173_Fi3lD5 ???}
    # with this line: CCTF{H0w_f1Nd_th3_4l _3I9EnV4Lu35_iN_FiN173_Fi3lD5!???}
    # so we have the full flag

    ss = tccand[i][0]
    j = 1
    while len(ss) > 1:
        ss = ss & tccand[i][j]
        j += 1
    if len(ss) > 0:
        c = list(ss)[0] // (i + 1)
    else:
        c = ord(" ")
    flag += chr(c)
    print(flag)

# CCTF{H0w_f1Nd_th3_4lL_3I9EnV4Lu35_iN_FiN173_Fi3lD5!???}

從 flag 可知預期解應該和 eigenvalues 有關，不過看不太出來是要怎麼弄...

Hamul

這題是個 RSA 的題目，它的質數生成的步驟如下:

1
2
3
4
5
6
7
8
while True:
    p, q = getPrime(nbit), getPrime(nbit)
    P = int(str(p) + str(q))
    Q = int(str(q) + str(p))
    PP = int(str(P) + str(Q))
    QQ = int(str(Q) + str(P))
    if isPrime(PP) and isPrime(QQ):
        break

然後拿 n = PP * QQ 去當 RSA modulus 加密 flag。

首先是 str(p) 和 str(q) 的長度很容易知道它不是 19 就是 20，所以 ，然後 ，之後其他的也是能用差不多的寫法用等式寫出來，然後最後化為一個 的多項式求根的問題，我這邊用 coppersmith 求出來就行了。

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

n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043
c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399

# https://github.com/defund/coppersmith/blob/master/coppersmith.sage
load("~/workspace/coppersmith.sage")


for plen in [20, 19]:
    for qlen in [20, 19]:
        Plen = plen + qlen
        Qlen = plen + qlen
        Z = Zmod(100 * n + 1)
        PZ = PolynomialRing(Z, "p,q")
        p, q = PZ.gens()
        P = p * 10 ^ qlen + q
        Q = q * 10 ^ plen + p
        PPP = P * 10 ^ Qlen + Q
        QQQ = Q * 10 ^ Plen + P
        f = PPP * QQQ - n
        sol = small_roots(f, (2 ^ 65, 2 ^ 65), m=7, d=3)
        if len(sol) > 0:
            p, q = sol[0]
            PPP = PPP(p, q)
            QQQ = QQQ(p, q)
            assert PPP * QQQ == n
            d = inverse_mod(65537, (PPP - 1) * (QQQ - 1))
            m = power_mod(c, d, n)
            print(long_to_bytes(m))
            exit()

medium

Tuti

這題把 flag 分成兩半 和 ，符合以下的等式，其中 是某個常數:

把它改寫為多項式的根之後可以發現它可以分解:

其中 和 是可以求出的兩個常數，符合 。由於 和 都是正數，多項式 的條件就只能是 了。

把這個式子整理一下可以變成 ，所以把 分解之後就能求得 和 所有的解了。

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

k = 246389259423689900229483388850933720271363907782961941639413620688310657308991195363798484778005049234253341752674411282663124201840620584781830032437353134292733496201534415265400175632719346764031781179041636
# xy-x+y-b=0
# (y-1)(x+1)=b-1
b = 992752253935874779143952218845275961347009322164731344882417010624071055636710540798045985678351986133613

# big factors are factored using FactorDB
f1 = 1357459302115148222329561139218955500171643099
f2 = 17258104558019725087
f3 = 2035395403834744453

assert (b - 1) % f1 == 0
assert (b - 1) % f2 == 0
assert (b - 1) % f3 == 0

fs = list(factor(b // f1 // f2 // f3)) + [(f3, 1), (f2, 1), (f1, 1)]


def divs(f):
    # copied from sage
    output = [1]
    for p, e in f:
        prev = output[:]
        pn = 1
        for i in range(e):
            pn *= p
            output.extend(a * pn for a in prev)
    output.sort()
    return output


for d in divs(fs):
    x, y = d - 1, (b - 1) // d + 1
    assert (y - 1) * (x + 1) == b - 1
    flag = long_to_bytes(x) + long_to_bytes(y)
    if b"CCTF" in flag:
        print(flag)
        break

Salt and Pepper

這題有兩個未知的 salt 和 pepper，長度已經告訴你都是 19 了。然後它有給你 md5(salt) 和 sha(pepper) 的值。目標是要找出一組 input 包含指定的 username 和 password，然後要知道 sha1(pepper + input_password + md5(salt + input_username)) 的值。

做法顯然是要使用 Length Extension Attack，工具用的是 HashPump。不過這邊一個小問題是它要有個 data 才行。後來我是自己把這邊的檢查註解掉再編譯一次，然後會發現它的效果能正常出現你想要的結果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from pwn import *
from hashpumpy import hashpump

# ./hashpump -s '5f72c4360a2287bc269e0ccba6fc24ba' -a 'n3T4Dm1n' -k 19
s1 = "95623660d3d04c7680a52679e35f041c"
d1 = b"\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98\x00\x00\x00\x00\x00\x00\x00n3T4Dm1n"
# ./hashpump -s '3e0d000a4b0bd712999d730bc331f400221008e0' -a 'P4s5W0rd95623660d3d04c7680a52679e35f041c' -k 19
s2 = "83875efbe020ced3e2c5ecc908edc98481eba47f"
d2 = b"\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98P4s5W0rd"


io = remote("02.cr.yp.toc.tf", 28010)
io.sendlineafter(b"Options", b"L")
io.sendlineafter(b"comma: ", d1.hex() + "," + d2.hex())
io.sendlineafter(b"hash: ", s2)
io.interactive()

Triplet

這題目標是要找 3 組 RSA 的 (至少 160 bits)，然後要提供 符合 ，且 。

首先可以簡單的推得 ，其中的 。 代表的是 ，在 的情況代表 ，所以需要想辦法壓 的大小。

一個簡單的方法是取三個質數 和 ，取 , , 的話 就會比較小了。然後把 拿去分解之後就可以求得 了。

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


def phi(k):
    p, q = k
    return (p - 1) * (q - 1)


def lcm(a, b):
    return a * b // GCD(a, b)


p = 880418646898378491477543405137962536180977254166879
q = 2 * p + 1
r = 2 * q + 1
k1 = (p, q)
k2 = (q, r)
k3 = (p, r)
l = lcm(lcm(phi(k1), phi(k2)), phi(k3))
print(",".join(map(str, k1)))
print(",".join(map(str, k2)))
print(",".join(map(str, k3)))
mn = min(phi(k1), phi(k2), phi(k3))

print(l + 1)

d = (
    83818189125408135328873033373544374818199783983
    * 34388019287720328558025059428347529
    * 10803954241
)
assert d < mn
assert (l + 1) % d == 0
e = (l + 1) // d
assert e < mn
assert e * d % phi(k1) == 1
assert e * d % phi(k2) == 1
assert e * d % phi(k3) == 1

print(f"{e},{d}")

# CCTF{7HrE3_b4Bie5_c4rRi3d_dUr1nG_0Ne_pr39naNcY_Ar3_triplets}

Onlude

這題會先把 flag encode 成一個 的 矩陣 ，接下來有兩個矩陣 和 ，後者用 LU 分解得到 。

加密的部分是用 進行加密。另外它還有提供三個矩陣 , 還有 。

首先 ，所以結合 之後可以算出 矩陣。有了 之後就可以求出 ，這樣又能再推出 。所以 和 都有了，解密就反過來算回去即可。

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
p = 71

with open("output.txt") as f:
    lines = [line.strip() for line in f.readlines() if "=" not in line]
    vecs = [[int(x) for x in line[1:-1].split(" ") if x] for line in lines]
    E = matrix(GF(p), vecs[:11])
    LUL = matrix(GF(p), vecs[11:22])
    L1S2L = matrix(GF(p), vecs[22:33])
    R1S8 = matrix(GF(p), vecs[33:44])

U = L1S2L * LUL ^ -1
S2 = LUL * U
R = (R1S8 * S2 ^ -4) ^ -1
A = U ^ -1 * E - R
print(A)

alphabet = "=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>"


flag = ""
for k in range(100):
    i, j = 5 * k // 11, 5 * k % 11
    if A[i, j] == 0:
        break
    flag += alphabet[A[i, j]]
print(flag)

Improved

這題是個奇怪的 hash，目標是要找 collision。它一開始有個 parameter generation 會生成兩個質數 和 ，然後求出 , 和 ，之後再算 , 以及 ，最後的參數是 。

hash 的部份是用 , 和 ，而最後 hash 的結果是 。

PS: 它的 有限制

這個題目雖然看起來很複雜，不過實際上很簡單就能解了。可以知道 中任意元素的 order 都是 ，所以把只要算一個 就能知道 ，然後還能找到另一根 。由於 是偶數所以可以確定 ，得到 collision。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from pwn import remote
import ast

io = remote("05.cr.yp.toc.tf", 14010)
io.sendlineafter(b"Options", b"G")
io.recvuntil(b"Parameters = ")
n, f, v = ast.literal_eval(io.recvlineS().strip())
assert f % 2 == 0
g = pow(48763, n, n * n)
x = pow(g, f // 2, n * n)
y = n * n - x
assert pow(x, f, n * n) == 1
assert pow(y, f, n * n) == 1
print(x)
print(y)
io.sendlineafter(b"Options", b"R")
io.sendlineafter(b"comma: ", f"{x},{y}".encode())
print(io.recvallS())

Maid

這題會先生成兩個質數 和 符合 ，然後算 和 private key 。

flag 的話是用傳統 RSA 加密 ，不過它的加密與解密的 oracle 是 rabin cryptosystem 的。它的加密函數很簡單的就是 ，不過解密的函數是藏起來的，但是可以看了出來它只用了 就可以解密，所以大概是類似 的樣子。

目標需要分解 和 ，首先可以用它的加密 oracle 算 gcd 得到 ，要取得 的關鍵則是在解密 oracle 的地方。

我一開始的作法是想說如果 為奇數，那麼 decrypt -1 之後 ，之後把得到的值 +1 之後就是 了，這個做法在 local 測試是完全沒問題的。不過它 remote 藏起來的 decrypt 函數似乎不這麼簡單，所以這個做法一直不成功。

後來我是用 的方法可以求出一個值，一開始以為是 ，不過後來發現那個是 ，這樣之後就能獲得 去得到 flag 了。

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
from pwn import *
from Crypto.Util.number import *
from gmpy2 import isqrt
from functools import reduce

# io = process(["python", "maid.py"])
io = remote("04.cr.yp.toc.tf", 38010)
io.sendlineafter(b"Options", b"S")
io.recvuntil(b" = ")
enc_flag = int(io.recvlineS().strip())


def encrypt(msg):
    io.sendlineafter(b"Options", b"E")
    io.sendlineafter(b"encrypt: ", str(msg).encode())
    io.recvuntil(b" = ")
    return int(io.recvlineS().strip())


def decrypt(msg):
    io.sendlineafter(b"Options", b"D")
    io.sendlineafter(b"decrypt: ", str(msg).encode())
    io.recvuntil(b" = ")
    return int(io.recvlineS().strip())


pub = GCD(
    GCD(2 ** 4000 - encrypt(2 ** 2000), 2 ** 4002 - encrypt(2 ** 2001)),
    GCD(2 ** 4004 - encrypt(2 ** 2002), 2 ** 4006 - encrypt(2 ** 2003)),
)
print(pub)
p2 = reduce(GCD, [decrypt(2 ** i) ** 2 - 2 ** i for i in range(1991, 2015, 2)])
p = isqrt(p2)
assert p > 100
assert pub % p == 0
q = pub // p // p
assert p * p * q == pub
d = pow(65537, -1, (p - 1) * (q - 1))
print(long_to_bytes(pow(enc_flag, d, p * q)))

最後附上出題者在 Discord 發的這題的解密函數:

1
2
3
4
5
6
7
8
9
def decrypt(c, privkey):
    m_p = pow(c, (privkey + 1) // 4, privkey)
    i = (c - pow(m_p, 2)) // privkey
    j = i * inverse(2*m_p, privkey) % privkey
    m = m_p + j * privkey
    if 2*m < privkey**2:
        return m
    else:
        return privkey**2 - m

Ferman

這題沒有 source，題目是會給你 的一個式子，然後用 去加密 flag，所以目標就是解開那個式子。

一開始沒什麼想法，不過分解一下 的時候會發現 ，重複拿多組參數進行測試也會有一樣的結果。然後雖然 Sage 裡面的 solver 解不開 ，但是它解了掉 。

既然有辦法取得 的解，用 Brahmagupta–Fibonacci identity 可以很簡單的從 的解拓展到 的解，然後再反覆往上拓展到 的解。

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

e = 65537
a = 769
b = 90
# (p - a)**2 + (q - b)**2 == k**7
k = 533349483431826854866479442416204129077526048835547852310509534957185
c = 4478819143432789024587861603523572305269547479550443133641110109373270566470025946722977115602647046295004476694988416461505550664119915082335497331912881526446940124404687029541487759747406116312872601161581904176763818623358120927587871262018474674411074996384180525486478668863914557062661081721929081678057785839028975581815732964462013512812566725502749216649190469493027431158255717939171221374546082898410798277258418126725070247145397363980604758633071972900958843430904130
p, q = var("p q")
assume(p, "integer")
assume(q, "integer")
sol = solve(p ** 2 + q ** 2 == k, p, q)
sol = [(Integer(p), Integer(q)) for p, q in sol if p > 0 and q > 0]


def mul(r, s):
    # https://en.m.wikipedia.org/wiki/Brahmagupta%E2%80%93Fibonacci_identity
    a, b = r
    c, d = s
    x1 = a * c - b * d
    y1 = a * d + b * c
    x2 = a * c + b * d
    y2 = a * d - b * c
    return (abs(x1), abs(y1)), (abs(x2), abs(y2))


def sqr(r):
    return mul(r, r)[0]


for r in sol:
    r2 = sqr(r)
    r4 = sqr(r2)
    for r3 in mul(r, r2):
        for r7 in mul(r4, r3):
            p, q = r7
            assert p ^ 2 + q ^ 2 == k ^ 7
            p += a
            q += b
            if isPrime(p) and isPrime(q):
                print(p, q)
                n = p * q
                phi = (p - 1) * (q - 1)
                d = inverse_mod(e, phi)
                m = power_mod(c, d, n)
                print(long_to_bytes(m))
                exit()

我後來發現這個 implementation 能解開這題其實只是運氣好，因為它直接把一個解往上開 7 次方，它不一定能包含所有 的解，正確的作法應該要真正的把 的所有解去相乘得到 的解，然後再把兩個的解再相乘得到 的解...

Tiny ECC

這題的目標要自己題供兩個質數 和 (至少 128 bits)，以及兩個數 和 。接下來它會用在兩條橢圓曲線 over or 上面隨機選兩個點然後給你兩個 ECDLP 要解開，算出來才有 flag。

我用的方法非常簡單暴力，就直接暴力找 使兩條曲線的 order 都是 2^40-smooth 的，大概幾分鐘就出來了。

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


def gp(b):
    while True:
        p = getPrime(b)
        if isPrime(2 * p + 1):
            return p, 2 * p + 1


while True:
    p, q = gp(128)
    a, b = 2, 3
    mxp = max([p for p, e in factor(EllipticCurve(GF(p), [a, b]).order())])
    mxq = max([p for p, e in factor(EllipticCurve(GF(q), [a, b]).order())])
    if mxp < 2 ^ 40 and mxq < 2 ^ 40:
        print(p, q)
        break
    print(log(mxp, 2).n(), log(mxq, 2).n())

然後剩下的部分就是用 sage 內建的 pohlig hellman 即可:

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
from pwn import remote
import ast

p = 301712731189529370473291776359599603783
q = 2 * p + 1
Ep = EllipticCurve(GF(p), [2, 3])
Eq = EllipticCurve(GF(q), [2, 3])


io = remote("01.cr.yp.toc.tf", 29010)
io.sendlineafter(b"Options", b"C")
io.sendline(str(p).encode())
io.sendlineafter(b"Options", b"A")
io.sendline(b"2,3")
io.sendlineafter(b"Options", b"S")
io.recvuntil(b"P = ")
P = Ep(*ast.literal_eval(io.recvlineS().strip()))
io.recvuntil(b"k*P = ")
kP = Ep(*ast.literal_eval(io.recvlineS().strip()))
io.recvuntil(b"Q = ")
Q = Eq(*ast.literal_eval(io.recvlineS().strip()))
io.recvuntil(b"l*Q = ")
lQ = Eq(*ast.literal_eval(io.recvlineS().strip()))
print("solve p")
k = discrete_log(kP, P, operation="+")
print(k)
print("solve q")
l = discrete_log(lQ, Q, operation="+")
print(l)
io.sendline((str(k) + "," + str(l)).encode())
io.interactive()
# CCTF{ECC_With_Special_Prime5}

另外，這題的一個另解挺有趣的，它雖然有要求 ，但是可以設 ，所以這等於是在 的 singular curve 上的 ECDLP 而已。由於 可以用 把它轉換到 或 的加法群上，這樣 DLP 就變成了簡單的除法了。

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
from pwn import remote
import ast

p = 301712731189529370473291776359599603783
q = 2 * p + 1
Fp = GF(p)
Fq = GF(q)


def phi(P, F):
    return F(P[0]) / F(P[1])


def solve_dlp(P, G, F):
    # xG = P
    pG = phi(G, F)
    pP = phi(P, F)
    return pP / pG


io = remote("01.cr.yp.toc.tf", 29010)
io.sendlineafter(b"Options", b"C")
io.sendline(str(p).encode())
io.sendlineafter(b"Options", b"A")
io.sendline(f"{p*q},{p*q}".encode())
io.sendlineafter(b"Options", b"S")
io.recvuntil(b"P = ")
P = ast.literal_eval(io.recvlineS().strip())
io.recvuntil(b"k*P = ")
kP = ast.literal_eval(io.recvlineS().strip())
io.recvuntil(b"Q = ")
Q = ast.literal_eval(io.recvlineS().strip())
io.recvuntil(b"l*Q = ")
lQ = ast.literal_eval(io.recvlineS().strip())
print("solve p")
k = solve_dlp(kP, P, Fp)
print(k)
print("solve q")
l = solve_dlp(lQ, Q, Fq)
print(l)
io.sendline((str(k) + "," + str(l)).encode())
io.interactive()
# CCTF{ECC_With_Special_Prime5}

*Elegant Curve

這題和前一題類似，不過這次它是要選兩個質數 符合 ，然後兩條曲線的 可以不同。這個理論上用前一題的暴力生成法也是可以的，不過效率不高。

這次我是先生成一條 anomalous curve，即 的曲線，然後用 next prime 找到 ，接下來 就用一樣的值去給它暴力找 smooth curve 而已。

生成腳本如下:

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
from Crypto.Util.number import *
from subprocess import check_output
import json


def nextPrime(p):
    assert p > 2
    p += 2
    while not isPrime(p):
        p += 2
    return p


ECGEN_PATH = "" # Prebuilt binary of ecgen: https://github.com/J08nY/ecgen


def gen_anomalous(bits):
    r = check_output([ECGEN_PATH, "--anomalous", "--fp", str(bits)])
    curve = json.loads(r)[0]
    return int(curve["a"], 16), int(curve["b"], 16), int(curve["field"]["p"], 16)


while True:
    a, b, p = gen_anomalous(160)
    q = nextPrime(p)
    mxq = max([p for p, e in factor(EllipticCurve(GF(q), [a, b]).order())])
    if mxq < 2 ^ 40:
        print(a, b)
        print(p, q)
        break
    print(log(mxq, 2).n())

拿到需要的參數之後就可以簡單的解開了:

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

a, b = (
    823375435824563939268788611110428744408176719161,
    128395071361889866257668408194030595816566744161,
)
p, q = (
    890662999704698873790151198748536866796172800897,
    890662999704698873790151198748536866796172800963,
)
Ep = EllipticCurve(GF(p), [a, b])
Eq = EllipticCurve(GF(q), [a, b])

assert Ep.order() == p


def smart_attack(P, G, p):
    # https://crypto.stackexchange.com/a/70508
    E = G.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ZZ(t) + randint(0, p) * p for t in E.a_invariants()])

    P_Qps = Eqp.lift_x(ZZ(G.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == G.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == P.xy()[1]:
            break

    p_times_P = p * P_Qp
    p_times_Q = p * Q_Qp

    x_P, y_P = p_times_P.xy()
    x_Q, y_Q = p_times_Q.xy()

    phi_P = -(x_P / y_P)
    phi_Q = -(x_Q / y_Q)
    k = phi_Q / phi_P
    return ZZ(k)


def recvpoint(io, name):
    io.recvuntil(f"{name} = {{".encode())
    return ast.literal_eval(io.recvlineS().strip()[:-1])


# io = process(["python", "elegant_curve.py"])
io = remote("07.cr.yp.toc.tf", 10010)
io.sendlineafter(b"Options", b"S")
io.sendlineafter(b"first", f"{a},{b},{p}".encode())
io.sendlineafter(b"second", f"{a},{b},{q}".encode())
G = Ep(recvpoint(io, "G"))
H = Eq(recvpoint(io, "H"))
rG = Ep(recvpoint(io, "r * G"))
sH = Eq(recvpoint(io, "s * H"))
r = smart_attack(rG, G, p)
s = discrete_log(sH, H, operation="+")
print(r, s)
io.sendline(f"{r},{s}".encode())
io.interactive()
# CCTF{Pl4yIn9_Wi7H_ECC_1Z_liK3_pLAiNg_wiTh_Fir3!!}

medium-hard

Wolf

這題用 AES-GCM 加密 flag，然後有個 oracle 可以讓你隨便加密任意資訊。此題關鍵在於它的 IV 都是固定的，所以它加密的地方和 CTR mode reuse nonce 有一樣的問題，把兩個密文 xor 然後再 xor 已知的明文就可得到 flag。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from pwn import remote


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


io = remote("01.cr.yp.toc.tf", 27010)
io.sendlineafter(b"Options", "G")
io.recvuntil(b"encrypt(flag) = ")
enc_flag = bytes.fromhex(io.recvlineS().strip())

io.sendlineafter(b"Options", "T")
io.sendlineafter(b"encrypt:", "a" * 128)
io.recvuntil(b"enc = ")
enc_a = bytes.fromhex(io.recvlineS().strip())
print(xor(b"a" * 128, xor(enc_flag, enc_a)))

Frozen

此題有兩個參數 ( 是 128 bits)，然後 keygen 的時候會先計算 5 個數字 ，然後 public key 是 的 high 96 bits，然後 private key 是 的 low 32 bits。 是個未知的隨機數。

然後它有個 sign 函數是把 msg 每四 bytes group 成一組轉換成數字 ，然後拿 q = next_prime(max(M))，之後以 做為 signature。它會隨機產生字串給你，能 sign 出正確的 signature 即可拿到 flag。

首先可知 ，所以能寫出:

把兩個式子中的 消除掉之後可以變成只有 和 的多項式，用 coppersmith 解開後可以還原出 ，可以算出完整的 private key，然後就能 sign msg 得到 flag。

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
from Crypto.Util.number import *
from pwn import remote
from sage.matrix.matrix2 import Matrix
import ast


def resultant(f1, f2, var):
    # Copied from https://jsur.in/posts/2021-07-19-google-ctf-2021-crypto-writeups#h1
    return Matrix.determinant(f1.sylvester_matrix(f2, var))


io = remote("03.cr.yp.toc.tf", 25010)
io.sendlineafter(b"Options", b"S")
io.recvuntil(b"p = ")
p = int(io.recvlineS().strip())
io.recvuntil(b"r = ")
r = int(io.recvlineS().strip())
io.sendlineafter(b"Options", b"P")
io.recvuntil(b"pubkey = ")
pubkey = ast.literal_eval(io.recvlineS().strip())
print(p, r)
print([hex(x) for x in pubkey])

ks = [pow(r, c + 1, p) for c in range(0, 5)]
Z = Zmod(p)
PP = PolynomialRing(Z, "s,x1,x2")
s, *xs = PP.gens()
f1 = ks[0] * s - (pubkey[0] + xs[0])
f2 = ks[1] * s - (pubkey[1] + xs[1])
f = PP.remove_var(s)(resultant(f1, f2, s))
print(f)
load("~/workspace/coppersmith.sage")
xs = small_roots(f, (2 ** 40, 2 ** 40), m=4, d=2)[0]
s = Z(pubkey[0] + xs[0]) / ks[0]
assert s == Z(pubkey[1] + xs[1]) / ks[1]
print(s)
U = [pow(r, c + 1, p) * s % p for c in range(0, 5)]
S = [int(bin(u)[2:][-32:], 2) for u in U]
print([hex(x) for x in S])


def sign(msg, privkey, d):
    msg = msg.encode("utf-8")
    l = len(msg) // 4
    M = [bytes_to_long(msg[4 * i : 4 * (i + 1)]) for i in range(l)]
    q = int(next_prime(max(M)))
    sign = [M[i] * privkey[i] % q for i in range(l)]
    return sign


io.sendlineafter(b"Options", b"F")
io.recvuntil(b"example: ")
msg = io.recvlineS().strip()
sig = sign(msg, S, 32)
io.sendline(",".join(map(str, sig)))
print(io.recvlineS())

flag 內容中也是有提到 Lattice，不過據別人所說，不用 Lattice 也是可以的。因為題目中其實還有個沒用到的 oracle，它會給你一組固定的 msg 和 signature，因為 msg 已知所以也能求 ，然後就可反推 private key。

LINDA

這題我覺得挺無聊的，它有四個參數 ，其中 是隨機的、、。

encrypt 的地方有 , 以及 。 (裡面的 都是隨機生成的，和前面無關)

這題看起來像是類似 ElGamal 有關的加密系統，不過關鍵在於它的質數 的生成方法是藏起來的，測試一下可以發現 是 2^40-smooth 的，所以直接 DLP 算出 出來之後就可以解密了。

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 *

p = 512156828103365901048559505103237592010730651992953680223000172094095757203886681225415426450387040031253612295400192069437985566674257501701743368686395531
u = 278331424202715529007235225803083105831898177238768088959896273495587346471193489462465390715976004916539200837444755811532762335472120306642106779851779895
v = 256568421561256620412008753530664775781745915184311927713911832406042827934333342438038088202080460367979454347035971495645785213472938457309904032230294302
w = 291075584404341211571864039572762475831612407000784732318354539887997569888845019102264165940156056600333692694871997403708476839090241830333179131216949773
ca, cb, cc = (
    287555353447321752440570170565916634951105240901098656962539161570704086923490274350537706807786632105173520254109700863175418950150190301275461066194290273,
    61323835393791353232128681044112245885676777670178659696073015541712435637029773641799576432645407470518574659302988690944012552307615441231640649288656467,
    24320377817820710179555605271052810810335284586923974087878926553551229844983654115310868607990402619355506091875700785511303195656702348392817435407241231,
)

Z = Zmod(p)

r = discrete_log(Z(ca), Z(u))
print(r)
s = discrete_log(Z(cb), Z(v))
print(s)
wrs = Z(w) ** (r + s)
m = Z(cc) / wrs
print(long_to_bytes(m))

*RSAphantine

這題要解個丟番圖方程式系統，然後解出解之後可以求出兩個質數 ，然用就可以把 flag 解密。

我一開始試著用 sage 裡面的 groebner basis 去解，不過跑了很久都沒結果，所以就沒解出來。

賽後看別人說可以注意到 ，所以把 分解之後可以解出 ，然後用第二式求出唯一的 即可。

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


def nextPrime(x):
    if x % 2 == 0:
        x += 1
    else:
        x += 2
    while not isPrime(x):
        x += 2
    return x


k1 = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613520747411963822349374260144229698759495359592287331083229572369186844312169397998958687629858407857496154424105344376591742814310010312178029414792153520127354594349356721
k2 = 89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051
k3 = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613609786612391835856376321085593999733543104760294208916442207908167085574197779179315081994735796390000652436258333943257231020011932605906567086908226693333446521506911058
c = 486675922771716096231737399040548486325658137529857293201278143425470143429646265649376948017991651364539656238516890519597468182912015548139675971112490154510727743335620826075143903361868438931223801236515950567326769413127995861265368340866053590373839051019268657129382281794222269715218496547178894867320406378387056032984394810093686367691759705672


# k3 - k1 = y^6 + x^3 = (y^4 - x*y^2 + x^2)*(y^2 + x)

s1 = 3133713317731333
s2 = 28413320364759425177418147555143516002041291710972733253944530195017276664069717887927099709630886727522090965378073004342203980057853092114878433424202989

assert s1 * s2 == k3 - k1


def solve_xy():
    P = PolynomialRing(QQ, "x,y")
    x, y = P.gens()
    I = P.ideal([y ^ 2 + x - s1, y ^ 4 - x * y ^ 2 + x ^ 2 - s2])
    V = I.variety()
    for sol in V:
        yield (Integer(sol[x]), Integer(sol[y]))


def solve_z(x, y):
    P = PolynomialRing(ZZ, "z")
    z = P.gen()
    f = x ^ 4 + y ^ 5 + x * y * z - k2
    rs = f.roots()
    if len(rs) > 0:
        return Integer(rs[0][0])


for x, y in solve_xy():
    z = solve_z(x, y)
    if z is None:
        continue
    print(x, y, z)
    assert 2 * z ** 5 - x ** 3 + y * z == k1
    assert x ** 4 + y ** 5 + x * y * z == k2
    assert y ** 6 + 2 * z ** 5 + z * y == k3
    p = nextPrime(x ** 2 + z ** 2 + y ** 2 << 76)
    print(p)
    q = nextPrime(z ** 2 + y ** 3 - y * x * z ^^ 67)
    print(q)
    n, e = p * q, 31337
    d = inverse_mod(e, (p - 1) * (q - 1))
    print(long_to_bytes(power_mod(c, d, n)))

賽後看到有人說可以直接用 Mathematica 解開，我之後也去試過了，真的幾分鐘內就可以解開。

1
2
3
4
5
6
7
In[4]:= FindInstance[{2z^5-x^3+y*z==k1,x^4+y^5+x*y*z==k2,y^6+2z^5+z*y==k3}, {x, y, z}, Integers]

Out[4]= {{x -> -97319611529501810510904538298668204056042623868316550440771307534558768612892,

>     y -> 311960913464334198969500852124413736815,

>     z -> 29896806674955692028025365368202021035722548934827533460297089}}

可以用 Docker 的 wolframresearch/wolframengine 免費在自己的電腦上跑，因為 tio.run 上面只能給你跑 60 秒

*Double Miff

這題給了一條奇怪的曲線 ，參數都未知。上面有定義一個奇怪的加法，然後給了三個點 ，而 flag 是 和 的 x 座標。

首先要找出 ，這邊就直接把點都代進去變成 的多項式，然後消掉一些變數之後用 gcd 可以找到 的倍數，之後用 factordb 就可以找到 。

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
from sage.matrix.matrix2 import Matrix


def resultant(f1, f2, var):
    # Copied from https://jsur.in/posts/2021-07-19-google-ctf-2021-crypto-writeups#h1
    return Matrix.determinant(f1.sylvester_matrix(f2, var))


P.<a, b> = ZZ[]


def point(x, y):
    return a * x * (y ** 2 - 1) - b * y * (x ** 2 - 1)


PQ = point(
    540660810777215925744546848899656347269220877882,
    102385886258464739091823423239617164469644309399,
)
QQ = point(
    814107817937473043563607662608397956822280643025,
    961531436304505096581595159128436662629537620355,
)
PP = point(
    5565164868721370436896101492497307801898270333,
    496921328106062528508026412328171886461223562143,
)

print(gcd(resultant(QQ, PP, a), resultant(QQ, PQ, a)))
# p = 1141623079614587900848768080393294899678477852887

然後想解 的話會發現根本解不出來，因為實際上 是多少都不影響，把點代進去的多項式做 gcd 會發現他們根本不互質，只要 呈一個線性關係即可符合。

之後目標是要利用它的加法公式逆推把點切半，這個可以直接列出兩個多項式，然後消掉變數之後求根就能找到了。

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
from Crypto.Util.number import *
from sage.matrix.matrix2 import Matrix


def resultant(f1, f2, var):
    # Copied from https://jsur.in/posts/2021-07-19-google-ctf-2021-crypto-writeups#h1
    return Matrix.determinant(f1.sylvester_matrix(f2, var))


p = 1141623079614587900848768080393294899678477852887
F = GF(p)

PQ = (
    F(540660810777215925744546848899656347269220877882),
    F(102385886258464739091823423239617164469644309399),
)
QQ = (
    F(814107817937473043563607662608397956822280643025),
    F(961531436304505096581595159128436662629537620355),
)
PP = (
    F(5565164868721370436896101492497307801898270333),
    F(496921328106062528508026412328171886461223562143),
)


def half(P):
    x3, y3 = P
    PP.<x1, y1> = GF(p)[]
    f1 = (1 + x1 ^ 2) * (1 - y1 ^ 2) * x3 - 2 * x1 * (1 + y1 ^ 2)
    f2 = (1 + y1 ^ 2) * (1 - x1 ^ 2) * y3 - 2 * y1 * (1 + x1 ^ 2)
    return [r for r, _ in resultant(f1, f2, y1).univariate_polynomial().roots()]


for x in half(PP):
    print(long_to_bytes(x))


for x in half(QQ):
    print(long_to_bytes(x))

*ecchimera

這題有個橢圓曲線在 上面，flag 是兩個點的 discrete log 結果。首先這題的 是合數，可以把它分解成 得到兩條曲線上的 DLP，只要分開解出來之後用 CRT 就可以還原了。

首先是一個質數 ，可以發現 ，所以這個可以用 Smart Attack 處裡即可。

另一個質數 會發現它的 ，因為 所以知道 embedding degree 是 2，這個很小所以可以用 MOV Attack 去解開。

不過我用 MOV Attack 的時候是發現它確實能弄出 pairing，但是主要問題在於它轉移到的 finite field 還是太大的算了很久都算不出來，後來去參考別人的 writeup 說這題因為 flag 不長，找個它 mod 一個某個小數字的值就夠了。

所以方法就是找 中的某個 divisor，然後用弄到 subgroup 之中再 MOV Attack 即可，不過我發現這個有機會會失敗，可能是我裡面取的點 沒有取好...。不過既然是找 subgroup 中的 order，其實連 MOV Attack 都不需要，直接算其實就夠了==。

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

n = 43216667049953267964807040003094883441902922285265979216983383601881964164181
U = 18230294945466842193029464818176109628473414458693455272527849780121431872221
V = 13100009444194791894141652184719316024656527520759416974806280188465496030062
W = 5543957019331266247602346710470760261172306141315670694208966786894467019982

p = 190116434441822299465355144611018694747
q = n // p

Ep = EllipticCurve(GF(p), [0, U, 0, V, W])
Eq = EllipticCurve(GF(q), [0, U, 0, V, W])
Gp = Ep(
    6907136022576092896571634972837671088049787669883537619895520267229978111036,
    35183770197918519490131925119869132666355991678945374923783026655753112300226,
)
Gq = Eq(
    6907136022576092896571634972837671088049787669883537619895520267229978111036,
    35183770197918519490131925119869132666355991678945374923783026655753112300226,
)
sGp = Ep(
    14307615146512108428634858855432876073550684773654843931813155864728883306026,
    4017273397399838235912099970694615152686460424982458188724369340441833733921,
)
sGq = Eq(
    14307615146512108428634858855432876073550684773654843931813155864728883306026,
    4017273397399838235912099970694615152686460424982458188724369340441833733921,
)


def find_embedding_degree(E):
    p = E.base().order()
    n = E.order()
    if p == n:
        # anomalous curve
        return 0
    for k in range(1, 13):
        if (p ** k - 1) % n == 0:
            return k


assert find_embedding_degree(Ep) == 0
assert find_embedding_degree(Eq) == 2


def smart_attack(P, G, p):
    # https://crypto.stackexchange.com/a/70508
    E = G.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ZZ(t) + randint(0, p) * p for t in E.a_invariants()])

    P_Qps = Eqp.lift_x(ZZ(G.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == G.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == P.xy()[1]:
            break

    p_times_P = p * P_Qp
    p_times_Q = p * Q_Qp

    x_P, y_P = p_times_P.xy()
    x_Q, y_Q = p_times_Q.xy()

    phi_P = -(x_P / y_P)
    phi_Q = -(x_Q / y_Q)
    k = phi_Q / phi_P
    return ZZ(k)


def mov_attack(P, G, p, ord):
    E = P.curve()
    k = find_embedding_degree(E)
    K = GF(p ** k, "a")
    EK = E.base_extend(K)
    PK = EK(P)
    GK = EK(G)
    QK = EK.random_point()  # Assuming QK is linear independent to PK
    egqn = PK.tate_pairing(QK, E.order(), k)  # e(P,Q)=e(G,Q)^n
    egq = GK.tate_pairing(QK, E.order(), k)  # e(G,Q)
    return discrete_log(egqn, egq, ord=ord)


sp = smart_attack(sGp, Gp, p)
assert sp * Gp == sGp
print(sp)

qsg = Integer(10214219295529808)
qsgx = Eq.order() // qsg
sq = discrete_log(sGq * qsgx, Gq * qsgx, ord=qsg, operation="+")
# sq = mov_attack(sGq * qsgx, Gq * qsgx, q, ord=qsg) # Not guaranteed to get correct value for unknown value...
print(sq)

s = crt([sp, sq], [Ep.order(), qsg])
print(s)
print(long_to_bytes(s))
# m1X3d_VeR5!0n_oF_3Cc!

hard

*Rohald

這題有條 的 Edwards Curve，不過參數全部未知。再來是它有給四個點，，其中 是 flag 的前半和後半。

首先需要先求出參數，可以把四個點都帶入式子中得到四個整數的多項式，之後用對消的方法可以把 全部消掉，之後 gcd 之後可以拿到 ，然後用 factordb 去分解就能知道 是多少了。

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
from sage.matrix.matrix2 import Matrix


def resultant(f1, f2, var):
    # Copied from https://jsur.in/posts/2021-07-19-google-ctf-2021-crypto-writeups#h1
    return Matrix.determinant(f1.sylvester_matrix(f2, var))


P.<c, d> = ZZ[]


def point(u, v):
    return u ** 2 + v ** 2 - c ** 2 * (1 + d * u ** 2 * v ** 2)


P = point(
    398011447251267732058427934569710020713094,
    548950454294712661054528329798266699762662,
)
Q = point(
    139255151342889674616838168412769112246165,
    649791718379009629228240558980851356197207,
)
sP = point(
    730393937659426993430595540476247076383331,
    461597565155009635099537158476419433012710,
)
tQ = point(
    500532897653416664117493978883484252869079,
    620853965501593867437705135137758828401933,
)

print(
    gcd(
        resultant(resultant(P, tQ, c), resultant(sP, Q, c), d),
        resultant(resultant(P, Q, c), resultant(sP, tQ, c), d),
    )
)
# Then factordb get p = 903968861315877429495243431349919213155709

再來是要求 ，既然知道 了就簡單多項式互消之後就能求出來了:

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
from sage.matrix.matrix2 import Matrix


def resultant(f1, f2, var):
    # Copied from https://jsur.in/posts/2021-07-19-google-ctf-2021-crypto-writeups#h1
    return Matrix.determinant(f1.sylvester_matrix(f2, var))

p = 903968861315877429495243431349919213155709
P.<c, d> = GF(p)[]

def point(u, v):
    return u ** 2 + v ** 2 - c ** 2 * (1 + d * u ** 2 * v ** 2)
P = point(
    398011447251267732058427934569710020713094,
    548950454294712661054528329798266699762662,
)
Q = point(
    139255151342889674616838168412769112246165,
    649791718379009629228240558980851356197207,
)
sP = point(
    730393937659426993430595540476247076383331,
    461597565155009635099537158476419433012710,
)
tQ = point(
    500532897653416664117493978883484252869079,
    620853965501593867437705135137758828401933,
)
dd = resultant(P,Q,c).univariate_polynomial().roots()[0][0]
cc = resultant(P,Q,d).univariate_polynomial().roots()[0][0]
print(cc, dd)

現在 都有了，問題在於 sage 的 EllipticCurve 不支援 Edwards Curve。其實去 wiki 就能查到一句話 Every Edwards curve is birationally equivalent to an elliptic curve in Weierstrass form，所以代表有辦法把曲線轉換成 Weierstrass form 之後讓 sage 來處理。

我首先是在這邊有找到把 形式的 Edwards Curve 轉換回 Weierstrass form 的公式，問題在於這條曲線有多出一個參數 。之後繼續查下去可以發現這種有 參數形式的是另外兩個人發明的，去找到了他們原本的 paper 就在第五頁看到了 和 互相轉換的公式。

轉換回去之後會發現曲線的 order 相當 smooth，所以直接讓 sage 解開即可:

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

p = 903968861315877429495243431349919213155709
c = 662698094423288904843781932253259903384619
d = 540431316779988345188678880301417602675534

F = GF(p)


P = (
    F(398011447251267732058427934569710020713094),
    F(548950454294712661054528329798266699762662),
)
Q = (
    F(139255151342889674616838168412769112246165),
    F(649791718379009629228240558980851356197207),
)
sP = (
    F(730393937659426993430595540476247076383331),
    F(461597565155009635099537158476419433012710),
)
tQ = (
    F(500532897653416664117493978883484252869079),
    F(620853965501593867437705135137758828401933),
)
assert P[0] ^ 2 + P[1] ^ 2 - c ^ 2 * (1 + d * P[0] ^ 2 * P[1] ^ 2) == 0

# https://eprint.iacr.org/2007/286.pdf page 5
d = F(d) * F(c) ^ 4


def phi(P):
    return (P[0] / c, P[1] / c)


P = phi(P)
Q = phi(Q)
sP = phi(sP)
tQ = phi(tQ)
assert P[0] ^ 2 + P[1] ^ 2 - (1 + d * P[0] ^ 2 * P[1] ^ 2) == 0

# https://fse.studenttheses.ub.rug.nl/10478/1/Marion_Dam_2012_WB_1.pdf page 22, 23

a2 = 2 * (d + 1)
a4 = (d - 1) ^ 2
E = EllipticCurve(F, [0, a2, 0, a4, 0])


def phi2(P):
    x, y = P
    A = 2 * y - (2 * d * y + d + 1) * x ^ 2 + 2
    return (A / (x ^ 2), (-2 * A) / (x ^ 3))


P = E(phi2(P))
Q = E(phi2(Q))
sP = E(phi2(sP))
tQ = E(phi2(tQ))

# E.order() is smooth
s = discrete_log(sP, P, operation="+")
t = discrete_log(tQ, Q, operation="+")
print(long_to_bytes(s) + long_to_bytes(t))

*DoRSA

這題有個奇怪的 RSA，參數大致如下:

首先可以推出:

由此可以知道 ，不過這個和解這題沒什麼關係。

最關鍵的一件事是要看出:

所以拿 去連分數展開有機會可以找到 ，結果也真的可以找到。

得到 之後利用利用這兩個式子:

用中國餘數定理能求出 的值，接下來利用 就能逼近然後暴力找出 ，再把 分解拿到 flag 即可。

雖然到這邊就能解出 flag 了，不過利用目前獲得的資訊是能繼續把 分解掉，因為 ，所以 ，然後這樣 也就解決了。

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 *

e = 93546309251892226642049894791252717018125687269405277037147228107955818581561
n1 = 36029694445217181240393229507657783589129565545215936055029374536597763899498239088343814109348783168014524786101104703066635008905663623795923908443470553241615761261684865762093341375627893251064284854550683090289244326428531870185742069661263695374185944997371146406463061296320874619629222702687248540071
n2 = 29134539279166202870481433991757912690660276008269248696385264141132377632327390980628416297352239920763325399042209616477793917805265376055304289306413455729727703925501462290572634062308443398552450358737592917313872419229567573520052505381346160569747085965505651160232449527272950276802013654376796886259
enc1 = 4813040476692112428960203236505134262932847510883271236506625270058300562795805807782456070685691385308836073520689109428865518252680199235110968732898751775587988437458034082901889466177544997152415874520654011643506344411457385571604433702808353149867689652828145581610443408094349456455069225005453663702
enc2 = 2343495138227787186038297737188675404905958193034177306901338927852369293111504476511643406288086128052687530514221084370875813121224208277081997620232397406702129186720714924945365815390097094777447898550641598266559194167236350546060073098778187884380074317656022294673766005856076112637129916520217379601


def phi_factor(n, phi):
    # n=pq
    # phi=(p-1)(q-1)=n-(p+q)+1
    ppq = n - phi + 1
    # (x-p)(x-q)=x^2-(p+q)x+n
    a = 1
    b = -ppq
    c = n
    D = b ^ 2 - 4 * a * c
    if is_square(D):
        sD = sqrt(D)
        return (-b + sD) / (2 * a), (-b - sD) / (2 * a)


for c in continued_fraction(n1 / n2).convergents():
    # n1 / n2 ~= x / k
    x = c.numer()
    k = c.denom()
    if k.nbits() < 250 or x.nbits() < 250:
        continue
    if k.nbits() > 260 or x.nbits() > 260:
        break
    if gcd(k, e) != 1:
        continue
    cc = crt([-inverse_mod(k, e), 0], [e, x])  # phi = cc (mod ex)
    s = cc + ((n1 - cc) // (e * x) - 10) * (e * x)  # bruteforce phi ~= n1
    for i in range(20):
        res = phi_factor(n1, s)
        if res:
            print(res)
            p, r = res
            d = inverse_mod(e, (p - 1) * (r - 1))
            m = power_mod(enc1, d, n1)
            print(long_to_bytes(m))
            phi2 = k * (p - 1) * (r - 1) // x
            q, s = phi_factor(n2, phi2)
            print((q, s))
            d2 = inverse_mod(e, (p - 1) * (r - 1))
            m2 = power_mod(enc2, d2, n2)
            print(long_to_bytes(m2))
            exit()
        s += e * x