認証方法、認証システム、プログラムおよび共有鍵生成方法
【課題】検証者側内部状態が攻撃者に漏洩する、または証明者側の端末が攻撃者の支配下に置かれるという環境において、短いパスワードが漏洩しない認証方法を提供する。
【解決手段】証明者端末は、乱数Ｂを生成し、識別子ＩとパスワードＡが入力されると、検証者装置にＩを送信する。検証者装置は、乱数Ｄを生成して証明者端末に送信し、証明者端末は、Ｒ＝Ｈ（Ｄ）、Ｙ＝ＧＡＲＢを計算し、Ｙを検証者装置に送信する。さらに、証明者端末は、識別子ＩとパスワードＡが入力されると、検証者装置にＩを送信する。検証者装置は、Ｒ＝Ｈ（Ｄ）を計算し、乱数ｕを生成して、Ｓ＝Ｇｕ，Ｔ＝Ｒｕ、証明情報πを計算して、証明者端末にＳ，Ｔ，πを送信する。証明者端末は、πを検証し、検証が合格であればＸ＝ＳＡＴＢを計算し、乱数Ｍを生成し、Ｖ＝ｈ（Ｘ，Ｍ）を計算して、（Ｖ，Ｍ）を検証者装置に送信する。検証者装置は、Ｖ＝ｈ（Ｙｕ，Ｍ）を確認する。
【解決手段】証明者端末は、乱数Ｂを生成し、識別子ＩとパスワードＡが入力されると、検証者装置にＩを送信する。検証者装置は、乱数Ｄを生成して証明者端末に送信し、証明者端末は、Ｒ＝Ｈ（Ｄ）、Ｙ＝ＧＡＲＢを計算し、Ｙを検証者装置に送信する。さらに、証明者端末は、識別子ＩとパスワードＡが入力されると、検証者装置にＩを送信する。検証者装置は、Ｒ＝Ｈ（Ｄ）を計算し、乱数ｕを生成して、Ｓ＝Ｇｕ，Ｔ＝Ｒｕ、証明情報πを計算して、証明者端末にＳ，Ｔ，πを送信する。証明者端末は、πを検証し、検証が合格であればＸ＝ＳＡＴＢを計算し、乱数Ｍを生成し、Ｖ＝ｈ（Ｘ，Ｍ）を計算して、（Ｖ，Ｍ）を検証者装置に送信する。検証者装置は、Ｖ＝ｈ（Ｙｕ，Ｍ）を確認する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エンティティの同一性を認証する技術、または同一のエンティティ間に限り秘密鍵を共有する技術に関する。
【背景技術】
【０００２】
ネットワークサービスにサービス提供者と利用者があり、提供者がサービスを実施するときに、利用者が提供者に対して、利用者にはサービスの提供を受ける権利があることを証明するためのシステムを考える。そのためには、利用者は、サービス利用の権利が発生した時に、利用者を識別する情報と、その利用者のみが知る秘密情報の組を提供者に登録し、サービスが実施される際には、実施に先立ち、利用者は、利用者を識別する情報を提示し、さらに登録時に用いた秘密情報を知っていることを証明する方法をとることができる。
【０００３】
以下では、サービス利用者を証明者、サービス提供者を検証者と呼ぶことにする。また、利用者を識別する情報を識別子と呼び、利用者のみが知る秘密情報をパスワードと呼ぶ。上記認証方法をパスワード認証方法と呼び、うち登録部分の手続きをパスワード登録、証明部分をパスワード認証と呼ぶこととする。パスワード認証方法を実現するシステムに対する攻撃とは、パスワードを知らない攻撃者が何らかの手段を講じた後に、検証者と通信することで、パスワードを知る証明者になり済ますことができることをいう。攻撃が困難なシステムを安全と呼ぶ。
【０００４】
パスワード認証方法を実現する自明なシステムの構成例は、次の通りである。あらかじめ一方向関数ｈの仕様を定め、検証者と証明者で合意してあると仮定する。
（パスワード登録）
証明者は、パスワードｐを一定のパスワード集合Ｐから任意に選び、秘密裏に記録する。証明者は、識別子ｉとｓ＝ｈ（ｐ）を検証者に送信し、検証者は（ｉ，ｓ）を記録する。
（パスワード認証）
証明者は、識別子ｉとパスワードｐを検証者に送信する。検証者はｈ（ｐ）を計算し、あらかじめ記録された情報（ｉ，ｓ）と照合する。
【０００５】
このようなシステムにおいては、パスワード集合が小さい場合に安全性に問題が生じる場合がある。たとえば銀行ＡＴＭや携帯端末におけるネットワークサービスなどでは、パスワード集合Ｐが１０進４桁の数であることが要請される場合がある。
攻撃者にとって検証者に蓄積された情報（ｉ，ｓ）を取得可能な攻撃環境を想定するとき、パスワード集合Ｐが十分小さければ、攻撃者は総当たり攻撃によってパスワードを推測することができる。このように可能性がある秘密情報を全数試行する攻撃手法を、辞書攻撃と呼ぶ。上記システムは、攻撃者がサーバの内部情報を知ることができる攻撃環境の下で、パスワードについての辞書攻撃に対して安全ではない。このようなシステムにおいては、検証者側の内部情報が漏洩する攻撃環境において、パスワードが推測可能である。
【０００６】
この課題を克服した従来技術に、ゼロ知識証明を用いた認証がある。ゼロ知識証明を用いた認証方法は、たとえば特許文献１に具体例が記載されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平９−５１３３０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来技術のゼロ知識証明を用いた認証においては、証明者側の端末が攻撃者の支配下に置かれるという環境において、短いパスワードが漏洩するという安全性の課題がある。パスワードの知識を証明する従来技術のゼロ知識証明を用いた場合、証明者の端末の乱数源を制御可能な攻撃環境において、秘密情報を抽出することができるという課題がある。また、ゼロ知識証明を用いた認証方法は複雑であるから、ゼロ知識証明を用いない認証方法と比較して、実装の手間や費用、実施に要する時間や費用が大きいという課題がある。
【０００９】
本発明は、このような課題に鑑みてなされたものであり、本発明の目的は、検証者側内部状態が攻撃者に漏洩する、または証明者側の端末が攻撃者の支配下に置かれるという環境において、短いパスワードが漏洩しない認証の技術を提供することにある。
【課題を解決するための手段】
【００１０】
本発明は、ゼロ知識証明で、証明者端末の内部情報を取得する攻撃環境や、証明者端末の内部の疑似乱数源を制御される攻撃環境で、パスワードが漏洩しないものを用いるものである。また、そのようなゼロ知識証明を利用した認証方法で、検証者と証明者の間の交信は一往復であるものを用いることで、実装の手間や費用、実施に要する時間や費用が大きくなる課題を解決するものである。
【００１１】
上記課題を解決するため、本発明の認証方法は、証明者端末にて証明者からの識別子ＩとパスワードＡを受け付けて、検証者装置によって当該証明者を認証する方法であって、前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、前記証明者端末は、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持しており、前記検証者装置は、前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶しており、前記証明者端末が、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信するステップと、前記検証者装置が、識別子Ｉを受信して、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、前記証明者端末が、前記第１の値Ｓと前記第２の値Ｔを受信して、前記第１の値Ｓと、前記パスワードＡと、前記第２の値Ｔと、前記第１の任意数Ｂとから定まる第２のパラメータＸを算出するとともに、該第２のパラメータＸと当該証明者端末によって生成した第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信するステップと、前記検証者装置が、値Ｖと第４の任意数Ｍを受信して、前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証するステップとを含むことを特徴とする。
【００１２】
本発明の認証方法は、前記検証者装置が、前記第１の値Ｓかつ前記第２の値Ｔとなる前記第３の任意数ｕの非対話的ゼロ知識証明となる証明情報πを算出し、算出した証明情報πを前記証明者端末に送信するステップと、前記証明者端末が、前記証明情報πを受信し、証明情報πを検証するステップとを更に含むことが好ましい。
【００１３】
また、前記第１関数Ｈは、ハッシュ関数であって、値Ｒは、Ｒ＝Ｈ（Ｄ）で表され、前記第１パラメータＹは、Ｙ＝ＧＡＲＢで表され、前記第１の値Ｓは、Ｓ＝Ｇｕで表され、前記第２の値Ｔは、Ｔ＝Ｒｕで表され、前記第２のパラメータＸは、Ｘ＝ＳＡＴＢで表され、前記第２関数ｈは、ハッシュ関数であって、前記証明者端末が算出する値Ｖは、Ｖ＝ｈ（Ｘ，Ｍ）で表され、前記検証者装置が算出する値Ｖは、Ｖ＝ｈ（Ｙｕ，Ｍ）で表され、前記証明情報πは、任意数ｗとし、ｎをＧの位数としたとき、π＝（ｚ，ｃ）（ここに、Ｗ１＝Ｇｗ、Ｗ２＝Ｒｗ、ｃ＝ｈ（Ｗ１，Ｗ２）、ｚ＝−ｃｕ＋ｗ（ｍｏｄ ｎ））で表され、前記検証するステップは、ｈ（ＧｚＳｃ，ＲｚＴｃ）＝ｃを満たすか否かで検証することが好ましい。
【００１４】
また、本発明の認証システムは、証明者端末にて証明者からの識別子ＩとパスワードＡを受け付けて、検証者装置によって当該証明者を認証する認証システムであって、前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、前記証明者端末が、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持する手段と、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信する手段と、前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信する手段と、受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信する手段とを備え、前記検証者装置が、前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶する手段と、前記証明者端末から、証明者の識別子Ｉを受信する手段と、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信する手段と、前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信する手段と、前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証する
手段とを備えることを特徴とする。
【００１５】
また、本発明の証明者端末は、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持する手段と、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信する手段と、前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信する手段と、受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信する手段とを備えることを特徴とする。
【００１６】
また、本発明の検証者装置は、前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶する手段と、前記証明者端末から、証明者の識別子Ｉを受信する手段と、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信する手段と、前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信する手段と、前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証する手段とを備えることを特徴とする。
【００１７】
また、本発明は、コンピュータに前記認証システムの証明者端末の機能を実現させるプログラムであって、証明者からの識別子ＩとパスワードＡの入力を受け付けて、検証者装置に識別子Ｉを送信するステップと、前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信するステップと、受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信するステップとを実行させるためのプログラムである。
【００１８】
また、本発明は、コンピュータに前記認証システムの検証者装置の機能を実現させるプログラムであって、前記証明者端末から、証明者の識別子Ｉを受信するステップと、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信するステップと、前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証するステップとを実行させるためのプログラムである。
【００１９】
また、本発明の共有鍵生成方法は、証明者端末と検証者装置の双方において使用される共有鍵を生成する共有鍵生成方法であって、前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、前記証明者端末は、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、証明者から受け付けたパスワードＡと、前記巡回群の値Ｇとを保持しており、前記検証者装置は、証明者の識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶しており、前記証明者端末が、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信するステップと、前記検証者装置が、識別子Ｉを受信して、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、前記証明者端末が、前記第１の値Ｓと前記第２の値Ｔを受信して、前記第１の値Ｓと、前記パスワードＡと、前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、証明者端末によって生成した第４の任意数Ｍ１を第２のパラメータＸで暗号化して値Ｖ１を算出し、算出した値Ｖ１を前記検証者装置に送信するステップと、前記検証者装置が、値Ｖ１を受信して、値Ｖ１を前記第１のパラメータＹと第３の任意数ｕで定まる第３の値で復号化して値Ｍ１を算出し、値Ｍ１と検証者装置によって生成した第５の任意数Ｍ２とをビット結合したものを前記第３の値で暗号化して値Ｖ２を算出し、算出した値Ｖ２を前記検証者装置に送信するステップと、前記証明者端末が、値Ｖ２を受信して、値Ｖ２を前記第２のパラメータＸで復号化して値Ｍを算出し、値Ｍが第５の任意数Ｍ２によって分解できるかどうかを確認し、分解できれば第５の任意数Ｍ２を第２のパラメータＸで暗号化して値Ｖ３を算出し、前記検証者装置に値Ｖ３を送信し、値Ｍ１と第５の任意数
Ｍ２とをビット結合したもので定まる第２関数ｈの値を共有鍵Ｋとするステップと、前記検証者装置が、値Ｖ３を受信して、値Ｖ３を前記第３の値で復号化して値Ｍ２を算出し、算出した値Ｍ２を用いて、前記第５の任意数Ｍ２を検証し、検証が成功であれば値Ｍ１と第５の任意数Ｍ２とをビット結合したもので定まる第２関数ｈの値を共有鍵Ｋとするステップとを含むことを特徴とする。
【００２０】
また、前記第１関数Ｈは、ハッシュ関数であって、値Ｒは、Ｒ＝Ｈ（Ｄ）で表され、前記第１パラメータＹは、Ｙ＝ＧＡＲＢで表され、前記第１の値Ｓは、Ｓ＝Ｇｕで表され、前記第２の値Ｔは、Ｔ＝Ｒｕで表され、前記第２のパラメータＸは、Ｘ＝ＳＡＴＢで表され、前記第４の任意数Ｍ１を第２のパラメータＸで暗号化して算出する値Ｖ１は、Ｖ１＝ＥＸ（Ｍ１）で表され、前記値Ｖ１を前記第３の値で復号化して算出する値Ｍ１は、
【数１】
で表され、前記値Ｍ１と前記第５の任意数Ｍ２とをビット結合したものを前記第３の値で暗号化して算出する値Ｖ２は、
【数２】
で表され、前記第５の任意数Ｍ２を前記第２のパラメータＸで暗号化して算出する値Ｖ３は、Ｖ３＝ＥＸ（Ｍ２）で表され、前記値Ｖ３を前記第３の値で復号化して算出する値Ｍ２は、
【数３】
で表され、前記第２関数ｈは、ハッシュ関数であることが好ましい。
【発明の効果】
【００２１】
本発明は、パスワードの知識を証明する認証方法において、証明者の内部情報が漏洩する攻撃環境や、証明者端末の内部情報を取得する攻撃環境や、証明者端末の内部の疑似乱数源を制御される攻撃環境における安全性を向上させることができる。また、証明者の内部情報が漏洩する攻撃環境における安全性を向上させた認証方法において、実装の手間や費用、実施に要する時間や費用を少なくすることができる。
【図面の簡単な説明】
【００２２】
【図１】証明者端末と検証者装置の構成図である。
【図２】設定段階における証明者端末と検証者装置の動作を説明するフローチャートである。
【図３】認証段階における証明者端末と検証者装置の動作を説明するフローチャートである。
【図４】共通鍵を求めるときの証明者端末と検証者装置の動作を説明するフローチャートである。
【発明を実施するための形態】
【００２３】
本発明の実施の形態について図面を参照して説明する。以下において、ｋをセキュリティパラメータとして、〈Ｇ〉を離散対数問題がｋに応じて困難である巡回群で元Ｇによって生成されるものとする。たとえば楕円エルガマル暗号で用いられる群などが好適である。以下、このような巡回群の暗号を用いる任意の点Ｇを単に巡回群の値Ｇと称する。
ｈ：｛０，１｝＊→｛０，１｝２ｋおよびＨ：｛０，１｝＊→〈Ｇ〉をハッシュ関数とする。
【００２４】
（第１の実施の形態）
第１の実施の形態は、証明者がパスワードを入力するための装置を備えた証明者端末と、検証者装置の間で実施される。実施される方式は、設定と認証の２段階からなる。
図１は、証明者端末と検証者装置の構成図である。証明者端末１０は、証明者からのデータ入力を受け付ける入力部１１と、検証者装置と通信を行う送受信部１２と、制御部１３と、各種演算を行う演算部１４と、乱数を生成する乱数生成部１５と、安全補強情報を蓄積するための静的記憶装置１６を備える。このような認証者端末には、ＩＣカードや、携帯端末、あるいは携帯端末上で動作する仮想マシンを想定することができる。
検証者装置２０は、証明者端末と通信を行う送受信部２２と、制御部２３と、各種演算を行う演算部２４と、乱数を生成する乱数生成部２５と、証明者の識別子と証明者の認証に用いる認証情報との組を記録する静的記憶装置２６を備える。このような検証者装置には一般的なＰＣやサーバなどを想定することができる。
なお、証明者端末１０と検証者装置２０は、予めｈおよびＨのハッシュ関数の仕様と、Ｇや巡回群の計算を行うために必要な情報、Ｇの位数を共有する。適切な巡回群の例としては、たとえば楕円曲線が考えられる。したがって、双方の装置は、楕円曲線を用いる場合、楕円パラメータと楕円の点Ｇの座標（ｘ，ｙ）の値、およびＧの位数を共有している。
【００２５】
図２は、設定段階における証明者端末と検証者装置の動作を説明するフローチャートである。設定段階において、証明者端末と検証者装置は次のようにふるまう。
証明者端末１０は、乱数生成部１５において２ｋビットの乱数Ｂを生成し、記憶装置１６に記憶する（Ｓ１００）。次に、入力部１１から証明者の識別子とパスワードの入力を受け付ける（Ｓ１０１）。識別子をＩ、パスワードをＡとする。次に、送受信部１２から検証者装置２０に識別子Ｉを送信する（Ｓ１０２）。
検証者装置２０は、送受信部２２を介して証明者端末１０から識別子Ｉを受信すると（Ｓ１０３）、乱数生成部２５において２ｋビットの乱数Ｄを生成し（Ｓ１０４）、生成された乱数Ｄを証明者端末１０に送信する（Ｓ１０５）。
証明者端末１０は、検証者装置２０から値Ｄを受信すると（Ｓ１０６）、演算部１４においてハッシュ値Ｒ＝Ｈ（Ｄ）、Ｙ＝ＧＡＲＢを計算し（Ｓ１０７）、計算して得られた値Ｙを検証者装置２０に送信する（Ｓ１０８）。
検証者装置２０は、証明者端末１０から値Ｙを受信すると（Ｓ１０９）、（Ｉ，Ｙ，Ｄ）を記憶装置２６に記憶する（Ｓ１１０）。
【００２６】
図３は、認証段階における証明者端末と検証者装置の動作を説明するフローチャートである。認証段階において、証明者端末と検証者装置は次のようにふるまう。
証明者端末１０は、入力部１１から証明者の識別子とパスワードの入力を受け付ける（Ｓ２００）。識別子をＩ、パスワードをＡとする。次に、送受信部１２から検証者装置２０に識別子Ｉを送信する（Ｓ２０１）。
検証者装置２０は、送受信部２２を介して証明者端末１０から識別子Ｉを受信すると（Ｓ２０２）、記憶装置２６から（Ｉ，Ｙ，Ｄ）を読み出し、演算部２４においてハッシュ値Ｒ＝Ｈ（Ｄ）を計算する（Ｓ２０３）。次に、乱数生成部２５において２ｋビットの乱数ｕを生成し（Ｓ２０４）、演算部２４においてＳ＝Ｇｕ，Ｔ＝Ｒｕを計算し、証明情報πを計算する（Ｓ２０５）。次に、送受信部２２から証明者端末１０にＳ，Ｔ，πを送信する（Ｓ２０６）。
証明者端末１０は、検証者装置２０から値ＳおよびＴ、証明情報πを受信すると（Ｓ２０７）、制御部１３において証明情報πを検証し（Ｓ２０８）、検証に不合格であれば処理を中止する。検証に合格すれば、記憶装置１６から値Ｂを読み出し、演算部１４においてＸ＝ＳＡＴＢを計算する（Ｓ２０９）。次に、乱数生成部１５においてｋビットの乱数Ｍを生成し（Ｓ２１０）、演算部１４においてハッシュ値Ｖ＝ｈ（Ｘ，Ｍ）を計算する（Ｓ２１１）。計算して得られた（Ｖ，Ｍ）を検証者装置２０に送信する（Ｓ２１２）。
検証者装置２０は、証明者端末１０から（Ｖ，Ｍ）を受信すると（Ｓ２１３）、制御部２３においてＶ＝ｈ（Ｙｕ，Ｍ）を確認する（Ｓ２１４）。Ｖ＝ｈ（Ｙｕ，Ｍ）であれば認証合格のメッセージを出力する（Ｓ２１５）。それ以外の場合は機能を停止する。
【００２７】
証明情報πの計算と検証は、Ｓ＝ＧｕかつＴ＝Ｒｕとなる数ｕの知識に関する非対話的ゼロ知識証明である。一例を次に述べる。πの計算のためには、２ｋビットの乱数ｗを生成し、Ｗ１＝Ｇｗ，Ｗ２＝Ｒｗ、ｃ＝ｈ（Ｗ１，Ｗ２）、ｚ＝−ｃｕ＋ｗ（ｍｏｄ ｎ）を計算し、π＝（ｚ，ｃ）とする。ただしｎはＧの位数である。π＝（ｚ，ｃ）の検証のためには、ｈ（ＧＺＳＣ，ＲＺＴＣ）＝ｃを満たすことを確認する。
【００２８】
（第２の実施の形態）
認証段階の後半を置き換えることで共通鍵生成方法として機能する。ＥＫ（Ｍ）は共通鍵暗号の暗号化を表し、ＤＫ（Ｃ）は共通鍵暗号の復号化を表すものとする。ただしＫは鍵、Ｍは平文、Ｃは暗号文である。
第１の実施の形態を共通鍵生成方法に変形すると、図４の通りである。登録段階と証明情報に関する手続は同様である。認証段階において、証明者端末と検証者装置は次のようにふるまう。
【００２９】
証明者端末１０は、入力部１１から証明者の識別子とパスワードの入力を受け付ける（Ｓ３００）。識別子をＩ、パスワードをＡとする。次に、送受信部１２から検証者装置２０に識別子Ｉを送信する（Ｓ３０１）。
検証者装置２０は、送受信部２２を介して証明者端末１０から識別子Ｉを受信すると（Ｓ３０２）、記憶装置２６から（Ｉ，Ｙ，Ｄ）を読み出し、演算部２４においてハッシュ値Ｒ＝Ｈ（Ｄ）を計算する（Ｓ３０３）。次に、乱数生成部２５において２ｋビットの乱数ｕを生成し（Ｓ３０４）、演算部２４においてＳ＝Ｇｕ，Ｔ＝Ｒｕを計算し、証明情報πを計算する（Ｓ３０５）。次に、送受信部２２から証明者端末１０にＳ，Ｔ，πを送信する（Ｓ３０６）。
【００３０】
証明者端末１０は、検証者装置２０から値ＳおよびＴ、証明情報πを受信すると（Ｓ３０７）、制御部１３において証明情報πを検証し（Ｓ３０８）、検証に不合格であれば処理を中止する。検証に合格すれば、記憶装置１６から値Ｂを読み出し、演算部１４においてＸ＝ＳＡＴＢを計算する（Ｓ３０９）。次に、乱数生成部１５においてｋビットの乱数Ｍ１を生成し（Ｓ３１０）、演算部１４においてＸを鍵としてＶ１＝ＥＸ（Ｍ１）を計算する（Ｓ３１１）。計算して得られたＶ１を検証者装置２０に送信する（Ｓ３１２）。
検証者装置２０は、証明者端末１０からＶ１を受信すると（Ｓ３１３）、演算部２４においてＹｕを鍵として
【数４】
を計算する（Ｓ３１４）。次に、乱数生成部２５においてｋビットの乱数Ｍ２を生成し（Ｓ３１５）、演算部２４においてＹｕを鍵として
【数５】
を計算する（Ｓ３１６）。計算して得られたＶ２を証明者端末１０に送信する（Ｓ３１７）。
【００３１】
証明者端末１０は、Ｖ２を検証者装置２０から受信すると（Ｓ３１８）、演算部１４においてＸを鍵としてＭ＝ＤＸ（Ｖ２）を計算する（Ｓ３１９）。次に、制御部１３において、ある文字列Ｍ２によってＭ＝Ｍ１｜Ｍ２と分解できるかどうかを確かめる（Ｓ３２０）。分解できなければ機能を停止する。なお、Ｍ１｜Ｍ２とは、Ｍ１とＭ２とをビット結合することを意味する。分解できたならば演算部１４においてＶ３＝ＥＸ（Ｍ２）を計算する（Ｓ３２１）。計算して得られたＶ３を検証者装置２０に送信する（Ｓ３２２）。そして、共有鍵をＫ＝ｈ（Ｍ１｜Ｍ２）とする（Ｓ３２３）。
検証者装置２０は、証明者端末１０からＶ３を受信すると（Ｓ３２４）、制御部２３において
【数６】
であることを確認する（Ｓ３２５）。確認できなければ、機能を停止する。確認できたならば、共有鍵をＫ＝ｈ（Ｍ１｜Ｍ２）とする（Ｓ３２６）。
【符号の説明】
【００３２】
１０ 証明者端末
１１ 入力部
１２，２２ 送受信部
１３，２３ 制御部
１４，２４ 演算部
１５，２５ 乱数生成部
１６，２６ 記憶装置
２０ 検証者装置
【技術分野】
【０００１】
本発明は、エンティティの同一性を認証する技術、または同一のエンティティ間に限り秘密鍵を共有する技術に関する。
【背景技術】
【０００２】
ネットワークサービスにサービス提供者と利用者があり、提供者がサービスを実施するときに、利用者が提供者に対して、利用者にはサービスの提供を受ける権利があることを証明するためのシステムを考える。そのためには、利用者は、サービス利用の権利が発生した時に、利用者を識別する情報と、その利用者のみが知る秘密情報の組を提供者に登録し、サービスが実施される際には、実施に先立ち、利用者は、利用者を識別する情報を提示し、さらに登録時に用いた秘密情報を知っていることを証明する方法をとることができる。
【０００３】
以下では、サービス利用者を証明者、サービス提供者を検証者と呼ぶことにする。また、利用者を識別する情報を識別子と呼び、利用者のみが知る秘密情報をパスワードと呼ぶ。上記認証方法をパスワード認証方法と呼び、うち登録部分の手続きをパスワード登録、証明部分をパスワード認証と呼ぶこととする。パスワード認証方法を実現するシステムに対する攻撃とは、パスワードを知らない攻撃者が何らかの手段を講じた後に、検証者と通信することで、パスワードを知る証明者になり済ますことができることをいう。攻撃が困難なシステムを安全と呼ぶ。
【０００４】
パスワード認証方法を実現する自明なシステムの構成例は、次の通りである。あらかじめ一方向関数ｈの仕様を定め、検証者と証明者で合意してあると仮定する。
（パスワード登録）
証明者は、パスワードｐを一定のパスワード集合Ｐから任意に選び、秘密裏に記録する。証明者は、識別子ｉとｓ＝ｈ（ｐ）を検証者に送信し、検証者は（ｉ，ｓ）を記録する。
（パスワード認証）
証明者は、識別子ｉとパスワードｐを検証者に送信する。検証者はｈ（ｐ）を計算し、あらかじめ記録された情報（ｉ，ｓ）と照合する。
【０００５】
このようなシステムにおいては、パスワード集合が小さい場合に安全性に問題が生じる場合がある。たとえば銀行ＡＴＭや携帯端末におけるネットワークサービスなどでは、パスワード集合Ｐが１０進４桁の数であることが要請される場合がある。
攻撃者にとって検証者に蓄積された情報（ｉ，ｓ）を取得可能な攻撃環境を想定するとき、パスワード集合Ｐが十分小さければ、攻撃者は総当たり攻撃によってパスワードを推測することができる。このように可能性がある秘密情報を全数試行する攻撃手法を、辞書攻撃と呼ぶ。上記システムは、攻撃者がサーバの内部情報を知ることができる攻撃環境の下で、パスワードについての辞書攻撃に対して安全ではない。このようなシステムにおいては、検証者側の内部情報が漏洩する攻撃環境において、パスワードが推測可能である。
【０００６】
この課題を克服した従来技術に、ゼロ知識証明を用いた認証がある。ゼロ知識証明を用いた認証方法は、たとえば特許文献１に具体例が記載されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平９−５１３３０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来技術のゼロ知識証明を用いた認証においては、証明者側の端末が攻撃者の支配下に置かれるという環境において、短いパスワードが漏洩するという安全性の課題がある。パスワードの知識を証明する従来技術のゼロ知識証明を用いた場合、証明者の端末の乱数源を制御可能な攻撃環境において、秘密情報を抽出することができるという課題がある。また、ゼロ知識証明を用いた認証方法は複雑であるから、ゼロ知識証明を用いない認証方法と比較して、実装の手間や費用、実施に要する時間や費用が大きいという課題がある。
【０００９】
本発明は、このような課題に鑑みてなされたものであり、本発明の目的は、検証者側内部状態が攻撃者に漏洩する、または証明者側の端末が攻撃者の支配下に置かれるという環境において、短いパスワードが漏洩しない認証の技術を提供することにある。
【課題を解決するための手段】
【００１０】
本発明は、ゼロ知識証明で、証明者端末の内部情報を取得する攻撃環境や、証明者端末の内部の疑似乱数源を制御される攻撃環境で、パスワードが漏洩しないものを用いるものである。また、そのようなゼロ知識証明を利用した認証方法で、検証者と証明者の間の交信は一往復であるものを用いることで、実装の手間や費用、実施に要する時間や費用が大きくなる課題を解決するものである。
【００１１】
上記課題を解決するため、本発明の認証方法は、証明者端末にて証明者からの識別子ＩとパスワードＡを受け付けて、検証者装置によって当該証明者を認証する方法であって、前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、前記証明者端末は、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持しており、前記検証者装置は、前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶しており、前記証明者端末が、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信するステップと、前記検証者装置が、識別子Ｉを受信して、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、前記証明者端末が、前記第１の値Ｓと前記第２の値Ｔを受信して、前記第１の値Ｓと、前記パスワードＡと、前記第２の値Ｔと、前記第１の任意数Ｂとから定まる第２のパラメータＸを算出するとともに、該第２のパラメータＸと当該証明者端末によって生成した第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信するステップと、前記検証者装置が、値Ｖと第４の任意数Ｍを受信して、前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証するステップとを含むことを特徴とする。
【００１２】
本発明の認証方法は、前記検証者装置が、前記第１の値Ｓかつ前記第２の値Ｔとなる前記第３の任意数ｕの非対話的ゼロ知識証明となる証明情報πを算出し、算出した証明情報πを前記証明者端末に送信するステップと、前記証明者端末が、前記証明情報πを受信し、証明情報πを検証するステップとを更に含むことが好ましい。
【００１３】
また、前記第１関数Ｈは、ハッシュ関数であって、値Ｒは、Ｒ＝Ｈ（Ｄ）で表され、前記第１パラメータＹは、Ｙ＝ＧＡＲＢで表され、前記第１の値Ｓは、Ｓ＝Ｇｕで表され、前記第２の値Ｔは、Ｔ＝Ｒｕで表され、前記第２のパラメータＸは、Ｘ＝ＳＡＴＢで表され、前記第２関数ｈは、ハッシュ関数であって、前記証明者端末が算出する値Ｖは、Ｖ＝ｈ（Ｘ，Ｍ）で表され、前記検証者装置が算出する値Ｖは、Ｖ＝ｈ（Ｙｕ，Ｍ）で表され、前記証明情報πは、任意数ｗとし、ｎをＧの位数としたとき、π＝（ｚ，ｃ）（ここに、Ｗ１＝Ｇｗ、Ｗ２＝Ｒｗ、ｃ＝ｈ（Ｗ１，Ｗ２）、ｚ＝−ｃｕ＋ｗ（ｍｏｄ ｎ））で表され、前記検証するステップは、ｈ（ＧｚＳｃ，ＲｚＴｃ）＝ｃを満たすか否かで検証することが好ましい。
【００１４】
また、本発明の認証システムは、証明者端末にて証明者からの識別子ＩとパスワードＡを受け付けて、検証者装置によって当該証明者を認証する認証システムであって、前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、前記証明者端末が、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持する手段と、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信する手段と、前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信する手段と、受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信する手段とを備え、前記検証者装置が、前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶する手段と、前記証明者端末から、証明者の識別子Ｉを受信する手段と、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信する手段と、前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信する手段と、前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証する
手段とを備えることを特徴とする。
【００１５】
また、本発明の証明者端末は、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持する手段と、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信する手段と、前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信する手段と、受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信する手段とを備えることを特徴とする。
【００１６】
また、本発明の検証者装置は、前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶する手段と、前記証明者端末から、証明者の識別子Ｉを受信する手段と、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信する手段と、前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信する手段と、前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証する手段とを備えることを特徴とする。
【００１７】
また、本発明は、コンピュータに前記認証システムの証明者端末の機能を実現させるプログラムであって、証明者からの識別子ＩとパスワードＡの入力を受け付けて、検証者装置に識別子Ｉを送信するステップと、前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信するステップと、受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信するステップとを実行させるためのプログラムである。
【００１８】
また、本発明は、コンピュータに前記認証システムの検証者装置の機能を実現させるプログラムであって、前記証明者端末から、証明者の識別子Ｉを受信するステップと、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信するステップと、前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証するステップとを実行させるためのプログラムである。
【００１９】
また、本発明の共有鍵生成方法は、証明者端末と検証者装置の双方において使用される共有鍵を生成する共有鍵生成方法であって、前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、前記証明者端末は、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、証明者から受け付けたパスワードＡと、前記巡回群の値Ｇとを保持しており、前記検証者装置は、証明者の識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶しており、前記証明者端末が、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信するステップと、前記検証者装置が、識別子Ｉを受信して、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、前記証明者端末が、前記第１の値Ｓと前記第２の値Ｔを受信して、前記第１の値Ｓと、前記パスワードＡと、前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、証明者端末によって生成した第４の任意数Ｍ１を第２のパラメータＸで暗号化して値Ｖ１を算出し、算出した値Ｖ１を前記検証者装置に送信するステップと、前記検証者装置が、値Ｖ１を受信して、値Ｖ１を前記第１のパラメータＹと第３の任意数ｕで定まる第３の値で復号化して値Ｍ１を算出し、値Ｍ１と検証者装置によって生成した第５の任意数Ｍ２とをビット結合したものを前記第３の値で暗号化して値Ｖ２を算出し、算出した値Ｖ２を前記検証者装置に送信するステップと、前記証明者端末が、値Ｖ２を受信して、値Ｖ２を前記第２のパラメータＸで復号化して値Ｍを算出し、値Ｍが第５の任意数Ｍ２によって分解できるかどうかを確認し、分解できれば第５の任意数Ｍ２を第２のパラメータＸで暗号化して値Ｖ３を算出し、前記検証者装置に値Ｖ３を送信し、値Ｍ１と第５の任意数
Ｍ２とをビット結合したもので定まる第２関数ｈの値を共有鍵Ｋとするステップと、前記検証者装置が、値Ｖ３を受信して、値Ｖ３を前記第３の値で復号化して値Ｍ２を算出し、算出した値Ｍ２を用いて、前記第５の任意数Ｍ２を検証し、検証が成功であれば値Ｍ１と第５の任意数Ｍ２とをビット結合したもので定まる第２関数ｈの値を共有鍵Ｋとするステップとを含むことを特徴とする。
【００２０】
また、前記第１関数Ｈは、ハッシュ関数であって、値Ｒは、Ｒ＝Ｈ（Ｄ）で表され、前記第１パラメータＹは、Ｙ＝ＧＡＲＢで表され、前記第１の値Ｓは、Ｓ＝Ｇｕで表され、前記第２の値Ｔは、Ｔ＝Ｒｕで表され、前記第２のパラメータＸは、Ｘ＝ＳＡＴＢで表され、前記第４の任意数Ｍ１を第２のパラメータＸで暗号化して算出する値Ｖ１は、Ｖ１＝ＥＸ（Ｍ１）で表され、前記値Ｖ１を前記第３の値で復号化して算出する値Ｍ１は、
【数１】
で表され、前記値Ｍ１と前記第５の任意数Ｍ２とをビット結合したものを前記第３の値で暗号化して算出する値Ｖ２は、
【数２】
で表され、前記第５の任意数Ｍ２を前記第２のパラメータＸで暗号化して算出する値Ｖ３は、Ｖ３＝ＥＸ（Ｍ２）で表され、前記値Ｖ３を前記第３の値で復号化して算出する値Ｍ２は、
【数３】
で表され、前記第２関数ｈは、ハッシュ関数であることが好ましい。
【発明の効果】
【００２１】
本発明は、パスワードの知識を証明する認証方法において、証明者の内部情報が漏洩する攻撃環境や、証明者端末の内部情報を取得する攻撃環境や、証明者端末の内部の疑似乱数源を制御される攻撃環境における安全性を向上させることができる。また、証明者の内部情報が漏洩する攻撃環境における安全性を向上させた認証方法において、実装の手間や費用、実施に要する時間や費用を少なくすることができる。
【図面の簡単な説明】
【００２２】
【図１】証明者端末と検証者装置の構成図である。
【図２】設定段階における証明者端末と検証者装置の動作を説明するフローチャートである。
【図３】認証段階における証明者端末と検証者装置の動作を説明するフローチャートである。
【図４】共通鍵を求めるときの証明者端末と検証者装置の動作を説明するフローチャートである。
【発明を実施するための形態】
【００２３】
本発明の実施の形態について図面を参照して説明する。以下において、ｋをセキュリティパラメータとして、〈Ｇ〉を離散対数問題がｋに応じて困難である巡回群で元Ｇによって生成されるものとする。たとえば楕円エルガマル暗号で用いられる群などが好適である。以下、このような巡回群の暗号を用いる任意の点Ｇを単に巡回群の値Ｇと称する。
ｈ：｛０，１｝＊→｛０，１｝２ｋおよびＨ：｛０，１｝＊→〈Ｇ〉をハッシュ関数とする。
【００２４】
（第１の実施の形態）
第１の実施の形態は、証明者がパスワードを入力するための装置を備えた証明者端末と、検証者装置の間で実施される。実施される方式は、設定と認証の２段階からなる。
図１は、証明者端末と検証者装置の構成図である。証明者端末１０は、証明者からのデータ入力を受け付ける入力部１１と、検証者装置と通信を行う送受信部１２と、制御部１３と、各種演算を行う演算部１４と、乱数を生成する乱数生成部１５と、安全補強情報を蓄積するための静的記憶装置１６を備える。このような認証者端末には、ＩＣカードや、携帯端末、あるいは携帯端末上で動作する仮想マシンを想定することができる。
検証者装置２０は、証明者端末と通信を行う送受信部２２と、制御部２３と、各種演算を行う演算部２４と、乱数を生成する乱数生成部２５と、証明者の識別子と証明者の認証に用いる認証情報との組を記録する静的記憶装置２６を備える。このような検証者装置には一般的なＰＣやサーバなどを想定することができる。
なお、証明者端末１０と検証者装置２０は、予めｈおよびＨのハッシュ関数の仕様と、Ｇや巡回群の計算を行うために必要な情報、Ｇの位数を共有する。適切な巡回群の例としては、たとえば楕円曲線が考えられる。したがって、双方の装置は、楕円曲線を用いる場合、楕円パラメータと楕円の点Ｇの座標（ｘ，ｙ）の値、およびＧの位数を共有している。
【００２５】
図２は、設定段階における証明者端末と検証者装置の動作を説明するフローチャートである。設定段階において、証明者端末と検証者装置は次のようにふるまう。
証明者端末１０は、乱数生成部１５において２ｋビットの乱数Ｂを生成し、記憶装置１６に記憶する（Ｓ１００）。次に、入力部１１から証明者の識別子とパスワードの入力を受け付ける（Ｓ１０１）。識別子をＩ、パスワードをＡとする。次に、送受信部１２から検証者装置２０に識別子Ｉを送信する（Ｓ１０２）。
検証者装置２０は、送受信部２２を介して証明者端末１０から識別子Ｉを受信すると（Ｓ１０３）、乱数生成部２５において２ｋビットの乱数Ｄを生成し（Ｓ１０４）、生成された乱数Ｄを証明者端末１０に送信する（Ｓ１０５）。
証明者端末１０は、検証者装置２０から値Ｄを受信すると（Ｓ１０６）、演算部１４においてハッシュ値Ｒ＝Ｈ（Ｄ）、Ｙ＝ＧＡＲＢを計算し（Ｓ１０７）、計算して得られた値Ｙを検証者装置２０に送信する（Ｓ１０８）。
検証者装置２０は、証明者端末１０から値Ｙを受信すると（Ｓ１０９）、（Ｉ，Ｙ，Ｄ）を記憶装置２６に記憶する（Ｓ１１０）。
【００２６】
図３は、認証段階における証明者端末と検証者装置の動作を説明するフローチャートである。認証段階において、証明者端末と検証者装置は次のようにふるまう。
証明者端末１０は、入力部１１から証明者の識別子とパスワードの入力を受け付ける（Ｓ２００）。識別子をＩ、パスワードをＡとする。次に、送受信部１２から検証者装置２０に識別子Ｉを送信する（Ｓ２０１）。
検証者装置２０は、送受信部２２を介して証明者端末１０から識別子Ｉを受信すると（Ｓ２０２）、記憶装置２６から（Ｉ，Ｙ，Ｄ）を読み出し、演算部２４においてハッシュ値Ｒ＝Ｈ（Ｄ）を計算する（Ｓ２０３）。次に、乱数生成部２５において２ｋビットの乱数ｕを生成し（Ｓ２０４）、演算部２４においてＳ＝Ｇｕ，Ｔ＝Ｒｕを計算し、証明情報πを計算する（Ｓ２０５）。次に、送受信部２２から証明者端末１０にＳ，Ｔ，πを送信する（Ｓ２０６）。
証明者端末１０は、検証者装置２０から値ＳおよびＴ、証明情報πを受信すると（Ｓ２０７）、制御部１３において証明情報πを検証し（Ｓ２０８）、検証に不合格であれば処理を中止する。検証に合格すれば、記憶装置１６から値Ｂを読み出し、演算部１４においてＸ＝ＳＡＴＢを計算する（Ｓ２０９）。次に、乱数生成部１５においてｋビットの乱数Ｍを生成し（Ｓ２１０）、演算部１４においてハッシュ値Ｖ＝ｈ（Ｘ，Ｍ）を計算する（Ｓ２１１）。計算して得られた（Ｖ，Ｍ）を検証者装置２０に送信する（Ｓ２１２）。
検証者装置２０は、証明者端末１０から（Ｖ，Ｍ）を受信すると（Ｓ２１３）、制御部２３においてＶ＝ｈ（Ｙｕ，Ｍ）を確認する（Ｓ２１４）。Ｖ＝ｈ（Ｙｕ，Ｍ）であれば認証合格のメッセージを出力する（Ｓ２１５）。それ以外の場合は機能を停止する。
【００２７】
証明情報πの計算と検証は、Ｓ＝ＧｕかつＴ＝Ｒｕとなる数ｕの知識に関する非対話的ゼロ知識証明である。一例を次に述べる。πの計算のためには、２ｋビットの乱数ｗを生成し、Ｗ１＝Ｇｗ，Ｗ２＝Ｒｗ、ｃ＝ｈ（Ｗ１，Ｗ２）、ｚ＝−ｃｕ＋ｗ（ｍｏｄ ｎ）を計算し、π＝（ｚ，ｃ）とする。ただしｎはＧの位数である。π＝（ｚ，ｃ）の検証のためには、ｈ（ＧＺＳＣ，ＲＺＴＣ）＝ｃを満たすことを確認する。
【００２８】
（第２の実施の形態）
認証段階の後半を置き換えることで共通鍵生成方法として機能する。ＥＫ（Ｍ）は共通鍵暗号の暗号化を表し、ＤＫ（Ｃ）は共通鍵暗号の復号化を表すものとする。ただしＫは鍵、Ｍは平文、Ｃは暗号文である。
第１の実施の形態を共通鍵生成方法に変形すると、図４の通りである。登録段階と証明情報に関する手続は同様である。認証段階において、証明者端末と検証者装置は次のようにふるまう。
【００２９】
証明者端末１０は、入力部１１から証明者の識別子とパスワードの入力を受け付ける（Ｓ３００）。識別子をＩ、パスワードをＡとする。次に、送受信部１２から検証者装置２０に識別子Ｉを送信する（Ｓ３０１）。
検証者装置２０は、送受信部２２を介して証明者端末１０から識別子Ｉを受信すると（Ｓ３０２）、記憶装置２６から（Ｉ，Ｙ，Ｄ）を読み出し、演算部２４においてハッシュ値Ｒ＝Ｈ（Ｄ）を計算する（Ｓ３０３）。次に、乱数生成部２５において２ｋビットの乱数ｕを生成し（Ｓ３０４）、演算部２４においてＳ＝Ｇｕ，Ｔ＝Ｒｕを計算し、証明情報πを計算する（Ｓ３０５）。次に、送受信部２２から証明者端末１０にＳ，Ｔ，πを送信する（Ｓ３０６）。
【００３０】
証明者端末１０は、検証者装置２０から値ＳおよびＴ、証明情報πを受信すると（Ｓ３０７）、制御部１３において証明情報πを検証し（Ｓ３０８）、検証に不合格であれば処理を中止する。検証に合格すれば、記憶装置１６から値Ｂを読み出し、演算部１４においてＸ＝ＳＡＴＢを計算する（Ｓ３０９）。次に、乱数生成部１５においてｋビットの乱数Ｍ１を生成し（Ｓ３１０）、演算部１４においてＸを鍵としてＶ１＝ＥＸ（Ｍ１）を計算する（Ｓ３１１）。計算して得られたＶ１を検証者装置２０に送信する（Ｓ３１２）。
検証者装置２０は、証明者端末１０からＶ１を受信すると（Ｓ３１３）、演算部２４においてＹｕを鍵として
【数４】
を計算する（Ｓ３１４）。次に、乱数生成部２５においてｋビットの乱数Ｍ２を生成し（Ｓ３１５）、演算部２４においてＹｕを鍵として
【数５】
を計算する（Ｓ３１６）。計算して得られたＶ２を証明者端末１０に送信する（Ｓ３１７）。
【００３１】
証明者端末１０は、Ｖ２を検証者装置２０から受信すると（Ｓ３１８）、演算部１４においてＸを鍵としてＭ＝ＤＸ（Ｖ２）を計算する（Ｓ３１９）。次に、制御部１３において、ある文字列Ｍ２によってＭ＝Ｍ１｜Ｍ２と分解できるかどうかを確かめる（Ｓ３２０）。分解できなければ機能を停止する。なお、Ｍ１｜Ｍ２とは、Ｍ１とＭ２とをビット結合することを意味する。分解できたならば演算部１４においてＶ３＝ＥＸ（Ｍ２）を計算する（Ｓ３２１）。計算して得られたＶ３を検証者装置２０に送信する（Ｓ３２２）。そして、共有鍵をＫ＝ｈ（Ｍ１｜Ｍ２）とする（Ｓ３２３）。
検証者装置２０は、証明者端末１０からＶ３を受信すると（Ｓ３２４）、制御部２３において
【数６】
であることを確認する（Ｓ３２５）。確認できなければ、機能を停止する。確認できたならば、共有鍵をＫ＝ｈ（Ｍ１｜Ｍ２）とする（Ｓ３２６）。
【符号の説明】
【００３２】
１０ 証明者端末
１１ 入力部
１２，２２ 送受信部
１３，２３ 制御部
１４，２４ 演算部
１５，２５ 乱数生成部
１６，２６ 記憶装置
２０ 検証者装置
【特許請求の範囲】
【請求項１】
証明者端末にて証明者からの識別子ＩとパスワードＡを受け付けて、検証者装置によって当該証明者を認証する方法であって、
前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、
前記証明者端末は、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持しており、
前記検証者装置は、前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶しており、
前記証明者端末が、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信するステップと、
前記検証者装置が、識別子Ｉを受信して、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、
前記証明者端末が、前記第１の値Ｓと前記第２の値Ｔを受信して、前記第１の値Ｓと、前記パスワードＡと、前記第２の値Ｔと、前記第１の任意数Ｂとから定まる第２のパラメータＸを算出するとともに、該第２のパラメータＸと当該証明者端末によって生成した第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信するステップと、
前記検証者装置が、値Ｖと第４の任意数Ｍを受信して、前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証するステップと、
を含むことを特徴とする認証方法。
【請求項２】
前記検証者装置が、前記第１の値Ｓかつ前記第２の値Ｔとなる前記第３の任意数ｕの非対話的ゼロ知識証明となる証明情報πを算出し、算出した証明情報πを前記証明者端末に送信するステップと、
前記証明者端末が、前記証明情報πを受信し、証明情報πを検証するステップと、
を更に含むことを特徴とする請求項１に記載の認証方法。
【請求項３】
前記第１関数Ｈは、ハッシュ関数であって、値Ｒは、Ｒ＝Ｈ（Ｄ）で表され、
前記第１パラメータＹは、Ｙ＝ＧＡＲＢで表され、
前記第１の値Ｓは、Ｓ＝Ｇｕで表され、
前記第２の値Ｔは、Ｔ＝Ｒｕで表され、
前記第２のパラメータＸは、Ｘ＝ＳＡＴＢで表され、
前記第２関数ｈは、ハッシュ関数であって、
前記証明者端末が算出する値Ｖは、Ｖ＝ｈ（Ｘ，Ｍ）で表され、
前記検証者装置が算出する値Ｖは、Ｖ＝ｈ（Ｙｕ，Ｍ）で表され、
前記証明情報πは、任意数ｗとし、ｎをＧの位数としたとき
π＝（ｚ，ｃ）、
ここに、Ｗ１＝Ｇｗ
Ｗ２＝Ｒｗ
ｃ＝ｈ（Ｗ１，Ｗ２）
ｚ＝−ｃｕ＋ｗ（ｍｏｄ ｎ）
で表され、
前記検証するステップは、ｈ（ＧｚＳｃ，ＲｚＴｃ）＝ｃを満たすか否かで検証することを特徴とする請求項２に記載の認証方法。
【請求項４】
証明者端末にて証明者からの識別子ＩとパスワードＡを受け付けて、検証者装置によって当該証明者を認証する認証システムであって、
前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、
前記証明者端末は、
証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持する手段と、
証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信する手段と、
前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信する手段と、
受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信する手段と、を備え、
前記検証者装置は、
前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶する手段と、
前記証明者端末から、証明者の識別子Ｉを受信する手段と、
受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信する手段と、
前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信する手段と、
前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証する手段と、
を備えることを特徴とする認証システム。
【請求項５】
証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持する手段と、
証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信する手段と、
前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信する手段と、
受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信する手段と、
を備えることを特徴とする証明者端末。
【請求項６】
前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶する手段と、
前記証明者端末から、証明者の識別子Ｉを受信する手段と、
受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信する手段と、
前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信する手段と、
前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証する手段と、
を備えることを特徴とする検証者装置。
【請求項７】
コンピュータに請求項４に記載の認証システムの証明者端末の機能を実現させるプログラムであって、
証明者からの識別子ＩとパスワードＡの入力を受け付けて、検証者装置に識別子Ｉを送信するステップと、
前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信するステップと、
受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信するステップと、
を実行させるためのプログラム。
【請求項８】
コンピュータに請求項４に記載の認証システムの検証者装置の機能を実現させるプログラムであって、
前記証明者端末から、証明者の識別子Ｉを受信するステップと、
受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、
前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信するステップと、
前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証するステップと、
を実行させるためのプログラム。
【請求項９】
証明者端末と検証者装置の双方において使用される共有鍵を生成する共有鍵生成方法であって、
前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、
前記証明者端末は、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、証明者から受け付けたパスワードＡと、前記巡回群の値Ｇとを保持しており、
前記検証者装置は、証明者の識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶しており、
前記証明者端末が、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信するステップと、
前記検証者装置が、識別子Ｉを受信して、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、
前記証明者端末が、前記第１の値Ｓと前記第２の値Ｔを受信して、前記第１の値Ｓと、前記パスワードＡと、前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、証明者端末によって生成した第４の任意数Ｍ１を第２のパラメータＸで暗号化して値Ｖ１を算出し、算出した値Ｖ１を前記検証者装置に送信するステップと、
前記検証者装置が、値Ｖ１を受信して、値Ｖ１を前記第１のパラメータＹと第３の任意数ｕで定まる第３の値で復号化して値Ｍ１を算出し、値Ｍ１と検証者装置によって生成した第５の任意数Ｍ２とをビット結合したものを前記第３の値で暗号化して値Ｖ２を算出し、算出した値Ｖ２を前記検証者装置に送信するステップと、
前記証明者端末が、値Ｖ２を受信して、値Ｖ２を前記第２のパラメータＸで復号化して値Ｍを算出し、値Ｍが第５の任意数Ｍ２によって分解できるかどうかを確認し、分解できれば第５の任意数Ｍ２を第２のパラメータＸで暗号化して値Ｖ３を算出し、前記検証者装置に値Ｖ３を送信し、値Ｍ１と第５の任意数Ｍ２とをビット結合したもので定まる第２関数ｈの値を共有鍵Ｋとするステップと、
前記検証者装置が、値Ｖ３を受信して、値Ｖ３を前記第３の値で復号化して値Ｍ２を算出し、算出した値Ｍ２を用いて、前記第５の任意数Ｍ２を検証し、検証が成功であれば値Ｍ１と第５の任意数Ｍ２とをビット結合したもので定まる第２関数ｈの値を共有鍵Ｋとするステップと、
を含むことを特徴とする共有鍵生成方法。
【請求項１０】
前記第１関数Ｈは、ハッシュ関数であって、値Ｒは、Ｒ＝Ｈ（Ｄ）で表され、
前記第１パラメータＹは、Ｙ＝ＧＡＲＢで表され、
前記第１の値Ｓは、Ｓ＝Ｇｕで表され、
前記第２の値Ｔは、Ｔ＝Ｒｕで表され、
前記第２のパラメータＸは、Ｘ＝ＳＡＴＢで表され、
前記第４の任意数Ｍ１を第２のパラメータＸで暗号化して算出する値Ｖ１は、Ｖ１＝ＥＸ（Ｍ１）で表され、
前記値Ｖ１を前記第３の値で復号化して算出する値Ｍ１は、
【数１】
で表され、
前記値Ｍ１と前記第５の任意数Ｍ２とをビット結合したものを前記第３の値で暗号化して算出する値Ｖ２は、
【数２】
で表され、
前記第５の任意数Ｍ２を前記第２のパラメータＸで暗号化して算出する値Ｖ３は、Ｖ３＝ＥＸ（Ｍ２）で表され、
前記値Ｖ３を前記第３の値で復号化して算出する値Ｍ２は、
【数３】
で表され、
前記第２関数ｈは、ハッシュ関数であることを特徴とする請求項９に記載の共有鍵生成方法。
【請求項１】
証明者端末にて証明者からの識別子ＩとパスワードＡを受け付けて、検証者装置によって当該証明者を認証する方法であって、
前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、
前記証明者端末は、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持しており、
前記検証者装置は、前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶しており、
前記証明者端末が、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信するステップと、
前記検証者装置が、識別子Ｉを受信して、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、
前記証明者端末が、前記第１の値Ｓと前記第２の値Ｔを受信して、前記第１の値Ｓと、前記パスワードＡと、前記第２の値Ｔと、前記第１の任意数Ｂとから定まる第２のパラメータＸを算出するとともに、該第２のパラメータＸと当該証明者端末によって生成した第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信するステップと、
前記検証者装置が、値Ｖと第４の任意数Ｍを受信して、前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証するステップと、
を含むことを特徴とする認証方法。
【請求項２】
前記検証者装置が、前記第１の値Ｓかつ前記第２の値Ｔとなる前記第３の任意数ｕの非対話的ゼロ知識証明となる証明情報πを算出し、算出した証明情報πを前記証明者端末に送信するステップと、
前記証明者端末が、前記証明情報πを受信し、証明情報πを検証するステップと、
を更に含むことを特徴とする請求項１に記載の認証方法。
【請求項３】
前記第１関数Ｈは、ハッシュ関数であって、値Ｒは、Ｒ＝Ｈ（Ｄ）で表され、
前記第１パラメータＹは、Ｙ＝ＧＡＲＢで表され、
前記第１の値Ｓは、Ｓ＝Ｇｕで表され、
前記第２の値Ｔは、Ｔ＝Ｒｕで表され、
前記第２のパラメータＸは、Ｘ＝ＳＡＴＢで表され、
前記第２関数ｈは、ハッシュ関数であって、
前記証明者端末が算出する値Ｖは、Ｖ＝ｈ（Ｘ，Ｍ）で表され、
前記検証者装置が算出する値Ｖは、Ｖ＝ｈ（Ｙｕ，Ｍ）で表され、
前記証明情報πは、任意数ｗとし、ｎをＧの位数としたとき
π＝（ｚ，ｃ）、
ここに、Ｗ１＝Ｇｗ
Ｗ２＝Ｒｗ
ｃ＝ｈ（Ｗ１，Ｗ２）
ｚ＝−ｃｕ＋ｗ（ｍｏｄ ｎ）
で表され、
前記検証するステップは、ｈ（ＧｚＳｃ，ＲｚＴｃ）＝ｃを満たすか否かで検証することを特徴とする請求項２に記載の認証方法。
【請求項４】
証明者端末にて証明者からの識別子ＩとパスワードＡを受け付けて、検証者装置によって当該証明者を認証する認証システムであって、
前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、
前記証明者端末は、
証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持する手段と、
証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信する手段と、
前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信する手段と、
受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信する手段と、を備え、
前記検証者装置は、
前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶する手段と、
前記証明者端末から、証明者の識別子Ｉを受信する手段と、
受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信する手段と、
前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信する手段と、
前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証する手段と、
を備えることを特徴とする認証システム。
【請求項５】
証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、パスワードＡと、前記巡回群の値Ｇとを保持する手段と、
証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信する手段と、
前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信する手段と、
受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信する手段と、
を備えることを特徴とする証明者端末。
【請求項６】
前記識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶する手段と、
前記証明者端末から、証明者の識別子Ｉを受信する手段と、
受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信する手段と、
前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信する手段と、
前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証する手段と、
を備えることを特徴とする検証者装置。
【請求項７】
コンピュータに請求項４に記載の認証システムの証明者端末の機能を実現させるプログラムであって、
証明者からの識別子ＩとパスワードＡの入力を受け付けて、検証者装置に識別子Ｉを送信するステップと、
前記検証者装置から、前記巡回群の値Ｇと検証者装置によって生成した第３の任意数ｕで定まる第１の値Ｓと、前記第２の任意数Ｄから定まる第１関数Ｈの値Ｒと第３の任意数ｕで定まる第２の値Ｔとを受信するステップと、
受信した前記第１の値Ｓと、前記パスワードＡと、受信した前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、第２のパラメータＸと第４の任意数Ｍから定まる第２関数ｈの値Ｖを算出し、算出した値Ｖと第４の任意数Ｍを前記検証者装置に送信するステップと、
を実行させるためのプログラム。
【請求項８】
コンピュータに請求項４に記載の認証システムの検証者装置の機能を実現させるプログラムであって、
前記証明者端末から、証明者の識別子Ｉを受信するステップと、
受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、
前記証明者端末から、前記第１の値Ｓ、前記パスワードＡ、前記第２の値Ｔ、および前記第１の任意数Ｂから算出された第２のパラメータＸと、証明者端末によって生成した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを受信するとともに、前記第４の任意数Ｍを受信するステップと、
前記第１のパラメータＹと第３の任意数ｕで定まる第３の値と、受信した第４の任意数Ｍとで定まる第２関数ｈの値Ｖを算出し、算出した値Ｖを用いて、前記受信した値Ｖを検証するステップと、
を実行させるためのプログラム。
【請求項９】
証明者端末と検証者装置の双方において使用される共有鍵を生成する共有鍵生成方法であって、
前記証明者端末と前記検証者装置の双方は、巡回群の値Ｇと、第１関数Ｈと、第２関数ｈとを共有しており、
前記証明者端末は、証明者端末によって生成した第１の任意数Ｂと、前記検証者装置によって生成された第２の任意数Ｄを受信して算出した第１関数Ｈの値Ｒと、証明者から受け付けたパスワードＡと、前記巡回群の値Ｇとを保持しており、
前記検証者装置は、証明者の識別子Ｉと、前記第２の任意数Ｄと、前記証明者端末から受信した、第１の任意数Ｂと値ＲとパスワードＡと巡回群の値Ｇから定まる第１パラメータＹとを予め記憶しており、
前記証明者端末が、証明者からの識別子ＩとパスワードＡの入力を受け付けて、前記検証者装置に識別子Ｉを送信するステップと、
前記検証者装置が、識別子Ｉを受信して、受信した識別子Ｉと予め記憶している識別子Ｉとを検証し、一致した場合に予め記憶している第２の任意数Ｄを用いて、第２の任意数Ｄから定まる第１関数Ｈの値Ｒを算出し、第３の任意数ｕを生成し、前記巡回群の値Ｇと第３の任意数ｕで定まる第１の値Ｓと、値Ｒと第３の任意数ｕで定まる第２の値Ｔとを算出し、前記証明者端末に第１の値Ｓと第２の値Ｔを送信するステップと、
前記証明者端末が、前記第１の値Ｓと前記第２の値Ｔを受信して、前記第１の値Ｓと、前記パスワードＡと、前記第２の値Ｔと、前記第１の任意数Ｂとから第２のパラメータＸを算出し、証明者端末によって生成した第４の任意数Ｍ１を第２のパラメータＸで暗号化して値Ｖ１を算出し、算出した値Ｖ１を前記検証者装置に送信するステップと、
前記検証者装置が、値Ｖ１を受信して、値Ｖ１を前記第１のパラメータＹと第３の任意数ｕで定まる第３の値で復号化して値Ｍ１を算出し、値Ｍ１と検証者装置によって生成した第５の任意数Ｍ２とをビット結合したものを前記第３の値で暗号化して値Ｖ２を算出し、算出した値Ｖ２を前記検証者装置に送信するステップと、
前記証明者端末が、値Ｖ２を受信して、値Ｖ２を前記第２のパラメータＸで復号化して値Ｍを算出し、値Ｍが第５の任意数Ｍ２によって分解できるかどうかを確認し、分解できれば第５の任意数Ｍ２を第２のパラメータＸで暗号化して値Ｖ３を算出し、前記検証者装置に値Ｖ３を送信し、値Ｍ１と第５の任意数Ｍ２とをビット結合したもので定まる第２関数ｈの値を共有鍵Ｋとするステップと、
前記検証者装置が、値Ｖ３を受信して、値Ｖ３を前記第３の値で復号化して値Ｍ２を算出し、算出した値Ｍ２を用いて、前記第５の任意数Ｍ２を検証し、検証が成功であれば値Ｍ１と第５の任意数Ｍ２とをビット結合したもので定まる第２関数ｈの値を共有鍵Ｋとするステップと、
を含むことを特徴とする共有鍵生成方法。
【請求項１０】
前記第１関数Ｈは、ハッシュ関数であって、値Ｒは、Ｒ＝Ｈ（Ｄ）で表され、
前記第１パラメータＹは、Ｙ＝ＧＡＲＢで表され、
前記第１の値Ｓは、Ｓ＝Ｇｕで表され、
前記第２の値Ｔは、Ｔ＝Ｒｕで表され、
前記第２のパラメータＸは、Ｘ＝ＳＡＴＢで表され、
前記第４の任意数Ｍ１を第２のパラメータＸで暗号化して算出する値Ｖ１は、Ｖ１＝ＥＸ（Ｍ１）で表され、
前記値Ｖ１を前記第３の値で復号化して算出する値Ｍ１は、
【数１】
で表され、
前記値Ｍ１と前記第５の任意数Ｍ２とをビット結合したものを前記第３の値で暗号化して算出する値Ｖ２は、
【数２】
で表され、
前記第５の任意数Ｍ２を前記第２のパラメータＸで暗号化して算出する値Ｖ３は、Ｖ３＝ＥＸ（Ｍ２）で表され、
前記値Ｖ３を前記第３の値で復号化して算出する値Ｍ２は、
【数３】
で表され、
前記第２関数ｈは、ハッシュ関数であることを特徴とする請求項９に記載の共有鍵生成方法。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１０−１６６５２６（Ｐ２０１０−１６６５２６Ａ）
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願番号】特願２００９−９２６８（Ｐ２００９−９２６８）
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]