乱数ジェネレーターを書く方法とMath.randomを予測することは可能ですか？

Math.random（）がどのように機能するか疑問に思ったことはありますか？ 乱数とはどのようなものですか？ そして、インタビューで質問を想像してください-数行のコードで乱数ジェネレーターを書いてください。 それで、それは何ですか、事故であり、それを予測することは可能ですか？



さまざまなITパズルとパズルに非常に興味があり、乱数ジェネレーターはそのようなパズルの1つです。 通常、私の電報チャネルでは、インタビューからあらゆる種類のパズルとさまざまなタスクを作成します。 乱数ジェネレーターに関するタスクは非常に人気があり、信頼できる情報源の1つ、つまりHabréでそれを永続させたかったのです。



この資料は、技術の最先端にあり、ブロックチェーンプロジェクト/スタートアップに参入したいすべてのフロントエンド開発者とNode.js開発者に役立ちます。ここでは、基本レベルであっても、フロントエンド開発者からもセキュリティと暗号化に関する質問が行われます。

擬似乱数ジェネレーターと乱数ジェネレーター

ランダムなものを得るには、エントロピーのソース、つまりランダム性を生成するために使用するある種のカオスのソースが必要です。



このソースは、エントロピーを蓄積し、そこから初期値（初期値、シード）を取得するために使用されます。初期値は、乱数ジェネレーター（RNG）が乱数を生成するために必要です。



擬似乱数生成器は単一の初期値を使用し、その初期値から擬似乱数が生成されます。一方、乱数生成器は常にエントロピーのさまざまなソースから取得される高品質の乱数値を最初に持つ乱数を生成します。

エントロピーは無秩序の尺度です。 情報エントロピーは、情報の不確実性または予測不能性の尺度です。

擬似ランダムシーケンスを作成するには、特定の式に基づいてシーケンスを生成するアルゴリズムが必要であることがわかりました。 しかし、そのようなシーケンスは予測できます。 それでも、Math.random（）がなければ、乱数ジェネレーターをどのように書くことができるか想像してみましょう。



PRNGには、再現可能なアルゴリズムがあります。

RNGは、ノイズから数値を完全に受信することであり、ゼロになる傾向がある計算能力です。 さらに、RNGには、分布を均等化するための特定のアルゴリズムがあります。

独自のPRNGアルゴリズムを発明

疑似乱数ジェネレーター（PRNG）は、要素が互いにほとんど独立しており、与えられた分布（通常は均一）に従う数列を生成するアルゴリズムです。

いくつかの数値のシーケンスを取得し、それらから数値のモジュラスを取得できます。 頭に浮かぶ最も簡単な例。 どのシーケンスを使用し、何からモジュールを使用するかを考える必要があります。 0からNおよびモジュール2に直面している場合、ジェネレーター1および0を取得します。

function* rand() { const n = 100; const mod = 2; let i = 0; while (true) { yield i % mod; if (i++ > n) i = 0; } } let i = 0; for (let x of rand()) { if (i++ > 100) break; console.log(x); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この関数は、シーケンス01010101010101を生成します...疑似ランダムと呼ぶこともできません。 ジェネレーターをランダムにするには、次のビットのテストに合格する必要があります。 しかし、そのようなタスクはありません。 それでも、テストなしでも次のシーケンスを予測できるため、このアルゴリズムは真正面から当てはまりませんが、正しい方向に進んでいます。



しかし、よく知られているが非線形のシーケンス、たとえばPIを使用するとどうなりますか。 そして、モジュールの値として、2ではなく何かを取ります。 モジュールの価値の変化について考えることもできます。 数字Piの数字列はランダムと見なされます。 ジェネレーターは、未知のポイントから始まるPi番号を使用して動作できます。 PIに基づくシーケンスと可変モジュールを使用したこのようなアルゴリズムの例：

 const vector = [...Math.PI.toFixed(48).replace('.','')]; function* rand() { for (let i=3; i<1000; i++) { if (i > 99) i = 2; for (let n=0; n<vector.length; n++) { yield (vector[n] % i); } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、JSでは、PI番号は最大48文字までしか表示できません。 したがって、そのようなシーケンスを予測することは依然として容易であり、そのようなジェネレーターを起動するたびに常に同じ数値が生成されます。 しかし、ジェネレーターは既に0から9までの数字を表示し始めています。



0から9までの数値のジェネレーターを取得しましたが、分布は非常に不均一であり、毎回同じシーケンスを生成します。



Pi番号ではなく、数値表現の時間を取り、この番号を数字のシーケンスと見なすことができます。したがって、シーケンスが毎回繰り返されないように、最後から読み取ります。 PRNGのアルゴリズムの合計は次のようになります。

 function* rand() { let newNumVector = () => [...(+new Date)+''].reverse(); let vector = newNumVector(); let i=2; while (true) { if (i++ > 99) i = 2; let n=-1; while (++n < vector.length) yield (vector[n] % i); vector = newNumVector(); } } // TEST: let i = 0; for (let x of rand()) { if (i++ > 100) break; console.log(x) }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、擬似乱数ジェネレーターのように見えます。 そして、同じMath.random（）はPRNGです。これについては後で説明します。 さらに、最初の数が異なることが判明するたびに。



実際、これらの簡単な例を使用して、より複雑な乱数ジェネレーターがどのように機能するかを理解できます。 また、既製のアルゴリズムもあります。 たとえば、そのうちの1つを見てみましょう。これは線形合同PRNG（LCPRNG）です。

線形合同PRNG

線形合同PRNG（LCPRNG）は、擬似乱数を生成する一般的な方法です。 暗号強度はありません。 この方法は、式で与えられる、ある自然数mを法とする線形反復シーケンスのメンバーを計算することにあります。 結果のシーケンスは、開始番号の選択に依存します-つまり シード。 異なるシード値に対して、異なる乱数シーケンスが取得されます。 JavaScriptでのこのようなアルゴリズムの実装例：

 const a = 45; const c = 21; const m = 67; var seed = 2; const rand = () => seed = (a * seed + c) % m; for(let i=0; i<30; i++) console.log( rand() )
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

多くのプログラミング言語はLPRNGを使用します（ただし、このようなアルゴリズムは使用しません（！））。



前述のように、このようなシーケンスは予測できます。 では、なぜPRNGが必要なのでしょうか？ 安全性の観点から、PRNGは問題です。 他のタスクについて話すと、これらのプロパティはプラスになります。 たとえば、グラフィックスのさまざまな特殊効果やアニメーションの場合、ランダムを頻繁に呼び出す必要があります。 そして、ここで価値の分布とパフォーマンスが重要です！ 世俗的なアルゴリズムは速度を誇ることはできません。



もう1つの特性は再現性です。 一部の実装ではシードを指定できますが、これはシーケンスを繰り返す必要がある場合に非常に便利です。 たとえば、テストでは再生が必要です。 また、安全なRNGが不要な他の多くのものが存在します。

Math.random（）の仕組み

Math.random（）メソッドは、[0、1）の範囲、つまり0（1を含む）から1（1を含まない）の範囲の擬似乱数浮動小数点数を返します。 実装自体は、乱数生成アルゴリズムの初期シードを選択します。 ユーザーが選択またはリセットすることはできません。

Math.random（）アルゴリズムの仕組みは興味深い質問です。 最近まで、つまり49 Chromeまで、MWC1616アルゴリズムが使用されていました。

 uint32_t state0 = 1; uint32_t state1 = 2; uint32_t mwc1616() { state0 = 18030 * (state0 & 0xffff) + (state0 >> 16); state1 = 30903 * (state1 & 0xffff) + (state1 >> 16); return (state0 << 16) + (state1 & 0xffff); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

0〜1の擬似乱数のシーケンスを生成するのは、このアルゴリズムです。

Math.random（）の予測

これは何でいっぱいでしたか？ そのようなクエストがあります： alf.nu/ReturnTrue



タスクがあります：

 { let rand = Math.random(); function random4(x) { return rand === x; } } random4(???)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

関数がtrueを返すには、質問の代わりに何を入力する必要がありますか？ これは不可能のようです。 ただし、これは仕様を調べてPRSP V8アルゴリズムを見た場合に可能です。 かつてこの問題の解決策は、Roman Dvornovによって示されました。

 random4(function(){var A=18030,B=36969,F=65535,Z=16,M=Math,I=M.imul,c=M.random,M=M.pow(2,32),k,d,g=c()*M,h=c()*M;for(k=0;F^k&&(c=I(A,g>>>Z)+k++)&F^h>>>Z;);for(k=0;F^k&&(d=I(B,g&F)+k++)&F^h&F;);for(k=2;k—;g=c<<Z|d&F)c=c/A|c%A<<Z,d=d/B|d%B<<Z;return(g<0?g+M:g)/M}())
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードは、Chrome <49およびNode.js <5のケースの70％で機能しました。RomaDvornovは、いつものように、魔法の奇跡を示しましたが、これはブラウザーの内部メカニズムの深い理解に他なりません。 ローマンがこれらの出来事に基づいてレポートを作成するか、より詳細な記事を書くのを待っています。



ここで何が起こっていますか？ 問題は、アルゴリズムを予測できることです。 これをより明確にするために、ランダムなピクセルの画像を生成できます。 サイトにそのようなジェネレーターがあります 。 ブラウザにMWC1616アルゴリズムが搭載されていた場合、次のようになります。







左のスライドでこれらの均一性を確認しますか？ この画像は、値の分布に問題があることを示しています。 左の写真は、場所によっては値が強くグループ化されており、大きな大きなフラグメントでは抜け落ちていることを示しています。 その結果、数字を予測できます。



Math.random（）を逆にして、特定の時間に得られたものに基づいてどのような数字が作成されたかを予測できることがわかりました。 これを行うには、Math.random（）を使用して2つの値を取得します。 次に、これらの値を使用して内部状態を計算します。 内部状態があると、内部状態を変更せずにMath.random（）の次の値を予測できます。 コードを変更して、次の代わりに前の値が返されるようにします。 実際、これはすべてrandom4タスクのソリューションコードで説明されています。 しかし、その後、アルゴリズムが変更されました（仕様の詳細を読んでください）。 JSが通常の64ビット数で動作するようになると、すぐに壊れる可能性があります。 しかし、それは別の話になります。



新しいアルゴリズムは次のようになります。

 uint64_t state0 = 1; uint64_t state1 = 2; uint64_t xorshift128plus() { uint64_t s1 = state0; uint64_t s0 = state1; state0 = s0; s1 ^= s1 << 23; s1 ^= s1 >> 17; s1 ^= s0; s1 ^= s0 >> 26; state1 = s1; return state0 + state1; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それでも計算および予測は可能です。 しかし今のところ、JSには「長い数学」はありません。 TypedArrayを使用して、特別なライブラリを作成または使用してみてください。 いつか誰かが再び予測変数を書くでしょう。 おそらく、読者になるでしょう。 誰が知っている;）

暗号ランダム値

Math.random（）メソッドは、暗号的に強力な乱数を提供しません。 セキュリティに関連するものには使用しないでください。 代わりに、Web Crypto API（Web Cryptography API）とより正確なwindow.crypto.getRandomValues（）メソッドを使用します。



乱数生成の例：

 let [rvalue] = crypto.getRandomValues(new Uint8Array(1)); console.log( rvalue )
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、PRSP Math.random（）とは異なり、この方法は非常にリソースを消費します。 実際、このジェネレーターはOSのシステムコールを使用してエントロピーのソース（ポピーアドレス、CPU、温度など）にアクセスします。