(57)【特許請求の範囲】
【請求項１】
ｎビットの乱数を生成する乱数生成装置であって、
前記乱数を保持するためのｎビットの保持手段と、
ｎより小さいｋビットの乱数を生成する乱数生成手段と、
新たな乱数を生成する旨の指示を受けると前記乱数生成手段により生成されたｋビットの乱数の少なくとも一部を前記保持手段のｎビットの一部に格納すると共に前記保持手段の残る部分には前記保持手段に保持されていた直前の乱数を再利用した値を格納する格納手段と、
前記格納手段により前記保持手段に格納された値を新たな乱数として出力する出力手段と
を備えることを特徴とする乱数生成装置。
【請求項２】
前記乱数生成手段はｋビットのフリーランカウンタであり、
前記格納手段は前記指示を受けた時における前記乱数生成手段のカウント値を前記保持手段に格納する
ことを特徴とする請求項１記載の乱数生成装置。
【請求項３】
前記保持手段は先入れ先だし方式のキューバッファであり、
前記格納手段は前記乱数生成手段により生成された乱数を前記保持手段に格納する
ことを特徴とする請求項２記載の乱数生成装置。
【請求項４】
前記格納手段が前記保持手段に格納する乱数の桁数は可変である
ことを特徴とする請求項３記載の乱数生成装置。
【請求項５】
前記格納手段は前記乱数生成手段により生成された乱数のうち有効桁の部分を前記保持手段に格納する
ことを特徴とする請求項４記載の乱数生成装置。
【請求項６】
前記格納手段は前記乱数生成手段により生成された乱数に対して一定の変換を施した後に前記保持手段に格納する
ことを特徴とする請求項１記載の乱数生成装置。
【請求項７】
前記保持手段はｋビット単位でシフトするレジスタであり、
前記格納手段は前記乱数生成手段により生成されたｋビットの乱数を前記保持手段に格納すると共にシフトされるｋビットデータに対して一定の変換を施した後にシフトさせる
ことを特徴とする請求項１記載の乱数生成装置。
【請求項８】
前記出力手段は前記保持手段に格納された値に対して一定の変換を施した後に新たな乱数として出力する
ことを特徴とする請求項１記載の乱数生成装置。
【請求項９】
相手の正当性を認証する認証装置であって、
請求項１に記載の乱数生成装置により生成されるｎビットの新たな乱数をチャレンジデータとし、前記チャレンジデータを用いてチャレンジ−レスポンス方式により相手の正当性を認証する
ことを特徴とする認証装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は乱数生成装置に関し、特にチャレンジとレスポンスによる機器間の認証に用いられるチャレンジデータを生成する装置に関する。
【０００２】
【従来の技術】
通信路を介して接続されている２つの機器間の認証方法として、国際標準規格ＩＳＯ／ＩＥＣ９７９８−２に記載される暗号技術を用いた一方向認証方法が通常よく利用されている。
証明される機器を証明者、証明者を認証する機器を認証者と称すると、この認証方法は証明者が認証鍵と呼ばれる認証者と同じ秘密のデータを持つことを、その鍵自身を知らせることなく認証者に対して証明することを基本としている。そのためにまず認証者があるデータ（チャレンジデータ）を選びこれを証明者に対して投げかける。これに対し証明者がある暗号変換を保有し前記認証鍵を用いて前記チャレンジデータを暗号化する。このように暗号化されたデータをレスポンスとして認証者に対して返す。このレスポンスを受信した認証者は前記暗号変換の逆変換である復号変換と認証鍵を共有しており、このレスポンスを前記認証鍵を用いて前記復号変換によって復号する。この結果が前記チャレンジデータと一致すれば証明者が正当であると認証する。
【０００３】
この認証方法におけるチャレンジデータは、比較的長いビット長（ｎビット：現在のところ６０ビット以上）のデータであり、できるだけ２＾ｎ（２のｎ乗）通りの値をランダムに取りうることが必要である。これは、機器間の通信路を監視（盗聴）してすべてのチャレンジとレスポンスの組み合わせをテーブルに搾取し、以降のチャレンジに対する偽のレスポンスとして利用するという攻撃（以下、「テーブル攻撃」と呼ぶ。）に対抗するためである。
＜第１の従来例＞
チャレンジデータを生成する方法の一例は、カウンタを用いる方法である。ｎビットのカウンタを設け、認証のたびにこれをカウントアップして用いる。この方法の利点は、カウンタが継続して動作するかぎりは、チャレンジデータが各認証毎に異なることが保証されており、例え機器間の通信路を監視していたとしても、過去の情報を次のチャレンジに対するレスポンス偽造に悪用できないことである。しかし、この方法を安全にするためにはｎビットもの長いビット長のカウンタが必要である。また実際の機器に適用する場合には、カウンタを電源をオフにしても内容が消去しないように実現する必要がある。
＜第２の従来例＞
また、チャレンジデータの別の生成方式の例が、特許公開公報Ｈ８−２９２９３１号に示されている。この方法ではカウンタをフリーランで動作させておき、認証の際に固定の乱数生成演算プログラムで変換して用いる。実際の機器間の認証が、ランダムなタイミングに行われることを利用した方法である。この方法を用いるとカウンタが電源オフでリセットされても、使用するタイミングが任意（ランダム）ならば第１の従来例に比べチャレンジデータとして取りうる値の種類が多くなる。
【０００４】
しかし、この場合であってもカウンタはｎビットの長さを有する必要がある。カウンタが短かければ、カウンタの出力として何度も同じ値が出力されて、前記テーブル攻撃が成立してしまうからである。
＜第３の従来例＞
また、第２の従来例におけるカウンタを、例えば符号理論におけるＭ系列を生成する線形フィードバックシフトレジスタ（ＬＦＳＲ）に置き換える方法も考えられる。Ｍ系列とＬＦＳＲについては、例えば今井秀樹著「符号理論」電子情報通信学会編１９９０に詳しく説明されている。ＬＦＳＲをフリーランで動作させておき、認証の際にこれを止めて、その状態から必要とされるビット長のチャレンジデータを出力するという方法である。
【０００５】
これにより、第２の従来例におけるカウンタと異なり、ＬＦＳＲの内部を秘密にすることで、次のチャレンジデータを予測することすら困難になり安全性が向上する。
しかしながら、２＾ｎ通りのチャレンジデータを生成するにはｎビット以上のＬＦＳＲが必要になる。ＬＦＳＲの取りうる値の種類の数は乱数生成装置の出力ｎビットの取りうる値の種類の数になるからである。例えば、２０ビットのＬＦＳＲの出力が８０ビットである場合、この出力の取りうる値の種類の数は、２＾８０ではなく、２＾２０にしかならない。チャレンジデータが２＾８０通りの値を取るためには、８０ビットのＬＦＳＲを備える必要がある。
【０００６】
【発明が解決しようとする課題】
以上説明したように、上記従来技術では、２＾ｎ通りの値をランダムにとり得るチャレンジデータを生成するには、ｎビットのカウンタや乱数生成手段が必要とされる。つまり、認証に適した安全なチャレンジデータを生成するには大きな規模のハードまたはソフトが必要になる。そのために、製品のコンパクト化や認証用回路のＬＳＩ化等が妨げられる。
【０００７】
そこで、本発明はかかる点に鑑みてなされたものであり、小規模で実現することができるチャレンジデータ生成用の乱数生成装置を提供することを目的とする。
なお、ここでの「乱数」は、次のチャレンジデータが予測できないことを必要としない。チャレンジデータができるだけ多くの値を取りうること（最大２＾ｎ通り）が重要である。具体的には、以下の条件を満たす乱数生成装置を提供することを目的とする。
（１）  ｎビットからなる出力データが、２＾ｎ通りの値を取りうる。
（２）  小さなハードウェアで実現できる。
（３）  あるチャレンジデータから次のチャレンジデータが予測されないほうが望ましい。また出力値から乱数生成装置の内部が解析されないほうが望ましい。
【０００８】
【課題を解決するための手段】
上記目的を達成するために、本発明はｎビットの乱数を生成する乱数生成装置であって、前記乱数を保持するためのｎビットの保持手段と、ｎより小さいｋビットの乱数を生成する乱数生成手段と、新たな乱数を生成する旨の指示を受けると前記乱数生成手段により生成されたｋビットの乱数の少なくとも一部を前記保持手段のｎビットの一部に格納すると共に前記保持手段の残る部分には前記保持手段に保持されていた直前の乱数を再利用した値を格納する格納手段と、前記格納手段により前記保持手段に格納された値を新たな乱数として出力する出力手段とを備えることを特徴とする。
【０００９】
これにより、２＾ｎ通りのチャレンジデータを生成する乱数生成装置が小規模な回路で実現される。
ここで、前記乱数生成手段をｋビットのフリーランカウンタとしたり、前記保持手段をシフトレジスタ等の先入れ先だし方式のキューバッファとしたり、前記保持手段に格納する乱数の桁数を可変としたり、前記乱数生成手段により生成された乱数に対して一定の変換を施した後に前記保持手段に格納したり、前記直前の乱数に対して一定の変換を施した後に再利用したり、前記保持手段に格納された値に対して一定の変換を施したものを新たな乱数として出力したりすることもできる。
【００１０】
これにより、よりコンパクトな乱数生成装置の実現が可能となったり、次に生成される乱数の秘匿度が増したりする。
【００１１】
【発明の実施の形態】
以下、本発明に係る乱数生成装置について図面を用いて詳細に説明する。
（実施の形態１）
図１は、実施形態１における乱数生成装置の構成を示すブロック図である。
本乱数生成装置は、６４ビットのチャレンジデータを生成する乱数生成装置であり、制御部１０、カウンタ１１及４個のシフトレジスタ１２ａ〜１２ｄから構成される。
【００１２】
カウンタ１１は、端子Ｃ１５をＭＳＢ、端子Ｃ０をＬＳＢとする１６ビットのフリーランカウンタであり、電源が投入された時から一定周波数で自ら１ずつインクリメントしている。
４個のシフトレジスタ１２ａ〜１２ｄは、いずれも並列出力端子を有する１６ビットのシフトレジスタであり、クロック端子に１個のクロック信号が入力されると右に１ビットシフトする。これらは、直列に接続されて６４ビットのシフトレジスタ、即ち、先入れ先だし方式のキューバッファを構成し、ここにチャレンジデータを保持する。なお、シフトレジスタ１２ａは、カウンタ１１の出力Ｃ０〜Ｃ１５と接続された並列入力端子を有し、セット信号が入力されるとその瞬間におけるカウンタ１１のカウント値Ｃ０〜Ｃ１５を取り込む。
【００１３】
制御部１０は、新たなチャレンジデータを生成するための制御を行うものであり、その要求を外部から受けたり、セット信号をシフトレジスタ１２ａに出力したり、クロック信号を４個のシフトレジスタ１２ａ〜１２ｄに出力したりする。
次に、以上のように構成された本乱数生成装置の動作について説明する。
図２は、制御部１０の動作を示すフローチャートである。
【００１４】
制御部１０は、外部から新たなチャレンジデータを要求する旨の信号を受けると（ステップＳ２０）、４個のシフトレジスタ１２ａ〜１２ｄそれぞれに１６個のクロック信号を出力する（ステップＳ２１）。その結果、４個のシフトレジスタ１２ａ〜１２ｄに格納されていた６４ビットのチャレンジデータは、右に１６ビットシフトする。つまり、旧チャレンジデータの上位４８ビットＲ１６〜Ｒ６３が下位に１６ビットだけシフトし新チャレンジデータの下位４８ビットＲ０〜Ｒ４７に移動する。
【００１５】
続いて、制御部１０は、シフトレジスタ１２ａにセット信号を出力する（ステップＳ２２）。その結果、セット信号が出力された瞬間におけるカウンタ１１の値がシフトレジスタ１２ａに並列入力される。つまり、このカウンタの値が新チャレンジデータの上位１６ビットＲ４８〜Ｒ６３となる。
以上のようにして、本乱数生成装置は、カウンタ１１からの新たな値を上位１６ビットとし、直前のチャレンジデータの上位４８ビットを下位４８ビットとする６４ビットの新たなチャレンジデータを生成する。
【００１６】
なお、本乱数生成装置は機器間の認証がランダムな時間に行われることを利用したものである。つまり、チャレンジデータの要求が任意の（ランダムな）タイミングで発生するため、カウンタ１１からシフトレジスタ１２ａに並列入力される値は２＾１６通りの値をとり得る。そして、他のシフトレジスタ１２ｂ〜１２ｄに格納されている値は過去にシフトレジスタ１２ａに格納されていた値であることを考慮すると、これら全体の６４ビットのシフトレジスタ１２ａ〜１２ｄは、２＾６４通りの値をとり得る。
【００１７】
また、４個のシフトレジスタ１２ａ〜１２ｄは、チャレンジデータの生成のためだけでなく、本装置の出力用レジスタとしての機能も兼用している。
従って、本装置は実質的には１個の１６ビットカウンタ１１だけを用いて６４ビットのチャレンジデータを生成する乱数生成装置である、と言うことができる。これにより、小さなハードウェア規模で大きな乱数を生成する装置が実現される。
（実施の形態２）
次に、実施の形態２に係る乱数生成装置について説明する。
【００１８】
本実施形態は、実施形態１と同様に６４ビットのチャレンジデータを生成する乱数生成装置であるが、常に上位１６ビットを固定的に更新した実施形態１と異なり、更新する上位ビット数を可変とすることを特徴とする。実施形態１と相違する点を中心に説明する。
図３は、実施形態２に係る乱数生成装置の構成を示すブロック図である。実施形態１の乱数生成装置と同一の構成要素１１、１２ａ〜１２ｄには同一の符号を付けている。
【００１９】
本乱数生成装置は、実施形態１に更に１個のシフトレジスタ１２ｅを追加し、実施形態１の制御部１０を新たな制御部１３に替えたものである。
新たなシフトレジスタ１２ｅは、実施形態１のシフトレジスタ１２ａと同一機能を有し、実施形態１における４個のシフトレジスタ１２ａ〜１２ｄの上位桁に直列に接続され、セット信号が入力されるとカウンタ１１からのカウント値が並列入力される。
【００２０】
制御部１３は、実施形態１の制御部１０が有する機能に加えて有効桁検出部１３ａを有している。この有効桁検出部１３ａは、制御部１０がセット信号を発した時におけるカウンタ１１のカウント値（これは同時にシフトレジスタ１２ｅに並列入力される値に等しい）の有効桁数を検出する。ここで、有効桁とは、リーディングゼロを除く桁をいい、例えば、カウント値が”０００１０１１１００１０１１０１”である場合には上位３桁のリーディングゼロを除く１３桁が有効桁となる。
【００２１】
この制御部１０は、新たなチャレンジデータの要求を受けるごとに常に１６個のクロック信号を発した実施形態１と異なり、有効桁検出部１３ａにより検出された有効桁数だけのクロック信号を発する。
図４は、制御部１０の動作を示すフローチャートである。
外部より新たなチャレンジデータの要求を受けると（ステップＳ３０）、まず、シフトレジスタ１２ｅにセット信号を発する（ステップＳ３１）。その結果、カウンタ１１からの１６ビットのカウント値は、シフトレジスタ１２ｅに並列入力されると同時に、有効桁検出部１３ａにも取り込まれる。
【００２２】
そして、有効桁検出部１３ａはそのカウント値の有効桁数を検出する（ステップＳ３２）。
最後に、制御部１０は、有効桁検出部１３ａが検出した有効桁数だけのクロック信号を６個のシフトレジスタ１２ａ〜１２ｅに出力する（ステップＳ３３）。その結果、４個のシフトレジスタ１２ａ〜１２ｄに格納されていた旧チャレンジデータは、そのクロック数に相当する桁数だけ右にシフトされ、新たなチャレンジデータとなる。
【００２３】
このように、本実施形態に係る乱数生成装置によれば、旧チャレンジデータの上位に格納される新たなカウント値の桁数が可変（ランダム）であるため、その桁数が固定である実施形態１に比べ、新たなチャレンジデータの予測はより困難になる。
（実施の形態３）
次に、実施の形態３に係る乱数生成装置について説明する。
【００２４】
本実施形態は、実施形態１と同様に６４ビットのチャレンジデータを生成する乱数生成装置であるが、旧チャレンジデータの上位桁にフリーランカウンタからのカウント値をそのまま入力した実施形態１と異なり、そのカウント値に対して変換を施した後に入力することを特徴とする。
図５は、実施形態３に係る乱数生成装置の構成を示すブロック図である。カウンタ１１は実施形態１と同一の機能を有する。
【００２５】
データ変換器１５は、セット信号が入力されるとその瞬間におけるカウンタ１１のカウント値を取り込み、一定の変換を施す。
図６は、このデータ変換器１５の変換ロジックの一例を示す図である。
データ変換器１５は、鍵データ記憶部１５２０と１５個の排他的論理和部１５００〜１５１５から構成され、入力されたカウント値Ｃ０〜１５と鍵データ記憶部１５２０に予め格納された１６ビットの秘密鍵データＦ０〜Ｆ１５とをビット毎に排他的論理和をとり、その結果を新たな１６ビットデータＤ０〜Ｄ１５として出力する。
【００２６】
４個のレジスタ１６ａ〜１６ｄはそれぞれ１６ビット並列入出力のレジスタであり、これらは６４ビットのチャレンジデータを保持するためのものであり、パイプラインを構成している。つまり、１個のクロック信号が入力されると、上段のレジスタ（又はデータ変換器１５）の値を取り込む。即ち、データ変換器１５と４個のレジスタ１６ａ〜１６ｄからなる合計８０ビットの保持手段は、一度に１６ビットだけ下位にシフトする８０ビットのシフトレジスタを構成していると言える。
【００２７】
制御部１４は、実施形態１の制御部１０に相当するものであり、以下の制御を行う。
外部から新たなチャレンジデータを要求する旨の信号を受けると、まず、データ変換器１５にセット信号を出力する。その結果、セット信号が出力された瞬間におけるカウンタ１１の値がデータ変換器１５に取り込まれ、変換が施される。
【００２８】
次に、制御部１４は、４個のレジスタ１６ａ〜１６ｄに１個のクロック信号を出力する。その結果、４個のレジスタ１６ａ〜１６ｄは、それぞれ直前の上段のデータ変換器１５及びレジスタ１６ａ〜１６ｃに格納されていた１６ビットデータを取り込む。
これによって、フリーランカウンタ１１からのカウント値はデータ変換器１５において変換された後に新チャレンジデータの上位１６ビットＲ４８〜Ｒ６３に格納され、旧チャレンジデータの上位４８ビットＲ１６〜Ｒ６３が下位に１６ビットだけシフトされて新チャレンジデータの下位４８ビットＲ０〜Ｒ４７に移動し、その結果、４個のレジスタ１６ａ〜１６ｄに新たなチャレンジデータＲ０〜Ｒ６３が生成される。
【００２９】
以上のように、実施形態１では旧チャレンジデータを要求した時から新チャレンジデータを要求するまでの時間（フリーランカウンタ１１でのインクリメント数）が分かると新チャレンジデータの上位１６ビットに格納される値が判明してしまう弱点があったが、本実施形態ではカウンタ１１とレジスタ１６ａとの間に秘密のデータ変換器１５が挿入されているために、その値の予測はより困難なものとなる。
（実施の形態４）
次に、実施の形態４に係る乱数生成装置について説明する。
【００３０】
本実施形態は、実施形態３と同様に４個の１６ビットレジスタ１６ａ〜１６ｄを用いて６４ビットのチャレンジデータを生成する乱数生成装置であるが、カウンタ１１と最上段のレジスタ１６ａとの間に変換器を挿入するのではなく、各レジスタ１６ａ〜１６ｄ間に変換器を挿入したことを特徴とする。
図７は、実施形態４に係る乱数生成装置の構成を示すブロック図である。
【００３１】
実施形態３と異なり、各１６ビットレジスタ１６ａ〜１６ｄの間にデータ変換器１７ａ〜１７ｃが挿入され、直列に接続されている。
各データ変換器１７ａ〜１７ｃは、例えば図６に示される変換ロジックを有するものである。
上記４個のレジスタ１６ａ〜１６ｄと３個のデータ変換器１７ａ〜１７ｃは、４段のパイプラインを構成する。即ち、最上段がレジスタ１６ａとデータ変換器１７ａとの組であり、第２段がレジスタ１６ｂとデータ変換器１７ｂとの組であり、第３段がレジスタ１６ｃとデータ変換器１７ｃとの組であり、最下段がレジスタ１６ｄである。
【００３２】
制御部１８は、外部から新たなチャレンジデータを要求する旨の信号を受けると、４個のレジスタ１６ａに１個のクロック信号を出力する。
その結果、４個のレジスタ１６ａ〜１６ｄはそれぞれ上段のカウンタ１１及びデータ変換器１７ａ〜１７ｃからの値を取り込み、その直後にデータ変換器１７ａ〜１７ｃはそれぞれ上段のレジスタ１６ａ〜１６ｃに取り込まれた新たな値を変換する。
【００３３】
このようにして、本乱数生成装置では、外部から新たなチャレンジデータを要求する旨の信号が入力されると、フリーランカウンタ１１のカウント値が新チャレンジデータの上位１６ビットＲ４８〜Ｒ６３に格納され、旧チャレンジデータの上位４８ビットＲ１６〜Ｒ６３が１６ビット単位で変換が施された後に下位に１６ビットだけシフトされて新チャレンジデータの下位４８ビットＲ０〜Ｒ４７に移動し、その結果、４個のレジスタ１６ａ〜１６ｄに新たなチャレンジデータＲ０〜Ｒ６３が生成される。
【００３４】
以上のように、本実施形態の乱数生成装置は、実施形態１の場合と同様に新たなチャレンジデータを生成する際には旧チャレンジデータの上位４８ビットを再利用しているが、１６ビット単位で変換を施した後に新チャレンジデータの一部としているので、新チャレンジデータを見ただけでは直前のチャレンジデータが再利用されているとは分かりにくくなっている。
【００３５】
なお、本実施形態の３個のデータ変換器１７ａはいずれも同一の変換ロジックを有したが異なるものであってもよい。これにより、新チャレンジデータの予測をさらに困難なものとすることができる。
（実施の形態５）
次に、実施の形態５に係る乱数生成装置について説明する。
【００３６】
本実施形態は、実施形態３と同様に４段のパイプライン（４個の１６ビットレジスタ１６ａ〜１６ｄ）からなる乱数生成装置であるが、カウンタ１１と最上段のレジスタ１６ａとの間に変換器を挿入するのではなく、各レジスタ１６ａ〜１６ｄの出力に変換器を置いたことを特徴とする。
図８は、実施形態５に係る乱数生成装置の構成を示すブロック図である。
【００３７】
カウンタ１１、制御部１８及び４個のレジスタ１６ａ〜１６ｄは実施形態４のものと同一である。
データ変換器１９は、入力された６４ビットデータに一定の変換を施し新たな６４ビットデータとして出力するものであり、例えば図６に示されるようなデータ変換器１５を６４ビットに拡張した構成を有する。但し、入力データを１６ビット単位のブロックに分割したときに、各ブロックに対する変換が相異なるように、秘密鍵データを設定している。
【００３８】
制御部１８は、外部から新たなチャレンジデータを要求する旨の信号を受けると、４個のレジスタ１６ａに１個のクロック信号を出力する。
その結果、４個のレジスタ１６ａ〜１６ｄはそれぞれ上段のカウンタ１１及びレジスタ１６ａ〜１６ｃからの値を取り込む。つまり、フリーランカウンタ１１のカウント値がレジスタ１６ａに格納され、３個のレジスタ１６ｂ〜１６ｄにはそれぞれ上段のレジスタ１６ａ〜１６ｃの値が格納される。
【００３９】
そして、４個のレジスタ１６ａに格納された新たな６４ビットデータは、データ変換器１９において変換が施され、新たな６４ビットのチャレンジデータとなる。
このように、本実施形態の乱数生成装置は、原理的には実施形態１の乱数生成装置の出力に対して更に秘密の変換を行うデータ変換器１９を付加した構成を有するものであり、新たなチャレンジデータの予測は更に困難となる。
【００４０】
なお、上記実施形態１〜５の乱数生成装置は、いずれも１６ビットのフリーランカウンタ１１を備える６４ビットのチャレンジデータを生成するものであったが、本発明はこのような数値に限定されるものではない。例えば、３２ビットのフリーランカウンタを備える５１２ビットのチャレンジデータを生成する乱数生成装置とすることもできる。
【００４１】
また、フリーランカウンタ１１を１６ビットの乱数生成装置に置き換えることもできる。例えば第３の従来例のＬＦＳＲで実現してもよい。本発明は、フリーランカウンタを用いることを要旨とするのではなく、小さいビット数の乱数を生成する装置を用いてその乱数よりも大きいビット数の乱数を生成することを要旨とするからである。
【００４２】
また、本発明は、論理回路を用いたハードウェアにより実現することができるだけでなく、ソフトウェアにより実現することもできるのは言うまでもない。
また、実施形態２の乱数生成装置は、カウント値の有効桁数だけ旧チャレンジデータを右にシフトしたが、シフトする桁数を可変にする方法としてはこの方法に限られず、例えば、カウント値と一定のハッシュ関数から得られるハッシュ値をシフトする桁数とすることもできる。
【００４３】
また、実施形態４のデータ変換器１７ａ〜１７ｃは独立した別個のものであっても共通する１個のものであってもよい。変換ロジックは同じであるが、各鍵データ記憶部に格納しておく秘密鍵データだけをそれぞれ異なるものとすることもできる。
さらに、実施形態３〜５におけるデータ変換器１５、１７ａ〜１７ｃ、１９は、図６に示されたような排他的論理和を行うものに限られず、例えば、ビット置換を行うための配線だけからなるものとすることもできる。これにより、回路のコンパクト化や処理の高速化が可能となる。
【００４４】
【発明の効果】
以上の説明から明らかなように、本発明はｎビットの乱数を生成する乱数生成装置であって、前記乱数を保持するためのｎビットの保持手段と、ｎより小さいｋビットの乱数を生成する乱数生成手段と、新たな乱数を生成する旨の指示を受けると前記乱数生成手段により生成されたｋビットの乱数の少なくとも一部を前記保持手段のｎビットの一部に格納すると共に前記保持手段の残る部分には前記保持手段に保持されていた直前の乱数を再利用した値を格納する格納手段と、前記格納手段により前記保持手段に格納された値を新たな乱数として出力する出力手段とを備えることを特徴とする。
【００４５】
つまり、直前の乱数を再利用することで新たな乱数の一部としているので、実質的にｎより小さいｋビットの乱数生成手段によってｎビットもの長い乱数を生成することが可能となる。これにより、チャレンジデータ生成用の乱数生成装置を小規模で実現することが可能となる。
ここで、前記乱数生成手段をｋビットのフリーランカウンタとし、前記格納手段は前記指示を受けた時における前記乱数生成手段のカウント値を前記保持手段に格納するとすることもできる。
【００４６】
これにより、ｋビットの乱数生成手段をコンパクトなものとすることができる。
また、前記保持手段をシフトレジスタ等の先入れ先だし方式のキューバッファとし、前記格納手段は前記乱数生成手段により生成された乱数を前記保持手段に格納するとすることもできる。
【００４７】
これにより、前記再利用を簡易な回路で実現することが可能となる。
また、前記格納手段が前記保持手段に格納する乱数の桁数を可変とすることもできる。例えば、乱数のうち有効桁の部分のみを格納する等である。
これにより、フリーランカウンタが作動した時間が分かった場合であっても次の乱数の予測が困難となる。
【００４８】
また、前記格納手段は前記乱数生成手段により生成された乱数に対して一定の変換を施した後に前記保持手段に格納したり、前記保持手段においてシフトされるｋビットデータに対して一定の変換を施した後にシフトさせたり、前記出力手段は前記保持手段に格納された値に対して一定の変換を施した後に新たな乱数として出力したりすることもできる。
【００４９】
これにより、直前の乱数に基づいて次の乱数を予測することが困難となり、その秘匿度が増す。
よって、本発明により、小規模の構成で大きな桁数の乱数を生成することができる乱数生成装置が実現され、特にチャレンジ・レスポンス型の機器間認証におけるランダムなチャレンジデータの生成に好適であり、その実用的価値は大きい。
【図面の簡単な説明】
【図１】本発明の実施形態１における乱数生成装置の構成を示すブロック図である。
【図２】図１に示された制御部１０の動作を示すフローチャートである。
【図３】本発明の実施形態２における乱数生成装置の構成を示すブロック図である。
【図４】図３に示された制御部１３の動作を示すフローチャートである。
【図５】本発明の実施形態３における乱数生成装置の構成を示すブロック図である。
【図６】図５に示されたデータ変換器１５の構成を示すブロック図である。
【図７】本発明の実施形態４における乱数生成装置の構成を示すブロック図である。
【図８】本発明の実施形態５における乱数生成装置の構成を示すブロック図である。
【符号の説明】
１０    制御部
１１    フリーランカウンタ
１２ａ〜１２ｅ  シフトレジスタ
１３、１４、１８    制御部
１３ａ  有効桁検出部
１５、１７ａ〜１７ｃ、１９    データ変換器
１５００〜１５１５  排他的論理和部
１５２０  鍵データ記憶部
１６ａ〜１６ｄ    レジスタ
【図１】
0003606418.tif 000002
【図２】
0003606418.tif 000003
【図３】
0003606418.tif 000004
【図４】
0003606418.tif 000005
【図５】
0003606418.tif 000006
【図６】
0003606418.tif 000007
【図７】
0003606418.tif 000008
【図８】
0003606418.tif 000009