逆ポーランド記法による数式処理

逆ポーランド記法とは

逆ポーランド記法(Reverse Polish Notation: RPN)は、演算子オペランドの後に記述する数式やプログラムの記法の一つです。

例えば、一般的な中間記法で記述された数式 (1+2)*(5+4)逆ポーランド記法では 1 2 + 5 4 + * と記述されます。

逆ポーランド記法では、中間記法で必要とされた括弧が不要であり、また式の計算(評価) の実装が容易であるためコンピュータでの利用に適しています。

演算子を被演算子の後ろに置くことから、後置記法 (Postfix Notation) とも言うらしいです。

逆ポーランド記法で表された数式の評価

実装にはスタックを用います。

先頭から順に記号を読み込み、その記号が演算子以外であればスタックに値を積み、演算子であればスタックから値を2つ取り出して演算結果をスタックに積む、という簡単な操作の繰り返していき、最後にスタックの中に残った値が答えとなります。

AOJ 0087: Strange Mathematical Expression

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0087

試しにこの問題を解いてみましょう。

  • C++による解答例
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <cstdlib>
#include <cctype>
#include <cstdio>

using namespace std;

int main()
{
    string s;
    stack<double> St;
    double a, b;
    while (getline(cin, s)) {
        stringstream ss(s);

        while (ss >> s) {
            if (s == "+") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a+b);
            }
            else if (s == "-") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a-b);
            }
            else if (s == "*") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a*b);
            }
            else if (s == "/") {
                b = St.top(); St.pop();
                a = St.top(); St.pop();
                St.push(a/b);
            }
            else {
                St.push(atoi(s.c_str()));
            }
        }
        printf("%.6f\n", St.top());
        St.pop();
    }
    return 0;
}   
# coding: utf-8

def Calculate_RPN(L):
    St = []
    for i in L:
        if i == '+':
            b, a = float(St.pop()), float(St.pop())
            St.append(a+b)
        elif i == '-':
            b, a = float(St.pop()), float(St.pop())
            St.append(a-b)
        elif i == '*':
            b, a = float(St.pop()), float(St.pop())
            St.append(a*b)
        elif i == '/':
            b, a = float(St.pop()), float(St.pop())
            St.append(a/b)
        else:
            St.append(i)

    return St[0]


while True:
    try:
        s = raw_input().split()

    except EOFError:
        break

    print Calculate_RPN(s)

中間記法で記述された数式を逆ポーランド記法に変換する

この変換もスタックを用いて行うことが出来ます。

次のような手順で変換できます。

ほぼここ(http://knowledge.sakura.ad.jp/etc/220/)に書いてあることのコピペ。

  • 数式を左から順に読み込む
  • 数値だったら出力だったらスタックに積む だったらスタック上の演算子が出てくるまで出力しは削除する
  • 演算子だったらスタックに積む
    • スタックトップの演算子の優先順位がスタックに積まれる演算子より高ければそれを出力する
  • 数式を最後まで読み込んだ後、スタック上に演算子が残っていればそれをスタックが空になるまで順に出力する

逆ポーランド記法では演算子の優先順位は左に行くほど高くなります。

中間記法の数式を左から読み込んでいき演算子をスタックに積んだとき、+-*/などの同じ優先順位のものは先にスタックに入っているものの方が当然優先順位は高くなります。(中間記法では同じ優先順位なら左から計算が行われるから) (それはそう)

空白区切りなしで中間記法で表された数式1行が与えられ逆ポーランド記法に変換したものを出力するプログラムは次のように書けます。

動けばいいやと思って書いたクッソ汚いコードなのであまり参考にしないほうが良いと思います。

#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <cstdlib>
#include <cctype>
#include <cstdio>
#include <cstring>

using namespace std;

int str2arr(char s[], string A[]) {
    bool flag = true;
    string t;
    int l = strlen(s);
    int n = 0;
    for (int i = 0; i < l; i++) {
        if (isdigit(s[i]) && flag) {
            t = "";
            int j = 0;
            while (isdigit(s[i + j])) {
                t += s[i + j];
                if (i + j == l - 1)
                    break;
                j++;
            }
            A[n++] = t;
            flag = false;
        }
        else if (!isdigit(s[i])) {
            A[n++] = s[i];
            flag = true;
        }
    }
    return n;
}

// generate Reverse Polish Notation
int Generate_RPN(int n, string A[], string B[]) {
    map<string, int> table;
    table["*"] = 1;
    table["/"] = 1;
    table["+"] = 0;
    table["-"] = 0;
    table["("] = -1;
    table[")"] = -1;
    stack<string> S;
    int j = 0;

    for (int i = 0; i < n; i++) {
        if (isdigit(A[i][0])) {
            B[j++] = A[i];
        }

        else if (A[i] == "(")
            S.push(A[i]);

        else if (A[i] == ")") {
            while (S.top() != "(") {
                B[j++] = S.top();
                S.pop();
            }
            S.pop();
        }
        else {
            while ((!S.empty()) && (table[S.top()] >= table[A[i]])) {
                B[j++] = S.top();
                S.pop();
            }
            S.push(A[i]);
        }
    }
    while (!S.empty()) {
        B[j++] = S.top();
        S.pop();
    }
    return j;
}

int main()
{
    int l, t;
    string A[100], B[100];
    char s[10];

    scanf("%s", s);

    l = str2arr(s, A);
    t = Generate_RPN(l, A, B);

    for (int i = 0; i < t; i++) {
        cout << B[i];
        cout << (i == t-1 ? "\n" : " ");
    }

    return 0;
}
# coding: utf-8

# Convert String to List
def String2List(s):
    L = []
    flag = True
    l = len(s)
    for i in range(l):
        if s[i].isdigit() and flag:
            t = ""
            j = 0
            while s[i+j].isdigit():
                t += s[i+j]
                if i+j == l-1:
                    break
                j += 1
            L.append(t)
            flag = False

        elif not s[i].isdigit():
            L.append(s[i])
            flag = True

    return L


# generate Reverse Polish Notation
def Generate_RPN_List(L):
    S, L2 = [], []
    table = {"*": 1, "/": 1, "+": 0, "-": 0, "(": -1, ")": -1}
    for i in L:
        if i.isdigit():
            L2.append(i)
        elif i == "(":
            S.append(i)
        elif i == ")":
            while S[-1] != "(":
                L2.append(S.pop())
            S.pop()
        else:
            while len(S) != 0 and (table[S[-1]] >= table[i]):
                L2.append(S.pop())
            S.append(i)

    while len(S) != 0:
        L2.append(S.pop())

    return L2

s = raw_input()

print " ".join(Generate_RPN_List(String2List(s)))

中間記法で記述された数式を評価する

先に書いた2つのコードを合体させれば中間記法で記述された数式の評価が出来ます。

AOJ0109: Smart Calculator

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109&lang=jp

この問題を解いてみましょう。

C++逆ポーランド記法の数式を評価するとき全てdoubleで計算して最後にintにキャストするみたいにやったらWrongAnswerが出て辛かったです。

  • C++による解答例
#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <cstdlib>
#include <cctype>
#include <cstdio>
#include <cstring>

using namespace std;

int str2arr(char s[], string A[]) {
    bool flag = true;
    string t;
    int l = strlen(s);
    int n = 0;
    for (int i = 0; i < l; i++) {
        if (isdigit(s[i]) && flag) {
            t = "";
            int j = 0;
            while (isdigit(s[i+j])) {
                t += s[i+j];
                if (i+j == l-1)
                    break;
                j++;
            }
            A[n++] = t;
            flag = false;
        }
        else if (!isdigit(s[i])) {
            A[n++] = s[i];
            flag = true;
        }
    }
    return n;
}

int Generate_RPN(int n, string A[], string B[]) {
    map<string, int> table;
    table["*"] = 1;
    table["/"] = 1;
    table["+"] = 0;
    table["-"] = 0;
    table["("] = -1;
    table[")"] = -1;
    stack<string> S;
    int j = 0;

    for (int i = 0; i < n; i++) {
        if (isdigit(A[i][0])) {
            B[j++] = A[i];
        }

        else if (A[i] == "(")
            S.push(A[i]);

        else if (A[i] == ")") {
            while (S.top() != "(") {
                B[j++] = S.top();
                S.pop();
            }
            S.pop();
        }
        else {
            while ((!S.empty()) && (table[S.top()] >= table[A[i]])) {
                B[j++] = S.top();
                S.pop();
            }
            S.push(A[i]);
        }
    }
    while (!S.empty()) {
        B[j++] = S.top();
        S.pop();
    }
    return j;
}

int Calculate_RPN(int n, string s[]) {
    stack<double> St;
    double a, b;

    for (int i = 0; i < n; i++) {
        if (s[i] == "+") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a+b);
        }
        else if (s[i] == "-") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a-b);
        }
        else if (s[i] == "*") {
            b = int(St.top()); St.pop();
            a = int(St.top()); St.pop();
            St.push(a*b);
        }
        else if (s[i] == "/") {
            b = int(St.top()); St.pop();
            a = St.top(); St.pop();
            St.push(a/b);
        }
        else {
            St.push(atoi(s[i].c_str()));
        }
    }
    return int(St.top());
}

int main()
{
    int n, l, t;
    string A[101], B[101];
    char s[101];

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        s[strlen(s)-1] = '\0';

        l = str2arr(s, A);
        t = Generate_RPN(l, A, B);

        cout << Calculate_RPN(t, B) << endl;
    }

    return 0;
}
# Convert string to list
def String2List(s):
    L = []
    flag = True
    l = len(s)
    for i in range(l):
        if s[i].isdigit() and flag:
            t = ""
            j = 0
            while s[i+j].isdigit():
                t += s[i+j]
                if i+j == l-1:
                    break
                j += 1
            L.append(t)
            flag = False

        elif not s[i].isdigit():
            L.append(s[i])
            flag = True

    return L

# generate Reverse Polish Notation
def Generate_RPN(L):
    S, L2 = [], []
    table = {"*": 1, "/": 1, "+": 0, "-": 0, "(": -1, ")": -1}
    for i in L:
        if i.isdigit():
            L2.append(i)
        elif i == "(":
            S.append(i)
        elif i == ")":
            while S[-1] != "(":
                L2.append(S.pop())
            S.pop()
        else:
            while len(S) != 0 and (table[S[-1]] >= table[i]):
                L2.append(S.pop())
            S.append(i)

    while len(S) != 0:
        L2.append(S.pop())

    return L2


def Calculate_RPN(L):
    St = []

    for i in L:
        if i == '+':
            St.append(int(St.pop()) + int(St.pop()))
        elif i == '-':
            St.append(-int(St.pop()) + int(St.pop()))
        elif i == '*':
            St.append(int(St.pop()) * int(St.pop()))
        elif i == '/':
            a = int(St.pop())
            b = float(St.pop())
            St.append(b/a)
        else:
            St.append(i)

    return St[0]


N = int(raw_input())

for i in range(N):
    s = raw_input()
    L = Generate_RPN(String2List(s[:-1]))
    print int(Calculate_RPN(L))

感想

やるだけなのにバグを埋め込みまくってコードを書くのにすごい時間がかかって辛かったです。あと一応AOJのシステムテストは通りましたが間違ってる可能性も大いにあるのでご注意ください。

AOJ0109: Smart Calculatorの他の人の解答を見てみたらみんな全然違う解き方をしていたのでみんなの解き方での実装もそのうちやりたいと思いました。

これ(https://gist.github.com/draftcode/1357281)とかめっちゃ参考になりそう。

参考文献

USBオーディオ変換ケーブルを買った。

PCに接続したヘッドホンの片側だけ音が聞こえなくなるということがあった。

別のヘッドホンに変えても同じ症状が起きたので、原因はヘッドホンの断線やプラグの酸化などではなくPCの差込口の方であることが分かった。

電子工作の心得があるわけでもないので自力で修理などできるはずもなく、新しいPCケースを買うのも面倒なのでしばらく放置していた。

中途半端にヘッドホンのプラグを差し込むと両方から聞こえる(ただしいくつかの音が明らかに抜け落ちている)という謎現象があったのでしばらくそれで我慢していたのだが、

USBの変換ケーブルなるものがあることを知り、試してみた。

BUFFALOの製品を買った。型番は BSHSAU01BK

価格は Amazon で 1,109 円だった。

 

f:id:kira000:20161115141640j:plain

 

https://www.amazon.co.jp/gp/product/B007WPMIN8/ref=oh_aui_detailpage_o00_s00?ie=UTF8&psc=1

使用した感じ不具合はないが、Amazon レビューなどによると、この製品に限らず USBオーディオ変換ケーブル全般に言えることとして、マイクにノイズが入るということがあるらしい。

自分は聞くだけなので関係ないけど、マイクも使う人は注意した方がいいと思う。

 

[追記]

後日談というか今回のオチ。

 

もしやと思ってマザーボードに接続されているオーディオのピンを一度抜いて、再びしっかりと差し込んだたら問題が解決した。

 

結局どこにも不具合は存在せず、ただマザーボード側のコネクタがしっかりささってなかったことが原因だったのだ。

冷静に考えるとまっさきに疑うべきポイントなんだよなぁ。

Pythonの組み込み実装のROT13を読む。

 アルファベットを任意の文字数ずらした暗号をシーザー暗号という。

シーザー暗号の中で13文字ずらしたものをとくにROT13と呼ぶ。

PythonではこのROT13が言語に組み込み実装として存在しており、thisモジュールはこのROT13でエンコードされている。

>>> print "hogefuga".decode("rot13")
ubtrshtn
>>> print "hogefuga".encode("rot13")
ubtrshtn
>>>

自明ではあるが上の出力でROT13においてはデコードとエンコードが同じ処理であることも確認できる。

組み込み実装として用意されているROT13のソースコードはthis.pyを見れば確認できる。

http://svn.python.org/view/python/trunk/Lib/this.py?view=markup

23 d = {}
24 for c in (65, 97):
25     for i in range(26):
26         d[chr(i+c)] = chr((i+13) % 26 + c)
27 
28 print "".join([d.get(c, c) for c in s])

23行目で空の辞書オブジェクトを生成している。

24行目ではついつい、

for c in (65, 97):

の部分を

for c in range(65, 97):

に空目してしまいがちだが

range()関数は使っていないので注意が必要。

65と97はASCII文字コードにおけるAaである。

chr()関数はASCII文字コードにおける整数を文字に変換する関数で、逆の処理をするのがord()関数。

  • chr()
>>> for c in (65, 97):
...   for i in range(26):
...     print chr(i+c),
...
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z
>>>
  • ord()
>>> for c in ('A', 'a'):
...   for i in range(26):
...     print ord(c)+i,
...
65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
>>>

26行目の

d[chr(i+c)] = chr((i+13) % 26 + c)

d['A'] = 'N'

d['B'] = 'O'

d['C'] = 'P'

...

のようなことをしており{'A':'N', 'B':'O', 'C':'P' ...(以下略)}という辞書を生成している。

13というのがずらす文字数で0から25の整数である変数iに13を足したものの剰余をとり65もしくは97を足してchr()関数を実行することで、うまくシーザー暗号を表現している。

この13をnにすることでより汎用性の高いプログラムになりそうである。

最後のprint "".join([d.get(c, c) for c in s])だが、

"".join()はリストから文字列への変換操作である。

>>> "".join(['h', 'o', 'g', 'e'])
'hoge'

リストは内包表記を使っている。d.get(c, c)はd[c]があればその値を返しなければcをそのまま返すという意味である。

>>> d = {'A':'N', 'B':'O',}
>>> d.get('A')
'N'
>>> d.get('N')
>>> d.get('N', 'N')
'N'

引数に文字列sと整数nをとり、文字列sをn文字シフトした文字列を返す関数caesar()は次のように書ける。

def caesar(s, n):
  d = {}
  for c in (65, 97):
    for i in range(26):
      d[chr(i+c)] = chr((i+n) % 26 + c)

  return "".join([d.get(c, c) for c in s])

例えばAOJのこの問題(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0017)の仕様に合わせるのであれば、

#!/usr/bin/env python2
# coding: utf-8

def caesar(s, n):
  d = {}
  for c in (65, 97):
    for i in range(26):
      d[chr(i+c)] = chr((i+n) % 26 + c)

  return "".join([d.get(c, c) for c in s])

while True:
  try:
    encrypt_txt = raw_input()
    for i in range(26):
      t = caesar(encrypt_txt, i)
      if  "the" in t or "this" in t or "that" in t:
        print t

  except EOFError:
    break

こんな風に使える。

場阿忍愚(バーニング)CTF write-up

はじめに

場阿忍愚(バーニング)CTFに出てた。

1628点とって105位だった。

解いた問題は以下の通り。簡単なのしか解けていない。

芸術と兵法術、諜報術は割愛。

id カテゴリ タイトル ポイント
101 練習 image level 1 10
111 芸術 ワットイズディス? 33
112 芸術 cole nanee? 55
121 二進術 壱萬回 100
131 解読術 image level 5 50
132 解読術 Ninjya Crypto 100
133 解読術 Decrypt RSA 200
152 解析術 情報漏洩 100
161 電網術 ftp is not secure. 50
162 電網術 ベーシック 75
173 諜報術 Akiko-chan 155
181 記述術 search_duplicate_character_string 100
183 記述術 Count Number Of Flag's SubString! 100
201 兵法術 将棋詰め壱 50
202 兵法術 将棋詰め弐 100
203 兵法術 将棋詰め参 150
204 兵法術 将棋詰め四 200

image level 1

問題文

フラグを探して奉り候

101-level001a.png
101-level001b.png
101-level001c.png
101-level001d.png

CTF始めての方は一回四つの画像ファイルをダウンロードして、何かフラグっぽい文字列が分かれば提出してみて下さい。
それでも駄目でしたら、この解き方(チュートリアル)をご覧下さい。

解法

次のような4つのpngファイルが与えられる。

f:id:kira000:20151124023919p:plain f:id:kira000:20151124023951p:plain f:id:kira000:20151124024003p:plain f:id:kira000:20151124024011p:plain

縦に並べれば、"START-YAMATO-SEC!!!"という文字列が読み取れる。

FLAG:START-YAMATO-SEC!!!

壱萬回

問題文

121-calculation

解法

問題のファイルをリンクを踏むなりwgetなりでダウンロードしfileコマンドをかけると、64ビットのELFファイルだとわかる。

仮想マシン上の64bit版のUbuntuでファイルに実行権限を付与して実行してみる。

kira@kira-VirtualBox:~/Downloads$ chmod +x 121-calculation
kira@kira-VirtualBox:~/Downloads$ ./121-calculation
9 % 8 = 1
1 / 10 = 0
3 / 3 = 1
2 + 8 = 10
9 % 9 = 0
7 % 2 = 2

gdbでmainを逆アセンブルすると、main+398のところで、FLAGを表示するであろうshowFlagという関数を呼んでいるのが分かる。

そこに処理を飛ばしてみるとFLAGが表示される。

kira@kira-VirtualBox:~/Downloads$ gdb 121-calculation
GNU gdb (GDB) 7.6.1-ubuntu

(中略)

(gdb) start
Temporary breakpoint 1 at 0x400660
Starting program: /home/kira/Downloads/121-calculation

Temporary breakpoint 1, 0x0000000000400660 in main ()
(gdb) disas
Dump of assembler code for function main:
=> 0x0000000000400660 <+0>:    push   %r15
   0x0000000000400662 <+2>:   push   %r14

(中略)

   0x00000000004007e9 <+393>: jmpq   0x4006c8 <main+104>
   0x00000000004007ee <+398>: callq  0x400920 <showFlag>
   0x00000000004007f3 <+403>: nopl   0x0(%rax,%rax,1)

(中略)

   0x0000000000400818 <+440>: retq   
   0x0000000000400819 <+441>: callq  0x4005e0 <__stack_chk_fail@plt>
End of assembler dump.
(gdb) jump *main+398
Continuing at 0x4007ee.
FLAG_5c33a1b8860e47da864714e042e13f1e
*** stack smashing detected ***: /home/kira/Downloads/121-calculation terminated
(以下略)

FLAG:FLAG_5c33a1b8860e47da864714e042e13f1e

image level 5

問題文

フラッグを探してください

131-mondai.zip

解法

与えらえたzipファイルを解凍すると、次のような9つのpngファイルがみつかる。

f:id:kira000:20160207144727p:plain

ファイル名がmd5ハッシュ値のようなので、Google検索とかしてみると元の値が分かる。

8f14e45fceea167a5a36dedd4bea2543 => 7
45c48cce2e2d7fbdea1afc51c7c6ad26 => 9
1679091c5a880faf6fb5e6087eb1b2dc => 6
a87ff679a2f3e71d9181a67b7542122c => 4
c4ca4238a0b923820dcc509a6f75849b => 1
c9f0f895fb98ab9159f51fd0297e236d => 8
c81e728d9d4c2f636f067f89cc14862c => 2
e4da3b7fbbce2345d7772b0674a318d5 => 5
eccbc87e4b5ce2fe28308fd9f2a7baf3 => 3

元の値の順番でファイルを並べると"KOUBE-GYU"という文字列が読み取れる。

FLAG:KOUBE-GYU

Ninjya Crypto

問題文

敵か仲間か? 証明して!

f:id:kira000:20160207160742j:plain

解法

忍者文字というものらしい。

http://iga-ueno.or.jp/ninjamoji/%E5%BF%8D%E8%80%85%E6%96%87%E5%AD%97%E3%83%95%E3%82%A9%E3%83%B3%E3%83%88/

ここのサイトを見ながら、デコードするとヤマトイエバとなる。

したがってFLAGは川

FLAG:

Decrypt RSA

問題文

133-Decrypt_RSA.zip

解法

与えられたzipファイルを解凍するとflag.txt, public-key.pem, READMEの3つのファイルが得られる。

opensslでn(=p*q)とeの値を取り出す。

$ openssl rsa  -text -pubin < public-key.pem
Public-Key: (640 bit)
Modulus:
    00:ae:5b:b4:f2:66:00:32:59:cf:9a:6f:52:1c:3c:
    03:41:01:76:cf:16:df:53:95:34:76:ea:e3:b2:1e:
    de:6c:3c:7b:03:bd:ca:20:b3:1c:00:67:ff:a7:97:
    e4:e9:10:59:78:73:ee:f1:13:a6:0f:ec:cd:95:de:
    b5:b2:bf:10:06:6b:e2:22:4a:ce:29:d5:32:dc:0b:
    5a:74:d2:d0:06:f1
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MGwwDQYJKoZIhvcNAQEBBQADWwAwWAJRAK5btPJmADJZz5pvUhw8A0EBds8W31OV
NHbq47Ie3mw8ewO9yiCzHABn/6eX5OkQWXhz7vETpg/szZXetbK/EAZr4iJKzinV
MtwLWnTS0AbxAgMBAAE=
-----END PUBLIC KEY-----

16進数を10進数に直して

#!/usr/bin/env python2
# -*- coding: utf-8 -*-

s = """
    00:ae:5b:b4:f2:66:00:32:59:cf:9a:6f:52:1c:3c:
    03:41:01:76:cf:16:df:53:95:34:76:ea:e3:b2:1e:
    de:6c:3c:7b:03:bd:ca:20:b3:1c:00:67:ff:a7:97:
    e4:e9:10:59:78:73:ee:f1:13:a6:0f:ec:cd:95:de:
    b5:b2:bf:10:06:6b:e2:22:4a:ce:29:d5:32:dc:0b:
    5a:74:d2:d0:06:f1"""

print int(s.replace(" ", "").replace(":", "").replace("\n", ""), 16)
n = 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609

http://factordb.com/index.php

に投げると素数p, qの値が分かる。

p = 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579

q = 1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571

あとはここ( http://d.hatena.ne.jp/kusano_k/20140323/1395571265)スクリプトを勝手に使わせてもらって、PRIVATE KEYを生成。

$ cat flag.txt | openssl rsautl -decrypt -inkey  private-key.pem
FLAG_IS_WeAK_rSA

FLAG:FLAG_IS_WeAK_rSA

情報漏洩

問題文

152-Leaked-Information.pcap

解法

与えられたpcapファイルをWiresharkで開くとUSBのパケットをキャプチャしたファイルだと分かる。

データのひときわ大きなパケットと前後二つのパケットを右クリックしてコピーしBinary Editor BZに貼り付ける。

ファイルのマジックナンバーを目印にして先頭の余分なバイト列を削除するとpngファイルが得られる。

f:id:kira000:20160207185318p:plain

FLAG:flag={gambare benesse}

ftp is not secure.

問題文

161-problem.pcap

解法

stringsコマンドで出てきた怪しげな文字列をbase64デコードすればFLAGが得られる。

$ echo RkxBR3tYVEluWDY5bnF2RmFvRXd3TmJ9Cg== | base64 -d
FLAG{XTInX69nqvFaoEwwNb}

FLAG:FLAG{XTInX69nqvFaoEwwNb}

ベーシック

問題文

162-basic.pcap

解法

pcapファイルをWiresharkで開くと何度かgetリクエストを送ってるのが分かる。

認証が成功した(200OKが返された)ときのgetリクエストを送ったパケットを見ると、

ユーザー名:http, パスワード://burning.nsc.gr.jpだと分かる。

ぱっと見た感じURIは見つからなかったけどおそらくhttp://burning.nsc.gr.jpにつなげばいいと推測がつくので、

そこにさっきのユーザー名とパスワードを使いアクセスすればFLAGが分かる。

FLAG:flag={BasicIsNotSecure}

Count Number Of Flag's SubString!

問題文

http://210.146.64.36:30840/count_number_of_flag_substring/

解法

GETリクエストの送り方や基本的な文字列操作ができれば、あとはやるだけ。

#!/usr/bin/env python2
#-*- coding: utf-8 -*-

import urllib, urllib2

FLAG = "flag={"
l = list("abcdefghijklmnopqrstuvwxyz_}")

while True:
  for i in l:
    FLAG += i
    url = "http://210.146.64.36:30840/count_number_of_flag_substring/?str=" + FLAG + "&count=count"
    req = urllib2.urlopen(url)
    s = "member of &quot;" + FLAG + "&quot; are 1"

    if i == '}':
      print "\n" + FLAG
      exit()

    elif s in req.read():
      print i,
      break

    else:
      FLAG = FLAG[:-1] #文字列のラストを削除
  • 実行結果
a f s f d s f d s f s o _ i d a r d k x a _ h g i a h r e i _ n x n k a s j d x _ h f u i d g i r e _ a n r e i a f n _ d s k a f i u d s u r e r f r a n d s k j n x x r
flag={afsfdsfdsfso_idardkxa_hgiahrei_nxnkasjdx_hfuidgire_anreiafn_dskafiudsurerfrandskjnxxr}

FLAG:afsfdsfdsfso_idardkxa_hgiahrei_nxnkasjdx_hfuidgire_anreiafn_dskafiudsurerfrandskjnxxr

search_duplicate_character_string

問題文

次のファイルに書かれている文字列の異なる2つの部分文字列s1, s2を考えた時、s1=s2となるもののうち、最も長いものを答えてください。

ただし、「sがSの部分文字列である」とは、0 <= k <= |S| - |s|であるようなある整数kを用いて、0 <= i < |s|なる全ての整数iについて、S[k+i] = s[i]が成り立つことを言います。

181-search_duplicate_character_string

解法

適当に実装した。

#!/usr/bin/env python2
# -*- coding: utf-8 -*-

with open("in.txt", "r") as file:
  strings = file.read()

strings_list = strings.split("\n") #行ごとに分けたリストを生成

tmp = FLAG = ""

maxnumber = 0

for i in range(len(strings_list)):

  for j in range(len(strings_list[i])):

    tmp += strings_list[i][j]

    if strings.count(tmp) == 1:
      tmp = tmp[1:] #先頭文字を削除

    if len(tmp) > maxnumber:
      maxnumber = len(tmp)
      FLAG = tmp

  tmp = ""

print FLAG

FLAG:f_sz!bp_$gufl=b?za>is#c|!?cxpr!i><

おわりに

受験まであと3週間切ったこの時期にやることじゃなかった。

原付免許をとった

 アルバイトでも始めようかと思ったのがきっかけだった。

バイトをはじめるにあたって良い機会だから、銀行口座を開設しようと思ってゆうちょ銀行の口座を作ろうとしたら、本人確認書類というものが必要らしく困った。

免許もパスポートも持ってないし、保険証もどこにあるのか把握していないとあってどうしたものかと思いGoogle先生を頼ったのだけれど、免許やパスポート、印鑑登録証明書などを新たに取得しようとすると、そのために身分証明書が必要だという。

住基カードは簡単に作れそうだと思ったら、マイナンバー制度による個人番号カードの交付開始に伴い、交付を終了するとのこと。

どうしたものかと思い、ゆうちょ銀行の本人確認書類一覧のページをながめていたら、母子健康手帳(母および子に限る)とあって、おそらくこれであれば家を探せばどこかにあるだろう踏んで家をあさってみたところ見つかったのでその日のうちに近所の郵便局へ行って無事口座開設できた。

ゆうちょ銀行に口座開設する際に必要だったものは次の3点。

これで当初の目的は果たせたのだけれど、身分証明書がなければ何かと不便であると分かったので、この際作ってしまおうと思い比較的容易に取得できそうな原付の免許でもとろうかと考え調べてみると、どうやら住民票の写しと学生証が必要なようだった。

学生証に関しては問題ないとして、住民票の写しはどうやって入手すればいいのか調べたところ、私の住んでる自治体の場合は学生証と預金通帳の2点があれば市役所等で取得可能だとのこと。

住民票の写しを手に入れる際に必要だったものは次の3点。

  • 学生証

  • 預金通帳

  • 手数料(300円)

住民票の写しを手に入れて、後日運転免許試験場に赴き原付免許の試験を受けてだるい講習を経て免許を取得した。

原付の免許を取得するのに必要だったものは次の通り。

  • 住民票の写し
  • 学生証
  • 手数料(合計7,750円)
  • 写真(縦3cm×横2.4cm)
  • 両眼で0.5以上の視力
  • 16歳以上の年齢
  • 学科試験を合格できるだけの知識

学科試験対策はスマホのアプリを主に利用した。下記のアプリがクオリティ高くてよかった。

無料1210問!原付免許問題集! - Google Play の Android アプリ

余談だけど視力検査で2回再検査になって辛かった。なんとか1.0までには回復させたい。