osu!gaming CTF 2024 wysi-prime Writeup

I was able to solve only one problem because I was swamped with research. I looked into lucky-roll-gaming with A1y and VinhChilling but we all did not have enough time to spend on it unfortunately. I think I should focus on learning how to solve chals fast by having some sort of a library (both in my brain and on my computer) of chals.

There were so many osu! references in this CTF that I could not understand because I am not a osu! player. Had I played osu! before, I might have enjoyed this CTF more. The competition website is here.

crypto/wysi-prime

Author: willwam

There was no challenge description, but it gives you two files: script.py and output.txt.

## script.py
from Crypto.Util.number import isPrime, bytes_to_long
import random
import os

def getWYSIprime():
    while True:
        digits = [random.choice("727") for _ in range(272)]
        prime = int("".join(digits))
        if isPrime(prime):
            return prime

# RSA encryption using the WYSI primes
p = getWYSIprime()
q = getWYSIprime()
n = p * q
e = 65537
flag = bytes_to_long(os.getenv("FLAG", b"osu{fake_flag_for_testing}"))
ciphertext = pow(flag, e, n)
print(f"{n = }")
print(f"{e = }")
print(f"{ciphertext = }")

## output.txt
n = 2160489795493918825870689458820648828073650907916827108594219132976202835249425984494778310568338106260399032800745421512005980632641226298431130513637640125399673697368934008374907832728004469350033174207285393191694692228748281256956917290437627249889472471749973975591415828107248775449619403563269856991145789325659736854030396401772371148983463743700921913930643887223704115714270634525795771407138067936125866995910432010323584269926871467482064993332990516534083898654487467161183876470821163254662352951613205371404232685831299594035879
e = 65537
ciphertext = 2087465275374927411696643073934443161977332564784688452208874207586196343901447373283939960111955963073429256266959192725814591103495590654238320816453299972810032321690243148092328690893438620034168359613530005646388116690482999620292746246472545500537029353066218068261278475470490922381998208396008297649151265515949490058859271855915806534872788601506545082508028917211992107642670108678400276555889198472686479168292281830557272701569298806067439923555717602352224216701010790924698838402522493324695403237985441044135894549709670322380450

A typical RSA chal, except there is a hint about how $p$ and $q$ were chosen: they are both 272-digit prime numbers with every digit being either 2 or 7.

Whatever they are, they must be equal to $N$ when multiplied together, i.e. $N = pq$. This is too obvious to be mentioned here (?), but this also means we should have $N \equiv pq\; (\textrm{mod } 10)$, $N \equiv pq\; (\textrm{mod } 100)$, and so on. For instance, we can already figure out that the least significant digit $p$ and $q$ should be 7, because the least significant digit of $N$ is 9. More specifically, it is because $2 \times 2 = 4 \equiv 4 \; (\textrm{mod } 10)$, and $2 \times 7 = 14 \equiv 4 \; (\textrm{mod } 10)$, but $7 \times 7 = 49 \equiv 9 \; (\textrm{mod } 10)$.

All we need to do is to automate this process. There isn't much things I had to do, other than the fact that I needed a rookie reminder that variables in Python are references to objects in memory (I wasted an hour on that).

## wysi-prime_sol.py
p_digit_list = [["0" for _ in range(272)]]
q_digit_list = [["0" for _ in range(272)]]

for i in range(1, 273):
    modulus = pow(10, i)
    n_mod = n % modulus
    new_p_digit_list = []
    new_q_digit_list = []

    for p_digit in p_digit_list:
        for q_digit in q_digit_list:
            p_digit_temp = list(p_digit)
            q_digit_temp = list(q_digit) 
            # This is to avoid changing both p_digit_temp and 
            # p_digit at the same time
            # See https://stackoverflow.com/questions/29785084/
            # changing-one-list-unexpectedly-changes-another-too
            for digit1, digit2 in [("2", "2"), ("2", "7"), ("7", "2"),\
             ("7", "7")]:
                p_digit_temp[272 - i] = digit1
                q_digit_temp[272 - i] = digit2                
                p_cand = int("".join(p_digit_temp))
                q_cand = int("".join(q_digit_temp))                
                if (p_cand * q_cand) % modulus == n_mod:
                    new_p_digit_list.append(list(p_digit_temp))
                    new_q_digit_list.append(list(q_digit_temp))
    
    p_digit_list = list(new_p_digit_list)
    q_digit_list = list(new_q_digit_list)

for p_digits in p_digit_list:
    for q_digits in q_digit_list:
        p_cand = int("".join(p_digits))
        q_cand = int("".join(q_digits))
        if p_cand * q_cand == n:
            if isPrime(p_cand) == True and isPrime(q_cand) == True:
                print("Found p and q")
                p = p_cand
                q = q_cand
                break

phi_n = (p - 1) * (q - 1)
d = pow(e, -1, phi_n)
m = pow(ciphertext, d, n)
plaintext = long_to_bytes(int(m)) 
## osu{h4v3_y0u_3v3r_n0t1c3d_th4t_727_1s_pr1m3?}
print(plaintext)

Yes, I had noticed it before :)

Flag: osu{h4v3_y0u_3v3r_n0t1c3d_th4t_727_1s_pr1m3?}

Interestingly, the first thing I tried was to see if I can brute force this. I tried to generate multiple 272-digit prime numbers that only had 2 and 7 for its digits, and see if any of them become $N$ when multiplied, but apparently this takes forever.