(57)【要約】【課題】ＳＨＡ−５１２等の広く使われているＭｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数の内部構造を変えずに用いて、任意のジェネリック攻撃に対して安全なハッシュ関数を構成することを目的とする。【解決手段】ハッシュ関数Ｈは、ｎ−ｓビットのハッシュ値を計算する。ハッシュ関数Ｈは、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数で計算されたハッシュ値ｈを入力として、２ｓ≦ｎの場合、ハッシュ値ｈの１ビット目からｓビット目までのｓビットに、０をｎ−２ｓビット付けたｎ−ｓビットの値ｙ１と、ハッシュ値ｈのｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算し、２ｓ＞ｎの場合、ハッシュ値ｈの１ビット目からｎ−ｓビット目までのｎ−ｓビットの値ｙ１と、ハッシュ値ｈのｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算する。【選択図】図１
2014126562.tif 000002
【特許請求の範囲】
【請求項１】
ｎ−ｓビット（ｎは２以上の整数、ｓはｎよりも小さい整数）のハッシュ値を計算するハッシュ値計算装置であり、
Ｌ個（Ｌは１以上の整数）のａビット（ａは１以上の整数）の値Ｍ［１］，．．．，Ｍ［Ｌ］を入力する既定長値入力部と、
ｉ＝１，．．．，Ｌの各整数ｉについて昇順に、前記既定長値入力部が入力した値Ｍ［ｉ］と、ｎビットの値ｙ［ｉ−１］（値ｙ［０］は所定値ＩＶ）とを入力として、ｎビットの値ｙ［ｉ］を計算する圧縮関数計算部と、
前記圧縮関数計算部が計算した値ｙ［Ｌ］を入力として、２ｓ≦ｎの場合、前記値ｙ［Ｌ］の１ビット目からｓビット目までのｓビットに、０をｎ−２ｓビット付けたｎ−ｓビットの値ｙ１と、前記値ｙ［Ｌ］のｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算し、２ｓ＞ｎの場合、前記値ｙ［Ｌ］の１ビット目からｎ−ｓビット目までのｎ−ｓビットの値ｙ１と、前記値ｙ［Ｌ］のｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算するハッシュ値計算部と
を備えることを特徴とするハッシュ値計算装置。
【請求項２】
前記圧縮関数計算部は、
前記値Ｍ［ｉ］と、前記値ｙ［ｉ−１］とを入力として、ａビットの値ｋ［ｉ］とｎビットの値ｖ［ｉ］とを計算する関数Ｆ計算部と、
前記関数Ｆ計算部が計算した値ｋ［ｉ］と値ｖ［ｉ］とを入力として、ｎビットの値ｗ［ｉ］を計算する可変置換関数計算部と、
前記可変置換関数計算部が計算した値ｗ［ｉ］を入力として、ｎビットの値ｙ［ｉ］を計算する関数Ｇ計算部と
を備えることを特徴とする請求項１に記載のハッシュ値計算装置。
【請求項３】
前記可変置換関数計算部は、前記値ｋ［ｉ］を固定値とした場合に、前記値ｖ［ｉ］と前記値ｗ［ｉ］とが置換関係になる可変置換関数により、前記値ｗ［ｉ］を計算する
ことを特徴とする請求項２に記載のハッシュ値計算装置。
【請求項４】
前記関数Ｆ計算部は、前記値Ｍ［ｉ］を前記値ｋ［ｉ］とし、前記値ｙ［ｉ−１］を前記値ｖ［ｉ］とする関数Ｆにより、前記値ｋ［ｉ］と前記値ｖ［ｉ］とを計算する
ことを特徴とする請求項２又は３に記載のハッシュ値計算装置。
【請求項５】
前記関数Ｇ計算部は、さらに前記値ｙ［ｉ−１］を入力として、前記値ｗ［ｉ］と前記値ｙ［ｉ−１］との排他的論理和を前記値ｙ［ｉ］とする関数Ｇにより、前記値ｙ［ｉ］を計算する
ことを特徴とする請求項２から４までのいずれかに記載のハッシュ値計算装置。
【請求項６】
前記関数Ｇ計算部は、前記値ｗ［ｉ］を前記値ｙ［ｉ］とする関数Ｇにより、前記値ｙ［ｉ］を計算する
ことを特徴とする請求項２から４までのいずれかに記載のハッシュ値計算装置。
【請求項７】
前記ハッシュ値計算装置は、さらに、
任意ビット長の値Ｍを入力する任意長値入力部と、
前記任意長値入力部が入力した値Ｍを入力として、全単射関数であるパディング関数により、ａビットのＬ倍のビットの値Ｍ＊を計算するパディング部と、
前記パディング部が計算した値Ｍ＊をＬ個に分割して、ａビットの値Ｍ［１］，．．．，値Ｍ［Ｌ］を計算する分割部と
を備え、
前記既定長値入力部は、前記分割部が計算した値Ｍ［１］，．．．，値Ｍ［Ｌ］を入力する
ことを特徴とする請求項１から６までのいずれかに記載のハッシュ値計算装置。
【請求項８】
前記パディング部は、前記値Ｍの後に１を１個付け、その後ろに０をｔ個付け、その後ろに前記値Ｍのビット長を６４ビットで表現した値を付けるパディング関数により、前記値Ｍ＊を計算する
ことを特徴とする請求項７に記載のハッシュ値計算装置。
【請求項９】
ｎ−ｓビット（ｎは２以上の整数、ｓはｎよりも小さい整数）のハッシュ値を計算するハッシュ値計算方法であり、
入力装置が、Ｌ個（Ｌは１以上の整数）のａビット（ａは１以上の整数）の値Ｍ［１］，．．．，Ｍ［Ｌ］を入力する既定長値入力ステップと、
処理装置が、ｉ＝１，．．．，Ｌの各整数ｉについて昇順に、前記既定長値入力ステップで入力した値Ｍ［ｉ］と、ｎビットの値ｙ［ｉ−１］（値ｙ［０］は所定値ＩＶ）とを入力として、ｎビットの値ｙ［ｉ］を計算する圧縮関数計算ステップと、
処理装置が、前記圧縮関数計算ステップで計算した値ｙ［Ｌ］を入力として、２ｓ≦ｎの場合、前記値ｙ［Ｌ］の１ビット目からｓビット目までのｓビットに、０をｎ−２ｓビット付けたｎ−ｓビットの値ｙ１と、前記値ｙ［Ｌ］のｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算し、２ｓ＞ｎの場合、前記値ｙ［Ｌ］の１ビット目からｎ−ｓビット目までのｎ−ｓビットの値ｙ１と、前記値ｙ［Ｌ］のｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算するハッシュ値計算ステップと
を備えることを特徴とするハッシュ値計算方法。
【請求項１０】
ｎ−ｓビット（ｎは２以上の整数、ｓはｎよりも小さい整数）のハッシュ値を計算するハッシュ値計算プログラムであり、
Ｌ個（Ｌは１以上の整数）のａビット（ａは１以上の整数）の値Ｍ［１］，．．．，Ｍ［Ｌ］を入力する既定長値入力処理と、
ｉ＝１，．．．，Ｌの各整数ｉについて昇順に、前記既定長値入力処理で入力した値Ｍ［ｉ］と、ｎビットの値ｙ［ｉ−１］（値ｙ［０］は所定値ＩＶ）とを入力として、ｎビットの値ｙ［ｉ］を計算する圧縮関数計算処理と、
前記圧縮関数計算処理で計算した値ｙ［Ｌ］を入力として、２ｓ≦ｎの場合、前記値ｙ［Ｌ］の１ビット目からｓビット目までのｓビットに、０をｎ−２ｓビット付けたｎ−ｓビットの値ｙ１と、前記値ｙ［Ｌ］のｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算し、２ｓ＞ｎの場合、前記値ｙ［Ｌ］の１ビット目からｎ−ｓビット目までのｎ−ｓビットの値ｙ１と、前記値ｙ［Ｌ］のｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算するハッシュ値計算処理と
をコンピュータに実行させることを特徴とするハッシュ値計算プログラム。
【請求項１１】
ｎ−ｓビット（ｎは２以上の整数、ｓはｎよりも小さい整数）のハッシュ値を計算するハッシュ値計算装置であり、
Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数によって計算されたｎビットのハッシュ値ｈを入力するハッシュ値入力部と、
前記ハッシュ値入力部が入力したハッシュ値ｈを入力として、２ｓ≦ｎの場合、前記ハッシュ値ｈの１ビット目からｓビット目までのｓビットに、０をｎ−２ｓビット付けたｎ−ｓビットの値ｙ１と、前記ハッシュ値ｈのｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算し、２ｓ＞ｎの場合、前記ハッシュ値ｈの１ビット目からｎ−ｓビット目までのｎ−ｓビットの値ｙ１と、前記ハッシュ値ｈのｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算するハッシュ値計算部と
を備えることを特徴とするハッシュ値計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ＳＨＡ−５１２等の広く使われているＭｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数の内部構造を変えずに用いて、任意のジェネリック攻撃に対して安全なハッシュ関数を構成する技術に関する。
【背景技術】
【０００２】
ハッシュ関数は、任意長の値を入力として、固定長のハッシュ値を出力する関数である。
【０００３】
Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数は、圧縮関数を繰り返し用いるハッシュ関数であり、入力値を固定長の複数の値に分割し、分割したうちの１つの値と前の圧縮関数の出力とを入力として順次圧縮関数を計算するハッシュ関数である。
【０００４】
非特許文献１，２，３には、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数の内部構造を変えずに、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数の出力を切り落とすことで、疑似ランダムオラクルの安全性を満たすハッシュ関数を構成することについて記載されている。
非特許文献１には、疑似ランダムオラクルの安全性についての証明が記載されている。非特許文献１によれば、非特許文献１，２，３に記載されたハッシュ関数では、疑似ランダムオラクルの安全性を破るためには、少なくともＯ（ｍｉｎ｛２ｓ／ｎ，２ｎ−ｓ｝）以上の計算量が必要となる。ここで、ｎは、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数の出力長であり、ｓは出力長ｎビットから切り落とすビット長である。
【０００５】
非特許文献４には、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数で用いられるパディング関数をｐｒｅｆｉｘ−ｆｒｅｅパディングに変更し、さらに出力を切り落とすことで、疑似ランダムオラクルの安全性を満たすハッシュ関数を構成することについて記載されている。非特許文献２に記載されたハッシュ関数では、疑似ランダムオラクルの安全性を破るためには、少なくともＯ（２ｎ／２）以上の計算が必要となる。
【０００６】
非特許文献５，６には、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数に関する記載がある。しかし、非特許文献５，６に記載されたハッシュ関数は、非特許文献３に記載された内容から、疑似ランダムオラクルの安全性を満たすことができない。
【０００７】
非特許文献７には、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数に、関数を追加することで、いくつかのジェネリック攻撃に対して安全なハッシュ関数を構成することについて記載されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Ｄｏｎｇｈｏｏｎ  Ｃｈａｎｇ，  Ｍｒｉｄｕｌ  Ｎａｎｄｉ．  Ｉｍｐｒｏｖｅｄ  Ｉｎｄｉｆｆｅｒｅｎｔｉａｂｉｌｉｔｙ  Ｓｅｃｕｒｉｔｙ  Ａｎａｌｙｓｉｓ  ｏｆ  ｃｈｏｐＭＤ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎ．  ＦＳＥ  ２００８：  ４２９−４４３，  ＬＮＣＳ  ５０８６．
【非特許文献２】ＦＩＰＳ１８０−４，  Ｓｅｃｕｒｅ  Ｈａｓｈ  Ｓｔａｎｄａｒｄ  （ＳＨＳ）．
【非特許文献３】Ｊｅａｎ−Ｓｅｂａｓｔｉｅｎ  Ｃｏｒｏｎ，  Ｙｅｖｇｅｎｉｙ  Ｄｏｄｉｓ，  Ｃｅｃｉｌｅ  Ｍａｌｉｎａｕｄ，  Ｐｒａｓｈａｎｔ  Ｐｕｎｉｙａ．  Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ  Ｒｅｖｉｓｉｔｅｄ：  Ｈｏｗ  ｔｏ  Ｃｏｎｓｔｒｕｃｔ  ａ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎ．  ＣＲＹＰＴＯ  ２００５．  ｐｐ４３０−４４８．  ＬＮＣＳ  ３６２１．
【非特許文献４】Ｕｅｌｉ  Ｍａｕｒｅｒ  ａｎｄ  Ｓｔｅｆａｎｏ  Ｔｅｓｓａｒｏ，  Ｄｏｍａｉｎ  Ｅｘｔｅｎｓｉｏｎ  ｏｆ  Ｐｕｂｌｉｃ  Ｒａｎｄｏｍ  Ｆｕｎｃｔｉｏｎｓ：  Ｂｅｙｏｎｄ  ｔｈｅ  Ｂｉｒｔｈｄａｙ  Ｂａｒｒｉｅｒ  ＣＲＹＰＴＯ  ２００７，  ｐｐ１８７−２０４，  ＬＮＣＳ  ４６２２．
【非特許文献５】Ｉｖａｎ  Ｄａｍｇａｒｄ．  Ａ  Ｄｅｓｉｇｎ  Ｐｒｉｎｃｉｐｌｅ  ｆｏｒ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ．  ＣＲＹＰＴＯ  １９８９．  ｐｐ４１６−４２７．  ＬＮＣＳ  ４３５．
【非特許文献６】Ｒａｌｐｈ  Ｃ．  Ｍｅｒｋｌｅ：  Ｏｎｅ  Ｗａｙ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  ＤＥＳ．  ＣＲＹＰＴＯ  １９８９．  ｐｐ４２８−４４６．  ＬＮＣＳ  ４３５
【非特許文献７】Ｓｔｅｆａｎ  Ｌｕｃｋｓ．  Ａ  Ｆａｉｌｕｒｅ−Ｆｒｉｅｎｄｌｙ  Ｄｅｓｉｇｎ  Ｐｒｉｎｃｉｐｌｅ  ｆｏｒ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ．  ＡＳＩＡＣＲＹＰＴ  ２００５，  ４７４−４９４，  ＬＮＣＳ  ３７８８
【発明の概要】
【発明が解決しようとする課題】
【０００９】
任意のジェネリック攻撃に対する安全性は、疑似ランダムオラクルの安全性を証明することで保証できる。但し、ハッシュ関数の出力長がｗビットである場合、疑似ランダムオラクルの安全性を破るための計算量がＯ（２ｗ）以上であることを示す必要がある。
【００１０】
非特許文献１，２，３に記載されたハッシュ関数の疑似ランダムオラクルの安全性を破るための計算量Ｏ（ｍｉｎ｛２ｓ／ｎ，２ｎ−ｓ｝）は、任意のジェネリック攻撃に対する安全性を保証する場合、ｓ≧ｎ／２＋ｌｏｇ２ｎとする必要がある。つまり、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数の出力長ｎビットに対して、任意のジェネリック攻撃に対する安全性を破る計算量を２ｎ／２以上にしたい場合、切り落とすｓビットはｎ／２より大きくする必要がある。そのため、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数の出力長（ｎビット）を大きくする必要がある。
その結果、非特許文献２に記載されているＳＨＡ−５１２／２５６は任意のジェネリック攻撃に対する安全性を満たさない。
【００１１】
非特許文献４に記載されたハッシュ関数では、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数で用いられるパディング関数をｐｒｅｆｉｘ−ｆｒｅｅパディングに変更する必要がある。ＳＨＡ−５１２等の標準的なハッシュ関数で用いられるパディング関数は、ｐｒｅｆｉｘ−ｆｒｅｅパディングではない。
【００１２】
非特許文献５，６に記載されたハッシュ関数では、上述した通り、疑似ランダムオラクルの安全性を満たすことができない。また、非特許文献７には、疑似ランダムオラクルの安全性を満たすことについては何ら記載されていない。
【００１３】
この発明は、ＳＨＡ−５１２等の広く使われている出力長がｎビットのＭｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数の内部構造を変えずに用いて任意のジェネリック攻撃に対して安全な出力長がｎ／２ビットのハッシュ関数を構成することを目的とする。
【課題を解決するための手段】
【００１４】
この発明に係るハッシュ値計算装置は、
ｎ−ｓビット（ｎは２以上の整数、ｓはｎよりも小さい整数）のハッシュ値を計算するハッシュ値計算装置であり、
Ｌ個（Ｌは１以上の整数）のａビット（ａは１以上の整数）の値Ｍ［１］，．．．，Ｍ［Ｌ］を入力する既定長値入力部と、
ｉ＝１，．．．，Ｌの各整数ｉについて昇順に、前記既定長値入力部が入力した値Ｍ［ｉ］と、ｎビットの値ｙ［ｉ−１］（値ｙ［０］は所定値ＩＶ）とを入力として、ｎビットの値ｙ［ｉ］を計算する圧縮関数計算部と、
前記圧縮関数計算部が計算した値ｙ［Ｌ］を入力として、２ｓ≦ｎの場合、前記値ｙ［Ｌ］の１ビット目からｓビット目までのｓビットに、０をｎ−２ｓビット付けたｎ−ｓビットの値ｙ１と、前記値ｙ［Ｌ］のｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算し、２ｓ＞ｎの場合、前記値ｙ［Ｌ］の１ビット目からｎ−ｓビット目までのｎ−ｓビットの値ｙ１と、前記値ｙ［Ｌ］のｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算するハッシュ値計算部と
を備えることを特徴とする。
【発明の効果】
【００１５】
この発明に係るハッシュ値計算装置は、既定長値入力部及び圧縮関数計算部として、ＳＨＡ−５１２等の広く使われているＭｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数の内部構造を変えずに用いることにより、任意のジェネリック攻撃に対して安全なハッシュ関数を構成することが可能である。
【図面の簡単な説明】
【００１６】
【図１】実施の形態１に係るハッシュ関数Ｈの構成図。
【図２】図１に示すハッシュ関数Ｈで用いられる圧縮関数Ｃの構成図。
【図３】実施の形態１に係るハッシュ値計算装置１０の構成図。
【図４】実施の形態１に係るハッシュ値計算装置１０の動作を示すフローチャート。
【発明を実施するための形態】
【００１７】
実施の形態１．
図１は、実施の形態１に係るハッシュ関数Ｈの構成図である。
図１において、括弧内に記載されたａ，ｎ，ｎ−ｓは、ビット長を表す。
ハッシュ関数Ｈは、ｎ−ｓビットのハッシュ値を計算する。ここで、ｎは、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数部分の出力長であり、２以上の整数である。ｓは、ｎビット長から切り落とすビット長であり、ｎよりも小さい整数である。
【００１８】
ハッシュ関数Ｈは、任意長の値Ｍを入力として、パディング関数ｐａｄにより、ａビットのＬ倍の長さの値Ｍ＊を生成する。例えば、パディング関数ｐａｄは、値Ｍの後に１を１個付け、その後に０をｕ個付け、最後に６４ビットの値＜Ｍ＞を付けて、ａビットのＬ倍の長さの値Ｍ＊を生成する関数である。値＜Ｍ＞は、値Ｍのビット長を６４ビット表現した値である。例えば、Ｍのビット長が８ビットの場合、値＜Ｍ＞は０．．．０１００である。０を付ける個数ｕは、値Ｍ＊がａビットのＬ倍の長さになるように調整される。
【００１９】
次に、ハッシュ関数Ｈは、分割関数ｄにより、値Ｍ＊を分割してａビットの値Ｍ［１］，．．．，Ｍ［Ｌ］を生成する。分割関数ｄは、例えば、値Ｍ＊を先頭からａビット毎に分割して、値Ｍ［１］，．．．，Ｍ［Ｌ］を生成する関数である。
【００２０】
次に、ハッシュ関数Ｈは、ｉ＝１，．．．，Ｌ（Ｌは１以上の整数）の各整数ｉについて昇順に、値Ｍ［ｉ］と、ｎビットの値ｙ［ｉ−１］（値ｙ［０］は所定値ＩＶ）とを入力として、圧縮関数Ｃにより、ｎビットの値ｙ［ｉ］を計算する。
なお、値ｙ［Ｌ］がＭｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数によって計算されたハッシュ値ｈである。
【００２１】
そして、ハッシュ関数Ｈは、以下の（１）（２）によりハッシュ値を計算する。
（１）２ｓ≦ｎの場合、（ｙ［１，ｓ］｜｜０ｎ−２ｓ）  ｘｏｒ  ｙ［ｓ＋１，ｎ］をハッシュ値として計算する。ここで、ｙ［ｊ，ｔ］は、値ｙ［Ｌ］のｊビット目からｔビット目までの値である。０ｎ−２ｓは、０をｎ−２ｓ個並べたビット列である。ｐ｜｜ｑは、ビット列ｐの後にビット列ｑを付ける演算である。つまり、２ｓ≦ｎの場合、値ｙ［Ｌ］の１ビット目からｓビット目までのｓビットの後に、０をｎ−２ｓビット追加したｎ−ｓビットの値ｙ１と、値ｙ［Ｌ］のｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算する。
（２）２ｓ＞ｎの場合、ｙ［１，ｎ−ｓ］  ｘｏｒ  ｙ［ｓ＋１，ｎ］をハッシュ値として計算する。つまり、２ｓ＞ｎの場合、値ｙ［Ｌ］の１ビット目からｎ−ｓビット目までのｎ−ｓビットの値ｙ１と、値ｙ［Ｌ］のｓ＋１ビット目からｎビット目までのｎ−ｓビットの値ｙ２との排他的論理和をハッシュ値として計算する。
【００２２】
図２は、図１に示すハッシュ関数Ｈで用いられる圧縮関数Ｃの構成図である。
図２において、括弧内に記載されたａ，ｎは、ビット長を表す。
圧縮関数Ｃは、ａビットの値Ｍ［ｉ］と、ｎビットの値ｙ［ｉ−１］とを入力として、ｎビットの値ｙ［ｉ］を計算する。
圧縮関数Ｃは、関数Ｆと、可変置換関数Ｐと、関数Ｇとを用いて構成される。
【００２３】
関数Ｆは、値Ｍ［ｉ］と、値ｙ［ｉ−１］とを入力として、ａビットの値ｋ［ｉ］とｎビットの値ｖ［ｉ］とを計算する。関数Ｆは、例えば、値Ｍ［ｉ］を値ｋ［ｉ］とし、値ｙ［ｉ−１］を値ｖ［ｉ］とする関数である。
【００２４】
可変置換関数Ｐは、値ｋ［ｉ］を鍵成分、値ｖ［ｉ］を平文成分として、ｎビットの値ｗ［ｉ］を暗号文成分として計算する。可変置換関数Ｐは、鍵成分を固定すると、平文成分と暗号文成分とが置換関係になる関数である。
【００２５】
関数Ｇは、値ｗ［ｉ］と値ｙ［ｉ−１］と値Ｍ［ｉ］とを入力として、ｎビットの値ｙ［ｉ］を計算する。関数Ｇは、例えば、値ｗ［ｉ］と値ｙ［ｉ−１］との排他的論理和を値ｙ［ｉ］とする関数や、値ｗ［ｉ］を値ｙ［ｉ］とする関数である。
【００２６】
図３は、実施の形態１に係るハッシュ値計算装置１０の構成図である。
ハッシュ値計算装置１０は、上述したハッシュ関数Ｈを実現する。
ハッシュ値計算装置１０は、任意長値入力部１１、パディング部１２、分割部１３、既定長値入力部１４、圧縮関数計算部１５、ハッシュ値計算部１６を備える。任意長値入力部１１〜圧縮関数計算部１５は、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数を計算してハッシュ値計算部１６へ入力する機能であるため、これらを総称してハッシュ値入力部と呼ぶ。
【００２７】
任意長値入力部１１は、任意長の値Ｍを入力装置により入力する。パディング部１２は、任意長値入力部１１が入力した値Ｍを入力として、処理装置によりパディング関数ｐａｄを計算して、値Ｍ＊を計算する。分割部１３は、パディング部１２が計算した値Ｍ＊を入力として、処理装置により分割関数ｄを計算して、値Ｍ［１］，．．．，Ｍ［Ｌ］を計算する。既定長値入力部１４は、分割部１３が計算した値Ｍ［１］，．．．，Ｍ［Ｌ］を入力装置により入力する。
圧縮関数計算部１５は、既定長値入力部１４が入力した値Ｍ［１］，．．．，Ｍ［Ｌ］と、値ｙ［０］である所定値ＩＶとを入力として、処理装置により圧縮関数Ｃを計算して、値ｙ［ｉ］を計算する。
ハッシュ値計算部１６は、圧縮関数計算部１５が計算した値ｙ［ｉ］を入力として、処理装置により上述した（１）又は（２）の計算を行い、ハッシュ値を計算する。
【００２８】
図４は、実施の形態１に係るハッシュ値計算装置１０の動作を示すフローチャートである。
（Ｓ１：任意長値入力ステップ）
任意長値入力部１１は、任意ビット長の値Ｍを入力する。
【００２９】
（Ｓ２：パディングステップ）
パディング部１２は、（Ｓ１）で入力された値Ｍを入力として、ａビットのＬ倍の長さの値Ｍ＊を生成する。
【００３０】
（Ｓ３：分割ステップ）
分割部１３は、（Ｓ２）で出力された値Ｍ＊を入力として、分割関数ｄを計算して、ａビットの値Ｍ［１］，．．．，Ｍ［Ｌ］を出力する。
【００３１】
（Ｓ４：既定長値入力ステップ）
既定長値入力部１４は、（Ｓ３）で出力された値Ｍ［１］，．．．，Ｍ［Ｌ］を入力装置により入力する。
【００３２】
（Ｓ５：圧縮関数計算ステップ）
圧縮関数計算部１５は、ａビットの値Ｍ［１］と、ｎビットの所定値ＩＶとを入力として、圧縮関数Ｃにより、ｎビットの値ｙ［１］を計算する。
続いて、圧縮関数計算部１５は、ｉ＝２，．．．，Ｌの各整数ｉについて昇順に、ａビットの値Ｍ［ｉ］と、ｎビットの値ｙ［ｉ−１］とを入力として、圧縮関数Ｃにより、ｎビットの値ｙ［ｉ］を計算する。
【００３３】
（Ｓ６：ハッシュ値計算ステップ）
ハッシュ値計算部１６は、（１）２ｓ≦ｎの場合、（ｙ［１，ｓ］｜｜０ｎ−２ｓ）  ｘｏｒ  ｙ［ｓ＋１，ｎ］をハッシュ値として計算し、２ｓ＞ｎの場合、ｙ［１，ｎ−ｓ］  ｘｏｒ  ｙ［ｓ＋１，ｎ］をハッシュ値として計算する。
【００３４】
実施の形態１に係るハッシュ関数Ｈは、圧縮関数Ｃが理想化された圧縮関数である場合、疑似ランダムオラクルの安全性を保証することができる。また、ハッシュ関数Ｈの疑似ランダムオラクルの安全性を破るための計算量は、Ｏ（ｍｉｎ｛２ｓ，２ｎ／２｝）である。
また、ハッシュ関数Ｈは、Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数の出力に対して計算を行うことにより、ハッシュ値を得る。つまり、ハッシュ関数Ｈは、ＳＨＡ−５１２等の広く使われているＭｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数の内部構造を変える必要がない。したがって、ＳＨＡ−５１２等の広く使われているＭｅｒｋｌｅ−Ｄａｍｇａｒｄ型のハッシュ関数をそのまま用いてハッシュ関数Ｈを構成することができる。
【００３５】
なお、パディング関数ｐａｄのパディング方法、分割関数ｄによる値Ｍ＊の分割方法、関数Ｆ、可変置換関数Ｃ、関数Ｇの構成は、上記説明で例示したものに限定されるわけではない。
【００３６】
以上に説明したハッシュ値計算装置１０は、例えば、回路やソフトウェア等で構成される。回路で構成される場合には、上記説明における処理装置は、例えば演算回路であり、メモリは、例えばレジスタである。また、ソフトウェアで構成される場合には、上記説明における処理装置は、例えばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）であり、メモリは、例えばＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。また、上記説明における入力装置は、例えばキーボード、通信ボードであり、出力装置は、例えばＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）等の表示装置、通信ボード、レジスタやＲＡＭ等のメモリである。もちろん、これらに限定されるものではない。
なお、ハッシュ値計算装置１０を回路で構成する場合、上述した「〜部」を「〜回路」と読み変えてもよい。また、上述した「〜部」は、「〜処理」、「〜装置」、「〜機器」、「〜手段」、「〜手順」、「〜機能」と読み替えてもよい。つまり、「〜部」として説明するものは、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実現されても構わない。
【符号の説明】
【００３７】
１０  ハッシュ値計算装置、１１  任意長値入力部、１２  パディング部、１３  分割部、１４  既定長値入力部、１５  圧縮関数計算部、１６  ハッシュ値計算部。
【図１】
2014126562.tif 000003
【図２】
2014126562.tif 000004
【図３】
2014126562.tif 000005
【図４】
2014126562.tif 000006