(57)【要約】高度な暗号基準のサブバイトファンクションに対するアフィン変換と逆変換を乗法的逆元ＲＯＭを用いて単一アフィン・オール変換にて実現する小さなハードウェア実現が提供される。論理が大幅に低減され、最大パス遅延も、ＲＯＭ実現よりは多少大きくなるが、マルチプレクサ実現と比較して低減される。
2006510067.tif 000002
【特許請求の範囲】
【請求項１】
ラインドールブロック暗号のサブバイトファンクションを遂行するための装置であって、
第一および第二の変換を合成することによって構成されるＳ−ボックスを備え、
前記第一の変換はルックアップテーブルであり、前記第二の変換はアフィンと逆アフィン変換との両方を遂行するアフィン・オール変換である装置。
【請求項２】
前記ルックアップテーブルは、自身に写像される｛００｝を有する有限体ＧＦ（２８）内の乗法的逆元であり、
前記アフィン・オール変換は、組合せ論理回路を用いて実現される請求項１記載の装置。
【請求項３】
前記ルックアップテーブルは、読出し専用メモリによって実現され、
前記組合せ論理回路は、前記アフィン変換に対しては｛１０００１１１１｝から成り、前記逆アフィン変換に対しては｛００１００１０１｝から成るロードパターンとしてのｐ＝ｐ０ｐ１ｐ２ｐ３ｐ４ｐ５ｐ６ｐ７と、前記アフィン変換に対しては｛１１０００１１０｝から成り、前記逆アフィン変換に対しては｛１０１０００００｝から成るロードベクトルとしてのｖ＝ｖ０ｖ１ｖ２ｖ３ｖ４ｖ５ｖ６ｖ７と、を有する式
【数１】
2006510067.tif 000017
を実現する請求項２記載の装置。
【請求項４】
データを暗号化及び復号化するための装置であって、
バイト置換を遂行するように構成されたデータ処理モジュールを備え、
前記データ処理モジュールの少なくとも一部は、
ルックアップテーブルと、
前記ルックアップテーブルを格納するための格納デバイスと、
アフィン変換或いは逆アフィン変換のいずれかを達成する単一変換を遂行する共有論理を有する回路と、
を備える装置。
【請求項５】
前記ルックアップテーブルは、有限体ＧＦ（２８）の乗法的逆元である請求項４記載の装置。
【請求項６】
前記ルックアップテーブルは、読出し専用メモリ（ＲＯＭ）にて実現される請求項５記載の装置。
【請求項７】
前記ルックアップテーブルは、読出し専用メモリ（ＲＯＭ）によって実現される請求項４記載の装置。
【請求項８】
前記装置は、一つのデータ処理パイプラインに配置されたデータ処理モジュールの複数のインスタンスを備える請求項４記載の装置。
【請求項９】
前記装置は、ラインドールブロック暗号に従って暗号化或いは復号化を遂行するように構成され、前記データ処理モジュールは、ラインドールラウンドを実現するように構成される請求項４記載の装置。
【請求項１０】
前記データ処理モジュールは、前記ラインドールラウンドのサブバイト変換を、暗号化に対するアフィン変換と、復号化に対する逆アフィン変換とから合成されるルックアップテーブルを用いて実現するように構成される請求項９記載の装置。
【請求項１１】
前記ルックアップテーブルは、読出し専用メモリによって実現される請求項１０記載の装置。
【請求項１２】
ラインドールブロック暗号器のあるラウンドのサブバイトファンクションを遂行するための装置であって、
有限体ＧＦ（２８）の乗法的逆元を得るための手段と、
アフィン及び逆アフィン変換から成るアフィン・オール変換を単一アフィン変換として遂行するための手段と、を合成することで構成されるＳ−ボックスを備える装置。
【請求項１３】
前記乗法的逆数を得るための手段は、ルックアップテーブルであり、前記アフィン・オール変換を遂行するための手段は、組合せ論理回路である請求項１２記載の装置。
【請求項１４】
ラインドールブロック暗号のあるラインドールラウンドのサブバイトファンクションを遂行するための方法であって、
有限体ＧＦ（２８）内の乗法的逆元に対するルックアップテーブルを生成するステップと、
アフィン及び逆アフィン変換から成るアフィン・オール変換を単一アフィン変換として提供するステップと、
前記ルックアップテーブルと前記アフィン・オール変換から構成されるＳ−ボックスを合成するステップと、
前記合成されたＳ−ボックスを用いて非線形バイト置換を遂行するステップと、
を含む方法。
【請求項１５】
前記提供するステップは、更に、前記単一アフィン変換を遂行する共有論理回路を提供するステップを含む請求項１４記載の方法。
【請求項１６】
前記ルックアップテーブルを読出し専用メモリ内に格納するステップを更に含む請求項１４記載の方法。
【請求項１７】
前記提供するステップは、前記単一アフィン変換を遂行する共有論理回路を実現するステップを更に含む請求項１６記載の方法。
【請求項１８】
前記ルックアップテーブルは、自身に写像される｛００｝を有する有限体ＧＦ（２８）内の乗法的逆元であり、
前記提供するステップは、前記単一アフィン変換を遂行する組合せ論理回路を実現するステップを更に含む請求項１４記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ暗号化の分野に関する。本発明は、より詳細には、以降、ＡＥＳ／Ｒｉｊｎｄａｅｌと呼ばれる、Advanced Encryption Standard（ＡＥＳ）アルゴリズム或いはRijndael Block Cipher（ラインドールブロック暗号）において見られるサブバイトファンクション（SubByte function）の小さなハードウェア実現のための装置及び方法に関する。これを収容するために逆及び通常の両方の処理ができるように再設計される。
【背景技術】
【０００２】
現在の技術水準は、逆暗号（inverse cipher）が、暗号を実現する回路を部分的に再使用するしかできないハードウェア実現を与える。高速ネットワーキングプロセッサ及びスマートカードアプリケーションのためには、非常に小さな（ゲートサイズ）と、（ＯＣ−１９２と９９５３．２８Ｍｂｐｓを超える光キャリア速度及び９．６Ｇｂｐｓなるペイロードに適応する）高いデータ速度が望まれる。
【０００３】
ＡＥＳ／Ｒｉｊｎｄａｅｌは、反復ブロック暗号器であり、Joan DaemenとVincent Rijmenによって書かれ、１９９９年３月９に出版されたプロポーザルにおいて説明されている。ＮＩＳＴ（National Institute of Standards and Technology)は、このＡＥＳ／Ｒｉｊｎｄａｅｌを暗号アルゴリズムとして認証し、２００１年１１月２６日にこのＡＥＳ／Ｒｉｊｎｄａｅｌを公表し（公報 197と呼ばれ、Federal Information Processing Standard 197、或いは、“FIPS197”としても知られている）、これは本明細書に十分述べられているかのように言及することにより組み込まれている。ＡＥＳ／Ｒｉｊｎｄａｅｌを含む、多くのプライベートキー暗号化／復号化アルゴリズムによると、暗号化／復号化は、反復或いはラウンドとして通常知られている複数のステージで遂行される。このようなアルゴリズムは、それら自身、データ処理パイプライン或いはパイプラインアーキテクチャになる。各ラウンドにおいて、ＡＥＳ／Ｒｉｊｎｄａｅｌは、アフィン変換とその逆変換を、他の変換とともに用いることで、情報を復号化（解読）及び暗号化する。暗号化は、データを暗号文と呼ばれる解読不能な形式に変換し、この暗号文の復号化は、このデータを平文（plaintext）と呼ばれる、その元の形式に変換し戻す。
【０００４】
このＡＥＳ／Ｒｉｊｎｄａｅｌアルゴリズムに対する入力及び出力は、各々、（各々が０或いは１なる値を有する）１２８ビットのシーケンスから成る。これらシーケンスは、通常、ブロックと呼ばれ、これらが含むビットの数はそれらの長さと呼ばれる（“FIPS197”、NIST、p.7）。ＡＥＳ／Ｒｉｊｎｄａｅｌアルゴリズムにおける処理のための基本単位は、８ビットのシーケンスが、左側に最上位ビット（most significant bit, ＭＳＢ）を有する単一のエンティティ（entity）として扱われたバイトである。内部的には、ＡＥＳ／Ｒｉｊｎｄａｅｌアルゴリズムの動作は、状態（State）と呼ばれるバイトの二次元アレイに関して遂行される。この状態は、バイトの４つの行から成り、各行は、Ｎｂ個のバイトを含み、ここで、Ｎｂは、ブロック長を３２で割った値である（“FIPS197”、NIST、p.9）。
【０００５】
暗号及び逆暗号（暗号化及び復号化）の開始において、入力、つまり、バイトのアレイ
ｉｎ０，ｉｎ１，．．．ｉｎ１５
が図１に図解されているように状態アレイ内にコピーされる。次に、暗号或いは逆暗号動作がこの状態アレイ内の各バイトに関して遂行され、この後に、最終値が、つまり、バイトのアレイ
ｏｕｔ０，ｏｕｔ１，．．．ｏｕｔ１５
が出力にコピーされる。
【０００６】
有限体内の２つの元の加法は、その２つの元に対する多項式内の対応するべきに対する係数を加えることで達成される。この加法は、ブール排他的ＸＯＲ演算（boolean exclusive XOR operation）にて遂行される（“FIPS197”、NIST、p.10）。２つのバイトを加えるための二進表記は、以下によって与えられる。
【数１】
2006510067.tif 000003
【０００７】
多項式表現においては、有限体ＧＦ（２８）内の乗法は、次数８の既約多項式を法とする多項式の乗法に対応する。ある多項式は、その唯一の約数が、１とそれ自身である場合、既約であると呼ばれる。ＡＥＳ／Ｒｉｊｎｄａｅｌアルゴリズムに対しては、この既約多項式は、
ｍ＜ｘ＞＝ｘ８＋ｘ４＋ｘ３＋ｘ＋１      （１．１）
である（“FIPS197”、NIST、p.10）。
【０００８】
各対角要素が１に等しい対角行列は、単位行列と呼ばれる。
【０００９】
ｎ×ｎ単位行列Ｉｎは、
【数２】
2006510067.tif 000004
として表記される。
【００１０】
もし、Ａ及びＢがｎ×ｎ行列であって、
ＡＢ＝ＢＡ＝Ｉｎ                        （１．３）
のとき、互いに他の逆行列であるいう。
【００１１】
ある行列による乗法と、これに続くあるベクトルの加法から成る変換は、アフィン変換（Affine Transformation）と呼ばれる。
【００１２】
ＡＥＳ／Ｒｉｊｎｄａｅｌのサブバイト（）ファンクションは、状態の各バイトに関して、置換テーブル（Ｓ−ボックス）を用いて独立的に動作する非線形バイト置換である。このＳ−ボックスは、可逆であるが、２つの変換を以下のように合成することで、構成される。
１．前述の有限体ＧＦ（２８）内の乗法的逆元を取り、要素｛００｝は自身の上に写像される。
２．（ＧＦ（２）上で）以下のアフィン変換を適用する。
【数３】
2006510067.tif 000005
【００１３】
行列形式においては、このＳ−ボックスのアフィン変換要素は、以下のように表すことができる（“FIPS197”、NIST、p.16）。
【数４】
2006510067.tif 000006
【００１４】
もし、これを上述のＡＥＳ／Ｒｉｊｎｄａｅｌプロポーザルによって示唆されるようにルックアップテーブルとして実現しようとした場合は、２５６エントリＲＯＭ或いはマルチプレクサが要求されることとなる。このＡＥＳ／Ｒｉｊｎｄａｅｌアルゴリズムを実現するためには、このテーブルの１２回のインスタンス化（instantiations）が必要となる。この行列の逆行列は以下のようにして見いだすことができる。
【数５】
2006510067.tif 000007
【００１５】
もし、これをＡＥＳ／Ｒｉｊｎｄａｅｌプロポーザルによって示唆されるようにルックアップテーブルとして実現しようとした場合は、１２８個のエントリの、１６ビットワードＲＯＭ或いはマルチプレクサが要求されることとなる。このＡＥＳ／Ｒｉｊｎｄａｅｌアルゴリズムを実現するためには、このテーブルの１２回のインスタンス化が必要となる。
【００１６】
従って、ゲート総数を削減するために、アフィン変換に対するほとんど全ての回路を共有するためのシステム及び方法に対する必要性が存在する。高いデータ速度と小さなゲートサイズを達成するためには、その設計は、最大経路が著しく長くならないように、かつゲートサイズが小さくてダイサイズを大幅に増加することなくパラレル処理を促進するために、その設計が複製できるように構成されることが必要となる。ダイサイズが増加すると、コストと電力消費が増加し、製品の市場性が損なわれる。本発明は、最大経路遅延が若干増加することを犠牲にして、ゲートサイズを低減するための装置及び方法である。このことは、回路をより小さくし、このため、高いデータ速度設計に対してより魅力的なものとなる。
【００１７】
ＡＥＳ／Ｒｉｊｎｄａｅｌにおける、アフィン変換と逆アフィン変換の一対の各発生が、本発明によって１つの変換、つまりアフィン・オール変換に低減される。一つの好ましい実施例においては、回路は、通常のアフィン変換と逆アフィン変換の両方を、極めて小さな繰り返し論理（duplicate logic）にて遂行する。この好ましい実施例においては、アフィン・オール変換を乗法的逆元（Multiplicative Inverse）ＲＯＭにて実現することで、論理が、大幅に低減され、最大パス遅延も、ＲＯＭ実現に対するよりもわずかながら増加するが、マルチプレクサ実現と比較すると、低減される。
【００１８】
こうして、本発明のこの好ましい実施例は、乗法的逆元に対しては、読出し専用メモリ（ＲＯＭ）を用い、アフィン変換に対しては、低減された組合せ論理実現（combinational logic implementation）を用いる。この実現は、ゲート数は非常に小さく、ほとんど同程度の最大パス遅延となる。
【発明を実施するための最良の形態】
【００１９】
本発明は、一部、最後の行の所から開始して、行列等式（１．５）及び（１．６）の各行が、その前の行から１ビットだけ左にシフトされるという事実に基づく。本発明においては各行列の第一の行は“ロードパターン（load pattern）”と呼ばれる。こうして、アフィン変換行列に対する“ロードパターン”は｛１０００１１１１｝となり、その逆アフィン変換に対する“ロードパターン”は｛００１００１０１｝となる。各“ロードパターン”内の０の数は奇数であり、これは、本発明のシステム及び方法において２つの変換を１つの回路に融合できるという重要な特徴であるということに注意する。
【００２０】
もし両方のアフィン変換がＤａｅｍｅｎとＲｉｊｍｅｎ（“FIPS197”）によって示唆されるように排他的ＯＲゲートを用いて実現された場合、回路等式（circuit equations）は以下のようなものとなる。
アフィン変換式
【数６】
2006510067.tif 000008
【００２１】
各等式は、奇数個の項、かつ同数の項、すなわち５個の項を有することに注意する。ベクトルの加法（addition）は幾つかの式の否定（negation）を決定する。こうして、各式内の項の数は”ロードパターン”によって決定される。否定の数は“ロードベクトル（load vector）”と呼ばれるベクトルの加法によって決定される。
逆アフィン変換の式
【数７】
2006510067.tif 000009
【００２２】
各等式は、奇数個の項、かつ、同数の項、すなわち３個の項を有することに注意する。ベクトルの加法は、幾つかの式の否定を決定する。こうして、各式内の項の数は“ロードパターン”によって決定される。否定の数はこのベクトルの加法によって決定される。
【００２３】
この加法ベクトルはこんどは、同様に“ロードベクトル”として用いることができる。これら等式の２つの組を調べてみると、融合されるべき共通の論理がないようにみえる。もし、これらの式が、含まれている“ロードパターン”にて書き換えられ、ベクトルの加法を用いて否定を決定すれば、共通の回路が明らかにされる。このことを得るために、排他的ＯＲの特定が用いられ、これらの特性は、
【数８】
2006510067.tif 000010
である。
【００２４】
一つの好ましい実施例においては、アフィン及び逆アフィン変換の両方を実現する回路は、乗法的逆元ＲＯＭを備え、この両方の変換を表す論理は、以下のような、“ロードパターン”としてのｐと、“ロードベクトル”としてのｖとを有している。例えば、アフィン行列の７個の等式は以下の通りとなる。
【数９】
2006510067.tif 000011
【００２５】
インスタンス化の数が半分に削減される。ｐとｂのＡＮＤ演算は、０を生成するので、この等式は、アフィン及び逆アフィン変換の両方に対して機能する。ｂと１とのＸＯＲ演算は常にｂの逆元となるために、適当であれば、ｖを用ることで毎回その等式が否定される。
【００２６】
比較
ＡＥＳ／Ｒｉｊｎｄａｅｌプロポーザル（FIPS197）によって示唆される設計を用いて、（回路が）以下の２つの方法にて実現された。
（１）１２８−エントリ、１６−ビットワードＲＯＭ、
（２）マルチプレクサとして実現される１２８−エントリ、１６−ビットワードルックアップテーブル。
【００２７】
本発明のＲＯＭ、マルチプレクサ、及びオールアフィン回路の実施例が合成され、最大パス分析を用いて時間が計られた。図２はこの結果を示す。つまり、図２には、サイズが、ゲートと、ミクロンの観点から、ＲＯＭ実現と比較して示されている。ネット面積は、ワイアロードモデルが技術によって異なるために、考慮されていない。
【００２８】
このＲＯＭ或いはルックアップテーブルの一つの好ましい実施例は、図３に１６進数フォーマットにて示されているような値を含む。
【００２９】
一つの好ましい実施例のアフィンオール組合せ論理のネットリストが図４に示されている。実現のためのコードが付録Ａとして含まれている。
【００３０】
本発明は、セキュリティネットワーキングプロセッサ、機密キーボードデバイス、磁気カードリーダ、スマートカードデバイス、及び無線８０２．１１デバイス、を含む安全な通信が可能な全てのシステム及びデバイスに適用することができる。
【００３１】
上に説明の実施例は単に典型的な例であり、当業者においてはこれらの修正物及び変形例が明白である。上に説明の実施例に対する様々な修正が添付のクレーム内に具現される本発明の範囲から逸脱することなく可能である。
【００３２】
付録Ａ
アフィン・オール回路を実現するためのＲＴＬを以下に示す。
【表１】
2006510067.tif 000012
2006510067.tif 000013
2006510067.tif 000014
2006510067.tif 000015
2006510067.tif 000016
【図面の簡単な説明】
【００３３】
【図１】状態アレイの入力と出力（“FIPS197”、NIST、p.9）を示す図である。
【図２】従来技術のＲＯＭと、本発明のアフィン・オール実現によるサブバイトファンクションの、ルックアップテーブル（マルチプレクサ）実現との比較を示す図である。
【図３】本発明のアフィン・オール変換に用いられるＲＯＭ或いはルックアップテーブルを示す図である。
【図４】アフィン・オール組合せ論理のネットリストを示す図である。
【図１】
2006510067.tif 000018
【図２】
2006510067.tif 000019
【図３】
2006510067.tif 000020
【図４】
2006510067.tif 000021
【国際調査報告】
2006510067.tif 000022
2006510067.tif 000023