ゼロ知識証明暗号方法及び装置
本発明は、ｍ≧１の秘密鍵Ｑ1，Ｑ2，…，Ｑm及び公開鍵Ｇ1，Ｇ2，…，Ｇmを保有するキーホルダーを使用し、一対になった各鍵（Ｑi、Ｇi）（ただし、ｉ＝１，…，ｍ）が関係式Ｇi＝Ｑiν ｍｏｄ ｎ、又はＧi×Ｑiν＝１ ｍｏｄ ｎを検証し、ｎは、そのうちの少なくとも二つの数値が異なる素因数であり、ここでは、ｐ1，．．．，ｐfと表記される、ｆ個の秘密素因数（ただし、ｆ＞１）の積に等しい公開整数であり、また、指数νが２の累乗に等しい公開整数である、鍵暗号方法に関する。本発明は、少なくとも上記素因数を知らない限り、公開パラメータに基づいて上記秘密鍵を（適切な時間で）計算することを不可能にさせるために、公開鍵に与えることができる数学的構造を特に教示している。本発明は、この方法を実施する各種装置にも関する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、非対称鍵暗号（「公開鍵暗号」とも呼ばれる）に関する。さらに具体的には、既知のエンティティの信憑性、又は既知のエンティティからのメッセージの信憑性を検証し、あるいはまた、メッセージに署名をするのに役立つ方法及びシステムに関する。
【背景技術】
【０００２】
非対称鍵暗号システムは、一対になった鍵のホルダーを備え、この一対の鍵はそれぞれ、一つの「公開」鍵と一つの「秘密」鍵を備える（各鍵は、さらに、複数のパラメータを持つことができる）。各公開鍵は、認証機関によって、そのホルダーのアイデンティティと結び付けられる。非対称鍵暗号システムは、さらに、ホルダーの認証されたアイデンティティとともに一定数の公開鍵を登録した、「コントローラ」と呼ばれるエンティティを備えている。
【０００３】
「ＲＳＡ」（発明家Ｒ．Ｒｉｖｅｓｔ、Ａ．Ｓｈａｍｉｒ及びＬ．Ａｄｌｅｍａｎの頭文字。「恐らく永遠に解けない新しい暗号」と題されたＭ．Ｇａｒｄｎｅｒの記事を参照、Ｓｃｉｅｎｔｉｆｉｃ Ａｍｅｒｉｃａｎ誌、１９７７年８月）と呼ばれる非対称鍵暗号法の発明以来、整数の素因数分解の問題が集中的に研究されてきた。（素因数分解アルゴリズムの進歩ではなく、コンピュータの出力の進歩により）著しい前進がなされたにもかかわらず、適正な時間内に巨大な整数を素因数分解できる方法は、いまだに確認されていない。利用者がＲＳＡ方法を信頼するのは、まさにこのためである。
【０００４】
ＲＳＡ方法の実行は、異なる二つの巨大な素因数ｐ1とｐ2の積であり、ｎと表記される、「モジュール」と呼ばれる整数と関係している。現行の計算能力を考慮して、少なくとも１０２４ビット（約１０308）のモジュールを使用することを推奨する。ＲＳＡ公開鍵は、モジュールｎ及び（ｐ1−１）と（ｐ2−１）についての素因数である「指数」ｅを含んでいる。これに対応するＲＳＡ秘密鍵は、次のような「指数」ｄを含んでいる。
ｅ×ｄ＝１ ｍｏｄ ［（ｐ1−１）（ｐ2−１）］（「ｍｏｄ」の記号は「ｍｏｄｕｌｏ」を意味する）。
この方法の安全性は、素因数ｐ1とｐ2を検証しない限り、適正な時間内に、ｎ及びｅからｄを計算できないという事実に立脚している。上述したように、適正な時間内に（当然、機密性が保持された）、これらの素因数を計算することは不可能である。
【０００５】
「エンティティの認証」と呼ばれる暗号法は、コントローラとキーホルダーを提示し、ホルダーは、ここでは、「デモンストレータ」と呼ばれ、確実な許可、例えば、情報源に対するアクセス権を取得するため、コントローラからの認証を要請する。デモンストレータは、コントローラに自己のアイデンティティを宣言し、そのアイデンティティに関する公開鍵に対応する秘密鍵を保有していることを実証しなければならない。
【０００６】
この認証は、デモンストレータが自己の秘密鍵について最小限度の情報さえもをコントローラに開示することなく行うことができる。これは、「ゼロ知識証明」（英語で、「ｚｅｒｏ−ｋｎｏｗｌｅｄｇｅ ｐｒｏｏｆ」）認証と呼ばれる。この技法は、「第１７回 計算理論に関するＡＣＭシンポジウム」で、Ｓ．Ｇｏｌｄｗａｓｓｅｒ、Ｓ．Ｍｉｃａｌｉ及びＣ．Ｒａｃｋｏｆｆの「対話証明システムの知識の複雑さ」（２９１ページ〜３０４ページ、１９８５年）と題された報告書によって一般的に報告された。
【０００７】
「アイデンティティのゼロ知識証明」と題された記事（暗号誌、第１巻、７７ページ〜９４ページ、１９８８年）の中で、Ｕ．Ｆｅｉｇｅ、Ａ．Ｆｉａｔ及びＡ．Ｓｈａｍｉｒは、「ゼロ知識認証」暗号方法を提案した。この方法の中では、デモンストレータは、一方では、秘密鍵Ｑを保有しており、他方では、ＲＳＡ モジュールｎ及び公開鍵Ｇ＝Ｑ2 ｍｏｄ ｎを公開している（Ｇに基づくＱの計算、つまり、ｍｏｄｕｌｏ ｎ累乗根の計算は、ｎの素因数がわからない限り、適性な時間内では不可能である）。
【０００８】
エンティティの認証に対して、この方法を適用する場合には、いわゆる「Ｆｉａｔ−Ｓｈａｍｉｒ」方法は、以下のような対話手順：
１．証明文手順：デモンストレータが、無作為に整数ｒを選択し、「証明文」Ｒ＝ｒ2 ｍｏｄ ｎを計算し、証明文をコントローラに伝送する；
２．チャレンジ手順：コントローラが、０又は１の値をとることができる、「チャレンジ」と呼ばれる整数ｄを無作為に選択し、このチャレンジをデモンストレータに伝送する；
３．レスポンス手順：デモンストレータが、「レスポンス」Ｄ＝ｒ×Ｑd ｍｏｄ ｎを計算し、このレスポンスをコントローラに伝送する；及び、
４．検証手順：コントローラが、（Ｄ2／Ｇd）ｍｏｄ ｎを計算し、結果が証明文Ｒに等しいことを検証することを含む。
【０００９】
認証が間違いなく行なわれたと見なす前に、念のため、（毎回、ｒとｄ変更しながら）できる限り何度も、この「一連の」手順を繰り返すことが推奨される。
【００１０】
これは、確かに「ゼロ知識証明」方法である。というのは、オブザーバは、交換されたデータに基づいて、デモンストレータの秘密鍵Ｑを計算できないからである。
【００１１】
いわゆる「Ｆｅｉｇｅ−Ｆｉａｔ−Ｓｈａｍｉｒ」の代案、つまり、「平行」代案によると、デモンストレータは、ｍ＞１個の秘密鍵Ｑ1，Ｑ2，…，Ｑm、を保有しており、ＲＳＡ モジュールｎだけでなく、ｉ＝１，…，ｍで、Ｇi＝Ｑi2 ｍｏｄ ｎである、多数の公開鍵Ｇ1，Ｇ2，…，Ｇmも公開している。
次に、以下の手順：
１．証明文手順：デモンストレータが、無作為に整数ｒを選択し、「証明文」Ｒ＝ｒ2 ｍｏｄ ｎを計算し、証明文をコントローラに伝送する；
２．チャレンジ手順：コントローラが、無作為にｍ個のチャレンジｄ1，ｄ2，…，ｄmを選択するが、ただし、ｉ＝１，…，ｍで、ｄ1は０又は１であり、これらのチャレンジをデモンストレータに伝送する；
３．レスポンス手順：デモンストレータが、レスポンス：
Ｄ＝ｒ×Ｑ1d1×Ｑ2d2×…×Ｑmdm ｍｏｄ ｎ
を計算し、次に、このレスポンスをコントローラに伝送する；
４．検証手順：コントローラが、［Ｄ2／（Ｇ1d1×Ｇ2d2×…×Ｇmdm）］ｍｏｄ ｎを計算し、結果が証明文Ｒに等しいことの検証を実行する。
【００１２】
この「平行」代案は、上述した「一連の」代案と比較すると、Ｆｉａｔ−Ｓｈａｍｉｒの認証手順を高速化することができる。
【００１３】
尚、これらの代案のいずれかを実行するために必要な計算は、デモンストレータが（整数論の専門家が熟知する）「中国の剰余定理」を使用すれば、簡略化することができる。これは、次の要領にしたがって行うことができる。
【００１４】
まず、証明文Ｒの計算を検討する。ｐ1＜ｐ2である、モジュールｎ＝ｐ1×ｐ2について、Ｃはｐ1より小さな正数であり、ｐ１は（ｐ2×Ｃ−１）を割り切る（この数字Ｃは、「中国の剰余」として知られている）。デモンストレータは、無作為に二つの整数ｒ1とｒ2、０＜ｒ1＜ｐ1及び０＜ｒ2＜ｐ2を選択し、二つの「証明文のコンポーネント」Ｒ1＝ｒ12 ｍｏｄ ｐ1及びＲ2＝ｒ22 ｍｏｄ ｐ2を計算する。証明文の値は、下記から導き出される。
Ｒ＝ｚ×ｐ2＋Ｒ2 ただし、ｚ＝Ｃ×（Ｒ1−Ｒ2）
【００１５】
次に、レスポンスＤの計算については、デモンストレータは、次のように行うことができる。ｉ＝１，…，ｍである、「秘密鍵のコンポーネント」Ｑi,1＝Ｑi ｍｏｄ ｐ1及びＱi,2＝Ｑi ｍｏｄ ｐ2を定義する。デモンストレータは、まず、二つの「レスポンスのコンポーネント」を計算する。
Ｄ1＝ｒ1×Ｑ1,ld1×Ｑ2,ld2×…×Ｑm,1dm ｍｏｄ ｐ1、及び、
Ｄ2＝ｒ2×Ｑ1,2d1×Ｑ2,2d2×…×Ｑm,2dm ｍｏｄ ｐ2
次に、レスポンスの値を下記から導き出す。
Ｄ＝ｚ×ｐ2＋Ｄ2 ただし、ｚ＝Ｃ×（Ｄ1−Ｄ2）
【００１６】
この「中国式」計算方法の利点は、ｐ1とｐ2の数値が一般的にｎよりもずっと小さいことを条件として、デモンストレータがｍｏｄｕｌｏ ｎの代わりに、ｍｏｄｕｌｏ ｐ1とｍｏｄｕｌｏ ｐ2を計算することである。
【００１７】
Ｆｉａｔ−Ｓｈａｍｉｒのエンティティの認証手順は、コントローラが受信したメッセージＭが、ここでも「デモンストレータ」と呼ばれるキーホルダーから間違いなく送信されたことを、コントローラが検証する手順に、簡単に置換することができる。このメッセージの認証手順は、次の対話手順：
１．証明文手順：デモンストレータが、整数ｒを無作為に選択し、まず、証明文Ｒ＝ｒ2 ｍｏｄ ｎを計算し、次に、ｈがハッシュ関数（例えば、ＩＳＯ／ＩＥＣ １０１１８−３規格に定義された関数の一つ）である、「タイトル」（「コイン」とも呼ばれる）Ｔ＝ｈ（Ｍ，Ｒ）を計算し、最後に、このタイトルＴをコントローラに伝送する；
２．チャレンジ手順：コントローラが、０又は１の値をとることができるチャレンジｄを無作為に選択し、このチャレンジをデモンストレータに伝送する；
３．レスポンス手順：デモンストレータが、レスポンスＤ＝ｒ×Ｑd ｍｏｄ ｎを計算し、このレスポンスをコントローラに伝送する；
４．検証手順：コントローラは、ｈ［Ｍ，（Ｄ2／Ｇd）ｍｏｄ ｎ］を計算し、結果が間違いなくタイトルＴに等しいことを検証することを含む。
【００１８】
最後に、Ｆｉａｔ−Ｓｈａｍｉｒのエンティティの認証手順は、今度は、「署名者」と呼ばれるあるキーホルダーからコントローラに伝送されるメッセージＭの署名手順を定義するように置換することができる。署名手順はどうかというと、対話式ではないことを注記しておく。署名者は、多数の秘密鍵Ｑ1，Ｑ2，…，Ｑmを保有しており、ここでは、ｍは１より大きく、ＲＳＡ モジュールｎだけでなく、ｉ＝１，…，ｍであり、Ｇi＝Ｑi2 ｍｏｄ ｎである、それぞれの公開鍵Ｇ1，Ｇ2，…，Ｇmも公開している。この署名手順は、以下の手順（上記との類推によって、名称は同じとした）：
１．証明文手順：署名者が、ｉ＝１，…，ｍであるｍ個の整数ｒiを無作為に選択し、まず、証明文Ｒi＝ｒi2 ｍｏｄ ｎを計算し、次に、ｈがｍビットのワードを生成するハッシュ関数である、タイトルＴ＝ｈ（Ｍ，Ｒ1，Ｒ2，…，Ｒm）を計算し、最後に、タイトルＴをコントローラに伝送する；
２．チャレンジ手順：署名者が、自ら、タイトルＴのビットｄ1，ｄ2，…，ｄmを特定する；
３．レスポンス手順：署名者が、「レスポンス」Ｄi＝ｒi×Ｑid1 ｍｏｄ ｎを計算し、これらのレスポンスをコントローラに伝送する；
４．検証手順：コントローラが、下記：
ｈ［Ｍ，（Ｄ12／Ｇ1d1）ｍｏｄ ｎ，（Ｄ22／Ｇ2d2）ｍｏｄ ｎ，…，（Ｄm2／Ｇmdm）ｍｏｄ ｎ］
を計算し、次に、結果が間違いなくタイトルＴに等しいことを検証することを含む。
【００１９】
ここで、Ｆｉａｔ−Ｓｈａｍｉｒ方法の安全性の問題をより間近に検証する。例えば、簡単に上述したエンティティの認証手順の場合には、詐称者（つまり、被詐称者のＲＳＡ モジュールｎ及び公開鍵Ｇを知っているが、秘密鍵Ｑについては知らないエンティティ）がコントローラを欺くことができるのだろうか。
【００２０】
まず、チャレンジは、無作為だとはいえ、二つの値しかとることができないことを注記しておく。詐称者が認証手順の間にコントローラから投げかけられたチャレンジの値を正確に見抜いたとすると（成功率は５０％）、Ｆｉａｔ−Ｓｈａｍｉｒ方法のすべての手順を、コントローラから「現場を押さえ」られずに、申し分なく履行することができるだろうか。この質問に対する回答は、「できる」である。実際、
−詐称者がチャレンジがｄ＝０であることを見抜くと、詐称者は、証明文Ｒ＝ｒ2 ｍｏｄ ｎをコントローラに伝送し、レスポンスは、Ｄ＝ｒとなる。
−詐称者がチャレンジがｄ＝１であることを見抜くと、詐称者は、ｌ＞０の何らかの整数を選択し、証明文Ｒ＝ｌ2×Ｇ ｍｏｄ ｎをコントローラに伝送し、レスポンスは、Ｄ＝ｌ×Ｇ ｍｏｄ ｎとなる。
【００２１】
Ｆｉａｔ−Ｓｈａｍｉｒ方法は、つまり、弱点があるが、この一連の手順を繰り返し、起こりうる詐称者によって一連のチャレンジが正しく予知される可能性を最小限にすると、上述したように弱点の影響を小さくすることができる。したがって、この認証手順の安全性を十分に高めるためには、その時間を著しく長くしなければならない。
【００２２】
国際公開第００／４５５５０号パンフレットは、この欠点を持たない（エンティティの認証手順、メッセージの認証手順及びメッセージの署名手順に適用できる）暗号方法を開示している。この方法によると、デモンストレータは、ＲＳＡ モジュールｎと公開鍵Ｇだけでなく、整数（「指数」と呼ばれる）ν＝２kも公開し、ここでは、ｋ（「安全パラメータ」と呼ばれる）は１より大きな整数となっている。さらに、
Ｇ＝Ｑν ｍｏｄ ｎ （１）
ただし、Ｑは、デモンストレータの秘密鍵である。
【００２３】
国際公開第００／４５５５０号パンフレットによる認証手順は、以下の手順：
１．証明文手順：デモンストレータが、整数ｒを無作為に選択し、「証明文」Ｒ＝ｒν ｍｏｄ ｎを計算し、証明文をコントローラに伝送する；
２．チャレンジ手順：コントローラが、０≦ｄ≦２k-1−１である、「チャレンジ」と呼ばれる整数ｄを無作為に選択し、このチャレンジをデモンストレータに伝送する；
３．レスポンス手順：デモンストレータが、「レスポンス」Ｄ＝ｒ×Ｑd ｍｏｄ ｎを計算し、このレスポンスをコントローラに伝送する；
４．検証手順：コントローラが、（Ｄν／Ｇd）ｍｏｄ ｎを計算し、結果が間違いなく証明文Ｒに等しいことを検証することを含む。
【００２４】
この手順では、チャレンジが異なる２k-1個の値をとれることがわかる（Ｆｉａｔ−Ｓｈａｍｉｒ方法によると二つの値しかとれない）。したがって、詐称者がチャレンジを正しく予知する可能性は、ｋを大きく設定すればするほど小さくなり、これは上記の一連の手順を一度実行するだけで実現される。
【００２５】
これを踏まえた上で、上述したように、この手順をｓ回繰り返す、且つ／又はｍ対の鍵を平行使用すると、安全性を強化することができる。したがって、「中国式に」計算する方が有利である。実際には、（攻撃者がコードを「破る」際、認証よりも署名においてより長い時間をかけることができることを考慮し）、積［（ｋ−１）×ｍ×ｓ］について、認証においては４０以上の値、署名においては８０以上の値を採用することを推奨する。
【００２６】
さらに、国際公開第００／４５５５０号パンフレットによると、公開鍵は次の関係を検証することを必要とする。
Ｇ＝ｇ2 ｍｏｄ ｎ （２）
ここでは、ｇは、１より大きな整数である（「基本数」と呼ばれる）。したがって、上記の（１）と（２）の方程式を組み合わせて、下記の方程式を満足するペア（ｇ，Ｑ）を見つけなければならないことがわかる。ここで、ｎ及びνは所定である。
Ｑν＝ｇ2 ｍｏｄ ｎ （３）
ところで、モジュールの素因数分解を知らない限り、つまり、キーホルダーでなければ、（適切な時間内に）この方程式（３）を解くのは不可能であることは明らかである。要するに、請願ＷＯ−００／４５５５０にしたがう一対の鍵を、これに対応する公開パラメータに基づいて計算するのは、この数値ｎを素因数分解するのと同じぐらい複雑だということである。これら二つの作業は、複雑さの観点からは「等価」であり、このような等価性を備えた１セットの鍵が「等価性基準」を満足すると言える。
【００２７】
ここにおける第１の利点は、これが一つの安全基準だということである（例えば、素因数分解の問題）。第２の利点は、国際公開第００／４５５５０号パンフレットによるキーホルダーについては、自己の公開鍵を認証機関から認証される必要がないこと、つまり、その公開鍵とそのホルダーのアイデンティティとを結び付ける認証を認証機関から取得する必要がないことである。ＲＳＡ モジュールｎについてだけ認証を受ければ、その他のパラメータはホルダー自体によって直接公開されるので、それで十分なのである。一方、例えば、Ｆｉａｔ−Ｓｈａｍｉｒ方法では、様々なエンティティが、同一のＲＳＡモジュールから対になった独自の鍵を構成することができる（Ｆｉａｔ−Ｓｈａｍｉｒのペアは、つまり、上記に定義した等価性基準を満足しない）ので、したがって、個別の各公開鍵は、認証機関を通じて、そのホルダーのアイデンティティと関連付けられなければならない。
【特許文献１】国際公開第００／４５５５０号パンフレット
【発明の開示】
【発明が解決しようとする課題】
【００２８】
ただし、ある種のモジュールｎ（ＲＳＡモジュールの約１／４を表す）についてしか、方程式（３）の解が存在しないことを実証することができる。これは、国際公開第００／４５５５０号パンフレットにしたがってペアになった鍵を生成することを希望するエンティティにとっては、厄介なことである。このエンティティがすでに一群のＲＳＡモジュールを備えている場合には、これらの鍵を構成するのに、一般的に、そのうちの一部しか使用することができず、まだＲＳＡモジュールを備えていない場合には、すべて（又は、ほぼすべて）のＲＳＡモジュールが本方法に適合しない限り、適切なモジュールを見付け出すのはさらに困難になる。
【課題を解決するための手段】
【００２９】
本発明は、したがって、第１の態様によれば、
ｍ≧１の秘密鍵Ｑ1，Ｑ2，…，Ｑm及び公開鍵Ｇ1，Ｇ2，…，Ｇmを保有するホルダーを使用し、一対になった各鍵（Ｑi、Ｇi）（ただし、ｉ＝１，…，ｍ）が関係式Ｇi＝Ｑiν ｍｏｄ ｎ、又はＧi×Ｑiν＝１ ｍｏｄ ｎを検証する非対称鍵暗号方法に関し、ｎは、そのうちの少なくとも二つの数値が異なる素因数であり、ここでは、ｐ1，．．．，ｐfと表記される、ｆ個の秘密素因数（ただし、ｆ＞１）の積に等しい公開整数であり、また、指数νが２の累乗に等しい公開整数である。この方法は、次の点が画期的である。
ν＝２b+k
ただし、ｋは厳密に正の整数で、ｂ＝ｍａｘ（ｂ1，…，ｂf）であり、ｂj（ただし、ｊ＝１，…，ｆ）は、
【数１】
が偶数となることを成立させる最大の整数であり、
各公開鍵Ｇｉ（ただし、ｉ＝１，…，ｍ）については、次のような形式になる：
【数２】
ただし、「基本数」と呼ばれる数字ｇiは、厳密に１より大きな整数であり、また、数字ａiは整数であり、１≦ａi≦ｂで、少なくともそのうちの一つが厳密に１より大きな整数である。
【００３０】
本発明は、とりわけ、各公開鍵がＧi＝ｇi2 ｍｏｄ ｎではなく、
【数３】
の形式であり、ここでは、数ａiの少なくとも一つは、厳密に１より大きな整数であるという点が、国際公開第００／４５５５０号パンフレットとは異なることを注記しておく。
【００３１】
後述する部分では、このような配列により、モジュールｎについて選択する値を問わず、ごく稀な例外を除き（ＲＳＡ方法を実行する際に、このような特殊なモジュールが選択されることは滅多にない）、本発明による鍵、つまり、簡単に上述した条件を満足するペアになった鍵（ｇ，Ｑ）が必ず存在することを証明する。要するに、どんなＲＳＡモジュールでも、本発明による方法に適合するということである。
【００３２】
本発明の特徴によると、上述した素因数ｐ1，…，ｐfの少なくとも一つは、４を法として１に合同であり、整数ａi（ただし、ｉ＝１，…，ｍ）はすべて、上述した数字ｂに等しくなる。
【００３３】
このような配列により、本発明による、セットになった鍵の構造は、著しく簡単になる。
【００３４】
別の特徴によると、上述した基本数ｇ1，…，ｇmの中には少なくとも一つの数字ｇsがあり、上述した素因数ｐ1，…，ｐfの中には、２ではない二つの数字ｐtとｐuがあり、上述した数字ｂ1，…，ｂfを考慮すると、以下を検証する。
・ｂt＝ｂuの場合には、（ｇs｜ｐt）＝−（ｇs｜ｐu）、及び、
・ｂt＜ｂuの場合には、（ｇs｜ｐt）＝−１
ただし、（ｇs｜ｐt）と（ｇs｜ｐu）は、ｐtとｐuに対するｇsのルジェンドル記号である（「Ｌｅｇｅｎｄｒｅ記号」の定義は、後述部分で詳述する）。
【００３５】
このような配列により、得られた鍵は、上記に定義した「等価性基準」を満足することを実証することができる。
【００３６】
さらに別の特徴によると、本方法は、コントローラ及び、ここでは「デモンストレータ」と呼ばれる上述したキーホルダーを提示する。この方法は、以下の手順：
−デモンストレータが、整数ｒを無作為に選択し、「証明文」Ｒ＝ｒν ｍｏｄ ｎを計算し、証明文をコントローラに伝送する手順、
−コントローラが、ｉ＝１，…，ｍである、ｍ個の「チャレンジ」ｄ1，ｄ2，…，ｄmを無作為に選択し、これらのチャレンジをデモンストレータに伝送する手順、
−デモンストレータが、「レスポンス」：
Ｄ＝ｒ×Ｑ1d1×Ｑ2d2×…×Ｑmdm ｍｏｄ ｎ
を計算し、
次に、このレスポンスをコントローラに伝送する手順、及び、
−コントローラが、下記：
Ｄν×Ｇ1ε1d1×Ｇ2ε2d2×…×Ｇmεmdm ｍｏｄ ｎ
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはεi＝−１であり、結果が間違いなく証明文Ｒに等しいことを検証する手順を含む点が注目に値する。
【００３７】
この方法を実行するコントローラとデモンストレータが、証明文又はレスポンスの全体を交換する必要がないことを、重要点として特筆しておく。実際、相互に協定を取り交わすことにより、これらのデータの一部だけを交換するか、又はハッシュ関数を事前に決定することにより、これらのデータの全体又は一部のハッシュの結果を交換することができるのである。
【００３８】
当然、「中国式」に計算を行えば、方法の実行を有利に高速化することができる。
【００３９】
例えば、証明文Ｒの計算については、デモンストレータは、次のように実行することができる。ｐ1＜ｐ2である、モジュールｎ＝ｐ1×ｐ2について、Ｃはｐ1より小さな正数であり、ｐ１は（ｐ2×Ｃ−１）を割り切る（この数字Ｃは、「中国の剰余」として知られている）。デモンストレータは、無作為に二つの整数ｒ1とｒ2、０＜ｒ1＜ｐ1及び０＜ｒ2＜ｐ2を選択し、二つの「証明文のコンポーネント」Ｒ1＝ｒ1ν ｍｏｄ ｐ1及びＲ2＝ｒ2ν ｍｏｄ ｐ2を計算する。証明文の値は、下記から導き出される。
Ｒ＝ｚ×ｐ2＋Ｒ2
ただし、ｚ＝Ｃ×（Ｒ1−Ｒ2）
【００４０】
デモンストレータは、レスポンスＤの取得についても、Ｆｉａｔ−Ｓｈａｍｉｒ方法について上述した計算方法に類似した方法にしたがって、「中国式」に計算することができる。
【００４１】
最後に、チャレンジを、ｉ＝１，…，ｍである、０≦ｄi≦２k−１を検証するチャレンジに限定できることを特筆しておく（これには、デモンストレータについても、コントローラについても、計算を簡略化できる利点がある）。実際、２kではない、ｄiの二つの値については、対応するＱidiの値は、素因数ｇiによって、いずれか一方の値から導き出されることが簡単に検証できる。公開鍵Ｇiの公開には、基本的に、基本数ｇiの開示が必要となるので、０≦ｄi≦２k−１の間に位置するチャレンジの値でも、この範囲を逸脱するチャレンジの値と同じ安全レベルを確保できることがわかる。
【００４２】
さらに別の特徴によると、上記の方法にしたがえば、コントローラは、自己が受信したメッセージＭが、ここでも「デモンストレータ」と呼ばれる上述したキーホルダーから間違いなく送信されたことを検証することができるようになる。この方法は、以下の手順：
−デモンストレータが、整数ｒを無作為に選択し、まず、「証明文」Ｒ＝ｒν ｍｏｄ ｎを計算し、次に、ｈがハッシュ関数である、「タイトル」Ｔ＝ｈ（Ｍ，Ｒ）を計算し、最後に、このタイトルＴをコントローラに伝送する手順、
−コントローラが、ｉ＝１，…，ｍである、ｍ個の「チャレンジ」ｄ1，ｄ2，…，ｄmを無作為に選択し、これらのチャレンジをデモンストレータに伝送する手順、
−デモンストレータが、「レスポンス」：
Ｄ＝ｒ×Ｑ1d1×Ｑ2d2×…×Ｑmdm ｍｏｄ ｎ
を計算し、
次に、このレスポンスをコントローラに伝送する手順、及び、
−コントローラが、下記：
ｈ（Ｍ，Ｄν×Ｇ1ε1d1×Ｇ2ε2d2×…×Ｇmεmdm ｍｏｄ ｎ）
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはεi＝−１であり、次に、結果が間違いなくタイトルＴに等しいことを検証する手順を含む点が注目に値する。
【００４３】
エンティティの認証方法におけるチャレンジの値に関する、上記の注目すべき事実は、言うまでもなく、このメッセージの認証方法にも適用される。
【００４４】
また、このメッセージの認証方法は、メッセージの署名形式と見なされる場合があることについても、特筆しておく。
【００４５】
さらに別の特徴によると、メッセージの別の署名方法を実行することができる。この実施形態にしたがうと、ここでは、「署名者」と呼ばれる上述したキーホルダーが、コントローラに伝送するメッセージＭに実際に署名することができるようになり、この実施形態が以下の手順：
−署名者が、ｉ＝１，…，ｍである、ｍ個の整数ｒiを無作為に選択し、まず、証明文Ｒ＝ｒν ｍｏｄ ｎを計算し、次に、ｈがｍビットのワードを生成するハッシュ関数である、タイトルＴ＝ｈ（Ｍ，Ｒ1，Ｒ2，…，Ｒm）を計算し、最後に、このタイトルＴをコントローラに伝送する手順、
−署名者が、自ら、タイトルＴのビットｄ1，ｄ2，…，ｄmを特定する手順、
−署名者が、「レスポンス」Ｄi＝ｒi×Ｑidi ｍｏｄ ｎを計算し、このレスポンスをコントローラに伝送する手順、及び、
−コントローラが、下記：
ｈ（Ｍ，Ｄ1ν×Ｇ1ε1d1 ｍｏｄ ｎ，Ｄ2ν×Ｇ2ε2d2 ｍｏｄ ｎ，…，Ｄmν×Ｇmεmdm ｍｏｄ ｎ）
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはεi＝−１であり、次に、結果が間違いなくタイトルＴに等しいことを検証する手段を含む点が注目に値する。
【００４６】
第２の態様によれば、本発明は、様々な装置に関する。
【００４７】
本発明は、第１に、プロセッサとメモリとを備えた電子回路に関する。この電子回路は、簡単に上述した暗号方法のいずれかを、上述したキーホルダーとして実行するようにプログラミングできる点が画期的である。
【００４８】
本発明は、第２に、専用電子回路に関する。この電子回路は、この回路がデータを処理し、簡単に上述した暗号方法のいずれかを、上述したキーホルダーとして実行できるようにする複数の小型コンポーネントを備えている点が画期的である。とりわけ、集積回路がこれに相当する（英語では、「Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ（専用用途集積回路）」、即ち「ＡＳＩＣ」）。
【００４９】
これらの二つの電子回路は、例えば、「電子チップ」の形態をとることができる。
【００５０】
本発明は、第３に、端末に接続し、この端末とデータを交換するようになっているポータブル装置に関する。このポータブル装置は、簡単に上述した電子回路を備え、識別データ、及び、上述したキーホルダーに固有の秘密鍵を保存できる点が画期的である。
【００５１】
このポータブル装置は、例えば、チップカード、又はＵＳＢキーとすることができる。
【００５２】
本発明は、第４に、ポータブル装置と接続し、このポータブル装置とデータを交換することができる端末に関する。この端末は、プログラミングされたデータ処理装置を備え、簡単に上述した暗号方法のいずれかを、上述したコントローラとして実行できる点が画期的である。
【００５３】
本発明は、第５に、簡単に上述したポータブル装置及び端末を備えた暗号システムに関する。
【００５４】
本発明は、第６に、情報プログラムコードの命令を備え、簡単に上述した暗号方法のいずれかの手順を、上述したキーホルダーとして実行する、取り外しのできないデータ保存手段に関する。
【００５５】
本発明は、第７に、情報プログラムコードの命令を備え、簡単に上述した暗号方法のいずれかの手順を、上述したキーホルダーとして実行する、部分的に、又は全体的に取り外しのできるデータ保存手段に関する。
【００５６】
本発明は、第８に、簡単に上述した保存手段「キーホルダー」を備えた、データ処理装置に関する。
【００５７】
このデータ処理装置は、例えば、パーソナルコンピュータ、又はサーバーとすることができる。
【００５８】
本発明は、第９に、情報プログラムコードの命令を備え、簡単に上述した暗号方法のいずれかの手順を、上述したコントローラとして実行する、取り外しのできないデータ保存手段に関する。
【００５９】
本発明は、第１０に、情報プログラムコードの命令を備え、簡単に上述した暗号方法のいずれかの手順を、上述したコントローラとして実行する、部分的に、又は全体的に取り外しのできるデータ保存手段に関する。
【００６０】
本発明は、第１１に、簡単に上述した保存手段「コントローラ」を備えた、データ処理装置に関する。
【００６１】
このデータ処理装置は、例えば、パーソナルコンピュータ、又はサーバーとすることができる。
【００６２】
本発明は、第１２に、簡単に上述したデータ処理装置「キーホルダー」及びデータ処理装置「コントローラ」を備えた暗号システムに関する。
【００６３】
これらの装置の提供する利点は、基本的に、簡単に上述した、該当する方法が提供する利点と同等である。
【００６４】
本発明は、さらに、プログラマブル・データ処理装置に指令を出すと、当該データ処理装置が簡単に上述した暗号方法のいずれかを実行するようになる命令を備えた、コンピュータプログラムに適用される。
【００６５】
このコンピュータプログラムの提供する利点は、基本的に、簡単に上述した暗号方法が提供する利点と同等である。
【００６６】
本発明の別の態様及び利点は、下記に詳述する部分を読むことによって明らかとなる。
【００６７】
少なくともそのうちの二つの数値が異なり、ｐ1，…，ｐfと表記される、ｆ個の巨大な素因数（ただし、ｆ＞１）の一般的には積である、ｎと表記されるモジュールについて考察する。
ｎ＝ｐ1×…×ｐf ただし、ｐ1≦…≦ｐf及びｐ1＜ｐf
【００６８】
ｊ＝１，…，ｆである各因数ｐjには、次のように定義された厳密に正の数ｂjを結び付けることができる。（ｐj−１）は２bjで割り切ることができるが、
【数４】
では割り切れない（要するに、ｂjは、
【数５】
が偶数となることを成立させる最大の整数である）。
ｐj＝３ ｍｏｄ ４の場合にはｂj＝１であり、ｐj＝１ ｍｏｄ ４の場合にはｂj＞１であることは、簡単に検証できる。
【００６９】
あるエンティティがキーホルダーになることを希望する場合には、ＲＳＡ モジュールｎをそのエンティティに与えるように認証機関に申請することができる。エンティティは、次に、ｍ≧１の秘密鍵Ｑ1，Ｑ2，…，Ｑmを設定し、当該モジュールｎ、「指数」ν及び公開鍵Ｇ1，Ｇ2，…，Ｇmを公開する。
【００７０】
本発明によると、これらの様々な数量は、次の条件にしたがう。
−指数は、次を成立させる形式となる。
ν＝２b+k
ただし、ｂ＝ｍａｘ（ｂ1，…，ｂf）及びｋ≧１
−各公開鍵Ｇｉ（ただし、ｉ＝１，…，ｍ）は、次を成立させる形式となる。
【数６】
ただし、（「基本数」と呼ばれる）数字ｇiは、厳密に１より大きな整数であり、また、数字ａiは整数であり、１≦ａi≦ｂで、少なくともそのうちの一つは厳密に１より大きな整数である。
−ペアになった各鍵（Ｑi，Ｇi）（ただし、ｉ＝１，…，ｍ）は、下記を検証する。
・関係式Ｇi＝Ｑiν ｍｏｄ ｎ（１ｉ）、又は、
・関係式Ｇi×Ｑiν＝１ ｍｏｄ ｎ （１´ｉ）
【００７１】
これらの条件を満たす鍵のペアが存在するためには、それぞれの素因数ｐjに対する各鍵Ｇiの階数（ｒａｎｋ）が、奇数である必要があることが証明できる。このことから、法ｐ（ただし、ｐは素数）に関する整数体に属するｎｕｌｌでない要素ｘの「ｐに対する階級λ」は、厳密に正の最小正数λであり、これはｘλ＝１ ｍｏｄ ｐ（ｘの連続する累乗は法ｐとされる）を成立させることができる。
【００７２】
モジュールｎの各素因数に対するＧiの階数を奇数にする条件は、いかなる素因数ｐjも、（ｐj−１）が２の累乗に等しくなることを成立させないことを前提とする。しかし、この条件を検証する素数（例えば、３、５、１７又は２５７）は稀であり、モジュールの素因数について巨大な数字を選択する場合には、尚更のこと、極めて稀になる。
【００７３】
この公開鍵の特性は、下記の規則にしたがって整数ｇiとａiを選択すると、確保することができる。
ａi≧ｈ（ｇi）ｍｏｄ ｐj ただし、ｊ＝１，…，ｆ
ここでは、法ｐ（ただし、ｐは素数）に関する整数体に属するｎｕｌｌでない全ての整数ｘについて、ｐに対するｘの階数を割り切る２の最大累乗として、ｈ（ｘ）ｍｏｄ ｐと表記される、「ｐに対するｘの高さ」を定義する。
【発明を実施するための最良の形態】
【００７４】
下記に、非限定の例として、一つの特定の実施形態を紹介する。
【００７５】
この実施形態によると、モジュールｎの素因数ｐjを、そのうちの少なくとも一つが４を法として１に合同であるように選択する（その他の因数は、４を法として１又は３に合同でもよい）。その結果、関係する数字ｂjから、上述した特性が得られる。
ｂ＞１
さらに、
【数７】
とする。
【００７６】
一方、（上述したように、Ｑiν＝ｇi2 ｍｏｄ ｎを検証する）請願ＷＯ−００／４５５５０で定義された鍵については、モジュールのすべての素因数が４を法として３に合同でない限り存在しないことを特筆しておく。
【００７７】
方程式（４）によって定義された公開鍵Ｇiは、モジュールの各素因数に対して奇数の階数を有することを実証することができる。
【００７８】
要するに、上述した基本数ｇ1，…，ｇmについては、少なくとも一つの数字ｇs、上述した素因数ｐ1，…，ｐfについては、２ではない二つの数字ｐtとｐuが存在することが必要であり、以下を検証する。
・ｂt＝ｂuの場合には、（ｇs｜ｐt）＝−（ｇs｜ｐu） （５ａ） 及び、
・ｂt＜ｂuの場合には、（ｇs｜ｐt）＝−１ （５ｂ）
ただし、数字ｂtとｂu（上述した定義を参照）は、ｐtとｐuに対して決定され、（ｇs｜ｐt）と（ｇs｜ｐu）は、対応するｇsのルジェンドル記号である。
【００７９】
この点については、法ｐ（ただし、ｐは２ではない素数である）に関する整数体に属するＮｕｌｌでない要素ｘの「ｐに対するルジェンドル記号」は、ここでは（ｘ｜ｐ）と表記され、 ｘ(p-1)/2 ｍｏｄ ｐに等しいことを繰り返しておく。
ｘがｐの倍数の場合には（ｘ｜ｐ）＝０、
ｘが数体の別の要素の法ｐの自乗に等しい場合には（ｘ｜ｐ）＝＋１、そうでなければ（ｘ｜ｐ）＝−１となることは、簡単に実証できる。
【００８０】
方程式（５ａ−５ｂ）の実施形態は、本発明の実施例の一つであり、ここでは、鍵は「等価性基準」を満足しており、したがって、モジュールの素因数を知らない限り、公開パラメータｎ、ν及びＧ1，Ｇ2，…，Ｇmに基づいて秘密鍵Ｑ1，Ｑ2，…，Ｑmを（適正な時間内に）計算することは不可能である。
【００８１】
ただし、モジュールの素因数分解を知っていれば、次のようにして秘密鍵を取得することができる。Ａは数字（ｐj−１）／２b（ただし、ｊ＝１，…，ｆ）の最小公倍数であり、また、ｕは、Ａの倍数である（ｕ×ν＋１）を成立させる正の最小整数である。各秘密鍵は、下記を検証する。
方程式（１ｉ）（つまり、Ｇi＝Ｑiν ｍｏｄ ｎ）を選択した場合には、Ｑi×Ｇiu＝１ ｍｏｄ ｎ、又は、
方程式（１´ｉ）（つまり、Ｇi×Ｑiν＝１ ｍｏｄ ｎ）を選択した場合には、Ｑi＝Ｇiu ｍｏｄ ｎ
さらに、「中国式」計算で、秘密鍵Ｑ1，Ｑ2，…，Ｑmを計算することもできる。
【００８２】
最後に、基本数に関して注目すべき点を記述する。
【００８３】
本発明による方法の実行中に行なった計算は、基本数が小さければ小さいほど速くなることが確認された。したがって、できるだけ小さな基本数を選択することを推奨する。
【００８４】
例えば、最初の５４個の素数から基本数を選択することができる（５４番目の素数は２５１である）。
【００８５】
代案として、体系的に、最初のｍ個の素数を基本数としてもよい。つまり、ｇ1＝２、ｇ2＝３、ｇ3＝５、ｇ4＝７、ｇ5＝１１といった具合である。このアプローチは、簡潔であるという利点があるが、等価性基準を満足する、セットになった鍵を取得できるかについては保証の限りではない。ただし、等価性基準を満足しないセットの比率は、１／２mより小さいことを証明することができる。例えば、ｍ＝１６（ｇ16＝５３に対応）の場合には、この比率は、１／６５５３６未満となる。
【技術分野】
【０００１】
本発明は、非対称鍵暗号（「公開鍵暗号」とも呼ばれる）に関する。さらに具体的には、既知のエンティティの信憑性、又は既知のエンティティからのメッセージの信憑性を検証し、あるいはまた、メッセージに署名をするのに役立つ方法及びシステムに関する。
【背景技術】
【０００２】
非対称鍵暗号システムは、一対になった鍵のホルダーを備え、この一対の鍵はそれぞれ、一つの「公開」鍵と一つの「秘密」鍵を備える（各鍵は、さらに、複数のパラメータを持つことができる）。各公開鍵は、認証機関によって、そのホルダーのアイデンティティと結び付けられる。非対称鍵暗号システムは、さらに、ホルダーの認証されたアイデンティティとともに一定数の公開鍵を登録した、「コントローラ」と呼ばれるエンティティを備えている。
【０００３】
「ＲＳＡ」（発明家Ｒ．Ｒｉｖｅｓｔ、Ａ．Ｓｈａｍｉｒ及びＬ．Ａｄｌｅｍａｎの頭文字。「恐らく永遠に解けない新しい暗号」と題されたＭ．Ｇａｒｄｎｅｒの記事を参照、Ｓｃｉｅｎｔｉｆｉｃ Ａｍｅｒｉｃａｎ誌、１９７７年８月）と呼ばれる非対称鍵暗号法の発明以来、整数の素因数分解の問題が集中的に研究されてきた。（素因数分解アルゴリズムの進歩ではなく、コンピュータの出力の進歩により）著しい前進がなされたにもかかわらず、適正な時間内に巨大な整数を素因数分解できる方法は、いまだに確認されていない。利用者がＲＳＡ方法を信頼するのは、まさにこのためである。
【０００４】
ＲＳＡ方法の実行は、異なる二つの巨大な素因数ｐ1とｐ2の積であり、ｎと表記される、「モジュール」と呼ばれる整数と関係している。現行の計算能力を考慮して、少なくとも１０２４ビット（約１０308）のモジュールを使用することを推奨する。ＲＳＡ公開鍵は、モジュールｎ及び（ｐ1−１）と（ｐ2−１）についての素因数である「指数」ｅを含んでいる。これに対応するＲＳＡ秘密鍵は、次のような「指数」ｄを含んでいる。
ｅ×ｄ＝１ ｍｏｄ ［（ｐ1−１）（ｐ2−１）］（「ｍｏｄ」の記号は「ｍｏｄｕｌｏ」を意味する）。
この方法の安全性は、素因数ｐ1とｐ2を検証しない限り、適正な時間内に、ｎ及びｅからｄを計算できないという事実に立脚している。上述したように、適正な時間内に（当然、機密性が保持された）、これらの素因数を計算することは不可能である。
【０００５】
「エンティティの認証」と呼ばれる暗号法は、コントローラとキーホルダーを提示し、ホルダーは、ここでは、「デモンストレータ」と呼ばれ、確実な許可、例えば、情報源に対するアクセス権を取得するため、コントローラからの認証を要請する。デモンストレータは、コントローラに自己のアイデンティティを宣言し、そのアイデンティティに関する公開鍵に対応する秘密鍵を保有していることを実証しなければならない。
【０００６】
この認証は、デモンストレータが自己の秘密鍵について最小限度の情報さえもをコントローラに開示することなく行うことができる。これは、「ゼロ知識証明」（英語で、「ｚｅｒｏ−ｋｎｏｗｌｅｄｇｅ ｐｒｏｏｆ」）認証と呼ばれる。この技法は、「第１７回 計算理論に関するＡＣＭシンポジウム」で、Ｓ．Ｇｏｌｄｗａｓｓｅｒ、Ｓ．Ｍｉｃａｌｉ及びＣ．Ｒａｃｋｏｆｆの「対話証明システムの知識の複雑さ」（２９１ページ〜３０４ページ、１９８５年）と題された報告書によって一般的に報告された。
【０００７】
「アイデンティティのゼロ知識証明」と題された記事（暗号誌、第１巻、７７ページ〜９４ページ、１９８８年）の中で、Ｕ．Ｆｅｉｇｅ、Ａ．Ｆｉａｔ及びＡ．Ｓｈａｍｉｒは、「ゼロ知識認証」暗号方法を提案した。この方法の中では、デモンストレータは、一方では、秘密鍵Ｑを保有しており、他方では、ＲＳＡ モジュールｎ及び公開鍵Ｇ＝Ｑ2 ｍｏｄ ｎを公開している（Ｇに基づくＱの計算、つまり、ｍｏｄｕｌｏ ｎ累乗根の計算は、ｎの素因数がわからない限り、適性な時間内では不可能である）。
【０００８】
エンティティの認証に対して、この方法を適用する場合には、いわゆる「Ｆｉａｔ−Ｓｈａｍｉｒ」方法は、以下のような対話手順：
１．証明文手順：デモンストレータが、無作為に整数ｒを選択し、「証明文」Ｒ＝ｒ2 ｍｏｄ ｎを計算し、証明文をコントローラに伝送する；
２．チャレンジ手順：コントローラが、０又は１の値をとることができる、「チャレンジ」と呼ばれる整数ｄを無作為に選択し、このチャレンジをデモンストレータに伝送する；
３．レスポンス手順：デモンストレータが、「レスポンス」Ｄ＝ｒ×Ｑd ｍｏｄ ｎを計算し、このレスポンスをコントローラに伝送する；及び、
４．検証手順：コントローラが、（Ｄ2／Ｇd）ｍｏｄ ｎを計算し、結果が証明文Ｒに等しいことを検証することを含む。
【０００９】
認証が間違いなく行なわれたと見なす前に、念のため、（毎回、ｒとｄ変更しながら）できる限り何度も、この「一連の」手順を繰り返すことが推奨される。
【００１０】
これは、確かに「ゼロ知識証明」方法である。というのは、オブザーバは、交換されたデータに基づいて、デモンストレータの秘密鍵Ｑを計算できないからである。
【００１１】
いわゆる「Ｆｅｉｇｅ−Ｆｉａｔ−Ｓｈａｍｉｒ」の代案、つまり、「平行」代案によると、デモンストレータは、ｍ＞１個の秘密鍵Ｑ1，Ｑ2，…，Ｑm、を保有しており、ＲＳＡ モジュールｎだけでなく、ｉ＝１，…，ｍで、Ｇi＝Ｑi2 ｍｏｄ ｎである、多数の公開鍵Ｇ1，Ｇ2，…，Ｇmも公開している。
次に、以下の手順：
１．証明文手順：デモンストレータが、無作為に整数ｒを選択し、「証明文」Ｒ＝ｒ2 ｍｏｄ ｎを計算し、証明文をコントローラに伝送する；
２．チャレンジ手順：コントローラが、無作為にｍ個のチャレンジｄ1，ｄ2，…，ｄmを選択するが、ただし、ｉ＝１，…，ｍで、ｄ1は０又は１であり、これらのチャレンジをデモンストレータに伝送する；
３．レスポンス手順：デモンストレータが、レスポンス：
Ｄ＝ｒ×Ｑ1d1×Ｑ2d2×…×Ｑmdm ｍｏｄ ｎ
を計算し、次に、このレスポンスをコントローラに伝送する；
４．検証手順：コントローラが、［Ｄ2／（Ｇ1d1×Ｇ2d2×…×Ｇmdm）］ｍｏｄ ｎを計算し、結果が証明文Ｒに等しいことの検証を実行する。
【００１２】
この「平行」代案は、上述した「一連の」代案と比較すると、Ｆｉａｔ−Ｓｈａｍｉｒの認証手順を高速化することができる。
【００１３】
尚、これらの代案のいずれかを実行するために必要な計算は、デモンストレータが（整数論の専門家が熟知する）「中国の剰余定理」を使用すれば、簡略化することができる。これは、次の要領にしたがって行うことができる。
【００１４】
まず、証明文Ｒの計算を検討する。ｐ1＜ｐ2である、モジュールｎ＝ｐ1×ｐ2について、Ｃはｐ1より小さな正数であり、ｐ１は（ｐ2×Ｃ−１）を割り切る（この数字Ｃは、「中国の剰余」として知られている）。デモンストレータは、無作為に二つの整数ｒ1とｒ2、０＜ｒ1＜ｐ1及び０＜ｒ2＜ｐ2を選択し、二つの「証明文のコンポーネント」Ｒ1＝ｒ12 ｍｏｄ ｐ1及びＲ2＝ｒ22 ｍｏｄ ｐ2を計算する。証明文の値は、下記から導き出される。
Ｒ＝ｚ×ｐ2＋Ｒ2 ただし、ｚ＝Ｃ×（Ｒ1−Ｒ2）
【００１５】
次に、レスポンスＤの計算については、デモンストレータは、次のように行うことができる。ｉ＝１，…，ｍである、「秘密鍵のコンポーネント」Ｑi,1＝Ｑi ｍｏｄ ｐ1及びＱi,2＝Ｑi ｍｏｄ ｐ2を定義する。デモンストレータは、まず、二つの「レスポンスのコンポーネント」を計算する。
Ｄ1＝ｒ1×Ｑ1,ld1×Ｑ2,ld2×…×Ｑm,1dm ｍｏｄ ｐ1、及び、
Ｄ2＝ｒ2×Ｑ1,2d1×Ｑ2,2d2×…×Ｑm,2dm ｍｏｄ ｐ2
次に、レスポンスの値を下記から導き出す。
Ｄ＝ｚ×ｐ2＋Ｄ2 ただし、ｚ＝Ｃ×（Ｄ1−Ｄ2）
【００１６】
この「中国式」計算方法の利点は、ｐ1とｐ2の数値が一般的にｎよりもずっと小さいことを条件として、デモンストレータがｍｏｄｕｌｏ ｎの代わりに、ｍｏｄｕｌｏ ｐ1とｍｏｄｕｌｏ ｐ2を計算することである。
【００１７】
Ｆｉａｔ−Ｓｈａｍｉｒのエンティティの認証手順は、コントローラが受信したメッセージＭが、ここでも「デモンストレータ」と呼ばれるキーホルダーから間違いなく送信されたことを、コントローラが検証する手順に、簡単に置換することができる。このメッセージの認証手順は、次の対話手順：
１．証明文手順：デモンストレータが、整数ｒを無作為に選択し、まず、証明文Ｒ＝ｒ2 ｍｏｄ ｎを計算し、次に、ｈがハッシュ関数（例えば、ＩＳＯ／ＩＥＣ １０１１８−３規格に定義された関数の一つ）である、「タイトル」（「コイン」とも呼ばれる）Ｔ＝ｈ（Ｍ，Ｒ）を計算し、最後に、このタイトルＴをコントローラに伝送する；
２．チャレンジ手順：コントローラが、０又は１の値をとることができるチャレンジｄを無作為に選択し、このチャレンジをデモンストレータに伝送する；
３．レスポンス手順：デモンストレータが、レスポンスＤ＝ｒ×Ｑd ｍｏｄ ｎを計算し、このレスポンスをコントローラに伝送する；
４．検証手順：コントローラは、ｈ［Ｍ，（Ｄ2／Ｇd）ｍｏｄ ｎ］を計算し、結果が間違いなくタイトルＴに等しいことを検証することを含む。
【００１８】
最後に、Ｆｉａｔ−Ｓｈａｍｉｒのエンティティの認証手順は、今度は、「署名者」と呼ばれるあるキーホルダーからコントローラに伝送されるメッセージＭの署名手順を定義するように置換することができる。署名手順はどうかというと、対話式ではないことを注記しておく。署名者は、多数の秘密鍵Ｑ1，Ｑ2，…，Ｑmを保有しており、ここでは、ｍは１より大きく、ＲＳＡ モジュールｎだけでなく、ｉ＝１，…，ｍであり、Ｇi＝Ｑi2 ｍｏｄ ｎである、それぞれの公開鍵Ｇ1，Ｇ2，…，Ｇmも公開している。この署名手順は、以下の手順（上記との類推によって、名称は同じとした）：
１．証明文手順：署名者が、ｉ＝１，…，ｍであるｍ個の整数ｒiを無作為に選択し、まず、証明文Ｒi＝ｒi2 ｍｏｄ ｎを計算し、次に、ｈがｍビットのワードを生成するハッシュ関数である、タイトルＴ＝ｈ（Ｍ，Ｒ1，Ｒ2，…，Ｒm）を計算し、最後に、タイトルＴをコントローラに伝送する；
２．チャレンジ手順：署名者が、自ら、タイトルＴのビットｄ1，ｄ2，…，ｄmを特定する；
３．レスポンス手順：署名者が、「レスポンス」Ｄi＝ｒi×Ｑid1 ｍｏｄ ｎを計算し、これらのレスポンスをコントローラに伝送する；
４．検証手順：コントローラが、下記：
ｈ［Ｍ，（Ｄ12／Ｇ1d1）ｍｏｄ ｎ，（Ｄ22／Ｇ2d2）ｍｏｄ ｎ，…，（Ｄm2／Ｇmdm）ｍｏｄ ｎ］
を計算し、次に、結果が間違いなくタイトルＴに等しいことを検証することを含む。
【００１９】
ここで、Ｆｉａｔ−Ｓｈａｍｉｒ方法の安全性の問題をより間近に検証する。例えば、簡単に上述したエンティティの認証手順の場合には、詐称者（つまり、被詐称者のＲＳＡ モジュールｎ及び公開鍵Ｇを知っているが、秘密鍵Ｑについては知らないエンティティ）がコントローラを欺くことができるのだろうか。
【００２０】
まず、チャレンジは、無作為だとはいえ、二つの値しかとることができないことを注記しておく。詐称者が認証手順の間にコントローラから投げかけられたチャレンジの値を正確に見抜いたとすると（成功率は５０％）、Ｆｉａｔ−Ｓｈａｍｉｒ方法のすべての手順を、コントローラから「現場を押さえ」られずに、申し分なく履行することができるだろうか。この質問に対する回答は、「できる」である。実際、
−詐称者がチャレンジがｄ＝０であることを見抜くと、詐称者は、証明文Ｒ＝ｒ2 ｍｏｄ ｎをコントローラに伝送し、レスポンスは、Ｄ＝ｒとなる。
−詐称者がチャレンジがｄ＝１であることを見抜くと、詐称者は、ｌ＞０の何らかの整数を選択し、証明文Ｒ＝ｌ2×Ｇ ｍｏｄ ｎをコントローラに伝送し、レスポンスは、Ｄ＝ｌ×Ｇ ｍｏｄ ｎとなる。
【００２１】
Ｆｉａｔ−Ｓｈａｍｉｒ方法は、つまり、弱点があるが、この一連の手順を繰り返し、起こりうる詐称者によって一連のチャレンジが正しく予知される可能性を最小限にすると、上述したように弱点の影響を小さくすることができる。したがって、この認証手順の安全性を十分に高めるためには、その時間を著しく長くしなければならない。
【００２２】
国際公開第００／４５５５０号パンフレットは、この欠点を持たない（エンティティの認証手順、メッセージの認証手順及びメッセージの署名手順に適用できる）暗号方法を開示している。この方法によると、デモンストレータは、ＲＳＡ モジュールｎと公開鍵Ｇだけでなく、整数（「指数」と呼ばれる）ν＝２kも公開し、ここでは、ｋ（「安全パラメータ」と呼ばれる）は１より大きな整数となっている。さらに、
Ｇ＝Ｑν ｍｏｄ ｎ （１）
ただし、Ｑは、デモンストレータの秘密鍵である。
【００２３】
国際公開第００／４５５５０号パンフレットによる認証手順は、以下の手順：
１．証明文手順：デモンストレータが、整数ｒを無作為に選択し、「証明文」Ｒ＝ｒν ｍｏｄ ｎを計算し、証明文をコントローラに伝送する；
２．チャレンジ手順：コントローラが、０≦ｄ≦２k-1−１である、「チャレンジ」と呼ばれる整数ｄを無作為に選択し、このチャレンジをデモンストレータに伝送する；
３．レスポンス手順：デモンストレータが、「レスポンス」Ｄ＝ｒ×Ｑd ｍｏｄ ｎを計算し、このレスポンスをコントローラに伝送する；
４．検証手順：コントローラが、（Ｄν／Ｇd）ｍｏｄ ｎを計算し、結果が間違いなく証明文Ｒに等しいことを検証することを含む。
【００２４】
この手順では、チャレンジが異なる２k-1個の値をとれることがわかる（Ｆｉａｔ−Ｓｈａｍｉｒ方法によると二つの値しかとれない）。したがって、詐称者がチャレンジを正しく予知する可能性は、ｋを大きく設定すればするほど小さくなり、これは上記の一連の手順を一度実行するだけで実現される。
【００２５】
これを踏まえた上で、上述したように、この手順をｓ回繰り返す、且つ／又はｍ対の鍵を平行使用すると、安全性を強化することができる。したがって、「中国式に」計算する方が有利である。実際には、（攻撃者がコードを「破る」際、認証よりも署名においてより長い時間をかけることができることを考慮し）、積［（ｋ−１）×ｍ×ｓ］について、認証においては４０以上の値、署名においては８０以上の値を採用することを推奨する。
【００２６】
さらに、国際公開第００／４５５５０号パンフレットによると、公開鍵は次の関係を検証することを必要とする。
Ｇ＝ｇ2 ｍｏｄ ｎ （２）
ここでは、ｇは、１より大きな整数である（「基本数」と呼ばれる）。したがって、上記の（１）と（２）の方程式を組み合わせて、下記の方程式を満足するペア（ｇ，Ｑ）を見つけなければならないことがわかる。ここで、ｎ及びνは所定である。
Ｑν＝ｇ2 ｍｏｄ ｎ （３）
ところで、モジュールの素因数分解を知らない限り、つまり、キーホルダーでなければ、（適切な時間内に）この方程式（３）を解くのは不可能であることは明らかである。要するに、請願ＷＯ−００／４５５５０にしたがう一対の鍵を、これに対応する公開パラメータに基づいて計算するのは、この数値ｎを素因数分解するのと同じぐらい複雑だということである。これら二つの作業は、複雑さの観点からは「等価」であり、このような等価性を備えた１セットの鍵が「等価性基準」を満足すると言える。
【００２７】
ここにおける第１の利点は、これが一つの安全基準だということである（例えば、素因数分解の問題）。第２の利点は、国際公開第００／４５５５０号パンフレットによるキーホルダーについては、自己の公開鍵を認証機関から認証される必要がないこと、つまり、その公開鍵とそのホルダーのアイデンティティとを結び付ける認証を認証機関から取得する必要がないことである。ＲＳＡ モジュールｎについてだけ認証を受ければ、その他のパラメータはホルダー自体によって直接公開されるので、それで十分なのである。一方、例えば、Ｆｉａｔ−Ｓｈａｍｉｒ方法では、様々なエンティティが、同一のＲＳＡモジュールから対になった独自の鍵を構成することができる（Ｆｉａｔ−Ｓｈａｍｉｒのペアは、つまり、上記に定義した等価性基準を満足しない）ので、したがって、個別の各公開鍵は、認証機関を通じて、そのホルダーのアイデンティティと関連付けられなければならない。
【特許文献１】国際公開第００／４５５５０号パンフレット
【発明の開示】
【発明が解決しようとする課題】
【００２８】
ただし、ある種のモジュールｎ（ＲＳＡモジュールの約１／４を表す）についてしか、方程式（３）の解が存在しないことを実証することができる。これは、国際公開第００／４５５５０号パンフレットにしたがってペアになった鍵を生成することを希望するエンティティにとっては、厄介なことである。このエンティティがすでに一群のＲＳＡモジュールを備えている場合には、これらの鍵を構成するのに、一般的に、そのうちの一部しか使用することができず、まだＲＳＡモジュールを備えていない場合には、すべて（又は、ほぼすべて）のＲＳＡモジュールが本方法に適合しない限り、適切なモジュールを見付け出すのはさらに困難になる。
【課題を解決するための手段】
【００２９】
本発明は、したがって、第１の態様によれば、
ｍ≧１の秘密鍵Ｑ1，Ｑ2，…，Ｑm及び公開鍵Ｇ1，Ｇ2，…，Ｇmを保有するホルダーを使用し、一対になった各鍵（Ｑi、Ｇi）（ただし、ｉ＝１，…，ｍ）が関係式Ｇi＝Ｑiν ｍｏｄ ｎ、又はＧi×Ｑiν＝１ ｍｏｄ ｎを検証する非対称鍵暗号方法に関し、ｎは、そのうちの少なくとも二つの数値が異なる素因数であり、ここでは、ｐ1，．．．，ｐfと表記される、ｆ個の秘密素因数（ただし、ｆ＞１）の積に等しい公開整数であり、また、指数νが２の累乗に等しい公開整数である。この方法は、次の点が画期的である。
ν＝２b+k
ただし、ｋは厳密に正の整数で、ｂ＝ｍａｘ（ｂ1，…，ｂf）であり、ｂj（ただし、ｊ＝１，…，ｆ）は、
【数１】
が偶数となることを成立させる最大の整数であり、
各公開鍵Ｇｉ（ただし、ｉ＝１，…，ｍ）については、次のような形式になる：
【数２】
ただし、「基本数」と呼ばれる数字ｇiは、厳密に１より大きな整数であり、また、数字ａiは整数であり、１≦ａi≦ｂで、少なくともそのうちの一つが厳密に１より大きな整数である。
【００３０】
本発明は、とりわけ、各公開鍵がＧi＝ｇi2 ｍｏｄ ｎではなく、
【数３】
の形式であり、ここでは、数ａiの少なくとも一つは、厳密に１より大きな整数であるという点が、国際公開第００／４５５５０号パンフレットとは異なることを注記しておく。
【００３１】
後述する部分では、このような配列により、モジュールｎについて選択する値を問わず、ごく稀な例外を除き（ＲＳＡ方法を実行する際に、このような特殊なモジュールが選択されることは滅多にない）、本発明による鍵、つまり、簡単に上述した条件を満足するペアになった鍵（ｇ，Ｑ）が必ず存在することを証明する。要するに、どんなＲＳＡモジュールでも、本発明による方法に適合するということである。
【００３２】
本発明の特徴によると、上述した素因数ｐ1，…，ｐfの少なくとも一つは、４を法として１に合同であり、整数ａi（ただし、ｉ＝１，…，ｍ）はすべて、上述した数字ｂに等しくなる。
【００３３】
このような配列により、本発明による、セットになった鍵の構造は、著しく簡単になる。
【００３４】
別の特徴によると、上述した基本数ｇ1，…，ｇmの中には少なくとも一つの数字ｇsがあり、上述した素因数ｐ1，…，ｐfの中には、２ではない二つの数字ｐtとｐuがあり、上述した数字ｂ1，…，ｂfを考慮すると、以下を検証する。
・ｂt＝ｂuの場合には、（ｇs｜ｐt）＝−（ｇs｜ｐu）、及び、
・ｂt＜ｂuの場合には、（ｇs｜ｐt）＝−１
ただし、（ｇs｜ｐt）と（ｇs｜ｐu）は、ｐtとｐuに対するｇsのルジェンドル記号である（「Ｌｅｇｅｎｄｒｅ記号」の定義は、後述部分で詳述する）。
【００３５】
このような配列により、得られた鍵は、上記に定義した「等価性基準」を満足することを実証することができる。
【００３６】
さらに別の特徴によると、本方法は、コントローラ及び、ここでは「デモンストレータ」と呼ばれる上述したキーホルダーを提示する。この方法は、以下の手順：
−デモンストレータが、整数ｒを無作為に選択し、「証明文」Ｒ＝ｒν ｍｏｄ ｎを計算し、証明文をコントローラに伝送する手順、
−コントローラが、ｉ＝１，…，ｍである、ｍ個の「チャレンジ」ｄ1，ｄ2，…，ｄmを無作為に選択し、これらのチャレンジをデモンストレータに伝送する手順、
−デモンストレータが、「レスポンス」：
Ｄ＝ｒ×Ｑ1d1×Ｑ2d2×…×Ｑmdm ｍｏｄ ｎ
を計算し、
次に、このレスポンスをコントローラに伝送する手順、及び、
−コントローラが、下記：
Ｄν×Ｇ1ε1d1×Ｇ2ε2d2×…×Ｇmεmdm ｍｏｄ ｎ
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはεi＝−１であり、結果が間違いなく証明文Ｒに等しいことを検証する手順を含む点が注目に値する。
【００３７】
この方法を実行するコントローラとデモンストレータが、証明文又はレスポンスの全体を交換する必要がないことを、重要点として特筆しておく。実際、相互に協定を取り交わすことにより、これらのデータの一部だけを交換するか、又はハッシュ関数を事前に決定することにより、これらのデータの全体又は一部のハッシュの結果を交換することができるのである。
【００３８】
当然、「中国式」に計算を行えば、方法の実行を有利に高速化することができる。
【００３９】
例えば、証明文Ｒの計算については、デモンストレータは、次のように実行することができる。ｐ1＜ｐ2である、モジュールｎ＝ｐ1×ｐ2について、Ｃはｐ1より小さな正数であり、ｐ１は（ｐ2×Ｃ−１）を割り切る（この数字Ｃは、「中国の剰余」として知られている）。デモンストレータは、無作為に二つの整数ｒ1とｒ2、０＜ｒ1＜ｐ1及び０＜ｒ2＜ｐ2を選択し、二つの「証明文のコンポーネント」Ｒ1＝ｒ1ν ｍｏｄ ｐ1及びＲ2＝ｒ2ν ｍｏｄ ｐ2を計算する。証明文の値は、下記から導き出される。
Ｒ＝ｚ×ｐ2＋Ｒ2
ただし、ｚ＝Ｃ×（Ｒ1−Ｒ2）
【００４０】
デモンストレータは、レスポンスＤの取得についても、Ｆｉａｔ−Ｓｈａｍｉｒ方法について上述した計算方法に類似した方法にしたがって、「中国式」に計算することができる。
【００４１】
最後に、チャレンジを、ｉ＝１，…，ｍである、０≦ｄi≦２k−１を検証するチャレンジに限定できることを特筆しておく（これには、デモンストレータについても、コントローラについても、計算を簡略化できる利点がある）。実際、２kではない、ｄiの二つの値については、対応するＱidiの値は、素因数ｇiによって、いずれか一方の値から導き出されることが簡単に検証できる。公開鍵Ｇiの公開には、基本的に、基本数ｇiの開示が必要となるので、０≦ｄi≦２k−１の間に位置するチャレンジの値でも、この範囲を逸脱するチャレンジの値と同じ安全レベルを確保できることがわかる。
【００４２】
さらに別の特徴によると、上記の方法にしたがえば、コントローラは、自己が受信したメッセージＭが、ここでも「デモンストレータ」と呼ばれる上述したキーホルダーから間違いなく送信されたことを検証することができるようになる。この方法は、以下の手順：
−デモンストレータが、整数ｒを無作為に選択し、まず、「証明文」Ｒ＝ｒν ｍｏｄ ｎを計算し、次に、ｈがハッシュ関数である、「タイトル」Ｔ＝ｈ（Ｍ，Ｒ）を計算し、最後に、このタイトルＴをコントローラに伝送する手順、
−コントローラが、ｉ＝１，…，ｍである、ｍ個の「チャレンジ」ｄ1，ｄ2，…，ｄmを無作為に選択し、これらのチャレンジをデモンストレータに伝送する手順、
−デモンストレータが、「レスポンス」：
Ｄ＝ｒ×Ｑ1d1×Ｑ2d2×…×Ｑmdm ｍｏｄ ｎ
を計算し、
次に、このレスポンスをコントローラに伝送する手順、及び、
−コントローラが、下記：
ｈ（Ｍ，Ｄν×Ｇ1ε1d1×Ｇ2ε2d2×…×Ｇmεmdm ｍｏｄ ｎ）
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはεi＝−１であり、次に、結果が間違いなくタイトルＴに等しいことを検証する手順を含む点が注目に値する。
【００４３】
エンティティの認証方法におけるチャレンジの値に関する、上記の注目すべき事実は、言うまでもなく、このメッセージの認証方法にも適用される。
【００４４】
また、このメッセージの認証方法は、メッセージの署名形式と見なされる場合があることについても、特筆しておく。
【００４５】
さらに別の特徴によると、メッセージの別の署名方法を実行することができる。この実施形態にしたがうと、ここでは、「署名者」と呼ばれる上述したキーホルダーが、コントローラに伝送するメッセージＭに実際に署名することができるようになり、この実施形態が以下の手順：
−署名者が、ｉ＝１，…，ｍである、ｍ個の整数ｒiを無作為に選択し、まず、証明文Ｒ＝ｒν ｍｏｄ ｎを計算し、次に、ｈがｍビットのワードを生成するハッシュ関数である、タイトルＴ＝ｈ（Ｍ，Ｒ1，Ｒ2，…，Ｒm）を計算し、最後に、このタイトルＴをコントローラに伝送する手順、
−署名者が、自ら、タイトルＴのビットｄ1，ｄ2，…，ｄmを特定する手順、
−署名者が、「レスポンス」Ｄi＝ｒi×Ｑidi ｍｏｄ ｎを計算し、このレスポンスをコントローラに伝送する手順、及び、
−コントローラが、下記：
ｈ（Ｍ，Ｄ1ν×Ｇ1ε1d1 ｍｏｄ ｎ，Ｄ2ν×Ｇ2ε2d2 ｍｏｄ ｎ，…，Ｄmν×Ｇmεmdm ｍｏｄ ｎ）
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはεi＝−１であり、次に、結果が間違いなくタイトルＴに等しいことを検証する手段を含む点が注目に値する。
【００４６】
第２の態様によれば、本発明は、様々な装置に関する。
【００４７】
本発明は、第１に、プロセッサとメモリとを備えた電子回路に関する。この電子回路は、簡単に上述した暗号方法のいずれかを、上述したキーホルダーとして実行するようにプログラミングできる点が画期的である。
【００４８】
本発明は、第２に、専用電子回路に関する。この電子回路は、この回路がデータを処理し、簡単に上述した暗号方法のいずれかを、上述したキーホルダーとして実行できるようにする複数の小型コンポーネントを備えている点が画期的である。とりわけ、集積回路がこれに相当する（英語では、「Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ（専用用途集積回路）」、即ち「ＡＳＩＣ」）。
【００４９】
これらの二つの電子回路は、例えば、「電子チップ」の形態をとることができる。
【００５０】
本発明は、第３に、端末に接続し、この端末とデータを交換するようになっているポータブル装置に関する。このポータブル装置は、簡単に上述した電子回路を備え、識別データ、及び、上述したキーホルダーに固有の秘密鍵を保存できる点が画期的である。
【００５１】
このポータブル装置は、例えば、チップカード、又はＵＳＢキーとすることができる。
【００５２】
本発明は、第４に、ポータブル装置と接続し、このポータブル装置とデータを交換することができる端末に関する。この端末は、プログラミングされたデータ処理装置を備え、簡単に上述した暗号方法のいずれかを、上述したコントローラとして実行できる点が画期的である。
【００５３】
本発明は、第５に、簡単に上述したポータブル装置及び端末を備えた暗号システムに関する。
【００５４】
本発明は、第６に、情報プログラムコードの命令を備え、簡単に上述した暗号方法のいずれかの手順を、上述したキーホルダーとして実行する、取り外しのできないデータ保存手段に関する。
【００５５】
本発明は、第７に、情報プログラムコードの命令を備え、簡単に上述した暗号方法のいずれかの手順を、上述したキーホルダーとして実行する、部分的に、又は全体的に取り外しのできるデータ保存手段に関する。
【００５６】
本発明は、第８に、簡単に上述した保存手段「キーホルダー」を備えた、データ処理装置に関する。
【００５７】
このデータ処理装置は、例えば、パーソナルコンピュータ、又はサーバーとすることができる。
【００５８】
本発明は、第９に、情報プログラムコードの命令を備え、簡単に上述した暗号方法のいずれかの手順を、上述したコントローラとして実行する、取り外しのできないデータ保存手段に関する。
【００５９】
本発明は、第１０に、情報プログラムコードの命令を備え、簡単に上述した暗号方法のいずれかの手順を、上述したコントローラとして実行する、部分的に、又は全体的に取り外しのできるデータ保存手段に関する。
【００６０】
本発明は、第１１に、簡単に上述した保存手段「コントローラ」を備えた、データ処理装置に関する。
【００６１】
このデータ処理装置は、例えば、パーソナルコンピュータ、又はサーバーとすることができる。
【００６２】
本発明は、第１２に、簡単に上述したデータ処理装置「キーホルダー」及びデータ処理装置「コントローラ」を備えた暗号システムに関する。
【００６３】
これらの装置の提供する利点は、基本的に、簡単に上述した、該当する方法が提供する利点と同等である。
【００６４】
本発明は、さらに、プログラマブル・データ処理装置に指令を出すと、当該データ処理装置が簡単に上述した暗号方法のいずれかを実行するようになる命令を備えた、コンピュータプログラムに適用される。
【００６５】
このコンピュータプログラムの提供する利点は、基本的に、簡単に上述した暗号方法が提供する利点と同等である。
【００６６】
本発明の別の態様及び利点は、下記に詳述する部分を読むことによって明らかとなる。
【００６７】
少なくともそのうちの二つの数値が異なり、ｐ1，…，ｐfと表記される、ｆ個の巨大な素因数（ただし、ｆ＞１）の一般的には積である、ｎと表記されるモジュールについて考察する。
ｎ＝ｐ1×…×ｐf ただし、ｐ1≦…≦ｐf及びｐ1＜ｐf
【００６８】
ｊ＝１，…，ｆである各因数ｐjには、次のように定義された厳密に正の数ｂjを結び付けることができる。（ｐj−１）は２bjで割り切ることができるが、
【数４】
では割り切れない（要するに、ｂjは、
【数５】
が偶数となることを成立させる最大の整数である）。
ｐj＝３ ｍｏｄ ４の場合にはｂj＝１であり、ｐj＝１ ｍｏｄ ４の場合にはｂj＞１であることは、簡単に検証できる。
【００６９】
あるエンティティがキーホルダーになることを希望する場合には、ＲＳＡ モジュールｎをそのエンティティに与えるように認証機関に申請することができる。エンティティは、次に、ｍ≧１の秘密鍵Ｑ1，Ｑ2，…，Ｑmを設定し、当該モジュールｎ、「指数」ν及び公開鍵Ｇ1，Ｇ2，…，Ｇmを公開する。
【００７０】
本発明によると、これらの様々な数量は、次の条件にしたがう。
−指数は、次を成立させる形式となる。
ν＝２b+k
ただし、ｂ＝ｍａｘ（ｂ1，…，ｂf）及びｋ≧１
−各公開鍵Ｇｉ（ただし、ｉ＝１，…，ｍ）は、次を成立させる形式となる。
【数６】
ただし、（「基本数」と呼ばれる）数字ｇiは、厳密に１より大きな整数であり、また、数字ａiは整数であり、１≦ａi≦ｂで、少なくともそのうちの一つは厳密に１より大きな整数である。
−ペアになった各鍵（Ｑi，Ｇi）（ただし、ｉ＝１，…，ｍ）は、下記を検証する。
・関係式Ｇi＝Ｑiν ｍｏｄ ｎ（１ｉ）、又は、
・関係式Ｇi×Ｑiν＝１ ｍｏｄ ｎ （１´ｉ）
【００７１】
これらの条件を満たす鍵のペアが存在するためには、それぞれの素因数ｐjに対する各鍵Ｇiの階数（ｒａｎｋ）が、奇数である必要があることが証明できる。このことから、法ｐ（ただし、ｐは素数）に関する整数体に属するｎｕｌｌでない要素ｘの「ｐに対する階級λ」は、厳密に正の最小正数λであり、これはｘλ＝１ ｍｏｄ ｐ（ｘの連続する累乗は法ｐとされる）を成立させることができる。
【００７２】
モジュールｎの各素因数に対するＧiの階数を奇数にする条件は、いかなる素因数ｐjも、（ｐj−１）が２の累乗に等しくなることを成立させないことを前提とする。しかし、この条件を検証する素数（例えば、３、５、１７又は２５７）は稀であり、モジュールの素因数について巨大な数字を選択する場合には、尚更のこと、極めて稀になる。
【００７３】
この公開鍵の特性は、下記の規則にしたがって整数ｇiとａiを選択すると、確保することができる。
ａi≧ｈ（ｇi）ｍｏｄ ｐj ただし、ｊ＝１，…，ｆ
ここでは、法ｐ（ただし、ｐは素数）に関する整数体に属するｎｕｌｌでない全ての整数ｘについて、ｐに対するｘの階数を割り切る２の最大累乗として、ｈ（ｘ）ｍｏｄ ｐと表記される、「ｐに対するｘの高さ」を定義する。
【発明を実施するための最良の形態】
【００７４】
下記に、非限定の例として、一つの特定の実施形態を紹介する。
【００７５】
この実施形態によると、モジュールｎの素因数ｐjを、そのうちの少なくとも一つが４を法として１に合同であるように選択する（その他の因数は、４を法として１又は３に合同でもよい）。その結果、関係する数字ｂjから、上述した特性が得られる。
ｂ＞１
さらに、
【数７】
とする。
【００７６】
一方、（上述したように、Ｑiν＝ｇi2 ｍｏｄ ｎを検証する）請願ＷＯ−００／４５５５０で定義された鍵については、モジュールのすべての素因数が４を法として３に合同でない限り存在しないことを特筆しておく。
【００７７】
方程式（４）によって定義された公開鍵Ｇiは、モジュールの各素因数に対して奇数の階数を有することを実証することができる。
【００７８】
要するに、上述した基本数ｇ1，…，ｇmについては、少なくとも一つの数字ｇs、上述した素因数ｐ1，…，ｐfについては、２ではない二つの数字ｐtとｐuが存在することが必要であり、以下を検証する。
・ｂt＝ｂuの場合には、（ｇs｜ｐt）＝−（ｇs｜ｐu） （５ａ） 及び、
・ｂt＜ｂuの場合には、（ｇs｜ｐt）＝−１ （５ｂ）
ただし、数字ｂtとｂu（上述した定義を参照）は、ｐtとｐuに対して決定され、（ｇs｜ｐt）と（ｇs｜ｐu）は、対応するｇsのルジェンドル記号である。
【００７９】
この点については、法ｐ（ただし、ｐは２ではない素数である）に関する整数体に属するＮｕｌｌでない要素ｘの「ｐに対するルジェンドル記号」は、ここでは（ｘ｜ｐ）と表記され、 ｘ(p-1)/2 ｍｏｄ ｐに等しいことを繰り返しておく。
ｘがｐの倍数の場合には（ｘ｜ｐ）＝０、
ｘが数体の別の要素の法ｐの自乗に等しい場合には（ｘ｜ｐ）＝＋１、そうでなければ（ｘ｜ｐ）＝−１となることは、簡単に実証できる。
【００８０】
方程式（５ａ−５ｂ）の実施形態は、本発明の実施例の一つであり、ここでは、鍵は「等価性基準」を満足しており、したがって、モジュールの素因数を知らない限り、公開パラメータｎ、ν及びＧ1，Ｇ2，…，Ｇmに基づいて秘密鍵Ｑ1，Ｑ2，…，Ｑmを（適正な時間内に）計算することは不可能である。
【００８１】
ただし、モジュールの素因数分解を知っていれば、次のようにして秘密鍵を取得することができる。Ａは数字（ｐj−１）／２b（ただし、ｊ＝１，…，ｆ）の最小公倍数であり、また、ｕは、Ａの倍数である（ｕ×ν＋１）を成立させる正の最小整数である。各秘密鍵は、下記を検証する。
方程式（１ｉ）（つまり、Ｇi＝Ｑiν ｍｏｄ ｎ）を選択した場合には、Ｑi×Ｇiu＝１ ｍｏｄ ｎ、又は、
方程式（１´ｉ）（つまり、Ｇi×Ｑiν＝１ ｍｏｄ ｎ）を選択した場合には、Ｑi＝Ｇiu ｍｏｄ ｎ
さらに、「中国式」計算で、秘密鍵Ｑ1，Ｑ2，…，Ｑmを計算することもできる。
【００８２】
最後に、基本数に関して注目すべき点を記述する。
【００８３】
本発明による方法の実行中に行なった計算は、基本数が小さければ小さいほど速くなることが確認された。したがって、できるだけ小さな基本数を選択することを推奨する。
【００８４】
例えば、最初の５４個の素数から基本数を選択することができる（５４番目の素数は２５１である）。
【００８５】
代案として、体系的に、最初のｍ個の素数を基本数としてもよい。つまり、ｇ1＝２、ｇ2＝３、ｇ3＝５、ｇ4＝７、ｇ5＝１１といった具合である。このアプローチは、簡潔であるという利点があるが、等価性基準を満足する、セットになった鍵を取得できるかについては保証の限りではない。ただし、等価性基準を満足しないセットの比率は、１／２mより小さいことを証明することができる。例えば、ｍ＝１６（ｇ16＝５３に対応）の場合には、この比率は、１／６５５３６未満となる。
【特許請求の範囲】
【請求項１】
ｍ≧１の秘密鍵Ｑ1，Ｑ2，…，Ｑm及び公開鍵Ｇ1，Ｇ2，…，Ｇmを保有するホルダーを使用し、一対になった各鍵（Ｑi、Ｇi）（ただし、ｉ＝１，…，ｍ）が関係式Ｇi＝Ｑiν ｍｏｄ ｎ、又はＧi×Ｑiν＝１ ｍｏｄ ｎを検証し、ｎは、そのうちの少なくとも二つの数値が異なる素因数であり、ここではｐ1，．．．，ｐfと表記される、ｆ個の秘密素因数（ただし、ｆ＞１）の積に等しい公開整数であり、また、指数νが２の累乗に等しい公開整数である、非対称鍵暗号方法であって、
ν＝２b+k
ただし、ｋは厳密に正の整数で、ｂ＝ｍａｘ（ｂ1，…，ｂf）であり、ｂj（ただし、ｊ＝１，…，ｆ）は、
【数１】
が偶数となることを成立させる最大の整数であり、
各公開鍵Ｇｉ（ただし、ｉ＝１，…，ｍ）については、次のような形式になる：
【数２】
ただし、「基本数」と呼ばれる数字ｇiは、厳密に１より大きな整数であり、また、数字ａiは整数であり、１≦ａi≦ｂで、少なくともそのうちの一つが厳密に１より大きな整数であることを特徴とする非対称鍵暗号方法。
【請求項２】
前記素因数ｐ1，…，ｐfの少なくとも一つが４を法として１に合同であり、前記整数ａi（ただし、ｉ＝１，…，ｍ）がすべて前記数字ｂに等しいことを特徴とする、請求項１に記載の方法。
【請求項３】
前記基本数ｇ1，…，ｇmの中には少なくとも一つの数字ｇsがあり、前記素因数ｐ1，…，ｐfの中には、２ではない二つの数字ｐtとｐuがあり、前記数字ｂ1，…，ｂfを考慮すると、以下を検証する。
・ｂt＝ｂuの場合には、（ｇs｜ｐt）＝−（ｇs｜ｐu）、及び、
・ｂt＜ｂuの場合には、（ｇs｜ｐt）＝−１
ただし、（ｇs｜ｐt）と（ｇs｜ｐu）が、ｐtとｐuに対するｇsのルジェンドル記号であることを特徴とする、請求項１又は２に記載の方法。
【請求項４】
前記基本数ｇ1，…，ｇmが素数であることを特徴とする、請求項１〜３のいずれか一つに記載の方法。
【請求項５】
コントローラ及び「デモンストレータ」と呼ばれる前記キーホルダーを提示し、以下の手順：
−前記デモンストレータが、整数ｒを無作為に選択し、「証明文」Ｒ＝ｒν ｍｏｄ ｎを計算し、前記証明文を前記コントローラに伝送する手順、
−前記コントローラが、ｉ＝１，…，ｍである、ｍ個の「チャレンジ」ｄ1，ｄ2，…，ｄmを無作為に選択し、前記チャレンジを前記デモンストレータに伝送する手順、
−前記デモンストレータが、「レスポンス」：
Ｄ＝ｒ×Ｑ1d1×Ｑ2d2×…×Ｑmdm ｍｏｄ ｎ
を計算し、
次に、前記レスポンスを前記コントローラに伝送する手順、及び、
−前記コントローラが、下記：
Ｄν×Ｇ1ε1d1×Ｇ2ε2d2×…×Ｇmεmdm ｍｏｄ ｎ
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはεi＝−１であり、結果が間違いなく前記証明文Ｒに等しいことを検証する手順を含むことを特徴とする、請求項１〜４のいずれか一つに記載の方法。
【請求項６】
コントローラが、自己が受信したメッセージＭが、ここで「デモンストレータ」と呼ばれる前記キーホルダーから間違いなく送信されたことを検証することができるようにする、以下の手順：
−前記デモンストレータが、整数ｒを無作為に選択し、まず、「証明文」Ｒ＝ｒν ｍｏｄ ｎを計算し、次に、ｈがハッシュ関数である、「タイトル」Ｔ＝ｈ（Ｍ，Ｒ）を計算し、最後に、前記タイトルＴを前記コントローラに伝送する手順、
−前記コントローラが、ｉ＝１，…，ｍである、ｍ個の「チャレンジ」ｄ1，ｄ2，…，ｄmを無作為に選択し、前記チャレンジを前記デモンストレータに伝送する手順、
−前記デモンストレータが、「レスポンス」：
Ｄ＝ｒ×Ｑ1d1×Ｑ2d2×…×Ｑmdm ｍｏｄ ｎ
を計算し、
次に、前記レスポンスを前記コントローラに伝送する手順、及び、
−前記コントローラが、下記：
ｈ（Ｍ，Ｄν×Ｇ1ε1d1×Ｇ2ε2d2×…×Ｇmεmdm ｍｏｄ ｎ）
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはε1＝−１であり、結果が間違いなく前記タイトルＴに等しいことを検証する手順を含むことを特徴とする、請求項１〜４のいずれか一つに記載の方法。
【請求項７】
前記チャレンジがｉ＝１，…，ｍである、０≦ｄi≦２k−１を検証することを特徴とする、請求項５又は６に記載の方法。
【請求項８】
ここでは「署名者」と呼ばれる、前記キーホルダーが、コントローラに伝送するメッセージＭに署名することができるようにする、以下の手順：
−前記署名者が、ｉ＝１，…，ｍであるｍ個の整数ｒiを無作為に選択し、まず、証明文Ｒ＝ｒν ｍｏｄ ｎを計算し、次に、ｈがｍ ビットのワードを生成するハッシュ関数である、タイトルＴ＝ｈ（Ｍ，Ｒ1，Ｒ2，…，Ｒm）を計算し、最後に、前記タイトルＴを前記コントローラに伝送する手順、
−前記署名者が、自ら、前記タイトルＴの前記ビットｄ1，ｄ2，…，ｄmを特定する手順、
−前記署名者が、「レスポンス」Ｄi＝ｒi×Ｑidi ｍｏｄ ｎを計算し、前記レスポンスを前記コントローラに伝送する手順、及び、
−前記コントローラが、下記：
ｈ（Ｍ，Ｄ1ν×Ｇ1ε1d1 ｍｏｄ ｎ，Ｄ2ν×Ｇ2ε2d2 ｍｏｄ ｎ，…，Ｄmν×Ｇmεmdm ｍｏｄ ｎ）
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはεi＝−１であり、結果が間違いなく前記タイトルＴに等しいことを検証する手順を含むことを特徴とする、請求項１〜４のいずれか一つに記載の方法。
【請求項９】
プロセッサとメモリとを備えた電子回路であって、請求項１〜８のいずれか一つに記載の方法を、前記キーホルダーとして実行するようにプログラミングできることを特徴とする電子回路。
【請求項１０】
データを処理し、請求項１〜８のいずれか一つに記載の方法を、前記キーホルダーとして実行できるようにする小型コンポーネントを備えることを特徴とする、専用電子回路。
【請求項１１】
端末に接続し、前記端末とデータを交換するようになっているポータブル装置であって、請求項９又は１０に記載の電子回路を備え、識別データ、及び、前記キーホルダーに固有の秘密鍵を保存できることを特徴とするポータブル装置。
【請求項１２】
ポータブル装置と接続し、前記ポータブル装置とデータを交換することができる端末であって、請求項１〜８のいずれか一つに記載の方法を、前記コントローラとして実行できるようにするプログラミングされたデータ処理装置を備えることを特徴とする端末。
【請求項１３】
請求項１１に記載のポータブル装置及び請求項１２に記載の端末を備えた暗号システム。
【請求項１４】
情報プログラムコードの命令を備え、請求項１〜８のいずれか一つに記載の方法の手順を、前記キーホルダーとして実行する、取り外しのできないデータ保存手段。
【請求項１５】
情報プログラムコードの命令を備え、請求項１〜８のいずれか一つに記載の方法の手順を、前記キーホルダーとして実行する、部分的に、又は全体的に取り外しのできるデータ保存手段。
【請求項１６】
請求項１４又は１５に記載のデータ保存手段を備えたデータ処理装置。
【請求項１７】
情報プログラムコードの命令を備え、請求項１〜８のいずれか一つに記載の方法の手順を、前記コントローラとして実行する、取り外しのできないデータ保存メカニズム。
【請求項１８】
情報プログラムコードの命令を備え、請求項１〜８のいずれか一つに記載の方法の手順を、前記コントローラとして実行する、部分的に、又は全体的に取り外しのできるデータ保存手段。
【請求項１９】
請求項１７又は１８に記載のデータ保存手段を備えていることを特徴とするデータ処理装置。
【請求項２０】
請求項１６に記載のデータ処理装置及び請求項１９に記載のデータ処理装置を備えた暗号システム。
【請求項２１】
プログラマブル・データ処理装置に指令を出すと、前記データ処理装置が請求項１〜８のいずれか一つに記載の方法を実行するようになる命令を備えたコンピュータプログラム。
【請求項１】
ｍ≧１の秘密鍵Ｑ1，Ｑ2，…，Ｑm及び公開鍵Ｇ1，Ｇ2，…，Ｇmを保有するホルダーを使用し、一対になった各鍵（Ｑi、Ｇi）（ただし、ｉ＝１，…，ｍ）が関係式Ｇi＝Ｑiν ｍｏｄ ｎ、又はＧi×Ｑiν＝１ ｍｏｄ ｎを検証し、ｎは、そのうちの少なくとも二つの数値が異なる素因数であり、ここではｐ1，．．．，ｐfと表記される、ｆ個の秘密素因数（ただし、ｆ＞１）の積に等しい公開整数であり、また、指数νが２の累乗に等しい公開整数である、非対称鍵暗号方法であって、
ν＝２b+k
ただし、ｋは厳密に正の整数で、ｂ＝ｍａｘ（ｂ1，…，ｂf）であり、ｂj（ただし、ｊ＝１，…，ｆ）は、
【数１】
が偶数となることを成立させる最大の整数であり、
各公開鍵Ｇｉ（ただし、ｉ＝１，…，ｍ）については、次のような形式になる：
【数２】
ただし、「基本数」と呼ばれる数字ｇiは、厳密に１より大きな整数であり、また、数字ａiは整数であり、１≦ａi≦ｂで、少なくともそのうちの一つが厳密に１より大きな整数であることを特徴とする非対称鍵暗号方法。
【請求項２】
前記素因数ｐ1，…，ｐfの少なくとも一つが４を法として１に合同であり、前記整数ａi（ただし、ｉ＝１，…，ｍ）がすべて前記数字ｂに等しいことを特徴とする、請求項１に記載の方法。
【請求項３】
前記基本数ｇ1，…，ｇmの中には少なくとも一つの数字ｇsがあり、前記素因数ｐ1，…，ｐfの中には、２ではない二つの数字ｐtとｐuがあり、前記数字ｂ1，…，ｂfを考慮すると、以下を検証する。
・ｂt＝ｂuの場合には、（ｇs｜ｐt）＝−（ｇs｜ｐu）、及び、
・ｂt＜ｂuの場合には、（ｇs｜ｐt）＝−１
ただし、（ｇs｜ｐt）と（ｇs｜ｐu）が、ｐtとｐuに対するｇsのルジェンドル記号であることを特徴とする、請求項１又は２に記載の方法。
【請求項４】
前記基本数ｇ1，…，ｇmが素数であることを特徴とする、請求項１〜３のいずれか一つに記載の方法。
【請求項５】
コントローラ及び「デモンストレータ」と呼ばれる前記キーホルダーを提示し、以下の手順：
−前記デモンストレータが、整数ｒを無作為に選択し、「証明文」Ｒ＝ｒν ｍｏｄ ｎを計算し、前記証明文を前記コントローラに伝送する手順、
−前記コントローラが、ｉ＝１，…，ｍである、ｍ個の「チャレンジ」ｄ1，ｄ2，…，ｄmを無作為に選択し、前記チャレンジを前記デモンストレータに伝送する手順、
−前記デモンストレータが、「レスポンス」：
Ｄ＝ｒ×Ｑ1d1×Ｑ2d2×…×Ｑmdm ｍｏｄ ｎ
を計算し、
次に、前記レスポンスを前記コントローラに伝送する手順、及び、
−前記コントローラが、下記：
Ｄν×Ｇ1ε1d1×Ｇ2ε2d2×…×Ｇmεmdm ｍｏｄ ｎ
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはεi＝−１であり、結果が間違いなく前記証明文Ｒに等しいことを検証する手順を含むことを特徴とする、請求項１〜４のいずれか一つに記載の方法。
【請求項６】
コントローラが、自己が受信したメッセージＭが、ここで「デモンストレータ」と呼ばれる前記キーホルダーから間違いなく送信されたことを検証することができるようにする、以下の手順：
−前記デモンストレータが、整数ｒを無作為に選択し、まず、「証明文」Ｒ＝ｒν ｍｏｄ ｎを計算し、次に、ｈがハッシュ関数である、「タイトル」Ｔ＝ｈ（Ｍ，Ｒ）を計算し、最後に、前記タイトルＴを前記コントローラに伝送する手順、
−前記コントローラが、ｉ＝１，…，ｍである、ｍ個の「チャレンジ」ｄ1，ｄ2，…，ｄmを無作為に選択し、前記チャレンジを前記デモンストレータに伝送する手順、
−前記デモンストレータが、「レスポンス」：
Ｄ＝ｒ×Ｑ1d1×Ｑ2d2×…×Ｑmdm ｍｏｄ ｎ
を計算し、
次に、前記レスポンスを前記コントローラに伝送する手順、及び、
−前記コントローラが、下記：
ｈ（Ｍ，Ｄν×Ｇ1ε1d1×Ｇ2ε2d2×…×Ｇmεmdm ｍｏｄ ｎ）
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはε1＝−１であり、結果が間違いなく前記タイトルＴに等しいことを検証する手順を含むことを特徴とする、請求項１〜４のいずれか一つに記載の方法。
【請求項７】
前記チャレンジがｉ＝１，…，ｍである、０≦ｄi≦２k−１を検証することを特徴とする、請求項５又は６に記載の方法。
【請求項８】
ここでは「署名者」と呼ばれる、前記キーホルダーが、コントローラに伝送するメッセージＭに署名することができるようにする、以下の手順：
−前記署名者が、ｉ＝１，…，ｍであるｍ個の整数ｒiを無作為に選択し、まず、証明文Ｒ＝ｒν ｍｏｄ ｎを計算し、次に、ｈがｍ ビットのワードを生成するハッシュ関数である、タイトルＴ＝ｈ（Ｍ，Ｒ1，Ｒ2，…，Ｒm）を計算し、最後に、前記タイトルＴを前記コントローラに伝送する手順、
−前記署名者が、自ら、前記タイトルＴの前記ビットｄ1，ｄ2，…，ｄmを特定する手順、
−前記署名者が、「レスポンス」Ｄi＝ｒi×Ｑidi ｍｏｄ ｎを計算し、前記レスポンスを前記コントローラに伝送する手順、及び、
−前記コントローラが、下記：
ｈ（Ｍ，Ｄ1ν×Ｇ1ε1d1 ｍｏｄ ｎ，Ｄ2ν×Ｇ2ε2d2 ｍｏｄ ｎ，…，Ｄmν×Ｇmεmdm ｍｏｄ ｎ）
を計算し、ただし、ｉ＝１，…，ｍ、Ｇi×Ｑiν＝１ ｍｏｄ ｎの場合にはεi＝＋１、Ｇi＝Ｑiν ｍｏｄ ｎの場合にはεi＝−１であり、結果が間違いなく前記タイトルＴに等しいことを検証する手順を含むことを特徴とする、請求項１〜４のいずれか一つに記載の方法。
【請求項９】
プロセッサとメモリとを備えた電子回路であって、請求項１〜８のいずれか一つに記載の方法を、前記キーホルダーとして実行するようにプログラミングできることを特徴とする電子回路。
【請求項１０】
データを処理し、請求項１〜８のいずれか一つに記載の方法を、前記キーホルダーとして実行できるようにする小型コンポーネントを備えることを特徴とする、専用電子回路。
【請求項１１】
端末に接続し、前記端末とデータを交換するようになっているポータブル装置であって、請求項９又は１０に記載の電子回路を備え、識別データ、及び、前記キーホルダーに固有の秘密鍵を保存できることを特徴とするポータブル装置。
【請求項１２】
ポータブル装置と接続し、前記ポータブル装置とデータを交換することができる端末であって、請求項１〜８のいずれか一つに記載の方法を、前記コントローラとして実行できるようにするプログラミングされたデータ処理装置を備えることを特徴とする端末。
【請求項１３】
請求項１１に記載のポータブル装置及び請求項１２に記載の端末を備えた暗号システム。
【請求項１４】
情報プログラムコードの命令を備え、請求項１〜８のいずれか一つに記載の方法の手順を、前記キーホルダーとして実行する、取り外しのできないデータ保存手段。
【請求項１５】
情報プログラムコードの命令を備え、請求項１〜８のいずれか一つに記載の方法の手順を、前記キーホルダーとして実行する、部分的に、又は全体的に取り外しのできるデータ保存手段。
【請求項１６】
請求項１４又は１５に記載のデータ保存手段を備えたデータ処理装置。
【請求項１７】
情報プログラムコードの命令を備え、請求項１〜８のいずれか一つに記載の方法の手順を、前記コントローラとして実行する、取り外しのできないデータ保存メカニズム。
【請求項１８】
情報プログラムコードの命令を備え、請求項１〜８のいずれか一つに記載の方法の手順を、前記コントローラとして実行する、部分的に、又は全体的に取り外しのできるデータ保存手段。
【請求項１９】
請求項１７又は１８に記載のデータ保存手段を備えていることを特徴とするデータ処理装置。
【請求項２０】
請求項１６に記載のデータ処理装置及び請求項１９に記載のデータ処理装置を備えた暗号システム。
【請求項２１】
プログラマブル・データ処理装置に指令を出すと、前記データ処理装置が請求項１〜８のいずれか一つに記載の方法を実行するようになる命令を備えたコンピュータプログラム。
【公表番号】特表２００７−５１９０４４（Ｐ２００７−５１９０４４Ａ）
【公表日】平成１９年７月１２日（２００７．７．１２）
【国際特許分類】
【出願番号】特願２００６−５５０２４１（Ｐ２００６−５５０２４１）
【出願日】平成１７年１月２４日（２００５．１．２４）
【国際出願番号】ＰＣＴ／ＦＲ２００５／０００１５８
【国際公開番号】ＷＯ２００５／０８１４５２
【国際公開日】平成１７年９月１日（２００５．９．１）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【出願人】（５０６２５０１４７）
【氏名又は名称原語表記】ＭＡＴＨ ＲＩＺＫ ＳＰＲＬ
【Ｆターム（参考）】
【公表日】平成１９年７月１２日（２００７．７．１２）
【国際特許分類】
【出願日】平成１７年１月２４日（２００５．１．２４）
【国際出願番号】ＰＣＴ／ＦＲ２００５／０００１５８
【国際公開番号】ＷＯ２００５／０８１４５２
【国際公開日】平成１７年９月１日（２００５．９．１）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【出願人】（５０６２５０１４７）
【氏名又は名称原語表記】ＭＡＴＨ ＲＩＺＫ ＳＰＲＬ
【Ｆターム（参考）】
[ Back to top ]