EASYCTF - Hidden Key
21 Feb 2018Ugh, another RSA problem? Help me decrypt this message please
In this RSA problems we were given n, e, c and 2d+phi, this is quite unusual.
Here is a little remainder about RSA which was the key to break this challenge :
(2d+ϕ(n))⋅e ≡ 2(modϕ(n)) (2d+ϕ(n))⋅e−2 is a multiple of ϕ(n)
Since we have a multiple of ϕ(n) we can simplify it as ϕ(n) and then compute d with e and ϕ(n). With d it’s easy to decrypt the message.
#!/usr/bin/python
# -*- coding: utf-8 -*-
import gmpy2
from binascii import unhexlify
n=19990710965993909791193558953663863842716769444918482808910894555010666976748556807943571692638988159930173956944656563631741966254238894083044816619560716384399435457151325454058699456619177095082739114918161476095521966514549276456455115517585546091939841433970464864198559599506627551134733008368542674335406822985465670762736804248626405288459854078565454481711995430549718518246465196294098491520982031878812304780893142564431716580715290610805513492838815042887242751666146443085743188203774501774915953398942354972882252219853560961234640718803572197573296585708559809830903143884640474369446564530912297999521
e=65537
c=8025685155587827180749002332463831813455982477944159367184464001423830512599313738552168574362711918043974393498564044937232805190392231176714828625219488929799007862383671251782267431518386284895291720893481842879894034679412243426415287703098927504021006098497271548107186318346892921299400164587635569971533266853314645746958189806838848498965711804048690998169078994695592407758719375981296365133822297753540261208595663456324109356953019435140804032717009580539387311073394562413638372631954952133915031842285456227340035222247884804569872816819686780785351794877280774221497500401217616558942721963001462728375
nd=2
d2phi =28210947928664918152315905418138701975334591740280006730014083553026787097541343438660133536252948089770695463356325540443494323679593792180973845459460952065666206687674099912172862321206054790665154184389292800680080635290974630855115550204608340568825978834279756678368982149319772886983641561438165277302259422493412115453040278208881837632374967653081531078115068245925765496120513676555110320384751634593488268523936092446138555814256400738443018669468243127211526991525454393164042696191097755962617379270695590316170180293471814761703656591983750865989997806949387354748826846587397721824112207687726809868578
phi_multiple = d2phi*e -nd
d = gmpy2.invert(e, phi_multiple)
intmsg = pow((c), d, n)
message = "%2X" % intmsg
print ("Plain : %s" % unhexlify(message))