Challenge Description

We are given an RSA setup where the primes have a special structure. From the provided Python code:

CR7 = 143
PnQ_Size = CR7 * 2

p = getPrime(...)
q = int(str(p)[CR7:] + str(p)[:CR7])

The challenge also provides:

• n
• e
• c

The key observation is that q is constructed by rotating the digits of p.

Specifically:

p = L | R
q = R | L

Where:

• L = first 143 digits
• R = last 143 digits

Thus both primes contain 286 digits.

Step 1 — Express p and q mathematically

Let:

B = 10^143

Then we can write:

p = L·B + R
q = R·B + L

Step 2 — Expand n

Since:

n = p · q

we obtain:

n = (L·B + R)(R·B + L)

Expanding:

n = LR·B² + (L² + R²)·B + LR

Define:

A = LR
C = L² + R²

So:

n = A·B² + C·B + A

Rearranging:

n = A(B² + 1) + C·B

Step 3 — Recover C

Take the equation modulo (B² + 1):

n ≡ C·B  (mod B² + 1)

Therefore:

C ≡ n · B⁻¹ mod (B² + 1)

So we can compute C directly.

Step 4 — Recover A

Using the previous equation:

A = (n - C·B) / (B² + 1)

Now we know:

A = LR
C = L² + R²

Step 5 — Solve for L and R

Using the identities:

(L + R)² = L² + R² + 2LR
(L - R)² = L² + R² - 2LR

Substitute A and C:

(L + R)² = C + 2A
(L - R)² = C - 2A

Thus:

S = √(C + 2A)
D = √(C - 2A)

Then:

L = (S + D) / 2
R = (S - D) / 2

Step 6 — Recover p and q

Now reconstruct the primes:

B = 10^143

p = L·B + R
q = R·B + L

Verify:

p * q == n

Step 7 — Decrypt the message

Standard RSA decryption:

φ = (p − 1)(q − 1)

d = e⁻¹ mod φ

m = c^d mod n

Convert the integer back to bytes.

Solver Script

from Crypto.Util.number import *
import gmpy2

n = ...
e = 65537
c = ...

CR7 = 143
B = 10**CR7

mod = B*B + 1

C = (n * inverse(B, mod)) % mod
A = (n - C*B) // mod

S = gmpy2.isqrt(C + 2*A)
D = gmpy2.isqrt(C - 2*A)

L = (S + D)//2
R = (S - D)//2

p = L*B + R
q = R*B + L

phi = (p-1)*(q-1)
d = inverse(e, phi)

m = pow(c, d, n)

print(long_to_bytes(m))

Final Flag

upCTF{H0p3_y0u_d1dnt_us3_41_1_sw3ar_th1s_1s_n1ce...If you are CR7 and you solved this, I love you}