パスワードを忘れた? アカウント作成
196574 story
数学

フリップフロップ回路を組み込んだ新たな乱数生成手法 37

ストーリー by hylom
その発想はなかった 部門より

あるAnonymous Coward 曰く、

独ハーゲン大学らの開発チームらが、乱数生成の新しい手法を開発したそうだ(Science Daily本家記事)。

このアルゴリズムでは、コンピュータメモリのフリップフロップ回路のランダムスイッチングを組み込んだとのこと。フリップフロップはスイッチングの直前は「準安定状態」にあり予測することができず、準安定状態の後メモリに保持されている内容は完全にランダムである。フリップフロップが組み込まれている場合、小さな配列では20倍「ランダム」な数を生成できることが実験で証明されているという。また、配列を故意に曲げようとする試みは、配列全体もしくは単体の要素が乱されるため容易に見分けられるという利点もあるとのこと。

乱数はセキュリティ分野だけでなく天気予報などの気象シミュレーションなどにも使われており、「ランダム」であればあるほどその精度が高まるとされている。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • Meta-stableは確かに「準安定状態」と訳して間違いないんだけど
    ここはメタステーブルとカタカナにしておくのが妥当な訳だと思う。

    熱雑音が乱数性の担保になるのかな?
    • by Anonymous Coward

      ぱっと見てメタスなテーブルに読めるので、メタ・ステーブルとでも書いた方がいいんじゃないですかね。
      まあ、準安定で全然構わないとおもいますが、カタカナでそのまま書けというなら判りやすく分けてほしいです。

      #個人的にはなるべく日本語にしてもらいたいものだけど。

    • by Anonymous Coward
      熱雑音というよりショット雑音だと予想。

      Meta-stableにいれるタイミング関係が、結果の分布に影響を与えそうですけど、
      "完全にランダム"っていっていいんだろうか。
      試作レベルでは確率50%に調整できても量産したら偏りそうです。
      ショットキーダイオードの雑音から乱数生成っていうのもあったような。
      • 十分実績のある熱雑音をサンプリングするタイプの乱数発生器と比べて同等の品質で実装が容易とかのメリットはあるのかな?
        親コメント
      • Re:メタステーブル (スコア:1, すばらしい洞察)

        by Anonymous Coward on 2010年02月27日 1時54分 (#1724593)
        フリップフロップの不定値ってことはRS-FFとかに11を放り込んだんだろうけど…
        それって単なるデジタルな発振回路を適当にサンプリングして乱数にしてるだけとしか読めない。
        発振回路の時間的なゆらぎってショット雑音とかとはまた違う気がするな。

        回路の製造が安定していればしているほど周期的なデータが出てきそうですごく嫌。
        コレ単品では使い物にならないだろうし、擬似乱数列のシードにしたり擬似乱数列をさらに乱すとかの用途ならぎりぎり使い物になるけれど、厳密な用途には使えないと思うなぁ…

        ツェナーダイオード使ったものはアナログ回路になるとはいえきっちりホワイトノイズになるから適当に作った単体でもそこそこ、組み合わせならかなりの品質が得られるってのが判るんだけど。
        親コメント
        • by Anonymous Coward
          発振回路を適当にサンプリングして乱数にする回路はまた別に提案されている。
          今回のものはFFを不安定な安定状態(メタステーブル状態)にしてノイズサンプリングしている。
          イメージとしては鉛筆を立ててどちらに転ぶかを観測するイメージ。鉛筆が立つという状態は安定状態ではあるが不安定なので最終的にはどちらかに転ぶ。
          鉛筆がどちらに転ぶかは外乱によってきまる。
          FFの場合はサーマルノイズやクロストークの影響によって決まると考えられるが実際のところはよくわからない。

          メタステーブルは回路のバランスが取れていれば取れているほど外乱によって決まる割合が高まるので製造が安定することは乱数品質的に優位になる。
          また、ADコンバータを利用する既存の乱数生成回路に対しデジタル回路のみで実装されるので実装が容易になる。
      • by Anonymous Coward
        s/ショットキーダイオード/チェナーダイオード/
        「乱数も作れるほど大きいノイズを出すから、コンデンサを付けるのを忘れるな」ってことだったかも。
  • Spin dice (スコア:1, 参考になる)

    by Anonymous Coward on 2010年02月25日 23時15分 (#1723958)

    MRAMで乱数を発生させる装置もあるのですが、どちらが良いのでしょか。
    http://venturewatch.jp/aist/20091130.html [venturewatch.jp]

  • by Anonymous Coward on 2010年02月26日 0時13分 (#1723989)

    産総研のスピンダイス [semiconjapan.jp]のことも思い出して下さい。

  • by Anonymous Coward on 2010年02月25日 23時39分 (#1723972)
    手作りマイコンにCRTディスプレイインターフェースを
    手作りしたような人は電源オンのたんびにほぼ似たような
    ランダムバターンが画面に出るのを見て
    回路にも癖があるんだぁー、と思ったもんです。

    D-RAMの場合は0xffのブロックと0x00のブロックが
    交互に現れるのはなにか理由があるんでしたっけ?
  • 発表はしてなかったのかなぁ。
  • by Anonymous Coward on 2010年02月25日 23時48分 (#1723979)
    電源投入直後で初期化前のSRAM(=フリップフロップを使った記憶素子)の
    内容を読み出して乱数に使ったってことなのかな?
  • by Anonymous Coward on 2010年02月26日 0時22分 (#1723994)
    ランダムはランダムじゃないの?
    何倍とかあるの?
    • by guicho2.71828 (38877) on 2010年02月26日 0時29分 (#1723997)

      分布密度とか、「mの次にnのでる確立」がm,nによらず変わらないとか、あるいはよく知らないもっと洗練された方法で定量化できるんじゃないでしょうか?

      何らかの方法で。

      #たよりなさすぎる

      --
      新人。プログラマレベルをポケモンで言うと、コラッタぐらい
      親コメント
    • Re:20倍って? (スコア:1, 参考になる)

      by Anonymous Coward on 2010年02月26日 1時02分 (#1724007)
      以下はアルゴリズム的に発生させた疑似乱数での話で、この手の物理的な要素の絡むものとは話が違うのですが参考までに。

      乱数ネタだけで教科書が1冊書けるぐらいいろんな評価尺度があります。例えば周期。疑似乱数は発生させ続けるとぐるっと回って同じ系列に戻っちゃうのですが、そこまでの長さが長いほど良い乱数です。

      他には、連続した乱数の間の相関関係。単純なアルゴリズムだと、偶数→奇数→偶数→奇数→偶数→奇数・・・と規則的にしか出てこないとか、それをそのまま使っちゃってCPUの手が全部読めちゃうカードゲームとかもありましたね。

      その親戚で、3次元空間のランダムな座標を「3つ連続で乱数を発生させてx,y,zとする」でやっちゃうと、全ての(x,y,z)がいくつかの平面上に集まっちゃうという残念さの評価尺度もあるらしいです。空間全体をランダムに飛び回って何かを調べているつもりが、そのいくつかの平面上しか調べられていない、などという残念な結果に陥るとか。これがn次元の場合でも十分にばらけるよ、みたいな評価をするとか書いてありました。
      親コメント
      • by Anonymous Coward
        こういうのを考えると決まって

         完全な乱数って一体なんなんだろう・・・

        と考えてはまってしまう
    • by flutist (16098) on 2010年02月26日 1時35分 (#1724022)

      調べもしないで書くけど、乱数列が与えられた時に、それが

       ・乱数でない確率

      を計算することでランダム性を検定したとして、たとえば比較対象(ショボい方)の乱数列がその確率が5%、もう一方(優れてる方)は0.025%だから20倍優れてるっていうような感じのことかも知れません。

      親コメント
      • by Anonymous Coward

        わかってないなら黙っていればいいのに。

        • by Anonymous Coward

          お前も分かってないなら黙ってろよ。
          分かってるなら、それを書けよ。

          あ、俺もか。

  • by Anonymous Coward on 2010年02月26日 9時22分 (#1724106)
    オレの脳チップに移植すれば・・・!!
  • by Anonymous Coward on 2010年02月26日 9時31分 (#1724111)

    まず読め。議論はそれからだ。

    "A meta-level true random number generator"
    Bernhard Fechner and Andre Osterloh,
    Int. J. Critical Computer-Based Systems, 1 (2010) 267-279
    http://dx.doi.org/10.1504/IJCCBS.2010.031719 [doi.org]

  • by Anonymous Coward on 2010年02月26日 10時19分 (#1724138)

    ロボットアームがさいころを掴む

    適当な擬似乱数を生成

    擬似乱数に応じた高さにロボットアームがさいころを持ち上げる

    さいころを転がす

    OCRでさいころの目を読む

    • by Anonymous Coward

      さいころの品質以上の乱数が得られません

    • by Anonymous Coward
      難点:6までしか乱数を生み出せない
      • by Anonymous Coward

        そのサイコロが六面ダイスだと誰が言った!

      • by Anonymous Coward

        五進数にするだろこの場合は……

      • by Anonymous Coward
        乱数用のサイコロは正二十面体でしょう。
    • by Anonymous Coward
      マジレスするとサイコロのランダム性が問題になる。変に偏ってたりしたら元の擬似乱数の方がマシという可能性も。
  • by Anonymous Coward on 2010年02月27日 7時54分 (#1724622)
    規則では規則に則っていることにならんの?

    (1-n)
  • by Anonymous Coward on 2010年02月28日 16時06分 (#1725061)
    メタスタビリティを利用したTrue Random Number Generator(TRNG)はすでに提案されている。 今回の回路はFFのsetup/hold time違反を利用しているようだが、これを利用したTRNGはDangerがFPGAで実装評価してる

    http://www.tsi.enst.fr/publications/enst/inproceedings-2007-7431.pdf [tsi.enst.fr]

    DangerらはFPGAで実装し、NISTテストまで通しているが今回のものはまともに評価できてないので、これで有用性を主張されてもという感じ。
    RSラッチのメタスタビリティを利用した物を提案されているが、これは92年ごろから提案されており最近ではFPGAでポストプロセッシングなしで NISTテストを通すものも報告されている。

    http://ci.nii.ac.jp/naid/110007131424 [nii.ac.jp]

    メタスタビリティベースのTRNGはすでに安定性の改善に焦点が移っており基本原理の確認レベルのこの研究に進歩性があるとは思えない。というかサーベイをろくにやってないのはどうよ。
typodupeerror

目玉の数さえ十分あれば、どんなバグも深刻ではない -- Eric Raymond

読み込み中...