# TSG CTF 2020 Sweet like Apple Pie Writeup

$c = \sin(m)$ is given. We can immediately calculate $m \bmod \pi$ from $c$ by using an appropriate series expansion of $\arcsin$. Note that there are two corresponding values.

Now let $x = m \bmod \pi$ and the calculation error be $\delta x$. We want to calculate

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

Now if we calculate $\left|\pi-\frac{x-m}{n}\right|$,

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

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{aligned}
\left|\pi-\frac{x-m}{n}\right|&=\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{aligned}
$$

So, from Legendre's theorem in Diophantine approximations:

> If $\left|\alpha−\frac{p}{q}\right|<\frac{1}{2q^2}$, $\frac{p}{q}$ will be a principal approximation of $\alpha$. [[Ref]](https://cryptee.blogspot.com/2018/10/rsawieners-attack.html)

$\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{aligned}
\frac{x-m}{n}&=\frac{p}{q}\\qx&=pn+qm
\end{aligned}
$$

Now let $N:=qx$, and from

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

we can calculate that $\operatorname{round}\left(q\left(x+\delta x\right)\right)=N$.

Nwo what we should do is to solve $n,m$ such that $N=pn+qm$, and this is achieved by

$$m=Nq^{-1}\bmod p$$

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}$.