CPCTF参加記その2

2025/04/25

とりあえずLV.1から解いてみよう

着実に点数を取ることは大切です。大会の難しさや雰囲気も大体一番簡単な問題を解くことでわかるので。45^2は前回の記事で解いたので、今回はHeroic Code、Luke or Bishopについて、解説を行います。

Heroic Code

まずはジャンルを見てみましょう。この問題はCryptoというジャンルの問題だそうです。Cryptoは主に暗号についての問題となっており、当たり前ですが暗号系の知識を要します。さて、実際に問題を見てみると、何やらただただ暗号文が載せられているだけで、一見すると何もヒントがないように見えますね。

しかし、最後に何やら怪しい文字列があります。SFSJV{qbuq_zqsjq_uij}、何か見たことがあるような気がする文字列ですね。そうCPCTF{flag}の形にものすごーく似ています。ただ、どうやってここから暗号を解けばいいのでしょうか？困ったらそこで止まらず、とりあえずgoogleのお世話になりましょう。

Google先生教えて

適当に「暗号　CTF」で検索をかけてみると、かなりの量の情報が出てきます。今回は解くことを念頭に置いて、暗号の種類と実際の暗号文を照らし合わせながら、それっぽいものを探してみましょう。RSA暗号、XORなどなど色々ありますが、どれもそれっぽくありません。もう少し調べてみると、シーザー暗号というものが、CTFの初心者向けの問題としてかなり出る上、暗号文の例を見てもそれっぽいようです。「シーザー暗号」で検索をかけてみると、復号ツールもあるようなのでこれを使ってみましょう。

もとに戻す

今回はCyberChefのツールを使って、復号してみましょう。(リンク先はROT13 Brute Forceという、シーザー暗号に対する総当たり攻撃を行うものになっています。総当たり攻撃については下に別で解説しています。)

Inputの部分に暗号文を渡してみると、下のOutputに「Amount = (数字): (文章)」のようにたくさん表示されています。ほとんどが意味のないような文章ですが、よーく目を凝らしてみると...？

シーザー暗号ってなんだよ

さて、答えもわかったところで今回使われたシーザー暗号について少し深掘りしましょう。この暗号は0~25(または1~26)の数字を「鍵」として、暗号化する古典的な暗号方式の一種です。暗号化の手順について簡略に説明すると、「元の文を一文字ずつ見てった時、A~Zにそれぞれ1~26の番号を振り(A=1, B=2, ... Z=26)、その後鍵の分だけ数をずらし(鍵が5なら+5する、A=6, B=7, ... Z=31)、最後にmod 26を取った数(A=6,B=7, ... Z=5)が暗号化した後の文字の番号となる(A=6なので、6番目のアルファベットはF、よってAはFに置き換わる)」ものです。(わかりづらいかも、わからない場合はwikiを参照)

復号するときは逆をすればいいでしょう。つまり、ずらす文字数の方向を逆にする、または別の言い換えとして鍵の値の正負を逆にして再度暗号化すれば、復号することが可能です。

このように、暗号には暗号化するときと復号するときのための「鍵」が基本的に必要です。(ハッシュ関数などは例外！気になる人は調べてみよう)

鍵について考えましょう。鍵はその名の通り、宝箱を思い浮かべると簡単ですが、宝箱にロックをかける時と、そのロックを外すときに必要で、これは暗号化と復号に対応しています。本来、鍵は複雑でないといけません。皆さんのスマホのパスワードも最低でも4桁の数字が設定されているでしょう。これは、仮にパスワードが1桁の数字だったら、0~9を試す、つまりたったの10回であなたの秘密がバレてしまうという、ほぼ意味のないものになってしまうからです。今回の暗号についてみてみると、取りうる鍵の数は0~25のたったの26個しかありません。つまり、26個全部試せば正解が現れる可能性があるということにもなります。この方法は**Brute Froce(総当たり攻撃)**と言われ、とりあえず全部試せばいいやという脳筋思考から成り立つ最も簡単な攻撃方法になります。

今回は簡単のため、この手段を使いましたが、SFSJV{~}とCPCTF{~}の部分を比べるとCがSに変わっていそうという予想から、C=3,S=19より、鍵は16であるという予想をつけることもできます。これを対策するにはどうすればいいでしょうか？そこで考えられたのはヴィジュネル暗号というものです。...と、これ以上は長くなり過ぎてしまうので一旦ここでこの問題は終わりにしましょう。暗号や乱数はかなり奥が深いので沼にハマらないようにしましょう。

Luke or Bishop

まずは問題を見てみましょう。この問題はチェスのコマの一つである、ルークとビショップの動きを使って、一定の位置に動くためには最低何手必要か？という問題になっています。変に難しく考えず、動きが素直なルークだけを使った場合を考えてみると、結局どの位置にも2手以内で行けることがわかります。((0,0)→(x,0)→(x,y)の順番でいけばいい)

また、仮にxまたはyが0ならばそれこそ1手でいけることもわかります。

しかし、ビショップのことも考えないといけません。が、先ほど2手でどこでも行けるとわかっているので、それより少ない1手でいける場合を考えればいいでしょう。ビショップが1手で動ける場合は|x|=|y|であるので、これらで条件分けすればうまくいきそうです。

ここまでの条件を整理すると、

  • (0,0)が行き先ならば0手
  • x,yのいずれかが0ならばルークで1手
  • |x|=|y|ならばビショップで1手
  • それ以外なら2手

よって、これをプログラムで再現すると、

// C++
#include <iostream>

int main() {
  long long x, y;
  cin >> x >> y;
  if (x == 0 && y == 0) {
    cout << 0 << endl; // 行き先がどちらも0
  } else if (x == 0 || y == 0) {
    cout << 1 << endl; // 行き先のxかyが0
  } else if (x == y || x == -y) {
    cout << 1 << endl; // 行き先のxとyの絶対値が等しい
  } else {
    cout << 2 << endl; // それ以外
  }
  return 0;
}

xy = input()
xy_spl = xy.split()
x = int(xy_spl[0])
y = int(xy_spl[1])
if (x == 0 and y == 0):
  print(0)
elif (x == 0 or y == 0):
  print(1)
elif (x == y or x == -y):
  print(1)
else:
  print(2)

コードについて詳しく説明するのもアレなので、わからない部分があった場合、以下のキーワードを残しておきます。おそらくこの問題では型というものにつまづく方が多いと思います。

言語関係なし共通事項

  • if else文 (文中if, else if(elif), elseについて)
  • 条件分岐 (x=0の時など条件で分岐を行いたいときについて)
  • 論理式 (x=0の時、x=0かつy=0の時などを表したいときについて)
    • fizzbuzz (上のやつが終わったらやってみるといいかもしれない課題)
  • 標準入力 (1 2のように入力されるとき、どのように値を変数に入れるかについて)

C++の方へ

  • long long型 (非常に大きい数を使うときについて)

Pythonの方へ

  • 型キャスト (見た目が同じでも内部的に違うものについて)

次回予告

次回は残りのLV.1について全て解説します。今回かなり飛ばし気味でごめんなさい。

ブログ一覧に戻る