TSG CTF 2020 Sweet like Apple Pie Writeup

$c=\sin (m)$ is given. We can immediately calculate

$mmod\pi$ from

$c$ by using an appropriate series expansion of

$\arcsin$. Note that there are two corresponding values.

Now let

$x=mmod\pi$ and the calculation error be

$\delta x$. We want to calculate

$$n\pi +m=x+\delta x$$

Now if we calculate

$|\pi -\frac{x-m}{n}|$,

$$\begin{array}{rl}|\pi -\frac{x-m}{n}|& =|\frac{x+\delta x-m}{n}-\frac{x-m}{n}|\\ & =\left|\frac{\delta x}{n}\right|\end{array}$$

From the condition given in the challenge script,

$\left|n\right|<2^{500}/\pi$. And if we experiment with the script we can tell that the precision of the function

$\sin (x)$ in the script is about 150 digit in decimal, so we can evaluate

$\left|\delta x\right|<2^{-500}$. So:

$$\begin{array}{rl}|\pi -\frac{x-m}{n}|& =\left|\frac{\delta x}{n}\right|\\ & =\left|\frac{\delta x\cdot n}{n^2}\right|\\ & <\frac{1}{\pi n^2}\\ & <\frac{1}{2n^2}\end{array}$$

So, from Legendre's theorem in Diophantine approximations:

If

$|\alpha -\frac{p}{q}|<\frac{1}{2q^2}$,

$\frac{p}{q}$ will be a principal approximation of

$\alpha$. [Ref]

$\frac{x-m}{n}$ will be a principal approximation of

$\pi$. That is, if we take some

$\frac{p}{q}$ which is a principal approximation of

$\pi$, we can observe

$$\begin{array}{rl}\frac{x-m}{n}& =\frac{p}{q}\\ qx& =pn+qm\end{array}$$

Now let

$N:=qx$, and from

$$|N-q(x+\delta x)|=|q\cdot \delta x|<\frac{1}{2}$$

we can calculate that

$\mathrm{round}\left(q(x+\delta x)\right)=N$.

Nwo what we should do is to solve

$n,m$ such that

$N=pn+qm$, and this is achieved by

$$m=N{q}^{-1}modp$$

Then you can try the above computation for all the principal approximation of

$\pi$, and the solution is one that satisfies

$c=\sin (m),m<2^{500}$.