説明

ハッシュ値演算装置、ハッシュ値演算方法及びハッシュ値演算プログラム

【課題】一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルと強識別不可能であるハッシュ関数であって、計算効率がよいハッシュ関数を構成することを目的とする。
【解決手段】ハッシュ関数で用いられる圧縮関数への入力値を、入力された値に所定の固定値を付加した値として、ハッシュ関数を構成する。

【発明の詳細な説明】
【技術分野】
【0001】
この発明は、例えば、効率的にハッシュ値を計算する技術に関する。
【背景技術】
【0002】
非特許文献1には、一方向性が破られた理想的な圧縮関数(WFILRO(Weakened Fixed Input Length Random Oracle))を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能なハッシュ関数であるジッパーハッシュ関数(zipperハッシュ関数)についての記載がある。
【0003】
非特許文献2には、一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能なハッシュ関数であるダブルパイプハッシュ関数(double pipeハッシュ関数)についての記載がある。
【先行技術文献】
【非特許文献】
【0004】
【非特許文献1】Moses Liskov: Constructing an Ideal Hash Function from Weak Ideal Compression Functions. Selected Areas in Cryptography 2006: 358−375
【非特許文献2】Stefan Lucks: A Failure−Friendly Design Principle for Hash Functions. ASIACRYPT 2005: 474−494
【非特許文献3】Mihir Bellare, Thomas Ristenpart: Multi−Property−Preserving Hash Domain Extension and the EMD Transform. ASIACRYPT 2006: 299−314
【非特許文献4】Shoichi Hirose, Je Hong Park, Aaram Yun: A Simple Variant of the Merkle−Damgard Scheme with a Permutation. ASIACRYPT 2007: 113−129
【非特許文献5】Ueli Maurer, Renato Renner, and Clemens Holensteinindifferentiability impossibility results on reductions and applicationsto the random oracle methodologyTCC 2004, pp 21−39, LNCS 2951 Springer 2004, ISBN 3−540−21000−8
【非特許文献6】Ralph C. Merkle/One Way Hash Functions and DES/,Crypto 1989, pp 428−446, LNCS 435 Springer 1990, ISBN 3−540−97317−6
【発明の概要】
【発明が解決しようとする課題】
【0005】
非特許文献1,2に記載されたジッパーハッシュ関数とダブルパイプハッシュ関数とは、一方向性が破られた理想的な圧縮関数を用い、ランダムオラクルと強識別不可能なハッシュ関数であるものの、計算効率が悪い。
この発明は、例えば、一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルと強識別不可能であるハッシュ関数であって、ジッパーハッシュ関数やダブルパイプハッシュ関数よりも計算効率がよいハッシュ関数を構成することを目的とする。
【課題を解決するための手段】
【0006】
この発明に係るハッシュ値演算装置は、例えば、
i個の値p[1],...,値p[i]を入力する既定長値入力部と、
前記既定長値入力部が入力した値p[1],...,値p[i]のうち、i−1個の値p[1],...,値p[i−1]それぞれに対して、固定値const[1],...,固定値const[i−1]を付加して、値x[1],...,値x[i−1]を生成して記憶装置に記憶する固定値付加部と、
j=1からi−1まで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加部が生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i−1]を得て記憶装置に記憶し、
固定値IV2と、値p[i]に値c[i−1]を付加した値x[i]とを入力として、圧縮関数hを計算した結果である値c[i]を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が得た値c[i]を出力する出力部と
を備えることを特徴とする。
【発明の効果】
【0007】
この発明に係るハッシュ値演算装置では、圧縮関数への入力値に固定値を付加しする。これにより、一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルと強識別不可能であるハッシュ関数を構成することができる。そして、このハッシュ関数は、ジッパーハッシュ関数やダブルパイプハッシュ関数よりも効率がよい。
【図面の簡単な説明】
【0008】
【図1】実施の形態1に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図2】図1に示すハッシュ値演算装置10の動作を示すフローチャート。
【図3】図1に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図4】値p[1],...,値p[i]を生成する機能を追加した実施の形態1に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図5】図4に示すハッシュ値演算装置10の動作を示すフローチャート。
【図6】図4に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図7】所定のパディング処理を行う場合の図4に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図8】圧縮関数としてSHA−256を用いる場合の図4に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図9】実施の形態2に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図10】図9に示すハッシュ値演算装置10の動作を示すフローチャート。
【図11】図9に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図12】値p[1],...,値p[i]を生成する機能を追加した実施の形態2に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図13】図12に示すハッシュ値演算装置10の動作を示すフローチャート。
【図14】図12に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図15】所定のパディング処理を行う場合の図12に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図16】所定のパディング処理を行う場合の図12に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図17】圧縮関数としてSHA−256を用いる場合の図12に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図18】実施の形態3に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図19】図18に示すハッシュ値演算装置10の動作を示すフローチャート。
【図20】図18に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図21】値p[1],...,値p[i+1]を生成する機能を追加した実施の形態3に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図22】図21に示すハッシュ値演算装置10の動作を示すフローチャート。
【図23】図21に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図24】所定のパディング処理を行う場合の図21に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図25】圧縮関数としてSHA−256を用いる場合の図21に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図26】実施の形態4に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図27】図26に示すハッシュ値演算装置10の動作を示すフローチャート。
【図28】図26に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図29】値p[1],...,値p[i]を生成する機能を追加した実施の形態2に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図30】図29に示すハッシュ値演算装置10の動作を示すフローチャート。
【図31】図29に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図32】所定のパディング処理を行う場合の図29に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図33】圧縮関数としてSHA−256を用いる場合の図29に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図34】実施の形態5に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図35】図34に示すハッシュ値演算装置10の動作を示すフローチャート。
【図36】図34に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図37】値p[1],...,値p[i]を生成する機能を追加した実施の形態5に係るハッシュ値演算装置10の機能を示す機能ブロック図。
【図38】図37に示すハッシュ値演算装置10の動作を示すフローチャート。
【図39】図37に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図40】所定のパディング処理を行う場合の図37に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図41】所定のパディング処理を行う場合の図37に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図42】圧縮関数としてSHA−256を用いる場合の図37に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図。
【図43】ハッシュ値演算装置10のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【0009】
まず、ハッシュ関数の安全性の概念について説明する。
【0010】
ハッシュ関数は、任意長の値を入力として、固定長の値を出力する関数である。
ハッシュ関数の満たすべき性質として、以下の3つの性質がある。以下、ハッシュ関数をHとする。
1.衝突困難性(collision resistance):H(M)=H(M’)となる2つの値M,M’を見つけることが困難であること。
2.第2現像計算困難性(second preimage resistance):ランダムな値Mに対して、H(M)=H(M’)となる値Mとは異なる値M’を見つけることが困難であること。
3.現像計算困難性(preimage resistance):ランダムな値zに対して、z=H(M)となる値Mを見つけることが困難であること。
【0011】
ハッシュ関数は、入力長、出力長が固定された圧縮関数と呼ばれる関数から構成される。ハッシュ関数の代表的な構成として、MD(Merkle−Damgard)構造がある。
MD構造は、以下のような構成である。
(Step1)入力Mにstrengthen MDパディングを適用し、長さがmの倍数となる値M’を作る。
(Step2)M’をmビットの値p[1],...,p[i]に分割する。
(Step3)値p[1],...,p[i]のそれぞれに対し、c[j]=h(c[j−1],p[j])を計算する。ここで、c[0]はnビットの固定値である。また、hは圧縮関数である。圧縮関数hは、入力として、nビットの値とmビットの値との2つの値を入力として、nビットの値を出力する関数である。
(Step4)C[i]を出力する。
【0012】
ハッシュ関数を用いるOAEP(Optimal Asymmetric Encryption Padding)やPSS(Probabilistic Signature Scheme)等の暗号アルゴリズムは、ハッシュ関数ではなく、理想関数であるランダムオラクルを用いた場合に安全であることが証明されている。
ランダムオラクルとは、予め全ての入力値と、各入力値に対してランダムに選択された出力値とのペアをリスト(メモリ)に記録しておき、入力値に対する出力値は、予め記録したリストを引いて決定する関数である。
【0013】
ランダムオラクルモデルを用いた場合に安全な暗号アルゴリズムは、ランダムオラクルに代えて安全なハッシュ関数を用いても、安全であると考えられている。ここで、安全なハッシュ関数とは、上述した3つの性質を満たすハッシュ関数である。
【0014】
しかし、実際には、ランダムオラクルを用いた場合に安全である暗号アルゴリズムが、ランダムオラクルに代えて安全なハッシュ関数を用いた場合にも安全であるとは限らない。つまり、ランダムオラクルを用いた暗号アルゴリズムが安全であっても、安全なハッシュ関数を用いた暗号アルゴリズムが安全であるとは限らない。
実際には、ランダムオラクルを用いた場合に安全である暗号アルゴリズムに対して、ランダムオラクルに代えてハッシュ関数を用いた場合に、その暗号アルゴリズムが安全であるというためには、用いたハッシュ関数がランダムオラクルといわゆる強識別不可能(非特許文献5参照)である必要がある。
つまり、ランダムオラクルを用いた場合に安全であることが証明されている暗号アルゴリズムが、ランダムオラクルと強識別不可能であるハッシュ関数を用いた場合には安全である。すなわち、ランダムオラクルを用いた暗号アルゴリズムが安全であれば、ランダムオラクルと強識別不可能であるハッシュ関数を用いた暗号アルゴリズムは安全である。
【0015】
ランダムオラクルと強識別不可能であるハッシュ関数とは、例えば、EMD(Employed Merkle−Damgard),MDP(Merkle−Damgard with Permutation)等である。
【0016】
一般に、EMDやMDPのように、ランダムオラクルといわゆる強識別不可能であるハッシュ関数は、圧縮関数として理想化された圧縮関数(FILRO(Fixed Input Length Random Oracle))を用いて構成される。つまり、EMDやMDPに代表されるハッシュ関数は、圧縮関数として理想化された圧縮関数(FILRO)を用いた場合に、ランダムオラクルといわゆる強識別不可能である。
理想化された圧縮関数(FILRO)とは、以下の1,2が与えられた圧縮関数である。
1.(リスト):全ての入力値と、各入力値に対してランダムに選択した出力値とのペアを記録したリストを持つ。
2.(順方向の値を出力するオラクル):入力値(x,y)に対し、リストから入力に対する出力値zを検索して、値zを出力する。つまり、f1(x,y)=zとなる値zを出力する。
【0017】
また、背景技術として記載したように、理想化された圧縮関数(FILRO)ではなく、一方向性が破られた理想的な圧縮関数(WFILRO)を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能であるハッシュ関数がある(非特許文献1,2参照)。
一方向性が破られた理想的な圧縮関数(WFILRO)とは、1−5が与えられた圧縮関数である。
1.(リスト):全ての入力値と、各入力値に対してランダムに選択した出力値とのペアを記録したリストを持つ。
2.(順方向の値を出力するオラクル):入力値(x,y)に対し、リストから入力に対する出力値zを検索して、値zを出力する。つまり、f1(x,y)=zとなる値zを出力する。
3.(一方向性を破るオラクル1):入力値zに対して、f1(x,y)=zを満たす全ての値(x,y)のペアからランダムに1つのペア選択して、選択したペアを出力する。
4.(一方向性を破るオラクル2):入力値x,zに対して、f1(x,y)=zを満たす全ての値yからランダムに1つの値を選択して、選択した値を出力する。入力値x,zに対して、f1(x,y)=zを満たす値yが存在しない場合は、識別情報⊥を出力する。
5.(一方向性を破るオラクル3):入力値y,zに対して、f1(x,y)=zを満たす全ての値xからランダムに1つの値を選択して、選択した値を出力する。入力値y,zに対して、f1(x,y)=zを満たす値xが存在しない場合は、識別情報⊥を出力する。
【0018】
一方向性が破られた理想的な圧縮関数(WFILRO)とは、理想化された圧縮関数(FILRO)に加え、さらに上記3−5が与えられた圧縮関数である。理想化された圧縮関数(FILRO)に比べ、一方向性が破られた理想的な圧縮関数(WFILRO)の方が、上記3−5が与えられた分、安全性が低い圧縮関数であると言える。
例えば、攻撃者Aがいた場合、理想化された圧縮関数(FILRO)であれば、攻撃者Aが上記1,2のみを用いることができる状態であり、一方向性が破られた理想的な圧縮関数(WFILRO)であれば、攻撃者Aが上記1−5を用いることができる状態である。すなわち、理想化された圧縮関数(FILRO)に比べ、一方向性が破られた理想的な圧縮関数(WFILRO)の方が、攻撃者Aに与えられる機能が多い分、攻撃者Aはより容易に攻撃することができる。そのため、理想化された圧縮関数(FILRO)に比べ、一方向性が破られた理想的な圧縮関数(WFILRO)の方が、上記3−5が与えられた分、安全性が低い圧縮関数であると言える。
【0019】
安全性の低い圧縮関数を用いて構成した場合であっても、ランダムオラクルと強識別不可能であるハッシュ関数は、安全性の高い圧縮関数を用いて構成した場合にのみ、ランダムオラクルと強識別不可能であるハッシュ関数よりも、ハッシュ関数の構成として、安全性の観点から優れていると言える。
つまり、一方向性が破られた理想的な圧縮関数(WFILRO))を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能であるハッシュ関数の方が、理想化された圧縮関数(FILRO)を用いて構成した場合にのみ、ランダムオラクルといわゆる強識別不可能であるハッシュ関数よりも、ハッシュ関数の構成として、安全性の観点から優れていると言える。
【0020】
以下の実施の形態において、非特許文献1,2に記載されたジッパーハッシュ関数とダブルパイプハッシュ関数と同様に、一方向性が破られた理想的な圧縮関数(WFILRO))を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置10について説明する。特に、非特許文献1,2に記載されたジッパーハッシュ関数とダブルパイプハッシュ関数よりも、効率的に計算可能なハッシュ関数を構成するハッシュ値演算装置10について説明する。
【0021】
また、以下の実施の形態において、一方向性が破られた理想的な圧縮関数(WFILRO)のうち、5.(一方向性を破るオラクル3)が与えられていない圧縮関数(以下、準一方向性が破られた理想的な圧縮関数と呼ぶ)を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置10について説明する。
準一方向性が破られた理想的な圧縮関数は、一方向性が破られた理想的な圧縮関数(WFILRO)よりも安全性が高い圧縮関数である。そのため、準一方向性が破られた理想的な圧縮関数を用いて構成した場合に、ランダムオラクルといわゆる強識別不可能であるハッシュ関数よりも、一方向性が破られた理想的な圧縮関数(WFILRO))を用いて構成した場合に、ランダムオラクルといわゆる強識別不可能であるハッシュ関数の方が、ハッシュ関数の構成として、安全性の観点から優れていると言える。しかし、準一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能であるハッシュ関数は、理想的な圧縮関数(FILRO))を用いて構成した場合にのみ、ランダムオラクルといわゆる強識別不可能であるハッシュ関数よりも、ハッシュ関数の構成として、安全性の観点から優れていると言える。そこで、以下の実施の形態では、準一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置10についても説明する。
【0022】
まず、実施の形態1−3で、一方向性が破られた理想的な圧縮関数(WFILRO))を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である3つの新たなハッシュ関数を構成するハッシュ値演算装置10について説明する。
次に、実施の形態4,5で、準一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である2つの新たなハッシュ関数を構成するハッシュ値演算装置10について説明する。
【0023】
なお、以下の実施の形態において、圧縮関数hは、nビットの値とmビットの値との2つの値が入力された場合にnビットの値を出力する圧縮関数である。ここで、mは所定の自然数であり、nはmよりも小さい自然数である。
【0024】
また、以下の説明において、処理装置は後述するCPU911、演算回路等である。記憶装置は後述するROM913、RAM914(メモリ,キャッシュメモリ)、磁気ディスク920等である。入力装置は後述するキーボード902、通信ボード915等である。出力装置は後述するRAM914、磁気ディスク920、通信ボード915、LCD901等である。つまり、処理装置、記憶装置、入力装置、出力装置はハードウェアである。また、記憶装置とは、上記の通り、RAM914(メモリ,キャッシュメモリ)等を含むものであるから、以下の説明において記憶装置に記憶するとは、RAM914(メモリ,キャッシュメモリ)に一時記憶することを意味する場合もある。
【0025】
実施の形態1.
実施の形態1では、一方向性が破られた理想的な圧縮関数(WFILRO))を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置10について説明する。
【0026】
図1は、実施の形態1に係るハッシュ値演算装置10の機能を示す機能ブロック図である。
図2は、図1に示すハッシュ値演算装置10の動作を示すフローチャートである。
図3は、図1に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0027】
図1に示すハッシュ値演算装置10の機能と動作について説明する。
図1に示すハッシュ値演算装置10は、既定長値入力部11、固定値付加部12、圧縮関数計算部13、出力部14を備える。
【0028】
(S101:既定長値入力ステップ)
既定長値入力部11は、m−nビット長のi個の値p[1],...,値p[i]を入力装置により入力して記憶装置に記憶する。
【0029】
(S102:固定値付加ステップ)
固定値付加部12は、(S101)で入力されたm−nビット長のi個の値p[1],...,値p[i]のうち、i−1個の値p[1],...,値p[i−1]のそれぞれに対して、予め記憶装置に記憶したnビット長の固定値const[1],...,固定値const[i−1]を付加して、mビット長の値x[1],...,値x[i−1]を処理装置により生成して記憶装置に記憶する。
つまり、固定値付加部12は、値p[1]に固定値const[1]を付加して、値x[1]を生成する。固定値付加部12は、値p[2]に固定値const[2]を付加して、値x[2]を生成する。以下同様に、j=3,...,i−1に対して、固定値付加部12は、値p[j]に固定値const[j]を付加して、値x[j]を生成する。
なお、j=1,...,i−1について、値p[j]に固定値const[j]を付加する位置は、どこであってもよい。つまり、固定値const[j]は、値p[j]の前や後に追加してもよいし、値p[j]の間に挿入してもよい。
また、固定値const[1]=固定値const[2]=...=固定値const[i−1]でもよいし、固定値const[1]≠固定値const[2]≠...≠固定値const[i−1]でもよい。
【0030】
(S103:第1圧縮関数計算ステップ)
圧縮関数計算部13は、予め記憶装置に記憶したnビット長の固定値IV1と、(S102)で生成されたmビット長の値x[1]とを圧縮関数hの入力として、c[1]=h(IV1,x[1])を処理装置により計算してnビット長の値c[1]を得て記憶装置に記憶する。
【0031】
(S104:第2圧縮関数計算ステップ)
圧縮関数計算部13は、j=2からi−1まで順に、nビット長の値c[j−1]とmビット長の値x[j]とを圧縮関数hの入力として、c[j]=h(c[j−1],x[j])を処理装置により計算してnビット長の値c[j]を得て記憶装置に記憶する。
つまり、まず、圧縮関数計算部13は、(S103)で計算したnビット長の値c[1]と、(S102)で生成されたmビット長の値x[2]とを入力として、c[2]=h(c[1],x[2])を処理装置により計算して値c[2]を得る。
次に、圧縮関数計算部13は、計算したnビット長の値c[2]と、(S102)で生成されたmビット長の値x[3]とを入力として、c[3]=h(c[2],x[3])を処理装置により計算してnビット長の値c[3]を得る。
これを繰り返して、最終的に、圧縮関数計算部13は、計算したnビット長の値c[i−2]と、(S102)で生成されたmビット長の値x[i−1]とを入力として、c[i−1]=h(c[i−2],x[i−1])を処理装置により計算してnビット長の値c[i−1]を得る。
【0032】
(S105:第3圧縮関数計算ステップ)
圧縮関数計算部13は、予め記憶装置に記憶したnビット長の固定値IV2と、m−nビット長の値p[i]に(S104)で計算したnビット長の値c[i−1]を付加したmビット長の値x[i]とを圧縮関数hの入力として、c[i]=h(IV2,x[i])を処理装置により計算して値c[i]を得て記憶装置に記憶する。
なお、値p[i]に値c[i−1]を付加する位置は、どこであってもよい。つまり、値c[i−1]は、値p[i]の前や後に追加してもよいし、値p[i]の間に挿入してもよい。
【0033】
(S106:出力ステップ)
出力部14は、(S105)で計算された値c[i]を出力装置により出力する。
【0034】
なお、i=2の場合、つまり(S101)で2個の値p[1]と値p[2]とのみが入力された場合には、(S104)は実行されない。つまり、(S103)で値c[1]を得た後、(S105)で固定値IV2と、値p[2]に値c[1]を付加した値x[2]とを入力として、値c[2]を得る。そして、(S106)で値c[2]を出力する。
【0035】
また、i=1の場合、つまり(S101)で1個の値p[1]のみが入力された場合には、(S102)から(S104)までは実行されない。つまり、(S101)で値p[1]が入力された後、(S105)で固定値IV2と、値p[1]に固定値IV1を付加した値x[1]とを入力として、値c[1]を得る。そして、(S106)で値c[1]を出力する。
【0036】
以上をまとめると、次のようになる。
まず、ハッシュ値演算装置10は、j=1からi−1まで順に、c[j]=h(c[j−1],p[j]||const[j])を計算する。ここで、c[0]は、IV1とする。
次に、ハッシュ値演算装置10は、c[i]=h(IV2,p[i]||c[i−1])を計算する。
そして、ハッシュ値演算装置10は、値c[i]を出力する。
【0037】
上記説明では、(S101)で既定長値入力部11が、m−nビット長のi個の値p[1],...,値p[i]を入力するとした。しかし、通常、ハッシュ関数へ入力される値は、1個の任意ビット長の値である。つまり、上記説明では、1個の任意ビット長の値が入力された場合に、どのようにm−nビット長のi個の値p[1],...,値p[i]を生成するのかについては説明を省略した。
次に、任意ビット長の値が入力された場合に、m−nビット長のi個の値p[1],...,値p[i]を生成する機能を追加したハッシュ値演算装置10について説明する。
【0038】
図4は、図1に示すハッシュ値演算装置10に、任意ビット長の値が入力された場合に、m−nビット長のi個の値p[1],...,値p[i]を生成する機能を追加したハッシュ値演算装置10の機能を示す機能ブロック図である。
図5は、図4に示すハッシュ値演算装置10の動作を示すフローチャートである。
図6は、図4に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0039】
図4に示すハッシュ値演算装置10の機能と動作について説明する。
図4に示すハッシュ値演算装置10は、図1に示すハッシュ値演算装置10が備える機能に加え、任意長値入力部15、パディング部16、分割部17を備える。
【0040】
(S111:任意長値入力ステップ)
任意長値入力部15は、任意ビット長の値Mを入力装置により入力する。
【0041】
(S112:パディングステップ)
パディング部16は、(S111)で入力された値Mに対して、パディング関数padを用いて、所定の値を付加してm−nビット長のi倍のビット長の値M’を処理装置により生成して記憶装置に記憶する。つまり、パディング部16は、M’=pad(M)を処理装置により計算して値M’を得る。
【0042】
(S113:分割ステップ)
分割部17は、(S112)で生成された値M’を処理装置によりi個に分割して、m−nビット長の値p[1],...,値p[i]を生成して記憶装置に記憶する。つまり、分割部17は、M’=p[1]||...||p[i]を処理装置により計算して値p[1],...,値p[i]を得る。
【0043】
(S114:既定長値入力ステップ)
既定長値入力部11は、(S113)で生成された値p[1],...,値p[i]を入力装置により入力する。
【0044】
(S115)から(S119)までの処理は、(S102)から(S106)までの処理と同一である。
【0045】
(S112)におけるパディング方法の一例を説明する。
図7は、以下に説明するパディング処理を行う場合の図4に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
(S112)でパディング部16は、(S111)で入力された値Mに対して、“1||0・・・0||<M>を付加して、m−nビット長のi倍のビット長の値M’を処理装置により生成する。ここで、<M>は、Mのビット長|M|の64ビット表現である。
つまり、パディング部16は、先頭が“1”で、その後が複数の“0”で、最後に<M>となるビット列を生成して、値Mに付加して、値M’を生成する。
なお、上記説明では、m−nビット長のi倍のビット長になるようにパディングすると説明した。しかし、予めiの値を決めておくのではなく、iの値は、入力された任意ビット長の値Mに応じて決定されるとしてもよい。例えば、上記パディング方法であれば、最少の0の個数で、m−nビット長の倍数のビット長となるようにパディングし、パディングをした結果得られた値M’のビット長がm−nビット長の何倍かをiの値としてもよい。
【0046】
パディングの方法は、例えば、全て“0”を付加する方法や、全て“1”を付加する方法等、どのような方法であっても構わない。しかし、上記説明のように、パディングして値M’を生成することにより、衝突困難性を高くすることができる。
【0047】
次に、図4に示すハッシュ値演算装置10の圧縮関数としてSHA−256(Secure Hash Algorithm−256)を用いた場合の例を説明する。なお、SHA−256の圧縮関数をSHA256と呼ぶ。SHA256は、256ビット長の値と512ビット長の値との2つの値が入力された場合に、256ビット長の値を出力する関数である。
図8は、圧縮関数としてSHA−256を用いる場合の図4に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0048】
(S111)では、任意長値入力部15は、任意ビット長の値Mを入力する。
(S112)では、パディング部16は、(S111)で入力された値Mに対して、パディング関数padを用いて、所定の値を付加して256(=512−256)ビット長のi倍のビット長の値M’を生成する。
(S113)では、分割部17は、(S112)で生成された値M’をi個に分割して、256ビット長の値p[1],...,値p[i]を生成する。
(S114)では、既定長値入力部11は、(S113)で生成された256ビット長のi個の値p[1],...,値p[i]を入力する。
(S115)では、固定値付加部12は、(S114)で入力された256ビット長のi個の値p[1],...,値p[i]のうち、i−1個の値p[1],...,値p[i−1]のそれぞれに対して、256ビット長の固定値const[1],...,固定値const[i−1]を付加して、512ビット長の値x[1],...,値x[i−1]を生成する。
(S116)では、圧縮関数計算部13は、256ビット長の固定値IV1と、(S115)で生成された512ビット長の値x[1]を圧縮関数hの入力として、c[1]=h(IV1,x[1])を計算して256ビット長の値c[1]を得る。
(S117)では、圧縮関数計算部13は、j=2からi−1まで順に、256ビット長の値c[j−1]と512ビット長の値x[j]とを圧縮関数hの入力として、c[j]=h(c[j−1],x[j])を計算して256ビット長の値c[j]を得る。
(S118)では、圧縮関数計算部13は、256ビット長の固定値IV2と、256ビット長の値p[i]に256ビット長の値c[i−1]を付加した512ビット長の値x[i]とを圧縮関数hの入力として、c[i]=h(IV2,x[i])を計算して値c[i]を得る。
(S119)では、出力部14は、(S118)で計算された値c[i]を出力する。
【0049】
実施の形態1に係るハッシュ値演算装置10により構成されたハッシュ関数は、圧縮関数hが一方向性が破られた理想的な圧縮関数の場合であっても、ランダムオラクルと強識別不可能性を満たすハッシュ関数となる。
【0050】
なお、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。なお、ストリーム処理とは、入力された先頭のビットから到着順に処理を行う方法であり、並列処理の一類型である。
【0051】
また、上記説明では、圧縮関数計算部13は所定の入力値に対して、処理装置により圧縮関数hを計算して、圧縮関数hを計算した結果を得るとした。しかし、圧縮関数計算部13は、ハッシュ値演算装置10の外部に備える圧縮関数計算装置に入力値を入力して、圧縮関数計算装置に圧縮関数hを計算させることにより、圧縮関数hを計算した結果を得てもよい。
【0052】
また、圧縮関数計算部13が値c[1],...,値c[i]を計算するのに用いる圧縮関数hは、同一の圧縮関数hであってもよいし、それぞれ異なる圧縮関数hであってもよい。
【0053】
つまり、実施の形態1に係るハッシュ値演算装置10をまとめると次のようになる。
ハッシュ値演算装置10は、i個のm−nビットの入力値p[1],...,p[i]に対して、圧縮関数演算装置に、nビット固定値IV1、第1メッセージp[1]、nビット固定値const[1]を入力し、その出力c[1]を得る。次に、圧縮関数演算装置に、nビット値c[1]、第2メッセージp[2]、nビット固定値const[2]を入力し、その出力c[2]を得る。この処理を、第i−1メッセージまで同様に行い、その出力値c[i−1]を得る。圧縮関数演算装置に、初期値IV2、i番目のメッセージp[i]、nビット値c[i−1]を入力し、その出力c[i]を得る。そして、c[i]を出力することを特徴とする。
【0054】
また、ハッシュ値演算装置10は、任意長の値Mから、任意長の値を入力とし、長さがm−nの倍数の値を出力する任意のパディング処理装置を用いて、m−nビットの倍数となるメッセージM’を生成する。そして、分割処理装置を用いてM’をi個のm−nビットの値p[1],...,p[i]に分割することを特徴とする。
【0055】
さらに、ハッシュ値演算装置10は、パディング処理装置を、M||1||0...0||<M>とすることを特徴とする。但し、<M>はMのビット長を64ビットで表したものである。
【0056】
また、さらに、ハッシュ値演算装置10は、圧縮関数演算装置として、SHA−256の圧縮関数演算装置を用いたことを特徴とする。
【0057】
実施の形態2.
実施の形態2では、実施の形態1とは異なるハッシュ関数であって、一方向性が破られた理想的な圧縮関数(WFILRO))を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置10について説明する。
【0058】
図9は、実施の形態2に係るハッシュ値演算装置10の機能を示す機能ブロック図である。
図10は、図9に示すハッシュ値演算装置10の動作を示すフローチャートである。
図11は、図9に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0059】
図9に示すハッシュ値演算装置10の機能と動作について説明する。
図9に示すハッシュ値演算装置10は、既定長値入力部11、固定値付加部12、圧縮関数計算部13、出力部14、排他的論理和計算部18を備える。
【0060】
(S201:既定長値入力ステップ)
既定長値入力部11は、m−sビット長のi個の値p[1],...,値p[i]を入力装置により入力して記憶装置に記憶する。
【0061】
(S202:排他的論理和計算ステップ)
排他的論理和計算部18は、(S201)で入力されたm−sビット長の値p[1],...,p[i]と、予め記憶装置に記憶したm−sビット長の固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを処理装置により計算してm−sビット長の値sumを得て記憶装置に記憶する。
【0062】
(S203:固定値付加ステップ)
固定値付加部12は、(S201)で入力されたm−sビット長のi個の値p[1],...,値p[i]のそれぞれに対して、予め記憶装置に記憶したsビット長の固定値const[1],...,固定値const[i]を付加して、mビット長の値x[1],...,値x[i]を処理装置により生成して記憶装置に記憶する。
つまり、固定値付加部12は、値p[1]に固定値const[1]を付加して、値x[1]を生成する。固定値付加部12は、値p[2]に固定値const[2]を付加して、値x[2]を生成する。以下同様に、j=3,...,iに対して、固定値付加部12は、値p[j]に固定値const[j]を付加して、値x[j]を生成する。
なお、j=1,...,i−1について、値p[j]に固定値const[j]を付加する位置は、どこであってもよい。つまり、固定値const[j]は、値p[j]の前や後に追加してもよいし、値p[j]の間に挿入してもよい。
また、固定値const[1]≠固定値const[2]≠...≠固定値const[i]である。例えば、j=1,...,iについて、固定値const[j]は、jをsビットで表現した値<j>である。
【0063】
(S204:第1圧縮関数計算ステップ)
圧縮関数計算部13は、予め記憶装置に記憶したnビット長の固定値IV1と、(S203)で生成されたmビット長の値x[1]を圧縮関数hの入力として、c[1]=h(IV1,x[1])を処理装置により計算してnビット長の値c[1]を得て記憶装置に記憶する。
【0064】
(S205:第2圧縮関数計算ステップ)
圧縮関数計算部13は、j=2からiまで順に、nビット長の値c[j−1]とmビット長の値x[j]とを圧縮関数hの入力として、c[j]=h(c[j−1],x[j])を処理装置により計算してnビット長の値c[j]を得て記憶装置に記憶する。
つまり、まず、圧縮関数計算部13は、(S204)で計算したnビット長の値c[1]と、(S203)で生成されたmビット長の値x[2]とを入力として、c[2]=h(c[1],x[2])を処理装置により計算してnビット長の値c[2]を得る。
次に、圧縮関数計算部13は、計算したnビット長の値c[2]と、(S203)で生成されたmビット長の値x[3]とを入力として、c[3]=h(c[2],x[3])を処理装置により計算してnビット長の値c[3]を得る。
これを繰り返して、最終的に、圧縮関数計算部13は、計算したnビット長の値c[i−1]と、(S203)で生成されたmビット長の値x[i]とを入力として、c[i]=h(c[i−1],x[i])を処理装置により計算してnビット長の値c[i]を得る。
【0065】
(S206:第3圧縮関数計算ステップ)
圧縮関数計算部13は、(S205)で計算したnビット長の値c[i]と、(S202)で計算されたm−sビット長の値sumにsビット長の固定値const[i+1]を付加したmビット長の値x[i+1]とを圧縮関数hの入力として、c[i+1]=h(c[i],x[i+1])を処理装置により計算してnビット長の値c[i+1]を得て記憶装置に記憶する。
なお、固定値const[i+1]≠固定値const[1]≠...≠固定値const[i]である。例えば、固定値const[i+1]は、i+1をsビットで表現した値<i+1>である。
また、値sumに固定値const[i+1]を付加する位置は、どこであってもよい。つまり、固定値const[i+1]は、値sumの前や後に追加してもよいし、値sumの間に挿入してもよい。
【0066】
(S207:第4圧縮関数計算ステップ)
圧縮関数計算部13は、予め記憶装置に記憶したnビット長の固定値IV2と、(S206)で計算したnビット長の値c[i+1]にm−nビット長の固定値const[i+2]を付加した値x[i+2]とを圧縮関数hの入力として、c[i+2]=h(IV2,x[i+2])を処理装置により計算してnビット長の値c[i+2]を得て記憶装置に記憶する。
なお、値c[i+1]に固定値const[i+2]を付加する位置は、どこであってもよい。つまり、固定値const[i+2]は、値c[i+1]の前や後に追加してもよいし、値c[i+1]の間に挿入してもよい。
また、例えば、固定値const[i+2]は、m−n−sビット長の固定値constと、i+2をsビットで表現した値<i+2>との2つの値であってもよい。固定値const[i+2]が固定値constと<i+2>とである場合には、どのように値c[i+1]に固定値constと<i+2>とを付加してもよい。例えば、x[i+2]=<i+2>||const||c[i+1]としてもよい。
【0067】
(S208:出力ステップ)
出力部14は、(S207)で計算された値c[i+2]を出力装置により出力する。
【0068】
なお、i=1の場合、つまり(S201)で1個の値p[1]のみが入力された場合には、(S205)は実行されない。つまり、(S204)で値c[1]を得た後、(S206)で値c[1]と、値sumに固定値const[2]を付加した値x[2]とを入力として、値c[2]を得る。そして、(S207)へ進む。
【0069】
以上をまとめると、次のようになる。
まず、ハッシュ値演算装置10は、sum=p[1] xor,...,xor p[i] xor yを処理装置により計算する。
また、ハッシュ値演算装置10は、j=1からiまで順に、c[j]=h(c[j−1],p[j]||<j>)を計算する。ここで、c[0]は、IV1とする。
次に、ハッシュ値演算装置10は、c[i+1]=h(c[i],sum||<i+1>)を計算する。
次に、ハッシュ値演算装置10は、c[i+2]=h(IV,c[i+1]||const||<i+2>)を計算する。
そして、ハッシュ値演算装置10は、値c[i+2]を出力する。
【0070】
上記説明では、(S201)で既定長値入力部11が、m−sビット長のi個の値p[1],...,値p[i]を入力するとした。しかし、通常、ハッシュ関数へ入力される値は、1個の任意ビット長の値である。つまり、上記説明では、1個の任意ビット長の値が入力された場合に、どのようにm−sビット長のi個の値p[1],...,値p[i]を生成するのかについては説明を省略した。
次に、任意ビット長の値が入力された場合に、m−sビット長のi個の値p[1],...,値p[i]を生成する機能を追加したハッシュ値演算装置10について説明する。
【0071】
図12は、図9に示すハッシュ値演算装置10に、任意ビット長の値が入力された場合に、m−sビット長のi個の値p[1],...,値p[i]を生成する機能を追加したハッシュ値演算装置10の機能を示す機能ブロック図である。
図13は、図12に示すハッシュ値演算装置10の動作を示すフローチャートである。
図14は、図12に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0072】
図12に示すハッシュ値演算装置10の機能と動作について説明する。
図12に示すハッシュ値演算装置10は、図9に示すハッシュ値演算装置10が備える機能に加え、任意長値入力部15、パディング部16、分割部17を備える。
【0073】
(S211:任意長値入力ステップ)
任意長値入力部15は、任意ビット長の値Mを入力装置により入力する。
【0074】
(S212:パディングステップ)
パディング部16は、(S211)で入力された値Mに対して、パディング関数padを用いて、所定の値を付加してm−sビット長のi倍のビット長の値M’を処理装置により生成して記憶装置に記憶する。つまり、パディング部16は、M’=pad(M)を処理装置により計算して値M’を得る。
【0075】
(S213:分割ステップ)
分割部17は、(S212)で生成された値M’を処理装置によりi個に分割して、m−sビット長の値p[1],...,値p[i]を生成して記憶装置に記憶する。つまり、分割部17は、M’=p[1]||...||p[i]を処理装置により計算して値p[1],...,値p[i]を得る。
【0076】
(S214:既定長値入力ステップ)
既定長値入力部11は、(S213)で生成された値p[1],...,値p[i]を入力装置により入力する。
【0077】
(S215)から(S221)までの処理は、(S202)から(S208)までの処理と同一である。
【0078】
(S212)におけるパディング方法の一例を説明する。
図15は、以下に説明するパディング処理を行う場合の図12に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
(S212)でパディング部16は、実施の形態1で説明した(S112)におけるパディング方法と同様に、(S211)で入力された値Mに対して、“1||0・・・0||<M>を付加して、m−sビット長のi倍のビット長の値M’を処理装置により生成する。ここで、<M>は、Mのビット長|M|の64ビット表現である。
このように、パディングして値M’を生成することにより、衝突困難性を高くすることができる。
【0079】
図16は、以下に説明するパディング処理を行う場合の図12に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
(S212)でパディング部16は、(S211)で入力された値Mに対して、“1||0・・・0を付加して、m−sビット長のi倍のビット長の値M’を処理装置により生成する。
このように、パディングして値M’を生成しても、衝突困難性を高くすることができる。
【0080】
なお、実施の形態1と同様に、予めiの値を決めておくのではなく、iの値は、入力された任意ビット長の値Mに応じて決定されるとしてもよい。
【0081】
次に、図12に示すハッシュ値演算装置10の圧縮関数としてSHA−256を用いた場合の例を説明する。なお、SHA−256の圧縮関数をSHA256と呼ぶ。SHA256は、256ビット長の値と512ビット長の値との2つの値が入力された場合に、256ビット長の値を出力する関数である。
図17は、圧縮関数としてSHA−256を用いる場合の図12に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
なお、以下の説明では、値sを56として説明する。
【0082】
(S211)では、任意長値入力部15は、任意ビット長の値Mを入力する。
(S212)では、パディング部16は、(S211)で入力された値Mに対して、パディング関数padを用いて、所定の値を付加して456(=512−56)ビット長のi倍のビット長の値M’を生成する。
(S213)では、分割部17は、(S212)で生成された値M’をi個に分割して、456ビット長の値p[1],...,値p[i]を生成する。
(S214)では、既定長値入力部11は、(S213)で生成された456ビット長の値p[1],...,値p[i]を入力する。
(S215)では、排他的論理和計算部18は、(S214)で入力された456ビット長の値p[1],...,p[i]と、456ビット長の固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算して456ビット長の値sumを得る。
(S216)では、固定値付加部12は、(S211)で入力された456ビット長の値p[1],...,値p[i]のそれぞれに対して、56ビット長の固定値const[1],...,固定値const[i]を付加して、512ビット長の値x[1],...,値x[i]を生成する。
(S217)では、圧縮関数計算部13は、256ビット長の固定値IV1と、(S216)で生成された512ビット長の値x[1]を圧縮関数hの入力として、c[1]=h(IV1,x[1])を計算して256ビット長の値c[1]を得る。
(S218)では、圧縮関数計算部13は、j=2からiまで順に、256ビット長の値c[j−1]と512ビット長の値x[j]とを圧縮関数hの入力として、c[j]=h(c[j−1],x[j])を計算して256ビット長の値c[j]を得る。
(S219)では、圧縮関数計算部13は、(S218)で計算した256ビット長の値c[i]と、(S215)で計算された456ビット長の値sumに56ビット長の固定値const[i+1]を付加した512ビット長の値x[i+1]とを圧縮関数hの入力として、c[i+1]=h(c[i],x[i+1])を計算して256ビット長の値c[i+1]を得る。
(S220)では、圧縮関数計算部13は、256ビット長の固定値IV2と、(S215)で計算した256ビット長の値c[i+1]に256ビット長の固定値const[i+2]を付加した値x[i+2]とを圧縮関数hの入力として、c[i+2]=h(IV2,x[i+2])を計算して256ビット長の値c[i+2]を得る。
(S221)では、出力部14は、(S220)で計算された値c[i+2]を出力する。
【0083】
実施の形態2に係るハッシュ値演算装置10により構成されたハッシュ関数は、圧縮関数hが一方向性が破られた理想的な圧縮関数の場合であっても、ランダムオラクルと強識別不可能性を満たすハッシュ関数となる。
【0084】
なお、実施の形態1と同様に、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。
【0085】
また、実施の形態1と同様に、圧縮関数計算部13は、ハッシュ値演算装置10の外部に備える圧縮関数計算装置に入力値を入力して、圧縮関数計算装置に圧縮関数hを計算させることにより、圧縮関数hを計算した結果を得てもよい。
また、同様に、排他的論理和計算部18は、ハッシュ値演算装置10の外部に備える排他的論理和計算装置に入力値を入力して、排他的論理和計算装置に排他的論理和演算を計算させることにより、排他的論理和演算を計算した結果を得てもよい。
【0086】
また、圧縮関数計算部13が値c[1],...,値c[i+2]を計算するのに用いる圧縮関数hは、同一の圧縮関数hであってもよいし、それぞれ異なる圧縮関数hであってもよい。
【0087】
つまり、実施の形態2に係るハッシュ値演算装置10をまとめると次のようになる。
ハッシュ値演算装置10は、i個のm−sビットの入力値p[1],...,p[i]に対して、圧縮関数演算装置に、nビット固定値IV1、第1メッセージp[1]、1のsビット表現値を入力し、その出力c[1]を得る。次に、圧縮関数演算装置に、nビット値c[1]、第2メッセージp[2]、2のsビット表現値を入力し、その出力c[2]を得る。この処理を、第iメッセージまで同様に行い、その出力値c[i]を得る。圧縮関数演算装置に、nビット値c[i]、sum=p[1] xor ... xor p[i] xor y、i+1のsビットの表現値を入力し、その出力c[i+1]を得る。圧縮関数演算装置に、初期値IV2、nビット値c[i−1]、m−n−sビット固定値const、i+2のsビット表現値を入力し、その出力c[i+2]を得る。そして、c[i+2]を出力することを特徴とする。ここで、yはm−sビット固定値である。
【0088】
また、ハッシュ値演算装置10は、任意長の値Mから、任意長の値を入力とし、m−sビットの値を出力する任意のパディング処理装置を用いて、m−sビットの倍数となるメッセージM’を生成する。分割処理装置を用いてM’をi個のm−sビットの値p[1],...,p[i]に分割することを特徴とする。
【0089】
さらに、ハッシュ値演算装置10は、パディング処理装置を、M||1||0...0||<M>とし、s=56とすることを特徴とする。但し、<M>はMのビット長を64ビットで表したものである。
【0090】
また、さらに、ハッシュ値演算装置10は、パディング処理装置を、M||1||0...0とし、s=56とすることを特徴とする。
【0091】
また、ハッシュ値演算装置10は、圧縮関数演算装置として、SHA−256の圧縮関数演算装置を用いたことを特徴とする。
【0092】
実施の形態3.
実施の形態3では、実施の形態1,2とは異なるハッシュ関数であって、一方向性が破られた理想的な圧縮関数(WFILRO))を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置10について説明する。
【0093】
図18は、実施の形態3に係るハッシュ値演算装置10の機能を示す機能ブロック図である。
図19は、図18に示すハッシュ値演算装置10の動作を示すフローチャートである。
図20は、図18に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0094】
図18に示すハッシュ値演算装置10の機能と動作について説明する。
図18に示すハッシュ値演算装置10は、既定長値入力部11、固定値付加部12、圧縮関数計算部13、出力部14、排他的論理和計算部18を備える。
【0095】
(S301:既定長値入力ステップ)
既定長値入力部11は、m−sビット長のi個の値p[1],...,値p[i]と、m−nビット長の1個の値p[i+1]との合計i+1個の値を入力装置により入力して記憶装置に記憶する。
【0096】
(S302:排他的論理和計算ステップ)
排他的論理和計算部18は、(S301)で入力されたm−sビット長のi個の値p[1],...,p[i]と、予め記憶装置に記憶したm−sビット長の固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを処理装置により計算してm−sビット長の値sumを得て記憶装置に記憶する。
【0097】
(S303:固定値付加ステップ)
固定値付加部12は、(S301)で入力されたm−sビット長のi個の値p[1],...,値p[i]のそれぞれに対して、予め記憶装置に記憶したsビット長の固定値const[1],...,固定値const[i]を付加して、mビット長の値x[1],...,値x[i]を処理装置により生成して記憶装置に記憶する。
つまり、固定値付加部12は、値p[1]に固定値const[1]を付加して、値x[1]を生成する。固定値付加部12は、値p[2]に固定値const[2]を付加して、値x[2]を生成する。以下同様に、j=3,...,iに対して、固定値付加部12は、値p[j]に固定値const[j]を付加して、値x[j]を生成する。
なお、j=1,...,i−1について、値p[j]に固定値const[j]を付加する位置は、どこであってもよい。つまり、固定値const[j]は、値p[j]の前や後に追加してもよいし、値p[j]の間に挿入してもよい。
また、固定値const[1]≠固定値const[2]≠...≠固定値const[i]である。例えば、j=1,...,iについて、固定値const[j]は、jをsビットで表現した値<j>である。
【0098】
(S304:第1圧縮関数計算ステップ)
圧縮関数計算部13は、予め記憶装置に記憶したnビット長の固定値IV1と、(S303)で生成されたmビット長の値x[1]を圧縮関数hの入力として、c[1]=h(IV1,x[1])を処理装置により計算してnビット長の値c[1]を得て記憶装置に記憶する。
【0099】
(S305:第2圧縮関数計算ステップ)
圧縮関数計算部13は、j=2からiまで順に、nビット長の値c[j−1]とmビット長の値x[j]とを圧縮関数hの入力として、c[j]=h(c[j−1],x[j])を処理装置により計算してnビット長の値c[j]を得て記憶装置に記憶する。
つまり、まず、圧縮関数計算部13は、(S304)で計算したnビット長の値c[1]と、(S303)で生成されたmビット長の値x[2]とを入力として、c[2]=h(c[1],x[2])を処理装置により計算してnビット長の値c[2]を得る。
次に、圧縮関数計算部13は、計算したnビット長の値c[2]と、(S303)で生成されたmビット長の値x[3]とを入力として、c[3]=h(c[2],x[3])を処理装置により計算してnビット長の値c[3]を得る。
これを繰り返して、最終的に、圧縮関数計算部13は、計算したnビット長の値c[i−1]と、(S303)で生成されたmビット長の値x[i]とを入力として、c[i]=h(c[i−1],x[i])を処理装置により計算してnビット長の値c[i]を得る。
【0100】
(S306:第3圧縮関数計算ステップ)
圧縮関数計算部13は、(S305)で計算したnビット長の値c[i]と、(S302)で計算されたm−sビット長の値sumにsビット長の固定値const[i+1]を付加したmビット長の値x[i+1]とを圧縮関数hの入力として、c[i+1]=h(c[i],x[i+1])を処理装置により計算してnビット長の値c[i+1]を得て記憶装置に記憶する。
なお、固定値const[i+1]≠固定値const[1]≠...≠固定値const[i]である。例えば、固定値const[i+1]は、i+1をsビットで表現した値<i+1>である。
また、値sumに固定値const[i+1]を付加する位置は、どこであってもよい。つまり、固定値const[i+1]は、値sumの前や後に追加してもよいし、値sumの間に挿入してもよい。
【0101】
(S307:第4圧縮関数計算ステップ)
圧縮関数計算部13は、予め記憶装置に記憶したnビット長の固定値IV2と、(S306)で計算したnビット長の値c[i+1]に(S301)で入力されたm−nビット長の値p[i+1]を付加した値x[i+2]とを圧縮関数hの入力として、c[i+2]=h(IV2,x[i+2])を処理装置により計算してnビット長の値c[i+2]を得て記憶装置に記憶する。
なお、値c[i+1]に値p[i+1]を付加する位置は、どこであってもよい。つまり、値p[i+1]は、値c[i+1]の前や後に追加してもよいし、値c[i+1]の間に挿入してもよい。
【0102】
(S308:出力ステップ)
出力部14は、(S307)で計算された値c[i+2]を出力装置により出力する。
【0103】
なお、i=1の場合、つまり(S301)で2個の値p[1](値p[i])と値p[2](値p[i+1])とのみが入力された場合には、(S305)は実行されない。つまり、(S304)で値c[1]を得た後、(S306)で値c[1]と、値sumに固定値const[2]を付加した値x[2]とを入力として、値c[2]を得る。そして、(S307)へ進む。
【0104】
以上をまとめると、次のようになる。
まず、ハッシュ値演算装置10は、sum=p[1] xor,...,xor p[i] xor yを処理装置により計算する。
また、ハッシュ値演算装置10は、j=1からiまで順に、c[j]=h(c[j−1],p[j]||<j>)を計算する。ここで、c[0]は、IV1とする。
次に、ハッシュ値演算装置10は、c[i+1]=h(c[i],sum||<i+1>)を計算する。
次に、ハッシュ値演算装置10は、c[i+2]=h(IV,c[i+1]||p[i+1])を計算する。
そして、ハッシュ値演算装置10は、値c[i+2]を出力する。
【0105】
上記説明では、(S301)で既定長値入力部11が、m−sビット長のi個の値p[1],...,値p[i]と、m−nビット長の1個の値p[i+1]とを入力するとした。しかし、通常、ハッシュ関数へ入力される値は、1個の任意ビット長の値である。つまり、上記説明では、1個の任意ビット長の値が入力された場合に、どのようにm−sビット長のi個の値p[1],...,値p[i]と、m−nビット長の1個の値p[i+1]とを生成するのかについては説明を省略した。
次に、任意ビット長の値が入力された場合に、m−sビット長のi個の値p[1],...,値p[i]と、m−nビット長の1個の値p[i+1]とを生成する機能を追加したハッシュ値演算装置10について説明する。
【0106】
図21は、図18に示すハッシュ値演算装置10に、任意ビット長の値が入力された場合に、m−sビット長のi個の値p[1],...,値p[i]と、m−nビット長の1個の値p[i+1]とを生成する機能を追加したハッシュ値演算装置10の機能を示す機能ブロック図である。
図22は、図21に示すハッシュ値演算装置10の動作を示すフローチャートである。
図23は、図21に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0107】
図21に示すハッシュ値演算装置10の機能と動作について説明する。
図21に示すハッシュ値演算装置10は、図18に示すハッシュ値演算装置10が備える機能に加え、任意長値入力部15、パディング部16、分割部17を備える。
【0108】
(S311:任意長値入力ステップ)
任意長値入力部15は、任意ビット長の値Mを入力装置により入力する。
【0109】
(S312:パディングステップ)
パディング部16は、(S311)で入力された値Mに対して、パディング関数padを用いて、所定の値を付加して((m−s)×i+(m−n))ビット長の値M’を処理装置により生成して記憶装置に記憶する。つまり、パディング部16は、M’=pad(M)を処理装置により計算して値M’を得る。
【0110】
(S313:分割ステップ)
分割部17は、(S312)で生成された値M’を処理装置によりi+1個に分割して、m−sビット長の値p[1],...,値p[i]と、m−nビット長の1個の値p[i+1]とを生成して記憶装置に記憶する。つまり、分割部17は、M’=p[1]||...||p[i]||p[i+1]を処理装置により計算して値p[1],...,値p[i]と、値p[i+1]とを得る。
【0111】
(S314:既定長値入力ステップ)
既定長値入力部11は、(S313)で生成された値p[1],...,値p[i]と、値p[i+1]とを入力装置により入力する。
【0112】
(S315)から(S321)までの処理は、(S302)から(S308)までの処理と同一である。
【0113】
(S312)におけるパディング方法の一例を説明する。
図24は、以下に説明するパディング処理を行う場合の図21に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
(S312)でパディング部16は、実施の形態1で説明した(S112)におけるパディング方法と同様に、(S311)で入力された値Mに対して、“1||0・・・0||<M>を付加して、m−sビット長のi倍のビット長の値M’を処理装置により生成する。ここで、<M>は、Mのビット長|M|の64ビット表現である。
このように、パディングして値M’を生成することにより、衝突困難性を高くすることができる。
【0114】
なお、実施の形態1と同様に、予めiの値を決めておくのではなく、iの値は、入力された任意ビット長の値Mに応じて決定されるとしてもよい。この場合、値M’のビット長|M’|が「|M’| mod m−s=m−n」となるように、値M’を生成すればよい。
【0115】
次に、図21に示すハッシュ値演算装置10の圧縮関数としてSHA−256を用いた場合の例を説明する。なお、SHA−256の圧縮関数をSHA256と呼ぶ。SHA256は、256ビット長の値と512ビット長の値との2つの値が入力された場合に、256ビット長の値を出力する関数である。
図25は、圧縮関数としてSHA−256を用いる場合の図12に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
なお、以下の説明では、値sを56として説明する。
【0116】
(S311)では、任意長値入力部15は、任意ビット長の値Mを入力する。
(S312)では、パディング部16は、(S311)で入力された値Mに対して、パディング関数padを用いて、所定の値を付加して((512−56)×i+(512−256))ビット長の値M’を生成する。
(S313)では、分割部17は、(S312)で生成された値M’をi個の456ビット長の値p[1],...,値p[i]と、1個の256ビット長の値p[i+1]とに分割する。
(S314)では、既定長値入力部11は、(S313)で生成されたi個の456ビット長の値p[1],...,値p[i]と、1個の256ビット長の値p[i+1]とを入力する。
(S315)では、排他的論理和計算部18は、(S314)で入力された456ビット長の値p[1],...,p[i]と、456ビット長の固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算して456ビット長の値sumを得る。
(S316)では、固定値付加部12は、(S311)で入力された456ビット長の値p[1],...,値p[i]のそれぞれに対して、56ビット長の固定値const[1],...,固定値const[i]を付加して、512ビット長の値x[1],...,値x[i]を生成する。
(S317)では、圧縮関数計算部13は、256ビット長の固定値IV1と、(S316)で生成された512ビット長の値x[1]を圧縮関数hの入力として、c[1]=h(IV1,x[1])を計算して256ビット長の値c[1]を得る。
(S318)では、圧縮関数計算部13は、j=2からiまで順に、256ビット長の値c[j−1]と512ビット長の値x[j]とを圧縮関数hの入力として、c[j]=h(c[j−1],x[j])を計算して256ビット長の値c[j]を得る。
(S319)では、圧縮関数計算部13は、(S318)で計算した256ビット長の値c[i]と、(S315)で計算された456ビット長の値sumに56ビット長の固定値const[i+1]を付加した512ビット長の値x[i+1]とを圧縮関数hの入力として、c[i+1]=h(c[i],x[i+1])を計算して256ビット長の値c[i+1]を得る。
(S320)では、圧縮関数計算部13は、256ビット長の固定値IV2と、(S315)で計算した256ビット長の値c[i+1]に、(S314)で入力された256ビット長の値p[i+1]を付加した値x[i+2]とを圧縮関数hの入力として、c[i+2]=h(IV2,x[i+2])を計算して256ビット長の値c[i+2]を得る。
(S321)では、出力部14は、(S320)で計算された値c[i+2]を出力する。
【0117】
実施の形態3に係るハッシュ値演算装置10により構成されたハッシュ関数は、圧縮関数hが一方向性が破られた理想的な圧縮関数の場合であっても、ランダムオラクルと強識別不可能性を満たすハッシュ関数となる。
【0118】
なお、実施の形態1と同様に、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。
【0119】
また、実施の形態1と同様に、圧縮関数計算部13は、ハッシュ値演算装置10の外部に備える圧縮関数計算装置に入力値を入力して、圧縮関数計算装置に圧縮関数hを計算させることにより、圧縮関数hを計算した結果を得てもよい。
また、同様に、排他的論理和計算部18は、ハッシュ値演算装置10の外部に備える排他的論理和計算装置に入力値を入力して、排他的論理和計算装置に排他的論理和演算を計算させることにより、排他的論理和演算を計算した結果を得てもよい。
【0120】
また、圧縮関数計算部13が値c[1],...,値c[i+2]を計算するのに用いる圧縮関数hは、同一の圧縮関数hであってもよいし、それぞれ異なる圧縮関数hであってもよい。
【0121】
つまり、実施の形態3に係るハッシュ値演算装置10をまとめると次のようになる。
ハッシュ値演算装置10は、i個のm−sビットの入力値m[1],…,m[i]とm−nビットの入力m[i+1]に対して、圧縮関数演算装置に、nビット固定値IV1、第一メッセージm[1]、1のsビット表現値を入力し、その出力c[1]を得る。次に、圧縮関数演算装置に、nビット値c[1]、第2メッセージm[2]、2のsビット表現値を入力し、その出力c[2]を得る。この処理を、第iメッセージまで同様に行い、その出力値c[i]を得る。圧縮関数演算装置に、nビット値c[i]、sum=m[1] xor … xor m[i] xor y、i+1のsビットの表現値を入力し、その出力c[i+1]を得る。圧縮関数演算装置に、初期値IV2、m−nビットのメッセージm[i+1]、nビット値c[i−1]を入力し、その出力c[i+2]を得る。そして、c[i+2]を出力することを特徴とする。ここで、yはm−sビット固定値である。
【0122】
また、ハッシュ値演算装置10は、任意長の値Mから、任意長の値を入力とし、任意のパディング処理装置を用いて、メッセージM’を生成する。ただし、|M’| mod m−s= m−nとなるようにする。分割処理装置を用いてM’をi個のm−sビットの値m[1],…,m[i]、m−nビットの値m[i]に分割することを特徴とする。
【0123】
さらに、ハッシュ値演算装置10は、パディング処理装置を、M||1||0…0||<M>とし、s=56とすることを特徴とする。但し、<M>はMのビット長を64ビットで表したものである。
【0124】
また、さらに、ハッシュ値演算装置10は、圧縮関数演算装置として、SHA−256の圧縮関数演算装置を用いたことを特徴とする。
【0125】
実施の形態4.
実施の形態4では、準一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置10について説明する。
【0126】
図26は、実施の形態4に係るハッシュ値演算装置10の機能を示す機能ブロック図である。
図27は、図26に示すハッシュ値演算装置10の動作を示すフローチャートである。
図28は、図26に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0127】
図26に示すハッシュ値演算装置10の機能と動作について説明する。
図26に示すハッシュ値演算装置10は、既定長値入力部11、固定値付加部12、圧縮関数計算部13、出力部14、置換関数計算部19を備える。
【0128】
(S401:既定長値入力ステップ)
既定長値入力部11は、m−nビット長のi個の値p[1],...,値p[i]を入力装置により入力して記憶装置に記憶する。
【0129】
(S402:固定値付加ステップ)
固定値付加部12は、(S401)で入力されたm−nビット長のi個の値p[1],...,値p[i]のそれぞれに対して、予め記憶装置に記憶したnビット長の固定値const[1],...,固定値const[i]を付加して、mビット長の値x[1],...,値x[i]を処理装置により生成して記憶装置に記憶する。
つまり、固定値付加部12は、値p[1]に固定値const[1]を付加して、値x[1]を生成する。固定値付加部12は、値p[2]に固定値const[2]を付加して、値x[2]を生成する。以下同様に、j=3,...,iに対して、固定値付加部12は、値p[j]に固定値const[j]を付加して、値x[j]を生成する。
なお、j=1,...,iについて、値p[j]に固定値const[j]を付加する位置は、どこであってもよい。つまり、固定値const[j]は、値p[j]の前や後に追加してもよいし、値p[j]の間に挿入してもよい。
また、固定値const[1]=固定値const[2]=...=固定値const[i]でもよいし、固定値const[1]≠固定値const[2]≠...≠固定値const[i]でもよい。
【0130】
(S403:第1圧縮関数計算ステップ)
圧縮関数計算部13は、予め記憶装置に記憶したnビット長の固定値IV1と、(S402)で生成されたmビット長の値x[1]を圧縮関数hの入力として、c[1]=h(IV1,x[1])を処理装置により計算してnビット長の値c[1]を得て記憶装置に記憶する。
【0131】
(S404:第2圧縮関数計算ステップ)
圧縮関数計算部13は、j=2からi−1まで順に、nビット長の値c[j−1]とmビット長の値x[j]とを圧縮関数hの入力として、c[j]=h(c[j−1],x[j])を処理装置により計算してnビット長の値c[j]を得て記憶装置に記憶する。
つまり、まず、圧縮関数計算部13は、(S403)で計算したnビット長の値c[1]と、(S402)で生成されたmビット長の値x[2]とを入力として、c[2]=h(c[1],x[2])を処理装置により計算してnビット長の値c[2]を得る。
次に、圧縮関数計算部13は、計算したnビット長の値c[2]と、(S402)で生成されたmビット長の値x[3]とを入力として、c[3]=h(c[2],x[3])を処理装置により計算してnビット長の値c[3]を得る。
これを繰り返して、最終的に、圧縮関数計算部13は、計算したnビット長の値c[i−2]と、(S402)で生成されたmビット長の値x[i−1]とを入力として、c[i−1]=h(c[i−2],x[i−1])を処理装置により計算してnビット長の値c[i−1]を得る。
【0132】
(S405:置換関数計算ステップ)
置換関数計算部19は、(S404)で計算されたnビット長の値c[i−1]を置換関数πの入力として、c’[i−1]=π(c[i−1])を処理装置により計算してnビット長の値c’[i−1]を得て記憶装置に記憶する。
なお、置換関数πは、任意の値aを入力した場合に値aとは異なる値a’に置換する置換関数であって、値aを入力した場合に入力した値aがそのまま出力されることのない置換関数である。つまり、置換関数πは、π(a)=aとなるような固定点(Fixed Point)を有さない置換関数である。
【0133】
(S406:第3圧縮関数計算ステップ)
圧縮関数計算部13は、(S405)で計算されたnビット長の値c’[i−1]と、(S402)で生成されたmビット長の値x[i]とを圧縮関数hの入力として、c[i]=h(c’[i−1],x[i])を処理装置により計算してnビット長の値c[i]を得て記憶装置に記憶する。
【0134】
(S407:出力ステップ)
出力部14は、(S406)で計算された値c[i]を出力装置により出力する。
【0135】
なお、i=2の場合、つまり(S401)で2個の値p[1]と値p[2]とのみが入力された場合には、(S404)は実行されない。つまり、(S403)で値c[1]を得た後、(S405)で値c[1]を入力として、値c’[1]を得る。そして、(S406)で値c’[1]と値x[2]とを入力として、値c[2]を得る。
【0136】
また、i=1の場合、つまり(S401)で1個の値p[1]のみが入力された場合には、(S403)と(S404)とは実行されない。つまり、(S402)で値x[1]が生成された後、(S405)で固定値IV1を入力として、値IV1’を得る。そして、(S406)で値IV1’と値x[1]とを入力として、値c[1]を得る。
【0137】
以上をまとめると、次のようになる。
まず、ハッシュ値演算装置10は、j=1からi−1まで順に、c[j]=h(c[j−1],p[j]||const[j])を計算する。ここで、c[0]は、IV1とする。
次に、ハッシュ値演算装置10は、c[i]=h(π(c[i−1]),p[i]||const[i])を計算する。
そして、ハッシュ値演算装置10は、値c[i]を出力する。
【0138】
上記説明では、(S401)で既定長値入力部11が、m−nビット長のi個の値p[1],...,値p[i]を入力するとした。しかし、通常、ハッシュ関数へ入力される値は、1個の任意ビット長の値である。つまり、上記説明では、1個の任意ビット長の値が入力された場合に、どのようにm−nビット長のi個の値p[1],...,値p[i]を生成するのかについては説明を省略した。
次に、任意ビット長の値が入力された場合に、m−nビット長のi個の値p[1],...,値p[i]を生成する機能を追加したハッシュ値演算装置10について説明する。
【0139】
図29は、図26に示すハッシュ値演算装置10に、任意ビット長の値が入力された場合に、m−nビット長のi個の値p[1],...,値p[i]を生成する機能を追加したハッシュ値演算装置10の機能を示す機能ブロック図である。
図30は、図29に示すハッシュ値演算装置10の動作を示すフローチャートである。
図31は、図29に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0140】
図29に示すハッシュ値演算装置10の機能と動作について説明する。
図29に示すハッシュ値演算装置10は、図1に示すハッシュ値演算装置10が備える機能に加え、任意長値入力部15、パディング部16、分割部17を備える。
【0141】
(S411:任意長値入力ステップ)
任意長値入力部15は、任意ビット長の値Mを入力装置により入力する。
【0142】
(S412:パディングステップ)
パディング部16は、(S411)で入力された値Mに対して、パディング関数padを用いて、所定の値を付加してm−nビット長のi倍のビット長の値M’を処理装置により生成して記憶装置に記憶する。つまり、パディング部16は、M’=pad(M)を処理装置により計算して値M’を得る。
【0143】
(S413:分割ステップ)
分割部17は、(S412)で生成された値M’を処理装置によりi個に分割して、m−nビット長の値p[1],...,値p[i]を生成して記憶装置に記憶する。つまり、分割部17は、M’=p[1]||...||p[i]を処理装置により計算して値p[1],...,値p[i]を得る。
【0144】
(S414:既定長値入力ステップ)
既定長値入力部11は、(S413)で生成された値p[1],...,値p[i]を入力装置により入力する。
【0145】
(S415)から(S420)までの処理は、(S402)から(S407)までの処理と同一である。
【0146】
(S412)におけるパディング方法の一例を説明する。
図32は、以下に説明する所定のパディング処理を行う場合の図29に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
(S412)でパディング部16は、(S411)で入力された値Mに対して、“1||0・・・0||<M>を付加して、m−nビット長のi倍のビット長の値M’を処理装置により生成する。ここで、<M>は、Mのビット長|M|の64ビット表現である。
このように、パディングして値M’を生成することにより、衝突困難性を高くすることができる。
【0147】
なお、実施の形態1と同様に、予めiの値を決めておくのではなく、iの値は、入力された任意ビット長の値Mに応じて決定されるとしてもよい。
【0148】
次に、図32に示すハッシュ値演算装置10の圧縮関数としてSHA−256を用いた場合の例を説明する。なお、SHA−256の圧縮関数をSHA256と呼ぶ。SHA256は、256ビット長の値と512ビット長の値との2つの値が入力された場合に、256ビット長の値を出力する関数である。
図33は、圧縮関数としてSHA−256を用いる場合の図29に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0149】
(S411)では、任意長値入力部15は、任意ビット長の値Mを入力する。
(S412)では、パディング部16は、(S411)で入力された値Mに対して、パディング関数padを用いて、所定の値を付加して256(=512−256)ビット長のi倍のビット長の値M’を生成する。
(S413)では、分割部17は、(S412)で生成された値M’をi個に分割して、256ビット長の値p[1],...,値p[i]を生成する。
(S414)では、既定長値入力部11は、(S413)で生成された256ビット長の値p[1],...,値p[i]を入力する。
(S415)では、固定値付加部12は、(S414)で入力された256ビット長の値p[1],...,値p[i]のそれぞれに対して、256ビット長の固定値const[1],...,固定値const[i]を付加して、512ビット長の値x[1],...,値x[i]を生成する。
(S416)では、圧縮関数計算部13は、256ビット長の固定値IV1と、(S415)で生成された512ビット長の値x[1]を圧縮関数hの入力として、c[1]=h(IV1,x[1])を計算して256ビット長の値c[1]を得る。
(S417)では、圧縮関数計算部13は、j=2からi−1まで順に、256ビット長の値c[j−1]と512ビット長の値x[j]とを圧縮関数hの入力として、c[j]=h(c[j−1],x[j])を計算して256ビット長の値c[j]を得る。
(S418)では、置換関数計算部19は、(S417)で計算された256ビット長の値c[i−1]を置換関数πの入力として、c’[i−1]=π(c[i−1])を計算して256ビット長の値c’[i−1]を得る。
(S419)では、圧縮関数計算部13は、(S418)で計算された256ビット長の値c’[i−1]と、(S415)で生成された512ビット長の値x[i]とを圧縮関数hの入力として、c[i]=h(c’[i−1],x[i])を計算して256ビット長の値c[i]を得る。
(S420)では、出力部14は、(S419)で計算された値c[i]を出力する。
【0150】
実施の形態4に係るハッシュ値演算装置10により構成されたハッシュ関数は、圧縮関数hが準一方向性が破られた理想的な圧縮関数の場合であっても、ランダムオラクルと強識別不可能性を満たすハッシュ関数となる。
【0151】
なお、実施の形態1と同様に、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。
【0152】
また、実施の形態1と同様に、圧縮関数計算部13は、ハッシュ値演算装置10の外部に備える圧縮関数計算装置に入力値を入力して、圧縮関数計算装置に圧縮関数hを計算させることにより、圧縮関数hを計算した結果を得てもよい。
また、同様に、置換関数計算部19は、ハッシュ値演算装置10の外部に備える置換関数演算装置に入力値を入力して、置換関数演算装置に置換関数πを計算させることにより、置換関数演算を計算した結果を得てもよい。
【0153】
また、圧縮関数計算部13が値c[1],...,値c[i]を計算するのに用いる圧縮関数hは、同一の圧縮関数hであってもよいし、それぞれ異なる圧縮関数hであってもよい。
【0154】
つまり、実施の形態4に係るハッシュ値演算装置10をまとめると次のようになる。
ハッシュ値演算装置10は、i個のm−sビットの入力値p[1],...,p[i]に対して、圧縮関数演算装置に、nビット固定値IV1、第1メッセージp[1]、nビット固定値const[1]を入力し、その出力c[1]を得る。次に、圧縮関数演算装置に、nビット値c[1]、第2メッセージp[2]、nビット固定値const[2]を入力し、その出力c[2]を得る。この処理を、第i−1メッセージまで同様に行い、その出力値c[i−1]を得る。fixed pointを持たないnビット上の任意の置換関数πを用いて、c=π(c[i−1])を計算する。圧縮関数演算装置に、nビット値c、第iメッセージp[i]、nビット固定値const[i]を入力し、その出力c[i]を得る。そして、c[i]を出力することを特徴とする。
【0155】
また、ハッシュ値演算装置10は、任意長の値Mから、任意長の値を入力とし、m−nビットの値を出力する任意のパディング処理装置を用いて、m−nビットの倍数となるメッセージM’を生成する。分割処理装置を用いてM’をi個のm−nビットの値p[1],...,p[i]に分割することを特徴とする。
【0156】
さらに、ハッシュ値演算装置10は、パディング処理装置を、M||1||0...0||<M>とすることを特徴とする。但し、<M>はMのビット長を64ビットで表したものである。
【0157】
また、さらに、ハッシュ値演算装置10は、圧縮関数演算装置として、SHA−256の圧縮関数演算装置を用いたことを特徴とする。
【0158】
実施の形態5.
実施の形態5では、実施の形態4とは異なるハッシュ関数であって、準一方向性が破られた理想的な圧縮関数を用いて構成した場合であっても、ランダムオラクルといわゆる強識別不可能である新たなハッシュ関数を構成するハッシュ値演算装置10について説明する。
【0159】
図34は、実施の形態5に係るハッシュ値演算装置10の機能を示す機能ブロック図である。
図35は、図34に示すハッシュ値演算装置10の動作を示すフローチャートである。
図36は、図34に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0160】
図34に示すハッシュ値演算装置10の機能と動作について説明する。
図34に示すハッシュ値演算装置10は、既定長値入力部11、固定値付加部12、圧縮関数計算部13、出力部14、排他的論理和計算部18、置換関数計算部19を備える。
【0161】
(S501:既定長値入力ステップ)
既定長値入力部11は、m−sビット長のi個の値p[1],...,値p[i]を入力装置により入力して記憶装置に記憶する。
【0162】
(S502:排他的論理和計算ステップ)
排他的論理和計算部18は、(S501)で入力されたm−sビット長の値p[1],...,p[i]と、予め記憶装置に記憶したm−sビット長の固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを処理装置により計算してm−sビット長の値sumを得て記憶装置に記憶する。
【0163】
(S503:固定値付加ステップ)
固定値付加部12は、(S501)で入力されたm−sビット長の値p[1],...,値p[i]のそれぞれに対して、予め記憶装置に記憶したsビット長の固定値const[1],...,固定値const[i]を付加して、mビット長の値x[1],...,値x[i]を処理装置により生成して記憶装置に記憶する。
つまり、固定値付加部12は、値p[1]に固定値const[1]を付加して、値x[1]を生成する。固定値付加部12は、値p[2]に固定値const[2]を付加して、値x[2]を生成する。以下同様に、j=3,...,iに対して、固定値付加部12は、値p[j]に固定値const[j]を付加して、値x[j]を生成する。
なお、j=1,...,i−1について、値p[j]に固定値const[j]を付加する位置は、どこであってもよい。つまり、固定値const[j]は、値p[j]の前や後に追加してもよいし、値p[j]の間に挿入してもよい。
また、固定値const[1]≠固定値const[2]≠...≠固定値const[i]である。例えば、j=1,...,iについて、固定値const[j]は、jをsビットで表現した値<j>である。
【0164】
(S504:第1圧縮関数計算ステップ)
圧縮関数計算部13は、予め記憶装置に記憶したnビット長の固定値IV1と、(S503)で生成されたmビット長の値x[1]を圧縮関数hの入力として、c[1]=h(IV1,x[1])を処理装置により計算してnビット長の値c[1]を得て記憶装置に記憶する。
【0165】
(S505:第2圧縮関数計算ステップ)
圧縮関数計算部13は、j=2からiまで順に、nビット長の値c[j−1]とmビット長の値x[j]とを圧縮関数hの入力として、c[j]=h(c[j−1],x[j])を処理装置により計算してnビット長の値c[j]を得て記憶装置に記憶する。
つまり、まず、圧縮関数計算部13は、(S504)で計算したnビット長の値c[1]と、(S503)で生成されたmビット長の値x[2]とを入力として、c[2]=h(c[1],x[2])を処理装置により計算してnビット長の値c[2]を得る。
次に、圧縮関数計算部13は、計算したnビット長の値c[2]と、(S503)で生成されたmビット長の値x[3]とを入力として、c[3]=h(c[2],x[3])を処理装置により計算してnビット長の値c[3]を得る。
これを繰り返して、最終的に、圧縮関数計算部13は、計算したnビット長の値c[i−1]と、(S503)で生成されたmビット長の値x[i]とを入力として、c[i]=h(c[i−1],x[i])を処理装置により計算してnビット長の値c[i]を得る。
【0166】
(S506:置換関数計算ステップ)
置換関数計算部19は、(S505)で計算されたnビット長の値c[i]を置換関数πの入力として、c’[i]=π(c[i])を処理装置により計算してnビット長の値c’[i]を得て記憶装置に記憶する。
なお、置換関数πは、任意の値aを入力した場合に値aとは異なる値a’に置換する置換関数であって、値aを入力した場合に入力した値aがそのまま出力されることのない置換関数である。つまり、置換関数πは、π(a)=aとなるような固定点(Fixed Point)を有さない置換関数である。
【0167】
(S507:第3圧縮関数計算ステップ)
圧縮関数計算部13は、(S506)で計算されたnビット長の値c’[i]と、(S502)で計算されたm−sビット長の値sumにsビット長の固定値const[i+1]を付加したmビット長のx[i+1]を圧縮関数hの入力として、c[i+1]=h(c’[i],x[i+1])を処理装置により計算してnビット長の値c[i+1]を得て記憶装置に記憶する。
なお、固定値const[i+1]≠固定値const[1]≠...≠固定値const[i]である。例えば、固定値const[i+1]は、i+1をsビットで表現した値<i+1>である。
また、値sumに固定値const[i+1]を付加する位置は、どこであってもよい。つまり、固定値const[i+1]は、値sumの前や後に追加してもよいし、値sumの間に挿入してもよい。
【0168】
(S508:出力ステップ)
出力部14は、(S507)で計算された値c[i+1]を出力装置により出力する。
【0169】
なお、i=1の場合、つまり(S501)で1個の値p[1]のみが入力された場合には、(S505)は実行されない。つまり、(S504)で値c[1]を得た後、(S506)で値c[1]を入力として、値c’[1]を得る。そして、(S507)で値c’[1]と値sumに固定値const[i+1]を付加した値x[2]とを入力として、値c[2]を得る。
【0170】
以上をまとめると、次のようになる。
まず、ハッシュ値演算装置10は、sum=p[1] xor,...,xor p[i] xor yを処理装置により計算する。
また、ハッシュ値演算装置10は、j=1からiまで順に、c[j]=h(c[j−1],p[j]||<j>)を計算する。ここで、c[0]は、IV1とする。
次に、ハッシュ値演算装置10は、c[i+1]=h(π(c[i]),sum||<i+1>)を計算する。
そして、ハッシュ値演算装置10は、値c[i+1]を出力する。
【0171】
上記説明では、(S501)で既定長値入力部11が、m−sビット長のi個の値p[1],...,値p[i]を入力するとした。しかし、通常、ハッシュ関数へ入力される値は、1個の任意ビット長の値である。つまり、上記説明では、1個の任意ビット長の値が入力された場合に、どのようにm−sビット長のi個の値p[1],...,値p[i]を生成するのかについては説明を省略した。
次に、任意ビット長の値が入力された場合に、m−sビット長のi個の値p[1],...,値p[i]を生成する機能を追加したハッシュ値演算装置10について説明する。
【0172】
図37は、図34に示すハッシュ値演算装置10に、任意ビット長の値が入力された場合に、m−sビット長のi個の値p[1],...,値p[i]を生成する機能を追加したハッシュ値演算装置10の機能を示す機能ブロック図である。
図38は、図37に示すハッシュ値演算装置10の動作を示すフローチャートである。
図39は、図37に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
【0173】
図37に示すハッシュ値演算装置10の機能と動作について説明する。
図37に示すハッシュ値演算装置10は、図34に示すハッシュ値演算装置10が備える機能に加え、任意長値入力部15、パディング部16、分割部17を備える。
【0174】
(S511:任意長値入力ステップ)
任意長値入力部15は、任意ビット長の値Mを入力装置により入力する。
【0175】
(S512:パディングステップ)
パディング部16は、(S511)で入力された値Mに対して、パディング関数padを用いて、所定の値を付加してm−sビット長のi倍のビット長の値M’を処理装置により生成して記憶装置に記憶する。つまり、パディング部16は、M’=pad(M)を処理装置により計算して値M’を得る。
【0176】
(S513:分割ステップ)
分割部17は、(S512)で生成された値M’を処理装置によりi個に分割して、m−sビット長の値p[1],...,値p[i]を生成して記憶装置に記憶する。つまり、分割部17は、M’=p[1]||...||p[i]を処理装置により計算して値p[1],...,値p[i]を得る。
【0177】
(S514:既定長値入力ステップ)
既定長値入力部11は、(S513)で生成された値p[1],...,値p[i]を入力装置により入力する。
【0178】
(S515)から(S521)までの処理は、(S502)から(S508)までの処理と同一である。
【0179】
(S512)におけるパディング方法の一例を説明する。
図40は、以下に説明するパディング処理を行う場合の図37に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
(S512)でパディング部16は、実施の形態1で説明した(S112)におけるパディング方法と同様に、(S511)で入力された値Mに対して、“1||0・・・0||<M>を付加して、m−sビット長のi倍のビット長の値M’を処理装置により生成する。ここで、<M>は、Mのビット長|M|の64ビット表現である。
このように、パディングして値M’を生成することにより、衝突困難性を高くすることができる。
【0180】
図41は、以下に説明するパディング処理を行う場合の図37に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
(S512)でパディング部16は、(S511)で入力された値Mに対して、“1||0・・・0を付加して、m−sビット長のi倍のビット長の値M’を処理装置により生成する。
このように、パディングして値M’を生成しても、衝突困難性を高くすることができる。
【0181】
なお、実施の形態1と同様に、予めiの値を決めておくのではなく、iの値は、入力された任意ビット長の値Mに応じて決定されるとしてもよい。
【0182】
次に、図37に示すハッシュ値演算装置10の圧縮関数としてSHA−256を用いた場合の例を説明する。なお、SHA−256の圧縮関数をSHA256と呼ぶ。SHA256は、256ビット長の値と512ビット長の値との2つの値が入力された場合に、256ビット長の値を出力する関数である。
図42は、圧縮関数としてSHA−256を用いる場合の図37に示すハッシュ値演算装置10により実現されるハッシュ関数の構造図である。
なお、以下の説明では、値sを56として説明する。
【0183】
(S511)では、任意長値入力部15は、任意ビット長の値Mを入力する。
(S512)では、パディング部16は、(S511)で入力された値Mに対して、パディング関数padを用いて、所定の値を付加して456(=512−56)ビット長のi倍のビット長の値M’を生成する。
(S513)では、分割部17は、(S512)で生成された値M’をi個に分割して、456ビット長の値p[1],...,値p[i]を生成する。
(S514)では、既定長値入力部11は、(S513)で生成された456ビット長の値p[1],...,値p[i]を入力する。
(S515)では、排他的論理和計算部18は、(S514)で入力された456ビット長の値p[1],...,p[i]と、456ビット長の固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算して456ビット長の値sumを得る。
(S516)では、固定値付加部12は、(S511)で入力された456ビット長の値p[1],...,値p[i]のそれぞれに対して、56ビット長の固定値const[1],...,固定値const[i]を付加して、512ビット長の値x[1],...,値x[i]を生成する。
(S517)では、圧縮関数計算部13は、256ビット長の固定値IV1と、(S516)で生成された512ビット長の値x[1]を圧縮関数hの入力として、c[1]=h(IV1,x[1])を計算して256ビット長の値c[1]を得る。
(S518)では、圧縮関数計算部13は、j=2からiまで順に、256ビット長の値c[j−1]と512ビット長の値x[j]とを圧縮関数hの入力として、c[j]=h(c[j−1],x[j])を計算して256ビット長の値c[j]を得る。
(S519)では、置換関数計算部19は、(S518)で計算された256ビット長の値c[i]を置換関数πの入力として、c’[i]=π(c[i])を計算して256ビット長の値c’[i]を得る。
(S520)では、圧縮関数計算部13は、(S519)で計算された256ビット長の値c’[i]と、(S515)で計算された456ビット長の値sumに56ビット長の固定値const[i+1]を付加した512ビット長のx[i+1]を圧縮関数hの入力として、c[i+1]=h(c’[i],x[i+1])を計算して256ビット長の値c[i+1]を得る。
(S521)では、出力部14は、(S520)で計算された値c[i+1]を出力する。
【0184】
実施の形態5に係るハッシュ値演算装置10により構成されたハッシュ関数は、圧縮関数hが準一方向性が破られた理想的な圧縮関数の場合であっても、ランダムオラクルと強識別不可能性を満たすハッシュ関数となる。
【0185】
なお、実施の形態1と同様に、必ずしも上述した処理順序通りに計算する必要はなく、ストリーム処理ができる場合には、ストリーム処理で計算してもよい。
【0186】
また、実施の形態1と同様に、圧縮関数計算部13は、ハッシュ値演算装置10の外部に備える圧縮関数計算装置に入力値を入力して、圧縮関数計算装置に圧縮関数hを計算させることにより、圧縮関数hを計算した結果を得てもよい。
また、同様に、排他的論理和計算部18は、ハッシュ値演算装置10の外部に備える排他的論理和計算装置に入力値を入力して、排他的論理和計算装置に排他的論理和演算を計算させることにより、排他的論理和演算を計算した結果を得てもよい。同様に、置換関数計算部19は、ハッシュ値演算装置10の外部に備える置換関数演算装置に入力値を入力して、置換関数演算装置に置換関数πを計算させることにより、置換関数演算を計算した結果を得てもよい。
【0187】
また、圧縮関数計算部13が値c[1],...,値c[i+1]を計算するのに用いる圧縮関数hは、同一の圧縮関数hであってもよいし、それぞれ異なる圧縮関数hであってもよい。
【0188】
つまり、実施の形態5に係るハッシュ値演算装置10をまとめると次のようになる。
ハッシュ値演算装置10は、i個のm−sビットの入力値p[1],...,p[i]に対して、圧縮関数演算装置に、nビット固定値IV1、第1メッセージp[1]、1のsビット表現値を入力し、その出力c[1]を得る。次に、圧縮関数演算装置に、nビット値c[1]、第2メッセージp[2]、2のsビット表現値を入力し、その出力c[2]を得る。この処理を、第iメッセージまで同様に行い、その出力値c[i]を得る。fixed pointを持たないnビット上の任意の置換関数πを用いて、c=π(c[i])を計算する。圧縮関数演算装置に、nビット値c、sum=p[1] xor ... xor p[i] xor y、i+1のsビットの表現値を入力し、その出力c[i+1]を得る。c[i+1]を出力することを特徴とする。ここで、yはm−sビット固定値である。
【0189】
また、ハッシュ値演算装置10は、任意長の値Mから、任意長の値を入力とし、m−sビットの値を出力する任意のパディング処理装置を用いて、m−sビットの倍数となるメッセージM’を生成する。分割処理装置を用いてM’をi個のm−sビットの値p[1],...,p[i]に分割することを特徴とする。
【0190】
さらに、ハッシュ値演算装置10は、パディング処理装置を、M||1||0...0||<M>とし、s=56とすることを特徴とする。但し、<M>はMのビット長を64ビットで表したものである。
【0191】
また、さらに、ハッシュ値演算装置10は、パディング処理装置を、M||1||0...0とし、s=56とすることを特徴とする。
【0192】
また、ハッシュ値演算装置10は、圧縮関数演算装置として、SHA−256の圧縮関数演算装置を用いたことを特徴とする。
【0193】
すなわち、以上の実施の形態に係るハッシュ値演算装置10は、EMD構造、MDP構造、圧縮関数に固定値を入力する操作、圧縮関数に圧縮関数番号を入力する操作、メッセージの排他的論理輪値を圧縮関数の入力とする操作を利用してハッシュ関数を構成する。これにより、一方向性が破られた圧縮関数または準一方向性が破られた圧縮関数から、ランダムオラクルと強識別不可能性を満たす、効率的なハッシュ関数を構成する。
【0194】
なお、以上の実施の形態に係るハッシュ値演算装置10は、暗号処理(署名処理を含む)を行う暗号処理装置等において用いられるハッシュ値を計算するための装置である。
【0195】
次に、実施の形態におけるハッシュ値演算装置10のハードウェア構成について説明する。
図43は、ハッシュ値演算装置10のハードウェア構成の一例を示す図である。
図43に示すように、ハッシュ値演算装置10は、プログラムを実行するCPU911(Central・Processing・Unit、中央処理装置、処理装置、演算装置、演算回路、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう)を備えている。CPU911は、バス912を介してROM913、RAM914、LCD901(Liquid Crystal Display)、キーボード902(K/B)、通信ボード915、磁気ディスク装置920と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置920(固定ディスク装置)の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置920は、所定の固定ディスクインタフェースを介して接続される。
【0196】
ROM913、磁気ディスク装置920は、不揮発性メモリの一例である。RAM914は、揮発性メモリの一例である。ROM913とRAM914と磁気ディスク装置920とは、記憶装置の一例である。また、キーボード902、通信ボード915は、入力装置の一例である。また、通信ボード915は、通信装置(ネットワークインタフェース)の一例である。さらに、LCD901は、表示装置の一例である。
【0197】
磁気ディスク装置920又はROM913などには、オペレーティングシステム921(OS)、ウィンドウシステム922、プログラム群923、ファイル群924が記憶されている。プログラム群923のプログラムは、CPU911、オペレーティングシステム921、ウィンドウシステム922により実行される。
【0198】
プログラム群923には、上記の説明において「既定長値入力部11」、「固定値付加部12」、「圧縮関数計算部13」、「出力部14」、「任意長値入力部15」、「パディング部16」、「分割部17」、「排他的論理和計算部18」、「置換関数計算部19」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、CPU911により読み出され実行される。
ファイル群924には、上記の説明において固定値や途中計算結果等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU911によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのCPU911の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のCPU911の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【0199】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、RAM914のメモリ、その他光ディスク等の記録媒体やICチップに記録される。また、データや信号は、バス912や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ROM913に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ROM913等の記録媒体に記憶される。プログラムはCPU911により読み出され、CPU911により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【0200】
10 ハッシュ値演算装置、11 既定長値入力部、12 固定値付加部、13 圧縮関数計算部、14 出力部、15 任意長値入力部、16 パディング部、17 分割部、18 排他的論理和計算部、19 置換関数計算部。

【特許請求の範囲】
【請求項1】
i個の値p[1],...,値p[i]を入力する既定長値入力部と、
前記既定長値入力部が入力した値p[1],...,値p[i]のうち、i−1個の値p[1],...,値p[i−1]それぞれに対して、固定値const[1],...,固定値const[i−1]を付加して、値x[1],...,値x[i−1]を生成して記憶装置に記憶する固定値付加部と、
j=1からi−1まで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加部が生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i−1]を得て記憶装置に記憶し、
固定値IV2と、値p[i]に値c[i−1]を付加した値x[i]とを入力として、圧縮関数hを計算した結果である値c[i]を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が得た値c[i]を出力する出力部と
を備えることを特徴とするハッシュ値演算装置。
【請求項2】
前記既定長値入力部は、所定の自然数mと、自然数mよりも小さい自然数nとについて、i個の値であって、m−nビット長の値p[1],...,値p[i]を入力し、
前記固定値付加部は、前記既定長値入力部が入力したm−nビット長の値p[1],...,値p[i]のうち、i−1個の値p[1],...,値p[i−1]それぞれに対して、nビット長の固定値const[1],...,固定値const[i−1]を付加して、mビット長の値x[1],...,値x[i−1]を生成し、
前記圧縮関数計算部は、j=1からi−1まで順に、nビット長の値c[j−1](値c[0]はnビット長の固定値IV1とする)と、前記固定値付加部が生成したmビット長の値x[j]とを入力として、圧縮関数hを計算した結果であるnビット長の値c[j]を得ることにより、nビット長の値c[i−1]を得て、
nビット長の固定値IV2と、m−nビット長の値p[i]にnビット長の値c[i−1]を付加したmビット長の値x[i]とを入力として、圧縮関数hを計算した結果であるnビット長の値c[i]を得る
ことを特徴とする請求項1に記載のハッシュ値演算装置。
【請求項3】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Mを入力する任意長値入力部と、
前記任意長値入力部が入力した値Mに対して、所定の値を付加してm−nビット長のi倍のビット長の値M’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値M’を分割して、m−nビット長の値p[1],...,値p[i]を生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値p[1],...,値p[i]を入力する
ことを特徴とする請求項2に記載のハッシュ値演算装置。
【請求項4】
入力装置が、i個の値p[1],...,値p[i]を入力する既定長値入力ステップと、
処理装置が、前記既定長値入力ステップで入力した値p[1],...,値p[i]のうち、i−1個の値p[1],...,値p[i−1]それぞれに対して、固定値const[1],...,固定値const[i−1]を付加して、値x[1],...,値x[i−1]を生成する固定値付加ステップと、
処理装置が、j=1からi−1まで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加ステップで生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i−1]を得て、
固定値IV2と、値p[i]に値c[i−1]を付加した値x[i]とを入力として、圧縮関数hを計算した結果である値c[i]を得る圧縮関数計算ステップと、
出力装置が、前記圧縮関数計算ステップで得た値c[i]を出力する出力ステップと
を備えることを特徴とするハッシュ値演算方法。
【請求項5】
i個の値p[1],...,値p[i]を入力する既定長値入力処理と、
前記既定長値入力処理で入力した値p[1],...,値p[i]のうち、i−1個の値p[1],...,値p[i−1]それぞれに対して、固定値const[1],...,固定値const[i−1]を付加して、値x[1],...,値x[i−1]を生成する固定値付加処理と、
j=1からi−1まで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加処理で生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i−1]を得て、
固定値IV2と、値p[i]に値c[i−1]を付加した値x[i]とを入力として、圧縮関数hを計算した結果である値c[i]を得る圧縮関数計算処理と、
前記圧縮関数計算処理で得た値c[i]を出力する出力処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項6】
i個の値p[1],...,値p[i]を入力する既定長値入力部と、
前記既定長値入力部が入力した値p[1],...,p[i]と、固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果である値sumを得て記憶装置に記憶する排他的論理和計算部と、
前記既定長値入力部が入力した値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成して記憶装置に記憶する固定値付加部と、
j=1からiまで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加部が生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i]を得て記憶装置に記憶し、
値c[i]と、前記排他的論理和計算部が得た値sumに固定値const[i+1]を付加した値x[i+1]とを入力として、圧縮関数hを計算した結果である値c[i+1]を得て記憶装置に記憶し、
固定値IV2と、値c[i+1]に固定値const[i+2]を付加した値x[i+2]とを入力として、圧縮関数hを計算した結果である値c[i+2]を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が計算した値c[i+2]を出力する出力部と
を備えることを特徴とするハッシュ値演算装置。
【請求項7】
前記既定長値入力部は、所定の自然数mと、自然数mよりも小さい自然数sとについて、i個の値であって、m−sビット長の値p[1],...,値p[i]を入力し、
前記排他的論理和計算部は、前記既定長値入力部が入力したm−sビット長の値p[1],...,p[i]と、m−sビット長の固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果であるm−sビット長の値sumを得て、
前記固定値付加部は、前記既定長値入力部が入力したm−sビット長の値p[1],...,値p[i]それぞれに対して、sビット長の固定値const[1],...,固定値const[i]を付加して、mビット長の値x[1],...,値x[i]を生成し、
前記圧縮関数計算部は、j=1からiまで順に、自然数mよりも小さい自然数nビット長の値c[j−1](値c[0]はnビット長の固定値IV1とする)と、前記固定値付加部が生成したmビット長の値x[j]とを入力として、圧縮関数hを計算した結果であるnビット長の値c[j]を得ることにより、nビット長の値c[i]を得て、
nビット長の値c[i]と、前記排他的論理和計算部が得たm−sビット長の値sumにsビット長の固定値const[i+1]を付加したmビット長の値x[i+1]とを入力として、圧縮関数hを計算した結果であるnビット長の値c[i+1]を得て、
nビット長の固定値IV2と、nビット長の値c[i+1]にm−nビット長の固定値const[i+2]を付加したmビット長の値x[i+2]とを入力として、圧縮関数hを計算した結果であるnビット長の値c[i+2]を得る
ことを特徴とする請求項6に記載のハッシュ値演算装置。
【請求項8】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Mを入力する任意長値入力部と、
前記任意長値入力部が入力した値Mに対して、所定の値を付加してm−sビット長のi倍のビット長の値M’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値M’を分割して、m−sビット長の値p[1],...,値p[i]を生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値p[1],...,値p[i]を入力する
ことを特徴とする請求項7に記載のハッシュ値演算装置。
【請求項9】
入力装置が、i個の値p[1],...,値p[i]を入力する既定長値入力ステップと、
処理装置が、前記既定長値入力ステップで入力した値p[1],...,p[i]と、固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果である値sumを得る排他的論理和計算ステップと、
処理装置が、前記既定長値入力ステップで入力した値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成する固定値付加ステップと、
処理装置が、j=1からiまで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加ステップで生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i]を得て、
値c[i]と、前記排他的論理和計算ステップで得た値sumに固定値const[i+1]を付加した値x[i+1]とを入力として、圧縮関数hを計算した結果である値c[i+1]を得て、
固定値IV2と、値c[i+1]に固定値const[i+2]を付加した値x[i+2]とを入力として、圧縮関数hを計算した結果である値c[i+2]を得る圧縮関数計算ステップと、
出力装置が、前記圧縮関数計算ステップで計算した値c[i+2]を出力する出力ステップと
を備えることを特徴とするハッシュ値演算方法。
【請求項10】
i個の値p[1],...,値p[i]を入力する既定長値入力処理と、
前記既定長値入力処理で入力した値p[1],...,p[i]と、固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果である値sumを得る排他的論理和計算処理と、
前記既定長値入力処理で入力した値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成する固定値付加処理と、
j=1からiまで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加処理で生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i]を得て、
値c[i]と、前記排他的論理和計算処理で得た値sumに固定値const[i+1]を付加した値x[i+1]とを入力として、圧縮関数hを計算した結果である値c[i+1]を得て、
固定値IV2と、値c[i+1]に固定値const[i+2]を付加した値x[i+2]とを入力として、圧縮関数hを計算した結果である値c[i+2]を得る圧縮関数計算処理と、
前記圧縮関数計算処理で計算した値c[i+2]を出力する出力処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項11】
i+1個の値p[1],...,値p[i+1]を入力する既定長値入力部と、
前記既定長値入力部が入力したi+1個の値p[1],...,値p[i+1]のうち、i個の値p[1],...,p[i]と、固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果である値sumを得て記憶装置に記憶する排他的論理和計算部と、
前記既定長値入力部が入力したi+1個の値p[1],...,値p[i+1]のうち、i個の値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成して記憶装置に記憶する固定値付加部と、
j=1からiまで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加部が生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i]を得て記憶装置に記憶し、
値c[i]と、前記排他的論理和計算部が得た値sumに固定値const[i+1]を付加した値x[i+1]とを入力として、圧縮関数hを計算した結果である値c[i+1]を得て記憶装置に記憶し、
固定値IV2と、値c[i+1]に値p[i+1]を付加した値x[i+2]とを入力として、圧縮関数hを計算した結果である値c[i+2]を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が計算した値c[i+2]を出力する出力部と
を備えることを特徴とするハッシュ値演算装置。
【請求項12】
前記既定長値入力部は、所定の自然数mと、自然数mよりも小さい自然数nと、自然数mよりも小さい自然数sとについて、i個の値であって、m−sビット長の値p[1],...,値p[i]と、1個の値であって、m−nビットの値p[i+1]を入力し、
前記排他的論理和計算部は、前記既定長値入力部が入力したm−sビット長の値p[1],...,p[i]と、m−sビット長の固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果であるm−sビット長の値sumを得て、
前記固定値付加部は、前記既定長値入力部が入力したm−sビット長の値p[1],...,値p[i]それぞれに対して、sビット長の固定値const[1],...,固定値const[i]を付加して、mビット長の値x[1],...,値x[i]を生成し、
前記圧縮関数計算部は、j=1からiまで順に、nビット長の値c[j−1](値c[0]はnビット長の固定値IV1とする)と、前記固定値付加部が生成したmビット長の値x[j]とを入力として、圧縮関数hを計算した結果であるnビット長の値c[j]を得ることにより、nビット長の値c[i]を得て、
nビット長の値c[i]と、前記排他的論理和計算部が得たm−sビット長の値sumにsビット長の固定値const[i+1]を付加したmビット長の値x[i+1]とを入力として、圧縮関数hを計算した結果であるnビット長の値c[i+1]を得て、
nビット長の固定値IV2と、nビット長の値c[i+1]にm−nビット長の値p[i+1]を付加したmビット長の値x[i+2]とを入力として、圧縮関数hを計算した結果であるnビット長の値c[i+2]を得る
ことを特徴とする請求項11に記載のハッシュ値演算装置。
【請求項13】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Mを入力する任意長値入力部と、
前記任意長値入力部が入力した値Mに対して、所定の値を付加して((m−s)×i+(m−n))ビット長の値M’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値M’を分割して、m−sビット長の値p[1],...,値p[i]とm−nビット長の値p[i+1]とを生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値p[1],...,値p[i]と値p[i+1]とを入力する
ことを特徴とする請求項12に記載のハッシュ値演算装置。
【請求項14】
入力装置が、i+1個の値p[1],...,値p[i+1]を入力する既定長値入力ステップと、
処理装置が、前記既定長値入力ステップで入力したi+1個の値p[1],...,値p[i+1]のうち、i個の値p[1],...,p[i]と、固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果である値sumを得る排他的論理和計算ステップと、
処理装置が、前記既定長値入力ステップで入力したi+1個の値p[1],...,値p[i+1]のうち、i個の値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成する固定値付加ステップと、
処理装置が、j=1からiまで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加ステップで生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i]を得て、
値c[i]と、前記排他的論理和計算ステップで得た値sumに固定値const[i+1]を付加した値x[i+1]とを入力として、圧縮関数hを計算した結果である値c[i+1]を得て、
固定値IV2と、値c[i+1]に値p[i+1]を付加した値x[i+2]とを入力として、圧縮関数hを計算した結果である値c[i+2]を得る圧縮関数計算ステップと、
出力装置が、前記圧縮関数計算ステップで計算した値c[i+2]を出力する出力ステップと
を備えることを特徴とするハッシュ値演算方法。
【請求項15】
i+1個の値p[1],...,値p[i+1]を入力する既定長値入力処理と、
前記既定長値入力処理で入力したi+1個の値p[1],...,値p[i+1]のうち、i個の値p[1],...,p[i]と、固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果である値sumを得る排他的論理和計算処理と、
前記既定長値入力処理で入力したi+1個の値p[1],...,値p[i+1]のうち、i個の値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成する固定値付加処理と、
j=1からiまで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加処理で生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i]を得て、
値c[i]と、前記排他的論理和計算処理で得た値sumに固定値const[i+1]を付加した値x[i+1]とを入力として、圧縮関数hを計算した結果である値c[i+1]を得て、
固定値IV2と、値c[i+1]に値p[i+1]を付加した値x[i+2]とを入力として、圧縮関数hを計算した結果である値c[i+2]を得る圧縮関数計算処理と、
前記圧縮関数計算処理で計算した値c[i+2]を出力する出力処理と
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項16】
ハッシュ値を計算するハッシュ値演算装置であり、
i個の値p[1],...,値p[i]を入力する既定長値入力部と、
前記既定長値入力部が入力した値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成して記憶装置に記憶する固定値付加部と、
j=1からi−1まで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加部が生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i−1]を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が得た値c[i−1]を入力として、置換関数πを計算した結果である値c’[i−1]を得て記憶装置に記憶する置換関数計算部とを備え、
前記圧縮関数計算部は、さらに、前記置換関数計算部が得た値c’[i−1]と値x[i]とを入力として、圧縮関数hを計算した結果である値c[i]を得て記憶装置に記憶し、
前記ハッシュ値演算装置は、さらに、
前記圧縮関数計算部が計算した値c[i]を出力する出力部
を備えることを特徴とするハッシュ値演算装置。
【請求項17】
前記既定長値入力部は、所定の自然数mと、自然数mよりも小さい自然数nとについて、i個の値であって、m−nビット長の値p[1],...,値p[i]を入力し、
前記固定値付加部は、前記既定長値入力部が入力したm−nビット長の値p[1],...,値p[i]それぞれに対して、nビット長の固定値const[1],...,固定値const[i]を付加して、mビット長の値x[1],...,値x[i]を生成し、
前記圧縮関数計算部は、j=1からi−1まで順に、nビット長の値c[j−1](値c[0]はnビット長の固定値IV1とする)と、前記固定値付加部が生成したmビット長の値x[j]とを入力として、圧縮関数hを計算した結果であるnビット長の値c[j]を得ることにより、nビット長の値c[i−1]を得て、
前記置換関数計算部は、前記圧縮関数計算部が得たnビット長の値c[i−1]を入力として、置換関数πを計算した結果であるnビット長の値c’[i−1]を得て、
前記圧縮関数計算部は、さらに、前記置換関数計算部が得たnビット長の値c’[i−1]とmビット長の値x[i]とを入力として、圧縮関数hを計算した結果であるnビット長の値c[i]を得る
ことを特徴とする請求項16に記載のハッシュ値演算装置。
【請求項18】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Mを入力する任意長値入力部と、
前記任意長値入力部が入力した値Mに対して、所定の値を付加してm−nビット長のi倍のビット長の値M’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値M’を分割して、m−nビット長の値p[1],...,値p[i]を生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値p[1],...,値p[i]を入力する
ことを特徴とする請求項17に記載のハッシュ値演算装置。
【請求項19】
ハッシュ値を計算するハッシュ値演算方法であり、
入力装置が、i個の値p[1],...,値p[i]を入力する既定長値入力ステップと、
処理装置が、前記既定長値入力ステップで入力した値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成する固定値付加ステップと、
処理装置が、j=1からi−1まで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加ステップで生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i−1]を得る圧縮関数計算ステップと、
処理装置が、前記圧縮関数計算ステップで得た値c[i−1]を入力として、置換関数πを計算した結果である値c’[i−1]を得る置換関数計算ステップとを備え、
前記圧縮関数計算ステップでは、さらに、処理装置が、前記置換関数計算ステップで得た値c’[i−1]と値x[i]とを入力として、圧縮関数hを計算した結果である値c[i]を得て、
前記ハッシュ値演算方法は、さらに、
出力装置が、前記圧縮関数計算ステップで計算した値c[i]を出力する出力ステップ
を備えることを特徴とするハッシュ値演算方法。
【請求項20】
ハッシュ値を計算するハッシュ値演算プログラムであり、
i個の値p[1],...,値p[i]を入力する既定長値入力処理と、
前記既定長値入力処理で入力した値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成する固定値付加処理と、
j=1からi−1まで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加処理で生成した[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i−1]を得る圧縮関数計算処理と、
前記圧縮関数計算処理で得た値c[i−1]を入力として、置換関数πを計算した結果である値c’[i−1]を得る置換関数計算処理とをコンピュータに実行させ、
前記圧縮関数計算処理では、さらに、前記置換関数計算処理で得た値c’[i−1]と値x[i]とを入力として、圧縮関数hを計算した結果である値c[i]を得て、
前記ハッシュ値演算プログラムは、さらに、
前記圧縮関数計算処理で計算した値c[i]を出力する出力処理
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。
【請求項21】
ハッシュ値を計算するハッシュ値演算装置であり、
i個の値p[1],...,値p[i]を入力する既定長値入力部と、
前記既定長値入力部が入力した値p[1],...,値p[i]と、固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果である値sumを得て記憶装置に記憶する排他的論理和計算部と、
前記既定長値入力部が入力した値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成して記憶装置に記憶する固定値付加部と、
j=1からiまで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加部が生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i]を得て記憶装置に記憶する圧縮関数計算部と、
前記圧縮関数計算部が得た値c[i]を入力として、置換関数πを計算した結果である値c’[i]を得て記憶装置に記憶する置換関数計算部とを備え、
前記圧縮関数計算部は、さらに、前記置換関数計算部が得た値c’[i]と、前記排他的論理和計算部が得た値sumに固定値const[i+1]を付加したx[i+1]を入力として、圧縮関数hを計算した結果である値c[i+1]を得て記憶装置に記憶し、
前記ハッシュ値演算装置は、さらに、
前記圧縮関数計算部が計算した値c[i+1]を出力する出力部
を備えることを特徴とするハッシュ値演算装置。
【請求項22】
前記既定長値入力部は、所定の自然数mと、自然数mよりも小さい自然数sとについて、i個の値であって、m−sビット長の値p[1],...,値p[i]を入力し、
前記排他的論理和計算部は、前記既定長値入力部が入力したm−sビット長の値p[1],...,値p[i]と、m−sビット長の固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果であるm−sビット長の値sumを得て、
前記固定値付加部は、前記既定長値入力部が入力したm−sビット長の値p[1],...,値p[i]それぞれに対して、sビット長の固定値const[1],...,固定値const[i]を付加して、mビット長の値x[1],...,値x[i]を生成し、
前記圧縮関数計算部は、j=1からiまで順に、自然数mよりも小さい自然数nビット長の値c[j−1](値c[0]はnビット長の固定値IV1とする)と、前記固定値付加部が生成したmビット長の値x[j]とを入力として、圧縮関数hを計算した結果であるnビット長の値c[j]を得ることにより、nビット長の値c[i]を得て、
前記置換関数計算部は、前記圧縮関数計算部が得たnビット長の値c[i]を入力として、置換関数πを計算した結果であるnビット長の値c’[i]を得て、
前記圧縮関数計算部は、さらに、前記置換関数計算部が得たnビット長の値c’[i]と、前記排他的論理和計算部が得たm−sビット長の値sumにsビット長の固定値const[i+1]を付加したmビット長のx[i+1]を入力として、圧縮関数hを計算した結果であるnビット長の値c[i+1]を得る
を備えることを特徴とする請求項21に記載のハッシュ値演算装置。
【請求項23】
前記ハッシュ値演算装置は、さらに、
任意ビット長の値Mを入力する任意長値入力部と、
前記任意長値入力部が入力した値Mに対して、所定の値を付加してm−sビット長のi倍のビット長の値M’を生成して記憶装置に記憶するパディング部と、
前記パディング部が生成した値M’を分割して、m−sビット長の値p[1],...,値p[i]を生成して記憶装置に記憶する分割部とを備え、
前記既定長値入力部は、前記分割部が生成した値p[1],...,値p[i]を入力する
ことを特徴とする請求項22に記載のハッシュ値演算装置。
【請求項24】
ハッシュ値を計算するハッシュ値演算方法であり、
入力装置が、i個の値p[1],...,値p[i]を入力する既定長値入力ステップと、
処理装置が、前記既定長値入力ステップで入力した値p[1],...,値p[i]と、固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果である値sumを得る排他的論理和計算ステップと、
処理装置が、前記既定長値入力ステップで入力した値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成する固定値付加ステップと、
処理装置が、j=1からiまで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加ステップで生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i]を得る圧縮関数計算ステップと、
処理装置が、前記圧縮関数計算ステップで得た値c[i]を入力として、置換関数πを計算した結果である値c’[i]を得る置換関数計算ステップとを備え、
前記圧縮関数計算ステップでは、さらに、処理装置が、前記置換関数計算ステップで得た値c’[i]と、前記排他的論理和計算ステップで得た値sumに固定値const[i+1]を付加したx[i+1]を入力として、圧縮関数hを計算した結果である値c[i+1]を得て、
前記ハッシュ値演算方法は、さらに、
出力装置が、前記圧縮関数計算ステップで計算した値c[i+1]を出力する出力ステップ
を備えることを特徴とするハッシュ値演算方法。
【請求項25】
ハッシュ値を計算するハッシュ値演算プログラムであり、
i個の値p[1],...,値p[i]を入力する既定長値入力処理と、
前記既定長値入力処理で入力した値p[1],...,値p[i]と、固定値yとを排他的論理和演算の入力として、sum=p[1] xor,...,xor p[i] xor yを計算した結果である値sumを得る排他的論理和計算処理と、
前記既定長値入力処理で入力した値p[1],...,値p[i]それぞれに対して、固定値const[1],...,固定値const[i]を付加して、値x[1],...,値x[i]を生成する固定値付加処理と、
j=1からiまで順に、値c[j−1](値c[0]は固定値IV1とする)と、前記固定値付加処理で生成した値x[j]とを入力として、圧縮関数hを計算した結果である値c[j]を得ることにより、値c[i]を得る圧縮関数計算処理と、
前記圧縮関数計算処理で得た値c[i]を入力として、置換関数πを計算した結果である値c’[i]を得る置換関数計算処理とをコンピュータに実行させ、
前記圧縮関数計算処理は、さらに、前記置換関数計算処理で得た値c’[i]と、前記排他的論理和計算処理で得た値sumに固定値const[i+1]を付加したx[i+1]を入力として、圧縮関数hを計算した結果である値c[i+1]を得て、
前記ハッシュ値演算プログラムは、さらに、
前記圧縮関数計算処理で計算した値c[i+1]を出力する出力処理
をコンピュータに実行させることを特徴とするハッシュ値演算プログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate

【図33】
image rotate

【図34】
image rotate

【図35】
image rotate

【図36】
image rotate

【図37】
image rotate

【図38】
image rotate

【図39】
image rotate

【図40】
image rotate

【図41】
image rotate

【図42】
image rotate

【図43】
image rotate