(57)【要約】【課題】  電子データの完全性の検証において、検証処理の高速化を図るとともに、検証対象の電子データ全体を一括処理する場合との互換性を維持する。【解決手段】  データ入力部202は、電子データを入力し、電子データをN個（NはN≧2の整数）のセグメントに分割する。ハッシュ値計算部203および検査データ生成部204は、M番目（Mは1≦M≦N-1の整数）のセグメントのデータに所定の演算を行った演算結果を、M+1番目のセグメントのデータの所定の演算を行うための入力とする演算処理をN番目のセグメントまで繰り返し行って、検査データを生成する。検証データ生成部205は、検査データ、および、検査データの生成の途中の演算結果を中間データとして含む、電子データの検証データを生成する。【選択図】  図1
2013138409.tif 000002
【特許請求の範囲】
【請求項１】
電子データを入力する入力手段と、
前記電子データをN個（NはN≧2の整数）のセグメントに分割する分割手段と、
M番目（Mは1≦M≦N-1の整数）のセグメントのデータに所定の演算を行った演算結果を、M+1番目のセグメントのデータの前記所定の演算を行うための入力とする演算処理をN番目のセグメントまで繰り返し行って、検査データを生成する演算手段と、
前記検査データ、および、前記検査データの生成の途中の演算結果を中間データとして含む、前記電子データの検証データを生成する生成手段とを有することを特徴とする情報処理装置。
【請求項２】
さらに、前記検証データに含める中間データの数を設定する設定手段を有することを特徴とする請求項1に記載された情報処理装置。
【請求項３】
前記演算手段は、さらに、各演算処理までに処理した前記電子データのデータサイズを示すデータを生成し、
前記生成手段は、前記中間データが生成されるまでに前記演算処理された前記電子データのデータサイズを示すデータを当該中間データに対応付けて前記検証データに含めることを特徴とする請求項1または請求項2に記載された情報処理装置。
【請求項４】
前記中間データは暗号化されていることを特徴とする請求項1から請求項3の何れか一項に記載された情報処理装置。
【請求項５】
検証対象の電子データ、前記電子データの検証データ、および、前記検証データの生成の途中の演算結果である中間データを入力する入力手段と、
前記検証対象の電子データをN個（NはN≧2の整数）のセグメントに分割し、一つまたは複数のセグメントを含む複数の部分データを生成する分割手段と、
前記複数の部分データから前記検証対象の電子データの検証データおよび中間データを生成する複数の演算手段と、
前記入力手段が入力した検証データおよび中間データ、並びに、前記複数の演算手段が生成した検証データおよび中間データを用いて、前記検証対象の電子データの完全性を検証する検証手段とを有し、
前記複数の演算手段はそれぞれ、前記複数の部分データの一つを入力し、前記入力した部分データが含むM番目（Mは1≦M≦N）のセグメントに所定の演算を行うために、M-1番目のセグメントのデータに前記所定の演算を行った演算結果または所定の初期値を入力する演算処理を、前記入力した部分データが含むX番目（XはM≦X≦Nの整数）のセグメントまで繰り返し、
N番目のセグメントを含まない部分データを入力した前記複数の演算手段の一つは前記入力した部分データに対応する中間データを生成し、前記N番目のセグメントを含む部分データを入力した前記複数の演算手段の一つは検証データを生成することを特徴とする情報処理装置。
【請求項６】
前記分割手段は、前記中間データの数に相当する数の部分データを生成することを特徴とする請求項5に記載された情報処理装置。
【請求項７】
前記複数の演算手段は、前記複数の部分データを並列処理することを特徴とする請求項5または請求項6に記載された情報処理装置。
【請求項８】
入力手段が、電子データを入力し、
分割手段が、前記電子データをN個（NはN≧2の整数）のセグメントに分割し、
演算手段が、M番目（Mは1≦M≦N-1の整数）のセグメントのデータに所定の演算を行った演算結果を、M+1番目のセグメントのデータの前記所定の演算を行うための入力とする演算処理をN番目のセグメントまで繰り返し行って、検査データを生成し、
生成手段が、前記検査データ、および、前記検査データの生成の途中の演算結果を中間データとして含む、前記電子データの検証データを生成することを特徴とする情報処理方法。
【請求項９】
さらに、設定手段が、前記検証データに含める中間データの数を設定することを特徴とする請求項8に記載された情報処理方法。
【請求項１０】
前記演算手段は、さらに、各演算処理までに処理した前記電子データのデータサイズを示すデータを生成し、
前記生成手段は、前記中間データが生成されるまでに前記演算処理された前記電子データのデータサイズを示すデータを当該中間データに対応付けて前記検証データに含めることを特徴とする請求項8または請求項9に記載された情報処理方法。
【請求項１１】
前記中間データは暗号化されていることを特徴とする請求項8から請求項10の何れか一項に記載された情報処理方法。
【請求項１２】
入力手段が、検証対象の電子データ、前記電子データの検証データ、および、前記検証データの生成の途中の演算結果である中間データを入力し、
分割手段が、前記検証対象の電子データをN個（NはN≧2の整数）のセグメントに分割し、一つまたは複数のセグメントを含む複数の部分データを生成し、
複数の演算手段が、前記複数の部分データから前記検証対象の電子データの検証データおよび中間データを生成し、
検証手段が、前記入力手段が入力した検証データおよび中間データ、並びに、前記複数の演算手段が生成した検証データおよび中間データを用いて、前記検証対象の電子データの完全性を検証し、
前記複数の演算手段はそれぞれ、前記複数の部分データの一つを入力し、前記入力した部分データが含むM番目（Mは1≦M≦N）のセグメントに所定の演算を行うために、M-1番目のセグメントのデータに前記所定の演算を行った演算結果または所定の初期値を入力する演算処理を、前記入力した部分データが含むX番目（XはM≦X≦Nの整数）のセグメントまで繰り返し、
N番目のセグメントを含まない部分データを入力した前記複数の演算手段の一つは前記入力した部分データに対応する中間データを生成し、前記N番目のセグメントを含む部分データを入力した前記複数の演算手段の一つは検証データを生成することを特徴とする情報処理方法。
【請求項１３】
前記分割手段は、前記中間データの数に相当する数の部分データを生成することを特徴とする請求項12に記載された情報処理方法。
【請求項１４】
前記複数の演算手段は、前記複数の部分データを並列処理することを特徴とする請求項12または請求項13に記載された情報処理方法。
【請求項１５】
コンピュータを請求項1から請求項7の何れか一項に記載された情報処理装置の各手段として機能させるためのプログラム。
【請求項１６】
請求項15に記載されたプログラムが記録されたコンピュータが読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子データの完全性を検証する情報処理に関する。
【背景技術】
【０００２】
データの改竄などを防ぎ、データの完全性を検証する技術として、ディジタル署名やメッセージ認証コード(MAC: message authentication code)が知られている。
【０００３】
ディジタル署名は、公開鍵暗号方式に基づいて完全性を検証する署名データを生成する技術であり「電子署名」とも呼ばれる。署名データの生成は、ハッシュ関数により署名対象のデータのハッシュ値（メッセージダイジェストとも呼ばれる）を生成し、このハッシュ値を自身の秘密鍵で暗号化して署名データを生成する。署名検証は、署名データを公開鍵で復号し、復号結果と署名対象のデータから生成したハッシュ値を比較し、それらが同一であば正当な署名と判断する。代表的なディジタル署名アルゴリズムにはRSA (Rivest Shamir Adleman)やDSA (digital signature algorithm)がある。
【０００４】
ハッシュ関数は、任意のサイズのデータから一定のサイズのデータ（ハッシュ値）を生成する一方向性関数である。とくに、ハッシュ値から、当該ハッシュ値が得られる他のデータを求めることが困難であること、同じハッシュ値が得られる異なる二つのデータを求めることが困難であるなどの特徴がある。代表的なハッシュ関数にはMD5 (message digest algorithm 5)、SHA1 (secure hash algorithm 1)、SHA2 (secure hash algorithm 2)などがある。
【０００５】
メッセージ認証コードは、共通鍵を用いて完全性を検証するための署名データ（MAC値と呼ぶこともある）である。ハッシュ関数を利用するHMAC(hash-basedMAC)やブロック暗号を利用するCMAC(cipher-basedMAC)などがある。
【０００６】
文献1は、上記のディジタル署名技術を適応してデータの完全性を検証する技術を開示し、記録媒体に記録されたコンテンツ（データ）の完全性を検証する場合に昨今のデータ量の増大に伴い検証に時間がかかる問題を解決する。文献1の技術は、コンテンツを細分化し、細分化したデータごとに署名データの生成と検証を行う。そして、署名検証において、すべての細分化データの検証に成功するとコンテンツの完全性の検証に成功したと判断する。つまり、細分化したデータを並列処理することで検証を高速化する。
【０００７】
また、情報処理環境においては、CPUのマルチコア化、画像処理アクセラレータであるGPU (graphics processing unit)を汎用計算に利用するなどにより、並列処理環境が一般的になってきた。
【０００８】
ディジタル署名はハッシュ関数を含む。ハッシュ関数は、前段の処理結果を後段に入力することを繰り返す、再帰的でシーケンシャルな処理であり、並列処理による高速化は困難である。なお、文献1の方式は、データを細分化してそれぞれを個別に検証するため、細分化されたデータごとに独立に並列処理して高速化することができる。言い替えれば、細分化されたデータごとの検証であり、署名データは細分化されたデータごとの署名データの集合である。つまり、一般に用いられるデータ全体を一括処理する方式とは異なる署名データになる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特許第4576936号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本発明は、電子データの完全性の検証において、検証処理の高速化を図るとともに、検証対象の電子データ全体を一括処理する場合との互換性を維持することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、前記の目的を達成する一手段として、以下の構成を備える。
【００１２】
本発明にかかる情報処理装置は、電子データを入力する入力手段と、前記電子データをN個（NはN≧2の整数）のセグメントに分割する分割手段と、M番目（Mは1≦M≦N-1の整数）のセグメントのデータに所定の演算を行った演算結果を、M+1番目のセグメントのデータの前記所定の演算を行うための入力とする演算処理をN番目のセグメントまで繰り返し行って、検査データを生成する演算手段と、前記検査データ、および、前記検査データの生成の途中の演算結果を中間データとして含む、前記電子データの検証データを生成する生成手段とを有することを特徴とする。
【発明の効果】
【００１３】
本発明によれば、電子データの完全性の検証において、検証処理の高速化を図るとともに、検証対象の電子データ全体を一括処理する場合との互換性を維持することができる。
【図面の簡単な説明】
【００１４】
【図１】実施例の情報処理装置における検証データを生成する機能構成例を説明するブロック図。
【図２】検証データの構成例を示す図。
【図３】実施例の情報処理装置における検証対象データを検証する機能構成例を説明するブロック図。
【図４】ハッシュ関数の概要とともにハッシュ値計算部における中間データの生成方法を説明する図。
【図５】中間データ計算部の処理を説明するフローチャート。
【図６】検証データの例を示す図。
【図７】CMACの概要を説明する図。
【図８】実施例3の情報処理装置における検証データを生成する機能構成例を説明するブロック図。
【図９】実施例3の情報処理装置における検証対象データを検証する機能構成例を説明するブロック図。
【図１０】検証対象データの検証処理を説明するフローチャート。
【図１１】検証処理において三並列処理が可能な場合の検証データの生成方法を説明する図。
【図１２】検査対象データの検証処理を三並列処理によって行う例を説明する図。
【発明を実施するための形態】
【００１５】
以下、本発明にかかる実施例の情報処理を図面を参照して詳細に説明する。
【実施例１】
【００１６】
［装置の構成］
実施例の情報処理装置は、CPUおよびROM、RAMなどのメモリを有する、例えばパーソナルコンピュータのようなコンピュータ装置に、後述する機能および処理を実現するプログラムを供給することにより実現される。なお、ワークメモリとして機能するRAMに格納し切れないデータを一時的に格納したり、各種プログラムやデータを格納するために、ハードディスクドライブ(HDD)やソリッドステートドライブ(SSD)を用いることができる。
【００１７】
また、実施例において、CPUは並列演算が可能な構成を前提とし、CPUは複数のチップで構成されてもよいし、単一のCPUチップが複数のCPUコアを有する構成でもよい。さらに、GPUなどを用いて並列演算を行ってもよく、その場合、GPUはCPUの一部と見做される。
【００１８】
また、情報処理装置は、各種インタフェイスを有する。例えば、ネットワークに接続するネットワークインタフェイス、キーボードやマウスなどの入力デバイスに接続するUSBなどのシリアルバスインタフェイス、ユーザインタフェイスや演算結果を表示するモニタに接続するビデオインタフェイスなどである。
【００１９】
なお、実施例の情報処理装置は、コンピュータ装置に限らず、情報家電や複合機(MFP: multi functional peripheral)などの様々な情報機器を含む。あるいは、後述する機能や処理を実現する専用チップやコンピュータ周辺機器でもよい。
【００２０】
［機能構成］
●検証データの生成
図1のブロック図により実施例の情報処理装置における検証データを生成する機能構成例を説明する。
【００２１】
データ入力部202は、完全性の検証対象である電子データ（以下、検証対象データ）を入力する。なお、検証対象データは、情報処理装置に保持されたデータ、例えばUSBメモリのような不揮発性メモリデバイスから読み込んだデータ、あるいは、ネットワークなどを介して外部の機器から入力したデータなどである。
【００２２】
ハッシュ値計算部203は、一方向性関数を用いて、データ入力部202が入力した検証対象データを表す値（ハッシュ値）を計算する。具体的には、検証対象データをN個（NはN≧2の整数）のセグメントに分割し、M番目（Mは1≦M≦N-1の整数）のセグメントの演算結果を、M+1番目のセグメント演算するための入力とする演算をN番目の最終セグメントまで繰り返し行う。なお、例えばSHA1の場合、セグメントサイズは512ビットであり、ハッシュ値は160ビットである。
【００２３】
ハッシュ値計算部203は、算出結果のハッシュ値を出力する。さらに、詳細は後述するが、計算の途中のハッシュ中間値、および、当該ハッシュ中間値を生成するために処理した検証対象データの一部（つまりセグメント）の、検証対象データ上の位置を特定するための情報のペアを出力する。なお、以下では、計算の途中のハッシュ中間値を「中間データ」、セグメントの位置を特定するための情報を「オフセット」と呼ぶ。また、ハッシュ関数にはMD5、SHA1、SHA2など、一般的なハッシュアルゴリズムを用いればよく、特定のハッシュアルゴリズムに限定されることはない。
【００２４】
検査データ生成部204は、鍵を使用して、ハッシュ値計算部203が出力したハッシュ値から検査データを生成する。検査データがディジタル署名データ（以下、単に署名データ）の場合、署名データの生成はハッシュ処理と狭義の署名生成処理に分けられ、検査データ生成部204の処理は後者（狭義の署名生成処理）に対応する。つまり、ハッシュ値計算部203の処理と検査データ生成部204の処理により、一般的な署名データの生成と等価の処理が得られる。
【００２５】
例えばDSA署名の場合、検査データ生成部204の処理は鍵を用いたべき乗剰余演算に相当する。また、RSA署名の場合、検査データ生成部204の処理はエンコーディングとべき乗剰余演算に相当する。なお、署名データの生成には鍵、とくに秘密鍵が必要になるが、秘密鍵は、情報処理装置に保持する、例えばUSBメモリのような不揮発性メモリデバイスから読み込む、あるいは、ネットワークなどを介して外部の機器から入力するなどが可能である。
【００２６】
検証データ生成部205は、ハッシュ値計算部203から中間データとオフセットのペアを、検査データ生成部204から検査データをそれぞれ入力し、それら入力したデータから検証データを作成する。図2により検証データの構成例を示す。検証データ101は、検査データ102に加えて、オフセット103と当該オフセットに対応するセグメントから生成された中間データ104を対応付けた複数のペアから構成される。
【００２７】
データ出力部206は、検証データ生成部205が生成した検証データを出力する。検証データの出力先は、例えばUSBメモリのような不揮発性メモリデバイスやネットワークを介した外部の機器である。
【００２８】
●検証対象データの検証
図3のブロック図により実施例の情報処理装置における検証対象データを検証する機能構成例を説明する。
【００２９】
データ入力部208は、検証対象データと、当該検証対象データの検証データを入力する。なお、検証データは、図2に示すように、検査データに加えて、オフセットと当該オフセットに対応するセグメントから生成された中間データの、複数のペアから構成される。また、検証対象データおよび検証データは、情報処理装置に保持されたデータ、例えばUSBメモリのような不揮発性メモリデバイスから読み込んだデータ、あるいは、ネットワークなどを介して外部の機器から入力したデータなどである。
【００３０】
分割部209は、データ入力部208が入力した検証データの生成に用いられたハッシュ関数および検証データに含まれるオフセットに基づき、データ入力部208が入力した検証対象データを分割したセグメントをハッシュ値計算部210に出力する。また、検証データに含まれる中間データを比較部213に出力し、検証データに含まれる検査データを検査データ検証部212に出力する。
【００３１】
ハッシュ値計算部210は、入力されるセグメントのハッシュ値を計算する。つまり、検証対象データから分割された第一のセグメントの演算結果を、第一のセグメントに続く第二のセグメントを演算するための入力とする演算を最終セグメントまで繰り返して行うことで、中間データと検証対象データのハッシュ値を生成する。
【００３２】
その際、ハッシュ値計算部210は、入力されるセグメントが、検証対象データの最初のデータだけを含むセグメント（以下、先頭セグメント）である場合は、規定のハッシュ初期値を用いてハッシュ値を演算する。
【００３３】
また、ハッシュ値計算部210は、入力されるセグメントが、最初のデータに続くデータを含む（言い換えれば、最初のデータは含まない）セグメントである場合は、当該セグメントの一つ前のセグメントの演算結果を用いてハッシュ中間値を演算する。言い換えれば、M番目（1＜M＜N）のセグメント（以下、途中セグメント）のハッシュ中間値は、M-1番目のセグメントの演算結果（ハッシュ中間値）を用いて演算される。
【００３４】
また、ハッシュ値計算部210は、入力されるセグメントが、検証対象データの最後のデータだけを含む最終セグメントである場合、算出されるデータは検証対象データのハッシュ値である。さらに、ハッシュ値計算部210は、オフセットに対応するセグメントの演算結果を中間データとして出力する。
【００３５】
ハッシュ値計算部210は、図3に示すように、並列処理部として構成される。つまり、分割部209が出力する、オフセットに対応するセグメントまたは複数のセグメントを並列処理部を構成する中間データ計算部2101〜210Nの何れかへ入力して中間データを生成する。このように、中間データの生成を並列に処理することが可能である。
【００３６】
分配部211は、中間データ計算部210が出力する中間データまたはハッシュ値の出力先を制御する。最終セグメントから生成されるハッシュ値は検査データ検証部212へ出力し、それ以外の中間データは比較部213へ出力する。なお、分配部211は、中間データ計算部210が出力する二つ以上の出力値の結合や演算は行わずに、単一の出力値として分配する。従って、中間データ計算部210の処理の完了を待つことなく、中間データ計算部210の出力ごとに分配を行うことができる。
【００３７】
検査データ検証部212は、鍵と、分配部211から入力される検証対象データのハッシュ値を用いて、分割部209から入力される検査データの検証処理を行う。つまり、検査データが署名データの場合、ハッシュ値計算部210で得られる検証対象データのハッシュ値と、検査データ検証部212の処理により、一般的な署名データの検証処理と等価の処理を行う。
【００３８】
例えばDSA署名の場合、検査データ検証部212の処理は鍵を用いたべき乗剰余演算に相当する。また、RSA署名の場合、検査データ検証部212の処理はべき乗剰余演算とデコーティングに相当する。なお、ハッシュ値計算部210が並列処理部として構成されている場合も、検査データ検証部212は、分配部211からハッシュ値を入力した時点で検証処理を行うことができ、ハッシュ値計算部210の処理の完了を待つ必要はない。
【００３９】
比較部213は、分割部209から入力される検証データに含まれる中間データ、ハッシュ値計算部210から入力される中間データ、および、検査データ検証部212から入力される検査データの検証結果から、検証対象データの完全性の検証結果を出力する。つまり、検証データに含まれる中間データと、ハッシュ値計算部210が計算した中間データの比較結果がすべて一致を示し、かつ、検査データの検証結果が成功を示す場合、検証対象データの完全性の検証に成功したと判断する。また、そうでない場合は、検証対象データの完全性の検証に失敗したと判断する。なお、比較部213の処理は、すべての中間データと検査データを用いる処理であり、ハッシュ値計算部210の処理の完了を待つ必要がある。
【００４０】
［中間データ］
●ハッシュ値計算部（検証データ生成側）
図4によりハッシュ関数の概要とともに検証データ生成側のハッシュ値計算部203における中間データの生成方法を説明する。
【００４１】
図4において、データ401は検証対象データである。データ401は、分割処理（div()）402によって、所定のサイズのセグメントに分割される。代表的なハッシュ関数であるSHA1を用いる場合のセグメントサイズは512ビットである。なお、図には示さないが、最終セグメントは、セグメントサイズになるようにパディング処理を行う。
【００４２】
まず、先頭セグメントのデータdata0と所定のハッシュ初期値H0をハッシュ処理部h()へ入力して値H1を得る。次に、次のセグメント（途中セグメント）のデータdata1と値H1をハッシュ処理部h()へ入力して値H2を得る。この処理を最終セグメントのデータdataNまで繰り返し、最後に得られるハッシュ値Hnがデータ401のハッシュ値Hである。
【００４３】
中間データは、あるセグメントのデータdataMに続くセグメントのデータdataM+1の演算を行うハッシュ処理部h()へ入力されるデータdataMのハッシュ中間値HMである。つまり、先頭セグメントのデータdata0のハッシュ中間値H1や途中セグメントのデータdata1のハッシュ中間値H2などが中間データとして出力される。ここで、セグメントとは、所定の演算処理（図4の例ではハッシュ処理部h()）に入力するデータ単位である。図4は所定の演算処理ごとに中間データを出力する例を示し、セグメントごとに中間データが出力されるが、後述するように、セグメントごとに中間データを出力する必要はない。
【００４４】
また、中間データに対応するオフセットは、当該中間データの生成までに処理した検証対象データのデータサイズである。SHA1の場合、セグメントサイズは512ビットになり、中間データH1に対応するオフセットは512ビットを表し、二番目の中間データH2に対応するオフセットは1024ビットを表す。つまり、オフセットは、ハッシュ関数に依存するセグメントサイズの整数倍になる。
【００４５】
●中間データ計算部
図5のフローチャートにより中間データ計算部2101〜210Nそれぞれの処理を説明する。
【００４６】
中間データ計算部は、分割部209からセグメントまたは複数のセグメントを入力し(S501)、入力されたセグメントの種類を判定する(S502)。なお、セグメントの種類の判定はオフセットを用いて行われる。
【００４７】
入力されたセグメントが先頭セグメントであると判定した場合、中間データ計算部は、所定のハッシュ初期値を用いて先頭セグメントのハッシュ中間値を演算する(S503)。また、入力されたセグメントが途中セグメントと判定した場合、中間データ計算部は、当該セグメントの一つ前のセグメントのハッシュ中間値を用いて当該セグメントのハッシュ中間値を演算する(S504)。ステップS503とS504の処理は、一般的なハッシュ関数からパディング処理を除いた処理と同様である。そして、入力された全セグメントの演算が終了したか否かを判定し(S505)、演算が未了のセグメントがあれば処理をステップS502に戻す。また、入力された全セグメントの演算が終了した場合は、最後に演算したセグメントのハッシュ中間値を中間データとして出力し(S506)、処理を終了する。
【００４８】
また、入力されたセグメントが最終セグメントと判定した場合、中間データ計算部は、最終セグメントの一つ前のセグメントのハッシュ中間値を用いて最終セグメントのハッシュ値を演算する(S507)。なお、必要であればパディング処理も実施する。そして、最終セグメントのハッシュ値を検証対象データのハッシュ値として出力し(S508)、処理を終了する。
【００４９】
［検証対象データの分割方法］
分割部209は、検証データの生成に用いられたハッシュ関数および検証データに含まれるオフセットに基づき、検証対象データを分割する。最も単純な分割方法は、10個の中間データを含む検証データの場合、それら中間データに対応するオフセットに基づき、検証対象データを10分割する。
【００５０】
なお、オフセットに合わせて分割される個々のデータを「部分データ」と呼ぶことにする。部分データは、検証データの生成に用いられたハッシュ関数に応じて検証対象データから分割される一つまたは複数のセグメントを含む。この単純な分割方法は、中間データの数が中間データ計算部2101〜210Nの数（並列処理部の数N）以下の場合に望ましい。もし、中間データの数がNを超える場合は、未処理の部分データを、処理を終了した中間データ計算部2101〜210Nの何れかへ逐次入力して、すべての部分データを処理する。
【００５１】
別の分割方法として、検証処理を行う情報処理装置の処理の並列度を考慮して、一部の中間データだけを利用する方法もある。
【００５２】
図6により検証データの例を示す。この例は、offset 1からoffset 5により五つの中間データと一つの検査データ（検証対象データのハッシュ値）を有する。図6に示す検証データを二並列の中間データ計算部2101と2102を用いて処理する場合、検証対象データを二分割するオフセットoffset 3に対応する中間データと検査データを利用して、二つの部分データにより検証処理を行うことが可能である。
【００５３】
同様に、図6に示す検証データを三並列の中間データ計算部2101〜2103を用いて処理することもできる。この場合、検証対象データを三分割するオフセットoffset 2とoffset 4に対応する中間データと検査データを利用して、三つの部分データにより検証処理を行うことが可能である。
【００５４】
検証対象データの分割数を減らすと、検証対象データを単純に分割する場合に比べ、比較部213が比較する中間データの数が減り、比較部213の処理が軽減される。例えば、図6の例において、オフセットoffset 3だけによる分割を行った場合、比較部213は、オフセットoffset 3に対応する中間データの比較を一度実施すればよい。同様に、オフセットoffset 2とoffset 4による分割を行った場合、比較部213は、オフセットoffset 2とoffset 4それぞれに対応する中間データの二度の比較を実施すればよい。
【００５５】
なお、情報処理装置の処理の並列度は、例えば、データ入力部208から入力してもよいし、別途、図示しない並列度取得部を設け、並列度取得部により取得してもよい。なお、最も典型的な処理の並列度はCPUチップが有するCPUコアの数である。
【００５６】
このように、ディジタル署名をベースとし、オフセットと中間データを含む検証データを利用して、検証対象データの完全性を検証する場合に、検証処理の並列処理を可能にし、高速な検証処理を実現することができる。検証データは、図2に示すように、検査データとして一般的な署名データを含むことが可能であり、署名データだけを利用する一般的な検証データによる検証も可能である。
【００５７】
つまり、電子データの完全性の検証において、検証処理を並列化して高速化を図るとともに、検証対象の電子データ全体を一括処理する場合との互換性を維持することができる。
【００５８】
［変形例］
上記では、検証データがオフセットと中間データのペアを含む例を説明した。しかし、中間データの数からオフセットを算出することが可能である。つまり、検証データの生成側と、検証側の双方においてデータを等分すると決めておくと、中間データの数からオフセットを決定することができ、検証データにオフセットを含める必要がなくなる。その結果、ハッシュ値計算部203におけるオフセットの出力が不要になり、データ入力部208におけるオフセットの取得が不要になる。ただし、分割部209における検証対象データの分割を、検証データの生成に用いられたハッシュ関数および中間データの数に基づき制御する必要がある。
【００５９】
また、図4には、すべてのセグメントに対応する中間データを出力する例を示した。しかし、常にすべてのセグメントに対応する中間データを出力する必要はない。中間データを多く出力すれば検証データのデータサイズが大きくなる。例えば、想定される検証処理における処理の並列度に応じて出力する中間データの数を決定することができる。
【００６０】
例えば、二並列処理が可能であれば検証処理において検証対象データを二分割させるために中間データを一つ出力すればよく、三並列処理が可能であれば検証処理において検証対象データを三分割させるために中間データを二つ出力すればよい。つまり、N並列処理が想定される場合、N-1個の中間データを出力すればよい。
【００６１】
想定される処理の並列度が複数ある場合、それらの最小公倍数から出力する中間データの数を決定すればよい。また、処理の並列度が一意ではない場合や不明な場合は、予め想定される最大の並列度から出力する中間データの数を決定すればよい。この場合、データ入力部202は想定された処理の並列度を入力し、ハッシュ値計算部203は、入力された処理の並列度に基づき出力する中間データの数を制御する。
【００６２】
また、検証処理を行う情報処理装置と、検証データを生成する情報処理装置が同じ場合、検証データの生成側に図示しない並列度取得部を設けて処理の並列度を取得し、それを利用してハッシュ値計算部203が出力する中間データの数を決定してもよい。
【００６３】
処理の並列度が決まる、言い替えれば、出力する中間データの数が決まると、図4に示すように、ハッシュ処理部h()の処理ごとに、ハッシュ値計算部203から検証データ生成部205へオフセットと中間データが出力される。検証データ生成部205は、すべての中間データを一時的に保持し、ハッシュ値の計算が完了すると、保持する中間データの数と出力する中間データの数から、実際に出力する中間データを決定する。
【００６４】
図11により検証処理において三並列処理が可能な場合の検証データの生成方法を説明する。検証対象データ1101は使用するハッシュ関数のセグメントサイズに基づき複数のセグメントに分割される。ここでは、ハッシュ関数がSHA1で、検証対象データが3072ビットの場合について、説明する。SHA1はセグメントサイズが512ビットであるので、検証対象データを512で割り、結果として、検証対象データ1101は六つのセグメントに分割される。なお、検証対象データは、パディングデータを含むとする。
【００６５】
そして、各セグメントごとにハッシュ中間値が演算されて、検査データが得られるまでに五つの中間データが生成される。検証データ生成部205は、それら五つの中間データを一時的に保持し、三並列処理に対応して中間データ2と中間データ4を含む検証データ101を生成する。
【００６６】
例えば、合計L個の中間データを一時的に保持し、N並列分、つまりN-1個の中間データを出力する場合、まず出力間隔SをS=ceiling(L/N)として求める。なお、ceiling(x)は天井関数と呼ばれ、実数xに対して、x以上の最小の整数を返す関数である。次に、オフセットの小さい順に中間データをソートし、出力間隔Sで抽出した中間データを合計N-1個出力する。例えば、七個の中間データを保持し(L=7)、三並列(N=3)の場合、S=celling(7/3)=3であるから三番目と六番目の中間データから検証データを生成する。
【００６７】
ハッシュ関数SHA1の例の場合、セグメントのサイズが512ビットであるため検証対象データ1101を512ビットごとに分割する。しかし、検証対象データ1101が大きいと分割数が膨大になる。通常のハッシュ演算部は、演算部内部でセグメントに分割する機能を有する。このため、検証データ1101をセグメントサイズの整数倍に分割して、ハッシュ演算部でセグメントごとに分割するという二段階の分割も可能である。つまり、図11の二つのセグメントデータをひと固まりとみなし三分割し、これらに対応する演算部をハッシュ演算部とみなして、ハッシュ演算部内部でセグメントに分割することも可能である。
【００６８】
言い換えれば、検証対象データ1101をN個（NはN≧2の整数）のセグメントに分割し、一つまたは複数のセグメントを含む複数の部分データを生成する。複数の演算部はそれぞれ、複数の部分データの一つを入力する。各演算部は、入力した部分データが含むM番目（Mは1≦M≦N）のセグメントに所定の演算を行う。その際、各演算部は、M-1番目のセグメントのデータに所定の演算を行った演算結果または所定の初期値を入力する演算処理を、入力した部分データが含むX番目（XはM≦X≦Nの整数）のセグメントまで繰り返す。そして、N番目のセグメントを含まない部分データを入力した演算部は、入力した部分データに対応する中間データを生成する。また、N番目のセグメントを含む部分データを入力した演算部は、検証対象データ1101の検証データを生成する。
【００６９】
図12により検査対象データの検証処理を三並列処理によって行う例を説明する。検証対象データ1201は、検証データ101の生成に用いられたハッシュ関数のセグメントサイズに基づき例えば六つのセグメントに分割され、さらに、検証データ101が含む中間データの数に基づき三つの部分データに分割される。各部分データは、中間データ計算部2101〜2103の何れかに入力されて、中間データA、Bおよび検査データが生成される。そして、比較部213は中間データAと中間データ2の比較および中間データBと中間データ4の比較を行い、検査データ検証部212は検査データによる検証を行う。
【００７０】
検証データ1201が大きくなると分割数が膨大になる。通常のハッシュ演算部は演算部内部でセグメントに分割する機能を有するため、生成処理同様、検証処理もセグメントの整数倍に分割し、ハッシュ演算部でセグメントごとに分割するという二段階の分割も可能である。
【００７１】
上記では、検証処理を行う計算機環境がホモジニアスな並列処理環境を想定した場合の等分割の方法を説明した。しかし、ヘテロジニアスな並列処理環境を想定して、その処理能力比率でデータを分割することも可能である。例えば、1：xの処理能力を有する二並列の計算機環境を想定すると、出力間隔S=ceiling{L/(1+x)}を求める。次に、オフセットの小さい順に中間データをソートし、i×S番目（iは自然数）の中間データから検証データを生成する。
【００７２】
さらに、出力する中間データの決定方法を検証データの生成側と、検証側で共有している場合は、検証対象データのサイズと中間データの数からオフセットを決定することも可能である。分割部209は、入力された検証対象データのデータサイズを求め、データサイズをハッシュ関数に依存するセグメントサイズで割ってLを求め、検証データに含まれる中間データの数からNを求め、出力間隔S=ceiling(L/N)を求める。さらに、出力間隔Sにハッシュ関数に依存するセグメントサイズを掛けてオフセットを求める。
【００７３】
このように、中間データの数を適応的に設定することができる。
【実施例２】
【００７４】
以下、本発明にかかる実施例2の情報処理を説明する。なお、実施例2において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００７５】
電子データの完全性の検証のベースに、実施例1ではディジタル署名を利用する例を説明したが、実施例2ではメッセージ認証コードのHMACを電子データの完全性の検証のベースに利用する例を説明する。なお、ディジタル署名もHMACもハッシュ関数を利用する点では同じであり、処理は基本的に実施例1と同様であるが、中間データが若干異なる。以下では中間データの差異について説明する。
【００７６】
［検査データの生成］
HMACにおける検査データ（HMAC値）の生成は次式で表すことができる。
hmac(data) =h[(key XOR opad)||h{(key XOR ipad)|| data}]      …(1)
ここで、h()はハッシュ関数、
||は連結、
XORは排他的論理和、
ipadとopadは所定の定数、
keyは秘密鍵、
dataは検証対象データ。
【００７７】
実施例1では、検証対象データのハッシュ値を計算する過程のデータを中間データとした。一方で、実施例2では、式(1)に示す二つあるハッシュ関数のうち、内側のハッシュ関数h{(key XOR ipad)||data}のハッシュ値を計算する過程のデータを中間データとする。なお、中間データを出力するハッシュ関数の対象が異なるだけで、検証データの生成手順は実施例1と同様である。
【００７８】
［機能構成］
実施例2において、検証データを生成する機能構成は図1に示す構成と同様、検証対象データの完全性を検証する機能構成は図3に示す構成と同様である。以下では、異なる処理ついて説明する。
【００７９】
●検査データ生成機能
検証データ生成側のハッシュ値計算部203は、式(1)に示すように、検証対象データ「data」に鍵「key」と所定の定数「ipad」を結合してハッシュ関数に入力する。中間データの生成方法は、実施例1と同様である。なお、実施例1においては検査データ生成部204だけが秘密鍵を利用するが、実施例2においてはハッシュ値計算部203も秘密鍵を利用する。実施例1と同様に、秘密鍵は、情報処理装置に保持する、例えばUSBメモリのような不揮発性メモリデバイスから読み込む、あるいは、ネットワークなどを介して外部の機器から入力するなどが可能である。
【００８０】
また、検査データ生成部204は、ハッシュ値計算部203からハッシュ値を入力してHMAC値を生成する。実施例1における検査データ生成部204は例えば狭義の署名データ生成処理を行うが、実施例2の検査データ生成部204は外側のハッシュ関数h[(key XOR opad)||ハッシュ値]のハッシュ値HMACを計算する。
【００８１】
●検証対象データの検証機能
検証側のハッシュ値計算部210は、先頭セグメントについては、所定の定数「ipad」および鍵「key」を式(1)に示す方法で結合し、既定の初期値を用いて中間データを計算する。また、途中セグメントの場合は、当該セグメントの直前のセグメントに対応する中間データをハッシュ初期値として中間データを計算する。なお、最終セグメントの場合、算出されるデータは中間データではなく検証対象データのハッシュ値である。
【００８２】
検査データ検証部212は、分配部211から入力されるハッシュ値を用いてHMAC値を生成する。実施例1における検査データ検証部212は例えば狭義の署名検証処理を行うが、実施例2の検査データ検証部212は式(1)に示す外側のハッシュ関数h[(key XOR opad)||ハッシュ値]のハッシュ値HMACを計算する。なお、HMACは対称処理であるため、検査データ生成部204と同様の処理になる。
【００８３】
［中間データ］
検証データ生成側のハッシュ値計算部203における中間データの生成方法が実施例1と異なる点は、中間データを計算するための入力が、検証対象データに所定の定数「ipad」および鍵「key」を結合したデータになる点である。さらに、検査データ生成部204における検査データの生成が例えば署名データからHMACに変更される点である。その他、中間データの生成数を含めて実施例1と同様である。
【００８４】
中間データの検証方法は、次の点で実施例1と異なる。一つは、検証側のハッシュ値計算部210が実行する中間データとハッシュ値の算出方法が異なる点である。つまり、ステップS502において、先頭セグメントであると判定した場合、所定の定数「ipad」および鍵「key」を結合し、既定の初期ハッシュ値を用いて中間データを計算する(S503)。さらに、検査データ検証部212が検証するデータが例えば署名データからHMAC値に変わる点である。その他、中間データの生成数を含めて実施例1と同様である。
【００８５】
ここで、中間データの保持方法を説明する。実施例1では、中間データを検証対象データだけから生成するため、中間データを含む検証データを検証対象データと同様に扱うことができる。一方、実施例2においては、中間データの生成に秘密鍵を用いるため、中間データは秘密鍵に関する情報を含むと見做すことが妥当である。従って、実施例2においては、中間データを、鍵と同様に、機密性を維持して管理する必要がある。
【００８６】
このように、HMACをベースとした、オフセットと中間データのペアを含む検証データを利用する電子データの完全性の検証においても、検証処理を並列化して高速化を図ることができる。また、図2に示す検証データには、署名データの代わりに検査データとしてHMAC値を含めることで、HMAC値を利用する一般的なHAMCによる検証を行うことも可能である。従って、検証対象の電子データ全体を一括処理する場合との互換性を維持することができる。
【００８７】
なお、実施例2においても、実施例1と同様に、検証データからオフセットを省略することができる。その方法は、実施例1の変形例で説明した方法と同様であり、詳細説明を省略する。
【実施例３】
【００８８】
以下、本発明にかかる実施例3の情報処理を説明する。なお、実施例3において、実施例1、2と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００８９】
実施例3では、電子データの完全性の検証のベースにメッセージ認証コードのCMACを利用する例を説明する。なお、MACの利用であり、基本は実施例2と同様である。以下では、中間データが若干異なる点について説明する。なお、CMACに適応可能な暗号アルゴリズムはブロック暗号であり、代表的なアルゴリズムの一つにAESがあるが、AESに限定されるわけではない。
【００９０】
［CMACの概要］
図7によりCMACの概要を説明する。
【００９１】
図7において、データ701は検証対象データである。データ701が分割処理（div()）702によって所定サイズ（ブロック暗号のブロックサイズ）に分割され、ブロックのデータごとに処理され、各処理に一つ前のブロックの処理結果とブロックのデータが入力される。ただし、最初のブロックのデータの処理における初期値がない、各処理が鍵kによる暗号化処理ek()、前処理結果とブロックのデータの排他的論理和をとる点で図4に示す処理とは異なる。さらに、最終のブロックのデータの処理が、前処理結果、最終のブロックのデータ、鍵K1の排他的論理和であり、処理msb()により排他的論理和の結果の上位ビット列を抽出して検査データTを出力するなど、図4に示す処理に比べて複雑な処理になる。
【００９２】
実施例3においては、最終の部分データの処理における暗号化処理ek()以外の暗号化処理ek()の結果を中間データにする。つまり、一般的なCMACにおいては、検証対象データ701と鍵kなどを入力し、検査データTを得るが、これらに加えて、実施例3においては、途中の暗号化処理ek()の結果を中間データとして出力する。また、実施例1と同様に、中間データとオフセットのペアを出力する。
【００９３】
なお、中間データの生成には機密情報である鍵を入力する必要があり、実施例2と同様に、中間データを含む検証データは鍵同様に機密性を維持して管理する必要がある。
【００９４】
［機能構成］
●検証データ生成機能
図8のブロック図により実施例3の情報処理装置における検証データを生成する機能構成例を説明する。図1に示す機能構成と異なる構成ついて説明する。
【００９５】
実施例1のハッシュ値計算部203の代わりに、実施例3は、データ入力部202が入力した検証対象データをブロック暗号アルゴリズムに従い逐次処理する暗号化部703を備える。
【００９６】
また、実施例1の検査データ生成部204の代わりに、実施例3は、暗号化部703から入力した暗号データの所定の上位ビット列を抽出して検査データにする抽出部704を備える。
【００９７】
●検証対象データの検証機能
図9のブロック図により実施例3の情報処理装置における検証対象データを検証する機能構成例を説明する。図3に示す機能構成と異なる構成、処理について説明する。
【００９８】
実施例1のハッシュ値計算部210の代わりに、実施例3は、部分データと中間データにより暗号化処理を行う暗号化部710を備える。具体的には、検証データに含まれるオフセットに基づき検証対象データから分割された第一の部分データの暗号化結果（中間データ）を、第一の部分データに続く第二の部分データを暗号化するための入力とする暗号化を最終の部分データまで繰り返す。この繰り返しにより、中間データと検証対象データの暗号データを生成する。
【００９９】
分配部211は、暗号化部710が生成した中間データを比較部213に入力し、暗号化部710が生成した検証対象データの暗号データを検査データ検証部212に入力する。検査データ検証部212は、分配部211から入力される暗号データを用いて、分割部209から入力される検査データの検証処理を行う。
【０１００】
暗号化部710は、図9に示すように、並列処理部として構成される。つまり、分割部209が出力する、オフセットに対応する部分データを並列処理部を構成する部分データ生成部7101〜710Nの何れかへ入力して中間データを生成する。このように、中間データの生成を並列に処理することが可能である。
【０１０１】
図10のフローチャートにより検証対象データの検証処理を説明する。
【０１０２】
データ入力部208は、検証対象データと検証データを入力する(S801)。なお、検証データは、図2に示すように、検査データ、並びに、オフセットと中間データの複数のペアを含む。
【０１０３】
分割部209は、データ入力部208が入力した検証データに含まれるオフセットに基づき、データ入力部208が入力した検証対象データを部分データに分割し、各部分データを中間データ生成部7101〜710Nの何れかに入力する(S802)。中間データ生成部7101〜710Nは、分割部209から入力される部分データの種類を判定する(S803)。なお、部分データの種類の判定はオフセットを用いて行われる。
【０１０４】
入力された部分データが、検証対象データの最初のデータだけを含む先頭の部分データであると判定した場合、中間データ生成部7101〜710Nは、先頭の部分データを暗号化処理して中間データを生成する(S804)。
【０１０５】
また、入力された部分データを途中の部分データと判定した場合、中間データ生成部は、当該部分データと、当該部分データの一つ前の部分データの中間データを排他的論理和した結果を暗号化処理して当該部分データの中間データを生成する(S805)。なお、途中の部分データとは、最初のデータに続くデータを含む（言い換えれば、最初のデータを含まない）部分データである。また、部分データがブロック暗号の所定のブロックサイズより大きい場合は、CMAC処理に従い、部分データを所定のブロックサイズに分割して処理を行う。
【０１０６】
比較部213は、中間データ生成部7101〜710Nの何れかが生成した中間データと、分割部209から入力される対応する中間データを比較する(S806)。この後、処理はステップS802に戻る。
【０１０７】
入力された部分データが最終の部分データであると判定した場合、中間データ生成部は、最終の部分データ、最終の部分データの一つ前の部分データの中間データ、鍵K1を排他的論理和した結果を暗号化処理して暗号データを生成する(S807)。検査データ検証部212は、暗号化部710が最終的に生成した暗号データから所定の上位ビット列を抽出し、抽出したビット列と検証データに含まれる検査データを比較する(S808)。
【０１０８】
比較部213は、ステップS809の判定により、検査データ検証部212における比較結果（検証結果）、および、中間データの比較結果（検証結果）のすべてが検証の成功を示す場合は検証対象データの完全性の検証に成功したと判定する(S810)。また、そうでない場合は、検証対象データの完全性の検証に失敗したと判定する(S811)。
【０１０９】
各中間データの検証処理(S806)の何れかにおいて不一致を検出した場合、あるいは、検査データの検証処理(S808)において検証に失敗した場合、その時点で他の処理を中断して、ステップS810（検証に失敗）に進むことができる。また、暗号化処理（ステップS803-S805、S807）は、複数の中間データ生成部7101〜710Nにより並列処理が可能である。
【０１１０】
このように、CMACをベースとした、オフセットと中間データのペアを含む検証データを利用する電子データの完全性の検証においても、検証処理を並列化して高速化を図ることができる。また、図2に示す検証データには、署名データの代わりに検査データとしてCMAC値を含めることで、CMAC値を利用する一般的なCAMCによる検証を行うことも可能である。従って、検証対象の電子データ全体を一括処理する場合との互換性を維持することができる。
【０１１１】
なお、実施例3においても、実施例1と同様に、検証データからオフセットを省略することができる。その方法は、実施例1の変形例で説明した方法と同様であり、詳細説明を省略する。
【０１１２】
［その他の実施例］
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記録媒体を介してシステム或いは装置に供給し、そのシステムあるいは装置のコンピュータ（又はCPUやMPU等）がプログラムを読み出して実行する処理である。
【図１】
2013138409.tif 000003
【図２】
2013138409.tif 000004
【図３】
2013138409.tif 000005
【図４】
2013138409.tif 000006
【図５】
2013138409.tif 000007
【図６】
2013138409.tif 000008
【図７】
2013138409.tif 000009
【図８】
2013138409.tif 000010
【図９】
2013138409.tif 000011
【図１０】
2013138409.tif 000012
【図１１】
2013138409.tif 000013
【図１２】
2013138409.tif 000014