nkhrlab challenge 2019 想定解法

はじめに

この記事は，2019/1/1 0:00より主催したCTF「nkhrlab challenge 2019」の解説記事である．

セキュリティ要素のないCTF
nkhrlab challenge 2019を
1/1 0:00より開催しています

正解者のうち先着3名にはAmazonギフト券でお年玉があります
1着 3072円
2着 2048円
3着 1024円

ご参加ください

https://t.co/fJeMcjfSxd
— nkhrlab (@nkhrlab) 2018年12月31日

nkhrlab challenge 2019 結果

🗻1着こおしいず様 (@kcz146) 1/1 2:28
🦅2着 keymoon 様 (@kymn_) 1/1 4:36
🍆3着りふれ様 (@refle_det) 1/1 4:57

他にも多くの方々にチャレンジしていただきました，ありがとうございました！良い一年になりますように！
— nkhrlab (@nkhrlab) 2019年1月1日

次のリンクから問題用のファイルをダウンロードできる．問題用のファイルとサーバは少なくとも2019/1/10 23:59まで有効である．
www.dropbox.com

以下，問題の解法を解説する．

問題

ダウンロードしたzipファイルを展開すると，次のような構造になる．

nkhrlab_challenge_2019
├── final.c
├── key01
├── key02
├── key03
├── key04
├── key05
├── key06
├── key07
├── key08
├── key09
├── key10
├── key11
├── key12
├── key13
├── key14
├── key15
├── key16
├── key17
└── key18

また，final.cの内容は次のようになっている．

#include <stdio.h>

int main(void)
{
  char a[19] = {};
  int t[40] = {1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10, 4, 5, 6, 17, 11, 12, 8, 13, 7, 1, 14, 9, 14, 5, 9, 17, 15, 9, 16, 17, 10, 18, 11, 4, 7, 8, 11, 1, 18};

  for(int i = 1; i <= 18; i++)
  {
    printf("input answer for key%02d >>> ", i);
    scanf(" %c%*[^\n]", &a[i]);
    if('A' <= a[i] && a[i] <= 'Z')
    {
      a[i] += 'a' - 'A';
    }
  }

  printf("http://3.112.2.176/?key=");
  for(int i = 0; i < 40; i++)
  {
    printf("%c", a[t[i]]);
  }
  printf("\nkeyが誤っていた場合，約3分間の間アクセスが遮断されます．\nご注意ください．\n");


  return 0;
}

final.cの内容を見ることから，key01からkey18までの18個の小問題の答えを取得し，final.cをコンパイルして得られるプログラムに入力すると出力されるURLにアクセスすることで次のステップへ進むことができると考えられる．

以下，18個の小問題の解説を行う．

key01

内容は次のようになっている．

# plot [0:100][-200:0] 'key01' with lines
71 -40
23 -44
24 -102
46 -89
69 -105
70 -157
43 -174
26 -153

1行目のコマンドをgnuplotに入力する．

gnuplot> plot [0:100][-200:0] 'key01'  with lines

すると，次のような図形が表示される．

key01の答えは「5」である．

key02

内容は次のようになっている．

Vm0wd2QyUXlVWGxWV0d4V1YwZDRWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhh
MUpUVmpBeFYySkVUbGhoCk1VcFVWbXBCZUZZeVNrVlViR2hvQ2sxVmNGVldi
WEJDWlVaWmVWTnJWbFZpUjJodlEyc3hWbU5HVmxkaAphMHBvVlhwS1UxTkdX
bkphUm1ocFVtNUNkMUV5ZUdGU01XUjFZa1prYVFwWFIyaFlWMnhXWVZkdFZs
ZFYKYmtwcFVqTkNWRmxzWkc5a2JFVjVZek5vV0ZaclducFZiWGh2Vm5kd2FW
WnJWak5XYkdoM1V6RlNkRlpyClpHb0tVbGQ0VkZsclZuZGpSbFowWlVoa1dG
WnJWalZVVmxZd1ZqSkdObEpyY0ZwV1ZuQnlXVlpHZDFkRwpTbFpqUlhCWFlr
ZG9NMVY2UmxOa1JscHpDbHBHVlV0WmJYUjNWMFpzY2xkdFJtcFNiRnA0VlRJ
d05XRXkKU2taV2FsWmFaV3MxZGxacVNrdFdhelZXWVVaa2FWZEhhSGxYVmxw
SFpERmtSd3BUYkZwcVVsaENXRmxyClpHOU5NVlkyVW14YWJGSnNTbmxEYkhC
SFdqQjBXbUpZVWpOV01GcHpZMnhhZFZwSGNGTmlTRUkyVm1wSgpNV0V4V1hn
S1YyNUtWMkZzV21oV2JGcDNUVEZzY2xkc2NHdE5WMUo1V1RCYWQyRkZNVmxS
Ym14WVZteHcKU0ZwRVJscGxRWEJVWWtkU1dGbFhjekZYUm14WUNtUkhSbWhT
YlhoV1ZXMTRUMkV4U25OalNIQkVZa2hDClNGWXhWakJYYlVwWlZXcE9WMDFH
Y0hwWk1uaGhaRlp3U0dOR1RtbFNiVGt6VmpKNFZ3cGlNa1Y0V2tWagpTMVl5
TlV0V01rWnpWMnhhVjJKWWFHRmFSRVpoWTJ4a2RGSnRjR2xTTVVsNFYxUkNZ
VmxYUmxkYVJXaG8KVTBkNFdWWnRlSGNLVTBad1JWSnNjR3hSV0VKVldXdGtV
Mkl4VWxWVGFsSllVbXhLV1VOck5WaFBWbWhUCllsWktXVll5ZEZkWlYwcEhV
MjVPVkdKdGVFVlphMmhEQ2xOR1pIRlJha0pZWWxWd1dsWlhjRTlYYXpGSApZ
MFpvV2sxV2NGQlpNVnBYWXpGd1IxUnRiRmhTTW1ONVZtMHhkMU4zY0U1U1ZF
WkpWV3hvYWdwVE1WSlgKVjIxR1YwMXJXbnBXTWpGdlZqSktTRlZzVWxaTlJu
Qm9WbXhhUjFkWFJrZGhSazVwVW01Qk1GWnNZM2hPClIxRjVVbXRhVGxadGVG
TUtXVmQwZDFkR2JITlZiR05MV1RKNGQxSldUbkphUm1SclRUQktXbGRYTVRC
awpNV1JIWWtab2FtVnJXbGxWYlRFMFpWVk9jMk5GYUZCV1ZGWlBDbFp0ZUhK
bFZscFlUVlJTV2xZd2NFaFYKTWpWVFZtMUtTVkZyVmxwaVJscG9RMnhPUjFk
c1pGZGhhMHBaV1d4V2QxZHNiRlphUnpsWFRXdHdXZ3BaClZXaDNWMjFXY2xk
cVRsWmlSbkJZV1hwR2QxSXhVblJpUm1oVFRXeEdObFp0Y0V0TlJsb3pZMFpr
VGxKRgpXa2xXYWtreFZHZHdWRTFXVmpVS1ZHeFdNRll3TVhKWGJuQlhUV3BH
ZGxacVNrdFNNazVJVW0xR1UxSlcKY0RaV2FrSnJWRzFXZEZKcmFHcFNNbWh6
V1d0YWQxZFdXWGhYYkdSYUNsWnRlRmxWYlhocldWWktXR0ZICk9FdFdWRUpy
VGtaa1YxZHVVbXhUUjA1TVZsUkNZV1F4U2xkVGJsSnJVbXMxY2xSVVFrdFdi
RnB4VVcxMApUd3BTTUd3MFZteG9hMWRIU25SVmJHeFdZbFJGTUZwV1ZrOWpN
azVHWVVaQ1YxWkdXbEJEYkZwMFpVaGsKVDFKc2NGbFVWVkpIVmxVeFdGVnJh
RllLVFdwV1VGWnJaRWRqYkdSeVZteHdhRTFXVmpSUk1qRlhWakZXCldWcEda
R2hoTUhCWlZrWmtNR1F4V25OV2JsSnNVbXMxV1ZsWWNFZFRRWEJhQ2sxR2NI
WlhWbHBMVmpGYQpjVlZzWkdoaE1YQlZWMnRXYTFReFNYaFZibEpwVW1zMWNG
WnJaREJPYkZwMFRWUkNhRTFFVmtOWk1GcHIKVkd4YWNncFhWRUpYWVd0YWRs
bHRaSGRXUlRGWFlrUlZTMVpIZUZkTlJsbDNUVmhLV0dKdVFsaFVWelZ2CllV
WmFjVk5yZEZoV01GcEpWVzB4UjFVeFNsY0tZMGM1VjJKWWFHaFdSRXBQWkVa
V2NscEdXbWxTVkZaMwpWbGN3TVZGck1YTlhXR2hXWVRBMVlVTnNXWGhTYWxK
WFZucFdVRlpyWkV0ak1XUnpDbFJWZEZoV2VrSTAKVkd0YWExSXlTa2xVYkZw
cFVqQTFUVll4VWt0T1IxRjRVMnhrVkdKck5WbFpiR2h2VlRGWmQxWnJkRmhp
ClIxSllWbGQwTUFwV1ozQk9WakZLV1ZkWGRHRmlNa3BIVTFoa1dHSkhlRmRa
YkdodlZFWlplRlpyT1dwaAplbFpZVjJ0YVYyRldaRVpUYm1SRVlrWmFNRnBG
YUdzS1ZERmFjMk5JYUZaTmJrSkVWako0V21ReVRrWmgKUmxsTFZGZHdWMVZH
YkZobFJYUlRZa2RTZVZadGVIZGhSVEZaVVcwNVVrMXFSbGhaZWtackNtTXhj
RWRhClIyaG9UVWhDWVZZeFpEQlpWMDEzVGxoT2FWSnNjRmRaV0hCelYwWlNW
MVp1WkZOa00wSllRMnN4ZFdGSQpXbGROYWtaWVdUSXhUd3BTYlVaSFYyMXNX
RkpVUWpSV2JURjNVakZzV0ZSWWFGWmlhelZvVlcweFUxWkcKYkhKYVJFNU9V
bXh3TUZSV1VsTldNREZZWlVaT1drMUdjR2dLV1ZaYVlXTm5jRmhXUlVwWVdW
UktVMDB4CldraGFTR1JYVWxSR1dWcFZVa1pUTVdSWVkwVTVhRTFXY0VsV1Zt
aHpWVVpLU0dWRlZsaGliVGt6Q2xReApWazlpYkVKVlRVVnpTd289Cg==

ファイルに含まれる文字の種類と末尾部分の特徴から，これはbase64文字列であると予想できる．この文字列をデコードすると，より短いbase64文字列が得られる．それをデコードすると，さらに短いbase64文字列が得られる．これを繰り返すと，最終的に1文字が残る．その文字は「2」である．

key02の答えは「2」である．

key03

内容は次のようになっている．

\documentclass{jsarticle}
\begin{document}
\begin{eqnarray*}
\sum_{k = 0}^{\infty} \frac{1}{k!}
\end{eqnarray*}
\end{document}

$\LaTeX$ でコンパイルすると， $\displaystyle \sum_{k = 0}^{\infty} \frac{1}{k!}$ のようになる．この無限級数は自然対数の底 $e$ に収束する．すなわち， $\displaystyle \sum_{k = 0}^{\infty} \frac{1}{k!} = e.$

key03の答えは「e」である．

key04

ヘッダを確認すると，このファイルがWAVフォーマットであることがわかる．key04.wavにリネームしたこのファイルを音声として再生すると，「zero」と聞こえる．

key04の答えは「0」である．

key05

ヘッダを確認すると，このファイルがBMPフォーマットであることがわかる．key05.bmpにリネームして開くと，一見真っ白な画像が表示されるが，実はとても薄く文字が書かれている．単純な塗りつぶしツールを使うと，「d」の文字が現れる．

key05の答えは「d」である．

key06

ヘッダを確認すると，このファイルがMicrosoft Excelのワークシート(xlsx)であることがわかる．Excelで開くと，セルA1に「1」と表示されたワークシートが表示される．

key06の答えは「1」である．

key07

内容は次のようになっている．

a = []
z = 0
for i in 0...10000000
  z = (7 * z + 10007) % 1000000007
  a.push(z)
end

for i in 0...9999999
  for j in 0...(9999999 - i)
    if a[j] > a[j + 1]
      a[j] ^= a[j + 1]
      a[j + 1] ^= a[j]
      a[j] ^= a[j + 1]
    end
  end
end

p a[5000000] % 10

このファイルはRubyのスクリプトファイルである．しかし，このファイルをそのまま実行しても時間がかかりすぎてしまう．そこで高速化を施す．

このファイルの中ほどにある2重ループの処理はバブルソートと呼ばれるソートアルゴリズムを実装したもので，低速であることで知られている．そこで，これをRuby標準のソートに置き換えて次のようにする．

a = []
z = 0
for i in 0...10000000
  z = (7 * z + 10007) % 1000000007
  a.push(z)
end

a.sort!

p a[5000000] % 10

これを実行すると「8」と出力される．

key07の答えは「8」である．

key08

内容は次のようになっている．

*****,*****,*****,*****,*****,*****,*****
*****,*****,*****,*****,*****,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
*****,*****,*****,*****,*****,*****,*****
*****,*****,*****,*****,*****,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
,,,,,*****,*****
*****,*****,*****,*****,*****,*****,*****
*****,*****,*****,*****,*****,*****,*****

CSVファイルとしてExcelなどで開くと，「*****」が入力されたセルが「3」の形に並べられて表示される．

key08の答えは「3」である．

なお，テキストとして表示すると「E」と紛らわしいという意見があった．今後はこのようなことがないようにしていきたい．

key09

ヘッダを確認すると，このファイルがMicrosoft PowerPointのプレゼンテーション(pptx)であることがわかる．

PowerPointで開くと，次のようなスライドが表示される．
f:id:nkhrlab:20190101142818p:plain

この回路図では，電源電圧 (16 V) と回路に流れる電流 (0.3 A) が明示されているので，回路全体の合成抵抗がオームの法則によりわかる (53.3 Ω)．「?」で隠されている部分の配線の選択肢 (a 〜 f) のうち，合成抵抗が条件に合うものは「c」のみである．

key09の答えは「c」である．

key10

内容は次のようになっている．

       IDENTIFICATION DIVISION.
       PROGRAM-ID. NKHRLAB-CHALLENGE-2019.

       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
           SELECT STDIN ASSIGN TO KEYBOARD ORGANIZATION LINE SEQUENTIAL.
       DATA DIVISION.


       FILE SECTION.

           FD STDIN.
           01 LN PIC X(65535) USAGE DISPLAY.
             88 EOF VALUE HIGH-VALUES.

       WORKING-STORAGE SECTION.

           01 N PIC 9(18) USAGE COMP.
           01 I PIC 9(18) USAGE COMP.
           01 Z PIC 9(18) USAGE COMP.
           01 D PIC 9(18) USAGE COMP.
           01 NOUT PIC Z(17)9 USAGE DISPLAY.

       PROCEDURE DIVISION.

           MAIN-PROCEDURE.
           MOVE 9999973 TO N
           PERFORM VARYING I FROM 0 BY 1 UNTIL I >= 10000000000000000
             DIVIDE N BY 2 GIVING Z REMAINDER D
             IF D = 0 THEN
                 DIVIDE N BY 2 GIVING N
             ELSE
                 MULTIPLY N BY 3 GIVING N
                 ADD 1 TO N
             END-IF
           END-PERFORM.

           MOVE N TO NOUT
           DISPLAY NOUT
           CLOSE STDIN

           STOP RUN.

       END PROGRAM NKHRLAB-CHALLENGE-2019.

COBOLで書かれたプログラムであるが，そのまま実行しても時間がかかりすぎてしまう．その原因はコードの後半にある $10^{16} - 1$ (約1京)回のループである．

ループ内の処理は，Nが奇数ならばNを3N + 1に更新し，偶数ならばN / 2に更新するという内容である．この処理を処理Cと呼ぶことにする．

とりあえず，ループ回数を次のように減らして様子を見てみよう．

PERFORM VARYING I FROM 0 BY 1 UNTIL I >= 100000

すると，「1」が出力される．すなわち，処理Cを $10^{5} - 1$ 回行うと，最終的にNの値は1になる．

Nの値が1の状態で処理Cを行うと，Nは奇数なので，Nの値は4に更新される．Nの値が4の状態で処理Cを行うと，Nは2に更新され，さらにもう一度処理Cを行うと，Nの値は1に戻る．このことから，Nの値が1の状態から3回処理Cを行った後のNの値は1である．さらに一般化すると，Nの値が1の状態から $3n\;\;(n \geq 1)$ 回処理Cを行った後のNの値は1である．

つまり，Nの値が1になったあと，処理CによってNの値は次のようにループする．
$1 \xrightarrow{C} 4 \xrightarrow{C} 2 \xrightarrow{C} 1.$

Nの値が9999973の状態から処理Cを $10^{16} - 1$ 回行うことは，Nの値が9999973の状態から処理Cを $10^{5} - 1$ 回行い，さらに $10^{16} - 10^{5}$ 回行うことと同値である．Nの値が9999973の状態から処理Cを $10^{5} - 1$ 回行ったあとのNの値は1だから，これはNの値が1の状態から処理Cを $10^{16} - 10^{5}$ 回行うことと同値であるといえる． $10^{16} - 10^{5} = 9999999999900000$ は3の倍数だから，このプログラムが最後に出力するNの値は1であるといえる．

key10の答えは「1」である．

key11

ヘッダを確認すると，このファイルがZIP圧縮されていることがわかる(key11.zip)．展開にはパスワードが必要である．パスワードを総当たりで求めると，パスワードが「1」であるとわかる．これでこのファイルが展開できる．

すると，このファイルの中から新たなパスワード付きZIPファイル(key11_2.zip)が得られるので，key11_2.zipのパスワードも総当たりで求めると，パスワードが「1」であるとわかる．

さらに，key11_2.zipの中からパスワードのついたkey11_3.zipが得られるので，key11_3.zipのパスワードも総当たりで求めると，パスワードが「2」であるとわかる．

こうして，次々と得られるZIPファイルのパスワードを解析し，ファイルとパスワードの対応を列挙すると，次のようになる．

key11.zip   : 1
key11_2.zip : 1
key11_3.zip : 2
key11_4.zip : 3
key11_5.zip : 5
key11_6.zip : 8
key11_7.zip : 13
key11_8.zip : 21
key11_9.zip : 34
...

パスワードがフィボナッチ数列になっていると推測すると，この後に得られるZIPファイルのパスワードも推測できる．こうして合計100回ほど展開すると，「6」と書かれた画像が得られる．

key11の答えは「6」である．

key12

内容は次のようになっている．

WITH t(a, i) AS
(
  SELECT
    GENERATE_SERIES(0, 15), 
    INET('192.168.99.' || (10 + 7 * GENERATE_SERIES(0, 15)))
)
SELECT
  TO_HEX(a)
FROM t
  WHERE i << INET('192.168.99.120/28')

これはPostgreSQLで実行できるSQL文である．実行すると，「f」と出力される．

key12の答えは「f」である．

key13

ヘッダを確認すると，このファイルがPNG画像であることがわかる．key13.pngにリネームして開くと，「a」と書かれた画像が表示される．

key13の答えは「a」である．

key14

ヘッダを確認すると，このファイルがPDF文書であることがわかる．key14.pdfにリネームして開くと，次のような内容が表示される．
f:id:nkhrlab:20190101153320p:plain

文章中の指示どおり，次のように定義される数列の一般項を求める．
$\begin{eqnarray}a_1&=&1.\\a_{n+1}&=&6a_n+3b_n+5\times 2^n.\;\;(n \geq 1)\\b_1&=&1.\\b_{n+1}&=&2a_n+5b_n+2^{n+1}.\;\;(n \geq 1)\end{eqnarray}$

解法1 (2018年度高等学校学習指導要領の範囲で)

やや技巧的で手数も多い問題．この解法を採用した場合は18個の小問題のうちで最も時間がかかる可能性が高い．

2つの漸化式の両辺を $2^{n+1}$ で割り整理すると次のようになる．
$\begin{eqnarray}\frac{a_{n+1}}{2^{n + 1}}&=&3\frac{a_n}{2^n}+\frac{3}{2}\frac{b_n}{2^n}+\frac{5}{2}.\;\;(n \geq 1)\\ \frac{b_{n+1}}{2^{n+1}}&=&\frac{a_n}{2^n}+\frac{5}{2}\frac{b_n}{2^n}+1.\;\;(n \geq 1)\end{eqnarray}$
$\displaystyle \frac{a_n}{2^n} = a'_n, \frac{b_n}{2^n} = b'_n$ と置き換えると，次のようになる．
$\begin{eqnarray}a'_{n+1}&=&3a'_n+\frac{3}{2}b'_n+\frac{5}{2}.\;\;(n \geq 1)\\ b'_{n+1}&=&a'_n+\frac{5}{2}b'_n+1.\;\;(n \geq 1)\end{eqnarray}$

これらの式から $a'_{n+1} + b'_{n+1}, 2a'_{n+1} - 3b'_{n+1}$ を計算し，次のように変形する．
$\begin{eqnarray}a'_{n+1} + b'_{n+1} + \frac{6}{7}&=&4\left(a'_n+b'_n+\frac{6}{7}\right).\;\;(n \geq 1)\\ 2a'_{n+1} - 3b'_{n+1} + 4&=&\frac{3}{2}(2a'_n-3b'_n+4).\;\;(n \geq 1)\end{eqnarray}$

こうして，数列 $\displaystyle \left(a'_n + b'_n +\frac{6}{7}\right), (2a'_n-3b'_n+4)$ がそれぞれ公比 $\displaystyle 4, \frac{3}{2}$ の等比数列であることがわかる． $\displaystyle a'_1 = b'_1 = \frac{1}{2}$ であることと合わせて，これらの数列の一般項は次のように表せる．
$\begin{eqnarray}a'_n + b'_n&=&\frac{13}{24}\times 4^n - \frac{6}{7}.\;\;(n \geq 1)\\ 2a'_n - 3b'_n &=&\frac{7}{3}\times \left(\frac{3}{2}\right)^n - 4.\;\;(n \geq 1)\end{eqnarray}$

これらの式を連立して $a'_n, b'_n$ について解くと，次のようになる．
$\begin{eqnarray}a'_n &=&\frac{13}{40}\times 4^n + \frac{7}{15} \times \left(\frac{3}{2}\right)^n - \frac{3}{2}.\;\;(n \geq 1)\\ b'_n &=&\frac{13}{60}\times 4^n - \frac{7}{15} \times \left(\frac{3}{2}\right)^n + \frac{2}{3}.\;\;(n \geq 1)\end{eqnarray}$

したがって， $a_n, b_n$ の一般項はそれぞれ次のようになる．
$\begin{eqnarray}a_n &=&\frac{13}{40}\times 8^n + \frac{7}{15} \times 3^n - \frac{3}{2} \times 2^n.\;\;(n \geq 1)\\ b_n &=&\frac{13}{60}\times 8^n - \frac{7}{15} \times 3^n + \frac{2}{3} \times 2^n.\;\;(n \geq 1)\end{eqnarray}$

key14の答えは，0〜9のうちこの一般項の表式に現れていない数字である．したがって，key14の答えは9である．

解法2 (行列の力を借りて)

行列を用いる場合，解法1に比べて易しい解法が存在する．

文章中に示された漸化式を次のように変形する．
$\begin{eqnarray} \begin{bmatrix}a_{n + 1} \\ b_{n + 1} \\ 2^{n + 1}\end{bmatrix} = A\begin{bmatrix}a_n \\ b_n \\ 2^n\end{bmatrix}, A = \begin{bmatrix}6 & 3 & 5 \\ 2 & 5 & 2 \\ 0 & 0 & 2\end{bmatrix}. \end{eqnarray}$
行列 $A$ を対角化すると，次のようになる．
$\begin{eqnarray}P^{-1}AP = \begin{bmatrix}8 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 2\end{bmatrix}, P = \begin{bmatrix}3 & 1 & -9 \\ 2 & -1 & 2 \\ 0 & 0 & 6\end{bmatrix}.\end{eqnarray}$
$n \geq 2$ に対して，
$\begin{eqnarray}\begin{bmatrix}a_n \\ b_n \\ 2^n\end{bmatrix} &=& A^{n - 1} \begin{bmatrix}a_1 \\ b_1 \\ 2^1\end{bmatrix} \\ &=& P(P^{-1}AP)^{n - 1}P^{-1}\begin{bmatrix}1 \\ 1 \\ 2\end{bmatrix} \end{eqnarray}$
を計算することで，解法1と同様の結論を得る．

解法3 (あの)

Wolfram Alphaで解けたとの報告があった．すごい！

key15

内容は次のようになっている．

解ける15パズルを1つ選べ

見本
  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15 --

a
 11  7 10  1
  8 12  2  9
 13 14  3  4
  5  6 15 --

b
 14 15  8 12
  2  3 10  6
 11  5 13  9
  1  4  7 --

c
  6  3 14  5
 12 13 10  1
  8  7  4  2
  9 11 15 --

d
  1 15  2  8
 10  4 11 13
 12  5 14  6
  7  9  3 --

e
  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 15 14 --

f
  8  1 13  9
 10  3  4  7
 12  2 14 15
 11  6  5 --

伝統的な15パズル6面のうち解くことが可能なものを選ぶ問題．自力で解いてもよいが，ソルバを利用するのが簡単であろう．

解くことができるのは「b」だけなので，key15の答えは「b」である．

key16

ヘッダを確認すると，このファイルがGIF画像であることがわかる．key16.gifにリネームして開くと，「b」と書かれた画像が表示される．

key16の答えは「b」である．

key17

内容は次のようになっている．

import java.io.IOException;

public class Main
{
  public static void main(String[] args) throws IOException
  {
    System.out.println(t(400, 200, 50) / t(40, 20, 50));
  }

  public static int t(int x, int y, int z)
  {
    return x <= y ? y : t(t(x - 1, y, z), t(y - 1, z, x), t(z - 1, x, y));
  }

}

このファイルはJavaのソースコードである．しかし，このファイルをそのまま実行しても時間がかかりすぎてしまう．そこで高速化を施す．

関数tは呼び出し時の引数が同じ場合には常に同じ返り値を返すから，メモ化をすることで高速化ができる．もしくは，竹内関数 - Wikipediaを参照する．

高速化を施した後にこのコードを実行すると，「8」が出力される．

key17の答えは「8」である．

key18

ヘッダを確認すると，このファイルがJPEG画像であることがわかる．key18.jpgにリネームし，EXIF情報を確認する．

$ exiftool key18
ExifTool Version Number         : 11.23
File Name                       : key18
Directory                       : .
File Size                       : 4.7 kB
File Modification Date/Time     : 2018:12:31 10:57:46+09:00
File Access Date/Time           : 2019:01:01 20:48:07+09:00
File Inode Change Date/Time     : 2019:01:01 13:21:48+09:00
File Permissions                : rwxr--r--
File Type                       : JPEG
File Type Extension             : jpg
MIME Type                       : image/jpeg
JFIF Version                    : 1.01
Resolution Unit                 : None
X Resolution                    : 72
Y Resolution                    : 72
Exif Byte Order                 : Big-endian (Motorola, MM)
User Comment                    : ****** answer is f ******
Exif Image Width                : 200
Exif Image Height               : 200
Current IPTC Digest             : d41d8cd98f00b204e9800998ecf8427e
IPTC Digest                     : d41d8cd98f00b204e9800998ecf8427e
Profile CMM Type                : Apple Computer Inc.
Profile Version                 : 2.2.0
......

User Commentに答えが記入されている．

key18の答えは「f」である．

final.c

final.cをコンパイルし，18個の小問題の答えをすべて入力すると，最終問題にアクセスするためのURLが表示される．

$ gcc final.c
$ ./a.out 
input answer for key01 >>> 5
input answer for key02 >>> 2
input answer for key03 >>> e
input answer for key04 >>> 0
input answer for key05 >>> d
input answer for key06 >>> 1
input answer for key07 >>> 8
input answer for key08 >>> 3
input answer for key09 >>> c
input answer for key10 >>> 1
input answer for key11 >>> 6
input answer for key12 >>> f
input answer for key13 >>> a
input answer for key14 >>> 9
input answer for key15 >>> b
input answer for key16 >>> b
input answer for key17 >>> 8
input answer for key18 >>> f
http://3.112.2.176/?key=52e0d1833c10d186f3a859c9dc8bcb81f608365f
keyが誤っていた場合，約3分間の間アクセスが遮断されます．
ご注意ください．
$

最終問題

3文字のASCII文字列Xで，

sha1(X) = 52e0d1833c10d186f3a859c9dc8bcb81f608365f

なるXを発見する問題．
総当たりで解を探索すると，

X = DML

を得る．

反省

18個の小問題に全て正解しなければ各小問題の正誤が分からないようになっていたことが解答者のストレスになっていたと考える．各問題にある程度の長さのflagを設定するべきだった．

nkhrlab~

140字超の記事

nkhrlab challenge 2019 想定解法

はじめに

問題

key01

key02

key03

key04

key05

key06

key07

key08

key09

key10

key11

key12

key13

key14

解法1 (2018年度高等学校学習指導要領の範囲で)

解法2 (行列の力を借りて)

解法3 (あの)

key15

key16

key17

key18

final.c

最終問題

反省

はじめに

問題

key01

key02

key03

key04

key05

key06

key07

key08

key09

key10

key11

key12

key13

key14

解法1 (2018年度 高等学校学習指導要領の範囲で)

解法2 (行列の力を借りて)

解法3 (あの)

key15

key16

key17

key18

final.c

最終問題

反省

解法1 (2018年度高等学校学習指導要領の範囲で)