# Defective RSA

## Buckeye CTF 2021

`I use whatever exponent I want`

We are given the file (chall.py).

```python
from Crypto.Util.number import getPrime, inverse, bytes_to_long

e = 1440

p = getPrime(1024)
q = getPrime(1024)
n = p * q

flag = b"buckeye{???????????????????????????????}"
c = pow(bytes_to_long(flag), e, n)

print(f"e = {e}")
print(f"p = {p}")
print(f"q = {q}")
print(f"c = {c}")

# e = 1440
# p = 108625855303776649594296217762606721187040584561417095690198042179830062402629658962879350820293908057921799564638749647771368411506723288839177992685299661714871016652680397728777113391224594324895682408827010145323030026082761062500181476560183634668138131801648343275565223565977246710777427583719180083291
# q = 124798714298572197477112002336936373035171283115049515725599555617056486296944840825233421484520319540831045007911288562132502591989600480131168074514155585416785836380683166987568696042676261271645077182221098718286132972014887153999243085898461063988679608552066508889401992413931814407841256822078696283307
# c = 4293606144359418817736495518573956045055950439046955515371898146152322502185230451389572608386931924257325505819171116011649046442643872945953560994241654388422410626170474919026755694736722826526735721078136605822710062385234124626978157043892554030381907741335072033672799019807449664770833149118405216955508166023135740085638364296590030244412603570120626455502803633568769117033633691251863952272305904666711949672819104143350385792786745943339525077987002410804383449669449479498326161988207955152893663022347871373738691699497135077946326510254675142300512375907387958624047470418647049735737979399600182827754
```

This is a basic RSA but e and phi(N) are not coprime so there is no unique decryption of the ciphertext (Similar to the Rabin-crypto system). But since we are given `p` and `q`, we can compute the e-rooth of the messages (mod p and mod q) and then use the CRT to find the plaintext. We konw the plaintext starts with `buckeye{` so this will allow us to identify the flag.

```python
from Crypto.Util.number import long_to_bytes

e = 1440
p = 108625855303776649594296217762606721187040584561417095690198042179830062402629658962879350820293908057921799564638749647771368411506723288839177992685299661714871016652680397728777113391224594324895682408827010145323030026082761062500181476560183634668138131801648343275565223565977246710777427583719180083291
q = 124798714298572197477112002336936373035171283115049515725599555617056486296944840825233421484520319540831045007911288562132502591989600480131168074514155585416785836380683166987568696042676261271645077182221098718286132972014887153999243085898461063988679608552066508889401992413931814407841256822078696283307
c = 4293606144359418817736495518573956045055950439046955515371898146152322502185230451389572608386931924257325505819171116011649046442643872945953560994241654388422410626170474919026755694736722826526735721078136605822710062385234124626978157043892554030381907741335072033672799019807449664770833149118405216955508166023135740085638364296590030244412603570120626455502803633568769117033633691251863952272305904666711949672819104143350385792786745943339525077987002410804383449669449479498326161988207955152893663022347871373738691699497135077946326510254675142300512375907387958624047470418647049735737979399600182827754

rmodp = (c % p).nth_root(e, all=True)
rq = (c % q).nth_root(e)

for rp in rmodp:
r = crt(int(rp), int(rq), p, q)
flag = long_to_bytes(r)

if b"buckeye" in flag:
print(flag.decode())
```

**NOTE**: To be completely correct, we might have to test for all roots of c mod q and not just the first one.

and the flag is `buckeye{r0ots_0f_uN1Ty_w0rk_f0r_th1s???}`

Original writeup (https://github.com/Y-CTF/writeups/blob/main/BuckeyeCTF/crypto/Defective-RSA/defective-RSA.md).