WhiteHat Summer Contest 2017: Da Nang

,

problem

整数$n, c_1, c_2, c_3, c_4$が書かれたファイルとバイナリmakefile.pycが与えられる。

solution

.pycのdecompileはuncompyleで一発。いくらかforkがあるがrocky/python-uncompyle6を使った。 以下のように得られた。

$ uncompyle6 makefile.pyc
# uncompyle6 version 2.9.11
# Python bytecode 2.7 (62211)
# Decompiled from: Python 3.5.2 (default, Nov 17 2016, 17:05:23) 
# [GCC 5.4.0 20160609]
# Embedded file name: /root/Desktop/ctf-2017/rade/makefile.py
# Compiled at: 2017-04-21 20:42:38
from FLAG import *
from Crypto.Util.number import *
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e1 = 17
e2 = 23
m1 = pow(flag, e1, n)
m2 = pow(flag, e2, n)
c1 = pow(m1 + 12345, e1, n)
c2 = pow(m1 + 56789, e1, n)
c3 = pow(m2 + 12345, e2, n)
c4 = pow(m2 + 56789, e2, n)
# okay decompiling makefile.pyc

まず$m_1, m_2$を求める。$c_1, c_2$と$c_3, c_4$の形から Franklin-Reiter Related Message Attack をそれぞれ使えばよい。 次に$m = \mathrm{flag}$。 $m_1 = m^{17}, \; m_2 = m^{23}$であるが、互いに素なので$-4 \cdot 17 + 3 \cdot 23 = 1$とできて$m = m_1^{-4} \cdot m_2^3$。

implementation

eshihoによる神ライブラリを借りた。

#!/usr/bin/env python2
import scryptos
import gmpy2
import Crypto.Util.number

n = 23992456508721632904544057999056395984840598682551527471151904763246778638836805311058576074076544471814362118450963752614808101805018226501728749753154687251596663180454809994272928278066817153483685668132338944992849111855590973474678454159123639456555256485147196164078477717189520027988101925788303558976065942012105491523422884349644306896086216721825961334666043695121350988761613913914655313225263251356627080558127266206207253980892813908459449433940028268804981985006285644508736389967109173883994849116220035021283230523958640143355551140077459561176550844398278642511471910168765368624465988996082307992457
c1 = 20373828497176435167633953604896280749084861536083536617122139289929021045377176745113967394233342868062933415554192920963948057887324013008257380015103546511196207444982065505097904316167335975881412955740451727799394577357107415462104942067847048630173382510001061068806873459709567970640047451719077689284250663779574472232440594570502056709748603086893912068708152949459839465110567129133452824619222918019880393381073202052633467737917229789195417254877277542398992729106705037414050409175283815504552780234997208287185820010853470529752628470226853313501197054312938111140137899570545855875031148908922559079288
c2 = 4360293477491071631082413589399984151934700148049881396354060511784164719699104502640364063839372357371432182276578283932647249629707984639755245731994004982047010862474568253438883825981211552726455647610616600152683140602219777227764342827766552684058977170125324805316413550680703753463380261978903747369677517090549750490497714726106808405188795507741435252228742048791254891796083781713724953974101730953449734214103419451007355326070889428042830527374106171411884042865409718813225704924308910578917985370161732700040769553579304781551439507813917217693054553136139858632877393572913681604198562756394542739717
c3 = 4345261358659519189634881349240932351623603440440060460588285817392306152201826610576491755629698765088135761317793967803519010356869269204503397215039512744495117601932620637450095192646479479541571697381615227131485964855439316795397514445542660502760126364064850197352955455820341422106740318181122113707487426652989875585231637716536188004952356846847687782788196021954904944243050038759261831381697585862182084930662578928342538660648403902072793943235882313263403348511364765676275877687747514403142706712995406077875195587485333137738286810493929324782535392363155178660765334428891921464976278013274433592459
c4 = 11163192691864487842504791707572292045010440994593022973064948393324184598662086767886111478358067883324039072186651857397731078118781186686459647088206129240315423019956385054334592265029781917246602461962626683725203283354094411740566113019140776580459728655850754495232498348144806199874330892136766891492831287879346899778473534258469040357585649045269842028785546606058644151580331160754603828262995696611984149905299109630697269974668616156412842759609194334129212734919638779629261074770920807952993453659743525451175541328430753432209789806184520128139906770561431423993324872179142853918272022140840732281811

e1 = 17
e2 = 23
a = 1
b1 = 12345
b2 = 56789

rsa1 = scryptos.crypto.RSA(e1, n)
rsa2 = scryptos.crypto.RSA(e2, n)
m1 = scryptos.crypto.attack.rsautil.franklin_reiter(rsa1, a, b2 - b1, c1, c2) - b1
m2 = scryptos.crypto.attack.rsautil.franklin_reiter(rsa2, a, b2 - b1, c3, c4) - b1
assert pow(m1 + 12345, e1, n) == c1
assert pow(m1 + 56789, e1, n) == c2
assert pow(m2 + 12345, e2, n) == c3
assert pow(m2 + 56789, e2, n) == c4
assert -4 * e1 + 3 * e2 == 1
flag = pow(gmpy2.invert(m1, n), 4, n) * pow(m2, 3, n) % n
assert pow(flag, e1, n) == m1
assert pow(flag, e2, n) == m2
print(Crypto.Util.number.long_to_bytes(flag))