ハッシュ値演算装置、ハッシュ値演算方法及びハッシュ値演算プログラム
【課題】擬似ランダムオラクルの性質を満たし、かつ、安全性のセキュリティレベルが少なくともO(2n)となるハッシュ関数を構成することを目的とする。
【解決手段】ハッシュ値演算装置は、任意ビット長の値Mを入力として関数Fを計算してtビット長(tは1以上の整数)の値wを求め、値wを入力として関数gを計算してdビット長(dはt以上の整数)の値kを求め、値kを鍵成分とし、nビット長の所定の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求め、値kを鍵成分とし、nビット長の所定の値c2を平文成分として、ブロック暗号の暗号化関数E2を計算してnビット長の値yyを求め、値yと値yyとを入力として関数hを計算してn’ビット長(n’は1以上2n以下の整数)の値zをハッシュ値として求める。
【解決手段】ハッシュ値演算装置は、任意ビット長の値Mを入力として関数Fを計算してtビット長(tは1以上の整数)の値wを求め、値wを入力として関数gを計算してdビット長(dはt以上の整数)の値kを求め、値kを鍵成分とし、nビット長の所定の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求め、値kを鍵成分とし、nビット長の所定の値c2を平文成分として、ブロック暗号の暗号化関数E2を計算してnビット長の値yyを求め、値yと値yyとを入力として関数hを計算してn’ビット長(n’は1以上2n以下の整数)の値zをハッシュ値として求める。
【発明の詳細な説明】
【技術分野】
【0001】
この発明は、例えば、安全性の高いハッシュ値を計算する技術に関する。
【背景技術】
【0002】
ハッシュ関数は、任意長の値を入力として、固定長の値を出力する関数である。
【0003】
非特許文献1〜3には、出力長がnビットのブロック暗号の暗号化関数を用いて、衝突困難性の性質を満たす出力長が2nビットのハッシュ関数の構成法についての記載がある。
ここで、非特許文献1〜3におけるハッシュ関数が衝突困難性の性質を満たすためには、用いる暗号化関数が理想化されたブロック暗号における暗号化関数である必要がある。
【0004】
非特許文献4,5には、出力長がsビットのブロック暗号の暗号化関数を用いて、擬似ランダムオラクルの性質を満たす出力長がnビットのハッシュ関数の構成法についての記載がある。但し、sはn以上の整数である。
ここで、非特許文献4,5におけるハッシュ関数が擬似ランダムオラクルの性質を満たすためには、用いる暗号化関数が理想化されたブロック暗号における暗号化関数である必要がある。また、非特許文献4,5におけるハッシュ関数の安全性のセキュリティレベルはO(2s/2)以下である。なお、安全性のセキュリティレベルとは、擬似ランダムオラクルの性質を破るために必要となる計算量である。
【0005】
非特許文献6には、入出力が固定長でありランダムオラクルの性質を満たす関数と、PrA(Preimage Aware)の性質を満たす任意長入力、固定長出力の関数とを用いて、擬似ランダムオラクルの性質を満たすハッシュ関数を構成することについての記載がある。非特許文献6では、PrAの性質をもつ関数として、出力長がnビットのブロック暗号の暗号化関数を用いている。
ここで、非特許文献6におけるハッシュ関数が、擬似ランダムオラクルの性質を満たすためには、用いる暗号化関数が理想化されたブロック暗号における暗号化関数である必要がある。
【先行技術文献】
【非特許文献】
【0006】
【非特許文献1】O. Ozen and M. Stam. Another Glance at Double−length Hashing. IMA Int. Conf. 2009. pp176−201. LNCS 5921.
【非特許文献2】S. Hirose. Some Plausible Constructions of Double−Block−length Hash Functions. FSE 2006. 210−225. LNCS 4047.
【非特許文献3】X. Lai and J. Massey: Hash Function Based on Block Ciphers. EUROCRYPT 1992. pp55−70. LNCS 653.
【非特許文献4】Shoichi Hirose, Je. Park, and A. Yun. A Simple Variant of the Merkle−Damgard Scheme with a Permutation. ASIACRYPT 2007. pp113−129. LNCS 4833.
【非特許文献5】J.−S. Coron, Y. Dodis, C. Malinaud, and P. Puniya. Merkle−Damgard Revisited: How to Construct a Hash Function. CRYPTO 2005. pp430−448. LNCS 3621.
【非特許文献6】Y. Dodis, T. Ristenpart, and T. Shrimpton. Salvaging Merkle−Damgard for Practical Applications. EUROCRYPT 2009. pp371−388. LNCS 5479.
【発明の概要】
【発明が解決しようとする課題】
【0007】
非特許文献1〜3に記載されたハッシュ関数は、ブロック暗号の暗号化関数を用いたハッシュ関数であるが、擬似ランダムオラクルの性質を満たさない。
非特許文献4,5に記載されたハッシュ関数は、ブロック暗号の暗号化関数を用いたハッシュ関数である。そして、このハッシュ関数は、用いる暗号化関数が理想化されたブロック暗号における暗号化関数で、その出力長がnビットの場合、擬似ランダムオラクルの性質を満たすものの、安全性のセキュリティレベルがO(2n/2)である。
非特許文献6に記載されたハッシュ関数は、入出力が固定長でありランダムオラクルの性質を満たす関数を使う必要がある。
この発明は、例えば、ランダムオラクルの性質を満たす関数を用いることなく、出力長がnビット長のブロック暗号の暗号化関数を用いて、擬似ランダムオラクルの性質を満たし、かつ、安全性のセキュリティレベルが少なくともO(2n)となるハッシュ関数を構成することを目的とする。
【課題を解決するための手段】
【0008】
この発明に係るハッシュ値演算装置は、
任意ビット長の値Mを入力する任意長値入力部と、
前記任意長値入力部が入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算部と、
前記関数計算部が求めた値wを入力として、関数gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算部と、
前記鍵成分計算部が生成した値kを鍵成分とし、nビット長の所定の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算部と、
前記鍵成分計算部が生成した値kを鍵成分とし、nビット長の所定の値c2を平文成分として、ブロック暗号の暗号化関数E2を計算してnビット長の値yyを求める暗号化関数E2計算部と、
前記暗号化関数E1計算部が求めた値yと、前記暗号化関数E2計算部が求めた値yyとを入力として、関数hを計算してn’ビット長(n’は1以上2n以下の整数)の値zをハッシュ値として求めるハッシュ値計算部と
を備えることを特徴とする。
【発明の効果】
【0009】
この発明に係るハッシュ値演算装置によれば、用いるブロック暗号の暗号化関数が理想化されたブロック暗号における暗号化関数であれば、擬似ランダムオラクルの性質を満たし、かつ、安全性のセキュリティレベルがO(2n)(nは暗号化関数の出力長)となるハッシュ関数を構成することができる。
【図面の簡単な説明】
【0010】
【図1】実施の形態1に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図2】図1に示す実施の形態1に係るハッシュ値演算装置10の動作を示すフローチャート。
【図3】図1に示す実施の形態1に係るハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図4】実施の形態2に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図5】図4に示す実施の形態2に係るハッシュ値演算装置10の動作を示すフローチャート。
【図6】図4に示す実施の形態2に係るハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図7】実施の形態3に係る関数計算部12の機能を示す機能ブロック図。
【図8】図7に示す実施の形態3に係る関数計算部12の動作を示すフローチャート。
【図9】図7に示す実施の形態3に係る関数計算部12により実現される関数Fの構造図。
【図10】実施の形態4に係る関数計算部12の機能を示す機能ブロック図。
【図11】図10に示す実施の形態4に係る関数計算部12の動作を示すフローチャート。
【図12】図10に示す実施の形態4に係る関数計算部12により実現されるハッシュ関数の構造図。
【発明を実施するための形態】
【0011】
実施の形態1.
まず、ハッシュ関数の安全性の概念について説明する。
【0012】
ランダムオラクルの性質を満たすハッシュ関数は、理想的なハッシュ関数である。
ランダムオラクルの性質を満たすハッシュ関数Hとは、以下の1,2が与えられたハッシュ関数である。
1.(リスト):全ての入力値と、各入力値に対してランダムに選択した出力値とのペアを記録したリストを持つ。
2.(順方向の値を出力するオラクル):入力値xに対し、リストから入力値xに対する出力値zを検索して、値zを出力する。つまり、H(x)=zとなる値zを出力する。
【0013】
ランダムオラクルの性質を満たすハッシュ関数は、「(1)衝突困難性」、「(2)第二原像計算困難性」、「(3)原像計算困難性」の3つの性質を満たす。
(1)〜(3)の各性質の定義は以下の通りである。以下の定義において、「H」は、ハッシュ関数を示す。「M」「M’(≠M)」は、ハッシュ関数Hの入力値を示す。「H(x)」は、xを入力したハッシュ関数Hの出力(ハッシュ値)を示す。
【0014】
(1)衝突困難性を満たすハッシュ関数とは、「H(M)=H(M’)」となる2つの入力値M、M’を見つけることが困難なハッシュ関数である。つまり、衝突困難性とは、ハッシュ値が同じである複数の入力値を求めることが難しいという性質である。
(2)第二原像計算困難性を満たすハッシュ関数とは、ランダムな入力値Mが与えられたとき、「H(M)=H(M’)」を満たす入力値M’を見つけることが困難なハッシュ関数である。つまり、第二原像計算困難性とは、第1の入力値とハッシュ値が同じである第2の入力値を求めることが難しいという性質である。
(3)原像計算困難性を満たすハッシュ関数とは、ランダムな値zが与えられたとき、「z=H(M)」を満たすMを見つけることが困難なハッシュ関数である。つまり、原像計算困難性とは、ハッシュ値に対応する入力値を求めることが難しいという性質である。
【0015】
(1)〜(3)各性質には、(1)衝突困難性を満たすハッシュ関数は(2)第二原像計算困難性を満たし、(2)第二原像計算困難性を満たすハッシュ関数は(3)原像計算困難性を満たすという関係がある。
また、(3)原像計算困難性が破られたハッシュ関数(原像計算困難性を満たさないハッシュ関数)は、(1)衝突困難性、及び、(2)第二原像計算困難性を満たさないという関係がある。つまり、原像計算困難性が破られたハッシュ関数は、安全なハッシュ関数が満たすべき(1)〜(3)の性質を満たさない関数であり、安全性が低いため一般的に使い物にならない。
【0016】
標準的な公開鍵暗号、電子署名アルゴリズムであるRSA−OAEP(RSA−Optimal Asymmetric Encryption Padding)、RSA−KEM(RSA−Key Encapsulation Mechanism)、RSA−PSS(RSA−Probabilistic Signature Scheme)などは、用いられるハッシュ関数がランダムオラクルの性質を満たすと仮定したときに安全なものである。
しかし、ランダムオラクルの性質を満たすハッシュ関数を実現することは困難であることが知られている。そのため、これらの公開鍵暗号、電子署名アルゴリズムを実現する際は、ランダムオラクルの性質を満たすハッシュ関数に代え、SHA−256(Secure Hash Algorithm−256)などのハッシュ関数を用いて運用されている。
【0017】
ランダムオラクルの性質を満たさないハッシュ関数を用いて、上述した公開鍵暗号、電子署名アルゴリズムを実現した場合、その安全性が保証されるとは限らない。しかし、その安全性を保証するための概念として、擬似ランダムオラクルという概念が存在する。
ここで、ハッシュ関数で用いる内部関数をP、Pを用いて構成したハッシュ関数をH[P]とする。H[P]が擬似ランダムオラクルの性質を満たすとは、どんな識別者でも、H[P]とランダムオラクルの性質を満たすハッシュ関数とを識別できないようなPをシミュレートするシミュレータSが存在することである。
【0018】
H[P]が擬似ランダムオラクルの性質を満たすならば、H[P]は(1)衝突困難性、(2)第二原像計算困難性、(3)原像計算困難性の性質を満たす。そして、ランダムオラクルの性質を満たすハッシュ関数を用いた場合に安全な暗号アルゴリズムは、H[P]を用いた場合にも安全であることが保証される。
【0019】
PrAの性質を満たすハッシュ関数とは、ハッシュ関数で用いる内部関数をP、Pを用いて構成したハッシュ関数をH[P]とすると、H[P]は衝突困難性を満たし、かつ、選択原像計算困難性を満たすというハッシュ関数である。
ここで、H[P]が選択原像計算困難性を満たす場合とは、任意の攻撃者Aがハッシュ関数の出力値zを決め(但し、この時点では、Aはその入力値を知らない)、攻撃者Aはzの入力値を求めようとした場合に、求めることができない場合である。
【0020】
ブロック暗号(E,D)は、Eは暗号化関数、Dは復号関数である。暗号化関数Eは、dビットとnビットの2つの値を入力とし、nビットの値を出力する。dビットの値を値kと固定した場合、E(k,・)はnビットの置換関数となる。
kを固定し、順方向の置換計算するのが関数E(k,・)とすると、復号関数Dは逆方向の置換計算する関数E−1(k,・)である。
理想化されたブロック暗号とは、全てのブロック暗号の関数の集合からランダムに1つブロック暗号の関数を取ってきた場合におけるブロック暗号の関数のことである。
【0021】
理想化されたブロック暗号を実現することは困難であることが知られている。そのため、非特許文献4,5に記載されたハッシュ関数等、擬似ランダムオラクルの性質を満たすハッシュ関数を実現する際は、理想化されたブロック暗号の代わりに、例えば、(1)衝突困難性、(2)第二原像計算困難性、(3)原像計算困難性の3つの性質に相当する性質を満たす関数を用いることが考えられる。つまり、(1)出力値が同じである複数の入力値を求めることが難しいという性質、(2)第1の入力値と出力値が同じである第2の入力値を求めることが難しいという性質、(3)出力値に対応する入力値を求めることが難しいという性質という3つの性質を満たす関数を用いることが考えられる。
この場合、理想的なブロック暗号を用いていないため、得られたハッシュ関数は、擬似ランダムオラクルの性質を満たすハッシュ関数とはならない。しかし、ランダムオラクルの性質を満たす関数を用いた場合に安全であることが証明されているため、ある程度の安全性があるものと認められる。
【0022】
以下の説明では、非特許文献4,5に記載されたハッシュ関数と同様に、理想的なブロック暗号における暗号化関数を用いたハッシュ関数について説明する。以下で説明するハッシュ関数は、非特許文献4,5に記載されたハッシュ関数と同様に、用いるブロック暗号が理想的なブロック暗号における暗号化関数の場合、擬似ランダムオラクルの性質を満たす。
しかし、以下で説明するハッシュ関数では、非特許文献4,5に記載されたハッシュ関数と同等の安全性を満たすのに必要なブロック暗号の暗号化関数の出力長が半分以下でよい。つまり、非特許文献4,5に記載されたハッシュ関数に比べ、用いる暗号化関数の出力長が小さくて済む。そのため、例えば、以下で説明するハッシュ関数を回路で実現した場合、回路規模を小さくすることができる。
【0023】
次に、実施の形態1に係るハッシュ関数について説明する。
【0024】
図1は、実施の形態1に係るハッシュ値演算装置10の機能を示す機能ブロック図である。
図2は、図1に示す実施の形態1に係るハッシュ値演算装置10の動作を示すフローチャートである。
図3は、図1に示す実施の形態1に係るハッシュ値演算装置10により実現されるハッシュ関数の構造図である。なお、図3では、各値の下に括弧書でその値のビット長を示す。例えば、値Mは任意長であり、値wはtビット長である。
【0025】
図1に示すハッシュ値演算装置10の機能と動作について、図2、図3を用いて説明する。
図1に示すハッシュ値演算装置10は、任意長値入力部11、関数計算部12、鍵成分計算部13、暗号化関数E1計算部14、暗号化関数E2計算部15、ハッシュ値計算部16を備える。
【0026】
(S1:任意長値入力ステップ)
任意長値入力部11は、任意ビット長の値Mを入力装置により入力する。
【0027】
(S2:関数F計算ステップ)
関数計算部12は、(S1)で入力された値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを処理装置により求める。
【0028】
(S3:関数g計算ステップ)
鍵成分計算部13は、(S2)で求められた値wを入力として、関数gを計算してdビット長(dはt以上の整数)の値kを処理装置により求める。
【0029】
(S4:暗号化関数E1計算ステップ)
暗号化関数E1計算部14は、(S3)で求められた値kを鍵成分とし、nビット長(nは1以上の整数)の固定値c1を平文成分として、暗号化関数E1を計算してnビット長の値yを処理装置により求める。
【0030】
(S5:暗号化関数E2計算ステップ)
暗号化関数E2計算部15は、(S3)で求められた値kを鍵成分とし、nビット長の固定値c2を平文成分として、暗号化関数E2を計算してnビット長の値yyを処理装置により求める。
なお、(S4)と(S5)とは並列に実行してもよい。
【0031】
(S6:ハッシュ値計算ステップ)
ハッシュ値計算部16は、(S4)で求められた値yと、(S5)で求められた値yyとを入力として、関数hを計算してn’ビット長(ここでのn’は1以上2n以下の整数)の値zをハッシュ値として求める。
【0032】
つまり、実施の形態1に係るハッシュ値演算装置10は、関数F、関数g、暗号化関数E1、暗号化関数E2、関数hを用いてハッシュ関数を構成する。
【0033】
関数Fは、任意長の値Mを入力として、tビット長の値wを出力する関数である。
関数Fについては、後の実施の形態で詳しく説明する。
【0034】
関数gは、tビット長の値wを入力として、dビット長の値kを出力する関数である。
関数gは、例えば、(d−t)ビット長の固定値cを用いて、入力値wと値cとをビット結合する関数である。ビット結合の方法は、w||cでもよいし、c||wでもよいし、値cのビットと値wのビットとをそれぞれ決められたルールでシャッフルして任意の順に結合してもよい。なお、“||”という記号は、ビット列の結合を意味する。つまり、w||cであれば、値wの後に値cを付加するという意味であり、c||wであれば、値cの後に値wを付加するという意味である。
【0035】
暗号化関数E1は、dビット長の値kと、nビット長の値c1とを入力として、nビット長の値を出力するブロック暗号の暗号化関数である。同様に、暗号化関数E2は、dビット長の値kと、nビット長の値c2とを入力として、nビット長の値を出力するブロック暗号の暗号化関数である。
暗号化関数E1と暗号化関数E2とは同じ関数であってもよいし、異なる関数であってもよい。但し、暗号化関数E1と暗号化関数E2とが同じ関数である場合、値c1と値c2とを異なる値とする。
【0036】
関数hは、2つのnビット長の値y、値yyを入力として、n’ビット長の値を出力する関数である。
関数hは、例えば、2つの入力された値y、値yyをビット結合し、そのビットからn’ビット選んで出力する関数である。なお、値y、値yyをビット結合の方法は、関数gにおいて値wと値cとのビット結合の方法と同様に、値yと値yyとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0037】
実施の形態1に係るハッシュ値演算装置10が実現するハッシュ関数は、関数FがPrAの性質を満たし、かつ、暗号化関数E1,E2が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。
【0038】
なお、図3に示す暗号化関数E1,E2は、三角の印が付いた部分の入力(図3では値k)を固定とすると、置換関数となる。以下の実施の形態においても同様に、図において三角の印が付いた部分の入力を固定とした場合、その暗号化関数は置換関数となる。
【0039】
実施の形態2
実施の形態2では、実施の形態1とは異なるハッシュ関数について説明する。
【0040】
図4は、実施の形態2に係るハッシュ値演算装置10の機能を示す機能ブロック図である。
図5は、図4に示す実施の形態2に係るハッシュ値演算装置10の動作を示すフローチャートである。
図6は、図4に示す実施の形態2に係るハッシュ値演算装置10により実現されるハッシュ関数の構造図である。なお、図6では、図3と同様に、各値の下に括弧書でその値のビット長を示す。
【0041】
図4に示すハッシュ値演算装置10の機能と動作について、図5、図6を用いて説明する。
図4に示すハッシュ値演算装置10は、暗号化関数E2計算部15を備えていない点で、図1に示すハッシュ値演算装置10と異なる。
【0042】
(S11)から(S12)までは、図2に示す(S1)から(S2)までと同じであるため、説明を省略する。
【0043】
(S13:関数G計算ステップ)
鍵成分計算部13は、(S12)で求められた値wを入力として、関数Gを計算してdビット長の値kを処理装置により求める。
【0044】
(S14:暗号化関数E1計算ステップ)
暗号化関数E1計算部14は、(S13)で求められた値kを鍵成分とし、nビット長の固定値c1を平文成分として、暗号化関数E1を計算してnビット長の値yを処理装置により求める。
【0045】
(S15:ハッシュ値計算ステップ)
ハッシュ値計算部16は、(S14)で求められた値yとを入力として、関数Hを計算してn’ビット長(ここでのn’は1以上n以下の整数)の値zをハッシュ値として求める。
【0046】
つまり、実施の形態2に係るハッシュ値演算装置10は、関数F、関数G、暗号化関数E1、関数Hを用いてハッシュ関数を構成する。
【0047】
関数Fは、任意長の値Mを入力として、tビット長の値wを出力する関数である。
関数Fについては、後の実施の形態で詳しく説明する。
【0048】
関数Gは、tビット長の値wを入力として、dビット長の値kを出力する関数である。
関数Gは、例えば、(d−t)ビット長の固定値cを用いて、入力値wと値cとをビット結合する関数である。入力値wと値cとのビット結合の方法は、入力値wと値cとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0049】
暗号化関数E1は、dビット長の値kと、nビット長の値c1とを入力として、nビット長の値を出力するブロック暗号の暗号化関数である。
【0050】
関数Hは、nビット長の値yを入力として、n’ビット長の値を出力する関数である。
関数Hは、例えば、入力された値yからn’ビット選んで出力する関数である。
【0051】
実施の形態2に係るハッシュ値演算装置10が実現するハッシュ関数は、関数FがPrAの性質を満たし、かつ、暗号化関数E1が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。
【0052】
実施の形態3.
実施の形態3では、実施の形態1,2における関数Fの一例について説明する。
【0053】
図7は、実施の形態3に係る関数計算部12の機能を示す機能ブロック図である。
図8は、図7に示す実施の形態3に係る関数計算部12の動作を示すフローチャートである。
図9は、図7に示す実施の形態3に係る関数計算部12により実現される関数Fの構造図である。なお、図9では、図3と同様に、各値の下に括弧書でその値のビット長を示す。
【0054】
図7に示す関数計算部12の機能と動作について、図8、図9を用いて説明する。
関数計算部12は、パディング部21、分割部22、鍵成分k1計算部23、暗号化関数Ej,1計算部24、関数R計算部25、関数p計算部26、暗号化関数Ej,2計算部27、関数S計算部28、鍵成分kj計算部29、関数V計算部30、変数j制御部31を備える。
【0055】
(S21:パディングステップ)
パディング部21は、任意長の値Mに対して、パディング関数padを用いて、所定の値を付加して(L’+L(i−1))ビット長(L’は1以上d以下の整数、ここでのLは1以上d−n以下の整数、iは1以上の整数)の値M’を処理装置により生成する。
【0056】
(S22:分割ステップ)
分割部22は、(S21)で生成された値M’を先頭から、最初はL’ビット、以降Lビットづつに分割して、L’ビット長の値m[1]と、Lビット長の値m[2],...,値m[i]を処理装置により生成する。
【0057】
(S23:変数j初期化ステップ)
変数j制御部31は、変数jを1に初期化する。
【0058】
(S24:関数T1計算ステップ)
鍵成分k1計算部23は、(S22)で生成された値m[j](つまり、値m[1])を入力として、関数T[j](つまり、関数T[1])を計算してdビット長の値k[j](つまり、値k[1])を処理装置により求める。
【0059】
(S25:暗号化関数Ej,1計算ステップ)
暗号化関数Ej,1計算部24は、(S24)又は後述する(S32)で求めた値k[j]を鍵成分とし、nビット長の値y[j−1](値y[0]は固定値IV)を平文成分として、暗号化関数Ej,1を計算してnビット長の値x[j]を処理装置により求める。
【0060】
(S26:関数R計算ステップ)
関数R計算部25は、(S25)で求めた値x[j]と、nビット長の値y[j−1]とを入力として、関数R[j]を計算してnビット長の値y[j]を処理装置により求める。
【0061】
(S27:関数p計算ステップ)
関数p計算部26は、nビット長の値y[j−1]とを入力として、関数p[j]を計算してnビット長の値vv[j]を処理装置により求める。
【0062】
(S28:暗号化関数Ej,2計算ステップ)
暗号化関数Ej,2計算部27は、(S24)又は後述する(S32)で求めた値k[j]を鍵成分とし、(S27)で求めた値vv[j]を平文成分として、暗号化関数Ej,2を計算してnビット長の値xx[j]を処理装置により求める。
【0063】
(S29:関数S計算ステップ)
関数S計算部28は、(S28)で求めた値xx[j]と、(S27)で求めた値vv[j]とを入力として、関数S[j]を計算してnビット長の値yy[j]を求める。
なお、(S25)から(S26)までと、(S27)から(S29)までとは並列に実行してもよい。
【0064】
(S30:変数j判定ステップ)
変数j制御部31は、変数jの値が値iであるか否かを判定する。変数jの値が値iでなければ(S30でNO)、処理を(S31)へ進める。一方、変数jの値が値iであれば(S30でYES)、処理を(S33)へ進める。
【0065】
(S31:変数jインクリメントステップ)
変数j制御部31は、変数jに1を加算する。
【0066】
(S32:関数T計算ステップ)
鍵成分kj計算部29は、(S22)で生成された値m[j]と、(S29)で求めた値yy[j−1]とを入力として、関数T[j]を計算してdビット長の値k[j]を処理装置により求める。
そして、処理を(S25)及び(S27)へ戻す。
【0067】
(S33:関数V計算ステップ)
関数V計算部30は、(S26)で求めた値y[i]と、(S29)で求めた値yy[i]とを入力として、関数Vを計算してtビット長の値wを処理装置により求める。
【0068】
つまり、実施の形態3に係る関数計算部12は、パディング関数pad、関数T[1],...,関数T[i]、関数p[1],...,関数p[i]、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、関数R[1],...,関数R[i]、関数S[1],...,関数S[i]、関数Vを用いて、図3や図6に示す関数Fを構成する。
【0069】
パディング関数padは、例えば、M’=pad(M)=M||1||0...0||<M>である。ここで、<M>は、例えば、64ビットの値であり、Mのビット長情報を含む値である。
つまり、パディング関数padは、先頭が“1”で、その後が複数の“0”で、最後に<M>となるビット列を生成して、値Mに付加して、値M’を生成する関数である。
なお、M’がL’+L(i−1)ビットとなるように0の個数が決定される。
【0070】
関数T[1]は、L’ビット長の値を入力として、dビット長の値を出力する関数である。
関数T[1]は、例えば、const’をd−L’ビット長の固定値とした場合、L’ビット長の入力値mに対して、const’をビット結合したものを出力する関数である。なお、L’=dの場合には、入力値をそのまま出力するものとする。
値mと値const’とのビット結合の方法は、値mと値const’とをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0071】
関数T[2],...,関数T[i]は、Lビット長の値と、nビット長の値とを入力として、dビット長の値を出力する関数である。
関数T[2],...,関数T[i]は、値constを(d−L−n)ビットの固定値とした場合、Lビットの入力値mと、nビットの入力値xと、値constとをビット結合したものを出力する関数である。なお、L=d−nの場合は、値constは付加しない。
入力値mと入力値xと値constとビット結合の方法は、入力値mと入力値xと値constとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0072】
関数p[1],...,関数p[i]は、全てのnビットの値xに対してp[j](x)≠x(j=1,...,i)となる置換関数である。
【0073】
暗号化関数E1,1,...,暗号化関数Ei,1と、暗号化関数E1,2,...,暗号化関数Ei,2とは、dビット長の値と、nビット長の値とを入力として、nビット長の値を出力するブロック暗号の暗号化関数である。
暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1,E2は、全て同じ暗号化関数であってもよい。
また、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2は同じ暗号化関数であり、暗号化関数E1,E2は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2と異なる暗号化関数であってもよい。この場合、暗号化関数E1,E2は、同じ暗号化関数であってもよいし、異なる暗号化関数であってもよい。
【0074】
関数R[1],...,関数R[i]と、関数S[1],...,関数S[i]とは、2つのnビット長の値を入力として、nビット長の値を出力する関数である。
関数R[1],...,関数R[i]と、関数S[1],...,関数S[i]とは、例えば、2つのnビット長の入力値x,yに対して、値xと値yとの排他的論理和を出力する関数である。
また、関数R[1],...,関数R[i]と、関数S[1],...,関数S[i]とは、2つのnビット長の入力値x,yに対して、値xと値yとを加算した値を出力する関数であってもよい。この場合、加算方法は、例えば、値xと値yとの先頭からLビットづつをそれぞれ加算していき、最後に加算したものをビット結合すればよい。
【0075】
関数Vは、2つのnビット長の値を入力として、tビット長の値を出力する関数である。
関数Vは、例えば、2つのnビット長の入力値x,yに対して、値xと値yとをビット結合し、そのうちtビットを所定の方法で抽出して出力する関数である。なお、t=2nの場合は、ビット結合した値をそのまま出力すればよい。
値xと値yとのビット結合の方法は、値xと値yとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。また、ビットの抽出方法は、先頭から抽出してもよいし、後ろから抽出してもよく、それ以外の抽出方法でもよい。
【0076】
実施の形態1に係るハッシュ値演算装置10が、実施の形態3に係る関数計算部12が実現する関数Fを用いて実現したハッシュ関数は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1,E2が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。そして、その安全性のセキュリティレベルはO(2n)となる。また、このハッシュ関数は、各暗号化関数の出力長がnビットであり、ハッシュ値の出力長が最大2nビットである。
【0077】
実施の形態2に係るハッシュ値演算装置10が、実施の形態3に係る関数計算部12が実現する関数Fを用いて実現したハッシュ関数は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。そして、その安全性のセキュリティレベルはO(2n)となる。また、このハッシュ関数は、各暗号化関数の出力長がnビットであり、ハッシュ値の出力長が最大nビットである。
【0078】
なお、実施の形態1に係るハッシュ関数と、実施の形態2に係るハッシュ関数との出力長を同じ2nとする場合、実施の形態1に係るハッシュ関数は、上述した通り、安全性のセキュリティレベルはO(2n)であり、用いる各暗号化関数の出力長がnビットである。一方、実施の形態2に係るハッシュ関数は、安全性のセキュリティレベルはO(22n)であり、用いる各暗号化関数の出力長が2nビットである。
つまり、ハッシュ関数の出力長を同じにした場合、実施の形態1に係るハッシュ関数の方が、実施の形態2に係るハッシュ関数よりも、用いる暗号化関数の出力長が短くてよい。そのため、例えば、ハッシュ関数を回路で実現した場合、回路規模を小さくできる。一方、実施の形態2に係るハッシュ関数の方が、実施の形態1に係るハッシュ関数よりも、安全性のセキュリティレベルが高い。
【0079】
実施の形態4.
実施の形態4では、実施の形態1,2における関数Fの実施の形態3とは異なる例について説明する。
【0080】
図10は、実施の形態4に係る関数計算部12の機能を示す機能ブロック図である。
図11は、図10に示す実施の形態4に係る関数計算部12の動作を示すフローチャートである。
図12は、図10に示す実施の形態4に係る関数計算部12により実現されるハッシュ関数の構造図である。なお、図12では、図3と同様に、各値の下に括弧書でその値のビット長を示す。
【0081】
図10に示すハッシュ値演算装置10の機能と動作について、図11、図12を用いて説明する。
図10に示す関数計算部12は、関数h計算部32、関数h’計算部33を備え、関数p計算部26、関数R計算部25、関数S計算部28を備えていない点が図7に示す関数計算部12と異なる。
【0082】
(S41)から(S43)までの処理は、図8に示す(S21)から(S23)までの処理と同じであるため、説明を省略する。但し、ここでのLは1以上d−2n以下の整数である。
【0083】
(S44:関数g1計算ステップ)
鍵成分k1計算部23は、(S42)で生成された値m[j](値m[1])を入力として、関数g[j](関数g[1])を計算してdビット長の値k[j](値k[1])を処理装置により求める。
【0084】
(S45:暗号化関数Ej,1計算ステップ)
暗号化関数Ej,1計算部24は、(S44)又は後述する(S50)で求めた値k[j]を鍵成分とし、nビット長の所定の値cj,1を平文成分として、暗号化関数Ej,1を計算してnビット長の値y[j]を処理装置により求める。
【0085】
(S46:暗号化関数Ej,2計算ステップ)
暗号化関数Ej,2計算部27は、(S44)又は後述する(S50)で求めた値k[j]を鍵成分とし、nビット長の所定の値cj,2を平文成分として、暗号化関数Ej,2を計算してnビット長の値yy[j]を処理装置により求める。
なお、(S45)と(S46)とは並列に実行してもよい。
【0086】
(S47:関数h計算ステップ)
関数h計算部32は、(S45)で求めた値y[j]と、(S46)で求めた値yy[j]とを入力として、関数h[j]を計算して2nビット長の値w[j]を処理装置により求める。
【0087】
(S48:変数j判定ステップ)
関数計算部12は、変数jの値が値iであるか否かを判定する。変数jの値が値iでなければ(S48でNO)、処理を(S49)へ進める。一方、変数jの値が値iであれば(S48でYES)、処理を(S51)へ進める。
【0088】
(S49:変数jインクリメントステップ)
関数計算部12は、変数jに1を加算する。
【0089】
(S50:関数g計算ステップ)
鍵成分kj計算部29は、(S42)で生成された値m[j]と、(S47)で求めた値w[j−1]とを入力として、関数g[j]を計算してdビット長の値k[j]を処理装置により求める。
そして、処理を(S45)及び(S46)へ戻す。
【0090】
(S51:関数h’計算ステップ)
関数h’計算部33は、(S47)で求めた値w[i]を入力として、関数h’を計算してtビット長の値wを処理装置により求める。
【0091】
つまり、実施の形態4に係る関数計算部12は、パディング関数pad、関数g[1],...,関数g[i]、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、関数h[1],...,関数h[i]、関数h’を用いて、図3や図6に示す関数Fを構成する。
【0092】
パディング関数padは、実施の形態3のパディング関数padと同じである。
【0093】
関数g[1]は、L’ビット長の値を入力として、dビット長の値を出力する関数である。
関数g[1]は、例えば、const’をd−L’ビット長の固定値とした場合、L’ビット長の入力値mに対して、const’をビット結合したものを出力する関数である。なお、L’=dの場合には、入力値をそのまま出力するものとする。
値mと値const’とのビット結合の方法は、値mと値const’とをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0094】
関数g[2],...,関数g[i]は、Lビット長の値と、nビット長の値とを入力として、dビット長の値を出力する関数である。
値constを(d−L−2n)ビットの固定値とした場合、Lビットの入力値mと、nビットの入力値xと、値constとをビット結合したものを出力する関数である。なお、L=d−2nの場合は、値constは付加しない。
入力値mと入力値xと値constとビット結合の方法は、入力値mと入力値xと値constとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0095】
暗号化関数E1,1,...,暗号化関数Ei,1と、暗号化関数E1,2,...,暗号化関数Ei,2とは、dビット長の値と、nビット長の値とを入力として、nビット長の値を出力するブロック暗号の暗号化関数である。
暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1,E2は、全て同じ暗号化関数であってもよい。
また、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2は同じ暗号化関数であり、暗号化関数E1,E2は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2と異なる暗号化関数であってもよい。この場合、暗号化関数E1,E2は、同じ暗号化関数であってもよいし、異なる暗号化関数であってもよい。
【0096】
関数h[1],...,関数h[i]は、2つのnビット長の値を入力として、2nビット長の値を出力する関数である。
関数h[1],...,関数h[i]は、2つのnビット長の値をビット結合する関数である。2つのnビットの値のビット結合の方法は、2つのnビットの値をそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0097】
関数h’は、2つのnビット長の値を入力として、tビット長の値を出力する関数である。
関数h’は、例えば、2つのnビット長の入力値x,yに対して、値xと値yとをビット結合し、そのうちtビットを所定の方法で抽出して出力する関数である。
値xと値yとのビット結合の方法は、値xと値yとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。また、ビットの抽出方法は、先頭から抽出してもよいし、後ろから抽出してもよく、それ以外の抽出方法でもよい。
【0098】
実施の形態1に係るハッシュ値演算装置10が、実施の形態4に係る関数計算部12が実現する関数Fを用いて実現したハッシュ関数は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1,E2が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。そして、その安全性のセキュリティレベルはO(2n)となる。また、このハッシュ関数は、各暗号化関数の出力長がnビットであり、ハッシュ値の出力長が最大2nビットである。
【0099】
実施の形態2に係るハッシュ値演算装置10が、実施の形態4に係る関数計算部12が実現する関数Fを用いて実現したハッシュ関数は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。そして、その安全性のセキュリティレベルはO(2n)となる。また、このハッシュ関数は、各暗号化関数の出力長がnビットであり、ハッシュ値の出力長が最大nビットである。
【0100】
なお、実施の形態1に係るハッシュ関数と、実施の形態2に係るハッシュ関数との出力長を同じ2nとする場合、実施の形態1に係るハッシュ関数は、上述した通り、安全性のセキュリティレベルはO(2n)であり、用いる各暗号化関数の出力長がnビットである。一方、実施の形態2に係るハッシュ関数は、安全性のセキュリティレベルはO(22n)であり、用いる各暗号化関数の出力長が2nビットである。
つまり、ハッシュ関数の出力長を同じにした場合、実施の形態1に係るハッシュ関数の方が、実施の形態2に係るハッシュ関数よりも、用いる暗号化関数の出力長が短くてよい。そのため、例えば、ハッシュ関数を回路で実現した場合、回路規模を小さくできる。一方、実施の形態2に係るハッシュ関数の方が、実施の形態1に係るハッシュ関数よりも、安全性のセキュリティレベルが高い。
【0101】
以上に説明したハッシュ値演算装置10は、例えば、回路やソフトウェア等で構成される。回路で構成される場合には、上記説明における処理装置は、例えば演算回路であり、記憶装置は、例えばレジスタである。また、ソフトウェアで構成される場合には、上記説明における処理装置は、例えばCPU(Central Processing Unit)であり、記憶装置は、例えばRAM(Random Access Memory)である。また、上記説明における入力装置は、例えばキーボード、通信ボードであり、出力装置は、例えばLCD(Liquid Crystal Display)等の表示装置、通信ボード、レジスタやRAM等の記憶装置である。もちろん、これらに限定されるものではない。
なお、ハッシュ値演算装置10を回路で構成する場合、上述した「〜部」を「〜回路」と読み変えてもよい。また、上述した「〜部」は、「〜処理」、「〜装置」、「〜機器」、「〜手段」、「〜手順」、「〜機能」と読み替えてもよい。つまり、「〜部」として説明するものは、ROM(Read Only Memory)に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実現されても構わない。
【符号の説明】
【0102】
10 ハッシュ値演算装置、11 任意長値入力部、12 関数計算部、13 鍵成分計算部、14 暗号化関数E1計算部、15 暗号化関数E2計算部、16 ハッシュ値計算部、21 パディング部、22 分割部、23 鍵成分k1計算部、24 暗号化関数Ej,1計算部、25 関数R計算部、26 関数p計算部、27 暗号化関数Ej,2計算部、28 関数S計算部、29 鍵成分kj計算部、30 関数V計算部、31 変数j制御部、32 関数h計算部、33 関数h’計算部。
【技術分野】
【0001】
この発明は、例えば、安全性の高いハッシュ値を計算する技術に関する。
【背景技術】
【0002】
ハッシュ関数は、任意長の値を入力として、固定長の値を出力する関数である。
【0003】
非特許文献1〜3には、出力長がnビットのブロック暗号の暗号化関数を用いて、衝突困難性の性質を満たす出力長が2nビットのハッシュ関数の構成法についての記載がある。
ここで、非特許文献1〜3におけるハッシュ関数が衝突困難性の性質を満たすためには、用いる暗号化関数が理想化されたブロック暗号における暗号化関数である必要がある。
【0004】
非特許文献4,5には、出力長がsビットのブロック暗号の暗号化関数を用いて、擬似ランダムオラクルの性質を満たす出力長がnビットのハッシュ関数の構成法についての記載がある。但し、sはn以上の整数である。
ここで、非特許文献4,5におけるハッシュ関数が擬似ランダムオラクルの性質を満たすためには、用いる暗号化関数が理想化されたブロック暗号における暗号化関数である必要がある。また、非特許文献4,5におけるハッシュ関数の安全性のセキュリティレベルはO(2s/2)以下である。なお、安全性のセキュリティレベルとは、擬似ランダムオラクルの性質を破るために必要となる計算量である。
【0005】
非特許文献6には、入出力が固定長でありランダムオラクルの性質を満たす関数と、PrA(Preimage Aware)の性質を満たす任意長入力、固定長出力の関数とを用いて、擬似ランダムオラクルの性質を満たすハッシュ関数を構成することについての記載がある。非特許文献6では、PrAの性質をもつ関数として、出力長がnビットのブロック暗号の暗号化関数を用いている。
ここで、非特許文献6におけるハッシュ関数が、擬似ランダムオラクルの性質を満たすためには、用いる暗号化関数が理想化されたブロック暗号における暗号化関数である必要がある。
【先行技術文献】
【非特許文献】
【0006】
【非特許文献1】O. Ozen and M. Stam. Another Glance at Double−length Hashing. IMA Int. Conf. 2009. pp176−201. LNCS 5921.
【非特許文献2】S. Hirose. Some Plausible Constructions of Double−Block−length Hash Functions. FSE 2006. 210−225. LNCS 4047.
【非特許文献3】X. Lai and J. Massey: Hash Function Based on Block Ciphers. EUROCRYPT 1992. pp55−70. LNCS 653.
【非特許文献4】Shoichi Hirose, Je. Park, and A. Yun. A Simple Variant of the Merkle−Damgard Scheme with a Permutation. ASIACRYPT 2007. pp113−129. LNCS 4833.
【非特許文献5】J.−S. Coron, Y. Dodis, C. Malinaud, and P. Puniya. Merkle−Damgard Revisited: How to Construct a Hash Function. CRYPTO 2005. pp430−448. LNCS 3621.
【非特許文献6】Y. Dodis, T. Ristenpart, and T. Shrimpton. Salvaging Merkle−Damgard for Practical Applications. EUROCRYPT 2009. pp371−388. LNCS 5479.
【発明の概要】
【発明が解決しようとする課題】
【0007】
非特許文献1〜3に記載されたハッシュ関数は、ブロック暗号の暗号化関数を用いたハッシュ関数であるが、擬似ランダムオラクルの性質を満たさない。
非特許文献4,5に記載されたハッシュ関数は、ブロック暗号の暗号化関数を用いたハッシュ関数である。そして、このハッシュ関数は、用いる暗号化関数が理想化されたブロック暗号における暗号化関数で、その出力長がnビットの場合、擬似ランダムオラクルの性質を満たすものの、安全性のセキュリティレベルがO(2n/2)である。
非特許文献6に記載されたハッシュ関数は、入出力が固定長でありランダムオラクルの性質を満たす関数を使う必要がある。
この発明は、例えば、ランダムオラクルの性質を満たす関数を用いることなく、出力長がnビット長のブロック暗号の暗号化関数を用いて、擬似ランダムオラクルの性質を満たし、かつ、安全性のセキュリティレベルが少なくともO(2n)となるハッシュ関数を構成することを目的とする。
【課題を解決するための手段】
【0008】
この発明に係るハッシュ値演算装置は、
任意ビット長の値Mを入力する任意長値入力部と、
前記任意長値入力部が入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算部と、
前記関数計算部が求めた値wを入力として、関数gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算部と、
前記鍵成分計算部が生成した値kを鍵成分とし、nビット長の所定の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算部と、
前記鍵成分計算部が生成した値kを鍵成分とし、nビット長の所定の値c2を平文成分として、ブロック暗号の暗号化関数E2を計算してnビット長の値yyを求める暗号化関数E2計算部と、
前記暗号化関数E1計算部が求めた値yと、前記暗号化関数E2計算部が求めた値yyとを入力として、関数hを計算してn’ビット長(n’は1以上2n以下の整数)の値zをハッシュ値として求めるハッシュ値計算部と
を備えることを特徴とする。
【発明の効果】
【0009】
この発明に係るハッシュ値演算装置によれば、用いるブロック暗号の暗号化関数が理想化されたブロック暗号における暗号化関数であれば、擬似ランダムオラクルの性質を満たし、かつ、安全性のセキュリティレベルがO(2n)(nは暗号化関数の出力長)となるハッシュ関数を構成することができる。
【図面の簡単な説明】
【0010】
【図1】実施の形態1に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図2】図1に示す実施の形態1に係るハッシュ値演算装置10の動作を示すフローチャート。
【図3】図1に示す実施の形態1に係るハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図4】実施の形態2に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図5】図4に示す実施の形態2に係るハッシュ値演算装置10の動作を示すフローチャート。
【図6】図4に示す実施の形態2に係るハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図7】実施の形態3に係る関数計算部12の機能を示す機能ブロック図。
【図8】図7に示す実施の形態3に係る関数計算部12の動作を示すフローチャート。
【図9】図7に示す実施の形態3に係る関数計算部12により実現される関数Fの構造図。
【図10】実施の形態4に係る関数計算部12の機能を示す機能ブロック図。
【図11】図10に示す実施の形態4に係る関数計算部12の動作を示すフローチャート。
【図12】図10に示す実施の形態4に係る関数計算部12により実現されるハッシュ関数の構造図。
【発明を実施するための形態】
【0011】
実施の形態1.
まず、ハッシュ関数の安全性の概念について説明する。
【0012】
ランダムオラクルの性質を満たすハッシュ関数は、理想的なハッシュ関数である。
ランダムオラクルの性質を満たすハッシュ関数Hとは、以下の1,2が与えられたハッシュ関数である。
1.(リスト):全ての入力値と、各入力値に対してランダムに選択した出力値とのペアを記録したリストを持つ。
2.(順方向の値を出力するオラクル):入力値xに対し、リストから入力値xに対する出力値zを検索して、値zを出力する。つまり、H(x)=zとなる値zを出力する。
【0013】
ランダムオラクルの性質を満たすハッシュ関数は、「(1)衝突困難性」、「(2)第二原像計算困難性」、「(3)原像計算困難性」の3つの性質を満たす。
(1)〜(3)の各性質の定義は以下の通りである。以下の定義において、「H」は、ハッシュ関数を示す。「M」「M’(≠M)」は、ハッシュ関数Hの入力値を示す。「H(x)」は、xを入力したハッシュ関数Hの出力(ハッシュ値)を示す。
【0014】
(1)衝突困難性を満たすハッシュ関数とは、「H(M)=H(M’)」となる2つの入力値M、M’を見つけることが困難なハッシュ関数である。つまり、衝突困難性とは、ハッシュ値が同じである複数の入力値を求めることが難しいという性質である。
(2)第二原像計算困難性を満たすハッシュ関数とは、ランダムな入力値Mが与えられたとき、「H(M)=H(M’)」を満たす入力値M’を見つけることが困難なハッシュ関数である。つまり、第二原像計算困難性とは、第1の入力値とハッシュ値が同じである第2の入力値を求めることが難しいという性質である。
(3)原像計算困難性を満たすハッシュ関数とは、ランダムな値zが与えられたとき、「z=H(M)」を満たすMを見つけることが困難なハッシュ関数である。つまり、原像計算困難性とは、ハッシュ値に対応する入力値を求めることが難しいという性質である。
【0015】
(1)〜(3)各性質には、(1)衝突困難性を満たすハッシュ関数は(2)第二原像計算困難性を満たし、(2)第二原像計算困難性を満たすハッシュ関数は(3)原像計算困難性を満たすという関係がある。
また、(3)原像計算困難性が破られたハッシュ関数(原像計算困難性を満たさないハッシュ関数)は、(1)衝突困難性、及び、(2)第二原像計算困難性を満たさないという関係がある。つまり、原像計算困難性が破られたハッシュ関数は、安全なハッシュ関数が満たすべき(1)〜(3)の性質を満たさない関数であり、安全性が低いため一般的に使い物にならない。
【0016】
標準的な公開鍵暗号、電子署名アルゴリズムであるRSA−OAEP(RSA−Optimal Asymmetric Encryption Padding)、RSA−KEM(RSA−Key Encapsulation Mechanism)、RSA−PSS(RSA−Probabilistic Signature Scheme)などは、用いられるハッシュ関数がランダムオラクルの性質を満たすと仮定したときに安全なものである。
しかし、ランダムオラクルの性質を満たすハッシュ関数を実現することは困難であることが知られている。そのため、これらの公開鍵暗号、電子署名アルゴリズムを実現する際は、ランダムオラクルの性質を満たすハッシュ関数に代え、SHA−256(Secure Hash Algorithm−256)などのハッシュ関数を用いて運用されている。
【0017】
ランダムオラクルの性質を満たさないハッシュ関数を用いて、上述した公開鍵暗号、電子署名アルゴリズムを実現した場合、その安全性が保証されるとは限らない。しかし、その安全性を保証するための概念として、擬似ランダムオラクルという概念が存在する。
ここで、ハッシュ関数で用いる内部関数をP、Pを用いて構成したハッシュ関数をH[P]とする。H[P]が擬似ランダムオラクルの性質を満たすとは、どんな識別者でも、H[P]とランダムオラクルの性質を満たすハッシュ関数とを識別できないようなPをシミュレートするシミュレータSが存在することである。
【0018】
H[P]が擬似ランダムオラクルの性質を満たすならば、H[P]は(1)衝突困難性、(2)第二原像計算困難性、(3)原像計算困難性の性質を満たす。そして、ランダムオラクルの性質を満たすハッシュ関数を用いた場合に安全な暗号アルゴリズムは、H[P]を用いた場合にも安全であることが保証される。
【0019】
PrAの性質を満たすハッシュ関数とは、ハッシュ関数で用いる内部関数をP、Pを用いて構成したハッシュ関数をH[P]とすると、H[P]は衝突困難性を満たし、かつ、選択原像計算困難性を満たすというハッシュ関数である。
ここで、H[P]が選択原像計算困難性を満たす場合とは、任意の攻撃者Aがハッシュ関数の出力値zを決め(但し、この時点では、Aはその入力値を知らない)、攻撃者Aはzの入力値を求めようとした場合に、求めることができない場合である。
【0020】
ブロック暗号(E,D)は、Eは暗号化関数、Dは復号関数である。暗号化関数Eは、dビットとnビットの2つの値を入力とし、nビットの値を出力する。dビットの値を値kと固定した場合、E(k,・)はnビットの置換関数となる。
kを固定し、順方向の置換計算するのが関数E(k,・)とすると、復号関数Dは逆方向の置換計算する関数E−1(k,・)である。
理想化されたブロック暗号とは、全てのブロック暗号の関数の集合からランダムに1つブロック暗号の関数を取ってきた場合におけるブロック暗号の関数のことである。
【0021】
理想化されたブロック暗号を実現することは困難であることが知られている。そのため、非特許文献4,5に記載されたハッシュ関数等、擬似ランダムオラクルの性質を満たすハッシュ関数を実現する際は、理想化されたブロック暗号の代わりに、例えば、(1)衝突困難性、(2)第二原像計算困難性、(3)原像計算困難性の3つの性質に相当する性質を満たす関数を用いることが考えられる。つまり、(1)出力値が同じである複数の入力値を求めることが難しいという性質、(2)第1の入力値と出力値が同じである第2の入力値を求めることが難しいという性質、(3)出力値に対応する入力値を求めることが難しいという性質という3つの性質を満たす関数を用いることが考えられる。
この場合、理想的なブロック暗号を用いていないため、得られたハッシュ関数は、擬似ランダムオラクルの性質を満たすハッシュ関数とはならない。しかし、ランダムオラクルの性質を満たす関数を用いた場合に安全であることが証明されているため、ある程度の安全性があるものと認められる。
【0022】
以下の説明では、非特許文献4,5に記載されたハッシュ関数と同様に、理想的なブロック暗号における暗号化関数を用いたハッシュ関数について説明する。以下で説明するハッシュ関数は、非特許文献4,5に記載されたハッシュ関数と同様に、用いるブロック暗号が理想的なブロック暗号における暗号化関数の場合、擬似ランダムオラクルの性質を満たす。
しかし、以下で説明するハッシュ関数では、非特許文献4,5に記載されたハッシュ関数と同等の安全性を満たすのに必要なブロック暗号の暗号化関数の出力長が半分以下でよい。つまり、非特許文献4,5に記載されたハッシュ関数に比べ、用いる暗号化関数の出力長が小さくて済む。そのため、例えば、以下で説明するハッシュ関数を回路で実現した場合、回路規模を小さくすることができる。
【0023】
次に、実施の形態1に係るハッシュ関数について説明する。
【0024】
図1は、実施の形態1に係るハッシュ値演算装置10の機能を示す機能ブロック図である。
図2は、図1に示す実施の形態1に係るハッシュ値演算装置10の動作を示すフローチャートである。
図3は、図1に示す実施の形態1に係るハッシュ値演算装置10により実現されるハッシュ関数の構造図である。なお、図3では、各値の下に括弧書でその値のビット長を示す。例えば、値Mは任意長であり、値wはtビット長である。
【0025】
図1に示すハッシュ値演算装置10の機能と動作について、図2、図3を用いて説明する。
図1に示すハッシュ値演算装置10は、任意長値入力部11、関数計算部12、鍵成分計算部13、暗号化関数E1計算部14、暗号化関数E2計算部15、ハッシュ値計算部16を備える。
【0026】
(S1:任意長値入力ステップ)
任意長値入力部11は、任意ビット長の値Mを入力装置により入力する。
【0027】
(S2:関数F計算ステップ)
関数計算部12は、(S1)で入力された値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを処理装置により求める。
【0028】
(S3:関数g計算ステップ)
鍵成分計算部13は、(S2)で求められた値wを入力として、関数gを計算してdビット長(dはt以上の整数)の値kを処理装置により求める。
【0029】
(S4:暗号化関数E1計算ステップ)
暗号化関数E1計算部14は、(S3)で求められた値kを鍵成分とし、nビット長(nは1以上の整数)の固定値c1を平文成分として、暗号化関数E1を計算してnビット長の値yを処理装置により求める。
【0030】
(S5:暗号化関数E2計算ステップ)
暗号化関数E2計算部15は、(S3)で求められた値kを鍵成分とし、nビット長の固定値c2を平文成分として、暗号化関数E2を計算してnビット長の値yyを処理装置により求める。
なお、(S4)と(S5)とは並列に実行してもよい。
【0031】
(S6:ハッシュ値計算ステップ)
ハッシュ値計算部16は、(S4)で求められた値yと、(S5)で求められた値yyとを入力として、関数hを計算してn’ビット長(ここでのn’は1以上2n以下の整数)の値zをハッシュ値として求める。
【0032】
つまり、実施の形態1に係るハッシュ値演算装置10は、関数F、関数g、暗号化関数E1、暗号化関数E2、関数hを用いてハッシュ関数を構成する。
【0033】
関数Fは、任意長の値Mを入力として、tビット長の値wを出力する関数である。
関数Fについては、後の実施の形態で詳しく説明する。
【0034】
関数gは、tビット長の値wを入力として、dビット長の値kを出力する関数である。
関数gは、例えば、(d−t)ビット長の固定値cを用いて、入力値wと値cとをビット結合する関数である。ビット結合の方法は、w||cでもよいし、c||wでもよいし、値cのビットと値wのビットとをそれぞれ決められたルールでシャッフルして任意の順に結合してもよい。なお、“||”という記号は、ビット列の結合を意味する。つまり、w||cであれば、値wの後に値cを付加するという意味であり、c||wであれば、値cの後に値wを付加するという意味である。
【0035】
暗号化関数E1は、dビット長の値kと、nビット長の値c1とを入力として、nビット長の値を出力するブロック暗号の暗号化関数である。同様に、暗号化関数E2は、dビット長の値kと、nビット長の値c2とを入力として、nビット長の値を出力するブロック暗号の暗号化関数である。
暗号化関数E1と暗号化関数E2とは同じ関数であってもよいし、異なる関数であってもよい。但し、暗号化関数E1と暗号化関数E2とが同じ関数である場合、値c1と値c2とを異なる値とする。
【0036】
関数hは、2つのnビット長の値y、値yyを入力として、n’ビット長の値を出力する関数である。
関数hは、例えば、2つの入力された値y、値yyをビット結合し、そのビットからn’ビット選んで出力する関数である。なお、値y、値yyをビット結合の方法は、関数gにおいて値wと値cとのビット結合の方法と同様に、値yと値yyとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0037】
実施の形態1に係るハッシュ値演算装置10が実現するハッシュ関数は、関数FがPrAの性質を満たし、かつ、暗号化関数E1,E2が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。
【0038】
なお、図3に示す暗号化関数E1,E2は、三角の印が付いた部分の入力(図3では値k)を固定とすると、置換関数となる。以下の実施の形態においても同様に、図において三角の印が付いた部分の入力を固定とした場合、その暗号化関数は置換関数となる。
【0039】
実施の形態2
実施の形態2では、実施の形態1とは異なるハッシュ関数について説明する。
【0040】
図4は、実施の形態2に係るハッシュ値演算装置10の機能を示す機能ブロック図である。
図5は、図4に示す実施の形態2に係るハッシュ値演算装置10の動作を示すフローチャートである。
図6は、図4に示す実施の形態2に係るハッシュ値演算装置10により実現されるハッシュ関数の構造図である。なお、図6では、図3と同様に、各値の下に括弧書でその値のビット長を示す。
【0041】
図4に示すハッシュ値演算装置10の機能と動作について、図5、図6を用いて説明する。
図4に示すハッシュ値演算装置10は、暗号化関数E2計算部15を備えていない点で、図1に示すハッシュ値演算装置10と異なる。
【0042】
(S11)から(S12)までは、図2に示す(S1)から(S2)までと同じであるため、説明を省略する。
【0043】
(S13:関数G計算ステップ)
鍵成分計算部13は、(S12)で求められた値wを入力として、関数Gを計算してdビット長の値kを処理装置により求める。
【0044】
(S14:暗号化関数E1計算ステップ)
暗号化関数E1計算部14は、(S13)で求められた値kを鍵成分とし、nビット長の固定値c1を平文成分として、暗号化関数E1を計算してnビット長の値yを処理装置により求める。
【0045】
(S15:ハッシュ値計算ステップ)
ハッシュ値計算部16は、(S14)で求められた値yとを入力として、関数Hを計算してn’ビット長(ここでのn’は1以上n以下の整数)の値zをハッシュ値として求める。
【0046】
つまり、実施の形態2に係るハッシュ値演算装置10は、関数F、関数G、暗号化関数E1、関数Hを用いてハッシュ関数を構成する。
【0047】
関数Fは、任意長の値Mを入力として、tビット長の値wを出力する関数である。
関数Fについては、後の実施の形態で詳しく説明する。
【0048】
関数Gは、tビット長の値wを入力として、dビット長の値kを出力する関数である。
関数Gは、例えば、(d−t)ビット長の固定値cを用いて、入力値wと値cとをビット結合する関数である。入力値wと値cとのビット結合の方法は、入力値wと値cとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0049】
暗号化関数E1は、dビット長の値kと、nビット長の値c1とを入力として、nビット長の値を出力するブロック暗号の暗号化関数である。
【0050】
関数Hは、nビット長の値yを入力として、n’ビット長の値を出力する関数である。
関数Hは、例えば、入力された値yからn’ビット選んで出力する関数である。
【0051】
実施の形態2に係るハッシュ値演算装置10が実現するハッシュ関数は、関数FがPrAの性質を満たし、かつ、暗号化関数E1が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。
【0052】
実施の形態3.
実施の形態3では、実施の形態1,2における関数Fの一例について説明する。
【0053】
図7は、実施の形態3に係る関数計算部12の機能を示す機能ブロック図である。
図8は、図7に示す実施の形態3に係る関数計算部12の動作を示すフローチャートである。
図9は、図7に示す実施の形態3に係る関数計算部12により実現される関数Fの構造図である。なお、図9では、図3と同様に、各値の下に括弧書でその値のビット長を示す。
【0054】
図7に示す関数計算部12の機能と動作について、図8、図9を用いて説明する。
関数計算部12は、パディング部21、分割部22、鍵成分k1計算部23、暗号化関数Ej,1計算部24、関数R計算部25、関数p計算部26、暗号化関数Ej,2計算部27、関数S計算部28、鍵成分kj計算部29、関数V計算部30、変数j制御部31を備える。
【0055】
(S21:パディングステップ)
パディング部21は、任意長の値Mに対して、パディング関数padを用いて、所定の値を付加して(L’+L(i−1))ビット長(L’は1以上d以下の整数、ここでのLは1以上d−n以下の整数、iは1以上の整数)の値M’を処理装置により生成する。
【0056】
(S22:分割ステップ)
分割部22は、(S21)で生成された値M’を先頭から、最初はL’ビット、以降Lビットづつに分割して、L’ビット長の値m[1]と、Lビット長の値m[2],...,値m[i]を処理装置により生成する。
【0057】
(S23:変数j初期化ステップ)
変数j制御部31は、変数jを1に初期化する。
【0058】
(S24:関数T1計算ステップ)
鍵成分k1計算部23は、(S22)で生成された値m[j](つまり、値m[1])を入力として、関数T[j](つまり、関数T[1])を計算してdビット長の値k[j](つまり、値k[1])を処理装置により求める。
【0059】
(S25:暗号化関数Ej,1計算ステップ)
暗号化関数Ej,1計算部24は、(S24)又は後述する(S32)で求めた値k[j]を鍵成分とし、nビット長の値y[j−1](値y[0]は固定値IV)を平文成分として、暗号化関数Ej,1を計算してnビット長の値x[j]を処理装置により求める。
【0060】
(S26:関数R計算ステップ)
関数R計算部25は、(S25)で求めた値x[j]と、nビット長の値y[j−1]とを入力として、関数R[j]を計算してnビット長の値y[j]を処理装置により求める。
【0061】
(S27:関数p計算ステップ)
関数p計算部26は、nビット長の値y[j−1]とを入力として、関数p[j]を計算してnビット長の値vv[j]を処理装置により求める。
【0062】
(S28:暗号化関数Ej,2計算ステップ)
暗号化関数Ej,2計算部27は、(S24)又は後述する(S32)で求めた値k[j]を鍵成分とし、(S27)で求めた値vv[j]を平文成分として、暗号化関数Ej,2を計算してnビット長の値xx[j]を処理装置により求める。
【0063】
(S29:関数S計算ステップ)
関数S計算部28は、(S28)で求めた値xx[j]と、(S27)で求めた値vv[j]とを入力として、関数S[j]を計算してnビット長の値yy[j]を求める。
なお、(S25)から(S26)までと、(S27)から(S29)までとは並列に実行してもよい。
【0064】
(S30:変数j判定ステップ)
変数j制御部31は、変数jの値が値iであるか否かを判定する。変数jの値が値iでなければ(S30でNO)、処理を(S31)へ進める。一方、変数jの値が値iであれば(S30でYES)、処理を(S33)へ進める。
【0065】
(S31:変数jインクリメントステップ)
変数j制御部31は、変数jに1を加算する。
【0066】
(S32:関数T計算ステップ)
鍵成分kj計算部29は、(S22)で生成された値m[j]と、(S29)で求めた値yy[j−1]とを入力として、関数T[j]を計算してdビット長の値k[j]を処理装置により求める。
そして、処理を(S25)及び(S27)へ戻す。
【0067】
(S33:関数V計算ステップ)
関数V計算部30は、(S26)で求めた値y[i]と、(S29)で求めた値yy[i]とを入力として、関数Vを計算してtビット長の値wを処理装置により求める。
【0068】
つまり、実施の形態3に係る関数計算部12は、パディング関数pad、関数T[1],...,関数T[i]、関数p[1],...,関数p[i]、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、関数R[1],...,関数R[i]、関数S[1],...,関数S[i]、関数Vを用いて、図3や図6に示す関数Fを構成する。
【0069】
パディング関数padは、例えば、M’=pad(M)=M||1||0...0||<M>である。ここで、<M>は、例えば、64ビットの値であり、Mのビット長情報を含む値である。
つまり、パディング関数padは、先頭が“1”で、その後が複数の“0”で、最後に<M>となるビット列を生成して、値Mに付加して、値M’を生成する関数である。
なお、M’がL’+L(i−1)ビットとなるように0の個数が決定される。
【0070】
関数T[1]は、L’ビット長の値を入力として、dビット長の値を出力する関数である。
関数T[1]は、例えば、const’をd−L’ビット長の固定値とした場合、L’ビット長の入力値mに対して、const’をビット結合したものを出力する関数である。なお、L’=dの場合には、入力値をそのまま出力するものとする。
値mと値const’とのビット結合の方法は、値mと値const’とをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0071】
関数T[2],...,関数T[i]は、Lビット長の値と、nビット長の値とを入力として、dビット長の値を出力する関数である。
関数T[2],...,関数T[i]は、値constを(d−L−n)ビットの固定値とした場合、Lビットの入力値mと、nビットの入力値xと、値constとをビット結合したものを出力する関数である。なお、L=d−nの場合は、値constは付加しない。
入力値mと入力値xと値constとビット結合の方法は、入力値mと入力値xと値constとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0072】
関数p[1],...,関数p[i]は、全てのnビットの値xに対してp[j](x)≠x(j=1,...,i)となる置換関数である。
【0073】
暗号化関数E1,1,...,暗号化関数Ei,1と、暗号化関数E1,2,...,暗号化関数Ei,2とは、dビット長の値と、nビット長の値とを入力として、nビット長の値を出力するブロック暗号の暗号化関数である。
暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1,E2は、全て同じ暗号化関数であってもよい。
また、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2は同じ暗号化関数であり、暗号化関数E1,E2は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2と異なる暗号化関数であってもよい。この場合、暗号化関数E1,E2は、同じ暗号化関数であってもよいし、異なる暗号化関数であってもよい。
【0074】
関数R[1],...,関数R[i]と、関数S[1],...,関数S[i]とは、2つのnビット長の値を入力として、nビット長の値を出力する関数である。
関数R[1],...,関数R[i]と、関数S[1],...,関数S[i]とは、例えば、2つのnビット長の入力値x,yに対して、値xと値yとの排他的論理和を出力する関数である。
また、関数R[1],...,関数R[i]と、関数S[1],...,関数S[i]とは、2つのnビット長の入力値x,yに対して、値xと値yとを加算した値を出力する関数であってもよい。この場合、加算方法は、例えば、値xと値yとの先頭からLビットづつをそれぞれ加算していき、最後に加算したものをビット結合すればよい。
【0075】
関数Vは、2つのnビット長の値を入力として、tビット長の値を出力する関数である。
関数Vは、例えば、2つのnビット長の入力値x,yに対して、値xと値yとをビット結合し、そのうちtビットを所定の方法で抽出して出力する関数である。なお、t=2nの場合は、ビット結合した値をそのまま出力すればよい。
値xと値yとのビット結合の方法は、値xと値yとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。また、ビットの抽出方法は、先頭から抽出してもよいし、後ろから抽出してもよく、それ以外の抽出方法でもよい。
【0076】
実施の形態1に係るハッシュ値演算装置10が、実施の形態3に係る関数計算部12が実現する関数Fを用いて実現したハッシュ関数は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1,E2が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。そして、その安全性のセキュリティレベルはO(2n)となる。また、このハッシュ関数は、各暗号化関数の出力長がnビットであり、ハッシュ値の出力長が最大2nビットである。
【0077】
実施の形態2に係るハッシュ値演算装置10が、実施の形態3に係る関数計算部12が実現する関数Fを用いて実現したハッシュ関数は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。そして、その安全性のセキュリティレベルはO(2n)となる。また、このハッシュ関数は、各暗号化関数の出力長がnビットであり、ハッシュ値の出力長が最大nビットである。
【0078】
なお、実施の形態1に係るハッシュ関数と、実施の形態2に係るハッシュ関数との出力長を同じ2nとする場合、実施の形態1に係るハッシュ関数は、上述した通り、安全性のセキュリティレベルはO(2n)であり、用いる各暗号化関数の出力長がnビットである。一方、実施の形態2に係るハッシュ関数は、安全性のセキュリティレベルはO(22n)であり、用いる各暗号化関数の出力長が2nビットである。
つまり、ハッシュ関数の出力長を同じにした場合、実施の形態1に係るハッシュ関数の方が、実施の形態2に係るハッシュ関数よりも、用いる暗号化関数の出力長が短くてよい。そのため、例えば、ハッシュ関数を回路で実現した場合、回路規模を小さくできる。一方、実施の形態2に係るハッシュ関数の方が、実施の形態1に係るハッシュ関数よりも、安全性のセキュリティレベルが高い。
【0079】
実施の形態4.
実施の形態4では、実施の形態1,2における関数Fの実施の形態3とは異なる例について説明する。
【0080】
図10は、実施の形態4に係る関数計算部12の機能を示す機能ブロック図である。
図11は、図10に示す実施の形態4に係る関数計算部12の動作を示すフローチャートである。
図12は、図10に示す実施の形態4に係る関数計算部12により実現されるハッシュ関数の構造図である。なお、図12では、図3と同様に、各値の下に括弧書でその値のビット長を示す。
【0081】
図10に示すハッシュ値演算装置10の機能と動作について、図11、図12を用いて説明する。
図10に示す関数計算部12は、関数h計算部32、関数h’計算部33を備え、関数p計算部26、関数R計算部25、関数S計算部28を備えていない点が図7に示す関数計算部12と異なる。
【0082】
(S41)から(S43)までの処理は、図8に示す(S21)から(S23)までの処理と同じであるため、説明を省略する。但し、ここでのLは1以上d−2n以下の整数である。
【0083】
(S44:関数g1計算ステップ)
鍵成分k1計算部23は、(S42)で生成された値m[j](値m[1])を入力として、関数g[j](関数g[1])を計算してdビット長の値k[j](値k[1])を処理装置により求める。
【0084】
(S45:暗号化関数Ej,1計算ステップ)
暗号化関数Ej,1計算部24は、(S44)又は後述する(S50)で求めた値k[j]を鍵成分とし、nビット長の所定の値cj,1を平文成分として、暗号化関数Ej,1を計算してnビット長の値y[j]を処理装置により求める。
【0085】
(S46:暗号化関数Ej,2計算ステップ)
暗号化関数Ej,2計算部27は、(S44)又は後述する(S50)で求めた値k[j]を鍵成分とし、nビット長の所定の値cj,2を平文成分として、暗号化関数Ej,2を計算してnビット長の値yy[j]を処理装置により求める。
なお、(S45)と(S46)とは並列に実行してもよい。
【0086】
(S47:関数h計算ステップ)
関数h計算部32は、(S45)で求めた値y[j]と、(S46)で求めた値yy[j]とを入力として、関数h[j]を計算して2nビット長の値w[j]を処理装置により求める。
【0087】
(S48:変数j判定ステップ)
関数計算部12は、変数jの値が値iであるか否かを判定する。変数jの値が値iでなければ(S48でNO)、処理を(S49)へ進める。一方、変数jの値が値iであれば(S48でYES)、処理を(S51)へ進める。
【0088】
(S49:変数jインクリメントステップ)
関数計算部12は、変数jに1を加算する。
【0089】
(S50:関数g計算ステップ)
鍵成分kj計算部29は、(S42)で生成された値m[j]と、(S47)で求めた値w[j−1]とを入力として、関数g[j]を計算してdビット長の値k[j]を処理装置により求める。
そして、処理を(S45)及び(S46)へ戻す。
【0090】
(S51:関数h’計算ステップ)
関数h’計算部33は、(S47)で求めた値w[i]を入力として、関数h’を計算してtビット長の値wを処理装置により求める。
【0091】
つまり、実施の形態4に係る関数計算部12は、パディング関数pad、関数g[1],...,関数g[i]、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、関数h[1],...,関数h[i]、関数h’を用いて、図3や図6に示す関数Fを構成する。
【0092】
パディング関数padは、実施の形態3のパディング関数padと同じである。
【0093】
関数g[1]は、L’ビット長の値を入力として、dビット長の値を出力する関数である。
関数g[1]は、例えば、const’をd−L’ビット長の固定値とした場合、L’ビット長の入力値mに対して、const’をビット結合したものを出力する関数である。なお、L’=dの場合には、入力値をそのまま出力するものとする。
値mと値const’とのビット結合の方法は、値mと値const’とをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0094】
関数g[2],...,関数g[i]は、Lビット長の値と、nビット長の値とを入力として、dビット長の値を出力する関数である。
値constを(d−L−2n)ビットの固定値とした場合、Lビットの入力値mと、nビットの入力値xと、値constとをビット結合したものを出力する関数である。なお、L=d−2nの場合は、値constは付加しない。
入力値mと入力値xと値constとビット結合の方法は、入力値mと入力値xと値constとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0095】
暗号化関数E1,1,...,暗号化関数Ei,1と、暗号化関数E1,2,...,暗号化関数Ei,2とは、dビット長の値と、nビット長の値とを入力として、nビット長の値を出力するブロック暗号の暗号化関数である。
暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1,E2は、全て同じ暗号化関数であってもよい。
また、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2は同じ暗号化関数であり、暗号化関数E1,E2は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2と異なる暗号化関数であってもよい。この場合、暗号化関数E1,E2は、同じ暗号化関数であってもよいし、異なる暗号化関数であってもよい。
【0096】
関数h[1],...,関数h[i]は、2つのnビット長の値を入力として、2nビット長の値を出力する関数である。
関数h[1],...,関数h[i]は、2つのnビット長の値をビット結合する関数である。2つのnビットの値のビット結合の方法は、2つのnビットの値をそのまま結合してもよいし、ビットを混ぜて結合してもよい。
【0097】
関数h’は、2つのnビット長の値を入力として、tビット長の値を出力する関数である。
関数h’は、例えば、2つのnビット長の入力値x,yに対して、値xと値yとをビット結合し、そのうちtビットを所定の方法で抽出して出力する関数である。
値xと値yとのビット結合の方法は、値xと値yとをそのまま結合してもよいし、ビットを混ぜて結合してもよい。また、ビットの抽出方法は、先頭から抽出してもよいし、後ろから抽出してもよく、それ以外の抽出方法でもよい。
【0098】
実施の形態1に係るハッシュ値演算装置10が、実施の形態4に係る関数計算部12が実現する関数Fを用いて実現したハッシュ関数は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1,E2が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。そして、その安全性のセキュリティレベルはO(2n)となる。また、このハッシュ関数は、各暗号化関数の出力長がnビットであり、ハッシュ値の出力長が最大2nビットである。
【0099】
実施の形態2に係るハッシュ値演算装置10が、実施の形態4に係る関数計算部12が実現する関数Fを用いて実現したハッシュ関数は、暗号化関数E1,1,...,暗号化関数Ei,1、暗号化関数E1,2,...,暗号化関数Ei,2、暗号化関数E1が理想化されたブロック暗号における暗号化関数である場合、擬似ランダムオラクルの性質を満たす。そして、その安全性のセキュリティレベルはO(2n)となる。また、このハッシュ関数は、各暗号化関数の出力長がnビットであり、ハッシュ値の出力長が最大nビットである。
【0100】
なお、実施の形態1に係るハッシュ関数と、実施の形態2に係るハッシュ関数との出力長を同じ2nとする場合、実施の形態1に係るハッシュ関数は、上述した通り、安全性のセキュリティレベルはO(2n)であり、用いる各暗号化関数の出力長がnビットである。一方、実施の形態2に係るハッシュ関数は、安全性のセキュリティレベルはO(22n)であり、用いる各暗号化関数の出力長が2nビットである。
つまり、ハッシュ関数の出力長を同じにした場合、実施の形態1に係るハッシュ関数の方が、実施の形態2に係るハッシュ関数よりも、用いる暗号化関数の出力長が短くてよい。そのため、例えば、ハッシュ関数を回路で実現した場合、回路規模を小さくできる。一方、実施の形態2に係るハッシュ関数の方が、実施の形態1に係るハッシュ関数よりも、安全性のセキュリティレベルが高い。
【0101】
以上に説明したハッシュ値演算装置10は、例えば、回路やソフトウェア等で構成される。回路で構成される場合には、上記説明における処理装置は、例えば演算回路であり、記憶装置は、例えばレジスタである。また、ソフトウェアで構成される場合には、上記説明における処理装置は、例えばCPU(Central Processing Unit)であり、記憶装置は、例えばRAM(Random Access Memory)である。また、上記説明における入力装置は、例えばキーボード、通信ボードであり、出力装置は、例えばLCD(Liquid Crystal Display)等の表示装置、通信ボード、レジスタやRAM等の記憶装置である。もちろん、これらに限定されるものではない。
なお、ハッシュ値演算装置10を回路で構成する場合、上述した「〜部」を「〜回路」と読み変えてもよい。また、上述した「〜部」は、「〜処理」、「〜装置」、「〜機器」、「〜手段」、「〜手順」、「〜機能」と読み替えてもよい。つまり、「〜部」として説明するものは、ROM(Read Only Memory)に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実現されても構わない。
【符号の説明】
【0102】
10 ハッシュ値演算装置、11 任意長値入力部、12 関数計算部、13 鍵成分計算部、14 暗号化関数E1計算部、15 暗号化関数E2計算部、16 ハッシュ値計算部、21 パディング部、22 分割部、23 鍵成分k1計算部、24 暗号化関数Ej,1計算部、25 関数R計算部、26 関数p計算部、27 暗号化関数Ej,2計算部、28 関数S計算部、29 鍵成分kj計算部、30 関数V計算部、31 変数j制御部、32 関数h計算部、33 関数h’計算部。
【特許請求の範囲】
【請求項1】
任意ビット長の値Mを入力する任意長値入力部と、
前記任意長値入力部が入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算部と、
前記関数計算部が求めた値wを入力として、関数gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算部と、
前記鍵成分計算部が求めた値kを鍵成分とし、nビット長の所定の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算部と、
前記鍵成分計算部が求めた値kを鍵成分とし、nビット長の所定の値c2を平文成分として、ブロック暗号の暗号化関数E2を計算してnビット長の値yyを求める暗号化関数E2計算部と、
前記暗号化関数E1計算部が求めた値yと、前記暗号化関数E2計算部が求めた値yyとを入力として、関数hを計算してn’ビット長(n’は1以上2n以下の整数)の値zをハッシュ値として求めるハッシュ値計算部と
を備えることを特徴とするハッシュ値演算装置。
【請求項2】
任意ビット長の値Mを入力する任意長値入力部と、
前記任意長値入力部が入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算部と、
前記関数計算部が求めた値wを入力として、関数Gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算部と、
前記鍵成分計算部が求めた値kを鍵成分とし、nビット長の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算部と、
前記暗号化関数E1計算部が求めた値yを入力として、関数Hを計算してn’ビット長(n’は1以上n以下の整数)の値zをハッシュ値として求めるハッシュ値計算部と
を備えることを特徴とするハッシュ値演算装置。
【請求項3】
前記関数計算部は、
前記任意長値入力部が入力した値Mに対して、所定の値を付加して(L’+L(i−1))ビット長(L’は1以上d以下の整数、Lは1以上d−n以下の整数、iは1以上の整数)の値M’を生成するパディング部と、
前記パディング部が生成した値M’を分割して、L’ビット長の値m[1]と、Lビット長の値m[2],...,値m[i]を生成する分割部と、
前記分割部が生成した値m[1]を入力として、関数T[1]を計算してdビット長の値k[1]を求める鍵成分k1計算部と、
j=1からiまで順に、値k[j]を鍵成分とし、nビット長の値y[j−1](値y[0]は固定値IVとする)を平文成分として、ブロック暗号の暗号化関数Ej,1を計算してnビット長の値x[j]を求める暗号化関数Ej,1計算部と、
j=1からiまで順に、前記値y[j−1]と、前記暗号化関数Ej,1計算部が計算した値x[j]とを入力として、関数R[j]を計算してnビット長の値y[j]を求める関数R計算部と、
j=1からiまで順に、前記値y[j−1]を入力として、関数p[j]を計算してnビット長の値vv[j]を求める関数p計算部と、
j=1からiまで順に、前記値k[j]を鍵成分とし、前記関数p計算部が求めた値vv[j]を平文成分として、ブロック暗号の暗号化関数Ej,2を計算してnビット長の値xx[j]を求める暗号化関数Ej,2計算部と、
j=1からiまで順に、前記暗号化関数Ej,2計算部が求めた値xx[j]を入力として、関数S[j]を計算してnビット長の値yy[j]を求める関数S計算部と、
j=2からiまで順に、前記分割部が生成した値m[j]と、前記関数S計算部が計算した値yy[j−1]とを入力として、関数T[j]を計算してdビット長の値k[j]を求める鍵成分kj計算部と、
前記関数R計算部が求めた値y[i]と、前記関数S計算部が求めた値yy[i]とを入力として、関数Vを計算して2nビット長の前記値wを求める関数V計算部と
を備えることを特徴とする請求項1又は2に記載のハッシュ値演算装置。
【請求項4】
前記関数計算部は、
前記任意長値入力部が入力した値Mに対して、所定の値を付加して(L’+L(i−1))ビット長(L’は1以上d以下の整数、Lは1以上d−2n以下の整数、iは1以上の整数)の値M’を生成するパディング部と、
前記パディング部が生成した値M’を分割して、L’ビット長の値m[1]と、Lビット長の値m[2],...,値m[i]を生成する分割部と、
前記分割部が生成した値m[1]を入力として、関数g[1]を計算してdビット長の値k[1]を求める鍵成分k1計算部と、
j=1からiまで順に、値k[j]を鍵成分とし、nビット長の所定の値cj,1を平文成分として、ブロック暗号の暗号化関数Ej,1を計算してnビット長の値y[j]を求める暗号化関数Ej,1計算部と、
j=1からiまで順に、前記値k[j]を鍵成分とし、nビット長の所定の値cj,2を平文成分として、ブロック暗号の暗号化関数Ej,2を計算してnビット長の値yy[j]を求める暗号化関数Ej,2計算部と、
j=1からiまで順に、前記暗号化関数Ej,1計算部が求めた値y[j]と、前記暗号化関数Ej,2計算部が求めた値yy[j]とを入力として、関数h[j]を計算して2nビット長の値w[j]を求める関数h計算部と、
j=2からiまで順に、前記分割部が生成した値m[j]と、前記関数h計算部が計算した値w[j−1]とを入力として、関数h[j]を計算してdビット長の値k[j]を求める鍵成分kj計算部と、
前記関数h計算部が求めた値w[i]を入力として、関数h’を計算してtビット長の前記値wを求める関数h’計算部と
を備えることを特徴とする請求項1又は2に記載のハッシュ値演算装置。
【請求項5】
任意ビット長の値Mを入力する任意長値入力工程と、
前記任意長値入力工程で入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算工程と、
前記関数計算工程で求めた値wを入力として、関数gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算工程と、
前記鍵成分計算工程で求めた値kを鍵成分とし、nビット長の所定の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算工程と、
前記鍵成分計算工程で求めた値kを鍵成分とし、nビット長の所定の値c2を平文成分として、ブロック暗号の暗号化関数E2を計算してnビット長の値yyを求める暗号化関数E2計算工程と、
前記暗号化関数E1計算工程で求めた値yと、前記暗号化関数E2計算工程で求めた値yyとを入力として、関数hを計算してn’ビット長(n’は1以上2n以下の整数)の値zをハッシュ値として求めるハッシュ値計算工程と
を備えることを特徴とするハッシュ値演算方法。
【請求項6】
任意ビット長の値Mを入力する任意長値入力処理と、
前記任意長値入力処理で入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算処理と、
前記関数計算処理で求めた値wを入力として、関数gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算処理と、
前記鍵成分計算処理で求めた値kを鍵成分とし、nビット長の所定の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算処理と、
前記鍵成分計算処理で求めた値kを鍵成分とし、nビット長の所定の値c2を平文成分として、ブロック暗号の暗号化関数E2を計算してnビット長の値yyを求める暗号化関数E2計算処理と、
前記暗号化関数E1計算処理で求めた値yと、前記暗号化関数E2計算処理で求めた値yyとを入力として、関数hを計算してn’ビット長(n’は1以上2n以下の整数)の値zをハッシュ値として求めるハッシュ値計算処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項7】
任意ビット長の値Mを入力する任意長値入力工程と、
前記任意長値入力工程で入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算工程と、
前記関数計算工程で求めた値wを入力として、関数Gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算工程と、
前記鍵成分計算工程で求めた値kを鍵成分とし、nビット長の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算工程と、
前記暗号化関数E1計算工程で求めた値yを入力として、関数Hを計算してn’ビット長(n’は1以上n以下の整数)の値zをハッシュ値として求めるハッシュ値計算工程と
を備えることを特徴とするハッシュ値演算方法。
【請求項8】
任意ビット長の値Mを入力する任意長値入力処理と、
前記任意長値入力処理で入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算処理と、
前記関数計算処理で求めた値wを入力として、関数Gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算処理と、
前記鍵成分計算処理で求めた値kを鍵成分とし、nビット長の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算処理と、
前記暗号化関数E1計算処理で求めた値yを入力として、関数Hを計算してn’ビット長(n’は1以上n以下の整数)の値zをハッシュ値として求めるハッシュ値計算処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項1】
任意ビット長の値Mを入力する任意長値入力部と、
前記任意長値入力部が入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算部と、
前記関数計算部が求めた値wを入力として、関数gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算部と、
前記鍵成分計算部が求めた値kを鍵成分とし、nビット長の所定の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算部と、
前記鍵成分計算部が求めた値kを鍵成分とし、nビット長の所定の値c2を平文成分として、ブロック暗号の暗号化関数E2を計算してnビット長の値yyを求める暗号化関数E2計算部と、
前記暗号化関数E1計算部が求めた値yと、前記暗号化関数E2計算部が求めた値yyとを入力として、関数hを計算してn’ビット長(n’は1以上2n以下の整数)の値zをハッシュ値として求めるハッシュ値計算部と
を備えることを特徴とするハッシュ値演算装置。
【請求項2】
任意ビット長の値Mを入力する任意長値入力部と、
前記任意長値入力部が入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算部と、
前記関数計算部が求めた値wを入力として、関数Gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算部と、
前記鍵成分計算部が求めた値kを鍵成分とし、nビット長の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算部と、
前記暗号化関数E1計算部が求めた値yを入力として、関数Hを計算してn’ビット長(n’は1以上n以下の整数)の値zをハッシュ値として求めるハッシュ値計算部と
を備えることを特徴とするハッシュ値演算装置。
【請求項3】
前記関数計算部は、
前記任意長値入力部が入力した値Mに対して、所定の値を付加して(L’+L(i−1))ビット長(L’は1以上d以下の整数、Lは1以上d−n以下の整数、iは1以上の整数)の値M’を生成するパディング部と、
前記パディング部が生成した値M’を分割して、L’ビット長の値m[1]と、Lビット長の値m[2],...,値m[i]を生成する分割部と、
前記分割部が生成した値m[1]を入力として、関数T[1]を計算してdビット長の値k[1]を求める鍵成分k1計算部と、
j=1からiまで順に、値k[j]を鍵成分とし、nビット長の値y[j−1](値y[0]は固定値IVとする)を平文成分として、ブロック暗号の暗号化関数Ej,1を計算してnビット長の値x[j]を求める暗号化関数Ej,1計算部と、
j=1からiまで順に、前記値y[j−1]と、前記暗号化関数Ej,1計算部が計算した値x[j]とを入力として、関数R[j]を計算してnビット長の値y[j]を求める関数R計算部と、
j=1からiまで順に、前記値y[j−1]を入力として、関数p[j]を計算してnビット長の値vv[j]を求める関数p計算部と、
j=1からiまで順に、前記値k[j]を鍵成分とし、前記関数p計算部が求めた値vv[j]を平文成分として、ブロック暗号の暗号化関数Ej,2を計算してnビット長の値xx[j]を求める暗号化関数Ej,2計算部と、
j=1からiまで順に、前記暗号化関数Ej,2計算部が求めた値xx[j]を入力として、関数S[j]を計算してnビット長の値yy[j]を求める関数S計算部と、
j=2からiまで順に、前記分割部が生成した値m[j]と、前記関数S計算部が計算した値yy[j−1]とを入力として、関数T[j]を計算してdビット長の値k[j]を求める鍵成分kj計算部と、
前記関数R計算部が求めた値y[i]と、前記関数S計算部が求めた値yy[i]とを入力として、関数Vを計算して2nビット長の前記値wを求める関数V計算部と
を備えることを特徴とする請求項1又は2に記載のハッシュ値演算装置。
【請求項4】
前記関数計算部は、
前記任意長値入力部が入力した値Mに対して、所定の値を付加して(L’+L(i−1))ビット長(L’は1以上d以下の整数、Lは1以上d−2n以下の整数、iは1以上の整数)の値M’を生成するパディング部と、
前記パディング部が生成した値M’を分割して、L’ビット長の値m[1]と、Lビット長の値m[2],...,値m[i]を生成する分割部と、
前記分割部が生成した値m[1]を入力として、関数g[1]を計算してdビット長の値k[1]を求める鍵成分k1計算部と、
j=1からiまで順に、値k[j]を鍵成分とし、nビット長の所定の値cj,1を平文成分として、ブロック暗号の暗号化関数Ej,1を計算してnビット長の値y[j]を求める暗号化関数Ej,1計算部と、
j=1からiまで順に、前記値k[j]を鍵成分とし、nビット長の所定の値cj,2を平文成分として、ブロック暗号の暗号化関数Ej,2を計算してnビット長の値yy[j]を求める暗号化関数Ej,2計算部と、
j=1からiまで順に、前記暗号化関数Ej,1計算部が求めた値y[j]と、前記暗号化関数Ej,2計算部が求めた値yy[j]とを入力として、関数h[j]を計算して2nビット長の値w[j]を求める関数h計算部と、
j=2からiまで順に、前記分割部が生成した値m[j]と、前記関数h計算部が計算した値w[j−1]とを入力として、関数h[j]を計算してdビット長の値k[j]を求める鍵成分kj計算部と、
前記関数h計算部が求めた値w[i]を入力として、関数h’を計算してtビット長の前記値wを求める関数h’計算部と
を備えることを特徴とする請求項1又は2に記載のハッシュ値演算装置。
【請求項5】
任意ビット長の値Mを入力する任意長値入力工程と、
前記任意長値入力工程で入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算工程と、
前記関数計算工程で求めた値wを入力として、関数gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算工程と、
前記鍵成分計算工程で求めた値kを鍵成分とし、nビット長の所定の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算工程と、
前記鍵成分計算工程で求めた値kを鍵成分とし、nビット長の所定の値c2を平文成分として、ブロック暗号の暗号化関数E2を計算してnビット長の値yyを求める暗号化関数E2計算工程と、
前記暗号化関数E1計算工程で求めた値yと、前記暗号化関数E2計算工程で求めた値yyとを入力として、関数hを計算してn’ビット長(n’は1以上2n以下の整数)の値zをハッシュ値として求めるハッシュ値計算工程と
を備えることを特徴とするハッシュ値演算方法。
【請求項6】
任意ビット長の値Mを入力する任意長値入力処理と、
前記任意長値入力処理で入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算処理と、
前記関数計算処理で求めた値wを入力として、関数gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算処理と、
前記鍵成分計算処理で求めた値kを鍵成分とし、nビット長の所定の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算処理と、
前記鍵成分計算処理で求めた値kを鍵成分とし、nビット長の所定の値c2を平文成分として、ブロック暗号の暗号化関数E2を計算してnビット長の値yyを求める暗号化関数E2計算処理と、
前記暗号化関数E1計算処理で求めた値yと、前記暗号化関数E2計算処理で求めた値yyとを入力として、関数hを計算してn’ビット長(n’は1以上2n以下の整数)の値zをハッシュ値として求めるハッシュ値計算処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項7】
任意ビット長の値Mを入力する任意長値入力工程と、
前記任意長値入力工程で入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算工程と、
前記関数計算工程で求めた値wを入力として、関数Gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算工程と、
前記鍵成分計算工程で求めた値kを鍵成分とし、nビット長の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算工程と、
前記暗号化関数E1計算工程で求めた値yを入力として、関数Hを計算してn’ビット長(n’は1以上n以下の整数)の値zをハッシュ値として求めるハッシュ値計算工程と
を備えることを特徴とするハッシュ値演算方法。
【請求項8】
任意ビット長の値Mを入力する任意長値入力処理と、
前記任意長値入力処理で入力した値Mを入力として、関数Fを計算してtビット長(tは1以上の整数)の値wを求める関数計算処理と、
前記関数計算処理で求めた値wを入力として、関数Gを計算してdビット長(dはt以上の整数)の値kを求める鍵成分計算処理と、
前記鍵成分計算処理で求めた値kを鍵成分とし、nビット長の値c1を平文成分として、ブロック暗号の暗号化関数E1を計算してnビット長(nは1以上の整数)の値yを求める暗号化関数E1計算処理と、
前記暗号化関数E1計算処理で求めた値yを入力として、関数Hを計算してn’ビット長(n’は1以上n以下の整数)の値zをハッシュ値として求めるハッシュ値計算処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2012−68436(P2012−68436A)
【公開日】平成24年4月5日(2012.4.5)
【国際特許分類】
【出願番号】特願2010−213244(P2010−213244)
【出願日】平成22年9月24日(2010.9.24)
【出願人】(000006013)三菱電機株式会社 (33,312)
【Fターム(参考)】
【公開日】平成24年4月5日(2012.4.5)
【国際特許分類】
【出願日】平成22年9月24日(2010.9.24)
【出願人】(000006013)三菱電機株式会社 (33,312)
【Fターム(参考)】
[ Back to top ]