(57)【要約】【課題】  鍵等の固定データから、拡大鍵等の拡大データを生成する際に、演算コストの大きい処理を削減して、処理を高速化することを可能にする技術を提供する。【解決手段】  シード情報に基づいて複数の拡大情報を生成する情報処理装置は、シード情報を入力する入力手段と、入力されたシード情報に基づいて複数の中間情報を演算する演算手段と、演算により得られた複数の中間情報に基づいて、該中間情報にそれぞれ対応する複数の拡大情報を導出する導出手段と、導出手段において導出された拡大情報を出力する出力手段と、を備え、導出手段は、複数の中間情報の第１の集合について、該中間情報にそれぞれ対応する第１拡大情報を、換字変換を伴う処理により導出し、複数の中間情報の第２の集合について、該中間情報にそれぞれ対応する第２拡大情報を、導出された第１拡大情報に基づいて、排他的論理和演算により導出する。【選択図】  図４
2007333815.tif 000002
【特許請求の範囲】
【請求項１】
シード情報に基づいて複数の拡大情報を生成する情報処理装置であって、
前記シード情報を入力する入力手段と、
入力された前記シード情報に基づいて複数の中間情報を演算する演算手段と、
前記演算により得られた前記複数の中間情報に基づいて、該中間情報にそれぞれ対応する複数の拡大情報を導出する導出手段と、
前記導出手段において導出された前記拡大情報を出力する出力手段と、
を備え、
前記導出手段は、
前記複数の中間情報の第１の集合について、該中間情報にそれぞれ対応する第１拡大情報を、換字変換を伴う処理により導出し、
前記複数の中間情報の第２の集合について、該中間情報にそれぞれ対応する第２拡大情報を、導出された前記第１拡大情報に基づいて、排他的論理和演算により導出する
ことを特徴とする情報処理装置。
【請求項２】
前記第１の集合に含まれる前記中間情報を一時的に記憶する記憶手段を更に備えることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記拡大情報は、拡大鍵情報、又は、疑似乱数であることを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
前記換字変換は、演算結果値が予測可能であり、可逆であることを特徴とする請求項１乃至３のいずれか１項に記載の情報処理装置。
【請求項５】
被演算値と演算結果値との対応関係を示すテーブル情報を記憶する第２記憶手段を更に備え、
前記導出手段は、前記テーブル情報の参照に基づいて前記換字変換を実行する
ことを特徴とする請求項１乃至４のいずれか１項に記載の情報処理装置。
【請求項６】
前記シード情報は固定長データであることを特徴とする請求項１乃至５のいずれか１項に記載の情報処理装置。
【請求項７】
共通鍵情報を入力し、当該共通鍵情報を拡大処理して得られた複数の拡大情報に基づき、複数のラウンドに分けて、処理対象の情報に対して暗号処理を行う情報処理装置であって、
前記共通鍵情報に基づいて、先頭ラウンド用の複数の中間情報を生成する中間情報生成手段と、
生成された前記中間情報に対して、換字処理を伴う処理を実行して、先頭ラウンド用の複数の拡大情報を生成する第１生成手段と、
前記先頭ラウンドに続く後段の注目ラウンドについて、当該注目ラウンド中の一つの拡大情報を、直前のラウンドの１つの拡大情報を逆変換して得られる中間情報に基づいて生成し、該注目ラウンド中の残りの拡大情報を、従前の拡大情報に基づき排他的論理和演算により導出する第２生成手段と、
を備えることを特徴とする情報処理装置。
【請求項８】
シード情報に基づいて複数の拡大情報を生成する情報処理装置の制御方法であって、
前記シード情報を入力する入力工程と、
入力された前記シード情報に基づいて複数の中間情報を演算する演算工程と、
前記演算により得られた前記複数の中間情報に基づいて、該中間情報にそれぞれ対応する複数の拡大情報を導出する導出工程と、
前記導出工程において導出された前記拡大情報を出力する出力工程と、
を備え、
前記導出工程においては、
前記複数の中間情報の第１の集合について、該中間情報にそれぞれ対応する第１拡大情報が、換字変換を伴う処理により導出され、
前記複数の中間情報の第２の集合について、該中間情報にそれぞれ対応する第２拡大情報が、導出された前記第１拡大情報に基づいて、排他的論理和演算により導出される
ことを特徴とする情報処理装置の制御方法。
【請求項９】
共通鍵情報を入力し、当該共通鍵情報を拡大処理して得られた複数の拡大情報に基づき、複数のラウンドに分けて、処理対象の情報に対して暗号処理を行う情報処理装置の制御方法であって、
前記共通鍵情報に基づいて、先頭ラウンド用の複数の中間情報を生成する中間情報生成工程と、
生成された前記中間情報に対して、換字処理を伴う処理を実行して、先頭ラウンド用の複数の拡大情報を生成する第１生成工程と、
前記先頭ラウンドに続く後段の注目ラウンドについて、当該注目ラウンド中の一つの拡大情報を、直前のラウンドの１つの拡大情報を逆変換して得られる中間情報に基づいて生成し、該注目ラウンド中の残りの拡大情報を、従前の拡大情報に基づき排他的論理和演算により導出する第２生成工程と、
を備えることを特徴とする情報処理装置の制御方法。
【請求項１０】
コンピュータを請求項１乃至７のいずれかに記載の情報処理装置として機能させるためのコンピュータプログラム。
【請求項１１】
請求項１０に記載のコンピュータプログラムを格納したコンピュータで読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置及びその制御方法、プログラム、記憶媒体に関する。
【背景技術】
【０００２】
従来より、データを暗号化するための様々な暗号方式が知られている。暗号方式の一つに共通鍵暗号と呼ばれる暗号方式がある。共通鍵暗号は、大きく分けてブロック暗号とストリーム暗号と呼ばれる２つの方式に分類される。ブロック暗号は、固定された長さ各入力ブロックと鍵データを、換字・転置処理により攪拌し、同じ長さの出力ブロックに写す暗号化方式である。ストリーム暗号は、平文と鍵ストリームに排他的論理和のような論理演算を施し、暗号文を得る暗号化方式である。ブロック暗号の代表的なものとしては、ＤＥＳ（Data Encryption Standard）やＡＥＳ（Advanced Encryption Standard）がある。ストリーム暗号の代表的なものとしてはＲＣ４がある。
【０００３】
図２は、共通鍵暗号による暗号化処理を行う一般的な暗号化装置の構成を示す図である。図２の暗号化装置は、暗号処理対象データ２００と鍵データ２０１を入力とし、暗号化データ２０６を出力する。暗号化装置は、暗号処理部２０２と鍵処理部２０３によって構成されている。暗号化装置は、第１ラウンド２０４から第ｎラウンド２０５まで順番に、ｎ段階の処理を行う。鍵処理部２０３は、入力された暗号鍵をもとに、ｎ段階のラウンド処理のそれぞれで用いられる拡大鍵１から拡大鍵ｎの生成を順次行う。
【０００４】
上記の拡大鍵の生成の代表的なものの１つに、非特許文献１の５．２Key Expansionがある。以下は、非特許文献１から、ＡＥＳに準拠するKeyExpansionの処理内容を抜粋したものである。
［KeyExpansion］ ・・・（＊１）
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)
begin
word temp
i＝0
while (i＜Nk)
w[i]＝word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])
i＝i+1
end while
i＝Nk
while (i＜Nb * (Nr+1))
temp＝w[i-1]
if (i mod Nk＝0)
temp＝SubWord(RotWord(temp)) xor Rcon[i/Nk] ・・・（＊２）
else if (Nk＞6 and i mod Nk＝4)
temp＝SubWord(temp)
end if
w[i]＝w[i-Nk] xor temp
i＝i + 1
end while
end
以下、上記のKeyExpansionで用いられている語句の説明を行う。上記のwordは４バイト単位を表す。Keyは暗号鍵（鍵の長さは１２８，１９２，２５６ビットのいずれか）を表す。Ｗは拡大鍵を表す。また、Nkは暗号鍵の長さをword単位で示したものであり、４，６，８のいずれかの値である。Nbはブロックサイズをword単位で示したものであり、ここでの値は４である。Nrはラウンド数を示したものであり、１０，１２，１４のいずれかの値である。SubWordsは１バイト毎の換字変換である。例えば入力として００（１６）（（１６）は１６進数表記を示す。）が与えられた場合、６３（１６）が出力値となる。SubWordsの原理は、ガロア体ＧＦ（２8）上における既約多項式Ｘ8＋Ｘ4＋Ｘ3＋Ｘ＋１での逆元演算である。RotWordsは、バイト単位の転置変換であり、例えば、入力ワードとして[a0，a1，a2，a3]が与えられた場合、出力ワードは[a1，a2，a3，a0]となる。Rconは換字変換である。
【０００５】
Rconの原理は、ガロア体ＧＦ（２8）上のべき乗演算であり、Rcon[ｉ]＝[Ｘi-1，｛００｝，｛００｝，｛００｝]によって表される。｛ ｝内は１６進表記で表されており、Ｘ＝｛０２｝である。（＊１）、（＊２）については、後の実施形態において説明する。上記のKeyExpansionに示されている通り、While文以下が拡大鍵生成処理となっており、換字処理、転置処理、排他的論理和によって構成されている。
【０００６】
上記のＡＥＳは暗号化と復号化で、暗号化・復号処理部の処理工程が異なっている。説明は割愛するが、詳しくは上記の非特許文献１の５．１Cipherおよび５．３Inverse Cipherを参照いただきたい。ただし、上記の非特許文献１には、上記の暗号化・復号処理部の処理工程を同じにするオプションも記載されている。上記のオプションを適用する場合は、上記のKeyExpansionに追加処理を適用しなければならない。追加処理は上記の非特許文献１の５．３．５Equivalent Inverse Cipherに記載されている。以下は、上記の非特許文献１より、上記の追加処理について抜粋したものである。
For the Equivalent Inverse Cipher, the following pseudo code is added at
the end of the Key Expansion routine (Sec. 5.2): ・・・（＊３）
for i＝0 step 1 to (Nr+1)*Nb-1
dw[i]＝w[i]
end forfor round＝1 step 1 to Nr-1
InvMixColumns(dw[round*Nb, (round+1)*Nb-1]) // note change of type
end for
ここで、上記の追加処理で用いられている語句の説明を行う。ｄｗは復号用の拡大鍵である。また、InvMixColumnsは列単位の換字変換および排他的論理和によって構成される。InvMixColumnsの換字変換の本質はガロア体上の乗算処理である。上記の乗算処理は、ガロア体ＧＦ（２8）上における既約多項式Ｘ8＋Ｘ4＋Ｘ3＋Ｘ＋１での乗算処理である。この乗算処理は、入力に対応する出力値が予測可能であることから、換字処理が用いられるのが一般的である。
【非特許文献１】ＦＩＰＳ１９７  Advanced Encryption Standard（ＡＥＳ）（ＮＩＳＴ／２００１）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
前述のように、拡大鍵生成は、換字処理や、排他的論理和やシフト処理のような論理演算を含む、複数の処理を伴うことが一般的である。しかし、換字処理や論理演算は、一般的に演算コストが大きい。このため、上記の処理をそのまま情報処理装置に実装すると、処理に時間がかかっていた。この問題は、鍵を頻繁に更新するような環境では特に顕著になる。
【０００８】
本発明は上記問題に鑑みなされたものであり、鍵等の固定データから、拡大鍵等の拡大データを生成する際に、演算コストの大きい処理を削減して、処理を高速化することを可能にする技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明による情報処理装置は以下の構成を備える。即ち、
シード情報に基づいて複数の拡大情報を生成する情報処理装置であって、
前記シード情報を入力する入力手段と、
入力された前記シード情報に基づいて複数の中間情報を演算する演算手段と、
前記演算により得られた前記複数の中間情報に基づいて、該中間情報にそれぞれ対応する複数の拡大情報を導出する導出手段と、
前記導出手段において導出された前記拡大情報を出力する出力手段と、
を備え、
前記導出手段は、
前記複数の中間情報の第１の集合について、該中間情報にそれぞれ対応する第１拡大情報を、換字変換を伴う処理により導出し、
前記複数の中間情報の第２の集合について、該中間情報にそれぞれ対応する第２拡大情報を、導出された前記第１拡大情報に基づいて、排他的論理和演算により導出する。
【００１０】
また、本発明による情報処理装置は以下の構成を備える。即ち、
共通鍵情報を入力し、当該共通鍵情報を拡大処理して得られた複数の拡大情報に基づき、複数のラウンドに分けて、処理対象の情報に対して暗号処理を行う情報処理装置であって、
前記共通鍵情報に基づいて、先頭ラウンド用の複数の中間情報を生成する中間情報生成手段と、
生成された前記中間情報に対して、換字処理を伴う処理を実行して、先頭ラウンド用の複数の拡大情報を生成する第１生成手段と、
前記先頭ラウンドに続く後段の注目ラウンドについて、当該注目ラウンド中の一つの拡大情報を、直前のラウンドの１つの拡大情報を逆変換して得られる中間情報に基づいて生成し、該注目ラウンド中の残りの拡大情報を、従前の拡大情報に基づき排他的論理和演算により導出する第２生成手段と、
を備える。
【００１１】
また、本発明による情報処理装置の制御方法は以下の構成を備える。即ち、
シード情報に基づいて複数の拡大情報を生成する情報処理装置の制御方法であって、
前記シード情報を入力する入力工程と、
入力された前記シード情報に基づいて複数の中間情報を演算する演算工程と、
前記演算により得られた前記複数の中間情報に基づいて、該中間情報にそれぞれ対応する複数の拡大情報を導出する導出工程と、
前記導出工程において導出された前記拡大情報を出力する出力工程と、
を備え、
前記導出工程においては、
前記複数の中間情報の第１の集合について、該中間情報にそれぞれ対応する第１拡大情報が、換字変換を伴う処理により導出され、
前記複数の中間情報の第２の集合について、該中間情報にそれぞれ対応する第２拡大情報が、導出された前記第１拡大情報に基づいて、排他的論理和演算により導出される。  また、本発明による情報処理装置の制御方法は以下の構成を備える。即ち、
共通鍵情報を入力し、当該共通鍵情報を拡大処理して得られた複数の拡大情報に基づき、複数のラウンドに分けて、処理対象の情報に対して暗号処理を行う情報処理装置の制御方法であって、
前記共通鍵情報に基づいて、先頭ラウンド用の複数の中間情報を生成する中間情報生成工程と、
生成された前記中間情報に対して、換字処理を伴う処理を実行して、先頭ラウンド用の複数の拡大情報を生成する第１生成工程と、
前記先頭ラウンドに続く後段の注目ラウンドについて、当該注目ラウンド中の一つの拡大情報を、直前のラウンドの１つの拡大情報を逆変換して得られる中間情報に基づいて生成し、該注目ラウンド中の残りの拡大情報を、従前の拡大情報に基づき排他的論理和演算により導出する第２生成工程と、
を備える。
【発明の効果】
【００１２】
本発明によれば、鍵等の固定データから、拡大鍵等の拡大データを生成する際に、演算コストの大きい処理を削減して、処理を高速化することを可能にする技術を提供することができる。
【発明を実施するための最良の形態】
【００１３】
以下、添付図面を参照して本発明に係る実施の形態を詳細に説明する。ただし、この実施の形態に記載されている構成要素はあくまでも例示であり、本発明の範囲をそれらのみに限定する趣旨のものではない。
【００１４】
＜＜第１実施形態＞＞
図１は本発明における各実施形態を実現する情報処理装置の電気的構成を説明するための図である。なお、本発明の実現にあたって、図１に示される全ての機能を使用することは必須ではない。
【００１５】
（情報処理装置の構成）
情報処理装置１００は、図１に示すように、以下のハードウェアがバス１１６を介して互いに通信可能に接続されて構成されている。
・公衆回線等のモデム１１８。
・表示部としてのモニタ１０２
・ＣＰＵ１０３。
・ＲＯＭ１０４。
・ＲＡＭ１０５。
・ＨＤ（ハードディスク）１０６。
・ネットワークのネットワーク接続部１０７。
・ＣＤ１０８。
・ＦＤ（フレキシブルディスク）１０９。
・ＤＶＤ（デジタル・ビデオ・ディスク、またはDigital Versatile Disk）１１０。
・プリンタ１１５のインターフェース（Ｉ／Ｆ）１１７。
・操作部としてのマウス１１２やキーボード１１３
・操作部のインターフェース（Ｉ／Ｆ）１１１。
【００１６】
マウス１１２及びキーボード１１３は、情報処理装置１００に対する各種指示等をユーザが入力するための操作部である。この操作部を介して入力された情報（操作情報）は、インターフェース１１１を介して、情報処理装置１００内に取り込まれる。
【００１７】
情報処理装置１００での各種情報（文字情報や画像情報等）は、プリンタ１１５により印刷出力できるようになされている。モニタ１０２は、ユーザへの各種指示情報や、文字情報或いは画像情報等の各種情報の表示を行う。
【００１８】
ＣＰＵ１０３は、情報処理装置１００全体の動作制御を司るものであり、本実施形態に係る構成においては制御手段として機能している。すなわち、ＣＰＵ１０３は、ＨＤ（ハードディスク）１０６等から処理プログラム（ソフトウェアプログラム）を読み出して実行することで、情報処理装置１００全体を制御する。特に、本実施形態に係る構成では、ＣＰＵ１０３は、ＨＤ１０６等から、暗号化処理機能および復号処理機能を実現する処理プログラムを読み出して実行することで、後述する情報変換処理を実施する。なお、例えば、本実施形態に係るプログラムをＲＯＭ１０４に記録しておき、これをメモリマップの一部をなすように構成し、直接ＣＰＵ１０３で実行することも可能である。
【００１９】
ＲＯＭ１０４は、暗号化処理機能および復号処理機能のための処理プログラムや、プログラム内で用いられる各種データ等を記憶する。ＲＡＭ１０５は、ＣＰＵ１０３での各種処理のために、一時的に処理プログラムや処理対象の情報を格納するための作業用エリア等として使用される。
【００２０】
ＨＤ１０６は、大容量記憶装置の一例としての構成要素であり、各種データ、あるいは各種処理の実行時にＲＡＭ１０５等へ転送される情報変換処理等のための処理プログラム等を保存する。ＣＤ（ＣＤドライブ）１０８は、外部記憶媒体の一例としてのＣＤ（ＣＤ−Ｒ）に記憶されたデータを読み込み、また、当該ＣＤへデータを書き出す機能を有する。ＦＤ（フレキシブルディスクドライブ）１０９は、ＣＤ１０８と同様に、外部記憶媒体の一例としてのＦＤ１０９に記憶されたデータを読み出す。また、種々のデータをＦＤ１０９へ書き込む機能を有している。ＤＶＤ（デジタル・ビデオ・ディスク）１１０は、ＣＤ１０８やＦＤ１０９と同様に、外部記憶媒体の一例としてのＤＶＤ１１０に記憶されたデータを読み出し、また、ＤＶＤ１１０へデータを書き込む機能を有している。
【００２１】
なお、ＣＤ１０８、ＦＤ１０９、ＤＶＤ１１０等の外部記憶媒体に対して、例えば、編集用のプログラム或いはプリンタドライバが記憶されている場合には、これらのプログラムをＨＤ１０６へインストールしておくように構成してもよい。この場合、プログラムが必要な場合になったときに、当該プログラムをＲＡＭ１０５へ転送するように構成することができる。
【００２２】
インターフェース（Ｉ／Ｆ）１１１は、マウス１１２、或いは、キーボード１１３によるユーザからの入力を受け付けるためのものである。モデム１１８は、通信モデムであり、インターフェース（Ｉ／Ｆ）１１９を介して、例えば、公衆回線等を通じて外部のネットワークに接続される。ネットワーク接続部１０７は、インターフェース（Ｉ／Ｆ）１１４を介して、外部のネットワークに接続される。
【００２３】
なお、本発明は、複数の機器（例えば、ホストコンピュータ、インターフェース機器、リーダ、プリンタ等）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置等）に適用してもよい。即ち、本実施形態では、説明の便宜のため、本実施形態に係る情報処理装置を１つの装置で実現した構成について述べるが、複数の装置にリソースを分散した構成によって実現してもよい。例えば、記憶や演算のリソースを複数の装置に分散した形に構成してもよい。或いは、情報処理装置上で仮想的に実現される構成要素毎にリソースを分散し、並列処理を行うようにしてもよい。
【００２４】
尚、以上の各装置と同等の機能を実現するソフトウェアにより、ハードウェア装置の代替として構成することもできる。
【００２５】
（ブロック暗号処理の概要）
以下、本実施形態に係る構成による処理ついて図面を参照して説明する。図２は、ブロック暗号処理を行う情報処理装置の機能構成を示すブロック図である。
【００２６】
図２において、暗号処理対象データ２００と鍵データ２０１が、図１に示す情報処理装置１００に入力される。暗号処理対象データ２００は暗号処理部２０２に、鍵データ２０１は鍵処理部２０３に、それぞれ入力される。鍵処理部２０３は、入力された鍵情報２０１を元に拡大鍵を生成し、暗号処理部２０２に入力する。
【００２７】
暗号処理部２０２は、鍵処理部２０３からの拡大鍵の入力と同時に入力された、暗号処理対象データ２００に対して、第１ラウンド２０４から第ｎラウンド２０５まで順次所定の処理を行うことにより暗号化処理を実行する。そして、第ｎラウンド２０５の出力を、暗号化データ２０６として情報処理装置１００から出力する。
【００２８】
なお、暗号化処理に対する復号処理は、暗号化処理に排他的論理和（ＸＯＲ）を用いて、上記の処理を逆側から順次行うことによって実現される。暗号化処理と復号処理とを包含するものとして、暗号処理と呼ぶ。
【００２９】
なお、上記の共通鍵暗号に基づく暗号処理は、例えば、ユーザの指示入力により暗号処理対象のデータと、鍵データが指定されたことに応じて実行するように構成することができる。或いは、共通鍵暗号に基づく暗号処理を実行する処理手続きにおける、予め定められたイベント発生に応じて実行するように構成することができる。ただし、ここに例示したものに限られないことは明らかである。
【００３０】
（従来の構成における処理）
図３は、従来の構成におけるＡＥＳの１２８ビット鍵３０１から復号用の拡大鍵を生成する処理を示すブロック図である。上記の１２８ビット鍵３０１から、上記のKeyExpansion処理３０２により、４４個の拡大鍵Ｗtが生成される。KeyExpansion処理３０２は上記（＊１）にて示されている処理である。また、Ｗtの一部から、InvMixColumns処理３０３を３６回実行することにより、３６個のｄＷtが生成される。InvMixColumns処理３０３は上記（＊３）にて示されている処理である。上記のように、ＷtからｄＷtを求めるInvMixColumns処理３０３は換字処理を伴うため、演算コストが大きい。
【００３１】
（拡大鍵生成の概要）
図４は、本実施形態におけるＡＥＳの１２８ビット鍵３０１（シード情報）から復号用の拡大鍵を生成する処理を示すブロック図である。上記の１２８ビット鍵４０１から、上記KeyExpansion処理４０２により、４４個の拡大鍵Ｗtが生成される。また、Ｗtの一部から、InvMixColumns処理４０３により、４０個のｄＷtが生成される。
【００３２】
ただし、本実施形態では、一部のｄｗtをInvMixColumns処理４０３を用いて算出した後は、その算出結果を元に、演算コストの低い排他的論理和により、残りのｄｗtを算出する。このため、本実施形態に係る構成によれば、上記の従来の構成における処理よりも、低い演算コストで、処理を実行することができる。
【００３３】
（拡大鍵生成処理）
次に、本実施形態に係る構成による拡大鍵生成処理について、図５を参照して説明する。図５は、本実施形態における拡大鍵生成処理の手順を示すフローチャートである。
【００３４】
まず、ステップＳ５０１において、上記の１２８ビット鍵を入力する。
【００３５】
次に、ステップＳ５０２において、上記KeyExpansion処理を行い、４４個のＷtを生成する。
【００３６】
次に、ステップＳ５０３において、４４個のＷtからＷ0〜Ｗ3を選択する。
【００３７】
次に、ステップＳ５０４において、ステップＳ５０３で選択されたＷ0〜Ｗ3に対し、上記のInvMixColumns変換を行う。この処理の結果、ｄＷ0〜ｄＷ3が生成される。
【００３８】
一方、ステップＳ５０５において、ステップＳ５０２のKeyExpansion処理で使用されるtempデータを確保する。ただし、このtempデータは、上記（＊１） KeyExpansionの処理内容で使用されているtempのことを指す。なお確保されるtempデータはi mod Nk＝０を満たすtempデータを指す。本実施形態に係る構成での、パラメータiは４以上３９以下の整数、パラメータNkは４である。
【００３９】
ステップＳ５０５の処理の後、ステップＳ５０６において、ステップＳ５０５で確保されたtempデータに対し、InvMixColumns変換を行う。ステップＳ５０６の結果、生成されたデータを、順にｄＷ'i-1として定義する。本実施形態に係る構成では、dＷ'3，dＷ'7などが定義される。
【００４０】
ステップＳ５０４及びステップＳ５０６の処理が終了すると、ステップＳ５０７へ進む。ステップＳ５０７では、ステップＳ５０４で求めたｄＷtを除く、残りのｄＷtの演算処理を行う。この演算処理は式１にて示される。
［式１］
2007333815.tif 000003
（ｔ：０〜３９）
ここで、記号
2007333815.tif 000004
は、排他的論理和を示す。なお、ｔ mod Nk＝０を満たす場合に限り、式中ｄＷt-1をｄＷ't-1に置き換える。本実施形態に係る構成にて、ｄＷ4を算出する際を例に挙げると、
2007333815.tif 000005
となる。このような排他的論理和演算により、InvMixColumns処理により求められたもの以外の全てのｄＷが算出される。そして、ステップＳ５０８へ進む。
【００４１】
ステップＳ５０８では、ステップＳ５０２の出力結果Ｗ0〜Ｗ3，Ｗ40〜Ｗ43と、ステップＳ５０７の結果ｄＷ4〜ｄＷ39を、復号用拡大鍵として出力する。以上で、復号用拡大鍵生成の処理は終了となる。
【００４２】
上記のように、本実施形態に係る構成においては、ｄｗtを算出する際に、演算コストの高いInvMixColumns処理４０３を逐一実行しない。代わりに、可能な限り演算コストの低い排他的論理和演算によりｄｗtを算出する。このため、本実施形態に係る構成によれば、１２８ビット鍵４０１から、拡大鍵を生成する際に、演算コストの大きいInvMixColumns処理４０３を削減して、処理を高速化することが可能である。
【００４３】
＜＜第２実施形態＞＞
第１実施形態に係る構成では、復号用拡大鍵の生成を行う際にtempデータを用いていた。しかし、ｔ mod Nk＝０を満たすｄＷtに関しては、KeyExpansionにて作成されたＷtからｄＷtを直接生成することができる。そこで、本実施形態では、tempデータを使用しない構成について説明する。なお、情報処理装置の構成、ブロック暗号処理の概要等、第１実施形態と同様の箇所については説明を省略し、相違する内容について説明する。
【００４４】
（拡大鍵生成処理）
本実施形態に係る構成による拡大鍵生成処理について、図６を参照して説明する。図６は、本実施形態における拡大鍵生成処理の手順を示すフローチャートである。
【００４５】
まず、ステップＳ６０１では、上記１２８ビット鍵が入力される。
【００４６】
次に、ステップＳ６０２において、上記KeyExpansion処理を行い、４４個のＷtを生成する。
【００４７】
次に、ステップＳ６０３において、４４個のＷtからＷ0〜Ｗ3を選択する。
【００４８】
次に、ステップＳ６０４において、ステップＳ６０３で選択されたＷ0〜Ｗ3に対し、上記のInvMixColumns変換を行う。この処理の結果、ｄＷ0〜ｄＷ3が生成される。
【００４９】
一方、ステップＳ６０５において、４４個のＷtからｔ mod Nk＝０を満たすＷtを選択する。ただし、本実施形態に係る構成では、パラメータｔは４以上３９以下の整数、パラメータNkは４である。
【００５０】
ステップＳ６０５の処理の後、ステップＳ６０６において、ステップＳ６０５で選択されたＷtに対し、InvMixColumns変換を行う。ステップＳ６０６の処理の結果、生成されたデータを、順にｄＷtとして定義する。本実施形態に係る構成では、ｄＷ4，ｄＷ8などが定義される。
【００５１】
ステップＳ６０４及びステップＳ６０６の処理が終了すると、ステップＳ６０７へ進む。ステップＳ６０７では、ステップＳ６０４、Ｓ６０６で求めたｄＷtを除く、残りのｄＷtの演算処理を行う。演算処理は式２にて示される。
［式２］
2007333815.tif 000006
（ｔ：０〜３９）
ここで、記号
2007333815.tif 000007
は、排他的論理和を示す。本実施形態に係る構成にて、ｄＷ4を算出する際を例に挙げると、
2007333815.tif 000008
となる。このような排他的論理和演算により、InvMixColumns処理により求められたもの以外の全てのｄＷが算出される。そして、ステップＳ６０８へ進む。
【００５２】
ステップＳ６０８では、ステップＳ６０２の出力結果Ｗ0〜Ｗ3，Ｗ40〜Ｗ43と、ステップＳ６０６，６０７の結果ｄＷ4〜ｄＷ39を、復号用拡大鍵として出力する。以上で、復号用拡大鍵生成の処理は終了となる。
【００５３】
上記のように、本実施形態においては、第１実施形態と同様に、ｄｗtを算出する際に、可能な限り演算コストの低い排他的論理和演算によりｄｗtを算出するため、演算コストを削減することができる。このため、本実施形態に係る構成によれば、１２８ビット鍵４０１から、拡大鍵を生成する際に、演算コストの大きいInvMixColumns処理４０３を削減して、処理を高速化することが可能である。
【００５４】
＜＜第３実施形態＞＞
第１及び第２実施形態に係る構成では、先にKeyExpansionにて拡大鍵を生成した後に復号用拡大鍵の生成を行っていた。第１実施形態に係る構成の内部処理を変更することによって、KeyExpansionの処理を行うことなしに、復号用拡大鍵を生成することも可能である。
【００５５】
（拡大鍵生成の概要）
まず、本実施形態における処理の概要について、図７を参照して説明する。図７は、本実施形態に係る構成におけるＡＥＳの１２８ビット鍵７０１から復号用の拡大鍵を生成する処理を示すブロック図である。
【００５６】
まず、上記の１２８ビット鍵７０１から、KeySet処理７０２により、４個の拡大鍵Ｗ0〜Ｗ3を生成する。このKeySet処理７０２は、従来のKeyExpansion処理の１２８ビット鍵からＷ0〜Ｗ3を生成する処理と同様である。また、Ｗ0〜Ｗ3より、InvMixColumns処理７０３により、ｄＷt（ｔ＝０〜４）が生成される。生成されたｄＷtを、後の処理にも流用することにより、最終的に全てのｄＷtが生成される。また、ｄＷtの一部から、MixColumns処理７０４により、Ｗtが生成される。ただし、MixColumns処理７０４は、InvMixColumns処理７０３の逆変換処理である。
【００５７】
（拡大鍵生成処理）
次に、本実施形態に係る構成による拡大鍵生成処理について、図８を参照して説明する。図８は、本実施形態における拡大鍵生成処理の手順を示すフローチャートである。
【００５８】
まず、ステップＳ８０１では、上記の１２８ビット鍵を入力する。次に、ステップＳ８０２では、上記のKeySet処理を行い、４個のＷ0〜Ｗ3を生成する。次に、ステップＳ８０３では、ステップＳ８０２で選択されたＷ0〜Ｗ3に対し、上記のInvMixColumns変換を行う。この変換の結果、ｄＷ0〜ｄＷ3が生成される。
【００５９】
一方、ステップＳ８０４において、ステップＳ８０２のKeySet処理で生成されたＷ3を選択する。次に、ステップＳ８０５では、ステップＳ８０４で選択されたＷ3に対し、上記（＊２）KeyExpansionの処理内容に記載されたSubWord＆RotWord＆Rcon処理を行う。次に、ステップＳ８０６では、ステップＳ８０５にて生成されたデータに対し、InvMixColumns変換を行う。ステップＳ８０６の結果、生成されたデータを、ｄＷ'3として定義する。
【００６０】
上記のステップＳ８０１〜Ｓ８０６の処理を行うと、ステップＳ８０７において、ステップＳ８０３及びＳ８０６で生成されたｄＷ，ｄＷ'sを用いてＷtの演算処理を行う。演算処理は式３にて示される。
［式３］
2007333815.tif 000009
（ｔ：０〜３９）
この演算処理では、まず、ｄＷ4を算出する（つまり、ｔ＝４から処理を開始する）。ここで、ｄＷ3はｄＷ'3と置き換えられて実行される。つまり、
2007333815.tif 000010
となる。ｄＷ5以降については、次のステップＳ８０８の判定を行った後に実行する。なお、ステップＳ８０７の処理は、実行するたびにｔの値を増加して行う。
【００６１】
ステップＳ８０７の処理の後、ステップＳ８０８において、ステップＳ８０７の処理ステップ毎にパラメータの判定を行う。即ち、ｄＷtの演算において、ｔが、ｔmodNk＝Nk−１、もしくは、３６≦ｔ≦３９を満たすか否かを判定する。ｔが、ｔmodNk＝Nk−１、又は、３６≦ｔ≦３９を満たす場合（ステップＳ８０８でＹＥＳ）はステップＳ８０９へ進み、満たさない場合（ステップＳ８０８でＮＯ）はステップＳ８０７へ戻って演算処理を継続する。なお、本実施形態に係る構成では、Nk＝４である。
【００６２】
ステップＳ８０９では、ステップＳ８０８が真（ＹＥＳ）である場合、上記MixColumnsの変換を行い、Ｗtを導出する。そして、ステップＳ８１０へと進む。
【００６３】
ステップＳ８１０では、ｔが、ｔ modNk＝Nk−１であり、かつ、ｔ≠３９であるか否かを判定する。ｔ modNk＝Nk−１、及び、ｔ≠３９の両方を満たす場合（ステップＳ８１０でＹＥＳ）、即ち、判定が真の時は、ステップＳ８１１へと進む。偽の場合（ステップＳ８１０でＮＯ）、ステップＳ８０７に戻り演算処理を継続する。
【００６４】
ステップＳ８１１では、ステップＳ８０９で生成されたＷtに対し、上記（＊２）KeyExpansionの処理内容に記載されたSubWord＆RotWord＆Rcon処理を行う。
【００６５】
次に、ステップＳ８１２において、ステップＳ８１１で生成されたデータに対し、InvMixColumns変換を行う。ステップＳ８１２の結果、生成されたデータを、ｄＷ'tとして定義する。そして、ステップＳ８０７に戻り、演算処理を継続する。この際、式３のｄＷt-1はｄＷ't-1に置き換えられる。このようにしてｄＷを算出する。
【００６６】
ステップＳ８０９において、全てのＷt、即ち、Ｗ0〜Ｗ39が導出されると、ステップＳ８１３へ進む。ステップＳ８１３では、ステップＳ８０９にて作成されたＷtからＷ36〜Ｗ39を選択する。
【００６７】
次に、ステップＳ８１４において、ステップＳ８１０で選択されたＷ36〜Ｗ39を用いて、Ｗ40〜Ｗ43生成処理を行う。この生成処理は、従来のKeyExpansion処理と同様である。
【００６８】
次に、ステップＳ８１５では、ステップＳ８０２の出力結果Ｗ0〜Ｗ3、ステップＳ８１４の出力結果Ｗ40〜Ｗ43、及び、ステップＳ８０７の出力結果ｄＷ4〜ｄＷ39を、復号用拡大鍵として出力する。以上で、復号用拡大鍵生成の処理は終了となる。
【００６９】
KeyExpansion処理においても換字変換が行われるが、以上のように、本実施形態に係る構成においては、全てのＷtを求めるために、逐一KeyExpansionの処理を実行しない。このため、本実施形態に係る構成によれば、更に、低い演算コストで復号用拡大鍵を生成することができる。
【００７０】
＜＜第４実施形態＞＞
第１〜第３実施形態では、入力する固定データが鍵データである場合を想定したが、入力する固定データはこれに限られない。例えば、入力データが固定長の擬似乱数のシード等の場合にも適用可能である。第１〜第３実施形態の手法を適用可能な、擬似乱数の生成に用いる擬似乱数生成器としては、例えば、ＰＡＮＡＭＡ型擬似乱数生成器のようなブロック暗号と同じ原理に基づいた擬似乱数生成器が挙げられる。なお、ＰＡＮＡＭＡ型擬似乱数生成器は、Fast Hashing and Stream Encryption with PANAMA（ＦＳＥ（Fast Software Encryption）／１９９８）に準拠している。
【００７１】
このような擬似乱数生成器は、式４および式５のような構成を、処理の全体もしくは処理の一部に含まなければならない。
［式４］
OutData＝Ｓ[InData] ・・・
［式５］
2007333815.tif 000011
式４および式５のInData，InDataX，InDataYは擬似乱数のシードもしくは擬似乱数の処理の過程で生成されるデータを指す。Ｓは換字変換を伴う処理を示しており、OutDataは擬似乱数の処理の過程で生成されるデータを指し、少なくとも上記の換字変換で生成されるデータを含む。式４のＳ[InData]が式５のように構成できるのであれば、第１〜第３実施形態の手法を適用可能であり、演算コストを削減することができる。
【００７２】
＜＜その他の実施形態＞＞
第１乃至第４の実施形態は、複数の機器（例えばホストコンピュータ、インターフェース機器、リーダ、プリンタ等）から構成されるシステムの一部として適用しても、ひとつの機器（たとえば複写機、ファクシミリ装置）からなるものの一部に適用してもよい。
【００７３】
また、本発明の実施形態例について詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様を取ることが可能である。具体的には、複数の機器から構成されるシステムに適用してもよいし、また、一つの機器からなる装置に適用してもよい。
【００７４】
尚、本発明は、前述した実施形態の機能を実現するプログラムを、システムあるいは装置に直接あるいは遠隔から供給し、そのシステムあるいは装置のコンピュータが該供給されたプログラムコードを読み出して実行することによっても達成される場合を含む。
【００７５】
従って、本発明の機能処理をコンピュータで実現するために、該コンピュータにインストールされるプログラムコード自体も本発明の技術的範囲に含まれる。つまり、本発明は、本発明の機能処理を実現するためのコンピュータプログラム自体も含む。
【００７６】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等の形態であってもよい。
【００７７】
プログラムを供給するための記録媒体としては、例えば、次のものが含まれる。即ち、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−Ｒ）等が含まれる。
【００７８】
その他、プログラムの供給形態としては、次のようなものも考えられる。即ち、クライアント装置のブラウザを用いてインターネットのホームページに接続し、該ホームページから本発明に係るコンピュータプログラム、或いは、圧縮され自動インストール機能を含むファイルをＨＤ等の記録媒体にダウンロードする形態も考えられる。また、本発明に係るプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明に含まれるものである。
【００７９】
また、次のような供給形態も考えられる。即ち、まず、本発明に係るプログラムを暗号化してＣＤ−ＲＯＭ等の記憶媒体に格納してユーザに配布する。そして、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせ、その鍵情報の使用により暗号化されたプログラムを実行してコンピュータにインストールさせて本発明に係る構成を実現する。このような供給形態も可能である。
【００８０】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される他、次のような実現形態も想定される。即ち、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行ない、その処理によっても前述した実施形態の機能が実現され得る。
【００８１】
さらに、記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムの指示に基づいても前述した実施形態の機能が実現される。即ち、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現される。
【図面の簡単な説明】
【００８２】
【図１】情報処理装置の電気的構成を説明するための図である。
【図２】共通鍵暗号による暗号化処理を行う一般的な暗号化装置の構成を示す図である。
【図３】従来の構成におけるＡＥＳの１２８ビット鍵から復号用の拡大鍵を生成する処理を示すブロック図である。
【図４】ＡＥＳの１２８ビット鍵から復号用の拡大鍵を生成する処理を示すブロック図である。
【図５】拡大鍵生成処理の手順を示すフローチャートである。
【図６】拡大鍵生成処理の手順を示すフローチャートである。
【図７】ＡＥＳの１２８ビット鍵から復号用の拡大鍵を生成する処理を示すブロック図である。
【図８】拡大鍵生成処理の手順を示すフローチャートである。
【図１】
2007333815.tif 000012
【図２】
2007333815.tif 000013
【図３】
2007333815.tif 000014
【図４】
2007333815.tif 000015
【図５】
2007333815.tif 000016
【図６】
2007333815.tif 000017
【図７】
2007333815.tif 000018
【図８】
2007333815.tif 000019