(57)【要約】【課題】簡単な装置構成で、少ないビット数の初期値を用い、多ビット数の安全な乱数を高速度に生成する方法及び乱数生成装置を提供する。【解決手段】ＲＡＭの非初期化領域、例えば、スタック・エリア１１に、ハッシュ演算の入力バッファ８として確保し、スタック・エリア１１の領域１１ｂに、プログラムが実行する際に発生したデータを一時的に保存する。これによって、入力バッファ８となるメモリ領域の値は随時書き換えられ、ハッシュ演算の入力データは毎回異なっている。こうすることによって、初期値から推測できず、安全な乱数を生成でき、得られる擬似乱数の周期も大きくなる。【選択図】図４
2004109420.tif 000002
【特許請求の範囲】
【請求項１】
第１の乱数を入力し、第２の乱数を生成する乱数生成手段と、
記憶部と
を有し、
前記乱数生成手段は、前記第１の乱数の少なくとも一部として、前記記憶部における初期化されない領域である非初期化領域の一部のデータを入力する
乱数生成装置。
【請求項２】
前記記憶部に、実行可能な処理プログラムが格納されており、
実行中の前記処理プログラムから出力された一時データが、前記記憶部の非初期化領域に保存された時に、前記第１の乱数の値は変更される
請求項１に記載の乱数生成装置。
【請求項３】
外部装置と通信するインタフェースを有し、
前記インタフェースを介して、前記外部装置からのデータが前記記憶部に格納され、
前記記憶部の非初期化領域に保存される一時データは、前記外部装置からのデータを含む
請求項２に記載の乱数生成装置。
【請求項４】
前記乱数生成手段は、前記第１の乱数を入力し、乱数関数の演算を行ない、第２の乱数を生成する乱数演算部を有する
請求項１に記載の乱数生成装置。
【請求項５】
前記乱数関数は、少なくともＳＨＡ−１からなるハッシュ関数、または、ＭＤ５からなるハッシュ関数のいずれかを含む
請求項４に記載の乱数生成装置。
【請求項６】
前記乱数関数は、少なくとも、ＤＥＳ共通鍵暗号関数を含む
請求項４に記載の乱数生成装置。
【請求項７】
前記第１の乱数は、前記乱数演算部が出力した乱数を含む
請求項４に記載の乱数生成装置。
【請求項８】
前記乱数生成手段は、初期値を生成する乱数発生器を有し、
前記第１の乱数は、前記乱数発生器が生成した初期値を含む
請求項１に記載の乱数生成装置。
【請求項９】
前記乱数発生器は、真性乱数発生回路を含む
請求項８に記載の乱数生成装置。
【請求項１０】
乱数関数の演算を行なう乱数演算部と、記憶部とを有する乱数生成装置により乱数を生成する方法であって、
前記記憶部の非初期化領域の一部のデータを、第１の乱数の少なくとも一部として前記乱数演算部に入力する工程と、
前記入力された第１の乱数を用い、第２の乱数を生成する工程と
を有する
乱数生成方法。
【請求項１１】
前記記憶部に実行可能な処理プログラムが格納されており、
前記記憶部の非初期化領域には、実行中の前記処理プログラムの一時データを保存した時に、前記第１の乱数の値は変更される
請求項１０に記載の乱数生成方法。
【請求項１２】
前記記憶部の非初期化領域に保存される一時データは、外部から入力されたデータを含む
請求項１０に記載の乱数生成方法。
【請求項１３】
前記第１の乱数は、前記乱数演算部が出力した乱数を含む
請求項１０に記載の乱数生成方法。
【請求項１４】
前記乱数生成装置は、初期値を生成する乱数発生器を含み、
前記第１の乱数は、前記乱数発生器が生成した初期値を含む
請求項１０に記載の乱数生成方法。
【請求項１５】
前記乱数関数は、少なくともＳＨＡ−１からなるハッシュ関数、または、ＭＤ５からなるハッシュ関数のいずれかを含む
請求項１０に記載の乱数生成方法。
【請求項１６】
前記乱数関数は、少なくとも、ＤＥＳ共通鍵暗号関数を含む
請求項１０に記載の乱数生成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、乱数を生成する乱数生成装置、及び乱数生成方法に関する。
【０００２】
【従来の技術】
近年、デジタル通信技術の発展につれて、データ通信の安全性を高めるセキュリティ技術が注目され、そのため、暗号化技術が一般的に知られるようになってきた。
コンピュータネットワークを利用したデータ通信における代表的な暗号化方式として、共通鍵暗号方式と公開鍵暗号方式とがある。共通鍵暗号方式は、暗号化と復号化とで同じ暗号鍵を使う方法である。これは、「秘密鍵暗号」、「対称鍵暗号」、「慣用暗号」とも呼ばれる。一方、公開鍵暗号方式は、暗号化と復号化とで違う暗号鍵を使う方法である。公開鍵暗号方式では、一方の暗号鍵で暗号化したデータは、もう一方の鍵を使わないと復号できない。このため一方の鍵を公開し、他方の鍵を秘密にしておく。
【０００３】
共通鍵暗号方式は、暗号化、復号化の処理速度が速いが、暗号化と復号の鍵が同一であるので、通信相手に安全な方法で暗号鍵を渡すことが難しく、鍵を共有するための手段が必要になる。
一方、公開鍵暗号方式は、暗号化および復号化の処理速度が低いが、暗号化の鍵と復号のための鍵が異なるので、暗号化の鍵を片方の鍵は公開する、例えば、安全性が保証されない通信網で配送することが可能であり、相手に暗号鍵を渡すことは非常に楽である。公開鍵暗号方式として、ＲＳＡ方式が代表的であり、よく知られている。しかし、ＲＳＡ方式は、暗号化、復号化とも共通鍵方式に比べ、１０００倍程度処理速度が遅い。
【０００４】
このため、コンピュータネットワークを利用したデータ通信において、高速な暗号システムを構成する場合、一般に、暗号化および復号は共通鍵暗号を用い、その鍵を公開鍵暗号によって暗号化し、配送するという方法を用いている。この方式を採用しているものには、ＰＧＰ、ＰＥＭ等がある。
ＲＳＡ方式は、このような共通鍵の受け渡し、あるいは、比較的少量のデータ伝送等に使われている。
【０００５】
以上の暗号化技術を利用すれば、電子マネーや、ネット上の音楽配信や、携帯電話とＩＤカードを用いた個人向けのサービス等において、データの暗号化、および、本人認証に必要なデジタル署名の生成を行なうことができる。
このような通信システムにおいて、安全なデータ通信を保証するために、乱数生成技術は不可欠なものである。乱数の主な用途として、パスワードの作成、暗号化に使用する鍵値の作成、暗号文の生成、電子署名情報の生成等がある。このような応用において、セキュリティを確保するために、乱数生成方式の実用性と生成した乱数の安全性が特に重要になってくる。即ち、外部から推測できない安全な乱数が必要である。
【０００６】
乱数の生成方法としては、物理手段を利用して乱数列を発生させる方式と、数学的な演算処理を行ない、長い周期の乱数列を生成する擬似乱数生成方式がある。
物理手段を利用して乱数列を発生させる方式が多数知られている。例えば、抵抗体の熱雑音により乱数を生成する方式があげられる。抵抗体の熱雑音は多数の電子により発生する微少電流を合成したものであり、それぞれの電子の衝突と散乱は無関係に発生するため、雑音は一様に発生する。高抵抗の両端に発生する微少な雑音電圧を、ハイインピーダンス、低雑音のアンプで増幅して雑音電圧を取得し、その電圧をＡ／Ｄコンバータでデジタルデータに変換してパーソナルコンピュータに入力し、棄却法や括り合せ法などの処理を行なうことによって、乱数の性質の改善を行なうことができ、適切な乱数が得られる。
【０００７】
この方式は、物理的な性質を利用するので、０と１の発生確率がおのおの約１／２になり、各ビットが他の部分と独立であるので、生成される乱数列の推測は困難であり、セキュリティの用途に適した乱数列が得られる。しかし、特別なハード・ウェアを必要とし、また、乱数を生成するのに時間がかかり、デジタル署名時のセッションキーなどを生成する際に、セキュリティ度を高めるためにデータ長を長くとった場合には、処理速度の低下等の不具合が懸念される。
【０００８】
擬似乱数生成方式も多数知られている。例えば、Ｍ系列等の線形回路を複数組み合わせて生成する擬似乱数生成方法や、ＤＥＳ（Ｄａｔａ　Ｅｎｃｒｙｐｔｉｏｎ　Ｓｔａｎｄａｒｄ）等の共通鍵暗号を用いて生成する方法などは知られている。特許文献１〜３は、擬似乱数の生成方法と生成装置、または、擬似乱数を用いた暗号認証システムに関する。
例えば、擬似乱数生成法では、乱数演算を行なう関数をＦとすれば、初期値Ｒ（０）より順番に乱数列Ｒ（１）、Ｒ（２）、Ｒ（３）、・・・を生成し、乱数Ｒ（１）、Ｒ（２）、Ｒ（３）、を結合して所望の乱数を生成する。ここでＲ（ｉ＋１）＝Ｆ（Ｒ（ｉ））。
擬似乱数生成法では、特別なハード・ウェアを必要とせず、ソフト・ウエアによる実現が可能であり、マイクロコンピュータ上で利用できるが、以上に示すように、初期値により乱数列が生成されるために、使った関数および初期値が決まると、全ての乱数列が決定され、そのため、関数および初期値を判明すれば、同様の乱数列を容易に生成し得ることが欠点である。
【０００９】
次に、１つの具体例を用いて述べる。ＤＥＳやトリプルＤＥＳのＣＢＣモードを利用して乱数を生成する場合、例えばある手段により得られた６４ビットの値をＤ、ＤＥＳに使われる鍵情報をＫｒ、乱数発生用のシードをＳとするとき、乱数Ｒは以下のように計算される。
【００１０】
Ｉ＝ＤＥＳ（Ｋｒ，Ｄ）　　　　　　　　　　　　　　　　　　　　　（１）
Ｒ＝ＤＥＳ（Ｋｒ、Ｓ　ｘｏｒ　Ｉ）　　　　　　　　　　　　　　　（２）
Ｓ＝ＤＥＳ（Ｋｒ、Ｒ　ｘｏｒ　Ｉ）　　　　　　　　　　　　　　　（３）
【００１１】
ここで、関数ＤＥＳ（Ｘ，Ｙ）において、第１引数Ｘを暗号鍵情報として、第２引数Ｙの値をＤＥＳで暗号化する関数とする。また、ここで、演算“ｘｏｒ”は６４ビット単位の排他的論理和演算である。最終的に出てきた値Ｓは新規のシードとして更新されていく。ビット数の多い乱数を生成する場合には、式２と式３を繰り返す。次に乱数を生成する時に備えて、シードＳは、例えば集積化回路化された乱数生成ＬＳＩの不揮発性メモリ内に格納されていることが多い。この場合、生成された擬似乱数列に関わる入力パラメータ変数は、ある手段（例えば時刻や日付などから生成）によって乱数生成時に生成するＤと、不揮発性メモリ等に保存させておいたシード、つまり前回の乱数値Ｓである。
【００１２】
このような乱数生成方法及び乱数生成回路において、生成された擬似乱数列は、基本的に入力Ｄ、Ｓに対して一定であり、不揮発性メモリ等の記録媒体を持たず、前回の乱数値Ｓは記憶されないシステムにおいては、生成された擬似乱数列はＤのみに依存してしまい、Ｄの選び方の論理によっては、容易に短周期性が生じてしまい、乱数の安全性（秘匿性）強度に不安がある。また得られる擬似乱数の周期性も２６４以下に固定されてしまう。
【００１３】
また、ＦＩＰＳ１８６におけるＳＨＡ−１（Ｓｅｃｕｒｅ　Ｈａｓｈ　Ａｌｇｏｒｉｔｈｍ）を用いた擬似乱数生成方法においては、長さが１６０ビットのビット列ｔと、長さがｂビット（１６０≦ｂ≦５１２）のビット列ｃをＳＨＡ−１演算器にかけて１６０ビットの乱数を生成する方法が知られているが、乱数生成に必要なシードの量が多く、かつ、５１２ビットの入力バッファにビット列ｃを格納した後に、入力バッファの残りのビットに（５１２−ｂ）個の０を埋めるので、ビット列ｃが決まると、ビット列ｃの入力に対し、ＳＨＡ−１演算器の出力は常に一定となってしまう。
【００１４】
【特許文献１】
特開２０００−２４２４７０号公報
【特許文献２】
特開２００１−７５４７６号公報
【特許文献３】
特開２０００−４２２３号公報
【００１５】
【発明が解決しようとする課題】
上記のように、従来の擬似乱数生成法は、初期値を用いて乱数列が生成されるために、使った関数および初期値が決まると、全ての乱数列が決定される。従って、関数および初期値を判明すれば、同様の乱数列を容易に生成し得ることが欠点であり、安全性上には問題がある。
【００１６】
本発明は、以上の実情に鑑みてなされ、その目的は、簡単な装置構成で、少ないビット数の初期値を用い、多ビット数の安全な乱数を高速度に生成する方法と、乱数生成装置を提供することにある。
【００１７】
【課題を解決するための手段】
本発明による乱数生成装置は、第１の乱数を入力し、第２の乱数を生成する乱数生成手段と、記憶部とを有し、前記乱数生成手段は、前記第１の乱数の少なくとも一部として、前記記憶部における初期化されない領域である非初期化領域の一部のデータを入力する。
好ましくは、前記記憶部に、実行可能な処理プログラムが格納されており、実行中の前記処理プログラムから出力された一時データが、前記記憶部の非初期化領域に保存された時に、前記第１の乱数の値は変更される。
【００１８】
また、好ましくは、外部装置と通信するインタフェースを有し、前記インタフェースを介して、前記外部装置からのデータが前記記憶部に格納され、前記記憶部の非初期化領域に保存される一時データは、前記外部装置からのデータを含む。
【００１９】
また、好ましくは、前記乱数生成手段は、前記第１の乱数を入力し、乱数関数の演算を行ない、第２の乱数を生成する乱数演算部を有し、前記乱数関数は、少なくともＳＨＡ−１からなるハッシュ関数、または、ＭＤ５からなるハッシュ関数のいずれかを含む。或は、前記乱数関数は、少なくとも、ＤＥＳ共通鍵暗号関数を含む。
好ましくは、前記第１の乱数は、前記乱数演算部が出力した乱数を含む。
【００２０】
好ましくは、前記乱数生成手段は、初期値を生成する乱数発生器を有し、前記第１の乱数は、前記乱数発生器が生成した初期値を含む。
前記乱数発生器は、真性乱数発生回路を含む。
【００２１】
本発明による乱数生成方法は、乱数関数の演算を行なう乱数演算部と、実行可能な処理プログラムを格納した記憶部とを有する乱数生成装置により乱数を生成する方法であって、前記記憶部の非初期化領域の一部のデータを、第１の乱数の少なくとも一部として前記乱数演算部に入力する工程と、前記入力された第１の乱数を用い、第２の乱数を生成する工程とを有する。
好ましくは、前記記憶部に実行可能な処理プログラムが格納されており、前記記憶部の非初期化領域には、実行中の前記処理プログラムの一時データを保存した時に、前記第１の乱数の値は変更される。
好ましくは、前記記憶部の非初期化領域に保存される一時データは、外部から入力されたデータを含む。
好ましくは、前記第１の乱数は、前記乱数演算部が出力した乱数を含む。
【００２２】
また、好ましくは、前記乱数生成装置は、初期値を生成する乱数発生器を含み、前記第１の乱数は、前記乱数発生器が生成した初期値を含む。
また、好ましくは、前記乱数関数は、少なくともＳＨＡ−１からなるハッシュ関数、または、ＭＤ５からなるハッシュ関数のいずれかを含む、或は、前記乱数関数は、少なくとも、ＤＥＳ共通鍵暗号関数を含む。
【００２３】
以上の本発明の乱数生成装置によれば、乱数生成手段は第１の乱数を入力して第２の乱数を生成する時に、第１の乱数の一部または全部として、記憶部における非初期化領域からデータを読み込む。記憶部の非初期化領域は、初期化（ゼロにリセットする）されず、かつ、その領域に随時上書きされるので、この非初期化領域のデータの値は常に変化している。この領域のデータを乱数生成手段に入力すると、入力データが毎回異なっているので、乱数生成手段から出力された乱数列は、外部から推測が困難な安全な乱数となる。
以上の本発明の乱数生成方法によれば、乱数演算部の入力データの一部または全部として、記憶部の非初期化領域からデータを読み込む。読み込んだデータが毎回の演算で異なっているので、出力された乱数列は、推測が困難な安全な乱数となる。
【００２４】
【発明の実施の形態】
次に、本発明にかかる乱数生成方法と乱数生成装置の実施形態について、添付の図面を参照して詳細に説明する。
第１の実施形態
図１は、本実施形態にかかる乱数演算装置の概略構成を示す図である。
図１において、乱数演算装置１０は、例えば、ＣＰＵ１、ランダム・アクセス・メモリ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ：　ＲＡＭ）２、書き換え可能な不揮発性メモリＥＥＰＲＯＭ３、ハッシュ演算器４を備えている。
【００２５】
ＣＰＵ１は、乱数生成装置１０が起動された時に、ＥＥＰＲＯＭ３に記憶されているオペレーティング・システム（ｏｐｅｒａｔｉｎｇ　ｓｙｓｔｅｍ：ＯＳ）、システム用アプリケーション・プログラムなど、または、実行しようとするユーザ用アプリケーション・プログラムをＲＡＭ２に読込む。また、乱数生成装置１０が通常に動作する時に、ＣＰＵ１において、実行しようとするアプリケーション・プログラムに記述された手続き、及び指示されたコマンドを逐次解釈し、実行させる。例えば、デジタル署名のルーチンにおいて、乱数生成のコマンドを実行させると、デジタル署名の時の乱数生成を行なう。
なお、ＣＰＵ１においてプログラムを実行させる際に一時的に発生するデータをＲＡＭ２の所定の領域に随時書き込む。
【００２６】
ＲＡＭ２、ＥＥＰＲＯＭ３、及び不図示の読み出し専用メモリ（ＲＯＭ）が乱数生成装置１０のメモリシステムを構成する。通常、ＲＯＭには、ＯＳまたはＯＳのカーネル部が記憶されており、ＯＳ上に動作するシステム用プログラムや、サービスを提供するアプリケーション・プログラムなどがＥＥＰＲＯＭ３に配置されている。
ＲＡＭ２はＣＰＵ１に直接にアクセスされる記憶装置である。乱数生成装置１０は起動された時に、ＥＥＰＲＯＭ３に記憶されているＯＳ、システム用アプリケーション・プログラムなどがＣＰＵ１によってＲＡＭ２の所定のアドレス領域に読み込まれ、また、乱数生成装置１０が通常に動作する時に、実行しようとするユーザ用アプリケーション・プログラムもＣＰＵ１によってＲＡＭ２の所定のアドレスに読込まれる。さらに、ＣＰＵ１において各種アプリケーション・プログラムを実行する際に一時的に発生するデータをＲＡＭ２の所定の領域に随時書き込む。
なお、パーソナルコンピュータのようにＣＰＵ１とＲＡＭ２が別々に実装されていても差し支えない。
以上の乱数生成装置１０のメモリシステムは、本発明の請求項においての「記憶部」に対応する。
【００２７】
ハッシュ演算器４は、入力されたデータに対してハッシュ演算を行ない、入力されたデータから推測することが困難であるデータを出力し、擬似乱数として使う。ハッシュ関数は一方向性があるので、入力されたデータから演算の結果を求める事は出来ず、無相関性の良い擬似乱数を生成できる。
図１において、ハッシュ演算を行なう手段は、ハード・ウェアで実装されて、ハッシュ演算器４となっているが、ハッシュ演算のソフト・ウエアを実装されても問題はない。
ハッシュ演算器４は、本発明の請求項での「乱数演算部」に対応する。
バスライン５は、乱数生成装置１０において、ＣＰＵ１，ＲＡＭ２、ＥＥＰＲＯＭ３、ハッシュ演算器４と接続し、これらの間にデータを伝送する。
【００２８】
図２は、乱数演算装置１０において、ハッシュ演算器４における処理の概略を示す図である。ハッシュ関数として、例えば、ＳＨＡ−１、ＭＤ５、或は、ＤＥＳ関数を用いることができるが、ここで、１具体例として、ＳＨＡ−１のハッシュ関数Ｈを用いた場合の演算処理を例として述べる。
ＳＨＡ−１のハッシュ関数Ｈを用いた場合は、ハッシュ演算器４に入力するデータＸは、２６４ビット未満の長さのビット列である。ここで、例えば、入力データのビット長を５１２ビットにする。図２に示すように、ハッシュ演算器４は、５１２ビットの入力バファ８を有する。
【００２９】
擬似乱数生成方式を利用して乱数を生成する時は、乱数を生成するごとに初期値を設定する必要がある。初期値を生成する方法が色々あるが、本実施形態では、システムが保有している現在時刻を用いて、乱数を生成するための３２ビットの初期値を生成し、図２のように、入力バッファ８に書き込む。入力バッファ８にシードエリアが書き込まれた領域をシードエリア７と呼ぶ。
本実施形態において、本発明の請求項における「乱数生成手段」は、ハッシュ演算器４及び初期値となる現在時刻を生成する部分に対応する。
入力バッファ８の残りの領域に所定のデータを埋め込んで、入力データとなる。例えば、従来は、ゼロを埋め込むようにしていた。本実施形態では、後述する方法で入力バッファ８の残りの領域を埋め込む。
【００３０】
ハッシュ演算器４が入力データに対してハッシュ演算を行なう。ハッシュ関数として、例えば、ＳＨＡ−１を用いる。ハッシュ演算が終了したら、例えばＳＨＡ−１の場合は、１６０ビット長の乱数（ビット列）Ｙを出力する。演算が行なっている間に、出力された１６０ビットの乱数は、例えば、ＲＡＭ２の出力データ領域９に記憶される。ビット長が長い乱数を生成する場合は、目標となる乱数のビット数で決められる回数ｎでハッシュ関数の演算を行なう。得られた１６０ビットの乱数（ビット列）Ｙ１、Ｙ２…Ｙｎをビット結合し、即ち、Ｙ１‖Ｙ２‖…‖Ｙｎ、ｎ×１６０ビットのビット列に変換する。このｎ×１６０ビット列から目標の乱数を抽出する。
ここで、演算子“ｘ‖ｙ”は、ビット列ｘとビット列ｙの結合を表わし、例えば、（０１１０）‖（１０１）＝０１１０１０１。
例えば、ＲＳＡ方式の公開鍵暗号方式において２０４８ビット長の公開鍵を作る場合は、１０２４ビット長の乱数を２つ生成する。そのため、ハッシュ演算器４が７回演算をし、１１２０ビット長のビット列を生成し、そのビット列から１０２４ビットを抽出し、１つ目の乱数が生成される。同じように、２つ目の１０２４ビットの乱数を生成する。
【００３１】
既に述べたように、ハッシュ演算のパターンが決まると、同じ入力データに対して、ハッシュ演算器４の出力は一定になってしまう。乱数Ｙ１、Ｙ２…Ｙｎが同じにならないように、毎回のハッシュ演算において、異なる入力データをハッシュ演算器に入力する必要がある。
従来は、演算で得られた１６０ビットの乱数（例えば、Ｙ１）を入力バッファ８へ入力し、次のハッシュ値を演算し、次の１６０ビットの乱数（例えば、Ｙ２）を得る。このように必要な回数で繰り返し、目標の乱数を生成する。
しかし、前述のように、こうして生成した乱数列は、演算パターンと初期値に依存し、使った関数および初期値が決まると、乱数列の全体が決定されてしまい、同様の乱数列を容易に生成し得る。また、初期値は３２ビットの場合は、擬似乱数の周期は最大でも２３２であり、周期は小さく、安全性上に問題がある。
本実施形態では、後述する方法で毎回のハッシュ演算において、ハッシュ演算器４に推測の困難なデータを入力し、乱数の安全性を高める。
【００３２】
図３は、乱数演算装置１０において、ＲＡＭ２の記憶領域の配置を示す図である。
図３に示すように、例えば、ＲＡＭ２の記憶領域には、スタック・エリア１１、ヒープ・エリア１３、スタティック・データ・エリア１４、コード・エリア１５が少なくとも割り当てられており、また、例えば、スタック・エリア１１とヒープ・エリア１３の間に未使用領域１２が存在する。
【００３３】
スタック・エリア１１は、ＣＰＵ１がプログラムの実行を行なう際に、一時的なデータを格納する領域として使われているデータ構造、いわゆるスタック・データ構造は、使用しているメモリ領域である。例えば、プログラムで関数や、サブルーチンを呼び出した場合は、引数やリターンアドレスなどがスタック・エリア１１に一時的に保存される。
スタック・データ構造は、Ｆｉｒｓｔ　Ｉｎ　Ｌａｓｔ　Ｏｕｔ（ＦＩＬＯ）のデータ構造であり、一番最後に入れたデータを、一番最初に取り出す。
【００３４】
ヒープ・エリア１３は、ＯＳが管理、利用するメモリ領域であり、ＯＳはプログラムを実行する際に利用する。ＯＳは、ヒープ・エリア１３からメモリを取得してアプリケーションに提供したり、この領域に新しいプログラム、または、システム・プログラムをロードし、アロケーションしたりする。ＯＳはメモリを管理する時、アプリケーション用とシステム用のヒープ領域に区別し、システム用はシステムヒープと呼ばれ、機能拡張ファイルなどをこちらに読込み、アプリケーション用ヒープ領域に一時的なデータを格納する。
【００３５】
スタティック・データ・エリア１４は、プログラムが実行する際に発生するスタティック・データを保存するメモリ領域である。スタティック・データは、プログラムが実行する際に、実行開始から終了まで値は変化しないと宣言された変数である。例えば、実行中のプログラムは関数やサブルーチンを呼び出した場合に、これらの変数を変化させないために、スタティック・データ・エリア１４に一時保存する。
コード・エリア１５は、ＲＡＭ２に読み込まれ、実行するプログラムのコード本体を保存するメモリ領域である。
【００３６】
スタック・エリア１１とヒープ・エリア１３は、通常ＣＰＵ１のワークＲＡＭ領域であり、様々なアプリケーションがこれらの領域を一時的に使用している。
使用プロセスが終了すると開放をするが、ゼロ初期化はされず、随時上書きされている領域であるので、この領域のデータの値は随時変化している。以降、これらの領域をＲＡＭ２の「非初期化領域」と呼ぶ。
本実施形態では、図２に示された入力バッファ８をＲＡＭ２の上記の非初期化領域に指定する。
【００３７】
図４は、本実施形態にかかる乱数演算装置１０において、ハッシュ演算器４の入力バッファをＲＡＭ２の非初期化領域に設ける例を示す図である。
図４に示すように、例えば、スタック・エリア１１において、点線で示された５１２ビットの領域をハッシュ演算器４の入力バッファ８として確保する。符号１１ｂで示された領域は、実行中のプログラムが出力した一時データを保存した領域であり、これによって、入力バッファ８となる５１２ビットのメモリ領域の値は書き換えられる。
図２と同じように、最初のハッシュ演算の際に、別途で生成された例えば３２ビットの初期値を入力バッファ８におけるシードエリア７に書き込む。
【００３８】
前述のように、非初期化領域に確保された入力バッファ８は、様々なアプリケーションに一時的に使用され、随時上書きされており、しかもゼロ初期化されないので、一定の初期値でハッシュ演算を開始しても、ハッシュ演算器４に入力される値は、初回を含めて、毎回全く異なっている。このようにして、３２ビットの初期値を用いても、入力バッファ８に予測できないデータが埋め込まれているため、入力データの変化範囲は実質上に５１２ビットに拡大され、初期値のビット長（３２ビット）をはるか越えている。これによって、得られる擬似乱数の周期は２３２より大きくなり、外部からの推測が困難な安全な乱数となる。
また、ハッシュ演算器４以外に専用の回路を必要とせず、容易に実現することが可能となる。
【００３９】
図５は、本実施形態の乱数演算装置１０において、乱数を生成する処理を示すフローチャートである。
ステップＳ１：
ＲＡＭ２上の非初期化領域、即ち、図４に示すように、スタック・エリア１１、或は、ヒープ領域１３に、ハッシュ演算器４への入力用の５１２ビットの入力バッファ８を確保する。即ち、この領域からデータを読込むことを宣言する。
ステップＳ２：
乱数を生成するための３２ビットの初期値を生成する。本実施形態において、例えば、システムが保有している現在時刻を用いて初期値を生成し、入力バッファ８におけるシードエリア７にこの３２ビットの初期値を書き込む。
【００４０】
ステップＳ３：
続いて、ハッシュ演算器４は、５１２ビットの入力バッファ８から入力データを読み込んで、ハッシュ演算を実行する。
乱数生成装置１０の電源がリセットされた時のみに、スタック・エリア１１や、ヒープ領域１３などの非初期化領域に、ゼロ初期化されるので、初期値を入力しなければ、入力バッファ８の全領域はゼロとなり、第１回目のハッシュ演算結果は初期値に依存する。このようなことを避けるために、最初は、別途に生成された初期値を用いてハッシュ演算を行なうこととする。
ハッシュ演算の詳細は、後程詳細に説明する。
【００４１】
ステップＳ４：
ハッシュ演算を行なった結果、例えば、ＳＨＡ−１の場合に、ハッシュ値から１６０ビットのビット列を乱数として取り出す。
ステップＳ５：
これまで生成された複数の乱数を結合し、目標の乱数のビット長になっているか否かを判断する。
結合されたビット列のビット長は、目標の乱数のビット長以上である場合は、ステップＳ７に進む。
結合されたビット列のビット長は、目標の乱数のビット長以下である場合は、ステップＳ６に進む。
【００４２】
ステップＳ６：
ステップＳ３で説明した理由で、ここで、従来と同じように、得られた１６０ビットの乱数値を入力バッファ８へ入力し、ステップＳ３に戻り、ステップＳ３〜６を経て、ハッシュ演算と、次の１６０ビットの乱数値の抽出と、今まで得られた全部の１６０ビット乱数の結合と、結合された乱数は必要なビット長に達したかどうかの判断を繰り返す。
ステップＳ３に戻った時に、乱数生成装置１０で実行しているプログラムが発生したデータを一時にＲＡＭ２の非初期化領域に記憶しているので、入力バッファ８は既に書き換えられた。即ち、ステップＳ３に戻って、次のハッシュ演算を行なう時には、入力バッファ８の値は、前回の入力バッファ８の値と全く異なり、前回の１６０ビットの乱数から予測できない次の１６０ビットの乱数を生成できる。
ステップＳ７：
結合されたビット列のビット長は、目標の乱数のビット長以上になった場合は、結合されたビット列のビット長から目標の乱数を抽出し、これで目標となる乱数が取得され、乱数生成処理を終了する。
【００４３】
次に、図６〜図１１を用い、ハッシュ演算回路４において、ハッシュ演算の詳細を説明する。なお、次の説明には、ＳＨＡ−１ハッシュ関数を一例として述べる。
図６（ａ）は、ハッシュ演算回路４の入力バッファ８のデータ構造を示している。図６（ｂ）は、ハッシュ演算回路４において、ハッシュ演算を実行する各バッファを示している。
図６（ａ）に示す入力バッファ８は、１６個のロングワード（３２ビット）Ｗ０、Ｗ１、…Ｗ１５から構成され、即ち、入力バッファ８のバッファサイズは、５１２ビットとなる。この入力バッファ８は、ＲＡＭ２上の非初期化領域、即ち、図４に示されたように、スタック・エリア１１、或は、ヒープ領域１３に設けられている。別途に生成された３２ビットの初期値は、例えば、入力バッファ８のロングワードＷ１０に入力されている。
【００４４】
ハッシュ演算回路４には、演算を実行する５ワードのバッファが２つある。図６（ｂ）に示すように、１番目のバッファが、５個の３２ビットのレジスタＡ、Ｂ、Ｃ、Ｄ、Ｅからなり、２番目のバッファが、５個の３２ビットのレジスタＨ０、Ｈ１、Ｈ２、Ｈ３、Ｈ４からなる。また、レジスタＴＥＭＰからなる１ワードのバッファには、演算を実行する際に、データを一時的に保存する。
演算をスタートする前に、図６（ｂ）に示すように、レジスタＨ０、Ｈ１、Ｈ２、Ｈ３、Ｈ４は予め初期化する。初期化後に、レジスタＨ０、Ｈ１、Ｈ２、Ｈ３、Ｈ４の値は、１６進数で次のようになる。
Ｈ０＝６７４５２３０１ｈ、
Ｈ１＝ＥＦＣＤＡＢ８９ｈ、
Ｈ２＝９８ＢＡＤＣＦＥｈ、
Ｈ３＝１０３２５４７６ｈ、
Ｈ４＝Ｃ３Ｄ２Ｅ１Ｆ０ｈ。
【００４５】
図６（ａ）に示すように、初期値を入力バッファ８のＷ１０に入力して、ハッシュ演算をスタートする。入力バッファ８から一回で読込んだ入力データに対して、一回のハッシュ演算を実行する。この一回のハッシュ演算は８０ステップに分けて行なう。
図７（ａ）と（ｂ）は、ハッシュ演算におけるステップ１の演算の内容を示す。
図７（ａ）に示すように、ハッシュ演算のステップ１において、まずは、予め与えられたレジスタＨ０、Ｈ１、Ｈ２、Ｈ３、Ｈ４での各初期値を、レジスタＡ、Ｂ、Ｃ、Ｄ、Ｅに転送する（ＳＴＥＰ１−１と記す）。
図７（ｂ）に示すように、各演算ステップにおいての値が定められている変数Ｗと、レジスタＡの値を５ビット左向きにローテーションさせた値Ａ≪５と、レジスタＥの値、加算定数Ｋ値、関数ｆの値とをビット単位で加算し、２３２で剰余をとった値を、レジスタＴＥＭＰに転送し、ＴＥＭＰの値とする（ＳＴＥＰ１−２と記す）。
変数Ｓに対して、ビット・ローテーション演算「Ｓ≪ｎ」は、変数Ｓを左側にｎビットをシフトして、あふれた上位のｎビットを最下位ビットからの下位ｎビットに割り当てる演算を表す。８ｂｉｔの数値を例にとると、Ｓ＝１００１　１０１１ｂとして、Ｓ≪２を求めると、Ｓ≪２＝０１１０　１１１０ｂのようになる。
従って、Ａ≪５は、Ａを左側に５ビットをシフトして、あふれた上位５ビットが下位５ビットに割り当てられた値となる。
【００４６】
図８（ａ）〜（ｃ）は、ＳＴＥＰ１−２における変数Ｗ、加算定数Ｋ、関数ｆの定義を示す図である。
図８（ａ）に示すように、ハッシュ演算の各ステップにおいて、変数Ｗの値が入力バッファ８の入力データＷ０〜Ｗ１５を用いて定められている。
具体的に、ハッシュ演算のステップ１からステップ１５までは、Ｗの値はそれぞれ入力バッファ８の入力データＷ０〜Ｗ１５そのままである。
ステップ１６から、Ｗの値は、図８（ａ）に示された定義のように、Ｗ０〜Ｗ１５を用いて演算で定められている。
即ち、ステップ１６では、Ｗの値は、Ｗ０、Ｗ２、Ｗ８、Ｗ１３のビット単位の排他的論理和演算（ｘｏｒ）の後に、左側に１ビットローテーションしてなる。
ステップ１７では、Ｗ１、Ｗ３、Ｗ９、Ｗ１４について同様な演算を行なってＷの値を決める。
ステップ１８では、Ｗ２、Ｗ４、Ｗ１０、Ｗ１５について同様な演算を行なってＷの値を決める。
このように類似した方法でステップ１９からステップ８０においてのＷを定義する。例えば、ステップ８０では、Ｗの値は、Ｗ６３、Ｗ６５、Ｗ７１、Ｗ７６のビット単位の排他的論理和演算（ｘｏｒ）の後に、左側に１ビットローテーションしてなる。
【００４７】
図８（ｂ）に示すように、加算定数Ｋの各ステップにおいての値が予め定められている。具体的に、Ｋの値は１６進数で次のようになる。
ステップ１　〜ステップ２０に、Ｋ＝５Ａ８２７９９９ｈ、
ステップ２１〜ステップ４０に、Ｋ＝６ＥＤ９ＥＢＡ１ｈ、
ステップ４１〜ステップ６０に、Ｋ＝８Ｆ１ＢＢＣＤＣｈ、
ステップ６１〜ステップ８０に、Ｋ＝ＣＡ６２Ｃ１Ｄ６ｈ。
【００４８】
図８（ｃ）に示すように、ハッシュ演算の各ステップにおいて、関数ｆの値がレジスタＢ、Ｃ、Ｄの値を用いて定められている。
ステップ１　〜ステップ２０に、
ｆ＝（Ｂ　ａｎｄ　Ｃ）　ｏｒ　（（ｎｏｔ　Ｂ）　ａｎｄ　Ｄ）、
ステップ２１〜ステップ４０に、
ｆ＝Ｂ　ｘｏｒ　Ｃ　ｘｏｒ　Ｄ、
ステップ４１〜ステップ６０に、
ｆ＝（Ｂ　ａｎｄ　Ｃ）　ｏｒ　（Ｂ　ａｎｄ　Ｄ）　ｏｒ　（Ｃ　ａｎｄ　Ｄ）、
ステップ６１〜ステップ８０に、
ｆ＝Ｂ　ｘｏｒ　Ｃ　ｘｏｒ　Ｄ．
ここで、“ａｎｄ”、“ｏｒ”、“ｎｏｔ”は、それぞれビット単位の論理積、論理和、反転演算を表わす。
【００４９】
図９（ａ）と（ｂ）は、図７に続き、ハッシュ演算におけるステップ１の演算の内容を示す。
図９（ａ）に示すように、図７（ｂ）に続いて、レジスタＥにレジスタＤの値を転送し、レジスタＤにレジスタＣの値を転送し、レジスタＣにはレジスタＢの値を左方向へ３０ビットローテーションした値を転送し、レジスタＢにはレジスタＡの値を転送、レジスタＡにはＴＥＭＰ値を転送して、レジスタＡ〜Ｅの値を更新する（ＳＴＥＰ１−３と記す）。
【００５０】
続いて、図９（ｂ）に示すように、レジスタＨ０にレジスタＡの値を加算してＨ０とし、レジスタＨ１にレジスタＢの値を加算してＨ１とし、レジスタＨ２にレジスタＣの値を加算してＨ２とし、レジスタＨ３にレジスタＤの値を加算してＨ３とし、レジスタＨ４にレジスタＥの値を加算してＨ４とし、レジスタＨ１、Ｈ２、Ｈ３、Ｈ４、Ｈ５の値を更新する（ＳＴＥＰ１−４と記す）。
【００５１】
上記ＳＴＥＰ１−１〜ＳＴＥＰ１−４を１つのステップとして各レジスタを次々と更新し、これを８０ステップ繰り返す。
例として、図１０（ａ）と（ｂ）は、ステップ２の一部（ＳＴＥＰ２−１）とステップ８０の一部（ＳＴＥＰ８０−４）を示している。
図１０（ａ）に示すように、ステップ２−１において、ＳＴＥＰ１−１と同じように、ステップ１で更新されたレジスタＨ０、Ｈ１、Ｈ２、Ｈ３、Ｈ４の各値を初期値として、レジスタＡ、Ｂ、Ｃ、Ｄ、Ｅに転送する。
そして、ＳＴＥＰ１−２〜ＳＴＥＰ１−４と同じような演算内容を、ＳＴＥＰ２−２〜ＳＴＥＰ２−４として実行され、レジスタＨ１、Ｈ２、Ｈ３、Ｈ４、Ｈ５の値をさらに更新する。
このように、ステップ３〜ステップ８０まで、ＳＴＥＰ１−２〜ＳＴＥＰ１−４と同じような演算内容を繰り返し、各レジスタを次々と更新する。
最後に、図１０（ｂ）に示すように、ステップ８０−４において、ＳＴＥＰ１−４と同じように、ステップ７９で更新されたレジスタＨ０、Ｈ１、Ｈ２、Ｈ３、Ｈ４の各値にレジスタＡ、Ｂ、Ｃ、Ｄ、Ｅの値をそれぞれ加算して、レジスタＨ１、Ｈ２，Ｈ３、Ｈ４、Ｈ５の値を更新する。
【００５２】
図１１（ａ）と（ｂ）は、図１０に続いて、ハッシュ演算の内容を示す。
ステップ８０−４において、最終的に５つの３２ビット長のビット列Ｈ０〜Ｈ４が得られた。図１１（ａ）に示すように、ビット列Ｈ０〜Ｈ４を結合して、即ち、Ｈ０‖Ｈ１‖Ｈ２‖Ｈ３‖Ｈ４、得られた５×３２ビット＝１６０ビットのビット列をハッシュ演算の結果（ハッシュ値）として取り出す。
このように得られたハッシュ値は、入力バッファ８のワードＷ０〜Ｗ１５の値が１ビットでも変化すると、全く異なる結果が得られるアルゴリズムとなっており、乱数値となる。
【００５３】
以上のように得られた１６０ビットの乱数値を、図１１（ｂ）に示すように、例えば、入力バッファ８の例えばＷ０〜Ｗ４に入力し、再びハッシュ演算を行ない、次の１６０ビットの乱数値が得られる。これを、必要な桁数の乱数値が得られるまで繰り返して擬似乱数を生成する。
前述のように、入力バッファ８は、ＲＡＭ２上のスタック・エリア１１、或は、ヒープ領域１３などの非初期化領域に設けられているので、以上のハッシュ演算を行なっている間に、乱数生成装置１０に実行している全てのプログラムが入力バッファ８を含む非初期化領域に上書きをする。これによって、８０ステップの演算を終了した時点で、入力バッファ８の１６のワードＷ０〜Ｗ１５の値はすでに更新された可能性が高い。
前述したように、電源のリセットによってＷ０〜Ｗ１５は全部ゼロになる。また、入力バッファ８の１６ワードＷ０〜Ｗ１５の更新が少ないこともあり得る。
このようなことを避けるために、以上のように、毎回得られた１６０ビットの乱数値を再び入力バッファ８に入力し、ハッシュ演算を繰り返すようにしている。
【００５４】
以上の本実施の形態によれば、入力バッファのデータからハッシュ演算によって乱数を生成する時に、入力バッファをＲＡＭのスタック・エリアや、ヒープ・エリアなどの初期化されない、かつ、随時上書きされる非初期化領域に設置することによって、ハッシュ演算の入力データが毎回異なっているので、外部から初期値からハッシュ演算の結果を推測することが困難となる。
また、初期値はビット長が短くても、入力バッファ８には、ゼロではなく、全く予測できない値を埋めこむので、入力データの変化範囲は実質上に５１２ビットに拡大し、得られる擬似乱数の周期は２３２より大きくなり、外部からの推測が困難な安全な乱数となる。ＥＥＰＲＯＭ等の不揮発性メモリにシード値を保存しておく必要も不要となる。
また、専用の回路を必要とせず、容易に実現することが可能となる。
【００５５】
第２の実施形態
本実施形態において、本発明にかかる乱数生成装置の他の実施形態について述べる。
図１２は、本実施形態にかかる乱数演算装置の概略構成を示す図である。なお、図１２において、第１の実施形態と同じ構成に同じ符号を用い、重複する説明を適宜に省略する。
図１２において、乱数演算装置３０は、例えば、ＣＰＵ１、ランダム・アクセス・メモリ（ＲＡＭ）２、書き換え可能な不揮発性メモリＥＥＰＲＯＭ３、ハッシュ演算器４、真性乱数発生回路３１を備えている。
本実施形態において、第１の実施形態と同じように、ハッシュ演算器４の入力バッファ８をＲＡＭ２のスタック・エリア１１、または、ヒープ・エリア１３に指定する。これによって、ハッシュ演算器４の入力データが毎回異なっているようになり、外部からの推測が困難となる。
【００５６】
真性乱数とは、物理手段を利用して発生した乱数を言う。例えば、抵抗体の熱雑音により乱数を生成する方式を用いる。抵抗体の熱雑音は多数の電子により発生する微少電流を合成したものであり、それぞれの電子の衝突と散乱は無関係に発生するため、雑音は一様に発生する。高抵抗の両端に発生する微少な雑音電圧を、ハイインピーダンス、低雑音のアンプで増幅して雑音電圧を取得し、その電圧をＡ／Ｄコンバータでデジタルデータに変換してパーソナルコンピュータに入力し、棄却法や括り合せ法などの処理を行なうことによって、乱数の性質の改善を行なうことができ、適切な乱数が得られる。
この方式は、物理的な性質を利用するので、０と１の発生確率がおのおの約１／２になり、各ビットが他の部分と独立であるので、生成される乱数列の推測は困難であり、セキュリティの用途に適した乱数列が得られる。しかし、乱数を生成するのに時間が掛かるので、特に、セキュリティ度を高めるためにデータ長を長くとった場合には、処理速度が十分ではない。
【００５７】
第１の実施形態では、乱数を生成するための３２ビットの初期値として、システムが保有している現在時刻を用いていた。
本実施形態では、ハッシュ演算の入力バッファ８はＲＡＭ２の非初期化領域に設けたことによって、初期値は少ないビット数でよいので、例えば、３２ビットで十分である。従って、例えば、図１２に示された真性乱数発生回路３１を乱数生成装置３０に搭載した場合は、ハッシュ演算の初期値を真性乱数とする。
また、動作の遅い真性乱数発生回路３１を乱数生成装置３０に搭載し、真性乱数が生成されるたびにハッシュ値の演算入力として使用し、未生成時は、第１の実施形態のようにハッシュ値の演算結果を使用するようにすれば、周期性の長い擬似乱数が高速に得られることになる。
本実施形態において、請求項における「乱数生成手段」は、ハッシュ演算器４及び真性乱数発生回路３１に対応する。
【００５８】
図１３は、本実施形態の乱数演算装置３０において、乱数を生成する処理を示すフローチャートである。
ステップＳ１１：
ＲＡＭ２上の非初期化領域、即ち、図４に示すように、スタック・エリア１１、或は、ヒープ領域１３に、ハッシュ演算器４への入力用の５１２ビットの入力バッファ８を確保する。
ステップＳ１２：
乱数を生成するための３２ビットの初期値を生成する。本実施形態において、真性乱数発生回路３１によって、ハッシュ演算の初期値となる乱数を生成し、入力バッファ８におけるシードエリア７に書き込む。
例えば、一様に発生する抵抗体の熱雑音により乱数を生成する方式を用いる。
高抵抗の両端に発生する微少な雑音電圧を、ハイインピーダンス、低雑音のアンプで増幅して雑音電圧を取得し、その電圧をＡ／Ｄコンバータでデジタルデータに変換してパーソナルコンピュータに入力し、例えば、３２ビットの乱数を抽出する。
【００５９】
ステップＳ１３：
続いて、ハッシュ演算器４は、５１２ビットの入力バッファ８から入力データを読み込んで、図６〜図１１に示されたようにハッシュ演算を実行する。
乱数生成装置１０の電源がリセットされた時のみに、スタック・エリア１１や、ヒープ領域１３などの非初期化領域に、ゼロ初期化されるので、最初は、真性乱数発生回路３１で生成された初期値を用いてハッシュ演算を行なうこととする。
【００６０】
ステップＳ１４：
ハッシュ演算の結果、例えば、ＳＨＡ−１の場合に、ハッシュ値から１６０ビットのビット列を乱数として取り出す。
ステップＳ１５：
これまでのハッシュ演算で生成された複数の１６０ビットの乱数を結合し、目標の乱数のビット長になっているか否かを判断する。
結合されたビット列のビット長は、目標の乱数のビット長以上である場合は、ステップＳ１８に進む。
結合されたビット列のビット長は、目標の乱数のビット長以下である場合は、ステップＳ１６に進む。
【００６１】
ステップＳ１６：
真性乱数発生回路３１は真性乱数シードを生成したか否かを判断し、
真性乱数発生回路３１は真性乱数シードを生成済みであれば、例えば、その３２ビットの乱数値を入力バッファ８へ入力し、ステップＳ１３に戻り、ステップＳ１３〜１５を経て、ハッシュ演算と、次の１６０ビットの乱数値の抽出と、今まで得られた全部の１６０ビット乱数の結合と、結合された乱数は必要なビット長に達したかどうかの判断を繰り返す。
ステップＳ１３に戻った時に、乱数生成装置３０で実行しているプログラムが発生したデータを一時にＲＡＭ２の非初期化領域に記憶しているので、入力バッファ８は既に書き換えられた。即ち、ステップＳ１３に戻って、次のハッシュ演算を行なう時には、入力バッファ８の値は、前回の入力バッファ８の値と全く異なり、前回の１６０ビットの乱数から予測できない次の１６０ビットの乱数を生成できる。
真性乱数シードは生成されていない場合は、ステップＳ１７に進む。
【００６２】
ステップＳ１７：
真性乱数シードは生成されていない場合は、前回のハッシュ演算で得られた１６０ビットの乱数値を入力バッファ８へ入力する。そして、ステップＳ１３に戻り、ステップＳ１３〜１５を経て、ハッシュ演算と、次の１６０ビットの乱数値の抽出と、今まで得られた全部の１６０ビット乱数の結合と、結合された乱数は必要なビット長に達したかどうかの判断を繰り返す。
同じように、ステップＳ１３に戻った時に、入力バッファ８は書き換えられたので、次のハッシュ演算の時に、入力バッファ８の値は、前回の入力バッファ８の値と全く異なり、前回の１６０ビットの乱数から予測できない乱数を生成できる。
ステップＳ１８：
結合されたビット列のビット長は、目標の乱数のビット長以上になった場合は、結合されたビット列のビット長から目標の乱数を抽出し、これで目標となる乱数が取得され、乱数生成処理を終了する。
【００６３】
以上の本実施の形態によれば、入力バッファのデータからハッシュ演算によって乱数を生成する時に、入力バッファをＲＡＭのスタック・エリアや、ヒープ・エリアなどの非初期化領域に設置することによって、ハッシュ演算の入力データが毎回異なっているので、外部から初期値からハッシュ演算の結果を推測することが困難となる。
また、初期値はビット長が短くても、入力バッファ８には、ゼロではなく、全く予測できない値を埋めこむので、入力データの変化範囲は実質上に５１２ビットに拡大し、得られる擬似乱数の周期は２３２より大きくなり、外部からの推測が困難な安全な乱数となる。また、ＥＥＰＲＯＭ等の不揮発性メモリにシード値を保存しておく必要も不要となる。
また、動作の遅い真性乱数発生回路を乱数生成装置に搭載し、真性乱数が生成されるたびにハッシュ値の演算入力として使用し、未生成時は、ハッシュ値の演算結果を使用することによって、安全性がさらに高く、周期性の長い擬似乱数が高速に得られる。
【００６４】
第３の実施形態
本実施形態において、本発明にかかる乱数生成装置の他の実施形態について述べる。
図１４は、本実施形態にかかる乱数演算装置の概略構成を示す図である。なお、図１４において、第１の実施形態と同じ構成に同じ符号を用い、重複する説明を適宜に省略する。
図１４において、乱数演算装置４０は、例えば、ＣＰＵ１、ランダム・アクセス・メモリ（ＲＡＭ）２、書き換え可能な不揮発性メモリＥＥＰＲＯＭ３、ハッシュ演算器４、インタフェース（Ｉ／Ｆ）４１、外部コンピュータ４２とを備えている。
本実施形態において、第１の実施形態と同じように、ハッシュ演算器４の入力バッファ８をＲＡＭ２のスタック・エリア１１、または、ヒープ・エリア１３に指定する。これによって、ハッシュ演算器４の入力データが毎回異なっているようになり、生成された乱数列を初期値から推測することが困難となる。
本実施形態では、乱数を生成するための初期値として、システムが保有している現在時刻を用いる。
本実施形態において、請求項における「乱数生成手段」は、ハッシュ演算器４及び初期値となる現在時刻を生成する部分に対応する。
【００６５】
外部コンピュータ４２は、例えば、公開鍵暗号、共通鍵暗号を用いて、電子マネーや、ネット上の音楽配信や、携帯電話とＩＤカードを用いた個人向けのサービス等を行なう通信システムにおけるホストコンピュータである。外部コンピュータ４２は、乱数生成装置４０で生成した乱数を用いて、パスワードの作成、暗号化に使用する鍵値の作成、暗号文の生成、電子署名情報の生成等を行なう。
Ｉ／Ｆ４１は、乱数生成装置４０と外部コンピュータ４２との間に送受信し、外部コンピュータ４２から受信した指令をＣＰＵ１に出力し、また、ＣＰＵ１から入力された信号を外部コンピュータ４２に送信する。例えば、Ｉ／Ｆ４１は、外部コンピュータ４２からの指示やデータなどを乱数生成装置４０に送信し、または、乱数生成装置４０からの演算結果を外部コンピュータ４２に送信する。
ＣＰＵ１は、外部コンピュータ４２からのコマンド、あるいは、予め乱数生成装置４０に設定されたコマンドに基づいて、ＥＥＰＲＯＭ３に記憶されているプログラムをＲＡＭ２に読込み、逐次解読して実行し、乱数を生成する。
【００６６】
乱数生成装置４０が外部コンピュータ４２とデータの送受信を行ない、受信したデータを、ＥＥＰＲＯＭ３に記憶されているプログラムが実行する際に、そのプログラムにより、ＲＡＭ２の非初期化領域に配置する。これにより乱数生成装置４０において、ハッシュ演算器４の入力バッファ８に入力されるデータの範囲は広くなり、ハッシュ演算器４が生成した乱数の周期はさらに拡大され、３２ビットの初期値を用い、２１６０の周期に近づくことになる。
【００６７】
図１５は、本実施形態の乱数演算装置４０において、乱数を生成する処理を示すフローチャートである。
ステップＳ２１：
乱数生成装置４０は、外部コンピュータ４２と通信し、データを送受信し、乱数生成装置４０は、乱数の演算を開始する。特に、乱数生成装置４０は、外部コンピュータ４２から受信したデータは、実行しているプログラムによって、ＲＡＭ２の非初期化領域に書き込まれる。
【００６８】
ステップＳ２２：
ＲＡＭ２上の非初期化領域、即ち、図４に示すように、スタック・エリア１１、或は、ヒープ領域１３に、ハッシュ演算器４への入力用の５１２ビットの入力バッファ８を確保する。
ステップＳ２３：
乱数を生成するための３２ビットの初期値を生成する。本実施形態において、システムが保有している現在時刻を用いて初期値を生成し、入力バッファ８におけるシードエリア７にこの３２ビットの初期値を書き込む。
【００６９】
ステップＳ２４：
続いて、ハッシュ演算器４は、５１２ビットの入力バッファ８から入力データを読み込んで、図６〜図１１に示されたようにハッシュ演算を実行する。
ステップＳ２５：
ハッシュ演算の結果、例えば、ＳＨＡ−１の場合に、ハッシュ値から１６０ビットのビット列を乱数として取り出す。
ステップＳ２６：
これまでのハッシュ演算で生成された複数の１６０ビットの乱数を結合し、目標の乱数のビット長になっているか否かを判断する。
結合されたビット列のビット長は、目標の乱数のビット長以上である場合は、ステップＳ２８に進む。
結合されたビット列のビット長は、目標の乱数のビット長以下である場合は、ステップＳ２７に進む。
【００７０】
ステップＳ２７：
前回のハッシュ演算で得られた１６０ビットの乱数値を入力バッファ８へ入力する。そして、ステップＳ２４に戻り、ステップＳ２４〜２６を経て、ハッシュ演算と、次の１６０ビットの乱数値の抽出と、今まで得られた全部の１６０ビット乱数の結合と、結合された乱数は必要なビット長に達したかどうかの判断を繰り返す。
ステップＳ２４に戻った時に、乱数生成装置４０で実行しているプログラムが発生したデータを一時にＲＡＭ２の非初期化領域に記憶しているので、入力バッファ８は既に書き換えられた。即ち、ステップＳ２４に戻って、次のハッシュ演算を行なう時には、入力バッファ８の値は、前回の入力バッファ８の値と全く異なり、前回の１６０ビットの乱数から予測できない次の１６０ビットの乱数を生成できる。
特に、本実施形態では、乱数生成装置４０が外部コンピュータ４２から受信したデータも、実行しているプログラムよりＲＡＭ２の非初期化領域に書き込むので、入力バッファ８に入力されるデータの範囲はさらに広くなる。これによって、生成された乱数の周期は拡大される。
【００７１】
ステップＳ２８：
結合されたビット列のビット長は、目標の乱数のビット長以上になった場合は、結合されたビット列のビット長から目標の乱数を抽出し、これで目標となる乱数が取得され、乱数生成処理を終了する。
ステップＳ２９：
乱数を取得した後に、乱数生成装置４０は得られた乱数を外部コンピュータ４２に送信する。そして、乱数生成装置４０と外部コンピュータ４２との通信が終了する。
【００７２】
以上の本実施の形態によれば、入力バッファのデータからハッシュ演算によって乱数を生成する時に、入力バッファをＲＡＭのスタック・エリアや、ヒープ・エリアなどの非初期化領域に設置することによって、ハッシュ演算の入力データが毎回異なっているので、外部から初期値からハッシュ演算の結果を推測することが困難となる。
また、初期値はビット長が短くても、入力バッファには、ゼロではなく、全く予測できない値を埋めこむので、入力データの変化範囲は実質上に５１２ビットに拡大し、得られる擬似乱数の周期は２３２より大きくなり、外部からの推測が困難な安全な乱数となる。ＥＥＰＲＯＭ等の不揮発性メモリにシード値を保存しておく必要も不要となる。
さらに、乱数生成装置が外部コンピュータから受信したデータもＲＡＭの非初期化領域に配置するので、入力バッファに入力されるデータの範囲は広くなり、生成された乱数の周期はさらに拡大され、３２ビットの初期値を用い、２１６０の周期に近づくことができる。
これによって、安全性がさらに高く、周期性の長い擬似乱数が高速に得られる。
【００７３】
以上、本発明を好ましい実施の形態に基づき説明したが、本発明は以上に説明した実施の形態に限られるものではなく、本発明の要旨を逸脱しない範囲で、種々の改変が可能である。
例えば、上記の実施形態での乱数生成装置の構成は一例であり、本発明の効果を得られれば、他の構成を用いても良い。
また、上記の実施形態でハッシュ関数としては、主にＳＨＡ−１を例として用いていたが、他のハッシュ関数を用いた場合も本発明を適用できることが明らかである。
また、ＲＡＭの非初期化領域としては、スタック・エリアとヒープ・エリアを例として用いていたが、他のプログラムの実行に妨げず、随時変化するメモリ領域であれば、他のメモリ領域でも良い。
【００７４】
【発明の効果】
以上説明した本発明の乱数生成方法及び乱数生成装置によれば、ハッシュ演算の入力バッファを記憶部の非初期化領域に配置することによって、ハッシュ演算の入力データが随時変化し、毎回の演算に異なっている値となるので、外部から初期値からハッシュ演算の結果を推測することが困難となる。
これによって、初期値はビット長が短くても、入力バッファ８には、予測できない値を埋めこむので、入力データの変化範囲は実質上に拡大され、得られる乱数の周期は大きくなり、推測が一層困難となり、安全な乱数を生成できる。
さらに、専用の回路を必要とせず、容易に実現することが可能となる。
また、真性乱数発生回路を搭載した場合は、真性乱数が生成されるたびにハッシュ値の演算入力として使用し、未生成時は、ハッシュ値の演算結果を使用することによって、安全性がさらに高く、周期性の長い擬似乱数が高速に得られる。
また、乱数生成装置が外部コンピュータから受信したデータもＲＡＭの非初期化領域に配置すれば、入力バッファに入力されるデータの範囲は広くなり、生成された乱数の周期はさらに拡大される。
従って、本発明によれば、デジタル署名生成時や各種公開鍵、共通鍵生成時に必要となる、安全性の高い長周期の擬似乱数を容易にかつ高速に得られることになる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態にかかる乱数演算装置の概略構成を示す図である。
【図２】本発明の第１の実施形態にかかる乱数演算装置において、ハッシュ演算器における処理の概略を示す図である。
【図３】本発明の第１の実施形態にかかる乱数演算装置において、メモリの記憶領域の配置を示す図である。
【図４】本発明の第１の実施形態にかかる乱数演算装置において、ハッシュ演算器の入力バッファをメモリに設ける例を示す図である。
【図５】本発明の第１の実施形態にかかる乱数演算装置において、乱数を生成する処理を示すフローチャートである。
【図６】本発明の第１の実施形態にかかる乱数演算装置において、ハッシュ演算器における演算処理を示す図である。
【図７】図６に続いて、本発明の第１の実施形態にかかる乱数演算装置において、ハッシュ演算器における演算処理を示す図である。
【図８】図７に続いて、本発明の第１の実施形態にかかる乱数演算装置において、ハッシュ演算器における演算処理を示す図である。
【図９】図８に続いて、本発明の第１の実施形態にかかる乱数演算装置において、ハッシュ演算器における演算処理を示す図である。
【図１０】図９に続いて、本発明の第１の実施形態にかかる乱数演算装置において、ハッシュ演算器における演算処理を示す図である。
【図１１】図１０に続いて、本発明の第１の実施形態にかかる乱数演算装置において、ハッシュ演算器における演算処理を示す図である。
【図１２】本発明の第２の実施形態にかかる乱数演算装置の概略構成を示す図である。
【図１３】本発明の第２の実施形態にかかる乱数演算装置において、乱数を生成する処理を示すフローチャートである。
【図１４】本発明の第３の実施形態にかかる乱数演算装置の概略構成を示す図である。
【図１５】本発明の第３の実施形態にかかる乱数演算装置において、乱数を生成する処理を示すフローチャートである。
【符号の説明】
１…ＣＰＵ、２…ＲＡＭ、３…ＥＥＰＲＯＭ、４…ハッシュ演算器、５…バスライン、７…シードエリア、８…入力バッファ、９…出力バッファ、１０…乱数生成装置、１１…スタック・エリア、１１ｂ…一時データ保存エリア、１２…未使用エリア、１３…ヒープ・エリア、１４…スタティック・データ・エリア、１５…コード・エリア、３０…乱数生成装置、３１…真性乱数発生回路、４０…乱数生成装置、４１…インタフェース、４２…外部コンピュータ。
【図１】
2004109420.tif 000003
【図２】
2004109420.tif 000004
【図３】
2004109420.tif 000005
【図４】
2004109420.tif 000006
【図５】
2004109420.tif 000007
【図６】
2004109420.tif 000008
【図７】
2004109420.tif 000009
【図８】
2004109420.tif 000010
【図９】
2004109420.tif 000011
【図１０】
2004109420.tif 000012
【図１１】
2004109420.tif 000013
【図１２】
2004109420.tif 000014
【図１３】
2004109420.tif 000015
【図１４】
2004109420.tif 000016
【図１５】
2004109420.tif 000017