(57)【特許請求の範囲】
【請求項１】
鍵交換を行う鍵交換装置であって、
ｋは整数、ｐはｋビットの素数、ＧとＧＴは位数ｐの巡回群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形ペアリング関数、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈは任意長の整数をｋビットの整数に変換するハッシュ関数、Ｍ、Ｎは整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、ＩＤＡ，ｍとＩＤＢ，ｍは任意の整数、ｓ０とｓＡ，ｍとｓＢ，ｎはランダムに選択された０以上ｐ−１以下の整数、Ｓ０は群Ｇの単位元、Ｐ０＝ｇ、Ｑ０＝Ｐ０＾ｓ０、＾はべき乗を示す記号であり、
当該鍵交換装置は、識別子がＩＤＡ＝（ＩＤＡ，１，…，ＩＤＡ，Ｍ）であり、長期秘密鍵として（ＳＡ，Ｍ，ＱＡ，１，…，ＱＡ，Ｍ）を記録しており、
鍵交換を行う相手の鍵交換装置は、識別子がＩＤＢ＝（ＩＤＢ，１，…，ＩＤＢ，Ｎ）であり、長期秘密鍵として（ＳＢ，Ｎ，ＱＢ，１，…，ＱＢ，Ｎ）を記録しており、
ｓＡ，０＝ｓＢ，０＝ｓ０
ＳＡ，０＝ＳＢ，０＝Ｓ０
とすると、
１〜Ｍのすべてのｍと１〜Ｎのすべてのｎについて、
ＰＡ，ｍ＝Ｈ１（ＩＤＡ，１，…，ＩＤＡ，ｍ）
ＳＡ，ｍ＝ＳＡ，ｍ−１ＰＡ，ｍ＾ｓＡ，ｍ−１
ＱＡ，ｍ＝Ｐ０＾ｓＡ，ｍ
ＰＢ，ｎ＝Ｈ１（ＩＤＢ，１，…，ＩＤＢ，ｎ）
ＳＢ，ｎ＝ＳＢ，ｎ−１ＰＢ，ｎ＾ｓＢ，ｎ−１
ＱＢ，ｎ＝Ｐ０＾ｓＢ，ｎ
の関係であり、
０以上ｐ−１以下の整数の中からランダムに選択した整数を短期秘密鍵ｘ〜とし、ｘ＝Ｈ２（ＳＡ，Ｍ，ｘ〜）を計算し、（Ｐ０＾ｘ，ＰＢ，２＾ｘ，…，ＰＢ，Ｎ＾ｘ）を短期公開鍵ｅｐｋＢ＝（Ｘ０，ＸＢ，２，…，ＸＢ，Ｎ）とし、当該短期公開鍵ｅｐｋＢを前記の相手の鍵交換装置に送信する短期鍵生成部と、
前記の相手の鍵交換装置から、短期公開鍵ｅｐｋＡ＝（Ｙ０，ＹＡ，２，…，ＹＡ，Ｍ）を受信する短期公開鍵受信部と、
σ１＝ｅ（Ｑ０，ＰＢ，１）＾ｘ
【数７】
0005427156.tif 000008
σ３＝Ｙ０＾ｘ
を計算し、σ１，σ２，σ３とハッシュ関数Ｈを用いてセッション鍵Ｋを求めるセッション鍵生成部と
を備える鍵交換装置。
【請求項２】
鍵交換を行う鍵交換装置であって、
ｋは整数、ｐはｋビットの素数、ＧとＧＴは位数ｐの巡回群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形ペアリング関数、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈは任意長の整数をｋビットの整数に変換するハッシュ関数、Ｍ、Ｎは整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、ＩＤＡ，ｍとＩＤＢ，ｍは任意の整数、ｓ０とｓＡ，ｍとｓＢ，ｎはランダムに選択された０以上ｐ−１以下の整数、Ｓ０は群Ｇの単位元、Ｐ０＝ｇ、Ｑ０＝Ｐ０＾ｓ０、＾はべき乗を示す記号であり、
当該鍵交換装置は、識別子がＩＤＢ＝（ＩＤＢ，１，…，ＩＤＢ，Ｎ）であり、長期秘密鍵として（ＳＢ，Ｎ，ＱＢ，１，…，ＱＢ，Ｎ）を記録しており、
鍵交換を行う相手の鍵交換装置は、識別子がＩＤＡ＝（ＩＤＡ，１，…，ＩＤＡ，Ｍ）であり、長期秘密鍵として（ＳＡ，Ｍ，ＱＡ，１，…，ＱＡ，Ｍ）を記録しており、
ｓＡ，０＝ｓＢ，０＝ｓ０
ＳＡ，０＝ＳＢ，０＝Ｓ０
とすると、
１〜Ｍのすべてのｍと１〜Ｎのすべてのｎについて、
ＰＡ，ｍ＝Ｈ１（ＩＤＡ，１，…，ＩＤＡ，ｍ）
ＳＡ，ｍ＝ＳＡ，ｍ−１ＰＡ，ｍ＾ｓＡ，ｍ−１
ＱＡ，ｍ＝Ｐ０＾ｓＡ，ｍ
ＰＢ，ｎ＝Ｈ１（ＩＤＢ，１，…，ＩＤＢ，ｎ）
ＳＢ，ｎ＝ＳＢ，ｎ−１ＰＢ，ｎ＾ｓＢ，ｎ−１
ＱＢ，ｎ＝Ｐ０＾ｓＢ，ｎ
の関係であり、
前記の相手の鍵交換装置から、短期公開鍵ｅｐｋＢ＝（Ｘ０，ＸＢ，２，…，ＸＢ，Ｎ）を受信する短期公開鍵受信部と、
０以上ｐ−１以下の整数の中からランダムに選択した整数を短期秘密鍵ｙ〜とし、ｙ＝Ｈ２（ＳＢ，Ｎ，ｙ〜）を計算し、（Ｐ０＾ｙ，ＰＡ，２＾ｙ，…，ＰＡ，Ｍ＾ｙ）を短期公開鍵ｅｐｋＡ＝（Ｙ０，ＹＡ，２，…，ＹＡ，Ｍ）とし、当該短期公開鍵ｅｐｋＡを前記の相手の鍵交換装置に送信する短期鍵生成部と、
【数８】
0005427156.tif 000009
σ２＝ｅ（Ｑ０，ＰＡ，１）＾ｙ
σ３＝Ｘ０＾ｙ
を計算し、σ１，σ２，σ３とハッシュ関数Ｈを用いてセッション鍵Ｋを求めるセッション鍵生成部と
を備える鍵交換装置。
【請求項３】
請求項１記載の鍵交換装置であって、
０以上ｐ−１以下の整数の中からランダムに整数を選択する乱数生成部と、
当該鍵交換装置の外部から情報を取得する情報取得部と、
長期秘密鍵（ＳＡ，Ｍ，ＱＡ，１，…，ＱＡ，Ｍ）を生成する長期秘密鍵計算部
も備え、
前記のｓＡ，Ｍは、前記乱数生成部が生成したものであり、
前記のＳＡ，Ｍ，ＱＡ，１，…，ＱＡ，Ｍ−１は、前記情報取得部が取得したものであり、
前記のＱＡ，Ｍは、前記長期秘密鍵計算部がＱＡ，Ｍ＝Ｐ０＾ｓＡ，Ｍのように求めたものであり、
前記長期秘密鍵計算部は、
さらに、
識別子が（ＩＤＡ，１，…，ＩＤＡ，Ｍ，ＩＤＡ，Ｍ＋１）の鍵交換装置のために、
ＰＡ，Ｍ＋１＝Ｈ１（ＩＤＡ，１，…，ＩＤＡ，Ｍ，ＩＤＡ，Ｍ＋１）
ＳＡ，Ｍ＋１＝ＳＡ，ＭＰＡ，Ｍ＋１＾ｓＡ，Ｍ
を計算する
ことを特徴とする鍵交換装置。
【請求項４】
請求項２記載の鍵交換装置であって、
０以上ｐ−１以下の整数の中からランダムに整数を選択する乱数生成部と、
当該鍵交換装置の外部から情報を取得する情報取得部と、
長期秘密鍵（ＳＢ，Ｎ，ＱＢ，１，…，ＱＢ，Ｎ）を生成する長期秘密鍵計算部
も備え、
前記のｓＢ，Ｎは、前記乱数生成部が生成したものであり、
前記のＳＢ，Ｎ，ＱＢ，１，…，ＱＡ，Ｎ−１は、前記情報取得部が取得したものであり、
前記のＱＢ，Ｎは、前記長期秘密鍵計算部がＱＢ，Ｎ＝Ｐ０＾ｓＢ，Ｎのように求めたものであり、
前記長期秘密鍵計算部は、
さらに、
識別子が（ＩＤＢ，１，…，ＩＤＢ，Ｎ，ＩＤＢ，Ｎ＋１）の鍵交換装置のために、
ＰＢ，Ｎ＋１＝Ｈ１（ＩＤＢ，１，…，ＩＤＢ，Ｎ，ＩＤＢ，Ｎ＋１）
ＳＢ，Ｎ＋１＝ＳＢ，ＮＰＢ，Ｎ＋１＾ｓＢ，Ｎ
を計算する
ことを特徴とする鍵交換装置。
【請求項５】
請求項１または３記載の鍵交換装置であって、
前記セッション鍵生成部が、
【数９】
0005427156.tif 000010
σ２＝ｅ（Ｑ０，ＰＢ，１）＾ｘ
σ３＝Ｙ０＾ｘ
のように前記のσ１，σ２，σ３を求めることもでき、どちらの方法でσ１，σ２，σ３を求めるかは、あらかじめ定めた方法に従う
ことを特徴とする鍵交換装置。
【請求項６】
請求項１記載の鍵交換装置と、
請求項２記載の鍵交換装置と、
を備える鍵交換システム。
【請求項７】
請求項６記載の鍵交換システムであって、
マスタ鍵生成手段と、
長期秘密鍵生成手段
も備え、
前記マスタ鍵生成手段は、
前記のｓ０を生成し、前記のＳ０を群Ｇの単位元に設定し、前記のＰ０とＱ０をＰ０＝ｇ、Ｑ０＝Ｐ０＾ｓ０のように求め、前記のＰ０とＱ０を公開し、
前記のＰＡ，１、ＳＡ，１を
ＰＡ，１＝Ｈ１（ＩＤＡ，１）
ＳＡ，１＝Ｓ０ＰＡ，１＾ｓ０
のように求め、
前記のＩＤＢ，１≠ＩＤＡ，１の場合は、前記のＰB，１、ＳB，１を
ＰＢ，１＝Ｈ１（ＩＤＢ，１）
ＳＢ，１＝Ｓ０ＰＢ，１＾ｓ０
のように求め、
長期秘密鍵生成手段は、
０以上ｐ−１以下の整数の中からランダムに整数を選択する乱数生成部と、
前記のＳＡ，１，ＳＢ，１を取得する情報取得部と、
長期秘密鍵を生成する長期秘密鍵計算部と
を有し、
前記乱数生成部が前記のｓＡ，ｍを生成し、
前記長期秘密鍵計算部が、
前記のＱＡ，ｍをＱＡ，ｍ＝Ｐ０＾ｓＡ，ｍのように求め、
前記のＰＡ，ｍ＋１とＳＡ，ｍ＋１を
ＰＡ，ｍ＋１＝Ｈ１（ＩＤＡ，１，…，ＩＤＡ，ｍ，ＩＤＡ，ｍ＋１）
ＳＡ，ｍ＋１＝ＳＡ，ｍＰＡ，ｍ＋１＾ｓＡ，ｍ
のように求める処理をｍ＝１〜Ｍ−１まで繰返し、
前記乱数生成部が前記のｓＡ，Ｍを生成し、
前記長期秘密鍵計算部が、
前記のＱＡ，ＭをＱＡ，Ｍ＝Ｐ０＾ｓＡ，Ｍのように求め、
（ＳＡ，Ｍ，ＱＡ，１，…，ＱＡ，Ｍ）を請求項１記載の鍵交換装置の長期秘密鍵とし、
ｎ＜Ｍ−１かつ（ＩＤＢ，１，…，ＩＤＢ，ｎ，ＩＤＢ，ｎ＋１）≠（ＩＤＡ，１，…，ＩＤＡ，ｎ，ＩＤＡ，ｎ＋１）の場合に、
前記乱数生成部が前記のｓＢ，ｎを生成し、
前記長期秘密鍵計算部が、
前記のＱＢ，ｎをＱＢ，ｎ＝Ｐ０＾ｓＢ，ｎのように求め、
前記のＰＢ，ｎ＋１とＳＢ，ｎ＋１を
ＰＢ，ｎ＋１＝Ｈ１（ＩＤＢ，１，…，ＩＤＢ，ｎ，ＩＤＢ，ｎ＋１）
ＳＢ，ｎ＋１＝ＳＢ，ｎＰＢ，ｎ＋１＾ｓＢ，ｎ
のように求める処理をｎ＝１〜Ｎ−１まで繰返し、
前記乱数生成部が前記のｓＢ，Ｎを生成し、
前記長期秘密鍵計算部が、
前記のＱＢ，ＮをＱＢ，Ｎ＝Ｐ０＾ｓＢ，Ｎのように求め、
（ＳＢ，Ｎ，ＱＢ，１，…，ＱＢ，Ｎ）を請求項２記載の鍵交換装置の長期秘密鍵とする
鍵交換システム。
【請求項８】
識別子がＩＤＡ＝（ＩＤＡ，１，…，ＩＤＡ，Ｍ）であり、長期秘密鍵として（ＳＡ，Ｍ，ＱＡ，１，…，ＱＡ，Ｍ）を記録する鍵交換装置ＡＭと、識別子がＩＤＢ＝（ＩＤＢ，１，…，ＩＤＢ，Ｎ）であり、長期秘密鍵として（ＳＢ，Ｎ，ＱＢ，１，…，ＱＢ，Ｎ）を記録する鍵交換装置ＢＮとが鍵交換を行う鍵交換方法であって、
ｋは整数、ｐはｋビットの素数、ＧとＧＴは位数ｐの巡回群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形ペアリング関数、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈは任意長の整数をｋビットの整数に変換するハッシュ関数、Ｍ、Ｎは整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、ＩＤＡ，ｍとＩＤＢ，ｍは任意の整数、ｓ０とｓＡ，ｍとｓＢ，ｎはランダムに選択された０以上ｐ−１以下の整数、Ｓ０は群Ｇの単位元、＾はべき乗を示す記号であり、
ｓＡ，０＝ｓＢ，０＝ｓ０
ＳＡ，０＝ＳＢ，０＝Ｓ０
とすると、
１〜Ｍのすべてのｍと１〜Ｎのすべてのｎについて、
ＰＡ，ｍ＝Ｈ１（ＩＤＡ，１，…，ＩＤＡ，ｍ）
ＳＡ，ｍ＝ＳＡ，ｍ−１ＰＡ，ｍ＾ｓＡ，ｍ−１
ＱＡ，ｍ＝Ｐ０＾ｓＡ，ｍ
ＰＢ，ｎ＝Ｈ１（ＩＤＢ，１，…，ＩＤＢ，ｎ）
ＳＢ，ｎ＝ＳＢ，ｎ−１ＰＢ，ｎ＾ｓＢ，ｎ−１
ＱＢ，ｎ＝Ｐ０＾ｓＢ，ｎ
の関係であり、
鍵交換装置ＡＭが、
０以上ｐ−１以下の整数の中からランダムに選択した整数を短期秘密鍵ｘ〜とし、ｘ＝Ｈ２（ＳＡ，Ｍ，ｘ〜）を計算し、（Ｐ０＾ｘ，ＰＢ，２＾ｘ，…，ＰＢ，Ｎ＾ｘ）を短期公開鍵ｅｐｋＢ＝（Ｘ０，ＸＢ，２，…，ＸＢ，Ｎ）とし、当該短期公開鍵ｅｐｋＢを鍵交換装置ＢＮに送信し、
鍵交換装置ＢＮが、
鍵交換装置ＡＭから、前記短期公開鍵ｅｐｋＢを受信し、
０以上ｐ−１以下の整数の中からランダムに選択した整数を短期秘密鍵ｙ〜とし、ｙ＝Ｈ２（ＳＢ，Ｎ，ｙ〜）を計算し、（Ｐ０＾ｙ，ＰＡ，２＾ｙ，…，ＰＡ，Ｍ＾ｙ）を短期公開鍵ｅｐｋＡ＝（Ｙ０，ＹＡ，２，…，ＹＡ，Ｍ）とし、当該短期公開鍵ｅｐｋＡを鍵交換装置ＡＭに送信し、
【数１０】
0005427156.tif 000011
σ２＝ｅ（Ｑ０，ＰＡ，１）＾ｙ
σ３＝Ｘ０＾ｙ
を計算し、σ１，σ２，σ３とハッシュ関数Ｈを用いてセッション鍵Ｋを求め、
鍵交換装置ＡＭが、
鍵交換装置ＢＮから、前記短期公開鍵ｅｐｋＡを受信し、
σ１＝ｅ（Ｑ０，ＰＢ，１）＾ｘ
【数１１】
0005427156.tif 000012
σ３＝Ｙ０＾ｘ
を計算し、σ１，σ２，σ３とハッシュ関数Ｈを用いてセッション鍵Ｋを求める
鍵交換方法。
【請求項９】
請求項８記載の鍵交換方法であって、
マスタ鍵生成手段が、
前記のｓ０を生成し、前記のＳ０を群Ｇの単位元に設定し、前記のＰ０とＱ０をＰ０＝ｇ、Ｑ０＝Ｐ０＾ｓ０のように求め、前記のＰ０とＱ０を公開し、
前記のＰＡ，１、ＳＡ，１を
ＰＡ，１＝Ｈ１（ＩＤＡ，１）
ＳＡ，１＝Ｓ０ＰＡ，１＾ｓ０
のように求め、
前記のＩＤＢ，１≠ＩＤＡ，１の場合は、前記のＰB，１、ＳB，１を
ＰＢ，１＝Ｈ１（ＩＤＢ，１）
ＳＢ，１＝Ｓ０ＰＢ，１＾ｓ０
のように求め、
長期秘密鍵生成手段が、
０以上ｐ−１以下の整数の中からランダムに前記のｓＡ，ｍを生成し、
前記のＱＡ，ｍをＱＡ，ｍ＝Ｐ０＾ｓＡ，ｍのように求め、
前記のＰＡ，ｍ＋１とＳＡ，ｍ＋１を
ＰＡ，ｍ＋１＝Ｈ１（ＩＤＡ，１，…，ＩＤＡ，ｍ，ＩＤＡ，ｍ＋１）
ＳＡ，ｍ＋１＝ＳＡ，ｍＰＡ，ｍ＋１＾ｓＡ，ｍ
のように求める処理をｍ＝１〜Ｍ−１まで繰返し、
０以上ｐ−１以下の整数の中からランダムに前記のｓＡ，Ｍを生成し、
前記のＱＡ，ＭをＱＡ，Ｍ＝Ｐ０＾ｓＡ，Ｍのように求め、
（ＳＡ，Ｍ，ＱＡ，１，…，ＱＡ，Ｍ）を鍵交換装置ＡＭの前記長期秘密鍵とし、
ｎ＜Ｍ−１かつ（ＩＤＢ，１，…，ＩＤＢ，ｎ，ＩＤＢ，ｎ＋１）≠（ＩＤＡ，１，…，ＩＤＡ，ｎ，ＩＤＡ，ｎ＋１）の場合に、
０以上ｐ−１以下の整数の中からランダムに前記のｓＢ，ｎを生成し、
前記のＱＢ，ｎをＱＢ，ｎ＝Ｐ０＾ｓＢ，ｎのように求め、
前記のＰＢ，ｎ＋１とＳＢ，ｎ＋１を
ＰＢ，ｎ＋１＝Ｈ１（ＩＤＢ，１，…，ＩＤＢ，ｎ，ＩＤＢ，ｎ＋１）
ＳＢ，ｎ＋１＝ＳＢ，ｎＰＢ，ｎ＋１＾ｓＢ，ｎ
のように求める処理をｎ＝１〜Ｎ−１まで繰返し、
０以上ｐ−１以下の整数の中からランダムに前記のｓＢ，Ｎを生成し、
前記のＱＢ，ＮをＱＢ，Ｎ＝Ｐ０＾ｓＢ，Ｎのように求め、
（ＳＢ，Ｎ，ＱＢ，１，…，ＱＢ，Ｎ）を鍵交換装置ＢＮの前記長期秘密鍵とする
鍵交換方法。
【請求項１０】
請求項１から５のいずれかに記載の鍵交換装置としてコンピュータを機能させる鍵交換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２つの装置で鍵を共有するための鍵交換装置、鍵交換システム、鍵交換方法、鍵交換プログラムに関する。
【背景技術】
【０００２】
従来の階層型ＩＤ認証鍵交換方式として、非特許文献１のＭＤＣ方式が知られている。背景技術の説明では、ｋは整数、ｐはｋビットの素数、ＧとＧＴは位数ｐの巡回群、ｇは群Ｇの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形ペアリング関数、ｇＴ＝ｅ（ｇ１，ｇ２）は群ＧＴの生成元、Ｈは群Ｇの元をｋ１ビットの整数に変換するハッシュ関数、Ｈ’は群ＧＴの元をｋ３ビットの整数に変換するハッシュ関数、ｆはｋ１ビット以上の整数をｋ２ビットの整数に変換するメッセージ認証コード、ＬはＩＤの階層の深さの最大値、Ｍ、Ｎは整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、ＩＤＡｍとＩＤＢｍは０以上ｐ−１以下の整数、＾はべき乗を示す記号、（＋）は排他的論理和を示す記号とする。
【０００３】
図１は、従来の階層型ＩＤ認証鍵交換方式のシステム構成を説明するための図である。図１のシステムでは、ネットワーク１０００を介して鍵生成手段９１０、鍵交換装置Ａ１９２０１〜鍵交換装置ＡＭ９２０Ｍ、鍵交換装置Ｂ１９３０１〜鍵交換装置ＢＮ９３０Ｎが接続されている。鍵交換装置Ａ１９２０１〜鍵交換装置ＡＭ９２０Ｍは階層的に識別子が付与されており、鍵交換装置Ａｍ９２０ｍの識別子は（ＩＤＡ１，…，ＩＤＡｍ）である。同様に鍵交換装置Ｂ１９３０１〜鍵交換装置ＢＮ９３０Ｎも階層的に識別子が付与されており、鍵交換装置Ｂｎ９３０ｎの識別子は（ＩＤＢ１，…，ＩＤＢｎ）である。
【０００４】
鍵生成手段９１０は、群Ｇの元ｇ２，ｇ３，ｈ１，…，ｈＬ、および０以上ｐ−１以下の整数ｓをランダムに選ぶ。そして、ｇ２＾ｓをマスタ秘密鍵とし、（ｇ，ｇ１＝ｇ＾ｓ，ｇ２，ｇ３，ｈ１，…，ｈＬ，ｇＴ，ｆ，Ｈ，Ｈ’）をマスタ公開鍵とし、マスタ公開鍵を公開する。
【０００５】
鍵生成手段９１０は、０以上ｐ−１以下の乱数ｒＡｍを生成し、
（（ｇ２＾ｓ）・（（ｈ１＾ＩＤＡ１）・…・（ｈｍ＾ＩＤＡｍ）・ｇ３）＾ｒＡｍ，ｇ＾ｒＡｍ，（ｈｍ＋１＾ｒＡｍ），…，（ｈＬ＾ｒＡｍ））＝（ｕＡ１，ｕＡ２，ｕＡ｜ｍ＋１，…，ｕＡ｜Ｌ）
を鍵交換装置Ａｍ９２０ｍ用の秘密鍵ｄＡｍとする。また、鍵生成手段９１０は、同様に０以上ｐ−１以下の乱数ｒＢｎを生成し、
（（ｇ２＾ｓ）・（（ｈ１＾ＩＤＢ１）・…・（ｈｎ＾ＩＤＢｎ）・ｇ３）＾ｒＢｎ，ｇ＾ｒＢｎ，（ｈｎ＋１＾ｒＢｎ），…，（ｈＬ＾ｒＢｎ））＝（ｕＢ１，ｕＢ２，ｕＢ｜ｎ＋１，…，ｕＢ｜Ｌ）
を鍵交換装置Ｂｎ９３０ｎ用の秘密鍵ｄＢｎとする。
【０００６】
このように鍵が生成された状態で、ユーザＵＡが使用する鍵交換装置ＡＭ９２０ＭとユーザＵＢが使用する鍵交換装置ＢＮ９３０Ｎとが共有鍵Ｋを共有する手順を次に示す。鍵交換装置ＡＭ９２０Ｍは、０以上ｐ−１以下の整数ｘをランダムに選び、短期秘密鍵とする。そして、
Ｘ１＝ｇ＾ｘ
Ｘ２＝（（ｈ１＾ＩＤＢ１）・…・（ｈＮ＾ＩＤＢＮ）・ｇ３）＾ｘ
Ｘ３＝ｇＴ＾ｘ
を計算し、（ＵＡ，Ｘ１，Ｘ２）を短期公開鍵として鍵交換装置ＢＮ９３０Ｎに送る。なお、Ｘ３は秘密情報として鍵交換装置ＡＭ９２０Ｍが保持する。
【０００７】
鍵交換装置ＢＮ９３０Ｎは、（ＵＡ，Ｘ１，Ｘ２）を受信する。鍵交換装置ＢＮ９３０Ｎは、０以上ｐ−１以下の整数ｙをランダムに選び、短期秘密鍵とする。そして、
Ｙ１＝ｇ＾ｙ
Ｙ２＝（（ｈ１＾ＩＤＡ１）・…・（ｈＭ＾ＩＤＡＭ）・ｇ３）＾ｙ
Ｙ３＝ｇＴ＾ｙ
を計算する。また、
ＫＡ＝ｅ（Ｘ１，ｕＢ１）／ｅ（ｕＢ２，Ｘ２）
＝ｅ（ｇ＾ｘ，（ｇ２＾ｓ）・（（ｈ１＾ＩＤＢ１）・…・（ｈＮ＾ＩＤＢＮ）・ｇ３）＾ｒＢＮ）／ｅ（ｇ＾ｒＢＮ，（（ｈ１＾ＩＤＢ１）・…・（ｈＮ＾ＩＤＢＮ）・ｇ３）＾ｘ）
＝ｅ（ｇ＾ｘ，ｇ２＾ｓ）
＝ｇＴ＾ｘ
を計算し、メッセージ認証子ｈを
ｈ＝ｆＨＡ（ＵＡ，ＵＢ，Ｙ１，Ｙ２）
ただし、ＨＡ＝Ｈ（ＫＡ）
のように計算する。そして、（Ｘ１，Ｙ１，Ｙ２，ｈ）を短期公開鍵として鍵交換装置ＡＭ９２０Ｍに送信する。また、鍵交換装置ＢＮ９３０Ｎは、共有鍵Ｋを、
Ｋ＝Ｈ’（ＫＡ＾ｙ）（＋）Ｈ’（ＫＡ・Ｙ３）
のように計算して求める。
【０００８】
鍵交換装置ＡＭ９２０Ｍは、（Ｘ１，Ｙ１，Ｙ２，ｈ）を受信する。鍵交換装置ＡＭ９２０Ｍは、メッセージ認証子ｈが、
ｆＨＸ（ＵＡ，ＵＢ，Ｙ１，Ｙ２）
ただし、ＨＸ＝Ｈ（Ｘ３）
と等しいことを確認する。そして、等しくない場合は、鍵交換装置ＡＭ９２０Ｍは処理を中止する。等しい場合は、鍵交換装置ＡＭ９２０Ｍは
ＫＢ＝ｅ（Ｙ１，ｕＡ１）／ｅ（ｕＡ２，Ｙ２）
＝ｅ（ｇ＾ｙ，（ｇ２＾ｓ）・（（ｈ１＾ＩＤＡ１）・…・（ｈＭ＾ＩＤＡＭ）・ｇ３）＾ｒＡＭ）／ｅ（ｇ＾ｒＡＭ，（（ｈ１＾ＩＤＡ１）・…・（ｈＭ＾ＩＤＡＭ）・ｇ３）＾ｙ）
＝ｅ（ｇ＾ｙ，ｇ２＾ｓ）
＝ｇＴ＾ｙ
を計算し、共有鍵Ｋを、
Ｋ＝Ｈ’（ＫＢ＾ｘ）（＋）Ｈ’（ＫＢ・Ｘ３）
のように計算して求める。
【０００９】
ここで、
ＫＡ＾ｙ＝ＫＢ＾ｘ＝ｇＴ＾（ｘｙ）
ＫＡ・Ｙ３＝ＫＢ・Ｘ３＝ｇＴ＾（ｘ＋ｙ）
なので、鍵交換装置ＡＭ９２０Ｍと鍵交換装置ＢＮ９３０Ｎとが求めた共有鍵Ｋは一致する。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】森山大輔, 土井洋, 趙晋輝, “A Two-Party Hierarchical Identity Based Key Agreement Protocol Without Random Oracles”,暗号と情報セキュリティシンポジウムSCIS2008 , 4D1-1,2008.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、従来技術は短期秘密鍵が漏れると安全でなくなるという課題がある。具体的には、攻撃者Ｃが、短期秘密鍵ｘ、ｙを取得したとすると、攻撃者Ｃは、
Ｋ＝Ｈ’（ｇＴ＾（ｘｙ））（＋）Ｈ’（ｇＴ＾（ｘ＋ｙ））
を計算することで、共有鍵Ｋを取得できる。
【００１２】
本発明は、攻撃者が短期秘密鍵を取得しても安全性を維持できる階層型ＩＤ認証鍵交換方式を提供することを目的とする。
【課題を解決するための手段】
【００１３】
まず、ｋは整数、ｐはｋビットの素数、ＧとＧＴは位数ｐの巡回群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形ペアリング関数、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈは任意長の整数をｋビットの整数に変換するハッシュ関数、Ｍ、Ｎは整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、ＩＤＡ，ｍとＩＤＢ，ｍは任意の整数、ｓ０とｓＡ，ｍとｓＢ，ｎはランダムに選択された０以上ｐ−１以下の整数、Ｓ０は群Ｇの単位元、Ｐ０＝ｇ、Ｑ０＝Ｐ０＾ｓ０、＾はべき乗を示す記号とする。そして、本発明の鍵交換装置は、識別子がＩＤＡ＝（ＩＤＡ，１，…，ＩＤＡ，Ｍ）であり、長期秘密鍵として（ＳＡ，Ｍ，ＱＡ，１，…，ＱＡ，Ｍ）を記録している。また、鍵交換を行う相手の鍵交換装置は、識別子がＩＤＢ＝（ＩＤＢ，１，…，ＩＤＢ，Ｎ）であり、長期秘密鍵として（ＳＢ，Ｎ，ＱＢ，１，…，ＱＢ，Ｎ）を記録している。そして、
ｓＡ，０＝ｓＢ，０＝ｓ０
ＳＡ，０＝ＳＢ，０＝Ｓ０
とすると、
１〜Ｍのすべてのｍと１〜Ｎのすべてのｎについて、
ＰＡ，ｍ＝Ｈ１（ＩＤＡ，１，…，ＩＤＡ，ｍ）
ＳＡ，ｍ＝ＳＡ，ｍ−１ＰＡ，ｍ＾ｓＡ，ｍ−１
ＱＡ，ｍ＝Ｐ０＾ｓＡ，ｍ
ＰＢ，ｎ＝Ｈ１（ＩＤＢ，１，…，ＩＤＢ，ｎ）
ＳＢ，ｎ＝ＳＢ，ｎ−１ＰＢ，ｎ＾ｓＢ，ｎ−１
ＱＢ，ｎ＝Ｐ０＾ｓＢ，ｎ
の関係である。なお、ＩＤＡ，Ｍ≠ＩＤＢ，Ｎであれば、ＩＤＡ，ｍ＝ＩＤＢ，ｎでもよい。
【００１４】
本発明の第１の鍵交換装置は、短期鍵生成部、短期公開鍵受信部、セッション鍵生成部を備える。短期鍵生成部は、０以上ｐ−１以下の整数の中からランダムに選択した整数を短期秘密鍵ｘ〜とし、ｘ＝Ｈ２（ＳＡ，Ｍ，ｘ〜）を計算し、（Ｐ０＾ｘ，ＰＢ，２＾ｘ，…，ＰＢ，Ｎ＾ｘ）を短期公開鍵ｅｐｋＢ＝（Ｘ０，ＸＢ，２，…，ＸＢ，Ｎ）とし、短期公開鍵ｅｐｋＢを相手の鍵交換装置（第２の鍵交換装置）に送信する。短期公開鍵受信部は、相手の鍵交換装置（第２の鍵交換装置）から、短期公開鍵ｅｐｋＡ＝（Ｙ０，ＹＡ，２，…，ＹＡ，Ｍ）を受信する。セッション鍵生成部は、
σ１＝ｅ（Ｑ０，ＰＢ，１）＾ｘ
【００１５】
【数１】
0005427156.tif 000002
【００１６】
σ３＝Ｙ０＾ｘ
を計算し、σ１，σ２，σ３とハッシュ関数Ｈを用いてセッション鍵Ｋを求める。
【００１７】
本発明の第２の鍵交換装置（第１の鍵交換装置の相手の鍵交換装置）も、短期鍵生成部、短期公開鍵受信部、セッション鍵生成部を備える。短期公開鍵受信部は、相手の鍵交換装置（第１の鍵交換装置）から、短期公開鍵ｅｐｋＢ＝（Ｘ０，ＸＢ，２，…，ＸＢ，Ｎ）を受信する。短期鍵生成部は、０以上ｐ−１以下の整数の中からランダムに選択した整数を短期秘密鍵ｙ〜とし、ｙ＝Ｈ２（ＳＢ，Ｎ，ｙ〜）を計算し、（Ｐ０＾ｙ，ＰＡ，２＾ｙ，…，ＰＡ，Ｍ＾ｙ）を短期公開鍵ｅｐｋＡ＝（Ｙ０，ＹＡ，２，…，ＹＡ，Ｍ）とし、短期公開鍵ｅｐｋＡを相手の鍵交換装置（第１の鍵交換装置）に送信する。セッション鍵生成部は、
【００１８】
【数２】
0005427156.tif 000003
【００１９】
σ２＝ｅ（Ｑ０，ＰＡ，１）＾ｙ
σ３＝Ｘ０＾ｙ
を計算し、σ１，σ２，σ３とハッシュ関数Ｈを用いてセッション鍵Ｋを求める。
【発明の効果】
【００２０】
本発明の鍵交換装置によれば、相手の鍵交換装置のＩＤに対応する短期公開鍵を計算する際に、短期秘密鍵をそのままべき乗するのではなく、長期秘密鍵と短期秘密鍵のハッシュ値をべき乗する。したがって、短期秘密鍵が漏れても、長期秘密鍵が漏れない限りハッシュ値の値は分からない。このように片方の秘密鍵が漏洩したとしても攻撃者は共有鍵を求めることができない。したがって、本発明の鍵交換装置は高い安全性を有している。
【図面の簡単な説明】
【００２１】
【図１】従来の階層型ＩＤ認証鍵交換方式のシステム構成を説明するための図。
【図２】実施例１の鍵交換装置の階層を示す図。
【図３】実施例１の鍵交換システムの機能構成例を示す図。
【図４】マスタ鍵生成手段の処理フローを示す図。
【図５】すべての鍵交換装置が長期秘密鍵を記録するまでの処理フローを示す図。
【図６】鍵を共有する処理のフローを示す図。
【図７】仮想的な階層構造を示す図。
【図８】変形例の鍵交換システムの機能構成例を示す図。
【発明を実施するための形態】
【００２２】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。また、以下の説明では、ｋは整数、ｐはｋビットの素数、ＧとＧＴは位数ｐの巡回群、ｇは群Ｇの生成元、ｇＴは群ＧＴの生成元、ｅはＧ×Ｇ→ＧＴのように写像する双線形ペアリング関数、Ｈ１は任意長の整数を群Ｇの元に変換するハッシュ関数、Ｈ２は任意長の整数を０以上ｐ−１以下の整数に変換するハッシュ関数、Ｈは任意長の整数をｋビットの整数に変換するハッシュ関数、Ｍ、Ｎは整数、ｍは１以上Ｍ以下の整数、ｎは１以上Ｎ以下の整数、ＩＤ＊，＊は任意の整数、ｓ０とｓ＊，＊はランダムに選択された０以上ｐ−１以下の整数、Ｓ０は群Ｇの単位元、Ｐ０＝ｇ、Ｑ０＝Ｐ０＾ｓ０、＾はべき乗を示す記号とする。
【実施例１】
【００２３】
図２に実施例１の鍵交換装置の階層を示す。最上位の階層（階層１）に１つ以上の鍵交換装置があり、これらの鍵交換装置は識別子として、１つのＩＤ＊，＊を有する。例えば、鍵交換装置Ａ１１２０１は、識別子としてＩＤＡ，１を有する。上位側からｍ番目の階層（階層ｍ）の鍵交換装置は、上位の鍵交換装置が有する識別子に１つの識別子ＩＤ＊，＊を加えたものを識別子として有する。例えば、鍵交換装置Ａ２１２０２は、識別子として（ＩＤＡ，１，ＩＤＡ，２）を有する。そして、上位側からＭ番目の階層（階層Ｍ）に属する鍵交換装置ＡＭ１２０Ｍは、識別子として（ＩＤＡ，１，ＩＤＡ，２，…，ＩＤＡ，Ｍ）を有する。また、上位側からＮ番目の階層（階層Ｎ）に属する鍵交換装置ＢＮ１３０Ｎは、識別子として（ＩＤＢ，１，ＩＤＢ，２，…，ＩＤＢ，Ｎ）を有する。本実施例では、共有鍵を共有する処理を行う鍵交換装置ＡＭ１２０Ｍと鍵交換装置ＢＮ１３０Ｎとは異なる鍵交換装置であることは言うまでもない。しかし、鍵交換装置ＡＭ１２０Ｍと鍵交換装置ＢＮ１３０Ｎの上位の鍵交換装置が同一であってもかまわない。例えば、上位からＩ番目の階層（階層Ｉ：ただし、Ｉは１以上Ｍ未満かつＮ未満の整数）までの鍵交換装置が同一であり、Ｉ＋１番目の階層から異なる場合もある。このときは、（ＩＤＡ，１，ＩＤＡ，２，…，ＩＤＡ，Ｉ）と（ＩＤＢ，１，ＩＤＢ，２，…，ＩＤＢ，Ｉ）は同じである。
【００２４】
図３は、実施例１の鍵交換システムの機能構成例を示す図である。鍵交換システムは、ネットワーク１０００で接続されたマスタ鍵生成手段１１０と複数の鍵交換装置で構成されている。図３では、本実施例の説明に必要な範囲の鍵交換装置を示しているが、この他にも鍵交換装置を備えてもよい。また、説明の都合上、鍵交換装置Ａ１１２０１〜鍵交換装置ＡＭ１２０Ｍと鍵交換装置Ｂ１１３０１〜鍵交換装置ＢＮ１３０Ｎを別々の装置として示している。しかし、上述のとおり、（ＩＤＡ，１，ＩＤＡ，２，…，ＩＤＡ，Ｉ）と（ＩＤＢ，１，ＩＤＢ，２，…，ＩＤＢ，Ｉ）とが同じ場合には、鍵交換装置Ａｉ１２０ｉと鍵交換装置Ｂｉ１３０ｉ（ただし、ｉは１以上Ｉ以下の整数）は、同じ装置である。
【００２５】
図４は、マスタ鍵生成手段の処理フローを示す図である。マスタ鍵生成手段１１０は、０以上ｐ−１以下の整数から１つを選定してマスタ秘密鍵ｓ０を生成する（Ｓ１１０）。そして、Ｓ０を群Ｇの単位元に設定し、Ｐ０とＱ０をＰ０＝ｇ、Ｑ０＝Ｐ０＾ｓ０のように求め、前記のＰ０とＱ０を公開する（Ｓ１１２）。次に、マスタ鍵生成手段１１０は、最上位の階層の鍵交換装置ごとに、Ｐ１、Ｓ１を求める（Ｓ１１３）。そして、最上位の階層のすべての鍵交換装置のためのＰ１、Ｓ１を求めたかを確認する（Ｓ１１４）。ステップＳ１１４がＮｏの場合には、最上位の階層の別の鍵交換装置に対象を変更し（Ｓ１１５）、ステップＳ１１３に戻る。図３の例の場合であれば、最上位の階層の鍵交換装置Ａ１１２０１のためのＰ１、Ｓ１であるＰＡ，１、ＳＡ，１を、
ＰＡ，１＝Ｈ１（ＩＤＡ，１）
ＳＡ，１＝Ｓ０ＰＡ，１＾ｓ０
のように計算する（Ｓ１１３）。そして、ＩＤＢ，１≠ＩＤＡ，１の場合（Ｓ１１４がＮｏの場合）は、対象を鍵交換装置Ｂ１１３０１に変更し（Ｓ１１５）、鍵交換装置Ｂ１１３０１のためのＰ１、Ｓ１であるＰB，１、ＳB，１を、
ＰＢ，１＝Ｈ１（ＩＤＢ，１）
ＳＢ，１＝Ｓ０ＰＢ，１＾ｓ０
のように計算する（Ｓ１１３）。
【００２６】
図５は、すべての鍵交換装置が長期秘密鍵を記録するまでの処理フローを示す図である。図３に示したように、鍵交換装置Ａｍ１２０ｍは、短期鍵生成部１２１ｍ、短期公開鍵受信部１２２ｍ、セッション鍵生成部１２３ｍ、乱数生成部１２４ｍ、情報取得部１２５ｍ、長期秘密鍵計算部１２６ｍ、記録部１２９ｍを備える。なお、乱数生成部１２４ｍ、情報取得部１２５ｍ、長期秘密鍵計算部１２６ｍで長期秘密鍵生成部１４２ｍを構成している。同様に、鍵交換装置Ｂｎ１３０ｎは、短期鍵生成部１３１ｎ、短期公開鍵受信部１３２ｎ、セッション鍵生成部１３３ｎ、乱数生成部１３４ｎ、情報取得部１３５ｎ、長期秘密鍵計算部１３６ｎ、記録部１３９ｎを備える。なお、乱数生成部１３４ｎ、情報取得部１３５ｎ、長期秘密鍵計算部１３６ｎで長期秘密鍵生成部１４３ｎを構成している。
【００２７】
乱数生成部１２４ｍは、０以上ｐ−１以下の整数の中からランダムに整数を選択し、鍵交換装置Ａｍ１２０ｍ用のｓｍであるｓＡ，ｍを生成する（Ｓ１４１）。情報取得部１２５ｍがＳＡ，ｍ，ＱＡ，１，…，ＱＡ，ｍ−１を取得し、長期秘密鍵計算部１２６ｍがＱＡ，ｍ＝Ｐ０＾ｓＡ，ｍのように、鍵交換装置Ａｍ１２０ｍ用のＱｍであるＱＡ，ｍを求める（Ｓ１４２）。鍵交換装置Ａｍ１２０ｍは、下位の階層に配下の鍵交換装置があるかを確認する（Ｓ１４３）。ステップＳ１４３がＮｏの場合は、後述するステップＳ１４７に進む。ステップＳ１４３がＹｅｓの場合は、長期秘密鍵計算部１２６ｍは、１つ下位の配下の鍵交換装置Ａｍ＋１１２０ｍ＋１（識別子がＩＤＡ，１，…，ＩＤＡ，ｍ，ＩＤＡ，ｍ＋１）用のＰｍ＋１、Ｓｍ＋１であるＰＡ，ｍ＋１、ＳＡ，ｍ＋１を求めるために、
ＰＡ，ｍ＋１＝Ｈ１（ＩＤＡ，１，…，ＩＤＡ，ｍ，ＩＤＡ，ｍ＋１）
ＳＡ，ｍ＋１＝ＳＡ，ｍＰＡ，ｍ＋１＾ｓＡ，ｍ
を計算する（Ｓ１４４）。鍵交換装置Ａｍ１２０ｍは、１つ下位の階層の配下の鍵交換装置のためのＰｍ＋１、Ｓｍ＋１をすべて求めたかを確認する（Ｓ１４５）。ステップＳ１４５がＮｏの場合には、対象を１つ下位の階層の配下の別の鍵交換装置に変更し（Ｓ１４６）、ステップＳ１４４を行う。ステップＳ１４５がＹｅｓの場合には、ステップＳ１４７に進む。長期秘密鍵計算部１２６ｍは、（ＳＡ，ｍ，ＱＡ，１，…，ＱＡ，ｍ）を鍵交換装置Ａｍ１２０ｍの長期秘密鍵とする（Ｓ１４７）。ステップＳ１４１〜Ｓ１４７が長期秘密鍵生成部１４２ｍ（１台の鍵交換装置の長期秘密鍵生成部）が行う処理（Ｓ１４０）である。
【００２８】
鍵交換システムのいずれかの装置が、すべての鍵交換装置がステップＳ１４０の処理を実行したかを確認する（Ｓ１４８）。ステップＳ１４８がＮｏの場合は、上位側の鍵交換装置であってステップＳ１４０を実行していない鍵交換装置に対象を変更し（Ｓ１４９）、ステップＳ１４０を実行する。この処理を繰り返すことで、ステップＳ１４８がＹｅｓになり、すべての鍵交換装置が長期秘密鍵を記録した状態となる。このとき、鍵交換装置Ａｍ１２０ｍは、識別子が（ＩＤＡ，１，…，ＩＤＡ，ｍ）であり、長期秘密鍵として（ＳＡ，ｍ，ＱＡ，１，…，ＱＡ，ｍ）を記録しており、鍵交換装置Ｂｎ１３０ｎは、（ＩＤＢ，１，…，ＩＤＢ，ｎ）であり、長期秘密鍵として（ＳＢ，ｎ，ＱＢ，１，…，ＱＢ，ｎ）を記録している。そして、
ｓＡ，０＝ｓＢ，０＝ｓ０
ＳＡ，０＝ＳＢ，０＝Ｓ０
とすると、
１〜Ｍのすべてのｍと１〜Ｎのすべてのｎについて、
ＰＡ，ｍ＝Ｈ１（ＩＤＡ，１，…，ＩＤＡ，ｍ）
ＳＡ，ｍ＝ＳＡ，ｍ−１ＰＡ，ｍ＾ｓＡ，ｍ−１
ＱＡ，ｍ＝Ｐ０＾ｓＡ，ｍ
ＰＢ，ｎ＝Ｈ１（ＩＤＢ，１，…，ＩＤＢ，ｎ）
ＳＢ，ｎ＝ＳＢ，ｎ−１ＰＢ，ｎ＾ｓＢ，ｎ−１
ＱＢ，ｎ＝Ｐ０＾ｓＢ，ｎ
が成り立つ関係となっている。
【００２９】
図６に、鍵を共有する処理のフローを示す。この処理では、鍵交換装置ＡＭ１２０Ｍと鍵交換装置ＢＮ１３０Ｎとが鍵交換を行う。上述のとおり、鍵交換装置ＡＭ１２０Ｍは、識別子がＩＤＡ＝（ＩＤＡ，１，…，ＩＤＡ，Ｍ）であり、長期秘密鍵として（ＳＡ，Ｍ，ＱＡ，１，…，ＱＡ，Ｍ）を記録しており、鍵交換装置ＢＮ１３０Ｎは、識別子がＩＤＢ＝（ＩＤＢ，１，…，ＩＤＢ，Ｎ）であり、長期秘密鍵として（ＳＢ，Ｎ，ＱＢ，１，…，ＱＢ，Ｎ）を記録している。
【００３０】
鍵交換装置ＡＭ１２０Ｍの短期鍵生成部１２１Ｍは、０以上ｐ−１以下の整数の中からランダムに選択した整数を短期秘密鍵ｘ〜とし、ｘ＝Ｈ２（ＳＡ，Ｍ，ｘ〜）を計算し、（Ｐ０＾ｘ，ＰＢ，２＾ｘ，…，ＰＢ，Ｎ＾ｘ）を短期公開鍵ｅｐｋＢ＝（Ｘ０，ＸＢ，２，…，ＸＢ，Ｎ）とし、短期公開鍵ｅｐｋＢを鍵交換装置ＢＮ１３０Ｎに送信する（Ｓ１２１）。
【００３１】
鍵交換装置ＢＮ１３０Ｎの短期公開鍵受信部１３２Ｎは、鍵交換装置ＡＭ１２０Ｍから短期公開鍵ｅｐｋＢ＝（Ｘ０，ＸＢ，２，…，ＸＢ，Ｎ）を受信する（Ｓ１３２）。鍵交換装置ＢＮ１３０Ｎの短期鍵生成部１３１Ｎは、０以上ｐ−１以下の整数の中からランダムに選択した整数を短期秘密鍵ｙ〜とし、ｙ＝Ｈ２（ＳＢ，Ｎ，ｙ〜）を計算し、（Ｐ０＾ｙ，ＰＡ，２＾ｙ，…，ＰＡ，Ｍ＾ｙ）を短期公開鍵ｅｐｋＡ＝（Ｙ０，ＹＡ，２，…，ＹＡ，Ｍ）とし、短期公開鍵ｅｐｋＡを鍵交換装置ＡＭ１２０Ｍに送信する（Ｓ１３１）。
【００３２】
鍵交換装置ＡＭ１２０Ｍの短期公開鍵受信部１２２Ｍは、鍵交換装置ＢＮ１３０Ｎから短期公開鍵ｅｐｋＡ＝（Ｙ０，ＹＡ，２，…，ＹＡ，Ｍ）を受信する（Ｓ１２２）。
鍵交換装置ＡＭ１２０Ｍのセッション鍵生成部１２３Ｍは、
σ１＝ｅ（Ｑ０，ＰＢ，１）＾ｘ
【００３３】
【数３】
0005427156.tif 000004
【００３４】
σ３＝Ｙ０＾ｘ
を計算し、σ１，σ２，σ３とハッシュ関数Ｈを用いてセッション鍵Ｋを求める。例えば、
Ｋ＝Ｈ（σ１，σ２，σ３，ＰＩＤ，ＩＤＡ，ＩＤＢ，ｅｐｋＡ，ｅｐｋＢ）
ただし、ＰＩＤは本実施例のプロトコルを示す識別子
のようにセッション鍵Ｋを求めればよい。
【００３５】
鍵交換装置ＢＮ１３０Ｎのセッション鍵生成部１３３Ｎは、
【００３６】
【数４】
0005427156.tif 000005
【００３７】
σ２＝ｅ（Ｑ０，ＰＡ，１）＾ｙ
σ３＝Ｘ０＾ｙ
を計算し、セッション鍵生成部１２３Ｍと同じようにσ１，σ２，σ３とハッシュ関数Ｈを用いてセッション鍵Ｋを求める。例えば、
Ｋ＝Ｈ（σ１，σ２，σ３，ＰＩＤ，ＩＤＡ，ＩＤＢ，ｅｐｋＡ，ｅｐｋＢ）
のようにセッション鍵Ｋを求めればよい。このように処理することによって、セッション鍵Ｋを共有できる。なお、
【００３８】
【数５】
0005427156.tif 000006
【００３９】
σ３＝Ｘ０＾ｙ＝Ｙ０＾ｘ＝Ｐ０＾（ｘｙ）
である。したがって、鍵交換装置ＡＭ１２０Ｍが計算するセッション鍵Ｋと鍵交換装置ＢＮ１３０Ｎが計算するセッション鍵Ｋとは等しくなる。
【００４０】
なお、鍵交換装置ＡＭ１２０Ｍと鍵交換装置ＢＮ１３０Ｎの処理が逆でもよい。また、鍵交換装置ＡＭ１２０Ｍは別の鍵交換装置と鍵交換を行う場合には、鍵交換装置ＡＭ１２０Ｍが上述の鍵交換装置ＢＮ１３０Ｎの処理を行うこともあり得る。したがって、セッション鍵生成部１２３Ｍは、
【００４１】
【数６】
0005427156.tif 000007
【００４２】
σ２＝ｅ（Ｑ０，ＰＢ，１）＾ｘ
σ３＝Ｙ０＾ｘ
のようにσ１，σ２，σ３を求めることもできるようにすればよい。そして、この場合は、どちらの方法でσ１，σ２，σ３を求めるかは、鍵交換システムのルールとしてあらかじめ定めておけばよい。
【００４３】
本実施例の鍵交換装置によれば、相手の鍵交換装置のＩＤに対応する短期公開鍵を計算する際に、短期秘密鍵をそのままべき乗するのではなく、長期秘密鍵と短期秘密鍵のハッシュ値をべき乗する。したがって、短期秘密鍵が漏れても、長期秘密鍵が漏れない限りハッシュ値の値は分からない。このように片方の秘密鍵が漏洩したとしても攻撃者は共有鍵を求めることができない。したがって、本発明の鍵交換装置は高い安全性を有している。
【００４４】
［変形例１］
実施例１では、各鍵交換装置１２０ｍ，１３０ｎが長期秘密鍵生成部１４２ｍ，１４３ｎを備え、長期秘密鍵生成部１４２１，…，１４２Ｍ，１４３１，…，１４３Ｎのすべてを合わせたものが、鍵交換システムの長期秘密鍵生成手段であった。しかし、長期秘密鍵生成部１４２１，…，１４２Ｍ，１４３１，…，１４３Ｎを１つの装置にまとめてもよいし、何個かに分散させてもよい。また、識別子がＩＤＡ＝（ＩＤＡ，１，…，ＩＤＡ，Ｍ）の鍵交換装置ＡＭ１２０Ｍと識別子がＩＤＢ＝（ＩＤＢ，１，…，ＩＤＢ，Ｎ）の鍵交換装置ＢＮ１３０Ｎとが鍵交換を行うときに、他の鍵交換装置は必要ない。そして、何らかの方法で、鍵交換装置ＡＭ１２０Ｍが長期秘密鍵（ＳＡ，ｍ，ＱＡ，１，…，ＱＡ，ｍ）を記録し、鍵交換装置ＢＮ１３０Ｎが長期秘密鍵（ＳＢ，ｎ，ＱＢ，１，…，ＱＢ，ｎ）を記録していれば、鍵交換を行うことができる。さらに、マスタ鍵生成手段と長期秘密鍵生成手段は、鍵交換システムの外部の装置が備え、必要に応じてネットワークを介して接続してもよい。
【００４５】
図７は、仮想的な階層構造を示す図であり、点線で示した装置は実在しなくてもよい。鍵交換装置ＡＭ１２０Ｍと鍵交換装置ＢＮ１３０Ｎとは、このような仮想的な階層構造での識別子を有していてもよいし、実在する鍵交換装置によって形成された階層構造での識別子を有していてもよい。図８に示すように鍵交換システムが、マスタ鍵生成手段１１０、鍵交換装置ＡＭ２２０Ｍ、鍵交換装置ＢＮ２３０Ｎ、長期秘密鍵生成手段２４０を備えればよい。本変形例では、鍵交換装置ＡＭ２２０Ｍの長期秘密鍵も鍵交換装置ＢＮ２３０Ｎの長期秘密鍵も、長期秘密鍵生成手段２４０が生成する。したがって、鍵交換装置ＡＭ２２０Ｍと鍵交換装置ＢＮ２３０Ｎは、長期秘密鍵生成部１４２Ｍ，１４３Ｎを備えていない。長期秘密鍵生成手段２４０は、乱数生成部１４４、情報取得部１４５、長期秘密鍵計算部１４６、記録部１４９を備えている。
【００４６】
本変形例では、情報取得部１４５が、マスタ鍵生成手段１１０が生成した最上位の階層の鍵交換装置用のすべてのＰ１とＳ１を取得した上で、図５の処理フローすべてを長期秘密鍵生成手段２４０が行う。図５の処理が終了したときには、鍵交換装置ＡＭ１２０Ｍは長期秘密鍵（ＳＡ，Ｍ，ＱＡ，１，…，ＱＡ，Ｍ）を記録しており、鍵交換装置ＢＮ１３０Ｎは、長期秘密鍵（ＳＢ，Ｎ，ＱＢ，１，…，ＱＢ，Ｎ）を記録している。そして、
ｓＡ，０＝ｓＢ，０＝ｓ０
ＳＡ，０＝ＳＢ，０＝Ｓ０
とすると、
１〜Ｍのすべてのｍと１〜Ｎのすべてのｎについて、
ＰＡ，ｍ＝Ｈ１（ＩＤＡ，１，…，ＩＤＡ，ｍ）
ＳＡ，ｍ＝ＳＡ，ｍ−１ＰＡ，ｍ＾ｓＡ，ｍ−１
ＱＡ，ｍ＝Ｐ０＾ｓＡ，ｍ
ＰＢ，ｎ＝Ｈ１（ＩＤＢ，１，…，ＩＤＢ，ｎ）
ＳＢ，ｎ＝ＳＢ，ｎ−１ＰＢ，ｎ＾ｓＢ，ｎ−１
ＱＢ，ｎ＝Ｐ０＾ｓＢ，ｎ
が成り立つ関係となっている。
【００４７】
鍵を共有する処理のフローは図６と同じであり、実施例１とまったく同じなので説明は省略する。本変形例の場合も、鍵交換装置ＡＭ１２０Ｍが長期秘密鍵（ＳＡ，ｍ，ＱＡ，１，…，ＱＡ，ｍ）を記録し、鍵交換装置ＢＮ１３０Ｎが長期秘密鍵（ＳＢ，ｎ，ＱＢ，１，…，ＱＢ，ｎ）を記録しているので、実施例１と同じ鍵交換を実行でき、同じ効果が得られる。
【００４８】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４９】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００５０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００５４】
１１０  マスタ鍵生成手段
１２０、１３０、２２０、２３０、９２０、９３０  鍵交換装置
１２１、１３１  短期鍵生成部            １２２、１３２  短期公開鍵受信部
１２３、１３３  セッション鍵生成部      １２４、１３４  乱数生成部
１２５、１３５  情報取得部              １２６、１３６  長期秘密鍵計算部
１２９、１３９  記録部                  １４２、１４３  長期秘密鍵生成部
１４４  乱数生成部                      １４５  情報取得部
１４６  長期秘密鍵計算部                １４９  記録部
２４０  長期秘密鍵生成手段              ９１０  鍵生成手段
１０００  ネットワーク
【図１】
0005427156.tif 000013
【図２】
0005427156.tif 000014
【図３】
0005427156.tif 000015
【図４】
0005427156.tif 000016
【図５】
0005427156.tif 000017
【図６】
0005427156.tif 000018
【図７】
0005427156.tif 000019
【図８】
0005427156.tif 000020