(57)【要約】      （修正有）【課題】計算上の傾向を加味したアルゴリズムにすることで、従来のハッシュ関数などを用いる検証方法より全体の計算量を小さくすることができ、検証を高速化できる。【解決手段】検証の元データＸをｄ個の分割情報Ｘiとし、次式によりＸiに対応するｄ個の識別子Ｙiを生成する（ｇ、Ｎは共に２以上の自然数）。2008178005.tif 000020  検証対象となるデータＸ´をＸiと同様な方法でｄ個の分割情報Ｘi´とし、次式によりＹ´を計算する（ｅｉは整数）。2008178005.tif 000021そして次式によりｘを計算する。2008178005.tif 000022Ｃ＝ｇｘ mod Ｎ  を計算し、Ｃ＝Ｙ´mod Ｎであれば整合性有りと判定する。【選択図】なし【特許請求の範囲】
【請求項１】
２つのデータの整合性を検証するデータ検証システムであって、
所定の情報Ｘを記憶する第１データ記憶部と、
上記情報Ｘが入力され、これを予め定められた手順に従いｄ個（ｄは２以上の自然数）に分割して分割情報Ｘi（２≦ｉ≦ｄ）を生成し出力する第１データ分割部と、
上記分割情報Ｘiが入力され、識別子Ｙｉを
【数１】
2008178005.tif 000007
（Ｎ、ｇは共に２以上の自然数）により計算し出力する識別子計算部と、
上記計算した識別子Ｙｉを記憶する識別子記憶部と、  
上記情報Ｘとの比較対象とする情報Ｘ´を記憶する第２データ記憶部と、
上記情報Ｘ´が入力され、これを上記予め定められた手順に従いｄ個に分割して分割情報Ｘi´を生成し出力する第２データ分割部と、
上記識別子Ｙｉが入力され、Ｙ´を
【数２】
2008178005.tif 000008
（ｅｉは整数）により計算し出力するＹ´計算部と、
上記分割情報Ｘｉ´が入力され、ｘを
【数３】
2008178005.tif 000009
により計算し、出力するｘ計算部と、
上記ｘが入力され、ＣをＣ＝ｇｘ mod Ｎにより計算し出力するＣ計算部と、
上記Ｙ´と上記Ｃとが入力され、Ｃ＝Ｙ´mod Ｎであれば整合性有り、そうでなければ整合性無しとの判定結果を出力する整合性判定部と、
を具備することを特徴とするデータ検証システム。
【請求項２】
請求項１に記載のデータ検証システムにおいて、上記Ｎは素因数分解困難な正の合成数であることを特徴とするデータ検証システム。
【請求項３】
２つのデータの整合性を検証するデータ検証システムであって、
Ｎ＝ｐ・ｑ（ｐとｑは共に素数）であり、
所定の情報Ｘを記憶する第１データ記憶部と、
上記情報Ｘが入力され、これを予め定められた手順に従いｄ個（ｄは２以上の自然数）に分割して分割情報Ｘi（２≦ｉ≦ｄ）を生成し出力する第１データ分割部と、
上記分割情報Ｘiが入力され、ξｉをξｉ＝Ｘｉ mod （ｐ−１）・（ｑ−１）により計算し出力するξ計算部と、
上記ξｉが入力され、識別子ＹｉをＹｉ＝ｇξimod Ｎ（ｇは２以上の自然数）により計算し出力する識別子計算部と、
上記計算した識別子Ｙｉを記憶する識別子記憶部と、  
上記情報Ｘとの比較対象とする情報Ｘ´を記憶する第２データ記憶部と、
上記情報Ｘ´が入力され、これを上記予め定められた手順に従いｄ個に分割して分割情報Ｘi´を生成し出力する第２データ分割部と、
上記識別子Ｙｉが入力され、Ｙ´を
【数４】
2008178005.tif 000010
（ｅｉは整数）により計算し出力するＹ´計算部と、
上記分割情報Ｘｉ´が入力され、ｘを
【数５】
2008178005.tif 000011
により計算し、出力するｘ計算部と、
上記ｘが入力され、ＣをＣ＝ｇｘ mod Ｎにより計算し出力するＣ計算部と、
上記Ｙ´と上記Ｃとが入力され、Ｃ＝Ｙ´mod Ｎであれば整合性有り、そうでなければ整合性無しとの判定結果を出力する整合性判定部と、
を具備することを特徴とするデータ検証システム。
【請求項４】
請求項３に記載のデータ検証システムにおいて、上記Ｎはｐとｑとに素因数分解することが困難な値であることを特徴とするデータ検証システム。
【請求項５】
請求項１〜４のいずれかに記載のデータ検証システムにおいて、上記ｇはＮと互いに素な２以上の自然数であることを特徴とするデータ検証システム。
【請求項６】
請求項１〜５のいずれかに記載のデータ検証システムにおいて、上記ｅｉをランダムに生成し出力するｅｉ生成部を具備することを特徴とするデータ検証システム。
【請求項７】
請求項６に記載のデータ検証システムにおいて、上記ｅｉ生成部は、
１以上のランダムな自然数ｅを生成し出力する乱数生成部と、
上記ｅが入力され、上記ｅｉをｅｉ＝ｅｉ−１ mod ｓ（ｓは２以上の自然数）により計算して出力する剰余べき乗計算部と、
を備えることを特徴とするデータ検証システム。
【請求項８】
請求項６に記載のデータ検証システムにおいて、上記ｅｉ生成部は、
１以上のランダムな自然数ｅを生成し出力する乱数生成部と、
上記ｅが入力され、上記ｅｉを
ｅｉ＝Ｈ（ｅ，ｉ）
（（ｅ，ｉ）はｅとｉとのビット連結、Ｈは逆像計算が困難な関数）により計算して出力するＨ関数計算部と、
を備えることを特徴とするデータ検証システム。
【請求項９】
請求項６に記載のデータ検証システムにおいて、上記ｅｉ生成部は、
１以上のランダムな自然数ｅを生成し出力する乱数生成部と、
上記ｅが入力され、上記ｅｉを
ｅｉ＝Ｓ（ｅ，ｉ）
（（ｅ，ｉ）はｅとｉとのビット連結、Ｓは衝突困難な関数）により計算して出力するＳ関数計算部と、
を備えることを特徴とするデータ検証システム。
【請求項１０】
請求項１〜５のいずれかに記載のデータ検証システムにおいて、上記ｅｉは定数であることを特徴とするデータ検証システム。
【請求項１１】
所定の情報Ｘを記憶するデータ記憶部と、
上記情報Ｘが入力され、これを予め定められた手順に従いｄ個（ｄは２以上の自然数）に分割して分割情報Ｘi（２≦ｉ≦ｄ）を生成し出力するデータ分割部と、
上記分割情報Ｘiが入力され、識別子Ｙｉを
【数６】
2008178005.tif 000012
（Ｎ、ｇは共に２以上の自然数）により計算し出力する識別子計算部と、
を具備する識別子生成装置。
【請求項１２】
Ｎ＝ｐ・ｑ（ｐとｑは共に素数）であり、
所定の情報Ｘを記憶するデータ記憶部と、
上記情報Ｘが入力され、これを予め定められた手順に従いｄ個（ｄは２以上の自然数）に分割して分割情報Ｘi（２≦ｉ≦ｄ）を生成し出力するデータ分割部と、
上記分割情報Ｘiが入力され、ξｉをξｉ＝Ｘｉ mod （ｐ−１）・（ｑ−１）により計算し出力するξ計算部と、
上記ξｉが入力され、識別子ＹｉをＹｉ＝ｇξi mod Ｎ（ｇは２以上の自然数）により計算し出力する識別子計算部と、
を具備する識別子生成装置。
【請求項１３】
請求項１１、１２のいずれかの識別子生成装置から出力された上記識別子Ｙｉを記憶する識別子記憶部と、  
上記識別子Ｙｉの生成元情報である情報Ｘの比較対象とする情報Ｘ´を記憶するデータ記憶部と、
上記情報Ｘ´が入力され、これを予め定められた手順に従いｄ個（ｄは２以上の自然数）に分割して分割情報Ｘi´（２≦ｉ≦ｄ）を生成し出力するデータ分割部と、
上記識別子Ｙｉが入力され、Ｙ´を
【数７】
2008178005.tif 000013
（ｅｉは整数、Ｎは２以上の自然数）により計算し出力するＹ´計算部と、
上記分割情報Ｘｉ´が入力され、ｘを
【数８】
2008178005.tif 000014
により計算し、出力するｘ計算部と、
上記ｘが入力され、ＣをＣ＝ｇｘ mod Ｎ（ｇは２以上の自然数）により計算し出力するＣ計算部と、
上記Ｙ´と上記Ｃとが入力され、Ｃ＝Ｙ´mod Ｎであれば整合性有り、そうでなければ整合性無しとの判定結果を出力する整合性判定部と、
を具備するデータ検証装置。
【請求項１４】
２つのデータの整合性を検証するデータ検証方法であって、
第１データ分割部が、所定の情報Ｘを予め定められた手順に従いｄ個（ｄは２以上の自然数）に分割して分割情報Ｘi（２≦ｉ≦ｄ）を生成するステップと、
識別子計算部が、上記分割情報Ｘiから識別子Ｙｉを
【数９】
2008178005.tif 000015
（Ｎ、ｇは共に２以上の自然数）により計算するステップと、  
第２データ分割部が、上記情報Ｘとの比較対象とする情報Ｘ´を上記予め定められた手順に従いｄ個に分割して分割情報Ｘi´を生成するステップと、
Ｙ´計算部が、上記識別子ＹｉからＹ´を
【数１０】
2008178005.tif 000016
（ｅｉは整数）により計算するステップと、
ｘ計算部が、上記分割情報Ｘｉ´からｘを
【数１１】
2008178005.tif 000017
により計算するステップと、
Ｃ計算部が、上記ｘからＣを、Ｃ＝ｇｘ mod Ｎにより計算するステップと、
整合性判定部が、上記Ｙ´と上記Ｃとを比較し、Ｃ＝Ｙ´mod Ｎであれば整合性有り、そうでなければ整合性無しとの判定結果を出力するステップと、
を具備することを特徴とするデータ検証方法。
【請求項１５】
２つのデータの整合性を検証するデータ検証方法であって、
Ｎ＝ｐ・ｑ（ｐとｑは共に素数）であり、
第１データ分割部が、所定の情報Ｘを予め定められた手順に従いｄ個（ｄは２以上の自然数）に分割して分割情報Ｘi（２≦ｉ≦ｄ）を生成するステップと、
ξ計算部が、上記分割情報Ｘiからξｉを、ξｉ＝Ｘｉ mod （ｐ−１）・（ｑ−１）により計算するステップと、
識別子計算部が、上記ξｉから識別子Ｙｉを、Ｙｉ＝ｇξi mod Ｎ（ｇは２以上の自然数）により計算するステップと、
第２データ分割部が、上記情報Ｘとの比較対象とする情報Ｘ´を上記予め定められた手順に従いｄ個に分割して分割情報Ｘi´を生成するステップと、
Ｙ´計算部が、上記識別子ＹｉからＹ´を
【数１２】
2008178005.tif 000018
（ｅｉは整数）により計算するステップと、
ｘ計算部が、上記分割情報Ｘｉ´からｘを
【数１３】
2008178005.tif 000019
により計算するステップと、
Ｃ計算部が、上記ｘからＣを、Ｃ＝ｇｘ mod Ｎにより計算するステップと、
整合性判定部が、上記Ｙ´と上記Ｃとを比較し、Ｃ＝Ｙ´mod Ｎであれば整合性有り、そうでなければ整合性無しとの判定結果を出力するステップと、
を具備することを特徴とするデータ検証方法。
【請求項１６】
請求項１〜１０のいずれかに記載したシステムとしてコンピュータを機能させるためのプログラム。
【請求項１７】
請求項１１、１２のいずれかに記載した装置としてコンピュータを機能させるためのプログラム。
【請求項１８】
請求項１３に記載した装置としてコンピュータを機能させるためのプログラム。
【請求項１９】
請求項１６に記載したプログラムを記録したコンピュータが読み取り可能な記録媒体。
【請求項２０】
請求項１７に記載したプログラムを記録したコンピュータが読み取り可能な記録媒体。
【請求項２１】
請求項１８に記載したプログラムを記録したコンピュータが読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの整合性を検証する技術に関し、詳しくは、時間的又は物理的に離隔した２つのデータが同一であるかどうかを検証するデータ検証システム、その方法、識別子生成装置、データ検証装置、それらのプログラム及びそのプログラムを記憶する記録媒体に関する。
【背景技術】
【０００２】
物理媒体に記憶されている情報は、時間を経ることにより様々なトラブルによって変化することがある。この変化を検出する手法としてはビット誤りを検出するparityやバースト誤りを検出するＣＲＣなどが有名である。これらの方式は計算が簡便であり、ディスクの異常を検知する方法として応用されＲＡＩＤなどのハードディスクやフレキシブルディスクで用いられている。
【０００３】
また、物理媒体同士が通信を行って転送される経路中になんらかのトラブルで情報が変化することもある。このため、巨大なデータＸをダウンロードする場合は、データＸと同時にＭＤ５やＳＨＡ−１のハッシュ値などによる短いビット長からなる識別子Ｙをダウンロードし、整合性が疑われるデータＸ´（ダウンロードを経たデータＸ）について識別子を計算して、データＸの識別子Ｙと比較することで正しくダウンロードできたかどうかを確認することがある。
【０００４】
もちろん、先の誤り検出符号を用いても同様の変化の検出が可能であるが、特にインターネットなどの不特定多数が利用するネットワークを介した通信の場合、通信内容が悪意のあるエンティティに書き換えられることも考慮し、人為的な操作に対しても暗号学的に安全なハッシュ関数などを用いることが多い。
【非特許文献１】Bruce Schneier 著、山形浩生 訳、“暗号技術大全”、p475〜509、ソフトバンクパブリッシング、2003年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ハッシュ関数などによる安全性を考慮した識別子は、識別子が計算される周辺の状況に比べ計算量が相対的に多く、識別子の計算に時間がかかる点である。このことは、特に検証対象のデータＸが巨大な場合に顕著である。近年ではハッシュ関数計算処理も高速化が図られてはいるが、ＡＤＳＬや光ファイバを利用した通信回線の普及に伴って回線速度が飛躍的に上昇している。そのため、データＸがこのような高速ネットワークにより伝送される場合、通信の完全性をハッシュ関数などを用いてリアルタイムに検証することが困難になっている。
【課題を解決するための手段】
【０００６】
本発明のデータ検証システムは、第１データ記憶部、第１データ分割部、識別子計算部、識別子記憶部、第２データ記憶部、第２データ分割部、Ｙ´計算部、ｘ計算部、Ｃ計算部及び整合性判定部を具備する。
第１データ記憶部は、所定の情報Ｘを記憶する。
第１データ分割部は、上記情報Ｘが入力され、これを予め定められた手順に従いｄ個（ｄは２以上の自然数）に分割して分割情報Ｘi（２≦ｉ≦ｄ）を生成し出力する。
識別子計算部は、上記分割情報Ｘiが入力され、識別子Ｙｉを
【０００７】
【数１】
2008178005.tif 000002
（Ｎ、ｇは共に２以上の自然数）により計算し出力する。
識別子記憶部は、上記計算した識別子Ｙｉを記憶する。
【０００８】
第２データ記憶部は、上記情報Ｘとの比較対象とする情報Ｘ´を記憶する。
第２データ分割部は、上記情報Ｘ´が入力され、これを上記予め定められた手順に従いｄ個に分割して分割情報Ｘi´を生成し出力する。
Ｙ´計算部は、上記識別子Ｙｉが入力され、Ｙ´を
【数２】
2008178005.tif 000003
（ｅｉは整数）により計算し出力する。
ｘ計算部は、上記分割情報Ｘｉ´が入力され、ｘを
【０００９】
【数３】
2008178005.tif 000004
により計算し、出力する。
Ｃ計算部は、上記ｘが入力され、Ｃを
Ｃ＝ｇｘ mod Ｎ      (4)
により計算し出力する。
整合性判定部は、上記Ｙ´と上記Ｃとが入力され、Ｃ＝Ｙ´mod Ｎであれば整合性有り、そうでなければ整合性無しとの判定結果を出力する。
【発明の効果】
【００１０】
本発明のデータ検証システムは、識別子の生成と整合性の検証に異なるアルゴリズムを用いることにより、計算回数が少ない識別子生成時の計算の１回の計算量より、計算回数の多い整合性検証時の計算の１回の計算量を小さくしている。このように計算上の傾向を加味したアルゴリズムにすることで、従来のハッシュ関数などを用いる検証方法より全体の計算量を小さくすることができ、よって検証を高速化できる。
【発明を実施するための最良の形態】
【００１１】
〔第１実施形態〕
図１、図２は第１実施形態のデータ検証システムを構成する識別子生成装置１０とデータ検証装置２０の機能構成例である。また、図３は第１実施形態の処理フローである。
識別子生成装置１０は、第１データ記憶部１１、第１データ分割部１２、識別子計算部１３、送信部１８及び制御部１９から構成される。
第１データ記憶部１１は、検証の元となるデータＸが記憶される（Ｓ１）。
第１データ分割部１２は、第１データ記憶部１１に記憶されたデータＸが入力されると、これをｄ個（ｄは２以上の自然数）に分割して、ｄ個の分割情報Ｘｉ（２≦ｉ≦ｄ）を出力する（Ｓ２）。
ｄの値については適宜決定してよく、例えばｄを定数として定めてもよいし、個々のＸｉが全て同じ長さとなるようにＸの長さに応じて定めてもよい。
データＸをｄ個に分割する方法についても適宜決定してよく、例えばデータＸ全体を単純にｄ個に分割してもよいし、先頭から１ワードごとにＸｉに割り振ってもよい。
【００１２】
識別子計算部１３は、第１データ分割部１２で分割されたｄ個のＸｉが入力されると、Ｘｉに対応するｄ個の識別子Ｙｉを式(1)により計算して出力する（Ｓ３）。なお、Ｎとｇは共に２以上の自然数である。
上記計算の際にはＸｉを適当な方法で０以上の自然数に対応させる。例えば、ビット列Ｘｉを長大な２進数であると解釈して対応させる。
送信部１８は、上記データＸを上記ｄ個の識別子Ｙｉと共にネットワークを介してデータ検証装置２０に送信する（Ｓ４）。なお、ネットワークは装置間に距離的離隔を生じさせるものであればＷＡＮでもＬＡＮでも構わない。
【００１３】
制御部１９は、識別子生成装置１０の上記各処理を制御する。
データ検証装置２０は、識別子記憶部２１、第２データ記憶部２２、Ｙ´計算部２３、第２データ分割部２４、ｘ計算部２５、Ｃ計算部２６、整合性判定部２７、受信部２８及び制御部２９から構成される。
受信部２８は、ネットワークを介して送信されたデータＸ´と上記ｄ個の識別子Ｙｉとを受信する（Ｓ５）。ここで、データＸ´は識別子Ｙｉに基づき元データＸとの整合性判定を行う対象となるデータである。なお、識別子Ｙｉは必ずデータＸから生成されているものとし、また伝送路において変化・改ざん等されることなく受信されているものとする。
【００１４】
識別子記憶部２１は、受信部２８で受信したｄ個の識別子Ｙｉを記憶する（Ｓ６）。
第２データ記憶部２２は、受信部２８で受信したデータＸ´を記憶する（Ｓ６）。
Ｙ´計算部２３は、識別子記憶部２１に記憶されたｄ個の識別子Ｙｉが入力されると、Ｙ´を式(2)によって計算して出力する（Ｓ７）。なお、ｅｉは整数である。
第２データ分割部２４は、第２データ記憶部２２に記憶されたデータＸ´が入力されると、これをｄ個（ｄは２以上の自然数）に分割して、ｄ個の分割情報Ｘｉ´（２≦ｉ≦ｄ）を出力する（Ｓ８）。ｄの値の決定方法及びデータＸ´をｄ個に分割する方法については、第１データ分割部１２と共通の予め定められた手順による。
ｘ計算部２５は、第２データ分割部２４で分割されたｄ個のＸｉ´が入力されると、式(3)によりｘを計算して出力する（Ｓ９）。
【００１５】
Ｃ計算部２６は、ｘ計算部２５で計算されたｘが入力されると、式(4)によりＣを計算して出力する（Ｓ１０）。
整合性判定部２７は、データＸから生成された識別子Ｙｉに基づき計算された上記Ｙ´と、データＸ´に基づき計算された上記Ｃとが入力されると、この両者を比較し、Ｃ＝Ｙ´mod ＮであればデータＸとデータＸ´とは整合性有りとの判定結果を出力し、そうでなければ整合性無しとの判定結果を出力する（Ｓ１１）。
制御部２９は、データ検証装置２０の上記各処理を制御する。
以上のように、本発明はハッシュ関数による整合性検証のように識別子生成部と検証部とで同じ演算を行うものと異なり、識別子生成部１０は式(1)の演算を行い、データ検証部２０は式(2)〜(4)の演算を行うというようにそれぞれ異なったアルゴリズムで演算を行う。
【００１６】
一般的に情報の「書き込まれる回数」と「読み込まれる回数」を比較した場合、「読み込まれる回数」の方が多いと考えられる。そのため、情報の完全性を検証する場合も、完全性の基準となる情報から識別子を生成する回数（＝「書き込まれる回数」）に比べて、その基準と差異が無いかどうかを調べる検証の回数（＝「読み込まれる回数」）の方が必然的に多くなる。特に大容量ファイルの代表格である映像コンテンツなどは一度作成した情報を、多くの人が何度も読み込むという状況が想定される。
そこで、演算コストが「識別子の生成」＞「識別子によるデータ整合性検証」となることが望ましい状況が存在することに注目し、本発明では識別子の生成と識別子によるデータ整合性検証に異なるアルゴリズムを採用した。
【００１７】
具体的には、式(1)の識別子の計算量は基本的にＸの大きさに比例することから、特に、Ｘが大きい場合においては識別子の生成にもある程度の時間を要する。しかし検証時については、式(2)の計算はＸのダウンロードと並行して行うことが可能であり、式(3)の計算は単に積和をとるだけであるため負荷が小さく、式(4)の計算は１回で終わるというように、検証時の演算コストは相対的に軽量化している。
このようなアルゴリズム構成は、映像コンテンツのように、データの整合性検証にはリアルタイム性を求めるが、識別子の生成は多少遅くても問題無い場合に特に有効である。
【００１８】
〔第２実施形態〕
第１実施形態は、物理媒体同士が通信を行って情報が転送される経路中に何らかのトラブルで情報が変化するような場合の構成、つまり物理的に離隔したデータＸとデータＸ´との整合性を検証する構成である。これに対し、第２実施形態は、同一の物理媒体に記憶されている情報が時間を経ることにより何らかのトラブルで情報が変化するような場合の構成、つまり時間的に離隔したデータＸとデータＸ´との整合性を検証する構成である。従って、第２実施形態においては、第１実施形態と異なり識別子生成装置とデータ検証装置とは一体的に構成される。
【００１９】
図４は第２実施形態のデータ検証システムを構成する一体型装置３０の機能構成例である。
一体型装置３０は、データ記憶部３１、データ分割部３２、識別子計算部１３、識別子記憶部２１、Ｙ´計算部２３、ｘ計算部２５、Ｃ計算部２６、整合性判定部２７及び制御部３９から構成される。
識別子計算部１３、識別子記憶部２１、Ｙ´計算部２３、ｘ計算部２５、Ｃ計算部２６、整合性判定部２７は第１実施形態の図１、図２の同名の部位と同じものである。従って、図４の中で図１、図２と対応する部分については同一参照番号を付け、説明は省略する。その他の図面についても同様とする。
【００２０】
データ記憶部３１は第１実施形態の第１データ記憶部１１と第２データ記憶部２２の機能を合わせ持つものであり、またデータ分割部３２は第１実施形態の第１データ分割部１２と第２データ分割部２４の機能を合わせ持つものである。
制御部３９は、一体型装置３０で行われる各処理を制御する。
第２実施形態の処理フローを図５に示す。
まず、検証に用いる識別子を生成する。
【００２１】
検証の元となるデータＸがデータ記憶部３１に記憶される（Ｓ１）。データ分割部３２はデータ記憶部３１に記憶されたデータＸをｄ分割してｄ個の分割情報Ｘｉを作成し出力する。ｄの値の決定方法及びデータＸ´をｄ個に分割する方法については、第１データ分割部１２と同様の考え方による（Ｓ２）。識別子計算部１３にデータ分割部３２で分割されたｄ個のＸｉが入力され、Ｘｉに対応するｄ個の識別子Ｙｉを式(1)により計算して出力し（Ｓ３）、識別子記憶部２１に記憶する（Ｓ４）。
そして、必要時などに次の検証処理を行う。
【００２２】
Ｙ´計算部２３は識別子記憶部２１に記憶されたｄ個の識別子Ｙｉを用いてＹ´を式(2)により計算する（Ｓ５）。データ分割部３２は、データ記憶部３１に記憶されているデータＸ´（識別子生成時のデータＸの、時間経過後のデータ）をＳ２で適用した方法と同じ方法でｄ分割してｄ個の分割情報Ｘｉ´を作成して出力する（Ｓ６）。ｘ計算部２５は、第２データ分割部２４で分割されたｄ個のＸｉ´がｘ計算部２５に入力されると式(3)によりｘを計算して出力する（Ｓ７）。Ｃ計算部２６は、ｘ計算部２５で計算されたｘが入力されると、式(4)によりＣを計算して出力する（Ｓ８）。整合性判定部２７は、データＸから生成された識別子Ｙｉに基づき計算された上記Ｙ´と、データＸ´に基づき計算された上記Ｃとが入力されるとこの両者を比較し、Ｃ＝Ｙ´mod ＮであればデータＸとデータＸ´とは整合性有りとの判定結果を出力し、そうでなければ整合性無しとの判定結果を出力する（Ｓ９）。
以上の構成により、同一の物理媒体に記憶されている情報が時間を経ることにより何らかのトラブルで情報が変化しても、第１実施形態同様、速やかにデータの整合性の検証を行うことができる。
【００２３】
〔第３実施形態〕
第３実施形態は、第２実施形態の一体型構成において外部記憶装置を使用する構成、詳しくは、識別子の生成後にデータＸを一旦ネットワークを介した外部記憶装置に移動・保存し、この外部記憶装置に保存したデータＸ´を再度一体型装置にダウンロードする場合のデータＸとデータＸ´との整合性を検証する構成である。
【００２４】
図６は第３実施形態のデータ検証システムを構成する一体型装置４０と外部記憶装置２００の機能構成例である。
一体型装置４０は、第１データ記憶部４１、データ分割部３２、識別子計算部１３、識別子記憶部２１、Ｙ´計算部２３、ｘ計算部２５、Ｃ計算部２６、整合性判定部２７、送受信部４８及び制御部４９から構成される。
データ分割部３２、識別子計算部１３、識別子記憶部２１、Ｙ´計算部２３、ｘ計算部２５、Ｃ計算部２６、整合性判定部２７は第２実施形態と同様である。
また、第１データ記憶部４１は、第２実施形態のデータ記憶部３１に送受信部４８とのインタフェース機能を付加したものである。
送受信部４８は、一体型装置４０と外部記憶装置２００との間の通信機能を有する。
制御部４９は、一体型装置４０で行われる各処理を制御する。
外部記憶装置２００は、第２データ記憶部２２２と送受信部４８とから構成される。
第２データ記憶部２２２は、送受信部４８で受信したデータＸ´を記憶する。
第３実施形態の処理フローを図７に示す。
まず、一体型装置４０で検証に用いる識別子を生成する。
【００２５】
検証の元となるデータＸが第１データ記憶部４１に記憶される（Ｓ１）。データ分割部３２は第１データ記憶部４１に記憶されたデータＸをｄ分割してｄ個の分割情報Ｘｉを作成し出力する。ｄの値の決定方法及びデータＸ´をｄ個に分割する方法については、第１データ分割部１２と同様の考え方による（Ｓ２）。識別子計算部１３は、データ分割部３２で分割されたｄ個のＸｉが入力されると、Ｘｉに対応するｄ個の識別子Ｙｉを式(1)により計算して出力し（Ｓ３）、識別子記憶部２１はこれを記憶する（Ｓ４）。
【００２６】
次に、データＸを外部記憶装置２００に移動・保存する。
送受信部４８は第１データ記憶部４１に記憶されたデータＸを外部記憶装置２００に送信し、送信後、制御部４９は第１データ記憶部４１のデータＸを消除する（Ｓ５）。外部記憶装置２００の送受信部４８は、ネットワークを介して送信されたデータＸ´を受信し、データＸ´を第２データ記憶部２２２に記憶する（Ｓ６）。
そして、データＸ´を一体型装置４０にダウンロードし整合性を検証する。
【００２７】
第２データ記憶部２２２に記憶されたデータＸ´は外部記憶装置２００の送受信部４８からネットワークを介して一体型装置４０に送信される（Ｓ７）。ネットワークを介して送信されたデータＸ´を一体型装置４０の送受信部４８で受信し、第１データ記憶部４１に記憶する（Ｓ８）。Ｙ´計算部２３は、識別子記憶部２１に記憶されたｄ個の識別子Ｙｉを用いてＹ´を式(2)により計算する（Ｓ９）。データ分割部３２は、第１データ記憶部４１に記憶されているデータＸ´をＳ２で適用した方法と同じ方法でｄ分割してｄ個の分割情報Ｘｉ´を作成して出力する（Ｓ１０）。ｘ計算部２５は、第２データ分割部２４で分割されたｄ個のＸｉ´がｘ計算部２５に入力されると、式(3)によりｘを計算して出力する（Ｓ１１）。Ｃ計算部２６は、ｘ計算部２５で計算されたｘが入力されると、式(4)によりＣを計算して出力する（Ｓ１２）。整合性判定部２７は、データＸから生成された識別子Ｙｉに基づき計算された上記Ｙ´と、データＸ´に基づき計算された上記Ｃとが入力されると、この両者を比較して、Ｃ＝Ｙ´mod ＮであればデータＸとデータＸ´とは整合性有りとの判定結果を出力し、そうでなければ整合性無しとの判定結果を出力する（Ｓ１３）。
【００２８】
以上の構成により、外部記憶装置を使用する場合においても、速やかにデータＸとデータＸ´との整合性の検証を行うことができる。
【００２９】
〔第４実施形態〕
第４実施形態は、識別子などの計算に用いる上記Ｎの値を素因数分解困難な正の合成数とし、悪意者による攻撃に対する安全性を向上するものである。
式(1)などの計算に用いるＮは２以上の自然数としているが、Ｎが素数の場合や容易に素因数分解できる数の場合、Ｙｉの位数を知ることができ、その結果、データＸに基づき生成されたＹｉについて式(1)を成立させる複数のＸiを計算できることになるため、悪意者による攻撃に対する安全性に不安が残る。
そこで、第４実施形態はＮを素因数分解が困難な正の合成数とし、衝突困難性を素因数分解の困難性に帰着させることで安全性を高めることができるものである。
【００３０】
〔第５実施形態〕
第５実施形態は、識別子生成者がＮ＝ｐ・ｑ（ｐ、ｑは共に素数）のｐ、ｑを知っていることを前提として、識別子の計算の高速化を図る構成である。
図８は第５実施形態のデータ検証システムを構成する識別子生成装置５０の機能構成例である。なお、ネットワークを介して対向するデータ検証装置の構成は第１実施形態と同様なものでよい。図９は第５実施形態の処理フローである。
識別子生成装置５０は、第１データ記憶部１１、第１データ分割部１２、ξ計算部５１、識別子計算部５３、送信部１８及び制御部５９から構成される。
【００３１】
第１データ記憶部１１、第１データ分割部１２及び送信部１８は、第１実施形態と同様である。つまり、第５実施形態は第１実施形態の識別子計算部１３をξ計算部５１と識別子計算部５３に置き換えた構成である。
なお、第２実施形態、第３実施形態の構成においても、識別子計算部１３をξ計算部５１と識別子計算部５３に置き換えることで、同様に高速化の効果を得ることができる。
ξ計算部５１は、第１データ分割部１２で分割されたｄ個のＸｉが入力され、Ｘｉに対応するｄ個のξｉを次式により計算して出力する。なお、ｐとｑは共に素数である。
ξｉ＝Ｘｉ mod （ｐ−１）・（ｑ−１）    (5)
識別子計算部５３は、ξ計算部５１で計算されたｄ個のξｉが入力され、ξｉに対応するｄ個の識別子Ｙｉを次式により計算して出力する。なお、Ｎ＝ｐ・ｑである。
【００３２】
【数４】
2008178005.tif 000005
制御部５９は、識別子生成装置５０で行われる各処理を制御する。
式(1)による識別子の計算は、元となるデータＸをｄ個に分割して行っているものの、特にデータＸが大きな値の場合には全体の処理速度への影響が大きい。
式(1)のような剰余計算の解（式(1)においてはＹｉ）はＮを法とする場合、べき乗数Ｘｉに関し、Ｙｉの位数の周期（ｐ、ｑが素数でＮ＝ｐ・ｑの場合、（ｐ−１）・（ｑ−１））で繰り返し同じ値をとる。このような特性から、式(1)のようにＸｉで直接べき乗するのではなく、先に式(5)のようにＸｉに対し位数により剰余計算を行い、Ｘｉを位数の範囲内に縮小化した計算結果ξｉをＸｉの代わりに利用して式(6)の剰余計算を行っても同じ解が得られる。
【００３３】
第５実施形態は、このような計算方法を採ることで単にデータＸをｄ個に分割した値をそのままべき乗するよりも、その値が更に位数の範囲内に縮小化されており、計算量を小さくできることから、識別子の計算の高速化を図ることができるものである。
なお、第５実施形態ではＮ＝ｐ・ｑの場合を取り上げたが、Ｎが素数の場合においても式(5)を、ξｉ＝Ｘｉ mod （Ｎ−１）に変えることで同様に高速化の効果を得ることができる。
【００３４】
〔第６実施形態〕
第６実施形態は、第５実施形態の場合において第４実施形態と同様に、識別子などの計算に用いる上記Ｎの値を素因数分解困難な正の合成数とするものである。
この形態をとることにより、第４実施形態で得られるより高い安全性と、第５実施形態で得られるより高い処理速度とを共に享受することができる。
【００３５】
〔第７実施形態〕
第７実施形態は、識別子などの計算に用いる上記ｇの値をＮと互いに素な２以上の自然数とし、第４実施形態と同様、悪意者による攻撃に対する安全性を向上するものである。
もし、式(1)などの計算に用いるｇがＮと互いに素でない数の場合、ｇとＮとの公約数を見出されればＮを素因数分解できてしまうため、悪意者による攻撃への発端になる危険がある。
このような理由から、第７実施形態はｇをＮと互いに素な数とすることで、攻撃の危険を回避し、より安全性の向上を図ることができるものである。
【００３６】
〔第８実施形態〕
第８実施形態は、上記Ｙ´の計算及び上記ｘの計算において用いるｅｉの値をランダムな値にすることで、悪意者の攻撃に対する安全性を高める構成である。
図１０は第８実施形態のデータ検証システムを構成するデータ検証装置８０の機能構成例である。なお、ネットワークを介して対向する識別子生成装置の構成は第１実施形態と同様なものでよい。図１１は第８実施形態の処理フローである。
データ検証装置８０は、識別子記憶部２１、第２データ記憶部２２、ｅｉ生成部８１、Ｙ´計算部８３、第２データ分割部２４、ｘ計算部８５、Ｃ計算部２６、整合性判定部２７、受信部２８及び制御部８９から構成される。
【００３７】
つまり、第８実施形態は第１実施形態のＹ´計算部２３をＹ´計算部８３に、ｘ計算部２５をｘ計算部８５に置き換えると共に、ｅｉ生成部８１を加えた構成である。
なお、第２実施形態、第３実施形態の構成においても、Ｙ´計算部２３をＹ´計算部８３に、ｘ計算部２５をｘ計算部８５に置き換えると共に、ｅｉ生成部８１を加えることで、同様に安全性の向上を図ることができる。
ｅｉ生成部８１は、整数をランダムに発生し出力する。
【００３８】
Ｙ´計算部８３は、識別子記憶部２１に記憶されたｄ個の識別子Ｙｉとｅｉ生成部８１から出力されたｅｉとが入力され、Ｙ´を式(2)によって計算して出力する。
ｘ計算部８５は、第２データ分割部２４で分割されたｄ個のＸｉ´とｅｉ生成部８１から出力されたｅｉとが入力され、式(3)によりｘを計算して出力する。
式(2)と式(3)において、ｅｉをそれぞれべき乗、乗算しているのは以下の理由による。
式(2)と式(3)にｅｉが無い場合を考えると、式(2)を変形するとＹ´＝ｇＸmod Nとなり、式(4)を変形するとＣ＝ｇＸ´mod Nとなる。そして、両式はｇとＮが共通しており、べき乗剰余演算の性質からＣ＝Ｙ´mod Ｎが成立するのはデータＸとデータＸ´とが整合している（べき乗部分の値が同じ）場合に限らず、従って、悪意者がＣ＝Ｙ´mod Ｎは成立するがＸ＝Ｘ´は成立しないＸ´を使って攻撃をしかけてくるという危険性は否めない。また、Ｘ及びＸ´をｄ個のＸｉ及びＸｉ´分割して計算を行う場合においても、Ｙ´とＣとの整合性判定において影響するのはあくまで総和であるＸ及びＸ´であるため、たとえｄ個のＸｉ´のうちいくつかの順序が入れ替わっていてもそれを検知することはできない。
【００３９】
一方、式(2)と式(3)にｅｉがある場合、式(2)と式(4)を変形すると、それぞれ次式のようになる。
【数５】
2008178005.tif 000006
この場合においてもＣ＝Ｙ´mod Ｎが成立するのは、必ずしも両式のべき乗部分の値が等しい場合に限らない。しかし、べき乗部分が単なる分割データＸｉ、Ｘｉ´の総和ではなく分割データＸｉ、Ｘｉ´ごとにｅｉが積算されているため、たとえべき乗部分の値がわかってもｅｉがわからない限り、Ｃ＝Ｙ´mod Ｎを成立させるデータＸ´を見つけ出すのは難しい。また、ｄ個のＸｉ´のうち順序が入れ替わっているものがあるような場合でも検出しやすい。
そこで、本発明においては全実施形態でＹ´及びｘの計算式にｅｉをべき乗又は乗算することにより攻撃に対する安全性の向上を図っている（第１〜第７実施形態においては、ｅｉは整数）。
【００４０】
そして、第８実施形態は、このｅｉをランダムな値とすることによって、悪意者がｅｉを知ることを困難にすることで、より安全性を高めることができるものである。
なお、更なる安全性向上のためには、検証の都度ｅｉを再計算することが望ましい。
【００４１】
〔第９実施形態〕
第９実施形態は、第８実施形態におけるランダムなｅｉを、べき乗剰余計算により生成するものである。
第９実施形態のデータ検証システムの機能構成は、ｅｉ生成部８１の内部構成を除き、第８実施形態のデータ検証装置８０と同様である。図１２ａは第９実施形態のｅｉ生成部８１の内部構成例である。ｅｉ生成部８１は、乱数生成部８１ａとべき乗剰余計算部８１ｂとを備える。
乱数生成部８１ａは、１以上のランダムな自然数ｅを生成し出力する。ランダムなｅとしては例えば疑似乱数を用いることができる。疑似乱数の生成方法としては、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される計算量理論に基づく疑似乱数生成アルゴリズム等を用いることができる。
【００４２】
べき乗剰余計算部８１ｂは、乱数生成部８１ａから出力された上記ランダムな自然数ｅが入力され、次式によりｅｉを計算し出力する。なお、ｓは２以上の自然数である。
ｅｉ＝ｅi-1 mod s      (9)
このようにべき乗剰余計算によりランダムなｅｉを生成することができる。  また、ｅｉを疑似乱数により生成させたい場合、予め疑似乱数によって発生させた上記eを式(9)に適用することで、ｅｉ算出時に疑似乱数生成アルゴリズムを動作させずにｄ個の疑似乱数ｅｉを発生させることができる。そのため、すべてのｅｉを疑似乱数生成アルゴリズムを用いて算出するよりも演算量を少なくできる。
式(9)において、ｓが大きな数であるほど悪意の攻撃者がｅｉを見つけ出すことが困難になる。例えば、８０ビット程度のセキュリティを確保したい場合、ｓも８０ビット程度以上の数とすることが望ましい。
【００４３】
〔第１０実施形態〕
第１０実施形態は、第８実施形態におけるランダムなｅｉを、逆像演算が困難な関数を用いて生成するものである。
第１０実施形態のデータ検証システムの機能構成は、ｅｉ生成部８１の内部構成を除き、第８実施形態のデータ検証装置８０と同様である。図１２ｂは第１０実施形態のｅｉ生成部８１の内部構成例である。ｅｉ生成部８１は、乱数生成部８１ａとＨ関数計算部８１ｃとを備える。
【００４４】
Ｈ関数計算部８１ｃは、乱数生成部８１ａから出力された上記ランダムな自然数ｅが入力され、次式によりｅｉを計算し出力する。なお、Ｈは逆像演算が困難な関数である。逆像演算が困難な関数としては、例えば一方向性ハッシュ関数等があげられる。また、（ｅ，ｉ）はｅとｉとのビット連結を意味する。
ｅｉ＝Ｈ（ｅ，ｉ）      (10)
このような関数計算により、ランダムなｅｉを生成することができる。また、ｅｉを疑似乱数により生成させたい場合、予め疑似乱数によって発生させた上記eを式(10)に適用することで、ｅｉ算出時に疑似乱数生成アルゴリズムを動作させずにｄ個の疑似乱数ｅｉを発生させることができる。そのため、すべてのｅｉを疑似乱数生成アルゴリズムを用いて算出するよりも演算量を少なくできる。
この実施形態においては、ｅｉから逆像演算でｅを求めることが困難であるため、たとえ一部のｅｉが漏洩した場合でも、攻撃者はｅを見出すことができず、従って、残りのｅｉを見出すことはできない。よって、悪意者の攻撃への安全性を向上できる。
【００４５】
〔第１１実施形態〕
第１１実施形態は、第８実施形態におけるランダムなｅｉを、異なる入力値に対するそれぞれの出力値が衝突困難な関数を用いて生成するものである。
第１１実施形態のデータ検証システムの機能構成は、ｅｉ生成部８１の内部構成を除き、第８実施形態のデータ検証装置８０と同様である。図１２ｂは第１０実施形態のｅｉ生成部８１の内部構成例である。ｅｉ生成部８１は、乱数生成部８１ａとＳ関数計算部８１ｄとを備える。
Ｓ関数計算部８１ｄは、乱数生成部８１ａから出力された上記ランダムな自然数ｅが入力され、次式によりｅｉを計算し出力する。なお、Ｓは異なる入力値に対する出力値が衝突困難な関数、例えば２つの入力値が与えられた場合に出力値はそれぞれ異なるという性質を持つ関数である。衝突困難な関数としては、例えばハッシュ関数等があげられる。また、（ｅ，ｉ）はｅとｉとのビット連結を意味する。
【００４６】
ｅｉ＝Ｓ（ｅ，ｉ）      (11)
このような関数計算により、ランダムなｅｉを生成することができる。また、ｅｉを疑似乱数により生成させたい場合、予め疑似乱数によって発生させた上記eを式(11)に適用することで、ｅｉ算出時に疑似乱数生成アルゴリズムを動作させずにｄ個の疑似乱数ｅｉを発生させることができる。そのため、すべてのｅｉを疑似乱数生成アルゴリズムを用いて算出するよりも演算量を少なくできる。
上記式(7)及び式(8)において、例えばもしｄ個のｅｉのうち複数のｅｉが同じ値であれば、その同じ値の部分に対応するＸｉとＸｉ´との間で並びが入れ替わっていてもそれを検知することができない。そこで、衝突困難な関数でｅｉを生成してｅｉをそれぞれ異なる値とすることでＸｉとＸｉ´との間で並びが入れ替わっているような場合もそれを検知でき、判定精度を向上することができる。
【００４７】
〔第１２実施形態〕
第１２実施形態は、ｅｉを整数でかつ定数とする構成であり、第１〜第７実施形態のそれぞれにおいて適用できる。
ｅｉを定数とすることで、ランダムにする場合より安全性は低下するが、装置を簡略化したい場合や処理をより軽くしたい場合に有効である。
本発明におけるデータ検証システム、その方法、識別子生成装置、データ検証装置は、上記の実施形態に限定されるものではなく、本発明を逸脱しない範囲で適宜変更が可能である。また、上記に説明した処理は記載の順に従った時系列において実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００４８】
また、上記データ検証システム、識別子生成装置、データ検証装置における処理機能をコンピュータによって実現する場合、データ検証システム、識別子生成装置、データ検証装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより上記データ検証システム、識別子生成装置、データ検証装置における処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magnet-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００４９】
また、このプログラムの流通は、例えば、このプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等をすることによって行う。更に、このプログラムをサーバコンピュータの記録装置に格納しておき、ネットワークを介してサーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦自己の記録装置に格納する。そして、処理の実行時、このコンピュータは自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、更に、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータからこのコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって上記の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５０】
また、この形態ではコンピュータ上で所定のプログラムを実行させることにより、データ検証システム、識別子生成装置、データ検証装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００５１】
＜発明の効果の実験による確認＞
本発明について、識別子生成とデータ完全性検証に関し、実験的に効果の確認を行った。以下、実験方法及び結果について説明する。
本発明の内容は、大きく分けて１．識別子生成と２．識別子によるデータ完全性検証の２種類に分けられる。本稿ではそれぞれに最適な実装を試みる。なお、測定環境は図１３、測定パラメータのサイズは図１４のとおりである。
【００５２】
１．識別子生成
識別子の計算の高速化を図った第５実施形態の効果の確認を行った。
識別子の計算にｐ、ｑを使わない場合との比較結果を図１５に示す。
ｐ、ｑを使用することにより約４００倍の高速化が可能になる。これならば、ほぼリアルタイムに近い速度で識別子の生成を行うことが可能である。また、本発明では情報Ｘをｄブロックに分割していることにより、それぞれの識別子Ｙ１，・・・，Ｙｄを全く独立に計算できるためこの部分は並列処理が可能である。
【００５３】
２．データ完全性検証
第１実施形態の検証方法によるデータ完全性検証時間の高速化効果の確認を行った。
標準的なハッシュ関数を用いて行った場合との比較結果を図１６に示す。比較は、データＸのサイズを１Ｇbitから１０Ｇbitまで１Ｇbitごとに変化させて行った。
ＸのサイズをαＧbitと置くと、本発明による検証方式では、処理時間は、1.23＋0.159α（秒）という結果が得られた。ファイルサイズが大きくなれば最初の定数部分は無視できるので、巨大なファイルにおいては6.29Ｇbpsで処理できていることになる。これは、SHA-1の約4.5倍、SHA-256の約11.3倍の処理速度である。
【００５４】
また、ファイルサイズが小さい時において、SHA-1の場合、2.24Ｇbit（286Ｍbyte）のときにほぼ同一の処理時間がかかり、SHA-256の場合、0.74Ｇbit（95Ｍbyte）のときのほぼ同一の処理時間がかかる。このときの処理時間はそれぞれ約1.6秒、約1.3秒である。本発明による検証方式は、検証する情報量が大容量になればなるほど、効果を発揮する。
一般的な映像コンテンツＤＶＤ１枚分の容量で比較した結果を図１７に示す。本発明の検証方式はSHA-1よりも４倍以上の速度で検証できていることがわかる。
【００５５】
更に、本発明の検証方式においては、式(2)の計算と式(3)(4)の計算は完全に並列に計算することが可能である。そこで、これらの部分を並列処理により行った場合についても検証実験を行った。
ＤＶＤ、ＨＤ−ＤＶＤ、Ｂｌｕ−ｒａｙの３種類のディスク容量分の乱数に対し、データの完全性を検証するために要した時間を図１８に示す。
ＡＭＤ６４ｘ２ ２ＧHzにおいて、約12Ｇbps（1.5Ｇbyte/s）のスループットが出ている。これは６bit／cycle以上であり、ＳＨＡ等のハッシュアルゴリズムを圧倒する性能を示している。
【００５６】
これらのことより、例えば巨大なデータの署名を検証する際に、ハッシュに要する時間が支配的になっており、0.1％程度のデータ増量を許容できるならば、識別子に対してハッシュ関数を計算し、署名を付けることで高速な署名検証が可能となるなど、様々な応用が期待できる。
【産業上の利用可能性】
【００５７】
本発明では識別子の生成と整合性の検証に異なるアルゴリズムを用いていることから、映像コンテンツのようにデータ整合性検証にはリアルタイム性が求められるが、タグの生成は多少遅くても問題無い状況において特に有効である。
【図面の簡単な説明】
【００５８】
【図１】本発明による識別子生成装置１０の構成図。
【図２】本発明によるデータ検証装置２０の構成図。
【図３】本発明による第１実施形態の処理手順。
【図４】本発明による一体型装置３０の構成図。
【図５】本発明による第２実施形態の処理手順。
【図６】本発明による一体型装置４０及び外部記憶装置２００の構成図。
【図７】本発明による第３実施形態の処理手順。
【図８】本発明による識別子生成装置５０の構成図。
【図９】本発明による第５実施形態の処理手順。
【図１０】本発明によるデータ検証装置８０の構成図。
【図１１】本発明による第８実施形態の処理手順。
【図１２】本発明によるｅｉ生成部８１の内部構成図。
【図１３】本発明による効果の実験確認の際の測定環境一覧。
【図１４】実験確認の際の測定パラメータサイズ一覧。
【図１５】識別子計算時のｐ，ｑの利用の有無による識別子作成時間の比較。
【図１６】標準的なハッシュ関数と提案方式との検証時間の容量別比較。
【図１７】ＤＶＤ一枚分の容量を検証した場合の検証時間の比較。
【図１８】並列処理実装時の主なディスク規格ごとの検証時間の比較。
【図１】
2008178005.tif 000023
【図２】
2008178005.tif 000024
【図３】
2008178005.tif 000025
【図４】
2008178005.tif 000026
【図５】
2008178005.tif 000027
【図６】
2008178005.tif 000028
【図７】
2008178005.tif 000029
【図８】
2008178005.tif 000030
【図９】
2008178005.tif 000031
【図１０】
2008178005.tif 000032
【図１１】
2008178005.tif 000033
【図１２】
2008178005.tif 000034
【図１３】
2008178005.tif 000035
【図１４】
2008178005.tif 000036
【図１５】
2008178005.tif 000037
【図１６】
2008178005.tif 000038
【図１７】
2008178005.tif 000039
【図１８】
2008178005.tif 000040