末尾に0がたくさん続くSHA1を探し求めて

珍しいSAH1が欲しい!


  • 2017/06/25 作成

Contents


概略

ふとしたきっかけで↓の記事に出会った。

へー、おもろいやん。

でも、やっぱりここって重大だよね。

「いや、つまりですよ。SHA1というのは160ビットのバイナリー列って最初に言ってたじゃないですか。この16進数の表現は、なんというか、人間が勝手に4ビットずつ区切って勝手に0からfに割り当てただけじゃないですか」

「なるほど、たしかにそれはそうだね」

「つまり、SHA1ハッシュが数字だろうがアルファベットだろうがSHA1にとっては何の特徴にもならない気がするんです」

「なるほどね」

つまり、SHA1の16進数表記が数字だけだろうが特に意味はないという話。じゃあ、どういう性質なら「意味がある」と言うことができるだろうか?

意味のあるSHA1

SHA1は16進数表記で$40$桁である。つまり2進数表記で$4\times 40=160$ビットである。このビットの並びに何らかの規則性があれば意味があると言えるのではないか?

少なくとも、次の記事では「特徴の異なるSHA1 = ビットの並びが大きく異なる」という風な感じなので、ビットの並びでSAH1の特徴を議論することは間違ってはいないはず。

ということで、SAH1を2進数表記したときに「1がたくさん連続している」、「0がたくさん連続している」といった状況なら特徴的と言えるだろう。そんな訳で、今回はSHA1の末尾ビットに0がなるべくたくさん並ぶSAH1を探すことにした。

ここから先の記述のために紹介しておくと、ビット列の右側(末尾)から見て 0 がいくつ連続しているかを Number of Training Zero (NTZ) と呼ぶ。$NTZ(0101100)=2$ という感じである。

つまり今回やりたいことは、「NTZがなるべく大きいSAH1の入力を求める」ことである。

1つ忠告しておくと、私は暗号の専門家ではないので適当なことを言っているかもしれない。ここから先の記述もあまり信用しないでほしい。

NTZの期待値

ちょっと数学っぽい話。ここでは、データ$D$の末尾から$i$ビット目を$D(i)$と書くことにする。

データが1個のときの話

SAH1が理想的なHash関数であると仮定すると、任意のビットが$0$になる確率は$\frac{1}{2}$である。$160$ビットのランダムデータ$D$について、少なくとも末尾$k$ビット($0\leq k\leq 160$)が全て$0$になる確率は \[ P\left[\bigwedge_{i=1}^{k} D(i)=0\right] = \prod_{i=1}^{k} P[D(i)=0] = \frac{1}{2^k} \]

したがって、$0\leq k \leq 159$ のとき、$NTZ=k$となる確率[1]は \[ \begin{align} P[NTZ=k] &= P\left[\bigwedge_{i=1}^{k} D(i)=0\right] - P\left[\bigwedge_{i=1}^{k+1} D(i)=0\right] \\ &= \frac{1}{2^k} - \frac{1}{2^{k+1}} \\ &= \frac{1}{2^k}\left(1-\frac{1}{2}\right) \\ &= \frac{1}{2^{k+1}} \end{align} \]

また、$NTZ=160$となる場合も合わせて、 \[ P[NTZ=k] = \begin{cases} \frac{1}{2^{k+1}} & (0\leq k \leq 159) \\ \frac{1}{2^{160}} & (k=160) \end{cases} \]

これを用いると、$\sum_{l=0}^{k}\frac{1}{2^{l+1}} = 1-\frac{1}{2^{k+1}}$より、 \[ P[NTZ\leq k] = \begin{cases} 1-\frac{1}{2^{k+1}} & (0\leq k \leq 159) \\ 1 & (k=160) \end{cases} \]

データが複数個のとき

いま、$N$個のデータ $D_1, D_2, D_3, \cdots, D_n$ があるとする。各データは$160$ビットで、それぞれに相関はないものとする。これらのデータのNTZはそれぞれ$NTZ_1, NTZ_2, NTZ_3, \cdots, NTZ_n$ とする。

この$n$個のデータのNTZの最大値を$M_n$とする。すなわち \[ M_n=\max \{ NTZ_j, j = 1, 2, \cdots, n \} \]

また、前小節の議論より、 $D_1, D_2, D_3, \cdots, D_n$ のすべてが$NTZ\leq k$を満たす確率は \[ \begin{align} P[M_n\leq k] &= \prod_{j=1}^{n}P[NTZ_j \leq k] \\ &= \begin{cases} \left(1-\frac{1}{2^{k+1}}\right)^n & (0\leq k \leq 159) \\ 1 & (k=160) \end{cases} \end{align} \]

ここで、
「 $M_n = m$ である[2]
⇔「$NTZ=m$となるデータは1つ以上存在するが、$NTZ\geq n+1$となるデータは存在しない」
⇔「全てのデータは$NTZ\leq m$を満たし、かつ少なくとも1つのデータは$NTZ=m$を満たす」
⇔「(全てのデータが$NTZ\leq m$を満たす) $\land$ $\lnot$(全てのデータが$NTZ\leq m-1$を満たす)」
なので、$n$個のデータのNTZの最大値$M_n$が$m$である確率は、 \[ \begin{align} P[M_n=m] &= \begin{cases} P[M_n\leq 0] & (m=0) \\ P[M_n\leq m] - P[M_n\leq m-1] & (1\leq m\leq 160) \end{cases} \\ &= \begin{cases} \left(1-\frac{1}{2}\right)^n & (m=0) \\ \left(1-\frac{1}{2^{m+1}}\right)^n - \left(1-\frac{1}{2^m}\right)^n & (1\leq m\leq 159) \\ 1 - \left(1-\frac{1}{2^{160}}\right)^n & (m=160) \end{cases} \end{align} \]

したがって、$n$個のデータのNTZの最大値$M_n$の期待値は、 \[ \begin{align} E[M_n] &= \sum_{m=0}^{160}m\cdot P[M_n=m] \\ &= 0 \cdot \left\{\left(1-\frac{1}{2^1}\right)^n\right\} \\ &\hphantom{==} + 1\cdot \left\{\left(1-\frac{1}{2^{2}}\right)^n - \left(1-\frac{1}{2^1}\right)^n\right\} \\ &\hphantom{==} + 2\cdot \left\{\left(1-\frac{1}{2^{3}}\right)^n - \left(1-\frac{1}{2^2}\right)^n\right\} \\ &\hphantom{==} + 3\cdot \left\{\left(1-\frac{1}{2^{4}}\right)^n - \left(1-\frac{1}{2^3}\right)^n\right\} \\ &\hphantom{==} + \cdots \\ &\hphantom{==} + 158\cdot \left\{\left(1-\frac{1}{2^{159}}\right)^n - \left(1-\frac{1}{2^{158}}\right)^n\right\} \\ &\hphantom{==} + 159\cdot \left\{\left(1-\frac{1}{2^{160}}\right)^n - \left(1-\frac{1}{2^{159}}\right)^n\right\} \\ &\hphantom{==} + 160\cdot \left\{1 - \left(1-\frac{1}{2^{159}}\right)^n\right\} \\ \end{align} \]

ここで、整理のために次のように決める。 \[ f_\alpha = \left(1-\frac{1}{2^{\alpha}}\right)^n \]

すると、$M_n$の期待値は、 \[ \begin{align} E[M_n] &= 0 \cdot \left\{f_1\right\} \\ &\hphantom{==} + 1\cdot \left\{f_2 - f_1 \right\} \\ &\hphantom{==} + 2\cdot \left\{f_3 - f_2 \right\} \\ &\hphantom{==} + 3\cdot \left\{f_4 - f_3 \right\} \\ &\hphantom{==} + \cdots \\ &\hphantom{==} + 158\cdot \left\{f_{159} - f_{158} \right\} \\ &\hphantom{==} + 159\cdot \left\{f_{160} - f_{159} \right\} \\ &\hphantom{==} + 160\cdot \left\{1 - f_{159} \right\} \\ &= f_1\left\{0 - 1 \right\} \\ &\hphantom{==} + f_2 \left\{1 - 2 \right\} \\ &\hphantom{==} + f_3 \left\{2 - 3 \right\} \\ &\hphantom{==} + \cdots \\ &\hphantom{==} + f_{158} \left\{157 - 158 \right\} \\ &\hphantom{==} + f_{159} \left\{158 - 159 \right\} \\ &\hphantom{==} + f_{160} \left\{159 - 160 \right\} + 160 \\ &= 160 - \left\{f_1 + f_2 + f_3 + \cdots + f_{160}\right\} \end{align} \]

なので、結局のところ$n$個のデータのNTZの最大値$M_n$の期待値は、 \[ E[M_n] = 160 - \sum_{i=1}^{160}\left\{\left(1-\frac{1}{2^i}\right)^n\right\} \] であることがわかる。

データ数とNTZ最大値の期待値 (準備の準備)

前小節より、次のことがわかる。

  • 互いに異なる$n$個のデータをそれぞれ(理想的な)ハッシュ関数に入力して、その出力を$D_1, \cdots, D_n$とすると、各$D_j$が160ビットなら、それらのNTZの最大値の期待値は上式で与えられる。
  • 言い換えると、ハッシュ関数への入力をとっかえひっかえ…ということを$n$回繰り返して、なるべく NTZ が長い SHA1 を探すという試行を行ったとき、その NTZ は平均して上式で与えられる $E[M_n]$ となる
  • 直感的に明らかなように次式が成立するので、無限個のデータについてハッシュを計算することを繰り返せば、いつかは $NTZ=160$ を満たす入力が見つかる(理想的なハッシュ関数ならば)。

\[ \lim_{n\to\infty}E[M_n] = 160 \]

では、データ数 $n$ の増加に従ってNTZの最大値の期待値はどのように大きくなるだろうか。

準備:任意精度の数値計算

この章の目標は、横軸が$n$で縦軸が$E[M_n]$のグラフを作ること。

失敗例:何も考えずScilabを使ったら

Scilabは倍精度浮動小数点数で計算してくれる。普段はこれで十分だが、これでグラフを作ると$n$が大きいときにきちんと計算してくれない。

Scilabで作ったグラフ(横軸$n$、縦軸$E[M_n]$)
Scilabで作ったグラフ(横軸$n$、縦軸$E[M_n]$)

上のグラフは明らかに $\lim_{n\to\infty}E[M_n] = 160$ を満たしていない。よってこのグラフは誤りである。

成功例:Maxima の多倍長浮動小数点数

Maximaといえば数式処理。Mathematicaの代用品として有名なので知っている人も多いはず。

まずは数値計算する前に厳密値を計算してみたい。$n$をいろいろ変えて$E[M_n]$を計算させてみる。

(%i1)	em(n) := 160 - sum((1-(1/2)^i)^n, i, 1, 160);
(%o1)	em(n):=160-sum((1-(1/2)^i)^n,i,1,160)
(%i2)	em(10);
(%o2)	165647370257559175101613947728[423 digits]300841505370879196400687512575/444624164770940446200168140655[422 digits]559538970957296160626364645376
(%i3)	em(10^2);
(%o3)	210873745927705653252506260690[4758 digits]721825796022394255213556924415/301946933723922757953065844661[4757 digits]955405473073995516655882469376
(%i4)	em(10^3);
 \<\< Expression longer than allowed by the configuration setting! \>\>

$n\gtrsim 10^3$ 程度になると、散々待たされた挙句「ダメです」と言われる。$n=2^{160} (\sim 1.46 \times 10^{48})$ 程度まで計算したいので、有理数のままでは駄目。

そこで、多倍長浮動小数点数 (big float)を使う。ここでは50桁程度の精度があれば少なくとも$n\sim 10^{50}$程度までは正しく計算できる。

(%i5)	fpprec:50;
(fpprec)	50
(%i6)	em(n) := 160 - sum(bfloat(bfloat((1-(1/2)^i))^n), i, 1, 160);
(%o6)	em(n):=160-sum(bfloat(bfloat(1-(1/2)^i)^n),i,1,160)
(%i7)	em(2^160);
(%o7)	1.5947813406154012091095327373482509142344635733901b2
(%i8)	em(2^165);
(%o8)	1.5999999999999998733583445090566389579005145580181b2
(%i9)	em(2^170);
(%o9)	1.6b2

多倍長浮動小数点数では必要に応じて利用者が浮動小数点数の精度を大域変数 fpprec で設定し, 表示桁数は大域変数 fpprintprec で設定する. 大域変数 fpprintprec が 0 であれば表示桁数は大域変数 fpprec の値に合せられる. 大域変数 fpprec の既定値は 16 と倍精度の浮動小数点数の精度であり, 大域変数 fpprintprec の値は 0 である. また, 多倍長浮動小数点数への変換は bfloat 函数を用いる.

Maxima の多倍長浮動小数点数は LISP の多倍長浮動小数点数を使わずに自前で定義した独特の書式の多倍長浮動小数点数を利用する為に処理に時間がかかる欠点を持つ.

多倍長浮動小数点演算というだけなら Maxima である必要はないが、グラフを描いたりするのには便利なのでこのまま行かせてもらう。

データ数とNTZ最大値の期待値

準備もできたのでグラフを作る。$bfloat(x)$を50桁精度の多倍長浮動小数点への変換として、次の関数を考える。 \[ em(n):=160-\sum_{i=1}^{160}\left\{bfloat\left(\left[bfloat\left(1-\frac{1}{2^i}\right)\right]^n\right)\right\} \]

横軸は対数軸にする。

(%i10)	plot2d([em(n)], [n,1,2^170], [y,0,165],
	 [plot_format, gnuplot], [logx])$
Maximaで作ったグラフ(横軸$n$、縦軸$em(n)$)
Maximaで作ったグラフ(横軸$n$、縦軸$em(n)$)

きちんと $\lim_{n\to\infty}E[M_n] = 160$ も満たしている。素晴らしい。

ところで、$n$が大きくなるまでは殆ど $\log_{2}n$ の直線に沿っている(当然といえば当然だが)。

Maximaで作ったグラフ(横軸$n$、縦軸$em(n)$, $\log_2 n$)
Maximaで作ったグラフ(横軸$n$、縦軸$em(n)$, $\log_2 n$)

このあたりの性質について、世の中ではどのような取り扱いが行われているのだろうか。

nビットのハッシュ関数に対する原像攻撃では、攻撃が成功するまでの試行回数は2nに比例する。

ハッシュ長が L ビットであるハッシュ関数において、与えられた特定のハッシュに対応する元のメッセージを見つけることは、総当たり攻撃では 2L の試行で可能である。これは原像攻撃と呼ばれる。

というわけで、160ビットのハッシュ関数について、任意の出力を与える入力を求めるのに必要な試行回数は$2^{160} (\sim 1.46 \times 10^{48})$回である。上のグラフでも$n=10^{48}$程度で$em(n)$は飽和している。

ちなみに、$em(n)$はほぼ$1$である。データのビット数が無限のとき厳密に1になる。そこから先は$n$が大きくなるごとに$\log_2 n$に近づいていくが、漸近するというわけではなく一定の間隔が開く。

$n$が小さいときのグラフ
$n$が小さいときのグラフ

そして$n$が$2^{160}$に近づくと、$em(n)$は増加が緩やかになり、縦軸座標$160$の直線に漸近する。

$n\sim 2^{160}$のときのグラフ
$n\sim 2^{160}$のときのグラフ

途中までは$\log_2 n$と似た挙動を示すが、同じというわけではなく$em(n)$の方が少し大きい。ではどれくらい大きいのかというと、だいたい$0.4$くらい大きい状態が$n\sim 2^{160}$になるまで続くようだ。

$em(n)-\log_2 n$のグラフ
$em(n)-\log_2 n$のグラフ

探索の方法

今回の探索のためにC++で適当にコードを書いた。探索では、ビット数の小さいデータから順に、すべての種類のデータを生成し、それぞれに対してSHA1を計算し、NTZを数える。NTZの数え方は#意味のあるSHA1中のリンクを参照のこと。

最初はRubyで書いたのだが、C++で書いたら10倍ほど速かったので、これから書く人はC/C++で書くことをお勧めする。(具体的には、どうということのないマシンでRubyコードを動かしたら、SHA1を10,000,000回計算するのに20~30秒掛かっていたのが、C++だと2~3秒になった(つまり100,000,000回の計算に25秒必要な程度)。もっとも、コードの記述の仕方に問題が含まれないとも限らないが。)

探索の結果

入力(input)、対応するSAH1(SHA1)、計算回数(step)、SAH1のNTZ(NTZ)をタブ区切りで置いておく。今回の試行では547,830,262,669回の計算でNTZ=39となるSAH1が得られた。実はこの先も550,700,000,000回程度まで計算を続けたが、SAH1のNTZが39を超えることはなかった。

input	SHA1	step	NTZ
0x02	0xc4ea21bb365bbeeaf5f2c654883e56d11e43c44e	3	1
0x07	0x5d1be7e9dda1ee8896be5b7e34a85ee16452a7b4	8	2
0x27	0xbb589d0621e5472f470fa3425a234c74b1e202e8	40	3
0x28	0x28ed3a797da3c48c309a4ef792147f3c56cfec40	41	6
0x1200	0x92a5652d382a18e89c4881ec57041fc7d885ca80	274	7
0x3f00	0x738f291e53e97c08dae378c71ef70a60e31ae900	319	8
0xe901	0xfa385d05acedaa4e4378d30a713aedddb9eacc00	745	10
0x0d06	0x8851f5acdebb6dd17fc5cbca01b421dccd0fa800	1805	11
0xa710	0x281f5a08e249a6a4860c873d3277e7519cc71000	4519	12
0x6711	0xb28027d59d4a2063f5d9ea514b736043097b6000	4711	13
0x3a3d	0x4ecc87266f257c265e368df6959c08d135674000	15930	14
0xb07001	0x58c3f4b778f0d292174b9f57705d59904ea28000	160175	15
0x4eaa01	0x87d2271c5b33fb0d36ca1a9cb9ae9ed1208c0000	174925	18
0x42050a	0xa1e56829953292773b92c10fc73627653bf00000	722497	20
0xb94872	0xbaa74e233828d53b9d7c43faaa63e74ad3c00000	7555512	22
0x45cd86	0xbc9bb8957f73e26572f3a68fce2df779e6000000	8900164	25
0x5d426a02	0xb98d029ab4510c3538cd502349b8497908000000	57361243	27
0xdd7e9717	0xe45a7bece6d6195ba7762de1c902211f30000000	412647387	28
0x8933652e	0x170582e9c8511d4b80d4c5ed684f8b61e0000000	795227271	29
0xe80c5534	0xe8fb607e0580bef90a794f707b1b677a80000000	894832102	31
0xe3f7834400	0xd9742910435beb8a60c992734e77f07c00000000	5461309664	34
0xfced2f9904	0x9fafb9d357c5c107286bef4892a7403000000000	24061734649	36
0x6f327bbb15	0xa05ad384b2a30fd8b35f809a277911c000000000	97651536748	38
0x906a398c7e	0xe574ed972ed78703485a2b71b987a18000000000	547830262669	39

もっと時間を掛ければNTZが大きいSAH1を見つけられるはずだが、それは他の人に任せることにしたい。

さて、この結果は概ね理論に従っていると言えるだろうか。先の$em(n)$に重ねてグラフを作成してみた。参考のために時間軸も追加した。グラフ自体はExcelで作成した。赤線はMaximaの計算結果を流用した。

(%i1)	fpprec:50;
(%i2)	em(n) := 160 - sum(bfloat(bfloat((1-(1/2)^i))^n), i, 1, 160);
(%i3)	for a:0 step 0.25 while (a<=12) do print(em(10^a));
試行回数とNTZの最大値
試行回数とNTZの最大値

ほぼ理論(赤線)に従ってNTZの最大値(青線)が増加しているのがわかる。

参考:任意の位置の0/1の連続を探す場合

今まではNTZに限定してきたが、他の位置でも0あるいは1がたくさん連続していれば、それは特徴と言えるかもしれない。そこで、任意の位置になるべく長い0/1の連続があるSHA1も探してみた。簡単のため、今度は入力データのビット長は固定とした[3]

実装により大きく異なるだろうが、私の実装では100,000,000回の計算に75秒程度が必要だった。NTZだけを調べるのに比べて3倍程度の時間が必要になったことになる。SHA1の計算時間はほぼ変化していないはず[4]だが、NTZを数えるのに必要な時間に比べて、0/1の連続を確かめるのに必要な時間はかなり長い。

input	SHA1	step	0s	1s	point(0s, 1s)	type(1:1s, 2:0s, 3:both)
0x0000000000000000	0x05fe405753166f125559e7c9ac558654f107c7e9	        1	  7	  8	( 19,   8), 3
0x0000000000400000	0x7c41db0fc56a5c596d436401c0a6479fbc1c99e2	        5	  9	  6	( 87,  29), 1
0x0100000000800000	0xbf644cf9376103cd8fcedc2d235eaff9b1c7faa4	        7	  6	  9	( 49, 117), 2
0x0600000000000000	0x0f29b02f9eff3b0f2b9bba51e299b6a0b7493ff0	       24	  6	 10	( 21, 147), 2
0x0500000000400000	0x7cedb3c67ae02002357147900da9e2813c389fed	       25	 11	  8	( 52, 148), 1
0x0e00000000400000	0xf19fd59757aa77fe11970f43231256d5858ffe11	       61	  4	 11	( 64, 141), 2
0x1200000000000000	0x8c00184e2b9d75b5015b31ac37517b27a7ca2a16	       72	 13	  5	(  7, 134), 1
0x1600000000800000	0xa8471d8e0f93b247e30435200060bb879f42b167	       91	 14	  6	( 92,  62), 1
0x1f00000000c00000	0xd5d3b7d179e90ede3184a2f774132d7ffb5e0359	      126	  7	 12	(144, 122), 2
0x2e00000000c00000	0xdf9a3958982bf2e260125befffd4a073ce7c1e31	      186	  8	 14	( 68,  93), 2
0x4800000000400000	0xb16319a3edd123d490c7876616dd3b63709ffffc	      292	  4	 19	( 69, 140), 2
0x6e00000000000000	0x78c5b76d00293060ee7c00040b479caf5d290a8e	      441	 15	  5	( 79,  74), 1
0xa700000000800000	0x72f70cf3f9e25d0496626000032e33fe9081023b	      672	 19	  9	( 84, 119), 1
0x0801000000000000	0x9904c56df8e3c48e59317bcc350534ffffff132a	     1052	  5	 24	(  9, 121), 2
0x0602000000800000	0x0da7fffffdfb968b77a7dc90a3029cec62217669	     2072	  6	 25	(105,  14), 2
0xf508000000c00000	0x602f1bcb50e00000b5949110a7b652f24fa6b503	     9512	 21	  5	( 44, 133), 1
0xd62d000000800000	0xb2fd86553cc070000002147c9d14dca86d1e7109	    54602	 26	  6	( 53,   9), 1
0x8dab060000800000	0x56a8246833687fffffe8405bd781e031cc6bc6b0	  1776077	  7	 26	( 83,  50), 2
0x60c9060000000000	0xadd698aae234a0abffffffbe571b1369d46a8344	  1787421	  5	 27	( 52,  63), 2
0xec170b0000c00000	0x9fd430b8000000d451de707f814ad60abf51b850	  2869601	 27	  8	( 30,  90), 1
0x6fcf0e0000800000	0xb53b8000000548d6c61a44a3ae2b7519712b6db5	  3895960	 28	  3	( 18,  11), 1
0x13b7100000000000	0xa8df5a30dfffffff651d697e8b2db03d20cfa45a	  4348492	  6	 29	(117,  36), 2
0xc6943b0000c00000	0x84431be8434dd47625446a315600000004233e81	 15613558	 30	  5	(104,  23), 1
0xdc40cb0000800000	0xd7ffffffe3d7e7b23c44f11b2a93a082fa992319	 53526480	  5	 30	(116,   6), 2
0xa1881f0100c00000	0xf7ab0d50c527f1d2379d172f5fffffffd4fe9167	 75889208	  4	 31	( 17, 100), 2
0xc1f49e0100800000	0xb844f000000017cbdb1708dd416e0ea8d9b2ecd9	109073325	 31	  5	( 21,  54), 1
0x4c8e9d0100400000	0x63d8abfffffffc9d1713a87bf84f7da4023493db	109104952	  8	 32	(127,  23), 2
0x81cebe0100000000	0x473fc00000001242b8f2e2842e7a5012d05129fc	115418502	 33	  8	( 19,  11), 1
0xdee5e00100800000	0xd899946e75c8791aa14735f4893fffffffe0f685	126389536	  5	 33	(140, 107), 2
0xe36ae00600c00000	0x10ffffffffe9c76656a00c7724b4769d078058c8	463872476	  9	 35	( 76,   9), 2
0xa672900e00400000	0xd4d059dd2a5771933c602d6c0cb0000000005027	981388359	 37	  4	(109,  67), 1
0x2010624400000000	0xee2c5001f6a093b313fffffffff6744253420492	4525028318	 11	 38	( 21,  71), 2
0xe9a7c9ea00400000	0x3905a996d5ffffffffff0d0a0e38297415da3f70	15831637992	  5	 41	(  9,  40), 2
0x7617984201400000	0x5fe44c000000000051f1dcdd5da3de9bbb673925	21752209966	 43	  8	( 23,   4), 1
0xe7c3fc3802800000	0x5d0e07400000000000fafebcf5fde4a620e784bb	38359608479	 46	  7	( 27,  81), 1
0x1024f8a603000000	0xa81affffffffffef55dab7a65359f58a915cbf74	61881485552	  6	 43	(  6,  17), 2

当然ながら少ない試行回数で長い0/1の連続を見つけることができた。しかしSHA1のビット列のチェックに時間が掛かるようになってしまったので効率は微妙。

0/1の連続がなぜ重要か

ここまで「0/1がたくさん連続している=>0/1の並びが特徴的=>意味のあるSHA1」という論調で話を進めてきたつもりだが、実際にこれが使われている場面があったりする。

Bitcoin のマイニングは、ざっくりと言えば SHA-256 の先頭に並んだ0の数、すなわち Number of Leading Zero (NLZ) が大きくなるような入力を探すという作業を一定の制限の下で行っている。

で、実際どれくらいの0が連続していればよいのかというと、記事作成時点では73bit程度は必要らしい。昔はもっと短くても(例えば36bit程度でも)よかったらしいが、最近は採掘者が多いのでそうもいかない、ということらしい。

しめくくり

特記事項はないので計算時間に関して少し計算を。

我がヘボPCでは、並列処理等を用いずにSHA1の計算とNTZの検査のセットを27秒で$10^8$回行うことができた。この調子で計算をしたら、$NTZ=160$を満たすSHA1、つまり0が160bit並んだようなSHA1はどれくらいの時間で得られるだろうか?

\[ \begin{align} Time &= 27 [sec]\times \frac{2^{160}}{10^8}\\ &= 3.95 \times 10^{41} [sec]\\ &= 4.57 \times 10^{36} [days]\\ &= 1.25 \times 10^{34} [years] \end{align} \]

Wikipedia曰く$10^{32}$は日本語では1溝(こう)と言うらしいので、125溝年(光年じゃないよ)の時を掛ければ000...00という感じで0が160ビット並んだSHA1がお目にかかれる。ただ、そのころには地球すら消滅している。宇宙の寿命はどうやら$10^{100}$程度らしいので、宇宙が死ぬよりは早く見つけられそうだ。

脚注

  1. この記事中では、$NTZ$は(離散)確率変数、$k$は実現値。
  2. 同様に、$M_n$は(離散)確率変数、$m$は実現値。
  3. 並列処理のために連続データが欲しかったのでこのようにした。
  4. 実際には入力データのビット長がさっきよりも長いので少しは変わるはず。