| 【発明の名称】 |
エンティティの真正性又はメッセージの完全性を証明するための方法、システム、デバイス |
| 【発明者】 |
【氏名】ギユ，ルイ
【氏名】キスクワテル，ジャン‐ジャック
|
| 【要約】 |
【課題】エンティティの真正性、及び／又はメッセージの完全性、及び／又は真正性を証明するように設計された方法、システム及びデバイスに関し、セキュリティおよび性能の両面で、従来のＲＳＡ技術の欠点を回避する。
【構成】秘密のＱiと公開のＧi＝ｇi2によるｍ組の値（ｍ≧１）と、ｆ個（ｆ＞２）の素数の因子の積により形成される公開のモジュールｎと、ＧiＱiv≡１mod ｎまたはＧi≡Ｑivmod ｎの関係により関連付けされた、べきｖ＝２k（ｋ＞１）とによって証明を行なう。 |
【特許請求の範囲】
【請求項１】
あるコントローラ・エンティティに対して、
・ あるエンティティの真正性、および／または、
・ 該エンティティと関連するメッセージMの完全性
を証明するようにされている方法であって、以下のパラメータ、
・ 秘密の値Q1、Q2、... 、Qmと公開値G1、G2、...、 Gm（ｍは1以上）のm個の組と、
・ f個の素因数p1、p2、... pfの積で構成される公開のモジュラスn（fは2以上）、
の全部若しくは一部またはこれらのパラメータからの算出値を用いるものであり、
前記モジュラスと前記秘密値と公開値とには次のタイプの関係があり、
【数１】
ここで、ｖは
【数２】
のタイプの公開値である指数値を表し（ｋは１より大きいセキュリティパラメータ）、
前記ｍ個の公開値Giは、ｍ個の区別できるベース数g1、g2、…gmの、f個の素因数p1、p2、…pfより小さい二乗値ｇi2であり、
前記p1、p2、…pfの素因数、および／または、ｍ個のベース数g1、g2、…gmは以下の条件が満たされるように生成される方法。
［第１の条件］
各方程式
【数３】
がモジュロｎの整数環におけるｘについて解を持つこと。
［第２の条件］
Gi(Qiv mod nである場合、Qiを二乗してモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）、
Gi.Qiv (１mod nである場合、Qiのモジュロｎを二乗したもののインバースのモジュロnをk-1回とって得られるｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）。
［第３の条件］
２ｍ個の方程式
【数４】
の少なくともひとつがモジュロｎの整数環におけるｘについて解を持つ。
前記方法は、f個の素因数piを持っている証人と呼ばれているエンティティ、および／または、ベースgiのｍ個の素因数、および／または、前記素因数のチャイニーズ・剰余法のパラメータ、および／または、公開値であるモジュラスn、および／または、ｍ個の秘密値Qi、および／または、前記秘密値Qiと公開の指数値ｖとのf.m個の構成要素Qi,j（Qi,j ( Qi mod pj）を以下のステップによって実現するものである。
・ 前記証人が、モジュロnの整数環において、コミットメントRを計算し、
それぞれのコミットメントは、
【数５】
のタイプの演算（ここで、ｒは０＜ｒ＜ｎである乱数値）を実行するか、
あるいは、
【数６】
のタイプの演算（ここで、ｒiは０＜ri＜piである素因数piに関連した乱数値、それぞれのriは乱数値の集合｛r1,r2,…rf｝に含まれている）を実行し、さらに、チャイニーズ・剰余法手法を適用するか
のいずれかによって計算されるステップと、
・証人は一つ以上のチャレンジdを受け、それぞれのチャレンジｄはｍ個の整数di（以下「要素チャレンジ」と呼ぶ）からなり、各々のチャレンジdに基づいて、前記証人は
【数７】
のタイプの演算を行なうことによって応答Dを計算するか、
【数８】
のタイプの演算を行なって、さらに、チャイニーズ・剰余法手法を適用するステップ（前記手法はチャレンジｄ、コミットメント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´が
【数９】
のタイプか、または
【数１０】
のタイプの関係を満たすとともに、
前記コントローラは、それぞれの再構成されたコミットメントR´がコントローラに向けて伝達されたそれぞれのコミットメントRの全てまたは一部を再生成していることを確認し、
［前記デモンストレータがコミットメントRの全部を送信するとき］
前記デモンストレータがコミットメントRの全部を送信したなら、ｍ個の公開値G1、G2、...、Gmを有している前記コントローラは、それぞれのコミットメントRが
【数１１】
のタイプか、または
【数１２】
のタイプの関係を満たしていることを確認する。
【請求項３】
デモンストレータエンティティと呼ばれるエンティティに関連したメッセージ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´は
【数１３】
のタイプか、または
【数１４】
のタイプの関係を満たし、
・ そして前記コントローラは、前記メッセージ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が、
【数１５】
のタイプの関係を満たすことを確認するか、
【数１６】
のタイプの関係を満たすことを確認し、
前記コントローラは前記メッセージM、前記チャレンジｄ、前記コミットメントRが前記ハッシュ関数
【数１７】
を満たすことを確認し、
［前記コントローラはチャレンジｄと応答Dを有する場合］
前記コントローラはチャレンジｄと応答Dを有する場合、
前記コントローラは、それぞれのチャレンジｄと応答Dに基づいて、
【数１８】
のタイプの関係か、または、
【数１９】
のタイプの関係を満たすコミットメントR´を再構成し、
前記コントローラは前記メッセージMと前記チャレンジｄが前記ハッシュ関数
【数２０】
を満たすことを確認し、
［前記コントローラはコミットメントRと応答Dを有する場合］
前記コントローラはコミットメントRと応答Dを有する場合、
前記コントローラは前記ハッシュ関数を適用してｄ´を再構成し、
【数２１】
前記コンとローラは、前記コミットメントR、前記チャレンジｄ´、前記応答Dが
【数２２】
のタイプの関係か、または、
【数２３】
のタイプの関係を満たすことを確認する。
【請求項６】
コントローラ・サーバーに対して、
・ エンティティの真正性、および／または
・ 該エンティティと関連するメッセージMの完全性、
を証明するようにされたシステムであって、
・ 秘密の値Q1、Q2、... 、Qmと公開値G1、G2、...、Gm（ｍは1以上）のm個の組、
・ f個の素因数p1、p2、... pfの積で構成される公開値であるモジュラスn（ｆは2以上）、
の全てあるいは部分以下のパラメータやそれらパラメータからの算出値を用いており、
前記モジュラスと前記秘密値と公開値は以下のタイプの関係があり、
【数２４】
ここで、ｖは
【数２５】
の形式の公開の指数値 ｃを表し、ｋは１より大きいセキュリティパラメータであり、
前記ｍ個の公開の値Giは、ｆ個の素因数p1, p2,…, pfより小さいｍ個の区別できるベース数g1,g2,…,gmによるgi2となる２乗値であり、
前記素因数p1, p2,…,pfおよび／または前記ｍ個のベース数g1,g2,…,gmは、以下の条件が満たされるように生成されているシステム。
［第１の条件］
方程式
【数２６】
がｘについてモジュロｎの整数環において解をもつこと。
［第２の条件］
Gi(Qiv mod nである場合、Qiを二乗してモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）、
Gi.Qiv (１mod nである場合、Qiのモジュロｎを二乗したもののインバースのモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）。
［第３の条件］
少なくとも２ｍ個の方程式
【数２７】
がモジュロｎの整数環におけるｘについて解を持つ。
前記システムは、例えばマイクロプロセッサベースの銀行カードの形態をとるようなノマドオブジェクトを特に含まれる証人装置を含み、
その証人装置は、
・ 前記ｆ個の素数pi、および／または、前記ｍ個のベースgi、および／または、前記素因数のチャイニーズ剰余のパラメータ、および／または、公開値であるモジュラスｎ、および／または、m個の秘密の値Qi 、および／または、公開の指数値ｖと秘密の値Qiとによるf.m個の成分Qi,j（Qi,j ( Qi mod pj）を含むメモリゾーンを含み、
前記証人装置は、また、
・ 前記証人装置の乱数値生成手段とここで呼ぶ乱数値生成手段と、
・前記証人装置のコミットメントRの計算手段と呼ぶ計算手段であって、モジュロｎの整数環においてコミットメントRの計算を行い、各コミットメントRは、
・ｒを０＜ｒ＜ｎである前記乱数値生成手段による乱数値として、
【数２８】
のタイプの演算を行なうか、
・ｒiが、０＜ｒi＜ｐiで、それぞれ、前記乱数生成手段によって生成され、各ｒIはチャイニーズ剰余法を適用することによって得られるランダム値の集合[r1,r2,…,rf]に属する、素因数piに関連した乱数値であるとして、
【数２９】
のタイプの演算を行なうか、
によって計算されるものである計算手段と
を含み、
前記証人装置は、また、
・ 前記証人で装置のチャレンジｄを受け付け、それぞれのチャレンジｄがｍ個の整数di（以下、要素チャレンジとよぶ）からなる1以上のチャレンジｄを受け付け、前記証人デバイスのチャレンジｄ受け付け手段と呼ばれる受け付け手段と、
・ それぞれのチャレンジｄに基づいて、前記証人装置の応答Dを計算し、
・方程式
【数３０】
のタイプの演算を行なうこと、あるいは、
・方程式
【数３１】
のタイプの演算をおこなって、そして、チャイニーズ剰余法を適用すること、
のいずれかにより応答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´は
【数３２】
のタイプの関係か、
【数３３】
のタイプの関係を満たし、
［前記デモンストレータが各コミットメントRの全部を伝送した場合］
前記デモンストレータが各コミットメントRの全部を伝送した場合には、ｍ個の公開値G1、G2、...、Gmを有する前記コントローラ装置の前記計算手段と前記比較手段は、各チャレンジRが
【数３４】
のタイプの関係か、
【数３５】
のタイプの関係を満たすことを確認する。
【請求項８】
コントローラとして知られたあるエンティティに、デモンストレータとして知られたエンティティに関連したメッセージMについての完全性の証明を与えるようになっている請求項６に記載のシステムであって、
・ 前記デモンストレータエンティテイに関連し、前記相互接続装置によって前記証人装置に相互接続されて、例えばマイクロプロセッサベースの銀行カード中のマイクロプロセッサの形態のような、ノマドオブジェクトにおける微小論理回路の形態を特にとることができるデモンストレータ装置と、
・前記コントローラエンティティと関連するコントローラ装置であって、前記コントローラ装置は、特に端末であるか遠隔サーバーの形になっていて、前記コントローラ装置が、特にデータ処理通信ネットワークを通って、それ自身の電気的、電磁気的、光学的、あるいは音響によるデモンストレータ装置への接続のために、接続手段とを含んでいるコントローラ装置と
を備えており、以下のステップの実行を可能にしている前記システム
［ステップ1（コミットメントRの行為）］
各々の呼び出しで、請求項1によって指定されるプロセスを適用することによって証人装置のコミットメントRの計算手段が各コミットメントRを計算し、
該証人手段は、コミットメントRの全部または一部を前記デモンストレータ装置に送信する、前記証人装置の伝送装置と呼ばれる伝送装置を有し、
［ステップ２（チャレンジｄの行為）］
前記デモンストレータ装置は、少なくともあるトークンTの計算に、前記メッセージと各コミットメントRの全部または一部とを変数とするハッシュ関数ｈを適用する、前記デモンストレータの計算手段と呼ばれる計算手段からなり、
前記デモンストレータ装置は、また、各トークンTを前記コントローラ装置に前記接続手段を通じて送信する、前記デモンストレータ装置の伝送装置と呼ばれる伝送装置を有し、
前記コントローラ装置は、前記トークンTを受け取った後に、コミットメントRの数と同じ数の前記チャレンジｄを生成するチャレンジ生成手段を有し、
前記コントローラ装置は、また、前記接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を有し、
［ステップ３（応答Dの行為）］
前記証人装置の前記チャレンジｄの受け取り手段は、前記相互接続装置を通して前記デモンストレータ装置から来るそれぞれのチャレンジｄを受け取り、
前記証人装置の前記応答Dの前記計算手段は、請求項１に記載のプロセスを適用することにより、前記チャレンジｄから前記応答Dを計算し、
［ステップ４（チェックの行為）］
前記デモンストレータの前記伝送手段はそれぞれの応答Dを前記コントローラへ伝送し、
前記コントローラは、また、前記コントローラ装置の計算手段と呼ばれる計算計算手段を有し、この計算手段は、ｍ個の公開値G1、G2、...、Gmを有するとともに、第１に、各チャレンジｄと各応答Dから再構成されたコミットメントR´を計算し、この再構成されたコミットメントR´は
【数３６】
のタイプの関係か、
【数３７】
のタイプの関係を満たし、
第２に、前記メッセージ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が
【数３８】
のタイプか、
【数３９】
のタイプの関係を満たすことを確認し、
．．前記コントローラ装置の前記計算手段と前記比較手段は、前記メッセージM,前記チャレンジｄ、前記コミットメントRが前記ハッシュ関数
【数４０】
を満たすことを確認し、
［前記コントローラ装置がチャレンジｄ、応答Dを有する場合］
前記コントローラ装置がチャレンジｄ、応答Dを有する場合、
．．前記コントローラ装置の前記計算手段は、各チャレンジｄと各レスポンスDに基づいて、
【数４１】
のタイプか、
【数４２】
のタイプの関係を満たすコミットメントR´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージMと前記チャレンジｄがハッシュ関数
【数４３】
を満たすことを確認する。
［前記コントローラ装置がコミットメントR、応答Dを有する場合］
前記コントローラ装置がコミットメントR、応答Dを有する場合、
．．前記コントローラ装置の前記計算手段は、前記ハッシュ関数を適用して、
【数４４】
のようなｄ´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記コミットメントR、前記チャレンジｄ´、前記応答Dが
【数４５】
のタイプの関係を満たすか、
【数４６】
のタイプの関係を満たすことを確認する。
【請求項１１】
あるエンティティに関連した端末装置であって、例えばマイクロプロセッサベースの銀行カード中のマイクロプロセッサの形態のようなノマドオブジェクトにおける微小論理回路の形態を特にとることができ、コントローラ装置に対して
・ あるエンティティの前記真正性、および／または、
・ 該エンティティに関連したあるメッセージMの完全性、
を、以下のパラメータ、
秘密の値Q1、Q2、... 、Qmと公開値G1、G2、...、Gm（ｍは1以上）のm個の組と、
f個の素因数p1、p2、... pfの積で構成される公開のモジュラスn（fは2以上）、
や、これらのパラメータからの算出値の全部または一部を用いて証明するようにされていて、前記モジュラスと前記秘密値と公開値は
【数４７】
のタイプの関係があり、ここで、ｖは
【数４８】
の形態の公開値である指数値を表し（ｋは１より大きいセキュリティパラメータ）；
前記ｍ個の公開値Giは、ｍ個の異なったベース数g1、g2、…gmの、f個の素因数p1、p2、…pfより小さい二乗値ｇi2であり；
前記p1、p2、…pfの素因数、および／または、ｍ個のベース数g1、g2、…gmは以下の条件が満たされるように生成される端末装置。
［第１の条件］
各方程式
【数４９】
がモジュロｎの整数環におけるｘについて解を持つこと；
［第２の条件］
Gi(Qiv mod nである場合、Qiを二乗してモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）、
Gi.Qiv (１mod nである場合、Qiのモジュロｎを二乗したもののインバースのモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）；
［第３の条件］
２ｍ個の方程式
【数５０】
がモジュロｎの整数環におけるｘについて解をもち、
前記端末装置は、以下を備える証人装置を備え、
・ 前記ｆ個の素因数pi、および／または、ベースgiのｍ個の素因数、および／または、前記素因数のチャイニーズ・剰余法のパラメータ、および／または、公開モジュラスn、および／または、ｍ個の秘密値Qi、および／または、前記秘密値Qiと公開の指数値ｖとのf.m個の構成要素Qi,j（Qi,j ( Qi mod pj）を含むメモリゾーン；
・ 前記証人装置の乱数値生成手段と呼ぶ乱数値生成手段；
・ 前記証人装置のコミットメントRの計算手段と呼ぶ計算手段であって、モジュロｎの整数環においてコミットメントRの計算を行い、各コミットメントRは、
・ｒがｒが０＜ｒ＜ｎである前記乱数値生成手段による乱数値としたとき、
【数５１】
のタイプの演算を行なうか、
・ｒiが、０＜ｒi＜ｐiで、それぞれ、前記乱数生成手段によって生成されて、チャイニーズ剰余法を適用することによって得られるランダム値の集合[r1,r2,…,rf]に属する、素因数piに関連した乱数値であるとしたとき、
【数５２】
のタイプの演算を行なうか、
によって計算され、
前記証人装置は、また、
・ 前記証人で装置のチャレンジｄを受け付け、それぞれのチャレンジｄがｍ個の整数di（以下、要素チャレンジとよぶ）からなる1以上のチャレンジｄを受け付ける受け付け手段、
・ それぞれのチャレンジｄに基づいて、前記証人装置の応答Dを計算し、
・方程式
【数５３】
のタイプの演算を行なうこと、あるいは、
・方程式
【数５４】
のタイプの演算をおこなって、そして、チャイニーズ剰余法を適用すること、
のいずれかにより応答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以上）で、前記コントローラ装置と関連しているコントローラエンティティには知られていないもの、
の全部若しくは一部またはこれらのパラメータからの算出値を用い、
前記モジュラスと前記秘密値と公開値は、
【数５５】
のタイプの関係があり、ここで、ｖは
【数５６】
のタイプの公開値である指数値を表し（ｋは１より大きいセキュリティパラメータ、Qiは、前記コントローラ装置には知られていない、前記公開値Giに関連している秘密値）；
前記ｍ個の公開値Giは、ｍ個の区別できるベース数g1、g2、…gmの、f個の素因数p1、p2、…pfより小さい二乗値ｇi2であり；
前記p1、p2、…pfの素因数、および／または、ｍ個のベース数g1、g2、…gmは以下の条件が満たされるように生成される、
コントローラ装置。
［第１の条件］
各方程式
【数５７】
がモジュロｎの整数環におけるｘについて解を持つこと；
［第２の条件］
Gi(Qiv mod nである場合、Qiを二乗してモジュロnをk-1回とったｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）、
Gi.Qiv (１mod nである場合、Qiのモジュロｎを二乗したもののインバースのモジュロnをk-1回とって得られるｍ個の数qiのうち、これらのいずれかが±giではないこと（つまり、トリビアルではないこと）；、
［第３の条件］
２ｍ個の方程式
【数５８】
がモジュロｎの整数環におけるｘについて解を持つこと。
【請求項１６】
コントローラと呼ばれるあるエンティティに対して、デモンストレータと呼ばれるあるエンティティの真正性を証明するようにされている請求項１５に記載のコントローラ装置であって、
前記コントローラ装置は、特にデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響によって接続する、デモンストレータエンティティに関連したデモンストレータ装置への接続のための接続手段を含んでいて、
以下のステップを実行するのに用いられる前記コントローラ装置。
［ステップ１および２（コミットメントＲの行為、チャレンジｄの行為）］
前記コントローラ装置は、また、前記接続装置を通して前記デモンストレータ装置から来るコミットメントRの全部または一部を受け付ける手段を有し、
前記コントローラ装置は、前記コミットメントRの全部または一部を受け取った後に、それぞれの数がコミットメントRと同じであるチャレンジd（各チャレンジｄはｍ個の整数di（以下「要素チャレンジ」と呼ぶ）からなる）を生成する、チャレンジ生成手段を含み、
前記コントローラ装置は、また、前記接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を含み、
［ステップ３および４（応答Dの行為、チェックの行為）］
前記コントローラ装置は、また、
・ 前記接続手段を通じて前記デモンストレータ装置から来る前記応答Dを受け付ける手段
・ 前記コントローラ装置の計算手段と呼ばれる計算手段
・ 前記コントローラ装置の比較手段と呼ばれる比較手段
を備え、
［前記デモンストレータが各コミットメントRの一部を伝送した場合］
前記デモンストレータが各コミットメントRの一部を伝送した場合には、
ｍ個の公開値G1、G2、...、Gmを有する前記コントローラ装置の前記計算手段は、各チャレンジRと各応答Dから再構成されたコミットメントR´を計算し、その再構成されたコミットメントR´は
【数５９】
のタイプの関係か、
【数６０】
のタイプの関係を満たし、
前記コントローラ装置の前記比較手段は、各再構成されたコミットメントR´を受け付けられた各コミットメントRの全部または一部と比較する。
［前記デモンストレータが各コミットメントRの全部を伝送した場合］
前記デモンストレータが各コミットメントRの全部を伝送した場合には、
ｍ個の公開値G1、G2、...、Gmを有する前記コントローラ装置の前記計算手段と前記比較手段は、各チャレンジRが
【数６１】
のタイプの関係か、
【数６２】
のタイプの関係を満たすことを確認する。
【請求項１７】
デモンストレータと呼ばれるあるエンティティの完全性を証明するようにされている請求項１５に記載のコントローラ装置であって、
前記コントローラ装置は、特にデータ処理通信ネットワークを通って、それ自身、電気的、電磁気的、光学的、あるいは音響によって、デモンストレータエンティティに関連したデモンストレータ装置への接続のために、接続手段を含んでいて、
以下のステップを実行するのに用いられる前記コントローラ装置。
［ステップ１および２（コミットメントＲの行為、チャレンジｄの行為）］
前記コントローラ装置は、前記接続装置を通して前記デモンストレータ装置から来るトークンTを受け付ける手段を、また有し、
前記コントローラ装置は、前記トークンTを受け取った後に、それぞれの数がコミットメントRと同じであるチャレンジd（各チャレンジｄはｍ個の整数di（以下「要素チャレンジ」と呼ぶ）からなる）を生成する、チャレンジ生成手段を含み、
前記コントローラ装置は、また、前記接続手段を通じて前記デモンストレータへチャレンジｄを伝送する、前記コントローラの伝送手段と呼ぶ伝送手段を含み、
［ステップ３および４（応答Dの行為、チェックの行為）］
前記コントローラ装置は、また、
・ 前記接続手段を通じて前記デモンストレータ装置から来る前記応答Dを受け付ける手段
・ 前記コントローラ装置の計算手段と呼ばれる計算手段であって、この計算手段は、第１に、ｍ個の公開値G1、G2、...、Gmを有するとともに、各チャレンジｄと各応答Dから再構成されたコミットメントR´を計算し、そのコミットメントRは
【数６３】
のタイプの関係か、
【数６４】
のタイプの関係を満たし、
第２に、前記メッセージMおよび各再構成されたコミットメントR´の全てまたは一部を変数として有する前記ハッシュ関数ｈを適用することによりトークンT´を計算し、
・ トークンT´を受け付けられたトークンTと比較する前記コントローラ装置の比較手段と呼ばれる比較手段
を備える。
【請求項１８】
署名されたメッセージと呼ばれているエンティティによって署名されたメッセージをチェックすることによってメッセージMの真正性を証明するようにされている請求項１５に記載のコントローラ装置であって、
前記署名メッセージは、ハッシュ関数ｈ（message,R）を有するある署名エンティティに関連した署名装置によって送られるとともに、
・ 前記メッセージM、
・ 前記チャレンジｄおよび／またはコミットメントR、
・ 前記応答D、
からなり、
［チェック動作］
前記コントローラ装置は、前記署名エンティティに関連した前記署名装置への、特にデータ処理通信ネットワークを通る電気的、電磁気的、光学的、あるいは音響による接続のための接続手段を含んでいて、該コントローラ装置が、前記署名装置から前記接続を通じて前記署名メッセージを受け取り、
前記コントローラ装置は、
・ 前記コントローラ装置の計算手段と呼ばれる計算手段、
・ 前記コントローラ装置の比較手段と呼ばれる比較手段、
を備え、
［場合前記コントローラ装置がコミットメントR、チャレンジｄ、応答Dを有する場合］
場合前記コントローラ装置がコミットメントR,チャレンジｄ、応答Dを有する場合
．．前記コントローラ装置の前記計算手段および前記比較手段は、
前記コミットメントR、前記チャレンジｄ、前記応答Dが
【数６５】
のタイプか、
【数６６】
のタイプの関係を満たすことを確認し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージM,前記チャレンジｄ、前記コミットメントRが前記ハッシュ関数
【数６７】
を満たすことを確認する。
［前記コントローラ装置がチャレンジｄ、応答Dを有する場合］
前記コントローラ装置がチャレンジｄ、応答Dを有する場合、
．．前記コントローラ装置の前記計算手段は、各チャレンジｄと各レスポンスDに基づいて、
【数６８】
のタイプか、
【数６９】
のタイプの関係を満たすコミットメントR´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記メッセージMと前記チャレンジｄがハッシュ関数
【数７０】
を満たすことを確認する。
［前記コントローラ装置がコミットメントR、応答Dを有する場合］
前記コントローラ装置がコミットメントR、応答Dを有する場合、
．．前記コントローラ装置の前記計算手段は、前記ハッシュ関数を適用して、
【数７１】
のようなｄ´を計算し、
．．前記コントローラ装置の前記計算手段と前記比較手段は前記コミットメントR、前記チャレンジｄ´、前記応答Dが
【数７２】
のタイプの関係を満たすか、
【数７３】
のタイプの関係を満たすことを確認する。
|
【発明の詳細な説明】【技術分野】
【０００１】
本発明は、エンティティの真正性、及び／又はメッセージの完全性、及び／又は真正性を証明するように設計された方法、システム及びデバイスに関する。
【背景技術】
【０００２】
Ｌｏｕｉｓ Ｇｕｉｌｌｏｕ及びＪｅａｎ−Ｊａｃｑｕｅｓ Ｑｕｉｓｑｕａｔｅｒが発明者である欧州特許第０３１１４７０Ｂ１号は、このような方法を説明している。以後、「ＧＱ特許」又は「ＧＱ方法」との用語によって彼らの研究を参照するものとする。以後、表現「ＧＱ２」又は「ＧＱ２発明」又は「ＧＱ２技術」が本発明を説明するために使用されるものとする。
【０００３】
ＧＱ方法に従って、「信頼できる権威者」（trusted authority）として知られているエンティティが「証人」と呼ばれている各エンティティにアイデンティティを割り当て、それについてのＲＳＡシグナチャを計算する。カスタマイズするプロセスでは、信頼できる権威者は証人にアイデンティティとシグナチャを与える。その後、その証人は「ここにあるのは私のアイデンティティです。私はそのＲＳＡシグナチャを知っています」と宣言する。証人は、自分が自分のアイデンティティの該ＲＳＡシグナチャを知っている旨を、それを明らかにすることなく証明する。該信頼できる権威者により配布されるＲＳＡ公開識別鍵を通して、「コントローラ」として知られているエンティティは、その知識を取得することなく、当該ＲＳＡシグナチャが宣言されたアイデンティティに一致することを確認する。ＧＱ方法を使用するこの機構は「知識の移転なしに」動作する。このＧＱ方法に従って、証人はＲＳＡ秘密鍵を知ることなく、信頼できる権威者がその鍵を用いて多数のアイデンティティに署名する。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
前述のＧＱ技術はＲＳＡ技術を利用する。しかしながら、ＲＳＡ技術が係数ｎの因数分解に強く依存するのに対し、ＲＳＡ技術を実現するデジタルシグナチャの多様な規格と比較して「積攻撃（multiplicative attacks）」と呼ばれているものに見られるように、この依存は等価ではなく、実際にはそれからは程遠い。
【課題を解決するための手段】
【０００５】
ＧＱ２技術の目標は２つの要素からなる。つまり、一方では、ＲＳＡ技術の性能特性を改善することであり、他方ではＲＳＡ技術に固有の問題を回避することである。該ＧＱ２秘密鍵の知識は、該係数ｎの該因数分解の知識と同等である。トリプレットＧＱ２に対する攻撃は該係数ｎの因数分解につながる。この時点では等価なものがある。ＧＱ２技術を用いると、該署名する又は自己認証する（ｓｅｌｆ−ａｕｔｈｅｎｔｉｃａｔｉｎｇ）エンティティと該コントローラエンティティの両方にとって作業負荷が削減される。因数分解するという問題をセキュリティおよび性能の両方に関してさらにうまく使用することにより、ＧＱ２技術はＲＳＡ技術の欠点を回避する。
【０００６】
ＧＱ方法は５１２ビット以上を備える数のモジュロ計算を実現する。これらの計算は、ほぼ２16＋１乗にされた実質的に同じ大きさを有する数に関する。しかし、既存のマイクロエレクトロニクスインフラストラクチャは、特に銀行カードの分野では、演算コプロセッサを持たないモノリシック自己プログラム可能マイクロプロセッサを使用する。ＧＱ方法等の方法に関与する該複数の演算応用例に関する作業負荷によって計算時間が掛かり、そのため、特定のケースで銀行カードを使用する消費者が自分達の買い物を支払うために不利となることがわかっている。ここでは、支払いカードのセキュリティを強化しようとする際に、銀行当局（ｂａｎｋｉｎｇ ａｕｔｈｏｒｉｔｉｅｓ）はとりわけ解決するのが困難である問題を提起してきたことが思い起こされるかもしれない。事実上、２つの明らかに矛盾する問題、つまり該作業負荷がユーザにとって過剰な計算時間につながらないようにしつつ、その一方で、ますます冗長且つ区別できる鍵を各カードに使用することによってセキュリティを強化することが、研究されなければならない。既存のインフラストラクチャ及び既存のマイクロプロセッサ構成要素を考慮に入れることも必要であるため、この問題は特に深刻になる。
【０００７】
ＧＱ２技術は、依然としてセキュリティを強化しつつ、この問題に解決策を提供することを目的とする。
【０００８】
方法
さらに詳細には、本発明は、コントローラエンティティに対して
−エンティティの真正性、及び／又は
−このエンティティに関連付けられたメッセージＭの完全性
を証明するように設計された方法に関する。
この証明は、以下のパラメータ
−秘密値Ｑ1、Ｑ2、．．．Ｑmと公開値Ｇ1、Ｇ2，．．．Ｇmのｍ個の組（ｍは１以上）
−ｆ個の素因数ｐ1、ｐ2，．．．ｐfの積によって構成される公開係数ｎ（ｆは２以上）
又はこれらのパラメータの算出値のすべて又は一部によって立証される。
【０００９】
前記係数及び前記秘密値と公開値は以下のタイプの関係
【数１】
によって関連付けられ、この場合ｖは以下のタイプ
【数２】
の公開指数を表し、この場合ｋは１より大きなセキュリティパラメータであり、
前記ｍ個の公開値Ｇiは該ｆ個の素因数ｐ1，ｐ2，．．．ｐfに従うｍ個の区別できるベース数ｇ1ｇ2，．．．ｇmの二乗ｇi2であり、前記ｆ個の素因数ｐ1，ｐ2，．．．ｐf、及び／又は前記ｍ個のベース数ｇ1ｇ2，．．．ｇmは以下の条件が満たされるように生成される。
【００１０】
第１の条件：
第１の条件に従えば、該方程式
【数３】
のそれぞれは、ｎを法とした整数の環の中のｘについて解を有する。
【００１１】
第２の条件：
第２の条件に従えば、Ｇi≡Ｑiv mod ｎのケースでは、ｋ−１階数回、Ｑiを二乗すること（mod ｎ）によって得られる該ｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００１２】
第２の条件に従えば、Ｇi，Ｑiv≡１ mod ｎのケースでは、Ｑiの逆数(mod ｎ)をｋ−１階数回二乗する（mod ｎ）ことによって得られるｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００１３】
現在の表記に従えば、±ｇiが数ｇiとｎ−ｇiとを表していることがここで留意されるべきである。
【００１４】
第３の条件：
第３の条件に従えば、以下の２ｍ個の方程式
【数４】
の中で、それらの内の少なくとも１つはｎを法として整数の環の中のｘについて解を有する。
【００１５】
該方法はここに後述されるステップの中で証人と呼ばれているエンティティを実現する。前記証人エンティティは、ｆ個の素因数ｐi、及び／又はｍ個のベース数ｇi、及び／又は該素因数のチャイニーズ剰余のパラメータ、及び／又は該公開係数ｎ、及び／又は該ｍ個の秘密値Ｑi、及び／又は該秘密値Ｑiと該公開指数ｖの該ｆ．ｍ個の成分Ｑi,j（Ｑi,j≡Ｑi、mod ｐj）を有する。
【００１６】
該証人はｎを法として整数の該環の中のコミットメントＲを計算する。各コミットメントは、
−以下のタイプ
【数５】
の演算を実行し、この場合ｒが０＜ｒ＜ｎとなるように無作為の値となることと、
−又は
＊＊以下のタイプ
【数６】
の演算を実行し、この場合ｒiが０＜ｒi＜ｐiとなるように素因数ｐiと関連付けられた無作為な値であり、各ｒiは無作為な値の集合体｛ｒi，ｒ2，．．．ｒf｝に属することと、
のいずれかによって、
＊＊次に、該チャイニーズ剰余方法を適用することによって計算される。
【００１７】
該証人は１つ又は複数のチャレンジｄを受け取る。各チャレンジｄは、以下に基本的なチャレンジと呼ばれるｍ個の整数ｄiを備える。該証人は各チャレンジｄiに基づいて応答Ｄを、
−以下のタイプ
【数７】
の演算を実行することによって、
−又は
＊＊以下のタイプ
【数８】
の演算を実行することによって、
＊＊次に該チャイニーズ剰余法を適用することによって
のいずれかで計算する。
【００１８】
前記手法はチャレンジｄ、コミットメントRと同じくらいの数の応答Dがある。R,ｄ、Dの数の群は｛R、d、D｝で参照される３つの数字の組で表されるトリプレットを形成する。
【００１９】
エンティティの真正性の証拠のケース
実施形態の第１の変形において、本発明による該方法は、証明者として知られているエンティティの真正性を、該コントローラとして知られているエンティティに対して証明するように設計されている。前記証明者エンティティは該証人を備える。前記証明者エンティティとコントローラエンティティは以下のステップを実行する。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人は前記に指定された該プロセスを適用することにより、各コミットメントＲを計算する。該証明者は該コントローラに各コミットメントＲのすべて又は部分を送信する。
・ステップ２：チャレンジｄの行為
該コントローラは、各コミットメントＲのすべて又は部分を受信した後に、コミットメントＲの数に数が等しいチャレンジｄを生成し、該チャレンジｄを該証明者に送信する。
・ステップ３：応答Ｄの行為
該証人は該チャレンジｄからの該応答Ｄを、前記に指定された該プロセスを適用することにより計算する。
・ステップ４：チェックの行為
該証明者は各応答Ｄを該コントローラに送信する。
【００２０】
第１のケース：該証明者が各コミットメントＲの一部を送信した。
該証明者が各コミットメントＲの一部を送信した場合、該ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラは、各チャレンジｄ及び各応答Ｄから再構築されたコミットメントＲ’を計算し、この再構築されたコミットメントＲ’は以下のタイプ
【数９】
の関係又は以下のタイプ
【数１０】
の関係を満たす。
【００２１】
該コントローラは、各再構築されたコミットメントＲ’が、それに送信された各コミットメントＲのすべて又は部分を再現することを確認する。
【００２２】
第２のケース：該証明者は各コミットメントＲの全体性を送信した。
該証明者が各コミットメントＲの全体性を送信した場合、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラは、各コミットメントＲが以下のタイプ
【数１１】
の関係又は以下のタイプ
【数１２】
の関係を満たすことを確認する。
【００２３】
メッセージの完全性の証明のケース
第１の変形と結合できる実施形態の第２の変形では、本発明による該方法は該コントローラエンティティとして知られているエンティティに対して、証明者エンティティと呼ばれているエンティティと関連付けられたメッセージＭの完全性の証拠を提供するように設計されている。前記証明者エンティティは該証人を備える。
【００２４】
前記証明者エンティティとコントローラエンティティは以下のステップを実行する。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人は前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。
・ステップ２：チャレンジｄの行為
該証明者は、少なくとも１つのトークンＴを計算するために、その引数が該メッセージＭ及び各コミットメントＲのすべて又は部分であるハッシュ関数ｈを適用する。該証明者は、該トークンＴを該コントローラに送信する。該コントローラは、トークンＴを受信後、コミットメントＲの数に数が等しいチャレンジｄを生成し、該チャレンジｄを該証明者に送信する。
・ステップ３：応答Ｄの行為
該証人は、前記に指定された該プロセスを適用することによって、該チャレンジｄから該応答Ｄを計算する。
・ステップ４：チェックの行為
該証人は該コントローラに各応答Ｄを送信する。該ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラは、各チャレンジｄ及び各応答Ｄから再構築されたコミットメントＲ’を計算し、この再構築されたコミットメントＲ’は以下のタイプ
【数１３】
の関係又は以下のタイプ
【数１４】
の関係を満たす。
【００２５】
次に、該コントローラは、該トークンＴ’を再構築するために、その引数が該メッセージＭ及び各再構築されたコミットメントＲ’のすべて又は部分である、該ハッシュ関数ｈを適用する。それから、該コントローラは、該トークンＴ’が送信された該トークンＴと同一であることを確認する。
【００２６】
メッセージのデジタルシグナチャ及びその真正性の証拠
該２つの前記実施形態と結合できる該本発明による実施形態の第３の変形では、本発明による該方法は、該署名エンティティとして知られているエンティティによってメッセージＭの該デジタルシグナチャを生成するように設計されている。前記署名エンティティは該証人を含む。
【００２７】
署名動作
前記署名エンティティは、
−該メッセージＭと、
−該チャレンジｄ、及び／又は該コミットメントＲと、
−該応答Ｄと、
を備える署名済みメッセージを取得するために署名動作を実行する。
【００２８】
前記署名エンティティは、以下のステップを実現することにより該署名動作を実行する。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人は前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。
・ステップ２：チャレンジｄの行為
該署名エンティティは、バイナリ行列を取得するために、その引数が該メッセージＭ及び各コミットメントＲであるハッシュ関数ｈを適用する。該署名エンティティは、このバイナリ行列からコミットメントＲの数に等しい数のチャレンジｄを抽出する。
・ステップ３：応答Ｄの行為
該証人は前記に指定されたプロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。
【００２９】
チェック動作
該メッセージＭの真正性を証明するために、コントローラと呼ばれているエンティティは該署名済みメッセージをチェックする。該署名済みメッセージを有する前記コントローラエンティティは以下のように進めることによってチェック動作を実行する。
【００３０】
・該コントローラがコミットメントＲ、チャレンジｄ、応答Ｄを有するケース
該コントローラがコミットメントＲ、チャレンジｄ、応答Ｄを有する場合、該コントローラは、該コミットメントＲ、該チャレンジｄ、及び該応答Ｄが、以下のタイプ
【数１５】
の関係又は以下のタイプ
【数１６】
の関係を満たすことを確認する。
その結果、該コントローラは、該メッセージＭ、該チャレンジｄ及び該コミットメントＲが該ハッシュ関数
【数１７】
を満たすことを確認する。
【００３１】
・該コントローラがチャレンジｄと応答Ｄを有するケース
該コントローラがチャレンジｄと応答Ｄを有する場合、該コントローラは、各チャレンジｄと各応答Ｄに基づいて、以下のタイプ
【数１８】
の関係又は以下のタイプ
【数１９】
の関係を満たすコミットメントＲ’を再構築する。
その結果、該コントローラは、該メッセージＭ及び該チャレンジｄが該ハッシュ関数
【数２０】
を満たすことを確認する。
【００３２】
・該コントローラがコミットメントＲ及び応答Ｄを有するケース
該コントローラがコミットメントＲ及び応答Ｄを有する場合、該コントローラは該ハッシュ関数を適用し、ｄ’
【数２１】
を再構築する。
その結果、該コントローラは、該コミットメントＲ、該チャレンジｄ’及び及び該応答Ｄが以下のタイプ
【数２２】
の関係又は以下のタイプ
【数２３】
の関係を満たすことを確認する。
【００３３】
システム
本発明は、該コントローラサーバに対して以下
−エンティティの真正性、及び／又は
−このエンティティと関連付けられたメッセージＭの完全性
を証明するように設計されているシステムにも関する。
【００３４】
この証明は、以下のパラメータ
−秘密値Ｑ1、Ｑ2、．．．Ｑmと公開値Ｇ1、Ｇ2，．．．Ｇmのｍ個の組（ｍは１以上）
−ｆ個の素因数ｐ1、ｐ2，．．．ｐfの積によって構成される公開係数ｎ（ｆは２以上）
又はこれらのパラメータの算出値のすべて又は一部によって立証される。
【００３５】
前記係数及び前記秘密値と公開値は以下のタイプの関係
【数２４】
によって結び付けられ、この場合ｖは以下のタイプ
ｖ＝２k
の公開指数を示し、この場合ｋは１より大きなセキュリティパラメータであり、
前記ｍ個の公開値Ｇiは該ｆ個の素因数ｐ1，ｐ2，．．．ｐfに従うｍ個の区別できるベース数ｇ1ｇ2，．．．ｇmの二乗ｇi2であり、前記ｆ個の素因数ｐ1，ｐ2，．．．ｐf、及び／又は前記ｍ個のベース数ｇ1ｇ2，．．．ｇmは以下の条件が満たされるように生成される。
【００３６】
第１の条件：
第１の条件に従えば、該方程式
【数２５】
のそれぞれは、ｎを法とした整数の環の中のｘについて解くことができる。
【００３７】
第２の条件：
第２の条件に従えば、Ｇi≡Ｑiv（mod n）のケースでは、ｋ−１階数回、Ｑiを二乗する（mod n）ことによって得られる該ｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００３８】
第２の条件に従えば、Ｇj，Ｑiv≡１（mod n）のケースでは、Ｑiの逆数（mod n）をｋ−１階数回二乗する（mod n）ことによって得られるｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００３９】
現在の表記に従えば、±ｇiが数ｇiとｎ−ｇiとを表していることがここで指摘されるべきである。
【００４０】
第３の条件：
第３の条件に従えば、以下の２ｍ個の方程式
【数２６】
の中で、それらの内の少なくとも１つはｎを法として整数の環の中のｘについて解くことができる。
【００４１】
前記システムは、例えばマイクロプロセッサをベースにした銀行カードの形等、特にノマドオブジェクトに含まれている証人デバイスを備える。該証人デバイスは、ｆ個の素因数ｐi、及び／又は該素因数のチャイニーズ剰余のパラメータ、及び／又は該公開係数ｎ、及び／又はｍ個の秘密値Ｑi、及び／又は該秘密値Ｑiと該公開指数ｖのｆ．ｍ個の成分Ｑi,j（Ｑi,j≡Ｑi、modｐj）とを含むメモリゾーンを備える。該証人デバイスは、
−以下に該証人デバイスの無作為値生成手段と呼ばれる無作為値生成手段と、
−以下に該証人デバイスのコミットメントＲの該計算のための手段と呼ばれる計算手段と、
をさらに備える。
【００４２】
該計算手段により、ｎを法として整数の環の中でコミットメントＲを計算することが可能になる。各コミットメントは
・以下のタイプ
【数２７】
の演算を実行し、この場合ｒは無作為因数生成手段によって生成される無作為な値であり、ｒは０＜ｒ＜ｎであることと、
・あるいは以下のタイプ
【数２８】
の演算を実行し、この場合ｒiは、０＜ｒi＜ｐiとなるように該素因数ｐiと関連付けられた無作為な値であり、各ｒiは該無作為因数生成手段によって、及び次に該チャイニーズ剰余方法を適用することによって生成される無作為な値の集合体｛ｒi，ｒ2，．．．ｒf｝に属することとの、いずれかによって計算される。
【００４３】
また該証人デバイスは、
−以下に１つ又は複数のチャレンジｄを受信するための、該証人デバイスの該チャレンジｄの受信のための手段と呼ばれている受信手段であって、各チャレンジｄが以下に基本的なチャレンジと呼ばれるｍ個の整数ｄiを備える受信手段と、
−以下に、
・以下のタイプ
【数２９】
の演算を実施することによって、
・又は以下のタイプ
【数３０】
の演算を実施することのいずれかによって
及び次に該チャイニーズ剰余法を適用することによって、
各チャレンジｄに基づいた応答Ｄの計算のための、該証人デバイスの該応答Ｄの該計算のための手段と呼ばれる計算手段と、
をさらに備える。
【００４４】
該証人デバイスは、１つ又は複数のコミットメントＲ及び１つ又は複数の応答Ｄを送信するための伝送手段も備える。前記手法はチャレンジｄ、コミットメントRと同じくらいの数の応答Dがあって、R,ｄ、Dの数の群は｛R、d、D｝で参照される３つの数字の組で表されるトリプレットを形成する。
【００４５】
エンティティの真正性の証明のケース
実施形態の第１の変形では、本発明による該システムは、コントローラと呼ばれているエンティティに対して証明者と呼ばれているエンティティの真正性を証明するように設計されている。
【００４６】
前記システムは、証明者エンティティと関連付けられる証明者デバイスを備える。前記証明者デバイスは、相互接続手段によって該証人デバイスと相互接続されている。それは特に、マイクロプロセッサをベースにした銀行カードにおけるマイクロプロセッサの形式等のノマドオブジェクト内の論理マイクロ回路の形を取ることができる。
【００４７】
前記システムは該コントローラエンティティと関連付けられるコントローラデバイスも備える。前記コントローラデバイスは特に端末又はリモートサーバの形を取る。前記コントローラデバイスは、特にコンピュータ通信ネットワークを通して、該証明者デバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段を備える。
【００４８】
前記システムは、以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の手段は、前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。該証人デバイスは、該相互接続手段を通して該証明者デバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証人デバイスの伝送の手段と呼ばれる該伝送の手段を備える。また該証明者デバイスは、該接続手段を通して該コントローラデバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証明者の伝送手段と呼ばれている該伝送手段も備える。
・ステップ２：チャレンジｄの行為
該コントローラデバイスは、各コミットメントＲのすべて又は一部を受信した後に、コミットメントＲの数に数が等しい該チャレンジｄの該生成のためのチャレンジ生成手段を備える。該コントローラデバイスは、該接続手段を通して該証明者に該チャレンジｄを送信するために、以下に該コントローラの該伝送手段と呼ばれている伝送手段も備える。
・ステップ３：応答Ｄの行為
該証人デバイスの該チャレンジｄの受信の手段は、該相互接続手段を通して該証明者デバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄの計算の手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。
・ステップ４：チェックの行為
該証明者の該伝送手段は、該コントローラに各応答Ｄを送信する。また該コントローラデバイスは、
−以下に該コントローラデバイスの計算手段と呼ばれる該計算手段と、
−以下に該コントローラデバイスの比較手段と呼ばれる該比較手段と、
も備える。
【００４９】
第１のケース：該証明者が各コミットメントＲの部分を送信した。
該証明者の該伝送手段が各コミットメントＲの部分を送信した場合、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの該計算手段は、各チャレンジｄ及び各応答Ｄから再構築されたコミットメントＲ’を計算し、この再構築されたコミットメントＲ’は以下のタイプ
【数３１】
の関係又は以下のタイプ
【数３２】
の関係を満たす。
【００５０】
該コントローラデバイスの該比較手段は、各再構築されたコミットメントＲ’を受信された各コミットメントＲのすべて又は部分と比較する。
【００５１】
第２のケース：該証明者が各コミットメントＲの全体性を送信した。
該証明者の該伝送手段が各コミットメントＲの全体性を送信した場合、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの該計算手段と該比較手段は、各コミットメントＲが以下のタイプ
【数３３】
の関係又は以下のタイプ
【数３４】
の関係を満たすことを確認する。
【００５２】
メッセージの完全性の証明のケース
第１の変形と結合できる第２の変形の実施形態では、本発明による該システムは、コントローラとして知られているエンティティに対して、証明者として知られているエンティティと関連付けられたメッセージＭの完全性の証拠を示すように設計されている。前記システムは、該証明者エンティティと関連付けられている証明者デバイスを備える。前記証明者デバイスは、相互接続手段によって該証人デバイスと相互接続されている。それは、例えばマイクロプロセッサをベースにした銀行カード内のマイクロプロセッサの形等、特にノマドオブジェクトの論理マイクロ回路の形を取ってよい。前記システムは該コントローラエンティティと関連付けられている該コントローラデバイスも備える。前記コントローラデバイスは特に端末又はリモートサーバの形を取る。前記コントローラデバイスは、特にデータ処理通信ネットワークを通して、該証明者デバイスへのその電気的、電磁的、光学的、又は音響的な接続のための接続手段を備える。
【００５３】
前記システムは以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の手段が、前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。該証人デバイスは、該相互接続手段を通して各コミットメントＲのすべて又は部分を該証明者デバイスに送信するために、以下に該証人デバイスの伝送手段と呼ばれる伝送の手段を有する。
ステップ２：チャレンジｄの行為
該証明者デバイスは、少なくとも１つのトークンＴを計算するために、その引数が該メッセージＭ及び各コミットメントＲのすべて又は部分であるハッシュ関数ｈを適用する、以下に該証明者の計算の手段と呼ばれる該計算手段を備える。該証明者デバイスは、該接続手段を通して該コントローラデバイスに各トークンＴを送信するために、以下に該証明者デバイスの該伝送手段として知られている伝送手段も備える。該コントローラデバイスは、該トークンＴを受信後、コミットメントＲの数と数が等しい該チャレンジｄの該生成のためのチャレンジ生成手段も有する。該コントローラデバイスは、該接続手段を通して該証明者に該チャレンジｄを送信するために、以下に該コントローラの該伝送手段と呼ばれる伝送手段も有する。
・ステップ３：応答Ｄの行為
該証人デバイスの該チャレンジｄの受信の手段は、該相互接続手段を通して該証明者デバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄの計算の手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。
・ステップ４：チェックの行為
該証明者の該伝送手段は、該コントローラに各応答Ｄを送信する。該コントローラデバイスは、第１に、各チャレンジｄ及び各応答Ｄから以下のタイプ
【数３５】
の関係又は以下のタイプ
【数３６】
の関係を満たす再構築されたコミットメントＲ’を計算するために、
第２に、引数として、該メッセージＭ及び各再構築されたコミットメントＲ’のすべて又は部分を有する該ハッシュ関数ｈを適用することによってトークンＴ’を計算するために、以下に、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの該計算手段と呼ばれる計算手段も備える。
【００５４】
該コントローラデバイスは、該計算されたトークンＴ’を該受信されたトークンＴと比較するために、以下に該コントローラデバイスの該比較手段として知られている比較手段も有する。
【００５５】
メッセージのデジタルシグナチャ及びその真正性の証明
該最初の２つの実施形態の一方、及び／又は他方と結合できる、本発明による実施形態の第３の変形では、本発明による該システムは署名エンティティと呼ばれるエンティティによって、以下に署名済みのメッセージとして知られているメッセージＭのデジタルシグナチャを証明するように設計されている。
【００５６】
該署名済みのメッセージは、
−該メッセージＭと、
−該チャレンジｄ、及び／又は該コミットメントＲと、
−該応答Ｄと、
を備える。
署名動作
【００５７】
前記システムは、該署名エンティティと関連付けられている署名デバイスを備える。前記署名デバイスは相互接続手段によって該証人デバイスと相互接続され、例えば、マイクロプロセッサをベースにした銀行カードの中のマイクロプロセッサの形等の、特にノマドオブジェクト内の論理マイクロ回路の形を取ってよい。
【００５８】
前記システムは、以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の手段は前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。該証人デバイスは、該相互接続手段を通して該署名デバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証人デバイスの該伝送手段と呼ばれている伝送の手段を備える。
・ステップ２：チャレンジｄの行為
該署名デバイスは、バイナリ行列を計算するために、及び数がコミットメントＲの数に等しいチャレンジｄをこのバイナリ行列から抽出するために、その引数が該メッセージＭ、及び各コミットメントＲのすべて又は一部であるハッシュ関数ｈを適用する、以下に該署名デバイスの該計算手段と呼ばれている計算手段を備える。
・ステップ３：応答Ｄの行為
該証人デバイスの該チャレンジｄの受信のための手段は、該相互接続手段を通して該署名デバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄを計算するための手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。該証人デバイスは、該相互接続手段を通して該署名デバイスに該応答Ｄを送信するために、以下に該証人デバイスの伝送の手段と呼ばれている伝送手段を備える。
【００５９】
チェック動作
該メッセージＭの真正性を証明するために、コントローラとして知られているエンティティは該署名済みメッセージをチェックする。
【００６０】
前記システムは、該コントローラエンティティと関連付けられているコントローラデバイスを備える。前記コントローラデバイスは、特に端末又はリモートサーバの形を取る。前記コントローラデバイスは、特にコンピュータ通信ネットワークを通して、該署名デバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段を備える。
【００６１】
該署名エンティティと関連付けられた前記署名デバイスは、該接続手段を通して該署名済みメッセージの、該コントローラデバイスに対する伝送のための、以下に該署名デバイスの該伝送手段として知られている伝送手段を備える。したがって、該コントローラデバイスは、
−該メッセージＭと、
−該チャレンジｄ、及び／又は該コミットメントＲと、
−該応答Ｄと、
を備える署名済みのメッセージを有する。
【００６２】
該コントローラデバイスは、
−以下に該コントローラデバイスの該計算手段と呼ばれる計算手段と、
−以下に該コントローラデバイスの該比較手段と呼ばれる比較手段と、
を備える。
・該コントローラデバイスがコミットメントＲ、チャレンジｄ、応答Ｄを有するケース
該コントローラデバイスがコミットメントＲ、チャレンジｄ、応答Ｄを有する場合、該コントローラデバイスの該計算手段と比較手段は、該コミットメントＲ、該チャレンジｄ、及び該応答Ｄが以下のタイプ
【数３７】
の関係又は以下のタイプ
【数３８】
の関係を満たすことを確認する。
【００６３】
次に、該コントローラデバイスの該計算手段と比較手段は、該メッセージＭ、該チャレンジｄ及び該コミットメントＲが該ハッシュ関数
【数３９】
を満たすことを確認する。
・該コントローラデバイスがチャレンジｄ及び応答Ｄを有するケース
該コントローラがチャレンジｄと応答Ｄとを有する場合、該コントローラの該計算手段は、各チャレンジｄと各応答Ｄに基づいて、以下のタイプ
【数４０】
の関係又は以下のタイプ
【数４１】
の関係を満たすコミットメントＲ’を再構築する。
【００６４】
次に、該コントローラデバイスの該計算手段と比較手段は、該メッセージＭ及び該チャレンジｄが該ハッシュ関数
【数４２】
を満たすことを確認する。
・該コントローラがコミットメントＲ及び応答Ｄを有するケース
該コントローラデバイスがコミットメントＲと、応答Ｄとを有する場合、該コントローラデバイスの該計算手段は該ハッシュ関数を適用し、
【数４３】
となるようにｄ’を計算する。
【００６５】
次に、該コントローラデバイスの該計算手段と比較手段は、該コミットメントＲ、該チャレンジｄ’、及び該応答Ｄが以下のタイプ
【数４４】
の関係又は以下のタイプ
【数４５】
の関係を満たすことを確認する。
【００６６】
端末装置
本発明は、エンティティに関連付けられる端末装置にも関する。該端末装置は、例えばマイクロプロセッサをベースにした銀行カードの中のマイクロプロセッサの形等、特にノマドオブジェクトの形を取る。該端末装置はコントローラデバイスに対して以下
−エンティティの真正性、及び／又は
−このエンティティと関連付けられているメッセージＭの完全性
を証明するように設計されている。
【００６７】
この証明は、以下のパラメータ
−秘密値Ｑ1、Ｑ2、．．．Ｑmと公開値Ｇ1、Ｇ2，．．．Ｇmのｍ個の組（ｍは１以上）
−ｆ個の素因数ｐ1、ｐ2，．．．ｐfの積によって構成される公開モジュールｎ（ｆは２以上）
又はこれらのパラメータの算出値のすべて又は一部によって立証される。
前記モジュール及び前記秘密値と公開値は以下のタイプの関係
【数４６】
によって関連付けられ、この場合ｖは以下のタイプ
【数４７】
の公開指数を示し、この場合ｋは１より大きなセキュリティパラメータである。
【００６８】
前記ｍ個の公開値Ｇiは該ｆ個の素因数ｐ1，ｐ2，．．．ｐfに従うｍ個の区別できるベース数ｇ1ｇ2，．．．ｇmの二乗ｇi2であり、前記ｆ個の素因数ｐ1，ｐ2，．．．ｐf、及び／又は前記ｍ個のベース数ｇ1ｇ2，．．．ｇmは以下の条件が満たされるように生成される。
【００６９】
第１の条件：
第１の条件に従えば、該方程式
【数４８】
のそれぞれは、ｎを法とした整数の環の中のｘについて解くことができる。
【００７０】
第２の条件：
第２の条件に従えば、Ｇi≡Ｑiv（mod n）のケースでは、ｋ−１階数回、Ｑiを二乗する（mod n）ことによって得られる該ｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
第２の条件に従えば、Ｇi，Ｑiv≡１（mod n）のケースでは、Ｑiの逆数（mod n）をｋ−１階数回二乗する（mod n）ことによって得られるｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
現在の表記に従えば、±ｇiが数ｇiとｎ−ｇiとを表していることが、ここで指摘されるべきである。
【００７１】
第３の条件：
第３の条件に従えば、以下の２ｍ個の方程式
【数４９】
の中で、それらの内の少なくとも１つはｎを法として整数の環の中のｘについて解くことができる。
【００７２】
前記端末装置は、該ｆ個の素因数ｐi、及び／又は該素因数のチャイニーズ剰余のパラメータ、及び／又は該公開係数ｎ、及び／又はｍ個の秘密値Ｑi、及び／又は該秘密値Ｑiと該公開指数ｖのｆ．ｍ個の成分Ｑi,j（Ｑi,j≡Ｑj、modｐj）とを含むメモリゾーンを備える証人デバイスを備える。
【００７３】
該証人デバイスは、
−以下に該証人デバイスの無作為値生成手段と呼ばれる無作為値生成手段と、
−以下に、ｎを法として該整数の環の中の該証人デバイスのコミットメントＲの該計算のための手段と呼ばれる計算手段と、
も備える。
【００７４】
各コミットメントは
・以下のタイプ
【数５０】
の演算を実行し、この場合ｒは無作為値生成手段によって生成される無作為値であり、ｒは０＜ｒ＜ｎであることと、
・あるいは以下のタイプ
【数５１】
の演算を実行し、この場合ｒiは、０＜ｒi＜ｐiとなるように該素数ｐiと関連付けられた無作為値であり、各ｒiは該無作為値生成手段によって、次に該チャイニーズ剰余方法を適用することによって生成される無作為値の集合体｛ｒ1，ｒ2，．．．ｒf｝に属することと、のいずれかによって計算される。
【００７５】
また該証人デバイスは、
−以下に１つ又は複数のチャレンジｄを受信するために該証人デバイスの該チャレンジｄの受信のための手段と呼ばれている受信手段であって、各チャレンジｄが以下に基本的なチャレンジと呼ばれるｍ個の整数ｄ1を備える受信手段と、
−以下に、
・以下のタイプ
【数５２】
の演算を実行することによって、
・又は以下のタイプ
【数５３】
の演算を実行することのいずれかによって
及び次に該チャイニーズ剰余法を適用することによって、
各チャレンジｄに基づいた応答Ｄの計算のための、該証人デバイスの該応答Ｄの該計算のための手段と呼ばれる計算手段と、
をさらに備える。
【００７６】
該証人デバイスは、１つ又は複数のコミットメントＲ及び１つ又は複数の応答Ｄを送信するための伝送手段も備える。チャレンジｄ、コミットメントRと同じくらいの数の応答Dがあって、R,ｄ、Dの数の群は｛R、d、D｝で参照されるトリプレットを形成する。
【００７７】
エンティティの真正性の証明のケース
第１の実施形態の変形では、本発明による該端末装置は、コントローラと呼ばれているエンティティに対して証明者と呼ばれているエンティティの真正性を証明するように設計されている。
【００７８】
前記端末装置は、証明者エンティティと関連付けられる証明者デバイスを備える。前記証明者デバイスは、相互接続手段によって該証人デバイスと相互接続されている。それは特に、マイクロプロセッサをベースにした銀行カードにおけるマイクロプロセッサの形式等の、ノマドオブジェクト内の論理マイクロ回路の形を取ってよい。
【００７９】
前記証明者デバイスは、特にデータ処理通信ネットワークを通して、該コントローラエンティティと関連付けられている該コントローラデバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段も備える。前記コントローラデバイスは特に端末又はリモートサーバの形を取る。
【００８０】
前記端末装置は、以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の手段は、前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。
該証人デバイスは、該相互接続手段を通して該証明者デバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証人デバイスの伝送の手段と呼ばれる該伝送の手段を有する。また該証明者デバイスは、該接続手段を通して該コントローラデバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証明者の伝送手段と呼ばれている該伝送手段も有する。
・ステップ２と３：チャレンジｄの行為、応答Ｄの行為
該証人デバイスの該チャレンジｄの受信手段は、該コントローラデバイスと該証明者デバイスの間の該接続手段を通して、及び該証明者デバイスと該証人デバイスの間の該相互接続手段を通して該コントローラデバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄの計算手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。
・ステップ４：チェックの行為
該証明者の該伝送手段は、チェックを実施する該コントローラデバイスに各応答Ｄを送信する。
【００８１】
メッセージの完全性の証明のケース
該第１の実施形態と結合できる第２の実施形態の変形では、本発明による該端末装置は、証明者として知られているエンティティに関連付けられるメッセージＭの完全性の証拠を、コントローラとして知られているエンティティに与えるように設計されている。前記端末装置は、それが該証明者エンティティと関連付けられている証明者デバイスを備え、前記証明者デバイスは相互接続手段によって該証人デバイスと相互接続されている。それは、例えばマイクロプロセッサをベースにした銀行カードの中のマイクロプロセッサの形等の、特にノマドオブジェクト内の論理マイクロ回路の形を取ってよい。前記証明者デバイスは、特にデータ処理通信ネットワークを通して、該コントローラエンティティと関連付けられている該コントローラデバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段を備える。前記コントローラデバイスは特に端末又はリモートサーバの形を取る。
【００８２】
前記端末装置は、以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の該手段は、前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。該証人デバイスは、該相互接続手段を通して該証明者デバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証人デバイスの該伝送手段と呼ばれる伝送の手段を有する。
・ステップ２と３：チャレンジｄの行為、応答Ｄの行為
該証明者デバイスは、少なくとも１つのトークンＴを計算するために、その引数が該メッセージＭ及び各コミットメントＲのすべて又は一部であるハッシュ関数ｈを適用する、以下に該証明者の計算手段と呼ばれる該計算手段を備える。該証明者デバイスは、該コントローラデバイスに該接続手段を通して各トークンＴを送信するために、以下に該証明者デバイスの伝送手段として知られている該伝送手段も有する。
前記コントローラデバイスは、該トークンＴを受信後、コミットメントＲの数に数が等しいチャレンジｄを生成する。
該証人デバイスの該チャレンジｄの受信の手段は、該コントローラデバイスと該証明者デバイスの間の該相互接続手段を通して、及び該証明者デバイスと該証人デバイスの間の該相互接続手段を通して該コントローラデバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄの計算の手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。
・ステップ４：チェックの行為
該証明者の該伝送手段は、各応答Ｄを該チェックを実行する該コントローラデバイスに送信する。
【００８３】
メッセージのデジタル署名及びその真正性の証明
最初の２つのいずれか一方と結合できる第３の実施形態の変形では、本発明による該端末装置は署名エンティティと呼ばれるエンティティによって、以下に該署名済みメッセージとして知られているメッセージＭの該デジタルシグナチャを生成するように設計されている。
【００８４】
該署名済みメッセージは、
−該メッセージＭと、
−該チャレンジｄ、及び／又は該コミットメントＲと、
−該応答Ｄと、
を備える。
【００８５】
前記端末装置は、該署名エンティティと関連付けられている署名デバイスを備える。前記署名デバイスは相互接続手段によって該証人デバイスと相互接続される。それは、マイクロプロセッサをベースにした銀行カードの中のマイクロプロセッサの形等の、特にノマドオブジェクトの中の論理マイクロ回路の形を取ってよい。前記署名デバイスは、特にデータ処理通信ネットワークを通して、該コントローラエンティティと関連付けられている該コントローラデバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段を備える。前記コントローラデバイスは特に端末又はリモートサーバの形を取る。
【００８６】
署名動作：
前記端末装置は以下のステップを実行するために使用される。
・ステップ１：コミットメントＲの行為
呼び出しのたびに、該証人デバイスの該コミットメントＲの計算の手段は、前記に指定された該プロセスを適用することによって各コミットメントＲを計算する。該証人デバイスは、該相互接続手段を通して該署名デバイスに各コミットメントＲのすべて又は部分を送信するために、以下に該証人デバイスの伝送手段と呼ばれている該伝送の手段を備える。
・ステップ２：チャレンジｄの行為
該署名デバイスは、バイナリ行列を計算し、その数がコミットメントＲの数に等しいチャレンジｄをこのバイナリ行列から抽出するために、その引数が該メッセージＭ及び各コミットメントＲのすべて又は部分であるハッシュ関数ｈを適用する、以下に該署名デバイスの計算手段と呼ばれる該計算手段を備える。
・ステップ３：応答Ｄの行為
該チャレンジｄの該受信のための該手段は、該相互接続手段を通して該署名デバイスから来る各チャレンジｄを受信する。該証人デバイスの該応答Ｄを計算するための該手段は、前記に指定された該プロセスを適用することによって該チャレンジｄから該応答Ｄを計算する。該証人デバイスは、該相互接続手段を通して該署名デバイスに該応答Ｄを送信するために、以下に該証人デバイスの伝送の手段と呼ばれている伝送手段を備える。
【００８７】
コントローラデバイス
本発明は、コントローラデバイスにも関する。該コントローラデバイスは特にコントローラエンティティと関連付けられた端末又はリモートサーバの形を取ってよい。該コントローラデバイスは、
−エンティティの真正性、及び／又は
−このエンティティと関連付けられるメッセージＭの完全性
をチェックするように設計されている。
【００８８】
この証明は、以下のパラメータ
−公開値Ｇ1、Ｇ2，．．．Ｇmのｍ個の組（ｍは１以上）
−ｆ個の素因数ｐ1、ｐ2，．．．ｐfの積によって構成され（ｆは２以上）、該コントローラデバイス及び該関連付けられたコントローラエンティティに未知の公開係数ｎ
又はこれらのパラメータの算出値のすべて又は一部によって立証される。
前記係数及び前記秘密値と公開値は以下のタイプの関係
【数５４】
によって関連付けられ、この場合ｖは以下のタイプ
【数５５】
の公開指数を示し、この場合ｋは１より大きなセキュリティパラメータである。
【００８９】
前記ｍ個の公開値Ｇiは該ｆ個の素因数ｐ1，ｐ2，．．．ｐfに従うｍ個の区別できるベース数ｇ1ｇ2，．．．ｇmの二乗ｇi2であり、前記ｆ個の素因数ｐ1，ｐ2，．．．ｐf、及び／又は前記ｍ個のベース数ｇ1ｇ2，．．．ｇmは以下の条件が満たされるように生成される。
【００９０】
第１の条件：
第１の条件に従えば、該方程式
【数５６】
のそれぞれは、ｎを法とした整数の環の中のｘについて解くことができる。
【００９１】
第２の条件：
第２の条件に従えば、Ｇi≡Ｑiv（mod n）のケースでは、ｋ−１階数回、Ｑiを二乗する（mod n）ことによって得られる該ｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００９２】
第２の条件に従えば、Ｇi，Ｑiv≡１（mod n）のケースでは、Ｑiの逆数（mod n）をｋ−１階数回二乗する（mod n）ことによって得られるｍ個の数ｑiの中で、それらの内の１つが±ｇiとは異なる（つまり、トリビアルではない）。
【００９３】
現在の表記に従えば、±ｇiが数ｇiとｎ−ｇiとを表していることがここで指摘されるべきである。
【００９４】
第３の条件：
第３の条件に従えば、以下の２ｍ個の方程式
【数５７】
の中で、それらの内の少なくとも１つはｎを法として整数の環の中のｘについて解くことができる。
【００９５】
エンティティの真正性の証明のケース
第１の実施形態の変形では、本発明による該コントローラデバイスは、証明者と呼ばれているエンティティ及びコントローラと呼ばれているエンティティの真正性を証明するように設計されている。
【００９６】
前記コントローラデバイスは、特にデータ処理通信ネットワークを通して、該証明者エンティティと関連付けられている該証明者デバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段も備える。
【００９７】
前記コントローラデバイスは、以下のステップを実行するために使用される。
・ステップ１と２：コミットメントＲの行為、チャレンジｄの行為
前記コントローラデバイスは、該接続手段を通して該証明者デバイスから来る該コミットメントＲのすべて又は部分の受信のための手段も有する。
該コントローラデバイスは、各コミットメントＲのすべて又は部分を受信後、コミットメントＲの数に数が等しい該チャレンジｄの該生成のためのチャレンジ生成手段を備え、各チャレンジｄは以下に基本的なチャレンジと呼ばれているｍ個の整数ｄiを備える。
該コントローラデバイスは、該接続手段を通して該証明者に該チャレンジｄを送信するために、以下に該コントローラの伝送手段と呼ばれている該伝送手段も備える。
・ステップ３と４：応答Ｄの行為、チェックの行為
またコントローラデバイスは、
−該接続手段を通して該証明者デバイスから来る該応答Ｄの受信のための手段と、
−以下に該コントローラデバイスの計算手段と呼ばれている該計算手段と、
−以下に該コントローラデバイスの比較手段と呼ばれている該比較手段と、
も備える。
・第１のケース：該証明者が各コミットメントＲの部分を送信した
該コントローラデバイスの該受信手段が各コミットメントＲの部分を受信した場合、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの該計算手段は、以下のタイプ
【数５８】
の関係又は以下のタイプ
【数５９】
の関係を満たす再構築されたコミットメントＲ’を、各チャレンジｄ及び各応答Ｄから計算する。
【００９８】
該コントローラデバイスの該比較手段は、再構築された各コミットメントＲ’を受信された各コミットメントＲのすべて又は部分と比較する。
・第２のケース：該証明者が各コミットメントＲの全体性を送信した
該コントローラデバイスの該受信手段が各コミットメントＲの全体性を受信した場合、ｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの該計算手段と該比較手段は、各コミットメントＲが以下のタイプ
【数６０】
の関係又は以下のタイプ
【数６１】
の関係を満たすことを確認する。
【００９９】
メッセージの完全性の証明のケース
該第１の実施形態の変形と結合できる第２の実施形態の変形では、本発明による該コントローラデバイスは、証明者として知られているエンティティと関連付けられているメッセージＭの完全性を証明するように設計されている。
【０１００】
前記コントローラデバイスは、特にデータ処理通信ネットワークを通して、該証明者エンティティと関連付けられている証明者デバイスに対するその電気的、電磁的、光学的又は音響的な接続のための接続手段を備える。
【０１０１】
前記コントローラデバイスは以下のステップを実行するために使用される。
・ステップ１と２：コミットメントＲの行為、チャレンジｄの行為
前記コントローラデバイスは、該接続手段を通して該証明者デバイスから来るトークンＴの該受信のための手段を有する。該コントローラデバイスは、該トークンＴを受信した後に、コミットメントＲの数に数が等しいチャレンジｄの該生成のためのチャレンジ生成手段を有し、各チャレンジｄは以下に基本的なチャレンジと呼ばれているｍ個の整数ｄiを備える。該コントローラデバイスは、該接続手段を通して該証明者に該チャレンジｄを送信するために、以下に該コントローラの伝送手段と呼ばれている該伝送手段も備える。
・ステップ３と４：応答Ｄの行為、チェックの行為
前記コントローラデバイスは、該接続手段を通して該証明者デバイスから来る該応答Ｄの該受信のための手段も備える。前記コントローラデバイスは、第１に、以下のタイプ
【数６２】
の関係又は以下のタイプ
【数６３】
の関係を満たす再構築されたコミットメントＲ’を各チャレンジｄ及び各応答Ｄから計算するために、
第２に、引数として、該メッセージＭ及び各再構築されたコミットメントＲ’のすべて又は部分を有するハッシュ関数ｈを適用することによってトークンＴ’を計算するために、以下にｍ個の公開値Ｇ1，Ｇ2，．．．，Ｇmを有する該コントローラデバイスの計算手段と呼ばれている該計算手段も備える。
【０１０２】
該コントローラデバイスは、該計算されたトークンＴ’を該受信されたトークンＴと比較するために、以下に該コントローラデバイスの比較手段と呼ばれている該比較手段も有する。
【０１０３】
メッセージのデジタルシグナチャ及びその真正性の証明
該最初の２つの実施形態の一方又は他方のいずれかと結合できる第３の実施形態の変形では、本発明によるコントローラデバイスは、コントローラと呼ばれているエンティティによって署名済みのメッセージをチェックすることによって該メッセージＭの真正性を証明するように設計されている。
【０１０４】
ハッシュ関数ｈ（メッセージ、Ｒ）を有する署名エンティティと関連付けられている署名デバイスによって送信される該署名済みメッセージは、
−該メッセージＭと、
−該チャレンジｄ、及び／又は該コミットメントＲと、
−該応答Ｄと、
を備える。
【０１０５】
チェック動作
前記コントローラデバイスは、特にデータ処理通信ネットワークを通して、該署名エンティティに関連付けられている署名デバイスに対するその電気的、電磁的、光学的、又は音響的な接続のための接続手段を備える。前記コントローラデバイスは、該接続手段を通して、該署名デバイスから該署名済みメッセージを受信する。
【０１０６】
該コントローラデバイスは、
−以下に該コントローラデバイスの計算手段と呼ばれる該計算手段と、
−以下に該コントローラデバイスの比較手段と呼ばれる該比較手段と、
を備える。
【０１０７】
・該コントローラデバイスが、コミットメントＲ、チャレンジｄ、応答Ｄを有するケース
該コントローラデバイスがコミットメントＲ、チャレンジｄ、応答Ｄを有する場合、該コントローラデバイスの該計算手段と比較手段は、該コミットメントＲ、該チャレンジｄ及び該応答Ｄが以下のタイプ
【数６４】
の関係又は以下のタイプ
【数６５】
の関係を満たすことを確認する。
【０１０８】
その結果、該コントローラデバイスの該計算手段と比較手段は、該メッセージＭ、該チャレンジｄ及び該コミットメントＲが該ハッシュ関数
【数６６】
を満たすことを確認する。
【０１０９】
・該コントローラデバイスがチャレンジｄ及び応答Ｄを有するケース
該コントローラデバイスがチャレンジｄと応答Ｄを有する場合、該コントローラデバイスの該計算手段は、各チャレンジｄ及び各応答Ｄに基づいて、以下のタイプ
【数６７】
の関係又は以下のタイプ
【数６８】
の関係を満たすコミットメントＲ’を計算することができ、次に該コントローラデバイスの該計算手段と比較手段は、該メッセージＭ及び該チャレンジｄが該ハッシュ関数
【数６９】
を満たすことを確認する。
【０１１０】
・該コントローラデバイスがコミットメントＲ及び応答Ｄを有するケース
該コントローラデバイスがコミットメントＲ及び応答Ｄを有する場合、該コントローラデバイスの該計算手段は該ハッシュ関数を適用し、
【数７０】
となるようにｄ’を計算し、その結果該コントローラデバイスの該計算手段と比較手段は、該コミットメントＲ、該チャレンジｄ’、及び該応答Ｄが以下のタイプ
【数７１】
の関係又は以下のタイプ
【数７２】
の関係を満たすことを確認する。
【０１１１】
ＧＱ方法の目標は、メッセージのデジタルシグナチャとともにエンティティ及びメッセージの動的認証である。これらは「知識の移転を伴わない」方法である。エンティティは、それが１つ又は複数の秘密数を知っていることを証明する。別のエンティティは、それが対応する１つ又は複数の公開数を知っているかチェックする。該証明する側のエンティティは、必要に応じて何度でもそれらを使用できるようにするために、該１つ又は複数の秘密数を明らかにすることなく、該チェック側のエンティティを説得することを希望する。
【０１１２】
各ＧＱ方法は、秘密の高い素数から構成される公開係数に依存している。公開指数ｖ及び公開係数ｎはともに、「ｎを法としてｖ乗する」ことを意味する検証鍵＜ｖ，ｎ＞を形成し、１つ又は複数の一般的な方程式によって、すべて同じタイプの直接的なＧ≡Ｑ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の次の値まで省略する、
−「失敗」を返す。
−「成功」を返す。
【０１６１】
手順が失敗すると、ＧＱ２鍵集合の該生成元は� | |