(57)【特許請求の範囲】
【請求項１】
証明情報生成装置の各々に固有の秘密情報を保持する秘密情報保持手段と、外部から認証情報および認証補助情報を入力する入力手段と、上記秘密情報保持手段に保持された秘密情報を指数とし、上記入力手段から入力された上記認証補助情報を法数として、上記入力手段から入力された上記認証情報に対して、べき乗剰余演算を実行する演算手段と、上記演算手段によって演算された演算結果を証明情報として出力する出力手段とを具備する証明情報生成装置とともに用いられ、上記秘密情報を回復する秘密情報回復装置において、
上記認証情報を記憶する認証情報記憶手段と、
互いに素である数列を記憶する数列記憶手段と、
上記数列記憶手段から順次に読み出した数と、上記認証情報記憶手段から読み出した上記認証情報とから回復用の認証補助情報を生成する認証補助情報生成手段と、
上記認証補助情報生成手段により生成した上記回復用の認証補助情報を上記入力手段へ入力する認証補助情報入力手段と、
上記回復用の認証補助情報および上記認証情報に基づいて上記出力手段から出力される回復用の証明情報を記憶する証明情報記憶手段と、
上記認証情報記憶手段に記憶された上記認証情報と上記数列記憶手段に記憶された上記数列と上記証明情報記憶手段に記憶された上記回復用の証明情報とに対して下記の所定の演算を行い、秘密情報を再構成する秘密情報回復手段とを有し、
上記所定の演算は、
（ａ）上記数列記憶手段から数列中の数値ｐｉを取り出し、
（ｂ）取りだした数列の数値を用いて所定の大きな数値Ｍに対し、Ｍ÷ｐｉを計算し計算結果を第一補助数Ｍ’とし、
（ｃ）Ｍ−１  ｍｏｄ  ｐｉを計算し計算結果を第二補助数ｙとし、
（ｄ）上記証明情報記憶手段から証明情報Ｒｉを読み出し、上記認証情報から認証情報Ｃを読み出し、秘密情報候補値Ｓ（初期値は０）をＳ＝Ｓ＋（ｌｏｇｃＲｉ）・Ｍ’・ｙ  ｍｏｄ  Ｍ  で計算し、
上記証明情報記憶手段中のすべての証明情報Ｒｉについて上記（ａ）〜（ｄ）の処理を繰り返したのち、当該秘密情報候補値Ｓを秘密情報として出力するものであることを特徴とする秘密情報回復装置。
【請求項２】
証明情報生成装置の各々に固有の秘密情報を保持する秘密情報保持手段と、外部から認証情報および認証補助情報を入力する入力手段と、上記秘密情報保持手段に保持された秘密情報を指数とし、上記入力手段から入力された上記認証補助情報を法数として、上記入力手段から入力された上記認証情報に対して、べき乗剰余演算を実行する演算手段と、上記演算手段によって演算された演算結果を証明情報として出力する出力手段とを具備する証明情報生成装置とともに用いられ、上記秘密情報を回復する秘密情報回復方法において、
認証情報記憶手段が、上記認証情報を記憶する認証情報記憶ステップと、
数列記憶手段が、互いに素である数列を記憶する数列記憶ステップと、
認証補助情報生成手段が、上記数列記憶手段から順次に読み出した数と、上記認証情報記憶手段から読み出した上記認証情報とから回復用の認証補助情報を生成する認証補助情報生成ステップと、
認証補助情報入力手段が、上記認証補助情報生成手段により生成した上記回復用の認証補助情報を上記入力手段へ入力する認証補助情報入力ステップと、
証明情報記憶手段が、上記回復用の認証補助情報および上記認証情報に基づいて上記出力手段から出力される回復用の証明情報を記憶する証明情報記憶ステップと、
秘密情報回復手段が、上記認証情報記憶手段に記憶された上記認証情報と上記数列記憶手段に記憶された上記数列と上記証明情報記憶手段に記憶された上記回復用の証明情報とに対して下記の所定の演算を行い、秘密情報を再構成する秘密情報回復ステップとを有し、
上記所定の演算は、
（ａ）上記数列記憶手段から数列中の数値ｐｉを取り出し、
（ｂ）取りだした数列の数値を用いて所定の大きな数値Ｍに対し、Ｍ÷ｐｉを計算し計算結果を第一補助数Ｍ’とし、
（ｃ）Ｍ−１  ｍｏｄ  ｐｉを計算し計算結果を第二補助数ｙとし、
（ｄ）上記証明情報記憶手段から証明情報Ｒｉを読み出し、上記認証情報から認証情報Ｃを読み出し、秘密情報候補値Ｓ（初期値は０）をＳ＝Ｓ＋（ｌｏｇｃＲｉ）・Ｍ’・ｙ  ｍｏｄ  Ｍ  で計算し、
上記証明情報記憶手段中のすべての証明情報Ｒｉについて上記（ａ）〜（ｄ）の処理を繰り返したのち、当該秘密情報候補値Ｓを秘密情報として出力するものであることを特徴とする秘密情報回復方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、外部から与えられた情報に対し、装置内部に保持された秘密情報を用いた演算を行い、その演算結果によって、特定の秘密情報を保持していることを証明する証明情報生成装置に関する。
【０００２】
【従来技術】
コンピュータや電子機器の発達により、多くのサービスや情報が電子的に提供されるようになってきた。電子的な情報やサービスを提供するコンピュータプログラムは複製が容易であるため、不正利用や不正複製が問題になってきている。
そのため、サービスや情報の正当な利用者であることを証明するための手段が必要とされてきている。正当なユーザであることを証明するためには、検証者から与えられた情報に対するユーザの秘密鍵による電子署名や暗号が用いられる。電子署名を行うためのものとして、特開平７−２８７５１４号公報のようなものがある。これは、装置内部に秘密指数および公開法数を封入し、それらを用いてＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａｄｅｌｍａｎ）タイプの暗復号、および、電子署名を行うものである。
【０００３】
【発明が解決しようとする課題】
しかしながら、従来の署名や暗号を持ちいた装置では、秘密指数および公開法数は共に装置内に装置作成時に封入されており、ユーザの手元に届けられた後、これらを変更することはできない。このため、検証者に応じて証明情報を変えるなど、多様な証明情報を生成することができないという問題があった。
【０００４】
本発明は、証明情報生成装置をユーザが手元に届けられた後にも、検証者に応じて証明情報を変えることができる柔軟な証明情報生成装置を提供することを目的とする。
【０００５】
【課題を解決するための手段】
本発明によれば、上述の目的を達成するために、証明情報生成装置に、証明情報生成装置の各々に固有の秘密情報を保持する秘密情報保持手段と、外部から認証情報および認証補助情報を入力する入力手段と、上記秘密情報保持手段に保持された上記秘密情報と上記入力手段から入力された上記認証情報および上記認証補助情報情報とに対し所定の演算を実行する演算手段と、演算手段によって演算された演算結果を証明情報として出力する出力手段とを設けるようにしている。
【０００６】
この構成においては、証明情報の生成に必要な認証情報、秘密情報および認証用補助情報のうち秘密情報を証明情報生成装置に保持させ、認証用補助情報は認証情報とともに証明時に入力されるようにしている。したがって、単一の秘密情報すなわち単一の証明情報生成装置を用いても、認証補助情報を変更することにより検証者に応じた多様な証明情報を生成することができる。
【０００７】
また、この構成において、さらに上記認証補助情報に付加された電子署名を検証するための署名検証情報を保持する署名検証情報保持手段と、入力された上記認証補助情報と、上記認証補助情報に付加された上記電子署名と、上記署名検証情報保持手段に保持された上記署名検証情報とから署名の真偽を判定する署名検証手段とを設け、上記演算手段は上記認証補助情報に付加された上記電子署名が真の場合のみ演算を行うようにしてもよい。これにより、認証補助情報を操作することによる不正が防止できる。
【０００８】
また、この構成において、さらに、正しい認証補助情報を記憶する認証補助情報保持手段と、上記入力手段から入力された上記認証補助情報が上記認証補助情報保持手段に登録されているかどうかを判定する認証補助情報判定手段とを設け、上記演算手段は上記認証補助情報判定手段が上記認証補助情報の登録を判定した場合のみ演算を行うようにしてもよい。この場合も、認証補助情報を操作することによる不正が防止できる。
【０００９】
また、上記演算手段において行われる演算に、上記入力手段より入力された上記認証補助情報を入力とする一方向性関数の演算結果を用いるようにしてもよい。この場合も、認証補助情報を操作することによる不正が防止できる。
【００１０】
また、上記演算手段において行われる演算に、上記入力手段より入力された上記認証補助情報と上記秘密情報保持手段に記憶された上記秘密情報とを入力とする一方向性関数の演算結果を用いるようにしてもよい。この場合も、認証補助情報を操作することによる不正が防止できる。
【００１１】
また、演算の履歴を記録する履歴記憶手段を設けるようにしてもよい。この場合、上記履歴記憶手段に記憶される履歴には少なくとも上記入力手段から入力された上記認証補助情報が含まれるようにしてもよい。また、上記履歴記憶手段に記憶される履歴には少なくとも上記入力手段から入力された上記認証補助情報の識別子が含まれるようにしてもよい。このようにすることにより、監査、認証回数による利用量課金等を行うことができる。
【００１２】
また、上記演算手段は公開鍵暗号を用いた演算とし、上記認証補助情報を上記公開鍵暗号の法数とすることができる。
【００１３】
また、本発明によれば、証明情報生成装置の各々に固有の秘密情報を保持する秘密情報保持手段と、外部から認証情報および認証補助情報を入力する入力手段と、上記秘密情報保持手段に保持された秘密情報を指数とし、上記入力手段から入力された上記認証補助情報を法数として、上記入力手段から入力された上記認証情報に対して、べき乗剰余演算を実行する演算手段と、上記演算手段によって演算された演算結果を証明情報として出力する出力手段とを具備する証明情報生成装置とともに用いられ、上記秘密情報を回復する秘密情報回復装置に、上記認証情報を記憶する認証情報記憶手段と、互いに素である数列を記憶する数列記憶手段と、上記数列記憶手段から順次に読み出した数と、上記認証情報記憶手段から読み出した上記認証情報とから回復用の認証補助情報を生成する認証補助情報生成手段と、上記認証補助情報生成手段により生成した上記回復用の認証補助情報を上記入力手段へ入力する認証補助情報入力手段と、上記回復用の認証補助情報および上記認証情報に基づいて上記出力手段から出力される回復用の証明情報を記憶する証明情報記憶手段と、上記認証情報記憶手段に記憶された上記認証情報と上記数列記憶手段に記憶された上記数列と上記証明情報記憶手段に記憶された上記回復用の証明情報とに対して所定の演算を行い、秘密情報を再構成する秘密情報回復手段とを設けるようにしている。
【００１４】
この構成においては、証明情報生成装置を変更すること無く、秘密情報を回復することができる。
【００１５】
【発明の実施の態様】
以下、本発明の実施例を用いて本発明を詳細に説明する。
【００１６】
［実施例１］
図１は、本発明による証明情報生成装置の実施例１の構成を示したものである。図１において、この実施例の証明情報生成装置は、秘密情報保持手段１、入力手段２、演算手段３および出力手段４を含んで構成されている。秘密情報保持手段１は、証明情報生成装置本体に固有の秘密情報を保持するものである。入力手段２は、外部から情報を取得するものである。演算手段３は、秘密情報保持手段１に保持された秘密情報と入力手段２から入力された情報とに基づいて所定の演算を実行するものである。出力手段４は、演算手段３によって演算された演算結果を証明情報として出力するものである。
【００１７】
なお、秘密情報保持手段１および演算手段３は安全性を向上させるため、ＩＣカード等の耐タンパー性を備える容器に封入され、この結果、読み出し、書き換え等が不正に行えないよう保護されている。
【００１８】
ここで、入力手段２および出力手段４は、どのようなものでもよく、例えば、入力手段２としてキーボード、シリアル通信、パラレル通信、赤外線など無線通信、イーサネット等のＬＡＮ（ローカルエリアネットワーク）、磁気ディスクやメモリカードといった記憶メディアなどが考えられ、出力手段４として、ＣＲＴ（陰極線管）ディスプレイ、シリアル通信、パラレル通信、赤外線など無線通信、イーサネット等のＬＡＮ、磁気ディスクやメモリカードといった記憶メディアなどが考えられる。
【００１９】
図２は、本実施例の証明情報生成装置に入力される情報の構成を示したものである。入力手段２から入力される情報は、認証情報Ｃと認証補助情報ｎとから構成されている。入力手段２から認証情報Ｃと認証補助情報ｎを入力する方法、データ構造は、演算手段３に渡す前に認証情報Ｃと認証補助情報ｎを区別できるようになっていれば、どのようなものであっても良い。例えば、認証情報Ｃと認証補助情報ｎを別々のデータとして入力してもよい。また、認証情報Ｃと認証補助情報ｎの少なくとも一方を固定長としてもよい。また、認証情報Ｃと認証補助情報ｎを区切り記号で区切った１つのデータとして入力してもよい（図２（ａ））。また、先頭に認証情報Ｃの長さを格納し、認証情報Ｃと認証補助情報ｎを１つのデータとして入力してもよい（図２（ｂ））。また、一定の長さ毎に交互に混ざったデータとして入力してもよい（図２（ｃ））。
【００２０】
本実施例における処理の流れを図３に示す。図３において、まず、入力手段２から入力された認証情報Ｃと認証補助情報ｎとは、演算手段３へ渡される（ステップ３−１、ステップ３−２）。演算手段３は、秘密情報保持手段１から秘密情報ｄを読み出し（ステップ３−３）、認証情報Ｃと認証補助情報ｎと秘密情報ｄを使い所定の演算を行う（ステップ３−４）。そして、演算手段３により計算された証明情報Ｒは、出力手段４より出力される（ステップ３−５）。
【００２１】
演算手段３で行う演算は認証情報Ｃ、認証補助情報ｎおよび秘密情報ｄを用いて、それぞれの情報に応じて値が変化し、偽造不可能で、検証者が証明情報Ｒが正しいことが検証できるものであればどのようなものでもよい。
【００２２】
例えば、演算手段３で行う演算として、ＲＳＡ署名を使うのであれば、法数を認証補助情報ｎとして入力し、秘密情報ｄを指数として、認証情報Ｃに対し、Ｃd  ｍｏｄ  ｎという、べき乗剰余演算を行えば良い。なお、この時、認証補助情報ｎと証明情報Ｒを検証するための検証情報ｅは、次の関係を満たすように生成される。
【００２３】
【数１】
ｎ＝ｐｑ
１≦ｄ≦（ｐ−１）（ｑ−１）
１≦ｅ≦（ｐ−１）（ｑ−１）
ｄｅ≡１  ｍｏｄ  （ｐ−１）（ｑ−１）
ただし、ｐ、ｑは異なる素数である。
【００２４】
検証者（検証計算を実行する検証装置）は、Ｒｅ  ｍｏｄ  ｎと認証情報Ｃとが等しいかどうかを確認すればよい。
【００２５】
あるいは、演算手段３で行う演算として、ＥｌＧａｍａｌ暗号を用いる場合、法数を認証補助情報ｎとして入力し、認証情報としてつぎのＣ、Ｃ‘を入力し、
【００２６】
【数２】
0003700333.tif 000002
0003700333.tif 000003
演算手段３では、Ｃ’／Ｃd  ｍｏｄ  ｎなる演算を行い、証明情報Ｒとして出力する。ここで、認証補助情報ｎは素数、αは乱数、ｇは乗法群の原始根、ｍは適当な数、ｙはｙ＝ｇd  ｍｏｄ  ｎである公開鍵である。検証は、証明情報Ｒと、Ｃ’の生成に使ったｍとが等しいかどうかを確認すれば良い。
【００２７】
また、法数を認証補助情報ｎとして入力し、認証情報としてつぎのＣを入力し、
【００２８】
【数３】
0003700333.tif 000004
Ｃd  ｍｏｄ  ｎという、べき乗剰余演算を行い、証明情報Ｒとして出力してもよい。この場合、検証は
【００２９】
【数４】
0003700333.tif 000005
が１になるかどうかを確認すれば良い。
【００３０】
［実施例２］
図４は、本発明の実施例２を全体として示している。この実施例２は、認証補助情報に電子署名を付与して正規の認証補助情報のみ受け付けるようにしたものである。図４において、この実施例の証明情報生成装置は、秘密情報保持手段１、入力手段２、演算手段３、出力手段４、署名検証情報保持手段５および署名検証手段６を含んで構成されている。秘密情報保持手段１、入力手段２、演算手段３および出力手段４は先の実施例１と同様である。署名検証情報保持手段５は、認証補助情報ｎに付加された電子署名を検証するための署名検証情報を保持するものである。署名検証手段６は、入力された認証補助情報ｎと、認証補助情報ｎに付加された電子署名と、署名検証情報保持手段５に保持された署名検証情報とから認証補助情報ｎに付加された電子署名の真偽を判定するものである。
【００３１】
なお、秘密情報保持手段１と演算手段３署名検証情報保持手段５と署名検証手段６は安全性を向上させるため、ＩＣカード等の耐タンパー性を備える容器に封入され、この結果、読み出し、書き換え等が不正に行えないよう保護されている。
【００３２】
図５は、本実施例において入力手段２から入力される入力データの構造を示している。入力手段２から入力された入力データは、認証情報Ｃと認証補助情報ｎと認証補助情報ｎに付加された電子署名ｓとから構成されている。これらの入力データの入力方法や入力データ構造は、演算手段３に渡す前に認証情報Ｃと認証補助情報ｎとを区別でき、さらに署名検証手段６へ渡す前に認証補助情報ｎと電子署名ｓとを区別できれば、どのようなるものであっても良い。例えば、認証情報Ｃと認証補助情報ｎと電子署名ｓとを別々のデータとして入力してもよい。また、認証情報Ｃと認証補助情報ｎと電子署名ｓとを区切り記号で区切った１つのデータとして入力してもよい（図５（ａ））。また、先頭に認証情報Ｃの長さを、認証情報Ｃの次に電子署名ｓの長さをそれぞれ格納し、認証情報Ｃと認証補助情報ｎと電子署名ｓとを１つのデータとして入力してもよい（図５（ｂ））。
【００３３】
認証補助情報ｎに付加する電子署名の方法は既存の各種電子署名でよく、例えば、ＲＳＡ署名を用いた場合、署名検証情報保持手段５に記憶される署名検証情報は、法数ｎ’と検証鍵ｅ’であり、認証補助情報生成者の署名鍵ｄ’および法数ｎ’とから作られた電子署名ｓが認証補助情報ｎに付加されている。
【００３４】
この時の処理の流れを図６に示す。図６において、まず、入力手段２から入力された認証補助情報ｎと認証補助情報ｎに付加された電子署名ｓとを署名検証手段６に渡す（ステップ６−１、ステップ６−２）。署名検証手段６は、署名検証情報保持手段５から署名検証情報ｎ’とｅ’とを読み出し（ステップ６−３）、ｓe'  ｍｏｄ  ｎ’を計算する（ステップ６−４）。そして前ステップでの計算結果と認証補助情報ｎとを比較し（ステップ６−５）、一致しなければエラーを出力手段４に出力し（ステップ６−６）、終了する。
【００３５】
ステップ６−５において両者が一致していれば、入力手段２から認証情報Ｃを取得し（ステップ６−７）、ステップ６−１で取得した認証補助情報ｎとともに演算手段３へ渡す。演算手段３は、秘密情報保持手段１から秘密情報ｄを読み出し（ステップ６−８）、認証情報Ｃと認証補助情報ｎと秘密情報ｄとを使い所定の演算を行う（ステップ６−９）。そして演算手段３により計算された証明情報Ｒを出力手段４より出力する（ステップ６−１０）。
【００３６】
本実施例では、認証補助情報ｎとステップ６−５で計算したｓe'  ｍｏｄ  ｎ’の計算結果を比較していたが、署名が認証補助情報ｎをハッシュ関数に適応した計算結果の場合、認証補助情報ｎをハッシュ関数にかけ、その結果とｓe'  ｍｏｄ  ｎ’の計算結果を比較するようにしても良い。
【００３７】
また、本実施例での署名はＲＳＡ署名としたが、ＥｌＧａｍａｌ署名など他の署名アルゴリズムを用いてもよい。
【００３８】
［実施例３］
図７は、本発明の実施例３を全体として示している。この実施例３においては、予め複数の認証補助情報を証明情報生成装置に登録しておき、登録されている認証補助情報のみ受け付けるようにしたものである。図７において、この実施例の証明情報生成装置は、秘密情報保持手段１、入力手段２、演算手段３、出力手段４、認証補助情報保持手段７および認証補助情報判定手段８を含んで構成されている。秘密情報保持手段１、入力手段２、演算手段３および出力手段４は先の実施例１と同様である。認証補助情報保持手段７は、正しい認証補助情報を記憶するものである。認証補助情報判定手段８は、入力手段２から入力された認証補助情報ｎが認証補助情報保持手段７に登録されているかどうかを判定するものである。
【００３９】
なお、秘密情報保持手段１と演算手段３認証補助情報保持手段７と認証補助情報判定手段８とは安全性を向上させるため、ＩＣカード等の耐タンパー性を備える容器に封入され、この結果、読み出し、書き換え等が不正に行えないように保護されている。
【００４０】
本実施例における処理の流れは図８に示したようになる。図８において、まず、入力手段２から入力された認証補助情報ｎを認証補助情報判定手段８へ送る（ステップ８−１）。認証補助情報判定手段８は、認証補助情報保持手段７から正しい認証補助情報ｎ’を読み出し（ステップ８−２）、入力された認証補助情報ｎと認証補助情報保持手段７から読み出した正しい認証補助情報ｎ’と比較する（ステップ８−３）。一致しなければ、認証補助情報保持手段７に比較していない認証補助情報が残っているか確認し（ステップ８−４）、残っていればステップ８−２に戻り、認証補助情報保持手段７から次の認証補助情報を読み出す。認証補助情報保持手段７内に比較する認証補助情報が残っていなければ、認証補助情報保持手段７内に入力された認証補助情報ｎと同じものが無いのでエラーを出力手段４に出力し（ステップ８−５）、終了する。
【００４１】
ステップ８−３において、入力された認証補助情報ｎと認証補助情報保持手段７から読み出した正しい認証補助情報ｎ’とが一致していると判断された場合には、入力手段２から認証情報Ｃを取得し（ステップ８−６）、ステップ８−１で取得した認証補助情報ｎとともに演算手段３へ渡す。演算手段３は、秘密情報保持手段１から秘密情報ｄを読み出し（ステップ８−７）、認証情報Ｃと認証補助情報ｎと秘密情報ｄとを使い所定の演算を行う（ステップ８−８）。そして演算手段３により計算された証明情報Ｒを出力手段４より出力する（ステップ８−９）。
【００４２】
認証補助情報保持手段７に保持される正しい認証補助情報は、証明情報生成装置をユーザに発行する際に、秘密情報とともに、登録しておいても良いし、証明情報生成装置をユーザに発行した後に、安全に登録できるようにしてもよい。例えば、正しい認証補助情報に信用できる発行者の電子署名を付加しておき、その検証を行い、正しいことを確認した後、認証補助情報保持手段７に保持するようにすればよい。
【００４３】
ここで、上記実施例では、認証補助情報保持手段７に正しい認証補助情報そのものを登録していたが、認証補助情報保持手段７には、正しい認証補助情報のハッシュ値のみを登録しておき、入力された認証補助情報ｎのハッシュ値と比較するようにしてもよい。あるいは、認証補助情報に識別子を付与し、認証補助情報保持手段７には、正しい認証補助情報の識別子を登録しておき、入力された認証補助情報ｎの識別子と比較しても良い。
【００４４】
［実施例４］
つぎに本発明の実施例４について説明する。本実施例は、実施例１（図１）の構成において、演算手段３で行われる演算が、認証補助情報ｎと秘密情報保持手段１に保持された秘密情報ｄを入力とする一方向性関数の演算結果を指数とした、べき乗剰余演算を含んでだものである。
【００４５】
図９は、一方向性関数としてｘn|d  ｍｏｄ  ｙを用いた場合の本実施例での処理の流れを示したものである。ここで、ｘ，ｙは検証者と共有している適当な定数とする。
【００４６】
図９において、入力手段２から入力された認証情報Ｃと認証補助情報ｎは、演算手段３へ渡される（ステップ９−１、ステップ９−２）。演算手段３は、秘密情報保持手段１から秘密情報ｄを読み出す（ステップ９−３）。
演算手段３は、定数ｘ，ｙを用いて、ｘn|d  ｍｏｄ  ｙを計算し、ｚとする（ステップ９−４）。ここで、ｎ｜ｄは認証補助情報ｎと秘密情報ｄのビット連結を表す。演算手段３は、秘密情報ｄとステップ９−４で計算したｚとを用いて、Ｃz  ｍｏｄ  ｎを計算する（ステップ９−５）。そして出力手段４へ演算結果を証明情報Ｒとして出力する（ステップ９−６）。
【００４７】
検証者は、ＲＳＡ署名を用いるのであれば、（ｎ｜ｄ）・ｅ≡１  ｍｏｄ  φ（ｎ）（ただし、φ（ｎ）＝（ｐ−１）（ｑ−１）、ｎ＝ｐｑ、ｐとｑは異なる素数）を満たすｅを使って、Ｒe  ｍｏｄ  ｎがＣと等しいかを検証することで証明情報の正しさを検証できる。
【００４８】
なお、ここではステップ９−４で用いる一方向性関数をｘn|d  ｍｏｄ  ｙとしたが、ＳＨＡやＭＤ５等公開されているハッシュアルゴリズムを用いてもよい。
【００４９】
また、一方向性関数としてｘn|d  ｍｏｄ  ｙを用いる場合でも、ステップ９−４および検証鍵ｅの生成に必要なビット連結の順序は逆でも良いし、指数部に他の演算を用いても良い。
【００５０】
また、ステップ９−４で用いる一方向性関数を、正当な検証鍵発行者と本発明による証明情報生成装置のみがアクセス可能な秘密の一方向性関数であるなら、認証補助情報ｎのみを一方向性関数の入力としてもよい。例えば、ステップ９−４での演算をｘn  ｍｏｄ  ｙ、ステップ９−５での演算をＣd+z  ｍｏｄ  ｎとして図９と同様に処理を行う。
【００５１】
この場合、検証者は、ＲＳＡ署名を用いるのであれば、Ｒ’＝Ｃ-z  ｍｏｄ  ｎ、Ｒ’’＝Ｒ・Ｒ’  ｍｏｄ  ｎ、Ｒ’’’＝Ｒ’’e  ｍｏｄ  ｎを計算し、Ｒ’’’とＣとが等しいことを確かめればよい。ここで、ｅはｅｄ  ｍｏｄ  φ（ｎ）＝１（ただし、φ（ｎ）＝（ｐ−１）（ｑ−１）、ｎ＝ｐｑ、ｐとｑは異なる素数）となる検証鍵である。
【００５２】
［実施例５］
図１０は、本発明の実施例５を全体として示している。この実施例においては、秘密情報を回復することができるようになっている。図１０において、この実施例の証明情報生成装置は、秘密情報保持手段１、入力手段２、演算手段３、出力手段４、認証情報記憶手段９、数列記憶手段１０、認証補助情報記憶手段１１、証明情報記憶手段１２、秘密情報回復手段１３および秘密情報出力手段１４を含んで構成されている。秘密情報保持手段１、入力手段２、演算手段３および出力手段４は先の実施例１と同様である。すなわち、秘密情報保持手段１は、各証明情報生成装置固有の秘密情報ｄを保持している。入力手段２は、外部から認証情報Ｃと認証補助情報ｎiとを与える。演算手段３は、秘密情報保持手段１に保持された秘密情報ｄと入力手段２から入力された認証情報Ｃと認証補助情報ｎiとから所定のべき乗剰余演算を施す。出力手段４は、演算手段３によって演算された証明情報Ｒiを出力する。
【００５３】
また、認証情報記憶手段９は、認証情報Ｃを記憶するものである。数列記憶手段１０は、互いに素である数列を記憶するものである。認証補助情報生成手段１１は、数列記憶手段１０から数値ｐiを順次読み出し、この数値ｐiと認証情報記憶手段９から読み出した認証情報Ｃとから認証補助情報ｎiを生成し、入力手段２に入力するものである。証明情報記憶手段１２は、出力手段４から出力された証明情報Ｒiを記憶するものである。秘密情報回復手段１３は、認証情報記憶手段９に記憶された認証情報Ｃと、数列記憶手段１０に記憶された数列と、証明情報記憶手段１２に記憶された証明情報Ｒiとを使い、所定の演算を行うものである。秘密情報出力手段１４は、秘密情報回復手段１３によって計算された秘密情報を出力するものである。
【００５４】
ここで、ｐiは数列記憶手段１０に記憶されているｉ番目の数値、ｎi、Ｒiはそれぞれｐiに対応するｉ番目の認証補助情報、証明情報である。
【００５５】
以下では、演算手段３で行うべき乗剰余演算がＣd  ｍｏｄ  ｎiである場合について述べる。
【００５６】
この構成における処理の流れは図１１および図１２のようになる。図１１および図１２において、まず、変数Ｍ、ｉを１で初期化する（ステップ１１−１）。認証補助情報生成手段１１は、認証情報記憶手段９から認証情報Ｃと、数列記憶手段１０から数値ｐｉとを読み出す（ステップ１１−２、ステップ１１−３）。認証補助情報生成手段１１は、所定の演算（ｎｉ←Ｃｐｉ−１）を行い、認証補助情報ｎｉを生成する（ステップ１１−４）。認証補助情報生成手段１１は、ステップ１１−４で生成した認証補助情報ｎｉと、認証情報記憶手段９から読み出した認証情報Ｃを、入力手段２に送り、これが演算手段３に渡される（ステップ１１−５）。演算手段３は、秘密情報保持手段１から秘密情報ｄを読み出し（ステップ１１−６）、認証情報Ｃと認証補助情報ｎｉ及び秘密情報ｄを使い、所定の演算（Ｒｉ←Ｃｄ  ｍｏｄ  ｎｉ）を行う（ステップ１１−７）。演算手段３により計算された証明情報Ｒｉは出力手段４から出力され、証明情報記憶手段１２に記憶される（ステップ１１−８、ステップ１１−９）。
【００５７】
つぎに変数Ｍにｐiを乗じ、その結果を変数Ｍに格納する（ステップ１１−１０）。Ｍの値がｄの桁よりも十分に大きいかどうか確認し（ステップ１１−１１）、小さければ変数ｉに１を加え（ステップ１１−１２）、ステップ１１−２に戻り繰り返す。Ｍの値が大きければ、変数ｉを１で、変数Ｓを０で初期化する（ステップ１１−１３）。
【００５８】
こののち数列記憶手段１０からｉ番目の数値ｐiを読み出す（ステップ１１−１４）。変数Ｍの値をｐiで割り、変数Ｍ’に格納する（ステップ１１−１５）。Ｍ-1  ｍｏｄ  ｐiを計算し、変数ｙに格納する（ステップ１１−１６）。
【００５９】
つぎに、証明情報記憶手段１２からｉ番目の証明情報Ｒiを読み出す（ステップ１１−１７）。認証情報記憶手段９から認証情報Ｃを読み出す（ステップ１１−１８）。Ｓ＋（ｌｏｇCＲi）Ｍ’ｙ  ｍｏｄ  Ｍを計算し、変数Ｓに格納する（ステップ１１−１９）。証明情報記憶手段１２に処理すべきＲiが残っていないか確認し（ステップ１１−２０）、残っていれば、変数ｉに１を加え（ステップ１１−２１）、ステップ１１−１４へ戻る。残っていなければ、変数Ｓの値を秘密情報として秘密情報出力手段１４より出力する（ステップ１１−２２）。
【００６０】
［実施例６］
図１３は本発明の実施例６を全体として示している。実施例６は履歴を記録して、監査や課金の利用できるようにしたものである。図１３において、この実施例の証明情報生成装置は、秘密情報保持手段１、入力手段２、演算手段３、出力手段４および履歴記憶手段１５を含んで構成されている。秘密情報保持手段１、入力手段２、演算手段３および出力手段４は先の実施例１と同様である。履歴記憶手段１５は、証明情報生成の履歴を記憶するものである。
【００６１】
なお、秘密情報保持手段１と演算手段３は安全性を向上させるため、ＩＣカード等の耐タンパー性を備える容器に封入され、この結果、読み出し、書き換え等が不正に行えないよう保護されるようになっている。監査などのために、履歴情報を改竄できないようにする必要がある場合には、履歴記憶手段１５も、秘密情報保持手段１と演算手段３と共に耐タンパー性を備える容器に封入する。
【００６２】
履歴記憶手段１５に保持される履歴としては、入力手段２から入力された認証情報、認証補助情報、生成した証明情報、生成した時刻、エラーの有無、認証情報の識別子、認証補助情報の識別子、認証補助情報に付けられた署名、など、また、これらの組み合わせが考えられる。
【００６３】
図１４は、履歴として入力手段２から入力された認証補助情報を保持する場合の処理の流れを示している。この図において、まず、入力手段２から入力された認証情報Ｃと認証補助情報ｎは、演算手段３へ渡される（ステップ１３−１、ステップ１３−２）。演算手段３は、秘密情報保持手段１から秘密情報ｄを読み出し（ステップ１３−３）、認証情報Ｃと認証補助情報ｎと秘密情報ｄとを使い所定の演算を行う（ステップ１３−４）。演算手段３は、演算に持ちいた認証補助情報ｎを履歴記憶手段１５へ送り、記憶させる（ステップ１３−５）。また演算手段３により計算された証明情報Ｒを出力手段４より出力する（ステップ１３−６）。
【００６４】
ここでは、ステップ１３−５で演算手段３から履歴記憶手段１５へ認証補助情報ｎが送られたが、他のステップで行ってもよい。例えば、入力手段２から入力された直後（ステップ１３−２の後）に履歴記憶手段１５へ送り、記憶してもよいし、証明情報Ｒの生成が終了した後（ステップ１３−６の後）でもよい。また、演算手段３より送られるのではなく、入力手段２から（証明情報を履歴に残すなら出力手段４から）直接送られてもよい。
【００６５】
［実施例７］
図１５は、本発明の実施例７を示している。この実施例は、履歴として認証補助情報に付加された識別子を保存するものである。図１５において、実施例７の証明情報生成装置は、秘密情報保持手段１、入力手段２、演算手段３、出力手段および履歴記憶手段１５を含んで構成されている。構成要素自体は実施例６と同様である。この実施例においては、入力手段２から入力した認証補助情報ｎに付加されている識別子を履歴記憶手段１５に送り、記憶するようになっている。
【００６６】
なお、この実施例においても、秘密情報保持手段１と演算手段３は安全性を向上させるため、ＩＣカード等の耐タンパー性を備える容器に封入され、この結果、読み出し、書き換え等が不正に行えないよう保護さらるようになっている。また、監査などのために履歴情報を改竄できないようにする必要がある場合には、履歴保持手段１５も、秘密情報保持手段１と演算手段３と共に耐タンパー性を備える容器に封入するようになっている。
【００６７】
図１６は、本実施例における認証補助情報のデータの構成例を示している。認証補助情報のデータ構成としては、固定長の識別子が付いているもの（図１６（ａ））、認証補助情報の先頭に識別子のサイズを示すフィールド（固定長）が付いているもの（図１６（ｂ））、識別子と認証補助情報の間に分離記号が入っているもの（図１６（ｃ））などがある。これらのデータ構造に限らず、識別子と認証補助情報が分離できる形式であればどのようなものでもよい。
【００６８】
図１７は、本実施例における処理の流れを示したものである。図１７において、入力手段２から入力された認証情報Ｃ、認証補助情報ｎは演算手段３へ送られる（ステップ１６−１、ステップ１６−２）。認証補助情報ｎに付加されていた識別子は入力手段２で分離され、履歴記憶手段１５へ送られる（ステップ１６−３）。
【００６９】
演算手段３は、秘密情報保持手段１から秘密情報ｄを読み出し（ステップ１６−４）、認証情報Ｃと認証補助情報ｎと秘密情報ｄとを使い所定の演算を行う（ステップ１６−５）。そして演算手段３により計算された証明情報Ｒを出力手段４より出力する（ステップ１６−６）。
【００７０】
ここで、認証補助情報に付加された識別子は入力手段２で分離されるとしたが、演算手段３で行うようにしてもよいし、入力手段２に入力する時点で別々に入力されるようにしてもよい。
【００７１】
以上説明したように、本発明の実施例によれば、異なる認証補助情報も用いることにより検証者に応じた多様な証明情報を生成することが可能となる。また、認証補助情報を順次生成して証明情報を取り出すことにより、秘密情報を回復することができる。また、証明情報生成の履歴を残すことが可能となり、この履歴を、監査、認証回数による利用量課金等に用いることができる。
【００７２】
【発明の効果】
以上説明したように、本発明によれば、異なる認証補助情報も用いることにより検証者に応じた多様な証明情報を生成することが可能となる。また、認証補助情報を順次生成して証明情報を取り出すことにより、秘密情報を回復することができる。
【図面の簡単な説明】
【図１】  本発明の実施例１の構成を示すブロック図である。
【図２】  上述実施例１の入力データの構成を示す図である。
【図３】  上述実施例１の処理の流れを示すフローチャートである。
【図４】  本発明の実施例２の構成を示すブロック図である。
【図５】  上述実施例２の入力データの構成を示す図である。
【図６】  上述実施例２の処理の流れを示すフローチャートである。
【図７】  本発明の実施例３の構成を示すブロック図である。
【図８】  上述実施例３の処理の流れを示すフローチャートである。
【図９】  本発明の実施例４の処理の流れを示すフローチャートである。
【図１０】  本発明の実施例５の構成を示すブロック図である。
【図１１】  上述実施例５の処理の流れを示すフローチャートである。
【図１２】  上述実施例５の処理の流れを示すフローチャートである。
【図１３】  本発明の実施例６の構成を示すブロック図である。
【図１４】  上述実施例６の処理の流れを示すフローチャートである。
【図１５】  本発明の実施例の構成を示すブロック図である。
【図１６】  上述実施例７の入力データの構成を示す図である。
【図１７】  上述実施例７の処理の流れを示すフローチャートである。
【符号の説明】
１    秘密情報保持手段
２    入力手段
３    演算手段
４    出力手段
５    署名検証情報保持手段
６    署名検証手段
７    認証補助情報保持手段
８    認証補助情報判定手段
９    認証情報記憶手段
１０    数列記憶手段
１１    認証補助情報記憶手段
１２    証明情報記憶手段
１３    秘密情報回復手段
１４    秘密情報出力手段
１５    履歴記憶手段
【図１】
0003700333.tif 000006
【図２】
0003700333.tif 000007
【図３】
0003700333.tif 000008
【図４】
0003700333.tif 000009
【図５】
0003700333.tif 000010
【図６】
0003700333.tif 000011
【図７】
0003700333.tif 000012
【図８】
0003700333.tif 000013
【図９】
0003700333.tif 000014
【図１０】
0003700333.tif 000015
【図１１】
0003700333.tif 000016
【図１２】
0003700333.tif 000017
【図１３】
0003700333.tif 000018
【図１４】
0003700333.tif 000019
【図１５】
0003700333.tif 000020
【図１６】
0003700333.tif 000021
【図１７】
0003700333.tif 000022