# 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 ```python= 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')) ```