(57)【要約】【課題】比較的簡易に構成できる圧縮関数だけで構成し、且つ署名関数と親和性の高いハッシュ関数器を実現する。【解決手段】ＴＣＲハッシュ関数の安全性を担保するために、ＴＣＲハッシュ関数に元々備わっている任意長乱数鍵に加え、固定長乱数鍵を追加し、ＴＣＲハッシュ関数のメッセージダイジェストを修飾する処理を追加した。  この処理により、ＳＰＲ圧縮関数で構成されるＴＣＲハッシュ関数で、署名関数に固定長の入力を与えることを実現した。【選択図】図２
2008233661.tif 000002
【特許請求の範囲】
【請求項１】
等長ＴＣＲハッシュ関数器と、
固定長鍵を生成する固定長鍵生成部と、
前記等長ＴＣＲハッシュ関数器の出力と、前記固定長鍵を受け、前記等長ＴＣＲハッシュ関数器の出力とビット長が等しいデータを出力する直列処理部と
よりなることを特徴とするハッシュ関数装置。
【請求項２】
更に、
前記等長ＴＣＲハッシュ関数器に任意長鍵を与える任意長鍵生成部と、
前記任意長鍵を所定ビット長で分割するビット長分割部と、
前記ビット長分割部の任意ビット長出力を受け、所定ビット長に縮小する並列処理部と、
前記並列処理部の出力と、前記ビット長分割部の所定ビット長出力と
を備え、
前記直列処理部は、前記等長ＴＣＲハッシュ関数器の出力と、前記並列処理部の出力と、前記ビット長分割部の所定ビット長出力と、前記固定長鍵を受け、前記等長ＴＣＲハッシュ関数器の出力とビット長が等しいデータを出力することを特徴とする、請求項１記載のハッシュ関数装置。
【請求項３】
前記並列処理部は等長ＳＰＲハッシュ関数器であることを特徴とする、請求項２記載のハッシュ関数装置。
【請求項４】
前記並列処理部は、
入力データを均等にビット分割する第1のビット長分割器と、
第１のビット長の入力端子と第２のビット長の入力端子を備える第１の圧縮関数器と、
前記第１の圧縮関数器と構成が等しい第２の圧縮関数器と、
前記ビット長分割器にて得られた上位ビット部分を、前記第１のビット長と前記第２のビット長にて交互に分割する第２のビット長分割器と、
前記ビット長分割器にて得られた下位ビット部分を、前記第１のビット長と前記第２のビット長にて交互に分割する第３のビット長分割器と、
前記第２のビット長分割器から得られる、前記第１のビット長のデータ部分と前記第２のビット長のデータ部分を前記第１の圧縮関数器に入力する第１のスイッチ部と、
前記第３のビット長分割器から得られる、前記第１のビット長のデータ部分と前記第２のビット長のデータ部分を前記第２の圧縮関数器に入力する第２のスイッチ部と、
前記第２のビット長分割器から得られる、前記第２のビット長のデータ部分と前記第１の圧縮関数器の出力データとの剰余演算データを前記第１の圧縮関数器に入力する第３のスイッチ部と、
前記第３のビット長分割器から得られる、前記第２のビット長のデータ部分と前記第２の圧縮関数器の出力データとの剰余演算データを前記第２の圧縮関数器に入力する第４のスイッチ部と、
前記第１の圧縮関数器の出力データと前記第２の圧縮関数器の出力データとをビット結合するビット結合器と
を備える等長ＳＰＲハッシュ関数器であることを特徴とする、請求項３記載のハッシュ関数装置。
【請求項５】
任意長メッセージのメッセージ長を取得して、任意長の乱数鍵を生成するステップと、
前記任意長の乱数鍵を用いて任意長メッセージのメッセージダイジェストを生成するステップと、
固定長の乱数鍵を生成するステップと、
前記任意長の乱数鍵を所定長に縮小するステップと、
前記縮小された乱数鍵と前記固定長の乱数鍵と前記メッセージダイジェストを受けて、前記メッセージダイジェストとビット長が等しいデータを出力するステップと
を含むことを特徴とするハッシュ値演算方法。
【請求項６】
コンピュータを、
等長ＴＣＲハッシュ関数器と、
前記等長ＴＣＲハッシュ関数器に任意長鍵を与える任意長鍵生成部と、
前記任意長鍵を所定ビット長で分割するビット長分割部と、
前記ビット長分割部の任意ビット長出力を受け、所定ビット長に縮小する並列処理部と、
固定長鍵生成部と、
前記等長ＴＣＲハッシュ関数器の出力と、前記並列処理部の出力と、前記ビット長分割部の所定ビット長出力と、前記固定長鍵を受け、前記等長ＴＣＲハッシュ関数器の出力とビット長が等しいデータを出力する直列処理部
として機能させるためのハッシュ値演算プログラム。
【請求項７】
等長ＴＣＲハッシュ関数器と、
固定長鍵を生成する固定長鍵生成部と、
前記等長ＴＣＲハッシュ関数器の出力と、前記固定長鍵を受け、前記等長ＴＣＲハッシュ関数器の出力とビット長が等しいデータを出力する直列処理部と、
前記直列処理部から得られるデータと、前記固定長鍵を受けて電子署名データを生成する署名関数器と
よりなることを特徴とする電子署名装置。
【請求項８】
更に、
前記等長ＴＣＲハッシュ関数器に任意長鍵を与える任意長鍵生成部と、
前記任意長鍵を所定ビット長で分割するビット長分割部と、
前記ビット長分割部の任意ビット長出力を受け、所定ビット長に縮小する並列処理部と、
前記並列処理部の出力と、前記ビット長分割部の所定ビット長出力と
を備え、
前記直列処理部は、前記等長ＴＣＲハッシュ関数器の出力と、前記並列処理部の出力と、前記ビット長分割部の所定ビット長出力と、前記固定長鍵を受け、前記等長ＴＣＲハッシュ関数器の出力とビット長が等しいデータを出力することを特徴とする、請求項７記載の電子署名装置。
【請求項９】
前記並列処理部は等長ＳＰＲハッシュ関数器であることを特徴とする、請求項８記載の電子署名装置。
【請求項１０】
任意長メッセージのメッセージ長を取得して、任意長の乱数鍵を生成するステップと、
前記任意長の乱数鍵を用いて任意長メッセージのメッセージダイジェストを生成するステップと、
固定長の乱数鍵を生成するステップと、
前記任意長の乱数鍵を所定長に縮小するステップと、
前記縮小された乱数鍵と前記固定長の乱数鍵と前記メッセージダイジェストを受けて、前記メッセージダイジェストとビット長が等しいデータを出力するステップと、
前記前記メッセージダイジェストとビット長が等しいデータと、前記固定長の乱数鍵を受けて電子署名データを生成するステップと
を含むことを特徴とする電子署名方法。
【請求項１１】
コンピュータを、
等長ＴＣＲハッシュ関数器と、
前記等長ＴＣＲハッシュ関数器に任意長鍵を与える任意長鍵生成部と、
前記任意長鍵を所定ビット長で分割するビット長分割部と、
前記ビット長分割部の任意ビット長出力を受け、所定ビット長に縮小する並列処理部と、
固定長鍵生成部と、
前記等長ＴＣＲハッシュ関数器の出力と、前記並列処理部の出力と、前記ビット長分割部の所定ビット長出力と、前記固定長鍵を受け、前記等長ＴＣＲハッシュ関数器の出力とビット長が等しいデータを出力する直列処理部と、
前記直列処理部から得られるデータと、前記固定長鍵を受けて電子署名データを生成する署名関数器
として機能させるための電子署名演算プログラム。
【請求項１２】
任意長メッセージを入力されて固定長のメッセージダイジェストを出力するハッシュ関数装置であって、
電子署名データを生成する署名関数器が生成する電子署名に添付される任意長乱数鍵を生成する任意長鍵生成部と、
前記任意長乱数鍵と共に前記電子書名に添付されるものであり、前記署名関数器に前記メッセージダイジェストと共に供給される固定長乱数鍵を生成する固定長鍵生成部と
を具備することを特徴とする、ハッシュ関数装置。
【請求項１３】
任意長メッセージを入力されて電子署名データを出力する電子署名装置であって、
前記電子署名データに添付される任意長乱数鍵を生成する任意長鍵生成部と、
前記任意長乱数鍵と共に前記電子書名データに添付される固定長乱数鍵を生成する固定長鍵生成部と、
前記任意長メッセージと前記任意長乱数鍵と前記固定長乱数鍵を受けてメッセージダイジェストを生成するハッシュ関数装置と、
前記メッセージダイジェストと前記固定長乱数鍵を受けて前記電子署名データを生成する署名関数器と
を具備することを特徴とする、電子署名装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子署名装置に適用して好適な技術に関する。
より詳細には、比較的簡易な圧縮関数から構成でき、署名関数との親和性が高いハッシュ関数に関する。
【背景技術】
【０００２】
これより、図１１から図２２を参照して、従来技術を説明する。
［ハッシュ関数とは］
情報通信の発達に伴い、電子商取引等、情報自体及び情報通信路に機密性や非改ざん性を要求される場面が増えている。
情報の機密性には暗号を、非改ざん性には電子署名を用いる。
これら技術に必須の要素技術が、ハッシュ関数である。
【０００３】
図１１（ａ）、（ｂ）及び（ｃ）はハッシュ関数の概略図である。
図１１（ａ）は、ハッシュ関数の定義そのものを示す図である。
ハッシュ関数１１０１とは、任意長の情報（メッセージ）１１０２を読み込み、固定長のメッセージダイジェスト１１０３を出力する関数である。
ハッシュ関数自体は数学的な処理を行うものであるが、実際にはコンピュータソフトウェアや、ＩＣ等のハードウェアにて実装される。すなわち、データ処理装置の一種である。
図１１（ｂ）及び（ｃ）は、ハッシュ関数の大まかな内部構造を示す図である。
ハッシュ関数１１０１は、任意長のメッセージ１１０２を固定長のデータブロック群１１０４に分割し、これを圧縮関数（ｈ）１１０５で処理をする。
最初に一番目のデータパケットと初期値（ＩＶ：Initial Value）１１０６を圧縮関数で処理し、次に二番目のデータパケットと直前の圧縮関数の結果を次の圧縮関数で処理する。これを全てのデータパケットにおいて処理し続ける。
ここで、図１１（ｂ）の処理は、図１１（ｃ）のように、単一の圧縮関数１１０５を繰り返し処理させることと等しい。最初は初期値１１０６をスイッチ１１０７で選択し、次は直前の演算結果をスイッチ１１０７で選択する。
圧縮関数とは、固定長の入力を受け入れ、より短い固定長のデータを出力する関数である。殆どの圧縮関数は、直前の圧縮関数の実行結果を受け入れる「端子」と、データパケットを受け入れる「端子」を備える。
【０００４】
［ハッシュ関数の安全性とは］
ハッシュ関数は、意味のある任意長メッセージから、全く意味のない固定長のメッセージダイジェストを出力する。メッセージダイジェストは固定長であるが故に、元のメッセージとメッセージダイジェストとは、多対一の関係が成立する。このことは、あるメッセージＭと、Ｍとは異なるメッセージＭ’とをそれぞれハッシュ関数に入力して処理させると、全く同じメッセージダイジェストを出力する可能性が多々あることを意味する。
後述するが、ハッシュ関数と組み合わせて用いられる電子署名の場合、ハッシュ関数が処理した元のメッセージＭに対し、メッセージダイジェストが同じで異なるメッセージＭ’を見つけられると、メッセージの非改ざん性が証明できなくなってしまう。
したがって、ハッシュ関数は、メッセージダイジェストから元のメッセージが作成され難くなっていなければならない。そのような性質を備える関数を、一方向関数と呼ぶ。ハッシュ関数はこのような性質を備える必要がある。
【０００５】
［ハッシュ関数の安全性を評価する定義］
図１２、図１３、図１４及び図１５は、ハッシュ関数の安全性を説明する図である。
図１２は、ＣＲ性（Collision Resistance）を説明する図である。「衝突困難性」又は「強衝突耐性」とも呼ばれる。
挑戦者１１０（或は悪意を持つクラッカー（Cracker））が、ハッシュ関数１２０１に対し、任意に選んだ二つの異なるメッセージ（Ｍ）１２０２及び（Ｍ’）１２０３を処理させる。この結果得られるハッシュ値、Ｈ（Ｍ）１２０４とＨ（Ｍ’）１２０５が同じであれば、挑戦者１１０の勝ちである。
このようなゲームを、ハッシュ関数における「ＣＲゲーム」ともいう。
このような作業が、現実的な計算機を用いて、現実的な時間、例えば数時間から数ヶ月程度で実現してしまうと、そのハッシュ関数は「ＣＲ性を満たさない」という。
ＣＲ性のポイントとして、二つのメッセージの決定権は両方共挑戦者１１０にある点に注意されたい。つまり、挑戦者１１０は自分の都合で、全く任意のメッセージＭ及びＭ’を見つけることができるのである。
ＣＲ性はハッシュ関数作成者側にとって厳しい条件である。これは、ＣＲ性ハッシュ関数を作り難い、転じて実現し難いことを意味する。
これまでにＣＲ性を破られたハッシュ関数として、ＭＤ４やＭＤ５、或はＳＨＡ−１等が挙げられる。
なお、二つの異なるメッセージから得られるハッシュ値が同一になることを、ハッシュ値の衝突（コリジョン：collision）という。
【０００６】
図１３は、ＳＰＲ性（Second Pre-image Resistance）を説明する図である。「別原像計算困難性」「第二原像計算困難性」又は「弱衝突耐性」とも呼ばれる。
（１）出題者１０２はメッセージ（Ｍ）１３０２を出題する。
（２）挑戦者１１０はメッセージ（Ｍ）１３０２のハッシュ値Ｈ（Ｍ）１３０４と同じハッシュ値を出力する、メッセージ（Ｍ）１３０２とは異なるメッセージ（Ｍ’）１３０３を探す。メッセージ（Ｍ’）１３０３を探すことができれば、挑戦者１１０の勝ちである。
このようなゲームを、ハッシュ関数における「ＳＰＲゲーム」ともいう。
ポイントとして、問題となるメッセージの決定権は出題者１０２にあることに注意されたい。つまり、挑戦者１１０は出題者１０２がメッセージ（Ｍ）１３０２を提示してから始めて、メッセージ（Ｍ’）１３０３を見つける作業に取り掛かることとなる。
このような作業（クラッキング）が、現実的な計算機を用いて、現実的な時間、例えば数時間から数ヶ月程度で実現してしまうと、そのハッシュ関数は「ＳＰＲ性を満たさない」という。そのようなハッシュ関数はもはや安全ではない。
ＳＰＲ性はハッシュ関数が満たすべき安全性に関する最低限の条件であり、これを満たさなくなったハッシュ関数は使い物にならなくなる。
【０００７】
図１４は、ＴＣＲ性（Target Collision Resistance）を説明する図である。
（１）挑戦者１１０は、メッセージ（Ｍ）１４０２を選ぶ。
（２）次に、出題者１０２は乱数鍵（ｋ）１４０６を出題する。
（３）挑戦者１１０は、メッセージ（Ｍ）１４０２とは異なると共に、メッセージ（Ｍ）１４０２のハッシュ値Ｈｋ（Ｍ）１４０４と同じハッシュ値を出力するメッセージ（Ｍ’）１４０３を探す。メッセージ（Ｍ）１４０２及びメッセージ（Ｍ’）１４０３を探すことができれば、挑戦者１１０の勝ちである。
なお、メッセージ（Ｍ’）１４０３の探し方は問わない。実際にハッシュ値Ｈｋ（Ｍ）１４０４を算出してから、これとコリジョンを起こすメッセージ（Ｍ’）１４０３を力ずくで探す、ブルートフォースアタック（Brute Force Attack）が一般的だが、ＭＤ４が安全でなくなったように、ハッシュ関数の内部解析を行って瞬時にコリジョンを見つけることができれば、それもまた挑戦者の勝ちとなる。
このようなゲームを、ハッシュ関数における「ＴＣＲゲーム」ともいう。
【０００８】
ＴＣＲ性のポイントとして、二つのメッセージの選択・決定権は両方共挑戦者１１０の都合で決められるものの、出題者１０２から「鍵」が与えられなければハッシュ値を得られないことに注意されたい。
つまり、
・初めに挑戦者１１０がメッセージ（Ｍ）１４０２を決定し、
・その後出題者１０２が乱数鍵（ｋ）１４０６を提示する。
・その後、挑戦者１１０はメッセージ（Ｍ’）１４０３を見つける作業にとりかかる。
このことは、出題者１０２は、挑戦者１１０が提示したメッセージ（Ｍ）１４０２を見て、これを参考にして、挑戦者１１０がコリジョンを見つけ難い乱数鍵（ｋ）１４０６を提示できることを意味する。例えて言うならば、将棋等の先手・後手の関係である。
【０００９】
乱数鍵（ｋ）１４０６の存在により、ハッシュ関数１４０１の挙動を推測し難くする要素が増えることとなる。つまり、ＴＣＲ性において追加された乱数鍵ｋの存在は、ＣＲ性と比べると、出題者１０２側に有利、転じて挑戦者１１０側に不利な条件が追加されたことを意味する。
ＣＲ性では、ハッシュ関数の構造が一意に決まっているので、逆方向演算のプロセスが推測され易い、といえる。ＴＣＲ性はこれに乱数を追加することにより、ハッシュ関数の構造を乱数で拡張したに等しい効果を得て、逆方向演算のプロセスを推測され難くしている。
【００１０】
図１５は、ｅ−ＴＣＲ性（Enhanced Target Collision Resistance）を説明する図である。
（１）挑戦者１１０は、メッセージ（Ｍ）１５０２を任意に選ぶ。
（２）出題者１０２は乱数鍵（ｋ）１５０６を出題する。
（３）挑戦者１１０は、
・メッセージ（Ｍ）１５０２とは異なるメッセージ（Ｍ’）１５０３と、
・乱数鍵（ｋ）１５０６とは異なる乱数鍵（ｋ’）１５０７
の組をハッシュ関数１５０１に処理させ、ハッシュ値Ｈｋ’（Ｍ）１５０５を得る。
挑戦者１１０は、メッセージ（Ｍ）１５０２と乱数鍵（ｋ）１５０６によって得られるハッシュ値Ｈｋ（Ｍ）１５０４と同じハッシュ値を出力する、メッセージ（Ｍ’）１５０３と乱数鍵（ｋ’）１５０７の組を探す。メッセージ（Ｍ）１５０２、乱数鍵（ｋ’）１５０７及びメッセージ（Ｍ’）１５０３を探すことができれば、挑戦者１１０の勝ちである。
このようなゲームを、ハッシュ関数における「ｅ−ＴＣＲゲーム」ともいう。
ポイントとして、ＴＣＲと比較すると、出題者１０２から与えられる「鍵」とは異なる鍵を挑戦者１１０が自前で用意することができる分だけ、挑戦者１１０側に有利であることに注意されたい。
つまり、
・初めに挑戦者１１０がメッセージ（Ｍ）１５０２を決定し、
・その後出題者１０２が乱数鍵（ｋ）１５０６を提示する。
・その後、挑戦者１１０はメッセージ（Ｍ’）１５０３を見つける作業にとりかかる。
このことは、出題者１０２は、挑戦者１１０が提示したメッセージ（Ｍ）１５０２を見て、これを参考にして、挑戦者１１０がコリジョンを見つけ難い乱数鍵（ｋ）１５０６を提示できることを意味する。
【００１１】
［圧縮関数の安全性を評価する定義］
以上に述べたハッシュ関数の安全性の定義は、ほぼそのままハッシュ関数の元になる圧縮関数にも当てはまる。
圧縮関数の安全性の定義には、安全性の要求条件が高い順から、ＣＲ性、ｅ−ＳＰＲ性、ＳＰＲ性などがある。
【００１２】
攻撃者にとって、安全性の要求条件の高い圧縮関数は、安全性の要求条件の低い圧縮関数より、ゲームに勝つことが容易である。以下、このことを「破りやすい」という。
すなわち、安全性の要求条件が最も低いSPR圧縮関数が攻撃者にとって最も破りにくいということになる。
ハッシュ関数は圧縮関数から構成することを考えると、ＳＰＲ圧縮関数から構成可能なハッシュ関数が、攻撃者にとって最も破りにくいものであるといえる。
【００１３】
［圧縮関数のＣＲ性］
挑戦者が、圧縮関数に対し、任意に選んだ二つの異なるメッセージパケットｍと初期値ｃの組、及びメッセージパケットｍ’と初期値ｃ’の組を処理させる。この結果得られる圧縮値ｈ（ｍ，ｃ）と圧縮値ｈ（ｍ’，ｃ’）が同じであれば、挑戦者の勝ちである。
このような条件を、「圧縮関数のＣＲ性」と呼ぶ。そして、このようなゲームを、圧縮関数における「ＣＲゲーム」と呼ぶ。ハッシュ関数のＣＲゲームと、ゲームの条件は同じである。
ＣＲ性のポイントとして、二つのメッセージパケット及び初期値の決定権は両方共挑戦者にある点に注意されたい。つまり、挑戦者は自分の都合で、全く任意のメッセージパケット及び初期値の組を見つけることができるのである。
【００１４】
［圧縮関数のｅ−ＳＰＲ性］
（１）挑戦者は、メッセージパケットと同じビット長のランダムな値Δｉ（ｉ＝１，．．．ｌ，ｌ≧１）を選ぶ。
（２）出題者は挑戦者に対し、メッセージパケットと同じビット長のランダムな値ｒと、初期値ｃ０を与える。
（３）挑戦者はｃｉ＝ｈ（ｃｉ−１，ΔｉＸＯＲｒ）を計算する。ｉを１からｌ−１まで計算し、最終的にｃｌ−１を得る。なお、「ΔｉＸＯＲｒ」とは、Δｉとｒとの排他的論理和演算（ＸＯＲ：Exclusive Or）を意味する。
（４）挑戦者は、ｃ＝ｃｌ−１，ｍ＝ｒＸＯＲΔｌとして、圧縮値ｈ（ｍ，ｃ）を得る。
（５）挑戦者が、圧縮値ｈ（ｍ，ｃ）と等しい圧縮値ｈ（ｍ’，ｃ’）を満たすメッセージパケットｍ’及び初期値ｃ’を見つけられれば、挑戦者の勝ちである。
このような条件を、「圧縮関数のｅ−ＳＰＲ性」と呼ぶ。そして、このようなゲームを、圧縮関数における「ｅ−ＳＰＲゲーム」と呼ぶ。
【００１５】
［圧縮関数のＳＰＲ性］
（１）出題者は挑戦者に対し、メッセージパケットｍと、初期値ｃを与える。
（２）挑戦者は、圧縮値ｈ（ｍ，ｃ）を得る。
（３）挑戦者が、圧縮値ｈ（ｍ，ｃ）と等しい圧縮値ｈ（ｍ’，ｃ’）を満たすメッセージパケットｍ’及び初期値ｃ’を見つけられれば、挑戦者の勝ちである。
このような条件を、「圧縮関数のＳＰＲ性」と呼ぶ。そして、このようなゲームを、圧縮関数における「ＳＰＲゲーム」と呼ぶ。ハッシュ関数のＳＰＲゲームと、ゲームの条件は同じである。
【００１６】
図１６は、圧縮関数とハッシュ関数の関係を示す概念図である。
三種類の圧縮関数は、その種類毎に構造の複雑さ（＝実現し難さ）と安全性が、トレードオフの関係になっている。
図１６中、矢印Ｒ１６０２、Ｒ１６０３及びＲ１６０４は、圧縮関数から構成可能なハッシュ関数を意味する。
ＣＲ性ハッシュ関数は、現状の技術ではＣＲ性圧縮関数でのみ作ることができることが知られている。つまり、ＣＲ性を満たさない圧縮関数は、ＣＲ性ハッシュ関数の条件を満たさないので、現状の技術では作ることができない。
ｅ−ＴＣＲ性ハッシュ関数は、現状の技術ではｅ−ＳＰＲ性圧縮関数でのみ作ることができることが知られている。つまり、ｅ−ＳＰＲ性を満たさない圧縮関数は、ｅ−ＴＣＲ性ハッシュ関数の条件を満たさないので、現状の技術では作ることができない。
ＴＣＲ性ハッシュ関数は、現状の技術ではＳＰＲ性圧縮関数で作ることができることが知られている。つまり、ＴＣＲ性を満たさない圧縮関数は、ＴＣＲ性ハッシュ関数の条件を満たさないので、現状の技術では作ることができない。
なお、これらの事実は、研究が進展することで状況が変わる可能性があることに留意されたい。
【００１７】
ハッシュ関数におけるＣＲ性、ｅ−ＴＣＲ性、ＴＣＲ性、そしてＳＰＲ性は、ハッシュ関数に対する要求条件である。
同様に、圧縮関数におけるＣＲ性、ｅ−ＳＰＲ性、そしてＳＰＲ性は、圧縮関数に対する要求条件である。
この関係は、ハッシュ関数の構成部品である圧縮関数が、ある要求条件を満たさなくなった場合に、それよりも緩い要求条件を満たしていれば、その要求条件で構成可能なハッシュ関数を作ることができる、ということを意味する。
【００１８】
一例を挙げて説明する。
例えば、ハッシュ関数の一種であるＭＤ５は、市販のパソコンにて数１０分程度でコリジョンを生成できる実装が広まっており、もはやＣＲ性を満たさなくなってしまった。したがって、ＭＤ５はセキュアな用途に用いるハッシュ関数としては使い物にならない。
このことは、ＭＤ５を構成する圧縮関数が、ＣＲ性を満たさなくなったことを意味する。
しかし、ＭＤ５の圧縮関数がｅ−ＳＰＲ性を満たしているのであれば、ｅ−ＳＰＲ性ハッシュ関数の構成部品として流用できるのである。
そして、仮にＭＤ５の圧縮関数がｅ−ＳＰＲ性を満たさなくなったとしても、ＳＰＲ性を満たしているのならば、ＴＣＲ性ハッシュ関数の構成部品として流用できるのである。
つまり、ハッシュ関数を作るには、その構成部品である圧縮関数を一から構築しなくとも、既存の圧縮関数を流用し、ハッシュ関数の構成方法を研究して実現すればよい。
【００１９】
図１７は、ハッシュ関数の種類と、実現し難さの概念を説明する図である。
ハッシュ関数に求められる条件が厳しくなればなるほど、構造が複雑なものになり、その条件をクリアするハッシュ関数は少なくなる。
【００２０】
［電子署名とは］
図１８は、電子署名の概念を説明する図である。
電子メールを例にとって説明する。
電子メールのメッセージ（本文）１８０２は、ハッシュ関数１８０３を通じてメッセージダイジェストに変換される。
署名関数１８０４は、メッセージダイジェストとメール送信者の秘密鍵１８０５をその入力として、署名データ１８０６を出力する。
電子メール１８０７は、本文１８０２と署名データ１８０６を添付したＭＩＭＥマルチパート形式にて作成された後、送信者１８０８から受信者１８０９に向けて送信される。
受信者１８０９は、受信した電子メール１８０７の本文１８０２と署名データ１８０６を、メール送信者の公開鍵１８１０と共に電子署名検証装置１８１１に入力させる。
電子署名検証装置１８１１は、電子メールの本文１８０２が改竄されていないか否かを、署名データ１８０６と公開鍵１８１０を基に検証を行い、検証結果を出力する。
【００２１】
次に、電子署名検証装置１８１１の仕組みを説明する。
電子署名検証装置１８１１は、先ず、署名データ１８０６と公開鍵１８１０を用いて、メッセージダイジェストを得る。
一方、電子署名装置１８０１の内部にあるものと同じハッシュ関数１８０３もあり、このハッシュ関数１８０３に本文１８０２を入力し、メッセージダイジェストを得る。
こうして、署名データ１８０６から復元したメッセージダイジェストと、受信した本文をハッシュ関数１８０３に通して得たメッセージダイジェストとを付き合わせ（verify）、合致していれば、本文の改ざんは行われていないといえる。
【００２２】
電子署名における標準の安全性定義として、ＥＵＦ−ＡＣＭＡ（Existential Unforgeability under Adaptive Chosen Message Attack：「適応的選択文書攻撃に対して存在的偽造不可能」）という尺度がある。つまり、これから作る電子署名装置は、これを達成できればいい。
ＥＵＦ−ＡＣＭＡを満たす電子署名装置であれば、装置内の構成、即ち演算ステップ数等は少ないほうが望ましい。
安全性の要求条件が低い圧縮関数から構成したハッシュ関数を用いた電子署名装置でも、ＥＵＦ−ＡＣＭＡを満たすのならば、安全性の要求条件が高いハッシュ関数よりも攻撃者にとって破ることが難しい。
【００２３】
図１８では、ＣＲ性ハッシュ関数を用いた場合の電子署名装置を説明した。
前述の通り、ＣＲ性ハッシュ関数は作り難い。
そこで、安全性の要求条件が低いハッシュ関数を用いた電子署名装置のバリエーションを以下に列挙し、説明する。
【００２４】
図１９（ａ）及び（ｂ）は、ＴＣＲハッシュ関数を用いた電子署名装置のブロック図と、作成されるメッセージ群である。
図１９（ａ）において、メッセージ（Ｍ）１９０２は、ＴＣＲハッシュ関数器１９０３に入力される。
ＴＣＲハッシュ関数器１９０３には、乱数鍵（ｋ）１９０４も入力される。
ＴＣＲハッシュ関数器１９０３が出力するメッセージダイジェストと、乱数鍵（ｋ）１９０４が、署名関数器１９０５に入力され、署名関数出力（Ｓ）１９０６を出力する。電子署名は、乱数鍵（ｋ）１９０４と署名関数出力（Ｓ）１９０６の組になる。
図１９（ｂ）において、メッセージ群は、メッセージ（Ｍ）１９０２と、電子署名を構成する乱数鍵（ｋ）１９０４と署名関数出力（Ｓ）１９０６の組になる。
【００２５】
ここで、電子署名の一部を構成する乱数鍵（ｋ）１９０４は固定長ではなく、メッセージ（Ｍ）１９０２の長さに依存する。署名関数は本来固定長データを受け入れるように作られており、任意長のデータを与えると、それだけ演算量が増える。したがって、演算効率が悪い。署名関数はハッシュ関数に比べると演算量が膨大で時間が掛かるので、署名関数の演算効率の悪さは実用上に悪影響を及ぼす。
【００２６】
図２０は、ＴＣＲハッシュ関数を用いた電子署名装置のブロック図と、作成されるメッセージ群である。
これは図１９に示した電子署名装置の問題点に対する解決策の一つである。
図２０（ｃ）において、メッセージ（Ｍ）２００２は、第１のＴＣＲハッシュ関数器２００３に入力される。
第１のＴＣＲハッシュ関数器２００３には、乱数鍵（ｋ１）２００４も入力される。
第１のＴＣＲハッシュ関数器２００３が出力するメッセージダイジェストと、乱数鍵（ｋ１）２００４は、更に第２のＴＣＲハッシュ関数器２００５に入力される。
第２のＴＣＲハッシュ関数器２００５には、乱数鍵（ｋ２）２００６も入力される。
第２のＴＣＲハッシュ関数器２００５が出力するメッセージダイジェストと、乱数鍵（ｋ２）２００６が、署名関数器２００７に入力され、署名関数出力（Ｓ）２００８を出力する。電子署名は、乱数鍵（ｋ１）２００４と乱数鍵（ｋ２）２００６と署名関数出力（Ｓ）２００８の組になる。
図２０（ｄ）において、メッセージ群は、メッセージ（Ｍ）２００２と、電子署名を構成する乱数鍵（ｋ１）２００４と乱数鍵（ｋ２）２００６と署名関数出力（Ｓ）２００８の組になる。
【００２７】
図１９の方式に比べると、乱数鍵（ｋ２）２００６の長さは乱数鍵（ｋ）１９０４よりも短くなっている。しかし、第２のＴＣＲハッシュ関数器に入力されることから、乱数鍵（ｋ２）２００６も固定長ではなく、メッセージ（Ｍ）２００２の長さに依存する。したがって、図１９の方式よりは改善されているものの、依然として演算効率が悪い。
【００２８】
図２１は、ＴＣＲハッシュ関数を用いた電子署名装置のブロック図と、作成されるメッセージ群である。
これは図１９に示した電子署名装置の問題点に対する解決策のもう一つである。
図２１（ｅ）において、メッセージ（Ｍ）２１０２は、ＴＣＲハッシュ関数器２１０３に入力される。
ＴＣＲハッシュ関数器２１０３には、乱数鍵（ｋ）２１０４も入力される。
乱数鍵（ｋ）２１０４は、ＳＰＲハッシュ関数器２１０５に入力される。
ＳＰＲハッシュ関数器２１０５には、公開鍵（ｐ）２１０６も入力される。
ＴＣＲハッシュ関数器２１０３が出力するメッセージダイジェストと、ＳＰＲハッシュ関数器２１０５が出力するメッセージダイジェストが、署名関数器２１０７に入力され、署名関数出力（Ｓ）２１０８を出力する。電子署名は、乱数鍵（ｋ）２１０４と署名関数出力（Ｓ）２１０８の組になる。
図２１（ｆ）において、メッセージ群は、メッセージ（Ｍ）２１０２と、電子署名を構成する乱数鍵（ｋ）２１０４と署名関数出力（Ｓ）２１０８の組になる。そして、これとは別に、公開鍵（ｐ）２１０６が存在する。
【００２９】
図１９の方式に比べると、署名関数２１０７には固定長のメッセージダイジェストのみが入力されるので、署名関数の部分だけを見ると、演算効率は良い。しかし、公開鍵ｐが乱数鍵ｋとは異なる決定方法である。
現在、ＳＰＲハッシュ関数器をＳＰＲ圧縮関数から構成する方式は存在しない。このため、ＳＰＲハッシュ関数器２１０５を構成する圧縮関数は、ｅ−ＳＰＲ圧縮関数等の、ＳＰＲ圧縮関数よりも要求条件の高い圧縮関数に限定されてしまうので、設計し難い。また、利用可能な圧縮関数が限定されることに伴い、効率性を担保し難い。
【００３０】
図２２は、ｅ−ＴＣＲハッシュ関数を用いた電子署名装置のブロック図である。
図２２（ｇ）において、メッセージ（Ｍ）２２０２は、ｅ−ＴＣＲハッシュ関数器２２０３に入力される。
ｅ−ＴＣＲハッシュ関数器２２０３には、乱数鍵（ｋ）２２０４も入力される。
ｅ−ＴＣＲハッシュ関数器２２０３が出力するメッセージダイジェストが、署名関数器２２０５に入力され、署名関数出力（Ｓ）２２０６を出力する。電子署名は、乱数鍵（ｋ）２２０４と署名関数出力（Ｓ）２２０６の組になる。
図２２（ｈ）において、メッセージ群は、メッセージ（Ｍ）２２０２と、電子署名を構成する乱数鍵（ｋ）２２０４と署名（Ｓ）２２０６の組になる。
【００３１】
ここで、乱数鍵（ｋ）２２０４は固定長ではないものの、署名関数器２２０５には入力されない。このため、署名関数の部分だけを見ると演算効率は良い。しかし、ｅ−ＴＣＲハッシュ関数は、ＳＰＲ圧縮関数よりも種類が少ない、ｅ−ＳＰＲ圧縮関数等の、厳しい要求条件を満たす圧縮関数からしか作れない。つまり、ＳＰＲ圧縮関数から作ることができない（ＳＰＲ圧縮関数から作られるｅ−ＴＣＲハッシュ関数は未だ存在しない。）。このため、ＳＰＲ圧縮関数から構成したハッシュ関数器よりも破られやすい。また、利用可能な圧縮関数が限定されることに伴い、効率性を担保し難い。
【００３２】
なお、電子署名に関する先行技術文献を特許文献１に、本願発明の基礎技術を非特許文献１に示す。
【特許文献１】特開２００６−１２１５０３号公報
【非特許文献１】Victor Shoup, “A Composition Theorem for Universal One-Way Hash Functions”, EUROCRYPT 2000, pp445.452.
【発明の開示】
【発明が解決しようとする課題】
【００３３】
［電子署名における課題］
背景技術において説明したように、電子署名に要求される安全性を満たす、演算効率の良いハッシュ関数は未だ存在しない。
【００３４】
本発明はかかる点に鑑みてなされたものであり、比較的容易に作成できる圧縮関数から構築でき、署名関数との親和性が高く、全体として演算効率が良い、電子署名に適したハッシュ関数装置、ハッシュ値演算方法、ハッシュ値演算プログラム、そしてこれを用いた電子署名装置、電子署名方法、電子署名演算プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３５】
上記課題を解決するための本発明は、等長ＴＣＲハッシュ関数器と、固定長鍵を生成する固定長鍵生成部と、等長ＴＣＲハッシュ関数器の出力と、固定長鍵を受け、等長ＴＣＲハッシュ関数器の出力とビット長が等しいデータを出力する直列処理部とよりなるハッシュ関数装置にかかるものである。
【００３６】
本発明のｒ−ｅ−ＴＣＲハッシュ関数Ｈは、等長ＴＣＲハッシュ関数、直列処理部、並列処理部の３つのパーツから構成する。
先ず、ｒ−ｅ−ＴＣＲハッシュ関数Ｈの任意長鍵ｋを、鍵ｋ＝（ｋ１｜｜ｋ２）に分解する。そして更にｋ１を、ｋ１＝（ｋ１＊｜｜ｋ１＊＊）に分解する。
このように任意長鍵の鍵成分を分解する理由は、等長ＴＣＲハッシュ関数で衝突を排除できなかったケースを、直列処理部と並列処理部で排除するためである。
以下、それぞれの部分の役割について説明する。
【００３７】
［等長ＴＣＲハッシュ関数］
等長ＴＣＲハッシュ関数は、ハッシュ関数への入力メッセージと、鍵の一部ｋ１を用いて動作する。このとき、等長ＴＣＲハッシュ関数の性質により、
・Ｍ≠Ｍ’且つ
・｜Ｍ｜＝｜Ｍ’｜且つ
・ｋ１＝ｋ１’
のときは、Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となるＭ及びＭ’を見つけることは困難である。
このことにより、等長ＴＣＲハッシュ関数では排除できない衝突のケースとして、以下のケースが考えられる。
［ケース１］
・｜Ｍ｜＝｜Ｍ’｜且つ
・ｋ１≠ｋ１’（但し、ｋ１＊≠ｋ１＊’、ｋ１＊＊＝ｋ１＊＊’）
の場合に、Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となる、Ｍ及びＭ’が存在するケース。
［ケース２］
・｜Ｍ｜≠｜Ｍ’｜
の場合に、Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となる、Ｍ及びＭ’が存在するケース。
［ケース３］
・｜Ｍ｜＝｜Ｍ’｜且つ
・ｋ１≠ｋ１’（但し、ｋ１＊＊≠ｋ１＊＊’）
の場合に、Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となる、Ｍ及びＭ’が存在するケース。
そこで、これらのケースを排除するために、並列処理部と直列処理部を用いる。
並列処理部は「ケース１」を排除するためのものであり、直列処理部は「ケース２と３」を排除するためのものである。
【００３８】
［並列処理部］
並列処理部の入力は、鍵の一部のｋ１＊である。
ここで、ｋ１＊を入力したときの並列処理部の出力をｐとし、ｋ１＊’を入力したときの並列処理部の出力をｐ’とする。
ｋ１＊が与えられたとき、ｐ＝ｐ’となるｋ１＊’を見つけるのが困難とする。
並列処理部のこの性質を「等長ＳＰＲ性」とよぶ。
この条件を並列処理部に要請することで、
・Ｍ≠Ｍ’且つ
・｜Ｍ｜＝｜Ｍ’｜且つ
・ｋ１≠ｋ１’（ｋ１＊≠ｋ１＊’、ｋ１＊＊＝ｋ１＊＊’）の場合に、
Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となるＭ及びＭ’を見つけること（「ケース１」）を困難にすることができる。
この証明は、並列処理部にｋ１＊を入力していることによって保証できることに注意されたい。
【００３９】
［直列処理部］
直列処理部の入力を、等長ＴＣＲハッシュ関数の出力値、並列処理部の出力値ｐ、ｋ１＊＊、Ｍの長さの情報、すなわち｜Ｍ｜とする。
直列処理部に｜Ｍ｜を入力することにより、ケース２の｜Ｍ｜を用いた衝突を排除でき、ｋ１＊＊を入力することにより、ケース３のｋ１＊＊を用いた衝突を排除することができる。
よって、直列処理部で
・［ケース２］の｜Ｍ｜≠｜Ｍ’｜の場合にＨｋ（Ｍ）＝Ｈｋ’（Ｍ’）となる、
または
・［ケース３］の｜Ｍ｜＝｜Ｍ’｜且つｋ１≠ｋ１’、（ｋ１＊＊≠ｋ１＊＊’）の場合に、Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となる
Ｍ及びＭ’を見つけることを困難にすることができる。
以上が３つの部分の役割である。
【００４０】
以上の構成により、等長ＴＣＲハッシュ関数と並列処理部と直列処理部を組み合わせるとｒ−ｅ−ＴＣＲ性の範囲内で、全てのパターンにおいてコリジョンの発見を防ぐことができる。
【００４１】
ＴＣＲハッシュ関数の欠点である、署名関数との相性の悪さを改善すると共に、コリジョンの発見をし難くするために、ＴＣＲハッシュ関数に元々備わっている任意長乱数鍵に加え、直列処理部において固定長乱数鍵を追加した。
この処理により、ＳＰＲ圧縮関数で構成されるｒ−ｅ−ＴＣＲハッシュ関数で、署名関数に固定長の入力を与えることを実現した。
【発明の効果】
【００４２】
本発明により、比較的容易に作成できる圧縮関数から構築でき、署名関数との親和性が高く、全体として演算効率が良く、安全である、電子署名に適したハッシュ関数装置、ハッシュ値演算方法、ハッシュ値演算プログラム、そしてこれを用いた電子署名装置、電子署名方法、電子署名演算プログラムを提供できる。
【発明を実施するための最良の形態】
【００４３】
以下、本発明の実施の形態を、図１〜図２２を参照して説明する。
【００４４】
図１は、本実施の形態の例である、ｒ−ｅ−ＴＣＲ（relaxed enhanced Target Collision Resistance：発明者による命名である。）ハッシュ関数の定義を示す概念図である。
ハッシュ関数におけるｒ−ｅ−ＴＣＲ性とは、以下の定義を満たす関数である。
（１）クラッカー（cracker）ともいえる挑戦者１１０は、メッセージ（Ｍ）１０７を任意に選ぶ。
（２）オラクル（oracle）ともいえる出題者１０２は、任意長乱数鍵（ｋ１）１０３及び固定長乱数鍵（ｋ２）１０４を出題する。
（３）挑戦者１１０は、ハッシュ関数１１１に対し、先に（１）にて選んだメッセージ（Ｍ）１０７を任意長乱数鍵（ｋ１）１０３及び固定長乱数鍵（ｋ２）１０４と共に処理させる。そして、これによって得られるハッシュ値１０５と同じハッシュ値１０６を出力するメッセージ（Ｍ’）１０８及び任意長乱数鍵（ｋ１’）１０９を探す。条件を満たすメッセージ（Ｍ）１０７、メッセージ（Ｍ’）１０８及び任意長乱数鍵（ｋ１’）１０９の組を探すことができれば、挑戦者１１０の勝ちである。
これを「ｒ−ｅ−ＴＣＲゲーム」とも言える旨、ここに定義する。
ポイントとして、図１５に表されるｅ−ＴＣＲと比較すると、出題者１０２から与えられる「鍵」が、任意長乱数鍵（ｋ１）１０３及び固定長乱数鍵（ｋ２）１０４と、増えている。
【００４５】
図２は、本実施の形態の例である、ｒ−ｅ−ＴＣＲハッシュ関数器の全体ブロック図である。
ｒ−ｅ−ＴＣＲハッシュ関数器２０１は、任意長メッセージ（Ｍ）１０７を入力され、固定長のハッシュ値データ（メッセージダイジェスト）２０２を出力する。
メッセージ（Ｍ）１０７は、その長さを取得するために、記憶部２０３に格納される。
メッセージ長検出部２０４は、記憶部２０３に格納されているメッセージ（Ｍ）１０７の長さ（メッセージ長）｜Ｍ｜を取得する。
メッセージ長検出部２０４から出力されるメッセージ長データ｜Ｍ｜は、任意長鍵生成部２０５に入力される。
任意長鍵生成部２０５は、メッセージ長データ｜Ｍ｜を受けて、所定の条件によって制約される任意長乱数鍵（ｋ１）１０３を生成する。任意長鍵生成部２０５の詳細な中身については後述する。
【００４６】
任意長乱数鍵（ｋ１）１０３は、等長ＴＣＲハッシュ関数器２０６に入力される。
等長ＴＣＲハッシュ関数器２０６は、任意長乱数鍵（ｋ１）１０３とメッセージ（Ｍ）１０７を入力され、メッセージダイジェストを出力する。等長ＴＣＲハッシュ関数器２０６の詳細な中身については後述する。
なお、メッセージ長検出部２０４及び任意長鍵生成部２０５は、等長ＴＣＲハッシュ関数器２０６に本来的に備わっているものを明示的に表示しているものである。
【００４７】
一方、任意長乱数鍵（ｋ１）１０３は、ビット長分割部２０７にも入力される。
ビット長分割部２０７は、任意の長さよりなる任意長乱数鍵（ｋ１）１０３の、下位ビットから所定ビット数を境に分割する。このビット数は、ｒ−ｅ−ＴＣＲハッシュ関数器２０１の内部で共通に使われる、図示しないＳＰＲ圧縮関数器の入力側ビット数と出力側ビット数に依存する。
ＳＰＲ圧縮関数器の入力をｕビット、出力をｖビットとすると、ビット長分割部２０７は、任意長乱数鍵（ｋ１）１０３の下位ビットから（ｕ−ｖ）ビットで分割する。
分割した任意長乱数鍵（ｋ１）１０３の下位ビット部（（ｕ−ｖ）ビット）を「ｋ”」として、直列処理部２０８に出力する。
分割した任意長乱数鍵（ｋ１）１０３の、残る上位ビット部を「ｋ’」として、等長ＳＰＲハッシュ関数器（並列処理部）２０９に出力する。
【００４８】
並列処理部２０９は、等長ＳＰＲハッシュ関数器である。つまり、等しいメッセージ長の異なるメッセージにおいてＳＰＲ性を満たすハッシュ関数器である。ＳＰＲ性は、図１３に示すＳＰＲ性である。
並列処理部２０９では、任意の長さよりなるｋ’を受けて、２ｖの長さの値Ｐを出力する。
並列処理部２０９の内部については後述する。
【００４９】
一方、固定長鍵生成部２１０は、２ｖの長さよりなる固定長乱数鍵（ｋ２）１０４を生成する。
生成された固定長乱数鍵（ｋ２）１０４、メッセージ長データ｜Ｍ｜、任意長乱数鍵（ｋ１）１０３の下位ビット分ｋ”、そして２ｖの長さのＰは、直列処理部２０８に入力される。
直列処理部２０８は、これらの値と等長ＴＣＲハッシュ関数器２０６が出力したメッセージダイジェストを受けて、改変したｖビットのメッセージダイジェストを出力する。
【００５０】
つまり、ｒ−ｅ−ＴＣＲハッシュ関数器２０１は、等長ＴＣＲハッシュ関数器２０６が出力したメッセージダイジェストを、等長ＴＣＲハッシュ関数器２０６にて用いた任意長乱数鍵（ｋ１）１０３と、新たに生成した固定長乱数鍵（ｋ２）１０４を用いて、付加的な演算処理を施した、ともいえる。
【００５１】
図３は任意長鍵生成部２０５のブロック図である。
メッセージ長データ｜Ｍ｜は鍵長算出部３０２に入力される。
鍵長算出部３０２は、メッセージ長データ｜Ｍ｜を基に、任意長乱数鍵（ｋ１）１０３に必要な長さを求める。
鍵長｜ｋ１｜は、以下の条件が課せられる。
【００５２】
【数１】
2008233661.tif 000003
【００５３】
なお、上記数式による任意長乱数鍵（ｋ１）１０３の条件は、ｒ−ｅ−ＴＣＲハッシュ関数器２０１における条件であり、等長ＴＣＲハッシュ関数器２０６における任意長乱数鍵（ｋ１）１０３の条件は別途必要である。
そして、乱数発生器３０３は鍵長算出部３０２の制約を受けて、指定されたビット長の乱数を発生する。
【００５４】
図４は、並列処理部２０９のブロック図である。
任意長乱数鍵（ｋ１）１０３の上位ビット部ｋ’は、ビット長分割器４０２にて均等なビット長に分割される。上位ビットをｋ１’、下位ビットをｋ２’とする。任意長乱数鍵（ｋ１）１０３の上位ビット部ｋ’のビット数が奇数の場合は、ｋ２’の方がｋ１’より１ビット多くなるように分割する。
これらｋ１’及びｋ２’を、（ｕ−ｖ）ビットで割り切れるように、パディング処理部４０３及び４０４にてそれぞれパディング処理を施す。
パディング処理とは、不足するビット数を所定の方法で満たすことである。
パディング処理部４０３では、ｋ１’の上位ビットから（ｕ−ｖ）ビットで割り切れるに必要な数のビット数を下位ビットに追加する、パディング処理を施して、ｋ１”とする。
同様に、パディング処理部４０４では、ｋ２’の上位ビットから（ｕ−ｖ）ビットで割り切れるに必要な数のビット数を下位ビットに追加する、パディング処理を施して、ｋ２”とする。
パディング処理部４０３及び４０４は、実際にはメモリ等で構成される。
【００５５】
パディング処理を施したｋ１”及びｋ２”は、先頭ビットから所定のビット長毎に選択スイッチ４０５、４０６、４０７、４０８、４０９及び４１０を通じて、ＳＰＲ圧縮関数器４１１及び４１２に順次入力される。
ここで、ｋ１”はａ０、ａ１、ａ２、ａ３…ａｉと分割する。ａ０、ａ２…ａｉ−１と、添え字が偶数の要素はｖビットにて、ａ１、ａ３、ａ５…ａｉと、添え字が奇数の要素は（ｕ−２ｖ）ビットにて構成する。すなわち、ｉは必ず奇数である。
同様に、ｋ２”はｂ０、ｂ１、ｂ２、ｂ３…ｂｉと分割する。ｂ０、ｂ２…ｂｉ−１と、添え字が偶数の要素はｖビットにて、ｂ１、ｂ３、ｂ５…ｂｉと、添え字が奇数の要素は（ｕ−２ｖ）ビットにて構成する。
【００５６】
ＳＰＲ圧縮関数器４１１の（ｕ−ｖ）ビット側端子には、選択スイッチ４０５を通じて、ｋ１”の上位ビットからｕ−ｖビットずつ入力する。つまり、ａ０｜｜ａ１、ａ２｜｜ａ３、ａ４｜｜ａ５…ａｉ−１｜｜ａｉと、順番に入力する。
ＳＰＲ圧縮関数器４１１のｖビット側端子には、選択スイッチ４０６を通じて最初はｂ０を、次に選択スイッチ４０７を通じてｂ２、ｂ４、ｂ６…ｂｉ−１と、直前の圧縮関数の出力値から排他的論理和演算器４１３にて得られた排他的論理和を入力する。
【００５７】
ＳＰＲ圧縮関数器４１２の（ｕ−ｖ）ビット側端子には、選択スイッチ４０８を通じて、ｋ１”の上位ビットからｕ−ｖビットずつ入力する。つまり、ｂ０｜｜ｂ１、ｂ２｜｜ｂ３、ｂ４｜｜ｂ５…ｂｉ−１｜｜ｂｉと、順番に入力する。
ＳＰＲ圧縮関数器４１２のｖビット側端子には、選択スイッチ４０９を通じて最初はａ０を、次に選択スイッチ４１０を通じてａ２、ａ４、ａ６…ａｉ−１と、直前の圧縮関数の出力値から排他的論理和演算器４１４にて得られた排他的論理和を入力する。
【００５８】
なお、図４中のａ０｜｜ａ１とは、ａ０とａ１をビット結合することを意味する。「｜｜」は、ビット結合演算子である。
【００５９】
二つの圧縮関数器の出力をメモリよりなるビット結合器４１５にてビット結合した、長さ２ｖの値Ｐが、並列処理部２０９の出力となる。
【００６０】
図５は、並列処理部２０９のうち、圧縮関数器４１１及び４１２と、選択スイッチ４０５、４０６、４０７、４０８、４０９及び４１０よりなる繰り返し処理の部分を説明するための概念図である。繰り返し処理を横方向に概念的に展開したものである。
上段の部分は、上位ビット演算部５０２である。
下段の部分は、下位ビット演算部５０３である。
【００６１】
上位ビット演算部５０２の、最初の圧縮関数器５０４には、ａ０｜｜ａ１とｂ０が入力される。
上位ビット演算部５０２の、二番目の圧縮関数器５０５には、ａ２｜｜ａ３と、最初の圧縮関数器５０４の結果とｂ２との排他的論理和演算器５０６の演算出力が入力される。
上位ビット演算部５０２の、三番目の圧縮関数器５０７には、ａ４｜｜ａ５と、二番目の圧縮関数器５０５の結果とｂ４との排他的論理和演算器５０８の演算出力が入力される。
以下、同様に圧縮関数器による演算が続き、最後の圧縮関数器５０９には、ａｉ−１｜｜ａｉと、直前の圧縮関数器の結果とｂｉ−１との排他的論理和演算器５１０の演算出力が入力される。
図５を見てわかるように、最初の圧縮関数器５０４、二番目の圧縮関数器５０５、三番目の圧縮関数器５０７及び最後の圧縮関数器５０９は、同じ圧縮関数器４１１である。
同様に、排他的論理和演算器５０６、５０８及び５１０も、同じ排他的論理和演算器４１３である。
【００６２】
下位ビット演算部５０３の、最初の圧縮関数器５１４には、ｂ０｜｜ｂ１とａ０が入力される。
下位ビット演算部５０３の、二番目の圧縮関数器５１５には、ｂ２｜｜ｂ３と、最初の圧縮関数器５１４の結果とａ２との排他的論理和演算器５１６の演算出力が入力される。
上位ビット演算部５０２の、三番目の圧縮関数器５１７には、ａ４｜｜ａ５と、二番目の圧縮関数器５１５の結果とａ４との排他的論理和演算器５１８の演算出力が入力される。
以下、同様に圧縮関数器による演算が続き、最後の圧縮関数器５１９には、ｂｉ−１｜｜ｂｉと、直前の圧縮関数器の結果とａｉ−１との排他的論理和演算器５２０の演算出力が入力される。
図５を見てわかるように、最初の圧縮関数器５１４、二番目の圧縮関数器５１５、三番目の圧縮関数器５１７及び最後の圧縮関数器５１９は、同じ圧縮関数器４１２である。
同様に、排他的論理和演算器５１６、５１８及び５２０も、同じ排他的論理和演算器４１４である。
【００６３】
本実施形態では、並列処理部２０９を具体的に開示した。
しかしながら、並列処理部２０９の構造に限らず、ＳＰＲ圧縮関数から構成可能な等長ＳＰＲ性を満たすハッシュ関数であれば、本実施形態によるｒ−ｅ−ＴＣＲハッシュ関数の安全性を保つことができる。
そのため、本実施形態にて開示した並列処理部２０９以外のもので、ＳＰＲ圧縮関数から構成可能な等長ＳＰＲ性を満たすハッシュ関数を並列処理部２０９の代わりに用いても、ｒ−ｅ−ＴＣＲハッシュ関数は安全である。
ハッシュ関数Ｈが等長ＳＰＲ性を満たすとは、メッセージｘを与えられた時に、
・Ｈ（ｘ）＝Ｈ（ｘ‘）かつ
・｜ｘ｜＝｜ｘ’｜かつ
・ｘ≠ｘ’
となるメッセージｘ’を見つけることが困難である、という性質を満たすことである。
【００６４】
図６は、直列処理部２０８のブロック図である。
並列処理部２０９の出力Ｐは、（ｕ−ｖ）ビットに至るまで、メモリよりなるパディング処理部６０２にてゼロビットでパディング処理され、出力Ｐ’となる。
出力Ｐ’は、排他的論理和演算器６０３によって、ビット長分割部２０７の出力ｋ”と排他的論理和演算が施される。
一方、固定長乱数鍵（ｋ２）１０４は、ビット長分割部６０６によって、上位ｖビットであるｋ２０と下位ｖビットであるｋ２１に分割される。
そして、等長ＴＣＲハッシュ関数器２０６の出力ｚは、排他的論理和演算器６０４によって、ｋ２０との排他的論理和演算が施される。
これらの値が、第１段目のＳＰＲ圧縮関数器６０５に入力される。
【００６５】
入力メッセージ（Ｍ）１０７のメッセージ長｜Ｍ｜は、排他的論理和演算器６０７によって、ビット長分割部２０７の出力ｋ”と排他的論理和演算が施される。
そして、第１段目のＳＰＲ圧縮関数器６０５の出力は、排他的論理和演算器６０８によって、ｋ２１との排他的論理和演算が施される。
これらの値が、第２段目のＳＰＲ圧縮関数器６０９に入力される。
【００６６】
第２段目のＳＰＲ圧縮関数器６０９の出力は、排他的論理和演算器６１０によって、ｋ２０との排他的論理和演算が施される。
これとビット長分割部２０７の出力ｋ”が、第３段目のＳＰＲ圧縮関数器６１１に入力される。
こうして、ハッシュ値データ２０２（メッセージダイジェスト）が得られる。
【００６７】
図７は等長ＴＣＲハッシュ関数器２０６の一例を示すブロック図である。ここでは一例として、「Shoupの構造」といわれる、非特許文献１を例示する。
等長ＴＣＲハッシュ関数とは、等しいメッセージ長のメッセージに限ってＴＣＲ性を備えるハッシュ関数である。
メッセージ（Ｍ）１０７は、（ｕ−ｖ）ビットで割り切れるビット長になるために、メモリよりなるパディング処理部７０２によってゼロビットパディングが施される。
パディング処理部７０２に含まれる、（ｕ−ｖ）ビットのメッセージパケットｍ０、ｍ１．．．ｍｎは、切替えスイッチ７０３を通じて、排他的論理和演算器７０４に入力される。
一方、任意長乱数鍵（ｋ１）１０３はビット長分割部７０５によって上位（ｕ−ｖ）ビットがｋｓとしてビット長分割処理された後、このｋｓが排他的論理和演算器７０４に入力される。
等長ＴＣＲハッシュ関数として、等長ＴＣＲハッシュ関数器２０６に開示するShoupの構造を用いる場合、任意長乱数鍵（ｋ１）１０３のビット長｜ｋ１｜の条件に
Ｌ≧ｌｏｇ２（ｎ），｜ｋ１＋１｜≧Ｌ×ｖ＋（ｕ−ｖ）
が追加される。
【００６８】
メモリよりなるビット長分割部７０５によって、任意長乱数鍵（ｋ１）１０３の、ｋｓとして上位（ｕ−ｖ）ビットが更にビット長分割処理された、残りのビットよりなるデータがｋｔとされる。
このｋｔはｋｔ０、ｋｔ１、ｋｔ２．．．ｋｔＬと、Ｌ＋１個存在する。これら要素のビット長はｖビットである。Ｌは、メッセージＭの分割数をｎとして、ｌｏｇ２ｎ以上の自然数の最小値が設定される。
ビット長分割部７０５に含まれる、ｖビットのｋｔ０〜ｋｔＬは、切替えスイッチ７０６を通じて、排他的論理和演算器７０７に入力される。
切り替えスイッチ７０６は、選択制御部７０８によって切り替え制御が行われる。
排他的論理和演算器７０７のもう一方の入力には、スイッチ７０９によって、最初のステップに限り、初期値（ＩＶ）７１１が入力され、それ以降はＳＰＲ圧縮関数器７１０の出力が入力される。
【００６９】
選択制御部７０８は以下の式によってｋｔ０〜ｋｔＬを選択する。
【００７０】
【数２】
2008233661.tif 000004
【００７１】
上記数式は、「ｉを２のｊ乗で割り切れる数の中で最も大きいｊをｖ（ｉ）とする」という意味である。
今、ｊを０から増加させていくと、２のｊ乗は、１，２，４，８，１６，３２，６４，１２８，２５６，５１２，１０２４．．．となる。
これに対し、ｉを０から増加させていくと、０，１，２，３，４，５．．．である。
ｉを２のｊ乗で割った際に割り切れるｊは、ｉが奇数のときは２で割り切れないので必ずｊが０になり、ｉが偶数のときは１と２以上の値を繰り返す。具体的には、０，１，０，２，０，1，０，３，０，１，０，２，０，１．．．と続く。
こうして算出された数値が、ｋｔＬの添え字Ｌとして、切り替えスイッチ７０６の制御、転じてｋｔＬの選択に用いられる。
【００７２】
図８はＳＰＲ圧縮関数器の一例を示すブロック図である。これはＳＨＡ−１の圧縮関数として周知である。
５１２ビット（＝１６ワード）の入力メッセージは、メモリよりなるワード格納部８０２に格納され、ワードＷ０〜Ｗ１５に分割される。
その後、仮想ワード生成器８０３を通じて、ワードＷ１６〜Ｗ７９が生成される。このようにしてＷ（ｔ）が生成される。ｔは０〜７９の数を取る。
【００７３】
なお、仮想ワード生成器８０３の内部処理は以下の通りである。
【００７４】
【数３】
2008233661.tif 000005
【００７５】
すなわち、
・ｔを１６から７９まで繰り返し演算処理するものであり、
・ワード群Ｗのｔ−３番目の要素と、ｔ−８番目の要素と、ｔ−１４番目の要素と、ｔ−１６番目の要素とを全て排他的論理和演算し、
・その結果を新たなｔ番目のワード群Ｗの要素とする
のである。
【００７６】
一方、１６０ビット（＝５ワード）の直前値或は初期値は、最初に上位ビットからＨ０、Ｈ１、Ｈ２、Ｈ３及びＨ４よりなる５つの変数８０４に一時保持された後、同様に上位ビットからＡ、Ｂ、Ｃ、Ｄ及びＥよりなる５つの変数８０５に格納される。
そして、以下の演算処理を０〜７９まで、８０回繰り返す。
【００７７】
（１）最初に、ＢとＣとＤを関数ｆ（ｔ）８０６に代入し、この値とＥを剰余演算器８０７によって２３２剰余を演算する。なお、図８中の「＋」は、２３２の剰余演算である。これは換言すれば、３２ビットレジスタを用いた、桁あふれを無視した加算処理である。
（２）次に、シフト演算器８０８によってＡを５ビット左にシフトした値と、（１）の値を、剰余演算器８０９によって２３２剰余演算をする。
（３）そして、剰余演算器８１０によって、Ｗ（ｔ）と（２）の値との２３２剰余演算をする。
（４）更に、剰余演算器８１２によって、定数ｋ（ｔ）８１１と（３）の値との２３２剰余演算をする。
（５）Ｄの値をＥに代入し、新たなＥとする。
（６）Ｃの値をＤに代入し、新たなＤとする。
（７）シフト演算器８１３によってＢの値を３０ビット左にシフトした値をＣに代入し、新たなＣとする。
（８）Ａの値をＢに代入し、新たなＢとする。
（９）（４）の値をＡに代入し、新たなＡとする。
【００７８】
なお、関数ｆ（ｔ）及び定数ｋ（ｔ）は以下の通りである。
【００７９】
【数４】
2008233661.tif 000006
【００８０】
８０回の繰り返し演算で得られたＡ〜Ｅの値を、先に取っておいたＨ０〜Ｈ４の値と、それぞれ剰余演算器８１４、８１５、８１６、８１７及び８１８にて２３２剰余演算し、これを圧縮関数器の出力とする。
【００８１】
図９（ａ）及び（ｂ）は、ｒ−ｅ−ＴＣＲハッシュ関数器２０１を用いた、電子署名装置のブロック図と、生成されるメッセージ群の概略図である。
任意長メッセージ（Ｍ）１０７は任意長乱数鍵（ｋ１）１０３及び固定長乱数鍵（ｋ２）１０４と共に、ｒ−ｅ−ＴＣＲハッシュ関数器２０１に入力され、処理され、メッセージダイジェストが得られる。
メッセージダイジェストと固定長乱数鍵（ｋ２）１０４は署名関数９０２に入力され、署名関数出力（Ｓ）９０３が得られる。電子署名は、固定長乱数鍵（ｋ２）１０４、任意長乱数鍵（ｋ１）１０３、そして署名関数出力（Ｓ）９０３の組となる。
署名関数９０２は固定長のメッセージダイジェストと固定長鍵ｋ２が入力されるので、電子署名生成に要する演算処理は、任意長の入力より軽い。したがって、演算処理は高速で済む。
なお、署名関数９０２にはメッセージ作成者の秘密鍵が入力されるが、図示を省略している。
【００８２】
図９において、署名関数９０２には、固定長のメッセージダイジェストと、固定長乱数鍵（ｋ２）１０４が入力される。つまり、署名関数９０２には、固定長のデータのみ入力されることに注目されたい。このことは、演算量が多くなりがちな署名関数において非常に有利に働く。
【００８３】
図１０は、圧縮関数と、本実施形態によるｒ−ｅ−ＴＣＲハッシュ関数を含めたハッシュ関数との関係を示す概念図である。
図１０中、矢印Ｒ１００２、Ｒ１００３、Ｒ１００４及びＲ１００５は、圧縮関数から構成可能なハッシュ関数を意味する。
ＣＲ性ハッシュ関数は、ＣＲ性圧縮関数でのみ作ることができる。つまり、ＣＲ性を満たさない圧縮関数は、ＣＲ性ハッシュ関数の条件を満たさないので、作ることができない。
ｅ−ＴＣＲ性ハッシュ関数は、ｅ−ＳＰＲ性圧縮関数でのみ作ることができる。つまり、ｅ−ＳＰＲ性を満たさない圧縮関数は、ｅ−ＴＣＲ性ハッシュ関数の条件を満たさないので、作ることができない。
ＴＣＲ性ハッシュ関数は、ＳＰＲ性圧縮関数で作ることができる。つまり、ＳＰＲ性を満たさない圧縮関数は、ＴＣＲ性ハッシュ関数の条件を満たさないので、作ることができない。
ｒ−ｅ−ＴＣＲ性ハッシュ関数は、ＳＰＲ性圧縮関数で作ることができる。つまり、ＳＰＲ性を満たさない圧縮関数は、ＴＣＲ性ハッシュ関数の条件を満たさないので、作ることができない。
【００８４】
攻撃者にとって、安全性の要求条件が低い圧縮関数は要求条件の高い圧縮関数に比べ、破りにくい。
すなわち、安全性の要求条件が低い圧縮関数を用いたハッシュ関数のほうが安全であるといえる。
本実施形態のｒ−ｅ−ＴＣＲ性ハッシュ関数は、最も安全なＳＰＲ圧縮関数から作ることができる。
ただし、同じくＳＰＲ圧縮関数から構成可能なＴＣＲハッシュ関数より構造が若干複雑になっており、ハッシュ関数の演算速度だけをみると、ＴＣＲハッシュ関数の方が若干速い。
しかし、署名関数の計算量を含めたトータルの計算量で比較すると、署名関数の演算はハッシュ関数の演算に比べてはるかに重い処理である。従来技術に開示されるＴＣＲハッシュ関数を用いた署名では、署名関数に固定長出力を与えることができないため、署名関数に掛かる処理が重くなってしまう。
本実施形態によるｒ−ｅ−ＴＣＲハッシュ関数を用いると、署名関数に固定長出力を与えることができるので、署名関数に掛かる演算処理が軽く済む。このため、トータルの計算量で遥かに勝る。
【００８５】
本実施形態において、従来のＴＣＲハッシュ関数における任意長乱数鍵（ｋ１）１０３に加えて、固定長乱数鍵（ｋ２）１０４を導入し、並列処理部及び直列処理部を設けた意義を説明する。
本実施形態では、並列処理部２０９を導入し、任意長乱数鍵（ｋ１）１０３の殆どの部分を並列処理部２０９に、残りの部分を直列処理部２０８に入力することにより、任意長乱数鍵（ｋ１）１０３を署名関数に入力する必要性がなくなった。
一方、直列処理部２０８では、署名関数への入力を最小限にする役割をし、固定長乱数鍵（ｋ２）１０４を用いて処理を行う。
固定長乱数鍵（ｋ２）１０４は直列処理部２０８の安全性を保つ大きな役割を果たしている。
【００８６】
本実施形態のｒ−ｅ−ＴＣＲハッシュ関数Ｈは、等長ＴＣＲハッシュ関数、直列処理部、並列処理部の３つの部分から構成する。
先ず、ｒ−ｅ−ＴＣＲハッシュ関数Ｈの任意長鍵ｋを、鍵ｋ＝（ｋ１｜｜ｋ２）に分解する。そして更にｋ１を、ｋ１＝（ｋ１＊｜｜ｋ１＊＊）に分解する。
このように任意長鍵の鍵成分を分解する理由は、等長ＴＣＲハッシュ関数で衝突を排除できなかったケースを、直列処理部と並列処理部で排除するためである。
以下、それぞれの部分の役割について説明する。
【００８７】
［等長ＴＣＲハッシュ関数］
等長ＴＣＲハッシュ関数は、ハッシュ関数への入力メッセージと、鍵の一部ｋ１を用いて動作する。このとき、等長ＴＣＲハッシュ関数の性質により、
・Ｍ≠Ｍ’且つ
・｜Ｍ｜＝｜Ｍ’｜且つ
・ｋ１＝ｋ１’
のときは、Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となるＭ及びＭ’を見つけることは困難である。
このことにより、等長ＴＣＲハッシュ関数では排除できない衝突のケースとして、以下のケースが考えられる。
［ケース１］
・｜Ｍ｜＝｜Ｍ’｜且つ
・ｋ１≠ｋ１’（但し、ｋ１＊≠ｋ１＊’、ｋ１＊＊＝ｋ１＊＊’）
の場合に、Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となる、Ｍ及びＭ’が存在するケース。
［ケース２］
・｜Ｍ｜≠｜Ｍ’｜
の場合に、Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となる、Ｍ及びＭ’が存在するケース。
［ケース３］
・｜Ｍ｜＝｜Ｍ’｜且つ
・ｋ１≠ｋ１’（但し、ｋ１＊＊≠ｋ１＊＊’）
の場合に、Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となる、Ｍ及びＭ’が存在するケース。
そこで、これらのケースを排除するために、並列処理部と直列処理部を用いる。
並列処理部は「ケース１」を排除するためのものであり、直列処理部は「ケース２と３」を排除するためのものである。
【００８８】
［並列処理部］
並列処理部の入力は、鍵の一部のｋ１＊である。
ここで、ｋ１＊を入力したときの並列処理部の出力をｐとし、ｋ１＊’を入力したときの並列処理部の出力をｐ’とする。
ｋ１＊が与えられたとき、ｐ＝ｐ’となるｋ１＊’を見つけるのが困難とする。
並列処理部のこの性質を「等長ＳＰＲ性」とよぶ。
この条件を並列処理部に要請することで、
・Ｍ≠Ｍ’且つ
・｜Ｍ｜＝｜Ｍ’｜且つ
・ｋ１≠ｋ１’（ｋ１＊≠ｋ１＊’、ｋ１＊＊＝ｋ１＊＊’）の場合に、
Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となるＭ及びＭ’を見つけること（「ケース１」）を困難にすることができる。
この証明は、並列処理部にｋ１＊を入力していることによって保証できることに注意されたい。
【００８９】
［直列処理部］
直列処理部の入力を、等長ＴＣＲハッシュ関数の出力値、並列処理部の出力値ｐ、ｋ１＊＊、Ｍの長さの情報、すなわち｜Ｍ｜とする。
直列処理部に｜Ｍ｜を入力することにより、ケース２の｜Ｍ｜を用いた衝突を排除でき、ｋ１＊＊を入力することにより、ケース３のｋ１＊＊を用いた衝突を排除することができる。
よって、直列処理部で
・［ケース２］の｜Ｍ｜≠｜Ｍ’｜の場合にＨｋ（Ｍ）＝Ｈｋ’（Ｍ’）となる、
または
・［ケース３］の｜Ｍ｜＝｜Ｍ’｜且つｋ１≠ｋ１’、（ｋ１＊＊≠ｋ１＊＊’）の場合に、Ｈｋ（Ｍ）＝Ｈｋ’（Ｍ’）となる
Ｍ及びＭ’を見つけることを困難にすることができる。
以上が３つの部分の役割である。
【００９０】
以上の構成により、等長ＴＣＲハッシュ関数と並列処理部と直列処理部を組み合わせるとｒ−ｅ−ＴＣＲ性の範囲内で、全てのパターンにおいてコリジョンの発見を防ぐことができる。
【００９１】
本実施形態には、以下のような応用例が考えられる。
（１）図５の上位ビット演算部５０２と下位ビット演算部５０３は、入力データをたすきがけの形式にすることもできる。
上位ビット演算部５０２の（ｕ−ｖ）ビット側端子にはａ０｜｜ａ１、ｂ２｜｜ｂ３、ａ４｜｜ａ５…と、ａとｂとを交互に入力する。
上位ビット演算部５０２のｖビット側端子にはｂ０、ａ２、ｂ４…と、ｂとａとを交互に入力する。
【００９２】
（２）本実施形態のｒ−ｅ−ＴＣＲハッシュ関数は、これを構成する圧縮関数がＳＰＲ性を満たしていれば良い。このことは、ＳＰＲ性よりも安全性の要求条件が高いＣＲ性、或はｅ−ＳＰＲ性を満たす圧縮関数の利用を妨げるものではない。
【００９３】
（３）本実施形態のｒ−ｅ−ＴＣＲハッシュ関数は、公開鍵暗号を生成する手段として利用することもできる。
【００９４】
上述の実施形態では、署名関数の入力ビット長が３ｖビット（＝「ｒ−ｅ−ＴＣＲハッシュ関数の出力であるハッシュ値ｖビット」＋「固定長乱数鍵（ｋ２）１０４の２ｖビット」）であった。
更に署名関数への入力長を短くしたい場合には、固定長乱数鍵（ｋ２）１０４の代わりに、圧縮関数ｈ（ｋ２，ｋｐ）を署名関数の入力とすることができる。こうすると、署名関数の入力ビット長は２ｖビット（＝「ｒ−ｅ−ＴＣＲハッシュ関数の出力であるハッシュ値ｖビット」＋「圧縮関数ｈ（ｋ２，ｋｐ）の出力ｖビット」）になる。
ここで、ｋｐは任意長乱数鍵（ｋ１）１０３の先頭ビットから（ｕ−２ｖ）ビット分とったものとする。すなわち、（ｋ１，ｋ２，σ（ｈ（ｋ２，ｋｐ）｜｜Ｈｋ（Ｍ）））（σは署名関数）が文書Ｍに対する署名になる。固定長乱数鍵（ｋ２）１０４及びｋｐは署名者によってランダムに選ばれるので、圧縮関数ｈがＳＰＲ圧縮関数であれば、ｒ−ｅ−ＴＣＲハッシュ関数自体の安全性を保障できる。
【００９５】
本実施形態においては、安全性の要求条件が低いＳＰＲ圧縮関数器で構成でき、且つ署名関数器における演算効率が良い、実用的な電子署名装置、及びそのためのハッシュ関数装置を実現できる。
本実施形態のハッシュ関数装置は、ＳＰＲ圧縮関数器で構築できるので、多くの圧縮関数を利用可能である。例えば、ＣＲ性を満たさなくなったハッシュ関数の圧縮関数であっても良い。この点はＴＣＲハッシュ関数に共通する利点である。
これに加えて、本実施形態のハッシュ関数装置は、従来のＴＣＲハッシュ関数では払拭できなかった、署名関数器との親和性の悪さを、等長ＴＣＲハッシュ関数に若干の演算処理を追加することと、固定長乱数鍵を導入することで解決した。
【００９６】
以上、本発明の実施形態例について説明したが、本発明は上記実施形態例に限定されるものではなく、特許請求の範囲に記載した本発明の要旨を逸脱しない限りにおいて、他の変形例、応用例を含むことは言うまでもない。
【図面の簡単な説明】
【００９７】
【図１】本発明の一実施の形態によるｒ−ｅ−ＴＣＲハッシュ関数の定義を示す概念図である。
【図２】本実施の形態の例である、ｒ−ｅ−ＴＣＲハッシュ関数器の全体ブロック図である。
【図３】任意長鍵生成部のブロック図である。
【図４】並列処理部のブロック図である。
【図５】並列処理部のうち、圧縮関数器と、選択スイッチよりなる繰り返し処理の部分を説明するための概念図である。
【図６】直列処理部のブロック図である。
【図７】等長ＴＣＲハッシュ関数器の一例を示すブロック図である。
【図８】ＳＰＲ圧縮関数器の一例を示すブロック図である。
【図９】ｒ−ｅ−ＴＣＲハッシュ関数器を用いた電子署名装置のブロック図と、生成されるメッセージ群の概略図である。
【図１０】圧縮関数と、本実施形態によるｒ−ｅ−ＴＣＲハッシュ関数を含めたハッシュ関数との関係を示す概念図である。
【図１１】ハッシュ関数の概略図である。
【図１２】ＣＲ性を説明する図である。
【図１３】ＳＰＲ性を説明する図である。
【図１４】ＴＣＲ性を説明する図である。
【図１５】ｅ−ＴＣＲ性を説明する図である。
【図１６】圧縮関数とハッシュ関数の関係を示す概念図である。
【図１７】ハッシュ関数の種類と、実現し難さの概念を説明する図である。
【図１８】電子署名の概念を説明する図である。
【図１９】ＴＣＲハッシュ関数を用いた電子署名装置のブロック図と、作成されるメッセージ群である。
【図２０】ＴＣＲハッシュ関数を用いた電子署名装置のブロック図と、作成されるメッセージ群である。
【図２１】ＴＣＲハッシュ関数を用いた電子署名装置のブロック図と、作成されるメッセージ群である。
【図２２】ｅ−ＴＣＲハッシュ関数を用いた電子署名装置のブロック図と、作成されるメッセージ群である。
【符号の説明】
【００９８】
１０２…出題者、１０３…任意長乱数鍵（ｋ１）、１０４…固定長乱数鍵（ｋ２）、１０５、１０６…ハッシュ値、１０７、１２０２、１３０２、１４０２、１５０２、１９０２、２００２、２１０２、２２０２…メッセージ（Ｍ）、１０８、１２０３、１３０３、１４０３、１４０３、１５０３…メッセージ（Ｍ’）、１０９…任意長乱数鍵（ｋ１’）、１１０…挑戦者、１１１…ハッシュ関数、２０１…ｒ−ｅ−ＴＣＲハッシュ関数器、２０２…ハッシュ値データ（メッセージダイジェスト）、２０３…記憶部、２０４…メッセージ長検出部、２０５…任意長鍵生成部、２０６…等長ＴＣＲハッシュ関数器、２０７、６０６、７０５…ビット長分割部、２０８…直列処理部、２０９…並列処理部、２１０…固定長鍵生成部、３０２…鍵長算出部、３０３…乱数発生器、４０２…ビット長分割器、４０３、４０４、６０２、７０２…パディング処理部、４０５、４０６、４０７、４０８、４０９、４１０…選択スイッチ、４１１、４１２、７１０…ＳＰＲ圧縮関数器、４１３、４１４、５０６、５０８、５１０、５１６、５１８、５２０、６０３、６０４、６０７、６０８、６１０、７０４、７０７…排他的論理和演算器、４１５…ビット結合器、５０２…上位ビット演算部、５０３…下位ビット演算部、５０４、５１４…最初の圧縮関数器、５０５、５１５…二番目の圧縮関数器、５０７、５１７…三番目の圧縮関数器、５０９、５１９…最後の圧縮関数器、６０５…第１段目のＳＰＲ圧縮関数器、６０９…第２段目のＳＰＲ圧縮関数器、６１１…第３段目のＳＰＲ圧縮関数器、７０３、７０６…切替えスイッチ、７０８…選択制御部、７０９、１１０７…スイッチ、７１１、１１０６…初期値（ＩＶ）、８０２…ワード格納部、８０３…仮想ワード生成器、８０４、８０５…変数、８０６…関数ｆ（ｔ）、８０７、８０９、８１０、８１２…剰余演算器、８０８…シフト演算器、８１１…定数ｋ（ｔ）、８１３…シフト演算器、９０２、１８０４…署名関数、９０３…署名関数出力（Ｓ）、Ｒ１００２、Ｒ１００３、Ｒ１００４、Ｒ１００５…矢印、１１０１、１２０１、１４０１、１５０１、１８０３…ハッシュ関数、１１０２…メッセージ、１１０３…メッセージダイジェスト、１１０４…データブロック群、１１０５…圧縮関数（ｈ）、１２０４、１３０４…ハッシュ値Ｈ（Ｍ）、１２０５…ハッシュ値Ｈ（Ｍ’）、１４０６、１５０６、１９０４、２１０４、２２０４…乱数鍵（ｋ）、１５０７…乱数鍵（ｋ’）、１４０４…ハッシュ値Ｈｋ（Ｍ）、Ｒ１６０２、Ｒ１６０３、Ｒ１６０４…矢印、１８０２…メッセージ（本文）、１８０５…秘密鍵、１８０６…署名データ、１８０７…電子メール、１８０８…送信者、１８０９…受信者、１８１０…公開鍵、１８１１…電子署名検証装置、１９０３…ＴＣＲハッシュ関数器、１９０５、２００７、２１０７、２２０５…署名関数器、１９０６、２００８、２１０８、２２０６…署名（Ｓ）、２００３…第１のＴＣＲハッシュ関数器、２００４…乱数鍵（ｋ１）、２００５…第２のＴＣＲハッシュ関数器、２００６…乱数鍵（ｋ２）、２１０３…ＴＣＲハッシュ関数器、２１０５…ＳＰＲハッシュ関数器、２１０６…公開鍵（ｐ）、２２０３…ｅ−ＴＣＲハッシュ関数器
【図１】
2008233661.tif 000007
【図２】
2008233661.tif 000008
【図３】
2008233661.tif 000009
【図４】
2008233661.tif 000010
【図５】
2008233661.tif 000011
【図６】
2008233661.tif 000012
【図７】
2008233661.tif 000013
【図８】
2008233661.tif 000014
【図９】
2008233661.tif 000015
【図１０】
2008233661.tif 000016
【図１１】
2008233661.tif 000017
【図１２】
2008233661.tif 000018
【図１３】
2008233661.tif 000019
【図１４】
2008233661.tif 000020
【図１５】
2008233661.tif 000021
【図１６】
2008233661.tif 000022
【図１７】
2008233661.tif 000023
【図１８】
2008233661.tif 000024
【図１９】
2008233661.tif 000025
【図２０】
2008233661.tif 000026
【図２１】
2008233661.tif 000027
【図２２】
2008233661.tif 000028