しばたテックブログ

気分で書いている技術ブログです。

Get-Randomで使われている乱数生成アルゴリズムについて調べてみた

PowerShell

PowerShellで気軽に乱数を生成できるGet-Randomコマンドレットですが、乱数生成に使われるアルゴリズムについては一切ドキュメント化されていません。

とりあえずで使う分には問題ないでしょうが真面目に乱数を扱う場合にアルゴリズムが不明なのは致命的だと思います。

そこで本エントリではGet-Randomの実装から内部で使用されているアルゴリズムを調べてみることにしました。

Get-Randomの実装について

Get-Randomコマンドレットの実体はMicrosoft.PowerShell.Commands.Utility.dllにあるGetRandomCommandクラスになります。
ILSpy等でこのクラスの中身を調べてみます。

PowerShell 2.0 〜 4.0 の実装

Get-RandomコマンドレットはPowerShell 1.0には存在せずPowerShell 2.0から導入された機能です。
PowerShell 2.0 〜 4.0の実装では乱数生成にSystem.Randomクラスが使われています。

PowerShell 5.0 ～ 5.1 の実装

PowerShell 5.0からの実装では乱数生成にMicrosoft.PowerShell.Commands.PolymorphicRandomNumberGeneratorクラスが使われています。

このクラスはPowerShell内部のInternalなクラスであり、-SetSeedパラメーターを指定してシードを指定した場合はSystem.Randomクラスを、シードを指定しない場合はSystem.Security.Cryptography.RandomNumberGeneratorクラスを使って乱数を生成する様になっています。

ちなみにSystem.Security.Cryptography.RandomNumberGeneratorクラスは抽象クラスであり、PolymorphicRandomNumberGeneratorクラス内ではRandomNumberGenerator.Create()メソッドを使用してインスタンスが生成されています。
このRandomNumberGenerator.Create()メソッドはmachine.configに特別な設定が無い限りはSystem.Security.Cryptography.RNGCryptoServiceProviderクラスのインスタンスを生成します。

なのでシードを指定しない場合はSystem.Security.Cryptography.RNGCryptoServiceProviderクラスを使って乱数を生成していると言い換えて良いと思われます。

ざっくりとしたまとめ

ここまでの内容をざっくりまとめると、

  • PowerShell 2.0 ～ 4.0

    • シード指定あり => System.Randomクラスで乱数生成
    • シード指定なし => System.Randomクラスで乱数生成

  • PowerShell 5.0 ～ 5.1

    • シード指定あり => System.Randomクラスで乱数生成
    • シード指定なし => System.Security.Cryptography.RNGCryptoServiceProviderクラスで乱数生成

となります。

各クラスで使用されるアルゴリズムについて

続いてSystem.RandomおよびSystem.Security.Cryptography.RNGCryptoServiceProviderクラスで使用されるアルゴリズムについて説明していきます。

正直なところ、私は乱数生成アルゴリズム自体についてはずぶの素人なので、あくまでも紹介する程度にとどめておきますがその点はご容赦ください。

System.Randomクラス

MSDNに記載されていますが、System.Randomクラスの乱数生成はKnuthの減算法に基づいているそうです。

私は未読なのですが、このアルゴリズムの詳細はThe Art of Computer Programmingの2巻に載っているとの事です。

The Art of Computer Programming (2) 日本語版 Seminumerical algorithms Ascii Addison Wesley programming series

The Art of Computer Programming (2) 日本語版 Seminumerical algorithms Ascii Addison Wesley programming series

  • 作者: Donald E.Knuth,有沢誠,和田英一,斎藤博昭,長尾高弘,松井祥悟,松井孝雄,山内斉
  • 出版社/メーカー: アスキー
  • 発売日: 2004/10
  • メディア: 単行本
  • 購入: 1人 クリック: 80回
  • この商品を含むブログ (44件) を見る

また、直接Reference Sourceの内容を見て実装を確認することもできます。

System.Security.Cryptography.RNGCryptoServiceProviderクラス

MSDNの記載によればこのクラスでは暗号化サービスプロバイダー(CSP)による実装で乱数生成されるとの事です。
CSPとは何ぞやといった話はCSP（Cryptographic Service Provider）についてを見ていただくとわかり易いかと思います。

先述の記事をみればわかる様にCSPには複数のタイプがありますが、MSDNを見てもどのタイプが使われているかは記載されていません。
これについては以下のフォーラムのスレッドにもある様に直接ソースを見て判断するしかない様です。

RNGCryptoServiceProviderクラスの乱数生成アルゴリズム

Reference Sourceはこちらになります。

このソースを見る限りでは、コンストラクタでCspParametersを明示しないデフォルト設定では、CSPのタイプはDefaultRsaProviderTypeという定数が指定され、これは、

internal const int DefaultRsaProviderType = Constants.PROV_RSA_AES;

と定義されているのでPROV_RSA_AESが使用される様です。

Get-Randomコマンドレット内でのRNGCryptoServiceProviderクラスの利用についてもCSPタイプは明示されていないので、恐らくはPROV_RSA_AESが使われているものと推測されます。

このあたりはかなり自信が無いので間違いがあればご指摘ください。

Get-Randomのランダム性と予測可能性について

Get-Randomのランダム性

Get-Randomのランダム性についてはPowerShell Magagineの以下の記事が役に立ちそうです。

www.powershellmagazine.com

こちらの記事ではGet-RandomコマンドレットとRNGCryptoServiceProviderクラスを直接使って生成したランダムなバイト列のエントロピーを計測することでGet-Randomのランダム性を検証しています。
検証の結果によればGet-RandomコマンドレットとRNGCryptoServiceProviderクラスのエントロピーは同程度にランダムなのでGet-Randomコマンドレットも乱数生成の候補になり得るとの事です。

ここで私見を述べれば、RNGCryptoServiceProviderクラスは暗号用の乱数生成なので、Get-Random(= System.Randomクラス)とはそもそもの用途が違うだろうと思っています。
単純にランダムな値を生成する分にはGet-Randomコマンドレットは十分に有用ですが、暗号用の乱数にはPowerShell 5.0までは使えないという結論になるのではないでしょうか。

あと、せっかくなので私も手元の検証環境でPowerShellのバージョン毎にこのエントロピーを計測してみました。
その結果が以下になります。

# PowerShell 2.0 な環境 ( Windows Server 2008 R2 )
CryptoRngAverage GetRandomAverageEntropy
---------------- -----------------------
7.95469907847973        7.95423735540815

# PowerShell 3.0 な環境 ( Windows Server 2008 R2 )
CryptoRngAverage GetRandomAverageEntropy
---------------- -----------------------
7.95364381891335        7.95460867915008

# PowerShell 4.0 な環境 ( Windows Server 2012 R2 )
CryptoRngAverage GetRandomAverageEntropy
---------------- -----------------------
7.95470953753356        7.95500104809818

# PowerShell 5.0 な環境 ( Windows 8.1 64bit版 )
CryptoRngAverage GetRandomAverageEntropy
---------------- -----------------------
7.95424647998367        7.95434225952585

PowerShell 5.0は内部でRNGCryptoServiceProviderクラスが使われる様になっているのでエントロピーが同程度になるのは当たり前ですが、他のバージョンも確かに同程度でした。

Get-Randomの予測可能性

Get-Randomコマンドレットではシードを明示した場合は常にSystem.Randomクラスを使用するので乱数は予測可能になります。
この点ついてはそういうものなので特に問題は無いでしょう。

また、PowerShell 2.0～4.0ではシードを指定しない場合もSystem.Randomクラスを使い、この場合内部的にはSystem.Randomクラスをデフォルトコンストラクタで生成しているためシードにはSystem.Environment.TickCountの値が設定さています。

このためGet-Randomコマンドレットを同時刻に複数同時に呼び出すと同じ乱数が生成されてしまいます。
以下の様な単純なバッチファイルでも結構な頻度で乱数値が一致する*1ので注意してください。

REM 同時に2つのPowerShellプロンプトを起動してGet-Randomを実行
start powershell.exe -NoExit -NoLogo -command "&{ 'Tick:' + [Environment]::TickCount; Get-Random }" 
start powershell.exe -NoExit -NoLogo -command "&{ 'Tick:' + [Environment]::TickCount; Get-Random }"

PowerShell 2.0な環境で試してみた結果(乱数値が一致しない場合も当然あります) f:id:stknohg:20160209181126p:plain

PowerShell 5.0ではRNGCryptoServiceProviderクラスを使う様に実装が変わっているのでこの様な問題は起きません。

最後に

ざっくりとですがGet-Randomコマンドレットで使われる乱数生成アルゴリズムについて調べてまとめてみました。

内部で使われているのがSystem.RandomおよびSystem.Security.Cryptography.RNGCryptoServiceProviderクラスですので.NET Frameworkの乱数生成で注意すべき点はそのままPowerShellにも当てはまります。

追記

PowerShell 6.0についての続きを書きました。

blog.shibata.tech

*1:当然ですが実行環境にかなり依存します...