oupoの日記スマートフォン用の表示で見るoupoの日記2019-12-22pattirudon氏のアルゴリズムについて背景ポケモンソード・シールドのレイドバトルと呼ばれるイベントではxoroshiro128+という疑似乱数を使ってモンスターを生成している。これについて、セーブデータを抽出せず、ゲームのプレイから得られる情報からxoroshiro128+の乱数の種を復元できないかということが問題になっていた。*1であるが、状態から乱数値を得るのに算術和を使っており、それが非線形なため復元は難しいのではないかとされていた。驚くべきことにpattirudon氏はそれを可能にした。github.comゲームでのxoroshiro128+の使われ方ゲームのセーブデータにレイドバトルの各巣ごとの64bitのseedが格納されている。seedはレイドバトルのイベントを起こしたり、日付が変わったりするごとに以下の式で更新される。2^64レイドバトルのイベントを起こしたときは、巣のseedと定数を使ってxoroshiro128+の種を与える。モンスターの属性が決定される。その決定のされ方は以下に書かれている。github.comxoroshiro128+についてxoroshiro128+は詳細を省けば以下のような疑似乱数生成器である。F_2^128が固定されており、状態遷移はこのnextで行う。val;}つまり、算術和を使っている。これが問題の困難な点である。2^kで乱数を発生させている。これがm以上の数ならばm未満の数が出るまでgetrand()を繰り返し呼んでいる。上に述べた通り、モンスターの属性がxoroshiro128+で決定されているわけだが、そのすべてがゲーム内からわかるわけではない。暗号化定数やPIDはそれぞれ32bitの情報があり、これが分かれば簡単にseedを復元できたはずだが、それはゲーム内から得られない。分かる情報はV固定箇所(3bit)、個体値(5bitの情報が5つ)、特性(1bit)である。合計29bitの情報が分かる。非線形関数を使っているので、単純な64-29=35bitのしらみつぶしというわけにはいかない。pattirudon氏のアルゴリズムpattirudon氏が気づいたのは「乱数値はseedから非線形だが、その乱数値の一歩手前の足し算する前の値は線形に得られる」という点である。seedから次の情報は線形に得られる。F_2^57が定まる。ゲーム内からわかる情報(足し算の結果)29bitがあり、足し算の片割れの情報28bit分をしらみつぶししてF_2^57の元xを考える。xという方程式を解けばよい。fのkernelの次元が7なので各xについて解は128個求まる。そのそれぞれについて、2匹目のモンスターの情報を使い絞り込む。35bitの空間の探索なので現実的な時間で終了する。話を少し単純化した部分がある。8で決めるため、6未満の値が出るまで乱数を振っている。したがって、本当はこの部分に不定個数の乱数消費がある。(ver.1.0)では1個の消費で済んでいると仮定しているようだ。ここで2個以上消費したseedは検索にヒットしないはずである。それから、seedから57bitの情報を得る部分は、s1の定数があるため、実際には線形ではなく線形写像と並行移動の合成である。これは考える方程式の定数項に影響を及ぼすだけである。2017の19日の記事です。別解ろいしんさんの乱数調整で遊ぼうを中身を見ながら解析します。»プロフィールid:oupo乱数調整やそれにまつわる数理的な話に興味があります。oupo.nejiki@gmail.com)はてなブログをはじめよう!oupoさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。