(57)【特許請求の範囲】
【請求項１】
ｎ台（ｎ≧３）の通信機からなる同報通信可能な通信システムにおける認証方法において、前記通信機のうち認証されることを望む通信機は、あらかじめ、所定の大きさの素数ｐ，ｑとその合成数Ｎ（＝ｐ×ｑ）と任意の整数ｓ（１≦ｓ≦Ｎ−１）と整数ｖ（ｓ2×ｖ mod N＝１）を生成して、前記ｐ，ｑ，ｓを秘密鍵として安全に保管し、前記Ｎ，ｖを公開鍵として公開し、認証の繰返し回数をｗと定め、認証を受ける際には、前記認証されることを望む通信機を除く通信機のＩＤをｊ（１≦ｊ≦ｎ−１）とし、
(１)前記認証されることを望む通信機は、前記認証されることを望む通信機を除く通信機ｊ（１≦ｊ≦ｎ−１）に対して、
・ｎ≧ｗの場合：ｎ−１個の乱数ｒjを生成して前半情報
Ｘj＝ｒj2 mod N（１≦ｊ≦ｎ−１）
を計算して同報通信し、
・ｎ＜ｗの場合：ｗ個の乱数ｒ1，…，ｒwを生成してｗ個の前半情報
Ｘj＝ｒj2 mod N，
Ｘj+n-1＝ｒj+n-12 mod N，
Ｘj+2(n-1)＝ｒj+2(n-1)2 mod N，…
を計算して同報通信し、
(２)前記認証されることを望む通信機を除く通信機ｊ（１≦ｊ≦ｎ−１）は、
・ｎ≧ｗの場合：自身のＩＤに対応した前記前半情報Ｘjを保持し、値が“０”または“１”の乱数ｅjを同報通信し、
・ｎ＜ｗの場合：自身のＩＤに対応した前記前半情報Ｘj，Ｘj+n-1，Ｘj+2(n-1)，…を保持し、値が“０”または“１”の乱数ｅj，ｅj+n-1，ｅj+2(n-1)，…を同報通信し、
(３)前記認証されることを望む通信機は、
・ｎ≧ｗの場合：ｅjを用いてｎ−１個の検証情報
Ｙj＝ｒj×ｓej mod Nを計算して同報通信し、
・ｎ＜ｗの場合：ｅj，ｅj+n-1，ｅj+2(n-1)，…を用いてｗ個の検証情報
Ｙj＝ｒj×ｓej mod N，
Ｙj+n-1＝ｒj×ｓej+n-1 mod N，
Ｙj+2(n-1)＝ｒj×ｓej+2(n-1) mod N，…
を計算して同報通信し、
(４)前記認証されることを望む通信機を除く通信機ｊは、
・ｎ≧ｗの場合：検証式
Ｙj2×ｖej mod N＝Ｘj
が成り立つことを確認し、
・ｎ＜ｗの場合：検証式
Ｙj2×ｖej mod N＝Ｘj，
Ｙj+n-12×ｖej+n-1 mod N＝Ｘj+n-1，
Ｙj+2(n-1)2×ｖej+2(n-1) mod N＝Ｘj+2(n-1)，…
が成り立つことを確認し、成り立たない場合は、不成立であることを同報通信し、成り立つ場合には、他の認証されることを望む通信機を除く通信機から不成立であることが同報通信されないかぎりは、認証したとすることを特徴とする認証方法。
【請求項２】
ｎ台（ｎは３以上の整数）の通信機からなる同報通信可能な通信システムにおける認証方法において、前記通信機のうち認証されることを望む通信機は、あらかじめ、所定の大きさの素数ｐ，ｑとその合成数Ｎ（＝ｐ×ｑ）と任意の整数ｓ（１≦ｓ≦Ｎ−１）と整数ｖ（ｓ2×ｖmod N＝１）を生成して、前記ｐ，ｑ，ｓを秘密鍵として安全に保管し、前記Ｎ，ｖを公開鍵として公開し、任意の圧縮関数ｈ( ‖ ‖…‖ )を公開し、認証の繰返し回数をｗと定め、認証を受ける際には、前記認証されることを望む通信機を除く通信機のＩＤをｊ（１≦ｊ≦ｎ−１）とし、
(１)前記認証されることを望む通信機は、前記認証されることを望む通信機を除く通信機ｊ（１≦ｊ≦ｎ−１）に対して、
・ｎ≧ｗの場合：ｎ−１個の乱数ｒjを生成してｎ−１個の前半情報
Ｘj＝ｈ(ｒj2 mod N)
を計算して同報通信し、
・ｎ＜ｗの場合：ｗ個の乱数ｒ1，…，ｒwを生成してｎ−１個の前半情報
Ｘj＝ｈ(ｒj2 mod N‖ｒj+n-12 mod N‖ｒi+2(n-1)2 mod N‖…)
を計算して同報通信し、
(２)前記証認証されることを望む通信機を除く通信機ｊ（１≦ｊ≦ｎ−１）は、
・ｎ≧ｗの場合：自身のＩＤに対応した前記前半情報Ｘjを保持し、値が“０”または“１”の乱数ｅjを同報通信し、
・ｎ＜ｗの場合：自身のＩＤに対応した前記前半情報Ｘjを保持し、値が“０”または“１”の乱数ｅj，ｅj+n-1，ｅj+2(n-1)，…を同報通信し、
(３)前記認証されることを望む通信機は、
・ｎ≧ｗの場合：ｅjを用いてｎ−１個の検証情報
Ｙj＝ｒj×ｓej mod N（１≦ｊ≦ｎ−１）
を計算して同報通信し、
・ｎ＜ｗの場合：ｅj，ｅj+n-1，ｅj+2(n-1)，…（１≦ｊ≦ｎ−１）を用いてｗ個の検証情報
Ｙj＝ｒj×ｓej mod N，
Ｙj+n-1＝ｒj×ｓej+n-1 mod N，
Ｙj+2(n-1)＝ｒj×ｓej+2(n-1) mod N，…（１≦ｊ≦ｎ−１）
を計算して同報通信し、
(４) 認証されることを望む通信機を除く通信機ｊは、
・ｎ≧ｗの場合：検証式
ｈ(Ｙj2×ｖej mod N)＝Ｘj
が成り立つことを確認し、
・ｎ＜ｗの場合：検証式
ｈ(Ｙj2×ｖej mod N‖Ｙj+n-12×ｖej+n-1 mod N
‖Ｙj+2(n-1)2×ｖej+2(n-1) mod N‖…)＝Ｘj
が成り立つことを確認し、成り立たない場合は、不成立であることを同報通信し、成り立つ場合には、他の認証されることを望む通信機を除く通信機から不成立であることが同報通信されないかぎりは、認証したとすることを特徴とする認証方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、認証方法に関し、特に、複数の通信機からなる同報通信可能な通信システムにおける認証方法に関する。
【０００２】
【従来の技術】
従来、認証方式の１つとして、並列Ｆｉａｔ−Ｓｈａｍｉｒ法が知られている（詳細は、今井秀樹著「暗号のおはなし」，日本規格協会，ｐｐ１４７−１５２を参照）。この方式は、安全性が高く演算量も少ないが、データ通信量や通信回数が多い。図６に、１対１の通信システムにおける従来の認証方式の構成を示し、図７〜図１０に、複数の通信機からなる同報通信可能な通信システムに、単純に並列Ｆｉａｔ−Ｓｈａｍｉｒ法を適用した構成を示す。
【０００３】
図６を参照して、１対１の通信システムにおける従来のＦｉａｔ−Ｓｈａｍｉｒ法による認証方法を説明する。信頼できる第３者の証明センターは、大きな素数ｐ，ｑを生成して秘密に保持するとともに、合成数Ｎ（＝ｐ×ｑ）を公開する。秘密鍵ｓ（１≦ｓ≦Ｎ−１）を生成して、認証されることを望む通信機１（以下証明者という）に秘密に保持させるとともに、公開鍵ｖ（ｓ２×ｖ  ｍｏｄ  Ｎ＝１）を計算して公開する。秘密鍵ｓを保持している者が本人であり、検証者２は、公開鍵ｖを使って証明者が秘密鍵ｓを保持しているか否かを、秘密鍵ｓを知ることなく検証する。
【０００４】
証明者１と検証者２の間で、認証の繰返し回数ｗを決める。証明者１は、ｗ個の乱数ｒｉ（１≦ｉ≦ｗ）を生成し、
Ｘｉ＝ｒｉ２  ｍｏｄ  Ｎ（１≦ｉ≦ｗ）
を計算して、検証者２にｗ個の乱数ｒｉ（１≦ｉ≦ｗ）を送る。検証者２は、ｗ個のＸｉ（１≦ｉ≦ｗ）を受信すると、値が“０”または“１”のｗ個の乱数ｅｉ（１≦ｉ≦ｗ）を生成して、ｗ個のｅｉ（１≦ｉ≦ｗ）を証明者１に送る。証明者１は、
Ｙｉ＝ｒｉ×ｓｅｉ  ｍｏｄ  Ｎ（１≦ｉ≦ｗ）
を計算して、検証者２にｗ個のＹｉ（１≦ｉ≦ｗ）を送る。検証者２は、
Ｙｉ２×ｖｅｉ≡Ｘｉ（ｍｏｄ  Ｎ）（１≦ｉ≦ｗ）
を検証する。ｗ回の検証が成功すれば、検証者２は、１−（１／２）ｗの確率で、証明者１が公開鍵ｖに対応する秘密鍵ｓを保持していること、すなわち本人であることを確認できる。１回でも検証に失敗すれば、証明者１は本人でないことがわかる。
【０００５】
図７〜図１０を参照して、並列Ｆｉａｔ−Ｓｈａｍｉｒ法による認証方法を説明する。信頼できる第３者の証明センターは、大きな素数ｐ，ｑを生成して秘密に保持するとともに、合成数Ｎ（＝ｐ×ｑ）を公開する。通信機数ｎ＝５とする。１台の通信機を証明者１とし、４台の通信機を検証者２とする。証明センターは、秘密鍵ｓ（１≦ｓ≦Ｎ−１）を生成して、証明者１に秘密に保持させるとともに、公開鍵ｖ（ｓ２×ｖ  ｍｏｄ  Ｎ＝１）を計算して公開する。証明者１と検証者２の間で、認証の繰返し回数ｗ＝８を決める。
【０００６】
図７に示すステップ（１）において、証明者１は、８×４個の乱数ｒｊｗ（１≦ｊ≦４，１≦ｗ≦８）を生成し、
Ｘｊｗ＝ｒｊｗ２  ｍｏｄ  Ｎ
を計算して検証者２に同報する。ｊ番目の検証者２（検証者ｊ）は、Ｘｊ１〜Ｘｊ８を受信する（１≦ｊ≦４）。
【０００７】
図８に示すステップ（２）において、検証者ｊは、乱数ｅｊ１〜ｅｊ８（１≦ｊ≦４）を発生して、証明者１に送る。証明者１は、ｅｊｗ（１≦ｊ≦４，１≦ｗ≦８）を受信する。
【０００８】
図９に示すステップ（３）において、証明者１は、
Ｙｊｗ＝ｒｊｗ×ｓｅｊｗ  ｍｏｄ  Ｎ（１≦ｊ≦４，１≦ｗ≦８）
を計算して、検証者２に同報する。検証者ｊは、Ｙｊ１〜Ｙｊ８（１≦ｊ≦４）を受信する。
【０００９】
図１０に示すステップ（４）において、検証者ｊは、
Ｙｊｗ２×ｖｅｊｗ≡Ｘｊｗ（ｍｏｄ  Ｎ）（１≦ｊ≦４，１≦ｗ≦８）
が成立するか否か検査する。各検証者２がすべての検証に成功すれば、１−（１／２）８の確率で、各検証者は証明者１が公開鍵ｖに対応する秘密鍵ｓを保持していること、すなわち本人であることを確認できる。
【００１０】
【発明が解決しようとする課題】
しかしながら、上記従来の認証方式においては、データ通信量や通信回数が多く、実用上は効率が悪いという欠点がある。特に、この方式を同報通信システムに単純に適用すると、非常にトラフィックが大きくなるという問題を有していた。
【００１１】
本発明は、上記従来の問題を解決するもので、並列Ｆｉａｔ−Ｓｈａｍｉｒ法を用いた認証方法において、データ通信量と通信回数および演算量を削減して、高速に認証を行なうことを目的とする。
【００１２】
【課題を解決するための手段】
上記問題を解決するために、本発明では、複数台の通信機からなる通信システムにおける認証方法を、通信機のうち認証されることを望む通信機（証明者）は、あらかじめ、所定の大きさの素数ｐ，ｑとその合成数Ｎ（＝ｐ×ｑ）と任意の整数ｓ（１≦ｓ≦Ｎ−１）と整数ｖ（ｓ２×ｖ  ｍｏｄ  Ｎ＝１）を生成して、ｐ，ｑ，ｓを秘密鍵として安全に保管し、Ｎ，ｖを公開鍵として公開し、任意の圧縮関数ｈ（  ‖  ‖…‖  ）を公開し、認証の繰返し回数をｗと定め、認証を受ける際には、（１）証明者は、ｗ個の乱数ｒｉ（１≦ｉ≦ｗ）を生成し、前半情報  Ｘ＝ｈ（ｒ１２  ｍｏｄ  Ｎ‖ｒ２２  ｍｏｄ  Ｎ‖…‖ｒｗ２  ｍｏｄ  Ｎ）  を計算して通信機のうち検証を依頼する通信機（検証者）に送信し、（２）検証者は、値が“０”または“１”のｗ個の乱数ｅｉ（１≦ｉ≦ｗ）を生成して証明者に送信し、（３）証明者は、ｗ個の検証情報  Ｙ１＝ｒ１×ｓｅ１  ｍｏｄ  Ｎ，Ｙ２＝ｒ２×ｓｅ２  ｍｏｄ  Ｎ，…，Ｙｗ＝ｒｗ×ｓｅｗ  ｍｏｄ  Ｎ  を計算して検証者に送信し、（４）検証者は検証式  ｈ（Ｙ１２×ｖｅ１  ｍｏｄ  Ｎ‖Ｙ２２×ｖｅ２  ｍｏｄ  Ｎ‖…‖Ｙｗ２×ｖｅｗ  ｍｏｄ  Ｎ）＝Ｘ  が成り立つことを検算し、成り立つ場合には証明者を認証し、成り立たない場合には証明者を認証しない構成とした。
【００１３】
このように構成したことにより、証明者から検証者へのデータ通信量と通信回数を削減することができる。
【００１４】
また、（１）証明者は、検証者ｊ（１≦ｊ≦ｎ−１）に対して、ｎ≧ｗの場合は、ｎ−１個の乱数ｒｊを生成して前半情報  Ｘｊ＝ｒｊ２  ｍｏｄ  Ｎ（１≦ｊ≦ｎ−１）を計算して同報通信し、ｎ＜ｗの場合は、ｗ個の乱数ｒ１，…，ｒｗを生成してｗ個の前半情報  Ｘｊ＝ｒｊ２  ｍｏｄ  Ｎ，  Ｘｊ＋ｎ−１＝ｒｊ＋ｎ−１２  ｍｏｄ  Ｎ，  Ｘｊ＋２（ｎ−１）＝ｒｊ＋２（ｎ−１）２  ｍｏｄ  Ｎ，…  を計算して同報通信し、（２）検証者ｊ（１≦ｊ≦ｎ−１）は、ｎ≧ｗの場合は自身のＩＤに対応した前半情報Ｘｊを保持し、値が“０”または“１”の乱数ｅｊを同報通信し、ｎ＜ｗの場合は自身のＩＤに対応した前半情報Ｘｊ，Ｘｊ＋ｎ−１，Ｘｊ＋２（ｎ−１），…を保持し、値が“０”または“１”の乱数ｅｊ，ｅｊ＋ｎ−１，ｅｊ＋２（ｎ−１），…を同報通信し、（３）証明者は、ｎ≧ｗの場合はｅｊを用いてｎ−１個の検証情報  Ｙｊ＝ｒｊ×ｓｅｊ  ｍｏｄ  Ｎ  を計算して同報通信し、ｎ＜ｗの場合はｅｊ，ｅｊ＋ｎ−１，ｅｊ＋２（ｎ−１），…を用いてｗ個の検証情報  Ｙｊ＝ｒｊ×ｓｅｊ  ｍｏｄ  Ｎ，  Ｙｊ＋ｎ−１＝ｒｊ×ｓｅｊ＋ｎ−１  ｍｏｄ  Ｎ，  Ｙｊ＋２（ｎ−１）＝ｒｊ×ｓｅｊ＋２（ｎ−１）  ｍｏｄ  Ｎ，…  を計算して同報通信し、（４）検証者ｊは、ｎ≧ｗの場合は検証式  Ｙｊ２×ｖｅｊ  ｍｏｄ  Ｎ＝Ｘｊ  が成り立つことを確認し、ｎ＜ｗの場合は検証式  Ｙｊ２×ｖｅｊ  ｍｏｄ  Ｎ＝Ｘｊ，  Ｙｊ＋ｎ−１２×ｖｅｊ＋ｎ−１  ｍｏｄ  Ｎ＝Ｘｊ＋ｎ−１，Ｙｊ＋２（ｎ−１）２×ｖｅｊ＋２（ｎ−１）  ｍｏｄ  Ｎ＝Ｘｊ＋２（ｎ−１），…  が成り立つことを確認し、成り立たない場合は、不成立であることを同報通信し、成り立つ場合には、他の検証者から不成立であることが同報通信されないかぎりは、認証したとする構成とした。
【００１５】
このように構成したことにより、証明者から検証者への通信量と検証者の演算量を削減できる。
【００１６】
また、（１）証明者は、検証者ｊ（１≦ｊ≦ｎ−１）に対して、ｎ≧ｗの場合はｎ−１個の乱数ｒｊを生成してｎ−１個の前半情報  Ｘｊ＝ｈ（ｒｊ２  ｍｏｄ  Ｎ）  を計算して同報通信し、ｎ＜ｗの場合はｗ個の乱数ｒ１，…，ｒｗを生成してｎ−１個の前半情報  Ｘｊ＝ｈ（ｒｊ２  ｍｏｄ  Ｎ‖ｒｊ＋ｎ−１２  ｍｏｄ  Ｎ‖ｒｉ＋２（ｎ−１）２  ｍｏｄ  Ｎ‖…）を計算して同報通信し、（２）証検証者ｊ（１≦ｊ≦ｎ−１）は、ｎ≧ｗの場合は自身のＩＤに対応した前半情報Ｘｊを保持し、値が“０”または“１”の乱数ｅｊを同報通信し、ｎ＜ｗの場合は自身のＩＤに対応した前半情報Ｘｊを保持し、値が“０”または“１”の乱数ｅｊ，ｅｊ＋ｎ−１，ｅｊ＋２（ｎ−１），…を同報通信し、（３）証明者は、ｎ≧ｗの場合はｅｊを用いてｎ−１個の検証情報  Ｙｊ＝ｒｊ×ｓｅｊ  ｍｏｄ  Ｎ（１≦ｊ≦ｎ−１）  を計算して同報通信し、ｎ＜ｗの場合はｅｊ，ｅｊ＋ｎ−１，ｅｊ＋２（ｎ−１），…（１≦ｊ≦ｎ−１）を用いてｗ個の検証情報  Ｙｊ＝ｒｊ×ｓｅｊ  ｍｏｄ  Ｎ，  Ｙｊ＋ｎ−１＝ｒｊ×ｓｅｊ＋ｎ−１  ｍｏｄ  Ｎ，  Ｙｊ＋２（ｎ−１）＝ｒｊ×ｓｅｊ＋２（ｎ−１）  ｍｏｄ  Ｎ，…（１≦ｊ≦ｎ−１）  を計算して同報通信し、（４）検証者ｊは、ｎ≧ｗの場合は検証式  ｈ（Ｙｊ２×ｖｅｊ  ｍｏｄ  Ｎ）＝Ｘｊ  が成り立つことを確認し、ｎ＜ｗの場合は検証式  ｈ（Ｙｊ２×ｖｅｊ  ｍｏｄ  Ｎ‖Ｙｊ＋ｎ−１２×ｖｅｊ＋ｎ−１  ｍｏｄ  Ｎ‖Ｙｊ＋２（ｎ−１）２×ｖｅｊ＋２（ｎ−１）  ｍｏｄ  Ｎ）＝Ｘｊ  が成り立つことを確認し、成り立たない場合は、不成立であることを同報通信し、成り立つ場合には、他の検証者から不成立であることが同報通信されないかぎりは、認証したとする構成とした。
【００１７】
このように構成したことにより、証明者から検証者への通信量と検証者の演算量を削減できる。
【００１８】
【発明の実施の形態】
【００１９】
本発明の請求項１に記載の発明は、ｎ台（ｎ≧３）の通信機からなる同報通信可能な通信システムにおける認証方法において、前記通信機のうち認証されることを望む通信機は、あらかじめ、所定の大きさの素数ｐ，ｑとその合成数Ｎ（＝ｐ×ｑ）と任意の整数ｓ（１≦ｓ≦Ｎ−１）と整数ｖ（ｓ2×ｖ mod N＝１）を生成して、前記ｐ，ｑ，ｓを秘密鍵として安全に保管し、前記Ｎ，ｖを公開鍵として公開し、認証の繰返し回数をｗと定め、認証を受ける際には、前記認証されることを望む通信機を除く通信機のＩＤをｊ（１≦ｊ≦ｎ−１）とし、(１)前記認証されることを望む通信機は、前記認証されることを望む通信機を除く通信機ｊ（１≦ｊ≦ｎ−１）に対して、ｎ≧ｗの場合：ｎ−１個の乱数ｒjを生成して前半情報  Ｘj＝ｒj2 mod N（１≦ｊ≦ｎ−１）  を計算して同報通信し、ｎ＜ｗの場合：ｗ個の乱数ｒ1，…，ｒwを生成してｗ個の前半情報  Ｘj＝ｒj2 mod N，  Ｘj+n-1＝ｒj+n-12 mod N，  Ｘj+2(n-1)＝ｒj+2(n-1)2 mod N，…  を計算して同報通信し、(２)前記認証されることを望む通信機を除く通信機ｊ（１≦ｊ≦ｎ−１）は、ｎ≧ｗの場合：自身のＩＤに対応した前記前半情報Ｘjを保持し、値が“０”または“１”の乱数ｅjを同報通信し、ｎ＜ｗの場合：自身のＩＤに対応した前記前半情報Ｘj，Ｘj+n-1，Ｘj+2(n-1)，…を保持し、値が“０”または“１”の乱数ｅj，ｅj+n-1，ｅj+2(n-1)，…を同報通信し、(３)前記認証されることを望む通信機は、ｎ≧ｗの場合：ｅjを用いてｎ−１個の検証情報  Ｙj＝ｒj×ｓej mod Nを計算して同報通信し、ｎ＜ｗの場合：ｅj，ｅj+n-1，ｅj+2(n-1)，…を用いてｗ個の検証情報  Ｙj＝ｒj×ｓej mod N，  Ｙj+n-1＝ｒj×ｓej+n-1 mod N，  Ｙj+2(n-1)＝ｒj×ｓej+2(n-1) mod N，…  を計算して同報通信し、(４)前記認証されることを望む通信機を除く通信機ｊは、ｎ≧ｗの場合：検証式  Ｙj2×ｖej mod N＝Ｘj  が成り立つことを確認し、ｎ＜ｗの場合：検証式  Ｙj2×ｖej mod N＝Ｘj，  Ｙj+n-12×ｖej+n-1 mod N＝Ｘj+n-1，  Ｙj+2(n-1)2×ｖej+2(n-1) mod N＝Ｘj+2(n-1)，…  が成り立つことを確認し、成り立たない場合は、不成立であることを同報通信し、成り立つ場合には、他の認証されることを望む通信機を除く通信機から不成立であることが同報通信されないかぎりは、認証したとすることを特徴とする認証方法であり、認証されることを望む通信機の通信量と認証されることを望む通信機を除く通信機の演算量を減少するという作用を有する。
【００２０】
本発明の請求項２に記載の発明は、ｎ台（ｎは３以上の整数）の通信機からなる同報通信可能な通信システムにおける認証方法において、前記通信機のうち認証されることを望む通信機は、あらかじめ、所定の大きさの素数ｐ，ｑとその合成数Ｎ（＝ｐ×ｑ）と任意の整数ｓ（１≦ｓ≦Ｎ−１）と整数ｖ（ｓ2×ｖmod N＝１）を生成して、前記ｐ，ｑ，ｓを秘密鍵として安全に保管し、前記Ｎ，ｖを公開鍵として公開し、任意の圧縮関数ｈ( ‖ ‖…‖ )を公開し、認証の繰返し回数をｗと定め、認証を受ける際には、前記認証されることを望む通信機を除く通信機のＩＤをｊ（１≦ｊ≦ｎ−１）とし、(１)前記認証されることを望む通信機は、前記認証されることを望む通信機を除く通信機ｊ（１≦ｊ≦ｎ−１）に対して、ｎ≧ｗの場合：ｎ−１個の乱数ｒjを生成してｎ−１個の前半情報  Ｘj＝ｈ(ｒj2 mod N)  を計算して同報通信し、ｎ＜ｗの場合：ｗ個の乱数ｒ1，…，ｒwを生成してｎ−１個の前半情報  Ｘj＝ｈ(ｒj2 mod N‖ｒj+n-12 mod N‖ｒi+2(n-1)2 mod N‖…)  を計算して同報通信し、(２)前記証認証されることを望む通信機を除く通信機ｊ（１≦ｊ≦ｎ−１）は、ｎ≧ｗの場合：自身のＩＤに対応した前記前半情報Ｘjを保持し、値が“０”または“１”の乱数ｅjを同報通信し、ｎ＜ｗの場合：自身のＩＤに対応した前記前半情報Ｘjを保持し、値が“０”または“１”の乱数ｅj，ｅj+n-1，ｅj+2(n-1)，…を同報通信し、(３)前記認証されることを望む通信機は、ｎ≧ｗの場合：ｅjを用いてｎ−１個の検証情報  Ｙj＝ｒj×ｓej mod N（１≦ｊ≦ｎ−１）  を計算して同報通信し、ｎ＜ｗの場合：ｅj，ｅj+n-1，ｅj+2(n-1)，…（１≦ｊ≦ｎ−１）を用いてｗ個の検証情報  Ｙj＝ｒj×ｓej mod N，  Ｙj+n-1＝ｒj×ｓej+n-1 mod N，  Ｙj+2(n-1)＝ｒj×ｓej+2(n-1) mod N，…（１≦ｊ≦ｎ−１）  を計算して同報通信し、(４)認証されることを望む通信機を除く通信機ｊは、ｎ≧ｗの場合：検証式  ｈ(Ｙj2×ｖej mod N)＝Ｘj  が成り立つことを確認し、ｎ＜ｗの場合：検証式  ｈ(Ｙj2×ｖej mod N‖Ｙj+n-12×ｖej+n-1 mod N‖Ｙj+2(n-1)2×ｖej+2(n-1) mod N‖…)＝Ｘj  が成り立つことを確認し、成り立たない場合は、不成立であることを同報通信し、成り立つ場合には、他の認証されることを望む通信機を除く通信機から不成立であることが同報通信されないかぎりは、認証したとすることを特徴とする認証方法であり、認証されることを望む通信機の通信量と認証されることを望む通信機を除く通信機の演算量を減少するという作用を有する。
【００２４】
以下、本発明の実施の形態について、図１〜図５を参照しながら詳細に説明する。
【００２５】
（第１の実施の形態）
本発明の第１の実施の形態は、証明者から検証者への前半のデータ送信の際に、ハッシュ関数で圧縮したデータを１回だけ送る認証方法である。
【００２６】
図１は、本発明の第１の実施の形態における認証方法の１対１のシステムでの手順を示す流れ図である。図１を参照して、１対１の通信システムにおける処理手順を説明する。
【００２７】
通信機のうち認証されることを望む通信機１（以下証明者という。ここでは、基地局を想定している。）は、あらかじめ、所定の大きさの素数ｐ，ｑとその合成数Ｎ（＝ｐ×ｑ）と任意の整数ｓ（１≦ｓ≦Ｎ−１）と整数ｖ（ｓ２×ｖ  ｍｏｄ  Ｎ＝１）を生成する。ｐ，ｑ，ｓを秘密鍵として安全に保管し、Ｎ，ｖを公開鍵として公開する。任意の圧縮関数ｈ（  ‖  ‖…‖  ）も公開する。
【００２８】
検証者２（移動端末を想定している。）が証明者１を認証する際に、証明者１と検証者２の間で、認証の繰返し回数ｗを決める。証明者１は、ｗ個の乱数ｒｉ（１≦ｉ≦ｗ）を生成し、
Ｘｉ＝ｒｉ２  ｍｏｄ  Ｎ（ｉ＝１〜ｗ）
Ｘ＝ｈ（Ｘ１‖Ｘ２‖・・・‖Ｘｗ）
を計算して、Ｘを検証者２に送る。検証者２は、Ｘを受信すると、値が“０”または“１”のｗ個の乱数ｅｉ（１≦ｉ≦ｗ）を生成して証明者１に送る。
【００２９】
証明者１は、
Ｙｉ＝ｒｉ×ｓｅｉ  ｍｏｄ  Ｎ（ｉ＝１〜ｗ）
を計算して、検証者２に送る。
【００３０】
検証者２は、
Ｚｉ＝Ｙｉ２×ｖｅｉ  ｍｏｄ  Ｎ（ｉ＝１〜ｗ）
を計算して、
ｈ（Ｚ１‖Ｚ２‖・・・‖Ｚｗ）＝Ｘ
を検証する。検証が成功すれば、検証者２は、１−（１／２）ｗの確率で、証明者１が公開鍵ｖに対応する秘密鍵ｓを保持していること、すなわち本人であることを確認できる。検証に失敗すれば、証明者１は本人でないことがわかる。
【００３１】
上記のように、本発明の第１の実施の形態では、認証方法を、証明者から検証者への前半のデータ送信の際に、ハッシュ関数で圧縮したデータを１回だけ送る構成としたので、並列Ｆｉａｔ−Ｓｈａｍｉｒ法の約半分の通信量で済む。
【００３２】
（第２の実施の形態）
本発明の第２の実施の形態は、証明者から検証者への前半情報を圧縮して同報通信し、複数の端末で分担して検証する認証方法である。
【００３３】
図２は、本発明の第２の実施の形態における認証方法の複数の通信機からなる同報通信可能な通信システムにおけるステップ（１）を示す図である。図３は、複数の通信機からなる同報通信可能な通信システムにおけるステップ（２）を示す図である。図４は、複数の通信機からなる同報通信可能な通信システムにおけるステップ（３）を示す図である。図５は、複数の通信機からなる同報通信可能な通信システムにおけるステップ（４）を示す図である。
【００３４】
図２〜図５を参照して、複数の通信機からなる同報通信可能な通信システムにおける処理手順を説明する。
【００３５】
５台の通信機のうち、認証されることを望む通信機１（以下証明者という。ここでは、基地局を想定している。）は、あらかじめ、所定の大きさの素数ｐ，ｑとその合成数Ｎ（＝ｐ×ｑ）と任意の整数ｓ（１≦ｓ≦Ｎ−１）と整数ｖ（ｓ２×ｖ  ｍｏｄ  Ｎ＝１）を生成する。ｐ，ｑ，ｓを秘密鍵として安全に保管し、Ｎ，ｖを公開鍵として公開する。任意の圧縮関数ｈ（  ‖  ‖…‖  ）も公開する。証明者１を除く通信機２（以下検証者という。ここでは、４台の移動端末を想定している。）と証明者１の間で、認証の繰返し回数ｗ＝８を決める。
【００３６】
図２に示すステップ（１）において、証明者１は、８個の乱数ｒｗ（１≦ｗ≦８）を生成し、
Ｚｗ＝ｒｗ２  ｍｏｄ  Ｎ（１≦ｗ≦８）
Ｘｊ＝ｈ（Ｚｊ‖Ｚｊ＋４）（ｊ＝１〜４）
を計算して検証者２に同報する。ｊ番目の検証者２（以下、検証者ｊという）は、Ｘｊを受信する（１≦ｊ≦４）。
【００３７】
図３に示すステップ（２）において、検証者ｊは、値が“０”または“１”の乱数ｅｊとｅｊ＋４（１≦ｊ≦４）を発生して、証明者１に送る。証明者１は、ｅ１〜ｅ８を受信する。
【００３８】
図４に示すステップ（３）において、証明者１は、
Ｙｗ＝ｒｗ×ｓｅｗ  ｍｏｄ  Ｎ（１≦ｗ≦８）
を計算して、検証者２に同報する。検証者ｊは、ＹｊとＹｊ＋４（１≦ｊ≦４）を受信する。
【００３９】
図５に示すステップ（４）において、検証者ｊは、
Ｕｊ＝Ｙｊ２×ｖｅｊ  ｍｏｄ  Ｎ
Ｕｊ＋４＝Ｙｊ＋４２×ｖｅｊ＋４  ｍｏｄ  Ｎ
を計算し、
ｈ（Ｕｊ‖Ｕｊ＋４）＝Ｘｊ（１≦ｊ≦４）
が成立するか否か検査する。不成立時には基地局または他の移動体端末に知らせることにより、すべての検証者２が検証に成功すれば、１−（１／２）８の確率で、証明者１が公開鍵ｖに対応する秘密鍵ｓを保持していること、すなわち本人であることを確認できる。
【００４０】
複数の通信機からなる同報通信可能な通信システムにおける本実施の形態と並列Ｆｉａｔ−Ｓｈａｍｉｒ法の通信量と演算量と通信回数を見積もって比較してみる。見積もり条件は、Ｎが１０２４ｂｉｔｓ、圧縮関数が１２８ｂｉｔの出力を行うＭＤ５とする。また、検証者が証明者に乱数を送信する確率を１／２、認証の繰返し回数ｗ＝２０、通信機数ｎ＝１１とする。以上の条件において、おおよそ本実施の形態では、検証者の演算時間が１／１０、証明者の前半の通信量が１／２、後半の通信量が１／１０、全検証者の通信回数の合計が１／２となる。
【００４１】
並列Ｆｉａｔ−Ｓｈａｍｉｒ法は、合成数Ｎが多項式時間で素因数分解できないことに安全性の根拠を求めている。本実施の形態の認証方法も、同様の部分に安全性の根拠を求めている。したがって、十分な安全性を持たせるためには、合成数Ｎの大きさを１０２４ｂｉｔ程度にとる必要性がある。本実施の形態と並列Ｆｉａｔ−Ｓｈａｍｉｒ法において、安全性が異なる可能性があるのは、圧縮関数による情報量の減少である。しかし、本実施の形態においても合成数Ｎの大きさは１０２４ｂｉｔのままであるから、これによる安全性の低下はない。
【００４２】
全数探索法による攻撃に対しても、一般的には１２８ｂｉｔもあれば十分安全であるとされているので、圧縮関数は、出力が１２８ｂｉｔ以上のものを用いれば安全である。圧縮関数に関しては、ＳＨＡ−１やＭＤ５などのハッシュ関数を用いるのが安全性の面から望ましいが、簡単化のために排他的論理和で代用することも可能である。圧縮しないで、検証を複数の端末で分担するだけでもよい。
【００４３】
また、並列Ｆｉａｔ−Ｓｈａｍｉｒの認証の繰返し回数ｗは、２０から４０にとるのが安全とされているので、本実施の形態においても２０から４０にとることで同様の安全性を保つことができる。
【００４４】
なお、検証者のうち代表検証者が、その他の全ての検証者の乱数を代りに選択して証明者に送信してもよい。また、検証者は、乱数を選ぶときに、通信状態などの負荷の度合いが高い場合や省電力状態の場合は乱数を送信しないこととし、負荷の度合いが低い場合または省電力状態でない場合は乱数を送信するようにしてもよい。この場合、証明者は、前情報を同報通信してから制限時間内に検証者が乱数を送信しない場合には、該当の乱数を“０”と見なすようにする。
【００４５】
上記のように、本発明の第２の実施の形態では、認証方法を、証明者から検証者への前半情報を圧縮して同報通信し、複数の端末で分担して検証する構成としたので、証明者と検証者との間の通信量と演算量を削減でき、高速に認証できる。
【００４６】
【発明の効果】
以上の説明から明らかなように、本発明では、複数台の通信機からなる通信システムにおける認証方法を、通信機のうち認証されることを望む通信機（証明者）は、あらかじめ、所定の大きさの素数ｐ，ｑとその合成数Ｎ（＝ｐ×ｑ）と任意の整数ｓ（１≦ｓ≦Ｎ−１）と整数ｖ（ｓ２×ｖ  ｍｏｄ  Ｎ＝１）を生成して、ｐ，ｑ，ｓを秘密鍵として安全に保管し、Ｎ，ｖを公開鍵として公開し、任意の圧縮関数ｈ（  ‖  ‖…‖  ）を公開し、認証の繰返し回数をｗと定め、認証を受ける際には、（１）証明者は、ｗ個の乱数ｒｉ（１≦ｉ≦ｗ）を生成し、前半情報  Ｘ＝ｈ（ｒ１２  ｍｏｄ  Ｎ‖ｒ２２  ｍｏｄ  Ｎ‖…‖ｒｗ２  ｍｏｄ  Ｎ）  を計算して通信機のうち検証を依頼する通信機（検証者）に送信し、（２）検証者は、値が“０”または“１”のｗ個の乱数ｅｉ（１≦ｉ≦ｗ）を生成して証明者に送信し、（３）証明者は、ｗ個の検証情報  Ｙ１＝ｒ１×ｓｅ１  ｍｏｄ  Ｎ，Ｙ２＝ｒ２×ｓｅ２  ｍｏｄ  Ｎ，…，Ｙｗ＝ｒｗ×ｓｅｗ  ｍｏｄ  Ｎ  を計算して検証者に送信し、（４）検証者は検証式  ｈ（Ｙ１２×ｖｅ１  ｍｏｄ  Ｎ‖Ｙ２２×ｖｅ２  ｍｏｄ  Ｎ‖…‖Ｙｗ２×ｖｅｗ  ｍｏｄ  Ｎ）＝Ｘ  が成り立つことを検算し、成り立つ場合には証明者を認証し、成り立たない場合には証明者を認証しない構成としたので、証明者から検証者へのデータ通信量と通信回数を削減することができるという効果が得られる。
【００４７】
また、（１）証明者は、検証者ｊ（１≦ｊ≦ｎ−１）に対して、ｎ≧ｗの場合は、ｎ−１個の乱数ｒｊを生成して前半情報  Ｘｊ＝ｒｊ２  ｍｏｄ  Ｎ（１≦ｊ≦ｎ−１）を計算して同報通信し、ｎ＜ｗの場合は、ｗ個の乱数ｒ１，…，ｒｗを生成してｗ個の前半情報  Ｘｊ＝ｒｊ２  ｍｏｄ  Ｎ，  Ｘｊ＋ｎ−１＝ｒｊ＋ｎ−１２  ｍｏｄ  Ｎ，  Ｘｊ＋２（ｎ−１）＝ｒｊ＋２（ｎ−１）２  ｍｏｄ  Ｎ，…  を計算して同報通信し、（２）検証者ｊ（１≦ｊ≦ｎ−１）は、ｎ≧ｗの場合は自身のＩＤに対応した前半情報Ｘｊを保持し、値が“０”または“１”の乱数ｅｊを同報通信し、ｎ＜ｗの場合は自身のＩＤに対応した前半情報Ｘｊ，Ｘｊ＋ｎ−１，Ｘｊ＋２（ｎ−１），…を保持し、値が“０”または“１”の乱数ｅｊ，ｅｊ＋ｎ−１，ｅｊ＋２（ｎ−１），…を同報通信し、（３）証明者は、ｎ≧ｗの場合はｅｊを用いてｎ−１個の検証情報  Ｙｊ＝ｒｊ×ｓｅｊ  ｍｏｄ  Ｎ  を計算して同報通信し、ｎ＜ｗの場合はｅｊ，ｅｊ＋ｎ−１，ｅｊ＋２（ｎ−１），…を用いてｗ個の検証情報  Ｙｊ＝ｒｊ×ｓｅｊ  ｍｏｄ  Ｎ，  Ｙｊ＋ｎ−１＝ｒｊ×ｓｅｊ＋ｎ−１  ｍｏｄ  Ｎ，  Ｙｊ＋２（ｎ−１）＝ｒｊ×ｓｅｊ＋２（ｎ−１）  ｍｏｄ  Ｎ，…  を計算して同報通信し、（４）検証者ｊは、ｎ≧ｗの場合は検証式  Ｙｊ２×ｖｅｊ  ｍｏｄ  Ｎ＝Ｘｊ  が成り立つことを確認し、ｎ＜ｗの場合は検証式  Ｙｊ２×ｖｅｊ  ｍｏｄ  Ｎ＝Ｘｊ，  Ｙｊ＋ｎ−１２×ｖｅｊ＋ｎ−１  ｍｏｄ  Ｎ＝Ｘｊ＋ｎ−１，Ｙｊ＋２（ｎ−１）２×ｖｅｊ＋２（ｎ−１）  ｍｏｄ  Ｎ＝Ｘｊ＋２（ｎ−１），…  が成り立つことを確認し、成り立たない場合は、不成立であることを同報通信し、成り立つ場合には、他の検証者から不成立であることが同報通信されないかぎりは、認証したとする構成としたので、証明者から検証者への通信量と検証者の演算量を削減できるという効果が得られる。
【００４８】
また、（１）証明者は、検証者ｊ（１≦ｊ≦ｎ−１）に対して、ｎ≧ｗの場合はｎ−１個の乱数ｒｊを生成してｎ−１個の前半情報  Ｘｊ＝ｈ（ｒｊ２  ｍｏｄ  Ｎ）  を計算して同報通信し、ｎ＜ｗの場合はｗ個の乱数ｒ１，…，ｒｗを生成してｎ−１個の前半情報  Ｘｊ＝ｈ（ｒｊ２  ｍｏｄ  Ｎ‖ｒｊ＋ｎ−１２  ｍｏｄ  Ｎ‖ｒｉ＋２（ｎ−１）２  ｍｏｄ  Ｎ‖…）を計算して同報通信し、（２）証検証者ｊ（１≦ｊ≦ｎ−１）は、ｎ≧ｗの場合は自身のＩＤに対応した前半情報Ｘｊを保持し、値が“０”または“１”の乱数ｅｊを同報通信し、ｎ＜ｗの場合は自身のＩＤに対応した前半情報Ｘｊを保持し、値が“０”または“１”の乱数ｅｊ，ｅｊ＋ｎ−１，ｅｊ＋２（ｎ−１），…を同報通信し、（３）証明者は、ｎ≧ｗの場合はｅｊを用いてｎ−１個の検証情報  Ｙｊ＝ｒｊ×ｓｅｊ  ｍｏｄ  Ｎ（１≦ｊ≦ｎ−１）  を計算して同報通信し、ｎ＜ｗの場合はｅｊ，ｅｊ＋ｎ−１，ｅｊ＋２（ｎ−１），…（１≦ｊ≦ｎ−１）を用いてｗ個の検証情報  Ｙｊ＝ｒｊ×ｓｅｊ  ｍｏｄ  Ｎ，  Ｙｊ＋ｎ−１＝ｒｊ×ｓｅｊ＋ｎ−１  ｍｏｄ  Ｎ，  Ｙｊ＋２（ｎ−１）＝ｒｊ×ｓｅｊ＋２（ｎ−１）  ｍｏｄ  Ｎ，…（１≦ｊ≦ｎ−１）  を計算して同報通信し、（４）検証者ｊは、ｎ≧ｗの場合は検証式  ｈ（Ｙｊ２×ｖｅｊ  ｍｏｄ  Ｎ）＝Ｘｊ  が成り立つことを確認し、ｎ＜ｗの場合は検証式  ｈ（Ｙｊ２×ｖｅｊ  ｍｏｄ  Ｎ‖Ｙｊ＋ｎ−１２×ｖｅｊ＋ｎ−１  ｍｏｄ  Ｎ‖Ｙｊ＋２（ｎ−１）２×ｖｅｊ＋２（ｎ−１）  ｍｏｄ  Ｎ）＝Ｘｊ  が成り立つことを確認し、成り立たない場合は、不成立であることを同報通信し、成り立つ場合には、他の検証者から不成立であることが同報通信されないかぎりは、認証したとする構成としたので、証明者から検証者への通信量と検証者の演算量を削減できるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態における認証方法の手順を示す流れ図、
【図２】本発明の第２の実施の形態における認証方法のステップ（１）を示す図、
【図３】本発明の第２の実施の形態における認証方法のステップ（２）を示す図、
【図４】本発明の第２の実施の形態における認証方法のステップ（３）を示す図、
【図５】本発明の第２の実施の形態における認証方法のステップ（４）を示す図、
【図６】従来の１対１の通信システムにおける認証方法の説明図、
【図７】従来の並列Ｆｉａｔ−Ｓｈａｍｉｒ法のステップ（１）の説明図、
【図８】従来の並列Ｆｉａｔ−Ｓｈａｍｉｒ法のステップ（２）の説明図、
【図９】従来の並列Ｆｉａｔ−Ｓｈａｍｉｒ法のステップ（３）の説明図、
【図１０】従来の並列Ｆｉａｔ−Ｓｈａｍｉｒ法のステップ（４）の説明図である。
【符号の説明】
１  証明者
２  検証者
３  同報通信網
【図１】
0003585397.tif 000002
【図２】
0003585397.tif 000003
【図３】
0003585397.tif 000004
【図４】
0003585397.tif 000005
【図５】
0003585397.tif 000006
【図６】
0003585397.tif 000007
【図７】
0003585397.tif 000008
【図８】
0003585397.tif 000009
【図９】
0003585397.tif 000010
【図１０】
0003585397.tif 000011