神のミソ汁のセカイ

大学生活のことや技術的な備忘録を残してます

EasyCTF 2015: Cave Johnson Write-up

問題

EasyCTF 2015: Cave Johnson

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

問題文のヒントにあるように単純なVigenere暗号である。Vigenere暗号はメッセージが長いと鍵が繰り返し使われるので、鍵長ごとにメッセージをグループ化すると単純なシーザー暗号になる。そこで頻度分析を行って鍵を推定して復号化すればよい。 以下が解読プログラム。暗号文はcave-johnson.txtに保存してある。

#! /usr/bin/env python3
# encoding: utf-8

def grouping(cipertext, keylength):
    group = [None] * keylength
    for i in range(len(cipertext)):
        if group[i % keylength] == None:
            group[i % keylength] = []
        group[i % keylength].append(cipertext[i])
    return group

def frequency_analysis(text):
    count_list = [0] * 26
    for i in range(len(text)):
        count_list[ord(text[i]) - ord('a')] += 1
    s = float(sum(count_list))
    occurences = [float(n)/s for n in count_list]
    return occurences

def frequency(group, i):
    alphabet_freq = [0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150, 0.01974, 0.00074]
    plain = [chr((ord(n) - ord('a') - i) % 26 + ord('a')) for n in group]
    occurences = frequency_analysis(plain)
    f = 0.0
    for j in range(26):
        f += pow(alphabet_freq[j] - occurences[j], 2) / alphabet_freq[j] # Chi-squared value
    return f

def get_key_letter(group):
    freq = [frequency(group, i) for i in range(26)]
    return freq.index(min(freq))

def decrypt(ciphertext, key):
    plaintext = ""
    index = 0
    for c in ciphertext:
        if c != '_':
            c = ord(c) - ord('a')
            k = ord(key[index % len(key)]) - ord('a')
            p = (c - k) % 26
            plaintext += chr(p + ord('a'))
            index += 1
        else:
            plaintext += '_'
    return plaintext

with open('cave-johnson.txt','r') as f:
    ciphertext = f.read().strip()

for keylength in range(1,31):
    group = grouping(ciphertext, keylength)
    key = ''
    for i in range(keylength):
        key += chr(get_key_letter(group[i]) + ord('a'))
    print('length : '+str(keylength)+' key : ' + key)
    plaintext = decrypt(ciphertext, key)
    print('plaintext : ' + plaintext)

このプログラムを実行すると鍵長を1から30として鍵を探索し、復号した結果を出力する。

実行結果は

$ ./solver.py
---省略---
length : 12 key : iammoroncore
plaintext : helloandagainwelcometotheaperturesciencecomputeraidedenrichmentcenterehopeyourbriefdetentionintherelaxationvaulthasbeenapleasantoneyourspecimenhasbeenprocessedandwearenowreadytobeginthetestproperbeforewestarthoweverkeepinmindthatalthoughfunandlearningaretheprimarygoalsofallenrichmentcenteractivitiesseriousinjuriesmayoccurforyourownsafetyandthesafetyofotherspleaserefrainfromturningintheflagwrappedinthestandardformatthis_is_aperture_and_we_talk_too_much
---省略---

出力結果を目視で確認すると鍵長12で意味のある英文が出現している。よってflagはthis_is_aperture_and_we_talk_too_much

感想

Vigenere暗号関連の問題(0CTF 2015 Quals CTF: oldcrypto)を最近解いていたので簡単だった。頻度分析での分布の評価をカイ二乗値を使うように修正したのでより正確に鍵推定ができるようになったと思う。

今週末のGoogle CTF 2017頑張るぞ