FCSC 2026 - Crypto Write-Ups
Hi 👋 ! In this post, I’ll present my write-ups for all the challenges listed in the crypto category that I’ve solved, ordered by difficulty rating.
Those challenges are :
This is fine
| Points | Difficulty | Solves |
|---|---|---|
| 151 | ★ | 194 |
Description
Code
The following source code was provided :
| |
The first notable observation is an array \(L\) containing \(38\) polynomials of degree \(16\) which is used to calculate the bytes of the flag.
Solving
Analyzing this file in more details, it appears that we need to find, for each polynomial \(y\) in \(L\), two numbers this and fine such that
| |
What is interesting is that the first check adds a constraint that forces the numbers to be equal (i.e., this = fine). So the question now becomes: what must this number be ?
After experimenting with the second assert test, I found out that it passes only when y(this) and y(fine) refer to the same object in memory. How can this occur ?
Spoiler
y(fine) is a small enough number, specifically when y(fine) \(\in [-5, 256]\)After some research, I came across this comment on this answer, which I found while reading the Stack Overflow question on the subject. The question provides a clear explanation. Further investigation led me to the Python C API documentation, which confirms that the result of y(this) must be a number between \(-5\) and \(256\) for the test to pass.
This implies that for each polynomial \(y\) in \(L\), we need to find an input value \(x\) such that \(y(x) \in [-5, 256]\). Since \(y(x)\) is used directly as a byte of the flag, it must be in the range \([32, 127]\) to be a valid printable ASCII character. Given the small size of this range and the assumption that there is only one solution, we can find \(x\) for each polynomial by brute-forcing all possible outputs \(c \in [32, 127]\) and solving \(y(x) - c = 0\). If a solution is found, it means we have the correct guess for \(c\). By repeating this process for all polynomials in \(L\), we can recover the flag.
Here is the final Sage script to solve this challenge :
| |
FCSC{dqcb7dVhWa9hunProTfJMsurwboPkT3V}
Code breaker
| Points | Difficulty | Solves |
|---|---|---|
| 291 | ★ | 94 |
Description
Code
The source code was provided :
| |
Along with its output.txt file
The program encrypts the flag using AES-128 in CBC mode. The goal is to recover the key, which is constructed as follows:
key = sum(b << i for i, b in enumerate(key)).to_bytes(32)Given that key was already constructed here:
| |
In output.txt, we are provided with the contents of \(d\), which include the values of \(C\), the ciphertext, and the IV used. Therefore, we must start from \(d\) to recover the values of \(b\), giving us the key and thus the flag.
Note that, because of the function
| |
the matrix \(C\) is only a random permutation of the matrix \(G\).
Solving
After a quick look at the script, I spotted the two important lines that will guide our entire solution.
| |
From this, we see that \(b\) takes the bits of the value of the key, which is what we’re looking for to decrypt the flag. Depending on its value (\(0\) or \(1\)), we generate a different matrix. The goal of this challenge is then to find a way to differentiate between these two cases to recover the correct value of \(b\) for this output.
By taking a closer look at these functions, we can see that the functions random_matrix and random_permutation_matrix, as their names suggest, only generate a random matrix and a permutation matrix, respectively. Meanwhile, the function random_grs generates a random special matrix with a particular form.
To be more formal, we can find through some research that it is a Generalized Reed-Solomon (GRS) code matrix representation.
To determine the value of the bit, we need to distinguish a Generalized Reed-Solomon (GRS) code from a random matrix. The Schur product (or hadamard product) is such a distinguisher for codes with algebraic structure.
More precisely, as stated in Distinguishing and Recovering Generalized Linearized Reed–Solomon Codes (2023, Section 4.1)
The main observation for distinguishing a random linear code in \(\mathbb{F}_{q^m}^n\) from a GRS code \(\mathcal{C}\) is that the squared GRS code has dimension dim(\(\mathcal{C} \star \mathcal{C}\)) = min(\(n, 2k − 1\)), which is small compared to the expected dimension of a squared random linear code
Multiplying \(G\) by \(S\) and \(P\) does not change this property because it only applies a permutation to the matrix, which does not alter its algebraic structure.
Time
It takes about 1 or 2 minutes for the script to finish on my machine, mainly because the output.txt file is quite large, I suppose.
Here is the final Python solve script
| |
FCSC{949f94d858ef6ad1333164d796a0d777fd82f9155ece7d6fad68c0b992f0e7af}
Little d - Big trouble
| Points | Difficulty | Solves |
|---|---|---|
| 410 | ★ ★ | 37 |
Description
Le standard FIPS 186-5 impose dans la génération d’une clef RSA que l’exposant privé \(d\) soit plus grand que \(2^{(size//2)}\). Le standard précise d’ailleurs que dans le cas extrêment rare où \(d\) serait plus petit, il faut générer de nouveaux nombres premiers \(p\) et \(q\).
Testez votre chance en soumettant un de ces cas extrêment rares.
nc challenges.fcsc.fr 2155
Code
The service’s source code was provided :
| |
First, before solving, I must admit in plain sight that I spend (and lost 😿) way too much time thinking there was a flaw in the way the checks ware made in the correctness function, but there isn’t, because it’s not the goal of this challenge.
I probably should have read the description more carefully this time. That being said, let’s solve this challenge!
Solving
Our goal is to find prime numbers \(p\) and \(q\) such that the corresponding private key \(d\) is “small”. If you know a bit about RSA, you should know that this happens when the chosen \(e\) is very large (about the same order as \(N\)), which is how challenges that aim to introduce Wiener’s attack are created.
The main difficulty here is that, as we can see in the first lines of the check function, \(e\) can’t be too big, so we can’t use the easy way.
| |
Let’s get back to the basics.
We want \(d\) to be small, and we know that \(d\) is calculated as
\[ d = e^{-1} \mod \phi(n) \]with \(\phi(n) = (p - 1)(q - 1)\).
It means that in most cases, \(d\) is of the order of \((p - 1)(q - 1) \approx n = p \cdot q\), but because of the challenge, we need to loosely verify \(p, \ q \ge 2^{512} \ \Longleftrightarrow \ n \ge 2^{1024} \) and \(d \lesssim p\). So this is not going to cut it with what we’ve said before.
At this point, I was stuck. I was until, while reading for the \(100\)-th time the RSA Wikipedia page, I finally realized that the following information, which I already knew, would be relevant this time. The private key can also be computed as
\[ d = e^{-1} \mod lcm(p - 1, q - 1) \]with \(lcm(p-1, q-1)\) calculating the least common multiple of \(p-1\) and \(q-1\). What it means is that if \(p-1\) and \(q-1\) share common big factor, then their \(lcm\) will be not much larger than them.
To generate such numbers, we will try to build prime numbers of the form
\[ \begin{aligned} p &= 2 g a + 1 \\ q &= 2 g b + 1 \\ \end{aligned} \]with \(g\) a big common number and \(a, \ b\) two small numbers. If we find such primes, we know that \(lcm(p - 1, q - 1) = 2 g a b\), which is small enough to brute-force a number \(e\) that satisfies the conditions and allows us to calculate \(d\) such that it also satisfies the conditions.
Here is the final Python solve script that implements those steps :
Note
The value of \(N\) in this script is arbitrary. It is a good value because the script finds primes fast enough and because the primes it generates satisfy the required conditions to proceed.
The script runs forever ?!
Because there aren’t many 10-bit primes, about half of the time the script gets stuck in the first infinite loop. Just re-run it a few times until it gets out fast. In the right conditions, this step should be instantaneous.
| |
FCSC{bef584620e83319d1e64cdcb57346b1fa3cd1a1b6875aa6591958a3dd7e6cd6f}
Fully Homomorphic RSA
| Points | Difficulty | Solves |
|---|---|---|
| 415 | ★ ★ | 35 |
Description
Il est bien connu que la primitive plain RSA est multiplicativement homomorphe : le chiffré du produit de deux clairs est égal au produit des deux chiffrés. À l’issue d’un travail de plusieurs années, nos chercheurs sont parvenus à un résultat révolutionnaire : ils ont trouvé comment calculer le chiffré de la somme de deux clairs uniquement à partir des chiffrés initiaux et de la clé publique. Cela rend le système RSA complètement homomorphe !
Les détails de leur résultat sont encore confidentiels. Cependant, nous sommes heureux de fournir à la communauté un émulateur de ce “Fully Homomorphic RSA” afin qu’elle puisse dès maintenant en explorer toutes les possibilités.
nc challenges.fcsc.fr 2150
Code
The service’s source code was provided :
| |
First things first, we are dealing with an RSA cryptosystem, and the goal is to recover the encrypted flag that is given to us when we connect to the service using its two other functionalities.
Solving
Let’s note our encrypted flag \(c_f\), such that
\[ c_f = m_f^e \mod n \]After a more thorough analysis, we can determine that the functions hom_sum let us calculate :
while the function hom_prod let us calculate :
From there, we know that we can calculate, with the help of the service, any linear combination of the encrypted flag. How is this helpful ?
Well, having faced RSA cryptanalysis quite a few times, I remembered it was something familiar. But even if you didn’t know, with a quick search as I did about common RSA attacks, you might stumble upon the Franklin-Reiter related-message.
And as it turns out, it is exactly what we need !
The key point here, as mentioned in my notes, is that \(b \neq 0\), which is what the function hom_sum will be useful for. So here is the plan :
- Choose two numbers \(A\), \(B < n\)
- Connect to the service, retrieve \(c_f\), \(e\) and \(N\).
- Using the public key \((n, e)\), compute
- Calculate \(c_b = B^e \mod n\)
- Then, send \((c_{f1}, c_b)\) to the service and use
hom_sumto compute
with \(m_{f2} = f(m_f) = Am_f + B\)
- Now, we’re in the exact case described by the attack, that we can then use to recover \(m_f\) using the two following encrypted messages
Important
In fact, the hom_prod function is useless here because, as stated in the challenge’s description, RSA is multiplicatively homomorphic by definition. This means we can perform this operation on our own since we know the public key used to encrypt the flag (provided by the service).
Compute Time
It takes this script about 15 to 30 minutes to recover the encrypted flag because \(e = 65537\) is not quite small.
Given this last piece of knowledge, here is the final Sage solve script :
| |
FCSC{4d7b3ef7300acf70c892d8327db8272f54434adbc61a4e130a563cb59a0d0f47}
Not Solved
In this section, there will be post-CTF write-ups about challenges I attempted but didn’t solve during the competition. For each, I am now writing a detailed solution, given the time to think more and the hints, solutions, and ideas from people who solved them and didn’t make a write-up but talked about it on Discord.
This means what you’ll read here is ultimately a combination of both my personnal progress during the CTF (and after) and the solutions given on the Discord channel.
I will mention under each following write-up the people or solutions that helped me understand better and wrote what you’ll read. Thanks to them ✨.
Those challenges are :
I love permutations
Important
The solution exposed here and the explanations are based on this writeup, from @Maxime, posted on the Discord server of the event.
| Points | Difficulty | Solves |
|---|---|---|
| 372 | ★ ★ | 54 |
Description
Moi, j’aime les permutations. Alors j’ai décidé de créer mon propre chiffrement par bloc.
nc challenges.fcsc.fr 2153
Code
The service’s source code was provided :
| |
When connecting to the service, we’re given th encrypted flag and the ability to perform 6 encryptions using the same key for chosen ciphertexts of our own.
| |
Solving
Let’s define:
- \(P_0\): the permutation generated by the seed \(0\)
- \(P_k\): a random unknown permutation generated from the key
- \(R = 101\): the number of rounds for the encryption process
- \(M = (l, r)\): our message, with \(l\) and \(r\) respectively the left and right branch
- \(E(x)\): our encryption function
- \(E_f\): our encrypted flag
- \(n=64\): the size of the permutations
The key point here is to observe that for a carefully crafted message \(M_c = (l, 0)\), with the right branch filled with \(0\), we have:
\[ E(M_c) = (l \cdot (P_k P_0)^R, 0) \]with \(\sigma = (P_k P_0)^R\) an unknown permutation, and \(P_k\) the key-based permutation we’re looking for.
Remark
These permutations apply to the bit representation and ordering of the numbers we are working with.
From there, if we can recover the permutation \(\sigma\) on its own, we can then take the \(R\)-th root to find \(P_k P_0\), and since we know \(P_0\), we finally have \(P_k\), which allows us to revert the encryption of the flag.
This is where I was stuck during the CTF. I knew that by constructing the \(l\) part of the message in a special way, I would be able to recover \(\sigma\), but I didn’t know how.
The trick is to create 6 messages \(M_i = (l_i, 0)\) with \(i \in [0, 5]\) and
\[ l_i = \sum_{j=0}^{64} \left(\left\lfloor \frac{j}{2^i} \right\rfloor \mod 2\right) \cdot 2^j \]Meaning
This formula is just a fancy mathematical way to say that we set the value of the \(j\)-th bit of \(l_i\) to the value of the \(i\)-th bit of \(j\).
Because of this formulation, we know that if
\[ \begin{aligned} E_i &= l_i \cdot (P_k P_0)^R \\ &= l_i \cdot \sigma \\ \end{aligned} \]then we have
\[ \begin{equation} \sigma = \left\{ \sum^{5}_{i=0} \left[\left(\left\lfloor \frac{E_i}{2^j} \right\rfloor \mod 2\right) \cdot 2^i \right] \mid j \in \{0, 1, \cdots, 64\} \right\} \tag{3} \end{equation} \]Proof
Here is the proof for (3) :
To be continued …
We can now take the \(R\)-th root of this permutation, and because \(R = 101\) is prime, we have a unique solution. I didn’t find many resources on how to do that, so you can read those Stack Exchange Math discussions (1, 2 and 3) or read the Sage’s source code of the function I will use.
Now that we have \(\beta = P_k P_0\) such that \(\beta^R = \sigma\), we can calculate
\[ P_k = \beta \cdot P_0^{-1} \]since we know the permutation \(P_0\).
Finally, we can recover our unencrypted flag \(M_f\) by running the encryption algorithm backward, as we now know \(P_k\), meaning we can undo it.
Tip
For future reference, I’m using Sage’s built-in permutation objects to find the \(101\)-th root of the full \(101\) rounds permutation.
Here is the final solve script using Sage :
| |
FCSC{af56d1a25c88e9ebe515958e32}
Shor
Important
I didn’t solve this challenge during the CTF, but managed to do so now after a simple message from @nikost on the Discord server of the event, which revealed the solution to me.
| Points | Difficulty | Solves |
|---|---|---|
| 437 | ★ ★ | 26 |
Description
Après des années de rêve, c’est enfin arrivé : on a mis la main sur un ordinateur quantique de compétition. Entre deux essais pour plier l’espace-temps (et miner du Bitcoin quantique), on s’est dit que casser du RSA serait plus rigolo.
nc challenges.fcsc.fr 2154
Code
The service’s source code was provided :
| |
As the name of the challenge suggests, it is going to be about Shor’s algorithm for factorization.
From the source code, we know that \(a = 3\), which is the base in Shor’s algorithm, and that \(e = 2^{16} + 1 = 65537\). If we connect to the server, we are given the public modulus \(N\) and the number \(c\), which is the result of the Quantum Fourier Transform. This is the last step of the quantum order-finding subroutine in Shor’s algorithm for \(N\) to the base \(a\).
The goal, given \(N\), \(c\), and \(a\), is to find one of the factors of \(N = pq\).
Solving
Let’s query the service one time to get example values :
| |
What is this number \(c\) ? If we read the Wikipedia page, as it is the result of the quantum order-finding subroutine, it should be the order \(r\), such that
\[ \begin{equation} a^r \equiv 1 \mod N \tag{1} \end{equation} \]But if you try these values, you’ll see that this is not the case, so \(c\) can’t be the order. So what is it ?
Reading the page again, we can find the answer in this section and the paragraph just above it. That is,
\[ c = 2^{2n} \frac{j}{r} \]for random \(j = 0, 1, \dots, r-1\).
But we also read that we can use continued fractions to extract the period \(r\) (what we’re looking for) from the decimal approximation of
\[ \frac{j}{r} = \frac{c}{2^{2n}} \]Since we know from the source code that \(N\) is generated from the product of two 1024-bits prime numbers, we can assume that the algorithm was implemented as stated and thus that \(n = 1024\).
Okay, now let’s do this using Sage
| |
We successfully find the order \(r\) such that \(a^r \equiv 1 \mod N\) ! We can now do the last part of shor’s algorithm to recover the factors of \(N\).
| |
and it doesn’t work …
This is where I got stuck until the end of the CTF 😭
After the CTF ended, I was looking through the crypto channel on Discord to find some insights and saw this message (in French):
And indeed, you really do have \(\phi(N) = \left\lfloor \frac{N}{r} \right\rfloor \cdot r\), because if you now try to recover the factors using this method, you successfully get back \(p\) and \(q\).
| |
which finally solves our challenge …
But hey, let’s be honest, I don’t have any idea why \(\phi(N) = \left\lfloor \frac{N}{r} \right\rfloor \cdot r\) is correct. So is there another way ? YES
Addendum - Explanations
As told to me just after the release of this post by none other than @nikost himself (again), here is the explanation of why it works.
We have
\[ \begin{aligned} \phi(N) &= (p - 1)(q - 1) \\ &= pq - p - q + 1 \\ &= N - p - q + 1 \end{aligned} \]So
\[ \frac{N}{r} = \frac{\phi(N)}{r} + \frac{p + q - 1}{r} \]Now, because of something we will discuss below, \(\phi(N)\) is a multiple of \(r\), thus we have \(k \cdot \phi(N) = r\) and
\[ k = \frac{\phi(N)}{r} \]is an integer.
Moreover, because with very high probability for a randomly chosen base \(a\), we have \(r \gg p + q - 1\), it means that
\[ 0 < \frac{p + q - 1}{r} < 1 \]In the end, it all comes down to
\[ \begin{aligned} \left\lfloor \frac{N}{r} \right\rfloor \cdot r &= \left\lfloor \frac{\phi(N)}{r} + \frac{p + q - 1}{r} \right\rfloor \cdot r \\ &= \left\lfloor \frac{\phi(N)}{r} \right\rfloor \cdot r \\ &= \frac{\phi(N)}{r} \cdot r \\ &= \phi(N) \end{aligned} \]For this specific example, we can actually find that \(\phi(N) = 2r\), which means that in many cases, \(\phi(N)\) must be a multiple of \(r\). But why ?
One part of the answer lies in the Euler’s theorem, which states that if \(a\) and \(N\) are coprime, then
\[ \begin{equation} a^{k \cdot \phi(N)} \equiv 1 \mod n \quad \forall k \in \mathbb{N}^* \tag{2} \end{equation} \]Now, because \(a\) should be coprime to \(N\) for shor’s algorithm, and following from equation (1), we should have, for \(k = 1\)
\[ \phi(N) = r \]If we take one last look at what is written on the Wikipedia page, we can read the last part of our answer under the previously mentioned section :
However, while \(b\) and \(c\) are coprime, it may be the case that \(j\) and \(r\) are not coprime. Because of that, \(b\) and \(c\) may have lost some factors that were in \(j\) and \(r\).
What does it mean ?
What this means is that we found our \(r\). However, due to the method we used (continued fractions), we lost a leading factor (\(2\) in our case) of the “true” value of \(r\).
We now have \(r = k \cdot r^{'}\) with \(r^{'}\) the actual order we found, which gives us
\[ \phi(N) = k \cdot r^{'} \]In the end, for a given \(r\) such that \(a^r \equiv 1 \mod n\), we must try to factor with multiples and factors of \(r\) if it doesn’t work with \(r\) directly.
So there it is. Now the strategy is to loop over many multiples until we find the correct one. It shouldn’t be too long, as this one is often small, and if it takes too much time, then retry from the beginning with new values.
One final point
In a normal case of shor’s algortihm implementation, because \(k \neq 1\), then we have from (2)
\[ k \cdot \phi(n) = r \]which means that \(r\) is a multiple of \(\phi(n)\).
To factor \(N\) from there, you should, as first discussed in this paper and as implemented in this attack, try to divide \(r\) by it’s divisors to find \(\phi(n)\)
Here is the final Sage solve script for this challenge :
| |
FCSC{e4d93d2d05e78587e736078953345d52f00f6b8ee16e7913f40fe53518452bbb}
End word
It was my first time parcticipating at FCSC CTF and I must stay I was suprised by the level of diffuclty of the challenges. I’m a bit frustated because I spent a lot time on some challenges which I didn’t solve in the end but discovered I was close to the solution after reading others. Guess I’ll have to train more and become better 😆.
Anyway, it was quite enjoyable and educational. Looking forward to next year to try my chance again to qualify for ECSC, as I’m still young enough to be a candidate for the two years to come !