(57)【要約】【課題】フェイステル暗号を用いた圧縮関数の安全性を向上する。【解決手段】入力部１０には平文と鍵が入力される。鍵スケジュール部１１は、入力された初期値定数に基づいてr個の乱数を生成する。定数埋込部１２は、相異なるr個の埋込定数それぞれをr個の乱数それぞれの予め定めたビット位置へ挿入することによりr個の副鍵を生成する。ラウンド関数演算部１３は、入力された平文に対して、上記r個の副鍵を用いてラウンド関数をr回繰り返し計算することで暗号文を生成する。ハッシュ値生成部１４は、暗号文と平文との排他的論理和を計算してハッシュ値を生成する。出力部１５はハッシュ値を出力する。【選択図】図６
2015025930.tif 000002
【特許請求の範囲】
【請求項１】
rを予め定めたラウンド数として、
入力された鍵に基づいてr個の乱数を生成する鍵スケジュール部と、
相異なるr個の埋込定数それぞれを上記r個の乱数それぞれの予め定めたビット位置へ挿入することによりr個の副鍵を生成する定数埋込部と、
入力された平文に対して、上記r個の副鍵を用いてラウンド関数をr回繰り返し計算することで暗号文を生成するラウンド関数演算部と、
上記暗号文と上記平文との排他的論理和を計算してハッシュ値を生成するハッシュ値生成部と、
を含む圧縮関数演算装置。
【請求項２】
請求項１に記載の圧縮関数演算装置であって、
上記埋込定数は、0以上r未満の各整数を二進法表記とした固定長のビット列である
圧縮関数演算装置。
【請求項３】
請求項２に記載の圧縮関数演算装置であって、
上記埋込定数は、log2rビットの固定長のビット列であり、
上記定数埋込部は、上記乱数の先頭log2rビットに上記埋込定数を挿入することにより上記副鍵を生成するものである
圧縮関数演算装置。
【請求項４】
rを予め定めたラウンド数として、
鍵スケジュール部が、入力された鍵に基づいてr個の乱数を生成する鍵スケジュールステップと、
定数埋込部が、相異なるr個の埋込定数を上記乱数の予め定めたビット位置へ挿入することによりr個の副鍵を生成する定数埋込ステップと、
ラウンド関数演算部が、入力された平文に対して、上記r個の副鍵を用いてラウンド関数をr回繰り返し計算することで暗号文を生成するラウンド関数演算ステップと、
ハッシュ値生成部が、上記暗号文と上記平文との排他的論理和を計算してハッシュ値を生成するハッシュ値生成ステップと、
を含む圧縮関数演算方法。
【請求項５】
請求項１から３のいずれかに記載の圧縮関数演算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関し、特に、ハッシュ関数を構成するために利用される圧縮関数の安全性を向上する技術に関する。
【背景技術】
【０００２】
共通鍵暗号の一種であるブロック暗号は、ブロックと呼ばれる固定長のデータを単位として処理する暗号の総称である。図１に、ブロックサイズがnビットのブロック暗号の構成例を示す。このブロック暗号EKは、送信者と受信者とで予め共有しておいたxビットの秘密鍵Kを用いて、nビットの平文Pからnビットの暗号文EK(P)を生成する。
【０００３】
図２に、ブロック暗号の構成例をより詳しく示す。ブロック暗号は鍵スケジュール関数（Key Schedule Function、KSF）及びラウンド関数（Round Function）から構成される。鍵スケジュール関数は、xビットの秘密鍵Kを入力とし、r個のyビットの副鍵k1,…,krを生成する。ラウンド関数は、nビットのデータとyビットの副鍵を入力とし、対応するnビットのデータを出力する。ラウンド関数は、第一ラウンドは平文Pと１つ目の副鍵k1とを用いて計算をし、第二ラウンド以降は、直前のラウンドの出力Xi（i=2,…,r）とそのラウンドに対応する副鍵ki（i=2,…,r）とを用いて計算する。ブロック暗号は、このラウンド関数をr回繰り返して暗号文EK(P)を計算する。
【０００４】
ブロック暗号の一種としてフェイステル（Feistel）暗号がある。以降で説明するフェイステル暗号は各副鍵のビット長がn/2ビットである場合の例であるが、フェイステル暗号の構成方法は複数存在し、これに限定されるものではない。
【０００５】
図３(A)に、フェイステル暗号の１ラウンド分の構成例を示す。Xiをラウンドiにおけるnビットの入力値とし、Liを入力値Xiの上位n/2ビットとし、Riを入力値Xiの下位n/2ビットとし、kiをラウンドiにおける副鍵とする。任意のラウンド関数Fを定めておき、ラウンドiにおける出力値Xi+1を以下の式(1)〜(3)で計算する。ラウンド関数Fは入力のビット長と出力のビット長とが等しい効率的に計算可能な関数であればどのような演算を行うものであってもよい。
【０００６】
【数１】
2015025930.tif 000003
【０００７】
ここで、以下の記号は、排他的論理和演算を表す。
【０００８】
【数２】
2015025930.tif 000004
【０００９】
また、以下の記号は、ビット列Aとビット列Bとを連結することを表す。
【００１０】
【数３】
2015025930.tif 000005
【００１１】
フェイステル暗号では、最終ラウンド（ラウンドr）に限り、出力における上位のビット列と下位のビット列との入れ替え処理を省略することが多い。図３(B)に、フェイステル暗号の最終ラウンドの構成例を示す。フェイステル暗号の最終ラウンドの出力値Xr+1は、以下の式(4)〜(6)のように計算される。
【００１２】
【数４】
2015025930.tif 000006
【００１３】
ブロック暗号は、暗号利用モードを経て、ハッシュ関数の構成部品として使われる。ブロック暗号をハッシュ関数で利用されるように構成することをハッシュ関数モードと呼び、その構成単位を圧縮関数と呼ぶ。
【００１４】
国際標準規格（International Standard Organization、ISO）で標準化されている代表的なフェイステル暗号がいくつか存在する。このようなフェイステル暗号は、例えば、非特許文献１や非特許文献２に記載されたものが挙げられる。これらの標準化されたフェイステル暗号を用いた圧縮関数では、次のようにハッシュ値H(M)を生成する。まず、秘密鍵Kの値を予め定めた初期値定数IV（Initial Value）に固定する。次に、平文Pをハッシュ値の計算対象であるメッセージMとし、メッセージMを初期値定数IVで暗号化して暗号文EIV(M)を生成する。そして、暗号文EIV(M)とメッセージMとの排他的論理和の結果をメッセージMのハッシュ値H(M)として出力する。すなわち、フェイステル暗号を用いた圧縮関数の出力は、以下の式(7)のように計算される。
【００１５】
【数５】
2015025930.tif 000007
【００１６】
なお、入力メッセージMのビット長がnビットではない場合には、値の付け足しやハッシュ値演算の繰り返し処理が必要となるが、この発明ではそれらの操作による影響はないため、以降の説明では明示的な記載は省略する。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】Kazumaro Aoki, Tetsuya Ichikawa, Masayuki Kanda, MitsuruMatsui, Shiho Moriai, Junko Nakajima, and Toshio Tokita, “Camellia: A 128-bit block cipher suitable for multiple platforms - design and analysis”, Selected Areas in Cryptography 2000, Springer-Verlag, volume 2012 of LNCS, pages 39-56, 2001.
【非特許文献２】Taizo Shirai, Kyoji Shibutani, Toru Akishita, Shiho Moriai, and Tetsu Iwata, “The 128-bit blockcipher CLEFIA (extended abstract)”, Fast Software Encryption 2007, Springer-Verlag, volume 4593 of LNCS, pages 181-195, 2007.
【非特許文献３】Kazumaro Aoki and Yu Sasaki, “Preimage attacks on one-block MD4, 63-step MD5 and more”, Selected Areas in Cryptography SAC 2008, Springer-Verlag, volume 5381 of LNCS, pages 103-119, 2009.
【発明の概要】
【発明が解決しようとする課題】
【００１８】
ハッシュ関数に対する攻撃手法として、最終ラウンド（ラウンドr）と第一ラウンド（ラウンド1）が繋がっているとみなす方法が存在する。この攻撃方法の詳細は、非特許文献３に記載されている。
【００１９】
図４に、フェイステル暗号において最終ラウンドと第一ラウンドを繋げたときの構造を示す。上述の通り、フェイステル暗号では最終ラウンドの出力において上位のビット列と下位のビット列の入れ替え処理を行わない場合が多い。このとき、最終ラウンドにおける副鍵krと第一ラウンドにおける副鍵k1が等しくなっていると、最終ラウンドのラウンド関数Fの出力と第一ラウンドのラウンド関数Fの出力とが等しくなる。その結果、２ラウンド分の計算結果が互いに打ち消すことになる。具体的な演算結果を式(8)に示す。
【００２０】
【数６】
2015025930.tif 000008
【００２１】
２ラウンド演算した結果が上位のビット列と下位のビット列を入れ替えるだけとなってしまうため、ハッシュ関数として脆弱な構造であることがわかる。
【００２２】
非特許文献１や非特許文献２に記載されているフェイステル暗号では、各副鍵k1,…,krがどのような値をとるかは秘密鍵Kに依存しており、ランダムに決定される。各副鍵の値がランダムに決定される場合には、第一ラウンドの副鍵k1と最終ラウンドの副鍵krの値が等しくなる確率はゼロではない。したがって、従来のフェイステル暗号を用いた圧縮関数は脆弱な構造となる可能性が存在する。
【００２３】
この発明は、フェイステル暗号を用いた圧縮関数において、上記の脆弱性を解決し、安全性を向上することを目的とする。
【課題を解決するための手段】
【００２４】
上記の課題を解決するために、この発明の圧縮関数演算装置は、鍵スケジュール部と定数埋込部とラウンド関数演算部とハッシュ値生成部とを含む。以下では、rを予め定めたラウンド数とする。鍵スケジュール部は、入力された鍵に基づいてr個の乱数を生成する。定数埋込部は、相異なるr個の埋込定数それぞれをr個の乱数それぞれの予め定めたビット位置へ挿入することによりr個の副鍵を生成する。ラウンド関数演算部は、入力された平文に対して、r個の副鍵を用いてラウンド関数をr回繰り返し計算することで暗号文を生成する。ハッシュ値生成部は、暗号文と平文との排他的論理和を計算してハッシュ値を生成する。
【発明の効果】
【００２５】
この発明によれば、フェイステル暗号で用いるすべての副鍵に相異なる埋込定数を挿入するため、最終ラウンドにおける副鍵krと第一ラウンドにおける副鍵k1とが等しくなることがない。これにより、フェイステル暗号を用いた圧縮関数において脆弱な鍵が生成される可能性を排除することができ、安全性が向上する。
【図面の簡単な説明】
【００２６】
【図１】図１は、ブロック暗号の構成を例示する図である。
【図２】図２は、ブロック暗号の詳細な構成を例示する図である。
【図３】図３（Ａ）は、フェイステル暗号の１ラウンド分の構成を例示する図である。図３（Ｂ）は、フェイステル暗号の最終ラウンドの構成を例示する図である。
【図４】図４は、最終ラウンドと第一ラウンドを繋いだ構成とする攻撃方法の例を説明する図である。
【図５】図５は、ブロック暗号を用いた圧縮関数の構成を例示する図である。
【図６】図６は、圧縮関数演算装置の機能構成を例示する図である。
【図７】図７は、圧縮関数演算方法の処理フローを例示する図である。
【図８】図８は、副鍵の構成を例示する模式図である。
【発明を実施するための形態】
【００２７】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２８】
［実施形態］
図６を参照して、実施形態に係る圧縮関数演算装置の機能構成の一例を説明する。実施形態に係る圧縮関数演算装置１は、入力部１０、鍵スケジュール部１１、定数埋込部１２、ラウンド関数演算部１３、ハッシュ値生成部１４、出力部１５、制御部１０１及びメモリ１０２を含む。圧縮関数演算装置１は、例えば、中央演算処理装置（Central Processing Unit、CPU）、主記憶装置（Random Access Memory、RAM）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。圧縮関数演算装置１は、例えば、制御部１０１の制御のもとで各処理を実行する。圧縮関数演算装置１に入力されたデータや各処理で得られたデータは、例えば、メモリ１０２に格納され、メモリ１０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００２９】
図７を参照して、圧縮関数演算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００３０】
ステップＳ１０において、入力部１０へnビットの平文M及びxビットの鍵Kが入力される。平文Mはハッシュ値を生成する対象となるビット列であり、どのような値であってもよい。鍵Kは予め定めた初期値定数IVもしくは任意の一方向性関数が出力する乱数である。鍵Kは鍵スケジュール部１１へ入力される。平文Mはラウンド関数演算部１３及びハッシュ値生成部１４へ入力される。
【００３１】
ステップＳ１１において、鍵スケジュール部１１は、鍵Kに基づいてr個のn/2ビットの乱数s1,…,srを生成する。rは予め定めた自然数であり、ブロック暗号におけるラウンド数である。乱数s1,…,srは定数埋込部１２へ入力される。鍵Kからr個の乱数s1,…,srを生成する方法は限定されず、例えば、既存のフェイステル暗号で用いられる鍵スケジュール関数を適用すればよい。
【００３２】
ステップＳ１２において、定数埋込部１２は、r個の相異なる値である埋込定数c1,…,crを、乱数s1,…,srの予め定めたビット位置へ挿入することにより副鍵k1,…,krを生成する。埋込定数c1,…,crは重複しないr個の値であればどのような値でもよい。例えば、0以上r未満の各整数を二進法表記とした固定長のビット列とすることができる。埋込定数の長さは短いほど全体の処理効率を良くすることができる。埋込定数を0以上r未満の各整数とするならば、各ビット列の長さはlog2rビットあれば足りる。したがって、埋込定数c1,…,crを0以上r未満の各整数として、log2rビットの固定長のビット列とした場合が最も効率が良くなる。埋込定数ciを挿入する乱数siのビット位置は各副鍵k1,…,krで統一されていればどのような位置でもよい。例えば、乱数siの先頭ビットに埋込定数ciを挿入するようにすれば桁あふれなどを考慮する必要がなく安全である。生成したr個の副鍵k1,…,krはラウンド関数演算部１３へ入力される。
【００３３】
図８に、定数埋込部１２が生成した副鍵k1,…,krの構成を示す。この例では、副鍵k1,…,krは固定長であり、すべてn/2ビットのビット列である。副鍵k1,…,krはそれぞれ先頭log2rビットに相異なる埋込定数c1,…,crが挿入されている。各埋込定数ciの値は、i=1,…,rとして、i-1を二進法表記としたビット列である。つまり、第一ラウンドにおける副鍵k1は先頭log2rビットが「0…00」であり、第二ラウンドにおける副鍵k2は先頭log2rビットが「0…01」であり、最終ラウンドにおける副鍵krは先頭log2rビットが「1…11」である。
【００３４】
ラウンド関数演算部１３は、入力された平文Mに対して、副鍵k1,…,krを用いてラウンド関数Fをr回繰り返し計算することで暗号文EIV(M)を生成する。ラウンド関数Fは、従来のフェイステル暗号と同様に、入力のビット長と出力のビット長とが等しい効率的に計算可能な関数であればどのような演算を行うものであってもよい。暗号文EIV(M)はハッシュ値生成部１４へ入力される。
【００３５】
ラウンド関数演算部１３の処理をより具体的に説明する。ステップＳ１３ａにおいて、ラウンド関数演算部１３は、平文Mを値X1へ代入する。同時に、カウンタ変数iを1に初期化する。ステップＳ１３ｂにおいて、ラウンド関数演算部１３は、値Xiを入力として副鍵kiを用いてラウンド関数Fを実行し、その出力を値Xi+1とする。具体的には、上述の式(1)〜(3)を計算する。ただし、カウンタ変数iがラウンド数rに等しい場合、すなわち最終ラウンドの場合には、上述の式(4)〜(6)を計算する。ステップＳ１３ｃにおいて、ラウンド関数演算部１３は、カウンタ変数iがラウンド数r未満であるか否かを確認する。カウンタ変数iがラウンド数r未満であれば、ステップＳ１３ｄにおいて、カウンタ変数iに1を加算した上で、ステップＳ１３ｂへ処理を戻す。カウンタ変数iがラウンド数r以上であれば、値Xi（=Xr）を暗号文EIV(M)として出力し、後続のステップＳ１４へ処理を進める。
【００３６】
ステップＳ１４において、ハッシュ値生成部１４は、暗号文EIV(M)と平文Mの排他的論理和を計算してハッシュ値H(M)を生成する。具体的には、上述の式(7)を計算する。ハッシュ値H(M)は出力部１５へ入力される。
【００３７】
ステップＳ１５において、出力部１５はハッシュ値H(M)を出力する。
【００３８】
実施形態の圧縮関数演算装置は、副鍵k1,…,krのそれぞれ同じビット位置に相異なる埋込定数c1,…,crを挿入するように構成することで、第一ラウンドの副鍵k1と最終ラウンドの副鍵krが等しくなる可能性をゼロとすることができる。これにより、非特許文献３に記載されるような最終ラウンドと第一ラウンドが繋がっているとみなす攻撃方法に対しても堅牢な構造とすることができる。したがって、フェイステル暗号を用いた圧縮関数の安全性を向上することができる。
【００３９】
なお、実施形態の圧縮関数演算装置は、副鍵の一部を定数値に固定することで、従来の圧縮関数を演算するよりも１ラウンド分の撹拌が弱くなる。したがって、従来の圧縮関数と同程度の安全性を実現するためにはラウンド数を増やすなどの対処が必要となり、効率が若干悪化する場合がある。しかしながら、埋込定数の長さはラウンド数の対数値log2rビットまで抑えることが可能であるため、効率の悪化は無視できる程度とすることができる。
【００４０】
［応用例］
この発明の圧縮関数演算技術は、圧縮関数を用いて構成されるハッシュ関数を演算するハッシュ関数演算技術に応用することが可能である。ブロック暗号を用いた圧縮関数によりハッシュ関数を構成する方法として、Merkle-Damgard構成が知られている。Merkle-Damgard構成の詳細は、「I. Damgard, “A design principle for hash functions”, CRYPT 1989, vol. 435, pp. 416-427, 1989」などを参照されたい。Merkle-Damgard構成は、MD5（Message Digest Algorithm 5）やSHA-1（Secure Hash Algorithm）等の古典的なハッシュ関数の多くが採用している構成である。したがって、この発明の圧縮関数演算技術は、ブロック暗号を用いたハッシュ関数の安全性を向上することができる。
【００４１】
ハッシュ関数は、メッセージ認証符号や擬似乱数生成器、公開鍵暗号、ディジタル署名など多くの暗号プリミティブを構成するために利用されている。したがって、この発明の圧縮関数演算技術は、ハッシュ関数を用いて構成されるすべての暗号プリミティブに適用することが可能である。
【００４２】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４３】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００４４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００４７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００４８】
１  圧縮関数演算装置
１０  入力部
１１  鍵スケジュール部
１２  定数埋込部
１３  ラウンド関数演算部
１４  ハッシュ値生成部
１５  出力部
１０１  制御部
１０２  メモリ
【図１】
2015025930.tif 000009
【図２】
2015025930.tif 000010
【図３】
2015025930.tif 000011
【図４】
2015025930.tif 000012
【図５】
2015025930.tif 000013
【図６】
2015025930.tif 000014
【図７】
2015025930.tif 000015
【図８】
2015025930.tif 000016