(57)【要約】【課題】Ｍ系列等の擬似乱数系列のタップ位置を自由に変更可能な、回路規模の小さい乱数生成回路を提供する。【解決手段】乱数生成回路は、擬似乱数系列の擬似乱数を生成する線形帰還シフトレジスタと、擬似乱数系列におけるタップ位置を記憶するレジスタと、前記線形帰還シフトレジスタに記憶されているデータと、前記レジスタに記憶されているタップ位置とに基づいて、前記線形帰還シフトレジスタへの帰還信号を生成する帰還信号生成回路と、を備える。【選択図】  図４
2006215825.tif 000002
【特許請求の範囲】
【請求項１】
擬似乱数系列の擬似乱数を生成する線形帰還シフトレジスタと、
擬似乱数系列におけるタップ位置を記憶するレジスタと、
前記線形帰還シフトレジスタに記憶されているデータと、前記レジスタに記憶されているタップ位置とに基づいて、前記線形帰還シフトレジスタへの帰還信号を生成する帰還信号生成回路と、
を備えることを特徴とする乱数生成回路。
【請求項２】
請求項１に記載の乱数生成回路であって、
前記レジスタは、
前記線形帰還シフトレジスタと同一ビット数で構成され、擬似乱数系列のタップ位置に対応するビットに一方の論理値が記憶され、タップ位置に対応するビット以外のビットに他方の論理値が記憶されており、
前記帰還信号生成回路は、
前記線形帰還シフトレジスタの各ビットと、前記レジスタの各ビットとの論理積を行う回路と、当該論理積により得られるデータの排他的論理和により前記帰還信号を生成する回路と、
を備えることを特徴とする乱数生成回路。
【請求項３】
請求項１又は２に記載の乱数生成回路であって、
物理乱数を生成する物理乱数生成回路と、
前記物理乱数生成回路により生成された物理乱数を前記線形帰還シフトレジスタにより生成された擬似乱数に応じて変化させて出力する変調回路と、
を更に備えることを特徴とする乱数生成回路。
【請求項４】
擬似乱数系列の擬似乱数を生成する線形帰還シフトレジスタと、
複数の擬似乱数系列における夫々のタップ位置を記憶する複数のレジスタと、
前記複数の擬似乱数系列のうちの何れの擬似乱数系列を用いるかを示す選択信号を受信し、当該選択信号に基づいて前記複数のレジスタの何れかを選択する選択回路と、
前記線形帰還シフトレジスタに記憶されているデータと、前記選択回路により選択されたレジスタに記憶されているタップ位置とに基づいて、前記線形帰還シフトレジスタへの帰還信号を生成する帰還信号生成回路と、
を備えることを特徴とする乱数生成回路。
【請求項５】
請求項４に記載の乱数生成回路であって、
前記レジスタは、
前記線形帰還シフトレジスタと同一ビット数で構成され、擬似乱数系列のタップ位置に対応するビットに一方の論理値が記憶され、タップ位置に対応するビット以外のビットに他方の論理値が記憶されており、
前記帰還信号生成回路は、
前記線形帰還シフトレジスタの各ビットと、前記選択回路により選択されたレジスタの各ビットとの論理積を行う回路と、当該論理積により得られるデータの排他的論理和により前記帰還信号を生成する回路と、
を備えることを特徴とする乱数生成回路。
【請求項６】
請求項４又は５に記載の乱数生成回路であって、
物理乱数を生成する物理乱数生成回路を更に備え、
前記選択信号は、前記物理乱数生成回路により生成された物理乱数であることを特徴とする乱数生成回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの暗号化等に用いられる乱数を生成する乱数生成回路に関する。
【背景技術】
【０００２】
近年、様々な情報処理システムにおいて、データの暗号化が行われている。暗号化においては、安全性を向上させるために乱数が用いられることが多い。このような乱数としては、例えば、線形帰還シフトレジスタを用いて生成可能なＭ系列（Maximum length code）等の擬似乱数がある。また、Ｍ系列等の擬似乱数以外の乱数としては、原子核の崩壊現象がランダムとなることや電気雑音等の自然現象を利用した物理乱数が知られており、暗号化においても物理乱数を利用することができる。さらに、線形帰還シフトレジスタにより生成されるＭ系列等の擬似乱数と物理乱数とを組み合わせることにより、乱数の予測困難性を高めることができる（例えば、特許文献１）。
【特許文献１】特開２００４−１５７１６８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、特許文献１に開示されている乱数生成装置においては、Ｍ系列におけるタップ位置が予め定められ、線形帰還シフトレジスタのタップ位置に対応するビットの排他的論理和を行う回路が構成されている。そのため、乱数生成装置を構成した後に、そのタップ位置を変更することが困難である。また、このような構造において、複数のＭ系列のタップ位置に対して夫々排他的論理和を行う回路を設け、その何れかを用いる構成とすることも可能であるが、対応するＭ系列の数に応じて回路規模が大きくなってしまう。
【０００４】
本発明は上記課題を鑑みてなされたものであり、Ｍ系列等の擬似乱数系列のタップ位置を自由に変更可能な、回路規模の小さい乱数生成回路を提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記目的を達成するため、本発明の乱数生成回路は、擬似乱数系列の擬似乱数を生成する線形帰還シフトレジスタと、擬似乱数系列におけるタップ位置を記憶するレジスタと、前記線形帰還シフトレジスタに記憶されているデータと、前記レジスタに記憶されているタップ位置とに基づいて、前記線形帰還シフトレジスタへの帰還信号を生成する帰還信号生成回路と、を備えることとする。
【０００６】
そして、前記レジスタは、前記線形帰還シフトレジスタと同一ビット数で構成され、擬似乱数系列のタップ位置に対応するビットに一方の論理値が記憶され、タップ位置に対応するビット以外のビットに他方の論理値が記憶されており、前記帰還信号生成回路は、前記線形帰還シフトレジスタの各ビットと、前記レジスタの各ビットとの論理積を行う回路と、当該論理積により得られるデータの排他的論理和により前記帰還信号を生成する回路と、を備えることとすることができる。
【０００７】
また、物理乱数を生成する物理乱数生成回路と、前記物理乱数生成回路により生成された物理乱数を前記線形帰還シフトレジスタにより生成された擬似乱数に応じて変化させて出力する変調回路と、を更に備えることとしてもよい。
【０００８】
また、本発明の乱数生成回路は、擬似乱数系列の擬似乱数を生成する線形帰還シフトレジスタと、複数の擬似乱数系列における夫々のタップ位置を記憶する複数のレジスタと、前記複数の擬似乱数系列のうちの何れの擬似乱数系列を用いるかを示す選択信号を受信し、当該選択信号に基づいて前記複数のレジスタの何れかを選択する選択回路と、前記線形帰還シフトレジスタに記憶されているデータと、前記選択回路により選択されたレジスタに記憶されているタップ位置とに基づいて、前記線形帰還シフトレジスタへの帰還信号を生成する帰還信号生成回路と、を備えることとする。
【０００９】
そして、前記レジスタは、前記線形帰還シフトレジスタと同一ビット数で構成され、擬似乱数系列のタップ位置に対応するビットに一方の論理値が記憶され、タップ位置に対応するビット以外のビットに他方の論理値が記憶されており、前記帰還信号生成回路は、前記線形帰還シフトレジスタの各ビットと、前記選択回路により選択されたレジスタの各ビットとの論理積を行う回路と、当該論理積により得られるデータの排他的論理和により前記帰還信号を生成する回路と、を備えることとすることができる。
【００１０】
また、物理乱数を生成する物理乱数生成回路を更に備え、前記選択信号は、前記物理乱数生成回路により生成された物理乱数であることとすることができる。
【発明の効果】
【００１１】
Ｍ系列等の擬似乱数系列のタップ位置を自由に変更可能で、かつ、回路規模の小さい乱数生成回路を提供することができる。
【発明を実施するための最良の形態】
【００１２】
＝＝全体構成＝＝
図１は、本発明の乱数生成回路を用いる一実施形態である自動車の錠の施錠・解錠を行うキーレスエントリーシステム１の全体構成を示す図である。キーレスエントリーシステム１は、携帯型の子機２と自動車等に搭載される親機３とを含んで構成されている。子機２は、例えば、自動車のドアロックやステアリングロックの鍵穴に差し込むキーのハンドル部等に設けられている。また、親機３は、自動車側に設けられている。
【００１３】
子機２は、電池１１、操作スイッチ１２、データ処理回路１３、及び送受信回路１４を備えている。電池１１は、子機２の各部の動作に必要な電力を供給するためのものである。操作スイッチ１２は、利用者からの施錠・解錠の指示を受け付けるスイッチである。データ処理回路１３は、施錠・解錠の際に必要となる認証用のデータの生成等を行う。送受信回路１４は、データ処理回路１３から出力されるデジタルデータをアナログデータに変換し、これを増幅して電磁波として送出する回路である。また、送受信回路１４は、親機３から送出された電磁波を受信し、これをデジタルデータに変換してデータ処理回路１３に入力することもできる。なお、電磁波としては、電波や赤外線が用いられる。
【００１４】
親機３は、データ処理回路２１、送受信回路２２、及び駆動回路２３を備えている。データ処理回路２１は、子機２から受信する認証用のデータに基づいた認証処理等を行う。送受信回路２２は、子機２から送出された電磁波を受信し、これをデジタルデータに変換してデータ処理回路２２に入力する回路である。また、送受信回路２２は、データ処理回路２１から出力されるデジタルデータをアナログデータに変換し、これを増幅して電磁波として送出することもできる。駆動回路２３は、自動車の錠を施錠・解錠するロック機構を作動させるアクチュエータ２４に駆動信号を送信する回路である。なお、親機２の各部２１〜２３には、自動車のバッテリ２５から電力が供給されている。
【００１５】
＝＝データ処理回路の構成＝＝
図２は、データ処理回路１３の構成を示す図である。データ処理回路１３は、ＣＰＵ５１Ａ、ＲＡＭ（Random Access Memory）５２Ａ、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read-Only Memory）５３Ａ、乱数生成回路５４Ａ、暗号処理回路５５Ａ、及び入出力ポート５６Ａを備えている。そして、各部５１Ａ〜５６Ａはバス５７Ａにより互いに通信可能に接続されている。
【００１６】
ＣＰＵ５１Ａは、データ処理回路１３の全体を制御するものである。ＲＡＭ５２Ａには、ＣＰＵ５１Ａが使用する作業用データ等が記憶される。ＥＥＰＲＯＭ５３Ａは書き換え可能な不揮発性メモリであり、プログラムや保存用のデータ等が記憶されている。乱数生成回路５４Ａは、暗号化の処理において用いられる乱数を生成する回路である。暗号処理回路５５Ａは、共通鍵ブロック暗号方式における転置又は換字等の処理を行う回路である。入出力ポート５６Ａは、データ処理回路１３の外部にある操作スイッチ１２や送受信回路１４等とデータの送受信を行うためのインタフェースである。
【００１７】
なお、本実施形態では、共通鍵ブロック暗号方式としてＤＥＳ（Data Encryption Standard）を用いることとする。このようなデータ処理回路１３では、プログラムの実行や暗号処理回路５５Ａの制御等により、ＤＥＳの暗号化又は復号の処理が行われる。なお、データ処理回路２１も同様の構成であり、ＣＰＵ５１Ｂ、ＲＡＭ５２Ｂ、ＥＥＰＲＯＭ５３Ｂ、乱数生成回路５４Ｂ、暗号処理回路５５Ｂ、入出力ポート５６Ｂ、及び各部５１Ｂ〜５６Ｂを互いに通信可能に接続するバス５７Ｂを備えている。
【００１８】
＝＝通信手順＝＝
図３は、キーレスエントリーシステム１の子機２と親機３との間における通信手順を示すフローチャートである。まず、子機２の操作スイッチ１２の操作等により送信処理が起動される（Ｓ３０１）。子機２のデータ処理回路１３は、ＥＥＰＲＯＭ５３Ａに記憶されている車番（車体番号）を親機３に送信する（Ｓ３０２）。親機３のデータ処理回路２１は、子機２から車番が送信されてくるのを待機しており（Ｓ３０３）、子機２から送信されてくる車番を受信すると、当該車番をＥＥＰＲＯＭ５３Ｂに記憶されている車番と比較する（Ｓ３０４）。
【００１９】
車番が一致しない場合（Ｓ３０４：ＮＧ）、親機３のデータ処理回路２１は、別の自動車の車番が送信されてきたと判断し、受信待機処理に戻る（Ｓ３０３）。車番が一致すると（Ｓ３０４：ＯＫ）、データ処理回路２１は、乱数生成回路５４Ｂを用いて６４ビットの乱数である一時鍵Ｒ０を生成する（Ｓ３０５）。そして、データ処理回路２１は、この一時鍵Ｒ０を、ＥＥＰＲＯＭ５３Ｂに記憶されている共通鍵Ｋを用いてＤＥＳで暗号化して子機２に送信する（Ｓ３０６）。
【００２０】
子機２のデータ処理回路１３は、親機３から送信されてくる暗号化された一時鍵Ｒ０を受信すると、ＥＥＰＲＯＭ５３Ａに記憶されている共通鍵Ｋを用いて一時鍵Ｒ０を復号する（Ｓ３０７）。続いて、データ処理回路１３は、乱数生成回路５４Ａを用いて６４ビットの乱数である一時鍵Ｒ１を生成する（Ｓ３０８）。そして、データ処理回路１３は、この一時鍵Ｒ１を親機３から受信した一時鍵Ｒ０を用いてＤＥＳで暗号化して親機３に送信する（Ｓ３０９）。親機３のデータ処理回路２１は、子機２から送信されてくる暗号化された一時鍵Ｒ１を受信すると、一時鍵Ｒ０を用いて一時鍵Ｒ１を復号する（Ｓ３１０）。
【００２１】
その後、子機２のデータ処理回路１３は、施錠・解錠指示等の情報データを、一時鍵Ｒ１を用いてＤＥＳで暗号化して親機３に送信する（Ｓ３１１）。親機３のデータ処理回路２１は、子機２から送信されてくる暗号化された情報データを受信すると、一時鍵Ｒ１を用いて情報データを復号する（Ｓ３１２）。そして、データ処理回路２１は、情報データに基づいて、例えば、駆動回路２３を介してアクチュエータ２４に施錠・解錠指示信号を送信する。
【００２２】
このように、キーレスエントリーシステム１においては、子機２及び親機３において乱数生成回路５４Ａ，５４Ｂを用いて一時鍵を生成し、ＤＥＳによる暗号化及び復号の処理を繰り返し行うことにより、セキュリティ強度を高めている。
【００２３】
＝＝乱数生成回路の構成＝＝
本実施形態においては、図３で説明した暗号化及び復号の処理における乱数生成処理において、乱数生成回路５４Ａ，５４Ｂが用いられている。乱数生成回路５４Ａ及び乱数生成回路５４Ｂは同様の構成であるため、以後、乱数生成回路５４Ａについて説明する。
【００２４】
図４は、乱数生成回路５４Ａの構成を示す図である。乱数生成回路５４Ａは、分周回路６１、ボーレートジェネレータ６２、カウンタ６３、シフトレジスタ６４、マスクＡレジスタ６５、マスクＢレジスタ６６、マルチプレクサ（選択回路）６７、ＡＮＤ回路６８、奇数パリティジェネレータ６９、物理乱数生成回路７０、ＯＲ回路７１、Ｄ型フリップフロップ（以後、「Ｄ−ＦＦ」と称する）７２、ＡＮＤ回路７３、ＯＲ回路７４、ＥＸＯＲ回路（変調回路）７５、マルチプレクサ７６、及びシフトレジスタ７７を備えている。また、シフトレジスタ６４、マスクＡレジスタ６５、マスクＢレジスタ６６、及びシフトレジスタ７７は、バス５７Ａに接続されている。なお、ＡＮＤ回路６８及び奇数パリティジェネレータ６９により、本発明の帰還信号生成回路が構成されている。
【００２５】
分周回路６１は、データ処理回路１３における例えば６ＭＨｚのシステムクロック（Ｓｙｓ＿ｃｌｋ）を４分の１に分周する回路である。また、ボーレートジェネレータ６２は、例えば８ビットのレジスタに分周値を設定可能な回路である。そして、カウンタ６３は、分周回路６１から出力されるクロックをボーレートジェネレータ６２に設定された分周値に基づいてカウントすることにより、乱数生成回路５４Ａの動作クロック（ＲＣＬＫ）を出力する。
【００２６】
シフトレジスタ６４は、例えば３２ビット（Ｑ０〜Ｑ３１）の線形帰還シフトレジスタであり、クロック入力（Ｃ）には動作クロック（ＲＣＬＫ）が入力され、１ビット目（Ｑ０）のデータ入力端子（Ｄ）に帰還信号（Ｆ）が入力される。なお、シフトレジスタ６４の初期値は、ＣＰＵ５１Ａによりバス５７Ａを介して設定される。
【００２７】
マスクＡレジスタ６５は、例えば３２ビット（ＡＱ０〜ＡＱ３１）のレジスタであり、シフトレジスタ６４でＭ系列の擬似乱数を生成する際のタップ位置を記憶するものである。例えば、シフトレジスタ６４を用いて４ビットのＭ系列を生成する場合、帰還信号（Ｆ）を、例えば原始多項式Ｘ４＋Ｘ＋１に基づいて次式（１）により求めることができる。
【数１】
2006215825.tif 000003
【００２８】
つまり、この場合、タップ位置は３ビット目と４ビット目であり、マスクＡレジスタ６５の３ビット目（ＡＱ２）と４ビット目（ＡＱ３）とに、例えば“１”が設定され、マスクＡレジスタ６５のその他のビットには、例えば“０”が設定される。
【００２９】
同様に、マスクＢレジスタ６６は、例えば３２ビット（ＢＱ０〜ＢＱ３１）のレジスタであり、マスクＡレジスタ６６とは異なるタップ位置を記憶するものである。例えば、シフトレジスタ６４を用いて前述したものとは異なる４ビットのＭ系列を生成する場合、帰還信号（Ｆ）を、例えば原始多項式Ｘ４＋Ｘ３＋１に基づいて次式（２）により求めることができる。
【数２】
2006215825.tif 000004
【００３０】
つまり、この場合、タップ位置は１ビット目と４ビット目であり、マスクＢレジスタ６６の１ビット目（ＢＱ０）と４ビット目（ＢＱ３）とに、例えば“１”が設定され、マスクＢレジスタ６６のその他のビットには、例えば“０”が設定される。なお、マスクＡレジスタ６５及びマスクＢレジスタ６６の値は、ＣＰＵ５１Ａによりバス５７Ａを介して設定される。
【００３１】
マルチプレクサ６７には、マスクＡレジスタ６５の値（ＡＱ０〜ＡＱ３１）とマスクＢレジスタ６６の値（ＢＱ０〜ＢＱ３１）とが入力されており、選択信号（ＳＥＬ）が例えば“０”の場合はＡ側（ＡＱ０〜ＡＱ３１）を出力し、選択信号（ＳＥＬ）が例えば“１”の場合はＢ側（ＢＱ０〜ＢＱ３１）を出力する。
【００３２】
ＡＮＤ回路６８（６８−０〜６８−３１）は、シフトレジスタ６４の値（Ｑ０〜Ｑ３１）と、マルチプレクサ６７から出力されるマスクＡレジスタ６５の値（ＡＱ０〜ＡＱ３１）またはマスクＢレジスタ６６の値（ＢＱ０〜ＢＱ３１）との、ビット毎の論理和を行う回路である。つまり、ＡＮＤ回路６８からは、シフトレジスタ６４の値（Ｑ０〜Ｑ３１）のうち、タップ位置に対応するビットについては、そのビットに記憶されている値が出力され、それ以外のビットについては“０”が出力される。
【００３３】
奇数パリティジェネレータ６９は、ＡＮＤ回路６８から出力される値の排他的論理和を行う回路である。つまり、マルチプレクサ６７から、マスクＡレジスタ６５の値（ＡＱ０〜ＡＱ３１）が出力される場合、次式（３）に示すように、奇数パリティジェネレータ６９から出力される値は、マスクＡレジスタ６５に設定したタップ位置に基づいたＭ系列を生成する場合における、シフトレジスタ６４への帰還信号（Ｆ）となる。
【数３】
2006215825.tif 000005
【００３４】
同様に、マルチプレクサ６７から、マスクＢレジスタ６６の値（ＢＱ０〜ＢＱ３１）が出力される場合、次式（４）に示すように、奇数パリティジェネレータ６９から出力される値は、マスクＢレジスタ６６に設定したタップ位置に基づいたＭ系列を生成する場合における、シフトレジスタ６４への帰還信号（Ｆ）となる。
【数４】
2006215825.tif 000006
【００３５】
また、本実施形態においては、奇数パリティジェネレータ６９から出力される帰還信号（Ｆ）を、Ｍ系列の擬似乱数（ＰＳＲ：pseudo random numbers）として用いることとする。
【００３６】
物理乱数生成回路７０は、物理乱数（ＰＨＲ：physical random numbers）を生成する回路である。図５に物理乱数生成回路７０の構成を示す。物理乱数生成回路７０は、物理乱数発生源８１、増幅回路８２、及び二値化回路８３を備える。物理乱数発生源８１は、自然現象に基づいてランダムに変化する信号を生じうるものであり、例えば、特開２０００−６６５９２号公報に開示されるような、接合を含む電流路に生じる雑音信号を生じる半導体素子を含むものとすることができる。なお、これに限られず、放射性物質の崩壊を利用したもの等もこの物理乱数発生源８１として用いることができる。
【００３７】
物理乱数発生源８１にて生成された信号は、増幅回路８２において増幅され、さらに二値化回路８３において二値化処理される。二値化回路８３は、増幅回路より出力される増幅された信号の振幅と所定の閾値とを比較し、例えば、増幅された信号の振幅が所定の閾値より高いときには“１”を、低いときには“０”を物理乱数（ＰＨＲ：physical random numbers）として出力する。なお、二値化回路８３における閾値のレベルは、“１”および“０”の発生確率が概ね４５〜５５％となるように設定されている。
【００３８】
ＯＲ回路７１は、物理乱数生成回路７０から出力される物理乱数（ＰＨＲ）と、乱数生成回路５４Ａにおいて物理乱数を用いるかどうかを示す選択信号（ＭＯＤＥ１）との論理和を行う回路である。本実施形態において、選択信号（ＭＯＤＥ１）が“０”のときをカウンタモード、“１”のときをＣＰＵモードと称することとする。カウンタモードの場合、ＯＲ回路７１から出力される信号は、物理乱数生成回路７０から出力される物理乱数（ＰＨＲ）となり、他の回路において物理乱数（ＰＨＲ）が用いられることとなる。一方、ＣＰＵモードの場合、ＯＲ回路７１から出力される信号は常に“１”となるため、他の回路において物理乱数（ＰＨＲ）が用いられないこととなる。
【００３９】
Ｄ−ＦＦ７２のデータ入力端子（Ｄ）には、ＯＲ回路７１から出力される信号が入力される。つまり、カウンタモードの場合、Ｄ−ＦＦ７２のデータ入力端子（Ｄ）には物理乱数（ＰＨＲ）が入力されることとなる。また、Ｄ−ＦＦ７２のクロック入力端子（Ｃ）には、動作クロック（ＲＣＬＫ）が入力される。そして、Ｄ−ＦＦ７２のデータ入力端子（Ｄ）に入力されている物理乱数（ＰＨＲ）が、動作クロック（ＲＣＬＫ）の立ち上がり時に、データ出力端子（Ｑ）から物理乱数（ＰＨＲＱ）として出力される。
【００４０】
ＡＮＤ回路７３は、Ｄ−ＦＦ７２から出力される物理乱数（ＰＨＲＱ）と、乱数生成回路５４Ａにおける動作モードを選択する選択信号（ＭＯＤＥ０）との論理積を行い、マルチプレクサ６７への選択信号（ＳＥＬ）を出力する回路である。本実施形態において、選択信号（ＭＯＤＥ０）が“０”のときを乗算モード、“１”のときをホッピングモードと称することとする。乗算モードとは、物理乱数をＭ系列の擬似乱数に応じて変化させて出力するモードであり、ホッピングモードとは、物理乱数に基づいてＭ系列を切り替えて出力するモードである。
【００４１】
乗算モードの場合、ＡＮＤ回路７３から出力される選択信号（ＳＥＬ）は常に“０”となる。つまり、乗算モードの場合、マルチプレクサ６７はマスクＡレジスタ６５の値（ＡＱ０〜ＡＱ３１）を出力する。ホッピングモードの場合、ＡＮＤ回路７３から出力される選択信号（ＳＥＬ）は、Ｄ−ＦＦ７２から出力される物理乱数（ＰＨＲＱ）となる。つまり、ホッピングモードの場合、マルチプレクサ６７は物理乱数（ＰＨＲＱ）に応じてマスクＡレジスタ６５の値（ＡＱ０〜ＡＱ３１）またはマスクＢレジスタ６６の値（ＢＱ０〜ＢＱ３１）を出力する。
【００４２】
ＯＲ回路７４は、Ｄ−ＦＦ７２から出力される物理乱数（ＰＨＲＱ）と、動作モードの選択信号（ＭＯＤＥ０）との論理和を行う回路である。つまり、乗算モードの場合、ＯＲ回路７４から出力される信号は物理乱数（ＰＨＲＱ）となり、ホッピングモードの場合、物理乱数（ＰＨＲＱ）にかかわらず常に“１”となる。
【００４３】
ＥＸＯＲ回路７５は、奇数パリティジェネレータ６９から出力される擬似乱数（ＰＳＲ）と、ＯＲ回路７４から出力される信号との排他的論理和を行い、乱数（Ｒ）を出力する回路である。
【００４４】
マルチプレクサ７６には、動作クロック（ＲＣＬＫ）を反転したクロック（／ＲＣＬＫ）と、ＣＰＵ５１Ａからの読み出し信号（ＣＰＵ＿ＲＤ）とが入力される。そして、マルチプレクサ７６は、選択信号（ＭＯＤＥ１）がカウンタモードの場合はクロック（／ＲＣＬＫ）を出力し、ＣＰＵモードの場合は読み出し信号（ＣＰＵ＿ＲＤ）を出力する。
【００４５】
シフトレジスタ７７は、例えば８ビットの線形シフトレジスタであり、データ入力端子（Ｄ）にＥＸＯＲ回路７５から出力される乱数（Ｒ）が入力され、クロック入力端子（Ｃ）にマルチプレクサ７６から出力されるクロック信号（／ＲＣＬＫ）または読み出し信号（ＣＰＵ＿ＲＤ）が入力される。
【００４６】
＝＝乱数生成回路の動作説明＝＝
次に、乱数生成回路５４Ａの動作について説明する。
【００４７】
（１）乗算モード
まず、カウンタモードで、動作モードが乗算モードの場合の動作を説明する。乗算モードの場合、ＡＮＤ回路７３から出力される選択信号（ＳＥＬ）は常に“０”となり、マスクＡレジスタ６５の値（ＡＱ０〜ＡＱ３１）がマルチプレクサ６７から出力される。そして、シフトレジスタ６４の値（Ｑ０〜Ｑ３１）と、マスクＡレジスタ６５の値（ＡＱ０〜ＡＱ３１）との論理積を行った結果がＡＮＤ回路６８から出力され、奇数パリティジェネレータ６９によってその排他的論理和が行われ、シフトレジスタ６４への帰還信号（Ｆ）が生成される。また、奇数パリティジェネレータ６９から出力される信号は、擬似乱数（ＰＳＲ）としてＥＸＯＲ回路７５に入力される。この擬似乱数（ＰＳＲ）は、マスクＡレジスタ６５に設定されたタップ位置に応じたＭ系列の擬似乱数となる。
【００４８】
ＥＸＯＲ回路７５は、擬似乱数（ＰＳＲ）と、ＯＲ回路７４から出力される物理乱数（ＰＨＲＱ）との排他的論理和を行い、乱数（Ｒ）をシフトレジスタ７７に出力する。そして、シフトレジスタ７７のクロック入力端子（Ｃ）には、マルチプレクサ７６を介してクロック（／ＲＣＬＫ）が入力される。
【００４９】
図６は、各信号の出力タイミングを示すタイミングチャートである。図に示すように、動作クロック（ＲＣＬＫ）の立ち上がり時（例えば時刻ｔ１）に、物理乱数（ＰＨＲＱ）、擬似乱数（ＰＳＲ）が生成され、さらにそれらの排他的論理和である乱数（Ｒ）が生成される。そして、動作クロック（ＲＣＬＫ）の立ち下がり時、つまり、クロック（／ＲＣＬＫ）の立ち上がり時（例えば時刻ｔ２）に、乱数（Ｒ）がシフトレジスタ７７にセットされる。
【００５０】
なお、シフトレジスタ７７は、ＥＸＯＲ回路７５から出力される乱数（Ｒ）を８ビット記憶すると、ＣＰＵ５１Ａに割込信号を送信する。ＣＰＵ５１Ａは、この割込信号を受信すると、８ビットの乱数（Ｒ）をシフトレジスタ７７から読み出す。
【００５１】
図７は、ＥＸＯＲ回路７５に入力される物理乱数（ＰＨＲＱ）及び擬似乱数（ＰＳＲ）の組合せと、その発生確率を示す図である。物理乱数（ＰＨＲＱ）が“０”となる確率をＸ（０≦Ｘ≦１）、擬似乱数（ＰＳＲ）が“０”となる確率をＹ（０≦Ｙ≦１）とすると、物理乱数（ＰＨＲＱ）及び擬似乱数（ＰＳＲ）が共に“０”となる確率はＸＹ、物理乱数（ＰＨＲＱ）が“０”、擬似乱数（ＰＳＲ）が“１”となる確率はＸ（１−Ｙ）となる。また、物理乱数（ＰＨＲＱ）が“１”、擬似乱数が“０”となる確率は（１−Ｘ）Ｙ、物理乱数（ＰＨＲＱ）及び擬似乱数（ＰＳＲ）が共に“１”となる確率は（１−Ｘ）（１−Ｙ）となる。
【００５２】
したがって、乱数（Ｒ）が“０”となる確率Ｐ０、および“１”となる確率Ｐ１は、次式（５），（６）により求められる。
【数５】
2006215825.tif 000007
【００５３】
ここで、例えば、擬似乱数（ＰＳＲ）を１６ビットのＭ系列とすると、擬似乱数（ＰＳＲ）においては、“０”が３２７６７回、“１”が３２７６８回発生することとなり、Ｙ≒０．４９９９（４９．９９％）となる。そして、物理乱数（ＰＨＲＱ）における“０”の発生確率Ｘを、例えば、０．４５（４５％）とすると、Ｐ０及びＰ１は、式（５），（６）より、Ｐ０≒０．５０００１（５０．００１％）、Ｐ１≒０．４９９９９（４９．９９９％）となる。また、例えば、物理乱数（ＰＨＲＱ）における“０”の発生確率Ｘを、例えば、０．５５（５５％）とすると、Ｐ０≒０．４９９９９（４９．９９９％）、Ｐ１≒０．５０００１（５０．００１％）となる。したがって、乱数（Ｒ）における“０”の発生確率の範囲は４９．９９９〜５０．００１％程度となり、乱数として用いることができる。
【００５４】
（２）ホッピングモード
次に、カウンタモードで、動作モードがホッピングモードの動作を説明する。ホッピングモードの場合、ＡＮＤ回路７３から出力される選択信号（ＳＥＬ）は、Ｄ−ＦＦ７２から出力される物理乱数（ＰＨＲＱ）となる。したがって、マルチプレクサ６７は、物理乱数（ＰＨＲＱ）が“０”の場合はマスクＡレジスタ６５の値（ＡＱ０〜ＡＱ３１）を出力し、“１”の場合はマスクＢレジスタ６６の値（ＢＱ０〜ＢＱ３１）を出力する。
【００５５】
物理乱数（ＰＨＲＱ）が“０”の場合、シフトレジスタ６４の値（Ｑ０〜Ｑ３１）と、マスクＡレジスタ６５の値（ＡＱ０〜ＡＱ３１）との論理積を行った結果がＡＮＤ回路６８から出力され、奇数パリティジェネレータ６９によってその排他的論理和が行われ、シフトレジスタ６４への帰還信号（Ｆ）が生成される。また、奇数パリティジェネレータ６９から出力される信号は、擬似乱数（ＰＳＲ）としてＥＸＯＲ回路７５に入力される。
【００５６】
そして、物理乱数（ＰＨＲＱ）が“１”の場合、シフトレジスタ６４の値（Ｑ０〜Ｑ３１）と、マスクＢレジスタ６６の値（ＢＱ０〜ＢＱ３１）との論理積を行った結果がＡＮＤ回路６８から出力され、奇数パリティジェネレータ６９によってその排他的論理和が行われ、シフトレジスタ６４への帰還信号（Ｆ）が生成される。また、奇数パリティジェネレータ６９から出力される信号は、擬似乱数（ＰＳＲ）としてＥＸＯＲ回路７５に入力される。
【００５７】
つまり、擬似乱数（ＰＳＲ）は、物理乱数（ＰＨＲＱ）が“０”の場合は、マスクＡレジスタ６５に設定されたタップ位置に応じたＭ系列の擬似乱数となり、物理乱数（ＰＨＲＱ）が“１”の場合は、マスクＢレジスタ６５に設定されたタップ位置に応じたＭ系列の擬似乱数となる。
【００５８】
ホッピングモードの場合、ＯＲ回路７４の出力は常に“１”となるため、ＥＸＯＲ回路７５から出力される乱数（Ｒ）は、擬似乱数（ＰＳＲ）を反転したものとなる。シフトレジスタ７７のデータ入力端子（Ｄ）には乱数（Ｒ）が入力され、クロック入力端子（Ｃ）には、マルチプレクサ７６を介してクロック（／ＲＣＬＫ）が入力される。そして、乗算モードの場合と同様に、クロック（／ＲＣＬＫ）の立ち上がり時に、乱数（Ｒ）がシフトレジスタ７７にセットされる。また、シフトレジスタ７７は、ＥＸＯＲ回路７５から出力される乱数（Ｒ）を８ビット記憶すると、ＣＰＵ５１Ａに割込信号を送信する。ＣＰＵ５１Ａは、この割込信号を受信すると、８ビットの乱数（Ｒ）をシフトレジスタ７７から読み出す。
【００５９】
（３）ＣＰＵモード
最後に、ＣＰＵモードの動作を説明する。ＣＰＵモードの場合、Ｄ−ＦＦ７２から出力される信号（ＰＨＲＱ）が常に“１”となる。したがって、ＡＮＤ回路７３から出力される選択信号（ＳＥＬ）は、乗算モードの場合は“０”、ホッピングモードの場合は“１”となる。つまり、マルチプレクサ６７は、乗算モードの場合はマスクＡレジスタ６５の値（ＡＱ０〜ＡＱ３１）を出力し、ホッピングモードの場合はマスクＢレジスタ６６の値（ＢＱ０〜ＢＱ３１）を出力する。
【００６０】
そして、シフトレジスタ６４の値（Ｑ０〜Ｑ３１）と、マスクＡレジスタ６５の値（ＡＱ０〜ＡＱ３１）またはマスクＢレジスタ６６の値（ＢＱ０〜ＢＱ３１）との論理積を行った結果がＡＮＤ回路６８から出力され、奇数パリティジェネレータ６９によってその排他的論理和が行われ、シフトレジスタ６４への帰還信号（Ｆ）が生成される。また、奇数パリティジェネレータ６９から出力される信号は、擬似乱数（ＰＳＲ）としてＥＸＯＲ回路７５に入力される。この擬似乱数（ＰＳＲ）は、マスクＡレジスタ６５またはマスクＢレジスタ６６に設定されたタップ位置に応じたＭ系列の擬似乱数となる。
【００６１】
ＣＰＵモードの場合、ＯＲ回路７４の出力は常に“１”となるため、ＥＸＯＲ回路７５から出力される乱数（Ｒ）は、擬似乱数（ＰＳＲ）を反転したものとなる。シフトレジスタ７７のデータ入力端子（Ｄ）には乱数（Ｒ）が入力され、クロック入力端子（Ｃ）には、マルチプレクサ７６を介してＣＰＵ５１Ａからの読み出し信号（ＣＰＵ＿ＲＤ）が入力される。そして、シフトレジスタ７７においては、読み出し信号（ＣＰＵ＿ＲＤ）が入力されるたびに、乱数（Ｒ）がセットされる。また、シフトレジスタ７７は、ＥＸＯＲ回路７５から出力される乱数（Ｒ）を８ビット記憶すると、ＣＰＵ５１Ａに割込信号を送信する。ＣＰＵ５１Ａは、この割込信号を受信すると、８ビットの乱数（Ｒ）をシフトレジスタ７７から読み出す。
【００６２】
以上、本発明の一実施形態である乱数生成回路５４Ａ，５４Ｂを適用したキーレスエントリーシステム１について説明した。前述したように、乱数生成回路５４Ａにおいては、乗算モードの場合、マスクＡレジスタ６５にＭ系列におけるタップ位置が記憶されており、線形帰還シフトレジスタ６４に記憶されているデータ（Ｑ０〜Ｑ３１）と、マスクＡレジスタ６５に記憶されているデータ（ＡＱ０〜ＡＱ３１）とに基づいて、線形帰還シフトレジスタ６４への帰還信号（Ｆ）が生成される。つまり、マスクＡレジスタ６５に所望のデータを設定することにより、Ｍ系列におけるタップ位置を自由に変更することが可能となる。このような乱数生成回路５４Ａにおいては、タップ位置が可変であるため、線形帰還シフトレジスタ６４により生成される擬似乱数の予測困難性が高まる。そして、複数のＭ系列を生成可能な乱数生成回路において、夫々のＭ系列のタップ位置に応じた回路を設ける必要がないため、回路規模を縮小することができる。
【００６３】
さらに、このように生成される擬似乱数を用いて物理乱数を変調して乱数（Ｒ）を生成することができる。つまり、物理乱数をＭ系列の擬似乱数を用いて変調することにより乱数の予測困難性を高める場合においても、Ｍ系列のタップ位置を自由に変更することが可能である。そのため、乱数の予測困難性を高めることができるとともに、複数のＭ系列のタップ位置を予め回路で構成する場合と比較して、回路規模を縮小することができる。
【００６４】
また、乱数生成回路５４Ａにおいては、Ｍ系列のタップ位置を記憶する２つのレジスタであるマスクＡレジスタ６５及びマスクＢレジスタ６６が設けられている。そして、線形帰還シフトレジスタ６４に記憶されているデータ（Ｑ０〜Ｑ３１）と、マルチプレクサ６７により選択された一方のレジスタに記憶されているデータ（ＡＱ０〜ＡＱ３１またはＢＱ０〜ＢＱ３１）とに基づいて、線形帰還シフトレジスタ６４への帰還信号（Ｆ）が生成される。つまり、マスクＡレジスタ６５及びマスクＢレジスタ６６に所望のデータを設定することにより、選択信号（ＳＥＬ）により切り替えることが可能な２つのＭ系列のタップ位置を自由に変更することが可能となる。このような乱数生成回路５４Ａにおいては、Ｍ系列が選択信号（ＳＥＬ）に基づいて切り替えられることに加えて、タップ位置がマスクＡレジスタ６５及びマスクＢレジスタ６６の設定により自由に変更されるため、線形帰還シフトレジスタ６４により生成される擬似乱数の予測困難性が高まる。そして、夫々のＭ系列のタップ位置に応じた回路を設ける必要がないため、回路規模を縮小することができる。
【００６５】
さらに、マルチプレクサ６７に入力される選択信号（ＳＥＬ）を物理乱数（ＰＨＲＱ）とすることができる。つまり、Ｍ系列を物理乱数に応じて切り替えることにより乱数の予測困難性を高める場合においても、Ｍ系列のタップ位置を自由に変更することが可能である。そのため、乱数の予測困難性を高めることができるとともに、複数のＭ系列のタップ位置を予め回路で構成する場合と比較して、回路規模を縮小することができる。
【００６６】
以上、本発明の実施形態について説明したが、上記実施形態は本発明の理解を容易にするためのものであり、本発明を限定して解釈するためのものではない。本発明は、その趣旨を逸脱することなく、変更、改良され得ると共に、本発明にはその等価物も含まれる。
【００６７】
例えば、本実施形態の乱数生成回路５４Ａにおいては、Ｍ系列のタップ位置を記憶するレジスタをマスクＡレジスタ６５及びマスクＢレジスタ６６の２つとしたが、タップ位置を記憶するレジスタを３つ以上設けることとしてもよい。タップ位置を記憶するレジスタを３つ以上設ける場合、例えば、フリップフロップ等を用いて物理乱数を２ビット以上記憶し、その値に応じてタップ位置を出力するレジスタを選択することとしてもよい。
【００６８】
また、本実施形態においては、擬似乱数系列としてＭ系列を用いているが、例えば、Ｇｏｌｄ系列等の他の擬似乱数系列を用いることとしてもよい。擬似乱数系列としてＧｏｌｄ系列を用いる場合においても、そのタップ位置をレジスタに記憶する構成とすることにより、タップ位置を自由に変更することが可能となり、また、複数のタップ位置に応じた回路を予め構成する場合と比較して、回路規模を縮小することができる。
【００６９】
また、本実施形態においては、乱数生成回路５４Ａをキーレスエントリーシステム１における暗号化に用いることとしたが、乱数生成回路５４Ａは、キーレスエントリーシステム１に限らず、安全性を高めるために乱数を使用する様々な情報処理システムに適用することができる。このように、様々な情報処理システムにおいて、乱数生成回路５４Ａを適用することにより、擬似乱数系列のタップ位置を自由に変更することが可能であるため、乱数の予測困難性を向上させ、安全性を高めることができる。また、複数の擬似乱数系列のタップ位置に応じた回路を予め構成する必要がないため、乱数生成回路の回路規模が縮小され、乱数生成回路を用いる装置を小型化することが可能となる。
【図面の簡単な説明】
【００７０】
【図１】本発明の乱数生成回路を用いる一実施形態である自動車の錠の施錠・解錠を行うキーレスエントリーシステムの全体構成を示す図である。
【図２】データ処理回路の構成を示す図である。
【図３】キーレスエントリーシステムの子機と親機との間における通信手順を示すフローチャートである。
【図４】乱数生成回路の構成を示す図である。
【図５】物理乱数生成回路７０の構成を示す図である。
【図６】乱数生成回路におけるタイミングチャートである。
【図７】物理乱数及び擬似乱数の発生確率を示す図である。
【符号の説明】
【００７１】
１  キーレスエントリーシステム          ２  子機
３  親機                                １１  電池
１２  操作スイッチ                      １３，２１  データ処理回路
１４，２２  送受信回路                  ２３  駆動回路
２４  アクチュエータ                    ２５  バッテリ
５１Ａ，５１Ｂ  ＣＰＵ                  ５２Ａ，５２Ｂ  ＲＡＭ
５３Ａ，５３Ｂ  ＥＥＰＲＯＭ            ５４Ａ，５４Ｂ  乱数生成回路
５５Ａ，５５Ｂ  暗号処理回路            ５６Ａ，５６Ｂ  入出力ポート
６１  分周回路                          ６２  ボーレートジェネレータ
６３  カウンタ                          ６４  シフトレジスタ
６５  マスクＡレジスタ                  ６６  マスクＢレジスタ
６７  マルチプレクサ                    ６８  ＡＮＤ回路
６９  奇数パリティジェネレータ          ７０  物理乱数生成回路
７１  ＯＲ回路                          ７２  Ｄ型フリップフロップ
７３  ＡＮＤ回路                        ７４  ＯＲ回路
７５  ＥＸＯＲ回路                      ７６  マルチプレクサ
７７  シフトレジスタ
【図１】
2006215825.tif 000008
【図２】
2006215825.tif 000009
【図３】
2006215825.tif 000010
【図４】
2006215825.tif 000011
【図５】
2006215825.tif 000012
【図６】
2006215825.tif 000013
【図７】
2006215825.tif 000014