PragyanCTF 2019|Decode this - crypto-writeup-public

Ram has something to show you, which can be of great help. It definitely contains the piece of text "pctf" and whatever follows it is the flag. Can you figure out what it is?

Note: Enclose it in pctf{}

ciphertext.txtとencrypt.pyが渡される。

import random

file = open("secret.txt","r")
secret = file.read()

flag = ""
for i in secret:
    if i.isalpha():
        flag += i
l = len(flag)

key = [[int(random.random()*10000) for e in range(2)] for e in range(2)]

i = 0
ciphertext = ""

while i <= (l-2):
    x = ord(flag[i]) - 97
    y = ord(flag[i+1]) - 97
    z = (x*key[0][0] + y*key[0][1])%26 + 97
    w = (x*key[1][0] + y*key[1][1])%26 + 97
    ciphertext = ciphertext + chr(z) + chr(w)
    i = i+2

cipherfile = open('ciphertext.txt','w')
cipherfile.write(ciphertext)

やっていることは a, b, c, d <= 10000 を作って、 $C_1 = (M_1a + M_2b) \mod 26, C_2 = (M_1c + M_2d) \mod 26$ を計算しているだけ。問題文によってpctfという文字列が含まれていることがわかっている + mod 26をとっていているので鍵の範囲はせいぜい0, 26程度だろうという推測から鍵を全探索して"pctf"を暗号化している部分を生成し、もし4バイトがマッチしたらその鍵を試してみる、という戦略が成り立つ。

これをやるといい感じになる。itertools.productのおかげでループが潰れて見た目にはそんなに重たくなさそうに見える。長いように見えるけど暗号化ルーチンをまとめずにかいているからそう見えるだけ

from itertools import product
import string

strs = [chr(ci) for ci in range(0x20, 0x7F)]
table = {}

for k1, k2, k3, k4 in product(range(27), range(27), range(27), range(27)):
    x = ord("p") - 97
    y = ord("c") - 97
    z = (x * k1 + y * k2) % 26 + 97
    w = (x * k3 + y * k4) % 26 + 97

    x = ord("t") - 97
    y = ord("f") - 97
    z2 = (x * k1 + y * k2) % 26 + 97
    w2 = (x * k3 + y * k4) % 26 + 97

    table[(z, w, z2, w2)] = (k1, k2, k3, k4)


ciphertext = open("ciphertext.txt").read().strip()

for i in range(len(ciphertext) - 4):
    a = ord(ciphertext[i])
    b = ord(ciphertext[i + 1])
    c = ord(ciphertext[i + 2])
    d = ord(ciphertext[i + 3])

    key = (a, b, c, d)

    if key in table:
        key = table[key]
        print("the key is {}".format(key))

        table2 = {}
        for c1, c2 in product(string.ascii_lowercase, string.ascii_lowercase):
            x = ord(c1) - 97
            y = ord(c2) - 97
            z = (x * key[0] + y * key[1]) % 26 + 97
            w = (x * key[2] + y * key[3]) % 26 + 97

            table2[(z, w)] = (c1, c2)

        try:
            plaintext = ""
            for i in range(len(ciphertext) // 2):
                z = ord(ciphertext[i * 2])
                w = ord(ciphertext[i * 2 + 1])

                c1, c2 = table2[(z, w)]
                plaintext += c1 + c2
            print(plaintext)
        except KeyError:
            pass

かなり雑なスクリプトなのでかなり雑に候補が出てくる。grep --color=auto pctf みたいなのを噛ましてあげて読めそうなのを探すと ramhasalittlesecretforyourighthereitispctfilikeclimbinghillswhataboutyou が見つかる