Hatena::ブログ(Diary)

oupoの日記

2016-12-10

出力関数が線形な場合のTinyMTにおいて連続する4つの乱数値からstateを得る

18:12

疑似乱数TinyMTの逆算について考えます。Page not found · GitHub Pagesの続きともいえるような内容です。

上の記事はstateから一つ前のstateを計算するという話でしたが、この記事では連続する4つの乱数値からstateを得ることを考えます。

TinyMTは何も設定しなければ出力関数非線形ですが、LINEARITY_CHECKをONにすると線形になります。その場合、連続する4つの乱数値からstateを得るのはただの(F_2係数の)連立一次方程式を解くだけなので簡単にできます。

SageMath Cloudで動かせるプログラムを作りました。

動かす場合、メニューのKernel→Change Kernel→SageMath 7.4と選ぶ必要があるかもしれません。

なお、TinyMTの実装はTinyMT/tinymt32.h at master ? MersenneTwister-Lab/TinyMT ? GitHubのtinymt32_next_stateとtinymt32_temperを参照。

LINEARITY_CHECKがOFFの場合、つまり出力関数非線形な場合は乱数値からstateを得るのは現実的な実行時間じゃ無理だろうなと思っていました。しかしそれをさき (@water_blow)さんがくつがえしてくれました。

そうなんです。LINEARITY_CHECKがOFFのとき以下のように算術加算が使われていて非線形なので逆算は不可能に見えます。しかし下位1bitを見ればxorしていることと変わらないので上のツイートのように逆算が可能になります。

	inline static uint32_t tinymt32_temper(tinymt32_t * random) {
		uint32_t t0, t1;
		t0 = random->status[3];
#if defined(LINEARITY_CHECK)
		t1 = random->status[0]
			^ (random->status[2] >> TINYMT32_SH8);
#else
		t1 = random->status[0]
			+ (random->status[2] >> TINYMT32_SH8);
#endif
		t0 ^= t1;
		t0 ^= -((int32_t)(t1 & 1)) & random->tmat;
		return t0;
	}

全く気が付きませんでした。すごいですね。さきさんがこの件について記事を書いてくれることを期待してみます。

追記(2016/12/11)

さきさんが書いてくれました。

追記(2016/12/11)

こちらでも連続した127個の乱数の下位1bitからstateを算出する行列を計算しました。

さきさんのツールと結果が一致します。