Twisted Pair - Crypto
Points: 379 | Flag: BCCTF{D0n7_g37_m3_Tw157eD} | Solved by: Smothy @ 0xN1umb
what we got
Two files - twisted.py (the encryption script) and output.txt (the ciphertext + leaked data).
Standard RSA setup: 2048-bit modulus, e=65537, encrypts the flag. But then it does something... extra:
python
big_phi = random.randint(0,n)*phi
while True:
re = random.randint(0,big_phi)
if GCD(re,big_phi) == 1:
break
rd = pow(re,-1,big_phi)
pair = (re,rd)
print(f'{pair = }')So it generates a random multiple of phi(n), picks a random re coprime to it, computes rd = re^-1 mod (k*phi), and gives us the pair (re, rd). Pirates of the Caribbean directed by Neil Breen energy fr
the solve
ngl this one is pretty clean once you see it.
The pair satisfies: re * rd ≡ 1 (mod k*phi(n))
Which means: re * rd - 1 = some_multiple * phi(n)
We don't need to know phi(n) exactly - any multiple of it works for RSA decryption. Since phi(n) | (re*rd - 1), we can just compute d = e^-1 mod (re*rd - 1) and decrypt directly.
python
from Crypto.Util.number import long_to_bytes
e = 65537
n = 19439549016736157994445321693716040304496933450908822830785546447356640938511848515214532122372952441346382348128090174385087017754998004263381903884172795798757896926826260449846311910180853151538259309672492531324912131577860449270020688788366137622442261077969101936856886468427403503365170525720181200754907385203281019298013389265144353497812868401395189562634728998457080685763102902488110622042183414383376133784185227529047183145706173322408469168595067002050530160003250965650735537845720141274147934660047991379437776625773963875755922847596512541977962335056654809228448939009248139668055223843528453193627
c = 10865486250749452142829147770482732012487969708821238516693448330349468418227459641475547081102702086677531653095577156280433833007301271064736089402735961863463499425835353938322367186631386954910571357542522352851606734267112862425675362830802930895116490507368125983668070978569384503057862431314754354250141897768332390599984376279250392410491911090745319395845216865552404683564862397429175177742652676096774337224907473253647904202840435500415158287477060365136008564890741237405076344181807293233823268380867432277489255560740985941277746668879974687962969921322915449681628570166395660116063667538437643191778
re, rd = (78765931572837890184732485573855040355734906667616732365425975961372176734490908760586140213247695844258164690113856764449962633507514086870855977086816171599249980551485754833342744585856747583660831419118402998816441031186529255916191778486002599988365783301200884074628562271353930052100268091401601001352029406181820779235660022506500744323483557190202214564852496130042887915901484203538953743898572705208120100144410589773705113057043119800833832111060314428862327520335726221445871013179354182645704676962338676793114575163621601767760507165301721886624251824432858237612254205394349688833372550507942811289139413264033829882510339925802192503391563444045703909987218227845096393478838535269070817059826463084736961089572978014382430035781314515208324747036229868042290784852033042874558604432224005163718694172245343564311670051223512443733554163748501818786399835388405106427636662313296155957034886040235139781879066960976091286511938017784550048698819479967398905299013186135794546137301063043829295439920954475639248584023875352900082592641833682772678691258949438442520763882466710221480527946455848870885439265744459533309671272363393961813498032240293923368716112266816632737047499214760445112990128047541791833572827, 131970604089427781093168606837673636992630015470914936103123920413207852926709889256646383426836615540159262846418011750882734630193317352850600322481025539933491985114268193122631390578816208240929415962476199734150525102408941592018308043892595100016034081973871738665243269781550616215211792968831596211190794343929452824581046407715989485527452256218968631961375664818092224014538346509000511329897864091996499571026139363240809226838903148669542961266755723503275265968159130125214735123578268845542378412361750129319969720614958017500379350599673543082513688655710046111460286418503919155149746284910623921263483191314244456818012541093775511309319094066327272065786426998104015986517123969641893773863826339545456049697091019834833730086250524311249733464240335712869091889103805867341240404898126314487597920288551355801575807245535302964160133333369247197055552045510147310254904775557090011535805307767892672774555376087479967970272926218076424124477211776587526151256641072847864998082118692762794409593378397349174173985530922396585882206274522841399151027762258839530878512906205295198572934622857595056290337561982608996188493611715171287228756006357170286646088568403471562908235292011333236920822539972541202731306163)
# re * rd - 1 is a multiple of phi(n) - use it directly
kphi = re * rd - 1
d = pow(e, -1, kphi)
m = pow(c, d, n)
print(long_to_bytes(m))
# b'BCCTF{D0n7_g37_m3_Tw157eD}'3 lines of actual math lmao. the "twisted pair" just hands you a multiple of phi on a silver platter.
flag
BCCTF{D0n7_g37_m3_Tw157eD}
smothy out ✌️