(57)【要約】【課題】一方のエンティティが他方のエンティティよりも計算量の少ない処理で相互認証を実現できる相互認証方法、相互認証装置、及び相互認証システムを提供する。【解決手段】本発明の相互認証方法は、エンティティＡが、チャレンジＸ＝Ｅ（ＲＡ）をエンティティＢに送信するステップと、エンティティＢが、受信したチャレンジＸに対するレスポンスＹ＝Ｄ（Ｘ）とチャレンジＲＢをエンティティＡに送信するステップと、エンティティＡが、受信したレスポンスＹを検証するステップと、エンティティＡが、受信したチャレンジＲＢに対するレスポンスＺ＝Ｅ（ＲＢ）をエンティティＢに送信するステップと、エンティティＢが、受信したレスポンスＺを検証するステップとを有し、前記ステップで行うエンティティＡによる処理の計算量及びエンティティＢによる処理の計算量のいずれか一方が他方よりも少ないものである。【選択図】        図１
2006025298.tif 000002
【特許請求の範囲】
【請求項１】
第１のエンティティと第２のエンティティの間で情報をやりとりして互いに相手の正当性を検証するステップを有し、
前記第１のエンティティによる検証のための処理の計算量及び前記第２のエンティティによる検証相互認証のための処理の計算量のいずれか一方が他方よりも少ない
ことを特徴とする相互認証方法。
【請求項２】
前記互いに相手の正当性を検証するステップにおいて、
前記第１のエンティティと前記第２のエンティティの内の一方が、共通の鍵情報を用いた変換を行い、
前記第１のエンティティと前記第２のエンティティの内の他方が、前記共通の鍵情報を用いた逆変換を行い、
前記変換の計算量と前記逆変換の計算量が異なる方式を用いる
ことを特徴とする請求項１に記載の相互認証方法。
【請求項３】
前記互いに相手の正当性を検証するステップにおいて、
公開鍵暗号に基づく方式で鍵情報の値を設定して、前記第１のエンティティが行う暗号化処理の計算量と前記第２のエンティティが行う復号処理の計算量が異なり、かつ、前記第２のエンティティが行う暗号化処理の計算量と前記第１のエンティティが行う復号処理の計算量が異なる方式を用いる
ことを特徴とする請求項１に記載の相互認証方法。
【請求項４】
前記互いに相手の正当性を検証するステップにおいて、
公開鍵暗号に基づく方式で鍵情報の値を設定して、前記第１のエンティティが行う暗号化処理の計算量が前記第２のエンティティが行う復号処理の計算量より大きく、かつ、前記第２のエンティティが行う暗号化処理の計算量が前記第１のエンティティが行う復号処理の計算量より小さくする公開鍵暗号化方式、又は、
公開鍵暗号に基づく方式で鍵情報の値を設定して、前記第１のエンティティが行う暗号化処理の計算量が前記第２のエンティティが行う復号処理の計算量より小さく、かつ、前記第２のエンティティが行う暗号化処理の計算量が前記第１のエンティティが行う復号処理の計算量より大きくする公開鍵暗号化方式
を用いることを特徴とする請求項１に記載の相互認証方法。
【請求項５】
前記互いに相手の正当性を検証するステップにおいて、
ディジタル署名に基づく方式で鍵情報の値を設定して、前記第１のエンティティが行う署名生成処理の計算量と前記第２のエンティティが行う署名検証処理の計算量が異なり、かつ、前記第２のエンティティが行う署名生成処理の計算量と前記第１のエンティティが行う署名検証処理の計算量が異なる方式を用いる
ことを特徴とする請求項１に記載の相互認証方法。
【請求項６】
前記互いに相手の正当性を検証するステップにおいて、
ディジタル署名に基づく方式で鍵情報の値を設定して、前記第１のエンティティが行う署名生成処理の計算量が前記第２のエンティティが行う署名検証処理の計算量より大きく、かつ、前記第２のエンティティが行う署名生成処理の計算量が前記第１のエンティティが行う署名検証処理の計算量より小さくするディジタル署名方式、又は、
ディジタル署名に基づく方式で鍵情報の値を設定して、前記第１のエンティティが行う署名生成処理の計算量が前記第２のエンティティが行う署名検証処理の計算量より小さく、かつ、前記第２のエンティティが行う署名生成処理の計算量が前記第１のエンティティが行う署名検証処理の計算量より大きくするディジタル署名方式
を用いることを特徴とする請求項１に記載の相互認証方法。
【請求項７】
前記互いに相手の正当性を検証するステップにおいて、
公開鍵暗号及びディジタル署名に基づく方式で鍵情報の値を設定して、前記第１のエンティティが行う暗号化処理の計算量が前記第２のエンティティが行う復号処理の計算量より大きく、かつ、前記第２のエンティティが行う暗号化処理の計算量が前記第１のエンティティが行う復号処理の計算量より小さくする公開鍵暗号化方式、並びに、前記第１のエンティティが行う署名生成処理の計算量が前記第２のエンティティが行う署名検証処理の計算量より大きく、かつ、前記第２のエンティティが行う署名生成処理の計算量が前記第１のエンティティが行う署名検証処理の計算量より小さくするディジタル署名方式、又は、
公開鍵暗号及びディジタル署名に基づく方式で鍵情報の値を設定して、前記第１のエンティティが行う暗号化処理の計算量が前記第２のエンティティが行う復号処理の計算量より小さく、かつ、前記第２のエンティティが行う暗号化処理の計算量が前記第１のエンティティが行う復号処理の計算量より大きくする公開鍵暗号化方式、並びに、前記第１のエンティティが行う署名生成処理の計算量が前記第２のエンティティが行う署名検証処理の計算量より小さく、かつ、前記第２のエンティティが行う署名生成処理の計算量が前記第１のエンティティが行う署名検証処理の計算量より大きくするディジタル署名方式
を用いることを特徴とする請求項１に記載の相互認証方法。
【請求項８】
前記互いに相手の正当性を検証するステップにおいて、前記第１のエンティティと前記第２のエンティティの間で１つ又は複数の秘密情報を共有することを特徴とする請求項１から７までのいずれかに記載の相互認証方法。
【請求項９】
前記互いに相手の正当性を検証するステップは、
前記第１のエンティティが、第１のチャレンジ情報を生成し、前記第１のチャレンジ情報を前記第２のエンティティに送信するステップと、
前記第２のエンティティが、受信した前記第１のチャレンジ情報に対する第１のレスポンス情報を計算し、第２のチャレンジ情報を生成し、前記第１のレスポンス情報と前記第２のチャレンジ情報とを前記第１のエンティティに送信するステップと、
前記第１のエンティティが、受信した前記第１のレスポンス情報を検証するステップと、
前記第１のエンティティが、受信した前記第２のチャレンジ情報に対する第２のレスポンス情報を計算し、前記第２のレスポンス情報を前記第２のエンティティに送信するステップと、
前記第２のエンティティが、受信した前記第２のレスポンス情報を検証するステップと
を含むことを特徴とする請求項１に記載の相互認証方法。
【請求項１０】
前記互いに相手の正当性を検証するステップは、
前記第１のエンティティが、暗号化関数を用いて第１のチャレンジ情報を生成し、前記第１のチャレンジ情報を前記第２のエンティティに送信するステップと、
前記第２のエンティティが、受信した前記第１のチャレンジ情報に対する第１のレスポンス情報を復号関数を用いて計算し、第２のチャレンジ情報を生成し、前記第１のレスポンス情報と前記第２のチャレンジ情報とを前記第１のエンティティに送信するステップと、
前記第１のエンティティが、受信した前記第１のレスポンス情報を検証するステップと、
前記第１のエンティティが、暗号化関数を用いて受信した前記第２のチャレンジ情報に対する第２のレスポンス情報を計算し、前記第２のレスポンス情報を前記第２のエンティティに送信するステップと、
前記第２のエンティティが、受信した前記第２のレスポンス情報を復号関数を用いて復号して検証するステップと
を含むことを特徴とする請求項２に記載の相互認証方法。
【請求項１１】
前記互いに相手の正当性を検証するステップは、
前記第１のエンティティが、第１のチャレンジ情報を生成し、前記第１のチャレンジ情報を前記第２のエンティティに送信するステップと、
前記第２のエンティティが、受信した前記第１のチャレンジ情報に対する第１のレスポンス情報を自身が保持する秘密鍵を用いた暗号化関数により計算し、第２のチャレンジ情報を生成し、前記第１のレスポンス情報と前記第２のチャレンジ情報とを前記第１のエンティティに送信するステップと、
前記第１のエンティティが、前記第２のエンティティの公開鍵を用いた復号関数により、受信した前記第１のレスポンス情報を検証するステップと、
前記第１のエンティティが、受信した前記第２のチャレンジ情報に対する第２のレスポンス情報を自身が保持する秘密鍵を用いた暗号化関数により計算し、前記第２のレスポンス情報を前記第２のエンティティに送信するステップと、
前記第２のエンティティが、前記第１のエンティティの公開鍵を用いた復号関数により、受信した前記第２のレスポンス情報を検証するステップと
を含むことを特徴とする請求項３に記載の相互認証方法。
【請求項１２】
前記互いに相手の正当性を検証するステップは、
前記第１のエンティティが、第１のチャレンジ情報を生成し、前記第１のチャレンジ情報を前記第２のエンティティに送信するステップと、
前記第２のエンティティが、受信した前記第１のチャレンジ情報に対する第１のレスポンス情報を署名生成関数を用いて計算し、第２のチャレンジ情報を生成し、前記第１のレスポンス情報と前記第２のチャレンジ情報とを前記第１のエンティティに送信するステップと、
前記第１のエンティティが、署名検証関数により、受信した前記第１のレスポンス情報を検証するステップと、
前記第１のエンティティが、受信した前記第２のチャレンジ情報に対する第２のレスポンス情報を署名生成関数を用いて計算し、前記第２のレスポンス情報を前記第２のエンティティに送信するステップと、
前記第２のエンティティが、署名検証関数により、受信した前記第２のレスポンス情報を検証するステップと
を含むことを特徴とする請求項５に記載の相互認証方法。
【請求項１３】
前記互いに相手の正当性を検証するステップは、
前記第１のエンティティが、第１のビット列及び第２のビット列から第１のチャレンジ情報を生成し、前記第１のチャレンジ情報を前記第２のエンティティに送信するステップと、
前記第２のエンティティが、受信した前記第１のチャレンジ情報に基づき第３のビット列及び第４のビット列を計算し、第２のチャレンジ情報を生成し、前記第３のビット列を前記第１のレスポンス情報として前記第２のチャレンジ情報と共に前記第１のエンティティに送信するステップと、
前記第１のエンティティが、受信した前記第１のレスポンス情報を検証するステップと、
前記第１のエンティティが、前記第２のビット列を共通秘密情報にするステップと、
前記第１のエンティティが、受信した前記第２のチャレンジ情報に対する第２のレスポンス情報を計算し、前記第２のレスポンス情報を前記第２のエンティティに送信するステップと、
前記第２のエンティティが、受信した前記第２のレスポンス情報を検証するステップと、
前記第２のエンティティが、前記第４のビット列を共通秘密情報にするステップと
を含むことを特徴とする請求項８に記載の相互認証方法。
【請求項１４】
相手エンティティとの間で相互認証を実行する相互認証装置において、
自身のチャレンジ情報及び自身のレスポンス情報を送信する送信手段と、
前記相手エンティティからのレスポンス情報及び前記相手エンティティからのチャレンジ情報を受信する受信手段と、
前記自身のチャレンジ情報を生成するチャレンジ生成手段と、
前記相手エンティティからのチャレンジ情報に基づいて前記自身のレスポンス情報を生成するレスポンス生成手段と、
前記相手エンティティからのレスポンス情報を検証する検証手段と
を有し、
相互認証において自身が処理した計算量が、前記相手エンティティが処理した計算量と異なる
ことを特徴とする相互認証装置。
【請求項１５】
自身が行う共通の鍵情報を用いた変換の計算量と、前記相手エンティティが行う前記共通の鍵情報を用いた逆変換の計算量が異なることを特徴とする請求項１４に記載の相互認証装置。
【請求項１６】
公開鍵暗号に基づく方式で鍵情報の値を設定して、自身が行う暗号化処理の計算量と前記相手エンティティが行う復号処理の計算量が異なり、かつ、前記相手エンティティが行う暗号化処理の計算量と自身が行う復号処理の計算量が異なる方式を用いる
ことを特徴とする請求項１４に記載の相互認証装置。
【請求項１７】
公開鍵暗号に基づく方式で鍵情報の値を設定して、自身が行う暗号化処理の計算量を前記相手エンティティが行う復号処理の計算量より大きく、かつ、前記相手エンティティが行う暗号化処理の計算量を自身が行う復号処理の計算量より小さくする公開鍵暗号化方式、又は、
公開鍵暗号に基づく方式で鍵情報の値を設定して、前記自身が行う暗号化処理の計算量を前記相手エンティティが行う復号処理の計算量より小さく、かつ、前記相手エンティティが行う暗号化処理の計算量を自身が行う復号処理の計算量より大きくする公開鍵暗号化方式
を用いることを特徴とする請求項１４に記載の相互認証装置。
【請求項１８】
ディジタル署名に基づく方式で鍵情報の値を設定して、自身が行う署名生成処理の計算量と前記相手エンティティが行う署名検証処理の計算量が異なり、かつ、前記相手エンティティが行う署名生成処理の計算量と自身が行う署名検証処理の計算量が異なる方式を用いる
ことを特徴とする請求項１４に記載の相互認証装置。
【請求項１９】
ディジタル署名に基づく方式で鍵情報の値を設定して、自身が行う署名生成処理の計算量を前記相手エンティティが行う署名検証処理の計算量より大きく、かつ、前記相手エンティティが行う署名生成処理の計算量を自身が行う署名検証処理の計算量より小さくするディジタル署名方式、又は、
ディジタル署名に基づく方式で鍵情報の値を設定して、自身が行う署名生成処理の計算量を前記相手エンティティが行う署名検証処理の計算量より小さく、かつ、前記相手エンティティが行う署名生成処理の計算量を自身が行う署名検証処理の計算量より大きくするディジタル署名方式
を用いることを特徴とする請求項１４に記載の相互認証装置。
【請求項２０】
公開鍵暗号及びディジタル署名に基づく方式で鍵情報の値を設定して、自身が行う暗号化処理の計算量を前記相手エンティティが行う復号処理の計算量より大きく、かつ、前記相手エンティティが行う暗号化処理の計算量を自身が行う復号処理の計算量より小さくする公開鍵暗号化方式、並びに、自身が行う署名生成処理の計算量を前記相手エンティティが行う署名検証処理の計算量より大きく、かつ、前記相手エンティティが行う署名生成処理の計算量を自身が行う署名検証処理の計算量より小さくするディジタル署名方式、又は、
公開鍵暗号及びディジタル署名に基づく方式で鍵情報の値を設定して、自身が行う暗号化処理の計算量を前記相手エンティティが行う復号処理の計算量より小さく、かつ、前記相手エンティティが行う暗号化処理の計算量を自身が行う復号処理の計算量より大きくする公開鍵暗号化方式、並びに、自身が行う署名生成処理の計算量を前記相手エンティティが行う署名検証処理の計算量より小さく、かつ、前記相手エンティティが行う署名生成処理の計算量を自身が行う署名検証処理の計算量より大きくするディジタル署名方式
を用いることを特徴とする請求項１４に記載の相互認証装置。
【請求項２１】
自身のチャレンジ情報及び自身のレスポンス情報に１つ又は複数の秘密情報を含ませる手段と、
前記秘密情報を管理する手段と
を有し、
前記相手エンティティを認証する際に、自身と前記相手エンティティの間で１つ又は複数の秘密情報を共有することを特徴とする請求項１４から２０までのいずれかに記載の相互認証装置。
【請求項２２】
前記相手エンティティからのチャレンジ情報及びレスポンス情報に含まれる１つ又は複数の秘密情報を抽出する手段と、
前記秘密情報を管理する手段と
を有し、
前記相手エンティティを認証する際に、自身と前記相手エンティティの間で１つ又は複数の秘密情報を共有することを特徴とする請求項１４から２１までのいずれかに記載の相互認証装置。
【請求項２３】
請求項１から請求項１３までのいずれかに記載の相互認証方法を行う前記第１のエンティティと前記第２のエンティティを有することを特徴とする相互認証システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、相互認証を行う２つのエンティティの内の一方のエンティティの計算量が他方のエンティティの計算量よりも少なくなるようにした相互認証方法、この方法を実施する相互認証装置及び相互認証システムに関し、例えば、一方のエンティティであるＩＣカード（サービス利用者側の情報端末）と他方のエンティティであるリーダ／ライタ（サービス提供者側の情報端末）のように処理能力に差のある２つのエンティティ間における相互認証に関するものである。
【背景技術】
【０００２】
近年、偽造が難しいＩＣカードなどの電子媒体を利用した認証システムが普及してきている。また、ネットワークを介した各種サービスにおいても、課金の対象となるサービス利用者とサービス提供者との間で互いに正当性を確認する相互認証は必須となる。人間が介在せずに、エンティティ間で認証を行うときには、セキュリティ強度の観点から暗号手法を利用した相互認証方式を用いることが主流となっている。なお、本出願において、「エンティティ」とは、情報のやりとりを行う主体的な存在であり、エンティティには、例えば、ＲＦＩＤ（Ｒａｄｉｏ  Ｆｒｅｑｕｅｎｃｙ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）タグ、ＩＣカード、ユビキタスデバイス、携帯情報通信端末、情報家電等のような種々の情報端末が含まれる。
【０００３】
チャレンジ／レスポンスによる相手認証方式は、現在まで一般に使われてきたユーザーＩＤとパスワードによる認証よりも、安全で強力な認証ができ、ＩＳＯ／ＩＥＣ９７９８における「ｅｎｔｉｔｙ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ（エンティティ認証）」としても国際標準化されている。チャレンジ／レスポンスによる相手認証は、秘密鍵暗号に基づく方式、公開鍵暗号／ディジタル署名を利用した方式等がある。３パス相互認証方式は、チャレンジ／レスポンスによる相手認証を双方向に行う４パス認証ではなく、２つのエンティティの内の一方のエンティティが、自身のチャレンジと、他方のエンティティのチャレンジに対するレスポンスとを組み合わせることで、１つのパスを削減した方式である。
【０００４】
図１１は、３パス相互認証方式の基本的な概念図である。図１１においては、説明を簡素化するために、２つのエンティティＡ，Ｂ間でやりとりする必要最低限の情報のみを描いているが、実際にやりとりされる情報には、端末のＩＤ情報や一時的なデータを付加することで、平文と暗号文の対応関係が外部にわからないようにする処理が施されるのが一般的である。
【０００５】
以下に、図１１に基づいて、従来の３パス相互認証を説明する（例えば、非特許文献１参照）。
［図１１のステップＳ５１］先ず、エンティティＡ（符号５１０）は、乱数ＲＡを生成し、乱数ＲＡをチャレンジ情報としてエンティティＢ（符号５２０）へ送信する。
［図１１のステップＳ５２］次に、エンティティＢは、エンティティＡより受信したチャレンジ情報からレスポンス情報Ｘ＝Ｆ（ＲＡ）を生成する。なお、Ｆ（・）は、暗号化関数又は署名生成関数を示す。
［図１１のステップＳ５３］次に、エンティティＢは、乱数ＲＢを生成し、乱数ＲＢをチャレンジ情報として、レスポンス情報Ｘと共に、エンティティＡへ送信する。
［図１１のステップＳ５４］次に、エンティティＡは、レスポンス情報Ｘを復号して乱数ＲＡが含まれていることを確認することによって、レスポンス情報Ｘの検証を行う。なお、Ｖ（・，・）は、チャレンジ／レスポンス検証関数を示す。
［図１１のステップＳ５５］次に、エンティティＡは、エンティティＢより受信したチャレンジ情報ＲＢからレスポンス情報Ｙ＝Ｆ（ＲＢ）を生成し、エンティティＢへ送信する。
［図１１のステップＳ５６］次に、エンティティＢは、レスポンス情報Ｙを復号して乱数ＲＢが含まれていることを確認することによって、レスポンス情報Ｙの検証を行う。
【０００６】
また、上記した基本的な相互認証方式を改良したものとして、特開平９−１０７３５０号公報（特許文献１）に開示されているように、認証を行う片方の機器に暗号変換装置のみを、もう片方の機器に暗号の逆変換装置のみを搭載して装置構成をコンパクトにしたものや、特開２００２−１１８５４８号公報（特許文献２）に開示されているように、上記コンパクトな装置構成でさらに装置間でやりとりする通信量を削減した方式が提案されている。しかし、これら文献は、相互認証を行う際に両装置が行う計算量に関して具体的に開示していない。
【０００７】
【非特許文献１】岡本龍明他著、「現代暗号」（産業図書）、ｐｐ．１５３−１５６
【特許文献１】特開平９−１０７３５０号公報（請求項１、図１）
【特許文献２】特開２００２−１１８５４８号公報（段落００８５、図１）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
図１１に示される３パス相互認証においては、エンティティＡが行うステップＳ５１，Ｓ５４，Ｓ５５の処理のそれぞれは、エンティティＢが行うステップＳ５３，Ｓ５６，Ｓ５２の処理のそれぞれと同様であり、その結果、相互認証に要するエンティティＡの計算量とエンティティＢの計算量が同じ値になる。
【０００９】
しかしながら、例えば、ＩＣカード（サービス利用者側の情報処理能力の低いエンティティ）とセンタ（サービス提供者側の情報処理能力の高いエンティティ）間の認証のように、処理能力の異なる２つのエンティティが相互認証を行う場合には、処理能力の低いエンティティに計算量の少ない処理を行わせ、処理能力の高いエンティティに計算量の多い処理を行わせることによって相互認証を実現させることが、処理効率の点において好ましい。
【００１０】
また、例えば、外部の電源ラインから電源供給を受けているエンティティと、バッテリー駆動であって電池容量の点から使用時間に制約があるエンティティとが相互認証を行う場合には、バッテリー駆動のエンティティに計算量の少ない処理を行わせ、電源ラインから電源供給を受けているエンティティに計算量の多い処理を行わせることが、バッテリー駆動のエンティティにおける電池容量の低下を抑制できるという点において好ましい。
【００１１】
そこで、本発明は、上記した従来技術の課題を解決するためになされたものであり、その目的は、相互認証を行う２つのエンティティの内の一方のエンティティが他方のエンティティよりも計算量の少ない処理で相互認証を実現できる相互認証方法、この方法を実施できる相互認証装置及び相互認証システムを提供することにある。
【課題を解決するための手段】
【００１２】
本発明の相互認証方法は、第１のエンティティと第２のエンティティの間で情報をやりとりして互いに相手の正当性を検証するステップを有し、前記第１のエンティティによる検証のための処理の計算量及び前記第２のエンティティによる検証相互認証のための処理の計算量のいずれか一方が他方よりも少ないことを特徴とするものである。
【００１３】
また、本発明の相互認証装置は、相手エンティティとの間で相互認証を実行する装置であって、自身のチャレンジ情報を生成して送信する手段と、相手エンティティのレスポンス情報を受信して検証する手段と、相手エンティティのチャレンジ情報を受信して相手エンティティに対する自身のレスポンス情報を生成して送信する手段とを有し、相互認証において自身が処理した計算量が、相手エンティティが処理した計算量と異なることを特徴とするものである。
【発明の効果】
【００１４】
本発明によれば、２つのエンティティの内の一方のエンティティが他方のエンティティよりも計算量の少ない処理で相互認証を実現できる。このため、例えば、処理能力の低いエンティティに計算量の少ない処理を、処理能力の高いエンティティに計算量の多い処理を行わせることによって、相互認証における処理効率の向上を図ることができる。
【発明を実施するための最良の形態】
【００１５】
本発明の実施形態においては、暗号化における計算量と復号における計算量との違い、署名生成における計算量と署名検証における計算量との違い等を利用して、２つのエンティティの内の一方のエンティティが計算量の少ない処理で、他方のエンティティが計算量の多い処理で、相互認証を実現できる３パス相互認証プロトコルを説明する。また、本発明の実施形態においては、相互認証を行う２つのエンティティの処理能力に差がある場合を例として説明する。ただし、本発明は、３パス相互認証に限定されるものではなく、４パス以上の相互認証にも適用可能である。また、本発明は、２つのエンティティの処理能力に差がある場合に限定されるものではなく、２つのエンティティのうちの一方の消費電力を抑制したい場合のように、相互認証を行う２つのエンティティの計算量に差を持たせることが好ましいすべての場合に適用可能である。
【００１６】
［１］第１の実施形態
［１−１］相互認証システムの構成
図１は、本発明の第１の実施形態に係る相互認証方法、相互認証装置（エンティティ）、及び相互認証システムを説明するための基本的な概念図である。第１の実施形態に係る相互認証方法、相互認証装置、及び相互認証システムは、共通鍵暗号方式に基づく３パス相互認証方式を採用している。図１に示されるように、第１の実施形態に係る相互認証システム（即ち、第１の実施形態に係る相互認証方法を実施することができる構成）は、エンティティＡ（符号１１０）と、エンティティＢ（符号１２０）と、エンティティＡ及びＢの間の通信を実現する手段（有線通信、無線通信、磁気的な読み取り、及び光学的な読み取りなどの情報交換可能な手段であればよい。）とから構成される。
【００１７】
第１の実施形態においては、２つのエンティティＡ，Ｂが同一の鍵情報を保持していることを確かめることにより、エンティティＡ，Ｂが互いに相手を認証する。第１の実施形態においては、暗号化処理を含む変換処理と復号処理を含む逆変換処理で、処理に要する計算量が異なる共通鍵暗号方式を用いる。変換処理と逆変換処理で処理に要する計算量が異なる方式としては、例えば、圧縮と暗号化、復号と解凍を組み合わせた方式がある。圧縮処理と解凍処理では、一般的に処理に要する計算量が異なることが多い。したがって、圧縮と暗号化を組み合わせた変換（以下、圧縮と暗号化を組み合わせた変換処理を行う場合には、この変換処理を「暗号化」と言う。）、復号と解凍を組み合わせた逆変換（以下、復号と解凍を組み合わせた逆変換処理を行う場合には、この逆変換処理を「復号」と言う。）との間で、計算量を異なる値にすることができる。また、この場合には、平文データを圧縮してから暗号化するので通信データ量が少なくなるという利点がある。
【００１８】
第１の実施形態に係る相互認証方法は、暗号化処理を含む変換処理における計算量と復号処理を含む逆変換処理における計算量の差、エンティティＡ及びＢの処理能力の差、いずれのエンティティから認証を開始するかによって、プロトコルが少し異なるが、第１の実施形態においては、
（暗号化に要する計算量）＞（復号に要する計算量）
（エンティティＡの処理能力）＞（エンティティＢの処理能力）
であって、エンティティＡがエンティティＢにチャレンジ情報を送信することにより認証を開始する場合を説明する。
【００１９】
［１−２］エンティティＡの構成
図２は、第１の実施形態における処理能力の大きい相互認証装置であるエンティティＡ（符号１１０）の構成を示すブロック図である。図２に示されるように、エンティティＡは、乱数生成部１１１と、暗号化部１１２と、検証部１１３と、送信部１１４と、受信部１１５とを備えている。
【００２０】
＜乱数生成部１１１＞
乱数生成部１１１は、擬似乱数情報を生成するものであり、生成した乱数情報ＲＡを暗号化部１１２と検証部１１３へ与える。
【００２１】
＜暗号化部１１２＞
暗号化部１１２は、乱数生成部１１１より与えられた乱数情報ＲＡを暗号化してチャレンジ情報Ｘ＝Ｅ（ＲＡ）を生成するものであり、生成したチャレンジ情報Ｘを送信部１１４へ与える。また、暗号化部１１２は、受信部１１５より与えられた相手エンティティのチャレンジ情報ＲＢを暗号化して、レスポンス情報Ｚ＝Ｅ（ＲＢ）を生成するものであり、生成したレスポンス情報Ｚを送信部１１４へ与える。また、暗号化部１１２は、暗号化に用いる鍵情報を秘密に保持する。暗号化部１１２で用いられる暗号化関数は、
（暗号化に要する計算量）＞（復号に要する計算量）
の関係を満たすものである。
【００２２】
＜検証部１１３＞
検証部１１３は、受信部１１５より与えられた相手エンティティのレスポンス情報Ｙ＝Ｄ（Ｘ）と、乱数生成部１１１より与えられた乱数情報ＲＡとを比較して、相手エンティティが同一の鍵情報を保持していることを確かめるものであり、成立すれば（即ち、相手エンティティが同一の鍵情報を保持していれば）相手エンティティを正しいと認証する。
【００２３】
＜送信部１１４＞
送信部１１４は、暗号化部１１２より与えられるチャレンジ情報Ｘとレスポンス情報Ｚを相手エンティティへ送信する。
【００２４】
＜受信部１１５＞
受信部１１５は、相手エンティティから受信したレスポンス情報Ｙを検証部１１３へ、チャレンジ情報ＲＢを暗号化部１１２へ与える。
【００２５】
［１−３］エンティティＢの構成
図３は、第１の実施形態における処理能力の小さい相互認証装置であるエンティティＢ（符号１２０）の構成を示すブロック図である。図３に示されるように、エンティティＢは、復号部１２１と、乱数生成部１２２と、検証部１２３と、送信部１２４と、受信部１２５とを備えている。
【００２６】
＜復号部１２１＞
復号部１２１は、受信部１２５より与えられた相手エンティティのチャレンジ情報Ｘ＝Ｅ（ＲＡ）を復号して、レスポンス情報Ｙ＝Ｄ（Ｘ）を生成するものであり、生成したレスポンス情報Ｙを送信部１２４へ与える。また、復号部１２１は、受信部１２５より与えられた相手エンティティのレスポンス情報Ｚ＝Ｅ（ＲＢ）を復号して、相手エンティティの検証情報Ｄ（Ｚ）を生成するものであり、生成した検証情報Ｄ（Ｚ）を検証部１２３へ与える。また、復号部１２１は、復号に用いる鍵情報を秘密に保持する。復号部１２１で用いられる復号関数は、
（暗号化に要する計算量）＞（復号に要する計算量）
の関係を満たすものである。
【００２７】
＜乱数生成部１２２＞
乱数生成部１２２は、擬似乱数情報を生成するものであり、生成した乱数情報ＲＢを検証部１２３と送信部１２４へ与える。
【００２８】
＜検証部１２３＞
検証部１２３は、復号部１２１より与えられた検証情報Ｄ（Ｚ）と、乱数生成部１２２より与えられた乱数情報ＲＢとを比較して、相手エンティティが同一の鍵情報を保持していることを確かめるものであり、成立すれば（即ち、相手エンティティが同一の鍵情報を保持していれば）相手エンティティを正しいと認証する。
【００２９】
＜送信部１２４＞
送信部１２４は、復号部１２１より与えられるレスポンス情報Ｙと乱数生成部１２２より与えられるチャレンジ情報ＲＢを相手エンティティへ送信する。
【００３０】
＜受信部１２５＞
受信部１２５は、相手エンティティから受信したチャレンジ情報Ｘとレスポンス情報Ｚを復号部１２１へ与える。
【００３１】
［１−４］相互認証方法（エンティティＡ及びＢの動作）
以下に、図１乃至図３に基づいて、第１の実施形態に係る相互認証方法を説明する。
［図１のステップＳ１１］先ず、エンティティＡは、乱数生成部１１１において乱数ＲＡを生成し、暗号化部１１２へ与える。
［図１のステップＳ１２］次に、エンティティＡは、暗号化部１１２において乱数ＲＡを暗号化したチャレンジ情報Ｘ＝Ｅ（ＲＡ）を生成し、生成されたチャレンジ情報Ｘを送信部１１４からエンティティＢへ送信する。なお、Ｅ（・）は、暗号化関数を示す。
［図１のステップＳ１３］次に、エンティティＢは、受信部１２５で受信したエンティティＡからのチャレンジ情報Ｘを復号部１２１において復号したレスポンス情報Ｙ＝Ｄ（Ｘ）を生成する。なお、Ｄ（・）は、復号関数を示す。
［図１のステップＳ１４］次に、エンティティＢは、乱数生成部１２２において乱数ＲＢをチャレンジ情報として生成し、レスポンス情報Ｙと共に、送信部１２４からエンティティＡへ送信する。
［図１のステップＳ１５］次に、エンティティＡは、検証部１１３において、受信部１１５により受信されたエンティティＢからのレスポンス情報Ｙが、ステップＳ１１において生成した乱数ＲＡと一致するか否かを検証する。一致する場合は、エンティティＡは、相手エンティティＢを正しいと認証し、プロトコルを続行する。
［図１のステップＳ１６］次に、エンティティＡは、エンティティＢより受信したチャレンジ情報ＲＢを暗号化部１１２において暗号化したレスポンス情報Ｚ＝Ｅ（ＲＢ）を生成し、生成されたレスポンス情報Ｚを、送信部１１４からエンティティＢへ送信する。
［図１のステップＳ１７］次に、エンティティＢは、エンティティＡより受信したレスポンス情報Ｚを復号部１２１において復号し、復号されたレスポンス情報Ｄ（Ｚ）がステップＳ１４において生成した乱数ＲＢと一致するか否かを検証部１２５で検証する。一致する場合は、エンティティＢは、相手エンティティＡを正しいと認証する。
【００３２】
［１−５］第１の実施形態の効果
以上に説明したように、第１の実施形態においては、処理能力の高いエンティティＡは計算量の多い暗号化処理のみを、処理能力の低いエンティティＢは計算量の少ない復号処理のみを行うことで相互認証を実現している。このため、例えば、ＩＣカード（サービス利用者側の情報処理能力の低いエンティティＢ）とセンタ（サービス提供者側の情報処理能力の高いエンティティＡ）間の認証のように、処理能力の異なる２つのエンティティＡとＢが相互認証を行う場合に、処理能力の低いエンティティＢに計算量の少ない処理を行わせ、処理能力の高いエンティティＡに計算量の多い処理を行わせることによって相互認証を実現させることができ、認証処理に要する時間の短縮や、処理能力の低いエンティティＢにおける消費電力の低減などの効果が期待できる。
【００３３】
［２］第２の実施形態
［２−１］相互認証システムの構成
図４は、本発明の第２の実施形態に係る相互認証方法、相互認証装置（エンティティ）、及び相互認証システムを説明するための基本的な概念図である。図４に示されるように、第２の実施形態に係る相互認証システム（即ち、第２の実施形態に係る相互認証方法を実施することができる構成）は、エンティティＡ（符号２１０）と、エンティティＢ（符号２２０）と、エンティティＡ及びＢの間の通信を実現する手段（有線通信、無線通信、磁気的な読み取り、及び光学的な読み取りなどの情報交換可能な手段であればよい。）とから構成される。
【００３４】
第２の実施形態に係る相互認証方法、相互認証装置、及び相互認証システムにおいては、エンティティの公開鍵・秘密鍵の値をエンティティの処理能力に応じて予め設定する。第２の実施形態においては、公開鍵暗号方式及び／又はディジタル署名に基づく３パス相互認証方式を用いる。第２の実施形態においては、エンティティＡ及びＢのそれぞれが、自身の公開鍵に対応する正しい秘密鍵を保持していることを証明することにより、認証を行う。ＲＳＡ（Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  Ａｄｌｅｍａｎ）暗号では、公開鍵として小さい値を設定し、公開鍵を用いた処理（暗号化処理及び署名検証処理）を高速に実行できるのが一般的である。それに伴い秘密鍵の値は大きくなるので、
（暗号化に要する計算量）＜（復号に要する計算量）
（署名生成に要する計算量）＞（署名検証に要する計算量）
という関係が成り立つ。
【００３５】
逆に、秘密鍵の値を小さくした場合は、公開鍵の値が大きくなるので、上記とは逆の関係、即ち、
（暗号化に要する計算量）＞（復号に要する計算量）
（署名生成に要する計算量）＜（署名検証に要する計算量）
が成り立つ。ただし、秘密鍵の値を小さくすることで、秘密鍵が特定しやすくなるような状況は存在してはならず、セキュリティレベルが低下しない範囲で秘密鍵の値を選択する必要がある。
【００３６】
第２の実施形態における相互認証方法は、公開鍵暗号に基づく場合と、ディジタル署名に基づく場合と、公開鍵暗号及びディジタル署名の両方を用いる場合のいずれによっても実現できる。第２の実施形態においては、
（エンティティＡの処理能力）＞（エンティティＢの処理能力）
であり、エンティティＡがエンティティＢにチャレンジを送信することにより認証を開始する場合で、公開鍵暗号方式に基づいて相互認証を行う場合の一例を説明する。第２の実施形態においては、事前にこれから相互認証を行う相手エンティティの正しい公開鍵を、なんらかの方法、例えば、信頼できる機関による公開鍵証明書によって得ていることを前提とする。
【００３７】
［２−２］エンティティＡ，Ｂの構成
図５は、第２の実施形態におけるエンティティＡ（符号２１０），Ｂ（符号２２０）の構成を示すブロック図である。図５に示されるように、エンティティＡは、乱数生成部２１１と、公開鍵情報管理部２１２と、暗号化・復号部２１３と、検証部２１４と、送信部２１５と、受信部２１６とを備えている。また、図５に示されるように、エンティティＢは、乱数生成部２２１と、公開鍵情報管理部２２２と、暗号化・復号部２２３と、検証部２２４と、送信部２２５と、受信部２２６とを備えている。
【００３８】
＜乱数生成部２１１，２２１＞
乱数生成部２１１（又は２２１）は、擬似乱数情報ＲＡ（又はＲＢ）を生成するものであり、チャレンジ情報が乱数情報の平文情報である場合には、生成した乱数情報ＲＡ（又はＲＢ）をチャレンジ情報として送信部２１５（又は２２５）と検証部２１６（又は２２６）へ与える。また、チャレンジ情報が乱数情報の暗号化情報である場合には、生成した乱数情報を暗号化部２１３（又は２２３）と検証部２１４（又は２２４）へ与える。
【００３９】
＜公開鍵情報管理部２１２，２２２＞
公開鍵情報管理部２１２（又は２２２）は、エンティティＡ（又はＢ）の正しい公開鍵情報を管理しているものであり、管理している公開鍵を暗号化・復号部２１３（又は２２３）へ与える。処理能力の高いエンティティＡの公開鍵情報ＰＫＡは、小さい値に設定され、処理能力の低いエンティティＢの公開鍵情報ＰＫＢは比較的大きな値（例えば、ＰＫＡより大きな値）に設定されることが好ましい。
【００４０】
＜暗号化・復号部２１３，２２３＞
暗号化・復号部２１３（又は２２３）は、受信部２１６（又は２２６）より与えられる相手エンティティのレスポンス情報Ｘ＝ＥＳＫＢ（ＲＡ）（又はＹ＝ＥＳＫＡ（ＲＢ））を、公開鍵情報管理部２１２（又は２２２）より与えられた相手エンティティの公開鍵情報ＰＫＡ（又はＰＫＢ）で復号するものであり、生成した相手エンティティの検証情報ＤＰＫＢ（Ｘ）（又はＤＰＫＡ（Ｙ））を検証部２１４（又は２２４）へ与える。暗号化・復号部２１３（又は２２３）は、受信部２１６（又は２２６）より与えられる相手エンティティのチャレンジ情報ＲＢ（又はＲＡ）を、自身の秘密鍵ＳＫＡ（又はＳＫＢ）により暗号化若しくは復号してレスポンス情報Ｙ＝ＥＳＫＡ（ＲＢ）（又はＸ＝ＥＳＫＢ（ＲＡ））を生成するものであり、生成したレスポンス情報を送信部２１５（又は２２５）へ与える。暗号化・復号部２１３（又は２２３）は、自身の公開鍵ＰＫＡ（又はＰＫＢ）に対応する秘密鍵ＳＫＡ（又はＳＫＢ）を秘密に保持する。処理能力の高いエンティティＡの秘密鍵情報ＳＫＡは、大きい値に設定されている。また、処理能力の低いエンティティＢの秘密鍵情報ＳＫＢは比較的小さな値（例えば、ＳＫＡより小さい値）に設定されていることが好ましい。ここでいう「比較的小さい」とは、秘密鍵情報の値を小さくすることでセキュリテイレベルが下がらない範囲で小さいという意味である。また、用いる公開鍵暗号は、ＲＳＡ暗号のように、暗号化処理と復号処理でアルゴリズムが同一のものであってもよい。また、第２の実施形態に係る相互認証方法を、公開鍵暗号方式ではなく、ディジタル署名方式により実現する場合には、暗号化・復号部２１３，２２３を、ディジタル署名の生成及び検証を行う署名生成・検証部にすればよい。
【００４１】
＜検証部２１４，２２４＞
検証部２１４（又は２２４）は、暗号化・復号部２１３（又は２２３）より与えられた検証情報ＤＰＫＢ（Ｘ）（又はＤＰＫＡ（Ｙ））と、乱数生成部２１１（又は２２１）より与えられた乱数情報ＲＡ（又はＲＢ）とを比較して、相手エンティティが公開鍵に対応する秘密鍵を保持していることを確かめるものであり、成立すれば（即ち、ＤＰＫＢ（Ｘ）＝ＲＡ（又はＤＰＫＡ（Ｙ）＝ＲＢ）であれば）、相手エンティティを正しいと認証する。また、レスポンス情報が暗号化されていない場合には、検証部２１４（又は２２４）は、受信部２１６（又は２２６）より与えられた相手エンティティのレスポンス情報Ｘ（又はＹ）と、乱数生成部２１１（又は２２１）より与えられた乱数情報とを比較して、相手エンティティが公開鍵に対応する秘密鍵を保持していることを確かめるものであり、成立すれば相手エンティティを正しいと認証する。
【００４２】
＜送信部２１５，２２５＞
送信部２１５（又は２２５）は、暗号化・復号部２１３（又は２２３）より与えられるチャレンジ情報若しくはレスポンス情報と、乱数生成部２１１（又は２２１）より与えられるチャレンジ情報を相手エンティティへ送信する。
【００４３】
＜受信部２１６，２２６＞
受信部２１６（又は２２６）は、相手エンティティから受信したチャレンジ情報とレスポンス情報を暗号化・復号部２１３（又は２２３）へ与える。また、受信部２１６（又は２２６）は、相手エンティティから受信したレスポンス情報を検証部２１４（又は２２４）へ与える。
【００４４】
［２−３］相互認証方法（エンティティＡ及びＢの動作）
以下に、図４及び図５に基づいて、第２の実施形態に係る相互認証方法を説明する。
［図４のステップＳ２１］先ず、エンティティＡは、乱数生成部２１１において乱数ＲＡをチャレンジ情報として生成し、送信部２１５からエンティティＢへ送信する。
［図４のステップＳ２２］次に、エンティティＢは、受信部２２６により受信したエンティティＡからのチャレンジ情報ＲＡを、暗号化・復号部２２３において、予め値が比較的小さく設定されている自身の秘密鍵ＳＫＢで暗号化し、レスポンス情報Ｘ＝ＥＳＫＢ（ＲＡ）を生成する。なお、ＥＫ（・）は、鍵Ｋを用いた暗号化関数を示す。
［図４のステップＳ２３］次に、エンティティＢは、乱数生成部２２１において乱数ＲＢをチャレンジ情報として生成し、レスポンス情報Ｘと共に、送信部２２５からエンティティＡへ送信する。
［図４のステップＳ２４］次に、エンティティＡは、受信部２１６により受信したエンティティＢからのレスポンス情報Ｘを、暗号化・復号部２１３においてエンティティＢの公開鍵ＰＫＢで復号し、復号した情報ＤＰＫＢ（Ｘ）が、ステップＳ２１で生成した乱数ＲＡと一致するか否かを検証部２１４で検証する。一致する場合は、相手エンティティを正しいと認証し、プロトコルを続行する。なお、ＤＫ（・）は、鍵Ｋを用いた復号関数を示す。
［図４のステップＳ２５］次に、エンティティＡは、エンティティＢより受信したチャレンジ情報ＲＢを、暗号化・復号部２１３において、自身の秘密鍵ＳＫＢで暗号化したレスポンス情報Ｙ＝ＥＳＫＡ（ＲＢ）を生成し、送信部２１５によりエンティティＢへ送信する。
［図４のステップＳ２６］次に、エンティティＢは、エンティティＡより受信したレスポンス情報Ｙを、暗号化・復号部２２３において、予め値が小さく設定されているエンティティＡの公開鍵ＰＫＡで復号し、復号した情報ＤＰＫＡ（Ｙ）が、ステップＳ２３において生成した乱数ＲＢと一致する否かを検証部２２４で検証する。一致する場合は、相手エンティティを正しいと認証する。
【００４５】
［２−４］第２の実施形態の効果
以上に説明したように、第２の実施形態においては、処理能力の高いエンティティＡの公開鍵の値を小さく設定し、また、処理能力の低いエンティティＢの秘密鍵の値をセキュリテイレベルが低下しない範囲で小さく設定することで、処理能力の低いエンティティＢが相互認証を行う上で要する計算量を少なくしている。このため、例えば、ＩＣカード（サービス利用者側の情報処理能力の低いエンティティＢ）とセンタ（サービス提供者側の情報処理能力の高いエンティティＡ）間の認証のように、処理能力の異なる２つのエンティティＡとＢが相互認証を行う場合に、処理能力の低いエンティティＢに計算量の少ない処理を行わせ、処理能力の高いエンティティＡに計算量の多い処理を行わせることによって相互認証を実現させることができ、認証処理に要する時間の短縮や、処理能力の低いエンティティＢにおける消費電力の低減などの効果が期待できる。
【００４６】
［３］第３の実施形態
［３−１］相互認証システムの構成
図６は、本発明の第３の実施形態に係る相互認証方法、相互認証装置（エンティティ）、及び相互認証システムを説明するための基本的な概念図である。図６に示されるように、第３の実施形態に係る相互認証システム（即ち、第３の実施形態に係る相互認証方法を実施することができる構成）は、エンティティＡ（符号３１０）と、エンティティＢ（符号３２０）と、エンティティＡ及びＢの間の通信を実現する手段（有線通信、無線通信、磁気的な読み取り、及び光学的な読み取りなどの情報交換可能な手段であればよい。）とから構成される。
【００４７】
第３の実施形態に係る相互認証方法、相互認証装置、及び相互認証システムにおいては、エンティティの公開鍵・秘密鍵の値をエンティティの処理能力に応じて予め設定する。第３の実施形態においては、第２の実施形態と同様に、公開鍵暗号方式及び／又はディジタル署名に基づく３パス相互認証方式を用いる。第３の実施形態における３パス相互認証方式は、ＲＳＡ暗号のように一般的に公開鍵の値を小さく設定して利用し、
（暗号化に要する計算量）＜（復号に要する計算量）、
（署名生成に要する計算量）＞（署名検証に要する計算量）
の関係が成り立つものと、楕円暗号のようにアルゴリズム的な問題から、
（暗号化に要する計算量）＞（復号に要する計算量）
（署名生成に要する計算量）＜（署名検証に要する計算量）
の関係が一般的に成り立つ、計算量が相反する２つの方式を組み合わせることを特徴とする。第３の実施形態における相互認証は、公開鍵暗号に基づく場合と、ディジタル署名に基づく場合と、公開鍵暗号及びディジタル署名の両方を用いる場合のいずれによっても実現できる。
【００４８】
第３の実施形態においては、
（エンティティＡの処理能力）＞（エンティティＢの処理能力）
であり、エンティティＡがエンティティＢにチャレンジを送信することにより認証を開始する場合であって、ディジタル署名に基づいて相互認証を行う場合を説明する。第３の実施形態においては、事前にこれから相互認証を行う相手エンティティの正しい公開鍵をなんらかの方法、例えば、信頼できる機関による公開鍵証明書によって得ていることを前提とする。
【００４９】
［３−２］エンティティＡ，Ｂの構成
図７は、第３の実施形態におけるエンティティＡ（符号３１０），Ｂ（符号３２０）の構成を示すブロック図である。図７に示されるように、エンティティＡは、乱数生成部３１１と、公開鍵情報管理部３１２と、署名生成部３１３と、署名検証部３１４と、送信部３１５と、受信部３１６とを備えている。また、図７に示されるように、エンティティＢは、乱数生成部３２１と、公開鍵情報管理部３２２と、署名生成部３２３と、署名検証部３２４と、送信部３２５と、受信部３２６とを備えている。
【００５０】
＜乱数生成部３１１，３２１＞
乱数生成部３１１（又は３２１）は、擬似乱数情報ＲＡ（又はＲＢ）を生成するものであり、生成した乱数情報ＲＡ（又はＲＢ）を送信部３１５（又は３２５）と署名検証部３１３（又は３２３）へ与える。
【００５１】
＜公開鍵情報管理部３１２，３２２＞
公開鍵情報管理部３１２（又は３２２）は、エンティティの正しい公開鍵情報を管理しているものであり、管理している公開鍵を署名検証部３１３（又は３２３）へ与える。例えば、処理能力の高いエンティティＡは、処理能力の低いエンティティＢの楕円暗号の公開鍵ＰＫＥＣＤＳＡを管理しており、エンティティＢは、エンティティＡのＲＳＡ暗号の公開鍵ＰＫＲＳＡを管理している。一つのエンティティＡ又はＢが、複数の公開鍵暗号方式による複数の公開鍵情報を保持していてもよい。
【００５２】
＜署名生成部３１３，３２３＞
署名生成部３１３（又は３２３）は、受信部３１６（又は３２６）より与えられる相手エンティティのチャレンジ情報ＲＢ（又はＲＡ）に対して、自身の秘密鍵を用いた署名をレスポンス情報Ｙ＝ｓｉｇ（ＲＢ）（又はＸ＝ｓｉｇ（ＲＡ））として生成するものであり、生成したレスポンス情報を送信部３１５（又は３２５）へ与える。処理能力の高いエンティティは、署名検証処理に要する計算量が署名生成処理に要する計算量より少ない署名生成アルゴリズムにより署名を生成し、処理能力の低いエンティティは、署名生成処理に要する計算量が署名検証処理に要する計算量より少ない署名生成アルゴリズムにより署名を生成する。署名検証処理に要する計算量が少ない署名生成アルゴリズムとしては、例えば、ＲＳＡ署名を用い、署名生成処理に要する計算量が少ない署名生成アルゴリズムとしては、例えば、ＥＣＤＳＡ（ＥＩｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ）署名等を用いる。なお、ＲＳＡ署名は、ＲＳＡ暗号方式を用いたディジタル署名であり、ＥＣＤＳＡ署名は、楕円曲線暗号を用いたディジタル署名である。また、一つのエンティティＡ又はＢが、署名生成関数ｓｉｇ（・）を、複数保持していてもよい。さらにまた、署名生成部３１３（又は３２３）は、自身の公開鍵ＰＫＥＣＤＳＡ（又はＰＫＲＳＡ）に対応する秘密鍵ＳＫＡ（又はＳＫＢ）を秘密に管理する。管理する秘密鍵は、複数の公開鍵暗号方式による複数の公開鍵に対応して複数であってもよい。
【００５３】
＜署名検証部３１４，３２４＞
署名検証部３１４（又は３２４）は、受信部３１６（又は３２６）より与えられる相手エンティティのレスポンス情報Ｘ（又はＹ）と、乱数生成部３１１（又は３２１）より与えられた乱数情報ＲＡ（又はＲＢ）と、公開鍵情報管理部３１２（又は３２２）より与えられた相手エンティティの公開鍵情報ＰＫＥＣＤＳＡ（又はＰＫＲＳＡ）より、相手エンティティが生成した署名が相手エンティティの公開鍵に対応する正しい秘密鍵ＳＫＡ（又はＳＫＢ）で生成されたかどうかを確かめるものであり、成立すれば相手エンティティを正しいと認証する。署名検証部３１４（又は３２４）は、署名生成に用いられたアルゴリズムに対する署名検証アルゴリズムを実行する。
【００５４】
＜送信部３１５，３２５＞
送信部３１５（又は３２５）は、署名生成部３１３（又は３２３）より与えられるレスポンス情報Ｙ（又はＸ）と、乱数生成部３１１（又は３２１）より与えられるチャレンジ情報ＲＡ（又はＲＢ）を相手エンティティへ送信する。
【００５５】
＜受信部３１６，３２６＞
受信部３１６（又は３２６）は、相手エンティティから受信したチャレンジ情報ＲＢ（又はＲＡ）を署名生成部３１３（又は３２３）へ、相手エンティティから受信したレスポンス情報Ｘ（又はＹ）を署名検証部３１４（又は３２４）へ与える。
【００５６】
［３−３］相互認証方法（エンティティＡ及びＢの動作）
以下に、図６及び図７に基づいて、第３の実施形態に係る相互認証方法を説明する。
［図６のステップＳ３１］先ず、エンティティＡは、乱数生成部３１１において乱数ＲＡをチャレンジ情報として生成し、送信部３１５からエンティティＢへ送信する。
［図６のステップＳ３２］次に、エンティティＢは、署名生成部３２４において、受信部３２６で受信されたエンティティＡからのチャレンジ情報ＲＡに対して、署名生成処理に要する計算量が少ない署名生成アルゴリズムと、自身の秘密鍵ＳＫＢを用いて署名を計算し、レスポンス情報Ｘ＝ｓｉｇ（ＲＡ）を生成する。なお、ｓｉｇ（・）は、署名生成関数を示す。
［図６のステップＳ３３］次に、エンティティＢは、乱数生成部３２１において、乱数ＲＢをチャレンジ情報として生成し、レスポンス情報Ｘと共に、送信部３２５からエンティティＡへ送信する。
［図６のステップＳ３４］次に、エンティティＡは、署名検証部３１４において、エンティティＢより受信したレスポンス情報Ｘと、エンティティＢの公開鍵ＰＫＥＣＤＳＡと、ステップＳ３１で生成した乱数ＲＡより、レスポンス情報ＸがエンティティＢの生成した署名Ｘであるかどうかを検証する。一致する場合は、エンティティＡは、相手エンティティを正しいと認証し、プロトコルを続行する。なお、Ｖ（・，・）は、署名検証関数を示す。
［図６のステップＳ３５］次に、エンティティＡは、署名生成部３１３において、エンティティＢより受信したチャレンジ情報ＲＢに対して、署名検証処理に要する計算量が少ない署名生成アルゴリズムと、自身の秘密鍵ＳＫＢを用いて署名を計算し、レスポンス情報Ｙ＝ｓｉｇ（ＲＢ）を生成する。エンティティＡは、生成したレスポンス情報Ｙを、エンティティＢへ送信する。
［図６のステップＳ３６］次に、エンティティＢは、署名検証部３２４において、エンティティＡより受信したレスポンス情報Ｙと、エンティティＡの公開鍵ＰＫＲＳＡと、ステップＳ３３で生成した乱数ＲＢより、レスポンス情報ＹがエンティティＡの生成した署名であるかどうかを検証する。一致する場合は、エンティティＢは、相手エンティティを正しいと認証する。
【００５７】
［３−４］第３の実施形態の効果
以上に説明したように、第３の実施形態においては、署名生成処理に要する計算量と署名検証処理に要する計算量との大小が相反する２つの公開鍵暗号方式を組み合わせている。処理能力の高いエンティティＡが署名検証処理に要する計算量が少ない署名生成アルゴリズムを用いて署名生成を行い、処理能力の低いエンティティＢが署名生成処理に要する計算量が少ない署名生成アルゴリズムを用いて署名生成を行うことで、処理能力の低いエンティティが相互認証を行う上で要する計算量を少なくできる。図６の動作において、処理能力の低いエンティティＢが相互認証において行う処理は、例えば、ＥＣＤＳＡ署名方式のような、署名生成処理に要する計算量が小さい署名生成アルゴリズムと、例えばＲＳＡ署名のような、署名検証処理に要する計算量が小さい署名検証アルゴリズムであり、共に計算量が小さい処理となるので、処理能力の低いエンティティＢが相互認証に要する計算量を少なくすることができる。このため、例えば、ＩＣカード（サービス利用者側の情報処理能力の低いエンティティＢ）とセンタ（サービス提供者側の情報処理能力の高いエンティティＡ）間の認証のように、処理能力の異なる２つのエンティティＡとＢが相互認証を行う場合に、処理能力の低いエンティティＢに計算量の少ない処理を行わせ、処理能力の高いエンティティＡに計算量の多い処理を行わせることによって相互認証を実現させることができ、認証処理に要する時間の短縮や、処理能力の低いエンティティＢにおける消費電力の低減などの効果が期待できる。
【００５８】
［４］第４の実施形態
［４−１］概要
本発明の第４の実施形態に係る相互認証方法、相互認証装置（エンティティ）、及び相互認証システムは、上記第１乃至第３の実施形態に係る相互認証方法、相互認証装置（エンティティ）、及び相互認証システムを改良したものである。第４の実施形態に係る相互認証方法、相互認証装置、及び相互認証システムは、２つのエンティティ間で相互認証を行うことにより、２つのエンティティのそれぞれが共通の秘密情報を保持することができる点において、上記第１乃至第３の実施形態に係る相互認証方法、相互認証装置（エンティティ）、及び相互認証システムと相違する。なお、第４の実施形態に係る相互認証方法、相互認証装置、及び相互認証システムの第２及び第３の実施形態に対する適用は、第２及び第３の実施形態が公開鍵暗号方式に基づく場合に実現可能である。
【００５９】
［４−２］相互認証システムの構成
以下に、第４の実施形態に係る相互認証方法、相互認証装置、及び相互認証システムを第１の実施形態に対して適用した場合を説明する。図８は、本発明の第４の実施形態に係る相互認証方法、相互認証装置（エンティティ）、及び相互認証システムを説明するための基本的な概念図である。図８に示されるように、第４の実施形態に係る相互認証システム（即ち、第４の実施形態に係る相互認証方法を実施することができる構成）は、エンティティＡ（符号４１０）と、エンティティＢ（符号４２０）と、エンティティＡ及びＢの間の通信を実現する手段（有線通信、無線通信、磁気的な読み取り、及び光学的な読み取りなどの情報交換可能な手段であればよい。）とから構成される。
【００６０】
第４の実施形態に係る相互認証方法、相互認証装置、及び相互認証システムにおいては、エンティティの公開鍵・秘密鍵の値をエンティティの処理能力に応じて予め設定する。第４の実施形態においては、第１の実施形態と同様に、共通鍵暗号方式に基づく相互認証方式で、
（暗号化の計算量）＞（復号の計算量）
（エンティティＡの処理能力）＞（エンティティＢの処理能力）
エンティティＡがエンティティＢにチャレンジを送信することにより認証を開始する場合を説明する。
【００６１】
［４−３］エンティティＡの構成
図９は、第４の実施形態における相互認証装置であるエンティティＡ（符号４１０）の構成を示すブロック図である。図９に示されるように、エンティティＡは、秘密情報管理部４１１と、乱数生成部４１２と、暗号化部４１３と、検証部４１４と、送信部４１５と、受信部４１６とを備えている。
【００６２】
＜秘密情報管理部４１１＞
秘密情報管理部４１１は、乱数生成部４１２より与えられた乱数情報を管理し、管理している乱数情報を暗号化部４１３へ与える。秘密情報管理部４１１は、検証部４１４より認証成功メッセージを与えられ、保持する乱数情報Ｑを相手エンティティとの間で秘密に共有する秘密情報ＫＥＹＡＢとして管理する。
【００６３】
＜乱数生成部４１２＞
乱数生成部４１２は、擬似乱数情報を生成するものであり、生成した乱数情報を暗号化部４１３、検証部４１４、及び秘密情報管理部４１１へ与える。
【００６４】
＜暗号化部４１３＞
暗号化部４１３は、乱数生成部４１２より与えられた乱数情報を暗号化してチャレンジ情報Ｘ＝Ｅ（ＲＡ||Ｑ）を生成するものであり、生成したチャレンジ情報Ｘを送信部４１５へ与える。また、暗号化部４１３は、受信部４１６より与えられた相手エンティティのチャレンジ情報ＲＢを暗号化して、レスポンス情報Ｚ＝Ｅ（ＲＢ）を生成するものであり、生成したレスポンス情報Ｚを送信部４１５へ与える。また、暗号化部４１３は、暗号化に用いる鍵情報を秘密に保持する。暗号化部４１３で用いられる暗号化関数は、
（暗号化に要する計算量）＞（復号に要する計算量）
の関係を満たすものを用いる。
【００６５】
＜検証部４１４＞
検証部４１４は、受信部４１６より与えられた相手エンティティのレスポンス情報Ｙ＝Ｄ（Ｘ）と、乱数生成部４１２より与えられた乱数情報とを比較して、相手エンティティが同一の鍵情報を保持していることを確かめるものであり、成立すれば（即ち、相手エンティティが同一の鍵情報を保持していれば）相手エンティティを正しいと認証する。
検証部４１４は、相手エンティティを正しいと認証することで、認証成功メッセージを秘密情報管理部４１１へ与える。
【００６６】
＜送信部４１５＞
送信部４１５は、暗号化部４１３より与えられるチャレンジ情報Ｘとレスポンス情報Ｚを相手エンティティへ送信する。
【００６７】
＜受信部４１６＞
受信部４１６は、相手エンティティから受信したレスポンス情報Ｙを検証部４１４へ、チャレンジ情報ＲＢを暗号化部４１３へ与える。
【００６８】
［４−４］エンティティＢの構成
図１０は、第４の実施形態における相互認証装置であるエンティティＢ（符号４２０）の構成を示すブロック図である。図１０に示されるように、エンティティＢは、秘密情報管理部４２１と、復号部４２２と、乱数生成部４２３と、検証部４２４と、送信部４２５と、受信部４２６とを備えている。
【００６９】
＜秘密情報管理部４２１＞
秘密情報管理部４２１は、復号部４２２より与えられた乱数情報を保持する。秘密情報管理部４２１は、検証部４２４より認証成功メッセージを与えられ、保持する乱数情報Ｐを相手エンティティとの間で秘密に共有する秘密情報ＫＥＹＡＢとして管理する。
【００７０】
＜復号部４２２＞
復号部４２２は、受信部４２６より与えられた相手エンティティのチャレンジ情報Ｘを復号して、レスポンス情報Ｙを生成するものであり、生成したレスポンス情報Ｙを送信部４２５へ与える。また、復号部４２２は、受信部４２６より与えられた相手エンティティのレスポンス情報Ｚを復号して、相手エンティティの検証情報Ｄ（Ｚ）を生成するものであり、生成した検証情報Ｄ（Ｚ）を検証部４２４へ与える。また、復号部４２２は、復号に用いる鍵情報を秘密に保持する。復号部１２１で用いられる復号関数は
（暗号化に要する計算量）＞（復号に要する計算量）
の関係を満たすものである。
復号部４２２は、相手エンティティのチャレンジ情報を復号することによって、２つの乱数情報Ｙ，Ｐを得るものであり、一方の乱数情報Ｙをレスポンス情報として送信部４２５へ、もう一方の乱数情報Ｐを秘密情報管理部４２１へ与える。復号部４２２は、２つの乱数情報Ｙ，Ｐは、例えば、相手エンティティのチャレンジ情報を復号したものを、左半分と右半分に分割することで得る。あるいは、左端より数ビットを第１の乱数情報、残り右側を第２の乱数情報というように、指定されていてもよい。
【００７１】
＜乱数生成部４２３＞
乱数生成部４２３は、擬似乱数情報を生成するものであり、生成した乱数情報ＲＢを検証部４２４と送信部４２５へ与える。
【００７２】
＜検証部４２４＞
検証部４２４は、復号部４２２より与えられた検証情報Ｄ（Ｚ）と、乱数生成部４２３より与えられた乱数情報ＲＢとを比較して、相手エンティティが同一の鍵情報を保持していることを確かめるものであり、成立すれば（即ち、相手エンティティが同一の鍵情報を保持していれば）相手エンティティを正しいと認証する。さらに、相手エンティティを正しいと認証することで、認証成功メッセージを秘密情報管理部４２１へ与える。
【００７３】
＜送信部４２５＞
送信部４２５は、復号部４２２より与えられるレスポンス情報Ｙと乱数生成部１２２より与えられるチャレンジ情報ＲＢを相手エンティティへ送信する。
【００７４】
＜受信部４２６＞
受信部４２６は、相手エンティティから受信したチャレンジ情報Ｘとレスポンス情報Ｚを復号部４２２へ与える。
【００７５】
［４−５］第４の実施形態の相互認証方法（エンティティＡ及びＢの動作）
以下に、図８乃至図１０に基づいて、第４の実施形態に係る相互認証方法を説明する。
［図８のステップＳ４１］先ず、エンティティＡは、乱数生成部４１２において、乱数ＲＡとＱを生成する。エンティティＡは、乱数Ｑを、秘密情報管理部４１１で保持する。
［図８のステップＳ４２］次に、エンティティＡは、乱数ＲＡとＱを連結させたビット配列‘ＲＡ||Ｑ’を暗号化部４１３により暗号化したチャレンジ情報Ｘ＝Ｅ（ＲＡ||Ｑ）を生成し、送信部４１５によりエンティティＢへ送信する。なお、記号‘||’は、ビット列の連結を示し、ビット列ｘとビット列ｙの連結を‘ｘ||ｙ’と表記する。また、Ｅ（・）は、暗号化関数である。
［図８のステップＳ４３］次に、エンティティＢは、受信部４２６により受信されたエンティティＡからのチャレンジ情報Ｘを復号部４２２により復号し、復号関数Ｄ（Ｘ）＝Ｙ||Ｐとなるレスポンス情報Ｙと乱数情報Ｐを生成する。乱数情報Ｐは、秘密情報管理部４２１で保持される。
［図８のステップＳ４４］次に、エンティティＢは、乱数生成部４２３において乱数ＲＢをチャレンジ情報として生成し、レスポンス情報Ｙと共に、送信部４２５よりエンティティＡへ送信する。
［図８のステップＳ４５］次に、エンティティＡは、検証部４１４において、受信部４１６により受信したエンティティＢからのレスポンス情報Ｙが、ステップＳ４１で生成した乱数ＲＡと一致するかどうかを検証する。一致する場合は、相手エンティティを正しいと認証し、認証成功メッセージを秘密情報管理部４１１へ与え、プロトコルを続行する。
［図８のステップＳ４６］次に、エンティティＡは、秘密情報管理部４１１で保持する乱数情報ＱをエンティティＢと秘密に共有する情報ＫＥＹＡＢとして管理する。
［図８のステップＳ４７］次に、エンティティＡは、エンティティＢより受信したチャレンジ情報ＲＢを暗号化部４１３により暗号化したレスポンス情報Ｚ＝Ｅ（ＲＢ）を生成し、送信部４１５よりエンティティＢへ送信する。
［図８のステップＳ４８］次に、エンティティＢは、受信部４２６により受信したエンティティＡからのレスポンス情報Ｚを復号部４２２により復号し（即ち、Ｄ（Ｚ）を計算し）、検証部４２４においてステップＳ４４で生成した乱数ＲＢと一致するかどうかを検証する。一致する場合は、相手エンティティを正しいと認証し、認証成功メッセージを秘密情報管理部へ与える。
［図８のステップＳ４９］次に、エンティティＢは、秘密情報管理部４２１で保持する乱数情報ＰをエンティティＡと秘密に共有する情報ＫＥＹＡＢとして管理する。
【００７６】
［４−５］第４の実施形態の効果
以上に説明した第４の実施形態においては、第１の実施形態の場合と同様の効果を得ることができる。
【００７７】
また、第４の実施形態においては、相互認証方式を行うことによりさらに、２つのエンティティＡ，Ｂが共通の秘密情報ＫＥＹＡＢを保持することができる。秘密情報ＫＥＹＡＢは、相互認証を実行する上でやりとりされる暗号化情報に含まれているため、第１の実施形態における共通鍵が漏洩しない限り、外部に漏洩しない。共有した秘密情報ＫＥＹＡＢは、その後の一時的な秘密通信を実現するためのセッション鍵として用いることができ、認証に用いる鍵と秘密通信に用いる鍵を分離することによって、セキュリテイレベルを向上させることができるという効果がある。
【００７８】
［４−６］第４の実施形態の変形例
上記した第４の実施形態の説明においては、相互認証方式を行うことにより、２つのエンティティＡ，Ｂが共通の秘密情報ＫＥＹＡＢを保持することができる方法を上記第１の実施形態に適用した場合を説明したが、同様の手順により第２及び第３の実施形態に適用することも可能である。秘密情報は相互認証を実行する上でやりとりされる暗号化情報に含まれているため、第２及び第３の実施形態における公開鍵暗号の秘密鍵が漏洩しない限り外部に漏洩しない。
【００７９】
［５］他の利用形態の説明
上記第１乃至第４の実施形態においては、説明を簡単にするため必要最低限の情報と構成のみを用いて説明した。しかし、実際の相互認証においては、平文と暗号文の対応関係を隠したり、悪意あるエンティティのアクセスにより鍵情報が解析されるのを防ぐために相互認証でやりとりされる情報には、エンティティのＩＤ情報や、意味のない一時的なデータを含ませてやりとりするのが一般的である。
【００８０】
また、上記第１乃至第４の実施形態においては、多数ある相互認証のパターンの中から１例を取り上げて説明したが、本発明は、上記第１乃至第４の実施形態で説明された例に限定されるものではない。例えば、いずれのエンティティからプロトコルを開始するかなどや、公開鍵暗号方式に基づく場合であるかディジタル署名に基づく場合であるかなどの各種条件によって様々なパターンが存在する。
【００８１】
さらに、上記第１の実施形態においては、共通鍵暗号を例にして述べたが、共通鍵に基づく変換は暗号に限定しない。例えば、圧縮方式やなんらかの変換方式で、変換に用いられた鍵を知るものにしか逆変換が困難な方式を想定している。
【００８２】
第４の実施形態においては相互認証を実行することで秘密情報を共有したが、共有する秘密情報は１つとは限らない。
暗号化情報に２つの秘密情報を含ませることも可能であるし、２つのエンティティが相互に秘密情報を生成し、それを共有する場合もある。
【図面の簡単な説明】
【００８３】
【図１】本発明の第１の実施形態に係る相互認証方法、相互認証装置（エンティティ）、及び相互認証システムを説明するための基本的な概念図である。
【図２】図１に示されるエンティティＡの構成を示すブロック図である。
【図３】図１に示されるエンティティＢの構成を示すブロック図である。
【図４】本発明の第２の実施形態に係る相互認証方法、相互認証装置（エンティティ）、及び相互認証システムを説明するための基本的な概念図である。
【図５】図３に示されるエンティティＡ，Ｂの構成を示すブロック図である。
【図６】本発明の第３の実施形態に係る相互認証方法、相互認証装置（エンティティ）、及び相互認証システムを説明するための基本的な概念図である。
【図７】図６に示されるエンティティＡ，Ｂの構成を示すブロック図である。
【図８】本発明の第４の実施形態に係る相互認証方法、相互認証装置（エンティティ）、及び相互認証システムを説明するための基本的な概念図である。
【図９】図８に示されるエンティティＡの構成を示すブロック図である。
【図１０】図８に示されるエンティティＢの構成を示すブロック図である。
【図１１】従来の相互認証方法を説明するための基本的な概念図である。
【符号の説明】
【００８４】
１１０，２１０，３１０，４１０  エンティティＡ、
１２０，２２０，３２０，４２０  エンティティＢ、
１１１  エンティティＡの乱数生成部、
１１２  エンティティＡの暗号化部、
１１３  エンティティＡの検証部、
１１４  エンティティＡの送信部、
１１５  エンティティＡの受信部、
１２１  エンティティＢの復号部、
１２２  エンティティＢの乱数生成部、
１２３  エンティティＢの検証部、
１２４  エンティティＢの送信部、
１２５  エンティティＢの受信部、
２１１，２２１  エンティティＡ，Ｂの乱数生成部、
２１２，２２２  エンティティＡ，Ｂの公開鍵情報管理部、
２１３，２２３  エンティティＡ，Ｂの暗号化・復号部、
２１４，２２４  エンティティＡ，Ｂの検証部、
２１５，２２５  エンティティＡ，Ｂの送信部、
２１６，２２６  エンティティＡ，Ｂの受信部、
３１１，３２１  エンティティＡ，Ｂの乱数生成部、
３１２，３２２  エンティティＡ，Ｂの公開鍵情報管理部、
３１３，３２３  エンティティＡ，Ｂの署名生成部、
３１４，３２４  エンティティＡ，Ｂの署名検証部、
３１５，３２５  エンティティＡ，Ｂの送信部、
３１６，３２６  エンティティＡ，Ｂの受信部、
４１１  エンティティＡの秘密情報管理部、
４１２  エンティティＡの乱数生成部、
４１３  エンティティＡの暗号化部、
４１４  エンティティＡの検証部、
４１５  エンティティＡの送信部、
４１６  エンティティＡの受信部、
４２１  エンティティＢの秘密情報管理部、
４２２  エンティティＢの復号部、
４２３  エンティティＢの乱数生成部、
４２４  エンティティＢの検証部、
４２５  エンティティＢの送信部、
４２６  エンティティＢの受信部。
【図１】
2006025298.tif 000003
【図２】
2006025298.tif 000004
【図３】
2006025298.tif 000005
【図４】
2006025298.tif 000006
【図５】
2006025298.tif 000007
【図６】
2006025298.tif 000008
【図７】
2006025298.tif 000009
【図８】
2006025298.tif 000010
【図９】
2006025298.tif 000011
【図１０】
2006025298.tif 000012
【図１１】
2006025298.tif 000013