(57)【要約】【課題】  ＩＤ証明者毎の公開鍵の取得を必要とせずにＩＤの正当性を検証する。【解決手段】  ＩＤ鍵発行装置１００は、乱数Ｒが素数ｐ及びｑを法として平方剰余であるか否かを判定することにより、公開鍵の要素を定義する公開鍵要素定義部１０３と、数ｎ（＝ｐｑ）と、前記公開鍵の要素とを公開鍵４００として生成する公開鍵生成部１０４と、公開鍵公開手段１０５と、証明対象となるＩＤに基づいて、ＩＤ鍵Ｔを生成するＩＤ鍵生成部１０９と、ＩＤ鍵発行部１１０とを備える。ＩＤ検証装置２００は、ＩＤによらない公開鍵４００に基づいて、ＩＤ証明装置３００がＩＤ鍵Ｔとして保持しているか否かを、ＩＤ証明装置３００との平方剰余に基づいたゼロ知識対話証明手続によって確認することにより、ＩＤの正当性の検証を行うＩＤ正当性検証部２０５を備える。【選択図】  図２
2005167385.tif 000002
【特許請求の範囲】
【請求項１】
２つの素数ｐ及びｑを生成する素数生成手段と、
乱数Ｒを生成する乱数生成手段と、
前記乱数Ｒが前記素数ｐを法として平方剰余であるか否かを判定すると共に、前記乱数Ｒが前記素数ｑを法として平方剰余であるか否かを判定することにより、前記乱数Ｒから、前記素数ｐを法としても前記素数ｑを法としても平方剰余である数Ｍ１と、前記素数ｐを法としたら平方剰余であり前記素数ｑを法としたら平方剰余でない数Ｍ２と、前記素数ｐを法としたら平方剰余でなく前記素数ｑを法としたら平方剰余である数Ｍ３と、前記素数ｐを法としても前記素数ｑを法としても平方剰余でない数Ｍ４とを公開鍵の要素として定義する公開鍵要素定義手段と、
前記素数ｐとｑとを乗算し、当該乗算で得られた数ｎと、前記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とを公開鍵として生成する公開鍵生成手段と、
前記公開鍵生成手段により生成された公開鍵を公開する公開鍵公開手段と、
を備えるＩＤ鍵発行装置。
【請求項２】
証明対象となるＩＤを取得するＩＤ取得手段と、
前記ＩＤ受信手段により受信されたＩＤを予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出するハッシュ値算出手段と、
前記ハッシュ値算出手段により算出されたハッシュ値Ｈと、前記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出するＩＤ鍵候補算出手段と、
前記ハッシュ値Ｈが前記素数ｐを法として平方剰余であるか否かを判定すると共に、前記ハッシュ値Ｈが前記素数ｑを法として平方剰余であるか否かを判定することにより、前記ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４のうち前記数ｎを法として平方剰余であるものを判定し、当該平方剰余であると判定されたものを候補Ｚとし、前記数ｎを法とした当該候補Ｚの平方根を算出し、当該平方根をＩＤ鍵ＴとするＩＤ鍵生成手段と、
前記ＩＤ鍵生成手段により生成されたＩＤ鍵Ｔを発行するＩＤ鍵発行手段と、
を更に備える請求項１に記載のＩＤ鍵発行装置。
【請求項３】
素数ｐとｑとを乗算して得られる数ｎと、前記素数ｐを法としても前記素数ｑを法としても平方剰余である数Ｍ１と、前記素数ｐを法としたら平方剰余であり前記素数ｑを法としたら平方剰余でない数Ｍ２と、前記素数ｐを法としたら平方剰余でなく前記素数ｑを法としたら平方剰余である数Ｍ３と、前記素数ｐを法としても前記素数ｑを法としても平方剰余でない数Ｍ４とを要素とする公開鍵を取得する公開鍵取得手段と、
ＩＤ証明装置から、検証対象となるＩＤを取得する検証対象ＩＤ取得手段と、
前記検証対象ＩＤ受信手段により受信されたＩＤを、前記公開鍵を生成するＩＤ鍵発行装置で用いられるハッシュ関数と同一の、予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出するハッシュ値算出手段と、
前記ハッシュ値算出手段により算出されたハッシュ値Ｈと、前記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、対話証明手続用情報として数Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出する対話証明手続用情報算出手段と、
前記数ｎを法とした前記数Ｚ１，Ｚ２，Ｚ３，Ｚ４のいずれかの平方根を、ＩＤ証明装置がＩＤ鍵Ｔとして保持しているか否かを、ＩＤ証明装置との平方剰余に基づいたゼロ知識対話証明手続によって確認することにより、前記検証対象ＩＤ受信手段により受信されたＩＤの正当性の検証を行うＩＤ正当性検証手段と、
を備えるＩＤ検証装置。
【請求項４】
証明対象となるＩＤを送信するＩＤ送信手段と、
前記証明対象となるＩＤに基づいて生成されたＩＤ鍵Ｔを取得するＩＤ鍵取得手段と、
素数ｐとｑとを乗算して得られる数ｎを要素に含む公開鍵を取得する公開鍵取得手段と、
自装置に前記ＩＤ鍵Ｔを保持しているか否かを、前記数ｎを用いた、ＩＤ検証装置との平方剰余に基づいたゼロ知識対話証明手続によって証明することにより、前記証明対象となるＩＤの正当性の証明を行うＩＤ正当性証明手段と、
を備えるＩＤ証明装置。
【請求項５】
素数生成手段が、２つの素数ｐ及びｑを生成する素数生成ステップと、
乱数生成手段が、乱数Ｒを生成する乱数生成ステップと、
公開鍵要素定義手段が、前記乱数Ｒが前記素数ｐを法として平方剰余であるか否かを判定すると共に、前記乱数Ｒが前記素数ｑを法として平方剰余であるか否かを判定することにより、前記乱数Ｒから、前記素数ｐを法としても前記素数ｑを法としても平方剰余である数Ｍ１と、前記素数ｐを法としたら平方剰余であり前記素数ｑを法としたら平方剰余でない数Ｍ２と、前記素数ｐを法としたら平方剰余でなく前記素数ｑを法としたら平方剰余である数Ｍ３と、前記素数ｐを法としても前記素数ｑを法としても平方剰余でない数Ｍ４とを公開鍵の要素として定義する公開鍵要素定義ステップと、
公開鍵生成手段が、前記素数ｐとｑとを乗算し、当該乗算で得られた数ｎと、前記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とを公開鍵として生成する公開鍵生成ステップと、
公開鍵公開手段が、前記公開鍵生成ステップにより生成された公開鍵を公開する公開鍵公開ステップと、
を備えるＩＤ鍵発行方法。
【請求項６】
ＩＤ取得手段が、証明対象となるＩＤを取得するＩＤ取得ステップと、
ハッシュ値算出手段が、前記ＩＤ受信ステップにより受信されたＩＤを予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出するハッシュ値算出ステップと、
ＩＤ鍵候補算出手段が、前記ハッシュ値算出ステップにより算出されたハッシュ値Ｈと、前記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出するＩＤ鍵候補算出ステップと、
ＩＤ鍵生成手段が、前記ハッシュ値Ｈが前記素数ｐを法として平方剰余であるか否かを判定すると共に、前記ハッシュ値Ｈが前記素数ｑを法として平方剰余であるか否かを判定することにより、前記ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４のうち前記数ｎを法として平方剰余であるものを判定し、当該平方剰余であると判定されたものを候補Ｚとし、前記数ｎを法とした当該候補Ｚの平方根を算出し、当該平方根をＩＤ鍵ＴとするＩＤ鍵生成ステップと、
ＩＤ鍵発行手段が、前記ＩＤ鍵生成ステップにより生成されたＩＤ鍵Ｔを発行するＩＤ鍵発行ステップと、
を更に備える請求項５に記載のＩＤ鍵発行方法。
【請求項７】
公開鍵取得手段が、素数ｐとｑとを乗算して得られる数ｎと、前記素数ｐを法としても前記素数ｑを法としても平方剰余である数Ｍ１と、前記素数ｐを法としたら平方剰余であり前記素数ｑを法としたら平方剰余でない数Ｍ２と、前記素数ｐを法としたら平方剰余でなく前記素数ｑを法としたら平方剰余である数Ｍ３と、前記素数ｐを法としても前記素数ｑを法としても平方剰余でない数Ｍ４とを要素とする公開鍵を取得する公開鍵取得ステップと、
検証対象ＩＤ取得手段が、ＩＤ証明装置から、検証対象となるＩＤを取得する検証対象ＩＤ取得ステップと、
ハッシュ値算出手段が、前記検証対象ＩＤ受信ステップにより受信されたＩＤを、前記公開鍵を生成するＩＤ鍵発行方法で用いられるハッシュ関数と同一の、予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出するハッシュ値算出ステップと、
対話証明手続用情報算出手段が、前記ハッシュ値算出ステップにより算出されたハッシュ値Ｈと、前記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、対話証明手続用情報として数Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出する対話証明手続用情報算出ステップと、
ＩＤ正当性検証手段が、前記数ｎを法とした前記数Ｚ１，Ｚ２，Ｚ３，Ｚ４のいずれかの平方根を、ＩＤ証明装置がＩＤ鍵Ｔとして保持しているか否かを、ＩＤ証明装置との平方剰余に基づいたゼロ知識対話証明手続によって確認することにより、前記検証対象ＩＤ受信ステップにより受信されたＩＤの正当性の検証を行うＩＤ正当性検証ステップと、
を備えるＩＤ検証方法。
【請求項８】
ＩＤ送信手段が、証明対象となるＩＤを送信するＩＤ送信ステップと、
ＩＤ鍵取得手段が、前記証明対象となるＩＤに基づいて生成されたＩＤ鍵Ｔを取得するＩＤ鍵取得ステップと、
公開鍵取得手段が、素数ｐとｑとを乗算して得られる数ｎを要素に含む公開鍵を取得する公開鍵取得ステップと、
ＩＤ正当性証明手段が、自装置に前記ＩＤ鍵Ｔを保持しているか否かを、前記数ｎを用いた、ＩＤ検証装置との平方剰余に基づいたゼロ知識対話証明手続によって証明することにより、前記証明対象となるＩＤの正当性の証明を行うＩＤ正当性証明ステップと、
を備えるＩＤ証明方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＤ鍵発行装置、ＩＤ検証装置、ＩＤ証明装置、ＩＤ鍵発行方法、ＩＤ検証方法及びＩＤ証明方法に関する。
【背景技術】
【０００２】
従来から、通信相手のＩＤ（ＩＰアドレス、ホスト名、メールアドレス、及びＳＩＰ（Session Initiation Protocol）アドレス等の識別情報）が、正当なＩＤ所有者以外の者によってなりすまされているものでなく、正当なものかどうかを検証するために、以下に示すような方法が一般に用いられている。まず、ＩＤ所有者（ＩＤ証明者）は、自身の秘密鍵により暗号化された検証用情報を、ＩＤと共に送信する。ＩＤ検証者は、受信した検証用情報を、ＩＤ所有者の公開鍵を用いて復号化する。次に、ＩＤ検証者は、復号化された情報から、その公開鍵とペアである秘密鍵をＩＤ所有者が持っていることを検証することにより、ＩＤ所有者の正当性を検証する（下記の非特許文献１参照）。
【０００３】
これを、ＩＰアドレスのなりすまし防止に適用した例として、ＨＩＰ（Host Identity Protocol）を用いた、以下に示すような方式がある。この方式では、ＩＤ検証者がＤＮＳ（Domain Name System）により、通信相手の公開鍵を取得しておく。ＩＤ証明者は、自身の秘密鍵によって生成したＨＩＴ（Host Identity Tag）をＩＰ（Internet Protocol）パケットに付加してＩＤ検証者に送信する。ＩＤ検証者は、ＨＩＴをそのＩＤ証明者の公開鍵で検証するため、そのＩＤ証明者の秘密鍵を持っていない者は、そのＩＤ証明者が所有するＩＰアドレスのなりすましを行うことができない（下記の非特許文献２参照）。
【非特許文献１】Bruce Schneier，“Applied Cryptography, Second Edition：Protocols, Algorithms, and Source Code in C”，John Wiley＆Sons, Inc.
【非特許文献２】Robert Moskowitz，“The Host Identity and Host Identity Payload”，Ipsec Global Summit in Paris，France，October 24,2001
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記の方法では、ＩＤ検証者がＩＤの検証を行うにはそれぞれのＩＤ証明者（通信相手）の公開鍵を所有していなければならない。そのため、ＩＤ検証者は各ＩＤ証明者の公開鍵を、それぞれ取得する必要があり、その点で煩雑さが発生していた。
【０００５】
本発明は、上記課題を解決するためになされたものであり、ＩＤ証明者毎の公開鍵の取得を必要とせずにＩＤの正当性を検証できるＩＤ鍵発行装置、ＩＤ検証装置、ＩＤ証明装置、ＩＤ鍵発行方法、ＩＤ検証方法及びＩＤ証明方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の説明で用いている平方剰余、平方根とは、以下に説明するものを指す。整数ｍとｙが与えられたとき、ｙ＝ｘ２  ｍｏｄ  ｍとなる整数ｘが存在するとき、ｙはｍを法として（（ｍｏｄ  ｍ）で）平方剰余であるという。ｘを、ｍを法とした（（ｍｏｄ  ｍ）での）ｙの平方根という。ｍが素数のとき、ｙがｍを法として平方剰余であるか否かは、平方剰余の相互法則を用いることにより高速に判定できる。即ち、ｙ（ｍ−１）／２が“１”であれば、ｙがｍを法として平方剰余であると判定できる。
【０００７】
本発明では、平方剰余に基づいたゼロ知識対話証明を用いている。以下に、平方剰余に基づいたゼロ知識対話証明を説明する。
【０００８】
ゼロ知識対話証明は、例えば上記非特許文献１に開示されている。この方法を用いることにより、ある秘密情報を持っている装置は、その秘密情報を漏らさずに「秘密情報を持っていること」を相手に認識させることができる。その原理としては、まず秘密情報を持っていることを証明する装置（証明装置）が、ある演算を乱数に施して得た演算結果を検証装置に送る。次に検証装置が、“０”か“１”かを任意に選び（例えば、コイン投げをして表か裏かでもよい）、選んだ値を証明装置に送る。証明装置は、その値が“０”であれば乱数そのものを検証装置に送り、その値が“１”であれば乱数と秘密情報とを演算して得た演算結果を送る。そして、検証装置は、証明装置から送信されたこれらの情報が公知の関係を満たしているかどうかを検証する。
【０００９】
仮に、証明装置が秘密情報を持っていないとすると、証明装置はこの検証に５０％の確率でしか合格できない。従って、このような検証を多くの回数繰り返すことによって、証明装置が秘密情報を持っているか否かを、限りなく１００％に近い確率で検証することができる。ここでは、一例として、図１を用いて、平方剰余問題を用いた対話証明方式を説明する。
【００１０】
ステップＳ１として、証明装置は、秘密情報ＴからＺ=Ｔ２  ｍｏｄ  ｎなるＺ及びｎを検証装置に安全な方法で届ける。ここで、ｎ=ｐｑ（ｐとｑは大きい素数）であるため、ｎを素因数分解するのは非常に難しい。
【００１１】
ステップＳ２として、証明装置は、乱数Ｒを生成し、Ｘ=Ｒ２  ｍｏｄ  ｎを計算し、得られたＸを検証装置に送る。
【００１２】
ステップＳ３として、検証装置は、ｂとして“０”又は“１”のうち何れかを二者択一的にランダムに選び、選んだｂを証明装置に送る。
【００１３】
ステップＳ４として、証明装置は、次のＹを検証装置に送る。ｂ=０のとき、Ｙ=Ｒであり、ｂ＝１のとき、Ｙ=ＴＲ  ｍｏｄ  ｎである。
【００１４】
そして、ステップＳ５として、検証装置は、次式が成立するか否かを検査する。即ち、ｂ=０のときは、Ｘ=Ｙ２  ｍｏｄ  ｎが成立するか。ｂ=１のときは、ＺＸ=Ｙ２  ｍｏｄ  ｎが成立するか。
【００１５】
以上のような対話証明方式では、証明装置が本当に秘密情報Ｔを知っていたら、ステップＳ５での検証にはいつも合格する。上記のステップＳ２〜Ｓ５をｋ回繰り返せば、偽の証明装置がだまし続けられる確率は、（１／２）ｋとなる。
【００１６】
なお、ステップＳ２〜Ｓ５をｋ回繰り返すのを省略して、代わりに、ステップＳ２で乱数をｋ個（Ｒ１，Ｒ２，…，Ｒｋ）生成し、Ｘ=Ｒ２  ｍｏｄ  ｎで計算した結果（Ｘ１，Ｘ２，…，Ｘｋ）を送る。次のステップＳ３で検証装置は、二者択一的にランダムに選んだｋ個の｛０，１｝の列（ｂ１，ｂ２，…，ｂｋ）を証明装置に送り、同様にステップＳ４で、証明装置は回答の列（Ｙ１，Ｙ２，…，Ｙｋ）を検証装置に送る。そして、検証装置は、回答の列（Ｙ１，Ｙ２，…，Ｙｋ）を１つ１つ検査し、それら全てが正解であったときのみ、証明装置が秘密情報を持っていることを認定する。
【００１７】
上記目的を達成するために、本発明に係るＩＤ鍵発行装置は、２つの素数ｐ及びｑを生成する素数生成手段と、乱数Ｒを生成する乱数生成手段と、上記乱数Ｒが上記素数ｐを法として平方剰余であるか否かを判定すると共に、上記乱数Ｒが上記素数ｑを法として平方剰余であるか否かを判定することにより、上記乱数Ｒから、上記素数ｐを法としても上記素数ｑを法としても平方剰余である数Ｍ１と、上記素数ｐを法としたら平方剰余であり上記素数ｑを法としたら平方剰余でない数Ｍ２と、上記素数ｐを法としたら平方剰余でなく上記素数ｑを法としたら平方剰余である数Ｍ３と、上記素数ｐを法としても上記素数ｑを法としても平方剰余でない数Ｍ４とを公開鍵の要素として定義する公開鍵要素定義手段と、上記素数ｐとｑとを乗算し、当該乗算で得られた数ｎと、上記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とを公開鍵として生成する公開鍵生成手段と、上記公開鍵生成手段により生成された公開鍵を公開する公開鍵公開手段とを備えることを特徴とする。ここで、上記素数の生成は、例えば、適当な数を選び、当該適当な数が素数か否かを判定し、素数でなければもう一度選びなおすという方法により達成される。素数か否かの判定は、文献「M.Agrawal，N.Kayal and N.Saxena，“PRIMES is in P”，Preprint，2002，1−9.」に記載された方法で確実に行える。
【００１８】
また、本発明に係るＩＤ鍵発行装置は、証明対象となるＩＤを取得するＩＤ取得手段と、上記ＩＤ受信手段により受信されたＩＤを予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出するハッシュ値算出手段と、上記ハッシュ値算出手段により算出されたハッシュ値Ｈと、上記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出するＩＤ鍵候補算出手段と、上記ハッシュ値Ｈが上記素数ｐを法として平方剰余であるか否かを判定すると共に、上記ハッシュ値Ｈが上記素数ｑを法として平方剰余であるか否かを判定することにより、上記ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４のうち上記数ｎを法として平方剰余であるものを判定し、当該平方剰余であると判定されたものを候補Ｚとし、上記数ｎを法とした当該候補Ｚの平方根を算出し、当該平方根をＩＤ鍵ＴとするＩＤ鍵生成手段と、上記ＩＤ鍵生成手段により生成されたＩＤ鍵Ｔを発行するＩＤ鍵発行手段とを更に備える構成とすることが望ましい。ここで、ハッシュ関数とは、データから一定長のメッセージダイジェスト（ハッシュ値）を生成する一方向性関数であり、例えばＳＨＡ−１（Secure Hash Algorithm 1）やＭＤ５（Message Digest 5）が相当する。
【００１９】
また、本発明に係るＩＤ検証装置は、素数ｐとｑとを乗算して得られる数ｎと、上記素数ｐを法としても上記素数ｑを法としても平方剰余である数Ｍ１と、上記素数ｐを法としたら平方剰余であり上記素数ｑを法としたら平方剰余でない数Ｍ２と、上記素数ｐを法としたら平方剰余でなく上記素数ｑを法としたら平方剰余である数Ｍ３と、上記素数ｐを法としても上記素数ｑを法としても平方剰余でない数Ｍ４とを要素とする公開鍵を取得する公開鍵取得手段と、ＩＤ証明装置から、検証対象となるＩＤを取得する検証対象ＩＤ取得手段と、上記検証対象ＩＤ受信手段により受信されたＩＤを、上記公開鍵を生成するＩＤ鍵発行装置で用いられるハッシュ関数と同一の、予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出するハッシュ値算出手段と、上記ハッシュ値算出手段により算出されたハッシュ値Ｈと、上記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、対話証明手続用情報として数Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出する対話証明手続用情報算出手段と、上記数ｎを法とした上記数Ｚ１，Ｚ２，Ｚ３，Ｚ４のいずれかの平方根を、ＩＤ証明装置がＩＤ鍵Ｔとして保持しているか否かを、ＩＤ証明装置との平方剰余に基づいたゼロ知識対話証明手続によって確認することにより、上記検証対象ＩＤ受信手段により受信されたＩＤの正当性の検証を行うＩＤ正当性検証手段とを備えることを特徴とする。
【００２０】
また、本発明に係るＩＤ証明装置は、証明対象となるＩＤを送信するＩＤ送信手段と、上記証明対象となるＩＤに基づいて生成されたＩＤ鍵Ｔを取得するＩＤ鍵取得手段と、素数ｐとｑとを乗算して得られる数ｎを要素に含む公開鍵を取得する公開鍵取得手段と、自装置に上記ＩＤ鍵Ｔを保持しているか否かを、上記数ｎを用いた、ＩＤ検証装置との平方剰余に基づいたゼロ知識対話証明手続によって証明することにより、上記証明対象となるＩＤの正当性の証明を行うＩＤ正当性証明手段とを備えることを特徴とする。
【００２１】
本発明により実行される処理を説明する。本発明における処理は、公開鍵の生成と公開、ＩＤ鍵の生成、及びＩＤの正当性の検証という大きく３つの処理に分けることができる。最初に、公開鍵の生成と公開の処理を説明する。
【００２２】
まず、ＩＤ鍵発行装置において、素数生成手段が、２つの素数ｐ及びｑを生成する。素数の生成は、上述したように例えば、適当な数を選び、当該適当な数が素数か否かを判定し、素数でなければ選び直すという方法により行う。ここで、当該２つの素数ｐ及びｑの大きさ（桁数）は、それらの積の値を実用的な時間で素因数分解をするのが難しいものとする。
【００２３】
続いて、乱数生成手段が、乱数Ｒを生成する。
【００２４】
続いて、公開鍵要素定義手段が、上記乱数Ｒが上記素数ｐを法として平方剰余であるか否かを判定する（判定１）。続いて、上記乱数Ｒが上記素数ｑを法として平方剰余であるか否かを判定する（判定２）。判定１、判定２共に平方剰余であると判定された場合は、上記乱数Ｒを公開鍵の要素である数Ｍ１として定義する。判定１のみ平方剰余であると判定された場合は、上記乱数Ｒを公開鍵の要素である数Ｍ２として定義する。判定２のみ平方剰余であると判定された場合は、上記乱数Ｒを公開鍵の要素である数Ｍ３として定義する。判定１、判定２共に平方剰余でないと判定された場合は、上記乱数Ｒを公開鍵の要素である数Ｍ４として定義する。上記乱数Ｒの生成及び公開鍵の要素の定義を、数Ｍ１〜Ｍ４すべてが定義されるまで繰り返す。
【００２５】
上記の処理により、Ｍ１は素数ｐを法としても素数ｑを法としても平方剰余である数（当該性質を有する数の集合をグループＧ１と呼ぶ）となる。Ｍ２は素数ｐを法としたら平方剰余であり素数ｑを法としたら平方剰余でない数（当該性質を有する数の集合をグループＧ２と呼ぶ）となる。Ｍ３は素数ｐを法としたら平方剰余でなく素数ｑを法としたら平方剰余である数（当該性質を有する数の集合をグループＧ３と呼ぶ）となる。Ｍ４は素数ｐを法としても素数ｑを法としても平方剰余でない数（当該性質を有する数の集合をグループＧ４と呼ぶ）となる。ここで、任意の整数は上記いずれかのグループに含まれ、同一のグループ同士の数の積をとると、その数は必ずｎ（＝ｐｑ）を法として平方剰余になる。この性質はヤコビ記号を用いて説明することができる。
【００２６】
続いて、公開鍵生成手段が、素数ｐとｑとを乗算し、当該乗算で得られた数ｎと、上記で得られた数Ｍ１，M２，M３，M４とを公開鍵として生成する。
【００２７】
続いて、公開鍵公開手段が、上記公開鍵を公開する。当該公開は、外部からアクセス可能なサーバに格納する等の方法により行われる。公開鍵の生成と公開の処理は以上である。
【００２８】
次に、ＩＤ鍵の生成の処理を説明する。まず、ＩＤ証明装置において、ＩＤ送信手段が、ＩＤ鍵発行装置に検証対象となるＩＤを送信する。ＩＤを送信されたＩＤ鍵発行装置では、ＩＤ取得手段が当該ＩＤを受信する。ここで、ＩＤは、ＩＰアドレス、ホスト名、メールアドレス、及びＳＩＰ（Session Initiation Protocol）アドレス等の識別情報であり、任意のビット列からなる。
【００２９】
続いて、ハッシュ値算出手段が、当該ＩＤを予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出する。続いて、ＩＤ鍵候補算出手段が、当該ハッシュ値Ｈと上記Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出する。
【００３０】
続いて、ＩＤ鍵生成手段が、上記ハッシュ値Ｈが上記素数ｐを法として平方剰余であるか否かを判定すると共に、上記ハッシュ値Ｈが上記素数ｑを法として平方剰余であるか否かを判定することにより、上記ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４のうち上記数ｎを法として平方剰余であるものを判定する。上記判定には、上述の、同一のグループ同士の数の積をとると、その数は必ずｎを法として平方剰余になるという性質を利用している。続いて、上記平方剰余と判定された候補をＺとし、上記数ｎを法とした当該候補Ｚの平方根を算出し、当該平方根をＩＤ鍵Ｔとする。上記の平方根の算出は、ラビン暗号の復号方法と同様に、以下の方法により行う。まず、次の４つの式によりｓ１，ｓ２，ｓ３，ｓ４を算出する。
ｓ１＝Ｚ（ｐ＋１）／４  ｍｏｄ  ｐ
ｓ２＝（ｐ−Ｚ（ｐ＋１）／４）  ｍｏｄ  ｐ
ｓ３＝Ｚ（ｐ＋１）／４  ｍｏｄ  ｑ
ｓ４＝（ｑ−Ｚ（ｐ＋１）／４）  ｍｏｄ  ｑ
【００３１】
次に、ａ＝ｑ（ｑ−１  ｍｏｄ  ｐ）とｂ＝ｐ（ｐ−１  ｍｏｄ  ｑ）を求める。次に、上記ｓ１，ｓ２，ｓ３，ｓ４，ａ，ｂから、上記数ｎを法とした当該候補Ｚの平方根を次の式により４つ求める。
Ｔ１＝（ａｓ１＋ｂｓ３）  ｍｏｄ  ｎ
Ｔ２＝（ａｓ１＋ｂｓ４）  ｍｏｄ  ｎ
Ｔ３＝（ａｓ２＋ｂｓ３）  ｍｏｄ  ｎ
Ｔ４＝（ａｓ２＋ｂｓ４）  ｍｏｄ  ｎ
【００３２】
そして、これら４つの平方根のうち、１つを任意に選択する。
【００３３】
続いて、ＩＤ鍵発行手段が、上記生成されたＩＤ鍵Ｔを、当該ＩＤ鍵Ｔに対応するＩＤを送付したＩＤ証明装置に対して発行する。
【００３４】
上記ＩＤ鍵Ｔを発行されたＩＤ証明装置では、ＩＤ鍵取得手段が、ＩＤ鍵Ｔを対話証明手続の際の秘密情報として、取得する。ＩＤ鍵の生成の処理は以上である。
【００３５】
次に、ＩＤの正当性の検証の処理を説明する。まず、ＩＤ検証装置において、公開鍵取得手段が、ＩＤ鍵発行装置により公開された公開鍵を取得する。一方、ＩＤ証明装置でも、公開鍵取得手段が、ＩＤ鍵発行装置により公開された公開鍵を取得する。なお、ＩＤ証明装置での上記公開鍵取得は、対話証明手続の際に用いる数ｎを取得するためのものであり、他の方法（ＩＤ鍵の取得と同時に取得する等）により当該数ｎを取得してもよい。
【００３６】
続いて、ＩＤ証明装置では、ＩＤ送信手段が、証明対象となるＩＤを、ＩＤ検証装置に送信する。当該送信されたＩＤ検証装置では、検証対象ＩＤ取得手段が、当該ＩＤを取得する。
【００３７】
続いて、ハッシュ値算出手段が、当該ＩＤを、ＩＤ鍵発行装置で用いられるハッシュ関数と同一の、予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出する。続いて、対話証明手続用情報算出手段が、当該ハッシュ値Ｈと、上記取得した公開鍵の要素である数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、対話証明手続用情報として数Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出する。
【００３８】
続いて、ＩＤ証明装置では、ＩＤ正当性証明手段が、自装置に上記ＩＤ鍵Ｔを保持しているか否かを、数ｎを用いた、ＩＤ検証装置との平方剰余に基づいたゼロ知識対話証明手続によって証明することにより、上記証明対象となるＩＤの正当性の証明を行う。一方、ＩＤ検証装置では、ＩＤ正当性検証手段が、上記数ｎを法とした上記数Ｚ１，Ｚ２，Ｚ３，Ｚ４のいずれかの平方根を、ＩＤ証明装置がＩＤ鍵Ｔとして保持しているか否かを、ＩＤ証明装置との平方剰余に基づいたゼロ知識対話証明手続によって確認することにより、上記ＩＤの正当性の検証を行う。即ち、ＩＤ正当性証明手段は、乱数ＲＩＤを生成し、Ｘ＝ＲＩＤ２  ｍｏｄ  ｎを計算し、得られたＸをＩＤ検証装置に送る（図１のＳ２に対応する）。ＩＤ正当性検証手段は、ｂとして“０”又は“１”のうち何れかを二者択一的にランダムに選び、選んだｂをＩＤ証明装置に送る（図１のＳ３に対応する）。ＩＤ正当性証明手段は、次のＹをＩＤ検証装置に送る。ｂ=０のとき、Ｙ=ＲＩＤであり、ｂ＝１のとき、Ｙ=ＴＲＩＤ  ｍｏｄ  ｎである（図１のＳ４に対応する）。ＩＤ検証装置は、次式が成立するか否かを検査する。即ち、ｂ=０のときは、Ｘ=Ｙ２  ｍｏｄ  ｎが成立するか。ｂ=１のときは、ＺＸ=Ｙ２  ｍｏｄ  ｎ（ＺはＺ１，Ｚ２，Ｚ３，Ｚ４のいずれか）が成立するか（図１のＳ５に対応する）。
【００３９】
上述のように、Ｚ１，Ｚ２，Ｚ３，Ｚ４のいずれかは必ずｎを法とした平方根を持つ。ＩＤ検証装置は、ＩＤ鍵発行装置が生成した素数ｐ及びｑを知らないので、Ｚ１，Ｚ２，Ｚ３，Ｚ４のうちどれが平方根を持つかはわからないが、ＩＤ証明装置が保持しているＩＤ鍵Ｔ（対話証明手続における秘密情報に該当する）がＺ１，Ｚ２，Ｚ３，Ｚ４のどれかの平方根となっているか否かをＺ１，Ｚ２，Ｚ３，Ｚ４をそれぞれ平方剰余問題におけるＺ（図１のＳ５の式に対応する）として試し確認することにより、ＩＤの正当性を検証することができる。
【００４０】
上記により、本発明によれば、ＩＤ検証装置はＩＤ鍵発行装置が公開する１つの公開鍵を用いて、ＩＤ証明装置毎の公開鍵を必要とせずにＩＤの正当性を検証できる。
【００４１】
ところで、本発明は上記のように装置の発明として記述できる他に、以下のように方法の発明としても記述することができる。これはカテゴリーが異なるだけで、実質的に同一の発明であり、同様の作用・効果を奏する。
【００４２】
即ち、本発明に係るＩＤ鍵発行方法は、素数生成手段が、２つの素数ｐ及びｑを生成する素数生成ステップと、乱数生成手段が、乱数Ｒを生成する乱数生成ステップと、公開鍵要素定義手段が、上記乱数Ｒが上記素数ｐを法として平方剰余であるか否かを判定すると共に、上記乱数Ｒが上記素数ｑを法として平方剰余であるか否かを判定することにより、上記乱数Ｒから、上記素数ｐを法としても上記素数ｑを法としても平方剰余である数Ｍ１と、上記素数ｐを法としたら平方剰余であり上記素数ｑを法としたら平方剰余でない数Ｍ２と、上記素数ｐを法としたら平方剰余でなく上記素数ｑを法としたら平方剰余である数Ｍ３と、上記素数ｐを法としても上記素数ｑを法としても平方剰余でない数Ｍ４とを公開鍵の要素として定義する公開鍵要素定義ステップと、公開鍵生成手段が、上記素数ｐとｑとを乗算し、当該乗算で得られた数ｎと、上記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とを公開鍵として生成する公開鍵生成ステップと、公開鍵公開手段が、上記公開鍵生成ステップにより生成された公開鍵を公開する公開鍵公開ステップとを備えることを特徴とする。
【００４３】
また、本発明に係るＩＤ鍵発行方法は、ＩＤ取得手段が、証明対象となるＩＤを取得するＩＤ取得ステップと、ハッシュ値算出手段が、上記ＩＤ受信ステップにより受信されたＩＤを予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出するハッシュ値算出ステップと、ＩＤ鍵候補算出手段が、上記ハッシュ値算出ステップにより算出されたハッシュ値Ｈと、上記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出するＩＤ鍵候補算出ステップと、ＩＤ鍵生成手段が、上記ハッシュ値Ｈが上記素数ｐを法として平方剰余であるか否かを判定すると共に、上記ハッシュ値Ｈが上記素数ｑを法として平方剰余であるか否かを判定することにより、上記ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４のうち上記数ｎを法として平方剰余であるものを判定し、当該平方剰余であると判定されたものを候補Ｚとし、上記数ｎを法とした当該候補Ｚの平方根を算出し、当該平方根をＩＤ鍵ＴとするＩＤ鍵生成ステップと、ＩＤ鍵発行手段が、上記ＩＤ鍵生成ステップにより生成されたＩＤ鍵Ｔを発行するＩＤ鍵発行ステップとを更に備える構成とすることが望ましい。
【００４４】
また、本発明に係るＩＤ検証方法は、公開鍵取得手段が、素数ｐとｑとを乗算して得られる数ｎと、上記素数ｐを法としても上記素数ｑを法としても平方剰余である数Ｍ１と、上記素数ｐを法としたら平方剰余であり上記素数ｑを法としたら平方剰余でない数Ｍ２と、上記素数ｐを法としたら平方剰余でなく上記素数ｑを法としたら平方剰余である数Ｍ３と、上記素数ｐを法としても上記素数ｑを法としても平方剰余でない数Ｍ４とを要素とする公開鍵を取得する公開鍵取得ステップと、検証対象ＩＤ取得手段が、ＩＤ証明装置から、検証対象となるＩＤを取得する検証対象ＩＤ取得ステップと、ハッシュ値算出手段が、上記検証対象ＩＤ受信ステップにより受信されたＩＤを、上記公開鍵を生成するＩＤ鍵発行方法で用いられるハッシュ関数と同一の、予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出するハッシュ値算出ステップと、対話証明手続用情報算出手段が、上記ハッシュ値算出ステップにより算出されたハッシュ値Ｈと、上記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、対話証明手続用情報として数Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出する対話証明手続用情報算出ステップと、ＩＤ正当性検証手段が、上記数ｎを法とした上記数Ｚ１，Ｚ２，Ｚ３，Ｚ４のいずれかの平方根を、ＩＤ証明装置がＩＤ鍵Ｔとして保持しているか否かを、ＩＤ証明装置との平方剰余に基づいたゼロ知識対話証明手続によって確認することにより、上記検証対象ＩＤ受信ステップにより受信されたＩＤの正当性の検証を行うＩＤ正当性検証ステップとを備えることを特徴とする。
【００４５】
また、本発明に係るＩＤ証明方法は、ＩＤ送信手段が、証明対象となるＩＤを送信するＩＤ送信ステップと、ＩＤ鍵取得手段が、上記証明対象となるＩＤに基づいて生成されたＩＤ鍵Ｔを取得するＩＤ鍵取得ステップと、公開鍵取得手段が、素数ｐとｑとを乗算して得られる数ｎを要素に含む公開鍵を取得する公開鍵取得ステップと、ＩＤ正当性証明手段が、自装置に上記ＩＤ鍵Ｔを保持しているか否かを、上記数ｎを用いた、ＩＤ検証装置との平方剰余に基づいたゼロ知識対話証明手続によって証明することにより、上記証明対象となるＩＤの正当性の証明を行うＩＤ正当性証明ステップとを備えることを特徴とする。
【発明の効果】
【００４６】
上記により、本発明によれば、ＩＤ検証装置はＩＤ鍵発行装置が公開する１つの公開鍵を用いて、ＩＤ証明装置毎の公開鍵を必要とせずに、任意のＩＤ証明装置のＩＤの正当性を検証できる。
【発明を実施するための最良の形態】
【００４７】
以下、図面を参照しながら本発明に係る実施形態について説明する。本実施形態は、クレジットカードでのオンラインショッピングのセキュリティへの適用である。即ち、カード会社の装置がＩＤ鍵発行装置に、オンラインショッピングサイトの装置がＩＤ検証装置に、カード保有者の装置がＩＤ証明装置にそれぞれ対応する。
【００４８】
図２に、本実施形態におけるＩＤ鍵発行装置１００、ＩＤ検証装置２００、ＩＤ証明装置３００の構成を示す。同図に示すように、ＩＤ鍵発行装置１００は、素数生成部１０１と、乱数生成部１０２と、公開鍵要素定義部１０３と、公開鍵生成部１０４と、公開鍵公開部１０５と、ＩＤ取得部１０６と、ハッシュ値算出部１０７と、ＩＤ鍵候補算出部１０８と、ＩＤ鍵生成部１０９と、ＩＤ鍵発行部１１０とを備える。素数生成部１０１は、２つの素数ｐ及びｑを生成する。乱数生成部１０２は、乱数Ｒを生成する。公開鍵要素定義部１０３は、乱数Ｒが素数ｐを法として平方剰余であるか否かを判定すると共に、乱数Ｒが素数ｑを法として平方剰余であるか否かを判定することにより、乱数Ｒから、素数ｐを法としても素数ｑを法としても平方剰余である数Ｍ１と、素数ｐを法としたら平方剰余であり素数ｑを法としたら平方剰余でない数Ｍ２と、素数ｐを法としたら平方剰余でなく素数ｑを法としたら平方剰余である数Ｍ３と、素数ｐを法としても素数ｑを法としても平方剰余でない数Ｍ４とを公開鍵４００の要素として定義する。公開鍵生成部１０４は、素数ｐとｑとを乗算し、当該乗算で得られた数ｎと、上記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とを公開鍵４００として生成する。公開鍵公開部１０５は、上記公開鍵４００を公開する。ＩＤ取得部１０６は、証明対象となるＩＤをＩＤ証明装置３００から取得する。ハッシュ値算出部１０７は、上記取得されたＩＤを予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出する。ＩＤ鍵候補算出部１０８は、上記算出されたハッシュ値Ｈと、上記数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出する。ＩＤ鍵生成部１０９は、上記ハッシュ値Ｈが素数ｐを法として平方剰余であるか否かを判定すると共に、上記ハッシュ値Ｈが素数ｑを法として平方剰余であるか否かを判定することにより、上記ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４のうち上記数ｎを法として平方剰余であるものを判定し、当該平方剰余であると判定されたものを候補Ｚとし、数ｎを法とした当該候補Ｚの平方根を算出し、当該平方根をＩＤ鍵Ｔとする。ＩＤ鍵発行部１１０は、上記生成されたＩＤ鍵Ｔを発行する。ここで、証明対象となるＩＤはクレジットカードのカード番号である。また、ハッシュ値算出部１０７で用いられるハッシュ関数はＭＤ５というアルゴリズムを用いる。ＭＤ５の場合は出力が１２８ビットなので、出力を８回連結させて１０２４ビットのハッシュ値Ｈが出力されるようにする。
【００４９】
また、ＩＤ検証装置２００は、公開鍵取得部２０１と、検証対象ＩＤ取得部２０２と、ハッシュ値算出部２０３と、対話証明手続用情報算出部２０４と、ＩＤ正当性検証部２０５とを備える。公開鍵取得部２０１は、ＩＤ鍵発行装置１００により公開された公開鍵４００を取得する。検証対象ＩＤ取得部２０２は、ＩＤ証明装置３００から、検証対象となるＩＤを取得する。ハッシュ値算出部２０３は、上記受信されたＩＤを予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出する。対話証明手続用情報算出部２０４は、上記算出されたハッシュ値Ｈと、公開鍵４００に要素として含まれる数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、対話証明手続用情報として数Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出する。ＩＤ正当性検証部２０５は、公開鍵４００に要素として含まれる数ｎを法とした上記数Ｚ１，Ｚ２，Ｚ３，Ｚ４のいずれかの平方根を、ＩＤ証明装置３００がＩＤ鍵Ｔとして保持しているか否かを、ＩＤ証明装置３００との平方剰余に基づいたゼロ知識対話証明手続によって確認することにより、上記受信されたＩＤの正当性の検証を行う。なお、ハッシュ値算出部２０３で用いられるハッシュ関数はハッシュ値算出部１０７で用いられたものと同じとする。
【００５０】
また、ＩＤ証明装置３００は、ＩＤ送信部３０１と、公開鍵取得部３０２と、ＩＤ鍵取得部３０３と、ＩＤ正当性証明部３０４とを備える。ＩＤ送信部３０１は、証明対象となるＩＤを送信する。公開鍵取得部３０２は、ＩＤ鍵発行装置１００により公開された公開鍵４００を取得する。ＩＤ鍵取得部３０３は、上記証明対象となるＩＤに基づいて生成されたＩＤ鍵Ｔを取得する。ＩＤ正当性証明部３０４は、自装置に上記ＩＤ鍵Ｔを保持しているか否かを、公開鍵４００に要素として含まれる数ｎを用いた、ＩＤ検証装置２００との平方剰余に基づいたゼロ知識対話証明手続によって証明することにより、上記証明対象となるＩＤの正当性の証明を行う。
【００５１】
公開鍵４００は、ＩＤ鍵発行装置１００により生成、公開され、上記数ｎ（＝ｐｑ）と、上記数Ｍ１，Ｍ２，Ｍ３，Ｍ４を要素とし、ＩＤの正当性の検証に用いられる。
【００５２】
以下、図３を用いて本実施形態において実行される処理を説明する。本実施形態における処理は、公開鍵の生成と公開、ＩＤ鍵の生成、及びＩＤの正当性の検証という大きく３つの処理に分けることができる。最初に、公開鍵の生成と公開の処理を説明する。
【００５３】
まず、ＩＤ鍵発行装置１００において、素数生成部１０１が、２つの素数ｐ及びｑを生成する（Ｓ０１）。素数の生成は、上述したように例えば、適当な数を選び、当該適当な数が素数か否かを判定し、素数でなければ選び直すという方法により行う。ここで、当該２つの素数ｐ及びｑの大きさ（桁数）は、それらの積の値を実用的な時間で素因数分解をするのが難しいものとする。
【００５４】
続いて、公開鍵４００の要素である数Ｍ１，Ｍ２，Ｍ３，Ｍ４を以下のように定義する（Ｓ０２）。当該定義の方法を、図４を用いて以下に説明する。
【００５５】
まず、乱数生成部１０２が、１０２４ビットの乱数Ｒを生成する（Ｓ０２１）。
【００５６】
続いて、公開鍵要素定義部１０３が、上記乱数Ｒが上記素数ｐを法として平方剰余であるか否かを判定する（Ｓ０２２）。上記乱数Ｒが上記素数ｐを法として平方剰余であると判定された場合、続いて、上記乱数Ｒが上記素数ｑを法として平方剰余であるか否かを判定する（Ｓ０２３）。上記乱数Ｒが上記素数ｐを法として平方剰余であると判定され、Ｍ１が定義されていなければＭ１＝Ｒとする。Ｍ１が定義されていれば何もしない（Ｓ０２４）。同様に、図３に記載されている通りに判定及び定義を行う（Ｓ０２５〜Ｓ０２８）。各数の定義後、Ｍ１，Ｍ２，Ｍ３，Ｍ４が全て定義されていた場合は、定義の処理（Ｓ０２）を終了する。全て定義されていない場合は、Ｓ０２１に戻る。
【００５７】
上記の処理により、Ｍ１は素数ｐを法としても素数ｑを法としても平方剰余である数（当該性質を有する数の集合をグループＧ１と呼ぶ）となる。Ｍ２は素数ｐを法としたら平方剰余であり素数ｑを法としたら平方剰余でない数（Ｇ２）となる。Ｍ３は素数ｐを法としたら平方剰余でなく素数ｑを法としたら平方剰余である数（Ｇ３）となる。Ｍ４は素数ｐを法としても素数ｑを法としても平方剰余でない数（Ｇ４）となる。
【００５８】
続いて、公開鍵生成部１０４が、素数ｐとｑとを乗算し、当該乗算で得られた数ｎと、上記で得られた数Ｍ１，Ｍ２，Ｍ３，Ｍ４とを公開鍵４００として生成する（Ｓ０３）。
【００５９】
続いて、公開鍵公開部１０５が、上記公開鍵４００を公開する（Ｓ０４）。当該公開は、外部からアクセス可能なサーバに格納する等の方法により行われる。公開鍵の生成と公開の処理は以上である。
【００６０】
次に、ＩＤ鍵の生成の処理を説明する。まず、ＩＤ証明装置３００において、ＩＤ送信部３０１が、ＩＤ鍵発行装置１００に検証対象となるＩＤであるカード番号“1234 5678 9012 3456”を送信する（Ｓ０５）。ＩＤを送信されたＩＤ鍵発行装置１００では、ＩＤ取得部１０６が当該ＩＤを受信する（Ｓ０６）。
【００６１】
続いて、ハッシュ値算出部１０７が、当該ＩＤを予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出する。続いて、ＩＤ鍵候補算出部１０８が、当該ハッシュ値Ｈと上記Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出する（Ｓ０７）。
【００６２】
続いて、ＩＤ鍵生成部１０９が、上記ハッシュ値Ｈが上記素数ｐを法として平方剰余であるか否かを判定すると共に、上記ハッシュ値Ｈが上記素数ｑを法として平方剰余であるか否かを判定することにより、上記ＩＤ鍵の候補Ｚ１，Ｚ２，Ｚ３，Ｚ４のうち上記数ｎを法として平方剰余であるものを判定する。上記判定には、上述の、同一のグループ同士の数の積をとると、その数は必ずｎを法として平方剰余になるという性質を利用している。続いて、上記平方剰余と判定された候補をＺとし、上記数ｎを法とした当該候補Ｚの平方根を算出し、当該平方根をＩＤ鍵Ｔとする（Ｓ０８）。上記の平方根の算出は、ラビン暗号の復号方法と同様に、以下の方法により行う。まず、次の４つの式によりｓ１，ｓ２，ｓ３，ｓ４を算出する。
ｓ１＝Ｚ（ｐ＋１）／４  ｍｏｄ  ｐ
ｓ２＝（ｐ−Ｚ（ｐ＋１）／４）  ｍｏｄ  ｐ
ｓ３＝Ｚ（ｐ＋１）／４  ｍｏｄ  ｑ
ｓ４＝（ｑ−Ｚ（ｐ＋１）／４）  ｍｏｄ  ｑ
【００６３】
次に、ａ＝ｑ（ｑ−１  ｍｏｄ  ｐ）とｂ＝ｐ（ｐ−１  ｍｏｄ  ｑ）を求める。次に、上記ｓ１，ｓ２，ｓ３，ｓ４，ａ，ｂから、上記数ｎを法とした当該候補Ｚの平方根を次の式により４つ求める。
Ｔ１＝（ａｓ１＋ｂｓ３）  ｍｏｄ  ｎ
Ｔ２＝（ａｓ１＋ｂｓ４）  ｍｏｄ  ｎ
Ｔ３＝（ａｓ２＋ｂｓ３）  ｍｏｄ  ｎ
Ｔ４＝（ａｓ２＋ｂｓ４）  ｍｏｄ  ｎ
【００６４】
そして、これら４つの平方根のうち、１つを任意に選択する。
【００６５】
続いて、ＩＤ鍵発行部１１０が、上記生成されたＩＤ鍵Ｔを、当該ＩＤ鍵Ｔに対応するＩＤを送付したＩＤ証明装置３００に対して発行する（Ｓ０９）。
【００６６】
上記ＩＤ鍵Ｔを発行されたＩＤ証明装置３００では、ＩＤ鍵取得部３０３が、ＩＤ鍵Ｔを対話証明手続の際の秘密情報として、取得する（Ｓ１０）。上記ＩＤ鍵の発行及び受信は、通信回線を介した通信により、行ってもよいが、安全性の確保のため、カード会社の者が郵送等で行ってもよい。ＩＤ鍵の生成の処理は以上である。
【００６７】
次に、ＩＤの正当性の検証の処理を説明する。まず、ＩＤ検証装置２００において、公開鍵取得部２０１が、ＩＤ鍵発行装置１００により公開された公開鍵４００を取得する（Ｓ１１）。一方、ＩＤ証明装置３００でも、公開鍵取得部３０２が、ＩＤ鍵発行装置１００により公開された公開鍵４００を取得する（Ｓ１２）。なお、ＩＤ証明装置３００での上記公開鍵４００取得は、対話証明手続の際に用いる数ｎを取得するためのものであり、他の方法（ＩＤ鍵の取得と同時に取得する等）により当該数ｎを取得してもよい。
【００６８】
続いて、ＩＤ証明装置３００では、ＩＤ送信部３０１が、ＩＤ検証装置２００の要求により、証明対象となるＩＤであるカード番号“1234 5678 9012 3456”を、ＩＤ検証装置２００に送信する（Ｓ１３）。当該送信されたＩＤ検証装置２００では、検証対象ＩＤ取得部２０２が、当該ＩＤを取得する（Ｓ１４）。
【００６９】
続いて、ハッシュ値算出部２０３が、当該ＩＤを予め定められたハッシュ関数で演算することによりハッシュ値Ｈを算出する。続いて、対話証明手続用情報算出部２０４が、当該ハッシュ値Ｈと、上記取得した公開鍵の要素である数Ｍ１，Ｍ２，Ｍ３，Ｍ４とをそれぞれ乗算し、対話証明手続用情報として数Ｚ１，Ｚ２，Ｚ３，Ｚ４を算出する（Ｓ１５）。
【００７０】
続いて、ＩＤ証明装置３００では、ＩＤ正当性証明部３０４が、自装置に上記ＩＤ鍵Ｔを保持しているか否かを、数ｎを用いた、ＩＤ検証装置２００との平方剰余に基づいたゼロ知識対話証明手続によって証明することにより、上記証明対象となるＩＤの正当性の証明を行う。一方、ＩＤ検証装置２００では、ＩＤ正当性検証部２０５が、上記数ｎを法とした上記数Ｚ１，Ｚ２，Ｚ３，Ｚ４のいずれかの平方根を、ＩＤ証明装置３００がＩＤ鍵Ｔとして保持しているか否かを、ＩＤ証明装置３００との平方剰余に基づいたゼロ知識対話証明手続によって確認することにより、上記ＩＤの正当性の検証を行う（Ｓ１６）。即ち、ＩＤ正当性証明部３０４は、乱数ＲＩＤを生成し、Ｘ＝ＲＩＤ２  ｍｏｄ  ｎを計算し、得られたＸをＩＤ検証装置２００に送る（図１のＳ２に対応する）。ＩＤ正当性検証部２０５は、ｂとして“０”又は“１”のうち何れかを二者択一的にランダムに選び、選んだｂをＩＤ証明装置３００に送る（図１のＳ３に対応する）。ＩＤ正当性証明部３０４は、次のＹをＩＤ検証装置２００に送る。ｂ=０のとき、Ｙ=ＲＩＤであり、ｂ＝１のとき、Ｙ=ＴＲＩＤ  ｍｏｄ  ｎである（図１のＳ４に対応する）。ＩＤ検証装置２００は、次式が成立するか否かを検査する。即ち、ｂ=０のときは、Ｘ=Ｙ２  ｍｏｄ  ｎが成立するか。ｂ=１のときは、ＺＸ=Ｙ２  ｍｏｄ  ｎ（ＺはＺ１，Ｚ２，Ｚ３，Ｚ４のいずれか）が成立するか（図１のＳ５に対応する）。
【００７１】
上述のように、Ｚ１，Ｚ２，Ｚ３，Ｚ４のいずれかは必ずｎを法とした平方根を持つ。ＩＤ検証装置２００は、ＩＤ鍵発行装置１００が生成した素数ｐ及びｑを知らないので、Ｚ１，Ｚ２，Ｚ３，Ｚ４のうちどれが平方根を持つかはわからないが、ＩＤ証明装置３００が保持しているＩＤ鍵Ｔ（対話証明手続における秘密情報に該当する）がＺ１，Ｚ２，Ｚ３，Ｚ４のどれかの平方根となっているか否かをＺ１，Ｚ２，Ｚ３，Ｚ４をそれぞれ平方剰余問題におけるＺ（図１のＳ５の式に対応する）として試し確認することにより、ＩＤの正当性を検証することができる。
【００７２】
上記により、本発明によれば、ＩＤ検証装置２００はＩＤ鍵発行装置１００が公開する１つの公開鍵を用いて、ＩＤ証明装置３００毎の公開鍵を必要とせずに、任意のＩＤ証明装置３００のＩＤの正当性を検証できる。
【００７３】
即ち、オンラインショッピングサイトの装置では、カード会社の装置が生成する１つの公開鍵を用いて、任意のカード保有者のカード番号の正当性を検証できる。また、カード保有者は安全にオンラインショッピングを行うことができる。
【図面の簡単な説明】
【００７４】
【図１】対話証明方式のシーケンス図である。
【図２】本発明の実施形態における、ＩＤ鍵発行装置、ＩＤ検証装置及びＩＤ証明装置の構成図である。
【図３】実施形態における処理を示す流れ図である。
【図４】公開鍵の要素Ｍ１，Ｍ２，Ｍ３，Ｍ４を定義する処理を示す流れ図である。
【符号の説明】
【００７５】
１００…ＩＤ鍵発行装置、１０１…素数生成部、１０２…乱数生成部、１０３…公開鍵要素定義部、１０４…公開鍵生成部、１０５…公開鍵公開部、１０６…取得部、１０７…ハッシュ値算出部、１０８…ＩＤ鍵候補算出部、１０９…ＩＤ鍵生成部、１１０…ＩＤ鍵発行部、２００…ＩＤ検証装置、２０１…公開鍵取得部、２０２…検証対象ＩＤ取得部、２０３…ハッシュ値算出部、２０４…対話証明手続用情報算出部、２０５      正当性検証部、３００…ＩＤ証明装置、３０１…ＩＤ送信部、３０２…公開鍵取得部、３０３…ＩＤ鍵取得部、３０４…正当性証明部、４００…公開鍵。
【図１】
2005167385.tif 000003
【図２】
2005167385.tif 000004
【図３】
2005167385.tif 000005
【図４】
2005167385.tif 000006