Crypto in CTF: Q1 2022

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
N = 0xba8cb3257c0c83edf4f56f5b7e139d3d6ac8adf71618b5f16a02d61b63426c2c275ce631a0927b2725c6cc7bdbe30cd8a8494bc7c7f6601bcee5d005b86016e79919e22da4c431cec16be1ee72c056723fbbec1543c70bff8042630c5a9c23f390e2221bed075be6a6ac71ad89a3905f6c706b4fb6605c08f154ff8b8e28445a7be24cb184cb0f648db5c70dc3581419b165414395ae4282285c04d6a00a0ce8c06a678181c3a3c37b426824a5a5528ee532bdd90f1f28b7ec65e6658cb463e867eb5280bda80cbdb066cbdb4019a6a2305a03fd29825158ce32487651d9bfa675f2a6b31b7d05e7bd74d0f366cbfb0eb711a57e56e6db6d6f1969d52bf1b27b
c1 = 0x75240fcc256f1e2fc347f75bba11a271514dd6c4e58814e1cb20913195db3bd0440c2ca47a72efee41b0f9a2674f6f46a335fd7e54ba8cd1625daeaaaa45cc9550c566f6f302b7c4c3a4694c0f5bb05cd461b5ca9017f2eb0e5f60fb0c65e0a67f3a1674d74990fd594de692951d4eed32eac543f193b70777b14e86cf8fa1927fe27535e727613f9e4cd00acb8fab336894caa43ad40a99b222236afc219397620ca766cef2fe47d53b07e302410063eae3d0bf0a9d67793237281e0bfdd48255b58b2c1f8674a21754cf62fab0ba56557fa276241ce99140473483f3e5772fcb75b206b3e7dfb756005cec2c19a3cb7fa17a4d17f5edd10a8673607047a0d1
c2 = 0xdb8f645b98f71b93f248442cfc871f9410be7efee5cff548f2626d12a81ee58c1a65096a042db31a051904d7746a56147cc02958480f3b5d5234b738a1fb01dc8bf1dffad7f045cac803fa44f51cbf8abc74a17ee3d0b9ed59c844a23274345c16ba56d43f17d16d303bb1541ee1c15b9c984708a4a002d10188ccc5829940dd7f76107760550fac5c8ab532ff9f034f4fc6aab5ecc15d5512a84288d6fbe4b2d58ab6e326500c046580420d0a1b474deca052ebd93aaa2ef972aceba7e6fa75b3234463a68db78fff85c3a1673881dcb7452390a538dfa92e7ff61f57edf48662991b8dd251c0474b59c6f73d4a23fe9191ac8e52c8c409cf4902eeaa71714

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

psych⌗

• Solves: 1/1127
• Difficulty: ❓
• Tags: ?
• Author: @kleptographic

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
    s = 0x6BF1B9BAE2CA5BC9C7EF4BCD5AADBC47
    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,
    0xea4aac7bf92c87cad6584d4cd8337af93afc2fd42314c02298afcdd26ec42771,
    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,
    0xdfdcac905116a9f8ac0fb9bdf8da193616b58713daa7dade,
    0x520b8ea46a7ad0a590064b6f067b9b3962c4874541eb34f0,
    0xa490b4afaf268540b0ecafff938b4531ad06b5706a4d68e6,
    0x087726f7bf592ad0ee92e78773dc860f4975766f382bf192
]

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