効率的相互認証方法，プログラム，及び装置

【課題】認証時に、共通鍵暗号ベースの相互認証と同等の処理速度を達成する公開鍵暗号ベースの相互認証方法を実現すること。
【解決手段】署名生成において、事前計算により署名対象データが入力された際の処理量を軽減できる署名方法と、公開鍵暗号の暗号化において、事前計算により暗号化対象データが入力された際の処理量を軽減できる公開鍵暗号方法を組み合わせ、チャレンジレスポンス型の相互認証を構成し、認証を行う一方に事前計算を行うことができる手順を集中させることで、実際の認証時の処理時間を共通鍵暗号ベースの相互認証と同等レベルに軽減する。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュリティ技術に係り、特に相互に相手や機器を認証しあう技術に関する。
【背景技術】
【０００２】
認証技術は通信や対話の相手が意図した人あるいは物であることを確認する技術であり、インターネット通信や不特定多数がアクセス可能な機器において、セキュリティを確保するための根幹にある技術である。認証には、暗号技術を用いた方法や、生体情報を元に本人確認を行う生体認証などがある。
【０００３】
いずれにおいても、通信などの最初に認証を行い、意図した相手である場合には、入室の許可や、鍵共有プロトコル実行後にその共有鍵による暗号化通信を行う。その際、認証が安全でなく、相手の正当性があやふやな状態ならば、その後に行われるサービス提供や重要な情報の送受信などで、サービス不正利用や機密情報漏洩を防止していることを保証することはできない。認証の安全性は慎重に検討されるべきものである。
【０００４】
暗号技術を用いた認証では、あるユーザ（あるいは物）は、自身のみが知っている秘密情報をもとにあるデータを作成し、それを相手に確認してもらう形で実行される。認証の課程、あるいは認証後にユーザの秘密情報が相手にもれないよう暗号技術を用いて構成されなければならない。
【０００５】
暗号技術を用いた認証方法としては、主に共通鍵暗号技術をベースにしたものと公開鍵暗号技術をベースにしたものに分けられる（例えば、非特許文献１、２参照。）。
【０００６】
ここでは認証しあう二者で事前に秘密鍵（Secret key）を共有しておき、一方が他者を認証する際、その秘密鍵（Secret key）を持っているもののみが可能な処理を実行できるか否かで判断する方法を共通鍵暗号技術ベースの認証と呼ぶ。共通鍵暗号を用いて、乱数を暗号化し、相手が正しく復号できるか否かを確認する、共通鍵暗号ベースのチャレンジレスポンス型認証や、乱数に対して相手にメッセージ認証子（Message Authentication Code、ＭＡＣ）を生成してもらい、正しいＭＡＣであるかどうかを確認する、ＭＡＣベースの認証などが代表的である。
【０００７】
公開鍵暗号技術ベースの認証は、証明者（自己を証明する人（物））のみが秘密鍵（Private key）を持ち、検証者は、対応する公開鍵を用いて秘密鍵（Private key）を持っているもののみが可能な処理を実行できるか否かで正しい証明者か否かを判断する方法のことをさす。ＲＳＡ暗号などの公開鍵暗号を用いて、暗号化した乱数を相手が正しく復号できるか否かを確認する、公開鍵暗号ベースの認証や、乱数に対して相手にデジタル署名を生成してもらい、正しい署名であるかどうかを確認する、デジタル署名ベースの認証、また、認証専用に設計された公開鍵暗号技術ベースの認証方法（例えば、非特許文献３参照。）などがある。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Needham, Roger; Schroeder, Michael (December 1978), "Using encryption for authentication in large networks of computers.", Communications of the ACM 21 (12): 993999．
【非特許文献２】Needham, R. M.; Schroeder, M. D. (1987). "Authentication revisited". ACM SIGOPS Operating Systems Review 21 (1): 7．
【非特許文献３】C.P. Schnorr, Efficient identification and signatures for smart cards, in G. Brassard, ed. Advances in CryptologyCrypto '89, 239-252, Springer-Verlag, 1990. Lecture Notes in Computer Science 435．
【発明の概要】
【発明が解決しようとする課題】
【０００９】
暗号技術を用いた認証において、共通鍵暗号技術ベースの認証は一般に認証する二者における処理速度が速く、実装規模も比較的小さいため、ＩＣカードなどの低リソースデバイスでの認証や、大量のユーザを同時に処理しなければならないサーバ、また、非常に短時間に認証を終えなければならない改札機などで利用されている。
【００１０】
しかし、鍵の事前共有のためのコストや、ユーザ数の増大による必要な秘密鍵（Secret key）の個数の爆発的増大などの問題があり、システムによっては複数ユーザにひとつの秘密鍵（Secret key）を割り当てるなどの妥協が採用されている場合もある。しかし明らかにこのような妥協は安全性に問題がある。例えば極端な例として、システムで共通のひとつの秘密鍵（Secret key）で運用する場合などは、あるひとりのユーザからの鍵の漏洩によりシステム全体の安全性が損なわれ、鍵の総入れ替えなどの大規模な復旧処理が発生する。このように、ユーザ数の多いシステムでは安全性を確保するためには、鍵管理のコストをかけなければならない。
【００１１】
一方、公開鍵暗号技術ベースの認証では、各ユーザがひとつの秘密鍵（Private key）を持ち、対応する公開鍵を公開するため、共通鍵暗号技術ベースの認証に比べ、鍵の管理コストが少なくて済む。すなわち、ひとりのユーザから漏れる可能性のある秘密情報は、そのユーザ自身の秘密鍵（Private key）であり、システム全体に及ぼす影響は最小限である。
【００１２】
しかし一般に処理速度は共通鍵暗号技術ベースの認証に比べ、１００倍〜１０００倍程度遅く、また実装に必要なメモリ領域や、回路規模も大きくなる。ＩＣカードに実装し利用されている例もあるが、認証のための処理時間を１秒から数秒かけてもよいシステムでなければならない。
【００１３】
公共交通機関の改札でのＩＣカードと改札機との相互の認証ではその処理時間は許容できず、共通鍵暗号技術ベースの認証を用いざるを得ないのが現状である。また、高速ですれ違う車と車との間の通信などで瞬時に認証する必要がある場合にも公開鍵暗号技術ベースの認証では間に合わない。
【００１４】
このように、暗号技術を用いた認証において、公開鍵暗号技術ベースの認証のような鍵管理の容易さを持ちつつ、共通鍵暗号技術ベースのような処理速度を達成する認証方法の実現が求められている。
【課題を解決するための手段】
【００１５】
本明細書では、相互認証において、事前計算を実施することにより、実際の処理対象が入力された後の処理が共通鍵暗号並みに高速に実行できる公開鍵暗号と、デジタル署名（ｏｎｌｉｎｅ／ｏｆｆｌｉｎｅ公開鍵暗号、ｏｎｌｉｎｅ／ｏｆｆｌｉｎｅ署名とも呼ばれる）と、を組み合わせて利用する相互認証技術が開示される。
【００１６】
開示にされるように、事前計算を行うことで、実際の認証時には共通鍵暗号技術ベースの相互認証と同等の処理速度を達成することが可能となる。
【００１７】
これにより、鍵管理のコストを抑えつつ、ＩＣカードなどの低リソースデバイスでの相互認証や、瞬時の処理が必要な、高速な相互認証、また、大量ユーザの同時処理を行うサーバの高速化が可能となる。
【００１８】
一例として、開示されるのは、通信でデータの送受信が可能な二種類の装置Ａと装置Ｂを備えるシステムにおいて、上記装置Ａと上記装置Ｂとが互いに相手装置の正当性を確認する相互認証方法である。
【００１９】
上記相互認証方法は、
上記装置Ａが、上記装置Ｂの正当性を確認するステップにおいて、
上記装置Ａによる、
認証時に、乱数ｒＡを生成するステップと、
生成した上記乱数ｒＡを上記装置Ｂに送信するステップと、
上記装置Ｂによる、
上記乱数ｒＡを受信した後、記憶する署名生成用事前計算データを利用して、上記乱数ｒＡに対する署名を生成するステップと、
生成した上記署名を上記装置Ａに送信するステップと、
上記装置Ａによる、
上記装置Ｂの署名検証鍵を用いて、受信した上記署名を検証するステップと、
上記署名が正しいと判断すれば上記装置Ｂを正当と判断し、正しくないと判断すれば上記装置Ｂを不当と判断するステップと、を備えることを特徴とする。
【００２０】
さらに、上記相互認証方法は、相互認証を行う上記装置Ｂが、上記装置Ａの正当性を確認するステップにおいて、
上記装置Ｂによる、
認証時に、乱数ｒＢを生成するステップと、
上記乱数ｒＢを、記憶する暗号化用事前計算データを用いて公開鍵暗号化をするステップと、
上記暗号化の結果である暗号文を上記装置Ａに送信するステップと、
上記装置Ａによる、
上記装置Ａの秘密鍵（Private key）を用いて、受信した上記暗号文を復号化するステップと、
上記復号化結果を上記装置Ｂに送信するステップと、
上記装置Ｂによる、
上記記憶した乱数ｒＢと、上記装置Ａから受信した復号化結果とを照合するステップと、
上記乱数ｒＢと上記復号化結果とが一致していれば上記装置Ａを正当と判断し、一致していなければ上記装置Ａを不当と判断するステップと、を備えることを特徴とする。
【発明の効果】
【００２１】
本発明により、鍵管理コストを抑え、かつ、高速な相互認証が可能になる。
【図面の簡単な説明】
【００２２】
【図１】第一の実施形態である相互認証装置の概略を例示する図。
【図２】相互認証における署名利用部分のシーケンスを例示する図。
【図３】相互認証における公開鍵暗号利用部のシーケンスを例示する図。
【図４】第二の実施形態におけるリーダライタとＩＣカードの構成を例示する図。
【図５】第二の実施形態における代理事前計算処理のシーケンスを例示する図。
【図６】第三の実施形態における大量ユーザとサーバの構成を例示する図。
【図７】第四の実施形態における走行車両と路側機の構成を例示する図。
【発明を実施するための形態】
【００２３】
本発明の実施の形態を図面を用いて説明する。
【実施例１】
【００２４】
図１は、本発明の第一の実施形態である相互認証装置Ａ１００と相互認証装置Ｂ２００が実行する相互認証の概略図である。
【００２５】
図示するように、相互認証装置Ａ１００は、処理部１１０と、記憶部１２０と、乱数生成部１３１と、外部通信部１３２と、を備える。
【００２６】
相互認証装置Ｂは、処理部２１０と、記憶部２２０と、乱数生成部２３１と、外部通信部２３２と、を備える。
【００２７】
相互認証装置Ａ１００の外部通信部１３２と、相互認証装置Ｂ２００の外部通信部２３２は、通信線３１０と、ネットワークを介し、通信可能である。
【００２８】
本実施形態では、相互認証装置Ａ１００と相互認証装置Ｂの相互認証をおこなう。
【００２９】
相互認証装置Ａ１００の処理部１１０は、署名検証部１１１と、公開鍵暗号復号化部１１２と、を備える。相互認証装置Ａ１００の記憶部１２０は、相互認証装置Ｂ２００の署名検証鍵を記憶する署名検証鍵記憶領域１２１と、相互認証装置Ａ１００の復号鍵を記憶する公開鍵暗号復号鍵記憶領域１２２と、を備える。
【００３０】
相互認証装置Ｂ２００の処理部２１０は、署名生成部２１１と、公開鍵暗号暗号化部２１２と、署名生成、公開鍵暗号暗号化に用いる事前データ計算部２１３と、を備える。相互認証装置Ｂ２００の記憶部２２０は、相互認証装置２００の署名生成鍵を記憶する署名生成鍵記憶領域２２１と、相互認証装置Ａの公開鍵を記憶する公開鍵暗号暗号鍵記憶領域２２２と、事前計算データ記憶領域２２３と、一時データ記憶領域２２４と、を備える。
【００３１】
署名検証部１１１は、署名検証鍵記憶領域１２１から署名検証鍵を読み出し、外部通信部１３２を経て得られた署名検証対象データに対して署名検証を行う。
【００３２】
公開鍵暗号復号化部１１２は、公開鍵暗号復号鍵記憶領域１２２から復号鍵を読み出し、外部通信部１３２を経て得られた復号対象データの復号を行う。
【００３３】
署名生成部２１１は、署名生成鍵記憶領域２２１から署名生成鍵を読み出し、事前計算データ記憶領域２２３から事前計算データを読み出し、乱数生成部２３１から乱数を得て、外部通信部２３２を経て得られた署名生成対象データに対して署名生成を行う。
【００３４】
公開鍵暗号暗号化部２１２は、公開鍵暗号暗号鍵記憶領域２２２から暗号鍵を読み出し、事前計算データ記憶領域２２３から事前計算データを読み出し、乱数生成部２３１から得られた乱数を暗号化する。
【００３５】
事前データ計算部２１３は、相互認証装置Ａ１００と相互認証装置Ｂ２００とが相互認証を行う前の任意の時点で、署名生成鍵記憶領域２２１から読み出した署名生成鍵と、乱数生成部２３１から得られた乱数を用いて、署名対象のデータが与えられる前に実行可能な、署名生成に必要な全ての計算を行い、その結果を事前計算データ記憶領域２２３に保存する。また事前データ計算部２１３は相互認証装置Ａ１００と相互認証装置Ｂ２００とが相互認証を行う前の任意の時点で、公開鍵暗号暗号鍵記憶領域２２２から読み出した暗号鍵と、乱数生成部２３１から得られた乱数を用いて、暗号化対象のデータが与えられる前に実行可能な、暗号化に必要な全ての計算を行い、その結果を事前計算データ記憶領域２２３に保存する。
【００３６】
相互認証装置Ａ１００と相互認証装置Ｂ２００の、上記処理部１１０，２１０の各機能は、それぞれ、ＣＰＵと記憶装置と通信装置とを備えた計算機において、記憶装置に格納されたプログラムをＣＰＵが実行することにより、実現される。また、乱数生成部１３１、２３１は、同様に、ＣＰＵがプログラムを実行することにより実現されても良いし、ハードウェアによって実現されてもよい。
【００３７】
プログラムは、予め記憶装置に格納されていても良いし、必要に応じて、図示しない外部インタフェースや通信装置と、上記計算機が利用可能な媒体を介して、他の装置から上記記憶装置に導入されてもよい。媒体とは、たとえば、外部インタフェースに着脱可能な記憶媒体、または通信媒体（すなわち有線、無線、光などのネットワーク、または当該ネットワーク３２０を伝搬する搬送波やディジタル信号）を指す。
【００３８】
相互認証装置Ａ１００と相互認証装置Ｂ２００との間の相互認証は、まず相互認証装置Ａが乱数生成部１３１から乱数ｒＡを得て、外部通信部１３２から相互認証装置Ｂに送信する。乱数ｒＡは通信線３１０、ネットワーク３２０などを経由して外部通信部２３２に送られる。
【００３９】
相互認証装置Ｂは送られた乱数ｒＡに対し、上記手順で署名ｓＢを生成する。さらに乱数生成部２３１から乱数ｒＢを得て、これを一時データ記憶領域２２４に記憶する。さらに上記手順でｒＢを暗号化して暗号文Ｃを計算する。外部通信部２３２はｓＢとＣを相互認証装置Ａに送信する。
【００４０】
相互認証装置Ａは外部通信部１３２を経て得られたｓＢとＣに対し、まずｓＢについて、上記手順で署名検証を行う。この署名を正しいと判断した場合は、相互認証装置Ｂを正しいと判断し、次にＣを上記手順で復号し、復号結果ｒＢ’を再び外部通信部１３２を経て相互認証装置Ｂに送信する。署名を正しいと判断しない場合は相互認証装置Ｂを正しいと判断しない。
【００４１】
相互認証装置Ｂは、外部通信部２３２を経て受信したｒＢ’と一時データ記憶領域２２４から読み出したｒＢとを比較して一致していれば相互認証装置Ａを正しいと判断する。一致していなければ相互認証装置Ａを正しいと判断しない。
【００４２】
上記相互認証で用いる署名方法は、署名生成において署名対象のデータが入力される前に事前計算をすることにより署名対象データが入力された際の処理量を削減できる方法ならば何でも良い。また、上記相互認証方法で用いる公開鍵暗号方法は、暗号化において暗号化対象のデータが入力される前に事前計算をすることにより暗号化対象データが入力された際の処理量を削減できる方法ならば何でも良い。
【００４３】
図２は署名方法の例として楕円シュノア署名（非特許文献３参照）を用いた場合の相互認証の署名利用部分の処理を示すシーケンス図である。
【００４４】
楕円シュノア署名に適した楕円曲線上の有理点Ｐが固定されていて、相互認証装置Ａ１００の署名検証鍵記憶領域１２１と、相互認証装置Ｂ２００の署名生成鍵記憶領域に記憶されている。相互認証装置Ｂ２００の秘密鍵（Private key）ｘは署名生成鍵記憶領域２２１に記憶され、公開鍵Ｑ＝ｘＰは署名検証鍵記憶領域１２１に記憶されている。
【００４５】
まず相互認証装置Ｂ２００側の事前計算として、署名生成鍵記憶領域から有理点Ｐのデータを読み出し（Ｓ１０）、次に乱数生成部２３１で乱数ｒを生成し、事前データ計算部２１３に送る（Ｓ１１）。事前データ計算部２１３はＲ＝ｒＰを計算し、ｒとＲを事前計算データ記憶領域２２３に記憶させる（Ｓ１２）。
【００４６】
次に、相互認証装置Ａ１００が相互認証装置Ｂを認証する場合、まず、乱数生成部１３１で乱数ｒＡを生成して外部通信部１３２を通じて相互認証装置Ｂ２００に送信する（Ｓ１３）。
【００４７】
相互認証装置Ｂ２００はｒＡを外部通信部２３２を通じて受信した後、事前計算データ記憶領域２２３からｒとＲを読み出し（Ｓ１４）、また署名生成鍵記憶領域２２１から署名生成鍵ｘを読み出す（Ｓ１５）。
【００４８】
署名生成部２１１は、Ｓ＝ｒ＋Ｈ（ｒＡ，Ｒ）を計算する。ここでＨはハッシュ関数である。相互認証装置Ｂ２００は［Ｒ，Ｈ（ｒＡ，Ｒ）、Ｓ］をｒＡに対する署名値として外部通信部２３２を通じて相互認証装置Ａ１００に送信する（Ｓ１６）。
【００４９】
署名値［Ｒ，Ｈ（ｒＡ，Ｒ），Ｓ］を外部通信部１３２を通じて受信した相互認証装置Ａ１００は、署名検証部１１１において、まず署名検証鍵記憶領域１２１から相互認証装置Ｂ２００の公開鍵ＱとシステムパラメータＰを読み出し（Ｓ１７）、Ｒ＝ＳＰ＋Ｈ（ｒＡ，Ｒ）Ｑが成立するか否かをチェックする。
【００５０】
成立した場合には相互認証装置Ｂ２００を正しいと判断し、そうでない場合には不正と判断する。
【００５１】
本実施例で用いる署名方法は上記楕円シュノア署名以外にも、署名生成処理において事前計算をすることで署名対象データの入力後の処理が大幅に軽減され、かつ署名として安全であるような方法であれば適用可能である。
【００５２】
図３は公開鍵暗号の例として変形エルガマル暗号を用いた場合の相互認証の公開鍵暗号利用部分の処理を示すシーケンス図である。
【００５３】
変形エルガマル暗号に適した楕円曲線上の有理点Ｐ’が固定されていて、相互認証装置Ｂ２００の公開鍵暗号暗号鍵記憶領域に記憶されている。相互認証装置Ａ１００の秘密鍵（Private key）ｘ’は公開鍵暗号復号鍵記憶領域１２２に記憶され、公開鍵Ｑ’＝ｘ’Ｐ’は公開鍵暗号暗号鍵記憶領域２２２に記憶されている。
【００５４】
まず相互認証装置Ｂ２００側の事前計算として、公開鍵暗号暗号鍵記憶領域２２２から有理点Ｐ’、Ｑ’のデータを読み出し（Ｓ２０）、次に乱数生成部２３１で乱数ｒ１を生成し、事前データ計算部２１３に送る（Ｓ２１）。事前データ計算部２１３はＲ１＝ｒ１Ｐ’と、Ｑ１＝ｒ１Ｑ’と、を計算し、事前計算データ記憶領域２２３に記憶させる（Ｓ２２）。
【００５５】
次に、相互認証装置Ｂ２００が相互認証装置Ａ１００を認証する場合、まず、乱数生成部１３１で乱数ｒ２、ｒＢを生成して公開鍵暗号化部２１２に送る（Ｓ２３）。
【００５６】
また、ｒＢは一時データ記憶領域２２４にも送られ記憶される（Ｓ２４）。
【００５７】
公開鍵暗号暗号化部２１２は公開鍵暗号暗号鍵記憶領域２２２から定数ｃ０を読み出し（Ｓ２６）、共通鍵暗号Ｅを用いてＣ＝Ｅ（Ｑ１，ｃ０｜｜ｒ２｜｜ｒＢ）を計算する。ここで共通鍵暗号Ｅの鍵はＱ１、暗号化対象データはｃ０｜｜ｒ２｜｜ｒＢである。また｜｜はデータの結合を表す。
【００５８】
相互認証装置Ｂ２００は外部通信部２３２を通じて相互認証装置Ａ１００に［Ｒ１，Ｃ］を送信する（Ｓ２７）。
【００５９】
相互認証装置Ａ１００は外部通信部１３２を通じて［Ｒ１，Ｃ］を受信した後、公開鍵暗号復号鍵記憶領域１２２から復号鍵ｘ’を読み出し（Ｓ２８）、Ｑ１＝ｘ’Ｒ１、ｃ０｜｜ｒ２｜｜ｒＢ’＝Ｄ（Ｑ１，Ｃ）を計算する。ここでＤは共通鍵暗号Ｅの復号化関数で、鍵はＱ１、復号化対象データはＣである。
【００６０】
公開鍵暗号復号化部１１２は定数ｃ０が正しいものであることを確認し、正しければｒＢ’を外部通信部１３２を通じて相互認証装置Ｂ２００に送信する（Ｓ２９）。
【００６１】
外部通信部２３２を通じてｒＢ’を受信した相互認証装置Ｂ２００は、一時データ記憶領域２２４からｒＢを読み出し（Ｓ３０）、ｒＢとｒＢ’が一致するならば相互認証装置Ａ１００を正しいと判断し、異なるなら不正と判断する。
【００６２】
本実施例で用いる公開鍵暗号は上記変形エルガマル暗号以外にも、暗号化処理において事前計算をすることで暗号化対象データの入力後の処理が大幅に軽減され、かつ暗号として安全であるような方法であれば適用可能である。
【００６３】
本実施例において、署名を用いた処理部分と、公開鍵暗号を用いた処理部分の順番は入れ替えても良い。
【実施例２】
【００６４】
次に、第二の実施形態である、ＩＣカードなどの低リソースデバイスと比較的計算能力の高いサーバなどとの相互認証の方法について説明する。
【００６５】
例えば図４は、ＩＣカード４００とそのリーダライタ３００の構成図である。これらは通信手段５０１、および５０２を持ち、データの送受信が可能である。通信手段は接触、非接触を問わない。
【００６６】
第一の実施形態における相互認証装置Ａ１００としてリーダライタ３００を、相互認証装置Ｂ２００としてＩＣカード４００を適用する。
【００６７】
ＩＣカード４００の事前データ計算部は通電している間に、以降の想定される相互認証の回数に必要な事前計算を実施して、事前計算データを記憶しても良いし、出荷時などに事前に事前計算データを計算し、記憶領域に保存していても良い。これらの場合、事前計算データの消費を管理しながら、相互認証の度に、毎回、新しい事前計算データを用いればよい。
【００６８】
また、図５で説明するように、各相互認証が正常に終了した段階で信頼したサーバに次回用の事前計算を代理で実行してもらい、計算結果を受信して保存する方法でもよい。
【００６９】
図５は第ｎ回目の相互認証の手順を示すシーケンス図である。
【００７０】
ＩＣカード４００は第ｎ回目の相互認証に必要な事前計算データを記憶している。リーダライタ３００とＩＣカード４００は実施例１に記載の方法で相互認証を行う（Ｓ１３、Ｓ１６、Ｓ２７、Ｓ２９）。ここで通信Ｓ１６とＳ２７は並行して行ってもよい。また、Ｓ１３、Ｓ１６とＳ２７、Ｓ２９の順番を入れ替え、Ｓ２７、Ｓ２９、Ｓ１３、Ｓ１６の順番で通信してもよい。その場合、通信Ｓ２９とＳ１３とを並行して行ってもよい。
リーダライタ３００がＩＣカード４００を正しいと判断し、またＩＣカード４００がリーダライタ３００を正しいと判断した場合、リーダライタ３００はＩＣカード４００の第ｎ＋１回目の認証のために必要な事前計算を代理で実行する。その事前計算データをＩＣカード４００に送信する（Ｓ４０）。
【００７１】
ＩＣカード４００はその事前計算データを事前計算データ記憶領域に記憶させ、第ｎ＋１回目の相互認証時に利用する。
【００７２】
リーダライタ３００が代理で行う事前計算は、事前計算を行う専用の計算機を別途利用しても良い。
【００７３】
相互認証においてどちらか一方が他方を正しいと判断しなかった場合には、その後の処理やサービスを停止してもよいし、再度、相互認証要求をしてもよい。その場合でも、規定の回数の相互認証を行い、全て正しいと判断しなかった場合にはその後の処理やサービスを停止する。
【実施例３】
【００７４】
次に、第三の実施形態である、大量のユーザとの相互認証を同時に行うサーバでの実施形態について説明する。
【００７５】
大量のユーザは、センサネットワークにおける各センサや、スマートグリッドにおいて用いられる、各ユーザの消費電力状況などの情報をサーバに送信する機能を持つタップ（スマートタップ）などでもよい。
【００７６】
図４は、大量のユーザとの相互認証を行うサーバの構成図である。
【００７７】
サーバ６００は、ネットワーク７００を通じて大量のユーザ５００と通信可能である。
【００７８】
第一の実施形態における相互認証装置Ａ１００としてサーバ６００を、相互認証装置Ｂ２００として大量のユーザ５００における各ユーザを適用する。サーバ６００は事前計算を実施する事前計算サーバ９００と通信路８００を通じて通信可能で、事前計算サーバは相互認証装置Ａ１００における事前計算を実施するとしてもよい。
【００７９】
サーバ６００は、ユーザ数や頻度に応じて、必要な回数分の事前計算データを用意する。
【００８０】
実際に、大量ユーザ５００からの相互認証要求がほぼ同時に来た場合、上記事前計算データを用いて、各ユーザ毎に実施例１に記載の方法で相互認証を実施する。
【実施例４】
【００８１】
第四の実施形態である、走行中の車両と、道路に設置された、車両との通信装置（以下、路側機）との相互認証を行う実施形態について説明する。
【００８２】
図７は走行車両１０２０と、路側機１０１０の構成図である。
【００８３】
走行車両１０２０と路側機１０１０は無線通信１０３０によりデータの送受信ができる。
【００８４】
第一の実施形態における相互認証装置Ａ１００として車両１０２０を、相互認証装置Ｂ２００として路側機１０１０を適用する。
【００８５】
路側機１０１０は、通信部１０１１と、相互認証装置Ａ１０１２を備える。
【００８６】
車両１０２０は、通信部１０２１と、相互認証装置Ｂ１０２２を備える。
【００８７】
車両１０２０は、相互認証を実行する前までに実施例１に記載の事前計算データを計算し、相互認証装置Ｂ１０２２内の記憶部に記憶する。
【００８８】
車両１０２０が走行中に、路側機１０１０との無線通信１０３１および１０３２が可能な範囲に近づいたとき、通信を開始し、実施例１に記載の手順で相互認証を実施する。
【００８９】
相互認証の結果、車両１０２０、または路側機１０１０のいずれかが他方を正しいと判断しなかった場合、認証エラーであることを他方に通知し、それ以降に発生した通信内容に従った処理は実行しない。車両１０２０が他の路側機との無線通信が可能な範囲に近づいたときには、再度、相互認証をおこなう。
【符号の説明】
【００９０】
１００：点生成装置、１１１：記憶部、１１２：有理関数記憶領域、１１３：基底記憶領域、１１４：パラメータ記憶領域、１２０：処理部、１２１：有理関数計算部、１２２：有限体演算計算部、１３１：入力部、１３２：出力部、１３３：通信部。

【特許請求の範囲】
【請求項１】
通信でデータの送受信が可能な二種類の装置Ａと装置Ｂを備えるシステムにおいて、前記装置Ａと前記装置Ｂとが互いに相手装置の正当性を確認する相互認証方法であって、
前記装置Ａが、前記装置Ｂの正当性を確認するステップにおいて、
前記装置Ａによる、
認証時に、乱数ｒＡを生成するステップと、
生成した前記乱数ｒＡを前記装置Ｂに送信するステップと、
前記装置Ｂによる、
前記乱数ｒＡを受信した後、記憶する署名生成用事前計算データを利用して、前記乱数ｒＡに対する署名を生成するステップと、
生成した前記署名を前記装置Ａに送信するステップと、
前記装置Ａによる、
前記装置Ｂの署名検証鍵を用いて、受信した前記署名を検証するステップと、
前記署名が正しいと判断すれば前記装置Ｂを正当と判断し、正しくないと判断すれば前記装置Ｂを不当と判断するステップと、を備える
ことを特徴とする相互認証方法。
【請求項２】
請求項１に記載の相互認証方法であって、
相互認証を行う前記装置Ｂが、前記装置Ａの正当性を確認するステップにおいて、
前記装置Ｂによる、
認証時に、乱数ｒＢを生成するステップと、
前記乱数ｒＢを、記憶する暗号化用事前計算データを用いて公開鍵暗号化をするステップと、
前記暗号化の結果である暗号文を前記装置Ａに送信するステップと、
前記装置Ａによる、
前記装置Ａの秘密鍵（Private key）を用いて、受信した前記暗号文を復号化するステップと、
前記復号化結果を前記装置Ｂに送信するステップと、
前記装置Ｂによる、
前記記憶した乱数ｒＢと、前記装置Ａから受信した復号化結果とを照合するステップと、
前記乱数ｒＢと前記復号化結果とが一致していれば前記装置Ａを正当と判断し、一致していなければ前記装置Ａを不当と判断するステップと、を備える
ことを特徴とする相互認証方法。
【請求項３】
請求項１または２に記載の相互認証方法であって、
前記装置Ａと前記装置Ｂとが互いに相手装置を正当と判断した場合、前記暗号化用事前計算データまたは、前記署名生成用事前計算データを、前記装置Ａが計算し、前記装置Ｂに送信する
ことを特徴とする相互認証方法。
【請求項４】
請求項１または３に記載の相互認証方法であって、
前記装置Ａまたは前記装置Ｂによる、前記署名生成用事前計算データを計算するステップとして、
乱数ｒを生成するステップと、
楕円曲線上の点のスカラー倍算Ｒ＝ｒＰを計算するステップと、
前記乱数ｒと前記スカラー倍算結果Ｒを記憶するステップと、を備える
ことを特徴とする相互認証方法。
【請求項５】
請求項２または３に記載の相互認証方法であって、
前記装置Ａまたは前記装置Ｂによる、前記暗号化用事前計算データを計算するステップとして、
乱数ｒ１を生成するステップと、
楕円曲線上の点のスカラー倍算Ｒ１＝ｒ１Ｐ’を計算するステップと、
楕円曲線上の点のスカラー倍算Ｑ１＝ｒ１Ｑ’を計算するステップと、
Ｒ１、Ｑ１を記憶するステップと、を備える
ことを特徴とする相互認証方法。
【請求項６】
請求項４に記載の相互認証方法であって、
前記装置Ａと前記装置Ｂが、楕円曲線上の固定された有理点Ｐと、前記装置Ｂの署名検証鍵であるＱ＝ｘＰと、を記憶し、
前記装置Ｂが、署名生成鍵ｘを記憶し、
前記装置Ｂによる前記乱数ｒＡに対する署名を生成するステップにおいて、
受信した前記乱数ｒＡと、前記スカラー倍算結果Ｒと、に基づき、ハッシュ値Ｈ（ｒＡ，Ｒ）を計算し、Ｓ＝ｒ＋Ｈ（ｒＡ，Ｒ）を計算し、［Ｒ，Ｈ（ｒＡ，Ｒ），Ｓ］を前記乱数ｒＡに対する署名とするステップと、を備え、
前記装置Ａによる受信した前記署名を検証するステップにおいて、
受信した前記署名［Ｒ，Ｈ（ｒＡ，Ｒ），Ｓ］について、前記装置Ｂの署名検証鍵Ｑを用いて、Ｒ＝ＳＰ＋Ｈ（ｒＡ，ｒ）Ｑが成立するかどうかを調べることにより、前記署名［Ｒ，Ｈ（ｒＡ，Ｒ），Ｓ］を検証するステップと、を備える
ことを特徴とする相互認証方法。
【請求項７】
請求項５に記載の相互認証方法であって、
相互認証を行う前記装置Ａと前記装置Ｂが、楕円曲線上の固定された有理点Ｐ’と、前記装置Ａの公開鍵Ｑ’＝ｘ’Ｐ’と、を保持し、
前記装置Ａが、復号化鍵ｘ’を記憶し、
前記装置Ｂによる、前記装置Ａの正当性を確認するステップにおいて、
乱数ｒ２と乱数ｒＢを生成するステップと、
前記装置Ａ、前記装置Ｂが共通に記憶する定数ｃ０、並びに、Ｑ１を鍵とし、および、ｃ０｜｜ｒ２｜｜ｒＢを暗号化対象データとする共通鍵暗号Ｅ、を用いて、Ｃ＝Ｅ（Ｑ１，ｃ０｜｜ｒ２｜｜ｒＢ）を計算するステップと、
［Ｒ１，Ｃ］をＡに送信するステップと、
前記装置Ａによる、
前記装置Ａの復号化鍵ｘ’を用いて、受信した［Ｒ１，Ｃ］について、
Ｑ１＝ｘ’Ｒ１を計算するステップと、
Ｑ１を鍵とし、復号化対象データをＣとする、前記共通鍵暗号Ｅに対応した復号化関数Ｄ、を用いて、ｃ０｜｜ｒ２｜｜ｒＢ’＝Ｄ（Ｑ１，Ｃ）を計算するステップと、
記憶する定数ｃ０と、前記復号結果のｃ０とを照合するステップと、
前記定数ｃ０と前記復号結果ｃ０とが一致していれば、前記ｒＢ’を前記復号化結果とするステップと、を備える
ことを特徴とする相互認証方法。
【請求項８】
請求項１から７のいずれか一に記載の相互認証方法であって、
前記システムは、さらに、前記装置Ｂと通信可能な装置Ｂ’を備え、
前記装置Ｂ’による、
請求項４に記載の署名生成用事前計算データを計算するステップ、または、請求項５に記載の暗号化用事前計算データを計算するステップと、
計算した前記署名生成用事前計算データ、または、前記暗号化用事前計算データを、前記装置Ｂに送信するステップと、を備える
ことを特徴とする相互認証方法。
【請求項９】
請求項１から７のいずれか一に記載の相互認証方法であって、
前記システムは、複数の前記装置Ａを備え、
１つの前記装置Ａと、前記装置Ｂとの相互認証において、前記装置Ａおよび／または前記装置Ｂを不当と判断した場合に、前記装置Ｂと他の前記装置Ａとによる、請求項１または請求項２に記載のステップを実行するステップを備える
ことを特徴とする相互認証方法。
【請求項１０】
通信でデータの送受信が可能な二種類の装置Ａと装置Ｂを備え、前記装置Ａと前記装置Ｂとが互いに相手装置の正当性を確認する相互認証システムであって、
前記装置Ａは、
乱数ｒＡを生成する手段と、
生成した前記乱数ｒＡを前記装置Ｂに送信する手段と、
前記装置Ｂの署名検証鍵を用いて、前記装置Ｂが生成した署名を検証する手段と、
前記署名が正しいと判断すれば前記装置Ｂを正当と判断し、正しくないと判断すれば前記装置Ｂを不当と判断する手段と、を備え、
前記装置Ｂは、
記憶する署名生成用事前計算データを利用して、前記装置Ａから受信した前記乱数ｒＡに対する署名を生成する手段と、
生成した前記署名を前記装置Ａに送信する手段と、を備える
ことを特徴とする相互認証システム。
【請求項１１】
請求項１０に記載の相互認証システムであって、
前記装置Ｂは、
乱数ｒＢを生成する手段と、
前記乱数ｒＢを、記憶する暗号化用事前計算データを用いて公開鍵暗号化をする手段と、
前記暗号化の結果である暗号文を前記装置Ａに送信する手段と、
前記乱数ｒＢと、前記装置Ａから受信した復号化結果とを照合する手段と、
前記乱数ｒＢと前記復号化結果とが一致していれば前記装置Ａを正当と判断し、一致していなければ前記装置Ａを不当と判断する手段と、を備え、
前記装置Ａは、
前記装置Ａの秘密鍵（Private key）を用いて、受信した前記暗号文を復号化して前記復号化結果とする手段と、
前記復号化結果を前記装置Ｂに送信する手段と、を備える
ことを特徴とする相互認証システム。
【請求項１２】
通信でデータの送受信が可能な二つのコンピュータＡとコンピュータＢに、互いに相手コンピュータの正当性を確認する相互認証システムを実現させるプログラムであって、
前記コンピュータＡが、前記コンピュータＢの正当性を確認するステップとして、
前記コンピュータＡに、
乱数ｒＡを生成するステップと、
生成した前記乱数ｒＡを前記コンピュータＢに送信するステップと、
前記コンピュータＢの署名検証鍵を用いて、前記コンピュータＢが生成した署名を検証するステップと、
前記署名が正しいと判断すれば前記コンピュータＢを正当と判断し、正しくないと判断すれば前記コンピュータＢを不当と判断するステップと、を実行させ、
前記コンピュータＢに、
記憶する署名生成用事前計算データを利用して、前記コンピュータＡから受信した前記乱数ｒＡに対する署名を生成するステップと、
生成した前記署名を前記コンピュータＡに送信するステップと、を実行させる
ことを特徴とするプログラム。
【請求項１３】
請求項１２に記載のプログラムであって、
前記コンピュータＢが、前記コンピュータＡの正当性を確認するステップとして、
前記コンピュータＢに、
乱数ｒＢを生成するステップと、
前記乱数ｒＢを、記憶する暗号化用事前計算データを用いて公開鍵暗号化をするステップと、
前記暗号化の結果である暗号文を前記コンピュータＡに送信するステップと、
前記乱数ｒＢと、前記コンピュータＡから受信した復号化結果とを照合するステップと、
前記乱数ｒＢと前記復号化結果とが一致していれば前記コンピュータＡを正当と判断し、一致していなければ前記コンピュータＡを不当と判断するステップと、を実行させ、
前記コンピュータＡに、
前記コンピュータＡの秘密鍵（Private key）を用いて、受信した前記暗号文を復号化して前記復号化結果とするステップと、
前記復号化結果を前記コンピュータＢに送信するステップと、を実行させる
ことを特徴とするプログラム。

【図１】