Visual Basicでの乱数生成を検証する

Rnd関数とRandomizeステートメントの弱点と対策

VB言語のPRNG関連機能

　VB言語には、PRNG関連の関数/ステートメントとしてRnd()とRandomizeの2つがあります。

Rnd()関数

　Rnd()関数は、0 <= Rnd() < 1であるような単精度浮動小数点数列を出力します。関数として使えるほか、VBステートメントの形で（1つの行に単独で）使用してもコンパイル上の問題は起こりません。ただ、本来は関数ですから、ステートメントとして使用した場合、コンパイラは返されてくる値を廃棄します。本稿では一貫してRnd()という表現を使用しますが、実用コードや、サンプルコード、コード例などでは、Rndという表現も見かけるかもしれません。

Randomizeステートメント

　Randomizeステートメントは、新しいシード値の下でRnd()数列を開始します。シード値の既定値は、現在のTimer()関数値（下記参照）です。Randomizeステートメントによって新しいシード値の下で数列を生成するには、そのRandomizeステートメントの前にRnd -1を呼び出してください（本稿では、シード値の再設定の例を示すときに"Rnd -1"としていますが、この-1は任意の負の値でかまいません）。

　シード値の再設定については、Microsoftのサポート技術情報に詳しい記事があります。

Timer()関数

　Timer()関数は、0.00から86400.00までの値を返します。これは真夜中から始まる1日の秒数を表していて、精度は1/100秒です。計算すると、一意のTimer()値が864万個あることがわかります。

Microsoft社の説明

　ありがたくもMicrosoft社がドキュメンテーションを提供してくれていますが、このヘルプファイルや製品文書の品質は、全体として誉めてよい出来映えだと思います。Randomizeのシード値とVB PRNG機能について、Microsoft社は次のように言っています。

クラシックVBのヘルプ（Randomize）

　オンラインヘルプ（VBヘルプファイル、msdn.microsoft.comとも）によると、Randomizeステートメントのシード値は「任意の数式」となっていますから、実に膨大な範囲のシード値を使用できます。

• 数値リテラル
• 数値変数（バイト、整数、長精度、単精度、倍精度、通貨、10進）
• 日付/時刻リテラルと変数（内部的には倍精度値として保管）
• 数値に還元できる式
• 数値を返す関数

VB.NETのPRNGヘルプ（RndとRandomize）

　Rnd()関数とRandomizeステートメントに関するVB.NETドキュメントには、新しい記述があります。

セキュリティ上の注意

　RandomizeステートメントとRnd関数は、シード値を得て、そこからある有限範囲内の数値を生成するものですから、数値生成に使われるアルゴリズムを知っている人物なら、結果を予測できる場合があります。したがって、暗号に使う乱数の生成にRandomizeステートメントとRnd関数を使うことは望ましくありません。

　私は暗号化の作業をしていたつもりはありませんが、行IDを長いランダム文字列として表現することにより、アンケートキーの値を簡単にはわからないようにしようと思っていました。

　Randomizeステートメントに関するオンラインドキュメントは、この「セキュリティ上の注意」の部分を除き、VB 3のオンラインヘルプ以来変わっていません。

実際に何が行われるのか

　ここで、VB PRNGの舞台裏を見ておくことにしましょう。VB PRNGは線形合同式法の乱数発生器です。これはつまり、次の公式に従い、前の値に基づいて次の値を数学的に導く、ということです。

Rk+1 = (Rk* L + M) Mod N

Rnd()の中身

　Rnd()は次の公式を使用します。

x1 = (x0 * a + c) MOD (2^24)

　ここで、a = 1140671485、c = 12820163です。

　x0の既定値は327680（&h50000）です。まずRandomizeステートメントを呼び出してからRnd()関数を使用しないと、同じ数列が繰り返されるのは、そのためです。

　2^24による除算に注意してください。ここでPRNGの「周期」が決まります。Rnd()関数から得られる数列は、1677万回の呼び出しで最初に戻ります。近所に住む暗号の専門家と話をしていて、これはPRNGに内在する深刻な欠陥だろうという結論になりました。しかし、私は数列の先頭にある30項目しか使っていませんでしたから、あまり気にしていませんでした。

　x1値はまず2^24で割られ、0 <= Rnd() < 1の値としてVisual Basicプログラムコードに戻されます。これから後はVBプログラマ次第です。VBプログラマは、返された値をアプリケーションに適した大きさと範囲に変換しなければなりません。

Randomizeの中身

　いろいろと文献を読みあさったあげく、私はRandomizeステートメントに弱点があり、その弱点はRnd()関数より深刻であることを発見しました。Randomizeステートメントの内部では、次のことが起こります。

1. 与えられたシード値が単精度データ型に変換されます。Rnd()関数が単精度データ型を返すところからも、これは理解できます（Timer()が返す値は単精度データ型で、変換が不要です）。
2. 次に、単精度データ型のシード値が、次のXOR演算によって2バイトのシード（TwoByteSeed）値に変換（mosh）されます。

TwoByteSeed = [byte1 XOR byte3] [byte2 XOR byte4]

3. この2バイトに対してもう一度XOR演算が行われます。演算内容は、最初に与えられたシード値の符号によって異なります。次のコードを見てください。

If originalseed < 0 Then
    TwoByteSeed = TwoByteSeed XOR &h06C0
Else
    TwoByteSeed = TwoByteSeed XOR &h0240
End If

　Randomizeステートメントで得られるシード値は単精度（浮動小数点）データ型ですが、そのうちの2バイトだけがシード値として使われます。

VB PRNG内部の仕組みに関する参考資料

• How Visual Basic Generates Pseudo-Random Numbers for the RND Function
• Microsoft Visual Basic: Pseudo Random Number Generator
• http://www.math.ucalgary.ca/~ware/amat483/papers/
random_number_generators.pdf

開発者にとって何を意味するか

　VB PRNGが抱える弱点と問題は、次のようにまとめられます。

• Rnd()数列の周期は1677万項目です。ディスク消去ユーティリティで使うような非常に長い乱数列を作る必要があるときは、こんな短い周期ではとても間に合いません。ただ、書き込みの回数を増やすことで、この欠陥をフォローできる可能性もあります。暗号操作によっては、この短い周期が制約となります。
• Rnd()数列は線形合同式法の実装にすぎないので、比較的簡単に破れます。
• Rnd()の前にRandomizeステートメントを呼んでおかないと、最初の値がいつも同じになります。
• Randomizeステートメントの前にRnd -1（または任意の負数）がないと、シード値がリセットされません。つまり、Randomizeステートメントが常に初期の目的と働きを果たせるとはかぎりません。
• Timer()値は1日周期で繰り返されるので、Randomizeステートメントで同じシード値が再使用される可能性があります。
• しかし、VB PRNGの最大の弱点は、可能な（mosh後の）一意のシード値が64Kほどしかないことです。これは、一意の乱数列の起点が64K個しかないことを意味します。

　Randomizeステートメントの既定のシード値であるTimer()値を用いても、下記に示すとおり、事態はあまり改善されません。私が自分のアプリケーションで経験したとおり、一意であることが保証されたシード値を使用しても役に立ちません。

　衝突の確率を見積もるには、与えられるシード値の総数を64Kで割ってみてください。これが衝突の平均的発生回数です（「衝突」とは、反復数列の発生のことを指します）。

タイマシード値の衝突統計

　以下に示す数字は、Timer()関数値に基づいてシード値を実際に生成し、それをRandomizeステートメントに与えて、同じ値がいくつ生成されたかを数えてみた結果です。

24時間の衝突数	8AMから5PMまでの衝突数
総数 = 8574465	総数 = 3174465
最大 = 134	最大 = 50
最小 = 128	最小 = 47
平均 = 130.83595	平均 = 48.438492
シード値総数 = 8640001	シード値総数 = 3240001

何ができるか/何をすべきか

　アプリケーションでVB PRNGを使用すれば、いつかは同じ数列が発生する――これは誰にも異論のないところでしょう。

　では、身を守るために何をすべきで、何ができるのでしょうか。

1. Rnd()関数を使用しているVB/.NETコードがないかを確認してください。
2. 衝突と重複数列の影響を予測してください。重複数列が現れても問題のないアプリケーション（部分）かもしれません。
3. 表にランダム数列を追加するときは、当該列に一意のインデックスを追加してください。重複キー状態が発生するので、それを処理するためのコードも追加します。
4. 潜在的な問題が予測できるときは、コードを少しいじって衝突の可能性を小さくできないかを考えてください。労力と効果を天秤にかける必要があります。衝突の可能性が小さいか、影響が軽微なら、わざわざコードを変更する必要などないかもしれません。しかし、修復の費用（会社や製品の評判の下落、サービス水準保証による罰則、プログラマへの緊急支払い、など）が甚大なら、コード変更を考えるべきでしょう。Rnd()とRandomizeを使い続けながらとりあえずできることを、近いうちに記事にまとめるつもりです。
5. 本稿を読み、コード分析を行った結果、お使いのVBアプリケーションに時限爆弾が見つかったときは、大がかりなコード修正が必要です。その大がかりな修正には、VB PRNG言語機能を別のPRNGで置き換えることが含まれるかもしれません。この点にも、今後の記事で触れるつもりです。
6. 古典的VBアプリケーションをもう.NETフレームワークに移行させたという開発者も、Microsoft.VisualBasic名前空間には同じ弱点が存在するので要注意です。ここでも、Rnd()とRandomizeはWin32版とまったく同じ動作をします。ただ、幸いなことに、できることの選択肢もいくつか増えています。Microsoft社は、次のどちらかの.NET名前空間を使うよう勧めています。
• System.Security.Cryptography
• System.Random

注

　この2つの.NET名前空間では、生成される（擬似）乱数列が異なります。

将来への期待（次回記事の予告）

　次回の記事では、わずかな修正で済ませる方法を詳しく紹介します。たとえば、次のような方法です。

• 一意のシード値をバイト値に分解し、そのバイト値シードから複数の数列を導く
• Rnd()数列の使い方を変える
• 複数のRnd()数列を使用する

　Rnd()とRandomizeを別の何かで置き換える方法（大がかりな修正）も紹介します。たとえば、次のような方法が考えられます。

• GUIDを生成し、使用する
• 擬似乱数の発生源を別に求める（Web上を探せば、立派なライブラリやサードパーティのルーチンが見つかります。Knuthのアルゴリズムをいくつか試してみてもよいでしょう）
• .NET名前空間を使用する