Dream Stealing - b01lers/bootcamp-2020 GitHub Wiki

Solution for: Dream Stealing

Concept

This challenge is meant as an introduction to RSA.

Solution

What is given:

Modulus: 98570307780590287344989641660271563150943084591122129236101184963953890610515286342182643236514124325672053304374355281945455993001454145469449640602102808287018619896494144221889411960418829067000944408910977857246549239617540588105788633268030690222998939690024329717050066864773464183557939988832150357227
One factor of N:  9695477612097814143634685975895486365012211256067236988184151482923787800058653259439240377630508988251817608592320391742708529901158658812320088090921919
Public key: 65537
Ciphertext: 75665489286663825011389014693118717144564492910496517817351278852753259053052732535663285501814281678158913989615919776491777945945627147232073116295758400365665526264438202825171012874266519752207522580833300789271016065464767771248100896706714555420620455039240658817899104768781122292162714745754316687483

With this information one can notice that given one factor of N we can easily compute the other. This is because N is typically the product of two primes factors, p and q, so . Now that we have the prime factors of N, computing the totient via Euler's totient is trivial for the following reasons:

  1. (Multiplicative)
  2. , for a prime m and is equivalent to

With these two properties in mind the solution is as follows:

In Python,

N= 98570307780590287344989641660271563150943084591122129236101184963953890610515286342182643236514124325672053304374355281945455993001454145469449640602102808287018619896494144221889411960418829067000944408910977857246549239617540588105788633268030690222998939690024329717050066864773464183557939988832150357227
p =  9695477612097814143634685975895486365012211256067236988184151482923787800058653259439240377630508988251817608592320391742708529901158658812320088090921919
e = 65537
c = 75665489286663825011389014693118717144564492910496517817351278852753259053052732535663285501814281678158913989615919776491777945945627147232073116295758400365665526264438202825171012874266519752207522580833300789271016065464767771248100896706714555420620455039240658817899104768781122292162714745754316687483
q = N//p
d = pow(e,-1,(p-1)*(q-1)) #Only works in Python3.8+ 
m = pow(c,d,N)

#Now to convert the integer into bytes
m = bytearray.fromhex(hex(m)[2:])
print(m)

Flag: flag{4cce551ng_th3_subc0nsc10us}