Writeup #
So, to start off, I knew pretty much nothing about cryptography and assumed that it was probably all black magic before this, but after spending 3 days on this challenge asking for help and googling everything I could, I can now say with abosulte certainty that my assumptions are correct. Crypto is black magic.
To start, we are given two files. puzzle.py, which is the script that was used to encrypt the flag, and output.txt, which gives us p, q, n, and our cipher text c. We also know what e is as it is used in the python script provided.
Now searching google for “get d from p q and e”, we can use the work and knowledge of other people to solve our own problems! I found a stackoverflow article
here which tells us that d is chosen such that d * e == 1 modulo phi(n), where phi is Euler’s Totient function. Normally without knowing p and q, finding Euler’s Totient of N would be a computationally hard problem, but with p and q it can simply be calculated as phi(N) = phi(pq) = phi(p)phi(q) = (p-1)(q-1). So now our d is chosen such that d * e == 1 modulo (p-1)(q-1).
Now to solve for d all we have to do is use the Euclidean algorithm to find the modular multiplicative inverse of e and phi(N).
I ended up copying and pasting some code from geeksforgeeks at first, but then I found a library which does the same thing in one line of code named sympy. Here is a great excerpt from their docs explaining the modular_inverse():
For a given a and m, the multiplicative inverse of a exists if the greatest common divisor of a and m is 1. The number c is the multiplicative inverse of a if a * c % b == 1. For example, for the numbers 56 and 15, the multiplicative inverse of 56 exists because the greatest common divisor of 56 and 15 is 1. The multiplicative inverse is 11 because 56 * 11 % 15 == 1.
With this information, we can write our python2 script to get d:
from sympy import *
e = 3
c = 15152748367446880771626735564570314364412539866133828878294832734877333779375887301666317343696170583205732549176049143952513352176887862696752491725708864667819416380851470922363167693469581137082049422236381718504826584222025025276217712186948248894030905507578741594465520464407304317496197519614579605451009261929501814390584449735588732230862107938755575264114796923591931144483631719354506203232033044574475941823978540906150537364865247200187073042362762490541339927821746184534026286488138506628489962230620460382693248638990548515405134649935123113868204987749497591513259850481628137175362068619575569454324
p = 130434182441603098085956776986813693398366763586020595512987159262899881890442688054651285679445774176839742529438968247167884605733178945825821059309729815062559567359570195682209847084470163302154894657907891113360770217802272940478214121960691147987814527126966323988405399896137541783289094003238223701919
q = 138597380327352419687534641412929290366492126278628014509152301908796041605702001247395731165417386922727859751004918809393586670242582269855310098688232449832555137905517447148665895209928971190929217518775532945000140189878993116900459734922686648711225089388803124904970682571061993115829417981574164016773
n = 18077835991546137626820743332925077231374737772399662733145449713866011668129359761316411770700730249209055598603865901584346720655918002520497560096702556660488788089523716553127902860314936315334492018184193779273443235661432144600266866272632983217297397458819395207649787022607046418182404092209433511795673252554662035312548958373228547867077383341748826769860988734874145040410943724039648358353546951266751272373383570512852677958180656795351767986838842090885711457878146575773989204434421168580537893668075110329840981458434754807779731175606434893879571660655888569704898013958232952940247995442346868287387
phi = (p-1)*(q-1)
d = mod_inverse(e, phi)
print d
And we get our d: 12051890661030758417880495555283384820916491848266441822096966475910674445419573174210941180467153499472703732402577267722897813770612001680331706731135037773659192059682477702085268573543290876889661345456129186182295490440954763066844577515088655478198264972546263471766524681738030945454936061472955674530269480661262053196516977969885869922208349634589452106559232849134966077943199356491734227672455860111455780061959788970860804454803263719780424552560586550660397835075372621962075641426681356058302520994261124180986714033835659166934038212482038064787021362760079413874347954327355612027419655638356320379131
We can double check that d is correct by checking if (ed) % phi(N) = 1. Checking our solution reveals that d is in fact the correct key. Now all that is left to to use the key to get the flag. To decrypt, we first need to convert from long to bytes, as we need to reverse what puzzle.py did, and then we can perform P = C ^ (d % N) and get the flag. The final python script looks like:
from sympy import *
from Crypto.Util.number import *
e = 3
c = 15152748367446880771626735564570314364412539866133828878294832734877333779375887301666317343696170583205732549176049143952513352176887862696752491725708864667819416380851470922363167693469581137082049422236381718504826584222025025276217712186948248894030905507578741594465520464407304317496197519614579605451009261929501814390584449735588732230862107938755575264114796923591931144483631719354506203232033044574475941823978540906150537364865247200187073042362762490541339927821746184534026286488138506628489962230620460382693248638990548515405134649935123113868204987749497591513259850481628137175362068619575569454324
p = 130434182441603098085956776986813693398366763586020595512987159262899881890442688054651285679445774176839742529438968247167884605733178945825821059309729815062559567359570195682209847084470163302154894657907891113360770217802272940478214121960691147987814527126966323988405399896137541783289094003238223701919
q = 138597380327352419687534641412929290366492126278628014509152301908796041605702001247395731165417386922727859751004918809393586670242582269855310098688232449832555137905517447148665895209928971190929217518775532945000140189878993116900459734922686648711225089388803124904970682571061993115829417981574164016773
n = 18077835991546137626820743332925077231374737772399662733145449713866011668129359761316411770700730249209055598603865901584346720655918002520497560096702556660488788089523716553127902860314936315334492018184193779273443235661432144600266866272632983217297397458819395207649787022607046418182404092209433511795673252554662035312548958373228547867077383341748826769860988734874145040410943724039648358353546951266751272373383570512852677958180656795351767986838842090885711457878146575773989204434421168580537893668075110329840981458434754807779731175606434893879571660655888569704898013958232952940247995442346868287387
phi = (p-1)*(q-1)
d = mod_inverse(e, phi)
m = pow(c, d, n)
m = long_to_bytes(m)
print m[:37]
And running it with python2 we get the flag!
osu{dE<rypT_RsA_W1TH-eU1ER'S-thEOrem}