The Obligatory RSA Challenge

RSA with factorable n

Problem

Would you believe last year someone complained because we didn't have any RSA challenges?

Solution

Passing n into factordb, we see that n is a square.

Decoding is then trivial. Note that since $n=p^2$, $\phi(n)=p(p-1)$ instead of $(p-1)^2$.

from Crypto.Util.number import inverse, long_to_bytes
import string

n = 475949103910858550021125990924158849158697270648919661828320221786290971910801162715741857913263841305791340620183586047714776121441772996725204443295179887266030140253810088374694440549840736495636788558700921470022460434066253254392608133925706614740652788148941399543678467908310542011120056872547434605870421155328267921959528599997665673446885264987610889953501339256839810594999040236799426397622242067047880689646122710665080146992099282095339487080392261213074797358333223941498774483959648045020851532992076627047052728717413962993083433168342883663806239435330220440022810109411458433074000776611396383445744445358833608257489996609945267087162284574007467260111258273237340835062232433554776646683627730708184859379487925275044556485814813002091723278950093183542623267574653922976836227138288597533966685659873510636714530467992896001651744874195741686965980241950250826962186888426335553052644834563667046655173614036106867858602780687612991191030530253828632354662026863532605714273940100720042141793891322151633985026545935269398026536029250450509019273191619994794225225837195941413997081931530563686314944827757612844439598729054246326818359094052377829969668199706378215473562124250809041972492524806233512261976041
e = 65537
c = 402152770613351738677048755708324474554170176764376236321890073753918413309501149040535095814748232081435325267703210634002909644227960630174709988528642707754801508241021668904011536073077213912653767687757898322382171898337974911700337832550299932085103965369544431307577718773533194882182023481111058393084914882624811257799702110086578537559675833661097129217671283819819802719020785020449340858391080587707215652771744641811550418602816414116540750903339669304799230376985830812200326676840611164703480548721567059811144937314764079780635943387160912954258110357655610465371113884532394048454506662310124118115282815379922723111955622863507979527460353779351769204461491799016534724821436662464400182076767643570270346372132221638470790194373337215168535861219992353368908816850146790012604023887493693793270280077392301335013736929937492555191042177475011094313978657365706039774511145223613781837484571546154539993982179172011867034689022507760853121804219571982660393205589671062476958539437099789304135763092469236641459611160765143625998223459045923936551054351546033776966693997323972592968414107451804594097481574453747907874383069514662912314790514989026350766602740419907710031860078783498791071782013064557781230616536
p = 21816257788879800226266741950501282709401872894176288619472731956291218914324742537604641219560786978413613510633536886641581153942571579359519401327796021367732695476711467566761398025402445133259848384123905962932802004021079944067083532491720877926448099933753336517689984808846750048960375488528766110009254176926887611598941876012437215971816681184483796662759984833863168641346915636162467824574775331116852844756225674938392321848711476249893809700776552828990831593983374320915711192051109410295925205263499219444742867868898381959251178728127024835656647566724333855154762699836449704050690295585931350731821
q = 21816257788879800226266741950501282709401872894176288619472731956291218914324742537604641219560786978413613510633536886641581153942571579359519401327796021367732695476711467566761398025402445133259848384123905962932802004021079944067083532491720877926448099933753336517689984808846750048960375488528766110009254176926887611598941876012437215971816681184483796662759984833863168641346915636162467824574775331116852844756225674938392321848711476249893809700776552828990831593983374320915711192051109410295925205263499219444742867868898381959251178728127024835656647566724333855154762699836449704050690295585931350731821

assert p * q == n

phi = p * (q-1)
d = inverse(e, phi)
m = pow(c, d, n)

m = long_to_bytes(m)
print(m)