(57)【要約】暗号化のための乱数がＣＡコアによって生成される。ＣＡコアは、１次元２状態３近傍セルオートマトンの構成とされる。セルの各セルに対しては、自分自身と両隣のセルに対する合計３個の入力が供給される。各セルは、論理演算を行い、論理演算結果を出力する。各セルには、レジスタが含まれ、各レジスタがクロックに同期して論理演算結果を順次取り込み、保持する。セルの出力が次のタイムステップの演算のために、セルに対してフィードバックされるが、その場合に、出力を左側へシフトさせてセルにフィードバックするローテーションシフト操作がなされる。多ビットの乱数として出力するために、セルの出力の中の４０ビットが選択される。選択されるセル番号は、等間隔ではなく、選択されるセル番号の間隔が徐々に大きくなるようにされる。
2004086673.tif 000002
【特許請求の範囲】
【請求項１】
１次元的に複数のセルが配置され、各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成装置において、
複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする経路と、
上記経路に挿入され、上記複数のセルの出力を所定のセル数シフトするシフト処理手段とを備えた乱数生成装置。
【請求項２】
請求の範囲１において、
上記１次元２状態Ｋ近傍セルオートマトンは、次の時刻での各セルの状態値は自分自身の状態値と両隣のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態３近傍セルオートマトンである乱数生成装置。
【請求項３】
請求の範囲１において、
さらに、上記複数のセルの出力の中で、所定の複数のセルを選択して並列化して出力するためのサンプリング手段を備えた乱数生成装置。
【請求項４】
請求の範囲３において、
上記所定の複数のセルは、選択されるセルの互いの間隔が順に大きくなるか、または順に小さくなる乱数生成装置。
【請求項５】
請求の範囲１において、
上記フィードバックする経路および上記シフト処理手段が集積回路上に実現されたことを特徴とする乱数生成装置。
【請求項６】
複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法において、
複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする時に、上記複数のセルの出力を所定のセル数シフトする乱数生成方法。
【請求項７】
請求の範囲６において、
上記１次元２状態Ｋ近傍セルオートマトンは、次の時刻での各セルの状態値は自分自身の状態値と両隣のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態３近傍セルオートマトンである乱数生成方法。
【請求項８】
請求の範囲６において、
さらに、上記複数のセルの出力の中で、所定の複数のセルを選択して並列化して出力する乱数生成方法。
【請求項９】
請求の範囲８において、
上記所定の複数のセルは、選択されるセルの互いの間隔が順に大きくなるか、または順に小さくなる乱数生成方法。
【請求項１０】
コンピュータに対して、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法を実行させるためのプログラムにおいて、
複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする時に、上記複数のセルの出力を所定のセル数シフトする乱数生成方法を実行させるためのプログラム。
【請求項１１】
コンピュータに対して、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法を実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体において、
複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする時に、上記複数のセルの出力を所定のセル数シフトする乱数生成方法を実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項１２】
平文と乱数との排他的論理和によって暗号文を生成する暗号化装置において、
乱数は、１次元的に複数のセルが配置され、各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成装置によって生成され、
複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする経路と、
上記経路に挿入され、上記複数のセルの出力を所定のセル数シフトするシフト処理手段とを備えたことを特徴とする暗号化装置。
【請求項１３】
請求の範囲１２において、
上記１次元２状態Ｋ近傍セルオートマトンは、次の時刻での各セルの状態値は自分自身の状態値と両隣のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態３近傍セルオートマトンである暗号化装置。
【請求項１４】
請求の範囲１３において、
さらに、上記乱数生成装置が上記複数のセルの出力の中で、所定の複数のセルを選択して並列化して出力するためのサンプリング手段を備えた暗号化装置。
【請求項１５】
請求の範囲１３において、
上記所定の複数のセルは、選択されるセルの互いの間隔が順に大きくなるか、または順に小さくなる暗号化装置。
【請求項１６】
請求の範囲１３において、
上記フィードバックする経路および上記シフト処理手段が集積回路上に実現されたことを特徴とする暗号化装置。
【請求項１７】
平文と乱数との排他的論理和によって暗号文を生成する暗号化方法において、
乱数は、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法によって生成され、
上記乱数生成方法は、複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする時に、上記複数のセルの出力を所定のセル数シフトすることを特徴とする暗号化方法。
【請求項１８】
請求の範囲１７において、
上記１次元２状態Ｋ近傍セルオートマトンは、次の時刻での各セルの状態値は自分自身の状態値と両隣のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態３近傍セルオートマトンである暗号化方法。
【請求項１９】
請求の範囲１７において、
さらに、上記乱数生成方法が上記複数のセルの出力の中で、所定の複数のセルを選択して並列化して出力する暗号化方法。
【請求項２０】
請求の範囲１７において、
上記所定の複数のセルは、選択されるセルの互いの間隔が順に大きくなるか、または順に小さくなる暗号化方法。
【請求項２１】
コンピュータに対して、平文と乱数との排他的論理和によって暗号文を生成する暗号化方法を実行させるためのプログラムにおいて、
乱数は、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法によって生成され、
上記乱数生成方法は、複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする時に、上記複数のセルの出力を所定のセル数シフトすることを特徴とする暗号化方法を実行させるためのプログラム。
【請求項２２】
コンピュータに対して、平文と乱数との排他的論理和によって暗号文を生成する暗号化方法を実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体において、
乱数は、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法によって生成され、
上記乱数生成方法は、複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする時に、上記複数のセルの出力を所定のセル数シフトすることを特徴とする暗号化方法を実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項２３】
暗号文と乱数との排他的論理和によって暗号文を復号する復号装置において、
乱数は、１次元的に複数のセルが配置され、各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成装置によって生成され、
複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする経路と、
上記経路に挿入され、上記複数のセルの出力を所定のセル数シフトするシフト処理手段とを備えたことを特徴とする復号装置。
【請求項２４】
請求の範囲２３において、
上記１次元２状態Ｋ近傍セルオートマトンは、次の時刻での各セルの状態値は自分自身の状態値と両隣のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態３近傍セルオートマトンである復号装置。
【請求項２５】
請求の範囲２３において、
上記フィードバックする経路および上記シフト処理手段が集積回路上に実現されたことを特徴とする復号装置。
【請求項２６】
暗号文と乱数との排他的論理和によって暗号文を復号する復号方法において、
乱数は、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法によって生成され、
上記乱数生成方法は、複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする時に、上記複数のセルの出力を所定のセル数シフトすることを特徴とする復号方法。
【請求項２７】
請求の範囲２６において、
上記１次元２状態Ｋ近傍セルオートマトンは、次の時刻での各セルの状態値は自分自身の状態値と両隣のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態３近傍セルオートマトンである復号方法。
【請求項２８】
コンピュータに対して、暗号文と乱数との排他的論理和によって暗号文を復号する復号方法を実行させるためのプログラムにおいて、
乱数は、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法によって生成され、
上記乱数生成方法は、複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする時に、上記複数のセルの出力を所定のセル数シフトすることを特徴とする復号方法を実行させるためのプログラム。
【請求項２９】
コンピュータに対して、コンピュータに対して、暗号文と乱数との排他的論理和によって暗号文を復号する復号方法を実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体において、
乱数は、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法によって生成され、
上記乱数生成方法は、複数のセルの少なくとも一つのセルの出力を出力すると共に、上記複数のセルの次の時刻の状態値を更新するために、現在の時刻の上記複数のセルの出力を入力にフィードバックする時に、上記複数のセルの出力を所定のセル数シフトすることを特徴とする復号方法を実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】  この発明は、例えばストリーム暗号化に適用される乱数生成、暗号化および復号のための装置、方法、プログラム、並びに記録媒体に関する。
【背景技術】  近年のインターネットやモバイルコミュニケーションの急速な普及に伴い、ディジタル情報の保護の重要性が増大している。暗号技術として、暗号化と復号に同じ秘密鍵を使用する共通鍵方式が知られており、共通鍵方式の中に、ブロック暗号とストリーム暗号とがある。
第１図Ａは、ブロック暗号を説明するものである。平文の情報ビット列を所定の長さ（ブロック）に区切り、ブロック毎に暗号化器１によって暗号化する。暗号化文もブロック毎に区切られている。
一方、第１図Ｂに示すように、ストリーム暗号の場合では、暗号化器（乱数生成器）２によって発生した乱数をビット毎に情報ビット列に対して作用させて暗号化を行う。
ストリーム暗号においては、平文のビット系列をｍ１，ｍ２，ｍ３，・・・とし、乱数のビット系列をｒ１，ｒ２，ｒ３，・・・とし、暗号文のビット系列をｃ１，ｃ２，ｃ３，・・・とすると、暗号化処
2004086673.tif 000003
、ｉ＝１，２，３，・・・）となる。
送信側と受信側とで共通の乱数を生成することが必要とされる。乱数列または乱数生成のパターンが知られてしまうと、容易に解読されてしまう。したがって、暗号用として安全な乱数は、統計的な乱数の一様性のみならず、過去の乱数列から将来の乱数列が予測不可能であることも必要である。
一般的にストリーム暗号の方がブロック暗号より高速であり、画像データのような大量のデータを暗号化して伝送する場合では、ストリーム暗号の方が適している。また、ストリーム暗号の方が回路規模を小さくできる場合が多い。このため、ＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）やＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）等のブロック暗号が標準化されているにもかかわらず、ストリーム暗号が使われている。
しかしながら、現在最も広く使用されているストリーム暗号であるＲＣ４（（Ｒｉｖｅｓｔ  Ｃｉｐｈｅｒ）４  Ｓｔｒｅａｍ  Ｃｉｐｈｅｒ）は、ｗｅａｋ  ｋｅｙの存在、ＷＥＰ（Ｗｉｒｅｄ  Ｅｑｕｉｖａｌｅｎｔ  Ｐｒｉｖａｃｙ  ｐｒｏｔｏｃｏｌ）を使うことによる問題点、アウトプットにおけるバイアスの存在など、その安全性がアカデミックな意味で問題視されている。また、ＲＣ４は、ソフトウェア向けにデザインされたものであり、その暗号化速度には限界がある。このことから、ハードウェア向けの安全で高速なストリーム暗号が求められていると言える。
一方、非線形力学系の分野で研究されてきたカオスを用いた暗号化アルゴリズムが近年盛んに研究されている。しかしながら、その多くは、写像力学系に基づいており、状態、時間、空間が全て離散な力学系であるセルオートマトン（以下、適宜ＣＡと表記する）を用いた暗号化アルゴリズムは、広く知られていない。ＣＡは、その構成上ハードウェアの埋め込みに適しており、高速なストリーム暗号の実現が期待される。Ｓｔｅｐｈｅｎ  Ｗｏｌｆｒａｍは、”Ａｄｖ．Ａｐｐｌ．Ｍａｔｈ．Ｖｏｌ．７（１９８６）１２３−１６９”、”Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｖｏｌ．２１８（１９８６）４２９−４３２”等において、１次元２状態３近傍セルオートマトンのルール３０を用いたストリーム暗号を提案している。
第２図は、ＣＡを用いた暗号化アルゴリズムによる構成を示す。入力情報データ（平文）が１ビットのストリームとして排他的論理和回路（以下、適宜ＥＸ−ＯＲゲートと称する）３に入力される。ＣＡコア４（乱数生成器）からの１ビットのストリームであるキーストリームがＥＸ−ＯＲゲート３の他方の入力とされ、ＥＸ−ＯＲゲート３から暗号文が出力される。ＣＡコア４に対しては、初期値としてのシークレットキーとクロックとが入力され、乱数が生成される。
１次元２状態３近傍セルオートマトンとは、１次元格子上にセルが配置され、各セルは、状態値として０か１を持つものとし、次の時刻（以下、タイムステップと適宜称する）での各セルの状態値は、自分自身の状態値と両隣りの状態値だけに依存する関数（ルール）で与えられ、各セルの状態値は、この関数によって同期的に更新される。すなわち、下記の式（１）で表される。
2004086673.tif 000004
ここで、ｉおよびｔが付加されたＳは、タイムステップｔでのｉ番目のセルの状態を表す。
Ｓｔｅｐｈｅｎ  Ｗｏｌｆｒａｍは、ランダム列を生み出すルールを１次元２状態３近傍ＣＡの範囲で探索し、ルール３０が最も良い擬似乱数生成器であることを示した。このルール３０の状態更新ルールは、下記の式（２）で表される。
2004086673.tif 000005
2004086673.tif 000006
式（２）をブール代数で表すと、以下の式（３）で示すものとなる。
2004086673.tif 000007
第３図は、縦軸に時間（ｔ）をとり、横軸にセル番号（ｉ）をとった図を示す。第３図では、影を付したｉ番目例えば第６番目のセル番号の状態がキーストリームとして使用されることを示している。
Ｓｔｅｐｈｅｎ  Ｗｏｌｆｒａｍは、ＣＡルール３０が生み出すビット列を７種類の統計テストにかけてそのランダム性を調べたが、ビット列のランダム性を何個か調べただけで、擬似乱数生成器としての性能評価としては不十分なものであった。
暗号用の乱数としての評価の試験とし、一例として、ＮＩＳＴ（Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ：米国標準技術研究所）が公開しているＲＮＧ  Ｔｅｓｔｉｎｇがある（ＮＩＳＴ  Ｓｐｅｃｉａｌ  Ｐｕｂｌｉｃａｔｉｏｎ（ＳＰ）８００−２２  Ａ  Ｓｔａｔｉｓｔｉｃａｌ  Ｔｅｓｔ  Ｓｕｉｔｅ  ｆｏｒ  Ｒａｎｄｏｍ  ａｎｄ  Ｐｓｅｕｄｏｒａｎｄｏｍ  Ｎｕｍｂｅｒ  Ｇｅｎｅｒａｔｏｒｓ  ｆｏｒ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ａｐｐｌｉｃａｔｉｏｎｓ）。第４図は、ＮＩＳＴの１６種類のテスト項目を示す。
ＮＩＳＴのテストでは、ｎビットの列に対してｐ−ｖａｌｕｅを求める。ｐ−ｖａｌｕｅは、理論上の完全なランダム列生成器がそのビット列よりランダム性が低いビット列を出す確率である。ここでの「ランダム性が低い」とは、テストしている特性量が平均値より離れていることを意味する。
求められたｐ−ｖａｌｕｅについて、ｐ−ｖａｌｕｅ≧αの場合を「サクセス」とする。これをｍサンプルに対して行い、そのサクセス率とｐ−ｖａｌｕｅの一様性を評価する。ｐ−ｖａｌｕｅが一様で、かつサクセス率が１−αを中心とする特定の範囲に収まっている場合にテストを「パスする」と言う。初期値（ＣＡコアに与えられるシークレットキー）に対して多少テストの結果が異なるので、各テストに対して数通りの初期値でテストする。以下の例では、ｎ＝１０６、α＝０．０１、ｍ＝１０００を用いた。各テストで用いたパラメータを第５図に示す。
第６図は、ＲＣ４（２５６ビットキー）のテスト結果を示し、第７図は、ＣＡルール３０のテスト結果を示す。各図は、初期値を異ならせて得られた二つのテスト結果を示している。テスト結果を示すグラフにおいて、横軸は、テストの種類、縦軸はサクセス率を示し、上下の線で囲まれた領域がパス領域である。また、ＣＡの場合、セル番号を固定して時間方向にビット列をサンプリングした。セル数は、例えば１０００である。
第６図から分かるように、ＲＣ４では、全てのテストでｐ−ｖａｌｕｅの一様性は、パスするが、７番目のテスト項目（Ｎｏｎ−ｏｖｅｒｌａｐｐｉｎｇ  Ｔｅｍｐｌａｔｅ  Ｍａｔｃｈｉｎｇ  Ｔｅｓｔの一つのｔｅｍｐｌａｔｅに対してだけ常にサクセス率が範囲からはずれている問題がある。７番目のテストでは、１４８種類のｔｅｍｐｌａｔｅを用いてパターンマッチングし、各種類に対するサクセス率が計算される。また、初期値によっては、１０番目のテスト項目（Ｌｅｍｐｅｌ  Ｚｉｖ  Ｃｏｍｐｒｅｓｓｉｏｎ）もはずれている。このように、ＲＣ４は、いくつかのテストをパスしないという問題がある。
第７図から分かるように、ＣＡルール３０では、初期値によっては、３番目のテスト項目（Ｒｕｎｓ  Ｔｅｓｔ）、１５番目のテスト項目（Ｒａｎｄｏｍ  Ｅｘｃｕｒｓｉｏｎｓ）、１６番目のテスト項目（Ｒａｎｄｏｍ  Ｅｘｃｕｒｓｉｏｎｓ  Ｖａｒｉａｎｔ）がパスしないという問題がある。それよりも深刻なことは、１０番目のテスト項目（Ｌｅｍｐｅｌ  Ｚｉｖ  Ｃｏｍｐｒｅｓｓｉｏｎ）のｐ−ｖａｌｕｅの一様性が破れていることである。これは、ビット列の特徴に偏りがあることを意味しており、そこからランダム列との区別ができる可能性があり問題である。
また、１タイムステップで１ビットの情報しか使用することができないという制約があるので、セル数（ゲート数）が増えても暗号化の処理速度を高速とできないという問題があった。
したがって、この発明の目的は、ＣＡを用いた場合に、全てのテストをパスすることができ、ランダム性に優れ、また、暗号化の処理速度を向上させることが可能な乱数生成、暗号化および復号のための装置、方法、プログラム、並びに記録媒体を提供することにある。
【発明の開示】
請求の範囲１の発明は、１次元的に複数のセルが配置され、各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成装置において、
複数のセルの少なくとも一つのセルの出力を出力すると共に、複数のセルの次の時刻の状態値を更新するために、現在の時刻の複数のセルの出力を入力にフィードバックする経路と、
経路に挿入され、複数のセルの出力を所定のセル数シフトするシフト処理手段とを備えた乱数生成装置である。
請求の範囲６の発明は、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法において、
複数のセルの少なくとも一つのセルの出力を出力すると共に、複数のセルの次の時刻の状態値を更新するために、現在の時刻の複数のセルの出力を入力にフィードバックする時に、複数のセルの出力を所定のセル数シフトする乱数生成方法である。
請求の範囲１０の発明は、コンピュータに対して、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法を実行させるためのプログラムにおいて、
複数のセルの少なくとも一つのセルの出力を出力すると共に、複数のセルの次の時刻の状態値を更新するために、現在の時刻の複数のセルの出力を入力にフィードバックする時に、複数のセルの出力を所定のセル数シフトする乱数生成方法を実行させるためのプログラムである。
請求の範囲１１の発明は、乱数生成方法を実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体である。
請求の範囲１２の発明は、平文と乱数との排他的論理和によって暗号文を生成する暗号化装置において、
乱数は、１次元的に複数のセルが配置され、各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成装置によって生成され、
複数のセルの少なくとも一つのセルの出力を出力すると共に、複数のセルの次の時刻の状態値を更新するために、現在の時刻の複数のセルの出力を入力にフィードバックする経路と、
経路に挿入され、複数のセルの出力を所定のセル数シフトするシフト処理手段とを備えたことを特徴とする暗号化装置である。
請求の範囲１７の発明は、平文と乱数との排他的論理和によって暗号文を生成する暗号化方法において、
乱数は、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法によって生成され、
乱数生成方法は、複数のセルの少なくとも一つのセルの出力を出力すると共に、複数のセルの次の時刻の状態値を更新するために、現在の時刻の複数のセルの出力を入力にフィードバックする時に、複数のセルの出力を所定のセル数シフトすることを特徴とする暗号化方法である。
請求の範囲２１の発明は、コンピュータに対して、平文と乱数との排他的論理和によって暗号文を生成する暗号化方法を実行させるためのプログラムにおいて、
乱数は、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法によって生成され、
乱数生成方法は、複数のセルの少なくとも一つのセルの出力を出力すると共に、複数のセルの次の時刻の状態値を更新するために、現在の時刻の複数のセルの出力を入力にフィードバックする時に、複数のセルの出力を所定のセル数シフトすることを特徴とする暗号化方法を実行させるためのプログラムである。
請求の範囲２２の発明は、暗号化方法を実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体である。
請求の範囲２３の発明は、暗号文と乱数との排他的論理和によって暗号文を復号する復号装置において、
乱数は、１次元的に複数のセルが配置され、各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成装置によって生成され、
複数のセルの少なくとも一つのセルの出力を出力すると共に、複数のセルの次の時刻の状態値を更新するために、現在の時刻の複数のセルの出力を入力にフィードバックする経路と、
経路に挿入され、複数のセルの出力を所定のセル数シフトするシフト処理手段とを備えたことを特徴とする復号装置である。
請求の範囲２６の発明は、暗号文と乱数との排他的論理和によって暗号文を復号する復号方法において、
乱数は、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法によって生成され、
乱数生成方法は、複数のセルの少なくとも一つのセルの出力を出力すると共に、複数のセルの次の時刻の状態値を更新するために、現在の時刻の複数のセルの出力を入力にフィードバックする時に、複数のセルの出力を所定のセル数シフトすることを特徴とする復号方法である。
請求の範囲２８の発明は、コンピュータに対して、暗号文と乱数との排他的論理和によって暗号文を復号する復号方法を実行させるためのプログラムにおいて、
乱数は、複数のセルの各セルが状態値として０か１を持ち、次の時刻での各セルの状態値は自分自身の状態値と近傍のセルの状態値だけに依存するルールで与えられ、各セルの状態値はこのルールによって更新される１次元２状態Ｋ近傍セルオートマトンによる乱数生成方法によって生成され、
乱数生成方法は、複数のセルの少なくとも一つのセルの出力を出力すると共に、複数のセルの次の時刻の状態値を更新するために、現在の時刻の複数のセルの出力を入力にフィードバックする時に、複数のセルの出力を所定のセル数シフトすることを特徴とする復号方法を実行させるためのプログラムである。
請求の範囲２９の発明は、復号方法を実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体である。
【図面の簡単な説明】  第１図は、従来のブロック暗号およびストリーム暗号の概略を説明するための略線図である。
第２図は、従来のＣＡを用いた暗号化器の構成を示すブロック図である。
第３図は、従来のＣＡを用いた暗号化器におけるキーストリームの説明に用いる略線図である。
第４図は、暗号用の乱数としての評価の統計テストの一例のテスト項目を示す略線図である。
第５図は、暗号用の乱数としての評価の統計テストの一例のパラメータを示す略線図である。
第６図は、従来のストリーム暗号であるＲＣ４の統計テストの結果の一例および他の例を示す略線図である。
第７図は、従来のＣＡを用いた暗号の統計テストの結果の一例および他の例を示す略線図である。
第８図は、この発明による暗号化器の基本構成および一実施形態を示すブロック図である。
第９図は、この発明による暗号化器の一実施形態を示すブロック図である。
第１０図は、この発明による暗号化器の一実施形態におけるキーストリームの説明に用いる略線図である。
第１１図は、ローテーションシフトを行うこの発明の統計テストの結果の一例および他の例を示す略線図である。
第１２図は、この発明の一実施形態の統計テストの結果の一例および他の例を示す略線図である。
【発明を実施するための最良の形態】  第８図Ａは、この発明の基本的構成を示す。入力情報データ（平文）がＭビットの並列データに変換されてＥＸ−ＯＲゲート１１に入力される。ＣＡコア１２からのＭビットの並列データのキーストリームがＥＸ−ＯＲゲート１１の他方の入力とされ、ＥＸ−ＯＲゲート１１から暗号文が出力される。ＣＡコア１２に対しては、初期値としてのシークレットキーのデータとクロックとが入力され、４０ビット並列の乱数データ（キーストリーム）が生成される。図８Ｂは、一例として、Ｍ＝４０とした場合の一実施形態を示す。ＣＡコア１２は、前述の１次元２状態３近傍セルオートマトンの構成とされ、式（２）または式（３）で示すようなルール３０にしたがって状態更新がなされるものである。
復号器の構成は、図示しないが、上述した暗号化器と同様に構成される。すなわち、暗号文がＥＸ−ＯＲゲートに供給され、キーストリームがＥＸ−ＯＲゲートに供給されることによって復号処理がなされる。初期値を共通として、同期をとることによって暗号化と復号とで、共通の鍵が使用される。
第９図は、一実施形態（３近傍ＣＡ、セル数１０００）におけるＣＡコア１２の構成の一例を示す。Ｓ１，Ｓ２，Ｓ３，・・・・，Ｓ９９９，Ｓ１０００は、それぞれ第１番目から第１０００番目のセルを示す。各セルに対しては、自分自身と両隣のセルに対する合計３個の入力が供給される。第１番目のセルＳ１に対する左隣のセルに対する入力として、セルＳ１０００に対する入力が使用され、第１０００番目のセルＳ１０００に対する右隣のセルに対する入力として、セルＳ１に対する入力が使用される。各セルは、前述した式（２）または式（３）で表される論理演算を行い、論理演算結果Ｏ１〜Ｏ１０００を出力する。
セルＳ１〜Ｓ１０００には、それぞれレジスタが含まれ、各レジスタがクロック（図示しない）に同期して論理演算結果を順次取り込み、保持する構成とされている。あるタイムステップｔにおける論理演算結果がセルＳ１〜Ｓ１０００から出力されると、各セルにおいて演算された次のタイムステップｔ＋１の論理演算結果がレジスタに取り込まれることになる。
セルＳ１〜Ｓ１０００の出力Ｏ１〜Ｏ１０００が次のタイムステップの演算のために、セルＳ１〜Ｓ１０００に対してフィードバックされるが、その場合に、ローテーションシフト部１３によってローテーションシフト操作がなされる。ローテーションシフト操作は、出力Ｏ１〜Ｏ１０００を全体的に図に向かって見て左側へシフトさせてセルにフィードバックするものである。一例として、１１セルのシフトがなされる。この場合では、最も左端のセルＳ１に対して、出力Ｏ１２が入力され、左から２番目のセルＳ２に対して、出力Ｏ１３が入力される。以下、１１セル分のシフトがなされてフィードバックされる。また、セルＳ１の左側にはみ出した出力Ｏ１〜Ｏ１１は、右側の１１個のセルＳ９９０〜Ｓ１０００に対して入力される。
なお、ローテーションシフトの方向は、図面に向かって見て左側としたが、反対の右側へローテーションシフトしても良い。また、ローテーションシフト量は、設定された後に変える必要がないので、ローテーションシフト部１３は、結線の仕方によって構成できる。但し、ローテーションシフト量の設定の変更を可能とするために、スイッチング回路によってローテーションシフト部１３を構成しても良い。
セルＳ１〜Ｓ１０００の出力Ｏ１〜Ｏ１０００の中の一つの出力を１ビットのキーストリームして選択して暗号鍵として使用することができる。一実施形態では、多ビットのキーストリームとして出力するために、セルＳ１〜Ｓ１０００の出力Ｏ１〜Ｏ１０００がサンプリング部１４に供給される。サンプリング部１４は、出力Ｏ１〜Ｏ１０００の中のＭビットをキーストリームとして選択する。サンプリングされるセル番号は、等間隔ではなく、選択されるセル番号の間隔が徐々に大きくなるようにされる。例えばＮ＝１０００，Ｍ＝４０の場合、１，７，１４，２２，３１，４１，５２，６４，・・・，９７６と間隔が１ずつ増加するようになされる。
一般に、ｎ番目（ｎ＞１）のセル番号ａ（ｎ）は、下記の式（４）で表したものとなる。上述した例の場合、パラメータは、ａ（１）＝１，ｄ＝６である。
2004086673.tif 000008
なお、サンプリングの方法は、設定された後に変える必要がないので、サンプリング部１４は、有効な出力線を設定するだけで構成できる。但し、サンプリングの方法の設定の変更を可能とするために、スイッチング回路によってサンプリング部１４を構成しても良い。また、サンプリングされるセル番号の間隔が徐々に大きくなるようにしたが、徐々に小さくなるようにしても良い。また、ランダムにセルの間隔が変化するものであっても良い。
第１０図は、上述した一実施形態においてサンプリング部１４から出力されるキーストリームを示すものである。最初のタイムステップ（ｔ＝１）では、元のＣＡから見ると、セル番号の１，７，１４，２２，３１，・・・がキーストリームとして選択されて出力される。ローテーションシフト処理がなされるので、次のタイムステップ（ｔ＝２）では、元のＣＡから見ると、セル番号の１２，１８，２５，３３，・・・がキーストリームとして選択されて出力される。
第１１図は、上述したこの発明の一実施形態において、ローテーションシフト部１３のみを有し、サンプリング部１４を有しない場合のＮＩＳＴテストの結果を示す。第１２図は、ローテーションシフト部１３およびサンプリング部１４の両方を有する場合のＮＩＳＴテストの結果を示す。
ローテーションシフト数を１１とした場合のテスト結果（第１１図）から分かるように、二つの初期値に対して１６種類の全てのテストをパスすることができる。
また、セル数が１０００で、サンプリングによって４０セルの情報を抜き出した場合のテスト結果（第１２図）では、初期値によっては、７番目のテスト（Ｎｏｎ−ｏｖｅｒｌａｐｐｉｎｇ  Ｔｅｍｐｌａｔｅ  Ｍａｔｃｈｉｎｇ  Ｔｅｓｔ）の一つのパターンがパスしていないが、常にパスしないということではないので問題はない。
セル数１０００のＣＡルール３０（ローテーションシフト数１１セル）をＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ：大規模ＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ  ｌｏｇｉｃ  Ｄｅｖｉｃｅ）に実装した結果、（ゲート数＝１４６９９、最大動作周波数＝１０５．８３１ＭＨｚ、暗号化（復号）速度＝４．２３３Ｇｂｐｓ）の結果が得られた。例えばディジタルビデオデータのリアルタイム暗号化および復号では、クロックの周波数が２７ＭＨｚであり、約１Ｇｂｐｓの暗号（復号）化速度を達成できた。
上述したこの発明によれば、先に提案されているＲＣ４およびルール３０と比較してランダム性をより向上することができる。また、安全性を損なうことなく、多ビットの乱数を取り出すことができるので、暗号化の速度を向上することが可能となる。さらに、回路構成が単純であるので、最大動作周波数を高くすることができる。すなわち、大量の情報を高速に処理するハードウェアを容易に実現できる。
この発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で種々の変形や応用が可能である。例えばこの発明は、一般的にＫ個のセルの状態値に依存する１次元２状態Ｋ近傍のセルオートマトンを使用できる。また、この発明による乱数生成器は、ストリーム暗号以外にモンテカルロ法に対しても適用することができる。
【符号の説明】
１１  ＥＸ−ＯＲゲート
１２  ＣＡコア
１３  ローテーションシフト部
１４  サンプリング部
Ｓ１〜Ｓ１０００  セル
2004086673.tif 000009
【図２】
2004086673.tif 000010
【図３】
2004086673.tif 000011
【図４】
2004086673.tif 000012
【図５】
2004086673.tif 000013
【図６】
2004086673.tif 000014
【図７】
2004086673.tif 000015
2004086673.tif 000016
【図９】
2004086673.tif 000017
【図１０】
2004086673.tif 000018
【図１１】
2004086673.tif 000019
【図１２】
2004086673.tif 000020
【国際調査報告】
2004086673.tif 000021
2004086673.tif 000022
2004086673.tif 000023
2004086673.tif 000024