(57)【要約】  本発明の鍵交換装置は、記憶部２５０および演算制御部２６０を備え、ネットワークを介して外部の相手装置と鍵交換処理を次のように行う。演算制御部２６０は、乱数、秘密鍵、自己公開鍵、相手公開鍵、初期セッション番号および開始指示が入力されると、第１のセッション番号および第１のハッシュ値を生成し、第１のセッション番号および第１のハッシュ値を含む開始者メッセージを相手装置に送信し、相手装置から開始者メッセージを受信する場合、生成した第２のハッシュ値と第１のハッシュ値とが一致していれば、生成した返答者セッション番号を第１のセッション番号に追加した第２のセッション番号の情報を用いて第３のハッシュ値を生成して鍵として格納し、第２のセッション番号および第３のハッシュ値を含む返答者メッセージを生成して相手装置に送信し、相手装置から返答者メッセージを受信する場合、生成した第４のハッシュ値と第３のハッシュ値とが一致していれば、第５のハッシュ値を生成して鍵として記憶部２５０に格納する。
2008099875.tif 000002
【特許請求の範囲】
【請求項１】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行う鍵交換装置であって、
前記演算制御部は、
乱数、秘密鍵、自装置の公開鍵である自己公開鍵、前記相手装置の公開鍵である相手公開鍵、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己公開鍵、および前記相手公開鍵を含む第１のセッション番号を生成し、該第１のセッション番号の情報、前記乱数、および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号および前記第１のハッシュ値を含む開始者メッセージを前記相手装置に送信し、
前記相手装置から前記開始者メッセージを受信する場合、前記第１のセッション番号の情報を用いて生成した第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、該返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号の情報を用いて第３のハッシュ値を生成し、該第３のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号および前記第３のハッシュ値を含む返答者メッセージを生成して前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報を用いて第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納する、鍵交換装置。
【請求項２】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行う鍵交換装置であって、
前記演算制御部は、
乱数、秘密鍵、自装置の公開鍵である自己公開鍵、前記相手装置の公開鍵である相手公開鍵、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己公開鍵、および前記相手公開鍵を含む第１のセッション番号を生成し、該第１のセッション番号の情報、前記乱数、および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号および前記第１のハッシュ値を含む第１の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第１の開始者メッセージを受信する場合、前記第１のセッション番号の情報を用いて生成した第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、該返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号の情報を用いて第３のハッシュ値を生成し、該第３のハッシュ値に含まれる演算結果を前記記憶部に格納し、前記第２のセッション番号および前記第３のハッシュ値を含む返答者メッセージを生成して前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報を用いて第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号および前記第５のハッシュ値を含む第２の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第２の開始者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第６のハッシュ値と前記第５のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記演算結果および前記第２のセッション番号の情報を用いて第６のハッシュ値を生成し、該第６のハッシュ値を鍵として前記記憶部に格納する、鍵交換装置。
【請求項３】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行う鍵交換装置であって、
前記演算制御部は、
乱数、秘密鍵、自装置の識別子である自己装置番号、前記相手装置の識別子である相手装置番号、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己装置番号、および前記相手装置番号を含む第１のセッション番号を生成し、該第１のセッション番号の情報および前記乱数を用いて第１の暗号文を生成し、前記第１のセッション番号の情報および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号、前記第１の暗号文および前記第１のハッシュ値を含む開始者メッセージを前記相手装置に送信し、
前記相手装置から前記開始者メッセージを受信する場合、前記第１のセッション番号の情報および前記秘密鍵を用いて前記第１の暗号文を復号し、該復号の結果を含む第２のハッシュ値を生成し、該第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、該返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号を生成し、該第２のセッション番号の情報および前記乱数を用いて第２の暗号文を生成し、前記第２のセッション番号の情報および前記秘密鍵を含む第３のハッシュ値を生成し、該第３のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号、前記第２の暗号文および前記第３のハッシュ値を含む返答者メッセージを前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報および前記秘密鍵を用いて前記第２の暗号文を復号し、該復号の結果を含む第４のハッシュ値を生成し、該第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報および前記秘密鍵を含む第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納する、鍵交換装置。
【請求項４】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行う鍵交換装置であって、
前記演算制御部は、
乱数、秘密鍵、自装置の識別子である自己装置番号、前記相手装置の識別子である相手装置番号、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己装置番号、および前記相手装置番号を含む第１のセッション番号を生成し、該第１のセッション番号の情報および前記乱数を用いて第１の暗号文を生成し、前記第１のセッション番号の情報および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号、前記第１の暗号文および前記第１のハッシュ値を含む第１の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第１の開始者メッセージを受信する場合、前記第１のセッション番号の情報および前記秘密鍵を用いて前記第１の暗号文を復号し、該復号の結果を含む第２のハッシュ値を生成し、該第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、該返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号を生成し、該第２のセッション番号の情報および前記乱数を用いて第２の暗号文を生成し、前記第２のセッション番号の情報および前記秘密鍵を含む第３のハッシュ値を生成し、該第３のハッシュ値に含まれる演算結果を前記記憶部に格納し、前記第２のセッション番号、前記第２の暗号文および前記第３のハッシュ値を含む返答者メッセージを前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報および前記秘密鍵を用いて前記第２の暗号文を復号し、該復号の結果を含む第４のハッシュ値を生成し、該第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報および前記秘密鍵を含む第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号および前記第５のハッシュ値を含む第２の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第２の開始者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第６のハッシュ値と前記第５のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記演算結果および前記第２のセッション番号の情報を用いて第６のハッシュ値を生成し、該第６のハッシュ値を鍵として前記記憶部に格納する、鍵交換装置。
【請求項５】
請求の範囲１から４のいずれか１項記載の鍵交換装置が複数設けられた鍵交換処理システム。
【請求項６】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行う鍵交換装置の前記演算制御部が実行する鍵交換方法であって、
乱数、秘密鍵、自装置の公開鍵である自己公開鍵、前記相手装置の公開鍵である相手公開鍵、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己公開鍵、および前記相手公開鍵を含む第１のセッション番号を生成し、
前記第１のセッション番号の情報、前記乱数、および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号および前記第１のハッシュ値を含む開始者メッセージを前記相手装置に送信し、
前記相手装置から前記開始者メッセージを受信する場合、前記第１のセッション番号の情報を用いて生成した第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、
前記返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号の情報を用いて第３のハッシュ値を生成し、該第３のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号および前記第３のハッシュ値を含む返答者メッセージを生成して前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報を用いて第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納する、鍵交換方法。
【請求項７】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行う鍵交換装置の前記演算制御部が実行する鍵交換方法であって、
乱数、秘密鍵、自装置の公開鍵である自己公開鍵、前記相手装置の公開鍵である相手公開鍵、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己公開鍵、および前記相手公開鍵を含む第１のセッション番号を生成し、
前記第１のセッション番号の情報、前記乱数、および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号および前記第１のハッシュ値を含む第１の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第１の開始者メッセージを受信する場合、前記第１のセッション番号の情報を用いて生成した第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、
前記返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号の情報を用いて第３のハッシュ値を生成し、該第３のハッシュ値に含まれる演算結果を前記記憶部に格納し、前記第２のセッション番号および前記第３のハッシュ値を含む返答者メッセージを生成して前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報を用いて第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号および前記第５のハッシュ値を含む第２の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第２の開始者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第６のハッシュ値と前記第５のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記演算結果および前記第２のセッション番号の情報を用いて第６のハッシュ値を生成し、該第６のハッシュ値を鍵として前記記憶部に格納する、鍵交換方法。
【請求項８】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行う鍵交換装置の前記演算制御部が実行する鍵交換方法であって、
乱数、秘密鍵、自装置の識別子である自己装置番号、前記相手装置の識別子である相手装置番号、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己装置番号、および前記相手装置番号を含む第１のセッション番号を生成し、
前記第１のセッション番号の情報および前記乱数を用いて第１の暗号文を生成し、前記第１のセッション番号の情報および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号、前記第１の暗号文および前記第１のハッシュ値を含む開始者メッセージを前記相手装置に送信し、
前記相手装置から前記開始者メッセージを受信する場合、前記第１のセッション番号の情報および前記秘密鍵を用いて前記第１の暗号文を復号し、該復号の結果を含む第２のハッシュ値を生成し、該第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、該返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号を生成し、
前記第２のセッション番号の情報および前記乱数を用いて第２の暗号文を生成し、前記第２のセッション番号の情報および前記秘密鍵を含む第３のハッシュ値を生成し、該第３のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号、前記第２の暗号文および前記第３のハッシュ値を含む返答者メッセージを前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報および前記秘密鍵を用いて前記第２の暗号文を復号し、該復号の結果を含む第４のハッシュ値を生成し、該第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報および前記秘密鍵を含む第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納する、鍵交換方法。
【請求項９】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行う鍵交換装置の前記演算制御部が実行する鍵交換方法であって、
乱数、秘密鍵、自装置の識別子である自己装置番号、前記相手装置の識別子である相手装置番号、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己装置番号、および前記相手装置番号を含む第１のセッション番号を生成し、
前記第１のセッション番号の情報および前記乱数を用いて第１の暗号文を生成し、前記第１のセッション番号の情報および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号、前記第１の暗号文および前記第１のハッシュ値を含む第１の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第１の開始者メッセージを受信する場合、前記第１のセッション番号の情報および前記秘密鍵を用いて前記第１の暗号文を復号し、該復号の結果を含む第２のハッシュ値を生成し、該第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、該返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号を生成し、
前記第２のセッション番号の情報および前記乱数を用いて第２の暗号文を生成し、前記第２のセッション番号の情報および前記秘密鍵を含む第３のハッシュ値を生成し、該第３のハッシュ値に含まれる演算結果を前記記憶部に格納し、前記第２のセッション番号、前記第２の暗号文および前記第３のハッシュ値を含む返答者メッセージを前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報および前記秘密鍵を用いて前記第２の暗号文を復号し、該復号の結果を含む第４のハッシュ値を生成し、該第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報および前記秘密鍵を含む第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号および前記第５のハッシュ値を含む第２の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第２の開始者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第６のハッシュ値と前記第５のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記演算結果および前記第２のセッション番号の情報を用いて第６のハッシュ値を生成し、該第６のハッシュ値を鍵として前記記憶部に格納する、鍵交換方法。
【請求項１０】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行うコンピュータの前記演算制御部に実行させるためのプログラムであって、
乱数、秘密鍵、自装置の公開鍵である自己公開鍵、前記相手装置の公開鍵である相手公開鍵、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己公開鍵、および前記相手公開鍵を含む第１のセッション番号を生成し、
前記第１のセッション番号の情報、前記乱数、および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号および前記第１のハッシュ値を含む開始者メッセージを前記相手装置に送信し、
前記相手装置から前記開始者メッセージを受信する場合、前記第１のセッション番号の情報を用いて生成した第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、
前記返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号の情報を用いて第３のハッシュ値を生成し、該第３のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号および前記第３のハッシュ値を含む返答者メッセージを生成して前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報を用いて第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納する処理を前記演算制御部に実行させるためのプログラム。
【請求項１１】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行うコンピュータの前記演算制御部に実行させるためのプログラムであって、
乱数、秘密鍵、自装置の公開鍵である自己公開鍵、前記相手装置の公開鍵である相手公開鍵、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己公開鍵、および前記相手公開鍵を含む第１のセッション番号を生成し、
前記第１のセッション番号の情報、前記乱数、および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号および前記第１のハッシュ値を含む第１の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第１の開始者メッセージを受信する場合、前記第１のセッション番号の情報を用いて生成した第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、
前記返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号の情報を用いて第３のハッシュ値を生成し、該第３のハッシュ値に含まれる演算結果を前記記憶部に格納し、前記第２のセッション番号および前記第３のハッシュ値を含む返答者メッセージを生成して前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報を用いて第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号および前記第５のハッシュ値を含む第２の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第２の開始者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第６のハッシュ値と前記第５のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記演算結果および前記第２のセッション番号の情報を用いて第６のハッシュ値を生成し、該第６のハッシュ値を鍵として前記記憶部に格納する処理を前記演算制御部に実行させるためのプログラム。
【請求項１２】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行うコンピュータの前記演算制御部に実行させるためのプログラムであって、
乱数、秘密鍵、自装置の識別子である自己装置番号、前記相手装置の識別子である相手装置番号、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己装置番号、および前記相手装置番号を含む第１のセッション番号を生成し、
前記第１のセッション番号の情報および前記乱数を用いて第１の暗号文を生成し、前記第１のセッション番号の情報および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号、前記第１の暗号文および前記第１のハッシュ値を含む開始者メッセージを前記相手装置に送信し、
前記相手装置から前記開始者メッセージを受信する場合、前記第１のセッション番号の情報および前記秘密鍵を用いて前記第１の暗号文を復号し、該復号の結果を含む第２のハッシュ値を生成し、該第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、該返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号を生成し、
前記第２のセッション番号の情報および前記乱数を用いて第２の暗号文を生成し、前記第２のセッション番号の情報および前記秘密鍵を含む第３のハッシュ値を生成し、該第３のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号、前記第２の暗号文および前記第３のハッシュ値を含む返答者メッセージを前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報および前記秘密鍵を用いて前記第２の暗号文を復号し、該復号の結果を含む第４のハッシュ値を生成し、該第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報および前記秘密鍵を含む第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納する処理を前記演算制御部に実行させるためのプログラム。
【請求項１３】
記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行うコンピュータの前記演算制御部に実行させるためのプログラムであって、
乱数、秘密鍵、自装置の識別子である自己装置番号、前記相手装置の識別子である相手装置番号、初期セッション番号および開始指示が入力されると、前記初期セッション番号、該初期セッション番号と異なる開始者セッション番号、前記自己装置番号、および前記相手装置番号を含む第１のセッション番号を生成し、
前記第１のセッション番号の情報および前記乱数を用いて第１の暗号文を生成し、前記第１のセッション番号の情報および前記秘密鍵を用いて第１のハッシュ値を生成し、前記第１のセッション番号、前記第１の暗号文および前記第１のハッシュ値を含む第１の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第１の開始者メッセージを受信する場合、前記第１のセッション番号の情報および前記秘密鍵を用いて前記第１の暗号文を復号し、該復号の結果を含む第２のハッシュ値を生成し、該第２のハッシュ値と前記第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記初期セッション番号および前記開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、該返答者セッション番号を前記第１のセッション番号に追加した第２のセッション番号を生成し、
前記第２のセッション番号の情報および前記乱数を用いて第２の暗号文を生成し、前記第２のセッション番号の情報および前記秘密鍵を含む第３のハッシュ値を生成し、該第３のハッシュ値に含まれる演算結果を前記記憶部に格納し、前記第２のセッション番号、前記第２の暗号文および前記第３のハッシュ値を含む返答者メッセージを前記相手装置に送信し、
前記相手装置から前記返答者メッセージを受信する場合、前記第２のセッション番号の情報および前記秘密鍵を用いて前記第２の暗号文を復号し、該復号の結果を含む第４のハッシュ値を生成し、該第４のハッシュ値と前記第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記第２のセッション番号の情報および前記秘密鍵を含む第５のハッシュ値を生成し、該第５のハッシュ値を鍵として前記記憶部に格納し、前記第２のセッション番号および前記第５のハッシュ値を含む第２の開始者メッセージを前記相手装置に送信し、
前記相手装置から前記第２の開始者メッセージを受信する場合、前記第２のセッション番号の情報を用いて生成した第６のハッシュ値と前記第５のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、前記演算結果および前記第２のセッション番号の情報を用いて第６のハッシュ値を生成し、該第６のハッシュ値を鍵として前記記憶部に格納する処理を前記演算制御部に実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、他の装置と互いに通信して同一の鍵を共有し、両装置が通信相手を互いに認証し、かつ鍵を交換するために行った通信結果が相手との通信証明にならない否認可能な通信を行う鍵交換装置、鍵交換処理システム、鍵交換方法、および、その鍵交換方法をコンピュータに実行させるためのプログラムに関する。
【背景技術】
【０００２】
鍵交換方式には２つの装置が参加し、これら２つの装置が互いに通信することにより、同一の鍵を共有する。特に、各装置が自分であることの認証を受ける方法を備え、鍵を交換した相手の装置を認証する方式を、認証付き鍵交換方式と呼んでいる。さらに、これら２つの装置が鍵を交換するために行った互いの通信が、これら装置が通信を行ったことの証明とならない場合、否認可能認証付き鍵交換方式と呼んでいる。【０００３】
関連する否認可能認証付き鍵交換方式の一例が、文献（Mario  Di  Raimondo,  Rosario  Gennaro,  and  Hugo  Krawczyk,  “Deniable  Authentication  and  Key  Exchange”,  13-th  ACM  Conference  on  Computaer  and  Communication  Security）に開示されている。以下に、この否認可能認証付き鍵交換方式の概略を説明する。【０００４】
図１は関連する否認可能認証付き鍵交換方式を説明するための図である。【０００５】
図１に示すように、鍵交換を行う２つの鍵交換装置A・107、鍵交換装置B・108が通信可能に接続されている。以下では、鍵交換装置A・107を単に「装置A」と称し、鍵交換装置B・108を単に「装置B」と称する。【０００６】
装置Aには、自身の秘密鍵101と、装置Bの公開鍵103と、乱数113とが入力される。装置Bには、自身の秘密鍵104と、装置Aの公開鍵102と、乱数114とが入力される。秘密鍵101をskAとし、秘密鍵104をskBとする。公開鍵102をpkAとし、公開鍵103をpkBとする。乱数113をrAとし、乱数114をrBとする。【０００７】
各装置A、Bは、公開鍵暗号方式の暗号化装置と復号装置を内蔵している。pkAおよびskA等の鍵は、これらの装置A、Bが対応する公開鍵暗号方式で利用される公開鍵と秘密鍵である。そのほかに、各装置は認証装置と疑似乱数生成装置を内蔵している。【０００８】
pを素数とし、gを（Z/pZ）*の素数位数qの部分群の生成元とする。これらp,  qは十分に大きいものとする。最初に装置Aが通信を開始するものとする。これは一般性を奪わない。【０００９】
次に、装置Aと装置Bの動作手順を簡単に説明する。【００１０】
装置Aは、x  ∈Z/qZ  および認証装置の鍵kAを無作為に選ぶ。そして、hA=gx  と、kAのpkBによる暗号文cAを生成し、これらを装置Bへ送信する（図１に符号115で示す）。【００１１】
装置Bは、y  ∈Z/qZ  および認証装置の鍵kBを無作為に選ぶ。そして、hB=gy  と、kBのpkAによる暗号文cBを生成する。装置Bは、装置AからhA=gx  とcAを受け取ると、cAをskBを用いて復号する。その復号の結果をkA'とする。続いて、hA,  hBに対する認証コードtBを、kA'を用いて生成する。その後、hB、cBおよびtBを装置Aへ送信する（図１に符号116で示す）。【００１２】
装置Aは、装置BからhB、cBおよびtBを受け取ると、kAを用いて、hA,  hBに対する認証コードtBを検証する。検証結果が正しくない場合、ここで停止する。検証結果が正しい場合、cBをskAを用いて復号し、その結果をkB'とする。【００１３】
次に、装置Aは、hA,  hBに対する認証コードtAを、kB'を用いて生成する。続いて、hBxから、鍵としてkAを用いて疑似乱数生成装置により疑似乱数qAを生成する。また、hBxから、鍵としてkB'を用いて疑似乱数生成装置により疑似乱数qB'を生成する。そして、交換した鍵110をqAとqB'のビット毎の排他的論理和として出力する。最後に、tAを装置Bへ送信する（図１に符号117で示す）。【００１４】
装置Bは、装置AからtAを受け取ると、kBを用いて、hA,  hBに対する認証コードtAを検証する。検証結果が正しい場合、ここで停止する。【００１５】
検証結果が正しい場合、装置Bは、hAyから、鍵としてkA'を用いて疑似乱数生成装置により疑似乱数qA'を生成する。また、hAyから、鍵としてkBを用いて疑似乱数生成装置により疑似乱数qBを生成する。最後に、交換した鍵111をqA'とqBのビット毎の排他的論理和として出力する。【００１６】
装置Aは、装置Bと通信をした結果得られた知識を履歴109として出力する可能性がある。装置Bは、装置Aと通信をした結果得られた知識を履歴112として出力する可能性がある。
【発明の開示】
【００１７】
上述の否認可能認証付き鍵交換方式では、装置Aと装置Bとの間で３回の通信を行う必要がある。通信回数が多いほど、各装置は相手の装置が返信するのを待たねばならなくなり、実行速度が落ちる。よって、通信回数が少ない方が好ましい。
【００１８】
また、各装置が暗号化装置および復号装置を備え、この暗号化装置で生成された暗号文を送信する必要がある。暗号装置は負荷の大きい計算を行わねばならず、鍵交換処理の実行速度を低下させてしまう。また、暗号文のデータ量は大きく、装置間の通信量を増大させてしまうことになる。
【００１９】
さらに、各装置は鍵を交換する相手の公開鍵を予め入手しておく必要がある。もし鍵交換処理を行う複数の装置が相手の公開鍵を所持していなければ、各装置はさらなる通信を行う必要が生じる。装置Aには装置Bの公開鍵が与えられておらず、装置A側から鍵交換処理を開始するためには、装置Aは装置Bから公開鍵pkBを予め受信する必要がある。この場合、通信回数は上記３回の他に、もう１回必要になる。
【００２０】
関連する否認可能認証付き鍵交換方式では、上述したように、演算処理や通信処理の負荷が大きいという問題があった。
【００２１】
本発明の目的は、鍵交換処理の負荷をより低減した鍵交換装置、鍵交換処理システム、鍵交換方法、および、その鍵交換方法をコンピュータに実行させるためのプログラムを提供することである。
【００２２】
本発明の鍵交換装置は、記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行う鍵交換装置であって、演算制御部は、乱数、秘密鍵、自装置の公開鍵である自己公開鍵、相手装置の公開鍵である相手公開鍵、初期セッション番号および開始指示が入力されると、初期セッション番号、初期セッション番号と異なる開始者セッション番号、自己公開鍵、および相手公開鍵を含む第１のセッション番号を生成し、第１のセッション番号の情報、乱数、および秘密鍵を用いて第１のハッシュ値を生成し、第１のセッション番号および第１のハッシュ値を含む開始者メッセージを相手装置に送信し、相手装置から開始者メッセージを受信する場合、第１のセッション番号の情報を用いて生成した第２のハッシュ値と第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、初期セッション番号および開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、返答者セッション番号を第１のセッション番号に追加した第２のセッション番号の情報を用いて第３のハッシュ値を生成し、第３のハッシュ値を鍵として記憶部に格納し、第２のセッション番号および第３のハッシュ値を含む返答者メッセージを生成して相手装置に送信し、相手装置から返答者メッセージを受信する場合、第２のセッション番号の情報を用いて生成した第４のハッシュ値と第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、第２のセッション番号の情報を用いて第５のハッシュ値を生成し、第５のハッシュ値を鍵として記憶部に格納するものである。
【００２３】
また、本発明の鍵交換装置は、記憶部および演算制御部を備え、ネットワークを介して外部の相手装置と鍵交換処理を行う鍵交換装置であって、演算制御部は、乱数、秘密鍵、自装置の識別子である自己装置番号、相手装置の識別子である相手装置番号、初期セッション番号および開始指示が入力されると、初期セッション番号、初期セッション番号と異なる開始者セッション番号、自己装置番号、および相手装置番号を含む第１のセッション番号を生成し、第１のセッション番号の情報および乱数を用いて第１の暗号文を生成し、第１のセッション番号の情報および秘密鍵を用いて第１のハッシュ値を生成し、第１のセッション番号、第１の暗号文および第１のハッシュ値を含む開始者メッセージを相手装置に送信し、相手装置から開始者メッセージを受信する場合、第１のセッション番号の情報および秘密鍵を用いて第１の暗号文を復号し、復号の結果を含む第２のハッシュ値を生成し、第２のハッシュ値と第１のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、初期セッション番号および開始者セッション番号のいずれとも異なる返答者セッション番号を生成し、返答者セッション番号を第１のセッション番号に追加した第２のセッション番号を生成し、第２のセッション番号の情報および乱数を用いて第２の暗号文を生成し、第２のセッション番号の情報および秘密鍵を含む第３のハッシュ値を生成し、第３のハッシュ値を鍵として記憶部に格納し、第２のセッション番号、第２の暗号文および第３のハッシュ値を含む返答者メッセージを相手装置に送信し、相手装置から返答者メッセージを受信する場合、第２のセッション番号の情報および秘密鍵を用いて第２の暗号文を復号し、復号の結果を含む第４のハッシュ値を生成し、第４のハッシュ値と第３のハッシュ値とが一致するか否かを双線形写像の性質を利用して判定し、これらのハッシュ値が一致していれば、第２のセッション番号の情報および秘密鍵を含む第５のハッシュ値を生成し、第５のハッシュ値を鍵として記憶部に格納するものである。
【００２４】
本発明では、鍵交換処理の開始側から返答側にメッセージを送るときと、返答側から開始側にメッセージを送るときの２回の通信で済むため、従来よりも通信処理の負荷が軽減する。また、双線形写像の性質を利用することでメッセージの送信元の認証を行うことが可能となるため、従来とは異なり、認証データなどの通信履歴を残さない。
【図面の簡単な説明】
【００２５】
【図１】図１は関連する否認可能認証付き鍵交換方式を説明するための図である。
【図２】図２は第１の実施形態の鍵交換装置の構成例を示すブロック図である。
【図３】図３は第１の実施形態の鍵交換準備部の動作手順を示すフローチャートである。
【図４】図４は第１の実施形態の鍵交換応答部の動作手順を示すフローチャートである。
【図５Ａ】図５は図４に示す処理１および処理２のそれぞれの手順を示すフローチャートである。
【図５Ｂ】図５は図４に示す処理１および処理２のそれぞれの手順を示すフローチャートである。
【図６】図６は第１の実施形態の鍵失効部の動作手順を示すフローチャートである。
【図７】図７は第２の実施形態の鍵交換装置の構成例を示すブロック図である。
【図８】図８は第２の実施形態の鍵交換準備部の動作手順を示すフローチャートである。
【図９】図９は第２の実施形態の鍵交換応答部の動作手順を示すフローチャートである。
【図１０Ａ】図１０Ａは図９に示す処理３の手順を示すフローチャートである。
【図１０Ｂ】図１０Ｂは図９に示す処理４の手順を示すフローチャートである。
【図１１】図１１は第３の実施形態の鍵交換応答部の動作手順を示すフローチャートである。
【図１２Ａ】図１２Ａは図１１に示す処理５の手順を示すフローチャートである。
【図１２Ｂ】図１２Ｂは図１１に示す処理６の手順を示すフローチャートである。
【図１３】図１３は図１１に示す処理７の手順を示すフローチャートである。
【図１４】図１４は第４の実施形態の鍵交換応答部の動作手順を示すフローチャートである。
【図１５Ａ】図１５Ａは図１４に示す処理８の手順を示すフローチャートである。
【図１５Ｂ】図１５Ｂは図１４に示す処理９の手順を示すフローチャートである。
【図１６】図１６は図１４に示す処理１０の手順を示すフローチャートである。
【符号の説明】
【００２６】
２００、７００    鍵交換装置
２５０、７５０    記憶部
２６０、７６０    演算制御部
【発明を実施するための最良の形態】
【００２７】
各実施形態では、qを素数とし、G,  G'を位数qの乗法的巡回群とし、eをGの２つの要素をG'の要素に写す双線形写像とする。なお、eが双線形であるとは、Gの任意の要素u,  vとZ/qZの任意の要素a,  bに対して、e（ua,vb）=e（u,v）ab  が成り立つことである。【００２８】
また、gをGの生成元とする。Hashをハッシュ関数とする。各実施形態の鍵交換装置は、群G,  G'における双線形写像eの体演算の装置、群演算装置Z/qZの体演算の装置、およびハッシュ関数の演算装置の機能を備えているものとする。以下に説明する実施形態では、これらの演算装置の機能が演算制御部に設けられているものとする。各種演算処理の結果は一時的に記憶部に格納される。【００２９】
また、各実施形態の鍵交換装置は、生成元gを保持している。なお、Hashをその値域がZ/qZであるハッシュ関数とし、Hash'をその値域がGであるハッシュ関数とし、Hash''をその値域が交換鍵の空間であるハッシュ関数とする。φは、対応するデータが空であることを表す。"開始"のように引用記号でくくられる単語は文字列データとして扱われる。【００３０】
（第１の実施形態）
本実施形態の鍵交換装置の構成を説明する。【００３１】
図２は本実施形態の鍵交換装置の構成例を示すブロック図である。【００３２】
図２に示すように、鍵交換装置200は、各種データが入力される入力部215と、ネットワーク213を介して外部と通信する通信部212と、入力されるデータを格納する記憶部250と、演算制御部260とを有する。鍵交換装置200は、ネットワーク213を介して他の鍵交換装置と接続され、鍵交換の処理を行う。相手の鍵交換装置も図２に示す鍵交換装置200と同様な構成である。【００３３】
なお、自装置の秘密鍵を自己秘密鍵と称し、自装置の公開鍵を自己公開鍵と称する。鍵交換処理を行う相手の公開鍵を相手公開鍵と称する。【００３４】
記憶部250には、鍵交換処理において処理過程の状態を示す情報である内部状態情報が格納される内部状態リスト207と、鍵交換処理により生成された鍵の情報である交換結果が格納される交換結果リスト208とがある。【００３５】
演算制御部260は、鍵交換準備部209、鍵交換応答部210および鍵失効部211を有する。演算制御部260には、プログラムにしたがって所定の処理を実行するＣＰＵ（Central  Processing  Unit）（不図示）、およびプログラムを格納するためのメモリ（不図示）が設けられている。演算制御部260がプログラムを実行することで、鍵交換準備部209、鍵交換応答部210および鍵失効部211が鍵交換装置内に仮想的に構成される。【００３６】
鍵交換準備部209および鍵交換応答部210は、鍵交換処理の過程で内部状態情報というデータを生成して記憶部250の内部状態リスト207に書き込む、内部状態リスト207から内部状態情報を読み出す、または内部状態リスト207の内部状態情報を消去する。鍵交換応答部210は、生成された鍵などのデータを交換結果として記憶部250の交換結果リスト208に書き込む。鍵失効部211は、交換結果リスト208から交換結果を消去する。【００３７】
内部状態情報と交換結果のそれぞれは、識別子となるセッション番号で同定され、記憶部内にセッション番号とともに登録される。これによりセッション番号で管理される。【００３８】
セッション番号の種類には、大本の識別子である初期セッション番号、鍵交換処理の開始側の識別子である開始者セッション番号、返答側となる相手の識別子である返答者セッション番号、およびこれらのセッション番号などにより新規に生成されるセッション番号がある。内部状態情報と交換結果のそれぞれは、新規に生成されるセッション番号で管理される。【００３９】
新規に生成されるセッション番号には、開始者セッション番号と、返答者セッション番号と、初期セッション番号と、セッション番号生成元の自己公開鍵と、相手公開鍵と、文字列データのラベルの情報が含まれる。生成されるセッション番号を、（開始者セッション番号、返答者セッション番号、初期セッション番号、自己公開鍵、相手公開鍵、文字列データのラベル）と表記する。【００４０】
鍵交換準備部209、鍵交換応答部210および鍵失効部211は、データが入力部707を介して入力されたとき、またはメッセージを通信部212を介して受信したときに、データまたはメッセージの内容にしたがって、記憶部250の内部状態情報または交換結果にアクセスして、鍵交換処理を進める。【００４１】
メッセージには、送信先を示す相手公開鍵、送信元を示す自己公開鍵、セッション番号、およびハッシュ値が含まれる。メッセージを、（相手公開鍵、自己公開鍵、セッション番号、ハッシュ値）と表記する。鍵交換装置200は、メッセージ内の相手公開鍵の情報でメッセージの送信元を特定することが可能である。【００４２】
セッション番号には相手装置を示す情報が含まれ、また、進行中の鍵交換処理の途中の状態を示す内部状態情報がセッション番号で管理されるため、鍵交換装置200は、鍵交換処理の相手装置が複数であっても、鍵交換処理の進捗状況を相手装置毎に管理でき、複数の鍵交換処理を並行して行うことができる。【００４３】
交換結果として記憶部250に格納される交換鍵は、読み出し装置214により読み込まれ、外部のアプリケーションにより利用される。【００４４】
次に、本実施形態の鍵交換装置の動作を詳しく説明する。【００４５】
図３は鍵交換準備部の動作手順を示すフローチャートである。図３に示すように、鍵交換装置200の鍵交換準備部209に、入力部215を介して、図２に示す命令201、初期セッション番号202、乱数203、自己秘密鍵204、自己公開鍵205、および相手公開鍵206が入力される（ステップ３０１）。初期セッション番号202をsidCとし、自己秘密鍵204をx  ∈  Z/qZとし、自己公開鍵205をy  =  gxとし、相手公開鍵206をy'とする。【００４６】
鍵交換準備部209は、命令201が“鍵交換開始”であるか否かを判定し（ステップ３０２）、命令201が“鍵交換開始”である場合、次のように動作する。
1.  r  ∈Z/qZ  を乱数203から生成する（ステップ３０３）。
2.  開始者セッション番号  sidI=gr  を生成する（ステップ３０３）。
3.  ハッシュ値H  =  Hash（sidI,  sidC,  y,  y',  y'r,  yx,  "開始"）を生成する（ステップ３０４）。
4.  セッション番号SIDを、SID=（sidI,  φ,  sidC,  y,  y',  "開始"）として生成する（ステップ３０５）。
5.  上記4の動作で決定されたセッション番号に対応する内部状態情報として  r  を記憶部250の内部状態リスト207に保存する（ステップ３０５）。
6.  メッセージ（y',  y,  SID,  H）を公開鍵y’の相手側の鍵交換装置に通信部212およびネットワーク213を介して送信する（ステップ３０６）。
7.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ３０７）。【００４７】
図３に示すステップ３０２で命令201が“鍵交換開始”でなければ、命令201が“鍵交換返答”であるか否かを判定し（ステップ３０８）、命令201が“鍵交換返答”である場合、鍵交換準備部209は、次のように動作する。
1.  セッション番号SIDを、SID=（φ,  φ,  sidC,  y,  y',  "返答"）として生成する（ステップ３０９）。このセッション番号では、開始者セッション番号と返答者セッション番号が空である。
2.  上記1の動作で決定したセッション番号に対応する内部状態情報として  φ  を記憶部250の内部状態リスト207に保存する（ステップ３０９）。
3.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ３１０）。ステップ３０８で、命令201が“鍵交換返答”でない場合も同様である。【００４８】
上述のようして、鍵交換準備部209は、自身が開始側であれば、ステップ３０３から３０６の処理を行い、相手が開始側で自身が返答側であれば、ステップ３０９の処理を行う。【００４９】
続いて、鍵交換応答部210の動作を説明する。図４は鍵交換応答部の動作手順を示すフローチャートである。図５Ａは図４に示す処理１の手順を示すフローチャートであり、図５Ｂは図４に示す処理２の手順を示すフローチャートである。【００５０】
鍵交換応答部210の動作には、自身が返答側で相手が開始側である場合に相手からメッセージを受信したときの動作と、自身が開始側で相手が返答側の場合に相手からメッセージを受信したときの動作とがある。以下に、これらの動作をそれぞれ順に説明する。【００５１】
鍵交換装置200の鍵交換応答部210は、ネットワーク213および通信部212を介して相手の鍵交換装置からメッセージ（y,  y',  SID',  H'）を受信すると（ステップ４０１）、セッション番号SID’がSID'=（sidI,  φ,  sidC,  y',  y,  "開始"）の形式であるか否かを判定する（ステップ４０２）。【００５２】
なお、メッセージ（y,  y',  SID',  H'）は、図３で説明した処理と同様にして、公開鍵y’の相手の鍵交換装置で作成されたものである。このメッセージに含まれるセッション番号とハッシュ値を、それぞれSID’およびH’と表記している。【００５３】
ステップ４０２でＹｅｓの場合、鍵交換応答部210は、自身が返答側として、次のように動作する。
1.  メッセージの送信先が自装置の公開鍵yに一致することを確認する。一致しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる。
2.  セッション番号SID=（φ,  φ,  sidC,  y,  y',  "返答"）に対応する内部状態情報が記憶部250の内部状態リスト207に存在するか否かを調べる（ステップ４０３）。図３で説明したステップ３０９の処理を行っていれば、その内部状態情報が内部状態リスト207に保管されている。そのセッション番号に対応する内部状態情報が存在しなければ、処理を終了して、次の入力待ちまたは受信待ちの待機状態になる（ステップ４０５）。【００５４】
ステップ４０３で上記内部状態情報が存在する場合、図５Ａに示すフローに進み、鍵交換応答部210は、次のように動作する。
3.  対応して保持していた内部状態情報  φ  を読み込む（ステップ５０１）。そして、h'=sidI  とし、続いて、受信したメッセージに含まれるH’を読み出し、H'  =Hash（sidI,  sidC,  y',  y,  h'x,  y'x,  "開始"）が成り立つことを確認する（ステップ５０２）。h'xは開始者セッション番号と自己秘密鍵との演算結果であり、y'xは相手公開鍵と自己秘密鍵との演算結果である。この式が成り立たなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ５０９）。
4.  r  ∈Z/qZ  を乱数から生成する（ステップ５０３）。
5.  返答者セッション番号  sidR=gr  を生成する（ステップ５０３）。
6.  ハッシュ値H  =  Hash（sidI,  sidR,  sidC,  y,  y',  h'r,  h'x,  y'r,  "返答"）を生成する（ステップ５０４）。h'rは返答者セッション番号の生成に用いた乱数と開始者セッション番号との演算結果であり、y'rは返答者セッション番号の生成に用いた乱数と相手公開鍵との演算結果である。
7.  受信した開始者セッション番号と生成した返答者セッション番号とをセッション番号SID=（φ,  φ,  sidC,  y,  y',  "返答"）に追加し、セッション番号SIDをSID=（sidI,  sidR,  sidC,  y,  y',  "返答"）に更新する（ステップ５０５）。
8.  交換鍵  K  =  Hash（sidI,  sidR,  sidC,  y',  y,  h'r,  h'x,  y'r,  "鍵"）を生成する（ステップ５０６）。
9.  上記7の動作で更新したセッション番号に対応する交換結果として  K  を記憶部250の交換結果リスト208に保存する（ステップ５０６）。
10.  メッセージ（y',  y,  SID,  H）を公開鍵y’の相手側の鍵交換装置に通信部212およびネットワーク213を介して送信する（ステップ５０７）。
11.  上記7の動作で更新したセッション番号に対応する内部状態情報  φ  を記憶部250の内部状態リスト207から消去する（ステップ５０８）。
12.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ５０９）。【００５５】
一方、ステップ４０２でＮｏの場合、鍵交換応答部210は、受信したメッセージ（y,  y',  SID',  H'）のセッション番号SID’を読み出し、SID'=（sidI,  sidR,  sidC,  y',  y,  "返答"）の形式であるか否かを調べる（ステップ４０６）。SID'=（sidI,  sidR,  sidC,  y',  y,  "返答"）の形式であると、自身が開始側として鍵交換準備部209が相手の鍵交換装置にメッセージを送ったことに対して、相手からの返答メッセージを受け取ったものと判断し、次のように動作する。
1.  メッセージの送信先が自装置の公開鍵yに一致することを確認する。一致しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる。
2.  セッション番号  SID=（sidI,  φ,  sidC,  y,  y',  "開始"）に対応する内部状態情報が記憶部250の内部状態リスト207に存在するか否かを調べる（ステップ４０７）。図３で説明したステップ３０５の処理を行っていれば、その内部状態情報が内部状態リスト207に保管されている。そのセッション番号に対応する内部状態情報が存在しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ４０９）。【００５６】
ステップ４０７で上記内部状態情報が存在する場合、図５Ｂに示すフローに進み、鍵交換応答部210は、次のように動作する。
3.  対応して保持していた内部状態情報  r  を読み込む（ステップ５２１）。そして、h'=sidR  とし、続いて、受信したメッセージからH’を読み出し、H'=Hash（sidI,  sidR,  sidC,  y',  y,  h'r,  y'x,  h'x,  "返答"）が成り立つことを確認する（ステップ５２２）。成り立たなければ、次の入力待ちまたは受信待ちの待機状態になる（ステップ５２６）。
4.  受信した返答者セッション番号をセッション番号SID=（sidI,  φ,  sidC,  y,  y',  "開始"）に追加し、セッション番号SIDをSID=（sidI,  sidR,  sidC,  y,  y',  "開始"）に更新する（ステップ５２３）。
5.  交換鍵  K  =  Hash（sidI,  sidR,  sidC,  y,  y',  h'r,  y'r,  h'x,  "鍵"）を生成する（ステップ５２４）。
6.  上記4の動作で更新したセッション番号に対応する交換結果として  K  を記憶部250の交換結果リスト208に保存する（ステップ５２４）。
7.  上記4の動作で更新したセッション番号に対応する内部状態情報  r  を記憶部250の内部状態リスト207から消去する（ステップ５２５）。
8.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ５２６）。【００５７】
なお、上述のようにして生成された鍵が不要になった場合には、次のように鍵の失効を行う。鍵失効の命令は、入力部215を介して入力される場合と、ネットワーク213および通信部212を介して受信する場合とがある。【００５８】
図６は鍵失効部の動作手順を示すフローチャートである。鍵交換装置200の鍵失効部211は、鍵失効命令とともに、失効対象となる鍵を特定するためのセッション番号SIDが入力されると（ステップ６０１）、次のように動作する。
1.  セッション番号SIDに一致するセッション番号の交換結果が記憶部250の交換結果リスト208に保持されているか否かを判定する（ステップ６０２）。該当する交換結果がある場合、これをセッション番号SIDとともに交換結果を消去する（ステップ６０３）。
2.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ６０４）。【００５９】
本実施形態の鍵交換装置においては、鍵交換処理のために他の鍵交換装置とメッセージの交換を行う際、開始側であっても返答側であっても、通信の回数は２回で済む。【００６０】
本実施形態の鍵交換装置を用いた鍵交換において、片方の鍵交換装置が計算したハッシュ関数の引数に、h'r,  y'x,  h'x  なる値があるが、これらは、それぞれ、hr',  yx',  yr'  に等しい。そして、前者の値は公開鍵  y  に対応する鍵交換装置が計算可能で、後者は公開鍵  y'  に対応する鍵交換装置が計算可能である。すなわち、（r,  x）または（r',  x'）の何れか片方のみの知識で計算可能である。【００６１】
ある値a,  b,  c  がそれぞれh'r,  y'x,  h'x  に等しいかどうかは、（r,  x）または（r',  x'）の何れか片方の知識があれば、もう片方の知識を持たずとも、それぞれ、e（a,  g）=  e（h,  h'）、e（b,  g）=  e（y,  y'）、e（c,  g）=  e（y,  h'）を確認することで可能である。このことは、もし、ある装置が正しくハッシュ関数の出力を計算できるならば、具体的な処理において、その装置がハッシュ関数を計算する処理を観測することにより、a,  b,  c  に対応する値を取り出し、その具体的処理が鍵交換において求められているハッシュ関数の値の計算を行っているかを確認することができる。【００６２】
装置Aと装置Bの従来の鍵交換処理において否認可能性を求める場合、装置Aが正直に振る舞っている限り、装置Bも正常に処理を続けても、装置Aは、装置Bが装置Aと鍵交換をした証拠を得ることができない。しかし、装置Aが不正直に振る舞う場合においても、装置Bが正直に振る舞うと、装置Aは、装置Bが装置Aと鍵交換をした証拠を得ることができてしまう。【００６３】
これに対して、本実施形態では、装置Aが正直な（すなわち正常な）処理を行っているか否かは、上述したように、値a,  b,  c  に対応する可能性のある値を抜き出し、それぞれ  e（a,  g）=  e（h,  h'）、e（b,  g）=  e（y,  y'）、e（c,  g）=  e（y,  h'）が成り立つかで、調べることができる。これにより、装置Bは装置Aにだまされることなく、振る舞うことができる。よって、本実施形態の鍵交換処理方法は否認可能性を有していることがわかる。【００６４】
（第２の実施形態）
本実施形態の鍵交換装置の構成を説明する。【００６５】
図７は本実施形態の鍵交換装置の構成例を示すブロック図である。【００６６】
図７に示すように、鍵交換装置700は、各種データが入力される入力部707と、ネットワーク715を介して外部と通信する通信部714と、入力されるデータを格納する記憶部750と、演算制御部760とを有する。本実施形態の演算制御部760は、暗号化装置と復号装置の機能を備えている。鍵交換装置700は、ネットワーク715を介して他の鍵交換装置と接続され、鍵交換の処理を行う。相手の鍵交換装置も図７に示す鍵交換装置700と同様な構成である。【００６７】
なお、装置番号は、識別子となり、それぞれの鍵交換装置に付与されている。装置番号として、装置固有のメールアドレスおよびurl（uniform  resource  locators）等の文字列が考えられるが、他のものであってもよい。自装置の装置番号を自己装置番号と称し、鍵交換処理を行う相手の装置番号を相手装置番号と称する。【００６８】
記憶部750には、鍵交換処理において処理過程の状態を示す情報である内部状態情報が格納される内部状態リスト708と、鍵交換処理により生成された鍵の情報である交換結果が格納される交換結果リスト711とがある。【００６９】
演算制御部760は、鍵交換準備部709、鍵交換応答部710および鍵失効部713を有する。演算制御部760には、プログラムにしたがって所定の処理を実行するＣＰＵ（不図示）、およびプログラムを格納するためのメモリ（不図示）が設けられている。演算制御部760がプログラムを実行することで、鍵交換準備部709、鍵交換応答部710および鍵失効部713が鍵交換装置内に仮想的に構成される。【００７０】
鍵交換準備部709および鍵交換応答部710は、鍵交換処理の過程で内部状態情報というデータを生成して記憶部750の内部状態リスト708に書き込む、内部状態リスト708から内部状態情報を読み出す、または内部状態リスト708の内部状態情報を消去する。鍵交換応答部710は、生成された鍵などのデータを交換結果として記憶部750の交換結果リスト711に書き込む。鍵失効部713は、交換結果リスト711から交換結果を消去する。【００７１】
内部状態情報と交換結果のそれぞれは、識別子となるセッション番号で同定され、記憶部内にセッション番号とともに登録される。これによりセッション番号で管理される。【００７２】
セッション番号の種類には、大本の識別子である初期セッション番号、鍵交換処理の開始側の識別子である開始者セッション番号、返答側となる相手の識別子である返答者セッション番号、およびこれらのセッション番号などにより新規に生成されるセッション番号がある。内部状態情報と交換結果のそれぞれは、新規に生成されるセッション番号で管理される。【００７３】
新規に生成されるセッション番号には、開始者セッション番号と、返答者セッション番号と、初期セッション番号と、自己装置番号と、相手装置番号と、文字列データのラベルの情報が含まれる。生成されるセッション番号を、（開始者セッション番号、返答者セッション番号、初期セッション番号、自己装置番号、相手装置番号、文字列データのラベル）と表記する。【００７４】
鍵交換準備部709、鍵交換応答部710および鍵失効部713は、データが入力部707を介して入力されたとき、またはメッセージを通信部714を介して受信したときに、データまたはメッセージの内容にしたがって、記憶部750の内部状態情報または交換結果にアクセスして、鍵交換処理を進める。【００７５】
メッセージには、送信先を示す相手装置番号、送信元を示す自己装置番号、セッション番号、暗号文およびハッシュ値が含まれる。メッセージを、（相手装置番号、自己装置番号、セッション番号、（暗号文、ハッシュ値））と表記する。鍵交換装置は、メッセージ内の相手装置番号でメッセージの送信元を特定することが可能である。【００７６】
セッション番号には相手装置を示す情報が含まれ、また、進行中の鍵交換処理の途中の状態を示す内部状態情報がセッション番号で管理されるため、鍵交換装置700は、鍵交換処理の相手装置が複数であっても、鍵交換処理の進捗状況を相手装置毎に管理でき、複数の鍵交換処理を並行して行うことができる。【００７７】
交換結果として記憶部750に格納される交換鍵は、読み出し装置712により読み込まれ、外部のアプリケーションにより利用される。【００７８】
次に、本実施形態の鍵交換装置の動作を詳しく説明する。【００７９】
図８は鍵交換準備部の動作手順を示すフローチャートである。図８に示すように、鍵交換装置700の鍵交換準備部709に、入力部707を介して、図７に示す命令701、初期セッション番号702、乱数703、自己秘密鍵704、自己装置番号705、相手装置番号706およびシステム鍵716が入力される（ステップ８０１）。初期セッション番号702をsidCとし、自己秘密鍵704をx  ∈  Gとし、自己装置番号705をidとし、相手装置番号706をid'とする。そして、システム鍵716をm  ∈  Gとする。【００８０】
鍵交換準備部709は、命令701が“鍵交換開始”であるか否かを判定し（ステップ８０２）、命令701が“鍵交換開始”である場合、次のように動作する。ただし、s  が  m=  gs  を満たすなら、x=  Hash（g,  m,  id）s  になるとする。
1.  r  ∈Z/qZ  を乱数から生成する（ステップ８０３）。
2.  開始者セッション番号  sidI=gr  を生成する（ステップ８０３）。
3.  ハッシュ値と暗号文として、
y'  =Hash'（g,  m,  id'），
u  =  Hash'（sidI,  sidC,  id,  id',  e（yr,  y'）,  "開始"），
c  =  Hash（u）+  r  ，
H  =  Hash（sidI,  sidC,  id,  id',  u,  e（y',  x）,  "開始"），
を生成する（ステップ８０４）。
4.  セッション番号SIDを、SID=（sidI,  φ,  sidC,  id,  id',  "開始"）として生成する（ステップ８０５）。
5.  上記4の動作で決定したセッション番号に対応する内部状態情報として  u  を記憶部750の内部状態リスト708に保存する（ステップ８０５）。
6.  メッセージ（id',  id,  SID,  （c,  H））を装置番号id'の相手側の鍵交換装置に通信部714およびネットワーク715を介して送信する（ステップ８０６）。
7.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ８０７）。【００８１】
図８に示すステップ８０２で命令701が“鍵交換開始”でなければ、命令701が“鍵交換返答”であるか否かを判定し（ステップ８０８）、命令701が“鍵交換返答”である場合、鍵交換準備部709は、次のように動作する。
1.  セッション番号SIDを、SID=（φ,  φ,  sidC,  id,  id',  "返答"）として生成する（ステップ８０９）。
2.  上記1の動作で決定したセッション番号に対応する内部状態情報として  φ  を記憶部750の内部状態リスト708に保存する（ステップ８０９）。
3.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ８１０）。ステップ８０８で、命令701が“鍵交換返答”でない場合も同様である。【００８２】
上述のようして、鍵交換準備部709は、自身が開始側であれば、ステップ８０３から８０６の処理を行い、相手が開始側で自身が返答側であれば、ステップ８０９の処理を行う。【００８３】
続いて、鍵交換応答部710の動作を説明する。図９は鍵交換応答部の動作手順を示すフローチャートである。図１０Ａは図９に示す処理３の手順を示すフローチャートであり、図１０Ｂは図９に示す処理４の手順を示すフローチャートである。【００８４】
鍵交換応答部710の動作には、自身が返答側で相手が開始側である場合に相手からメッセージを受信したときの動作と、自身が開始側で相手が返答側の場合に相手からメッセージを受信したときの動作とがある。以下に、これらの動作をそれぞれ順に説明する。【００８５】
鍵交換装置700の鍵交換応答部710は、ネットワーク715および通信部714を介して相手の鍵交換装置からメッセージ（id,  id',  SID',  （c',  H'））を受信すると（ステップ９０１）、セッション番号SID’がSID'=（sidI,  φ,  sidC,  id',  id,  "開始"）の形式であるか否かを判定する（ステップ９０２）。【００８６】
なお、メッセージ（id,  id',  SID',  （c',  H'））は、図８で説明した処理と同様にして、装置番号id'の相手の鍵交換装置で作成されたものである。このメッセージに含まれるセッション番号、暗号文およびハッシュ値を、それぞれSID’、c’およびH’と表記している。【００８７】
ステップ９０２でＹｅｓの場合、鍵交換応答部710は、自身が返答側として、次のように動作する。
1.  メッセージの送信先が自装置の番号idに一致することを確認する。一致しなければ、次の入力あるいは通信の受信を待って停止する。
2.  セッション番号  SID=（φ,  φ,  sidC,  id,  id',  "返答"）  に対応する内部状態情報が記憶部750の内部状態リスト708に存在するか否かを調べる（ステップ９０３）。図８で説明したステップ８０９の処理を行っていれば、その内部状態情報が内部状態リスト708に保管されている。そのセッション番号に対応する内部状態情報が存在しなければ、処理を終了して、次の入力待ちまたは受信待ちの待機状態になる（ステップ９０５）。【００８８】
ステップ９０３で上記内部状態情報が存在する場合、図１０Ａに示すフローに進み、鍵交換応答部710は、次のように動作する。
3.  対応して保持していた内部状態情報  φ  を読み込む（ステップ１００１）。そして、y'=  Hash'（g,  m,  id'）、h'=  sidI  とし、
u'  =  Hash'（sidI,  sidC,  id',  id,  e（h',  x）,  "開始"），
r'=  c'  -  Hash（u'），
を生成することで、暗号文を復号する（ステップ１００１）。
続いて、h'  =  gr'，H'  =  Hash（sidI,  sidC,  id',  id,  u',  e（x,  y'）,  "開始"）が成り立つことを確認する（ステップ１００２）。これらが成り立たなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１００９）。
4.  r  ∈Z/qZ  を乱数から生成する（ステップ１００３）。
5.  返答者セッション番号  sidR=gr  を生成する（ステップ１００３）。
6.  u  =  Hash'（sidI,  sidR,  sidC,  id,  id',  e（yr,  y'）,  "返答"），
c  =  hash（u）  +  r，
H  =  Hash（sidI,  sidR,  sidC,  id,  id',  u,  u',  e（x,  y'）,  "返答"），
K  =  Hash（sidI,  sidR,  sidC,  id',  id,  u',  u,  e（x,  y'）），
を生成する（ステップ１００４）。このようにして暗号文、ハッシュ値およびKを生成する。
7.  受信した開始者セッション番号と生成した返答者セッション番号とをセッション番号SID=  （φ,  φ,  sidC,  id,  id',  "返答"）に追加し、セッション番号SIDを、SID=  （sidI,  sidR,  sidC,  id,  id',"返答"）に更新する(ステップ１００５)。
8.  ステップ１００４で生成したKを交換鍵とする（ステップ１００６）。
9.  上記7の動作で更新したセッション番号に対応する交換結果として  K  を記憶部750の交換結果リスト711に保存する（ステップ１００６）。
10.  メッセージ（id',  id,  SID,  （c,  H））を  装置番号id'の相手側の鍵交換装置に通信部714およびネットワーク715を介して送信する（ステップ１００７）。
11.  上記7の動作でしたセッション番号に対応する内部状態情報  φ  を記憶部750の内部状態リスト708から消去する（ステップ１００８）。
12.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１００９）。【００８９】
一方、ステップ９０２でＮｏの場合、鍵交換応答部710は、受信したメッセージ（id,  id',  SID',  （c',  H'））のセッション番号SID’を読み出し、SID'=（sidI,  sidR,  sidC,  id',  id,  "返答"）の形式であるか否かを調べる（ステップ９０６）。SID'=（sidI,  sidR,  sidC,  id',  id,  "返答"）の形式であると、自身が開始側として鍵交換準備部709が相手の鍵交換装置にメッセージを送ったことに対して、相手からの返答メッセージを受け取ったものと判断し、次のように動作する。
1.  メッセージの送信先が自装置の番号idに一致することを確認する。一致しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる。
2.  セッション番号SID=（sidI,  φ,  sidC,  id,  id',  "開始"）に対応する内部状態情報が記憶部750の内部状態リスト708に存在するか否かを調べる(ステップ９０７)。図８で説明したステップ８０５の処理を行っていれば、その内部状態情報が内部状態リスト708に保管されている。そのセッション番号に対応する内部状態情報が存在しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ９０９）。【００９０】
ステップ９０７で上記内部状態情報が存在する場合、図１０Ｂに示すフローに進み、鍵交換応答部710は、次のように動作する。
3.  対応して保持していた内部状態情報  u  を読み込む（ステップ１０２１）。そして、y'  =Hash'（g,  m,  id'），h'  =  sidR  とし、
u'  =  Hash'（sidI,  sidR,  sidC,  id',  id,  e（h',  x）,  "返答"），
r'  =  c'  -  Hash（u'），
を生成することで、暗号文を復号する（ステップ１０２１）。
続いて、  h'  =  gr'，H'  =  Hash（sidI,  sidR,  sidC,  id',  id,  u',  u,  e（x,  y'）,  "開始"）が成り立つことを確認する（ステップ１０２２）。成り立たなければ、次の入力待ちまたは受信待ちの待機状態になる（ステップ１０２６）。
4.  受信した返答者セッション番号をセッション番号SID=（sidI,  φ,  sidC,  id,  id',  "開始"）に追加し、セッション番号SIDを、SID=（sidI,  sidR,  sidC,  id,  id',  "開始"）に更新する（ステップ１０２３）。
5.  交換鍵  K  =  Hash（sidI,  sidR,  sidC,  id,  id',  u,  u',  e（x,  y'）,  "鍵"）を生成する（ステップ１０２４）。
6.  上記4で更新したセッション番号に対応する交換結果として  K  を記憶部750の交換結果リスト711に保存する（ステップ１０２４）。
7.  上記4で更新したセッション番号に対応する内部状態情報  u  を記憶部750の内部状態リスト708から消去する（ステップ１０２５）。
8.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１０２６）。【００９１】
なお、上述のようにして生成された鍵が不要になった場合には、次のように鍵の失効を行う。鍵失効の命令は、入力部707を介して入力される場合と、ネットワーク715および通信部714を介して受信する場合とがある。図６に示したフローチャートを参照して説明する。【００９２】
鍵失効部711は、鍵失効命令とともに、失効対象となる鍵を特定するためのセッション番号SIDが入力されると（ステップ６０１）、次のように動作する。
1.  セッション番号SIDに一致するセッション番号の交換結果が記憶部750の交換結果リスト711に保持されているか否かを判定する（ステップ６０２）。該当する交換結果がある場合、これをセッション番号SIDとともに消去する（ステップ６０３）。
2.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ６０４）。【００９３】
本実施形態の鍵交換装置においても、鍵交換処理のために他の鍵交換装置とメッセージの交換を行う際、開始側であっても返答側であっても、通信の回数は２回で済む。また、否認可能性を有することも、第１の実施形態で説明したとおりである。【００９４】
また、鍵交換装置は、鍵交換処理の開始側の装置は相手の装置の公開鍵  y'  を必要としない。装置を識別するための装置番号  id'  として、装置固有のメールアドレスやurl等の任意の文字列を使用することが可能であるためである。通信相手を特定した時点で、セッション番号およびメッセージ等の生成時に必要な相手先の情報が揃うことになる。【００９５】
（第３の実施形態）
本実施形態の鍵交換装置は、第１の実施形態と同様な構成であるが、動作が異なる。本実施形態では構成についての詳細な説明を省略し、以下に、本実施形態の鍵交換装置の動作について詳細に説明する。【００９６】
第１の実施形態の図３で説明したように、鍵交換装置200の鍵交換準備部209に、入力部215を介して、命令201、初期セッション番号202、乱数203、自己秘密鍵204、自己公開鍵205、および相手公開鍵206が入力される（ステップ３０１）。なお、第１の実施形態と同様に、初期セッション番号202をsidCとし、自己秘密鍵204をx  ∈  Z/qZとし、自己公開鍵205をy  =  gxとし、相手公開鍵206をy'としている。【００９７】
鍵交換準備部209は、命令201が“鍵交換開始”であるか否かを判定し（ステップ３０２）、命令201が“鍵交換開始”である場合、次のように動作する。
1.  r  ∈Z/qZ  を乱数203から生成する（ステップ３０３）。
2.  開始者セッション番号  sidI=gr  を生成する（ステップ３０３）。
3.  ハッシュ値H  =  Hash（sidI,  sidC,  y,  y',  y'r,  "開始"）を生成する（ステップ３０４）。
4.  セッション番号SIDを、SID=（sidI,  φ,  sidC,  y,  y',  "開始"）として生成する（ステップ３０５）。
5.  上記4の動作で決定されたセッション番号に対応する内部状態情報として  r  を記憶部250の内部状態リスト207に保存する（ステップ３０５）。
6.  メッセージ（y',  y,  SID,  H）を公開鍵y’の相手側の鍵交換装置に通信部212およびネットワーク213を介して送信する（ステップ３０６）。
7.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ３０７）。【００９８】
図３に示すステップ３０２で命令201が“鍵交換開始”でなければ、命令201が“鍵交換返答”であるか否かを判定し（ステップ３０８）、命令201が“鍵交換返答”である場合、鍵交換準備部209は、次のように動作する。
1.  セッション番号SIDを、SID=（φ,  φ,  sidC,  y,  y',  "返答"）として生成する（ステップ３０９）。このセッション番号では、開始者セッション番号と返答者セッション番号が空である。
2.  上記1の動作で決定したセッション番号に対応する内部状態情報として  φ  を記憶部250の内部状態リスト207に保存する（ステップ３０９）。
3.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ３１０）。ステップ３０８で、命令201が“鍵交換返答”でない場合も同様である。【００９９】
上述のようして、鍵交換準備部209は、自身が開始側であれば、ステップ３０３から３０６の処理を行い、相手が開始側で自身が返答側であれば、ステップ３０９の処理を行う。【０１００】
続いて、鍵交換応答部210の動作を説明する。図１１は鍵交換応答部の動作手順を示すフローチャートである。図１２Ａは図１１に示す処理５の手順を示すフローチャートであり、図１２Ｂは図１１に示す処理６の手順を示すフローチャートである。図１３は図１１に示す処理７の手順を示すフローチャートである。【０１０１】
鍵交換応答部210の動作には、自身が返答側で相手が開始側である場合に相手からメッセージを受信したときの動作と、自身が開始側で相手が返答側の場合に相手からメッセージを受信したときの動作とがある。以下に、これらの動作を説明する。【０１０２】
鍵交換装置200の鍵交換応答部210は、ネットワーク213および通信部212を介して相手の鍵交換装置からメッセージ（y,  y',  SID',  H'）を受信すると（ステップ１１０１）、セッション番号SID’がSID'=（sidI,  φ,  sidC,  y',  y,  "開始"）の形式であるか否かを判定する（ステップ１１０２）。【０１０３】
なお、メッセージ（y,  y',  SID',  H'）は、図３で説明した処理と同様にして、公開鍵y’の相手の鍵交換装置で作成されたものである。このメッセージに含まれるセッション番号とハッシュ値を、それぞれSID’およびH’と表記している。【０１０４】
ステップ１１０２でＹｅｓの場合、鍵交換応答部210は、自身が返答側として、次のように動作する。
1.  メッセージの送信先が自装置の公開鍵yに一致することを確認する。一致しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる。
2.  セッション番号SID=（φ,  φ,  sidC,  y,  y',  "返答"）に対応する内部状態情報が記憶部250の内部状態リスト207に存在するか否かを調べる（ステップ１１０３）。図３で説明したステップ３０９の処理を行っていれば、その内部状態情報が内部状態リスト207に保管されている。そのセッション番号に対応する内部状態情報が存在しなければ、処理を終了して、次の入力待ちまたは受信待ちの待機状態になる（ステップ１１０５）。【０１０５】
ステップ１１０３で上記内部状態情報が存在する場合、図１２Ａに示すフローに進み、鍵交換応答部210は、次のように動作する。
3.  対応して保持していた内部状態情報  φ  を読み込む（ステップ１２０１）。そして、h'=sidI  とし、続いて、受信したメッセージに含まれるH’を読み出し、H'  =Hash（sidI,  sidC,  y',  y,  h'x,  "開始"）が成り立つことを確認する（ステップ１２０２）。この式が成り立たなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１２０８）。
4.  r  ∈Z/qZ  を乱数から生成する（ステップ１２０３）。
5.  返答者セッション番号  sidR=gr  を生成する（ステップ１２０３）。
6.  ハッシュ値H  =  Hash（sidI,  sidR,  sidC,  y,  y',  h'r,  h'x,  y'r,  "返答"）を生成する（ステップ１２０４）。
7.  受信した開始者セッション番号と生成した返答者セッション番号とをセッション番号SID=（φ,  φ,  sidC,  y,  y',  "返答"）に追加し、セッション番号SIDをSID=（sidI,  sidR,  sidC,  y,  y',  "返答"）に更新する（ステップ１２０５）。
8.  上記7の動作で更新したセッション番号に対応する内部状態情報として、（h'r｝,  y'r,  h'x）を記憶部250の内部状態リスト207に保存する（ステップ１２０６）。
9.  メッセージ（y',  y,  SID,  H）を公開鍵y’の相手側の鍵交換装置に通信部212およびネットワーク213を介して送信する（ステップ１２０７）。
10.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１２０８）。【０１０６】
一方、ステップ１１０２でＮｏの場合、鍵交換応答部210は、受信したメッセージ（y,  y',  SID',  H'）のセッション番号SID’を読み出し、SID'=（sidI,  sidR,  sidC,  y',  y,  文字列データ）の形式であるか否かを調べる（ステップ１１０６）。SID'=（sidI,  sidR,  sidC,  y',  y,  文字列データ）の形式であると、文字列データが“返答”を含むものであるか否かを判定する（ステップ１１０７）。【０１０７】
ステップ１１０７で文字列データが“返答”を含むものである場合、鍵交換応答部210は、自身が開始側として鍵交換準備部209が相手の鍵交換装置にメッセージを送ったことに対して、相手からの返答メッセージを受け取ったものと判断し、次のように動作する。
1.  メッセージの送信先が自装置の公開鍵yに一致することを確認する。一致しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる。
2.  セッション番号  SID=（sidI,  φ,  sidC,  y,  y',  "開始"）に対応する内部状態情報が記憶部250の内部状態リスト207に存在するか否かを調べる（ステップ１１０８）。図３で説明したステップ３０５の処理を行っていれば、その内部状態情報が内部状態リスト207に保管されている。そのセッション番号に対応する内部状態情報が存在しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１１１０）。
3.  ステップ１１０８で、そのセッション番号に対応する内部状態情報が存在すれば、図１２Ｂに示すフローに進み、鍵交換応答部210は、対応して保持していた内部状態情報  r  を読み込む（ステップ１２２１）。そして、h'=sidR  とし、続いて、受信したメッセージからH’を読み出し、H'=Hash（sidI,  sidR,  sidC,  y',  y,  h'r,  y'r,  h'x,  "返答"）が成り立つことを確認する（ステップ１２２２）。成り立たなければ、次の入力待ちまたは受信待ちの待機状態になる（ステップ１２２８）。
4.  受信した返答者セッション番号をセッション番号SID=（sidI,  φ,  sidC,  y,  y',  "開始"）に追加し、セッション番号SIDをSID=（sidI,  sidR,  sidC,  y,  y',  "開始"）に更新する（ステップ１２２３）。
5.  ハッシュ値H''  =  Hash（sidI,  sidR,  sidC,  y,  y',  h'r,  y'r,  h'x,  "開始"）を生成し（ステップ１２２４）、交換鍵  K  =  Hash（sidI,  sidR,  sidC,  y,  y',  h'r,  y'r,  h'x,  "鍵"）を生成する（ステップ１２２５）。
6.  上記4で更新したセッション番号に対応する交換結果として  K  を記憶部250の交換結果リスト208に保存する（ステップ１２２５）。
7.  メッセージ（y',  y,  SID,  H''）を公開鍵y’の相手側の鍵交換装置に通信部212およびネットワーク213を介して送信する（ステップ１２２６）。
8.  上記4の動作で更新したセッション番号に対応する内部状態情報  r  を消去する（ステップ１２２７）。
9.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１２２８）。【０１０８】
さらに、ステップ１１０７で文字列データが“開始”であると、このメッセージはステップ１２２６で開始側の鍵交換装置が返答側の鍵交換装置に送信したメッセージに相当する。開始側から受信する２回のメッセージのいずれにも、SID’の文字列データに“開始”が含まれているが、SID’に返答者セッション番号が含まれているか否かで２回のメッセージのうちいずれであるかを判定することが可能である。返答者セッション番号が含まれていれば、開始側から送信された２回目のメッセージに相当する。【０１０９】
鍵交換応答部210は、メッセージ（y,  y',  SID',  H''）を受信し（ステップ１１０１）、このメッセージのSID’を読み出し、SID'=（sidI,  sidR,  sidC,  y',  y,  "開始"）の形式であると（ステップ１１０７）、このメッセージが開始側からの２回目のメッセージと判断し、次のように動作する。
1.  メッセージの送信先が自装置の公開鍵yに一致することを確認する。一致しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる。
2.  セッション番号  SID=（sidI,  sidR,  sidC,  y,  y',  "返答"）に対応する内部状態情報が記憶部250の内部状態リスト207に存在するか否かを調べる（ステップ１１１２）。図１２Ａで説明したステップ１２０６の処理を行っていれば、その内部状態情報が内部状態リスト207に保管されている。そのセッション番号に対応する内部状態情報が存在しなければ、処理を終了して、次の入力待ちまたは受信待ちの待機状態になる（ステップ１１１４）。【０１１０】
ステップ１１１２で上記内部状態情報が存在する場合、図１３に示すフローに進み、鍵交換応答部210は、次のように動作する。
3.  対応して保持していた内部状態情報  （h'r｝,  y'r,  h'x）  を読み込む（ステップ１３０１）。そして、h'=sidI  とし、続いて、受信したメッセージに含まれるH''を読み出し、H''=Hash（sidI,  sidR,  sidC,  y',  y,  h'r,  h'x,  y'r,  "開始"）が成り立つことを確認する（ステップ１３０２）。この式が成り立たなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１３０５）。
4.  交換鍵  K  =  Hash（sidI,  sidR,  sidC,  y,  y',  h'r,  y'r,  h'x,  "鍵"）を生成する（ステップ１３０３）。
5.  ステップ１２０５で更新したセッション番号に対応する交換結果として  K  を記憶部250の交換結果リスト208に保存する（ステップ１３０３）。
6.  ステップ１２０５で更新したセッション番号に対応する内部状態情報を記憶部250の内部状態リスト207から消去する（ステップ１３０４）。
7.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１３０５）。【０１１１】
なお、鍵失効部211の動作は、第１の実施形態の図６で説明した処理と同様であるため、ここではその詳細な説明を省略する。【０１１２】
本実施形態の鍵交換装置によれば、メッセージの通信回数が３回となるが、その他の点については第１の実施形態と同様な効果が得られる。暗号化などの負荷の大きい演算を必要としない。また、認証のためのハッシュ値の計算に用いるパラメータが第１の実施形態よりも１つ少ないため、第１の実施形態よりも計算の負荷が軽減する。【０１１３】
（第４の実施形態）
本実施形態の鍵交換装置は、第２の実施形態と同様な構成であるが、動作が異なっている。本実施形態では構成についての詳細な説明を省略し、以下に、本実施形態の鍵交換装置の動作について詳細に説明する。【０１１４】
第２の実施形態の図８で説明したように、鍵交換装置700の鍵交換準備部709に、入力部707を介して、命令701、初期セッション番号702、乱数703、自己秘密鍵704、自己装置番号705、相手装置番号706およびシステム鍵716が入力される（ステップ８０１）。初期セッション番号702をsidCとし、自己秘密鍵704をx  ∈  Gとし、自己装置番号705をidとし、相手装置番号706をid'とする。そして、システム鍵716をm  ∈  Gとする。【０１１５】
鍵交換準備部709は、命令701が“鍵交換開始”であるか否かを判定し（ステップ８０２）、命令701が“鍵交換開始”である場合、次のように動作する。ただし、s  が  m=  gs  を満たすなら、x=  Hash（g,  m,  id）s  になるとする。
1.  r  ∈Z/qZ  を乱数から生成する（ステップ８０３）。
2.  開始者セッション番号  sidI=gr  を生成する（ステップ８０３）。
3.  ハッシュ値と暗号文として、
y'  =Hash'（g,  m,  id'），
u  =  Hash'（sidI,  sidC,  id,  id',  e（yr,  y'）,  "開始"），
c  =  Hash（u）+  r  ，
H  =  Hash（sidI,  sidC,  id,  id',  u,  "開始"），
を生成する（ステップ８０４）。
4.  セッション番号SIDを、SID=（sidI,  φ,  sidC,  id,  id',  "開始"）として生成する（ステップ８０５）。
5.  上記4の動作で決定したセッション番号に対応する内部状態情報として  u  を記憶部750の内部状態リスト708に保存する（ステップ８０５）。
6.  メッセージ（id',  id,  SID,  （c,  H））を装置番号id'の相手側の鍵交換装置に通信部714およびネットワーク715を介して送信する（ステップ８０６）。
7.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ８０７）。【０１１６】
図８に示すステップ８０２で命令701が“鍵交換開始”でなければ、命令701が“鍵交換返答”であるか否かを判定し（ステップ８０８）、命令701が“鍵交換返答”である場合、鍵交換準備部709は、次のように動作する。
1.  セッション番号SIDを、SID=（φ,  φ,  sidC,  id,  id',  "返答"）として生成する（ステップ８０９）。
2.  上記1の動作で決定したセッション番号に対応する内部状態情報として  φ  を記憶部750の内部状態リスト708に保存する（ステップ８０９）。
3.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ８１０）。ステップ８０８で、命令701が“鍵交換返答”でない場合も同様である。【０１１７】
上述のようして、鍵交換準備部709は、自身が開始側であれば、ステップ８０３から８０６の処理を行い、相手が開始側で自身が返答側であれば、ステップ８０９の処理を行う。【０１１８】
続いて、鍵交換応答部710の動作を説明する。図１４は鍵交換応答部の動作手順を示すフローチャートである。図１５Ａは図１４に示す処理８の手順を示すフローチャートであり、図１５Ｂは図１４に示す処理９の手順を示すフローチャートである。図１６は図１４に示す処理１０の手順を示すフローチャートである。【０１１９】
鍵交換応答部710の動作には、自身が返答側で相手が開始側である場合に相手からメッセージを受信したときの動作と、自身が開始側で相手が返答側の場合に相手からメッセージを受信したときの動作とがある。以下に、これらの動作を説明する。【０１２０】
鍵交換装置700の鍵交換応答部710は、ネットワーク715および通信部714を介して相手の鍵交換装置からメッセージ（id,  id',  SID',  （c',  H'））を受信すると（ステップ１４０１）、セッション番号SID’がSID'=（sidI,  φ,  sidC,  id',  id,  "開始"）の形式であるか否かを判定する（ステップ１４０２）。【０１２１】
なお、メッセージ（id,  id',  SID',  （c',  H'））は、図８で説明した処理と同様にして、装置番号id'の相手の鍵交換装置で作成されたものである。このメッセージに含まれるセッション番号、暗号文およびハッシュ値を、それぞれSID’、c’およびH’と表記している。【０１２２】
ステップ１４０２でＹｅｓの場合、鍵交換応答部710は、自身が返答側として、次のように動作する。
1.  メッセージの送信先が自装置の番号idに一致することを確認する。一致しなければ、次の入力あるいは通信の受信を待って停止する。
2.  セッション番号  SID=（φ,  φ,  sidC,  id,  id',  "返答"）  に対応する内部状態情報が記憶部750の内部状態リスト708に存在するか否かを調べる（ステップ１４０３）。図８で説明したステップ８０９の処理を行っていれば、その内部状態情報が内部状態リスト708に保管されている。そのセッション番号に対応する内部状態情報が存在しなければ、処理を終了して、次の入力待ちまたは受信待ちの待機状態になる（ステップ１４０５）。【０１２３】
ステップ１４０３で上記内部状態情報が存在する場合、図１５Ａに示すフローに進み、鍵交換応答部710は、次のように動作する。
3.  対応して保持していた内部状態情報  φ  を読み込む（ステップ１５０１）。そして、y'=  Hash'（g,  m,  id'）、h'=  sidI  とし、
u'  =  Hash'（sidI,  sidC,  id',  id,  e（h',  x）,  "開始"），
r'=  c'  -  Hash（u'），
を生成することで、暗号文を復号する（ステップ１５０１）。
続いて、h'  =  gr'，H'  =  Hash（sidI,  sidC,  id',  id,  u',  "開始"）が成り立つことを確認する（ステップ１５０２）。これらが成り立たなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１５０８）。
4.  r  ∈Z/qZ  を乱数から生成する（ステップ１５０３）。
5.  返答者セッション番号  sidR=gr  を生成する（ステップ１５０３）。
6.  u  =  Hash'（sidI,  sidR,  sidC,  id,  id',  e（yr,  y'）,  "返答"），
c  =  hash（u）  +  r，
H  =  Hash（sidI,  sidR,  sidC,  id,  id',  u,  u',  "返答"），
を生成する（ステップ１５０４）。このようにして暗号文およびハッシュ値を生成する。
7.  受信した開始者セッション番号と生成した返答者セッション番号とをセッション番号SID=  （φ,  φ,  sidC,  id,  id',  "返答"）に追加し、セッション番号SIDを、SID=  （sidI,  sidR,  sidC,  id,  id',"返答"）に更新する(ステップ１５０５)。
8.  上記7の動作で更新したセッション番号に対応する内部状態情報として、（u,  u'）を記憶部750の交換結果リスト711に保存する（ステップ１５０６）。
9.  メッセージ（id',  id,  SID,  （c,  H））を  装置番号id'の相手側の鍵交換装置に通信部714およびネットワーク715を介して送信する（ステップ１５０７）。
10.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１５０８）。【０１２４】
一方、ステップ１４０２でＮｏの場合、鍵交換応答部710は、受信したメッセージ（id,  id',  SID',  （c',  H'））のセッション番号SID’を読み出し、SID'=（sidI,  sidR,  sidC,  id',  id,  文字列データ）の形式であるか否かを調べる（ステップ１４０６）。SID'=（sidI,  sidR,  sidC,  id',  id,  文字列データ）の形式であると、文字列データが“返答”を含むものであるか否かを判定する（ステップ１４０７）。【０１２５】
ステップ１４０７で文字列データが“返答”を含むものである場合、鍵交換応答部710は、自身が開始側として鍵交換準備部709が相手の鍵交換装置にメッセージを送ったことに対して、相手からの返答メッセージを受け取ったものと判断し、次のように動作する。
1.  メッセージの送信先が自装置の番号idに一致することを確認する。一致しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる。
2.  セッション番号SID=（sidI,  φ,  sidC,  id,  id',  "開始"）に対応する内部状態情報が記憶部750の内部状態リスト708に存在するか否かを調べる(ステップ１４０８)。図８で説明したステップ８０５の処理を行っていれば、その内部状態情報が内部状態リスト708に保管されている。そのセッション番号に対応する内部状態情報が存在しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１４１０）。【０１２６】
ステップ１４０８で上記内部状態情報が存在する場合、図１５Ｂに示すフローに進み、鍵交換応答部710は、次のように動作する。
3.  対応して保持していた内部状態情報  u  を読み込む（ステップ１５２１）。そして、y'  =Hash'（g,  m,  id'），h'  =  sidR  とし、
u'  =  Hash'（sidI,  sidR,  sidC,  id',  id,  e（h',  x）,  "返答"），
r'  =  c'  -  Hash（u'），
を生成することで、暗号文を復号する（ステップ１５２１）。
続いて、  h'  =  gr'，H'  =  Hash（sidI,  sidR,  sidC,  id',  id,  u',  u,  "開始"）が成り立つことを確認する（ステップ１５２２）。成り立たなければ、次の入力待ちまたは受信待ちの待機状態になる（ステップ１５２８）。
4.  受信した返答者セッション番号をセッション番号SID=（sidI,  φ,  sidC,  id,  id',  "開始"）に追加し、セッション番号SIDを、SID=（sidI,  sidR,  sidC,  id,  id',  "開始"）に更新する（ステップ１５２３）。
5.  ハッシュ値H''  =  Hash（sidI,  sidR,  sidC,  id,  id',  u,  u',  "開始"）を生成し（ステップ１５２４）、交換鍵  K  =  Hash（sidI,  sidR,  sidC,  id,  id',  u,  u',  "鍵"）を生成する（ステップ１５２５）。
6.  上記4で更新したセッション番号に対応する交換結果として  K  を記憶部750の交換結果リスト711に保存する（ステップ１５２５）。
7.  メッセージ（id',  id,  SID,  H''）を装置番号id'の相手側の鍵交換装置に通信部714およびネットワーク715を介して送信する（ステップ１５２６）。
8.  上記4で更新したセッション番号に対応する内部状態情報  u  を記憶部750の内部状態リスト708から消去する（ステップ１５２７）。
9.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１５２８）。【０１２７】
さらに、ステップ１４０７で文字列データが“開始”であると、このメッセージはステップ１５２６で開始側の鍵交換装置が返答側の鍵交換装置に送信したメッセージに相当する。開始側から受信する２回のメッセージのいずれにも、SID’の文字列データに“開始”が含まれているが、SID’に返答者セッション番号が含まれているか否かで２回のメッセージのうちいずれであるかを判定することが可能である。返答者セッション番号が含まれていれば、開始側から送信された２回目のメッセージに相当する。【０１２８】
鍵交換応答部710は、メッセージ（id,  id',  SID',  H''）を受信し（ステップ１４０１）、このメッセージのSID’を読み出し、SID'=（sidI,  sidR,  sidC,  id',  id,  "開始"）の形式であると（ステップ１４０７）、このメッセージが開始側からの２回目のメッセージと判断し、次のように動作する。
1.  メッセージの送信先が自装置の番号idに一致することを確認する。一致しなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる。
2.  セッション番号  SID=（sidI,  sidR,  sidC,  id,  id',  "返答"）に対応する内部状態情報が記憶部750の内部状態リスト708に存在するか否かを調べる（ステップ１４１２）。図１５Ａで説明したステップ１５０６の処理を行っていれば、その内部状態情報が内部状態リスト708に保管されている。そのセッション番号に対応する内部状態情報が存在しなければ、処理を終了して、次の入力待ちまたは受信待ちの待機状態になる（ステップ１４１４）。【０１２９】
ステップ１４１２で上記内部状態情報が存在する場合、図１６に示すフローに進み、鍵交換応答部710は、次のように動作する。
3.  対応して保持していた内部状態情報  （u,  u'）  を読み込む（ステップ１６０１）。そして、受信したメッセージに含まれるH''を読み出し、H''=Hash（sidI,  sidR,  sidC,  id',  id,  u',  u,  "開始"）が成り立つことを確認する（ステップ１６０２）。この式が成り立たなければ、処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１６０５）。
4.  交換鍵  K  =  Hash（sidI,  sidR,  sidC,  id',  id,  u',  u,  "鍵"）を生成する（ステップ１６０３）。
5.  ステップ１５０５で更新したセッション番号に対応する交換結果として  K  を記憶部750の交換結果リスト711に保存する（ステップ１６０３）。
6.  ステップ１５０５で更新したセッション番号に対応する内部状態情報を記憶部750の内部状態リスト708から消去する（ステップ１６０４）。
7.  処理を終了し、次の入力待ちまたは受信待ちの待機状態になる（ステップ１６０５）。【０１３０】
なお、鍵失効部713の動作は、図６を参照して第２の実施形態で説明した処理と同様であるため、ここではその詳細な説明を省略する。【０１３１】
本実施形態の鍵交換装置によれば、メッセージの通信回数が３回となるが、その他の点については第２の実施形態と同様な効果が得られる。相手の公開鍵を知らなくても鍵交換処理を実行可能である。認証のためのハッシュ値の計算に用いるパラメータが第２の実施形態よりも１つ少ないため、第２の実施形態よりも計算の負荷が軽減する。【０１３２】
（第５の実施形態）
本実施形態は、第１の実施形態から第４の実施形態のそれぞれにおいて説明した鍵交換装置が複数設けられた鍵交換処理システムである。本実施形態のシステムの複数の鍵交換装置は、第１の実施形態から第４の実施形態のいずれか１つの実施形態における種類の装置に統一されているものとする。また、鍵交換装置の構成および動作については第１の実施形態から第４の実施形態のそれぞれに詳細に説明したため、ここでは、装置間のやり取りについて簡単に説明する。【０１３３】
複数の鍵交換装置がネットワークを介して互いに通信可能な状況に設置されている。そのうち任意の２台の鍵交換装置を、鍵交換処理を行う対象装置の一組とする。第１の実施形態または第３の実施形態の装置であれば、公開鍵をそれぞれy、y'とする。第２の実施形態または第４の実施形態の装置であれば、装置番号をそれぞれid、id'とする。以下では、公開鍵yまたは装置番号idに対応する装置を一方の鍵交換装置とし、公開鍵y’または装置番号id’に対応する装置を他方の鍵交換装置とする。【０１３４】
初期セッション番号sidCを決定し、一方の鍵交換装置に、鍵交換開始命令とともに、初期セッション番号sidCと、相手先を示す公開鍵y'または装置番号id'を入力する。また、他方の鍵交換装置に、鍵交換返答命令とともに、初期セッション番号sidCと、相手先を示す公開鍵yまたは装置番号idを入力する。【０１３５】
それ以降、第１の実施形態から第４の実施形態のそれぞれにおいて説明したように、２台のうち片方の装置が通信部およびネットワークを介してもう片方の装置宛にメッセージを送出すると、もう片方の装置がネットワークおよび通信部を介してそのメッセージを受信するというデータ通信を行う。両装置は、それぞれの実施形態で説明したように、自身の交換結果に交換した鍵を書き込んで鍵交換処理を終了する。【０１３６】
また、鍵失効命令とともにセッション番号SIDを鍵交換装置に入力すると、鍵交換装置は、このセッション番号SIDに対応する交換結果を消去する。【０１３７】
本実施形態のシステムにおいては、上記鍵交換処理を任意の組の鍵交換装置に対して実施させてもよく、各鍵交換装置は、一連の鍵交換処理が終了するのを待たずに、他の鍵交換処理を行っても問題ない。【０１３８】
以上説明したように、第１の実施形態および第２の実施形態のそれぞれの鍵交換装置は、通信回数２回で、否認可能な認証付き鍵交換を可能にする。第２の実施形態および第４の実施形態のそれぞれの鍵交換装置は、相手の公開鍵を必要とせずに、否認可能な認証付き鍵交換を可能にする。第１の実施形態および第３の実施形態のそれぞれの鍵交換装置は、暗号化などの負荷の大きい演算を必要とせずに、否認可能な認証付き鍵交換を可能にする。よって、本発明の鍵交換装置は、演算および通信の負荷が従来よりも軽減する。【０１３９】
本発明の鍵交換方法を、ユーザがインターネットなどのネットワークを介してサービスを受ける際に情報処理装置に実行させれば、ユーザはネットワークのサービスをサービスプロバイダから受けるときに、認証を受けた上で、安全な通信を行うことができる。また、その後に、ユーザがサービスを受けたことをサービスプロバイダが他人に証明することができなくなる。ユーザも、サービスプロバイダがサービスを提供したことを証明できなくなる。【０１４０】
認証付の通信を行うと、認証データにより通信をしたことを証明できる場合が多いが、本発明の鍵交換装置では、相手装置と通信をした結果を履歴に残さないため、そのようなことが起きない。それゆえ、強いプライバシーが要求されるサービスにおいて、本発明の鍵交換装置が実行する方法は有効である。【０１４１】
なお、コンピュータが実行するためのプログラムに本発明の鍵交換装置の動作を書き込み、本発明の鍵交換処理方法をコンピュータに実行させてもよい。【０１４２】
実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【０１４３】
この出願は、２００７年２月１５日に出願された日本出願の特願２００７−０３５１１２の内容が全て取り込まれており、この日本出願を基礎として優先権を主張するものである。
【図１】
2008099875.tif 000003
【図２】
2008099875.tif 000004
【図３】
2008099875.tif 000005
【図４】
2008099875.tif 000006
【図５Ａ】
2008099875.tif 000007
【図５Ｂ】
2008099875.tif 000008
【図６】
2008099875.tif 000009
【図７】
2008099875.tif 000010
【図８】
2008099875.tif 000011
【図９】
2008099875.tif 000012
【図１０Ａ】
2008099875.tif 000013
【図１０Ｂ】
2008099875.tif 000014
【図１１】
2008099875.tif 000015
【図１２Ａ】
2008099875.tif 000016
【図１２Ｂ】
2008099875.tif 000017
【図１３】
2008099875.tif 000018
【図１４】
2008099875.tif 000019
【図１５Ａ】
2008099875.tif 000020
【図１５Ｂ】
2008099875.tif 000021
【図１６】
2008099875.tif 000022
【国際調査報告】
2008099875.tif 000023
2008099875.tif 000024
2008099875.tif 000025
2008099875.tif 000026