EVEN RSA CAN BE BROKEN???

• Description: This service provides you an encrypted flag. Can you decrypt it with just N & e?
• Difficulty: Easy

---

🔎 Solution

This challenge centers around the RSA algorithm.

We begin by recalling the fundamentals of RSA, including its key formulas and structure. RSA encryption uses a public key (N, e) and encrypts a message M into a ciphertext C using the equation:

C = M^e mod N

To decrypt and recover the original plaintext M, we need the private key exponent d, which satisfies:

M = C^d mod N

However, computing d requires knowing Euler's totient function φ(N), which in turn depends on the prime factors p and q of N, since:

N = p * q
φ(N) = (p - 1)(q - 1)

Upon connecting to the server, we are provided with N, e, and the ciphertext C.

N: 21037151367180372765283953053086158000036636729721345923644288910205211401496718658564665653657364950489341853920464418028274161652165537591176971735966138
e: 65537
cyphertext: 6941187568627937171315289359497121515277569008096997024216911574186045398719488165082024925203613804200214707279648799387512395476391994412507744098543075

A key insight in this challenge is that N is an even number. Since the product of 2 odd primes is always odd, the only way for N to be even is if one of the primes is 2. Thus, we deduce:

p = 2
q = N / 2

With both p and q known, we can compute φ(N), derive the private exponent d, and ultimately decrypt the ciphertext to recover the original plaintext M. Here I write a little script to solve the challenge:

from Crypto.Util.number import long_to_bytes

N = 21037151367180372765283953053086158000036636729721345923644288910205211401496718658564665653657364950489341853920464418028274161652165537591176971735966138
e = 65537

q = N // 2
phi_N = q - 1
d = pow(e, -1, phi_N)

c = 6941187568627937171315289359497121515277569008096997024216911574186045398719488165082024925203613804200214707279648799387512395476391994412507744098543075
m = pow(c, d, N)
flag = long_to_bytes(m)
print(flag)

🚩Flag

picoCTF{tw0_1$_pr!m33486c703}