(57)【要約】【課題】実行時にデータ変換の処理スループットを保ったままデータ変換の複雑度を向上させること。【解決手段】入力データを再構成可能ハードウェア上に構成したデータ変換回路Ｃにより変換して出力データとする。外部から受信する鍵データに基づきデータ変換規則を生成し、該生成したデータ変換規則に基づき再構成可能ハードウェア上に前記データ変換回路Ｃを設定する。【選択図】  図１
2005018310.tif 000002
【特許請求の範囲】
【請求項１】
入力データを再構成可能ハードウェア上に構成したデータ変換部により変換して出力データとするデータ変換方法であって、
外部から受信した鍵データに基づきデータ変換規則を生成し、該生成したデータ変換規則に基づき前記再構成可能ハードウェア上に前記データ変換部を構成してデータ変換を行うことを特徴とするデータ変換方法。
【請求項２】
請求項１に記載のデータ変換方法において、
前記データ変換規則は逐次実行される複数の部分変換規則の集合で構成し、各部分変換規則毎に独立に動作可能な機能で前記データ変換部を構成することを特徴とするデータ変換方法。
【請求項３】
請求項１又は２に記載のデータ変換方法において、
前記データ変換規則を前記鍵データおよび外部から受信する制約条件に基づき生成し、該制約条件はデータ変換の処理単位、要求暗号強度、要求処理スループット、要求消費電力等の条件を設定することを特徴とするデータ変換方法。
【請求項４】
外部から受信した鍵データに基づきデータ変換規則を生成する制御部と、回路の書き換えが可能な再構成可能ハードウェア上に構成され入力データを変換して出力データとするデータ変換部とを具備し、
前記データ変換部には前記再構成可能ハードウェア上に前記データ変換規則に基づくデータ変換回路が構成されていることを特徴とするデータ変換装置。
【請求項５】
請求項４に記載のデータ変換装置において、
前記データ変換部の前記データ変換回路は、前記データ変換規則を逐次実行可能な複数の部分変換規則に対応し且つ独立動作可能な複数の状態遷移演算手段の集合で構成されていることを特徴とするデータ変換装置。
【請求項６】
請求項４又は５に記載のデータ変換装置において、
前記制御部は外部から前記鍵データおよび制約条件を受信して前記鍵データおよび前記制約条件に基づき前記データ変換規則を生成し、
前記データ変換部は前記制約条件によりデータ変換の処理単位、要求暗号強度、要求処理スループット、要求消費電力等の条件を設定したデータ変換を行うよう前記データ変換回路が設定されていることを特徴とするデータ変換装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ある対象データの内容を鍵データに従って別のデータに変換するデータ変換方法およびその装置に関するものである。
【０００２】
【従来の技術】
以下、セルラーオートマトンを使用した暗号化／復号化装置をデータ変換装置の一例として説明を行う。以下では、データの暗号化／復号化装置がデータ変換装置に相当する。
【０００３】
［基本となるデータ変換方式（非特許文献１）］
まず、具体例を示す基礎となる、セルラーオートマトンを利用した共通鍵暗号方式によるデータの暗号化／復号化処理のアルゴリズムについて説明する。この処理は次のような考え方を基本としている。まず、平文データをセルラーオートマトンを構成する各セルの初期状態としてセットする。そして、秘密鍵からセルラーオートマトンの状態遷移規則（部分変換規則）を生成する。セルラーオートマトンは生成された規則に従って状態遷移を繰り返し、状態遷移後の各セルの状態が暗号文データとなる。なお、この処理における秘密鍵が鍵データに相当する。
【０００４】
前提とするセルラーオートマトンは図２２のようなｎ個のセルで構成される一次元のものである。Ｃ０，Ｃ１，・・・，Ｃｎ−１はそれぞれセルラーオートマトンを形成するセルであり、各セルはそれぞれ０または１の２つの状態のいずれかをとる。各セルは記憶素子ｍおよび演算部πを持つ。各セルの状態をｓ０，ｓ１，・・・，ｓｎ−１と表すと、セルラーオートマトンの系全体の状態Ｓを次の式
2005018310.tif 000003
で表すことが可能である。
【０００５】
各セルにはそれぞれ次状態を決定するための状態遷移規則が定義される。Ｃ０，Ｃ１，・・・，Ｃｎ−１の各セルの状態遷移規則をそれぞれπ０，π１，・・・，πｎ−１と表わすとし、系全体の状態遷移規則をΠと表わすとする。各セルは時刻がｔからｔ＋１に推移すると、状態遷移規則Πに従って状態ｓ０，ｓ１，・・・，ｓｎ−１を更新する。時刻ｔにおける系全体の状態をＳ（ｔ）、各セルの状態をそれぞれｓ０（ｔ），ｓ１（ｔ），・・・，ｓｎ−１（ｔ）と表すとする。また、状態遷移規則Πにより遷移することを明示するため、Ｓ（ｔ＋１）＝Π・Ｓ（ｔ）とも表記する。
【０００６】
例えば、セルの数（ビット数）ｎ＝４で、状態遷移規則Πが以下のように定義されている場合、
2005018310.tif 000004
Ｓ（ｔ）は図２３のような変化を起こす。図２３において、節点中の各数字はある時刻ｔにおける系全体の状態Ｓ（ｔ）の値を、節点間を接続する矢印は時刻ｔが１増加したときの系全体の状態Ｓの変化を表す。
【０００７】
さて、系全体の状態Ｓ（ｔ）の変化は状態遷移規則Πに依存して一般には様々な形態をとる。しかし、状態遷移規則Πを適切に選択することにより、図２３のように周期的に初期状態に戻るような状態遷移を起こさせることが可能である。図２３の状態遷移では８つの状態で構成される状態遷移のサイクルが２つ存在している。
【０００８】
このような状態遷移のサイクルをもつセルラーオートマトンでは、任意の時刻ｔについて次の式
2005018310.tif 000005
が成立する。ただし、Π２ｒは状態遷移規則Πによる状態遷移を２ｒ回行うことを示す。従って、２ｒは状態遷移のサイクル１つを構成する状態の数である。これを状態遷移周期と呼ぶ。２ｒは一般に最小の状態遷移周期の任意の倍数をとることが可能であるが、以下では、２ｒはそれらのうち最小のものに限定する。つまり、
2005018310.tif 000006
とする。
【０００９】
この性質を利用すると、任意の状態ＳについてＴ＝ΠｒＳ，Ｓ＝ΠｒＴ、Ｓ≠ＴなるＴを定めることが可能である。例えば、図２３では２ｒ＝８であるため、これを元にＳ、Ｔの組を計算すると次の
2005018310.tif 000007
ようになる。
【００１０】
この関係により、状態遷移規則Πから状態Ｓの値域０≦Ｓ＜２４における整数の変換規則が得られる。これを状態遷移規則Πのデータ変換規則と呼ぶ。データ変換規則は一般に非線形なものとなるため、これら｛Ｓ，Ｔ｝の組から状態遷移規則Πを計算するのは困難である。従って、このデータ変換規則を暗号化処理に利用することが可能である。具体的には、平文データを初期状態としてセルラーオートマトンにセットし、これを秘密鍵から生成した状態遷移規則Πにより状態遷移をさせることで、平文データの暗号化が可能である。なお、その原理から、この暗号化方式における暗号文データからの平文データの取得は初期状態に暗号文データをセットし、同様に状態遷移規則Πにより状態遷移させ、状態Ｓを取り出すことで可能である。
【００１１】
より一般的には、状態遷移規則を複数用意し、これを多重に作用させることでさらに暗号の安全性を高める。つまり、秘密鍵から状態遷移規則をΠ０，Π１，・・・，Πｐ−１のｐ種類を生成し、それぞれの状態遷移規則に対する状態遷移周期をそれぞれ２ｒ０，２ｒ１，・・・，２ｒｐ−１として算出する。そして、セルラーオートマトンの初期状態として平文データをセットし、
2005018310.tif 000008
を計算することで暗号化を行う。
【００１２】
この暗号化方式における暗号強度は、セルラーオートマトンを構成するセルの数ｎと多重に作用させる状態遷移規則の数ｐに依存する。つまり、セルの数ｎが大きいほど、また状態遷移規則の数ｐが大きいほど暗号の強度は増大する。
【００１３】
［従来の装置構成方式］
上記の暗号化／復号化方式の従来の実現方法には大きく２つある。１つは計算機上にプログラムしたソフトウェアによる方法で、もう１つは専用ハードウェアによる方法である。図２４にソフトウェアによる実現方法の一例を示す。図２４の例はｎ個のセルで構成されるセルラーオートマトンでのｐ個の状態遷移規則による暗号化／復号化の処理である。
【００１４】
ソフトウェアによる処理では各セルの状態遷移を順次計算して処理を行うため、ステップＡ５を
2005018310.tif 000009
回処理する必要がある。ただし、２ｒｊは状態遷移規則Πｊにおける状態遷移周期である。
【００１５】
次に、図２５にセルラーオートマトンを利用した、専用ハードウェアによる従来の暗号化装置の例を示す。この例もｎ個のセルで構成されたセルラーオートマトンによる暗号化／復号化処理を実現するものである。この暗号化装置はデータ変換部Ｒ０と制御部Ｘ０から構成される。データ変換部Ｒ０はセル状態保持メモリＭ０，Ｍ１，・・・，Ｍｎ−１及び状態遷移規則定義メモリＲＡＭから構成される。データ変換部Ｒ０にはｎビットのアドレスバスＡＢとｎビットのデータバスＤＢが存在し、アドレスバスＡＢは状態遷移規則定義メモリＲＡＭのアドレスポートＡＰ、セル状態保持メモリＭ０，Ｍ１，・・・，Ｍｎ−１及び制御部Ｘ０と接続されている。またデータバスＤＢは平文データ／暗号文データＩをやりとりする人出力部、制御部Ｘ０、状態遷移規則定義メモリＲＡＭ及びセル状態保持メモリＭ０，Ｍ１，・・・，Ｍｎ−１とそれぞれ接続されている。一方、制御部Ｘ０はデータ変換部Ｒ０のアドレスバスＡＢ、データバスＤＢとの接続を利用して状態遷移規則定義メモリＲＡＭにアクセスする機能と鍵データＫを受信する機能を持つ。
【００１６】
この暗号化装置では、鍵データＫを制御部Ｘ０が受信し、データ変換部Ｒ０の動作を制御部Ｘ０が制御することで動作する。制御部Ｘ０の制御手順の一例を図２６に示す。鍵データＫと平文データ／暗号文データＩが送られると制御部Ｘ０が動作を開始する。なお、Ｉは暗号化処理時は平文データ、復号化処理時は暗号文データである。最初に制御部Ｘ０はステップＢ１のようにセル状態保持メモリＭ０，Ｍ１，・・・，Ｍｎ−１にデータＩをセットするようにデータ変換部Ｒ０に指示する。次にステップＢ２のように、制御部Ｘ０は鍵データＫから状態遷移規則の列Π０，Π１，・・・，Πｐ−１、及びそれらの状態遷移周期２ｒ０，２ｒ１，・・・，２ｒｐ−１を算出する。続いて、ステップＢ４のように状態遷移規則定義メモリＲＡＭに状態遷移規則を書き込む。具体的には、セルラーオートマトンの系の状態をアドレスとし、次の状態をデータとして状態遷移規則定義メモリＲＡＭに書き込む。
【００１７】
ステップＢ５にあるように、セル状態保持メモリＭ０，Ｍ１，・・・，Ｍｎ−１をアドレスとして状態遷移規則定義メモリＲＡＭを読み出し、セル状態保持メモリＭ０，Ｍ１，・・・，Ｍｎ−１に書き戻せば、セルラーオートマトンの状態遷移が計算可能である。この処理を状態遷移周期の半分だけ行うように制御部Ｘ０がデータ変換部Ｒ０に指示する。ステップＢ５が終了した後、制御部Ｘ０はステップＢ６、ステップＢ７を処理をしてステップＢ４に戻る。これで状態遷移規則Π０の処理は終了である。この後、状態遷移規則定義メモリＲＡＭに次の状態遷移規則を書き込み、次の状態遷移を計算する。この繰り返しを行い、全ての状態遷移規則の処理が終了した後、制御部Ｘ０はステップＢ８のようにセル状態保持メモリＭ０，Ｍ１，・・・，Ｍｎ−１をデータバスＤＢに出力するように指示し、暗号化／復号化処理は終了する。
【００１８】
【非特許文献１】パリマル  パル  チャウドリ、ディパンウィッタ  ロイ  チョードハリ、スクマル  ナンディ、サンタヌ  チャトパディヤ著、「付加的セルラーオートマトン」、２６−５５頁、ＩＥＥＥコンピュータソサエティプレス、１９９７年  ＩＳＢＮ  Ｏ−８１８６−７７１７−１（Ｐａｒｉｍａｌ  Ｐａｌ  Ｃｈａｕｄｈｕｒｉ，Ｄｉｐａｎｗｉｔａ  Ｒｏｙ  Ｃｈｏｗｄｈｕｒｙ，Ｓｕｋｕｍａｒ  Ｎａｎｄｉ，ａｎｄ  Ｓａｎｔａｎｕ  Ｃｈａｔｔｏｐａｄｈｙａｙ．”Ａｄｄｉｔｉｖｅ  Ｃｅｌｌｕｌａｒ  Ａｕｔｏｍａｔａ”，ｐｐ．２６−５５．ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ  Ｐｒｅｓｓ，  １９９７．ＩＳＢＮ  Ｏ−８１８６−７７１７−１．）。
【００１９】
【発明が解決しようとする課題】
上記したソフトウェアでは逐次実行が基本となるため、この繰り返し処理を行っている間は他の状態遷移規則の計算はできない。従って、ソフトウェアではステップＡ５の処理回数が増大すると暗号化／復号化処理のスループットが低下する。つまり、ソフトウェアによる実現方法ではセルの数ｎまたは状態遷移規則の数ｐを増加させて暗号強度を高めると、暗号化／復号化処理のスループットが低下するという欠点がある。
【００２０】
上記した専用ハードウェアによる従来の暗号化／復号化装置では、セルラーオートマトンの構成セル数ｎがハードウェアの設計時に決定されてしまい、高い機密性の要求される暗号化／復号化処理を行う要求が発生した場合、ｎの追加によって暗号強度を向上させるのが困難であるという欠点がある。また、暗号強度を向上させるために状態遷移規則の数ｐを増大させる場合についても、それに応じてステップＢ５の処理回数が増加するため、暗号化／復号化処理のスループットが低下するという欠点がある。
【００２１】
なお、上記ソフトウェアによる方法と専用ハードウェアによる方法を組み合わせた方法も考えられるが、どちらの方法も暗号強度の向上に対して暗号処理のスループットが低下するという欠点を解決することは出来ないため、両者の組み合わせでもこの欠点を解決することが出来ない。
【００２２】
加えて、専用ハードウェアによる従来の暗号化／復号化装置では、実用的に考えられる暗号強度においてスループットが保持可能なように装置を設計するため、最も使用頻度が高いと思われる平均的な強度の暗号処理では設計したハードウェアの能力が余剰するという欠点がある。
【００２３】
本発明はこれらの欠点を除去するためになされたもので、第１の目的は、実行時に回路の書き換えが可能な再構成可能ハードウェアを利用し、データの変換規則を実行時に再構成可能ハードウェア上に設定することで、データ変換の処理スループットを保ったまま複雑なデータ変換を実現可能たらしめることである。
【００２４】
第２の目的は、実行時の変換規則の再構成可能なハードウェアの設定内容を変更することで、データ変換処理のスループットを状況に応じて柔軟に変更し、データ変換処理に必要な資源を最適な量に調整可能とすることである。
【００２５】
【課題を解決するための手段】
請求項１にかかる発明は、入力データを再構成可能ハードウェア上に構成したデータ変換部により変換して出力データとするデータ変換方法であって、外部から受信した鍵データに基づきデータ変換規則を生成し、該生成したデータ変換規則に基づき前記再構成可能ハードウェア上に前記データ変換部を構成してデータ変換を行うことを特徴とするデータ変換方法とした。
【００２６】
請求項２にかかる発明は、請求項１に記載のデータ変換方法において、前記データ変換規則は逐次実行される複数の部分変換規則の集合で構成し、各部分変換規則毎に独立に動作可能な機能で前記データ変換部を構成することを特徴とするデータ変換方法とした。
【００２７】
請求項３にかかる発明は、請求項１又は２に記載のデータ変換方法において、前記データ変換規則を前記鍵データおよび外部から受信する制約条件に基づき生成し、該制約条件はデータ変換の処理単位、要求暗号強度、要求処理スループット、要求消費電力等の条件を設定することを特徴とするデータ変換方法とした。
【００２８】
請求項４にかかる発明は、外部から受信した鍵データに基づきデータ変換規則を生成する制御部と、回路の書き換えが可能な再構成可能ハードウェア上に構成され入力データを変換して出力データとするデータ変換部とを具備し、前記データ変換部には前記再構成可能ハードウェア上に前記データ変換規則に基づくデータ変換回路が構成されていることを特徴とするデータ変換装置とした。
【００２９】
請求項５にかかる発明は、請求項４に記載のデータ変換装置において、前記データ変換部の前記データ変換回路は、前記データ変換規則を逐次実行可能な複数の部分変換規則に対応し且つ独立動作可能な複数の状態遷移演算手段の集合で構成されていることを特徴とするデータ変換装置とした。
【００３０】
請求項６にかかる発明は、請求項４又は５に記載のデータ変換装置において、前記制御部は外部から前記鍵データおよび制約条件を受信して前記鍵データおよび前記制約条件に基づき前記データ変換規則を生成し、前記データ変換部は前記制約条件によりデータ変換の処理単位、要求暗号強度、要求処理スループット、要求消費電力等の条件を設定したデータ変換を行うよう前記データ変換回路が設定されていることを特徴とするデータ変換装置とした。
【００３１】
【発明の実施の形態】
［第１の実施形態］（請求項１、４）  第１の実施形態のデータ暗号化／復号化装置の構成例を図１に示す。この装置は制御部Ｘとデータ変換部Ｒで構成される。制御部Ｘは鍵データＫを受信し、構成データＹをデータ変換部Ｒに送信する機能を持つ。一方、データ変換部Ｒは平文データあるいは暗号文データＩを受信し、暗号文データあるいは平文データＯを送信する機能を持つ。この装置が暗号化処理を行う場合にはＩは平文データ、Ｏは暗号文データであり、復号化処理を行う場合にはＩは暗号文データ、Ｏは平文データとなる。データ変換部Ｒは再構成可能ハードウェアＤで構成され、該再構成可能ハードウェアＤ上にはデータ変換回路Ｃが構成される。なお、制御部Ｘも再構成可能ハードウェアＤの一部として実現されていても良い。
【００３２】
図１の構成によって暗号化処理を行う場合の動作を図１においてセルの数（ビット数）ｎ＝４、状態遷移規則（部分変換規則）の数ｐ＝１の場合を例にとって説明する。ｐ＝１であるため、状態遷移規則はΠ０の１つである。まず、制御部Ｘは鍵データＫを外部から受信する。鍵データＫは４ビットで構成されるとし、Ｋの各ビットＫｉ（０≦ｉ＜４）の値に応じてＸはｉ番目のセルの状態遷移規則πｉを次の
2005018310.tif 000010
のように生成するとする。
【００３３】
例えば、鍵データＫがＫ３＝１、Ｋ２＝１、Ｋ１＝１、Ｋ０＝１である場合、式６で表わされる状態遷移規則の計算を行う回路は図２のようになる。図２のπ０，π１，π２，π３がそれぞれ式６で示される状態遷移規則を計算する回路（ＸＮＯＲ）となっている。図２では、セルラーオートマトンの現状態をＩ０，Ｉ１，Ｉ２，Ｉ３として入力し、状態遷移の結果をＯ０，Ｏ１，Ｏ２，Ｏ３として出力する。Ｋ３＝１、Ｋ２＝１、Ｋ１＝１、Ｋ０＝１である場合、その状態遷移は図３のようになる。状態遷移周期が８となるので、変換規則は状態遷移の演算を４回線り返すことで実現可能である。従って、データ変換回路Ｃの構成としては図４のようなものが考えられる。
【００３４】
なお、実際にこれを装置として実現する際には、Ｋ３、Ｋ２、Ｋ１、Ｋ０から状態遷移周期を求める必要がある。式６で表わされるセルラーオートマトンの場合、あるｊ（０≦ｊ＜ｎ）において、ｊ≦ｉ＜ｊ＋ａの範囲で常にＫｉ＝１である、という性質を満たすａの集合のうち最大の要素をＬとし、ｒを２（ｒ−１）−１＜Ｌ≦２ｒ−１を満たす整数とすると、状態遷移周期は２ｒとなる、という性質があるため（参考文献１）、これを利用して算出する。例えば、Ｋ３＝１、Ｋ２＝１、Ｋ１＝１、Ｋ０＝１である場合、連続してＫｉ＝１となるｉの数は４が最大であるため、Ｌ＝４である。従って、ｒ＝３となり、状態遷移周期は２ｒ＝８となる。
【００３５】
参考文献１：ワーナ  プリエス、アドニオス  タナイラキス、ハワード  Ｃ  カード著、「セルラーオートマトンの群の性質およびＶＬＳＩへの応用」、ＩＥＥＥトランザクション  オン  コンピュータ、Ｃ−３５巻、１２号，１０１３−１０２４頁、１９８６年１２月（Ｗｅｒｎｅｒ  Ｐｒｉｅｓ，Ａｄｏｎｉｏｓ  Ｔｈａｎａｉｌａｋｉｓ，ａｎｄ  Ｈｏｗａｒｄ  Ｃ．Ｃａｒｄ  ”Ｇｒｏｕｐ  ｐｒｏｐｅｒｔｉｅｓ  ｏｆ  ｃｅｌｌｕｌａｒ  ａｕｏｍａｔａ  ａｎｄ  ｖｌｓｉ  ａｐｐｌｉｃａｔｉｏｎｓ”  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ，Ｖｏｌ．Ｃ−３５，Ｎｏ．１２，ｐｐ．１０１３−１０２４，Ｄｅｃｅｍｂｅｒ  １９８６．）。
【００３６】
制御部Ｘは図４で示す回路を表す構成データＹを生成し、再構成可能ハードウェアＤに送信する。再構成可能ハードウェアＤは構成データＹを受信すると、構成データＹに従って再構成可能ハードウェアＤ上にデータ変換回路Ｃに相当する回路を設定し、データ変換回路Ｃが回路として動作する状態になる。
【００３７】
データ変換回路Ｃの構成が終了した後、制御部Ｘは平文データＩを４ビット単位でデータ変換部Ｒに送信するように指示する。送信された平文データはデータ変換回路Ｃによって演算が行われ、演算結果が暗号文データＯとして出力される。これにより、暗号化処理が完了する。
【００３８】
この第１の実施形態では、データ変換部Ｒが再構成可能ハードウェアＤ上に構成されるため、データ変換処理の複雑さに応じて回路を変更することで、データ変換処理のスループットを調整可能であるという利点がある。
【００３９】
［第２の実施形態］（請求項２、５）
第２の実施形態は第１の実施形態のデータ変換回路Ｃの具体的な構成方法に相当する。第２の実施形態として図１におけるデータ変換回路Ｃの構成例を図５に示す。データ変換回路Ｃは置換演算ユニットＴ０，Ｔ１，・・・，Ｔｎ−１がパイプライン状に接続された形をとる。具体的には、平文データ／暗号文データＩが置換演算ユニットＴ０に入力され、その置換演算ユニットＴ０の出力が置換演算ユニットＴ１に入力され、というようにそれぞれが直列に接続された形をとる。そして、置換演算ユニットＴｎ−１の出力が暗号文データ／平文データＯとなっている。
【００４０】
置換演算ユニットＴ０，Ｔ１，・・・，Ｔｎ−１はそれぞれ状態遷移規則Π０，Π１，・・・，Πｎ−１により作成されるデータ変換規則を実現する。置換演算ユニットＴ０，Ｔ１，・・・，Ｔｎ−１の構成例を図６に示す。各データ変換規則は逐次実行される複数の状態遷移規則（部分変換規則）の集合で構成される。すなわち、各置換演算ユニットＴｉ（０≦ｉ＜ｐ）は状態遷移演算ユニット（状態遷移演算手段）Ｓｉ０，Ｓｉ１，・・・，Ｓｉ（ｒｉ−１）がパイプライン状に接続された形をとる。具体的には、入力Ｉｉ０，Ｉｉ１，・・・，Ｉｉ（ｎ−１）が状態遷移演算ユニットＳｉ０に入力され、その状態遷移演算ユニットＳｉ０の出力が状態遷移演算ユニットＳｉ１に入力され、というようにそれぞれが直列に接続された形をとる。そして、状態遷移演算ユニットＳｉ（ｒｉ−１）の出力が置換演算ユニットＴｉの出力となっている。
【００４１】
状態遷移演算ユニットＳｉ０，Ｓｉ１，・・・，Ｓｉ（ｒｉ−１）はそれぞれ状態遷移規則Πｉで規定される状態遷移の演算を１回行う機能を持つ。状態遷移演算ユニットＳｉ０，Ｓｉ１，・・・，Ｓｉ（ｒｉ−１）の構成例を図７に示す。状態遷移演算ユニットＳｉ０，Ｓｉ１，・・・，Ｓｉ（ｒｉ−１）は全て同じ機能であるため、一つだけを代表して図７に示している。これを以下状態遷移演算ユニットＳｉと表記する。状態遷移演算ユニットＳｉは、状態遷移規則Πｉで規定される状態遷移の演算を１回行うセル演算ユニットπｉ０，πｉ１，・・・，πｉ（ｎ−１）と演算結果を格納する１ビット記憶素子ｍｉ０，ｍｉ１，・・・，ｍｉ（ｎ−１）から構成される。状態遷移演算ユニットＳｉへの入力データにおいて、それぞれｊ−１，ｊ，ｊ＋１ビットめの入力はセル演算ユニットπｉｊに入力され、その演算結果が記憶素子ｍｉｊに格納される。そして記憶素子ｍｉｊの内容が状態遷移演算ユニットＳｉのｊビットめの出力データとなっている。
【００４２】
このような構成を持ったデータ変換回路Ｃの具体的な動作を、セルの数（ビット数）ｎ＝４、状態遷移規則の数ｐ＝１の場合を例に説明する。この場合、状態遷移規則は１つである。そこで、その１つの状態遷移規則として、次のような場合
2005018310.tif 000011
を例とする。
【００４３】
この場合、置換演算ユニットはＴ０のみである。そして、上の状態遷移規則における状態遷移は図８のようになる。従って、状態遷移周期は８となる。このため、Ｔ０は８／２＝４つの状態遷移演算ユニットＳｉ０，Ｓｉ１，Ｓｉ２，Ｓｉ３から構成される。そして、各状態遷移演算ユニット内の状態遷移演算回路πｉ０，πｉ１，πｉ２，πｉ３はそれぞれ２入力のＸＮＯＲ回路となる。従って、データ変換回路Ｃは図９のようになる。
【００４４】
図９のデータ変換回路Ｃの動作をＩ０＝０、Ｉ１＝０、Ｉ２＝０、Ｉ３＝０という平文データ／暗号文データが入力された場合を例に説明する。各状態遷移演算ユニットＳｉ０，Ｓｉ１，Ｓｉ２，Ｓｉ３は図８のような状態遷移を計算するので、最初に１ビット記憶素子ｍ００，ｍ０１，ｍ０２，ｍ０３には１０進数で１５が格納される。すなわちｍ００＝１，ｍ０１＝１，ｍ０２＝１，ｍ０３＝１となる。そして、この値からさらに状態遷移が計算され、１ビット記憶素子ｍ１０，ｍ１１，ｍ１２，ｍ１３には１０進数で７が格納される。すなわちｍ１０＝１，ｍ１１＝１，ｍ１２＝１，ｍ１３＝０となる。以下、同様に、１ビット記憶素子ｍ２０，ｍ２１，ｍ２２，ｍ２３には１０進数で１１が格納される。すなわちｍ２０＝１，ｍ２１＝１，ｍ２２＝０，ｍ２３＝１となる。最後に、１ビット記憶素子ｍ３０，ｍ３１，ｍ３２，ｍ３３には１０進数で１が格納される。すなわちｍ３０＝１，ｍ３１＝０，ｍ３２＝０，ｍ３３＝０となる。そして、これが暗号文データ／平文データＯとなる。すなわち、Ｏ０＝１，Ｏ１＝０，Ｏ２＝０，Ｏ３＝０となる。以上の動作によって、データ変換回路Ｃはデータの変換を行う。
【００４５】
再度データ変換回路Ｃ全体の構成を見ると、データ変換回路Ｃは状態遷移演算ユニットを単位とするパイプライン処理によってデータの暗号化を行っていることが分かる。データ変換回路Ｃは全体で暗号化／復号化の処理を行うが、その内部は逐次的に、かつ各々が独立に実行可能なセルラーオートマトンの状態遷移演算の集合で構成されている。なお、図９は１回の状態遷移演算をパイプライン処理の単位としたデータ変換回路Ｃの構成であるが、図１０のように２回の状態遷移演算をパイプライン処理の単位としたデータ変換回路Ｃの構成も考えられる。
【００４６】
このようなデータ変換回路Ｃの構成方法が第２の実施形態である。この構成では、暗号化／復号化処理の実行時に制御部Ｘが鍵データＫを受信してからデータ変換回路Ｃを構成するため、実行時に決定されるセルの数ｎおよび状態遷移規則の数ｐに応じてデータ変換回路Ｃを構成可能である。従って、セルの数ｎを増加させても各セルの状態遷移を計算する並列度を実行時に増加させられるため、例えば１度に変換するデータのサイズを増大させた場合でもスループットを低下させることなく処理が可能であるという利点がある。また、状態遷移規則の数ｐを増加させても、各セルの状態遷移を計算するパイプラインの段数を実行時に増加させられるため、例えば暗号強度を増大させた場合でもスループットを低下させることなく処理が可能であるという利点がある。
【００４７】
加えて、その他の利点として、データ変換回路Ｃの回路規模を制限することにより、一般的に回路規模が小さい回路は消費電力が小さいという性質を利用して、データ変換回路Ｃを許容された消費電力で動作させることが可能である、という利点もある。
【００４８】
［第３の実施形態］（請求項３、６）
第３の実施形態のデータ暗号化／復号化装置の構成例を図１１に示す。この装置は制御部Ｘとデータ変換部Ｒで構成される。制御部Ｘは鍵データＫと制約条件Ｗを受信し、構成データＹをデータ変換部Ｒに送信する機能を持つ。一方、データ変換部Ｒは平文データ／暗号文データＩを受信し、暗号文データ／平文データＯを送信する機能を持つ。この装置が暗号化処理を行う場合、Ｉとして平文データが入力され、Ｏとして暗号文データが出力される。一方、復号化処理を行う場合、Ｉとして暗号文データが入力され、Ｏとして平文データが出力される。データ変換部Ｒは再構成可能ハードウェアＤで構成され、再構成可能ハードウェアＤ上にはデータ変換回路Ｃが構成される。なお、制御部Ｘも再構成可能ハードウェアＤの一部として実現されていても良い。
【００４９】
前記した第２の実施形態の説明で分かるように、第２の実施形態におけるデータ変換回路Ｃの構成方法は、セルの数ｎおよび状態遷移規則の数ｐを柔軟に変更可能な能力を持つ。これを利用して、データ変換の処理単位、要求暗号強度、要求処理スループット、要求消費電力に応じた制約条件Ｗを制御部Ｘに入力し、制御部Ｘがこの制約条件Ｗに応じた構成データＹを構成し、その構成データＹにより再構成可能ハードウェアＤ上にデータ変換回路Ｃを設定すれば、要求された制約条件Ｗに応じた適切な実現形態でデータ変換処理が可能になるという利点がある。
【００５０】
以下それぞれの実施例を示す。以下では、制約条件Ｗに応じて処理形態を変更する実施例として、制約条件ＷをＷ０，Ｗ１，Ｗ２の３ビットで構成する場合について説明する。制御部ＸはＷ０の値によってデータ変換回路Ｃで構成されるパイプラインの段数を変更する。具体的には、Ｗ０＝０のとき図１２のようにデータ変換回路Ｃのパイプラインを１回の状態遷移演算を単位として構成し、Ｗ０＝１のとき図１３のようにデータ変換回路Ｃのパイプラインを２回の状態遷移演算を単位として構成するとする。また、制御部ＸはＷ１の値によってデータ変換回路Ｃによって実現するセルラーオートマトンの状態遷移規則の数ｐを変更する。具体的には、Ｗ１＝０のとき制御部Ｘはデータ変換のために状態遷移規則を１つ使用し、Ｗ１＝１のとき２つ使用するとする。最後に、制御部ＸはＷ２の値によってデータ変換回路Ｃで実現するセルラーオートマトンの構成セル数を変更する。具体的には、Ｗ２＝０のときセルの数ｎを４とし、Ｗ２＝１のとき８とする。鍵データＫは４、８、１６ビットのいずれかの幅を持つとし、鍵データＫに応じて制御部Ｘは必要な数の状態遷移規則を生成する。
【００５１】
＜データ変換の処理単位を変更する実施例＞
データ変換の処理単位を変更する場合はＷ２を変更する。データ変換の処理単位を小さくとりたい場合は、外部からＷ０＝０，Ｗ１＝０，Ｗ２＝０を制約条件Ｗとして制御部Ｘに入力し、鍵データＫとして４ビットの値を制御部Ｘに入力する。この場合、制約条件Ｗの意味から、制御部Ｘは▲１▼１回の状態遷移演算をパイプライン処理の単位とする、▲２▼状態遷移規則が１つ、▲３▼セル数が４のセルラーオートマトンの状態遷移演算を行う、ようなデータ変換回路Ｃの構成データＹを生成する。
【００５２】
一例として、制御部Ｘは鍵データＫの各ビットＫｉ（０≦ｉ＜４）の値に応じてｉ番目のセルの状態遷移規則πｉを次の
2005018310.tif 000012
のように生成するとして説明する。
【００５３】
制御部Ｘはこの状態遷移１回をパイプライン処理の単位として構成するデータ変換回路Ｃの構成データＹを生成する。データ変換回路Ｃを決定するには鍵データＫから生成した状態遷移規則によるセルラーオートマトンの状態遷移周期を求める必要がある。式８で表わされるセルラーオートマトンの場合、あるｊ（０≦ｊ＜４）において、ｊ≦ｉ＜ｊ＋ａの範囲で常にＫｉ＝１である、という性質を満たすａの集合のうち最大の要素をＬとし、ｒを２（ｒ−１）−１＜Ｌ≦２ｒ−１を満たす整数とすると、状態遷移周期は２ｒとなる、という性質があるため（参考文献１）、これを利用して算出する。例えば、Ｋ３＝１，Ｋ２＝１，Ｋ１＝１，Ｋ０＝１である場合、連続してＫｉ＝１となるｉの数は４が最大であるため、Ｌ＝４である。従って、ｒ＝３となり、状態遷移周期は２ｒ＝８となる。
【００５４】
以上から、制御部Ｘはデータ変換回路Ｃを図１４のように構成する。データ変換回路Ｃは平文データ／暗号文データＩを入力として受信し、暗号文データ／平文データをＯとして出力する。この例の場合、データ変換に利用する状態遷移規則は１つなので、データ変換回路Ｃは置換演算ユニットＴ０の１つから構成される。そして、状態遷移周期が８であるため、置換演算ユニットＴ０は４つの状態遷移演算ユニットＳ００，Ｓ０１，Ｓ０２，Ｓ０３をパイプライン状に接続した構成となっている。各状態遷移演算ユニットは状態遷移を計算する論理回路と、計算結果を記憶する１ビット記憶素子から構成される。例えば、状態遷移演算ユニットＳ００では４つのＸＮＯＲ演算回路と４つの１ビット記憶素子ｍ００，ｍ０１，ｍ０２，ｍ０３から構成される。
【００５５】
制御部Ｘは図１４のようなデータ変換回路Ｃを表す構成データＹを生成し、再構成可能ハードウェアＤに送信する。再構成可能ハードウェアＤは構成データＹを受信すると、構成データＹに従って再構成可能ハードウェアＤ上にデータ変換回路Ｃに相当する回路を設定し、データ変換回路Ｃが回路として動作する状態になる。
【００５６】
データ変換回路Ｃの構成が終了した後、制御部Ｘは平文データ／暗号文データＩを４ビット単位でデータ変換部Ｒに送信するように外部に指示する。これによって外部から平文データ／暗号文データＩが送信され、送信された平文データ／暗号文データＩはデータ変換回路Ｃによって演算が行われ、演算結果が暗号文データ／平文データＯとして出力される。これによりデータ変換処理が完了する。
【００５７】
一方、データ変換の処理単位を大きくとりたい場合は、外部からＷ０＝０，Ｗ１＝０，Ｗ２＝１を制約条件Ｗとして制御部Ｘに入力し、鍵データＫとして８ビットの値を制御部Ｘに入力する。この場合、制約条件Ｗの意味から、制御部Ｘは▲１▼１回の状態遷移演算をパイプライン処理の単位とする、▲２▼状態遷移規則が１つ、▲３▼セル数が８のセルラーオートマトンの状態遷移演算を行う、ようなデータ変換回路Ｃの構成データＹを生成する。
【００５８】
例えば、制御部Ｘは鍵データＫの各ビットＫｉ（０≦ｉ＜８）の値に応じてｉ番目のセルの状態遷移規則πｉを次の
2005018310.tif 000013
のように生成するとする。
【００５９】
制御部Ｘはこの状態遷移１回をパイプライン処理の単位として構成するデータ変換回路Ｃの構成データＹを生成する。データ変換回路Ｃを決定するには鍵データＫから生成した状態遷移規則によるセルラーオートマトンの状態遷移周期を求める必要がある。式９で表わされるセルラーオートマトンの場合、あるｊ（０≦ｊ＜８）において、ｊ≦ｉ＜ｊ＋ａの範囲で常にＫｉ＝１である、という性質を満たすａの集合のうち最大の要素をＬとし、ｒを２（ｒ−１）−１＜Ｌ≦２ｒ−１を満たす整数とすると、状態遷移周期は２ｒとなる、という性質があるため（参考文献１）、これを利用して算出する。例えば、Ｋ７＝１，Ｋ６＝１，Ｋ５＝１，Ｋ４＝１，Ｋ３＝１，Ｋ２＝１，Ｋ１＝１，Ｋ０＝１である場合、連続してＫｉ＝１となるｉの数は８が最大であるため、Ｌ＝８である。従って、ｒ＝４となり、状態遷移周期は２ｒ＝１６となる。
【００６０】
以上から、制御部Ｘはデータ変換回路Ｃを図１５のように構成する。データ変換回路Ｃは平文データ／暗号文データＩを入力として受信し、暗号文データ／平文データＯを出力する。この例の場合、データ変換に利用する状態遷移規則は１つなので、データ変換回路Ｃは置換演算ユニットＴ０の１つから構成される。そして、状態遷移周期が１６であるため、置換演算ユニットＴ０は８つの状態遷移演算ユニットＳ００，Ｓ０１，Ｓ０２，Ｓ０３，Ｓ０４，Ｓ０５，Ｓ０６，Ｓ０７をパイプライン状に接続した構成となっている。各状態遷移演算ユニットは状態遷移を計算する論理回路と、計算結果を記憶する１ビット記憶素子から構成される。例えば、状態遷移演算ユニットＳ００では８つのＸＮＯＲ回路と８つの１ビット記憶素子ｍ００，ｍ０１，ｍ０２，ｍ０３，ｍ０４，ｍ０５，ｍ０６，ｍ０７から構成される。
【００６１】
制御部Ｘは図１５のようなデータ変換回路Ｃを表す構成データＹを生成し、再構成可能ハードウェアＤに送信する。構成可能ハードウェアＤは構成データＹを受信すると、構成データＹに従って再構成可能ハードウェアＤ上にデータ変換回路Ｃに相当する回路を設定し、データ変換回路Ｃが回路として動作する状態になる。
【００６２】
データ変換回路Ｃの構成が終了した後、制御部Ｘは平文データ／暗号文データＩを８ビット単位でデータ変換部Ｒに送信するように外部に指示する。これによって外部から平文データ／暗号文データＩが送信され、送信された平文データ／暗号文データＩはデータ変換回路Ｃによって演算が行われ、演算結果が暗号文データ／平文データ０として出力される。これによりデータ変換処理が完了する。
【００６３】
＜暗号強度を変更する実施例＞
暗号強度を変更する場合はＷ１，Ｗ２を変更する。例えば、低い暗号強度で良い場合には、外部からＷ０＝０、Ｗ１＝０、Ｗ２＝０を制約条件Ｗとして制御部Ｘに入力し、鍵データＫとして４ビットの値を制御部Ｘに入力する。この場合、制約条件Ｗの意味から、制御部Ｘは▲１▼１回の状態遷移演算をパイプライン処理の単位とする、▲２▼状態遷移規則が１つ、▲３▼セル数が４のセルラーオートマトンの状態遷移演算を行う、ようなデータ変換回路Ｃの構成データＹを生成する。
【００６４】
例えば、制御部Ｘは鍵データＫの各ビットＫｉ（０≦ｉ＜４）の値に応じてｉ番目のセルの状態遷移規則πｉを次の
2005018310.tif 000014
のように生成するとする。
【００６５】
制御部Ｘはこの状態遷移１回をパイプライン処理の単位として構成するデータ変換回路Ｃの構成データＹを生成する。データ変換回路Ｃを決定するには鍵データＫから生成した状態遷移規則によるセルラーオートマトンの状態遷移周期を求める必要がある。式１０で表わされるセルラーオートマトンの場合、あるｊ（０≦ｊ＜４）において、ｊ≦ｉ＜ｊ＋ａの範囲で常にＫｉ＝１である、という性質を満たすａの集合のうち最大の要素をＬとし、ｒを２（ｒ−１）−１＜Ｌ≦２ｒ−１を満たす整数とすると、状態遷移周期は２ｒとなる、という性質があるため（参考文献１）、これを利用して算出する。例えば、Ｋ３＝１，Ｋ２＝１，Ｋ１＝１，Ｋ０＝１である場合、連続してＫｉ＝１となるｉの数は４が最大であるため、Ｌ＝４である。従って、ｒ＝３となり、状態遷移周期は２ｒ＝８となる。
【００６６】
以上から、制御部Ｘはデータ変換回路Ｃを図１６のように構成する。データ変換回路Ｃは平文データ／暗号文データＩを入力として受信し、暗号文データ／平文データＯを出力する。この例の場合、データ変換に利用する状態遷移規則は１つなので、データ変換回路Ｃは置換演算ユニットＴ０の１つから構成される。そして、状態遷移周期が８であるため、置換演算ユニットＴ０は４つの状態遷移演算ユニットＳ００，Ｓ０１，Ｓ０２，Ｓ０３をパイプライン状に接続した構成となっている。各状態遷移演算ユニットは状態遷移を計算する論理回路と、計算結果を記憶する１ビット記憶素子から構成される。例えば、状態遷移演算ユニットＳ００では４つのＸＮＯＲ回路と４つの１ビット記憶素子ｍ００，ｍ０１，ｍ０２，ｍ０３から構成される。
【００６７】
制御部Ｘは図１６のようなデータ変換回路Ｃを表す構成データＹを生成し、再構成可能ハードウェアＤに送信する。再構成可能ハードウェアＤは構成データＹを受信すると、構成データＹに従って再構成可能ハードウェアＤ上にデータ変換回路Ｃに相当する回路を設定し、データ変換回路Ｃが回路として動作する状態になる。
【００６８】
データ変換回路Ｃの構成が終了した後、制御部Ｘは平文データ／暗号文データＩを４ビット単位でデータ変換部Ｒに送信するように外部に指示する。これによって外部から平文データ／暗号文データＩが送信され、送信された平文データ／暗号文データＩはデータ変換回路Ｃによって演算が行われ、演算結果が暗号文データ／平文データＯとして出力される。これによりデータ変換処理が完了する。
【００６９】
一方、高い暗号強度が要求される場合には、外部からＷ０＝０，Ｗ１＝１，Ｗ２＝１を制約条件Ｗとして制御部Ｘに入力し、鍵データＫとして１６ビットの値を制御部Ｘに入力する。この場合、制約条件Ｗの意味から、制御部Ｘは▲１▼１回の状態遷移演算をパイプライン処理の単位とする、▲２▼状態遷移規則が２つ、▲３▼セル数が８のセルラーオートマトンの状態遷移演算を行う、ようなデータ変換回路Ｃの構成データＹを生成する。
【００７０】
例えば、制御部Ｘは鍵データＫの各ビットＫｉ（０≦ｉ＜１６）の値に応じてＫｉ（０≦ｉ＜８）では１つめの状態遷移規則Π０のｉ番目のセルの状態遷移規則πｉを次の
2005018310.tif 000015
のように生成するとする。
【００７１】
また、Ｋｉ（８≦ｉ＜１６）では２つめの状態遷移規則Π１のｉ−８番目のセルの状態遷移規則πｉ−８を次の
2005018310.tif 000016
のように生成するとする。
【００７２】
制御部Ｘはこの状態遷移１回をパイプライン処理の単位として構成するデータ変換回路Ｃの構成データＹを生成する。データ変換回路Ｃを決定するには鍵データＫから生成した状態遷移規則によるセルラーオートマトンの状態遷移周期を求める必要がある。式１１、式１２で表わされるセルラーオートマトンの場合、式１１、式１２の状態遷移規則それぞれについて、あるｊ（０≦ｊ＜８）において、ｊ≦ｉ＜ｊ＋ａの範囲で常にＫｉ＝１である、という性質を満たすａの集合のうち最大の要素をＬとし、ｒを２（ｒ−１）−１＜Ｌ≦２ｒ−１を満たす整数とすると、状態遷移周期は２ｒとなる、という性質があるため（参考文献１）、これを利用して状態遷移周期を算出する。例えば、Ｋｉ＝１（０≦ｉ＜１６）の場合、１つめの状態遷移規則Π０では連続してＫｉ＝１となるｉの数は８が最大であるため、Ｌ＝８である。従って、ｒ＝４となり、Π０の状態遷移周期は１６となる。また、２つめの状態遷移親則Π１では連続してＫｉ＝１となるｉの数は８が最大であるため、Ｌ＝８である。従ってｒ＝４となり、Π１の状態遷移周期は１６となる。
【００７３】
以上から、制御部Ｘはデータ変換回路Ｃを図１７のように構成する。データ変換回路Ｃは平文データ／暗号文データＩを入力として受信し、暗号文データ／平文データＯを出力する。この例の場合、データ変換に利用する状態遷移規則は２つなので、データ変換回路Ｃは置換演算ユニットＴ０，Ｔ１から構成される。そして、それぞれの状態遷移規則における状態遷移周期が１６であるため、置換演算ユニットＴ０は８つの状態遷移演算ユニットＳ００，Ｓ０１，Ｓ０２，Ｓ０３，Ｓ０４，Ｓ０５，Ｓ０６，Ｓ０７をパイプライン状に接続した構成に、置換演算ユニットＴ１は８つの状態遷移演算ユニットＳ１０，Ｓ１１，Ｓ１２，Ｓ１３，Ｓ１４，Ｓ１５，Ｓ１６，Ｓ１７をパイプライン状に接続した構成に、それぞれなっている。各状態遷移演算ユニットは状態遷移を計算する論理回路と、計算結果を記憶する１ビット記憶素子から構成される。例えば、状態遷移演算ユニットＳ００では８つのＸＮＯＲ回路と８つの１ビット記憶素子ｍ００，ｍ０１，ｍ０２，ｍ０３，ｍ０４，ｍ０５，ｍ０６，ｍ０７から構成される。
【００７４】
制御部Ｘは図１７のようなデータ変換回路Ｃを表す構成データＹを生成し、再構成可能ハードウェアＤに送信する。再構成可能ハードウェアＤは構成データＹを受信すると、構成データＹに従って再構成可能ハードウェアＤ上にデータ変換回路Ｃに相当する回路を設定し、データ変換回路Ｃが回路として動作する状態になる。
【００７５】
データ変換回路Ｃの構成が終了した後、制御部Ｘは平文データ／暗号文データＩを８ビット単位でデータ変換部Ｒに送信するように外部に指示する。これによって外部から平文データ／暗号文データＩが送信され、送信された平文データ／暗号文データＩはデータ変換回路Ｃによって演算が行われ、演算結果が暗号文データ／平文データＯとして出力される。これによりデータ変換処理が完了する。
【００７６】
図１６のデータ変換回路Ｃが４ビットのセルラーオートマトンの状態遷移規則を１つだけ使用して暗号化を行うのに対し、図１７のデータ変換回路Ｃは８ビットのセルラーオートマトンの状態遷移規則を２つ使用して暗号化を行うため、後者のほうがより暗号強度が高くなる。
【００７７】
＜処理スループットを変更する実施例＞
処理スループットを変更する場合はＷ０を変更する。例えば、低い処理スループットで良い場合には、外部からＷ０＝１、Ｗ１＝０、Ｗ２＝０を制約条件Ｗとして制御部Ｘに入力し、鍵データＫとして４ビットの値を制御部Ｘに入力する。この場合、制約条件Ｗの意味から、制御部Ｘは▲１▼２回の状態遷移演算をパイプライン処理の単位とする、▲２▼状態遷移規則が１つ、▲３▼セル数が４のセルラーオートマトンの状態遷移演算を行う、ようなデータ変換回路Ｃの構成データＹを生成する。
【００７８】
例えば、制御部ＸはＫの各ビットＫｉ（０≦ｉ＜４）の値に応じてｉ番目のセルの状態遷移規則πｉを次の
2005018310.tif 000017
のように生成するとする。
【００７９】
制御部Ｘはこの状態遷移２回をパイプライン処理の単位として構成するデータ変換回路Ｃの構成データＹを生成する。データ変換回路Ｃを決定するには鍵データＫから生成した状態遷移規則によるセルラーオートマトンの状態遷移周期を求める必要がある。式１３で表わされるセルラーオートマトンの場合、あるｊ（０≦ｊ＜４）において、ｊ≦ｉ＜ｊ＋ａの範囲で常にＫｉ＝１である、という性質を満たすａの集合のうち最大の要素をＬとし、ｒを２（ｒ−１）−１＜Ｌ≦２ｒ−１を満たす整数とすると、状態遷移周期は２ｒとなる、という性質があるため（参考文献１）、これを利用して算出する。例えば、Ｋ３＝１、Ｋ２＝１、Ｋ１＝１、Ｋ０＝１である場合、連続してＫｉ＝１となるｉの数は４が最大であるため、Ｌ＝４である。従って、ｒ＝３となり、状態遷移周期は２ｒ＝８となる。
【００８０】
以上から、データ変換回路Ｃは図１８のようになるため、制御部Ｘはこれを表す構成データＹを生成し、再構成可能ハードウェアＤに送信する。再構成可能ハードウェアＤは構成データＹを受信すると、構成データＹに従って再構成可能ハードウェアＤ上にデータ変換回路Ｃに相当する回路を設定し、データ変換回路Ｃが回路として動作する状態になる。
【００８１】
データ変換回路Ｃの構成が終了した後、制御部Ｘは平文データ／暗号文データＩを４ビット単位でデータ変換部Ｒに送信するように外部に指示する。これによって外部から平文データ／暗号文データＩが送信され、送信された平文データ／暗号文データＩはデータ変換回路Ｃによって演算が行われ、演算結果が暗号文データ／平文データＯとして出力される。これによりデータ変換処理が完了する。
【００８２】
一方、高い処理スループットが要求される場合には、外部からＷ０＝０、Ｗ１＝０、Ｗ２＝０を制約条件Ｗとして制御部Ｘに入力し、鍵データＫとして４ビットの値を制御部Ｘに入力する。
【００８３】
この場合、制約条件Ｗの意味から、制御部Ｘは▲１▼１回の状態遷移演算をパイプライン処理の単位とする、▲２▼状態遷移規則が１つ、▲３▼セル数が４のセルラーオートマトンの状態遷移演算を行う、ようなデータ変換回路Ｃの構成データＹを生成する。
【００８４】
例えば、制御部ＸはＫの各ビットＫｉ（０≦ｉ＜４）の値に応じてｉ番目のセルの状態遷移規則πｉを次の
2005018310.tif 000018
のように生成するとする。
【００８５】
制御部Ｘはこの状態遷移１回をパイプライン処理の単位として構成するデータ変換回路Ｃの構成データＹを生成する。データ変換回路Ｃを決定するには鍵データＫから生成した状態遷移規則によるセルラーオートマトンの状態遷移周期を求める必要がある。式１４で表わされるセルラーオートマトンの場合、あるｊ（０≦ｊ＜４）において、ｊ≦ｉ＜ｊ＋ａの範囲で常にＫｉ＝１である、という性質を満たすａの集合のうち最大の要素をＬとし、ｒを２（ｒ−１）−１＜Ｌ≦２ｒ−１を満たす整数とすると、状態遷移周期は２ｒとなる、という性質があるため（参考文献１）、これを利用して算出する。例えば、Ｋ３＝１，Ｋ２＝１，Ｋ１＝１，Ｋ０＝１である場合、連続してＫｉ＝１となるｉの数は４が最大であるため、Ｌ＝４である。従って、ｒ＝３となり、状態遷移周期は２ｒ＝８となる。
【００８６】
以上から、データ変換回路Ｃは図１９のようになるため、制御部Ｘはこれを表す構成データＹを生成し、再構成可能ハードウェアＤに送信する。再構成可能ハードウェアＤは構成データＹを受信すると、構成データＹに従って再構成可能ハードウェアＤ上にデータ変換回路Ｃに相当する回路を設定し、データ変換回路Ｃが回路として動作する状態になる。
【００８７】
データ変換回路Ｃの構成が終了した後、制御部Ｘは平文データ／暗号文データＩを４ビット単位でデータ変換部Ｒに送信するように外部に指示する。これによって外部から平文データ／暗号文データＩが送信され、送信された平文データ／暗号文データＩはデータ変換回路Ｃによって演算が行われ、演算結果が暗号文データ／平文データＯとして出力される。これによりデータ変換処理が完了する。
【００８８】
図１８のデータ変換回路Ｃは状態遷移の演算２回をパイプライン処理の単位とするのに対し、図１９のデータ変換回路Ｃは状態遷移の演算１回をパイプライン処理の単位とするため、後者のほうがより処理スループットを高くすることが可能である。
【００８９】
＜消費電力を変更する実施例＞
消費電力を変更する場合はＷ０を変更する。例えば、消費電力を低く抑える場合には、外部からＷ０＝１，Ｗ１＝０，Ｗ２＝０を制約条件Ｗとして制御部Ｘに入力し、鍵データＫとして４ビットの値を制御部Ｘに入力する。この場合、制約条件Ｗの意味から、制御部Ｘは▲１▼２回の状態遷移演算をパイプライン処理の単位とする、▲２▼状態遷移規則が１つ、▲３▼セル数が４のセルラーオートマトンの状態遷移演算を行う、ようなデータ変換回路Ｃの構成データＹを生成する。
【００９０】
例えば、制御部Ｘは鍵データＫの各ビットＫｉ（０≦ｉ＜４）の値に応じてｉ番目のセルの状態遷移規則πｉを次の
2005018310.tif 000019
のように生成するとする。
【００９１】
制御部Ｘはこの状態遷移２回をパイプライン処理の単位として横成するデータ変換回路Ｃの構成データＹを生成する。データ変換回路Ｃを決定するには鍵データＫから生成した状態遷移規則によるセルラーオートマトンの状態遷移周期を求める必要がある。式１５で表わされるセルラーオートマトンの場合、あるｊ（０≦ｊ＜４）において、ｊ≦ｉ＜ｊ＋ａの範囲で常にＫｉ＝１である、という性質を満たすａの集合のうち最大の要素をＬとし、ｒを２（ｒ−１）−１＜Ｌ≦２ｒ−１を満たす整数とすると、状態遷移周期は２ｒとなる、という性質があるため（参考文献１）、これを利用して算出する。例えば、Ｋ３＝１，Ｋ２＝１，Ｋ１＝１，Ｋ０＝１である場合、連続してＫｉ＝１となるｉの数は４が最大であるため、Ｌ＝４である。従って、ｒ＝３となり、状態遷移周期は２ｒ＝８となる。
【００９２】
以上から、データ変換回路Ｃは図２０のようになるため、制御部Ｘはこれを表す構成データＹを生成し、再構成可能ハードウェアＤに送信する。再構成可能ハードウェアＤは構成データＹを受信すると、構成データＹに従って再構成可能ハードウェアＤ上にデータ変換回路Ｃに相当する回路を設定し、データ変換回路Ｃが回路として動作する状態になる。
【００９３】
データ変換回路Ｃの構成が終了した後、制御部Ｘは平文データ／暗号文データＩを４ビット単位でデータ変換部Ｒに送信するように外部に指示する。これによって外部から平文データ／暗号文データＩが送信され、送信された平文データ／暗号文データＩはデータ変換回路Ｃによって演算が行われ、演算結果が暗号文データ／平文データＯとして出力される。これによりデータ変換処理が完了する。
【００９４】
一方、消費電力を多くとれる場合には、外部からＷ０＝０，Ｗ１＝０，Ｗ２＝０を制約条件Ｗとして制御部Ｘに入力し、鍵データＫとして４ビットの値を制御部Ｘに入力する。この場合、制約条件Ｗの意味から、制御部Ｘは▲１▼１回の状態遷移演算をパイプライン処理の単位とする、▲２▼状態遷移規則が１つ、▲３▼セル数が４のセルラーオートマトンの状態遷移演算を行う、ようなデータ変換回路Ｃの構成データＹを生成する。
【００９５】
例えば、制御部Ｘは鍵データＫの各ビットＫｉ（０≦ｉ＜４）の値に応じてｉ番目のセルの状態遷移規則πｉを次の
2005018310.tif 000020
のように生成するとする。
【００９６】
制御部Ｘはこの状態遷移１回をパイプライン処理の単位として構成するデータ変換回路Ｃの構成データＹを生成する。データ変換回路Ｃを決定するには鍵データＫから生成した状態遷移規則によるセルラーオートマトンの状態遷移周期を求める必要がある。式１６で表わされるセルラーオートマトンの場合、あるｊ（０≦ｊ＜４）において、ｊ≦ｉ＜ｊ＋ａの範囲で常にＫｉ＝１である、という性質を満たすａの集合のうち最大の要素をＬとし、ｒを２（ｒ−１）−１＜Ｌ≦２ｒ−１を満たす整数とすると、状態遷移周期は２ｒとなる、という性質があるため（参考文献１）、これを利用して算出する。例えば、Ｋ３＝１，Ｋ２＝１，Ｋ１＝１，Ｋ０＝１である場合、連続してＫｉ＝１となるｉの数は４が最大であるため、Ｌ＝４である。従って、ｒ＝３となり、状態遷移周期は２ｒ＝８となる。
【００９７】
以上から、データ変換回路Ｃは図２１のようになるため、制御部Ｘはこれを表す構成データＹを生成し、再構成可能ハードウェアＤに送信する。再構成可能ハードウェアＤは構成データＹを受信すると、構成データＹに従って再構成可能ハードウェアＤ上にデータ変換回路Ｃに相当する回路を設定し、データ変換回路Ｃが回路として動作する状態になる。
【００９８】
データ変換回路Ｃの構成が終了した後、制御部Ｘは平文データ／暗号文データＩを４ビット単位でデータ変換部Ｒに送信するように外部に指示する。これによって外部から平文データ／暗号文データＩが送信され、送信された平文データ／暗号文データＩはデータ変換回路Ｃによって演算が行われ、演算結果が暗号文データ／平文データＯとして出力される。これによりデータ変換処理が完了する。
【００９９】
図２０のデータ変換回路Ｃは４ビットのセルラーオートマトンの状態遷移を２回の状態遷移を単位としたパイプライン処理により行うのに対し、図２１のデータ変換回路Ｃは４ビットのセルラーオートマトンの状態遷移を１回の状態遷移を単位としたパイプライン処理により行うため、前者のほうが実現に必要な回路規模が小さくなり、結果として処理に必要な消費電力を小さく抑えることが可能である。
【０１００】
＜その他の実施例＞
第３の実施形態における各実施例はデータ変換の処理単位、暗号強度、処理スループット、消費電力の各要求に応じて２つの回路の選択肢を用意し、制約条件Ｗにより制御部Ｘがデータ変換回路Ｃを選択する形式となっているが、データ変換回路Ｃの実現の原理から、より細かい条件によるデータ変換回路Ｃの実現形態の制御が可能であることは容易に推測可能である。
【０１０１】
以上のように、データ変換の処理単位、要求暗号強度、要求処理スループット、要求消費電力に応じて制約条件Ｗを制御部Ｘに入力し、制御部Ｘが制約条件Ｗに応じたデータ変換回路Ｃを構成し、その構成データＹにより再構成可能ハードウェアＤ上にデータ変換回路Ｃを設定すれば、要求された制約条件Ｗに応じた適切な実現形態でデータ変換処理が可能になるという利点がある。
【０１０２】
【発明の効果】
本発明により、実行時にデータ変換の処理スループットを保ったままデータ変換の複雑度を向上させることが可能となる。また、実行時の環境の制約条件に応じて処理スループットを動的に調整しながらデータ変換処理が可能となる。
【図面の簡単な説明】
【図１】第１の実施形態のデータ暗号化／復号化装置のブロック図である。
【図２】セルラーオートマトンの状態遷移規則の計算を行う回路図である。
【図３】セルラーオートマトンの系全体の状態遷移の説明図である。
【図４】再構成可能ハードウェア上に実現するセルラーオートマトンによるデータ変換回路の回路図である。
【図５】第２の実施形態のデータ変換回路Ｃのブロック図である。
【図６】図５のデータ変換回路Ｃを構成する置換演算ユニットのブロック図である。
【図７】図６の置換演算ユニットを構成する状態遷移演算ユニットのブロック図である。
【図８】セルラーオートマトンの系全体の状態遷移の説明図である。
【図９】データ変換回路Ｃの具体的な一例の回路図である。
【図１０】データ変換回路Ｃの具体的な別の一例の回路図である。
【図１１】第３の実施形態のデータ暗号化／復号化装置のブロック図である。
【図１２】一段のパイプラインでセルラーオートマトンの状態遷移を１回計算する実施例の回路図である。
【図１３】一段のパイプラインでセルラーオートマトンの状態遷移を２回計算する実施例の回路図である。
【図１４】データ変換の処理単位を４ビットとした場合のデータ変換回路Ｃの具体的な一例の回路図である。
【図１５】データ変換の処理単位を８ビットとした場合のデータ変換回路Ｃの具体的な一例の回路図である。
【図１６】暗号強度をそれほど必要としない場合のデータ変換回路Ｃの具体的な一例の回路図である。
【図１７】暗号強度を必要とする場合のデータ変換回路Ｃの具体的な構成の一例の回路図である。
【図１８】スループットを要求されない場合のデータ変換回路Ｃの具体的な一例の回路図である。
【図１９】スループットを要求される場合のデータ変換回路Ｃの具体的な一例の回路図である。
【図２０】消費電力を抑えたい場合のデータ変換回路Ｃの具体的な一例の回路図である。
【図２１】消費電力を抑えない場合のデータ変換回路Ｃの具体的な一例の回路図である。
【図２２】従来のセルラーオートマトンの基本構成のブロック図である。
【図２３】セルラーオートマトンの系全体の状態遷移の説明図である。
【図２４】セルラーオートマトンを利用した暗号化／復号化方式のソフトウェアによる実現例を説明するためのフローチャートである。
【図２５】セルラーオートマトンを利用した暗号化／復号化方式の専用ハードウェアによる実現例を説明するためのブロック図である。
【図２６】図２５における制御部Ｘ０の制御のフローチャートである。
【符号の説明】
Ｘ，Ｘ０：制御部、Ｋ：鍵データ、Ｒ，Ｒ０：データ変換部、Ｃ：データ変換回路、Ｄ：再構成可能ハードウェア、Ｙ：構成データ、Ｗ：制約条件、ＲＡＭ：演算定義メモリ、ＡＰ：アドレスポート、ＤＰ：データポート、ＡＢ：アドレスバス、ＤＢ：データバス、Ｍ：セル状態保持メモリ
【図１】
2005018310.tif 000021
【図２】
2005018310.tif 000022
【図３】
2005018310.tif 000023
【図４】
2005018310.tif 000024
【図５】
2005018310.tif 000025
【図６】
2005018310.tif 000026
【図７】
2005018310.tif 000027
【図８】
2005018310.tif 000028
【図９】
2005018310.tif 000029
【図１０】
2005018310.tif 000030
【図１１】
2005018310.tif 000031
【図１２】
2005018310.tif 000032
【図１３】
2005018310.tif 000033
【図１４】
2005018310.tif 000034
【図１５】
2005018310.tif 000035
【図１６】
2005018310.tif 000036
【図１７】
2005018310.tif 000037
【図１８】
2005018310.tif 000038
【図１９】
2005018310.tif 000039
【図２０】
2005018310.tif 000040
【図２１】
2005018310.tif 000041
【図２２】
2005018310.tif 000042
【図２３】
2005018310.tif 000043
【図２４】
2005018310.tif 000044
【図２５】
2005018310.tif 000045
【図２６】
2005018310.tif 000046