廢文集中區

Crypto CTF 2023 WriteUps

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

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

Easy

Suction

#!/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，但是 n,e,cn,e,c 都少了 lowest 8 bits。這邊我是直接爆搜 nn 的最後 8 bits 去硬分解，然後得到 p,qp,q 之後再去搜 2562256^2 的空間找到真正的 e,ce,c 解出 flag。

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

#!/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 所以應該不大，一個最可能的解是 (e,d)=(3,73)(e,d)=(3,73)。這樣的話會變成要解 x3+y3+z3=dxyzx^3+y^3+z^3=dxyz，明顯是一條橢圓曲線。透過 sage 轉換之後 enumerate 一下找到全部為正整數的 (x,y,z)(x,y,z)，然後反過來得到 (p,q,r)(p,q,r) 之後就可以解出 flag 了。

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

#!/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，曲線是 x3+y3+c=dxyx^3+y^3+c=dxy。

先檢查一下 curve 是什麼 curve:

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 的性質把原本的 (x,y)(x,y) 換回 (x′,y′,z′)(x',y',z')，用 x=x′/z′,y=y′/z′x=x'/z',y=y'/z' 代換可以得到 x3+y3+z3=dxyzx^3+y^3+z^3=dxyz，確實符合。然後再用 sage 內建的那些操作可發現轉換過去的橢圓曲線 order 相當 smooth，所以直接 dlog 搞定。

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

#!/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}')

這題的 p=am+r,q=bm+sp=a^m+r, q=b^m+s，而 e=rse=rs。因為 ee 是 28 bits 所以可以回推 m=4m=4。

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

不過我這邊發現因為 r,sr,s 真的太小了 (compared to a,ba,b)，可得 ⌊n4⌋=ab\lfloor \sqrt[4]{n} \rfloor = ab，所以

n=pq=(a4+r)(b4+s)=a4b4+sa4+rb4+rs≡sa4+rb4+e(moda4b4)\begin{aligned} n&=pq \\ &=(a^4+r)(b^4+s) \\ &=a^4b^4+sa^4+rb^4+rs \\ &\equiv sa^4+rb^4+e \pmod{a^4b^4} \end{aligned}

由於 sa4+rb4sa^4+rb^4 遠比 a4b4a^4b^4 小，n−emod  a4b4=sa4+rb4n-e \mod{a^4b^4}=sa^4+rb^4。同時又有 sa4rb4=e(ab)4sa^4rb^4=e(ab)^4，所以這邊有個相加與相乘的關係，所以 sa4,rb4sa^4,rb^4 是以下多項式的兩根:

f(x)=(x−sa4)(x−rb4)=x2−(sa4+rb4)x+sa4rb4=x2−(n−emod  a4b4)x+e(ab)4\begin{aligned} f(x)&=(x-sa^4)(x-rb^4) \\ &=x^2-(sa^4+rb^4)x+sa^4rb^4 \\ &=x^2-(n-e \mod{a^4b^4})x+e(ab)^4 \end{aligned}

得到 sa4,rb4sa^4,rb^4 之後 gcd 就有 a,b,s,ra,b,s,r 了，然後就可以解出 p,qp,q 了。不過由於 ee 和 (p−1)(q−1)(p-1)(q-1) 不互質所以要直接 enumerate 所有可能的 mm 再 CRT 找 flag。

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

#!/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。

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

#!/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，不過這次 nn 有 2048 bit，但 dd 只有 64 bit 所以大概是可以爆一下 ee 的 8 bits 用 wiener/boneh-durfee attack 之類的攻擊求解。

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

ed=1+kφ(n)=1+k(n′+y−s+1)=1+k(n′−t)\begin{aligned} ed&=1+k\varphi(n) \\ &=1+k(n'+y-s+1) \\ &=1+k(n'-t) \\ \end{aligned}

其中 yy 是 nn 的未知 8 bit 而 s=p+qs=p+q，而 kk 應該和 dd 差不多大，所以 coppersmith 就能求出 k,tk,t。

有 tt 之後就有 φ(n)\varphi(n)，然後爆一下 yy 檢查 xφ(n)≡?1(modn′+y)x^\varphi(n) \stackrel{?}{\equiv} 1 \pmod{n'+y} 就能得到 nn。

最後爆一下 cc 就能解出 flag 了:

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) 應該更適合點，因為 dd 真的很小。原本的 (e+x)d=1+k(n−t)(e+x)d=1+k(n-t) 稍微改寫可得 e/n≈k/de/n \approx k/d，不過實際上要用 210252^{1025} 去近似 tt 才能找到 k,dk,d。剩下就隨便爆一下就有了。

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

#!/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 搞定。

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

#!/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}')

這題在 Z/nZ\mathbb{Z}/n\mathbb{Z} 上使用類似 RSA 的方法加密 flag，而 n=pqn=pq 所以一定得分解 nn 才行。

它 keygen 的方法是先生成 pp，然後 flip 兩個固定的 bit 變成 ss 之後 q=nextPrime⁡(2s+1)q=\operatorname{nextPrime}(2s+1)。

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

p=p′+2as=p′±2bq=2s+1+t=2p′±2b+1+1+t\begin{aligned} p&=p'+2^a \\ s&=p' \pm 2^b \\ q&=2s+1+t \\ &=2p' \pm 2^{b+1} + 1 + t \end{aligned}

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

分解之後就拿 ee 對 #E(Fp)×#E(Fq)\#E(\mathbb{F}_p) \times \#E(\mathbb{F}_q) 求 inverse 當作 dd 解密 flag 即可。

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

#!/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 有 r,s,tr,s,t 符合 tk=hr−sdtk=hr-sd，其中 kk 是 nonce 而 dd 是 private key。不過 kk 根據它生成的方法可知它一定不到 255−24=231255-24=231 bits，所以可以 LLL 解出 kk，進而求出 dd。

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 上去之後會出現這樣的訊息:

> 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:

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

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

#!/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 可以拿來用。只需要搞清楚各個參數的意義就行了。

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

#!/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，很難處理。這邊的關鍵是想辦法令一個函數 f(x,y)f(x,y) 去代表那個運算:

f:F3×F3→F2f(x,y)=(x+ymod  3)mod  2\begin{gathered} f: \mathbb{F}_3 \times \mathbb{F}_3 \rightarrow \mathbb{F}_2 \\ f(x,y)=(x+y \mod{3})\mod{2} \end{gathered}

如果有辦法把這個函數簡單的表達出來，就能在 F2\mathbb{F}_2 上解 linear system 了。

可以先畫出個 f(x,y)f(x,y) 的表格:

012
0010
1100
2001

假設說使用類似 one hot encoding 的方法，把 RR 中的 0,1,20,1,2 如此做編碼 (g(x)g(x)):

  • g(0)=(1,0,0)g(0) = (1,0,0)
  • g(1)=(0,1,0)g(1) = (0,1,0)
  • g(2)=(0,0,1)g(2) = (0,0,1)

然後再對 mm 中的 0,1,20,1,2 用一個不同的編碼 (h(y)h(y)):

  • h(0)=(0,1,0)h(0) = (0,1,0)
  • h(1)=(1,0,0)h(1) = (1,0,0)
  • h(2)=(0,0,1)h(2) = (0,0,1)

那麼可以發現 f′(x,y)=g(x)⋅h(y)f'(x,y)=g(x) \cdot h(y) 的表格和前面 f(x,y)f(x,y) 長的一模一樣:

012
0010
1100
2001

所以可知 f′(x,y)f'(x,y) 和 f(x,y)f(x,y) 是一樣的，那麼原本的 b = ((int(r[_]) + int(_seed[_])) % 3) % 2 操作其實就變成了 b = g(int(r[_])) * h(int(_seed[_]))，這邊的 * 要理解成 F2\mathbb{F}_2 上的內積，由此這樣整個系統就變成線性的了。

所以只要先把原本 R∈F3l2×lR \in \mathbb{F}_3^{l^2 \times l} 的矩陣的每個元素透過 g(x)g(x) 做編碼，讓它變成 R′∈F2l2×3lR' \in \mathbb{F}_2^{l^2 \times 3l}，然後在 F2\mathbb{F}_2 上解 R′m′=SR'm'=S 就會得到一個被編碼過的 m′m'，最後再把 m′m' 透過 h−1(y)h^{-1}(y) 解碼回來就能得到 mm。

不過在解碼的過程中會發現有個問題是解碼時會找不到 h(y)h(y) 的 preimage，例如 (1,1,0)(1,1,0) 因為一些原因會出現在 m′m' 之中。

稍微研究一下會發現這是因為 R′R' 其實不是 full rank 的，儘管 dimension 有 3l3l，但它的 rank 因為一些未知原因而固定是 2l+12l+1，所以有 l−1l-1 維的 kernel。計算一下可以發現它長的意外整齊，大概像下面這樣:

111000000000...
000111000000...
000000111000...
...

這個意思就是說在 h(y)h(y) 這個 encoding 其實不是一對一的，而是一對二，包含它的 bitwise inverse。所以這就代表 22 其實同時有 (0,0,1)(0,0,1) 和 (1,1,0)(1,1,0) 兩個 encoding，那麼在用 h−1(y)h^{-1}(y) 解碼時就多把這個考慮進去就好，最後解出來的 flag 回是正確的。

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!}

解完這之後我又在想: 如果是先  mod 5\bmod{5} 再  mod 2\bmod{2} 也能解嗎? 如果是這樣的話 encoding (g(x),h(x)g(x), h(x)) 要怎麼找?

測試了一下也真的可以，一個方法是先隨便選個已知的字串且選定好 g(x)g(x)，然後用上面的方法建表並回推出 h−1(y)h^{-1}(y)。另一個是利用 f(x,y)=g(x)⋅h(y)f(x,y)=g(x) \cdot h(y) 的性質，可知 Mf=MgMhTM_f=M_g M_h^{T}。在一般情況下 g(x)g(x) 用最簡單的 one hot encoding 的話 Mg=IM_g=I，那 Mh=MfTM_h=M_f^{T}。

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)))