(57)【要約】【課題】複数の疑似乱数生成器１を統一的に評価し、より安全で効率的な疑似乱数生成器１を選択可能とするための効率的な疑似乱数生成器強度評価装置２を提供する。【解決手段】推定可能な周期長の第１疑似乱数に基づき第２疑似乱数を生成する疑似乱数生成器１について、算出手順を表すブール代数式の構造を変えることなく、演算子をＡＮＤ演算子から積演算子へ、ＥＸ−ＯＲ演算子から和演算子へと対応付けて変換し、定数項を取り除くことで得られる評価式の変数へ底を２として周期長に１を足した値の対数値を代入し、評価値である実数を算出するようにした。【選択図】図３
2006285830.tif 000002
【特許請求の範囲】
【請求項１】
所定の周期長を有すると推定される第１疑似乱数を算出する第１回路と、前記第１疑似乱数を変数とする予め定められたブール代数式で表される算出手順を適用し、第２疑似乱数を算出する第２回路とを備えた疑似乱数生成器の強度評価を行うものであって、
前記ブール代数式の構造を変えることなく、演算子をＡＮＤ演算子から積演算子へ、ＥＸ−ＯＲ演算子から和演算子へと対応付けて変換し、定数項を取り除くことで得られる評価式の前記変数へ底を２として前記周期長に１を足した値の対数値を代入し、評価値である実数を算出する疑似乱数生成器強度評価装置。
【請求項２】
第１疑似乱数を算出する所定数のシフトレジスタを有したＬＦＳＲである第１回路と、前記第１疑似乱数を変数とする予め定められたブール代数式で表される算出手順を適用し、第２疑似乱数を算出する第２回路とを備えた疑似乱数生成器の強度評価を行うものであって、
前記ブール代数式の構造を変えることなく、演算子をＡＮＤ演算子から積演算子へ、ＥＸ−ＯＲ演算子から和演算子へと対応付けて変換し、定数項を取り除くことで得られる評価式の前記変数へ前記所定数を代入し、評価値である実数を算出する疑似乱数生成器強度評価装置。
【請求項３】
前記ブール代数式が、前記算出手順の一部を簡略化して表したものであることを特徴とする請求項１又は２記載の疑似乱数生成器強度評価装置。
【請求項４】
暗号化の強度要求値を示す強度要求値データを受け付ける強度要求値データ受付部と、
第１疑似乱数を算出する第１算出部と、前記第１疑似乱数を変数とするブール代数式で表される算出手順を適用し、第２疑似乱数を算出する第２算出部とを備えた疑似乱数生成部と、
前記第１算出部について請求項１又は２記載の疑似乱数生成器強度評価装置が算出した評価値等、疑似乱数生成器の強度を表す第１強度値を示す第１強度値データを予め格納している第１強度値データ格納部と、
前記第１強度値と積演算子と和演算子とを含み、前記強度要求値以上の値を示す第２強度値を算出する評価式を作成した後、前記評価式に含まれる前記第１強度値を対応する前記変数へ変換し、演算子を、積演算子からＡＮＤ演算子へ、和演算子からＥＸ−ＯＲ演算子へと対応付けて変換することで前記ブール代数式とし、前記ブール代数式で表される前記算出手順を前記第２算出部へ設定する算出手順設定部と、
前記第２疑似乱数を用いて暗号化を行う暗号化部とを備えた暗号化装置。
【請求項５】
前記疑似乱数生成部が備える前記第１算出部が、初期値であるシードより定まり所定のビット数で表現可能な値に基づき、第１疑似乱数を算出するものであり、
前記暗号化部が、前記疑似乱数生成部に前記シードを設定し、前記第２疑似乱数を用いて暗号化を行うものであって、
暗号化を行ったデータのビット量が２の前記第２強度値乗から１を引いた値で示される推定周期を超える前に、前記暗号化部が前記シードを変更するようにしたものであることを特徴とする請求項４記載の暗号化装置。
【請求項６】
前記第１強度値データ格納部に換えて、予め算出した前記第２強度値を示す第２強度値データと、前記算出手順を示す算出手順データとを対応させて格納している第２強度値手順対応データ格納部を備え、
前記算出手順設定部が、前記強度要求値以上の値を示す第２強度値データと対応している前記算出手順を前記第２算出部へ設定するようにした請求項４又は５記載の暗号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、疑似乱数生成器の評価を行う疑似乱数生成器強度評価装置と、その評価結果を利用する暗号化装置に関する。
【背景技術】
【０００２】
暗号通信や認証等において、他者に対して通信内容を隠蔽し模倣を禁止するために送信者と受信者との間で乱数を用いた情報の変換が行われる。しかし、予測不可能に値が変化する真性乱数を表すデータは多量となり、これを送信者と受信者とが共用することは現実的ではない。このため、より少量のデータであるシードから一定の規則に基づいて生成され周期性を有する乱数である疑似乱数が用いられる。
【０００３】
そこで、特許文献１にあるように、この疑似乱数が暗号学的に安全であることを確認するため、疑似乱数の周期長や統計的性質、予測を困難とする非線形性、統計的性質を利用した解読法である相関解読法に対し解読を困難とする無相関性等が評価される。
【特許文献１】特開２００３−５６４２公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、複数の疑似乱数生成器を統一的に評価し、より安全で効率的な疑似乱数生成器を選択するためにはこれら従来の評価方法は十分ではない。
【０００５】
即ち、統計的特性及び無相関性については、今日の疑似乱数生成器は既に十分に優れた評価を得られるよう対策されており、非線形性や周期長については、評価方法が曖昧である、ある種の型式の疑似乱数生成器に対して適用不可能又は現実的な評価を示せない等の不都合がある。
【０００６】
そこで本願発明者は、疑似乱数生成器一般に統一的に適用可能なだけでなく、未だ十分な対策が行われていない線形解読法に対する解読の困難性を示す、疑似乱数生成器の強度を評価する方法を提案する。即ち、疑似乱数生成器に線形解読法を適用した際に解読に要する独立な方程式の数を疑似乱数生成器の強度を表す強度値と定め、強度値を以て評価を行えばよい。
【０００７】
このような疑似乱数生成器の強度（以下単に強度とする）を示す強度値を得るには、疑似乱数生成器の入出力を表すブール代数式に着眼し、本ブール代数式の２次以上の変数項を新たな一変数とすることで線形なブール代数式へ変形し、その際に現れる独立未知項の総数を算出すればよい。しかし、これは複雑な手順である。
【０００８】
また、強度値によれば、２強度値−１≦周期長≦２線形複雑度−１といった関係が成り立つといった特性があることが本願発明者の研究により判明しており、強度値に基づく周期長の推定等が可能となることから、その応用が考えられる。
【０００９】
そこで本発明は、上記事情を踏まえ単純な手順でより効率的に様々の疑似乱数生成器の強度値を求める疑似乱数生成器強度評価装置を提供するだけでなく、強度値の特性を利用しより安全で効率的に暗号化を行う暗号化装置を提供することをその主たる所期課題としたものである。
【課題を解決するための手段】
【００１０】
すなわち本発明に係る疑似乱数生成器強度評価装置は、所定の周期長を有すると推定される第１疑似乱数を算出する第１回路と、前記第１疑似乱数を変数とする予め定められたブール代数式で表される算出手順を適用し、第２疑似乱数を算出する第２回路とを備えた疑似乱数生成器の強度評価を行うものであって、前記ブール代数式の構造を変えることなく、演算子をＡＮＤ演算子から積演算子へ、ＥＸ−ＯＲ演算子から和演算子へと対応付けて変換し、定数項を取り除くことで得られる評価式の前記変数へ底を２として前記周期長に１を足した値の対数値を代入し、評価値である実数を算出するものである。
【００１１】
このよう疑似乱数生成器評価装置を用いて評価を行えば、その評価値として強度値を得ることができる。そして、入出力の関係が明らかでない部分的な回路を備えた疑似乱数生成器であっても、その回路から出力される疑似乱数の周期長が推定可能でさえあれば、疑似乱数生成器の評価を行える。また強度値が判明している回路であれば、周期長を例えば２強度値―１等と推定可能であることから、強度値を用いて段階的に疑似乱数生成器の強度値を算出することが可能となる。更に、ブール代数式の構造を変えることなく演算子を変換して得られる評価式を用い、その変数に値を代入することで評価値を算出しているので、入出力の関係を表すブール代数式を２次以上の変数項を新たな一変数とすることで線形なブール代数式へ変形し、独立未知項をカウントし、その総数を求めるよりも条件分岐や判断の少ない単純且つ効率的な処理となり、自動化にも好適である。
【００１２】
また、第１疑似乱数を算出する所定数のシフトレジスタを有したＬＦＳＲである第１回路と、前記第１疑似乱数を変数とする予め定められたブール代数式で表される算出手順を適用し、第２疑似乱数を算出する第２回路とを備えた疑似乱数生成器の強度評価を行うものであって、前記ブール代数式の構造を変えることなく、演算子をＡＮＤ演算子から積演算子へ、ＥＸ−ＯＲ演算子から和演算子へと対応付けて変換し、定数項を取り除くことで得られる評価式の前記変数へ前記所定数を代入し、評価値である実数を算出するものとすることで、ＬＦＳＲを含んだ疑似乱数生成器に対して単純且つ効率的に強度値を得られ、自動化にも好適である。
【００１３】
また、前記ブール代数式が、前記算出手順の一部を簡略化して表したものであることを特徴とするものであれば、複雑な回路を有する疑似乱数生成器に対する評価を容易とすることができる。
【００１４】
このようにして得られる強度値は、一般に疑似乱数生成器の処理効率とは相反する関係にある。そこで、暗号化の強度要求値を示す強度要求値データを受け付ける強度要求値データ受付部と、第１疑似乱数を算出する第１算出部と、前記第１疑似乱数を変数とするブール代数式で表される算出手順を適用し、第２疑似乱数を算出する第２算出部とを備えた疑似乱数生成部と、前記第１算出部について請求項１又は２記載の疑似乱数生成器強度評価装置が算出した評価値等、疑似乱数生成器の強度を表す第１強度値を示す第１強度値データを予め格納している第１強度値データ格納部と、前記第１強度値と積演算子と和演算子とを含み、前記強度要求値以上の値を示す第２強度値を算出する評価式を作成した後、前記評価式に含まれる前記第１強度値を対応する前記変数へ変換し、演算子を、積演算子からＡＮＤ演算子へ、和演算子からＥＸ−ＯＲ演算子へと対応付けて変換することで前記ブール代数式とし、前記ブール代数式で表される前記算出手順を前記第２算出部へ設定する算出手順設定部と、前記第２疑似乱数を用いて暗号化を行う暗号化部とを備えた暗号化装置とすることで、要求された強度を有する効率的な疑似乱数生成器を利用し、安全で効率的に暗号化を行うことができる。
【００１５】
更に、前記疑似乱数生成部が備える前記第１算出部が、初期値であるシードより定まり所定のビット数で表現可能な値に基づき、第１疑似乱数を算出するものであり、前記暗号化部が、前記疑似乱数生成部に前記シードを設定し、前記第２疑似乱数を用いて暗号化を行うものであって、暗号化を行ったデータのビット量が２の前記第２強度値乗から１を引いた値で示される推定周期を超える前に、前記暗号化部が前記シードを変更するようにしたものであることを特徴とするものであれば、より安全に通信を行うことができる。
【００１６】
また、前記第１強度値データ格納部に換えて、予め算出した前記第２強度値を示す第２強度値データと、前記算出手順を示す算出手順データとを対応させて格納している第２強度値手順対応データ格納部を備え、前記算出手順設定部が、前記強度要求値以上の値を示す第２強度値データと対応している前記算出手順を前記第２算出部へ設定するようにしたものであれば、算出手順の設定が高速に行えるようになり、動的に疑似乱数生成部を切り替えるに好ましい。
【発明の効果】
【００１７】
この様な疑似乱数生成器強度評価装置であれば、様々な疑似乱数生成器に対して有用且つ統一的な評価を行うことができる。また、入出力の関係が明らかでない部分的な回路を有したものであっても、その回路から出力される疑似乱数の周期長が推定可能か又はその回路の強度が判明してさえいれば評価可能なだけでなく、未だ十分な対策が行われていない線形解読法に対する疑似乱数生成器の強度を評価するものであり、従来の統計的な評価等と併せることで総合的に疑似乱数の安全性を表すことを可能としている。また、単純且つ効率的な処理で評価が行え、自動化にも好適である。
【００１８】
そして、このような強度を利用した暗号化装置であれば、疑似乱数生成器の強度を保証しながら効率的に暗号化を行うことができる。
【発明を実施するための最良の形態】
【００１９】
＜第１実施形態＞
【００２０】
本願発明に係る第１の実施形態について以下に説明する。
【００２１】
まず、本実施形態において評価対象とする疑似乱数生成器１について図１及び２を参照しながら説明する。
【００２２】
図１に示す疑似乱数生成器１は非線形コンバイナ型疑似乱数生成器であり、シードを示すシードデータを受け付けるシードデータ受付部１１と、シードに基づき、第１疑似乱数を算出する第１回路１２と、第１疑似乱数に予め定められたブール代数式で表される算出手順を適用し、第２疑似乱数を算出する第２回路１３とを備えている。ここでシードとは、疑似乱数生成器１が生成する疑似乱数の乱数系列を指定する値であり、第１回路１２に含まれる記憶部であるレジスタＲの初期値となるものである。
【００２３】
以下に各部を詳細に説明する。
【００２４】
シードデータ受付部１１とはシードデータを受け付け、シードデータに基づいて第１回路１２の所定のレジスタＲへ所定の値を設定するものである。
【００２５】
第１回路１２は、本実施形態では図２に示すように、それぞれＥＸ−ＯＲによる帰還のかかったｎ個のシフトレジスタＲを有するｎ段のＬＦＳＲ回路である。図示しないクロック信号を受け付け、演算処理を行いつつ、シフトレジスタＲの値を左から右へ時々刻々とシフトさせることで右端にある最終段のシフトレジスタＲより１ビットの第１疑似乱数データを出力する。なお、シフトレジスタＲの段数をｎとすると第１疑似乱数の周期は２ｎで表すことができる。また、最大周期を得られるよう各第１回路１２はＭ系列発生器とし、レジスタ数が互いに素となるようにしている。
【００２６】
第２回路１３は、レジスタＲを有さず、入力によってのみ出力が定まる非線形な回路である。各第１回路１２が出力した第１疑似乱数データを入力として第１疑似乱数に所定の演算処理を行うことで時々刻々と１ビットの第２疑似乱数データを出力するものである。なお、ｉ番目の第１回路１２が時刻ｔに出力する疑似乱数をｘｉ（ｔ）、時刻ｔにおける第１回路群１２（１）、１２（２）、１２（３）からの入力をＸ（ｔ）、第２疑似乱数の算出手順を表す関数をｆ（・）として、算出手順を表すブール代数式は式（１）の右辺として表せる。
【数１】
2006285830.tif 000003
【００２７】
ここで、ＮＯＴ演算はＥＸ−ＯＲ演算を用いて表し、式に含まれる演算子をＡＮＤ演算とＥＸ−ＯＲ演算とのみとして表すようにしている。
【００２８】
次に、本実施形態における疑似乱数生成器強度評価装置２について図３及び４を参照しながら説明する。
【００２９】
図３に疑似乱数生成器強度評価装置２の機能構成図を示す。疑似乱数生成器強度評価装置２は、第２疑似乱数の算出手順を表すブール代数式の演算順序等を定める構造を変えることなく、その演算子をＡＮＤ演算子から積演算子へ、ＥＸ−ＯＲ演算子から和演算子へと対応付けて変換し、定数項を取り除く。そして得られる評価式の各第１疑似乱数を表す変数へ所定の数を代入し、疑似乱数生成器１の強度（以下単に強度とする）を表す評価値を算出するものであり、第１回路構成データ受付部２１と、第２回路構成データ受付部２２と、評価部２３とを備えている。
【００３０】
ここで、強度について説明する。
【００３１】
強度とは、線形解読法による疑似乱数生成器１に設定された初期値等の解読の困難性を表すものである。線形化攻撃とは代数的攻撃法（文献「Ｎ．Ｃｏｕｒｔｏｉｓ  ＡＮＤ  Ｗ．Ｍｅｉｅｒ，Ａｌｇｅｂｒａｉｃ  Ａｔｔａｃｋｓ  ｏｎ  Ｓｔｒｅａｍ  Ｃｉｐｈｅｒｓ ｗｉｔｈ  Ｌｉｎｅａｒ  Ｆｅｅｄｂａｃｋ”，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＥＵＲＯＣＲＹＰＴ  ２００３，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｖｏｌ．  ２６５６，  ｐｐ.３４５−３５９，Ｓｐｒｉｎｇｅｒ  Ｖｅｒｌａｇ，  ２００３」）の一つであり、シードと疑似乱数との関係を表す方程式の非線形な２次以上の変数項を新たな一変数と再定義することにより２次以上の方程式を線形方程式へ変形し、方程式を解くことを容易にする解読方法である。この解読方法では、変数と同数個の独立な方程式を用意することが必要であり、変数が増加すると、攻撃に必要な既知平文組数の増加を招いたり、もしくは攻撃を不可能にする場合を生じさせたりすることとなる。そこで、この変数の総数を強度としている。
【００３２】
図４は、本実施形態における疑似乱数生成器強度評価装置２を示したハードウェア構成図である。この疑似乱数生成器強度評価装置２は、同図が示すように、例えば汎用コンピュータであり、図１に示すように、ＣＰＵ１０１、内部メモリ１０２、ＨＤＤ等の外部記憶装置１０３、通信ネットワークに接続するためのモデム等の通信インタフェース１０４、ディスプレイ１０５、マウスやキーボードといった入力手段１０６等を具備する。
【００３３】
しかして本実施形態では、図３に示すように、前記コンピュータに所定のプログラムをインストールし、そのプログラムに基づいてＣＰＵ１０１や周辺機器を共働させることにより、第１回路構成データ受付部２１、第２回路構成データ受付部２２、評価部２３等として機能するようにしている。
【００３４】
以下に疑似乱数生成器強度評価装置２の各部を説明する。
【００３５】
第１回路構成データ受付部２１は、疑似乱数生成器１の各第１回路１２に含まれるレジスタ数である正の整数を示す第１回路構成データを受け付けるメモリ１０２などである。
【００３６】
第２回路構成データ受付部２２は、算出式を示す第２回路構成データを受け付けるメモリ１０２などである。算出式は、第１疑似乱数を表す変数項と、定数項と、演算子とからなるブール代数式として表されるが、勿論そのデータ形式は例えば式（１）の右辺に表す数式の他、二分木形式や逆ポーランド形式等その他様々な形式で表すことができ、算出式へ変形可能なものであればどのような形式であっても構わない、またテキスト形式であってもバイナリ形式であっても当然構わない。
【００３７】
評価部２３は、ＣＰＵ１０１等の演算機能を利用し、レジスタ数と算出式とを用いて強度を表す評価値を算出し評価値を示す評価値データを出力するものである。まず算出式の演算子を、ＡＮＤ演算子から積演算子へＥＸ−ＯＲ演算子から和演算子へと対応付けて変換し定数項を取り除くことで算出式を評価式へ変換する。そして評価式の各変数へ各第１回路１２に関して対応するレジスタ数を代入し演算処理を行うことにより評価値である実数を算出するようにしている。
【００３８】
以下に図３を参照しながら、図５のフローチャートを用いて、本実施形態における疑似乱数生成器強度評価装置２の動作の一例を示す。
【００３９】
図３に示す第１回路構成データ受付部２１が、３つの各第１回路１２のレジスタ数を示す各第１回路構成データを受け付け格納する（ステップＳａ１）。以下、ｉ番目の第１回路１２のレジスタ数をｒｉ、全第１回路構成データをＲとすると、図２より各第１回路１２に対応する第１回路構成データの値は以下のようになる。
【数２】
2006285830.tif 000004
【００４０】
図３に示す第２回路構成データ受付部２２が、算出手順を表す以下の式（２）の算出式を示す第２回路構成データを受け付け格納する（ステップＳａ２）。
【数３】
2006285830.tif 000005
【００４１】
なお、式（２）は便宜のためＡＮＤ演算を∧として明示しているが、式（１）と同じものである。
【００４２】
評価部２３が、演算子をＡＮＤ演算子から積演算子へ、ＥＸ−ＯＲ演算子から和演算子へと対応付けて変換し、定数項を取り除くことで以下の式３に示す評価式を作成する（ステップＳａ３）。ここで評価手順を表す関数をＦ（・）としている、また本実施形態では定数項は予め含まれていない。なお評価式は式（３）の右辺であり、便宜上展開を行っているが行わなくても構わない。
【数４】
2006285830.tif 000006
【００４３】
評価部２３が、レジスタ数を評価式へ代入し（式４）、評価値を算出する（ステップＳａ４）。
【数５】
2006285830.tif 000007
【００４４】
評価値は２６となる。
【００４５】
このような疑似乱数生成器強度評価装置２であれば、
【００４６】
疑似乱数生成器一般に統一的に適用可能なだけでなく、未だ十分な対策が行われていない線形解読法に対する解読の困難性を表す強度を評価することができる。各算出式について複雑な条件判断を伴うことなく一律に評価値の算出を行えるものとし、自動化にも好適である。また単純な文字の置換操作により容易に変換が行える。
【００４７】
＜第２実施形態＞
【００４８】
本願発明に係る第２の実施形態について以下に説明する。なお、第１実施形態と対応する部分には同一の符号を付してある。
【００４９】
まず、本実施形態において評価対象とする疑似乱数生成器１について図６及び７を参照しながら説明する。
【００５０】
疑似乱数生成器１は、図６に示すように、シードを示すシードデータを受け付けるシードデータ受付部１１と、シードに基づき、第１疑似乱数を算出する第１回路１２と、第１疑似乱数に予め定められたブール代数式で表される算出手順を適用し、第２疑似乱数を算出する第２回路１３とを備えている。
【００５１】
図６に示す第１回路１２は、図７に示すように本実施形態では３種類あり、第１実施形態と同様のＬＦＳＲ回路１２（１）と、その強度が３であり入出力の関係が未知の疑似乱数生成回路１２（４）と、周期長が２５−１であり入出力の関係が未知の疑似乱数生成回路１２（５）とである。
【００５２】
図６に示す第２回路１３は第１の実施形態と同様である。
【００５３】
次に、本実施形態における疑似乱数生成器強度評価装置２について図３及び８を参照しながら説明する。
【００５４】
本実施形態に係る疑似乱数強度評価装置２の機能構成及びハードウェア構成は第１実施形態のものと同様である。
【００５５】
以下に各部を説明する。
【００５６】
第１回路構成データ受付部２１は、第１回路１２の構成に関するデータである第１回路構成データを受け付けるものであり、レジスタ数データ受付部２１１と、強度値データ受付部２１２と、周期長データ受付部２１３とを備えている。
【００５７】
レジスタ数データ受付部２１１は、第１回路１２に含まれるレジスタ数を示すレジスタ数データを受け付けるメモリ１０２等であり、第１実施形態における第１回路構成データ受付部２１と同様である。
【００５８】
強度値データ受付部２１２は、第１回路１２となる疑似乱数生成器１の強度を表す強度値を示す強度値データを受け付けるメモリ１０２等である。
【００５９】
周期長データ受付部２１３は、測定又は推定された疑似乱数の周期長を示す周期長データを受け付けるメモリ１０２等である。
【００６０】
第２回路構成データ受付部２２は、第１実施形態に同様である。
【００６１】
評価部２３は、第１回路構成データが示すレジスタ数と、強度値と、周期長とに基づいて第２回路構成データが示す算出手順を用い評価値を算出するものである。
【００６２】
ここで、レジスタ数と強度と周期長との関係について説明する。
【００６３】
ある強度値を有する疑似乱数生成器１が生成する疑似乱数は、レジスタ数が前記強度値の示す数と同数のＬＦＳＲ回路を用いて生成可能である。このため、所定の強度を持った疑似乱数生成器１を、同数のレジスタＲを持つＬＦＳＲ回路を備えるもの見なせばレジスタ数と強度とを同様に扱うことが可能である。また、本願発明者の研究により、２強度−１≦周期長≦２線形複雑度−１といった関係が成り立つことが判明している。このため、周期長が得られれば、強度の存在範囲の上限を推定することができ、とりわけＭ系列のＬＦＳＲについては２レジスタ数−１＝周期長の関係が成り立つことから、ｌｏｇ２（周期長＋１）と強度とを同様に扱うことができる。そこで、入出力の関係が不明な第１回路１２（４）、１２（５）についても、その強度又は周期長が判明する又は推定可能であれば、Ｍ系列のＬＦＳＲとみなし、前記第１回路１２（４）、１２（５）を含む疑似乱数生成器１の強度の評価を行うことが可能となる。
【００６４】
本評価部２３では、まず第１実施形態と同様にして算出式を評価式へ変換する。次に入出力の関係が不明な回路についても、レジスタ数と強度とｌｏｇ２（周期長＋１）とを同様に扱い、ＬＦＳＲ回路にはそのレジスタ数を、強度値が与えられている回路にはその強度値を、周期長が与えられている回路にはｌｏｇ２（周期長＋１）を対応付けて評価式の各変数へ代入し演算処理を行うことにより、第１実施形態と同様にして評価値である実数を算出する。
【００６５】
以下に図３、７及び８を参照しながら、図９のフローチャートを用いて、本実施形態における疑似乱数生成器強度評価装置２の動作の一例を示す。
【００６６】
図３に示す第１回路構成データ受付部２１が第１回路構成データを受け付ける。即ち、図８に示すレジスタ数データ受付部２１１は図７に示す１番目の第１回路１２（１）のレジスタ数を示すレジスタ数データを受け付け、強度値データ受付部２１２は２番目の第１回路１２（４）の強度値を示す強度値データを受け付け、周期長データ受付部２１３は３番目の第１回路１２（５）の周期長を示す周期長データを受け付ける（ステップＳｂ１）。以下、ｉ番目の第１回路１２のレジスタ数またはそれと同様の値をｒｉ、全第１回路構成データをＲ’とすると、図７より各第１回路１２に対応する第１回路構成データの値は以下のようになる。
【数６】
2006285830.tif 000008
【００６７】
図３に示す第２回路構成データ受付部２２が、算出手順を表す以下の式（５）の右辺に示す算出式を示す第２回路構成データを受け付ける（ステップＳｂ２）。なお、第１実施形態同様に第２回路構成データの格納形式は数式を直接表すものでなくても構わない。なお、ｘｉ（ｔ）及びｆ（・）の定義は第１実施形態と同様である。
【数７】
2006285830.tif 000009
【００６８】
評価部２３が、演算子をＡＮＤ演算子から積演算子へ、ＥＸ−ＯＲ演算子から和演算子へと対応付けて変換し、定数項を取り除くことで式（６）に示す評価式とする（ステップＳｂ３）。なお、Ｆ（・）の定義は第１実施形態と同様である。
【数８】
2006285830.tif 000010
【００６９】
評価部２３が、周期長より強度値を推定し第１回路構成データを変換する（ステップＳｂ４）。変換済みの全第１回路構成データを以下のようにＲで表す。
【数９】
2006285830.tif 000011
【００７０】
評価部２３が、代入し（式（７））、評価値を算出する（ステップＳｂ５）。
【数１０】
2006285830.tif 000012
【００７１】
このような疑似乱数生成器強度評価装置２であれば、入出力の関係が明らかでない部分的な回路を備えた疑似乱数生成器１であっても、その回路から出力される疑似乱数の周期長が推定可能でさえあれば、疑似乱数生成器１の評価を行える。また強度が判明している回路について、部分的な回路の既知の強度値に基づいて疑似乱数生成器全体の強度値を段階的に算出することが可能となる。更に、条件分岐や判断の少ない単純且つ効率的な処理であり、自動化にも好適である。
【００７２】
＜第３実施形態＞
【００７３】
本願発明に係る第３の実施形態について以下に説明する。
【００７４】
暗号化装置３の機能構成について説明する。
【００７５】
暗号化装置３は、図１０に示すように強度要求値データ受付部３１と、疑似乱数生成部３２と、第１強度値データ格納部３３と、算出手順設定部３４と、暗号化部３５とを備えたものである。
【００７６】
本実施形態に係る暗号化装置３のハードウェア構成は、図４に示すように、第１実施形態の疑似乱数生成器強度評価装置２と同様の汎用コンピュータである。本実施形態では、図１０に示すように、前記コンピュータに所定のプログラムをインストールし、そのプログラムに基づいてＣＰＵ１０１や周辺機器を共働させることにより、強度要求値データ受付部３１、疑似乱数生成部３２、第１強度値データ格納部３３、算出手順設定部３４、暗号化部３５等として機能するようにしている。
【００７７】
以下に暗号化装置３の各部を詳細に説明する。
【００７８】
強度要求値データ受付部３１は、暗号化の強度要求値を示す強度要求値データを受け付けるメモリ１０２等である。
【００７９】
疑似乱数生成部３２は、シードより定まり所定のビット数で表現可能な値に基づき第１疑似乱数を算出する第１算出部１２と、第１疑似乱数を変数とするブール代数式で表される算出手順を適用し、第２疑似乱数を算出する第２算出部１３とを備え、第２疑似乱数を生成するものである。本実施形態では、第１実施形態で説明した図１に示す疑似乱数生成器２の、３つのＬＦＳＲ回路１２と同様のＬＦＳＲ算出部を第１算出部１２として備えている。そして各第１算出部１２はシフトレジスタＲに対応するメモリ１０２を有している。また第２算出部１３はメモリ１０２の実行可能領域上に、その算出手順を再設定可能な状態で設けられている。
【００８０】
第１強度値データ格納部３３は、第１算出部１２について疑似乱数生成器強度評価装置２が予め算出した評価値等の強度値を示す第１強度値データ格納しているメモリ１０２等である。なおこの格納されている強度値データが示す強度値を第１強度値等として後述する算出手順設定部３４の評価式が算出する第２強度値と区別している。第１強度値を示す第１強度値データは第１算出部１２を示す名前やＩＤ等と対応付けられて格納されている。データ及びデータ構造を図１２に示す。
【００８１】
算出手順設定部３４は、第１強度値と積演算子と和演算子とを含み第２強度値を算出する評価式を、強度要求値以上の値である第２強度値を算出するように作成した後、第１強度値データに含まれる第１強度値と第１算出部１２との対応を辿り、前記評価式に含まれる第１強度値を対応する第１疑似乱数を表す変数へ変換し、演算子を、積演算子からＡＮＤ演算子へ、和演算子からＥＸ−ＯＲ演算子へと対応付けて変換することでブール代数式である算出式を作成し、算出式で表される算出手順を第２算出部１３へ設定するものである。
【００８２】
暗号化部３５は、疑似乱数生成部３２にシードを設定し、得られる第２疑似乱数を用いて、例えば平文と第２疑似乱数とのＥＸ−ＯＲを演算処理することで暗号文を算出し、暗号文データを出力するものである。
【００８３】
以下に図１０及び１２を参照しながら、図１１のフローチャートを用いて、本実施形態における暗号化装置３の動作の一例を示す。
【００８４】
図１０に示す強度要求値データ受付部３１が強度要求データを受け付けメモリ１０２内に格納する（ステップＳｃ１）。ここでは強度要求値を６とする。
【００８５】
算出手順設定部３４が、第１強度値データ格納部３３が格納している図１２に示す第１強度値データを参照し、強度要求値以上の値を示すように評価式を作成する（ステップＳｃ２）。評価式の作成は、式の構造と第１強度値との組み合わせを評価し、条件を満たすものを選ぶことで行う。式の構造とは、式より変数の区別を除いて得られるものであり、統計的に優れた性質が得られる式の構造を図示しない格納部へ予め格納しておき利用するようにしている。ここでは１番目及び２番目の第１算出部１２と対応する第１強度値を用い、以下の評価式（式（８））が得たものとする。
【数１１】
2006285830.tif 000013
【００８６】
評価式の値である第２強度値は６であり、要求強度値以上であることから条件を満たしている。
【００８７】
図１０に示す算出手順設定部３４が、強度値データを参照して前記評価式に含まれる前記第１強度値を対応する変数へ変換し、演算子を、積演算子からＡＮＤ演算子へ、和演算子からＥＸ−ＯＲ演算子へと対応付けて変換することで算出式（式（９））を得る（ステップＳｃ３）。ここで時刻ｔにおいてｉ番目の第１算出部１２が出力する第１疑似乱数をｘｉ（ｔ）として表している。
【数１２】
2006285830.tif 000014
【００８８】
算出式で表される算出手順を、第２算出部１３へ設定する（ステップＳｃ４）。ここでは、予め第２算出部１３がパラメータに基づいて第２疑似乱数の算出を行うように構成しておき、前記パラメータを算出式に基づいて設定することで算出手順を設定するようにしている。
【００８９】
暗号化部３５が、疑似乱数生成部３２へ図示しないシードを設定する（ステップＳｃ５）。このとき、疑似乱数生成器１の第１回路１２の各シフトレジスタＲに対応する第１算出部１２の各メモリ１０２へ、シードに基づいた値の設定を行う。
【００９０】
暗号化部３５が、平文を示す平文データと第２疑似乱数を示す第２疑似乱数データとのＥＸ−ＯＲを演算処理することで暗号化し、得られる暗号文データを出力する（ステップＳｃ６）。
【００９１】
このような暗号化装置３であれば、要求された強度を満たしつつ、効率的に暗号化を行うことができる。また、予め統計的条件を考慮して式の構造を格納しており、これを用いて算出手順を設定しているので統計的性質も優れたものとなる。
【００９２】
更に、例えば予め第１回路１２が算出する第１疑似乱数の統計的性質に関するデータを第１強度値データ格納部３３が格納しており、前記統計的性質に関するデータに基づいて評価式を作成するようにすれば、統計的により安全に暗号化を行うこともできる。
【００９３】
また、例えば暗号化を行ったデータのビット量が２の第２強度値乗で示される推定周期を超える前に、暗号化部３５が前記シードを変更するようにすれば、より安全である。このようにするには、暗号化部３５がメモリ１０２等であるカウンタを有し、ステップＳｃ５で暗号化を行ったデータのビット量をカウントしておき、推定周期を超える前にステップＳｃ４を実行するようにすればよい。
【００９４】
また、例えば第１強度値データ格納部３３に代えて、評価式の値である第２強度値データと、評価式に基づいて定まる算出手順を表す算出手順データとを対応させて格納している第２強度値手順対応データ格納部を備え、算出手順設定部３４が、強度要求値以上の値を示す強度値データと対応している算出手順を第２算出部１３へ設定するようにすれば、算出手順の設定を高速化できる。このようにした場合の第２強度値手順対応データの構造を図１３に示す。なお図中では算出手段に現れる第１強度値と対応する変数を第１算出部名で表している。
【００９５】
なお、本発明は上記実施形態に限られない。
【００９６】
例えば、第１及び第２実施形態における疑似乱数生成器も、疑似乱数生成器強度評価装置と同一のコンピュータ上で動作するプログラムであっても構わない。また、ＦＰＧＡ等の再構成可能なハードウェア上に構成されたものであっても構わない。
【００９７】
第２実施形態における入出力の関係が不明な第１回路について、例えば前記第１回路をＬＦＳＲ回路以外の回路と見なす場合、前記各第１回路のレジスタ数と同様の値はその回路の特性に応じて、例えば１以上２ｎ−１以下の値に、適切に定めるようにして構わない。
【００９８】
前記各構成の一部又は全部を適宣組み合わせてもよい。例えば、第３実施形態における疑似乱数生成部が第２実施形態における疑似乱数生成器と同様のもの等であっても構わないし、暗号化装置が疑似乱数生成器強度評価装置を備え、第１算出部を動的に評価するなどとしても構わない。
【００９９】
その他本発明の趣旨を逸脱しない範囲で様々な変形が可能である。
【図面の簡単な説明】
【０１００】
【図１】本発明の第１の実施形態における疑似乱数生成器の機能ブロックを示す第１疑似乱数生成器機能ブロック図。
【図２】同実施形態における疑似乱数生成器の回路の概略を示す第１概略回路図。
【図３】同実施形態における疑似乱数生成器強度評価装置の機能ブロックを示す第１疑似乱数生成器強度評価装置機能ブロック図。
【図４】同実施形態における疑似乱数生成器強度評価装置のハードウェア構成を示す疑似乱数生成器強度評価装置ハードウェア構成図。
【図５】同実施形態における疑似乱数生成器強度評価装置の処理フローの一例を示す第１疑似乱数生成器強度評価装置フローチャート。
【図６】本発明の第２の実施形態における疑似乱数生成器の機能ブロックを示す第２疑似乱数生成器機能ブロック図。
【図７】同実施形態における疑似乱数生成器の回路の概略を示す第２概略回路図。
【図８】同実施形態における第１回路構成データ受付部の機能ブロックを示す第１回路構成データ受付部機能ブロック図。
【図９】同実施形態における疑似乱数生成器強度評価装置の処理フローの一例を示す第２疑似乱数生成器強度評価装置フローチャート。
【図１０】本発明の第３の実施形態における暗号化装置の機能ブロックを示す暗号化装置機能ブロック図。
【図１１】同実施形態における暗号化装置の処理フローの一例を示す暗号化装置フローチャート。
【図１２】同実施形態における第１強度値データ格納部のデータとデータ構造の一例を示す第１強度値データ格納部データ構造図。
【図１３】同実施形態の別の例における第２強度値手順対応データ格納部のデータとデータ構造の一例を示す第２強度値手順対応データ格納部データ構造図。
【符号の説明】
【０１０１】
１…疑似乱数生成器
１２…第１回路
１３…第２回路
２…疑似乱数生成器強度評価装置
２３…評価部
３…暗号化装置
３１…強度要求値データ受付部
３２…疑似乱数生成部
３３…第１強度値データ格納部
３４…算出手順設定部
３５…暗号化部
【図１】
2006285830.tif 000015
【図２】
2006285830.tif 000016
【図３】
2006285830.tif 000017
【図４】
2006285830.tif 000018
【図５】
2006285830.tif 000019
【図６】
2006285830.tif 000020
【図７】
2006285830.tif 000021
【図８】
2006285830.tif 000022
【図９】
2006285830.tif 000023
【図１０】
2006285830.tif 000024
【図１１】
2006285830.tif 000025
【図１２】
2006285830.tif 000026
【図１３】
2006285830.tif 000027