(57)【要約】  【課題】複数のデータからの任意抜粋保存に対応し、署名長を比較的短くできる効率的な署名技術を提供すること。  【解決手段】署名装置１８０の署名処理部１８９では、数学関数計算部１９０において、複数のデータの各々から算出したハッシュ値を連結した連結値からさらにハッシュ値を算出する処理を繰り返し行うことで一つのハッシュ値ｈを算出し、算出した当該一つのハッシュ値から署名値を算出する。そして、署名処理部１８９は、複数のデータに含まれる一のデータに対して、算出した署名値と、一つのハッシュ値ｈを算出するまでに、当該一のデータから算出されたハッシュ値に連結された他のハッシュ値と、を含めて署名を生成する。【選択図】図２
2009182864.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータの各々に署名を生成する署名装置であって、
前記複数のデータの各々からハッシュ値を算出する第一の処理と、
算出されたハッシュ値を連結した連結値からハッシュ値を算出する処理を繰り返すことで、一つのハッシュ値を算出する第二の処理と、
前記一つのハッシュ値から署名鍵を用いて署名値を算出する第三の処理と、
前記複数のデータに含まれる一のデータに対して、前記署名値と、前記一つのハッシュ値を算出するまでに、前記一のデータから算出されたハッシュ値に連結された他のハッシュ値と、を含む署名を生成する第四の処理と、
を行う制御部を備えること、
を特徴とする署名装置。
【請求項２】
請求項１に記載の署名装置であって、
前記第二の処理は、前記第一の処理で算出されたハッシュ値を、予め定められた順番に従って二つ連結することで連結値を生成してハッシュ値を算出するものであり、
前記第四の処理で生成する署名には、前記番号が含まれること、
を特徴とする署名装置。
【請求項３】
請求項１又は２に記載の署名装置であって、
前記第一の処理は、前記複数のデータの各々に対して、予め定められた値を連結した値にからハッシュ値を算出すること、
を特徴とする署名装置。
【請求項４】
請求項３に記載の署名装置であって、
前記第一の処理において、前記複数のデータの各々に対して連結する値は、前記署名装置を識別するための識別情報であり、
前記第四の署名で生成する署名には、前記識別番号が含まれること、
を特徴とする署名装置。
【請求項５】
請求項３に記載の署名装置であって、
前記第一の処理において、前記複数のデータの各々に対して連結する値は、時刻情報であり、
前記第四の署名で生成する署名には、前記時刻情報が含まれること、
を特徴とする署名装置。
【請求項６】
請求項１乃至５のいずれか一項に記載の署名装置であって、
前記制御部は、
前記複数のデータが、２べき数ではない場合には、任意の値によりデータを生成して付加することで、署名値の算出対象とするデータの数を２べき数にする第五の処理を、少なくとも前記第二の処理の前に行うこと、
を特徴とする署名装置。
【請求項７】
複数のデータの各々に付された署名を検証する検証装置であって、
前記複数のデータに含まれる一のデータの前記署名には、署名値と、当該署名値を算出するための一つハッシュ値を算出するまでに、前記一のデータから算出されたハッシュ値に連結された他のハッシュ値と、が含まれており、
前記一のデータからからハッシュ値を算出する第一の処理と、
算出されたハッシュ値に前記他のハッシュ値を連結する処理を繰り返すことで、一つのハッシュ値を算出する第二の処理と、
前記署名値から検証鍵を用いて一つのハッシュ値を算出する第三の処理と、
前記第二の処理で算出された一つのハッシュ値と、前記第三の処理で算出された一つのハッシュ値と、を検証する第四の処理と、
を行う制御部を備えること、
を特徴とする検証装置。
【請求項８】
請求項７に記載の検証装置であって、
前記署名には、前記一のデータから算出されたハッシュ値を他のハッシュ値に連結する順番を特定する情報が含まれており、
前記第二の処理は、前記順番に従って、前記一のデータから算出されたハッシュ値を他のハッシュ値に連結した連結値からハッシュ値を算出すること、
を特徴とする検証装置。
【請求項９】
請求項７又は８に記載の検証装置であって、
前記署名には、前記一のデータに連結した所定の値を特定する情報が含まれており、
前記第一の処理は、前記一のデータに前記所定の値を連結した値からハッシュ値を算出すること、
を特徴とする検証装置。
【請求項１０】
コンピュータを、複数のデータの各々に署名を生成する署名装置として機能させるプログラムであって、
前記コンピュータを、
前記複数のデータの各々からハッシュ値を算出する第一の処理と、
算出されたハッシュ値を連結した連結値からハッシュ値を算出する処理を繰り返すことで、一つのハッシュ値を算出する第二の処理と、
前記一つのハッシュ値から署名鍵を用いて署名値を算出する第三の処理と、
前記複数のデータに含まれる一のデータに対して、前記署名値と、前記一つのハッシュ値を算出するまでに、前記一のデータから算出されたハッシュ値に連結された他のハッシュ値と、を含む署名を生成する第四の処理と、
を行う制御手段として機能させること、
を特徴とするプログラム。
【請求項１１】
請求項１０に記載のプログラムであって、
前記第二の処理は、前記第一の処理で算出されたハッシュ値を、予め定められた順番に従って二つ連結することで連結値を生成してハッシュ値を算出するものであり、
前記第四の処理で生成する署名には、前記番号が含まれること、
を特徴とするプログラム。
【請求項１２】
請求項１０又は１１に記載のプログラムであって、
前記第一の処理は、前記複数のデータの各々に対して、予め定められた値を連結した値にからハッシュ値を算出すること、
を特徴とするプログラム。
【請求項１３】
請求項１２に記載のプログラムであって、
前記第一の処理において、前記複数のデータの各々に対して連結する値は、前記署名装置を識別するための識別情報であり、
前記第四の署名で生成する署名には、前記識別番号が含まれること、
を特徴とするプログラム。
【請求項１４】
請求項１２に記載のプログラムであって、
前記第一の処理において、前記複数のデータの各々に対して連結する値は、時刻情報であり、
前記第四の署名で生成する署名には、前記時刻情報が含まれること、
を特徴とするプログラム。
【請求項１５】
請求項１０乃至１４のいずれか一項に記載のプログラムであって、
前記制御手段は、
前記複数のデータが、２べき数ではない場合には、任意の値によりデータを生成して付加することで、署名値の算出対象とするデータの数を２べき数にする第五の処理を、少なくとも前記第二の処理の前に行うこと、
を特徴とするプログラム。
【請求項１６】
コンピュータを、複数のデータの各々に付された署名を検証する検証装置として機能させるプログラムであって、
前記複数のデータに含まれる一のデータの前記署名には、署名値と、当該署名値を算出するための一つハッシュ値を算出するまでに、前記一のデータから算出されたハッシュ値に連結された他のハッシュ値と、が含まれており、
前記コンピュータを、
前記一のデータからからハッシュ値を算出する第一の処理と、
算出されたハッシュ値に前記他のハッシュ値を連結する処理を繰り返すことで、一つのハッシュ値を算出する第二の処理と、
前記署名値から検証鍵を用いて一つのハッシュ値を算出する第三の処理と、
前記第二の処理で算出された一つのハッシュ値と、前記第三の処理で算出された一つのハッシュ値と、を検証する第四の処理と、
を行う制御手段として機能させること、
を特徴とするプログラム。
【請求項１７】
請求項１６に記載のプログラムであって、
前記署名には、前記一のデータから算出されたハッシュ値を他のハッシュ値に連結する順番を特定する情報が含まれており、
前記第二の処理は、前記順番に従って、前記一のデータから算出されたハッシュ値を他のハッシュ値に連結した連結値からハッシュ値を算出すること、
を特徴とするプログラム。
【請求項１８】
請求項１６又は１７に記載のプログラムであって、
前記署名には、前記一のデータに連結した所定の値を特定する情報が含まれており、
前記第一の処理は、前記一のデータに前記所定の値を連結した値からハッシュ値を算出すること、
を特徴とするプログラム。
【請求項１９】
複数のデータの各々に署名を生成する制御部を備える署名装置が行う署名方法であって、
前記制御部が、前記複数のデータの各々からハッシュ値を算出する第一の過程と、
前記制御部が、算出されたハッシュ値を連結した連結値からハッシュ値を算出する処理を繰り返すことで、一つのハッシュ値を算出する第二の過程と、
前記制御部が、前記一つのハッシュ値から署名鍵を用いて署名値を算出する第三の過程と、
前記制御部が、前記複数のデータに含まれる一のデータに対して、前記署名値と、前記一つのハッシュ値を算出するまでに、前記一のデータから算出されたハッシュ値に連結された他のハッシュ値と、を含む署名を生成する第四の過程と、
を備えること、
を特徴とする署名方法。
【請求項２０】
複数のデータの各々に付された署名を検証する制御部を備える検証装置が行う検証方法であって、
前記複数のデータに含まれる一のデータの前記署名には、署名値と、当該署名値を算出するための一つハッシュ値を算出するまでに、前記一のデータから算出されたハッシュ値に連結された他のハッシュ値と、が含まれており、
前記制御部が、前記一のデータからからハッシュ値を算出する第一の過程と、
前記制御部が、算出されたハッシュ値に前記他のハッシュ値を連結する処理を繰り返すことで、一つのハッシュ値を算出する第二の過程と、
前記制御部が、前記署名値から検証鍵を用いて一つのハッシュ値を算出する第三の過程と、
前記制御部が、前記第二の過程で算出された一つのハッシュ値と、前記第三の過程で算出された一つのハッシュ値と、を検証する第三の過程と、
を備えること、
を特徴とする検証方法。
【請求項２１】
複数のデータの各々に署名を生成する署名装置と、当該署名装置で生成された署名を検証する検証装置と、を備えるシステムであって、
前記署名装置は、
前記複数のデータの各々からハッシュ値を算出する第一の処理と、
算出されたハッシュ値を連結した連結値からハッシュ値を算出する処理を繰り返すことで、一つのハッシュ値を算出する第二の処理と、
前記一つのハッシュ値から署名鍵を用いて署名値を算出する第三の処理と、
前記複数のデータに含まれる一のデータに対して、前記署名値と、前記一つのハッシュ値を算出するまでに、前記一のデータから算出されたハッシュ値に連結された他のハッシュ値と、を含む署名を生成する第四の処理と、
を行う制御部を備え、
前記検証装置は、
前記一のデータからからハッシュ値を算出する第五の処理と、
算出されたハッシュ値に前記他のハッシュ値を連結する処理を繰り返すことで、一つのハッシュ値を算出する第六の処理と、
前記署名値から検証鍵を用いて一つのハッシュ値を算出する第七の処理と、
前記第二の処理で算出された一つのハッシュ値と、前記第七の処理で算出された一つのハッシュ値と、を検証する第八の処理と、
を行う制御部を備えること、
を特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のデータから署名を生成し、生成した署名を検証する技術に関する。
【背景技術】
【０００２】
監視対象とするエリアに監視カメラを設置し、この監視カメラで撮影した映像を、インターネットを通じて警備会社などの監視センタに送信し、遠隔地を一括監視する映像監視システムでは、データサイズの大きな映像（例えば、ＪＰＥＧやＭＰＥＧなど）を監視センタなどに設置した蓄積サーバに長期間保存しておき、保存した映像に対する証拠性を確保するためにデジタル署名の適用が望まれている。
【０００３】
特に、中小規模の映像監視システムでは、低コスト化などのために、蓄積サーバの容量に制約があり、映像データを抜粋して保存したり、監視側の装置から映像データの一部の送信を要求された場合に、連続する映像データから抜粋して監視側の装置に送信したりするのが一般的である。
【０００４】
このような映像データを抜粋保存する際に適用可能な署名技術として、例えば、特許文献１に記載の技術がある。
【０００５】
特許文献１に記載の技術では、抜粋保存する際に選択したデータ、および、抜粋保存する際に選択されなかったデータのハッシュ値、全てのデータのハッシュ値から生成した署名値、を署名付きデータとして署名検証側のサーバに送信する。
【０００６】
署名検証側のサーバでは、選択されたデータのハッシュ値を算出して、選択されなかったデータのハッシュ値に連結して、署名の検証を行う。
【０００７】
【特許文献１】特開２００７−２８０１４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
特許文献１に記載の技術では、抜粋保存する際に選択したデータ、および、抜粋保存する際に選択されなかったデータのハッシュ値、全てのデータのハッシュ値から生成した署名値、を署名付きデータとして署名検証側のサーバに送信するため、署名対象のデータ数が多い場合、署名長が長くなってしまう。署名長が長くなると、記憶領域を圧迫し、送受信の効率性に大きな影響を及ぼし、署名の検証にも多くの時間がかかってしまうという課題がある。
【０００９】
そこで、本発明は、複数のデータからの任意抜粋保存に対応し、署名長を比較的短くできる効率的な署名技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
以上の課題を解決するため、本発明は、複数のデータの各々から算出したハッシュ値を連結した連結値からさらにハッシュ値を算出する処理を繰り返し行うことで一つのハッシュ値を算出し、算出した当該一つのハッシュ値から署名値を算出し、当該署名値と、当該署名値を算出するまでに連結したハッシュ値と、を特定する情報から署名を生成する。
【００１１】
例えば、本発明は、複数のデータの各々に署名を生成する署名装置であって、前記複数のデータの各々からハッシュ値を算出する第一の処理と、算出されたハッシュ値を連結した連結値からハッシュ値を算出する処理を繰り返すことで、一つのハッシュ値を算出する第二の処理と、前記一つのハッシュ値から署名鍵を用いて署名値を算出する第三の処理と、前記複数のデータに含まれる一のデータに対して、前記署名値と、前記一つのハッシュ値を算出するまでに、前記一のデータから算出されたハッシュ値に連結された他のハッシュ値と、を含む署名を生成する第四の処理と、を行う制御部を備えること、を特徴とする。
【発明の効果】
【００１２】
以上のように、本発明によれば、複数のデータからの任意抜粋保存に対応し、署名長を比較的短くできる効率的な署名技術を提供することができる。
【発明を実施するための最良の形態】
【００１３】
図１は、本発明の第一の実施形態である映像監視システム１００の概略図である。
【００１４】
図示するように、映像監視システム１００は、映像生成装置１１０、エンコーダ１２０、蓄積装置１３０、表示装置１４０及び検証装置１５０を備え、映像生成装置１１０とエンコーダ１２０はネットワーク１７０を介して情報を送受信することができ、エンコーダ１２０と蓄積装置１３０はネットワーク１７１を介して情報を送受信することができ、蓄積装置１３０と表示装置１４０はネットワーク１７２を介して情報を送受信することができるようにされている。
【００１５】
なお、本実施形態においては、検証装置１５０は、ネットワーク１７０、１７１、１７２にいずれにも接続されていないが、これらの少なくともいずれか一つに接続することができるようにしてもよい。
【００１６】
映像生成装置１１０は、撮像素子を備えるカメラ等により構成される映像処理部を有する（図示せず）。
【００１７】
また、映像生成装置１１０は、映像データを記憶部に記憶し、他の映像生成装置１１０、蓄積装置１３０及び表示装置１４０の少なくとも何れかの装置からの要求、または、映像生成装置１１０自身の判断により、ネットワーク１７１を介して、他の映像生成装置１１０、蓄積装置１３０及び表示装置１４０の少なくとも何れかの装置に配信する配信機能を有する。ここで、映像生成装置１１０の判断とは、例えば、差分等により動体を検知した場合等を指す。
【００１８】
エンコーダ１２０は、映像データをネットワーク伝送に適した形式に変換する機能も有する。例えば、映像データがアナログ信号である場合にはデジタル変換処理を行なったり、ネットワーク１７１の伝送帯域に応じて圧縮処理を行ったりする。
【００１９】
なお、本実施形態においては、映像生成装置１１０とエンコーダ１２０とを別々の装置として説明したが、これらが同じ装置（筐体）内に実現されていてもよい。
【００２０】
蓄積装置１３０は、映像生成装置１１０、または、他の蓄積装置１３０が配信した映像データを受信して、記憶部に記憶する記憶制御部を有する（図示せず）。
【００２１】
蓄積装置１３０の記憶制御部は、受信した複数の映像データの中から任意に一つ以上を抜粋して記憶部に記憶することも可能である。抜粋されなかった映像データは記憶部には保存されず、破棄される。抜粋保存を行う際、抜粋保存の対象となる映像データの個数は、蓄積装置１３０において設定を受け付けてもよいし、映像生成装置１１０において決定し蓄積装置１３０に設定されてもよい。
【００２２】
また、蓄積装置１３０は、他の蓄積装置１３０及び表示装置１４０の少なくとも何れか一方からの映像要求、または、蓄積装置１３０自身の判断により、ネットワーク１７２を介して、映像データを蓄積装置１３０又は表示装置１４０に配信する配信機能も有する。
【００２３】
表示装置１４０は、蓄積装置１３０から映像データを受信して表示する処理を制御する表示処理部を有する（図示せず）。また、表示処理部は、受信した複数の映像データの中から任意に少なくとも一つ以上を抜粋して記憶部に保存すること可能である。抜粋されなかった映像データは破棄される。抜粋保存を行う際、抜粋保存の対象となる映像データの個数は、表示装置１４０において設定を受け付けてもよいし、映像生成装置１１０又は蓄積装置１３０において決定し表示装置１４１に設定されてもよい。
【００２４】
ここで、本実施形態においては、以上に記載した映像生成装置１１０、エンコーダ１２０、蓄積装置１３０及び表示装置１４０のいずれについても、以下に記載する署名装置１８０の各機能部をさらに備えることで、署名装置１８０として利用することができる。
【００２５】
即ち、映像生成装置１１０、エンコーダ１２０、蓄積装置１３０及び表示装置１４０の何れかで生成した署名付き映像データを、映像生成装置１１０、エンコーダ１２０、蓄積装置１３０及び表示装置１４０の何れかにおいて抜粋保存しておき、抜粋して保存しておいた署名付き映像データを後述するように検証装置１５０で検証することで、映像データの真正性を証明することができるようになる。
【００２６】
図２は、署名装置１８０の概略図である。
【００２７】
図示するように署名装置１８０は、記憶部１８１と、制御部１８６と、入力部１９１と、出力部１９２と、送受信部１９３と、を備える。
【００２８】
記憶部１８１は、署名鍵記憶部１８２と、検証鍵記憶部１８３と、映像データ記憶部１８４と、署名付きデータ記憶部１８５と、を備える。
【００２９】
署名鍵記憶部１８２には、映像データに対して署名を行う署名鍵ｓｋが記憶される。
【００３０】
検証鍵記憶部１８３には、署名鍵ｓｋを用いて生成された署名に対して検証を行うための検証鍵ｐｋが記憶される。
【００３１】
映像データ記憶部１８４には、映像生成装置１１０で撮影された予め定められたデータ形式にされた複数の映像データが記憶される。
【００３２】
署名付きデータ記憶部１８５には、後述する署名処理部１８９で映像データから生成された署名付き映像データが記憶される。
【００３３】
制御部１８６は、全体制御部１８９と、映像処理部１８８と、署名処理部１８９と、数学関数計算部１９０と、を備える。
【００３４】
全体制御部１８９は、署名装置１８０における処理の全体を制御する。
【００３５】
映像処理部１８８は、映像生成装置１１０で撮影された映像データを映像データ記憶部１８４に記憶する処理を行う。
【００３６】
署名処理部１８９は、映像データ記憶部１８４に記憶されている映像データに署名を付すことにより、署名付き映像データを生成し、署名付きデータ記憶部１８５に記憶する処理を行う。
【００３７】
数学関数計算部１９０は、予め定められたハッシュ関数を用いて、入力されたデータのハッシュ値を算出する処理を行う。
【００３８】
また、数学関数計算部１９０は、予め定められた署名生成エンジン及び署名鍵記憶部１８２に記憶されている署名鍵ｓｋを用いて、入力されたデータの署名値を生成する処理を行う。
【００３９】
ここで、図３（署名の生成処理を示す概略図）を用いて、本実施形態における署名処理部１８９及び数学関数計算部１９０が署名付き映像データを生成する処理の概略を説明する。
【００４０】
図３では、８個の映像データＭ１，Ｍ２，・・・，Ｍ８に対する署名付き映像データを生成する。
【００４１】
ここで、本実施形態においては、図示するように、映像データから算出されるハッシュ値を二つ連結してさらにハッシュ値を算出するハッシュ木の構造を用いる。
【００４２】
まず、署名処理部１８９は、映像データ記憶部１８４に記憶されている各映像データに１〜８までの自然数の連番を付すことにより、映像データＭ１，Ｍ２，・・・，Ｍ８とし、各映像データＭｉ（ｉ＝１，２，・・・，８）を数学関数計算部１９０に入力することで、各映像データＭｉの０段目のハッシュ値ｈ０，ｉを算出する。
【００４３】
次に、署名処理部１８９は、各映像データＭｉのハッシュ値ｈ０．ｉを順番に２個ずつ連結した値ｈ０，ｊ||ｈ０，ｊ＋１（ｊは奇数の自然数）を算出し、１段目のハッシュ値ｈ１，ｉを算出する。なお、１段目では、０段目のハッシュ値を二つ連結しているため、４(＝８/２)個のハッシュ値が算出される。
【００４４】
以上のように、署名処理部１８９は、ｋ段目のハッシュ値を２個ずつ連結したｈｋ，ｊ||ｈｋ，ｊ＋１に対するハッシュ値を計算する処理をハッシュ値が一つになるまで繰り返し、最終的に算出されたハッシュ値ｈ３，１と署名鍵記憶部１８２に記憶されている署名鍵ｓｋを数学関数計算部１９０に入力することで、数学関数計算部１９０は、署名鍵ｓｋを用いてハッシュ値ｈ３，１から署名値σを算出する。
【００４５】
そして、署名処理部１８９は、任意の映像データＭｉから算出されるハッシュ値に連結されたハッシュ値と、算出した署名値σと、映像データＭｉの番号（ハッシュ木に入力する位置）を特定する情報と、を有する署名を生成し、映像データＭｉに添付することで、署名付き映像データを生成する。
【００４６】
ここで、例えば、署名付き映像データを生成する映像データをＭ５とすると、映像データＭ５から算出されるハッシュ値（図３では、ｈ０，５、ｈ１，３、ｈ２，２）に連結されるハッシュ値は、ｈ０，６、ｈ１，４、ｈ２，１であるため、これらのハッシュ値を署名に含める。なお、これらのハッシュ値は、映像データＭ５から算出されるハッシュ値に連結する順序がわかるように署名に含めておく（本実施形態では、連結する順に署名に含めるようにしている）。
【００４７】
なお、複数の映像データＭ１，・・・，Ｍ８は必ずしも時系列に沿って連続する映像とは限らない。
【００４８】
図２に戻り、入力部１９１は、情報の入力を受け付ける。
【００４９】
出力部１９２は、情報を出力する。
【００５０】
送受信部１９３は、ネットワークを介して情報の送受信を行うためのインターフェースである。
【００５１】
以上に記載した署名装置１８０は、例えば、図４（コンピュータ５００の概略図）に示すような、ＣＰＵ（Central Processing Unit）５０１と、メモリ５０２と、ＨＤＤ（Hard Disk Drive）等の外部記憶装置５０３と、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）やＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory）等の可搬性を有する記憶媒体５０４から情報を読み出す読取装置５０５と、キーボードやマウスなどの入力装置５０６と、ディスプレイなどの出力装置５０７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置５０８と、を備えた一般的なコンピュータ５００で実現できる。
【００５２】
例えば、記憶部１８１は、ＣＰＵ５０１がメモリ５０２又は外部記憶装置５０３を利用することにより実現可能であり、制御部１８６は、外部記憶装置５０３に記憶されている所定のプログラムをメモリ５０２にロードしてＣＰＵ５０１で実行することで実現可能であり、入力部１９１は、ＣＰＵ５０１が入力装置５０６を利用することで実現可能であり、出力部１９２は、ＣＰＵ５０１が出力装置５０７を利用することで実現可能であり、送受信部１９３は、ＣＰＵ５０１が通信装置５０８を利用することで実現可能である。
【００５３】
この所定のプログラムは、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、外部記憶装置５０３にダウンロードされ、それから、メモリ５０２上にロードされてＣＰＵ５０１により実行されるようにしてもよい。また、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、メモリ５０２上に直接ロードされ、ＣＰＵ５０１により実行されるようにしてもよい。
【００５４】
図５は、検証装置１５０の概略図である。
【００５５】
図示するように、検証装置１５０は、記憶部１５１と、制御部１５４と、入力部１５８と、出力部１５９と、を備える。
【００５６】
記憶部１５１は、検証鍵記憶部１５２と、署名付きデータ記憶部１５３と、を備える。
【００５７】
検証鍵記憶部１５２には、署名装置１８０で生成された署名付き映像データに対して検証を行うための検証鍵ｐｋが記憶される。
【００５８】
署名付きデータ記憶部１５３には、署名装置１８０で生成された署名付き映像データが記憶される。
【００５９】
制御部１５４は、全体制御部１５５と、検証処理部１５６と、数学関数計算部１５７と、を備える。
【００６０】
全体制御部１５５は、検証装置１５０における処理の全体を制御する。
【００６１】
検証処理部１５６は、署名付きデータ記憶部１５３に記憶されている署名付き映像データを検証する処理を行う。
【００６２】
数学関数計算部１５７は、予め定められたハッシュ関数を用いて、入力されたデータのハッシュ値を算出する処理を行う。
【００６３】
また、数学関数計算部１５８は、予め定められた署名検証エンジン及び検証鍵記憶部１５２に記憶されている検証鍵ｐｋを用いて、入力された署名値から復号データを生成する処理を行う。
【００６４】
ここで、図６（検証処理を示す概略図）を用いて、本実施形態における検証処理部１５６及び数学関数計算部１５７において署名付き映像データを検証する処理の概略を説明する。
【００６５】
図６では、図３に示した８個の映像データＭ１，Ｍ２，・・・，Ｍ８の内の一つの映像データＭｉから生成された署名Ｓｉを検証する場合を例にして説明する。
【００６６】
まず、検証処理部１５６は、署名付き映像データより映像データＭｉを抽出して、数学関数計算部１５７に入力することで、ハッシュ木の０段目のハッシュ値ｈ０，ｉを算出する。
【００６７】
次に、検証処理部１５６は、署名付きデータよりハッシュ木の０段目のハッシュ値ｈ０，ａ（ａは、ｉが奇数の場合にはａ＝ｉ＋１、偶数の場合には、ａ＝ｉ−１）を抽出し、算出したハッシュ値ｈ０，ｉに連結して（ｉが奇数の場合にはｈ０，ｉ||ｈ０，ａ、ｉが偶数の場合にはｈ０，ａ||ｈ０，ｉ）、数学関数計算部１５７に入力することで、ハッシュ僕の１段目のハッシュ値ｈ１，ｉを算出する。
【００６８】
例えば、図６の例では、映像データＭ５から算出されるハッシュ値ｈ０，５に、署名付き映像データに含まれているハッシュ値ｈ０，６を連結した値（ｈ０，５||ｈ０，６）から、ハッシュ値ｈ１，３を算出する。
【００６９】
検証処理部１５６は、以上の処理を署名付き映像データに含まれている全てのハッシュ値を連結するまで繰り返し行うことで、最終的にハッシュ値ｈ３，１を算出する。
【００７０】
そして、検証処理部１５６は、署名付き映像データに含まれている署名値σと、検証鍵記憶部１５２に記憶されている検証鍵ｐｋを数学関数計算部１５７に入力することで、数学関数計算部１５７は、検証鍵ｐｋを用いて署名値σから検証値を算出する。
【００７１】
さらに、検証処理部１５６は、算出したハッシュ値ｈ３，１と、算出した検証値と、が一致する場合には、映像データＭｉの真正性が検証されたと判断する。
【００７２】
図５に戻り、入力部１５８は、情報の入力を受け付ける。
【００７３】
出力部１５９は、情報を出力する。
【００７４】
以上に記載した検証装置１５０は、例えば、図４に示すような一般的なコンピュータ５００で実現できる。
【００７５】
例えば、記憶部１５１は、ＣＰＵ５０１がメモリ５０２又は外部記憶装置５０３を利用することにより実現可能であり、制御部１５４は、外部記憶装置５０３に記憶されている所定のプログラムをメモリ５０２にロードしてＣＰＵ５０１で実行することで実現可能であり、入力部１５８は、ＣＰＵ５０１が入力装置５０６を利用することで実現可能であり、出力部１５９は、ＣＰＵ５０１が出力装置５０７を利用することで実現可能である。
【００７６】
この所定のプログラムは、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、外部記憶装置５０３にダウンロードされ、それから、メモリ５０２上にロードされてＣＰＵ５０１により実行されるようにしてもよい。また、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、メモリ５０２上に直接ロードされ、ＣＰＵ５０１により実行されるようにしてもよい。
【００７７】
図７は、署名装置１８０で署名付き映像データを生成する処理を示すフローチャートである。
【００７８】
まず、署名装置１８０の署名処理部１８９は、映像データ記憶部１８４から、複数の映像データＭ１，・・・，Ｍｋ（ｋは２ｍなる自然数で、ｍは１以上の自然数）を取得し、また、署名鍵記憶部１８２から署名鍵ｓｋを取得して、記憶部１８１に署名格納領域ｓ［１］，・・・，ｓ［ｋ］を確保する（Ｓ１０）。
【００７９】
次に、署名処理部１８９は、カウンタｉに１を代入する（Ｓ１１）。
【００８０】
次に、署名処理部１８９は、ｉ≦ｋ（＝２ｍ）であるか否かを判定し（Ｓ１２）、ｉ≦ｋが成立する場合（ステップＳ１２でＹｅｓ）ステップＳ１３に進み、ｉ≦ｋが成立しない場合（ステップＳ１２でＮｏ）ステップＳ１５に進む。
【００８１】
ステップＳ１３で、数学関数計算部１９０は、映像データＭｉのハッシュ値ｈ０，ｉ＝ｈ（Ｍｉ）を計算する。ここで、ｈはＳＨＡ−２５６などの暗号学的ハッシュ関数を表す。
【００８２】
そして、署名処理部１８９は、ｉに１をインクリメント（ｉ←ｉ＋１）して（Ｓ１４）、ステップＳ１２に戻り処理を繰り返す。
【００８３】
一方、ステップＳ１５では、署名処理部１８９は、カウンタｉに１（ｉ←１）、カウンタｊに１（ｊ←１）を代入する。
【００８４】
次に、署名処理部１８９は、ｊ≦ｍであるか否かを判定し（Ｓ１６）、ｊ≦ｍが成立する場合（ステップＳ１６でＹｅｓ）ステップＳ１７に進み、ｊ≦ｍが成立しない場合（ステップＳ１６でＮｏ）ステップＳ２１に進む。
【００８５】
ステップＳ１７では、署名処理部１８９は、ｉ≦２ｍ−ｊであるか否かを判定し、ｉ≦２ｍ−ｊが成立する場合（ステップＳ１７でＹｅｓ）ステップＳ１８に進み、ｉ≦２ｍ−ｊが成立しない場合（ステップＳ１７でＮｏ）ステップＳ２０に進む。
【００８６】
ステップＳ１８では、署名処理部１８９がハッシュ値ｈｊ−１，２ｉ−１及びハッシュ値ｈｊ−１、２ｉを連結した値（ｈｊ−１，２ｉ−１||ｈｊ−１、２ｉ）を数学関数計算部１９０に入力することで、数学関数計算部１９０が、ハッシュ値ｈｊ＝ｈ（ｈｊ−１，２ｉ−１||ｈｊ−１、２ｉ）を算出する。
【００８７】
次に、署名処理部１８９は、ｉに１をインクリメント（ｉ←ｉ＋１）して（Ｓ１９）、ステップＳ１７に戻り処理を繰り返す。
【００８８】
一方、ステップＳ２０では、署名処理部１８９は、ｊに１をインクリメント（ｊ←ｊ＋１）するとともにｉを初期値（ｉ←１）に戻し、ステップＳ１６に戻り処理を繰り返す。
【００８９】
また、ステップＳ２１では、署名処理部１８９は、署名鍵ｓｋを用いて、ハッシュ値ｈｍ，１から署名値σを算出する。
【００９０】
そして、署名処理部１８９は、ｉを初期値（ｉ←１）に戻す（Ｓ２２）。
【００９１】
次に、署名処理部１８９は、１≦ｉ≦２ｍであるか否かを判定し（Ｓ２３）、１≦ｉ≦２ｍが成立する場合（ステップＳ２３でＹｅｓ）、ステップＳ２４に進み、１≦ｉ≦２ｍが成立しない場合（ステップＳ２３でＮｏ）、処理を終了する。
【００９２】
ステップＳ２４では、署名処理部１８９は、図８に示すアルゴリズムを用いてａ（ｉ，０），ａ（ｉ，１），・・・，ａ（ｉ，ｍ−１）を算出することで、署名に含めるハッシュ値を特定する（Ｓ２５）。
【００９３】
そして、署名処理部１９は、映像データＭｉの署名として(ｈ０，ａ（ｉ，０），ｈ１，ａ（ｉ，１），・・・，ｈｍ−１，ａ（ｉ，ｍ−１），ｍ，ｉ，σ)をｓ［ｉ］に代入する（Ｓ２５）。
【００９４】
図８は、署名に含めるハッシュ値を特定するための数列を算出する処理を示すフローチャートである。
【００９５】
まず、署名処理部１８９は、映像データＭｉに割り振られる番号ｉと、署名対象個数ｋ(＝２ｍ)の2を底とする対数ｍを特定する（Ｓ３０）。
【００９６】
次に、署名処理部１８９は、ａ（ｉ，０）にｉを代入（ａ（ｉ，０）←ｉ）する（Ｓ３１）。
【００９７】
次に、署名処理部１８９は、ａ（ｉ，０）が偶数であるか否かを判定し（Ｓ３２）、ａ（ｉ，０）が偶数である場合（ステップＳ３２でＹｅｓ）ステップＳ３３に進み、ａ（ｉ，０）が奇数である場合（ステップＳ２２でＮｏ）ステップＳ３４に進む。
【００９８】
ステップＳ３３では、署名処理部１２９は、ａ（ｉ，０）にａ（ｉ，０）−１を代入（ａ（ｉ，０）←ａ（ｉ，０）−１）する。
【００９９】
一方、ステップＳ３４では、署名処理部１２９は、ａ（ｉ，０）にａ（ｉ，０）＋１を代入（ａ（ｉ，０）←ａ（ｉ，０）＋１）する。
【０１００】
次に、署名処理部１８９は、カウンタｊを初期化（ｊ←１）する（Ｓ３５）。
【０１０１】
次に、署名処理部１８９は、ｊ≦ｍ−１であるか否かを判定し（Ｓ３６）、ｊ≦ｍ−１が成立する場合（ステップＳ３５でＹｅｓ）にはステップＳ３７に進み、ｊ≦ｍ−１が成立しない場合（ステップＳ３５でＮｏ）にはステップＳ３８に進む。
【０１０２】
ステップＳ３８では、署名処理部１８９は、ｂ（ｉ，ｊ−１）にａ（ｉ，ｊ−１）／２を代入（ｂ（ｉ，ｊ−１）←ａ（ｉ，ｊ−１）／２）する。
【０１０３】
一方、ステップＳ３９では、署名処理部１８９は、ｂ（ｉ，ｊ−１）にａ（ｉ，ｊ−１）−１／２を代入（ｂ（ｉ，ｊ−１）←ａ（ｉ，ｊ−１）−１/２）する。
【０１０４】
次に、署名処理部１８９は、ｂ(ｉ，ｊ−１)が偶数である否かを判定し（Ｓ４０）、ｂ(ｉ，ｊ−１)が偶数である場合（ステップＳ３７でＹｅｓ）ステップＳ４１に進み、ｂ(ｉ，ｊ−１)が奇数である場合（ステップＳ３７でＮｏ）ステップＳ４２に進む。
【０１０５】
ステップＳ４１では、署名処理部１８９は、ａ（ｉ，ｊ）にｂ（ｉ，ｊ−１）−１を代入（ａ（ｉ，ｊ）←ｂ（ｉ，ｊ−１）−１）する。
【０１０６】
一方、ステップＳ４２では、署名処理部１８９は、ａ（ｉ，ｊ）にｂ（ｉ，ｊ−１）＋１を代入（ａ（ｉ，ｊ）←ｂ（ｉ，ｊ−１）＋１）する。
【０１０７】
そして、署名処理部１８９は、ｊに１をインクリメント（ｊ←ｊ＋１）して（Ｓ４３）、ステップＳ３６に戻り処理を繰り返す。
【０１０８】
一方、ステップＳ４４では、署名処理部１８９は、算出した数列ａ（ｉ，０），・・・，ａ（ｉ，ｍ−１）により、ハッシュ値を特定する。
【０１０９】
以上のようにして、署名装置１８０では、映像データＭ１，・・・，Ｍｋから署名Ｓ１，・・・，Ｓｋを生成する。
【０１１０】
そして、映像生成装置１１０、エンコーダ１２０、蓄積装置１３０又は表示装置１４０で映像データＭ１，・・・，Ｍｋを抜粋保存する場合には、任意の自然数ｉ（ｉ＝１，・・・，ｋ）を選択し、ｉに対応するメッセージＭｉと、メッセージＭｉに対応する署名Ｓｉと、を署名付き映像データとして保存する。
【０１１１】
なお、抜粋保存される映像データは、ＭＰＥＧ４の場合は基準画像、または、基準画像が含まれている映像データを用いる。
【０１１２】
図９は、検証装置１５０で署名付き映像データ（Ｍｉ、Ｓｉ）の検証処理を示すフローチャートである。
【０１１３】
まず、検証処理部１５６は、署名付きデータ記憶部１５３より映像データＭｉ及び署名Ｓｉ＝(ｈ０，ａ（ｉ，０），ｈ１，ａ（ｉ，１），ｈ２，ａ（ｉ，２），・・・，ｈｍ−１，ａ（ｉ，ｍ−１），ｍ，ｉ，σ)を取得し、また、検証鍵記憶部１５２より検証鍵ｐｋを取得する（Ｓ５０）。
【０１１４】
次に、検証処理部１５６は、ｂ０にｉを代入（ｂ０←ｉ）し、数学関数計算部１５７に映像メッセージＭｉを入力することで、ハッシュ値ｈ０，ｉ＝ｈ（Ｍｉ）を算出する（Ｓ５１）。
【０１１５】
次に、検証処理部１５６は、カウンタｊに１を代入（ｊ←１）する（Ｓ５２）。
【０１１６】
次に、検証処理部１５６は、ｊ≦ｍであるか否かを判定し（Ｓ５３）、ｊ≦ｍが成立する場合（ステップＳ５３でＹｅｓ）にはステップＳ５４に進み、ｊ≦ｍが成立しない場合（ステップＳ５３でＮｏ）にはステップＳ５６に進む。
【０１１７】
ステップＳ５４では、検証処理部１５６は、ｂｊ−１が偶数であるか否かを判定し、ｂｊ−１が偶数の場合（ステップＳ５４でＹｅｓ）にはステップＳ５５に進み、ｂｊ−１が奇数の場合（ステップＳ５４でＮｏ）にはステップＳ５６に進む。
【０１１８】
ステップＳ５５では、検証処理部１５６は、ｂｊにｂｊ−１／２を代入（ｂｊ←ｂｊ−１／２）し、数学関数計算部１５７を用いてハッシュ値ｈｊ，Ｂｊ＝ｈ（ｈｊ−１，ａ（ｉ，ｊ−１）||ｈｊ−１，Ｂｊ−１）を計算する。なお、Ｂｊ＝ｂｊであり、Ｂｊ−１＝ｂｊ−１である。
【０１１９】
一方、ステップＳ５６では、検証処理部１５６は、ｂｊに（ｂｊ−１＋１）／２を代入（ｂｊ←（ｂｊ−１＋１）／２）し、数学関数計算部１５７を用いてハッシュ値ｈｊ，Ｂｊ＝ｈ（ｈｊ−１，Ｂｊ−１||ｈｊ−１，ａ（ｉ，ｊ−１））を計算する。なお、Ｂｊ＝ｂｊであり、Ｂｊ−１＝ｂｊ−１である。
【０１２０】
次に、検証処理部１５６は、ｊにｊ＋１を代入（ｊ←ｊ＋１）して（Ｓ５７）、ステップＳ５３に戻り処理を繰り返す。
【０１２１】
次に、ステップＳ５８では、数学関数処理部１５７は、署名検証関数Ｖを用いてｈｍ，Ｂｍ＝Ｖ（σ，ｐｋ）であるか否かを判定し、一致する場合（ステップＳ５８でＹｅｓ）有効と判断し（Ｓ５９）、一致しない場合（ステップＳ５８でＮｏ）無効と判断する（Ｓ６０）。なお、Ｂｍ＝ｂｍである。
【０１２２】
以上のように、本実施形態によれば、映像メッセージＭｉと、これに対応する署名Ｓｉと、を任意に選択して保存しても、容易に検証を行うことができる。
【０１２３】
なお、以上に記載した実施形態において、署名Ｓ［ｉ］には、番号ｉが含まれている。これは、例えば、図６に示すように、署名(ｈ０，６，ｈ１，４，ｈ２，１，σ，５)に対する検証では、映像データＭ５に対するハッシュ値ｈ０，５を計算した後、計算したハッシュ値ｈ０，５と、署名に含まれるハッシュ値ｈ０，６と、の結合ｈ０，５||ｈ０，６に対するハッシュ値ｈ１，３を計算する。このとき、計算したハッシュ値ｈ０，５と、署名に含まれるハッシュ値ｈ０，６と、の結合の順序、すなわち、ｈ０，５||ｈ０，６であるか、ｈ０，６||ｈ０，５であるか、を決定する必要があるためである。
【０１２４】
また、同様の理由により、署名を検証する際、ハッシュ値の結合の順序を決定するために、図９のステップＳ５４に示すようにｂｊ−１の偶奇判定が必要となる。
【０１２５】
また、署名ｓ［ｉ］に、底を２とする署名対象個数の対数ｍが含まれるのは、本実施形態に記載の署名の生成及び署名の検証をソフトウェアなどで実現する際、署名ｓ［ｉ］に何個のハッシュ値が含まれているのかを示す値が必要となるためである。
【０１２６】
なお、本実施形態では署名ｓ［ｉ］に含まれているハッシュ値の個数を判断するためにｍを用いたが、このような態様に限定されず、署名ｓ［ｉ］に含まれているハッシュ値の個数を判断できればどのような情報や形式であってもよい。例えば、署名ｓ［ｉ］＝（ｉ，σ，ｈ０，ａ（ｉ，０），ｈ１，ａ（ｉ，１），ｈ２，ａ（ｉ，２），・・・，ｈｍ−１，ａ（ｉ，ｍ−１））のように署名に含まれる順序を入れ替えることで、ハッシュ値の個数を特定することができるようにしてもよい。即ち、このような署名の形式であれば、署名ｓ［ｉ］の４番目（データのビット数で特定可能）の成分ｈ０，ａ（ｉ，０）からハッシュ値が挿入されていると決めておけば、ｈｍ−１，ａ（ｉ，ｍ−１）が署名ｓ［ｉ］に含まれる最後の成分（署名データｓ［ｉ］の終端ＥＯＦ(End Of File)）であることがわかり、署名ｓ［ｉ］に含まれているハッシュ値の個数がｍであることがわかる。
【０１２７】
なお、図３及び図６では、ハッシュ木の２段目まではハッシュ関数ｈ、ハッシュ木３段目（最終段）ではハッシュ関数Ｈを用いている。このハッシュ関数ｈとハッシュ関数Ｈは同一のハッシュ関数（例えばＳＨＡ−２５６など）を用いてもよく、また、別々のハッシュ関数を用いてもよい。例えば、実システムへの適用時にはハッシュ関数Ｈと署名生成エンジンの部分をＲＳＡ−ＰＳＳ、ＥＣＤＳＡなどの署名方式に置き換えて使用してもよく、ハッシュ関数Ｈと署名生成エンジンの部分を署名方式に置き換える場合、図３及び図６のハッシュ木の最終段を含めて（図３及び図６の場合はｈ２，１||ｈ２，２、一般の場合はｈｍ−１，１||ｈｍ−１，２に対して）、署名生成することになる。
【０１２８】
さらに、以上に記載した実施形態においては、映像データＭ１，・・・，Ｍｋ（ｋ＝２ｍ）のハッシュ値をハッシュ木の０段目としたが、このような態様に限定されず、例えば、各映像データＭｉ（１≦ｉ≦ｋ）の各々に対応して予め定めた値ｒｉを連結したデータｍｉ＝Ｍｉ||ｒｉのハッシュ値をハッシュ木の０段目としてもよい。
【０１２９】
ここで、値ｒｉは、任意の値を用いることが可能であり、例えば、署名装置１８０のＭＡＣアドレスやＩＰアドレス、署名生成時の時刻（年月日時等）を用いることができる。このようなデータｍｉを用いることにより、映像データの正当性ばかりでなく、署名装置１８０や署名の生成時刻の正当性も検証することができる。なお、このような値ｒｉを映像データＭｉに連結した場合には、データｍｉと署名ｓｉとを署名付きデータとして抜粋保存する。
【０１３０】
また、本実施形態では、署名対象データを映像データとして説明したが、他のデータでもよい。
【０１３１】
本実施形態に記載の署名方式が高い安全性を備える理由は以下のとおりである。（ハッシュ関数Ｈと署名生成エンジンの部分の）署名方式（例えば、ＲＳＡ−ＰＳＳやＥＣＤＳＡなど）が暗号学的に安全（安全性証明可能）であり、かつ、ハッシュ関数が理想的なランダム関数（ランダムオラクルモデル）であると仮定し、攻撃モデルと安全性の定義を上述の方式にあわせて変更することにより、上述の複数のデータに対する署名生成／検証方式も暗号学的に安全（安全性証明可能）であることが証明できるからである。
【０１３２】
また、本実施形態に記載の署名方式が高い効率性を備える理由は以下の通りである。上述のとおり、公開鍵暗号では、その数学関数に最も処理時間を要し、ハッシュ関数の処理時間は、数学関数の処理時間と比較すると、非常に短い。それゆえ複数の映像データＭ１，・・・，Ｍｋに署名を生成する際に、本実施形態では、上述の署名方式では数学関数（署名関数、署名検証関数）を１回だけ計算すればよく、処理時間を短縮することができる。
【０１３３】
本実施形態では、署名対象個数ｎが２べきの数(ｋ＝２ｍ)の場合のみを説明したが、２べきの数だけでなく、任意個の複数の映像データに対する署名生成も可能である。
【０１３４】
署名対象個数が２べきの数でない場合、例えば、図１０（署名の生成処理を示す概略図）のような方法を用いることができる。
【０１３５】
図１０に示す署名の生成方法では、複数の署名データ（図１０では、Ｍ１〜Ｍ１１）のうちの最大の２べき数の映像データ（図１０では、Ｍ１〜Ｍ８）で図３と同様の方法で一つのハッシュ値（第一のハッシュ値）を算出し、残りの映像データ（図１０では、Ｍ９〜Ｍ１１）で一つのハッシュ値（第二のハッシュ値）を算出して、最後に第一のハッシュ値と第二のハッシュ値とを連結して署名生成エンジンに入力するハッシュ値を算出するようにしている。ここで、２べき数の映像データの残りの映像データ（図１０では、Ｍ９〜Ｍ１１）については、ハッシュ木の特定の段数での連結を行わずに一つのハッシュ値を算出することができるまでハッシュ値の算出を行う。
【０１３６】
また、図１０に示す署名の生成方法で生成された署名の検証については、図１１（検証処理を示す概略図）に示すように、署名する映像データＭ５、映像データＭ５から算出されたハッシュ値ｈ０，５に連結するハッシュ値（図１１では、ｈ０，６、ｈ１，４、ｈ２，１、ｈ３，２）、署名値σ、及び、映像データＭ５の番号５を署名に含めておくことで、図６と同様に検証可能である。
【０１３７】
次に、本発明の第二の実施形態について説明する。
【０１３８】
本発明の第二の実施形態については、第一の実施形態と比較して署名装置２８０が異なっているため、以下、署名装置２８０に関連する事項について説明する。
【０１３９】
図１２は、本発明の第二の実施形態における署名装置２８０の概略図である。
【０１４０】
図示するように署名装置２８０は、記憶部１８１と、制御部２８６と、入力部１９１と、出力部１９２と、送受信部１９３と、を備え、第一の実施形態と比較して制御部２８６が異なっているため、以下、制御部２８６に関連する事項について説明する。
【０１４１】
制御部２８６は、全体制御部１８９と、映像処理部１８８と、署名処理部２８９と、数学関数計算部１９０と、を備え、第一の実施形態と比較して署名処理部２８９が異なっているため、以下、署名処理部２８９に関連する事項について説明する。
【０１４２】
本実施形態における署名処理部２８９は、映像データ記憶部１８４に記憶されている映像データの数が２べき数に該当しない場合に、特定のデータを新たに生成し、署名対象となる映像データの個数を２べきの数にして、第一の実施形態と同様の方法で、署名を生成するようにしている。
【０１４３】
ここで、署名処理部２８９が新たに生成するデータは、予め定められた固定値でもよく、また、乱数でもよい。
【０１４４】
図１３は、署名装置２８０での署名の生成処理を示すフローチャートである。
【０１４５】
まず、署名装置２８０の署名処理部２８９は、＊Ｄａｔａｉｎｆｏ、署名鍵ｉｓｔａｔｅ＿ｓ、乱数生成用シードｓｅｅｄ＿ｒ［ｓＬｅｎ］、及び、署名格納用領域ｓ［ｎ］［ｆＬｅｎ］を取得する（Ｓ７０）。
【０１４６】
ここで、ｆＬｅｎ＝ｉｄＬｅｎ＋ｅｍＬｅｎ＋ｈＬｅｎ＊ｍを満たす正の整数であり、ｉｄＬｅｎはｉｄのバイト長、ｅｍＬｅｎは(ＲＳＡ−ＰＳＳやＥＣＤＳＡなどの)デジタル署名方式の署名長、ｈＬｅｎはハッシュ関数の出力バイト長、ｍは２ｍ−１＜ｎ≦２ｍを満たす正の整数である。
【０１４７】
一般に署名生成毎に署名対象個数ｎは変わる（可変である）ので、ｎに依存するｆＬｅｎも可変である。
【０１４８】
＊Ｄａｔａｉｎｆｏは、図１４（＊Ｄａｔａｉｎｆｏのフォーマットを示す概略図）に示すように署名対象とする複数の映像データＭ１，・・・，Ｍｎ、署名対象個数ｎ、及び、上記各映像データＭｉのバイト長Ｌｅｎｉを格納するための記憶領域であり、映像データ格納用の領域サイズは予め固定されている（例えば、１ＭＢｙｔｅなど）。
【０１４９】
また、＊Ｄａｔａｉｎｆｏに保存されている映像データ量が上記領域サイズに達していなくても、署名対象数が予め定められた数（これをＮＭＡＸとする）に達すると署名生成を行う。
【０１５０】
なお、複数の映像データＭ１，・・・，Ｍｎは同一の映像生成装置１１０によって生成された映像とは限らず、異なる複数の映像生成装置１１０によって生成された映像でもよい。
【０１５１】
さらに、複数の映像データＭ１，・・・，Ｍｎは同一の映像生成装置１１０によって生成された時系列に沿って連続する映像データとは限らない。時系列に沿って連続する複数の映像データに対して署名生成を行う場合は、署名生成を行う前に、予め時系列に沿って連続する複数の映像データＭ１，・・・，Ｍｎを上記記憶領域＊Ｍに格納しておけばよい。例えば、ＭＰＥＧ４の場合、時系列に沿って連続する複数の映像データＭ１，・・・，Ｍｎは、ＧＯＶ（Group of Video）と呼ばれる単位で記憶されている。この場合、Ｍｉは基準画像（Ｉフレーム）または差分画像（Ｐフレーム）のように、Ｍｉをフレーム１枚としてもよいし、Ｍｉは１つのＧＯＶであってもよいし、Ｍ１は基準画像、Ｍ２はＭ１の差分画像（複数）、Ｍ３は（Ｍ１とは異なる）基準画像、Ｍ２はＭ３の差分画像（複数）のようにしてもよい。
【０１５２】
また、署名格納用領域ｓｉｇｎ［ｎ］［ｆＬｅｎ］は、例えば、図１５（署名格納用領域のフォーマットを示す概略図）に記載のようなフォーマットをもつ。
【０１５３】
さらに、図１５に記載の署名格納用領域内のＩＤｉ（ｉ＝１，・・・，ｎ）部分は、例えば、図１６（ＩＤｉのフォーマットを示す概略図）に記載のようなフォーマットである。
【０１５４】
図１６に記載のアルゴリズム識別子（ａｌｇＩＤ）は、署名生成の際に用いた署名方式に対応する値を記憶する領域であり、署名方式に対応する値は、例えば、署名されていない場合は０ｘ００、ＲＳＡ−ＰＳＳは０ｘ０１、ＥＣＤＳＡは０ｘ０２などのように予め定められている。
【０１５５】
また、図１６に記載の鍵ＩＤは、署名の生成に用いる署名鍵が正当な鍵であるかどうかを確認するために用いる領域である。
【０１５６】
図１３に戻り、ステップＳ７０に続き、署名処理部２８９は、Ｎ≦ＮＭＡＸであるか否かを判定し（Ｓ７１）、Ｎ≦ＮＭＡＸが成立する場合（ステップＳ７１でＹｅｓ）ステップＳ７２に進み、Ｎ≦ＮＭＡＸが成立しない場合（ステップＳ７１でＮｏ）ステップＳ８３に進む。
【０１５７】
ステップＳ８３では、署名処理部２８９は、エラーを示す−１００を出力部１９２に出力して処理を終了する。
【０１５８】
次に、署名処理部２８９は、ｔｅｍｐにｈ（ｐ×ｑ）を代入する（Ｓ７２）。
【０１５９】
次に、署名処理部２８９は、カウンタｊを初期化（ｊ←１）する（Ｓ７３）。
【０１６０】
次に、署名処理部２８９は、ｊ≦ｎであるか否かを判定し（Ｓ７４）、ｊ≦ｎが成立する場合（ステップＳ７４でＹｅｓ）にはステップＳ７５に進み、ｊ≦ｎが成立しない場合（ステップＳ７４でＮｏ）にはステップＳ７７に進む。
【０１６１】
ステップＳ７５では、署名処理部２８９は、鍵ＩＤ（ｋｅｙＩＤｊ）にｔｅｍｐを代入する。
【０１６２】
そして、署名処理部２８９は、ｊに１をインクリメント（ｊ←ｊ＋１）して（Ｓ７６）、ステップＳ７４に戻り処理を繰り返す。
【０１６３】
一方、ステップＳ７７では、署名処理部２８９は、２ｍ−１＜ｎ≦２ｍなるｍを計算する。
【０１６４】
そして、署名処理部２８９は、ｎ＜２ｍであるか否かを判定し（Ｓ７８）、ｎ＜２ｍが成立する場合（ステップＳ７８でＹｅｓ）にはステップＳ７９に進み、ｎ＜２ｍが成立しない場合（ステップＳ７８でＮｏ）にはステップＳ８０に進む。
【０１６５】
ステップＳ７９では、署名処理部２８９は、記憶部１８１に領域Ｍｎ＋１，・・・，Ｍｋ（ｋ＝２ｍ）を確保し、これらの領域Ｍｎ＋１，・・・，Ｍｋ（ｋ＝２ｍ）に予め定められた固定値又は乱数を入力する（Ｓ７９）。
【０１６６】
次に、署名処理部２８９は、署名生成計算のために、領域ｈｊ，ｋ（１≦ｊ≦ｍ、１≦ｋ≦２ｍ−ｊ）を動的確保し、領域確保に成功したか否かを確認する（Ｓ８０）。そして、署名処理部は、領域確保に成功した場合（ステップＳ８０でＹｅｓ）にはステップＳ８１に進み、領域確保に失敗した場合（ステップＳ８０でＮｏ）にはステップＳ８４に進む。
【０１６７】
ステップＳ８４では、署名処理部２８９は、エラーを示す−１００を出力部１９２に出力して処理を終了する。
【０１６８】
一方、ステップＳ８１では、署名処理部２８９は、署名方式を決定し、図７に示すアルゴリズムを用いて、複数の映像データＭ１，・・・，Ｍｎ、ｉｓｔａｔｅ＿ｓ、ｓｅｅｄ＿ｒ［ｓＬｅｎ］、ｓ［ｆＬｅｎ］［１］，・・・，ｓ［ｆＬｅｎ］［ｎ］の署名生成を行い、使用した署名方式に対応する値をアルゴリズム識別子に代入する。
【０１６９】
次に、署名処理部２８９は、ステップＳ８０で確保した領域を解放して（Ｓ８２）、処理を終了する。
【０１７０】
なお、以上のフローチャートでは、ステップＳ７９で２べき数に不足する全てのデータに対して領域を確保しているが、このような態様に限定されず、例えば、連結するハッシュ値が必要となった段階で領域を確保するようにしてもよい。
【０１７１】
図１７は、検証装置１５０における検証処理を示すフローチャートである。
【０１７２】
ここでは、署名装置２８０で生成された、映像データ＊ｄａｔａ、映像データ＊ｄａｔａの署名(ｈ０，ａ（ｉ，０），ｈ１，ａ（ｉ，１），・・・，ｈｍ−１，ａ（ｉ，ｍ−１），ｍ，ｎ，ｉ，σ)を含むような図１８（ｓ［ｉ］のフォーマットを示す概略図）に記載のフォーマットをもつｓ［ｉ］、及び、検証鍵ｐｋから署名σが「有効」であるか否かを計算する手順について説明する。
【０１７３】
まず、検証装置１５０の検証処理部１５６は、映像データ＊ｄａｔａ、映像データ＊ｄａｔａのバイト長ｄａｔａＬｅｎ、映像データ＊ｄａｔａの署名ｓｉｇｎ［ｆＬｅｎ］、及び、検証鍵ｉｓｔａｔｅ＿ｐを取得する（Ｓ９０）。
【０１７４】
次に、検証処理部１５６は、ｓｉｇｎ［ｆＬｅｎ］から鍵ＩＤ（ｋｅｙＩＤｊ）を取り出す（Ｓ９１）。
【０１７５】
次に、検証処理部１５６は、公開鍵ｉｓｔａｔｅ＿ｐとｋｅｙＩＤｊを用いて公開鍵ｉｓｔａｔｅ＿ｐの正当性を確認する（Ｓ９２）。正当な場合（Ｓ９２でＹｅｓ）にはステップＳ９３に進み、正当ではない場合（ステップＳ９２でＮｏ）にはステップＳ９８に進む。
【０１７６】
ここで、署名方式として（通常のＮ＝ｐ×ｑ型）ＲＳＡを用いている場合を例に、ステップＳ９２における正当性の確認について説明する。
【０１７７】
ＲＳＡ署名では、同程度ビット長の素数ｐ、ｑ、および、ランダムな整数０≦ｄ＜（ｐ−１）×（ｑ−１）に対して、(ｐ，ｑ，ｄ)を署名鍵、Ｎ＝ｐ×ｑ、ｅ＝１／ｄｍｏｄ（ｐ−１）×（ｑ−１）に対して(Ｎ，ｅ)を検証鍵とする。ＮはＲＳＡモジュラスと呼ばれる。ｋｅｙＩＤｊは予めＲＳＡモジュラスＮのハッシュ値ｈ（Ｎ）の一部（または全体）を格納しておく領域であり、署名生成時に上記ハッシュ値ｈ（Ｎ）の一部（または全体）が格納されているとする。
【０１７８】
正当性の確認は、検証鍵(Ｎ，ｅ)からｈ（Ｎ）を計算し、上記ｈ（Ｎ）の一部（または全体）と上記予めｋｅｙＩＤｊに保存されているＲＳＡモジュラスＮのハッシュ値ｈ（Ｎ）の一部（または全体）と比較し、一致する場合、検証鍵は正当であるとし、一致しない場合、検証鍵は不等（正当ではない）と判断する。このような正当性の確認により、入力された署名が正等な検証鍵を用いて検証されたか否かを確認することができる。
【０１７９】
また、ｋｅｙＩＤｊは検証鍵の正当性確認だけでなく、署名検証に必要な検証鍵を効率的に検索する役割も担っている。即ち、署名検証処理では、どの装置で生成された署名なのかを確認し、署名を生成した装置の検証鍵を効率的に検索する必要がある。そのため、検証装置１５０は予め複数の映像生成装置１１０、エンコーダ１２０、蓄積装置１３０又は表示装置１４０の署名鍵に対応する検証鍵と、ｈ（Ｎ）の一部（または全体）と、の組を、例えば、図１９（検証鍵の管理方法を示す概略図）に記載の方法で紐付けしてリストとして保持しておくと、署名検証の際に、ｋｅｙＩＤｊに保存された値と一致する検証鍵リストのＩＤ（これをＩＤｉとする）に対応する検証鍵（これを検証鍵ｉとする）を効率的に検索することができるからである。
【０１８０】
図１７に戻り、ステップＳ９８では、検証処理部１５６は、ｏｕｔｐｕｔｄａｔａにエラーを示す−２０１を代入して、ステップＳ９７に進む。
【０１８１】
一方、ステップＳ９３では、検証処理部１５６は、ｉ≦ｎ≦２ｍであるか否かを判定し、ｉ≦ｎ≦２ｍが成立する場合（ステップＳ９３でＹｅｓ）にはステップＳ９４に進み、ｉ≦ｎ≦２ｍが成立しない場合（ステップＳ９３でＮｏ）にはステップＳ９９に進む。
【０１８２】
ステップＳ９９では、検証処理部１５６は、ｏｕｔｐｕｔｄａｔａにエラーを示す−２０１を代入して、ステップＳ９７に進む。
【０１８３】
一方、ステップＳ９４では、検証処理部１５６は、署名検証計算のために領域を動的確保し、領域確保に成功したか否か確認する。そして、検証処理部１５６は、領域確保に成功した場合（ステップＳ９４でＹｅｓ）にはステップＳ９５に進み、領域確保に失敗した場合（ステップＳ９４でＮｏ）にはステップＳ１００に進む。
【０１８４】
ステップＳ１００では、検証処理部１５６は、エラーを示す−１００を出力部１５９に出力して、処理を終了する。
【０１８５】
一方、ステップＳ９５では、検証処理部１５６は、図９に示すアルゴリズムを用いて（＊ｄａｔａ，ｄａｔａＬｅｎ［２］，ｓｉｇｎ［ｆＬｅｎ］，ｉｓｔａｔｅ＿ｐ）の署名検証を行う。
【０１８６】
そして、検証処理部１５６は、ステップＳ９４で確保した領域を解放する（Ｓ９６）。
【０１８７】
ステップＳ９７において、検証処理部１５６は、出力部１５９に正常終了を示す０を出力して、処理を終了する。
【０１８８】
本実施形態では、検証対象の署名が入力として与えられる場合についてのみ説明したが、映像データに署名データが付加されていない場合も起こり得る。例えば、検証装置１５０が図１に示すように他の装置とネットワークで繋がっていない状況下で、ユーザが、映像生成装置１１０、エンコーダ１２０、蓄積装置１３０、表示装置１４０の何れかの装置から映像データと署名データをＵＳＢメモリや外付けＨＤＤなどの外部記憶装置に取り出し、検証装置１５０へ移動する際に誤って署名を取り出さなかった場合、ユーザが署名を誤って削除してしまった場合などがある。
【０１８９】
このように映像データに署名データが付加されていない場合は、本実施形態に記載の署名検証関数を呼び出す上位関数が（例えば、検証処理部１５６が）、署名が付加されていないことを確認し、署名検証が行えないことを表示するように実現されていてもよい。
【０１９０】
図３に記載のハッシュ関数ｈとハッシュ関数Ｈは同一のハッシュ関数（例えばSHA-256など）でもよく、また、実システムへの適用時にはハッシュ関数Ｈと署名生成エンジンの部分をＲＳＡ−ＰＳＳ、ＥＣＤＳＡなどの署名方式に置き換えて使用してもよいことは第一の実施形態と同様である。
【０１９１】
なお、上記複数の映像データＭ１，・・・，Ｍｋ（ｋ＝２ｍ）の代わりに、各ｉ（１≦ｉ≦２ｍ）に対し、予め定められた値ｒｉ を用いてｍｉ＝Ｍｉ||ｒｉとし、ｍ１，・・・，ｍｋを複数のデータとして本実施形態に記載の方法で署名生成を行ってもよいことも第一の実施形態と同様である。
【０１９２】
また、本実施形態では、署名対象データを映像データとして説明したが、他のデータでもよいことも第一の実施形態と同様である。
【０１９３】
さらに、本実施形態において署名生成に使用する方式は、図１３のステップＳ８１で決定せず、予め使用する署名方式を決定しておき、ステップＳ７０でメッセージ＊Ｄａｔａｉｎｆｏや署名鍵ｉｓｔａｔｅ＿ｓなどと一緒に、上記使用する署名方式に対応する値を入力してもよい。
【０１９４】
また、以上の記載した実施形態において、署名検証の出力値や返り値（outputdata）は本実施形態に記載の値とは別の値でもよく、出力値や返り値をみて、どのようなエラーが出たのかを把握することができればよい。
【０１９５】
以上の通り、本実施形態の署名方式によれば、複数の映像データに対して、ハッシュ木の構造を用いて署名を生成し、署名検証に必要となるハッシュ値の添え字を計算することにより、複数の映像データからの任意抜粋保存に対応し、高い安全性と高い効率性を兼ね備えた署名生成や検証が可能になる。
【０１９６】
なお、上記各実施形態では、署名処理部１８９、２８９や検証処理部１５６を、ソフトウェアで実現するものとして説明したが、専用のハードウェアを用いて実現してもよい。また、数学関数計算部１９０、１５７を専用ハードウェアで実現しても良い。
【図面の簡単な説明】
【０１９７】
【図１】映像監視システムの概略図。
【図２】署名装置の概略図。
【図３】署名の生成処理を示す概略図。
【図４】コンピュータの概略図。
【図５】検証装置の概略図。
【図６】検証処理を示す概略図。
【図７】署名付き映像データを生成する処理を示すフローチャート。
【図８】署名に含めるハッシュ値を特定するための数列を算出する処理を示すフローチャート。
【図９】署名付き映像データの検証処理を示すフローチャート。
【図１０】署名の生成処理を示す概略図。
【図１１】検証処理を示す概略図。
【図１２】署名装置の概略図。
【図１３】署名装置での署名の生成処理を示すフローチャート。
【図１４】＊Ｄａｔａｉｎｆｏのフォーマットを示す概略図。
【図１５】署名格納用領域のフォーマットを示す概略図。
【図１６】ＩＤｉのフォーマットを示す概略図。
【図１７】検証処理を示すフローチャート。
【図１８】ｓ［ｉ］のフォーマットを示す概略図。
【図１９】検証鍵の管理方法を示す概略図。
【符号の説明】
【０１９８】
１００  映像監視システム
１１０  映像生成装置
１２０  エンコーダ
１３０  蓄積装置
１４０  表示装置
１５０  検証装置
１５１  記憶部
１５２  検証鍵記憶部
１５３  署名付きデータ記憶部
１５４  制御部
１５５  全体制御部
１５６  検証処理部
１５７  数学関数計算部
１５８  入力部
１５９  出力部
１８０  署名装置
１８１  記憶部
１８２  署名鍵記憶部
１８３  検証鍵記憶部
１８４  映像データ記憶部
１８５  署名付きデータ記憶部
１８６  制御部
１８７  全体制御部
１８８  映像処理部
１８９、２８９  署名処理部
１９０  数学関数計算部
【図１】
2009182864.tif 000003
【図２】
2009182864.tif 000004
【図３】
2009182864.tif 000005
【図４】
2009182864.tif 000006
【図５】
2009182864.tif 000007
【図６】
2009182864.tif 000008
【図７】
2009182864.tif 000009
【図８】
2009182864.tif 000010
【図９】
2009182864.tif 000011
【図１０】
2009182864.tif 000012
【図１１】
2009182864.tif 000013
【図１２】
2009182864.tif 000014
【図１３】
2009182864.tif 000015
【図１４】
2009182864.tif 000016
【図１５】
2009182864.tif 000017
【図１６】
2009182864.tif 000018
【図１７】
2009182864.tif 000019
【図１８】
2009182864.tif 000020
【図１９】
2009182864.tif 000021