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}\mathrm{mod}pq$.

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

$$s=\sum _{i=1}^{q-1}\lfloor \frac{ip}{q}\rfloor$$

Analysis

First, expand the sum

$$\begin{array}{rcl}s& =& \sum _{i=1}^{q-1}\lfloor \frac{ip}{q}\rfloor \\ & =& \lfloor \frac{p}{q}\rfloor +\lfloor \frac{2p}{q}\rfloor +\lfloor \frac{3p}{q}\rfloor +\cdots +\lfloor \frac{(q-1)p}{q}\rfloor \end{array}$$

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{array}{rcl}2s& =& (\lfloor \frac{p}{q}\rfloor +\lfloor \frac{(q-1)p}{q}\rfloor )+(\lfloor \frac{2p}{q}\rfloor +\lfloor \frac{(q-2)p}{q}\rfloor )+\cdots \\ & =& (p+\lfloor \frac{p}{q}\rfloor +\lfloor \frac{-p}{q}\rfloor )+(p+\lfloor \frac{2p}{q}\rfloor +\lfloor \frac{-2p}{q}\rfloor )+\cdots \end{array}$$

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{array}{rcl}2s& =& (p-1)+(p-1)+\cdots \\ & =& (p-1)(q-1)\\ & =& \varphi (n)\end{array}$$

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

$$d=e^{-1}\mathrm{mod}\varphi (n)=e^{-1}\mathrm{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'))