(57)【要約】      （修正有）【課題】エンティティの真正性、及び／又はメッセージの完全性、及び／又は真正性を証明するように設計された方法、システム及びデバイスに関し、セキュリティおよび性能の両面で、従来のＲＳＡ技術の欠点を回避する。【解決手段】秘密のＱiと公開のＧi＝ｇi2によるｍ組の値（ｍ≧１）と、ｆ個（ｆ＞２）の素数の因子の積により形成される公開のモジュールｎと、ＧiＱiv≡１mod ｎまたはＧi≡Ｑivmod ｎの関係により関連付けされた、べきｖ＝２k（ｋ＞１）とによって証明を行なう。【選択図】図１
2008048451.tif 000002
【特許請求の範囲】
【請求項１】
あるコントローラ・エンティティに対して、
・ あるエンティティの真正性、および／または、
・ 該エンティティと関連するメッセージMの完全性
を証明するようにされている方法であって、以下のパラメータ、
・ 秘密の値Q1、Q2、... 、Qmと公開値G1、G2、...、 Gm（ｍは1以上）のm個の組と、
・ f個の素因数p1、p2、... pfの積で構成される公開のモジュラスn（fは2以上）、
の全部若しくは一部またはこれらのパラメータからの算出値を用いるものであり、
前記モジュラスと前記秘密値と公開値とには次のタイプの関係があり、
【数１】
2008048451.tif 000133
ここで、ｖは
【数２】
2008048451.tif 000134
のタイプの公開値である指数値を表し（ｋは１より大きいセキュリティパラメータ）、
前記ｍ個の公開値Giは、ｍ個の区別できるベース数g1、g2、…gmの、f個の素因数p1、p2、…pfより小さい二乗値ｇi2であり、
前記p1、p2、…pfの素因数、および／または、ｍ個のベース数g1、g2、…gmは以下の条件が満たされるように生成される方法。
［第１の条件］
各方程式
【数３】
2008048451.tif 000135
がモジュロｎの整数環におけるｘについて解を持つこと。
［第２の条件］
Gi(Qiv mod nである場合、Qiを二乗してモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）、
Gi.Qiv (１mod nである場合、Qiのモジュロｎを二乗したもののインバースのモジュロnをk-1回とって得られるｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）。
［第３の条件］
２ｍ個の方程式
【数４】
2008048451.tif 000136
の少なくともひとつがモジュロｎの整数環におけるｘについて解を持つ。
前記方法は、f個の素因数piを持っている証人と呼ばれているエンティティ、および／または、ベースgiのｍ個の素因数、および／または、前記素因数のチャイニーズ・剰余法のパラメータ、および／または、公開値であるモジュラスn、および／または、ｍ個の秘密値Qi、および／または、前記秘密値Qiと公開の指数値ｖとのf.m個の構成要素Qi,j（Qi,j ( Qi mod pj）を以下のステップによって実現するものである。
・ 前記証人が、モジュロnの整数環において、コミットメントRを計算し、
それぞれのコミットメントは、
【数５】
2008048451.tif 000137
のタイプの演算（ここで、ｒは０＜ｒ＜ｎである乱数値）を実行するか、
あるいは、
【数６】
2008048451.tif 000138
のタイプの演算（ここで、ｒiは０＜ri＜piである素因数piに関連した乱数値、それぞれのriは乱数値の集合｛r1,r2,…rf｝に含まれている）を実行し、さらに、チャイニーズ・剰余法手法を適用するか
のいずれかによって計算されるステップと、
・証人は一つ以上のチャレンジdを受け、それぞれのチャレンジｄはｍ個の整数di（以下「要素チャレンジ」と呼ぶ）からなり、各々のチャレンジdに基づいて、前記証人は
【数７】
2008048451.tif 000139
のタイプの演算を行なうことによって応答Dを計算するか、
【数８】
2008048451.tif 000140
のタイプの演算を行なって、さらに、チャイニーズ・剰余法手法を適用するステップ（前記手法はチャレンジｄ、コミットメントRと同じくらいの数の応答Dがあって、R,ｄ、Dの数の群は｛R、d、D｝で参照される３つの数字の組で表される）。
【請求項２】
コントローラとして知られているエンティティに対して、デモンストレータとして知られているエンティティの真正性を証明するようにできている請求項1に記載の方法であって、デモンストレータは前記証人を含んでいて、
前記デモンストレータエンティティとコントローラエンティティが、以下のステップを実行する方法。
［ステップ1（コミットメントRの行為）］
・ 各々の呼び出しで、証人は請求項1によって指定されるプロセスを適用することによって各々のコミットメントRを計算し、
・ デモンストレータは、各々のコミットメントRのコントローラに全部または一部を送り、
［ステップ2（チャレンジdの行為）］
・ コントローラが、各々のコミットメントRの全部または一部を受けた後に、数がコミットメントRの数と等しいチャレンジdを生成してデモンストレータに送り、
［ステップ3（応答Dの行為）］
・ 前記証人は、請求項1によって指定されるプロセスを適用することによってチャレンジdから応答Dを計算し、
［ステップ4（チェックする行為）］
・ 前記デモンストレータが前記コントローラへ各々の応答Dを送り、
［前記デモンストレータがコミットメントRの一部だけを送信するとき］
前記デモンストレータがコミットメントRの一部だけを送信したなら、ｍ個の公開値G1、G2、...、Gmを有している前記コントローラが、それぞれのチャレンジｄとそれぞれの応答Dから、再構成されたコミットメントR´を計算し、該再構成されたコミットメントR´が
【数９】
2008048451.tif 000141
のタイプか、または
【数１０】
2008048451.tif 000142
のタイプの関係を満たすとともに、
前記コントローラは、それぞれの再構成されたコミットメントR´がコントローラに向けて伝達されたそれぞれのコミットメントRの全てまたは一部を再生成していることを確認し、
［前記デモンストレータがコミットメントRの全部を送信するとき］
前記デモンストレータがコミットメントRの全部を送信したなら、ｍ個の公開値G1、G2、...、Gmを有している前記コントローラは、それぞれのコミットメントRが
【数１１】
2008048451.tif 000143
のタイプか、または
【数１２】
2008048451.tif 000144
のタイプの関係を満たしていることを確認する。
【請求項３】
デモンストレータエンティティと呼ばれるエンティティに関連したメッセージMの完全性について、コントローラエンティティとして知られるエンティティに証明を提供するようにできている請求項１に記載の方法であって、前記デモンストレータエンティティは前記証人を含んでいて、
前記デモンストレータエンティティとコントローラエンティティは以下のステップを実行する方法。
［ステップ1（コミットメントRの行為）］
・ 各々の呼び出しで、証人が請求項1によって指定されるプロセスを適用することによって各々のコミットメントRを計算し、
［ステップ2（チャレンジdの行為）］
-   前記デモンストレータは、メッセージMとそれぞれのコミットメントRの全てまたは一部とを変数とするハッシュ関数ｈを適用し、
-   前記デモンストレータはトークンTを前記コントローラに送り、
-   前記コントローラは、前記トークンTを受け付けると、コミットメントRと同じ数のチャレンジｄを生成して該チャレンジｄを前記デモンストレータに送り、
［ステップ3（応答Dの行為）］
-   前記証人は、請求項1によって指定されるプロセスを適用することによってチャレンジdから応答Dを計算し、
［ステップ4（チェックする行為）］
・ 前記デモンストレータは、前記コントローラへ各々の応答Dを送り、
・前記コントローラはｍ個の公開値G1、G2、...、Gmを有していて、それぞれのチャレンジｄとそれぞれの応答Dから、再構成されたコミットメントR´を計算し、該再構成されたコミットメントR´は
【数１３】
2008048451.tif 000145
のタイプか、または
【数１４】
2008048451.tif 000146
のタイプの関係を満たし、
・ そして前記コントローラは、前記メッセージMとそれぞれの再構成されたコミットメントR´のすべてまたは一部とを変数とするハッシュ関数ｈを適用してトークンT´を再構成し、
・ そして前記コントローラは前記トークンT´が伝達されたトークンTと同一であることを確認する。
【請求項４】
署名エンティティとして知られたエンティティによってメッセージMのディジタル署名を生成するようにするようにされた請求項1に記載の方法であって、当該署名エンティティは前記証人を含んでおり、
［署名動作］
前記署名エンティティは、
・ 前記メッセージM、
・ 前記チャレンジｄおよび／またはコミットメントR、
・ 前記応答D、
を備えた署名されたメッセージを得るために署名動作を行ない、
前記署名エンティティは、次のステップを行なって署名動作を行なう方法。
［ステップ1（コミットメントRの行為）］
・ 各々の呼び出しで、前記証人は請求項1によって指定されるプロセスを適用することによって各々のコミットメントRを計算し、
［ステップ2（チャレンジdの行為）］
・ 前記署名エンティティは、メッセージMとそれぞれのコミットメントRとを変数とするハッシュ関数ｈを適用してバイナリトレインを得て、
・ 該バイナリトレインから前記署名エンティティは、コミットメントRと同じ数のチャレンジｄを引き出し、
［ステップ3（応答Dの行為）］
・前記証人は、請求項1によって指定されるプロセスを適用することによってチャレンジdから応答Dを計算する。
【請求項５】
署名されたメッセージを、コントローラと呼ばれているエンティティによってチェックすることによってメッセージMの真正性を証明するようにされている請求項４に記載の方法であって、
［チェック動作］
前記署名されたメッセージを有している前記コントローラエンティティが以下のように進行するチェック動作を行なう方法。
［前記コントローラがコミットメントR、チャレンジd、応答Dを持つケース］
コントローラがコミットメントR、チャレンジd、応答Dを持つ場合、
前記コントローラは、前記コミットメントR、前記チャレンジｄ、前記応答Dが、
【数１５】
2008048451.tif 000147
のタイプの関係を満たすことを確認するか、
【数１６】
2008048451.tif 000148
のタイプの関係を満たすことを確認し、
前記コントローラは前記メッセージM、前記チャレンジｄ、前記コミットメントRが前記ハッシュ関数
【数１７】
2008048451.tif 000149
を満たすことを確認し、
［前記コントローラはチャレンジｄと応答Dを有する場合］
前記コントローラはチャレンジｄと応答Dを有する場合、
前記コントローラは、それぞれのチャレンジｄと応答Dに基づいて、
【数１８】
2008048451.tif 000150
のタイプの関係か、または、
【数１９】
2008048451.tif 000151
のタイプの関係を満たすコミットメントR´を再構成し、
前記コントローラは前記メッセージMと前記チャレンジｄが前記ハッシュ関数
【数２０】
2008048451.tif 000152
を満たすことを確認し、
［前記コントローラはコミットメントRと応答Dを有する場合］
前記コントローラはコミットメントRと応答Dを有する場合、
前記コントローラは前記ハッシュ関数を適用してｄ´を再構成し、
【数２１】
2008048451.tif 000153
前記コンとローラは、前記コミットメントR、前記チャレンジｄ´、前記応答Dが
【数２２】
2008048451.tif 000154
のタイプの関係か、または、
【数２３】
2008048451.tif 000155
のタイプの関係を満たすことを確認する。
【請求項６】
コントローラ・サーバーに対して、
・ エンティティの真正性、および／または
・ 該エンティティと関連するメッセージMの完全性、
を証明するようにされたシステムであって、
・ 秘密の値Q1、Q2、... 、Qmと公開値G1、G2、...、Gm（ｍは1以上）のm個の組、
・ f個の素因数p1、p2、... pfの積で構成される公開値であるモジュラスn（ｆは2以上）、
の全てあるいは部分以下のパラメータやそれらパラメータからの算出値を用いており、
前記モジュラスと前記秘密値と公開値は以下のタイプの関係があり、
【数２４】
2008048451.tif 000156
ここで、ｖは
【数２５】
2008048451.tif 000157
の形式の公開の指数値 ｃを表し、ｋは１より大きいセキュリティパラメータであり、
前記ｍ個の公開の値Giは、ｆ個の素因数p1, p2,…, pfより小さいｍ個の区別できるベース数g1,g2,…,gmによるgi2となる２乗値であり、
前記素因数p1, p2,…,pfおよび／または前記ｍ個のベース数g1,g2,…,gmは、以下の条件が満たされるように生成されているシステム。
［第１の条件］
方程式
【数２６】
2008048451.tif 000158
がｘについてモジュロｎの整数環において解をもつこと。
［第２の条件］
Gi(Qiv mod nである場合、Qiを二乗してモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）、
Gi.Qiv (１mod nである場合、Qiのモジュロｎを二乗したもののインバースのモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）。
［第３の条件］
少なくとも２ｍ個の方程式
【数２７】
2008048451.tif 000159
がモジュロｎの整数環におけるｘについて解を持つ。
前記システムは、例えばマイクロプロセッサベースの銀行カードの形態をとるようなノマドオブジェクトを特に含まれる証人装置を含み、
その証人装置は、
・ 前記ｆ個の素数pi、および／または、前記ｍ個のベースgi、および／または、前記素因数のチャイニーズ剰余のパラメータ、および／または、公開値であるモジュラスｎ、および／または、m個の秘密の値Qi 、および／または、公開の指数値ｖと秘密の値Qiとによるf.m個の成分Qi,j（Qi,j ( Qi mod pj）を含むメモリゾーンを含み、
前記証人装置は、また、
・ 前記証人装置の乱数値生成手段とここで呼ぶ乱数値生成手段と、
・前記証人装置のコミットメントRの計算手段と呼ぶ計算手段であって、モジュロｎの整数環においてコミットメントRの計算を行い、各コミットメントRは、
・ｒを０＜ｒ＜ｎである前記乱数値生成手段による乱数値として、
【数２８】
2008048451.tif 000160
のタイプの演算を行なうか、
・ｒiが、０＜ｒi＜ｐiで、それぞれ、前記乱数生成手段によって生成され、各ｒIはチャイニーズ剰余法を適用することによって得られるランダム値の集合[r1,r2,…,rf]に属する、素因数piに関連した乱数値であるとして、
【数２９】
2008048451.tif 000161
のタイプの演算を行なうか、
によって計算されるものである計算手段と
を含み、
前記証人装置は、また、
・ 前記証人で装置のチャレンジｄを受け付け、それぞれのチャレンジｄがｍ個の整数di（以下、要素チャレンジとよぶ）からなる1以上のチャレンジｄを受け付け、前記証人デバイスのチャレンジｄ受け付け手段と呼ばれる受け付け手段と、
・ それぞれのチャレンジｄに基づいて、前記証人装置の応答Dを計算し、
・方程式
【数３０】
2008048451.tif 000162
のタイプの演算を行なうこと、あるいは、
・方程式
【数３１】
2008048451.tif 000163
のタイプの演算をおこなって、そして、チャイニーズ剰余法を適用すること、
のいずれかにより応答Dを計算する計算手段と、
・ １以上のコミットメントRと１以上の応答Dを伝送する伝送手段と
を備えている（前記手法はチャレンジｄ、コミットメントRと同じくらいの数の応答Dがあって、R,ｄ、Dの数の群は｛R、d、D｝で参照される３つの数字の組で表される）。
【請求項７】
請求項６に記載のシステムであって、デモンストレータと呼ばれているエンティティとコントローラと呼ばれているエンティティの真正性を証明するようにできていて、前記システムは、
・ 前記デモンストレータエンティテイに関連し、相互接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースの銀行カード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができるデモンストレータ装置と
・ 前記コントローラエンティティと関連するコントローラ装置であって、前記コントローラ装置は特に端末であるか遠隔サーバーの形になっていて、特にデータ処理通信ネットワークを通って、それ自身の電気的、電磁気的、光学的、あるいは音響によるデモンストレータ装置への接続のために、接続手段を含んでいる前記コントローラ装置と、
を備えており、以下のステップの実行を可能にしている前記システム。
［ステップ1（コミットメントRの行為）］
各々の呼び出しで、請求項1によって指定されるプロセスを適用することによって証人装置のコミットメントRの計算手段が各コミットメントRを計算するステップであって、
該証人手段は、コミットメントRの全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
前記デモンストレータ装置は、また、コミットメントRの全てはまた一部を前記コントローラ装置に前記相互接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有する、ステップ。
［ステップ２（チャレンジｄの行為）］
前記コントローラ装置は、前記コミットメントRの全部または一部を受け取った後に、数がコミットメントRと同じチャレンジdを生成する、チャレンジ生成手段を含み、
前記コントローラ装置は、また、接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を含み、
［ステップ３（応答Dの行為）］。
前記証人装置の前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれぞれのチャレンジｄを受け取り、
前記証人装置の前記応答Dの前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答Dを計算し、
［ステップ４（チェックの行為）］
前記デモンストレータの前記伝送手段はそれぞれの応答Dを前記コントローラへ伝送し、前記コントローラは、また、
・ 前記コントローラ装置の計算手段と呼ばれる計算手段、
・ 前記コントローラ装置の比較手段とよばれる比較手段、
を備えており、
［前記デモンストレータが各コミットメントRの一部を伝送した場合］
前記デモンストレータが各コミットメントRの一部を伝送した場合には、
ｍ個の公開値G1、G2、...、Gmを有する前記コントローラ装置の前記計算手段は、各チャレンジRと各応答Dから再構成されたコミットメントR´を計算し、その再構成されたコミットメントR´は
【数３２】
2008048451.tif 000164
のタイプの関係か、
【数３３】
2008048451.tif 000165
のタイプの関係を満たし、
［前記デモンストレータが各コミットメントRの全部を伝送した場合］
前記デモンストレータが各コミットメントRの全部を伝送した場合には、ｍ個の公開値G1、G2、...、Gmを有する前記コントローラ装置の前記計算手段と前記比較手段は、各チャレンジRが
【数３４】
2008048451.tif 000166
のタイプの関係か、
【数３５】
2008048451.tif 000167
のタイプの関係を満たすことを確認する。
【請求項８】
コントローラとして知られたあるエンティティに、デモンストレータとして知られたエンティティに関連したメッセージMについての完全性の証明を与えるようになっている請求項６に記載のシステムであって、
・ 前記デモンストレータエンティテイに関連し、前記相互接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースの銀行カード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができるデモンストレータ装置と、
・前記コントローラエンティティと関連するコントローラ装置であって、前記コントローラ装置は、特に端末であるか遠隔サーバーの形になっていて、前記コントローラ装置が、特にデータ処理通信ネットワークを通って、それ自身の電気的、電磁気的、光学的、あるいは音響によるデモンストレータ装置への接続のために、接続手段とを含んでいるコントローラ装置と
を備えており、以下のステップの実行を可能にしている前記システム
［ステップ1（コミットメントRの行為）］
各々の呼び出しで、請求項1によって指定されるプロセスを適用することによって証人装置のコミットメントRの計算手段が各コミットメントRを計算し、
該証人手段は、コミットメントRの全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
［ステップ２（チャレンジｄの行為）］
前記デモンストレータ装置は、少なくともあるトークンTの計算に、前記メッセージと各コミットメントRの全部または一部とを変数とするハッシュ関数ｈを適用する、前記デモンストレータの計算手段と呼ばれる計算手段からなり、
前記デモンストレータ装置は、また、各トークンTを前記コントローラ装置に前記接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有し、
前記コントローラ装置は、前記トークンTを受け取った後に、コミットメントRの数と同じ数の前記チャレンジｄを生成するチャレンジ生成手段を有し、
前記コントローラ装置は、また、前記接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を有し、
［ステップ３（応答Dの行為）］
前記証人装置の前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれぞれのチャレンジｄを受け取り、
前記証人装置の前記応答Dの前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答Dを計算し、
［ステップ４（チェックの行為）］
前記デモンストレータの前記伝送手段はそれぞれの応答Dを前記コントローラへ伝送し、
前記コントローラは、また、前記コントローラ装置の計算手段と呼ばれる計算計算手段を有し、この計算手段は、ｍ個の公開値G1、G2、...、Gmを有するとともに、第１に、各チャレンジｄと各応答Dから再構成されたコミットメントR´を計算し、この再構成されたコミットメントR´は
【数３６】
2008048451.tif 000168
のタイプの関係か、
【数３７】
2008048451.tif 000169
のタイプの関係を満たし、
第２に、前記メッセージMおよび各再構成されたコミットメントR´の全てまたは一部を変数として有する前記ハッシュ関数ｈを適用することによりトークンT´を計算し、
前記コントローラ装置は、また、受け付けられたトークンTについて前記トークンT´を計算する、前記コントローラ装置の比較手段として知られている比較手段を有する。
【請求項９】
署名エンティティと呼ばれるエンティティによって、署名されたメッセージとして知られているメッセージMのディジタル署名を生成するようにするようにされた請求項６に記載のシステムであって、前記署名されたメッセージは、
・ 前記メッセージM、
・ 前記チャレンジd、および／または、前記コミットメントR、
・ 前記応答D;
を含んでいて、
［署名動作］
前記システムは、前記署名エンティティに関連している署名装置からなるようなものであり、前記署名装置は、前記証人装置に、相互接続手段で相互接続されていて、例えばマイクロプロセッサベースの銀行カード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができ、
以下のステップの実行を可能にする前記システム。
［ステップ1（コミットメントRの行為）］
各々の呼び出しで、請求項1によって指定されるプロセスを適用することによって証人装置のコミットメントRの計算手段が各コミットメントRを計算し、
該証人手段は、コミットメントRの全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
［ステップ２（チャレンジｄの行為）］
前記署名装置は、前記メッセージと各コミットメントRの全部または一部とを変数とするハッシュ関数ｈを適用し、あるバイナリトレインを計算し、このバイナリトレインからコミットメントRと同じ数のチャレンジｄを導出する前記署名装置の計算手段と呼ばれる該計算手段を有し、
［ステップ３（応答Dの行為）］
前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記署名装置から来るそれぞれのチャレンジｄを受け取り、
前記証人装置の前記応答Dの前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答Dを計算し、
前記証人装置が、前記証人装置の伝達装置と呼ばれ、前記相互接続手段を通して前記署名装置へと前記応答Dを伝達させる、伝達装置を含むものである。
【請求項１０】
コントローラと呼ばれているエンティティによって、署名されたメッセージをチェックすることによってメッセージMの真正性を証明するようにできている、請求項9に記載のシステムであって、
［チェック動作］
前記システムは、コントローラエンティティに関連したコントローラ装置を有するようになっていて、前記コントローラ装置は、特に端末であるか遠隔サーバーの形になっていて、特にデータ処理通信ネットワークを通って、それ自身の電気的、電磁気的、光学的、あるいは音響による前記署名装置への接続のための接続手段を含んでいて、
前記署名装置は、前記署名エンティティに関連していて、前記接続装置を通じて、前記署名されたメッセージの前記コントローラ装置への伝送手段であって署名装置の伝送手段として知られてるものを含み、前記コントローラ装置が、
・ 前記メッセージM、
・ 前記チャレンジｄ、および／または、前記コミットメントR、
・ 前記応答D、
を含む署名されたメッセージを含むようになっていて、
前記コントローラ装置は、
・ 前記コントローラ装置の計算手段と呼ばれる計算手段、
・ 前記コントローラ装置の比較手段と呼ばれる比較手段、
を含んでおり、
［前記コントローラ装置がコミットメントR、チャレンジｄ、応答Dを有する場合］
前記コントローラ装置がコミットメントR,チャレンジｄ、応答Dを有する場合
．．前記コントローラ装置の前記計算手段および前記比較手段は、
前記コミットメントR、前記チャレンジｄ、前記応答Dが
【数３８】
2008048451.tif 000170
のタイプか、
【数３９】
2008048451.tif 000171
のタイプの関係を満たすことを確認し、
．．前記コントローラ装置の前記計算手段と前記比較手段は、前記メッセージM,前記チャレンジｄ、前記コミットメントRが前記ハッシュ関数
【数４０】
2008048451.tif 000172
を満たすことを確認し、
［前記コントローラ装置がチャレンジｄ、応答Dを有する場合］
前記コントローラ装置がチャレンジｄ、応答Dを有する場合、
．．前記コントローラ装置の前記計算手段は、各チャレンジｄと各レスポンスDに基づいて、
【数４１】
2008048451.tif 000173
のタイプか、
【数４２】
2008048451.tif 000174
のタイプの関係を満たすコミットメントR´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージMと前記チャレンジｄがハッシュ関数
【数４３】
2008048451.tif 000175
を満たすことを確認する。
［前記コントローラ装置がコミットメントR、応答Dを有する場合］
前記コントローラ装置がコミットメントR、応答Dを有する場合、
．．前記コントローラ装置の前記計算手段は、前記ハッシュ関数を適用して、
【数４４】
2008048451.tif 000176
のようなｄ´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記コミットメントR、前記チャレンジｄ´、前記応答Dが
【数４５】
2008048451.tif 000177
のタイプの関係を満たすか、
【数４６】
2008048451.tif 000178
のタイプの関係を満たすことを確認する。
【請求項１１】
あるエンティティに関連した端末装置であって、例えばマイクロプロセッサベースの銀行カード中のマイクロプロセッサの形態のようなノマドオブジェクトにおける微小論理回路の形態を特にとることができ、コントローラ装置に対して
・ あるエンティティの前記真正性、および／または、
・ 該エンティティに関連したあるメッセージMの完全性、
を、以下のパラメータ、
秘密の値Q1、Q2、... 、Qmと公開値G1、G2、...、Gm（ｍは1以上）のm個の組と、
f個の素因数p1、p2、... pfの積で構成される公開のモジュラスn（fは2以上）、
や、これらのパラメータからの算出値の全部または一部を用いて証明するようにされていて、前記モジュラスと前記秘密値と公開値は
【数４７】
2008048451.tif 000179
のタイプの関係があり、ここで、ｖは
【数４８】
2008048451.tif 000180
の形態の公開値である指数値を表し（ｋは１より大きいセキュリティパラメータ）；
前記ｍ個の公開値Giは、ｍ個の異なったベース数g1、g2、…gmの、f個の素因数p1、p2、…pfより小さい二乗値ｇi2であり；
前記p1、p2、…pfの素因数、および／または、ｍ個のベース数g1、g2、…gmは以下の条件が満たされるように生成される端末装置。
［第１の条件］
各方程式
【数４９】
2008048451.tif 000181
がモジュロｎの整数環におけるｘについて解を持つこと；
［第２の条件］
Gi(Qiv mod nである場合、Qiを二乗してモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）、
Gi.Qiv (１mod nである場合、Qiのモジュロｎを二乗したもののインバースのモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）；
［第３の条件］
２ｍ個の方程式
【数５０】
2008048451.tif 000182
がモジュロｎの整数環におけるｘについて解をもち、
前記端末装置は、以下を備える証人装置を備え、
・ 前記ｆ個の素因数pi、および／または、ベースgiのｍ個の素因数、および／または、前記素因数のチャイニーズ・剰余法のパラメータ、および／または、公開モジュラスn、および／または、ｍ個の秘密値Qi、および／または、前記秘密値Qiと公開の指数値ｖとのf.m個の構成要素Qi,j（Qi,j ( Qi mod pj）を含むメモリゾーン；
・ 前記証人装置の乱数値生成手段と呼ぶ乱数値生成手段；
・ 前記証人装置のコミットメントRの計算手段と呼ぶ計算手段であって、モジュロｎの整数環においてコミットメントRの計算を行い、各コミットメントRは、
・ｒがｒが０＜ｒ＜ｎである前記乱数値生成手段による乱数値としたとき、
【数５１】
2008048451.tif 000183
のタイプの演算を行なうか、
・ｒiが、０＜ｒi＜ｐiで、それぞれ、前記乱数生成手段によって生成されて、チャイニーズ剰余法を適用することによって得られるランダム値の集合[r1,r2,…,rf]に属する、素因数piに関連した乱数値であるとしたとき、
【数５２】
2008048451.tif 000184
のタイプの演算を行なうか、
によって計算され、
前記証人装置は、また、
・ 前記証人で装置のチャレンジｄを受け付け、それぞれのチャレンジｄがｍ個の整数di（以下、要素チャレンジとよぶ）からなる1以上のチャレンジｄを受け付ける受け付け手段、
・ それぞれのチャレンジｄに基づいて、前記証人装置の応答Dを計算し、
・方程式
【数５３】
2008048451.tif 000185
のタイプの演算を行なうこと、あるいは、
・方程式
【数５４】
2008048451.tif 000186
のタイプの演算をおこなって、そして、チャイニーズ剰余法を適用すること、
のいずれかにより応答Dを計算する計算手段、
・ １以上のコミットメントRと１以上の応答Dを伝送する伝送手段、
を備えている（前記手法はチャレンジｄ、コミットメントRと同じくらいの数の応答Dがあって、R,ｄ、Dの数の群は｛R、d、D｝で参照される３つの数字の組で表される）。
【請求項１２】
請求項１１に記載の端末装置であって、デモンストレータと呼ばれているエンティティとコントローラと呼ばれているエンティティの真正性を証明するようにされていて、
前記デモンストレータエンティテイに関連し、前記接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースの銀行カード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができるデモンストレータ装置
を含み、前記デモンストレータ装置が、
前記コントローラエンティティと関連していて、特に端末であるか遠隔サーバーの形になっている前記コントローラ装置へと、特にデータ処理通信ネットワークを通じて、それ自身の電気的、電磁気的、光学的、あるいは音響によるデモンストレータ装置への接続のために接続手段をまた含んでいるような、以下のステップの実行を可能にしている前記端末装置。
［ステップ1（コミットメントRの行為）］
各々の呼び出しで、請求項1によって指定されるプロセスを適用することによって証人装置のコミットメントRの計算手段が各コミットメントRを計算し、
・ 該証人手段は、コミットメントRの全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
・ 前記デモンストレータ装置は、また、コミットメントRの全てはまた一部を前記コントローラ装置に前記接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有する、
［ステップ２および３（チャレンジｄの行為、応答Dの行為）］
前記証人装置の前記チャレンジｄの受け取り手段は、前記コントローラ装置と前記デモンストレータ装置の間の前記接続装置を通して、また、前記デモンストレータ装置と前記証人装置の間の前記相互接続装置を通して、前記コントローラ装置から来るそれぞれのチャレンジｄを受け取り、
前記証人装置の前記応答Dの前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答Dを計算する、
［ステップ４（チェックの行為）］
前記デモンストレータの前記伝送手段はそれぞれの応答Dをチェックを行なう前記コントローラへ伝送する。
【請求項１３】
コントローラとして知られたあるエンティティに、デモンストレータとして知られたエンティティに関連したメッセージMについての完全性の証明を与えるようにされた請求項１１に記載の端末装置であって、
前記デモンストレータエンティテイに関連し、前記相互接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースの銀行カード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができるデモンストレータ装置を備え、前記デモンストレータ装置が
前記コントローラエンティティと関連していて、特に端末であるか遠隔サーバーの形になっている前記コントローラ装置へと、特にデータ処理通信ネットワークを通じて、それ自身の電気的、電磁気的、光学的、あるいは音響によるデモンストレータ装置への接続のための接続手段
をまた含んでいるような、以下のステップの実行をする前記端末装置。
［ステップ1（コミットメントRの行為）］
各々の呼び出しで、請求項1によって指定されるプロセスを適用することによって証人装置のコミットメントRの計算手段が各コミットメントRを計算し、
該証人手段は、コミットメントRの全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
［ステップ２および３（チャレンジｄの行為、応答Dの行為）］
前記デモンストレータ装置は、少なくともあるトークンTの計算に、変数を前記メッセージおよび各コミットメントRの全部または一部とするハッシュ関数ｈを適用する、前記デモンストレータの計算手段と呼ばれる計算手段からなり、
前記デモンストレータ装置は、また、各トークンTを前記コントローラ装置に前記接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有し、
（前記コントローラ装置は、前記トークンTを受け取った後、コミットメントRの数と同じ数のチャレンジｄを生成し、）
前記証人装置の前記チャレンジｄの受け取り手段は、前記コントローラ装置と前記デモンストレータ装置の間の前記相互接続装置を通して、また、前記デモンストレータ装置と前記証人装置の間の前記相互接続装置を通して、前記コントローラ装置から来るそれぞれのチャレンジｄを受け取り、
前記証人装置の前記応答Dの前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答Dを計算する、
［ステップ４（チェックの行為）］
前記デモンストレータの前記伝送手段は、それぞれの応答Dをチェックを行なう前記コントローラへ伝送する。
【請求項１４】
署名エンティティと呼ばれるエンティティによって、署名されたメッセージとして知られているメッセージMのディジタル署名を生成するようにするようにされた請求項１１に記載の端末装置であって、
前記署名されたメッセージは、
・ 前記メッセージM、
・ 前記チャレンジd、および／または、前記コミットメントR、
・ 前記応答D;
を含んでいて、
前記端末装置は、前記署名エンティティに関連している署名装置からなるようなものであり、前記署名装置は、前記証人装置に、相互接続手段で相互接続されていて、例えばマイクロプロセッサベースの銀行カード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができ、
前記署名装置は、また、前記コントローラエンティティと関連していて、特に端末であるか遠隔サーバーの形になっている前記コントローラ装置へと、特にデータ処理通信ネットワークを通じて、それ自身の電気的、電磁気的、光学的、あるいは音響によるデモンストレータ装置への接続のための接続手段を含んでいて、
［署名動作］
以下のステップの実行をする前記端末装置。
［ステップ1（コミットメントRの行為）］
各々の呼び出しで、請求項1によって指定されるプロセスを適用することによって証人装置のコミットメントRの計算手段が各コミットメントRを計算し、
該証人手段は、コミットメントRの全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
［ステップ２（チャレンジｄの行為）］
前記署名装置は、前記署名装置の計算手段と呼ばれる該計算手段を含み、変数を前記メッセージおよび各コミットメントRの全部または一部とするハッシュ関数ｈを適用して、あるバイナリトレインを計算し、このバイナリトレインからコミットメントRと同じ数のチャレンジｄを導出し、
［ステップ３（応答Dの行為）］
前記証人装置の前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれぞれのチャレンジｄを受け取り、前記証人装置の前記応答Dの前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答Dを計算し、
前記証人装置は、前記証人装置の伝達装置と呼ばれ、前記相互接続手段を通して前記署名装置へと前記応答Dを伝達させる、伝達装置からなる。
【請求項１５】
あるコントローラエンティティに関連した端末か遠隔サーバ形態を特にとるコントローラ装置であって、
・ あるエンティティの真正性、および／または、
・ 該エンティティと関連するメッセージMの完全性
を証明するようにされている装置であって、以下のパラメータ、
・ 秘密の値Q1、Q2、... 、Qmと公開値G1、G2、...、Gm（ｍは1以上）のm個の組
・ f個の素因数p1、p2、... pfの積で構成される公開のモジュラスn（fは2以上）で、前記コントローラ装置と関連しているコントローラエンティティには知られていないもの、
の全部若しくは一部またはこれらのパラメータからの算出値を用い、
前記モジュラスと前記秘密値と公開値は、
【数５５】
2008048451.tif 000187
のタイプの関係があり、ここで、ｖは
【数５６】
2008048451.tif 000188
のタイプの公開値である指数値を表し（ｋは１より大きいセキュリティパラメータ、Qiは、前記コントローラ装置には知られていない、前記公開値Giに関連している秘密値）；
前記ｍ個の公開値Giは、ｍ個の区別できるベース数g1、g2、…gmの、f個の素因数p1、p2、…pfより小さい二乗値ｇi2であり；
前記p1、p2、…pfの素因数、および／または、ｍ個のベース数g1、g2、…gmは以下の条件が満たされるように生成される、
コントローラ装置。
［第１の条件］
各方程式
【数５７】
2008048451.tif 000189
がモジュロｎの整数環におけるｘについて解を持つこと；
［第２の条件］
Gi(Qiv mod nである場合、Qiを二乗してモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）、
Gi.Qiv (１mod nである場合、Qiのモジュロｎを二乗したもののインバースのモジュロnをk-1回とって得られるｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）；、
［第３の条件］
２ｍ個の方程式
【数５８】
2008048451.tif 000190
がモジュロｎの整数環におけるｘについて解を持つこと。
【請求項１６】
コントローラと呼ばれるあるエンティティに対して、デモンストレータと呼ばれるあるエンティティの真正性を証明するようにされている請求項１５に記載のコントローラ装置であって、
前記コントローラ装置は、特にデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響によって接続する、デモンストレータエンティティに関連したデモンストレータ装置への接続のための接続手段を含んでいて、
以下のステップを実行するのに用いられる前記コントローラ装置。
［ステップ１および２（コミットメントＲの行為、チャレンジｄの行為）］
前記コントローラ装置は、また、前記接続装置を通して前記デモンストレータ装置から来るコミットメントRの全部または一部を受け付ける手段を有し、
前記コントローラ装置は、前記コミットメントRの全部または一部を受け取った後に、それぞれの数がコミットメントRと同じであるチャレンジd（各チャレンジｄはｍ個の整数di（以下「要素チャレンジ」と呼ぶ）からなる）を生成する、チャレンジ生成手段を含み、
前記コントローラ装置は、また、前記接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を含み、
［ステップ３および４（応答Dの行為、チェックの行為）］
前記コントローラ装置は、また、
・ 前記接続手段を通じて前記デモンストレータ装置から来る前記応答Dを受け付ける手段
・ 前記コントローラ装置の計算手段と呼ばれる計算手段
・ 前記コントローラ装置の比較手段と呼ばれる比較手段
を備え、
［前記デモンストレータが各コミットメントRの一部を伝送した場合］
前記デモンストレータが各コミットメントRの一部を伝送した場合には、
ｍ個の公開値G1、G2、...、Gmを有する前記コントローラ装置の前記計算手段は、各チャレンジRと各応答Dから再構成されたコミットメントR´を計算し、その再構成されたコミットメントR´は
【数５９】
2008048451.tif 000191
のタイプの関係か、
【数６０】
2008048451.tif 000192
のタイプの関係を満たし、
前記コントローラ装置の前記比較手段は、各再構成されたコミットメントR´を受け付けられた各コミットメントRの全部または一部と比較する。
［前記デモンストレータが各コミットメントRの全部を伝送した場合］
前記デモンストレータが各コミットメントRの全部を伝送した場合には、
ｍ個の公開値G1、G2、...、Gmを有する前記コントローラ装置の前記計算手段と前記比較手段は、各チャレンジRが
【数６１】
2008048451.tif 000193
のタイプの関係か、
【数６２】
2008048451.tif 000194
のタイプの関係を満たすことを確認する。
【請求項１７】
デモンストレータと呼ばれるあるエンティティの完全性を証明するようにされている請求項１５に記載のコントローラ装置であって、
前記コントローラ装置は、特にデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響によって、デモンストレータエンティティに関連したデモンストレータ装置への接続のために、接続手段を含んでいて、
以下のステップを実行するのに用いられる前記コントローラ装置。
［ステップ１および２（コミットメントＲの行為、チャレンジｄの行為）］
前記コントローラ装置は、前記接続装置を通して前記デモンストレータ装置から来るトークンTを受け付ける手段を、また有し、
前記コントローラ装置は、前記トークンTを受け取った後に、それぞれの数がコミットメントRと同じであるチャレンジd（各チャレンジｄはｍ個の整数di（以下「要素チャレンジ」と呼ぶ）からなる）を生成する、チャレンジ生成手段を含み、
前記コントローラ装置は、また、前記接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を含み、
［ステップ３および４（応答Dの行為、チェックの行為）］
前記コントローラ装置は、また、
・ 前記接続手段を通じて前記デモンストレータ装置から来る前記応答Dを受け付ける手段
・ 前記コントローラ装置の計算手段と呼ばれる計算手段であって、この計算手段は、第１に、ｍ個の公開値G1、G2、...、Gmを有するとともに、各チャレンジｄと各応答Dから再構成されたコミットメントR´を計算し、そのコミットメントRは
【数６３】
2008048451.tif 000195
のタイプの関係か、
【数６４】
2008048451.tif 000196
のタイプの関係を満たし、
第２に、前記メッセージMおよび各再構成されたコミットメントR´の全てまたは一部を変数として有する前記ハッシュ関数ｈを適用することによりトークンT´を計算し、
・ トークンT´を受け付けられたトークンTと比較する前記コントローラ装置の比較手段と呼ばれる比較手段
を備える。
【請求項１８】
署名されたメッセージと呼ばれているエンティティによって署名されたメッセージをチェックすることによってメッセージMの真正性を証明するようにされている請求項１５に記載のコントローラ装置であって、
前記署名メッセージは、ハッシュ関数ｈ（message,R）を有するある署名エンティティに関連した署名装置によって送られるとともに、
・ 前記メッセージM、
・ 前記チャレンジｄおよび／またはコミットメントR、
・ 前記応答D、
からなり、
［チェック動作］
前記コントローラ装置は、前記署名エンティティに関連した前記署名装置への、特にデータ処理通信ネットワークを通る電気的、電磁気的、光学的、あるいは音響による接続のための接続手段を含んでいて、該コントローラ装置が、前記署名装置から前記接続を通じて前記署名メッセージを受け取り、
前記コントローラ装置は、
・ 前記コントローラ装置の計算手段と呼ばれる計算手段、
・ 前記コントローラ装置の比較手段と呼ばれる比較手段、
を備え、
［場合前記コントローラ装置がコミットメントR、チャレンジｄ、応答Dを有する場合］
場合前記コントローラ装置がコミットメントR,チャレンジｄ、応答Dを有する場合
．．前記コントローラ装置の前記計算手段および前記比較手段は、
前記コミットメントR、前記チャレンジｄ、前記応答Dが
【数６５】
2008048451.tif 000197
のタイプか、
【数６６】
2008048451.tif 000198
のタイプの関係を満たすことを確認し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージM,前記チャレンジｄ、前記コミットメントRが前記ハッシュ関数
【数６７】
2008048451.tif 000199
を満たすことを確認する。
［前記コントローラ装置がチャレンジｄ、応答Dを有する場合］
前記コントローラ装置がチャレンジｄ、応答Dを有する場合、
．．前記コントローラ装置の前記計算手段は、各チャレンジｄと各レスポンスDに基づいて、
【数６８】
2008048451.tif 000200
のタイプか、
【数６９】
2008048451.tif 000201
のタイプの関係を満たすコミットメントR´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージMと前記チャレンジｄがハッシュ関数
【数７０】
2008048451.tif 000202
を満たすことを確認する。
［前記コントローラ装置がコミットメントR、応答Dを有する場合］
前記コントローラ装置がコミットメントR、応答Dを有する場合、
．．前記コントローラ装置の前記計算手段は、前記ハッシュ関数を適用して、
【数７１】
2008048451.tif 000203
のようなｄ´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記コミットメントR、前記チャレンジｄ´、前記応答Dが
【数７２】
2008048451.tif 000204
のタイプの関係を満たすか、
【数７３】
2008048451.tif 000205
のタイプの関係を満たすことを確認する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エンティティの真正性、及び／又はメッセージの完全性、及び／又は真正性を証明するように設計された方法、システム及びデバイスに関する。
【背景技術】
【０００２】
Ｌｏｕｉｓ  Ｇｕｉｌｌｏｕ及びＪｅａｎ−Ｊａｃｑｕｅｓ  Ｑｕｉｓｑｕａｔｅｒが発明者である欧州特許第０３１１４７０Ｂ１号は、このような方法を説明している。以後、「ＧＱ特許」又は「ＧＱ方法」との用語によって彼らの研究を参照するものとする。以後、表現「ＧＱ２」又は「ＧＱ２発明」又は「ＧＱ２技術」が本発明を説明するために使用されるものとする。
【０００３】
ＧＱ方法に従って、「信頼できる権威者」（trusted authority）として知られているエンティティが「証人」と呼ばれている各エンティティにアイデンティティを割り当て、それについてのＲＳＡシグナチャを計算する。カスタマイズするプロセスでは、信頼できる権威者は証人にアイデンティティとシグナチャを与える。その後、その証人は「ここにあるのは私のアイデンティティです。私はそのＲＳＡシグナチャを知っています」と宣言する。証人は、自分が自分のアイデンティティの該ＲＳＡシグナチャを知っている旨を、それを明らかにすることなく証明する。該信頼できる権威者により配布されるＲＳＡ公開識別鍵を通して、「コントローラ」として知られているエンティティは、その知識を取得することなく、当該ＲＳＡシグナチャが宣言されたアイデンティティに一致することを確認する。ＧＱ方法を使用するこの機構は「知識の移転なしに」動作する。このＧＱ方法に従って、証人はＲＳＡ秘密鍵を知ることなく、信頼できる権威者がその鍵を用いて多数のアイデンティティに署名する。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
前述のＧＱ技術はＲＳＡ技術を利用する。しかしながら、ＲＳＡ技術が係数ｎの因数分解に強く依存するのに対し、ＲＳＡ技術を実現するデジタルシグナチャの多様な規格と比較して「積攻撃（multiplicative attacks）」と呼ばれているものに見られるように、この依存は等価ではなく、実際にはそれからは程遠い。
【課題を解決するための手段】
【０００５】
ＧＱ２技術の目標は２つの要素からなる。つまり、一方では、ＲＳＡ技術の性能特性を改善することであり、他方ではＲＳＡ技術に固有の問題を回避することである。該ＧＱ２秘密鍵の知識は、該係数ｎの該因数分解の知識と同等である。トリプレットＧＱ２に対する攻撃は該係数ｎの因数分解につながる。この時点では等価なものがある。ＧＱ２技術を用いると、該署名する又は自己認証する（ｓｅｌｆ−ａｕｔｈｅｎｔｉｃａｔｉｎｇ）エンティティと該コントローラエンティティの両方にとって作業負荷が削減される。因数分解するという問題をセキュリティおよび性能の両方に関してさらにうまく使用することにより、ＧＱ２技術はＲＳＡ技術の欠点を回避する。
【０００６】
ＧＱ方法は５１２ビット以上を備える数のモジュロ計算を実現する。これらの計算は、ほぼ２16＋１乗にされた実質的に同じ大きさを有する数に関する。しかし、既存のマイクロエレクトロニクスインフラストラクチャは、特に銀行カードの分野では、演算コプロセッサを持たないモノリシック自己プログラム可能マイクロプロセッサを使用する。ＧＱ方法等の方法に関与する該複数の演算応用例に関する作業負荷によって計算時間が掛かり、そのため、特定のケースで銀行カードを使用する消費者が自分達の買い物を支払うために不利となることがわかっている。ここでは、支払いカードのセキュリティを強化しようとする際に、銀行当局（ｂａｎｋｉｎｇ  ａｕｔｈｏｒｉｔｉｅｓ）はとりわけ解決するのが困難である問題を提起してきたことが思い起こされるかもしれない。事実上、２つの明らかに矛盾する問題、つまり該作業負荷がユーザにとって過剰な計算時間につながらないようにしつつ、その一方で、ますます冗長且つ区別できる鍵を各カードに使用することによってセキュリティを強化することが、研究されなければならない。既存のインフラストラクチャ及び既存のマイクロプロセッサ構成要素を考慮に入れることも必要であるため、この問題は特に深刻になる。
【０００７】
ＧＱ２技術は、依然としてセキュリティを強化しつつ、この問題に解決策を提供することを目的とする。
【０００８】
方法
さらに詳細には、本発明は、コントローラエンティティに対して
−エンティティの真正性、及び／又は
−このエンティティに関連付けられたメッセージＭの完全性
を証明するように設計された方法に関する。
この証明は、以下のパラメータ
−秘密値Ｑ1、Ｑ2、．．．Ｑmと公開値Ｇ1、Ｇ2，．．．Ｇmのｍ個の組（ｍは１以上）
−ｆ個の素因数ｐ1、ｐ2，．．．ｐfの積によって構成される公開係数ｎ（ｆは２以上）
又はこれらのパラメータの算出値のすべて又は一部によって立証される。
【０００９】
前記係数及び前記秘密値と公開値は以下のタイプの関係
【数１】
2008048451.tif 000003
によって関連付けられ、この場合ｖは以下のタイプ
【数２】
2008048451.tif 000004
の公開指数を表し、この場合ｋは１より大きなセキュリティパラメータであり、
前記ｍ個の公開値Ｇiは該ｆ個の素因数ｐ1，ｐ2，．．．ｐfに従うｍ個の区別できるベース数ｇ1ｇ2，．．．ｇmの二乗ｇi2であり、前記ｆ個の素因数ｐ1，ｐ2，．．．ｐf、及び／又は前記ｍ個のベース数ｇ1ｇ2，．．．ｇmは以下の条件が満たされるように生成される。
【００１０】
第１の条件：
第１の条件に従えば、該方程式
【数３】
2008048451.tif 000005
のそれぞれは、ｎを法とした整数の環の中のｘについて解を有する。
【００１１】
第２の条件：
第２の条件に従えば、Ｇi≡Ｑiv mod ｎのケースでは、ｋ−１階数回、Ｑiを二乗すること（mod ｎ）によって得られる該ｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００１２】
第２の条件に従えば、Ｇi，Ｑiv≡１ mod ｎのケースでは、Ｑiの逆数(mod ｎ)をｋ−１階数回二乗する（mod ｎ）ことによって得られるｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００１３】
現在の表記に従えば、±ｇiが数ｇiとｎ−ｇiとを表していることがここで留意されるべきである。
【００１４】
第３の条件：
第３の条件に従えば、以下の２ｍ個の方程式
【数４】
2008048451.tif 000006
の中で、それらの内の少なくとも１つはｎを法として整数の環の中のｘについて解を有する。
【００１５】
該方法はここに後述されるステップの中で証人と呼ばれているエンティティを実現する。前記証人エンティティは、ｆ個の素因数ｐi、及び／又はｍ個のベース数ｇi、及び／又は該素因数のチャイニーズ剰余のパラメータ、及び／又は該公開係数ｎ、及び／又は該ｍ個の秘密値Ｑi、及び／又は該秘密値Ｑiと該公開指数ｖの該ｆ．ｍ個の成分Ｑi,j（Ｑi,j≡Ｑi、mod ｐj）を有する。
【００１６】
該証人はｎを法として整数の該環の中のコミットメントＲを計算する。各コミットメントは、
−以下のタイプ
【数５】
2008048451.tif 000007
の演算を実行し、この場合ｒが０＜ｒ＜ｎとなるように無作為の値となることと、
−又は
＊＊以下のタイプ
【数６】
2008048451.tif 000008
の演算を実行し、この場合ｒiが０＜ｒi＜ｐiとなるように素因数ｐiと関連付けられた無作為な値であり、各ｒiは無作為な値の集合体｛ｒi，ｒ2，．．．ｒf｝に属することと、
のいずれかによって、
＊＊次に、該チャイニーズ剰余方法を適用することによって計算される。
【００１７】
該証人は１つ又は複数のチャレンジｄを受け取る。各チャレンジｄは、以下に基本的なチャレンジと呼ばれるｍ個の整数ｄiを備える。該証人は各チャレンジｄiに基づいて応答Ｄを、
−以下のタイプ
【数７】
2008048451.tif 000009
の演算を実行することによって、
−又は
＊＊以下のタイプ
【数８】
2008048451.tif 000010
の演算を実行することによって、
＊＊次に該チャイニーズ剰余法を適用することによって
のいずれかで計算する。
【００１８】
前記手法はチャレンジｄ、コミットメントRと同じくらいの数の応答Dがある。R,ｄ、Dの数の群は｛R、d、D｝で参照される３つの数字の組で表されるトリプレットを形成する。
【００１９】
エンティティの真正性の証拠のケース
実施形態の第１の変形において、本発明による該方法は、証明者として知られているエンティティの真正性を、該コントローラとして知られているエンティティに対して証明するように設計されている。前記証明者エンティティは該証人を備える。前記証明者エンティティとコントローラエンティティは以下のステップを実行する。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人は前記に指定された該プロセスを適用することにより、各コミットメントＲを計算する。該証明者は該コントローラに各コミットメントＲのすべて又は部分を送信する。
・ステップ２：チャレンジｄの行為
該コントローラは、各コミットメントＲのすべて又は部分を受信した後に、コミットメントＲの数に数が等しいチャレンジｄを生成し、該チャレンジｄを該証明者に送信する。
・ステップ３：応答Ｄの行為
該証人は該チャレンジｄからの該応答Ｄを、前記に指定された該プロセスを適用することにより計算する。
・ステップ４：チェックの行為
該証明者は各応答Ｄを該コントローラに送信する。
【００２０】
第１のケース：該証明者が各コミットメントＲの一部を送信した。
該証明者が各コミットメントＲの一部を送信した場合、該ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラは、各チャレンジｄ及び各応答Ｄから再構築されたコミットメントＲ’を計算し、この再構築されたコミットメントＲ’は以下のタイプ
【数９】
2008048451.tif 000011
の関係又は以下のタイプ
【数１０】
2008048451.tif 000012
の関係を満たす。
【００２１】
該コントローラは、各再構築されたコミットメントＲ’が、それに送信された各コミットメントＲのすべて又は部分を再現することを確認する。
【００２２】
第２のケース：該証明者は各コミットメントＲの全体性を送信した。
該証明者が各コミットメントＲの全体性を送信した場合、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラは、各コミットメントＲが以下のタイプ
【数１１】
2008048451.tif 000013
の関係又は以下のタイプ
【数１２】
2008048451.tif 000014
の関係を満たすことを確認する。
【００２３】
メッセージの完全性の証明のケース
第１の変形と結合できる実施形態の第２の変形では、本発明による該方法は該コントローラエンティティとして知られているエンティティに対して、証明者エンティティと呼ばれているエンティティと関連付けられたメッセージＭの完全性の証拠を提供するように設計されている。前記証明者エンティティは該証人を備える。
【００２４】
前記証明者エンティティとコントローラエンティティは以下のステップを実行する。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人は前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。
・ステップ２：チャレンジｄの行為
該証明者は、少なくとも１つのトークンＴを計算するために、その引数が該メッセージＭ及び各コミットメントＲのすべて又は部分であるハッシュ関数ｈを適用する。該証明者は、該トークンＴを該コントローラに送信する。該コントローラは、トークンＴを受信後、コミットメントＲの数に数が等しいチャレンジｄを生成し、該チャレンジｄを該証明者に送信する。
・ステップ３：応答Ｄの行為
該証人は、前記に指定された該プロセスを適用することによって、該チャレンジｄから該応答Ｄを計算する。
・ステップ４：チェックの行為
該証人は該コントローラに各応答Ｄを送信する。該ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラは、各チャレンジｄ及び各応答Ｄから再構築されたコミットメントＲ’を計算し、この再構築されたコミットメントＲ’は以下のタイプ
【数１３】
2008048451.tif 000015
の関係又は以下のタイプ
【数１４】
2008048451.tif 000016
の関係を満たす。
【００２５】
次に、該コントローラは、該トークンＴ’を再構築するために、その引数が該メッセージＭ及び各再構築されたコミットメントＲ’のすべて又は部分である、該ハッシュ関数ｈを適用する。それから、該コントローラは、該トークンＴ’が送信された該トークンＴと同一であることを確認する。
【００２６】
メッセージのデジタルシグナチャ及びその真正性の証拠
該２つの前記実施形態と結合できる該本発明による実施形態の第３の変形では、本発明による該方法は、該署名エンティティとして知られているエンティティによってメッセージＭの該デジタルシグナチャを生成するように設計されている。前記署名エンティティは該証人を含む。
【００２７】
署名動作
前記署名エンティティは、
−該メッセージＭと、
−該チャレンジｄ、及び／又は該コミットメントＲと、
−該応答Ｄと、
を備える署名済みメッセージを取得するために署名動作を実行する。
【００２８】
前記署名エンティティは、以下のステップを実現することにより該署名動作を実行する。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人は前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。
・ステップ２：チャレンジｄの行為
該署名エンティティは、バイナリ行列を取得するために、その引数が該メッセージＭ及び各コミットメントＲであるハッシュ関数ｈを適用する。該署名エンティティは、このバイナリ行列からコミットメントＲの数に等しい数のチャレンジｄを抽出する。
・ステップ３：応答Ｄの行為
該証人は前記に指定されたプロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。
【００２９】
チェック動作
該メッセージＭの真正性を証明するために、コントローラと呼ばれているエンティティは該署名済みメッセージをチェックする。該署名済みメッセージを有する前記コントローラエンティティは以下のように進めることによってチェック動作を実行する。
【００３０】
・該コントローラがコミットメントＲ、チャレンジｄ、応答Ｄを有するケース
該コントローラがコミットメントＲ、チャレンジｄ、応答Ｄを有する場合、該コントローラは、該コミットメントＲ、該チャレンジｄ、及び該応答Ｄが、以下のタイプ
【数１５】
2008048451.tif 000017
の関係又は以下のタイプ
【数１６】
2008048451.tif 000018
の関係を満たすことを確認する。
その結果、該コントローラは、該メッセージＭ、該チャレンジｄ及び該コミットメントＲが該ハッシュ関数
【数１７】
2008048451.tif 000019
を満たすことを確認する。
【００３１】
・該コントローラがチャレンジｄと応答Ｄを有するケース
該コントローラがチャレンジｄと応答Ｄを有する場合、該コントローラは、各チャレンジｄと各応答Ｄに基づいて、以下のタイプ
【数１８】
2008048451.tif 000020
の関係又は以下のタイプ
【数１９】
2008048451.tif 000021
の関係を満たすコミットメントＲ’を再構築する。
その結果、該コントローラは、該メッセージＭ及び該チャレンジｄが該ハッシュ関数
【数２０】
2008048451.tif 000022
を満たすことを確認する。
【００３２】
・該コントローラがコミットメントＲ及び応答Ｄを有するケース
該コントローラがコミットメントＲ及び応答Ｄを有する場合、該コントローラは該ハッシュ関数を適用し、ｄ’
【数２１】
2008048451.tif 000023
を再構築する。
その結果、該コントローラは、該コミットメントＲ、該チャレンジｄ’及び及び該応答Ｄが以下のタイプ
【数２２】
2008048451.tif 000024
の関係又は以下のタイプ
【数２３】
2008048451.tif 000025
の関係を満たすことを確認する。
【００３３】
システム
本発明は、該コントローラサーバに対して以下
−エンティティの真正性、及び／又は
−このエンティティと関連付けられたメッセージＭの完全性
を証明するように設計されているシステムにも関する。
【００３４】
この証明は、以下のパラメータ
−秘密値Ｑ1、Ｑ2、．．．Ｑmと公開値Ｇ1、Ｇ2，．．．Ｇmのｍ個の組（ｍは１以上）
−ｆ個の素因数ｐ1、ｐ2，．．．ｐfの積によって構成される公開係数ｎ（ｆは２以上）
又はこれらのパラメータの算出値のすべて又は一部によって立証される。
【００３５】
前記係数及び前記秘密値と公開値は以下のタイプの関係
【数２４】
2008048451.tif 000026
によって結び付けられ、この場合ｖは以下のタイプ
ｖ＝２k
の公開指数を示し、この場合ｋは１より大きなセキュリティパラメータであり、
前記ｍ個の公開値Ｇiは該ｆ個の素因数ｐ1，ｐ2，．．．ｐfに従うｍ個の区別できるベース数ｇ1ｇ2，．．．ｇmの二乗ｇi2であり、前記ｆ個の素因数ｐ1，ｐ2，．．．ｐf、及び／又は前記ｍ個のベース数ｇ1ｇ2，．．．ｇmは以下の条件が満たされるように生成される。
【００３６】
第１の条件：
第１の条件に従えば、該方程式
【数２５】
2008048451.tif 000027
のそれぞれは、ｎを法とした整数の環の中のｘについて解くことができる。
【００３７】
第２の条件：
第２の条件に従えば、Ｇi≡Ｑiv（mod n）のケースでは、ｋ−１階数回、Ｑiを二乗する（mod n）ことによって得られる該ｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００３８】
第２の条件に従えば、Ｇj，Ｑiv≡１（mod n）のケースでは、Ｑiの逆数（mod n）をｋ−１階数回二乗する（mod n）ことによって得られるｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００３９】
現在の表記に従えば、±ｇiが数ｇiとｎ−ｇiとを表していることがここで指摘されるべきである。
【００４０】
第３の条件：
第３の条件に従えば、以下の２ｍ個の方程式
【数２６】
2008048451.tif 000028
の中で、それらの内の少なくとも１つはｎを法として整数の環の中のｘについて解くことができる。
【００４１】
前記システムは、例えばマイクロプロセッサをベースにした銀行カードの形等、特にノマドオブジェクトに含まれている証人デバイスを備える。該証人デバイスは、ｆ個の素因数ｐi、及び／又は該素因数のチャイニーズ剰余のパラメータ、及び／又は該公開係数ｎ、及び／又はｍ個の秘密値Ｑi、及び／又は該秘密値Ｑiと該公開指数ｖのｆ．ｍ個の成分Ｑi,j（Ｑi,j≡Ｑi、modｐj）とを含むメモリゾーンを備える。該証人デバイスは、
−以下に該証人デバイスの無作為値生成手段と呼ばれる無作為値生成手段と、
−以下に該証人デバイスのコミットメントＲの該計算のための手段と呼ばれる計算手段と、
をさらに備える。
【００４２】
該計算手段により、ｎを法として整数の環の中でコミットメントＲを計算することが可能になる。各コミットメントは
・以下のタイプ
【数２７】
2008048451.tif 000029
の演算を実行し、この場合ｒは無作為因数生成手段によって生成される無作為な値であり、ｒは０＜ｒ＜ｎであることと、
・あるいは以下のタイプ
【数２８】
2008048451.tif 000030
の演算を実行し、この場合ｒiは、０＜ｒi＜ｐiとなるように該素因数ｐiと関連付けられた無作為な値であり、各ｒiは該無作為因数生成手段によって、及び次に該チャイニーズ剰余方法を適用することによって生成される無作為な値の集合体｛ｒi，ｒ2，．．．ｒf｝に属することとの、いずれかによって計算される。
【００４３】
また該証人デバイスは、
−以下に１つ又は複数のチャレンジｄを受信するための、該証人デバイスの該チャレンジｄの受信のための手段と呼ばれている受信手段であって、各チャレンジｄが以下に基本的なチャレンジと呼ばれるｍ個の整数ｄiを備える受信手段と、
−以下に、
・以下のタイプ
【数２９】
2008048451.tif 000031
の演算を実施することによって、
・又は以下のタイプ
【数３０】
2008048451.tif 000032
の演算を実施することのいずれかによって
及び次に該チャイニーズ剰余法を適用することによって、
各チャレンジｄに基づいた応答Ｄの計算のための、該証人デバイスの該応答Ｄの該計算のための手段と呼ばれる計算手段と、
をさらに備える。
【００４４】
該証人デバイスは、１つ又は複数のコミットメントＲ及び１つ又は複数の応答Ｄを送信するための伝送手段も備える。前記手法はチャレンジｄ、コミットメントRと同じくらいの数の応答Dがあって、R,ｄ、Dの数の群は｛R、d、D｝で参照される３つの数字の組で表されるトリプレットを形成する。
【００４５】
エンティティの真正性の証明のケース
実施形態の第１の変形では、本発明による該システムは、コントローラと呼ばれているエンティティに対して証明者と呼ばれているエンティティの真正性を証明するように設計されている。
【００４６】
前記システムは、証明者エンティティと関連付けられる証明者デバイスを備える。前記証明者デバイスは、相互接続手段によって該証人デバイスと相互接続されている。それは特に、マイクロプロセッサをベースにした銀行カードにおけるマイクロプロセッサの形式等のノマドオブジェクト内の論理マイクロ回路の形を取ることができる。
【００４７】
前記システムは該コントローラエンティティと関連付けられるコントローラデバイスも備える。前記コントローラデバイスは特に端末又はリモートサーバの形を取る。前記コントローラデバイスは、特にコンピュータ通信ネットワークを通して、該証明者デバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段を備える。
【００４８】
前記システムは、以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の手段は、前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。該証人デバイスは、該相互接続手段を通して該証明者デバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証人デバイスの伝送の手段と呼ばれる該伝送の手段を備える。また該証明者デバイスは、該接続手段を通して該コントローラデバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証明者の伝送手段と呼ばれている該伝送手段も備える。
・ステップ２：チャレンジｄの行為
該コントローラデバイスは、各コミットメントＲのすべて又は一部を受信した後に、コミットメントＲの数に数が等しい該チャレンジｄの該生成のためのチャレンジ生成手段を備える。該コントローラデバイスは、該接続手段を通して該証明者に該チャレンジｄを送信するために、以下に該コントローラの該伝送手段と呼ばれている伝送手段も備える。
・ステップ３：応答Ｄの行為
該証人デバイスの該チャレンジｄの受信の手段は、該相互接続手段を通して該証明者デバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄの計算の手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。
・ステップ４：チェックの行為
該証明者の該伝送手段は、該コントローラに各応答Ｄを送信する。また該コントローラデバイスは、
−以下に該コントローラデバイスの計算手段と呼ばれる該計算手段と、
−以下に該コントローラデバイスの比較手段と呼ばれる該比較手段と、
も備える。
【００４９】
第１のケース：該証明者が各コミットメントＲの部分を送信した。
該証明者の該伝送手段が各コミットメントＲの部分を送信した場合、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの該計算手段は、各チャレンジｄ及び各応答Ｄから再構築されたコミットメントＲ’を計算し、この再構築されたコミットメントＲ’は以下のタイプ
【数３１】
2008048451.tif 000033
の関係又は以下のタイプ
【数３２】
2008048451.tif 000034
の関係を満たす。
【００５０】
該コントローラデバイスの該比較手段は、各再構築されたコミットメントＲ’を受信された各コミットメントＲのすべて又は部分と比較する。
【００５１】
第２のケース：該証明者が各コミットメントＲの全体性を送信した。
該証明者の該伝送手段が各コミットメントＲの全体性を送信した場合、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの該計算手段と該比較手段は、各コミットメントＲが以下のタイプ
【数３３】
2008048451.tif 000035
の関係又は以下のタイプ
【数３４】
2008048451.tif 000036
の関係を満たすことを確認する。
【００５２】
メッセージの完全性の証明のケース
第１の変形と結合できる第２の変形の実施形態では、本発明による該システムは、コントローラとして知られているエンティティに対して、証明者として知られているエンティティと関連付けられたメッセージＭの完全性の証拠を示すように設計されている。前記システムは、該証明者エンティティと関連付けられている証明者デバイスを備える。前記証明者デバイスは、相互接続手段によって該証人デバイスと相互接続されている。それは、例えばマイクロプロセッサをベースにした銀行カード内のマイクロプロセッサの形等、特にノマドオブジェクトの論理マイクロ回路の形を取ってよい。前記システムは該コントローラエンティティと関連付けられている該コントローラデバイスも備える。前記コントローラデバイスは特に端末又はリモートサーバの形を取る。前記コントローラデバイスは、特にデータ処理通信ネットワークを通して、該証明者デバイスへのその電気的、電磁的、光学的、又は音響的な接続のための接続手段を備える。
【００５３】
前記システムは以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の手段が、前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。該証人デバイスは、該相互接続手段を通して各コミットメントＲのすべて又は部分を該証明者デバイスに送信するために、以下に該証人デバイスの伝送手段と呼ばれる伝送の手段を有する。
ステップ２：チャレンジｄの行為
該証明者デバイスは、少なくとも１つのトークンＴを計算するために、その引数が該メッセージＭ及び各コミットメントＲのすべて又は部分であるハッシュ関数ｈを適用する、以下に該証明者の計算の手段と呼ばれる該計算手段を備える。該証明者デバイスは、該接続手段を通して該コントローラデバイスに各トークンＴを送信するために、以下に該証明者デバイスの該伝送手段として知られている伝送手段も備える。該コントローラデバイスは、該トークンＴを受信後、コミットメントＲの数と数が等しい該チャレンジｄの該生成のためのチャレンジ生成手段も有する。該コントローラデバイスは、該接続手段を通して該証明者に該チャレンジｄを送信するために、以下に該コントローラの該伝送手段と呼ばれる伝送手段も有する。
・ステップ３：応答Ｄの行為
該証人デバイスの該チャレンジｄの受信の手段は、該相互接続手段を通して該証明者デバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄの計算の手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。
・ステップ４：チェックの行為
該証明者の該伝送手段は、該コントローラに各応答Ｄを送信する。該コントローラデバイスは、第１に、各チャレンジｄ及び各応答Ｄから以下のタイプ
【数３５】
2008048451.tif 000037
の関係又は以下のタイプ
【数３６】
2008048451.tif 000038
の関係を満たす再構築されたコミットメントＲ’を計算するために、
第２に、引数として、該メッセージＭ及び各再構築されたコミットメントＲ’のすべて又は部分を有する該ハッシュ関数ｈを適用することによってトークンＴ’を計算するために、以下に、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの該計算手段と呼ばれる計算手段も備える。
【００５４】
該コントローラデバイスは、該計算されたトークンＴ’を該受信されたトークンＴと比較するために、以下に該コントローラデバイスの該比較手段として知られている比較手段も有する。
【００５５】
メッセージのデジタルシグナチャ及びその真正性の証明
該最初の２つの実施形態の一方、及び／又は他方と結合できる、本発明による実施形態の第３の変形では、本発明による該システムは署名エンティティと呼ばれるエンティティによって、以下に署名済みのメッセージとして知られているメッセージＭのデジタルシグナチャを証明するように設計されている。
【００５６】
該署名済みのメッセージは、
−該メッセージＭと、
−該チャレンジｄ、及び／又は該コミットメントＲと、
−該応答Ｄと、
を備える。
署名動作
【００５７】
前記システムは、該署名エンティティと関連付けられている署名デバイスを備える。前記署名デバイスは相互接続手段によって該証人デバイスと相互接続され、例えば、マイクロプロセッサをベースにした銀行カードの中のマイクロプロセッサの形等の、特にノマドオブジェクト内の論理マイクロ回路の形を取ってよい。
【００５８】
前記システムは、以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の手段は前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。該証人デバイスは、該相互接続手段を通して該署名デバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証人デバイスの該伝送手段と呼ばれている伝送の手段を備える。
・ステップ２：チャレンジｄの行為
該署名デバイスは、バイナリ行列を計算するために、及び数がコミットメントＲの数に等しいチャレンジｄをこのバイナリ行列から抽出するために、その引数が該メッセージＭ、及び各コミットメントＲのすべて又は一部であるハッシュ関数ｈを適用する、以下に該署名デバイスの該計算手段と呼ばれている計算手段を備える。
・ステップ３：応答Ｄの行為
該証人デバイスの該チャレンジｄの受信のための手段は、該相互接続手段を通して該署名デバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄを計算するための手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。該証人デバイスは、該相互接続手段を通して該署名デバイスに該応答Ｄを送信するために、以下に該証人デバイスの伝送の手段と呼ばれている伝送手段を備える。
【００５９】
チェック動作
該メッセージＭの真正性を証明するために、コントローラとして知られているエンティティは該署名済みメッセージをチェックする。
【００６０】
前記システムは、該コントローラエンティティと関連付けられているコントローラデバイスを備える。前記コントローラデバイスは、特に端末又はリモートサーバの形を取る。前記コントローラデバイスは、特にコンピュータ通信ネットワークを通して、該署名デバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段を備える。
【００６１】
該署名エンティティと関連付けられた前記署名デバイスは、該接続手段を通して該署名済みメッセージの、該コントローラデバイスに対する伝送のための、以下に該署名デバイスの該伝送手段として知られている伝送手段を備える。したがって、該コントローラデバイスは、
−該メッセージＭと、
−該チャレンジｄ、及び／又は該コミットメントＲと、
−該応答Ｄと、
を備える署名済みのメッセージを有する。
【００６２】
該コントローラデバイスは、
−以下に該コントローラデバイスの該計算手段と呼ばれる計算手段と、
−以下に該コントローラデバイスの該比較手段と呼ばれる比較手段と、
を備える。
・該コントローラデバイスがコミットメントＲ、チャレンジｄ、応答Ｄを有するケース
該コントローラデバイスがコミットメントＲ、チャレンジｄ、応答Ｄを有する場合、該コントローラデバイスの該計算手段と比較手段は、該コミットメントＲ、該チャレンジｄ、及び該応答Ｄが以下のタイプ
【数３７】
2008048451.tif 000039
の関係又は以下のタイプ
【数３８】
2008048451.tif 000040
の関係を満たすことを確認する。
【００６３】
次に、該コントローラデバイスの該計算手段と比較手段は、該メッセージＭ、該チャレンジｄ及び該コミットメントＲが該ハッシュ関数
【数３９】
2008048451.tif 000041
を満たすことを確認する。
・該コントローラデバイスがチャレンジｄ及び応答Ｄを有するケース
該コントローラがチャレンジｄと応答Ｄとを有する場合、該コントローラの該計算手段は、各チャレンジｄと各応答Ｄに基づいて、以下のタイプ
【数４０】
2008048451.tif 000042
の関係又は以下のタイプ
【数４１】
2008048451.tif 000043
の関係を満たすコミットメントＲ’を再構築する。
【００６４】
次に、該コントローラデバイスの該計算手段と比較手段は、該メッセージＭ及び該チャレンジｄが該ハッシュ関数
【数４２】
2008048451.tif 000044
を満たすことを確認する。
・該コントローラがコミットメントＲ及び応答Ｄを有するケース
該コントローラデバイスがコミットメントＲと、応答Ｄとを有する場合、該コントローラデバイスの該計算手段は該ハッシュ関数を適用し、
【数４３】
2008048451.tif 000045
となるようにｄ’を計算する。
【００６５】
次に、該コントローラデバイスの該計算手段と比較手段は、該コミットメントＲ、該チャレンジｄ’、及び該応答Ｄが以下のタイプ
【数４４】
2008048451.tif 000046
の関係又は以下のタイプ
【数４５】
2008048451.tif 000047
の関係を満たすことを確認する。
【００６６】
端末装置
本発明は、エンティティに関連付けられる端末装置にも関する。該端末装置は、例えばマイクロプロセッサをベースにした銀行カードの中のマイクロプロセッサの形等、特にノマドオブジェクトの形を取る。該端末装置はコントローラデバイスに対して以下
−エンティティの真正性、及び／又は
−このエンティティと関連付けられているメッセージＭの完全性
を証明するように設計されている。
【００６７】
この証明は、以下のパラメータ
−秘密値Ｑ1、Ｑ2、．．．Ｑmと公開値Ｇ1、Ｇ2，．．．Ｇmのｍ個の組（ｍは１以上）
−ｆ個の素因数ｐ1、ｐ2，．．．ｐfの積によって構成される公開モジュールｎ（ｆは２以上）
又はこれらのパラメータの算出値のすべて又は一部によって立証される。
前記モジュール及び前記秘密値と公開値は以下のタイプの関係
【数４６】
2008048451.tif 000048
によって関連付けられ、この場合ｖは以下のタイプ
【数４７】
2008048451.tif 000049
の公開指数を示し、この場合ｋは１より大きなセキュリティパラメータである。
【００６８】
前記ｍ個の公開値Ｇiは該ｆ個の素因数ｐ1，ｐ2，．．．ｐfに従うｍ個の区別できるベース数ｇ1ｇ2，．．．ｇmの二乗ｇi2であり、前記ｆ個の素因数ｐ1，ｐ2，．．．ｐf、及び／又は前記ｍ個のベース数ｇ1ｇ2，．．．ｇmは以下の条件が満たされるように生成される。
【００６９】
第１の条件：
第１の条件に従えば、該方程式
【数４８】
2008048451.tif 000050
のそれぞれは、ｎを法とした整数の環の中のｘについて解くことができる。
【００７０】
第２の条件：
第２の条件に従えば、Ｇi≡Ｑiv（mod n）のケースでは、ｋ−１階数回、Ｑiを二乗する（mod n）ことによって得られる該ｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
第２の条件に従えば、Ｇi，Ｑiv≡１（mod n）のケースでは、Ｑiの逆数（mod n）をｋ−１階数回二乗する（mod n）ことによって得られるｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
現在の表記に従えば、±ｇiが数ｇiとｎ−ｇiとを表していることが、ここで指摘されるべきである。
【００７１】
第３の条件：
第３の条件に従えば、以下の２ｍ個の方程式
【数４９】
2008048451.tif 000051
の中で、それらの内の少なくとも１つはｎを法として整数の環の中のｘについて解くことができる。
【００７２】
前記端末装置は、該ｆ個の素因数ｐi、及び／又は該素因数のチャイニーズ剰余のパラメータ、及び／又は該公開係数ｎ、及び／又はｍ個の秘密値Ｑi、及び／又は該秘密値Ｑiと該公開指数ｖのｆ．ｍ個の成分Ｑi,j（Ｑi,j≡Ｑj、modｐj）とを含むメモリゾーンを備える証人デバイスを備える。
【００７３】
該証人デバイスは、
−以下に該証人デバイスの無作為値生成手段と呼ばれる無作為値生成手段と、
−以下に、ｎを法として該整数の環の中の該証人デバイスのコミットメントＲの該計算のための手段と呼ばれる計算手段と、
も備える。
【００７４】
各コミットメントは
・以下のタイプ
【数５０】
2008048451.tif 000052
の演算を実行し、この場合ｒは無作為値生成手段によって生成される無作為値であり、ｒは０＜ｒ＜ｎであることと、
・あるいは以下のタイプ
【数５１】
2008048451.tif 000053
の演算を実行し、この場合ｒiは、０＜ｒi＜ｐiとなるように該素数ｐiと関連付けられた無作為値であり、各ｒiは該無作為値生成手段によって、次に該チャイニーズ剰余方法を適用することによって生成される無作為値の集合体｛ｒ1，ｒ2，．．．ｒf｝に属することと、のいずれかによって計算される。
【００７５】
また該証人デバイスは、
−以下に１つ又は複数のチャレンジｄを受信するために該証人デバイスの該チャレンジｄの受信のための手段と呼ばれている受信手段であって、各チャレンジｄが以下に基本的なチャレンジと呼ばれるｍ個の整数ｄ1を備える受信手段と、
−以下に、
・以下のタイプ
【数５２】
2008048451.tif 000054
の演算を実行することによって、
・又は以下のタイプ
【数５３】
2008048451.tif 000055
の演算を実行することのいずれかによって
及び次に該チャイニーズ剰余法を適用することによって、
各チャレンジｄに基づいた応答Ｄの計算のための、該証人デバイスの該応答Ｄの該計算のための手段と呼ばれる計算手段と、
をさらに備える。
【００７６】
該証人デバイスは、１つ又は複数のコミットメントＲ及び１つ又は複数の応答Ｄを送信するための伝送手段も備える。チャレンジｄ、コミットメントRと同じくらいの数の応答Dがあって、R,ｄ、Dの数の群は｛R、d、D｝で参照されるトリプレットを形成する。
【００７７】
エンティティの真正性の証明のケース
第１の実施形態の変形では、本発明による該端末装置は、コントローラと呼ばれているエンティティに対して証明者と呼ばれているエンティティの真正性を証明するように設計されている。
【００７８】
前記端末装置は、証明者エンティティと関連付けられる証明者デバイスを備える。前記証明者デバイスは、相互接続手段によって該証人デバイスと相互接続されている。それは特に、マイクロプロセッサをベースにした銀行カードにおけるマイクロプロセッサの形式等の、ノマドオブジェクト内の論理マイクロ回路の形を取ってよい。
【００７９】
前記証明者デバイスは、特にデータ処理通信ネットワークを通して、該コントローラエンティティと関連付けられている該コントローラデバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段も備える。前記コントローラデバイスは特に端末又はリモートサーバの形を取る。
【００８０】
前記端末装置は、以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の手段は、前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。
該証人デバイスは、該相互接続手段を通して該証明者デバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証人デバイスの伝送の手段と呼ばれる該伝送の手段を有する。また該証明者デバイスは、該接続手段を通して該コントローラデバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証明者の伝送手段と呼ばれている該伝送手段も有する。
・ステップ２と３：チャレンジｄの行為、応答Ｄの行為
該証人デバイスの該チャレンジｄの受信手段は、該コントローラデバイスと該証明者デバイスの間の該接続手段を通して、及び該証明者デバイスと該証人デバイスの間の該相互接続手段を通して該コントローラデバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄの計算手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。
・ステップ４：チェックの行為
該証明者の該伝送手段は、チェックを実施する該コントローラデバイスに各応答Ｄを送信する。
【００８１】
メッセージの完全性の証明のケース
該第１の実施形態と結合できる第２の実施形態の変形では、本発明による該端末装置は、証明者として知られているエンティティに関連付けられるメッセージＭの完全性の証拠を、コントローラとして知られているエンティティに与えるように設計されている。前記端末装置は、それが該証明者エンティティと関連付けられている証明者デバイスを備え、前記証明者デバイスは相互接続手段によって該証人デバイスと相互接続されている。それは、例えばマイクロプロセッサをベースにした銀行カードの中のマイクロプロセッサの形等の、特にノマドオブジェクト内の論理マイクロ回路の形を取ってよい。前記証明者デバイスは、特にデータ処理通信ネットワークを通して、該コントローラエンティティと関連付けられている該コントローラデバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段を備える。前記コントローラデバイスは特に端末又はリモートサーバの形を取る。
【００８２】
前記端末装置は、以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の該手段は、前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。該証人デバイスは、該相互接続手段を通して該証明者デバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証人デバイスの該伝送手段と呼ばれる伝送の手段を有する。
・ステップ２と３：チャレンジｄの行為、応答Ｄの行為
該証明者デバイスは、少なくとも１つのトークンＴを計算するために、その引数が該メッセージＭ及び各コミットメントＲのすべて又は一部であるハッシュ関数ｈを適用する、以下に該証明者の計算手段と呼ばれる該計算手段を備える。該証明者デバイスは、該コントローラデバイスに該接続手段を通して各トークンＴを送信するために、以下に該証明者デバイスの伝送手段として知られている該伝送手段も有する。
前記コントローラデバイスは、該トークンＴを受信後、コミットメントＲの数に数が等しいチャレンジｄを生成する。
該証人デバイスの該チャレンジｄの受信の手段は、該コントローラデバイスと該証明者デバイスの間の該相互接続手段を通して、及び該証明者デバイスと該証人デバイスの間の該相互接続手段を通して該コントローラデバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄの計算の手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。
・ステップ４：チェックの行為
該証明者の該伝送手段は、各応答Ｄを該チェックを実行する該コントローラデバイスに送信する。
【００８３】
メッセージのデジタル署名及びその真正性の証明
最初の２つのいずれか一方と結合できる第３の実施形態の変形では、本発明による該端末装置は署名エンティティと呼ばれるエンティティによって、以下に該署名済みメッセージとして知られているメッセージＭの該デジタルシグナチャを生成するように設計されている。
【００８４】
該署名済みメッセージは、
−該メッセージＭと、
−該チャレンジｄ、及び／又は該コミットメントＲと、
−該応答Ｄと、
を備える。
【００８５】
前記端末装置は、該署名エンティティと関連付けられている署名デバイスを備える。前記署名デバイスは相互接続手段によって該証人デバイスと相互接続される。それは、マイクロプロセッサをベースにした銀行カードの中のマイクロプロセッサの形等の、特にノマドオブジェクトの中の論理マイクロ回路の形を取ってよい。前記署名デバイスは、特にデータ処理通信ネットワークを通して、該コントローラエンティティと関連付けられている該コントローラデバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段を備える。前記コントローラデバイスは特に端末又はリモートサーバの形を取る。
【００８６】
署名動作：
前記端末装置は以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の手段は、前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。該証人デバイスは、該相互接続手段を通して該署名デバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証人デバイスの伝送手段と呼ばれている該伝送の手段を備える。
・ステップ２：チャレンジｄの行為
該署名デバイスは、バイナリ行列を計算し、その数がコミットメントＲの数に等しいチャレンジｄをこのバイナリ行列から抽出するために、その引数が該メッセージＭ及び各コミットメントＲのすべて又は部分であるハッシュ関数ｈを適用する、以下に該署名デバイスの計算手段と呼ばれる該計算手段を備える。
・ステップ３：応答Ｄの行為
該チャレンジｄの該受信のための該手段は、該相互接続手段を通して該署名デバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄを計算するための該手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。該証人デバイスは、該相互接続手段を通して該署名デバイスに該応答Ｄを送信するために、以下に該証人デバイスの伝送の手段と呼ばれている伝送手段を備える。
【００８７】
コントローラデバイス
本発明は、コントローラデバイスにも関する。該コントローラデバイスは特にコントローラエンティティと関連付けられた端末又はリモートサーバの形を取ってよい。該コントローラデバイスは、
−エンティティの真正性、及び／又は
−このエンティティと関連付けられるメッセージＭの完全性
をチェックするように設計されている。
【００８８】
この証明は、以下のパラメータ
−公開値Ｇ1、Ｇ2，．．．Ｇmのｍ個の組（ｍは１以上）
−ｆ個の素因数ｐ1、ｐ2，．．．ｐfの積によって構成され（ｆは２以上）、該コントローラデバイス及び該関連付けられたコントローラエンティティに未知の公開係数ｎ
又はこれらのパラメータの算出値のすべて又は一部によって立証される。
前記係数及び前記秘密値と公開値は以下のタイプの関係
【数５４】
2008048451.tif 000056
によって関連付けられ、この場合ｖは以下のタイプ
【数５５】
2008048451.tif 000057
の公開指数を示し、この場合ｋは１より大きなセキュリティパラメータである。
【００８９】
前記ｍ個の公開値Ｇiは該ｆ個の素因数ｐ1，ｐ2，．．．ｐfに従うｍ個の区別できるベース数ｇ1ｇ2，．．．ｇmの二乗ｇi2であり、前記ｆ個の素因数ｐ1，ｐ2，．．．ｐf、及び／又は前記ｍ個のベース数ｇ1ｇ2，．．．ｇmは以下の条件が満たされるように生成される。
【００９０】
第１の条件：
第１の条件に従えば、該方程式
【数５６】
2008048451.tif 000058
のそれぞれは、ｎを法とした整数の環の中のｘについて解くことができる。
【００９１】
第２の条件：
第２の条件に従えば、Ｇi≡Ｑiv（mod n）のケースでは、ｋ−１階数回、Ｑiを二乗する（mod n）ことによって得られる該ｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００９２】
第２の条件に従えば、Ｇi，Ｑiv≡１（mod n）のケースでは、Ｑiの逆数（mod n）をｋ−１階数回二乗する（mod n）ことによって得られるｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００９３】
現在の表記に従えば、±ｇiが数ｇiとｎ−ｇiとを表していることがここで指摘されるべきである。
【００９４】
第３の条件：
第３の条件に従えば、以下の２ｍ個の方程式
【数５７】
2008048451.tif 000059
の中で、それらの内の少なくとも１つはｎを法として整数の環の中のｘについて解くことができる。
【００９５】
エンティティの真正性の証明のケース
第１の実施形態の変形では、本発明による該コントローラデバイスは、証明者と呼ばれているエンティティ及びコントローラと呼ばれているエンティティの真正性を証明するように設計されている。
【００９６】
前記コントローラデバイスは、特にデータ処理通信ネットワークを通して、該証明者エンティティと関連付けられている該証明者デバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段も備える。
【００９７】
前記コントローラデバイスは、以下のステップを実行するために使用される。
・ステップ１と２：コミットメントＲの行為、チャレンジｄの行為
前記コントローラデバイスは、該接続手段を通して該証明者デバイスから来る該コミットメントＲのすべて又は部分の受信のための手段も有する。
該コントローラデバイスは、各コミットメントＲのすべて又は部分を受信後、コミットメントＲの数に数が等しい該チャレンジｄの該生成のためのチャレンジ生成手段を備え、各チャレンジｄは以下に基本的なチャレンジと呼ばれているｍ個の整数ｄiを備える。
該コントローラデバイスは、該接続手段を通して該証明者に該チャレンジｄを送信するために、以下に該コントローラの伝送手段と呼ばれている該伝送手段も備える。
・ステップ３と４：応答Ｄの行為、チェックの行為
またコントローラデバイスは、
−該接続手段を通して該証明者デバイスから来る該応答Ｄの受信のための手段と、
−以下に該コントローラデバイスの計算手段と呼ばれている該計算手段と、
−以下に該コントローラデバイスの比較手段と呼ばれている該比較手段と、
も備える。
・第１のケース：該証明者が各コミットメントＲの部分を送信した
該コントローラデバイスの該受信手段が各コミットメントＲの部分を受信した場合、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの該計算手段は、以下のタイプ
【数５８】
2008048451.tif 000060
の関係又は以下のタイプ
【数５９】
2008048451.tif 000061
の関係を満たす再構築されたコミットメントＲ’を、各チャレンジｄ及び各応答Ｄから計算する。
【００９８】
該コントローラデバイスの該比較手段は、再構築された各コミットメントＲ’を受信された各コミットメントＲのすべて又は部分と比較する。
・第２のケース：該証明者が各コミットメントＲの全体性を送信した
該コントローラデバイスの該受信手段が各コミットメントＲの全体性を受信した場合、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの該計算手段と該比較手段は、各コミットメントＲが以下のタイプ
【数６０】
2008048451.tif 000062
の関係又は以下のタイプ
【数６１】
2008048451.tif 000063
の関係を満たすことを確認する。
【００９９】
メッセージの完全性の証明のケース
該第１の実施形態の変形と結合できる第２の実施形態の変形では、本発明による該コントローラデバイスは、証明者として知られているエンティティと関連付けられているメッセージＭの完全性を証明するように設計されている。
【０１００】
前記コントローラデバイスは、特にデータ処理通信ネットワークを通して、該証明者エンティティと関連付けられている証明者デバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段を備える。
【０１０１】
前記コントローラデバイスは以下のステップを実行するために使用される。
・ステップ１と２：コミットメントＲの行為、チャレンジｄの行為
前記コントローラデバイスは、該接続手段を通して該証明者デバイスから来るトークンＴの該受信のための手段を有する。該コントローラデバイスは、該トークンＴを受信した後に、コミットメントＲの数に数が等しいチャレンジｄの該生成のためのチャレンジ生成手段を有し、各チャレンジｄは以下に基本的なチャレンジと呼ばれているｍ個の整数ｄiを備える。該コントローラデバイスは、該接続手段を通して該証明者に該チャレンジｄを送信するために、以下に該コントローラの伝送手段と呼ばれている該伝送手段も備える。
・ステップ３と４：応答Ｄの行為、チェックの行為
前記コントローラデバイスは、該接続手段を通して該証明者デバイスから来る該応答Ｄの該受信のための手段も備える。前記コントローラデバイスは、第１に、以下のタイプ
【数６２】
2008048451.tif 000064
の関係又は以下のタイプ
【数６３】
2008048451.tif 000065
の関係を満たす再構築されたコミットメントＲ’を各チャレンジｄ及び各応答Ｄから計算するために、
第２に、引数として、該メッセージＭ及び各再構築されたコミットメントＲ’のすべて又は部分を有するハッシュ関数ｈを適用することによってトークンＴ’を計算するために、以下にｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの計算手段と呼ばれている該計算手段も備える。
【０１０２】
該コントローラデバイスは、該計算されたトークンＴ’を該受信されたトークンＴと比較するために、以下に該コントローラデバイスの比較手段と呼ばれている該比較手段も有する。
【０１０３】
メッセージのデジタルシグナチャ及びその真正性の証明
該最初の２つの実施形態の一方又は他方のいずれかと結合できる第３の実施形態の変形では、本発明によるコントローラデバイスは、コントローラと呼ばれているエンティティによって署名済みのメッセージをチェックすることによって該メッセージＭの真正性を証明するように設計されている。
【０１０４】
ハッシュ関数ｈ（メッセージ、Ｒ）を有する署名エンティティと関連付けられている署名デバイスによって送信される該署名済みメッセージは、
−該メッセージＭと、
−該チャレンジｄ、及び／又は該コミットメントＲと、
−該応答Ｄと、
を備える。
【０１０５】
チェック動作
前記コントローラデバイスは、特にデータ処理通信ネットワークを通して、該署名エンティティに関連付けられている署名デバイスに対するその電気的、電磁的、光学的、又は音響的な接続のための接続手段を備える。前記コントローラデバイスは、該接続手段を通して、該署名デバイスから該署名済みメッセージを受信する。
【０１０６】
該コントローラデバイスは、
−以下に該コントローラデバイスの計算手段と呼ばれる該計算手段と、
−以下に該コントローラデバイスの比較手段と呼ばれる該比較手段と、
を備える。
【０１０７】
・該コントローラデバイスが、コミットメントＲ、チャレンジｄ、応答Ｄを有するケース
該コントローラデバイスがコミットメントＲ、チャレンジｄ、応答Ｄを有する場合、該コントローラデバイスの該計算手段と比較手段は、該コミットメントＲ、該チャレンジｄ及び該応答Ｄが以下のタイプ
【数６４】
2008048451.tif 000066
の関係又は以下のタイプ
【数６５】
2008048451.tif 000067
の関係を満たすことを確認する。
【０１０８】
その結果、該コントローラデバイスの該計算手段と比較手段は、該メッセージＭ、該チャレンジｄ及び該コミットメントＲが該ハッシュ関数
【数６６】
2008048451.tif 000068
を満たすことを確認する。
【０１０９】
・該コントローラデバイスがチャレンジｄ及び応答Ｄを有するケース
該コントローラデバイスがチャレンジｄと応答Ｄを有する場合、該コントローラデバイスの該計算手段は、各チャレンジｄ及び各応答Ｄに基づいて、以下のタイプ
【数６７】
2008048451.tif 000069
の関係又は以下のタイプ
【数６８】
2008048451.tif 000070
の関係を満たすコミットメントＲ’を計算することができ、次に該コントローラデバイスの該計算手段と比較手段は、該メッセージＭ及び該チャレンジｄが該ハッシュ関数
【数６９】
2008048451.tif 000071
を満たすことを確認する。
【０１１０】
・該コントローラデバイスがコミットメントＲ及び応答Ｄを有するケース
該コントローラデバイスがコミットメントＲ及び応答Ｄを有する場合、該コントローラデバイスの該計算手段は該ハッシュ関数を適用し、
【数７０】
2008048451.tif 000072
となるようにｄ’を計算し、その結果該コントローラデバイスの該計算手段と比較手段は、該コミットメントＲ、該チャレンジｄ’、及び該応答Ｄが以下のタイプ
【数７１】
2008048451.tif 000073
の関係又は以下のタイプ
【数７２】
2008048451.tif 000074
の関係を満たすことを確認する。
【０１１１】
ＧＱ方法の目標は、メッセージのデジタルシグナチャとともにエンティティ及びメッセージの動的認証である。これらは「知識の移転を伴わない」方法である。エンティティは、それが１つ又は複数の秘密数を知っていることを証明する。別のエンティティは、それが対応する１つ又は複数の公開数を知っているかチェックする。該証明する側のエンティティは、必要に応じて何度でもそれらを使用できるようにするために、該１つ又は複数の秘密数を明らかにすることなく、該チェック側のエンティティを説得することを希望する。
【０１１２】
各ＧＱ方法は、秘密の高い素数から構成される公開係数に依存している。公開指数ｖ及び公開係数ｎはともに、「ｎを法としてｖ乗する」ことを意味する検証鍵＜ｖ，ｎ＞を形成し、１つ又は複数の一般的な方程式によって、すべて同じタイプの直接的なＧ≡Ｑv（mod n）又は逆のＧｘＱv≡１（mod n）を実現する。該タイプは該チェック側エンティティの中の計算の演算に影響を及ぼすが、該証明側エンティティの中では影響を及ぼさない。つまり、事実上、該セキュリティ分析は該２つのタイプを混同する。公開数Ｇと秘密数Ｑに結び付けられた各一般方程式は、ともに１組の数｛Ｇ，Ｑ｝を形成する。再開するためには、各ＧＱ方法は同じ鍵＜ｖ，ｎ＞に対して１つ又は複数の組の数｛Ｇ，Ｑ｝を実現する。
【０１１３】
ここでＧＱ１と呼ばれているＧＱ方法の旧バージョンは、ＲＳＡデジタルシグナチャ機構を使用する。その結果、該検証鍵＜ｖ，ｎ＞は、奇数の指数ｖが好ましくは素数であるＲＳＡ公開鍵である。一般的には、各ＧＱ１方法は数｛Ｇ，Ｑ｝の単一の組を使用する。つまり、該公開数Ｇは、該ＲＳＡデジタルシグナチャ技術の欠くことのできない部分であるフォーマット機構に従って識別データから推定される。該秘密数Ｑ又はｎを法としたその逆数は、識別データのためのＲＳＡシグナチャである。該証明エンティティは独自の識別データのＲＳＡシグナチャのその知識を示し、この証明は、必要に応じて何度でも使用されるために、したがって秘密のままとなる該シグナチャを明らかにしない。
【０１１４】
ＧＱ１方法は、一般的に２つのレベルの鍵を実現する。つまり、該ＲＳＡ秘密署名鍵は、自らを識別データによって他のものと区別する権威認定エンティティのために確保されている。このような機構は「アイデンティティに基づいている」と言われている。したがって、チップカードのエミッタは、該カードに多様な秘密鍵として銘記される秘密数Ｑを計算するために各カードの排出のために自分のＲＳＡ秘密鍵を使用する。あるいはさらに、コンピュータのネットワーク上のクライアントは、セッションの間に該クライアントの一時的な秘密鍵となる秘密数Ｑを計算するためにそれぞれの該セッションに入るときに自分のＲＳＡ秘密鍵を使用する。該証明側エンティティ、チップカード、又はセッション中のクライアントは、自分達の識別データのＲＳＡシグナチャを知っている。彼らは、鍵階層の中では次に高いレベルにある該ＲＳＡ秘密鍵を知らない。それにも関わらず、権威者のレベルにおいて７６８ビットの係数を用いるＧＱ１によるエンティティの動的認証は、各エンティティのレベルにある３つの素因数の５１２ビットの係数を用いるＲＳＡによるエンティティの動的認証とほぼ同じ作業負荷を必要とし、該証明側エンティティがその積のためのモジュロ結果を計算する前に該素因数のそれぞれにモジュロ結果を計算することによって該チャイニーズ剰余技法を使用できるようになる。
【０１１５】
しかしながら、権威者と該認定されたエンティティの間の鍵の階層は強制的なものではない。該証明側エンティティのレベルでの係数が、例えば７６８ビットと比べて５１２ビット等、該権威者のレベルの係数より低いことがあるという事実は別として、ＧＱ１は該証明側エンティティに属するモジュールと使用することができ、該証明側エンティティの作業負荷を削減するために該チャイニーズ剰余技法を使用できるようにし、基本的には該チェック側エンティティの作業負荷を変更しない。
【０１１６】
該エンティティが独自の係数の素因数を知っているときに、なぜＲＳＡデジタルシグナチャ機構に呼び掛けるのか？？
【０１１７】
ここでは基本的なＧＱ２と呼ばれているＧＱ法の別のバージョンは、係数ｎの因数分解の問題を直接的に処理している。この文脈では「直接的に」との表現は「ＲＳＡシグナチャを要求しないで」ということを意味する。ＧＱ２の目的は、該証明側エンティティだけではなく、該チェック側エンティティの作業負荷も削減することである。該証明側エンティティは独自の係数の分解（ｂｒｅａｋｄｏｗｎ）についての知識を立証し、この証明は、必要に応じて頻繁に使用できるようにするために、したがって秘密のままとなる分解を明らかにしない。該ＧＱ２プロトコルのセキュリティは該モジュールの因数分解に同等である。
【０１１８】
各証明側エンティティは独自の係数ｎを有している。各ＧＱ２機構はパラメータｋ、公開指数ｖ＝２kを固定する１より大きい小さな数、及び数｛Ｇ1，Ｑ1｝から｛Ｇm，Ｑm｝の１つ又は複数の組を実現する。各公開数Ｇ1は、１より大きい小さな数ｇiの二乗であり、「ベース数」と呼ばれている。すべての該証明側エンティティは、１つ又は複数の該同じ公開数Ｇ1からＧmを使用できる。その結果、該係数ｎ及び１つ又は複数の該秘密数Ｑ1からＱmの該因数分解は、該鍵階層の同じレベルにある。基本的なＧＱ２鍵の各集合は、以下の２つの必要かつ十分な条件によって定義される。
−ベース数ごとに、該２つの方程式ｘ2≡±ｇi（mod n）のどちらもｎを法として整数の環の中のｘについて解を有する。すなわち、該数±ｇiはｎを法として２つの非平方剰余である。
−ベース数ごとに、該方程式ｘv≡±ｇi2（mod n）であり、この場合ｖ＝２kはｎを法として整数の環の中のｘについて解を有する。ｎを法として該秘密数Ｑi又はその逆数はこれらの解の内の任意の１つである。
【０１１９】
該第２の条件を考慮に入れると、該数±ｇiがｎを法として２つの非平方剰余となるためには、該係数ｎは、ｇiのどのルジャンドル記号が異なるのかを基準にして、（４を法として）３と合同で少なくとも２つの素因数を備えなければならない。結果的に、どれも３（mod 4）と合同ではない、あるいはただ１つのものが３（mod 4）と合同である素因数から構成される任意の係数により、基本的なＧＱ２鍵の集合を確立することは可能ではなく、３（mod 4）と合同の該素因数に特権が与えられる。このようにして無作為に高い素数を取ることによって、半分だけが３（mod 4）と合同であり、半分が１（mod 4）に合同であるように見える。その結果、使用中の多くのＲＳＡモデルは基本的なＧＱ２鍵の集合を確立できない。
【０１２０】
ここで、この制限を克服し、どのような係数とであっても、特に任意のどのようなＲＳＡ係数であっても、ＧＱ２技術を使用できるようにするために一般化されたＧＱ２鍵の集合を紹介する。つまり、それらは以下の２つの必要且つ十分な原則に依存している。
【０１２１】
第１の原則は該第２の基本的なＧＱ２条件を再現する。
−ベース数ｇiからｇmごとに、方程式ｘv≡±ｇi2（mod n）であり、この場合ｖ＝２kはｎを法として整数の環の中のｘについて解を有する。
【０１２２】
秘密数Ｑ又はｎを法としてその逆数が該方程式の解であるため、ｎを法として連続したｋの二乗値−１はそれを、ｎを法として整数の環の中のＧ1の平方根である数ｑiに変換する。該数ｑiが該２つの数ｇi又はｎ−ｇiの一方に等しいのか、あるいは該２つの数ｇiとｎ−ｇiと異なるかどうかに応じて、それがトリビアルであるかどうかが言われる。数ｑiがトリビアルではないとき、ｑi2−ｇi2を除算するｎはｑi−ｇi又はｑi＋ｇiのどちらも除算しない。したがって任意のノントリビアル数ｑは係数ｎの分解を明らかにする。
ｎ＝ｐｇｃｄ（ｎ，ｑi−ｇi）ｘｐｇｃｄ（ｎ，ｑi＋ｇi）
【０１２３】
第２の原則は第１の基本的なＧＱ２条件を広げる。
−数ｑiからｑmの中では、少なくとも１つの数ｑiがトリビアルではない。
【０１２４】
該数±ｇiがｎを法として整数の環の中の２つの非平方剰余である一方、数ｑ＋が存在する場合、該ｑi数は明白にトリビアルではないことが留意されるべきである。したがって、基本的なＧＱ２鍵の集合は必ず、どのような係数でも、すなわち、その内の少なくとも２つが区別でき、差別せずに３と合同の、又は１（mod 4）と合同の高い素数の任意の構成の使用を可能にする、一般化されたＧＱ２鍵の該集合の一部である。他方、一般化されたＧＱ２鍵の多くの集合は基本的なＧＱ２鍵の集合ではない。一般化されたＧＱ２鍵の各集合は、以下のケースの１つに従っている。
−２ｘｍ個の数±ｇiから±ｇmがすべて非平方剰余であるとき、これは基本的なＣＱ２鍵の集合である。
−２ｘｍ個の数±ｇiから±ｇmの中で、少なくとも１つの平方剰余があるとき、これは基本的なＧＱ２鍵の集合ではなく、ここでは補完的なＧＱ２鍵の集合として知られているものである。
【０１２５】
本発明は補完的なＧＱ２鍵の該集合に関し、一般化されたＧＱ２鍵のこれらの集合は定義により基本的ではない。該２つの前記原則に加えて、このような集合は以下の第３の原則を満たさなければならない。
−２ｘｍ個の数±ｇiから±ｇmの中で、少なくとも１つの平方剰余がある。
【０１２６】
該問題を評価し、私たちが提供する解決策すなわち本発明を理解するために、まず第１に、ノントリビアル数ｑによって明らかにされた該係数ｎの該分解を分析し、次に該チャイニーズ剰余技法、それからガロア域ＣＧ（ｐ）の階数の概念に言及する。次に、ＣＧ（ｐ）の中の関数「二乗する」ことと、ＣＧ（ｐ）の平方剰余の「平方根を取る」こととを検討する。そして最後に、前述された３つの原則の適用性を分析する。
【０１２７】
該モジュールの分解の分析：
ちょうど該係数ｎがｆ個の素因数ｐiからｐfに分解されるように、ｎを法として整数の該環がｆ個のガロア域ＣＧ（ｐi）からＣＧ（ｐf）に分解される。各域において、２つの単位平方根があり、つまり±１である。したがって、該環の中には２f個の単位平方根がある。各秘密数Ｑ1からＱmは、該環ｎ中のこれらの２f個の単位平方根の内の１つである数Δi＝ｑi／ｇi（mod n）を定義する。言い換えると、ｎによってΔi2−１を除算する。
・ｑiがトリビアル、すなわちΔi＝±１であるとき、ｎはΔi−１又はΔi＋１を除算し、したがってΔiは該係数ｎの該分解を明らかにしない。
・ｑiがノントリビアル、すなわちΔiΔ±１であるとき、ｎはΔi−１もΔi＋１も除算せず、したがってΔによって、分解、つまり各域におけるΔiの値から生じるｎ＝ｐｇｃｄ（ｎ，Δi−１）ｘｐｇｃｄ（ｎ，Δi＋１）が明らかになる。つまり、一方では１つ又は複数の該素因数がΔi−１を除算し、これ又はこれらは他方でΔi＋１を除算する。
【０１２８】
該数ｑの乗法の構成（multiplicative composition）の規則の検査。２つの数｛ｑ1、ｑ2｝は、合成数、ｑ1ｘｑ2（mod n）を示す。
−ｑ1がトリビアルではなく、ｑ2がトリビアルであるとき、該合成数ｑ1ｘｑ2（mod n）はトリビアルではない。それはｑ1と同じ分解を明らかにする。
−ｑ1とｑ2がトリビアルではなく、Δ1＝±Δ2であるとき、該合成数ｑ1ｘｑ2（mod n）はトリビアルである。それは分解を明らかにしない。
−ｑ1とｑ2がトリビアルではなく、Δ１≠±Δ２であるとき、該合成数ｑ1ｘｑ2（mod n）はトリビアルではない。それは第３の分解を明らかにする。
【０１２９】
３つの数｛ｑ1、ｑ2、ｑ3｝は、４つの合成数｛ｑ１ｘｑ２、ｑ１ｘｑ３、ｑ２ｘｑ３、ｑ１ｘｑ２ｘｑ３（mod n）｝を示す。つまり、７つの数の合計である。したがって、ｍ個の数は２m−ｍ−１個の合成数を提供し、つまり２m−１個の数の合計である。
ここで、我々は、ｉ個の数ｑ1からｑi、したがって単位根であるｉ個の数Δ1からΔiを示す、ｉ個のベース数ｇ1からｇi及びｉ個の秘密数Ｑ1からＱiを備える一般化されたＧＱ２鍵の集合を考えるものとする。数ｑi+1、したがってルートΔi+1を示す秘密数Ｑi+1によって別のベース数ｇi+1を考慮に入れてみよう。
・２i+1−１個の数の合計は、以下のケースのそれぞれで多くのノントリビアル数を備える。
−該ルートΔi+1はトリビアルであり、少なくとも１つのルートΔ1からΔiはトリビアルではない。
−該ルートΔi+1はトリビアルではなく、該２ｘｉのルート±Δ1と±Δiの間に現れる。
・該ルートΔi+1がトリビアルではなく、該２ｘｉのルート±Δ1と±Δiの間に現れないケースでは、ｑi+1が現れる各合成数はトリビアルではない。
【０１３０】
その結果、ｍ個の数ｑ1からｑmの中で、少なくとも１つがトリビアルではないとき、該２m−１個の数の合計の半分より多くがトリビアルではない。
【０１３１】
定義により、ｌ＜ｆのノントリビアル数｛ｑ1、ｑ2、．．．ｑ1｝は、２l−ｌ−１個の対応する合成数のそれぞれがトリビアルではないとき、すなわち合計で２1−１個の数がすべてトリビアルではないときに、該係数ｎを基準にして独立していると言われる。こうして、これらの２l−１個のそれぞれによって該係数ｎの異なる分解が明らかになる。
−該ｆ個の素因数が区別できるとき、該係数ｎの２f-1−１個のの分解がある。したがって、ｆ−１個の数ｑが独立している場合、該２f-1−１個のの分解と、該ｆ−１個の独立した数と該２f-1−ｆ個の対応する合成数を備える２f-1−１個の数の合計の間にｂｉ−ｕｎｉｖｏｃａｌな対応がある。
・チャイニーズ剰余
２つの数ａとｂのいずれか、０＜ａ＜ｂであるそれらの間の素数、及び２つの数０からａ−１のＸaと０からｂ−１のＸb。それは、Ｘa≡Ｘ（ｍｏｄ ａ）及びＸb≡Ｘ（ｍｏｄ ｂ）となるように０からａｘｂ−１までの一意の数Ｘの決定に関する。数、ｘ≡｛ｂ（ｍｏｄ  ａ）｝-1（ｍｏｄ  ａ）がチャイニーズ剰余パラメータである。該基本的なチャイニーズ剰余動作は以下に示される。
ｘ≡Ｘb（ｍｏｄ ａ）
ｙ＝Ｘa−ｘ。ｙが負である場合は、ｙ＋ａでｙを置換する。
ｚ≡ａｘｙ（ｍｏｄ ａ）
Ｘ＝ｚｘｂ＋Ｘb
再開する場合、Ｘ＝Chinese Remainder（Ｘa，Ｘb）と書く。
ｆ個の素因数が低い方から順に、つまり最小のｐ1から最大のｐfまで配列されるとき、該チャイニーズ剰余パラメータは以下の通りとなることがある（該素因数より１つ少ない、すなわちｆ−１である）。
−第１のパラメータはｘ≡（ｐ2（ｍｏｄ  ｐ1））−１（ｍｏｄ  ｐ1）である。
−第２のパラメータはβ≡（ｐ1ｘｐ2（ｍｏｄ  ｐ3））-1（ｍｏｄ  ｐ3）である。
−該ｉ番目のパラメータはλ≡（ｐ1ｘ．．．ｐi-1（ｍｏｄ  ｐi））-1（ｍｏｄ ｐ1）
−等々。
ｆ−１個の基本的な（elementary）演算では、Ｘjが０からｐj−１である、Ｘ1からＸfまでのｆ個の成分の任意の集合から開始する０からｎ−１までの数Ｘを確立する。
−第１のパラメータ付きの第１の結果（ｍｏｄ  ｐ1ｘｐ2）
−次に第２のパラメータ付きの第２の結果（ｍｏｄ  ｐ1ｘｐ2ｘｐ3）
−最後のパラメータ付きの最後の結果（ｍｏｄ  ｎ＝ｐ1ｘｐ2ｘ．．．ｐf）まで
再開する場合、該素因数ｐ1からｐfを考えると、ｎを法として該整数の該環の各要素は２つの同等な表現を有している。
−ｆ個の数Ｘ1からＸf、素因数成分：Ｘj≡Ｘ（ｍｏｄ  ｐj）
−０からｎ−１までの数Ｘ、Ｘ＝チャイニーズ剰余（Ｘ1、Ｘ2．．．Ｘf）
ＣＧ（ｐ）の中の数の階数−ｐを奇数の素数とし、ａをｐより小さい、つまり０＜ａ＜ｂの数であるとする。定義によって、ｐに関してａの階数は｛ｘi＝ａ；その結果、ｉ≧１の場合、ｘi＋１≡ａ×ｘi（ｍｏｄ  ｐ）｝によって定義されるシーケンス［Ｘ］の期間である。フェルマ定理を適用することによって、以下を得る。ｘi+p＝ａp×ｘ1≡ａ×ｘi≡ｘi+1。（ｍｏｄ  ｐ）したがって、素数ｐに関する数ａの該階数はｐ−１又はｐ−１の除算器である。
【０１３２】
例えば、（ｐ−１）／２が奇数の素数ｐ’であるとき、該ガロア域ＣＧ（ｐ）は階数１の数を含む。これは１であり、階数２の数を含み、これは−１であり、階数ｐ’のｐ’−１数及び階数２ｘｐ’＝ｐ−１のｐ’−１数である。ＣＧ（ｐ）では、任意の数の階数ｐ−１は「生成元」である。該名前はＣＧ（ｐ）内の生成元の連続二乗、つまり１からｐ’−１までのインデックスのためのシーケンス「Ｘ」の項が、ＣＧ（ｐ）のすべてのゼロ以外の要素の順列をなすという事実に起因する。
【０１３３】
ｙをＣＧ（ｐ）の生成元であるとする。ｉ及びｐ−１に従って該数ｙ’ （ｍｏｄ  ｙ）の階数を評価しよう。ｉがｐ−１と互いに素であるとき、これはｐ−１である。ｉがｐ−１を除算するとき、これは（ｐ−１）／ｉになる。すべてのケースで、これは（ｐ−１）／ｌｇｃｄ（ｐ−１，ｉ）（ｌｇｃｄ＝最大公約数）である。
【０１３４】
定義によって、オイラーの関数ψ（ｎ）はｎより小さい数の中の数であり、ｎと互いに素である。ＣＧ（ｐ）では、ψ（ｐ−１）の生成元がある。
【０１３５】
例として、ＲＳＡの基礎を理解することは該階数で容易にされる。モジュールｎはｆ個の素因数ｐ−１からｐ−ｆの積であり、ｆ≧２である。ｐiからｐfまでの各素因数ｐiの場合、該公開指数ｅはｐj−１と互いに素でなければならない。ここで、鍵＜ｅ，ｐj＞はＣＧ（ｐj）の要素の階数を観察する。それはＣＧ（ｐj）の該要素を並べ替える。概して可能な限り小さい数ｄjが存在し、その結果ｐ-1がｅ×ｄj-1を除算する。鍵＜ｄj，ｐj＞は、ＣＧ（ｐj）の要素の該順列を反転させる。各域ＣＧ（ｐ1）からＣＧ（ｐf）に１つの、これらのｆ個の順列は、公開鍵＜ｅ，ｎ＞によって要約される該ＲＳＡ順列によって、ｎを法として整数の該環で表される。概して可能な限り小さい数ｄが存在し、その結果（ｐ1−１、ｐ2−１、．．．ｐf−１）の最小公倍数（ｓｃｍ）がｄ×ｅ−１を除算する。ｐ1からｐfまでの各素因数ｐjの場合、ｄj≡ｄ（ｍｏｄ ｐj-1）を有する。該公開鍵＜ｅ，ｎ＞によって要約された該ＲＳＡ順列は、該秘密鍵＜ｄ，ｎ＞によって反転する。
【０１３６】
ＣＧ（ｐ）の中の二乗−ｐ−１が２t-1ではなく２tで除算できるように数ｔを定義しよう。それぞれの大きな素数は唯一のカテゴリｔ＝１、ｔ＝２、ｔ＝３、ｔ＝４等に出現する。連続素数の十分に大きい数が検討される場合、２の中から約１が、ｐが３（ｍｏｄ  ４）と合同である第１のカテゴリに出現し、４の中から１が、ｐが５（ｍｏｄ  ８）と合同である第２のカテゴリに出現し、頂点（ｈｅｉｇｈｔ）の中から１が、ｐが９（ｍｏｄ  １６）と合同である第３のカテゴリに出現し、１６の中から１が、ｐが１７（ｍｏｄ  ３２）と合同である第４のカテゴリに出現する等である。平均すると、２tの中から１が、ｐが２t+1（ｍｏｄ ２t+1）に合同であるｎ番目のカテゴリに出現する。
【０１３７】
数ｘとｐ−ｘはＣＧ（ｐ）の中で同じ二乗を有するため、鍵＜２，ｐ＞はＣＧ（ｐ）を並べ替えない。ＣＧ（ｐ）の関数「二乗を取る」は、該域の各ゼロ以外の要素がその場所を見つける有向グラフによって表されてよい。各要素の該階数のパリティに従って、該グラフの構造を枝及び円まで分析してみよう。
【０１３８】
−ゼロ要素が設定されている。これは０である。階数は、他の要素が関連していない該ゼロ要素に対して定義されていない。つまりゼロ要素は隔離されている。
【０１３９】
−単位要素が設定されている。これは１であり、階数１の唯一の要素である。ＣＧ（ｐ）の個体のすべてのルートは１に関連付けられている枝の中に位置する。ｙをＣＧ（ｐ）の非平方剰余、任意の剰余とする。鍵＜（ｐ−１）／２t，ｐ＞はｙを、ｂとして参照される−１のプリミティブな２t-1番目のルートに変換する。つまり、ｙ(p-1)/2≡−１（ｍｏｄ  ｐ）を有する。したがって、ＣＧ（ｐ）では、１から２t-1までの累乗のためのｂの該二乗は１以外の個体の該２t-1ルートである。それらが１に関連する枝を作り上げる。
【０１４０】
−偶数の階数の任意の要素の該二乗は、その階数が２で除算される別の要素である。したがって、偶数の階数の各要素は枝の中に置かれる。各枝は、４でではなく２で除算できる階数を含み、次にｔ≧２の場合には、８でではなく４で除算できる２つの階数を含み、次にｔ≧３の場合には、１６でではなく８で除算できる４つの階数を含み、次にｔ≧４の場合には、３２でではなく１６で除算できる８つの階数を含む等である。すべての枝は１に関連付けられている枝に類似している。各枝の２t-1の葉は非平方剰余である。各枝は２t-1の要素を含み、奇数の階数の要素に関連付けられている。すべて同じ長さｔとなる（ｐ−１）／２tの枝がある。
【０１４１】
−該単位要素以外の奇数の階数の任意の要素の二乗は、同じ階数を有する別の要素である。鍵＜２，ｐ＞は、奇数の階数の（ｐ−１）／２tの要素の集合を並べ替える。該順列は順列サイクルに因数分解される。サイクル数は（ｐ−１）／２tの因数分解に依存する。（ｐ−１）／２tの各除算器Ｐ’に、階数ｐ’の該ψ（ｐ’）要素を含むサイクルがある。定義によって、オイラーの関数ψ（ｐ’）がｐ’より小さく、ｐ’と互いに素である数の中の数であることを思い出そう。例えば、ｐ’が（ｐ−１）／２tに等しく、互いに素であるとき、階数ｐ’のｐ’−１個の数は大きな順列サイクルを形成する。
【０１４２】
図１Ａから図１Ｄは、それぞれ３（ｍｏｄ ４）と合同、５（ｍｏｄ ８）と合同、９（ｍｏｄ １６）と合同、及び１７（ｍｏｄ ３２）と合同であるＰのグラフ部分をそれぞれ描いている。
−該枝の上の該葉は、白い円で描かれている。これらは非平方剰余である。
−該枝の中の節は灰色の円で描かれている。これらは偶数の階数の二次要素である。
−該円の中の該節は黒い円で描かれている。これらは偶数の階数の二次要素である。
【０１４３】
ＣＧ（ｐ）の中の平方根−ａがＣＧ（ｐ）の平方剰余であることを知っているので、該方程式ｘ2≡ａ（ｍｏｄ  ｐ）に対する解の計算方法を確かめよう。つまりＣＧ（ｐ）の中で「平方根を取る」。言うまでもなく、同じ結果を得るための多くの方法がある。数学シリーズの大学院生用教科書（Ｇｒａｄｕａｔｅ  Ｔｅｘｔｓ  ｉｎ  Ｍａｔｈｅｍａｔｉｃｓ  ｓｅｒｉｅｓ）の第１３８巻（ＧＴＭ  １３８）として１９９３年にベルリン（Ｂｅｒｌｉｎ）のスプリンガー（Ｓｐｒｉｎｇｅｒ）によって出版された、Ｈｅｎｒｉ  Ｃｏｈｅｎの書籍、計算代数的数論における過程（ａ  Ｃｏｕｒｓｅ  ｉｎ  Ｃｏｍｐｕｔａｔｉｏｎ  Ａｌｇｅｂｒａｉｃ  Ｎｕｍｂｅｒ  Ｔｈｅｏｒｙ）の３１から３６ページを参考にしてよい。
該数ｓ＝（ｐ−１＋２t）／２t+1は、
ｐが３（ｍｏｄ  ４）と合同であるときに＜（ｐ＋１）／４，ｐ＞であり、
ｐが５（ｍｏｄ  ８）と合同であるときに＜（ｐ＋３）／８，ｐ＞であり、
ｐが９（ｍｏｄ  １６）と合同であるときに＜（ｐ＋７）／１６，ｐ＞であり、
ｐが１７（ｍｏｄ  ３２）と合同であるときに＜（ｐ＋１５）／３２，ｐ＞である等の鍵＜ｓ，ｐ＞を提供する。
【０１４４】
−鍵＜ｓ，ｐ＞はサイクルの任意の要素を該サイクルの中の従前の要素に変換する。ａが偶数の階数であるとき、それは奇数階数の解であり、私たちはそれをｗと名付ける。つまり、ＣＧ（ｐ）では、ｗ2／ａはａの(２×（ｐ−１＋２t）／＜２t+1)−１＝（ｐ−１）／２t乗に等しい。他の解は偶数階数である。これはｐ−ｗである。
【０１４５】
−一般的に、該鍵＜ｓ，ｐ＞は該第１の近似の中の任意の平方剰余ａを、私たちがｒと名付ける解に変換する。ａは平方剰余であるため、該鍵＜２t-1，ｐ＞は必ずｒ2／ａを１に変換する。ａの平方根に近づく場合、＋１又は−１を得るためにｒ2／ａ（ｍｏｄ  ｐ）の２t-2乗を取ろう。該結果が＋１である場合には該新しい近似はｒのままとなり、それ以外の場合は、ｐが域ＣＧ（ｐ）内の１の任意のプリミティブな２t番目のルートを参照することを知っているので、該結果が−１である場合それはｂ×ｒ（ｍｏｄ  ｐ）になる。したがって、鍵＜２t-2，ｐ＞は該新しい近似を１に変換する。それは、該鍵＜２t-3，ｐ＞を使用することによって、及び必要な場合にはｂ２（ｍｏｄ  ｐ）で乗算することによって等で、依然として近づいてよい。
【０１４６】
以下のアルゴリズムが該方程式を解く。それは、前記に定義されたような数ａ、ｂ、ｐ、ｒ及びｔ、及び２つの変数を使用する。ｃは該連続補正を表し、ｗは該連続近似を表す。該アルゴリズムの最初では、ｃ＝ｂ及びｗ＝ｒである。該計算の最後では、該２つの解はｗとｐ−ｗである。
【０１４７】
ｔ−２から１までのｉの場合、以下のシーケンスを繰り返す。
−＋１又は−１を得るために、鍵＜２t，ｐ＞を数ｗ3／ａ（ｍｏｄ  ｐ）に適用する。
−−１が得られると、ｗをｗ×ｃ（ｍｏｄ  ｐ）で置き換える。
−ｃをｃ２（ｍｏｄ  ｐ）で置き換える。
【０１４８】
原則の適用性−定義によって、私たちは、パラメータｋ、ベース数ｇ及び素因数ｐが、指数ｖが２kである方程式ｘv≡ｇ2（ｍｏｄ  ｐ）が該域ＣＧ（ｐ）のｘについて解を有するときに矛盾しないという。数ｋとｇは小さく、１より大きい。数ｐは大きい素数である。
−ｔ＝１、つまりｐ≡３（ｍｏｄ  ４）であるとき、該方程式は２つの解を有する。
−ｔ＝２、つまりｐ≡５（ｍｏｄ  ８）であるとき、ｐに関してｇのルジャンドル記号に従って、該方程式は（ｇ｜ｐ）＝＋１である場合、４つの解を有し、（ｇ｜ｐ）＝−１である場合は、解を有さない。
−ｔ＞２、つまりｐ≡１（ｍｏｄ  ８）であるとき、ｕを、２uが公開数Ｇ＝ｇ2の階数をｐに関して除算するが、２u+1がそれを除算しないような該数にしよう。したがってｕは０からｔ−１の数の内の１つに等しい。該方程式はｕ＞０及びｋ＋ｕ＞ｔの場合、解を有さない。それはｋ＋ｕ≦ｔの場合２kの解を有する。ｕ＝０及びｋ＞ｔの場合はそれは２tの解を有する。
【０１４９】
したがって、Ｇがサイクル内にあるのか、又はそれ以外の場合枝の適切な位置にあるのかに従って、２つのタイプの適合性がある、
−Ｇがサイクル内にある、つまりｕ＝０であるとき、ｋの該値に関係なく、該サイクルの中に奇数階数の解、及び該サイクルに関連付けられたα＝最小（ｋ，ｔ）連続枝で広められる偶数階数の解、つまりすべての中に２αの解がある。図２Ａは、ｕ＝０を課す、ｋ≧ｔ＝３、つまり９（ｍｏｄ  １６）と合同である素因数のこのケースを描いている。
−Ｇが枝の適切な位置にあるとき、つまりｕ＞０及びｕ＋ｋ≦ｔのとき、すべて偶数階数の２kの解が枝の中にある。図２Ｂがこのケースを描いている。
【０１５０】
したがって、パラメータｋを考えると、ｔの該値がｋより少ないか、あるいはそれ以外の場合ｋより大きい又はｋに等しいかに従って、２つのタイプの素因数がある。
−ｔ＜ｋのような任意の素因数ｐjの場合、各Ｇiはサイクル内になければならず、Ｇiに関連付けられた枝に解はない。ｇiがサイクル内にあるのか、あるいは−ｇiがサイクル内にあるのかに従って、＋１又は−１である数Δi,jを定義しよう。ｍ個の数Δ1,jからΔm,jのどれにも選択肢はない。図３Ａは、ｔ＜ｋのケースを描いている。つまりＧiは、素因数ｐjが９（ｍｏｄ  １６）と合同であるサイクル内にある。つまりｋ＞３の場合にｕ＝０、ｔ＝３。
−ｔ≧ｋとなるような任意の素因数ｐjの場合、各Ｇiはｕ＋ｋ≦ｔ、つまり、ｕ＝０のサイクル内にあるか、あるいはそれ以外の場合１≦ｕ≦ｔ−ｋの枝の適切な位置にあるかのいずれかでなければならない。Ｑi,jがｇiに又は−ｇiに関連付けられた該グラフの該部分にあるかどうかに従って、＋１又は−１となる数Δi,jを定義しよう。ｍ個の数Δ1,jからΔm,jのそれぞれに選択肢がある。つまり、各数Δ1,jは個々に一方の値から他方の値に切り替えられてよい。図３Ｂは、ｔ≧ｋのときのケースを描いている。つまりＧiは、素因数ｐjが１７（ｍｏｄ  ３２）と合同である枝の中にある。つまりｋ＝３の場合にｕ＝１、ｔ＝４。
【０１５１】
ｆ個の成分｛Δi,j．．．Δi,f｝の各集合はＣＧ（ｐj）において個体の平方根である。このルートは、あるいは該ｆ個の成分が等しいかどうかに従ってトリビアルである、又はトリビアルではない。その結果、該数ｑiがトリビアルであるか、又はトリビアルではないかのいずれかであるという事実を表す、ｆ個の成分の該集合が一定である、又は可変であるという。したがって、数ｑiがノントリビアルであるとき、ｆ個の成分｛Δi,j．．．Δi,f｝の該集合は該モジュールの因数分解を要約する。したがって、該秘密成分Ｑi,jを計算する前に該原則を試すことが可能である。
−公開数Ｇiが素因数ｐjのためのサイクル内にあるとき、該数Δ1,jは、ｇiがサイクル内にあるのか、それとも−ｇiがサイクル内にあるのかに従って、＋１又は−１である。ｐj≡３（ｍｏｄ  ４）であるとき、これはルジャンドルの記号、Δi,j＝（ｇi｜ｐj）である。
−公開数Ｇiが素因数ｐjのための枝の適切な位置にあるとき、Δi,jに与えられる該値は該秘密成分Ｑiを計算することによって決定されてよい。
【０１５２】
鍵の集合の生成−パラメータｋを考慮すると、以下の２つの戦略がある。
−該生成元は、ｍ個のベース数を決定するためにｆ個の素因数を必要とする。該第1の素数２、３、５、７、．．．は、該ｆ個の大きな素因数ｐ1からｐfのそれぞれとのそれらの適合性を評価するために調べられる。ｇ＝２はｐ≡５（ｍｏｄ  ８）と適合しないが、２はベース数の構成に入ってよい。つまり、２つの数が枝の類似する位置にあるとき、それらの積は、まさに平方が該円をより密接にするため、さらに円に近くなる。ベース数はそれによって、個々には適切ではない該数を構成することによって得られてよい。
−あるいは、該生成元は、ｆ≧２個の素因数を決定するために、ビットサイズ（例えば、５１２、７６８、１０２４、１５３６，２０４８）及び強力な重みのある１まで連続するビットの数（例えば、１、８、１６、２４、３２）のように、ｍ個のベース数及び該モジュールの特性を必要とする。Ｇ1、Ｇ2，．．．Ｇmとして留意され、該ベース数は一般的には第１の素数、２、３、５、７、１１．．．の中に出現する、あるいはそれ以外の場合これらは該第１の素数の組み合わせである。特に別に示されないならば、これらは第１のｍ個の素数、Ｇ1＝２、Ｇ2＝３、Ｇ3＝５、Ｇ4＝７，．．．である。ｐ≡５（ｍｏｄ  ８）がｇ＝２と適合しないことに留意しよう。モジュールｎは、密接なサイズ、つまりｆで除算される該モジュールに割り当てられる該サイズとのｆ個の素因数の積になる。
【０１５３】
第１の原則−該パラメータｋ、ｐ1からｐfの各素因数、及びｇ1からｇmの各ベース数ｇは適合できなければならない。２h+1はそれを除算しないのに対して、２h等の数ｈがｇの該階数を、ｐに関して除算することを定義しよう。該数ｈを計算するために、以下の手順はルジャンドルの記号（ｇ｜ｐ）、及び数ｂ、つまりＣＧ（ｐ）の中の個体のプリミティブな２t番目のルートを使用する。
−ｔ＝１で（ｇ｜ｐ）＝＋１の場合、「ｈ＝０」を返す。
−ｔ＞１で（ｇ｜ｐ）＝＋１の場合、ｗと呼ばれる結果を得るために該鍵＜（ｐ−１＋２t）／２t+1，ｐ＞をＧに適用する。
−ｗ＝＋ｇの場合、「ｈ＝０」を返す。
−ｗ＝ｐ−ｇの場合、「ｈ＝１」を返す。
−それ以外の場合、ｃをｂに設定し、ｉの場合ｔ−１から２に設定する。
−±１を得るために、鍵＜２i，ｐ＞をｗ／ｇ（ｍｏｄ  ｐ）に適用する。
−−１の場合、ｈをｉに設定し、ｗをｗ×ｃ（ｍｏｄ  ｐ）に置き換える。
−ｃをｃ２（ｍｏｄ  ｐ）で置き換える。
−「２からｔ−１へのｈの値」を返す。
−（ｇ｜ｐ）＝−１の場合、「ｈ＝１」を返す。
【０１５４】
ｋ＋ｕ＞ｔでｕ＞０のときにｋ、ｇ及びｐが適合しないことを思い出そう。それらはｋの該値に関係なくｈ＝０又は１のときに、及び等しくｋ＋ｈ≦ｔ＋１でｋ＞１のときに適合する。
【０１５５】
第２の原則−以下の３つの手順は第２の原則のさまざまな実現例に対応する。特定の実現例では、該第２の原則は、各数ｑ1からｑmがトリビアルではないことを必要とする点まで強化されてよい。その結果、該ベース数の役割は安定している。つまり、該第２の原則を釣り合わせる、あるいは釣り合わせないことには、該方式の該セキュリティの該立証の特定の態様という効果がある。最後にｆ＞２の区別できる素因数があるとき、ｍ個の数｛ｑ1．．．ｑm｝の中ではｆ−１個の独立した数の少なくとも１つの部分集合があることが必要とされることがある。
【０１５６】
該３つの手順は、以下のように定義されるｍ×ｆの数δi,jを使用する。
−ｐjがｔ＜ｋであるとき、ｉが１からｍの場合、δi,j＝Δi,j、つまり、ｈi,j＝０の場合、＋１、ｈi,j＝１の場合、−１である。
−ｐjがｔ≧ｋであるとき、ｉが１からｍの場合、δi,j＝０であり、つまりΔi,jからΔm,jは、該第２の原則に従って選択されてよい。
【０１５７】
第１の手順は、少なくとも１つの集合｛δi,1．．．δi,f｝が可変又はゼロである、つまり少なくとも１つの数ｑiからｑmがトリビアルではない、又はノントリビアルとして選ばれてよいことを確認する。
【０１５８】
−１からｍのｉ及び１からｆのｊの場合、
−δi,1＝０又は≠δi,jの場合、「成功」を返す。
−「失敗」を返す。
【０１５９】
第２の手順は、各集合｛δi,1．．．δi,f｝が可変又はゼロである、つまり各数ｑlからｑmがトリビアルではない、又はノントリビアルとして選択されてよいことを確認する。
−１からｍのｉの場合、
−１からｆのｊの場合、
−δi,j＝０又は≠δi,lの場合、ｉの次の値まで省略する、
−「失敗」を返す。
−「成功」を返す。
【０１６０】
第３の手順は、１≦ｊ1≦ｊ2≦ｆである素因数ｐj1とｐj2の各組において、δl,j1がゼロである、又はδi,j2とは異なる、少なくとも１つの集合｛δi,1．．．δi,f｝があることを確認する。それはｍがｆ−１より小さいときには明らかに失敗する。それが成功するとき、ｍ個の数ｑlからｑmの中に、該ｆ個の素因数に関して独立したｆ−１個の数の少なくとも１つの集合がある。
−１からｆ−１のｊ1の場合、及びｊ1+1からｆのｊ2の場合
−１からｍのｉの場合、
−δl,j1＝０又は≠δi,j2の場合、ｊ1及びｊ2の次の値まで省略する、
−「失敗」を返す。
−「成功」を返す。
【０１６１】
手順が失敗すると、ＧＱ２鍵集合の該生成元は以下の２つの考えられる戦略から選ばれるその戦略に従う。
−該ｆ個の素因数を保ちながら、該ｍ個のベース数の１つを変更する、
−該ｍ個のベース数を保ちながら、該ｆ個の素因数の１つを変更する。
【０１６２】
第３の原則−以下の手順は、生成中の又はすでに生成されたかのいずれかの一般化されたＧＱ２鍵の集合が、
−基本的なＧＱ２鍵の集合である、つまり２×ｍ個の数±ｇlから±ｇmがすべて非平方剰余であるものか、
−あるいはそれ以外の場合、補完的なＧＱ２鍵の集合である、つまり２×ｍ個の数±ｇlから±ｇmの中で、少なくとも１つの平方剰余がある
のどちらであるかを判断する。
【０１６３】
該手順は、１からｍのｉ及び１からｆのｊの場合、両方のルジャンドルの記号（ｇi｜ｐj）と（−ｇi｜ｐj）を使用する。
−１からｍのｉの場合
−１からｆのｊの場合
−（ｇi｜ｐj）＝−１の場合、ｉの次の値まで省略する。
−「補完的なＧＱ２鍵の集合」を返す。
−１からｆのｊの場合
−（ｇi｜ｐj）＝−１の場合、ｉの次の値まで省略する。
−「補完的なＧＱ２鍵の集合」を返す。
−「基本的なＧＱ２鍵の集合」を返す。
【０１６４】
秘密成分−直接タイプの方程式：ｘV≡ｇi2（ｍｏｄ  ｐj）の場合、以下の計算が該秘密成分Ｑi,jのすべての考えられる値を立証する。該２つの最も簡略且つ最新のケース、つまりｔ＝１及びｔ＝２の後には、より複雑なケース、つまりｔ＞２が続く。
ｔ＝１、つまりｐj≡３（ｍｏｄ  ４）の場合、該鍵＜（ｐj＋１）／４，ｐj＞はＣＧ（ｐj）の中の任意の平方剰余の二次平方根を提供する。このことから、以下の数が導出され、
ｓj≡（（ｐj＋１）／４）k（ｍｏｄ  （ｐj−１）／２）、それはＧiをｗ≡Ｇisj（ｍｏｄ  ｐj）に変換する鍵＜ｓj，ｐj＞を与える。Ｑi,jはｗ又はｐj−ｗに等しい。
ｔ＝２、つまりｐj≡５（ｍｏｄ  ８）の場合、該鍵＜（ｐj＋３）／８，ｐj＞は、ＣＧ（ｐj）の中の奇数階数の任意の要素のための奇数階数の該平方根を提供する。このことから、以下の数が引き出され、ｓj≡（（ｐj＋３）／８）k（ｍｏｄ  （ｐj−１）／４）、それはＧiをｗ≡Ｇisj（ｍｏｄ  ｐj）に変換する鍵＜ｓj，ｐj＞を与える。２がＣＧ（ｐj）の非平方剰余であるため、ｚ≡２(pj-1)/4（ｍｏｄ  ｐj）が−１の平方根であることに留意しよう。Ｑijは、ｗ又はｐj−ｗに等しい、あるいはそれ以外の場合、（ｐjを法として）ｗ’≡ｗ×ｚ又はｐj−ｗtに等しい。
ｔ＞２でｐj≡２t＋１（ｍｏｄ  ２t+1）の場合、鍵＜（ｐj−１＋２t）／２t+1，ｐj＞は、奇数階数の任意の要素の奇数階数の該平方根を提供する。ｋ、ｇ、及びｐ間の適合性試験は、ｈの該値、つまりｕの次の値を示していた。
−Ｇiがサイクル内（ｋの該値に関係なくｕ＝０）にあるとき、以下の数
ｓj≡（（ｐj−１＋２t）／２t+1）k（ｍｏｄ  （ｐj−１）／２t）が立証される。鍵＜ｓj，ｐj＞がＧiを奇数階数ｗ≡Ｇisj（ｍｏｄ  ｐj）の解に変換する。例えば、α本の枝の中等の、該サイクルに関連付けられている最小（ｋ，ｔ）連続枝で分散される偶数階数の解がある。Ｑi,jは、ＣＧ（ｐj）の中の個体の２α番目のルートのいずれかによるｗの積に等しい。
−Ｇjが枝の中の適切な位置（ｕ＞０、ｕ＋ｋ≦ｔ）にあるとき、すべての解はＧjと同じ枝、つまり該数Ｇiの２u乗によりサイクルに関連付けられる枝にある。数は
ｓj≡（（ｐj−１＋２t）／２t+1）k+u（ｍｏｄ  （ｐj−１）／２t）
として確立される。
【０１６５】
鍵＜ｓj，ｐj＞は、Ｇiの２u乗を奇数階数ｗの数に変換する。ＣＧ（ｐj）内の個体の該プリミティブな２k+u乗のルートとのｗの積の集合は、Ｑi,jの２kの値を備える。
【０１６６】
ｐjがｔ≧ｋであるとき、数ｂjはＣＧ（ｐj）内の個体の該プリミティブな２t乗のルートであるので、ＣＧ（ｐj）内のｂjの該プリミティブな２t-u乗が存在する。これは個体のプリミティブな２k乗のルートである。数Δi,jの該値は、Ｑi,jを個体のプリミティブな２k乗のルートで乗算することにより切り替えられてよい。
【０１６７】
逆数タイプの方程式：１≡ｘV×ｇi2（ｍｏｄ  ｐj）の場合、ＣＧ（ｐj）の中のＱi,jの値を反転させることに相当する、該鍵＜ｓj，ｐj＞の中の（（ｐj−１）／２t）−ｓjで数ｓjを置換することで十分である。
【０１６８】
５（ｍｏｄ ８）と合同である２つの素因数のある鍵の集合の例
【数７３】
2008048451.tif 000075
【０１６９】
ここでは、本当に最初の素数のルジャンドル記号がある。
【数７４】
2008048451.tif 000076
【０１７０】
ＣＧ（ｐj）では、該階数は−５、−１１及び１７の場合、奇数である。
【数７５】
2008048451.tif 000077
【０１７１】
ＣＧ（ｐ2）では、該階数は３、−５、７及び１１の場合、奇数である。
【０１７２】
カーマイケルの関数は以下の通りである。
【数７６】
2008048451.tif 000078
【０１７３】
ｋ＝９では、該数σ≡λ（ｎ）−（（１＋λ（ｎ））／２）9（ｍｏｄ  λ（ｎ））は、該逆数タイプの該一般方程式を使用するために秘密指数として使用される。
【数７７】
2008048451.tif 000079
【０１７４】
数２、３、７、１３及び１７はベース数として適切ではない。
【０１７５】
鍵＜σ，ｎ＞はｇ1＝５を、因数分解を示さない秘密数Ｑ1に変換する。つまり、両方の域では、−５がサイクル上にある。
【数７８】
2008048451.tif 000080
【０１７６】
鍵＜σ，ｎ＞はｇ2＝１１を、因数分解を示す秘密数Ｑ2に変換する。つまり、１１は両方の域で同じ位置にない。
【数７９】
2008048451.tif 000081
【０１７７】
鍵＜σ，ｎ＞はｇ3＝２１＝３×７を、因数分解を示す秘密数Ｑ3に変換する。
【数８０】
2008048451.tif 000082
【０１７８】
鍵＜σ，ｎ＞はｇ4＝２６＝２×１３を、因数分解を示す秘密数Ｑ4に変換する。
【数８１】
2008048451.tif 000083
【０１７９】
該秘密鍵は、両方の素因数、該チャイニーズ剰余の該パラメータ及び８つの秘密成分によってさらに表されてよい。
【数８２】
2008048451.tif 000084
【０１８０】
該秘密鍵ＧＱ２の多様性−該秘密鍵ＧＱ２の考えられるさまざまな表示は同等であることが判明している。つまり、それらはすべて、実際のＧＫ２秘密鍵である、モジュールｎの因数分解を知っていることに相当する。ＧＱ２秘密鍵の該表示は、該管理側エンティティの中ではなく、該証明側エンティティの中の該計算の進行に影響を及ぼす。ここでは、該ＧＱ２秘密鍵について考えられる以下の３つの主要な表示がある。１）ＧＱ秘密鍵の従来の表示は、ｍ個の秘密数Ｑi及び該公開チェック鍵＜ｖ，ｎ＞を記憶することにあり、ＧＱ２方式の場合、この表示は以下の２つと競合している。２）作業負荷に関して最適の表示は、該パラメータｋ、該ｆ個の素因数ｐj、該ｍ×ｆ個の秘密成分Ｑi,j及び該チャイニーズ剰余の該ｆ−１個のパラメータを記憶することにある。３）秘密鍵サイズに関して最適の表示は、該パラメータｋ、該ｍ個のベース数ｇi及び該ｆ個の素因数ｐjを記憶すること、及び次にｍ個の秘密数Ｑiと該モジュールｎのいずれかを、それが該第１の表示に相当するように、あるいはｍ×ｆ個の秘密成分Ｑi,j及び該チャイニーズ剰余の該ｆ−１個のパラメータを、それが該第２の表示に相当するように立証することによって、各使用を開始することにある。
【０１８１】
該動的認証機構の、あるいは該デジタルシグナチャのセキュリティは該ＧＱ２方式で該モジュールの因数分解を知っていることに同等であるため、該同じモジュールを単に使用して２つのエンティティを区別することはできない。一般的には、各証明エンティティは独自のＧＱ２モジュールを有する。しかしながら、４つの素因数のあるＧＱ２モジュールが指定されてよく、その内の２つはエンティティに公知であり、他方の２つの別のエンティティは別のエンティティに公知である。
【０１８２】
動的認証−動的認証機構は、コントローラと呼ばれるエンティティに対して、考えられる関連メッセージＭの真正性だけではなく、証明者と呼ばれる別のエンティティの真正性を証明し、その結果該コントローラが、それが実際に該証明者と対応している旨、及び任意選択としてそれ自体及び該証明者が該同じメッセージＭについて話をしていることを確認するためである。該関連メッセージＭはオプションであり、それが空であってよいことを意味する。
【０１８３】
該動的認証機構は以下の４つの行為、つまり、関与行為、チャレンジ行為、応答行為、及びチェック行為のシーケンスである。該証明者は該関与行為と応答行為を行う。該コントローラは該チャレンジ行為とチェック行為を行う。
【０１８４】
該証明者の中で、該証明者の最も敏感なパラメータ及び関数、つまりコミットメント及び応答の生成を隔離するために、証人は隔離されてよい。該証人は該パラメータｋと該ＧＱ２秘密鍵、つまり前述された該３つの表示、つまり・該ｆ個の素因数と該ｍ個のベース数、・該ｍ×ｆ個の秘密成分、該ｆ個の素因数及び該チャイニーズ剰余の該ｆ−１個のパラメータ、・該ｍ個の秘密数及び該モジュールｎの内の１つによる、モジュールｎの因数分解を有する。
【０１８５】
該証人はある特定の実施形態、例えば、・該証明者をともに形成するＰＣに接続されているチップカード、又は・ＰＣ内で特に保護されているプログラムにも、あるいは・チップカード内で特に保護されているプログラムにも対応してよい。該それによって隔離された証人は、以後、該署名エンティティの中で定められる該証人に類似している。該機構の実行のたびに、該証人は１つ又は複数のコミットメントＲを、次に多くのチャレンジｄと同じくらい多くの応答Ｄを生成する。各集合｛Ｒ、ｄ、Ｄ｝がＧＱ２トリプレットを形成する。
【０１８６】
該証人を備えるそれに加えて、該証明者は、必要な場合、ハッシュ関数及びメッセージＭも有する。
【０１８７】
該コントローラは、該モジュールｎを例えば公開鍵のディレクトリから、あるいは公開鍵の証明書からも有する。必要な場合、それは同じハッシュ関数及びメッセージＭ’も有する。ＧＱ２公開パラメータ、つまり数ｋ、ｍ及びｇ1からｇmは、該証明者によって該コントローラに与えられてよい。該コントローラは任意のチャレンジｄから、及び任意の応答ＤからコミットメントＲ’を再構築することができる。パラメータｋとｍは該コントローラに知らせる。特に別に示されないならば、ｇ1からｇmの該ｍ個のベース数は第１のｍ個の素数である。各チャレンジｄは、ｄ1からｄmに参照されるｍ個の基本的なチャレンジを含まなければならない。つまりベース数あたり１個である。ｄ1からｄmの各基本的なチャレンジは数０から２k-1−１である（ｖ／２からｖ−１までの数は使用されない）。通常、各チャレンジはｍ×（ｋ−１）ビットでコーディングされる（ｍ×ｋビットではない）。例えば、ｋ＝５及びｍ＝４のベース数、５、１１、２１及び２６では、各チャレンジは４つのカルテットで送信される１６ビットを含む。該考えられる（ｋ−１）×ｍのチャレンジが等しくあり得るときには、該数（ｋ−１）×ｍは、各ＧＱ２トリプレットによってもたらされる該セキュリティを決定する。つまり、定義によって該モジュールｎの因数分解を知らない詐欺師（ｉｍｐｏｓｔｏｒ）は、正確には２(k-1)×mの内、１回の成功の確率を有している。（ｋ−１）×ｍが１５から２０であるとき、１つのトリプレットは動的認証を妥当に保証するために十分である。任意のレベルのセキュリティを達成するために、トリプレットは並列で生成されてよい。それらはシーケンスでも生成されてよい。つまり該機構の該実行を繰り返してよい。
【０１８８】
１）コミットメントの行為は以下の動作を備える。
該証人が該チャイニーズ剰余を使用しないとき、それは該パラメータｋ、Ｑ1からＱmの該ｍ個の秘密数、及びモジュールｎを有する。それは無作為に且つ非公開で１つ又は複数の乱数ｒ（０＜ｒ＜ｎ）を選び、次にそれらをｋ回、連続して二乗する（mod n）ことによって、それは各乱数ｒをコミットメントＲに変換する。
【数８３】
2008048451.tif 000085
【０１８９】
ここには、該チャイニーズ剰余を使用しない鍵の従前の集合の例がある。
【数８４】
2008048451.tif 000086
【０１９０】
該証人が該チャイニーズ剰余を使用するとき、それは該パラメータｋ、ｐlからｐfの該第１のｆ個の素因数、チャイニーズ剰余のｆ−１個のパラメータ、及びｍ×ｆ個の秘密成分Ｑi,jを有する。それは無作為に且つ非公開でｆ個の乱数の１つ又は複数の集合体を選ぶ。各集合体は素因数ｐiごとに１個の乱数ｒiを含む（０＜ｒi＜ｐi）。そして次にそれをｋ回連続して二乗する（ｍｏｄ  ｐi）ことによって、それは各乱数ｒiをコミットメント成分Ｒiに変換する。
【数８５】
2008048451.tif 000087
【０１９１】
ｆ個のコミットメント成分の各集合体の場合、該証人は該チャイニーズ剰余技法に従ってコミットメントを確立する。乱数集合体があるのと同じくらい多くのコミットメントがある。
【数８６】
2008048451.tif 000088
【０１９２】
ここに鍵の該従前の集合及び該チャイニーズ剰余のある例がある。
【数８７】
2008048451.tif 000089
【０１９３】
両方のケースでは、該証明者は該コントローラに対して、各コミットメントＲのすべて又は部分のいずれか、あるいはそれ以外の場合各コミットメントＲとメッセージＭをハッシュすることにより取得されるハッシュコードＨを送信する。
【０１９４】
２）チャレンジの行為は、それぞれがｍ個の基本的なチャレンジｄ1，ｄ2，．．．ｄmからなる１つ又は複数のチャレンジｄを無作為に選ぶことにある。各基本的なチャレンジｄ1は０からｖ／２−１の該数の１つである。
ｄ＝ｄ1，ｄ2，．．．ｄm
【０１９５】
ここに、両方の例、つまりｋ＝５及びｍ＝４のためのチャレンジがある。
【数８８】
2008048451.tif 000090
【０１９６】
該コントローラは各チャレンジｄを該証明者に送信する。
【０１９７】
３）応答の行為は以下の動作を含む。
【０１９８】
該証人がチャイニーズ剰余を使用しないとき、それは該パラメータｋ、Ｑ1からＱmの該ｍ個の秘密数、及び該モジュールｎを有する。それは、該コミットメント行為からの各乱数ｒ、及び該基本的なチャレンジによる該秘密数を使用することによって、１つ又は複数の応答Ｄを計算する。
【数８９】
2008048451.tif 000091
ここに、該チャイニーズ剰余を使用しない該例の続きがある。
【数９０】
2008048451.tif 000092
【０１９９】
該証人がチャイニーズ剰余を使用するとき、それは該パラメータｋ、ｐlからｐfのｆ個の素因数、該ｆ−１個のチャイニーズ剰余パラメータ及びｍ×ｆ個の秘密成分Ｑi,jを有する。それは、該コミットメント行為からの乱数の各集合体を使用することによって、ｆ個の応答成分の１つ又は複数の集合体を計算する。応答成分の各集合体は素因数あたり１つの成分を含む。
【数９１】
2008048451.tif 000093
【０２００】
応答成分の集合体ごとに、該証人は該チャイニーズ剰余技法に従って応答を確立する。チャレンジがあるのと同じくらい多くの応答がある。
【数９２】
2008048451.tif 000094
ここに該チャイニーズ剰余を使用しない該例の続きがある。
【数９３】
2008048451.tif 000095
【数９４】
2008048451.tif 000096
【０２０１】
両方のケースで、該証明者は各応答Ｄを該コントローラに送信する。
【０２０２】
４）チェックする行為は、各トリプレット｛Ｒ，ｄ，Ｄ｝が、ゼロ以外の値について以下のタイプの方程式を満たすことをチェックすること、
【数９５】
2008048451.tif 000097
又はそれ以外の場合
【数９６】
2008048451.tif 000098
あるいは、各コミットメントを復元することにある。それらのどれもゼロであってはならない。
【数９７】
2008048451.tif 000099
又はそれ以外の場合
【数９８】
2008048451.tif 000100
【０２０３】
任意選択として、該コントローラは次に、各復元されたコミットメントＲ’と該メッセージＭ’をハッシュすることによってハッシュコードＨ’を計算する。したがって該コントローラが、それが該コミットメント行為の最後に受信したもの、つまり各コミットメントＲのすべて又は部分、つまりハッシュコードＨを取り出すと、動的認証は成功である。
【０２０４】
例えば、基本的な動作のシーケンスは応答ＤをコミットメントＲ’に変換する。該シーケンスは、ベース数でのｋ−１回の除算又は乗算（mod n）によって分離されるｋ個の二乗（mod n）を備える。ｉ番目の二乗と該ｉ＋１番目の二乗の間に実行されるｉ番目の除算又は乗算の場合、該基本的なチャレンジｄ1のｉ番目のビットは、ｇiが使用されなければならないかどうかを示し、該基本的なチャレンジｄ2のｉ番目のビットはｇ2が使用されなければならないかどうかを、・・・ｇmが使用されなければならないかどうかを示す該基本的なｄmのｉ番目のビットまで示す。
【０２０５】
ここに、該チャイニーズ剰余を使用しない該最後の例がある。
【数９９】
2008048451.tif 000101
【０２０６】
ｎを法として二乗する。
【数１００】
2008048451.tif 000102
５×２６＝１３０、つまりｎを法として「８２」。
【数１０１】
2008048451.tif 000103
【０２０７】
ｎを法として二乗する。
【数１０２】
2008048451.tif 000104
２１で、つまりｎを法として「１５」で乗算する。
【数１０３】
2008048451.tif 000105
【０２０８】
ｎを法として二乗する。
【数１０４】
2008048451.tif 000106
【０２０９】
５×１１×２１＝１１５５、つまりｎを法として「４８３」。
【数１０５】
2008048451.tif 000107
【０２１０】
ｎを法として二乗する。
【数１０６】
2008048451.tif 000108
【０２１１】
５×１１×２６＝１４３０、つまりｎを法として「５９６」。
【数１０７】
2008048451.tif 000109
【０２１２】
ｎを法として二乗する。
【数１０８】
2008048451.tif 000110
【０２１３】
該コミットメントｒが取り出される。認証が成功する。
【０２１４】
ここに該チャイニーズ剰余を使用する最後の例がある。
【数１０９】
2008048451.tif 000111
【０２１５】
ｎを法として二乗する。
【数１１０】
2008048451.tif 000112
【０２１６】
５×２６＝１３０、つまりｎを法として「８２」。
【数１１１】
2008048451.tif 000113
【０２１７】
ｎを法として二乗する。
【数１１２】
2008048451.tif 000114
【０２１８】
２１で乗算する。つまりｎを法として「１５」。
【数１１３】
2008048451.tif 000115
【０２１９】
ｎを法として二乗する。
【数１１４】
2008048451.tif 000116
【０２２０】
５×１１×２１＝１１５５、つまりｎを法として「４８３」。
【数１１５】
2008048451.tif 000117
【０２２１】
ｎを法として二乗する。
【数１１６】
2008048451.tif 000118
【０２２２】
５×１１×２６＝１４３０、つまりｎを法として「５９６」。
【数１１７】
2008048451.tif 000119
【０２２３】
ｎを法として二乗する。
【数１１８】
2008048451.tif 000120
【０２２４】
該コミットメントｒは正しく取り出される。認証は成功する。
【０２２５】
デジタルシグナチャ
該デジタル署名機構により、署名エンティティと呼ばれるエンティティは署名済みメッセージを生成し、コントローラと呼ばれるエンティティは署名済みメッセージを確認できる。メッセージＭは任意の２進数列である。それは空であることができる。該メッセージＭは、該対応する応答だけではなく、１つ又は複数のコミットメント、及び／又はチャレンジも備えるシグナチャ付加物をそれに加えることによって署名される。
【０２２６】
該コントローラは、例えば、公開鍵のディレクトリから、又は公開鍵の証明書からも該モジュールｎを有する。また、それは該同じハッシュ関数も有する。該ＧＱ２公開パラメータ、つまり数ｋ、ｍ及びｇ1からｇmは、例えばそれらを該シグナチャ付加物に入れることによって該証明者によって該コントローラに与えられることができる。
【０２２７】
数ｋとｍは該コントローラに知らせる。一方、ｄ1からｄmの各基本的なチャレンジは数０から２k-1−１である（数ｖ／２からｖ−１は使用されない）。他方、各チャレンジｄは、ｄ1からｄmにおいて参照されるベース数ほど多くのｍ個の基本的なチャレンジを含まなければならない。さらに特に別に示されない限り、ｇ1からｇmの該ｍ個のベース数は該第１のｍ個の素数である。（ｋ−１）×ｍが１５から２０であると、並列に生成される４つのＧＱ２トリプレットで署名することが可能である。（ｋ−１）×ｍが６０以上の場合、１つのＧＱ２トリプレットだけで署名することが可能である。例えば、ｋ＝９及びｍ＝８では、ただ１つのＧＱ２トリプレットで十分である。各チャレンジは８バイトを含み、該ベース数は２、３、５、７、１１、１３、１７及び１９である。
【０２２８】
該署名動作は、３つの行為、つまりコミットメント行為、チャレンジ行為、及び応答行為のシーケンスである。各行為は、それぞれがコミットメントｒ（≠０）、ｄ1，ｄ2，．．．ｄmによって参照されるｍ個の基本的なチャレンジからなるチャレンジｄ、及び応答Ｄ（≠０）を備える、１つ又は複数のＧＱ２トリプレットを生成する。
【０２２９】
該署名エンティティはハッシュ関数、パラメータｋ、及びＧＱ２秘密鍵、つまり前述された該３つの表示の内の１つによる該モジュールｎの該因数分解を有する。該署名エンティティの中では、該証明者の最も敏感な関数及びパラメータを隔離するために該コミットメント行為と応答行為を実行する証人を隔離することが可能である。コミットメント及び応答を計算するために、該証人は該パラメータｋ及びＧＱ２秘密鍵、つまり前述された該３つの表示の内の１つによる該モジュールｎの該因数分解を有する。該それによって隔離された証人は該証明者の中で定められる該証人に類似している。それはある特定の実施形態に、例えば、・ともに該署名エンティティを形成するＰＣに接続されているチップカードに、又は・ＰＣ内で特に保護されているプログラムにも、又は・チップカード内で特に保護されているプログラムにも相当することができる。
【０２３０】
１）コミットメントの行為は以下の動作を備える。
該証人が該ｍ個の秘密数Ｑ1からＱm及び該モジュールｎを有するとき、それは無作為に且つ非公開で１つ又は複数の乱数ｒ（０＜ｒ＜ｎ）を選び、次にｋ回の連続二乗（mod n）によって、それは各乱数ｒをコミットメントＲに変換する。
【数１１９】
2008048451.tif 000121
【０２３１】
該証人がｐlからｐfのｆ個の素因数及びｍ×ｆ個の秘密成分Ｑl,jを有するとき、それは無作為に且つ非公開でｆ個の乱数の１つ又は複数の集合体を選ぶ。各集合体は素因数ｐiごとに１個の乱数ｒiを含む（０＜ｒi＜ｐl）。そして次にｋ回連続の二乗（ｍｏｄ  ｐi）によって、それは各乱数ｒiをコミットメント成分Ｒiに変換する。
【数１２０】
2008048451.tif 000122
【０２３２】
ｆ個のコミットメント成分の各集合体の場合、該証人は該チャイニーズ剰余技法に従ってコミットメントを確立する。乱数集合体があるのと同じくらい多くのコミットメントがある。
【数１２１】
2008048451.tif 000123
【０２３３】
２）チャレンジの行為は、該署名エンティティが、それぞれがｍ個の基本的なチャレンジを備える１つ又は複数のチャレンジを形成するハッシュコードを取得するために、すべてのコミットメントｒ及び署名されなければならない該メッセージｍをハッシュすることにある。各基本的なチャレンジは０からｖ／２−１の数である。例えば、ｋ＝９及びｍ＝８の場合、各チャレンジは８バイトを含む。コミットメントと同じくらい多くのチャレンジがある。ハッシュ（Ｍ，Ｒ）結果から抽出される、ｄ＝ｄ1，ｄ2，．．．ｄm
【０２３４】
３）応答の行為は以下の動作を含む。
該証人が該ｍ個の秘密数Ｑ1からＱm、及び該モジュールｎを有するとき、それは、該コミットメント行為の各乱数ｒ、及び該基本的なチャレンジによる該秘密数を使用することによって１つ又は複数の応答Ｄを計算する。
【数１２２】
2008048451.tif 000124
【０２３５】
該証人がｐlからｐfのｆ個の素因数及びｍ×ｆ個の素数成分Ｑi,jを有するとき、それは該コミットメント行為からの乱数の各集合体を使用することによって、ｆ個の応答成分の１つ又は複数の集合体を計算する。応答成分の各集合体は素因数あたり１つの成分を含む。
【数１２３】
2008048451.tif 000125
【０２３６】
応答成分の集合体ごとに、該証人は該チャイニーズチャイニーズ剰余技法による応答を確立する。チャレンジと同じくらい多くの応答がある。
【数１２４】
2008048451.tif 000126
該署名エンティティは、
−各ＧＱ２トリプレット、つまり各コミットメントＲ、各チャレンジｄ、及び各応答Ｄ、
−又は各コミットメントＲと各対応する応答Ｄ、
−各チャレンジｄ及び各対応する応答Ｄ
のいずれかを備える、シグナチャ付加物を追加することによって該メッセージＭに署名する。
【０２３７】
該検証動作の実行は、該シグナチャ付加物の該コンテンツに依存する。３つのケースが区別される。
【０２３８】
該付加物が１つ又は複数のトリプレットを備えるならば、該チェック動作は出来事が起こった順序が無関係である２つの独立したプロセスを含む。該コントローラは、両方の以下の条件が満たされるとき且つそのときに限り該署名済みメッセージを受け入れる。
【０２３９】
第１に、各トリプレットは一貫して（以下のタイプの適切な関係が検証されなければならない）、受け入れ可能でなければならない（該比較はゼロ以外の値で行われなければならない）。
【数１２５】
2008048451.tif 000127
あるいは別に
【数１２６】
2008048451.tif 000128
【０２４０】
例えば、該応答Ｄは、基本的な動作のシーケンス、つまりベース数でのｋ−１回の乗算動作（mod n）又は除算動作によって分離されるｋ個の二乗（mod n）によって変換される。ｉ番目の二乗とｉ＋１番目の二乗の間に実行されるｉ番目の乗算又は除算の場合、該基本的なチャレンジｄ1のｉ番目のビットはｇ1を使用することが必要かどうかを示し、該基本的なチャレンジｄ2のｉ番目のビットはｇ2を使用することが必要かどうかを、．．．ｇmを使用することが必要であることを示す、該基本的なチャレンジｄmのｉ番目のビットまで示す。したがって、該シグナチャ付加物に存在する各コミットメントＲを取り出すことが必要である。
【０２４１】
さらに、該１つ又は複数のトリプレットは該メッセージＭに結び付けられなければならない。すべての該コミットメントＲ及び該メッセージＭをハッシュすることによって、各チャレンジｄがその中から回復されなければならないハッシュコードが取得される。
ｄ＝ｄ1，ｄ2，．．．ｄm、該結果ハッシュ（Ｍ，Ｒ）から抽出されるものに同一。
【０２４２】
該付加物がチャレンジを有さない場合、該チェック動作はすべてのコミットメントＲ及び該メッセージＭをハッシュすることによって、１つ又は複数のチャレンジｄ’の該再構成を開始する。
ｄ＝ｄ’1，ｄ’2，．．．ｄ’m、該結果ハッシュ（Ｍ，Ｒ）から抽出される。
【０２４３】
次に、該コントローラは、各トリプレットが一貫して（以下のタイプの適切な関係が検証される）、受け入れ可能である（該比較はゼロ以外の値で行われる）とき、且つそのときに限り該署名済みメッセージを受け入れる。
【数１２７】
2008048451.tif 000129
あるいはそれ以外に
【数１２８】
2008048451.tif 000130
該付加物がコミットメントを備えない場合には、該チェック動作は以下の２つの式の内の１つ、すなわち適切な一方に従って１つ又は複数のコミットメントＲ’の該再構成を開始する。再確立されたコミットメントはゼロであってはならない。
【数１２９】
2008048451.tif 000131
あるいはそれ以外に
【数１３０】
2008048451.tif 000132
その結果、該コントローラは、各チャレンジｄを再構成するためにすべてのコミットメントＲ’及び該メッセージＭをハッシュしなければならない。
ｄ＝ｄ1，ｄ2，．．．ｄm、該結果ハッシュ（Ｍ，Ｒ’）から抽出されるものに同一。
【０２４４】
該コントローラは、各再構成されたチャレンジが該付加物の中の該対応するチャレンジに同一であるとき、且つそのときに限り該署名済みメッセージを受け入れる。
【図面の簡単な説明】
【０２４５】
【図１】図１Ａから図１Ｄは、それぞれ３（ｍｏｄ  ４）と合同、５（ｍｏｄ  ８）と合同、９（ｍｏｄ  １６）と合同、及び１７（ｍｏｄ  ３２）と合同であるＰのグラフ部分をそれぞれ描いている。
【図２】図２Ａは、ｕ＝０を課す、ｋ≧ｔ＝３、つまり９（ｍｏｄ  １６）と合同である素因数のこのケースを描いている。−Ｇが枝の適切な位置にあるとき、つまりｕ＞０及びｕ＋ｋ≦ｔのとき、すべて偶数階数の２kの解が枝の中にある。図２Ｂがこのケースを描いている。
【図３】図３Ａは、ｔ＜ｋのケースを描いている。図３Ｂは、ｔ≧ｋのときのケースを描いている。
【図１】
2008048451.tif 000206
【図２】
2008048451.tif 000207
【図３】
2008048451.tif 000208
【手続補正書】
【提出日】平成19年10月29日(2007.10.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
１個または複数の秘密値Ｑ1，Ｑ2，．．．，Ｑm及びそれぞれの公開値Ｇ1，Ｇ2，．．．，Ｇmの集合を取得するステップであって、鍵（Ｑi，Ｇi）の各組が方程式Ｇi・Ｑiv≡１（ｍｏｄ ｎ）または方程式Ｇi≡Ｑiv（ｍｏｄ ｎ）のどちらかを検証するものであり、ここで、ｍは１以上の整数であり、ｉは１とｍの間の整数であり、ｎはｐ1，．．．，ｐfによって指定されるｆ個の秘密素因数の積に等しい公開整数であり、これらの素因数の少なくとも２個が互いに異なり、ｆは１より大きい整数であり、ｖは、ｋを１より大きい整数値のセキュリティパラメータとしてｖ＝２kとなるような公開指数であり、各公開値Ｇi（ｉ＝１，．．．，ｍ）は、ｇi（ｉ＝１，．．．，ｍ）を、１より大きく該素因数ｐ1，．．．，ｐfのそれぞれより小さい整数を有する基本数であるとして、Ｇi≡ｇi2（ｍｏｄ ｎ）となるようなものであり、ｇlまたは−ｇlは、１とｍの間の少なくとも１個の整数値ｌに対してｎを法とした整数の環の平方剰余であり、ｉ＝１，．．．，ｍに対してＧi×Ｑiv＝１（ｍｏｄ ｎ）の場合にｑi≡Ｑi-v/2（ｍｏｄ ｎ）としＧi＝Ｑiv（ｍｏｄ ｎ）の場合にｑi≡Ｑiv/2（ｍｏｄ ｎ）として、１とｍの間の少なくとも１個の整数値ｓに対してｑsがｇs（ｍｏｄ ｎ）と合同でも−ｇs（ｍｏｄ ｎ）と合同でもない、取得ステップと、
認証方法においてまたは署名方法において、少なくとも前記秘密値Ｑ1，Ｑ2，．．．，Ｑmを使用するステップと
を含むコンピュータにより実現される方法。
【請求項２】
ｒを前記証明者によって無作為に選ばれる０＜ｒ＜ｎであるような整数として、Ｒ＝ｒv（ｍｏｄ ｎ）によって計算がなされて値が得られるコミットメントＲを証明者から受信するステップと、
ｍ個のチャレンジｄ1，ｄ2，．．．，ｄmを無作為に選択するステップと、
該チャレンジｄ1，ｄ2，．．．，ｄmを前記証明者に送信するステップと、
【数１】
2008048451.tif 000209
によって計算がなされて値が得られる応答Ｄを該証明者から受信するステップと、
【数２】
2008048451.tif 000210
を前記コミットメントＲと等しくするような値を該応答Ｄが有する場合に前記証明者を真正なものと判断し、ここで、ｉ＝１，．．．，ｍに対して、Ｇi×Ｑiv＝１（ｍｏｄ ｎ）の場合にεi＝＋１であり、Ｇi＝Ｑiv（ｍｏｄ ｎ）の場合にεi＝−１である、判断するステップと
をさらに含み、エンティティが認証されるようにする請求項１に記載の方法。
【請求項３】
コミットメントの集合Ｒjからチャイニーズ剰余法を使用して計算される値を有するコミットメントＲを証明者から受信し、ここで、ｊ＝１，．．．，ｆであり、各コミットメント成分ＲjはＲj＝ｒjv（ｍｏｄ  ｐj）であるように値を有し、ｒjは該証明者によって無作為に選ばれる０＜ｒj＜ｐjとなるように整数である、受信するステップと、
ｍ個のチャレンジｄ1，ｄ2，．．．，ｄmを無作為に選択するステップと、
該チャレンジｄ1，ｄ2，．．．，ｄmを前記証明者に送信するステップと、
チャイニーズ剰余法を使用して応答成分Ｄjの集合から計算される応答Ｄを該証明者から受信し、ここで、該応答成分Ｄjは、ｊ＝ｌ，．．．，ｆに対して、
【数３】
2008048451.tif 000211
となる値を有し、ここで、ｉ＝１，．．．，ｍ及びｊ＝ｌ，．．．，ｆに対してＱi,j＝Ｑi（ｍｏｄ  ｐj）である、受信するステップと、
【数４】
2008048451.tif 000212
が該コミットメントＲと等しくなるような値を前記応答Ｄが有する場合に、前記証明者を真正なものと判断し、ｉ＝１，．．．，ｍに対して、Ｇi×Ｑiv＝１（ｍｏｄ ｎ）の場合にはεi＝＋１であり、Ｇi＝Ｑiv（ｍｏｄ ｎ）の場合にはεi＝−１である、判断するステップと
をさらに含み、エンティティが認証されるようにする請求項１に記載の方法。
【請求項４】
Ｔ＝ｈ（Ｍ，Ｒ）を満たす値のトークンＴを証明者から受信するステップであって、ｈはハッシュ関数であり、Ｍは該証明者から受信されるメッセージであり、Ｒは、Ｒ＝ｒv（ｍｏｄ ｎ）によって計算がなされて値が得られるコミットメントであり、ｒは該証明者によって無作為に選ばれる０＜ｒ＜ｎの整数である、受信するステップと、
ｍ個のチャレンジｄ1，ｄ2，．．．，ｄmを無作為に選択するステップと、
該チャレンジｄ1，ｄ2，．．．，ｄmを前記証明者に送信するステップと、
【数５】
2008048451.tif 000213
によって値が得られる応答Ｄを該証明者から受信するステップと、
【数６】
2008048451.tif 000214
がトークンＴと等しくなるような値を該応答Ｄが有する場合に前記メッセージＭを真正なものと判断し、ｉ＝１，．．．，ｍに対して、Ｇi×Ｑiv＝１（ｍｏｄ ｎ）の場合にはεi＝＋１であり、Ｇi＝Ｑiv（ｍｏｄ ｎ）の場合にはεi＝−１である、判断するステップと
をさらに含み、メッセージの認証を可能にする請求項１に記載の方法。
【請求項５】
Ｔ＝ｈ（Ｍ，Ｒ）を満たす値のトークンＴを証明者から受信し、ここで、ｈはハッシュ関数であり、Ｍは前記証明者から受信されるメッセージであり、Ｒはコミットメント成分Ｒjの集合からチャイニーズ剰余法を使用して計算される値を有するコミットメントであり、ここでｊ＝１，．．．，ｆであり、各コミットメント成分ＲjがＲj＝ｒjv（ｍｏｄ  ｐj）となるように値を有し、ｒjは該証明者によって無作為に選ばれる０＜ｒj＜ｐjとなるように整数であるステップと、
ｍ個のチャレンジｄ1，ｄ2，．．．，ｄmを無作為に選択するステップと、
該チャレンジｄ1，ｄ2，．．．，ｄmを該証明者に送信するステップと、
チャイニーズ剰余法を使用して応答成分Ｄjの集合から計算される応答Ｄを該証明者から受信し、該応答成分Ｄjが、ｊ＝１，．．．，ｆに対して
【数７】
2008048451.tif 000215
となる値を有し、ここで、ｉ＝１，．．．，ｍ及びｊ＝１，．．．，ｆに対してＱi,j＝Ｑi（ｍｏｄ  ｐj）である、受信するステップと、
【数８】
2008048451.tif 000216
がトークンＴと等しくなるような値を前記応答Ｄが有する場合に該メッセージＭを真正なものと判断し、ここで、ｉ＝１，．．．，ｍに対して、Ｇi×Ｑiv＝１（ｍｏｄ ｎ）の場合にはεi＝＋１であり、Ｇi＝Ｑiv（ｍｏｄ ｎ）の場合にはεi＝−１である、判断するステップと
をさらに含み、メッセージの認証を可能にする請求項１に記載の方法。
【請求項６】
該チャレンジがｉ＝１，．．．，ｍに対して０≦ｄi≦２k−１となるようなものである請求項２に記載のコンピュータにより実現される方法。
【請求項７】
ｉ＝１，．．．，ｍに対して、０≦ｒi≦ｎであるｍ個の整数ｒiを無作為に選択するステップと、
ｉ＝１，．．．，ｍに対して、Ｒi＝ｒiv（ｍｏｄ ｎ）となる値をもつコミットメントＲjを計算するステップと、
Ｔ＝ｈ（Ｍ，Ｒ1，Ｒ2，．．．，Ｒm）となる値をもつトークンＴを計算し、ここで、Ｍは署名されるメッセージであり、ｈはｍ個のビットからなるバイナリ行列を生成するハッシュ関数である、計算するステップと、
該トークンＴの該ビットｄ1，ｄ2，．．．，ｄmを識別するステップと、
ｉ＝１，．．．，ｍに対して、応答、Ｄi＝ｒi×Ｑid1（ｍｏｄ ｎ）を計算するステップと
をさらに含み、署名者がメッセージに署名することを可能にする請求項１に記載のコンピュータにより実現される方法。
【請求項８】
ｉ＝１，．．．，ｍの場合、前記トークンＴ及び前記応答Ｄiを収集するステップと、
【数９】
2008048451.tif 000217
がトークンＴと等しくなるような値を該応答Ｄが有する場合に前記メッセージＭを真正なもと判断し、ここで、ｉ＝１，．．．，ｍに対して、Ｇi×Ｑiv＝１（ｍｏｄ ｎ）の場合にはεi＝＋１であり、Ｇi＝Ｑiv（ｍｏｄ ｎ）の場合にはεi＝−１である、判断ステップと、
をさらに含み、署名を検証することを可能にする請求項７に記載のコンピュータにより実現される方法。
【請求項９】
命令の集合を記憶するメモリと、
該メモリに記憶されている該命令の集合を実行するための、該メモリに結合されているプロセッサと
を含み、該命令が、
１個または複数の秘密値Ｑ1，Ｑ2，．．．，Ｑm及びそれぞれの公開値Ｇ1，Ｇ2，．．．，Ｇmの集合を取得するステップであって、鍵（Ｑi，Ｇi）の各組が方程式Ｇi・Ｑiv≡１（ｍｏｄ ｎ）または方程式Ｇi≡Ｑiv（ｍｏｄ ｎ）のどちらかを検証するものであり、ｍは１以上の整数であり、ｉは１とｍの間の整数であり、ｎはｐ1，．．．，ｐfによって指定されるｆ個の秘密素因数の積に等しい公開整数であり、これらの素因数の少なくとも２個が互いに異なり、ｆは１より大きい整数であり、ｖは、ｋを１より大きい整数値を有するセキュリティパラメータとしてｖ＝２kとなるような公開指数であり、各公開値Ｇi（ｉ＝１，．．．，ｍ）は、ｇi（ｉ＝１，．．．，ｍ）を１より大きく該素因数ｐ1，．．．，ｐfのそれぞれより小さい整数を有する基本数として、Ｇi≡ｇi2（ｍｏｄ ｎ）となるようなものであり、ｇlまたは−ｇlは、１とｍの間の少なくとも１個の整数値ｌに対してｎを法とした整数の環の平方剰余であり、ｉ＝１，．．．，ｍに対してＧi×Ｑiv＝１（ｍｏｄ ｎ）の場合にｑi≡Ｑi-v/2（ｍｏｄ ｎ）としＧi＝Ｑiv（ｍｏｄ ｎ）の場合にｑi≡Ｑiv/2（ｍｏｄ ｎ）として、１とｍの間の少なくとも１個の整数値ｓに対してｑsがｇs（ｍｏｄ ｎ）と合同でも−ｇs（ｍｏｄ ｎ）と合同でもない、取得するステップと、
認証方法においてまたは署名方法において、少なくとも前記秘密値Ｑ1，Ｑ2，．．．，Ｑmを使用するステップと
を含む命令である、システム。
【請求項１０】
実行時にプロセッサに、
１個または複数の秘密値Ｑ1，Ｑ2，．．．，Ｑm及びそれぞれの公開値Ｇ1，Ｇ2，．．．，Ｇmの集合を取得するステップであって、鍵（Ｑi，Ｇi）の各組が方程式Ｇi・Ｑiv≡１（ｍｏｄ ｎ）または方程式Ｇi≡Ｑiv（ｍｏｄ ｎ）のどちらかを検証し、この場合、ｍは１以上の整数であり、ｉは１とｍの間の整数であり、ｎはｐ1，．．．，ｐfによって指定されるｆ個の秘密素因数の積に等しい公開整数であり、これらの素因数の少なくとも２個が互いに異なり、ｆは１より大きい整数であり、ｖは、ｋを１より大きい整数値を有するセキュリティパラメータとしてｖ＝２kとなるような公開指数であり、各公開値Ｇi（ｉ＝１，．．．，ｍ）はＧi≡ｇi2（ｍｏｄ ｎ）となるようなものであり、ｇi（ｉ＝１，．．．，ｍ）は１より大きく該素因数ｐ1，．．．，ｐfのそれぞれより小さい整数を有する基本数であり、１とｍの間の少なくとも１個の整数値ｌに対して、ｇlまたは−ｇlはｎを法とした整数の環の平方剰余であり、ｉ＝１，．．．，ｍに対してＧi×Ｑiv＝１（ｍｏｄ ｎ）の場合にｑi≡Ｑi-v/2（ｍｏｄ ｎ）としＧi＝Ｑiv（ｍｏｄ ｎ）の場合にｑi≡Ｑiv/2（ｍｏｄ ｎ）として、１とｍの間の少なくとも１個の整数値ｓに対してｑsがｇs（ｍｏｄ ｎ）と合同でも−ｇs（ｍｏｄ ｎ）と合同でもない、取得するステップと、
認証方法においてまたは署名方法において少なくとも該秘密値Ｑ1，Ｑ2，．．．，Ｑmを使用するステップと
を実行させるための命令を記憶するコンピュータ可読記憶媒体。
【請求項１１】
非対称暗号鍵を生成するためのコンピュータにより実現される方法であって、前記鍵はｍ≧１個の秘密値Ｑ1，Ｑ2，．．．，Ｑm及びｍ個のそれぞれの公開値Ｇ1，Ｇ2，．．．，Ｇmを含んでおり、
ｋを１より大きい整数として、セキュリティパラメータｋを選択するステップと、
少なくとも２個の素因数ｐ1，．．．，ｐfの該積に等しい公開整数である係数ｎを決定するステップと、
ｍ個の基本数ｇ1，ｇ2，．．．，ｇmを選択し、（ｉ＝１，．．．，ｍの場合）各基本数ｇiが１より大きく該素因数ｐ1，．．．，ｐfのそれぞれより小さい整数値を有し、１とｍの間の少なくとも１個の整数値ｌに対して、ｇlまたは−ｇlはｎを法として整数の環の平方剰余であるステップと、Ｇi≡ｇi2（ｍｏｄ ｎ）によって、ｉ＝１，．．．，ｍに対して該公開値Ｇiを計算するステップと、
該方程式Ｇi・Ｑiv≡１（ｍｏｄ ｎ）または該方程式Ｇi≡Ｑiv（ｍｏｄ ｎ）のどちらかを解くことによってｉ＝１，．．．，ｍに対して該秘密値Ｑiを計算し、ここで、該公開指数ｖはｖ＝２kとなるものであり、その結果、ｉ＝１，．．．，ｍに対してＧi×Ｑiv＝１（ｍｏｄ ｎ）の場合にｑi≡Ｑi-v/2（ｍｏｄ ｎ）としＧi＝Ｑiv（ｍｏｄ ｎ）の場合にｑi≡Ｑiv/2（ｍｏｄ ｎ）として、１とｍの間の少なくとも１個の整数値ｓに対してｑsがｇs（ｍｏｄ ｎ）と合同でも−ｇs（ｍｏｄ ｎ）と合同でもない、計算するステップと
を含むコンピュータにより実現される方法。