(57)【要約】【課題】情報処理量を増やすことなく、耐改ざん性の高いタイムスタンプを発行するために必要なハッシュ値を導出することができるネットワークシステムを提供する。【解決手段】サーバ１が、通信端末１１より受領した電子データを構成するビットデータの配列を識別し、識別された配列に基づき少なくともいずれか一つのビットデータを、メモリ９に保持されているルールに従って他のビットデータと置換する。そして、ビットデータが置換された新たな電子データに対して一つのハッシュ関数を所定規則に従って複数回適用することにより、電子データを表す一つのハッシュ値を導出し、このハッシュ値をメモリ９に保持されているルール及び電子データと関連付けて通信端末１１に送る。【選択図】図１
2007256756.tif 000002
【特許請求の範囲】
【請求項１】
複数の単位データから成る電子データにおける各単位データの配列を識別する識別手段と、
この識別手段で識別された配列に基づき少なくともいずれか一つの単位データを、所定のメモリに保持されているルールに従って他の単位データと置換する第１処理手段と、
前記第１処理手段により単位データが置換された電子データに対して一つのハッシュ関数を所定規則に従って複数回適用することにより、前記電子データを表す一つのハッシュ値を導出するとともに、このハッシュ値を前記メモリに保持されているルール及び前記電子データと関連付ける第２処理手段と、
を有する情報処理装置。
【請求項２】
前記ルールが、非予測性因子に基づいて１回の置換用に１つ又は複数生成される、
請求項１記載の情報処理装置。
【請求項３】
前記電子データが複数のブロックに区分されており、
前記第１処理手段は、互いに異なるブロック内の単位データ同士を置換する、
請求項１又は２記載の情報処理装置。
【請求項４】
前記第２処理手段は、前記ルールを符号化し、符号化したルールを前記ハッシュ値及び前記電子データと関連付ける、
請求項１、２又は３記載の情報処理装置。
【請求項５】
情報処理装置による電子データの作成時刻を証明するためのタイムスタンプトークンの発行方法であって、
前記情報処理装置が、
複数の単位データから成る電子データにおける各単位データの配列を識別する処理、
識別された配列に基づき少なくともいずれか一つの単位データを、所定のメモリに保持されているルールに従って他の単位データと置換する処理、及び、
単位データが置換された電子データに対して一つのハッシュ関数を所定規則に従って複数回適用することにより、前記電子データを表す一つのハッシュ値を導出するとともに、このハッシュ値を前記メモリに保持されているルール及び前記電子データと関連付ける処理、
を実行する、タイムスタンプトークンの発行方法。
【請求項６】
コンピュータを、複数の単位データから成る電子データにおける各単位データの配列を識別する識別手段、この識別手段で識別された配列に基づき少なくともいずれか一つの単位データを、所定のメモリに保持されているルールに従って他の単位データと置換する第１処理手段、前記第１処理手段により単位データが置換された電子データに対して一つのハッシュ関数を所定規則に従って複数回適用することにより、前記電子データを表す一つのハッシュ値を導出するとともに、このハッシュ値を前記メモリに保持されているルール及び前記電子データと関連付ける第２処理手段、として機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば電子データの作成時刻や保存時刻等を証明するためのタイムスタンプトークンの信頼性を高める情報処理装置及びその関連技術に関する。
【背景技術】
【０００２】
電子データがある時刻に存在し、かつ、その時刻以降、電子データに対して改ざんがなされていないことを電子的に証明する電子情報として、タイムスタンプがある。タイムスタンプは、例えば、タイムスタンプ局（ＴＳＡ）と呼ばれる機関で発行される。このタイムスタンプ局が生成するタイムスタンプデータを、この明細書では、「タイムスタンプトークン」と呼ぶ。
【０００３】
タイムスタンプを発行するための技術として、タイムスタンプトークンの作成メカニズムの観点から、シンプルプロトコル方式とリンキングプロトコル方式の２つの方式がある。
シンプルプロトコル方式は、電子データを表すハッシュ値と時刻情報を含むデータに対し、タイムスタンプ局の秘密鍵でデジタル署名を作成する方式である。
リンキングプロトコル方式は、「以前に発行したタイムスタンプトークン」と、「今回発行対象となる電子データのハッシュ値」を含むデータを表すハッシュ値を導出し、そのハッシュ値をタイムスタンプトークンとし、以後、同様の処理を繰り返し行うことによってハッシュ値の連鎖値を作成し、ある時期にハッシュ連鎖値上の一部のハッシュ値を公開する方式である。
リンキングプロトコル方式に基づく従来例として、例えば、特許文献１記載の発明「数値文書にタイムスタンプを確実に押す方法」が挙げられる。
【０００４】
シンプルプロトコル方式およびリンキングプロトコル方式の共通点は、電子データそのものをタイムスタンプトークンの発行対象とするのではなく、電子データを表すハッシュ値をタイムスタンプトークンの発行対象とする点である。これは、ハッシュ関数の安全性の指標となる原像発見困難性(preimage resistance)、第２原像発見困難性(second-preimage resistance)及び衝突困難性(collision resistance)を担保するために、次の３項目を考慮して、一般的に採用されている。
（１）電子データのハッシュ値がある時刻に存在することが証明されれば、当該ハッシュ値の原像となる当該電子データも、その時刻以前に存在していたはずであることを強く推測できること。
（２）取り扱うデータサイズが小さくなることで、タイムスタンプトークンの発行処理を高速化できること。
（３）タイムスタンプ局に時刻証明の対象となる電子データそのものを送付しないため、利用者のプライバシーを確保できること。
ハッシュ関数としては、「ＭＤ５」、「ＳＨＡ−１」、「ＳＨＡ−２５６」、「ＳＨＡ−５１２」など、その使用態様が公開されたものが使われることが多い。
【０００５】
なお、原像発見困難性(preimage resistance)とは、ハッシュ関数ｈ（ｍ）に対して出力ｙ＝ｈ（ｍ）が与えられたときに、ｙの原像であるｍ（複数ありうる）を求めることが計算量的に困難であることをいう。また、第２原像発見困難性(second-preimage resistance)とは、出力ｙ＝ｈ（ｍ）が与えられたときに、ｙ＝ｈ（ｍ’）となるｍ’（ただしｍ’≠ｍ）を求めることが計算量的に困難であることをいう。衝突困難性(collision resistance)とは、ハッシュ値が同一値となる任意の２つのメッセージｍ及びｍ’（すなわち、ｈ（ｍ）＝ｈ（ｍ’）、かつ、ｍ≠ｍ’）を求めることが計算量的に困難であることをいう。
【０００６】
【特許文献１】特表平６−５０１５７１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述した従来例は、ハッシュ関数の安全性に依存するところが大きい。近年、ハッシュ関数の衝突を発見する方法の研究が進んでおり、「ＭＤ５」については、既に衝突が発見されている。「ＳＨＡ−１」については、衝突自体は発見されていないものの、衝突を発見するための計算量を大幅に削減する計算方針又は近衝突(near collision)と呼ばれるハッシュ値がほぼ同じあるいは数ビットの差しかないデータ対が発見されており（ハッシュ値の危殆）、タイムスタンプの長期的な安全性が危惧されている。
ハッシュ関数の危殆対策として、従来、１種類のハッシュ関数のみを用いてハッシュ値を作成するのではなく、２種類の異なるハッシュ関数（例えば、「ＭＤ５」と「ＳＨＡ−１」）を用いてそれぞれハッシュ値を作成し、それらを連結したものを当該電子データのハッシュ値としてタイムスタンプシステムを運用する方式がある。しかし、このような対策によっても、以下のような課題が存在する。
（１）ハッシュ関数の種類を増やして安全性を向上させようとしても、実質標準的なハッシュ関数の種類は少なく、選択肢が限られる。
（２）使用するハッシュ関数の種類を多くすると、その分、情報処理量が増加する。
（３）使用するハッシュ関数の種類を多くすると、多くのハッシュ関数モジュールの実装が必要となり、その分、実装コストが増加する。
【０００８】
本発明は、情報処理量を増やすことなく、耐改ざん性の高いタイムスタンプを発行するうえで好適となる情報処理の仕組を提供することを課題とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、本発明は、情報処理装置、タイムスタンプトークンの発行方法、及び、コンピュータプログラムを提供する。
本発明が提供する情報処理装置は、複数の単位データから成る電子データにおける各単位データの配列を識別する識別手段と、この識別手段で識別された配列に基づき少なくともいずれか一つの単位データを、所定のメモリに保持されているルールに従って他の単位データと置換する第１処理手段と、前記第１処理手段により単位データが置換された電子データに対して一つのハッシュ関数を所定規則に従って複数回適用することにより、前記電子データを表す一つのハッシュ値を導出するとともに、このハッシュ値を前記メモリに保持されているルール及び前記電子データと関連付ける第２処理手段と、を有する。
【００１０】
本発明の情報処理装置では、ルールを、非予測性因子、例えば乱数に基づいて、１回の置換用に１つ又は複数生成する。これにより、第三者が電子データにおける単位データの配列等を予測することが困難になる。
電子データを複数のブロックに区分し、第１処理手段が、互いに異なるブロック内の単位データ同士を置換するようにしてもよい。また、第２処理手段が、ルールを符号化し、符号化したルールをハッシュ値及び電子データと関連付けるようにすることもできる。
【００１１】
本発明が提供するタイムスタンプトークンの発行方法は、例えば上述した情報処理装置による電子データの作成時刻を証明するための方法である。より具体的には、情報処理装置が、複数の単位データから成る電子データにおける各単位データの配列を識別する処理、識別された配列に基づき少なくともいずれか一つの単位データを、所定のメモリに保持されているルールに従って他の単位データと置換する処理、及び、単位データが置換された電子データに対して一つのハッシュ関数を所定規則に従って複数回適用することにより、前記電子データを表す一つのハッシュ値を導出するとともに、このハッシュ値を前記メモリに保持されているルール及び前記電子データと関連付ける処理を実行する。
【００１２】
本発明のコンピュータプログラムは、コンピュータを、複数の単位データから成る電子データにおける各単位データの配列を識別する識別手段、この識別手段で識別された配列に基づき少なくともいずれか一つの単位データを、所定のメモリに保持されているルールに従って他の単位データと置換する第１処理手段、前記第１処理手段により単位データが置換された電子データに対して一つのハッシュ関数を所定規則に従って複数回適用することにより、前記電子データを表す一つのハッシュ値を導出するとともに、このハッシュ値を前記メモリに保持されているルール及び前記電子データと関連付ける第２処理手段、として機能させるためのコンピュータプログラムである。
【発明の効果】
【００１３】
本発明によれば、従来のように複数のハッシュ関数を用いることなく、一つのハッシュ関数を用いるだけで、タイムスタンプに用いるハッシュ値の耐改ざん性を向上させることができる。ハッシュ値の導出には単一種類のハッシュ関数しか用いないため、複数種類のハッシュ関数を用いる場合に比べて、ハッシュ値導出処理時に必要なハッシュ関数モジュールが少なくて済み、タイムスタンプシステムの実装時のコストを低減することができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明をタイムスタンプトークンの発行を行うネットワークシステムに適用した場合の実施の形態例を説明する。ここでは、単位データとして、二値データの一つであるビットデータを用いる場合の例を示すが、単位データは、バイトコード、１０進コード、１６進コードであっても良い。
【００１５】
［構成］
図１は、本実施形態によるネットワークシステムの全体構成図である。このネットワークシステムは、ネットワーク１０を介して接続されたサーバ１と、１又は複数の通信端末１１とを含んで構成される。
サーバ１は、プロセッサとメモリ媒体とを含む通信機能付のコンピュータ（情報処理装置）が、メモリ媒体に記録されているコンピュータプログラムを実行することにより、そのコンピュータにタイムスタンプトークンの発行に関わる種々の機能を形成する。具体的には、サーバ１は、ネットワーク１０を介した通信を可能にするためのインターフェイス２（以下、Ｉ／Ｆ２）、主制御部３、データ管理部４、ビット置換部５、ハッシュ値導出部６、乱数生成部７、ルール管理部８、及び、メモリ（メモリ管理部）９を構築する。
【００１６】
データ管理部４は、ビットデータ群から成る電子データｍを複数のブロックに区分するとともに、各ブロックにおけるビットデータの配列を識別する処理、及び、後述するハッシュ値導出部６によって導出されるハッシュ値をメモリ９に保持されているルール及び電子データｍと関連付ける処理等を行う。電子データｍは、通信端末１１より送信され、メモリ９に格納される。ビットデータの配列の識別は、例えば、先頭から何番目のブロックの何番目のビットデータであるかによって識別する。あるいは、各ブロックが格納されるメモリ９の領域のビットアドレスによって識別するようにしてもよい。
ビット置換部５は、識別された配列に基づき少なくともいずれか一つのビットデータを、メモリ９に保持されているルールに従って他のビットデータと置換する処理を行う。ルールについては、後述する。
【００１７】
ハッシュ値導出部６は、ビットデータが置換された電子データｍに対して一つのハッシュ関数を、例えば所定規則に従って複数回適用することにより、置換される前の電子データｍを表す一つのハッシュ値を導出する処理を行う。
乱数生成部７は、後述するルール管理部８の要求に応じ、ビット置換部５がビットデータの置換を行う際に用いるルールを生成するために用いる非予測性因子の一例となる乱数を生成する処理を行う。なお、非予測性因子は乱数に限定されるものではない。
【００１８】
ルール管理部８は、ビットデータを置換するためのルールを生成し、あるいは、外部より取得し、これをメモリ９に格納する処理を行う。
メモリ９は、通信端末１１から送信される電子データｍ、ハッシュ値の導出に用いる初期値ＩＶ、及び、ルール等を格納する。
主制御部３は、上述した各処理部４〜９の統括的制御を行うとともに、Ｉ／Ｆ２を介してネットワーク１０に接続された通信端末１１との間のデータ送受信、内部バスを介して各処理部４〜９への各種データの受け渡し等を行う。
【００１９】
［動作］
次に、上記のように構成されるサーバ１の動作を、図２に示す処理手順説明図を参照して説明する。前提として、ハッシュ値の導出に用いられる初期値ＩＶ及び電子データｍが、通信端末１１からサーバ１に予め送信され、サーバ１側で、通信端末１１の通信アドレスと共にメモリ９に格納されているものとする。
【００２０】
主制御部３は、初期値ＩＶ及び電子データｍをメモリ９から読み込み（ステップＳ２０１）、電子データｍについては、これをデータ管理部４に伝送する。
データ管理部４は、電子データｍをそれぞれビットデータ群から成る複数のブロックに区分し、各ブロック内のビットデータの配列を識別するとともに、識別結果を保存しておく（ステップＳ２０２）。
【００２１】
乱数生成部７は、ビットデータのルールＲを生成するための乱数を生成する（ステップＳ２０３）。生成された乱数は、主制御部３を通じてルール管理部８に伝送される。ルール管理部８は、乱数生成部７によって生成された乱数に基づき、置換されるビットデータのアドレスをランダムに決定するルールＲを生成する（ステップＳ２０４）。本実施形態では、ルールＲとして、電子データｍに含まれるビットデータを置換するためのｎ個（ｎは２以上の整数、以下同様）のルールＲ１・・・Ｒｎを生成する。生成されたルールＲ１・・・Ｒｎは、電子データｍと共に、主制御部３を通じてビット置換部６に伝送される。なお、ルールＲの数（ｎ）は任意に設定することができる。
【００２２】
ビット置換部５は、ルールＲに従い、データ管理部４によって識別された電子データの各ブロック内のビットデータを置換する。ビットデータの置換は、ルールＲの数だけ行われる。そのため、ルールＲがＲ１からＲｎまでｎ個ある場合は、ビットデータが置換されたｎ個の置換された電子データｍ１・・・ｍｋ・・・ｍｎ（ｋは２≦ｋ≦ｎを満たす整数、以下同様）が生成される（ステップＳ２０５）。
置換された電子データｍ１・・・ｍｋ・・・ｍｎは、主制御部３によってハッシュ値導出部６に伝送される。
【００２３】
ハッシュ値導出部６は、複数の置換された電子データｍ１・・・ｍｋ・・・ｍｎに対し、一つのハッシュ関数ｈｋ＝ｈ（ｍｋ）を用いてハッシュ値Ｈｋを導出する（ステップＳ２０６）。
【００２４】
ここで、ハッシュ値Ｈｋの導出手順を、図３及び図４を参照して詳細に説明する。
図３はビットデータの置換の概要、図４はハッシュ値の導出原理をそれぞれ概略的に示した図である。
図３を参照すると、電子データｍは、ルールＲ１・・・Ｒｋ・・・Ｒｎによってビットデータが置換された電子データｍ１・・・ｍｋ・・・ｍｎに変換される。図示の例では、ルールＲ１：{{１，７}，{２，２}}，{３，３}，{ｎ−１，６}}により、元の電子データｍの第１ブロックの７ビット目のビット“１”と、第２ブロックの２ビット目のビット“０”とが置換される（{{１，７}，{２，２}}）。また、元の電子データの第３ブロックの３ビット目のビット“１”と、第ｎ−１ブロックの６ビット目のビット“０”が置換される（{３，３}，{ｎ−１，６}）。
【００２５】
続いて、図４に示すように、変換後の電子データｍ１・・・ｍｋ・・・ｍｎには、一種類のハッシュ関数ｈ（ｍｋ）が適用され、ｎ個のハッシュ値Ｈ１・・・Ｈｋ・・・Ｈｎが導出される。ハッシュ値を導出するための一般式は、次の通りである。「ＩＶ」は初期値である。
Ｈｋ＝ｈ（Ｈｋ−１||ｈｋ）  ただし、Ｈ１＝ｈ（ＩＶ||ｈ１）
以上のようにして、ハッシュ値導出部６により、最終的なハッシュ値Ｈｎが導出される（ステップＳ２０７）。
【００２６】
最終的なハッシュ値Ｈｎは、主制御部３によって、メモリ９に保持されているルールＲ及び初期値ＩＶと関連付けられる（ステップＳ２０８）。関連付けられた情報は、タイムスタンプトークンとして通信端末１１に送信される。
上述のようにして関連付けられたハッシュ値Ｈｎ、ルールＲ及び初期値ＩＶを含むタイムスタンプの情報項目は、例えば図５に示す内容のものとなる。
このように、タイムスタンプの情報項目にハッシュ値Ｈｎ、ルールＲ及び初期値ＩＶが含まれるので、タイムスタンプトークンの検証者は、タイムスタンプの情報項目と電子データｍとからハッシュ値Ｈｎを容易に求めることができる。その結果、電子データｍとタイムスタンプトークンとの対応関係、すなわち、電子データｍに関するタイムスタンプの証明時刻を確認することができる。
【００２７】
以上のように、本実施形態のネットワークシステムによれば、複数のハッシュ関数を用いることなく、一つのハッシュ関数を用いるだけで、タイムスタンプに用いるハッシュ値の耐改ざん性を向上させることができる。
また、複数のハッシュ値を導出する際に一種類のハッシュ関数しか用いないため、複数のハッシュ関数を用いる場合に比べて、ハッシュ値導出処理時に必要なハッシュ関数モジュールが少なくて済み、タイムスタンプシステムの実装時の開発コストを低減することができる。
【００２８】
なお、図３に示すビットデータの置換の説明では、元の電子データの第１ブロックのビットデータと第２ブロックのビットデータとを置換する場合について説明したが、図６に示すように、ビットデータとの置換を複数のブロックを跨ぐブロック間において実行するように構成してもよい。このようにすれば、ハッシュ値がＨｋとなるようなデータ対を発見しようとする攻撃者は、攻撃の目的を達成するために、電子データの全ブロックにわたる考察を余儀なくされるため、攻撃に対する処理量を増加させることができる。結果として、タイムスタンプにおけるハッシュ関数の強度を高めることができる。
【００２９】
以上の説明では、サーバ１が通信端末１１から初期値ＩＶを含む複数種類の情報を受信する形態について説明したが、本発明の実施の形態は、上記の例に限定されるものではなく、種々の変形実施が可能である。
例えば、ネットワークシステムを一つの情報処理装置乃至システムとして把握できるときに、サーバ１と通信端末１１の一方が上記の各処理部２〜９のいずれかを有し、他方が残部の処理部を有するようにしても良い。初期値ＩＶ及びルールＲも任意のメモリ領域に存在していればよい。
また、通信端末１１単独、あるいは、サーバ１単独で、情報の入出力手段、メモリ媒体及び上記の各処理部２〜９を含む構成であっても良い。
【図面の簡単な説明】
【００３０】
【図１】本発明の情報処理装置の構成を示すブロック図。
【図２】本発明の情報処理装置及びタイムスタンプトークンの発行方法の処理手順説明図。
【図３】本発明の情報処理装置及びタイムスタンプトークンの発行方法における置換された電子データの生成原理を概略的に示す図。
【図４】本発明の情報処理装置及びタイムスタンプトークンの発行方法におけるハッシュ値の導出方法の原理を概略的に示す図。
【図５】本発明の情報処理装置及びタイムスタンプトークンの発行方法におけるハッシュ値Ｈｎ、ルールＲ及び初期値ＩＶを含むタイムスタンプの情報項目を示す図。
【図６】本発明の他の形態による情報処理装置及びタイムスタンプトークンの発行方法におけるハッシュ値の導出方法の原理を概略的に示す図。
【符号の説明】
【００３１】
１  サーバ、２  Ｉ／Ｆ、３  主制御部、４  データ管理部、５  ビット置換部、６  ハッシュ値導出部、７  乱数生成部、８  ルール管理部、９  メモリ、１０ネットワーク、１１  通信端末。
【図１】
2007256756.tif 000003
【図２】
2007256756.tif 000004
【図３】
2007256756.tif 000005
【図４】
2007256756.tif 000006
【図５】
2007256756.tif 000007
【図６】
2007256756.tif 000008