(57)【要約】  高い安全性を持つ暗号処理と高速な暗号処理とを組合せ、大きいブロックサイズのブロック暗号を構築する共通鍵ブロック暗号化装置、その方法、そのプログラム、及び記録媒体を提供する。  大きいブロックサイズのブロック暗号において、ユニバーサルハッシュ関数を用いた置換により平文を処理した後、１ブロック分について高い安全性を持つブロック暗号で暗号化し、このブロック暗号の入力と出力の和を入力とした擬似乱数生成器の出力と残りのブロックとを加算する。最後に、ユニバーサルハッシュ関数を用いた置換を適用する。構成されたブロック暗号は、使用するブロック暗号が選択暗号文攻撃に安全で、かつ擬似乱数生成器が既知平文攻撃に対して安全であれば、選択暗号文攻撃への安全性が保証される。また、大きいブロックサイズにおいてはブロック暗号の速度は問題とならず、擬似乱数生成器とユニバーサルハッシュ関数の速度が主になる。
2008053650.tif 000002
【特許請求の範囲】
【請求項１】
暗号化される平文を、第１のブロックと、第２のブロックと、に分割し、該分割した第１のブロックをハッシュ関数により圧縮し、該圧縮した第１のブロックと、前記第２のブロックと、を加算し単位ブロック中間文を生成し、該生成した単位ブロック中間文と、前記第１のブロックと、を出力する第１のハッシュ手段と、
前記単位ブロック中間文を暗号化し、単位ブロック中間暗号文を生成する単位ブロック暗号化手段と、
前記単位ブロック中間文と、前記単位ブロック中間暗号文と、の和を基に中間乱数を生成する擬似乱数生成手段と、
前記中間乱数と、前記第１のブロックと、を加算し、第１の加算結果を出力する加算手段と、
前記第１の加算結果をハッシュ関数により圧縮し、該圧縮した第１の加算結果及び前記単位ブロック中間暗号文から暗号文を算出する第２のハッシュ手段と、
前記第２のハッシュ手段から出力された暗号文を出力する暗号文出力手段とを有することを特徴とする共通鍵ブロック暗号化装置。
【請求項２】
前記第２のハッシュ手段は、前記単位ブロック中間暗号文をハッシュ関数により置換し、該置換された単位ブロック中間暗号文と、前記圧縮した第１の加算結果と、を加算した第２の加算結果と、前記第１の加算結果と、を連結させ、暗号文として出力することを特徴とする請求項１記載の共通鍵ブロック暗号化装置。
【請求項３】
第１のハッシュ手段は、秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１のブロックを圧縮し、
第２のハッシュ手段は、該秘密鍵の指数倍と、単位ブロック中間暗号文と、の積を算出し、該秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１の加算結果を圧縮し、該算出された積と、該圧縮した第１の加算結果と、を加算して第２の加算結果を算出することを特徴とする請求項２記載の共通鍵ブロック暗号化装置。
【請求項４】
前記単位ブロック暗号化手段は、ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、
前記擬似乱数生成手段は、前記ブロック暗号を簡略化して得られる簡易ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする請求項１から３のいずれか１項記載の共通鍵ブロック暗号化装置。
【請求項５】
前記単位ブロック暗号化手段は、ブロック暗号を複数回組み合わせて得られる強化ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、
前記擬似乱数生成手段は、前記ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする請求項１から３のいずれか１項記載の共通鍵ブロック暗号化装置。
【請求項６】
前記単位ブロック暗号化手段は、ブロック暗号を用いて前記単位ブロック中間平文を前記単位ブロック中間暗号文に変換し、
前記擬似乱数生成手段は、初期ベクトルを付加的な入力として受け付けるストリーム暗号へ、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を初期ベクトルとして入力して得られる鍵ストリームを中間乱数とすることを特徴とする請求項１から３のいずれか１項記載の共通鍵ブロック暗号化装置。
【請求項７】
情報処理装置において行う共通鍵ブロック暗号化方法であって、
暗号化される平文を、第１のブロックと、第２のブロックと、に分割し、該分割した第１のブロックをハッシュ関数により圧縮し、該圧縮した第１のブロックと、前記第２のブロックと、を加算し単位ブロック中間文を生成し、該生成した単位ブロック中間文と、前記第１のブロックと、を出力する第１のハッシュ工程と、
前記単位ブロック中間文を暗号化し、単位ブロック中間暗号文を生成する単位ブロック暗号化工程と、
前記単位ブロック中間文と、前記単位ブロック中間暗号文と、の和を基に中間乱数を生成する擬似乱数生成工程と、
前記中間乱数と、前記第１のブロックと、を加算し、第１の加算結果を出力する加算工程と、
前記第１の加算結果をハッシュ関数により圧縮し、該圧縮した第１の加算結果及び前記単位ブロック中間暗号文から暗号文を算出する第２のハッシュ工程と、
前記第２のハッシュ工程から出力された暗号文を出力する暗号文出力工程とを有することを特徴とする共通鍵ブロック暗号化方法。
【請求項８】
前記第２のハッシュ工程は、前記単位ブロック中間暗号文をハッシュ関数により置換し、該置換された単位ブロック中間暗号文と、前記圧縮した第１の加算結果と、を加算した第２の加算結果と、前記第１の加算結果と、を連結させ、暗号文として出力することを特徴とする請求項７記載の共通鍵ブロック暗号化方法。
【請求項９】
第１のハッシュ工程は、秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１のブロックを圧縮し、
第２のハッシュ工程は、該秘密鍵の指数倍と、単位ブロック中間暗号文と、の積を算出し、該秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１の加算結果を圧縮し、該算出された積と、該圧縮した第１の加算結果と、を加算して第２の加算結果を算出することを特徴とする請求項８記載の共通鍵ブロック暗号化方法。
【請求項１０】
前記単位ブロック暗号化工程は、ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、
前記擬似乱数生成工程は、前記ブロック暗号を簡略化して得られる簡易ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする請求項７から９のいずれか１項記載の共通鍵ブロック暗号化方法。
【請求項１１】
前記単位ブロック暗号化工程は、ブロック暗号を複数回組み合わせて得られる強化ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、
前記擬似乱数生成工程は、前記ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする請求項７から９のいずれか１項記載の共通鍵ブロック暗号化方法。
【請求項１２】
前記単位ブロック暗号化工程は、ブロック暗号を用いて前記単位ブロック中間平文を前記単位ブロック中間暗号文に変換し、
前記擬似乱数生成工程は、初期ベクトルを付加的な入力として受け付けるストリーム暗号へ、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を初期ベクトルとして入力して得られる鍵ストリームを中間乱数とすることを特徴とする請求項７から９のいずれか１項記載の共通鍵ブロック暗号化方法。
【請求項１３】
情報処理装置において実行させる共通鍵ブロック暗号化プログラムであって、
暗号化される平文を、第１のブロックと、第２のブロックと、に分割し、該分割した第１のブロックをハッシュ関数により圧縮し、該圧縮した第１のブロックと、前記第２のブロックと、を加算し単位ブロック中間文を生成し、該生成した単位ブロック中間文と、前記第１のブロックと、を出力する第１のハッシュ処理と、
前記単位ブロック中間文を暗号化し、単位ブロック中間暗号文を生成する単位ブロック暗号化処理と、
前記単位ブロック中間文と、前記単位ブロック中間暗号文と、の和を基に中間乱数を生成する擬似乱数生成処理と、
前記中間乱数と、前記第１のブロックと、を加算し、第１の加算結果を出力する加算処理と、
前記第１の加算結果をハッシュ関数により圧縮し、該圧縮した第１の加算結果及び前記単位ブロック中間暗号文から暗号文を算出する第２のハッシュ処理と、
前記第２のハッシュ処理から出力された暗号文を出力する暗号文出力処理とを有することを特徴とする共通鍵ブロック暗号化プログラム。
【請求項１４】
前記第２のハッシュ処理は、前記単位ブロック中間暗号文をハッシュ関数により置換し、該置換された単位ブロック中間暗号文と、前記圧縮した第１の加算結果と、を加算した第２の加算結果と、前記第１の加算結果と、を連結させ、暗号文として出力することを特徴とする請求項１３記載の共通鍵ブロック暗号化プログラム。
【請求項１５】
第１のハッシュ処理は、秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１のブロックを圧縮し、
第２のハッシュ処理は、該秘密鍵の指数倍と、単位ブロック中間暗号文と、の積を算出し、該秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１の加算結果を圧縮し、該算出された積と、該圧縮した第１の加算結果と、を加算して第２の加算結果を算出することを特徴とする請求項１４記載の共通鍵ブロック暗号化プログラム。
【請求項１６】
前記単位ブロック暗号化処理は、ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、
前記擬似乱数生成処理は、前記ブロック暗号を簡略化して得られる簡易ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする請求項１３から１５のいずれか１項記載の共通鍵ブロック暗号化プログラム。
【請求項１７】
前記単位ブロック暗号化処理は、ブロック暗号を複数回組み合わせて得られる強化ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、
前記擬似乱数生成処理は、前記ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする請求項１３から１５のいずれか１項記載の共通鍵ブロック暗号化プログラム。
【請求項１８】
前記単位ブロック暗号化処理は、ブロック暗号を用いて前記単位ブロック中間平文を前記単位ブロック中間暗号文に変換し、
前記擬似乱数生成処理は、初期ベクトルを付加的な入力として受け付けるストリーム暗号へ、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を初期ベクトルとして入力して得られる鍵ストリームを中間乱数とすることを特徴とする請求項１３から１５のいずれか１項記載の共通鍵ブロック暗号化プログラム。
【請求項１９】
請求項１３から１８のいずれか１項記載の共通鍵ブロック暗号化プログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共通鍵ブロック暗号化装置、その方法、そのプログラム、及び記録媒体に関し、特に、安全性の高い暗号処理と、高速な暗号処理と、の組み合わせを用いて、大きなブロックサイズのブロック暗号を構築する共通鍵ブロック暗号化装置、その方法、そのプログラム、及び記録媒体に関する。
【背景技術】
【０００２】
近年、ブロック暗号やハッシュ関数などの暗号処理を暗号部品とし、新たな暗号を構成するアプローチが数多く知られている。【０００３】
例えば、ファイル暗号では、暗号化データのセクタ単位での処理を容易とするために、標準的なブロックサイズ（１２８bitなど）のブロック暗号を用いて、セクタのサイズに対応した、より大きなブロックサイズ（５１２bitなど）のブロック暗号を構成する研究が行われている。【０００４】
通常、このような暗号部品の組み合わせは、該暗号部品の選択平文攻撃への安全性が、該暗号部品により新たに構成される暗号の十分な安全性を確保するために必要とされてきた。なお、新たに構成される暗号の十分な安全性とは、新たに構成される暗号がブロック暗号の場合には、選択平文攻撃への安全性、もしくは、選択平文攻撃と選択暗号文攻撃を任意に組み合わせた攻撃への安全性を示している。新たに構成される暗号がストリーム暗号の場合には、初期ベクトルを攻撃者が選択できるというモデルにおける選択平文攻撃への安全性を示している。【０００５】
なお、選択平文攻撃又は選択暗号文攻撃に安全な部品のみを用いた方法の場合には、新たに構成されるスループット（単位時間当たりの処理量）が、暗号部品のスループットを上回ることはできない。【０００６】
これに対し、選択平文攻撃又は選択暗号文攻撃に安全な暗号部品のみを用いるのではなく、選択平文攻撃に安全な暗号部品と既知平文攻撃に安全な部品とを組み合わせる方法がある（例えば、特許文献１、非特許文献２参照）。【０００７】
なお、上記特許文献１、上記非特許文献２は、ブロック暗号の出力を、ハッシュ関数やストリーム暗号で拡大することによりストリーム暗号を構成するものである。なお、上記特許文献１には、選択平文攻撃に安全なブロック暗号と、既知平文攻撃に安全なハッシュ関数やストリーム暗号と、を用いれば、新たに構成されるストリーム暗号は安全である旨が記載されている。【０００８】
既知平文攻撃は、選択平文攻撃より弱いクラスの攻撃である。既知平文攻撃に安全な暗号部品は、安全性への要求が低いため、選択平文攻撃や選択暗号文攻撃に安全な暗号部品より高速に動作することが期待できる。さらに、上記特許文献１の手法において、選択平文攻撃に安全なブロック暗号と、既知平文攻撃に安全なハッシュ関数やストリーム暗号と、を用いれば、新たに構成される暗号のスループットを、既知平文攻撃に安全な暗号部品のスループットとほぼ同等にすることが可能となる。【０００９】
また、非特許文献１には、選択平文／暗号文攻撃に安全なブロック暗号と、既知平文攻撃に安全な暗号（必ずしもブロック暗号とは限らない）とを組み合わせ、任意の大きいブロックサイズのブロック暗号を構成する手法が示されている。ここに示されている方法を、nビットブロックの選択暗号文攻撃に安全なブロック暗号Eと、nビットブロックの既知平文攻撃に安全な暗号Fを用いて実現する場合を考える。構成する対象がnmビットブロックサイズの選択平文攻撃に安全なブロック暗号の場合、Eの呼び出し回数は1回、Fの呼び出し回数はm-1回となっている。また構成する対象がnmビットブロックサイズの選択暗号文攻撃に安全なブロック暗号の場合、Eの呼び出し回数は２回、Fの呼び出し回数はm-2回となっている。
【特許文献１】米国特許第６１０４８１１号明細書
【非特許文献１】Kazuhiko Minematsu, Yukiyasu Tsunoo: Hybrid Symmetric Encryption Using Known-Plaintext Attack-Secure Componets. pp. 242-260, Information Security and Cryptology-ICISC 2002, 5th International Conference Seoul, Korea, November 28-29, 2002. Lecture Notes in Computer Science 2587 Springer 2003, ISBN 3-540-00716-4
【非特許文献２】W. Aiello, R. Rajagopalan and V. Venkatesan, High-Speed Pseudorandom Number Generation With Small Memory, Fast Software Encryption, 6th International Workshop, FSE'99, Lecture Notes in Computer Science; Vol. 1636, Mar. 1999
【非特許文献３】IEEE Computer Society Security in Storage Working Group (SISWG), Draft Proposal for Tweakable Wide-block Encryption, http://www.siswg.org/docs/EME-AES-03-22-2004.pdf
【非特許文献４】S. Halevi and H. Krawczyk, MMH:Software Message Authentication in the Gbit/second rates, Fast Software Encryption, 4th Internatioanl Workshop, FSE '97, Lecture Notes in Computer Science; Vol. 1267, Feb. 1997
【非特許文献５】The Poly1305-AES Message Authentication Code, D.J.Bernstein, Fast Software Encryption, FSE 2005, Lecture notes in computer science 3557, pp.32-49, Springer, 2005.
【非特許文献６】J. Daemen, V. Rijmen, "AES Proposal: Rijndael", AES submission, 1998.
【非特許文献７】U. Maurer and Johan Sjoedin, From Known-Plaintext to Chosen- Ciphertext Security, Cryptology ePrint Archive 2006/071, http://eprint.iacr. org/2006/071.pdf
【非特許文献８】P. Rogaway and D. Coppersmith, A Software-Optimized Encryption Algorithm, Fast Software Encryption, 1st InternatioanlWorkshop, FSE '93, Lecture Notes in Computer Science; Vol. 809, Feb. 1993.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかし、上記の発明は以下の問題を有している。【００１１】
上記非特許文献１には、選択暗号文攻撃に安全な大きいブロックサイズのブロック暗号を構成する場合において、ブロック暗号の構成要素である小さいブロックサイズの選択暗号文攻撃に安全なブロック暗号を２回呼び出す必要があり、またそれぞれの鍵も変える必要がある。【００１２】
また、選択暗号文攻撃に安全で、かつブロックサイズが任意の大きさにできるということは非特許文献３でも述べられているように、ディスクセクタ暗号化に望まれる要件でもある。【００１３】
そこで、本発明は、上記事情に鑑みてなされたものであり、選択暗号文攻撃に安全な固定長ブロック暗号Eと、既知平文攻撃に安全な暗号F（必ずしもブロック暗号とは限らない）とを組み合わせ、選択暗号文攻撃に安全な、任意の大きいブロックサイズのブロック暗号を効率よい方法で提供する共通鍵ブロック暗号化装置、その方法、そのプログラム、及び記録媒体を提案することを目的とするものである。具体的には、非特許文献１では、固定長ブロック暗号Eを２回呼び出す必要があるが、本発明は固定長ブロック暗号Eを１回だけ呼び出す。
【課題を解決するための手段】
【００１４】
請求項１記載の共通鍵ブロック暗号化装置は、暗号化される平文を、第１のブロックと、第２のブロックと、に分割し、該分割した第１のブロックをハッシュ関数により圧縮し、該圧縮した第１のブロックと、前記第２のブロックと、を加算し単位ブロック中間文を生成し、該生成した単位ブロック中間文と、前記第１のブロックと、を出力する第１のハッシュ手段と、前記単位ブロック中間文を暗号化し、単位ブロック中間暗号文を生成する単位ブロック暗号化手段と、前記単位ブロック中間文と、前記単位ブロック中間暗号文と、の和を基に中間乱数を生成する擬似乱数生成手段と、前記中間乱数と、前記第１のブロックと、を加算し、第１の加算結果を出力する加算手段と、前記第１の加算結果をハッシュ関数により圧縮し、該圧縮した第１の加算結果及び前記単位ブロック中間暗号文から暗号文を算出する第２のハッシュ手段と、前記第２のハッシュ手段から出力された暗号文を出力する暗号文出力手段とを有することを特徴とする。【００１５】
請求項２記載の発明は、請求項１記載の共通鍵ブロック暗号化装置において、前記第２のハッシュ手段は、前記単位ブロック中間暗号文をハッシュ関数により置換し、該置換された単位ブロック中間暗号文と、前記圧縮した第１の加算結果と、を加算した第２の加算結果と、前記第１の加算結果と、を連結させ、暗号文として出力することを特徴とする。【００１６】
請求項３記載の発明は、請求項２記載の共通鍵ブロック暗号化装置において、第１のハッシュ手段は、秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１のブロックを圧縮し、第２のハッシュ手段は、該秘密鍵の指数倍と、単位ブロック中間暗号文と、の積を算出し、該秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１の加算結果を圧縮し、該算出された積と、該圧縮した第１の加算結果と、を加算して第２の加算結果を算出することを特徴とする。【００１７】
請求項４記載の発明は、請求項１から３のいずれか１項記載の共通鍵ブロック暗号化装置において、前記単位ブロック暗号化手段は、ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、前記擬似乱数生成手段は、前記ブロック暗号を簡略化して得られる簡易ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする。【００１８】
請求項５記載の発明は、請求項１から３のいずれか１項記載の共通鍵ブロック暗号化装置においいて、前記単位ブロック暗号化手段は、ブロック暗号を複数回組み合わせて得られる強化ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、前記擬似乱数生成手段は、前記ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする。【００１９】
請求項６記載の発明は、請求項１から３のいずれか１項記載の共通鍵ブロック暗号化装置において、前記単位ブロック暗号化手段は、ブロック暗号を用いて前記単位ブロック中間平文を前記単位ブロック中間暗号文に変換し、前記擬似乱数生成手段は、初期ベクトルを付加的な入力として受け付けるストリーム暗号へ、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を初期ベクトルとして入力して得られる鍵ストリームを中間乱数とすることを特徴とする。【００２０】
請求項７記載の発明は、情報処理装置において行う共通鍵ブロック暗号化方法であって、暗号化される平文を、第１のブロックと、第２のブロックと、に分割し、該分割した第１のブロックをハッシュ関数により圧縮し、該圧縮した第１のブロックと、前記第２のブロックと、を加算し単位ブロック中間文を生成し、該生成した単位ブロック中間文と、前記第１のブロックと、を出力する第１のハッシュ工程と、前記単位ブロック中間文を暗号化し、単位ブロック中間暗号文を生成する単位ブロック暗号化工程と、前記単位ブロック中間文と、前記単位ブロック中間暗号文と、の和を基に中間乱数を生成する擬似乱数生成工程と、前記中間乱数と、前記第１のブロックと、を加算し、第１の加算結果を出力する加算工程と、前記第１の加算結果をハッシュ関数により圧縮し、該圧縮した第１の加算結果及び前記単位ブロック中間暗号文から暗号文を算出する第２のハッシュ工程と、前記第２のハッシュ工程から出力された暗号文を出力する暗号文出力工程とを有することを特徴とする。【００２１】
請求項８記載の発明は、請求項７記載の共通鍵ブロック暗号化方法において、前記第２のハッシュ工程は、前記単位ブロック中間暗号文をハッシュ関数により置換し、該置換された単位ブロック中間暗号文と、前記圧縮した第１の加算結果と、を加算した第２の加算結果と、前記第１の加算結果と、を連結させ、暗号文として出力することを特徴とする。【００２２】
請求項９記載の発明は、請求項８記載の共通鍵ブロック暗号化方法において、第１のハッシュ工程は、秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１のブロックを圧縮し、第２のハッシュ工程は、該秘密鍵の指数倍と、単位ブロック中間暗号文と、の積を算出し、該秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１の加算結果を圧縮し、該算出された積と、該圧縮した第１の加算結果と、を加算して第２の加算結果を算出することを特徴とする。【００２３】
請求項１０記載の発明は、請求項７から９のいずれか１項記載の共通鍵ブロック暗号化方法において、前記単位ブロック暗号化工程は、ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、前記擬似乱数生成工程は、前記ブロック暗号を簡略化して得られる簡易ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする。【００２４】
請求項１１記載の発明は、請求項７から９のいずれか１項記載の共通鍵ブロック暗号化方法において、前記単位ブロック暗号化工程は、ブロック暗号を複数回組み合わせて得られる強化ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、前記擬似乱数生成工程は、前記ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする。【００２５】
請求項１２記載の発明は、請求項７から９のいずれか１項記載の共通鍵ブロック暗号化方法において、前記単位ブロック暗号化工程は、ブロック暗号を用いて前記単位ブロック中間平文を前記単位ブロック中間暗号文に変換し、前記擬似乱数生成工程は、初期ベクトルを付加的な入力として受け付けるストリーム暗号へ、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を初期ベクトルとして入力して得られる鍵ストリームを中間乱数とすることを特徴とする。【００２６】
請求項１３記載の発明は、情報処理装置において実行させる共通鍵ブロック暗号化プログラムであって、暗号化される平文を、第１のブロックと、第２のブロックと、に分割し、該分割した第１のブロックをハッシュ関数により圧縮し、該圧縮した第１のブロックと、前記第２のブロックと、を加算し単位ブロック中間文を生成し、該生成した単位ブロック中間文と、前記第１のブロックと、を出力する第１のハッシュ処理と、前記単位ブロック中間文を暗号化し、単位ブロック中間暗号文を生成する単位ブロック暗号化処理と、前記単位ブロック中間文と、前記単位ブロック中間暗号文と、の和を基に中間乱数を生成する擬似乱数生成処理と、前記中間乱数と、前記第１のブロックと、を加算し、第１の加算結果を出力する加算処理と、前記第１の加算結果をハッシュ関数により圧縮し、該圧縮した第１の加算結果及び前記単位ブロック中間暗号文から暗号文を算出する第２のハッシュ処理と、前記第２のハッシュ処理から出力された暗号文を出力する暗号文出力処理とを有することを特徴とする。【００２７】
請求項１４記載の発明は、請求項１３記載の共通鍵ブロック暗号化プログラムにおいて、前記第２のハッシュ処理は、前記単位ブロック中間暗号文をハッシュ関数により置換し、該置換された単位ブロック中間暗号文と、前記圧縮した第１の加算結果と、を加算した第２の加算結果と、前記第１の加算結果と、を連結させ、暗号文として出力することを特徴とする。【００２８】
請求項１５記載の発明は、請求項１４記載の共通鍵ブロック暗号化プログラムにおいて、第１のハッシュ処理は、秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１のブロックを圧縮し、第２のハッシュ処理は、該秘密鍵の指数倍と、単位ブロック中間暗号文と、の積を算出し、該秘密鍵を変数とした有限体上の多項式ハッシュ関数を用いて前記第１の加算結果を圧縮し、該算出された積と、該圧縮した第１の加算結果と、を加算して第２の加算結果を算出することを特徴とする。【００２９】
請求項１６記載の発明は、請求項１３から１５のいずれか１項記載の共通鍵ブロック暗号化プログラムにおいて、前記単位ブロック暗号化処理は、ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、前記擬似乱数生成処理は、前記ブロック暗号を簡略化して得られる簡易ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする。【００３０】
請求項１７記載の発明は、請求項１３から１５のいずれか１項記載の共通鍵ブロック暗号化プログラムにおいて、前記単位ブロック暗号化処理は、ブロック暗号を複数回組み合わせて得られる強化ブロック暗号を用いて前記単位ブロック中間文を前記単位ブロック中間暗号文に変換し、前記擬似乱数生成処理は、前記ブロック暗号を複数回用いた拡大処理に、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を入力として適用した結果を中間乱数とすることを特徴とする。【００３１】
請求項１８記載の発明は、請求項１３から１５のいずれか１項記載の共通鍵ブロック暗号化プログラムにおいて、前記単位ブロック暗号化処理は、ブロック暗号を用いて前記単位ブロック中間平文を前記単位ブロック中間暗号文に変換し、前記擬似乱数生成処理は、初期ベクトルを付加的な入力として受け付けるストリーム暗号へ、前記単位ブロック中間暗号文と前記単位ブロック中間文との和を初期ベクトルとして入力して得られる鍵ストリームを中間乱数とすることを特徴とする。【００３２】
請求項１９記載の記録媒体は、請求項１３から１８のいずれか１項記載の共通鍵ブロック暗号化プログラムを記録することを特徴とする。
【発明の効果】
【００３３】
本発明は、選択暗号文攻撃に安全なブロック暗号と、既知平文攻撃に安全な暗号関数とを組み合わせることにより、１ブロックの暗号化につき選択暗号文攻撃に安全なブロック暗号の呼び出し回数はブロックサイズに関わらず１回で済むことになるため、もし第一および第二のハッシュ手段で用いるハッシュ関数が十分高速であれば、大きいブロックサイズでは暗号化のスループットは、既知平文攻撃に安全な関数のスループットにほぼ一致することになり、選択暗号文攻撃に安全な、かつ任意の大きいブロックサイズのブロック暗号を効率よく提供できる。
【発明を実施するための最良の形態】
【００３４】
まず、図１を参照しながら、本実施形態における共通鍵ブロック暗号化装置について説明する。【００３５】
本実施形態における共通鍵ブロック暗号化装置は、図１に示すように、暗号化される平文を入力する平文入力手段１０１と、平文を、PAブロックと、PBブロックと、に分割し、該分割したPBブロックをAXUハッシュ関数H1により圧縮し、該圧縮したPBブロックと、PAブロックと、を加算した単位ブロック中間文を生成し、該生成した単位ブロック中間文と、PBブロックと、を出力する第１のハッシュ手段１０２と、単位ブロック中間文を暗号化し、単位ブロック中間暗号文を生成する単位ブロック暗号化手段１０３と、単位ブロック中間暗号文及び単位ブロック中間文から中間乱数を生成する擬似乱数生成手段１０４と、中間乱数と、PBブロックと、を加算し、加算結果を出力する加算手段１０５と、AXUハッシュ関数H1と独立なAXUハッシュ関数H2によって加算結果を圧縮し、該圧縮した加算結果と、AXUハッシュ関数H1，H2と独立なAXU置換G3によって単位ブロック中間暗号文を変換した結果と、を加算した加算結果と、加算手段１０５の加算結果と、を連結して暗号文として出力する第２のハッシュ手段１０６と、暗号文を出力する暗号文出力手段１０７と、を有することを特徴とするものである。これにより、選択平文／暗号文攻撃に安全な暗号部品と、既知平文攻撃に安全な暗号部品と、を組み合わせ、安全なブロック暗号を提供することが可能となる。【００３６】
＜第１の実施形態＞
まず、図１を参照しながら、第１の実施形態における共通鍵ブロック暗号化装置の構成について説明する。なお、図１は、第１の実施形態における共通鍵ブロック暗号化装置の構成を示すブロック図である。【００３７】
第１の実施形態における共通鍵ブロック暗号化装置は、平文入力手段１０１と、第１のハッシュ手段１０２と、単位ブロック暗号化手段１０３と、擬似乱数生成手段１０４と、加算手段１０５と、第２のハッシュ手段１０６と、暗号文出力手段１０７と、を有して構成される。【００３８】
なお、本実施形態における共通鍵ブロック暗号化装置は、CPUとメモリとディスクとにより実現することは可能である。共通鍵ブロック暗号化装置の各手段は、上記各手段を実行するためのプログラムをディスクに格納し、該格納したプログラムをCPUが実行することで実現することになる。【００３９】
次に、共通鍵ブロック暗号化装置を構成する各手段について説明する。【００４０】
＜平文入力手段１０１＞
平文入力手段１０１は、暗号化される対象となる平文を入力するものである。例えば、キーボードなどの文字入力装置により実現されることになる。【００４１】
＜第１のハッシュ手段１０２＞
第１のハッシュ手段１０２は、平文入力手段１０１から入力された平文をPAブロックと、PBブロックと、に分割し、該分割したPBブロックをハッシュ関数により圧縮し、該圧縮したPBブロックと、PAブロックと、を加算する。そして、第１のハッシュ手段１０２は、ハッシュ関数により圧縮したPBブロックと、ハッシュ関数により圧縮していないPAブロックとの和を、ハッシュ関数により圧縮する前のPBブロックと、を連結して出力する。【００４２】
第１のハッシュ手段１０２の条件を以下に示す。平文全体のブロックサイズをnmビット（ただし、mは２以上の整数）とし、単位ブロック暗号化手段１０３へ入力される単位ブロック中間文のビット幅をnとする。入力の左側のnビット（PAブロック）を取り出す関数をleft、入力の右側n(m-1)ビット（PBブロック）を取り出す関数をrightとする。第一のハッシュ手段１０２をG1とすると、G1は鍵付きのnmビット置換であり、任意の異なる２つの入力長x、x'についてleft(G1(x))＝left(G1(x'))となる確率が小さいことが必要である。【００４３】
実際には、第１のハッシュ手段１０２は、almost XOR universal（以下、AXUとする）と呼ばれる性質を持つ鍵付きのハッシュ関数により実現可能である。これは、鍵付きハッシュ関数への異なる２つの入力について、それぞれに対するハッシュ関数の出力の和がほぼ一様に分布することを意味する。このようなハッシュ関数Hは、一般にユニバーサルハッシュ関数と呼ばれ、例えば有限体の積や、非特許文献４に記載のMultimodular Hash Functionを使うことで実現可能である。【００４４】
具体的には、AXUハッシュ関数によるフェイステル型置換により実現可能である。これは、n(m-1)ビット入力、nビット出力のAXUハッシュ関数をH1とした場合、入力長xについて第１のハッシュ手段１０２の出力は、式１となる。
G1(x)=(left(x)+H1(right(x))||right(x))・・・（式１）
ここで、left(x)+H1(right(x))を単位ブロック中間文とする。【００４５】
＋記号は、ビットごとの排他的論理和をあらわすとする。例えば、right(x)をnビットベクトルr_1,...,r_[m-1]を用いてright(x)=(r_1,...,r_[m-1])とあらわした場合、H1はnビットの秘密鍵K1を変数とし、nビットベクトルr_1,...,r_[m-1]を係数とした有限体上の多項式計算により実現可能である。具体的には、式２となる。
H1(right(x))=mul(r_[m-1],K1^[m-1])+mul(r_[m-2],K1^[m-2])+...+mul(r_[1],K1)・・・（式２）
ここで、K1^[i]はK1のi乗を指し、mul(a,b)は変数aと係数bの有限体上の積を表す。積を高速に行うアルゴリズムは、例えば非特許文献５に示されている。【００４６】
＜単位ブロック暗号化手段１０３＞
単位ブロック暗号化手段１０３は、単位ブロック中間文の暗号文である単位ブロック中間暗号文を生成する手段である。単位ブロック中間暗号文は、非特許文献６に開示されているAES（Advanced Encryption Standard）などの選択暗号文攻撃に安全なブロック暗号や、そのシリアル連結などにより実現可能である。【００４７】
＜擬似乱数生成手段１０４＞
擬似乱数生成手段１０４は、単位ブロック中間文と単位ブロック中間暗号文とを基に、それらの和を用いて中間乱数を生成する手段である。【００４８】
擬似乱数生成手段１０４において、単位ブロック中間文と単位ブロック中間暗号文の和を入力される乱数生成器は、既知平文攻撃に安全であることが求められる。すなわち、攻撃者がランダムに入力を選択できるモデルのもとで中間乱数を得たときに、中間乱数と、真の乱数と、の判別が困難となればよい。一般に、擬似乱数生成手段１０４で用いる乱数生成器の出力長は入力長より大幅に長くなるが、このような処理は、特許文献１や非特許文献８の手法を利用することで、出力幅が固定された小さい値である、既知平文攻撃に安全な関数から実現可能である。【００４９】
また、擬似乱数生成手段１０４で用いる乱数生成器は、初期ベクトルと呼ばれる付加的な入力を持つストリーム暗号でも実現可能である。このようなストリーム暗号は、例えば、非特許文献８に記載のストリーム暗号SEALにより実現可能である。【００５０】
＜加算手段１０５＞
加算手段１０５は、中間乱数と平文の一部であるPBブロックとの加算を行う手段である。平文全体のブロックサイズがnmビットの場合、PBブロックは右側n(m-1)ビットに相当する。【００５１】
＜第２のハッシュ手段１０６＞
第２のハッシュ手段１０６は、加算手段１０５の出力と単位ブロック中間暗号文から出力となる暗号文を求める手段である。【００５２】
第２のハッシュ手段１０６の条件を以下に示す。平文全体のブロックサイズをnmビット（ただし、mは２以上の整数）とし、単位ブロック暗号化手段１０３へ入力される単位ブロック中間文のビット幅をnとする。入力の左側nビット（単位ブロック中間暗号文）を取り出す関数をleft、入力の右n(m-1)ビット（加算手段１０５による加算結果）を取り出す関数をrightとする。第１のハッシュ手段１０２をG1、第２のハッシュ手段１０６をG2とする。G1、G2ともに鍵付きのnmビット置換であり、それぞれの逆関数をG1^[-1]、G2^[-1]とする。【００５３】
このとき、G1への任意の異なる２つの入力長x、x'及びG2^[-1]への任意の異なる２つの入力長y、y'について、left(G1(x)+G2^[-1](y))=left(G1(x')+G2^[-1](y'))となる確率と、left(G2^[-1](y))=left(G2^[-1](y'))となる確率の両方が小さいことが必要である。これは正確にはG1とG2両方を考慮した条件となる。【００５４】
具体的に、第１のハッシュ手段１０２をAXUハッシュ関数H1によるフェイステル型置換とした場合、第２のハッシュ手段１０６は、式３となる。
G2(x)=G3(left(x))+H2(right(x))||right(x))・・・（式３）
ここで、||は系列の連結を表す。H2はH1と独立な、n(m-1)ビット入力nビット出力のAXUハッシュ関数である。また、G3はnビットのAXU置換であることが必要である。これは、任意のcと異なる２つのnビットの入力長z、z'について、G3(z)-G3(z')=cとなる確率が小さくなることを意味する。例えば、G3の鍵をnビットの独立な、0以外の値を一様にとる乱数K3とし、G3(z)=mul(z,K3)とすることで実現可能である。ただしmul(a,b)は有限体GF(2^n)上での積をあらわす。【００５５】
もし、第１のハッシュ手段１０２が秘密鍵K1を用いて（式２）であらわされるH1を実現し、これを（式１）で用いる場合、第２のハッシュ手段１０６は、（式３）において、H2をG1と同じ秘密鍵K1を用いて、（式２）のH1と同じ関数とし、AXU置換をG3(left(x))=mul(left(x),K1^[m])とすることでも実現可能である。ただし、この場合、秘密鍵K1は0以外の値を一様にとる乱数でなくてはならない。【００５６】
＜暗号文出力手段１０７＞
暗号文出力手段１０７は、第２のハッシュ手段１０６から入力された出力結果を暗号文として出力する手段である。コンピュータディスプレイやプリンターなどで実現可能である。【００５７】
次に、図２を参照しながら、図１に示す第１の実施形態における共通鍵ブロック暗号化装置の処理動作について説明する。【００５８】
まず、平文入力手段１０１は、暗号化される平文（PAブロック、PBブロック）を第１のハッシュ手段１０２に入力することになる（ステップＡ１）。【００５９】
第１のハッシュ手段１０２は、平文入力手段１０１から入力された平文（PAブロック、PBブロック）をPAブロックと、PBブロックと、に分割し、該分割したPBブロックをAXUハッシュ関数H1により圧縮し、該圧縮したPBブロックと、PAブロックと、を加算し単位ブロック中間文を生成し、該生成した単位ブロック中間文と、PBブロックと、を出力する（ステップＡ２）。【００６０】
単位ブロック暗号化手段１０３は、第１のハッシュ手段１０２から入力された単位ブロック中間文を暗号化し、単位ブロック中間暗号文を生成し、該生成した単位ブロック中間暗号文を、擬似乱数生成手段１０４と、第２のハッシュ手段１０６と、に出力することになる（ステップＡ３）。【００６１】
擬似乱数生成手段１０４は、単位ブロック中間文と、単位ブロック暗号化手段１０３から入力された単位ブロック中間暗号文と、を基に中間乱数を生成し、該生成した中間乱数を加算手段１０５に出力する（ステップＡ４）。【００６２】
加算手段１０５は、擬似乱数生成手段１０４から入力された中間乱数と、第１のハッシュ手段１０２から入力されたPBブロックと、の加算処理を行い、該加算処理を行った加算値を第２のハッシュ手段１０６に出力することになる（ステップＡ５）。【００６３】
第２のハッシュ手段１０６は、単位ブロック暗号化手段１０３から入力された単位ブロック中間暗号文をAXU置換Ｇ３により変換し（ステップＡ６）、ＡＸＵ置換Ｇ３により変換された単位ブロック中間暗号文と、AXUハッシュ関数H2により圧縮された加算手段１０５から入力された加算結果と、を加算した該加算結果と、加算手段１０５から入力された加算結果と、を連結して暗号文として出力する（ステップＡ７）。【００６４】
暗号文出力手段１０７は、第２のハッシュ手段１０６から入力された暗号文を出力する（ステップＡ８）。【００６５】
これにより、本実施形態における共通鍵ブロック暗号化装置は、選択暗号文攻撃に安全なブロック暗号と、既知平文攻撃に安全な暗号関数とを組み合わせることにより、高速で安全なブロック暗号を大きいブロックサイズに対して実現することが可能となる。本実施形態における共通鍵ブロック暗号化装置は、１ブロックの暗号化につき選択暗号文攻撃に安全なブロック暗号の呼び出し回数はブロックサイズに関わらず１回で済むことになるため、もし第１および第２のハッシュ手段で用いるハッシュ関数が十分高速であれば、大きいブロックサイズでは暗号化のスループットは、既知平文攻撃に安全な関数のスループットにほぼ一致することになる。本実施形態における共通鍵ブロック暗号化装置で用いるハッシュ関数は、ユニバーサル性を満たせば十分であり、このようなハッシュ関数は既存の高速な有限体の演算アルゴリズムなどにより、通常の共通鍵暗号と比べ大幅に高速にできる。既知平文攻撃は、選択平文攻撃よりも弱いクラスの攻撃であるため、既知平文攻撃に安全な関数は一般にそれより弱い定義の安全性を満たす関数よりも高速に動作することになる。したがって、ブロック暗号とその短縮段などを組み合わせることにより、従来の暗号運用モードよりも高速なブロック暗号を構築できる。【００６６】
また、AESなどの代表的なブロック暗号よりも高速なストリーム暗号も近年多数提案されており、AESと組み合わせて用いることで、AESベースの従来方式よりも高速な方式が実現可能である。反対に、既存のブロック暗号をシリアルに鍵を変えて連結した連結ブロック暗号と、ブロック暗号そのものとを組み合わせて本実施形態における共通鍵ブロック暗号化装置に適用すると、これを破るには連結ブロック暗号を選択暗号文攻撃で破るか、ブロック暗号そのものを既知平文攻撃で破ることが必要となる。これは、従来の暗号運用モードと同等の速度を有し、かつ従来より高い安全性を実現していることを意味している。【００６７】
この出願は、２００６年１０月３０日に出願された日本出願特願２００６−２９４５３６を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００６８】
本発明によれば、２者間で暗号化通信を行うシステムや、映画や音楽などのコンテンツを安全に配信するシステム、また、コンピュータサーバ上のデータを安全に運用するためのファイル暗号化といった用途に適用できる。
【図面の簡単な説明】
【００６９】
【図１】本実施形態に係る共通鍵ブロック暗号化装置の構成を示すブロック図である。
【図２】本実施形態に係る共通鍵ブロック暗号化装置の動作の流れを示すフローチャートである。
【符号の説明】
【００７０】
１０１    平文入力手段
１０２    第１のハッシュ手段
１０３    単位ブロック暗号化手段
１０４    擬似乱数生成手段
１０５    加算手段
１０６    第２のハッシュ手段
１０７    暗号文出力手段
【図１】
2008053650.tif 000003
【図２】
2008053650.tif 000004
【国際調査報告】
2008053650.tif 000005
2008053650.tif 000006
2008053650.tif 000007
2008053650.tif 000008