# floorsa - BSides AHM 2021
###### tags: `BSides AHM 2021`

## Challenge Overview
The flag is encrypted with a simple RSA:
Given two primes $p, q$ and plaintext $m$, the cipher is $c = m^{65537} \mod pq$.

Along with the public key and ciphertext, we're also given the following value $s$:

$$s = \sum_{i=1}^{q-1}\left\lfloor \cfrac{ip}{q} \right\rfloor$$

## Analysis
First, expand the sum

$$\begin{eqnarray}
s &=& \sum_{i=1}^{q-1}\left\lfloor \cfrac{ip}{q} \right\rfloor\\
&=& \left\lfloor \cfrac{p}{q} \right\rfloor + \left\lfloor \cfrac{2p}{q} \right\rfloor + \left\lfloor \cfrac{3p}{q} \right\rfloor + \cdots + \left\lfloor \cfrac{(q-1)p}{q} \right\rfloor
\end{eqnarray}$$

Let's calculate $s+s$ and group up the 1st and (q-1)-th terms, 2nd and (q-2)-th terms, and so on:

$$\begin{eqnarray}
2s &=& \left(\left\lfloor \cfrac{p}{q} \right\rfloor + \left\lfloor \cfrac{(q-1)p}{q} \right\rfloor \right) + \left(\left\lfloor \cfrac{2p}{q} \right\rfloor + \left\lfloor \cfrac{(q-2)p}{q} \right\rfloor \right) + \cdots \\
&=& \left(p + \left\lfloor \cfrac{p}{q} \right\rfloor + \left\lfloor \cfrac{-p}{q} \right\rfloor \right) + \left(p + \left\lfloor \cfrac{2p}{q} \right\rfloor + \left\lfloor \cfrac{-2p}{q} \right\rfloor \right) + \cdots
\end{eqnarray}$$

For all $i\in\{1,2,\cdots,q-1\}$, $\lfloor ip/q\rfloor + \lfloor -ip/q\rfloor = -1$ because $\gcd(p, i)=1$.
Therefore,

$$\begin{eqnarray}
2s &=& (p-1) + (p-1) + \cdots\\
&=& (p-1)(q-1)\\
&=& \phi(n)
\end{eqnarray}$$

Now you can find the private key $d$ by calculating

$$d = e^{-1} \mod \phi(n) = e^{-1} \mod 2s$$

## Script

from Crypto.Util.number import inverse

exec(open("../distfiles/output.txt").read())
d = inverse(65537, 2*s)

m = pow(c, d, n)
print(int.to_bytes(m, 2048//8, 'big'))