この大会は2018/9/15 13:00(JST)~2018/9/16 13:00(JST)に開催されました。
今回もチームで参戦。結果は 3000点で165チーム中21位でした。
自分で解けた問題をWriteupとして書いておきます。
Analysis-Offensive 300
Alice, Bob, CyrilのメッセージがRSA暗号で暗号化されている。
eはすべて65537。Nはすべて異なる。お互いの組、3組について、公約数を求めてみる。
1以外になったので、素因数分解できた。あとはそのまま復号する。
from Crypto.Util.number import inverse
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y
def decrypt(p, q, e, c):
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
return m
N1 = 23795719145225386804055015945976331504878851440464956768596487167710701468817080174616923533397144140667518414516928416724767417895751634838329442802874972281385084714429143592029962130216053890866347
N2 = 46914096084767238967814493997294740286838053572386502727910903794939283633197997427383196569296188299557978279732421725469482678512672280108542428152186999218210536447287087212703368704976239539968977
N3 = 24543003393712692769038137223030855401835344295968717177380639898023646407807465197761211529143336105057325706788229129519925129413109571220297378014990693203802558792781281981621549760273376606206491
p1, _, _ = egcd(N1, N2)
p2, _, _ = egcd(N2, N3)
p3, _, _ = egcd(N1, N3)
assert p1 * p3 == N1
assert p1 * p2 == N2
assert p2 * p3 == N3
e = 65537
c1 = 18700320110367574655449823553009212724937318442101140581378358928204994827498139841897479168675123789374462637095265564472109735802305521045676412446455683615469865332270051569768255072111079626023422
m1 = decrypt(p1, p3, e, c1)
msg1 = ('%x' % m1).decode('hex')
print msg1
c2 = 27979368157170890767030069060194038526134599497456846620984054211906413024410400026053694007247773572972357106574636186987337336771777265971389911503143036021889778839064900818858188026318442675667707
m2 = decrypt(p1, p2, e, c2)
msg2 = ('%x' % m2).decode('hex')
print msg2
c3 = 24084879450015204136831744759734371350696278325227327049743434712309456808867398488915798176282769616955247276506807739249439515225213919008982824219656080794207250454008942016125074768497986930713993
m3 = decrypt(p2, p3, e, c3)
msg3 = ('%x' % m3).decode('hex')
print msg3
実行結果は以下の通りで、Bobのメッセージにフラグが含まれていた。
Hi Alice, party is tommorow at 8
Hi Bob, remember, that the flag is TMCTF{B3Car3fu11Ab0utTh3K3ys}
Hi Cyril, could you bring beer tommorow?
TMCTF{B3Car3fu11Ab0utTh3K3ys}
Forensics-Crypto1 400
ブロック暗号のFeistel構造の問題。ただf(x)がXOR関数になっているため、簡単に計算できる。
n: ブロック長の半分( = 144)
h: ラウンド数
l: 鍵サイズ( = 288)
M: 平文空間(2n)
C: 暗号空間(2n)
K: 鍵空間(l)
hが1の場合はMの後半とCの前半が同じになるが、この場合同じになっていない。まずhが2の場合を考える。
M = (m0, m1)
m0, m1 -> m1, m2 = m1, m0 ^ (m1 ^ k1)
m1, m2 -> m2, m3 = m2, m1 ^ (m2 ^ k2) = C
m2 = m0 ^ (m1 ^ k1)
m3 = m1 ^ (m2 ^ k2) = m1 ^ (m0 ^ (m1 ^ k1) ^ k2)
= m0 ^ k1 ^ k2
このことから逆算して復号する。
M = '010000010110111000100000011000010111000001110000011011000110010100100000011000010110111001100100001000000110000101101110001000000110111101110010011000010110111001100111011001010010000001110111011001010110111001110100001000000111010001101111001000000101010001110010011001010110111001100100'
C = '000100100011000101110101001101100110001100110001001110100011110101100000011110010010111000110011001110000000110100100101011111000011000000100001010000100110011100100001011000000111001101110100011011100110000000100000011011010110001001100100001011010110111001100110001010110110110101110001'
SECRET = '000000110000111001011100001000000001100100101100000100100111111000001001000001100000001100001001000100100010011101001010011000010111100100100010010101110100010001000010010101010100010101111111010001000110000001101001011111110111100001100101011000010010001001001011011000100111001001101011'
m0 = int(M[:144], 2)
m1 = int(M[144:], 2)
m2 = int(C[:144], 2)
m3 = int(C[144:], 2)
k1 = m0 ^ m1 ^ m2
k2 = m0 ^ m3 ^ k1
SECRET1 = int(SECRET[:144], 2)
SECRET2 = int(SECRET[144:], 2)
PLAIN1 = SECRET2 ^ k1 ^ k2
PLAIN2 = SECRET1 ^ PLAIN1 ^ k1
flag1 = ('%036x' % PLAIN1).decode('hex')
flag2 = ('%036x' % PLAIN2).decode('hex')
flag = flag1 + flag2
print flag
TMCTF{Feistel-Cipher-Flag-TMCTF2018}