(57)【要約】本発明は、秘密のＱiと公開のＧi＝ｇi2によるｍ組の値（ｍ≧１）と、ｆ個（ｆ＞２）の素数の因子の積により形成される公開のモジュールｎと、ＧiＱiv≡１mod ｎまたはＧi≡Ｑivmod ｎの関係により関連付けされた、べきｖ＝２k（ｋ＞１）とによって証明を行なう方法に関する。Ｑiかそのインバースモジュロｎをモジュロｎの二乗まで増加させて得られるｍ個の値か、ｋ−１倍されたランクのうちのそれらの何れかは±ｇiとは異なっている。ｘ2≡ｇiｍｏｄ ｎ、ｘ2≡−ｇiｍｏｄ ｎの２ｍ個の方程式のうち、少なくともそれらのうちの一つは、ｘの解を整数ｎのモジュロの環に有している。【特許請求の範囲】
【請求項１】
あるコントローラ・エンティティに対して、
・ あるエンティティの真性性、および／または、
・ 該エンティティと関連するメッセージ Ｍ の完全性
を証明するようにされている方法であって、以下のパラメータ：
・ 秘密の値 Ｑ１ 、 Ｑ２ 、 ．．．  、 Ｑｍ と公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、  Ｇｍ （ｍは １ 以上）の ｍ 個の組
・  ｆ 個の素因数 ｐ１ 、 ｐ２ 、 ．．．   ｐｆ の積で構成される公開のモジュラス ｎ （ ２ 以上の ｆ ）、
の全部若しくは一部またはこれらのパラメータからの算出値を用い、
前記モジュラスと前記秘密値と公開値は次のタイプの関係があり、
【数１】
2004527139.tif 000126
ここで、ｖは
【数２】
2004527139.tif 000127
のタイプの公開値である指数値を表し（ｋは１より大きいセキュリティパラメータ）；
前記ｍ個の公開値 Ｇｉ は、ｍ個の区別できるベース数 ｇ１ 、 ｇ２ 、… ｇｍ の、 ｆ 個の素因数 ｐ１ 、 ｐ２ 、… ｐｆ より小さい二乗値ｇ ｉ２ であり；
前記 ｐ１ 、 ｐ２ 、… ｐｆ の素因数、および／または、ｍ個のベース数 ｇ１ 、 ｇ２ 、… ｇｍ は以下の条件が満たされるように生成される方法。：
［第１の条件］
各方程式
【数３】
2004527139.tif 000128
がモジュロｎの整数環におけるｘについて解を持つこと；
［第２の条件］
Ｇｉ（Ｑｉｖ   ｍｏｄ   ｎ である場合、 Ｑｉ を二乗してモジュロ ｎ を ｋ−１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）、
Ｇｉ．Ｑｉｖ   （ １ ｍｏｄ   ｎ である場合、 Ｑｉ のモジュロｎを二乗したものの逆モジュロ ｎ を ｋ−１ 回とって得られるｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）；、
［第３の条件］
２ｍ個の方程式
【数４】
2004527139.tif 000129
がモジュロｎの整数環におけるｘについて解を持ち、
前記方法は、 ｆ 個の素因数 ｐｉ を持っている証人と呼ばれているエンティティ、および／または、ベース ｇｉ のｍ個の素因数、および／または、前記素因数のチャイニーズ・剰余法のパラメータ、および／または、公開モジュラス ｎ 、および／または、ｍ個の秘密値 Ｑ  ｉ 、および／または、前記秘密値 Ｑｉ と公開の指数値ｖとの ｆ．ｍ 個の構成要素 Ｑｉ，ｊ （ Ｑｉ，ｊ   （   Ｑｉ   ｍｏｄ   ｐｊ ）を以下のステップによって実現する。
・ 前記証人が、モジュロ ｎ の整数環において、コミットメント Ｒ を計算し ；
それぞれのコミットメントは、
【数５】
2004527139.tif 000130
のタイプの演算（ここで、ｒは０＜ｒ＜ｎである乱数値）を実行するか、
あるいは、
【数６】
2004527139.tif 000131
のタイプの演算（ここで、ｒ ｉ は０＜ ｒｉ ＜ ｐｉ である素因数 ｐｉ に関連した乱数値、それぞれの ｒｉ は乱数値の集合｛ ｒ１，ｒ２， … ｒｆ ｝に含まれている）を実行し、さらに、チャイニーズ・剰余法手法を適用する
ことからなるステップ、
・証人は一つ以上のチャレンジ ｄ を受け、それぞれのチャレンジｄはｍ個の整数 ｄｉ （以下「要素チャレンジ」と呼ぶ）からなり ； 各々のチャレンジ ｄ に基づいて、前記証人は
【数７】
2004527139.tif 000132
のタイプの演算を行なうことによって応答 Ｄ を計算するか、
【数８】
2004527139.tif 000133
のタイプの演算を行なって、さらに、チャイニーズ・剰余法手法を適用するステップ（前記手法はチャレンジｄ、コミットメント Ｒ と同じくらいの数の応答 Ｄ があって、 Ｒ， ｄ、 Ｄ の数の群は｛ Ｒ 、 ｄ 、 Ｄ ｝で参照される３つの数字の組で表される）。
【請求項２】
コントローラとして知られているエンティティについてのデモンストレータとして知られているエンティティの真性性を証明するようにできている請求項 １ に記載の方法であって、
前記デモンストレータエンティティとコントローラエンティティが以下のステップを実行する方法：
［ステップ １ （コミットメント Ｒ の行為）］
・ 各々の呼び出しで、証人は請求項 １ によって指定されるプロセスを適用することによって各々のコミットメント Ｒ を計算し、
・ デモンストレータは、各々のコミットメント Ｒ のコントローラ全部または一部を送り、
［ステップ ２ （チャレンジ ｄ の行為）］
・ 各々のコミットメント Ｒ の全部または一部を受けた後にチャレンジ ｄ を生成し、コントローラは数がコミットメント Ｒ の数と等しいチャレンジ ｄ をデモンストレータに送り、
［ステップ ３ （応答 Ｄ の行為）］
・ 前記証人は、請求項 １ によって指定されるプロセスを適用することによってチャレンジ ｄ から応答 Ｄ を計算し、
［ステップ ４ （チェックする行為）］
・ 前記デモンストレータは、前記コントローラへ各々の応答 Ｄ を送り、
［前記デモンストレータがコミットメント Ｒ の一部だけを送信するとき］
前記デモンストレータがコミットメント Ｒ の一部だけを送信したなら、前記コントローラはｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有していて、それぞれのチャレンジｄとそれぞれの応答 Ｄ から、再構成されたコミットメント Ｒ ´を計算し、該再構成されたコミットメント Ｒ ´は
【数９】
2004527139.tif 000134
のタイプか、または
【数１０】
2004527139.tif 000135
のタイプの関係を満たすとともに、前記コントローラは、それぞれの再構成されたコミットメント Ｒ ´はコントローラに向けて伝達されたそれぞれのコミットメント Ｒ の全てまたは一部を再生成することを確認する。
［前記デモンストレータがコミットメント Ｒ の全部を送信するとき］
前記デモンストレータがコミットメント Ｒ の全部を送信したなら、前記コントローラはｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有していて、それぞれのコミットメント Ｒ は
【数１１】
2004527139.tif 000136
のタイプか、または
【数１２】
2004527139.tif 000137
のタイプの関係を満たすことを確認する。
【請求項３】
デモンストレータエンティティと呼ばれるエンティティに関連したメッセージ Ｍ の完全性について、コントローラエンティティとして知られるエンティティに証明を提供するようにされた請求項 １ に記載の方法であって、
前記デモンストレータエンティティは前記証人を含み、
前記デモンストレータエンティティとコントローラエンティティは以下のステップを実行する方法：
［ステップ １ （コミットメント Ｒ の行為）］
・ 各々の呼び出しで、証人は請求項 １ によって指定されるプロセスを適用することによって各々のコミットメント Ｒ を計算し、
・ デモンストレータは、各々のコミットメント Ｒ のコントローラ全部または一部を送り、
［ステップ ２ （チャレンジ ｄ の行為）］
− 前記デモンストレータは、変数をメッセージ Ｍ とそれぞれのコミットメント Ｒ の全てまたは一部とするハッシュ関数ｈを適用し、
− 前記デモンストレータはトークン Ｔ を前記コントローラに送り、
− 前記コントローラは、前記トークン Ｔ を受け付けると、コミットメント Ｒ と同じ数のチャレンジｄを生成して該チャレンジｄを前記デモンストレータに送り、
［ステップ ３ （応答 Ｄ の行為）］
− 前記証人は、請求項 １ によって指定されるプロセスを適用することによってチャレンジ ｄ から応答 Ｄ を計算し、
［ステップ ４ （チェックする行為）］
・ 前記デモンストレータは、前記コントローラへ各々の応答 Ｄ を送り、
・ 前記デモンストレータがコミットメント Ｒ の一部だけを送信したなら、前記コントローラはｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有していて、それぞれのチャレンジｄとそれぞれの応答 Ｄ から、再構成されたコミットメント Ｒ ´を計算し、該再構成されたコミットメント Ｒ ´は
【数１３】
2004527139.tif 000138
のタイプか、または
【数１４】
2004527139.tif 000139
のタイプの関係を満たし、
・ そして前記コントローラは、前記メッセージ Ｍ とそれぞれの再構成されたコミットメント Ｒ ´のすべてまたは一部とを変数とするハッシュ関数ｈを適用してトークン Ｔ ´を再構成し、
・ そして前記コントローラは前記トークン Ｔ ´が伝達されたトークン Ｔ と同一であることを確認する。
【請求項４】
署名エンティティとして知られたエンティティによってメッセージ Ｍ のディジタル署名を生成するようにするようにされた請求項 １ に記載の方法であって、
［署名動作］
前記署名エンティティは、
・ 前記メッセージ Ｍ 、
・ 前記チャレンジｄおよび／またはコミットメント Ｒ 、
・ 前記応答 Ｄ 、
を備えた署名されたメッセージを得るために署名動作を行ない、
前記署名エンティティは次のステップを行なって署名動作を行なう方法：
［ステップ １ （コミットメント Ｒ の行為）］
・ 各々の呼び出しで、前記証人は請求項 １ によって指定されるプロセスを適用することによって各々のコミットメント Ｒ を計算し、
［ステップ ２ （チャレンジ ｄ の行為）］
・ 前記署名エンティティは、変数をメッセージ Ｍ とそれぞれのコミットメント Ｒ のとするハッシュ関数ｈを適用してバイナリトレインを得て、
・ 該バイナリトレインから前記署名エンティティは、コミットメント Ｒ と同じ数のチャレンジｄを引き出し、
［ステップ ３ （応答 Ｄ の行為）］
前記証人は、請求項 １ によって指定されるプロセスを適用することによってチャレンジ ｄ から応答 Ｄ を計算する。
【請求項５】
コントローラと呼ばれているエンティティによって署名されたメッセージをチェックすることによってメッセージ Ｍ の真性性を証明するようにされている請求項４に記載の方法であって、
［チェック動作］
前記コントローラエンティティは前記署名されたメッセージを有して以下のように進行するチェック動作を行なう方法：
［前記コントローラがコミットメント Ｒ 、チャレンジ ｄ 、応答 Ｄ を持つケース］
コントローラがコミットメント Ｒ 、チャレンジ ｄ 、応答 Ｄ を持つ場合、
前記コントローラは、前記コミットメント Ｒ 、前記チャレンジｄ、前記応答 Ｄ が
【数１５】
2004527139.tif 000140
のタイプの関係を満たすことを確認するか、
【数１６】
2004527139.tif 000141
のタイプの関係を満たすことを確認し、
前記コントローラは前記メッセージ Ｍ 、前記チャレンジｄ、前記コミットメント Ｒ が前記ハッシュ関数
【数１７】
2004527139.tif 000142
を満たすことを確認する。
［前記コントローラはチャレンジｄと応答 Ｄ を有する場合］
前記コントローラはチャレンジｄと応答 Ｄ を有する場合、
前記コントローラは、それぞれのチャレンジｄと応答 Ｄ に基づいて、
【数１８】
2004527139.tif 000143
のタイプの関係か、または、
【数１９】
2004527139.tif 000144
のタイプの関係を満たすコミットメント Ｒ ´を再構成し、
前記コントローラは前記メッセージ Ｍ と前記チャレンジｄが前記ハッシュ関数
【数２０】
2004527139.tif 000145
を満たすことを確認する。
［前記コントローラはコミットメント Ｒ と応答 Ｄ を有する場合］
前記コントローラはコミットメント Ｒ と応答 Ｄ を有する場合、
前記コントローラは前記ハッシュ関数を適用してｄ´を再構成し、
【数２１】
2004527139.tif 000146
前記コンとローラは、前記コミットメント Ｒ 、前記チャレンジｄ´、前記応答 Ｄ が
【数２２】
2004527139.tif 000147
のタイプの関係か、または、
【数２３】
2004527139.tif 000148
のタイプの関係を満たすことを確認する。
【請求項６】
コントローラ・サーバーに対して、
・ エンティティの真性性、および／または
・ 該エンティティと関連するメッセージ Ｍ の完全性、
を証明するようにされたシステムであって、
・ 秘密の値 Ｑ１ 、 Ｑ２ 、 ．．．  、 Ｑｍ と公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ （ｍは １ 以上）の ｍ 個の組、
・  ｆ 個の素因数 ｐ１ 、 ｐ２ 、 ．．．   ｐｆ の積で構成される公開のモジュラス ｎ （ｆは ２ 以上）、
の全てあるいは部分以下のパラメータやそれらパラメータからの算出値を用いており、
前記モジュラスと前記秘密値と公開値は以下のタイプの関係があり、：
【数２４】
2004527139.tif 000149
ここで、ｖは
【数２５】
2004527139.tif 000150
の形式の公開の指数値 ｃを表し、ｋは１より大きいセキュリティパラメータであり、
前記ｍ個の公開の値 Ｇｉ は、ｆ個の素因数 ｐ１，   ｐ２， … ，   ｐｆ より小さいｍ個の区別できるベース数 ｇ１，ｇ２， … ，ｇｍ による ｇｉ２ となる２乗値であり、
前記素因数 ｐ１，   ｐ２， … ，ｐｆ および／または前記ｍ個のベース数 ｇ１，ｇ２， … ，  ｇｍ は以下の条件が満たされるように生成されているシステム：
［第１の条件］
方程式
【数２６】
2004527139.tif 000151
がｘについてモジュロｎの整数環において解をもつこと；
［第２の条件］
Ｇｉ（Ｑｉｖ   ｍｏｄ   ｎ である場合、 Ｑｉ を二乗してモジュロ ｎ を ｋ−１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）、
Ｇｉ．Ｑｉｖ   （ １ ｍｏｄ   ｎ である場合、 Ｑｉ のモジュロｎを二乗したものの逆モジュロ ｎ を ｋ−１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）、
［第３の条件］
少なくとも２ｍ個の方程式
【数２７】
2004527139.tif 000152
がモジュロｎの整数環におけるｘについて解を持つこと；
前記システムは、例えばマイクロプロセッサベースのバンクカードの形態をとるようなノマドオブジェクト証人装置であって、
その証人装置は
・ 前記ｆ個の素数 ｐｉ、 および／または、前記ｍ個のベース ｇｉ 、および／または、前記素因数のチャイニーズ剰余のパラメータ、および／または、秘密の値 Ｑｉ  および公開の指数値ｖの ｆ．ｍ 個の成分 Ｑｉ，ｊ （ Ｑｉ，ｊ   （   Ｑｉ   ｍｏｄ   ｐｊ ）を含むメモリゾーン、
・ 前記証人装置の乱数値生成手段と呼ぶ乱数値生成手段；
・前記証人装置のコミットメント Ｒ の計算手段と呼ぶ計算手段であって、モジュロｎの整数環においてコミットメント Ｒ の計算を行い、各コミットメント Ｒ は、
・ｒがｒが０＜ｒ＜ｎである前記乱数値生成手段による乱数値として、
【数２８】
2004527139.tif 000153
のタイプの演算を行なうか、
・ｒ ｉ が、０＜ｒ ｉ ＜ｐ ｉ で、それぞれ、前記乱数生成手段によって生成され、各ｒ Ｉ はチャイニーズ剰余法を適用することによって得られるランダム値の集合 ［ｒ１，ｒ２， … ，ｒｆ］ に属する、素因数 ｐｉ に関連した乱数値であるとして、
【数２９】
2004527139.tif 000154
のタイプの演算を行なうか、
によって計算され、
前記証人装置は、また、
・ 前記証人で装置のチャレンジｄを受け付け、それぞれのチャレンジｄがｍ個の整数 ｄ  ｉ （以下、要素チャレンジとよぶ）からなる １ 以上のチャレンジｄを受け付ける受け付け手段、
・ それぞれのチャレンジｄに基づいて、前記証人装置の応答 Ｄ を計算し、
・方程式
【数３０】
2004527139.tif 000155
のタイプの演算を行なうこと、あるいは、
・方程式
【数３１】
2004527139.tif 000156
のタイプの演算をおこなって、そして、チャイニーズ剰余法を適用すること、
のいずれかにより応答 Ｄ を計算する計算手段、
・ １以上のコミットメント Ｒ と１以上の応答 Ｄ を伝送する伝送手段、
を備えている（前記手法はチャレンジｄ、コミットメント Ｒ と同じくらいの数の応答 Ｄ があって、 Ｒ， ｄ、 Ｄ の数の群は｛ Ｒ 、 ｄ 、 Ｄ ｝で参照される３つの数字の組で表される）。
【請求項７】
請求項６に記載のシステムであって、デモンストレータと呼ばれているエンティティとコントローラと呼ばれているエンティティの真性性を証明するようにできていて、前記システムは、
・ 前記デモンストレータエンティテイに関連し、前記相互接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができるデモンストレータ装置、
・ 前記コントローラエンティティと関連するコントローラ装置であって、前記コントローラ装置は特に端末であるか遠隔サーバーの形になっていて、特にデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響によるデモンストレータ装置への接続のために、接続手段を含んでいる前記コントローラ装置 ；
を備えており、以下のステップの実行を可能にしている前記システム：
［ステップ １ （コミットメント Ｒ の行為）］：
各々の呼び出しで、請求項 １ によって指定されるプロセスを適用することによって証人装置のコミットメント Ｒ の計算手段が各コミットメント Ｒ を計算し、
該証人手段は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
前記デモンストレータ装置は、また、コミットメント Ｒ の全てはまた一部を前記コントローラ装置に前記相互接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有し、
［ステップ２（チャレンジｄの行為）］：
前記コントローラ装置は、前記コミットメント Ｒ の全部または一部を受け取った後に、それぞれの数がコミットメント Ｒ と同じチャレンジ ｄ を生成する、チャレンジ生成手段を含み、
前記コントローラ装置は、また、接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を含み、
［ステップ３（応答 Ｄ の行為）］：
前記証人装置の前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれそれのチャレンジｄを受け取り、
前記証人装置の前記応答 Ｄ の前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算し、
［ステップ４（チェックの行為）］：
前記デモンストレータの前記伝送手段はそれぞれの応答 Ｄ を前記コントローラへ伝送し、前記コントローラは、また、
・ 前記コントローラ装置の計算手段と呼ばれる計算手段、
・ 前記コントローラ装置の比較手段とよばれる比較手段、
からなり、
［前記デモンストレータが各コミットメント Ｒ の一部を伝送した場合］
前記デモンストレータが各コミットメント Ｒ の一部を伝送した場合には、
ｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有する前記コントローラ装置の前記計算手段は、各チャレンジ Ｒ と各応答 Ｄ から再構成されたコミットメント Ｒ ´を計算し、その再構成されたコミットメント Ｒ ´は
【数３２】
2004527139.tif 000157
のタイプの関係か、
【数３３】
2004527139.tif 000158
のタイプの関係を満たす。
［前記デモンストレータが各コミットメント Ｒ の全部を伝送した場合］
前記デモンストレータが各コミットメント Ｒ の全部を伝送した場合には、
ｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有する前記コントローラ装置の前記計算手段と前記比較手段は、各チャレンジ Ｒ が
【数３４】
2004527139.tif 000159
のタイプの関係か、
【数３５】
2004527139.tif 000160
のタイプの関係を満たすことを確認する。
【請求項８】
コントローラとして知られたあるエンティティに、デモンストレータとして知られたエンティティに関連したメッセージ Ｍ についての完全性の証明を与えるようにされた請求項６に記載のシステムであって、
・ 前記デモンストレータエンティテイに関連し、前記相互接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができるデモンストレータ装置、
・ 前記コントローラエンティティと関連するコントローラ装置であって、前記コントローラ装置は、特に端末であるか遠隔サーバーの形になっていて、前記コントローラ装置を備えており、前記コントローラは、特にデモンストレータ装置へのデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響による接続のために、接続手段を含んでいて、以下のステップの実行を可能にしている前記システム：
［ステップ １ （コミットメント Ｒ の行為）］：
各々の呼び出しで、請求項 １ によって指定されるプロセスを適用することによって証人装置のコミットメント Ｒ の計算手段が各コミットメント Ｒ を計算し、
該証人手段は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
［ステップ２（チャレンジｄの行為）］：
前記デモンストレータ装置は、少なくともあるトークン Ｔ の計算に、変数を前記メッセージおよび各コミットメント Ｒ の全部または一部とするハッシュ関数ｈを適用する、前記デモンストレータの計算手段と呼ばれる計算手段からなり、
前記デモンストレータ装置は、また、各トークン Ｔ を前記コントローラ装置に前記接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有し、
前記コントローラ装置は、また、前記トークンを受け取った後で、コミットメント Ｒ の数と同じ数の前記チャレンジｄを生成するチャレンジ生成手段を有し、
前記コントローラ装置は、また、接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を有し、
［ステップ３（応答 Ｄ の行為）］：
前記証人装置の前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれそれのチャレンジｄを受け取り、
前記証人装置の前記応答 Ｄ の前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算し、
［ステップ４（チェックの行為）］：
前記デモンストレータの前記伝送手段はそれぞれの応答 Ｄ を前記コントローラへ伝送し、
前記コントローラは、また、前記コントローラ装置の計算手段と呼ばれる計算計算手段を有し、この計算手段は、ｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有するとともに、第１に、各チャレンジｄと各応答 Ｄ から再構成されたコミットメント Ｒ ´を計算し、この再構成されたコミットメント Ｒ ´は
【数３６】
2004527139.tif 000161
のタイプの関係か、
【数３７】
2004527139.tif 000162
のタイプの関係を満たし、
第２に、前記メッセージ Ｍ および各再構成されたコミットメント Ｒ ´の全てまたは一部を変数として有する前記ハッシュ関数ｈを適用することによりトークン Ｔ ´を計算し、
前記コントローラ装置は、また、受け付けられたトークン Ｔ について前記トークン Ｔ ´を計算する、前記コントローラ装置の比較手段として知られている比較手段を有する。
【請求項９】
署名エンティティと呼ばれるエンティティによって、署名されたメッセージとして知られているメッセージ Ｍ のディジタル署名を生成するようにするようにされた請求項６に記載のシステムであって、前記署名されたメッセージは、
・ 前記メッセージ Ｍ 、
・ 前記チャレンジ ｄ 、および／または、前記コミットメント Ｒ 、
・ 前記応答 Ｄ；
を含んでいて、
［署名動作］
前記システムは、前記署名エンティティに関連している署名装置からなるようなものであり、前記署名装置は、前記証人装置に、相互接続手段で相互接続されていて、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができ、
以下のステップの実行を可能にする前記システム：
［ステップ １ （コミットメント Ｒ の行為）］
各々の呼び出しで、請求項 １ によって指定されるプロセスを適用することによって証人装置のコミットメント Ｒ の計算手段が各コミットメント Ｒ を計算し、
該証人手段は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
［ステップ２（チャレンジｄの行為）］
前記署名装置は、変数を前記メッセージおよび各コミットメント Ｒ の全部または一部とするハッシュ関数ｈを適用し、あるバイナリトレインを計算し、このバイナリトレインからコミットメント Ｒ と同じ数のチャレンジｄを導出する前記署名装置の計算手段と呼ばれる該計算手段、
［ステップ３（応答 Ｄ の行為）］
前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれそれのチャレンジｄを受け取り、
前記証人装置の前記応答 Ｄ の前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算し、
前記証人装置は、前記証人装置の伝達装置と呼ばれ、前記相互接続手段を通して前記署名装置へと前記応答 Ｄ を伝達させる、伝達装置からなる。
【請求項１０】
コントローラと呼ばれているエンティティによって、署名されたメッセージをチェックすることによってメッセージ Ｍ の真性性を証明するようにできている、請求項 ９ に記載のシステムであって、
［チェック動作］
前記システムは
コントローラエンティティに関連したコントローラ装置からなるようになっていて、
前記コントローラ装置は、特に端末であるか遠隔サーバーの形になっていて、特に前記署名装置へのデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響による接続のために、接続手段を含んでいて、
前記署名装置は、署名装置の伝送手段として知られていて、
前記接続装置を通じて、前記署名されたメッセージの前記コントローラ装置への伝送手段からなる前記署名エンティティに関連していて、前記コントローラ装置は、
・ 前記メッセージ Ｍ 、
・ 前記チャレンジｄ、および／または、前記コミットメント Ｒ 、
・ 前記応答 Ｄ 、
を含む署名されたメッセージからなり、
前記コントローラ装置は、
・ 前記コントローラ装置の計算手段と呼ばれる計算手段、
・ 前記コントローラ装置の比較手段と呼ばれる比較手段、
からなり、
［前記コントローラ装置がコミットメント Ｒ 、チャレンジｄ、応答 Ｄ を有する場合］
前記コントローラ装置がコミットメント Ｒ， チャレンジｄ、応答 Ｄ を有する場合
．．前記コントローラ装置の前記計算手段および前記比較手段は、
前記コミットメント Ｒ 、前記チャレンジｄ、前記応答 Ｄ が
【数３８】
2004527139.tif 000163
のタイプか、
【数３９】
2004527139.tif 000164
のタイプの関係を満たすことを確認し、
．．前記コントローラ装置の前記計算手段と前記比較手段は、前記メッセージ Ｍ， 前記チャレンジｄ、前記コミットメント Ｒ が前記ハッシュ関数
【数４０】
2004527139.tif 000165
を満たすことを確認する。
［前記コントローラ装置がチャレンジｄ、応答 Ｄ を有する場合］
前記コントローラ装置がチャレンジｄ、応答 Ｄ を有する場合、
．．前記コントローラ装置の前記計算手段は、各チャレンジｄと各レスポンス Ｄ に基づいて、
【数４１】
2004527139.tif 000166
のタイプか、
【数４２】
2004527139.tif 000167
のタイプの関係を満たすコミットメント Ｒ ´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージ Ｍ と前記チャレンジｄがハッシュ関数
【数４３】
2004527139.tif 000168
を満たすことを確認する。
［前記コントローラ装置がコミットメント Ｒ 、応答 Ｄ を有する場合］
前記コントローラ装置がコミットメント Ｒ 、応答 Ｄ を有する場合、
．．前記コントローラ装置の前記計算手段は、前記ハッシュ関数を適用して、
【数４４】
2004527139.tif 000169
のようなｄ´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記コミットメント Ｒ 、前記チャレンジｄ´、前記応答 Ｄ が
【数４５】
2004527139.tif 000170
のタイプの関係を満たすか、
【数４６】
2004527139.tif 000171
のタイプの関係を満たすことを確認する。
【請求項１１】
あるエンティティに関連した端末装置であって、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のようなノマドオブジェクトにおける微小論理回路の形態を特にとることができ、コントローラ装置に対して
・ あるエンティティの前記真性性、および／または、
・ 該エンティティに関連したあるメッセージ Ｍ の完全性、
を、パラメータ：
秘密の値 Ｑ１ 、 Ｑ２ 、 ．．．  、 Ｑｍ と公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ （ｍは １ 以上）の ｍ 個の組、
ｆ 個の素因数 ｐ１ 、 ｐ２ 、 ．．．   ｐｆ の積で構成される公開のモジュラス ｎ （ ２ 以上の ｆ ）、
や、これらのパラメータからの算出値の全部または一部を用いて証明するようにされていて、前記モジュラスと前記秘密値と公開値は
【数４７】
2004527139.tif 000172
のタイプの関係があり、ここで、ｖは
【数４８】
2004527139.tif 000173
の形態の公開値である指数値を表し（ｋは１より大きいセキュリティパラメータ）；
前記ｍ個の公開値 Ｇｉ は、ｍ個の異なったベース数 ｇ１ 、 ｇ２ 、… ｇｍ の、 ｆ 個の素因数 ｐ１ 、 ｐ２ 、… ｐｆ より小さい二乗値ｇ ｉ２ であり；
前記 ｐ１ 、 ｐ２ 、… ｐｆ の素因数、および／または、ｍ個のベース数 ｇ１ 、 ｇ２ 、… ｇｍ は以下の条件が満たされるように生成される端末装置：
［第１の条件］
各方程式
【数４９】
2004527139.tif 000174
がモジュロｎの整数環におけるｘについて解を持つこと；
［第２の条件］
Ｇｉ（Ｑｉｖ   ｍｏｄ   ｎ である場合、 Ｑｉ を二乗してモジュロ ｎ を ｋ−１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）、
Ｇｉ．Ｑｉｖ   （ １ ｍｏｄ   ｎ である場合、 Ｑｉ のモジュロｎを二乗したものの逆モジュロ ｎ を ｋ−１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）；
［第３の条件］
２ｍ個の方程式
【数５０】
2004527139.tif 000175
がモジュロｎの整数環におけるｘについて解をもち、
前記端末装置は、以下を備える証人装置を備え、
・ 前記ｆ個の素因数 ｐｉ 、および／または、ベース ｇｉ のｍ個の素因数、および／または、前記素因数のチャイニーズ・剰余法のパラメータ、および／または、公開モジュラス ｎ 、および／または、ｍ個の秘密値 Ｑｉ 、および／または、前記秘密値 Ｑｉ と公開の指数値ｖとの ｆ．ｍ 個の構成要素 Ｑｉ，ｊ （ Ｑｉ，ｊ   （   Ｑｉ   ｍｏｄ   ｐｊ ）を含むメモリゾーン；
・ 前記証人装置の乱数値生成手段と呼ぶ乱数値生成手段；
・ 前記証人装置のコミットメント Ｒ の計算手段と呼ぶ計算手段であって、モジュロｎの整数環においてコミットメント Ｒ の計算を行い、各コミットメント Ｒ は、
・ｒがｒが０＜ｒ＜ｎである前記乱数値生成手段による乱数値としたとき、
【数５１】
2004527139.tif 000176
のタイプの演算を行なうか、
・ｒ ｉ が、０＜ｒ ｉ ＜ｐ ｉ で、それぞれ、前記乱数生成手段によって生成されて、チャイニーズ剰余法を適用することによって得られるランダム値の集合 ［ｒ１，ｒ２， … ，ｒｆ  ］ に属する、素因数 ｐｉ に関連した乱数値であるとしたとき、
【数５２】
2004527139.tif 000177
のタイプの演算を行なうか、
によって計算され、
前記証人装置は、また、
・ 前記証人で装置のチャレンジｄを受け付け、それぞれのチャレンジｄがｍ個の整数 ｄ  ｉ （以下、要素チャレンジとよぶ）からなる １ 以上のチャレンジｄを受け付ける受け付け手段、
・ それぞれのチャレンジｄに基づいて、前記証人装置の応答 Ｄ を計算し、
・方程式
【数５３】
2004527139.tif 000178
のタイプの演算を行なうこと、あるいは、
・方程式
【数５４】
2004527139.tif 000179
のタイプの演算をおこなって、そして、チャイニーズ剰余法を適用すること、
のいずれかにより応答 Ｄ を計算する計算手段、
・ １以上のコミットメント Ｒ と１以上の応答 Ｄ を伝送する伝送手段、
を備えている（前記手法はチャレンジｄ、コミットメント Ｒ と同じくらいの数の応答 Ｄ があって、 Ｒ， ｄ、 Ｄ の数の群は｛ Ｒ 、 ｄ 、 Ｄ ｝で参照される３つの数字の組で表される）。
【請求項１２】
請求項１１に記載の端末装置であって、デモンストレータと呼ばれているエンティティとコントローラと呼ばれているエンティティの真性性を証明するようにされていて、
前記デモンストレータエンティテイに関連し、前記接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができるデモンストレータ装置
を含み、前記デモンストレータ装置が、
前記コントローラエンティティと関連していて、特に端末であるか遠隔サーバーの形になっている前記コントローラ装置へと、特にデモンストレータ装置へのデータ処理通信ネットワークを通じて、それ自身、電気的、電磁気的、光学的、あるいは音響によって接続するための接続手段
をまた含んでいるような、以下のステップの実行を可能にしている前記端末装置：
［ステップ １ （コミットメント Ｒ の行為）］：
各々の呼び出しで、請求項 １ によって指定されるプロセスを適用することによって証人装置のコミットメント Ｒ の計算手段が各コミットメント Ｒ を計算し、
・ 該証人手段は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
・ 前記デモンストレータ装置は、また、コミットメント Ｒ の全てはまた一部を前記コントローラ装置に前記接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有する、
［ステップ２および３（チャレンジｄの行為、応答 Ｄ の行為）］：
前記証人装置の前記チャレンジｄの受け取り手段は、前記コントローラ装置と前記デモンストレータ装置の間の前記接続装置を通して、また、前記デモンストレータ装置と前記証人装置の間の前記相互接続装置を通して、前記コントローラ装置から来るそれそれのチャレンジｄを受け取り、
前記証人装置の前記応答 Ｄ の前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算する、
［ステップ４（チェックの行為）］：
前記デモンストレータの前記伝送手段はそれぞれの応答 Ｄ をチェックを行なう前記コントローラへ伝送する。
【請求項１３】
コントローラとして知られたあるエンティティに、デモンストレータとして知られたエンティティに関連したメッセージ Ｍ についての完全性の証明を与えるようにされた請求項１１に記載の端末装置であって、
前記デモンストレータエンティテイに関連し、前記相互接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができるデモンストレータ装置、を備え、前記デモンストレータ装置が
前記コントローラエンティティと関連していて、特に端末であるか遠隔サーバーの形になっている前記コントローラ装置へと、特にデモンストレータ装置へのデータ処理通信ネットワークを通じて、それ自身、電気的、電磁気的、光学的、あるいは音響によって接続するための接続手段
をまた含んでいるような、以下のステップの実行をする前記端末装置：
［ステップ １ （コミットメント Ｒ の行為）］：
各々の呼び出しで、請求項 １ によって指定されるプロセスを適用することによって証人装置のコミットメント Ｒ の計算手段が各コミットメント Ｒ を計算し、
該証人手段は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
［ステップ２および３（チャレンジｄの行為、応答 Ｄ の行為）］：
前記デモンストレータ装置は、少なくともあるトークン Ｔ の計算に、変数を前記メッセージおよび各コミットメント Ｒ の全部または一部とするハッシュ関数ｈを適用する、前記デモンストレータの計算手段と呼ばれる計算手段からなり、
前記デモンストレータ装置は、また、各トークン Ｔ を前記コントローラ装置に前記接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有し、
（前記コントローラ装置は、前記トークン Ｔ を受け取った後、コミットメント Ｒ の数と同じ数のチャレンジｄを生成し、）
前記証人装置の前記チャレンジｄの受け取り手段は、前記コントローラ装置と前記デモンストレータ装置の間の前記相互接続装置を通して、また、前記デモンストレータ装置と前記証人装置の間の前記相互接続装置を通して、前記コントローラ装置から来るそれそれのチャレンジｄを受け取り、
前記証人装置の前記応答 Ｄ の前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算する、
［ステップ４（チェックの行為）］：
前記デモンストレータの前記伝送手段は、それぞれの応答 Ｄ をチェックを行なう前記コントローラへ伝送する。
【請求項１４】
署名エンティティと呼ばれるエンティティによって、署名されたメッセージとして知られているメッセージ Ｍ のディジタル署名を生成するようにするようにされた請求項１１に記載の端末装置であって、
前記署名されたメッセージは、
・ 前記メッセージ Ｍ 、
・ 前記チャレンジ ｄ 、および／または、前記コミットメント Ｒ 、
・ 前記応答 Ｄ；
を含んでいて、
前記端末装置は、前記署名エンティティに関連している署名装置からなるようなものであり、前記署名装置は、前記証人装置に、相互接続手段で相互接続されていて、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができ、
前記署名装置は、また、前記コントローラエンティティと関連していて、特に端末であるか遠隔サーバーの形になっている前記コントローラ装置へと、特にデモンストレータ装置へのデータ処理通信ネットワークを通じて、それ自身、電気的、電磁気的、光学的、あるいは音響によって接続するための接続手段を含んでいて、
［署名動作］
以下のステップの実行をする前記端末装置：
［ステップ １ （コミットメント Ｒ の行為）］：
各々の呼び出しで、請求項 １ によって指定されるプロセスを適用することによって証人装置のコミットメント Ｒ の計算手段が各コミットメント Ｒ を計算し、
該証人手段は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
［ステップ２（チャレンジｄの行為）］：
前記署名装置は、前記署名装置の計算手段と呼ばれる該計算手段を含み、変数を前記メッセージおよび各コミットメント Ｒ の全部または一部とするハッシュ関数ｈを適用して、あるバイナリトレインを計算し、このバイナリトレインからコミットメント Ｒ と同じ数のチャレンジｄを導出し、
［ステップ３（応答 Ｄ の行為）］：
前記証人装置の前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれそれのチャレンジｄを受け取り、前記証人装置の前記応答 Ｄ の前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算し、
前記証人装置は、前記証人装置の伝達装置と呼ばれ、前記相互接続手段を通して前記署名装置へと前記応答 Ｄ を伝達させる、伝達装置からなる。
【請求項１５】
あるコントローラエンティティに関連した端末か遠隔サーバ形態を特にとるコントローラ装置であって、
・ あるエンティティの真性性、および／または、
・ 該エンティティと関連するメッセージ Ｍ の完全性
を証明するようにされている装置であって、以下のパラメータ：
・ 秘密の値 Ｑ１ 、 Ｑ２ 、 ．．．  、 Ｑｍ と公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ （ｍは １ 以上）の ｍ 個の組
・  ｆ 個の素因数 ｐ１ 、 ｐ２ 、 ．．．   ｐｆ の積で構成される公開のモジュラス ｎ （ ２ 以上の ｆ ）で、前記コントローラ装置と関連しているコントローラエンティティには知られていないもの、
の全部若しくは一部またはこれらのパラメータからの算出値を用い、
前記モジュラスと前記秘密値と公開値は、
【数５５】
2004527139.tif 000180
のタイプの関係があり、ここで、ｖは
【数５６】
2004527139.tif 000181
のタイプの公開値である指数値を表し（ｋは１より大きいセキュリティパラメータ、 Ｑｉ は、前記コントローラ装置には知られていない、前記公開値 Ｇｉ に関連している秘密値）；
前記ｍ個の公開値 Ｇｉ は、ｍ個の区別できるベース数 ｇ１ 、 ｇ２ 、… ｇｍ の、 ｆ 個の素因数 ｐ１ 、 ｐ２ 、… ｐｆ より小さい二乗値ｇ ｉ２ であり；
前記 ｐ１ 、 ｐ２ 、… ｐｆ の素因数、および／または、ｍ個のベース数 ｇ１ 、 ｇ２ 、… ｇｍ は以下の条件が満たされるように生成される、
コントローラ装置：
［第１の条件］
各方程式
【数５７】
2004527139.tif 000182
がモジュロｎの整数環におけるｘについて解を持つこと；
［第２の条件］
Ｇｉ（Ｑｉｖ   ｍｏｄ   ｎ である場合、 Ｑｉ を二乗してモジュロ ｎ を ｋ−１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）、
Ｇｉ．Ｑｉｖ   （ １ ｍｏｄ   ｎ である場合、 Ｑｉ のモジュロｎを二乗したものの逆モジュロ ｎ を ｋ−１ 回とって得られるｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）；、
［第３の条件］
２ｍ個の方程式
【数５８】
2004527139.tif 000183
がモジュロｎの整数環におけるｘについて解を持つこと。
【請求項１６】
コントローラと呼ばれるあるエンティティに対して、デモンストレータと呼ばれるあるエンティティの真性性を証明するようにされている請求項１５に記載のコントローラ装置であって、
前記コントローラ装置は、特にデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響によって接続する、デモンストレータエンティティに関連したデモンストレータ装置への接続のための接続手段を含んでいて、
以下のステップを実行するのに用いられる前記コントローラ装置：
［ステップ１および２（コミットメントＲの行為、チャレンジｄの行為）］：
前記コントローラ装置は、また、前記接続装置を通して前記デモンストレータ装置から来るコミットメント Ｒ の全部または一部を受け付ける手段を有し、
前記コントローラ装置は、前記コミットメント Ｒ の全部または一部を受け取った後に、それぞれの数がコミットメント Ｒ と同じであるチャレンジ ｄ （各チャレンジｄはｍ個の整数 ｄｉ （以下「要素チャレンジ」と呼ぶ）からなる）を生成する、チャレンジ生成手段を含み、
前記コントローラ装置は、また、前記接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を含み、
［ステップ３および４（応答 Ｄ の行為、チェックの行為）］：
前記コントローラ装置は、また、
・ 前記接続手段を通じて前記デモンストレータ装置から来る前記応答 Ｄ を受け付ける手段
・ 前記コントローラ装置の計算手段と呼ばれる計算手段
・ 前記コントローラ装置の比較手段と呼ばれる比較手段
を備え、
［前記デモンストレータが各コミットメント Ｒ の一部を伝送した場合］
前記デモンストレータが各コミットメント Ｒ の一部を伝送した場合には、
ｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有する前記コントローラ装置の前記計算手段は、各チャレンジ Ｒ と各応答 Ｄ から再構成されたコミットメント Ｒ ´を計算し、その再構成されたコミットメント Ｒ ´は
【数５９】
2004527139.tif 000184
のタイプの関係か、
【数６０】
2004527139.tif 000185
のタイプの関係を満たし、
前記コントローラ装置の前記比較手段は、各再構成されたコミットメント Ｒ ´を受け付けられた各コミットメント Ｒ の全部または一部と比較する。
［前記デモンストレータが各コミットメント Ｒ の全部を伝送した場合］
前記デモンストレータが各コミットメント Ｒ の全部を伝送した場合には、
ｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有する前記コントローラ装置の前記計算手段と前記比較手段は、各チャレンジ Ｒ が
【数６１】
2004527139.tif 000186
のタイプの関係か、
【数６２】
2004527139.tif 000187
のタイプの関係を満たすことを確認する。
【請求項１７】
デモンストレータと呼ばれるあるエンティティの完全性を証明するようにされている請求項１５に記載のコントローラ装置であって、
前記コントローラ装置は、特にデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響によって、デモンストレータエンティティに関連したデモンストレータ装置への接続のために、接続手段を含んでいて、
以下のステップを実行するのに用いられる前記コントローラ装置：
［ステップ１および２（コミットメントＲの行為、チャレンジｄの行為）］：
前記コントローラ装置は、前記接続装置を通して前記デモンストレータ装置から来るトークン Ｔ を受け付ける手段を、また有し、
前記コントローラ装置は、前記トークン Ｔ を受け取った後に、それぞれの数がコミットメント Ｒ と同じであるチャレンジ ｄ （各チャレンジｄはｍ個の整数 ｄｉ （以下「要素チャレンジ」と呼ぶ）からなる）を生成する、チャレンジ生成手段を含み、
前記コントローラ装置は、また、前記接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を含み、
［ステップ３および４（応答 Ｄ の行為、チェックの行為）］：
前記コントローラ装置は、また、
・ 前記接続手段を通じて前記デモンストレータ装置から来る前記応答 Ｄ を受け付ける手段
・ 前記コントローラ装置の計算手段と呼ばれる計算手段であって、この計算手段は、第１に、ｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有するとともに、各チャレンジｄと各応答 Ｄ から再構成されたコミットメント Ｒ ´を計算し、そのコミットメント Ｒ は
【数６３】
2004527139.tif 000188
のタイプの関係か、
【数６４】
2004527139.tif 000189
のタイプの関係を満たし、
第２に、前記メッセージ Ｍ および各再構成されたコミットメント Ｒ ´の全てまたは一部を変数として有する前記ハッシュ関数ｈを適用することによりトークン Ｔ ´を計算し、
・ トークン Ｔ ´を受け付けられたトークン Ｔ と比較する前記コントローラ装置の比較手段と呼ばれる比較手段
を備える。
【請求項１８】
署名されたメッセージと呼ばれているエンティティによって署名されたメッセージをチェックすることによってメッセージ Ｍ の真性性を証明するようにされている請求項１５に記載のコントローラ装置であって、
前記署名メッセージは、ハッシュ関数ｈ（ ｍｅｓｓａｇｅ，Ｒ ）を有するある署名エンティティに関連した署名装置によって送られるとともに、
・ 前記メッセージ Ｍ 、
・ 前記チャレンジｄおよび／またはコミットメント Ｒ 、
・ 前記応答 Ｄ 、
からなり、
［チェック動作］
前記コントローラ装置は、前記署名エンティティに関連した前記署名装置への、特にデータ処理通信ネットワークを通る電気的、電磁気的、光学的、あるいは音響による接続のための接続手段を含んでいて、該コントローラ装置が、前記署名装置から前記接続を通じて前記署名メッセージを受け取り、
前記コントローラ装置は、
・ 前記コントローラ装置の計算手段と呼ばれる計算手段、
・ 前記コントローラ装置の比較手段と呼ばれる比較手段、
を備え、
［場合前記コントローラ装置がコミットメント Ｒ 、チャレンジｄ、応答 Ｄ を有する場合］
場合前記コントローラ装置がコミットメント Ｒ， チャレンジｄ、応答 Ｄ を有する場合
．．前記コントローラ装置の前記計算手段および前記比較手段は、
前記コミットメント Ｒ 、前記チャレンジｄ、前記応答 Ｄ が
【数６５】
2004527139.tif 000190
のタイプか、
【数６６】
2004527139.tif 000191
のタイプの関係を満たすことを確認し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージ Ｍ， 前記チャレンジｄ、前記コミットメント Ｒ が前記ハッシュ関数
【数６７】
2004527139.tif 000192
を満たすことを確認する。
［前記コントローラ装置がチャレンジｄ、応答 Ｄ を有する場合］
前記コントローラ装置がチャレンジｄ、応答 Ｄ を有する場合、
．．前記コントローラ装置の前記計算手段は、各チャレンジｄと各レスポンス Ｄ に基づいて、
【数６８】
2004527139.tif 000193
のタイプか、
【数６９】
2004527139.tif 000194
のタイプの関係を満たすコミットメント Ｒ ´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージ Ｍ と前記チャレンジｄがハッシュ関数
【数７０】
2004527139.tif 000195
を満たすことを確認する。
［前記コントローラ装置がコミットメント Ｒ 、応答 Ｄ を有する場合］
前記コントローラ装置がコミットメント Ｒ 、応答 Ｄ を有する場合、
．．前記コントローラ装置の前記計算手段は、前記ハッシュ関数を適用して、
【数７１】
2004527139.tif 000196
のようなｄ´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記コミットメント Ｒ 、前記チャレンジｄ´、前記応答 Ｄ が
【数７２】
2004527139.tif 000197
のタイプの関係を満たすか、
【数７３】
2004527139.tif 000198
のタイプの関係を満たすことを確認する。
【発明の詳細な説明】
【０００１】
【発明が属する技術分野】
本発明は、エンティティや完全性の真性性やメッセージの真性性を証明するように設計されている方法、システム、装置に関する。
【０００２】
【従来の技術】
発明者がルイス Ｇｕｉｌｌｏｕ とジーン − ジャック Ｑｕｉｓｑｕａｔｅｒ である特許 ＥＰ   ０ の ３１１ の ４７０ の Ｂ１ は、そのような方法を記述する。
【０００３】
以下、「 ＧＱ 特許」または「 ＧＱ 方法」の語によって彼らの仕事を参照する。以下、「 Ｇ  Ｑ２ 」または「 ＧＱ２ 発明」、あるいは、「 ＧＱ２ 技術」の表現は本発明を指し示すのに用いられる。
【０００４】
ＧＱ 方法によると、「信頼されたオーソリティ（ ｔｒｕｓｔｅｄ   ａｕｔｈｏｒｉｔｙ ）」として知られているエンティティは、「証人（ ｗｉｔｎｅｓｓ ）」と呼ばれるアイデンティティを各々のエンティティへ割り当て、その ＲＳＡ 署名を計算する。カスタマイズしているプロセスでは、信頼されたオーソリティは、証人にアイデンティティと署名を与える。その後で、証人は「私のアイデンティティは、ここにある。私は、その ＲＳＡ 署名を知っている」と宣言する。証人は、彼がそれを明らかにすることなく彼のアイデンティティの ＲＳＡ 署名を知っているということを、証明する。信頼されたオーソリティによって配布される ＲＳＡ の公開識別鍵によって、その知識を得ることなく、「コントローラ」として知られているエンティティは、 ＲＳＡ 署名が宣言されたアイデンティティと一致することを確かめる。 ＧＱ 方法を使用しているメカニズムは、「知識の移動なしで」動く。 Ｇ  Ｑ 方法によれば、証人は信頼されたオーソリティが多数のアイデンティティに署名する Ｒ  ＳＡ 秘密鍵を知らない。
【０００５】
上で記述される ＧＱ 技術は、 ＲＳＡ 技術を利用する。しかし、 ＲＳＡ 技術が正にモジュロｎの因数分解に依存するのに対して、この依存は等価ではない、つまり、 ＲＳＡ 技術を実装しているディジタル署名のいろいろな標準に対する「増殖性の攻撃」と呼ばれていることにおいて見られることができるように、等価などとは全く言えない。
【０００６】
ＧＱ２ 技術の目的は、二つの面を有する： １ つには、 ＲＳＡ 技術の中のパフォーマンス特徴を改善するために、そしてもう １ つは、 ＲＳＡ 技術に固有の問題を避けるためである。 ＧＱ２ 秘密鍵についての知識は、モジュロｎの因数分解についての知識に等しい。トリプレット ＧＱ２ への任意の攻撃でも、モジュロｎの因数分解につながる：今度は、等価性がある。 ＧＱ２ 技術で、署名しているか自己真性性しているエンティティのために、そして、コントローラエンティティのために作業負荷は減らされる。セキュリティとパフォーマンスに関して因数分解する問題のより良い使用を通して、 ＧＱ２ 技術は、 ＲＳＡ 技術の欠点を避ける。
【０００７】
ＧＱ 方法は、 ５１２ ビット以上を含んでいる数のモジュロ計算を実行する。これらの計算は、かなり同じサイズを ２１６＋１ のオーダーのべき乗まで上げておいている数に関連がある。しかし、特にバンク・カードの分野では、既存のマイクロエレクトロニクスのインフラは、算数のコプロセッサなしでモノリシックの自己プログラム可能なマイクロプロセッサーを使用する。 ＧＱ 方法のような方法に関係している複数の算数のアプリケーションに関連した作業負荷は、特定のケースには、彼らの購入の料金を払うためにバンク・カードを使っている消費者にとって不利である計算時間となることがわかる、それは、支払いカードのセキュリティを増やそうとする際に、当局が持つ銀行業務が特に解が難しい問題を提起したことで思い出されるかもしれない。実際、 ２ つの明らかに矛盾している課題を調べなくてはならない： １ つは、各々のカードのためにますます長くてはつきりした鍵を用いて、もう １ つは、作業負荷がユーザーのための過度の計算時間に至るのを防ぐまで、セキュリティを増やす。それがまた、既存の基盤と既存のマイクロプロセッサー構成要素を考慮するのに必要であるので、この問題は特に明確になる。
【０００８】
本発明（ ＧＱ２ 技術）は、セキュリティを増やしつつ、はこの問題のソリューションを提供することを目的とする。
【０００９】
［方法］
より詳細には、本発明は、あるコントローラ・エンティティに対して、
・ あるエンティティの真性性、および／または、
・ 該エンティティと関連するメッセージ Ｍ の完全性
を証明するようにされている方法であって、以下のパラメータ：
・ 秘密の値 Ｑ１ 、 Ｑ２ 、 ．．．  、 Ｑｍ と公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、  Ｇｍ （ｍは １ 以上）の ｍ 個の組
・  ｆ 個の素因数 ｐ１ 、 ｐ２ 、 ．．．   ｐｆ の積で構成される公開のモジュラス ｎ （ ２ 以上の ｆ ）、
の全部若しくは一部またはこれらのパラメータからの算出値を用い、
前記モジュラスと前記秘密値と公開値は次のタイプの関係があり、
【数７４】
2004527139.tif 000002
ここで、ｖは
【数７５】
2004527139.tif 000003
のタイプの公開値である指数値を表し（ｋは１より大きいセキュリティパラメータ）；
前記ｍ個の公開値 Ｇｉ は、ｍ個の区別できるベース数 ｇ１ 、 ｇ２ 、… ｇｍ の、 ｆ 個の素因数 ｐ１ 、 ｐ２ 、… ｐｆ より小さい二乗値ｇ ｉ２ であり；
前記 ｐ１ 、 ｐ２ 、… ｐｆ の素因数、および／または、ｍ個のベース数 ｇ１ 、 ｇ２ 、… ｇｍ は以下の条件が満たされるように生成される方法。：
【００１０】
［第１の条件］
第１の条件は、各方程式
【数７６】
2004527139.tif 000004
がモジュロｎの整数環におけるｘについて解をもつこと；
【００１１】
［第２の条件］
Ｇｉ（Ｑｉｖ   ｍｏｄ   ｎ である場合には、第 ２ の条件は、 Ｑｉ を二乗してモジュロ ｎ を ｋ  −１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）。
Ｇｉ．Ｑｉｖ   （ １ ｍｏｄ   ｎ である場合には、第 ２ の条件は、 Ｑｉ のモジュロｎを二乗したものの逆モジュロ ｎ を ｋ−１ 回とって得られるｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）。；
ここでの表記によれば、± ｇｉ が数 ｇｉ と ｎ−ｇｉ を表現するものであることをここで指摘しておく。
【００１２】
［第３の条件］
第 ３ の条件は、２ｍ個の方程式
【数７７】
2004527139.tif 000005
がモジュロｎの整数環におけるｘについて分解され、
前記方法は、 ｆ 個の素因数 ｐｉ を持っている証人と呼ばれているエンティティ、および／または、ベース ｇｉ のｍ個の素因数、および／または、前記素因数のチャイニーズ・剰余法のパラメータ、および／または、公開モジュラス ｎ 、および／または、ｍ個の秘密値 Ｑ  ｉ 、および／または、前記秘密値 Ｑｉ と公開の指数値ｖとの ｆ．ｍ 個の構成要素 Ｑｉ，ｊ （ Ｑｉ，ｊ   （   Ｑｉ   ｍｏｄ   ｐｊ ）を以下のステップによって実現する。
・ 前記証人が、モジュロ ｎ の整数環において、コミットメント Ｒ を計算し ；
それぞれのコミットメントは、
【数７８】
2004527139.tif 000006
のタイプの演算（ここで、ｒは０＜ｒ＜ｎである乱数値）を実行するか、
あるいは、
【数７９】
2004527139.tif 000007
のタイプの演算（ここで、ｒ ｉ は０＜ ｒｉ ＜ ｐｉ である素因数 ｐｉ に関連した乱数値、それぞれの ｒｉ は乱数値の集合｛ ｒ１，ｒ２， … ｒｆ ｝に含まれている）を実行し、さらに、チャイニーズ・剰余法手法を適用する
ことからなるステップ、
・証人は一つ以上のチャレンジ ｄ を受け、それぞれのチャレンジｄはｍ個の整数 ｄｉ （以下「要素チャレンジ」と呼ぶ）からなり ； 各々のチャレンジ ｄ に基づいて、前記証人は
【数８０】
2004527139.tif 000008
のタイプの演算を行なうことによって応答 Ｄ を計算するか、
【数８１】
2004527139.tif 000009
のタイプの演算を行なって、さらに、チャイニーズ・剰余法手法を適用するステップ（前記手法はチャレンジｄ、コミットメント Ｒ と同じくらいの数の応答 Ｄ があって、 Ｒ， ｄ、 Ｄ の数の群は｛ Ｒ 、 ｄ 、 Ｄ ｝で参照される３つの数字の組で表される）。
【００１３】
［エンティティの真性性の証明の場合］
実施の形態の最初の変形において、本発明の方法はコントローラとして知られるエンティティに対して、デモンストレータとして知られるエンティティの真性性の証明のために用いられる。
【００１４】
・ステップ１（コミットメント Ｒ の行為）
各々の呼び出しで、証人は請求項 １ によって指定されるプロセスを適用することによって各々のコミットメント Ｒ を計算し、
デモンストレータは、各々のコミットメント Ｒ のコントローラ全部または一部を送り、
【００１５】
・ステップ ２ （チャレンジ ｄ の行為）
各々のコミットメント Ｒ の全部または一部を受けた後にチャレンジ ｄ を生成し、コントローラは数がコミットメント Ｒ の数と等しいチャレンジ ｄ をデモンストレータに送り、
【００１６】
・ステップ ３ （応答 Ｄ の行為）
前記証人は、上に指定されるプロセスを適用することによってチャレンジ ｄ から応答 Ｄ を計算し、
【００１７】
・ステップ ４ （チェックする行為）
前記デモンストレータは、前記コントローラへ各々の応答 Ｄ を送り、
【００１８】
［第 １ のケース：前記デモンストレータがコミットメント Ｒ の一部だけを送信するとき］
前記デモンストレータがコミットメント Ｒ の一部だけを送信したなら、前記コントローラはｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有していて、それぞれのチャレンジｄとそれぞれの応答 Ｄ から、再構成されたコミットメント Ｒ ´を計算し、該再構成されたコミットメント Ｒ ´は
【数８２】
2004527139.tif 000010
のタイプか、または
【数８３】
2004527139.tif 000011
のタイプの関係を満たすとともに、前記コントローラは、それぞれの再構成されたコミットメント Ｒ ´はコントローラに向けて伝達されたそれぞれのコミットメント Ｒ の全てまたは一部を再生成することを確認する。
【００１９】
［第２のケース：前記デモンストレータがコミットメント Ｒ の全部を送信するとき］
前記デモンストレータがコミットメント Ｒ の全部を送信したなら、前記コントローラはｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有していて、それぞれのコミットメント Ｒ は
【数８４】
2004527139.tif 000012
のタイプか、または
【数８５】
2004527139.tif 000013
のタイプの関係を満たすことを確認する。
【００２０】
［メッセージの完全性の証明のケース］
最初のものと組み合わせられることができる第二の異なる実施形態は、デモンストレータエンティティと呼ばれるエンティティに関連したメッセージ Ｍ の完全性について、コントローラエンティティとして知られるエンティティに証明を提供するようにされた本発明に記載の方法であって、
前記デモンストレータエンティティは前記証人を含み、
前記デモンストレータエンティティとコントローラエンティティは以下のステップを実行する方法：
【００２１】
・ステップ １ （コミットメント Ｒ の行為）
各々の呼び出しで、証人は上述のように指定されるプロセスを適用することによって各々のコミットメント Ｒ を計算し、
デモンストレータは、各々のコミットメント Ｒ のコントローラ全部または一部を送り、
【００２２】
・ステップ ２ （チャレンジ ｄ の行為）
前記デモンストレータは、変数をメッセージ Ｍ とそれぞれのコミットメント Ｒ の全てまたは一部とするハッシュ関数ｈを適用し、
前記デモンストレータはトークン Ｔ を前記コントローラに送り、
前記コントローラは、前記トークン Ｔ を受け付けると、コミットメント Ｒ と同じ数のチャレンジｄを生成して該チャレンジｄを前記デモンストレータに送り、
【００２３】
・ステップ ３ （応答 Ｄ の行為）
− 前記証人は、上述のように指定されるプロセスを適用することによってチャレンジ ｄ から応答 Ｄ を計算し、
【００２４】
・ステップ ４ （チェックする行為）
・ 前記デモンストレータは、前記コントローラへ各々の応答 Ｄ を送り、
・ 前記デモンストレータがコミットメント Ｒ の一部だけを送信したなら、前記コントローラはｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有していて、それぞれのチャレンジｄとそれぞれの応答 Ｄ から、再構成されたコミットメント Ｒ ´を計算し、該再構成されたコミットメント Ｒ ´は
【数８６】
2004527139.tif 000014
のタイプか、または
【数８７】
2004527139.tif 000015
のタイプの関係を満たし、
・ そして前記コントローラは、前記メッセージ Ｍ とそれぞれの再構成されたコミットメント Ｒ ´のすべてまたは一部とを変数とするハッシュ関数ｈを適用してトークン Ｔ ´を再構成し、
・ そして前記コントローラは前記トークン Ｔ ´が伝達されたトークン Ｔ と同一であることを確認する。
【００２５】
［メッセージのデジタル署名とその真性性の証明］
本発明の実施形態の第３の変形は、既述の２つの実施形態と組み合わせることができるものであって、署名エンティティとして知られたエンティティによってメッセージ Ｍ のディジタル署名を生成するようにするようにされた本発明の方法であって、
【００２６】
（署名動作）
前記署名エンティティは、
・ 前記メッセージ Ｍ 、
・ 前記チャレンジｄおよび／またはコミットメント Ｒ 、
・ 前記応答 Ｄ 、
を備えた署名されたメッセージを得るために署名動作を行ない、
前記署名エンティティは次のステップを行なって署名動作を行なう方法：
【００２７】
・ステップ １ （コミットメント Ｒ の行為）
各々の呼び出しで、前記証人は上述のように指定されるプロセスを適用することによって各々のコミットメント Ｒ を計算し、
【００２８】
・ステップ ２ （チャレンジ ｄ の行為）
前記署名エンティティは、変数をメッセージ Ｍ とそれぞれのコミットメント Ｒ のとするハッシュ関数ｈを適用してバイナリトレインを得て、該バイナリトレインから前記署名エンティティは、コミットメント Ｒ と同じ数のチャレンジｄを引き出し、
【００２９】
・ステップ ３ （応答 Ｄ の行為）
前記証人は、上述のように指定されるプロセスを適用することによってチャレンジ ｄ から応答 Ｄ を計算する。
【００３０】
［チェック動作］
メッセージ Ｍ の真性性を証明するために、コントローラと呼ばれているエンティティが署名されたメッセージをチェックする。そのコントローラエンティティは、以下のようなプロセスを行ってチェック動作実行する：
【００３１】
［前記コントローラがコミットメント Ｒ 、チャレンジ ｄ 、応答 Ｄ を持つケース］
コントローラがコミットメント Ｒ 、チャレンジ ｄ 、応答 Ｄ を持つ場合、前記コントローラは、前記コミットメント Ｒ 、前記チャレンジｄ、前記応答 Ｄ が
【数８８】
2004527139.tif 000016
のタイプか、または、
【数８９】
2004527139.tif 000017
のタイプの関係を満たすことを確認する。
そして、前記コントローラは前記メッセージ Ｍ 、前記チャレンジｄ、前記コミットメント Ｒ が前記ハッシュ関数
【数９０】
2004527139.tif 000018
を満たすことを確認する。
【００３２】
［前記コントローラはチャレンジｄと応答 Ｄ を有する場合］
前記コントローラはチャレンジｄと応答 Ｄ を有する場合、前記コントローラは、それぞれのチャレンジｄと応答 Ｄ に基づいて、
【数９１】
2004527139.tif 000019
のタイプの関係か、または、
【数９２】
2004527139.tif 000020
のタイプの関係を満たすコミットメント Ｒ ´を再構成する。
そして、前記コントローラは前記メッセージ Ｍ と前記チャレンジｄが前記ハッシュ関数
【数９３】
2004527139.tif 000021
を満たすことを確認する。
【００３３】
［前記コントローラはコミットメント Ｒ と応答 Ｄ を有する場合］
前記コントローラはコミットメント Ｒ と応答 Ｄ を有する場合、前記コントローラは前記ハッシュ関数を適用してｄ´を再構成する。
【数９４】
2004527139.tif 000022
そして、前記コンとローラは、前記コミットメント Ｒ 、前記チャレンジｄ´、前記応答 Ｄ が
【数９５】
2004527139.tif 000023
のタイプの関係か、または、
【数９６】
2004527139.tif 000024
のタイプの関係を満たすことを確認する。
【００３４】
［システム］
本発明は、コントローラ・サーバーに対して、
・ エンティティの真性性、および／または
・ 該エンティティと関連するメッセージ Ｍ の完全性、
を証明するようにされたシステムにもまた関連している。この証明は、
・ 秘密の値 Ｑ１ 、 Ｑ２ 、 ．．．  、 Ｑｍ と公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ （ｍは １ 以上）の ｍ 個の組、
・  ｆ 個の素因数 ｐ１ 、 ｐ２ 、 ．．．   ｐｆ の積で構成される公開のモジュラス ｎ （ｆは ２ 以上）、
の全てあるいは部分以下のパラメータやそれらパラメータからの算出値を用いている。
【００３５】
前記モジュラスと前記秘密値と公開値は以下のタイプの関係があり、：
【数９７】
2004527139.tif 000025
ここで、ｖは
【数９８】
2004527139.tif 000026
の形式の公開の指数値 ｃを表し、ｋは１より大きいセキュリティパラメータであり、
前記ｍ個の公開の値 Ｇｉ は、ｆ個の素因数 ｐ１，ｐ２， … ，ｐｆ より小さいｍ個の区別できるベース数 ｇ１，ｇ２， … ，ｇｍ による ｇｉ２ となる２乗値であり、
前記素因数 ｐ１，ｐ２， … ，ｐｆ および／または前記ｍ個のベース数 ｇ１，ｇ２， … ，ｇ  ｍ は以下の条件が満たされるように生成されているシステム：
【００３６】
［第１の条件］
第 １ の条件によれば、方程式
【数９９】
2004527139.tif 000027
がｘについてモジュロｎの整数環において解をもつこと；
【００３７】
［第２の条件］
Ｇｉ（Ｑｉｖ   ｍｏｄ   ｎ である場合、第２の条件は、 Ｑｉ を二乗してモジュロ ｎ を ｋ−１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）である。
Ｇｉ．Ｑｉｖ   （ １ ｍｏｄ   ｎ である場合、第２の条件はば、 Ｑｉ のモジュロｎを二乗したものの逆モジュロ ｎ を ｋ−１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）である。
ここでの表記によれば、± ｇｉ が数 ｇｉ と ｎ−ｇｉ を表現するものであることをここで指摘しておく。
【００３８】
［第３の条件］
第３の条件は、少なくとも２ｍ個の方程式
【数１００】
2004527139.tif 000028
がモジュロｎの整数環におけるｘについて解を持つことである。
前記システムは、例えばマイクロプロセッサベースのバンクカードの形態をとるようなノマドオブジェクト証人装置である。
その証人装置は前記ｆ個の素数 ｐｉ、 および／または、前記ｍ個のベース ｇｉ 、および／または、前記素因数のチャイニーズ剰余のパラメータ、および／または、秘密の値 Ｑｉ  および公開の指数値ｖの ｆ．ｍ 個の成分 Ｑｉ，ｊ （ Ｑｉ，ｊ   （   Ｑｉ   ｍｏｄ   ｐｊ ）を含むメモリゾーンからなる。
前記証人装置は、
・ 前記証人装置の乱数値生成手段と呼ぶ乱数値生成手段、
・ 前記証人装置のコミットメント Ｒ の計算手段と呼ぶ計算手段
からなる。
前記計算手段は、モジュロｎの整数環においてコミットメント Ｒ の計算を行い、各コミットメント Ｒ は、
・ｒがｒが０＜ｒ＜ｎである前記乱数値生成手段による乱数値として、
【数１０１】
2004527139.tif 000029
のタイプの演算を行なうか、
ｒ ｉ が、０＜ｒ ｉ ＜ｐ ｉ で、それぞれ、前記乱数生成手段によって生成され、各ｒ Ｉ はチャイニーズ剰余法を適用することによって得られるランダム値の集合 ［ｒ１，ｒ２， … ，  ｒｆ］ に属する、素因数 ｐｉ に関連した乱数値であるとして、
【数１０２】
2004527139.tif 000030
のタイプの演算を行なうか、
によって計算される。
【００３９】
前記証人装置は、また、
・ 前記証人で装置のチャレンジｄを受け付け、それぞれのチャレンジｄがｍ個の整数 ｄ  ｉ （以下、要素チャレンジとよぶ）からなる １ 以上のチャレンジｄを受け付ける受け付け手段、
・ それぞれのチャレンジｄに基づいて、前記証人装置の応答 Ｄ を計算し、
・方程式
【数１０３】
2004527139.tif 000031
のタイプの演算を行なうこと、あるいは、
・方程式
【数１０４】
2004527139.tif 000032
のタイプの演算をおこなって、そして、チャイニーズ剰余法を適用することのいずれかにより応答 Ｄ を計算する計算手段、
からなる。
【００４０】
前記証人手段は、また、
・ １以上のコミットメント Ｒ と１以上の応答 Ｄ を伝送する伝送手段、
を備えている（前記手法はチャレンジｄ、コミットメント Ｒ と同じくらいの数の応答 Ｄ があって、 Ｒ， ｄ、 Ｄ の数の群は｛ Ｒ 、 ｄ 、 Ｄ ｝で参照される３つの数字の組で表される）。
【００４１】
［あるエントリの真性性の証明ケース］
実施形態の第１の変形によれば、本発明のシステムは、デモンストレータと呼ばれているエンティティとコントローラと呼ばれているエンティティの真性性を証明するようにできている。
【００４２】
前記システムは、前記デモンストレータエンティテイに関連し、前記相互接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができるデモンストレータ装置からなる。、
【００４３】
前記システムは、また、前記コントローラエンティティと関連するコントローラ装置であって、前記コントローラ装置は特に端末であるか遠隔サーバーの形になっていて、特にデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響によるデモンストレータ装置への接続のために、接続手段を含んでいる前記コントローラ装置からなる。
【００４４】
前記システムは、以下のステップの実行を可能にしている前記システム：
・ステップ １ （コミットメント Ｒ の行為）
各々の呼び出しで、上述のように指定されるプロセスを適用することによって証人装置のコミットメント Ｒ の計算手段が各コミットメント Ｒ を計算する。該証人手段は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有する。前記デモンストレータ装置は、また、コミットメント Ｒ の全てはまた一部を前記コントローラ装置に前記相互接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有する。
【００４５】
・ステップ２（チャレンジｄの行為）
前記コントローラ装置は、前記コミットメント Ｒ の全部または一部を受け取った後に、それぞれの数がコミットメント Ｒ と同じチャレンジ ｄ を生成する、チャレンジ生成手段を含む。前記コントローラ装置は、また、接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を含む。
【００４６】
・ステップ３（応答 Ｄ の行為）
前記証人装置の前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれそれのチャレンジｄを受け取る。前記証人装置の前記応答 Ｄ の前記計算手段は、上述のようなプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算する。
【００４７】
・ステップ４（チェックの行為）
前記デモンストレータの前記伝送手段はそれぞれの応答 Ｄ を前記コントローラへ伝送し、前記コントローラは、また、
・ 前記コントローラ装置の計算手段と呼ばれる計算手段、
・ 前記コントローラ装置の比較手段とよばれる比較手段、
からなる。
【００４８】
［第１のケース：前記デモンストレータが各コミットメント Ｒ の一部を伝送した場合］
前記デモンストレータが各コミットメント Ｒ の一部を伝送した場合には、
ｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有する前記コントローラ装置の前記計算手段は、各チャレンジ Ｒ と各応答 Ｄ から再構成されたコミットメント Ｒ ´を計算し、その再構成されたコミットメント Ｒ ´は
【数１０５】
2004527139.tif 000033
のタイプの関係か、
【数１０６】
2004527139.tif 000034
のタイプの関係を満たす。
【００４９】
［第２のケース：前記デモンストレータが各コミットメント Ｒ の全部を伝送した場合］
前記デモンストレータが各コミットメント Ｒ の全部を伝送した場合には、ｍ個の公開値 Ｇ  １ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有する前記コントローラ装置の前記計算手段と前記比較手段は、各チャレンジ Ｒ が
【数１０７】
2004527139.tif 000035
のタイプの関係か、
【数１０８】
2004527139.tif 000036
のタイプの関係を満たすことを確認する。
【００５０】
［メッセージの完全性の証明の場合］
第１の変形と組み合わせることができる実施形態の第２の変形においては、本発明のシステムは、コントローラとして知られたあるエンティティに、デモンストレータとして知られたエンティティに関連したメッセージ Ｍ についての完全性の証明を与えるようにされたシステムである。前記システムは、前記デモンストレータエンティテイに関連したデモンストレータ装置を含むようなものである。該デモンストレータは、前記相互接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができる。前記コントローラは、前記コントローラエンティティと関連するコントローラ装置である。前記コントローラ装置は、特に端末であるか遠隔サーバーの形になっていて、特にデモンストレータ装置へのデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響による接続のために、接続手段を含んでいる。
前記システムは、以下のステップの実行を可能にしている：
【００５１】
・ステップ １ （コミットメント Ｒ の行為）
証人装置のコミットメント Ｒ の計算手段が、各々の呼び出しで、上述のように指定されるプロセスを適用することによって各コミットメント Ｒ を計算する。該証人手段は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有する。
【００５２】
・ステップ２（チャレンジｄの行為）
前記デモンストレータ装置は、少なくともあるトークン Ｔ の計算に、変数を前記メッセージおよび各コミットメント Ｒ の全部または一部とするハッシュ関数ｈを適用する、前記デモンストレータの計算手段と呼ばれる計算手段からなる。前記デモンストレータ装置は、また、各トークン Ｔ を前記コントローラ装置に前記接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有する。前記コントローラ装置は、また、前記トークンを受け取った後で、コミットメント Ｒ の数と同じ数の前記チャレンジｄを生成するチャレンジ生成手段を有する。前記コントローラ装置は、また、接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を有する。
【００５３】
・ステップ３（応答 Ｄ の行為）
前記証人装置の前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれそれのチャレンジｄを受け取る。前記証人装置の前記応答 Ｄ の前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算する。
【００５４】
・ステップ４（チェックの行為）
前記デモンストレータの前記伝送手段は、それぞれの応答 Ｄ を前記コントローラへ伝送する。前記コントローラは、また、前記コントローラ装置の計算手段と呼ばれる計算計算手段を有し、この計算手段は、ｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有するとともに、第１に、各チャレンジｄと各応答 Ｄ から再構成されたコミットメント Ｒ ´を計算し、この再構成されたコミットメント Ｒ ´は
【数１０９】
2004527139.tif 000037
のタイプの関係か、
【数１１０】
2004527139.tif 000038
のタイプの関係を満たし、
そして、第２に、前記メッセージ Ｍ および各再構成されたコミットメント Ｒ ´の全てまたは一部を変数として有する前記ハッシュ関数ｈを適用することによりトークン Ｔ ´を計算する。
【００５５】
前記コントローラ装置は、また、受け付けられたトークン Ｔ について前記トークン Ｔ ´を計算する、前記コントローラ装置の比較手段として知られている比較手段を有する。
【００５６】
［メッセージのディジタル署名とその真性性の証明］
先の２つの実施形態のいずれか、および／または、他のものと組み合わせることができる、本発明による実施の形態の第３の変形においては、署名エンティティと呼ばれるエンティティによって、署名されたメッセージとして知られているメッセージ Ｍ のディジタル署名を生成するようにするようにされ、前記署名されたメッセージは、
・ 前記メッセージ Ｍ 、
・ 前記チャレンジ ｄ 、および／または、前記コミットメント Ｒ 、
・ 前記応答 Ｄ；
を含んでいるような、システムである。
【００５７】
・署名動作：
前記システムは、前記署名エンティティに関連している署名装置からなるようなものであり、前記署名装置は、前記証人装置に、相互接続手段で相互接続されていて、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができる。
前記システムは、以下のステップの実行を可能にする：
【００５８】
・ステップ １ （コミットメント Ｒ の行為）：
各々の呼び出しで、上述のように指定されるプロセスを適用することによって証人装置のコミットメント Ｒ の計算手段が各コミットメント Ｒ を計算しする。該証人手段は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有する。
【００５９】
・ステップ２（チャレンジｄの行為）：
前記署名装置は、変数を前記メッセージおよび各コミットメント Ｒ の全部または一部とするハッシュ関数ｈを適用し、あるバイナリトレインを計算し、このバイナリトレインからコミットメント Ｒ と同じ数のチャレンジｄを導出する前記署名装置の計算手段と呼ばれる該計算手段を有する。
【００６０】
・ステップ３（応答 Ｄ の行為）：
前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれそれのチャレンジｄを受け取り、前記証人装置の前記応答 Ｄ の前記計算手段は、上述のようなプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算する。前記証人装置は、前記証人装置の伝達装置と呼ばれ、前記相互接続手段を通して前記署名装置へと前記応答 Ｄ を伝達させる、伝達装置からなる。
【００６１】
［チェック動作］
前記メッセージ Ｍ の真性性を証明するために、コントローラとして知られているエンティティは、前記署名されたメッセージをチェックする。
前記システムは、コントローラエンティティに関連したコントローラ装置からなるようになっている。前記コントローラ装置は、特に端末であるか遠隔サーバーの形になっていて、特に前記署名装置へのデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響による接続のために、接続手段を含んでいる。
【００６２】
前記署名装置は、署名装置の伝送手段として知られていて、前記接続装置を通じて、前記署名されたメッセージの前記コントローラ装置への伝送手段からなる前記署名エンティティに関連している。こうして、前記コントローラ装置は、
・ 前記メッセージ Ｍ 、
・ 前記チャレンジｄ、および／または、前記コミットメント Ｒ 、
・ 前記応答 Ｄ 、
を含む署名されたメッセージからなる。
前記コントローラ装置は、
・ 前記コントローラ装置の計算手段と呼ばれる計算手段、
・ 前記コントローラ装置の比較手段と呼ばれる比較手段、
からなる。
【００６３】
・場合前記コントローラ装置がコミットメント Ｒ 、チャレンジｄ、応答 Ｄ を有する場合：
場合前記コントローラ装置がコミットメント Ｒ， チャレンジｄ、応答 Ｄ を有する場合、前記コントローラ装置の前記計算手段および前記比較手段は、前記コミットメント Ｒ 、前記チャレンジｄ、前記応答 Ｄ が
【数１１１】
2004527139.tif 000039
のタイプか、
【数１１２】
2004527139.tif 000040
のタイプの関係を満たすことを確認する。
そして、前記コントローラ装置の前記計算手段と前記比較手段は、前記メッセージ Ｍ， 前記チャレンジｄ、前記コミットメント Ｒ が前記ハッシュ関数：
【数１１３】
2004527139.tif 000041
を満たすことを確認する。
【００６４】
・前記コントローラ装置がチャレンジｄ、応答 Ｄ を有する場合：
前記コントローラ装置がチャレンジｄ、応答 Ｄ を有する場合、前記コントローラ装置の前記計算手段は、各チャレンジｄと各レスポンス Ｄ に基づいて、
【数１１４】
2004527139.tif 000042
のタイプか、
【数１１５】
2004527139.tif 000043
のタイプの関係を満たすコミットメント Ｒ ´を計算する。
そして、前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージ Ｍ と前記チャレンジｄがハッシュ関数
【数１１６】
2004527139.tif 000044
を満たすことを確認する。
【００６５】
・前記コントローラ装置がコミットメント Ｒ 、応答 Ｄ を有する場合：
前記コントローラ装置がコミットメント Ｒ 、応答 Ｄ を有する場合、前記コントローラ装置の前記計算手段は、前記ハッシュ関数を適用して、
【数１１７】
2004527139.tif 000045
のようなｄ´を計算する。
そして、前記コントローラ装置の前記計算手段と前記比較手段は前記コミットメント Ｒ 、前記チャレンジｄ´、前記応答 Ｄ が
【数１１８】
2004527139.tif 000046
のタイプの関係を満たすか、
【数１１９】
2004527139.tif 000047
のタイプの関係を満たすことを確認する。
【００６６】
［端末装置］
本発明は、また、あるエンティティに関連したある端末装置に関係する。その端末装置は、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のようなノマドオブジェクトにおける微小論理回路の形態を特にとることができる。前記端末装置は、コントローラ装置に対して
・ あるエンティティの前記真性性、および／または、
・ 該エンティティに関連したあるメッセージ Ｍ の完全性、
を証明するようにされている。
この用命は、パラメータ：
秘密の値 Ｑ１ 、 Ｑ２ 、 ．．．  、 Ｑｍ と公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ （ｍは １ 以上）の ｍ 個の組、
ｆ 個の素因数 ｐ１ 、 ｐ２ 、 ．．．   ｐｆ の積で構成される公開のモジュラス ｎ （ ２ 以上の ｆ ）、
や、これらのパラメータからの算出値の全部または一部を用いるようにされている。
【００６７】
前記モジュラスと前記秘密値と公開値は
【数１２０】
2004527139.tif 000048
のタイプの関係があり、ここで、ｖは
【数１２１】
2004527139.tif 000049
の形態の公開値である指数値を表す（ｋは１より大きいセキュリティパラメータ）。
前記ｍ個の公開値 Ｇｉ は、ｍ個の異なったベース数 ｇ１ 、 ｇ２ 、… ｇｍ の、 ｆ 個の素因数 ｐ１ 、 ｐ２ 、… ｐｆ より小さい二乗値ｇ ｉ２ であり；前記 ｐ１ 、 ｐ２ 、… ｐｆ の素因数、および／または、ｍ個のベース数 ｇ１ 、 ｇ２ 、… ｇｍ は以下の条件が満たされる。
【００６８】
・第１の条件：
第１の条件は、各方程式
【数１２２】
2004527139.tif 000050
がモジュロｎの整数環におけるｘについて解を持つこと。
【００６９】
・第２の条件：
Ｇｉ（Ｑｉｖ   ｍｏｄ   ｎ である場合、第２の条件は、 Ｑｉ を二乗してモジュロ ｎ を ｋ−１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）。
Ｇｉ．Ｑｉｖ   （ １ ｍｏｄ   ｎ である場合、第２の条件は、 Ｑｉ のモジュロｎを二乗したものの逆モジュロ ｎ を ｋ−１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）。
【００７０】
・第３の条件：
第３の条件は、２ｍ個の方程式
【数１２３】
2004527139.tif 000051
がモジュロｎの整数環におけるｘについて解をもつこと。
前記端末装置は、前記ｆ個の素因数 ｐｉ 、および／または、ベース ｇｉ のｍ個の素因数、および／または、前記素因数のチャイニーズ・剰余法のパラメータ、および／または、公開モジュラス ｎ 、および／または、ｍ個の秘密値 Ｑｉ 、および／または、前記秘密値 Ｑｉ と公開の指数値ｖとの ｆ．ｍ 個の構成要素 Ｑｉ，ｊ （ Ｑｉ，ｊ   （   Ｑｉ   ｍｏｄ   ｐｊ ）を含むメモリゾーンを備える証人装置を有する。
前記証人装置は、また、
・ 前記証人装置の乱数値生成手段と呼ぶ乱数値生成手段；
・ 前記証人装置のコミットメント Ｒ の計算手段と呼ぶ計算手段であって、モジュロｎの整数環においてコミットメント Ｒ の計算を行う計算手段
を備える。
【００７１】
各コミットメント Ｒ は、
・ｒは、ｒが０＜ｒ＜ｎである前記乱数値生成手段による乱数値としたとき、
【数１２４】
2004527139.tif 000052
のタイプの演算を行なうか、
・ｒ Ｉ が０＜ｒ ｉ ＜ｐ ｉ で、それぞれ、前記乱数生成手段によって生成されて、チャイニーズ剰余法を適用することによって得られるランダム値の集合 ［ｒ１，ｒ２  ， … ，ｒｆ］ に属する、素因数 ｐｉ に関連した乱数値であるとしたとき、
【数１２５】
2004527139.tif 000053
のタイプの演算を行なうか、
によって計算される。
【００７２】
前記証人装置は、また、
・ 前記証人で装置のチャレンジｄを受け付け、それぞれのチャレンジｄがｍ個の整数 ｄ  ｉ （以下、要素チャレンジとよぶ）からなる １ 以上のチャレンジｄを受け付ける受け付け手段、
・ それぞれのチャレンジｄに基づいて、前記証人装置の応答 Ｄ を計算し、
・方程式
【数１２６】
2004527139.tif 000054
のタイプの演算を行なうこと、あるいは、
・方程式
【数１２７】
2004527139.tif 000055
のタイプの演算をおこなって、そして、チャイニーズ剰余法を適用すること、
のいずれかにより応答 Ｄ を計算する計算手段を備えている。
【００７３】
前記証人装置は、また、１以上のコミットメント Ｒ と１以上の応答 Ｄ を伝送する伝送手段を備えている。前記手法はチャレンジｄ、コミットメント Ｒ と同じくらいの数の応答 Ｄ があって、 Ｒ， ｄ、 Ｄ の数の群は｛ Ｒ 、 ｄ 、 Ｄ ｝で参照される３つの数字の組で表される。
【００７４】
［エンティティの真性性の証明のケース］
実施形態の第１の変形において、本発明の前記端末装置は、デモンストレータと呼ばれているエンティティとコントローラと呼ばれているエンティティの真性性を証明するようにされている。
【００７５】
前記端末装置は、前記デモンストレータエンティテイに関連しているデモンストレータ装置を含む。前記デモンストレータ装置は、前記接続装置によって前記証人装置に相互接続されている。それは、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができる。
【００７６】
前記デモンストレータ装置は、また、前記コントローラエンティティと関連していて、特に端末であるか遠隔サーバーの形になっている前記コントローラ装置へと、特にデモンストレータ装置へのデータ処理通信ネットワークを通じて、それ自身、電気的、電磁気的、光学的、あるいは音響によって接続するための接続手段を、含んでいる。
【００７７】
前記端末装置は、以下のステップの実行を可能にしている：
・ステップ １ （コミットメント Ｒ の行為）：
各々の呼び出しで、上述のように指定されるプロセスを適用することによって証人装置のコミットメント Ｒ の計算手段が各コミットメント Ｒ を計算する。
該証人装置は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有する。前記デモンストレータ装置は、また、コミットメント Ｒ の全てはまた一部を前記コントローラ装置に前記接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有する。
【００７８】
・ステップ２および３（チャレンジｄの行為、応答 Ｄ の行為）：
前記証人装置の前記チャレンジｄの受け取り手段は、前記コントローラ装置と前記デモンストレータ装置の間の前記接続装置を通して、また、前記デモンストレータ装置と前記証人装置の間の前記相互接続装置を通して、前記コントローラ装置から来るそれそれのチャレンジｄを受け取る。前記証人装置の前記応答 Ｄ の前記計算手段は、上述のようなプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算する。
【００７９】
・ステップ４（チェックの行為）：
前記デモンストレータの前記伝送手段はそれぞれの応答 Ｄ をチェックを行なう前記コントローラへ伝送する。
【００８０】
［メッセージの完全性の証明の場合］
第１の実施の形態と組み合わせることができる、実施形態の第２の変形において、本発明の端末装置は、コントローラとして知られたあるエンティティに、デモンストレータとして知られたエンティティに関連したメッセージ Ｍ についての完全性の証明を与えるようにされている。前記端末装置は、前記デモンストレータエンティテイに関連し、前記相互接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができるデモンストレータ装置、を備えるようなものである。前記デモンストレータ装置は、前記コントローラエンティティと関連していて、特に端末であるか遠隔サーバーの形になっている前記コントローラ装置へと、特にデモンストレータ装置へのデータ処理通信ネットワークを通じて、それ自身、電気的、電磁気的、光学的、あるいは音響によって接続するための接続手段をまた含んでいる。
【００８１】
・ステップ １ （コミットメント Ｒ の行為）：
各々の呼び出しで、上述のように指定されるプロセスを適用することによって証人装置のコミットメント Ｒ の計算手段が各コミットメント Ｒ を計算する。該証人手段は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有する。
【００８２】
・ステップ２および３（チャレンジｄの行為、応答 Ｄ の行為）：
前記デモンストレータ装置は、少なくともあるトークン Ｔ の計算に、変数を前記メッセージおよび各コミットメント Ｒ の全部または一部とするハッシュ関数ｈを適用する、前記デモンストレータの計算手段と呼ばれる計算手段からなる。前記デモンストレータ装置は、また、各トークン Ｔ を前記コントローラ装置に前記接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有する。
前記コントローラ装置は、前記トークン Ｔ を受け取った後、コミットメント Ｒ の数と同じ数のチャレンジｄを生成しする。
前記証人装置の前記チャレンジｄの受け取り手段は、前記コントローラ装置と前記デモンストレータ装置の間の前記相互接続装置を通して、また、前記デモンストレータ装置と前記証人装置の間の前記相互接続装置を通して、前記コントローラ装置から来るそれそれのチャレンジｄを受け取る。
【００８３】
前記証人装置の前記応答 Ｄ の前記計算手段は、上述のようなプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算する。
【００８４】
・ステップ４（チェックの行為）：
前記デモンストレータの前記伝送手段は、それぞれの応答 Ｄ をチェックを行なう前記コントローラへ伝送する。
【００８５】
［メッセージのディジタル署名とその真性性の証明］
先の二つの実施形態のいずれかに組み合わせることができる第３の実施形態の変形において、本発明の前記端末装置は、署名エンティティと呼ばれるエンティティによって、署名されたメッセージとして知られているメッセージ Ｍ のディジタル署名を生成するようにするようにされている。
前記署名されたメッセージは、
・ 前記メッセージ Ｍ 、
・ 前記チャレンジ ｄ 、および／または、前記コミットメント Ｒ 、
・ 前記応答 Ｄ；
を含んでいる。
【００８６】
前記端末装置は、前記署名エンティティに関連している署名装置からなるようなものであり、前記署名装置は、前記証人装置に、相互接続手段で相互接続されていて、例えばマイクロプロセッサベースのバンクカード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができる。前記署名装置は、また、前記コントローラエンティティと関連していて、特に端末であるか遠隔サーバーの形になっている前記コントローラ装置へと、特にデモンストレータ装置へのデータ処理通信ネットワークを通じて、それ自身、電気的、電磁気的、光学的、あるいは音響によって接続するための接続手段を含んでいる。
【００８７】
・署名動作：
前記端末装置は、以下のステップの実行をする：
・ステップ １ （コミットメント Ｒ の行為）：
各々の呼び出しで、上述のように指定されるプロセスを適用することによって証人装置のコミットメント Ｒ の計算手段が各コミットメント Ｒ を計算する。該証人手段は、コミットメント Ｒ の全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有する。
【００８８】
・ステップ２（チャレンジｄの行為）：
前記署名装置は、前記署名装置の計算手段と呼ばれる該計算手段を含み、変数を前記メッセージおよび各コミットメント Ｒ の全部または一部とするハッシュ関数ｈを適用して、あるバイナリトレインを計算し、このバイナリトレインからコミットメント Ｒ と同じ数のチャレンジｄを導出する。
【００８９】
・ステップ３（応答 Ｄ の行為）：
前記証人装置の前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれそれのチャレンジｄを受け取り、前記証人装置の前記応答 Ｄ の前記計算手段は、上述のようなプロセスを適用することにより、前記チャレンジｄから前記応答 Ｄ を計算する。前記証人装置は、前記証人装置の伝達装置と呼ばれ、前記相互接続手段を通して前記署名装置へと前記応答 Ｄ を伝達させる、伝達装置からなる。
【００９０】
［コントローラ装置］
本発明はまたコントローラ装置に関連する。そのコントローラ装置は、コントローラエンティティに関連した端末か遠隔サーバ形態を特にとることができる。
該コントローラ装置は、
・ あるエンティティの真性性、および／または、
・ 該エンティティと関連するメッセージ Ｍ の完全性
をチェックするようにされている。この証明は、以下のパラメータ：
・ 秘密の値 Ｑ１ 、 Ｑ２ 、 ．．．  、 Ｑｍ と公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ （ｍは １ 以上）の ｍ 個の組
・  ｆ 個の素因数 ｐ１ 、 ｐ２ 、 ．．．   ｐｆ の積で構成される公開のモジュラス ｎ （ ２ 以上の ｆ ）で、前記コントローラ装置と関連しているコントローラエンティティには知られていないもの、
の全部若しくは一部またはこれらのパラメータからの算出値を用いることで成り立つ。
【００９１】
前記モジュラスと前記秘密値と公開値は、
【数１２８】
2004527139.tif 000056
のタイプの関係があり、ここで、ｖは
【数１２９】
2004527139.tif 000057
のタイプの公開値である指数値を表す（ｋは１より大きいセキュリティパラメータ、 Ｑｉ は、前記コントローラ装置には知られていない、前記公開値 Ｇｉ に関連している秘密値）。
【００９２】
前記ｍ個の公開値 Ｇｉ は、ｍ個の区別できるベース数 ｇ１ 、 ｇ２ 、… ｇｍ の、 ｆ 個の素因数 ｐ１ 、 ｐ２ 、… ｐｆ より小さい二乗値ｇ ｉ２ であり；前記 ｐ１ 、 ｐ２ 、… ｐｆ の素因数、および／または、ｍ個のベース数 ｇ１ 、 ｇ２ 、… ｇｍ は以下の条件が満たされるように生成される。
【００９３】
［第１の条件］
第１の条件は、各方程式
【数１３０】
2004527139.tif 000058
がモジュロｎの整数環におけるｘについて解を持つこと。
【００９４】
［第２の条件］
Ｇｉ（Ｑｉｖ   ｍｏｄ   ｎ である場合、第２の条件は、 Ｑｉ を二乗してモジュロ ｎ を ｋ−１ 回とったｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）。
Ｇｉ．Ｑｉｖ   （ １ ｍｏｄ   ｎ である場合、第２の条件は、 Ｑｉ のモジュロｎを二乗したものの逆モジュロ ｎ を ｋ−１ 回とって得られるｍ個の数 ｑｉ のうち、これらのいずれかが± ｇｉ ではないこと（つまり、トリビアルではないこと）。
【００９５】
［第３の条件］
第３の条件は、２ｍ個の方程式
【数１３１】
2004527139.tif 000059
がモジュロｎの整数環におけるｘについて解を持つこと。
【００９６】
［エンティティの真性性の証明の場合］
実施形態の第１の変形において、本発明のコントローラ装置は、コントローラと呼ばれるあるエンティティに対して、デモンストレータと呼ばれるあるエンティティの真性性を証明するようにされている。
前記コントローラ装置は、特にデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響によって接続する、デモンストレータエンティティに関連したデモンストレータ装置への接続のための接続手段を含んでいる。
前記コントローラ装置は、以下のステップを実行するのに用いられる：
【００９７】
・ステップ１および２（コミットメントＲの行為、チャレンジｄの行為）：
前記コントローラ装置は、また、前記接続装置を通して前記デモンストレータ装置から来るコミットメント Ｒ の全部または一部を受け付ける手段を有する。
前記コントローラ装置は、前記コミットメント Ｒ の全部または一部を受け取った後に、それぞれの数がコミットメント Ｒ と同じであるチャレンジ ｄ （各チャレンジｄはｍ個の整数 ｄｉ （以下「要素チャレンジ」と呼ぶ）からなる）を生成する、チャレンジ生成手段を含む。
前記コントローラ装置は、また、前記接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を含む。
【００９８】
・ステップ３および４（応答 Ｄ の行為、チェックの行為）：
前記コントローラ装置は、また、
・ 前記接続手段を通じて前記デモンストレータ装置から来る前記応答 Ｄ を受け付ける手段
・ 前記コントローラ装置の計算手段と呼ばれる計算手段
・ 前記コントローラ装置の比較手段と呼ばれる比較手段
を備える。
【００９９】
・第１のケース：前記デモンストレータが各コミットメント Ｒ の一部を伝送した場合：
前記デモンストレータが各コミットメント Ｒ の一部を伝送した場合には、
ｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有する前記コントローラ装置の前記計算手段は、各チャレンジ Ｒ と各応答 Ｄ から再構成されたコミットメント Ｒ ´を計算し、その再構成されたコミットメント Ｒ ´は
【数１３２】
2004527139.tif 000060
のタイプの関係か、
【数１３３】
2004527139.tif 000061
のタイプの関係を満たす。
前記コントローラ装置の前記比較手段は、各再構成されたコミットメント Ｒ ´を受け付けられた各コミットメント Ｒ の全部または一部と比較する。
【０１００】
・前記デモンストレータが各コミットメント Ｒ の全部を伝送した場合：
前記デモンストレータが各コミットメント Ｒ の全部を伝送した場合には、
ｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有する前記コントローラ装置の前記計算手段と前記比較手段は、各チャレンジ Ｒ が
【数１３４】
2004527139.tif 000062
のタイプの関係か、
【数１３５】
2004527139.tif 000063
のタイプの関係を満たすことを確認する。
【０１０１】
［メッセージの完全性を証明する場合］
本発明による前記第１のコントローラ装置に組み合わせることのできる、実施の形態の第２の変形は、デモンストレータと呼ばれるあるエンティティの完全性を証明するようにされている。
前記コントローラ装置は、特にデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響によって、デモンストレータエンティティに関連したデモンストレータ装置への接続のために、接続手段を含んでいる。
前記コントローラ装置は以下のステップを実行するのに用いられる：
【０１０２】
・ステップ１および２（コミットメントＲの行為、チャレンジｄの行為）：
前記コントローラ装置は、また、前記接続装置を通して前記デモンストレータ装置から来るトークン Ｔ を受け付ける手段を有する。前記コントローラ装置は、前記トークン Ｔ を受け取った後に、それぞれの数がコミットメント Ｒ と同じであるチャレンジ ｄ （各チャレンジｄはｍ個の整数 ｄｉ （以下「要素チャレンジ」と呼ぶ）からなる）を生成する、チャレンジ生成手段を含む。前記コントローラ装置は、また、前記接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を含む。
【０１０３】
・ステップ３および４（応答 Ｄ の行為、チェックの行為）：
前記コントローラ装置は、また、前記接続手段を通じて前記デモンストレータ装置から来る前記応答 Ｄ を受け付ける手段を含む。前記コントローラ装置は、前記コントローラ装置の計算手段と呼ばれる計算手段であって、この計算手段は、第１に、ｍ個の公開値 Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ を有するとともに、各チャレンジｄと各応答 Ｄ から再構成されたコミットメント Ｒ ´を計算し、そのコミットメント Ｒ は
【数１３６】
2004527139.tif 000064
のタイプの関係か、
【数１３７】
2004527139.tif 000065
のタイプの関係を満たし、
【０１０４】
第２に、前記メッセージ Ｍ および各再構成されたコミットメント Ｒ ´の全てまたは一部を変数として有する前記ハッシュ関数ｈを適用することによりトークン Ｔ ´を計算しする、計算手段を含む。
前記コントローラ装置は、トークン Ｔ ´を受け付けられたトークン Ｔ と比較する前記コントローラ装置の比較手段と呼ばれる比較手段を備える。
【０１０５】
［メッセージのディジタル署名とその真性性の証明］
先の２つの実施形態のいずれか、および／または、他のものと組み合わせることができる、本発明による実施の形態の第３の変形においては、署名されたメッセージと呼ばれているエンティティによって署名されたメッセージをチェックすることによってメッセージ Ｍ の真性性を証明するようにされている本発明のコントローラ装置である。
前記署名メッセージは、ハッシュ関数ｈ（ ｍｅｓｓａｇｅ，Ｒ ）を有するある署名エンティティに関連した署名装置によって送られるとともに、
・ 前記メッセージ Ｍ 、
・ 前記チャレンジｄおよび／またはコミットメント Ｒ 、
・ 前記応答 Ｄ 、
からなる。
【０１０６】
・チェック動作：
前記コントローラ装置は、前記署名エンティティに関連した前記署名装置への、特にデータ処理通信ネットワークを通る電気的、電磁気的、光学的、あるいは音響による接続のための接続手段を含んでいる。該コントローラ装置は、前記署名装置から前記接続を通じて前記署名メッセージを受け取り、
前記コントローラ装置は、
・ 前記コントローラ装置の計算手段と呼ばれる計算手段、
・ 前記コントローラ装置の比較手段と呼ばれる比較手段、
を備える。
【０１０７】
・場合前記コントローラ装置がコミットメント Ｒ 、チャレンジｄ、応答 Ｄ を有する場合：
場合前記コントローラ装置がコミットメント Ｒ， チャレンジｄ、応答 Ｄ を有する場合、前記コントローラ装置の前記計算手段および前記比較手段は、前記コミットメント Ｒ 、前記チャレンジｄ、前記応答 Ｄ が
【数１３８】
2004527139.tif 000066
のタイプか、
【数１３９】
2004527139.tif 000067
のタイプの関係を満たすことを確認する。
そして、前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージ Ｍ， 前記チャレンジｄ、前記コミットメント Ｒ が前記ハッシュ関数
【数１４０】
2004527139.tif 000068
を満たすことを確認する。
【０１０８】
・前記コントローラ装置がチャレンジｄ、応答 Ｄ を有する場合：
前記コントローラ装置がチャレンジｄ、応答 Ｄ を有する場合、前記コントローラ装置の前記計算手段は、各チャレンジｄと各レスポンス Ｄ に基づいて、
【数１４１】
2004527139.tif 000069
のタイプか、
【数１４２】
2004527139.tif 000070
のタイプの関係を満たすコミットメント Ｒ ´を計算し、前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージ Ｍ と前記チャレンジｄがハッシュ関数
【数１４３】
2004527139.tif 000071
を満たすことを確認する。
【０１０９】
・前記コントローラ装置がコミットメント Ｒ 、応答 Ｄ を有する場合：
前記コントローラ装置がコミットメント Ｒ 、応答 Ｄ を有する場合、前記コントローラ装置の前記計算手段は、前記ハッシュ関数を適用して、
【数１４４】
2004527139.tif 000072
のようなｄ´を計算する。
そして、前記コントローラ装置の前記計算手段と前記比較手段は前記コミットメント Ｒ 、前記チャレンジｄ´、前記応答 Ｄ が
【数１４５】
2004527139.tif 000073
のタイプの関係を満たすか、
【数１４６】
2004527139.tif 000074
のタイプの関係を満たすことを確認する。
【０１１０】
［発明の記述］
ＧＱ 方法の目的は、メッセージのディジタル署名とエンティティとメッセージのダイナミックな真性性である。これらは、「知識の移動なしで」方法である。エンティティは、それが １ または秘密のいくつかの数を知っているということを証明する。もう一つのエンティティは、チェックする ； それは、対応する公開値または数を知っている。証明しているエンティティは秘密の数を明らかにすることなくチェックしているエンティティを確信させようとすし、そのような方法で、必要に応じて何度も使うことができる。
【０１１１】
各々の ＧＱ 方法は、秘密の高い素数からなる公開のモジュロに依存する。公開されている指数値 ｖ と公開されているモジュロｎは、ともに、「べき乗ｖモジュロｎへの増加」と意味し、一般的ないくつかの方程式（すべて同じタイプの）：直接、 Ｇ ≡ Ｑｖ （ ｍｏｄ   ｎ ）から、あるいは、 Ｇｘ   Ｑｖ ≡１の逆演算で実現される。このタイプは、証明エンティティの範囲内で以外でない、エンティティをチェックすることの範囲内で計算の演算に影響を及ぼす ； 実際、セキュリティ分析は、 ２ つのタイプを混乱させる。公開値 Ｇ にリンクされる各々の一般的な方程式と秘密の数 Ｑ は、一緒に一対の数｛ Ｇ，Ｑ ｝を作る。再開するために、各々の ＧＱ 方法は、同じ鍵 ＜ｖ，ｎ＞ のために １ または数対の数｛ Ｇ，Ｑ ｝を含む。 ＧＱ１ と呼ばれてここでは、 ＧＱ 方法の古典バージョンは、 ＲＳＡ ディジタル署名メカニズムを使う。確認鍵 ＜ｖ，ｎ＞ は、それから変わった指数値 ｖ が望ましくは素数である ＲＳＡ 公開鍵である。各々の ＧＱ１ 法は、一般に １ 対の一つの数｛ Ｇ，Ｑ ｝を使う： ＲＳＡ ディジタル署名技術の必要不可欠な一部であるフォーマット・メカニズムによって、公開値 Ｇ は、識別データから推論される。秘密の数 Ｑ またはその逆のモジュロｎは、識別データのための ＲＳＡ 署名である。証明エンティティはそれ自身の識別データの ＲＳＡ 署名についてのその知識を示する、そして、この証明はしたがって、必要に応じて多くの時間として使われるために、秘密のままである署名を現しない。 ＧＱ１ 法は、一般に ２ レベルの鍵を実装する：識別データによる他から一つの鍵に署名して秘密の ＲＳＡ は、彼ら自身を識別しているエンティティを公認しているオーソリティのために予約されてある。そのようなメカニズムは、「基礎を形成されるアイデンティティ」であると言われる。このように、チップカードのエミッタは、カードにおいて多様化された秘密鍵として刻まれる秘密の数 Ｑ を計算するために各々のカードの刊行のために彼の ＲＳＡ 秘密鍵を使用する ； または、さらに、セッションの間のクライアントの短命な秘密鍵である秘密の数 Ｑ を計算するために各セッションに入るとき、コンピュータのネットワークの上のクライアントは彼の ＲＳＡ 秘密鍵を使用する。エンティティ（開会中のチップカードまたはクライアント）を証明することは、彼らの識別データの ＲＳＡ 署名を知っている ； 彼らは、鍵ヒエラルキーおいて、次のより高いレベルにある ＲＳＡ 秘密鍵を知らない。それでもなお、オーソリティのレベルの ７６８ のビットのモジュロによる ＧＱ１ によるエンティティのダイナミックな真性性は各々のエンティティのレベルの ３ つの素因数による ５１２ のビットのモジュロをもつ ＲＳＡ のそばのエンティティのダイナミックな真性性と同じほとんど作業負荷を必要とする。そして、それは証明エンティティを彼らの製品のために法結果を計算する前に素因数の各々のために法結果を計算することによってチャイニーズ剰余法テクニックを使用させる。しかし、オーソリティと公認のエンティティの間の鍵のヒエラルキは、義務的ではない。人は証明エンティティに属しているモジュールで、 ＧＱ１ を使うことができる。そして、それは証明エ���ティティのレベルのモジュロが当局たとえば ７６８ のビットと比較すると ５１２ のビットのレベルのモジュロより短くありえるという事実は別として、基本的にエンティティをチェックする作業負荷を変えないエンティティを証明する作業負荷を減らすことをチャイニーズ剰余法テクニックを使用する可能性があるようにする。エンティティがそれ自身のモジュロの素因数を知っている時に、なぜ ＲＳＡ ディジタル署名メカニズムの呼び出すのか？
【０１１２】
基本の ＧＱ２ とここで呼ぶ、 ＧＱ 方法のもう一つのバージョンは、直接モジュロｎの因数分解の問題を扱いる。この文脈では、「直接」は、「 ＲＳＡ 署名を求めるない」ことを意味する。証明エンティティでだけでなくエンティティをチェックすることでも、 ＧＱ２ の狙いは、作業負荷を減らすことになっている。証明エンティティはそれ自身のモジュロの分解についての知識を示する、そして、この証明はしたがって、必要なほど、しばしば使われることができるために、秘密のままである分解を明らかにしない。 ＧＱ２ プロトコルのセキュリティは、モジュールの因数分解に等しい。
【０１１３】
各証明エンティティは、それ自身のモジュロｎを持つ。各 ＧＱ２ メカニズムは、公開の指数値 ｖ＝２ｋ を固定する １ を超える小さな数であるパラメータ ｋ と、１以上のいくつかの数の対｛ Ｇ１，Ｑ１ ｝から｛ Ｇｍ，Ｑｍ ｝とを
インプリメントする。各々の公開値 Ｇｉ は、 １ を超える小さな数である ｇｉ の二乗値であって、「ベース数」と呼ぶ。全ての証明エンティティは同じ公開値 Ｇ１ から Ｇｍ を使うことができる。モジュロｎと Ｑ１ から Ｑｍ の数の因数分解は、それから、同じ鍵ヒエラルキのレベルにある。
基本の ＧＱ２ 鍵の各々の集合は、 ２ つの必要で十分な条件によって定義される：
【０１１４】
・ 各々のベース数について、 ２ つの方程式 ｘｖ ≡± ｇｉ （ ｍｏｄ   ｎ ）のどちらも、モジュロｎの整数環において、 ｘ の中に解を持つ。いわば、数± ｇＩ は ２ つのモジュロｎの非二次の残余である。
・ 各々のベース数について、方程式 ｘｖ ≡± ｇ２ （ ｍｏｄ   ｎ ）（ここで、 ｖ＝２ｋ ）がモジュロｎの整数環に、 ｘ の中に解を持つ。秘密の数 Ｑｉ またはその逆のモジュロｎは、これらの解の任意のものになる。
【０１１５】
第 ２ の条件を考慮することにより、数± ｇｉ が ２ つのモジュロｎの非二次の残余とするために、モジュロｎは、 ｇｉ の Ｌｅｇｅｎｄｒｅ シンボルが関連する ３ （ ｍｏｄ   ４ ）に適合する少なくとも二つの素因数を含む。従って、モジュロは、 ３ （ ｍｏｄ   ４ ）に適合するのが全く無いか、 １ つだけの素因数から成る場合、一組の基本の ＧＱ２ 鍵を確立させない。そして、それは ３ （ ｍｏｄ   ４ ）まで適合する素因数に特権を与える。このように、高い素数を無作為に選ぶことによって、半分だけが ３ （ ｍｏｄ   ４ ）と半分が １ （ ｍｏｄ   ４ ）まで適合するようである。その結果、使用中の多くの ＲＳＡ モデルは、一組の基本の ＧＱ２ 鍵を確立することができない。
【０１１６】
ここでは、我々は何ら任意のモジュロででも、そして、特に、何ら任意の ＲＳＡ モジュロのいても ＧＱ２ 技術を使用することができるためにこの制限を克服するために一般化された ＧＱ２ 鍵の集合を導入する。それは、 ２ つの必要で十分な原則に依存する。：
【０１１７】
第１の原則は、第二の基本の ＧＱ２ 条件を複写する：
−ｇ１ から ｇｍ までの各々のベースについて、方程式 ｘｖ（ｇｉ２ （ ｍｏｄ   ｎ ）、ここで、 ｖ＝２ｋ 、が、がモジュロｎの整数環において、 ｘ に解を持つこと。
秘密の数 Ｑ またはその逆のモジュロｎが方程式の解であるので、連続した二乗値 ｋ−１ つのモジュロｎが、それをモジュロｎの整数環における Ｇｉ の根である数 ｑｉ に変える。数 ｑｉ が ２ つの数 ｇｉ か ｎ−ｇｉ のうちの １ つと等しいか ２ つの数 ｇｉ と ｎ−ｇｉ と異なるかどうかに従い、それがトリビアルか、あるいはそうではないと言われる。
【０１１８】
数 ｑｉ が非トリビアルのとき、 ｑｉ２−ｇｉ２ を割る ｎ は ｑｉ−ｇｉ か ｑｉ＋ｇｉ を割らない。任意の非トリビアル数 ｑ は、このようにモジュロｎの分解を明らかにする。
【数１４７】
2004527139.tif 000075
ｎ＝ｐｇｃｄ（ｎ，ｑｉ−ｇｉ）ｘｐｇｃｄ（ｎ，ｑｉ＋ｇｉ）
第２の原則原則が最初の基本の ＧＱ２ 条件を拡張する：
・数 ｑ１ から ｑｍ の中で、少なくともいずれかつの数 ｑｉ は、非トリビアルである。
数± ｇｉ がモジュロｎの整数環における ２ つの非二次の残余である間、数 ｑ＋ が存在するならば、数 ｑｉ が明白に非トリビアルである点に注意されたい。
【０１１９】
このように、基本の ＧＱ２ 鍵の集合は、確かに一般化された ＧＱ２ 鍵の集合の部分であり、一般化された ＧＱ２ 鍵は、何ら任意のモジュロでも使うことを可能にする、つまり、少なくとも二つが区別できるかぎり、無関係に、 ３ つまり １ （ ｍｏｄ   ４ ）に適合する高い素数の任意の合成である。他方、一般化された ＧＱ２ 鍵の多くの集合は、基本の ＧＱ２ 鍵の集合ではない。一般化された ＧＱ２ 鍵の各々の集合は、以下のケースのうちの １ つに従っている：
・ 数± ｇ１ から± ｇｍ までの ２ｘｍ が全て、非二次の残余であるとき、これは一組の基本（ ｅｌｅｍｅｎｔａｒｙ ）の ＧＱ２ 鍵である。
・ 数± ｇ１ から± ｇｍ までの ２ｘｍ において、少なくともいずれかつの非二次の残余があれば、これは一組の基本の ＧＱ２ 鍵ではなく、ここでは一組の相補型 ＧＱ２ 鍵とされる。
【０１２０】
本発明は、定義において、基本でない一般化された ＧＱ２ 鍵のこれらのセットである、その相補型 ＧＱ２ 鍵の集合に関する。 ２ つの前の原則の他に、そのようなセットは、第 ３ の原則を満たさなければならない。
・ ± ｇ１ から± ｇｍ への ２ｘｍ 数± ｇ１ の中に、少なくともいずれかつの二次の残余がある。
【０１２１】
問題を評価して、我々が提供するソリューション、つまり、本発明、を理解するために、まず第一に非トリビアル数 ｑ によって現れられるモジュロｎの分解を分析し、それから、チャイニーズ剰余法テクニック、それからガロア域 ＣＧ（ｐ） でランクの概念に戻る。そして、次に、 ＣＧ（ｐ） で関数「二乗値への増加」と、 ＣＧ（ｐ） で二次の残余の「平方根をとること」を議論し、そして最後に、上述の ３ つの原則の適用性を分析する。
【０１２２】
（モジュールの分解の分析）
モジュロｎが ｐｆ に ｆ 個の素因数 ｐ１ に分解されるように、モジュロｎの整数環は ｆ 個のガロア域 ＣＧ（ｐ１）  から ＣＧ（ｐｆ） に分解される。各々のフィールドでは、 ２ 個の単位根（すなわち± １ ）がある。つまり、環では ２ｆ 個の単位根がある。 Ｑ１ から Ｑｍ の各秘密の数は、環におけるこれらの ２ｆ 個の単位平方根のうちの １ つである数Δ ｉ＝ｑｉ  ／ｇｉ （ ｍｏｄ   ｎ ）を定義する ；
言い換えると、Δ ｉ２−１ は ｎ で割り切れる。
【０１２３】
・ ｑｉ がトリビアル、つまり、Δ ｉ＝ ± １ｎ なら、Δ ｉ−１ あるいはΔ ｉ＋１ は ｎ で割り切れる。したがって、Δ ｉ は、モジュロｎの分解を明らかにはしない。
・ ｑｉ が非トリビアル、つまり、Δ ｉ ≠± １ なら、Δ ｉ−１ あるいはΔ ｉ＋１ は ｎ では割り切れない。従って、Δ ｉ は分解、 ｎ＝ｐｇｃｄ（ｎ 、Δ ｉ−１）ｘｐｇｃｄ（ｎ 、Δ ｉ  ＋１） 各々のフィールドでΔ ｉ の値から導かれる）：この素因数は、Δ ｉ−１ を割り切るか、他方、Δ ｉ＋１ を割り切る。
数 ｑ の増殖性の構成の支配の検査
【０１２４】
２ つの数｛ ｑ１，ｑ２ ｝は、合成数 ｑ１ｘｑ２（ｍｏｄ   ｎ） を与える。
・  ｑ１ が非トリビアル、そして、 ｑ２ がトリビアルとき、合成数 ｑ１ｘｑ２（ｍｏｄ   ｎ  ） は非トリビアルである ； これは、 ｑ１ と同じ分解を明らかにする。
・  ｑ１ と ｑ２ が非トリビアルΔ １   ＝ ±Δ ２ であるとき、合成数 ｑ１ｘｑ２（ｍｏｄ   ｎ  ） はトリビアルである ； これは、いかなる分解も明らかにしない。。
・  ｑ１ と ｑ２ が非トリビアルおよび Ｄ１ ≠± Ｄ２ であるとき、合成数 ｑ１ｘ   ｑ２   （ｍ  ｏｄ   ｎ） は非トリビアルである ； これは、第 ３ の分解を明らかにする。
３ つの数｛ ｑ１，   ｑ２，ｑ３ ｝は、 ４ 合成数｛ ｑ１ｘ   ｑ２ 、 ｑ１ｘ   ｑ３ 、 ｑ２ｘ   ｑ３ 、 ｑ１ｘ   ｑ２ｘ   ｑ３   （ｍｏｄ   ｎ） ｝（すなわち合計 ７ つの数）を与える ；
ｍ 番号は、このように ２ｍ−ｍ−１ 合成数（すなわち ２ｍ−１ 番号の合計）を提供する。
【０１２５】
我々は現在、 ｉ 個のベース数 ｇ１ 〜 ｇｉ と、 ｉ 個の数 ｑ１ 〜 ｑｉ を与える ｉ 個の秘密数 Ｑ  １ 〜 Ｑｉ と、単位平方根である ｉ 個のベース数Δ １ 〜Δ ｉ を含んでいる一組の一般化された ＧＱ２ 鍵を考える。秘密の数 Ｑｉ＋１ によって、もう一つのベース数に ｇｉ＋１ を、数 ｑｉ   ＋１ と、そして根Δ ｉ＋１ を与えて、考慮してみる。
【０１２６】
・ ２ｉ＋１−１ 個の数の合計は、以下のケースの各々では、多くの非トリビアル数からなる：
・ 根Δ ｉ＋１ はトリビアルである、そして、ダイへの少なくともいずれかつの根 Ｄ１ は非トリビアルである。
・ 根Δ ｉ＋１ は、トリビアルでも、 ２ｘｉ 根±Δ １ と±Δ ｉ の中で現れる ２ｘｉ 個の根±Δ １ 〜±Δ ｉ の数でもない。
・根Δ ｉ＋１ が非トリビアルであって、 ２ｘｉ 個の根±Δ １ 〜±Δ ｉ の数の中ではなく、各々の ｑｉ   ＋１ 個の数の合成数が非トリビアルでないとき。
従って、数 ｑ１ 〜 ｑｍ への ｍ 個の数の中で少なくともいずれかが非トリビアルのとき、 ２  ｍ−１ 個の数の半分の合計より多くのものは非トリビアルである。
【０１２７】
定義によって、 ２ｌ−ｌ−１ 個の対応する合成数の各々が非トリビアル、すなわち、全体で ２ｌ−ｌ 個の数が非トリビアルであるとき、数えるモジュロｎと比較して、 ｌ＜ｆ 個の非トリビアル数｛ ｑ１，   ｑ２，．．．，   ｑｌ ｝が、独立していると言われる。
【０１２８】
これらの ２ｌ−ｌ 個の数の各々は、このようにモジュロｎの異なる分解を明らかにする。
・  ｆ 個の素因数が異なっているとき、モジュロｎの ２ｆ−１   −１ 分解がある。
このように、 ｆ−１ 個の数 ｑ が独立しているならば、双単一の意味での対応が、 ２ｆ   −  １−１ 分解と、 ｆ−１ 個の独立した数と ２ｆ−１−ｆ 個の対応する合成数を含んでいる ２  ｆ   −１−  １ 個の数の合計との間にある。
【０１２９】
・チャイニーズ剰余法
２ 個の数 ａ，ｂ のいずれか、 ０＜ａ＜ｂ のその間の素数、 ０ から ａ−１ の数 Ｘａ と、０から ｂ−１ の Ｘｂ の ２ つの数については、 ； 数が ０ から ａｘｂ−１ までの、その Ｘａ ≡ Ｘ（  ｍｏｄ   ａ） と Ｘｂ ≡ Ｘ（ｍｏｄ   ｂ） にユニークな Ｘ ものの決定に関する。数 ｘ ≡ ［ｂ（  ｍｏｄ   ａ）］−１（ｍｏｄ   ａ） は、チャイニーズ剰余法パラメータである。
基本のチャイニーズ剰余法の演算は、下に与えられる：
【数１４８】
2004527139.tif 000076
要約すると、： Ｘ＝Ｃｈｉｎｅｓｅ   ｒｅｍａｉｎｄｅｒｓ（Ｘａ，Ｘｂ ）。
【０１３０】
ｆ 個の素因数が最も小さい ｐ１ から最大の ｐｆ に増加するように並べられると、チャイニーズ剰余法パラメータは以下のように与えられる（素因数（すなわち ｆ−１ ）より少なくなるものがある）。
・ 最初のパラメータは、 ｘ ≡（ ｐ２   （ｍｏｄ   ｐ１） ） −１（ｍｏｄ   ｐ１） である ．
・ 第二のパラメータは、β≡（ ｐ１ｘ   ｐ２   （ｍｏｄ   ｐ３） ） −１（ｍｏｄ   ｐ３） である ．
・  ｉ 番目のパラメータは、（ ｐ１ × ．．．ｐｉ−１（ｍｏｄ   ｐｉ） ） −１（ｍｏｄ   ｐ  ｉ） である。
・ 等。
ｆ−１ 個の基本の演算において、人は ０ から ０ から ｐｊ−１ まで Ｘｊ で Ｘ１ から ｆ 構成要素の任意の集合からでも Ｘｆ まで始まっている ｎ−１ まで、数 Ｘ を確立する：
・ 最初のパラメータによる最初の結果（ ｍｏｄ   ｐ１ｘ   ｐ２ ）、
・ そして第二のパラメータによる第二の結果（ ｍｏｄ   ｐ１ｘ   ｐ２ｘｐ３ ）、
・ 最終結果まで（ ｍｏｄ   ｎ   ＝   ｐ１ｘ   ｐ２ｘ．．．   ｐｆ ）最後のパラメータで。
ｐｆ に素因数 ｐ１ を与えられて、再開するために、モジュロｎの整数環の各々の要素は、 ２ つの等価表現を持つ：
・  ｆ 個の数 Ｘ１ 〜 Ｘｆ の素因数構成要素： Ｘｊ ≡ Ｘ（ｍｏｄ   ｐｊ） 、
・  ０ から ｎ−１ への数 Ｘ 、 Ｘ＝   Ｃｈｉｎｅｓｅ   ｒｅｍａｉｎｄｅｒｓ （ Ｘ１，Ｘ２，  ．．．   Ｘｆ ））。
ＣＧ（ｐ） での数のランク
ｐ を奇数の素数とし、 ａ を ｐ より小さい数、すなわち ０＜ａ＜ｐ とする。定義より、 ｐ についての ａ のランクは、｛ ｘｉ   ＝ａ； そして、 ｉ ≧ １，ｘｉ＋１ ≡ ａ × ｘｉ （ ｍｏｄ   ｐ ）｝で提起されるシーケンス｛ Ｘ ｝の期間である。フェルマー定理を適用することによって ｘｉ＋ｐ ≡ ａｐ × ｘｉ ≡ ａ × ｘｉ ≡ ｘｉ＋１ （ ｍｏｄ   ｐ ）が得られる。したがって素数 ｐ についての数 ａ のランクは、 ｐ−１ 、または、 ｐ−１ の割る数である。
【０１３１】
例えば、（ ｐ−１ ） ／２ が、奇数の素数 ｐ であるとき、 ＣＧ（ｐ） が数を含むガロア域は、ランク１の数を含む：これは、ランク ２ の、 １ である：これは、ランクｐ´である ｐ’  −１ 個の数と、ランク２×ｐ´＝ ｐ−１ の、ｐ´ −１ 個の数である、 ＣＧ（ｐ） では、ランク ｐ−１ の任意の数は、「ジェネレータ」である。この名称は、 ＣＧ（ｐ） でのジェネレータの連続したべき乗（すなわち １ から ｐ’−１ へのインデックスのためのシーケンス｛ Ｘ ｝の項）が ＣＧ（ｐ） の全てのゼロ以外の要素の順列を作るという事実による。
【０１３２】
ｙ を ＣＧ（ｐ） のジェネレータとする。 ｉ と ｐ−１ によって数 ｙ ´（ ｍｏｄ   ｙ ）のランクを評価することにする。 ｉ が ｐ−１ と互いに素であるとき、これは ｐ−１ である。 ｐ−  １ が ｉ で割り切れるとき、これは （ｐ−１）／ｉ である。全てのケースで、（ ｐ−１ ） ／  ｌｇｃｄ（ｐ−１，ｉ） （ ｌｇｃｄ   ＝ 最大公約数）。
【０１３３】
定義によって、オイラーの関数φ （ｎ） は、 ｎ より小さい数で、 ｎ と互いに素な ｎ より小さい数の個数である。 ＣＧ（ｐ） にはφ （ｐ−１） 個のジェネレータがある。
例証として、 ＲＳＡ の基礎を理解することは、ランクを用いて容易になる。モジュール ｎ は、 ｆ ≧ ２ について、 ｆ 個の素因数 ｐ−１ から ｐ−ｆ までの積である。 ｐ１ から ｐｆ への各々の素因数 ｐｉ について、公開されている指数値 ｅ は、 ｐｊ−１ と互いに素でなければならない。今度は、鍵 ＜ｅ，ｐｊ＞ は、 ＣＧ（ｐｊ） の要素のランクに従う。：これは Ｃ  Ｇ（ｐｊ） の要素を並べ替える ； 通常は ｅ × ｄｊ−１ が ｐ−１ で分りきれてできるだけ小さいような数 ｄｊ が存在する。鍵 ＜ｄｊ 、 ｐｊ＞ は ＣＧ（ｐｊ） の要素の順列を逆にする。これらの ｆ 個の順列（各フィールド ＣＧ（ｐ１） から ＣＧ（ｐｆ） ）は、公開鍵 ＜ｅ，  ｎ＞ によってまとめられる ＲＳＡ 順列によって、モジュロｎの整数環において表される。ｄ× ｅ−１ が（ ｐ１−１、ｐ２−１ 、．．． ｐｆ−１ ）の最小公倍数（ ｓｃｍ ）で割り切れるような、一般に、できるだけ小さい数 ｄ が、存在する。
【０１３４】
ｐ１ から ｐｆ への各々の素因数 ｐｊ に対して、我々は ｄｊ ≡ ｄ （ ｍｏｄ   ｐｊ−１ ）を持つ。 ＲＳＡ 順列は、公開鍵 ＜ｅ，ｎ＞ が秘密鍵 ＜ｄ，ｎ＞ によって逆演算されることにまとめられる。
【０１３５】
ＣＧ（ｐ） の二乗値
ｐ−１ が ２ｔ で割り切れるが、 ２ｔ−１ 以外である、そのようなその数 ｔ を定義しよう。各々の大きい素数は、 ｔ＝１，ｔ＝２，ｔ＝３、ｔ−４ 等々の中の唯一の １ つのカテゴリーの中に現れる。もし、連続した素数の十分に大きい数が考慮されるならば、大体 ２ つに １ つは、 ｐ が ３ （ ｍｏｄ   ４ ）に適合する最初のカテゴリー、 ４ つに １ つは ｐ が ５ （ ｍｏ  ｄ   ８ ）に適合する第二のもの、８個に １ つは ｐ が ９ （ ｍｏｄ   １６ ）に適合する第 ３ のものに、 １６ 中 １ 、 ｐ が １７ （ ｍｏｄ   ３２ ）に適合する第 ４ のもの、その他、というようにところに現れ ； 大体、２ ｔ 個に １ つは ｐ が２ ｔ＋１ （ ｍｏｄ   ２ｔ＋１ ）適合する第ｎのものに、現れる。
【０１３６】
数 ｘ と ｐ−ｘ には ＣＧ（ｐ） で同じ二乗値があるので、鍵 ＜２，ｐ＞ は ＣＧ（ｐ） の順序を変更しない。 ＣＧ（ｐ） で「二乗値になる」関数は、フィールドの各々のゼロ以外の要素が自身の場所を捜し出す方向付けられたグラフによって表示されるかもしれない。各々の要素のランクのパリティによって、ブランチとサイクルをもちいてグラフの構造を分析しよう。
【０１３７】
ゼロ要素がセットされる。これは、０である。 ０ 要素について他のいかなる要素も関係がなく；ランクは定義されない ；０ 要素は、孤立する。
単位元が、セットされる。これは、 １ である、ランク １ の唯一の要素。
ＣＧ（ｐ） 中の単位の全ての根は、 １ に関連したブランチにある。 ｙ を ＣＧ（ｐ） の非二次の残余（任意の残余）とする。鍵 ＜（ｐ−１）／２ｔ 、 ｐ＞ は、 ｂ として参照される、 ｙ を −１ のプリミティブな ２ｔ−１ 番目の根に変える ； 実際、 ｙ（ｐ−１）／２ ≡ −１（  ｍｏｄ   ｐ） が得られる。したがって、 ＣＧ（ｐ） において、 １ 以外の単位の ２ｔ−１ 個の根は、 １ から ２ｔ−１ への指数値のための ｂ のべき乗である：彼らは、 １ に関連したブランチを作る。
【０１３８】
偶数のランクの任意の要素の二乗値は、２で割り切れる数のランク他の要素である。したがって、偶数のランクの各々の要素は、あるブランチに置かれる ； 各々のブランチは２で割り切れるが、４では割り切れないランク数を含み、次に ｔ ≧ ２ ならば、４で割り切れるが、８では割り切れない二つのランク数、次に ｔ ≧ ３ ならば、８で割り切れるが、１６では割り切れない４つのランク数、次に ｔ ≧４ならば、１６で割り切れるが、３２では割り切れない８つのランク数、等々となる。全てのブランチは、 １ に関連したブランチと類似している ； 各々のブランチの ２ｔ−１ 個のリーフは、非二次の残余である ； 各々のブランチは、 ２ｔ−１ 個の要素を含んで、奇数ランクの要素と関連がある ； （ ｐ−１ ） ／２ｔ 個の同じ長さ ｔ をもつブランチがある。
【０１３９】
単位元以外の奇数のランクの任意の要素は、同じランクを持っているもう一つの要素である。鍵 ＜２，ｐ＞ は、奇数のランクの（ ｐ−１ ） ／   ２ｔ 個の要素のセットにおいて、並びを変更する。順列は、順列サイクルに因数分解される。サイクルの数は、（ ｐ−１ ） ／  ２ｔ の因数分解に依存する。（ ｐ−１ ） ／２ｔ の各割る数 ｐ ´について、ランク ｐ ´のφ （ｐ） 個の要素を含むをサイクルが存在する。定義によって、オイラーの関数φ （ｐ） は、 ｐ と互いに素で ｐ より少ない数の数であることを、思い起こそう。例えば、 （ｐ−１）  ／２ｔ と等しい ｐ ´が、素数で、ランクｐ´の ｐ ´ −１ 個の数が大きな順列サイクルをつくる。
【０１４０】
図 １Ａ−１Ｄ は、それぞれ、 ３ （ ｍｏｄ   ４ ）、 ５ （ ｍｏｄ   ８ ）、 ９ （ ｍｏｄ   １６ ）と １７ （ ｍｏｄ   ３２ ）まで適合する ｐ のために各々グラフ断片を図示する。
ブランチの上のリーフは、白円で図示される ； これらは、非二次の残余である。
ブランチの中のノードは、灰色の円で図示される ； これらは、偶数ランクの二次の要素である。
サイクルのノードは、黒人のサークルとして図示される ； これらは、偶数ランクの二次の要素である。
【０１４１】
ＣＧ（ｐ） での平方根
ａ が ＣＧ（ｐ） の二次の残余であることがわかったので、方程式 ｘ２ ≡ ａ （ ｍｏｄ   ｐ ）の解を計算する方法、つまり、 ＣＧ（ｐ） で「平方根とる」、を見ることにする。もちろん、多くの方法が、同じ結果を得るためにある ； アンリ・コーエンの本、「計算代数的数論コース（ ａ   Ｃｏｕｒｓｅ   ｉｎ   Ｃｏｍｐｕｔａｔｉｏｎ   Ａｌｇｅｂｒａｉｃ   Ｎｕｍ  ｂｅｒ   Ｔｈｅｏｒｙ ）」 Ｂｅｒｌｉｎ の Ｓｐｒｉｎｇｅｒ 社 １９９３ 年発行のボリューム １３８ 、数学大学院テキスト（ Ｇｒａｄｕａｔｅ   Ｔｅｘｔｓ   ｉｎ   Ｍａｔｈｅｍａｔ  ｉｃｓ 、 ＧＴＭ   １３８ ）シリーズ、のページ ３１−３６ を用いることができるかもしれない。
数  ｓ   ＝ （ ｐ−１＋２ｔ ） ／２ｔ＋１ は鍵 ＜ｓ，ｐ＞ を提供する。これは：
＜（ｐ＋１）／４ 、 ｐ＞ ： ｐ が ３ （ ｍｏｄ   ４ ）に適合するとき
＜（ｐ＋３）／８ 、 ｐ＞ ： ｐ が ５ （ ｍｏｄ   ８ ）に適合するとき
＜（ｐ＋７）／１６ 、 ｐ＞ ： ｐ が ９ （ ｍｏｄ   １６ ）に適合するとき
＜（ｐ＋１５）／３２ 、 ｐ＞ ： ｐ が １７ （ ｍｏｄ   ３２ ）に適合するとき
等々
ということである。
【０１４２】
鍵 ＜ｓ 、 ｐ＞ はサイクルの任意の要素 ａ を、サイクルに前の要素に変換する。 ａ が偶数ランクのものであるとき、それは奇数のランクの解答である、我々はそれに ｗ という名前をつける。実際に、 ＣＧ（ｐ） で、 ｗ２／ａ が等しいことためにために −１ のべき乗（ ２ × （ｐ−１＋２ｔ）／＜２ｔ＋１ ） −１＝ （ ｐ−１ ） ／２ｔ．
他の解は、偶数ランクである ； これは、 ｐ−ｗ である。
【０１４３】
鍵 ＜ｓ 、 ｐ＞ は任意の要素の二次の残余 ａ を、第 １ 近似として、ｒとよぶ解に変換する。 ａ は二次の残余なので、鍵 ＜２ｔ−１ 、 ｐ＞ は ｒ２／ａ を１に確かに変換する。 ａ の平方根にアプローチするため、 ＋１ または −１ を得るのに ｒ２／ａ （ ｍｏｄ   ｐ ）の２ ｔ−２ 乗をとる。結果が ＋１ である、あるいは、他にならば、それが ｂ ´ ｒ （ ｍｏｄ   ｐ ）になる、結果が −１ であるならば、新しい近似は ｒ のままである。そして、 ｐ がフィールド Ｃ  Ｇ（ｐ） で １ の任意のプリミティブな ２ｔ 乗根に言及するということを知っている。したがって鍵 ＜２ｔ−２ 、 ｐ＞ はこの新しい近似を１へと変える。また、鍵 ＜２ｔ−３ 、 ｐ＞ をもちいて、 ｂ２ （ ｍｏｄ   ｐ ）で掛けること、等々でも、アプローチできる。
【０１４４】
以下のアルゴリズムは、方程式を解く。それは、上記のように定義済みの ２ つの変数として数 ａ，ｂ，ｐ，ｒ，ｔ を使う。 ｃ は、連続した訂正と ｗ を表する連続した近似。アルゴリズム、 ｃ   ＝   ｂ と ｗ   ＝   ｒ の初めの。計算終了後、 ２ つの解は、 ｗ と ｐ−ｗ である。 ｔ  −２ から １ への ｉ のために、以下のシーケンスを繰り返す必要がある：
・ 鍵 ＜２ｔ （数 ｗ３／ａ （ ｍｏｄ   ｐ ）への ＋１ または −１ を得るために ｐ＞ ）を適用する。
・  −１ が得られるとき、 ｗ を ｗ ´ ｃ （ ｍｏｄ   ｐ ）と取り替える。
・  ｃ を ｃ２ （ ｍｏｄ   ｐ ）と取り替える。
【０１４５】
原則の適用性
定義によって、我々は指数値 ｎ が ２ｋ である方程式 ｘｎ   ｏ   ｇ２ （ ｍｏｄ   ｐ ）がフィールド ＣＧ（ｐ） で ｘ の中に解を持つとき、パラメータ ｋ 、ベース数 ｇ と素因数 ｐ が互換性（ ｃｏｍｐａｔｉｂｌｅ ）を持つと述べる。数 ｋ と ｇ は、小さくて １ より大きい。 ｐ 番は、大きい素数である。
【０１４６】
・  ｔ   ＝   １ のとき、（すなわち ｐ ≡ ３ （ ｍｏｄ   ４ ））方程式は、を持つ ２ 解。
・  ｔ   ＝   ２ のとき、（すなわち ｐ  ≡  ５ （ ｍｏｄ   ８ ））方程式は、 ｇ の Ｌｅｇｅｎｄｒ  ｅ シンボルに ｐ に関して一致したを持つ ４ 解（（ ｇ ｜ ｐ ） ＝   ＋１ のとき） ； 解なし（ ｇ ｜ ｐ ） ＝−１ のとき）。
・  ｔ   ＞   ２ のとき、（すなわち ｐ  ≡  １ （ ｍｏｄ   ８ ））、 ｕ を、 ２ｕ が公開値 Ｇ   ＝   ｇ  ２ を ｐ に関して割り切れるようなものだが、 ２ｕ＋１ は割り切れないようなものとする ； したがって、 ｕ は ０ から ｔ−１ まで数のうちのいずれかと等しい。 ｕ   ＞   ０ と ｋ   ＋   ｕ   ＞   ｔ ならば方程式には解がない ；ｋ   ＋   ｕ ≦ ｔ ならばそれは ２ｋ 個の解を持つ ；ｕ   ＝   ０ と ｋ   ＞   ｔ ならばそれは ２ｔ 個の解を持つ。
したがって、 Ｇ がサイクルの中にまたはブランチの他の適当な位置にあるかどうかに応じて ， 互換性には ２ つのタイプがある。
・ Ｇ が ｋ の値に関係なくサイクルの中にあるとき、すなわち ｕ   ＝   ０ のとき、 ｋ の値に拠らず、そのサイクルには、奇数のランクと、α ＝   ｍｉｎ（ｋ，ｔ） によって散在するようにされた広められる偶数ランクとには、共に解があり、連続的なブランチが全部でサイクル（すなわち ２ａ 個の解）と関連がある。図 ２Ａ はこのケースを ｋ  ≧ ｔ   ＝   ３ （すなわち ９ （ ｍｏｄ   １６ ）まで適合する素因数）で図示する。そして、それはその ｕ   ＝   ０ を強要する。
・ Ｇ がブランチ（すなわち ｕ   ＞   ０ と ｕ＋ｋ ≦ ｔ ）の中に、適当な位置にあるとき、 ２ｋ の解（偶数ランクの、そして、ブランチの中の全て）がある。
図 ２Ｂ は、このケースを図示する。
パラメータ ｋ が与えられれば、 ｔ の値が ｋ 未満か、あるいは、ｋ以上かによって、 ２ 種類の素因数がある。
【０１４７】
・ｔ＜ｋの任意の素因数 ｐｊ につては、各 Ｇｉ は、はあるサイクルの中に無くてはならならず、 Ｇｉ に関連したブランチには解がない。数Δ ｉ，ｊ で、 ｇｉ，−ｇｉ がサイクルにあるかどうかによって＋１か、−１の値をとるものを定義する。ｍ個の数Δ １，ｊ 〜Δ ｍ  ，ｊ の何れであってもよい。図 ３Ａ は、ｔ＜ｋのケースを図示する： Ｇｉ は、 ９ （ ｍｏｄ   １６ ）に適合する素因数 ｐｊ （すなわち ｋ   ＞   ３ による ｕ   ＝   ０ 、 ｔ   ＝   ３ ）で、サイクルの中にある。
【０１４８】
・ｔ≧ｋの任意の素因数 ｐｊ につては、各 Ｇｉ は、 ｕ＋ｋ ≦ ｔ， つまり、 ｕ＝０ のサイクルにあるか、あるいは、 １ ≦ ｕ ≦ ｔ−ｋ のブランチの適当な場所にある。数Δ ｉ，ｊ で、 Ｑｉ，ｊ が ｇｉ，−ｇｉ に関連したグラフの場所にあるかどうかによって＋１か、−１の値をとるものを定義する。ｍ個の数Δ １，ｊ 〜Δ ｍ，ｊ には選択がある。各数Δ ｉ，ｊ は個別に、互いの間をスイッチされても良い。図 ３Ｂ は、ｔ≧ｋのケースを図示する： Ｇｉ は、１７（ ｍｏｄ ３２）に適合する素因数 ｐｊ （すなわち ｋ   ＞   ３ による ｕ   ＝   ０ 、 ｔ   ＝   ３ ）で、サイクルの中にある。
【０１４９】
ｆ 個の構成要素の各々のセット｛Δ ｉ，１    ．．． Δ ｉ，ｆ ｝は ＣＧ（ｐｊ）． の単位の平方根である。この根は、トリビアルか、 ｆ 個の構成要素が等しいかどうかに、一致していません ； 我々はそれから、 ｆ 個の構成要素の集合が一定であるか変化すると述べる。そして、それは数 ｑｉ がトリビアルという事実を表する。数 ｑｉ が些細でないとき、したがって、 ｆ 個の構成要素のセット｛Δ ｉ，１    ．．． Δ ｉ，ｆ ｝モジュールの因数分解をまとめる。したがって、秘密の構成要素 Ｑｉ，ｊ を計算する前に原則をテストすることが可能である。
【０１５０】
・公開値 Ｇｉ が素因数 ｐｊ のためにサイクルの中にあるとき、数Δ ｉ，ｊ が ＋１ または −  １ であって、によってどうか ｇｉ 、あるいは、 − 、 ｇｉ はサイクルの中にある。
。そのとき、 ｐｊ  ≡  ３ （ ｍｏｄ   ４ ）、これは Ｌｅｇｅｎｄｒｅ のシンボルである：
Δ ｉ，ｊ＝ （ ｇｉ ｜ ｐｊ ）。
【０１５１】
・公開値 Ｇｉ が素因数 ｐｊ のためにブランチの中に適当な位置にあるとき、Δ ｉ，ｊ に与えられる値は秘密の構成要素 Ｑｉ を計算することによって決定されるかもしれない。
鍵の集合の生産・パラメータ ｋ があれば、 ２ つの戦略がある。
【０１５２】
・ジェネレータが適切に ｍ が基礎を形成すると決心することを ｆ 個の素因数に要求するどちらでも、計算する。
最初の素数： ２ 、 ３ 、 ５ 、 ７ 、 ．．． は、 ｐｆ に ｆ 個の大きい素因数 ｐ１ の各々との彼らの互換性を評価することがないか調べられる。
ｇ   ＝   ２ が ｐ  ≡  ５ （ ｍｏｄ   ８ ）と、互換性を持たないけれども、 ２ はベース数の構成を始めるかもしれない。本当に、 ２ 個の数がブランチの中に類似した位置にあるとき、彼らの製品は正確に二乗値がより近いサイクルを持ってきて、サイクルにより近いである。ベース数は、個々に適切でない数を組み立てることによってそれによって得られるかもしれない。
【０１５３】
・または、ジェネレータは ｍ ベース数とビット・サイズ（たとえば、 ５１２ 、 ７６８ 、 １  ０２４ 、 １５３６ 、 ２０４８ ）と強い重さ（たとえば、 １ 、 ８ 、 １６ 、 ２４ 、 ３２ ）による １ まで連続した多くのビットが ｆ   ３   ２ を決定するためにスタンバイするようなものは因数に分解するモジュールの特性を必要とする。
Ｇ１ 、 Ｇ２ 、 ．．． 、 Ｇｍ として注意した、ベース数は、最初の素数の中に一般に現れる： ２ 、 ３ 、 ５ 、 ７ 、 １１   ．．． 、でなければ、これら、組合せは最初の素数である。別途指示しなかった限り、これらは最初の ｍ 素数である ；
Ｇ１＝２ 、 Ｇ２   ＝   ３ 、 Ｇ３   ＝５ （ Ｇ４   ＝   ７ ） ．．．ｐ  ≡  ５ （ ｍｏｄ   ８ ）が ｇ   ＝   ２ と互換性を持たない点に注意する。モジュール ｎ は、近いサイズ（すなわち ｆ によって分けられるモジュールに割り当てられるサイズ）による ｆ 個の素因数の製品である。
【０１５４】
最初の原則
パラメータ ｋ 、 ｐ１ から ｐｆ への各々の素因数と各々のベースは ｇ１ から ｇ を数える。そして、 ｇｍ は互換性を持たなければならない。 ２ｈ のような数 ｈ が ｐ に関して ｇ のランクを分けることを定義しようのに、 ２ｈ＋１ はそれを分けない。以下の手順が Ｌｅｇｅｎｄ  ｒｅ のシンボル（ ｇ ｜ ｐ ）を使って、数 ｈ を計算するために、そして、数 ｂ （ ＣＧ（ｐ）  ． での統一の最初の ２ｔ 乗根）
【０１５５】
・ （ ｇ ？ ｐ ） ｔ   ＝   １ （帰りの「 ｈ   ＝   ０ 」）で ＝   ＋   １ 。
・ （ ｇ ？ ｐ ）、 ｔ   ＞   １ による ＝   ＋   １ は、鍵 ＜（ｐ を適用する？ １ｔ ） ／２ｔ＋１ （ Ｇ への ｗ と呼ばれている結果を得るために ｐ   ＞ ）。
・ ＋ｇ   ｗ   ＝ ならば、「 ｈ   ＝   ０ 」を返する。
・ ＝ｐｇ   ｗ ならば、「 ｈ   ＝   １ 」を返する。
・他に、 ｃ を ｂ に、そして、 ｔ−１ から ２ への ｉ のために設定する、
・ 鍵 ＜２ｉ （ ｗ／ｇ （ ｍｏｄ   ｐ ）への± １ を得るために ｐ＞ ）を適用する
・  −１ が ｈ を ｉ にセットして、 ｗ を ｗ ´ ｃ （ ｍｏｄ   ｐ ）と取り替えるならば、
・  ｃ を ｃ２ （ ｍｏｄ   ｐ ）と取り替える。
・「 ２ から ｔ−１ への ｈ の値」を返する。
・（ ｇ ？ ｐ ） ＝ − １ は、「 ｈ   ＝ｔ 」を返する。
【０１５６】
ｋ 、 ｇ と ｐ が相容れないことを思い出す我々をます ｋ＋ｕ   ＞   ｔ でいつの ｕ   ＞   ０；
彼らは、互換性を持つ、 ｋ の値に関係なく、いつの ｈ   ＝   ０ または １ 、そして、等しくいつの ｋ   ｋ＋ｈ £ ｔ＋１． で ＞   １
原則の支持を表明する ３ つの以下の手順は第二の原則の異なる実施と一致する。
【０１５７】
特定の実施において、第二の原則は、 ｑｍ への各々の数 ｑ１ がトリビアルなことを必要とすることで適切に補強されるかもしれない。
ベース数の役割は、それから釣り合いる ；
第二の原則を釣り合わせることは、計画のセキュリティのデモンストレーションの特定の面の影響を持つ。
【０１５８】
最後に、 ｆ   ＞   ２ つの異なった素因数があるとき、 ｍ 番号｛ ｑ１   ．．．   ｑｍ ｝の中で、 ｆ−１ 個の独立した数の少なくともいずれかつのサブセットが存在することを義務づけられるかもしれない。
３ つの手順は、次のように定義される ｍ ´ ｆ 個の数 ｄｉ，ｊ を使う。
・ ｐｊ がすなわち １ から ｍ （ ｄｉ，ｊ   ＝  Δ ｉ，ｊ ）まで ｉ のために ＜ｋ そのようなその ｔ である、 ＋１   ｈｉ，ｊ   ＝   ０ と −１ に ｈｉ，ｊ   ＝   １ に。
・ ｐｊ が ３ｋ そのようなその ｔ であるとき、 １ からそれを意味する ｍ （ ｄｉ，ｊ   ＝   ０ ）への ｉ のために、 Ｄｍ，ｊ への Ｄ１，ｊ は第二の原則に従って選ばれるかもしれない。
【０１５９】
最初の手順は、少なくともいずれかセット｛ ｄｉ，１   ．．．   ｄｉ，ｆ ｝が変化する、あるいは、些細でないように、 ０ 、すなわちその少なくともいずれかつの数 ｑ１ 、 ｑｍ が些細でないか、選ばれるかもしれないことを確かめる。
・なぜならば、 １ から ｍ への私と １ から ｆ への ｊ 、
・ ｄｉ，ｊ   ＝   ０ または １ つの ｄｉ，１ ならば、「成功」を返する。
・「失敗」を返する。
【０１６０】
些細でないように、第二の手順は各々のセット｛ ｄｉ，１   ．．．   ｄｉ，ｆ ｝が変化することは、あるいは、 ０ がすなわち ｑｍ にとても各々 ｑ１ を数えることは些細でないことを確かめるか、選ばれるかもしれない。
・なぜならば、 １ から ｍ への私、
・  １ から ｆ への ｊ のために、
・  ｄｉ，ｊ   ＝   ０ または １ つの ｄｉ，１ が ｉ の次の値まであるきップするならば、
・ リターン「失敗」。
・「成功」を返する。
【０１６１】
第 ３ の手順は、素因数 ｐｊ１ と、 １ つのそこの£ ｊ１ £ ｊ２ £ ｆ で、 ｐｊ２ の各々のペアが ｄｉ，ｊ１ がゼロであるか ｄｉ，ｊ２ と異なる少なくともいずれかつのセット｛ ｄｉ，  １   ．．．   ｄｉ，ｆ ｝であることを確かめる。
ｍ が ｆ−１ より小さいとき、それは明らかに、失敗する。
それが成功するとき、数 ｑ１ 〜 ｑｍ への ｍ 個の数の中で、独立した ｆ−１ 番号の少なくともいずれかセットが ｆ 個の素因数に関してある。
【０１６２】
・ １ から ｆ−１ への ｊ１ のために、そして、 ｊ１＋１ から ｆ への ｊ２ のために、
・なぜならば、 １ から ｍ への私、
・  ｄｉ，ｊ１   ＝   ０ または １ つの ｄｉ，ｊ２ が ｊ１ と ｊ２ の次の値まであるきップするならば、
・「失敗」を返する。
・「成功」を返する。
手順が失敗するとき、鍵がセットする ＧＱ２ のジェネレータは ２ つの可能な戦略から選ばれるその戦略に従う：
・ ｆ 個の素因数を保つ間、 ｍ ベース・数のうちの １ 個を変えてください、
・ ｍ を保つことは数の基礎を形成する間、 ｆ 個の素因数のうちの １ つを変えてください。
第 ３ の原則（手順が分化していない ＧＱ２ 鍵（生産の間、かすでに生じられる）の集合がいるかどうか決定することになること）
一組の両方の基本の ＧＱ２ 鍵、すなわち、± ｇｍ への ２ ´ ｍ 数± ｇ１ が全ての非二次の残余であるために、
・でなければ、相補型そこの ＧＱ２ 鍵（すなわち± ｇｍ への ２ ´ ｍ 数± ｇ１ の中のそれ）の集合は、少なくともいずれかつの二次の残余である。
手順は、両方の Ｌｅｇｅｎｄｒｅ のシンボルを使う（ ｇｉ ？ ｐｊ ）、そして、（ −ｇｉ ？ ｐｊ ）、
なぜならば、 １ から ｍ まで、そして、 １ から ｆ． への ｊ のための私
・なぜならば、 １ から ｍ への私、
・ １ から ｆ への ｊ のために、
・（ ｇｉ ？ ｐｊ ） −１ 、スキップ、次が ｉ． の評価する ＝
・「相補型 ＧＱ２ 鍵の集合」を返する。
・ １ から ｆ への ｊ のために、
・（ ｇｉ ？ ｐｊ ） −１ 、スキップ、次が ｉ． の評価する ＝
・「相補型 ＧＫ２ 鍵の集合」を返する。
・「基本の ＧＫ２ 鍵の集合」を返する。
秘密の構成要素 ― 直接的なタイプの方程式のために：
【０１６３】
以下の計算が全ての可能性が秘密の構成要素 Ｑｉ，ｊ． のために高く評価すると確証する ｘｎ  ≡  ｇｉ２ （ ｍｏｄ   ｐｊ ） ２ つの最も単純で最も現在のケース（すなわち ｔ   ＝   １ と ｔ   ＝   ２ ）の後に、より複雑なケース（すなわち ｔ   ＞   ２ ）が続く。 ｔ   ＝   １ （すなわち ｐｊ  ≡  ３ （ ｍｏｄ   ４ ））のために、鍵 ＜（ｐｊ＋１）／４，ｐｊ＞ は、 ＣＧ（ｐｊ  ） で任意の二次の残余でもの二次の平方根を提供する。これから、数が引き出された ｓｊ   ｏ であること（（ ｐｊ＋１ ） ／４ ） ｋ （ ｍｏｄ  （ ｐｊ−１ ） ／２ ）、そしてそれは鍵 ＜  ｓｊ （ Ｇｉ を ｗ  ≡  Ｇｉｓｊ （ ｍｏｄ   ｐｊ ）に変えている ｐｊ＞ ）を与える。
【０１６４】
Ｑｉ，ｊ は、 ｗ または ｐｊ−ｗ と等しい。
ｔ   ＝   ２ （すなわち ｐｊ  ≡  ５ （ ｍｏｄ   ８ ）、鍵 ＜（ｐｊ＋３）／８ ）のために、 ｐｊ  ＞ は ＣＧ（ｐｊ） で奇数のランクの任意の要素のためにでも奇数のランクの平方根を提供する。
これから、数が引き出された ｓｊ   ｏ であること（（ ｐｊ＋３ ） ／８ ） ｋ （ ｍｏｄ  （ ｐｊ  −１ ） ／４ ）、そしてそれは鍵 ＜ｓｊ （ Ｇｉ を ｗ  ≡  Ｇｉｓｊ （ ｍｏｄ   ｐｊ ）に変えている ｐｊ＞ ）を与える。
２ が ＣＧ （ ｐｊ ）の中の非二次の残余であるので、 ｚ  ≡  ２（ｐｊ−１）／４ （モード ｐ  ｊ ）が −１ の平方根である点に注意しよう。
Ｑｉ，ｊ は、 ｗ にまたは ｐｊ−ｗ にまたは他に ｗ 等しい』 ｏ   ｗ ´ ｚ （ ｍｏｄ   ｐｊ ）または ｐｊ−ｗ 』。
【０１６５】
ｔ   ＞   ２ による ｐｊ  ≡  ２ｔ＋１ （ ｍｏｄ   ２ｔ＋１ ）のために、 ＜（ｐｊ−１＋２ｔ に鍵をかけること） ２ｔ＋１／ 、 ｐｊ＞ は奇数のランクの任意の要素でもの奇数のランクの平方根を提供する。 ｋ 、 ｇ と ｐ の間の互換性テストは、 ｈ （次に ｕ のそれ）の値を与えた。
・ Ｇｉ がサイクル（ ｋ の値に関係なく、 ｕ   ＝   ０ ）の中にあるとき、数は確立される、 ｓ  ｊ  ≡（（ ｐｊ−１＋２ｔ ） ／２ｔ＋１ ） ｋ （ ｍｏｄ  （ ｐｊ−１ ） ／２ｔ ）。
鍵 ＜ｓｊ 、 ｐｊ＞ は Ｇｉ を変わった全くの ｗ  ≡  Ｇｉｓｊ （ ｍｏｄ   ｐｊ ）の解答に変える。配布される偶数ランクの解答が ｍｉｎ（ｋ にある、 ｔ） 連続的なブランチはサイクルに関連がありました、ブランチでは、言おう。 Ｑｉ，ｊ は、 ＣＧ（ｐｊ） で統一の ２ａｔ  ｈ 根のどれにでもよって、 ｗ の製品と等しい。
・ Ｇｊ がブランチ（ ｕ   ＞   ０ （ ｕ   ＋   ｋ £ ｔ ））の中に、適当な位置にあるとき、全ての解が Ｇｊ 、関連したブランチ、数の ２ｕｔｈ べき乗によるサイクルと同じブランチにあって、数につき ｇｉ． 確立する
ｓｊ  ≡（（ ｐｊ−１＋２ｔ ） ／２ｔ＋１）ｋ＋ｕ （ ｍｏｄ  （ ｐｊ−１ ） ／２ｔ．
＜ｓｊ に鍵をかけてください、 ｐｊ＞ は多くの変わったランク ｗ に Ｇｉ の ２ｕｔｈ べき乗を変換する。
【０１６６】
ＣＧ（ｐｊ） での統一の最初の ２ｋ＋ｕ 乗根による ｗ の製品の集合は、 Ｑｉ，ｊ の ２ｋ の値から成る。数 ｂｊ が ＣＧ（ｐｊ） での統一の最初の ２ｔ 乗根であって、 ｐｊ が ３ｋ そのようなその ｔ であるとき、 ＣＧ（ｐｊ） での ｂｊ の ２ｔｕ 乗べき乗が存在する ；
これは、統一の最初の ２ｋｔｈ 根である。数Δ ｉ，ｊ の値は、 Ｑｉ，ｊ に統一の最初の ２  ｋ 乗根を掛けることによって変えられるかもしれない。
【０１６７】
逆のタイプの方程式のために：
１  ≡  ｘｎ ´ ｇｉ２ （ ｍｏｄ   ｐｊ ）、それは数 ｓｊ を取り替えるのに十分であるで（（ ｐｊ−１ ） ／２ｔ ） −ＣＧ（ｐｊ）． で Ｑｉ，ｊ の値を逆にすることに達する鍵 ＜ｓｊ （ ｐｊ＞ ）で ｓｊ 適合する ２ つの素因数による一組の鍵の例
【数１４９】
2004527139.tif 000077
Ｄ１ は、非常に最初の素数の Ｌｅｇｅｎｄｒｅ シンボルである。
【数１５０】
2004527139.tif 000078
ＣＧ（ｐ１） で、ランクは −５ 、 −１１ と １７ のために変わっている。
【数１５１】
2004527139.tif 000079
ＣＧ（ｐ２） で、ランクは ３ 、 −５ 、 ７ と １１ のために変わっている。カーマイケルの関数は、
【数１５２】
2004527139.tif 000080
【０１６８】
逆のタイプの一般的な方程式を使用するために、より麻痺した ｓ  ≡  ｌ（ｎ）−（（１＋  ｌ（ｎ））／２）９ （ ｍｏｄ   ｌ（ｎ） ）が、秘密の指数値として使われる。
【数１５３】
2004527139.tif 000081
【０１６９】
番号 ２ 、 ３ 、 ７ 、 １３ と １７ は、ベース数として適当ではない。
鍵 ＜ｓ，ｎ＞ は、 ｇ１   ＝   ５ を少しの因数分解も表さない秘密の数 Ｑ１ に変える。
本当に、両方のフィールドでは、 −５ はあるサイクルにある。
【数１５４】
2004527139.tif 000082
【０１７０】
鍵 ＜ｓ，ｎ＞ は、 ｇ２   ＝   １１ を因数分解を示す秘密の数 Ｑ２ に変える。
本当に、 １１ が両方のフィールドに同じ位置にあるというわけではない。
【数１５５】
2004527139.tif 000083
【０１７１】
鍵 ＜ｓ，ｎ＞ は、 ｇ３   ＝   ２１   ＝   ３ × ７ を因数分解を示す秘密の数 Ｑ３ に変える。
【数１５６】
2004527139.tif 000084
【０１７２】
鍵 ＜ｓ，ｎ＞ は、 ｇ４   ＝   ２６   ＝   ２ × １３ を因数分解を示す秘密の数 Ｑ４ に変える。
【数１５７】
2004527139.tif 000085
【０１７３】
秘密鍵がさらに、チャイニーズ剰余法パラメータと ８ つのの構成要素の両方で表されるかもしれない。
【数１５８】
2004527139.tif 000086
【０１７４】
秘密鍵 ＧＱ２ が等しいことを証明する秘密鍵で異なる可能な表現の多形性：
彼ら全ては、実際の ＧＫ２ 秘密鍵であるモジュール ｎ の因数分解を知っていることに達する。 ＧＱ２ 秘密鍵の表現は、エンティティを制御することの範囲内で以外エンティティを示さないことの範囲内で計算の進捗に影響を及ぼする。 ＧＱ２ 秘密鍵にとって可能である ３ つの主な表現は、ここにある。 １ ）、 ＧＱ 秘密鍵の従来の表現は、鍵 ＜ｎ （ ｎ＞ ）をチェックしている ｍ 秘密の数 Ｑｉ と公開を保存することにある ；ＧＱ２ 計画のために、この表現は、以下 ２ と競争してある。 ２ ）、作業負荷に関する最適の表現は、パラメータ ｋ 、 ｆ 個の素因数 ｐｊ 、 ｍ ´ ｆ 秘密の構成要素 Ｑｉ，ｊ とチャイニーズ剰余法の ｆ−１ パラメータを格納することにある。 ３ ）、最適の中で表現は、チャイニーズ剰余法のそれが第二の表現に達するように秘密の構成要素 Ｑｉ，ｊ と ｆ−１ パラメータをサイズがそれが最初の表現または ｍ ´ ｆ に達するように、どちらの ｍ 秘密の数 Ｑｉ でもとモジュール ｎ を確立して、パラメータ ｋ 、 ｍ ベース数 ｇｉ と ｆ 個の素因数 ｐｊ を保存する際に、そして、それから各々の使用を始める際にある秘密鍵であると言える。
【０１７５】
ダイナミックな真性性メカニズムのまたはディジタル署名のセキュリティがモジュールの因数分解を知ることに等しいので、 ＧＱ２ 計画で、とても同じモジュールを使用している ２ つのエンティティを識別することが可能ではない。
【０１７６】
通常、各々の証明エンティティは、それ自身の ＧＱ２ モジュールを持つ。しかし、 ４ つの素因数による ＧＱ２ モジュールは、指定されるかもしれない、どちらがもう １ までエンティティと他 ２ に知られているか ２ つ。ダイナミックな真性性−ダイナミックな真性性メカニズムはコントローラ（可能な関連するメッセージ Ｍ のコントローラがそれが実際にデモンストレータと任意にそれを扱っていることを確かめるように真性性と同様にデモンストレータと呼ばれているもう一つのエンティティの真性性）と呼ばれているエンティティに証明することのためであるそれ自体、そして、デモンストレータ、同じメッセージ Ｍ． について話すことは関連するメッセージ Ｍ であるオプションである、そしてそれはそれが空かもしれないことを意味する。
【０１７７】
ダイナミックな真性性メカニズムは、 ４ つの行為のシーケンスである：
約束行為、チャレンジ行為、応答行為とチェックは、行いる。
実演者は、約束と応答行為をする。コントローラはチャレンジを演奏する、そして、チェックすることは行いる。デモンストレータの範囲内で、最も機密パラメータと実演者（すなわちコミットメントと応答の成果）の関数を孤立させるために、証人は孤立するかもしれない。証人はパラメータ ｋ と ＧＱ２ 秘密鍵を持つ。そして、 ３ つの表現のうちの １ つに従うモジュール ｎ の因数分解がすなわち上で言及される： ｆ 個の素因数と ｍ が基礎を形成する・は、数える、・ ｍ ´ ｆ 秘密の構成要素、 ｆ 個の素因数、そして、 ｆ−１ チャイニーズ剰余法、秘密の ｍ が数える・とモジュール ｎ． のパラメータ‖証人は、特定の具体化（たとえばチップカードが一緒にデモンストレータを作っている ＰＣ または特に ＰＣ の範囲内で保護されている・プログラムにさえ接続した・または特にチップカードの範囲内で保護されている・プログラムさえ）と一致するかもしれない。
【０１７８】
それによって孤立した証人は、署名しているエンティティの範囲内でこの後定義される証人と類似している。メカニズムの各々の遂行に、証人は一つ以上のコミットメント Ｒ を生産する、それから、多くの応答として、さらに同じだけへの Ｄ は ｄ にチャレンジする。各々のセット｛ Ｒ 、 ｄ 、 Ｄ ｝は、 ＧＱ２ トリプレットを作る。それに加えて証人を含んで、必要に応じて、デモンストレータもハッシュしている関数とメッセージ Ｍ を持つ。たとえば、コントローラは公開鍵のディレクトリからまたは公開鍵証明書からさえモジュール ｎ を持つ ； 必要ならば、それも同じものを関数とメッセージ Ｍ をハッシュするようにする』。 ＧＱ２ 公開されているパラメータ、すなわち数 ｋ 、 ｍ と ｇｍ への ｇ１ は、デモンストレータによってコントローラに提供されるかもしれない。
【０１７９】
コントローラは、コミットメント Ｒ を再建することができる』、コントローラは任意のチャレンジ ｄ からでも、そして、任意の応答 Ｄ． パラメータ ｋ でもと ｍ から密告する。別途指示しなかった限り、 ｇ１ から ｇｍ への ｍ ベース数は最初の ｍ 素数である。各々のチャレンジ ｄ は、基本のチャレンジが ｄ１ から ｄｍ． までリファレンスをつけた ｍ を含まなければならない：
ベース数につき人。 ｄ１ から ｄｍ． への各々の基本のチャレンジは、 ０ から ２ｋ−１−１ （ ｎ／２ から ｎ−１ への数が、使われません）への数である。
一般的に、各々のチャレンジは、 ｍ 時間 ｋ−１ ビット（そして、 ｍ 時間 ｋ ビットでない）でコード化される。たとえば、 ｋ   ＝   ５ と ｍ   ＝   ４ で数、 ５ 、 １１ 、 ２１ と ２６ の基礎を形成する、各々のチャレンジは ４ 人のカルテットの上で送られる １６ のビットを含む。
【０１８０】
そのとき、可能であるもの‖（ ｋ−１） ´ ｍ チャレンジは、等しくありえる、数（ ｋ−１  ） ´ ｍ は、各々の ＧＱ２ トリプレットによって持ってこられるセキュリティを決定する：
【０１８１】
その通り、定義によるモジュール ｎ の因数分解を知らない詐称者は、 ２（ｋ−１） ´ ｍ から成功の １ つのチャンスを持つ。 Ｗｈｅｎ（ｋ−１） ´ ｍ は １５ から ２０ まである。そして、トリプレットが合理的に十分であるものがダイナミックな真性性を確実にする。セキュリティの任意のレベルでも成し遂げるために、トリプレットは平行に生産されるかもしれない ； 彼らはまた、順番に生産されるかもしれない、すなわち、メカニズムの遂行を繰り返する。 １）  コミットメントの行為は、以下の演算から成る。証人がチャイニーズ剰余法を使わないとき、それはパラメータ ｋ （ Ｑ１ から Ｑｍ とモジュール ｎ への ｍ 秘密の数）を持つ ； それは、ランダムに、そして、私的に一つ以上の乱数 ｒ （ ０ の ＜   ｒ   ＜   ｎ ）を選びます ；
【０１８２】
それから、彼らを連続して二乗値にすることによって、 ｋ は時間を計る（ ｍｏｄ   ｎ ）、それは各々の乱数 ｒ を変えるコミットメント Ｒ．
ここの Ｒ  ≡  ｒｎ （ ｍｏｄ   ｎ ）は、チャイニーズ剰余法のない鍵の前の集合と一緒の例である。
【０１８３】
証人がチャイニーズ剰余法を使う、それが持つ
【数１５９】
2004527139.tif 000087
【０１８４】
パラメータ ｋ 、 ｐ１ から ｐｆ への最初の ｆ 個の素因数、チャイニーズ剰余法の ｆ−ｌ パラメータ、そして、 ｍ ´ ｆ 秘密の構成要素 Ｑｉ，ｊ；
それは、ランダムに、そして、私的に ｆ 乱数の一つ以上のコレクションを選びます：あらゆるコレクションは、素因数パイ（ ０ の ＜   ＜ｒｉ パイ）につき、 １ つの乱数 ｒｉ を含む ； それから、それを連続して二乗することによって、 ｋ は時間を計る（ ｍｏｄ  パイ）、それは各々の乱数 ｒｉ を変えるコミットメント構成要素 Ｒｉ．ｆ コミットメント構成要素の各々のコレクションのための
【数１６０】
2004527139.tif 000088
【０１８５】
証人はチャイニーズ剰余法テクニックにコミットメントを確立する。
そこで、あるのと、同じくらい多くのコミットメントが乱数コレクション、鍵の前の集合と一緒の、そして、チャイニーズ剰余法による例は、ここにある。
【数１６１】
2004527139.tif 000089
【０１８６】
双方ともの中の
【数１６２】
2004527139.tif 000090
【０１８７】
が下見する、デモンストレータがコントローラ、各々のコミットメント Ｒ のどちらの全部または一部でもまたは他に、各々のコミットメント Ｒ とメッセージ Ｍ． をハッシュすることによって得られるハッシュしているコード Ｈ に送るチャイニーズ剰余法（ Ｒ１，Ｒ２ ）
２）  チャレンジの行為は一つ以上のチャレンジ ｄ をランダムに選ぶことにある。そして、各々 ｍ 基本のチャレンジ ｄ１ 、 ｄ２ 、… ｄｍ． から成る ；
各々の基本のチャレンジジ、 ０ から ｎ／２−１ への数の人は、そうである。
ここの ｄ   ＝ｄ１   ｄ２ … ｄｍ． は、両方の例（すなわち ｋ   ＝   ５ と ｍ   ＝   ４ に賛成の）のためのチャレンジである。
【数１６３】
2004527139.tif 000091
【０１８８】
コントローラが各々送るのは、デモンストレータに ｄ にチャレンジする。
３）  応答の行為は、以下の演算を含む。
証人がチャイニーズ剰余法を使わないとき、それはパラメータ ｋ （ Ｑ１ から Ｑｍ とモジュール ｎ への ｍ 秘密の数）を持つ ；
それは、基本のチャレンジによってコミットメント行為と秘密の数から各々の乱数 ｒ を用いて一つ以上の応答 Ｄ を計算する。
ここの
【数１６４】
2004527139.tif 000092
がチャイニーズ剰余法のない例の継続であることをする。
【０１８９】
証人がチャイニーズ剰余法を使う、それが持つ
【数１６５】
2004527139.tif 000093
【０１９０】
パラメータ ｋ 、 ｐ１ から ｐｆ への ｆ 個の素因数、 ｆ−１ チャイニーズ剰余法パラメータ、そして、 ｍ ´ ｆ 秘密の構成要素 Ｑｉ，ｊ；
それは、コミットメント行為から乱数の各々のコレクションを用いて ｆ 応答構成要素の一つ以上のコレクションを計算する：
【数１６６】
2004527139.tif 000094
応答構成要素の各々のコレクションは、素因数につき １ つの構成要素を含む。
【０１９１】
応答構成要素の各々のコレクションのために ｒｉ ´ Ｑ１，ｉｄ１ ´ Ｑ２，ｉｄ２ ´… Ｑｍ  ，ｉｄｍ （ ｍｏｄ  パイ）をする、証人はチャイニーズ剰余法テクニックによって応答を確立する。
そこで、チャレンジであるのと、同じくらい多くの応答が、ある。
Ｄ   ＝Ｃｈｉｎｅｓｅ   ｒｅｍａｉｎｄｅｒｓ（Ｄ１ 、 Ｄ２ 、… Ｄｆ ）、チャイニーズ剰余法のない例の継続は、ここにある。
【数１６７】
2004527139.tif 000095
両方のケースには、デモンストレータは各々の応答 Ｄ をコントローラに送る。
【０１９２】
４）  チェックすることの行為は、各々のトリプレット｛ Ｒ 、 ｄ 、 Ｄ ｝がゼロ以外の値のために以下のタイプの方程式を満たすことを確認することにある。
【数１６８】
2004527139.tif 000096
または各々のコミットメントをはやりに元に戻すこと：
彼らの誰も、ゼロでないにちがいある。
【数１６９】
2004527139.tif 000097
任意に、コントローラはそれからハッシュしているコード Ｈ を計算する』各々の回復するコミットメント Ｒ をハッシュすることによって』、そして、メッセージ Ｍ 』。ダイナミックな真性性が、成功しているコントローラがこのようにそれがコミットメント行為（すなわち各々のコミットメント Ｒ の全部若しくは一部またはハッシュしているコード Ｈ． ）終了後、受けたものを取り戻すとき、たとえば、基本の演算のシーケンスは、応答 Ｄ をコミットメント Ｒ に変える』。シーケンスは、ベース数によって ｋ−１ 分割または掛け算（モード ｎ ）によって切り離される ｋ 二乗値（ ｍｏｄ   ｎ ）から成る。
【０１９３】
分割または掛け算（二乗値と ｉ＋１−ｔｈ が二乗値にする、 ｉ−ｔｈ が基本のチャレンジ ｄ１ の噛んだ ｉ−ｔｈ の間で、それは実行される）が示す ｉ−ｔｈ のために ｇ１ が使われなければならないならば、基本のチャレンジ ｄ２ の ｉ−ｔｈ なビットが ｇ２ が使われなければならないかどうか示すこと、 ．．． 噛まれる ｉ−ｔｈ 次第の基本の ｄｍ． 、 ｇｍ が使われなければならないかどうか示する。
以上がチャイニーズ剰余法のない例である。
【数１７０】
2004527139.tif 000098
は、四角のモジュロｎをとる：
【数１７１】
2004527139.tif 000099
が ５ つの時間 ２６   ＝   １３０ （すなわち ’８２ ）までに、増やす
【０１９４】
四角のモジュロｎをとる：
【数１７２】
2004527139.tif 000100
０７ は、 ２１ を掛ける。
【数１７３】
2004527139.tif 000101
すなわち ’１５ 』モジュロｎ：
【数１７４】
2004527139.tif 000102
四角のモジュロｎをとる：
【数１７５】
2004527139.tif 000103
１１ の ５ 回時間 ２１   ＝   １１５５
【数１７６】
2004527139.tif 000104
（すなわち『 ４８３ 』のモジュロｎ）までに、増やす：
【数１７７】
2004527139.tif 000105
は、 １１ の ５ 回時間 ２６   ＝   １４３０ （すなわち『 ５９６ 』のモジュロｎ）までに、
【数１７８】
2004527139.tif 000106
四角のモジュロｎをとる：
【数１７９】
2004527139.tif 000107
３Ａ 、コミットメント ｒ は、取り戻される。
真性性は、成功している。
チャイニーズ剰余法による例の終わりは、ここにある。
【０１９５】
【数１８０】
2004527139.tif 000108
は、四角のモジュロｎをとる：
【数１８１】
2004527139.tif 000109
５ つの時間 ２６   ＝   １３０ （すなわち ’８２ ）までに増える
【数１８２】
2004527139.tif 000110
四角のモジュロｎをとる：
【０１９６】
【数１８３】
2004527139.tif 000111
２１ を掛ける。すなわち ’１５’ モジュロｎ：
【数１８４】
2004527139.tif 000112
四角のモジュロｎをとる：
【数１８５】
2004527139.tif 000113
【０１９７】
１１ の ５ 回時間 ２１   ＝   １１５５ （すなわち『 ４８３ 』のモジュロｎ）までに、増やす：
【数１８６】
2004527139.tif 000114
四角のモジュロｎをとる：
【数１８７】
2004527139.tif 000115
１１ の ５ 回時間 ２６   ＝   １４３０ （すなわち『 ５９６ 』のモジュロｎ）までに、増やする：
【数１８８】
2004527139.tif 000116
【０１９８】
四角のモジュロｎをとる：
【数１８９】
2004527139.tif 000117
コミットメント ｒ は、正しく取り戻される。真性性は、成功している。
ディジタル署名しているメカニズムが署名しているエンティティと呼ばれているエンティティに生じるのを可能にするディジタル署名はメッセージに署名した、そして、確かめるコントローラと呼ばれているエンティティはメッセージに署名した。メッセージ Ｍ は、任意のバイナリのシーケンスである：それは、空かもしれない。
メッセージ Ｍ は署名アペンディクスをそれに加えることによって署名される。そして、それは一つ以上のコミットメントやチャレンジ（対応する応答と同様に）から成る。たとえば、コントローラは公開鍵のディレクトリからまたは公開鍵証明書からさえモジュール ｎ を持つ ； それも、同じものを関数をハッシュするようにする。彼らを署名アペンディクスに入れることによる例のために、 ＧＱ２ 公開されているパラメータ、すなわち数 ｋ 、 ｍ と ｇｍ への ｇ１ はデモンストレータによってコントローラに与えられるかもしれない。数 ｋ と ｍ は、コントローラに知らせます。
【０１９９】
ｄ１ から ｄｍ． への各々の基本のチャレンジは、一方、 ０ から ２ｋ−１−１ （ ｎ−１ への数 ｎ／２ が、使われません）への数である。各々のチャレンジ ｄ は、他方多くであるように、ベース数があって、基本のチャレンジが ｄ１ から ｄｍ． までリファレンスをつけた ｍ を含まなければならない。
さらに、別途指示しなかった限り、 ｍ ベース数は ｇ１ から ｇｍ まで最初の ｍ 素数である。で（ ｋ−１） ´ ｍ が １５ から ２０ まであって、平行に生産される ４ 匹の ＧＱ２ トリプレットと署名することが可能である ；
で（ ｋ−１ ）´ ｍ が ６０ 以上であって、 １ 匹の ＧＱ２ トリプレットだけと署名することが可能である。たとえば、 ｋ   ＝   ９ と ｍ   ＝   ８ で、 １ 匹の ＧＱ２ トリプレットだけは、十分である ；
【０２００】
各々のチャレンジは ８ バイトを含む、そして、ベース数は ２，３，５，７，１１，１３，  １７ と １９ である。
署名している演算は、 ３ つの行為のシーケンスである：
コミットメント行為、チャレンジ行為と応答は、行いる。
各々の行為は、各々成り立っている一つ以上の ＧＱ２ トリプレットを生産する：
【０２０１】
コミットメント ｒ （ １   ０ ）（基本のチャレンジが ｄ１ によってリファレンスをつけた ｍ からなるチャレンジ ｄ ） ｄ２ 、 ．．．ｄｍ． 、そして、応答 Ｄ （ １   ０ ）。
すなわち、署名しているエンティティはハッシュしている関数、パラメータ ｋ と ＧＱ２ 秘密鍵を持つ。そして、 ３ つの表現のうちの １ つに従うモジュール ｎ の因数分解が上で言及される。
【０２０２】
署名しているエンティティの範囲内で、コミットメントを実行する証人を孤立させることが可能である、そして、応答はデモンストレータの最も機密関数とパラメータを孤立させるために行いる。
コミットメントと応答を計算するために、証人はパラメータ ｋ と ＧＱ２ 秘密鍵（すなわち ３ つの表現が上で言及した人に従うモジュール ｎ の因数分解）を持つ。
【０２０３】
それによって孤立した証人はデモンストレータの範囲内で定義される証人と類似している。それは特定の具体化（例、チップカードが一緒に署名しているエンティティをつくっている ＰＣ に接続した・または特に ＰＣ の範囲内で保護されている・プログラムさえのためであるか平らな）と一致するかもしれない特にチップカードの範囲内で保護されている・プログラム。
【０２０４】
１ ）コミットメントの行為は、以下の演算から成る。
証人が Ｑｍ とモジュール ｎ に ｍ 秘密の数 Ｑ１ を持つとき、それはランダムに、そして、私的に一つ以上の乱数 ｒ （ ０ の ＜   ｒ   ＜   ｎ ）を選びます ；
それから、 ｋ 連続した ｓｑｕａｒｉｎｇｓ （モード ｎ ）によって、それは各々の乱数 ｒ をコミットメント Ｒ に変える。
証人が ｐｆ への ｐ１ と ｍ ´ ｆ 個の秘密の構成要素 Ｑ１，ｊ （ ｆ 個の乱数のランダムにそれと私的に選択一つ以上コレクション）から ｆ 個の素因数を持つ
【数１９０】
2004527139.tif 000118
各々のコレクションは、素因数パイ（ ０ の ＜   ＜ｒｉ   ｐ１ ）につき、乱数 ｒｉ を含む ； それから、 ｋ 連続した ｓｑｕａｒｉｎｇｓ （ ｍｏｄ  パイ）、それは各々の乱数 ｒｉ を証人がチャイニーズ剰余法テクニックにコミットメントを確立するコミットメント構成要素 Ｒ  ｉ （ ｆ 個のコミットメント構成要素の各々のコレクションのための
【０２０５】
【数１９１】
2004527139.tif 000119
に変える。
そこで、乱数コレクションであるのと、同じくらい多くのコミットメントが、ある。
【数１９２】
2004527139.tif 000120
【０２０６】
２）チャレンジの行為は、署名しているエンティティが各々の基本の ｍ を含むことはチャレンジする一つ以上のチャレンジを作るハッシュしているコードを得るために署名されるために全てのコミットメント ｒ とメッセージ ｍ をハッシュすることにある ；
各々の基本のチャレンジは、 ０ から ｎ／２−１ への数である ；
たとえば、 ｋ   ＝   ９ と ｍ   ＝   ８ で、各々のチャレンジは、 ８ バイトを含む。
そこで、コミットメントであるのと、同じくらい多くのチャレンジが、ある。
ｄ   ＝ｄ１ （ ｄ２ ） ．．．   ｄｍ． （ Ｈａｓｈ（Ｍ （ Ｒ ）結果 ３） から引き出される））
【０２０７】
３）応答の行為は、以下の演算を含む。
証人が ｍ 秘密の数 Ｑ１ を持つとき、 Ｑｍ とモジュール ｎ にとって、それは基本のチャレンジによってコミットメント行為と秘密の数の各々の乱数 ｒ を用いて、一つ以上の応答 Ｄ を計算する。
【０２０８】
【数１９３】
2004527139.tif 000121
証人が ｐ１ から ｐｆ と ｍ ´ ｆ 個の主要な構成要素 Ｑｉ，ｊ まで ｆ 個の素因数を持つ、それがコミットメントから乱数の各々のコレクションを使うに際して ｆ 個の応答構成要素の一つ以上のコレクションが行うと思う
【数１９４】
2004527139.tif 000122
応答構成要素の各々のコレクションは応答構成要素の各々のコレクションのための素因数× ｏ   Ｑ１，ｉｄ１ ´ Ｑ２，ｉｄ２ ´… Ｑｍ，ｉｄｍ （ ｍｏｄ  パイ）ダイ ｏ   ｒｉ ´クシー（ ｍｏｄ  パイ）につき、 １ つの構成要素を含む、証人はチャイニーズ剰余法テクニックによって応答を確立する。
【０２０９】
そこで、チャレンジであるのと、同じくらい多くの応答が、ある。
署名しているエンティティが署名アペンディクスを加えて、メッセージ Ｍ に署名する Ｄ   ＝Ｃｈｉｎｅｓｅ 余り（ Ｄ１ （ Ｄ２ ） ．．．   Ｄｆ ）は、以下を含む：
・どちらか各々の ＧＱ２ トリプレット（すなわち各々のコミットメント Ｒ 、各々のチャレンジ ｄ と各々の応答 Ｄ ）
・または各々のコミットメント Ｒ と各々の対応する応答 Ｄ 、
・または各々のチャレンジ ｄ と各々の対応する応答 Ｄ．
確認演算のランニングは、署名アペンディクスの内容に依存する。
３ つのケースは、識別される。
【０２１０】
付録は、そうしなければならない一つ以上のトリプレット（作動が年代順配列が無関心である ２ つの独立したプロセスを含むことを確認すること）を成る。
【０２１１】
コントローラは、署名されたメッセージもしもともしもだけを扱いると、両方の以下の条件が納得する。
第１に、各々のトリプレットは、整合的でなければならなく（以下のタイプの適当な関係は、確かめられなければならない）て許容できなければならない（比較は、ゼロ以外の値の上でされなければならない）。
【数１９５】
2004527139.tif 000123
応答 Ｄ は、基本の演算のシーケンスによって変わる：
ｋ 二乗値（ ｍｏｄ   ｎ ）は、ベース数によって ｋ−ｌ 掛け算または分割演算（ ｍｏｄ   ｎ ）によって分かれました。
ｉ−ｔｈ な二乗値と ｉ＋ 第 １ の二乗値の間で実行される、基本のチャレンジ ｄ１ の ｉ−ｔ  ｈ なビットが示す ｉ−ｔｈ な掛け算または分割のためにそれが ｇ１ を使うのに必要であるかどうかに関係なく、基本のチャレンジ ｄ２ の ｉ−ｔｈ なビットがそれが基本のチャレンジの ｉ−ｔｈ なビットに、 ｇ２ 、 ．．． を使い果たすのに必要かどうか示すこと ｄｍ． 、それがグラムを使うのに必要かどうか示する
【０２１２】
それは、このように署名アペンディクスにおいて各々のコミットメント Ｒ プレゼントを取り戻すのに必要である。
さらに、トリプレットまたはトリプレットは、メッセージ Ｍ にリンクされなければならない。
全てのコミットメント Ｒ とメッセージ Ｍ をハッシュすることによって、ハッシュしているコードは、各々のチャレンジ ｄ は回復されてどちらでなければならないかについて得られる。
ｄ   ＝ｄ１   ｄ２ … ｄｍ （結果 Ｈａｓｈ（Ｍ （ Ｒ ） ） から引き出されるそれらと同一の）。
【０２１３】
付録には難問がないならば、チェックしている演算は一つ以上のチャレンジ ｄ の還元から始める』全てのコミットメント Ｒ とメッセージ Ｍ． をハッシュすることによって
ｄ   ＝ｄ’１   ｄ’２ … ｄ’ｍ （結果 Ｈａｓｈ（Ｍ （ Ｒ ） ） から引き出される）。
それから、各々のトリプレットが整合的（以下のタイプの適当な関係は、確かめられる）で許容できる（比較は、ゼロ以外の値の上でされる）場合に限り、コントローラは署名されたメッセージを扱う。
【０２１４】
【数１９６】
2004527139.tif 000124
そうしなければならない付録が、コミットメント（一つ以上のコミットメント Ｒ の還元によるチェックしている作動スタート）から成りません』以下の ２ つの公式（すなわち、適切であるもの）のうちの １ つによって。再確立されたコミットメントは、ゼロであってはならない。
【０２１５】
【数１９７】
2004527139.tif 000125
コントローラが、全てのコミットメント Ｒ をハッシュしなければならない』各々のチャレンジ ｄ を再構成するためにメッセージ Ｍ を、そして。 ｄ   ＝ｄ１   ｄ２   ．．．   ｄｍ． （結果ハッシュ（ Ｍ （ Ｒ ）』）から抜き取られるそれらと同一の）。各々の再構成されたチャレンジが付録において対応するチャレンジと同一の場合に限り、コントローラは署名されたメッセージを扱う。
【国際公開パンフレット】
2004527139.tif 000199
2004527139.tif 000200
2004527139.tif 000201
2004527139.tif 000202
2004527139.tif 000203
2004527139.tif 000204
2004527139.tif 000205
2004527139.tif 000206
2004527139.tif 000207
2004527139.tif 000208
2004527139.tif 000209
2004527139.tif 000210
2004527139.tif 000211
2004527139.tif 000212
2004527139.tif 000213
2004527139.tif 000214
2004527139.tif 000215
2004527139.tif 000216
2004527139.tif 000217
2004527139.tif 000218
2004527139.tif 000219
2004527139.tif 000220
2004527139.tif 000221
2004527139.tif 000222
2004527139.tif 000223
2004527139.tif 000224
2004527139.tif 000225
2004527139.tif 000226
2004527139.tif 000227
2004527139.tif 000228
2004527139.tif 000229
2004527139.tif 000230
2004527139.tif 000231
2004527139.tif 000232
2004527139.tif 000233
2004527139.tif 000234
2004527139.tif 000235
2004527139.tif 000236
2004527139.tif 000237
2004527139.tif 000238
2004527139.tif 000239
2004527139.tif 000240
2004527139.tif 000241
2004527139.tif 000242
2004527139.tif 000243
2004527139.tif 000244
2004527139.tif 000245
2004527139.tif 000246
2004527139.tif 000247
2004527139.tif 000248
2004527139.tif 000249
2004527139.tif 000250
2004527139.tif 000251
2004527139.tif 000252
2004527139.tif 000253
2004527139.tif 000254
2004527139.tif 000255
2004527139.tif 000256
2004527139.tif 000257
2004527139.tif 000258
2004527139.tif 000259
2004527139.tif 000260
2004527139.tif 000261
2004527139.tif 000262
2004527139.tif 000263
2004527139.tif 000264
2004527139.tif 000265
2004527139.tif 000266
2004527139.tif 000267
2004527139.tif 000268
2004527139.tif 000269
2004527139.tif 000270
2004527139.tif 000271
2004527139.tif 000272
2004527139.tif 000273
2004527139.tif 000274
2004527139.tif 000275
2004527139.tif 000276
2004527139.tif 000277
2004527139.tif 000278
2004527139.tif 000279
2004527139.tif 000280
2004527139.tif 000281
2004527139.tif 000282
2004527139.tif 000283
2004527139.tif 000284
2004527139.tif 000285
2004527139.tif 000286
2004527139.tif 000287
2004527139.tif 000288
2004527139.tif 000289
2004527139.tif 000290
2004527139.tif 000291
2004527139.tif 000292
2004527139.tif 000293
2004527139.tif 000294
2004527139.tif 000295
2004527139.tif 000296
2004527139.tif 000297
2004527139.tif 000298
2004527139.tif 000299
2004527139.tif 000300
【国際調査報告】
2004527139.tif 000301
2004527139.tif 000302
2004527139.tif 000303
2004527139.tif 000304
2004527139.tif 000305
2004527139.tif 000306