$ :(){ :|:& };:

読者です 読者をやめる 読者になる 読者になる

$ :(){ :|:& };:

なめこうどん

Vigenere - SECCON 2016 Online CTF

CTF

Problem

Vigenere


k: ????????????

p: SECCON{???????????????????????????????????}

c: LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ


k=key, p=plain, c=cipher, md5(p)=f528a6ab914c1ecf856a1d93103948fe


|ABCDEFGHIJKLMNOPQRSTUVWXYZ{}

-+—————————-

A|ABCDEFGHIJKLMNOPQRSTUVWXYZ{}

B|BCDEFGHIJKLMNOPQRSTUVWXYZ{}A

C|CDEFGHIJKLMNOPQRSTUVWXYZ{}AB

D|DEFGHIJKLMNOPQRSTUVWXYZ{}ABC

E|EFGHIJKLMNOPQRSTUVWXYZ{}ABCD

F|FGHIJKLMNOPQRSTUVWXYZ{}ABCDE

G|GHIJKLMNOPQRSTUVWXYZ{}ABCDEF

H|HIJKLMNOPQRSTUVWXYZ{}ABCDEFG

I|IJKLMNOPQRSTUVWXYZ{}ABCDEFGH

J|JKLMNOPQRSTUVWXYZ{}ABCDEFGHI

K|KLMNOPQRSTUVWXYZ{}ABCDEFGHIJ

L|LMNOPQRSTUVWXYZ{}ABCDEFGHIJK

M|MNOPQRSTUVWXYZ{}ABCDEFGHIJKL

N|NOPQRSTUVWXYZ{}ABCDEFGHIJKLM

O|OPQRSTUVWXYZ{}ABCDEFGHIJKLMN

P|PQRSTUVWXYZ{}ABCDEFGHIJKLMNO

Q|QRSTUVWXYZ{}ABCDEFGHIJKLMNOP

R|RSTUVWXYZ{}ABCDEFGHIJKLMNOPQ

S|STUVWXYZ{}ABCDEFGHIJKLMNOPQR

T|TUVWXYZ{}ABCDEFGHIJKLMNOPQRS

U|UVWXYZ{}ABCDEFGHIJKLMNOPQRST

V|VWXYZ{}ABCDEFGHIJKLMNOPQRSTU

W|WXYZ{}ABCDEFGHIJKLMNOPQRSTUV

X|XYZ{}ABCDEFGHIJKLMNOPQRSTUVW

Y|YZ{}ABCDEFGHIJKLMNOPQRSTUVWX

Z|Z{}ABCDEFGHIJKLMNOPQRSTUVWXY

{|{}ABCDEFGHIJKLMNOPQRSTUVWXYZ

}|}ABCDEFGHIJKLMNOPQRSTUVWXYZ{


Vigenere cipher

https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher

Solution

ヴィジュネル暗号の問題(ご丁寧にWikiのリンクまである)。

plainの一部が解っているのでKPAして残りの5文字を総当りしてhashと一致するか見て終わり。

計算量はO(n^5)だけどn=28なのでまあ余裕だろうと

require 'digest/md5'

def enc s
    s.ord <= 90?(s.ord-"A".ord):(s=='{' ? 26:27)
end

def dec i
    i <= 25?((i+"A".ord).chr):(i==26?'{':'}')
end

def bfa s,i,key
    3.times { |e| key[(7+i)+12*e] = dec(s) }
    26.times { |e| bfa(e,i+1,key) } if i < 4
    key.size.times { |e| $plain[e] = dec($table[key[e].to_sym].index($cipher[e])) }
    if Digest::MD5.hexdigest($plain) == $plain_md5
        puts $plain
        exit
    end
end

$cipher = "LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ"
$plain = "SECCON{???????????????????????????????????}"
$key = "???????????????????????????????????????????"
$plain_md5 = "f528a6ab914c1ecf856a1d93103948fe"
# Vigenere table
$table = { "A":"ABCDEFGHIJKLMNOPQRSTUVWXYZ{}" }
28.times { |e| $table[dec(e+1).to_sym] = $table[dec(e).to_sym].split("").rotate.join  }

# KPA
7.times { |e| 4.times { |f| $key[e+12*f] = $table.select { |k,v| v[enc($plain[e])] == $cipher[e] }.keys.join } }

# 総当り
28.times { |e| bfa(e,0,$key) }


f:id:taiyoslime:20161211212129p:plain

ちょうどJOI2016-17予選前夜だったので競プロっぽく(?)楽しめた

FLAG:SECCON{ABABABCDEDEFGHIJJKLMNOPQRSTTUVWXYYZ}