SECCON予選のCrazy Repetition of Codesのための繰り返し二乗法

はじめに

このブログは以前SECCONで解いた「Crazy Repetition of Codes」という問題の解説記事(https://kurenaif.hatenablog.com/entry/2019/10/20/213842) の前提知識である、繰り返し二乗法というアルゴリズムを解説する記事になります。

繰り返し二乗法

繰り返し二乗法はその名の通り、二乗を繰り返して、効率的に $n$ 乗を求めるアルゴリズムです。

例えば、 $x^ n$ を求めたいとします。

pow() 関数のような関数を使わずにこの値を求めたい場合は、

int x = 1;
for(int i=0;i<n;i++){
    x *= x;
}

のようなコードを書いて求めるのがお手軽です。この書き方で $n$ 乗を求めようとすると $\mathcal{O}(n)$ になりますね。 ( $\Theta(n)$ )のほうが適切という説もありますが、このブログでは計算量をすべてビッグオー記法で説明します。)

しかし、人間が計算する場合は $x^ n$ を求める場合は順番にかけていくことは少ないと思います。例えば、 $2^ 8$ を求める場合は $1 ( 2^ 0 ) \rightarrow 2 ( 2^ 1 ) \rightarrow 4 ( 2^ 2 ) \rightarrow 16 ( 2^ 4 ) \rightarrow 256 (2^ 8)$ と二乗を意識して計算することが多いのではないでしょうか。 8回計算しなければならなかった掛け算が、3,4回の計算で収まりましたね。 $2^ {16}$ を求めたい場合は、 $2^ 8$ を知っているので、 $256 \times 256$ を計算すれば良さそうです。これは電卓が必要になりますが、コードで実現する場合は実質電卓で計算しているようなものなので、気にしなくて良さそうですね。

では、この工夫した計算方法では何回で計算が終わるのでしょうか？乗数が倍々になっているので、 $x$ 番目の乗数は $2^ x$ になっていそうです。逆に考えると、乗数 $n$ の計算回数が知りたい場合は log を取ればいいので、 $\log(n)$ になりそうですね。

$x^ 4$ や $x^ 8$ を求めたい場合は良かったのですが、例えば $x^ 6$ を求めたい場合はどのようにすればよいでしょうか？

幸いなことに、世の中には2の乗数で任意の整数を表現する方法があります！
2進数です！ $6$ は2進数表現で $\mathrm{0b110}$ です！なので、 $x^ 6 = x^ 4 \times x^ 2$ で求めることがきますね！

よって、大まかなアルゴリズムの流れは

乗数を２進数表現する。
1が立っているbitに対応する乗数を掛けていく

といった流れになります。

具体的なソースコードは以下のようになりますね。

int pow(int x, uint64_t n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res = res * x;
		x = x*x;
		n >>= 1;
	}
	return res;
}

これで任意の整数 $n$ に対して、 $\mathcal{O}( \log (n))$ で $n$ 乗を求めることができました！

大きな $n$ 乗を求めたい場合は多倍長整数を使うか、剰余を求めて有限体上で計算することが多いと思います。掛け算をしたあとでも mod計算は有効なので、xの10億乗を $10^ 9 + 7$ で割ったあまりを求めたい場合もこのやり方は有効です。

ちなみに、Pythonのpow関数では第3引数に剰余を与えることができ、計算も高速なので、気軽に整数の剰余を求めたく、Pythonを使用している場合はpow関数を使えば良いでしょう。言語や実装によっては遅い場合もあるので、自前で pow を用意したほうがいい場合もあります。

CTFにおけるCryptographyと行列

CTFにおけるCryptographyでは、アルゴリズムの内容を式に落とし込むことで考察が進むことが多々あります。

最近私が解いた問題では、SECCON Beginners CTFのPartyが直球でそういう問題でした。

kurenaif.hatenablog.com

ある(平文)ベクトル $x$ があり、処理 $A$ をかけたら (暗号文)ベクトル $y$ になる。ということが行列演算で表現できた場合、以下のような式になります。

$y = Ax$

もし、 $y$ と $A$ が与えられ、 $x$ がわからないという問題だった場合、 $A$ の逆行列を求めることで、 $x$ を求めることができます。

$A^{-1} y = x$

Cryptoで逆行列を求めたい場合の注意事項ですが、大体の場合は64bit整数に収まらないので、 numpy 等の機能を使用すると、bitが溢れてオーバーフローします。自前で実装するか、 Z3 などを使うと良いでしょう。
また、行列演算も普通の整数ではなく、有限体を扱う場合もあるので、問題に合わせて使うツールやアルゴリズムを選択しましょう。
高速に逆行列を求める必要がない場合は自前で実装しても良いかもしれませんね。

逆行列を用いて解く問題の例として、この問題を作ったので、よろしければ解いてみてください！

github.com

他にも、メルセンヌ・ツイスタという擬似乱数生成アルゴリズムも、624個連続した値を取得できれば次の値を予測できるということで有名ですが、これもアルゴリズムが行列で表現でき、逆行列が求められるからという說明が可能です。

行列表現と繰り返し二乗法

アルゴリズムを行列で表現できると、逆行列を使用することで平文を逆算できるといいましたが、例えばどういうものが行列表現にできるのでしょうか？

暗号とは関係ありませんが、有名所ではフィボナッチ数列があります。
フィボナッチ数列は、以下で求められる数列です。

a[i] = a[i-1] + a[i-2]
ただし、
a[0] = 0
a[1] = 1

この式は、実は行列で表現することが可能です。

$\left( \begin{array}{c} a[i] \\ a[i-1] \\ \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} \right) \left( \begin{array}{c} a[i-1] \\ a[i-2] \\ \end{array} \right)$

n番目のフィボナッチ数列の要素は、

$\left( \begin{array}{c} a[i] \\ a[i-1] \\ \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} \right)^n \left( \begin{array}{c} a[1] \\ a[0] \\ \end{array} \right)$

のようにして求められます。行列表現をすることにより、n番目のフィボナッチ数列を $\mathcal{O}(\log(n))$ で求められることにお気づきになられたでしょうか？行列の掛け算を繰り返し二乗法で求められるからですね。

フィボナッチ数列の他にも、同じあみだくじを $N$ 個連結させた時の最終結果も繰り返し二乗法で、 $\mathcal{O}(\log(N))$ で求めることができますし、グラフを隣接行列形式に落とし込んで繰り返し二乗法を用いるケースもあります。競技プログラミングで使用する場合は、行列積に3乗のオーダーがかかるので、大きな行列の計算になる場合は気をつけましょう。(100個の和を求めるフィボナッチ数列みたいな問題は危なそうですね)

序盤で述べた SECCON 2019 Online CTF Crazy Repetition of Codes では、CRC32というアルゴリズムを $10^ {10000}$ 回適用した結果を求めるという内容になっています。この回数を愚直に計算しているとコンテスト期間中に到底間に合いませんが、CRC32をうまく行列表現し、繰り返し二乗法でlogオーダーに抑えることで現実的な時間で解けます。

以前のブログで解いた手法では、CRC32を求める過程をうまく行列表現し、logで求めています。
私のアルゴリズムでは $\mathcal{O}(\log^2 N)$ の計算量がかかり、多倍長整数演算も行うので比較的速い言語で解いても50分ほどかかりますが、どうやら $\mathcal{O}(\log N)$ で抑える方法もあるらしく、かなり高速に求める手法もあるみたいです。

まとめ

このブログでは、繰り返し二乗法の說明から、行列表現、CTFにおけるCryptographyや競技プログラミングでの行列の扱い方の一例を取り上げました。問題を数式で表現すると、様々な性質が見えてくることもあり、考察が捗ることも多くあります。もし行き詰まった場合は一度数式に落とし込んで、世の中の使える定理を調べてみてはいかがでしょうか。