Twisted Pair
by SeanPirates of the Caribbean -- Directed by Neil Breen
Solution
Analysis
We are given two files:
- twisted.py -- The encryption script.
- output.txt -- The output containing RSA parameters e, n, c, and a "twisted" pair (re, rd).
The encryption script does standard RSA encryption of the flag:
pub, priv = genRSA()
n, e = pub
phi, d = priv
c = pow(m, e, n)
It then generates a "twisted" keypair:
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)
So re * rd = 1 (mod big_phi), where big_phi = k * phi(n) for some random k.
Approach
The critical observation is straightforward: since re * rd = 1 (mod k * phi(n)), the value re * rd - 1 is a multiple of phi(n).
For RSA decryption, we do not actually need phi(n) itself -- any multiple of phi(n) works as the modulus for computing the private exponent. Specifically:
d = e^{-1} mod (re * rd - 1)
Since re * rd - 1 is a multiple of phi(n), and gcd(e, phi(n)) = 1, this inverse exists and produces a valid decryption exponent. Then:
m = pow(c, d, n)
This was solved in a single step with no false starts.
Key Insight
The "twisted" pair (re, rd) satisfies re * rd = 1 (mod k * phi(n)), which means re * rd - 1 is a multiple of phi(n). Since RSA decryption works with any multiple of phi(n) as the modulus for computing d, the private exponent can be derived directly from the leaked pair without needing to factor n or recover phi(n) exactly.
Flag
BCCTF{D0n7_g37_m3_Tw157eD}
Solve Scripts
from Crypto.Util.number import long_to_bytes
e = 65537
n = 19439549016736157994445321693716040304496933450908822830785546447356640938511848515214532122372952441346382348128090174385087017754998004263381903884172795798757896926826260449846311910180853151538259309672492531324912131577860449270020688788366137622442261077969101936856886468427403503365170525720181200754907385203281019298013389265144353497812868401395189562634728998457080685763102902488110622042183414383376133784185227529047183145706173322408469168595067002050530160003250965650735537845720141274147934660047991379437776625773963875755922847596512541977962335056654809228448939009248139668055223843528453193627
c = 10865486250749452142829147770482732012487969708821238516693448330349468418227459641475547081102702086677531653095577156280433833007301271064736089402735961863463499425835353938322367186631386954910571357542522352851606734267112862425675362830802930895116490507368125983668070978569384503057862431314754354250141897768332390599984376279250392410491911090745319395845216865552404683564862397429175177742652676096774337224907473253647904202840435500415158287477060365136008564890741237405076344181807293233823268380867432277489255560740985941277746668879974687962969921322915449681628570166395660116063667538437643191778
re = 78765931572837890184732485573855040355734906667616732365425975961372176734490908760586140213247695844258164690113856764449962633507514086870855977086816171599249980551485754833342744585856747583660831419118402998816441031186529255916191778486002599988365783301200884074628562271353930052100268091401601001352029406181820779235660022506500744323483557190202214564852496130042887915901484203538953743898572705208120100144410589773705113057043119800833832111060314428862327520335726221445871013179354182645704676962338676793114575163621601767760507165301721886624251824432858237612254205394349688833372550507942811289139413264033829882510339925802192503391563444045703909987218227845096393478838535269070817059826463084736961089572978014382430035781314515208324747036229868042290784852033042874558604432224005163718694172245343564311670051223512443733554163748501818786399835388405106427636662313296155957034886040235139781879066960976091286511938017784550048698819479967398905299013186135794546137301063043829295439920954475639248584023875352900082592641833682772678691258949438442520763882466710221480527946455848870885439265744459533309671272363393961813498032240293923368716112266816632737047499214760445112990128047541791833572827
rd = 131970604089427781093168606837673636992630015470914936103123920413207852926709889256646383426836615540159262846418011750882734630193317352850600322481025539933491985114268193122631390578816208240929415962476199734150525102408941592018308043892595100016034081973871738665243269781550616215211792968831596211190794343929452824581046407715989485527452256218968631961375664818092224014538346509000511329897864091996499571026139363240809226838903148669542961266755723503275265968159130125214735123578268845542378412361750129319969720614958017500379350599673543082513688655710046111460286418503919155149746284910623921263483191314244456818012541093775511309319094066327272065786426998104015986517123969641893773863826339545456049697091019834833730086250524311249733464240335712869091889103805867341240404898126314487597920288551355801575807245535302964160133333369247197055552045510147310254904775557090011535805307767892672774555376087479967970272926218076424124477211776587526151256641072847864998082118692762794409593378397349174173985530922396585882206274522841399151027762258839530878512906205295198572934622857595056290337561982608996188493611715171287228756006357170286646088568403471562908235292011333236920822539972541202731306163
# re * rd - 1 is a multiple of phi(n)
kphi = re * rd - 1
# Compute private exponent
d = pow(e, -1, kphi)
# Decrypt
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag.decode())