Tags: crypto rsa
Rating: 5.0
# More than RSA
## Problem statement
We are given the following RSA parameters:
```py
n = 1100850264887168314211762819883795365780121968205537296902223426731243068938524059257925143313777052757053856786982874173716276177998575844405107994774163623594567853401672642143800707599048708305224295632993779740746149997736938447
e = 65537
```
and the following ciphertext:
```py
ciphertext = 480094491344184716025867044738553123253487474486589471961845430330096785266173544331123030859187762374111000621126862865088179081207677858976347099293571569918719633123584814249747143430742130678496191240615060301658387433503985739
```
We are (implicitly) asked to find the plaintext.
## Solution
Consider the description:
> British scientists have found RSA-512 to be lacking. We have made it 1.5 times better. Can you break it now?
The phrase "1.5 times better" leads us to suspect that either the modulus was manipulated
in some unsavory fashion, or perhaps we have 3 primes instead of 2.
In any case, to start with, let's see if we can easily factor the modulus:
```py
>>> import sympy
>>> sympy.factorint(n)
```
This takes long enough that we give up. OK, let's throw RsaCtfTool at it:
```sh
$ RsaCtfTool.py -n 1100850264887168314211762819883795365780121968205537296902223426731243068938524059257925143313777052757053856786982874173716276177998575844405107994774163623594567853401672642143800707599048708305224295632993779740746149997736938447 -e 65537
# ...
[*] Performing pollard_p_1 attack on /tmp/tmpp2645c_8.
ValueError: RSA factor q is composite
```
We're in luck!
Looks like we have more than two prime divisors of the modulus, and we have just found one in less than a minute.
By changing the RsaCtfTool source to just print `p` and `q` instead of trying to construct a private key, we get
```py
p = 54469
q = 20210583357270526615354840732963619045330774719666916905069368388096771905827609452310950142535700173622681833464592229960459640859912534550021259703210332915870822915817669539440795821458971310382498221612179032858068809740163
```
Now, `p` is prime, as we can easily check, so it remains to factor `q`.
We repeat the process, now setting `n = q`:
```py
$ RsaCtfTool.py -n 20210583357270526615354840732963619045330774719666916905069368388096771905827609452310950142535700173622681833464592229960459640859912534550021259703210332915870822915817669539440795821458971310382498221612179032858068809740163 -e 65537
```
This time, it looks like RsaCtfTool can't help us.
Let's try sympy again, hoping that we've shaved off enough bits:
```py
>>> sympy.factorint(q)
{142163931281005755026535550620537881622367024340878866899822911342984290337906414351811561305643313838918021183679: 1, 142163931281005755026535550620537881622367024340878866899822911342984290337906414351811561305643313842490901812797: 1}
```
Lucky again! So, in summary, we have:
```py
p1 = 54469
p2 = 142163931281005755026535550620537881622367024340878866899822911342984290337906414351811561305643313838918021183679
p3 = 142163931281005755026535550620537881622367024340878866899822911342984290337906414351811561305643313842490901812797
```
Now it's trivial to decrypt the ciphertext:
```py
>>> phi = (p1 - 1) * (p2 - 1) * (p3 - 1)
>>> d = gmpy2.invert(e, phi)
>>> flag = pow(ciphertext, d, n)
>>> print(binascii.unhexlify(hex(flag)[2:]))
b'ugra_3rsa_is_secure_unless_you_get_bad_primes_4d43902417d0d31d'
```
