(57)【特許請求の範囲】
【請求項１】
第一端末と第二端末との間で相互認証を実行する相互認証システムであって、
前記第一端末は、
乱数ｒａを生成する第一乱数生成手段と、
前記第二端末との間で予め共有された鍵ｋに基づきマスクｍａを生成する第一マスク生成手段と、
前記乱数ｒａと前記マスクｍａとの排他的論理和を生成する第一排他的論理和手段と、
前記排他的論理和を前記第二端末に送信する第一送信手段と、
を有し、
前記第二端末は、
前記排他的論理和を受信する第一受信手段と、
前記鍵ｋに基づきマスクｍａを生成する第二マスク生成手段と、
前記第一受信手段により受信された前記排他的論理和と前記第二マスク生成手段により生成されたマスクｍａとに基づき乱数ｒａを復元する第一復元手段と、
乱数ｒｂを生成する第二乱数生成手段と、
前記鍵ｋと前記第二マスク生成手段により生成されたマスクｍａとに基づきマスクｍｂを生成する第三マスク生成手段と、
前記乱数ｒｂと前記マスクｍｂとの排他的論理和を生成する第二排他的論理和手段と、
前記第一復元手段により復元された乱数ｒａと、前記第二排他的論理和手段により求められた排他的論理和を送信する第二送信手段と、
を有し、
前記第一端末は、さらに、
前記第二端末において前記第一復元手段により復元された乱数ｒａと前記第二排他的論理和手段により求められた排他的論理和とを受信する第二受信手段と、
前記第二端末において前記第一復元手段により復元された乱数ｒａと前記第一端末において前記第一乱数生成手段により生成された乱数ｒａとが一致しているかどうかに基づき前記第二端末を認証する第一認証手段と、
前記第二端末において前記第一復元手段により復元された乱数ｒａと前記第一端末において前記第一乱数生成手段により生成された乱数ｒａとが一致している場合には、前記鍵ｋと前記第一マスク生成手段により生成されたマスクｍａとからマスクｍｂを生成する第四マスク生成手段と、
前記第二端末において前記第二排他的論理和手段により求められた排他的論理和と前記第四マスク生成手段により生成されたマスクｍｂとから乱数ｒｂを復元する第二復元手段と
を有し、
前記第二端末は、さらに、
前記第一端末において前記第二復元手段により復元された乱数ｒｂを受信し、当該乱数ｒｂと、前記第二端末において前記第三マスク生成手段により生成された乱数ｒｂとが一致するかどうかに基づき前記第一端末を認証する第二認証手段と
を有すること特徴とする相互認証システム。
【請求項２】
前記第一端末は、
Khoureich方式にしたがって前記第一端末と前記第二端末との間で鍵ｋを共有するために必要となるパラメータｒ１、ｒ３を生成するとともに、前記第一端末と前記第二端末との間で予め共有されている鍵テーブルから鍵ｋを生成する第一鍵生成手段とをさらに有し、
前記第一端末の前記第一マスク生成手段は、前記第一鍵生成手段により生成された前記鍵ｋに基づきマスクｍａを生成するように構成されており、
前記第一端末の前記第一送信手段は、前記鍵ｋを共有するために必要となるパラメータｒ１、ｒ３を前記第二端末に送信するように構成されており、
前記第二端末の前記第一受信手段は、前記鍵ｋを共有するために必要となるパラメータｒ１、ｒ３を受信するように構成されており、
前記第二端末は、
前記鍵ｋを共有するために必要となるパラメータｒ１、ｒ３および、前記第一端末と前記第二端末との間の予め共有されている前記鍵テーブルから鍵ｋを生成する第二鍵生成手段をさらに有し、
前記第二端末の前記第二マスク生成手段は、前記第二鍵生成手段により生成された前記鍵ｋに基づきマスクｍａを生成するように構成されており、
前記第二端末の前記第三マスク生成手段は、前記第二鍵生成手段により生成された鍵ｋと前記第二マスク生成手段により生成されたマスクｍａとに基づきマスクｍｂを生成するように構成されており、
前記第一端末の前記第四マスク生成手段は、前記第二端末において前記第一復元手段により復元された乱数ｒａと前記第一端末において前記第一乱数生成手段により生成された乱数ｒａとが一致している場合には、前記第一鍵生成手段により生成された鍵ｋと前記第一マスク生成手段により生成されたマスクｍａとからマスクｍｂを生成するように構成されていることを特徴とする請求項１に記載の相互認証システム。
【請求項３】
前記第一端末と前記第二端末との間で予め共有されている鍵テーブルのサイズＬｔは、前記鍵ｋの長さＬｋがセキュリティパラメータＬ以上となるように予め決定されていることを特徴とする請求項２に記載の相互認証システム。
【請求項４】
前記第一鍵生成手段で生成された鍵ｋの長さＬｋが前記セキュリティパラメータＬ以上でなければ、前記第一鍵生成手段は前記鍵ｋを再生成することを特徴とする請求項３に記載の相互認証システム。
【請求項５】
前記鍵テーブルのサイズＬｔは、（Ｌｔ − ２Ｌ）／√Ｌｔ＞２となるように決定されていることを特徴とする請求項３または４に記載の相互認証システム。
【請求項６】
前記第一マスク生成手段は、前記第一鍵生成手段により生成された鍵ｋを１ビット左シフトして得られたものに当該鍵ｋを加算することでマスクｍａを生成し、
前記第二マスク生成手段は、前記第二鍵生成手段により生成された鍵ｋを１ビット左シフトして得られたものに当該鍵ｋを加算することでマスクｍａを生成し、
前記第三マスク生成手段は、前記第二マスク生成手段により生成されたマスクｍａを１ビット左シフトして得られたものに前記第二鍵生成手段により生成された鍵ｋを加算することで前記マスクｍｂを生成し、
前記第四マスク生成手段は、前記第一マスク生成手段により生成されたマスクｍａを１ビット左シフトして得られたものに前記第一鍵生成手段により生成された鍵ｋを加算することで前記マスクｍｂを生成することを特徴とする請求項２ないし５のいずれか一項に記載の相互認証システム。
【請求項７】
前記第一鍵生成手段は、
乱数ｒ１と乱数ｒ２を生成し、
前記乱数ｒ１に基づきマスクｍ１を生成し、
前記第一端末と前記第二端末との間で予め共有されている鍵テーブルの一つである第一鍵テーブルＳＲと前記マスクｍ１との排他的論理和ＳＲ'を求め、
前記排他的論理和ＳＲ'と前記乱数ｒ２との排他的論理和ｒ３を求め、
前記排他的論理和ＳＲ'と前記第一端末と前記第二端末との間で予め共有されている鍵テーブルの一つである第二鍵テーブルＳＴとでビットが共通している共通位置を求め、前記乱数ｒ２における当該共通位置のビットを抽出することで前記鍵ｋを生成し、
前記第二鍵生成手段は、
前記第一端末から受信したパラメータｒ１からマスクｍ１を生成し、
前記第一端末と前記第二端末との間で予め共有されている鍵テーブルの一つである前記第一鍵テーブルＳＲと前記マスクｍ１との排他的論理和ＳＲ'を求め、
前記第一端末から受信したパラメータｒ３と前記第一端末と前記第二端末との間で予め共有されている鍵テーブルの一つである第二鍵テーブルＳＴとの排他的論理和ｒ４を求め、
前記排他的論理和ＳＲ'と前記第一端末と前記第二端末との間で予め共有されている前記第二鍵テーブルＳＴとでビットが共通している共通位置を求め、前記排他的論理和ｒ４における当該共通位置のビットを抽出することで前記鍵ｋを生成することを特徴とする請求項２ないし６のいずれか一項に記載の相互認証システム。
【請求項８】
他の端末装置との間で相互認証を実行する端末装置であって、
乱数ｒａを生成する第一乱数生成手段と、
前記他の端末装置との間で予め共有された鍵ｋに基づきマスクｍａを生成する第一マスク生成手段と、
前記乱数ｒａと前記マスクｍａとの排他的論理和を生成する第一排他的論理和手段と、
前記排他的論理和を前記他の端末装置に送信する第一送信手段と、
前記他の端末装置により復元された乱数ｒａと前記他の端末装置により求められた排他的論理和とを受信する第二受信手段と、
前記他の端末装置により復元された乱数ｒａと前記第一乱数生成手段により生成された乱数ｒａとが一致しているかどうかに基づき前記他の端末装置を認証する第一認証手段と、
前記他の端末装置により復元された乱数ｒａと前記第一乱数生成手段により生成された乱数ｒａとが一致している場合には、前記鍵ｋと前記第一マスク生成手段により生成されたマスクｍａとからマスクｍｂを生成する第四マスク生成手段と、
前記他の端末装置により求められた排他的論理和と前記第四マスク生成手段により生成されたマスクｍｂとから乱数ｒｂを復元して前記他の端末装置に送信する第二復元手段と
を有すること特徴とする端末装置。
【請求項９】
他の端末装置との間で相互認証を実行する端末装置であって、
前記他の端末装置との間で予め共有された鍵ｋに基づきマスクｍａを生成する第二マスク生成手段と、
前記他の端末装置において求められた排他的論理和と前記第二マスク生成手段により生成されたマスクｍａとに基づき乱数ｒａを復元する第一復元手段と、
乱数ｒｂを生成する第二乱数生成手段と、
前記鍵ｋと前記第二マスク生成手段により生成されたマスクｍａとに基づきマスクｍｂを生成する第三マスク生成手段と、
前記乱数ｒｂと前記マスクｍｂとの排他的論理和を生成する第二排他的論理和手段と、
前記第一復元手段により復元された乱数ｒａおよび前記第二排他的論理和手段により求められた排他的論理和を前記他の端末装置に送信する第二送信手段と、
前記他の端末装置の第二復元手段により復元された乱数ｒｂを受信し、当該乱数ｒｂと、前記第三マスク生成手段により生成された乱数ｒｂとが一致するかどうかに基づき前記他の端末装置を認証する第二認証手段と
を有すること特徴とする端末装置。
【請求項１０】
請求項８または９に記載の端末装置の各手段としてコンピュータを機能させるプログラム。
【請求項１１】
第一端末と第二端末との間で鍵共有と相互認証を実行する相互認証方法であって、
前記第一端末は、
乱数ｒａを生成する第一乱数生成工程と、
前記第二端末との間で予め共有された鍵ｋに基づきマスクｍａを生成する第一マスク生成工程と、
前記乱数ｒａと前記マスクｍａとの排他的論理和を生成する第一排他的論理和工程と、
前記排他的論理和を前記第二端末に送信する第一送信工程と、
を実行し、
前記第二端末は、
前記排他的論理和を受信する第一受信工程と、
前記鍵ｋに基づきマスクｍａを生成する第二マスク生成工程と、
前記第一受信工程により受信された前記排他的論理和と前記第二マスク生成工程により生成されたマスクｍａとに基づき乱数ｒａを復元する第一復元工程と、
乱数ｒｂを生成する第二乱数生成工程と、
前記鍵ｋと前記第二マスク生成工程により生成されたマスクｍａとに基づきマスクｍｂを生成する第三マスク生成工程と、
前記乱数ｒｂと前記マスクｍｂとの排他的論理和を生成する第二排他的論理和工程と、
前記第一復元工程により復元された乱数ｒａおよび前記第二排他的論理和工程により求められた排他的論理和を送信する第二送信工程と、
を実行し、
前記第一端末は、さらに、
前記第二端末において前記第一復元工程により復元された乱数ｒａと前記第二排他的論理和工程により求められた排他的論理和とを受信する第二受信工程と、
前記第二端末において前記第一復元工程により復元された乱数ｒａと前記第一端末において前記第一乱数生成工程により生成された乱数ｒａとが一致しているかどうかに基づき前記第二端末を認証する第一認証工程と、
前記第二端末において前記第一復元工程により復元された乱数ｒａと前記第一端末において前記第一乱数生成工程により生成された乱数ｒａとが一致している場合には、前記鍵ｋと前記第一マスク生成工程により生成されたマスクｍａとからマスクｍｂを生成する第四マスク生成工程と、
前記第二端末において前記第二排他的論理和工程により求められた排他的論理和と前記第一端末において前記第四マスク生成工程により生成されたマスクｍｂとから乱数ｒｂを復元する第二復元工程と
を実行し、
前記第二端末は、さらに、
前記第一端末において前記第二復元工程により復元された乱数ｒｂを受信し、当該乱数ｒｂと、前記第二端末において前記第三マスク生成工程により生成された乱数ｒｂとが一致するかどうかに基づき前記第一端末を認証する第二認証工程と
を実行すること特徴とする相互認証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は相互認証技術に関する。
【背景技術】
【０００２】
複数の端末間で相互に正当な端末であることを認証する相互認証が実行されることがある。たとえば、ＲＦＩＤタグとその読み取り装置との間で、ＲＦＩＤタグが正当なＲＦＩＤタグであり、かつ、読み取り装置も正当な読み取り装置であることが検証される（非特許文献１〜３）。
【０００３】
ところで、複数の端末間で鍵を共有し、この共有している鍵を用いて認証を行うことも提案されている（非特許文献４）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Hung-Yu Chien, SASI: "A New Ultralightweight RFID Authentication Protocol Providing Strong Authentication and Strong Integrity" IEEE Transaction on Dependable and Secure Computing, Vol. 4, No. 4, pp. 337-340, 2007.
【非特許文献２】Pedro Peris-Lop, et al. "Advanced in ultra lightweight cryptography for low-cost RFID tags: Gossamer protocol." The 9th International Workshop on Information Security Workshop, pp.56-68, 2009.
【非特許文献３】David, Mathieu, and Neeli R. Prasad. "Providing strong security and high privacy in low-cost RFID networks." International conference on Security and privacy in mobile information and communication systems, Italy, pp172-179, 2009.
【非特許文献４】Ka Ahmad Khoureich, "Light-hHB: A New Version of hHB with Improved Session Key Exchange."Cryptology ePrint Archive: Report 2015/713, https://eprint.iacr.org/2015/713, 2015.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来技術では、認証に必要な情報を複数の端末間で同期して更新する必要があった。相互認証に必要な情報を複数の端末間で同期して更新すると複数の端末間での通信回数が増加してしまう。そこで、本発明は複数の端末間での通信回数を削減可能な相互認証のための技術を提供する。
【課題を解決するための手段】
【０００６】
本発明によれば、
第一端末と第二端末との間で相互認証を実行する相互認証システムであって、
前記第一端末は、
乱数ｒａを生成する第一乱数生成手段と、
前記第二端末との間で予め共有された鍵ｋに基づきマスクｍａを生成する第一マスク生成手段と、
前記乱数ｒａと前記マスクｍａとの排他的論理和を生成する第一排他的論理和手段と、
前記排他的論理和を前記第二端末に送信する第一送信手段と、
を有し、
前記第二端末は、
前記排他的論理和を受信する第一受信手段と、
前記鍵ｋに基づきマスクｍａを生成する第二マスク生成手段と、
前記第一受信手段により受信された前記排他的論理和と前記第二マスク生成手段により生成されたマスクｍａとに基づき乱数ｒａを復元する第一復元手段と、
乱数ｒｂを生成する第二乱数生成手段と、
前記鍵ｋと前記第二マスク生成手段により生成されたマスクｍａとに基づきマスクｍｂを生成する第三マスク生成手段と、
前記乱数ｒｂと前記マスクｍｂとの排他的論理和を生成する第二排他的論理和手段と、
前記第一復元手段により復元された乱数ｒａと、前記第二排他的論理和手段により求められた排他的論理和を送信する第二送信手段と、
を有し、
前記第一端末は、さらに、
前記第二端末において前記第一復元手段により復元された乱数ｒａと前記第二排他的論理和手段により求められた排他的論理和とを受信する第二受信手段と、
前記第二端末において前記第一復元手段により復元された乱数ｒａと前記第一端末において前記第一乱数生成手段により生成された乱数ｒａとが一致しているかどうかに基づき前記第二端末を認証する第一認証手段と、
前記第二端末において前記第一復元手段により復元された乱数ｒａと前記第一端末において前記第一乱数生成手段により生成された乱数ｒａとが一致している場合には、前記鍵ｋと前記第一マスク生成手段により生成されたマスクｍａとからマスクｍｂを生成する第四マスク生成手段と、
前記第二端末において前記第二排他的論理和手段により求められた排他的論理和と前記第四マスク生成手段により生成されたマスクｍｂとから乱数ｒｂを復元する第二復元手段と
を有し、
前記第二端末は、さらに、
前記第一端末において前記第二復元手段により復元された乱数ｒｂを受信し、当該乱数ｒｂと、前記第二端末において前記第三マスク生成手段により生成された乱数ｒｂとが一致するかどうかに基づき前記第一端末を認証する第二認証手段と
を有すること特徴とする相互認証システムが提供される。
【発明の効果】
【０００７】
本発明によれば、複数の端末間での通信回数を削減可能な相互認証のための技術が提供される。
【図面の簡単な説明】
【０００８】
【図１】相互認証システムの一例を示す図
【図２】第一端末の機能を示すブロック図
【図３】第二端末の機能を示すブロック図
【図４】第一端末が実行する工程を示すフローチャート
【図５】第二端末が実行する工程を示すフローチャート
【図６】第一端末が実行する工程を示すフローチャート
【図７】第二端末が実行する工程を示すフローチャート
【図８】相互認証システムの通信シーケンスを示す図
【図９】鍵生成方法を示す図
【図１０】従来技術と本実施例との比較結果を示す図
【発明を実施するための形態】
【０００９】
＜相互認証システム＞
図１は相互認証システム１００の一例を示す図である。第一端末１０１と第二端末１０３（１０３ａ、１０３ｂ）は鍵共有を実行して相互認証を実行する端末装置である。これらの端末装置としては、たとえば、スマートフォンなどのコンピュータとその周辺機器などがある。なお、第一端末１０１と第二端末１０３はコンテンツを提供するコンテンツサーバとコンテンツを受信して再生するコンテンツクライアントであってもよい。また、ＲＦＩＤタグとその読み書き装置なども端末装置の一例である。これらの端末は有線回線や無線回線などの通信リンク１０２を介して鍵共有と相互認証とを実行する。なお、第一端末１０１はイニシエータ端末と呼ばれ、第二端末１０３はレスポンダ端末と呼ばれてもよい。複数の端末間で共有された鍵はコンテンツを暗号化／復号化するためのコンテンツ鍵として使用されてもよいし、通信サービスにおけるセッションを暗号化／復号化するためのセッション鍵として使用されてもよい。
【００１０】
図２ないし図１０を用いて第一端末１０１と第二端末１０３の機能と相互認証方法について説明する。図２は第一端末１０１の機能を示している。図３は第二端末１０３の機能を示している。なお、これらの機能はＣＰＵが記憶装置に記憶されたプログラムを実行することで実現されてもよいし、ＡＳＩＣ（特定用途集積回路）やＦＰＧＡ（フィールドプログラマブルロジックアレイ）等のハードウエアによって実現されてもよい。プログラムはコンピュータ可読記録媒体に格納されて提供されてもよい。図４は第一端末１０１が実行する相互認証方法の一部を示している。
【００１１】
Ｓ４０１で第一鍵生成部２０１はパラメータｒ１、ｒ２を生成する。ここで、パラメータｒ１、ｒ２は、たとえば乱数ｒ１と乱数ｒ２である。乱数ｒ１はKhoureich方式にしたがって第一端末１０１と第二端末１０３との間で鍵ｋを共有するために必要となるパラメータの一つである。
【００１２】
Ｓ４０２で第一鍵生成部２０１は乱数ｒ１に基づきマスクｍ１を生成する。たとえば、第一鍵生成部２０１は、次式にしたがってマスクｍ１を生成してもよい。ｍ１＝（ｒ１≪１）＋（ｒ１≫１）。ここで、≪は左シフト演算を示している。≫は右シフト演算を示している。つまり、ｒ１を１ビット左シフトしたものと、ｒ１を１ビット右シフトしたものとを加算することでマスクｍ１が生成される。
【００１３】
Ｓ４０３で第一鍵生成部２０１は第一鍵テーブルＳＲとマスクｍ１との排他的論理和ＳＲ'を求める（ＳＲ'＝ＳＲ XOR ｍ１）。ここで、第一鍵テーブルＳＲは第一端末１０１と第二端末１０３との間で予め共有されている鍵テーブルの一つであり、第一保持部２０２に記憶されているものとする。XORは排他的論理和を示す演算記号である。排他的論理和を示す演算記号としては、＋記号を丸で囲んだ記号が採用されてもよい。図面では演算記号の記述スペースを削減するため、後者の演算記号が用いられている。
【００１４】
Ｓ４０４で第一鍵生成部２０１は排他的論理和ＳＲ'と乱数ｒ２に基づきパラメータｒ３を求める。たとえば、パラメータｒ３は、排他的論理和ＳＲ'と乱数ｒ２との排他的論理和ｒ３である（ｒ３＝ｒ２ XORＳＲ'）。排他的論理和ｒ３はKhoureich方式にしたがって第一端末１０１と第二端末１０３との間で鍵ｋを共有するために必要となるパラメータの一つである。
【００１５】
Ｓ４０５で第一鍵生成部２０１は第一端末１０１と第二端末１０３との間で予め共有されている鍵テーブルから鍵ｋを生成する。たとえば、第一鍵生成部２０１は排他的論理和ＳＲ'のビット列と第二鍵テーブルＳＴのビット列とでビットが共通している共通位置を求め、乱数ｒ２における当該共通位置のビットを抽出することで鍵ｋを生成する。図９（Ａ）が示すように、排他的論理和ＳＲ'と第二鍵テーブルＳＴとでビットが共通している共通位置は、左から３ビット目、４ビット目、６ビット目、８ビット目である。したがって、第一鍵生成部２０１は乱数ｒ２から３ビット目、４ビット目、６ビット目、８ビット目にあるビットを抽出することで、鍵ｋ（＝００１０）を生成する。なお、第二鍵テーブルＳＴは、第一端末１０１と第二端末１０３との間で予め共有されている鍵テーブルの一つであり、第一保持部２０２に記憶されているものとする。
【００１６】
Ｓ４０６で第一鍵生成部２０１は、生成された鍵ｋのサイズ（鍵長Ｌｋ）がセキュリティパラメータＬ以上であるかどうかを判定する。これは鍵の強度を確保するための判定処理である。鍵長ＬｋがセキュリティパラメータＬ以上であれば第一鍵生成部２０１はＳ４０７に進む。鍵長ＬｋがセキュリティパラメータＬ未満であれば第一鍵生成部２０１はＳ４０１に戻り、Ｓ４０１ないしＳ４０６を繰り返すことで鍵ｋを再生成する。これにより鍵の強度が確保される。
【００１７】
Ｓ４０７で第一乱数生成部２０４は乱数ｒａを生成する。
【００１８】
Ｓ４０８で第一マスク生成部２０３は鍵ｋに基づきマスクｍａを生成する。たとえば、第一マスク生成部２０３は次式にしたがってマスクｍａを生成してもよい。ｍａ＝（ｋ≪１）＋ｋ。つまり、鍵ｋを一ビット左シフトしたものに元の鍵ｋを加算することでマスクｍａが生成されてもよい。
【００１９】
Ｓ４０９で第一排他的論理和部２０５は乱数ｒａとマスクｍａとの排他的論理和（ｒａ XOR ｍａ）を生成する。
【００２０】
Ｓ４１０で第一送信部２０６は鍵共有で必要となるパラメータ（乱数ｒ１、排他的論理和ｒ３）と、鍵ｋに基づき演算された排他的論理和（ｒａ XOR ｍａ）を第二端末１０３に送信する。図８が示すように、第一端末１０１から鍵共有で必要となるパラメータである乱数ｒ１、排他的論理和ｒ３、排他的論理和（ｒａ XOR ｍａ）とを連結して構成されたデータが第二端末１０３に送信される。
【００２１】
図５は第二端末１０３が実行する相互認証方法の一部を示している。
【００２２】
Ｓ５０１で第一受信部３０１は鍵共有で必要となるパラメータ（乱数ｒ１、排他的論理和ｒ３）と、鍵ｋに基づき演算された排他的論理和（ｒａ XOR ｍａ）を第一端末１０１から受信する。
【００２３】
Ｓ５０２で第二鍵生成部３０２は第一端末１０１から受信したパラメータ（乱数ｒ１）からマスクｍ１を生成する。たとえば、第二鍵生成部３０２は、次式にしたがってマスクｍ１を生成してもよい。ｍ１＝（ｒ１≪１）＋（ｒ１≫１）。
【００２４】
Ｓ５０３で第二鍵生成部３０２は第一鍵テーブルＳＲとマスクｍ１との排他的論理和ＳＲ'を求める（ＳＲ'＝ＳＲ XOR ｍ１）。なお、第二保持部３０３は第一保持部２０２と同様に第一鍵テーブルＳＲと第二鍵テーブルＳＴを予め記憶している。
【００２５】
Ｓ５０４で第二鍵生成部３０２は第一端末１０１から受信したパラメータ（排他的論理和ｒ３）と第二鍵テーブルＳＴとの排他的論理和ｒ４を求める（ｒ４＝ｒ３ XOR ＳＴ）。
【００２６】
Ｓ５０５で第二鍵生成部３０２は鍵共有で必要となるパラメータと第一端末１０１と第二端末１０３との間の予め共有されている鍵テーブルから鍵ｋを生成する。たとえば、第二鍵生成部３０２は受信した乱数ｒ１から求めた排他的論理和ＳＲ'と第二鍵テーブルＳＴとでビットが共通している共通位置を求め、排他的論理和ｒ４における当該共通位置のビットを抽出することで鍵ｋを生成する。図９（Ｂ）が示すように、排他的論理和ＳＲ'と第二鍵テーブルＳＴとでビットが共通している共通位置は、左から３ビット目、４ビット目、６ビット目、８ビット目である。したがって、第一鍵生成部２０１は排他的論理和ｒ４から３ビット目、４ビット目、６ビット目、８ビット目のビットを抽出することで、鍵ｋ（＝００１０）を生成する。
【００２７】
Ｓ５０６で第二マスク生成部３０４は第二鍵生成部３０２により生成された鍵ｋに基づきマスクｍａを生成する。たとえば、第二マスク生成部３０４は次式にしたがってマスクｍａを生成してもよい。ｍａ＝（ｋ≪１）＋ｋ。つまり、鍵ｋを一ビット左シフトしたものに元の鍵ｋを加算することでマスクｍａが生成されてもよい。
【００２８】
Ｓ５０７で第一復元部３０５は第一受信部３０１により受信された排他的論理和（ｒａ XOR ｍａ）と第二マスク生成部３０４により生成されたマスクｍａとに基づき乱数ｒａを復元する。
【００２９】
Ｓ５０８で第二乱数生成部３０８は乱数ｒｂを生成する。
【００３０】
Ｓ５０９で第三マスク生成部３０６は第二鍵生成部３０２により生成された鍵ｋと第二マスク生成部３０４により生成されたマスクｍａとに基づきマスクｍｂを生成する。たとえば、第三マスク生成部３０６は次式にしたがってマスクｍｂを生成してもよい。ｍｂ＝（ｍａ≪１）＋ｋ。つまり、マスクｍａを一ビット左シフトしたものに鍵ｋを加算することでマスクｍｂが生成されてもよい。
【００３１】
Ｓ５１０で第二排他的論理和部３０７は乱数ｒｂとマスクｍｂとの排他的論理和（ｒｂ XOR ｍｂ）を生成する。
【００３２】
Ｓ５１１で第二送信部３０９は第一復元部３０５により復元された乱数ｒａと、第二排他的論理和部３０７により求められた排他的論理和（ｒｂ XOR ｍｂ）を送信する。図８が示すように、第二端末１０３から復元された乱数ｒａと排他的論理和（ｒｂ XOR ｍｂ）とが連結されて生成された認証データが第一端末１０１に送信される。
【００３３】
図６は第一端末１０１が実行する相互認証方法の一部を示している。
【００３４】
Ｓ６０１で第二受信部２０７は第二端末１０３の第一復元部３０５により復元された乱数ｒａと第二排他的論理和部３０７により求められた排他的論理和（ｒｂ XOR ｍｂ）とを受信する。
【００３５】
Ｓ６０２で第一認証部２０８は第二端末１０３が正当な端末かどうかを認証する。たとえば、第一認証部２０８は第二受信部２０７により受信された乱数ｒａと第一乱数生成部２０４により生成された乱数ｒａとが一致しているかどうかに基づき第二端末１０３を認証する。第二端末１０３側の乱数ｒａと第一端末１０１側の乱数ｒａとが不一致であれば、第一認証部２０８は認証失敗（ＮＧ）と判定する。一方で、第二端末１０３側の乱数ｒａと第一端末１０１側の乱数ｒａとが一致している場合には、第一認証部２０８は認証成功（ＯＫ）と判定し、Ｓ６０３に進む。
【００３６】
Ｓ６０３で第四マスク生成部２０９は第一鍵生成部２０１により生成された鍵ｋと第一マスク生成部２０３により生成されたマスクｍａとからマスクｍｂを生成する。第四マスク生成部２０９は、第三マスク生成部３０６と同様の式を用いてマスクｍｂを生成する。ｍｂ＝（ｍａ≪１）＋ｋ。つまり、マスクｍａを一ビット左シフトしたものに鍵ｋを加算することでマスクｍｂが生成される。
【００３７】
Ｓ６０４で第二復元部２１０は第二受信部２０７により受信された排他的論理和（ｒｂ XOR ｍｂ）と第四マスク生成部２０９により生成されたマスクｍｂとから乱数ｒｂを復元する。
【００３８】
Ｓ６０４で第一送信部２０６は第二復元部２１０により復元された乱数ｒｂを第二端末１０３に送信する。図８に示すように第一端末１０１から第二端末１０３へ復元された乱数ｒｂが認証データとして送信される。
【００３９】
図７は第二端末１０３が実行する相互認証方法の一部を示している。
【００４０】
Ｓ７０１で第一受信部３０１は第一端末１０１の第二復元部２１０により復元された乱数ｒｂを受信する。
【００４１】
Ｓ７０２で第二認証部３１０は受信した乱数ｒｂと、第三マスク生成部３０６により生成された乱数ｒｂとが一致するかどうかに基づき第一端末１０１を認証する。第一端末１０１の第二復元部２１０により復元された乱数ｒｂと、第二端末１０３において第三マスク生成部３０６により生成された乱数ｒｂとが一致していれば、第二認証部３１０は第一端末１０１を正当な端末と判定する（認証成功）。一方で、第一端末１０１から受信した乱数ｒｂと、第三マスク生成部３０６により生成された乱数ｒｂとが一致していなければ、第二認証部３１０は第一端末１０１を正当な端末ではないと判定する（認証失敗）。
【００４２】
図８が示すように本実施例では第一端末１０１と第二端末１０３との間で三回の通信を実行することで鍵ｋの共有と相互認証とを実行することが可能となる。
【００４３】
＜鍵の強度の担保＞
第一端末１０１と第二端末１０３とで共有される鍵ｋの強度を確保するために、本実施例では以下のような工夫が採用されてもよい。ここでは、第一鍵テーブルＳＲと第二鍵テーブルＳＴの各テーブルサイズをＬｔビットと仮定する。鍵ｋの鍵長Ｌｋは、平均がＬｔ／２で、かつ、標準偏差が√（Ｌｔ）／２の正規分布Ｎ（Ｌｔ／２，√（Ｌｔ）／２）で近似される。このため、鍵長ＬｋがセキュリティパラメータＬを下回る確率は次式から求められる。
【００４４】
【数１】
0006464077.tif 000002
【００４５】
ここでＺはＮ（０，１）にしたがう確率変数である。この確率が十分に小さくなるには、（Ｌｔ−２Ｌ）／√Ｌｔが２以上となるようにＬｔが選択されればよい。たとえば、セキュリティパラメータＬが６４である場合、Ｌｔは１９２であればよい。つまり、鍵ｋの鍵長ＬｋがセキュリティパラメータＬ未満となる確率はＰｒ［Ｚ＜−４．６１９］＝１．９２×１０−６である。このようにテーブルサイズＬｔを選択しておくことで、Ｓ４０１ないしＳ４０６の鍵生成が再実行される確率が非常に小さくなる。
【００４６】
＜比較＞
本実施例の効果を説明するために、非特許文献１ないし３と本実施例とを比較する。図１０は、非特許文献１ないし３と本実施例との比較結果を示している。非特許文献１（SASIプロトコル）、非特許文献２（Gossamerプロトコル）および非特許文献３（David-Prasadプロトコル）と比較すると、本実施例は、総演算回数をほとんど増やすことなく、通信回数を３回に削減することが可能となる。また、本実施例ではワード単位での演算も可能となる点で、非特許文献１、２よりも有利である。
【００４７】
＜まとめ＞
本実施例によれば、図８が示すように、第一端末１０１から鍵共有で必要となるパラメータである乱数ｒ１、排他的論理和ｒ３、排他的論理和（ｒａ XOR ｍａ）とが第二端末１０３に送信される。また復元された乱数ｒａと排他的論理和（ｒｂ XOR ｍｂ）とが認証データとして第二端末１０３から第一端末１０１に送信される。さらに、第一端末１０１から第二端末１０３へ復元された乱数ｒｂが認証データとして送信される。つまり、本実施例では、３回の通信回数で鍵ｋの共有と、第一端末１０１と第二端末１０３との相互認証が実現可能となっている。本実施例では鍵共有と相互認証とを同時並行的に実行するものとして説明したが、鍵ｋについては事前に共有されていてもよい。つまり、相互認証だけが実行されてもよい。
【００４８】
第一端末１０１と第二端末１０３との間で予め共有されている鍵テーブルＳＴ、ＳＲのサイズＬｔは、鍵ｋの長さＬｋがセキュリティパラメータＬ以上となるように予め決定されている。これにより、鍵共有（鍵生成）が再実施される確率を十分に小さくすることが可能となる。たとえば、鍵テーブルのサイズＬｔは、（Ｌｔ − ２Ｌ）／√Ｌｔ＞２となるように決定されれば、鍵共有（鍵生成）が再実施される確率は極めて小さくなる。
【００４９】
また、本実施例によれば事前に鍵テーブルを共有しておくだけで、認証ごとのデータの同期は不要となる。つまり、認証ごとのデータの同期が必要となる従来技術と比較して、軽量な認証プロトコルが実現可能となっている。
【図１】
0006464077.tif 000003
【図２】
0006464077.tif 000004
【図３】
0006464077.tif 000005
【図４】
0006464077.tif 000006
【図５】
0006464077.tif 000007
【図６】
0006464077.tif 000008
【図７】
0006464077.tif 000009
【図８】
0006464077.tif 000010
【図９】
0006464077.tif 000011
【図１０】
0006464077.tif 000012