(57)【要約】  （Ａ）において、入力データ（ｆ0）が取り込まれると、ハッシュ値（ｈ0）が算出される。ハッシュ値（ｈ0）は、優先度が最も高い記憶領域（Ｍ１）に格納される。（Ｂ）において、入力データ（ｆ1）が取り込まれると、ハッシュ値（ｈ1）が算出される。記憶領域（Ｍ１）には、すでにハッシュ値（ｈ0）が格納済みである。この場合、ハッシュ値（ｈ0）を記憶領域（Ｍ１）から読み出して記憶領域（Ｍ１）を空にする。そして、読み出したハッシュ値（ｈ0）とハッシュ値（ｈ1）とを結合して結合ハッシュ値（ｈ0｜ｈ1）とする。そして、ハッシュ値（ｈ0,1）が算出される。ハッシュ値（ｈ0,1）は、記憶領域（Ｍ１）のつぎに優先度が高い記憶領域（Ｍ２）に格納される。（Ｃ）において、入力データ（ｆ2）が取り込まれると、ハッシュ値（ｈ2）が算出される。ハッシュ値（ｈ2）は、５個の記憶領域のうち優先度が最も高い記憶領域（Ｍ１）に格納される。
2010097942.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
連続的に入力されてくる一連の入力データを入力順に取得する取得手段、
前記取得手段によって取得された入力データまたは対象データを一方向性関数に与えて前記入力データまたは前記対象データの固有値を演算する演算手段、
優先順位が割り当てられている記憶領域群の中から選ばれた対象領域が空き領域か否かを判断する判断手段、
前記判断手段によって前記対象領域が空き領域であると判断された場合、前記演算手段によって演算された前記入力データまたは前記対象データの固有値を前記対象領域に格納する格納手段、
前記判断手段によって前記対象領域が空き領域でないと判断された場合、前記対象領域内の格納済み固有値と前記入力データまたは前記対象データの固有値との結合固有値をあらたに前記対象データとして設定する設定手段、
前記入力データの固有値が演算された場合、前記記憶領域群の中から最優先される記憶領域を前記対象領域として選択するとともに、前記判断手段によって前記対象領域が空き領域でないと判断された場合、前記対象領域として選択された記憶領域の次に優先される記憶領域をあらたに前記対象領域として選択する選択手段、
前記一連の入力データの取得後、前記記憶領域群に格納されている固有値の数に基づいて、前記一連の入力データに対する電子署名の生成元となる固有値を決定する決定手段、
として機能させることを特徴とする電子署名プログラム。
【請求項２】
前記格納手段は、
前記一連の入力データの取得後、前記記憶領域群に格納されている固有値の数が複数である場合、当該複数の固有値を前記記憶領域群から退避先となる他の記憶領域に移動させ、
前記取得手段は、
前記他の記憶領域に退避させられた前記複数の固有値を、当該固有値について前記記憶領域群に割り当てられていた優先順位に従って取得し、
前記格納手段は、
前記判断手段によって前記対象領域が空き領域であると判断された場合、前記取得手段によって前記優先順位に従って前記他の記憶領域から取得された固有値または前記演算手段によって演算された前記対象データの固有値を前記対象領域に格納し、
前記設定手段は、
前記判断手段によって前記対象領域が空き領域でないと判断された場合、前記対象領域内の格納済み固有値と前記取得手段または前記演算手段によって得られた固有値との結合固有値をあらたに前記対象データとして設定し、
前記選択手段は、
前記記憶領域群の中から最優先される記憶領域を前記対象領域として選択するとともに、前記判断手段によって前記対象領域が空き領域でないと判断された場合、前記対象領域として選択された記憶領域の次に優先される記憶領域をあらたに前記対象領域として選択し、
前記決定手段は、
前記複数の固有値の取得後、前記記憶領域群に格納されている固有値の数に基づいて、前記一連の入力データに対する電子署名の生成元となる固有値を決定することを特徴とする請求項１に記載の電子署名プログラム。
【請求項３】
前記取得手段は、
前記記憶領域群（以下、「第１の記憶領域群」）と同一記憶領域数でかつ優先順位が割り当てられている第２の記憶領域群の中から選ばれた記憶領域を対象領域とし、前記一連の入力データの取得後、前記第１の記憶領域群に格納されている固有値の数が複数である場合、当該複数の固有値を前記第１の記憶領域群に割り当てられていた優先順位に従って取得し、
前記格納手段は、
前記判断手段によって前記対象領域が空き領域であると判断された場合、前記取得手段によって前記優先順位に従って前記第１の記憶領域群から取得された固有値または前記演算手段によって演算された前記対象データの固有値を前記対象領域に格納し、
前記設定手段は、
前記判断手段によって前記対象領域が空き領域でないと判断された場合、前記対象領域内の格納済み固有値と前記取得手段または前記演算手段によって得られた固有値との結合固有値をあらたに前記対象データとして設定し、
前記選択手段は、
前記第２の記憶領域群の中から最優先される記憶領域を前記対象領域として選択するとともに、前記判断手段によって前記対象領域が空き領域でないと判断された場合、前記対象領域として選択された記憶領域の次に優先される記憶領域をあらたに前記対象領域として選択し、
前記決定手段は、
前記複数の固有値の取得後、前記第２の記憶領域群に格納されている固有値の数に基づいて、前記一連の入力データに対する電子署名の生成元となる固有値を決定することを特徴とする請求項１に記載の電子署名プログラム。
【請求項４】
連続的に入力されてくる一連の入力データを入力順に取得する取得手段と、
前記取得手段によって取得された入力データまたは対象データを一方向性関数に与えて前記入力データまたは前記対象データの固有値を演算する演算手段と、
優先順位が割り当てられている記憶領域群の中から選ばれた対象領域が空き領域か否かを判断する判断手段と、
前記判断手段によって前記対象領域が空き領域であると判断された場合、前記演算手段によって演算された前記入力データまたは前記対象データの固有値を前記対象領域に格納する格納手段と、
前記判断手段によって前記対象領域が空き領域でないと判断された場合、前記対象領域内の格納済み固有値と前記入力データまたは前記対象データの固有値との結合固有値をあらたに前記対象データとして設定する設定手段と、
前記入力データの固有値が演算された場合、前記記憶領域群の中から最優先される記憶領域を前記対象領域として選択するとともに、前記判断手段によって前記対象領域が空き領域でないと判断された場合、前記対象領域として選択された記憶領域の次に優先される記憶領域をあらたに前記対象領域として選択する選択手段と、
前記一連の入力データの取得後、前記記憶領域群に格納されている固有値の数に基づいて、前記一連の入力データに対する電子署名の生成元となる固有値を決定する決定手段と、
を備えることを特徴とする電子署名装置。
【請求項５】
コンピュータが、
連続的に入力されてくる一連の入力データを入力順に取得する取得工程と、
前記取得工程によって取得された入力データまたは対象データを一方向性関数に与えて前記入力データまたは前記対象データの固有値を演算する演算工程と、
優先順位が割り当てられている記憶領域群の中から選ばれた対象領域が空き領域か否かを判断する判断工程と、
前記判断工程によって前記対象領域が空き領域であると判断された場合、前記演算工程によって演算された前記入力データまたは前記対象データの固有値を前記対象領域に格納する格納工程と、
前記判断工程によって前記対象領域が空き領域でないと判断された場合、前記対象領域内の格納済み固有値と前記入力データまたは前記対象データの固有値との結合固有値をあらたに前記対象データとして設定する設定工程と、
前記入力データの固有値が演算された場合、前記記憶領域群の中から最優先される記憶領域を前記対象領域として選択するとともに、前記判断工程によって前記対象領域が空き領域でないと判断された場合、前記対象領域として選択された記憶領域の次に優先される記憶領域をあらたに前記対象領域として選択する選択工程と、
前記一連の入力データの取得後、前記記憶領域群に格納されている固有値の数に基づいて、前記一連の入力データに対する電子署名の生成元となる固有値を決定する決定工程と、
を実行することを特徴とする電子署名方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示技術は、電子署名に用いられるハッシュツリーの生成をおこなう電子署名プログラム、電子署名装置、および電子署名方法に関する。
【背景技術】
【０００２】
署名対象となる動画像または音声のストリーミングデータを分割し、分割された部分データをリーフとしてハッシュツリーを生成してルートハッシュ値を求めることで、ストリーミングデータの電子署名をおこなう技術が開示されている（たとえば、下記特許文献１を参照。）。上述した従来技術では、分割されたデータが保持できるレジスタ／メモリが用意されていることが前提となる。【０００３】
図１１は、従来のハッシュツリー作成方法を示す説明図である。ストリーミングデータは、複数の部分データに分割される。ＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）−１のストリーミングデータを抽出可能なように部分データに分割する場合、画像単位とＧＯＰ（Ｇｒｏｕｐ  ｏｆ  Ｐｉｃｔｕｒｅ）単位が考えられる。ＧＯＰは、何枚かの画像をまとめた動画像の最小単位であり、その単位で独立した再生が可能であり、動画像を途中から再生したり編集したりするための構造である。ここでは、単純化のために、部分データへの分割をＧＯＰ単位とする。【０００４】
図１１の（Ａ）において、ストリーミングデータは入力データｆ0〜ｆ14に分割され、それぞれハッシュ関数Ｈ（）に与えられることで、ハッシュ値ｈ0〜ｈ14がレジスタ／メモリに格納される。【０００５】
（Ｂ）において、（Ａ）で得られたハッシュ値ｈ0〜ｈ14について隣接ハッシュ値どうしを結合する。“ｈｘ｜ｈｙ”（ｘ，ｙは番号）は、ハッシュ値ｈｘの末尾とハッシュ値ｈｙの先頭をつなげた符号列である。また、ｈｘ，ｙは結合ハッシュ値をハッシュ関数に与えた場合に得られるハッシュ値である。（Ｃ）〜（Ｅ）においても同様に繰り返す。（Ｅ）において、ハッシュ値が単一になったため、ハッシュ値ｈ0,14がルートハッシュ値となる。【０００６】
このように、従来技術では、（Ａ）〜（Ｅ）のハッシュツリー生成をおこなうには、ストリーミングデータをすべて取り込むことが可能な大容量のレジスタ／メモリが必要となる。また、ストリーミングデータをすべて取り込んだあとに、（Ａ）〜（Ｅ）のハッシュツリー生成をおこなうため、処理に時間を要することとなる。【０００７】
【特許文献１】特開２００８−１７８０４８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本開示技術では、リアルタイムでツリー生成の逐次処理を可能とすることにより、レジスタ／メモリの大幅削減と後処理時間の大幅削減を実現することを課題とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するため、本開示技術は、連続的に入力されてくる一連の入力データを入力順に取得し、取得された入力データまたは対象データを一方向性関数に与えて前記入力データまたは前記対象データの固有値を演算し、優先順位が割り当てられている記憶領域群の中から選ばれた対象領域が空き領域か否かを判断し、前記対象領域が空き領域であると判断された場合、演算された前記入力データまたは前記対象データの固有値を前記対象領域に格納し、前記対象領域が空き領域でないと判断された場合、前記対象領域内の格納済み固有値と前記入力データまたは前記対象データの固有値との結合固有値をあらたに前記対象データとして設定し、前記入力データの固有値が演算された場合、前記記憶領域群の中から最優先される記憶領域を前記対象領域として選択するとともに、前記対象領域が空き領域でないと判断された場合、前記対象領域として選択された記憶領域の次に優先される記憶領域をあらたに前記対象領域として選択し、前記一連の入力データの取得後、前記記憶領域群に格納されている固有値の数に基づいて、前記一連の入力データに対する電子署名の生成元となる固有値を決定することを要件とする。
【発明の効果】
【００１０】
本開示技術によれば、リアルタイムでツリー生成の逐次処理を可能とすることにより、レジスタ／メモリの大幅削減と後処理時間の大幅削減を実現することができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】電子署名装置のハードウェア構成を示すブロック図である。
【図２】入力データ群の一例を示す説明図である。
【図３−１】第１の格納処理（その１）を示す説明図である。
【図３−２】第１の格納処理（その２）を示す説明図である。
【図３−３】第１の格納処理（その３）を示す説明図である。
【図３−４】第１の格納処理（その４）を示す説明図である。
【図３−５】第１の格納処理（その５）を示す説明図である。
【図４−１】第２の格納処理（その１）を示す説明図である。
【図４−２】第２の格納処理（その２）を示す説明図である。
【図５】第１の格納処理および第２の格納処理の実行により生成されたハッシュツリーを示す説明図である。
【図６】本実施の形態にかかる電子署名装置の機能的構成を示すブロック図である。
【図７】本実施の形態にかかるルートハッシュ値生成処理手順を示すフローチャートである。
【図８】第１の格納処理の詳細な処理手順を示すフローチャートである。
【図９】第２の格納処理の詳細な処理手順を示すフローチャートである。
【図１０】本実施の形態と図１１に示した従来技術とを比較した図表である。
【図１１】従来のハッシュツリー作成方法を示す説明図である。
【発明を実施するための最良の形態】
【００１２】
以下に添付図面を参照して、本開示技術にかかる電子署名装置、電子署名方法、および電子署名プログラムの好適な実施の形態を詳細に説明する。【００１３】
（電子署名装置のハードウェア構成）
図１は、電子署名装置のハードウェア構成を示すブロック図である。電子署名装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０１と、メモリ１０２と、ハードディスクドライブ１０３と、Ｉ／Ｆ１０４（インターフェース）と、を備えている。ＣＰＵ１０１、メモリ１０２、ハードディスクドライブ１０３、およびＩ／Ｆ１０４は、バス１０５により接続されている。【００１４】
ここで、ＣＰＵ１０１は、電子署名装置１００の全体の制御を司る。ＣＰＵ１０１は内部にレジスタ１０６を有する。レジスタ１０６は、各種データを保持する。レジスタ１０６は、ＣＰＵ１０１の外部にあってもよい。メモリ１０２は、各種データを記憶する主記憶装置である。メモリ１０２は、ＣＰＵ１０１のワークエリアとしても利用される。メモリ１０２は、たとえば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、フラッシュメモリなどにより構成される。【００１５】
ハードディスクドライブ１０３は、各種データを記憶するハードディスクを有する。ハードディスクには、本開示技術の電子署名プログラム（メモリ１０２に記憶してもよい）やブラウザ、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）を記憶する。Ｉ／Ｆ１０４は、外部の装置（たとえば、デジタルビデオカメラ１０８）やネットワーク１０９からデータを取得したり、外部の装置やネットワーク１０９へデータを出力する。Ｉ／Ｆ１０４は、バッファ１０７を有し、外部の装置やネットワーク１０９からのデータを一時的に保持して、レジスタ１０６、メモリ１０２、ハードディスクなどの記憶領域にデータを送る。【００１６】
図２は、入力データ群の一例を示す説明図である。図２において、署名対象となる動画像または音声のストリーミングデータＳＴは、複数の入力データｆ0〜ｆ14に分割される。図１１に示したように、説明の単純化のために、入力データｆ0〜ｆ14への分割をＧＯＰ単位とする。各入力データｆ0〜ｆ14のハッシュ値について２分木処理を施すことで、最終的にルートハッシュ値ｈ0,14が得られ、電子署名２００が生成されることとなる。【００１７】
（ハッシュツリー生成の具体例）
つぎに、本実施の形態におけるハッシュツリー生成の具体例について説明する。本実施の形態のハッシュツリー生成は、大きく分けて２つのフェーズからなる。第１のフェーズは、ストリーミングデータから分割された一連の入力データから得られるハッシュ値を、優先順位が割り当てられた記憶領域群から順次選ばれた対象領域に格納する。以降、第１の格納処理と称す。【００１８】
第２のフェーズは、第１の格納処理でハッシュツリーが未完成である場合に、再度第１の格納処理を実行させる。以降、第２の格納処理という。第２の格納処理は、ハッシュ値が単一になるまで繰り返し実行される。なお、記憶領域群とは、一方向性関数（たとえば、ハッシュ関数）から得られた固有値を格納する複数の記憶領域である。記憶領域群は、たとえば、複数個のレジスタ１０６でもよく、メモリ１０２やハードディスクドライブ１０３のハードディスクにおいてアドレス指定された複数の記憶領域でもよい。【００１９】
以降、図２に示した入力データ群を例にして説明する。図３−１〜図３−５では第１の格納処理を説明し、図４−１，図４−２では第２の格納処理を説明する。なお、複数の記憶領域として５個の記憶領域Ｍ１〜Ｍ５を設定する。記憶領域群Ｍには、優先順位が割り当てられているため、ここでは、右端の記憶領域Ｍ１が最も優先度が高い記憶領域であり、左に行くほど優先度が下がり、左端の記憶領域Ｍ５が最も優先度が低い記憶領域とする。また、一連の入力データは、入力データｆ0，ｆ1，ｆ2，…，ｆ14の順に取り込まれるものとする。【００２０】
図３−１は、第１の格納処理（その１）を示す説明図である。（Ａ）は初期状態であるため、５個の記憶領域Ｍ１〜Ｍ５は空である。入力データｆ0が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ0が算出される。ハッシュ値ｈ0は、５個の記憶領域のうち優先度が最も高い記憶領域Ｍ１に格納される。【００２１】
（Ｂ）において、記憶領域Ｍ１には、ハッシュ値ｈ0が格納されている。入力データｆ1が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ1が算出される。記憶領域Ｍ１には、すでにハッシュ値ｈ0が格納済みである。この場合、ハッシュ値ｈ0を記憶領域Ｍ１から読み出して記憶領域Ｍ１を空にする。そして、読み出したハッシュ値ｈ0とハッシュ値ｈ1とを結合して結合ハッシュ値ｈ0｜ｈ1とする。結合ハッシュ値ｈ0｜ｈ1は、ハッシュ値ｈ0の末尾とハッシュ値ｈ1の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ0｜ｈ1をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ0,1が算出される。ハッシュ値ｈ0,1は、記憶領域Ｍ１のつぎに優先度が高い記憶領域Ｍ２に格納される。【００２２】
（Ｃ）において、記憶領域Ｍ２には、ハッシュ値ｈ0,1が格納されている。入力データｆ2が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ2が算出される。ハッシュ値ｈ2は、５個の記憶領域のうち優先度が最も高い記憶領域Ｍ１に格納される。【００２３】
図３−２は、第１の格納処理（その２）を示す説明図である。（Ｄ）において、記憶領域Ｍ１にはハッシュ値ｈ2が格納されており、記憶領域Ｍ２にはハッシュ値ｈ0,1が格納されている。入力データｆ3が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ3が算出される。記憶領域Ｍ１には、すでにハッシュ値ｈ2が格納済みである。【００２４】
この場合、ハッシュ値ｈ2を記憶領域Ｍ１から読み出して記憶領域Ｍ１を空にする。そして、読み出したハッシュ値ｈ2とハッシュ値ｈ3とを結合して結合ハッシュ値ｈ2｜ｈ3とする。結合ハッシュ値ｈ2｜ｈ3は、ハッシュ値ｈ2の末尾とハッシュ値ｈ3の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ2｜ｈ3をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ2,3が算出される。【００２５】
ところが、記憶領域Ｍ１のつぎに優先度が高い記憶領域Ｍ２には、すでにハッシュ値ｈ０，１が格納済みである。この場合、ハッシュ値ｈ0,1を記憶領域Ｍ２から読み出して記憶領域Ｍ２を空にする。そして、読み出したハッシュ値ｈ0,1とハッシュ値ｈ2,3とを結合して結合ハッシュ値ｈ0,1｜ｈ2,3とする。結合ハッシュ値ｈ0,1｜ｈ2,3は、ハッシュ値ｈ0,1の末尾とハッシュ値ｈ2,3の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ0,1｜ｈ2,3をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ0,3が算出される。ハッシュ値ｈ0,3は、記憶領域Ｍ２のつぎに優先度が高い記憶領域Ｍ３に格納される。【００２６】
（Ｅ）において、記憶領域Ｍ３には、ハッシュ値ｈ0,3が格納されている。入力データｆ4が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ4が算出される。ハッシュ値ｈ4は、５個の記憶領域のうち優先度が最も高い記憶領域Ｍ１に格納される。【００２７】
（Ｆ）において、記憶領域Ｍ１にはハッシュ値ｈ4が格納されており、記憶領域Ｍ３にはハッシュ値ｈ0,3が格納されている。入力データｆ5が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ5が算出される。記憶領域Ｍ１には、すでにハッシュ値ｈ4が格納済みである。【００２８】
この場合、ハッシュ値ｈ4を記憶領域Ｍ１から読み出して記憶領域Ｍ１を空にする。そして、読み出したハッシュ値ｈ4とハッシュ値ｈ5とを結合して結合ハッシュ値ｈ4｜ｈ5とする。結合ハッシュ値ｈ4｜ｈ5は、ハッシュ値ｈ4の末尾とハッシュ値ｈ5の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ4｜ｈ5をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ4,5が算出される。ハッシュ値ｈ4,5は、記憶領域Ｍ１のつぎに優先度が高い記憶領域Ｍ２に格納される。【００２９】
図３−３は、第１の格納処理（その３）を示す説明図である。（Ｇ）において、記憶領域Ｍ２にはハッシュ値ｈ4,5が格納されており、記憶領域Ｍ３にはハッシュ値ｈ0,3が格納されている。入力データｆ6が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ6が算出される。ハッシュ値ｈ6は、５個の記憶領域のうち優先度が最も高い記憶領域Ｍ１に格納される。【００３０】
（Ｈ）において、記憶領域Ｍ１にはハッシュ値ｈ6が格納されており、記憶領域Ｍ２にはハッシュ値ｈ4,5が格納されている。記憶領域Ｍ３には結合ハッシュ値ｈ0,3が格納されている。入力データｆ7が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ7が算出される。記憶領域Ｍ１には、すでにハッシュ値ｈ6が格納済みである。【００３１】
この場合、ハッシュ値ｈ6を記憶領域Ｍ１から読み出して記憶領域Ｍ１を空にする。そして、読み出したハッシュ値ｈ6とハッシュ値ｈ7とを結合して結合ハッシュ値ｈ6｜ｈ7とする。結合ハッシュ値ｈ6｜ｈ7は、ハッシュ値ｈ6の末尾とハッシュ値ｈ7の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ6｜ｈ7をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ6,7が算出される。【００３２】
ところが、記憶領域Ｍ１のつぎに優先度が高い記憶領域Ｍ２には、すでにハッシュ値ｈ4,5が格納済みである。この場合、ハッシュ値ｈ4,5を記憶領域Ｍ２から読み出して記憶領域Ｍ２を空にする。そして、読み出したハッシュ値ｈ4,5とハッシュ値ｈ6,7とを結合して結合ハッシュ値ｈ4,5｜ｈ6,7とする。結合ハッシュ値ｈ4,5｜ｈ6,7は、ハッシュ値ｈ4,5の末尾とハッシュ値ｈ6,7の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ4,5｜ｈ6,7をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ4,7が算出される。【００３３】
ところが、記憶領域Ｍ２のつぎに優先度が高い記憶領域Ｍ３には、すでにハッシュ値ｈ0,3が格納済みである。この場合、ハッシュ値ｈ0,3を記憶領域Ｍ３から読み出して記憶領域Ｍ３を空にする。そして、読み出したハッシュ値ｈ0,3とハッシュ値ｈ4,7とを結合して結合ハッシュ値ｈ0,3｜ｈ4,7とする。結合ハッシュ値ｈ0,3｜ｈ4,7は、ハッシュ値ｈ0,3の末尾とハッシュ値ｈ4,7の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ0,3｜ｈ4,7をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ0,7が算出される。そして、ハッシュ値ｈ0,7は、記憶領域Ｍ３のつぎに優先度が高い記憶領域Ｍ４に格納される。【００３４】
（Ｉ）において、記憶領域Ｍ４にはハッシュ値ｈ0,7が格納されている。入力データｆ8が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ8が算出される。ハッシュ値ｈ8は、５個の記憶領域のうち優先度が最も高い記憶領域Ｍ１に格納される。【００３５】
図３−４は、第１の格納処理（その４）を示す説明図である。（Ｊ）において、記憶領域Ｍ１にはハッシュ値ｈ8が格納されており、記憶領域Ｍ４にはハッシュ値ｈ0,7が格納されている。入力データｆ9が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ9が算出される。記憶領域Ｍ１には、すでにハッシュ値ｈ8が格納済みである。【００３６】
この場合、ハッシュ値ｈ8を記憶領域Ｍ１から読み出して記憶領域Ｍ１を空にする。そして、読み出したハッシュ値ｈ8とハッシュ値ｈ9とを結合して結合ハッシュ値ｈ8｜ｈ9とする。結合ハッシュ値ｈ8｜ｈ9は、ハッシュ値ｈ8の末尾とハッシュ値ｈ9の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ8｜ｈ9をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ8,9が算出される。ハッシュ値ｈ8,9は、記憶領域Ｍ１のつぎに優先度が高い記憶領域Ｍ２に格納される。【００３７】
（Ｋ）において、記憶領域Ｍ２にはハッシュ値ｈ8,9が格納されており、記憶領域Ｍ４にはハッシュ値ｈ0,7が格納されている。入力データｆ10が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ10が算出される。ハッシュ値ｈ10は、５個の記憶領域のうち優先度が最も高い記憶領域Ｍ１に格納される。【００３８】
（Ｌ）において、記憶領域Ｍ１にはハッシュ値ｈ10が格納されており、記憶領域Ｍ２にはハッシュ値ｈ8,9が格納されており、記憶領域Ｍ４にはハッシュ値ｈ0,7が格納されている。入力データｆ11が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ11が算出される。記憶領域Ｍ１には、すでにハッシュ値ｈ10が格納済みである。【００３９】
この場合、ハッシュ値ｈ10を記憶領域Ｍ１から読み出して記憶領域Ｍ１を空にする。そして、読み出したハッシュ値ｈ10とハッシュ値ｈ11とを結合して結合ハッシュ値ｈ10｜ｈ11とする。結合ハッシュ値ｈ10｜ｈ11は、ハッシュ値ｈ10の末尾とハッシュ値ｈ11の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ10｜ｈ11をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ10,11が算出される。【００４０】
ところが、記憶領域Ｍ１のつぎに優先度が高い記憶領域Ｍ２には、すでにハッシュ値ｈ8,9が格納済みである。この場合、ハッシュ値ｈ8,9を記憶領域Ｍ２から読み出して記憶領域Ｍ２を空にする。そして、読み出したハッシュ値ｈ8,9とハッシュ値ｈ10,11とを結合して結合ハッシュ値ｈ8｜ｈ11とする。結合ハッシュ値ｈ8｜ｈ11は、ハッシュ値ｈ8,9の末尾とハッシュ値ｈ10,11の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ8｜ｈ11をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ8,11が算出される。ハッシュ値ｈ8,11は、記憶領域Ｍ２のつぎに優先度が高い記憶領域Ｍ３に格納される。【００４１】
図３−５は、第１の格納処理（その５）を示す説明図である。（Ｍ）において、記憶領域Ｍ３にはハッシュ値ｈ8,11が格納されており、記憶領域Ｍ４にはハッシュ値ｈ0,7が格納されている。入力データｆ12が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ12が算出される。ハッシュ値ｈ12は、５個の記憶領域Ｍ１〜Ｍ５のうち優先度が最も高い記憶領域Ｍ１に格納される。【００４２】
（Ｎ）において、記憶領域Ｍ１にはハッシュ値ｈ12が格納されており、記憶領域Ｍ３にはハッシュ値ｈ8,11が格納されており、記憶領域Ｍ４にはハッシュ値ｈ0,7が格納されている。入力データｆ13が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ13が算出される。記憶領域Ｍ１には、すでにハッシュ値ｈ12が格納済みである。【００４３】
この場合、ハッシュ値ｈ12を記憶領域Ｍ１から読み出して記憶領域Ｍ１を空にする。そして、読み出したハッシュ値ｈ12とハッシュ値ｈ13とを結合して結合ハッシュ値ｈ12｜ｈ13とする。結合ハッシュ値ｈ12｜ｈ13は、ハッシュ値ｈ12の末尾とハッシュ値ｈ13の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ12｜ｈ13をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ12,13が算出される。ッシュ値ｈ12,13は、記憶領域Ｍ１のつぎに優先度が高い記憶領域Ｍ２に格納される。【００４４】
（Ｏ）において、記憶領域Ｍ２には結合ハッシュ値ｈ12,13が格納されており、記憶領域Ｍ３にはハッシュ値ｈ8,11が格納されており、記憶領域Ｍ４にはハッシュ値ｈ0,7が格納されている。最後の入力データｆ14が取り込まれると、ハッシュ関数Ｈ（）により、ハッシュ値ｈ14が算出される。ハッシュ値ｈ14は、５個の記憶領域のうち優先度が最も高い記憶領域Ｍ１に格納される。【００４５】
これにより、一連の入力データｆ0〜ｆ14が取り込まれると、記憶領域Ｍ１にはハッシュ値ｈ14が格納され、記憶領域Ｍ２にはハッシュ値ｈ12,13が格納され、記憶領域Ｍ３にはハッシュ値ｈ8,11が格納され、記憶領域Ｍ４にはハッシュ値ｈ0,7が格納された状態となる。そして、第２の格納処理（第２のフェーズ）に移行する。【００４６】
図４−１は、第２の格納処理（その１）を示す説明図である。（Ｐ）において、記憶領域群に格納されているハッシュ値ｈ14，ｈ12,13，ｈ8,11，ｈ0,7を他の記憶領域に退避させ、記憶領域群Ｍを空にする。退避先の記憶領域Ｎは、記憶領域群Ｍと同等のサイズであればよい。（Ｑ）以降では、退避先の記憶領域Ｎから、記憶領域群Ｍで格納されていた記憶領域Ｍｊの優先順位ｊ順に取り込まれる。具体的には、ハッシュ値ｈ14，ｈ12,13，ｈ8,11，ｈ0,7の順に取り込まれることとなる。【００４７】
（Ｑ）では５個の記憶領域は空である。ハッシュ値ｈ14が取り込まれると、５個の記憶領域のうち優先度が最も高い記憶領域Ｍ１に格納される。【００４８】
（Ｒ）において、記憶領域Ｍ１には、ハッシュ値ｈ14が格納されている。ハッシュ値ｈ12,13が取り込まれると、ハッシュ値ｈ14を記憶領域Ｍ１から読み出して記憶領域Ｍ１を空にする。そして、読み出したハッシュ値ｈ14とハッシュ値ｈ12,13とを結合して結合ハッシュ値ｈ12｜ｈ14とする。結合ハッシュ値ｈ12,13｜ｈ14は、ハッシュ値ｈ12，13の末尾とハッシュ値ｈ14の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ12,13｜ｈ14をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ12,14が算出される。ハッシュ値ｈ12,14は、記憶領域Ｍ１のつぎに優先度が高い記憶領域Ｍ２に格納される。【００４９】
図４−２は、第２の格納処理（その２）を示す説明図である。（Ｓ）において、記憶領域Ｍ２には、ハッシュ値ｈ12,14が格納されている。ハッシュ値ｈ8,11が取り込まれると、５個の記憶領域のうち優先度が最も高い記憶領域Ｍ１に格納される。【００５０】
（Ｔ）において、記憶領域Ｍ１にはハッシュ値ｈ8,11が格納されており、記憶領域Ｍ２にはハッシュ値ｈ12,14が格納されている。最後のハッシュ値ｈ0,7が取り込まれると、ハッシュ値ｈ8,11を記憶領域Ｍ１から読み出して記憶領域Ｍ１を空にする。そして、読み出したハッシュ値ｈ8,11とハッシュ値ｈ0,7とを結合して結合ハッシュ値ｈ0,7｜ｈ8,11とする。結合ハッシュ値ｈ0,7｜ｈ8,11は、ハッシュ値ｈ0,7の末尾とハッシュ値ｈ8,11の先頭とをつなげたコード列である。そして、結合ハッシュ値ｈ0,7｜ｈ8,11をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ0,11が算出される。【００５１】
ところが、記憶領域Ｍ１のつぎに優先度が高い記憶領域Ｍ２には、すでにハッシュ値ｈ12,14が格納済みである。この場合、ハッシュ値ｈ12,14を記憶領域Ｍ２から読み出して記憶領域Ｍ２を空にする。そして、読み出したハッシュ値ｈ12,14とハッシュ値ｈ0,11とを結合して結合ハッシュ値ｈ0,11｜ｈ12,14とする。結合ハッシュ値ｈ0,11｜ｈ12,14は、ハッシュ値ｈ0,11の末尾とハッシュ値ｈ12,14の先頭とをつなげたコード列である。【００５２】
そして、結合ハッシュ値ｈ0,11｜ｈ12,14をハッシュ関数Ｈ（）に与えて、ハッシュ値ｈ0,14が算出される。ハッシュ値ｈ0,14は、記憶領域Ｍ２のつぎに優先度が高い記憶領域Ｍ３に格納される。退避先の記憶領域Ｎにはハッシュ値がなく、記憶領域群Ｍには単一のハッシュ値ｈ0,14が残存するため、ハッシュ値ｈ0,14がルートハッシュ値となる。【００５３】
図５は、第１の格納処理および第２の格納処理の実行により生成されたハッシュツリーを示す説明図である。符号５０１〜５０４でそれぞれ囲まれた領域が、第１の格納処理で得られたハッシュツリーを示している。また、符号５０５で囲まれた領域が、第２の格納処理で得られたハッシュツリーを示している。【００５４】
（電子署名装置１００の機能的構成）
図６は、本実施の形態にかかる電子署名装置１００の機能的構成を示すブロック図である。図６において、電子署名装置１００は、取得部６０１と、演算部６０２と、判断部６０３と、格納部６０４と、設定部６０５と、選択部６０６と、決定部６０７とを含む構成である。この制御部となる機能（取得部６０１〜決定部６０７）は、具体的には、たとえば、図１に示したレジスタ１０６、メモリ１０２、ハードディスクドライブ１０３などの記憶装置に記憶されたプログラムをＣＰＵ１０１に実行させることにより、または、Ｉ／Ｆ１０４により、その機能を実現する。【００５５】
取得部６０１は、連続的に入力されてくる一連の入力データｆ0〜ｆ14を入力順に取得する機能を有する。具体的には、たとえば、動画像や音声などのストリーミングデータＳＴをＧＯＰ単位で分割した入力データ群ｆ0〜ｆ14をＩ／Ｆ１０４で順次取り込み、Ｉ／Ｆ１０４のバッファ１０７から入力順で出力されたデータを取り込む。【００５６】
演算部６０２は、取得部６０１によって入力データｆi（ｉはｉ番目の入力の意味）が取得される都度、入力データｆiを一方向性関数に与えて入力データｆiの固有値を演算する機能を有する。また、後述する設定部６０５によって設定された対象データを一方向性関数に与えて対象データの固有値を演算する機能を有する。対象データについては後述する。一方向性関数とは、与えられたデータ固有の特徴量（固有値）を出力する関数である。たとえば、ハッシュ関数Ｈ（）である。ハッシュ関数Ｈ（）は、与えられたデータ固有のハッシュ値を算出する。【００５７】
判断部６０３は、優先順位が割り当てられている記憶領域群Ｍの中から選ばれた対象領域が空き領域か否かを判断する機能を有する。記憶領域群Ｍとは、演算部６０２から得られたハッシュ値を格納する複数の記憶領域Ｍ１〜Ｍ５である。たとえば、複数個のレジスタ１０６でもよく、メモリ１０２やハードディスクドライブ１０３においてアドレス指定された複数の記憶領域でもよい。対象領域とは、後述する選択部６０６によって選択された記憶領域Ｍｊである。たとえば、図３−１の（Ａ）に示したように、対象領域である記憶領域Ｍ１にはどのハッシュ値も格納されていないため、空であると判断する。一方、図３−１の（Ｂ）に示したように、対象領域である記憶領域Ｍ１にハッシュ値ｈ０が格納済みであるため、空でないと判断する。【００５８】
格納部６０４は、判断部６０３によって対象領域が空き領域であると判断された場合、演算部６０２によって演算された入力データｆiまたは対象データの固有値を対象領域に格納する機能を有する。空き領域であれば、そのまま固有値を格納する。たとえば、図３−１の（Ａ）に示したように、対象領域である記憶領域Ｍ１は空と判断されるため、ハッシュ値ｈ0を格納する。一方、空き領域でない場合については、後述する。【００５９】
設定部６０５は、判断部６０３によって対象領域が空き領域でないと判断された場合、対象領域内の格納済み固有値と入力データｆiまたは対象データの固有値との結合固有値をあらたに対象データとして設定する機能を有する。具体的には、対象領域が空き領域でない場合は、格納済み固有値との２分木処理を実行する。【００６０】
すなわち、現時点での対象データの固有値と対象領域内の格納済み固有値との結合固有値ｈｘ｜ｈｙを生成する。“ｈｘ｜ｈｙ”（ｘ，ｙは番号でｘ＜ｙ）は、固有値ｈｘの末尾と固有値ｈｙの先頭をつなげた符号列である。また、ｈｘ，ｙは結合固有値を一方向性関数に与えた場合に得られるあらたな固有値である。このように、結合固有値も対象データとなるため、演算部６０２に渡されてその固有値が演算されることとなる。【００６１】
たとえば、図３−１の（Ｂ）に示したように、対象領域である記憶領域Ｍ１にはすでにハッシュ値ｈ0が格納済みであるため、ハッシュ値ｈ0とハッシュ値ｈ1とを結合して結合ハッシュ値ｈ0｜ｈ1を生成して、対象データに設定する。結合ハッシュ値ｈ0｜ｈ1は対象データであるため、上述した演算部６０２に渡されてハッシュ値ｈ0,1が算出される。【００６２】
選択部６０６は、入力データｆiの固有値が演算された場合、記憶領域群Ｍの中から最優先される記憶領域を対象領域として選択する機能を有する。具体的には、入力データｆiの固有値が得られると、最も優先度が高い記憶領域が対象領域となる。【００６３】
また、選択部６０６は、判断部６０３によって対象領域が空き領域でないと判断された場合、対象領域として選択された記憶領域の次に優先される記憶領域をあらたに対象領域として選択する機能を有する。これにより、次の格納先を確保することができる。たとえば、図３−１の（Ｂ）に示したように、対象領域である記憶領域Ｍ１にはすでにハッシュ値ｈ0が格納済みであるため、次に優先度が高い記憶領域Ｍ２が対象領域に選択される。そして、対象領域である空の記憶領域Ｍ２にハッシュ値ｈ0,1が格納されることとなる。【００６４】
決定部６０７は、一連の入力データｆ0〜ｆ14の取得後、記憶領域群Ｍに格納されている固有値の数に基づいて、一連の入力データｆ0〜ｆ14に対する電子署名の生成元となる固有値を決定する機能を有する、具体的には、たとえば、記憶領域群Ｍに単一の固有値が残存する場合は、その単一の固有値がルートとなる。したがって、一連の入力データｆ0〜ｆ14に対する電子署名の生成元となる。一方、固有値が複数残存している場合、ハッシュツリーが未完成である。この場合、第２の格納処理（図４−１および図４−２を参照）を実行することとなる。第２の格納処理への移行に際し、２通りの移行方法がある。【００６５】
１つ目の移行方法は、図４−１および図４−２に示したように、記憶領域群Ｍとは異なる他の記憶領域を退避先の記憶領域Ｎとして、記憶領域群Ｍに格納されているハッシュ値群を退避先の記憶領域Ｎに移動させる。そして、記憶領域群Ｍの各記憶領域Ｍ１〜Ｍ５の優先度にしたがって、退避先の記憶領域Ｎから順次ハッシュ値を取り出す。【００６６】
この場合、選択部６０６では、記憶領域群Ｍのうち優先度が最も高い記憶領域Ｍ１を対象領域に選択する。そして、判断部６０３では対象領域が空きであるか否かを判断し、空きであれば退避先の記憶領域から取り出したハッシュ値をそのまま格納する。空きでない場合、上述したように、格納済みハッシュ値との結合ハッシュ値を生成して対象データとする。【００６７】
そして、次に優先度が高い記憶領域Ｍ２を対象領域に選択し、判断部６０３により、選択された対象領域が空きか否かを判断する。このあと、結合ハッシュ値をハッシュ関数Ｈ（）に与えてあらたなハッシュ値を算出する。あらたに選択された対象領域（記憶領域Ｍ２）が空きであれば、あらたなハッシュ値が格納される。空きでなければ、対象領域の選択および空きの判断、結合ハッシュ値の生成、対象データの設定、格納を繰り返す。【００６８】
２つ目の移行方法は、記憶領域群（以下、第１の記憶領域群）Ｍと同等の第２の記憶領域群Ｍを用意しておく。すなわち、第２の記憶領域群Ｍは、第１の記憶領域群Ｍと同数かつ同サイズの記憶領域を有し、第１の記憶領域群Ｍと同じように各記憶領域Ｍ１〜Ｍ５に優先順位が割り当てられている。この場合、取得部６０１では、第１の記憶領域群Ｍの中からハッシュ値が格納されている優先順位が最も高い記憶領域から順次ハッシュ値を取り出すこととなる。そして、選択部６０６は、第２の記憶領域群Ｍの中から対象領域を選択し、判断部６０３はその対象領域が空きか否かを判断し、格納部６０４は空きである場合にハッシュ値を格納することとなる。いずれの移行方法であっても、追加で利用される記憶領域は記憶領域群Ｍのサイズと同等であるため、省メモリ化を図ることができる。【００６９】
（ルートハッシュ値生成処理手順）
図７は、本実施の形態にかかるルートハッシュ値生成処理手順を示すフローチャートである。まず、第１の格納処理を実行し（ステップＳ７０１）、第１の格納処理後のハッシュ値の数が単一であるか否かを判断する（ステップＳ７０２）。単一でない場合（ステップＳ７０２：Ｎｏ）、第２の格納処理を実行し（ステップＳ７０３）、再度、ハッシュ値の数が単一であるか否かを判断する（ステップＳ７０２）。単一でなければ（ステップＳ７０２：Ｎｏ）、単一になるまで第２の格納処理（ステップＳ７０３）を実行し続けることとなる。【００７０】
一方、ステップＳ７０２において、単一である場合（ステップＳ７０２：Ｙｅｓ）、単一のハッシュ値をルートハッシュ値に決定し（ステップＳ７０４）、ルートハッシュ値と入力データ群とを関連付けて保存する（ステップＳ７０５）。これにより、ルートハッシュ値生成処理を終了する。【００７１】
図８は、第１の格納処理（ステップＳ７０１）の詳細な処理手順を示すフローチャートである。まず、入力データｆiの入力順を示す変数ｉをｉ＝０、記憶領域Ｍｊの優先度を示す変数ｊをｊ＝１とし（ステップＳ８０１）、入力データｆiがあるか否かを判断する（ステップＳ８０２）。入力データｆiがある場合（ステップＳ８０２：Ｙｅｓ）、取得部６０１により、入力データｆiを取得し（ステップＳ８０３）、演算部６０２により、入力データｆiのハッシュ値ｈｙを算出する（ステップＳ８０４）。そして、判断部６０３により、記憶領域Ｍｊが空であるか否かを判断する（ステップＳ８０５）。【００７２】
空である場合（ステップＳ８０５：Ｙｅｓ）、格納部６０４により、未格納ハッシュ値ｈｙを記憶領域Ｍｊに格納する（ステップＳ８０６）。そして、ｉをインクリメントし（ステップＳ８０７）、ステップＳ８０２に戻る。一方、ステップＳ８０５において、記憶領域Ｍｊが空でない場合（ステップＳ８０５：Ｎｏ）、記憶領域Ｍｊに格納されているハッシュ値ｈｘを読み出して、当該ハッシュ値ｈｘと未格納ハッシュ値ｈｙとを結合して結合ハッシュ値ｈｘ｜ｈｙを生成する（ステップＳ８０８）。これにより、結合ハッシュ値ｈｘ｜ｈｙがあらたな対象データに設定される。そして、結合ハッシュ値ｈｘ｜ｈｙのハッシュ値を算出する（ステップＳ８０９）。【００７３】
このあと、ｊをインクリメントすることで（ステップＳ８１０）、次に優先度が高い記憶領域を対象領域として選択する。そして、ｊ＞Ｊであるか否かを判断する（ステップＳ８１１）。Ｊは記憶領域の総数である。図３−１〜図４−２の場合は、Ｊ＝５である。ｊ＞Ｊである場合（ステップＳ８１１：Ｎｏ）、ステップＳ８０５に戻る。一方、ｊ＞Ｊである場合（ステップＳ８１１：Ｙｅｓ）、未格納ハッシュ値ｈｙを格納させる記憶領域がないため、エラー出力する（ステップＳ８１２）。これにより、一連の処理を終了する。また、ステップＳ８０２において、入力データｆiがない場合（ステップＳ８０２：Ｎｏ）、ステップＳ７０２に移行する。【００７４】
図９は、第２の格納処理（ステップＳ７０３）の詳細な処理手順を示すフローチャートである。まず、移行処理（上述した第１または第２の移行方法）を実行する（ステップＳ９０１）。つぎに、優先順位を示す変数ｋをｋ＝Ｊ、ｊ＝１とする（ステップＳ９０２）。そして、優先順位ｋのハッシュ値があるか否かを判断する（ステップＳ９０３）。優先順位ｋのハッシュ値がない場合（ステップＳ９０３：Ｎｏ）、ステップＳ９０７に移行する。一方、優先順位ｋのハッシュ値がある場合（ステップＳ９０３：Ｙｅｓ）、取得部６０１により、優先順位ｋのハッシュ値を未格納ハッシュ値ｈｙとして取得し（ステップＳ９０４）、記憶領域Ｍｊが空か否かを判断する（ステップＳ９０５）。【００７５】
空である場合（ステップＳ９０５：Ｙｅｓ）、未格納ハッシュ値ｈｙを記憶領域Ｍｊに格納する（ステップＳ９０６）。そして、ステップＳ９０７において、ｋをデクリメントし（ステップＳ９０７）、ｋ＜０であるか否かを判断する（ステップＳ９０８）。ｋ＜０である場合（ステップＳ９０８：Ｙｅｓ）、ステップＳ７０２に戻る。一方、ｋ＜０でない場合（ステップＳ９０８：Ｎｏ）、ステップＳ９０３に戻る。また、ステップＳ９０５において、記憶領域Ｍｊが空でない場合（ステップＳ９０５：Ｎｏ）、記憶領域Ｍｊに格納されているハッシュ値ｈｘを読み出して、当該ハッシュ値ｈｘと未格納ハッシュ値ｈｙとを結合して結合ハッシュ値ｈｘ｜ｈｙを生成する（ステップＳ９０９）。【００７６】
これにより、結合ハッシュ値ｈｘ｜ｈｙがあらたな対象データに設定される。そして、結合ハッシュ値ｈｘ｜ｈｙのハッシュ値を算出する（ステップＳ９１０）。このあと、ｊをインクリメントすることで（ステップＳ９１１）、次に優先度が高い記憶領域を対象領域として選択する。そして、ｊ＞Ｊであるか否かを判断する（ステップＳ９１２）。ｊ＞Ｊである場合（ステップＳ９１２：Ｎｏ）、ステップＳ９０５に戻る。一方、ｊ＞Ｊである場合（ステップＳ９１２：Ｙｅｓ）、未格納ハッシュ値ｈｙを格納させる記憶領域がないため、エラー出力する（ステップＳ９１３）。これにより、一連の処理を終了する。【００７７】
図１０は、本実施の形態と図１１に示した従来技術とを比較した図表である。図１０では、従来技術における入力データ数をｎとしている。図１０において、本実施の形態では、逐次処理が可能であり、レジスタ／メモリ数、撮影（入力データ取り込み）中ハッシュ処理回数、撮影後ハッシュ処理回数が格段に減少している。このように、合計ハッシュ処理回数は同じでも、本実施の形態によれば、レジスタ／メモリ数の大幅削減と、撮影後の後処理の時間を大幅削減することができる。【００７８】
なお、本実施の形態で説明したハッシュツリーの生成方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本電子署名プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本電子署名プログラムは、インターネット等のネットワーク１０９を介して配布してもよい。
【符号の説明】
【００７９】
１００  電子署名装置
６０１  取得部
６０２  演算部
６０３  判断部
６０４  格納部
６０５  設定部
６０６  選択部
６０７  決定部
【図１】
2010097942.tif 000003
【図２】
2010097942.tif 000004
【図３−１】
2010097942.tif 000005
【図３−２】
2010097942.tif 000006
【図３−３】
2010097942.tif 000007
【図３−４】
2010097942.tif 000008
【図３−５】
2010097942.tif 000009
【図４−１】
2010097942.tif 000010
【図４−２】
2010097942.tif 000011
【図５】
2010097942.tif 000012
【図６】
2010097942.tif 000013
【図７】
2010097942.tif 000014
【図８】
2010097942.tif 000015
【図９】
2010097942.tif 000016
【図１０】
2010097942.tif 000017
【図１１】
2010097942.tif 000018
【国際調査報告】
2010097942.tif 000019
2010097942.tif 000020
2010097942.tif 000021
2010097942.tif 000022