I participated in AeroCTF as a member of Super Guesser. We reached 1st place :)

We were able to grab first bloods on all three cryptography challenges.

Phoenix was solved by rbtree, and I solved horcrux and boggart.

### Phoenix

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #!/usr/bin/env sage   p = 2 F = GF(p) P. = PolynomialRing(F)     class Cipher:     def __init__(self, size, params):         self.size = size         self.params = params       def sequence(self, key):         while True:             key = key * self.params[0]             yield key + self.params[1]       def encrypt(self, key, data, strength):         for value, pbit in zip(self.sequence(key), data):             xbit = sum(value[i] for i in range(0, strength, 2))             ybit = mul(value[i] for i in range(1, strength, 2))                          yield int(pbit) ^^ int(xbit) ^^ int(ybit)     def main():     size = 256     length = 1024     strength = 10       q = P.irreducible_element(size, 'minimal_weight')     R. = P.quo(q)       key, a, b = [R.random_element() for _ in range(3)]       with open('flag.txt', 'rb') as file:         flag = file.read().strip()       message = int.from_bytes(flag, 'big')     assert message.bit_length() < size     plaintext = list(map(int, bin(message)[2:]))     padding = [0] * (length - len(plaintext))       cipher = Cipher(size, [a, b])     ciphertext = list(cipher.encrypt(key, padding + plaintext, strength))     result = int(''.join(map(str, ciphertext)), 2)       print(a)     print(b)     print(result)     if __name__ == '__main__':     main()   Colored by Color Scripter cs

#### Solution (due to rbtree)

Let's look at the encryption scheme.

We have a key $k \in GF(2^{256})$ and known parameters $a, b \in GF(2^{256})$.

To encrypt a plaintext $m$, it is first converted to binary then padded at the front with zeros to have length 1024.

Then, we take the first 10 bits of the polynomial representation of $a^i k +b$ for each $i$, and calculate $$xbit_i = \sum \text{(even index bits)}$$ $$ybit_i = \prod \text{(odd index bits)}$$ where calculations are done in $GF(2)$.

Finally, we encrypt our text with a stream cipher, i.e. XOR our plaintext with $\{xbit_i \oplus ybit_i\}_{i \ge 1}$.

We now make some observations.

• It's very likely that $ybit_i$ is $0$, since it is a product of 5 bits. Heuristically, it has a $31/32$ chance of being $0$.
• The message bit length is guaranteed to be less than 256. This means the length of the padding is at least 768.
• If we write each 256 coefficients of $k$ as variables, then $xbit_i$ can be written as a linear combination of them (and $0, 1$)

Now we have our solution idea.

• If we assume that $ybit_i = 0$ and know the ptxt/ctxt bits, we can recover $xbit_i$. This gives us a linear equation over our 256 variables.
• Of course, we know 768 bits of the plaintext and all of the ciphertext, so we can do this for 768 different values of $i$.
• We take 256 equations out of those 768 and hope that the system of equations have a unique solution.
• If there is a unique solution, we can recover the key and perform the decryption process to get a candidate for our flag.
• If our recovered flag has "Aero{" in it, we can finish the challenge. If not, we try another set of 256 equations.

We need to have $ybit = 0$ for all 256 bits/equations we selected. This has a probability of $$(31/32)^{256} \approx 0.0003$$ of succeeding, and we also need our system to be uniquely solvable. Thankfully, our algorithm terminates in about 2000 trials, and each trial doesn't take too long. It seems like SageMath is very efficient when it comes to matrices over $GF(2)$ :)

Here's the solution script, by rbtree. It runs in a few minutes.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 import random from Crypto.Util.number import *   p = 2 F = GF(p) P. = PolynomialRing(F)   size = 256 length = 1024 strength = 10   q = P.irreducible_element(size, 'minimal_weight') R. = P.quo(q)   class Cipher:     def __init__(self, size, params):         self.size = size         self.params = params       def sequence(self, key):         while True:             key = key * self.params[0]             yield key + self.params[1]       def encrypt(self, key, data, strength):         for value, pbit in zip(self.sequence(key), data):             xbit = sum(value[i] for i in range(0, strength, 2))             ybit = mul(value[i] for i in range(1, strength, 2))                          yield int(pbit) ^^ int(xbit) ^^ int(ybit)   enc = 69824286833704501471834043923417254326103912707315595840737453739249974863266259092449058810542265536810346421685955365128856715192808287450464619418781355923155781710833586631897182535937891456025282049302526058466298304955387306232279075295308862156912873485647349272079984781574084434511227361370780842056 enc = list(map(int, bin(enc)[2:])) enc = [0] * (length - len(enc)) + enc   a = x^255 + x^252 + x^246 + x^245 + x^240 + x^239 + x^236 + x^234 + x^233 + x^232 + x^231 + x^229 + x^228 + x^227 + x^224 + x^223 + x^218 + x^217 + x^216 + x^215 + x^210 + x^209 + x^204 + x^202 + x^200 + x^198 + x^197 + x^196 + x^192 + x^188 + x^187 + x^182 + x^181 + x^180 + x^178 + x^177 + x^176 + x^174 + x^173 + x^172 + x^167 + x^166 + x^161 + x^160 + x^157 + x^155 + x^154 + x^151 + x^150 + x^149 + x^148 + x^147 + x^146 + x^144 + x^140 + x^137 + x^135 + x^133 + x^132 + x^130 + x^129 + x^126 + x^122 + x^119 + x^118 + x^115 + x^112 + x^111 + x^109 + x^107 + x^106 + x^105 + x^104 + x^101 + x^100 + x^99 + x^97 + x^96 + x^94 + x^92 + x^87 + x^86 + x^84 + x^83 + x^81 + x^79 + x^75 + x^71 + x^69 + x^68 + x^67 + x^66 + x^65 + x^63 + x^62 + x^61 + x^56 + x^55 + x^53 + x^52 + x^50 + x^46 + x^44 + x^43 + x^41 + x^39 + x^38 + x^37 + x^36 + x^35 + x^34 + x^33 + x^32 + x^30 + x^29 + x^27 + x^24 + x^21 + x^17 + x^16 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^5 + x^4 + x^3 + x + 1 b = x^255 + x^254 + x^250 + x^247 + x^243 + x^242 + x^241 + x^238 + x^235 + x^232 + x^229 + x^227 + x^222 + x^221 + x^219 + x^218 + x^217 + x^216 + x^215 + x^211 + x^207 + x^206 + x^204 + x^202 + x^201 + x^197 + x^195 + x^193 + x^192 + x^190 + x^189 + x^188 + x^186 + x^184 + x^181 + x^180 + x^179 + x^178 + x^176 + x^173 + x^172 + x^169 + x^167 + x^165 + x^161 + x^160 + x^158 + x^149 + x^147 + x^146 + x^145 + x^140 + x^138 + x^137 + x^134 + x^133 + x^132 + x^130 + x^129 + x^128 + x^126 + x^125 + x^124 + x^121 + x^120 + x^118 + x^117 + x^114 + x^112 + x^111 + x^110 + x^109 + x^108 + x^107 + x^106 + x^105 + x^101 + x^96 + x^95 + x^94 + x^93 + x^92 + x^90 + x^89 + x^88 + x^86 + x^85 + x^84 + x^83 + x^81 + x^80 + x^79 + x^78 + x^77 + x^76 + x^71 + x^70 + x^69 + x^68 + x^67 + x^64 + x^63 + x^59 + x^56 + x^55 + x^53 + x^50 + x^46 + x^43 + x^42 + x^40 + x^38 + x^37 + x^35 + x^34 + x^33 + x^25 + x^23 + x^22 + x^21 + x^18 + x^16 + x^14 + x^13 + x^12 + x^11 + x^10 + x^8 + x^3 + x^2 + x t = sum(b[i] for i in range(0, 10, 2))   vs = [ x^i for i in range(size) ] vecs = [] for idx in range(length - size):     for i in range(size):         vs[i] = vs[i] * a          arr = [int( sum(vs[j][i] for i in range(0, 10, 2)) ) for j in range(size)]     val = int(t) ^^ enc[idx]       vecs.append( (arr, val) )     cipher = Cipher(size, [a, b]) cnt = 0 while True:     cnt += 1     random.shuffle(vecs)       mat = Matrix(F, [vecs[i][0] for i in range(size)])     vec = Matrix(F, [vecs[i][1] for i in range(size)]).transpose()     try:         vec = mat.inverse() * vec           key = 0         for i in range(size):             if int(vec[i][0]):                 key += x^i           plaintext = list(cipher.encrypt(key, enc, strength))         plaintext = int(''.join(map(str, plaintext)), 2)         plaintext = long_to_bytes(plaintext)           if b'Aero{' in plaintext:             while True:                 print(plaintext)         else:             print("FAIL2", cnt)       except:         print("FAIL", cnt)         pass Colored by Color Scripter cs

### Horcrux

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 #!/usr/bin/env python3.8   from os import urandom from gmpy2 import next_prime from random import randrange, getrandbits from Crypto.Cipher import AES from fastecdsa.curve import Curve     def bytes_to_long(data):     return int.from_bytes(data, 'big')     def generate_random_point(p):     while True:         a, x, y = (randrange(0, p) for _ in range(3))         b = (pow(y, 2, p) - pow(x, 3, p) - a * x) % p           if (4 * pow(a, 3, p) + 27 * pow(b, 2, p)) % p != 0:             break       return Curve(None, p, a, b, None, x, y).G     class DarkWizard:     def __init__(self, age):         self.power = int(next_prime(getrandbits(age)))         self.magic = generate_random_point(self.power)         self.soul = randrange(0, self.power)       def create_horcrux(self, location, weakness):         # committing a murder         murder = self.cast_spell(b'AVADA KEDAVRA')           # splitting the soul in half         self.soul = self.soul * pow(2, -1, self.power) % self.power           # making a horcrux         horcrux = (self.soul + murder) * self.magic           # nobody should know location and weakness of the horcrux         horcrux.x ^= location         horcrux.y ^= weakness           return horcrux       def cast_spell(self, spell_name):         spell = bytes_to_long(spell_name)           return spell %~ spell     def encrypt(key, plaintext):     cipher = AES.new(key=key, mode=AES.MODE_ECB)     padding = b'\x00' * (AES.block_size - len(plaintext) % AES.block_size)       return cipher.encrypt(plaintext + padding)     def main():     wizard_age = 3000     horcruxes_count = 2       wizard = DarkWizard(wizard_age)     print(f'Wizard\'s power:\n{hex(wizard.power)}\n')     print(f'Wizard\'s magic:\n{wizard.magic}\n')       key = urandom(AES.key_size[0])     horcrux_length = len(key) // horcruxes_count       for i in range(horcruxes_count):         key_part = key[i * horcrux_length:(i + 1) * horcrux_length]           horcrux_location = bytes_to_long(key_part[:horcrux_length // 2])         horcrux_weakness = bytes_to_long(key_part[horcrux_length // 2:])           horcrux = wizard.create_horcrux(horcrux_location, horcrux_weakness)         print(f'Horcrux #{i + 1}:\n{horcrux}\n')       with open('flag.txt', 'rb') as file:         flag = file.read().strip()       ciphertext = encrypt(key, flag)     print(f'Ciphertext:\n{ciphertext.hex()}')     if __name__ == '__main__':     main()   Colored by Color Scripter cs

#### Solution

We first take a look at what's going on.

• We have a 3000 bit prime $p$, which we know.
• We have a point $G$ on some elliptic curve $y^2 = x^3 + ax + b$ over $\mathbb{F}_p$ - we know $G$ but we don't know $a, b$.
• We have a 128 bit AES key we have to recover : this is split into two "horcruxes" of 64 bits.
• Each horcrux is split into two parts of 32 bits - they are XOR'ed to the coordinates of some point on the curve then given.

Writing this in mathematical equations, we have

• We are given a 3000 bit prime $p$ and three coordinates $(x_0, y_0), (x_1, y_1), (x_2, y_2)$
• 128 bit AES key is equal to $\alpha_1 || \beta_1 || \alpha_2 || \beta_2$ with each part being 32 bits, i.e. less than $2^{32}$.
• $(x_0, y_0)$ lies on a elliptic curve $y^2 = x^3 + ax + b$ over $\mathbb{F}_p$, so $y_0^2 = x_0^3 + ax_0 + b$ in $\mathbb{F}_p$.
• $(x_1 \oplus \alpha_1, y_1 \oplus \beta_1)$ lies on the curve, so $(y_1 \oplus \beta_1)^2 = (x_1 \oplus \alpha_1)^3 + a(x_1 \oplus \alpha_1) + b$
• $(x_2 \oplus \alpha_2, y_1 \oplus \beta_2)$ lies on the curve, so $(y_2 \oplus \beta_2)^2 = (x_2 \oplus \alpha_2)^3 + a(x_2 \oplus \alpha_2) + b$

Since XOR is hard to deal with, we change it to normal addition - of course, it's clear that

• $U, V \ge 0$, $V < 2^b$ implies $|(U \oplus V) - U| < 2^b$.

Therefore, we can change each XOR to addition, by changing our constraints from $0 \le \alpha_i, \beta_i < 2^{32}$ to $|\alpha_i|, |\beta_i| < 2^{32}$.

Now we have to solve, given $p, x_0, y_0, x_1, y_1, x_2, y_2$, the system of equations \begin{equation*} \begin{aligned} y_0^2 &= x_0^3 + ax_0 + b \\ (y_1 + \beta_1)^2 &= (x_1 + \alpha_1)^3 + a(x_1 + \alpha_1) + b \\ (y_2 + \beta_2)^2 &= (x_2 + \alpha_2)^3 + a(x_2 + \alpha_2) + b \end{aligned} \end{equation*} over $\mathbb{F}_p$ and $|\alpha_i|, |\beta_i| < 2^{32}$. Now what do we do? There were a few ideas at this point...

Idea 1 : Lattices

Of course, "small solutions" imply that we have to use lattices. Maybe we can directly use them here?

For example, using github.com/rkm0959/Inequality_Solving_with_CVP we can solve a system of linear inequalities.

Turns out, it's quite difficult to do so, since our system has terms like $a \alpha_1$ and $a \alpha_2$.

Because we don't know the value of $a$ and its size can be large, we can't deal with this term using this method.

To use the tool in the link, we need all terms of our equations to be either

• linear in terms of our variables (i.e. variable multiplied by a known constant)
• small (so that we can move this to the lower bound / upper bound vector for the CVP)

In this case, $a \alpha_1$ and $a \alpha_2$ term does not satisfy this requirement.

Idea 2 : Determinant

The failure of our Idea 1 leads to the key idea : removing $a$ in our system completely.

This can be done by realizing that $[1, -a, -b]^{T}$ is in the kernel of the matrix $$\left[ \begin{matrix} y_0^2 - x_0^3 & x_0 & 1 \\ (y_1 + \beta_1)^2 - (x_1 + \alpha_1)^3 & (x_1 + \alpha_1) & 1 \\ (y_2 + \beta_2)^2 - (x_2 + \alpha_2)^3 & (x_2 + \alpha_2) & 1 \end{matrix} \right]$$ which means its determinant must be $0$ in $\mathbb{F}_p$. This gives us a polynomial equation in $\alpha_1, \alpha_2, \beta_1, \beta_2$. Now what?

The first idea was multivariable coppersmith - I tried to use defund's implementation, but the matrix size got way too large.

The second idea is, of course, lattices from Idea 1. If we expand our determinant, we will get a equation of the form $$\sum \text{(constant coefficient)} \cdot \text{(some monomial)} = 0$$ we can simply bound each monomials with $|\alpha_i|, |\beta_i| < 2^{32}$, then solve using the CVP toolkit above.

To be more precise : our equation will be in a form of $$\sum_{i=1}^k c_i m_i \equiv -c_{k+1} \pmod{p}$$ where $c_i$ is a known constant and $m_i$ is some non-constant monomial over $\alpha_i$, $\beta_i$. (Consider $m_{k+1}$ as $1$)

We solve this system by utilizing the following inequalities and plugging them into the CVP toolkit :

$$-2^{32 \cdot \deg(m_i)} < m_i < 2^{32 \cdot \deg(m_i)}$$ $$\sum_{i=1}^k c_i m_i+ pX = -c_{k+1}$$ where $\deg(m_i)$ is the degree of the monomial. Note that abuse of notation was used - $m_i$ is used both as a monomial, and as the actual value of the monomial with the true values of $\alpha_i$, $\beta_i$ plugged in. For further details, please take a look in the github repo and the solution.

UPD : Mystiz gives a good insight on entropy to explain why this line of thinking works. Link is here.

This is a very useful way to think about whether or not the above CVP toolkit will work, when it comes to the uniqueness of the solution.

### Boggart

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 #!/usr/bin/env python3.8   from gmpy import next_prime from random import getrandbits     def bytes_to_long(data):     return int.from_bytes(data, 'big')     class Wardrobe:     @staticmethod     def create_boggarts(fear, danger):         # for each level of danger we're increasing fear         while danger > 0:             fear = next_prime(fear)               if getrandbits(1):                 yield fear                 danger -= 1     class Wizard:     def __init__(self, magic, year, experience):         self.magic = magic         self.knowledge = year - 1 # the wizard is currently studying the current year         self.experience = experience       def cast_riddikulus(self, boggart):         # increasing the wizard's experience by casting the riddikulus charm         knowledge, experience = self.knowledge, self.experience           while boggart > 1:             knowledge, experience = experience, (experience * self.experience - knowledge) % self.magic             boggart -= 1           self.experience = experience     def main():     year = 3     bits = 512     boggart_fear = 31337     boggart_danger = 16       neutral_magic, light_magic, dark_magic = [getrandbits(bits) for _ in range(3)]     magic = next_prime(neutral_magic | light_magic) * next_prime(neutral_magic | dark_magic)       print('Hello. I am Professor Remus Lupin. Today I\'m going to show you how to deal with the boggart.')       print(neutral_magic)     print(magic)       with open('flag.txt', 'rb') as file:         flag = file.read().strip()       # some young wizards without knowledge of the riddikulus charm     harry_potter = Wizard(magic, year, bytes_to_long(b'the boy who lived'))     you = Wizard(magic, year, bytes_to_long(flag))       for boggart in Wardrobe.create_boggarts(boggart_fear, boggart_danger):         # wizards should train to learn the riddikulus charm         harry_potter.cast_riddikulus(boggart)         you.cast_riddikulus(boggart)       # wizard's experience should be increased     print(harry_potter.experience)     print(you.experience)     if __name__ == '__main__':     main()   Colored by Color Scripter cs

#### Solution

There is a lot going on in this code, so let's take a look at it.

• We have random 512 bit integer $M_N, M_L, M_D$ corresponding to neutral/light/dark magic
• The value magic is created as $M = \text{next_prime}(M_N | M_L) \times \text{next_prime}(M_N | M_D)$.
• We are given the values of $M_N$ and $M$ - so the factorization of $M$ is unknown.

Now, the text "the boy who lived" and the flag goes through some encryption process, and we know their ciphertexts.

• The encryption process itself is quite random - it uses the cast_ridikkulus algorithm randomly.
• To be more precise, it starts the parameter "fear" at 31337, and increases it to the next prime each time.
• Then, with a 50% chance, the text gets encrypted with the said value of "fear" and the cast_ridikkulus algorithm.
• If we have used the cast_ridikkulus algorithm 16 times, the encryption process terminates.

cast_riddikulus algorithm

Naturally, we have to look at the cast_riddikulus algorithm and how to reverse/decrypt it.

We note that the value of self.knowledge is fixed at $2$ at all times. Denote the self.experience as $x$, and the boggart as $n$.

The algorithm calculates a linear recurrence - it starts with $a_0=2$, $a_1 = x$, and moves up by $$a_{i} = xa_{i-1} - a_{i-2}$$ Let's forget about the modulos and solve this recurrence. Using standard techniques, we get $$a_n = \left( \frac{x - \sqrt{x^2 - 4}}{2} \right)^n + \left( \frac{x + \sqrt{x^2- 4}}{2} \right)^n$$ This looks kinda scary, but then we can see that this is just $$x = t + t^{-1} \implies a_n = t^n + t^{-n}$$ Note that this implication holds even when we consider the fact that we are working modulo $M$.

This has a lot of meaning - for example, the encryption function is commutative in a sense that encrypting a text (experience) with (boggart) $m$ then $n$ is equivalent to encrypting with $n$ then $m$, which is equivalent to encryption once with $mn=nm$.

It also implies that under some "mild" conditions, we can reverse the encryption function as follows -

• Given $ctxt \equiv t^n + t^{-n} \pmod{M}$, we solve for the value $t^n \pmod{M}$.
• We solve for $t \pmod{M}$ using the value of $t^n \pmod{M}$.
• We get our original value $ptxt = t + t^{-1} \pmod{M}$.

In the above algorithm, we needed

• Factorization of $M$, and we need $t$ to be coprime to $M$
• $t^n + t^{-n} \equiv ctxt \pmod{M}$ to be solvable, i.e. $ctxt^2 - 4$ being a quadratic residue
• $n$ being coprime to $\phi(M)$, for the discrete root to be easy to solve
• (of course, we can use adlemann root extraction, but that's not very fast)

Let's review our requirements and how difficult they are

• Factorization of $M$ : this is hard but must be done - and this is probably why we are given $M_N$.
• $t$ being coprime to $M$ : this will probably hold even if we don't care about it
• $ctxt^2 - 4$ being a quadratic residue : if not, we can just get our random values of $M_N, M_L, M_D, M$ again.
• $n$ being coprime to $\phi(M)$ : in our context, we will use 16 primes larger than $30000$ as $n$, so it'll most likely be true.

Therefore, it's time to go back and try to factorize $M$ with our information of $M_N$.

factorization of $M$

The key idea is that the value of $M_N$ gives us known bits of each prime $p, q$ of $M$.

• $M_N|M_L$ and $M_N|M_D$ obviously has all bits that $M_N$ has.
• Then, we apply the next_prime function. Due to the small prime gap, this is similar to adding a few thousand to each number.
• Therefore, some lower bits will definitely change, and even higher bits can change due to carry

Consider $M'_N = M_N - (M_N \pmod{2^{16}})$, i.e. $M_N$ but changed the $16$ LSB to 0.

• If no carry happens at the 16th bit, our primes will still have all the bits of $M'_N$.
• If a carry happens at the 16th bit, we hope our primes will still have all the bits of $M'_N + 2^{16}$.

Therefore, we write $M''_N = M'_N \& (M'_N + 2^{16})$ and claim that $p, q$ all have the bits of $M''_N$.

It is known that with around 57% of the bits of $p, q$ known, we can factorize $N$ using the following algorithm -

• At stage $k$, calculate all possible $(p \pmod{2^k}, q \pmod{2^k})$ such that $pq \equiv N \pmod{2^k}$.
• Of course, we must respect the known bits of $p, q$ while calculating this.
• We can change $p \pmod{2^k}$ to $p \pmod{2^{k+1}}$ or $p + 2^k \pmod{2^{k+1}}$ while moving to the next stage.
• If we find a set of $(p, q)$ such that $pq = N$, the algorithm terminates.
• This can be written in a depth-first search style or a breadth-first search style. The latter works better on my machine.

We require that $M''_N$ has a lot of ones in its binary representation. We simply restart the connection until we get good parameters.

For the details of the factorization algorithm, please refer to the solution script below.

how did we encrypt this?

Now we know the factorization of $M$. We can now check if $ctxt^2 - 4$ is a quadratic residue modulo $M$.

We test this for the ciphertext of the "the boy who lived" and the ciphertext of the flag. If this check fails, we run our algorithm again with a new connection for a good set of parameters. We now assume $ctxt^2 - 4$ is a quadratic residue.

We reasonably guess that our encryption algorithm will have used 16 primes out of the 35 consecutive primes larger than 31337.

We also verify that $p-1$ and $q-1$ are all coprime to these 35 candidate primes. If not, we look for a good set of parameters.

Now we can encrypt and decrypt as we like. Let's find out which 16 primes were used for encryption.

To do this, we use meet-in-the-middle algorithm. Basically what we do is

• Split the set of 35 primes into two pieces, and assume that 8 primes were used in each piece
• Calculate the encryption of "the boy who lived" with each combination of 8 primes of the first piece
• Calculate the decryption of the ciphertext with each combination of 8 primes of the second piece
• Find a match, and if there is one, we have found our set of 16 primes.
• If not, we can try a new split of the primes and continue on.

Now we know which primes were used for encryption. All we need to do is decrypt the ciphertext of the flag.

Note 1 : speeding up cast_riddikulus algorithm

• This is a linear recurrence, so we can speedup using matrix multiplication
• However, this is also a Lucas sequence used in Williams's $p+1$ algorithm
• Therefore, we can just copy the implementation from Wikipedia to achieve a speedup.

Note 2 : requirements relaxation

• If we assume that the flag is small, we only need to work with mod $p$ or mod $q$, instead of mod $M$.
• Therefore, we can relax our quadratic residue conditions to "QR modulo at least one of the primes"
• Thankfully, I was very lucky with the parameters and got QR modulo $M$.

Note 3 : meet-in-the-middle, but not quite middle

• If we try to run the code, we can see that encryption is faster than decryption.
• Therefore, it's reasonable to give the encryption part more work than just "half" of the bunch.

The solution code is displayed in parts for reader's understanding. Feel free to comment and ask questions...

 1 2 3 4 5 6 7 8 9 10 11 12 13 def recvint():     T = r.recvline()     return int(T[:-1].decode(), 10)     def get_vals():     r.recvline()     C = recvint()     N = recvint()     H = bytes_to_long(b'the boy who lived')     H_AFTER = recvint()     F_AFTER = recvint()     return C, N, H_AFTER, F_AFTER cs

factorization of $M$

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 def bsum(x):     ret = 0     while x > 0:         ret += x % 2         x //= 2     return ret    def factor(N, C, cand, k):     if len(cand) == 0:         return     print(k, len(cand))     # fix pq mod 2^{k+1} by adding 2^k or not     ret = []     if (C >> k) % 2 == 1: # we know p, q has 2^k         for p, q in cand:             if p * q == N:                 print(p)                 print(q)                 return             pp = p + (1 << k)             qq = q + (1 << k)             if (pp * qq - N) % (1 << (k + 1)) == 0 and pp * qq <= N:                 ret.append((pp, qq))         factor(N, C, ret, k + 1)     else:         for p, q in cand:             if p * q == N:                 print(p)                 print(q)                 return             for i in range(0, 2):                 for j in range(0, 2):                     pp = p + i * (1 << k)                     qq = q + j * (1 << k)                     if (pp * qq - N) % (1 << (k + 1)) == 0 and pp * qq <= N:                         ret.append((pp, qq))         factor(N, C, ret, k + 1)   # M_N to M''_N C -=  C % (1 << 16) C &= (C + (1 << 16)) # check number of 1s, if bsum(C) is small (<256), stop and rerun print(C.bit_length(), bsum(C))  # factorize factor(N, C, [(1, 1)], 1) Colored by Color Scripter cs

encryption and decryption

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def mlucas(v, a, n): # encryption fast, from Wikipedia     v1, v2 = v, (v**2 - 2) % n     for bit in bin(a)[3:]:         if bit == "0":             v1, v2 = ((v1**2 - 2) % n, (v1*v2 - v) % n)         else:             v1, v2 = ((v1*v2 - v) % n, (v2**2 - 2) % n)     return v1   def REV(val, ex, pr): # decryption modulo a prime     # t^n + 1/t^n = val     if val == 0: # if invalid         return 0 # return invalid     cc = tonelli((val * val - 4) % pr, pr) # modular sqrt     if cc == -1: # failure         return 0 # return failure     tn = ((val + cc) * inverse(2, pr)) % pr     t = pow(tn, inverse(ex, pr-1), pr)     return ((t + inverse(t, pr))) % pr cs

meet-in-the-middle

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 primes = [31337, 31357, 31379, 31387, 31391, 31393, 31397, 31469, 31477, 31481, 31489, 31511, 31513, 31517, 31531, 31541, 31543, 31547, 31567, 31573, 31583, 31601, 31607, 31627, 31643, 31649, 31657, 31663, 31667, 31687, 31699, 31721, 31723, 31727, 31729, 31741, 31751, 31769, 31771, 31793]   L = primes[15:35] R = primes[:15]   LV = [] RV = []   # generally, encryption is faster than decryption # therefore, we leave the "heavy" work for the encryption part...   for combo_L in tqdm(itertools.combinations(L, 8)):     CC = list(combo_L)     cur = H     # you can also just multiply all primes and encrypt at once     for pr in combo_L:         cur = mlucas(cur, pr, p)     CC.append(cur)     LV.append(CC)   print("LEFT DONE")   for combo_R in tqdm(itertools.combinations(R, 8)):     CC = list(combo_R)     cur = HAFTER     # you can also just multiply all primes and decrypt at once     for pr in combo_R:         cur = REV(cur, pr, p)     CC.append(cur)     RV.append(CC)   print("RIGHT DONE")   for i in tqdm(range(len(LV))):     for j in range(len(RV)):         if LV[i][8] == RV[j][8]:             print("FOUND!!")             print(LV[i])             print(RV[j]) Colored by Color Scripter cs

the finish, and the parameters I got

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 H = bytes_to_long(b'the boy who lived') sys.setrecursionlimit(10 ** 6)   C = 12124756848659098434025945489515506912896022954145117746118560512007665385702760439414990812257455576297349156226093149988609289245714223348281989890389750 N = 157597985389833012337654133040126048344064622845161536236706459270343905778002470548499258715513540516431526518690532156245280894778788692043941237295606686168037171464988128988463706375526180496632421973522548093894845498612792150825707672843107252573999144787226703076358545319417530365329436368718460943493 HAFTER = 66161881147822169408519540711422900962287264738494143175834051626001922954586728648835878096124744364195826536091510407493007528877139856387261499433277826944946254511824024047480941829026088269865298686453128715170657018128276813244425143986311708022950785583195028647859774987948632731985531259912781472862 FAFTER = 149186530719822614329126547638374064715014252925601014676661223009475822460330945440469384214084001910035138025738722725987466200681944900264994344927428683388976167111544750466576538413516454786176229441173029050647235653998791477157269246962955063391947778663841551982999293815571149539542758304215156142104   C -=  C % (1 << 16) C &= (C + (1 << 16))   # factor(N, C, [(1, 1)], 1)   p = 12558711464274427739528720572494472142909592647353129013838950445222814801805965383430302364628487022743397586481672449715551542652546057434522020868473011 q = 12548897698474048380978452887676419841595083766206501465313606366388795637681128899285066184154566275021196792336453455837893284460576050862858626214885863   # recovered set of primes pr = [31543, 31567, 31573, 31607, 31649, 31667, 31687, 31699, 31357, 31379, 31397, 31469, 31477, 31513, 31517, 31531] hp = FAFTER % p  hq = FAFTER % q    # reverse for i in pr:     hp = REV(hp, i, p)     hq = REV(hq, i, q)   flag, tt = CRT(hp, p, hq, q) # CRT print(long_to_bytes(flag)) Colored by Color Scripter cs

#### 'CTF' 카테고리의 다른 글

LINE CTF Crypto Writeups  (0) 2021.03.22 2021.03.07 2021.02.21 2021.01.31 2021.01.31