CTF Challenge Name Solves (Difficulty)
TetCTF 2022 shares 🔥 29/602 (⭐⭐⭐)
TetCTF 2022 shares_v2 🔥 15/602 (⭐⭐⭐)
TetCTF 2022 fault 🔥 14/602 (⭐⭐⭐)
TetCTF 2022 algebra 🔥 14/602 (⭐⭐⭐)
DiceCTF 2022 baby-rsa 162/1127 (⭐)
DiceCTF 2022 rejected 44/1127 (⭐⭐)
DiceCTF 2022 correlated 17/1127 (⭐⭐)
DiceCTF 2022 commitment-issues 🔥 16/1127 (⭐⭐⭐)
DiceCTF 2022 pow-pow 🔥 13/1127 (⭐⭐⭐)
DiceCTF 2022 learning without errors 6/1127 (❓)
DiceCTF 2022 shibari 1/1127 (❓)
DiceCTF 2022 psych 1/1127 (❓)
TSJ CTF 2022 babyRSA 13/428 (⭐⭐)
TSJ CTF 2022 Top Secret 9/428 (⭐⭐⭐)
TSJ CTF 2022 Cipher Switching Service 🔥 4/428 (⭐⭐⭐)
TSJ CTF 2022 Signature 🔥 2/428 (⭐⭐⭐)
TSJ CTF 2022 RNG++ 21/428 (⭐⭐)
TSJ CTF 2022 RNG+++ 2/428 (⭐⭐⭐⭐)
CODEGATE 2022 PrimeGenerator 🔥 10/141 (⭐⭐⭐)
CODEGATE 2022 Dark Arts 🔥 2/141 (⭐⭐⭐⭐)
CODEGATE 2022 Happy S-Box 🔥 1/141 (⭐⭐⭐⭐)
zer0pts CTF 2022 Anti-Fermat 125/632 (⭐)
zer0pts CTF 2022 CurveCrypto 36/632 (⭐⭐)
zer0pts CTF 2022 EDDH 24/632 (⭐⭐)
zer0pts CTF 2022 OK 🔥 9/632 (⭐⭐⭐)
zer0pts CTF 2022 Karen 🔥 8/632 (⭐⭐⭐⭐)

## TetCTF 2022⌗

### shares 🔥⌗

• Solves: 29/602
• Difficulty: ⭐⭐⭐
• Tags: secret sharing
• Author: @_ndh___

Define a secret sharing scheme $\text{SecretSharing}(s, n, t)$. Hereby $s$ is the secret to share, $n$ and $t$ are respectively the number of shares returned and the minimum number of shares for recovery. Here $s = (s_1, s_2, …, s_l) \in \text{GF}(37)^l$ with $l \leq n$. The algorithm $\mathcal{A}$ below is used to generate shares.

1. Define $s' = (s_1, …, s_l, s_{l+1}, …, s_t)$ where $s_{l+1}, …, s_t \in \text{GF}(37)$ are randomly picked.
2. For $i = 1, 2, …, n$,
• Generate $a_{i, 1}, a_{i, 2}, …, a_{i, n} \in \text{GF}(37)$.
• Compute $b_i = \sum_{k=1}^n a_{ik} s_k\ \text{mod}\ 37$.
• Define $S_i := (a_{i, 1}, a_{i, 2}, …, a_{i, n}, b_i)$.
3. Return $S_1, S_2, …, S_n$ as the shares.

When connected to the server, a password with $l = 16$ is generated. Let also $n = 16$ and $t = 32$. We are given 2022 attempts to guess the password. For each incorrect attempt, we will be given a set of shares from algorithm $\mathcal{A}$. Otherwise we will be given the flag.

### shares_v2 🔥⌗

• Solves: 15/602
• Difficulty: ⭐⭐⭐
• Tags: secret sharing
• Author: @_ndh___

This challenge is based on the $\text{SecretSharing}$ algorithm defined above.

Define a secret sharing scheme $\text{SecretSharingV2}(m, s, n, t)$ with $m \geq n$. The below algorithm $\mathcal{A}_2$ is to generate shares:

1. Generate a master secret $(r_1, r_2, …, r_m)$ with $r_1, r_2, …, r_m \in \{0, 1\}$.
2. Define $S_1, S_2, …, S_n := \text{SecretSharing}(s, n, t)$. Note that $S_i = (a_{i, 1}, a_{i, 2}, …, a_{i, n}, b_i)$.
3. For each $i = 1, 2, …, n$, if $r_i = 1$, update $b_i \leftarrow (b_i + 18)\ \text{mod}\ 37$.
4. Return $(r_1, r_2, …, r_m)$ as the master secret and $S_1, S_2, …, S_n$ as the shares.

When connected to the server, a password with $l = 32$ is generated. Let also $n = 32$, $t = 32$ and $m = 128$. We are given 2022 attempts to guess the password. For each incorrect attempt, we will be given a set of shares from algorithm $\mathcal{A}_2$. Otherwise we will be given the flag.

### fault 🔥⌗

• Solves: 14/602
• Difficulty: ⭐⭐⭐
• Tags: rsa
• Author: @_ndh___

When connected to the server, a RSA private key is generated such that:

1. $p, q$ are 512-bit primes, and
2. $d$ is a 64-bit prime.

The encrypted flag $c_0$ is also computed (not returned). We are allowed to call the oracle $\mathcal{O}$ 2022 times, which does one of the below:

1. [Decrypt message] We give an $c < n$ and the server returns $\text{FaultilyDecrypt}(c)$; or
2. [Decrypt flag] The server returns $\text{FaultilyDecrypt}(c_0)$.

Hereby $\text{FaultilyDecrypt}(c)$ returns a pair $(v, m')$ where $v$ is a 64-bit integer and

$$m' = c^{d \oplus v}\ \text{mod}\ n.$$

Note that we are given nothing (including $n$ and $e$) but the oracle. The objective is to recover the flag.

### algebra 🔥⌗

• Solves: 14/602
• Difficulty: ⭐⭐⭐
• Tags: math
• Author: @_ndh___

Let $C$ be a constant and $p$ is a prime such that $x^2 + 2Cx + 1 \equiv 0\ (\text{mod}\ p)$ has two distinct roots. Define an operator $\star$ over $\text{GF}(p) \cup \{ \infty \}$ by

$$a \star b = \begin{cases} -2C &\text{if}\ a = b = \infty \\ \infty &\text{if}\ a = \infty\ \land\ b = 0 \\ -(1 + 2Cb) / b &\text{if}\ a = \infty \\ \infty &\text{if}\ ab = 1 \\ (a + b + 2Cab) / (1 - ab) &\text{otherwise} \end{cases}.$$

Define also $a^k$ by

$$a^k = \underbrace{a \star a \star \dots \star a}_{k\ \text{times}}.$$

We are given some expressions those may reveal some properties:

1. $(2020 \star 2021) \star 2022 = 2020 \star (2021 \star 2022)$, and
2. $2022^{p-1} = 0$.

When connected to the server, $a, b \in [0, p)$ and $m, n \in [0, p-1)$ are generated randomly. Also, $c := a^m \star b^n$. We are given $a, b$ and $c$ and is asked to send $\hat{a}, \hat{b}$ and $\hat{c}$ such

$$\hat{a}^m \cdot \hat{b}^n \equiv \hat{c}\ (\text{mod}\ p). \qquad [\dagger]$$

If we send $\hat{a}, \hat{b}$ and $\hat{c}$ with $[\dagger]$ holds, we will be given the first $\hat{c}^4\ \text{mod}\ p$ characters of the flag (this bans trivial solutions like $\hat{a} = \hat{b} = \hat{c} = 1$).

## DiceCTF 2022⌗

### baby-rsa⌗

• Solves: 162/1127
• Difficulty: ⭐
• Tags: rsa
• Author: ireland

We are given a RSA public key $(n, e)$ and the encrypted flag $c$. The prime factors of $n$ (i.e., $p$ and $q$) are 128-bit long and are generated such that $p \equiv q \equiv 1\ (\text{mod}\ e^2)$.

N = 57996511214023134147551927572747727074259762800050285360155793732008227782157
e = 17
cipher = 19441066986971115501070184268860318480501957407683654861466353590162062492971

The goal is to recover the flag (flag format being dice{???????????????????????}).

### rejected⌗

• Solves: 44/1127
• Difficulty: ⭐⭐
• Tags: lfsr
• Author: ireland

Suppose that there is a 64-bit LFSR and we have the feedback polynomial. We are asked to give a $n$ with $2^{27} < n < 2^{31}$ when connected to the server. We are then given up to 1023 queries to generate random numbers in $[0, n)$ via rejection sampling with algorithm $\mathcal{A}$ and obtain the number of attempts to generate such an number (the generated number is not given, however). After that, we are asked the seed and will be given the flag when the seed is correct.

Algorithm $\mathcal{A}$ is specified below (we are only given $\text{count}$ in the challenge):

1. Denote $\text{count} \leftarrow 1$ and $K \leftarrow \lfloor 2^{32} / n \rfloor$.
2. Generate 32 bits ($k_0, k_1, …, k_{31}$) from the LFSR.
3. Compute $x \leftarrow k_0 + 2 \cdot k_1 + … + 2^{31} \cdot k_{31}$.
4. If $x < n \cdot K$, return $(x\ \text{mod}\ n, \text{count})$. Otherwise set $\text{count} \leftarrow \text{count} + 1$ and go back to step 2.

### correlated⌗

• Solves: 17/1127
• Difficulty: ⭐⭐
• Tags: lfsr
• Author: ireland

Suppose that there is a 45-bit LFSR and we have the feedback polynomial. We are given 20000 bits from the LFSR (yet for every bit, there is a 20% chance that it is flipped) when connected to the server. We are asked to find the seed in 60 seconds and will be given the flag when the key is correct.

### commitment-issues 🔥⌗

• Solves: 16/1127
• Difficulty: ⭐⭐⭐
• Tags: rsa
• Author: gripingberry

Define a commitment scheme $\mathcal{C}$ that uses a composite modulus $n$ (which is a product of two 1024-bit primes $p, q$ with $p, q \neq 1\ (\text{mod}\ 5)$). To commit a secret $s$:

1. Generate a random number $r \in [0, n)$,
2. Compute $c_1 := (s + r)\ \text{mod}\ n$ and $c_2 := r^5\ \text{mod}\ n$, and
3. Return $(c_1, c_2)$ as the commitment.

Suppose that $s$ is the RSA signature of the flag (i.e., $m^d\ \text{mod}\ n$, the $m$ is the flag and $n$ serves as the modulus for $\mathcal{C}$ as well). We are given the public key of RSA $(n, e)$ and a commitment $\mathcal{C}(s) = (c_1, c_2)$. The objective is to recover the flag $m$ (flag format being dice{???????????????????????}).

e = 0xd4088c345ced64cbbf8444321ef2af8b

### pow-pow 🔥⌗

• Solves: 13/1127
• Difficulty: ⭐⭐⭐
• Tags: math
• Author: @kleptographic

We are given $n$ (a product of two 1024-bit primes) and $T = 2^{64}$ and the objective is to find $1 \leq g, h, \pi < n$ such that:

$$h = \pi^m \cdot g^r \ \text{mod}\ n,$$

where $g \neq 1$ and $g \neq n-1$, $m \leftarrow \text{HASH}(g, h)$ and $r \leftarrow 2^T\ \text{mod}\ m$.

n = 20074101780713298951367849314432888633773623313581383958340657712957528608477224442447399304097982275265964617977606201420081032385652568115725040380313222774171370125703969133604447919703501504195888334206768326954381888791131225892711285554500110819805341162853758749175453772245517325336595415720377917329666450107985559621304660076416581922028713790707525012913070125689846995284918584915707916379799155552809425539923382805068274756229445925422423454529793137902298882217687068140134176878260114155151600296131482555007946797335161587991634886136340126626884686247248183040026945030563390945544619566286476584591
T = 2**64

### learning without errors⌗

• Solves: 6/1127
• Difficulty: ❓
• Tags: ?
• Author: ireland

### shibari⌗

• Solves: 1/1127
• Difficulty: ❓
• Tags: ?
• Author: ireland

## TSJ CTF 2022⌗

### babyRSA⌗

• Solves: 13/428
• Difficulty: ⭐⭐
• Tags: ecc
• Author: @maple3142

Let $p$ and $q$ be two primes of respectively 1024 bits and 512 bits. Denote $n = pq$ and define the elliptic curve $\mathcal{C}$ by

$$\mathcal{C}: \quad y^2 \equiv x^3 + px + q\ (\text{mod}\ n).$$

Let $P = (x, y)$ be a point on $\mathcal{C}$ with $\text{flag}$ being 1536 bits long. Finally, we are given $Q$ with $Q = e \cdot P$ ($e = 65537$). The goal is to recover $x$ (the padded flag).

### Top Secret⌗

• Solves: 9/428
• Difficulty: ⭐⭐⭐
• Tags: matrix, dlog
• Author: @maple3142
def forward(s: int, n: int, k: int) -> int:
for _ in range(n):
s = (s >> 1) ^ ((s & 1) * k)
return s

class Cipher:
bs = 16
k = 0x5C2B76970103D4EEFCD4A2C681CC400D

def __init__(self, key: int):
self.key = key

def _next(self):
self.s = forward(self.s, self.key, self.k)

def ks(self, n):
ks = b""
while len(ks) < n:
self._next()
ks += self.s.to_bytes(self.bs, "big")
return ks[:n]

def encrypt(self, plaintext: bytes) -> bytes:
return bytes(x ^ y for x, y in zip(plaintext, self.ks(len(plaintext))))

def decrypt(self, ciphertext: bytes) -> bytes:
return self.encrypt(ciphertext)

The above cipher is defined for the challenge. We are given a PNG file encrypted with the above algorithm, with $\text{key} \in [0, 2^{128})$. The goal is to recover the PNG file.

### Cipher Switching Service 🔥⌗

• Solves: 4/428
• Difficulty: ⭐⭐⭐
• Tags: rsa, elgamal
• Author: @maple3142

When connected to the server, the below encryption keys are generated:

1. RSA keys $(n, e)$, here $n = pq$ ($p, q$ are both 512 bits) and $e = 65537$; and
2. ElGamal keys $(p, g, h = g^x\ \text{mod}\ p)$, here $p$ is 1024 bits.

We are given that the flag and the padded flag are of respectively 20 and 96 bytes. We are also given $\text{Enc}_\text{RSA}(\text{padded flag})$. We can call the below functions in a total of 1337 times:

1. [RSA to ElGamal] Give $c$ and we will obtain $(c_1, c_2) = \text{Enc}_\text{ElGamal}(\text{Dec}_\text{RSA}(c)))$, or
2. [ElGamal to RSA] Give $(c_1, c_2)$ and we will obtain $c = \text{Enc}_\text{RSA}(\text{Dec}_\text{ElGamal}(c_1, c_2)))$.

The objective is to recover $\text{flag}$.

### Signature 🔥⌗

• Solves: 2/428
• Difficulty: ⭐⭐⭐
• Tags: ecdsa
• Author: @maple3142

Suppose that $d$ is the private key for ECDSA (over curve secp256k1). We are given six signatures signed with the above private key. However, $k$ is computed by $k = d \oplus z$ ($z$ is the hash of the message) rather than generated randomly.

$d$ is then used to derive a key for AES-CTR which is used to encrypt the message, which is in the form Congrats! This is your flag: [FLAG]. The objective is to recover the flag.

### RNG++⌗

• Solves: 21/428
• Difficulty: ⭐⭐
• Tags: lcg
• Author: @maple3142

Suppose that we have a linear congruence generator $s_{k+1} = (a \cdot s_k + c)\ (\text{mod}\ m)$ for all $k \geq 0$. We have a transcript file that contains $m$, $a$ and $c$ ($a$ and $c$ are primes less than $m$). We are also given a number of ciphertexts. The $k$-th ciphertext $c_k$ ($k \geq 1$) is computed by:

$$c_k = m_k \oplus s_k.$$

Here $m_k$ is the $k$-th message. $m_1$ is the flag with length $l$ and $m_2, m_3, …$ are strings of length $l$ those contain digits only (for example, m2 = b"133765536"). The goal is to recover $m_1$.

In this challenge, the parameters are given below:

l = 32
# m = 2^256
m = 115792089237316195423570985008687907853269984665640564039457584007913129639936
a = 86063744400850297667628777812749377798737932751281716573108946773081904916117
c = 64628347935200268328771003490390752890895505335867420334664237461501166025747
ciphertexts = [
0x59fe4b12f3f85e6756189ba75cc7bfc6ebc5b9a9e0f008623dd008f9632927c2,
0x413c3d70d09e08d2e5b10b51800b65571f3afde82ca233351cddae591c3996d2,
0x8c6425226df355ccd09cc5c968b3cfa8fd606179346a66841ee5b7f6e6425409,
0x16cd6c30d1bff2dc1ba2e6257fb37fd5c477d0952e254aa3c5c301b0e43846c8
]

### RNG+++⌗

• Solves: 2/428
• Difficulty: ⭐⭐⭐⭐
• Tags: lcg
• Author: @maple3142

The challenge has the same setting as RNG++ with a different set of parameters:

l = 24
# m = 2^192 + 133 = NextPrime(2^192)
m = 6277101735386680763835789423207666416102355444464034513029
a = 5122535491606943208710238231068027098883286375061143870757
c = 3210047385276654404868184757570927620150853542689320481571
ciphertexts = [
0x0b8bb965128d77d56f2efc1b7ec640699927dbb711d13a41,
0x5c894788bdf78b2b7bf4081270ebb495b95c90ab6a7fb3f0,
0x737d9ea03e9fd30eeb2176aa588480c0b798682a7f4013fc,
0x299bd16cef01a65b467d5e3dfd46ec62b4e29f8994b1a4c0,
0xaa9b3e5f5635b7cab0eaa50aa854223975bfc10976a5b198,
]

## CODEGATE 2022⌗

### PrimeGenerator 🔥⌗

• Solves: 10/141
• Difficulty: ⭐⭐⭐
• Tags: math, rsa
• Author: BarkingDog

When connected to the server, a 296-bit random number $r$ is generated. We can call the below operations as many time as we wish:

1. [Generate Prime] Obtain a random 216-bit $s$ such that $2^{216}r + s$ is a 512-bit prime.
2. [Generate Ciphertext] The server finish the below procedures:
• Generate 512-bit prime $p = 2^{216}r + s$ for some $s$.
• Generate 512-bit prime $q$ randomly.
• Compute $n = pq$ and let $(n, e)$ be the RSA public key.
• Compute $c := \text{Enc}(\text{flag})$.
• Return $(n, c)$.

The objective is to recover $\text{flag}$.

### Dark Arts 🔥⌗

• Solves: 2/141
• Difficulty: ⭐⭐⭐⭐
• Tags: math
• Author: @rkm0959

This challenge consists of four stages. One needs to complete the four stages in 300 seconds to gain the flag.

#### Stage 1⌗

At the beginning of each round, a key $(k_1, k_2, …, k_{256}) \in \mathbb{Z}_2^{256}$ and the “answer” $m \in \mathbb{Z}_2$ are randomly generated.

We can send $a = (a_1, a_2, …, a_{256}) \in \mathbb{Z}_2^{256}$ as many times as we want. The server would finish the below steps:

1. If one has already asked with $a$, a cached $y_m$ will be returned.
2. Denote $r = \sum a_i \cdot k_i$. Compute $y_0 = ((r\ \text{mod}\ 2) + (r\ \text{mod}\ 3))\ \text{mod}\ 2$.
3. Pick $y_1 \in \mathbb{Z}_2$ randomly.
4. Return $y_m$ to us.

We need to find the correct $m$ for 64 rounds, without failing, to proceed.

#### Stage 2⌗

At the beginning of each round, a key $(k_1, k_2, …, k_{256}) \in \mathbb{Z}_2^{256}$ and the “answer” $m \in \mathbb{Z}_2$ are randomly generated.

We can send $a$ as many times as we want. The server would finish the below steps:

1. Compute $h = (h_1, h_2, …, h_{256}) \in {\mathbb{Z}_2}^{256}$ to be the bits of $\text{SHA256}(a)$.
2. If one has already asked with $h$, a cached $y_m$ will be returned.
3. Denote $r = \sum h_i \cdot k_i$. Compute $y_0 = ((r\ \text{mod}\ 5) + (r\ \text{mod}\ 7))\ \text{mod}\ 5$.
4. Pick $y_1 \in \mathbb{Z}_2$ randomly.
5. Return $y_m$ to us.

We need to find the correct $m$ for 64 rounds, without failing, to proceed.

#### Stage 3⌗

At the beginning, a key $k = (k_1, k_2, …, k_{64}) \in \mathbb{Z}_4^{64}$ is generated.

We can send $a$ as many time as we want. The server would finish the below steps:

1. Compute $h = (h_1, h_2, …, h_{64}) \in \mathbb{Z}_5^{64}$ from $\text{SHA256}(a)$.
2. Denote $r = \sum h_i \cdot k_i$.
3. Return $r\ \text{mod}\ 5\ \text{mod}\ 2$ to us.

We need to guess $k$ correctly to proceed.

#### Stage 4⌗

At the beginning, a key $k = (k_1, k_2, …, k_{16}) \in \mathbb{Z}_{2^{256}}^{16}$ is generated. A 257-bit $p$ and a 129-bit $q$ are also generated and we are given $p$ and $q$.

We can send $a$ as many time as we want. The server would finish the below steps:

1. Compute $h = (h_1, h_2, …, h_{16}) \in \mathbb{Z}_{2^{256}}^{64}$ by SHA256 $a$ multiple times.
2. Denote $r = \sum h_i \cdot k_i$.
3. Return $((r\ \text{mod}\ p) + (r\ \text{mod}\ q))\ \text{mod}\ p$ to us.

We need to guess $k$ correctly to proceed.

### Happy S-Box 🔥⌗

• Solves: 1/141
• Difficulty: ⭐⭐⭐⭐
• Tags: lfsr, sbox
• Author: @RBTree_
class LFSR:
rand = random.Random("Codegate2022")
Sbox = [ [0] * 64 + [1] * 64 for _ in range(512 - 6) ]
for i in range(len(Sbox)):
rand.shuffle(Sbox[i])

def __init__(self, seed):
self.state = seed
for _ in range(1024):
self.next()
print(format(self.state, '0512b'))
assert False

def next(self):
v = self.state
# x^512 + x^8 + x^5 + x^2 + 1
n = ((v >> 0) ^ (v >> 504) ^ (v >> 507) ^ (v >> 509)) & 1
self.state = (v >> 1) | (n << 511)

def output(self):
out = 0
for i in range(512 - 6):
out ^= self.Sbox[i][(self.state >> i) & 127]
return out

Denote the above implementation of LFSR by LFSR*.

When connected to the server, a 500-bit number $s$ is generated. We are given the first bit of lfsr.output() for every LFSR* with seed $2^{12} s, 2^{12} s + 1, …, 2^{12} s + 4095$. The objective is to recover $s$.

## zer0pts CTF 2022⌗

### Anti-Fermat⌗

• Solves: 125/632
• Difficulty: ⭐
• Tags: rsa
• Author: @ptrYudai

Suppose that $p$ and $q$ are two 1024-bit prime of RSA such that

$$q = \text{NextPrime}(p \oplus \text{MASK}),$$

where $\text{MASK} = 2^{1024} - 1$. We are given the public key $(n = pq, e)$ and the encrypted flag $c$. The goal is to recover the flag.

### CurveCrypto⌗

• Solves: 36/632
• Difficulty: ⭐⭐
• Tags: ecc
• Author: @theoremoon

Suppose that $p$ and $q$ are two 512-bit primes with $p \equiv q \equiv 3\ (\text{mod}\ 4)$. Define $n := pq$ and generate $a, b \in \mathbb{Z}_n$ randomly. Define the elliptic curve $\mathcal{C}$ by

$$\mathcal{C}: y^2 \equiv x^3 + ax + b\ (\text{mod}\ n).$$

Let $G \in \mathcal{C}$ be a random point. Suppose that $m_1, m_2, …$ are 16-byte plaintext blocks (which is the flag). The ciphertext $(c_1, c_2, …)$ is defined by

\begin{aligned} c_1 = m_1 \oplus G_x, \qquad & c_2 = m_2 \oplus G_y \\ c_3 = m_3 \oplus (2G)_x, \qquad & c_4 = m_4 \oplus (2G)_y \\ c_5 = m_5 \oplus (4G)_x, \qquad & c_6 = m_6 \oplus (2^2G)_y \\ … \end{aligned}

Here $(kG)_x$ and $(kG)_y$ are respectively the x and y-coordinate of $kG$. We are given $n, a, b, (c_1, c_2, …)$ and the objective is to recover the flag.

### EDDH⌗

• Solves: 24/632
• Difficulty: ⭐⭐
• Tags: ecc
• Author: @theoremoon

Define the Edward’s curve $\mathcal{C}$ over modulo $p$ (a 256-bit prime) and a generator $G \in \mathcal{C}$ with $|G| = q$:

$$\mathcal{C}: x^2 + y^2 \equiv c(1 + dx^2 y^2)\ (\text{mod}\ p).$$

The parameters are given below:

p  = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a  = 362
d  = 1
q  = 64141017538026690847507665744072764126693080268699847241685146737444135961328
c  = 4
gx = 36618472676058339844598776789780822613436028043068802628412384818014817277300
gy = 997024778044160712222759651785524947622008210955201775563781855981697196559

When connected to the server, we are given $P$ defined by $P = sG$ with $s \in [0, q)$. We can send a point $Q$. A shared point $T = (T_x, T_y)$ is computed by $T = sQ$. $T_x$ and $T_y$ is used as a 64-byte keystream (would not change throughout the communication) that is used to encrypt the communication between the server and the client afterwards (denoted by $k$).

For most of the cases, the server would perform the below steps when a message $c$ (of length $\leq 64$) is received:

1. Compute $m_0 = c \oplus k$
2. Compute $m := \text{Unpad}(m_0)$ ($\text{Unpad}$ truncates everything since the last null bytes). Terminates when $m_0$ does not have a null byte.
3. If $m = \text{quit}$, terminates the interaction.
4. If $m = \text{flag}$, sends $c' = \text{Pad}(\text{FLAG})$ \oplus k.
5. Otherwise, compute $c' = \text{Pad}(m) \oplus k$.

Note that $\text{Pad}(m)$ adds a null byte followed by FF’s until $m$ is 64 bytes long. Also, $\text{FLAG}$ is the flag encrypted in AES with key derived from $s$. The objective is to recover the flag.

### OK 🔥⌗

• Solves: 9/632
• Difficulty: ⭐⭐⭐
• Tags: oblivious transfer, rsa
• Author: @theoremoon, @kymn_

Suppose $P = 2^{1000} - 1245$ and $e = 65537$.

When connected to the server, the below procedures will be operated:

1. The server generates two 512-bit primes $p$ and $q$.
2. The server computes $n = pq$ and defines a RSA key $(n, e, d)$.
3. The server generates $x_1, x_2, k \in \mathbb{Z}_n$ randomly.
4. The server computes the ciphertext $c$ by $c := (\text{FLAG}^e\ \text{mod}\ P) \oplus k$.
5. The server sends $n, x_1, x_2$ to us.
6. We send a $v \in \mathbb{Z}$ to the server.
7. The server computes $k_1 = (v - x_1)^d\ \text{mod}\ n$ and $k_2 &= (v - x_2)^d\ \text{mod}\ n$
8. The server computes $c_1 = (k_1 + k)\ \text{mod}\ n$ and $c_2 = (k_2 + c)\ \text{mod}\ n$.

The objective is to recover the flag $\text{FLAG}$.

### Karen 🔥⌗

• Solves: 8/632
• Difficulty: ⭐⭐⭐⭐
• Tags: math
• Author: @theoremoon

Suppose that $m = 351$ and $n = 70$. Let $p$ be a 512-bit prime, $x_1, x_2, …, x_n \in \mathbb{Z}_p$ and $a_{11}, a_{12}, …, a_{mn} \in \{0, 1\}$ be randomly generated (Except $a_{1k}, a_{2k}, …, a_{mk}$ for some unknown $k \in \{1, 2, …, n\}$, which are the flag bits).

It is known that

$$\left[\begin{matrix} h_1 \\ \vdots \\ h_m \end{matrix}\right] \equiv \left[\begin{matrix} a_{11} & \cdots & a_{1n} \\ & \vdots & \\ a_{m1} & \cdots & a_{mn} \end{matrix}\right]\left[\begin{matrix} x_1 \\ \vdots \\ x_n \end{matrix}\right]\ (\text{mod}\ p).$$

We are given $p$ and $h_1, h_2, …, h_m$. The objective is to recover $a_{1k}, a_{2k}, …, a_{mk}$ (i.e., the flag bits).