# ASIS CTF Quals 2023 - renamiara

Recently, I have participated in Asis CTF Quals 2023. Although I can only solve one challenge, which is **renamiara**, through this challenge I have learned a little more about math and gained a little experience about the way that I should approach a problem. Because this is the most recent flag of mine, I want to share the solution and all my thinking process. This will be a super fast write-up and I hope you like it. :pancakes: 

# Renamiara

This is the link to the challenge [renamiara.py](https://github.com/KienHoSD/CTF-file/blob/master/2023archive/ASIS2023/renamiara/renamiara.py)

First, the server will give us a banner with "greetings and welcome" to the challenge and tell us that this is a real-world's discrete log problem (I don't think so :P)


If we enter "y" then the fun begin. If we enter "n" then ... :cricket:

ans = sc().decode().strip().lower()
if ans == 'y':
    NBIT = 32
    STEP = 40

    pr(border, "In each step solve the given equation and send the solution for x, y", border)
    c = 1
    while c <= STEP:
        nbit = NBIT * c
        p = getPrime(nbit)
        pr(border, f'p = {p}')
        pr(border, 'First send the base g: ')
        g = sc().strip().decode()
        pr(border, 'Send the solutions for pow(g, x + y, p) = x * y, as x and y:')
        xy = sc().strip().decode().split(',')
        try:
            g, x, y = [int(_) for _ in [g] + xy]
            print(g,x,y)
        except:
            die(border, 'Given number is not correct! Bye!!')
        if (x >= p-1 or x <= 1) or (y >= p-1 or y <= 1) or x == y:
            die(border, "Kidding me!? Your solutions must be smaller than p-1 and x ≠ y :(")
        if g <= 2**24 or g >= p-1:
            die(border, "Kidding me!? Please send the correct base :P")
        if pow(g, x + y, p) ==  x * y % p:
            if c == STEP:
                die(border, f"Congratulation! the flag is: {flag}")
            else:
                pr(border, "Good job, try to solve the next level!")
                c += 1
        else:
            die(border, "Try harder and be smarter to find the solution!!")
elif ans == 'n':
    pr(border, 'Bye!!')
else:
    pr(border, 'Please send a valid answer! Bye!!')

From the code of the challenge, we can see that this challenge will contain 40 sub-problems with the variable `c` being raised by 1 each time we complete 1 level (in this case, the prime `p = getPrime(32*c)` will be bigger). If we got to level 40, we could have the `flag`. So our way to solve all the sub-problems will be harder and harder, right? We will know later. :wink:

The server gave us $p$, and our job is to find $g,x,y$ to make the equation below valid. $$ g^{x+y}\%p = {xy \%p} $$

We can only input $x,y$ for $x \in range(1,p-1)$, $y \in range(1,p-1)$ and $x ≠ y$

if (x >= p-1 or x <= 1) or (y >= p-1 or y <= 1) or x == y:
    die(border, "Kidding me!? Your solutions must be smaller than p-1 and x ≠ y :(")

Also, we can only input $g$ for $g \in range(2^{24},p-1)$

if g <= 2**24 or g >= p-1:
    die(border, "Kidding me!? Please send the correct base :P")

So from here, I have come up with many weird solutions, like brute forcing the pair $(x,y)$ such that $x \in range(1,p-1)$ and $y = p-x$ that satisfies the equation at level 1 to see if there is any relation between $x,y$ and $g$ (I choose $g = 2^{24}+1$), but it takes longer than I thought, so I changed my approach.

Another approach of mine is to solve the equation with my crypto-challenge legendary ultimate tool, CASIO fx-580VN X the calculator (You didn't read wrong :P They work like magic sometimes) with small $g$ (like $g=2$) for computation test for random $x$ to have $y$, but I know this just for testing and then move on to the next idea.

After some thought, from the equation above, I have: $$ g^{x+y}\%p = {xy \%p}
<=> {g^{x+y} \over x*y} ≡ {1 (mod \ p)} $$

From Fermat little theorem we have: $$g^{p-1} ≡ 1(mod \ p) \ \ \ with \ p \ is \ prime$$
Linked those two together, I have to make $${g^{x+y} \over x*y} = g^{p-1}$$
To do that, first I came up with another weird solution is to find a pair $(x,y)$ to make $x+y = p-1$ and $inverse(x+y,p) = 1$, another brute force solution :laughing:. But I remember that I can change the variable $g$, so this leads me to my final solution for this challenge.

So my solution is to make $x+y = p$ and $(x*y)\%p=g$. Hence,$${g^{x+y} \over x*y} = {g^{p} \over g} = {g^{p-1}}$$
We will pick a random $x$ (I choose constant $x=2^{24}$) and $y=p-x$, and formed $g = (x*y)\%p$. Below is my code to solve this challenge first attempt:

from Crypto.Util.number import inverse
from pwn import *

io = remote('45.153.241.194', 31337)
# receive the greetings
for i in range(6):  
    print(io.recvline())
# yes
io.sendline(b'y')

# make the same attack for 40 levels
for i in range(40):
    # receive instruction msg or "next level" msg
    print(io.recvline())
    # receive p
    p = io.recvline()
    p = int(p.decode()[5:],10)
    print(io.recvline())
    print(p)
    x = 2**24 
    y = p-x
    g =pow(x*y,1,p)
    # send g
    io.sendline(str(g).encode())
    print(io.recvline())
    # send x,y
    io.sendline((str(x)+","+str(y)).encode())

io.interactive()

By the time I ran this code, it was working well for all my attempts to get the flag. But I remember that $g$ have to be in $range(2^{24},p-1)$, so maybe add another while loop to find random $x$ make pair $(x,p-x)$ that $(x*(p-x))\%p \in range(2^{24},p-1)$ if $g \notin range(2^{24},p-1)$ to make sure $g$ is valid before send $g,x,y$ to the server.

#### Conclusion
To sum up, this challenge was the easiest in the crypto category. I have learned that I should not approach a challenge with a brute-force solution instead of examining the math behind it first, and I shouldn't forget any detail that could lead me to the solution (I don't remember the $g$ at the time; only focus on $x$ and $y$). But this challenge didn't take me long to solve, and I'm really glad that I could solve it :smile:

I'm still really naive about crypto challenges, so my explanation could be unprecised. Other unsolved challenges still remain unsolved for me. I'm really curious about others' challenge solutions, but I will come back to it later if I can find a way to solve it. And finally, I hope that you will enjoy reading this little **Sonic** write-up of mine. Thanks you for reading, and have an A1 day!

#KienSD :running: