線形代数によるメルセンヌ・ツイスタのリバースエンジニアリング
メルセンヌ・ツイスタ擬似乱数生成器の内部状態は、出力観測値と線形代数を用いて数学的に再構築できる。本記事では、MT19937の状態ベクトルと遷移行列の構造を解説し、出力を状態の線形関数として表現することで、連立方程式を解いて内部状態を逆算する手法を示す。このリバースエンジニアリングにより、乱数生成器の予測可能性や暗号論的強度の限界が明らかになる。
関連記事
The Mersenne Twister (MT) is a random number generator with strong statistical but weak cryptographic properties. This post demonstrates how to recover the internal state of an MT generator from its output using linear algebra, contrasting this approach with the usual bit twiddling method.
The post explains how to recover the internal state of the lehmer64 random number generator from its outputs, following a similar approach to a previous article on hacking the Mersenne Twister. The lehmer64 generator is noted for its simple implementation and high speed.
The article discusses the probability that a random n × n binary matrix (filled with 0s and 1s) is invertible, exploring different approaches to calculating this probability depending on the underlying assumptions about the entries.
A blog post discusses the probability that a random matrix over a finite field is invertible, noting that this probability converges quickly as the matrix dimension n increases.