第5世代でペラップの鳴き声だけから64bit LCGのseedを見つける
概要
Mathematica (or Wolfram Cloud)を使ったら、ペラップの鳴き声だけから64bit LCGのseedを特定できた。 これは64bit LCGの上位5bitの連続した値を13個観測してseedを十分現実的な時間で復元したことになる。
内容
第5世代のポケモンでは64bitの線形合同法 (LCG)を疑似乱数の一部に使っている。 ペラップというポケモンのおしゃべりという特別な技において、マイクで収録した音を再生でき、その音程は再生するたび変わる。そこにLCGが使われている。 その音程の情報だけからLCGのseedを特定できたというのが今回の内容である。 計算時間はWolfram Cloud上でおよそ14秒である。 なお、このゲームのseedは現在時刻などのパラメータから決定されており、それはツールから完全に再現可能になっているので、このゲームの乱数調整には今回の結果はあまり影響を与えないと考えられる。
実践
まず、ペラップの鳴き声から乱数値を得る。13回の鳴き声が必要だ。 これはすでにツールがある。
このツールは周波数で表示するので、それを0~31の値に変換しておく。たとえば次のようなRubyのスクリプトでできる。
list = " 988 1016 1011 1058 1020 1042 1081 899 1040 951 1030 961 953 " a = list.split("\n").select{|x| x != "" }.map(&:to_i) mi = 1 * 880 ma = 1.25 * 880 p a.map{|x| (32 * (x - mi) / (ma - mi)).floor }
これをMathematica (or Wolfram Could)に入れる。 まず必要となる関数を定義しておく (汚い定義だが)。
SolveLCG[a_, c_, b_, r_, h1_, h2_, h3_, h4_, h5_, h6_, h7_, h8_, h9_, h10_, h11_, h12_, h13_] :=
With[{M = 2^b, m = 2^(b - r)},
Solve[{ s == l1 + h1 m,
a s+c == l2 + h2 m + k2 M,
a^2 s+(1+a)c == l3 + h3 m + k3 M,
a^3 s+(1+a+a^2)c == l4 + h4 m + k4 M,
a^4 s+(1+a+a^2+a^3)c == l5 + h5 m + k5 M,
a^5 s+(1+a+a^2+a^3+a^4)c == l6 + h6 m + k6 M,
a^6 s+(1+a+a^2+a^3+a^4+a^5)c == l7 + h7 m + k7 M,
a^7 s +(1+a+a^2+a^3+a^4+a^5+a^6)c== l8 + h8 m + k8 M,
a^8s+(1+a+a^2+a^3+a^4+a^5+a^6+a^7)c == l9 + h9 m + k9 M,
a^9s+(1+a+a^2+a^3+a^4+a^5+a^6+a^7+a^8)c == l10 + h10 m + k10 M,
a^10s+(1+a+a^2+a^3+a^4+a^5+a^6+a^7+a^8+a^9)c == l11 + h11 m + k11 M,
a^11s+(1+a+a^2+a^3+a^4+a^5+a^6+a^7+a^8+a^9+a^10)c == l12 + h12 m + k12 M,
a^12s+(1+a+a^2+a^3+a^4+a^5+a^6+a^7+a^8+a^9+a^10+a^11)c == l13 + h13 m + k13 M,
l1 >= 0, l1 < m,
l2 >= 0, l2 < m,
l3 >= 0, l3 < m,
l4 >= 0, l4 < m,
l5 >= 0, l5 < m,
l6 >= 0, l6 < m,
l7 >= 0, l7 < m,
l8 >= 0, l8 < m,
l9 >= 0, l9 < m,
l10 >= 0, l10 < m,
l11 >= 0, l11 < m,
l12 >= 0, l12 < m,
l13 >= 0, l13 < m},
Integers]]
そして次のような文を実行する。
SolveLCG[6726279311198226789, 2531011, 64, 5, 15, 19, 19, 25, 20, 23, 29, 2, 23, 10, 21, 11, 10]
6726279311198226789, 2531011, 64, 5,までは固定でその後の引数を先ほどの0-31の値の列を入れる。
これで実行すると解が出る。その中のsがseedである。
出たseedが本当にあっているか確かめたい場合は次のようなペラップの鳴き声の音程のリスト出力するプログラムで、13回目以降も一致しているか確かめればよい。
A = 0x5d588b656c078965 C = 0x269ec3 M = 2**64 s = 8978365926194661437 50.times do |i| x = s >> (64 - 13) x = x.to_f / 8192 puts "%03d %02d %s" % [i, (1 + x * 0.25) * 880, "*" * (x * 10).to_i] s = (s * A + C) % M end
参考文献
Mathematicaのプログラムは上の文献を参考にした。
追記 (2020/9/7)
Wolfram言語のコードが汚かったので任意個数の入力を取れるバージョンを作成。
SolveLCG[a_, c_, b_, r_, h_] :=
With[{M = 2^b, m = 2^(b - r)},
Solve[Flatten[Map[Function[i,{Mod[a^(i-1), M] s +Mod[ Sum[a^j, {j, 0, i-2}]c, M] == Subscript[l, i] + h[[i]] m+If[i > 1, Subscript[k, i]M, 0] ,Subscript[l, i]>= 0, Subscript[l, i] < m}], Range[Length[h]]]], Integers]]
これで
SolveLCG[6726279311198226789, 2531011, 64, 5, {15, 19, 19, 25, 20, 23, 29, 2, 23, 10, 21, 11, 10}]
などとすればよい。
