(57)【要約】  倍ブロック長ブロック暗号化装置は、２ｎビット平文が入力されると、２ｎビット平文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成し、ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、第２の中間変数をｍビットに短縮した結果を調整値として第１の中間変数を暗号化してｎビットの第３の中間変数を生成する。そして、倍ブロック長ブロック暗号化装置は、ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、第３の中間変数をｍビットに短縮した結果を調整値として第２の中間変数を暗号化してｎビットの第４の中間変数を得、第３及び第４の中間変数を連結して、ユニバーサルハッシュ関数ベースの逆撹拌を適用し、２ｎビット暗号文を生成する。
2010024003.tif 000002
【特許請求の範囲】
【請求項１】
暗号化される２ｎビット平文を入力する平文入力手段と、
前記２ｎビット平文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌手段と、
ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第２の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第３の中間変数を生成する第１の調整値付き単位ブロック暗号化手段と、
前記ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第４の中間変数を得る第２の調整値付き単位ブロック暗号化手段と、
前記第３及び第４の中間変数を連結して、ユニバーサルハッシュ関数ベースの逆撹拌を適用し、２ｎビット暗号文を生成する逆撹拌手段と、
前記２ｎビット暗号文を出力する暗号文出力手段と、
を有する倍ブロック長ブロック暗号化装置。
【請求項２】
前記ユニバーサルハッシュ関数ベースの置換及び前記ユニバーサルハッシュ関数ベースの逆置換は、ユニバーサルハッシュ関数をラウンド関数としたFeistel型置換を、ｍ＝ｎの場合は１回、ｍ＜ｎの場合は２回繰り返すことで構成されることを特徴とする、請求項１記載の倍ブロック長ブロック暗号化装置。
【請求項３】
前記暗号化関数は、平文のブロック長をｎビットとし、鍵長をｎビットとする暗号化関数であり、
前記第１の調整値付き単位ブロック暗号化手段は、前記調整値をｎビットになるようにパディングした値を平文として、該平文をｎビット鍵で前記暗号化関数を用いて暗号化し、該暗号化した結果をｎビット鍵とし、前記第１の中間変数を平文として、該平文を該ｎビット鍵で該暗号化関数を用いて暗号化することにより、前記第３の中間変数を生成し、
前記第２の調整値付き単位ブロック暗号化手段は、前記調整値をｎビットになるようにパディングした値を平文として、該平文をｎビット鍵で前記暗号化関数を用いて暗号化し、該暗号化した結果をｎビット鍵とし、前記第３の中間変数を平文として、該平文を該ｎビット鍵で該暗号化関数を用いて暗号化することにより、前記第４の中間変数を生成する、請求項１又は２記載の倍ブロック長ブロック暗号化装置。
【請求項４】
前記第１及び第２の調整値付き単位ブロック暗号化手段が用いるｍビット調整値付きｎビットブロック暗号の暗号化関数は、ｎビットブロック暗号の暗号化処理における中間変数へ調整値を加算することで調整値付きの暗号化を行うための関数である、請求項１から３のいずれか１項記載の倍ブロック長ブロック暗号化装置。
【請求項５】
復号される２ｎビット暗号文を入力する暗号文入力手段と、
前記２ｎビット暗号文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌手段と、
ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第１の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第３の中間変数を生成する第２の調整値付き単位ブロック復号手段と、
前記ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第４の中間変数を生成する第１の調整値付き単位ブロック復号手段と、
前記第３及び第４の中間変数を連結してユニバーサルハッシュ関数ベースの逆置換を適用して２ｎビット平文を生成する逆撹拌手段と、
前記２ｎビット平文を出力する平文出力手段と、
を有する倍ブロック長ブロック復号装置。
【請求項６】
ユニバーサルハッシュ関数ベースの置換及びユニバーサルハッシュ関数ベースの逆置換は、ユニバーサルハッシュ関数をラウンド関数としたFeistel型置換を、ｍ＝ｎの場合は１回、ｍ＜ｎの場合は２回繰り返すことで構成されることを特徴とする、請求項５記載の倍ブロック長ブロック復号装置。
【請求項７】
前記復号関数は、暗号文のブロック長をｎビットとし、鍵長をｎビットとする復号関数であり、
前記第１の調整値付き単位ブロック復号手段は、前記調整値をｎビットになるようにパディングした値を暗号文として、該暗号文をｎビット鍵で前記復号関数を用いて復号し、該復号した結果をｎビット鍵とし、前記第１の中間変数を暗号文として、該暗号文を該ｎビット鍵で該復号関数を用いて復号することにより、前記第３の中間変数を生成し、
前記第２の調整値付き単位ブロック復号手段は、前記調整値をｎビットになるようにパディングした値を暗号文として、該暗号文をｎビット鍵で前記復号関数を用いて復号し、該復号した結果をｎビット鍵とし、前記第１の中間変数を暗号文として、該暗号文を該ｎビット鍵で該復号関数を用いて復号することにより、前記第４の中間変数を生成する、請求項５又は６に記載の倍ブロック長ブロック暗号化装置。
【請求項８】
前記第１及び第２の調整値付き単位ブロック復号手段が用いるｍビット調整値付きｎビットブロック暗号の復号関数は、ｎビットブロック暗号Ｅの復号処理における中間変数へ調整値を加算することで調整値付きの復号を行うための関数である、請求項５から７の何れか１項記載の倍ブロック長ブロック復号装置。
【請求項９】
暗号化される２ｎビット平文を入力する平文入力処理と、
前記２ｎビット平文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌処理と、
ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第２の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第３の中間変数を生成する第１の調整値付き単位ブロック暗号化処理と、
前記ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第４の中間変数を得る第２の調整値付き単位ブロック暗号化処理と、
前記第３及び第４の中間変数を連結して、ユニバーサルハッシュ関数ベースの逆撹拌を適用し、２ｎビット暗号文を生成する逆撹拌処理と、
前記２ｎビット暗号文を出力する暗号文出力処理と、
を有する倍ブロック長ブロック暗号化方法。
【請求項１０】
復号される２ｎビット暗号文を入力する暗号文入力処理と、
前記２ｎビット暗号文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌処理と、
ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第１の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第３の中間変数を生成する第２の調整値付き単位ブロック復号処理と、
前記ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第４の中間変数を生成する第１の調整値付き単位ブロック復号処理と、
前記第３及び第４の中間変数を連結してユニバーサルハッシュ関数ベースの逆置換を適用して２ｎビット平文を生成する逆撹拌処理と、
前記２ｎビット平文を出力する平文出力処理と、
を有する倍ブロック長ブロック復号方法。
【請求項１１】
請求項９記載の倍ブロック長ブロック暗号化方法をコンピュータに実行させる、倍ブロック長ブロック暗号化プログラム。
【請求項１２】
請求項１０記載の倍ブロック長ブロック復号方法をコンピュータに実行させる、倍ブロック長ブロック復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ブロック暗号の運用モードに関し、特にｎビットブロック暗号による汎用的で高い安全性を持つ倍ブロック長ブロック暗号化装置、復号装置、暗号化方法及び復号方法、及びそのプログラムに関する。
【背景技術】
【０００２】
ブロック暗号とは、鍵により一意に定まる置換の集合であり、置換への入力が平文、出力が暗号文にそれぞれ相当する。平文や暗号文の長さをブロックサイズという。ブロックサイズがｎビットのブロック暗号を、一般的にｎビットブロック暗号という。ブロック暗号化・復号に関連する技術としては、特許文献１に開示される「ブロック暗号方法及び復号方法」がある。【０００３】
２ｎビットブロックサイズのブロック暗号を構成する場合、ｎビット入出力のラウンド関数と呼ばれる処理を用いた２ｎビット置換を繰り返す方法がある。例えば、ＤＥＳ(Data  Encryption  Standard)は６４ビットブロックサイズであり、３２ビット入出力長のラウンド関数と呼ばれる処理を用いたFeistel型置換と呼ばれる置換を繰り返すことで構成されている。ＤＥＳなどの実用的なブロック暗号では、ラウンド関数の処理は比較的シンプルであり、ラウンド関数の出力自体の乱数性は低い（乱数と容易に判別可能）ため、Feistel型置換の繰り返し回数を十分大きく取り、６４ビット全体の乱数性を高める必要がある。ＤＥＳの場合は１６回の繰り返しを行っている。【０００４】
一方、計算量的に高い乱数性を持つｎビット入出力ラウンド関数を用いるアプローチがある。このアプローチの利点は、ラウンド関数による２ｎビット置換を繰り返す回数がごく僅かでも、高い安全性を有することである。例えば、ラウンド関数の出力が真の乱数と効率的に判別できないほど高い乱数性をもつならば、Feistel型置換を３〜４回繰り返すことで、全体として計算量的安全性が保証された２ｎビットブロック暗号となることがLuby  及び  Rackoffによって証明されている。【０００５】
よく考えられた既存のｎビットブロック暗号は、計算量的に高い乱数性を持つと考えられるため、Luby  及び  Rackoffの結果に基づき、ＤＥＳをラウンド関数とした１２８ビットブロック暗号や、１２８ビットブロック暗号であるＡＥＳ(Advanced  Encryption  Standard)をラウンド関数とした２５６ビットブロック暗号を構成することが可能である。【０００６】
上記のようなブロック暗号は、既存のｎビットブロックサイズのブロック暗号を部品として用いて２ｎビットブロックサイズを実現しているという意味で、「倍ブロック長ブロック暗号」と呼ばれている。【０００７】
倍ブロック長ブロック暗号の応用としては、ハードディスクなどストレージの暗号化が考えられる。一般的なストレージの暗号化において、カウンタなどの状態変数を用いた暗号化は、状態変数を保管するストレージ領域の確保や安全性などの観点から現実的ではなく、また、システム制約上平文と暗号文との長さが等しいため、メッセージ認証コードの併用による改ざんも防止できない（メッセージ認証コードの併用により暗号文が平文よりも長くなるため）。【０００８】
倍ブロック長ブロック暗号の構成方法は、非特許文献１に開示されている４回のFeistel型置換の繰り返しによる方法（図１３、図１４参照）など様々提案されているが、この方式を含めほとんどの場合、その安全性保証は、一つの鍵で処理する暗号化回数ｑが２n/2よりも十分に小さい（これをｑ≪２n/2と表す）場合に限られている。２n/2は「バースデーバウンド」と呼ばれ、バースデーバウンド程度の回数の暗号化の結果を用いた攻撃は一般にバースデー攻撃と呼ばれる。このような攻撃は、６４ビットブロック暗号を用いた場合には現実的な脅威となり、また１２８ビットブロック暗号を用いた場合でも将来的なリスクと考えられるため、対策が必要である。【０００９】
例えば、Feistel型置換を４回繰り返す構成の場合、ラウンド関数によらずバースデー攻撃による攻撃が可能であることが知られている。【００１０】
バースデー攻撃に対する耐性のある倍ブロック長ブロック暗号の構成方法としては、非特許文献２が知られている。これにより、５ないし６回のFeistel型置換の繰り返しにより、バースデー攻撃への耐性を持つことが示されている。【００１１】
ただし、この結果は、ｎビット入出力ラウンド関数がバースデー攻撃への理論的耐性を持つ疑似ランダム関数である場合に成立するものである。現実的に安全なｎビットブロック暗号は、疑似ランダム置換と考えることができるが、疑似ランダム置換は逆関数が存在する以上、バースデー攻撃への理論的耐性を持つ疑似ランダム関数とは成り得ないため、上記の結果をそのまま適用することはできない。【００１２】
疑似ランダム置換からバースデー攻撃への理論的耐性を持つ疑似ランダム関数への変換は、非特許文献３に開示されるＳＵＭ方式で可能であるが、疑似ランダム関数を１コール実現するのに疑似ランダム置換を少なくとも２コール必要とするため、５ないし６回Feistel型置換のラウンド関数としてＳＵＭ方式を用いると、全体としてはｎビットブロック暗号を少なくとも１０コールから１２コール必要とすることとなる。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００２−１０８２０５号公報
【非特許文献】
【００１４】
【非特許文献１】M.  Naor,  O.  Reingold,  On  the  Construction  of  Pseudo-Random  Permutations:  Luby-Rackoff  Revisited,  Electronic  Colloquium  on  Computational  Complexity  (ECCC)  4(5),  1997.
【非特許文献２】J.  Patarin,  Security  of  Random  Feistel  Schemes  with  5  or  More  Rounds,  Advances  in  Cryptology  -  CRYPTO  2004,  24th  Annual  International  Cryptology  Conference,  Santa  Barbara,  California,  USA,  August  15-19,  2004,  Proceedings.  Lecture  Notes  in  Computer  Science  3152  Springer  2004,  pp.  106-122.
【非特許文献３】S.  Lucks,  The  Sum  of  PRPs  Is  a  Secure  PRF,  Advances  in  Cryptology  -  EUROCRYPT  2000,  International  Conference  on  the  Theory  and  Application  of  Cryptographic  Techniques,  Bruges,  Belgium,  May  14-18,  2000,  Proceeding.  Lecture  Notes  in  Computer  Science  1807  Springer  2000,  pp.  470-484.
【発明の概要】
【発明が解決しようとする課題】
【００１５】
このように、ブロック暗号を用いた倍ブロック長ブロック暗号構成方法としては、バースデー攻撃によって破られる方式か、理論的耐性を持つが非常に効率の悪い方式かのいずれかしか実現されていなかった。【００１６】
本発明は係る問題に鑑みてなされたものであり、現実的なブロック暗号を用いて、バースデー攻撃への理論的耐性を持つ倍ブロック長ブロック暗号を効率よく構成できる倍ブロック長ブロック暗号化装置、方法及びそのプログラム、並びに復号装置、方法及びそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
上記目的を達成するために、本発明の倍ブロック長ブロック暗号化装置は、暗号化される２ｎビット平文を入力する平文入力手段と、前記２ｎビット平文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌手段と、ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第２の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第３の中間変数を生成する第１の調整値付き単位ブロック暗号化手段と、前記ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第４の中間変数を得る第２の調整値付き単位ブロック暗号化手段と、前記第３及び第４の中間変数を連結して、ユニバーサルハッシュ関数ベースの逆撹拌を適用し、２ｎビット暗号文を生成する逆撹拌手段と、前記２ｎビット暗号文を出力する暗号文出力手段と、を有する。【００１８】
本発明の倍ブロック長ブロック復号装置は、復号される２ｎビット暗号文を入力する暗号文入力手段と、前記２ｎビット暗号文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌手段と、ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第１の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第３の中間変数を生成する第２の調整値付き単位ブロック復号手段と、前記ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第４の中間変数を生成する第１の調整値付き単位ブロック復号手段と、前記第３及び第４の中間変数を連結してユニバーサルハッシュ関数ベースの逆置換を適用して２ｎビット平文を生成する逆撹拌手段と、前記２ｎビット平文を出力する平文出力手段と、を有する。【００１９】
本発明の倍ブロック長ブロック暗号化方法は、暗号化される２ｎビット平文を入力する平文入力処理と、前記２ｎビット平文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌処理と、ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第２の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第３の中間変数を生成する第１の調整値付き単位ブロック暗号化処理と、前記ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第４の中間変数を得る第２の調整値付き単位ブロック暗号化処理と、前記第３及び第４の中間変数を連結して、ユニバーサルハッシュ関数ベースの逆撹拌を適用し、２ｎビット暗号文を生成する逆撹拌処理と、前記２ｎビット暗号文を出力する暗号文出力処理と、を有する倍ブロック長ブロック暗号化方法である。【００２０】
本発明の倍ブロック長ブロック復号方法は、復号される２ｎビット暗号文を入力する暗号文入力処理と、前記２ｎビット暗号文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌処理と、ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第１の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第３の中間変数を生成する第２の調整値付き単位ブロック復号処理と、前記ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第４の中間変数を生成する第１の調整値付き単位ブロック復号処理と、前記第３及び第４の中間変数を連結してユニバーサルハッシュ関数ベースの逆置換を適用して２ｎビット平文を生成する逆撹拌処理と、前記２ｎビット平文を出力する平文出力処理と、を有する倍ブロック長ブロック復号方法である。【００２１】
本発明の倍ブロック長ブロック暗号化プログラムは、本発明の倍ブロック長ブロック暗号化方法をコンピュータに実行させる、プログラムである。【００２２】
本発明の倍ブロック長ブロック復号プログラムは、本発明の倍ブロック長ブロック復号方法をコンピュータに実行させる、プログラムである。
【発明の効果】
【００２３】
本発明によれば、現実的なブロック暗号を用いて、バースデー攻撃への理論的耐性を持つ倍ブロック長ブロック暗号を効率よく構成できる倍ブロック長ブロック暗号化装置、方法及びそのプログラム、並びに復号装置、方法及びそのプログラムを提供できる。
【図面の簡単な説明】
【００２４】
【図１】本発明を好適に実施した第１の実施形態に係る倍ブロック長ブロック暗号化装置の構成を示す図である。
【図２】第１の実施形態に係る倍ブロック長ブロック暗号化装置における情報の流れを示す図である。
【図３】調整値のビット長よりもブロックサイズのビット長が大きい場合にFeistel型置換を用いて構成した撹拌部及び逆撹拌部を備えた倍ブロック長ブロック暗号化装置の要部を示す図である。
【図４】調整値のビット長がブロックサイズのビット長に等しい場合にFeistel型置換を用いて構成した撹拌部及び逆撹拌部を備えた倍ブロック長ブロック暗号化装置の要部を示す図である。
【図５】通常のブロック暗号による鍵更新を用いて実現した調整値付き単位ブロック暗号化部を示す図である。
【図６】第１の実施形態に係る倍ブロック長ブロック暗号化装置の動作の流れを示す図である。
【図７】本発明を好適に実施した第２の実施形態に係る倍ブロック長ブロック復号装置の構成を示す図である。
【図８】第２の実施形態に係る倍ブロック長ブロック復号装置における情報の流れを示す図である。
【図９】調整値のビット長よりもブロックサイズのビット長が大きい場合にFeistel型置換を用いて構成した撹拌部及び逆撹拌部を備えた倍ブロック長ブロック復号装置の要部を示す図である。
【図１０】調整値のビット長がブロックサイズのビット長に等しい場合にFeistel型置換を用いて構成した撹拌部及び逆撹拌部を備えた倍ブロック長ブロック復号装置の要部を示す図である。
【図１１】通常のブロック暗号による鍵更新を用いて実現した調整値付き単位ブロック復号部を示す図である。
【図１２】第２の実施形態に係る倍ブロック長ブロック復号装置の動作の流れを示す図である。
【図１３】Feistel型置換の４回の繰り返しによる倍ブロック長ブロック暗号化を示す図である。
【図１４】Feistel型置換の４回の繰り返しによる倍ブロック長ブロック復号を示す図である。
【発明を実施するための形態】
【００２５】
本発明は、バースデーバウンドを超えた安全性を保証する効率的な倍ブロック長ブロック暗号を効率よく実現するものである。部品として用いる（ｍビット調整値、ｎビットブロックの）調整値付きブロック暗号が理論的に安全で、攻撃者が用いる平文・暗号文対の数が２(n+m)/2よりも十分小さい場合に理論的安全性を持つため、バースデー攻撃に対する理論的耐性を持つからである。
【００２６】
調整値付きブロック暗号自体にもバースデーバウンドを超えた安全性が求められるが、調整値の長さ（要求する安全性のレベルにより決まる）によっては通常のブロック暗号で実現可能であり、また、R.  Schroeppel,  Specification  for  the  Hasty  Pudding  Cipher,  http://www.cs.arizona.edu/~rcs/hpc/hpc-spec.に記載のHasty  Pudding  Cipherのように一から設計された調整値付きブロック暗号アルゴリズムも存在し、また、D.  Goldenberg,  S.  Hohenberger,  M.  Liskov,  E.  C.  Schwartz,  H.  Seyalioglu,  On  Tweaking  Luby-Rackoff  Blockciphers,  Advances  in  Cryptology  -  ASIACRYPT  2007,  13th  International  Conference  on  the  Theory  and  Application  of  Cryptology  and  Information  Security,  Kuching,  Malaysia,  December  2-6,  2007,  Proceedings.  Lecture  Notes  in  Computer  Science  4833  Springer  2007,  pp.  342-356.（以下、文献Ａ）に記載のように、通常のブロック暗号のアルゴリズムにおける中間変数へ調整値を加算することで調整値付きブロック暗号を作るアプローチも提案されており、これらの成果に基づいたアルゴリズムで実現することも可能である。
【００２７】
さらに、最初と最後とには撹拌と呼ばれる処理が必要であるが、これはユニバーサルハッシュ関数で実現可能であり、実装環境に応じて最適化することで、ブロック関数よりも大幅に高速に動作させることが可能である。
【００２８】
以下、本発明の好適な実施の形態について説明する。
【００２９】
〔第１の実施形態〕
図１に、本発明を好適に実施した第１の実施形態に係る倍ブロック長ブロック暗号化装置の構成を示す。倍ブロック長ブロック暗号化装置１０は、平文入力部１００、撹拌部１０１、第１の調整値付き単位ブロック暗号化部１０２、第２の調整値付き単位ブロック暗号化部１０３、逆撹拌部１０４、及び暗号文出力部１０５を有する。
【００３０】
倍ブロック長ブロック暗号化装置１０は、ＣＰＵとメモリとディスクとによって実現可能である。倍ブロック長ブロック暗号化装置１０の各機能部は、ディスクに格納されたプログラムをＣＰＵ上で実行させることにより、ソフトウェア処理で実現可能である。
【００３１】
次に、倍ブロック長ブロック暗号化装置１０の各機能部について説明する。以下の説明においては、調整値付きブロック暗号のブロックサイズをｎビット、調整値の長さをｍ（１≦ｍ≦ｎ）ビットとする。図２に、撹拌部１０１、第１の調整値付き単位ブロック暗号化部１０２、第２の調整値付き単位ブロック暗号化部１０３、及び逆撹拌部１０４における情報の流れを示す。
【００３２】
平文入力部１００は、暗号化の対象となる２ｎビットの平文を入力する。これは、キーボードなどの文字入力装置によって実現される。
【００３３】
撹拌部１０１は、入力された２ｎビットの平文へシンプルな鍵付き置換mix1を適用する。鍵付き置換mix1は、任意の異なる二つの２ｎビット平文x，x'を、x=(xL，xR)、x'＝(x'L,x'R)とし、対応するmix1の出力を(SE,TE)=mix1(xL，xR)及び(SE',TE')=mix1(x'L,x'R)とすると（各変数はそれぞれｎビット）、どのような平文対であっても下記式（１）、（２）の条件を十分小さいe1,e2について満たすことが必要である。
【００３４】
【数１】
2010024003.tif 000003
ただし、cutはｎビット入力から任意のｍビットを取り出す関数である。例えば、最下位ｍビットを取り出すとすればよい。また、確率はmix1の鍵のランダムネスによって定義される。具体的には、mix1は２ｎビット空間上でのPairwise  independent  permutationと呼ばれる置換で実現可能である。これは、入力の２ｎビットｘを有限体GF（22n）の要素と見なして、mul(x,K1)+K2を出力とするものである。ただし、mul(a,b)はGF(22n)上の要素a,bの乗算であり、K1,K2はmix1の鍵であり、K1はGF(22n)から零元を除いた集合上で一様に分布し、K2はGF(22n)全体で一様に分布するものである。
【００３５】
また、別の実現方法として、Feistel型置換を用いる方法がある。これは、ｎビット入出力の鍵付き関数Hと、n-mビット入力n+mビット出力の鍵付き関数Gとを用いて、下記式（３）、（４）とすればよい。
【００３６】
【数２】
2010024003.tif 000004
ただし、H(xL)+xRの右n-mビットをwe1、左mビットをwe2とし、G(we1)の上位nビットをZE1、下位mビットをZE2とし、||はビットの連結を、＋はビットごとの排他的論理和（XOR）演算を表すとする。
【００３７】
ここで、鍵付き関数H、Gのそれぞれがe1-almostユニバーサルとe2-almostユニバーサルとであれば、式（１）及び式（２）の条件を満たせることとなる。ただし任意の鍵付き関数（ｔビット入力ｓビット出力）Fがe-almostユニバーサルであるとは、任意の異なるtビット入力ペアx,x'について、Pr[F(x)=F(x')]が高々eであることを言う。このような性質を持つ鍵付き関数はユニバーサルハッシュ関数と呼ばれ、有限体上の乗算で実現可能である。または、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にあるような具体的な実装環境に特化した関数を用いても良い。m<nの場合にFeistel型置換を用いて撹拌部１０１を実現した場合の構成を図３に示している。
【００３８】
また、m=nの場合は、式（１）の条件は不要となるため、関数Ｈによる処理のみで十分であり、関数Ｇは不要となる。具体的にはTE=ｘR+H(ｘL),SE=xLとすればよい。この時の構成は図４に示す。
【００３９】
第１の調整値付き単位ブロック暗号化部１０２は、撹拌部１０１の出力をｎビットブロック二つに分けて、片方をパラメータとして他方を暗号化する。
【００４０】
具体的には、撹拌部１０１の出力を(SE,TE)（共にｎビット）とした場合、第１の調整値付き単位ブロック暗号化部１０２は、下記式（５）に示すような調整値付きブロック暗号（tweakable  block  cipher）の暗号化関数TWENC1を用いて、２ｎビットの(UE,TE)を出力する。K1はTWENC1の鍵である。
【００４１】
【数３】
2010024003.tif 000005
ここで、調整値付きブロック暗号とは、秘密鍵以外に調整値（tweak）と呼ばれるパラメータを用いて暗号化を行うブロック暗号のことを指す。調整値と鍵とが定まれば、平文と暗号文とが一対一に対応することが条件である。すなわち、調整値付きブロック暗号の暗号化関数TWENCと、対応する復号関数TWDECとが存在するとき、平文M、暗号文C、鍵K、調整値Tについて、常に下記式（６）を満たす。
【００４２】
【数４】
2010024003.tif 000006
式（６）を含めた調整値付きブロック暗号の形式的な定義と安全性要件とは、M.  Liskov,  R.  Rivest,  D.  Wagner,  Tweakable  Block  Ciphers,  Advances  in  Cryptology  -  CRYPTO  2002,  22nd  Annual  International  Cryptology  Conference,  Santa  Barbara,  California,  USA,  August  18-22,  2002,  Proceedings.  Lecture  Notes  in  Computer  Science  2442  Springer  2002,  pp.  31-46.（以下、文献Ｂ）に記載されている。
【００４３】
第１の調整値付き単位ブロック暗号化部１０２で用いる調整値付きブロック暗号は、式（５）が示すようにｍビット調整値を持ち、ｎビットブロックサイズである。
【００４４】
具体的な構成方法としては、既存のブロック暗号又はそのシリアル合成に対して、中間変数の一部へ調整値を加算する方式がある。例えば、Feistel暗号についてはこのようなアプローチの妥当性が文献Ａに示されている。
【００４５】
また、調整値に依存したブロック暗号の鍵更新を利用することで、既存の（調整値付きではない）ｎビットブロック暗号のアルゴリズムに手を加えることなく構成することも可能である。具体的には、ｎビットブロック、ｎビット鍵のブロック暗号の暗号化関数ＥＮＣを用いる。調整値Ｔ（ｍビット）、鍵K1で平文Ｍを暗号化するTWENC1を下記式（７）で定義する。
【００４６】
【数５】
2010024003.tif 000007
ここで、Kはブロック暗号のｎビット鍵であり。padはn-mビットの適当なパディング（例えば全ゼロを付け加えるなど）である。この時のTWENCを図５に示す。
【００４７】
このTWENCを用いた場合、上記式（５）の処理は、下記式（８）となる。
【００４８】
【数６】
2010024003.tif 000008
pad(cut(TE))は単にTEのあるn-mビットを固定する処理でも良い。ただし、この方式は安全性の理由からm<n/2が必要である。
【００４９】
なお、文献Ｂに記載の方式や、P.  Rogaway:  Efficient  Instantiations  of  Tweakable  Blockciphers  and  Refinements  to  Modes  OCB  and  PMAC.  Advances  in  Cryptology  -  ASIACRYPT  2004,  10th  International  Conference  on  the  Theory  and  Application  of  Cryptology  and  Information  Security,  Jeju  Island,  Korea,  December  5-9,  2004,  Proceedings.  Lecture  Notes  in  Computer  Science  3329  Springer  2004,  pp.  16-31に記載のXEXモードなども、ｎビットブロック暗号を用いて調整値付きブロック暗号を実現することも可能であるが、その場合の安全性はバースデーバウンドを超えない。
【００５０】
第２の調整値付き単位ブロック暗号化部１０３は、第１の調整値付き単位ブロック暗号化部１０２が出力する２ｎビットをｎビットブロック二つに分けて、片方をパラメータとして他方を暗号化する。具体的には、第１の調整値付き単位ブロック暗号化部１０２の出力を（UE,TE）（ともにｎビット）とした場合、第２の調整値付き単位ブロック暗号化部１０３は、下記式（９）に示すような調整値付きブロック暗号の暗号化関数TWENC2（mビット調整値、nビットブロック）を用いて、2nビットの(UE,VE)を出力する。K2はTWENC2の鍵である。
【００５１】
【数７】
2010024003.tif 000009
TWENC1と同様、TWENC2はｎビットブロック、ｎビット鍵のブロック暗号の暗号化関数ENCを用いて図５に従い、下記式（１０）として生成しても良い。ただしこの方式はTWENC1と同様、安全性の理由からm<n/2が必要である。
【００５２】
【数８】
2010024003.tif 000010
暗号化関数TWENC2は、第１の調整値付き単位ブロック暗号化部１０２が用いるTWENC1と異なるアルゴリズムでも良いし、同じアルゴリズムでも良い。後者の場合、任意のM,K,TについてTWENC2(K,T,M)=TWENC1(K,T,M)となる。さらに、K2は第１の調整値付き単位ブロック暗号化部１０２が用いる鍵K1と同じでも良いし、独立でも良い。
【００５３】
逆撹拌部１０４は、第２の調整値付き単位ブロック暗号化部１０３の２ｎビット出力へシンプルな鍵付き置換invmix2を適用する。逆撹拌部１０４の入力を(UE,VE)とすると、出力はinvmix2(UE,VE)となる。invmix12は、その逆置換をmix2としたとき（すなわち、任意の２ｎビットｘについてmix2（invmix2(x)）=x、mix2が撹拌部１０１におけるmix1と同様の性質を持つとする。
【００５４】
具体的には、任意の異なる二つの2nビット暗号文y,  y'を、y=(yL,yR)、y'=(y'L,y'R)とし、対応するmix2の出力を(UE,VE)=mix2(yL,yR)及び(UE',VE')=mix2(y'L,y'R)とすると（各変数はそれぞれnビット）、どのような暗号文対であっても下記式（１１）、（１２）の条件を十分小さいg1,g2について満たすことが必要である。
【００５５】
【数９】
2010024003.tif 000011
ここで、mix2はmix1の処理を左右反転させたものでよく、invmix2はmix2を定めれば一意に定まる。
【００５６】
具体的には、invmix2はmix1のPairwise  independent  permutationの逆置換とするか、mix1がFeistel型置換である場合、invmix2の入力が(UE,VE)、出力が(yL,yR)ならば、下記式（１３）、（１４）とすれば良い。
【００５７】
【数１０】
2010024003.tif 000012
ただし、UEの左n-mビットをwe3、右mビットをwe4とし、G(we3)の上位nビットをZE3、下位mビットをZE4とする。ここで用いる鍵付き関数HとGの鍵は、それぞれ撹拌部１０１が用いるHとGの鍵と等しくてもよいし、独立でもよい。m<nの場合にFeistel型置換を用いて逆撹拌部１０４を実現した場合の構成は図３に示す。
【００５８】
また、もしm=nの場合は、上記式（１１）の条件は不要となるため、単に、yR=VE、yL=H(yR)+UEとして(yL,yR)を出力すればよい。このときの構成は図４に示す。
【００５９】
暗号文出力部１０５は、逆撹拌部１０４から入力される暗号文(yL,yR)を出力する。暗号文出力部１０５は、コンピュータディスプレイやプリンタなどで実現可能である。
【００６０】
具体的に通信やデータストレージにおける暗号化に使用する場合、本実施形態で得られる2nビットブロック暗号を何らかの暗号モードで使用することが考えられる。すなわち、暗号化の対象となるパケットなどの情報を2nビットごとに分割し、通信であればCBCモードや、T.  Krovetz  and  P.  Rogaway.  The  OCB  Authenticated-Encryption  Algorithm.  Internet  draft,  March  2005.に記載のOCBモードが適用する。ハードディスクなどデータストレージの暗号化においては、文献Ｂに記載の方式を応用して適用可能である。これは、ハードディスクのセクタとセクタ中のバイトポジション（1セクタは通常512バイト）に応じてマスク値を足しつつECBモード暗号化を行うものである。
【００６１】
この方法では、例えばn=128とし、本実施形態で得られる256ビットブロック暗号の暗号化関数をDENCとすると、まずセクタの内容を256ビット（32バイト）ごとに分割する。分割した結果を（m1,m2,...,m16）、ただしmiは32バイトとする。このとき、mi（i=1,...,16）をDENC(mi+mul(i,SecNum))と暗号化する。ただしSecNumはセクタ番号に応じた乱数（ブロック暗号でセクタ番号を暗号化することで生成される）であり、mul(i,SecNum)はiとSecNumを有限体GF(2256)の元と見たときの乗算を表す。
【００６２】
図６に、本実施形態に係る倍ブロック長ブロック暗号化装置の動作の流れを示す。
【００６３】
まず、平文入力部１００を介して平文(xL,xR)を入力し（ステップＳ１０１）、撹拌部１０１によって中間変数(SE,TE)を求める（ステップＳ１０２）。次に、第１の調整値付き単位ブロック暗号化部１０２を用いて、TEのあるmビット部分を調整値として上記式（５）に従ってSEを暗号化し、UEを求める（ステップＳ１０３）。次に、第２の調整値付き単位ブロック暗号化部１０３を用いて、UEのあるmビット部分を調整値としてTEを暗号化しVEを求める（ステップＳ１０４）。続いて、得られた(UE,VE)を逆撹拌部１０４へ入力し、暗号文(yL,yR)を出力する（ステップＳ１０５）。
【００６４】
〔第２の実施形態〕
本発明を好適に実施した第２の実施形態について説明する。
【００６５】
図７に、本実施形態に係る倍ブロック長ブロック復号装置の構成を示す。倍ブロック長ブロック復号装置２０は、暗号文入力部２００、撹拌部２０１、第２の調整値付き単位ブロック復号部２０２、第１の調整値付き単位ブロック復号部２０３、逆撹拌部２０４、及び平文出力部２０５を有する。
【００６６】
倍ブロック長ブロック復号装置２０は、ＣＰＵとメモリとディスクとによって実現可能である。倍ブロック長ブロック復号装置２０の各機能部は、ディスクに格納されたプログラムをＣＰＵ上で実行させることにより、ソフトウェア処理で実現可能である。
【００６７】
倍ブロック長ブロック復号装置２０の各機能部について説明する。以下の説明においては、調整値付きブロック暗号のブロックサイズをｎビット、調整値の長さをｍ（１≦ｍ≦ｎ）ビットとする。図８に、撹拌部２０１、第２の調整値付き単位ブロック復号部２０２、第１の調整値付き単位ブロック復号部２０３、及び逆撹拌部１０４における情報の流れを示す。
【００６８】
暗号文入力部２００は、復号の対象となる２ｎビットの暗号文を入力する。これは、キーボードなどの文字入力装置によって実現される。
【００６９】
撹拌部２０１は、入力された２ｎビットの暗号文へ鍵付き置換mix2を適用する。mix2は、第１の実施形態における逆撹拌部１０４が用いる２ｎビット置換invmix2の逆置換である。具体的には、例えばinvmix2が式（１３）及び式（１４）で指定される、鍵付き関数Ｈ、Ｇを用いたFeistel型置換の場合、mix2は入力された暗号文(yL,yR)について、下記式（１５）、（１６）を求め、(UD,VD)を出力すればよい。
【００７０】
【数１１】
2010024003.tif 000013
ただし、H(yR)+yLの左n-mビットをwd1、右mビットをwd2とし、G(wd1)の上位nビットをZD1、下位mビットをZD2とする。m<nの場合にFeistel型置換を用いて攪拌部２０１を実現した場合の構成を図９に示す。また、もしm=nの場合は、単に、VD=yR，UD  =yL+H(yR)として(UD,VD)を出力すればよい。このときの構成を図１０に示す。
【００７１】
第２の調整値付き単位ブロック復号部２０２は、撹拌部２０１の出力をｎビットブロック二つに分けて、片方をパラメータとして他方を暗号化する。具体的には、撹拌部２０１の出力を(UD,VD)（共にｎビット）とした場合、第２の調整値付き単位ブロック復号部２０２は、第１の実施形態における第２の調整値付き単位ブロック暗号化部１０２が用いる調整値付きブロック暗号の暗号化関数TWENC2に対応した復号関数TWDEC2を用いて、（UD,VD）から下記式（１７）によってＴＤを求め、(UD,TD)を出力する。TWDEC2の鍵K2は、上記式（９）におけるK2と同じ値である。
【００７２】
【数１２】
2010024003.tif 000014
TWENC2がnビットブロック暗号の暗号化関数ENCを用いて上記式（１０）のように行われる場合、TWDEC2はｎビットブロック、ｎビット鍵のブロック暗号の暗号化関数ENCと復号関数DECとを用いて実現することも可能である。具体的には、ｎビット鍵Kとｎビット暗号文Cとｍビット調整値Tとに対して、下記式（１８）と定義する。このときのTWDECを図１１に示す。
【００７３】
【数１３】
2010024003.tif 000015
このTWDEC2を用いた場合の上記式（１７）の処理は、下記式（１９）となる。
【００７４】
【数１４】
2010024003.tif 000016
pad(cut(UD))は、単にUDのあるn-mビットを固定する処理でも良い。ただし、この方式はTWENCの場合と同様に、安全性の理由からm<n/2が必要である。
【００７５】
第１の調整値付き単位ブロック復号部２０３は、第２の調整値付き単位ブロック復号部２０２が出力する２ｎビットをｎビットブロック二つに分けて、片方をパラメータとして他方を復号する。
【００７６】
具体的には、第２の調整値付き単位ブロック復号部２０２の出力を(UD,TD)（共にｎビット）とした場合、第１の調整値付き単位ブロック復号部２０３は、第１の実施形態における第１の調整値付き単位ブロック暗号化部１０２が用いる調整値付きブロック暗号の暗号化関数TWENC1（ｍビット調整値、ｎビットブロック）に対応する復号関数TWDEC1を用いて(UD,TD)から、下記式（２０）によって、２ｎビットの(SD,TD)を出力する。TWDEC1の鍵K1は上記式（５）におけるK1と同じ値である。
【００７７】
【数１５】
2010024003.tif 000017
もしTWENC1がｎビットブロック暗号の暗号化関数ENCを用いて上記式（８）のように行われる場合、TWDEC1はTWDEC2と同様に、ｎビットブロック暗号の暗号化関数ENCと復号関すDECとを用いて、下記式（２１）のようになる。
【００７８】
【数１６】
2010024003.tif 000018
復号関数TWDEC1は第２の調整値付き単位ブロック復号部２０１が用いるTWDEC2と異なるアルゴリズムでもよいし、同じアルゴリズムでもよい。後者の場合、任意のC,K,TについてTWDEC1(K,T,C)=TWDEC2(K,T,C)となる。さらに、K1は第２の調整値付き単位ブロック復号部２０２が用いる鍵K2と同じでもよいし、独立でもよい。
【００７９】
逆撹拌部２０４は、第１の調整値付き単位ブロック復号部２０３の出力へ鍵付き置換invmix1を適用する。invmix1は、第１の実施形態における撹拌部１０１が用いる置換mix1の逆置換である。
【００８０】
平文出力部２０５は、逆撹拌部２０４から与えられる平文(xL,xR)を出力する。平文出力部２０５は、コンピュータディスプレイやプリンタなどで実現可能である。
【００８１】
図１２に、本実施形態に係る倍ブロック長ブロック復号装置２０の動作の流れを示す。
【００８２】
まず、暗号文入力部２００を介して暗号文(yL,yR)を入力し（ステップＳ２０１）、撹拌部２０１によって中間変数(UD,VD)を求める（ステップＳ２０２）。次に、第２の調整値付き単位ブロック復号部２０２を用いて、UDのあるｍビット部分を調整値として上記式（１７）に従ってVDを復号し、TDを求める（ステップＳ２０３）。続いて、第１の調整値付き単位ブロック復号部２０３を用いて、TDのあるｍビット部分を調整値としてUDを復号し、SDを求める（ステップＳ２０４）。さらに、得られた(SD,TD)を逆撹拌部２０４へ入力し、平文(xL,xR)を出力する（ステップＳ２０５）。
【００８３】
なお、上記各実施形態は本発明の好適な実施の一例であり、本発明はこれらに限定されることはない。
【００８４】
例えば、本発明は、無線又は有線のデータ通信における認証と暗号化といった用途や、ストレージ上のデータの暗号化と改ざん防止といった用途にも適用可能である。
【００８５】
このように、本発明は様々な変形が可能である。
【００８６】
この出願は、２００８年８月２９日に出願された日本出願特願２００８−２２１６３１を基礎として優先権の利益を主張するものであり、その開示の全てを引用によってここに取り込む。
【符号の説明】
【００８７】
１０    倍ブロック長ブロック暗号化装置
２０    倍ブロック長ブロック復号装置
１００    平文入力部
１０１、２０１    撹拌部
１０２    第１の調整値付き単位ブロック暗号化部
１０３    第２の調整値付き単位ブロック暗号化部
１０４、２０４    逆撹拌部
１０５    暗号文出力部
２００    暗号文入力部
２０２    第２の調整値付き単位ブロック復号部
２０３    第１の調整値付き単位ブロック暗号化部
２０５    平文出力部
【図１】
2010024003.tif 000019
【図２】
2010024003.tif 000020
【図３】
2010024003.tif 000021
【図４】
2010024003.tif 000022
【図５】
2010024003.tif 000023
【図６】
2010024003.tif 000024
【図７】
2010024003.tif 000025
【図８】
2010024003.tif 000026
【図９】
2010024003.tif 000027
【図１０】
2010024003.tif 000028
【図１１】
2010024003.tif 000029
【図１２】
2010024003.tif 000030
【図１３】
2010024003.tif 000031
【図１４】
2010024003.tif 000032
【手続補正書】
【提出日】平成21年9月4日(2009.9.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
暗号化される２ｎビット平文を入力する平文入力手段と、
前記２ｎビット平文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌手段と、
ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第２の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第３の中間変数を生成する第１の調整値付き単位ブロック暗号化手段と、
前記ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第４の中間変数を得る第２の調整値付き単位ブロック暗号化手段と、
前記第３及び第４の中間変数を連結して、ユニバーサルハッシュ関数ベースの逆撹拌を適用し、２ｎビット暗号文を生成する逆撹拌手段と、
前記２ｎビット暗号文を出力する暗号文出力手段と、
を有する倍ブロック長ブロック暗号化装置。
【請求項２】
前記ユニバーサルハッシュ関数ベースの置換及び前記ユニバーサルハッシュ関数ベースの逆置換は、ユニバーサルハッシュ関数をラウンド関数としたＦｅｉｓｔｅｌ型置換を、ｍ＝ｎの場合は１回、ｍ＜ｎの場合は２回行うことで構成されることを特徴とする、請求項１記載の倍ブロック長ブロック暗号化装置。
【請求項３】
前記暗号化関数は、平文のブロック長をｎビットとし、鍵長をｎビットとする暗号化関数であり、
前記第１の調整値付き単位ブロック暗号化手段は、前記調整値をｎビットになるようにパディングした値を平文として、該平文をｎビット鍵で前記暗号化関数を用いて暗号化し、該暗号化した結果をｎビット鍵とし、前記第１の中間変数を平文として、該平文を該ｎビット鍵で該暗号化関数を用いて暗号化することにより、前記第３の中間変数を生成し、
前記第２の調整値付き単位ブロック暗号化手段は、前記調整値をｎビットになるようにパディングした値を平文として、該平文をｎビット鍵で前記暗号化関数を用いて暗号化し、該暗号化した結果をｎビット鍵とし、前記第３の中間変数を平文として、該平文を該ｎビット鍵で該暗号化関数を用いて暗号化することにより、前記第４の中間変数を生成する、請求項１又は２記載の倍ブロック長ブロック暗号化装置。
【請求項４】
前記第１及び第２の調整値付き単位ブロック暗号化手段が用いるｍビット調整値付きｎビットブロック暗号の暗号化関数は、ｎビットブロック暗号の暗号化処理における中間変数へ調整値を加算することで調整値付きの暗号化を行うための関数である、請求項１から３のいずれか１項記載の倍ブロック長ブロック暗号化装置。
【請求項５】
復号される２ｎビット暗号文を入力する暗号文入力手段と、
前記２ｎビット暗号文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌手段と、
ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第１の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第３の中間変数を生成する第２の調整値付き単位ブロック復号手段と、
前記ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第４の中間変数を生成する第１の調整値付き単位ブロック復号手段と、
前記第３及び第４の中間変数を連結してユニバーサルハッシュ関数ベースの逆置換を適用して２ｎビット平文を生成する逆撹拌手段と、
前記２ｎビット平文を出力する平文出力手段と、
を有する倍ブロック長ブロック復号装置。
【請求項６】
ユニバーサルハッシュ関数ベースの置換及びユニバーサルハッシュ関数ベースの逆置換は、ユニバーサルハッシュ関数をラウンド関数としたＦｅｉｓｔｅｌ型置換を、ｍ＝ｎの場合は１回、ｍ＜ｎの場合は２回行うことで構成されることを特徴とする、請求項５記載の倍ブロック長ブロック復号装置。
【請求項７】
前記復号関数は、暗号文のブロック長をｎビットとし、鍵長をｎビットとする復号関数であり、
前記第１の調整値付き単位ブロック復号手段は、前記調整値をｎビットになるようにパディングした値を暗号文として、該暗号文をｎビット鍵で前記復号関数を用いて復号し、該復号した結果をｎビット鍵とし、前記第１の中間変数を暗号文として、該暗号文を該ｎビット鍵で該復号関数を用いて復号することにより、前記第３の中間変数を生成し、
前記第２の調整値付き単位ブロック復号手段は、前記調整値をｎビットになるようにパディングした値を暗号文として、該暗号文をｎビット鍵で前記復号関数を用いて復号し、該復号した結果をｎビット鍵とし、前記第１の中間変数を暗号文として、該暗号文を該ｎビット鍵で該復号関数を用いて復号することにより、前記第４の中間変数を生成する、請求項５又は６に記載の倍ブロック長ブロック暗号化装置。
【請求項８】
前記第１及び第２の調整値付き単位ブロック復号手段が用いるｍビット調整値付きｎビットブロック暗号の復号関数は、ｎビットブロック暗号Ｅの復号処理における中間変数へ調整値を加算することで調整値付きの復号を行うための関数である、請求項５から７の何れか１項記載の倍ブロック長ブロック復号装置。
【請求項９】
暗号化される２ｎビット平文を入力する平文入力処理と、
前記２ｎビット平文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌処理と、
ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第２の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第３の中間変数を生成する第１の調整値付き単位ブロック暗号化処理と、
前記ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第４の中間変数を得る第２の調整値付き単位ブロック暗号化処理と、
前記第３及び第４の中間変数を連結して、ユニバーサルハッシュ関数ベースの逆撹拌を適用し、２ｎビット暗号文を生成する逆撹拌処理と、
前記２ｎビット暗号文を出力する暗号文出力処理と、
を有する倍ブロック長ブロック暗号化方法。
【請求項１０】
復号される２ｎビット暗号文を入力する暗号文入力処理と、
前記２ｎビット暗号文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌処理と、
ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第１の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第３の中間変数を生成する第２の調整値付き単位ブロック復号処理と、
前記ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第４の中間変数を生成する第１の調整値付き単位ブロック復号処理と、
前記第３及び第４の中間変数を連結してユニバーサルハッシュ関数ベースの逆置換を適用して２ｎビット平文を生成する逆撹拌処理と、
前記２ｎビット平文を出力する平文出力処理と、
を有する倍ブロック長ブロック復号方法。
【請求項１１】
請求項９記載の倍ブロック長ブロック暗号化方法をコンピュータに実行させる、倍ブロック長ブロック暗号化プログラム。
【請求項１２】
請求項１０記載の倍ブロック長ブロック復号方法をコンピュータに実行させる、倍ブロック長ブロック復号プログラム。
【手続補正書】
【提出日】平成23年2月24日(2011.2.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
暗号化される２ｎビット平文を入力する平文入力手段と、
前記２ｎビット平文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌手段と、
ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第２の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第３の中間変数を生成する第１の調整値付き単位ブロック暗号化手段と、
前記ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第４の中間変数を得る第２の調整値付き単位ブロック暗号化手段と、
前記第３及び第４の中間変数を連結して、ユニバーサルハッシュ関数ベースの逆撹拌を適用し、２ｎビット暗号文を生成する逆撹拌手段と、
前記２ｎビット暗号文を出力する暗号文出力手段と、
を有する倍ブロック長ブロック暗号化装置。
【請求項２】
前記ユニバーサルハッシュ関数ベースの置換及び前記ユニバーサルハッシュ関数ベースの逆置換は、ユニバーサルハッシュ関数をラウンド関数としたFeistel型置換を、ｍ＝ｎの場合は１回、ｍ＜ｎの場合は２回行うことで構成されることを特徴とする、請求項１記載の倍ブロック長ブロック暗号化装置。
【請求項３】
前記暗号化関数は、平文のブロック長をｎビットとし、鍵長をｎビットとする暗号化関数であり、
前記第１の調整値付き単位ブロック暗号化手段は、前記調整値をｎビットになるようにパディングした値を平文として、該平文をｎビット鍵で前記暗号化関数を用いて暗号化し、該暗号化した結果をｎビット鍵とし、前記第１の中間変数を平文として、該平文を該ｎビット鍵で該暗号化関数を用いて暗号化することにより、前記第３の中間変数を生成し、
前記第２の調整値付き単位ブロック暗号化手段は、前記調整値をｎビットになるようにパディングした値を平文として、該平文をｎビット鍵で前記暗号化関数を用いて暗号化し、該暗号化した結果をｎビット鍵とし、前記第３の中間変数を平文として、該平文を該ｎビット鍵で該暗号化関数を用いて暗号化することにより、前記第４の中間変数を生成する、請求項１又は２記載の倍ブロック長ブロック暗号化装置。
【請求項４】
前記第１及び第２の調整値付き単位ブロック暗号化手段が用いるｍビット調整値付きｎビットブロック暗号の暗号化関数は、ｎビットブロック暗号の暗号化処理における中間変数へ調整値を加算することで調整値付きの暗号化を行うための関数である、請求項１から３のいずれか１項記載の倍ブロック長ブロック暗号化装置。
【請求項５】
復号される２ｎビット暗号文を入力する暗号文入力手段と、
前記２ｎビット暗号文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌手段と、
ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第１の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を復号してｎビットの第３の中間変数を生成する第２の調整値付き単位ブロック復号手段と、
前記ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を復号してｎビットの第４の中間変数を生成する第１の調整値付き単位ブロック復号手段と、
前記第３及び第４の中間変数を連結してユニバーサルハッシュ関数ベースの逆置換を適用して２ｎビット平文を生成する逆撹拌手段と、
前記２ｎビット平文を出力する平文出力手段と、
を有する倍ブロック長ブロック復号装置。
【請求項６】
ユニバーサルハッシュ関数ベースの置換及びユニバーサルハッシュ関数ベースの逆置換は、ユニバーサルハッシュ関数をラウンド関数としたFeistel型置換を、ｍ＝ｎの場合は１回、ｍ＜ｎの場合は２回行うことで構成されることを特徴とする、請求項５記載の倍ブロック長ブロック復号装置。
【請求項７】
前記復号関数は、暗号文のブロック長をｎビットとし、鍵長をｎビットとする復号関数であり、
前記第１の調整値付き単位ブロック復号手段は、前記調整値をｎビットになるようにパディングした値を暗号文として、該暗号文をｎビット鍵で前記復号関数を用いて復号し、該復号した結果をｎビット鍵とし、前記第１の中間変数を暗号文として、該暗号文を該ｎビット鍵で該復号関数を用いて復号することにより、前記第３の中間変数を生成し、
前記第２の調整値付き単位ブロック復号手段は、前記調整値をｎビットになるようにパディングした値を暗号文として、該暗号文をｎビット鍵で前記復号関数を用いて復号し、該復号した結果をｎビット鍵とし、前記第１の中間変数を暗号文として、該暗号文を該ｎビット鍵で該復号関数を用いて復号することにより、前記第４の中間変数を生成する、請求項５又は６に記載の倍ブロック長ブロック暗号化装置。
【請求項８】
前記第１及び第２の調整値付き単位ブロック復号手段が用いるｍビット調整値付きｎビットブロック暗号の復号関数は、ｎビットブロック暗号Ｅの復号処理における中間変数へ調整値を加算することで調整値付きの復号を行うための関数である、請求項５から７の何れか１項記載の倍ブロック長ブロック復号装置。
【請求項９】
暗号化される２ｎビット平文を入力する平文入力処理と、
前記２ｎビット平文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌処理と、
ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第２の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を暗号化してｎビットの第３の中間変数を生成する第１の調整値付き単位ブロック暗号化処理と、
前記ｍビット調整値付きｎビットブロック暗号の暗号化関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を暗号化してｎビットの第４の中間変数を得る第２の調整値付き単位ブロック暗号化処理と、
前記第３及び第４の中間変数を連結して、ユニバーサルハッシュ関数ベースの逆撹拌を適用し、２ｎビット暗号文を生成する逆撹拌処理と、
前記２ｎビット暗号文を出力する暗号文出力処理と、
を有する倍ブロック長ブロック暗号化方法。
【請求項１０】
復号される２ｎビット暗号文を入力する暗号文入力処理と、
前記２ｎビット暗号文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌処理と、
ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第１の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を復号してｎビットの第３の中間変数を生成する第２の調整値付き単位ブロック復号処理と、
前記ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を復号してｎビットの第４の中間変数を生成する第１の調整値付き単位ブロック復号処理と、
前記第３及び第４の中間変数を連結してユニバーサルハッシュ関数ベースの逆置換を適用して２ｎビット平文を生成する逆撹拌処理と、
前記２ｎビット平文を出力する平文出力処理と、
を有する倍ブロック長ブロック復号方法。
【請求項１１】
請求項９記載の倍ブロック長ブロック暗号化方法をコンピュータに実行させる、倍ブロック長ブロック暗号化プログラム。
【請求項１２】
請求項１０記載の倍ブロック長ブロック復号方法をコンピュータに実行させる、倍ブロック長ブロック復号プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
本発明の倍ブロック長ブロック復号装置は、復号される２ｎビット暗号文を入力する暗号文入力手段と、前記２ｎビット暗号文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌手段と、ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第１の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を復号してｎビットの第３の中間変数を生成する第２の調整値付き単位ブロック復号手段と、前記ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を復号してｎビットの第４の中間変数を生成する第１の調整値付き単位ブロック復号手段と、前記第３及び第４の中間変数を連結してユニバーサルハッシュ関数ベースの逆置換を適用して２ｎビット平文を生成する逆撹拌手段と、前記２ｎビット平文を出力する平文出力手段と、を有する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
本発明の倍ブロック長ブロック復号方法は、復号される２ｎビット暗号文を入力する暗号文入力処理と、前記２ｎビット暗号文へユニバーサルハッシュ関数ベースの置換を適用し、それぞれがｎビットの第１及び第２の中間変数を生成する撹拌処理と、ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第１の中間変数をｍビットに短縮した結果を調整値として前記第２の中間変数を復号してｎビットの第３の中間変数を生成する第２の調整値付き単位ブロック復号処理と、前記ｍビット調整値付きｎビットブロック暗号の復号関数を用いて、前記第３の中間変数をｍビットに短縮した結果を調整値として前記第１の中間変数を復号してｎビットの第４の中間変数を生成する第１の調整値付き単位ブロック復号処理と、前記第３及び第４の中間変数を連結してユニバーサルハッシュ関数ベースの逆置換を適用して２ｎビット平文を生成する逆撹拌処理と、前記２ｎビット平文を出力する平文出力処理と、を有する倍ブロック長ブロック復号方法である。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００７１
【補正方法】変更
【補正の内容】
【００７１】
第２の調整値付き単位ブロック復号部２０２は、撹拌部２０１の出力をｎビットブロック二つに分けて、片方をパラメータとして他方を復号する。具体的には、撹拌部２０１の出力を(UD,VD)（共にｎビット）とした場合、第２の調整値付き単位ブロック復号部２０２は、第１の実施形態における第２の調整値付き単位ブロック暗号化部１０３が用いる調整値付きブロック暗号の暗号化関数TWENC2に対応した復号関数TWDEC2を用いて、（UD,VD）から下記式（１７）によってＴＤを求め、(UD,TD)を出力する。TWDEC2の鍵K2は、上記式（９）におけるK2と同じ値である。
【国際調査報告】
2010024003.tif 000033
2010024003.tif 000034