# 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}$.
Solver can be found [here](https://github.com/tsg-ut/tsgctf2020/blob/master/crypto/sweet_like_apple_pie/solver/solve.py).