(57)【要約】【課題】キャッシュ攻撃型暗号解読法という新たな暗号解読法に対する防御機能を備えた暗号装置を提供する。【解決手段】ビット列変換に使用する換字テーブル３０５を用いて暗号処理を行う暗号プログラム３Ａがキャッシュ４を有するコンピュータに実装された暗号装置において、暗号処理に先立って換字テーブル３０５をキャッシュ４にプリロードする手段３１１を備える。１つの平文の暗号処理における換字テーブル３０５に対するアクセス時のキャッシュミスヒット回数が、任意の平文についてほぼ均一化されるため、換字テーブルの動作エントリ数が少ない平文も多い平文も、その暗号時間がほぼ同じになり、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となる。【選択図】　図１
2004120307.tif 000002
【特許請求の範囲】
【請求項１】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を備えたことを特徴とする暗号装置。
【請求項２】
前記調整手段は、暗号処理または復号処理で使用する複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表のみを調整対象とすることを特徴とする請求項１記載の暗号装置。
【請求項３】
攻撃対象とされる可能性の高い変換表には、エントリ総数に対する参照総エントリ数の比である利用率が小さな変換表を含むことを特徴とする請求項２記載の暗号装置。
【請求項４】
前記調整手段は、前記変換表をキャッシュにプリロードする手段を備えることを特徴とする請求項１、２または３記載の暗号装置。
【請求項５】
前記調整手段は、キャッシュミスヒット回数が増加する方向に調整することを特徴とする請求項１、２または３記載の暗号装置。
【請求項６】
前記調整手段は、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表のエントリのうち暗号処理または復号処理で実際に使用されなかったエントリをアクセスする不使用エントリロード手段とを備えたことを特徴とする請求項５記載の暗号装置。
【請求項７】
前記調整手段は、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表の使用エントリの最大数と暗号処理または復号処理で実際に使用されたエントリ数の差分だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備えたことを特徴とする請求項５記載の暗号装置。
【請求項８】
前記調整手段は、暗号処理または復号処理で変換表のエントリにキャッシュヒットした回数を管理する使用エントリ管理手段と、前記キャッシュヒットした回数だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備えたことを特徴とする請求項５記載の暗号装置。
【請求項９】
前記調整手段は、暗号処理または復号処理で変換表のエントリにキャッシュヒットする毎にキャッシュミスヒットを発生させる手段を備えたことを特徴とする請求項５記載の暗号装置。
【請求項１０】
前記調整手段は、１つの平文または１つの暗号文の暗号処理または復号処理で参照される総回数がｎ回である同一内容の変換表をｎ個備え、各参照毎にそれぞれ異なる変換表を参照させるものであることを特徴とする請求項５記載の暗号装置。
【請求項１１】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における暗号処理時間または復号処理時間を、任意の平文または暗号文についてほぼ均一化する調整手段を備えたことを特徴とする暗号装置。
【請求項１２】
前記調整手段は、実質的な暗号処理または復号処理に要した時間を計測する計測手段と、計測された時間が予め設定された時間より短い場合、不足している時間だけ暗号処理または復号処理に要する時間を延長する延長手段とを含むことを特徴とする請求項１１記載の暗号装置。
【請求項１３】
前記予め設定された時間として、実質的な暗号処理または復号処理に要する最大時間を用いたことを特徴とする請求項１２記載の暗号装置。
【請求項１４】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の実質的な暗号処理または復号処理に要した時間を計測する計測手段と、計測された時間が予め設定された時間より短い場合、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段とを含む調整手段を備えたことを特徴とする暗号装置。
【請求項１５】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理に要する時間を調整する調整手段を備え、該調整手段は、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段を含むことを特徴とする暗号装置。
【請求項１６】
換字処理を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、換字処理に用いる変換表のうち攻撃対象とされる可能性の高い変換表でない場合にはテーブル構造の変換表として備え、攻撃対象とされる可能性の高い変換表の場合はテーブル構造の変換表として持たずに演算処理によって換字処理を実行することを特徴とする暗号装置。
【請求項１７】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムであって、キャッシュ装備のコンピュータで実行されたときに１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を有することを特徴とする暗号プログラム。
【請求項１８】
前記調整手段は、暗号処理または復号処理で使用する複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表のみを調整対象とすることを特徴とする請求項１７記載の暗号プログラム。
【請求項１９】
攻撃対象とされる可能性の高い変換表には、エントリ総数に対する参照総エントリ数の比である利用率が小さな変換表を含むことを特徴とする請求項１８記載の暗号プログラム。
【請求項２０】
前記調整手段は、前記変換表をキャッシュにプリロードする手段を備えることを特徴とする請求項１７、１８または１９記載の暗号プログラム。
【請求項２１】
前記調整手段は、キャッシュミスヒット回数が増加する方向に調整することを特徴とする請求項１７、１８または１９記載の暗号プログラム。
【請求項２２】
前記調整手段は、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表のエントリのうち暗号処理または復号処理で実際に使用されなかったエントリをアクセスする不使用エントリロード手段とを備えたことを特徴とする請求項２１記載の暗号プログラム。
【請求項２３】
前記調整手段は、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表の使用エントリの最大数と暗号処理または復号処理で実際に使用されたエントリ数の差分だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備えたことを特徴とする請求項２１記載の暗号プログラム。
【請求項２４】
前記調整手段は、暗号処理または復号処理で変換表のエントリにキャッシュヒットした回数を管理する使用エントリ管理手段と、前記キャッシュヒットした回数だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備えたことを特徴とする請求項２１記載の暗号プログラム。
【請求項２５】
前記調整手段は、暗号処理または復号処理で変換表のエントリにキャッシュヒットする毎にキャッシュミスヒットを発生させる手段を備えたことを特徴とする請求項２１記載の暗号プログラム。
【請求項２６】
前記調整手段は、１つの平文または１つの暗号文の暗号処理または復号処理で参照される総回数がｎ回である同一内容の変換表をｎ個備え、各参照毎にそれぞれ異なる変換表を参照させるものであることを特徴とする請求項２１記載の暗号プログラム。
【請求項２７】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムであって、キャッシュ装備のコンピュータ上で実行されたときに１つの平文または１つの暗号文の暗号処理または復号処理における暗号処理時間または復号処理時間を、任意の平文または暗号文についてほぼ均一化する調整手段を有することを特徴とする暗号プログラム。
【請求項２８】
前記調整手段は、実質的な暗号処理または復号処理に要した時間を計測する計測手段と、計測された時間が予め設定された時間より短い場合、不足している時間だけ暗号処理または復号処理に要する時間を延長する延長手段とを含むことを特徴とする請求項２７記載の暗号プログラム。
【請求項２９】
前記予め設定された時間として、実質的な暗号処理または復号処理に要する最大時間を用いたことを特徴とする請求項２８記載の暗号プログラム。
【請求項３０】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムであって、１つの平文または１つの暗号文の実質的な暗号処理または復号処理に要した時間を計測する計測手段と、計測された時間が予め設定された時間より短い場合、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段とを含む調整手段を有することを特徴とする暗号プログラム。
【請求項３１】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムであって、１つの平文または１つの暗号文の暗号処理または復号処理に要する時間を調整する調整手段を備え、該調整手段は、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段を含むことを特徴とする暗号プログラム。
【請求項３２】
換字処理を用いて暗号処理または復号処理を行う暗号プログラムであって、換字処理に用いる変換表のうち攻撃対象とされる可能性の高い変換表でない場合にはテーブル構造の変換表として備え、攻撃対象とされる可能性の高い変換表である場合はテーブル構造の変換表として持たずに演算処理によって換字処理を実行することを特徴とする暗号プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデータの通信や蓄積の際にデータを秘匿するための暗号装置に関し、特に換字テーブルなどの変換表を用いてデータを暗号化する暗号装置の改良に関する。
【０００２】
【従来の技術】
一般に暗号方式は、共通鍵暗号と公開鍵暗号に大別される。共通鍵暗号では、暗号化アルゴリズムは公開するが、暗号化の鍵と復号化の鍵が同一であり、鍵の値を秘密にする。他方、公開鍵暗号は、暗号化の鍵と復号化の鍵が異なっており、暗号化アルゴリズムに加えて暗号化の鍵を公開し、復号化の鍵を秘密にする。公開鍵暗号は、鍵の配送の手間がかからず鍵管理が容易である等の利点を有するが、共通鍵暗号に比べて処理量が多くなり処理速度が遅くなるといった問題があるため、大量データの暗号化には共通鍵暗号が専ら使用されている。
【０００３】
共通鍵暗号は、更に、ブロック暗号とストリーム暗号とに分けられる。ストリーム暗号は、乱数生成器が出力する乱数列を１ビットずつデータに作用させるビット単位の処理によって暗号化する。他方、ブロック暗号は、数十ビット以上の比較的長いデータブロック毎に暗号化および復号化を行う。ブロック暗号の代表的なものに、ＤＥＳ暗号、ＦＥＡＬ暗号などがある。
【０００４】
ＤＥＳ暗号やＦＥＡＬ暗号などの暗号処理部は、データランダム化部と鍵生成部とで構成される。鍵生成部は、鍵を拡大し、データランダム化部に出力する。データランダム化部は、平文（または暗号文）と鍵を混ぜ合わせ、暗号文（または平文）を出力する。データランダム化部は、通常、入力部、データ変換部および出力部で構成される。入力部は、初期置換（ＩＰ：Ｉｎｉｔｉａｌ　Ｐｅｒｍｕｔａｔｉｏｎ）など簡単な処理を行い、出力部は逆初期置換（ＩＰ−１）などの処理を行う。データ変換部は、入力部の出力と鍵生成部で生成された鍵とを用いて、基本的な単位操作を複数回繰り返し、結果を出力部へ出力する。単位操作では、排他的論理和、換字（ｓｕｂｓｔｉｔｕｔｉｏｎ）、置換（ｃｏｏｒｄｉｎａｔｅ　ｐｅｒｍｕｔａｔｉｏｎ）などの操作が組み合わされる。
【０００５】
換字の処理を行う部分は、Ｓボックスとも呼ばれる。Ｓボックスでは、一般に換字テーブルと呼ばれる変換表が使われ、Ｓボックスの入力ビット列で表される番地に格納されているビット列を換字テーブルから読み出し、Ｓボックスの出力として出力する。一般にＳボックスは、使用する換字テーブルの種類に応じて複数種類存在し、入力ビット数に応じてＳ７ボックス、Ｓ９ボックスなどとして区別される。各Ｓｉボックスは、一般に１ブロックの暗号化（または復号）の過程で複数回実行される。
【０００６】
図１３に換字テーブルの簡単な例を示す。この例の換字テーブルは１６個のエントリを有し、各エントリに１６進数で０からＦの番地が振られており、各エントリに０からＦの値が格納されている。左上のエントリを０番地とし、右方向に１、２、３番地を割振り、２段目は左から右に４、５、６、７番地を、３段目は同じく左から右に８、９、Ａ、Ｂ番地を、４段目は同じく左から右にＣ、Ｄ、Ｅ、Ｆ番地を割振るものとすると、例えば、入力ビットが００００（１６進数で０）の場合、０番地のエントリに格納されている１６進数で８の値が読み出され、２進数で表現した１０００が出力される。このような換字テーブルを使用すると、換字テーブルを交換するだけで異なる暗号変換を実施でき、秘匿通信の柔軟性が向上する等の利点がある。
【０００７】
図１４は従来の暗号装置のブロック図である。図１４において、１はＣＰＵ（演算装置）、２はメモリ（主記憶）、３は暗号プログラム、４はキャッシュであり、ＣＰＵ１とキャッシュ４との間はデータ線、アドレス線および制御線を含むプロセッサバス５によって接続され、キャッシュ４とメモリ２との間は、同じくデータ線、アドレス線および制御線を含むメモリバス６によって接続されている。周知のようにキャッシュ４は、メモリ２よりも高速アクセス可能な小容量のメモリであり、メモリ２の内容の一部の写しを保持する。ＣＰＵ１がプロセッサバス５を通じて要求する命令やデータがキャッシュ４に存在すれば（これをキャッシュヒットと呼ぶ）、キャッシュ４はキャッシュヒットした命令やデータを直ちにＣＰＵ１に返却する。他方、ＣＰＵ１が要求する命令やデータがキャッシュ４に存在しなければ（これをキャッシュミスヒットと呼ぶ）、キャッシュ４はミスヒットした命令やデータを含む所定サイズのデータをメモリバス６を通じてメモリ２から読み出して自身に格納すると共にＣＰＵ１に該当する命令やデータを返却する。ここで、所定サイズのデータとは、例えば３２バイト、１２８バイトといったサイズである。このようなサイズでキャッシュ４に読み込んでおくことにより、命令が実行される場合には実行アドレスが近い命令が続けて実行されることが多いという原理（命令の局所性の原理）により、キャッシュヒット率を高めることができ、高速化が可能となる。
【０００８】
暗号プログラム３は、前述したＤＥＳ暗号やＦＥＡＬ暗号などの共通鍵暗号を実現するプログラムであり、通常は図示しない磁気ディスク等の補助記憶装置に格納されており、使用時に図１４に示すようにメモリ２にロードされて実行される。図１４のメモリ２のブロックの右に記載した構成図は、１つの平文を暗号化する際の暗号プログラム３の処理の内容を示している。
【０００９】
暗号プログラム３は、他のプログラムからの呼出しなどによって起動されると（ステップ３０１）、先ず、入力部３０２によって、平文の入力、初期置換などの処理を行い、その後、鍵生成部３０３による鍵生成処理、データ変換部３０４によるデータ変換処理が実行される。鍵生成部３０３では、暗号プログラム３に設定されている鍵を拡大し、データ変換部３０４で使う幾つかの鍵（拡大鍵）を生成する。拡大鍵は、共通鍵が変更されなければ変化せず、平文や暗号文に依存しない。そのため、鍵生成部３０３をあらかじめ一度実行して拡大鍵を生成記憶し、暗号化／復号化では記憶した拡大鍵を使い、鍵生成部３０３を動作させない場合もある。データ変換部３０４は、入力部３０２から出力された初期置換後の平文と鍵生成部３０３で生成された鍵を混ぜ合わせる基本操作を複数回繰り返し、結果のデータを出力する。このとき、換字を行う場合は、暗号プログラム３に予め設定されている換字テーブル３０５をアクセスして換字処理が実行される。データ変換部３０４で複数回の基本操作が繰り返されて得られたデータは、出力部３０６において逆初期置換などの処理が実行され、最終的に得られた暗号文が呼出し元のプログラム等に返却され、１つの平文の暗号化を終える（ステップ３０７）。復号処理は、暗号化の逆となり、ほぼ同様の動作となる。
【００１０】
一方、暗号アルゴリズムで使われる鍵を解読する方法が幾つか存在する。古典的な解読方法は、鍵の全数探索法と呼ばれるもので、鍵の値として取りうる全ての値を用いて既知の平文の暗号化を試み、既知の暗号文と一致するかどうかを調べるものである。しかし、この方法は鍵長が長くなると調べるべき鍵の候補数が膨大となり、現実的でなくなる。このため、調べるべき鍵の候補数を現実的な範囲に押え込む解読方法として、差分解読法や線形解読法が提案されている。更に近年においては、主に公開鍵暗号を対象としたタイミングアタックと呼ばれる方法が提案され（後述する非特許文献１参照）、更にタイミングアタックに対する防御技術が提案されている（後述する特許文献１参照）。
【００１１】
非特許文献１に記載されるタイミングアタックは、公開鍵暗号の基本演算である冪乗剰余演算の演算時間の差違に基づいて秘密鍵の候補を絞り込むものであり、このため特許文献１では、冪乗剰余演算毎に伝搬遅延によるクリティカルパスの遅延時間を変化させることで、公開鍵暗号に対するタイミングアタックを防御している。
【００１２】
【非特許文献１】
Ｐａｕｌ　Ｃ．Ｋｏｈｃｅｒ，”Ｔｉｍｉｎｇ　Ａｔｔａｃｋｓ　ｏｎ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎｓ　ｏｆ　Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ，ＲＳＡ，ＤＳＳ，ａｎｄ　Ｏｔｈｅｒ　Ｓｙｓｔｅｍｓ，Ａｄｖａｎｃｅｓｍ　Ｃｒｙｐｔｏｌｏｇｙ：Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｃｒｙｐｔｏ　９６，Ｐｌｅｎｕｍ　Ｐｒｅｓｓ，１９９５，ｐｐ１０４−１１３
【特許文献１】
特開平１０−２２２０６５号公報
【００１３】
【発明が解決しようとする課題】
本発明者は、換字テーブルを用いて暗号化を行う図１４に示したような暗号装置の安全性を研究する過程で、新たな暗号解読法を見出した。以下、この新たな暗号解読法をキャッシュ攻撃型暗号解読法と呼び、その解読方法について説明する。
【００１４】
今、図１５に示すように、平文Ｐ０と鍵ｋ０の排他的論理和で換字テーブルＳを引いた出力値と、平文Ｐ１と鍵ｋ１の排他的論理和で同じ換字テーブルＳを引いた出力値とを暗号文とする暗号器を考えてみる。そして、双方で換字テーブルＳのそれぞれ異なるエントリを引いたものとする。このとき、次式が成り立つ。
Ｐ０○ｋ０≠Ｐ１○ｋ１
Ｐ０○Ｐ１≠ｋ０○ｋ１＝Δｋ
…（１）
ここで、記号○は排他的論理和を示し、鍵ｋ０、ｋ１のビット数はｎである。また、Δｋを鍵差分と呼ぶ。
【００１５】
式（１）は２テーブルモデルであるが、一般にｎテーブルモデルへ拡張することができ、次式が導き出せる。
Ｐｉ○ｋｉ≠Ｐｊ○ｋｊ
Ｐｉ○Ｐｊ≠ｋｉ○ｋｊ＝Δｋｉｊ
…（２）
ここで、ｉ、ｊ＝１〜ｎである。
【００１６】
式（２）は、暗号過程（または復号過程）で換字テーブルＳをｎ回引く場面がある場合に、全ての場面で換字テーブルＳの異なるエントリを引くこととなる任意の２つの平文Ｐｉと平文Ｐｊの排他的論理和は鍵差分Δｋｉｊに一致せず、且つ、任意の２つの鍵はその鍵差分がΔｋｉｊとなる関係にあることを意味する。このような鍵差分Δｋｉｊが求まれば、鍵探索の範囲は２２Ｎから２Ｎに狭まる。例えば、図１５においてｋ０〇ｋ１＝ΔｋのＮビットが求まれば、ｋ０のＮビットを全数探査すればｋ１＝ｋ０〇Δｋで他方のＮビットのｋ１が計算できるからである。これにより、ｋ０とｋ１の２Ｎビットの全数探査が、ｋ０のみのＮビットの全数探査で済むようになる。
【００１７】
鍵差分Δｋｉｊは、例えば以下のようにして求めることができる。先ず、図１６（ａ）に示すように、鍵差分Δｋｉｊの取りうる全ての値毎に初期値として値０のカウンタを設定したテーブルを用意する。次に、暗号過程の全場面で換字テーブルＳの異なるエントリを引く多数の平文の集合から任意のペアを抽出し、そのペアの排他的論理和の値と一致する鍵差分Δｋｉｊに対応するカウンタを＋１する処理を、全てのペアについて繰り返す。この結果、カウンタの値は図１６（ｂ）に示すように更新されていき、初期値０のまま或いは極めて小さな値（この値は式（２）の成立確率に依存する）になっているカウンタに対応する鍵差分Δｋｉｊの値が求める鍵差分となる。
【００１８】
次に、暗号過程（または復号過程）で換字テーブルＳをｎ回引く場面がある場合に、全ての場面（もしくは、かなり多くの場面）で換字テーブルＳの異なるエントリを引くこととなる任意の平文の集合を求める方法について説明する。
【００１９】
図１４で説明したように、キャッシュ４を備えるコンピュータで暗号プログラム３を実行すると、ＣＰＵ１の処理速度が一定で、他のプログラムが実行されていない理想的な環境下でも、与える平文（または暗号文）によって暗号化処理時間（または復号時間）が相違する。その理由は、与える平文が異なれば、換字テーブル（Ｓ）３０５の使用するエントリが異なる場合があり、換字テーブル３０５アクセス時のキャッシュヒット率が相違するからである。つまり、キャッシュミスヒットが最も多くなる平文の暗号処理時間が最も長くなる。キャッシュミスヒットが最も多くなる平文は、換字テーブルＳを引く全場面（もしくは、かなり多くの場面）で異なるエントリを引いている可能性があると推測される。
【００２０】
本発明者は、この推測の正しさを、既知の暗号アルゴリズムを用いて検証した。検証に使用した暗号アルゴリズムは、１９９６年に三菱電気株式会社によって提案されたＭＩＳＴＹ１という、６４ビットのブロック暗号（鍵長は１２８ビット）である。図１７にＭＩＳＴＹ１のデータランダム化部の構成を示し、図１８にデータランダム化部で使用されるＦＯｉ関数と、さらにこのＦＯｉ関数で使用されるＦＩｉｊ関数の構成を示す。ＦＯｉ関数は合計８個あり、１つのＦＯｉ関数の中に３個のＦＩｉｊ関数があり、１つのＦＩｉｊ関数の中で換字テーブルＳ９が２回使用され、換字テーブルＳ７が１回使用されている。つまり、暗号化の過程で、換字テーブルＳ９は、８×３×２＝４８回使用され、換字テーブルＳ７は８×３×１＝２４回使用される。換字テーブルＳ９は入力が９ビットで、５１２のエントリ（サンプルプログラムでは１エントリのサイズは３２ビットで記述されていた）を有し、換字テーブルＳ７は入力が７ビットで、１２８のエントリ（サンプルプログラムでは１エントリのサイズは８ビットで記述されていた）を有する。
【００２１】
図１９は、ＭＩＳＴＹ１で多数の平文を暗号化したときの暗号化時間の分布を示し、横軸は暗号化時間、縦軸は平文数である。また、図２０は、暗号化時間と変換テーブルＳ９の動作エントリ数の関係を示し、図２１は、暗号化時間と変換テーブルＳ７の動作エントリ数の関係を示す。ここで、動作エントリ数とは、変換テーブルのエントリの内、幾つのエントリが暗号化処理で使用されたかを示し、変換テーブルＳ９の最大値は４８、変換テーブルＳ７の最大値は２４である。図１９および図２０から理解されるように、暗号処理時間が或るしきい値Ｔ以上かかる平文は、換字テーブルＳ９を引く殆どの場面で異なるエントリを引いており、毎回キャッシュミスヒットを起こしているために暗号処理時間が長くなっている。これに対し、変換テーブルＳ７は、動作エントリ数にかかわらず暗号処理時間はほぼ一定である。変換テーブルＳ９とＳ７とでこのような差違が生じる理由は、変換テーブルＳ７は１２８エントリと小型のテーブルであるため、何回かミスヒットするとキャッシュ４にテーブルの大部分のエントリがロードされて、その後ミスヒットが発生しなくなるのに対し、変換テーブルＳ９は５１２エントリと大型のテーブルであるため、そのような状況が発生しないためと考えられる。従って、図１５および図１６で説明した原理による攻撃は、換字テーブルＳ７に対しては余り効果がなく、換字テーブルＳ９が攻撃対象となる。
【００２２】
図２２は、暗号過程で換字テーブルＳ９をほぼ４８回引く可能性が高い平文の集合を抽出する処理の一例を示す。先ず、ＭＩＳＴＹ１の暗号プログラムをコンピュータのメモリにロードする（ステップ１０１）。次に、乱数によって平文を生成し（ステップ１０２）、コンピュータのキャッシュをクリアし（ステップ１０３）、前記生成した平文を暗号化対象の平文に設定して（ステップ１０４）、ＭＩＳＴＹ１による暗号化とこの暗号化の処理に要した時間の測定とを行う（ステップ１０５）。次に、測定した暗号化時間が予め設定したしきい値Ｔ以上であるかどうかを判定する（ステップ１０６）。ここで、しきい値Ｔは図１９および図２０のＴで示される暗号化時間を使用する。しきい値Ｔは、解読が成立するのに必要充分な数の平文が得られるように設定する。因みに、式（２）の成立確率が高いほど少ない数の平文で足りる。そして、暗号化時間がしきい値Ｔ以上であれば、今回の平文を保存し（ステップ１０７）、ステップ１０２に戻って上述した処理を繰り返す。暗号化時間がしきい値Ｔ以上でなければ、今回の平文を保存せずにステップ１０２に戻って上述した処理を繰り返す。このような処理の繰り返しによって、暗号過程で換字テーブルＳ９をほぼ４８回引く可能性が高い平文を充分な数だけ抽出することができる。
【００２３】
こうして抽出した平文の集合を用いて、図１６で示したような方法で鍵差分Δｋを決定し、鍵の候補を絞り込む。そして、最終的には、確定しなかった鍵のビット部分について総当りによってビット値を確定することにより、秘密鍵の全ビットを特定する。
【００２４】
このように、キャッシュを備えるコンピュータに、換字テーブルを用いて暗号化処理を行う暗号プログラムを実装した暗号装置では、キャッシュ攻撃型暗号解読法により、暗号化時間から換字エントリの動作エントリ数が推測され、鍵差分の決定によって鍵の候補数が絞り込まれ、最終的には鍵の全ビットが解読されてしまう危険性がある。キャッシュ攻撃型暗号解読法はタイミングアタックの一種と考えられるが、冪乗剰余積演算を使用しない共通鍵暗号に対して適用されるため、特許文献１記載の技術では防御できない。このため、キャッシュ攻撃型暗号解読方法に頑健な暗号装置の開発が強く望まれる。
【００２５】
本発明はこのような事情に鑑みて提案されたものであり、その目的は、キャッシュ攻撃型暗号解読法に対する防御機能を備えた暗号装置を提供することにある。
【００２６】
【課題を解決するための手段】
第１の観点に基づく本発明の暗号装置は、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を備えたことを特徴とする。ここで、前記調整手段は、暗号処理または復号処理で使用する複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表のみを調整対象として良い。また、攻撃対象とされる可能性の高い変換表には、エントリ総数に対する参照総エントリ数（動作エントリ数）の比である利用率が小さな変換表を含むようにして良い。
【００２７】
前記調整手段は、実質的な暗号処理または復号処理におけるキャッシュミスヒット回数が減少するように、前記変換表をキャッシュにプリロードする手段を備えるようにして良い。
【００２８】
また前記調整手段は、キャッシュミスヒット回数が増加する方向に調整するようにして良い。この場合、前記調整手段は、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表のエントリのうち暗号処理または復号処理で実際に使用されなかったエントリをアクセスする不使用エントリロード手段とを備えるようにしても良いし、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表の使用エントリの最大数と暗号処理または復号処理で実際に使用されたエントリ数の差分だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備えるようにしても良い。また、暗号処理または復号処理で変換表のエントリにキャッシュヒットした回数を管理する使用エントリ管理手段と、前記キャッシュヒットした回数だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備えるようにしても良いし、暗号処理または復号処理で変換表のエントリにキャッシュヒットする毎にキャッシュミスヒットを発生させる手段を備えるようにしても良い。更に、１つの平文または１つの暗号文の暗号処理または復号処理で参照される総回数がｎ回である同一内容の変換表をｎ個備え、各参照毎にそれぞれ異なる変換表を参照させるものであっても良い。
【００２９】
第２の観点に基づく本発明の暗号装置は、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における暗号処理時間または復号処理時間を、任意の平文または暗号文についてほぼ均一化する調整手段を備えたことを特徴とする。この場合、前記調整手段は、実質的な暗号処理または復号処理に要した時間を計測する計測手段と、計測された時間が予め設定された時間より短い場合、不足している時間だけ暗号処理または復号処理に要する時間を延長する延長手段とを含むものであって良い。また、前記予め設定された時間として、実質的な暗号処理または復号処理に要する最大時間を用いても良い。
【００３０】
第３の観点に基づく本発明の暗号装置は、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の実質的な暗号処理または復号処理に要した時間を計測する計測手段と、計測された時間が予め設定された時間より短い場合、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段とを含む調整手段を備えたことを特徴とする。また、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理に要する時間を調整する調整手段を備え、該調整手段は、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段を含むことを特徴とする。
【００３１】
第４の観点に基づく本発明の暗号装置は、換字処理を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、換字処理に用いる変換表のうち攻撃対象とされる可能性の高い変換表でない場合にはテーブル構造の変換表として備え、攻撃対象とされる可能性の高い変換表である場合はテーブル構造の変換表として持たずに演算処理によって換字処理を実行することを特徴とする。
【００３２】
【作用】
第１の観点に基づく本発明の暗号装置にあっては、１つの平文または１つの暗号文の暗号処理または復号処理における換字テーブル等の変換表に対するアクセス時のキャッシュミスヒット回数が、任意の平文または暗号文についてほぼ均一化されるため、換字テーブル等の変換表の動作エントリ数が少ない平文または暗号文も、反対に多い平文または暗号文も、その暗号時間または復号時間がほぼ同じになり、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となる。このため鍵差分を決定できず、鍵の解読が困難となる。
【００３３】
第２の観点に基づく本発明の暗号装置にあっては、１つの平文または１つの暗号文の暗号処理または復号処理における暗号処理時間または復号処理時間が任意の平文または暗号文について均一化されるため、換字テーブル等の変換表の動作エントリ数が少ない平文または暗号文も、反対に多い平文または暗号文も、その暗号時間または復号時間がほぼ同じになり、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となる。このため鍵差分を決定できず、鍵の解読が困難となる。
【００３４】
第３の観点に基づく本発明の暗号装置にあっては、真に最大暗号時間を与える平文とそれ以外の平文の一部とが同じ暗号時間および復号時間になり、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となる。その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。
【００３５】
第４の観点に基づく本発明の暗号装置にあっては、キャッシュ型攻撃暗号解読法による攻撃の可能性の高い換字テーブルが無いので、それに対するキャッシュミスはそもそも発生せず、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となる。その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。
【００３６】
【発明の第１の実施の形態】
図１を参照すると、本発明の第１の実施の形態にかかる暗号装置は、ハードウェアとしてＣＰＵ１とメモリ（主記憶）３とキャッシュ４とを含んで構成されるコンピュータ上に暗号プログラム３Ａが実装されている。
【００３７】
ＣＰＵ１とキャッシュ４との間はデータ線、アドレス線および制御線を含むプロセッサバス５によって接続され、キャッシュ４とメモリ２との間は、同じくデータ線、アドレス線および制御線を含むメモリバス６によって接続されている。キャッシュ４は、メモリ２よりも高速アクセス可能な小容量のメモリであり、メモリ２の内容の一部の写しを保持する。ＣＰＵ１がプロセッサバス５を通じて要求する命令やデータがキャッシュ４に存在すれば、キャッシュヒットした命令やデータがキャッシュ４から直ちにＣＰＵ１に返却される。他方、ＣＰＵ１が要求する命令やデータがキャッシュ４に存在しなければ、キャッシュ４はミスヒットした命令やデータを含む所定サイズのデータをメモリバス６を通じてメモリ２から読み出して自身に格納すると共にＣＰＵ１に該当する命令やデータを返却する。前記所定サイズとしては、例えば３２バイト、１２８バイトが使用される。
【００３８】
暗号プログラム３Ａは、ＤＥＳ暗号やＦＥＡＬ暗号など、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う共通鍵暗号を実現するプログラムであり、通常は図示しない磁気ディスク等の補助記憶装置に格納されており、使用時に図１に示すようにメモリ２にロードされて実行される。図１のメモリ２のブロックの右に記載した構成図は、１つの平文を暗号化する際の暗号プログラム３Ａの処理の内容を示している。ここで、プリロード部３１１が調整手段を構成する。
【００３９】
暗号プログラム３Ａは、他のプログラムからの呼出しなどによって起動されると（ステップ３０１）、先ず、入力部３０２によって、平文の入力、初期置換などの処理を行う。次いで、本実施の形態の特徴として、プリロード部３１１によって、ビット列変換に使用する変換表である換字テーブル３０５をキャッシュ４にプリロードする処理を行う（ステップ３１１）。このプリロードは、例えば、換字テーブル３０５の全エントリを一度リードする処理で可能である。このプリロード処理時に発生するキャッシュミスヒット回数をＣ回とする。このキャッシュミスヒット回数Ｃは、任意の平文および暗号文について等しい。
【００４０】
プリロード対象とする換字テーブル３０５は、本実施の形態の場合、暗号処理または復号処理で使用する全ての換字テーブルのうち、キャッシュ攻撃暗号解読法で攻撃される可能性の高い換字テーブルである。攻撃対象とされる可能性の高い換字テーブルは、当該暗号プログラムのアルゴリズムに照らして事前に決定され、暗号プログラム３Ａに設定されている。図１７および図１８で説明したＭＩＳＴＹ１の場合、変換テーブルＳ９が設定される。一般的に、図２０で示されるように、暗号時間が長くなるのに応じて動作エントリ数が増加する傾向を示す換字テーブルが攻撃対象とされる可能性が高い。また、簡便な方法として、エントリ総数に対する参照総エントリ数（動作エントリ数）の比である利用率が小さい変換表を、攻撃対象とされる可能性の高い換字テーブルとして決定する方法を用いることができる。
【００４１】
次に、暗号プログラム３Ａは、鍵生成部３０３による鍵生成処理、データ変換部３０４によるデータ変換処理を実行する。鍵生成部３０３では、暗号プログラム３Ａが使用する共通鍵を拡大し、データ変換部３０４で使う幾つかの鍵を生成する。データ変換部３０４は、入力部３０２から出力された初期置換後の平文と鍵生成部３０３で生成された鍵を混ぜ合わせる基本操作を複数回繰り返し、暗号文を出力する。このとき、換字を行う場合は、暗号プログラム３Ａに予め設定されている換字テーブル３０５をアクセスして換字処理が実行されるが、換字テーブルのうちプリロード部３１１でキャッシュ４にプリロードされた換字テーブルのアクセス時にはほぼ１００％近くキャッシュヒットする。換言すれば、攻撃対象となる可能性の高いものとして設定された換字テーブルに対する、実質的な暗号処理におけるキャッシュミスヒット回数はほぼ０に均一化される。
【００４２】
データ変換部３０４で複数回の基本操作が繰り返されて得られたデータは、出力部３０６において逆初期置換などの処理が実行され、最終的に得られた暗号文が呼出し元のプログラム等に返却され、１つの平文の暗号化を終える（ステップ３０７）。
【００４３】
以上の暗号プログラム３Ａの動作は平文を暗号化する際の動作であるが、一般に暗号処理と復号処理の大部分は同じである。概略を説明すると、先ず、入力部３０２によって、暗号文の入力、初期置換などの処理を行い、次いで、プリロード部３１１によって、攻撃される可能性の高い換字テーブル３０５をキャッシュ４にプリロードし、鍵生成部３０３による鍵生成処理、データ変換部３０４によるデータ変換処理を実行する。鍵生成部３０３では、暗号時と逆の順番で順次に鍵を生成してデータ変換部３０４に供給し、データ変換部３０４では、暗号時と逆の順番で基本操作を複数回繰り返し、その結果を出力する。最後に出力部３０６において逆初期置換などの処理が実行され、最終的に得られた平文が呼出し元のプログラム等に返却され、１つの暗号文の復号を終える（ステップ３０７）。
【００４４】
本実施の形態によれば、キャッシュ型攻撃暗号解読法の攻撃対象とされる可能性の高い換字テーブルについては、１つの平文または１つの暗号文の実質的な暗号処理または復号処理におけるアクセス時のキャッシュミスヒット回数が、任意の平文または暗号文についてほぼ０に均一化される。また、その換字テーブルのプリロード時におけるキャッシュミスヒット回数は常に一定回数Ｃとなる。従って、攻撃対象とされる可能性の高い換字テーブルの動作エントリ数が少ない平文または暗号文も、反対に多い平文または暗号文も、その暗号時間または復号時間がほぼ同じになり、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となる。そうなると、鍵差分を決定できず、結果として鍵の解読が困難となる。
【００４５】
以上の説明では、キャッシュ型攻撃暗号解読法で攻撃される可能性の高い換字テーブルだけをプリロードしたが、キャッシュ４の容量が許すなら、全ての換字テーブルをプリロードするようにしても良い。この場合、真に残したい換字テーブルがキャッシュのＬＲＵ等の掃き出しアルゴリズムで掃き出されてしまわないように、攻撃される可能性の高い換字テーブルは他の換字テーブルより後にプリロードするのが望ましい。また、キャッシュ４に保持されたデータに優先度を付けることができ、優先度の高いデータほど掃き出され難くすることができるコンピュータでは、攻撃される可能性の高い換字テーブルのデータに高い優先度を設定してプリロードするのが望ましい。
【００４６】
図１の実施の形態では、換字テーブル３０５を参照する箇所が暗号プログラム３Ａのデータ変換部３０４内だけであるＤＥＳ等の共通鍵暗号を対象としたので、換字テーブルのプリロード部３１１をデータ変換部３０４の直前に設けたが、スタートのステップ３０１の直後に設けるようにしても良い。こうすれば、入力部３０２や、鍵生成部３０３においても換字テーブル３０５を参照するような共通鍵暗号に対しても適用可能である。また、同じ換字テーブルのプリロードを複数の時点、例えばスタートのステップ３０１の直後とデータ変換部３０４の直前に設けるようにしても良い。更に、暗号プログラム３Ａが呼出される前に、換字テーブル３０５のプリロード処理を行うプログラムを別途設けることも考えられる。
【００４７】
また、図１の実施の形態では、プリロード対象となる換字テーブルの全エントリがキャッシュ４にプリロードされるようにしたが、例えば約半分程度のエントリをプリロードしても、キャッシュミスヒット回数を或る程度均一化できるため、必ずしも全エントリをプリロードする必要はない。
【００４８】
【発明の第２の実施の形態】
図２（ａ）を参照すると、本発明の第２の実施の形態にかかる暗号装置は、図１の第１の実施の形態にかかる暗号装置と比較して、暗号プログラム３Ｂには、換字テーブル３０５のプリロード部がなく、その代わりに、換字テーブル３０５のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理部３１２と、換字テーブル３０５のエントリのうち暗号処理または復号処理で実際に使用されなかったエントリをアクセスする不使用エントリロード部３１３とを備えている。ここで、使用エントリ管理部３１２と不使用エントリロード部３１３とで調整手段を構成する。以下、第１の実施の形態の暗号装置との相違点を中心に、本実施の形態の構成と動作を説明する。
【００４９】
図２（ｂ）は使用エントリ管理部３１２に備わる管理テーブルの一例を示す。この管理テーブルは、キャッシュ攻撃型暗号解読法によって攻撃される可能性の高い換字テーブル毎に対応して設けられ、対応する換字テーブルと同数のエントリを持つ。管理テーブルの各エントリは、暗号処理および復号処理の開始時点で未使用を示す値にクリアされる。図２（ｂ）では、×の記号が未使用を示す。使用エントリ管理部３１２は、暗号処理または復号処理の過程で、攻撃される可能性の高い換字テーブルのエントリが参照される毎に、対応する管理テーブルの対応するエントリを使用済みを示す値に変更する。図２（ｂ）では、○の記号が使用済みを示す。つまり、○の記号が付けられたエントリに対応する換字テーブルエントリは動作エントリであることが示される。
【００５０】
不使用エントリロード部３１３は、実際の暗号処理または復号処理でもはや換字テーブル３０５が参照されなくなった時点で、図２（ｂ）の管理テーブルを参照し、攻撃対象とされる可能性の高い換字テーブル毎に、参照されなかったエントリの全てをロード（参照、リード）する命令を実行する。
【００５１】
次に本実施の形態の効果を説明する。今、攻撃対象とされる可能性の高い換字テーブルとして、ＭＩＳＴＹ１の換字テーブルＳ９を考える。この換字テーブルＳ９のエントリ総数は５１２、１文の暗号化または復号化で動作するエントリ数（最大動作エントリ数）は４８である。図２２で説明したように攻撃者は、暗号プログラム３Ｂの起動前に換字テーブルＳ９をクリアするため、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最大値は４８になる。また、実際上は出現しないかも知れないが、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最小数を１とする。
【００５２】
キャッシュミスヒット回数が最大の４８の場合、動作エントリ数も４８なので、不使用エントリロード部３１３は、５１２−４８＝４６４エントリをリードする。このときのキャッシュミスヒット回数は、既に４８エントリのキャッシュミスヒットにより換字エントリＳ９の未だ参照されていない他の多くのエントリがキャッシュ４に存在するため、「小さな数の或る回数」となる。他方、キャッシュミスヒット回数が最小の１の場合、動作エントリ数も１なので、不使用エントリロード部３１３は、５１２−１＝５１１エントリをリードする。このときのキャッシュミスヒット回数は、未だ１エントリのキャッシュミスしか起こしていないので換字エントリＳ９の未だ参照されていない他の多くのエントリはキャッシュ４に存在しないため、「大きな数の或る回数」となる。従って、最終的なキャッシュミスヒット回数は、キャッシュミスヒット回数が最大の４８の場合、４８＋「小さな数の或る回数」となり、キャッシュミスヒット回数が最小の１の場合、１＋「大きな数の或る回数」となり、両者は均一化される傾向を示す。このため、第１の実施の形態と同様の理由で、キャッシュ攻撃型暗号解読法に対する防御が可能になる。
【００５３】
以上の説明では、キャッシュ型攻撃暗号解読法で攻撃される可能性の高い換字テーブルについてだけ不使用エントリ分のロードを実行したが、全ての換字テーブルを対象にして同様のロードを実行しても良い。
【００５４】
【発明の第３の実施の形態】
図３を参照すると、本発明の第３の実施の形態にかかる暗号装置は、図２（ａ）の第２の実施の形態にかかる暗号装置と比較して、暗号プログラム３Ｃに、不使用エントリロード部３１３の代わりに、換字テーブル３０５の使用エントリの最大数と暗号処理または復号処理で実際に使用されたエントリ数の差分である不足エントリ数だけキャッシュミスヒットを発生させるキャッシュミスヒット発生部３１４を備えている。ここで、使用エントリ管理部３１２とキャッシュミスヒット発生部３１４とで調整手段を構成する。以下、第２の実施の形態の暗号装置との相違点を中心に、本実施の形態の構成と動作を説明する。
【００５５】
第２の実施の形態と同様に使用エントリ管理部３１２は、図２（ｂ）に示したような管理テーブルによって、キャッシュ攻撃型暗号解読法によって攻撃される可能性の高い換字テーブル毎に、暗号処理または復号処理で実際に使用されたエントリを管理している。キャッシュミスヒット発生部３１４は、実際の暗号処理または復号処理でもはや換字テーブル３０５が参照されなくなった時点で、図２（ｂ）の管理テーブルを参照し、攻撃対象とされる可能性の高い換字テーブル毎に、使用エントリの最大数と使用されたエントリ数の差分である不足エントリ数を算出する。そして、その不足エントリ数の総数だけ、キャッシュミスヒットを発生させる処理を実行する。この処理は、例えばメモリ２上に暗号化および復号化で使わないデータ領域を設定しておき、キャッシュ４に一度に読み込まれるデータサイズ以上の間隔でリード要求を発行することで可能である。
【００５６】
次に本実施の形態の効果を説明する。今、攻撃対象とされる可能性の高い換字テーブルとして、ＭＩＳＴＹ１の換字テーブルＳ９を考える。この換字テーブルＳ９のエントリ総数は５１２、最大動作エントリ数は４８である。図２２で説明したように攻撃者は、暗号プログラム３Ｃの起動前に換字テーブルＳ９をクリアするため、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最大値は４８である。また、最小数は第２の実施の形態と同様に１を想定する。
【００５７】
キャッシュミスヒット回数が最大の４８の場合、動作エントリ数も４８なので、キャッシュミスヒット発生部３１４は、不足エントリ数として、４８−４８＝０を算出する。従って、この場合はキャッシュミスヒットはもはや１回も発生させない。他方、キャッシュミスヒット回数が最小の１の場合、動作エントリ数も１なので、キャッシュミスヒット発生部３１４は、不足エントリ数として、４８−１＝４７を算出する。そして、４７回だけキャッシュミスヒットを発生させる。従って、最終的なキャッシュミスヒット回数の総数は１＋４７＝４８となり、両者は均一化される。このため、第２の実施の形態と同様の理由で、キャッシュ攻撃型暗号解読法に対する防御が可能になる。
【００５８】
以上の説明では、キャッシュ型攻撃暗号解読法で攻撃される可能性の高い換字テーブルについてだけ不足エントリ分のキャッシュミスヒットを発生させたが、全ての換字テーブルを対象にして同様のキャッシュミスヒットを発生させるようにしても良い。
【００５９】
【発明の第４の実施の形態】
図４（ａ）を参照すると、本発明の第４の実施の形態にかかる暗号装置は、図２（ａ）の第２の実施の形態にかかる暗号装置と比較して、暗号プログラム３Ｄに、使用エントリ管理部３１２および不使用エントリロード部３１３の代わりに、暗号処理または復号処理で換字テーブル３０５のエントリにキャッシュヒットした回数を管理する使用エントリ管理部３１５および前記キャッシュヒットした回数だけキャッシュミスヒットを発生させるキャッシュミスヒット発生部３１６とを備えている。ここで、使用エントリ管理部３１５とキャッシュミスヒット発生部３１６とで調整手段を構成する。以下、第２の実施の形態の暗号装置との相違点を中心に、本実施の形態の構成と動作を説明する。
【００６０】
図４（ｂ）は使用エントリ管理部３１５に備わる管理テーブルの一例を示す。この管理テーブルは、キャッシュ攻撃型暗号解読法によって攻撃される可能性の高い換字テーブル毎に対応して設けられ、対応する換字テーブルと同数のエントリを持つ。管理テーブルの各エントリは、暗号処理および復号処理の開始時点で０の値にクリアされる。使用エントリ管理部３１５は、暗号処理または復号処理の過程で、攻撃される可能性の高い換字テーブルのエントリが参照される毎に、対応する管理テーブルの対応するエントリの値を＋１する。
【００６１】
キャッシュミスヒット発生部３１６は、実際の暗号処理または復号処理でもはや換字テーブル３０５が参照されなくなった時点で、図４（ｂ）の管理テーブルを参照し、攻撃対象とされる可能性の高い換字テーブル毎に、キャッシュヒットした回数の総数を求め、その総数だけキャッシュミスヒットを発生させる。この処理は、第３の実施の形態のキャッシュミスヒット発生部３１４と同様に行える。
【００６２】
次に本実施の形態の効果を説明する。今、攻撃対象とされる可能性の高い換字テーブルとして、ＭＩＳＴＹ１の換字テーブルＳ９を考える。この換字テーブルＳ９のエントリ総数は５１２、最大動作エントリ数は４８である。図２２で説明したように攻撃者は、暗号プログラム３Ｄの起動前に換字テーブルＳ９をクリアするため、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最大値は４８である。また、最小数は第２の実施の形態と同様に１を想定する。
【００６３】
キャッシュミスヒット回数が最大の４８の場合、動作エントリ数も４８なので、図４（ｂ）の管理テーブルのエントリの値は、何れか４８個のエントリだけが値１を示し、他の全てのエントリは値０になる。キャッシュミスヒット発生部３１６は、キャッシュヒット回数の総数として、２以上の値を持つエントリ毎に、そのエントリの値から１を引いた値を計算し、その結果を合計する。従って、今の場合は０になる。従って、キャッシュミスヒット発生部３１６は１回もキャッシュミスヒットを発生させない。この結果、キャッシュミスヒット回数の総数は４８となる。他方、キャッシュミスヒット回数が最小の１の場合、動作エントリ数も１なので、図４（ｂ）の管理テーブルのエントリの値は、何れか１つのエントリの値が４８になり、他の全てのエントリは値０になる。従って、キャッシュミスヒット発生部３１４は、キャッシュヒット回数として、４８−１＝４７を求め、キャッシュミスヒットを４７回発生させる。この結果、最終的なキャッシュミスヒット回数の総数は１＋４７＝４８となり、両者は均一化される。このため、第２の実施の形態と同様の理由で、キャッシュ攻撃型暗号解読法に対する防御が可能になる。
【００６４】
以上の説明では、キャッシュ型攻撃暗号解読法で攻撃される可能性の高い換字テーブルについてだけキャッシュヒット回数分のキャッシュミスヒットを発生させたが、全ての換字テーブルを対象にして同様のキャッシュミスヒットを発生させるようにしても良い。
【００６５】
また、本実施の形態では、キャッシュヒットした回数分のキャッシュミスヒットをキャッシュミスヒット発生部３１６でまとめて発生したが、他の実施の形態として、使用エントリ管理部３１５にキャッシュミスヒットを発生させる機能を持たせ、キャッシュヒットが発生する毎に、つまり図４（ｂ）の管理テーブルの或るエントリの値を＋１したときに２以上の値となる毎に、１回だけキャッシュミスヒットを発生させるようにしても良い。
【００６６】
【発明の第５の実施の形態】
図５を参照すると、本発明の第５の実施の形態にかかる暗号装置は、図１４に示した従来の暗号装置と比較して、暗号プログラム３Ｅは、換字テーブル３０５が１つの平文または１つの暗号文の暗号処理または復号処理でｎ回参照される場合に、換字テーブル３０５と同じ内容を持つｎ個の換字テーブル３０５−１〜３０５−ｎを備え、データ変換部３０４は、１つの平文または１つの暗号文の暗号処理または復号処理において換字テーブル３０５を参照する場合、各参照毎にそれぞれ異なる換字テーブル３０５−１〜３０５−ｎを参照するように構成される点で相違する。
【００６７】
この第５の実施の形態によれば、１つの平文または１つの暗号文の暗号処理または復号処理において、データ変換部３０４は、換字テーブル３０５を参照する場合、各参照毎にそれぞれ異なる換字テーブル３０５−１〜３０５−ｎを参換するため、何回必ずキャッシュミスヒットが発生する。このため、任意の平文または暗号文について、換字テーブルに対するキャッシュミスヒット回数を均一化することができる。従って、キャッシュ攻撃型暗号解読法による攻撃を防御することができる。
【００６８】
同じ内容の換字テーブルをｎ個独立して備えるようにする換字テーブルは、キャッシュ型攻撃暗号解読法で攻撃される可能性の高い換字テーブルのみとする構成以外に、全ての換字テーブルを対象に複数備える構成が考えられる。
【００６９】
【発明の第６の実施の形態】
図６を参照すると、本発明の第６の実施の形態にかかる暗号装置は、図１４の従来の暗号装置と比較して、暗号プログラム３Ｆに、暗号処理および復号処理の開始時に内部のタイマＴを起動するタイマ起動部３２１と、暗号処理および復号処理の終了時にタイマＴのタイマ値が予め設定された暗号処理または復号処理の最大時間Ｔｍａｘより短いかどうかを判定する判定部３２２と、タイマＴのタイマ値が最大時間Ｔｍａｘより短い場合に、その差の時間「Ｔｍａｘ−Ｔ」だけ暗号処理または復号処理の時間を延長するためにウエイトを行うウエイト部３２３とを備えている。ここで、タイマ起動部３２１と判定部３２２とウエイト部３２３とで調整手段を構成する。
【００７０】
上記の最大時間Ｔｍａｘとしては、例えば、図１９に示したような暗号化時間分布における最大の暗号化時間が用いられる。勿論、その最大の暗号化時間より若干長い時間を設定しても良い。
【００７１】
本実施の形態の暗号装置によれば、１つの平文または１つの暗号文の暗号処理または復号処理における暗号処理時間および復号処理時間が、任意の平文または暗号文についてほぼ均一化するため、図１９の暗号化時間分布が最大の暗号化時間の箇所に集中する。このため、キャッシュ攻撃型暗号解読法による攻撃を防御することができる。
【００７２】
【発明の第７の実施の形態】
図７を参照すると、本発明の第７の実施の形態にかかる暗号装置は、図６の第６の実施の形態の暗号装置と比較して、暗号プログラム３Ｇに、ウエイト部３２３に代えて、予め定められた一定時間Ｔｃだけウエイトを行うウエイト部３２４を備えている。ここで、一定時間Ｔｃとしては、例えば、図１９に示したような暗号化時間分布における最大暗号時間の半分の時間を用いる。勿論、それより若干長い時間、短い時間を設定しても良い。ここで、タイマ起動部３２１と判定部３２２とウエイト部３２４とで調整手段を構成する。
【００７３】
本実施の形態の暗号装置によれば、図１９に示した暗号化時間分布の中央部分の山が最大の暗号時間の箇所に移動し、真に最大暗号時間を与えた平文に混合される。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となる。その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。
【００７４】
【発明の第８の実施の形態】
図８を参照すると、本発明の第８の実施の形態にかかる暗号装置は、図７の第７の実施の形態の暗号装置と比較して、暗号プログラム３Ｈに、ウエイト部３２４に代えて、０か１の何れかの値をとる乱数ｒを無作為に生成する乱数生成部３２５、生成した乱数ｒが０か否かを判定する判定部３２６、乱数ｒが０の場合に、ウエイト時間ｔを乱数によって生成するウエイト時間生成部３２７、生成されたウエイト時間ｔだけウエイトを行うウエイト部３２８を備えている。ここで、タイマ起動部３２１と判定部３２２、３２６と、乱数生成部３２５とウエイト時間生成部３２７とウエイト部３２８とで調整手段を構成する。ウエイト時間生成部３２７は、図１９に示したような暗号化時間分布におけるほぼ最大暗号時間から時間０の範囲内で、ウエイト時間ｔを無作為に生成する。
【００７５】
本実施の形態の暗号装置によれば、図１９に示した暗号化時間分布の特性が不定なものとなり、真に最大暗号時間を与えた平文とそれ以外の平文とが同じ暗号時間帯に出現する。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となり、その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。
【００７６】
【発明の第９の実施の形態】
図９を参照すると、本発明の第９の実施の形態にかかる暗号装置は、図１４の従来の暗号装置と比較して、暗号プログラム３Ｉに、０か１の何れかの値をとる乱数ｒを無作為に生成する乱数生成部３３１、生成した乱数ｒが０か否かを判定する判定部３３２、乱数ｒが０の場合に、予め定められた一定時間Ｔｃだけウエイトを行うウエイト部３３３を備えている。ここで、乱数生成部３３１と判定部３３２とウエイト部３３３とで調整手段を構成する。一定時間Ｔｃとしては、例えば、図１９に示したような暗号化時間分布における最大暗号時間の半分の時間を用いる。勿論、それより若干長い時間、短い時間を設定しても良い。
【００７７】
本実施の形態の暗号装置によれば、図１９に示した暗号化時間分布の特性が不定なものとなり、真に最大暗号時間を与えた平文は同じ暗号時間に揃わず、また、それ以外の平文と同じ暗号時間帯に出現する。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となり、その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。
【００７８】
なお、図９の実施の形態では、暗号プログラム３Ｉの終了間際でウエイトを行うようにしているが、ウエイトする箇所は暗号プログラム３Ｉの任意の箇所で良い。また、複数の箇所で分散的にウエイトするようにしても良い。
【００７９】
【発明の第１０の実施の形態】
図１０を参照すると、本発明の第１０の実施の形態にかかる暗号装置は、図１４の従来の暗号装置と比較して、暗号プログラム３Ｊに、ウエイト時間ｔを乱数によって生成するウエイト時間生成部３３４、生成されたウエイト時間ｔだけウエイトを行うウエイト部３３５を備えている。ここで、ウエイト時間生成部３３４とウエイト部３３５とで調整手段を構成する。ウエイト時間生成部３３４は、図１９に示したような暗号化時間分布におけるほぼ最大暗号時間から時間０の範囲内で、ウエイト時間ｔを無作為に生成する。
【００８０】
本実施の形態の暗号装置によれば、図１９に示した暗号化時間分布の特性が不定なものとなり、真に最大暗号時間を与えた平文は同じ暗号時間に揃わず、また、それ以外の平文と同じ暗号時間帯に出現する。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となり、その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。
【００８１】
なお、図１０の実施の形態では、暗号プログラム３Ｊの終了間際でウエイトを行うようにしているが、ウエイトする箇所は暗号プログラム３Ｊの任意の箇所で良い。また、複数の箇所で分散的にウエイトするようにしても良い。
【００８２】
【発明の第１１の実施の形態】
図１１を参照すると、本発明の第１１の実施の形態にかかる暗号装置は、図１０の第１０の実施の形態の暗号装置と比較して、暗号プログラム３Ｋに、０か１の何れかの値をとる乱数ｒを無作為に生成する乱数生成部３３６と生成した乱数ｒが０か否かを判定する判定部３３７とが追加され、ウエイト時間ｔを乱数によって生成するウエイト時間生成部３３４および生成されたウエイト時間ｔだけウエイトを行うウエイト部３３５は、０の乱数ｒが生成された場合に限って動作する。ここで、乱数生成部３３６と判定部３３７とウエイト時間生成部３３４とウエイト部３３５とで調整手段を構成する。ウエイト時間生成部３３４が生成するウエイト時間ｔは、例えば、図１９に示したような暗号化時間分布におけるほぼ最大暗号時間から時間０の範囲内で無作為に生成される。
【００８３】
本実施の形態の暗号装置によれば、図１９に示した暗号化時間分布の特性が不定なものとなり、真に最大暗号時間を与えた平文は同じ暗号時間に揃わず、また、それ以外の平文と同じ暗号時間帯に出現する。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となり、その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。
【００８４】
なお、図１１の実施の形態では、暗号プログラム３Ｋの終了間際でウエイトを行うようにしているが、ウエイトする箇所は暗号プログラム３Ｋの任意の箇所で良い。また、複数の箇所で分散的にウエイトするようにしても良い。
【００８５】
【発明の第１２の実施の形態】
図１２を参照すると、本発明の第１２の実施の形態にかかる暗号装置は、図１４の従来の暗号装置と比較して、暗号プログラム３Ｌが、換字処理に用いる換字テーブルのうち攻撃対象とされる可能性の高い換字テーブル以外はテーブル構造の換字テーブルとして備えるが、攻撃対象とされる可能性の高い換字テーブルは持たず、演算処理によって等価な換字処理を実行する点で相違する。換字テーブルを使わずに等価な換字処理を実現する演算処理の一例としてブール演算を使う方法が考えられる。以下、２ビットの例で説明する。今、（０，１，２，３）を（３，０，１，２）に変換するものとする。入力の各ビットをｘ１、ｘ２、出力の各ビットをｙ１、ｙ２とすると、以下のように表現される。
（（ｘ１ｘ２），（ｘ１ｘ２），（ｘ１ｘ２），（ｘ１ｘ２））
＝（（０　０），　（０　１），（１　０），（１　１））
→（（ｙ１ｙ２），（ｙ１ｙ２），（ｙ１ｙ２），（ｙ１ｙ２））
＝（（１　１），　（０　０），（０　１），（１　０））
ここで、ｘ１とｘ２の排他的論理和をとると（０，１，１，０）なので、この排他的論理和を反転（ｎｏｔ）すると（１，０，０，１）となり、ｙ１の列（１，０，０，１）と等しくなる。また、ｙ２の列（１，０，１，０）はｘ２の列（０，１，０，１）を反転したものに等しい。従って、（０，１，２，３）を（３，０，１，２）に変換する演算処理は、以下のブール式で実現できる。
ｙ１＝¬（ｘ１○ｘ２）
ｙ２＝¬ｘ２
…（３）
ここで、¬は反転（ｎｏｔ）、○は排他的論理和を示す。
【００８６】
本実施の形態の暗号装置によれば、キャッシュ型攻撃暗号解読法による攻撃の可能性の高い換字テーブルを使わないので、それに対するキャッシュミスはそもそも発生せず、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となる。その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。
【００８７】
本実施の形態では、攻撃対象となる可能性の高い換字テーブルだけを無くしたが、攻撃対象となる可能性の低い換字テーブルも無くして、演算処理によって等価な換字処理を実行するようにしても良い。
【００８８】
【発明の効果】
以上説明したように本発明によれば、キャッシュ攻撃型暗号解読法という新たな暗号解読法による攻撃によって秘密鍵を推測されることを防止することができるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態にかかる暗号装置の構成図である。
【図２】本発明の第２の実施の形態にかかる暗号装置の構成図である。
【図３】本発明の第３の実施の形態にかかる暗号装置の構成図である。
【図４】本発明の第４の実施の形態にかかる暗号装置の構成図である。
【図５】本発明の第５の実施の形態にかかる暗号装置の構成図である。
【図６】本発明の第６の実施の形態にかかる暗号装置の構成図である。
【図７】本発明の第７の実施の形態にかかる暗号装置の構成図である。
【図８】本発明の第８の実施の形態にかかる暗号装置の構成図である。
【図９】本発明の第９の実施の形態にかかる暗号装置の構成図である。
【図１０】本発明の第１０の実施の形態にかかる暗号装置の構成図である。
【図１１】本発明の第１１の実施の形態にかかる暗号装置の構成図である。
【図１２】本発明の第１２の実施の形態にかかる暗号装置の構成図である。
【図１３】換字テーブルの構成例を示す図である。
【図１４】従来の暗号装置の構成図である。
【図１５】キャッシュ攻撃型暗号解読法の原理説明図である。
【図１６】キャッシュ攻撃型暗号解読法による鍵差分値の決定方法の説明図である。
【図１７】ＭＩＳＴＹ１のデータランダム化部の構成を示す図である。
【図１８】ＭＩＳＴＹ１のデータランダム化部で使用されるＦＯｉ関数と、さらにこのＦＯｉ関数で使用されるＦＩｉｊ関数の構成を示す図である。
【図１９】暗号化時間分布を示す図である。
【図２０】ＭＩＳＴＹ１で使われる換字テーブルＳ９の動作エントリ数と暗号化時間との関係を示す図である。
【図２１】ＭＩＳＴＹ１で使われる換字テーブルＳ７の動作エントリ数と暗号化時間との関係を示す図である。
【図２２】暗号過程で換字テーブルＳ９の全エントリがほぼ参照される可能性の高い平文の集合を抽出する処理例を示すフローチャートである。
【符号の説明】
１…ＣＰＵ
２…メモリ（主記憶）
３、３Ａ〜３Ｌ…暗号プログラム
４…キャッシュ
５…プロセッサバス
６…メモリバス
【図１】
2004120307.tif 000003
【図２】
2004120307.tif 000004
【図３】
2004120307.tif 000005
【図４】
2004120307.tif 000006
【図５】
2004120307.tif 000007
【図６】
2004120307.tif 000008
【図７】
2004120307.tif 000009
【図８】
2004120307.tif 000010
【図９】
2004120307.tif 000011
【図１０】
2004120307.tif 000012
【図１１】
2004120307.tif 000013
【図１２】
2004120307.tif 000014
【図１３】
2004120307.tif 000015
【図１４】
2004120307.tif 000016
【図１５】
2004120307.tif 000017
【図１６】
2004120307.tif 000018
【図１７】
2004120307.tif 000019
【図１８】
2004120307.tif 000020
【図１９】
2004120307.tif 000021
【図２０】
2004120307.tif 000022
【図２１】
2004120307.tif 000023
【図２２】
2004120307.tif 000024
【手続補正書】
【提出日】平成15年7月10日(2003.7.10)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を備え、前記調整手段は、暗号処理または復号処理で使用する複数の変換表をキャッシュにプリロードするプリロード手段を備え、前記プリロード手段は、前記複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表を他の変換表より後にプリロードするものであることを特徴とする暗号装置。
【請求項２】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムを、高い優先度の付いたデータほどキャッシュから掃き出され難くすることができるキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を備え、前記調整手段は、暗号処理または復号処理で使用する複数の変換表をキャッシュにプリロードするプリロード手段を備え、前記プリロード手段は、前記複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表は高い優先度を設定してプリロードするものであることを特徴とする暗号装置。
【請求項３】
前記プリロード手段は、１つの平文または１つの暗号文の暗号処理または復号処理において同じ変換表を複数の時点でプリロードするものであることを特徴とする請求項１または２記載の暗号装置。
【請求項４】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を備え、前記調整手段は、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表のエントリのうち暗号処理または復号処理で実際に使用されなかったエントリをアクセスする不使用エントリロード手段とを備えたことを特徴とする暗号装置。
【請求項５】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を備え、前記調整手段は、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表の使用エントリの最大数と暗号処理または復号処理で実際に使用されたエントリ数の差分だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備えたことを特徴とする暗号装置。
【請求項６】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を備え、前記調整手段は、暗号処理または復号処理で変換表のエントリにキャッシュヒットした回数を管理する使用エントリ管理手段と、前記キャッシュヒットした回数だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備えたことを特徴とする暗号装置。
【請求項７】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を備え、前記調整手段は、暗号処理または復号処理で変換表のエントリにキャッシュヒットする毎にキャッシュミスヒットを発生させる手段を備えたことを特徴とする暗号装置。
【請求項８】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を備え、前記調整手段は、１つの平文または１つの暗号文の暗号処理または復号処理で参照される総回数がｎ回である同一内容の変換表をｎ個備え、各参照毎にそれぞれ異なる変換表を参照させるものであることを特徴とする暗号装置。
【請求項９】
前記調整手段は、暗号処理または復号処理で使用する複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表のみを調整対象とすることを特徴とする請求項４乃至８の何れか１項に記載の暗号装置。
【請求項１０】
攻撃対象とされる可能性の高い変換表には、エントリ総数に対する参照総エントリ数の比である利用率が小さな変換表を含むことを特徴とする請求項９記載の暗号装置。
【請求項１１】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の実質的な暗号処理または復号処理に要した時間を計測する計測手段と、計測された時間が予め設定された時間より短い場合、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段とを含む調整手段を備えたことを特徴とする暗号装置。
【請求項１２】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理に要する時間を調整する調整手段を備え、該調整手段は、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段を含むことを特徴とする暗号装置。
【請求項１３】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、暗号処理または復号処理で使用する複数の変換表をキャッシュにプリロードする際に攻撃対象とされる可能性の高いものとして設定された変換表を他の変換表より後にプリロードするプリロード手段を備え、１つの平文または１つの暗号文の暗号処理または復号処理における前記攻撃対象とされる可能性の高いものとして設定された変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項１４】
高い優先度の付いたデータほどキャッシュから掃き出され難くすることができるキャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、暗号処理または復号処理で使用する複数の変換表をキャッシュにプリロードする際に攻撃対象とされる可能性の高いものとして設定された変換表は高い優先度を設定してプリロードするプリロード手段を備え、１つの平文または１つの暗号文の暗号処理または復号処理における前記攻撃対象とされる可能性の高いものとして設定された前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項１５】
前記プリロード手段は、１つの平文または１つの暗号文の暗号処理または復号処理において同じ変換表を複数の時点でプリロードするものであることを特徴とする請求項１３または１４記載の暗号プログラム。
【請求項１６】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表のエントリのうち暗号処理または復号処理で実際に使用されなかったエントリをアクセスする不使用エントリロード手段とを含み、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項１７】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表の使用エントリの最大数と暗号処理または復号処理で実際に使用されたエントリ数の差分だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを含み、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項１８】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、暗号処理または復号処理で変換表のエントリにキャッシュヒットした回数を管理する使用エントリ管理手段と、前記キャッシュヒットした回数だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを含み、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項１９】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、暗号処理または復号処理で変換表のエントリにキャッシュヒットする毎にキャッシュミスヒットを発生させる手段を含み、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項２０】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、１つの平文または１つの暗号文の暗号処理または復号処理で参照される総回数がｎ回である同一内容の変換表をｎ個備え、各参照毎にそれぞれ異なる変換表を参照させることにより、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項２１】
前記調整手段は、暗号処理または復号処理で使用する複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表のみを調整対象とすることを特徴とする請求項１６乃至２０の何れか１項に記載の暗号プログラム。
【請求項２２】
攻撃対象とされる可能性の高い変換表には、エントリ総数に対する参照総エントリ数の比である利用率が小さな変換表を含むことを特徴とする請求項２１記載の暗号プログラム。
【請求項２３】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、１つの平文または１つの暗号文の実質的な暗号処理または復号処理に要した時間を計測する計測手段と、計測された時間が予め設定された時間より短い場合、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段とを含む調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項２４】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段を含み、１つの平文または１つの暗号文の暗号処理または復号処理に要する時間を調整する調整手段を有する暗号装置として機能させるための暗号プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
図１２に換字テーブルの簡単な例を示す。この例の換字テーブルは１６個のエントリを有し、各エントリに１６進数で０からＦの番地が振られており、各エントリに０からＦの値が格納されている。左上のエントリを０番地とし、右方向に１、２、３番地を割振り、２段目は左から右に４、５、６、７番地を、３段目は同じく左から右に８、９、Ａ、Ｂ番地を、４段目は同じく左から右にＣ、Ｄ、Ｅ、Ｆ番地を割振るものとすると、例えば、入力ビットが００００（１６進数で０）の場合、０番地のエントリに格納されている１６進数で８の値が読み出され、２進数で表現した１０００が出力される。このような換字テーブルを使用すると、換字テーブルを交換するだけで異なる暗号変換を実施でき、秘匿通信の柔軟性が向上する等の利点がある。


【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
図１３は従来の暗号装置のブロック図である。図１３において、１はＣＰＵ（演算装置）、２はメモリ（主記憶）、３は暗号プログラム、４はキャッシュであり、ＣＰＵ１とキャッシュ４との間はデータ線、アドレス線および制御線を含むプロセッサバス５によって接続され、キャッシュ４とメモリ２との間は、同じくデータ線、アドレス線および制御線を含むメモリバス６によって接続されている。周知のようにキャッシュ４は、メモリ２よりも高速アクセス可能な小容量のメモリであり、メモリ２の内容の一部の写しを保持する。ＣＰＵ１がプロセッサバス５を通じて要求する命令やデータがキャッシュ４に存在すれば（これをキャッシュヒットと呼ぶ）、キャッシュ４はキャッシュヒットした命令やデータを直ちにＣＰＵ１に返却する。他方、ＣＰＵ１が要求する命令やデータがキャッシュ４に存在しなければ（これをキャッシュミスヒットと呼ぶ）、キャッシュ４はミスヒットした命令やデータを含む所定サイズのデータをメモリバス６を通じてメモリ２から読み出して自身に格納すると共にＣＰＵ１に該当する命令やデータを返却する。ここで、所定サイズのデータとは、例えば３２バイト、１２８バイトといったサイズである。このようなサイズでキャッシュ４に読み込んでおくことにより、命令が実行される場合には実行アドレスが近い命令が続けて実行されることが多いという原理（命令の局所性の原理）により、キャッシュヒット率を高めることができ、高速化が可能となる。


【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
暗号プログラム３は、前述したＤＥＳ暗号やＦＥＡＬ暗号などの共通鍵暗号を実現するプログラムであり、通常は図示しない磁気ディスク等の補助記憶装置に格納されており、使用時に図１３に示すようにメモリ２にロードされて実行される。図１３のメモリ２のブロックの右に記載した構成図は、１つの平文を暗号化する際の暗号プログラム３の処理の内容を示している。


【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
【発明が解決しようとする課題】
本発明者は、換字テーブルを用いて暗号化を行う図１３に示したような暗号装置の安全性を研究する過程で、新たな暗号解読法を見出した。以下、この新たな暗号解読法をキャッシュ攻撃型暗号解読法と呼び、その解読方法について説明する。


【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
今、図１４に示すように、平文Ｐ０と鍵ｋ０の排他的論理和で換字テーブルＳを引いた出力値と、平文Ｐ１と鍵ｋ１の排他的論理和で同じ換字テーブルＳを引いた出力値とを暗号文とする暗号器を考えてみる。そして、双方で換字テーブルＳのそれぞれ異なるエントリを引いたものとする。このとき、次式が成り立つ。
Ｐ０○ｋ０≠Ｐ１○ｋ１
Ｐ０○Ｐ１≠ｋ０○ｋ１＝Δｋ
…（１）
ここで、記号○は排他的論理和を示し、鍵ｋ０、ｋ１のビット数はｎである。また、Δｋを鍵差分と呼ぶ。


【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
式（２）は、暗号過程（または復号過程）で換字テーブルＳをｎ回引く場面がある場合に、全ての場面で換字テーブルＳの異なるエントリを引くこととなる任意の２つの平文Ｐｉと平文Ｐｊの排他的論理和は鍵差分Δｋｉｊに一致せず、且つ、任意の２つの鍵はその鍵差分がΔｋｉｊとなる関係にあることを意味する。このような鍵差分Δｋｉｊが求まれば、鍵探索の範囲は２２Ｎから２Ｎに狭まる。例えば、図１４においてｋ０〇ｋ１＝ΔｋのＮビットが求まれば、ｋ０のＮビットを全数探査すればｋ１＝ｋ０〇Δｋで他方のＮビットのｋ１が計算できるからである。これにより、ｋ０とｋ１の２Ｎビットの全数探査が、ｋ０のみのＮビットの全数探査で済むようになる。


【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
鍵差分Δｋｉｊは、例えば以下のようにして求めることができる。先ず、図１５（ａ）に示すように、鍵差分Δｋｉｊの取りうる全ての値毎に初期値として値０のカウンタを設定したテーブルを用意する。次に、暗号過程の全場面で換字テーブルＳの異なるエントリを引く多数の平文の集合から任意のペアを抽出し、そのペアの排他的論理和の値と一致する鍵差分Δｋｉｊに対応するカウンタを＋１する処理を、全てのペアについて繰り返す。この結果、カウンタの値は図１５（ｂ）に示すように更新されていき、初期値０のまま或いは極めて小さな値（この値は式（２）の成立確率に依存する）になっているカウンタに対応する鍵差分Δｋｉｊの値が求める鍵差分となる。


【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
図１３で説明したように、キャッシュ４を備えるコンピュータで暗号プログラム３を実行すると、ＣＰＵ１の処理速度が一定で、他のプログラムが実行されていない理想的な環境下でも、与える平文（または暗号文）によって暗号化処理時間（または復号時間）が相違する。その理由は、与える平文が異なれば、換字テーブル（Ｓ）３０５の使用するエントリが異なる場合があり、換字テーブル３０５アクセス時のキャッシュヒット率が相違するからである。つまり、キャッシュミスヒットが最も多くなる平文の暗号処理時間が最も長くなる。キャッシュミスヒットが最も多くなる平文は、換字テーブルＳを引く全場面（もしくは、かなり多くの場面）で異なるエントリを引いている可能性があると推測される。


【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
本発明者は、この推測の正しさを、既知の暗号アルゴリズムを用いて検証した。検証に使用した暗号アルゴリズムは、１９９６年に三菱電気株式会社によって提案されたＭＩＳＴＹ１という、６４ビットのブロック暗号（鍵長は１２８ビット）である。図１６にＭＩＳＴＹ１のデータランダム化部の構成を示し、図１７にデータランダム化部で使用されるＦＯｉ関数と、さらにこのＦＯｉ関数で使用されるＦＩｉｊ関数の構成を示す。ＦＯｉ関数は合計８個あり、１つのＦＯｉ関数の中に３個のＦＩｉｊ関数があり、１つのＦＩｉｊ関数の中で換字テーブルＳ９が２回使用され、換字テーブルＳ７が１回使用されている。つまり、暗号化の過程で、換字テーブルＳ９は、８×３×２＝４８回使用され、換字テーブルＳ７は８×３×１＝２４回使用される。換字テーブルＳ９は入力が９ビットで、５１２のエントリ（サンプルプログラムでは１エントリのサイズは３２ビットで記述されていた）を有し、換字テーブルＳ７は入力が７ビットで、１２８のエントリ（サンプルプログラムでは１エントリのサイズは８ビットで記述されていた）を有する。


【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
図１８は、ＭＩＳＴＹ１で多数の平文を暗号化したときの暗号化時間の分布を示し、横軸は暗号化時間、縦軸は平文数である。また、図１９は、暗号化時間と変換テーブルＳ９の動作エントリ数の関係を示し、図２０は、暗号化時間と変換テーブルＳ７の動作エントリ数の関係を示す。ここで、動作エントリ数とは、変換テーブルのエントリの内、幾つのエントリが暗号化処理で使用されたかを示し、変換テーブルＳ９の最大値は４８、変換テーブルＳ７の最大値は２４である。図１８および図１９から理解されるように、暗号処理時間が或るしきい値Ｔ以上かかる平文は、換字テーブルＳ９を引く殆どの場面で異なるエントリを引いており、毎回キャッシュミスヒットを起こしているために暗号処理時間が長くなっている。これに対し、変換テーブルＳ７は、動作エントリ数にかかわらず暗号処理時間はほぼ一定である。変換テーブルＳ９とＳ７とでこのような差違が生じる理由は、変換テーブルＳ７は１２８エントリと小型のテーブルであるため、何回かミスヒットするとキャッシュ４にテーブルの大部分のエントリがロードされて、その後ミスヒットが発生しなくなるのに対し、変換テーブルＳ９は５１２エントリと大型のテーブルであるため、そのような状況が発生しないためと考えられる。従って、図１４および図１５で説明した原理による攻撃は、換字テーブルＳ７に対しては余り効果がなく、換字テーブルＳ９が攻撃対象となる。


【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
図２１は、暗号過程で換字テーブルＳ９をほぼ４８回引く可能性が高い平文の集合を抽出する処理の一例を示す。先ず、ＭＩＳＴＹ１の暗号プログラムをコンピュータのメモリにロードする（ステップ１０１）。次に、乱数によって平文を生成し（ステップ１０２）、コンピュータのキャッシュをクリアし（ステップ１０３）、前記生成した平文を暗号化対象の平文に設定して（ステップ１０４）、ＭＩＳＴＹ１による暗号化とこの暗号化の処理に要した時間の測定とを行う（ステップ１０５）。次に、測定した暗号化時間が予め設定したしきい値Ｔ以上であるかどうかを判定する（ステップ１０６）。ここで、しきい値Ｔは図１８および図１９のＴで示される暗号化時間を使用する。しきい値Ｔは、解読が成立するのに必要充分な数の平文が得られるように設定する。因みに、式（２）の成立確率が高いほど少ない数の平文で足りる。そして、暗号化時間がしきい値Ｔ以上であれば、今回の平文を保存し（ステップ１０７）、ステップ１０２に戻って上述した処理を繰り返す。暗号化時間がしきい値Ｔ以上でなければ、今回の平文を保存せずにステップ１０２に戻って上述した処理を繰り返す。このような処理の繰り返しによって、暗号過程で換字テーブルＳ９をほぼ４８回引く可能性が高い平文を充分な数だけ抽出することができる。


【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
こうして抽出した平文の集合を用いて、図１５で示したような方法で鍵差分Δｋを決定し、鍵の候補を絞り込む。そして、最終的には、確定しなかった鍵のビット部分について総当りによってビット値を確定することにより、秘密鍵の全ビットを特定する。


【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
【課題を解決するための手段】
第１の観点に基づく本発明の暗号装置は、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を備え、前記調整手段は、暗号処理または復号処理で使用する複数の変換表をキャッシュにプリロードするプリロード手段を備え、前記プリロード手段は、前記複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表を他の変換表より後にプリロードするものであることを特徴とする。また、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムを、高い優先度の付いたデータほどキャッシュから掃き出され難くすることができるキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を備え、前記調整手段は、暗号処理または復号処理で使用する複数の変換表をキャッシュにプリロードするプリロード手段を備え、前記プリロード手段は、前記複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表は高い優先度を設定してプリロードするものであることを特徴とする。ここで、前記プリロード手段は、１つの平文または１つの暗号文の暗号処理または復号処理において同じ変換表を複数の時点でプリロードするものであっても良い。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】削除
【補正の内容】
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
第２の観点に基づく本発明の暗号装置は、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を備える。具体的には、以下の（１）乃至（５）に記載される何れかの調整手段を備える。
（１）変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表のエントリのうち暗号処理または復号処理で実際に使用されなかったエントリをアクセスする不使用エントリロード手段とを備える調整手段。
（２）変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表の使用エントリの最大数と暗号処理または復号処理で実際に使用されたエントリ数の差分だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備える調整手段。
（３）暗号処理または復号処理で変換表のエントリにキャッシュヒットした回数を管理する使用エントリ管理手段と、前記キャッシュヒットした回数だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備える調整手段。
（４）暗号処理または復号処理で変換表のエントリにキャッシュヒットする毎にキャッシュミスヒットを発生させる手段を備える調整手段。
（５）１つの平文または１つの暗号文の暗号処理または復号処理で参照される総回数がｎ回である同一内容の変換表をｎ個備え、各参照毎にそれぞれ異なる変換表を参照させる調整手段。
ここで、前記（１）〜（５）の調整手段は、暗号処理または復号処理で使用する複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表のみを調整対象として良い。また、攻撃対象とされる可能性の高い変換表には、エントリ総数に対する参照総エントリ数（動作エントリ数）の比である利用率が小さな変換表を含むようにして良い。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】削除
【補正の内容】
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】削除
【補正の内容】
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】００３２
【補正方法】変更
【補正の内容】
【００３２】
【作用】
第１および第２の観点に基づく本発明の暗号装置にあっては、１つの平文または１つの暗号文の暗号処理または復号処理における換字テーブル等の変換表に対するアクセス時のキャッシュミスヒット回数が、任意の平文または暗号文についてほぼ均一化されるため、換字テーブル等の変換表の動作エントリ数が少ない平文または暗号文も、反対に多い平文または暗号文も、その暗号時間または復号時間がほぼ同じになり、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となる。このため鍵差分を決定できず、鍵の解読が困難となる。


【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】００３３
【補正方法】削除
【補正の内容】
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】削除
【補正の内容】
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】００３６
【補正方法】変更
【補正の内容】
【００３６】
【発明の第１の実施の形態】
図１を参照すると、本発明の第１の実施の形態にかかる暗号装置は、ハードウェアとしてＣＰＵ１とメモリ（主記憶）２とキャッシュ４とを含んで構成されるコンピュータ上に暗号プログラム３Ａが実装されている。


【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】００４０
【補正方法】変更
【補正の内容】
【００４０】
プリロード対象とする換字テーブル３０５は、本実施の形態の場合、暗号処理または復号処理で使用する全ての換字テーブルのうち、キャッシュ攻撃暗号解読法で攻撃される可能性の高い換字テーブルである。攻撃対象とされる可能性の高い換字テーブルは、当該暗号プログラムのアルゴリズムに照らして事前に決定され、暗号プログラム３Ａに設定されている。図１６および図１７で説明したＭＩＳＴＹ１の場合、変換テーブルＳ９が設定される。一般的に、図１９で示されるように、暗号時間が長くなるのに応じて動作エントリ数が増加する傾向を示す換字テーブルが攻撃対象とされる可能性が高い。また、簡便な方法として、エントリ総数に対する参照総エントリ数（動作エントリ数）の比である利用率が小さい変換表を、攻撃対象とされる可能性の高い換字テーブルとして決定する方法を用いることができる。


【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】００４５
【補正方法】変更
【補正の内容】
【００４５】
以上の説明では、キャッシュ型攻撃暗号解読法で攻撃される可能性の高い換字テーブルだけをプリロードしたが、キャッシュ４の容量が許すなら、全ての換字テーブルをプリロードする。この場合、真に残したい換字テーブルがキャッシュのＬＲＵ等の掃き出しアルゴリズムで掃き出されてしまわないように、攻撃される可能性の高い換字テーブルは他の換字テーブルより後にプリロードする。また、キャッシュ４に保持されたデータに優先度を付けることができ、優先度の高いデータほど掃き出され難くすることができるコンピュータでは、攻撃される可能性の高い換字テーブルのデータに高い優先度を設定してプリロードする。
【手続補正２５】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
次に本実施の形態の効果を説明する。今、攻撃対象とされる可能性の高い換字テーブルとして、ＭＩＳＴＹ１の換字テーブルＳ９を考える。この換字テーブルＳ９のエントリ総数は５１２、１文の暗号化または復号化で動作するエントリ数（最大動作エントリ数）は４８である。図２１で説明したように攻撃者は、暗号プログラム３Ｂの起動前に換字テーブルＳ９をクリアするため、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最大値は４８になる。また、実際上は出現しないかも知れないが、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最小数を１とする。


【手続補正２６】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
次に本実施の形態の効果を説明する。今、攻撃対象とされる可能性の高い換字テーブルとして、ＭＩＳＴＹ１の換字テーブルＳ９を考える。この換字テーブルＳ９のエントリ総数は５１２、最大動作エントリ数は４８である。図２１で説明したように攻撃者は、暗号プログラム３Ｃの起動前に換字テーブルＳ９をクリアするため、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最大値は４８である。また、最小数は第２の実施の形態と同様に１を想定する。


【手続補正２７】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
次に本実施の形態の効果を説明する。今、攻撃対象とされる可能性の高い換字テーブルとして、ＭＩＳＴＹ１の換字テーブルＳ９を考える。この換字テーブルＳ９のエントリ総数は５１２、最大動作エントリ数は４８である。図２１で説明したように攻撃者は、暗号プログラム３Ｄの起動前に換字テーブルＳ９をクリアするため、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最大値は４８である。また、最小数は第２の実施の形態と同様に１を想定する。


【手続補正２８】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
【発明の第５の実施の形態】
図５を参照すると、本発明の第５の実施の形態にかかる暗号装置は、図１３に示した従来の暗号装置と比較して、暗号プログラム３Ｅは、換字テーブル３０５が１つの平文または１つの暗号文の暗号処理または復号処理でｎ回参照される場合に、換字テーブル３０５と同じ内容を持つｎ個の換字テーブル３０５−１〜３０５−ｎを備え、データ変換部３０４は、１つの平文または１つの暗号文の暗号処理または復号処理において換字テーブル３０５を参照する場合、各参照毎にそれぞれ異なる換字テーブル３０５−１〜３０５−ｎを参照するように構成される点で相違する。


【手続補正２９】
【補正対象書類名】明細書
【補正対象項目名】００６９
【補正方法】変更
【補正の内容】
【００６９】
【発明の第６の実施の形態】
図６を参照すると、本発明の第６の実施の形態にかかる暗号装置の前提となる装置は、図１３の従来の暗号装置と比較して、暗号プログラム３Ｆに、暗号処理および復号処理の開始時に内部のタイマＴを起動するタイマ起動部３２１と、暗号処理および復号処理の終了時にタイマＴのタイマ値が予め設定された暗号処理または復号処理の最大時間Ｔｍａｘより短いかどうかを判定する判定部３２２と、タイマＴのタイマ値が最大時間Ｔｍａｘより短い場合に、その差の時間「Ｔｍａｘ−Ｔ」だけ暗号処理または復号処理の時間を延長するためにウエイトを行うウエイト部３２３とを備えている。ここで、タイマ起動部３２１と判定部３２２とウエイト部３２３とで調整手段を構成する。


【手続補正３０】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
上記の最大時間Ｔｍａｘとしては、例えば、図１８に示したような暗号化時間分布における最大の暗号化時間が用いられる。勿論、その最大の暗号化時間より若干長い時間を設定しても良い。


【手続補正３１】
【補正対象書類名】明細書
【補正対象項目名】００７１
【補正方法】変更
【補正の内容】
【００７１】
図６の前提装置によれば、１つの平文または１つの暗号文の暗号処理または復号処理における暗号処理時間および復号処理時間が、任意の平文または暗号文についてほぼ均一化するため、図１８の暗号化時間分布が最大の暗号化時間の箇所に集中する。このため、キャッシュ攻撃型暗号解読法による攻撃を防御することができる。


【手続補正３２】
【補正対象書類名】明細書
【補正対象項目名】００７２
【補正方法】変更
【補正の内容】
【００７２】
さて、図７を参照すると、本発明の第６の実施の形態にかかる暗号装置は、図６の前提装置と比較して、暗号プログラム３Ｇに、ウエイト部３２３に代えて、予め定められた一定時間Ｔｃだけウエイトを行うウエイト部３２４を備えている。ここで、一定時間Ｔｃとしては、例えば、図１８に示したような暗号化時間分布における最大暗号時間の半分の時間を用いる。勿論、それより若干長い時間、短い時間を設定しても良い。ここで、タイマ起動部３２１と判定部３２２とウエイト部３２４とで調整手段を構成する。


【手続補正３３】
【補正対象書類名】明細書
【補正対象項目名】００７３
【補正方法】変更
【補正の内容】
【００７３】
本実施の形態の暗号装置によれば、図１８に示した暗号化時間分布の中央部分の山が最大の暗号時間の箇所に移動し、真に最大暗号時間を与えた平文に混合される。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となる。その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。


【手続補正３４】
【補正対象書類名】明細書
【補正対象項目名】００７４
【補正方法】変更
【補正の内容】
【００７４】
【発明の第７の実施の形態】
図８を参照すると、本発明の第７の実施の形態にかかる暗号装置は、図７の第６の実施の形態の暗号装置と比較して、暗号プログラム３Ｈに、ウエイト部３２４に代えて、０か１の何れかの値をとる乱数ｒを無作為に生成する乱数生成部３２５、生成した乱数ｒが０か否かを判定する判定部３２６、乱数ｒが０の場合に、ウエイト時間ｔを乱数によって生成するウエイト時間生成部３２７、生成されたウエイト時間ｔだけウエイトを行うウエイト部３２８を備えている。ここで、タイマ起動部３２１と判定部３２２、３２６と、乱数生成部３２５とウエイト時間生成部３２７とウエイト部３２８とで調整手段を構成する。ウエイト時間生成部３２７は、図１８に示したような暗号化時間分布におけるほぼ最大暗号時間から時間０の範囲内で、ウエイト時間ｔを無作為に生成する。


【手続補正３５】
【補正対象書類名】明細書
【補正対象項目名】００７５
【補正方法】変更
【補正の内容】
【００７５】
本実施の形態の暗号装置によれば、図１８に示した暗号化時間分布の特性が不定なものとなり、真に最大暗号時間を与えた平文とそれ以外の平文とが同じ暗号時間帯に出現する。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となり、その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。


【手続補正３６】
【補正対象書類名】明細書
【補正対象項目名】００７６
【補正方法】変更
【補正の内容】
【００７６】
【発明の第８の実施の形態】
図９を参照すると、本発明の第８の実施の形態にかかる暗号装置は、図１３の従来の暗号装置と比較して、暗号プログラム３Ｉに、０か１の何れかの値をとる乱数ｒを無作為に生成する乱数生成部３３１、生成した乱数ｒが０か否かを判定する判定部３３２、乱数ｒが０の場合に、予め定められた一定時間Ｔｃだけウエイトを行うウエイト部３３３を備えている。ここで、乱数生成部３３１と判定部３３２とウエイト部３３３とで調整手段を構成する。一定時間Ｔｃとしては、例えば、図１８に示したような暗号化時間分布における最大暗号時間の半分の時間を用いる。勿論、それより若干長い時間、短い時間を設定しても良い。


【手続補正３７】
【補正対象書類名】明細書
【補正対象項目名】００７７
【補正方法】変更
【補正の内容】
【００７７】
本実施の形態の暗号装置によれば、図１８に示した暗号化時間分布の特性が不定なものとなり、真に最大暗号時間を与えた平文は同じ暗号時間に揃わず、また、それ以外の平文と同じ暗号時間帯に出現する。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となり、その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。


【手続補正３８】
【補正対象書類名】明細書
【補正対象項目名】００７９
【補正方法】変更
【補正の内容】
【００７９】
【発明の第９の実施の形態】
図１０を参照すると、本発明の第９の実施の形態にかかる暗号装置は、図１３の従来の暗号装置と比較して、暗号プログラム３Ｊに、ウエイト時間ｔを乱数によって生成するウエイト時間生成部３３４、生成されたウエイト時間ｔだけウエイトを行うウエイト部３３５を備えている。ここで、ウエイト時間生成部３３４とウエイト部３３５とで調整手段を構成する。ウエイト時間生成部３３４は、図１８に示したような暗号化時間分布におけるほぼ最大暗号時間から時間０の範囲内で、ウエイト時間ｔを無作為に生成する。


【手続補正３９】
【補正対象書類名】明細書
【補正対象項目名】００８０
【補正方法】変更
【補正の内容】
【００８０】
本実施の形態の暗号装置によれば、図１８に示した暗号化時間分布の特性が不定なものとなり、真に最大暗号時間を与えた平文は同じ暗号時間に揃わず、また、それ以外の平文と同じ暗号時間帯に出現する。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となり、その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。


【手続補正４０】
【補正対象書類名】明細書
【補正対象項目名】００８２
【補正方法】変更
【補正の内容】
【００８２】
【発明の第１０の実施の形態】
図１１を参照すると、本発明の第１０の実施の形態にかかる暗号装置は、図１０の第９の実施の形態の暗号装置と比較して、暗号プログラム３Ｋに、０か１の何れかの値をとる乱数ｒを無作為に生成する乱数生成部３３６と生成した乱数ｒが０か否かを判定する判定部３３７とが追加され、ウエイト時間ｔを乱数によって生成するウエイト時間生成部３３４および生成されたウエイト時間ｔだけウエイトを行うウエイト部３３５は、０の乱数ｒが生成された場合に限って動作する。ここで、乱数生成部３３６と判定部３３７とウエイト時間生成部３３４とウエイト部３３５とで調整手段を構成する。ウエイト時間生成部３３４が生成するウエイト時間ｔは、例えば、図１８に示したような暗号化時間分布におけるほぼ最大暗号時間から時間０の範囲内で無作為に生成される。


【手続補正４１】
【補正対象書類名】明細書
【補正対象項目名】００８３
【補正方法】変更
【補正の内容】
【００８３】
本実施の形態の暗号装置によれば、図１８に示した暗号化時間分布の特性が不定なものとなり、真に最大暗号時間を与えた平文は同じ暗号時間に揃わず、また、それ以外の平文と同じ暗号時間帯に出現する。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となり、その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。


【手続補正４２】
【補正対象書類名】明細書
【補正対象項目名】００８５
【補正方法】削除
【補正の内容】
【手続補正４３】
【補正対象書類名】明細書
【補正対象項目名】００８６
【補正方法】削除
【補正の内容】
【手続補正４４】
【補正対象書類名】明細書
【補正対象項目名】００８７
【補正方法】削除
【補正の内容】
【手続補正４５】
【補正対象書類名】明細書
【補正対象項目名】図面の簡単な説明
【補正方法】変更
【補正の内容】
【図面の簡単な説明】
【図１】本発明の第１の実施の形態にかかる暗号装置の構成図である。
【図２】本発明の第２の実施の形態にかかる暗号装置の構成図である。
【図３】本発明の第３の実施の形態にかかる暗号装置の構成図である。
【図４】本発明の第４の実施の形態にかかる暗号装置の構成図である。
【図５】本発明の第５の実施の形態にかかる暗号装置の構成図である。
【図６】本発明の第６の実施の形態にかかる暗号装置の前提となる装置の構成図である。
【図７】本発明の第６の実施の形態にかかる暗号装置の構成図である。
【図８】本発明の第７の実施の形態にかかる暗号装置の構成図である。
【図９】本発明の第８の実施の形態にかかる暗号装置の構成図である。
【図１０】本発明の第９の実施の形態にかかる暗号装置の構成図である。
【図１１】本発明の第１０の実施の形態にかかる暗号装置の構成図である。
【図１２】換字テーブルの構成例を示す図である。
【図１３】従来の暗号装置の構成図である。
【図１４】キャッシュ攻撃型暗号解読法の原理説明図である。
【図１５】キャッシュ攻撃型暗号解読法による鍵差分値の決定方法の説明図である。
【図１６】ＭＩＳＴＹ１のデータランダム化部の構成を示す図である。
【図１７】ＭＩＳＴＹ１のデータランダム化部で使用されるＦＯｉ関数と、さらにこのＦＯｉ関数で使用されるＦＩｉｊ関数の構成を示す図である。
【図１８】暗号化時間分布を示す図である。
【図１９】ＭＩＳＴＹ１で使われる換字テーブルＳ９の動作エントリ数と暗号化時間との関係を示す図である。
【図２０】ＭＩＳＴＹ１で使われる換字テーブルＳ７の動作エントリ数と暗号化時間との関係を示す図である。
【図２１】暗号過程で換字テーブルＳ９の全エントリがほぼ参照される可能性の高い平文の集合を抽出する処理例を示すフローチャートである。
【符号の説明】
１…ＣＰＵ
２…メモリ（主記憶）
３、３Ａ〜３Ｋ…暗号プログラム
４…キャッシュ
５…プロセッサバス
６…メモリバス


【手続補正４６】
【補正対象書類名】図面
【補正対象項目名】図１２
【補正方法】変更
【補正の内容】
【図１２】
2004120307.tif 000025
【手続補正４７】
【補正対象書類名】図面
【補正対象項目名】図１３
【補正方法】変更
【補正の内容】
【図１３】
2004120307.tif 000026
【手続補正４８】
【補正対象書類名】図面
【補正対象項目名】図１４
【補正方法】変更
【補正の内容】
【図１４】
2004120307.tif 000027
【手続補正４９】
【補正対象書類名】図面
【補正対象項目名】図１５
【補正方法】変更
【補正の内容】
【図１５】
2004120307.tif 000028
【手続補正５０】
【補正対象書類名】図面
【補正対象項目名】図１６
【補正方法】変更
【補正の内容】
【図１６】
2004120307.tif 000029
【手続補正５１】
【補正対象書類名】図面
【補正対象項目名】図１７
【補正方法】変更
【補正の内容】
【図１７】
2004120307.tif 000030
【手続補正５２】
【補正対象書類名】図面
【補正対象項目名】図１８
【補正方法】変更
【補正の内容】
【図１８】
2004120307.tif 000031
【手続補正５３】
【補正対象書類名】図面
【補正対象項目名】図１９
【補正方法】変更
【補正の内容】
【図１９】
2004120307.tif 000032
【手続補正５４】
【補正対象書類名】図面
【補正対象項目名】図２０
【補正方法】変更
【補正の内容】
【図２０】
2004120307.tif 000033
【手続補正５５】
【補正対象書類名】図面
【補正対象項目名】図２１
【補正方法】変更
【補正の内容】
【図２１】
2004120307.tif 000034
【手続補正５６】
【補正対象書類名】図面
【補正対象項目名】図２２
【補正方法】削除
【補正の内容】
【手続補正書】
【提出日】平成15年10月17日(2003.10.17)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を備え、前記調整手段は、暗号処理または復号処理で使用する複数の変換表をキャッシュにプリロードするプリロード手段を備え、前記プリロード手段は、前記複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表を他の変換表より後にプリロードするものであることを特徴とする暗号装置。
【請求項２】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムを、高い優先度の付いたデータほどキャッシュから掃き出され難くすることができるキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を備え、前記調整手段は、暗号処理または復号処理で使用する複数の変換表をキャッシュにプリロードするプリロード手段を備え、前記プリロード手段は、前記複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表は高い優先度を設定してプリロードするものであることを特徴とする暗号装置。
【請求項３】
前記プリロード手段は、１つの平文または１つの暗号文の暗号処理または復号処理において同じ変換表を複数の時点でプリロードするものであることを特徴とする請求項１または２記載の暗号装置。
【請求項４】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を備え、前記調整手段は、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表のエントリのうち暗号処理または復号処理で実際に使用されなかったエントリをアクセスする不使用エントリロード手段とを備えたことを特徴とする暗号装置。
【請求項５】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を備え、前記調整手段は、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表の使用エントリの最大数と暗号処理または復号処理で実際に使用されたエントリ数の差分だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備えたことを特徴とする暗号装置。
【請求項６】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を備え、前記調整手段は、暗号処理または復号処理で変換表のエントリにキャッシュヒットした回数を管理する使用エントリ管理手段と、前記キャッシュヒットした回数だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを備えたことを特徴とする暗号装置。
【請求項７】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を備え、前記調整手段は、暗号処理または復号処理で変換表のエントリにキャッシュヒットする毎にキャッシュミスヒットを発生させる手段を備えたことを特徴とする暗号装置。
【請求項８】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を備え、前記調整手段は、１つの平文または１つの暗号文の暗号処理または復号処理で参照される総回数がｎ回である同一内容の変換表をｎ個備え、各参照毎にそれぞれ異なる変換表を参照させるものであることを特徴とする暗号装置。
【請求項９】
前記調整手段は、暗号処理または復号処理で使用する複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表のみを調整対象とすることを特徴とする請求項４乃至８の何れか１項に記載の暗号装置。
【請求項１０】
攻撃対象とされる可能性の高い変換表には、エントリ総数に対する参照総エントリ数の比である利用率が小さな変換表を含むことを特徴とする請求項９記載の暗号装置。
【請求項１１】
ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の実質的な暗号処理または復号処理に要した時間を計測する計測手段と、計測された時間が予め設定された時間より短い場合、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段とを含む調整手段を備えたことを特徴とする暗号装置。
【請求項１２】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、暗号処理または復号処理で使用する複数の変換表をキャッシュにプリロードする際に攻撃対象とされる可能性の高いものとして設定された変換表を他の変換表より後にプリロードするプリロード手段を備え、１つの平文または１つの暗号文の暗号処理または復号処理における前記攻撃対象とされる可能性の高いものとして設定された変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項１３】
高い優先度の付いたデータほどキャッシュから掃き出され難くすることができるキャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、暗号処理または復号処理で使用する複数の変換表をキャッシュにプリロードする際に攻撃対象とされる可能性の高いものとして設定された変換表は高い優先度を設定してプリロードするプリロード手段を備え、１つの平文または１つの暗号文の暗号処理または復号処理における前記攻撃対象とされる可能性の高いものとして設定された前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項１４】
前記プリロード手段は、１つの平文または１つの暗号文の暗号処理または復号処理において同じ変換表を複数の時点でプリロードするものであることを特徴とする請求項１２または１３記載の暗号プログラム。
【請求項１５】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表のエントリのうち暗号処理または復号処理で実際に使用されなかったエントリをアクセスする不使用エントリロード手段とを含み、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項１６】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、変換表のエントリのうち暗号処理または復号処理で実際に使用されたエントリを管理する使用エントリ管理手段と、変換表の使用エントリの最大数と暗号処理または復号処理で実際に使用されたエントリ数の差分だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを含み、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項１７】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、暗号処理または復号処理で変換表のエントリにキャッシュヒットした回数を管理する使用エントリ管理手段と、前記キャッシュヒットした回数だけキャッシュミスヒットを発生させるキャッシュミスヒット発生手段とを含み、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項１８】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、暗号処理または復号処理で変換表のエントリにキャッシュヒットする毎にキャッシュミスヒットを発生させる手段を含み、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項１９】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、１つの平文または１つの暗号文の暗号処理または復号処理で参照される総回数がｎ回である同一内容の変換表をｎ個備え、各参照毎にそれぞれ異なる変換表を参照させることにより、１つの平文または１つの暗号文の暗号処理または復号処理における前記変換表に対するアクセス時のキャッシュミスヒット回数を、任意の平文または暗号文についてキャッシュミスヒット回数が増加する方向に調整してほぼ均一化する調整手段を有する暗号装置として機能させるための暗号プログラム。
【請求項２０】
前記調整手段は、暗号処理または復号処理で使用する複数の変換表のうち攻撃対象とされる可能性の高いものとして設定された変換表のみを調整対象とすることを特徴とする請求項１５乃至１９の何れか１項に記載の暗号プログラム。
【請求項２１】
攻撃対象とされる可能性の高い変換表には、エントリ総数に対する参照総エントリ数の比である利用率が小さな変換表を含むことを特徴とする請求項２０記載の暗号プログラム。
【請求項２２】
キャッシュ装備のコンピュータを、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号装置であって、１つの平文または１つの暗号文の実質的な暗号処理または復号処理に要した時間を計測する計測手段と、計測された時間が予め設定された時間より短い場合、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段とを含む調整手段を有する暗号装置として機能させるための暗号プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
図９に換字テーブルの簡単な例を示す。この例の換字テーブルは１６個のエントリを有し、各エントリに１６進数で０からＦの番地が振られており、各エントリに０からＦの値が格納されている。左上のエントリを０番地とし、右方向に１、２、３番地を割振り、２段目は左から右に４、５、６、７番地を、３段目は同じく左から右に８、９、Ａ、Ｂ番地を、４段目は同じく左から右にＣ、Ｄ、Ｅ、Ｆ番地を割振るものとすると、例えば、入力ビットが００００（１６進数で０）の場合、０番地のエントリに格納されている１６進数で８の値が読み出され、２進数で表現した１０００が出力される。このような換字テーブルを使用すると、換字テーブルを交換するだけで異なる暗号変換を実施でき、秘匿通信の柔軟性が向上する等の利点がある。


【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
図１０は従来の暗号装置のブロック図である。図１０において、１はＣＰＵ（演算装置）、２はメモリ（主記憶）、３は暗号プログラム、４はキャッシュであり、ＣＰＵ１とキャッシュ４との間はデータ線、アドレス線および制御線を含むプロセッサバス５によって接続され、キャッシュ４とメモリ２との間は、同じくデータ線、アドレス線および制御線を含むメモリバス６によって接続されている。周知のようにキャッシュ４は、メモリ２よりも高速アクセス可能な小容量のメモリであり、メモリ２の内容の一部の写しを保持する。ＣＰＵ１がプロセッサバス５を通じて要求する命令やデータがキャッシュ４に存在すれば（これをキャッシュヒットと呼ぶ）、キャッシュ４はキャッシュヒットした命令やデータを直ちにＣＰＵ１に返却する。他方、ＣＰＵ１が要求する命令やデータがキャッシュ４に存在しなければ（これをキャッシュミスヒットと呼ぶ）、キャッシュ４はミスヒットした命令やデータを含む所定サイズのデータをメモリバス６を通じてメモリ２から読み出して自身に格納すると共にＣＰＵ１に該当する命令やデータを返却する。ここで、所定サイズのデータとは、例えば３２バイト、１２８バイトといったサイズである。このようなサイズでキャッシュ４に読み込んでおくことにより、命令が実行される場合には実行アドレスが近い命令が続けて実行されることが多いという原理（命令の局所性の原理）により、キャッシュヒット率を高めることができ、高速化が可能となる。


【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
暗号プログラム３は、前述したＤＥＳ暗号やＦＥＡＬ暗号などの共通鍵暗号を実現するプログラムであり、通常は図示しない磁気ディスク等の補助記憶装置に格納されており、使用時に図１０に示すようにメモリ２にロードされて実行される。図１０のメモリ２のブロックの右に記載した構成図は、１つの平文を暗号化する際の暗号プログラム３の処理の内容を示している。


【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
【発明が解決しようとする課題】
本発明者は、換字テーブルを用いて暗号化を行う図１０に示したような暗号装置の安全性を研究する過程で、新たな暗号解読法を見出した。以下、この新たな暗号解読法をキャッシュ攻撃型暗号解読法と呼び、その解読方法について説明する。


【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
今、図１１に示すように、平文Ｐ０と鍵ｋ０の排他的論理和で換字テーブルＳを引いた出力値と、平文Ｐ１と鍵ｋ１の排他的論理和で同じ換字テーブルＳを引いた出力値とを暗号文とする暗号器を考えてみる。そして、双方で換字テーブルＳのそれぞれ異なるエントリを引いたものとする。このとき、次式が成り立つ。
Ｐ０○ｋ０≠Ｐ１○ｋ１
Ｐ０○Ｐ１≠ｋ０○ｋ１＝Δｋ
…（１）
ここで、記号○は排他的論理和を示し、鍵ｋ０、ｋ１のビット数はｎである。また、Δｋを鍵差分と呼ぶ。


【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
式（２）は、暗号過程（または復号過程）で換字テーブルＳをｎ回引く場面がある場合に、全ての場面で換字テーブルＳの異なるエントリを引くこととなる任意の２つの平文Ｐｉと平文Ｐｊの排他的論理和は鍵差分Δｋｉｊに一致せず、且つ、任意の２つの鍵はその鍵差分がΔｋｉｊとなる関係にあることを意味する。このような鍵差分Δｋｉｊが求まれば、鍵探索の範囲は２２Ｎから２Ｎに狭まる。例えば、図１１においてｋ０〇ｋ１＝ΔｋのＮビットが求まれば、ｋ０のＮビットを全数探査すればｋ１＝ｋ０〇Δｋで他方のＮビットのｋ１が計算できるからである。これにより、ｋ０とｋ１の２Ｎビットの全数探査が、ｋ０のみのＮビットの全数探査で済むようになる。


【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
鍵差分Δｋｉｊは、例えば以下のようにして求めることができる。先ず、図１２（ａ）に示すように、鍵差分Δｋｉｊの取りうる全ての値毎に初期値として値０のカウンタを設定したテーブルを用意する。次に、暗号過程の全場面で換字テーブルＳの異なるエントリを引く多数の平文の集合から任意のペアを抽出し、そのペアの排他的論理和の値と一致する鍵差分Δｋｉｊに対応するカウンタを＋１する処理を、全てのペアについて繰り返す。この結果、カウンタの値は図１２（ｂ）に示すように更新されていき、初期値０のまま或いは極めて小さな値（この値は式（２）の成立確率に依存する）になっているカウンタに対応する鍵差分Δｋｉｊの値が求める鍵差分となる。


【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
図１０で説明したように、キャッシュ４を備えるコンピュータで暗号プログラム３を実行すると、ＣＰＵ１の処理速度が一定で、他のプログラムが実行されていない理想的な環境下でも、与える平文（または暗号文）によって暗号化処理時間（または復号時間）が相違する。その理由は、与える平文が異なれば、換字テーブル（Ｓ）３０５の使用するエントリが異なる場合があり、換字テーブル３０５アクセス時のキャッシュヒット率が相違するからである。つまり、キャッシュミスヒットが最も多くなる平文の暗号処理時間が最も長くなる。キャッシュミスヒットが最も多くなる平文は、換字テーブルＳを引く全場面（もしくは、かなり多くの場面）で異なるエントリを引いている可能性があると推測される。


【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
本発明者は、この推測の正しさを、既知の暗号アルゴリズムを用いて検証した。検証に使用した暗号アルゴリズムは、１９９６年に三菱電気株式会社によって提案されたＭＩＳＴＹ１という、６４ビットのブロック暗号（鍵長は１２８ビット）である。図１３にＭＩＳＴＹ１のデータランダム化部の構成を示し、図１４にデータランダム化部で使用されるＦＯｉ関数と、さらにこのＦＯｉ関数で使用されるＦＩｉｊ関数の構成を示す。ＦＯｉ関数は合計８個あり、１つのＦＯｉ関数の中に３個のＦＩｉｊ関数があり、１つのＦＩｉｊ関数の中で換字テーブルＳ９が２回使用され、換字テーブルＳ７が１回使用されている。つまり、暗号化の過程で、換字テーブルＳ９は、８×３×２＝４８回使用され、換字テーブルＳ７は８×３×１＝２４回使用される。換字テーブルＳ９は入力が９ビットで、５１２のエントリ（サンプルプログラムでは１エントリのサイズは３２ビットで記述されていた）を有し、換字テーブルＳ７は入力が７ビットで、１２８のエントリ（サンプルプログラムでは１エントリのサイズは８ビットで記述されていた）を有する。


【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
図１５は、ＭＩＳＴＹ１で多数の平文を暗号化したときの暗号化時間の分布を示し、横軸は暗号化時間、縦軸は平文数である。また、図１６は、暗号化時間と変換テーブルＳ９の動作エントリ数の関係を示し、図１７は、暗号化時間と変換テーブルＳ７の動作エントリ数の関係を示す。ここで、動作エントリ数とは、変換テーブルのエントリの内、幾つのエントリが暗号化処理で使用されたかを示し、変換テーブルＳ９の最大値は４８、変換テーブルＳ７の最大値は２４である。図１５および図１６から理解されるように、暗号処理時間が或るしきい値Ｔ以上かかる平文は、換字テーブルＳ９を引く殆どの場面で異なるエントリを引いており、毎回キャッシュミスヒットを起こしているために暗号処理時間が長くなっている。これに対し、変換テーブルＳ７は、動作エントリ数にかかわらず暗号処理時間はほぼ一定である。変換テーブルＳ９とＳ７とでこのような差違が生じる理由は、変換テーブルＳ７は１２８エントリと小型のテーブルであるため、何回かミスヒットするとキャッシュ４にテーブルの大部分のエントリがロードされて、その後ミスヒットが発生しなくなるのに対し、変換テーブルＳ９は５１２エントリと大型のテーブルであるため、そのような状況が発生しないためと考えられる。従って、図１１および図１２で説明した原理による攻撃は、換字テーブルＳ７に対しては余り効果がなく、換字テーブルＳ９が攻撃対象となる。


【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
図１８は、暗号過程で換字テーブルＳ９をほぼ４８回引く可能性が高い平文の集合を抽出する処理の一例を示す。先ず、ＭＩＳＴＹ１の暗号プログラムをコンピュータのメモリにロードする（ステップ１０１）。次に、乱数によって平文を生成し（ステップ１０２）、コンピュータのキャッシュをクリアし（ステップ１０３）、前記生成した平文を暗号化対象の平文に設定して（ステップ１０４）、ＭＩＳＴＹ１による暗号化とこの暗号化の処理に要した時間の測定とを行う（ステップ１０５）。次に、測定した暗号化時間が予め設定したしきい値Ｔ以上であるかどうかを判定する（ステップ１０６）。ここで、しきい値Ｔは図１５および図１６のＴで示される暗号化時間を使用する。しきい値Ｔは、解読が成立するのに必要充分な数の平文が得られるように設定する。因みに、式（２）の成立確率が高いほど少ない数の平文で足りる。そして、暗号化時間がしきい値Ｔ以上であれば、今回の平文を保存し（ステップ１０７）、ステップ１０２に戻って上述した処理を繰り返す。暗号化時間がしきい値Ｔ以上でなければ、今回の平文を保存せずにステップ１０２に戻って上述した処理を繰り返す。このような処理の繰り返しによって、暗号過程で換字テーブルＳ９をほぼ４８回引く可能性が高い平文を充分な数だけ抽出することができる。


【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
こうして抽出した平文の集合を用いて、図１２で示したような方法で鍵差分Δｋを決定し、鍵の候補を絞り込む。そして、最終的には、確定しなかった鍵のビット部分について総当りによってビット値を確定することにより、秘密鍵の全ビットを特定する。


【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
第３の観点に基づく本発明の暗号装置は、ビット列変換に使用する変換表を用いて暗号処理または復号処理を行う暗号プログラムをキャッシュ装備のコンピュータに実装した暗号装置において、１つの平文または１つの暗号文の実質的な暗号処理または復号処理に要した時間を計測する計測手段と、計測された時間が予め設定された時間より短い場合、予め設定された一定時間または無作為に決定した時間だけ暗号処理または復号処理に要する時間を常に或いは無作為に延長する延長手段とを含む調整手段を備えたことを特徴とする。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００４０
【補正方法】変更
【補正の内容】
【００４０】
プリロード対象とする換字テーブル３０５は、本実施の形態の場合、暗号処理または復号処理で使用する全ての換字テーブルのうち、キャッシュ攻撃暗号解読法で攻撃される可能性の高い換字テーブルである。攻撃対象とされる可能性の高い換字テーブルは、当該暗号プログラムのアルゴリズムに照らして事前に決定され、暗号プログラム３Ａに設定されている。図１３および図１４で説明したＭＩＳＴＹ１の場合、変換テーブルＳ９が設定される。一般的に、図１６で示されるように、暗号時間が長くなるのに応じて動作エントリ数が増加する傾向を示す換字テーブルが攻撃対象とされる可能性が高い。また、簡便な方法として、エントリ総数に対する参照総エントリ数（動作エントリ数）の比である利用率が小さい変換表を、攻撃対象とされる可能性の高い換字テーブルとして決定する方法を用いることができる。


【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
次に本実施の形態の効果を説明する。今、攻撃対象とされる可能性の高い換字テーブルとして、ＭＩＳＴＹ１の換字テーブルＳ９を考える。この換字テーブルＳ９のエントリ総数は５１２、１文の暗号化または復号化で動作するエントリ数（最大動作エントリ数）は４８である。図１８で説明したように攻撃者は、暗号プログラム３Ｂの起動前に換字テーブルＳ９をクリアするため、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最大値は４８になる。また、実際上は出現しないかも知れないが、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最小数を１とする。


【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
次に本実施の形態の効果を説明する。今、攻撃対象とされる可能性の高い換字テーブルとして、ＭＩＳＴＹ１の換字テーブルＳ９を考える。この換字テーブルＳ９のエントリ総数は５１２、最大動作エントリ数は４８である。図１８で説明したように攻撃者は、暗号プログラム３Ｃの起動前に換字テーブルＳ９をクリアするため、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最大値は４８である。また、最小数は第２の実施の形態と同様に１を想定する。


【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
次に本実施の形態の効果を説明する。今、攻撃対象とされる可能性の高い換字テーブルとして、ＭＩＳＴＹ１の換字テーブルＳ９を考える。この換字テーブルＳ９のエントリ総数は５１２、最大動作エントリ数は４８である。図１８で説明したように攻撃者は、暗号プログラム３Ｄの起動前に換字テーブルＳ９をクリアするため、１つの平文を暗号化する際の換字テーブルＳ９のキャッシュミスヒット回数の最大値は４８である。また、最小数は第２の実施の形態と同様に１を想定する。


【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
【発明の第５の実施の形態】
図５を参照すると、本発明の第５の実施の形態にかかる暗号装置は、図１０に示した従来の暗号装置と比較して、暗号プログラム３Ｅは、換字テーブル３０５が１つの平文または１つの暗号文の暗号処理または復号処理でｎ回参照される場合に、換字テーブル３０５と同じ内容を持つｎ個の換字テーブル３０５−１〜３０５−ｎを備え、データ変換部３０４は、１つの平文または１つの暗号文の暗号処理または復号処理において換字テーブル３０５を参照する場合、各参照毎にそれぞれ異なる換字テーブル３０５−１〜３０５−ｎを参照するように構成される点で相違する。


【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】００６９
【補正方法】変更
【補正の内容】
【００６９】
【発明の第６の実施の形態】
図６を参照すると、本発明の第６の実施の形態にかかる暗号装置の前提となる装置は、図１０の従来の暗号装置と比較して、暗号プログラム３Ｆに、暗号処理および復号処理の開始時に内部のタイマＴを起動するタイマ起動部３２１と、暗号処理および復号処理の終了時にタイマＴのタイマ値が予め設定された暗号処理または復号処理の最大時間Ｔｍａｘより短いかどうかを判定する判定部３２２と、タイマＴのタイマ値が最大時間Ｔｍａｘより短い場合に、その差の時間「Ｔｍａｘ−Ｔ」だけ暗号処理または復号処理の時間を延長するためにウエイトを行うウエイト部３２３とを備えている。ここで、タイマ起動部３２１と判定部３２２とウエイト部３２３とで調整手段を構成する。


【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
上記の最大時間Ｔｍａｘとしては、例えば、図１５に示したような暗号化時間分布における最大の暗号化時間が用いられる。勿論、その最大の暗号化時間より若干長い時間を設定しても良い。


【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】００７１
【補正方法】変更
【補正の内容】
【００７１】
図６の前提装置によれば、１つの平文または１つの暗号文の暗号処理または復号処理における暗号処理時間および復号処理時間が、任意の平文または暗号文についてほぼ均一化するため、図１５の暗号化時間分布が最大の暗号化時間の箇所に集中する。このため、キャッシュ攻撃型暗号解読法による攻撃を防御することができる。


【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】００７２
【補正方法】変更
【補正の内容】
【００７２】
さて、図７を参照すると、本発明の第６の実施の形態にかかる暗号装置は、図６の前提装置と比較して、暗号プログラム３Ｇに、ウエイト部３２３に代えて、予め定められた一定時間Ｔｃだけウエイトを行うウエイト部３２４を備えている。ここで、一定時間Ｔｃとしては、例えば、図１５に示したような暗号化時間分布における最大暗号時間の半分の時間を用いる。勿論、それより若干長い時間、短い時間を設定しても良い。ここで、タイマ起動部３２１と判定部３２２とウエイト部３２４とで調整手段を構成する。


【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】００７３
【補正方法】変更
【補正の内容】
【００７３】
本実施の形態の暗号装置によれば、図１５に示した暗号化時間分布の中央部分の山が最大の暗号時間の箇所に移動し、真に最大暗号時間を与えた平文に混合される。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となる。その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。


【手続補正２５】
【補正対象書類名】明細書
【補正対象項目名】００７４
【補正方法】変更
【補正の内容】
【００７４】
【発明の第７の実施の形態】
図８を参照すると、本発明の第７の実施の形態にかかる暗号装置は、図７の第６の実施の形態の暗号装置と比較して、暗号プログラム３Ｈに、ウエイト部３２４に代えて、０か１の何れかの値をとる乱数ｒを無作為に生成する乱数生成部３２５、生成した乱数ｒが０か否かを判定する判定部３２６、乱数ｒが０の場合に、ウエイト時間ｔを乱数によって生成するウエイト時間生成部３２７、生成されたウエイト時間ｔだけウエイトを行うウエイト部３２８を備えている。ここで、タイマ起動部３２１と判定部３２２、３２６と、乱数生成部３２５とウエイト時間生成部３２７とウエイト部３２８とで調整手段を構成する。ウエイト時間生成部３２７は、図１５に示したような暗号化時間分布におけるほぼ最大暗号時間から時間０の範囲内で、ウエイト時間ｔを無作為に生成する。


【手続補正２６】
【補正対象書類名】明細書
【補正対象項目名】００７５
【補正方法】変更
【補正の内容】
【００７５】
本実施の形態の暗号装置によれば、図１５に示した暗号化時間分布の特性が不定なものとなり、真に最大暗号時間を与えた平文とそれ以外の平文とが同じ暗号時間帯に出現する。このため、キャッシュ型攻撃暗号解読法の要である鍵差分を抽出する際に用いる平文の抽出が困難となり、その結果、鍵差分を決定できず、結果として鍵の解読が困難となる。


【手続補正２７】
【補正対象書類名】明細書
【補正対象項目名】００７６
【補正方法】削除
【補正の内容】
【手続補正２８】
【補正対象書類名】明細書
【補正対象項目名】００７７
【補正方法】削除
【補正の内容】
【手続補正２９】
【補正対象書類名】明細書
【補正対象項目名】００７８
【補正方法】削除
【補正の内容】
【手続補正３０】
【補正対象書類名】明細書
【補正対象項目名】００７９
【補正方法】削除
【補正の内容】
【手続補正３１】
【補正対象書類名】明細書
【補正対象項目名】００８０
【補正方法】削除
【補正の内容】
【手続補正３２】
【補正対象書類名】明細書
【補正対象項目名】００８１
【補正方法】削除
【補正の内容】
【手続補正３３】
【補正対象書類名】明細書
【補正対象項目名】００８２
【補正方法】削除
【補正の内容】
【手続補正３４】
【補正対象書類名】明細書
【補正対象項目名】００８３
【補正方法】削除
【補正の内容】
【手続補正３５】
【補正対象書類名】明細書
【補正対象項目名】００８４
【補正方法】削除
【補正の内容】
【手続補正３６】
【補正対象書類名】明細書
【補正対象項目名】図面の簡単な説明
【補正方法】変更
【補正の内容】
【図面の簡単な説明】
【図１】本発明の第１の実施の形態にかかる暗号装置の構成図である。
【図２】本発明の第２の実施の形態にかかる暗号装置の構成図である。
【図３】本発明の第３の実施の形態にかかる暗号装置の構成図である。
【図４】本発明の第４の実施の形態にかかる暗号装置の構成図である。
【図５】本発明の第５の実施の形態にかかる暗号装置の構成図である。
【図６】本発明の第６の実施の形態にかかる暗号装置の前提となる装置の構成図である。
【図７】本発明の第６の実施の形態にかかる暗号装置の構成図である。
【図８】本発明の第７の実施の形態にかかる暗号装置の構成図である。
【図９】換字テーブルの構成例を示す図である。
【図１０】従来の暗号装置の構成図である。
【図１１】キャッシュ攻撃型暗号解読法の原理説明図である。
【図１２】キャッシュ攻撃型暗号解読法による鍵差分値の決定方法の説明図である。
【図１３】ＭＩＳＴＹ１のデータランダム化部の構成を示す図である。
【図１４】ＭＩＳＴＹ１のデータランダム化部で使用されるＦＯｉ関数と、さらにこのＦＯｉ関数で使用されるＦＩｉｊ関数の構成を示す図である。
【図１５】暗号化時間分布を示す図である。
【図１６】ＭＩＳＴＹ１で使われる換字テーブルＳ９の動作エントリ数と暗号化時間との関係を示す図である。
【図１７】ＭＩＳＴＹ１で使われる換字テーブルＳ７の動作エントリ数と暗号化時間との関係を示す図である。
【図１８】暗号過程で換字テーブルＳ９の全エントリがほぼ参照される可能性の高い平文の集合を抽出する処理例を示すフローチャートである。
【符号の説明】
１…ＣＰＵ
２…メモリ（主記憶）
３、３Ａ〜３Ｋ…暗号プログラム
４…キャッシュ
５…プロセッサバス
６…メモリバス


【手続補正３７】
【補正対象書類名】図面
【補正対象項目名】図９
【補正方法】変更
【補正の内容】
【図９】
2004120307.tif 000035
【手続補正３８】
【補正対象書類名】図面
【補正対象項目名】図１０
【補正方法】変更
【補正の内容】
【図１０】
2004120307.tif 000036
【手続補正３９】
【補正対象書類名】図面
【補正対象項目名】図１１
【補正方法】変更
【補正の内容】
【図１１】
2004120307.tif 000037
【手続補正４０】
【補正対象書類名】図面
【補正対象項目名】図１２
【補正方法】変更
【補正の内容】
【図１２】
2004120307.tif 000038
【手続補正４１】
【補正対象書類名】図面
【補正対象項目名】図１３
【補正方法】変更
【補正の内容】
【図１３】
2004120307.tif 000039
【手続補正４２】
【補正対象書類名】図面
【補正対象項目名】図１４
【補正方法】変更
【補正の内容】
【図１４】
2004120307.tif 000040
【手続補正４３】
【補正対象書類名】図面
【補正対象項目名】図１５
【補正方法】変更
【補正の内容】
【図１５】
2004120307.tif 000041
【手続補正４４】
【補正対象書類名】図面
【補正対象項目名】図１６
【補正方法】変更
【補正の内容】
【図１６】
2004120307.tif 000042
【手続補正４５】
【補正対象書類名】図面
【補正対象項目名】図１７
【補正方法】変更
【補正の内容】
【図１７】
2004120307.tif 000043
【手続補正４６】
【補正対象書類名】図面
【補正対象項目名】図１８
【補正方法】変更
【補正の内容】
【図１８】
2004120307.tif 000044
【手続補正４７】
【補正対象書類名】図面
【補正対象項目名】図１９
【補正方法】削除
【補正の内容】
【手続補正４８】
【補正対象書類名】図面
【補正対象項目名】図２０
【補正方法】削除
【補正の内容】
【手続補正４９】
【補正対象書類名】図面
【補正対象項目名】図２１
【補正方法】削除
【補正の内容】