(57)【要約】【課題】ランダムオラクルモデルで安全な任意の暗号アルゴリズムを原像計算困難性がないランダムオラクルモデルで安全な暗号アルゴリズムに変換する。【解決手段】暗号アルゴリズムＣからハッシュ関数Ｈが呼び出されたとき、加工関数ｆは、ハッシュ関数Ｈの入力Ｍに固定値ｃを付加した値「ｃ｜｜Ｍ」をハッシュ関数Ｈに入力する。ハッシュ関数Ｈは「ｃ｜｜Ｍ」のハッシュ値Ｈ（ｃ｜｜Ｍ）を出力し、暗号アルゴリズムＣはハッシュ値Ｈ（ｃ｜｜Ｍ）を計算に使用する。【選択図】図２
2010276736.tif 000002
【特許請求の範囲】
【請求項１】
対象データに付加データを付加した対象加工データを暗号アルゴリズムＣＰＵを用いて生成する対象加工データ生成部と、
前記対象加工データ生成部により生成された対象加工データをハッシュ関数の入力としてハッシュ値を暗号アルゴリズムＣＰＵを用いて算出するハッシュ値算出部と、
前記ハッシュ値算出部により算出されたハッシュ値に基づいて前記対象データに対する暗号処理を暗号アルゴリズムＣＰＵを用いて実行する暗号処理部と
を備えたことを特徴とする暗号処理装置。
【請求項２】
前記対象加工データ生成部は、前記付加データとして固定データを前記対象データに付加して前記対象加工データを生成する
ことを特徴とする請求項１記載の暗号処理装置。
【請求項３】
前記対象加工データ生成部は、前記付加データとして前記対象データに含まれる部分データを前記対象データに付加して前記対象加工データを生成する
ことを特徴とする請求項１記載の暗号処理装置。
【請求項４】
前記対象加工データ生成部は、前記部分データとして前記対象データの先頭に位置する先頭データを前記対象データに付加して前記対象加工データを生成する
ことを特徴とする請求項３記載の暗号処理装置。
【請求項５】
前記対象加工データ生成部は、前記部分データとして前記対象データの末尾に位置する末尾データを前記対象データに付加して前記対象加工データを生成する
ことを特徴とする請求項３記載の暗号処理装置。
【請求項６】
前記対象加工データ生成部は、前記付加データを前記対象データの前に付加して前記対象加工データを生成する
ことを特徴とする請求項１〜請求項５いずれかに記載の暗号処理装置。
【請求項７】
前記対象加工データ生成部は、前記付加データを前記対象データの後ろに付加して前記対象加工データを生成する
ことを特徴とする請求項１〜請求項５いずれかに記載の暗号処理装置。
【請求項８】
前記対象加工データ生成部は、入力データに前記付加データが含まれる場合、前記入力データを前記対象加工データとし、入力データに前記付加データが含まれない場合、前記入力データを前記対象データとして前記対象加工データを生成する
ことを特徴とする請求項１〜請求項７いずれかに記載の暗号処理装置。
【請求項９】
対象加工データ生成部が、対象データに付加データを付加した対象加工データを暗号アルゴリズムＣＰＵを用いて生成し、
ハッシュ値算出部が、前記対象加工データ生成部により生成された対象加工データをハッシュ関数の入力としてハッシュ値を暗号アルゴリズムＣＰＵを用いて算出し、
暗号処理部が、前記ハッシュ値算出部により算出されたハッシュ値に基づいて前記対象データに対する暗号処理を暗号アルゴリズムＣＰＵを用いて実行する
ことを特徴とする暗号処理装置の暗号処理方法。
【請求項１０】
請求項９記載の暗号処理方法をコンピュータに実行させる暗号処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュ関数を用いた暗号アルゴリズムを実行する暗号処理装置、暗号処理装置の暗号処理方法および暗号処理プログラムに関するものである。
【背景技術】
【０００２】
ハッシュ関数の危殆により、ハッシュ関数を用いた暗号アルゴリズムの安全性が問題となる。通常、暗号アルゴリズムは、理想ハッシュ関数であるランダムオラクルモデルで安全である。
【０００３】
ランダムオラクルは理想的なハッシュ関数である。定義は以下のとおり。
【０００４】
「Ｘ」をハッシュ関数の入力の集合、「Ｙ」をハッシュ関数の出力（ハッシュ値）の集合とする。ＸからＹへ移すハッシュ関数の集合を「Ｆ」とおく。
ランダムオラクルは、Ｆからランダムに選んだ１つのハッシュ関数である。
【０００５】
安全なハッシュ関数は「（１）衝突困難性」「（２）第二原像計算困難性」および「（３）原像計算困難性」を満たす。
各性質（１）〜（３）の定義は以下のとおりである。以下の定義において、「Ｈ」はハッシュ関数、「Ｍ」「Ｍ’（≠Ｍ）」はハッシュ関数Ｈの入力値、「Ｈ（ｘ）」はｘを入力したハッシュ関数Ｈの出力（ハッシュ値）を示す。
【０００６】
（１）衝突困難性を満たすハッシュ関数とは、「Ｈ（Ｍ）＝Ｈ（Ｍ’）」となる２つの入力値Ｍ、Ｍ’を見つけることが困難なハッシュ関数である。つまり、衝突困難性とは、ハッシュ値が同じである複数の入力値を求めることが難しいという性質のことである。
（２）第二原像計算困難性を満たすハッシュ関数とは、ランダムな入力値Ｍが与えられたとき、「Ｈ（Ｍ）＝Ｈ（Ｍ’）」を満たす入力値Ｍ’を見つけることが困難なハッシュ関数である。つまり、第二原像計算困難性とは、第１の入力値とハッシュ値が同じである第２の入力値を求めることが難しいという性質のことである。
（３）原像計算困難性を満たすハッシュ関数とは、ランダムな値ｚが与えられたとき、「ｚ＝Ｈ（Ｍ）」を満たすＭを見つけることが困難なハッシュ関数である。つまり、原像計算困難性とは、ハッシュ値に対応する入力値を求めることが難しいという性質のことである。
【０００７】
上記（１）〜（３）には、（１）衝突困難性を満たすハッシュ関数は（２）第二原像計算困難性を満たし、（２）第二原像計算困難性を満たすハッシュ関数は（３）原像計算困難性を満たす、という関係がある。
また、（３）原像計算困難性が破られたハッシュ関数（原像計算困難性を満たさない［有さない］ハッシュ関数）は、（１）衝突困難性および（２）第二原像計算困難性を満たさない、という関係がある。つまり、原像計算困難性が破られたハッシュ関数は、安全なハッシュ関数が満たすべき上記３つの性質（１）〜（３）を満たさない関数であり、安全性が低いため一般的に使い物にならない。
【０００８】
原像計算困難性が破られたランダムオラクルモデル（ＦＰＴ−ＲＯ：Ｆｉｒｓｔ  Ｐｒｅｉｍａｇｅ  Ｔｒａｃｔａｂｌｅ  −  Ｒａｎｄｏｍ  Ｏｒａｃｌｅ）は、前述のランダムオラクル（ＲＯ）と以下の原像計算オラクル（ＦＰＯ）との２つのオラクル（関数）から構成される。
【０００９】
原像計算オラクル（ＦＰＯ）とは、特定の一つの値ｚに対して「ｚ＝ＲＯ（Ｍｉ）」を満たす全ての入力値Ｍｉ（ｉ＝１、２、・・・）の中から入力値Ｍｘをランダムに１つ選び、選んだ入力値Ｍｘを出力する関数（オラクル）である。
【００１０】
一般的に、暗号アルゴリズムは、ランダムオラクルモデル（上記性質（１）〜（３）を満たすＲＯ）では安全であっても、（３）原像計算困難性がないランダムオラクルモデルでは安全でない。
【００１１】
非特許文献１では、ハッシュ関数をランダムオラクルと仮定し、原像計算困難性が破られたランダムオラクルモデルで安全な電子署名方式を提案している。但し、使用する暗号方式がＲＳＡ−ＦＤＨである場合にしか適用できない。
非特許文献２では、原像計算困難性が破られたランダムオラクルモデルでＯＡＥＰ（Ｏｐｔｉｍａｌ  Ａｓｙｍｍｅｔｒｉｃ  Ｅｎｃｒｙｐｔｉｏｎ  Ｐａｄｄｉｎｇ）が安全であることを示している。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Ａ．  Ｎｕｍａｙａｍａ，  Ｔ．  Ｉｓｓｈｉｋｉ，  ａｎｄ  Ｋ．  Ｔａｎａｋａ，  Ｓｅｃｕｒｉｔｙ  ｏ加工関数ｆ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ  ｉｎ  Ｗｅａｋｅｎｅｄ  Ｒａｎｄｏｍ  Ｏｒａｃｌｅ  Ｍｏｄｅｌｓ．  ＰＫＣ  ２００８．  ｐｐ２６８−２８７．
【非特許文献２】Ａｋｉｎｏｒｉ  Ｋａｗａｃｈｉ，  Ａｋｉｒａ  Ｎｕｍａｙａｍａ，Ｋｅｉｓｕｋｅ  Ｔａｎａｋａ，ａｎｄ  Ｋｅｉｔａ  Ｘａｇａｗ，  Ｓｅｃｕｒｉｔｙ  ｏ加工関数ｆ  ｔｈｅ  ＯＡＥＰ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ  ｉｎ  ｔｈｅ  Ｗｅａｋｅｎｅｄ  Ｒａｎｄｏｍ  Ｏｒａｃｌｅ  Ｍｏｄｅｌｓ．  ＳＣＩＳ  ２００９．  ３Ｄ１−２．
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本発明は、例えば、上記のような課題を解決するためになされたものであり、ランダムオラクルモデルで安全な任意の暗号アルゴリズム（ＲＳＡ−ＦＤＨ、ＯＡＥＰに限らない）を、原像計算困難性がないランダムオラクルモデルで安全な暗号アルゴリズムへ変換することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の暗号処理装置は、
対象データに付加データを付加した対象加工データを暗号アルゴリズムＣＰＵを用いて生成する対象加工データ生成部と、
前記対象加工データ生成部により生成された対象加工データをハッシュ関数の入力としてハッシュ値を暗号アルゴリズムＣＰＵを用いて算出するハッシュ値算出部と、
前記ハッシュ値算出部により算出されたハッシュ値に基づいて前記対象データに対する暗号処理を暗号アルゴリズムＣＰＵを用いて実行する暗号処理部とを備える。
【発明の効果】
【００１５】
本発明によれば、例えば、ランダムオラクルモデルで安全な任意の暗号アルゴリズムを、原像計算困難性がないランダムオラクルモデルで安全な暗号アルゴリズムへ変換することができる。すなわち、理想モデル（ランダムオラクルモデル）で一方向性（原像計算困難性）が破られた場合でも安全性が保証される暗号アルゴリズムを作ることができる。
【図面の簡単な説明】
【００１６】
【図１】実施の形態１における暗号アルゴリズムを示すフローチャート。
【図２】実施の形態１における暗号アルゴリズムの概要図。
【図３】実施の形態１における暗号アルゴリズムの概要図。
【図４】実施の形態１における暗号アルゴリズムの概要図。
【図５】実施の形態１における暗号アルゴリズムの概要図。
【図６】実施の形態１における暗号アルゴリズムの概要図。
【図７】実施の形態１における暗号アルゴリズムの概要図。
【図８】実施の形態１における暗号アルゴリズム強化装置１００の機能構成図。
【図９】実施の形態１における暗号アルゴリズム強化装置１００のハードウェア資源の一例を示す図。
【図１０】実施の形態１における電子署名装置の電子署名生成方法を示すフローチャート。
【図１１】実施の形態２における暗号アルゴリズムを示すフローチャート。
【図１２】実施の形態２における暗号アルゴリズムの概要図。
【図１３】実施の形態２における暗号アルゴリズムの概要図。
【図１４】実施の形態２における暗号アルゴリズムの概要図。
【図１５】実施の形態２における暗号アルゴリズムの概要図。
【図１６】実施の形態２における暗号アルゴリズムの概要図。
【図１７】実施の形態２における暗号アルゴリズムの概要図。
【発明を実施するための形態】
【００１７】
実施の形態１．
ハッシュ関数を用いる暗号アルゴリズムでハッシュ関数の入力データに特定のデータを付加することにより、暗号アルゴリズムの安全性を強化する暗号アルゴリズム強化装置、方法およびプログラムについて説明する。
暗号アルゴリズムとは、データの暗号化、データの復号、電子署名の生成、電子署名の検証などの暗号処理を実行するための手順、方法またはプログラムである。
【００１８】
図１は、実施の形態１における暗号アルゴリズムを示すフローチャートである。
実施の形態１における暗号アルゴリズムについて、図１に基づいて以下に説明する。
【００１９】
実施の形態１における暗号アルゴリズムは、ハッシュ関数の従来の入力データに特定の付加データを付加する処理（Ｓ１２０参照）が含まれるという特徴を有する。
【００２０】
Ｓ１１０において、ハッシュ関数が呼び出されるまでの処理を実行する。
Ｓ１２０において、ハッシュ値を求める対象のデータ（以下、「対象データ」という）に特定の付加データを付加する。対象データは、従来の暗号アルゴリズムにおいてハッシュ関数の入力となるデータである。以下、対象データに付加データを付加したデータを「対象加工データ」という。対象加工データは、実施の形態１においてハッシュ関数の入力となるデータである。
Ｓ１３０において、対象加工データをハッシュ関数に入力し、対象加工データのハッシュ値、つまり、対象データに対応するハッシュ値を算出する。
Ｓ１４０において、ハッシュ関数の呼び出しが残っている場合（ＹＥＳ）、Ｓ１１０に戻り、ハッシュ関数の呼び出しが残っていない場合（ＮＯ）、Ｓ１５０に進む。
Ｓ１５０において、残りの処理を実行し、暗号アルゴリズムの結果データを出力する。Ｓ１３０で算出されたハッシュ値は、Ｓ１５０において残りの処理で使用される。
【００２１】
付加データを付加した対象データ（対象加工データ）をハッシュ関数の入力データにすることにより、暗号アルゴリズムの安全性を高めることができる。
【００２２】
例えば、原像計算困難性がないランダムオラクルモデルにおいて、対象データがハッシュ値に基づいて特定される可能性を従来の「１／２ｋ」程度にすることができる。「ｋ」（後述するセキュリティパラメータ）は付加データのビット数である。例えば、対象データに１ビット（「０」または「１」）の付加データを付加した場合（「ｋ＝１」の場合）、対象加工データからビット「０」を除去したデータと対象加工データからビット「１」を除去したデータとの２つのデータそれぞれに対象データである可能性が生じる。
【００２３】
原像計算困難性がないランダムオラクルモデルとは、原像計算困難性がないランダムオラクルをハッシュ関数として使用するシステムを意味する。
【００２４】
ランダムオラクルとは、同じ値が入力される度に同じ値を出力する関数であって、各入力値に対応する出力値が所定の値域内で一様に分布する関数である。
【００２５】
原像計算困難性がないランダムオラクルモデルでは、算出されたハッシュ値に対応する複数の入力データ（ハッシュ値対応データ群）のうち一つの入力データが対象加工データの候補として特定される。ハッシュ値対応データ群には対象加工データが含まれる。
【００２６】
例えば、ハッシュ値対応データ群に含まれる入力データの数が「ｉ」である場合、特定入力データ（対象加工データの候補として特定された入力データ）が対象加工データである可能性は「１／ｉ」である。
さらに、付加データのビット数が「ｋ」である場合、特定入力データから求められる対象データの候補数は「２ｋ」である。
したがって、特定入力データが対象データである可能性は「１／（ｉ×２ｋ）」である。
【００２７】
ハッシュ関数の入力（対象データ）に付加データを付加することを条件として、「ランダムオラクルモデルで安全な暗号アルゴリズムは原像計算困難性がないランダムオラクルモデルで安全な暗号アルゴリズムである」と言える。このことは、強識別不可能性に基づいて証明される。
強識別不可能性とは、使用されている関数がランダムオラクルとハッシュ関数とのいずれであるか識別できないという性質をいう。
【００２８】
つまり、実施の形態１における暗号アルゴリズムは、原像計算困難性があるランダムオラクルモデルにおいて安全であれば、原像計算困難性が破られたランダムオラクルモデルにおいても安全である。
【００２９】
ＲＳＡ、Ｒａｂｉｎ関数およびＰａｉｌｌｉｅｒ関数は、原像計算困難性を通常有する一方向性関数の一例である。
ＲＳＡ−ＯＡＥＰ、ＲＳＡ−ＰＳＳ、ＲＳＡ−ＫＥＭなどの暗号アルゴリズムやＲＳＡの代わりにＲａｂｉｎ関数またはＰａｉｌｌｉｅｒ関数を用いた暗号アルゴリズムは、原像計算困難性があるランダムオラクルモデルで安全な暗号アルゴリズムの一例であり、実施の形態１を適用する暗号アルゴリズムとして適している。
【００３０】
次に、対象データに付加する付加データおよび付加データの付加方法について説明する。
【００３１】
まず、付加データについて説明する。
付加データのサイズは、セキュリティパラメータとして予め定められた固定長「ｋ」ビットである。付加データのサイズはｋビット以上であってもよい。
付加データの値は、所定の固定値または対象データに含まれる部分データの値である。
つまり、ｋビットの固定値、対象データの先頭ｋビットまたは対象データの末尾ｋビットが付加データとなる。対象データの中間ｋビット（ｘ＋１ビット目からｘ＋ｋビット目まで）を付加データとしてもよい。
【００３２】
次に、付加データの付加方法について説明する。
付加データは、対象データの前または後ろに結合される。付加データを対象データ中に挿入してもよい。
【００３３】
図２〜図７は、実施の形態１における暗号アルゴリズムの概要図である。
実施の形態１における暗号アルゴリズムの概要について、図２〜図７に基づいて以下に説明する。
【００３４】
図２〜図７において、暗号アルゴリズムを「Ｃ（大文字）」、ハッシュ関数を「Ｈｘ（ｘ：１、２、・・・、ｉ）」、対象データに付加データを付加する加工関数を「ｆ」とする。
ハッシュ関数Ｈｘの従来の入力値（対象データ）を「Ｍｘ」、ｋビットの固定値を「ｃ（小文字）」、入力値Ｍｘの先頭ｋビットを「Ｍｘ［ｋ］」、入力値Ｍｘの末尾ｋビットを「Ｍｘ（ｋ）」とする。
ビット列の結合を「｜｜」で表す。「ａ｜｜ｂ」は、ａの後ろにｂを結合すること、またはｂの前にａを結合することを意味する。
ハッシュ関数Ｈｘにより求められる「ｙ」のハッシュ値を「Ｈｘ（ｙ）」とする。
【００３５】
図２は、暗号アルゴリズムＣにおいてｉ個のハッシュ関数Ｈｘが呼び出され、加工関数ｆが各ハッシュ関数Ｈｘの入力値Ｍｘを「ｃ｜｜Ｍｘ」に変更し、各ハッシュ関数Ｈｘが変更後の入力値「ｃ｜｜Ｍｘ」のハッシュ値Ｈｘ（ｃ｜｜Ｍｘ）を出力することを示している。暗号アルゴリズムＣでは入力値Ｍｘに対する暗号処理（例えば、電子署名の作成または検証）として、従来のハッシュ値Ｈｘ（Ｍｘ）の代わりにハッシュ値Ｈｘ（ｃ｜｜Ｍｘ）を用いた処理が行われる。
【００３６】
図３〜図７は、同様に、加工関数ｆがハッシュ関数Ｈｘの入力値Ｍｘを「Ｍｘ｜｜ｃ」（図３）、「Ｍｘ［ｋ］｜｜Ｍｘ」（図４）、「Ｍｘ｜｜Ｍｘ［ｋ］」（図５）、「Ｍｘ（ｋ）｜｜Ｍｘ」（図６）、「Ｍｘ｜｜Ｍｘ（ｋ）」（図７）に変更することを示している。
【００３７】
図２において、ハッシュ関数Ｈｘ毎に固定値ｃが異なっても構わない。
図２において、ハッシュ関数Ｈｘ毎に付加データおよび付加方法が異なっても構わない。例えば、「Ｍ１」が「ｃ｜｜Ｍ１」に変更され、「Ｍ２」が「Ｍ２｜｜ｃ」に変更され、「Ｍ３」が「Ｍｘ［ｋ］｜｜Ｍ３」に変更されてもよい。
図２〜図７それぞれにおいて、ｉ個のハッシュ関数Ｈｘは同じハッシュ関数であっても構わない。つまり、ハッシュ関数は一種類であっても構わない。
図２〜図７それぞれにおいて、ハッシュ関数の呼び出し回数が１回であっても構わない。つまり、暗号アルゴリズムＣで呼び出されるハッシュ関数が一つであり、呼び出される回数が一回であっても構わない。
【００３８】
図２〜図７それぞれにおいて、全体を装置（暗号処理装置の一例）とし、暗号アルゴリズムＣ（暗号処理部の一例）、加工関数ｆ（対象加工データ生成部の一例）およびハッシュ関数Ｈｘ（ハッシュ値算出部の一例）をＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）により動作する処理部としてもよい。
【００３９】
実施の形態１における暗号アルゴリズムは、例えば、携帯電話機のデジタル署名や本人確認方式に利用することができる。
【００４０】
図８は、実施の形態１における暗号アルゴリズム強化装置１００の機能構成図である。
実施の形態１における暗号アルゴリズム強化装置１００の機能構成について、図８に基づいて以下に説明する。以下に説明する暗号アルゴリズム強化装置１００は、実施の形態１における暗号アルゴリズムに基づいた暗号処理を実行する装置である。
【００４１】
暗号アルゴリズム強化装置１００（暗号処理装置）は、ハッシュ前処理部１１０、ハッシュ入力加工部１２０（対象加工データ生成部の一例）、ハッシュ処理部１３０（ハッシュ値算出部の一例）、ハッシュ後処理部１４０（暗号処理部の一例）およびデータ記憶部１９０を備える。
【００４２】
ハッシュ前処理部１１０は、ハッシュ関数を実行するまでの前処理をＣＰＵを用いて実行する。
例えば、ハッシュ前処理部１１０は、前処理として、電子署名を付ける文書データや暗号化する文書データを生成する。
【００４３】
ハッシュ入力加工部１２０は、ハッシュ値を算出する対象データ（ハッシュ関数の従来の入力データ）に付加データを付加した対象加工データをＣＰＵを用いて生成する。
【００４４】
例えば、ハッシュ入力加工部１２０は、以下の（１）〜（７）いずれかの方法で対象加工データを生成する。ただし、以下の（１）〜（７）の各方法を複数組み合わせて対象加工データを生成してもよい。
（１）付加データとして固定データを対象データに付加する。
（２）付加データとして対象データに含まれる部分データを対象データに付加する。
（３）部分データとして対象データの先頭に位置する先頭データ（例えば、対象データの先頭ｋビット）を対象データに付加する。
（４）部分データとして対象データの末尾に位置する末尾データ（例えば、対象データの末尾ｋビット）を対象データに付加する。
（５）付加データを対象データの前に付加する。
（６）付加データを対象データの後ろに付加する。
（７）入力データに付加データが含まれる場合、入力データを対象加工データとして扱い、入力データに付加データが含まれない場合、入力データを対象データとして扱う。
【００４５】
例えば、ハッシュ入力加工部１２０は、ハッシュ前処理部１１０により生成された文書データ（対象データの一例）に付加データを付加して文書加工データ（対象加工データの一例）を生成する。
【００４６】
ハッシュ処理部１３０は、ハッシュ入力加工部１２０により生成された対象加工データをハッシュ関数の入力としてハッシュ値をＣＰＵを用いて算出する。
例えば、ハッシュ処理部１３０は、ハッシュ入力加工部１２０により生成された文書加工データを入力としてハッシュ関数を実行してハッシュ値を算出する。
【００４７】
ハッシュ後処理部１４０は、ハッシュ処理部１３０により算出されたハッシュ値に基づいて、対象データに対する暗号処理をＣＰＵを用いて実行する。
例えば、ハッシュ後処理部１４０は、ハッシュ処理部１３０により算出されたハッシュ値を暗号化し、暗号化したハッシュ値を文書データの電子署名として文書データと共に所定の端末装置に送信する。
【００４８】
データ記憶部１９０は、暗号アルゴリズム強化装置１００で使用されるデータを記憶する。
対象データ、付加データおよび対象加工データはデータ記憶部１９０に記憶されるデータの一例である。
【００４９】
図９は、実施の形態１における暗号アルゴリズム強化装置１００のハードウェア資源の一例を示す図である。
図９において、暗号アルゴリズム強化装置１００は、ＣＰＵ９１１（マイクロプロセッサ、マイクロコンピュータともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、ドライブ装置９０４、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。ドライブ装置９０４は、ＦＤ（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｃ）などの記憶媒体を読み書きする装置である。
【００５０】
通信ボード９１５は、有線または無線で、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネット、電話回線などの通信網に接続している。
【００５１】
磁気ディスク装置９２０には、ＯＳ９２１（オペレーティングシステム）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。
【００５２】
プログラム群９２３には、実施の形態において「〜部」として説明する機能を実行するプログラムが含まれる。プログラムは、ＣＰＵ９１１により読み出され実行される。すなわち、プログラムは、「〜部」としてコンピュータを機能させるものであり、また「〜部」の手順や方法をコンピュータに実行させるものである。
【００５３】
ファイル群９２４には、実施の形態において説明する「〜部」で使用される各種データ（入力、出力、判定結果、計算結果、処理結果など）が含まれる。
【００５４】
実施の形態において構成図およびフローチャートに含まれている矢印は主としてデータや信号の入出力を示す。
【００５５】
実施の形態において「〜部」として説明するものは「〜回路」、「〜装置」、「〜機器」であってもよく、また「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ファームウェア、ソフトウェア、ハードウェアまたはこれらの組み合わせのいずれで実装されても構わない。
【００５６】
次に、電子署名を生成する電子署名装置を暗号アルゴリズム強化装置１００の具体例として、電子署名装置の処理内容を説明する。
【００５７】
図１０は、実施の形態１における電子署名装置の電子署名生成方法を示すフローチャートである。
実施の形態１における電子署名装置の電子署名生成方法について、図１０に基づいて以下に説明する。電子署名生成方法は、実施の形態１における暗号アルゴリズムに基づいた暗号処理方法の一例である。
【００５８】
電子署名装置（暗号アルゴリズム強化装置１００）の各「〜部」は、以下に説明する処理をＣＰＵを用いて実行する。
【００５９】
＜Ｓ２１０＞
ハッシュ前処理部１１０は、電子署名を付ける対象の文書データ（対象データの一例）を生成する。この文書データは、従来の暗号アルゴリズムにおいてハッシュ関数に入力されるデータである。
Ｓ２１０は、暗号アルゴリズム（図１参照）のＳ１１０に相当する。
Ｓ２１０の後、処理はＳ２２０に進む。
【００６０】
＜Ｓ２２０＞
ハッシュ入力加工部１２０は、Ｓ２１０で生成された文書データに付加データを付加する。以下、付加データが付加された文書データを「文書加工データ（対象加工データの一例）」という。
Ｓ２２０は、暗号アルゴリズムのＳ１２０に相当する。
Ｓ２２０の後、処理はＳ２３０に進む。
【００６１】
＜Ｓ２３０＞
ハッシュ処理部１３０は、Ｓ２２０で得られた文書加工データをハッシュ関数の入力としてハッシュ関数を実行する。ハッシュ関数の実行により、文書加工データのハッシュ値、つまり、文書データに対応するハッシュ値が算出される。
Ｓ２３０は、暗号アルゴリズムのＳ１３０に相当する。
Ｓ２３０の後、処理はＳ２４０に進む。
【００６２】
＜Ｓ２４０＞
ハッシュ後処理部１４０は、Ｓ２３０で算出されたハッシュ値を秘密鍵で暗号化する。暗号化されたハッシュ値が文書データの電子署名となる。
Ｓ２４０は、暗号アルゴリズムのＳ１１０またはＳ１５０に相当する。
Ｓ２４０の後、処理はＳ２５０に進む。
【００６３】
＜Ｓ２５０＞
ハッシュ後処理部１４０は、Ｓ２１０で生成された文書データとＳ２４０で生成された電子署名とを所定の端末装置に送信する。
Ｓ２５０は、暗号アルゴリズムのＳ１１０またはＳ１５０に相当する。
Ｓ２５０により、電子署名付き文書データの生成処理は終了する。
【００６４】
端末装置は、電子署名を検証し、文書データが改ざんされていないか確認する。電子署名を検証する端末装置は暗号アルゴリズム強化装置１００の一例である。
端末装置は、電子署名の一般の検証方法と同様に、文書データに対応するハッシュ値と電子署名を復号して得られるハッシュ値とが同じであれば文書データが改ざんされていないと判定する。
但し、端末装置は、電子署名装置と同じく、文書データに付加データを付加した文書加工データをハッシュ関数の入力として文書データに対応するハッシュ値を得る。端末装置が使用する付加データおよびハッシュ関数は電子署名装置が使用するものと同じである。
【００６５】
実施の形態１における暗号アルゴリズム、つまり、ハッシュ関数の入力データに付加データを付加するという方法は、上記のような電子署名の生成処理または検証処理以外の暗号処理に適用しても構わない。
例えば、文書データを暗号化する処理または暗号化された文書データを復号する処理において、付加データを付加した文書データをハッシュ関数の入力にしても構わない。
【００６６】
実施の形態１において、ランダムオラクルモデルで安全な任意の暗号アルゴリズムを原像計算困難性がないランダムオラクルモデルで安全な暗号アルゴリズムに変換する暗号アルゴリズム強化装置について説明した。
暗号アルゴリズム強化装置は、暗号アルゴリズムに利用されるハッシュ関数への入力を加工する。
【００６７】
実施の形態１において、例えば、以下のような暗号アルゴリズムについて説明した。
【００６８】
ハッシュ関数を用いた任意の暗号アルゴリズムに対して、ハッシュ関数の入力に特定ビット長の固定値を付加し、その値をハッシュ関数の入力とする入力加工処理を加えた暗号アルゴリズム。
【００６９】
ハッシュ関数を用いた任意の暗号アルゴリズムで用いるハッシュ関数への入力に対して、その入力の先頭ｋビット分をその入力の先頭に付加し、その値をハッシュ関数の入力とする入力加工処理を加えた暗号アルゴリズム。
【００７０】
ハッシュ関数を用いた任意の暗号アルゴリズムで用いるハッシュ関数への入力に対して、その入力の先頭ｋビット分をその入力の後ろに付加し、その値をハッシュ関数の入力とする入力加工処理を加えた暗号アルゴリズム。
【００７１】
ハッシュ関数を用いた任意の暗号アルゴリズムで用いるハッシュ関数への入力に対して、その入力の後ろｋビット分をその入力の後ろに付加し、その値をハッシュ関数の入力とする入力加工処理を加えた暗号アルゴリズム。
【００７２】
任意の暗号アルゴリズムのうちランダムオラクルを用いたときに安全な暗号アルゴリズムであって、一方向性が破られたランダムオラクルを用いたときに安全であるかどうか証明されていない暗号アルゴリズム（例えば、ＲＳＡ−ＰＳＳ、ＲＳＡ−ＫＥＭ）に対して、入力加工処理を加えた暗号アルゴリズム。
【００７３】
ハッシュ関数を用いた暗号アルゴリズムは、必ず、ハッシュ関数にある入力を与え、その出力を暗号アルゴリズムの計算で用いる。
このハッシュ関数の入力Ｍを変換ｆでｆ（Ｍ）に変換し、ｆ（Ｍ）をハッシュ関数の入力とし、その出力を暗号アルゴリズムの計算で用いる。
以下は、ｆの具体例である。
（１）ｆ（Ｍ）＝Ｍ｜｜ｃ
（２）ｆ（Ｍ）＝ｃ｜｜Ｍ
（３）ｆ（Ｍ）＝Ｍ［ｋ］｜｜Ｍ
（４）ｆ（Ｍ）＝Ｍ｜｜Ｍ［ｋ］
（５）ｆ（Ｍ）＝Ｍ｜｜Ｍ（ｋ）
「ｃ」は固定値、「Ｍ［ｋ］」はＭの先頭ｋビット、「Ｍ（ｋ）」はＭの後ろｋビットである。また、ｃの長さおよびｋの値は、セキュリティパラメータがｓビットを示す場合、ｓ以上の値となる。
【００７４】
実施の形態２．
ハッシュ関数の入力データに付加データが含まれている場合、入力データをそのままハッシュ関数に入力し、ハッシュ関数の入力データに付加データが含まれていない場合、入力データに付加データを付加した加工データをハッシュ関数に入力する形態について説明する。
以下、実施の形態１と異なる事項について説明する。説明を省略する事項は実施の形態１と同様である。
【００７５】
図１１は、実施の形態２における暗号アルゴリズムを示すフローチャートである。
実施の形態２における暗号アルゴリズムについて、図１１に基づいて以下に説明する。
【００７６】
実施の形態２において暗号アルゴリズムは、実施の形態１（図１参照）のＳ１２０をＳ１２１およびＳ１２２に変更したものである。その他（Ｓ１１０、Ｓ１３０〜Ｓ１５０）は実施の形態１と同じである。
以下、Ｓ１２１とＳ１２２とについて説明する。
【００７７】
Ｓ１２１において、ハッシュ関数が呼び出されたときの入力データ（対象データまたは対象加工データ）に付加データが含まれるか、つまり、入力データが対象加工データであるか判定する。
入力データに付加データが含まれる場合（ＹＥＳ）、Ｓ１３０に進む。
入力データに付加データが含まれない場合（ＮＯ）、Ｓ１２２に進む。
【００７８】
Ｓ１２２において、Ｓ１２０と同様、入力データ（対象データ）に付加データを付加して対象加工データを生成する。入力データに付加データ（例えば、「１１００１」）の一部（「１１０」）が含まれる場合、付加データの残り（「０１」）を入力データに付加して対象加工データを生成してもよい。つまり、入力データに含まれる付加データのビット数が所定のビット数ｋより小さい場合、ｋビットに足りない分を入力データに付加してもよい。
【００７９】
Ｓ１３０では、対象加工データ（入力データまたは入力データ＋付加データ）がハッシュ関数に入力される。
【００８０】
図１２〜図１７は、実施の形態２における暗号アルゴリズムの概要図である。
図１２〜図１７は、それぞれ実施の形態１における図２〜図７に対応している。
【００８１】
図１２は、加工関数ｆが入力値Ｍｘまたは「ｃ｜｜Ｍｘ」をハッシュ関数Ｈｘの入力にすることを示している。
加工関数ｆは、複数のハッシュ関数の入力値Ｍｘに対し、固定値ｃを含む入力値Ｍｘをそのままハッシュ関数Ｈｘに入力し、固定値ｃを含まない入力値Ｍｘを「ｃ｜｜Ｍｘ」に変更してハッシュ関数Ｈｘに入力する。
図１３〜図１７も同様である。付加データ（ｃ、Ｍｘ［ｋ］またはＭｘ（ｋ））と付加方法（Ｍｘの前に付加または後ろに付加）との少なくともいずれかが図１２とは異なる。
【００８２】
入力データ（入力値Ｍｘ）に付加データが含まれるか否かは、例えば以下のように判定される。
（１）入力データの先頭ｋビットが付加データか（図１２、１４、１６）。
（２）入力データの末尾ｋビットが付加データか（図１３、１５、１７）。
（３）入力データの先頭部分が付加データ（または、同じｋビット）の繰り返しか（図１４）。
（４）入力データの先頭ｋビットと最終ｋビットが同じか（図１５、１６）。
（５）入力データの末尾部分が付加データ（または、同じｋビット）の繰り返しか（図１７）。
また、暗号アルゴリズムＣの仕様（例えば、ハッシュ関数の入力フォーマット）に基づいて判定されてもよい。
【００８３】
実施の形態２により、入力データに付加データを不要に付加することを防ぐことができる。
【００８４】
実施の形態１において、例えば、以下のような暗号アルゴリズムについて説明した。
【００８５】
ハッシュ関数を用いた任意の暗号アルゴリズムで、特定のビット長以上の長さを持つ固定値が付加されていないハッシュ関数への入力に特定のビット長の固定値を付加し、その値をハッシュ関数の入力とする処理を加えた暗号アルゴリズム。
【００８６】
ハッシュ関数を用いた任意の暗号アルゴリズムで、ハッシュ関数への入力のフォーマットとして、あるビット長ｋ以上の特定ビットパタンが入力の先頭で２回以上現れない場合、ハッシュ関数への入力に対して、その入力の先頭ｋビット分をその入力の先頭に付加し、その値をハッシュ関数の入力とする処理を加えた暗号アルゴリズム。
【００８７】
ハッシュ関数を用いた任意の暗号アルゴリズムで、ハッシュ関数への入力のフォーマットとして、あるビット長ｋ以上の特定ビットパタンが入力の先頭と後ろに現れない場合、ハッシュ関数への入力に対して、その入力の先頭ｋビット分をその入力の後ろに付加し、その値をハッシュ関数の入力とする処理を加えた暗号アルゴリズム。
【００８８】
ハッシュ関数を用いた任意の暗号アルゴリズムで、ハッシュ関数への入力のフォーマットとして、あるビット長ｋビット以上の特定ビットパタンが入力の後ろで２回以上現れない場合、ハッシュ関数への入力に対して、その入力の後ろｋビット分をその入力の後ろに付加し、その値をハッシュ関数の入力とする処理を加えた暗号アルゴリズム。
【符号の説明】
【００８９】
１００  暗号アルゴリズム強化装置、１１０  ハッシュ前処理部、１２０  ハッシュ入力加工部、１３０  ハッシュ処理部、１４０  ハッシュ後処理部、１９０  データ記憶部、Ｃ  暗号アルゴリズム、ｆ  加工関数、Ｈ  ハッシュ関数、９０１  表示装置、９０２  キーボード、９０３  マウス、９０４  ドライブ装置、９１１  ＣＰＵ、９１２  バス、９１３  ＲＯＭ、９１４  ＲＡＭ、９１５  通信ボード、９２０  磁気ディスク装置、９２１  ＯＳ、９２２  ウィンドウシステム、９２３  プログラム群、９２４  ファイル群。
【図１】
2010276736.tif 000003
【図２】
2010276736.tif 000004
【図３】
2010276736.tif 000005
【図４】
2010276736.tif 000006
【図５】
2010276736.tif 000007
【図６】
2010276736.tif 000008
【図７】
2010276736.tif 000009
【図８】
2010276736.tif 000010
【図９】
2010276736.tif 000011
【図１０】
2010276736.tif 000012
【図１１】
2010276736.tif 000013
【図１２】
2010276736.tif 000014
【図１３】
2010276736.tif 000015
【図１４】
2010276736.tif 000016
【図１５】
2010276736.tif 000017
【図１６】
2010276736.tif 000018
【図１７】
2010276736.tif 000019