RRSA Writeup

Overview

This is a crypto challenge built on a textbook RSA setup with one twist: both primes are generated from the same public constant. The handout ships the generator source, so the relationship between p, q and that constant is visible in plaintext. Recovering phi(n) from that relationship, without ever factoring n, is enough to decrypt the ciphertext and read the flag.

Reconnaissance

The handout is the generator itself, with the flag blanked and its output pasted into a trailing docstring:

r = 1333932344710022001826837667329537548527

p = x * r + 1
q = y * r + 1

n = p*q

flag = b'SkillBit{REDACTED}'.hex()
flag = int(flag,16)

ct = pow(flag,65537,n)

‍
x and y come from the missing secret module, so they are the only unknowns. r is right there in the source, which is the whole challenge in one line: the primes are not independent, and the quantity they share is public.

Checking the sizes is the next move, and it settles the approach immediately:‍

$ python3 -c "
r=1333932344710022001826837667329537548527
n=8747185035038982590352709040026122318881751481045969499780427282145739554557145347428163122801488496160428126673378817922050559571378731528689279527994219
print('n bits', n.bit_length(), '| r bits', r.bit_length(), '| (n-1) % r ==', (n-1)%r)"
n bits 512 | r bits 130 | (n-1) % r == 0

‍
r divides n - 1 exactly, confirming the x*r + 1 shape. A 512-bit n against a 130-bit r leaves x and y at roughly 126 bits each, so their sum lands around 127 bits and stays comfortably under r.

Exploitation

That size relation is what collapses the problem. Write out = (n - 1) / r = x*y*r + (x + y). Because x + y < r, this is literally out written in base r: the high part is x*y and the low part is x + y. One divmod recovers both.

$ python3 -c "
r=1333932344710022001826837667329537548527
n=8747185035038982590352709040026122318881751481045969499780427282145739554557145347428163122801488496160428126673378817922050559571378731528689279527994219
xy, s = divmod((n-1)//r, r)
print('x*y =', xy); print('x+y =', s); print('check:', xy*r*r + s*r + 1 == n)"
x*y = 4915873593709293827309521584358477882447515767535180913750809363560371424736
x+y = 140743442471588577643702866489893047062
check: True

‍The reconstruction check passes, so the split is right. x and y are now the roots of z^2 - (x+y)*z + x*y, which would hand over p and q, but decrypting never needs them. phi(n) is x*y*r^2, and x*y is already in hand.

Getting the Flag

With phi(n) known, the private exponent is an ordinary modular inverse and the decryption is a single pow:‍

$ python3 -c "
r=1333932344710022001826837667329537548527
n=8747185035038982590352709040026122318881751481045969499780427282145739554557145347428163122801488496160428126673378817922050559571378731528689279527994219
ct=1046038076233413876680986621738638966868902190991554511891709431142926821179422307244746230382433945021363558520372439295018128820530515472036158797508375
phi = ((n-1)//r // r) * r * r
d = pow(65537, -1, phi)
print(bytes.fromhex(hex(pow(ct, d, n))[2:]).decode())"
SkillBit{aLLLways_th3_w4yy}

‍The plaintext decodes cleanly, which confirms phi(n) was exact rather than a multiple that happened to work.