openssl primeを用いてksnctfのG00913を解く

この記事は、2020年8月18日に旧ブログに投稿したものです。

ksnctfのG00913のwriteupです。

G00913 wirteupで検索すると、既に多くの方がwriteupを書かれています。 しかしながら、openssl primeを用いた解き方が見当たらなかったので執筆することにしました。勉強会で発表したネタでもあります。

問題

https://ksnctf.sweetduet.info/problem/20

解説

多くのサーバー証明書に使われているRSA暗号は、鍵を生成するために素数を必要とします。 例えば、鍵長が2048bit（RSA-2048）の場合、1024bitの素数が2つ必要です。 RSA暗号は既知の素数を利用しないため、OpenSSL（LibreSSL）には素数を生成・判定するコマンドが含まれていると推測できます。

そこで、$ man opensslで、primeを検索してみます。すると、SEE ALSOセクションに、prime (1)があります。 $ man primeを見ると、$ openssl primeは、指定された数値が素数であるかどうかを判定できるコマンドであることが分かります。

1$ openssl prime 1
21 (1) is not prime
3$ openssl prime 2
42 (2) is prime
5$ openssl prime 1234567890987654321
6112210F4B16C1CB1 (1234567890987654321) is not prime

以上より、円周率を最初から1桁ずつずらした値をopenssl primeに与えれば解けそうです。 そこで、以下のシェルスクリプトを作成しました¹。 PIURLには、円周率が1万桁ほど収録されたファイルを指定します。 なお、このスクリプトは素数を発見してもループを抜けません。

1#!/bin/bash
2PIFILE=円周率1万桁のファイルパス
3for i in $(seq 1 1000000); do
4  TRG=$(cut -c$i-$((i+9)) < $PIFILE)
5  openssl prime $TRG
6done

補足

akictfのYet Another G00913も同様の方法で解けます。

この場合、TRG=$(cut -c$i-$((i+9)) < $PIFILE)をTRG=$(cut -c$i-$((i+199)) < $PIFILE)に変えればOKです。