(57)【要約】【課題】認証の連続失敗回数が所定の回数を超えた場合に認証処理を拒絶する認証装置。【解決手段】  認証装置自身の利用者が正規利用者であるか否かを判定する認証装置であって、認証の合否を判定する認証判定部１０２と、認証失敗回数に依存する第一の状態情報を記憶する第一の状態記憶部１０３と、認証失敗回数に依存する第二の状態情報を記憶する第二の状態記憶部１０４と、認証判定部が認証に失敗したときに、第一の状態を更新する第一の状態更新部１０５と、認証判定部が認証に合格したときに、第一の状態に基づいて第二の状態を更新する第二の状態更新部１０５と、第一の状態および第二の状態に基づいて認証の連続失敗回数が所定の回数以下であるかを判定する状態判定部１０７と、認証判定部および状態判定部の判定結果に基づいて認証処理等を制御する制御部１０８とを備えることを特徴とする認証装置。【選択図】図１
2009076034.tif 000002
【特許請求の範囲】
【請求項１】
認証装置自身の利用者が正規利用者であるか否かを判定する認証装置であって、
認証の要求および認証で用いるデータを受け付ける入出力部と、
前記認証で用いるデータに基づいて認証の合否を判定する認証判定部と、
第一の状態情報あるいは第二の状態情報を更新する場合に用いられる更新情報を記憶するパラメータ記憶部と、
前記更新情報と認証失敗回数とに依存する前記第一の状態情報を記憶する第一の状態情報記憶部と、
認証失敗回数に依存する前記第二の状態情報を記憶する第二の状態情報記憶部と、
前記認証判定部が認証に失敗したと判定するときに、前記更新情報に基づいて前記第一の状態情報を更新する第一の状態情報更新部と、
前記認証判定部が認証に合格したと判定するときに、前記第一の状態情報に基づいて前記第二の状態情報を更新する第二の状態情報更新部と、
前記第一の状態情報および前記第二の状態情報に基づいて認証の連続失敗回数が所定の回数以下であるかを判定する状態判定部と、
前記認証判定部の判定結果および前記状態判定部の判定結果に依存して認証処理の実行可否を制御する制御部とを備え、
前記認証判定部は、認証処理の実行が可となった場合に認証の合否を判定すること
を特徴とする認証装置。
【請求項２】
前記第二の状態情報更新部は、前記認証判定部が認証に合格したと判定するときに、第二の状態情報と更新情報に基づいて、第二の状態情報を第一の状態情報よりもＭステップ（Ｍは０より大きい整数値）初期状態（情報）に近い状態へと更新し、
前記状態判定部は第一の状態情報と第二の状態情報の差がＭステップ以上Ｎ＋Ｍステップ未満であるときに、認証の連続失敗回数が所定の回数（Ｎ回、Ｎは０より大きい整数値）以下であると判定する
ことを特徴とする請求項1記載の認証装置。
【請求項３】
前記第二の状態情報更新部は、前記認証判定部が認証に合格したと判定するときに、第一の状態情報と更新情報に基づいて、第二の状態情報を第一の状態情報よりもＮ＋Ｍ−１ステップ（Ｎ，Ｍは０より大きい整数値）初期状態よりも先の状態へと更新し、
前記状態判定部は第二の状態情報と第一の状態情報の差がＭステップ以上Ｎ＋Ｍステップ未満であるときに、認証の連続失敗回数が所定の回数（Ｎ回）以下であると判定する
ことを特徴とする請求項１記載の認証装置。
【請求項４】
前記第二の状態情報更新部は、前記認証判定部が認証に用いる情報から計算される更新情報、および第一の状態情報に基づいて第二の状態情報を更新する
ことを特徴とする請求項1記載の認証装置。
【請求項５】
前記パラメータ記憶部は、更新情報と付加情報計算データを記憶し、
前記第二の状態情報更新部は、前記認証判定部が認証に合格したと判定するときに、第二の状態情報を第一の状態情報および付加情報計算データに依存する情報とに更新し、
前記状態判定部は、付加情報計算データに基づいて第二の状態情報が不正な書き換えが行われていないかを検査し、さらに第一の状態情報と第二の状態情報の部分情報とに基づいて認証の連続失敗回数が所定の回数（Ｎ回、Ｎは０より大きい整数値）以下であること
を判定する
ことを特徴とする請求項１記載の認証装置。
【請求項６】
前記第一の状態情報更新部は、一方向性関数を用いて算出した値に第一の状態情報を更新する
ことを特徴とする請求項１記載の認証装置。
【請求項７】
前記第一の状態情報更新部は、一方向性関数を用いて算出した値に第一の状態情報を更新する  前記第二の状態情報更新部は、前記認証判定部が認証に合格したと判定するときに、第二の状態情報と更新情報に基づいて、第二の状態情報を第一の状態情報よりもＭステップ（Ｍは０より大きい整数値）初期状態（情報）に近い状態へと更新し、
前記状態判定部は第一の状態情報が、第二の状態情報をＭステップ以上Ｎ＋Ｍステップ未満更新した値と一致するか否かを検査し、一致するものがあるときに、認証の連続失敗回数が所定の回数（Ｎ回、Ｎは０より大きい整数値）以下であると判定する
ことを特徴とする請求項1記載の認証装置。
【請求項８】
前記第一の状態情報更新部は、一方向性関数を用いて算出した値に第一の状態情報を更新し、
前記第二の状態情報更新部は、前記認証判定部が認証に合格したと判定するときに、前記認証判定部が認証に用いる情報から計算される更新情報、および第一の状態情報および
第二の状態情報に基づいて、第二の状態情報を第一の状態情報よりもＭステップ（Ｍは０より大きい整数値）初期状態（情報）に近い状態へと更新し、
前記状態判定部は第一の状態情報が、第二の状態情報をＭステップ以上Ｎ＋Ｍステップ未満更新した値と一致するか否かを検査し、一致するものがあるときに、認証の連続失敗回数が所定の回数（Ｎ回、Ｎは０より大きい整数値）以下であると判定する
ことを特徴とする請求項1記載の認証装置。
【請求項９】
前記パラメータ記憶部は、更新情報と付加情報計算データを記憶し、
前記第一の状態情報更新部は、一方向性関数を用いて算出した値に第一の状態情報を更新し、
前記第二の状態情報更新部は、前記認証判定部が認証に合格したと判定するときに、第二の状態情報を第一の状態情報と第一の状態情報および付加情報計算データに依存する情報とに更新し、
前記状態判定部は、付加情報計算データに基づいて第二の状態情報が不正な書き換えが行われていないかを検査し、さらに第一の状態情報と第二の状態情報の部分情報とに基づいて認証の連続失敗回数が所定の回数（Ｎ回、Ｎは０より大きい整数値）以下であること
を判定する
ことを特徴とする請求項１記載の認証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、認証装置の利用者が所定の回数以上連続して認証に失敗する場合には以後の認証処理を受け付けないことにより、認証装置の不正利用を防止するための認証装置に関わる。
【背景技術】
【０００２】
ＩＣカードやモバイル端末などの持ち運び可能なデバイスが広く使用されているが、これらのデバイスは遺失や盗難などにより悪意のある不特定多数に利用される恐れがある。
【０００３】
そのため、デバイスの利用者が正規利用者であるか否かを判定した後にデバイスの利用を許可することの重要性は大きい。
【０００４】
デバイスの利用者が正規利用者であるか否かを判定する手法として、パスワードや生体情報などを用いた認証が用いられる。しかし、認証で用いる情報は有限であるため、総当り的に認証を試行されると悪意ある利用を十分に防ぐことはできない。そこで、認証の試行回数に上限を設け、一定の回数以上認証に失敗したら以後の認証を受け付けない（ロックする）ことがよく知られている。この手法では、認証の試行回数あるいは失敗回数を記憶するカウンタを実装する必要がある。
【０００５】
近年、認証装置の動作時の消費電力や漏洩電磁波を観測することで認証装置内部の状態を推測する解析手法や、認証装置への供給電源を故意に変化させたり認証装置に高エネルギーの光を照射したりすることで誤動作を誘発してデータを書き換えて内部の秘密データを推測する解析手法など、認証装置に対する物理的な解析が多数報告されている。
【０００６】
上述の認証の総当り的な試行を防ぐ目的で認証の失敗回数を記憶するカウンタを実装する場合、物理的な解析によりカウンタ値が初期化されてしまうと試行回数の制限が意味をなさないため、悪意ある利用を十分に防ぐことはできない。
【０００７】
非特許文献１は、物理的な解析によりデータを変化させることができるメモリ領域を「書込みのみ可能なメモリ領域（Ｗｒｉｔｅ Ｏｎｌｙ Ｍｅｍｏｒｙ）」とみなして、上述の総当り的な試行を防ぐことができる書込みのみ可能なメモリ領域へのカウンタの実装方法を開示している。物理的な解析ではデータを意図した値に変化させることは一般には困難であるが、非特許文献１で開示された方法では仮にデータを意図した値に書き換えることができたとしても、悪意ある利用から認証装置を保護することが可能である。
【０００８】
しかし、非特許文献１は認証の通算失敗回数が所定の回数を超えた場合に認証装置をロックする方法を開示しているが、認証の連続失敗回数が所定の回数を超えた場合に認証装置をロックする適切な方法は開示されていない。
【非特許文献１】R. Gennaro, et al., “Algorithmic Tamper-Proof Security: Theoretical Foundations for Security against Hardware Tampering”, Theory of Cryptography Conference 2004, Lecture Notes in Computer Science 2951, pp. 258-277, Springer-Verlag
【発明の開示】
【発明が解決しようとする課題】
【０００９】
非特許文献１で開示されている手法のように、認証の通算失敗回数に基づいて認証装置をロックする場合には、正規の利用者の誤入力に配慮して上限を高めに設定することが一般的である。一方で、上限を高めに設定すると認証の試行回数が増えるため安全性が低下してしまうという問題があった。
【００１０】
本発明は、上記従来技術の問題点を解決するためになされたものであって、認証の連続失敗回数が所定の回数を超えた場合に認証装置をロックする認証装置に関わる。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明の実施形態に係る認証装置は、  認証で用いるデータを受け渡す入出力部と、前記データに基づいて認証の合否を判定する認証判定部と、第一あるいは第二の状態を更新する更新情報を記憶するパラメータ記憶部と、前記更新情報と認証失敗回数とに依存する第一の状態（第一の状態情報）を記憶する第一の状態記憶部と、認証失敗回数に依存する第二の状態（第二の状態情報）を記憶する第二の状態記憶部と、前記認証判定部が認証に失敗したと判定するときに、前記更新情報に基づいて前記第一の状態を更新する第一の状態更新部と、前記認証判定部が認証に合格したと判定すると
きに、前記第一の状態と前記更新情報とに基づいて前記第二の状態を更新する第二の状態更新部と、前記第一および第二の状態記憶部に記憶される第一および第二の状態に基づいて認証の連続失敗回数が所定の回数（Ｎ回、Ｎは０より大きい整数値）以下であるかを判定する状態判定部と、前記認証判定部および状態判定部の判定結果に依存してデバイスの利用可否や認証処理の実行有無を制御する制御部とを備えることを特徴とする
【発明の効果】
【００１２】
本発明によれば、認証の連続失敗回数が所定の回数を超えた場合に認証装置をロックし、物理的な解析に対しても悪意ある利用から認証装置を保護できる認証装置を提供することが可能となる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施形態について説明する。
【００１４】
（第１の実施形態）
（基本構成）
図１は本発明の第1の実施形態に係る認証装置１００の内部構成を示すブロック図である。認証装置１００は、入出力部１０１と、認証判定部１０２と、第一の状態記憶部１０３と、第二の状態記憶部１０４と、第一の状態更新部１０５と、第二の状態更新部１０６と、状態判定部１０７と、制御部１０８と、パラメータ記憶部１０９とを備える。
【００１５】
例えば、認証装置１００は、ＩＣカードなどである。利用者は、認証装置１００を用いて認証を行い、キャッシュディスペンサーなどでサービスを受ける。例えば、利用者は、ＩＣカードをキャッシュディスペンサーに挿入し、キャッシュディスペンサーを介して正規な利用者であることの認証を受け、キャッシュディスペンサーのサービスを受ける。
【００１６】
入出力部１０１は、認証装置１００に接続された外部の装置（図示せず）を介して認証を要求する要求者が操作することにより、当該外部の装置から送信された認証の要求と認証用のデータを受け付けて、状態判定部１０７に状態判定の要求を出力する。後述する認証判定部１０２から認証用のデータ取得要求を受けると、認証用のデータを認証判定部１０２に出力する。また、認証結果を外部の装置に出力する。
【００１７】
なお、認証用のデータは、認証判定部１０２から取得要求を受け取った後に外部の装置へ要求して取得しても良く、認証要求と一緒に取得しても良い。
【００１８】
ここで、外部装置とは少なくとも認証要求と認証用のデータを入出力部１０１に出力する装置であり、例えば、ＩＣカードの読取装置などがある。
【００１９】
認証の要求は、認証を要求する情報である。認証を要求する情報は、認証装置１００に対する外部からの働きをトリガーとして生成されるか、または、そのトリガー自体を認証を要求する情報としても良い。ここで、外部からの働きとしては、例えば、認証装置１００への電力供給などがある。
【００２０】
認証用のデータとは利用者を識別する利用者識別情報である。例えば、利用者識別情報には、パスワード情報や、生体情報や、対話の情報を用いて認証する場合は対話の情報なども含む。また、ここで、利用者とは認証装置１００の利用者であることを意味するが、認証装置１００を介してサービスなどを受ける利用者という意味も含めてもよい。
【００２１】
認証結果とは認証に合格したという情報、または、認証に不合格という情報である。
【００２２】
認証判定部１０２は、制御部１０８から認証処理の実行の指示を受けると、認証用のデータに基づいて認証の要求者が正規の利用者であるか否かを判定する。そして、認証判定部１０２の判定結果を入出力部１０１に出力する。
【００２３】
具体的には、認証に不合格の場合には、第一の状態更新部１０５に第一の状態の更新を指示して、更に入出力部１０１に認証不合格の情報を出力する。
【００２４】
また、認証に合格の場合には、第二の状態更新部１０６に第二の状態の更新を指示して、更に入出力部１０１に認証合格の情報を出力する。
【００２５】
また、認証判定部１０２は、制御部１０８から認証処理の停止の指示を受け付けると、認証処理を停止し、認証処理を停止した旨を入出力部１０１に出力する。
【００２６】
第一の状態記憶部１０３は、認証失敗回数に依存する情報である第一の状態（第一の状態情報）を記憶する。
【００２７】
ここで、例えば、第一の状態は認証の失敗回数に依存するデータＪ（Ｊは整数値、初期値を整数値Ｊ０とする。Ｊ０はランダムあるいは意図した値として設定される）からなる。
【００２８】
第二の状態記憶部１０４は、直近（最新）の認証成功時における認証失敗回数に依存する情報である第二の状態（第二の状態情報）を記憶する。
【００２９】
ここで、第二の状態は、例えば、データＫ（Ｋは整数値、初期値はＪの初期値Ｊ０を用いる）を用いる。
【００３０】
第一の状態更新部１０５は、認証判定部１０２が認証に失敗したと判定するときに後述するパラメータ記憶部１０９が記憶する更新情報と更新前の第一の状態に基づいて、更新後の第一の状態を生成し、第一の状態を更新する。
【００３１】
ここで、更新情報とは、更新の前後で、更新対象の値を変える際に用いられる情報であり、Ｓで表す。
【００３２】
ここで、第一の状態は、更新関数Ｆに基づいて更新する。以下の説明では、更新関数Ｆはｘと更新情報Ｓを入力としてＦ（ｘ，Ｓ）＝ｘ＋Ｓを計算する関数であるとする。
【００３３】
第二の状態更新部１０６は、認証判定部１０２から第二の状態の更新の指示を受け付けるときに第一の状態に基づいて第二の状態を更新する。
【００３４】
更新の仕方としては、例えば、第一の状態記憶部１０３から第一の状態Ｊを入手し、第二の状態記憶部１０４に記憶される第二の状態ＫをＪに更新する。
【００３５】
状態判定部１０７は、認証の連続失敗回数が所定の回数以下であることを判定する。また、後述するパラメータ記憶部１０９が記憶する更新情報に基づいて第一の状態が健全であることおよび第二の状態が健全であることを判定してもよい。
【００３６】
ここで、第一の状態が健全であるとは、第一の状態について不正な書き換えが行われていないことを意味し、第二の状態が健全であるとは、第二の状態について不正な書き換えが行われていないことを意味する。
【００３７】
また、状態判定部１０７が許容する認証の連続失敗回数の上限（上限回数）をＮで表す（例えば３回連続して認証に失敗したらデバイスをロックする場合にはＮ＝３とする）。
【００３８】
例えば、状態判定部１０７は、第一の状態記憶部１０３から第一の状態Ｊを読み出し、第二の状態記憶部１０４から第二の状態Ｋを読み出し、パラメータ記憶部１０９から上限回数Ｎ、更新情報Ｓを読み出す。そして、読み出したＪ、Ｋ、Ｎ、Ｓと基づいて、Ｊ−Ｋが０以上Ｎ＊Ｓ未満のＳの倍数であることを検査する。検査に合格するときには制御部１０８に合格を伝え、不合格の場合には制御部１０８に不合格を伝える。
【００３９】
ここで、正しく（物理的な解析によるデータの書き換えなどが行なわれることなく）認証処理が行われている場合に、利用者が認証の要求にＬ回連続（Ｌ＝０，１，．．．，Ｎ−１）して失敗するとき、第一の状態Ｊと第二の状態Ｋの間にはＫ≦Ｊ＝Ｋ＋Ｌ＊Ｓ＜Ｋ＋Ｎ＊Ｓの関係が成り立つ。一方、Ｌ＝Ｎ回連続して失敗してしまうと、Ｊ＝Ｋ＋Ｎ＊Ｓとなる。すなわち、正しく認証処理が行われるとき、認証の連続失敗回数がＮ回未満であることはＪ−Ｋが０以上Ｎ＊Ｓ未満のＳの倍数であるときに限られる。
【００４０】
制御部１０８は、状態判定部１０７の判定結果に基づいて認証装置１００の利用可否または認証処理の実行可否を制御する。
【００４１】
具体的には、状態判定部１０７から合格を受け取る場合には認証判定部１０２に認証処理の実行を指示する。一方、状態判定部１０７から不合格を受け取る場合には認証判定部１０２に認証処理の停止を指示して認証装置１００の利用要求を拒絶する（認証処理の終了）。
【００４２】
パラメータ記憶部１０９は、更新情報Ｓおよび認証の連続失敗回数の上限Ｎを記憶する。
【００４３】
なお、本実施の形態や以降の例では、デバイスのメモリ領域（または記憶装置）は、外部から読み出しも書き込みも可能な領域Ｉ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ＲＡＭ）、外部から読み出しは可能だが書き込みは不可能な領域ＩＩ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ、ＲＯＭ）、外部から書き込みは可能だが読み出しは不可能な領域ＩＩＩ（物理的な解析によりデータを操作可能な領域、Ｗｒｉｔｅ Ｏｎｌｙ Ｍｅｍｏｒｙ）、外部からの書き込みも読み出しも不可能な領域ＩＶ（最も安全な耐タンパ実装が施された領域）の４つに分類される。
【００４４】
また、認証の連続失敗回数の上限Ｎと更新関数Ｆを領域ＩＩに、第一の状態Ｊおよび第二の状態Ｋを領域ＩＩＩに、更新情報Ｓを領域ＩＶに記憶する（Ｓを公開情報とする場合には領域ＩＩに記憶する。以降ではＳは秘密情報であるとして領域ＩＶに記憶されるものとする）。すなわち、第一および第二の状態記憶部１０３と１０４は領域ＩＩＩであり、パラメータ記憶部１０９は領域ＩＶである。
【００４５】
また、ここでいう、認証の失敗回数または更新回数が、特許請求の範囲のステップに相当する。つまり、各１回が１ステップに該当する。
【００４６】
次に、本実施の形態の認証装置１００の動作について説明する。
【００４７】
入出力部１０１は外部より認証要求を受け付けたら（認証処理の開始）、状態判定部１０７に状態の判定を要求する。
【００４８】
状態判定部１０７は、第一の状態記憶部１０３から第一の状態Ｊを読み出し、第二の状態記憶部１０４から第二の状態Ｋを読み出し、パラメータ記憶部１０９から更新情報Ｓ、認証の連続失敗回数の上限Ｎを読み出す。そして、読み出したＪ、Ｋ、Ｓ、Ｎに基づいて、Ｊ−Ｋが０以上Ｎ＊Ｓ未満のＳの倍数であることを検査する。検査に合格するときには制御部１０８に合格を伝え、不合格の場合には制御部１０８に不合格を伝える。
【００４９】
制御部１０８は、状態判定部１０７から合格を受け取る場合には認証判定部１０２に認証処理の実行を指示する。一方、状態判定部１０７から不合格を受け取る場合には認証判定部１０２に認証処理の停止を指示して認証装置１００の利用要求を拒絶する（認証処理の終了）。
【００５０】
認証判定部１０２は、認証処理の実行が指示されるとき、パスワードや生体情報など認証用のデータに基づいて認証処理を実行する。そして、認証に合格する場合には第二の状態更新部１０６に第二の状態の更新を指示して入出力部１０１に認証合格を伝え、認証に不合格の場合には第一の状態更新部１０５に第一の状態の更新を指示して入出力部１０１に認証不合格を伝える。
【００５１】
ここで、認証判定部１０２は、認証処理の実行が指示されると入出力部１０１に認証用のデータの取得要求を行い、入出力部１０１はその要求に応じて、外部の装置を介して認証用のデータを取得して認証判定部１０２に認証用のデータを受け渡すこともでき、また、入出力部１０１が認証用のデータを予め取得している場合は、入出力部１０１に認証用のデータの取得要求を行って、入出力部１０１から取得しても良い。
【００５２】
第二の状態更新部１０６は第二の状態の更新の指示を受けたら、第一の状態記憶部１０３から第一の状態Ｊを入手し、第二の状態記憶部１０４に記憶される第二の状態ＫをＪに更新する。
【００５３】
第一の状態更新部１０５は第一の状態の更新の指示を受けたら、パラメータ記憶部１０９から更新情報Ｓと更新関数Ｆを入手し、入手したＳと第一の状態記憶部１０３に記憶される第一の状態Ｊとに基づいて、Ｆ（Ｊ，Ｓ）＝Ｊ＋Ｓを計算し、ＪをＦ（Ｊ，Ｓ）、つまりＪ＋Ｓに更新する。
【００５４】
制御部１０８は認証合格を受け付けた場合には利用者から認証装置１００の利用要求を許可し（認証処理の終了）、認証不合格を受け付けた場合には利用者から認証装置１００の利用要求を拒絶する（認証処理の終了）。
【００５５】
入出力部１０１は、認証結果を受け付けると外部の装置に出力する。外部の装置は自己の利用を許可または拒絶をしたり、また、認証結果を表示などする。例えば、認証結果を受けた外部の装置がキャッシュディスペンサー自体のサービスを許可または拒絶する制御を行うことにより、利用者はサービスを受けたり、受けることができなかったりする。
【００５６】
ここで、第一の状態および第二の状態は領域ＩＩＩに記憶されているため、攻撃者はＪとＫを読み出すことはできない。一方、更新情報Ｓは領域ＩＶに記憶されているため、攻撃者はＳを読み出すことも書き換えることもできない。
【００５７】
攻撃者はＳを読み出すことができないため、第一の状態ＪをＪ’−Ｋが０以上Ｎ＊Ｓ未満のＳの倍数となるようなＪ’に書き換えることは困難である。
【００５８】
同様に、攻撃者はＳを読み出すことができないため、第二の状態ＫをＪ−Ｋ’が０以上Ｎ＊Ｓ未満のＳの倍数となるようなＫ’に書き換えることは困難である。
【００５９】
（変形例１）
基本構成の具体例では、物理的な解析により第一の状態と第二の状態を同一の状態に書き換えることができれば認証の試行を何度も繰り返すことが可能であった。
【００６０】
変形例１では、認証判定部が認証に合格したと判定するときに第二の状態と秘密情報に基づいて、第二の状態を第一の状態よりもＭステップ（Ｍは０より大きい整数値）初期状態（情報）に近い状態へと更新する。認証成功時の第一および第二の状態に差分を設けることにより、第一の状態と第二の状態を同一の状態に書き換えたとしても認証を試行することができない。
【００６１】
［変形例１の認証装置の構成］
図２は変形例１に係る認証装置の構成を示すブロック図である。
【００６２】
装置構成は基本構成とほぼ同一であるが、パラメータ記憶部２０９から第二の状態更新部２０６へのデータパスが増え、第二の状態更新部２０６、状態判定部２０７、パラメータ記憶部２０９が異なるが、他の構成要素については、名称が同一のものは図の番号は異なるが機能は同様である。
【００６３】
ここで、認証の連続失敗回数の上限Ｎ、更新情報Ｓ、第一の状態Ｊ、第二の状態Ｋ、更新関数Ｆ（Ｆ（ｘ，Ｓ）をｘ＋Ｓで定める）は基本構成と同じ意味で用い、基本構成と同じメモリ領域に記憶されているものとする。ただし、第二の状態Ｋの初期値をＫ０（Ｋ０は整数値。ランダムあるいは意図した値として設定される）とするとき、第一の状態の初期値Ｊ０は、Ｋ０に更新関数をＭ回（Ｍは０より大きい整数値）施した値であり、Ｊ０＝Ｆ（Ｆ（・・・（Ｆ（Ｋ０，Ｓ），Ｓ）・・・），Ｓ）＝Ｋ０＋Ｍ＊Ｓにより定める。Ｍはパラメータ記憶部２０９の領域ＩＩに記憶される。
【００６４】
第１の実施形態と異なる構成要素のみについて、以下に説明する。
【００６５】
第二の状態更新部２０６は認証判定部２０２から第二の状態の更新の指示を受けたら、第一の状態記憶部２０３から第一の状態Ｊとパラメータ記憶部２０９から更新回数Ｍおよび更新情報Ｓを入手してＪ−Ｍ＊Ｓを計算し、第二の状態記憶部２０４に記憶される第二の状態ＫをＪ−Ｍ＊Ｓに更新する。
【００６６】
状態判定部２０７は、第一の状態記憶部２０３から第一の状態Ｊを読み出し、第二の状態記憶部２０４から第二の状態Ｋを読み出し、パラメータ記憶部２０９から更新回数Ｍ、上限Ｎ、更新情報Ｓを読み出す。そして、読み出したＪ、Ｋ、Ｍ、Ｎ、Ｓに基づいて、Ｊ−ＫがＭ＊Ｓ以上（Ｎ＋Ｍ）＊Ｓ未満のＳの倍数であることを検査する。検査に合格するときには制御部２０８に合格を伝え、不合格の場合には制御部２０８に不合格を伝える。
【００６７】
ここで、正しく（物理的な解析によるデータの書き換えなどが行なわれることなく）認証処理が行われている場合に、利用者が認証の要求にＬ回連続（Ｌ＝０，１，．．．，Ｎ−１）して失敗するとき、第一の状態Ｊと第二の状態Ｋの間にはＫ＋Ｍ＊Ｓ≦Ｊ＝Ｋ＋（Ｍ＋Ｌ）＊Ｓ＜Ｋ＋（Ｍ＋Ｎ）＊Ｓの関係が成り立つ。一方、Ｌ＝Ｎ回連続して失敗してしまうと、Ｊ＝Ｋ＋（Ｍ＋Ｎ）＊Ｓとなる。すなわち、正しく認証処理が行われるとき、認証の連続失敗回数がＮ回未満であることはＪ−ＫがＭ＊Ｓ以上（Ｍ＋Ｎ）＊Ｓ未満のＳの倍数であるときに限られる。
【００６８】
パラメータ記憶部２０９は、認証の連続失敗回数Ｎ、第一の状態の初期値Ｊ０を決定するためにＫ０に施す更新関数の回数（更新回数）Ｍ、更新情報Ｓ、更新関数Ｆを記憶する。
【００６９】
次に、本変形例の認証装置２００の動作について説明する。
【００７０】
入出力部２０１は外部の装置より認証要求を受け付けたら（認証処理の開始）、状態判定部２０７に状態の判定を要求する。
【００７１】
状態判定部２０７は、第一の状態記憶部２０３から第一の状態Ｊを読み出し、第二の状態記憶部２０４から第二の状態Ｋを読み出し、パラメータ記憶部２０９から更新回数Ｍ、更新情報Ｓを読み出す。そして、読み出したＪ、Ｋ、Ｍ、Ｓと基づいて、Ｊ−ＫがＭ＊Ｓ以上（Ｎ＋Ｍ）＊Ｓ未満のＳの倍数であることを検査する。検査に合格するときには制御部２０７に合格を伝え、不合格の場合には制御部２０７に不合格を伝える。
【００７２】
制御部２０８は、状態判定部２０７から合格を受け取る場合には認証判定部２０２に認証処理の実行を指示する。一方、状態判定部２０７から不合格を受け取る場合には認証判定部２０２に認証処理の停止を指示してデバイスの利用要求を拒絶する（認証処理の終了）。
【００７３】
認証処理の実行が指示されるとき、認証判定部２０２はパスワードや生体情報など認証要求者を識別する情報に基づいて認証処理を実行する。認証に合格する場合には第二の状態更新部２０６に第二の状態の更新を指示して入出力部２０１に認証合格を伝え、認証に不合格の場合には第一の状態更新部２０５に第一の状態の更新を指示して入出力部２０１に認証不合格を伝える。
【００７４】
第二の状態更新部２０６は第二の状態の更新の指示を受けたら、第一の状態記憶部２０３から第一の状態Ｊとパラメータ記憶部２０９から更新回数Ｍおよび更新情報Ｓを入手してＪ−Ｍ＊Ｓを計算し、第二の状態記憶部２０４に記憶される第二の状態ＫをＪ−Ｍ＊Ｓに更新する。
【００７５】
第一の状態更新部２０５は第一の状態の更新の指示を受けたら、パラメータ記憶部２０９から更新情報Ｓと更新関数Ｆを入手し、第一の状態記憶部２０３に記憶される第一の状態ＪをＦ（Ｊ，Ｓ）＝Ｊ＋Ｓに更新する。
【００７６】
入出力部２０１は、認証結果を受け付けると外部の装置に出力し、外部の装置は自己の利用を許可または拒絶をしたりする。例えば、認証結果を受けた外部の装置がキャッシュディスペンサー自体のサービスを許可または拒絶する制御を行うことにより、利用者はサービスを受けたり、受けることができなかったりする。
【００７７】
ここで、第一の状態および第二の状態は領域ＩＩＩに記憶されているため、攻撃者はＪとＫを読み出すことはできない。一方、更新情報Ｓは領域ＩＶに記憶されているため、攻撃者はＳを読み出すことも書き換えることもできない。また、更新回数Ｍは領域ＩＩに記憶されているため、攻撃者はＭを書き換えることはできない。
【００７８】
攻撃者はＳを読み出すことができないため、第一の状態ＪをＪ’−ＫがＭ＊Ｓ以上（Ｍ＋Ｎ）＊Ｓ未満のＳの倍数となるようなＪ’に書き換えることは困難である。
【００７９】
同様に、攻撃者はＳを読み出すことができないため、第二の状態ＫをＪ−Ｋ’がＭ＊Ｓ以上（Ｍ＋Ｎ）＊Ｓ未満のＳの倍数となるようなＫ’に書き換えることは困難である。
【００８０】
一方、第一の状態Ｊと第二の状態ＫをともにＪ’とＪ’に書き換えると、状態判定部２０７により不合格と判定されるため、悪意ある認証の試行を行うことはできない。他方、攻撃者はＳを読み出すことができないため、第一の状態Ｊと第二の状態ＫをＫ’−Ｊ’がＭ＊Ｓ以上（Ｍ＋Ｎ）＊Ｓ未満のＳの倍数となるようなＪ’とＫ’に書き換えることは困難である。
【００８１】
（変形例２）
変形例１では、第一の状態Ｊと第二の状態Ｋの間にＪ＞Ｋの関係をもたせた。変形例２においては、Ｊ＜Ｋの関係をもたせる認証装置とその動作手順を開示する。
【００８２】
［変形例２の認証装置の構成］
図３は変形例２に係る認証装置の構成を示すブロック図である。装置構成は変形例１とほぼ同一であるが、第二の状態記憶部３０４に記憶する初期値と、第二の状態更新部３０６と、状態判定部３０７が異なり、以下にその異なる構成についてのみ説明する。
【００８３】
まず、認証の連続失敗回数の上限Ｎ、更新情報Ｓ、第一の状態Ｊ、第二の状態Ｋ、更新関数Ｆ（Ｆ（ｘ，Ｓ）をｘ＋Ｓで定める）、更新回数Ｍは変形例１と同じ意味で用い、変形例１と同じメモリ領域に記憶されているものとする。ただし、第一の状態Ｊの初期値をＪ０（Ｊ０は整数値。ランダムあるいは意図した値に設定される）とするとき、第二の状態の初期値Ｋ０をＪ０に更新関数を（Ｍ＋Ｎ−１）回（Ｍは０より大きい整数値）施したＫ０＝Ｆ（Ｆ（・・・（Ｆ（Ｊ０，Ｓ），Ｓ）・・・），Ｓ）＝Ｊ０＋（Ｍ＋Ｎ−１）＊Ｓにより定める。
【００８４】
Ｋ０は、予め上述にて定められた方式により計算して第二の状態記憶部３０４に記憶しておいても良く、また、認証装置１００内に初期値生成手段として設け（図示せず）、Ｊ０、Ｍ、Ｎを入力とし、上述に定められた方式により生成して、第二の状態記憶部３０４に記憶させても良い。
【００８５】
第二の状態記憶部３０４に記憶する初期値は、上記のように定められたＫ０である。
【００８６】
第二の状態更新部３０６は、第二の状態の更新の指示を受けたら、第一の状態記憶部３０３から第一の状態Ｊを読み出し、パラメータ記憶部３０９から更新回数Ｍ、上限回数Ｎ、更新情報Ｓを読み出してＪ＋（Ｍ＋Ｎ−１）＊Ｓを計算する。そして、第二の状態記憶部３０４に記憶される第二の状態ＫをＪ＋（Ｍ＋Ｎ−１）＊Ｓに更新する。
【００８７】
状態判定部３０７は、第一の状態記憶部３０３から第一の状態Ｊを読み出し、第二の状態記憶部３０４から第二の状態Ｋを読み出し、パラメータ記憶部３０９から更新回数Ｍ、上限回数Ｎ、更新情報Ｓを読み出す。そして、読み出したＪ、Ｋ、Ｓ、Ｍ、Ｎに基づいて、Ｋ−ＪがＭ＊Ｓ以上（Ｍ＋Ｎ）＊Ｓ未満のＳの倍数であることを検査する。検査に合格するときには制御部３０７に合格を伝え、不合格の場合には制御部３０７に不合格を伝える。
【００８８】
変形例２における認証装置の動作を以下に説明する。
【００８９】
認証装置３００は、入出力部３０１より認証要求を受け付けたら（認証処理の開始）、状態判定部３０７に状態の判定を要求する。
【００９０】
状態判定部３０７は、第一の状態記憶部３０３から第一の状態Ｊを読み出し、第二の状態記憶部３０４から第二の状態Ｋを読み出し、パラメータ記憶部３０９から更新回数Ｍ、上限回数Ｎ、更新情報Ｓを読み出す。そして、読み出したＪ、Ｋ、Ｍ、Ｎ、Ｓに基づいて、Ｋ−ＪがＭ＊Ｓ以上（Ｍ＋Ｎ）＊Ｓ未満のＳの倍数であることを検査する。検査に合格するときには制御部３０８に合格を伝え、不合格の場合には制御部３０８に不合格を伝える。
【００９１】
状態判定部３０７の出力に対する制御部３０８の動作は変形例１と同様であるため説明は省略する。
【００９２】
認証判定部３０２の動作は変形例１と同一であるため説明は省略する。
【００９３】
第二の状態更新部３０６は第二の状態の更新の指示を受けたら、第一の状態記憶部３０３から第一の状態Ｊを読み出し、パラメータ記憶部３０９から更新回数Ｍ、上限回数Ｎ、更新情報Ｓを読み出してＪ＋（Ｍ＋Ｎ−１）＊Ｓを計算する。そして、第二の状態記憶部３０４に記憶される第二の状態ＫをＪ＋（Ｍ＋Ｎ−１）＊Ｓに更新する。
【００９４】
第一の状態更新部３０５の動作は変形例１と同様であるため説明は省略する。
【００９５】
認証判定部３０２の出力に対する制御部３０８の動作は変形例１と同様であるため説明は省略する。
【００９６】
ここで、正しく（物理的な解析によるデータの書き換えなどが行なわれることなく）認証処理が行われている場合に、利用者が認証の要求にＬ回連続（Ｌ＝０，１，．．．，Ｎ−１）して失敗するとき、第一の状態Ｊと第二の状態Ｋの間にはＪ＋Ｍ＊Ｓ≦Ｋ＝Ｊ＋（Ｍ＋Ｎ−１−Ｌ）＊Ｓ≦Ｊ＋（Ｍ＋Ｎ−１）＊Ｓの関係がなりたつ。すなわち、正しく認証処理が行われるとき、認証の連続失敗回数がＮ回未満であることはＫ−ＪがＭ＊Ｓ以上（Ｍ＋Ｎ）＊Ｓ未満のＳの倍数であるときに限られる。
【００９７】
また、第一の状態および第二の状態は領域ＩＩＩに記憶されているため、攻撃者はＪとＫを読み出すことはできない。一方、更新情報Ｓは領域ＩＶに記憶されているため、攻撃者はＳを読み出すことも書き換えることもできない。また、更新回数Ｍは領域ＩＩに記憶されているため、攻撃者は書き換えることができない。
【００９８】
攻撃者はＳを読み出すことができないため、第一の状態ＪをＫ−Ｊ’がＭ＊Ｓ以上（Ｍ＋Ｎ）＊Ｓ未満のＳの倍数となるようなＪ’に書き換えることは困難である。
【００９９】
同様に、攻撃者はＳを読み出すことができないため、第二の状態ＫをＫ’−ＪがＭ＊Ｓ以上（Ｍ＋Ｎ）＊Ｓ未満のＳの倍数となるようなＫ’に書き換えることは困難である。
【０１００】
一方、第一の状態Ｊと第二の状態ＫをともにＪ’とＪ’に書き換えると、状態判定部３０７により不合格と判定されるため、悪意ある認証の試行を行うことはできない。他方、攻撃者はＳを読み出すことができないため、第一の状態Ｊと第二の状態ＫをＫ’−Ｊ’がＭ＊Ｓ以上（Ｍ＋Ｎ）＊Ｓ未満のＳの倍数となるようなＪ’とＫ’に書き換えることは困難である。
【０１０１】
（変形例３）
変形例１では、第二の状態更新部２０６は第二の状態の更新の指示を受けたら、第一の状態記憶部２０３とパラメータ記憶部２０９からそれぞれ第一の状態Ｊと更新情報Ｓを入手して、第二の状態記憶部２０４に記憶される第二の状態Ｋを更新していた。しかし、攻撃者が第二の状態更新を直接実行することができると、認証の試行回数を増やすことができてしまう。また、変形例２の第二の状態更新部３０６も変形例１の第二の状態更新部２０６と同様のことが言える。
【０１０２】
そこで、変形例３では、更新情報Ｓを認証に用いるデータに基づいて計算される値とし、第二の状態更新部４０６は更新情報Ｓを状態記憶部４０９から入手するのではなく、認証判定部４０２で処理されるデータに基づいて再計算して第二の状態を更新する。これにより、攻撃者が第二の状態更新部４０６を直接実行できたとしても、正しい認証情報を入力しなければ次回の認証処理で状態判定部４０７において合格と判定されるように第二の状態を更新することは困難となる。
【０１０３】
以下ではパスワードを用いる装置を例に変形例３に係る認証装置とその動作手順を開示する。
【０１０４】
図４は変形例３に係る認証装置の構成を示すブロック図である。装置構成は第1の実施形態の変形例１とほぼ同一であるが、認証判定部４０２と、第二の状態記憶部４０４、第二の状態更新部４０６、パラメータ記憶部４０９が異なる。
【０１０５】
認証の連続失敗回数の上限Ｎ、第一の状態Ｊ、第二の状態Ｋ、更新回数Ｍを変形例１と同じ意味で用いる。
【０１０６】
また、利用者のパスワードをｐａｓｓであらわし、更新情報Ｓを更新情報生成関数Ｇにｐａｓｓを入力してＳ＝Ｇ（ｐａｓｓ）で定める。ここで、パラメータ記憶部４０９に記憶されるＳは予め、上述の式で求めておき、記憶しておく。更新関数Ｆ（Ｆ（ｘ，Ｓ）をｘ＋Ｓで定める）は基本構成と同じ意味で用いる。Ｍ，Ｎ，Ｊ，Ｋ，Ｓは変形例１と同じメモリ領域に記憶されているものとする。ただし、第二の状態Ｋの初期値をＫ０（Ｋ０は整数値。ランダムあるいは意図した値として設定される）とするとき、第一の状態の初期値Ｊ０をＫ０に更新関数をＭ回（Ｍは０より大きい整数値）施したＪ０＝Ｆ（Ｆ（・・・（Ｆ（Ｋ０，Ｓ），Ｓ）・・・），Ｓ）＝Ｋ０＋Ｍ＊Ｓにより定める。
【０１０７】
認証判定部４０２は、認証用のデータ（利用者を識別する情報）に基づいて認証の要求者が正規の利用者であるかを判定する。また、判定結果を入出力部４０１に出力する。
【０１０８】
そして、認証に不合格の場合には、第一の状態更新部４０５に第一の状態の更新を指示して、更に入出力部４０１に認証不合格の情報を出力する。
【０１０９】
また、認証に合格の場合には、第二の状態更新部４０６に第二の状態の更新を指示し、またパスワードｐａｓｓを出力する。更に入出力部４０１に認証合格の情報を出力する。
【０１１０】
第二の状態更新部４０６は、第二の状態の更新の指示を受け付ける。また、第一の状態記憶部４０３から第一の状態Ｊを受け付け、認証判定部４０２からパスワードｐａｓｓを受け付け、パラメータ記憶部４０９から更新回数Ｍを受け付ける。そして、Ｊ、ｐａｓｓ、Ｍと、第二の状態更新部４０６に記憶されている更新情報生成関数Ｇに基づいてＪ−Ｍ＊Ｇ（ｐａｓｓ）を計算する。なお、更新情報生成関数Ｇは、パラメータ記憶部４０９に記憶しておき、読み出して上記計算に用いてもよい。
【０１１１】
状態判定部４０７は、第一の状態記憶部４０３から第一の状態Ｊを読み出し、第二の状態記憶部４０４から第二の状態Ｋを読み出し、パラメータ記憶部４０９から更新回数Ｍ、更新上限Ｎ、更新情報Ｓを読み出し、読み出したＪ、Ｋ、Ｍ、Ｓに基づいてＪ−ＫがＭ＊Ｓ以上（Ｎ＋Ｍ）＊Ｓ未満のＳの倍数であることを検査する。検査に合格するときには制御部４０８に合格を伝え、不合格の場合には制御部４０８に不合格を伝える。
【０１１２】
そして、第二の状態記憶部４０４に記憶される第二の状態ＫをＪ−Ｍ＊Ｇ（ｐａｓｓ）に更新する。
【０１１３】
変形例３における認証処理４００の動作を以下に説明する。
【０１１４】
入出力部４０１は外部の装置から認証要求を受け付けたら（認証処理の開始）、状態判定部４０７に状態の判定を要求する。
【０１１５】
状態判定部４０７は、第一の状態記憶部４０３から第一の状態Ｊを読み出し、第二の状態記憶部４０４から第二の状態Ｋを読み出し、パラメータ記憶部４０９から更新回数Ｍ、更新上限Ｎ、更新情報Ｓを読み出し、読み出したＪ、Ｋ、Ｍ、Ｓに基づいてＪ−ＫがＭ＊Ｓ以上（Ｎ＋Ｍ）＊Ｓ未満のＳの倍数であることを検査する。検査に合格するときには制御部４０８に合格を伝え、不合格の場合には制御部４０８に不合格を伝える。
【０１１６】
状態判定部４０７の出力に対する制御部４０８の動作は変形例１と同様であるため説明は省略する。
【０１１７】
認証判定部４０２の動作は変形例１と同様であるため説明は省略する。
【０１１８】
第二の状態更新部４０６は第二の状態の更新の指示を受けたら、第一の状態記憶部４０３から第一の状態Ｊを読み出し、認証判定部４０２からパスワードｐａｓｓを入手し、パラメータ記憶部４０９からＭを読み出してＪ−Ｍ＊Ｇ（ｐａｓｓ）を計算する。そして、第二の状態記憶部４０４に記憶される第二の状態ＫをＪ−Ｍ＊Ｇ（ｐａｓｓ）に更新する。
【０１１９】
第一の状態更新部４０５の動作は本発明の変形例１と同様であるため説明は省略する。
【０１２０】
認証判定部４０２の出力に対する制御部４０８の動作は変形例１と同様であるため説明は省略する。
【０１２１】
このように、変形例３では、更新情報Ｓを認証に用いるデータに基づいて計算される値とし、第二の状態更新部４０６は更新情報Ｓを状態記憶部４０９から入手するのではなく、認証判定部４０２で処理されるデータに基づいて再計算して第二の状態を更新する。これにより、攻撃者が第二の状態更新部４０６を直接実行できたとしても、正しい認証情報を入力しなければ次回の認証処理で状態判定部４０７において合格と判定されるように第二の状態を更新することは困難となる。
【０１２２】
（変形例４）
基本構成では、物理的な解析により第一の状態と第二の状態を同一の状態に書き換えることができれば認証の試行を何度も繰り返すことが可能であった。
【０１２３】
変形例１から３では、認証成功時の第一の状態および第二の状態に差分を設けることにより、第一の状態と第二の状態を同一の状態に書き換えたとしても所定の回数以上に認証を試行することを困難としていた。
【０１２４】
変形例４では、第二の状態に健全性（第二の情報が不正に書き換えられていないこと）を確認するための情報を付加する。
【０１２５】
図５は変形例４に係る認証装置の構成を示すブロック図である。装置構成は基本構成とほぼ同一であるが、パラメータ記憶部５０９から第二の状態更新部５０６へのデータパスが増え、第二の状態記憶部５０４、第二の状態更新部５０６、状態判定部５０７が異なる。
【０１２６】
ここで、認証の連続失敗回数の上限Ｎ、更新情報Ｓ、第一の状態Ｊ、第二の状態Ｋ、更新関数Ｆ（Ｆ（ｘ，Ｓ）をｘ＋Ｓで定める）は基本構成と同じ意味で用い、基本構成と同じメモリ領域に記憶されているものとする。付加情報計算データＴはパラメータ記憶部５０９の領域ＩＶに記憶されているものとする。Ｈを入力ｘ、Ｔに対してＨ（ｘ，Ｔ）＝ｘ＋Ｔを出力する付加情報計算関数とし、パラメータ記憶部５０９の領域ＩＩに記憶されているものとする。
【０１２７】
ただし、第一の状態Ｊの初期値をＪ０とするとき、第二の状態の初期値を（Ｋ０，Ｈ０’）＝（Ｊ０，Ｈ（Ｊ０，Ｔ））により定める。
【０１２８】
第二の状態記憶部５０４は、第二の状態（Ｋ，Ｈ’）を記憶する。
【０１２９】
第二の状態更新部５０６は、第二の状態の更新の指示を受け付けると、第一の状態記憶部５０３から第一の状態Ｊを読み出し、さらに、パラメータ記憶部５０９から更新情報Ｓと付加情報計算データＴと付加情報計算関数Ｈを読み出す。そして、第二の状態記憶部５０４に記憶される第二の状態（Ｋ、Ｈ’）を（Ｊ、Ｈ（Ｊ，Ｔ））に更新する。
【０１３０】
状態判定部５０７は、第一の状態記憶部５０３から第一の状態Ｊを抽出し、第二の状態記憶部５０４から第二の状態（Ｋ，Ｈ’）を読み出し、パラメータ記憶部５０９から更新上限Ｎ、更新情報Ｓ、付加情報計算データＴ、付加情報計算関数Ｈを読み出す。そして、Ｊ−Ｋが０以上Ｎ＊Ｓ未満のＳの倍数であること、Ｈ’＝Ｈ（Ｋ，Ｔ）がなりたつことを検査する。すべての検査に合格するときには制御部５０８に合格を伝え、いずれか一つでも不合格の場合には制御部５０８に不合格を伝える。
【０１３１】
次に、変形例４の認証装置５００の動作について説明する。
【０１３２】
入出力部５０１は外部の装置から認証要求を受け付けたら（認証処理の開始）、状態判定部５０７に状態の判定を要求する。
【０１３３】
状態判定部５０７は、第一の状態記憶部５０３から第一の状態Ｊを抽出し、第二の状態記憶部５０４から第二の状態（Ｋ，Ｈ’）を抽出し、パラメータ記憶部５０９から更新上限Ｎ、更新情報Ｓ、付加情報計算データＴ、付加情報計算関数Ｈを抽出する。そして、Ｊ−Ｋが０以上Ｎ＊Ｓ未満のＳの倍数であること、Ｈ’＝Ｈ（Ｋ，Ｔ）がなりたつことを検査する。すべての検査に合格するときには制御部５０８に合格を伝え、いずれか一つでも不合格の場合には制御部５０８に不合格を伝える。
【０１３４】
状態判定部５０７の出力に対する制御部５０８の動作は基本構成と同様であるため説明は省略する。
【０１３５】
認証判定部５０２の動作は基本構成と同様であるため説明は省略する。
【０１３６】
第二の状態更新部５０６は第二の状態の更新の指示を受けたら、第一の状態記憶部５０３から第一の状態Ｊを読み出し、パラメータ記憶部から付加情報計算データＴ、付加情報計算関数Ｈを読み出し、第二の状態記憶部５０４に記憶される第二の状態（Ｋ，Ｈ（Ｋ，Ｔ））を（Ｊ，Ｈ（Ｊ，Ｔ））に更新する。
【０１３７】
第一の状態更新部５０５の動作は本発明の基本構成と同様であるため説明は省略する。
【０１３８】
認証判定部５０２の出力に対する制御部５０８の動作は基本構成と同様であるため説明は省略する。
【０１３９】
ここで、変形例４の動作原理は基本構成の動作原理と以下の点を除いて同様である。変形例４では、第二の状態が健全であることを検証するためにＫとＨ（Ｋ，Ｔ）を組にして記憶している。正しく動作している場合には（不正な書き換えが行われていない場合には）Ｈ’＝Ｈ（Ｋ，Ｔ）がなりたつ。
【０１４０】
また、第一および第二の状態は領域ＩＩＩに記憶されているため、攻撃者はＪと（Ｋ，Ｈ（Ｋ，Ｔ））を読み出すことはできない。一方、更新情報Ｓと付加情報計算データＴは領域ＩＶに記憶されているため、攻撃者はＳとＴを読み出すことも書き換えることもできない。
【０１４１】
攻撃者はＳを読み出すことができないため、第一の状態ＪをＪ’−Ｋが０以上Ｍ＊Ｓ未満のＳの倍数となるようなＪ’に書き換えることは困難である。
【０１４２】
同様に、攻撃者はＳとＴを読み出すことができないため、第二の状態（Ｋ，Ｈ’）をＪ−Ｋ’が０以上Ｍ＊Ｓ未満のＳの倍数となるようなＫ’とＨ（Ｋ’，Ｔ）に書き換えることは困難である。
【０１４３】
一方、第一の状態Ｊと第二の状態（Ｋ，Ｈ’）を同時に書き換える攻撃では、付加情報計算データＴを読み出すことができないため、第一の状態と第二の状態をＪ’と（Ｊ’，Ｈ（Ｊ’，Ｔ））に書き換えることは困難である。他方、攻撃者はＳとＴを読み出すことができないため、第一の状態Ｊと第二の状態ＫをＫ’−Ｊ’が０以上Ｎ＊Ｓ未満のＳの倍数となるようなＪ’と（Ｋ’，Ｈ（Ｋ’，Ｔ））に書き換えることは困難である。
【０１４４】
（変形例５）
変形例３では、第二の状態更新で用いる更新情報Ｓを、入手したパスワードｐａｓｓを更新情報生成関数Ｇで復元することで、攻撃者が第二の状態更新を直接実施する攻撃を防いでいた。
【０１４５】
変形例５では、更新情報としてｐａｓｓに関するデジタル署名Ｓを利用する。第二の状態更新では、入手したｐａｓｓとＳの検証処理を行い、検証処理に合格する場合には第二の状態を更新し、検証処理に不合格の場合にはデバイスをロックする。デジタル署名が偽造困難であるとき、正しいｐａｓｓを知らない攻撃者が第二の状態更新を直接実行することは困難となる。
【０１４６】
変形例５により、製造コストの高い領域ＩＶを使用せずに、認証装置を構成することが可能となる。
【０１４７】
以下ではパスワードｐａｓｓを用いる装置を例に変形例５に係る認証装置とその動作手順を開示する。
【０１４８】
図１０は変形例５に係る認証装置の構成を示すブロック図である。
【０１４９】
認証の連続失敗回数の上限Ｎ、第一の状態Ｊ、第二の状態Ｋ、更新回数Ｍを変形例３と同じ意味で用いる。
【０１５０】
また、偽造困難なデジタル署名方式の署名生成関数をＳｉｇｎであらわし、署名検証関数をＶｅｒであらわす。署名生成に用いる署名鍵をｓｉｇｋであらわし、検証処理で用いる検証鍵をｖｅｒｋであらわす。
【０１５１】
利用者のパスワードをｐａｓｓであらわし、更新情報（署名）ＳをＳｉｇｎにｓｉｇｋとｐａｓｓを入力してＳ＝Ｓｉｇｎ（ｓｉｇｋ，ｐａｓｓ）で定める。ここで、パラメータ記憶部１００９に記憶されるＳは予め、上述の式で求めておき、記憶しておく。更新関数Ｆ（Ｆ（ｘ，Ｓ）をｘ＋Ｓで定める）は基本構成と同じ意味で用いる。
【０１５２】
各データは以下の領域に記憶される。第一の状態記憶部１００３は領域ＩＩＩであり、第一の状態Ｊを記憶する。第二の状態記憶部１００４は領域ＩＩＩであり、第二の状態Ｋを記憶する。パラメータ記憶部１００９は領域ＩＩと領域ＩＩＩで構成される。領域ＩＩには、上限Ｎ、更新回数Ｍ、更新関数Ｆ、検証鍵ｖｅｒｋを記憶する。署名生成関数Ｓｉｇｎ、署名検証関数Ｖｅｒがパラメータ記憶部１００９に記憶されるときには、領域ＩＩに記憶される。領域ＩＩＩには、署名鍵ｓｉｇｋ、更新情報Ｓを記憶する。
【０１５３】
認証判定部１００２は、認証用のデータ（利用者を識別する情報）に基づいて認証の要求者が正規の利用者であるかを判定する。また、判定結果を入出力部１００１に出力する。
【０１５４】
そして、認証に不合格の場合には、第一の状態更新部１００５に第一の状態の更新を指示して、更に入出力部１００１に認証不合格の情報を出力する。
【０１５５】
また、認証に合格の場合には、第二の状態更新部１００６に第二の状態の更新を指示し、またパスワードｐａｓｓを伝える。更に入出力部１００１に認証合格の情報を出力する。
【０１５６】
第二の状態更新部１００６は、第二の状態の更新の指示を受け付ける。また、第一の状態記憶部１００３から第一の状態Ｊを受け付け、認証判定部１００２からパスワードｐａｓｓを受け付け、パラメータ記憶部１００９から更新回数Ｍと更新情報Ｓと署名鍵ｓｉｇｋおよび検証鍵ｖｅｒｋを受け付ける。
【０１５７】
そして、第二の状態更新部１００６に記憶されている署名検証関数Ｖｅｒを用いて署名検証処理Ｖｅｒ（ｖｅｒｋ，ｐａｓｓ，Ｓ）を実行する。検証処理に不合格となる場合には、制御部１００８に不合格を伝える。検証処理に合格する場合には、Ｊ、Ｍと、第二の状態更新部１００６に記憶されているＳに基づいてＪ−Ｍ＊Ｓを計算する。なお、Ｊ、ｐａｓｓ、Ｍ、ｓｉｇｋと、第二の状態更新部１００６に記憶されている署名生成関数Ｓｉｇｎに基づいてＪ−Ｍ＊Ｓｉｇｎ（ｓｉｇｋ，ｐａｓｓ）を計算して求めても良い。
【０１５８】
状態判定部１００７は、第一の状態記憶部１００３から第一の状態Ｊを読み出し、第二の状態記憶部１００４から第二の状態Ｋを読み出し、パラメータ記憶部１００９から更新回数Ｍ、更新上限Ｎ、更新情報Ｓを読み出し、読み出したＪ、Ｋ、Ｍ、Ｓに基づいてＪ−ＫがＭ＊Ｓ以上（Ｎ＋Ｍ）＊Ｓ未満のＳの倍数であることを検査する。検査に合格するときには制御部１００８に合格を伝え、不合格の場合には制御部１００８に不合格を伝える。
【０１５９】
第二の状態更新部では、第二の状態記憶部１００４に記憶される第二の状態ＫをＪ−Ｍ＊Ｓｉｇｎ（ｓｉｇｋ，ｐａｓｓ）に更新する。
【０１６０】
変形例５における認証処理１０００の動作を以下に説明する。
【０１６１】
入出力部１００１は外部の装置から認証要求を受け付けたら（認証処理の開始）、状態判定部１００７に状態の判定を要求する。
【０１６２】
状態判定部１００７は、第一の状態記憶部１００３から第一の状態Ｊを読み出し、第二の状態記憶部１００４から第二の状態Ｋを読み出し、パラメータ記憶部１００９から更新回数Ｍ、更新上限Ｎ、更新情報Ｓ、署名鍵ｓｉｇｋ、検証鍵ｖｅｒｋを読み出す。そして、状態判定部１００７は内部で乱数Ｒを発生し、状態判定部に記憶されている署名生成関数Ｓｉｇｎと署名検証関数Ｖｅｒを用いて、Ｖｅｒ（ｖｅｒｋ，Ｒ，Ｓｉｇｎ（ｓｉｇｋ，Ｒ））を検証する。検証に不合格となるときには制御部１００８に不合格を伝える。検証に合格するときには、Ｊ−ＫがＭ＊Ｓ以上（Ｎ＋Ｍ）＊Ｓ未満のＳの倍数であることを検査する。検査に合格するときには制御部１００８に合格を伝え、不合格の場合には制御部１００８に不合格を伝える。なお、署名生成関数Ｓｉｇｎや署名検証関数Ｖｅｒは、パラメータ記憶部１００９に記憶しておき、読み出して上記計算に用いてもよい。
【０１６３】
状態判定部１００７の出力に対する制御部１００８の動作は変形例３と同様であるため説明は省略する。
【０１６４】
認証処理の実行が指示されるとき、認証判定部１００２はパスワードや生体情報など認証要求者を識別する情報に基づいて認証処理を実行する。具体的には、入出力部１００１からｐａｓｓを受け付け、パラメータ記憶部１００９からｖｅｒｋ、Ｓを読み出す。そして、認証判定部１００２は、内部に記憶するＶｅｒを用いて、Ｖｅｒ（ｖｅｒｋ、ｐａｓｓ、Ｓ）が受理されるか検査する。検査に合格する場合には第二の状態更新部１００６に第二の状態の更新を指示して入出力部１００１に認証合格を伝え、検査に不合格の場合には第一の状態更新部１００５に第一の状態の更新を指示して入出力部１００１に認証不合格を伝える。署名検証関数Ｖｅｒは、パラメータ記憶部１００９に記憶しておき、読み出して上記計算に用いてもよい。
【０１６５】
第二の状態更新部１００６は第二の状態の更新の指示を受けたら、第一の状態記憶部１００３から第一の状態Ｊを読み出し、認証判定部１００２からパスワードｐａｓｓを入手し、パラメータ記憶部１００９からＭ、Ｓ、ｓｉｇｋ、ｖｅｒｋを読み出す。そして、第二の状態更新部内部で乱数Ｒを発生して、第二の状態更新部に記憶されている署名検証関数Ｖｅｒと署名生成関数Ｓｉｇｎを用いて、Ｖｅｒ（ｖｅｒｋ，Ｒ，Ｓｉｇｎ（ｓｉｇｋ，Ｒ））を検証する。検証に不合格となるときには制御部１００８に不合格を伝える。検証に合格するときには、さらに、Ｖｅｒ（ｖｅｒｋ，ｐａｓｓ，Ｓ）を検証する。検証に不合格となるときは、制御部１００８に不合格を伝える。検証に合格するときには、Ｊ−Ｍ＊Ｓを計算する。そして、第二の状態記憶部１００４に記憶される第二の状態ＫをＪ−Ｍ＊Ｓに更新する。なお、ＳはＳｉｇｎ（ｓｉｇｋ，ｐａｓｓ）を計算することにより、都度計算されても良い。これにより更に安全性を高めることができる。
【０１６６】
第二の状態更新部１００６の出力に対して、制御部１００８は、認証不合格を受け付けた場合には利用者から認証装置１０００の利用要求を拒絶する（認証処理の終了）。
【０１６７】
第一の状態更新部１００５の動作は本発明の変形例３と同様であるため説明は省略する。
【０１６８】
認証判定部１００２の出力に対する制御部１００８の動作は変形例３と同様であるため説明は省略する。
【０１６９】
このように、変形例５では、更新情報Ｓを認証に用いるデータに基づいて計算される値（Ｓ＝Ｓｉｇｎ（ｓｉｇｋ、ｐａｓｓ））とし、第二の状態更新部１００６は更新情報Ｓを状態記憶部１００９から入手するのではなく、認証判定部１００２で処理されるデータに基づいて再計算して第二の状態を更新する。これにより、攻撃者が第二の状態更新部１００６を直接実行できたとしても、正しい認証情報を入力しなければ次回の認証処理で状態判定部１００７において合格と判定されるように第二の状態を更新することは困難となる。
【０１７０】
なお、状態判定部１００７と第二の状態更新部１００６で、乱数Ｒを用いたチャレンジ−レスポンス方式によりｓｉｇｋが改ざんされていないことを検証する箇所は、Ｕ＝Ｓｉｇｎ（ｓｉｇｋ，ｓｉｇｋ）をあらかじめ計算してパラメータ記憶部１００９の領域ＩＩＩに記憶しておき、Ｖｅｒ（ｖｅｒｋ，ｓｉｇｋ，Ｕ）が受理されることで確認してもよい。
【０１７１】
（変形例６）
変形例４では、状態を更新するために用いるデータＳ、および、第二の状態の正当性を保証するためのデータＴを利用した。変形例４における認証装置を安全に構成するために、ＳとＴはパラメータ記憶部５０９の領域ＩＶに記憶されていた。
【０１７２】
変形例５では、Ｓをパスワードｐａｓｓの署名としてＳｉｇｎ（ｓｉｇｋ，ｐａｓｓ）で定め、パラメータ記憶部１００９の領域ＩＩＩに記憶した。
【０１７３】
変形例６では、変形例５と同様に、更新情報Ｓをｐａｓｓの署名Ｓｉｇｎ（ｓｉｇｋ，ｐａｓｓ）で定める。また、Ｔの署名をＶ＝Ｓｉｇｎ（ｓｉｇｋ、Ｔ）で定める。このとき、変形例５と同様に、パラメータ記憶部の領域ＩＩにＳｉｇ、Ｖｅｒ、ｖｅｒｋを記憶し、領域ＩＩＩにｓｋ、Ｓ、Ｔ、Ｖを記憶する。
【０１７４】
変形例６では、変形例５と同様に、Ｓの正当性を検証Ｖｅｒ（ｖｅｒｋ、ｐａｓｓ、Ｓ）で行う。さらに、変形例６では、変形例４におけるＴを用いた処理を実行する前に、Ｖｅｒ（ｖｅｒｋ、Ｔ、Ｖ）の検証を行い、検証に合格するときは以降の処理を実行し、検証に不合格となるときには制御部に不合格を伝えて認証処理の停止を指示し、デバイスの利用要求を拒絶する（認証処理の終了）。
【０１７５】
その他の処理は変形例４と同様であるため説明は省略する。
【０１７６】
（第二の実施形態）
第一実施形態では更新関数Ｆとして更新情報Ｓを加算する認証装置の構成を述べた。第二実施形態では更新関数として一方向性関数を用いる装置の構成例を述べる。
【０１７７】
（基本構成）
本発明により開示される基本構成では物理的な解析に対する耐性は不十分ではあるが、物理的な解析に対して耐性をもつ変形例を説明する上で基本となる認証装置とその動作について説明する。
【０１７８】
図６は、第2の実施形態の基本構成に係る認証装置の構成を示すブロック図である。構成は、第1の実施形態の基本構成とほぼ同一であるが、第一の状態更新部６０５、状態判定部６０７が異なる。
【０１７９】
ここで、状態判定部６０７が許容する認証の連続失敗回数の上限Ｎ、パラメータ記憶部６０９に記憶される更新情報Ｓ、第一の状態Ｊ（Ｊは整数値、初期値を整数値Ｊ０とする。Ｊ０はランダムあるいは意図した値として設定される）、第二の状態Ｋ（Ｋは整数値、初期値はＪの初期値Ｊ０を用いる）は第一実施形態と同様のメモリ領域に保存されるものとする。
【０１８０】
第一の状態更新部６０５では、更新関数Ｆに基づいて第一の状態を更新する。以下の説明では、更新関数Ｆはｘを入力としてＦ（ｘ，Ｓ）＝ｆ（ｘ‖Ｓ）により計算するものとし（‖はデータの連接を表す）、パラメータ記憶部６０９に記憶されているものとする。ただし、ｆは入力ｘからｆ（ｘ）を計算することができるが、出力ｙが与えられたときにｙ＝ｆ（ｘ）となる入力ｘを計算することが事実上困難な一方向性関数である。一方向性関数には、ＳＨＡ（Ｓｅｃｕｒｅ Ｈａｓｈ Ａｌｇｏｒｉｔｈｍ）に代表されるハッシュ関数やＲＳＡ暗号（Ｒｉｖｅｓｔ-Ｓｈａｍｉｒ-Ａｄｌｅｍａｎ暗号）に代表される暗号化関数などが用いられる。以下、第2の実施形態で、ｆと記載した場合は、上述の関数を意味する。
【０１８１】
状態更新部６０５は、第一の状態の更新の指示を受けたら、パラメータ記憶部６０９から更新情報Ｓと更新関数Ｆを入手し、第一の状態記憶部６０３に記憶される第一の状態ＪをＦ（Ｊ，Ｓ）＝ｆ（Ｊ‖Ｓ）に更新する。ここで、状態判定部６０７は、第一の状態記憶部６０３から第一の状態Ｊを読み出し、第二の状態記憶部６０４から第二の状態Ｋを読み出し、パラメータ記憶部６０９から更新上限Ｎと更新関数Ｆを読み出す。そして、読み出したＪ、Ｋ、Ｎに基づいて、Ｋ、Ｆ（Ｋ，Ｓ）、Ｆ（Ｆ（Ｋ，Ｓ），Ｓ）、...、ＦＮ−１（Ｋ，Ｓ）のいずれか（ただしＦＬ（ｘ，Ｓ）はｘとＳにＦをＬ回連鎖的に作用させることをあらわす）がＪに一致するか否かを検査する。検査に合格するときには制御部６０８に合格を伝え、不合格の場合には制御部６０８に不合格を伝える。
【０１８２】
第2の実施形態の基本構成における認証装置の動作を以下に説明する。
【０１８３】
認証装置６００は、入出力部６０１より認証要求を受け付けたら（認証処理の開始）、状態判定部６０７に状態の判定を要求する。
【０１８４】
状態判定部６０７は、第一の状態記憶部６０３から第一の状態Ｊを読み出し、第二の状態記憶部６０４から第二の状態Ｋを読み出し、パラメータ記憶部６０９から更新上限Ｎと更新関数Ｆを読み出す。そして、読み出したＪ、Ｋ、Ｎに基づいて、Ｋ、Ｆ（Ｋ，Ｓ）、Ｆ（Ｆ（Ｋ，Ｓ），Ｓ）、...、ＦＮ−１（Ｋ，Ｓ）のいずれか（ただしＦＬ（ｘ，Ｓ）はｘとＳにＦをＬ回連鎖的に作用させることをあらわす）がＪに一致するか否かを検査する。検査に合格するときには制御部６０８に合格を伝え、不合格の場合には制御部６０８に不合格を伝える。
【０１８５】
制御部６０８は、状態判定部６０７から合格を受け取る場合には認証判定部６０２に認証処理の実行を指示する。一方、状態判定部６０７から不合格を受け取る場合には認証判定部６０２に認証処理の停止を指示して認証装置６００の利用要求を拒絶する（認証処理の終了）。
【０１８６】
認証判定部６０２は、認証処理の実行が指示されるとき、パスワードや生体情報など認証要求者を識別する情報（認証用のデータ）に基づいて認証処理を実行する。認証に合格する場合には第二の状態更新部６０６に第二の状態の更新を指示して入出力部６０１に認証合格を伝え、認証に不合格の場合には第一の状態更新部６０５に第一の状態の更新を指示して入出力部６０１に認証不合格を伝える。
【０１８７】
第二の状態更新部６０６は第二の状態の更新の指示を受けたら、第一の状態記憶部６０３から第一の状態Ｊを入手し、第二の状態記憶部６０４に記憶される第二の状態ＫをＪに更新する。
【０１８８】
第一の状態更新部６０５は第一の状態の更新の指示を受けたら、パラメータ記憶部６０９から更新情報Ｓを入手し、第一の状態記憶部６０３に記憶される第一の状態ＪをＦ（Ｊ，Ｓ）＝ｆ（Ｊ‖Ｓ）に更新する。
【０１８９】
入出力部６０１は、認証結果を受け付けると外部の装置に出力し、外部の装置は自己の利用を許可または拒絶をしたりする。例えば、認証結果を受けた外部の装置がキャッシュディスペンサー自体のサービスを許可または拒絶する制御を行うことにより、利用者はサービスを受けたり、受けることができなかったりする。
【０１９０】
入出力部６０１は、認証結果を受け付けると外部の装置に出力し、外部の装置は自己の利用を許可または拒絶をしたりする。例えば、認証結果を受けた外部の装置がキャッシュディスペンサー自体のサービスを許可または拒絶する制御を行うことにより、利用者はサービスを受けたり、受けることができなかったりする。
【０１９１】
ここで、正しく（物理的な解析によるデータの書き換えなどが行なわれることなく）認証処理が行われている場合に、利用者が認証の要求にＬ回連続（Ｌ＝０，１，．．．，Ｎ−１）して失敗するとき、第一の状態Ｊと第二の状態Ｋの間にはＪ＝ＦＬ（Ｋ，Ｓ）の関係がなりたつ。一方、Ｌ＝Ｎ回連続して失敗してしまうと、Ｊ＝ＦＮ（Ｋ，Ｓ）となる。すなわち、正しく認証処理が行われるとき、認証の連続失敗回数がＮ回未満であることはＪ＝ＦＬ（Ｋ，Ｓ）となるＬが０以上Ｎ未満であるときに限られる。
【０１９２】
また、第一および第二の状態は領域ＩＩＩに記憶されているため、攻撃者はＪとＫを読み出すことはできない。一方、更新情報Ｓは領域ＩＶに記憶されているため、攻撃者はＳを読み出すことも書き換えることもできない。
【０１９３】
攻撃者はＳを読み出すことができないため、第一の状態ＪをＪ’＝ＦＬ（Ｋ，Ｓ）をみたす０以上Ｎ未満のＬが存在するようなＪ’に書き換えることは困難である。
【０１９４】
同様に、攻撃者はＳを読み出すことができないため、第二の状態ＫをＪ＝ＦＬ（Ｋ’）をみたす０以上Ｎ未満のＬが存在するようなＫ’に書き換えることは困難である。
【０１９５】
一方、第一の状態Ｊと第二の状態ＫをともにＪ’とＪ’に書き換えることができれば、状態判定部１０７の検査に合格するため認証の試行を何度も繰り返すことができる。このような解析は、第１の実施形態の変形例と同様に回避することが可能である。以下では第１の実施形態の変形例１、変形例３、変形例４に対応する装置のみを説明する。第１の実施形態の変形例２に対応する装置は、これらの装置と同様に第１の実施形態の変形例２から構成可能であるため、説明は省略する。
【０１９６】
（変形例１）
第２の実施形態の基本構成では、物理的な解析により第一の状態と第二の状態を同一の状態に書き換えることができれば認証の試行を何度も繰り返すことが可能であった。
【０１９７】
第２の実施形態の変形例１では、認証判定部が認証に合格したと判定するときに第二の状態と秘密情報に基づいて、第二の状態を第一の状態よりもＭステップ（Ｍは０より大きい整数値）初期状態（情報）に近い状態へと更新する。認証成功時の第一および第二の状態に差分を設けることにより、第一の状態と第二の状態を同一の状態に書き換えたとしても認証を試行することができない。
【０１９８】
図７は、第2の実施形態の変形例１に係る認証装置の構成を示すブロック図である。構成は、第２の実施形態の基本構成とほぼ同一であるが、パラメータ記憶部７０９から第二の状態更新部７０６へのデータパスが増え、第一の状態更新部７０５、状態判定部７０７が異なる。
【０１９９】
ここで、認証の連続失敗回数の上限Ｎ、更新情報Ｓ、第一の状態Ｊ、第二の状態Ｋ、更新関数Ｆ（Ｆ（ｘ，Ｓ）をｆ（ｘ‖Ｓ）、ただしｆは一方向性関数で定める）は基本構成と同じ意味で用い、基本構成と同じメモリ領域に記憶されているものとする（‖はデータの連接を表す）。ただし、第二の状態Ｋの初期値をＫ０（Ｋ０は整数値。ランダムあるいは意図した値として設定される）とするとき、第一の状態の初期値Ｊ０をＫ０に更新関数をＭ回（Ｍは０より大きい整数値）施したＪ０＝Ｆ（Ｆ（・・・（Ｆ（Ｋ０，Ｓ），Ｓ）・・・），Ｓ）＝ｆ（ｆ（・・・（ｆ（Ｋ０‖Ｓ）‖Ｓ）・・・）‖Ｓ）により定める。
【０２００】
第２の実施形態の変形例１における認証装置の動作を以下に説明する。
【０２０１】
認証装置７００は、入出力部７０１より認証要求を受け付けたら（認証処理の開始）、状態判定部７０７に状態の判定を要求する。
【０２０２】
状態判定部７０７は、第一の状態記憶部７０３から第一の状態Ｊを読み出し、第二の状態記憶部７０４から第二の状態Ｋを読み出し、パラメータ記憶部７０９から更新回数Ｍ、更新上限Ｎ、更新情報Ｓ、更新関数Ｆを入手し、入手したＪ、Ｋ、Ｍ、Ｎ、Ｓ、Ｆに基づいて、ＪがＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）のいずれかに一致するか否かを検査する。検査に合格するときには制御部７０８に合格を伝え、不合格の場合には制御部７０８に不合格を伝える。
【０２０３】
状態判定部７０７の出力に対する制御部７０８の動作は第二実施形態の基本構成と同様であるため説明は省略する。
【０２０４】
認証判定部７０２の動作は第二実施形態の基本構成と同様であるため説明は省略する。
【０２０５】
第二の状態更新部７０６は、第二の状態の更新の指示を受けたら、第一の状態記憶部７０３から第一の状態Ｊを読み出し、第二の状態記憶部７０４から第二の状態Ｋを入手し、パラメータ記憶部７０９から更新回数Ｍ、更新上限Ｎ、更新情報Ｓ、更新関数Ｆを読み出し、入手したＪ、Ｋ、Ｍ、Ｎ、Ｓ、Ｆに基づいて、ＪがＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）のいずれかに一致するか否かを求め、Ｊ＝ＦＬ（Ｋ，Ｓ）をみたすＬを求めた後、ＬがＭより大きい場合には第二の状態記憶部７０４に記憶される第二の状態ＫをＦＬ−Ｍ（Ｋ，Ｓ）に更新する。ここで、上記のようにＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）を計算した後に、Ｊと一致するかを求めても良いが、各ＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）を計算した時点で、Ｊと一致するか否かを求めて、一致した時点でＬを求めても良い。
【０２０６】
第一の状態更新部７０５の動作は第二実施形態の基本構成と同様であるため説明は省略する。
【０２０７】
認証判定部７０２の出力に対する入出力部７０１の動作は第二実施形態の基本構成と同様であるため説明は省略する。
【０２０８】
ここで、正しく（物理的な解析によるデータの書き換えなどが行なわれることなく）認証処理が行われている場合に、利用者が認証の要求にＬ回連続（Ｌ＝０，１，．．．，Ｎ−１）して失敗するとき、第一の状態Ｊは第二の状態Ｋの間にはＪ＝ＦＭ＋Ｌ（Ｋ，Ｓ）の関係がなりたつ。一方、Ｌ＝Ｎ回連続して失敗してしまうと、Ｊ＝ＦＭ＋Ｎ（Ｋ，Ｓ）となる。すなわち、正しく認証処理が行われるとき、認証の連続失敗回数がＮ回未満であることはＪがＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）のいずれかであるときに限られる。
【０２０９】
また、第一および第二の状態は領域ＩＩＩに記憶されているため、攻撃者はＪとＫを読み出すことはできない。一方、更新情報Ｓは領域ＩＶに記憶されているため、攻撃者はＳを読み出すことも書き換えることもできない。
【０２１０】
攻撃者はＳを読み出すことができないため、第一の状態ＪをＪ’がＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）のいずれかとなるようなＪ’に書き換えることは困難である。
【０２１１】
同様に、攻撃者はＳを読み出すことができないため、第二の状態ＫをＪがＦＭ（Ｋ’，Ｓ）、ＦＭ＋１（Ｋ’，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ’，Ｓ）のいずれかとなるようなＫ’に書き換えることは困難である。
【０２１２】
一方、第一の状態Ｊと第二の状態ＫをともにＪ’とＪ’に書き換えると、多くの場合に状態判定部７０７により不合格と判定されるため、悪意ある認証の試行を行うことはできない。他方、攻撃者はＳを読み出すことができないため、第一の状態Ｊと第二の状態ＫをＪ’がＦＭ（Ｋ’，Ｓ）、ＦＭ＋１（Ｋ’，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ’，Ｓ）のいずれかとなるようなＪ’とＫ’に書き換えることは困難である。
【０２１３】
（変形例２）
本変形例は、第１の実施形態の変形例３に対応するものである。
【０２１４】
図８は、第２の実施形態の変形例２に係る認証装置の構成を示すブロック図である。装置構成は第２の実施形態の変形例1とほぼ同一であるが、第二の状態更新部８０６が異なり、その構成のみ以下に説明する。
【０２１５】
第二の状態更新部８０６は、第二の状態の更新の指示を受け付ける。また、第一の状態記憶部８０３から第一の状態Ｊを読み出し、第二の状態記憶部８０４から第二の状態Ｋを読み出し、認証判定部８０２からパスワードｐａｓｓを受け付け、パラメータ記憶部４０９から更新回数Ｍ、上限回数Ｎを受け付ける。そして、受け付けたｐａｓｓとパラメータ記憶部７０９に記憶されている更新情報生成関数Ｇに基づいてＳ＝Ｇ（ｐａｓｓ）を計算する。そして、そのＳと、受け付けたＪ、Ｋ、Ｍ、Ｎとに基づいて、ＪがＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）のいずれかに一致するか否かを求め、Ｊ＝ＦＬ（Ｋ，Ｓ）をみたすＬを求めた後、第二の状態記憶部７０４に記憶される第二の状態ＫをＦＬ−Ｍ（Ｋ，Ｓ）に更新する。ここで、上記のようにＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）を計算した後に、Ｊと一致するかを求めても良いが、各ＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）を計算した時点で、Ｊと一致するか否かを求めて、一致した時点でＬを求めても良い。
【０２１６】
次に、本変形例の動作も、基本的には、第２の実施形態の変形例１と同じであるため、異なる点のみを以下に説明する。
【０２１７】
第二の状態更新部８０６は、認証判定部８０２から更新の指示を受け付けると、第一の状態記憶部８０３から第一の状態Ｊを読み出し、第二の状態記憶部８０４から第二の状態Ｋを読み出し、認証判定部８０２からパスワードｐａｓｓを受け付け、パラメータ記憶部８０９から更新回数Ｍ、上限回数Ｎ、更新情報生成関数Ｇを受け付ける。そして、受け付けたｐａｓｓに基づいてＳ＝Ｇ（ｐａｓｓ）を計算する。そして、そのＳと、受け付けたＪ、Ｋ、Ｍ、Ｎとに基づいて、ＪがＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）のいずれかに一致するか否かを求め、Ｊ＝ＦＬ（Ｋ，Ｓ）をみたすＬを求めた後、第二の状態記憶部８０４に記憶される第二の状態ＫをＦＬ−Ｍ（Ｋ，Ｓ）に更新する。なお、前述のように各ＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）を計算した時点で、Ｊと一致するか否かを求めて、一致した時点でＬを求めても良い。
【０２１８】
このように、第２の実施形態の変形例２では、更新情報Ｓを認証に用いるデータに基づいて計算される値とし、第二の状態更新部８０６は更新情報Ｓを状態記憶部８０９から入手するのではなく、認証判定部８０２で処理されるデータに基づいて再計算して第二の状態を更新する。これにより、攻撃者が第二の状態更新部８０６を直接実行できたとしても、正しい認証情報を入力しなければ次回の認証処理で状態判定部８０７において合格と判定されるように第二の状態を更新することは困難となる。
【０２１９】
（変形例３）
本変形例は、第１の実施形態の変形例４に対応するものである。
【０２２０】
図９は、第２の実施形態の変形例３に係る認証装置の構成を示すブロック図である。装置構成は第２の実施形態の基本構成とほぼ同一であるが、パラメータ記憶部９０９から第二の状態更新部９０６へのデータパスが増え、第二の状態記憶部９０４、第二の状態更新部９０６、状態判定部９０７が異なり、その構成のみ以下に説明する。
【０２２１】
まず、認証の連続失敗回数の上限Ｎ、更新情報Ｓ、第一の状態Ｊ、第二の状態Ｋ、更新関数Ｆは基本構成と同じ意味で用い、基本構成と同じメモリ領域に記憶されているものとする。付加情報計算データＴはパラメータ記憶部９０９の領域ＩＶに記憶されているものとする。Ｈを入力ｘ、Ｔに対して、ｘとＴとを連接してハッシュした値を出力する付加情報計算関数とし、パラメータ記憶部の領域ＩＩに記憶されているものとする。つまり、Ｈ’＝Ｈ（ｘ，Ｔ）＝ｆ（ｘ‖Ｔ）である。
【０２２２】
ただし、第一の状態Ｊの初期値をＪ０とするとき、第二の状態の初期値を（Ｋ０，Ｈ０’）＝（Ｊ０，Ｈ（Ｊ０，Ｔ））＝（Ｊ０，ｆ（Ｊ０‖Ｔ））により定める。
【０２２３】
第二の状態記憶部９０４は、第二の状態（Ｋ，Ｈ’）を記憶する。
【０２２４】
第二の状態更新部９０６は、第二の状態の更新の指示を受けると、第一の状態記憶部９０３から第一の状態Ｊを読み出し、さらに、パラメータ記憶部９０９から更新情報Ｓと付加情報計算関数Ｈと付加情報計算データＴを読み出す。そして、第二の状態記憶部９０４に記憶される第二の状態（Ｋ、Ｈ’）を（Ｊ、Ｈ（Ｊ，Ｔ））に更新する。
【０２２５】
状態判定部９０７は、入出力部９０１から状態の判定の要求を受け付けたら、第一の状態記憶部９０３から第一の状態Ｊを読み出し、第二の状態記憶部９０４から第二の状態（Ｋ，Ｈ’）を読み出し、パラメータ記憶部９０９から更新回数Ｍ、更新上限Ｎ、更新情報Ｓ、更新関数Ｆ、付加情報計算データＴ、付加情報計算関数Ｈを読み出す。そして、入手したＪ、（Ｋ，Ｈ’）、Ｍ、Ｎ、Ｓ、Ｆ、Ｔ、Ｈに基づいて、ＪがＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）のいずれかに一致するか否か、およびＨ’＝Ｈ（Ｋ，Ｔ）が成り立つことを検査する。検査に合格するときには制御部９０８に合格を伝え、不合格の場合には制御部９０８に不合格を伝える。
【０２２６】
ここで、第２の実施形態の変形例３の動作について説明するが、基本構成とほぼ同一であるため、異なる点のみ説明する。
【０２２７】
状態判定部は、入出力部９０１から状態の判定の要求を受け付けたら、第一の状態記憶部９０３から第一の状態Ｊを読み出し、第二の状態記憶部９０４から第二の状態（Ｋ，Ｈ’）を読み出し、パラメータ記憶部から更新回数Ｍ、更新上限Ｎ、更新情報Ｓ、更新関数Ｆ、付加情報計算データＴ、付加情報計算関数Ｈを読み出す。そして、入手したＪ、（Ｋ，Ｈ’）、Ｍ、Ｎ、Ｓ、Ｆ、Ｔ、Ｈに基づいて、ＪがＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）のいずれかに一致するか否か、およびＨ’＝Ｈ（Ｋ，Ｔ）が成り立つことを検査する。検査に合格するときには制御部９０８に合格を伝え、不合格の場合には制御部９０８に不合格を伝える。
【０２２８】
制御部９０８、認証判定部９０２の動作は、基本構成と同一であるため省略する。
【０２２９】
第二の状態更新部９０６は、第二の状態の更新の指示を受けると、第一の状態記憶部９０３から第一の状態Ｊを読み出し、さらに、パラメータ記憶部９０９から更新情報Ｓを読み出す。そして、第二の状態更新部９０６に記憶されている関数Ｈと付加情報計算データＴ抽出する。そして、第二の状態記憶部９０４に記憶される第二の状態（Ｋ、Ｈ’）を（Ｊ、Ｈ（Ｊ，Ｔ））に更新する。
【０２３０】
ここで、本変形例の動作原理は基本構成の動作原理と以下の点を除いて同様である。本変形例では、第二の状態が健全であることを検証するためにＫとＨ（Ｋ，Ｔ）を組にして記憶している。正しく動作している場合には（不正な書き換えが行われていない場合には）Ｈ’＝Ｈ（Ｋ，Ｔ）がなりたつ。
【０２３１】
また、第一および第二の状態は領域ＩＩＩに記憶されているため、攻撃者はＪと（Ｋ，Ｈ（Ｋ，Ｔ））を読み出すことはできない。一方、更新情報Ｓと付加情報計算データＴは領域ＩＶに記憶されているため、攻撃者はＳとＴを読み出すことも書き換えることもできない。
【０２３２】
攻撃者はＳを読み出すことができないため、第一の状態ＪをＪ’−Ｋが０以上Ｍ＊Ｓ未満のＳの倍数となるようなＪ’に書き換えることは困難である。
【０２３３】
同様に、攻撃者はＳとＴを読み出すことができないため、第二の状態（Ｋ，Ｈ’）をＪ−Ｋ’が０以上Ｍ＊Ｓ未満のＳの倍数となるようなＫ’とＨ（Ｋ’）に書き換えることは困難である。
【０２３４】
一方、第一の状態Ｊと第二の状態（Ｋ，Ｈ’）を同時に書き換える攻撃では、付加情報計算データＴを読み出すことができないため、第一の状態と第二の状態をＪ’と（Ｊ’，Ｈ（Ｊ’，Ｔ））に書き換えることは困難である。他方、攻撃者はＳとＴを読み出すことができないため、第一の状態Ｊと第二の状態ＫをＫ’−Ｊ’が０以上Ｎ＊Ｓ未満のＳの倍数となるようなＪ’と（Ｋ’，Ｈ（Ｋ’，Ｔ））に書き換えることは困難である。
【０２３５】
（変形例４）
本変形例は、第１の実施形態の変形例５に対応するものである。署名生成関数Ｓｉｇｎ、署名検証関数Ｖｅｒ、署名鍵ｓｉｇｋ、検証鍵ｖｅｒｋを第１の実施形態の変形例５と同じ意味で用い、対応する領域に記憶する。
【０２３６】
すなわち、変形例４では、更新情報としてｐａｓｓに関するデジタル署名Ｓ＝Ｓｉｇｎ（ｓｉｇｋ、ｐａｓｓ）を利用する。第二の状態更新では、入手したｐａｓｓとＳの検証処理を行い、検証処理に合格する場合には第二の状態を更新し、検証処理に不合格の場合にはデバイスをロックする。デジタル署名が偽造困難であるとき、正しいｐａｓｓを知らない攻撃者が第二の状態更新を直接実行することは困難となる。
【０２３７】
変形例４により、製造コストの高い領域ＩＶを使用せずに、認証装置を構成することが可能となる。
【０２３８】
以下ではパスワードｐａｓｓを用いる装置を例に変形例４に係る認証装置とその動作手順を開示する。
【０２３９】
認証の連続失敗回数の上限Ｎ、第一の状態Ｊ、第二の状態Ｋ、更新回数Ｍを変形例２と同じ意味で用いる。
【０２４０】
図１１は、第２の実施形態の変形例４に係る認証装置の構成を示すブロック図である。
【０２４１】
装置構成は第２の実施形態の変形例２とほぼ同一であるが、第二の状態更新部１１０６が異なり、その構成のみ以下に説明する。
【０２４２】
第二の状態更新部１１０６は、第二の状態の更新の指示を受け付ける。また、第一の状態記憶部１１０３から第一の状態Ｊを読み出し、第二の状態記憶部１１０４から第二の状態Ｋを読み出し、認証判定部１１０２からパスワードｐａｓｓを受け付け、パラメータ記憶部１１０９から更新回数Ｍ、上限回数Ｎ、更新情報Ｓ、署名鍵ｓｉｇｋ、検証鍵ｖｅｒｋを受け付ける。
【０２４３】
第二の状態更新部１１０６は、内部で乱数Ｒを生成し、第二の状態更新部１１０６に記憶されている署名生成関数Ｓｉｇｎと署名検証関数Ｖｅｒを用いて、Ｖｅｒ（ｖｅｒｋ，Ｒ，Ｓｉｇｎ（ｓｉｇｋ，Ｒ））を検証する。検証に不合格となるときには制御部１１０８に不合格を伝える。検証に合格するときには、さらにＶｅｒ（ｐａｓｓ，Ｓ）を検証する。検証に不合格となるときには、制御部１１０８に不合格を伝える。検証に合格するときには、ＪがＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）のいずれかに一致するか否かを求め、Ｊ＝ＦＬ（Ｋ，Ｓ）をみたすＬを求めた後、第二の状態記憶部１１０４に記憶される第二の状態ＫをＦＬ−Ｍ（Ｋ，Ｓ）に更新する。ここで、上記のようにＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）を計算した後に、Ｊと一致するかを求めても良いが、各ＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）を計算した時点で、Ｊと一致するか否かを求めて、一致した時点でＬを求めても良い。なお、ＳはＳｉｇｎ（ｓｉｇｋ，ｐａｓｓ）を計算することにより、都度計算されても良い。これにより更に安全性を高めることができる。
【０２４４】
各データは以下の領域に記憶される。第一の状態記憶部１１０３は領域ＩＩＩであり、第一の状態Ｊを記憶する。第二の状態記憶部１１０４は領域ＩＩＩであり、第二の状態Ｋを記憶する。パラメータ記憶部１１０９は領域ＩＩと領域ＩＩＩで構成される。領域ＩＩには、上限Ｎ、更新回数Ｍ、更新関数Ｆ、検証鍵ｖｅｒｋを記憶する。署名生成関数Ｓｉｇｎ、署名検証関数Ｖｅｒがパラメータ記憶部１１０９に記憶されるときには、領域ＩＩに記憶される。領域ＩＩＩには、署名鍵ｓｉｇｋ、更新情報Ｓ＝Ｓｉｇｎ（ｓｉｇｋ，ｐａｓｓ）を記憶する。
【０２４５】
変形例４における認証処理１１００の動作を以下に説明する。
【０２４６】
入出力部１１０１は外部の装置から認証要求を受け付けたら（認証処理の開始）、状態判定部１１０７に状態の判定を要求する。
【０２４７】
状態判定部１２０７は、第一の状態記憶部１１０３から第一の状態Ｊを読み出し、第二の状態記憶部１１０４から第二の状態Ｋを読み出し、パラメータ記憶部１１０９から更新回数Ｍ、更新上限Ｎ、更新情報Ｓ、署名鍵ｓｉｇｋ、検証鍵ｖｅｒｋを読み出す。そして、状態判定部１１０７は内部で乱数Ｒを発生し、状態判定部に記憶されている署名生成関数Ｓｉｇｎと署名検証関数Ｖｅｒを用いて、Ｖｅｒ（ｖｅｒｋ，Ｒ，Ｓｉｇｎ（ｓｉｇｋ，Ｒ））を検証する。検証に不合格となるときには制御部１１０８に不合格を伝える。検証に合格するときには、ＪがＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）のいずれかに一致するか否かを求め、Ｊ＝ＦＬ（Ｋ，Ｓ）をみたすＬを求めた後、第二の状態記憶部１１０４に記憶される第二の状態ＫをＦＬ−Ｍ（Ｋ，Ｓ）に更新する。ここで、上記のようにＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）を計算した後に、Ｊと一致するかを求めても良いが、各ＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）を計算した時点で、Ｊと一致するか否かを求めて、一致した時点でＬを求めても良い。そして、Ｌが０以上Ｎ未満であることを検査する。検査に合格するときには制御部１１０８に合格を伝え、不合格の場合には制御部１１０８に不合格を伝える。なお、署名生成関数Ｓｉｇｎや署名検証関数Ｖｅｒは、パラメータ記憶部１１０９に記憶しておき、読み出して上記計算に用いてもよい。
【０２４８】
状態判定部１１０７の出力に対する制御部１１０８の動作は第二の実施形態の変形例２と同様であるため説明は省略する。
【０２４９】
認証判定部１１０２の動作は第二の実施形態の変形例２と同様であるため説明は省略する。
【０２５０】
第二の状態更新部１１０６は第二の状態の更新の指示を受けたら、第一の状態記憶部１１０３から第一の状態Ｊを読み出し、認証判定部１１０２からパスワードｐａｓｓを入手し、パラメータ記憶部１１０９からＭ、Ｓ、ｓｉｇｋ、ｖｅｒｋを読み出す。そして、第二の状態更新部内部で乱数Ｒを発生して、第二の状態更新部に記憶されている署名検証関数Ｖｅｒと署名生成関数Ｓｉｇｎを用いて、Ｖｅｒ（ｖｅｒｋ，Ｒ，Ｓｉｇｎ（ｓｉｇｋ，Ｒ））を検証する。検証に不合格となるときには制御部１１０８に不合格を伝える。検証に合格するときには、さらに、Ｖｅｒ（ｖｅｒｋ，ｐａｓｓ，Ｓ）を検証する。検証に不合格となるときは、制御部１１０８に不合格を伝える。検証に合格するときには、ＪがＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）のいずれかに一致するか否かを求め、Ｊ＝ＦＬ（Ｋ，Ｓ）をみたすＬを求めた後、ＬがＭより大きい場合には第二の状態記憶部１１０４に記憶される第二の状態ＫをＦＬ−Ｍ（Ｋ，Ｓ）に更新する。ここで、上記のようにＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）を計算した後に、Ｊと一致するかを求めても良いが、各ＦＭ（Ｋ，Ｓ）、ＦＭ＋１（Ｋ，Ｓ）、...、ＦＮ＋Ｍ−１（Ｋ，Ｓ）を計算した時点で、Ｊと一致するか否かを求めて、一致した時点でＬを求めても良い。
【０２５１】
第二の状態更新部１１０６の出力に対して、制御部１１０８は、認証不合格を受け付けた場合には利用者から認証装置１１００の利用要求を拒絶する（認証処理の終了）。
【０２５２】
第一の状態更新部１１０５の動作は本発明の第二の実施形態の変形例２と同様であるため説明は省略する。
【０２５３】
認証判定部１１０２の出力に対する制御部１１０８の動作は本発明の第二の実施形態の変形例２と同様であるため説明は省略する。
【０２５４】
このように、変形例４では、更新情報Ｓを認証に用いるデータに基づいて計算される値とし、第二の状態更新部１１０６は更新情報Ｓを状態記憶部１１０９から入手するのではなく、認証判定部１１０２で処理されるデータに基づいて再計算して第二の状態を更新する。これにより、攻撃者が第二の状態更新部１１０６を直接実行できたとしても、正しい認証情報を入力しなければ次回の認証処理で状態判定部１１０７において合格と判定されるように第二の状態を更新することは困難となる。
【０２５５】
なお、状態判定部１１０７と第二の状態更新部１１０６で、乱数Ｒを用いたチャレンジ−レスポンス方式によりｓｉｇｋが改ざんされていないことを検証する箇所は、Ｕ＝Ｓｉｇｎ（ｓｉｇｋ，ｓｉｇｋ）をあらかじめ計算してパラメータ記憶部１１０９の領域ＩＩＩに記憶しておき、Ｖｅｒ（ｖｅｒｋ，ｓｉｇｋ，Ｕ）が受理されることで確認してもよい。
【０２５６】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０２５７】
【図１】本発明の第１の実施形態の基本構成を示すブロック図。
【図２】本発明の第１の実施形態の変形例１の構成を示すブロック図。
【図３】本発明の第１の実施形態の変形例２の構成を示すブロック図。
【図４】本発明の第１の実施形態の変形例３の構成を示すブロック図。
【図５】本発明の第１の実施形態の変形例４の構成を示すブロック図。
【図６】本発明の第２の実施形態の基本構成を示すブロック図。
【図７】本発明の第２の実施形態の変形例１の構成を示すブロック図。
【図８】本発明の第２の実施形態の変形例２の構成を示すブロック図。
【図９】本発明の第２の実施形態の変形例３の構成を示すブロック図。
【図１０】本発明の第１の実施形態の変形例５の構成を示すブロック図。
【図１１】本発明の第２の実施形態の変形例４の構成を示すブロック図。
【符号の説明】
【０２５８】
１００・・・認証装置
１０１・・・入出力部
１０２・・・認証判定部
１０３・・・第一の状態記憶部
１０４・・・第二の状態記憶部
１０５・・・第一の状態更新部
１０６・・・第二の状態更新部
１０７・・・状態判定部
１０８・・・制御部
１０９・・・パラメータ記憶部
【図１】
2009076034.tif 000003
【図２】
2009076034.tif 000004
【図３】
2009076034.tif 000005
【図４】
2009076034.tif 000006
【図５】
2009076034.tif 000007
【図６】
2009076034.tif 000008
【図７】
2009076034.tif 000009
【図８】
2009076034.tif 000010
【図９】
2009076034.tif 000011
【図１０】
2009076034.tif 000012
【図１１】
2009076034.tif 000013