ハッシュ値演算装置、ハッシュ値演算方法及びハッシュ値演算プログラム
【課題】少ない数の関数を用いつつ、安全性の高いハッシュ関数を構成することを目的とする。
【解決手段】ハッシュ値演算装置１０は、３つの異なる非圧縮な内部関数ｆ１，ｆ２，ｆ３を用いて、擬似ランダムオラクルの性質を満たすハッシュ関数を実現する。なお、ハッシュ値演算装置１０が実現するハッシュ関数が擬似ランダムオラクルの性質を満たすのは、用いる３つの非圧縮な内部関数ｆ１，ｆ２，ｆ３が、それぞれランダムオラクルの性質を満たす場合である。
【解決手段】ハッシュ値演算装置１０は、３つの異なる非圧縮な内部関数ｆ１，ｆ２，ｆ３を用いて、擬似ランダムオラクルの性質を満たすハッシュ関数を実現する。なお、ハッシュ値演算装置１０が実現するハッシュ関数が擬似ランダムオラクルの性質を満たすのは、用いる３つの非圧縮な内部関数ｆ１，ｆ２，ｆ３が、それぞれランダムオラクルの性質を満たす場合である。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば、安全性の高いハッシュ値を計算する技術に関する。
【背景技術】
【０００２】
ハッシュ関数は、任意長の値を入力として、固定長の値を出力する関数である。
【０００３】
非特許文献１には、非圧縮な４つの関数ｆ１，ｆ２，ｆ３，ｆ４を用いて擬似ランダムオラクルの性質を満たすハッシュ関数を構成することについての記載がある。ここで、非特許文献１においてハッシュ関数が擬似ランダムオラクルの性質を満たすためには、４つの関数ｆ１，ｆ２，ｆ３，ｆ４がランダムオラクルである必要がある。なお、非圧縮な関数とは、入力長と出力長とが同じ関数である。
【０００４】
非特許文献２には、非圧縮な３つの関数ｆ１，ｆ２，ｆ３を用いて、衝突困難性の性質を満たすハッシュ関数を構成することについての記載がある。ここで、非特許文献２においてハッシュ関数が衝突困難性の性質を満たすためには、３つの関数ｆ１，ｆ２，ｆ３がランダムオラクルである必要がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｙ． Ｄｏｄｉｓ， Ｔ． Ｒｉｓｔｅｎｐａｒｔ ａｎｄ Ｔ． Ｓｈｒｉｍｐｔｏｎ， Ｓａｌｖａｇｉｎｇ Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ ｆｏｒ Ｐｒａｃｔｉｃａｌ Ａｐｐｌｉｃａｔｉｏｎｓ． ＥＵＲＯＣＲＹＰＴ ２００９， ｐｐ ３７１−３８８， ＬＮＣＳ ５４７９
【非特許文献２】Ｔ． Ｒｉｓｔｅｎｐａｒｔ ａｎｄ Ｔ． Ｓｈｒｉｍｐｔｏｎ， Ｂｕｉｌｄｉｎｇ ａ Ｃｏｌｌｉｓｉｏｎ−Ｒｅｓｉｓｔａｎｔ Ｃｏｍｐｒｅｓｓｉｏｎ Ｆｕｎｃｔｉｏｎ ｆｒｏｍ Ｎｏｎ−ｃｏｍｐｒｅｓｓｉｎｇ Ｐｒｉｍｉｔｉｖｅｓ． ＩＣＡＬＰ ２００８， ｐｐ６４３−６５４， ＬＮＣＳ５１２６
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１に記載されたハッシュ関数は、擬似ランダムオラクルの性質を満たすために４つの異なる関数が必要である。非特許文献２に記載されたハッシュ関数で用いる関数は３つであるが、衝突困難性の性質しか保障しておらず、擬似ランダムオラクルの性質を保障していない。
本発明は、例えば、少ない数の関数を用いつつ、安全性の高いハッシュ関数を構成することを目的とする。
【課題を解決するための手段】
【０００７】
この発明に係るハッシュ値演算装置は、
ｉ個（ｉは１以上の整数）のｎビット長（ｎは１以上の整数）の値ｍ［１］，．．．，値ｍ［ｉ］を入力する既定長値入力部と、
ｊ＝１からｉまで順に、値ｗ［ｊ−１］（値ｗ［０］は固定値ＩＶとする）を入力として関数ｆ１を計算してｎビット長の値ｘ［ｊ］を求め、前記既定長値入力部が入力した値ｍ［ｊ］を入力として関数ｆ２を計算してｎビット長の値ｙ［ｊ］を求め、値ｘ［ｊ］と値ｙ［ｊ］との排他的論理和を入力として関数ｆ３を計算して値ｚ［ｊ］を求め、値ｙ［ｊ］と値ｚ［ｊ］との排他的論理和を計算して値ｗ［ｊ］を求める第１関数計算部と、
前記第１関数計算部が求めた値ｗ［ｉ］を入力として置換関数ｐを計算して、ｎビット長の値ａを求める第２関数計算部と、
前記第２関数計算部が求めた値ａを入力として前記関数ｆ２を計算してｎビット長の値ｗを求める第３関数計算部と、
前記第３関数計算部が計算した値ｗを出力する出力部と
を備えることを特徴とする。
【発明の効果】
【０００８】
この発明に係るハッシュ値演算装置によれば、３つの関数を用いて、安全性の高いハッシュ関数を構成することができる。
【図面の簡単な説明】
【０００９】
【図１】実施の形態１に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図２】図１に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図３】図１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【発明を実施するための形態】
【００１０】
実施の形態１．
まず、ハッシュ関数の安全性の概念について説明する。
【００１１】
ランダムオラクルの性質を満たすハッシュ関数は、理想的なハッシュ関数である。
ランダムオラクルの性質を満たすハッシュ関数Ｈとは、以下の１，２が与えられたハッシュ関数である。
１．（リスト）：全ての入力値と、各入力値に対してランダムに選択した出力値とのペアを記録したリストを持つ。
２．（順方向の値を出力するオラクル）：入力値ｘに対し、リストから入力値ｘに対する出力値ｚを検索して、値ｚを出力する。つまり、Ｈ（ｘ）＝ｚとなる値ｚを出力する。
【００１２】
ランダムオラクルの性質を満たすハッシュ関数は、「（１）衝突困難性」、「（２）第二原像計算困難性」、「（３）原像計算困難性」の３つの性質を満たす。
（１）〜（３）の各性質の定義は以下の通りである。以下の定義において、「Ｈ」は、ハッシュ関数を示す。「Ｍ」「Ｍ’（≠Ｍ）」は、ハッシュ関数Ｈの入力値を示す。「Ｈ（ｘ）」は、ｘを入力したハッシュ関数Ｈの出力（ハッシュ値）を示す。
【００１３】
（１）衝突困難性を満たすハッシュ関数とは、「Ｈ（Ｍ）＝Ｈ（Ｍ’）」となる２つの入力値Ｍ、Ｍ’を見つけることが困難なハッシュ関数である。つまり、衝突困難性とは、ハッシュ値が同じである複数の入力値を求めることが難しいという性質である。
（２）第二原像計算困難性を満たすハッシュ関数とは、ランダムな入力値Ｍが与えられたとき、「Ｈ（Ｍ）＝Ｈ（Ｍ’）」を満たす入力値Ｍ’を見つけることが困難なハッシュ関数である。つまり、第二原像計算困難性とは、第１の入力値とハッシュ値が同じである第２の入力値を求めることが難しいという性質である。
（３）原像計算困難性を満たすハッシュ関数とは、ランダムな値ｚが与えられたとき、「ｚ＝Ｈ（Ｍ）」を満たすＭを見つけることが困難なハッシュ関数である。つまり、原像計算困難性とは、ハッシュ値に対応する入力値を求めることが難しいという性質である。
【００１４】
（１）〜（３）各性質には、（１）衝突困難性を満たすハッシュ関数は（２）第二原像計算困難性を満たし、（２）第二原像計算困難性を満たすハッシュ関数は（３）原像計算困難性を満たすという関係がある。
また、（３）原像計算困難性が破られたハッシュ関数（原像計算困難性を満たさないハッシュ関数）は、（１）衝突困難性、及び、（２）第二原像計算困難性を満たさないという関係がある。つまり、原像計算困難性が破られたハッシュ関数は、安全なハッシュ関数が満たすべき（１）〜（３）の性質を満たさない関数であり、安全性が低いため一般的に使い物にならない。
【００１５】
標準的な公開鍵暗号、電子署名アルゴリズムであるＲＳＡ−ＯＡＥＰ（ＲＳＡ−Ｏｐｔｉｍａｌ Ａｓｙｍｍｅｔｒｉｃ Ｅｎｃｒｙｐｔｉｏｎ Ｐａｄｄｉｎｇ）、ＲＳＡ−ＫＥＭ（ＲＳＡ−Ｋｅｙ Ｅｎｃａｐｓｕｌａｔｉｏｎ Ｍｅｃｈａｎｉｓｍ）、ＲＳＡ−ＰＳＳ（ＲＳＡ−Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅ）などは、用いられるハッシュ関数がランダムオラクルの性質を満たすと仮定したときに安全なものである。
しかし、ランダムオラクルの性質を満たすハッシュ関数を実現することは困難であることが知られている。そのため、これらの公開鍵暗号、電子署名アルゴリズムを実現する際は、ランダムオラクルの性質を満たすハッシュ関数に代え、ＳＨＡ−２５６（Ｓｅｃｕｒｅ Ｈａｓｈ Ａｌｇｏｒｉｔｈｍ−２５６）などのハッシュ関数を用いて運用されている。
【００１６】
ランダムオラクルの性質を満たさないハッシュ関数を用いて、上述した公開鍵暗号、電子署名アルゴリズムを実現した場合、その安全性が保証されるとは限らない。しかし、その安全性が保証するための概念として、擬似ランダムオラクルという概念が存在する。
ここで、ハッシュ関数で用いる内部関数をＰ、Ｐを用いて構成したハッシュ関数をＨ［Ｐ］とする。Ｈ［Ｐ］が擬似ランダムオラクルの性質を満たすとは、どんな識別者でも、Ｈ［Ｐ］とランダムオラクルの性質を満たすハッシュ関数とを識別できないようなＰをシミュレートするシミュレータＳが存在することである。
【００１７】
Ｈ［Ｐ］が擬似ランダムオラクルの性質を満たすならば、Ｈ［Ｐ］は（１）衝突困難性、（２）第二原像計算困難性、（３）原像計算困難性の性質を満たす。そして、ランダムオラクルの性質を満たすハッシュ関数を用いた場合に安全な暗号アルゴリズムは、Ｈ［Ｐ］を用いた場合にも安全であることが保証される。
【００１８】
擬似ランダムオラクルの性質を満たすハッシュ関数には、例えば、非特許文献１に記載されたハッシュ関数等がある。非特許文献１に記載されたハッシュ関数等、擬似ランダムオラクルの性質を満たすハッシュ関数は、内部関数としてランダムオラクルの性質を満たす（理想化された）非圧縮な関数を用いて構成される。つまり、非特許文献１に記載されたハッシュ関数等は、内部関数としてランダムオラクルの性質を満たす非圧縮な関数を用いた場合に、擬似ランダムオラクルの性質を満たす。
【００１９】
ランダムオラクルの性質を満たす関数ｆ（ＦＩＬＲＯ（Ｆｉｘｅｄ Ｉｎｐｕｔ Ｌｅｎｇｔｈ Ｒａｎｄｏｍ Ｏｒａｃｌｅ））とは、以下の１，２が与えられた関数である。
１．（リスト）：全ての入力値と、各入力値に対してランダムに選択した出力値とのペアを記録したリストを持つ。
２．（順方向の値を出力するオラクル）：入力値（ｘ）に対し、リストから入力に対する出力値ｚを検索して、値ｚを出力する。つまり、ｆ（ｘ）＝ｚとなる値ｚを出力する。
【００２０】
ランダムオラクルの性質を満たす関数を実現することは困難であることが知られている。そのため、非特許文献１に記載されたハッシュ関数等、擬似ランダムオラクルの性質を満たすハッシュ関数を実現する際は、ランダムオラクルの性質を満たす関数に代え、例えば、（１）衝突困難性、（２）第二原像計算困難性、（３）原像計算困難性の３つの性質に相当する性質を満たす関数を用いることが考えられる。つまり、（１）出力値が同じである複数の入力値を求めることが難しいという性質、（２）第１の入力値と出力値が同じである第２の入力値を求めることが難しいという性質、（３）出力値に対応する入力値を求めることが難しいという性質という３つの性質を満たす関数を用いることが考えられる。
この場合、ランダムオラクルの性質を満たす関数を用いていないため、得られたハッシュ関数は、擬似ランダムオラクルの性質を満たすハッシュ関数とはならない。しかし、ランダムオラクルの性質を満たす関数を用いた場合に安全であることが証明されているため、ある程度の安全性があるものと認められる。
【００２１】
以下の説明では、非特許文献１に記載されたハッシュ関数と同様に、非圧縮な関数を用いたハッシュ関数について説明する。以下で説明するハッシュ関数は、非特許文献１に記載されたハッシュ関数と同様に、用いる非圧縮な関数がランダムオラクルの性質を満たす場合、擬似ランダムオラクルの性質を満たす。しかし、以下で説明するハッシュ値の計算方法では、非圧縮な関数を３つだけ用いる。したがって、用いる関数の数が少ないため、例えば、以下で説明するハッシュ値の計算方法を回路で実現した場合、回路規模を小さくすることができる。
【００２２】
なお、以下の説明では、内部関数として、異なる３つの非圧縮な関数ｆ１，ｆ２，ｆ３を用いる。また、関数ｆ１，ｆ２，ｆ３の入力長及び出力長をｎビット（ｎは１以上の整数）とする。また、ｐをｎビットの置換関数とし、任意のｘに対してｐ（ｘ）≠ｘを満たす関数とする。例えば、ｐ（ａ）＝ａ＋１がその例であり、ｐは容易に実現可能な関数（非常に小さな回路で実現可能な関数）なので、内部関数には数えず、ハッシュ関数の構造の一部とみなしている。
【００２３】
図１は、実施の形態１に係るハッシュ値演算装置１０の機能を示す機能ブロック図である。
図２は、図１に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図３は、図１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【００２４】
図１に示すハッシュ値演算装置１０の機能と動作について、図２、図３を用いて説明する。
図１に示すハッシュ値演算装置１０は、任意長値入力部１１、パディング部１２、分割部１３、既定長値入力部１４、関数計算部１５、出力部１６を備える。
【００２５】
（Ｓ１：任意長値入力ステップ）
任意長値入力部１１は、任意ビット長の値Ｍを入力装置により入力する。
【００２６】
（Ｓ２：パディングステップ）
パディング部１２は、（Ｓ１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加してｎビットのｉ倍（ｉは１以上の整数）のビット長の値Ｍ’を処理装置により生成して記憶装置に記憶する。
パディング関数ｐａｄとしては、例えば、Ｍ’＝ｐａｄ（Ｍ）＝Ｍ｜｜１｜｜０．．．０｜｜＜Ｍ＞などがある。ここで、＜Ｍ＞は、例えば、６４ビットの値であり、Ｍのビット長情報を含む値である。つまり、パディング部１２は、先頭が“１”で、その後が複数の“０”で、最後に＜Ｍ＞となるビット列を生成して、値Ｍに付加して、値Ｍ’を生成する。なお、Ｍ’がｎの倍数のビット長となるように０の個数が決定される。
【００２７】
（Ｓ３：分割ステップ）
分割部１３は、（Ｓ２）で生成された値Ｍ’を処理装置により、先頭からｎビット毎にｉ個に分割して、ｎビット長の値ｍ［１］，．．．，値ｍ［ｉ］を生成して記憶装置に記憶する。
【００２８】
（Ｓ４：既定長値入力ステップ）
既定長値入力部１４は、分割部１３が生成したｎビット長のｉ個の値ｍ［１］，．．．，値ｍ［ｉ］を入力装置により入力する。
【００２９】
（Ｓ５：関数計算ステップ）
関数計算ステップは、（Ｓ５１）から（Ｓ５５）までの５つのステップを備える。
まず、関数計算部１５は、ｗ［０］にＩＶを設定して記憶装置に記憶する（Ｓ５１）。ここで、ＩＶは、ｎビットの固定値である。
【００３０】
続いて、第１関数計算部１５１は、ｊ＝１，．．．，ｉの各ｊについて順に、（Ｓ５２）から（Ｓ５４）を実行する。
第１関数計算部１５１は、処理装置により、ｘ［ｊ］＝ｆ１（ｗ［ｊ−１］），ｙ［ｊ］＝ｆ２（ｍ［ｊ］）を計算する（Ｓ５２）。つまり、第１関数計算部１５１は、ｎビット長の値ｗ［ｊ−１］を入力として、関数ｆ１を計算してｎビット長の値ｘ［ｊ］を求めるとともに、ｎビット長の値ｍ［ｊ］を入力として、関数ｆ２を計算してｎビット長の値ｙ［ｊ］を求める。
次に、第１関数計算部１５１は、処理装置により、ｚ［ｊ］＝ｆ３（ｘ［ｊ］＾ｙ［ｊ］）を計算する（Ｓ５３）。ここで、ｘ［ｊ］＾ｙ［ｊ］は、ｘ［ｊ］とｙ［ｊ］との排他的論理和である。つまり、第１関数計算部１５１は、ｎビット長の値ｘ［ｊ］とｎビット長の値ｙ［ｊ］との排他的論理和を計算するとともに、計算した（ｎビット長の）排他的論理和を入力として、関数ｆ３を計算してｎビット長の値ｚ［ｊ］を求める。
そして、第１関数計算部１５１は、処理装置により、ｗ［ｊ］＝ｙ［ｊ］＾ｚ［ｊ］を計算する（Ｓ５４）。つまり、第１関数計算部１５１は、ｎビット長の値ｙ［ｊ］とｎビット長の値ｚ［ｊ］との排他的論理和を計算してｎビット長の値ｗ［ｊ］を求める。
ｊ＝１，．．．，ｉの各ｊについて順に（Ｓ５２）から（Ｓ５４）が実行されることにより、ｗ［ｉ］が計算される。
【００３１】
次に、第２関数計算部１５２は、処理装置により、ａ＝ｐ（ｗ［ｉ］）を計算する（Ｓ５５）。つまり、第２関数計算部１５２は、ｎビット長の値ｗ［ｉ］を入力として、置換関数ｐを計算してｎビット長の値ａを求める。
【００３２】
そして、第３関数計算部１５３は、処理装置により、ｗ＝ｆ１（ａ）を計算する（Ｓ５６）。つまり、第３関数計算部１５３は、ｎビット長の値ａを入力として、関数ｆ１を計算してｎビット長の値ｗを求める。
【００３３】
（Ｓ６：出力ステップ）
出力部１６は、関数計算部１５が求めたｎビット長の値ｗをハッシュ値として、出力装置から出力する。
【００３４】
なお、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。ストリーム処理とは、入力された先頭のビットから到着順に処理を行う方法であり、並列処理の一類型である。
【００３５】
また、内部関数ｆ１，ｆ２，ｆ３としては、例えば、３つのブロック暗号の暗号化関数を用いてもよい。
ブロック暗号の暗号化関数Ｅは、鍵ｋと、平文情報ｍとを入力として、平文情報ｍと同じビット長の暗号文ｃを計算する関数である。つまり、ｃ＝Ｅ（ｋ，ｍ）である。なお、暗号化関数Ｅを暗号処理で用いる場合、暗号文ｃを作成す者及び復号する者以外には鍵ｋは秘密にされる。
ここで、任意の値＊に対して、Ｅ（ｋ，＊）は、任意の値＊を他の値に置換する置換関数となる。そのため、関数Ｅをハッシュ関数における内部関数として用いることができる。なお、この場合、鍵ｋは公開パラメータとされる。
例えば、Ｅ１，Ｅ２，Ｅ３をブロック暗号の暗号化関数、ｋ［１］，ｋ［２］，ｋ［３］を公開パラメータとした場合、関数ｆ１，ｆ２，ｆ３を、ｆ１（ａ）＝Ｅ１（ｋ［１］，ａ）＾ａ、ｆ２（ａ）＝Ｅ２（ｋ［２］，ａ）＾ａ、ｆ３（ａ）＝Ｅ３（ｋ［３］，ａ）＾ａとしてもよい。ここで、ｋ［ｔ］≠ｋ［ｓ］ならば、Ｅｔ＝Ｅｓであってもよい。
【００３６】
また、Ｐ１，Ｐ２，Ｐ３をそれぞれ異なる置換関数とした場合、関数ｆ１，ｆ２，ｆ３を、ｆ１（ａ）＝Ｐ１（ａ）＾ａ、ｆ２（ａ）＝Ｐ２（ａ）＾ａ、ｆ３（ａ）＝Ｐ３（ａ）＾ａとしてもよい。
特に、Ｐ１，Ｐ２，Ｐ３は、（１）出力値が同じである複数の入力値を求めることが難しいという性質、（２）第１の入力値と出力値が同じである第２の入力値を求めることが難しいという性質、（３）出力値に対応する入力値を求めることが難しいという性質という３つの性質を満たす置換関数であることが望ましい。
【００３７】
以上に説明したハッシュ値演算装置１０は、例えば、回路やソフトウェア等で構成される。回路で構成される場合には、上記説明における処理装置は、例えば演算回路であり、記憶装置は、例えばレジスタである。また、ソフトウェアで構成される場合には、上記説明における処理装置は、例えばＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）であり、記憶装置は、例えばＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）である。また、上記説明における入力装置は、例えばキーボード、通信ボードであり、出力装置は、例えばＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）等の表示装置、通信ボード、レジスタやＲＡＭ等の記憶装置である。もちろん、これらに限定されるものではない。
なお、ハッシュ値演算装置１０を回路で構成する場合、上述した「〜部」を「〜回路」と読み変えてもよい。また、上述した「〜部」は、「〜処理」、「〜装置」、「〜機器」、「〜手段」、「〜手順」、「〜機能」と読み替えてもよい。つまり、「〜部」として説明するものは、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実現されても構わない。
【００３８】
ハッシュ関数は計算機パワーのない小型なもので実装することがあるため、回路規模が小さいものが望ましい。上述したように、ハッシュ値演算装置１０は、３つの内部関数で構成でき、内部関数が少ないため、回路規模を小さくすることができる。
【符号の説明】
【００３９】
１０ ハッシュ値演算装置、１１ 任意長値入力部、１２ パディング部、１３ 分割部、１４ 既定長値入力部、１５ 関数計算部、１５１ 第１関数計算部、１５２ 第２関数計算部、１５３ 第３関数計算部、１６ 出力部。
【技術分野】
【０００１】
この発明は、例えば、安全性の高いハッシュ値を計算する技術に関する。
【背景技術】
【０００２】
ハッシュ関数は、任意長の値を入力として、固定長の値を出力する関数である。
【０００３】
非特許文献１には、非圧縮な４つの関数ｆ１，ｆ２，ｆ３，ｆ４を用いて擬似ランダムオラクルの性質を満たすハッシュ関数を構成することについての記載がある。ここで、非特許文献１においてハッシュ関数が擬似ランダムオラクルの性質を満たすためには、４つの関数ｆ１，ｆ２，ｆ３，ｆ４がランダムオラクルである必要がある。なお、非圧縮な関数とは、入力長と出力長とが同じ関数である。
【０００４】
非特許文献２には、非圧縮な３つの関数ｆ１，ｆ２，ｆ３を用いて、衝突困難性の性質を満たすハッシュ関数を構成することについての記載がある。ここで、非特許文献２においてハッシュ関数が衝突困難性の性質を満たすためには、３つの関数ｆ１，ｆ２，ｆ３がランダムオラクルである必要がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｙ． Ｄｏｄｉｓ， Ｔ． Ｒｉｓｔｅｎｐａｒｔ ａｎｄ Ｔ． Ｓｈｒｉｍｐｔｏｎ， Ｓａｌｖａｇｉｎｇ Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ ｆｏｒ Ｐｒａｃｔｉｃａｌ Ａｐｐｌｉｃａｔｉｏｎｓ． ＥＵＲＯＣＲＹＰＴ ２００９， ｐｐ ３７１−３８８， ＬＮＣＳ ５４７９
【非特許文献２】Ｔ． Ｒｉｓｔｅｎｐａｒｔ ａｎｄ Ｔ． Ｓｈｒｉｍｐｔｏｎ， Ｂｕｉｌｄｉｎｇ ａ Ｃｏｌｌｉｓｉｏｎ−Ｒｅｓｉｓｔａｎｔ Ｃｏｍｐｒｅｓｓｉｏｎ Ｆｕｎｃｔｉｏｎ ｆｒｏｍ Ｎｏｎ−ｃｏｍｐｒｅｓｓｉｎｇ Ｐｒｉｍｉｔｉｖｅｓ． ＩＣＡＬＰ ２００８， ｐｐ６４３−６５４， ＬＮＣＳ５１２６
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１に記載されたハッシュ関数は、擬似ランダムオラクルの性質を満たすために４つの異なる関数が必要である。非特許文献２に記載されたハッシュ関数で用いる関数は３つであるが、衝突困難性の性質しか保障しておらず、擬似ランダムオラクルの性質を保障していない。
本発明は、例えば、少ない数の関数を用いつつ、安全性の高いハッシュ関数を構成することを目的とする。
【課題を解決するための手段】
【０００７】
この発明に係るハッシュ値演算装置は、
ｉ個（ｉは１以上の整数）のｎビット長（ｎは１以上の整数）の値ｍ［１］，．．．，値ｍ［ｉ］を入力する既定長値入力部と、
ｊ＝１からｉまで順に、値ｗ［ｊ−１］（値ｗ［０］は固定値ＩＶとする）を入力として関数ｆ１を計算してｎビット長の値ｘ［ｊ］を求め、前記既定長値入力部が入力した値ｍ［ｊ］を入力として関数ｆ２を計算してｎビット長の値ｙ［ｊ］を求め、値ｘ［ｊ］と値ｙ［ｊ］との排他的論理和を入力として関数ｆ３を計算して値ｚ［ｊ］を求め、値ｙ［ｊ］と値ｚ［ｊ］との排他的論理和を計算して値ｗ［ｊ］を求める第１関数計算部と、
前記第１関数計算部が求めた値ｗ［ｉ］を入力として置換関数ｐを計算して、ｎビット長の値ａを求める第２関数計算部と、
前記第２関数計算部が求めた値ａを入力として前記関数ｆ２を計算してｎビット長の値ｗを求める第３関数計算部と、
前記第３関数計算部が計算した値ｗを出力する出力部と
を備えることを特徴とする。
【発明の効果】
【０００８】
この発明に係るハッシュ値演算装置によれば、３つの関数を用いて、安全性の高いハッシュ関数を構成することができる。
【図面の簡単な説明】
【０００９】
【図１】実施の形態１に係るハッシュ値演算装置１０の機能を示す機能ブロック図。
【図２】図１に示すハッシュ値演算装置１０の動作を示すフローチャート。
【図３】図１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図。
【発明を実施するための形態】
【００１０】
実施の形態１．
まず、ハッシュ関数の安全性の概念について説明する。
【００１１】
ランダムオラクルの性質を満たすハッシュ関数は、理想的なハッシュ関数である。
ランダムオラクルの性質を満たすハッシュ関数Ｈとは、以下の１，２が与えられたハッシュ関数である。
１．（リスト）：全ての入力値と、各入力値に対してランダムに選択した出力値とのペアを記録したリストを持つ。
２．（順方向の値を出力するオラクル）：入力値ｘに対し、リストから入力値ｘに対する出力値ｚを検索して、値ｚを出力する。つまり、Ｈ（ｘ）＝ｚとなる値ｚを出力する。
【００１２】
ランダムオラクルの性質を満たすハッシュ関数は、「（１）衝突困難性」、「（２）第二原像計算困難性」、「（３）原像計算困難性」の３つの性質を満たす。
（１）〜（３）の各性質の定義は以下の通りである。以下の定義において、「Ｈ」は、ハッシュ関数を示す。「Ｍ」「Ｍ’（≠Ｍ）」は、ハッシュ関数Ｈの入力値を示す。「Ｈ（ｘ）」は、ｘを入力したハッシュ関数Ｈの出力（ハッシュ値）を示す。
【００１３】
（１）衝突困難性を満たすハッシュ関数とは、「Ｈ（Ｍ）＝Ｈ（Ｍ’）」となる２つの入力値Ｍ、Ｍ’を見つけることが困難なハッシュ関数である。つまり、衝突困難性とは、ハッシュ値が同じである複数の入力値を求めることが難しいという性質である。
（２）第二原像計算困難性を満たすハッシュ関数とは、ランダムな入力値Ｍが与えられたとき、「Ｈ（Ｍ）＝Ｈ（Ｍ’）」を満たす入力値Ｍ’を見つけることが困難なハッシュ関数である。つまり、第二原像計算困難性とは、第１の入力値とハッシュ値が同じである第２の入力値を求めることが難しいという性質である。
（３）原像計算困難性を満たすハッシュ関数とは、ランダムな値ｚが与えられたとき、「ｚ＝Ｈ（Ｍ）」を満たすＭを見つけることが困難なハッシュ関数である。つまり、原像計算困難性とは、ハッシュ値に対応する入力値を求めることが難しいという性質である。
【００１４】
（１）〜（３）各性質には、（１）衝突困難性を満たすハッシュ関数は（２）第二原像計算困難性を満たし、（２）第二原像計算困難性を満たすハッシュ関数は（３）原像計算困難性を満たすという関係がある。
また、（３）原像計算困難性が破られたハッシュ関数（原像計算困難性を満たさないハッシュ関数）は、（１）衝突困難性、及び、（２）第二原像計算困難性を満たさないという関係がある。つまり、原像計算困難性が破られたハッシュ関数は、安全なハッシュ関数が満たすべき（１）〜（３）の性質を満たさない関数であり、安全性が低いため一般的に使い物にならない。
【００１５】
標準的な公開鍵暗号、電子署名アルゴリズムであるＲＳＡ−ＯＡＥＰ（ＲＳＡ−Ｏｐｔｉｍａｌ Ａｓｙｍｍｅｔｒｉｃ Ｅｎｃｒｙｐｔｉｏｎ Ｐａｄｄｉｎｇ）、ＲＳＡ−ＫＥＭ（ＲＳＡ−Ｋｅｙ Ｅｎｃａｐｓｕｌａｔｉｏｎ Ｍｅｃｈａｎｉｓｍ）、ＲＳＡ−ＰＳＳ（ＲＳＡ−Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅ）などは、用いられるハッシュ関数がランダムオラクルの性質を満たすと仮定したときに安全なものである。
しかし、ランダムオラクルの性質を満たすハッシュ関数を実現することは困難であることが知られている。そのため、これらの公開鍵暗号、電子署名アルゴリズムを実現する際は、ランダムオラクルの性質を満たすハッシュ関数に代え、ＳＨＡ−２５６（Ｓｅｃｕｒｅ Ｈａｓｈ Ａｌｇｏｒｉｔｈｍ−２５６）などのハッシュ関数を用いて運用されている。
【００１６】
ランダムオラクルの性質を満たさないハッシュ関数を用いて、上述した公開鍵暗号、電子署名アルゴリズムを実現した場合、その安全性が保証されるとは限らない。しかし、その安全性が保証するための概念として、擬似ランダムオラクルという概念が存在する。
ここで、ハッシュ関数で用いる内部関数をＰ、Ｐを用いて構成したハッシュ関数をＨ［Ｐ］とする。Ｈ［Ｐ］が擬似ランダムオラクルの性質を満たすとは、どんな識別者でも、Ｈ［Ｐ］とランダムオラクルの性質を満たすハッシュ関数とを識別できないようなＰをシミュレートするシミュレータＳが存在することである。
【００１７】
Ｈ［Ｐ］が擬似ランダムオラクルの性質を満たすならば、Ｈ［Ｐ］は（１）衝突困難性、（２）第二原像計算困難性、（３）原像計算困難性の性質を満たす。そして、ランダムオラクルの性質を満たすハッシュ関数を用いた場合に安全な暗号アルゴリズムは、Ｈ［Ｐ］を用いた場合にも安全であることが保証される。
【００１８】
擬似ランダムオラクルの性質を満たすハッシュ関数には、例えば、非特許文献１に記載されたハッシュ関数等がある。非特許文献１に記載されたハッシュ関数等、擬似ランダムオラクルの性質を満たすハッシュ関数は、内部関数としてランダムオラクルの性質を満たす（理想化された）非圧縮な関数を用いて構成される。つまり、非特許文献１に記載されたハッシュ関数等は、内部関数としてランダムオラクルの性質を満たす非圧縮な関数を用いた場合に、擬似ランダムオラクルの性質を満たす。
【００１９】
ランダムオラクルの性質を満たす関数ｆ（ＦＩＬＲＯ（Ｆｉｘｅｄ Ｉｎｐｕｔ Ｌｅｎｇｔｈ Ｒａｎｄｏｍ Ｏｒａｃｌｅ））とは、以下の１，２が与えられた関数である。
１．（リスト）：全ての入力値と、各入力値に対してランダムに選択した出力値とのペアを記録したリストを持つ。
２．（順方向の値を出力するオラクル）：入力値（ｘ）に対し、リストから入力に対する出力値ｚを検索して、値ｚを出力する。つまり、ｆ（ｘ）＝ｚとなる値ｚを出力する。
【００２０】
ランダムオラクルの性質を満たす関数を実現することは困難であることが知られている。そのため、非特許文献１に記載されたハッシュ関数等、擬似ランダムオラクルの性質を満たすハッシュ関数を実現する際は、ランダムオラクルの性質を満たす関数に代え、例えば、（１）衝突困難性、（２）第二原像計算困難性、（３）原像計算困難性の３つの性質に相当する性質を満たす関数を用いることが考えられる。つまり、（１）出力値が同じである複数の入力値を求めることが難しいという性質、（２）第１の入力値と出力値が同じである第２の入力値を求めることが難しいという性質、（３）出力値に対応する入力値を求めることが難しいという性質という３つの性質を満たす関数を用いることが考えられる。
この場合、ランダムオラクルの性質を満たす関数を用いていないため、得られたハッシュ関数は、擬似ランダムオラクルの性質を満たすハッシュ関数とはならない。しかし、ランダムオラクルの性質を満たす関数を用いた場合に安全であることが証明されているため、ある程度の安全性があるものと認められる。
【００２１】
以下の説明では、非特許文献１に記載されたハッシュ関数と同様に、非圧縮な関数を用いたハッシュ関数について説明する。以下で説明するハッシュ関数は、非特許文献１に記載されたハッシュ関数と同様に、用いる非圧縮な関数がランダムオラクルの性質を満たす場合、擬似ランダムオラクルの性質を満たす。しかし、以下で説明するハッシュ値の計算方法では、非圧縮な関数を３つだけ用いる。したがって、用いる関数の数が少ないため、例えば、以下で説明するハッシュ値の計算方法を回路で実現した場合、回路規模を小さくすることができる。
【００２２】
なお、以下の説明では、内部関数として、異なる３つの非圧縮な関数ｆ１，ｆ２，ｆ３を用いる。また、関数ｆ１，ｆ２，ｆ３の入力長及び出力長をｎビット（ｎは１以上の整数）とする。また、ｐをｎビットの置換関数とし、任意のｘに対してｐ（ｘ）≠ｘを満たす関数とする。例えば、ｐ（ａ）＝ａ＋１がその例であり、ｐは容易に実現可能な関数（非常に小さな回路で実現可能な関数）なので、内部関数には数えず、ハッシュ関数の構造の一部とみなしている。
【００２３】
図１は、実施の形態１に係るハッシュ値演算装置１０の機能を示す機能ブロック図である。
図２は、図１に示すハッシュ値演算装置１０の動作を示すフローチャートである。
図３は、図１に示すハッシュ値演算装置１０により実現されるハッシュ関数の構造図である。
【００２４】
図１に示すハッシュ値演算装置１０の機能と動作について、図２、図３を用いて説明する。
図１に示すハッシュ値演算装置１０は、任意長値入力部１１、パディング部１２、分割部１３、既定長値入力部１４、関数計算部１５、出力部１６を備える。
【００２５】
（Ｓ１：任意長値入力ステップ）
任意長値入力部１１は、任意ビット長の値Ｍを入力装置により入力する。
【００２６】
（Ｓ２：パディングステップ）
パディング部１２は、（Ｓ１）で入力された値Ｍに対して、パディング関数ｐａｄを用いて、所定の値を付加してｎビットのｉ倍（ｉは１以上の整数）のビット長の値Ｍ’を処理装置により生成して記憶装置に記憶する。
パディング関数ｐａｄとしては、例えば、Ｍ’＝ｐａｄ（Ｍ）＝Ｍ｜｜１｜｜０．．．０｜｜＜Ｍ＞などがある。ここで、＜Ｍ＞は、例えば、６４ビットの値であり、Ｍのビット長情報を含む値である。つまり、パディング部１２は、先頭が“１”で、その後が複数の“０”で、最後に＜Ｍ＞となるビット列を生成して、値Ｍに付加して、値Ｍ’を生成する。なお、Ｍ’がｎの倍数のビット長となるように０の個数が決定される。
【００２７】
（Ｓ３：分割ステップ）
分割部１３は、（Ｓ２）で生成された値Ｍ’を処理装置により、先頭からｎビット毎にｉ個に分割して、ｎビット長の値ｍ［１］，．．．，値ｍ［ｉ］を生成して記憶装置に記憶する。
【００２８】
（Ｓ４：既定長値入力ステップ）
既定長値入力部１４は、分割部１３が生成したｎビット長のｉ個の値ｍ［１］，．．．，値ｍ［ｉ］を入力装置により入力する。
【００２９】
（Ｓ５：関数計算ステップ）
関数計算ステップは、（Ｓ５１）から（Ｓ５５）までの５つのステップを備える。
まず、関数計算部１５は、ｗ［０］にＩＶを設定して記憶装置に記憶する（Ｓ５１）。ここで、ＩＶは、ｎビットの固定値である。
【００３０】
続いて、第１関数計算部１５１は、ｊ＝１，．．．，ｉの各ｊについて順に、（Ｓ５２）から（Ｓ５４）を実行する。
第１関数計算部１５１は、処理装置により、ｘ［ｊ］＝ｆ１（ｗ［ｊ−１］），ｙ［ｊ］＝ｆ２（ｍ［ｊ］）を計算する（Ｓ５２）。つまり、第１関数計算部１５１は、ｎビット長の値ｗ［ｊ−１］を入力として、関数ｆ１を計算してｎビット長の値ｘ［ｊ］を求めるとともに、ｎビット長の値ｍ［ｊ］を入力として、関数ｆ２を計算してｎビット長の値ｙ［ｊ］を求める。
次に、第１関数計算部１５１は、処理装置により、ｚ［ｊ］＝ｆ３（ｘ［ｊ］＾ｙ［ｊ］）を計算する（Ｓ５３）。ここで、ｘ［ｊ］＾ｙ［ｊ］は、ｘ［ｊ］とｙ［ｊ］との排他的論理和である。つまり、第１関数計算部１５１は、ｎビット長の値ｘ［ｊ］とｎビット長の値ｙ［ｊ］との排他的論理和を計算するとともに、計算した（ｎビット長の）排他的論理和を入力として、関数ｆ３を計算してｎビット長の値ｚ［ｊ］を求める。
そして、第１関数計算部１５１は、処理装置により、ｗ［ｊ］＝ｙ［ｊ］＾ｚ［ｊ］を計算する（Ｓ５４）。つまり、第１関数計算部１５１は、ｎビット長の値ｙ［ｊ］とｎビット長の値ｚ［ｊ］との排他的論理和を計算してｎビット長の値ｗ［ｊ］を求める。
ｊ＝１，．．．，ｉの各ｊについて順に（Ｓ５２）から（Ｓ５４）が実行されることにより、ｗ［ｉ］が計算される。
【００３１】
次に、第２関数計算部１５２は、処理装置により、ａ＝ｐ（ｗ［ｉ］）を計算する（Ｓ５５）。つまり、第２関数計算部１５２は、ｎビット長の値ｗ［ｉ］を入力として、置換関数ｐを計算してｎビット長の値ａを求める。
【００３２】
そして、第３関数計算部１５３は、処理装置により、ｗ＝ｆ１（ａ）を計算する（Ｓ５６）。つまり、第３関数計算部１５３は、ｎビット長の値ａを入力として、関数ｆ１を計算してｎビット長の値ｗを求める。
【００３３】
（Ｓ６：出力ステップ）
出力部１６は、関数計算部１５が求めたｎビット長の値ｗをハッシュ値として、出力装置から出力する。
【００３４】
なお、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。ストリーム処理とは、入力された先頭のビットから到着順に処理を行う方法であり、並列処理の一類型である。
【００３５】
また、内部関数ｆ１，ｆ２，ｆ３としては、例えば、３つのブロック暗号の暗号化関数を用いてもよい。
ブロック暗号の暗号化関数Ｅは、鍵ｋと、平文情報ｍとを入力として、平文情報ｍと同じビット長の暗号文ｃを計算する関数である。つまり、ｃ＝Ｅ（ｋ，ｍ）である。なお、暗号化関数Ｅを暗号処理で用いる場合、暗号文ｃを作成す者及び復号する者以外には鍵ｋは秘密にされる。
ここで、任意の値＊に対して、Ｅ（ｋ，＊）は、任意の値＊を他の値に置換する置換関数となる。そのため、関数Ｅをハッシュ関数における内部関数として用いることができる。なお、この場合、鍵ｋは公開パラメータとされる。
例えば、Ｅ１，Ｅ２，Ｅ３をブロック暗号の暗号化関数、ｋ［１］，ｋ［２］，ｋ［３］を公開パラメータとした場合、関数ｆ１，ｆ２，ｆ３を、ｆ１（ａ）＝Ｅ１（ｋ［１］，ａ）＾ａ、ｆ２（ａ）＝Ｅ２（ｋ［２］，ａ）＾ａ、ｆ３（ａ）＝Ｅ３（ｋ［３］，ａ）＾ａとしてもよい。ここで、ｋ［ｔ］≠ｋ［ｓ］ならば、Ｅｔ＝Ｅｓであってもよい。
【００３６】
また、Ｐ１，Ｐ２，Ｐ３をそれぞれ異なる置換関数とした場合、関数ｆ１，ｆ２，ｆ３を、ｆ１（ａ）＝Ｐ１（ａ）＾ａ、ｆ２（ａ）＝Ｐ２（ａ）＾ａ、ｆ３（ａ）＝Ｐ３（ａ）＾ａとしてもよい。
特に、Ｐ１，Ｐ２，Ｐ３は、（１）出力値が同じである複数の入力値を求めることが難しいという性質、（２）第１の入力値と出力値が同じである第２の入力値を求めることが難しいという性質、（３）出力値に対応する入力値を求めることが難しいという性質という３つの性質を満たす置換関数であることが望ましい。
【００３７】
以上に説明したハッシュ値演算装置１０は、例えば、回路やソフトウェア等で構成される。回路で構成される場合には、上記説明における処理装置は、例えば演算回路であり、記憶装置は、例えばレジスタである。また、ソフトウェアで構成される場合には、上記説明における処理装置は、例えばＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）であり、記憶装置は、例えばＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）である。また、上記説明における入力装置は、例えばキーボード、通信ボードであり、出力装置は、例えばＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）等の表示装置、通信ボード、レジスタやＲＡＭ等の記憶装置である。もちろん、これらに限定されるものではない。
なお、ハッシュ値演算装置１０を回路で構成する場合、上述した「〜部」を「〜回路」と読み変えてもよい。また、上述した「〜部」は、「〜処理」、「〜装置」、「〜機器」、「〜手段」、「〜手順」、「〜機能」と読み替えてもよい。つまり、「〜部」として説明するものは、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実現されても構わない。
【００３８】
ハッシュ関数は計算機パワーのない小型なもので実装することがあるため、回路規模が小さいものが望ましい。上述したように、ハッシュ値演算装置１０は、３つの内部関数で構成でき、内部関数が少ないため、回路規模を小さくすることができる。
【符号の説明】
【００３９】
１０ ハッシュ値演算装置、１１ 任意長値入力部、１２ パディング部、１３ 分割部、１４ 既定長値入力部、１５ 関数計算部、１５１ 第１関数計算部、１５２ 第２関数計算部、１５３ 第３関数計算部、１６ 出力部。
【特許請求の範囲】
【請求項１】
ｉ個（ｉは１以上の整数）のｎビット長（ｎは１以上の整数）の値ｍ［１］，．．．，値ｍ［ｉ］を入力する既定長値入力部と、
ｊ＝１からｉまで順に、値ｗ［ｊ−１］（値ｗ［０］は固定値ＩＶとする）を入力として関数ｆ１を計算してｎビット長の値ｘ［ｊ］を求め、前記既定長値入力部が入力した値ｍ［ｊ］を入力として関数ｆ２を計算してｎビット長の値ｙ［ｊ］を求め、値ｘ［ｊ］と値ｙ［ｊ］との排他的論理和を入力として関数ｆ３を計算して値ｚ［ｊ］を求め、値ｙ［ｊ］と値ｚ［ｊ］との排他的論理和を計算して値ｗ［ｊ］を求める第１関数計算部と、
前記第１関数計算部が求めた値ｗ［ｉ］を入力として置換関数ｐを計算して、ｎビット長の値ａを求める第２関数計算部と、
前記第２関数計算部が求めた値ａを入力として前記関数ｆ１を計算してｎビット長の値ｗを求める第３関数計算部と、
前記第３関数計算部が計算した値ｗを出力する出力部と
を備えることを特徴とするハッシュ値演算装置。
【請求項２】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Ｍを入力する任意長値入力部と、
前記任意長値入力部が入力した値Ｍに対して、所定の値を付加してｎビット長のｉ倍のビット長の値Ｍ’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値Ｍ’を分割して、ｎビット長の値ｍ［１］，．．．，値ｍ［ｉ］を生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値ｍ［１］，．．．，値ｍ［ｉ］を入力する
ことを特徴とする請求項１に記載のハッシュ値演算装置。
【請求項３】
前記関数ｆ１，ｆ２，ｆ３は、それぞれ、ｎビットの値が入力された場合に、ｎビットの暗号文ｃを計算する暗号化関数Ｅ１，Ｅ２，Ｅ３である
ことを特徴とする請求項１又は２に記載のハッシュ値演算装置。
【請求項４】
前記関数ｆ１，ｆ２，ｆ３は、それぞれ、ｎビットの入力値が入力された場合に、ｎビットの暗号文を計算する暗号化関数Ｅ１，Ｅ２，Ｅ３を用いて、入力値に対する暗号文を計算するとともに、計算した暗号文と、前記入力値との排他的論理和を計算して出力する関数である
ことを特徴とする請求項１又は２に記載のハッシュ値演算装置。
【請求項５】
前記関数ｆ１，ｆ２，ｆ３は、それぞれ、ｎビットの入力値が入力された場合に、前記入力値とは異なるｎビットの出力値を計算する置換関数を用いて、入力値に対する出力値を計算するとともに、計算した出力値と、前記入力値との排他的論理和を計算して出力する関数である
ことを特徴とする請求項１又は２に記載のハッシュ値演算装置。
【請求項６】
ｉ個（ｉは１以上の整数）のｎビット長（ｎは１以上の整数）の値ｍ［１］，．．．，値ｍ［ｉ］を入力する既定長値入力ステップと、
ｊ＝１からｉまで順に、値ｗ［ｊ−１］（値ｗ［０］は固定値ＩＶとする）を入力として関数ｆ１を計算してｎビット長の値ｘ［ｊ］を求め、前記既定長値入力ステップで入力した値ｍ［ｊ］を入力として関数ｆ２を計算してｎビット長の値ｙ［ｊ］を求め、値ｘ［ｊ］と値ｙ［ｊ］との排他的論理和を入力として関数ｆ３を計算して値ｚ［ｊ］を求め、値ｙ［ｊ］と値ｚ［ｊ］との排他的論理和を計算して値ｗ［ｊ］を求める第１関数計算ステップと、
前記第１関数計算ステップで求めた値ｗ［ｉ］を入力として置換関数ｐを計算して、ｎビット長の値ａを求める第２関数計算ステップと、
前記第２関数計算ステップで求めた値ａを入力として前記関数ｆ１を計算してｎビット長の値ｗを求める第３関数計算ステップと、
前記第３関数計算ステップで計算した値ｗを出力する出力ステップと
を備えることを特徴とするハッシュ値演算方法。
【請求項７】
ｉ個（ｉは１以上の整数）のｎビット長（ｎは１以上の整数）の値ｍ［１］，．．．，値ｍ［ｉ］を入力する既定長値入力処理と、
ｊ＝１からｉまで順に、値ｗ［ｊ−１］（値ｗ［０］は固定値ＩＶとする）を入力として関数ｆ１を計算してｎビット長の値ｘ［ｊ］を求め、前記既定長値入力処理で入力した値ｍ［ｊ］を入力として関数ｆ２を計算してｎビット長の値ｙ［ｊ］を求め、値ｘ［ｊ］と値ｙ［ｊ］との排他的論理和を入力として関数ｆ３を計算して値ｚ［ｊ］を求め、値ｙ［ｊ］と値ｚ［ｊ］との排他的論理和を計算して値ｗ［ｊ］を求める第１関数計算処理と、
前記第１関数計算処理で求めた値ｗ［ｉ］を入力として置換関数ｐを計算して、ｎビット長の値ａを求める第２関数計算処理と、
前記第２関数計算処理で求めた値ａを入力として前記関数ｆ１を計算してｎビット長の値ｗを求める第３関数計算処理と、
前記第３関数計算処理で計算した値ｗを出力する出力処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項１】
ｉ個（ｉは１以上の整数）のｎビット長（ｎは１以上の整数）の値ｍ［１］，．．．，値ｍ［ｉ］を入力する既定長値入力部と、
ｊ＝１からｉまで順に、値ｗ［ｊ−１］（値ｗ［０］は固定値ＩＶとする）を入力として関数ｆ１を計算してｎビット長の値ｘ［ｊ］を求め、前記既定長値入力部が入力した値ｍ［ｊ］を入力として関数ｆ２を計算してｎビット長の値ｙ［ｊ］を求め、値ｘ［ｊ］と値ｙ［ｊ］との排他的論理和を入力として関数ｆ３を計算して値ｚ［ｊ］を求め、値ｙ［ｊ］と値ｚ［ｊ］との排他的論理和を計算して値ｗ［ｊ］を求める第１関数計算部と、
前記第１関数計算部が求めた値ｗ［ｉ］を入力として置換関数ｐを計算して、ｎビット長の値ａを求める第２関数計算部と、
前記第２関数計算部が求めた値ａを入力として前記関数ｆ１を計算してｎビット長の値ｗを求める第３関数計算部と、
前記第３関数計算部が計算した値ｗを出力する出力部と
を備えることを特徴とするハッシュ値演算装置。
【請求項２】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Ｍを入力する任意長値入力部と、
前記任意長値入力部が入力した値Ｍに対して、所定の値を付加してｎビット長のｉ倍のビット長の値Ｍ’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値Ｍ’を分割して、ｎビット長の値ｍ［１］，．．．，値ｍ［ｉ］を生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値ｍ［１］，．．．，値ｍ［ｉ］を入力する
ことを特徴とする請求項１に記載のハッシュ値演算装置。
【請求項３】
前記関数ｆ１，ｆ２，ｆ３は、それぞれ、ｎビットの値が入力された場合に、ｎビットの暗号文ｃを計算する暗号化関数Ｅ１，Ｅ２，Ｅ３である
ことを特徴とする請求項１又は２に記載のハッシュ値演算装置。
【請求項４】
前記関数ｆ１，ｆ２，ｆ３は、それぞれ、ｎビットの入力値が入力された場合に、ｎビットの暗号文を計算する暗号化関数Ｅ１，Ｅ２，Ｅ３を用いて、入力値に対する暗号文を計算するとともに、計算した暗号文と、前記入力値との排他的論理和を計算して出力する関数である
ことを特徴とする請求項１又は２に記載のハッシュ値演算装置。
【請求項５】
前記関数ｆ１，ｆ２，ｆ３は、それぞれ、ｎビットの入力値が入力された場合に、前記入力値とは異なるｎビットの出力値を計算する置換関数を用いて、入力値に対する出力値を計算するとともに、計算した出力値と、前記入力値との排他的論理和を計算して出力する関数である
ことを特徴とする請求項１又は２に記載のハッシュ値演算装置。
【請求項６】
ｉ個（ｉは１以上の整数）のｎビット長（ｎは１以上の整数）の値ｍ［１］，．．．，値ｍ［ｉ］を入力する既定長値入力ステップと、
ｊ＝１からｉまで順に、値ｗ［ｊ−１］（値ｗ［０］は固定値ＩＶとする）を入力として関数ｆ１を計算してｎビット長の値ｘ［ｊ］を求め、前記既定長値入力ステップで入力した値ｍ［ｊ］を入力として関数ｆ２を計算してｎビット長の値ｙ［ｊ］を求め、値ｘ［ｊ］と値ｙ［ｊ］との排他的論理和を入力として関数ｆ３を計算して値ｚ［ｊ］を求め、値ｙ［ｊ］と値ｚ［ｊ］との排他的論理和を計算して値ｗ［ｊ］を求める第１関数計算ステップと、
前記第１関数計算ステップで求めた値ｗ［ｉ］を入力として置換関数ｐを計算して、ｎビット長の値ａを求める第２関数計算ステップと、
前記第２関数計算ステップで求めた値ａを入力として前記関数ｆ１を計算してｎビット長の値ｗを求める第３関数計算ステップと、
前記第３関数計算ステップで計算した値ｗを出力する出力ステップと
を備えることを特徴とするハッシュ値演算方法。
【請求項７】
ｉ個（ｉは１以上の整数）のｎビット長（ｎは１以上の整数）の値ｍ［１］，．．．，値ｍ［ｉ］を入力する既定長値入力処理と、
ｊ＝１からｉまで順に、値ｗ［ｊ−１］（値ｗ［０］は固定値ＩＶとする）を入力として関数ｆ１を計算してｎビット長の値ｘ［ｊ］を求め、前記既定長値入力処理で入力した値ｍ［ｊ］を入力として関数ｆ２を計算してｎビット長の値ｙ［ｊ］を求め、値ｘ［ｊ］と値ｙ［ｊ］との排他的論理和を入力として関数ｆ３を計算して値ｚ［ｊ］を求め、値ｙ［ｊ］と値ｚ［ｊ］との排他的論理和を計算して値ｗ［ｊ］を求める第１関数計算処理と、
前記第１関数計算処理で求めた値ｗ［ｉ］を入力として置換関数ｐを計算して、ｎビット長の値ａを求める第２関数計算処理と、
前記第２関数計算処理で求めた値ａを入力として前記関数ｆ１を計算してｎビット長の値ｗを求める第３関数計算処理と、
前記第３関数計算処理で計算した値ｗを出力する出力処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１２−１４０７７（Ｐ２０１２−１４０７７Ａ）
【公開日】平成２４年１月１９日（２０１２．１．１９）
【国際特許分類】
【出願番号】特願２０１０−１５２３０４（Ｐ２０１０−１５２３０４）
【出願日】平成２２年７月２日（２０１０．７．２）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２４年１月１９日（２０１２．１．１９）
【国際特許分類】
【出願日】平成２２年７月２日（２０１０．７．２）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]