JP2008532389A - 認証のための小型の公開鍵を用いたデジタル署名 - Google Patents

Abstract

【課題】認証のための小型の公開鍵を用いたデジタル署名を提供すること。
【解決手段】開示された実施形態は、共通の法Ｎを使用することについて合意した２つのエンティティ間の認証を可能にする。この認証は、擬似乱数列値を生成することと、法Ｎと前記擬似乱数列値とに基づいて公開鍵値を生成することと、前記公開鍵値に対応する私有鍵値を生成することと、検証者の公開鍵値を受信することと、前記法Ｎと前記私有鍵値と、検証者の公開鍵値とに基づいて共有秘密値を生成することと、前記共有秘密値を用いて認証署名値を計算することと、認証のために前記認証署名値を送信すること、とを含む。前記認証署名が受信されたときに、認証署名値を計算するために前記公開鍵値と前記共有値とが生成される。その後、前記２つの認証署名値が比較されて認証される。

Description

認証技術ではある形態のデジタル署名およびメッセージ認証コードが用いられる。デジタル署名およびメッセージ認証コードは公開鍵及び／または対称鍵を用いた暗号システムをもとにしている。この２つのシステムは異なる特性を有しており、ある状況においては一方のシステムがより好適し、他の状況においては他方のシステムがより好適する。

概して、公開鍵システムは鍵管理及び配布の観点において利点を有する。しかしながら、公開鍵システムはしばしば計算上困難であり、大型のデジタル署名を要する。したがって、公開鍵システムはパワフルなプロセッサを必要とし、コストの増大、装置の重量及び／またはサイズの増大とを引き起こす。また、公開鍵システムはさらなる処理時間を必要とし、遅延を引き起こし、より多くのエネルギを使い及び／またはバッテリを消費し、あるいはそれらの組み合わせを引き起こす。

その結果、最も小型の認証デバイスは、計算上の要求と小さな出力に対する要求とから、対称鍵を用いる暗号技術を使用することを余儀なくされてきた。しかしながら、携帯電話などのデバイスにおいてより有能なプロセッサの出現により、計算上の要求はもはや主要な要因ではなくなりつつある。その一方で、より小型のデジタル署名に対するニーズがいまだ存在する。

要約
一側面において、共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための手段を備えた方法及び装置は、入力値から擬似乱数列値を生成することと、前記法Ｎと前記擬似乱数列値とに基づいて第１の公開鍵値を生成することと、前記第１の公開鍵値に対応する第１の私有鍵値を生成することと、第２の公開鍵値を受信することと、前記法Ｎと、前記第１の私有鍵値と、前記第２の公開鍵値とに基づいて、共有秘密値を生成すること、とを具備する。これにより、前記共有秘密値を使用して認証署名値が計算されて送信される。

他の側面において、共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための装置は、入力値から擬似乱数列値を生成するように構成された擬似乱数生成器と、前記法Ｎと前記擬似乱数列値とに基づいて第１の公開鍵値を生成するとともに、前記第１の公開鍵値に対応する第１の私有鍵値を生成するように構成された鍵生成ユニットと、第２の公開鍵値を受信するように構成された受信器ユニットと、前記法Ｎと、前記第１の私有鍵値と、前記第２の公開鍵値とに基づいて、共有秘密値を生成するように構成された秘密値生成ユニットと、を具備する。

さらに、他の側面において、共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための手段を備えた方法及び装置は、第１の認証署名値を受信することと、入力値から擬似乱数列値を生成することと、前記法Ｎ及び前記擬似乱数列値とに基づいて第１の公開鍵値を生成することと、前記法Ｎと、私有鍵値と、前記第１の公開鍵とに基づいて共有秘密値を生成することと、前記共有秘密値を用いて第２の認証署名値を計算することと、前記第１の認証署名値と、前記第２の認証署名値とを比較することと、を具備する。

また、さらに他の側面において、共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための装置は、第１の認証署名値を受信するように構成された受信器ユニットと、入力値から擬似乱数列値を生成するように構成された擬似乱数生成器と、前記法Ｎ及び前記擬似乱数列値とに基づいて第１の公開鍵値を生成するように構成された鍵生成ユニットと、前記法Ｎと、私有鍵値と、前記第１の公開鍵とに基づいて共有秘密値を生成するように構成された共有秘密値生成ユニットと、前記共有秘密値を用いて第２の認証署名値を計算するように構成されたメッセージ認証コードユニットと、 前記第１の認証署名値と、前記第２の認証署名値とを比較するように構成された比較ユニットと、を具備する。

また、さらに他の側面において、共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための手段を備えた方法及び装置は、法Ｎに基づいて生成された公開鍵値を受信することと、Ｎを法とする離散対数問題を解決することによって、前記公開鍵値に対応する私有鍵を生成することと、前記私有鍵を共有秘密鍵として用いることと、を具備する。

上記方法はプロセッサによって実現及び／又は制御される。同様に、上記方法は機械読み取り可能な媒体に記憶された命令によって実現及び／又は実行される。

次の記述において、本実施形態の完全な理解を提供するために詳細な説明がされる。しかしながら、当業者ならば、これらの特別な詳細なしに本実施形態を実施することができることを理解するであろう。例えば、不必要な詳細を述べることで本実施形態を不明確にすることがないように回路はブロック図で示される。また、既知の回路、構造及び技術は本実施形態を不明確にしない程度に詳細に示される。

また、本実施形態はフローチャート、フロー図、構造図あるいはブロック図として示されるプロセスとして記載されことに注意されたい。フローチャートは動作を順次実行されるプロセスとして記載するが、多くの動作は並列的あるいは同時に実行されるものである。さらに、動作の順番は変更できる。あるプロセスは、動作が完了したときに停止される。あるプロセスは方法、機能、手順、サブルーチン、サブプログラムに対応する。プロセスが機能に対応するとき、その停止は、コール機能あるいはメイン機能への機能のリターンに対応する。

さらに、本実施形態は、ハードウエア、ソフトウエア、ファームウエア、ミドルウエア、マクロコードあるいはそれらの組み合わせにより実装される。ソフトウエア、ファームウエア、ミドルウエアあるいはマクロコードにおいて実行された場合には、プログラムコードあるいは必要なタスクを実行するためのコードセグメントは種々の記憶媒体などの機械読取可能な媒体に記憶される。コードセグメントはプロシージャ、機能、サブプログラム、ルーチン、サブルーチン、モジュール、ソフトウエアパッケージ、クラス、あるいは指令、データ構造あるいはプログラムステートメントの組み合わせ、を含む。コードセグメントは、情報、データ、独立変数、パラメータあるいはメモリコンテンツを渡す及び／または受け取ることによって他のコードセグメントあるいはハードウエア回路に結合される。情報、独立変数、パラメータ、データなどは、メモリ共有、メッセージ渡し、トークン渡し、ネットワーク送信などを含む適切な手段を介して渡され、転送あるいは送信される。

概して、以下の記述は、例えば６桁クラスの比較的小型のデジタル署名を実現できる。このことは、署名が低帯域チャネルを介して送信される、署名が認証目的で概して人間の手で入力されるなどの種々の状況において便利に、容易に、安価に及び／または効率的に使用されることを可能にする。後者の場合、小型のデジタル署名はさらにユーザフレンドリなものになる。

以下の説明において、本発明に関する概念は本発明の説明のため及び／またはより良い理解のために説明される。特定の状況、理論及び／または数式の参照は一例を示すためであり、本発明の権利範囲を限定するためではない。

公開鍵署名
概して、今日使用されている公開鍵デジタル署名アルゴリズムには主として２つのクラスがある。

最も一般的なものはＲＳＡシステムである。ここでは公開鍵は大きな合成数Ｎであり、Ｎをｐ＊ｑに因数分解することの困難さが数学的に”難問題”であることの基礎となっている。現在の因数分解アルゴリズムが複雑さにおいて準指数関数的になっている。したがって、例えば８０ビットの鍵によって対称型アルゴリズムを破ることと同等の安全さを維持することを仮定すると、法（モジュラス）Ｎとして約１０２４ビットが必要となる。ＲＳＡシステムにおけるデジタル署名は、Ｎと約同じサイズの整数である。デジタル署名の検証では、Ｎの（概して小さな）ｅ冪乗を法として指数計算を実行しなければならない。

他の良く用いられるデジタル署名技術は、正確な実装によってエルガマル、シャノアあるいはデジタル署名（標準）アルゴリズムＤＳＡと呼ばれている。これらの技術は素数Ｐを法として離散対数を計算することの困難さに基づいている。一番最初に発明されたのは、ディフィ・ヘルマン（Ｄ−Ｈ）鍵交換アルゴリズムであり、離散対数問題に依存している。エルガマルは当該Ｄ−Ｈのデジタル署名への応用である。シャノア及びＤＳＡはデジタル署名のサイズを小さくするために特殊な方法を使用する。法Ｐは概して１０２４ビットである。

因数分解と離散対数の問題が繋がっていることに対する証明は存在しないが、いずれかの問題を解決するためのアルゴリズムは、他に適用可能な類似性をもっており、これが類似の鍵サイズが比較的安全なシステムを獲得する理由である。エルガマルデジタル署名は一対の数（ｒ、ｓ）に関連し、各数のサイズはＰに匹敵する。これに対してシャノアの手法はより小さな署名を可能とし、ｒとｓとは１６０ビット（８０ビット安全性と同等）である。

楕円曲線デジタル署名はエルガマルの変形例であり、より小さな鍵と異なる計算とを用いる。しかしながら、得られる署名は最小の安全さを考慮して約３２０ビットである。

上記の技術のいずれかを使用したときに実用上最も短いデジタル署名は３２０ビットである。１０進数で表現すると、これは、大文字及び小文字、桁、一対の句読点の通常の符号化を使用すると、９０桁の数あるいは約５５文字になる。したがって、ユーザが例えばデジタル署名を正確にタイプ入力することは大変不便で困難な作業である。

数学的背景
以下の議論では、離散対数を計算することに伴う問題点について説明する。この問題は実質的にディフィ・ヘルマンであるが、因数が公知となっていないモジュロである合成数Ｎは、ＲＳＡシステムに類似するものである。

例えば、離散対数問題は以下の処理から開始される。整数Ｎ、ｇ、Ｘが与えられたとき、Ｘ≡ｇ^x(mod N)を満たすｘを見つける。従来の離散対数システムにおいて、Ｎは概して素数であり、ｇは、Ｎを法とする乗法群の大きな素数位数の部分群の生成元である。説明を容易にするために、合成数Ｎが使用される。Ｎを法とする離散対数問題を解決することは、Ｎを因数分解する能力を意味する。ここで、Ｎ≡３(mod ４）かつＮ＝ｐｑ、ｐ、ｑは素数、Ｎはいわゆるブラム整数である。以下では、Ｎは素数ｐとｑの積を表すものとする。

中国人の余剰定理（ＣＲＴ）もまた有用な技術である。単純な場合、任意の整数Ｘ mod Ｎは一対の整数（ａ、ｂ）として表現でき、ここでａ≡Ｘ(mod p) かつｂ≡Ｘ(mod ｑ)である。２つの表現形式の間で変換することは容易なことである。Ｎを法とする所望の解答に戻す前に、しばしば後者の表現を用いて乗算及び累乗などの演算を実行することは都合がよい。２つの因数で表現されるが、それは多数の因数に一般化できる。因数分解の一意性の定理は、どの整数も素数冪の積として一意の表現をもっていることを述べている。その結果、ＣＲＴは概して素因数に関連して用いられる。

さらに、小さな素因数のみをもつ整数は滑らか(smooth)であると呼ばれる。ここでの“小さい”は、概して滑らか境界Ｂの観点から定義される。素因数の１つに関してｐ、ｐ−１が滑らかであるならば、合成数を因数分解するのにポラードのｐ−１アルゴリズムが使用可能である。Ｐ−１が滑らかであるならば、素数Ｐを法とする離散対数を計算するのに同様のアルゴリズムの変形例が使用可能である。特にそれを構成するのにＣＲＴを使用することによって、Ｎのすべての素数を法とする離散対数を計算することが可能であるならば、ポーリッヒ・ヘルマンアルゴリズムは、合成数Ｎを法とする離散対数を計算することができる。

さらに、ディフィ・ヘルマン（Ｄ−Ｈ）鍵交換アルゴリズム規約は以下のように動作する。例えば、アリスとボブなどの２者あるいは両エンティティは、共通の法Ｎと、Ｎを法とする単位群の大きな部分群の生成元ｇの使用に関して合意する。通常、Ｄ−Ｈは素数を法として動作するが、ここでは合成数が使用される。通常、アリスとボブはそれぞれ秘密鍵ａ、ｂを選択し、続いて、Ａ＝ｇ^ａ(mod N)及びＢ＝ｇ^b(mod N)をそれぞれ計算してＡ、Ｂを交換する。次に、アリスは、共有秘密値Ｓ＝Ｂ^ａ(mod N)≡ｇ^ab(mod N)を計算し、ボブは共有秘密値Ｓ＝Ａ^b (mod N)≡ｇ^ab(mod N)を計算する。盗聴者は通常、Ｎを法とする離散対数問題を解決することなしにＳを計算することができない。

さらに、２，３の暗号学上の原始関数（primitive）を以下に説明する。１つはメッセージ認証コード（ＭＡＣ）であり、ここではメッセージに付けるタグを生成するのに秘密の対称鍵が使用される。同じ秘密鍵をもつエンティティはタグが正しいことを検証することができるが、これはタグは鍵を知っている誰かによって生成され、メッセージは改竄されなかったことを意味する。また、擬似乱数器（ＰＲＧ）は比較的小さな入力値であり、それを任意の所望のサイズのランダム状の出力値に“伸張”する。

上記２つの関数はハッシュ関数、ストリーム暗号、あるいはブロック暗号から既知の手法により構成される。例えばＳＨＡ−２５６などのハッシュ関数（ＨＡＳＨ）は、ディフィ・ヘルマン（Ｄ−Ｈ）鍵交換アルゴリズムから引き出される共有秘密値をハッシュすることによって鍵を引き出すのに使用される。最後に、鍵の生成にあたって、鍵を生成するのに暗号学的に安全な乱数の生成元が使用される。

システム概略
離散対数に基づくシステムを使用するデジタル署名には概して２つの部分がある。一方は一時的公開鍵であり、他方は、ディフィ・ヘルマン共有秘密Ｓから引き出される対称鍵を用いて署名された文書のＭＡＣである。一時的公開鍵はしばしば大型である。これは、例えば署名者であるアリスがランダムに選択された秘密鍵からそれを生成し、概して鍵を生成する場合にほとんどあるいは全く制約がないからである。

以下に述べる実施形態において、一時的公開鍵は、小さな語句または少数の文字を公開鍵として使用できるものに引き伸ばすために、ＰＲＧを用いて生成される。小さな数は例えば、数列、選択された数、乱数、時間、アルファベット、英数字の語句、記号（符号）文字、あるいはそれらの組み合わせである。次に、法Ｎの特別な構成を使用するとともにその因数を知ることによって、アリスは自身の公開鍵を効率よく“破壊して”、対応する秘密鍵を見つけることができる。攻撃者はその因数分解を知らないのでそのようなことはできない。ＭＡＣ関数は署名されるべきデータと引き出された鍵とともに使用される。当該鍵はデータを認証するために文脈において有用な任意のサイズに切断される。ここでは、出力ＭＡＣを生成するのに使用される鍵は、続いて任意の通信のためのセッション鍵としても使用することも可能である。

短い署名はオフライン計算においてもともと攻撃されやすいことに注目されたし。したがって、これらの署名は特定の認証者に向けたものとなる。それらはその場での認証（ログイン、ＡＴＭ取引など）あるいは短い時間依存性(time-sensitive)のメッセージの検証においてより有用である。認証者は、２因数認証を用いたり、失敗の回数が多い場合にはそのアカウントを不作動にするなどによって、力づくの攻撃（ブルートフォースアタック）を防止するためにさらなる方策を用いることができる。

したがって、秘密鍵を記憶して必要な計算を実行するために何らかのデバイスが使用される。これは認証のための因数の１つを形成する。２因数認証に関して、パスワード、個人識別番号（ＰＩＮ）あるいは生物測定（バイオメトリック）など（これらに限定されない）種々の第２の因数が実行される。例えば、ＰＩＮ番号は認証デバイスに入力されて署名デバイスの鍵を開けるのに使用される及び／又は署名計算それ自身に組み込まれる。

したがって、アリスの秘密鍵は、例えば携帯電話など彼女が所持する任意のデバイス内に保持される。概して、それは、乱数からデバイス内で生成され、彼女が新たな携帯電話を入手したときに、バックアップとして再構成するのに使用される“秘密共有”の形態を除いてけっして外部に出されない。

以下の議論において、説明のために“６桁の番号”の署名を用いることとする。しかしながら、当業者ならば、６桁未満、６桁以上あるいは６桁の他のワード、符号化された英数字あるいは入力デバイスに適した任意のものが使用されることを認識するであろう。これは認証者が異なれば異なるものである。６（１０進法）桁の数は、約２²⁰の可能性をもち、８個の英数字からなるワードは３⁴⁰の可能性をもつ。これはブルートフォースアタックから保護するために十分な大きさである。以下にいくつかの使用法について述べる。ここで、ここで述べる使用法は一例であり、当業者ならば、他の使用法及び／又は以下に述べる使用法内での変形例が用いられることを認識するであろう。

イントラネットログイン：彼女の会社のイントラネットにログオンするにあたって、アリスは“ＢｉｇＣｏｍ”を入力するために彼女の電話などのデバイスを使用する。電話は６桁の番号を表示する。次にアリスは彼女の名前をタイプし、パスワードのフィールドに彼女のパスワードと認証番号とをタイプ入力する。この場合、デジタル署名は当該番号が要求されるごとに増大される連続番号に基づく。イントラネット認証サーバは、パスワードと認証番号とを検証するとともに、リプレイ攻撃を防ぐために前記連続番号を使用する。

電話による認証：アリスが電話を介して例えば株式仲買人などの第３者に対して彼女自身を認証することを望んでいることを想定する。アリスのパスワードは彼女の電話を介して入力される。次にこのパスワードは署名の計算に組み込まれる。最終的な番号がパスワードとしてタイプ入力される。この方法は、例えば、署名が電話を介して読み出されるかあるいはＤＴＭＦトーンとして送信される場合に好適する。当該パスワードが株式仲買人あるいは盗聴者に知られないようにすることが望ましい。

物理的アクセス：例えばオフィスビルなどの構造物に入るために、アリスは彼女の電話アプリケーションで”office”を選択して彼女の従業員番号と署名番号とをタイプ入力する。これは、音、ＤＴＭＦトーン、赤外線、ブルーツースあるいはＲＦＩＤを使用して送信することにより自動化される。

ホームエントリ：アリスが家に戻ったとき、彼女はＰＩＮ番号を電話に入力することによりドアを開ける。これは認証アプリケーションをアンロックする効果をもつ。このことは、ドアコントローラが彼女の鍵に用いるべく構成されたパスワードをもつ必要はないが、アリスの電話を盗むことは家に入るのに十分ではないことを意味する。次に彼女は、ドアを制御しているスタンドアロンデバイスに最終的な番号を入力する。このデバイスは、異なる公開鍵の番号を認識するようにあらかじめ構成されている。アリスと彼女の家族一員に関して、それは入力を許可するのはどの鍵（すなわちどの家族一員）かを決定するために署名番号を使用する。（ここでも送信方法が自動化されていることが望ましい）。

システム実装
概して、認証プロセスには多くの段階がある。説明の都合上、ここではアリスは署名するエンティティであり、ビクターは認証するエンティティであることを想定する。認証プロセスは以下の手順で行われる。

１．アリスは彼女の公開鍵を生成する。アリスは生成した公開鍵を彼女が望むだけ多くの異なる認証者に関して使用できるので、一度だけ公開鍵の生成を行えばよい。しかしながら、当業者ならば、異なる認証者あるいは認証者の組に関して２つまたはそれ以上の複数の公開鍵を生成することを認識するであろう。

２．ビクターはアリスの公開鍵を受信して記憶し、それを例えばアカウント、ロック及び自動車などを安全にするのに適切なオブジェクトと関連つける。ここで互いに信頼する必要の複数の認証者が存在することに注意されたし。

３．ビクターはアリスとの使用のための、自身の私有−公開鍵対を生成し、それをアリスに送信する。アリスはこれをビクターとの相互通信のために記憶する。この鍵対はアリスのＮを法として計算されねばならず、他の署名者によって使用できないことに注意されたし。

４．アリスとビクターとは入力値を同期させる。入力値はランダムな数かまたは英数値であるので、これを行うのに数列を使用することは効果的である。数列が使用されるならば、署名プロセスへの入力は通信される必要はない。代わりに、短い乱数が署名の一部として使用される。

５．アリスがビクターに対して彼女を認証することを欲するときはいつでも、彼女は、入力値の現在値に基づいて短い認証子（authenticator）を効率よく生成してそれをタイプし、電話を介して読み、それをＤＴＭＦトーンを使用してそれを可聴状態で送信するかあるいは必要な他の種々の手段を用いてそれを通信する。

上記のプロセスで、第１のステップは一度だけ発生する。結果は公開鍵なので、例えば公開ディレクトリなどに公開された、認証者による次の認証を容易にするために、例えば認証機関（Certificate Authority）に提出される。ステップ２−４は各認証者に独自のものであり、アリスとビクターの公開鍵は大きいので、ステップ２及び３はオンラインで実行される必要がある。アリスは法Ｎの因数分解を知っているので、ビクターの公開鍵を‘破って’、彼の秘密鍵を回収することができる。しかし、この秘密鍵はアリスにとって特殊なものである。したがって、アリスはそれを実行する特別な動機をもたない。

図１は、例えばデジタル署名を生成するためにアリスによって使用される例示的なデバイス１００を示す。デバイス１００は、入力値から擬似乱数列値を生成するように構成された擬似乱数生成器（ＰＲＧ）１１０を備える。デバイス１００は法Ｎ及び、公開鍵として使用される擬似乱数列値をもとにして１つの値を生成するように構成された鍵生成ユニット１２０を含む。鍵生成ユニット１２０はさらに生成された公開鍵に対応する私有鍵を生成するように構成されている。さらに、デバイス１００は、認証エンティティの公開鍵値を受信するように構成された受信器１３０と、モジュロＮと、私有鍵値と、認証者の公開鍵値とに基づいて共有秘密値を生成するように構成された秘密鍵生成ユニット１４０と、共有秘密鍵を用いて認証署名値を計算するように構成されたＭＡＣユニット１５０と、認証署名値あるいはデジタル署名を送信するように構成された送信ユニット１６０とを具備する。

図２は、装置１００に対応する例示的装置２００を示しており、例えばビクターによって受信したデジタル署名を認証するのに用いられる。装置２００は、認証署名値を受信するように構成された受信ユニット２１０と、入力値から擬似乱数列値を生成するように構成されたＰＲＧユニット２２０と、モジュラスＮ及び擬似乱数列値に基づいて公開鍵値を生成するように構成された鍵生成ユニット２３０と、モジュラスＮと、私有鍵値と、公開鍵値とに基づいて共有秘密値を生成するように構成された秘密値生成ユニット２４０と、共有秘密鍵を用いて認証署名値を計算するように構成されたＭＡＣユニット２５０と、受信した認証署名値と計算した認証署名値とを比較するように構成された比較ユニット２６０とを具備する。認証署名が一致するならば、受信した認証署名は認証されたことになる。

概して、あるエンティティのデジタル署名は、他のエンティティによって認証されるが、この２つのエンティティは、以下に述べるように共通モジュラスＮの使用に関して合意している。装置１００は、必要に応じて種々の情報またはデータを記憶するように構成された記憶ユニット１７０、必要に応じて暗号化を行うように構成された暗号化ユニット１８０、ユーザが装置１００と対話可能なように構成されたユーザインタフェース１９０などのさらなる要素を具備することができるが、これらに限定されることはない。同様に、装置２００は、必要に応じて種々の情報またはデータを記憶するように構成された記憶ユニット２７０、必要に応じて復号を行うように構成された復号ユニット２８０などのさらなる要素を具備することができるが、これらに限定されることはない。

装置１００の動作に影響を与えることなしに要素１１０−１９０のいずれか１つあるいは任意の組み合わせを再配置することができる。同様にして、装置２００の動作に影響を与えることなしに要素２１０−２８０のいずれか１つあるいは任意の組み合わせを再配置することができる。さらに、装置１００の動作に影響を与えることなしに要素１１０−１９０のいずれか１つあるいは任意の組み合わせを組み合わせとして実行することができる。同様にして、装置２００の動作に影響を与えることなしに要素２１０−２８０のいずれか１つあるいは任意の組み合わせを組み合わせとして実行することができる。装置１００及び２００の動作について以下に詳細に説明する。

以下の説明では説明をわかりやすくするために法Ｎは１０２４ビットであることを想定する。しかしながら、サイズは１０２４ビットより小さくてもよくあるいは１０２４ビットよりも大きくてもよい。実際のサイズは本質的ではなく、サイズを増大すれば暗号化に関してより大きな安全性が得られるが、計算上のオーバヘッドが大きくなりコスト増大につながる。さらに、他の特定の値、理論及び／またはアルゴリズムの引用は説明を容易にするための単なる一例である。したがって、当業者ならば、異なる値、理論及び／またはアルゴリズムを用いることができる。

ステップ１：アリスの公開鍵を生成すること
このシステムにおける公開鍵は、合成数からなる法Ｎと、単位群の生成元ｇ（すなわち、Ｎを法とする（乗法の逆数をもつ元）とを具備する。概して、例えば、２は少なくとも半分は満足な生成元であり、したがって、真になるまで可能なＮｓを生成するとともに変数ｇの可能性を無視してもよい。

Ｎは以下の基準を満たすように不規則的に生成される。

１．Ｎは素数ｐとｑの積である。Ｎ≡３mod 4（すなわち、Ｎはブラム数）
２．２はＮを法とする単位群の生成元である、あるいはそのような生成元である小さなｇを見つける。

３．（ｐ−１）／２は大きな素数ｐ１とｐ２との積である。同様にして、（ｑ−１）／２は大きな素数ｑ１とｑ２との積である。
４．ｐ１、ｐ２、ｑ１、ｑ２はそれぞれ滑らかである。すなわち、（ｐ１−１）及び（ｐ２−１）、（ｑ１−１）（ｑ２−１）は例えば１００００００以下の異なる素数の積である。

Ｎを生成する工程は実際下から上に向かって進行する。１００００００以下には約５００００の素数が存在するが、そのうちの約１２が４つの第３段階の因数（four third stage factor）（全体で約５０）の各々に対して必要となる。約２．８×１０¹⁷⁰の組み合わせが存在するので、候補が不足することはない。工程は長いが一度だけ実行される。とり得るＮｓの数は、約１０³⁰⁵ の１０２４ビット素数の比較的小部分であるが、その特別な特性にもとづく探索を防止するのに満足する数より以上である。
５００００前後の基礎となる素数のテーブルがアプリケーションによって提供され、鍵生成の後に廃棄されるかあるいはエラトステネスのふるいを使用して動的に生成される。候補としての大きな素数の素数性のチェックは、試行割算法（trial division）などの既知のアルゴリズムを使用して行われ、その後にミラー・ラビンアルゴリズムのような確率素数性チェックアルゴリズムが複数ラウンド実行される。

アリスの秘密鍵は、上記したすべての種々の素数であり、それらが組み合わされてＮを形成する。種々の中国人剰余定理の計算を行うためのさらなるデータが記憶される。

ステップ２：公開鍵を取り出すこと
アリスの公開鍵は法Ｎ（かつｇ（それが定数２でない場合））をもとにしている。これはアリスが彼女の身元をビクターに証明したときに、ビクターに直接送信されるかあるいは、彼女の公開鍵を含む認証を生成する認証機関に送信されて必要に応じて配布される。公開鍵なので、ビクターがアリスとの接続を確信している限り、それがどのようにしてビクターに到達するかは全然問題にならない。

公開鍵なので、多くの異なる状況において同じような鍵が認証のために使用可能であり、鍵が配布される方法は柔軟であり、公開鍵インフラストラクチャ（ＰＫＩ）認証、ＬＤＡＰ／アクティブディレクトリなどを含めることができる。

ステップ３：ビクターの公開鍵対
ビクターはディフィ・ヘルマン鍵交換アルゴリズムに関して通常の方法でアリスとの間で使用される鍵対を生成する。すなわち、彼は乱数ｖを選択してＶ＝ｇ^ｖ(mod N)を計算する。Ｖは公開鍵であり、アリスに対して送信される必要がある（アリスがビクターとの接続を確信している限りにおいて公開鍵は極秘のものではない）。ビクターの秘密鍵ｖはアリスにとって独自のものでなくてはならない、すなわち、彼は申込者が異なるならば異なるｖｓを使用しなければならない。彼は、アリスに関連するパスワード／生体情報とともに、認証／認可データベースにｖを記憶する。

ステップ４：数列の同期化
認証署名を作成するときに、アリスとビクターとにより使用可能な入力項目あるいは入力値が必要である。短い署名ならば、この入力は数列のように暗に同期化されるかあるいはそれは小さな乱数であるか、現在の時間に関連しているか、署名が適用されるデータであってもよい。リプレイ攻撃からの保護が重要であるが、数列は単純な方法でこの保護を提供する。署名が何らかの方法で送信されたデータに適用されるならば、当該データ自身はある程度リプレイ攻撃に対処できる。

説明を簡単にするために、アリスとビクターとは数列を使用することを想定する。この数列はゼロに初期化されるが、認証番号が生成／受諾されるたびに増加される。ビクターが最後に数列ｉに関する署名を見たならば、彼は、数例ｉ＋１、ｉ＋２、．．．比較的小さな限度、を仮定して署名をチェックする。署名が受諾された場合には、リプレイ攻撃を防ぐために数列はその値に更新される。時間を基準としたシステムならば、例えば、現在の時間の小さな範囲内の時間値をもとにして署名を受諾する。

ステップ５：認証署名の生成／チェック
説明を簡単にするために署名すべき入力値あるいはデータ項目を（それが数列、時間スタンプ、あるいはある種の短いメッセージであるにしろ）Ａと呼ぶことにする。

１．Ａは伸張される。Ｄ＝ＰＲＧ（Ａ）mod Ｎを計算する。ＰＲＧは、入力から任意の長さの擬似乱数列を生成することを思い出していただきたい。ＰＲＧは、法（モジュラス）内に存在するのと同等のビットを生成する。その程度のビットが生成されるが、それらは有用ではない。そこで、安全のために、Ｎを法とする整数上で略一様に配布されることが望ましい。無視できる確率でＤの無効な値が生成されるであろう。非常に小さな値であるかあるいはＧＣＤ（Ｄ，Ｎ）≠１となる値である（この場合、Ｎは偶発的に素因数分解された）。

２．ディフィ・ヘルマン鍵交換アルゴリズムにおいて、Ｄはアリスの公開鍵として使用される。このプロセスを完了させるために、彼女は対応する秘密値（ｄ）を知る必要がある。これを実行するために、彼女はＮを法とする離散対数問題を解決することになる。アリスは、種々の数の因数の詳細のすべてを知っているのでこれを行うことができる。

ａ．ｐを法とし、ｑを法とする対応する離散対数から中国人の余剰定理を用いて、秘密値ｄが計算される。

ｂ．ポーリッヒ・ヘルマンアルゴリズムを使用して、ｐ１及びｐ２を法とする離散対数を計算することによって、ｐを法とする離散対数が決定される。ｑについても同様である。

ｃ．再びポーリッヒ・ヘルマンアルゴリズムを使用して、ｐ１−１の全ての素因数を法とする離散対数を見つけることによって、ｐ１を法とする離散対数が決定される。

ｄ．ｆを法とする離散対数の計算は、ｆが１０００００００よりも小さい素数であるとき、ポラード・ローアルゴリズム、指数計算あるいはブルートフォースによって管理可能な時間内に行うことができる。これは、ここではｆの約５０の値について行う必要がある。

３．アリスは、通常のディフィ・ヘルマン鍵交換アルゴリズムによって共有秘密値Ｓを計算する。Ｓ＝ＨＡＳＨ（Ｖ^d（mod Ｎ））。数列が使用された場合には、この段階までのステップは、認証署名が送信されるまでにすべて計算されることに注意されたし。その場合、例えば電話などの装置はＳのすでに計算された値を使用し、次のステップが完了した後、次のＳの比較的高価な計算を開始する。

４．アリスは、ａ＝ＭＡＣ（Ｓ）として送信される認証署名すなわちデジタル署名を計算する。あるいは、認証署名は、ａ＝ＭＡＣ（Ｓ、入力値）、ａ＝ＭＡＣ（Ｓ、d[PIN]）、ａ＝ＭＡＣ（Ｓ、入力値、d[PIN]）あるいはａ＝ＭＡＣ（Ｓ、ｄ［入力値、PIN］）、などの他の値を入力値として用いて生成される。しかしこれらに限定されないことは勿論である。ここで、d[ ]は、ｄを用いた［］の暗号化を意味する。次に、認証署名は適切な長さに切断された後、所望の形態に変換される。ＰＩＮ／パスワード及び／または入力値が個別に送信される場合には、ここでの計算に含まれない。

５．アリスはどうにか彼女のメッセージ（おそらく空である）と認証署名ａとを送信する。これは単に、数字キーパッド上で６桁の数をタイプ入力することにより行うことができる。

６．ビクターは前記認証署名を受信して、Ａが何であるか（それが現在の数列であるか現在の時間であるかあるいは受信メッセージであるか）を知る。彼は、Ｄ＝ＰＲＧ（Ａ）をアリスと同様の方法で計算する。

７．ビクターは共有秘密値Ｓ＝ＨＡＳＨ（Ｄ^d（mod Ｎ））を計算する。

８．ビクターは受信したａが、彼がアリスと同じ方法で計算したものと同じであるかどうかをチェックする。

９．署名が一致するならば認証は成功したとみなされる。ＰＩＮ／パスワードが別個に送信された場合にはそれも一致することになる。数列の方法が使用された場合には、ビクターは現在の数列をＡ＋１に更新する。

因数の１つ−１が滑らかならば、ポラードのｐ−１アルゴリズムはＮを素因数分解できることに注意されたし。ｐ及びｑはこの可能性を避けるために特別に選択された。（ｐ−１及びｑ−１が両方とも滑らかであるときにこの方法を使用することが可能であることに注意されたし。これは、ｐ−１及びｑ−１の因数のすべてに関して特別な選択を必要とし、結果的に、公開鍵を破るためのアリスの作業は、Ｎを因数分解するための攻撃者の作業の平方根となることに帰着する。他のレイヤの大きな素数を導入することによって、大きな利点が得られる。）Ｎの構造が他の因数分解アルゴリズムが乱数Ｎの場合よりも良い確率で成功することを可能にすることはない。

成功した認証の最後に、共有秘密値Ｓはセッション鍵あるいは共有秘密鍵として使用されることに注意されたし。しかし、これは帯域が制限されている場合には効率的ではない。また、アリスがビクターの公開鍵Ｖを受信したとき、彼女は、ｖ（アリスといっしょに使用されるビクターの秘密鍵）を取得するために彼女自身の一時的な値に関して行うのと同様の方法でそれを”破る“ことができる。実際に起こったことは、彼のｖをアリスに送信するために公開鍵方法がビクターに関して使用されたということである。上で説明したことの残りは、共有されたｖをセッション鍵すなわち共有秘密鍵として使用するときでさえも、アリスの装置及びビクターの装置で全く同様に実行される。

したがって、デジタル署名及び認証の生成が実行される。図３は、上記したＮを共有の法として使用することに関して合意した２つのエンティティ間の認証に使用される例示的方法３００を示している。方法３００において、入力値から擬似乱数列値が生成される（３１０）。この入力値は上記したとおりのものであり、ユーザが入力したデータに基づく。例えば、ユーザ入力データは、数列、乱数、現在の時刻、アルファベット文字の語、アルファベット文字のフレーズ、英数字の作品、あるいは英数字のフレーズであるが、これに限定されない。

次に、認証または署名エンティティのための公開鍵が、入力値を引き伸ばすすなわち伸張し、Ｎを法とする引き伸ばされた入力値を解決することによって、法Ｎ及び上記した擬似乱数列値に基づいて生成される（３２０）。同様にして公開鍵値に対応する私有鍵値が生成される（３３０）。私有鍵値は、Ｎを法とする離散対数問題を解決することによって生成される。例えば、私有鍵値は、中国人の余剰定理、ポーリッヒ・ヘルマンアルゴリズムそしてポラード・ローアルゴリズムを用いて生成される。

次に、共有秘密値が、法Ｎ、私有鍵値そして検証者の公開鍵値に基づいて生成される（３４０）。ここで、検証者の公開鍵は、共有秘密値の生成に先立つ任意の時点で受信される。共有秘密値を用いて認証署名値すなわちデジタル署名が生成される（３５０）。あるいは、認証署名は、共有秘密値とＰＩＮまたはパスワードを用いて生成される。あるいは、認証署名は、共有秘密値、入力値そしてＰＩＮを用いて生成される。ＰＩＮが使用される場合、このＰＩＮは署名エンティティから受信され、認証署名において使用すべく暗号化される。入力値とＰＩＮ（必要であるとき）とは、検証者が暗号化された鍵を復号することが可能な限り、私有鍵あるいは他の認可された暗号鍵を用いて暗号化される。さらに、認証署名値を生成するのに使用されるならば、（暗号化された）入力値及び／又は暗号化されたＰＩＮは検証者に送信される。ある場合には、入力値は認証署名の中で用いられ、例えば数列が使用されるならば、送信されないことに注意されたし。

その後、認証署名値は検証エンティティに送信される。認証署名値は送信に先立って切断してもよい。

方法３００を獲得及び／又は実行するのに種々の方法が実行される。例示的装置１００を使用するならば、ＰＲＧユニット１１０は擬似乱数列値を生成し、鍵生成ユニット１２０は公開鍵と私有鍵とを生成し、秘密鍵生成ユニット１４０は秘密値を生成し、ＭＡＣユニット１５０は認証署名を計算する。記憶ユニット１７０は合意された共通の法に関連するデータ及び／又は情報に加えて、装置１００の動作に必要な他のデータ及び／又は情報を記憶する。受信器ユニット１３０は検証者の公開鍵を受信する。送信器ユニット１６０は認証署名及び必要に応じて入力値を送信する。さらに、暗号化ユニット１８０は入力値及び／又はＰＩＮを暗号化し、ユーザインタフェース１９０はユーザ入力データ及びＰＩＮを受信するのに使用される。さらに、認証署名は、生成された後、送信に先立って、ＭＡＣユニット１５０によってあるいは例えば（図示せぬ）プロセッサあるいは送信器ユニット１６０などの別個の要素によって切断される。

図４は、共通の法Ｎの使用に関して合意した２つのエンティティ間の認証での使用のための方法３００に対応する例示的方法４００を示している。方法４００において、認証署名値は認証すべく受信される（４１０）。認証のために、擬似乱数列値が入力値から生成される（４２０）。ここでは、擬似乱数列値は方法３００と同じ方法によって生成される。

次に、法Ｎ及び擬似乱数列値に基いて方法３００と同じ方法によって公開鍵が生成され（４３０）、法Ｎ、私有鍵値、公開鍵に基いて方法３００と同じ方法によって共有秘密値が生成される（４４０）。ここで、私有鍵は署名エンティティの公開鍵に対応する私有鍵であり、方法３００と同じ方法によって生成される。すなわち、私有鍵は、Ｎを法とする離散対数問題を解決することによって生成可能である。

認証署名値は共有秘密値を用いて方法３００と同じ方法によって生成される（４５０）。したがって、認証署名はまた、入力値または暗号化された入力値を用いて生成される。あるいは、認証署名は、共有秘密値及びＰＩＮまたはパスワードを用いて生成される。あるいは、認証署名は、共有秘密値、入力値及びＰＩＮを用いて生成される。ＰＩＮが用いられる場合には、暗号化されたＰＩＮが署名エンティティから受信されて、認証署名において使用される。入力値が使用される場合には、ときとして入力値が署名エンティティから受信される。しかしながら、場合によっては、例えば数列が使用されるならば入力値を受信する必要はない。

受信された認証署名値は計算された認証署名値と比較される（４６０）。受信された認証が認証署名の切断部分であった場合には、受信された認証署名値は計算された認証署名値の切断された部分と比較される。２つの署名値が一致するならば、受信された認証署名が認証されたことになる。ここでは、認証プロセスにおいてＰＩＮが使用される。すなわち、２つの因数認証を提供するために、署名エンティティに対応するＰＩＮが記憶される。すなわち、暗号化されたＰＩＮが受信されたならば、ＰＩＮは復号されて、記憶されているＰＩＮと比較される。両方の認証署名値とＰＩＮとが一致するならば、認証署名は認証されたことになる。検証者が暗号化鍵を復号できるという条件で、入力値及び必要ならばＰＩＮが署名エンティティの私有鍵あるいは他の合意された暗号化鍵を用いて復号される。

方法４００を獲得及び／又は実行するために種々の手段が実装される。例示的装置２００を使用するならば、受信器ユニット２１０は認証署名値と入力値及び／又は必要ならば暗号化されたＰＩＮを受信する。ＰＲＧユニット２２０は擬似乱数列値を生成し、鍵生成ユニット２３０は公開鍵と私有鍵を生成し、秘密値生成ユニット２４０は共有秘密値を生成し、ＭＡＣユニット２５０は認証署名を計算し、比較ユニット２６０は、認証署名及び必要に応じてＰＩＮを比較する。記憶ユニット２７０は合意された共通の法に関連するデータ及び／又は情報に加えて、装置２００の動作に必要な他のデータ及び／又は情報を記憶する。復号ユニット２８０は入力値及び／又は必要に応じてＰＩＮを復号する。

このようにしてデジタル署名が生成されて送信され、認証される。

種々の他の認証が達成可能であることに注意されたい。例えば図５は、他のエンティティの法Ｎに基いて生成された公開鍵が受信される（５１０）他の方法５００を示している。Ｎを法とする離散対数問題を解決することによって、受信された公開鍵に対応する私有鍵が生成される（５２０）。その後、検証者の公開鍵に対応する私有鍵は、２つのエンティティ間での将来の通信における共有鍵あるいは対称鍵として使用される（５３０）。

さらに、方法３００、４００そして５００は、６００として示される記憶媒体６１０及びプロセッサ６２０によって実行される。記憶媒体６１０は方法３００，４００そして５００を実行するように構成された命令を具備する。プロセッサ６２０は例えば記憶媒体に記憶された命令を実行することによって方法３００、４００そして５００の動作を制御する。

さらに、デジタル署名は短いので、空間及び帯域制限があるすべての状況に対処することができる。例えば、それらは電話を介して読み出したり、キーパッドに入力したり、手書き入力することもできる。したがって、それらは一般的な状況において偽造を完全に防ぐことはできない。それであっても、一般的な状況においてそのような署名が使用可能である。例えば、署名は時間依存性を持たせて短い時間の間だけ有効となるように実装可能である。また、署名入力は比較的盗聴できにくくすることができる（例えば、局所検証を行うドア上のキーパッドに署名を入力する）。また、認証が短時間に連続して２，３回以上成功しなかった場合、検証エンティティはある時間不作動にされるかあるいは締め出される。このことは、ＰＩＮが連続して３回まちがって入力されたときに、ＡＴＭがカードを“食べる”のと原理的に類似している。

他の方法として、署名は特別な検証エンティティに関して、すなわち、署名は一人の特定の検証者自身の公開鍵に特定して生成されることが考えられる。この場合においても、認証動作が何回も失敗したならば検証者は当該アカウントを締め出すことができる。しかしながら、署名は必ずしも時間に依存したものにする必要はなく、アクセス行為は時間間隔を置くこともできる。これはログインパスワードの現在のやり方と類似している。

最後に、アリスとビクターをエンティティとして実施形態を説明したが、他の種類のエンティティも適用できることは勿論である。また、特定の条件及び値を参照して実装の例を説明したが、一般的な認証方法に影響を与えることなしに他の条件及び値を使用することは勿論である。

したがって、上記の実施形態は一例であり、本発明を制限するものと解釈されることを意図していない。実施形態の記述は例示的であり、特許請求の範囲を限定するものではない。したがって、本発明の教義は、他の種類の装置にも容易に適用可能であり、当業者ならば多くの代替例、変更例、変形例を思いつくことが可能である。

以下の図面を参照して種々の実施形態を詳細に説明する。ここで同じ要素については同じ参照番号を用いることとする。
図１は、デジタル署名を生成するためにエンティティによって使用される例示的デバイスを示す。 図２は、デジタル署名を認証するために検証エンティティによって使用される例示的デバイスを示す。 図３は、デジタル署名を生成するのに用いられる例示的方法を示す。 図４は、デジタル署名を認証するのに使用される例示的方法を示す。 図５は、認証に使用される他の例示的方法を示す。 図６は、認証に使用される他の例示的デバイスを示す。

Claims (42)

1. 共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための方法であって、
   入力値から擬似乱数列値を生成することと、
   前記法Ｎと前記擬似乱数列値とに基づいて第１の公開鍵値を生成することと、
   前記第１の公開鍵値に対応する第１の私有鍵値を生成することと、
   第２の公開鍵値を受信することと、
   前記法Ｎと、前記第１の私有鍵値と、前記第２の公開鍵値とに基づいて、共有秘密値を生成することと、
   を具備する方法。
2. 前記共有秘密値を用いて認証署名値を計算することと、前記認証署名値を送信することと、をさらに具備する請求項１記載の方法。
3. 前記認証署名値を切断すること、をさらに具備し、前記認証署名値を送信することは、切断された認証署名値を送信することを含む請求項２記載の方法。
4. 前記認証署名値を計算することは、前記共有秘密値と前記入力値とを用いて認証署名値を計算することを含む請求項２または請求項２に従属する請求項３記載の方法。
5. パスワード値を受信することと、
   前記第１の私有鍵値を用いて前記パスワード値を暗号化することと、
   前記暗号化されたパスワード値を送信することと、
   をさらに具備する請求項２または請求項２に従属する請求項３，４のいずれかに記載の方法。
6. 前記認証署名値を計算することは、前記共有秘密値と前記暗号化されたパスワード値とを用いて前記認証署名値を計算することを含む請求項５記載の方法。
7. 前記第１の私有鍵値を生成することは、
   前記Ｎを法とする離散対数問題を解決することによって前記第１の私有鍵値を生成することを含む請求項１から６のいずれか１つに記載の方法。
8. ユーザ入力データを受信することをさらに具備し、前記入力値は前記ユーザ入力データに基づく請求項１から７のいずれか１つに記載の方法。
9. 前記入力値を送信することをさらに具備する請求項１から８のいずれか１つに記載の方法。
10. 前記Ｎを法とする離散対数問題を解決することによって前記第２の公開鍵に対応する第２の私有鍵を生成することと、
    前記第２の私有鍵を共有秘密鍵として用いることと、をさらに具備する請求項１から９のいずれか１つに記載の方法。
11. 請求項１から１０のいずれか１つに記載の方法の実行を制御するように構成されたプロセッサ。
12. 請求項１または請求項１に従属する請求項２−１０のいずれか１つに記載の方法を実行する指令を記憶するように構成された記憶媒体。
13. 共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための装置であって、
    入力値から擬似乱数列値を生成するための手段と、
    前記法Ｎと前記擬似乱数列値とに基づいて第１の公開鍵値を生成するための手段と、
    前記第１の公開鍵値に対応する第１の私有鍵値を生成するための手段と、
    第２の公開鍵値を受信するための手段と、
    前記法Ｎと、前記第１の私有鍵値と、前記第２の公開鍵値とに基づいて、共有秘密値を生成するための手段と、
    を具備する装置。
14. 前記共有秘密値を用いて認証署名値を計算するための手段と、前記認証署名値を送信するための手段と、をさらに具備する請求項１３記載の装置。
15. 前記認証署名値を切断するための手段をさらに具備し、前記認証署名値を送信することは、切断された認証署名値を送信することを含む請求項１４記載の装置。
16. 前記認証署名値を計算するための手段は、前記共有秘密値及び／または前記入力値を用いて認証署名値を計算することを含む請求項１４または請求項１４に従属する請求項１５記載の装置。
17. パスワード値を受信するための手段と、
    前記第１の私有鍵値を用いて前記パスワード値を暗号化するための手段と、
    前記暗号化されたパスワード値を送信するための手段と、
    をさらに具備する請求項１４または請求項１４に従属する請求項１５、１６のいずれか１つに記載の装置。
18. 前記認証署名値を計算するための手段は、前記共有秘密値と前記暗号化されたパスワードとを用いて前記認証署名値を計算するための手段を含む請求項１７記載の装置。
19. 前記第１の私有鍵値を生成するための手段は、
    前記Ｎを法とする離散対数問題を解決することによって前記第１の私有鍵値を生成するための手段を含む請求項１３または請求項１３に従属する請求項１４から１８のいずれか１つに記載の方法。
20. Ｎを法とする離散対数問題を解決することによって前記第２の公開鍵に対応する第２の私有鍵を生成するための手段と、
    前記第２の私有鍵を共有秘密鍵として用いるための手段と、をさらに具備する請求項１３または請求項１３に従属する請求項１４から１９のいずれか１つに記載の装置。
21. 共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための装置であって、
    入力値から擬似乱数列値を生成するように構成された擬似乱数生成器と、
    前記法Ｎと前記擬似乱数列値とに基づいて第１の公開鍵値を生成するとともに、前記第１の公開鍵値に対応する第１の私有鍵値を生成するように構成された鍵生成ユニットと、
    第２の公開鍵値を受信するように構成された受信器ユニットと、
    前記法Ｎと、前記第１の私有鍵値と、前記第２の公開鍵値とに基づいて、共有秘密値を生成するように構成された秘密値生成ユニットと、
    を具備する装置。
22. 前記共有秘密値を用いて認証署名値を計算するように構成されたメッセージ認証コードユニットと、
    前記認証署名値を送信するように構成された送信器ユニットと、をさらに具備する請求項２１記載の装置。
23. 前記送信器ユニットは、切断された認証署名値を送信する請求項２２記載の装置。
24. 共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための方法であって、
    第１の認証署名値を受信することと、
    入力値から擬似乱数列値を生成することと、
    前記法Ｎ及び前記擬似乱数列値とに基づいて第１の公開鍵値を生成することと、
    前記法Ｎと、私有鍵値と、前記第１の公開鍵とに基づいて共有秘密値を生成することと、
    前記共有秘密値を用いて第２の認証署名値を計算することと、
    前記第１の認証署名値と、前記第２の認証署名値とを比較することと、
    を具備する方法。
25. 前記第１及び第２の認証署名値を比較することは、前記第１の認証署名値と、前記第２の認証署名値の切断部とを比較することを含む請求項２４記載の方法。
26. 前記入力値を受信することをさらに具備する請求項２４または２５記載の方法。
27. 前記認証署名値を計算することは、前記共有秘密値と前記入力値とを用いて前記認証署名値を計算することを含む請求項２４または請求項２４に従属する請求項２５、２６のいずれか１つに記載の方法。
28. 暗号化されたパスワード値を受信することと、
    前記第１の公開鍵値を用いて前記パスワード値を復号することと、
    前記復号されたパスワード値を検証することと、
    をさらに具備する請求項２４または請求項２４に従属する請求項２５から２７のいずれか１つに記載の方法。
29. 前記認証署名値を計算することは、前記共有秘密鍵値と前記暗号化されたパスワード値とを用いて前記認証署名値を計算することを含む請求項２８記載の方法。
30. 請求項２４または請求項２４に従属する請求項２５から２９のいずれか１つに記載の方法の実行を制御するように構成されたプロセッサ。
31. 請求項２４または請求項２４に従属する請求項２５から２９のいずれか１つに記載の方法を実行するための命令を記憶するように構成された記憶媒体。
32. 共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための装置であって、
    第１の認証署名値を受信するための手段と、
    入力値から擬似乱数列値を生成するための手段と、
    前記法Ｎ及び前記擬似乱数列値に基づいて第１の公開鍵値を生成するための手段と、
    前記法Ｎと、私有鍵値と、前記第１の公開鍵とに基づいて共有秘密値を生成するための手段と、
    前記共有秘密値を用いて第２の認証署名値を計算するための手段と、
    前記第１の認証署名値と、前記第２の認証署名値とを比較するための手段と、
    を具備する装置。
33. 前記第１及び第２の認証署名値を比較するための手段は、前記第１の認証署名値と、前記第２の認証署名値の切断部とを比較することを含む請求項３２記載の装置。
34. 前記入力値を受信するための手段をさらに具備する請求項３２または３３記載の装置。
35. 前記認証署名値を計算するための手段は、前記共有秘密値と前記入力値とを用いて前記認証署名値を計算するための手段を含む請求項３２または請求項３２に従属する請求項３３，３４のいずれか１つに記載の装置。
36. 暗号化されたパスワード値を受信するための手段と、
    前記第１の公開鍵値を用いて前記パスワード値を復号するための手段と、
    前記復号されたパスワード値を検証するための手段と、
    をさらに具備する請求項３２または請求項３２に従属する請求項３３から３５のいずれか１つに記載の方法。
37. 前記認証署名値を計算するための手段は、前記共有秘密値と前記暗号化されたパスワード値とを用いて前記認証署名値を計算するための手段を含む請求項３６記載の方法。
38. 共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための装置であって、
    第１の認証署名値を受信するように構成された受信器ユニットと、
    入力値から擬似乱数列値を生成するように構成された擬似乱数生成器と、
    前記法Ｎ及び前記擬似乱数列値に基づいて第１の公開鍵値を生成するように構成された鍵生成ユニットと、
    前記法Ｎと、私有鍵値と、前記第１の公開鍵とに基づいて共有秘密値を生成するように構成された共有秘密値生成ユニットと、
    前記共有秘密値を用いて第２の認証署名値を計算するように構成されたメッセージ認証コードユニットと、
    前記第１の認証署名値と、前記第２の認証署名値とを比較するように構成された比較ユニットと、
    を具備する装置。
39. 前記比較ユニットは、前記第１の認証署名値と、前記第２の認証署名値の切断部とを比較する請求項３８記載の装置。
40. 共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための方法であって、
    前記法Ｎに基づいて生成された公開鍵値を受信することと、
    Ｎを法とする離散対数問題を解決することによって、前記公開鍵値に対応する私有鍵を生成することと、
    前記私有鍵を共有秘密鍵として用いることと、
    を具備する方法。
41. 前記私有鍵を生成することは、中国人剰余定理を用いて前記私有鍵を計算することを含む請求項４０記載の方法。
42. 共通の法Ｎを使用することについて合意した２つのエンティティ間の認証における使用のための装置であって、
    法Ｎに基づいて生成された公開鍵値を受信するための手段と、
    Ｎを法とする離散対数問題を解決することによって、前記公開鍵値に対応する私有鍵を生成するための手段と、
    前記私有鍵を共有秘密鍵として用いるための手段と、
    を具備する装置。

Images