(57)【特許請求の範囲】
【請求項１】
「プロバ」（Ａ）と呼ばれる第１の実体と「ベリファイヤ」（Ｂ）と呼ばれる第２の実体とを含む認証プロセスであって、第１の実体は、公開鍵ｖと秘密鍵ｓとを有し、
これらの鍵は、ｖ＝ｓ-t（ｍｏｄ  ｎ）の関係によって関連付けられ、ここで、ｎは、モジュラスと呼ばれる整数であり、ｎは、プロバ（Ａ）に特有であり、かつ、少なくとも２つの素数の積であり、ｔはパラメータであり、
第２の実体は、公開鍵ｖを知っており、
これらの実体は、ゼロ認識情報を交換しかつこの情報に基づいてプロバ（Ａ）の認証のための暗号計算を実行する手段を提供され、
ｎを法とする計算は、「チャイニーズ剰余」方法に従って実行され、
暗号計算は、
・プロバ（Ａ）が、１とｎ−１との間の範囲にわたる少なくとも１つの整数ｒをランダムに選択し、ｒt（ｍｏｄ  ｎ）に等しい少なくとも１つのパラメータ（ｘ）を計算し、そして、該少なくとも１つのパラメータとメッセージ（Ｍ）との少なくとも１つの関数である、少なくとも１つのオープニングｃを計算し、該少なくとも１つのオープニングをベリファイヤ（Ｂ）へ送り、
・ベリファイヤ実体（Ｂ）が、オープニングｃを受信し、かつ、１つの質問ｅをランダムに選択し、質問ｅをプロバ（Ａ）へ送り、
・プロバ（Ａ）が、質問ｅを受信し、質問ｅと秘密鍵ｓとを使用して計算を実行し、該計算の結果が少なくとも１つの回答ｙを生じ、プロバ（Ａ）が、該少なくとも１つの回答をベリファイヤ（Ｂ）へ送り、
・ベリファイヤ（Ｂ）が、該少なくとも１つの回答ｙを受信し、公開鍵ｖとモジュラスｎとを使用して１つの計算を実行し、結果が受信されたオープニングｃに密接であることをｎを法とする計算を伴ってチェックする
ことによって完了される
ことを特徴とする認証プロセス。
【請求項２】
ｎのサイズは、ビットの数で表現され、１０００より小さい
ことを特徴とする請求項１記載のプロセス。
【請求項３】
ｎのサイズは、７００と８００との間である
ことを特徴とする請求項２記載のプロセス。
【請求項４】
公開鍵ｖ、秘密鍵ｓ、及び署名されるべきメッセージＭを記憶する記憶装置と、該記憶装置に接続されるプロセッサとを有する署名者装置（Ａ）によって実行されるメッセージ署名プロセスであって、
これらの鍵は、ｎを法とするｖ＝ｓ-t（ｍｏｄ  ｎ）の演算を介して関連付けられ、ここで、ｎは、モジュラスと呼ばれる整数であり、ｎは、署名者装置に特有であり、かつ、少なくとも２つの素数の積であり、ｔはパラメータであり、
前記プロセスは、
前記プロセッサによって、メッセージＭの関数であるオープニングｃを計算することと、
前記プロセッサによって、秘密鍵の関数である数ｙを計算することと、
前記プロセッサによって、数ｙおよびｃをメッセージＭの署名としてメッセージＭと送信することとを含み、
ｎを法とする計算は、「チャイニーズ剰余」方法に従って実行される
ことを特徴とするメッセージ署名プロセス。
【請求項５】
前記プロセッサは、１とｎ−１との間の整数ｒをランダムに選択し、かつ、ｒt（ｍｏｄ  ｎ）に等しいパラメータｘを計算し、かつ、パラメータｘとメッセージＭとの関数である数ｃを計算し、署名者装置の秘密鍵ｓを使用して数ｙを計算し、
前記数ｙは、数ｒとｅとの関数であり、
前記プロセッサは、数ｃとｙとをメッセージＭの署名として送信する
ことを特徴とする請求項４記載の署名プロセス。
【請求項６】
秘密鍵ｓを記憶する記憶装置と、該記憶装置に接続されるプロセッサとを有するプロバ装置によって、オープニングｃを生成して送信することであって、オープニングｃを生成することは、
前記プロセッサによって、ｎを法として計算することであって、ｎは、プロバ装置に特有な整数であり、かつ、素数の積であることと、
前記プロセッサによって、１とｎ−１との間の数ｒをランダムに選択することと、
前記プロセッサによって、ｒt（ｍｏｄ  ｎ）に等しいパラメータｘを計算することであって、ｔはパラメータであることと、
前記プロセッサによって、少なくとも部分的にパラメータｘに基づいてオープニングｃを計算することとであって、ｃはパラメータｘと異なることとを含むことと、
オープニングｃの送信に応じて、前記プロセッサによって、質問ｅを受信することと、
前記プロセッサによって、結果ｙを生成して送信し、結果ｙと、プロバ装置によって保持される秘密鍵ｓに関連する公開鍵ｖとに基づいてプロバ装置が認証されることを可能とすることであって、結果ｙを生成することは、少なくとも部分的に質問ｅと秘密鍵ｓとに基づき、ｎを法として計算することを含むことと、
を含み、
ｎを法として計算することは、「チャイニーズ剰余」方法を用いることを含む
認証方法。
【請求項７】
認証プロセスのためのプロバ装置であって、
プロバ装置によって保持される秘密鍵ｓを記憶する記憶装置と、
該記憶装置に接続されるプロセッサと、を含み、
該プロセッサは、
オープニングｃを生成し、プロバ装置にオープニングｃを送信させ、ここで、オープニングｃの生成は、
ｎを法とする計算であって、ｎは、プロバ装置に特有の整数であり、かつ、素数の積であることと、
１とｎ−１との間の数ｒのランダムな選択と、
ｒt（ｍｏｄ  ｎ）に等しいパラメータｘの計算であって、ｔはパラメータであることと、
少なくとも部分的にパラメータｘに基づいた、オープニングｃの計算であって、ｃはパラメータｘと異なることとを含み、
オープニングｃの送信に応じて、質問ｅの受信においてプロバ装置を制御し、
結果ｙを生成し、プロバ装置に結果ｙを送信させ、結果ｙと、プロバ装置によって保持される秘密鍵ｓに関連する公開鍵ｖとに基づいてプロバ装置が認証されることを可能とし、ここで、結果ｙの生成は、少なくとも部分的に質問ｅと秘密鍵ｓとに基づき、ｎを法とする計算を含み、
ｎを法とする計算は、「チャイニーズ剰余」方法とｎの少なくとも２つの素因数とを用いることを含む
ように構成されている
プロバ装置。
【請求項８】
命令が格納された、コンピュータ読み取り可能な媒体であって、
該命令は、秘密鍵ｓを記憶する記憶装置と、該記憶装置と接続されるプロセッサとを有するプロバ装置で実行されると、プロバ装置に認証方法を実行させ、
該認証方法は、
前記プロセッサによって、オープニングｃを生成して送信することであって、オープニングｃを生成することは、
前記プロセッサによって、ｎを法として計算することであって、ｎは、プロバ装置に特有な整数であり、かつ、素数の積であることと、
前記プロセッサによって、１とｎ−１との間の数ｒをランダムに選択することと、
前記プロセッサによって、ｒt（ｍｏｄ  ｎ）に等しいパラメータｘを計算することであって、ｔはパラメータであることと、
前記プロセッサによって、少なくとも部分的にパラメータｘに基づいてオープニングｃを計算することであって、ｃはパラメータｘと異なることとを含むことと、
前記プロセッサによって、オープニングｃの送信に応じて、プロバ装置によって、質問ｅを受信することと、
前記プロセッサによって、結果ｙを生成して送信し、結果ｙと、プロバ装置によって保持される秘密鍵ｓに関連する公開鍵ｖとに基づいてプロバ装置が認証されることを可能とすることであって、結果ｙを生成することは、少なくとも部分的に質問ｅと秘密鍵ｓとに基づき、ｎを法として計算することを含むことと、
を含み、
ｎを法として計算することは、「チャイニーズ剰余」方法とｎの少なくとも２つの素因数とを用いることを含む
コンピュータ読み取り可能な媒体。
【請求項９】
結果ｙを生成することは、前記プロセッサによって、ｒｓe（ｍｏｄ  ｎ）に等しいｙを計算することを含む
請求項６記載の方法。
【請求項１０】
前記プロセッサは、ｒｓe（ｍｏｄ  ｎ）に等しいｙを計算することによりｙを計算するように構成されている
請求項７記載のプロバ装置。
【請求項１１】
結果ｙを生成することは、前記プロセッサによって、ｒｓe（ｍｏｄ  ｎ）に等しいｙを計算することを含む
請求項８記載のコンピュータ読み取り可能な媒体。
【請求項１２】
認証プロセスのためのプロバ装置であって、
オープニングｃを生成し、プロバ装置にオープニングｃを送信させる手段であって、オープニングｃの生成は、
ｎを法とする計算であって、ｎは、プロバ装置に特有の整数であり、かつ、少なくとも２つの異なる素数の積であることと、
１とｎ−１との間の数ｒのランダムな選択と、
ｒt（ｍｏｄ  ｎ）に等しいパラメータｘの計算であって、ｔはパラメータであることと、
少なくとも部分的にパラメータｘに基づいた、オープニングｃの計算であって、ｃはパラメータｘと異なることとを含む、手段と、
オープニングｃの送信に応じて、質問ｅの受信においてプロバ装置を制御する手段と、
結果ｙを生成し、プロバ装置に結果ｙを送信させ、結果ｙと、プロバ装置によって保持される秘密鍵ｓに関連する公開鍵ｖとに基づいてプロバ装置が認証されることを可能とする手段であって、結果ｙの生成は、少なくとも部分的に質問ｅと秘密鍵ｓとに基づき、ｎを法とする計算を含む手段と、
を含み、
ｎを法とする計算は、「チャイニーズ剰余」方法とｎの少なくとも２つの素因数とを用いることを含む
プロバ装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、減少された計算の組を伴う認証または署名プロセスに関する。
【０００２】
より正確には、本発明は、公開鍵暗号分野に関する。このプロセスによると、認証されるべき実体−プロバ（prover）−は、秘密鍵と関係する公開鍵とを有する。認証する実体−ベリファイヤ−（verifier）は、認証を達成するためには、この公開鍵を必要とするだけである。
【０００３】
更により正確には、本プロセスは、「ゼロ認識プロトコル」と呼ばれる（即ち、認識の如何なる通信も有しない）プロセスの組に関する。この種のプロセスによると、認証は、プロバの秘密鍵について何も開示しないプロトコルに従って（認識されるように、かつ、完全に筋が通っているとして科学共同体によって考慮された仮定の下で）実行される。
【０００４】
更により正確であるために、本発明は、因数分解問題に基づく（即ち、大きな整数を素数の積に因数分解することの困難に基づく）ゼロ認識プロセスに関する。
【０００５】
本発明は、電話相手またはメッセージを認証する必要がある全てのシステム、または、メッセージに署名する必要がある全てのシステムに適用可能であり、詳細には、プロバによって実行されるべき計算の量がクリティカルであるシステムに適用可能である。これは、特に、標準のマイクロプロセッサを使用するカード、または、低価格のカードに対する場合である。これらのカードは（しばしば、暗号プロセッサと呼ばれる）算術コプロセッサを具備せず、該カードでは、暗号計算が加速されなくてはならない。
【０００６】
本発明の一般的なアプリケーションは、電子財布である。電子財布は、価格理由または技術的理由（例えば、接触不要なインターフェースの使用）のいずれかまたはその両方の理由によって暗号プロセッサの使用を放棄しながら、非常に高いセキュリティレベルを要求する。
【０００７】
他の可能性のあるアプリケーションは、次世代テレカード（telecard）である。次世代テレカードの価格制約は、電子財布の価格制約よりもはるかに厳しい。
【０００８】
【従来の技術および発明が解決しようとする課題】
多数のゼロ認識識別プロセスが、公表されている。例えば、
−“Advances in Cryptology: Proceedings of CRYPTO'86, Lecture Notes in Computer Science”vol. 263, Springer-Verlag, Berlin, 1987, pp. 186-194において公表された“how to prove yourself: Practical solutions to identification and signature problems”とタイトルの付けられたA. FIATとA. SHAMIRとによる記事に記載されたFIAT-SHAMIRプロトコル
−Advances in Cryptology: Proceedings of EUROCRYPT'88; Lecture notes in Computer Sciences”vol. 330, Springer-Verlag, Berlin, 1988, pp. 123-128において公表された“A Practical zero-knowledge protocol fitted to security microprocessors minimising both transmission and memory”とタイトルの付けられたL.C. GUILLOUとJ.J. QUISQUATERとによる記事に記載されたGUILLOU-QUISQUATERプロトコル
−離散対数問題に基づくフランス特許出願FR-A-2 176 058に記載されたGIRAULTプロトコル
【０００９】
一般的に言えば、大抵のゼロ認識識別（または、メッセージ認証）プロトコルは、３つのステップを含む。簡単のために、「ベリファイヤＢは、プロバＡに関する全ての公開パラメータ（即ち、プロバＡの識別子や公開鍵など）を既に知っている」ということを仮定する。
【００１０】
第１のトランザクションとして、Ａは、認証または署名されるべきメッセージだけでなく、「オープニング」と呼ばれる値“ｃ”、即ち、（Ａよってランダムに選択された数ｒからそれ自身得られた）パラメータｘの擬似ランダム関数ｈを通したイメージを、Ｂに供給する。ｃ＝ｈ（ｘ，〔Ｍ〕）であり、ここで、シンボル〔Ｍ〕は「Ｍが任意である」ということを意味する。これが、第１のステップである。いくつかのプロトコルは、いくつかのオープニングを含む。
【００１１】
第２のトランザクションの間、Ｂは、ランダムに選択されたパラメータｅ（「質問」）を、Ａへ送る。それが、第２のステップである。
【００１２】
第３のトランザクションの間、Ａは、質問ｅとオープニングｃとＡの秘密鍵とに密接した「回答」ｙを、Ｂへ送る（第３のステップ）。
【００１３】
そして、Ｂは受信した回答をチェックする。より正確には、Ｂは、式
【数３９】
0004945026.tif 000002
を使用して要素ｙとｅとｖとからｘを再計算し、かつ、
【数４０】
0004945026.tif 000003
をベリファイする。これが、第４のステップである。
【００１４】
認証すべきメッセージがないときは、擬似ランダム関数ｈの使用は任意である。この場合、ｃ＝ｘが便利である。立証は、
【数４１】
0004945026.tif 000004
をチェックすることを具備する。
【００１５】
いくつかのプロトコルにおいて、ベリファイヤとプロバとの間には、１または２以上のトランザクションがある。
【００１６】
メッセージ署名に対して、パラメータｅはｃに等しくされるので、最初の２つのステップは破棄される。そして、Ａは、ｃとｅ（＝ｃ）とｙとを連続的に計算するだけである。
【００１７】
回答されるべき質問の数ｕは、希望されるプロトコルセキュリティレベルに直接依存する。このレベルは、詐称者（即ち、Ａを不正に模倣する実体Ｃ）を検出することの確率ｐとして定義される。確率ｐは、パラメータｋによって測定される。パラメータｋの値は、式ｐ＝１−２-kによって、ｐに関係付けられる。言い換えると、詐称者は、２k回に１回の成功しか有しない。「もし、プロトコルが困難な数学的計算に依存するならば、かつ、もし、オープニングが十分な長さであるならば、ｕの長さは単にｋビットに等しくなくてはならない」ということが、本ケースにおいて論証されることができる。ｋの一般的な値は３２である。このことは、４０億回に１回成功することを、詐称者に与える。識別の失敗が非常に有害な結果を有するかも知れないアプリケーション（例えば、法律行為）においては、この長さは、少ないビットに減少されてもよい。
【００１８】
因数分解を使用するプロトコルに対して、ｒの項におけるｘの計算は、または、ｅの項におけるｙの計算は、または、その両方は、ｎを法とする作業を含む。ここで、ｎは、因数分解することが困難な合成数である。この数は、信頼できる第三者によって生成された普遍的なタイプの数であるべきと言われる。この数は、全ての認可された実体によって記憶されかつ使用される。ｎの因数分解を解くことは全ての信用されたユーザーの秘密鍵を処理することなので、ｎの「普遍的な」特徴は「大きな数（通常は１０２４ビット）である」ということを意味する。
【００１９】
それらの基本的なバージョンでは、上述されたプロトコルはいずれも、以前の段落において記述されたようなシビアな仕様（低価格、低複雑化）に応じなくてはならないアプリケーションにおいて実現されることができない。なぜならば、要求される計算は、暗号プロセッサ無しのマイクロプロセッサカードによっては実行されることができないからである。
【００２０】
フランス特許出願FR-A-2 752 122はこれらのプロトコルを楽天的に記述しているが、該特許出願は、いわゆる「予備計算を伴う」モードに続く離散対数法を含むプロトコルに限定され、「規則正しく予定された再ロードを含む」という欠点を有する。
Cryptology, Crypto 88 Proceegings, XP000090662, pp. 583-588において先に公表された“zero-knowledge Authentication scheme with Secret Key Exchange”とタイトルの付けられたJ. BRANDTらからの文献は、２人のユーザーの間における秘密鍵の交換を伴うゼロ認識認証スキームを記述している。該スキームでは、プロバは、該プロバ自身のモジュラスｎ＝ｐｑを計算し、かつ、タイプｍd（ｍｏｄ  ｎ）の作業を実行する。
【００２１】
本発明は、因数分解を含むゼロ認識識別（またはメッセージ署名または認証）プロトコルを使用するときに、プロバによって実行されるべき計算の数を減少することを目的とする。特定の作業ｖ＝ｓ-t（ｍｏｄ  ｎ）を使用するとき、ゲインは約数２または３に到達しやすい。
【００２２】
本発明は、また、−詳細にはGUILLOU-QUISQUATERプロトコルと結合されたときに−、電子財布または次世代テレカードのようなアプリケーションに対して、低価格の標準マイクロ回路カードにおいて具備される公開鍵を伴う識別（またはメッセージ認証または署名）の高速な完了を可能にする。
【００２３】
モジュラスｎは各個のパラメータであり（言い換えれば、各ユーザーは彼自身のｎ値を有し）、この選択物は（好ましくは結合されてもよい）以下の２つの方法で活用される。
１）第１に、現在使用される値よりも小さい（一般的には、１０００ビットより小さく、かつ、例えば、７００ビットと８００ビットとの間の範囲にわたる）ｎの長さを保持することによる。ｎの因数分解を解くことは関連するユーザーの秘密鍵だけを処理しかつ他のユーザーの秘密鍵を処理する方法がないので、これは可能である。この修正は、ｎを法として実行される計算の継続期間を、単独で４０％減少する。
２）もし、ユーザーが該ユーザーのセキュリティデバイスのメモリ内にｎの素因数を記憶しているならば、２つの素因数が存在するときに、彼は、ｎを法とする計算の継続期間を４０％更に減少するために、チャイニーズ剰余技術（Chinese remainders technique）を使用してもよい。この減少は、いくつか（一般的には、３または４）の素因数を使用するときに増大される。
【００２４】
総合的に考えると、ｎを法とする計算は、少なくとも６０％（即ち、係数２）減少されることができる。
【００２５】
正確には、本発明は、「プロバ」と呼ばれる第１の実体と「ベリファイヤ」と呼ばれる第２の実体とを含む認証のプロセスに関し、第１の実体は、公開鍵
【数４１】
0004945026.tif 000005
と秘密鍵
【数４２】
0004945026.tif 000006
とを有し、これらの鍵は、
【数４３】
0004945026.tif 000007
を法とする計算によって関連付けられ、ここで、
【数４４】
0004945026.tif 000008
は、プロバに特有のモジュラスと呼ばれる整数であり、第２の実体は、公開鍵
【数４５】
0004945026.tif 000009
を知っており、これらの実体は、ゼロ認識コンテクストにおいて情報を交換しかつこの情報に基づく暗号計算を実行する手段を提供され、いくつかの計算は、
【数４６】
0004945026.tif 000010
を法とするモードで実行され、該プロセスは、「ｎを法とする作業のモジュラスはｖ＝ｓ-t（ｍｏｄ  ｎ）として表現され、ｔはパラメータである」ということを特徴とする。
【００２６】
前記実体は、例えば、マイクロ回路カードや電子財布やテレカードなどであってもよい。
【００２７】
好ましい実現によると、ゼロ認識情報交換および暗号計算は、以下の通りである。
・プロバが、１とｎ−１との間の範囲にわたる１つの（いくつかの）整数
【数４７】
0004945026.tif 000011
をランダムに選択し、かつ、ｒt（ｍｏｄ  ｎ）に等しい１つの（いくつかの）パラメータ
【数４８】
0004945026.tif 000012
を計算し、そして、オープニングと呼ばれる１つの（いくつかの）の数
【数４９】
0004945026.tif 000013
を計算し、オープニングは、この（これらの）パラメータとおそらくメッセージ（Ｍ）との１つの（いくつかの）の関数であり、かつ、プロバが、この（これらの）オープニングをベリファイヤへ送る。
・ベリファイヤ実体が、オープニング
【数５０】
0004945026.tif 000014
を受信し、かつ、「質問」と呼ばれる１つの数
【数５１】
0004945026.tif 000015
をランダムに選択し、かつ、この質問をプロバへ送る。
・プロバが、質問
【数５２】
0004945026.tif 000016
を受信し、かつ、この質問
【数５３】
0004945026.tif 000017
と秘密鍵
【数５４】
0004945026.tif 000018
とを使用して１つの（いくつかの）計算を実行し、この（これらの）計算の結果が１つの（いくつかの）回答
【数５５】
0004945026.tif 000019
を生じ、かつ、プロバが、この（これらの）回答をベリファイヤへ送る。
・ベリファイヤが、回答
【数５６】
0004945026.tif 000020
を受信し、かつ、公開鍵
【数５７】
0004945026.tif 000021
とモジュラス
【数５８】
0004945026.tif 000022
とを使用して１つの計算を実行し、かつ、「結果が、受信されたオープニングに密接である」ということを
【数５９】
0004945026.tif 000023
を法とする計算を伴ってチェックする。
【００２８】
数ｎのサイズは、ビットの数で表現され、１０００より小さい。例えば、該サイズは、７００と８００との間であってもよい。
【００２９】
本発明は、また、「署名者」と呼ばれる実体によって使用されるべきメッセージ署名プロセスに関し、この実体は、公開鍵
【数６３】
0004945026.tif 000024
と秘密鍵
【数６４】
0004945026.tif 000025
とを提供され、これらの鍵は、
【数６５】
0004945026.tif 000026
を法とする作業によって関連付けられ、ここで、
【数６６】
0004945026.tif 000027
は、モジュラスと呼ばれる整数であり、
【数６７】
0004945026.tif 000028
はパラメータであり、該プロセスにおいて、署名者は、署名されるべきメッセージの注目すべき関数であるオープニング
【数６８】
0004945026.tif 000029
と秘密鍵の関数である数
【数６９】
0004945026.tif 000030
とを計算し、署名とメッセージとである数
【数７０】
0004945026.tif 000031
と
【数７１】
0004945026.tif 000032
とを送信し、該プロセスは、「モジュラスｎは、署名者に特有である」ということを特徴とする。
【００３０】
好ましい実現によると、署名者は、１とｎ−１との間の整数
【数７２】
0004945026.tif 000033
をランダムに選択し、そして、ｒt（ｍｏｄ  ｎ）に等しいパラメータ
【数７３】
0004945026.tif 000034
を計算し、そして、パラメータ
【数７４】
0004945026.tif 000035
と署名されるべきメッセージとの関数である数
【数７５】
0004945026.tif 000036
を計算し、そして、秘密鍵
【数７６】
0004945026.tif 000037
を使用して数
【数７７】
0004945026.tif 000038
と
【数７８】
0004945026.tif 000039
との関数として数
【数７９】
0004945026.tif 000040
を計算し、そして、数
【数８０】
0004945026.tif 000041
と
【数８１】
0004945026.tif 000042
とを署名として送信する。
【００３１】
【発明の実施の形態】
以下の記述において、本発明は、一例として、プロトコルGUILLOU-QUISQUATERと組み合わされることが仮定される。「本発明はこのプロトコルに限定されない」ということは明らかである。
【００３２】
「GUILLOU-QUISQUATERプロトコルの普遍的なパラメータは、少なくとも１０２４ビットを具備するモジュラス
【数８２】
0004945026.tif 000043
（素数の積）と整数値
【数８３】
0004945026.tif 000044
とである」ということに注意されたい。
【００３３】
公開鍵
【数８４】
0004945026.tif 000045
と秘密鍵
【数８５】
0004945026.tif 000046
とは、式ｖ＝ｓ-t（ｍｏｄ  ｎ)をベリファイする。
【００３４】
保持されるセキュリティレベルは、（
【数８６】
0004945026.tif 000047
以下であり、一般には
【数８７】
0004945026.tif 000048
に等しい）
【数８８】
0004945026.tif 000049
である。
【００３５】
通常の用語に従うと、ＢによるＡの認証は、以下の通りに完了する。ここで、Ａはアリスと呼ばれ、かつ、Ｂはボブと呼ばれる。
１．アリスが、範囲〔１，ｎ−１〕内においてｒを選択し、かつ、ｘ＝ｒt（ｍｏｄ  ｎ）そしてｃ＝ｈ（ｘ，〔Ｍ〕）を計算し、かつ、ｃをボブへ送る。
２．ボブが、範囲〔１，ｕ−１〕内においてｅを選択し、かつ、ｅをアリスへ送る。
３．アリスが、ｙ＝ｒｓe（ｍｏｄ  ｎ）を計算し、かつ、ｙをボブへ送る。
４．ボブが、ｘ＝ｙtｖe（ｍｏｄ  ｎ）を計算し、かつ、ｃ＝ｈ（ｘ，〔Ｍ〕）をベリファイする。
【００３６】
メッセージが認証されるべきでないときは、擬似ランダム関数ｈを含むことは任意である。ｃ＝ｘが使用されることができる。そして、立証は、ｘ＝ｙtｖe（ｍｏｄ  ｎ）をチェックすることを具備する。
【００３７】
本発明によって修正されたプロトコルでは、ｔは唯一の普遍的なパラメータである。
【００３８】
公開鍵は（ｎ，ｖ）である。ここで、ｎは少なくても７６８ビットを有する。アリスの公開鍵ｖと秘密鍵とは、式ｖ＝ｓ-t（ｍｏｄ  ｎ）を満足する。
【００３９】
本発明の第２の特徴の利点を得るために、秘密鍵は、ｎに基づく素因数を具備してもよい。
【００４０】
パラメータｔは公開鍵内に具備されてもよい（この場合、普遍的なパラメータはもはや存在しない）。
【００４１】
アリスとボブとによって保持されるセキュリティレベルは（ｔ以下であり、通常はｕ＝ｔである）ｕである。
【００４２】
ボブによるアリスの認証は、上述されたように実行される。しかし、より高速な計算を伴うと、より小さなモジュラスｎに起因する。
【００４３】
全てのアリスの計算はｎを法として実行されるので、たった１つの係数の乗算に起因するゲインファクタは、プロトコルを実行するときに、アリスによって完了される完全な組の計算に影響を及ぼす。このことは、例えば、Fiat-ShamirまたはGiraultプロトコルと同じであるべきである（後者の場合、係数計算がないので、ステップ３においてゲインは予測されるべきでないが、このステップの実行時間は、第１ステップの係数の累乗に関して無視できる）。
【００４４】
本発明は、また、チャイニーズ剰余技術によって実現されてもよい。チャイニーズ剰余技術は、ｎの素因数のｎを法とする値を計算することを具備する。これらの数は無視できるほど小さいので、これらの作業は迅速に行われる。更に、ｎを法とする結果は「再構成」作業を通して取得されるべきである。この技術は、“Electronic Letters”vol. 18, October 1982, pp. 905-907において公表された“Fast Decipherment algorithm for RSA public-key cryptosystem”とタイトルの付けられたJ.J QUISQUATERとC.COUVREURの記事に記述されている。
【００４５】
ｎが２つの素因数ｐとｑとの積である場合を考える。
【００４６】
ベゾアールの定理から、「ａｂ＋ｂｑ＝１のような２つの整数が存在する」ということが知られる。
【００４７】
ｙ＝ｘe（ｍｏｄ  ｎ）を計算するために、ｘp＝ｘ（ｍｏｄ  ｐ）とｘq＝ｘ（ｍｏｄ  ｑ）とを計算することによって、各素因数を法とするｘの減少を開始する。また、ｅp＝ｅ  ｍｏｄ（ｐ−１）とｅq＝ｅ  ｍｏｄ（ｑ−１）とを計算することによって、（ｐ−１）と（ｑ−１）とを法とするｅを減少する（Guillou-Quisquaterのプロトコルにおいて、ｅは常にｐ−１およびｑ−１より小さく、そして、ｅp＝ｅq＝１である）。
【００４８】
そして、ｙp＝ｘpep（ｍｏｄ  ｐ）とｙq＝ｘqeq（ｍｏｄ  ｑ）とを計算する。ｐとｑとが同様のサイズのとき、これらの計算の各々は、ｅとｎとが同様のサイズのとき（第１の場合）の計算ｙ＝ｘe（ｍｏｄ  ｎ）よりも約８倍高速であり、ｅのサイズがｐのサイズ以下であるとき（例えば、アルゴリズムにおける第２の場合を参照）よりも４倍高速である。そして、２つの計算の組は、４倍高速であるか、または、２倍高速である。
【００４９】
ｙは、更に、ｙpとｙqとから再構成されることができる。これは、式ｙ＝ｙp+ａｐ（ｙq−ｙp）（ｍｏｄ  ｎ）を使用して実行される。
【００５０】
総合的に考えると、チャイニーズ剰余の方法は、（同様のサイズであると仮定される）素因数の数が２より大きくかつｋに等しいときに、第１の場合における３から４の範囲の約数と第２の場合における１．５から２の範囲の約数とによる計算の加速を導く。加速係数は、第１の場合はｋ2に近く、かつ、第２の場合はｋ近い。