Less-easy RSA

Some maths!

Building on the earlier RSA challenge we have another, this time we're supplied with the following python code and it's output:

from Crypto.Util.number import *
from hidden import flag

p = getPrime(1024)
q = getPrime(1024)

e = 65537
n = p*q

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'{p + q = }')
print(f'{n = }')
print(f'{c = }')

p + q = 305559156843841841389033710781133965556321458576866220907849183308693546714043512600698516947685361766624383841606747482633535445140079519528240320749805575844657043457909059454564796917753145497047446112771977379894990155344510798505753591355017390426655436017455701975436639733788682497712555081124041108504
n = 23188040411222209920167986750501131244318516442962990541515576387124854402318391629172444526500800965352563481948025523069307688734978877788582154983828265728979836346230916441702819081687132120502927880576972264858012420528897803917497250525726895443788067912595087466018445625962255735533336400618516729233629740322049370618105066369945361055722299665722022103476872981475943414671857074556406922063765496862305498568111476621548141431004908705091722285447839010524392324923330340438905501774865462509715616229821737276087883253095417776939517336466256500675683806887439470955205208968714490262618489505437687978879
c = 7602552372128353681340203028777617487893783242719660434508062970905157083968456375476457709806021327183741493198422526937752676825986305299627542075157495218836184263521003203443989850632844780199031334970568756351549070900453776053848522682801053986204140169534021107527540794913780887413298543910962401529426727912556767734031848799755736369065463875883284565962138661031191649386025039769994991957405583464743627422304946156556627194310926108190762593414381393635313095993893383799789163391052373656530082623266221548297861304865773999431768151481093182012861656362875712106925312196356260955439183458418659584407

The first thing we need to decrypt the ciphertext c is to find the Euler totient of n given the information we have (p + q and p * q), it turns out with a bit of rearranging this is fairly easy:

$$\begin{aligned} \varphi &= (p-1)(q-1) \\ &= pq - p - q + 1 \\ &= pq - (p + q) + 1 \end{aligned}$$

Now that we've got phi decrypting the ciphertext is trivial, I'm going to use sage for the built in extended euclidean algorithm implementation:

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.2, Release Date: 2020-10-24               │
│ Using Python 3.9.7. Type "help()" for help.                  │
└────────────────────────────────────────────────────────────────────┘
sage: from Crypto.Util.number import long_to_bytes
sage: sum = 3055591568438418413890337107811339655563214585768662209078491833086935467140435126006985169476853617666243838416067
....: 4748263353544514007951952824032074980557584465704345790905945456479691775314549704744611277197737989499015534451079850575
....: 3591355017390426655436017455701975436639733788682497712555081124041108504
sage: product = 231880404112222099201679867505011312443185164429629905415155763871248544023183916291724445265008009653525634819
....: 4802552306930768873497887778858215498382826572897983634623091644170281908168713212050292788057697226485801242052889780391
....: 7497250525726895443788067912595087466018445625962255735533336400618516729233629740322049370618105066369945361055722299665
....: 7220221034768729814759434146718570745564069220637654968623054985681114766215481414310049087050917222854478390105243923249
....: 2333034043890550177486546250971561622982173727608788325309541777693951733646625650067568380688743947095520520896871449026
....: 2618489505437687978879
sage: ciphertext = 760255237212835368134020302877761748789378324271966043450806297090515708396845637547645770980602132718374149
....: 3198422526937752676825986305299627542075157495218836184263521003203443989850632844780199031334970568756351549070900453776
....: 0538485226828010539862041401695340211075275407949137808874132985439109624015294267279125567677340318487997557363690654638
....: 7588328456596213866103119164938602503976999499195740558346474362742230494615655662719431092610819076259341438139363531309
....: 5993893383799789163391052373656530082623266221548297861304865773999431768151481093182012861656362875712106925312196356260
....: 955439183458418659584407
sage: phi = product - sum + 1
sage: e = 65537
sage: _, d, _ = xgcd(e, phi)
sage: decrypted = pow(ciphertext, d, product)
sage: long_to_bytes(decrypted).decode()
ictf{3u13r_wuz_@_5m@r+_dud3}