(57)【要約】【課題】  必要メモリ量の増大を抑えつつ、演算回数を削減する。【解決手段】  ＡＥＳ復号処理のミックスカラム逆変換InvMixColumns()の仕様に基づいた行列演算を第１行列Ｐｂと第２行列Ｐａの積で実行する際に、第１行列Ｐｂの１６個の係数ｐｂ11，…，ｐｂ44を｛１｝と｛４｝と｛５｝のみから構成し、第２行列Ｐａの１６個の係数ｐａ11，…，ｐａ44を｛０｝と｛２｝と｛３｝のみから構成するようにしたので、従来に比べ、必要なメモリ量が同一であるにも関わらず、加算回数を２回低減することができる。【選択図】  図３
2008209499.tif 000002
【特許請求の範囲】
【請求項１】
バイト換字逆変換InvSubBytes()及びミックスカラム逆変換InvMixColumns()の処理を含むＡＥＳ暗号方式によるＡＥＳ復号装置であって、
前記バイト換字逆変換InvSubBytes()に用いられ、予め換字対象データの半分のビット数の行データ及び列データとバイト換字逆変換結果s’( )とが互いに関連付けられた逆Ｓボックス情報が記憶された逆Ｓボックス記憶手段と、
前記換字対象データとしての４行４列の入力データｙij(但し、i, j ＝ 1, 2, 3, 4)に基づいて、前記逆Ｓボックス情報を参照しながら前記バイト換字逆変換InvSubBytes()の処理を実行してバイト換字逆変換結果s’(ｙij)を得るバイト換字逆変換手段と、
前記バイト換字逆変換手段により得られたバイト換字逆変換結果s’(ｙij)が記憶されるバイト換字逆変換結果記憶手段と、
前記バイト換字逆変換結果記憶手段内のバイト換字逆変換結果s’(ｙij)に基づき、次式に示すように、列毎のバイト換字逆変換結果（s’(ｙ1j)，s’(ｙ2j)，…，s’(ｙ4j)）に第１行列Ｐｂ＝（ｐｂij）(但し、i, j ＝ 1, 2, 3, 4)及び第２行列Ｐａ＝（ｐａij）(但し、i, j ＝ 1, 2, 3, 4)を乗算することにより、ミックスカラム逆変換InvMixColumns()の処理を実行してミックスカラム逆変換結果（ｘ1j，ｘ2j，…，ｘ４j）を得るミックスカラム逆変換手段と、
【数１】
2008209499.tif 000011
を備えており、
前記第１行列Ｐｂの１６個の係数ｐb11，…，ｐb44が｛１｝と｛４｝と｛５｝のみから構成され、
前記第２行列Ｐａの１６個の係数ｐa11，…，ｐa44が｛０｝と｛２｝と｛３｝のみから構成されることを特徴とするＡＥＳ復号装置。
【請求項２】
請求項１に記載のＡＥＳ復号において、
前記第１行列Ｐｂは
【数２】
2008209499.tif 000012
であることを特徴とするＡＥＳ復号装置。
【請求項３】
請求項２に記載のＡＥＳ復号装置において、
前記ミックスカラム逆変換手段は、
前記第１行列Ｐｂに代えて、前記第１行列Ｐｂに行入れ替えまたは列入れ替えの一方もしくは両方を施して得られる第１行列Ｐｂ’と、
前記第２行列Ｐａに代えて、前記第１行列Ｐｂの行入れ替えに対応した列入れ替えと、前記第１行列Ｐｂの列入れ替えに対応した行入れ替えとを前記第２行列Ｐａに施して得られる第２行列Ｐａ’と
を用いて前記乗算を実行することを特徴とするＡＥＳ復号装置。
【請求項４】
請求項１乃至請求項３のいずれか１項に記載のＡＥＳ復号装置において、
前記ミックスカラム逆変換手段は、
前記乗算する際に、前記第１行列における係数｛４｝の乗算及び係数｛５｝の乗算を係数｛２｝の乗算２回と加算とにより実行し、前記第２行列における係数｛２｝の乗算及び係数｛３｝の乗算を係数｛２｝の乗算１回と加算とにより実行することを特徴とするＡＥＳ復号装置。
【請求項５】
請求項４に記載のＡＥＳ復号装置において、
前記係数｛２｝と乗数との乗算結果を示す乗算表データが記憶された乗算表記憶手段を更に備えており、
前記ミックスカラム逆変換手段は、前記乗算表データを参照しながら前記係数｛２｝の乗算を実行することを特徴とするＡＥＳ復号装置。
【請求項６】
バイト換字逆変換InvSubBytes()及びミックスカラム逆変換InvMixColumns()の処理を含むＡＥＳ暗号方式によるＡＥＳ復号装置のプログラムであって、
前記ＡＥＳ復号装置のコンピュータを、
前記バイト換字逆変換InvSubBytes()に用いられ、予め換字対象データの半分のビット数の行データ及び列データとバイト換字逆変換結果s’( )とが互いに関連付けられた逆Ｓボックス情報を前記コンピュータのメモリに書込む手段、
前記換字対象データとしての４行４列の入力データｙij(但し、i, j ＝ 1, 2, 3, 4)に基づいて、前記逆Ｓボックス情報を参照しながら前記バイト換字逆変換InvSubBytes()の処理を実行してバイト換字逆変換結果s’(ｙij)を得るバイト換字逆変換手段、
前記バイト換字逆変換手段により得られたバイト換字逆変換結果s’(ｙij)をメモリに書込む手段、
このメモリ内のバイト換字逆変換結果s’(ｙij)に基づき、次式に示すように、列毎のバイト換字逆変換結果（s’(ｙ1j)，s’(ｙ2j)，…，s’(ｙ4j)）に第１行列Ｐｂ＝（ｐｂij）(但し、i, j ＝ 1, 2, 3, 4)及び第２行列Ｐａ＝（ｐａij）(但し、i, j ＝ 1, 2, 3, 4)を乗算することにより、ミックスカラム逆変換InvMixColumns()の処理を実行してミックスカラム逆変換結果（ｘ1j，ｘ2j，…，ｘ４j）を得るミックスカラム逆変換手段、
【数３】
2008209499.tif 000013
として機能させ、
前記第１行列Ｐｂの１６個の係数ｐｂ11，…，ｐｂ44が｛１｝と｛４｝と｛５｝のみから構成され、
前記第２行列Ｐａの１６個の係数ｐａ11，…，ｐａ44が｛０｝と｛２｝と｛３｝のみから構成されるプログラム。
【請求項７】
請求項６に記載のプログラムにおいて、
前記第１行列Ｐｂは
【数４】
2008209499.tif 000014
であるプログラム。
【請求項８】
請求項７に記載のプログラムにおいて、
前記ミックスカラム逆変換手段は、
前記第１行列Ｐｂに代えて、前記第１行列Ｐｂに行入れ替えまたは列入れ替えの一方もしくは両方を施して得られる第１行列Ｐｂ’と、
前記第２行列Ｐａに代えて、前記第１行列Ｐｂの行入れ替えに対応した列入れ替えと、前記第１行列Ｐｂの列入れ替えに対応した行入れ替えとを前記第２行列Ｐａに施して得られる第２行列Ｐａ’と
を用いて前記乗算を実行するように前記コンピュータを機能させるためのプログラム。
【請求項９】
請求項６乃至請求項８のいずれか１項に記載のプログラムにおいて、
前記ミックスカラム逆変換手段は、
前記乗算する際に、前記第１行列における係数｛４｝の乗算及び係数｛５｝の乗算を係数｛２｝の乗算２回と加算とにより実行し、前記第２行列における係数｛２｝の乗算及び係数｛３｝の乗算を係数｛２｝の乗算１回と加算とにより実行する手段として前記コンピュータを機能させるためのプログラム。
【請求項１０】
請求項９に記載のプログラムにおいて、
前記係数｛２｝と乗数との乗算結果を示す乗算表データを予めメモリに書込む手段を更に備えており、
前記ミックスカラム逆変換手段は、前記乗算表データを参照しながら前記係数｛２｝の乗算を実行する手段として前記コンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＡＥＳ暗号方式に用いられるＡＥＳ復号装置及びプログラムに係り、例えば、必要メモリ量の増大を抑えつつ、演算回数を削減し得るＡＥＳ復号装置及びプログラムに関する。
【背景技術】
【０００２】
データの秘匿あるいは認証のためには暗号技術が有効であり広く用いられている。暗号化の方法には共通鍵暗号と公開鍵暗号がある。共通鍵暗号では、暗号作成側と復号側で同一の共通鍵を用い、この共通鍵が秘密に管理され、暗号化されたデータ（以下、暗号文）の復号又は認証の際に用いられる。一方、公開鍵暗号では、暗号文作成側と復号側で異なる鍵を用い、暗号文復号用の鍵が秘密に管理され、暗号文作成用の鍵が公開される。
【０００３】
さて、高速かつ安全な共通鍵暗号を構成するために、暗号化対象のデータを適当な長さのブロックに分割し、そのブロック毎に暗号化する方法をブロック暗号と呼ぶ。ブロック暗号方式の代表例として、ＤＥＳ(data encryption standard)暗号が広く知られている。
【０００４】
このＤＥＳ暗号を含め、多くの共通鍵暗号は、換字(substitution)と、置換(permutation)の組み合わせから構成される。換字置換は、共通鍵暗号を構成する一般的な概念である。ＤＥＳ暗号の場合、換字は８種類の参照表をもち、それぞれ６ビットの入力を４ビットに変換する。この参照表による換字を一般にＳボックス(S-box)と呼ぶ。また、ＤＥＳ暗号の代表的な置換であるＰ転置は、３２ビットの入力データをビット毎に並び換え、３２ビットの出力データを得る。
【０００５】
一方、ＤＥＳ暗号と同様のブロック暗号の代表例として、ＡＥＳ暗号が広く知られている（例えば、非特許文献１参照。）。このＡＥＳ暗号では、換字は１種類の参照表により、８ビットの入力データを８ビットの出力データに変換する。また、基本的な転置はガロア体上の乗算で表される。この転置はミックスカラム(MixColumns())演算と呼ばれる。なお、ＡＥＳ暗号は、ラインデール（RIJNDAEL）と呼ばれる暗号を、所定のパラメータの下で実装したものである。
【０００６】
ＡＥＳ暗号は、複数段のＳＰＮ(Substitution Permutation Network)型構造を有している。１段のＳＰＮ型構造は、次の式（１）に示すように、行列演算で表現可能である。ＡＥＳ暗号は、ＳＰＮ型構造を複数回繰り返すことにより、安全性を増進させる。
【０００７】
【数５】
2008209499.tif 000003
【０００８】
ここで、Ｓ(x,k)は入力ｘと鍵ｋの組み合わせに換字を行った出力であり、ｐij（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ）は転置を表す行列Ｐである。以降では、一般性を損なうことなく簡略化のために鍵ｋを省略し、Ｓ（ｘ）と記載する。すなわち、ｘは、入力と鍵との演算を行った中間的な値である。
【０００９】
ＡＥＳ暗号では、４行４列の入力配列ｘij(但しi,j＝1,2,3,4)の列j毎に転置を行うミックスカラム(MixColumns())演算を次の式（２）に示す行列演算で定義している。
【００１０】
【数６】
2008209499.tif 000004
【００１１】
ここで、行列Ｐの要素（あるいは係数）は、０倍、１倍、ｘ倍…、ｘ＾3＋ｘ＾2＋ｘ＋１（ただし、記号＾はべき乗を表す）までの１６通りのパターンを有する。ＡＥＳ暗号ではいわゆるガロア体上の乗算を用い、既約多項式は（ｘ＾4＋ｘ＋１）である。すなわち、乗算結果がｘ＾4以上の場合には、（ｘ＾4＋ｘ＋１）の剰余を用いる。
【００１２】
ＡＥＳ暗号の仕様では、ミックスカラム処理を行列演算で表す場合に、簡単のため、上記係数を２進展開したものを１６進表記で記述する。具体的にはｘ倍は４桁の２進数で００１０と記述でき、１６進数で表記すると係数｛２｝となる。同様に、行列Ｐの要素の係数｛１｝は１倍、２はｘ倍、３は（ｘ＋１）倍に対応する。また、行列演算における加算は排他的論理和演算（あるいはＸＯＲ演算）に対応する。
【００１３】
ＡＥＳ暗号の最も単純な実装方法では、４つの各入力ｘ1j，…，ｘ4jに対してＳボックスによる換字結果を計算し、それぞれについてｙ1jの計算ならば、ｘ1j，ｘ2j，ｘ3j，ｘ4jのそれぞれ換字結果をｘ倍、（ｘ＋１）倍、１倍、１倍して加算する。行列式の計算に用いるガロア体上の乗算を全て事前計算参照表で参照すると仮定すると、必要メモリ量は１種類の換字Ｓと２種類の乗算結果である。
【００１４】
x倍算をxtime() で書くと、式（２）の計算の手続きは、図８に示すように、入力ｘ1j〜ｘ4jをＳボックスにより換字処理して換字結果ｔ1〜ｔ4を求め（ＳＴ１）、各換字結果ｔ1〜ｔ4と行列Ｐの第１行及び第３行とを乗算して結果ｙ1j，ｙ3jを求めると共に（ＳＴ２）、各換字結果ｔ1〜ｔ4と行列Ｐの第２行及び第４行とを乗算して結果ｙ2j，ｙ4jを求める（ＳＴ３）。
【００１５】
すなわち、式（２）の暗号化の計算には、１列あたり、図９に示すように、１単位の換字処理の必要メモリ量（換字処理の参照表（Ｓ−ボックス）のメモリ量）、１単位の置換処理の必要メモリ量（置換処理の参照表（ｘ倍以上の事前計算結果）のメモリ量）、４回の換字処理の参照表参照（“S( )”の回数）、４回の置換処理のｘ倍以上の演算に対する参照表参照（“xtime( )”の回数）、８回の換字処理の加算（“＋”の回数）、といったメモリ量、参照表参照回数及び加算回数が必要となる。
【００１６】
ここで、ｘ倍の演算は、ビットシフトと既約多項式（ｘ＾4＋ｘ＋１）による剰余の演算を行う代わりに参照表（ｘ倍した事前計算結果）を参照するものとして説明するが、換言すれば、ｘ倍の演算をその都度行うことに相当する。
【００１７】
ここで、ＡＥＳ暗号は、Ｓボックス(S-box)が８ビット入力８ビット出力であるため、１単位のメモリ量が一般に２５６バイトとなる。また、演算回数は８ビット同士の演算の回数である。
【００１８】
以上の実装方法は最も単純な例であり、必要十分なメモリ量と演算ワード長があるならば、より効率的な実装方法がある。例えば、Ｓボックスによる換字と行列Ｐによる置換を結合した換字置換関数ＳＰの出力をメモリなどに事前計算することにより、必要な演算量を削減できる。
【００１９】
この効率的な実装方法の例として、８ビットの入力ｘ1j，…，ｘ4jに対して換字Ｓを行った８ビット出力をそれぞれｘ倍、（ｘ＋１）倍、１倍、１倍した３２ビットの事前計算参照表を用いる場合、式（２）の暗号化の計算には、１列あたり、４単位の換字置換処理の必要メモリ量、４回の換字転置処理の参照表参照、３回の換字転置処理のシフト、３回の換字転置処理の加算、のメモリ量、参照表参照回数、シフト回数、加算回数が必要となる。
【００２０】
この効率的な実装方法は、最も単純な実装方法に比べ、メモリ量の増加と引き替えに演算回数の削減と、計算機の演算でも特に低速な参照表参照回数の削減とにより、処理効率を向上させることが可能となる。
【００２１】
但し、この効率的な実装方法は、計算機が４バイトの演算ワード長を持つ必要があるので、仮に計算機の演算ワード長が２バイトの場合には全ての演算回数が２倍に増加し、処理効率の向上が小さくなる。  
以上は、ＡＥＳ暗号技術における暗号化の場合の代表的な実装方法である。
【００２２】
しかしながら、ＡＥＳ暗号では、暗号化の処理と復号の処理手順が若干異なるため、復号処理においては、暗号化とは別に換字あるいは換字置換用の事前計算格納のメモリが必要となる。
【００２３】
ＡＥＳ暗号方式による復号処理では、暗号化の際に行ったミックスカラム処理の転置操作を消去する逆転置の操作としてミックスカラム逆変換(InvMixColumn)の処理が必要となる。ミックスカラム逆変換の処理は、４行４列の入力配列ｙij(但しi,j＝1,2,3,4)の列j毎に、式（３）に示す行列演算で定義される。ここで、“Ｅ”などは１６進数表記であり、 (x＾3＋ｘ＾2＋ｘ)倍に相当する。
【００２４】
【数７】
2008209499.tif 000005
【００２５】
ＡＥＳ暗号方式における復号処理の最も単純な実装方法は、４つの各入力ｙ1j，…，ｙ4jに対してＳボックスによる換字の逆変換結果を計算し、それぞれについてｘ1jの計算ならば、ｙ1j,ｙ2j,ｙ3j,ｙ4jのそれぞれ換字結果を(ｘ＾3＋ｘ＾2＋ｘ)倍、(ｘ＾3＋ｘ＋１)倍、(x＾3＋ｘ＾2＋１)倍、(ｘ＾3＋１)倍して加算する。行列式の計算に用いるガロア体上のｘ倍以上の乗算を全て事前計算参照表で参照すると仮定すると、必要メモリ量は１種類の換字の逆変換ｓ’と４種類の乗算結果である。
【００２６】
式（３）の復号の計算には、１列あたり、１単位の換字処理の必要メモリ量、４単位の置換処理の必要メモリ量、４回の換字処理の参照表参照、１６回の置換処理のｘ倍以上の演算に対する参照表参照、１２回の換字処理の加算、のメモリ量、参照表参照回数、加算回数が必要となる。
【００２７】
従って、ＡＥＳの復号処理においては、ＡＥＳの暗号化処理よりも多くのメモリ量及び参照表参照が必要となる。
【００２８】
以上の実装方法は最も単純な例であり、必要十分なメモリ量と演算ワード長があるならば、より効率的な実装方法がある。例えば、Ｓボックスによる換字の逆変換Ｓ’と行列Ｐによる置換の逆変換Ｐ’を結合した換字置換関数Ｓ’Ｐ’の出力をメモリなどに事前計算することにより、必要な演算量を削減できる。
【００２９】
この効率的な実装方法の例として、８ビットの入力ｙ1j，…，ｙ4jに対して換字の逆変換Ｓ’を行った８ビット出力をそれぞれ（ｘ＾3＋ｘ＾2＋ｘ)倍、(ｘ＾3＋ｘ＋１)倍、(ｘ＾3＋ｘ＾2＋１)倍、(ｘ＾3＋１)倍した３２ビットの事前計算参照表を用いる場合、４種類の換字の各出力が４倍の大きさとなるから、式（３）の復号の計算には、１列あたり、１６単位の換字置換処理の必要メモリ量、４回の換字転置処理の参照表参照、３回の換字転置処理のシフト、３回の換字転置処理の加算、のメモリ量、参照表参照回数、シフト回数、加算回数が必要となる。
【００３０】
この効率的な実装方法は、最も単純な実装方法に比べ、メモリ量の増加と引き替えに演算回数の削減と、計算機の演算でも特に低速な参照表参照回数の削減により、処理効率を向上させることが可能となる。
【００３１】
また、この効率的な実装方法では、暗号化よりも復号の演算量が多い単純な実装方法とは異なり、暗号化と復号の演算量が同一であるので、鍵スケジュールを除いた暗号化と復号とを同じ処理効率で実行できる。
【００３２】
なお、上述したＡＥＳ暗号の暗号化及び復号方法は、必要なメモリを確保可能なパーソナルコンピュータなど計算機環境における効率的な実装である。すなわち、ＩＣカードやコントローラといった、必要メモリの削減の優先度が高いシステムでの利用に際しては、ＡＥＳ暗号技術は、異なる実装方法が求められる。また、計算機のワード長が小さい場合、事前計算の参照表を利用する方法は処理効率が低下する。
【００３３】
一方、ＡＥＳ暗号同様に、置換処理にガロア体上の乗算を用いたＳＨＡＲＫ暗号では、３２ビット出力の事前計算参照表を複数用いた方法以外にも、事前計算参照表を削減する方法が述べられている（例えば、非特許文献２参照。）。非特許文献２では、置換行列Ｐを行列計算で行うとともに、置換行列Ｐを行列計算の基本的算法であるＬＵ分解により計算量を削減し、処理の効率化を図る手法が開示されている。
【００３４】
また、ＡＥＳ暗号同様に、置換処理にガロア体上の乗算を用いたヒエロクリプト(Hierocrypt)暗号では、置換Ｐの演算幅よりも計算機のワード長が短い場合における効率的な実装方法が本発明者らにより発表されている（例えば、非特許文献３参照。）。非特許文献３記載の方法は、式（１）で表されるＳＰＮ型暗号の置換行列Ｐを二つ以上の行列式の積を用いて計算する。次の式（４）は置換行列Ｐを二つの行列Ｐａ，Ｐｂの積で示している。
【００３５】
【数８】
2008209499.tif 000006
【００３６】
…（４）
非特許文献３記載の方法においては、行列Ｐａ，Ｐｂを適切に選択することにより、例えばｘ倍とｘ＾2倍の演算の組を２種類の演算参照表ではなく、ｘ倍算の１種類の演算参照表を２回参照することにより実現できる。すなわち、必要な事前計算参照表の数を削減できる。行列の選択は暗号アルゴリズムの仕様に依存し、自明でない。
【００３７】
ＡＥＳ暗号の暗号化処理では、置換行列Ｐにｘ倍や（ｘ＋１）倍の２種類の乗算値しか現れない上に、入力ｘの（ｘ＋１）倍算は入力ｘのｘ倍の計算に入力ｘを足せば計算できるため、１種類の事前計算参照表で実現可能である。そのため、式（４）に示す２つ以上の行列の積を用いる方法で、事前計算参照表の数を削減することはできない。
【００３８】
しかしながら、ＡＥＳ暗号の復号処理に着目すると、復号処理では(ｘ＾3＋ｘ＾2＋ｘ)倍、(ｘ＾3＋ｘ＋１)倍、(ｘ＾3＋ｘ＾2＋１)倍、(ｘ＾3＋１)倍の４種類の事前計算参照表が必要とされる。ここで、置換行列の逆行列Ｐ’を複数の行列の積で表現することにより事前計算参照表の数を削減可能である。事前計算参照表数の削減は、ＩＣカードやコントローラといった、必要メモリの削減の優先度が高いシステムでの利用に際して有用である。
【００３９】
一方、バレット(Paulo Barreto)は、同様の考えをＡＥＳ暗号の復号処理に適用し、式（５）で示される行列演算による置換Ｐの逆変換Ｐ’の計算方法を提案した（例えば、非特許文献４参照。）。
【００４０】
【数９】
2008209499.tif 000007
【００４１】
x倍算をxtime()で書くと、式（５）の計算の手続きは、図１０に示すように表される。すなわち、４行４列の入力配列ｙij(但しi,j＝1,2,3,4)のうち、ｊ列目の入力ｙ1j〜ｙ4jをＳボックスにより換字処理して換字結果ｔ1〜ｔ4を求める（ＳＴ１１）。
【００４２】
続いて、この換字結果ｔ1〜ｔ4と第１行列の第１行(2 3 1 1)及び第３行(1 1 2 3)との乗算途中結果ｖ1，ｖ3を求めると共に（ＳＴ１２）、各換字結果ｔ1〜ｔ4と第１行列の第２行(1 2 3 1)及び第４行(3 1 1 2)との乗算途中結果ｖ2，ｖ4を求める（ＳＴ１３）。さらに、この乗算途中結果ｖ1〜ｖ4に換字結果ｔ1〜ｔ4を加算して乗算結果ｖ1〜ｖ4を求める（ＳＴ１４）。この乗算結果ｖ1〜ｖ4は、換字結果ｔ1〜ｔ4と第１行列との乗算結果を意味している。
【００４３】
次に、乗算結果ｖ1〜ｖ4と第２行列との乗算を実行する。具体的には乗算結果ｖ1〜ｖ4に対し、ｘ倍算を実行して途中結果ｗ1，ｗ2を算出し（ＳＴ１５）、この途中結果ｗ1，ｗ2に乗算結果ｖ1〜ｖ4を個別に加算することにより、乗算結果ｘ1j〜ｘ4jを算出する（ＳＴ１６）。この乗算結果ｘ1j〜ｘ4jは、乗算結果ｖ1〜ｖ4と第２行列との乗算結果を意味しており、換言すると、ｊ列目の入力ｙ1j〜ｙ4jに対するミックスカラム逆変換の結果Ｐ’を意味している。
【００４４】
非特許文献４記載の手法は、暗号化の置換Ｐのミックスカラム(MixColumn)処理を元に、最小限の付加的な演算を加えることにより、復号の置換Ｐ’のミックスカラム逆変換(InvMixColumn)の処理を実現する方法である。
【００４５】
具体的には、復号用の逆変換Ｐ’は、暗号化処理の置換Ｐに１０回の加算(ＸＯＲ演算)と４回のｘ倍算処理を追加することとなり、１列あたり、図１１に示すように、１単位の換字処理の必要メモリ量（換字処理の参照表（Ｓ−ボックス）のメモリ量）、１単位の置換処理の必要メモリ量（置換処理の参照表（ｘ倍以上の演算の事前計算結果）のメモリ量）、４回の換字処理の参照表参照回数（“S( )”の回数）、８回の置換処理のｘ倍以上の演算に対する参照表参照回数（“xtime( )”の回数）、１８回の換字処理の加算回数（“＋”の回数）、といったメモリ量、参照表参照回数、加算回数が必要である。
【００４６】
非特許文献４記載の方法は、暗号化と復号で処理の一部が共有できる点が優れている。なお、共有部分が少ないことから、ソフトウェアでの実装に比べ、僅かでも回路規模を削減したいハードウェアでの実装に向いている。
【非特許文献１】米国標準技術研究所 (National Institute of Standards and Technology): "Advanced Encryption Standard", Federal Information Processing Standards 197,2001
【非特許文献２】Rijmen, et al.: "The Cipher SHARK", Fast Software Encryption, LNCS 1039, pp.99-111, Springer-Verlag, 1996
【非特許文献３】佐野ら: “Hierocrypt の実装について”暗号と情報セキュリティシンポジウム,2001
【非特許文献４】Public Comments on the Draft Federal Information Processing Standard(FIPS) for the Advanced Encryption Standard(AES)
【発明の開示】
【発明が解決しようとする課題】
【００４７】
しかしながら非特許文献４記載の方法は、本発明者の検討によれば、メモリ量の削減の観点から優れた実装手法であるものの、暗号用の置換Ｐを包含するため、必ずしも最適な実装手法とは言えない。すなわち、非特許文献４記載の方法は、例えば、必要メモリ量の増大を抑えつつ、演算回数を削減させる余地があると考えられる。
【００４８】
本発明は上記実情を考慮してなされたもので、必要メモリ量の増大を抑えつつ、演算回数を削減し得るＡＥＳ復号装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００４９】
第１の発明は、バイト換字逆変換InvSubBytes()及びミックスカラム逆変換InvMixColumns()の処理を含むＡＥＳ暗号方式によるＡＥＳ復号装置であって、前記バイト換字逆変換InvSubBytes()に用いられ、予め換字対象データの半分のビット数の行データ及び列データとバイト換字逆変換結果s’( )とが互いに関連付けられた逆Ｓボックス情報が記憶された逆Ｓボックス記憶手段と、前記換字対象データとしての４行４列の入力データｙij(但し、i, j ＝ 1, 2, 3, 4)に基づいて、前記逆Ｓボックス情報を参照しながら前記バイト換字逆変換InvSubBytes()の処理を実行してバイト換字逆変換結果s’(ｙij)を得るバイト換字逆変換手段と、前記バイト換字逆変換手段により得られたバイト換字逆変換結果s’(ｙij)が記憶されるバイト換字逆変換結果記憶手段と、前記バイト換字逆変換結果記憶手段内のバイト換字逆変換結果s’(ｙij)に基づき、次式に示すように、列毎のバイト換字逆変換結果（s’(ｙ1j)，s’(ｙ2j)，…，s’(ｙ4j)）に第１行列Ｐｂ＝（ｐｂij）(但し、i, j ＝ 1, 2, 3, 4)及び第２行列Ｐａ＝（ｐａij）(但し、i, j ＝ 1, 2, 3, 4)を乗算することにより、ミックスカラム逆変換InvMixColumns()の処理を実行してミックスカラム逆変換結果（ｘ1j，ｘ2j，…，ｘ４j）を得るミックスカラム逆変換手段と、  
【００５０】
【数１０】
2008209499.tif 000008
【００５１】
を備えており、前記第１行列Ｐｂの１６個の係数ｐｂ11，…，ｐｂ44が｛１｝と｛４｝と｛５｝のみから構成され、前記第２行列Ｐａの１６個の係数ｐａ11，…，ｐａ44が｛０｝と｛２｝と｛３｝のみから構成されるＡＥＳ復号装置である。
【００５２】
なお、第１の発明は、「装置」として表現したが、「装置」に限らず、「方法」、「プログラム」又は「プログラムを記憶した記憶媒体」として表現してもよい。
【００５３】
（作用）
第１の発明は、第１行列Ｐｂの１６個の係数ｐｂ11，…，ｐｂ44を｛１｝と｛４｝と｛５｝のみから構成し、第２行列Ｐａの１６個の係数ｐａ11，…，ｐａ44を｛０｝と｛２｝と｛３｝のみから構成するようにしたので、従来の図１１及び各実施形態の図５から分かるように、必要なメモリ量が同一であるにも関わらず、加算回数を２回低減することができる。すなわち、第１の発明では、必要メモリ量の増大を抑えつつ、演算回数を削減することができる。
【発明の効果】
【００５４】
以上説明したように本発明によれば、必要メモリ量の増大を抑えつつ、演算回数を削減できる。
【発明を実施するための最良の形態】
【００５５】
以下、本発明の各実施形態について図面を用いて説明する。なお、以下のＡＥＳ復号装置は、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体からＡＥＳ復号装置のコンピュータにインストールされ、ＡＥＳ復号装置の機能をコンピュータに実現させるためのプログラムが用いられる。
【００５６】
（第１の実施形態）
図１は本発明の第１の実施形態に係るＡＥＳ復号装置の構成を示す模式図である。このＡＥＳ復号装置１０は、バイト換字逆変換InvSubBytes()及びミックスカラム逆変換InvMixColumns()の処理を含むＡＥＳ暗号方式による装置である。
【００５７】
具体的には、ＡＥＳ復号装置１０は、ＩＣカード又はコントローラ等のように必要メモリ量の削減が要請される装置であり、ＲＯＭ１、ＲＡＭ２、不揮発性メモリ３、ＣＰＵ４及び入出力部５が互いにバス６を介して接続された構成となっている。
【００５８】
ここで、ＲＯＭ１は、ＣＰＵ５から読出可能な読出専用メモリであり、ＡＥＳ復号装置１０のＯＳが予め記憶されている。
【００５９】
ＲＡＭ２は、ＣＰＵ５から読出／書込可能なランダムアクセスメモリであり、不揮発性メモリ３の記憶内容が読み出され、ＡＥＳ復号処理中に暗号文、鍵、処理中データ、復号された平文等を一時的に保存するために用いられる。ラウンド鍵配列２ａ、内部状態配列(State array)２ｂは、ＲＡＭ２の一部の領域に形成されている。
【００６０】
不揮発性メモリ３は、ＣＰＵ５から読出／書込可能で電源オフ時にも記憶内容が消去されないメモリであり、例えば、外部の記憶媒体からインストールされたＡＥＳ復号処理の動作プログラム、逆Ｓボックス(inverse S-box)に相当する参照表（逆Ｓボックス情報）、及びｘ倍算の事前計算結果を示す参照表（乗算表データ）、などが予め記憶され、また、外部のＡＥＳ暗号装置（図示せず）と共有する鍵、などが適宜、記憶される。なお、共有する鍵（共通鍵）の鍵長は、ＡＥＳ暗号の仕様の通り、１２８ビット、１９２ビット又は２５６ビットのいずれでもよい。
【００６１】
ここで、一方の参照表（逆Ｓボックス情報）は、８ビット入力８ビット出力に対応しており、バイト換字逆変換InvSubBytes()に用いられ、予め換字対象データの半分のビット数の行データ及び列データとバイト換字逆変換結果s’( )とが互いに関連付けられている。ここでは、換字対象データとしてのｉ行ｊ列の入力データｙijを個別にバイト換字逆変換結果s’(ｙij)に関連付けている。例えば、入力データｙ12＝｛ｅｄ｝を、参照表のｅ行目でｄ列目のバイト換字逆変換結果ｓ’(ｅｄ)＝｛５３｝に関連付ける換字表として構成されている。
【００６２】
また、他方の参照表（乗算表データ）は、８ビット入力８ビット出力に対応しており、行列演算時に参照され、係数｛２｝と乗数との乗算結果を示すものである。
【００６３】
ＣＰＵ４は、入出力部５から入力された暗号化データに対してＡＥＳ復号処理を実行し、得られた復号結果を入出力部５から出力するＡＥＳ復号処理を実行するものであり、具体的にはメモリ１〜３を参照しながら、図２乃至図４に示す処理を実行する機能をもっている。
【００６４】
ここで、ＣＰＵ４は、例えば、ｉ行ｊ列の入力データｙij(但し、i, j ＝ 1, 2, 3, 4)に基づいて、逆Ｓボックスに相当する参照表を参照しながらバイト換字逆変換InvSubBytes()の処理を実行してバイト換字逆変換結果s’(ｙij)を得る機能と、得られたバイト換字逆変換結果s’(ｙij)をＲＡＭ２に書き込む機能と、このバイト換字逆変換結果s’(ｙij)に基づき、次式に示すように、列ｊ毎のバイト換字逆変換結果（s’(ｙ1j)，s’(ｙ2j)，…，s’(ｙ4j)）に第１行列Ｐｂ＝（ｐｂij）(但し、i, j ＝ 1, 2, 3, 4)及び第２行列Ｐａ＝（ｐａij）(但し、i, j ＝ 1, 2, 3, 4)を乗算することにより、ミックスカラム逆変換InvMixColumns()の処理を実行してミックスカラム逆変換結果（ｘ1j，ｘ2j，…，ｘ４j）を得る機能とをもっている。
【００６５】
【数１１】
2008209499.tif 000009
【００６６】
なお、ＣＰＵ４は、第１行列Ｐｂに代えて、第１行列Ｐｂにおける行ｉ同士または列ｊ同士の一方もしくは両方を入れ替えた第１行列Ｐｂ’と、第２行列Ｐａに代えて、第２行列Ｐａにおける行ｉ同士または列ｊ同士の一方もしくは両方を入れ替えた第２行列Ｐａ’とを用いて乗算を実行してもよい。この入れ替えの例は第２の実施形態で具体的に述べる。
【００６７】
また、ＣＰＵ４は、乗算する際に、第１行列Ｐｂにおける係数｛４｝の乗算及び係数｛５｝の乗算を係数｛２｝の乗算２回と加算とにより実行し、第２行列Ｐａにおける係数｛２｝の乗算及び係数｛３｝の乗算を係数｛２｝の乗算１回と加算とにより実行する。係数｛２｝の乗算は、ＲＡＭ２内の参照表（乗算表データ）の参照により実行される。
【００６８】
入出力部５は、図示しない外部装置とＡＥＳ復号装置１０との間のデータ等の入出力機能を有し、さらに、ＡＥＳ復号装置１０がＩＣカードの場合には外部からＡＥＳ復号装置１０内への電源の入力機能などをもっている。
【００６９】
次に、以上のように構成されたＡＥＳ復号装置の動作を図２乃至図４のフローチャートを用いて説明する。  
（ＡＥＳ暗号方式の復号処理）
いま、ＡＥＳ復号装置１０では、操作者の操作により、ＡＥＳ復号プログラムが起動され、不揮発性メモリ３の記憶内容がＲＡＭ２に書き込まれたとする。また、ＡＥＳ復号装置１０では、操作者の操作により、暗号文データが入出力部５を介してＲＡＭ２に書き込まれた後、復号要求が入出力部５を介して入力されたとする。
【００７０】
ＣＰＵ４は、この復号要求を受けると、ＲＡＭ２内の鍵をラウンド鍵配列２ａに書き込むと共に（ＳＴ２１）、暗号文データをＲＡＭ２内の内部状態配列２ｂに書き込む（ＳＴ２２）。
【００７１】
しかる後、ＣＰＵ４は、ＡＥＳ暗号方式の仕様に基づいた復号処理の繰り返し処理を実行する（ＳＴ２３〜ＳＴ３０）。ＡＥＳ暗号方式では、１２８ビット鍵の場合には１０回の繰り返し処理を実行し、１９２ビット鍵の場合には１２回の繰り返し処理を実行し、２５６ビット鍵の場合には１４回の繰り返し処理を実行する。繰り返される処理の一単位は、一般に、「段」又は「ラウンド」と呼ばれる。
【００７２】
１段の処理においては、ＣＰＵ４は内部状態配列２ｂの記憶内容を読み出し（ＳＴ２３）、鍵加算(AddKey)処理を実行する（ＳＴ２４）。鍵加算処理は、内部状態配列２ｂの記憶内容に対し、ラウンド鍵配列２ａ内のラウンド鍵を加算する処理である。
【００７３】
鍵加算処理の後、ＣＰＵ４は、４行４列の内部状態配列２ｂの記憶内容（ｙij）(i, j ＝ 1, 2, 3, 4)に対し、逆Ｓボックスに相当する参照表を参照しながらバイト換字逆変換InvSubBytes()の処理を実行して１６個のバイト換字逆変換結果s’(ｙij)を得ると（ＳＴ２５）、これらバイト換字逆変換結果s’(ｙij)をＲＡＭ２の内部状態配列２ｂに書き込む。
【００７４】
続いて、ＣＰＵ４は、ＡＥＳ暗号方式の仕様に定められた最終段か否かの判定を行い（ＳＴ２６）、最終段の場合には、ラウンド鍵配列２ａ内の復号用ラウンド鍵を更新し（ＳＴ３１）、更新後のラウンド鍵で内部状態配列２ｂの記憶内容に対して鍵加算(AddKey)処理を実行し（ＳＴ３２）、得られた平文を出力する（ＳＴ３３）。
【００７５】
一方、ステップＳＴ２６の判定の結果、最終段でない場合には、内部状態配列２ｂ内のバイト換字逆変換結果s’(ｙij)の列ｊ毎に、ミックスカラム逆変換InvMixColumns()のうちの第１行列Ｐｂによる変換処理と（ＳＴ２７）、第２行列Ｐａによる変換処理とを順次、実行する（ＳＴ２８）。
【００７６】
全ての列ｊに対し、第１及び第２行列Ｐｂ，Ｐａによる変換処理が終了すると、ＣＰＵ４は、得られた変換結果（ｘij）(但しi,j＝1,2,3,4)を内部状態配列２ｂに更新する（ＳＴ２９）。
【００７７】
ここで、ステップＳＴ２７〜ＳＴ２９のミックスカラム逆変換InvMixColumns()の処理について図３を用いて述べる。  
ミックスカラム逆変換InvMixColumns()の処理においては、始めに、４行４列の内部状態配列２ｂに記憶されたバイト換字逆変換結果s’(ｙij)をＲＡＭ２内の４行４列の一時記憶領域（図示せず）に読み出す（ＳＴ２７−１）。ＣＰＵ４は、４行４列のバイト換字逆変換結果s’(ｙij)に対し、１列毎に処理を行うため、ＲＡＭ２内のカウンタ値ｊを１で初期化する（ＳＴ２７−２）。
【００７８】
ＣＰＵ４は、カウンタ値ｊで示されるｊ列目の４バイトのバイト換字逆変換結果s’(ｙ1j)，…，s’(ｙ4j)を参照し（ＳＴ２７−３）、このバイト換字逆変換結果s’(ｙ1j)，…，s’(ｙ4j)と第１行列Ｐｂとを乗算して変換処理を実行し、４バイトの中間値を求める（ＳＴ２７−４）。
【００７９】
続いて、ＣＰＵ４は、この中間値と第２行列Ｐａとを乗算して変換処理を実行し、４バイトの内部状態の更新値ｘ1j，…，ｘ4jを求め（ＳＴ２８−１）、一時記憶領域内のｊ列目のバイト換字逆変換結果s’(ｙ1j)，…，s’(ｙ4j)を更新値ｘ1j，…，ｘ4jに更新する（ＳＴ２８−２）。
【００８０】
次に、ＣＰＵ４は、カウンタ値ｊに１を加え（ＳＴ２８−３）、カウンタ値ｊが４以下であるかを判定し（ＳＴ２８−４）、カウンタ値ｊが４以下の場合には、ステップＳＴ２７−３に戻って処理を繰り返す。
【００８１】
一方、ステップＳＴ２８−４の判定の結果、カウンタ値ｊが４を越えた場合には、１列目から４列目までの全ての列ｊに対し、第１及び第２行列Ｐｂ，Ｐａによる変換処理が終了したことになる。
【００８２】
従って、ＣＰＵ４は、一時記憶領域内の４行４列の更新値（ｘij）により内部状態配列２ｂを更新し（ＳＴ２９）、図３に示すミックスカラム逆変換InvMixColumns()の処理を終了する。
【００８３】
以下、図２に示すように、ＣＰＵ４は、前述同様に、ラウンド鍵配列２ａ内の復号用ラウンド鍵を更新し（ＳＴ３０）、次段の処理として、ステップＳＴ２３からの処理を繰り返す。
【００８４】
（ミックスカラム逆変換の評価）
次に、以上のようなミックスカラム逆変換InvMixColumns()の処理を評価する。具体的には、式（６）に基づいた図３の計算の手続きから、計算に必要なメモリ量や、計算の複雑さ、回数をまとめる。行列に記述されたｘ倍算をxtime() で書くと、図４に示す通りとなる。
【００８５】
すなわち、ＣＰＵ４は、ステップＳＴ２７−３で参照したｊ列目のバイト換字逆変換結果s’(ｙ1j)，…，s’(ｙ4j)を入力データｔ1〜ｔ4とし（ＳＴ２７−４−１）、この入力データｔ1〜ｔ4と第１行列Ｐｂとを乗算して乗算途中結果ｖ1，ｖ2を求める（ＳＴ２７−４−２）。ここで、ＣＰＵ４は、この第１行列Ｐｂとの乗算の際に、第１行列Ｐｂにおける係数｛４｝の乗算及び係数｛５｝の乗算を係数｛２｝の乗算２回と加算とにより実行する。このとき、ＣＰＵ４は参照表（乗算表データ）を４回参照する。
【００８６】
さらに、ＣＰＵ４は、この乗算途中結果ｖ1，ｖ2に入力データｔ1〜ｔ4を加算して中間値ｔ1〜ｔ4を求める（ＳＴ２７−４−３）。この中間値ｔ1〜ｔ4は、入力データｔ1〜ｔ4と第１行列Ｐｂとの乗算結果を意味している。
【００８７】
次に、ステップＳＴ２７−４で得られた中間値ｔ1〜ｔ4と第２行列Ｐａとの乗算を実行して内部状態の更新値ｘ1j〜ｘ4jを算出する（ＳＴ２８−１）。ここで、ＣＰＵ４は、第２行列Ｐａとの乗算の際に、第２行列Ｐａにおける係数｛２｝の乗算及び係数｛３｝の乗算を係数｛２｝の乗算１回と加算とにより実行する。このとき、ＣＰＵ４は参照表（乗算表データ）を４回参照する。
【００８８】
ステップＳＴ２８−１で得られた内部状態の更新値ｘ1j〜ｘ4jは、バイト換字逆変換結果s’(ｙ1j)，…，s’(ｙ4j)に対するミックスカラム逆変換の処理結果Ｐ’を意味している。
【００８９】
なお、ガロア体上での演算であるため、図４中の加算＋は、ＸＯＲ演算となる。  
これにより、内部状態配列２ｂ内の値のうち、１列分の４バイトについて計算される。内部状態配列は４列分あるため、図３のフローチャートに基づいて、２列目（ｊ＝２）、３列目（ｊ＝３）、４列目（ｊ＝４）の場合の乗算結果（ｘij）をそれぞれ計算する。
【００９０】
この場合、１列あたり、図５に示すように、１単位の換字処理の必要メモリ量（換字処理の参照表（Ｓ−ボックス）のメモリ量）、１単位の置換処理の必要メモリ量（置換処理の参照表（ｘ倍以上の演算の事前計算結果）のメモリ量）、４回の換字処理の参照表参照（“S( )”の回数）、８回の置換処理のｘ倍以上の演算に対する参照表参照（“xtime( )”の回数）、１６回の換字処理の加算（“＋”の回数）、といったメモリ量、参照表の参照回数及び加算回数が必要となる。
【００９１】
参照表の参照回数については、ＡＥＳ暗号の復号処理をそのまま実装する式（３）における１６回に比べ、本実施形態では８回に半減する。また、加算回数については、従来の効率的な実装であるバレットの方法（図１１）における１８回に比べ、本実施形態では１６回に削減された。すなわち、加算回数は、１列の演算毎に２回削減された。
【００９２】
この計算手順では、行列の係数｛２｝に対応するｘ倍の計算に対応した置換処理メモリに対する参照表参照で行ったが、シフトと定数のＸＯＲを組み合わせた方法による計算も可能である。
【００９３】
上述したように本実施形態によれば、ＡＥＳ復号処理のミックスカラム逆変換InvMixColumns()の仕様に基づいた行列演算を第１行列Ｐｂと第２行列Ｐａの積で実行する際に、第１行列Ｐｂの１６個の係数ｐｂ11，…，ｐｂ44を｛１｝と｛４｝と｛５｝のみから構成し、第２行列Ｐａの１６個の係数ｐａ11，…，ｐａ44を｛０｝と｛２｝と｛３｝のみから構成するようにしたので、従来の図１１及び各実施形態の図５から分かるように、必要なメモリ量が同一であるにも関わらず、加算回数を２回低減することができる。すなわち、本実施形態では、行列演算により必要メモリ量を抑制し、行列内の係数の適正化により演算回数を減らしたので、必要メモリ量の増大を抑えつつ、演算回数を削減できる。従って、十分なメモリ容量を確保できない環境において、効率的にＡＥＳ暗号の復号処理を実行できる。換言すると、本実施形態によれば、メモリ量が少ない場合には、最もメモリ読出回数及び演算回数が少なく、最も高速な実装方法を提供することができる。
【００９４】
また、本実施形態は、ＡＥＳ暗号方式の復号処理を実行するデバイス、例えば復号処理モジュール又は暗復号処理モジュールを持つＩＣカードあるいはその他の暗号処理装置に適用することができる。本実施形態の構成を適用することにより、ＩＣカードなどの読出／書込可能なメモリや読出専用メモリの容量が厳しく制限された計算装置において、ＡＥＳ暗号方式の復号機能を持つデバイスあるいは装置を提供することができる。
【００９５】
また、本実施形態は、ＩＣカードやコントローラのように８ビットあるいは１６ビットを基本演算単位とする任意の演算装置をＡＥＳ復号装置１０とした場合においても、同様の効果を得ることができる。
【００９６】
（第２の実施形態）
次に、本発明の第２の実施形態に係るＡＥＳ復号装置について図１を参照しながら説明する。すなわち、本実施形態は、第１の実施形態の変形例であり、ミックスカラム逆変換の演算式を式（６）に代えて、次の式（７）の演算式で実行するように構成されている。
【００９７】
【数１２】
2008209499.tif 000010
【００９８】
ここで、式（７）の第１行列Ｐｂ’は、式（６）の第１行列Ｐｂの第１行(1415)と第２行(5141)とを入れ替えるとともに、式（６）の第１行列Ｐｂの第３行(1514)と第４行(4151)とを入れ替えた構成となっている。
【００９９】
また、式（７）の第２行列Ｐａ’は、式（６）の第２行列Ｐａの第１列(2300)と第２列(0230)とを入れ替えると共に、式（６）の第２行列Ｐａの第３列(0023)と第４列(3002)とを入れ替えた構成となっている。
【０１００】
以上のような構成によれば、第１行列Ｐｂ’内の係数ｐbijの順序と、第２行列Ｐａ’内の係数ｐaijの順序とがそれぞれ第１実施形態とは異なることを除き（図６中のＳＴ２７−４’及びＳＴ２８−１’参照）、ＡＥＳ復号装置１０は、図２及び図６に示すように、前述同様に、ＡＥＳ暗号方式による復号処理を実行することができる。
【０１０１】
ここで、式（７）の計算の手続きは図７に示す通りとなる。なお、ガロア体上での演算であるため、前述同様に、図７中の加算＋は、ＸＯＲ演算となる。
【０１０２】
この場合、図５と同様に、１単位の換字処理の必要メモリ量（換字処理の参照表（Ｓ−ボックス）のメモリ量）、１単位の置換処理の必要メモリ量（置換処理の参照表（ｘ倍以上の演算の事前計算結果）のメモリ量）、４回の換字処理の参照表参照（“S( )”の回数）、８回の置換処理のｘ倍以上の演算に対する参照表参照（“xtime( )”の回数）、１６回の換字処理の加算（“＋”の回数）、といったメモリ量、参照表の参照回数及び加算回数が必要となる。
【０１０３】
上述したように本実施形態によれば、第１の実施形態と同様に動作し、同様の効果を得ることができる。具体的には本実施形態は、第１の実施形態と同じ計算処理の手間で、ＡＥＳ暗号の復号処理が実現できる。これは、式（７）と式（６）は異なる式に見えるものの、式（７）が、式（６）に行列の基本変形と呼ばれる行あるいは列の入れ替えを行うことにより求まるためである。
【０１０４】
なお、行列の基本変形によれば、本実施形態の式（７）に限らず、適宜、第１行列Ｐｂに代えて、第１行列Ｐｂに行入れ替えまたは列入れ替えの一方もしくは両方を施して得られる第１行列Ｐｂ’と、第２行列Ｐａに代えて、第１行列Ｐｂの行入れ替えに対応した列入れ替えと、第１行列Ｐｂの列入れ替えに対応した行入れ替えとを第２行列Ｐａに施して得られる第２行列Ｐａ’とを用いて乗算を実行することができる。
【０１０５】
換言すると、第１行列Ｐｂに代えて、第１行列Ｐｂにおける「行ｉ，ｉ’同士」または「列ｊ，ｊ’同士」の一方もしくは両方を入れ替えた第１行列Ｐｂ’と、第２行列Ｐａに代えて、第１行列Ｐｂの入れ替えに対応して第２行列Ｐａにおける「列ｉ，ｉ’同士」または「行ｊ，ｊ’同士」の一方もしくは両方を入れ替えた第２行列Ｐａ’とを用いて乗算を実行することができる。
【０１０６】
なお、２つの行列の積に、行または列の入れ替えを行う行列の基本変形を適用する場合、以下の操作となる。行列の基本変形では、第１行列Ｐｂの行ｉと行ｉ’を入れ替えると、この行入れ替えに対応して、第２行列Ｐａの列ｉと列ｉ’を入れ替える操作となる。すなわち、一方の行列でｉとｉ’の行入れ替えを行えば、他方の行列ではｉとｉ’の列入れ替えを行うことになる。例えば、第１行列Ｐｂの１行目と４行目を入れ替えると、この行入れ替えに対応して、第２行列Ｐａの１列目と４列目を入れ替えることになる。
【０１０７】
逆に、第１行列Ｐｂの列ｊと列ｊ’を入れ替えると、この列入れ替えに対応して、第２行列Ｐａの行ｊと行ｊ’を入れ替える操作となる。すなわち、一方の行列でｊとｊ’の列入れ替えを行えば、他方の行列ではｊとｊ’の行入れ替えを行うことになる。例えば、第１行列Ｐｂの１列目と４列目を入れ替えると、第２行列Ｐａの１行目と４行目を入れ替えることになる。  
また、行列の基本変形では、行入れ替えや列入れ替えを、複数回、行ってもよい。
【０１０８】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１０９】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１１０】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１１１】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１１２】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１１３】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１１４】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１１５】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１１６】
【図１】本発明の第１の実施形態におけるＡＥＳ復号装置が適用された計算機の構成を示す模式図である。
【図２】同実施形態におけるＡＥＳ暗号の復号処理を説明するためのフローチャートである。
【図３】同実施形態におけるミックスカラム逆変換の処理を説明するためのフローチャートである。
【図４】同実施形態におけるミックスカラム逆変換の処理を詳細に説明するためのフローチャートである。
【図５】同実施形態におけるミックスカラム逆変換の処理に必要なメモリ量及び演算回数を表形式で示す図である。
【図６】第２の実施形態におけるミックスカラム逆変換の処理を説明するためのフローチャートである。
【図７】同実施形態におけるミックスカラム逆変換の処理を詳細に説明するためのフローチャートである。
【図８】一般的な暗号化時のミックスカラム変換の処理を詳細に説明するためのフローチャートである。
【図９】一般的な暗号化時のミックスカラム変換の処理に必要なメモリ量及び演算回数を表形式で示す図である。
【図１０】従来のミックスカラム逆変換の処理を詳細に説明するためのフローチャートである。
【図１１】従来のミックスカラム逆変換の処理に必要なメモリ量及び演算回数を表形式で示す図である。
【符号の説明】
【０１１７】
１…ＲＯＭ、２…ＲＡＭ、２ａ…ラウンド鍵配列、２ｂ…内部状態配列、３…不揮発性メモリ、４…ＣＰＵ、５…入出力部、６…バス、１０…ＡＥＳ復号装置。
【図１】
2008209499.tif 000015
【図２】
2008209499.tif 000016
【図３】
2008209499.tif 000017
【図４】
2008209499.tif 000018
【図５】
2008209499.tif 000019
【図６】
2008209499.tif 000020
【図７】
2008209499.tif 000021
【図８】
2008209499.tif 000022
【図９】
2008209499.tif 000023
【図１０】
2008209499.tif 000024
【図１１】
2008209499.tif 000025