# 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

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:

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:

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:

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

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:

e = 3494680627
p2 = 7700290168101389106225891477639129929001226792416017984661341954505371362577871619513480110997045873606558858973494882905175759502920368168780896854509931
ct = 896937076301392762743958156834404549614745613199699888403224725624929617011876252397149275690138390286900204448543394686055815777377732974510626768032590

Paste that into the solve script:

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