NITIC CTF 2 Writeup [Crypto]

Caesar Cipher

フラグの中身がシーザー暗号で暗号化されています。 暗号化されたフラグの中身はfdhvduです。

nitic_ctf{復号したフラグの中身}

を提出してください

とのことなので、rot13.comで適当にいじってROT10と特定し復号しました。

ord_xor

import os
flag = os.environ["FLAG"]


def xor(c: str, n: int) -> str:
    temp = ord(c)
    for _ in range(n):
        temp ^= n
    return chr(temp)


enc_flag = ""
for i in range(len(flag)):
    enc_flag += xor(flag[i], i)

with open("./flag", "w") as f:
    f.write(enc_flag)

暗号化の関数xor(c, n)は $n⊕c$ を $n$ 回行っています。ここで $n$ が偶数のときxor()への第一引数と返り値は同じになり、また奇数の場合でも $n⊕c$ をもう1回行えば復号できると考えられます。配布ファイルのxor()をそのまま流用して復号しました。

def xor(c: str, n: int) -> str:
    temp = ord(c)
    for _ in range(n):
        temp ^= n
    return chr(temp)


cipher = "nhtjcZcsfroydRx`rl"
flag = ""

for i in range(len(cipher)):
    flag += xor(cipher[i], i)

print(flag)

tanitu_kanji

import os
alphabets = "abcdefghijklmnopqrstuvwxyz0123456789{}_"
after1 = "fl38ztrx6q027k9e5su}dwp{o_bynhm14aicjgv"
after2 = "rho5b3k17pi_eytm2f94ujxsdvgcwl{}a086znq"

format = os.environ["FORMAT"]
flag = os.environ["FLAG"]

assert len(format) == 10


def conv(s: str, table: str) -> str:
    res = ""
    for c in s:
        i = alphabets.index(c)
        res += table[i]
    return res


for f in format:
    if f == "1":
        flag = conv(flag, after1)
    else:
        flag = conv(flag, after2)

with open("./flag", "w") as file:
    file.write(flag)

暗号化の重要部conv(s, table)はsの各文字に対して、その文字がalphabets[i]にあるときtable[i]の文字と置き換えるという処理を行っています。tableとして取りうるのはafter1とafter2の2つでformatに沿って暗号化されているみたいです。

ここでformatの長さが10でbit全探索で殴れることに注目し、あとは暗号化と逆の手順を行えばフラグを得ることができます。

alphabets = "abcdefghijklmnopqrstuvwxyz0123456789{}_"
after1 = "fl38ztrx6q027k9e5su}dwp{o_bynhm14aicjgv"
after2 = "rho5b3k17pi_eytm2f94ujxsdvgcwl{}a086znq"

cipher = "l0d0pipdave0dia244im6fsp8x"

def conv(s: str, table: str) -> str:
    res = ""
    for c in s:
        i = table.index(c)
        res += alphabets[i]
    return res


for i in range(2**10):
    flag = cipher
    for j in range(10):
        if i & 1:
            flag = conv(flag, after1)
        else:
            flag = conv(flag, after2)
        i >>= 1
    if "ctf{" in flag:
        print(flag)

summeRSA

from Crypto.Util.number import *
from random import getrandbits

with open("flag.txt", "rb") as f:
    flag = f.read()
    assert len(flag) == 18


p = getStrongPrime(512)
q = getStrongPrime(512)
N = p * q

m = bytes_to_long(b"the magic words are squeamish ossifrage. " + flag)

e = 7
d = pow(e, -1, (p - 1) * (q - 1))
c = pow(m, e, N)

print(f"N = {N}")
print(f"e = {e}")
print(f"c = {c}")

自明stereo-typed message attackです。既知部分としてthe magic words are squeamish ossifrage. nitic_ctf{が与えられているので、そのまましゅっと復号します。

from Crypto.Util.number import *


def stereotyped_message_attack(prefix, c):
    PR.<x> = PolynomialRing(Zmod(n))
    f = (prefix + x)^e - c
    diff = f.small_roots(epsilon=1/40)
    if len(diff):
        return long_to_bytes(int(diff[0]))
    else:
        return "not found..."

n = 139144195401291376287432009135228874425906733339426085480096768612837545660658559348449396096584313866982260011758274989304926271873352624836198271884781766711699496632003696533876991489994309382490275105164083576984076280280260628564972594554145121126951093422224357162795787221356643193605502890359266274703
e = 7
c = 137521057527189103425088525975824332594464447341686435497842858970204288096642253643188900933280120164271302965028579612429478072395471160529450860859037613781224232824152167212723936798704535757693154000462881802337540760439603751547377768669766050202387684717051899243124941875016108930932782472616565122310

prefix = "the magic words are squeamish ossifrage. nitic_ctf{"
prefix = bytes_to_long(prefix.encode("utf-8")) << (8 * 8)

print(stereotyped_message_attack(prefix, c))