Tags: rsa
Rating:
As this challenge name implies, the problem comes from reversing the typical
challenge of RSA. This time, rather than starting with a modulus and trying to
discover the private exponent, we are given the private exponent, and trying to
find the modulus.
As a reminder, once we find $N$, we can simply evaluate $c^d \mod N$ to
determine the final message.
First, we know that the relationship between $e$ and $d$ is that $ed \equiv 1
\mod \phi(N)$. Translating this to plain algebra, this means $ed - 1 = k\phi(N)$
for some positive integer $k$. This tells us that $ed - 1$ must divide
$\phi(N)$.
We use an [external factoring service] to factor $ed - 1$. Using the
`gen_prime` method given to us, we are able to validate that our factorization
ended up being what was expected: exactly 16 64-bit primes, and a handful of
smaller primes. The only thing left is organizing the 16 primes into two groups
of 8.
[external factoring service]: https://www.alpertron.com.ar/ECM.HTM
Trusty old combinatorics tells us ${16 \choose 8} = 12870$, which is easily
iterable within a matter of seconds. After picking 8 primes, we simply run
through the same process as `gen_prime` in order to generate our $p$ and $q$:
```python
for perm in tqdm(perms):
perm = set(list(perm))
p = prod(perm)
q = prod(bigprimes - perm)
for i in range(7):
if isPrime(p + 1): break
p *= small_primes[i]
for i in range(7):
if isPrime(q + 1): break
q *= small_primes[i]
p = p + 1
q = q + 1
```
All that's left is to run $c^d \mod N$ and find strings that begin with
`uiuctf{` to determine which of these organizations of prime factors is the
correct one.
[solve script](https://git.sr.ht/~mzhang/uiuctf-2022/tree/master/item/crypto/asr/solve2.py)
