Crypto CTF 2023 WriteUps

發表於 2023-07-09

分類於 CTF

This article is LLM-translated by GPT-4o, so the translation may be inaccurate or complete. If you find any mistake, please let me know.

This year, as usual, I participated in this year’s Crypto CTF with isanapap, and after more than 6 hours, we achieved AK and won first place again.

Problems marked with * are those solved by teammates, which I later upsolved myself.

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

In short, this problem involves a 256-bit RSA, but the lowest 8 bits of $n, e, c$ are missing. Here, I directly brute-forced the last 8 bits of $n$ to factorize it, then after obtaining $p, q$ , I searched the $256^2$ space to find the actual $e, c$ and solved for the 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] are 10543, 4, and since e appears in the exponent, it should not be large. A most likely solution is $(e,d)=(3,73)$ . In this case, it becomes solving $x^3+y^3+z^3=dxyz$ , which is clearly an elliptic curve. By converting it using sage and enumerating, we find all positive integer $(x,y,z)$ , then reverse to get $(p,q,r)$ and solve for the 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}')

This problem requires solving dlog on a group formed by an unknown curve, where the curve is $x^3+y^3+c=dxy$ .

First, check what the curve is:

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

So it’s Genus 1, which means it’s an elliptic curve. Then, by referring to the Explicit-Formulas Database, we can see it should be Hessian curves/Twisted Hessian curves, so theoretically, we can find papers with formulas to convert it back to Weierstrass form.

However, I was too lazy to look up papers and wanted to use sage’s built-in EllipticCurve_from_cubic, but its input needs to be a homogeneous cubic in three variables with rational coefficients.

Using the properties of projective coordinates, we convert the original $(x,y)$ back to $(x',y',z')$ , and substituting $x=x'/z', y=y'/z'$ gives $x^3+y^3+z^3=dxyz$ , which fits. Then using sage’s built-in operations, we find the converted elliptic curve order is quite smooth, so we directly solve 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}')

In this problem, $p=a^m+r, q=b^m+s$ , and $e=rs$ . Since $e$ is 28 bits, we can deduce $m=4$ .

This problem reminded me of a previous one, Power RSA, which mentioned A New Attack on Special-Structured RSA Primes, perfectly fitting this problem’s situation.

However, I found that since $r, s$ are really small (compared to $a, b$ ), we get $\lfloor \sqrt[4]{n} \rfloor = ab$ , so

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

Since $sa^4+rb^4$ is much smaller than $a^4b^4$ , $n-e \mod{a^4b^4}=sa^4+rb^4$ . Also, $sa^4rb^4=e(ab)^4$ , so there is an addition and multiplication relationship, making $sa^4, rb^4$ the roots of the following polynomial:

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

After obtaining $sa^4, rb^4$ , gcd gives $a, b, s, r$ , then we can solve for $p, q$ . However, since $e$ and $(p-1)(q-1)$ are not coprime, we need to enumerate all possible $m$ and use CRT to find the 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')

This problem involves some strange operations to encrypt the message, embed it into an image, and then rotate it for output. Since there are only 4 rotations, we can brute-force to get the final state of _msg after the loop. Then, since the key length is only 3, we can brute-force the six permutations of [0, 1, 2] (_conf) and use z3 to solve, combined with the known flag prefix to get the flag and 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)}')

Similar to the previous suction, but this time $n$ is 2048 bits, and $d$ is only 64 bits, so we can brute-force the 8 bits of $e$ using wiener/boneh-durfee attack or similar methods.

I used the boneh-dufee method, treating $e$ as known, then we can write

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

where $y$ is the unknown 8 bits of $n$ and $s=p+q$ , and $k$ should be about the same size as $d$ , so coppersmith can solve for $k, t$ .

After obtaining $t$ , we get $\varphi(n)$ , then brute-force $y$ to check $x^\varphi(n) \stackrel{?}{\equiv} 1 \pmod{n'+y}$ to get $n$ .

Finally, brute-force $c$ to solve for the 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!}

Later, I thought using wiener (continued fraction) might be more suitable since $d$ is really small. The original $(e+x)d=1+k(n-t)$ can be rewritten as $e/n \approx k/d$ , but actually, we need to approximate $t$ with $2^{1025}$ to find $k, d$ . The rest is just brute-forcing.

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

A very strange RNG, but it can be solved directly by solving a 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}')

This problem encrypts the flag using a method similar to RSA in $\mathbb{Z}/n\mathbb{Z}$ , where $n=pq$ , so we must factorize $n$ .

The keygen method first generates $p$ , then flips two fixed bits to become $s$ , and $q=\operatorname{nextPrime}(2s+1)$ .

Since the two bits are fixed positions, let’s denote them as the $a$ and $b$ bits, and since the $a$ bit is exactly p.bit_length() - 1, flipping it is equivalent to $p-2^a$ , so we can rewrite the generation method as:

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

Here, the $\pm$ sign is unknown, but we can guess, and $t$ is very small, so we brute-force it, turning it into a quadratic polynomial root-finding problem.

After factorizing, we use $e$ to find the inverse of $\#E(\mathbb{F}_p) \times \#E(\mathbb{F}_q)$ as $d$ to decrypt the 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()

This problem involves a signature scheme similar to ECDSA, where each signature has $r, s, t$ satisfying $tk=hr-sd$ , where $k$ is the nonce and $d$ is the private key. However, from the generation method, we know $k$ is less than $255-24=231$ bits, so we can use LLL to solve for $k$ and then find $d$ .

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

A tricky part of this problem is that if you send msg, it will sign msg + b'\n' …

Byeween

This problem has no code; connecting via nc shows the following message:

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

Although it seems there is a typo, it should be finding the half point of $Q$ , which can be easily solved using 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()}')

This is clearly the previously broken SIDH (An efficient key recovery attack on SIDH), and there is already an existing implementation available. We just need to understand the meaning of each parameter.

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

Similar to ASIv1, but it first mods 3 then mods 2, making it difficult to handle. The key here is to find a function $f(x,y)$ to represent the operation:

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

If we can express this function simply, we can solve the linear system in $\mathbb{F}_2$ .

We can first draw a table for $f(x,y)$ :

	0	1	2
0	0	1	0
1	1	0	0
2	0	0	1

Assuming we use a one-hot encoding method, encoding $0, 1, 2$ in $R$ as follows ( $g(x)$ ):

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

Then encoding $0, 1, 2$ in $m$ differently ( $h(y)$ ):

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

We find that $f'(x,y)=g(x) \cdot h(y)$ has the same table as $f(x,y)$ :

	0	1	2
0	0	1	0
1	1	0	0
2	0	0	1

So $f'(x,y)$ and $f(x,y)$ are the same, meaning the original b = ((int(r[_]) + int(_seed[_])) % 3) % 2 operation becomes b = g(int(r[_])) * h(int(_seed[_])), where * is understood as the dot product in $\mathbb{F}_2$ . This makes the entire system linear.

We just need to encode each element of the original $R \in \mathbb{F}_3^{l^2 \times l}$ matrix using $g(x)$ , turning it into $R' \in \mathbb{F}_2^{l^2 \times 3l}$ , then solve $R'm'=S$ in $\mathbb{F}_2$ to get an encoded $m'$ , and finally decode $m'$ using $h^{-1}(y)$ to get $m$ .

However, during decoding, we find that some $h(y)$ preimages are missing, such as $(1,1,0)$ appearing in $m'$ .

Further research shows this is because $R'$ is not full rank; despite having a dimension of $3l$ , its rank is fixed at $2l+1$ for unknown reasons, leaving a kernel of $l-1$ dimensions. Calculations show it looks surprisingly neat, like this:

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

This means the $h(y)$ encoding is not one-to-one but one-to-two, including its bitwise inverse. So $2$ has both $(0,0,1)$ and $(1,1,0)$ encodings, and we need to consider this during $h^{-1}(y)$ decoding to get the correct 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!}

After solving this, I wondered: if it first mods 5 then mods 2, can it still be solved? If so, how to find the encoding ( $g(x), h(x)$ )?

Testing shows it can be done. One method is to choose a known string and $g(x)$ , then build the table and deduce $h^{-1}(y)$ . Another method uses the property $f(x,y)=g(x) \cdot h(y)$ , knowing $M_f=M_g M_h^{T}$ . In general, with $g(x)$ as the simplest one-hot encoding, $M_g=I$ , so $M_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)))

Easy#

Suction#

Medium#

*Derik#

Barak#

Risk#

Bertrand#

Resuction#

ASIv1#

Keymoted#

Hard#

Marjan#

Byeween#

Shevid#

Tough#

*ASIv2#