ガロア体の逆元演算回路
【課題】ダイナミックハザードに起因する消費電力の増加を一様に抑えて、ＤＰＡ攻撃を困難にする。
【解決手段】８ビットの入力データは４つのデコーダ１１１乃至１１４によって２ビットずつデコードされ、それぞれ４ビットずつ計１６ビットのデコードデータとなる。演算部１２０はデコードデータに対してＧＦ（（（２2）2）2）逆元演算を行う。演算結果は４つのエンコーダ１３１乃至１２４によって４ビットずつエンコードされ、それぞれ２ビットずつ計８ビットの出力データとなる。デコーダ１１１乃至１１４は共通の制御信号ＰＣｄｌｙに同期して演算開始前に固定値「００００」を一旦出力した後に、入力データに応じて何れか１ビットのみを「１」に変化させる。演算部１２０は固定値が入力されると固定値を出力し、固定値以外が入力されると演算結果を出力する。これにより、中間値への遷移を抑止する。
【解決手段】８ビットの入力データは４つのデコーダ１１１乃至１１４によって２ビットずつデコードされ、それぞれ４ビットずつ計１６ビットのデコードデータとなる。演算部１２０はデコードデータに対してＧＦ（（（２2）2）2）逆元演算を行う。演算結果は４つのエンコーダ１３１乃至１２４によって４ビットずつエンコードされ、それぞれ２ビットずつ計８ビットの出力データとなる。デコーダ１１１乃至１１４は共通の制御信号ＰＣｄｌｙに同期して演算開始前に固定値「００００」を一旦出力した後に、入力データに応じて何れか１ビットのみを「１」に変化させる。演算部１２０は固定値が入力されると固定値を出力し、固定値以外が入力されると演算結果を出力する。これにより、中間値への遷移を抑止する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ガロア体の逆元演算回路に関し、特にメッセージの暗号化または復号化の際に利用されるガロア体の逆元演算回路に関する。
【背景技術】
【０００２】
２００１年、米国国立標準技術研究所（ＮＩＳＴ）はＲｉｊｎｄｅａｌを次期米国標準の１２８ビット共通鍵ブロック暗号ＡＥＳ（Advanced Encryption Standard）として選出した。ＡＥＳの回路実装においては、演算速度の高速化や回路規模削減手法が学会等で報告されてきているが、それに加えて、低消費電力化やサイドチャンネル攻撃に対する耐性をもつ構成も近年報告されている。特に、従来の共通鍵ブロック暗号のＤＥＳ（Data Encryption Standard）の置換えとして用いる場合、電池動作の組込み機器への搭載や、非接触動作するＩＣカードへの搭載に際しては、消費電力に対する仕様は著しく制限される。
【０００３】
ＡＥＳ暗号の入力データは１２８ビットであるが、８ビットを単位とした４×４のマトリクスとして定義され、演算処理は８ビット単位で行われる。暗号化の際の演算処理としては、ＳｕｂＢｙｔｅｓ、ＳｈｉｆｔＲｏｗｓ、ＭｉｘＣｏｌｕｍｎｓ、ＡｄｄＲｏｕｎｄＫｅｙが行われる。ＳｕｂＢｙｔｅｓは、８ビットデータに対して逆元を計算し、アフィン変換を行うものである。ＳｈｉｆｔＲｏｗｓは、４×４のマトリクスの横方向（各行）に対して回転処理を行うものである。ＭｉｘＣｏｌｕｍｎｓは、４×４のマトリクスの縦方向（各列）に対して処理を行うものである。ＡｄｄＲｏｕｎｄＫｅｙは、ラウンド鍵との排他的論理和（ＸＯＲ）演算を行うものである。この中で、回路規模および消費電力が最も大きいのがＳｕｂＢｙｔｅｓである。このＳｕｂＢｙｔｅｓでは、８ビット入力８ビット出力のテーブル（Ｓｂｏｘ）が定義され、このテーブルに従った変換が行われる。このテーブルＳｂｏｘは、１６個必要とされる。
【０００４】
Ｓｂｏｘの主要な構成方法としては、（１）テーブルをランダムロジックにて構成する方法、（２）二分決定グラフにより構成する方法、（３）合成体上で逆元演算を行う数値演算回路により構成する方法が考えられる。これらを比較すると、一般的にゲート規模は（１）、（２）、（３）の順に小さくなり、ゲート規模の観点からは（３）の逆元演算が有利である。（３）の逆元演算では、ＡＥＳの仕様書に公開されているように、入力値を以下の既約多項式でのガロア体ＧＦ（２8）の要素とみなして演算する。
ｘ8＋ｘ4＋ｘ3＋ｘ＋１
【０００５】
Ｓｂｏｘの暗号化時の演算式は、暗号化演算時の８ビット入力を（ｂ７ ｂ６ ｂ５ ｂ４ ｂ３ ｂ２ ｂ１ ｂ０）、８ビット出力を（ｂ７' ｂ６' ｂ５' ｂ４' ｂ３' ｂ２' ｂ１' ｂ０'）としたとき、出力は以下の演算式により生成される。
【数１】
【０００６】
復号化演算時の８ビット入力を（ｂ７' ｂ６' ｂ５' ｂ４' ｂ３' ｂ２' ｂ１' ｂ０'）、８ビット出力を（ｂ７ ｂ６ ｂ５ ｂ４ ｂ３ ｂ２ ｂ１ ｂ０）としたとき、出力は以下の演算式により生成される。
【数２】
【０００７】
ガロア体上の演算では、基底が異なれば異なる演算になる。ＳｕｂＢｙｔｅｓで用いる既約多項式とは異なる体に合成体がある。ここで、合成体とは、素体から複数回の拡大により得られた体をいう。合成体上の乗算はさらに小さい合成体を用いて構成することができ、これにより、回路規模を削減することができる（例えば、非特許文献１参照。）。以下の既約多項式（式１）を使って得られる合成体ＧＦ（（（２2）2）2）上の逆元演算回路は、ＧＦ（２8）と同形な体上の逆元演算回路として得られる。
ＧＦ（２）→ＧＦ（２2）： ｘ2＋ｘ＋１
ＧＦ（２2）→ＧＦ（（２2）2）： ｘ2＋ｘ＋φ ・・・（式１）
ＧＦ（（２2）2）→ＧＦ（（（２2）2）2）： ｘ2＋ｘ＋λ
ただし、φ＝｛１０｝2、λ＝｛１１００｝2である。
【０００８】
逆元の演算は、もとの体Ａの元を同形写像δで合成体Ｂへマップし、合成体Ｂ上で逆元演算を実行した後、同形写像δ-1でもとの体Ａへマップするという手順で行われる。合成体ＧＦ（（（２2）2）2）上の逆元演算において、入力データを（ＰH，ＰL）、出力データを（ＰH-1, ＰL-1）としたとき、２つのデータの積は次式のようになる。
（ＰH・ｘ＋ＰL）・（ＰH-1・ｘ＋ＰL-1）
＝ＰH・ＰH-1・ｘ2＋（ＰH・ＰL-1＋ＰL・ＰH-1）ｘ＋ＰL・ＰL-1
＝ＰH・ＰH-1・（ｘ＋λ）＋（ＰH・ＰL-1＋ＰL・ＰH-1）・ｘ＋ＰL・ＰL-1
＝（ＰH・ＰH-1＋ＰH・ＰL-1＋ＰL・ＰH-1）・ｘ＋ＰH・ＰH-1・λ＋ＰL・ＰL-1
＝１
これにより、次式が得られる。
ＰH・ＰH-1＋ＰH・ＰL-1＋ＰL・ＰH-1＝０
ＰH・ＰH-1・λ＋ＰL・ＰL-1＝１
上式をＰH-1およびＰL-1について解くと、以下の式が得られる。
【数３】
【０００９】
この合成体上での８ビットの逆元演算を用いた（３）の構成では、回路規模は、他の２つの構成に比べて半分以下になるが、消費電流に関してはゲート規模の比率ほどは小さくならない。原因としては、乗算回路や逆元演算回路の２つの入力の遅延差に起因するダイナミックハザードが考えられる。このダイナミックハザードは後段に行くほど累積され、余分な電力消費が増加する。８ビットの逆元演算回路の最終段には、２つの４ビット乗算器が配置されるが、逆元演算回路への信号入力を起点とした時、上位側の乗算器の一方の入力は遅延ゼロでデータが入力されるのに対して、他方の入力は十数乃至三十数ゲートの遅延でデータが入力される。この間、出力は一旦中間値に遷移してから演算結果に遷移する。そして、遅延はビット毎に異なり、さらに、各ビット値が「０」か「１」かにより遅延は異なってくる。また、この逆元演算回路の入力信号も、ビット毎に異なるタイミングで入ってくる。これらにより、最終的な値に到達するまでに、８ビットの逆元演算回路は様々な中間値に遷移し、その度に演算回路での貫通電流および負荷で充放電電流を消費する。そして、この充放電電流は、消費電流を測定して、それに統計処理を施すことにより鍵を取り出すＤＰＡ（Difference Power Analysis）攻撃の対象となる。このようなＤＰＡ攻撃への対策の１つとして、遅延調整のための遅延回路を配置して、２入力演算回路の信号遅延差を調整する方法が提案されている（例えば、非特許文献１参照。）。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Sumio Morioka and Akashi Satoh : "An Optimized S-box circuit architecture for low power AES design", Workshop on Cryptographic Hardware and Embedded Systems 2002（CHES 2002），第１７２乃至１８６頁，２００２年８月
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上述のＤＰＡ攻撃に対処するために、遅延調整のための遅延回路を配置して、２入力演算回路の信号遅延差を調整する方法が提案されている。しかしながら、入力の遅延差は入力データ値によっても異なるため、すべてのデータに対して一様に消費電力を削減することは困難である。そして、削減できなかったハザード電流により、ＤＰＡ攻撃に対する脅威は依然残ってしまう。
【００１２】
本発明はこのような状況に鑑みてなされたものであり、ダイナミックハザードに起因する消費電力の増加を一様に抑えて、ＤＰＡ攻撃に対して耐性のある回路構成を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、ガロア体の入力データよりもビット幅が広い所定の固定値を一旦出力した後に、上記入力データに応じて上記固定値から所定ビット数だけ異なる値を示すデコードデータを出力するデコーダと、上記デコードデータに対してガロア体の逆元演算を実行して上記デコードデータの逆元データを出力する演算部と、上記逆元データを上記入力データと等しいビット幅の出力データにエンコードするエンコーダとを具備するガロア体の逆元演算回路である。これにより、固定値から所定ビット数だけ異なるデコードデータを演算対象として、中間値への遷移を抑止するという作用をもたらす。
【００１４】
また、この第１の側面において、上記デコーダは、制御信号に同期して上記固定値の出力を行うようにしてもよい。これにより、入力データの各ビットの遷移にばらつきがある場合であっても一斉に演算を駆動するという作用をもたらす。
【００１５】
また、この第１の側面において、上記制御信号は、上記入力データが上記デコーダに入力されるタイミングを示すものであってもよい。これにより、デコーダに入力されるタイミングに合わせて一斉に演算を駆動するという作用をもたらす。
【００１６】
また、この第１の側面において、上記演算部は、上記デコーダから上記固定値が出力されている間は上記固定値を出力するようにしてもよい。これにより、演算結果の遷移する期間を制限するという作用をもたらす。
【００１７】
また、本発明の第２の側面は、ガロア体の８ビットの入力データを２ビットずつに区切った４組の部分データに対してそれぞれ４ビット幅の固定値を一旦出力した後に、上記部分データに応じて上記固定値から１ビットだけ異なる４ビット幅のデコードデータをそれぞれ出力する４つのデコーダと、上記４組のデコードデータからなる１６ビットデータに対して逆元演算を実行して上記１６ビットデータの逆元データを出力する演算部と、上記逆元データを４ビットずつに区切ってそれぞれ２ビット幅の出力データにエンコードする４つのエンコーダとを具備するガロア体の逆元演算回路である。これにより、固定値から４ビット中１ビットだけ異なるデコードデータを演算対象として、中間値への遷移を抑止するという作用をもたらす。
【００１８】
また、この第２の側面において、上記４つのデコーダは、共通の制御信号に同期して上記固定値の出力を行うようにしてもよい。これにより、８ビットの入力データの各ビットの遷移にばらつきがある場合であっても一斉に演算を駆動するという作用をもたらす。
【００１９】
また、この第２の側面において、上記制御信号は、上記入力データが上記デコーダに入力されるタイミングを示すものであってもよい。これにより、デコーダに入力されるタイミングに合わせて一斉に演算を駆動するという作用をもたらす。
【００２０】
また、この第２の側面において、上記演算部は、上記４つのデコーダの全てが上記固定値を出力している間は４組の上記固定値からなる１６ビット幅のデータを出力するようにしてもよい。これにより、演算結果の遷移する期間を制限するという作用をもたらす。
【発明の効果】
【００２１】
本発明によれば、ダイナミックハザードに起因する消費電力の増加を一様に抑えて、ＤＰＡ攻撃を困難にすることができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００２２】
【図１】本発明において想定する暗号化および復号化の処理手順例を示す図である。
【図２】本発明において想定する暗号化および復号化の共通化した処理手順例を示す図である。
【図３】本発明において想定するＳｕｂＢｙｔｅｓ／Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９３１）の処理内容を示す図である。
【図４】既約多項式を用いた逆元演算回路の基本原理を示す図である。
【図５】本発明の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の構成例を示す図である。
【図６】本発明の実施の形態におけるデコーダ１１１乃至１１４およびエンコーダ１３１乃至１３４の構成例を示す図である。
【図７】本発明の実施の形態におけるデコーダ１１１乃至１１４の各々の動作の真理値表を示す図である。
【図８】本発明の実施の形態におけるエンコーダ１３１乃至１３４の各々の動作の真理値表を示す図である。
【図９】本発明の実施の形態におけるｘ2・λ演算回路１２１の構成例を示す図である。
【図１０】本発明の実施の形態におけるｘ2・λ演算回路１２１の動作の真理値表である。
【図１１】本発明の実施の形態における排他的論理和演算回路１２２および１２４の半分の構成例を示す図である。
【図１２】本発明の実施の形態における排他的論理和演算回路１２２および１２４の半分の構成例による動作の真理値表である。
【図１３】本発明の第１の実施の形態における排他的論理和演算回路１２２および１２４の動作タイミング例を示す図である。
【図１４】本発明の実施の形態におけるＧＦ（（２2）2）逆元演算回路１２５の構成例を示す図である。
【図１５】本発明の実施の形態におけるＧＦ（（２2）2）逆元演算回路１２５の構成例による動作の真理値表である。
【図１６】本発明の実施の形態における乗算回路１２３、１２６および１２７の構成例を示す図である。
【図１７】本発明の実施の形態におけるインバータ２３６の構成例を示す図である。
【図１８】本発明の実施の形態における否定排他的論理和演算回路２３１および２３２の構成例を示す図である。
【図１９】本発明の実施の形態における乗算回路２３３の構成例を示す図である。
【図２０】本発明の実施の形態における乗算回路２３３の構成例による動作の真理値表である。
【図２１】本発明の実施の形態における乗算φ演算回路２３４の構成例を示す図である。
【図２２】本発明の実施の形態における乗算φ演算回路２３４の構成例による動作の真理値表である。
【図２３】本発明の実施の形態における負論理乗算回路２３５の構成例を示す図である。
【図２４】本発明の実施の形態における負論理乗算回路２３５の構成例による動作の真理値表である。
【図２５】本発明の実施の形態における負論理入力排他的論理和演算回路２３７の構成例を示す図である。
【図２６】本発明の実施の形態における乗算回路１２３、１２６および１２７の動作タイミング例を示す図である。
【図２７】本発明の実施の形態によるＧＦ（（（２2）2）2）逆元演算回路１００の構成例における遅延量を示す図である。
【図２８】本発明の第１の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の動作タイミング例を示す図である。
【図２９】本発明の第２の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の動作タイミング例を示す図である。
【発明を実施するための形態】
【００２３】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（１ラウンドの処理を２相に分けて実行する例）
２．第２の実施の形態（１ラウンドの処理を１クロックサイクルで実行する例）
３．変形例
【００２４】
＜１．第１の実施の形態＞
［暗号化装置または復号化装置の構成］
図１は、本発明において想定する暗号化および復号化の処理手順例を示す図である。図１（ａ）は、メッセージを暗号化するための処理手順であり、ＳｕｂＢｙｔｅｓ（９１１）、ＳｈｉｆｔＲｏｗｓ（９１２）、ＭｉｘＣｏｌｕｍｎｓ（９１５）、ＡｄｄＲｏｕｎｄＫｅｙ（９１６）の各手順を含む。ＡＥＳ暗号の入力データは１２８ビットであるが、８ビットを単位とした４×４のマトリクスとして定義され、演算処理は８ビット単位で行われる。この１２８ビットの入力データは、ラウンド演算の開始前（Ｒｄ０）に入力され、ＡｄｄＲｏｕｎｄＫｅｙ（９１６）を経てレジスタ９１０に保持される。
【００２５】
ＳｕｂＢｙｔｅｓ（９１１）は、８ビットデータに対して逆元を計算し、アフィン変換を行うものである。ＳｈｉｆｔＲｏｗｓ（９１２）は、４×４のマトリクスの横方向（各行）に対して回転処理を行うものである。ＭｉｘＣｏｌｕｍｎｓ（９１５）は、４×４のマトリクスの縦方向（各列）に対して演算処理を行うものである。ＡｄｄＲｏｕｎｄＫｅｙ（９１６）は、ラウンド鍵（９１９）との排他的論理和（ＸＯＲ）演算を行うものである。レジスタ９１０には、各手順を１ラウンド行う度に（Ｒｄ１乃至１０）中間値が更新される。
【００２６】
この暗号化処理では、各手順を１０ラウンド繰り返した後にレジスタ９１０に保持された値が暗号として出力される。なお、最終ラウンド（Ｒｄ１０）では、ＭｉｘＣｏｌｕｍｎｓ（９１５）の処理は行われない。
【００２７】
図１（ｂ）は、暗号化されたメッセージを復号化するための処理手順であり、Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９２１）、Ｉｎｖ＿ＳｈｉｆｔＲｏｗｓ（９２２）、ＡｄｄＲｏｕｎｄＫｅｙ（９２３）、Ｉｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９２５）の各手順を含む。暗号化されたメッセージは、ラウンド演算の開始前（Ｒｄ１０）に入力され、ＡｄｄＲｏｕｎｄＫｅｙ（９２３）を経てレジスタ９２０に保持される。
【００２８】
Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９２１）は、ＳｕｂＢｙｔｅｓ（９１１）の逆の処理を行うものである。Ｉｎｖ＿ＳｈｉｆｔＲｏｗｓ（９２２）は、ＳｈｉｆｔＲｏｗｓ（９１２）の逆の処理を行うものである。ＡｄｄＲｏｕｎｄＫｅｙ（９２３）は、ラウンド鍵（９２８）との排他的論理和演算を行うものである。Ｉｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９２５）は、ＭｉｘＣｏｌｕｍｎｓ（９１５）の逆の処理を行うものである。レジスタ９２０には、各手順を１ラウンド行う度に（Ｒｄ９乃至０）中間値が更新される。
【００２９】
この復号化処理では、各手順を１０ラウンド繰り返した後にレジスタ９２０に保持された値が復号化されたメッセージとして出力される。なお、最終ラウンド（Ｒｄ０）では、Ｉｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９２５）の処理は行われない。
【００３０】
ここで、ＳｕｂＢｙｔｅｓ（９１１）およびＳｈｉｆｔＲｏｗｓ（９１２）とＩｎｖ＿ＳｕｂＢｙｔｅｓ（９２１）およびＩｎｖ＿ＳｈｉｆｔＲｏｗｓ（９２２）とは対になる処理であるため、暗号化処理と復号化処理との間で共通化することができる。ＭｉｘＣｏｌｕｍｎｓ（９１５）とＩｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９２５）との間も同様である。そこで、次のように両者を共通化した処理手順として実現した場合のイメージを示す。
【００３１】
図２は、本発明において想定する暗号化および復号化の共通化した処理手順例を示す図である。ＳｕｂＢｙｔｅｓ／Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９３１）は、ＳｕｂＢｙｔｅｓ（９１１）とＩｎｖ＿ＳｕｂＢｙｔｅｓ（９２１）とを共通化したものである。ＳｈｉｆｔＲｏｗｓ／Ｉｎｖ＿ＳｈｉｆｔＲｏｗｓ（９３２）は、ＳｈｉｆｔＲｏｗｓ（９１２）とＩｎｖ＿ＳｈｉｆｔＲｏｗｓ（９２２）とを共通化したものである。ＡｄｄＲｏｕｎｄＫｅｙ（９３３）は、ＡｄｄＲｏｕｎｄＫｅｙ（９２３）と同様に、ラウンド鍵（９２８）との排他的論理和演算を行うものである。選択手順９３４は、暗号化時にＡｄｄＲｏｕｎｄＫｅｙ（９３３）を経ない値を選択し、復号化時にＡｄｄＲｏｕｎｄＫｅｙ（９３３）の出力を選択するものである。ＭｉｘＣｏｌｕｍｎｓ／Ｉｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９３５）は、ＭｉｘＣｏｌｕｍｎｓ（９１５）とＩｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９２５）とを共通化したものである。ＡｄｄＲｏｕｎｄＫｅｙ（９３６）は、ＡｄｄＲｏｕｎｄＫｅｙ（９１６）と同様に、ラウンド鍵（９１９）との排他的論理和演算を行うものである。選択手順９３７は、暗号化時にＡｄｄＲｏｕｎｄＫｅｙ（９３６）の出力を選択し、復号化時にＡｄｄＲｏｕｎｄＫｅｙ（９３６）を経ない値を選択するものである。レジスタ９３０は、レジスタ９１０とレジスタ９２０とを共通化したものであり、暗号化または復号化の中間値を保持するものである。
【００３２】
図３は、本発明において想定するＳｕｂＢｙｔｅｓ／Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９３１）の処理内容を示す図である。このＳｕｂＢｙｔｅｓ／Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９３１）を、以下ではＳｂｏｘと呼称する。上述のレジスタ９３０の出力は、別の演算回路に入力されることなく、このＳｂｏｘに入力される。このＳｂｏｘは、暗号化時と復号化時とで共通化されているため、両者を切り換えるスイッチ３４および３８を備えている。
【００３３】
Ｓｂｏｘにおいて、暗号化時には、同形写像変換回路１２において写像変換δを行い、逆元演算回路１００においてＧＦ（（（２2）2）2）上の逆元演算を行う。そして、逆同形写像変換・アフィン変換回路１６において逆写像変換δ-1とアフィン変換を行った後に排他的論理和（ＸＯＲ）演算回路１７により排他的論理和演算を行う。
【００３４】
一方、復号化時には、排他的論理和演算回路２１により排他的論理和演算を行った後に逆アフィン変換・同形写像回路２２において逆アフィン変換と写像変換δを行う。そして、逆元演算回路１００においてＧＦ（（（２2）2）2）上の逆元演算を行う。その後、逆同形写像回路２６において逆写像変換δ-1を行う。
【００３５】
［逆元演算回路の構成］
図４は、既約多項式を用いた逆元演算回路の基本原理を示す図である。図４（ａ）は、８ビットのＧＦ（（（２2）2）2）逆元演算回路である。ここでは、入力データの上位４ビットをＰH、下位４ビットをＰLにより表し、出力データの上位４ビットをＰH-1、下位４ビットをＰL-1により表している。逆元演算回路は階層的な構造を有し、合成体ＧＦ（（（２2）2）2）上の逆元演算は、以下の部分体ＧＦ（（２2）2）の演算回路を組み合わせることにより実現される。すなわち、このＧＦ（（（２2）2）2）逆元演算回路は、ｘ2・λ演算回路８１１と、排他的論理和演算回路８１２および８１４と、乗算回路８１３、８１６および８１７と、逆元演算回路８２０とを備える。
【００３６】
図４（ｂ）は、４ビットのＧＦ（（２2）2）逆元演算回路８２０である。合成体ＧＦ（（２2）2）上の逆元演算は、以下の部分体ＧＦ（２2）の演算を組み合わせることにより実現される。すなわち、このＧＦ（（２2）2）逆元演算回路８２０は、ｘ2・φ演算回路８２１と、排他的論理和演算回路８２２および８２４と、乗算回路８２３、８２６および８２７と、逆元演算回路８３０とを備える。
【００３７】
上述のとおり、この逆元演算回路の基本原理をそのまま利用した場合、ダイナミックハザードによる中間値への遷移のため、ＤＰＡ攻撃の対象とされるおそれが生じる。そこで、本発明の実施の形態では、逆元演算回路の前段にデコーダを配置して、逆元演算回路をデコードデータによるテーブル回路で構成することにより、演算によるゲート遅延を削減する。そして、それとともに、演算回路の入力が全て確定するまで固定値を出力する構成を採ることにより、中間値への遷移を抑止するように制御を行う。
【００３８】
図５は、本発明の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の構成例を示す図である。このＧＦ（（（２2）2）2）逆元演算回路１００は、４つのデコーダ１１１乃至１１４と、演算部１２０と、４つのエンコーダ１３１乃至１３４とを備えている。
【００３９】
デコーダ１１１乃至１１４は、８ビットの入力データのうちそれぞれ２ビットずつをデコードして、それぞれ４ビットのデコードデータを出力するものである。デコーダ１１１乃至１１４は、共通する制御信号ＰＣｄｌｙ（Phase Control delay）によって動作タイミングを制御される。なお、ここでは４つのデコーダ１１１乃至１１４を用いた例について説明するが、これらは一体化したものでもよく、また、任意の数に分割したものでもよい。
【００４０】
演算部１２０は、デコーダ１１１乃至１１４から出力された１６ビットのデコードデータに対してＧＦ（（（２2）2）2）逆元演算を行うものである。部分体で使用する規約多項式が決まっている場合、合成体上での演算で、１つまたは２つの４ビット入力が決まれば、出力の４ビットは自動的に決まる。そして、ここでは、２ビット単位でデコードしたデータで演算がなされるものとしている。この演算部１２０は、図４（ａ）の基本原理に準じた構成を備えており、ｘ2・λ演算回路１２１と、排他的論理和演算回路１２２および１２４と、乗算回路１２３、１２６および１２７と、ＧＦ（（２2）2）逆元演算回路１２５とを備える。各回路の構成についてはさらに後述する。
【００４１】
エンコーダ１３１乃至１３４は、演算部１２０から出力された１６ビットのデコードデータのうちそれぞれ４ビットずつをエンコードして、それぞれ２ビットのバイナリデータを出力するものである。なお、ここでは４つのエンコーダ１３１乃至１３４を用いた例について説明するが、これらは一体化したものでもよく、また、任意の数に分割したものでもよい。
【００４２】
図６は、本発明の実施の形態におけるデコーダ１１１乃至１１４およびエンコーダ１３１乃至１３４の構成例を示す図である。
【００４３】
図６（ａ）は、デコーダ１１１乃至１１４の構成例である。ここでは、デコーダ１１１の内部を代表として示しているが、デコーダ１１２乃至１１４についても同様の構成を備える。デコーダ１１１は、８ビットの入力データのうち上位の２ビットｂ６およびｂ７を入力として、ｂ６およびｂ７ならびにこれらの反転信号を組み合わせて４ビットのデコードデータを生成する。このデコーダ１１１は、インバータと否定論理和（ＮＯＲ）演算回路の２ゲート遅延を有する。また、否定論理和演算回路には制御信号ＰＣｄｌｙが入力され、この制御信号ＰＣｄｌｙが「１」を示す間は、デコードデータは所定の固定値になる。本発明の実施の形態では、所定の固定値としてデコードデータを全ビット「０」にすることを想定している。
【００４４】
図６（ｂ）は、エンコーダ１３１乃至１３４の構成例である。ここでは、エンコーダ１３１の内部を代表として示しているが、エンコーダ１３２乃至１３４についても同様の構成を備える。エンコーダ１３１は、１６ビットのデコードデータのうち上位の４ビットを入力として、ｄ０乃至ｄ３を組み合わせて２ビットのエンコードデータを生成する。このエンコーダ１３１は、否定論理和演算回路とインバータの２ゲート遅延を有する。
【００４５】
図７は、本発明の実施の形態におけるデコーダ１１１乃至１１４の各々の動作の真理値表を示す図である。上述のようにデコーダ１１１乃至１１４の各々には２ビットの入力データと制御信号ＰＣｄｌｙが入力される。制御信号ＰＣｄｌｙが「１」の場合、入力データにかかわらず、デコードデータは「００００」になる。制御信号ＰＣｄｌｙが「０」の場合、入力データに応じて、４ビットのデコードデータのうち１ビットだけが「１」となり、他のビットは「０」になる。
【００４６】
これにより、制御信号ＰＣｄｌｙのタイミングに合わせてデコードデータを「００００」にリセットして、その後、入力データに応じてデコードデータの４ビットのうち１ビットだけを「１」にするという遷移を実現することができる。
【００４７】
図８は、本発明の実施の形態におけるエンコーダ１３１乃至１３４の各々の動作の真理値表を示す図である。デコードデータが「１」を示すビット位置に応じて、出力データが決定される。ここで、出力データが定義されるのは、４ビットのデコードデータのうち１ビットだけが「１」となり、他のビットが「０」となっている場合、および、４ビットのデコードデータが全て「０」となっている場合である。これ以外の場合は未定義である。図６（ｂ）の構成例では、この性質を利用して、４ビットのうち下位１ビットを参照することなくバイナリデータを生成している。
【００４８】
図９は、本発明の実施の形態におけるｘ2・λ演算回路１２１の構成例を示す図である。また、図１０は、本発明の実施の形態におけるｘ2・λ演算回路１２１の動作の真理値表である。デコード前の２進数データによりｘ2・λ演算の真理値表を作成すると、図１０（ａ）に示すようになる。図７の関係を利用してデコードデータによるｘ2・λ演算の真理値表を作成すると、図１０（ｂ）に示すようになる。図９は図１０（ｂ）の関係を組合せ回路により実現したものである。
【００４９】
このｘ2・λ演算回路１２１では、下位４ビットの出力については、インバータ２１１または否定論理和演算回路２１２と否定論理和演算回路２１３との２ゲート遅延により演算が行われる。また、上位４ビットの出力については、論理積−否定論理和演算回路２１４とインバータ２１５との２ゲート遅延により演算が行われる。したがって、上位および下位の演算結果は、データにかかわらず等しく２ゲート遅延により出力される。また、このｘ2・λ演算回路１２１に、２進数データでは定義されないデコードデータとして「００００＿００００」が入力された場合、「００００＿００００」を出力する。
【００５０】
図１１は、本発明の実施の形態における排他的論理和演算回路１２２および１２４の半分の構成例を示す図である。また、図１２は、本発明の実施の形態における排他的論理和演算回路１２２および１２４の半分の構成例による動作の真理値表である。排他的論理和演算回路では、各ビットは独立して動作するため、半分の規模の排他的論理和演算回路を並列配置することにより回路を構成することができる。したがって、ここでは、デコード後の８ビット幅の排他的論理和演算回路１２２および１２４を、４ビット幅の排他的論理和演算回路の並列配置により実現する構成例について説明する。
【００５１】
デコード前の２進数データにより排他的論理和演算の真理値表を作成すると、図１２（ａ）に示すようになる。図７の関係を利用してデコードデータによる排他的論理和演算の真理値表を作成すると、図１２（ｂ）に示すようになる。図１１は図１２（ｂ）の関係を組合せ回路により実現したものである。この排他的論理和演算回路では、論理積−否定論理和演算回路２２１とインバータ２２２との２ゲート遅延により演算が行われる。また、この排他的論理和演算回路の２つのデコード入力のうち、少なくとも一方のデコード入力に「００００」が入力された場合、入力信号は論理積−否定論理和演算回路２２１により受けているため、排他的論理和演算回路１２２または１２４は「００００」を出力する。
【００５２】
図１３は、本発明の第１の実施の形態における排他的論理和演算回路１２２および１２４の動作タイミング例を示す図である。本発明の第１の実施の形態では、１ラウンドの動作をプリチャージ相とエバリュエーション相の２相に分けて交互に行うようにフェーズ制御（ＰＣ：Phase Control）を行う。プリチャージ相では、出力は一旦「００００」にリセットされる。そして、エバリュエーション相では２つの入力が何れも「００００」以外になった後、さらに演算遅延が経過した後に排他的論理和演算結果が出力される。この排他的論理和演算結果は、デコードデータであるため、１ビットだけが「１」であり、それ以外のビットは「０」を示す。したがって、プリチャージ相でリセットされた「００００」から１ビットだけが、エバリュエーション相において「１」に遷移する。また、２つの入力の変化タイミングに遅延差がある場合、両方のデータが確定するまで「００００」が出力される。そして、両方のデータが確定した後に排他的論理和演算を実行して、演算結果に遷移する。このとき、中間値への遷移は起こらない。
【００５３】
図１４は、本発明の実施の形態におけるＧＦ（（２2）2）逆元演算回路１２５の構成例を示す図である。また、図１５は、本発明の実施の形態におけるＧＦ（（２2）2）逆元演算回路１２５の構成例による動作の真理値表である。デコード前の２進数データによりＧＦ（（２2）2）逆元演算の真理値表を作成すると、図１５（ａ）に示すようになる。図７の関係を利用してデコードデータによるＧＦ（（２2）2）逆元演算の真理値表を作成すると、図１５（ｂ）に示すようになる。図１４は図１５（ｂ）の関係を組合せ回路により実現したものである。
【００５４】
このＧＦ（（２2）2）逆元演算回路１２５では、論理積−否定論理和演算回路２５１とインバータ２５２との２ゲート遅延により演算が行われる。したがって、このＧＦ（（２2）2）逆元演算回路１２５における演算結果は、データにかかわらず等しく２ゲート遅延により出力される。また、このＧＦ（（２2）2）逆元演算回路１２５に、２進数データでは定義されないデコードデータとして「００００＿００００」が入力された場合、「００００＿００００」を出力する。
【００５５】
図１６は、本発明の実施の形態における乗算回路１２３、１２６および１２７の構成例を示す図である。４ビットの２進数データ（デコードデータでは８ビット）を入力とする乗算回路では、入力の組み合わせは２4×２4＝２５６通りになる。これをテーブルで構成すると、回路規模は他のテーブルを用いた４ビット演算回路（例えば逆元演算回路）の１６倍となり、回路規模が各段に大きくなる。ここでは、回路規模を削減するため、部分体ＧＦ（（２2）2）での乗算器を用いて構成する例を示す。
【００５６】
部分体ＧＦ（（２2）2）での乗算器は、図１６に示すように４ビットのデコードデータの排他的論理和演算回路および４ビットのデコードデータの乗算回路により構成される。また、遅延時間を考慮して一部の回路の入力または出力は負論理になっている。すなわち、この回路は、否定排他的論理和（ＸＮＯＲ）演算回路２３１および２３２と、乗算回路２３３と、乗算φ演算回路２３４と、負論理乗算回路２３５と、インバータ２３６と、負論理入力排他的論理和演算回路２３７と、排他的論理和演算回路２３８とを備える。そして、演算器２３１乃至２３８は、デコードデータの演算をする演算器である。なお、排他的論理和演算回路２３８は図１１に示した回路をそのまま利用することができる。また、インバータ２３６は、入力がデコードデータの場合、図１７に示すように、配線のみで実現でき、乗算器の演算遅延に影響を与えない。
【００５７】
図１８は、本発明の実施の形態における否定排他的論理和演算回路２３１および２３２の構成例を示す図である。この回路は、図１１の排他的論理和演算回路において最終段のインバータを取り除いたものになっている。したがって、この否定排他的論理和演算回路２３１および２３２では、論理積−否定論理和演算回路３１１による１ゲート遅延により演算が行われる。
【００５８】
図１９は、本発明の実施の形態における乗算回路２３３の構成例を示す図である。また、図２０は、本発明の実施の形態における乗算回路２３３の構成例による動作の真理値表である。デコード前の２進数データにより乗算の真理値表を作成すると、図２０（ａ）に示すようになる。図７の関係を利用してデコードデータによる乗算の真理値表を作成すると、図２０（ｂ）に示すようになる。図１９は図２０（ｂ）の関係を組合せ回路により実現したものである。
【００５９】
この乗算回路２３３では、最下位ビットｄ０を出力するために、否定論理和（ＮＯＲ）演算回路３３１と否定論理和演算回路３３２との２ゲート遅延により演算が行われる。上位３ビットを出力するために、論理積−否定論理和演算回路３３３と、インバータ３３４との２ゲート遅延により演算が行われる。したがって、この乗算回路２３３における演算結果は、データにかかわらず等しく２ゲート遅延により出力される。また、この乗算回路２３３の２つの入力のうちの少なくとも一方の入力に、２進数データでは定義されないデコードデータとして「００００」が入力された場合、「００００」を出力する。
【００６０】
図２１は、本発明の実施の形態における乗算φ演算回路２３４の構成例を示す図である。また、図２２は、本発明の実施の形態における乗算φ演算回路２３４の構成例による動作の真理値表である。デコード前の２進数データにより乗算φ演算の真理値表を作成すると、図２２（ａ）に示すようになる。図７の関係を利用してデコードデータによる乗算の真理値表を作成すると、図２２（ｂ）に示すようになる。図２１は図２２（ｂ）の関係を組合せ回路により実現したものである。
【００６１】
この乗算φ演算回路２３４は、乗算結果にφ（＝１０）を乗じた値を出力するものであるが、φが固定値であるため、図１９の乗算回路２３３の出力のビット順序を変更することにより実現可能である。したがって、この乗算φ演算回路２３４における演算結果は、乗算回路２３３と同様に、データにかかわらず等しく２ゲート遅延により出力される。また、この乗算φ演算回路２３４の２つの入力のうちの少なくとも一方の入力に、２進数データでは定義されないデコードデータとして「００００」が入力された場合、「００００」を出力する。
【００６２】
図２３は、本発明の実施の形態における負論理乗算回路２３５の構成例を示す図である。また、図２４は、本発明の実施の形態における負論理乗算回路２３５の構成例による動作の真理値表である。この負論理乗算回路２３５は、入力および出力ともに負論理となっている。
【００６３】
この負論理乗算回路２３５では、最下位ビット／ｄ０を出力するために、否定論理積（ＮＡＮＤ）演算回路３５１と否定論理積演算回路３５２との２ゲート遅延により演算が行われる。上位３ビットを出力するために、論理和−否定論理積演算回路３５３と、インバータ３５４との２ゲート遅延により演算が行われる。したがって、この負論理乗算回路２３５における演算結果は、データにかかわらず等しく２ゲート遅延により出力される。また、この負論理乗算回路２３５の少なくとも何れか一方の入力に、２進数データでは定義されないデコードデータ「００００」の負論理の値「１１１１」が入力された場合、負論理の値「１１１１」を出力する。
【００６４】
図２５は、本発明の実施の形態における負論理入力排他的論理和演算回路２３７の構成例を示す図である。この負論理入力排他的論理和演算回路２３７は、入力のみが負論理となっている。
【００６５】
この負論理入力排他的論理和演算回路２３７では、各ビットを出力するために、論理和−否定論理積演算回路３７１の１ゲート遅延により演算が行われる。したがって、この負論理入力排他的論理和演算回路２３７における演算結果は、データにかかわらず等しく１ゲート遅延により出力される。また、この負論理入力排他的論理和演算回路２３７の何れか一方の入力に、２進数データでは定義されないデコードデータ「００００」の負論理の値「１１１１」が入力された場合、「００００」を出力する。
【００６６】
これらの回路構成により、４ビット乗算回路１２３、１２６および１２７は、上位２ビットおよび下位２ビットともに、遅延時間は４ゲート遅延となる。また、４ビット乗算回路としてみた場合、入力も出力も正論理の動作となる。
【００６７】
図２６は、本発明の実施の形態における乗算回路１２３、１２６および１２７の動作タイミング例を示す図である。本発明の第１の実施の形態では、上述のように、１ラウンドの動作をプリチャージ相とエバリュエーション相の２相に分けて交互に行うようにフェーズ制御を行う。プリチャージ相では、出力は一旦「００００」にリセットされる。そして、エバリュエーション相では２つの入力が何れも「００００」以外になった後、さらに演算遅延が経過した後に乗算演算結果が出力される。この乗算演算結果は、デコードデータであるため、１ビットだけが「１」であり、それ以外のビットは「０」を示す。したがって、プリチャージ相でリセットされた「００００」から１ビットだけが、エバリュエーション相において「１」に遷移する。また、２つの入力の変化タイミングに遅延差がある場合、両方のデータが確定するまで「００００」が出力される。そして、両方のデータが確定した後に乗算動作を実行して、実行結果に遷移する。このとき、中間値への遷移は起こらず、したがって、中間値遷移による電流も発生しない。
【００６８】
［逆元演算回路の遅延量］
図２７は、本発明の実施の形態によるＧＦ（（（２2）2）2）逆元演算回路１００の構成例における演算データの信号経路を示す図である。
【００６９】
上述のように、ｘ2・λ演算回路１２１では２ゲート遅延を要し、排他的論理和演算回路１２２または１２４では２ゲート遅延を要し、乗算回路１２３、１２６または１２７では４ゲート遅延を要し、ＧＦ（（２2）2）逆元演算回路１２５では２ゲート遅延を要する。そして、これらの演算回路を通る演算データの信号経路は、経路Ａ乃至Ｅの５つの信号経路が存在する。この中で、最も回路動作による遅延が大きいのは経路Ｂで、その遅延は１４ゲート遅延ある。他の経路での、通過する演算回路による遅延の積算は、経路Ａで１０ゲート遅延、経路Ｃで１２ゲート遅延、経路Ｄで４ゲート遅延、そして、経路Ｅで６ゲート遅延である。しかし、２つの入力データから演算結果を生成する「排他的論理和演算回路」および「乗算回路」は、２つの入力のうち少なくとも一方が固定値の場合は固定値を出力し、２つの入力が共にデコード値になってから演算動作を開始する。そして、その出力は、排他的論理和演算回路では２ゲート遅延後、乗算回路では４ゲート遅延後、固定値から演算結果に遷移する。５つの演算経路には、「排他的論理和演算回路」および「乗算回路」の２入力演算器の少なくとも１つが配置されている。そして、２入力演算器の２つの入力が有効値になるタイミングは異なる場合が多いが、２入力演算器は２つの入力の少なくとも一方が固定値の場合は固定値を出力し、両方の入力が有効値になってから所定時間経過後に出力は固定値から演算結果に遷移する。したがって、異なる遅延で入力された２つの経路の信号は、２入力演算器を通過した後は遅い方の経路の遅延タイミングに一致して以降の回路に入力される。例えば、ＧＦ（（２2）2）逆元演算回路１２５の出力となる経路Ａ乃至Ｃは、全て最も回路遅延の積算の大きい経路Ｂの遅延と一致して乗算器１２６および１２７に入力される。経路Ｄのデータは、遅延なく乗算器１２６に入力されるが、他方の入力遅延が経路Ｂのタイミングとなるため、乗算器１２６を経た経路Ｄのタイミングも経路Ｂのタイミングと一致する。同様に、乗算器１２７を経た経路Ｅのタイミングも経路Ｂのタイミングと一致する。これらより、全ての演算経路においてデータが確定するのは、経路Ｂの遅延である１４ゲート遅延後となる。
【００７０】
このデコードデータによる逆元演算回路では、入力部にはデコーダ１１１乃至１１４のデコード回路が、出力部にはエンコーダ１３１乃至１３４がそれぞれ配置され、各々２ゲート遅延を要する。これは全ての信号パスに共通に付加される遅延時間で、結局、ＧＦ（（（２2）2）2）逆元演算回路１００の演算遅延時間は、演算パスに関わらず１８ゲート遅延となる。また、この演算回路では、２入力の演算回路の場合、両方の入力が確定してから演算が開始され、その演算器の演算遅延後に出力が固定値から演算結果に遷移する構成となっているため、各演算経路で中間値への遷移は起こらない。そして、各演算器の出力が固定値からデコード値に変化した時、変化する信号線は出力値にかかわらずデコード単位で１本であるため、ＤＰＡ攻撃で鍵が取り出される可能性は低くなる。また、遅延時間が短縮されたことにより、動作周波数を高く設定することができる。
【００７１】
［逆元演算回路の動作］
図２８は、本発明の第１の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の動作タイミング例を示す図である。この第１の実施の形態では、１ラウンドの動作をプリチャージ相とエバリュエーション相の２相に分けて交互に行うようにフェーズ制御の制御信号ＰＣが変化する。プリチャージ相ではレジスタ９３０の出力が一旦「００００」にリセットされ、エバリュエーション相ではレジスタ９３０に保持された値が出力される。
【００７２】
図２および図３により説明したように、レジスタ９３０からＧＦ（（（２2）2）2）逆元演算回路１００への入力はある程度の遅延を伴う。そこで、この遅延タイミングにあわせた制御信号ＰＣｄｌｙ（Phase Control delay）が利用される。この制御信号ＰＣｄｌｙは、制御信号ＰＣと同じタイミングで立ち上がり、制御信号ＰＣの立下り後、レジスタ９３０からＧＦ（（（２2）2）2）逆元演算回路１００までの回路動作による遅延時間に若干のマージンを見込んだ時間経過後に立ち下がる。すなわち、図６により説明したように、この制御信号ＰＣｄｌｙは、デコーダ１１１乃至１１４からデコードデータが演算部１２０へ出力されるタイミングを示す。この制御信号ＰＣｄｌｙはデコーダ１１１乃至１１４に入力され、制御信号ＰＣｄｌｙが「１」を示している間、デコードデータは入力データにかかわらず「００００」になる。一方、制御信号ＰＣｄｌｙが「０」を示している間、デコーダ１１１乃至１１４から入力データに応じたデコードデータが出力される。
【００７３】
プリチャージ相では、クロックの立上りに同期して制御信号ＰＣが「１」になり、レジスタからの信号は全て「０」に制御される。これが伝播して、各回路ブロックのノードは順次プリチャージレベルに遷移していく。そして、制御信号ＰＣの立上りに同期して制御信号ＰＣｄｌｙも「１」に遷移し、デコード回路１１１乃至１１４からのデコード出力は全て「００００」に制御されて、ＧＦ（（（２2）2）2）のデコードデータによる逆元演算回路１２０へ入力される。これにより、４ゲート遅延後に乗算回路１２６のデコード出力が、６ゲート遅延後に乗算回路１２７のデコード出力がそれぞれ「００００＿００００」となる。
【００７４】
エバリュエーション相では、制御信号ＰＣが「０」になり、レジスタ９３０に保持された値が出力されるようになる。これにより、各回路ブロックで演算が開始され、演算結果が次の回路に供給されていく。そして、所定時間経過後、ＧＦ（（（２2）2）2）逆元演算回路１００に演算結果が供給される。制御信号ＰＣｄｌｙは、レジスタ９３０の出力からＧＦ（（（２2）2）2）逆元演算回路１００の入力までの演算時間に若干のマージンを見込んだ時間を発生させる遅延回路によって発生されるタイミングで「０」に遷移する。これにより、制御信号ＰＣｄｌｙが「０」になった時点で、ＧＦ（（（２2）2）2）逆元演算回路１００の入力信号のデコードデータがＧＦ（（（２2）2）2）逆元演算回路１００に入力されて演算が実行される。そして、１４ゲート遅延経過後、乗算器１２６および１２７の出力は各々ほぼ同時に「００００＿００００」から演算結果に遷移する。
【００７５】
このとき、演算結果の出力端に、ＤＰＡ攻撃の対象となる演算の中間値が現れることはない。そして、エバリュエーション相で、ＧＦ（（（２2）2）2）逆元演算回路１００の入力ＰHおよびＰLならびに出力ＰH-1およびＰL-1は、「００００＿００００」からデコードデータに変化するだけである。すなわち、デコードデータは４本の信号線毎に１本だけ「１」に変化するだけであるため、配線容量に差異がないと仮定した場合、入力値および出力値に関係なく信号変化に伴う配線の充放電電流は一定である。そのため、ＧＦ（（（２2）2）2）逆元演算回路１００に対するＤＰＡ攻撃は困難となる。また、ＧＦ（（（２2）2）2）逆元演算回路１００の内部動作においても、各演算ブロックの出力信号は、プリチャージ相で設定された固定値「００００」からデコードデータに変化するだけで、変化は４本の信号線で１本だけとなる。したがって、ＧＦ（（（２2）2）2）逆元演算回路１００の内部動作電流に対するＤＰＡ攻撃も困難となる。
【００７６】
このように、本発明の第１の実施の形態では、デコードデータで動作する演算回路を用いて、プリチャージ相において各演算回路出力のデコードデータを「００００」にリセットし、エバリュエーション相で１ビットだけ「１」に変化させる。これにより、逆元演算時の中間値への遷移を抑止することができる。
【００７７】
＜２．第２の実施の形態＞
上述の第１の実施の形態では１ラウンドの処理をプリチャージ相およびエバリュエーション相の２相に分けて実行したが、この第２の実施の形態では１ラウンドの処理を１クロックサイクルで実行することを想定する。
【００７８】
本発明の第２の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路の回路構成は、上述の第１の実施の形態において説明したものと同様である。したがって、ゲート遅延も第１の実施の形態の場合と同様であり、少ないゲート遅延による逆元演算が可能となる。ただし、制御信号ＰＣｄｌｙのタイミングが第１の実施の形態の場合とは異なる。
【００７９】
［逆元演算回路の動作］
図２９は、本発明の第２の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の動作タイミング例を示す図である。この第２の実施の形態では、レジスタ９３０の出力からＧＦ（（（２2）2）2）逆元演算回路１００までの演算パスの遅延時間にマージンを加えた時間が経過した後に、制御信号ＰＣｄｌｙが「１」から「０」に変化するように制御される。すなわち、この制御信号ＰＣｄｌｙは、演算部１２０への入力データがデコーダ１１１乃至１１４から出力されるタイミングを示すことになる。
【００８０】
クロックの立上りで、レジスタ９３０の出力は更新され、更新データによるラウンド演算が開始される。これと同時に制御信号ＰＣｄｌｙも「１」になり、ＧＦ（（（２2）2）2）逆元演算回路１００の入力信号はデコーダ１１１乃至１１４によって「００００＿００００」に制御され、この入力を受けてＧＦ（（（２2）2）2）逆元演算回路１００が動作する。そして、エンコーダ１３１乃至１３４の入力も「００００＿００００」になる。このときの出力変化は、直前のデコードデータに関わらず、４本の信号線で１本だけ「０」に変化する。
【００８１】
レジスタ９３０の出力からＧＦ（（（２2）2）2）逆元演算回路１００までの演算パスの遅延時間にマージンを加えた時間が経過した後、制御信号ＰＣｄｌｙは「０」となり、ＧＦ（（（２2）2）2）逆元演算回路１００に到達している演算データがデコードされる。これにより、ＧＦ（（（２2）2）2）逆元演算回路１００が動作を開始する。
【００８２】
そして、１４ゲート遅延後に乗算回路１２６および１２７の出力も「００００＿００００」から演算結果に遷移する。このときの出力変化も、４本の信号線で１本だけ「１」に変化する。
【００８３】
このように、本発明の第２の実施の形態によれば、レジスタ９３０の出力からの遅延時間にマージンを加えたタイミングで制御信号ＰＣｄｌｙを制御することにより、逆元演算時の中間値への遷移を抑止することができる。
【００８４】
＜３．変形例＞
上述の実施の形態ではＲｉｊｎｄｅａｌへの適用例について説明したが、数値演算でＳｂｏｘ値を生成する他の暗号にも本発明は適用可能である。例えば、ＡＥＳと同様な構成をとる次世代暗号として、Ｃａｍｅｌｌｉａ、Ｈｉｅｒｏｃｒｙｐｔ等にも適用することができる。
【００８５】
このように、本発明の実施の形態によれば、ＧＦ（（（２2）2）2）逆元演算回路１００において入力データを制御信号ＰＣｄｌｙにより固定値とデコード値の切り替えを制御し、逆元演算後に演算結果をエンコードすることにより、中間値への遷移を抑止することができる。また、逆元演算サイクル数が少ないため、中間値への遷移の確率およびその遷移時間も短く、中間値遷移による消費電流の増加を抑えることができる。そして、それと同時に、高い周波数での動作が可能となる。また、逆元演算回路において、２入力回路での入力遅延の差による中間値への遷移がほとんど発生しないため、その遷移に伴う電流に対するＤＰＡ攻撃が困難になる。また、逆元演算回路の入出力信号の変化は、固定値（例えば「００００＿００００」）から演算結果のデコード値への変化またはその逆であるため、変化する信号線は例えば４本に付き常に１本であり、これは入出力データに依存しない。そのため、入出力信号の変化に対するＤＰＡ攻撃は困難になる。
【００８６】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、本発明の実施の形態において明示したように、本発明の実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本発明の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【符号の説明】
【００８７】
１２ 同形写像変換回路
１６ 逆同形写像・アフィン変換回路
２２ 逆アフィン変換・同形写像変換回路
２６ 逆同形写像変換回路
１７、２１ 排他的論理和（ＸＯＲ）演算回路
３４、３８ スイッチ
１００ ＧＦ（（（２2）2）2）逆元演算回路
１１１〜１１４ デコーダ
１２０ デコードデータによる逆元演算部
１２１ ｘ2・λ演算回路
１２２、１２４ 排他的論理和（ＸＯＲ）演算回路
１２３、１２６、１２７ 乗算回路
１２５ ＧＦ（（２2）2）逆元演算回路
１３１〜１３４ エンコーダ
２３１、２３２ 否定排他的論理和（ＸＮＯＲ）演算回路
２３３ 乗算回路
２３４ 乗算φ演算回路
２３５ 負論理乗算回路
２３６ インバータ
２３７ 負論理入力排他的論理和演算回路
２３８ 排他的論理和（ＸＯＲ）演算回路
９１０、９２０、９３０ レジスタ
【技術分野】
【０００１】
本発明は、ガロア体の逆元演算回路に関し、特にメッセージの暗号化または復号化の際に利用されるガロア体の逆元演算回路に関する。
【背景技術】
【０００２】
２００１年、米国国立標準技術研究所（ＮＩＳＴ）はＲｉｊｎｄｅａｌを次期米国標準の１２８ビット共通鍵ブロック暗号ＡＥＳ（Advanced Encryption Standard）として選出した。ＡＥＳの回路実装においては、演算速度の高速化や回路規模削減手法が学会等で報告されてきているが、それに加えて、低消費電力化やサイドチャンネル攻撃に対する耐性をもつ構成も近年報告されている。特に、従来の共通鍵ブロック暗号のＤＥＳ（Data Encryption Standard）の置換えとして用いる場合、電池動作の組込み機器への搭載や、非接触動作するＩＣカードへの搭載に際しては、消費電力に対する仕様は著しく制限される。
【０００３】
ＡＥＳ暗号の入力データは１２８ビットであるが、８ビットを単位とした４×４のマトリクスとして定義され、演算処理は８ビット単位で行われる。暗号化の際の演算処理としては、ＳｕｂＢｙｔｅｓ、ＳｈｉｆｔＲｏｗｓ、ＭｉｘＣｏｌｕｍｎｓ、ＡｄｄＲｏｕｎｄＫｅｙが行われる。ＳｕｂＢｙｔｅｓは、８ビットデータに対して逆元を計算し、アフィン変換を行うものである。ＳｈｉｆｔＲｏｗｓは、４×４のマトリクスの横方向（各行）に対して回転処理を行うものである。ＭｉｘＣｏｌｕｍｎｓは、４×４のマトリクスの縦方向（各列）に対して処理を行うものである。ＡｄｄＲｏｕｎｄＫｅｙは、ラウンド鍵との排他的論理和（ＸＯＲ）演算を行うものである。この中で、回路規模および消費電力が最も大きいのがＳｕｂＢｙｔｅｓである。このＳｕｂＢｙｔｅｓでは、８ビット入力８ビット出力のテーブル（Ｓｂｏｘ）が定義され、このテーブルに従った変換が行われる。このテーブルＳｂｏｘは、１６個必要とされる。
【０００４】
Ｓｂｏｘの主要な構成方法としては、（１）テーブルをランダムロジックにて構成する方法、（２）二分決定グラフにより構成する方法、（３）合成体上で逆元演算を行う数値演算回路により構成する方法が考えられる。これらを比較すると、一般的にゲート規模は（１）、（２）、（３）の順に小さくなり、ゲート規模の観点からは（３）の逆元演算が有利である。（３）の逆元演算では、ＡＥＳの仕様書に公開されているように、入力値を以下の既約多項式でのガロア体ＧＦ（２8）の要素とみなして演算する。
ｘ8＋ｘ4＋ｘ3＋ｘ＋１
【０００５】
Ｓｂｏｘの暗号化時の演算式は、暗号化演算時の８ビット入力を（ｂ７ ｂ６ ｂ５ ｂ４ ｂ３ ｂ２ ｂ１ ｂ０）、８ビット出力を（ｂ７' ｂ６' ｂ５' ｂ４' ｂ３' ｂ２' ｂ１' ｂ０'）としたとき、出力は以下の演算式により生成される。
【数１】
【０００６】
復号化演算時の８ビット入力を（ｂ７' ｂ６' ｂ５' ｂ４' ｂ３' ｂ２' ｂ１' ｂ０'）、８ビット出力を（ｂ７ ｂ６ ｂ５ ｂ４ ｂ３ ｂ２ ｂ１ ｂ０）としたとき、出力は以下の演算式により生成される。
【数２】
【０００７】
ガロア体上の演算では、基底が異なれば異なる演算になる。ＳｕｂＢｙｔｅｓで用いる既約多項式とは異なる体に合成体がある。ここで、合成体とは、素体から複数回の拡大により得られた体をいう。合成体上の乗算はさらに小さい合成体を用いて構成することができ、これにより、回路規模を削減することができる（例えば、非特許文献１参照。）。以下の既約多項式（式１）を使って得られる合成体ＧＦ（（（２2）2）2）上の逆元演算回路は、ＧＦ（２8）と同形な体上の逆元演算回路として得られる。
ＧＦ（２）→ＧＦ（２2）： ｘ2＋ｘ＋１
ＧＦ（２2）→ＧＦ（（２2）2）： ｘ2＋ｘ＋φ ・・・（式１）
ＧＦ（（２2）2）→ＧＦ（（（２2）2）2）： ｘ2＋ｘ＋λ
ただし、φ＝｛１０｝2、λ＝｛１１００｝2である。
【０００８】
逆元の演算は、もとの体Ａの元を同形写像δで合成体Ｂへマップし、合成体Ｂ上で逆元演算を実行した後、同形写像δ-1でもとの体Ａへマップするという手順で行われる。合成体ＧＦ（（（２2）2）2）上の逆元演算において、入力データを（ＰH，ＰL）、出力データを（ＰH-1, ＰL-1）としたとき、２つのデータの積は次式のようになる。
（ＰH・ｘ＋ＰL）・（ＰH-1・ｘ＋ＰL-1）
＝ＰH・ＰH-1・ｘ2＋（ＰH・ＰL-1＋ＰL・ＰH-1）ｘ＋ＰL・ＰL-1
＝ＰH・ＰH-1・（ｘ＋λ）＋（ＰH・ＰL-1＋ＰL・ＰH-1）・ｘ＋ＰL・ＰL-1
＝（ＰH・ＰH-1＋ＰH・ＰL-1＋ＰL・ＰH-1）・ｘ＋ＰH・ＰH-1・λ＋ＰL・ＰL-1
＝１
これにより、次式が得られる。
ＰH・ＰH-1＋ＰH・ＰL-1＋ＰL・ＰH-1＝０
ＰH・ＰH-1・λ＋ＰL・ＰL-1＝１
上式をＰH-1およびＰL-1について解くと、以下の式が得られる。
【数３】
【０００９】
この合成体上での８ビットの逆元演算を用いた（３）の構成では、回路規模は、他の２つの構成に比べて半分以下になるが、消費電流に関してはゲート規模の比率ほどは小さくならない。原因としては、乗算回路や逆元演算回路の２つの入力の遅延差に起因するダイナミックハザードが考えられる。このダイナミックハザードは後段に行くほど累積され、余分な電力消費が増加する。８ビットの逆元演算回路の最終段には、２つの４ビット乗算器が配置されるが、逆元演算回路への信号入力を起点とした時、上位側の乗算器の一方の入力は遅延ゼロでデータが入力されるのに対して、他方の入力は十数乃至三十数ゲートの遅延でデータが入力される。この間、出力は一旦中間値に遷移してから演算結果に遷移する。そして、遅延はビット毎に異なり、さらに、各ビット値が「０」か「１」かにより遅延は異なってくる。また、この逆元演算回路の入力信号も、ビット毎に異なるタイミングで入ってくる。これらにより、最終的な値に到達するまでに、８ビットの逆元演算回路は様々な中間値に遷移し、その度に演算回路での貫通電流および負荷で充放電電流を消費する。そして、この充放電電流は、消費電流を測定して、それに統計処理を施すことにより鍵を取り出すＤＰＡ（Difference Power Analysis）攻撃の対象となる。このようなＤＰＡ攻撃への対策の１つとして、遅延調整のための遅延回路を配置して、２入力演算回路の信号遅延差を調整する方法が提案されている（例えば、非特許文献１参照。）。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Sumio Morioka and Akashi Satoh : "An Optimized S-box circuit architecture for low power AES design", Workshop on Cryptographic Hardware and Embedded Systems 2002（CHES 2002），第１７２乃至１８６頁，２００２年８月
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上述のＤＰＡ攻撃に対処するために、遅延調整のための遅延回路を配置して、２入力演算回路の信号遅延差を調整する方法が提案されている。しかしながら、入力の遅延差は入力データ値によっても異なるため、すべてのデータに対して一様に消費電力を削減することは困難である。そして、削減できなかったハザード電流により、ＤＰＡ攻撃に対する脅威は依然残ってしまう。
【００１２】
本発明はこのような状況に鑑みてなされたものであり、ダイナミックハザードに起因する消費電力の増加を一様に抑えて、ＤＰＡ攻撃に対して耐性のある回路構成を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、ガロア体の入力データよりもビット幅が広い所定の固定値を一旦出力した後に、上記入力データに応じて上記固定値から所定ビット数だけ異なる値を示すデコードデータを出力するデコーダと、上記デコードデータに対してガロア体の逆元演算を実行して上記デコードデータの逆元データを出力する演算部と、上記逆元データを上記入力データと等しいビット幅の出力データにエンコードするエンコーダとを具備するガロア体の逆元演算回路である。これにより、固定値から所定ビット数だけ異なるデコードデータを演算対象として、中間値への遷移を抑止するという作用をもたらす。
【００１４】
また、この第１の側面において、上記デコーダは、制御信号に同期して上記固定値の出力を行うようにしてもよい。これにより、入力データの各ビットの遷移にばらつきがある場合であっても一斉に演算を駆動するという作用をもたらす。
【００１５】
また、この第１の側面において、上記制御信号は、上記入力データが上記デコーダに入力されるタイミングを示すものであってもよい。これにより、デコーダに入力されるタイミングに合わせて一斉に演算を駆動するという作用をもたらす。
【００１６】
また、この第１の側面において、上記演算部は、上記デコーダから上記固定値が出力されている間は上記固定値を出力するようにしてもよい。これにより、演算結果の遷移する期間を制限するという作用をもたらす。
【００１７】
また、本発明の第２の側面は、ガロア体の８ビットの入力データを２ビットずつに区切った４組の部分データに対してそれぞれ４ビット幅の固定値を一旦出力した後に、上記部分データに応じて上記固定値から１ビットだけ異なる４ビット幅のデコードデータをそれぞれ出力する４つのデコーダと、上記４組のデコードデータからなる１６ビットデータに対して逆元演算を実行して上記１６ビットデータの逆元データを出力する演算部と、上記逆元データを４ビットずつに区切ってそれぞれ２ビット幅の出力データにエンコードする４つのエンコーダとを具備するガロア体の逆元演算回路である。これにより、固定値から４ビット中１ビットだけ異なるデコードデータを演算対象として、中間値への遷移を抑止するという作用をもたらす。
【００１８】
また、この第２の側面において、上記４つのデコーダは、共通の制御信号に同期して上記固定値の出力を行うようにしてもよい。これにより、８ビットの入力データの各ビットの遷移にばらつきがある場合であっても一斉に演算を駆動するという作用をもたらす。
【００１９】
また、この第２の側面において、上記制御信号は、上記入力データが上記デコーダに入力されるタイミングを示すものであってもよい。これにより、デコーダに入力されるタイミングに合わせて一斉に演算を駆動するという作用をもたらす。
【００２０】
また、この第２の側面において、上記演算部は、上記４つのデコーダの全てが上記固定値を出力している間は４組の上記固定値からなる１６ビット幅のデータを出力するようにしてもよい。これにより、演算結果の遷移する期間を制限するという作用をもたらす。
【発明の効果】
【００２１】
本発明によれば、ダイナミックハザードに起因する消費電力の増加を一様に抑えて、ＤＰＡ攻撃を困難にすることができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００２２】
【図１】本発明において想定する暗号化および復号化の処理手順例を示す図である。
【図２】本発明において想定する暗号化および復号化の共通化した処理手順例を示す図である。
【図３】本発明において想定するＳｕｂＢｙｔｅｓ／Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９３１）の処理内容を示す図である。
【図４】既約多項式を用いた逆元演算回路の基本原理を示す図である。
【図５】本発明の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の構成例を示す図である。
【図６】本発明の実施の形態におけるデコーダ１１１乃至１１４およびエンコーダ１３１乃至１３４の構成例を示す図である。
【図７】本発明の実施の形態におけるデコーダ１１１乃至１１４の各々の動作の真理値表を示す図である。
【図８】本発明の実施の形態におけるエンコーダ１３１乃至１３４の各々の動作の真理値表を示す図である。
【図９】本発明の実施の形態におけるｘ2・λ演算回路１２１の構成例を示す図である。
【図１０】本発明の実施の形態におけるｘ2・λ演算回路１２１の動作の真理値表である。
【図１１】本発明の実施の形態における排他的論理和演算回路１２２および１２４の半分の構成例を示す図である。
【図１２】本発明の実施の形態における排他的論理和演算回路１２２および１２４の半分の構成例による動作の真理値表である。
【図１３】本発明の第１の実施の形態における排他的論理和演算回路１２２および１２４の動作タイミング例を示す図である。
【図１４】本発明の実施の形態におけるＧＦ（（２2）2）逆元演算回路１２５の構成例を示す図である。
【図１５】本発明の実施の形態におけるＧＦ（（２2）2）逆元演算回路１２５の構成例による動作の真理値表である。
【図１６】本発明の実施の形態における乗算回路１２３、１２６および１２７の構成例を示す図である。
【図１７】本発明の実施の形態におけるインバータ２３６の構成例を示す図である。
【図１８】本発明の実施の形態における否定排他的論理和演算回路２３１および２３２の構成例を示す図である。
【図１９】本発明の実施の形態における乗算回路２３３の構成例を示す図である。
【図２０】本発明の実施の形態における乗算回路２３３の構成例による動作の真理値表である。
【図２１】本発明の実施の形態における乗算φ演算回路２３４の構成例を示す図である。
【図２２】本発明の実施の形態における乗算φ演算回路２３４の構成例による動作の真理値表である。
【図２３】本発明の実施の形態における負論理乗算回路２３５の構成例を示す図である。
【図２４】本発明の実施の形態における負論理乗算回路２３５の構成例による動作の真理値表である。
【図２５】本発明の実施の形態における負論理入力排他的論理和演算回路２３７の構成例を示す図である。
【図２６】本発明の実施の形態における乗算回路１２３、１２６および１２７の動作タイミング例を示す図である。
【図２７】本発明の実施の形態によるＧＦ（（（２2）2）2）逆元演算回路１００の構成例における遅延量を示す図である。
【図２８】本発明の第１の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の動作タイミング例を示す図である。
【図２９】本発明の第２の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の動作タイミング例を示す図である。
【発明を実施するための形態】
【００２３】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（１ラウンドの処理を２相に分けて実行する例）
２．第２の実施の形態（１ラウンドの処理を１クロックサイクルで実行する例）
３．変形例
【００２４】
＜１．第１の実施の形態＞
［暗号化装置または復号化装置の構成］
図１は、本発明において想定する暗号化および復号化の処理手順例を示す図である。図１（ａ）は、メッセージを暗号化するための処理手順であり、ＳｕｂＢｙｔｅｓ（９１１）、ＳｈｉｆｔＲｏｗｓ（９１２）、ＭｉｘＣｏｌｕｍｎｓ（９１５）、ＡｄｄＲｏｕｎｄＫｅｙ（９１６）の各手順を含む。ＡＥＳ暗号の入力データは１２８ビットであるが、８ビットを単位とした４×４のマトリクスとして定義され、演算処理は８ビット単位で行われる。この１２８ビットの入力データは、ラウンド演算の開始前（Ｒｄ０）に入力され、ＡｄｄＲｏｕｎｄＫｅｙ（９１６）を経てレジスタ９１０に保持される。
【００２５】
ＳｕｂＢｙｔｅｓ（９１１）は、８ビットデータに対して逆元を計算し、アフィン変換を行うものである。ＳｈｉｆｔＲｏｗｓ（９１２）は、４×４のマトリクスの横方向（各行）に対して回転処理を行うものである。ＭｉｘＣｏｌｕｍｎｓ（９１５）は、４×４のマトリクスの縦方向（各列）に対して演算処理を行うものである。ＡｄｄＲｏｕｎｄＫｅｙ（９１６）は、ラウンド鍵（９１９）との排他的論理和（ＸＯＲ）演算を行うものである。レジスタ９１０には、各手順を１ラウンド行う度に（Ｒｄ１乃至１０）中間値が更新される。
【００２６】
この暗号化処理では、各手順を１０ラウンド繰り返した後にレジスタ９１０に保持された値が暗号として出力される。なお、最終ラウンド（Ｒｄ１０）では、ＭｉｘＣｏｌｕｍｎｓ（９１５）の処理は行われない。
【００２７】
図１（ｂ）は、暗号化されたメッセージを復号化するための処理手順であり、Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９２１）、Ｉｎｖ＿ＳｈｉｆｔＲｏｗｓ（９２２）、ＡｄｄＲｏｕｎｄＫｅｙ（９２３）、Ｉｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９２５）の各手順を含む。暗号化されたメッセージは、ラウンド演算の開始前（Ｒｄ１０）に入力され、ＡｄｄＲｏｕｎｄＫｅｙ（９２３）を経てレジスタ９２０に保持される。
【００２８】
Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９２１）は、ＳｕｂＢｙｔｅｓ（９１１）の逆の処理を行うものである。Ｉｎｖ＿ＳｈｉｆｔＲｏｗｓ（９２２）は、ＳｈｉｆｔＲｏｗｓ（９１２）の逆の処理を行うものである。ＡｄｄＲｏｕｎｄＫｅｙ（９２３）は、ラウンド鍵（９２８）との排他的論理和演算を行うものである。Ｉｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９２５）は、ＭｉｘＣｏｌｕｍｎｓ（９１５）の逆の処理を行うものである。レジスタ９２０には、各手順を１ラウンド行う度に（Ｒｄ９乃至０）中間値が更新される。
【００２９】
この復号化処理では、各手順を１０ラウンド繰り返した後にレジスタ９２０に保持された値が復号化されたメッセージとして出力される。なお、最終ラウンド（Ｒｄ０）では、Ｉｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９２５）の処理は行われない。
【００３０】
ここで、ＳｕｂＢｙｔｅｓ（９１１）およびＳｈｉｆｔＲｏｗｓ（９１２）とＩｎｖ＿ＳｕｂＢｙｔｅｓ（９２１）およびＩｎｖ＿ＳｈｉｆｔＲｏｗｓ（９２２）とは対になる処理であるため、暗号化処理と復号化処理との間で共通化することができる。ＭｉｘＣｏｌｕｍｎｓ（９１５）とＩｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９２５）との間も同様である。そこで、次のように両者を共通化した処理手順として実現した場合のイメージを示す。
【００３１】
図２は、本発明において想定する暗号化および復号化の共通化した処理手順例を示す図である。ＳｕｂＢｙｔｅｓ／Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９３１）は、ＳｕｂＢｙｔｅｓ（９１１）とＩｎｖ＿ＳｕｂＢｙｔｅｓ（９２１）とを共通化したものである。ＳｈｉｆｔＲｏｗｓ／Ｉｎｖ＿ＳｈｉｆｔＲｏｗｓ（９３２）は、ＳｈｉｆｔＲｏｗｓ（９１２）とＩｎｖ＿ＳｈｉｆｔＲｏｗｓ（９２２）とを共通化したものである。ＡｄｄＲｏｕｎｄＫｅｙ（９３３）は、ＡｄｄＲｏｕｎｄＫｅｙ（９２３）と同様に、ラウンド鍵（９２８）との排他的論理和演算を行うものである。選択手順９３４は、暗号化時にＡｄｄＲｏｕｎｄＫｅｙ（９３３）を経ない値を選択し、復号化時にＡｄｄＲｏｕｎｄＫｅｙ（９３３）の出力を選択するものである。ＭｉｘＣｏｌｕｍｎｓ／Ｉｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９３５）は、ＭｉｘＣｏｌｕｍｎｓ（９１５）とＩｎｖ＿ＭｉｘＣｏｌｕｍｎｓ（９２５）とを共通化したものである。ＡｄｄＲｏｕｎｄＫｅｙ（９３６）は、ＡｄｄＲｏｕｎｄＫｅｙ（９１６）と同様に、ラウンド鍵（９１９）との排他的論理和演算を行うものである。選択手順９３７は、暗号化時にＡｄｄＲｏｕｎｄＫｅｙ（９３６）の出力を選択し、復号化時にＡｄｄＲｏｕｎｄＫｅｙ（９３６）を経ない値を選択するものである。レジスタ９３０は、レジスタ９１０とレジスタ９２０とを共通化したものであり、暗号化または復号化の中間値を保持するものである。
【００３２】
図３は、本発明において想定するＳｕｂＢｙｔｅｓ／Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９３１）の処理内容を示す図である。このＳｕｂＢｙｔｅｓ／Ｉｎｖ＿ＳｕｂＢｙｔｅｓ（９３１）を、以下ではＳｂｏｘと呼称する。上述のレジスタ９３０の出力は、別の演算回路に入力されることなく、このＳｂｏｘに入力される。このＳｂｏｘは、暗号化時と復号化時とで共通化されているため、両者を切り換えるスイッチ３４および３８を備えている。
【００３３】
Ｓｂｏｘにおいて、暗号化時には、同形写像変換回路１２において写像変換δを行い、逆元演算回路１００においてＧＦ（（（２2）2）2）上の逆元演算を行う。そして、逆同形写像変換・アフィン変換回路１６において逆写像変換δ-1とアフィン変換を行った後に排他的論理和（ＸＯＲ）演算回路１７により排他的論理和演算を行う。
【００３４】
一方、復号化時には、排他的論理和演算回路２１により排他的論理和演算を行った後に逆アフィン変換・同形写像回路２２において逆アフィン変換と写像変換δを行う。そして、逆元演算回路１００においてＧＦ（（（２2）2）2）上の逆元演算を行う。その後、逆同形写像回路２６において逆写像変換δ-1を行う。
【００３５】
［逆元演算回路の構成］
図４は、既約多項式を用いた逆元演算回路の基本原理を示す図である。図４（ａ）は、８ビットのＧＦ（（（２2）2）2）逆元演算回路である。ここでは、入力データの上位４ビットをＰH、下位４ビットをＰLにより表し、出力データの上位４ビットをＰH-1、下位４ビットをＰL-1により表している。逆元演算回路は階層的な構造を有し、合成体ＧＦ（（（２2）2）2）上の逆元演算は、以下の部分体ＧＦ（（２2）2）の演算回路を組み合わせることにより実現される。すなわち、このＧＦ（（（２2）2）2）逆元演算回路は、ｘ2・λ演算回路８１１と、排他的論理和演算回路８１２および８１４と、乗算回路８１３、８１６および８１７と、逆元演算回路８２０とを備える。
【００３６】
図４（ｂ）は、４ビットのＧＦ（（２2）2）逆元演算回路８２０である。合成体ＧＦ（（２2）2）上の逆元演算は、以下の部分体ＧＦ（２2）の演算を組み合わせることにより実現される。すなわち、このＧＦ（（２2）2）逆元演算回路８２０は、ｘ2・φ演算回路８２１と、排他的論理和演算回路８２２および８２４と、乗算回路８２３、８２６および８２７と、逆元演算回路８３０とを備える。
【００３７】
上述のとおり、この逆元演算回路の基本原理をそのまま利用した場合、ダイナミックハザードによる中間値への遷移のため、ＤＰＡ攻撃の対象とされるおそれが生じる。そこで、本発明の実施の形態では、逆元演算回路の前段にデコーダを配置して、逆元演算回路をデコードデータによるテーブル回路で構成することにより、演算によるゲート遅延を削減する。そして、それとともに、演算回路の入力が全て確定するまで固定値を出力する構成を採ることにより、中間値への遷移を抑止するように制御を行う。
【００３８】
図５は、本発明の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の構成例を示す図である。このＧＦ（（（２2）2）2）逆元演算回路１００は、４つのデコーダ１１１乃至１１４と、演算部１２０と、４つのエンコーダ１３１乃至１３４とを備えている。
【００３９】
デコーダ１１１乃至１１４は、８ビットの入力データのうちそれぞれ２ビットずつをデコードして、それぞれ４ビットのデコードデータを出力するものである。デコーダ１１１乃至１１４は、共通する制御信号ＰＣｄｌｙ（Phase Control delay）によって動作タイミングを制御される。なお、ここでは４つのデコーダ１１１乃至１１４を用いた例について説明するが、これらは一体化したものでもよく、また、任意の数に分割したものでもよい。
【００４０】
演算部１２０は、デコーダ１１１乃至１１４から出力された１６ビットのデコードデータに対してＧＦ（（（２2）2）2）逆元演算を行うものである。部分体で使用する規約多項式が決まっている場合、合成体上での演算で、１つまたは２つの４ビット入力が決まれば、出力の４ビットは自動的に決まる。そして、ここでは、２ビット単位でデコードしたデータで演算がなされるものとしている。この演算部１２０は、図４（ａ）の基本原理に準じた構成を備えており、ｘ2・λ演算回路１２１と、排他的論理和演算回路１２２および１２４と、乗算回路１２３、１２６および１２７と、ＧＦ（（２2）2）逆元演算回路１２５とを備える。各回路の構成についてはさらに後述する。
【００４１】
エンコーダ１３１乃至１３４は、演算部１２０から出力された１６ビットのデコードデータのうちそれぞれ４ビットずつをエンコードして、それぞれ２ビットのバイナリデータを出力するものである。なお、ここでは４つのエンコーダ１３１乃至１３４を用いた例について説明するが、これらは一体化したものでもよく、また、任意の数に分割したものでもよい。
【００４２】
図６は、本発明の実施の形態におけるデコーダ１１１乃至１１４およびエンコーダ１３１乃至１３４の構成例を示す図である。
【００４３】
図６（ａ）は、デコーダ１１１乃至１１４の構成例である。ここでは、デコーダ１１１の内部を代表として示しているが、デコーダ１１２乃至１１４についても同様の構成を備える。デコーダ１１１は、８ビットの入力データのうち上位の２ビットｂ６およびｂ７を入力として、ｂ６およびｂ７ならびにこれらの反転信号を組み合わせて４ビットのデコードデータを生成する。このデコーダ１１１は、インバータと否定論理和（ＮＯＲ）演算回路の２ゲート遅延を有する。また、否定論理和演算回路には制御信号ＰＣｄｌｙが入力され、この制御信号ＰＣｄｌｙが「１」を示す間は、デコードデータは所定の固定値になる。本発明の実施の形態では、所定の固定値としてデコードデータを全ビット「０」にすることを想定している。
【００４４】
図６（ｂ）は、エンコーダ１３１乃至１３４の構成例である。ここでは、エンコーダ１３１の内部を代表として示しているが、エンコーダ１３２乃至１３４についても同様の構成を備える。エンコーダ１３１は、１６ビットのデコードデータのうち上位の４ビットを入力として、ｄ０乃至ｄ３を組み合わせて２ビットのエンコードデータを生成する。このエンコーダ１３１は、否定論理和演算回路とインバータの２ゲート遅延を有する。
【００４５】
図７は、本発明の実施の形態におけるデコーダ１１１乃至１１４の各々の動作の真理値表を示す図である。上述のようにデコーダ１１１乃至１１４の各々には２ビットの入力データと制御信号ＰＣｄｌｙが入力される。制御信号ＰＣｄｌｙが「１」の場合、入力データにかかわらず、デコードデータは「００００」になる。制御信号ＰＣｄｌｙが「０」の場合、入力データに応じて、４ビットのデコードデータのうち１ビットだけが「１」となり、他のビットは「０」になる。
【００４６】
これにより、制御信号ＰＣｄｌｙのタイミングに合わせてデコードデータを「００００」にリセットして、その後、入力データに応じてデコードデータの４ビットのうち１ビットだけを「１」にするという遷移を実現することができる。
【００４７】
図８は、本発明の実施の形態におけるエンコーダ１３１乃至１３４の各々の動作の真理値表を示す図である。デコードデータが「１」を示すビット位置に応じて、出力データが決定される。ここで、出力データが定義されるのは、４ビットのデコードデータのうち１ビットだけが「１」となり、他のビットが「０」となっている場合、および、４ビットのデコードデータが全て「０」となっている場合である。これ以外の場合は未定義である。図６（ｂ）の構成例では、この性質を利用して、４ビットのうち下位１ビットを参照することなくバイナリデータを生成している。
【００４８】
図９は、本発明の実施の形態におけるｘ2・λ演算回路１２１の構成例を示す図である。また、図１０は、本発明の実施の形態におけるｘ2・λ演算回路１２１の動作の真理値表である。デコード前の２進数データによりｘ2・λ演算の真理値表を作成すると、図１０（ａ）に示すようになる。図７の関係を利用してデコードデータによるｘ2・λ演算の真理値表を作成すると、図１０（ｂ）に示すようになる。図９は図１０（ｂ）の関係を組合せ回路により実現したものである。
【００４９】
このｘ2・λ演算回路１２１では、下位４ビットの出力については、インバータ２１１または否定論理和演算回路２１２と否定論理和演算回路２１３との２ゲート遅延により演算が行われる。また、上位４ビットの出力については、論理積−否定論理和演算回路２１４とインバータ２１５との２ゲート遅延により演算が行われる。したがって、上位および下位の演算結果は、データにかかわらず等しく２ゲート遅延により出力される。また、このｘ2・λ演算回路１２１に、２進数データでは定義されないデコードデータとして「００００＿００００」が入力された場合、「００００＿００００」を出力する。
【００５０】
図１１は、本発明の実施の形態における排他的論理和演算回路１２２および１２４の半分の構成例を示す図である。また、図１２は、本発明の実施の形態における排他的論理和演算回路１２２および１２４の半分の構成例による動作の真理値表である。排他的論理和演算回路では、各ビットは独立して動作するため、半分の規模の排他的論理和演算回路を並列配置することにより回路を構成することができる。したがって、ここでは、デコード後の８ビット幅の排他的論理和演算回路１２２および１２４を、４ビット幅の排他的論理和演算回路の並列配置により実現する構成例について説明する。
【００５１】
デコード前の２進数データにより排他的論理和演算の真理値表を作成すると、図１２（ａ）に示すようになる。図７の関係を利用してデコードデータによる排他的論理和演算の真理値表を作成すると、図１２（ｂ）に示すようになる。図１１は図１２（ｂ）の関係を組合せ回路により実現したものである。この排他的論理和演算回路では、論理積−否定論理和演算回路２２１とインバータ２２２との２ゲート遅延により演算が行われる。また、この排他的論理和演算回路の２つのデコード入力のうち、少なくとも一方のデコード入力に「００００」が入力された場合、入力信号は論理積−否定論理和演算回路２２１により受けているため、排他的論理和演算回路１２２または１２４は「００００」を出力する。
【００５２】
図１３は、本発明の第１の実施の形態における排他的論理和演算回路１２２および１２４の動作タイミング例を示す図である。本発明の第１の実施の形態では、１ラウンドの動作をプリチャージ相とエバリュエーション相の２相に分けて交互に行うようにフェーズ制御（ＰＣ：Phase Control）を行う。プリチャージ相では、出力は一旦「００００」にリセットされる。そして、エバリュエーション相では２つの入力が何れも「００００」以外になった後、さらに演算遅延が経過した後に排他的論理和演算結果が出力される。この排他的論理和演算結果は、デコードデータであるため、１ビットだけが「１」であり、それ以外のビットは「０」を示す。したがって、プリチャージ相でリセットされた「００００」から１ビットだけが、エバリュエーション相において「１」に遷移する。また、２つの入力の変化タイミングに遅延差がある場合、両方のデータが確定するまで「００００」が出力される。そして、両方のデータが確定した後に排他的論理和演算を実行して、演算結果に遷移する。このとき、中間値への遷移は起こらない。
【００５３】
図１４は、本発明の実施の形態におけるＧＦ（（２2）2）逆元演算回路１２５の構成例を示す図である。また、図１５は、本発明の実施の形態におけるＧＦ（（２2）2）逆元演算回路１２５の構成例による動作の真理値表である。デコード前の２進数データによりＧＦ（（２2）2）逆元演算の真理値表を作成すると、図１５（ａ）に示すようになる。図７の関係を利用してデコードデータによるＧＦ（（２2）2）逆元演算の真理値表を作成すると、図１５（ｂ）に示すようになる。図１４は図１５（ｂ）の関係を組合せ回路により実現したものである。
【００５４】
このＧＦ（（２2）2）逆元演算回路１２５では、論理積−否定論理和演算回路２５１とインバータ２５２との２ゲート遅延により演算が行われる。したがって、このＧＦ（（２2）2）逆元演算回路１２５における演算結果は、データにかかわらず等しく２ゲート遅延により出力される。また、このＧＦ（（２2）2）逆元演算回路１２５に、２進数データでは定義されないデコードデータとして「００００＿００００」が入力された場合、「００００＿００００」を出力する。
【００５５】
図１６は、本発明の実施の形態における乗算回路１２３、１２６および１２７の構成例を示す図である。４ビットの２進数データ（デコードデータでは８ビット）を入力とする乗算回路では、入力の組み合わせは２4×２4＝２５６通りになる。これをテーブルで構成すると、回路規模は他のテーブルを用いた４ビット演算回路（例えば逆元演算回路）の１６倍となり、回路規模が各段に大きくなる。ここでは、回路規模を削減するため、部分体ＧＦ（（２2）2）での乗算器を用いて構成する例を示す。
【００５６】
部分体ＧＦ（（２2）2）での乗算器は、図１６に示すように４ビットのデコードデータの排他的論理和演算回路および４ビットのデコードデータの乗算回路により構成される。また、遅延時間を考慮して一部の回路の入力または出力は負論理になっている。すなわち、この回路は、否定排他的論理和（ＸＮＯＲ）演算回路２３１および２３２と、乗算回路２３３と、乗算φ演算回路２３４と、負論理乗算回路２３５と、インバータ２３６と、負論理入力排他的論理和演算回路２３７と、排他的論理和演算回路２３８とを備える。そして、演算器２３１乃至２３８は、デコードデータの演算をする演算器である。なお、排他的論理和演算回路２３８は図１１に示した回路をそのまま利用することができる。また、インバータ２３６は、入力がデコードデータの場合、図１７に示すように、配線のみで実現でき、乗算器の演算遅延に影響を与えない。
【００５７】
図１８は、本発明の実施の形態における否定排他的論理和演算回路２３１および２３２の構成例を示す図である。この回路は、図１１の排他的論理和演算回路において最終段のインバータを取り除いたものになっている。したがって、この否定排他的論理和演算回路２３１および２３２では、論理積−否定論理和演算回路３１１による１ゲート遅延により演算が行われる。
【００５８】
図１９は、本発明の実施の形態における乗算回路２３３の構成例を示す図である。また、図２０は、本発明の実施の形態における乗算回路２３３の構成例による動作の真理値表である。デコード前の２進数データにより乗算の真理値表を作成すると、図２０（ａ）に示すようになる。図７の関係を利用してデコードデータによる乗算の真理値表を作成すると、図２０（ｂ）に示すようになる。図１９は図２０（ｂ）の関係を組合せ回路により実現したものである。
【００５９】
この乗算回路２３３では、最下位ビットｄ０を出力するために、否定論理和（ＮＯＲ）演算回路３３１と否定論理和演算回路３３２との２ゲート遅延により演算が行われる。上位３ビットを出力するために、論理積−否定論理和演算回路３３３と、インバータ３３４との２ゲート遅延により演算が行われる。したがって、この乗算回路２３３における演算結果は、データにかかわらず等しく２ゲート遅延により出力される。また、この乗算回路２３３の２つの入力のうちの少なくとも一方の入力に、２進数データでは定義されないデコードデータとして「００００」が入力された場合、「００００」を出力する。
【００６０】
図２１は、本発明の実施の形態における乗算φ演算回路２３４の構成例を示す図である。また、図２２は、本発明の実施の形態における乗算φ演算回路２３４の構成例による動作の真理値表である。デコード前の２進数データにより乗算φ演算の真理値表を作成すると、図２２（ａ）に示すようになる。図７の関係を利用してデコードデータによる乗算の真理値表を作成すると、図２２（ｂ）に示すようになる。図２１は図２２（ｂ）の関係を組合せ回路により実現したものである。
【００６１】
この乗算φ演算回路２３４は、乗算結果にφ（＝１０）を乗じた値を出力するものであるが、φが固定値であるため、図１９の乗算回路２３３の出力のビット順序を変更することにより実現可能である。したがって、この乗算φ演算回路２３４における演算結果は、乗算回路２３３と同様に、データにかかわらず等しく２ゲート遅延により出力される。また、この乗算φ演算回路２３４の２つの入力のうちの少なくとも一方の入力に、２進数データでは定義されないデコードデータとして「００００」が入力された場合、「００００」を出力する。
【００６２】
図２３は、本発明の実施の形態における負論理乗算回路２３５の構成例を示す図である。また、図２４は、本発明の実施の形態における負論理乗算回路２３５の構成例による動作の真理値表である。この負論理乗算回路２３５は、入力および出力ともに負論理となっている。
【００６３】
この負論理乗算回路２３５では、最下位ビット／ｄ０を出力するために、否定論理積（ＮＡＮＤ）演算回路３５１と否定論理積演算回路３５２との２ゲート遅延により演算が行われる。上位３ビットを出力するために、論理和−否定論理積演算回路３５３と、インバータ３５４との２ゲート遅延により演算が行われる。したがって、この負論理乗算回路２３５における演算結果は、データにかかわらず等しく２ゲート遅延により出力される。また、この負論理乗算回路２３５の少なくとも何れか一方の入力に、２進数データでは定義されないデコードデータ「００００」の負論理の値「１１１１」が入力された場合、負論理の値「１１１１」を出力する。
【００６４】
図２５は、本発明の実施の形態における負論理入力排他的論理和演算回路２３７の構成例を示す図である。この負論理入力排他的論理和演算回路２３７は、入力のみが負論理となっている。
【００６５】
この負論理入力排他的論理和演算回路２３７では、各ビットを出力するために、論理和−否定論理積演算回路３７１の１ゲート遅延により演算が行われる。したがって、この負論理入力排他的論理和演算回路２３７における演算結果は、データにかかわらず等しく１ゲート遅延により出力される。また、この負論理入力排他的論理和演算回路２３７の何れか一方の入力に、２進数データでは定義されないデコードデータ「００００」の負論理の値「１１１１」が入力された場合、「００００」を出力する。
【００６６】
これらの回路構成により、４ビット乗算回路１２３、１２６および１２７は、上位２ビットおよび下位２ビットともに、遅延時間は４ゲート遅延となる。また、４ビット乗算回路としてみた場合、入力も出力も正論理の動作となる。
【００６７】
図２６は、本発明の実施の形態における乗算回路１２３、１２６および１２７の動作タイミング例を示す図である。本発明の第１の実施の形態では、上述のように、１ラウンドの動作をプリチャージ相とエバリュエーション相の２相に分けて交互に行うようにフェーズ制御を行う。プリチャージ相では、出力は一旦「００００」にリセットされる。そして、エバリュエーション相では２つの入力が何れも「００００」以外になった後、さらに演算遅延が経過した後に乗算演算結果が出力される。この乗算演算結果は、デコードデータであるため、１ビットだけが「１」であり、それ以外のビットは「０」を示す。したがって、プリチャージ相でリセットされた「００００」から１ビットだけが、エバリュエーション相において「１」に遷移する。また、２つの入力の変化タイミングに遅延差がある場合、両方のデータが確定するまで「００００」が出力される。そして、両方のデータが確定した後に乗算動作を実行して、実行結果に遷移する。このとき、中間値への遷移は起こらず、したがって、中間値遷移による電流も発生しない。
【００６８】
［逆元演算回路の遅延量］
図２７は、本発明の実施の形態によるＧＦ（（（２2）2）2）逆元演算回路１００の構成例における演算データの信号経路を示す図である。
【００６９】
上述のように、ｘ2・λ演算回路１２１では２ゲート遅延を要し、排他的論理和演算回路１２２または１２４では２ゲート遅延を要し、乗算回路１２３、１２６または１２７では４ゲート遅延を要し、ＧＦ（（２2）2）逆元演算回路１２５では２ゲート遅延を要する。そして、これらの演算回路を通る演算データの信号経路は、経路Ａ乃至Ｅの５つの信号経路が存在する。この中で、最も回路動作による遅延が大きいのは経路Ｂで、その遅延は１４ゲート遅延ある。他の経路での、通過する演算回路による遅延の積算は、経路Ａで１０ゲート遅延、経路Ｃで１２ゲート遅延、経路Ｄで４ゲート遅延、そして、経路Ｅで６ゲート遅延である。しかし、２つの入力データから演算結果を生成する「排他的論理和演算回路」および「乗算回路」は、２つの入力のうち少なくとも一方が固定値の場合は固定値を出力し、２つの入力が共にデコード値になってから演算動作を開始する。そして、その出力は、排他的論理和演算回路では２ゲート遅延後、乗算回路では４ゲート遅延後、固定値から演算結果に遷移する。５つの演算経路には、「排他的論理和演算回路」および「乗算回路」の２入力演算器の少なくとも１つが配置されている。そして、２入力演算器の２つの入力が有効値になるタイミングは異なる場合が多いが、２入力演算器は２つの入力の少なくとも一方が固定値の場合は固定値を出力し、両方の入力が有効値になってから所定時間経過後に出力は固定値から演算結果に遷移する。したがって、異なる遅延で入力された２つの経路の信号は、２入力演算器を通過した後は遅い方の経路の遅延タイミングに一致して以降の回路に入力される。例えば、ＧＦ（（２2）2）逆元演算回路１２５の出力となる経路Ａ乃至Ｃは、全て最も回路遅延の積算の大きい経路Ｂの遅延と一致して乗算器１２６および１２７に入力される。経路Ｄのデータは、遅延なく乗算器１２６に入力されるが、他方の入力遅延が経路Ｂのタイミングとなるため、乗算器１２６を経た経路Ｄのタイミングも経路Ｂのタイミングと一致する。同様に、乗算器１２７を経た経路Ｅのタイミングも経路Ｂのタイミングと一致する。これらより、全ての演算経路においてデータが確定するのは、経路Ｂの遅延である１４ゲート遅延後となる。
【００７０】
このデコードデータによる逆元演算回路では、入力部にはデコーダ１１１乃至１１４のデコード回路が、出力部にはエンコーダ１３１乃至１３４がそれぞれ配置され、各々２ゲート遅延を要する。これは全ての信号パスに共通に付加される遅延時間で、結局、ＧＦ（（（２2）2）2）逆元演算回路１００の演算遅延時間は、演算パスに関わらず１８ゲート遅延となる。また、この演算回路では、２入力の演算回路の場合、両方の入力が確定してから演算が開始され、その演算器の演算遅延後に出力が固定値から演算結果に遷移する構成となっているため、各演算経路で中間値への遷移は起こらない。そして、各演算器の出力が固定値からデコード値に変化した時、変化する信号線は出力値にかかわらずデコード単位で１本であるため、ＤＰＡ攻撃で鍵が取り出される可能性は低くなる。また、遅延時間が短縮されたことにより、動作周波数を高く設定することができる。
【００７１】
［逆元演算回路の動作］
図２８は、本発明の第１の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の動作タイミング例を示す図である。この第１の実施の形態では、１ラウンドの動作をプリチャージ相とエバリュエーション相の２相に分けて交互に行うようにフェーズ制御の制御信号ＰＣが変化する。プリチャージ相ではレジスタ９３０の出力が一旦「００００」にリセットされ、エバリュエーション相ではレジスタ９３０に保持された値が出力される。
【００７２】
図２および図３により説明したように、レジスタ９３０からＧＦ（（（２2）2）2）逆元演算回路１００への入力はある程度の遅延を伴う。そこで、この遅延タイミングにあわせた制御信号ＰＣｄｌｙ（Phase Control delay）が利用される。この制御信号ＰＣｄｌｙは、制御信号ＰＣと同じタイミングで立ち上がり、制御信号ＰＣの立下り後、レジスタ９３０からＧＦ（（（２2）2）2）逆元演算回路１００までの回路動作による遅延時間に若干のマージンを見込んだ時間経過後に立ち下がる。すなわち、図６により説明したように、この制御信号ＰＣｄｌｙは、デコーダ１１１乃至１１４からデコードデータが演算部１２０へ出力されるタイミングを示す。この制御信号ＰＣｄｌｙはデコーダ１１１乃至１１４に入力され、制御信号ＰＣｄｌｙが「１」を示している間、デコードデータは入力データにかかわらず「００００」になる。一方、制御信号ＰＣｄｌｙが「０」を示している間、デコーダ１１１乃至１１４から入力データに応じたデコードデータが出力される。
【００７３】
プリチャージ相では、クロックの立上りに同期して制御信号ＰＣが「１」になり、レジスタからの信号は全て「０」に制御される。これが伝播して、各回路ブロックのノードは順次プリチャージレベルに遷移していく。そして、制御信号ＰＣの立上りに同期して制御信号ＰＣｄｌｙも「１」に遷移し、デコード回路１１１乃至１１４からのデコード出力は全て「００００」に制御されて、ＧＦ（（（２2）2）2）のデコードデータによる逆元演算回路１２０へ入力される。これにより、４ゲート遅延後に乗算回路１２６のデコード出力が、６ゲート遅延後に乗算回路１２７のデコード出力がそれぞれ「００００＿００００」となる。
【００７４】
エバリュエーション相では、制御信号ＰＣが「０」になり、レジスタ９３０に保持された値が出力されるようになる。これにより、各回路ブロックで演算が開始され、演算結果が次の回路に供給されていく。そして、所定時間経過後、ＧＦ（（（２2）2）2）逆元演算回路１００に演算結果が供給される。制御信号ＰＣｄｌｙは、レジスタ９３０の出力からＧＦ（（（２2）2）2）逆元演算回路１００の入力までの演算時間に若干のマージンを見込んだ時間を発生させる遅延回路によって発生されるタイミングで「０」に遷移する。これにより、制御信号ＰＣｄｌｙが「０」になった時点で、ＧＦ（（（２2）2）2）逆元演算回路１００の入力信号のデコードデータがＧＦ（（（２2）2）2）逆元演算回路１００に入力されて演算が実行される。そして、１４ゲート遅延経過後、乗算器１２６および１２７の出力は各々ほぼ同時に「００００＿００００」から演算結果に遷移する。
【００７５】
このとき、演算結果の出力端に、ＤＰＡ攻撃の対象となる演算の中間値が現れることはない。そして、エバリュエーション相で、ＧＦ（（（２2）2）2）逆元演算回路１００の入力ＰHおよびＰLならびに出力ＰH-1およびＰL-1は、「００００＿００００」からデコードデータに変化するだけである。すなわち、デコードデータは４本の信号線毎に１本だけ「１」に変化するだけであるため、配線容量に差異がないと仮定した場合、入力値および出力値に関係なく信号変化に伴う配線の充放電電流は一定である。そのため、ＧＦ（（（２2）2）2）逆元演算回路１００に対するＤＰＡ攻撃は困難となる。また、ＧＦ（（（２2）2）2）逆元演算回路１００の内部動作においても、各演算ブロックの出力信号は、プリチャージ相で設定された固定値「００００」からデコードデータに変化するだけで、変化は４本の信号線で１本だけとなる。したがって、ＧＦ（（（２2）2）2）逆元演算回路１００の内部動作電流に対するＤＰＡ攻撃も困難となる。
【００７６】
このように、本発明の第１の実施の形態では、デコードデータで動作する演算回路を用いて、プリチャージ相において各演算回路出力のデコードデータを「００００」にリセットし、エバリュエーション相で１ビットだけ「１」に変化させる。これにより、逆元演算時の中間値への遷移を抑止することができる。
【００７７】
＜２．第２の実施の形態＞
上述の第１の実施の形態では１ラウンドの処理をプリチャージ相およびエバリュエーション相の２相に分けて実行したが、この第２の実施の形態では１ラウンドの処理を１クロックサイクルで実行することを想定する。
【００７８】
本発明の第２の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路の回路構成は、上述の第１の実施の形態において説明したものと同様である。したがって、ゲート遅延も第１の実施の形態の場合と同様であり、少ないゲート遅延による逆元演算が可能となる。ただし、制御信号ＰＣｄｌｙのタイミングが第１の実施の形態の場合とは異なる。
【００７９】
［逆元演算回路の動作］
図２９は、本発明の第２の実施の形態におけるＧＦ（（（２2）2）2）逆元演算回路１００の動作タイミング例を示す図である。この第２の実施の形態では、レジスタ９３０の出力からＧＦ（（（２2）2）2）逆元演算回路１００までの演算パスの遅延時間にマージンを加えた時間が経過した後に、制御信号ＰＣｄｌｙが「１」から「０」に変化するように制御される。すなわち、この制御信号ＰＣｄｌｙは、演算部１２０への入力データがデコーダ１１１乃至１１４から出力されるタイミングを示すことになる。
【００８０】
クロックの立上りで、レジスタ９３０の出力は更新され、更新データによるラウンド演算が開始される。これと同時に制御信号ＰＣｄｌｙも「１」になり、ＧＦ（（（２2）2）2）逆元演算回路１００の入力信号はデコーダ１１１乃至１１４によって「００００＿００００」に制御され、この入力を受けてＧＦ（（（２2）2）2）逆元演算回路１００が動作する。そして、エンコーダ１３１乃至１３４の入力も「００００＿００００」になる。このときの出力変化は、直前のデコードデータに関わらず、４本の信号線で１本だけ「０」に変化する。
【００８１】
レジスタ９３０の出力からＧＦ（（（２2）2）2）逆元演算回路１００までの演算パスの遅延時間にマージンを加えた時間が経過した後、制御信号ＰＣｄｌｙは「０」となり、ＧＦ（（（２2）2）2）逆元演算回路１００に到達している演算データがデコードされる。これにより、ＧＦ（（（２2）2）2）逆元演算回路１００が動作を開始する。
【００８２】
そして、１４ゲート遅延後に乗算回路１２６および１２７の出力も「００００＿００００」から演算結果に遷移する。このときの出力変化も、４本の信号線で１本だけ「１」に変化する。
【００８３】
このように、本発明の第２の実施の形態によれば、レジスタ９３０の出力からの遅延時間にマージンを加えたタイミングで制御信号ＰＣｄｌｙを制御することにより、逆元演算時の中間値への遷移を抑止することができる。
【００８４】
＜３．変形例＞
上述の実施の形態ではＲｉｊｎｄｅａｌへの適用例について説明したが、数値演算でＳｂｏｘ値を生成する他の暗号にも本発明は適用可能である。例えば、ＡＥＳと同様な構成をとる次世代暗号として、Ｃａｍｅｌｌｉａ、Ｈｉｅｒｏｃｒｙｐｔ等にも適用することができる。
【００８５】
このように、本発明の実施の形態によれば、ＧＦ（（（２2）2）2）逆元演算回路１００において入力データを制御信号ＰＣｄｌｙにより固定値とデコード値の切り替えを制御し、逆元演算後に演算結果をエンコードすることにより、中間値への遷移を抑止することができる。また、逆元演算サイクル数が少ないため、中間値への遷移の確率およびその遷移時間も短く、中間値遷移による消費電流の増加を抑えることができる。そして、それと同時に、高い周波数での動作が可能となる。また、逆元演算回路において、２入力回路での入力遅延の差による中間値への遷移がほとんど発生しないため、その遷移に伴う電流に対するＤＰＡ攻撃が困難になる。また、逆元演算回路の入出力信号の変化は、固定値（例えば「００００＿００００」）から演算結果のデコード値への変化またはその逆であるため、変化する信号線は例えば４本に付き常に１本であり、これは入出力データに依存しない。そのため、入出力信号の変化に対するＤＰＡ攻撃は困難になる。
【００８６】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、本発明の実施の形態において明示したように、本発明の実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本発明の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【符号の説明】
【００８７】
１２ 同形写像変換回路
１６ 逆同形写像・アフィン変換回路
２２ 逆アフィン変換・同形写像変換回路
２６ 逆同形写像変換回路
１７、２１ 排他的論理和（ＸＯＲ）演算回路
３４、３８ スイッチ
１００ ＧＦ（（（２2）2）2）逆元演算回路
１１１〜１１４ デコーダ
１２０ デコードデータによる逆元演算部
１２１ ｘ2・λ演算回路
１２２、１２４ 排他的論理和（ＸＯＲ）演算回路
１２３、１２６、１２７ 乗算回路
１２５ ＧＦ（（２2）2）逆元演算回路
１３１〜１３４ エンコーダ
２３１、２３２ 否定排他的論理和（ＸＮＯＲ）演算回路
２３３ 乗算回路
２３４ 乗算φ演算回路
２３５ 負論理乗算回路
２３６ インバータ
２３７ 負論理入力排他的論理和演算回路
２３８ 排他的論理和（ＸＯＲ）演算回路
９１０、９２０、９３０ レジスタ
【特許請求の範囲】
【請求項１】
ガロア体の入力データよりもビット幅が広い所定の固定値を一旦出力した後に、前記入力データに応じて前記固定値から所定ビット数だけ異なる値を示すデコードデータを出力するデコーダと、
前記デコードデータに対してガロア体の逆元演算を実行して前記デコードデータの逆元データを出力する演算部と、
前記逆元データを前記入力データと等しいビット幅の出力データにエンコードするエンコーダと
を具備するガロア体の逆元演算回路。
【請求項２】
前記デコーダは、制御信号に同期して前記固定値の出力を行う請求項１記載のガロア体の逆元演算回路。
【請求項３】
前記制御信号は、前記入力データが前記デコーダに入力されるタイミングを示す請求項２記載のガロア体の逆元演算回路。
【請求項４】
前記演算部は、前記デコーダから前記固定値が出力されている間は前記固定値を出力する請求項１記載のガロア体の逆元演算回路。
【請求項５】
ガロア体の８ビットの入力データを２ビットずつに区切った４組の部分データに対してそれぞれ４ビット幅の固定値を一旦出力した後に、前記部分データに応じて前記固定値から１ビットだけ異なる４ビット幅のデコードデータをそれぞれ出力する４つのデコーダと、
前記４組のデコードデータからなる１６ビットデータに対して逆元演算を実行して前記１６ビットデータの逆元データを出力する演算部と、
前記逆元データを４ビットずつに区切ってそれぞれ２ビット幅の出力データにエンコードする４つのエンコーダと
を具備するガロア体の逆元演算回路。
【請求項６】
前記４つのデコーダは、共通の制御信号に同期して前記固定値の出力を行う請求項５記載のガロア体の逆元演算回路。
【請求項７】
前記制御信号は、前記入力データが前記デコーダに入力されるタイミングを示す請求項６記載のガロア体の逆元演算回路。
【請求項８】
前記演算部は、前記４つのデコーダの全てが前記固定値を出力している間は４組の前記固定値からなる１６ビット幅のデータを出力する請求項５記載のガロア体の逆元演算回路。
【請求項１】
ガロア体の入力データよりもビット幅が広い所定の固定値を一旦出力した後に、前記入力データに応じて前記固定値から所定ビット数だけ異なる値を示すデコードデータを出力するデコーダと、
前記デコードデータに対してガロア体の逆元演算を実行して前記デコードデータの逆元データを出力する演算部と、
前記逆元データを前記入力データと等しいビット幅の出力データにエンコードするエンコーダと
を具備するガロア体の逆元演算回路。
【請求項２】
前記デコーダは、制御信号に同期して前記固定値の出力を行う請求項１記載のガロア体の逆元演算回路。
【請求項３】
前記制御信号は、前記入力データが前記デコーダに入力されるタイミングを示す請求項２記載のガロア体の逆元演算回路。
【請求項４】
前記演算部は、前記デコーダから前記固定値が出力されている間は前記固定値を出力する請求項１記載のガロア体の逆元演算回路。
【請求項５】
ガロア体の８ビットの入力データを２ビットずつに区切った４組の部分データに対してそれぞれ４ビット幅の固定値を一旦出力した後に、前記部分データに応じて前記固定値から１ビットだけ異なる４ビット幅のデコードデータをそれぞれ出力する４つのデコーダと、
前記４組のデコードデータからなる１６ビットデータに対して逆元演算を実行して前記１６ビットデータの逆元データを出力する演算部と、
前記逆元データを４ビットずつに区切ってそれぞれ２ビット幅の出力データにエンコードする４つのエンコーダと
を具備するガロア体の逆元演算回路。
【請求項６】
前記４つのデコーダは、共通の制御信号に同期して前記固定値の出力を行う請求項５記載のガロア体の逆元演算回路。
【請求項７】
前記制御信号は、前記入力データが前記デコーダに入力されるタイミングを示す請求項６記載のガロア体の逆元演算回路。
【請求項８】
前記演算部は、前記４つのデコーダの全てが前記固定値を出力している間は４組の前記固定値からなる１６ビット幅のデータを出力する請求項５記載のガロア体の逆元演算回路。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【公開番号】特開２０１２−２２２１８（Ｐ２０１２−２２２１８Ａ）
【公開日】平成２４年２月２日（２０１２．２．２）
【国際特許分類】
【出願番号】特願２０１０−１６１２２３（Ｐ２０１０−１６１２２３）
【出願日】平成２２年７月１６日（２０１０．７．１６）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２４年２月２日（２０１２．２．２）
【国際特許分類】
【出願日】平成２２年７月１６日（２０１０．７．１６）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]