Crypto CTF 2023 WriteUps

今年一樣與 isanapap 參加了今年的 Crypto CTF,在 6 個多小時之後 AK 並再次拿下第一名。

* 標記的題目都是代表隊友解的題目,我再自己 upsolve

Easy

Suction

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

from Crypto.Util.number import *
from flag import flag

def keygen(nbit, r):
while True:
p, q = [getPrime(nbit) for _ in '__']
e, n = getPrime(16), p * q
phi = (p - 1) * (q - 1)
if GCD(e, phi) == 1:
N = bin(n)[2:-r]
E = bin(e)[2:-r]
PKEY = N + E
pkey = (n, e)
return PKEY, pkey

def encrypt(msg, pkey, r):
m = bytes_to_long(msg)
n, e = pkey
c = pow(m, e, n)
C = bin(c)[2:-r]
return C

r, nbit = 8, 128
PKEY, pkey = keygen(nbit, r)
print(f'PKEY = {int(PKEY, 2)}')
FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
enc = encrypt(FLAG, pkey, r)
print(f'enc = {int(enc, 2)}')

簡單來說這題有 256 bit 的 RSA,但是 都少了 lowest 8 bits。這邊我是直接爆搜 的最後 8 bits 去硬分解,然後得到 之後再去搜 的空間找到真正的 解出 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
from tqdm import tqdm
from Crypto.Util.number import *

PKEY = 55208723145458976481271800608918815438075571763947979755496510859604544396672
ENC = 127194641882350916936065994389482700479720132804140137082316257506737630761

e_msb = int(bin(PKEY)[-8:], 2)
n_msb = int(bin(PKEY)[2:-8], 2)
# for i in tqdm(range(14, 256)):
# if i % 2 == 0:
# continue
# n = (n_msb << 8) + i
# print('trying', i)
# fs = factor(n)
# if len(fs) == 2:
# print(i, n, fs)

p = 188473222069998143349386719941755726311
q = 292926085409388790329114797826820624883
n = p * q
assert (n >> 8) == n_msb
phi = (p - 1) * (q - 1)

for i in tqdm(range(256)):
e = (e_msb << 8) + i
try:
d = pow(e, -1, phi)
for j in range(256):
m = pow((ENC << 8) + j, d, n)
flag = long_to_bytes(m)
if flag.isascii():
print(flag)
except:
pass
# CCTF{6oRYGy&Dc$G2ZS}

Medium

*Derik

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import C, e, d, p, q, r, flag

O = [1391526622949983, 2848691279889518, 89200900157319, 31337]

assert isPrime(e) and isPrime(d) and isPrime(p) and isPrime(q) and isPrime(r)
assert C[0] * p - C[1] * q >= 0
assert C[2] * q - C[3] * r >= 0
assert C[4] * r - C[5] * p >= 0
assert (C[0] * p - C[1] * q) ** e + (C[2] * q - C[3] * r) ** e + (C[4] * r - C[5] * p) ** e == d * (C[0] * p - C[1] * q) * (C[2] * q - C[3] * r) * (C[4] * r - C[5] * p)
assert C[6] * e - C[7] * d == O[3]

n = e * d * p * q * r
m = bytes_to_long(flag)
c = pow(m, 65537, n)
print(f'C = {C}')
print(f'c = {c}')

C[6], C[7]10543, 4,而 e 又出現在 exponent 所以應該不大,一個最可能的解是 。這樣的話會變成要解 ,明顯是一條橢圓曲線。透過 sage 轉換之後 enumerate 一下找到全部為正整數的 ,然後反過來得到 之後就可以解出 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
from itertools import permutations
from Crypto.Util.number import long_to_bytes

# fmt: off
O = [1391526622949983, 2848691279889518, 89200900157319, 31337]
C = [5960650533801939766973431801711817334521794480800845853788489396583576739362531091881299990317357532712965991685855356736023156123272639095501827949743772, 6521307334196962312588683933194431457121496634106944587943458360009084052009954473233805656430247044180398241991916007097053259167347016989949709567530079, 1974144590530162761749719653512492399674271448426179161347522113979158665904709425021321314572814344781742306475435350045259668002944094011342611452228289, 2613994669316609213059728351496129310385706729636898358367479603483933513667486946164472738443484347294444234222189837370548518512002145671578950835894451, 8127380985210701021743355783483366664759506587061015828343032669060653534242331741280215982865084745259496501567264419306697788067646135512747952351628613, 5610271406291656026350079703507496574797593266125358942992954619413518379131260031910808827754539354830563482514244310277292686031300804846114623378588204, 10543, 4]
ct = 80607532565510116966388633842290576008441185412513199071132245517888982730482694498575603226192340250444218146275844981580541820190393565327655055810841864715587561905777565790204415381897361016717820490400344469662479972681922265843907711283466105388820804099348169127917445858990935539611525002789966360469324052731259957798534960845391898385316664884009395500706952606508518095360995300436595374193777531503846662413864377535617876584843281151030183895735511854
# fmt: on

# guess, otherwise exponent will be too big
e, d = 3, 73
assert C[6] * e - C[7] * d == O[3]

# solve a^3+b^3+c^3=d*a*b*c
a, b, c = QQ["a, b, c"].gens()
phi = EllipticCurve_from_cubic(a ^ 3 + b ^ 3 + c ^ 3 - d * a * b * c)
G = phi.codomain().gen(0)

Mi = matrix([[C[0], -C[1], 0], [0, C[2], -C[3]], [-C[5], 0, C[4]]]).inverse()
phii = phi.inverse()
for i in range(-5, 5):
print(i)
x, y, z = phii(i * G)
assert x ^ 3 + y ^ 3 + z ^ 3 == d * x * y * z
if all([x < 0 for x in (x, y, z)]):
x, y, z = -x, -y, -z
if all([x > 0 for x in (x, y, z)]):
for perm in permutations((x, y, z)):
p, q, r = Mi * vector(perm)
mul = lcm(lcm(p.denominator(), q.denominator()), r.denominator())
div = gcd(gcd(p.numerator(), q.numerator()), r.numerator())
p, q, r = [ZZ(mul * i / div) for i in [p, q, r]]
assert (C[0] * p - C[1] * q) ** e + (C[2] * q - C[3] * r) ** e + (
C[4] * r - C[5] * p
) ** e == d * (C[0] * p - C[1] * q) * (C[2] * q - C[3] * r) * (
C[4] * r - C[5] * p
)
if all([p.is_integer() and is_pseudoprime(p) for p in (p, q, r)]):
print("Found")
break
else:
continue
break

n = e * d * p * q * r
phi = (e - 1) * (d - 1) * (p - 1) * (q - 1) * (r - 1)
d = pow(65537, -1, phi)
pt = pow(ct, d, n)
print(long_to_bytes(pt))

Barak

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

from Crypto.Util.number import *
from flag import flag

def on_barak(P, E):
c, d, p = E
x, y = P
return (x**3 + y**3 + c - d*x*y) % p == 0

def add_barak(P, Q, E):
if P == (0, 0):
return Q
if Q == (0, 0):
return P
assert on_barak(P, E) and on_barak(Q, E)
x1, y1 = P
x2, y2 = Q
if P == Q:
x3 = y1 * (c - x1**3) * inverse(x1**3 - y1**3, p) % p
y3 = x1 * (y1**3 - c) * inverse(x1**3 - y1**3, p) % p
else:

x3 = (y1**2*x2 - y2**2*x1) * inverse(x2*y2 - x1*y1, p) % p
y3 = (x1**2*y2 - x2**2*y1) * inverse(x2*y2 - x1*y1, p) % p
return (x3, y3)

def mul_barak(m, P, E):
if P == (0, 0):
return P
R = (0, 0)
while m != 0:
if m & 1:
R = add_barak(R, P, E)
m = m >> 1
if m != 0:
P = add_barak(P, P, E)
return R

def rand_barak(E):
c, d, p = E
while True:
y = randint(1, p - 1)
K = Zmod(p)
P.<x> = PolynomialRing(K)
f = x**3 - d*x*y + c + y^3
R = f.roots()
try:
r = R[0][0]
return (r, y)
except:
continue

p = 73997272456239171124655017039956026551127725934222347
d = 68212800478915688445169020404812347140341674954375635
c = 1
E = (c, d, p)

P = rand_barak(E)

FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
m = bytes_to_long(FLAG)
assert m < p
Q = mul_barak(m, P, E)
print(f'P = {P}')
print(f'Q = {Q}')

這題要在一條未知的曲線所構成的群上解 dlog,曲線是

先檢查一下 curve 是什麼 curve:

1
2
3
4
sage: x,y=ZZ['x,y'].gens()
sage: eq=x^3+y^3+1-68212800478915688445169020404812347140341674954375635*x*y
sage: Curve(eq).genus()
1

所以是 Genus 1,也就是橢圓曲線。然後去 Explicit-Formulas Database 可以知道它應該是 Hessian curves/Twisted Hessian curves,所以理論上可以找 paper 看看有沒有寫轉回 Weierstrass form 的公式。

不過這邊我懶得查 paper,想直接利用 sage 內建的 EllipticCurve_from_cubic 來做,不過它的輸入需要是一個 a homogeneous cubic in three variables with rational coefficients 才行。

這邊先利用 projective coodinate 的性質把原本的 換回 ,用 代換可以得到 ,確實符合。然後再用 sage 內建的那些操作可發現轉換過去的橢圓曲線 order 相當 smooth,所以直接 dlog 搞定。

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 long_to_bytes

p = 73997272456239171124655017039956026551127725934222347
d = 68212800478915688445169020404812347140341674954375635
c = 1

F = GF(p)

x, y, z = QQ["x,y,z"].gens()
eq = x ^ 3 + y ^ 3 + c * z ^ 3 - d * x * y * z
phi = EllipticCurve_from_cubic(eq)
E = phi.codomain().change_ring(GF(p))
P = (
71451574057642615329217496196104648829170714086074852,
69505051165402823276701818777271117086632959198597714,
)
Q = (
40867727924496334272422180051448163594354522440089644,
56052452825146620306694006054673427761687498088402245,
)

fx, fy, fz = map(lambda f: f.change_ring(F), phi.defining_polynomials())
phiP = lambda x, y, z=1: E(fx(x, y, z) / fz(x, y, z), fy(x, y, z) / fz(x, y, z))
EP = phiP(*P)
EQ = phiP(*Q)
x = discrete_log(EQ, EP, operation="+")
print(x)
od = EP.order() # the generator doesn't have full order
print(
[
flag
for i in range(E.order() // od)
if (flag := long_to_bytes(int(x + od * i))).isascii()
]
)
# CCTF{_hE5S!4n_f0rM_0F_3CC!!}

Risk

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

from Crypto.Util.number import *
from secret import m, flag

def genPrime(m, nbit):
assert m >= 2
while True:
a = getRandomNBitInteger(nbit // m)
r = getRandomNBitInteger(m ** 2 - m + 2)
p = a ** m + r
if isPrime(p):
return (p, r)

def genkey(m, nbit):
p, r = genPrime(m, nbit // 2)
q, s = genPrime(m, nbit // 2)
n = p * q
e = r * s
return (e, n)

def encrypt(msg, pkey):
e, n = pkey
m = bytes_to_long(msg)
c = pow(m, e, n)
return c

pkey = genkey(m, 2048)
enc = encrypt(flag, pkey)

print(f'pkey = {pkey}')
print(f'enc = {enc}')

這題的 ,而 。因為 是 28 bits 所以可以回推

看到這題就讓我想到之前出過的 Power RSA,裡面有提到 A New Attack on Special-Structured RSA Primes 這篇文章,內容完美符合這題的情況。

不過我這邊發現因為 真的太小了 (compared to ),可得 ,所以

由於 遠比 小,。同時又有 ,所以這邊有個相加與相乘的關係,所以 是以下多項式的兩根:

得到 之後 gcd 就有 了,然後就可以解出 了。不過由於 不互質所以要直接 enumerate 所有可能的 再 CRT 找 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
from Crypto.Util.number import long_to_bytes

e, n = (
150953688,
373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818881164334490044163316692588337720342646339764174333821950301279825316497898035760524780198230860089280791887363472060435443944632303774987556026740232641561706904946900169858650106994947597642013168757868017723456208796677559254390940651802333382820063200360490892131573853635471525711894510477078934343423255983,
)
enc = 275574424285842306309073814038154403551700455145115884031072340378743712325975683329051874910297915882286569143815715537085387363420246497061870251520240399514896001311724695996978111559476733709139080970977190150345474341853495386364275702356438666152069791355990718058189043717952080875207858163490627801836274404446661613239167700736337269924479349700031535265765885064606399858172168036794462235707003475360358004643720927563261787867952228496769300443415094124132722170498229611285689671203272698693505808912907778910378274197503048226322090611405601517624884408718689404556983397217070272851442351897456769883
m = 4


def solve_quadratic(a, b, c):
d = b**2 - 4 * a * c
r1 = (-b + sqrt(d)) / (2 * a)
r2 = (-b - sqrt(d)) / (2 * a)
return r1, r2


ab, _ = n.nth_root(4, truncate_mode=True)
a4s_b4r = (n - e) % (ab**4)
a4b4rs = ab**4 * e
a4s, b4r = solve_quadratic(1, -a4s_b4r, a4b4rs)
a = gcd(a4s, ab)
b = gcd(b4r, ab)
s = a4s // a**4
r = b4r // b**4
assert r * s == e
p = a**4 + r
q = b**4 + s
assert p * q == n

# phi = (p - 1) * (q - 1)
# d = pow(e, -1, phi)
# m = pow(enc, d, n)
# print(long_to_bytes(m))

for mp in GF(p)(enc).nth_root(e, all=True):
for mq in GF(q)(enc).nth_root(e, all=True):
m = crt([ZZ(mp), ZZ(mq)], [p, q])
flag = long_to_bytes(m)
if flag.isascii():
print(flag)
# CCTF{S!mP1E_A7t4cK_0n_SpEc1aL-5trucTur3D_RSA_pR1me5!}

Bertrand

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

import sys
import math
import functools
from PIL import Image
from random import randint
import string
from secret import flag, key, n

def pad(s, l):
while len(s) < l:
s += string.printable[randint(0, 61)]
return s

def sox(n, d):
x, y, t = 0, 0, d
for s in range(n - 1):
u = 1 & t // 2
v = 1 & t ^ u
x, y = spin(2**s, x, y, u, v)
x += 2**s * u
y += 2**s * v
t = t // 4
return x, y

def spin(n, x, y, u, v):
if v == 0:
if u == 1:
x = n - 1 - x
y = n - 1 - y
x, y = y, x
return x, y

def encrypt(msg, key, n):
_msg = pad(msg, n ** 2)
_msg, _key = [ord(_) for _ in _msg], [ord(_) for _ in key]
img = Image.new('RGBA', (n, n), 'darkblue')
pix = img.load()

for _ in range(len(key)):
w = len(_key)
h = n**2 // w + 1
arr = [[_msg[w*x + y] if w*x + y < n**2 else None for x in range(h)] for y in range(w)]
_conf = sorted([(_key[i], i) for i in range(w)])
_marshal = [arr[_conf[i][1]] for i in range(w)]
_msg = functools.reduce(lambda a, r: a + _marshal[r], range(w), [])
_msg = list(filter(lambda x: x is not None, _msg))
_msg = [(_msg[_] + _key[_ % w]) % 256 for _ in range(n**2)]

for d in range(n**2):
x, y = sox(n, d)
pix[x,y] = (_msg[d], _msg[d], _msg[d])
keysum = sum(_key) if w > 0 else 0
orient = keysum % 4
img = img.rotate(90*orient)
return img

assert len(key) == 3
img = encrypt(flag, key, n)
img.save('enc.png')

用了一些奇怪的操作對 message 加密過後塞到 image 然後旋轉後輸出。因為旋轉只有 4 種所以可以爆一下就得到迴圈結束後 _msg 的最後狀態。之後因為 key 長度只有 3,稍微爆一下 [0, 1, 2] 的六種排列組合 (_conf) 就能分別用 z3 處理,配合已知 flag prefix 得到 flag 和 key。

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
import sys
import math
import functools
from PIL import Image
from random import randint
import string
import itertools
import z3


def pad(s, l):
while len(s) < l:
s += string.printable[randint(0, 61)]
return s


def sox(n, d):
x, y, t = 0, 0, d
for s in range(n - 1):
u = 1 & t // 2
v = 1 & t ^ u
x, y = spin(2**s, x, y, u, v)
x += 2**s * u
y += 2**s * v
t = t // 4
return x, y


def spin(n, x, y, u, v):
if v == 0:
if u == 1:
x = n - 1 - x
y = n - 1 - y
x, y = y, x
return x, y


n = 256
img = Image.open("enc.png")
img = img.rotate(90 * 1) # guess
pix = img.load()
msg = []
for d in range(n**2):
x, y = sox(n, d)
msg.append(pix[x, y][0])


def try_conf(conf):
key_sym = [z3.BitVec("key_%d" % i, 8) for i in range(3)]
msg_sym = [z3.BitVec("msg_%d" % i, 8) for i in range(n**2)]
msg_arr = msg_sym[:]
for _ in range(len(key_sym)):
w = len(key_sym)
h = n**2 // w + 1
arr = [
[msg_arr[w * x + y] if w * x + y < n**2 else None for x in range(h)]
for y in range(w)
]
_marshal = [arr[conf[i]] for i in range(w)]
msg_arr = functools.reduce(lambda a, r: a + _marshal[r], range(w), [])
msg_arr = list(filter(lambda x: x is not None, msg_arr))
msg_arr = [(msg_arr[_] + key_sym[_ % w]) % 256 for _ in range(n**2)]
sol = z3.Solver()
for i in range(n**2):
sol.add(msg_arr[i] == msg[i])
for x, y in zip(msg_sym, b"CCTF{"):
sol.add(x == y)
if sol.check() == z3.sat:
m = sol.model()
print([m.eval(x) for x in key_sym])
print(bytes([m.eval(x).as_long() for x in msg_sym])[:100])


for conf in itertools.permutations(range(3)):
# correct conf = (1, 2, 0)
print(conf)
try_conf(conf)
# CCTF{3nCrypTioN_8Y_c0lUmn4R_7rAnSp05it!On!}

Resuction

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

from Crypto.Util.number import *
from flag import flag

from decimal import *

def keygen(nbit, r):
while True:
p, q = [getPrime(nbit) for _ in '__']
d, n = getPrime(64), p * q
phi = (p - 1) * (q - 1)
if GCD(d, phi) == 1:
e = inverse(d, phi)
N = bin(n)[2:-r]
E = bin(e)[2:-r]
PKEY = N + E
pkey = (n, e)
return PKEY, pkey

def encrypt(msg, pkey, r):
m = bytes_to_long(msg)
n, e = pkey
c = pow(m, e, n)
C = bin(c)[2:-r]
return C

r, nbit = 8, 1024
PKEY, pkey = keygen(nbit, r)
print(f'PKEY = {int(PKEY, 2)}')
FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
enc = encrypt(FLAG, pkey, r)
print(f'enc = {int(enc, 2)}')

類似前面的 suction,不過這次 有 2048 bit,但 只有 64 bit 所以大概是可以爆一下 的 8 bits 用 wiener/boneh-durfee attack 之類的攻擊求解。

我這邊用 boneh-dufee 的方法,把 當作以知的,那麼可以寫出

其中 的未知 8 bit 而 ,而 應該和 差不多大,所以 coppersmith 就能求出

之後就有 ,然後爆一下 檢查 就能得到

最後爆一下 就能解出 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
from tqdm import tqdm
from Crypto.Util.number import *

PKEY = 14192646310719975031517528381795548241077678859071194396837281472399230674325587198691913743313024193030641258581477544395982020385534616950314446352119543012689979705497443206671093873748633162188213109347667494028713308821945628880987033909436936504594085029207071182583896573425433818693447573712242776054326253393149643818428222532313129014785625379928796322492111783102063504659053965652092334907431265629283336869752591405010801363428649651892548988084920295512198406822149854508798413366425646089176325412867633899847841343293434518769693835679828109184625256833518392375615524221729773443578746961887429674099018040291053535429314874943299587513900900515776980848746070077651676814430155460898107362207677739452859298842563030631706907437662807884529549746843462830493900480079096937402325307522965877069080418178692616875205678928420840955518031258855869218152431304423803589723140983606576549207164114711076498723237274262054605174412193097533550076687418481230734706280737017543741247718967059747548710091320650704988384742281590019869955579949961574733610565593105027342454880292474482792325237942870408329807427182014062811782475262070063065860763705715879581562335668163076088547827008755841277828137570366416095778
enc = 93313196155732054514477836642637636744872135106456047659057794344503071105783322399713135615723000054324693644981340568454628360027598469597864407205974007198804288563284521413279406211756674451582156555173212403946908121125010635246043311803494356106191509999360722019559999844621905376368824621365540442906142224342650371557766313381899279520110833822291649001754956653102495882094754863493058001964760438040783400782352466943990226083197340594364084294954324101604417550048379969516185353765224920719355485680872367930581872987972421836853197205534334204586713387469939986387582911728909524428102693874671302382

n_msb = int(bin(PKEY)[2 : 2 + 2048 - 8], 2)
e_msb = int(bin(PKEY)[2 + 2048 - 8 :], 2)

load("~/workspace/single_files/coppersmith.sage")

"""
s =p+q
ed=1+k*(n'+y-s+1)
=1+k*(n-t)
t =s-y-1
"""

for i in tqdm(range(256)):
e = (e_msb << 8) + i
k, t = Zmod(e)["k, t"].gens()
f = 1 + k * (n_msb * 2**8 - t)
rs = small_roots(f, (2**64, 2**1025), m=3, d=4)
if rs:
print(i, rs)
# i = 171
break


rs = [
(
6823792554575489397,
339429557959585189701831352324590530872763312539010344903142994882560384526456848728524471256411137222762385478052025872755202468572218239287614181033902856793017322338973563489979888570193807877377040282961710845331494163541163584827604616161828513831660392743437795710563167837376965534351712230091159840872,
)
]
k, t = map(ZZ, rs[0])
phi = n_msb * 2**8 - t
for i in tqdm(range(256)):
n = n_msb * 2**8 + i
if pow(2, phi, n) == 1:
break
d = pow(e, -1, phi)

for i in tqdm(range(256)):
m = pow((enc << 8) + i, d, n)
flag = long_to_bytes(m)
if flag.isascii():
print(flag)
# CCTF{aIr_pr3s5urE_d!Ff3rEn7i4L_8eTw3eN_ArEa5!}

後來想了一下這題用 wiener (continued fraction) 應該更適合點,因為 真的很小。原本的 稍微改寫可得 ,不過實際上要用 去近似 才能找到 。剩下就隨便爆一下就有了。

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

PKEY = 14192646310719975031517528381795548241077678859071194396837281472399230674325587198691913743313024193030641258581477544395982020385534616950314446352119543012689979705497443206671093873748633162188213109347667494028713308821945628880987033909436936504594085029207071182583896573425433818693447573712242776054326253393149643818428222532313129014785625379928796322492111783102063504659053965652092334907431265629283336869752591405010801363428649651892548988084920295512198406822149854508798413366425646089176325412867633899847841343293434518769693835679828109184625256833518392375615524221729773443578746961887429674099018040291053535429314874943299587513900900515776980848746070077651676814430155460898107362207677739452859298842563030631706907437662807884529549746843462830493900480079096937402325307522965877069080418178692616875205678928420840955518031258855869218152431304423803589723140983606576549207164114711076498723237274262054605174412193097533550076687418481230734706280737017543741247718967059747548710091320650704988384742281590019869955579949961574733610565593105027342454880292474482792325237942870408329807427182014062811782475262070063065860763705715879581562335668163076088547827008755841277828137570366416095778
enc = 93313196155732054514477836642637636744872135106456047659057794344503071105783322399713135615723000054324693644981340568454628360027598469597864407205974007198804288563284521413279406211756674451582156555173212403946908121125010635246043311803494356106191509999360722019559999844621905376368824621365540442906142224342650371557766313381899279520110833822291649001754956653102495882094754863493058001964760438040783400782352466943990226083197340594364084294954324101604417550048379969516185353765224920719355485680872367930581872987972421836853197205534334204586713387469939986387582911728909524428102693874671302382

n_msb = int(bin(PKEY)[2 : 2 + 2048 - 8], 2)
e_msb = int(bin(PKEY)[2 + 2048 - 8 :], 2)


nn = n_msb << 8
ee = e_msb << 8

cf = continued_fraction(ee / (nn - 2**1025))
for c in cf.convergents():
print(c)
if c.denominator() <= 2**64:
k = c.numerator()
d = c.denominator()
if k == 0:
continue
for i in range(256):
e = ee + i
phi = (e * d - 1) // k
if (phi >> 1500) == (nn >> 1500):
print("try phi", phi)
for j in range(256):
n = nn + j
if pow(2, phi, n) == 1:
print("found", n, e, d)
for i in tqdm(range(256)):
m = pow((enc << 8) + i, d, n)
flag = long_to_bytes(m)
if flag.isascii():
print(flag)
exit()

ASIv1

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

from Crypto.Util.number import *
from flag import flag

def base(n, l):
D = []
while n > 0:
n, r = divmod(n, l)
D.append(r)
return ''.join(str(d) for d in reversed(D)) or '0'

def asiv_prng(seed):
l = len(seed)
_seed = base(bytes_to_long(seed), 3)
_seed = [int(_) for _ in _seed]
_l = len(_seed)
R = [[getRandomRange(0, 3) for _ in range(_l)] for _ in range(_l**2)]
S = []
for r in R:
s = 0
for _ in range(_l):
s += (r[_] * _seed[_]) % 3
# s += getRandomRange(0, 3)
s %= 3
S.append(s)
return R, S

seed = flag.lstrip(b'CCTF{').rstrip(b'}')
R, S = asiv_prng(seed)

f = open('output.txt', 'w')
f.write(f'R = {R}\nS = {S}')
f.close()

一個很奇怪的 RNG,不過一眼就能看出是直接解 linear system 搞定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from sage.all import *
from Crypto.Util.number import *
from collections import Counter

with open("output.txt") as f:
exec(f.read())

l = len(R[0]) + 5
sol = matrix(Zmod(3), R[:l]).solve_right(vector(S[:l]))

flag = 0
for x in sol:
flag = flag * 3 + ZZ(x)
print(long_to_bytes(flag))

# CCTF{3Xpl0i7eD_bY_AtT4ck3r!}

Keymoted

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

from Crypto.Util.number import *
from flag import flag

def gen_koymoted(nbit):
p = getPrime(nbit)
a, b = [randint(1, p - 1) for _ in '__']
Ep = EllipticCurve(GF(p), [a, b])
tp = p + 1 - Ep.order()
_s = p ^^ ((2 ** (nbit - 1)) + 2 ** (nbit // 2))
q = next_prime(2 * _s + 1)
Eq = EllipticCurve(GF(q), [a, b])
n = p * q
tq = q + 1 - Eq.order()
e = 65537
while True:
if gcd(e, (p**2 - tp**2) * (q**2 - tq**2)) == 1:
break
else:
e = next_prime(e)
pkey, skey = (n, e, a, b), (p, q)
return pkey, skey

def encrypt(msg, pkey, skey):
n, e, a, b = pkey
p, q = skey
m = bytes_to_long(msg)
assert m < n
while True:
xp = (m**3 + a*m + b) % p
xq = (m**3 + a*m + b) % q
if pow(xp, (p-1)//2, p) == pow(xq, (q-1)//2, q) == 1:
break
else:
m += 1
eq1, eq2 = Mod(xp, p), Mod(xq, q)
rp, rq = sqrt(eq1), sqrt(eq2)
_, x, y = xgcd(p, q)
Z = Zmod(n)
x = (Z(rp) * Z(q) * Z(y) + Z(rq) * Z(p) * Z(x)) % n
E = EllipticCurve(Z, [a, b])
P = E(m, x)
enc = e * P
return enc

nbit = 256
pkey, skey = gen_koymoted(nbit)
enc = encrypt(flag, pkey, skey)

print(f'pkey = {pkey}')
print(f'enc = {enc}')

這題在 上使用類似 RSA 的方法加密 flag,而 所以一定得分解 才行。

它 keygen 的方法是先生成 ,然後 flip 兩個固定的 bit 變成 之後

因為那兩個 bit 是固定位置的,這邊把它訂為第 和第 個 bit,而 的那個 bit 由於正好是 p.bit_length() - 1,所以 xor 之後就相當於 ,所以可以把整個生成方法這樣改寫:

這邊 那邊的正負不知道,但是可以猜,而 很小所以直接爆,這樣就變成一個二次多項式求根了。

分解之後就拿 求 inverse 當作 解密 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
from Crypto.Util.number import long_to_bytes

pkey = (
6660938713055850877314255610895820875305739186102790477966786501810416821294442374977193379731704125177528590285016474818841859956990486067573436301232301,
65537,
5539256645640498184116966196249666621079506508209770360679460869295427007578,
20151017657582479433586370393795140515103572865771721775868586710594524816458,
)
encx = 6641320679869421443758875467781930795132746694454926965779628505713445486895274490835545942727970688359873955019634877304270220728625521646208912044469433
ency = 2856872654927815636828860866843721158889474116106462420201092148493803550131351543372740950198853438539317164093538508795630146854596724019329887894933972

n, e, a, b = pkey
nbit = 256
pp = ZZ["pp"].gen()
p = 2 ** (nbit - 1) + pp
s = pp + 2 ** (nbit // 2) # guess
for t in range(1000):
q = 2 * s + 1 + t
f = p * q - n
rs = f.roots()
if rs:
print(t, rs)
break
p = 2 ** (nbit - 1) + rs[0][0]
q = n // p
assert p * q == n
Z = Zmod(n)
E = EllipticCurve(Z, [a, b])
C = E(encx, ency)
Ep = EllipticCurve(GF(p), [a, b])
Eq = EllipticCurve(GF(q), [a, b])
od = Ep.order() * Eq.order()
d = pow(e, -1, od)
M = d * C
print(long_to_bytes(int(M.xy()[0])))

Hard

Marjan

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

import sys
from Crypto.Util.number import *
from hashlib import sha256
from flag import flag


p = 114863632180633827211184132915225798242263961691870412740605315763112513729991
A = -3
B = 105675527217961035404524512435875047840495516468907806313576241823653895562912
E = EllipticCurve(GF(p), [A, B])
G = E.random_point()
_o = E.order()
original_msg = 'I love all cryptographers!!!'

def die(*args):
pr(*args)
quit()

def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()

def sc():
return sys.stdin.buffer.readline()

def keygen(E):
skey = randint(1, _o)
pkey = skey * G
return pkey, skey

def encrypt(msg, pkey):
e, l = randint(1, _o), len(msg)
m1, m2 = bytes_to_long(msg[:l // 2]), bytes_to_long(msg[l // 2:])
assert m1 < p and m2 < p
e1, e2 = (e * pkey).xy()
c1, c2 = m1 * e1 % p, m2 * e2 % p
return (c1, c2, e * G)

def sign(msg, skey):
_tail = bytes_to_long(sha256(str(skey).encode('utf-8')).digest()) % (1 << 24)
while True:
K = [randint(1, 2**255) // (1 << 24) + _tail for _ in '__']
r, s = int((K[0] * G).xy()[0]), int((K[1] * G).xy()[1])
if r * s != 0:
break
h = bytes_to_long(sha256(msg).digest())
t = inverse(K[0], _o) * (h * r - s * skey) % _o
return (r, s, t)

def verify(msg, pkey, _sign):
r, s, t = [int(_) % _o for _ in _sign]
h = bytes_to_long(sha256(msg.encode('utf-8')).digest())
u = int(h * r * inverse(t, _o) % _o)
v = int(s * inverse(t, _o) % _o)
# u = h * r * inverse(t, _o) % _o
# v = s * inverse(t, _o) % _o
_R = (u * G - v * pkey).xy()[0]
return _R == r

def main():
border = "|"
pr(border*72)
pr(border, "Hi all, now it's time to solve a probably simple ECC challenge about", border)
pr(border, "encryption and signing in elliptic curves! Follow the questions and ", border)
pr(border, "find the secret flag, are you ready!? ", border)
pr(border*72)

pkey, skey = keygen(E)

while True:
pr("| Options: \n|\t[E]ncrypt a message! \n|\t[G]et the flag \n|\t[P]ublic Key \n|\t[S]ign a message \n|\t[V]erify signature \n|\t[Q]uit")
ans = sc().decode().lower().strip()
if ans == 'e':
pr(border, 'Send your message here: ')
_msg = sc()
_enc = encrypt(_msg, pkey)
pr(border, f'enc = {_enc}')
elif ans == 'g':
pr(border, 'You should send the valid signature for my given message!')
pr(border, 'Send the signature of original message here: ')
_sgn = sc().split(b',')
try:
_sgn = [int(_) for _ in _sgn]
if verify(original_msg, pkey, _sgn):
die(border, f'Congratz! You got the flag: {flag}')
else:
pr(border, 'Your signature is not correct!')
except:
import traceback; traceback.print_exc()
pr(border, 'Try to send valid signature!')
continue
elif ans == 's':
pr(border, 'Send your message to sign: ')
_msg = sc()
if len(_msg) >= 10:
die(border, 'Sorry, I sign only short messages! :/')
_sgn = sign(_msg, skey)
pr(border, f'sgn = {_sgn}')
elif ans == 'v':
pr(border, 'Send your signature to verify: ')
_sgn = sc().split(b',')
try:
_sgn = [int(_) for _ in _sgn]
pr(border, 'Send your message: ')
_msg = sc()
if verify(_msg, pkey, _sgn):
pr(border, 'Your message successfully verified :)')
else:
pr(border, 'Verification failed :(')
except:
pr(border, 'Try to send valid signature!')
continue
elif ans == 'p':
pr(border, f'pkey = {pkey}')
pr(border, f'G = {G}')
elif ans == 'q':
die(border, 'Quitting...')
else:
die(border, 'You should select valid choice!')

if __name__ == '__main__':
main()

這題有個類似 ECDSA 的 signature scheme,每個 signature 有 符合 ,其中 是 nonce 而 是 private key。不過 根據它生成的方法可知它一定不到 bits,所以可以 LLL 解出 ,進而求出

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
from sage.all import *
from pwn import process, remote, context
from Crypto.Util.number import *
from hashlib import sha256
import ast, os

p = 114863632180633827211184132915225798242263961691870412740605315763112513729991
A = -3
B = 105675527217961035404524512435875047840495516468907806313576241823653895562912
E = EllipticCurve(GF(p), [A, B])
G = E.random_point()
q = E.order()
original_msg = "I love all cryptographers!!!"
R = Zmod(q)

context.log_level = "debug"
# io = process(["sage", "Marjan.sage"])
io = remote("06.cr.yp.toc.tf", 13337)
io.sendline(b"p")
io.recvuntil(b"pkey = ")
pkey = E(ast.literal_eval(io.recvlineS().strip().replace(":", ",")))
io.recvuntil(b"G = ")
G = E(ast.literal_eval(io.recvlineS().strip().replace(":", ",")))


def sign(msg: bytes):
io.sendline(b"s")
io.sendline(msg)
io.recvuntil(b"sgn = ")
r, s, t = ast.literal_eval(io.recvlineS().strip())
h = bytes_to_long(sha256(msg + b"\n").digest())
return h, r, s, t


n_sigs = 16
sigs = [sign(os.urandom(4).hex().encode()) for _ in range(n_sigs)]
PR = PolynomialRing(R, ["d"] + [f"k{i}" for i in range(n_sigs)])
d, *ks = PR.gens()
eqs = []
for (h, r, s, t), k in zip(sigs, ks):
eqs.append(t * k - (h * r - s * d))
eqs2 = [f.sylvester_matrix(g, d).det() for f, g in zip(eqs, eqs[1:])]

M, v = Sequence(eqs2).coefficient_matrix()
print(vector(v))
L = block_matrix(ZZ, [[M.T.dense_matrix(), 1], [q, 0]])
bounds = [0] * len(eqs2) + [1 << (256 - 24)] * len(ks) + [1]
Q = diagonal_matrix([2**512 // b if b else 2**1024 for b in bounds])
L *= Q
L = L.LLL()
L /= Q
v = L[0]
if v[-1] < 0:
v = -v
print(v)
k_sol = vector(ZZ, v[len(eqs2) : -1])
d = (
eqs[0]
.subs({ks[0]: k_sol[0]})
.univariate_polynomial()
.roots(multiplicities=False)[0]
)
assert (
d
== eqs[1]
.subs({ks[1]: k_sol[1]})
.univariate_polynomial()
.roots(multiplicities=False)[0]
)
assert d * G == pkey


def sign(msg, skey):
_tail = bytes_to_long(sha256(str(skey).encode("utf-8")).digest()) % (1 << 24)
while True:
K = [randint(1, 2**255) // (1 << 24) + _tail for _ in "__"]
r, s = int((K[0] * G).xy()[0]), int((K[1] * G).xy()[1])
if r * s != 0:
break
h = bytes_to_long(sha256(msg).digest())
t = inverse(K[0], q) * (h * r - s * skey) % q
return (r, s, t)

def verify(msg, pkey, _sign):
r, s, t = [int(_) % q for _ in _sign]
h = bytes_to_long(sha256(msg.encode('utf-8')).digest())
u = h * r * inverse(t, q) % q
v = s * inverse(t, q) % q
_R = (u * G - v * pkey).xy()[0]
return _R == r

sig = sign(original_msg.encode(), d)
assert verify(original_msg, pkey, sig)
io.sendline(b"g")
io.recvuntil(b"here: ")
io.sendline(",".join(map(str, sig)).encode())
io.interactive()
# CCTF{L4T71c3_atTAck5_a9A!nS7_ECDSA!}

這題有個很坑的地方是你送 msg 過去的話它會 sign msg + b'\n' ...

Byeween

這題沒 code,nc 上去之後會出現這樣的訊息:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
> nc 06.cr.yp.toc.tf 33137
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Hi all, I have created a basic and simple cryptography task about |
| elliptic curve over rational field. Your mission is to find all |
| points Q over E such that 2 * Q = P, such that P is given. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Generating parameters, please wait...
| Options:
| [I]informations
| [S]ubmit points
| [Q]uit
I
| E = Elliptic Curve defined by y^2 = x^3 - 76479349401*x over Rational Field
| Q = (2740238460026645848168554718863025/9496587522097110856052646144 : -40938233945632940227696869615241088990456963438185/925446596757862314622073825244539026870272 : 1)
| Options:
| [I]informations
| [S]ubmit points
| [Q]uit
S
| Please send the points on elliptic curve one by one:

雖然他看起來符號有打錯,不過應該就是求 的 half point 而已,sage 很簡單就搞定了。

1
2
3
4
5
6
7
8
9
E = EllipticCurve(QQ, [-76479349401, 0])
Q = E(
2740238460026645848168554718863025 / 9496587522097110856052646144,
-40938233945632940227696869615241088990456963438185
/ 925446596757862314622073825244539026870272,
)
for x in Q.division_points(2):
print(",".join(map(str, x.xy())))
# CCTF{H4lVin9_pO!ntS_0n_3lLipT1C_cuRve5!}

Shevid

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

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from flag import flag

def gen_param(B):
while True:
a = randint(B >> 1, B)
b = randint(B >> 2, B >> 1)
p = 2**a * 3**b - 1
if is_prime(p):
return a, b

def gen_dmap(E):
return E.isogeny(E.lift_x(ZZ(1)), codomain = E)

def gen_tpt(E, a, b):
P, Q = [((p + 1) // 2**a) * _ for _ in E.gens()]
R, S = [((p + 1) // 3**b) * _ for _ in E.gens()]
return P, Q, R, S

def keygen(EC, b, P, Q, R, S):
skey = randint(1, 3**b)
T = R + skey * S
phi = EC.isogeny(T, algorithm = "factored")
_phi_dom, _phi_P, _phi_Q = phi.codomain(), phi(P), phi(Q)
return skey, _phi_dom, _phi_P, _phi_Q

a, b = gen_param(190)
p = 2**a * 3**b - 1

F.<x> = GF(p^2, modulus = x**2 + 1)
EC = EllipticCurve(F, [0, 6, 0, 1, 0])
P, Q, R, S = gen_tpt(EC, a, b)

print(f'P = {P.xy()}')
print(f'Q = {Q.xy()}')
print(f'R = {R.xy()}')
print(f'S = {S.xy()}')

skey, _phi_dom, _phi_P, _phi_Q = keygen(EC, b, P, Q, R, S)

print(f'_phi_dom = {_phi_dom}')
print(f'_phi_P = {_phi_P.xy()}')
print(f'_phi_Q = {_phi_Q.xy()}')

key = md5(long_to_bytes(skey)).digest()
iv = md5(str(skey).encode()).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
enc = cipher.encrypt(flag)

print(f'enc = {enc.hex()}')

一看就知道是之前被破解的 SIDH (An efficient key recovery attack on SIDH),而這也早就有了現成的 implementation 可以拿來用。只需要搞清楚各個參數的意義就行了。

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
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from hashlib import md5
from public_values_aux import generate_distortion_map

load("./castryck_decru_shortcut.sage")

x = QQ["x"].gen()
P = (
3799366067639160994711391413511701264777392349807255916259320256251336249666 * x
+ 633884628131689177031068067897867565283026098415356709331881575255526844055,
3967348484864888240941807454988077684669074109524399477973520952727771366997 * x
+ 2712354532382043232096058211997452093712477916671679907467703464009558475387,
)
Q = (
560486392227142181240528415381730657098132581407794833013161975335122628946 * x
+ 3215971074127995409351672272900519761566156375365764079386358523254177565572,
2231746347912007096335360835242707156884468521076802738444724241125548841199 * x
+ 1147378568798166954853288670809304301194478550602719730593160186622788033023,
)
R = (
2656280316115888204975052029900945854050191685154131031859911335618240136443 * x
+ 1127449111197960889758916770042950976852995868310602942974825430779982061546,
3477289737920472771668877366806058236254602770820629911886593813749930497839 * x
+ 4646016633241840360901490323351236375375727836768954121794139000985805816564,
)
S = (
2403139149412141532587482679318245468078604585804423116505024414375742701912 * x
+ 2772488504607240668919423445309052101443116827322741849326656561794480962717,
3356599382898540527962106232860239304405841217130774924490318752448476310798 * x
+ 2818004736373436361527915593539097434287090434842750370886675729711731978922,
)
# def eq(x, y):
# return y^2 -(x^3+6*x^2+1*x)
# eqs = [eq(*P) for P in (P, Q, R, S)]
# pmul = gcd(eqs[0].resultant(eqs[1]), eqs[2].resultant(eqs[3]))
# print(factor(pmul))

p = 4651852759096127491733667803074539573102288457512521355046899661762757394431
a = valuation(p + 1, 2)
b = valuation(p + 1, 3)
F = GF(p ^ 2, "a", modulus=x ^ 2 + 1)
E_start = EllipticCurve(F, [0, 6, 0, 1, 0])
E_start.set_order((p + 1) ^ 2)
P, Q, R, S = [E_start(P) for P in (P, Q, R, S)]

a2 = 6
a4 = (
2070374075904221348548347954672740119972290047985052548426161483408084160515 * x
+ 896749506444795652787374405713981306103783874504413776724865996633074195878
)
a6 = (
2497300913991521538985990865799426081199023429830552981773916386651958830387 * x
+ 4243320791854592301388975795466391442631117041175807728844738724691845270777
)
E_end = EllipticCurve(F, [0, a2, 0, a4, a6])
E_end.set_order((p + 1) ^ 2)
_phi_P = (
76437828586489590038329193939006186966443918785230388533883401536928551274 * x
+ 1854701339851606878866613257086348330205980107370562791121360193846610915298,
3614996124089236146025194675467338095830005859290616536023140003816221458491 * x
+ 1308394538776387115295908857102539180825411698539070801598965381200026966383,
)
_phi_Q = (
2350346337927935568113772636838467488287314266120334638991371449749383548230 * x
+ 3389994457403704259291228848441313337916860864318549296438418403582347527289,
3514523396038039657181009561828298688334341559779027220238590888980836781356 * x
+ 1132784636339236588815425424619354807485262558088269015122405460656452137103,
)
phi_P, phi_Q = [E_end(P) for P in (_phi_P, _phi_Q)]

P2 = P
Q2 = Q
P3 = R
Q3 = S

two_i = generate_distortion_map(E_start)
skey = CastryckDecruAttack(E_start, P, Q, E_end, phi_P, phi_Q, two_i, 4)

ct = bytes.fromhex(
"50d8ed352ccf3ce6d64b25e50ed67b832dcbcd94dcb7dc8293e813e0c83ace541abb61618d5f971ff5d24fab8a2e"
)

key = md5(long_to_bytes(skey)).digest()
iv = md5(str(skey).encode()).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
flag = cipher.decrypt(ct)
print(flag)
# CCTF{3FfiC!En7_k3Y_R3c0vErY_4tTacK_ON_SIDH!!!}

Tough

*ASIv2

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

from Crypto.Util.number import *
from flag import flag

def base(n, l):
D = []
while n > 0:
n, r = divmod(n, l)
D.append(r)
return ''.join(str(d) for d in reversed(D)) or '0'

def asiv_prng(seed):
l = len(seed)
_seed = base(bytes_to_long(seed), 3)
_l = len(_seed)
R = [[getRandomRange(0, 3) for _ in range(_l)] for _ in range(_l**2)]
S = []
for r in R:
s = 0
for _ in range(_l):
b = ((int(r[_]) + int(_seed[_])) % 3) % 2
s = s ^ b
S.append(s)
print(len(S))
return R, S

seed = flag.lstrip(b'CCTF{').rstrip(b'}')
R, S = asiv_prng(seed)

f = open('output.txt', 'w')
f.write(f'R = {R}\nS = {S}')
f.close()

和 ASIv1 很像,不過它會先 mod 3 再 mod 2,很難處理。這邊的關鍵是想辦法令一個函數 去代表那個運算:

如果有辦法把這個函數簡單的表達出來,就能在 上解 linear system 了。

可以先畫出個 的表格:

012
0010
1100
2001

假設說使用類似 one hot encoding 的方法,把 中的 如此做編碼 ():

然後再對 中的 用一個不同的編碼 ():

那麼可以發現 的表格和前面 長的一模一樣:

012
0010
1100
2001

所以可知 是一樣的,那麼原本的 b = ((int(r[_]) + int(_seed[_])) % 3) % 2 操作其實就變成了 b = g(int(r[_])) * h(int(_seed[_])),這邊的 * 要理解成 上的內積,由此這樣整個系統就變成線性的了。

所以只要先把原本 的矩陣的每個元素透過 做編碼,讓它變成 ,然後在 上解 就會得到一個被編碼過的 ,最後再把 透過 解碼回來就能得到

不過在解碼的過程中會發現有個問題是解碼時會找不到 的 preimage,例如 因為一些原因會出現在 之中。

稍微研究一下會發現這是因為 其實不是 full rank 的,儘管 dimension 有 ,但它的 rank 因為一些未知原因而固定是 ,所以有 維的 kernel。計算一下可以發現它長的意外整齊,大概像下面這樣:

1
2
3
4
111000000000...
000111000000...
000000111000...
...

這個意思就是說在 這個 encoding 其實不是一對一的,而是一對二,包含它的 bitwise inverse。所以這就代表 其實同時有 兩個 encoding,那麼在用 解碼時就多把這個考慮進去就好,最後解出來的 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
from collections import Counter
from Crypto.Util.number import *

with open("output.txt") as f:
exec(f.read())

l = len(R[0])

mapping = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]

RR = []
for row in R:
r = []
for x in row:
r += mapping[x]
RR.append(r)

A = matrix(GF(2), RR)
b = vector(S)
ker = A.right_kernel_matrix()
print(ker[0])
print(ker[1])
print(ker[2])

sol = A.solve_right(b)
inv = {
(0, 1, 0): 0,
(1, 0, 0): 1,
(0, 0, 1): 2,
}

digits = []
for i in range(l):
thing = tuple(sol[i * 3 : (i + 1) * 3])
if thing in inv:
digits.append(inv[thing])
else:
thing2 = tuple(1 - x for x in thing)
digits.append(inv[thing2])

print(long_to_bytes(int("".join(str(s) for s in digits), 3)))
# CCTF{4n0Th3R_47tACkER_!n_Vi5A!}

解完這之後我又在想: 如果是先 也能解嗎? 如果是這樣的話 encoding () 要怎麼找?

測試了一下也真的可以,一個方法是先隨便選個已知的字串且選定好 ,然後用上面的方法建表並回推出 。另一個是利用 的性質,可知 。在一般情況下 用最簡單的 one hot encoding 的話 ,那

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


def base(n, l):
D = []
while n > 0:
n, r = divmod(n, l)
D.append(r)
return "".join(str(d) for d in reversed(D)) or "0"


def asiv_prng(seed, mod):
l = len(seed)
_seed = base(bytes_to_long(seed), mod)
_l = len(_seed)
R = [[getRandomRange(0, mod) for _ in range(_l)] for _ in range(_l**2)]
S = []
for r in R:
s = 0
for _ in range(_l):
b = ((int(r[_]) + int(_seed[_])) % mod) % 2
s = s ^^ b
S.append(s)
return _seed, R, S


# choose parameter
mapping = [
[1, 0, 0],
[0, 1, 0],
[0, 0, 1],
]
mod = 3

# mapping = [
# [1, 0, 0, 0, 0],
# [0, 1, 0, 0, 0],
# [0, 0, 1, 0, 0],
# [0, 0, 0, 1, 0],
# [0, 0, 0, 0, 1],
# ]
# mapping = [
# [1, 0, 0, 0, 0],
# [0, 0, 0, 0, 1],
# [0, 1, 0, 0, 0],
# [0, 0, 0, 1, 0],
# [0, 0, 1, 0, 0],
# ]
# mod = 5

# mapping = matrix.identity(7)
# mod = 7

# choose encodings
mf = matrix(GF(2), mod, mod)
for x in range(mod):
for y in range(mod):
mf[x, y] = ((x + y) % mod) % 2
mg = matrix(GF(2), mapping)
mh = (mg.inverse() * mf).T
assert mg * mh.T == mf
inv_table = {}
for i in range(mod):
t = tuple(mh[i])
inv_table[t] = i
t2 = tuple(1 - x for x in t)
inv_table[t2] = i

sv, R, S = asiv_prng(b"flag{test}", mod)
l = len(R[0])
RR = []
for row in R:
r = []
for x in row:
r += mapping[x]
RR.append(r)

A = matrix(GF(2), RR)
sol = A.solve_right(vector(S))
digits = []
for i in range(l):
thing = tuple(sol[i * mod : (i + 1) * mod])
digits.append(inv_table[thing])
print(long_to_bytes(int("".join(str(s) for s in digits), mod)))