Challenge

This challenge is about a server send out RSA modulus $N$, a public exponent $e$, and a value $H \equiv (ed)^{N-p-q} \pmod N$, then asks for the totient (φ) in hex. After you submit φ, the server returns the encrypted flag.

When connecting with $nc$, the server prints:

Can you solve this RSA mystery..?
{"N": 2628966957595745200..., "e": 65537}

H = pow(e*d, N-p-q, N)
{"H": 1655862580644323756...}
Give me the totient and I will give you an encrypted secret !!!
Totient (HEX format) >

So the server gives us:

  • The RSA public modulus $N$
  • The public exponent $e$
  • A value $H$ computed as:
\[H = (e \cdot d)^{N - p - q} \bmod N,\]

Solve

Euler’s totient is:

\[\phi(N) = (p-1)(q-1) = N - (p + q) + 1.\]

Therefore:

\[\phi(N) - 1 = N - p - q\]

Our equation:

\[H = (e \cdot d)^{N - p - q} \bmod N,\]

we substitute:

\[H = (e \cdot d)^{\phi - 1} \bmod N.\]

We can split the exponent:

\[(\phi - 1) = \phi + (-1)\]

So we can rewrite:

\[H \equiv (e\cdot d)^{\phi} \cdot (e\cdot d)^{-1} \pmod{N}.\]

From Euler’s theorem:

\[(e\cdot d)^{\phi} \equiv 1 \pmod{N}.\]

So:

\[H \equiv (e\cdot d)^{-1} \pmod{N}.\]

From RSA key relations there exists an integer \(k\) such that:

\[e \cdot d = 1 + k \cdot \phi.\]

Replace our value of \(e \cdot d\) :

\[H \equiv (1 + k \phi)^{-1} \pmod{N}\]

Rearranging to solve for φ

Starting from:

\[H \cdot (1 + k \phi) \equiv 1 \pmod{N}\]

Multiply both sides by the inverse of \(H\) modulo \(N\) :

\[1 + k \phi \equiv H^{-1} \pmod{N}\]

Then:

\[k \phi \equiv H^{-1} - 1 \pmod{N}\]

Finally:

\[\phi \equiv \bigl((H^{-1} \bmod N) - 1\bigr) \cdot (k^{-1} \bmod N) \pmod{N}\]

Then compute the private key \(d\) as:

\[d = \frac{1 + k \cdot \phi}{e}\]

Verify the candidate by checking:

\[H \stackrel{?}{=} (e \cdot d)^{\phi - 1} \bmod N\]

Brute-force \(k\) in the range \([1, e)\) . Once verification passes, send \(\phi\) to the server. The server will return the secret \(c\) .

from tqdm import *
from pwn import *
from json import *

e = 65537

io = remote('<target-host>', <target-port>)
print(io.readline())
N = int(loads(io.readline())['N'])
print(f"{N = }")
print(io.readline())
print(io.readline())
H = int(loads(io.readline())['H'])
print(f"{H = }")

for k in trange(1, e):
  phi_ = ((pow(H, -1, N) - 1) * pow(k, -1, N)) % N
  d_ = (1 + k*phi_) // e
  if H == pow(e*d_,phi_-1,N):
      break

io.sendlineafter(b"Totient (HEX format) >", hex(phi_).encode()[2:])
io.interactive()

Output

b'Can you solve this RSA mystery..? \n'
N = 17855693236867595798209950063495084897824464817565576281911400841218796475380262262790517958368701614249455174903696331949702900564132477223082690944525752469960049609943171500500354523083548683917854544195239819967768707580577711430934360276425034163541794347425390991862677902817168733367887928787749972990872681305361734061142558673591975052229807520262152353004135641247484395143182842813911271207307430919049815664424153174101420460043500877345120160195265875347436714955314086949876575184854361131605360490438608055211937504959816076657868409199925299499813725357336511544193877775903107144884576091042690007867
b'\n'
b'H=pow(e*d,N-p-q,N)\n'
H = 9156039753068189625876702673322746815604131738949343680170518116978305038431704348266480886635819606903067128401129671333328430451012286289677587862553837317743443072858529495840436021322630535520222513439247869236683208579814756884333706383534433327104785343348852039708943359428816190119241371978762110559173188845869695988059729256038793908669001312191241088572896597129409242029663785507945343787650040224809021255455599012244894250161725248435270717683148379918037832843296361581061569393784842175224734234417493844103311683195917305469164250630564363132706636860072123879682950934228744567980771318228041059780
  7%|██▍                                | 4548/65536 [00:47<10:38, 95.45it/s]
[*] Switching to interactive mode
 {"Secret": 4627543643611901345294197868238621476004591986127547457964568512128761042275140084589946961296209275221264660047272711376551411166858028295511108840866320695157973986732131612751981985103325600033797921475513474672730673537359438302301243437357395989838058276595853907398362741061336996066840662475091866292897841455545902224385815199292305041453059118840067425781774777961286666387740391598195741826739090150544245559824895236629588771739053257098504903280992612755838048059468753268602613007286347113098913544109227567345668765382553678298771904684500056729185970204929524872176641601306367671557748967440797892415}

Now we have the values of \(c\) and \(k\) , we can easily decrypt our flag.

N = 17855693236867595798209950063495084897824464817565576281911400841218796475380262262790517958368701614249455174903696331949702900564132477223082690944525752469960049609943171500500354523083548683917854544195239819967768707580577711430934360276425034163541794347425390991862677902817168733367887928787749972990872681305361734061142558673591975052229807520262152353004135641247484395143182842813911271207307430919049815664424153174101420460043500877345120160195265875347436714955314086949876575184854361131605360490438608055211937504959816076657868409199925299499813725357336511544193877775903107144884576091042690007867
H = 9156039753068189625876702673322746815604131738949343680170518116978305038431704348266480886635819606903067128401129671333328430451012286289677587862553837317743443072858529495840436021322630535520222513439247869236683208579814756884333706383534433327104785343348852039708943359428816190119241371978762110559173188845869695988059729256038793908669001312191241088572896597129409242029663785507945343787650040224809021255455599012244894250161725248435270717683148379918037832843296361581061569393784842175224734234417493844103311683195917305469164250630564363132706636860072123879682950934228744567980771318228041059780
c = 4627543643611901345294197868238621476004591986127547457964568512128761042275140084589946961296209275221264660047272711376551411166858028295511108840866320695157973986732131612751981985103325600033797921475513474672730673537359438302301243437357395989838058276595853907398362741061336996066840662475091866292897841455545902224385815199292305041453059118840067425781774777961286666387740391598195741826739090150544245559824895236629588771739053257098504903280992612755838048059468753268602613007286347113098913544109227567345668765382553678298771904684500056729185970204929524872176641601306367671557748967440797892415
e = 65537
k = 4549
phi_ = ((pow(H, -1, N) - 1) * pow(k, -1, N)) % N
d_ = (1 + k*phi_) // e
flag = pow(c, d_, N)
print(bytes.fromhex(f"{flag:02x}"))
#JUST{89d2555c6359010daa498cee87bbfe89}