japan.internet.com翻訳記事

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

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

Mark Hutchinson[著] / japan.internet.com[訳]

2005/12/14 12:00

VBの擬似乱数発生器（PRNG）の動作は、あまり優秀ではありません。本稿では、PRNG関連の関数/ステートメントである、Rnd()とRandomizeの弱点・問題点を検証し、その対応策を提案します。

はじめに

　私があるクライアントのためにMicrosoft Accessアプリケーションを書き、その使い方を新しいユーザーに指導しているときのことでした。そのアプリケーションで実に予想外のことが起こったのです。普段なら、どこかでまぎれ込んでしまったエラーを血眼で探すところですが、今回ばかりは、驚きと戸惑いの方が勝りました。こんなことが起こるはずはないのです。しかし、現実にこの目で見たのですから否定できません。もちろん、こういう場合に最優先すべきは、こんなことも起こりうるのだという可能性を受け入れ、（別の方法を使って）一時しのぎのパッチを作成することです。幸い、私が作ったパッチはうまく働いて、その日の業務に支障は出ませんでした。最悪の事態が避けられたことに安堵しながらも、私はまだ信じられない気持ちでクライアントのオフィスを後にしました。次になすべきは、コンピュータ科学者として原因を究明することです。以下に記すのは、私の研究の記録であり、VB言語のPRNG機能を使用するすべてのVB開発者への警告です。

　PRNGとは何だ、とお尋ねですか。Visual Basicの新しいステートメントか、機能か、被参照クラスか。いえ、そのどれでもありませんし、新種のポテトチップでもありません。これは「Pseudo-Random Number Generator」（擬似乱数発生器）の頭字語です。PRNGとVBのPRNG機能については後で説明することにして、まず、Microsoft AccessビジネスアプリケーションになぜPRNG機能が必要かをお話しておきましょう。

アプリケーション

　数年前、私は企業幹部向けのあるアンケートアプリケーションに、インターネットブラウザ経由で回答できる機能を付け加えました（もともとは、すべてがアンケート用紙で行われていて、回収した用紙を典型的なデータエントリ方式でデータベースアプリケーションに打ち込んでいました）。このアプリケーションのオペレータは、まずセットアップデータを入力し、Excelデータをインポートしてから、質問事項を（LAMP）サーバに送信します。すると、URLと当該アンケートへのキーを記した電子メールが回答者宛てに送信されます。調査期間終了後に、アンケートへの回答が（完全な回答も不完全な回答も共に）Microsoft Accessデータベースにダウンロードされ、そこから詳細なプロファイルが作成されます。

アプリケーションの構造1（処理フロー）

Webアンケートテーブルに行を追加する
新しく挿入された行のプライマリキーをVB PRNGのシード値とする
Rnd()を繰り返し、文字列から30文字を拾い出す
新しく挿入された行をランダム文字列で更新する
MySQLテーブルデータをLAMPサーバにセキュアコピーする
データインポートPHPスクリプトを呼ぶ

アプリケーションソースの構造1（新規レコード）

　ここが問題部分（VBのPRNG不具合のためにアプリケーションがエラーを生じた場所）です。エラーは2番目の.Updateメソッドで、私がrs!Email_IDに値を指定したときに起こりました。Email_ID列は一意のインデックスになっていて、我ながら、よくぞこの列に一意性を強制しておいた、と思いました（なにしろ、MySQLデータベースでの問題分析はずっと困難ですから）。

With rs
    .AddNew
        !Source_ID = lngSourceID
        !Source_Name = strSourcename
        !Target_ID = Me.cboTarget.Column(0)
        !Target_Name = Me.cboTarget.Column(2) & " " & _
            Me.cboTarget.Column(3)
        !Survey_Name = Me.cboSurvey.Column(1)
        !Expire_Date = Format(CDate(Me.txtSurveyExpireDate), _
            "YYYYMMDD")
    .Update
End With
rs.Bookmark = rs.LastModified
rs.Edit
    rs!Email_ID = EmailID_For_SID(rs!S_ID)
rs.Update

Export_Survey_For_Person rs!S_ID

アプリケーションソースの構造2（ランダム文字列の生成）

　パラメータ（＝rowID）を新しいPRNG文字列のシード値に使い、ランダム文字列を作成します。

Public Function EmailID_For_SID(parmS_ID) As String
    Dim strTemp As String
    Dim intLoop As Integer
    Dim intCharPosn As Integer
    Dim strCharBase As String
    strCharBase = "01234ABCDEFGIJKLMNOPQRSTUVWXYZ" & _
        "abcdefghijklmnopqrstuvwxyz56789"
    strTemp = String(30, "A")

    Rnd -1               'resets the random seed
    Randomize (parmS_ID) 'initialize the seed

    For intLoop = 1 To Len(strTemp)
        Mid$(strTemp, intLoop, 1) = _
            Mid$(strCharBase, Rnd() * Len(strCharBase) + 1, 1)
    Next

    EmailID_For_SID = strTemp
End Function

　アンケートIDに長い整数値を使うことは、セキュリティ上の理由から好ましくありません。万一打ち間違ったときに、他者のアンケート回答が見えてしまう危険があるからです。回答者である企業幹部には、同僚や上司を評価するよう求められることもあり、これなどは特に秘密を要する事柄です。クライアントにとっても業界にとっても貴重なデータですから、万一、競争相手がそれを見たり（ましてや変更したり）できてしまうと、私のクライアントにとってきわめて不都合な状況を生じかねません。そこで、我々は、英字（大文字と小文字）と数字から成る30桁のID文字列を使うこととし、それを作り出すためのPHPアプリケーションを書きました。

　VB PRNGに与えるシード値には、Webアンケートテーブルにいま挿入したばかりの行のキー値（自動インクリメント値）を使い、30回繰り返して、アルファベットと数字の文字列から30個の文字を拾い出します。シード値の幅を広げるため、表の自動インクリメントフィールドの既定値を「順次」から「ランダム」に変更もしました。これで、プライマリキー値の範囲が「1～21.4億」から「-21.4億～21.4億」に広がります。ところが、私の書いたアプリケーションは、2つの行の自動インクリメント値からまったく同じ30桁のランダム文字列を作り出したのです。2つのランダム文字列が一致することなど起こりえない……と、少なくとも私はそう思っていました。私が発見したことは、映画『ロスト・イン・スペース』ならロボットが両腕を振り回し、「危険、ウィル・ロビンソン！衝突間近！」と叫ぶほどの事態だったと言えるでしょう。

PRNGの紹介

　この問題を徹底的に理解し、パッチによらない迂回策を開発するために、私はPRNGとVB PRNG機能の仕組みを研究しました。私の作ったパッチを当てれば、衝突のためにアンケートができなくなる危険は確かに減りますが、私としては、「パッチでもだめだから、すぐになんとかしろ」という電話が半狂乱のユーザーからかかってくることを、絶対に避けなければなりません。研究の結果、3つの重要なことがわかりました。

PRNGを理解するうえで鍵となるのは、先頭の「P」の部分です。これは「Pseudo（擬似）」を意味します。ソフトウェアで完全にランダムな文字列を作り出すことはできません。ランダムに見えても、実は違います。コンピュータを使うかぎり、せいぜい「ランダムに近い」ものができるだけです。コンピュータ世界で人間にできる精一杯のところは、「できるだけランダムに近づく」ということでしょう（真にランダムなデータソースとしては、原子核崩壊を測定するガイガーカウンタや大気状態のセンサがあります）。
一口にPRNGと言っても、良いPRNGも悪いPRNGもあり、それぞれの（擬似）ランダム性を測定する方法も考案されていいます。
VB PRNGの動作は、あまり優秀ではありません。

PRNGはどこで使用されるか

　PRNGの3大使用場所は、セキュリティ、統計、ゲームです。PRNGがどの方面に適用されるかは本稿のメインテーマではありませんが、それを知っておけば、VBコードのどこを探せばPRNGが見つかるかを予測するうえで参考になるでしょう。

セキュリティでのPRNG使用

　最も安全とされるデータ暗号化法の1つに、ワンタイムパッド法があります。送信者と受信者の双方が同じ乱数列（メッセージと同サイズ）を使ってメッセージを暗号化すれば、その乱数列を知らないかぎり、解読の手がかりが存在せず、誰もメッセージを解読できません（この方法では、メッセージごとに異なる乱数列を使用しなければならないことが問題となります）。また、ハードディスクから機密データを消し去るときにも、ランダムデータの生成にPRNGが利用されます。セキュリティ場面でのPRNGの利用例を列挙すると、リストは膨大なものになり、ここに示した2例はほんの一部にすぎません。

統計でのPRNG使用

　統計でのPRNG使用と言えば、モンテカルロ法が最も有名ですが、科学研究の分野では他にもいろいろな使い方があります。たとえば、遺伝的アルゴリズムでは、育種のための雌雄ペアの選択や育種方法の決定にPRNGが使用されます（ここでは、「統計」をかなり広い意味に使っています）。

ゲームでのPRNG使用

　新米プログラマの頃に誰もが書くアプリケーションがゲームです。三目並べゲームでのマスの選択、トランプのシャッフル、サイコロ振りのどれにもPRNGが使用されます。カジノでも、電子ゲームにはPRNGを使用しています。PRNGがどう動作しようと自分には関係ないと思う人は、テレビのゲームショー「Press Your Luck」の制作者の立場になって考えてみてください。

PRNGの研究に役立つ資料

『The Art of Computer Programming, Vol. 2 Seminumerical Algorithms』 Knuth, D. E. 著、Addison-Wesley、1981年
『Applied Cryptography』 Bruce Schneier 著
役に立ちそうなPRNG関連WebサイトのURLリスト

pseudorandom_number_generator.htm

http://www.cacr.math.uwaterloo.ca/hac/

会員登録無料すると、続きをお読みいただけます

新規会員登録無料のご案内

・全ての過去記事が閲覧できます
・会員限定メルマガを受信できます

メールバックナンバー

新規会員登録無料

次のページ
VB言語のPRNG関連機能

この記事は参考になりましたか？

印刷用を表示

japan.internet.com翻訳記事連載記事一覧: 式ツリーからラムダ式を構築する

Microsoft Visual Studio 2010の紹介

分散DBMS「Mnesia」の並列処理

もっと読む

この記事の著者: japan.internet.com（ジャパンインターネットコム）

japan.internet.com は、1999年9月にオープンした、日本初のネットビジネス専門ニュースサイト。月間2億以上のページビューを誇る米国 Jupitermedia Corporation (Nasdaq: JUPM) のニュースサイト internet.com や EarthWeb.com からの最新記事を日本語に翻訳して掲載するとともに、日本独自のネットビジネス関連記事やレポートを配信。

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この著者の最近の執筆記事; Mark Hutchinson（Mark Hutchinson）

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この著者の最近の執筆記事