Hello Codegate

코드게이트 디스코드 시작 공지에 적혀있다.

The Codegate2025 competition has begun.
Hello Codegate's Flag is: codegate2025{65782695e16255e3ef8517a1bfb059f0}

플래그: codegate2025{65782695e16255e3ef8517a1bfb059f0}

Capcha World

문제가 너무 빠르게 풀리길래 먼저 풀었다.

그냥 WSL에서 nc로 접속 후 보이는 문자열을 입력하면 된다.

10라운드만 보내면 됨.

플래그: codegate2025{4445996c1f4cc11f9fb7eabe177d4988952dc112d768b8baf17076c0d30a10124aaee8b64682a53fab5d07bd31fff8}

Encrypted flag

Me:

from Crypto.Util.number import bytes_to_long, getPrime
from sympy import nextprime
import gmpy2

p = getPrime(512)
q = nextprime(p)

n = p * q
e = 65537

flag = "codegate2025{FAKE_FLAG}"
phi = (p - 1) * (q - 1)

d = gmpy2.invert(e, phi)

m = bytes_to_long(flag.encode())
c = pow(m, e, n)

print(f"n: {n}")
print(f"e: {e}")
print("Encrypted flag:", c)

# n : 54756668623799501273661800933882720939597900879404357288428999230135977601404008182853528728891571108755011292680747299434740465591780820742049958146587060456010412555357258580332452401727868163734930952912198058084689974208638547280827744839358100210581026805806202017050750775163530268755846782825700533559
# e : 65537
# Encrypted flag : 7728462678531582833823897705285786444161591728459008932472145620845644046450565339835113761143563943610957661838221298240392904711373063097593852621109599751303613112679036572669474191827826084312984251873831287143585154570193022386338846894677372327190250188401045072251858178782348567776180411588467032159

write the python code to find the correct flag

ChagGPT:

Below is one way to break this RSA instance using Fermat’s factorization (which works well here since the primes are consecutive). In this code, we factorize nnn to recover ppp and qqq, compute ϕ(n)\phi(n)ϕ(n), derive the private exponent ddd, and then decrypt ccc to obtain the flag.

from math import isqrt
from Crypto.Util.number import long_to_bytes
import gmpy2

# Given RSA parameters:
n = 54756668623799501273661800933882720939597900879404357288428999230135977601404008182853528728891571108755011292680747299434740465591780820742049958146587060456010412555357258580332452401727868163734930952912198058084689974208638547280827744839358100210581026805806202017050750775163530268755846782825700533559
e = 65537
c = 7728462678531582833823897705285786444161591728459008932472145620845644046450565339835113761143563943610957661838221298240392904711373063097593852621109599751303613112679036572669474191827826084312984251873831287143585154570193022386338846894677372327190250188401045072251858178782348567776180411588467032159

# Since q is the immediate prime after p, p and q are very close.
# We can use Fermat's factorization method to find them.
a = isqrt(n)
if a * a < n:
    a += 1

while True:
    b2 = a * a - n
    b = isqrt(b2)
    if b * b == b2:
        break
    a += 1

p = a - b
q = a + b

# Calculate the Euler totient function
phi = (p - 1) * (q - 1)

# Compute the modular inverse of e modulo phi to get d
d = int(gmpy2.invert(e, phi))

# Decrypt the ciphertext
m = pow(c, d, n)

# Convert the resulting number back to bytes (the flag)
flag = long_to_bytes(m)
print(flag.decode())

How the code works:

1. **Fermat Factorization:**p=a−bandq=a+b

   We compute a=⌈n⌉a = \lceil \sqrt{n} \rceila=⌈n⌉ and then look for a bbb such that a2−n=b2a^2 - n = b^2a2−n=b2. When found, we have:

   p=a−bandq=a+bp = a - b \quad \text{and} \quad q = a + b

2. Key Recovery:

   Once ppp and qqq are known, we compute ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)ϕ(n)=(p−1)(q−1) and then determine the private key exponent ddd as the modular inverse of eee modulo ϕ(n)\phi(n)ϕ(n).