During the ongoing AIS3, I participated in Crypto CTF 2021 and ranked 19th. The competition lasted only 24 hours, so I only solved the easier and medium-difficulty problems. Even with more time, I might have only solved 1-2 more problems.

Problems marked with * were solved after the competition.

easy#

Farm#

The key is the product of any 14 elements in $\mathbb F_{64}$, and the encryption part is to first base64 encode the flag, then convert it to elements of $\mathbb F_{64}$, multiply each element by the key, and convert it back to base64 characters to form the ciphertext.

The solution is to brute force 64 keys and see which key can convert back to normal base64.

import string, base64

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

enc = "805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj"

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

As the flag suggests, this is just a substitution cipher, but in a finite field version.

KeyBase#

This problem is an AES-CBC challenge. First, you are given a flag encrypted with a fixed key and IV, and an oracle that allows you to provide any 32 bytes of plaintext to be encrypted with the same key and IV. After encryption, the oracle gives you the first 14 bytes of the key and the second block (last 16 bytes) of the ciphertext.

Since the first 14 bytes of the key are known, you can brute force 65536 combinations to find the key, treating the key as known. However, the challenge lies in not knowing the IV. To obtain the IV, encrypt known plaintext using the oracle, brute force the key to decrypt the second block of the ciphertext, and XOR it with the second block of the plaintext to get the first block of the ciphertext. With the first block of plaintext and ciphertext, brute force the key to deduce the IV, and then decrypt the flag with the IV and key.

from Crypto.Cipher import AES
import string

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


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


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


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


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


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

Symbols#

This problem gives you an image with many mathematical symbols, resembling a substitution cipher.

$\Cap\Cap\Theta\Finv\{\Pi\ltimes\aleph y\_\wp\infty\therefore\heartsuit\_\Lsh\aleph\Theta\eth\Xi\}$

My solution was to use Detexify to look up the LaTeX commands for the symbols. Noticing that the first character of each command corresponds to the flag character, I found CCTF{Play_with_LaTeX}.

medium-easy#

Rima#

This problem converts the flag into a 0-1 array and encodes it using some shifting additions. The code is hard to read, so I used z3 to solve it directly.

from Crypto.Util.number import *
from sage.all import Integer, next_prime
from z3 import *

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

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

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

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

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

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

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

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

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


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

Hyper Normal#

This problem encodes the flag into a matrix $V$ over $\mathbb F_{8443}$ and shuffles it. Assuming the flag characters are $a_0 \sim a_{l-1}$, the matrix $V$ becomes:

Then the rows are randomly shuffled.

Next, it loops $i=0 \sim l-1$, generates a vector $R=(r_0,\cdots,r_{l-1})$, and calculates:

where $V_i$ and $W_i$ are the $i$-th row vectors of matrices $V$ and $W$. After generating $W$, it shuffles the rows of $W^\intercal$ and outputs it as the encrypted flag.

My solution uses the property $0 \leq r_i \leq 126$ to brute force the possible values of $(i+1)a_{i}$, intersecting multiple rows to deduce $(i+1)a_{i}$, and then solving for the flag.

However, my solution had some issues, and I had to adjust which sets to union to get the correct flag.

# fmt: off
W = [] # fill this
# fmt: on

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

p = 8443


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


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


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


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


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

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

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

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

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

# CCTF{H0w_f1Nd_th3_4lL_3I9EnV4Lu35_iN_FiN173_Fi3lD5!???}

The expected solution seems related to eigenvalues, but it's unclear how to proceed...

Hamul#

This problem is an RSA challenge. The prime generation steps are as follows:

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    P = int(str(p) + str(q))
    Q = int(str(q) + str(p))
    PP = int(str(P) + str(Q))
    QQ = int(str(Q) + str(P))
    if isPrime(PP) and isPrime(QQ):
        break

Then n = PP * QQ is used as the RSA modulus to encrypt the flag.

First, the lengths of str(p) and str(q) are either 19 or 20, so $P=p10^a+q$ and $Q=q10^b+p$. Using similar equations, it becomes a polynomial root-finding problem $f(p,q)$, which I solved using Coppersmith's method.

from Crypto.Util.number import *

n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043
c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399

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


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

medium#

Tuti#

This problem splits the flag into two halves $x$ and $y$, satisfying the following equation, where $k$ is a constant:

Rewriting it as a polynomial root problem, it can be factored as:

where $a$ and $b$ are constants satisfying $a+2=b$. Since $x$ and $y$ are positive, the condition $f(x,y)=0$ can only be $xy-x+y-b=0$.

Rewriting this equation, it becomes $(x+1)(y-1)=b-1$. By factoring $b-1$, all solutions for $x$ and $y$ can be found.

from Crypto.Util.number import *

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

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

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

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


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


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

Salt and Pepper#

This problem involves two unknowns, salt and pepper, both of length 19. You are given md5(salt) and sha(pepper). The goal is to find an input containing the specified username and password and determine sha1(pepper + input_password + md5(salt + input_username)).

The solution uses a Length Extension Attack with HashPump. However, HashPump requires data. I commented out this check and recompiled it to get the desired result.

from pwn import *
from hashpumpy import hashpump

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


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

Triplet#

This problem requires finding 3 sets of RSA $(p,q)$ (at least 160 bits) and providing $(e,d)$ such that $ed \equiv 1 \pmod{\varphi(n_i)}$ and $1<e,d<\min(\varphi(n_1),\varphi(n_2),\varphi(n_3))$.

First, deduce $ed \equiv 1 \pmod{l}$, where $l=\operatorname{lcm}(\varphi(n_1),\varphi(n_2),\varphi(n_3))$. This implies $ed-1=kl$, and for $k=1$, $ed \approx l$, so $l$ needs to be minimized.

A simple method is to choose three primes $p$, $q$, and $r$, and set $n_1=pq$, $n_2=qr$, $n_3=rp$, making $l=lcm(p-1,q-1,r-1)$ smaller. Then factor $l+1$ to find $(e,d)$.

from Crypto.Util.number import *


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


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


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

print(l + 1)

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

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

# CCTF{7HrE3_b4Bie5_c4rRi3d_dUr1nG_0Ne_pr39naNcY_Ar3_triplets}

Onlude#

This problem encodes the flag into an $11 \times 11$ matrix $A$ over $\mathbb F_{71}$. There are two matrices $R$ and $S$, with $S$ decomposed into $S=LU$.

Encryption is done using $E=L^{-1}S(A+R)=U(A+R)$. Additionally, three matrices $LUL$, $L^{-1}S^2L$, and $R^{-1}S^8$ are provided.

First, calculate $U$ from $L^{-1}S^2L=ULUL$ and $LUL$. Then deduce $S^2=LULU$ and $R$. With $U$ and $R$, decryption is straightforward.

p = 71

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

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

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


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

Improved#

This problem involves a strange hash function, and the goal is to find a collision. Parameter generation produces two primes $p$ and $q$, then calculates $n=pq$, $f=\operatorname{lcm}(p-1,q-1)$, and $g=p+q$. Next, compute $e \equiv g^f \pmod{n^2}$, $u=\lfloor \frac{e-1}{n} \rfloor$, and $v \equiv u^{-1} \pmod{n}$. The final parameters are $n, f, v$.

The hash function uses $e \equiv m^f \pmod{n^2}$, $u=\lfloor \frac{e-1}{n} \rfloor$, and $L=\lfloor \frac{uv}{n} \rfloor$. The final hash result is $\operatorname{sha1}(L)$.

PS: $m$ is restricted to $1 \lt m \lt n^2-1$

Although the problem seems complex, it is easily solved. Any element in $Z_{n^2}$ has an order of $fn$, so calculating $x \equiv k^{fn/2} \pmod{n^2}$ yields $x^2 \equiv 1 \pmod{n^2}$, and another root $y=n^2-x$. Since $f$ is even, $x^2 \equiv y^2 \equiv 1 \pmod{n^2}$, resulting in a collision.

from pwn import remote
import ast

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

Maid#

This problem generates two primes $p$ and $q$ such that $p \equiv q \equiv 3 \pmod{4}$, then calculates $n=p^2q$ and the private key $p$.

The flag is encrypted using traditional RSA $c \equiv m^e \pmod{pq}$, but the encryption and decryption oracles use the Rabin cryptosystem. The encryption function is simply $c \equiv m^2 \pmod{n}$, but the decryption function is hidden, likely similar to $m \equiv c^\frac{p+1}{4} \pmod{p}$.

The goal is to factor $p$ and $q$. First, use the encryption oracle to calculate gcd and obtain $n$. The key to obtaining $p$ lies in the decryption oracle.

Initially, I tried decrypting -1, assuming $\frac{p+1}{4}$ is odd, yielding $p-1 \equiv (-1)^\frac{p+1}{4} \pmod {p}$. Adding 1 gives $p$, which worked locally but failed remotely due to the hidden decryption function.

Later, I used $\gcd(\operatorname{decrypt}(m)^2 - m)$ to find a value, initially thought to be $p$, but it was $p^2$. This allowed me to obtain $p$ and $q$ and retrieve the flag.

from pwn import *
from Crypto.Util.number import *
from gmpy2 import isqrt
from functools import reduce

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


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


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


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

Here is the decryption function posted by the problem creator on Discord:

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

Ferman#

This problem has no source code. It provides an equation $(p-a)^2+(q-b)^2=r$ and uses $(n,e)=(pq,65537)$ to encrypt the flag. The goal is to solve the equation.

Initially, I had no idea, but factoring $r$ revealed $r=k^7$. Repeatedly testing multiple parameters yielded the same result. Although Sage's solver couldn't solve $x^2+y^2=k^7$, it solved $x^2+y^2=k$.

Given solutions for $x^2+y^2=k$, use the Brahmagupta–Fibonacci identity to extend solutions to $k^2$, then repeatedly extend to $k^7$.

from Crypto.Util.number import *

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


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


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


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

I later realized this implementation worked by luck, as directly raising a solution to the 7th power doesn't guarantee all solutions for $k^7$. The correct approach should multiply all solutions for $k$ to obtain solutions for $k^2$, then multiply solutions for $k^2$ to get $k^3$, and so on...

Tiny ECC#

This problem requires providing two primes $p$ and $q=2p+1$ (at least 128 bits), and two numbers $a$ and $b$. It then selects two random points on two elliptic curves $y^2=x^3+ax+b$ over $F_p$ or $F_q$ and gives you two ECDLPs to solve, yielding the flag.

My method was simple and brute-force: find $(p,q)$ such that both curves' orders are 2^40-smooth. This took a few minutes.

from Crypto.Util.number import *


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


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

The remaining part is solved using Sage's built-in Pohlig-Hellman:

from pwn import remote
import ast

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


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

Additionally, an interesting alternative solution sets $(a,b) = (pq,pq)$, making the ECDLP on the singular curve $y^2=x^3$. Since $y^2=x^3$ can be mapped to the additive group of $\mathbb F_p$ or $\mathbb F_q$ via $(x,y)\mapsto\frac{x}{y}$, the DLP becomes simple division.

from pwn import remote
import ast

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


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


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


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

*Elegant Curve#

This problem is similar to the previous one but requires selecting two primes $p$ and $q$ such that $0 \lt q-p \leq 2022$, and the curves' $a,b$ can differ. The previous brute-force method works but is inefficient.

This time, I generated an anomalous curve $\#E(\mathbb F_p)=p$, then used next prime to find $q$. Then, I brute-forced $a,b$ to find smooth curves.

The generation script is as follows:

from Crypto.Util.number import *
from subprocess import check_output
import json


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


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


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


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

With the required parameters, solving the problem is straightforward:

from pwn import remote, process
import ast

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

assert Ep.order() == p


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

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

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

    p_times_P = p * P_Qp
    p_times_Q = p * Q_Qp

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

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


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


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

medium-hard#

Wolf#

This problem uses AES-GCM to encrypt the flag and provides an oracle to encrypt arbitrary information. The key is that the IV is fixed, so it has the same issue as CTR mode reuse nonce. XORing two ciphertexts and then XORing the known plaintext reveals the flag.

from pwn import remote


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


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

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

Frozen#

This problem has two parameters $(p,r)$ ($p$ is 128 bits). During key generation, it calculates 5 numbers $u_i \equiv r^{i+1}s \pmod{p}$, with public key $p_i$ being the high 96 bits of $u_i$ and private key $x_i$ being the low 32 bits. $s$ is an unknown random number.

The sign function groups the msg into four-byte numbers $M_i$, then calculates q = next_prime(max(M)). The signature is $M_ix_i \mod{q}$. The goal is to sign a given random string correctly to get the flag.

First, $r^{i+1}s \equiv p_i+x_i \pmod{p}$, so:

Eliminating $s$ from two equations yields a polynomial in $x_0$ and $x_1$. Solving it with Coppersmith's method reveals $s$, allowing the complete private key to be calculated and the msg to be signed, revealing the flag.

from Crypto.Util.number import *
from pwn import remote
from sage.matrix.matrix2 import Matrix
import ast


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


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

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


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


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

The flag mentions Lattice, but according to others, it's unnecessary. The problem includes an unused oracle providing a fixed msg and signature. Since the msg is known, $q$ can be deduced, and the private key can be inferred.

LINDA#

This problem is rather dull. It has four parameters $(p,u,v,w)$, with $u$ being random, $w \equiv u^x \pmod{p}$, and $v \equiv u^r \pmod{p}$.

Encryption involves $c_a \equiv u^r \pmod{p}$, $c_b \equiv v^s \pmod{p}$, and $c_c \equiv mw^{r+s} \pmod{p}$, where $r,s$ are random and unrelated to the previous ones.

This problem resembles an ElGamal-like encryption system, but the key is that $p-1$ is 2^40-smooth. Directly solving DLP for $r,s$ allows decryption.

from Crypto.Util.number import *

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

Z = Zmod(p)

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

*RSAphantine#

This problem involves solving a system of Diophantine equations to find two primes $p, q$ and decrypt the flag.

Initially, I tried using Sage's Groebner basis, but it ran indefinitely, so I didn't solve it.

After the competition, I learned that $k_3-k_1=y^6+x^3=(y^4-xy^2+x^2)(y^2+x)$. Factoring $k_3-k_1$ reveals $x, y$, and the second equation yields $z$.

from Crypto.Util.number import *


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


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


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

s1 = 3133713317731333
s2 = 28413320364759425177418147555143516002041291710972733253944530195017276664069717887927099709630886727522090965378073004342203980057853092114878433424202989

assert s1 * s2 == k3 - k1


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


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


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

Post-competition, I found that Mathematica can solve this in minutes.

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

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

>     y -> 311960913464334198969500852124413736815,

>     z -> 29896806674955692028025365368202021035722548934827533460297089}}

You can run it for free on your computer using Docker's wolframresearch/wolframengine, as tio.run only allows 60 seconds.

*Double Miff#

This problem involves a strange curve $ax(y^2-1)-by(x^2-1) \equiv 0 \pmod{p}$ with unknown parameters. It defines a strange addition and provides three points $P+P, P+Q, Q+Q$, with the flag being the x-coordinates of $P$ and $Q$.

First, find $p$ by substituting points into the polynomial, eliminating variables, and using gcd to find a multiple of $p$. Then use factordb to find $p$.

from sage.matrix.matrix2 import Matrix


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


P.<a, b> = ZZ[]


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


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

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

Solving for $a, b$ is impossible as they don't matter. The polynomial gcd reveals they are linearly related.

The goal is to reverse the addition formula to halve the points. This involves listing two polynomials, eliminating variables, and solving for the roots.

from Crypto.Util.number import *
from sage.matrix.matrix2 import Matrix


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


p = 1141623079614587900848768080393294899678477852887
F = GF(p)

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


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


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


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

*ecchimera#

This problem involves an elliptic curve over $\mathbb Z_n$, with the flag being the discrete log results of two points. First, factor $n$ into