JP2012060621A - 署名生成装置、検証装置、署名生成方法及び署名生成プログラム - Google Patents

Abstract

【課題】コンポーネントソフトウェアの完全性を効率的に確認できる署名生成装置、検証装置、署名生成方法及び署名生成プログラムを提供すること。
【解決手段】署名生成装置１は、ソフトウェアに対応して、非公開の署名鍵、及び公開されている検証鍵を記憶する記憶部１１と、一方向性ハッシュ関数演算を行う一方向性ハッシュ関数演算部１３と、ソフトウェアから演算されたハッシュ値に対して署名鍵を乗じて公開署名情報を生成する署名情報生成部１４と、ソフトウェア、検証鍵及び公開署名情報を公開する公開部１５と、を備え、署名情報生成部１４は、ソフトウェアが当該ソフトウェアを構成する部品ソフトウェアを有する場合、部品ソフトウェアの公開署名情報と、部品ソフトウェアから演算されたハッシュ値に対して署名鍵を乗じた結果と、ソフトウェアから演算されたハッシュ値に対して署名鍵を乗じた結果とを総和して、公開署名情報を生成する。
【選択図】図１

Description

本発明は、ソフトウェアの完全性を確認するための署名生成装置、検証装置、署名生成方法及び署名生成プログラムに関する。

従来、コンピュータ向けのソフトウェアが数多く作成されている。これらの中には、機能が類似している物、あるいは発展的に進化した物がある。このようなソフトウェアを作成する上で、業務の効率化や開発時間の短縮を目的として、基本機能に特化した汎用的なソフトウェア等、既存のソフトウェア（以下、部品ソフトウェアと呼ぶ）を組み込んで、新たな機能を有するソフトウェア（以下、コンポーネントソフトウェアと呼ぶ）を作成する手法が採用される場合がある。また、この手法を用いるための開発環境も整備されてきている。

ところで、ソフトウェアは、許可無く改竄されたり、ウィルスが混入されたりすることで、正常に利用できないことがある。この対策のため、電子署名を用いて、ソフトウェアが改竄されていないか、又はウィルス等の悪意のあるソフトウェアが混入されていないか否かを確認する方法が提案されている（例えば、特許文献１〜４参照）。

特開平３−２８６３３４号公報 特開２００３−２０２９３１号公報 特開２００４−２４８０４５号公報 特開２００４−２２２３３０号公報

しかしながら、これらの方法は、一つのソフトウェアに対して、その完全性を保証するためのものである。したがって、前述のコンポーネントソフトウェアに対して、これらの方法を適用すると、ソフトウェアが組み込まれる度に、完全性の確認及び電子署名の生成のために多くの処理が発生していた。

本発明は、コンポーネントソフトウェアの完全性を効率的に確認できる署名生成装置、検証装置、署名生成方法及び署名生成プログラムを提供することを目的とする。

本発明では、以下のような解決手段を提供する。

（１）本発明に係る署名生成装置は、ソフトウェアの完全性を保証する公開署名情報を生成する署名生成装置であって、前記ソフトウェアに対応して、非公開の署名鍵、及び公開されている検証鍵を記憶する記憶部と、一方向性ハッシュ関数演算を行う第１ハッシュ演算部と、前記第１ハッシュ演算部により前記ソフトウェアから演算されたハッシュ値に対して、前記署名鍵を乗じて前記公開署名情報を生成する署名情報生成部と、前記ソフトウェア、前記検証鍵、及び前記公開署名情報を公開する公開部と、を備え、前記署名情報生成部は、前記ソフトウェアが当該ソフトウェアを構成する部品ソフトウェアを有する場合、前記部品ソフトウェアの公開署名情報と、前記部品ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果と、前記ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果とを総和して、前記公開署名情報を生成する。

このような構成によれば、署名生成装置は、部品ソフトウェアから得られたハッシュ値と、コンポーネントソフトウェアの署名鍵との積により、木構造において連続する２つのノード間の関係を表し、さらに部品ソフトウェアの公開署名情報を用いて、コンポーネントソフトウェアの公開署名情報を生成する。署名生成装置は、この公開署名情報により、コンポーネントソフトウェアを構成する部品ソフトウェアの木構造を表現できるので、コンポーネントソフトウェアの完全性を効率的に確認できる。

（２）また、上記署名生成装置では、前記署名鍵は、所定の自然数からなり、前記検証鍵は、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループの要素である楕円曲線上の点と前記署名鍵とに基づいて生成される、当該楕円曲線上の点からなる。

このような構成によれば、署名生成装置は、署名鍵を知らない第三者がＧＤＨグループの要素である楕円曲線上の点から署名鍵を求めることを、計算量的に困難にすることができる。また、署名者の数（ノードの数）が増えても、生成される公開署名情報は楕円曲線上の点であるため、情報のサイズ（容量）は増大せず一定値以下に抑制され、署名生成装置は、効率的に署名情報を生成することができる。

（３）また、上記署名生成装置では、前記公開部は、前記ソフトウェアを最上位ノードとし、前記部品ソフトウェアを下位ノードとする木構造の構成を示すリストデータを、さらに公開する。

このような構成によれば、署名生成装置は、コンポーネントソフトウェアを最上位ノードとし、部品ソフトウェアを下位ノードとする木構造の構成を示すリストデータを、さらに公開する。したがって、コンポーネントソフトウェアの完全性を確認する際に、木構造を容易に把握できるので、検証の処理効率が向上する。

（４）また、上記署名生成装置では、前記公開部は、前記第１ハッシュ演算部により前記ソフトウェアから演算されたハッシュ値を、さらに公開する。

このような構成によれば、署名生成装置は、部品ソフトウェアに対する一方向性ハッシュ関数演算の処理負荷を低減することができる。

（５）本発明に係る検証装置は、上記署名生成装置により公開された前記公開署名情報を検証する検証装置であって、前記ソフトウェア又は当該ソフトウェアから演算されたハッシュ値、及び対応する検証鍵、並びに当該ソフトウェアを構成する全ての部品ソフトウェア又は当該部品ソフトウェアから演算されたハッシュ値、及び対応する検証鍵を収集する収集部と、前記収集部により収集されたソフトウェアのそれぞれに対して、一方向性ハッシュ関数演算を行う第２ハッシュ演算部と、前記収集部により収集された全てのソフトウェアに対応する検証鍵、及び当該全てのソフトウェアから演算されたハッシュ値に基づいて、前記公開署名情報の正当性を検証する検証部と、を備える。

このような構成によれば、検証装置は、コンポーネントソフトウェア及び部品ソフトウェアの検証鍵とハッシュ値とに基づいて、コンポーネントソフトウェアに対する公開署名情報の正当性を検証する。よって、検証装置では、各部品ソフトウェアに対して生成される個々の署名情報等を検証することなく、検証対象であるコンポーネントソフトウェアに対して生成される公開署名情報を検証することにより、木構造における署名順序を証明することができる。すなわち、検証装置は、処理負荷を低減して検証処理を実行することができる。

（６）本発明に係る検証装置は、上記署名生成装置により公開された前記公開署名情報を検証する検証装置であって、前記ソフトウェア及び当該ソフトウェアを構成する全ての部品ソフトウェアから演算されたハッシュ値、並びに対応する検証鍵を収集する収集部と、前記収集部により収集された全てのソフトウェアに対応する検証鍵、及び当該全てのソフトウェアから演算されたハッシュ値に基づいて、前記公開署名情報の正当性を検証する検証部と、を備える。

このような構成によれば、検証装置は、検証対象であるコンポーネントソフトウェア及び部品ソフトウェアに対して、一方向性ハッシュ関数演算の処理負荷を低減することができる。

（７）本発明に係る署名生成方法は、ソフトウェアの完全性を保証する公開署名情報をコンピュータが生成する署名生成方法であって、前記ソフトウェアに対応して、非公開の署名鍵、及び公開されている検証鍵を記憶する記憶ステップと、一方向性ハッシュ関数演算を行うハッシュ演算ステップと、前記ハッシュ演算ステップにおいて前記ソフトウェアから演算されたハッシュ値に対して、前記署名鍵を乗じて前記公開署名情報を生成する署名情報生成ステップと、前記ソフトウェア、前記検証鍵、及び前記公開署名情報を公開する公開ステップと、を含み、前記署名情報生成ステップにおいて、前記ソフトウェアが当該ソフトウェアを構成する部品ソフトウェアを有する場合、前記部品ソフトウェアの公開署名情報と、前記部品ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果と、前記ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果とを総和して、前記公開署名情報を生成する。

このような構成によれば、署名生成方法をコンピュータが実行することにより、（１）と同様の効果が期待できる。

（８）本発明に係る署名生成プログラムは、ソフトウェアの完全性を保証する公開署名情報をコンピュータに生成させる署名生成プログラムであって、前記ソフトウェアに対応して、非公開の署名鍵、及び公開されている検証鍵を記憶する記憶ステップと、一方向性ハッシュ関数演算を行うハッシュ演算ステップと、前記ハッシュ演算ステップにおいて前記ソフトウェアから演算されたハッシュ値に対して、前記署名鍵を乗じて前記公開署名情報を生成する署名情報生成ステップと、前記ソフトウェア、前記検証鍵、及び前記公開署名情報を公開する公開ステップと、を実行させ、前記署名情報生成ステップにおいて、前記ソフトウェアが当該ソフトウェアを構成する部品ソフトウェアを有する場合、前記部品ソフトウェアの公開署名情報と、前記部品ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果と、前記ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果とを総和して、前記公開署名情報を生成させる。

このような構成によれば、署名生成プログラムをコンピュータに実行させることにより、（１）と同様の効果が期待できる。

本発明によれば、コンポーネントソフトウェアの完全性を効率的に確認できる。

第１実施形態に係る署名生成装置の構成を示すブロック図である。 第１実施形態に係る検証装置の構成を示すブロック図である。 第１実施形態に係る公開署名情報を公開する方法を示すフローチャートである。 第１実施形態に係る公開署名情報の正当性を検証する方法を示すフローチャートである。 第１実施形態に係る署名生成装置の動作についての説明に供する図である。 第２実施形態に係る署名生成装置の構成を示すブロック図である。 第２実施形態に係る検証装置の構成を示すブロック図である。

＜第１実施形態＞
以下、本発明の実施形態の一例である第１実施形態について説明する。本実施形態に係る署名生成装置１は、ソフトウェアの完全性を保証するための公開署名情報を生成する。ここで、署名対象がコンポーネントソフトウェアである場合、このコンポーネントソフトウェアは、１又は複数の部品ソフトウェアから構成される。これらの部品ソフトウェアは、さらに下位の部品ソフトウェアから構成される場合もある。署名生成装置１は、このように、コンポーネントソフトウェアを最上位ノードとし、部品ソフトウェアを下位ノードとする木構造状に構成された各ノードにおける、ソフトウェアの完全性を保証するための公開署名情報を生成する。また、各ノードのソフトウェアに対して生成された公開署名情報は、検証装置２により正当性が検証され、ソフトウェアの完全性が確認される。

なお、木構造とは、対称か非対称かを問わず、任意の構造を持つ木構造全てを指す。本発明は、この任意の構造を持つ木構造に対して適応可能である。

ところで、各ノード（コンポーネントソフトウェア又は部品ソフトウェア）には、非公開の署名鍵と、公開されている検証鍵とが認証局（ＣＡ）によってそれぞれ割り当てられている。署名鍵は、所定の自然数（ｘ）からなり、検証鍵は、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループ（Ｇ）の要素である楕円曲線上の点（ｇ）と署名鍵（ｘ）とに基づいて生成される楕円曲線上の点（ｖ＝ｘｇ）からなることが好ましい。このように構成されることにより、署名鍵（ｘ）を知らない第三者が「ｖ」や「ｇ」の値から署名鍵（ｘ）を求めることは計算量的に困難となる。

ここで、本実施形態で採用される具体的な署名方式について説明する。署名生成装置１では、ベースとなる署名方式としてＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＧＤＨ）署名を採用する。ＧＤＨ署名とは、Ｄｅｃｉｓｉｏｎ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題をペアリングと呼ばれるある種のブラックボックス関数ｅ（Ｐ，Ｑ）を用いることで、解くことが可能であることを利用した署名である。

次に、ペアリング演算を用いたＧＤＨ署名について説明する。楕円曲線上のＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題に関連して、ＧＤＨグループが定義されている。ＧＤＨグループについて簡単に説明する。Ｇをある楕円曲線上の点の集合とする。「ｇ」を集合Ｇの要素としたとき、集合Ｇにおける楕円曲線上のＤｅｃｉｓｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＤＨ）問題とＣｏｍｐｕｔａｔｉｏｎａｌ Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＣＤＨ）問題が以下のように定義される。

ＤＤＨ問題：あるａ、ｂ、ｃという自然数があり、ｇ、ａｇ、ｂｇ、ｃｇが与えられた時、ｃ＝ａｂかどうかを判定する問題。
ＣＤＨ問題：あるａ、ｂ、ｃという自然数があり、ｇ、ａｇ、ｂｇが与えられた時、ａｂｇを計算する問題。

このとき、ＤＤＨ問題は、計算量的に簡単であるが、ＣＤＨ問題は、計算量的に難問である場合、この集合ＧをＧＤＨグループと定義する。

これに対し、ある楕円曲線上の点をＰ，Ｑとし、そのＰ，Ｑによっては次にあげる性質を持つことができるペアリングと呼ばれるブラックボックス関数ｅ（Ｐ，Ｑ）を定義できるものが存在する。
ｅ（Ｐ，Ｑ_１＋Ｑ_２）＝ｅ（Ｐ，Ｑ_１）ｅ（Ｐ，Ｑ_２） ・・・（１）
ｅ（Ｐ_１＋Ｐ_２，Ｑ）＝ｅ（Ｐ_１，Ｑ）ｅ（Ｐ_２，Ｑ） ・・・（２）
ｅ（ａＰ，ｂＱ）＝ｅ（ｂＰ，ａＱ）＝ｅ（ａｂＰ，Ｑ）＝ｅ（Ｐ，ａｂＱ）＝ｅ（Ｐ，Ｑ）^ａｂ ・・・（３）

よって、ｇがペアリング演算の可能な楕円曲線上の点である場合には、上記の性質から、（３）式にｇ、ａｇ、ｂｇ、ｃｇを入力すると、
ｅ（ａｇ，ｂｇ）＝ｅ（ｇ，ｇ）^ａｂ ・・・（４）
ｅ（ｇ，ｃｇ）＝ｅ（ｇ，ｇ）^ｃ ・・・（５）
となり、両者の値が一致するかどうかにより、「ａｂ＝ｃ」であるかどうかを判定でき、ｇはＧＤＨグループＧの要素となりうる。

この性質を利用してＧＤＨ署名が構成される。集合Ｇは、ＧＤＨグループであり、ｇは集合Ｇの要素となる点とする。また、一方向性ハッシュ関数Ｈを、通常使用される任意のビット長のサイズの数値データが固定のビット長のサイズの数値データに写像変換される方式とは異なり、
Ｈ：｛０，１｝^＊→Ｇ
のように任意のビット長のサイズの数値データを楕円曲線上の点として表現されるＧＤＨグループＧの要素に写像変換する方式であると定義する。

このとき、ＧＤＨ署名は以下のように定義される。
鍵生成：自然数ｘを選び、ｇからｖ＝ｘｇを計算する。ｘを署名鍵、楕円曲線上の点ｖを検証鍵とする。
署名：署名者は、メッセージ「ｍ∈｛０，１｝^＊」に対しｈ＝Ｈ（ｍ）を計算し、さらに自分の署名鍵を用いてσ＝ｘｈを計算する。σをｍに対する署名として公開する。
検証：検証者は、メッセージｍからｈ＝Ｈ（ｍ）を計算し、ｇ、ｖ、ｈ、σを準備する。ｅ（ｇ，σ）とｅ（ｖ，ｈ）を計算し、両者の値が一致したら、署名σは、正しい署名と判定する。

このとき、ｈの値は集合Ｇの要素となるので、ある自然数ｙを用いてｈ＝ｙｇと表現できる。その結果、正しく署名が行われていれば（ｇ，ｖ，ｈ，σ）＝（ｇ，ｘｇ，ｙｇ，ｘｙｇ）となる。したがって、正当な署名であれば上記の検証でのペアリング演算は、ｅ（ｇ，σ）＝ｅ（ｇ，ｘｙｇ）＝ｅ（ｇ，ｇ）^ｘｙ＝ｅ（ｘｇ，ｙｇ）＝ｅ（ｖ，ｈ）となり、値が一致することから、検証可能となる。なお、ＧＤＨグループの条件であるＣＤＨ問題の困難性から、署名鍵ｘを知らない第三者がｇ、ｖ、ｈの値から署名σを導出することは不可能である。

図１は、本実施形態に係る署名生成装置１の構成を示すブロック図である。
署名生成装置１は、記憶部１１と、受信部１２と、一方向性ハッシュ関数演算部１３と、署名情報生成部１４と、公開部１５と、を備える。

記憶部１１は、自身のノード（署名者ｕ_ｕｐ）が作成したソフトウェア（ｍ_ｕｐ）に対応して割り当てられている署名鍵（ｘ_ｕｐ）と検証鍵（ｖ_ｕｐ＝ｘ_ｕｐｇ）とを記憶する。

受信部１２は、署名対象である自身のソフトウェアが構成要素として部品ソフトウェアを有する場合、１又は複数の下位ノード（署名者ｕ_ｌｏｗ）が作成した部品ソフトウェア（ｍ_ｌｏｗ）と、これらの部品ソフトウェアに対して後述の公開部１５により公開されている公開署名情報（σ_ｌｏｗ）と、を受信する。さらに、受信部１２は、公開部１５により同様に公開されている、部品ソフトウェアを最上位ノードとする木構造の構成を示すリストデータを受信する。

一方向性ハッシュ関数演算部１３は、受信部１２により受信された部品ソフトウェア（ｍ_ｌｏｗ）のそれぞれと、署名対象である自身のソフトウェア（ｍ_ｕｐ）とに一方向性ハッシュ関数演算を行う。

署名情報生成部１４は、部品ソフトウェアの公開署名情報（σ_ｌｏｗ）と、部品ソフトウェア（ｍ_ｌｏｗ）それぞれから演算されたハッシュ値（ｈ_ｌｏｗ＝Ｈ（ｍ_ｌｏｗ））に自身の署名鍵（ｘ_ｕｐ）により演算（楕円曲線上の乗算）を行った結果（ｘ_ｕｐｈ_ｌｏｗ）と、自身のソフトウェア（ｍ_ｕｐ）から演算されたハッシュ値（ｈ_ｕｐ＝Ｈ（ｍ_ｕｐ））に自身の署名鍵（ｘ_ｕｐ）により演算（楕円曲線上の乗算）を行った結果（ｘ_ｕｐｈ_ｕｐ）と、を総和して、自身のソフトウェアに対する公開署名情報（σ_ｕｐ＝Σ_ｌｏｗ（σ_ｌｏｗ＋ｘ_ｕｐｈ_ｌｏｗ）＋ｘ_ｕｐｈ_ｕｐ）を生成する（Σ_ｌｏｗは、直下のノード全てについての総和を示す）。

なお、署名情報生成部１４は、部品ソフトウェアがない場合、自身のソフトウェア（ｍ_ｕｐ）から演算されたハッシュ値（ｈ_ｕｐ）に自身の署名鍵（ｘ_ｕｐ）により演算（楕円曲線上の乗算）を行った結果（ｘ_ｕｐｈ_ｕｐ）のみを、自身のソフトウェアに対する公開署名情報（σ_ｕｐ＝ｘ_ｕｐｈ_ｕｐ）とする。

公開部１５は、自身のソフトウェア（ｍ_ｕｐ）、検証鍵（ｖ_ｕｐ）、及び署名情報生成部１４により生成された公開署名情報（σ_ｕｐ）を公開する。

このような構成によれば、署名生成装置１は、各ノードにおいて、部品ソフトウェアと部品ソフトウェアの公開署名情報とを用いて、コンポーネントソフトウェアの公開署名情報を生成する。この公開署名情報は、自身のノードに至るまでの木構造を表現し、かつ楕円曲線上の点のみで生成される。すなわち、署名者（部品ソフトウェアの数）が多くなっても、署名サイズは増大せず、一定値以下に抑制される。また、署名生成装置１は、自身のソフトウェアに対して生成した公開署名情報（σ_ｕｐ）を、ソフトウェアの利用者（検証装置２）や、さらに上位のコンポーネントソフトウェアの作成者（署名生成装置１）へ提供できる。

また、公開部１５は、自身のソフトウェアを最上位ノードとし、部品ソフトウェアを下位ノードとする木構造の構成を示すリストデータ（Ｌ）を、さらに公開する。
このリストデータは、例えば、
Ｌ＝｛（ｕ_ｐ，｛ｕ_ｐ１，ｕ_ｐ２，・・・｝，ＩＤ（ｍ_ｐ）），
（ｕ_ｐ１，｛｝，ＩＤ（ｍ_ｐ１）），
（ｕ_ｐ２，｛｝，ＩＤ（ｍ_ｐ２）），・・・｝
のように、構成される。ここで、署名者ｕ_ｐは、コンポーネントソフトウェアｍ_ｐの公開署名情報を生成し、ｍ_ｐを構成する部品ソフトウェア（ｍ_ｐ１、ｍ_ｐ２、・・・）は、それぞれ署名者（ｕ_ｐ１、ｕ_ｐ２、・・・）によって公開署名情報が生成されている。なお、ＩＤ（ｍ_α）は、ソフトウェアｍ_αの識別子（ＩＤ）である。

このような構成によれば、上位のノードにおいてコンポーネントソフトウェアの公開署名情報を生成する際の処理効率や、後述の検証装置２における検証の処理効率が向上する。

次に、署名生成装置１により公開された公開署名情報（σ）を検証する検証装置２について説明する。なお、検証装置２は、署名生成装置１と統合されていてもよい。

図２は、本実施形態に係る検証装置２の構成を示すブロック図である。
検証装置２は、収集部２１と、一方向性ハッシュ関数演算部２２と、検証部２３と、を備える。

収集部２１は、検証対象のソフトウェア及び対応する検証鍵と、このソフトウェアよりも下位のノードに位置する全ての部品ソフトウェア及び対応する検証鍵とを収集する。このとき、収集部２１は、検証対象のソフトウェアと共に公開されているリストデータ（Ｌ）を取得し、このリストデータにより示されている木構造の構成に従って、各ノードの部品ソフトウェア及び対応する検証鍵を収集する。

一方向性ハッシュ関数演算部２２は、収集部２１により収集された各ソフトウェア（ｍ_ｉ）に対して、一方向性ハッシュ関数演算を行う（ｈ_ｉ＝Ｈ（ｍ_ｉ））。

検証部２３は、収集部２１により収集された全てのノードのソフトウェアに対応する検証鍵と、一方向性ハッシュ関数演算部２２により得られた全てのノードのソフトウェアから演算されたハッシュ値と、リストデータ（Ｌ）から得られる各ノード（署名者）の配置、及び各署名者と署名を行ったソフトウェアとの対応関係に関する情報と、に基づいて、公開署名情報（σ）の正当性を検証する。

具体的には、検証部２３は、各ノードの検証鍵とハッシュ値とから、「｛Π_{ｉ∈ａｌｌ−ｎｏｄｅ}（ｅ（ｖ_ｉ，ｈ_ｉ））｝｛Π（ｅ（ｖ_ｕｐ，ｈ_ｌｏｗ））｝」を計算し、この計算結果と「ｅ（ｇ，σ）」の値とが一致することを確認することによって、公開署名情報（σ）の正当性を検証する。なお、式中で、直結する上下関係のノードをそれぞれ、「ｕｐ」（上位ノード）及び「ｌｏｗ」（下位ノード）と表した。

このようにして、検証装置２は、各ノードのソフトウェアに対して生成される個々の署名情報等を検証することなく、検証対象のコンポーネントソフトウェアに対して公開された公開署名情報を数値演算のみで検証できる。これにより、検証装置２は、メモリコストや処理負荷を低減し、木構造で構成されているコンポーネントソフトウェアの完全性を効率的に確認することができる。また、検証装置２は、コンポーネントソフトウェアを構成する各部品ソフトウェアの完全性も確認できるので、改竄やウィルスの混入等があった箇所を容易に特定できる。

次に、署名生成装置１において、各ノードにおけるソフトウェアの公開署名情報を生成する方法と、検証装置２において、公開署名情報の正当性を検証する方法について説明する。

署名生成装置１は、図３に示すように、記憶ステップＳ１と、受信ステップＳ２と、一方向性ハッシュ関数演算ステップＳ３と、署名情報生成ステップＳ４と、公開ステップＳ５とにより、各ノードにおけるソフトウェアの公開署名情報（σ）を公開する。

記憶ステップＳ１において、記憶部１１は、署名対象のソフトウェアに対応して、秘密情報である署名鍵と、公開情報である検証鍵とを取得して記憶する。

受信ステップＳ２において、受信部１２は、直下のノード（署名者ｕ_ｌｏｗの部品ソフトウェア）が存在する場合に、この部品ソフトウェア（ｍ_ｌｏｗ）、及び直下のノードの部品ソフトウェアに対して生成された公開署名情報（σ_ｌｏｗ）を受信する。

一方向性ハッシュ関数演算ステップＳ３において、一方向性ハッシュ関数演算部１３は、直下のノードの部品ソフトウェア（ｍ_ｌｏｗ）及び自身のノードのソフトウェア（ｍ_ｕｐ）に対して、それぞれ一方向性ハッシュ関数演算を行う。

署名情報生成ステップＳ４において、署名情報生成部１４は、自身のノードのソフトウェアから演算により得られたハッシュ値（ｈ_ｕｐ）に自身の署名鍵（ｘ_ｕｐ）を乗じた結果と、直下のノードがある場合に、この直下のノードの部品ソフトウェアから演算により得られたハッシュ値（ｈ_ｌｏｗ）に自身の署名鍵（ｘ_ｕｐ）を乗じた結果と、直下のノードから受信した公開署名情報（σ_ｌｏｗ）と、を用いて自身のノードのソフトウェアに対して公開署名情報（σ_ｕｐ）を生成する。

公開ステップＳ５において、公開部１５は、署名情報生成ステップＳ４により生成された公開署名情報、及び木構造の構成を示すリストデータを、ソフトウェア及び検証鍵と共に公開し、直上のノードの署名生成装置１又は検証装置２により参照可能とする。

このように、署名生成装置１に係る署名生成方法によれば、木構造の各ノードにおいて、直下のノードの部品ソフトウェアから得られたハッシュ値と、自身のノードのソフトウェアから得られたハッシュ値とに対して、自身のノードに割り当てられている署名鍵によって演算を行い、さらに直下のノードの部品ソフトウェアに対して生成された公開署名情報を用いて、自身の公開署名情報を生成する。この公開署名情報は、自身のノードに至るまでの署名経路を保持し、かつ楕円曲線上の点のみで生成される。すなわち、署名者（ノードの数）が多くなっても、署名サイズは増大せず、一定値以下に抑制することができる。

また、検証装置２は、図４に示すように、収集ステップＳ１１と、一方向性ハッシュ関数演算ステップＳ１２と、検証ステップＳ１３とにより、公開署名情報（σ）の正当性を検証する。

収集ステップＳ１１において、収集部２１は、署名が行われた全てのノードのソフトウェア（ｍ_ｉ）、及びこれら全てのノードの検証鍵（ｖ_ｉ）を収集する。

一方向性ハッシュ関数演算ステップＳ１２において、一方向性ハッシュ関数演算部２２は、収集ステップＳ１１により収集されたソフトウェアのそれぞれに対して、一方向性ハッシュ関数演算を行う。

検証ステップＳ１３において、検証部２３は、収集ステップＳ１１により収集された全てのノードの検証鍵、全てのノードのソフトウェアから一方向性ハッシュ関数演算ステップＳ１２により得られたハッシュ値、及びリストデータに基づいて公開署名情報（σ）の正当性を検証する。

このようにして、検証装置２に係る検証方法では、各ノードのソフトウェアに対して生成される個々の公開署名情報等を検証することなく、検証対象のソフトウェアに対して公開された公開署名情報を数値演算のみで検証できる。これにより、検証装置２は、メモリコストや処理負荷を低減し、木構造で構成されているコンポーネントソフトウェアの完全性を効率的に確認することができる。

［実施例］
ここで、木構造が３分木３階層で構成されている場合における各ノードの署名生成装置１の動作について図５を参照しながら具体的に説明する。なお、第１層は、最終コンポーネントソフトウェアの作成者かつ署名者であるルートノードである。また、第２層は、最終コンポーネントソフトウェアを構成する中間コンポーネントソフトウェアの作成者かつ署名者である中間ノードである。また、第３層は、中間コンポーネントソフトウェアを構成する部品ソフトウェアの作成者かつ署名者であるリーフノードである。

すなわち、第１層には、一つのルートノードが配置されている。また、第２層には、三つの中間ノードが配置され、ｕ_ｒｏｏｔの直下にｕ_１からｕ_３が配置されている。また、第３層には、九つのリーフノードが配置され、ｕ_１の直下にｕ_１１からｕ_１３が配置され、ｕ_２の直下にｕ_２１からｕ_２３が配置され、ｕ_３の直下にｕ_３１からｕ_３３が配置されている。

また、認証局（ＣＡ）は、予め各ノードに署名鍵と検証鍵を、以下のように付与している。なお、ｓとｔはそれぞれ、１≦ｓ≦３、１≦ｔ≦３となる整数の符号である。
第１層：（署名鍵，検証鍵）＝（ｘ_ｒｏｏｔ，ｖ_ｒｏｏｔ）＝（ｘ_ｒｏｏｔ，ｘ_ｒｏｏｔｇ）
第２層：（署名鍵，検証鍵）＝（ｘ_ｓ，ｖ_ｓ）＝（ｘ_ｓ，ｘ_ｓｇ）
第３層：（署名鍵，検証鍵）＝（ｘ_ｓｔ，ｖ_ｓｔ）＝（ｘ_ｓｔ，ｘ_ｓｔｇ）

第３層の九つのリーフノード（署名者ｕ_ｓｔ）は、署名対象である自身の作成した部品ソフトウェア（ｍ_ｓｔ）に対してハッシュ値（ｈ_ｓｔ＝Ｈ（ｍ_ｓｔ））を求め、ハッシュ値に自身の署名鍵ｘ_ｓｔを乗じて、公開署名情報（σ_ｓｔ＝ｘ_ｓｔｈ_ｓｔ）を生成する。また、リーフノード（署名者ｕ_ｓｔ）は、生成した公開署名情報（σ_ｓｔ）と、部品ソフトウェア（ｍ_ｓｔ）とを公開する。

第２層の三つの中間ノード（署名者ｕ_ｓ）は、まず署名対象である自身の作成した中間コンポーネントソフトウェア（ｍ_ｓ）から、ハッシュ値（ｈ_ｓ＝Ｈ（ｍ_ｓ））を求める。
次に、中間ノード（署名者ｕ_ｓ）は、直下のリーフノード（署名者ｕ_ｓ１、ｕ_ｓ２、ｕ_ｓ３）から受信した部品ソフトウェア（ｍ_ｓ１、ｍ_ｓ２、ｍ_ｓ３）から、ハッシュ値（ｈ_ｓ１＝Ｈ（ｍ_ｓ１）、ｈ_ｓ２＝Ｈ（ｍ_ｓ２）、ｈ_ｓ３＝Ｈ（ｍ_ｓ３））を求める。

さらに、中間ノード（署名者ｕ_ｓ）は、直下のリーフノードから受信した公開署名情報（σ_ｓ１、σ_ｓ２、σ_ｓ３）を用いて、
σ_ｓ＝σ_ｓ１＋ｘ_ｓｈ_ｓ１＋σ_ｓ２＋ｘ_ｓｈ_ｓ２＋σ_ｓ３＋ｘ_ｓｈ_ｓ３
＋ｘ_ｓｈ_ｓ ・・・（６）
＝ｘ_ｓ１ｈ_ｓ１＋ｘ_ｓｈ_ｓ１＋ｘ_ｓ２ｈ_ｓ２＋ｘ_ｓｈ_ｓ２
＋ｘ_ｓ３ｈ_ｓ３＋ｘ_ｓｈ_ｓ３＋ｘ_ｓｈ_ｓ ・・・（７）
を計算する。そして、中間ノード（署名者ｕ_ｓ）は、生成した公開署名情報（σ_ｓ）と、中間コンポーネントソフトウェア（ｍ_ｓ）とを公開する。

第１層のルートノード（署名者ｕ_ｒｏｏｔ）は、まず署名対象である自身の作成した最終コンポーネントソフトウェア（ｍ_ｒｏｏｔ）から、ハッシュ値（ｈ_ｒｏｏｔ＝Ｈ（ｍ_ｒｏｏｔ））を求める。
次に、ルートノード（署名者ｕ_ｒｏｏｔ）は、直下の中間ノード（署名者ｕ_１、ｕ_２、ｕ_３）から受信した中間コンポーネントソフトウェア（ｍ_１、ｍ_２、ｍ_３）から、ハッシュ値（ｈ_１＝Ｈ（ｍ_１）、ｈ_２＝Ｈ（ｍ_２）、ｈ_３＝Ｈ（ｍ_３））を求める。

さらに、ルートノード（署名者ｕ_ｒｏｏｔ）は、直下の中間ノードから受信した公開署名情報（σ_１、σ_２、σ_３）を用いて、
σ＝σ_１＋ｘ_ｒｏｏｔｈ_１＋σ_２＋ｘ_ｒｏｏｔｈ_２＋σ_３＋ｘ_ｒｏｏｔｈ_３
＋ｘ_ｒｏｏｔｈ_ｒｏｏｔ ・・・（８）
＝ｘ_１１ｈ_１１＋ｘ_１ｈ_１１＋ｘ_１２ｈ_１２＋ｘ_１ｈ_１２
＋ｘ_１３ｈ_１３＋ｘ_１ｈ_１３＋ｘ_１ｈ_１＋ｘ_ｒｏｏｔｈ_１
＋ｘ_２１ｈ_２１＋ｘ_２ｈ_２１＋ｘ_２２ｈ_２２＋ｘ_２ｈ_２２
＋ｘ_２３ｈ_２３＋ｘ_２ｈ_２３＋ｘ_２ｈ_２＋ｘ_ｒｏｏｔｈ_２
＋ｘ_３１ｈ_３１＋ｘ_３ｈ_３１＋ｘ_３２ｈ_３２＋ｘ_３ｈ_３２
＋ｘ_３３ｈ_３３＋ｘ_３ｈ_３３＋ｘ_３ｈ_３＋ｘ_ｒｏｏｔｈ_３
＋ｘ_ｒｏｏｔｈ_ｒｏｏｔ ・・・（９）
を計算する。そして、ルートノード（署名者ｕ_ｒｏｏｔ）は、生成した公開署名情報（σ）と、最終コンポーネントソフトウェア（ｍ_ｒｏｏｔ）とを公開する。

このようにして、署名生成装置１は、木構造上において連続（隣接）する２つのノード間の関係を署名鍵とハッシュ値の積で表すことにより、木構造を表現することができる。また、ノードの数が増えても、公開されるのは、署名対象のコンポーネントソフトウェアに対して生成される公開署名情報（σ）である。この署名情報は楕円曲線上の点であるため、情報のサイズ（容量）は増大せず、一定値以下に抑制される。したがって、署名生成装置１は、効率的に署名情報を生成することができる。

また、検証装置２は、以下の検証過程１から検証過程３により公開署名情報（σ）の正当性を検証する。

（検証過程１）検証装置２は、署名を行った全てのノードが署名対象としたソフトウェア（ｍ_ｒｏｏｔ、ｍ_１、ｍ_２、ｍ_３、ｍ_１１、ｍ_１２、ｍ_１３、ｍ_２１、ｍ_２２、ｍ_２３、ｍ_３１、ｍ_３２、ｍ_３３）を収集し、これらに対してハッシュ値（ｈ_ｒｏｏｔ＝Ｈ（ｍ_ｒｏｏｔ）、ｈ_１＝Ｈ（ｍ_１）、ｈ_２＝Ｈ（ｍ_２）、ｈ_３＝Ｈ（ｍ_３）、ｈ_１１＝Ｈ（ｍ_１１）、ｈ_１２＝Ｈ（ｍ_１２）、ｈ_１３＝Ｈ（ｍ_１３）、ｈ_２１＝Ｈ（ｍ_２１）、ｈ_２２＝Ｈ（ｍ_２２）、ｈ_２３＝Ｈ（ｍ_２３）、ｈ_３１＝Ｈ（ｍ_３１）、ｈ_３２＝Ｈ（ｍ_３２）、ｈ_３３＝Ｈ（ｍ_３３））を求める。

（検証過程２）検証装置２は、署名を行った全てのノードの検証鍵（ｖ_ｒｏｏｔ、ｖ_１、ｖ_２、ｖ_３、ｖ_１１、ｖ_１２、ｖ_１３、ｖ_２１、ｖ_２２、ｖ_２３、ｖ_３１、ｖ_３２、ｖ_３３）を収集する。

（検証過程３）検証装置２は、公開された公開署名情報（σ）の正当性を検証する。具体的には、検証装置２は、検証過程１で求めたハッシュ値と、収集した全てのノードの検証鍵とから、
ｅ（ｖ_１１，ｈ_１１）・ｅ（ｖ_１，ｈ_１１）
・ｅ（ｖ_１２，ｈ_１２）・ｅ（ｖ_１，ｈ_１２）
・ｅ（ｖ_１３，ｈ_１３）・ｅ（ｖ_１，ｈ_１３）
・ｅ（ｖ_１，ｈ_１）・ｅ（ｖ_ｒｏｏｔ，ｈ_１）
・ｅ（ｖ_２１，ｈ_２１）・ｅ（ｖ_２，ｈ_２１）
・ｅ（ｖ_２２，ｈ_２２）・ｅ（ｖ_２，ｈ_２２）
・ｅ（ｖ_２３，ｈ_２３）・ｅ（ｖ_２，ｈ_２３）
・ｅ（ｖ_２，ｈ_２）・ｅ（ｖ_ｒｏｏｔ，ｈ_２）
・ｅ（ｖ_３１，ｈ_３１）・ｅ（ｖ_３，ｈ_３１）
・ｅ（ｖ_３２，ｈ_３２）・ｅ（ｖ_３，ｈ_３２）
・ｅ（ｖ_３３，ｈ_３３）・ｅ（ｖ_３，ｈ_３３）
・ｅ（ｖ_３，ｈ_３）・ｅ（ｖ_ｒｏｏｔ，ｈ_３）
・ｅ（ｖ_ｒｏｏｔ，ｈ_ｒｏｏｔ） ・・・（１０）
を計算し、この値とｅ（ｇ，σ）の値とが一致することを確認する。検証装置２は、これらの値が一致した場合には、公開署名情報（σ）が正当であると判断する。

ここで、（検証過程３）における「ｅ（ｇ，σ）」を展開すると、
ｅ（ｇ，σ）
＝ｅ（ｇ，ｘ_１１ｈ_１１）・ｅ（ｇ，ｘ_１ｈ_１１）
・ｅ（ｇ，ｘ_１２ｈ_１２）・ｅ（ｇ，ｘ_１ｈ_１２）
・ｅ（ｇ，ｘ_１３ｈ_１３）・ｅ（ｇ，ｘ_１ｈ_１３）
・ｅ（ｇ，ｘ_１ｈ_１）・ｅ（ｇ，ｘ_ｒｏｏｔｈ_１）
・ｅ（ｇ，ｘ_２１ｈ_２１）・ｅ（ｇ，ｘ_２ｈ_２１）
・ｅ（ｇ，ｘ_２２ｈ_２２）・ｅ（ｇ，ｘ_２ｈ_２２）
・ｅ（ｇ，ｘ_２３ｈ_２３）・ｅ（ｇ，ｘ_２ｈ_２３）
・ｅ（ｇ，ｘ_２ｈ_２）・ｅ（ｇ，ｘ_ｒｏｏｔｈ_２）
・ｅ（ｇ，ｘ_３１ｈ_３１）・ｅ（ｇ，ｘ_３ｈ_３１）
・ｅ（ｇ，ｘ_３２ｈ_３２）・ｅ（ｇ，ｘ_３ｈ_３２）
・ｅ（ｇ，ｘ_３３ｈ_３３）・ｅ（ｇ，ｘ_３ｈ_３３）
・ｅ（ｇ，ｘ_３ｈ_３）・ｅ（ｇ，ｘ_ｒｏｏｔｈ_３）
・ｅ（ｇ，ｘ_ｒｏｏｔｈ_ｒｏｏｔ） ・・・（１１）
＝ｅ（ｘ_１１ｇ，ｈ_１１）・ｅ（ｘ_１ｇ，ｈ_１１）
・ｅ（ｘ_１２ｇ，ｈ_１２）・ｅ（ｘ_１ｇ，ｈ_１２）
・ｅ（ｘ_１３ｇ，ｈ_１３）・ｅ（ｘ_１ｇ，ｈ_１３）
・ｅ（ｘ_１ｇ，ｈ_１）・ｅ（ｘ_ｒｏｏｔｇ，ｈ_１）
・ｅ（ｘ_２１ｇ，ｈ_２１）・ｅ（ｘ_２ｇ，ｈ_２１）
・ｅ（ｘ_２２ｇ，ｈ_２２）・ｅ（ｘ_２ｇ，ｈ_２２）
・ｅ（ｘ_２３ｇ，ｈ_２３）・ｅ（ｘ_２ｇ，ｈ_２３）
・ｅ（ｘ_２ｇ，ｈ_２）・ｅ（ｘ_ｒｏｏｔｇ，ｈ_２）
・ｅ（ｘ_３１ｇ，ｈ_３１）・ｅ（ｘ_３ｇ，ｈ_３１）
・ｅ（ｘ_３２ｇ，ｈ_３２）・ｅ（ｘ_３ｇ，ｈ_３２）
・ｅ（ｘ_３３ｇ，ｈ_３３）・ｅ（ｘ_３ｇ，ｈ_３３）
・ｅ（ｘ_３ｇ，ｈ_３）・ｅ（ｘ_ｒｏｏｔｇ，ｈ_３）
・ｅ（ｘ_ｒｏｏｔｇ，ｈ_ｒｏｏｔ） ・・・（１２）
＝ｅ（ｖ_１１，ｈ_１１）・ｅ（ｖ_１，ｈ_１１）
・ｅ（ｖ_１２，ｈ_１２）・ｅ（ｖ_１，ｈ_１２）
・ｅ（ｖ_１３，ｈ_１３）・ｅ（ｖ_１，ｈ_１３）
・ｅ（ｖ_１，ｈ_１）・ｅ（ｖ_ｒｏｏｔ，ｈ_１）
・ｅ（ｖ_２１，ｈ_２１）・ｅ（ｖ_２，ｈ_２１）
・ｅ（ｖ_２２，ｈ_２２）・ｅ（ｖ_２，ｈ_２２）
・ｅ（ｖ_２３，ｈ_２３）・ｅ（ｖ_２，ｈ_２３）
・ｅ（ｖ_２，ｈ_２）・ｅ（ｖ_ｒｏｏｔ，ｈ_２）
・ｅ（ｖ_３１，ｈ_３１）・ｅ（ｖ_３，ｈ_３１）
・ｅ（ｖ_３２，ｈ_３２）・ｅ（ｖ_３，ｈ_３２）
・ｅ（ｖ_３３，ｈ_３３）・ｅ（ｖ_３，ｈ_３３）
・ｅ（ｖ_３，ｈ_３）・ｅ（ｖ_ｒｏｏｔ，ｈ_３）
・ｅ（ｖ_ｒｏｏｔ，ｈ_ｒｏｏｔ） ・・・（１３）
となり、署名の過程が正しく行われていれば、（１０）式と一致する。よって、公開されているソフトウェア作成者の検証鍵と、全ての部品ソフトウェア、中間コンポーネントソフトウェア及び最終コンポーネントソフトウェアから求めたハッシュ値とから、公開署名情報の検証が可能となる。

ここで、σの値に着目すると、署名者ｕ_ｓｔはｈ_ｓｔにのみ署名処理（ｘ_ｓｔｈ_ｓｔの演算）を行っており、他のｈ_ｓ及びｈ_ｒｏｏｔにはこのような署名処理を行っていない。これにより、署名者ｕ_ｓｔが最初、すなわち木構造におけるリーフノードの署名者であることが分かる。

また、「ｘ_ｓｈ_ｓｔ」の項により、この最初の署名者が署名処理したｈ_ｓｔに対して署名処理を行っているのがユーザｕ_ｓであることが表されているので、この署名者ｕ_ｓが２番目（中間ノード）の署名者であることが分かる。署名者ｕ_ｓは同時にｈ_ｓに対して署名処理（ｘ_ｓｈ_ｓ）を行っている。同様に「ｘ_ｒｏｏｔｈ_ｓ」の項により、このｈ_ｓに対して署名処理を行っているのが署名者ｕ_ｒｏｏｔであることが表されているので、この署名者ｕ_ｒｏｏｔが３番目の署名者であることが分かる。

さらに、ｈ_ｒｏｏｔに対して署名処理を行っている署名者はなく、署名者ｕ_ｒｏｏｔで収束しているため、この３番目の署名者がルートノードであることが分かる。

また、（１１）式において、ＣＤＨ問題や楕円曲線上の離散対数問題から、秘密情報である署名鍵を知らない第三者が、右辺の各項（ｘ_αｈ_β又はｘ_βｈ_β）を任意に取り除くことはできないため、第三者による順序の入れ替えは不可能である。すなわち、本署名方式は、木構造における署名順序を署名鍵とハッシュ値の積により表現することができる。

また、署名者の数（ノードの数）が増えても、公開される情報は公開署名情報（σ）のみである。この公開署名情報（σ）は一つの楕円曲線上の点であるため、情報のサイズ（容量）は増大せず、一定値以下に抑制される。

さらに、検証装置２では、検証過程３で示した数値演算のみで検証することにより、ノード間をどのような順序で署名されてきたかを証明することができる。したがって、検証装置２は、メモリコストや処理負荷を低減し、木構造で構成されているコンポーネントソフトウェアの完全性を効率的に確認することができる。

＜第２実施形態＞
以下、本発明の実施形態の一例である第２実施形態について説明する。なお、第１実施形態と同様の構成については、同一の符号を付し、説明を省略又は簡略化する。

図６は、本実施形態に係る署名生成装置１ａの構成を示すブロック図である。
署名生成装置１ａは、受信部１２ａ、一方向性ハッシュ関数演算部１３ａ及び公開部１５ａの構成が第１実施形態と異なる。

すなわち、受信部１２ａは、直下のノードから、ソフトウェア（ｍ_ｌｏｗ）の代わりにハッシュ値（ｈ_ｌｏｗ）を受信して署名情報生成部１４へ供給する。これにより、一方向性ハッシュ関数演算部１３ａは、直下のノードのソフトウェア（ｍ_ｌｏｗ）に一方向性ハッシュ関数演算を行う必要がなくなる。

また、公開部１５ａは、ソフトウェア（ｍ_ｕｐ）、検証鍵（ｖ_ｕｐ）、公開署名情報（σ_ｕｐ）及びリストデータ（Ｌ_ｕｐ）に加えて、一方向性ハッシュ関数演算部１３ａにより自身の署名対象であるソフトウェアから演算されたハッシュ値を、さらに公開する。これにより、直上のノードの署名生成装置１ａ又は検証装置２ａは、この公開されているハッシュ値を、ソフトウェアそのものの代わりに利用する。

図７は、本実施形態に係る検証装置２ａの構成を示すブロック図である。
検証装置２ａは、収集部２１ａの構成が第１実施形態と異なる。さらに、検証装置２ａは、第１実施形態における一方向性ハッシュ関数演算部２２を必要としない。

すなわち、収集部２１ａは、各ノードから、ソフトウェア（ｍ_ｉ）の代わりにハッシュ値（ｈ_ｉ）を受信して検証部２３へ供給する。これにより、検証装置２ａは、各ノードのソフトウェア（ｍ_ｉ）に一方向性ハッシュ関数演算を行う必要がなくなる。

本実施形態によれば、署名生成装置１ａ及び検証装置２ａにおける一方向性ハッシュ関数演算の処理負荷を低減することができる。
具体的には、第１実施形態の署名生成装置１における一方向性ハッシュ関数演算ステップＳ３の処理負荷が低減され、検証装置２における一方向性ハッシュ関数演算ステップＳ１２は不要となる。

なお、各ノードにおける署名処理では、直下のノードからソフトウェア（ｍ_ｉ）又はハッシュ値（ｈ_ｉ）のいずれかを受信すればよく、署名生成装置１ａ及び検証装置２ａ内において統一されていなくてもよい。

以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。

前述の実施形態において、ペアリング関数への入力である２つの引数は、ペアリングの演算が可能な楕円曲線上の点ｇのスカラー倍として表されるが、この楕円曲線は、第１引数と第２引数とで共通でなくてもよい。すなわち、ペアリング関数の第１引数用と第２引数用とに、それぞれ異なる楕円曲線（Ｇ_１又はＧ_２）上の２点（ｇ_１又はｇ_２）が与えられていてもよい。
この場合、前述の実施形態の説明におけるペアリング関数の第１引数に表れるｇはｇ_１に、第２引数に表れるｇはｇ_２に読み替えられる。また、楕円曲線上の点を用いて生成される前述の各種公開情報（検証鍵、ハッシュ値、公開署名情報）は、ペアリング関数の第１引数又は第２引数のいずれに入力されるかに応じて、Ｇ_１若しくはＧ_２のいずれかを用いて１種類、又は双方を用いて２種類生成される。
このことにより、公開情報の数、すなわち演算回数が増加する場合があるが、ペアリング関数の演算において並列して処理できるため、計算時間の短縮が期待できる。

また、署名生成装置１（又は１ａ）及び検証装置２（２ａ）による一連の処理は、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。また、当該プログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。

１、１ａ 署名生成装置
２、２ａ 検証装置
１１ 記憶部
１２、１２ａ 受信部
１３、１３ａ 一方向性ハッシュ関数演算部（第１ハッシュ演算部）
１４ 署名情報生成部
１５、１５ａ 公開部
２１、２１ａ 収集部
２２ 一方向性ハッシュ関数演算部（第２ハッシュ演算部）
２３ 検証部

Claims (8)

1. ソフトウェアの完全性を保証する公開署名情報を生成する署名生成装置であって、
   前記ソフトウェアに対応して、非公開の署名鍵、及び公開されている検証鍵を記憶する記憶部と、
   一方向性ハッシュ関数演算を行う第１ハッシュ演算部と、
   前記第１ハッシュ演算部により前記ソフトウェアから演算されたハッシュ値に対して、前記署名鍵を乗じて前記公開署名情報を生成する署名情報生成部と、
   前記ソフトウェア、前記検証鍵、及び前記公開署名情報を公開する公開部と、を備え、
   前記署名情報生成部は、前記ソフトウェアが当該ソフトウェアを構成する部品ソフトウェアを有する場合、前記部品ソフトウェアの公開署名情報と、前記部品ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果と、前記ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果とを総和して、前記公開署名情報を生成する署名生成装置。
2. 前記署名鍵は、所定の自然数からなり、
   前記検証鍵は、ＧＤＨ（ＧＡＰ−Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）グループの要素である楕円曲線上の点と前記署名鍵とに基づいて生成される、当該楕円曲線上の点からなる請求項１に記載の署名生成装置。
3. 前記公開部は、前記ソフトウェアを最上位ノードとし、前記部品ソフトウェアを下位ノードとする木構造の構成を示すリストデータを、さらに公開する請求項１又は請求項２に記載の署名生成装置。
4. 前記公開部は、前記第１ハッシュ演算部により前記ソフトウェアから演算されたハッシュ値を、さらに公開する請求項１から請求項３のいずれかに記載の署名生成装置。
5. 請求項１から請求項４のいずれかに記載の署名生成装置により公開された前記公開署名情報を検証する検証装置であって、
   前記ソフトウェア又は当該ソフトウェアから演算されたハッシュ値、及び対応する検証鍵、並びに当該ソフトウェアを構成する全ての部品ソフトウェア又は当該部品ソフトウェアから演算されたハッシュ値、及び対応する検証鍵を収集する収集部と、
   前記収集部により収集されたソフトウェアのそれぞれに対して、一方向性ハッシュ関数演算を行う第２ハッシュ演算部と、
   前記収集部により収集された全てのソフトウェアに対応する検証鍵、及び当該全てのソフトウェアから演算されたハッシュ値に基づいて、前記公開署名情報の正当性を検証する検証部と、を備える検証装置。
6. 請求項４に記載の署名生成装置により公開された前記公開署名情報を検証する検証装置であって、
   前記ソフトウェア及び当該ソフトウェアを構成する全ての部品ソフトウェアから演算されたハッシュ値、並びに対応する検証鍵を収集する収集部と、
   前記収集部により収集された全てのソフトウェアに対応する検証鍵、及び当該全てのソフトウェアから演算されたハッシュ値に基づいて、前記公開署名情報の正当性を検証する検証部と、を備える検証装置。
7. ソフトウェアの完全性を保証する公開署名情報をコンピュータが生成する署名生成方法であって、
   前記ソフトウェアに対応して、非公開の署名鍵、及び公開されている検証鍵を記憶する記憶ステップと、
   一方向性ハッシュ関数演算を行うハッシュ演算ステップと、
   前記ハッシュ演算ステップにおいて前記ソフトウェアから演算されたハッシュ値に対して、前記署名鍵を乗じて前記公開署名情報を生成する署名情報生成ステップと、
   前記ソフトウェア、前記検証鍵、及び前記公開署名情報を公開する公開ステップと、を含み、
   前記署名情報生成ステップにおいて、前記ソフトウェアが当該ソフトウェアを構成する部品ソフトウェアを有する場合、前記部品ソフトウェアの公開署名情報と、前記部品ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果と、前記ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果とを総和して、前記公開署名情報を生成する署名生成方法。
8. ソフトウェアの完全性を保証する公開署名情報をコンピュータに生成させる署名生成プログラムであって、
   前記ソフトウェアに対応して、非公開の署名鍵、及び公開されている検証鍵を記憶する記憶ステップと、
   一方向性ハッシュ関数演算を行うハッシュ演算ステップと、
   前記ハッシュ演算ステップにおいて前記ソフトウェアから演算されたハッシュ値に対して、前記署名鍵を乗じて前記公開署名情報を生成する署名情報生成ステップと、
   前記ソフトウェア、前記検証鍵、及び前記公開署名情報を公開する公開ステップと、を実行させ、
   前記署名情報生成ステップにおいて、前記ソフトウェアが当該ソフトウェアを構成する部品ソフトウェアを有する場合、前記部品ソフトウェアの公開署名情報と、前記部品ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果と、前記ソフトウェアから演算されたハッシュ値に対して前記署名鍵を乗じた結果とを総和して、前記公開署名情報を生成させる署名生成プログラム。

Images