---
# System prepended metadata

title: Hero 3 (YBN CTF 2024)
tags: [gcd ctf, gcd ctf challenge, unsafe eval, gcd exploit, eval ctf challenge, ctf, eval ctf writeup, eval exploit ctf challenge, fermats little theorem, fermat crypto, modinv ctf, crypto, ybn, custom rsa ctf, modular arithmetic ctf, ybnctf2024, fermat little theorem ctf, eval, rsa, fermat little theorem, eval exploit ctf writeup, writeups, gcd ctf writeup, custom rsa, "eval exploit\_", ybnctf, fermat ctf challenge, ybn ctf 2024, fermat ctf, fermat little theorem cryptography, eval is dangerous, fermat cryptography, ybn ctf writeups, fermat little theorem exploit, fermat theorem, ybn ctf, hcf, ctf writeups, modular inverse ctf, hcf ctf, eval exploit ctf, custom rsa challenge, fermat's little theorem, gcd, modular arithmetic, eval ctf, fermat]

---

# Hero 3
Crypto Challenge using Fermat's Little Theorem (YBN CTF 2024)

### Challenge Details
> Title: Hero 3 \
> Description: Because you were so good, I made it even harder! I even asked Fermat to help. I wonder what he did hmm.... \
> Attachments: `https://ctf.ybn.sg/files/b782a8f915f3ca4b5371263e8cc33fbe/Hero_3_chall.py` \
> Instance: `nc tcp.ybn.sg 20259`

### TLDR
```py
from Crypto.Util.number import long_to_bytes

e = 3494680627
p2 = 7700290168101389106225891477639129929001226792416017984661341954505371362577871619513480110997045873606558858973494882905175759502920368168780896854509931
ct = 896937076301392762743958156834404549614745613199699888403224725624929617011876252397149275690138390286900204448543394686055815777377732974510626768032590

d = pow(e, -1, p2 - 1)
f = pow(ct, d, p2)

print(long_to_bytes(f))
```


### Writeup
In the given file, we have:
```py
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import random

flag = b"YBN24{????????????????????????????????????????}"

try:
    p1 = getPrime(64)
    p2 = getPrime(512)
    e = getPrime(32)

    c = str(random.randint(0,999999999))
    a = input("a: ")
    b = input("b: ")

    check = ' 01qwertyuiopasdfghjklzxcvbnm%^&*()+-/><'

    for char in a:
        assert char not in check and char.isascii()

    for char in b:
        assert char not in check and char.isascii()

    a = eval(a + c)
    b = eval(b)
    d = pow(a, b, getPrime(128))
    z = pow(p1, p2-d, p2)

    ct = pow(bytes_to_long(flag) * z, e, p2)

    print("e =", e)
    print("p2 =", p2)
    print("ct =", ct)

except Exception as e:
    print(e)
    quit()
```

We also have the hint that this is using Fermat's Little Theorem, which states that:
> **If $p$ is a prime number, then for any integer $a$**,
> $$a^p \equiv a \pmod p$$
> **If $a$ and $p$ are coprime, then equivalently**,
> $$a^{p - 1} \equiv 1 \pmod p$$

Identify that in line 26:
```py
z = pow(p1, p2-d, p2)
```
If $d = 1$, then, since $p_1$ and $p_2$ are coprime, we can use Fermat's Little Theorem to derive that $z = 1$ \
To make $d = 1$, we can craft an input that would make $b = 0$, so that:
```py
d = pow(a, b, getPrime(128))
  = pow(a, 0, getPrime(128))
  = 1
```
Crafting an input that would make $b = 0$ is easy, as they use an unsafe eval. One could use `[]=={}` for example.

Finally, we solve for `bytes_to_long(flag)` in \
$\text{ct} = \text{bytes\_{}to\_{}long(flag)}^e \pmod 2 $
with 
```py
d = pow(e, -1, p2 - 1)
f = pow(ct, d, p2)

print(long_to_bytes(f))
```
Connecting to the challenge instance, and inputting `a: 3` (arbitrary number) and `b: []=={}` (evaluates to 0), I got:
```py
e = 3494680627
p2 = 7700290168101389106225891477639129929001226792416017984661341954505371362577871619513480110997045873606558858973494882905175759502920368168780896854509931
ct = 896937076301392762743958156834404549614745613199699888403224725624929617011876252397149275690138390286900204448543394686055815777377732974510626768032590
```
Paste that into the solve script:
```py
from Crypto.Util.number import long_to_bytes

e = 3494680627
p2 = 7700290168101389106225891477639129929001226792416017984661341954505371362577871619513480110997045873606558858973494882905175759502920368168780896854509931
ct = 896937076301392762743958156834404549614745613199699888403224725624929617011876252397149275690138390286900204448543394686055815777377732974510626768032590

d = pow(e, -1, p2 - 1)
f = pow(ct, d, p2)

print(long_to_bytes(f))
```
And we get:
:::spoiler Flag
YBN24{r0und1ng_up_w1th_f3rm4t's_l1ttl3_th30r3m}
:::
\
\
\
Main Writeups Page: https://hackmd.io/@ctf-lol/ybnctf2024