Crypto CTF 2022 WriteUps

發表於 2022-07-18

分類於 CTF

This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .

This time I joined isanapap and several other Taiwanese CTF crypto players to participate in this year's Crypto CTF, and we were lucky enough to win first place. Here, I will only write about the problems that I think are worth writing about, and the problems I write about are not necessarily the ones I solved during the competition.

medium-easy

SOTS

This problem has no source. When you connect using nc, you will see

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|  Hey math experts, in this challenge we will deal with the numbers   |
|  those are the sum of two perfect square, now try hard to find them! |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Generating the `n', please wait...
| Options:
|       [G]et the n
|       [S]olve the challenge!
|       [Q]uit
G
| n = 4681699452900793124255588703544500598149979834311033888906299527764579361
| Options:
|       [G]et the n
|       [S]olve the challenge!
|       [Q]uit
S
| Send your pair x, y here:

In short, there is an $n$ , and you need to find two positive integers $x,y$ that satisfy $x^2+y^2=n$ . The simplest solution is to search on Google and find that sage has a built-in function two_squares that solves this problem. So, you can solve it directly by inputting it.

Of course, if you want to explore it mathematically, you can know:

x^2+y^2=(x+iy)(x-iy)

So, after decomposing $n$ in the Gaussian integer $\mathbb{Z}[i]$ , it is easy to find the solution. Since $n$ itself can be tested with ecm.factor(n) to know that it is fixed in the format $n=pqr$ , and the numbers are not large, decomposition is not difficult.

There are also some solutions using basic number theory, which can be referred to in this writeup.

polyRSA

The primes in this problem follow a fixed form $p=f(k), q=g(k)$ , and $\deg{f(x)}=6, \deg{g(x)}=5$ , so directly finding the roots of the 11th-degree polynomial $f(x)g(x)-n$ in $\mathbb{Z}$ can yield $k$ , and thus decompose $n$ .

from Crypto.Util.number import *

n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532

P.<k> = ZZ[]
p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
f = p * q - n
k = f.roots()[0][0]
p = ZZ(p(k))
q = ZZ(q(k))
d = inverse_mod(31337, (p-1)*(q-1))
m = power_mod(enc, d, n)
print(long_to_bytes(m))

medium

Cantilever

There is $n=pq$ , and the flag is split into two halves $m_1, m_2$ , encrypted as $c_1 \equiv m_1^e \pmod{n}$ and $c_2 \equiv e^{m_2} \pmod{n}$ .

Reading the source code, you can know that the factors of $p-1$ and $q-1$ are all less than $2^{19}$ , so you can directly use Pollard's p-1 to decompose $n$ , and then use RSA to solve $m_1$ .

The part of $m_2$ is a discrete log problem. You can solve it separately in $\mathbb{F}_p$ and $\mathbb{F}_q$ and then use CRT to restore it. Since $p-1,q-1$ are very smooth, you can directly use Pohlig-Hellman to solve it.

from Crypto.Util.number import *

n = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212
e = 0x10001

a = 2
for p in primes(2 ^ 19):
    a = power_mod(a, p, n)
    p = gcd(a - 1, n)
    if 1 < p < n:
        print(p)
        break
q = n // p
m_1 = power_mod(c_1, inverse_mod(e, (p - 1) * (q - 1)), n)
m_2p = GF(p)(c_2).log(e)
m_2q = GF(p)(c_2).log(e)
m_2 = crt([ZZ(m_2p), ZZ(m_2q)], [p, q])
print(long_to_bytes(m_1) + long_to_bytes(m_2))

Diploma

This problem also has no source. When you connect using nc, you will see

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|  Hi all, cryptographers know that the calculation of the order of a  |
|  given element in a group is not easy at all. We are working in the  |
|  group GL(d, p), the group of invertible matrices of order `d' on a  |
|  finite field of order `p'. In each stage send the order matrix M.   |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Generating the parameters for p = 127, please wait...
| M =
[ 44 119   6]
[123  30  99]
[ 57  23  50]
| Send the order of matrix M:

You need to calculate the order of a matrix in $GL(\mathbb{F}_p)$ , and sage has a built-in function for this, so you can write a script to solve it.

from pwn import remote, context
import re

context.log_level = 'debug'

def s2row(s):
    return list(map(int, re.split(r'\s+', s[1:-1].strip())))

io = remote("08.cr.yp.toc.tf", 37313)
for _ in range(20):
    io.recvuntil(b'p = ')
    p = int(io.recvuntil(b',')[:-1])
    print(f'{p = }')
    io.recvuntil(b'M = \n')
    s = io.recvlineS().strip()
    row = s2row(s)
    mat = [row]
    for _ in range(len(row) - 1):
        s = io.recvlineS().strip()
        print(s)
        row = s2row(s)
        mat.append(row)
        print(row)
    M = matrix(GF(p), mat)
    print(M)
    od = M.multiplicative_order()
    print(od)
    io.sendline(str(od).encode())
io.interactive()
# CCTF{ma7RicES_4R3_u5EfuL_1n_PUbl!c-k3y_CrYpt0gr4Phy!}

Faonsa

This problem has a signature similar to DSA, and you need to obtain a signature for a specified message. One oracle is a signing oracle, and another oracle allows you to flip any 30 bits of $p$ . The normal solution is to try to flip $p-1$ to be smooth enough, then solve the DLP of the signature to restore the private key.

However, the key code looks like this:

def main():
    border = "|"
    pr(border*72)
    pr(border, "Hello guys! This is a another challenge on fault attack too, again  ", border)
    pr(border, "our storage could apply at most `l' bit fault on ElGamal modulus, p,", border)
    pr(border, "try to sign the given message and get the flag! Have fun and enjoy!!", border)
    pr(border*72)
    pr(border, "Generating the parameters, it's time consuming ...")
    nbit = 256
    while True:
        _p = getPrime(255)
        p = 2 * _p + 1
        if isPrime(p):
            g = 2
            if pow(g, _p, p) != 1: break
            else: g += 1
    x = getRandomRange(2, p // 2)
    y = pow(g, x, p)

    B, l = [int(b) for b in bin(p)[2:]], 30
    
    MSG = "4lL crypt0sy5t3ms suck5 fr0m faul7 atTaCk5 :P"
    m = bytes_to_long(MSG.encode('utf-8'))

    while True:
        pr("| Options: \n|\t[A]pply fault \n|\t[G]et the parameters \n|\t[S]ign the message \n|\t[V]erify the signature \n|\t[Q]uit")
        ans = sc().lower()
        if ans == 'a':
            _B = B
            pr(border, f"please send at most {l}-tuple array from indices of bits of ElGamal modulus, like: 5, 12, ...")
            ar = sc()
            try:
                ar = [int(_) for _ in ar.split(',')]
                if len(ar) <= l:
                    for i in range(len(ar)): _B[ar[i]] = (_B[ar[i]] + 1) % 2
                    P = int(''.join([str(b) for b in _B]), 2)
                    Y = pow(g, x, P)
                else: raise Exception('Invalid length!')
            except: pr(border, "Something went wrong!!")
		# omitted...

The main point is that _B = B does a shallow copy, so when it modifies _B below, it also modifies B. Therefore, by using Apply fault multiple times, you can flip any number of bits. According to its signature verification, the simplest way is to directly set $p=1$ to pass the verification.

from pwn import *

# io = process(["python", "faonsa.py"])
io = remote("06.cr.yp.toc.tf", 31117)
io.sendline(b"g")
io.recvuntil(b"p = ")
p = int(io.recvline())
io.recvuntil(b"g = ")
g = int(io.recvline())
io.recvuntil(b"y = ")
y = int(io.recvline())
print(f"{p = }")
print(f"{g = }")
print(f"{y = }")

bits = [int(x) for x in bin(p)[2:]]
print(bits)
idxs = [i for i, b in enumerate(bits) if b]
print(idxs)

chk = 30
for grp in [idxs[i : i + chk] for i in range(0, len(idxs), chk)]:
    print(grp)
    io.sendline(b"a")
    io.sendline(",".join(map(str, grp)).encode())
io.sendline(b"a")
io.sendline(str(len(bits) - 1).encode())
io.sendline(b"v")
io.sendline(b"1,1")
io.interactive()
# CCTF{n3W_4t7aCk_8y_fAuL7_!nJ3cT10N_oN_p!!!}

Additionally, there is a second unintended solution, mainly in this part:

        elif ans == 's':
            pr(border, "Please send your message to sign: ")
            msg = sc().encode('utf-8')
            if msg != MSG.encode('utf-8'):
                _m = bytes_to_long(msg)
                try:
                    sgn = sign_esa((g, P, Y), x, _m)
                    pr(border, f'sign = {sgn}')
                except:
                    import traceback
                    traceback.print_exc()
                    pr(border, "Something went wrong!!")
            else:
                pr(border, "Kidding me!? Really?")

The signing oracle checks msg != MSG.encode('utf-8'), but later uses bytes_to_long(msg), so using msg = b'\x00' + MSG.encode() can bypass the check and get the target signature.

from pwn import *
import ast

# io = process(["python", "faonsa.py"])
io = remote("06.cr.yp.toc.tf", 31117)
io.sendline(b"g")
io.recvuntil(b"p = ")
p = int(io.recvline())
io.recvuntil(b"g = ")
g = int(io.recvline())
io.recvuntil(b"y = ")
y = int(io.recvline())
print(f"{p = }")
print(f"{g = }")
print(f"{y = }")

io.sendline(b"a")
io.sendline(b"0,0")
io.sendline(b"s")
io.sendline(b"\x004lL crypt0sy5t3ms suck5 fr0m faul7 atTaCk5 :P")
io.recvuntil(b"sign = ")
sig = ast.literal_eval(io.recvlineS())
io.sendline(b"v")
io.sendline(",".join(map(str, sig)).encode())
io.interactive()
# CCTF{n3W_4t7aCk_8y_fAuL7_!nJ3cT10N_oN_p!!!}

Fiercest

This problem is similar to Faonsa, but it uses RSA signature, and there is no signing oracle available, and the number of bits to flip is only 2.

However, the shallow copy bug mentioned in the previous problem still exists, so you can flip $N$ into a prime $p$ to pass this problem.

from pwn import *
from Crypto.Util.number import *

# context.log_level = 'debug'

# io = process(["python", "firecest.py"])
io = remote("04.cr.yp.toc.tf", 37713)
io.sendline(b"g")
io.recvuntil(b"e = ")
e = int(io.recvline())
io.recvuntil(b"n = ")
n = int(io.recvline())
print(f"{e = }")
print(f"{n = }")

bits = [int(x) for x in bin(n)[2:]]
print(bits)
idxs = [i for i, b in enumerate(bits) if b]
print(idxs)
chk = 2
for grp in [idxs[i : i + chk] for i in range(0, len(idxs), chk)]:
    print(grp)
    io.sendline(b"a")
    io.sendline(",".join(map(str, grp)).encode())

p = getPrime(n.bit_length())
bits = [int(x) for x in bin(p)[2:]]
print(bits)
idxs = [i for i, b in enumerate(bits) if b]
print(idxs)
chk = 2
for grp in [idxs[i : i + chk] for i in range(0, len(idxs), chk)]:
    print(grp)
    io.sendline(b"a")
    io.sendline(",".join(map(str, grp)).encode())
m = bytes_to_long(b"4lL crypt0sy5t3ms suck5 fr0m faul7 atTaCk5 :P")
e = 65537
d = pow(e,-1,p-1)
io.sendline(b"v")
io.sendline(str(pow(m,d,p)).encode())

io.interactive()
# CCTF{R3aLlY_tH1S_1z_Seiferts_R54_AT7aCk!!?}

Starter ECC

#!/usr/bin/env sage

from Crypto.Util.number import *
from secret import n, a, b, x, flag

y = bytes_to_long(flag.encode('utf-8'))

assert y < n
E = EllipticCurve(Zmod(n), [a, b])

try:
	G = E(x, y)
	print(f'x = {x}')
	print(f'a = {a}')
	print(f'b = {b}')
	print(f'n = {n}')
	print('Find the flag :P')
except:
	print('Ooops, ERROR :-(')

The problem provides an $n$ , an elliptic curve $E$ , and the x-coordinate of a point, with the y-coordinate of that point being the flag.

First, using ecc.factor(n), you can find that $n=p^{63} q^6 r^5$ , where $p=2$ , and directly using lift_x takes a long time at $p^{63}$ for some reason.

After checking, it is known that sage has a built-in square_root_mod_prime_power, but it still takes a long time for $p=2$ , so it is faster to use Hensel lifting to solve it yourself.

The reason it is slow is that sage's implementation method is very poor $\mathcal{O}(2^k)$ , but this method has been fixed in this commit, so it will be directly usable in sage 9.7 in the future.

from Crypto.Util.number import *
from collections.abc import Iterable

x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936

# ecm.factor(n)
p = 2
q = 690712633549859897233
r = 651132262883189171676209466993073
assert n == p ^ 63 * q ^ 6 * r ^ 5


def single_lift(f, df, p, k, rs):
    # f(r) = 0 (mod p^k)
    # df(r) != 0 (mod p^k)
    # returns s such that f(s) = 0 (mod p^(k+1))
    pk = p**k
    pk1 = pk * p
    for r in rs:
        assert f(r) % pk == 0, (r, k)
        # assert df(r) % (p ** k) != 0, (r,k)
        if df(r) % p != 0:
            a = inverse_mod(df(r), p)
            s = r - f(r) * a
            assert f(s) % pk1 == 0
            yield s
        else:
            for t in range(0, p):
                s = r + t * pk
                if f(s) % pk1 == 0:
                    yield s


def hensel_lift(f, df, p, k, m, rs):
    # f(r) = 0 (mod p^k)
    # df(r) != 0 (mod p^k)
    # returns s such that f(s) = 0 (mod p^m)
    if not isinstance(rs, Iterable):
        rs = [rs]
    assert m >= k
    if m == k:
        return rs
    return hensel_lift(f, df, p, k + 1, m, single_lift(f, df, p, k, rs))


y2 = (x ^ 3 + a * x + b) % n
f = lambda x: x ^ 2 - y2
df = lambda x: 2 * x
for yp in hensel_lift(f, df, p, 1, 63, [ZZ(GF(p)(y2).sqrt())]):
    for yq in hensel_lift(f, df, q, 1, 6, [ZZ(GF(q)(y2).sqrt())]):
        for yr in hensel_lift(f, df, r, 1, 5, [ZZ(GF(r)(y2).sqrt())]):
            y = crt([ZZ(yp), ZZ(yq), ZZ(yr)], [p ^ 63, q ^ 6, r ^ 5])
            EllipticCurve(Zmod(n), [a, b])(x, y)
            print(long_to_bytes(y))
# CCTF{8E4uTy_0f_L1f7iN9_cOm3_Up!!}

The Hensel lifting inside is a version I wrote myself before: https://gist.github.com/maple3142/acf736f336cb303cdf47a3ef18f543dc

Additionally, after the competition, I learned on Discord that this kind of square root modulo prime power can be directly solved using p-adic, roughly like this:

yp = ZZ(Qp(p, prec=63)(y2).sqrt()) % (p ^ 63)
assert power_mod(yp, 2, p ^ 63) == y2 % (p ^ 63)

medium-hard

313 Loyal

In this problem, you first need to choose a set of Paillier public keys for the server, and then decide on a polynomial $f(x)$ . The server will have some flag points. For each point $x$ in the flag points, it will use Paillier's homomorphic property to calculate $k f(x)+x$ for you, where $k$ is a random number that changes each time.

Since the public key is self-chosen, all ciphertexts can be easily decrypted. The method to obtain those points is to use $f(x)=n$ to eliminate $k$ .

from Crypto.Util.number import *
from pwn import *
import numpy as np


def keygen(nbit):
    p, q = [getPrime(nbit) for _ in "__"]
    n, phi = p * q, (p - 1) * (q - 1) // 2
    while True:
        g = getRandomRange(2, n**2)
        if GCD(g, n) == 1:
            w = (pow(g, phi, n**2) - 1) // n
            if GCD(w, n) == 1:
                u = inverse(w, n)
                break
    pkey, skey = (n, g), (phi, u)
    return pkey, skey


def add(pkey, a, b):
    n, g = pkey
    return pow(a * b, 1, n**2)


def multiply(pkey, a, k):
    n, g = pkey
    return pow(a, k, n**2)


def encrypt(pkey, m):
    n, g = pkey
    while True:
        r = getRandomRange(2, n)
        if GCD(r, n) == 1:
            break
    return (pow(g, m, n**2) * pow(r, n, n**2)) % (n**2)


def decrypt(pkey, skey, c):
    n, g = pkey
    phi, u = skey
    t = (pow(c, phi, n**2) - 1) // n
    return (t * u) % n


def evaluate_poly(pkey, poly, point):
    n, g = pkey
    _point = point
    result = poly[0]
    for term in poly[1:]:
        result = add((n, g), result, multiply((n, g), term, _point))
        _point = (_point * point) % n
    return result


pkey, skey = keygen(256)
print(pkey)

# io = process(['python', '313loyal.py'])
io = remote("07.cr.yp.toc.tf", 31377)
lenflag = 43


def sendparam(io, n, g, poly):
    io.sendline(b"S")
    io.sendline(f'{n},{g},{" ".join(map(str, poly))}'.encode())
    res = []
    for _ in range(lenflag):
        io.recvuntil(b"=")
        res.append(int(io.recvline()))
    return [decrypt(pkey, skey, x) for x in res]


def encrypt_poly(poly):
    return [encrypt(pkey, x) for x in poly]


n, g = pkey
res = sendparam(io, *pkey, encrypt_poly([n]))
s = np.array(res).argsort()
f = np.array([x % (2**10) for x in res])[s]
print(bytes(f.tolist()))
# CCTF{4n0t3R_h0MomORpH1C_3NcRyP7!0n_5CH3Me!}

Soda

This problem has a special RSA-based signature:

def soda(g, p, q, m):
	n, phi = p * q, (p - 1) * (q - 1)
	if isPrime(m) and m.bit_length() <= 128:
		e = m
	else:
		e = 2 * (pow(g, m**2, n) % 2**152) ^ 1
	if GCD(e, phi) == 1:
		d = inverse(e, phi)
		return pow(g, d, n)

You need to sign a specified message, and there is an oracle that allows you to sign all values except that message.

However, it can be noted that it uses m**2, which means $m$ and $-m$ have the same signature. Therefore, by using the oracle to sign $-m$ and then verifying it, you can get the flag.

from Crypto.Util.number import *
from pwn import *

# io = process(['python', 'soda_server.py'])
io = remote("01.cr.yp.toc.tf", 37711)
io.sendline(b"G")
io.recvuntil(b"n = ")
n = int(io.recvline())
print(f"{n = }")

m = bytes_to_long(b"Long Live Crypto :))")
io.sendline(b"T")
io.sendline(str(-m).encode())
io.recvuntil(b"soda(g, p, q, m) = ")
sig = int(io.recvline())
io.sendline(b"V")
io.sendline(str(sig).encode())
io.interactive()
# CCTF{f4cToriZat!On__5Tt4cK_0n_4_5i9na7urE!}

The intended solution should be as the flag suggests, to forge it by decomposing its special $e$ .

Sparse

#!/usr/bin/env python3

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

def sparse(p, k):
	nbit = p.bit_length()
	while True:
		CF = [getRandomRange(-1, 1) for _ in '_' * k]
		XP = [getRandomRange(3, nbit - 3) for _ in '_' * k]
		A = sum([CF[_] * 2 ** XP[_] for _ in range(0, k)])
		q = p + A
		if isPrime(q) * A != 0:
			return q

p = getPrime(417)
q = sparse(p, 5)
e, n = 65537, p * q
print(f'n = {n}')
m = bytes_to_long(flag.encode('utf-8'))
assert m < n
c = pow(m, e, n)
print(f'c = {c}')

The $p,q$ in this problem satisfy

q=p-\sum_{i \in S}{2^i}

where $|S| \leq 5$ , so you can consider directly brute-forcing this $|S|$ and then solving the quadratic equation to decompose it.

My script only brute-forces up to $|S|=3$ , but for the parameters of this problem, $|S|=1$ is enough.

from Crypto.Util.number import *
from itertools import combinations, chain
import gmpy2


n = 94144887513744538681657844856583985690903055376400570170371837200724227314957348031684706936655253125445176582486308241015430205703156336248578475428712275706238423997982248462635972817633320331030484841129628650918661036694615254018290264619628335177
c = 80250313885079761377138486357617323555591919111371649902793873860183455237161293320577683249054725852540874552433031133240624696119120378419135912301004715004977978507247634217071922495893934816945961054193052791946557226599493364850793396744903765857

tp = [gmpy2.mpz(1 << i) for i in range(512)]
it = chain(*[combinations(range(3, 417 - 3), i) for i in range(4)])
for cf in it:
    A = -sum([tp[i] for i in cf])
    # q = p + A
    # n=pq=p(p+A)
    # p^2+Ap-n=0
    # D=A^2-4*1*-n
    D = A**2 + 4 * n
    if gmpy2.is_square(D):
        d = gmpy2.isqrt(D)
        p = (-A + d) // 2
        q = n // p
        print(p)
        print(q)
        print(p * q == n)
        print(bin(p - q))
        break
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, n)))

Additionally, after the competition, someone mentioned that a method similar to the Google CTF problem YAFM (or PlaidCTF's xorsa) can be used, recovering bit by bit from the LSB, and then using Coppersmith.

Versace

This problem has a mysterious $n$ and $e=65537$ , and $\mathit{fi}=5^x, \mathit{th}=13^y$ as the public key.

The encryption is

\begin{aligned} c_1&=k^e \\ c_2&=5^u \\ c_3&=13^v \\ c_4&=\mathit{fi}^u \mathit{th}^v (k+1)^e m \end{aligned}

All calculations are in $\mathbb{Z}_n$

It can be known that it is a hybrid of Diffie-Hellman and RSA. Since it should calculate dlog, Utaha guessed that $\phi(n)$ should be very smooth, so I used rsactftool's Pollard p-1 to successfully decompose it into $n=pqr$ .

Then, after separately calculating dlog and using CRT, and decrypting back $k$ , you can get $m$ .

from Crypto.Util.number import *
import gmpy2

n = 141886649864474336567180245736091175577519141092893110664440298696325928109107819365023509727482657156444454196974621121317731892910779276975799862237645015028934626195549529415068518701179353407407170273107294065819774663163018151369555922179926003735413019069305586784817562889650637936781439564028325920769
p = 106618752612001652530923691512073519044983443846656721126867402977583225110529
q = 104492689192892408108975038373966852967734827395344990285038653889732962680833
r = 12735676857401163601385118447483795668229644118624917660231942016044435957817541173149617917604011645058841872384142319678290750015804888147769138207522817
assert p * q * r == n
assert all(is_prime(p) for p in [p, q, r])
n, e, fi, th = (
    141886649864474336567180245736091175577519141092893110664440298696325928109107819365023509727482657156444454196974621121317731892910779276975799862237645015028934626195549529415068518701179353407407170273107294065819774663163018151369555922179926003735413019069305586784817562889650637936781439564028325920769,
    65537,
    125494383162828289973475117066203219587304356806057400173045477137700391356840397636206107925460433939119412469184723408274805651096828270461235114589209044543108910295997506041345432448035371092981112305692014036117962906342882215492784319467728201344342591126197621795974549431806828947671232171059809967991,
    138257736445723754207239869344459794807808248188757696052272858978544083465381926995900887162870612185045399616892685750962667762789508194359878372465943702647287813020223160406789982302692329883577043521781397505345137392777694159916452699296748509096494301465498192136911589776144421856343483031920756519249,
)
c1, c2, c3, c4 = (
    88920444409754899592335110119456825172544580816901497880270628553955508488170483498726344301421934007876515783471747430111559265733377611608113080609941423596790625452564403457107243481310552344096683637970851198148957553062631972064855184560312748315536290880767375156429548232884895308088306625307674645678,
    45539956581550314230977168288877082058214432324397034618326297663129864608739856352261029083496409133620455599376139981575342903237304167908534019438874239934645347320209162850653298515960349717851268830205737252263548268549179642907155075129172651815656517165432021020317138111104384072600486843574535899860,
    69849817078368866947686316374564245958824276178721440086311727765763093314086243149277327430285562537315291446874425715021031882041090977200029684675392021083309757246079110723453995717856469919242618068208424495615283285085190255592463862108516827540775850882615540406750734639040903336048095547788528187976,
    20285007564778647051596518902857046010716548094264173639037549746086538656814534621919993169453446815272789643882592631536755194356753848872566348635207131520597253599540337542405837637606323276917410384296602682043902830628022440639028040137219164743287397377174047728489836106561656239657061612908104843401,
)

print(factor(p - 1))
print(factor(q - 1))
print(factor(r - 1))


def alllog(a, b):
    xp = ZZ(GF(p)(a).log(b))
    xq = ZZ(GF(q)(a).log(b))
    xr = ZZ(GF(r)(a).log(b))
    assert power_mod(b, xp, p) == a % p
    assert power_mod(b, xq, q) == a % q
    assert power_mod(b, xr, r) == a % r
    x = crt(
        [xp, xq, xr],
        [
            GF(p)(b).multiplicative_order(),
            GF(q)(b).multiplicative_order(),
            GF(r)(b).multiplicative_order(),
        ],
    )
    assert power_mod(b, x, n) == a
    return x


d = inverse_mod(e, (p - 1) * (q - 1) * (r - 1))
k = power_mod(c1, d, n)
x = alllog(fi, 5)
y = alllog(th, 13)
t = power_mod(c2, x, n) * power_mod(c3, y, n) * power_mod(k + 1, e, n) % n
m = (c4 / t) % n
print(long_to_bytes(m))

Watery soup

This problem has a special oracle where you need to choose two numbers $p,g$ . $p$ is a prime number between 128 and 224 bits, and $g$ is a number between 64 and 128 bits.

Then, given that the flag (more than 256 bits) is $x$ , it will give you:

r \equiv (g^3 x)^{x-g} x + x^2 + g \pmod {p}

I didn't touch this problem during the competition, but later implemented it according to Utaha's method. The concept is that since $x^x$ is difficult to handle, you need to find a way to eliminate it, so you want to use the property $g^3=1$ to see if it works.

Then, his method is to choose $tg=t+1$ in addition to $g^3=1$ , and then send $(p,t)$ and $(p,tg)$ to the oracle. Assuming the numbers obtained are $r_1, r_2$ , they are:

\begin{aligned} r_1 &= (t^3 x)^{x-t} t + x^2 + g \\ r_2 &= (t^3 x)^{x-t-1} t + x^2 + tg \end{aligned}

After simplifying, you get:

\begin{aligned} r_1 &= (t^3 x)^{x-t} t + x^2 + g \\ (t^3 x)r_2 &= (t^3 x)^{x-t} t + (t^3 x)(x^2 + tg) \end{aligned}

After eliminating, you get a polynomial of $x$ that can be solved, and you get $x \bmod{p}$ , then use CRT to get the flag back.

from sage.all import *
from pwn import *
from Crypto.Util.number import *


def gen():
    while True:
        p = ZZ(getPrime(128))
        rs = [ZZ(x) for x in GF(p)(1).nth_root(3, all=True) if x != 1]
        if len(rs) == 0:
            continue
        g = rs[0]
        t = inverse_mod(g - 1, p)  # t*g=t+1
        if (64 < t.nbits() < 128) and (64 < (t * g % p).nbits() < 128):
            return p, g, t


# io = process(["python", "watery_soup.py"])
io = remote("05.cr.yp.toc.tf", 37377)
mods = []
rems = []
while len(mods) < 3:
    p, g, t = gen()
    io.sendline(b"S")
    io.sendline(str(p).encode())
    io.sendline(str(t).encode())
    io.recvuntil(b"mixed flag: ")
    r1 = ZZ(io.recvline())
    io.sendline(b"S")
    io.sendline(str(p).encode())
    io.sendline(str((t * g) % p).encode())
    io.recvuntil(b"mixed flag: ")
    r2 = ZZ(io.recvline())
    P = PolynomialRing(GF(p), "x")
    x = P.gen()
    t3x = t**3 * x
    lhs = r1 - t3x * r2
    rhs = x**2 + t - t3x * (x**2 + t * g)
    f = lhs - rhs
    if len(f.roots()) != 1:
        continue
    x = ZZ(f.roots()[0][0])
    rems.append(x)
    mods.append(p)
x = crt(rems, mods)
print(long_to_bytes(x))
# CCTF{Pl34se_S!r_i_w4N7_5omE_M0R3_5OuP!!}

Additionally, Hellman provided another method where sending $g,2g,4g,8g$ can get a polynomial system that can also solve $x$ .

Note: This problem seems to be based on this problem (by Hellman)

hard

Persian cat

This problem has a very strange block cipher, with code that is long and difficult to read. However, the code needed to solve the problem is actually just this part:

def keygen(u, v):
    return [a ^ b for a, b in zip(u, v)][:20]


def encrypt(msg, key):
    msg = padding(msg)
    blocks = [msg[i * 32 : i * 32 + 32] for i in range(len(msg) // 32)]
    ciphers = []
    enc = encrypt_iginition([ord(item) for item in blocks[0]], key)
    ciphers.append(enc)
    for i in range(len(blocks) - 1):
        enc = encrypt_iginition(
            [ord(item) for item in blocks[i + 1]],
            keygen([ord(item) for item in blocks[i]], ciphers[i]),
        )
        ciphers.append(enc)
    return "".join("".join(str(format(i, "02x")) for i in item) for item in ciphers)

It can be known that it first divides into blocks, then uses the plaintext and ciphertext of the previous block to xor to get the key for the next block. The problem's oracle allows you to get the result of encrypt(msg + flag, key), so as long as msg == 'a' * 32, you can align the flag with the block and get the key needed to decrypt the flag.

Then, its decryption function does not need to be written by yourself, because encrypt_iginition seems to be the inverse function of itself under the same key, so you can directly solve it like this:

pt = b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
ct = bytes.fromhex(
    "127f1023480f4f61caab33b69825447a38f8d62592f4c1b0fb2f92cf3b10e4bb168e208a12f39b725addbe1e8e9f923477fa62508c0f9d7fbe0ca52026e470458f6fbf2b0ca4865e50018d735e055233ab0953882f0f3da553fcab3db6710621722ae640fa3b9e3b47c52597b9e91dc1bf6d139ea7c1cb58c83228d7b8ae3250"
)
blks = [ct[i : i + 32] for i in range(0, len(ct), 32)]
for prev, cur in zip(blks, blks[1:]):
    key = keygen(pt, prev)
    pt = bytes(encrypt_iginition(cur, key))
    print(pt.decode(), end="")
# the flag is: CCTF{d0_yOu_tH47_the_ori9iN_of_Iraqi_C1ph3r_Iz_Iran?!!}****************************

Another simpler method is to notice that encrypting twice with the same key is equivalent to not encrypting, so you can directly get the flag. (by Hellman)

medium-easy#

SOTS#

polyRSA#

medium#

Cantilever#

Diploma#

Faonsa#

Fiercest#

Starter ECC#

medium-hard#

313 Loyal#

Soda#

Sparse#

Versace#

Watery soup#

hard#

Persian cat#