Potluck CTF  Upsidedown Cake
This is the solution of the challenge “Upsidedown Cake” from Potluck CTF. It was an modular equation solved after transformation by the Coppersmith method applied to bivariate polynomials.
Details
Category: cryptography
Author: Neobeo
Points: 258
Description
Let’s bake a cake – an upsidedown cake full of secrets! Ready to flip the script?
Solution
The python script is simple, the flag is 44 byte long and has the form potluck{???????????????????????????????????}
. It is split into two halves. Each half is inverted modulo $p$ and added together. We got the result in the comment:


The only confusing part is the computation of $p$:


But if we break it into pieces we have:


Finally using the bitwise not operator ~
on $(2^{521})$ flips all the bits and gives $p = 2^{521}1$


Then we have the equation:
$$x^{1} + y^{1} = a \mod p$$
With $a$ being the value given in the comment. The first thing to notice is that the values $x,y$ are 176 bit long which is very small compared to $p$. This kind of equation can be solved for small roots by a variation of the Coppersmith method applied to bivariate polynomials. However we do not have yet a bivariate polynomials. If we multiply both side by $xy$ we got:
$$y + x = xya \mod p$$
Now we can applied such method but the solution $(0,0)$ is now a valid solution and very small as well. To overcome that, we can integrate in our polynomial the fact that $x$ start with the value potluck{
. We can compute $x_0$ being the known upper bits of $x$:


Now, our polynomial is: $$(x+x_0) + y = (x+x_0)ya$$ With $x$ being only 112 bits long. Coppersmith method for bivariate polynomials is not implemented in Sage but I used an implementation by William Wang. The method gave two solutions:


Hopefully the second one gave the flag:

