(57)【特許請求の範囲】
【請求項１】
ステージＸ及び前記ステージＸの次のステージであるステージＹを少なくとも含む、複数のステージのパイプライン処理によって符号化処理を行う符号化回路であって、
前記複数のステージの各々は、符号化処理の一部である部分符号化処理及び該一部の逆処理となる部分復号処理を実行しうる部分符号化・部分復号ブロックを含み、
或るサイクルにおいて、
・  前記ステージＹにおいて、前記或るサイクルの１つ前のサイクルにおいて前記ステージＸで部分符号化されたデータが部分符号化され、
・  前記ステージＸにおいて、前記１つ前のサイクルにおいて前記ステージＸで部分符号化されたデータが部分復号され、
・  予め記憶されていた、前記１つ前のサイクルにおいて前記ステージＸで部分符号化される前のデータと、前記部分復号されたデータとが比較され、
前記或るサイクルの次のサイクルにおいて、
・  前記ステージＹにおいて、前記或るサイクルにおいて前記ステージＹで部分符号化されたデータが部分復号され、
・  予め記憶されていた、前記或るサイクルにおいて前記ステージＹで部分符号化される前のデータと、前記ステージＹで部分復号されたデータとが比較され、
・  前記ステージＸにおいて、別のデータが部分符号化される、
ように構成される、符号化回路。
【請求項２】
ステージＸ及び前記ステージＸの次のステージであるステージＹを少なくとも含む、複数のステージのパイプライン処理によって復号処理を行う復号回路であって、
前記複数のステージの各々は、復号処理の一部である部分復号処理及び該一部の逆処理となる部分符号化処理を実行しうる部分符号化・部分復号ブロックを含み、
或るサイクルにおいて、
・  前記ステージＹにおいて、前記或るサイクルの１つ前のサイクルにおいて前記ステージＸで部分復号されたデータが部分復号され、
・  前記ステージＸにおいて、前記１つ前のサイクルにおいて前記ステージＸで部分復号されたデータが部分符号化され、
・  予め記憶されていた、前記１つ前のサイクルにおいて前記ステージＸで部分復号される前のデータと、前記部分符号化されたデータとが比較され、
前記或るサイクルの次のサイクルにおいて、
・  前記ステージＹにおいて、前記或るサイクルにおいて前記ステージＹで部分復号されたデータが部分符号化され、
・  予め記憶されていた、前記或るサイクルにおいて前記ステージＹで部分復号される前のデータと、前記ステージＹで部分符号化されたデータとが比較され、
・  前記ステージＸにおいて、別のデータが部分復号される、
ように構成される、復号回路。
【請求項３】
前記ステージＸが、暗号化において反復実行されるランダム化関数の一部である部分暗号化処理及び該一部の逆関数となる部分復号処理を実行しうる部分暗号化・部分復号ブロックを含み、前記ステージＹが、前記ランダム化関数の残部である部分暗号化処理及び該残部の逆関数である部分復号処理を実行しうる部分暗号化・部分復号処理ブロックを含む、請求項１に記載の符号化回路。
【請求項４】
前記ステージＸが、復号において反復実行されるランダム化関数の一部である部分復号処理及び該一部の逆関数となる部分暗号化処理を実行しうる部分復号・部分暗号化ブロックを含み、前記ステージＹが、前記ランダム化関数の残部である部分復号処理及び該残部の逆関数である部分暗号化処理を実行しうる部分復号・暗号化処理ブロックを含む、請求項１に記載の復号回路。
【請求項５】
（ａ）  符号化処理をＮステージ（Ｎは２以上の整数）のパイプライン処理で行う符号化回路であって、
（ｂ）  各ステージは、符号化処理の一部である部分符号化処理及び該一部の逆処理となる部分復号処理を実行しうる部分符号化・部分復号ブロックを含み、
（ｃ）  前記部分符号化・部分復号ブロックの各々に対し、該部分符号化・部分復号ブロックの部分符号化処理の結果をストアするためのレジスタである第１レジスタと、該部分符号化・部分復号ブロックへの入力データのコピーをストアするためのレジスタである第２レジスタと、比較器とが割り当てられ、
（ｄ）  ｉ番目（２≦ｉ≦Ｎ）の前記部分符号化・部分復号ブロックによる部分符号化処理が行われるサイクルにおいて、
（ｄ−１）  ｉ−１番目の前記部分符号化・部分復号ブロックに関する前記第１レジスタにストアされたデータを入力データとして、前記ｉ番目の部分符号化・部分復号ブロックによる部分符号化処理が実行され、
（ｄ−２）  前記部分符号化処理を施されたデータが、前記サイクルの次のサイクルにおいて、前記ｉ番目の部分符号化・部分復号ブロックに関する前記第１レジスタにストアされるように準備され、
（ｄ−３）  前記入力データが、前記次のサイクルにおいて、前記ｉ番目の部分符号化・部分復号ブロックに関する前記第２レジスタにストアされるように準備され、
（ｄ−４）  前記ｉ−１番目の前記部分符号化・部分復号ブロックに関する前記第１レジスタにストアされたデータに対し、前記ｉ−１番目の部分符号化・部分復号ブロックによる部分復号処理が実行され、
（ｄ−５）  前記部分復号処理を施されたデータと、前記ｉ−１番目の部分符号化・部分復号ブロックに関する前記第２レジスタにストアされたデータとの比較処理が、前記ｉ−１番目の部分符号化・部分復号ブロックに関する前記比較器による実行され、
（ｅ）  前記次のサイクルにおいて、
（ｅ−１）  前記ｉ番目の部分符号化・部分復号ブロックに関する前記第１及び第２レジスタに対するストア処理が実行され、
（ｅ−２）  前記ｉ番目の部分符号化・部分復号ブロックに関する前記第１レジスタにストアされたデータに対し、前記ｉ番目の部分符号化・部分復号ブロックによる部分復号処理が実行され、
（ｅ−３）  前記（ｅ−２）における部分復号処理を施されたデータと、前記ｉ番目の部分符号化・部分復号ブロックに関する前記第２レジスタにストアされたデータとの比較処理が、前記ｉ番目の部分符号化・部分復号ブロックに関する前記比較器によって実行され、
（ｅ−４）  別のデータに対して前記ｉ−１番目の部分符号化・部分復号ブロックによる部分符号化処理が実行され、
るように構成される、符号化回路。
【請求項６】
（ａ）  復号処理をＮステージ（Ｎは２以上の整数）のパイプライン処理で行う復号回路であって、
（ｂ）  各ステージは、復号処理の一部である部分復号処理及び該一部の逆処理となる部分符号化処理を実行しうる部分符号化・部分復号ブロックを含み、
（ｃ）  前記部分符号化・部分復号ブロックの各々に対し、該部分符号化・部分復号ブロックの部分復号処理の結果をストアするためのレジスタである第１レジスタと、該部分符号化・部分復号ブロックへの入力データのコピーをストアするためのレジスタである第２レジスタと、比較器とが割り当てられ、
（ｄ）  ｉ番目（２≦ｉ≦Ｎ）の前記部分符号化・部分復号ブロックによる部分復号処理が行われるサイクルにおいて、
（ｄ−１）  ｉ−１番目の前記部分符号化・部分復号ブロックに関する前記第１レジスタにストアされたデータを入力データとして、前記ｉ番目の部分符号化・部分復号ブロックによる部分復号処理が実行され、
（ｄ−２）  前記部分復号処理を施されたデータが、前記サイクルの次のサイクルにおいて前記ｉ番目の部分符号化・部分復号ブロックに関する前記第１レジスタにストアされるように準備され、
（ｄ−３）  前記入力データが、前記次のサイクルにおいて前記ｉ番目の部分符号化・部分復号ブロックに関する前記第２レジスタにストアされるように準備され、
（ｄ−４）  ｉ−１番目の前記部分符号化・部分復号ブロックに関する前記第１レジスタにストアされたデータに対し、前記ｉ−１番目の部分符号化・部分復号ブロックによる部分符号化処理が実行され、
（ｄ−５）  前記部分符号化処理を施されたデータと、前記ｉ−１番目の部分符号化・部分復号ブロックに関する前記第２レジスタにストアされたデータとの比較処理が、前記ｉ−１番目の部分符号化・部分復号ブロックに関する前記比較器によって実行され、
（ｅ）  前記次のサイクルにおいて、
（ｅ−１）  前記ｉ番目の部分符号化・部分復号ブロックに関する前記第１及び第２レジスタに対するストア処理が実行され、
（ｅ−２）  前記ｉ番目の部分符号化・部分復号ブロックに関する前記第１レジスタにストアされたデータに対し、前記ｉ番目の部分符号化・部分復号ブロックによる部分符号化処理が実行され、
（ｅ−３）  前記（ｅ−２）における部分符号化処理を施されたデータと、前記ｉ番目の部分符号化・部分復号ブロックに関する前記第２レジスタにストアされたデータとの比較処理が、前記ｉ番目の部分符号化・部分復号ブロックに関する前記比較器によって実行され、
（ｅ−４）  別のデータに対して前記ｉ−１番目の部分符号化・部分復号ブロックによる部分復号処理が実行され、
るように構成される、復号回路。
【請求項７】
前記第１レジスタ、前記第２レジスタ、前記比較器の少なくとも１つ以上が、２つの前記部分符号化・部分復号ブロックによって共有されるように構成される、請求項５に記載の符号化回路。
【請求項８】
前記第１レジスタ、前記第２レジスタ、前記比較器の少なくとも１つ以上が、２つの前記部分符号化・部分復号ブロックによって共有されるように構成される、請求項６に記載の復号回路。
【請求項９】
請求項１，３，５，７のいずれかに記載の符号化回路を含む、半導体チップ。
【請求項１０】
請求項１，３，５，７のいずれかに記載の符号化回路を含む、電子機器。
【請求項１１】
請求項２，４，６，８のいずれかに記載の復号回路を含む、半導体チップ。
【請求項１２】
請求項２，４，６，８のいずれかに記載の復号回路を含む、電子機器。
【請求項１３】
プログラマブルロジックデバイスを請求項１，３，５，７のいずれかに記載の符号化回路に構成する、プログラム。
【請求項１４】
プログラマブルロジックデバイスを請求項２，４，６，８のいずれかに記載の復号回路に構成する、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化・復号処理のための回路構成であって、誤り検出能力を有する新規な回路構成に関するものである。
【背景技術】
【０００２】
VLSIの高速化・高集積化技術の進歩による情報機器の高性能化と、ブロードバンド・ネットワークの急速な普及にともなって、業務だけでなく日常生活のあらゆる場面で大量のデータをやりとりするようになっている。データバンド幅の拡大や記憶デバイス容量の削減のためにはデータ圧縮技術が用いられ、また誤り検出・訂正符号や暗号技術によって、情報の信頼性と通信の安全性の確保が行われている。データ圧縮技術は音声画像といったデジタルコンテンツへの利用が盛んであるが、このようなデータは多少のエラーが発生しても大きな問題とならず機密性も低い場合が多い。それに対して、サーバーからダウンロードして使用するプログラムや金銭やプライバシー情報などは、誤りを生じたり内容が漏洩したりすると大きな損害を生じる恐れがある。
【０００３】
誤り検出・訂正符号は、主に通信路や記録メディア上で発生したエラーを検出・訂正したり、送信先に再送を求めたりするといった用途で用いられる。従って、その符号化あるいは復号の装置自体にエラーが発生した場合には、元々訂正不可能なデータが生成されたり、エラーが検出できないといったことが起きる。暗号技術も、送信あるいは記録されるデータの安全性を確保することはできても、暗号装置の故障によるデータの損失や、それを利用した攻撃に対処することはできない。そこで、データを符号化・復号する装置自体の信頼性を確保する技術が必要となる。
【０００４】
図１は、符号化の過程で回路に発生するエラーを検出する従来方式を説明するための図である。復号時のエラー検出については、図の符号化と復号を互いに置き換えて考えればよい。図１(a)に描かれる方式では、入力されたデータを左側のパスで符号化した後に、その出力のビット幅以下のパリティを生成する。それと同時に期待値回路ではパリティを直接生成し、２つのパリティが一致しているかどうかでエラーの発生を検出するものである。期待値回路は符号化後にパリティを生成するのよりも小さい回路となるが、パリティなのでエラーの発生を全て検出できるわけではない。
【０００５】
図１(b)に描かれる方式は、同じ符号化回路を２つ用意して、両者で同時に同じ演算を行って結果を比較するものである。当然のことながら、回路のコストは2倍に増加する。図１(c)に描かれる方式では、符号化と復号が別の回路ブロックでサポートされている。入力データをレジスタ2にストアするのと同時に、符号化したデータをレジスタ1にストアする。次のサイクルでは新しい入力データの符号化が可能で、それと平行にレジスタ1のデータを復号してレジスタ2と比較してエラー検出を行う。しかし、符号化と復号の回路は演算コンポーネントを共有している場合が多く、その場合には適用することができない。また、独立していた場合でも、別のデータに対して符号化と復号を同時に行うことはできなくなってしまう。例えばデータの双方向通信を行うときに符号化と復号を同時行うことができないため、結局、回路のコスト的は2倍に増加していることに等しい。
【０００６】
図１(d)に描かれる方式は、一つの符号化回路で同じ処理を2回繰り返してその結果を比較するものである。まず、入力データを符号化して結果をレジスタ1にストアする。次のサイクルでも同じデータをもう復号化して、その結果がレジスタ1と一致するかどうかを調べる。この方式は、電源ノイズなどに起因する一時的なエラーには検出できるものの、トランジスタや配線の欠陥によって常に同じエラーが発生する場合は検出できないという欠点を持つ。また、同じ復号処理を2回繰り返すため動作速度は1/2に低下してしまう。
【０００７】
図１(e)に描かれる方式は、符号化と復号が同じ回路ブロックで処理される方式である。入力データをレジスタ2にストアするのと同時に、レジスタ1には符号化したデータを保持する。次のサイクルではレジスタ1のデータを復号してレジスタ2と比較する。２サイクルで１つのデータしか処理できないので、エラー検出を行わない場合に対してスループットが1/2になるのは図１(d)の場合と同様である。しかし、同じ演算ブロックを使用しているものの、符号化と復号といった異なる処理を行い、元のデータが復元できることを確認しているため、図１(d)のように回路の欠陥によって検出不可能なエラーが起こる可能性は低い。
【０００８】
図１(f)に描かれる方式は、図１(d)の場合の符号化部を2分割してレジスタを挟み、パイプライン処理する実装で、２つのレジスタの前後で2回結果の比較を行っている。パイプライン化したことで動作周波数が向上し、エラー検出による速度へのペナルティが改善される。しかしながら、図１(d)の場合と同様に、回路の欠陥があった場合にエラーを検出できないという問題は解決されていない。
【０００９】
以上のように、従来の回路動作時のエラー検出手法は、エラーの検出率に問題があったり、回路規模が2倍あるいは動作速度が1/2になったりしてしまうといった欠点を持っている。
【００１０】
上記のエラー検出方式に準じた暗号回路は、下記非特許文献1にまとめられている。また下記特許文献1及び2において、暗号回路の実装法が開示されているが、これは演算部ではなく、データレジスタに誤りエラー検出・訂正回路を付加するものである。
【非特許文献１】T. G. Malkin, et al., "A Comparative Cost/Security Analysis of Fault Attack Countermeasures," FDTC2006, LNCS 4236, pp. 159-172, Oct. 2006.
【特許文献１】特開2007−174024号公報
【特許文献２】特開2007−325219
【発明の開示】
【発明が解決しようとする課題】
【００１１】
以上のような背景の下、本発明は、符号化・復号回路の動作時のエラー検出を確実に行い、かつ回路規模と動作速度に対するペナルティを軽微なものとする新たな手法を開発すべくなされたものである。
【課題を解決するための手段】
【００１２】
本発明は、符号化又は復号処理をパイプライン処理で行う方式に関する。各パイプライン・ステージは、符号化処理の一部である部分符号化処理だけでなくその一部処理の逆処理となる部分復号処理を実行しうる、部分符号化・部分復号ブロックを含む。以下では混乱をきたさない範囲で，部分符号化及び部分復号をそれぞれ単純に，符号化及び復号と記す。
【００１３】
本発明の符号化回路における具現化形態では、あるステージにおいて符号化処理が実行されている時、その１つ前段のステージでは、直前のサイクルにおける符号化処理の検証としての復号処理が並行して実行される。復号されたデータは、直前のサイクルにおいて符号化の対象となったデータと比較されて、一致しているかどうかが調べられる。その次のサイクルでは、前回符号化処理を行った同じステージにおいて、先に符号化されたデータが復号され、符号化される前のデータと一致しているかどうかが調べられる。並行して、当該先に符号化されたデータに対して次段のステージで符号化処理が進められ（次段のステージがない場合には回路から出力され）、前段のステージには新たなデータが入力されて符号化処理が行われる。
【００１４】
本発明の復号回路における具現化形態では、上記の符号化回路における符号化と復号の順番や役割が逆転する。
【００１５】
すなわち、本発明に基づく符号化・復号回路は、複数の符号化・復号ブロックからなるパイプラインとして構成され、各符号化・復号ブロックは、１サイクル毎に、符号化処理と復号処理を切り替える。従って全体としては、各サイクルにおいてデータの処理が進行するだけでなく、前のサイクルにおける処理の検証も同時に行われている。符号化回路として動作する場合には、復号が検証のために行われ、復号回路として動作する場合には、符号化が検証のために行われる。
【００１６】
本発明によれば、符号化又は復号処理を分割してパイプラインで処理すると共に、処理を進めるのと並行して検証処理も行うため、処理の途中でエラー検出を行うことができる。このような能力は、特に、故意にエラーを発生させて情報を盗むような攻撃、例えば共通鍵暗号に対する故障利用解析攻撃に対する防御に有効であり、エラーを検出した場合に直ちに処理を停止させるなどの目的に利用することができる。
【００１７】
また、本発明においては、符号化と復号が同じ回路ブロックで処理されるものの、符号化と復号といった異なる処理を行い、元のデータが復元できることを確認しているため、回路の欠陥によって検出不可能なエラーが起こる可能性は非常に低い。これらのことから、本発明による誤り検出機能は、非常に強力かつ信頼性の高いものであると言える。
【００１８】
一方、本発明による回路構成では、各符号化・復号ブロックの処理を１サイクル毎に符号化と復号とで切り替えるため、データの入力は多くとも２サイクルに１回しか行うことができない。しかしながら、演算ブロックを複数のブロックに分割し、パイプライン処理することで、動作周波数を向上させることができるため、処理性能の低下は限定的である。回路規模の点でも、もともと一つであった演算ブロックを複数に分割しただけであるので、回路規模はそれほど増加しない。付加回路も、パイプライン処理用のレジスタとセレクタ、そしてエラー検出用の比較器だけでよい。
【００１９】
このため本発明によれば、強力かつ信頼性の高い誤り検出機能を回路に持たせつつ、回路規模と動作速度への悪影響を最小限に抑えることができる。
【００２０】
また、ここで開示される回路構成は、符号化・復号の演算方式に依存した構成ではないため、様々な方式に対して広く適用することが可能である。
【００２１】
本発明の実施形態は、次のような符号化回路を含む。この回路は、ステージＸ及び前記ステージＸの次のステージであるステージＹを少なくとも含む、複数のステージのパイプライン処理によって符号化処理を行う符号化回路であって、
前記複数のステージの各々は、符号化処理の一部である部分符号化処理及び該一部の逆処理となる部分復号処理を実行しうる部分符号化・部分復号ブロックを含み、
或るサイクルにおいて、
・  前記ステージＹにおいて、前記或るサイクルの１つ前のサイクルにおいて前記ステージＸで部分符号化されたデータが部分符号化され、
・  前記ステージＸにおいて、前記１つ前のサイクルにおいて前記ステージＸで部分符号化されたデータが部分復号され、
・  予め記憶されていた、前記１つ前のサイクルにおいて前記ステージＸで部分符号化される前のデータと、前記部分復号されたデータとが比較され、
前記或るサイクルの次のサイクルにおいて、
・  前記ステージＹにおいて、前記或るサイクルにおいて前記ステージＹで部分符号化されたデータが部分復号され、
・  予め記憶されていた、前記或るサイクルにおいて前記ステージＹで部分符号化される前のデータと、前記ステージＹで部分復号されたデータとが比較され、
・  前記ステージＸにおいて、別のデータが部分符号化される、
ように構成される、符号化回路である。
【００２２】
また本発明の実施形態は、次のような復号回路を含む。この回路は、ステージＸ及び前記ステージＸの次のステージであるステージＹを少なくとも含む、複数のステージのパイプライン処理によって復号処理を行う復号回路であって、
前記複数のステージの各々は、復号処理の一部である部分復号処理及び該一部の逆処理となる部分符号化処理を実行しうる部分符号化・部分復号ブロックを含み、
或るサイクルにおいて、
・  前記ステージＹにおいて、前記或るサイクルの１つ前のサイクルにおいて前記ステージＸで部分復号されたデータが部分復号され、
・  前記ステージＸにおいて、前記１つ前のサイクルにおいて前記ステージＸで部分復号されたデータが部分符号化され、
・  予め記憶されていた、前記１つ前のサイクルにおいて前記ステージＸで部分復号される前のデータと、前記部分符号化されたデータとが比較され、
前記或るサイクルの次のサイクルにおいて、
・  前記ステージＹにおいて、前記或るサイクルにおいて前記ステージＹで部分復号されたデータが部分符号化され、
・  予め記憶されていた、前記或るサイクルにおいて前記ステージＹで部分復号される前のデータと、前記ステージＹで部分符号化されたデータとが比較され、
・  前記ステージＸにおいて、別のデータが部分復号される、
ように構成される、復号回路である。
【００２３】
本発明は、デジタルデータを扱う一般及び業務用の電子情報機器全般に対して有用であり、特にデジタルコンテンツや暗号技術、情報セキュリティに関係する情報機器に対して有用である。従って本発明の実施形態は、単に符号化回路や復号回路及びこれらの回路を含む半導体チップを含むだけでなく、これらの回路を含む電子機器、例えばパーソナルコンピュータや通信機器、デジタルＴＶ・レコーダ、ＩＣカードやネットワーク機器等をも含むものである。また、本明細書に開示される技術思想を具体化した符号化回路や復号回路は、再構成不可能なハードウェアとして実装されうるのみならず、ＦＰＧＡ等のプログラマブルロジックデバイスとしても実装可能なものである。すると本発明の実施形態は、本明細書に開示される技術思想をプログラマブルロジックデバイス上に表現するためのプログラムをも含む。
【００２４】
本発明の好適な具現化形態のいくつかの例が、添付の特許請求の範囲に定義されている。また、以下の実施例の説明にも、いくつかの好適な具現化形態の例が説明されている。しかしながら、本発明の具現化形態は、特許請求の範囲や実施例の説明に現れる形態に限定されるものではなく、本発明の範囲を逸脱することなく、様々なバリエーションをとることができることには留意されたい。また本発明の範囲は、特許請求の範囲や明細書、図面に明示的又は黙示的に現れる、全ての新規かつ有用な特徴及びそれらの組合せを包含することを申し述べる。
【発明を実施するための最良の形態】
【００２５】
以下、本発明の理解に資するために、添付図面を参照しつつ本発明の実施形態の例をいくつか説明する。前述のように、本発明は、符号化・復号演算のための、誤り検出能力を有する回路構成に関するものであり、パイプライン処理を利用している。そこでまず、パイプライン処理が２つのステージのみからなる、最も簡単な実施形態の例について説明する。
【００２６】
図２は、これから説明する実施形態に係る符号化回路200の回路構成の重要な部分を説明するための図である。符号化回路200は、二つの部分符号化・部分復号ブロック202及び204を有し、これらの二つのブロックによって符号化演算をパイプライン処理によって行う。部分符号化・部分復号ブロック202は、符号化回路200による符号化処理全体の前半部分の演算を担当し、部分符号化・部分復号ブロック204は、当該符号化処理全体の後半部分の演算を担当する。また、部分符号化・部分復号ブロック202及び204は、それぞれの部分符号化演算の逆演算となる部分復号演算を行ないうるように構成される。この場合、復号演算全体の前半部分は符号化演算の後半部分の逆演算となり、復号演算全体の後半部分は符号化演算の前半部分の逆演算となる。したがって、部分符号化・部分復号ブロック202は、復号演算の後半部分を処理し、部分符号化・部分復号ブロック204は復号演算の前半部分を処理する。なお、背景技術の項でも説明したように、符号化回路と復号回路は演算コンポーネントを共有して一つの処理回路にまとめられていることが多いので、部分符号化・部分復号ブロック202及び204のように、一つの処理回路で部分符号化及び部分復号の両方の演算を処理するように構成することは、当業者であれば困難なくできることである。
【００２７】
符号化回路200には、符号化・復号ブロック202及び204が演算処理の結果をストアするためのレジスタ206と、符号化・復号ブロック202及び204への入力データのコピーをストアするためのレジスタ208が設けられる。したがって、レジスタ206及び208は、符号化・復号ブロック202及び204によって共用される。また符号化回路200には、比較器210が設けられる。比較器210も、符号化・復号ブロック202及び204で共用され、演算処理の結果とレジスタ208にストアされているデータとの比較を行うために用いられる。レジスタ206，208及び比較器210を共用するために、三つのセレクタ212ａ〜ｃが設けられる。
【００２８】
次に、符号化回路200の処理の流れを図３の(a)〜(d)と式を追って詳細に説明する。以下の説明において、符号化・復号ブロック202で符号化が行われるとき、その関数をENCpre()、復号が行われるときの関数をDECpost()で表すことにする。また、符号化・復号ブロック204についても、同様に、符号化が行われるときの関数をENCpost()、復号が行われるときの関数をDECpre()と表す。
【００２９】
最初の演算サイクル(a)では、入力されたデータD0に対して符号化・復号ブロック202で符号化の前半処理を施し、次式のように途中結果E0preを求める。
E0pre = ENCpre(D0)
演算の結果は、次のサイクル(b)において、レジスタ206にストアされるべく準備される。また入力データD0も、次のサイクル(b)において、レジスタ208にストアされるべく準備される。
【００３０】
次のサイクル(b)では、新たなデータの入力は行われないが、前のサイクルにおける演算結果E0preがレジスタ206に、前のサイクルにおける入力データD0がレジスタ208にストアされる。そして、レジスタ206にストアされた演算結果E0preに対し、符号化・復号ブロック204で符号化の後半処理が行われ、次のように符号化結果E0が得られる。
E0 = ENCpost(E0pre)
結果E0は、次のサイクルでレジスタ206にストアされるべく準備される。また、符号化・復号ブロック204への入力データE0preも、次のサイクルでレジスタ208にストアされるべく準備される。
【００３１】
符号化・復号ブロック204による処理と同時に、符号化・復号ブロック202は、レジスタ206にストアされたE0preに対して復号の後半処理を行い、回路が正しく動作していれば次のようにD0を得る。
D0 = DECpost(E0pre) = DECpost(ENCpre(D0))
【００３２】
比較器210は、符号化・復号ブロック202により復号されたデータD0を、をレジスタ208が保持しているD0と比較する。この比較結果が一致すればエラーは存在せず、一致しなければエラーが存在することになり、検証が可能となる。
【００３３】
念のために記しておくと、２サイクルで実行される符号化の関数の順番をENCpre()→ENCpost()、復号をDECpre()→DECpost()としたので、ENCpre()→ENCpost()→DECpre()→DECpost()で元のデータに戻ることになる。従って、ENCpre()とDECpost()およびENCpost()とDECpre()の組が、それぞれ逆関数になっている。
【００３４】
次のサイクル(c)では、レジスタ206に結果E0がストアされると共に、レジスタ208には前のサイクルにおける符号化・復号ブロック204への入力データE0preがストアされる。そして、レジスタ206からは符号化結果E0が出力される。同時に、レジスタ206が保持する値E0に対し、符号化・復号ブロック204によって復号の前半処理が次のように行われ、レジスタ208が保持する値E0preと一致するかどうかが比較器210でチェックされる。
E0pre = DECpre(E0) = DECpre(ENCpost(E0pre))
【００３５】
また、これらの処理と同時に新たなデータD1が入力され、符号化・復号ブロック20による次の符号化処理によって途中結果E0preが計算される。
E1pre = ENCpre(D1)
E1pre，D1は、それぞれ次のサイクルにおいてレジスタ206，208にストアされるべく準備される。
【００３６】
次のサイクル(d)では、上述のサイクル(b)と同様に、レジスタ206の途中結果E1preに次のように符号化の後半処理と、検証処理としての復号処理が行われ、以下、新たなデータ入力がある度に、同様の処理が繰り返されていく。
E1 = ENCpost(E1pre)
D1 = DECpost(E1pre)
【００３７】
符号化回路200は、符号化と復号が同じ回路ブロックで処理されるものの、符号化と復号といった異なる処理を行い、元のデータが復元できることを確認しているため、回路の欠陥によって検出不可能なエラーが起こる可能性は非常に低い。また、符号化と復号を行って元のデータに戻ることを確認しているため、検出できないエラーのあるパリティ・チェック等に比べて信頼性が高いエラー検出方式であると言える。
【００３８】
一方、符号化回路200では、データの入力を２サイクルに１回しか行うことができないので、エラー検出を行わない場合に対して2倍のサイクル数が必要となる。しかしながら、演算ブロックを2分割したことで、動作周波数がおよそ2倍に向上するため、処理性能の低下は限定的である。付加回路もパイプライン処理用のレジスタとセレクタ、そしてエラー検出用の比較器だけでよい。演算ブロックは２つになっているが、もともと１つだったものを分割しただけなので、図１(c)の方式における二重化のように、演算部を丸ごと新たに加えるようなことはなく、回路規模の増加も極めて限定的である。
【００３９】
すなわち符号化回路200に例示される回路構成は、符号化・復号回路の動作時のエラー検出を確実に行い、且つ回路規模と動作速度に対するペナルティを軽微なものとすることを可能とする。さらに、ここで説明された構成は、符号化の演算方式に依存した構成ではないため、適用範囲が広いという特長をも有している。
【００４０】
以上の説明で理解されるように、符号化処理に係る本発明の実施形態においては、符号化処理が複数のステージに分割され、各サイクルにおいて、符号化の部分演算と、その１サイクル前における符号化部分演算の検証処理としての復号演算が同時に行われる。符号化回路200を用いた例では、簡単のため演算処理を２分割としたか、パイプライン処理が可能な場合は、３，４，５・・・と分割数を増やすことで、動作周波数を2分割の場合よりもさらに向上させることが可能である。分割数を増やすほど処理部の遅延時間は短縮されるが、他の部分の固定の遅延時間があるため、動作周波数は次第に向上しなくなる。またその反面、パイプラインレジスタと比較器といった付加回路が増えていくため、処理能力と回路規模のバランスを見ながら、符号処理の特性に応じて分割数を選択する必要がある。
【００４１】
図２，図３を用いた上述の説明では、回路200を符号化回路として説明したが、符号化・復号ブロック202と204の使用の順序を入れ替えるだけで、回路200を復号回路として動作させることができる。すなわち、あるステージの復号処理を行いながら、その前ステージの復号処理に対する逆処理としての符号化処理を並行して行うことで検証を行う、復号回路が実現できる。本発明の実施形態の多くは、符号化回路としても、復号回路としても動作することができる。そこで次に、分割数を４つとした実施例について、復号処理についても詳しく触れつつ説明する。
【００４２】
図４(a)は、第２実施例として説明する符号化・復号回路400の回路構成の重要な部分を説明するための図である。符号化・復号回路400は、符号化演算及び復号演算を、四つのステージ410，420，430，440でパイプライン処理するように構成されている。各ステージは、それぞれ部分符号化・部分復号ブロックを備えており（412，422，432，442）、符号化・復号処理の異なる段階を担当する。ブロック412は符号化処理の1段目と復号処理の4段目を担当し、ブロック422は符号化処理の2段目と復号処理の3段目を担当し、ブロック432は符号化処理の3段目と復号処理の2段目を担当し、ブロック442は符号化処理の4段目と復号処理の1段目を担当する。各符号化・復号ブロック412〜442で処理される符号化処理と復号処理は互いに逆関数の関係になっている。図４(b)に描かれるように、入力データをブロック412，422，432，442の順で処理する場合、符号化・復号回路400は符号化回路として動作し、入力データをブロック442，432，422，412の順で処理する場合は復号回路として動作する。
【００４３】
各符号化・復号ブロックには、それぞれ当該ブロックで処理されたデータを保持するための第１レジスタ（413，423，433，443）と、エラー検出のために一つ前のサイクルのデータを保持するための第２レジスタ（414，424，434，444）が設けられる。また、第２レジスタ（414，424，434，444）に保持されたデータと、逆処理を行なって元に戻したデータとの一致・不一致を判定する比較器が、各符号化・復号ブロックに設けられる（415，425，435，445）。このほか符号化・復号回路400は、各符号化・復号ブロック（412，422，432，442）について、データの入力をコントロールするためのセレクタが設けられる（411，421，431，441）。
【００４４】
符号化・復号回路400が符号化回路として動作するときであっても復号回路として動作するときであっても、各符号化・復号ブロック（412，422，432，442）は、１サイクルごとに、符号化処理と復号処理を切り替える。ある符号化・復号ブロックが符号化処理を行うサイクルにおいて、隣接するブロックは復号処理を行う。符号化・復号回路400が符号化回路として動作するとき、復号処理はエラー検出のために行われる。反対に、符号化・復号回路400が復号回路として動作するときは、符号化処理はエラー検出のために行われる。
【００４５】
各ステージで部分処理されたデータは第１レジスタ（413，423，433，443）に保持ざれ、次のサイクルで符号化ならば右のステージに、復号ならば左のステージに渡されて処理が続けられる。これと同時に、同じステージではエラー検出のための逆処理が行われ、第２レジスタ（414，424，434，444）に保持される一つ前のサイクルのデータと逆処理後のデータが一致するかどうかが比較器（415，425，435，445）でチェックされる。
【００４６】
図５は、符号化・復号回路400が復号回路として動作する場合の様子を描いた図である。上段(a)があるサイクルにおける動作を示し、下段(b)が(a)の次のサイクルにおける動作を示している。また、 (b)の次のサイクルにおける符号化・復号回路400の動作の様子は、また(a)に戻る。図の右上から復号すべきデータが入力され、左下に復号されたデータが出力される。
【００４７】
図５に描かれるように、各ステージでは、復号と、符号化による検証（エラー検出）が交互に行われる。たとえば、符号化・復号ブロック442は、(a)のサイクルでは復号処理を行うが、(b)のサイクルではその復号処理の検証としての符号化処理を行なっている。同様の関係が、いずれの符号化・復号ブロック412，422，432，442についても見ることができる。
【００４８】
また、復号が行われるステージの隣のステージでは、１サイクル前の復号の結果を検証すべく、符号化が並行的に行われる。たとえば、(b)における符号化・復号ブロック443と符号化・復号ブロック442を見ると、符号化・復号ブロック443が2段目の復号演算を実行しているのに対し、符号化・復号ブロック442では、1段目の復号演算の逆演算としての4段目の符号化処理を、エラー検出のために実行している。同様の関係が、(a)における符号化・復号ブロック422と432、(b)における符号化・復号ブロック412と422にも見ることができる。
【００４９】
図５において、灰色に示したコンポーネントと破線のバスは、処理が行われていない部分を示しており、各サイクルで、半分のレジスタと比較器が使用されていないことが理解できる。これはすなわち、二つのステージでレジスタと比較器を共有することができることを示している。次に説明する符号化・復号回路600は、このことを利用して、符号化・復号回路400におけるレジスタと比較器を半分にした実施例である。また、図２を用いて説明された符号化回路200において、二つの符号化・復号ブロック202，204に対してレジスタが二つ（206，208）および比較器が一つしか設けられていなかったのも、同様の理由による。
【００５０】
図６に描かれる符号化・復号回路600は、符号化・復号回路400の変形例であり、隣接する符号化・復号ブロックで、レジスタと比較器を共用するように構成したことを特徴とする。図６と図４を比較すると分かるように、図４に描かれるレジスタ413と423が、図６においては一つのレジスタ613に置き換えられており、図４におけるレジスタ414と424が、図６ではレジスタ614に置き換えられている。また、図４に描かれる比較器425と435は、図６では一つの比較器615に置き換えられている。図４におけるレジスタ433及び443と図６のレジスタ633、図４におけるレジスタ434及び444と図６のレジスタ634、図４における比較的435及び445と図６の比較器635の関係についても同様である。
【００５１】
符号化・復号回路600には、レジスタ及び比較器を共有するために、符号化・復号回路400に比べてセレクタ616，617，626，627が追加されているが、二つのレジスタ及び一つの比較器が二つのステージで共有されることができるので、全体としての回路規模は、符号化・復号回路400に比べて小さくて済む。
［ＡＥＳへの応用例］
【００５２】
次に、本発明のより具体的な実施例として、国際標準暗号AES（Advanced Encryption Standard）回路へ適用した例を示す。暗号は、元のデータが1ビットでも異なると、まったく異なるデータに変換されるという特性を有する。このため、演算エラーが発生すると、データがまったく復元できなくなるという極めて深刻な問題を生じる結果となる。また暗号は、ICカードなど金銭に関係するアプリケーションにも使用されるため、秘密の情報を盗み出そうとする悪意の利用者による電源やクロックへの不正なノイズ印加による誤動作にも対応する必要がある。このように、暗号回路は符号化・復号回路の中でも特に高い信頼性が要求され、高性能なエラー検出機構が不可欠である。
【００５３】
図７は、128ビットの秘密鍵を用いた、エラー検出機能を有さないAESの暗号化・復号回路例の概略図である。128ビットのデータにラウンド関数と呼ばれる変換を10回繰り返して暗号化と復号を行うため、通常はこの図の左側のデータ変換部にあるように、ラウンド関数ブロックを１つだけ用意して、それを１回の暗号化（または復号）で10回利用するループアーキテクチャが用いられる。ラウンド関数は大きく４つの部分から構成され、暗号化の場合にそれぞれShiftRows、SubBytes、MixColumns、AddRoundKeyと表される。復号はこれらの逆関数となる処理によって行われ、それぞれInvShiftRows、InvSubBytes、InvMixColumns、AddRoundKeyと表される。（なお、図中MixColumnsとInvMixColumnsはそれぞれMixCol．と InvMixCol．と表されている。）暗号化と復号で対応する関数はそれぞれ回路を共有している。同じ入力データを同じ関数で変換しても、秘密鍵を変えることによってまったく異なるデータが出力される。秘密鍵は右側の鍵スケジューラで簡単な変換が行われながら、ラウンド関数に10回入力される。
【００５４】
図７において、データレジスタ712は、ループ処理を行うために、各ループの処理結果を保持するために用いられる。ShiftRows及びその逆関数InvShiftRowsの処理は、ブロック714で行われ、SubBytes及びその逆関数InvSubByteの処理は、ブロック716で行われる。MixColumns及びその逆関数InvMixColumnsの処理は、ブロック718で行われ、AddRoundKeyの処理はブロック720で行われる。
【００５５】
図８は、図２を用いて説明した2分割構成を、図７のAES回路に適用したものである。ラウンド関数はShiftRows/InvShiftRowsとSubBytes/InvSubByte、そしてMixColumns/InvMixColumnsとAddRoundKeyをまとめた２ブロックに分割されている。すなわち図２と図８を比較すると、図２の符号化・復号ブロック202が、図８におけるShiftRows/InvShiftRowsブロック714及びSubBytes/InvSubByteブロック716に対応し、図２の符号化・復号ブロック204が、図８におけるMixColumns/InvMixColumnsブロック718及びAddRoundKeyブロック820，821に対応する。また、図２のレジスタ206は図８のレジスタ712に対応し、図２のレジスタ208は図８のレジスタ812に対応する。図２の比較器210に対応するものは、図８では比較器828である。さらに図８のＡＥＳ回路では、図７のＡＥＳ回路を２ステージ化するために、図２のセレクタ212ｂ，212ｃに対応するセレクタ824，826が設けられている。
【００５６】
図２の構成では２サイクルで１回の符号化を行っていた。一方、図７の回路は１０サイクルで暗号化（符号化）を行い、図８はその各サイクルのラウンド関数毎に逆変換を行ってエラー検出を行うので、２０サイクルで一回の暗号化を行うことになる。しかしながら、１回のラウンド関数変換を１回の符号化と考えれば、図５と基本的に等価である。図８の一致信号1はサイクル毎に、半分のラウンド関数処理のエラーチェック結果が出力される。
【００５７】
図８のアーキテクチャでは、AddRoundKeyとInvMixColumnsの順序を入れ替えてXORゲートを共有することは行っていない。このため、図７においてはAddRoundKeyブロックが１つ（720）であるのに対し、図８においては２つ（820，821）となっている。図７のアーキテクチャではXORゲートを共有することでクリティカルパスであるラウンド関数ブロックを短くできるが、その代わりに鍵スケジューラにMixColumnsが必要となる。これに対してラウンド関数を２分割する提案方式の実装では、XORを共有しないで鍵スケジューラのMixColumnsを省略したほうが回路規模と動作速度のバランスが良かったためである。ところでラウンド関数ブロックの遅延時間が分割によって短くなると，鍵スケジューラがクリティカルパスとなってくる。そこで，鍵スケジュールも１ラウンドを２クロックで処理するようにレジスタを挿入している。
【００５８】
ラウンド関数は正しく動作していても、鍵スケジューラにエラーが発生したり、制御カウンタの故障によって本来10ラウンドの繰り返し処理が１回で終了してしまうといったことも考えられる。これを防ぐために、最終ラウンドの処理が終了したときにオンザフライで生成された鍵を調べ、暗号化であれば復号鍵レジスタと、復号であれば暗号化鍵レジスタとの一致を比較器830で確認している。攻撃者がカウンタの値を飛ばすことができたとしても、値が不明の鍵スケジューラの128ビットまで正しく飛ばすことは不可能である。
【００５９】
図９を参照しつつ、図８の提案AES回路の暗号化時の動作例を説明する。矢印の頭部が黒く塗りつぶされている場合は処理の流れがあることを示し、白抜きになっている場合は処理の流れがないことを示す。暗号化用の初期鍵K0は暗号化鍵レジスタ732に入力され、右側の鍵スケジューラで復号用の初期鍵（＝暗号化用の最終鍵）K10に変換されて復号鍵レジスタ734に既にセットされているものとする。
【００６０】
まず(a)では、入力された平文と暗号化用の初期鍵K0がXORされてデータレジスタ712にD0として書き込まれ、暗号化処理の前半のShiftRrows 714とSubBytes 716のパスを通ったデータがD1Xとしてフィードバックされる。それと同時にデータD0は比較用レジスタ812に渡される。また鍵スケジューラでは、オンザフライで初期鍵K0から第１ラウンドの鍵K1が生成される。(b)では、検算のために(a)で暗号化に使用したパスで復号が行われ、データレジスタ712に書き込まれたデータD1XがInvShirtRows 714とInvSubBytes 716によって逆変換された後、比較器828において、比較用レジスタ812に保持されている値D0と比較される。一方、同じデータD1Xは、別のパスでMixColumns 718とAddroundKey 820（ラウンド鍵K1とのXOR）によりD1に変換される。(c)では、(a)と同じパスでデータレジスタ712の値D1がD2Xに変換されるのと同時に、その右のパスではInvMixColumns 718とAddroundKey 821（ラウンド鍵K1とのXOR）でD1Xに戻されて比較用レジスタ812の値と比較される。以下同様に、第9ラウンドまで暗号化と検算が繰り返される。
【００６１】
(d)ではエラー検出のためにInvShiftrowsとInvSubBytes、そして暗号化の最後の処理である最終第１0ラウンドの鍵K10とのXORが行われる。図３でも示したように、最終ラウンドではMixColumnsは行われないので、その処理ブロックはバイパスされる。最終ラウンドなので、オンザフライで生成されたラウンド鍵レジスタのK10と事前計算による暗号化鍵レジスタ732のK10との比較により、10ラウンドきちんと処理されたことのチェックが行われる。ここで暗号文D10の出力も可能であるが、最後に(e)でD10Xに戻ることが確認された後に出力している。この最終チェックが済むまで次の平文は入力されないため、１ブロックの暗号化に要するクロック数は、20クロック（=10ラウンド×2クロック）に(e)の１クロック分が加算され、21クロックとなる。
【００６２】
図７と図８の回路をそれぞれ設計し、90nmのCMOSスタンダードセル・ライブラリを用いた論理合成で回路規模と動作速度を評価した結果を図１０の表に示す。なお、図８の回路においては、前述のように暗号化が終了してから次のデータを入れるのに１サイクルインターバルを入れる設計としているため、サイクル数は21となっている。論理合成時の最適化は、回路規模（ゲート）を最小とするものと動作速度（スループット）を最大とする2種類の他に、単位ゲートあたりのスループットである回路効率を最大とする実装も行った。論理合成の条件によって回路規模と動作速度は大きく変動し、小型化するほど速度は遅くなり、高速化するほど回路規模は大きくなるので、その値を単純比較しても実装の優劣をつけることは難しい。そこで、回路効率が単純比較の指標としては最適である。図１０の表からわかるように、回路規模最適化と動作速度最適化の双方において、エラー検出なしと本発明の回路効率は同等である。規模と速度のバランスが最適な実装においても、エラー検出なしの169.48 kbps/gateに対して本発明はその85.5%の145.01 kbps/gateであった。つまり、本発明を適用したAES回路は、最大でもわずか15%程度のオーバーヘッドで、確実なエラー検出が可能である優れた手法であることがわかる。
【００６３】
以上、本発明の実施形態の例を紹介してきたが、これらの実施形態を紹介したのは本発明の範囲を限定する意図でなされたものではなく、あくまで本発明の深い理解に資するためのものである。本発明は、その思想の範囲を逸脱することなく、本明細書に紹介した実施形態以外にも様々な実施形態を取りうるものである。特許請求の範囲に記載される実施形態は、本発明の好適な実施形態ではあるが、本発明の実施形態はそれに止まるものではなく、本願の出願書類及び技術常識から当業者が感得しうる全ての構成を含むものである。
【図面の簡単な説明】
【００６４】
【図１】従来のエラー検出回路方式を説明するための図である。
【図２】第１実施例として紹介する符号化回路200の回路構成の重要な部分を説明するためのである。
【図３】符号化回路200の処理の流れを説明するための図である。
【図４】第２実施例として紹介する符号化・復号回路400の回路構成の重要な部分を説明するための図である。
【図５】符号化・復号回路400が復号回路として動作する場合の様子を説明するための図である。
【図６】符号化・復号回路400の変形例を説明するための図である。
【図７】エラー検出機能を有さないAESの暗号化・復号回路例を説明するための図である。
【図８】本発明の第３実施例として紹介する、AESの暗号化・復号回路を説明するための図である。
【図９】図８のAES回路の動作を説明するための図である。
【図１０】図７と図８のAES回路の性能を比較するための図である。
【符号の説明】
【００６５】
200    符号化回路
200    符号化回路
202，204    部分符号化・部分復号ブロック
206，208    レジスタ
208    レジスタ
210    比較器
212ａ-212ｃ    セレクタ
400    符号化・復号回路
410，420，430，440    ステージ
411，421，431，441    セレクタ
412，422，432，442    部分符号化・部分復号ブロック
413，423，433，443    レジスタ
414，424，434，444    レジスタ
415，425，435，445    比較器
600    符号化・復号回路
613    レジスタ
614    レジスタ
615    比較器
616，617，626，627    セレクタ
633    レジスタ
634    レジスタ
635    比較器
【図１】
0005164154.tif 000002
【図２】
0005164154.tif 000003
【図３】
0005164154.tif 000004
【図４】
0005164154.tif 000005
【図５】
0005164154.tif 000006
【図６】
0005164154.tif 000007
【図７】
0005164154.tif 000008
【図８】
0005164154.tif 000009
【図９】
0005164154.tif 000010
【図１０】
0005164154.tif 000011