ハッシュ関数の安全性評価装置、方法及びプログラム
【課題】ＭＤファミリーのハッシュ関数の安全性を評価する技術を提供する。
【解決手段】ＭＮを０からＮ−１までの整数の集合として、複数の自然数ｘのそれぞれに対して、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣと、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２とから構成される複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）を決定する。複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）のそれぞれについて、１≦ｊ≦（ｋ１−１）又はｋ２≦ｊ≦ｘという条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＢ＝φでありかつｋ１≦ｊ≦（ｋ２−１）という条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＡ＝φであるという独立条件を満たすか判定する。独立条件を満たす組に対応するｘの中で最大のｘを出力する。
【解決手段】ＭＮを０からＮ−１までの整数の集合として、複数の自然数ｘのそれぞれに対して、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣと、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２とから構成される複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）を決定する。複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）のそれぞれについて、１≦ｊ≦（ｋ１−１）又はｋ２≦ｊ≦ｘという条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＢ＝φでありかつｋ１≦ｊ≦（ｋ２−１）という条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＡ＝φであるという独立条件を満たすか判定する。独立条件を満たす組に対応するｘの中で最大のｘを出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号学的ハッシュ関数の安全性の評価技術に関する。特に、ハッシュ関数の中間一致型原像攻撃に対する安全性の評価技術に関する。
【背景技術】
【０００２】
暗号学的ハッシュ関数Ｈ（以下、ハッシュ関数Ｈとする。）は、任意の長さのビット列Ｍを入力して、固定長のビット列Ｈ（Ｍ）を出力する関数である。
【０００３】
与えられたｖに対してｖ＝Ｈ（ｕ）となるｕを見つけることをハッシュ関数Ｈに対する原像攻撃という。ハッシュ関数Ｈは、その原像攻撃を実行することが計算量的に困難であることが求められる。
【０００４】
ハッシュ関数Ｈは、いわゆるマークル・ダンガード構造を有しており、ステップ関数Ｒの繰り返しを用いて定義されている。ステップ関数Ｒの繰り返し数が多いほどハッシュ関数Ｈの安全性が増す。
【０００５】
非特許文献１には、ハッシュ関数であるＭＤ４、ＭＤ５に対して、ステップ関数Ｒの繰り返しの回数ｘがいくつ以下だと原像攻撃が可能であり、安全性を確保することができないかについて記載されている。具体的には、ＭＤ５ではステップ関数Ｒの繰り返しの回数ｘが５５以下の場合には原像攻撃が可能である旨が記載されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Kazumaro Aoki19, Yu Sasaki, “Preimage Attacks on One-Block MD4, 63-Step MD5 and More”, SAC 2008
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１には、ハッシュ関数の安全性を評価する一般的な手法は開示されておらず、ＭＤ４、ＭＤ５以外の他のハッシュ関数についての安全性を評価することができないという課題がある。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、ＭＮを０からＮ−１までの整数の集合として、複数の自然数ｘのそれぞれに対して、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣと、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２とから構成される複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）を決定する。メッセージ拡大関数Ｗｊ（Ｍｉ）が用いるＭｉを構成するビットの位置を示すｊｗ個の整数ｗ１，…，ｗｊｗの集合をＮｊ＝｛ｗ１，…，ｗｊｗ｝として、複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）のそれぞれについて、１≦ｊ≦（ｋ１−１）又はｋ２≦ｊ≦ｘという条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＢ＝φでありかつｋ１≦ｊ≦（ｋ２−１）という条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＡ＝φであるという独立条件を満たすか判定する。独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対応するｘの中で最大のｘを出力する。
【発明の効果】
【０００９】
いわゆるＭＤファミリーのハッシュ関数の安全性を評価することができる。
【図面の簡単な説明】
【００１０】
【図１】ハッシュ関数の安全性評価装置の例の機能ブロック図。
【図２】ハッシュ関数の安全性評価方法のフローチャートを例示する図。
【図３】ハッシュ関数の構造を説明するための図。
【図４】ハッシュ関数の構造を説明するための図。
【図５】この発明が安全性の評価と基準となる理由を説明するための図。
【発明を実施するための形態】
【００１１】
以下、この発明の一実施形態について、詳細に説明する。
【００１２】
［対象となるハッシュ関数について］
安全性の評価の対象となるハッシュ関数はいわゆるＭＤファミリーに属するハッシュ関数である。そこで、まずＭＤファミリーに属するハッシュ関数の説明を行う。
【００１３】
ＭＤファミリーに属するハッシュ関数Ｈは、以下に述べる構造を有する。
【００１４】
図３に例示するように、ハッシュ関数Ｈに入力されたメッセージＭはＮの倍数のビット数となるようにパディングされる。Ｍは任意長の長さのビット列であり、Ｎは所定の自然数である。パディングされたビット列ｐａｄ（Ｍ）と表記する。
【００１５】
パディングされたビット列ｐａｄ（Ｍ）は、ｐａｄ（Ｍ）＝Ｍ１‖Ｍ２‖…‖ＭＬとＬ個のビット列に分割される。各Ｍｉ（ｉ＝１，…，Ｌ）は、Ｎ個のビットから構成される。
【００１６】
ＩＶ（Ｉｎｉｔｉａｌ Ｖａｌｕｅ）を所定の定数とし、Ｈ０＝ＩＶとし、ｉ＝１，…，Ｌとして、Ｈｉ＝ｃｆ（Ｈｉ−１，Ｍｉ）の演算を順次繰り返すことにより得られたＨＬが入力されたメッセージＭに対するハッシュ値Ｈ（Ｍ）となる。
【００１７】
Ｈ０＝ＩＶ
Ｈｉ＝ｃｆ（Ｈｉ−１，Ｍｉ），ｉ＝１，…，Ｌ
ｃｆ（Ｈｉ−１，Ｍｉ）は、圧縮関数と呼ばれる関数である。圧縮関数ｃｆ（Ｈｉ−１，Ｍｉ）は、図４に例示するように、Ｈｉ−１及びＭｉを入力として用いて、ｐｉ１＝Ｈｉ−１とし、ｊ＝１，…，ｘとして、ｐｉｊ＋１＝Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の演算を順次繰り返すことにより得られたｐｉｘ＋１とｐｉ１とを加算した値を出力する。
【００１８】
ｐｉ１＝Ｈｉ−１
ｐｉｊ＋１＝Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ），ｊ＝１，…，ｘ
ｃｆ（Ｈｉ−１，Ｍｉ）＝ｐｉｘ＋１＋ｐｉ１
Ｗｊ（Ｍｉ）は、メッセージ拡大関数と呼ばれる関数であり、入力されたビット列Ｍｉを構成する全部又は一部のビットを用いて出力値を計算する。用いるビットはｊに応じて異なる。メッセージ拡大関数Ｗｊ（Ｍｉ）が用いる、Ｍｉを構成するビットの位置を示すｊｗ個の整数ｗ１，…，ｗｊｗの集合をＮｊ＝｛ｗ１，…，ｗｊｗ｝と表記する。
【００１９】
Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）は、ステップ関数と呼ばれる関数であり、Ｗｊ（Ｍｉ）及びｐｉｊを入力として用いて出力値を計算する。ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）はＷｊ（Ｍｉ）に対して可逆関数であり、ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の出力値とＷｊ（Ｍｉ）の値から、入力値であるｐｉｊを計算可能であるとする。また、ｃｆ（Ｈｉ−１，Ｍｉ）の出力値Ｈｉのビット数とＲ（Ｗｊ（Ｍｉ），ｐｉｊ）の出力値ｐｉｊ＋１のビット数とが同じであるとする。
【００２０】
ｘはステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の演算の繰り返しの回数である。一般に繰り返しの回数ｘが多いほどハッシュ関数Ｈの安全性が増す。この発明は、原像攻撃が可能であり、安全性を確保することができない繰り返しの回数ｘを求めて、安全性を評価するための指標として用いる。
【００２１】
メッセージ拡大関数Ｗｊ（Ｍｉ）及びステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）は、仕様に応じて適宜設計される。
【００２２】
［実施形態］
ハッシュ関数の安全性評価装置は、図１に示すように、設定部１、決定部２、判定部３、出力部４、制御部５を例えば含む。このハッシュ関数の安全性評価装置が、図２に示すハッシュ関数の安全性方法を例えば実行する。
【００２３】
設定部１は、順次異なる自然数をｘに設定する。この例では、まず、ｘ＝１とする（ステップＳ１１）。その後、ｘ＝Ｘとなるまで、順次ｘに自然数を設定する（ステップＳ１２，ステップＳ１３）。Ｘは所定の整数である。
【００２４】
また、制御部５は、ｔｅｍｐに１を代入して、変数ｔｅｍｐを初期化する（ステップＳ４０）。
【００２５】
決定部２は、ＭＮを０からＮ−１までの整数の集合として、設定部１で設定されたｘに対して、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣと、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２とから構成される複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）を決定する（ステップＳ２）。複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）についての情報は、判定部３に送られる。
【００２６】
決定部２の具体例を以下に説明する。決定部２は、図１に例示するように、集合決定部２１と整数決定部２２とを含む。
【００２７】
まず、集合決定部２１が、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣを決定する。
【００２８】
その後、整数決定部２２が、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２を決定する
判定部３は、ある組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）について、１≦ｊ≦（ｋ１−１）又はｋ２≦ｊ≦ｘという条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＢ＝φでありかつｋ１≦ｊ≦（ｋ２−１）という条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＡ＝φであるという独立条件を満たすか判定する（ステップＳ３１）。独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）についての情報は、出力部４に送られる。
【００２９】
Ｎｊは、安全性の評価の対象となっているハッシュ関数Ｈのメッセージ拡大関数Ｗｊ（Ｍｉ）が用いる、Ｍｉを構成するビットの位置を示すｊｗ個の整数ｗ１，…，ｗｊｗの集合Ｎｊ＝｛ｗ１，…，ｗｊｗ｝である。
【００３０】
図２に示すように、制御部５は、あるｘに対応するすべての組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）について独立条件を満たすか判定されたか判断し（ステップＳ３２）。すべての組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）について独立条件を満たすか判定されていな場合には、制御部５は、まだ独立条件を満たすか判定されていない組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対して判定部３が独立条件を満たすか判定するように制御する。これにより、判定部３は、あるｘに対応するすべての組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）の独立条件を判定することになる。
【００３１】
出力部４は、独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対応するｘの中で最大のｘを出力する（ステップＳ４）。後述するように、ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の繰り返しの回数がｘ以下の場合には、後述するように、ハッシュ関数Ｈに対して原像攻撃の一種である中間値一致型原像攻撃が可能であり、安全性を確保することができない。このため、出力されたｘは、安全性の評価の指標となる。
【００３２】
ステップＳ３１（図２）において、組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）が独立条件を満たすと判定された場合には、制御部５は、その組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対応するｘとｔｅｍｐとを比較する（ステップＳ４１）。
【００３３】
ｘ＞ｔｅｍｐであれば、制御部５はｔｅｍｐにｘを代入する（ステップＳ４２）。その後、ステップＳ３２に進む。ｘ≦ｔｅｍｐであれば、ステップＳ３２に進む。
【００３４】
ステップＳ３２において、すべての組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）について独立条件を判定したと判断された場合には、制御部５は、ｘ＝Ｘであるか判定する（ステップＳ１２）。
【００３５】
ｘ＝Ｘであれば、出力部４はｔｅｍｐを出力する（ステップＳ４）。ステップＳ４１、ステップＳ４２、ステップＳ１２及びステップＳ１３の処理により、ｔｅｍｐの値はｘの最大値となっている。ｘ＝Ｘでなければ、設定部１は、ｘ＋１をｘとする（ステップＳ１３）。その後、ステップＳ２に進む。
【００３６】
［ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の繰り返しの回数がｘ以下の場合には安全性を確保することができない理由］
集合ＭＡを構成する整数をｍＡ１，ｍＡ２，…，ｍＡＮＡと表記する。すなわち、集合ＭＡ＝｛ｍＡ１，ｍＡ２，…，ｍＡＮＡ｝とする。ＮＡは、集合ＭＡを構成する整数の数である。同様に、集合ＭＢを構成する整数をｍＢ１，ｍＢ２，…，ｍＢＮＢと表記する。すなわち、集合ＭＢ＝｛ｍＢ１，ｍＢ２，…，ｍＢＮＢ｝とする。ＮＢは、集合ＭＢを構成する整数の数である。同様に、集合ＭＣを構成する整数をｍＣ１，ｍＣ２，…，ｍＣＮＣと表記する。すなわち、集合ＭＣ＝｛ｍＣ１，ｍＣ２，…，ｍＣＮＣ｝とする。ＮＣは、集合ＭＣを構成する整数の数である。
【００３７】
独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）の情報、及び、ｃｆ（Ｈｉ−１，Ｍｉ）の値が公知であるとする。
【００３８】
（１）まず、ＭｉのｍＣ１，ｍＣ２，…，ｍＣＮＣ番目の位置のビットの値ｂ（ｍＣ１），ｂ（ｍＣ２），…，ｂ（ｍＣＮＣ）とｐｉｋ１とを所定の値に固定する。
【００３９】
（２）次に、ＭｉのｍＢ１，ｍＢ２，…，ｍＢＮＢ番目の位置のビットの値の組（ｂ（ｍＢ１），ｂ（ｍＢ２），…，ｂ（ｍＢＮＢ））を複数生成し、各組に対応するｐｉｋ２の値をｐｉｋ１及びステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）を用いて計算する。ｉ＝ｋ１からｋ２−１までのＷｊ（Ｍｉ）は、ＭｉのｍＡ１，ｍＡ２，…，ｍＡＮＡ番目の位置のビットの値ｂ（ｍＡ１），ｂ（ｍＡ２），…，ｂ（ｍＡＮＡ）を用いないため、これらのビットの値ｂ（ｍＡ１），ｂ（ｍＡ２），…，ｂ（ｍＡＮＡ）がなくても、各組に対応するｐｉｋ２の値を計算することができる。
【００４０】
（３）次に、ＭｉのｍＡ１，ｍＡ２，…，ｍＡＮＡ番目の位置のビットの値の組（ｂ（ｍＡ１），ｂ（ｍＡ２），…，ｂ（ｍＡＮＡ））を複数生成し、各組に対応するｐｉｋ２の値をｐｉｋ１及びステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の逆関数Ｒ−１（Ｗｊ（Ｍｉ），ｐｉｊ＋１）と、関係式ｐｉｘ＋１＝ｃｆ（Ｈｉ−１，Ｍｉ）−ｐｉ１を用いて計算する。ｉ＝１からｋ１−１までのＷｊ（Ｍｉ）及びｉ＝ｋ２からｘまでのＷｊ（Ｍｉ）は、ＭｉのｍＢ１，ｍＢ２，…，ｍＢＮＢ番目の位置のビットの値ｂ（ｍＢ１），ｂ（ｍＢ２），…，ｂ（ｍＢＮＢ）を用いないため、これらのビットの値ｂ（ｍＢ１），ｂ（ｍＢ２），…，ｂ（ｍＢＮＢ）がなくても、各組に対応するｐｉｋ２の値を計算することができる。
【００４１】
上記（２）で求められたｐｉｋ２の値と上記（３）で求められたｐｉｋ２の値とで一致するものがあった場合には、その一致するｐｉｋ２に対応する組（ｂ（ｍＢ１），ｂ（ｍＢ２），…，ｂ（ｍＢＮＢ））及び組（ｂ（ｍＡ１），ｂ（ｍＡ２），…，ｂ（ｍＡＮＡ））によりＭｉが定まる。ＭｉのｍＣ１，ｍＣ２，…，ｍＣＮＣ番目の位置のビットの値としては、上記（１）で定めたｂ（ｍＣ１），ｂ（ｍＣ２），…，ｂ（ｍＣＮＣ）をそれぞれ用いる。
【００４２】
このように、独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）の情報、及び、ｃｆ（Ｈｉ−１，Ｍｉ）の値が公知であるとすると、このように、原像攻撃の一種であるいわゆる中間一致型原像攻撃が可能であり、ｃｆ（Ｈｉ−１，Ｍｉ）の値からＭｉを計算することができる可能性がある。
【００４３】
一般に、ＭＤファミリーのハッシュ関数Ｈの圧縮関数ｃｆ（Ｈｉ−１，Ｍｉ）についての原像攻撃が可能であるとすると、そのハッシュ関数Ｈ自体も原像攻撃が可能であることが知られている。
【００４４】
ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の繰り返しの回数がｘ以下の場合には、独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）が存在し、その存在が知られている可能性がある。
【００４５】
このため、ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の繰り返しの回数がｘ以下の場合には、ハッシュ関数の安全性を確保することができないと言えるのである。
【００４６】
［変形例等］
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００４７】
例えば、ハッシュ関数の安全性評価装置は、コンピュータによって実現することができる。この場合、これらの装置の各部はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これらの装置の各部が、コンピュータ上で実現される。
【００４８】
このプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００４９】
１ 設定部
２ 決定部
２１ 集合決定部
２２ 整数決定部
３ 判定部
４ 出力部
５ 制御部
【技術分野】
【０００１】
この発明は、暗号学的ハッシュ関数の安全性の評価技術に関する。特に、ハッシュ関数の中間一致型原像攻撃に対する安全性の評価技術に関する。
【背景技術】
【０００２】
暗号学的ハッシュ関数Ｈ（以下、ハッシュ関数Ｈとする。）は、任意の長さのビット列Ｍを入力して、固定長のビット列Ｈ（Ｍ）を出力する関数である。
【０００３】
与えられたｖに対してｖ＝Ｈ（ｕ）となるｕを見つけることをハッシュ関数Ｈに対する原像攻撃という。ハッシュ関数Ｈは、その原像攻撃を実行することが計算量的に困難であることが求められる。
【０００４】
ハッシュ関数Ｈは、いわゆるマークル・ダンガード構造を有しており、ステップ関数Ｒの繰り返しを用いて定義されている。ステップ関数Ｒの繰り返し数が多いほどハッシュ関数Ｈの安全性が増す。
【０００５】
非特許文献１には、ハッシュ関数であるＭＤ４、ＭＤ５に対して、ステップ関数Ｒの繰り返しの回数ｘがいくつ以下だと原像攻撃が可能であり、安全性を確保することができないかについて記載されている。具体的には、ＭＤ５ではステップ関数Ｒの繰り返しの回数ｘが５５以下の場合には原像攻撃が可能である旨が記載されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Kazumaro Aoki19, Yu Sasaki, “Preimage Attacks on One-Block MD4, 63-Step MD5 and More”, SAC 2008
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１には、ハッシュ関数の安全性を評価する一般的な手法は開示されておらず、ＭＤ４、ＭＤ５以外の他のハッシュ関数についての安全性を評価することができないという課題がある。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、ＭＮを０からＮ−１までの整数の集合として、複数の自然数ｘのそれぞれに対して、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣと、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２とから構成される複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）を決定する。メッセージ拡大関数Ｗｊ（Ｍｉ）が用いるＭｉを構成するビットの位置を示すｊｗ個の整数ｗ１，…，ｗｊｗの集合をＮｊ＝｛ｗ１，…，ｗｊｗ｝として、複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）のそれぞれについて、１≦ｊ≦（ｋ１−１）又はｋ２≦ｊ≦ｘという条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＢ＝φでありかつｋ１≦ｊ≦（ｋ２−１）という条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＡ＝φであるという独立条件を満たすか判定する。独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対応するｘの中で最大のｘを出力する。
【発明の効果】
【０００９】
いわゆるＭＤファミリーのハッシュ関数の安全性を評価することができる。
【図面の簡単な説明】
【００１０】
【図１】ハッシュ関数の安全性評価装置の例の機能ブロック図。
【図２】ハッシュ関数の安全性評価方法のフローチャートを例示する図。
【図３】ハッシュ関数の構造を説明するための図。
【図４】ハッシュ関数の構造を説明するための図。
【図５】この発明が安全性の評価と基準となる理由を説明するための図。
【発明を実施するための形態】
【００１１】
以下、この発明の一実施形態について、詳細に説明する。
【００１２】
［対象となるハッシュ関数について］
安全性の評価の対象となるハッシュ関数はいわゆるＭＤファミリーに属するハッシュ関数である。そこで、まずＭＤファミリーに属するハッシュ関数の説明を行う。
【００１３】
ＭＤファミリーに属するハッシュ関数Ｈは、以下に述べる構造を有する。
【００１４】
図３に例示するように、ハッシュ関数Ｈに入力されたメッセージＭはＮの倍数のビット数となるようにパディングされる。Ｍは任意長の長さのビット列であり、Ｎは所定の自然数である。パディングされたビット列ｐａｄ（Ｍ）と表記する。
【００１５】
パディングされたビット列ｐａｄ（Ｍ）は、ｐａｄ（Ｍ）＝Ｍ１‖Ｍ２‖…‖ＭＬとＬ個のビット列に分割される。各Ｍｉ（ｉ＝１，…，Ｌ）は、Ｎ個のビットから構成される。
【００１６】
ＩＶ（Ｉｎｉｔｉａｌ Ｖａｌｕｅ）を所定の定数とし、Ｈ０＝ＩＶとし、ｉ＝１，…，Ｌとして、Ｈｉ＝ｃｆ（Ｈｉ−１，Ｍｉ）の演算を順次繰り返すことにより得られたＨＬが入力されたメッセージＭに対するハッシュ値Ｈ（Ｍ）となる。
【００１７】
Ｈ０＝ＩＶ
Ｈｉ＝ｃｆ（Ｈｉ−１，Ｍｉ），ｉ＝１，…，Ｌ
ｃｆ（Ｈｉ−１，Ｍｉ）は、圧縮関数と呼ばれる関数である。圧縮関数ｃｆ（Ｈｉ−１，Ｍｉ）は、図４に例示するように、Ｈｉ−１及びＭｉを入力として用いて、ｐｉ１＝Ｈｉ−１とし、ｊ＝１，…，ｘとして、ｐｉｊ＋１＝Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の演算を順次繰り返すことにより得られたｐｉｘ＋１とｐｉ１とを加算した値を出力する。
【００１８】
ｐｉ１＝Ｈｉ−１
ｐｉｊ＋１＝Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ），ｊ＝１，…，ｘ
ｃｆ（Ｈｉ−１，Ｍｉ）＝ｐｉｘ＋１＋ｐｉ１
Ｗｊ（Ｍｉ）は、メッセージ拡大関数と呼ばれる関数であり、入力されたビット列Ｍｉを構成する全部又は一部のビットを用いて出力値を計算する。用いるビットはｊに応じて異なる。メッセージ拡大関数Ｗｊ（Ｍｉ）が用いる、Ｍｉを構成するビットの位置を示すｊｗ個の整数ｗ１，…，ｗｊｗの集合をＮｊ＝｛ｗ１，…，ｗｊｗ｝と表記する。
【００１９】
Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）は、ステップ関数と呼ばれる関数であり、Ｗｊ（Ｍｉ）及びｐｉｊを入力として用いて出力値を計算する。ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）はＷｊ（Ｍｉ）に対して可逆関数であり、ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の出力値とＷｊ（Ｍｉ）の値から、入力値であるｐｉｊを計算可能であるとする。また、ｃｆ（Ｈｉ−１，Ｍｉ）の出力値Ｈｉのビット数とＲ（Ｗｊ（Ｍｉ），ｐｉｊ）の出力値ｐｉｊ＋１のビット数とが同じであるとする。
【００２０】
ｘはステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の演算の繰り返しの回数である。一般に繰り返しの回数ｘが多いほどハッシュ関数Ｈの安全性が増す。この発明は、原像攻撃が可能であり、安全性を確保することができない繰り返しの回数ｘを求めて、安全性を評価するための指標として用いる。
【００２１】
メッセージ拡大関数Ｗｊ（Ｍｉ）及びステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）は、仕様に応じて適宜設計される。
【００２２】
［実施形態］
ハッシュ関数の安全性評価装置は、図１に示すように、設定部１、決定部２、判定部３、出力部４、制御部５を例えば含む。このハッシュ関数の安全性評価装置が、図２に示すハッシュ関数の安全性方法を例えば実行する。
【００２３】
設定部１は、順次異なる自然数をｘに設定する。この例では、まず、ｘ＝１とする（ステップＳ１１）。その後、ｘ＝Ｘとなるまで、順次ｘに自然数を設定する（ステップＳ１２，ステップＳ１３）。Ｘは所定の整数である。
【００２４】
また、制御部５は、ｔｅｍｐに１を代入して、変数ｔｅｍｐを初期化する（ステップＳ４０）。
【００２５】
決定部２は、ＭＮを０からＮ−１までの整数の集合として、設定部１で設定されたｘに対して、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣと、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２とから構成される複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）を決定する（ステップＳ２）。複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）についての情報は、判定部３に送られる。
【００２６】
決定部２の具体例を以下に説明する。決定部２は、図１に例示するように、集合決定部２１と整数決定部２２とを含む。
【００２７】
まず、集合決定部２１が、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣを決定する。
【００２８】
その後、整数決定部２２が、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２を決定する
判定部３は、ある組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）について、１≦ｊ≦（ｋ１−１）又はｋ２≦ｊ≦ｘという条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＢ＝φでありかつｋ１≦ｊ≦（ｋ２−１）という条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＡ＝φであるという独立条件を満たすか判定する（ステップＳ３１）。独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）についての情報は、出力部４に送られる。
【００２９】
Ｎｊは、安全性の評価の対象となっているハッシュ関数Ｈのメッセージ拡大関数Ｗｊ（Ｍｉ）が用いる、Ｍｉを構成するビットの位置を示すｊｗ個の整数ｗ１，…，ｗｊｗの集合Ｎｊ＝｛ｗ１，…，ｗｊｗ｝である。
【００３０】
図２に示すように、制御部５は、あるｘに対応するすべての組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）について独立条件を満たすか判定されたか判断し（ステップＳ３２）。すべての組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）について独立条件を満たすか判定されていな場合には、制御部５は、まだ独立条件を満たすか判定されていない組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対して判定部３が独立条件を満たすか判定するように制御する。これにより、判定部３は、あるｘに対応するすべての組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）の独立条件を判定することになる。
【００３１】
出力部４は、独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対応するｘの中で最大のｘを出力する（ステップＳ４）。後述するように、ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の繰り返しの回数がｘ以下の場合には、後述するように、ハッシュ関数Ｈに対して原像攻撃の一種である中間値一致型原像攻撃が可能であり、安全性を確保することができない。このため、出力されたｘは、安全性の評価の指標となる。
【００３２】
ステップＳ３１（図２）において、組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）が独立条件を満たすと判定された場合には、制御部５は、その組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対応するｘとｔｅｍｐとを比較する（ステップＳ４１）。
【００３３】
ｘ＞ｔｅｍｐであれば、制御部５はｔｅｍｐにｘを代入する（ステップＳ４２）。その後、ステップＳ３２に進む。ｘ≦ｔｅｍｐであれば、ステップＳ３２に進む。
【００３４】
ステップＳ３２において、すべての組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）について独立条件を判定したと判断された場合には、制御部５は、ｘ＝Ｘであるか判定する（ステップＳ１２）。
【００３５】
ｘ＝Ｘであれば、出力部４はｔｅｍｐを出力する（ステップＳ４）。ステップＳ４１、ステップＳ４２、ステップＳ１２及びステップＳ１３の処理により、ｔｅｍｐの値はｘの最大値となっている。ｘ＝Ｘでなければ、設定部１は、ｘ＋１をｘとする（ステップＳ１３）。その後、ステップＳ２に進む。
【００３６】
［ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の繰り返しの回数がｘ以下の場合には安全性を確保することができない理由］
集合ＭＡを構成する整数をｍＡ１，ｍＡ２，…，ｍＡＮＡと表記する。すなわち、集合ＭＡ＝｛ｍＡ１，ｍＡ２，…，ｍＡＮＡ｝とする。ＮＡは、集合ＭＡを構成する整数の数である。同様に、集合ＭＢを構成する整数をｍＢ１，ｍＢ２，…，ｍＢＮＢと表記する。すなわち、集合ＭＢ＝｛ｍＢ１，ｍＢ２，…，ｍＢＮＢ｝とする。ＮＢは、集合ＭＢを構成する整数の数である。同様に、集合ＭＣを構成する整数をｍＣ１，ｍＣ２，…，ｍＣＮＣと表記する。すなわち、集合ＭＣ＝｛ｍＣ１，ｍＣ２，…，ｍＣＮＣ｝とする。ＮＣは、集合ＭＣを構成する整数の数である。
【００３７】
独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）の情報、及び、ｃｆ（Ｈｉ−１，Ｍｉ）の値が公知であるとする。
【００３８】
（１）まず、ＭｉのｍＣ１，ｍＣ２，…，ｍＣＮＣ番目の位置のビットの値ｂ（ｍＣ１），ｂ（ｍＣ２），…，ｂ（ｍＣＮＣ）とｐｉｋ１とを所定の値に固定する。
【００３９】
（２）次に、ＭｉのｍＢ１，ｍＢ２，…，ｍＢＮＢ番目の位置のビットの値の組（ｂ（ｍＢ１），ｂ（ｍＢ２），…，ｂ（ｍＢＮＢ））を複数生成し、各組に対応するｐｉｋ２の値をｐｉｋ１及びステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）を用いて計算する。ｉ＝ｋ１からｋ２−１までのＷｊ（Ｍｉ）は、ＭｉのｍＡ１，ｍＡ２，…，ｍＡＮＡ番目の位置のビットの値ｂ（ｍＡ１），ｂ（ｍＡ２），…，ｂ（ｍＡＮＡ）を用いないため、これらのビットの値ｂ（ｍＡ１），ｂ（ｍＡ２），…，ｂ（ｍＡＮＡ）がなくても、各組に対応するｐｉｋ２の値を計算することができる。
【００４０】
（３）次に、ＭｉのｍＡ１，ｍＡ２，…，ｍＡＮＡ番目の位置のビットの値の組（ｂ（ｍＡ１），ｂ（ｍＡ２），…，ｂ（ｍＡＮＡ））を複数生成し、各組に対応するｐｉｋ２の値をｐｉｋ１及びステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の逆関数Ｒ−１（Ｗｊ（Ｍｉ），ｐｉｊ＋１）と、関係式ｐｉｘ＋１＝ｃｆ（Ｈｉ−１，Ｍｉ）−ｐｉ１を用いて計算する。ｉ＝１からｋ１−１までのＷｊ（Ｍｉ）及びｉ＝ｋ２からｘまでのＷｊ（Ｍｉ）は、ＭｉのｍＢ１，ｍＢ２，…，ｍＢＮＢ番目の位置のビットの値ｂ（ｍＢ１），ｂ（ｍＢ２），…，ｂ（ｍＢＮＢ）を用いないため、これらのビットの値ｂ（ｍＢ１），ｂ（ｍＢ２），…，ｂ（ｍＢＮＢ）がなくても、各組に対応するｐｉｋ２の値を計算することができる。
【００４１】
上記（２）で求められたｐｉｋ２の値と上記（３）で求められたｐｉｋ２の値とで一致するものがあった場合には、その一致するｐｉｋ２に対応する組（ｂ（ｍＢ１），ｂ（ｍＢ２），…，ｂ（ｍＢＮＢ））及び組（ｂ（ｍＡ１），ｂ（ｍＡ２），…，ｂ（ｍＡＮＡ））によりＭｉが定まる。ＭｉのｍＣ１，ｍＣ２，…，ｍＣＮＣ番目の位置のビットの値としては、上記（１）で定めたｂ（ｍＣ１），ｂ（ｍＣ２），…，ｂ（ｍＣＮＣ）をそれぞれ用いる。
【００４２】
このように、独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）の情報、及び、ｃｆ（Ｈｉ−１，Ｍｉ）の値が公知であるとすると、このように、原像攻撃の一種であるいわゆる中間一致型原像攻撃が可能であり、ｃｆ（Ｈｉ−１，Ｍｉ）の値からＭｉを計算することができる可能性がある。
【００４３】
一般に、ＭＤファミリーのハッシュ関数Ｈの圧縮関数ｃｆ（Ｈｉ−１，Ｍｉ）についての原像攻撃が可能であるとすると、そのハッシュ関数Ｈ自体も原像攻撃が可能であることが知られている。
【００４４】
ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の繰り返しの回数がｘ以下の場合には、独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）が存在し、その存在が知られている可能性がある。
【００４５】
このため、ステップ関数Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）の繰り返しの回数がｘ以下の場合には、ハッシュ関数の安全性を確保することができないと言えるのである。
【００４６】
［変形例等］
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００４７】
例えば、ハッシュ関数の安全性評価装置は、コンピュータによって実現することができる。この場合、これらの装置の各部はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これらの装置の各部が、コンピュータ上で実現される。
【００４８】
このプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００４９】
１ 設定部
２ 決定部
２１ 集合決定部
２２ 整数決定部
３ 判定部
４ 出力部
５ 制御部
【特許請求の範囲】
【請求項１】
Ｎ，Ｌを自然数とし、ＩＶを所定の定数とし、入力されたメッセージＭをＮの倍数のビット数となるようにパディングしたビット列ｐａｄ（Ｍ）を構成するそれぞれＮ個のビットから構成されるＬ個のビット列をＭ１，…，Ｍｉ，…，ＭＬとし、Ｈ０＝ＩＶとし、Ｈｉ＝ｃｆ（Ｈｉ−１，Ｍｉ）（ｉ＝１，…，Ｌ）とし、入力されたビット列Ｍｉを構成する全部又は一部のビットを用いて出力値を計算するメッセージ拡大関数をＷｊ（Ｍｉ）（ｊ＝１，…，ｘ）とし、ｐｉ１＝Ｈｉ−１とし、ｐｉｊ＋１＝Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）（ｊ＝１，…，ｘ）とし、ｃｆ（Ｈｉ−１，Ｍｉ）＝ｐｉｘ＋１＋ｐｉ１とし、Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）を可逆関数とし、ｃｆ（Ｈｉ−１，Ｍｉ）の出力値のビット数とＲ（Ｗｊ（Ｍｉ），ｐｉｊ）の出力値のビット数とが同じとして、ＨＬを入力されたメッセージＭに対するハッシュ値とするハッシュ関数の安全性評価装置において、
ＭＮを０からＮ−１までの整数の集合として、複数の自然数ｘのそれぞれに対して、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣと、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２とから構成される複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）を決定する決定部と、
メッセージ拡大関数Ｗｊ（Ｍｉ）が用いるＭｉを構成するビットの位置を示すｊｗ個の整数ｗ１，…，ｗｊｗの集合をＮｊ＝｛ｗ１，…，ｗｊｗ｝として、上記複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）のそれぞれについて、１≦ｊ≦（ｋ１−１）又はｋ２≦ｊ≦ｘという条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＢ＝φでありかつｋ１≦ｊ≦（ｋ２−１）という条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＡ＝φであるという独立条件を満たすか判定する判定部と、
上記独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対応するｘの中で最大のｘを出力する出力部と、
を含むハッシュ関数の安全性評価装置。
【請求項２】
Ｎ，Ｌを自然数とし、ＩＶを所定の定数とし、入力されたメッセージＭをＮの倍数のビット数となるようにパディングしたビット列ｐａｄ（Ｍ）を構成するそれぞれＮ個のビットから構成されるＬ個のビット列をＭ１，…，Ｍｉ，…，ＭＬとし、Ｈ０＝ＩＶとし、Ｈｉ＝ｃｆ（Ｈｉ−１，Ｍｉ）（ｉ＝１，…，Ｌ）とし、入力されたビット列Ｍｉを構成する全部又は一部のビットを用いて出力値を計算するメッセージ拡大関数をＷｊ（Ｍｉ）（ｊ＝１，…，ｘ）とし、ｐｉ１＝Ｈｉ−１とし、ｐｉｊ＋１＝Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）（ｊ＝１，…，ｘ）とし、ｃｆ（Ｈｉ−１，Ｍｉ）＝ｐｉｘ＋１＋ｐｉ１とし、Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）を可逆関数とし、ｃｆ（Ｈｉ−１，Ｍｉ）の出力値のビット数とＲ（Ｗｊ（Ｍｉ），ｐｉｊ）の出力値のビット数とが同じとして、ＨＬを入力されたメッセージＭに対するハッシュ値とするハッシュ関数の安全性評価方法において、
決定部が、ＭＮを０からＮ−１までの整数の集合として、複数の自然数ｘのそれぞれに対して、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣと、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２とから構成される複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）を決定する決定ステップと、
判定部が、メッセージ拡大関数Ｗｊ（Ｍｉ）が用いるＭｉを構成するビットの位置を示すｊｗ個の整数ｗ１，…，ｗｊｗの集合をＮｊ＝｛ｗ１，…，ｗｊｗ｝として、上記複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）のそれぞれについて、１≦ｊ≦（ｋ１−１）又はｋ２≦ｊ≦ｘという条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＢ＝φでありかつｋ１≦ｊ≦（ｋ２−１）という条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＡ＝φであるという独立条件を満たすか判定する判定ステップと、
出力部が、上記独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対応するｘの中で最大のｘを出力する出力ステップと、
を含むハッシュ関数の安全性評価方法。
【請求項３】
請求項１に記載されたハッシュ関数の安全性評価装置の各部としてコンピュータを機能させるためのハッシュ関数の安全性評価プログラム。
【請求項１】
Ｎ，Ｌを自然数とし、ＩＶを所定の定数とし、入力されたメッセージＭをＮの倍数のビット数となるようにパディングしたビット列ｐａｄ（Ｍ）を構成するそれぞれＮ個のビットから構成されるＬ個のビット列をＭ１，…，Ｍｉ，…，ＭＬとし、Ｈ０＝ＩＶとし、Ｈｉ＝ｃｆ（Ｈｉ−１，Ｍｉ）（ｉ＝１，…，Ｌ）とし、入力されたビット列Ｍｉを構成する全部又は一部のビットを用いて出力値を計算するメッセージ拡大関数をＷｊ（Ｍｉ）（ｊ＝１，…，ｘ）とし、ｐｉ１＝Ｈｉ−１とし、ｐｉｊ＋１＝Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）（ｊ＝１，…，ｘ）とし、ｃｆ（Ｈｉ−１，Ｍｉ）＝ｐｉｘ＋１＋ｐｉ１とし、Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）を可逆関数とし、ｃｆ（Ｈｉ−１，Ｍｉ）の出力値のビット数とＲ（Ｗｊ（Ｍｉ），ｐｉｊ）の出力値のビット数とが同じとして、ＨＬを入力されたメッセージＭに対するハッシュ値とするハッシュ関数の安全性評価装置において、
ＭＮを０からＮ−１までの整数の集合として、複数の自然数ｘのそれぞれに対して、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣと、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２とから構成される複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）を決定する決定部と、
メッセージ拡大関数Ｗｊ（Ｍｉ）が用いるＭｉを構成するビットの位置を示すｊｗ個の整数ｗ１，…，ｗｊｗの集合をＮｊ＝｛ｗ１，…，ｗｊｗ｝として、上記複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）のそれぞれについて、１≦ｊ≦（ｋ１−１）又はｋ２≦ｊ≦ｘという条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＢ＝φでありかつｋ１≦ｊ≦（ｋ２−１）という条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＡ＝φであるという独立条件を満たすか判定する判定部と、
上記独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対応するｘの中で最大のｘを出力する出力部と、
を含むハッシュ関数の安全性評価装置。
【請求項２】
Ｎ，Ｌを自然数とし、ＩＶを所定の定数とし、入力されたメッセージＭをＮの倍数のビット数となるようにパディングしたビット列ｐａｄ（Ｍ）を構成するそれぞれＮ個のビットから構成されるＬ個のビット列をＭ１，…，Ｍｉ，…，ＭＬとし、Ｈ０＝ＩＶとし、Ｈｉ＝ｃｆ（Ｈｉ−１，Ｍｉ）（ｉ＝１，…，Ｌ）とし、入力されたビット列Ｍｉを構成する全部又は一部のビットを用いて出力値を計算するメッセージ拡大関数をＷｊ（Ｍｉ）（ｊ＝１，…，ｘ）とし、ｐｉ１＝Ｈｉ−１とし、ｐｉｊ＋１＝Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）（ｊ＝１，…，ｘ）とし、ｃｆ（Ｈｉ−１，Ｍｉ）＝ｐｉｘ＋１＋ｐｉ１とし、Ｒ（Ｗｊ（Ｍｉ），ｐｉｊ）を可逆関数とし、ｃｆ（Ｈｉ−１，Ｍｉ）の出力値のビット数とＲ（Ｗｊ（Ｍｉ），ｐｉｊ）の出力値のビット数とが同じとして、ＨＬを入力されたメッセージＭに対するハッシュ値とするハッシュ関数の安全性評価方法において、
決定部が、ＭＮを０からＮ−１までの整数の集合として、複数の自然数ｘのそれぞれに対して、ＭＡ⊆ＭＮ，ＭＢ⊆ＭＮ，ＭＣ⊆ＭＮ，ＭＡ∩ＭＢ＝φ，ＭＢ∩ＭＣ＝φ，ＭＣ∩ＭＡ＝φ，ＭＡ∪ＭＢ∪ＭＣ＝ＭＮという条件を満たす集合ＭＡ，ＭＢ，ＭＣと、１≦ｋ１＜ｋ２≦ｘという条件を満たす整数ｋ１，ｋ２とから構成される複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）を決定する決定ステップと、
判定部が、メッセージ拡大関数Ｗｊ（Ｍｉ）が用いるＭｉを構成するビットの位置を示すｊｗ個の整数ｗ１，…，ｗｊｗの集合をＮｊ＝｛ｗ１，…，ｗｊｗ｝として、上記複数の組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）のそれぞれについて、１≦ｊ≦（ｋ１−１）又はｋ２≦ｊ≦ｘという条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＢ＝φでありかつｋ１≦ｊ≦（ｋ２−１）という条件を満たす各ｊに対応するＮｊがＮｊ∩ＭＡ＝φであるという独立条件を満たすか判定する判定ステップと、
出力部が、上記独立条件を満たす組（ＭＡ，ＭＢ，ＭＣ，ｋ１，ｋ２）に対応するｘの中で最大のｘを出力する出力ステップと、
を含むハッシュ関数の安全性評価方法。
【請求項３】
請求項１に記載されたハッシュ関数の安全性評価装置の各部としてコンピュータを機能させるためのハッシュ関数の安全性評価プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１２−２８３１（Ｐ２０１２−２８３１Ａ）
【公開日】平成２４年１月５日（２０１２．１．５）
【国際特許分類】
【出願番号】特願２０１０−１３４６７１（Ｐ２０１０−１３４６７１）
【出願日】平成２２年６月１４日（２０１０．６．１４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年１月５日（２０１２．１．５）
【国際特許分類】
【出願日】平成２２年６月１４日（２０１０．６．１４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]