ctf4b writeup

1. veni_vidi_vici

• 問題のzipファイルを解凍すると3つのファイルが出てくる。

1. Gur svefg cneg bs gur synt vf: pgs4o{a0zber
2. Lzw kwugfv hsjl gx lzw xdsy ak: _uDskk!usd_u
3. {ʎɥdɐɹɓ0ʇdʎᴚ :sı ɓɐlɟ ǝɥʇ ɟo ʇɹɐd pɹıɥʇ ǝɥ⊥

• 3番目のファイルの内容に注目するとthe third part of the flag is : Rypt0graphy} となっている。
  　このことから1番目と2番目のファイルの内容をthe first part of the flag isとthe second part of the flag is
  　になるように文字をずらせばよいと予想をたてる。つまりrot13のこと。

　rot13のデコードはこのサイトを使用しました。

• 1番目(Gur svefg cneg bs gur synt vf: pgs4o{a0zber)についてはGからTまで13文字ずらせばいいのでROT13を指定
  結果はThe first part of the flag is: ctf4b{n0moreです。

• 2番目(Lzw kwugfv hsjl gx lzw xdsy ak: _uDskk!usd_u)についてはLからTまで8文字ずらせばいいのでROT8を指定しました。
  　結果はThe second part of the flag is: _cLass!cal_cです。

• よってctf4b{n0more_cLass!cal_cRypt0graphy}が答えです。

• ちなみに問題文の意味はこちら

2. RSA is Power

問題文にもある通りRSA暗号に関する問題です。RSA暗号についてはこちら

N=97139961312384239075080721131188244842051515305572003521287545456189235939577

E = 65537

C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

RSA暗号についてほとんど理解していなかったので、ひとまずWEBで調査しました。

とりあえず分かったことは、

1. 公開鍵(ここではNのこと)=P x Q
2. Eは暗号化指数ということ
3. Cは暗号文(cipherの頭文字)
4. 暗号文＝平文^E % N
5. 平文＝暗号文^D % N

ここでDが何か調べました。すると復号化指数についてこちらに説明がありました。

Dの値が欲しいのでこちらのサイトを参考にしてプログラムを組みました。

また、PとQの値も必要なので求めます。こちらのサイトを使用しました。

P=299681192390656691733849646142066664329
Q=324144336644773773047359441106332937713

処理終了時に出力される文字列を16進数に直して、ASCIに変換する処理も追加しています。

以上のすべてをまとめたコードがこちら

rsa.py

# -*- coding: utf-8 -*-
import binascii
def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1

    while c1 != 0:
        m = c0 % c1
        q = c0 // c1

        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)

    return c0, a0, b0


def lcm(x, y):#最小公倍数
    return x * y // gcd(x, y)

def gcd(a,b):#最大公約数
    while b:
        a, b=b, (a%b)
    return a

cipher = 77361455127455996572404451221401510145575776233122006907198858022042920987316
p, q = 299681192390656691733849646142066664329, 324144336644773773047359441106332937713
n = p * q
e = 65537
λ = lcm(p-1, q-1)
c, a, b = ex_euclid(e, λ)
d = a % λ

plain = pow(cipher, d, n)
print(binascii.unhexlify(str(hex(plain))))

実行するとctf4b{5imple_rs4_1s_3asy_f0r_u}が得られます。