(57)【要約】本発明は、電子デバイスを使用する公開鍵の暗号化方法のための電子鍵（ｄ）を生成するための方法に関する。本発明の方法は、２つの別々の計算ステップ、すなわち、（ｉ）ｅが公開指数であり、ｌが暗号化方法の鍵の長さであるペア（ｅ，ｌ）の知識から独立している素数（ｐ，ｑ）のペアの計算と、（ｉｉ）このようにして入手したペアの記憶からなるステップＡと、ステップＡの結果およびペア（ｅ，ｌ）の知識から鍵ｄを計算することからなる、非常に迅速で、上記デバイスによりリアルタイムで実行することができるステップＢを含む。【特許請求の範囲】
【請求項１】
電子デバイスを使用する公開鍵暗号化方法用の電子鍵ｄを生成するための方法であって、２つの別々の計算ステップ、すなわち、
ステップＡ
１）素数のペア（ｐ，ｑ）または素数のペアを表す値を計算するステップであって、この計算は、ｅが公開指数であり、ｌが前記暗号化方法の鍵の長さであり、また、ｌが前記方法のモジュラスＮの長さでもある前記ペア（ｅ，ｌ）の知識とは独立して行われるステップと、
２）このようにして得られた前記ペアまたは値を記憶するステップと、
ステップＢ
ステップＡの結果および前記ペア（ｅ，ｌ）の知識から鍵ｄを計算するステップと
を含むことを主として特徴とする方法。
【請求項２】
ステップＡ−１）が、各ペア（ｐ，ｑ）が将来のペア（ｅ，ｌ）に対応することができる最大の確率を有し、鍵ｄを計算することができるように、小さな素数の積であるパラメータΠを使用して、前記公開指数ｅまたは前記鍵の長さｌを知らなくても、素数のペア（ｐ，ｑ）を計算することを特徴とする、請求項１に記載の電子鍵を生成するための方法。
【請求項３】
ステップＡ−１）の計算が、また、ｅが組｛３，１７，．．．，２１６＋１｝の一部を形成する高い確率を有し、この使用がペア（ｐ，ｑ）ではなく、前記ペア（ｐ，ｑ）の画像と呼ばれる表示値を計算することを可能にするシードσの計算の際に使用されるという事実を考慮に入れることを特徴とする、請求項２に記載の電子鍵を生成するための方法。
【請求項４】
前記記憶ステップＡ−２）が、前記ペアの前記画像を記憶するステップであることを特徴とする、請求項１および３に記載の電子鍵を生成するための方法。
【請求項５】
ステップＡ−１）が、異なる可能なペア（ｅ，ｌ）に対する素数のペア（ｐ，ｑ）を計算するステップであることを特徴とする、請求項１に記載の電子鍵を生成するための方法。
【請求項６】
前記パラメータΠが、例えば、３、１７のような前記公開指数ｅの通常の値を含むことを特徴とする、請求項２および５に記載の電子鍵を生成するための方法。
【請求項７】
ステップＡ−１）が、前記計算したペア（ｐ，ｑ）を圧縮する動作を含み、ステップＡ−２）が、このようにして得られた前記圧縮した値を記憶するステップであることを特徴とする、請求項１に記載の電子鍵を生成するための方法。
【請求項８】
ステップＡ−１）が、例えば、Ｂ０＝２５６ビットのように∝０≧Ｂ０になるように、下限Ｂ０が生成対象のこの素数の長さ∝０に対して設定される素数ｑの生成を含み、下記のサブステップ、すなわち、
１）下記の関係からパラメータｖおよびｗを計算し、これらのパラメータを記憶するサブステップと、
【数１】
2005530212.tif 000009
ここで、Πが記憶され、最も小さい素数ｆの積に対応し、ｆはΠ≦２Ｂｏになるように選択され、
２）整数｛ｖ，．．．，ｗ−１｝の範囲内のある数ｊを選択し、∝＝ｊΠを計算するサブステップと、
３）整数｛０，．．．，Π−１｝の範囲内のＲＳＡ鍵の長さより短い長さの素数ｋを選択し、記憶し、（ｋ，Π）は相互に素の関係にあるサブステップと、
４）ｑ＝ｋ＋∝を計算するサブステップと、
５）ｑが素数であるかどうかを確認し、ｑが素数でない場合には、
ａ）下記の関係を使用してｋに対する新しい値を選択するサブステップと、
ｋ＝ａｋ（ｍｏｄ  Π）；（ａは整数モジュロΠの乗法グループＺ＊πに属する）
ｂ）サブステップ４）からのこの方法の反復を行うサブステップと
を含むことを特徴とする、請求項１に記載の電子鍵を生成するための方法。
【請求項９】
ある数ｊおよびｋを、メモリ内に記憶しているシードσから生成することができることを特徴とする、請求項３および８に記載の電子鍵を生成するための方法。
【請求項１０】
前記素数ｐが、ｑをｐにより置き換え、∝０を∝−∝０により置き換えながら、前記サブステップのすべてを反復することにより生成されることを特徴とする、請求項８に記載の電子鍵を生成するための方法。
【請求項１１】
ステップＢが、ステップＡで入手したペア（ｐ，ｑ）に対して、
・下記の条件：
（ｉ）ｐ−１およびｑ−１が所与のｅを含む素数であること、
（ｉｉ）Ｎ＝ｐ＊ｑが所与の長さ∝の整数であること
を確認するステップと、
・前記ペア（ｐ，ｑ）がこれらの条件を満足しない場合には、
・他のペアを選択し、適切なあるペアを発見するまで前記確認を反復するステップと、
・入手したペア（ｐ，ｑ）から前記鍵ｄを計算するステップと
を含むことを特徴とする、請求項１乃至１１のいずれかに記載の電子鍵を生成するための方法。
【請求項１２】
ＲＳＡタイプの暗号化アルゴリズムの電子鍵ｄを生成することができるセキュア・ポータブル・オブジェクトであって、少なくとも下記のもの、すなわち、
・少なくとも１つのペア（ｅ，ｌ）を受信するための通信手段と、
・ｅが前記公開指数であり、ｌが前記暗号化方法の前記鍵の長さであり、また、ｌがこのｐの前記モジュラスＮの長さである前記ペア（ｅ，ｌ）を知らなくても、素数のペア（ｐ，ｑ）または素数のペアを表す値を計算するステップからなるステップＡの結果を記憶するためのメモリと、
・ステップＡの結果およびペア（ｅ，ｌ）の知識から鍵ｄを計算するステップからなるステップＢを実施するためのプログラムと
を備えることを特徴とするセキュア・ポータブル・オブジェクト。
【請求項１３】
セキュア・ポータブル・オブジェクトは、また、ステップＡを実施するためのプログラムを備え、ステップＡおよびＢが時間の点で独立していることを特徴とする、請求項１２に記載のセキュア・ポータブル・オブジェクト。
【請求項１４】
ステップＡを実施するための前記プログラムが、下記のサブステップ、すなわち、
１）下記の関係からパラメータｖおよびｗを計算し、これらのパラメータを記憶するサブステップと、
【数２】
2005530212.tif 000010
ここで、Πが記憶され、最も小さい素数ｆの積に対応し、ｆはΠ≦２Ｂｏになるように選択され、Ｂ０は、例えば、Ｂ０＝２５６ビットのように∝０≧Ｂ０になるように、生成対象の前記素数の長さ∝０に対して設定される下限であり、
２）整数｛ｖ，．．．，ｗ−１｝の範囲内のある数ｊを選択し、∝＝ｊΠを計算するサブステップと、
３）整数｛０，．．．，Π−１｝の範囲内のＲＳＡ鍵の長さより短い長さの素数ｋを選択し、記憶し、（ｋ，Π）は相互に素の関係にあるサブステップと、
４）ｑ＝ｋ＋∝を計算するサブステップと、
５）ｑが素数であるかどうかを確認し、ｑが素数でない場合には、
ａ）下記の関係を使用してｋに対する新しい値を選択するサブステップと、
ｋ＝ａｋ（ｍｏｄ  Π）；（ａは整数モジュロΠの乗法グループＺ＊πに属する）
ｂ）サブステップ４）からこの方法の反復を行うサブステップと
を実行することを特徴とする、請求項１３に記載のセキュア・ポータブル・オブジェクト。
【請求項１５】
チップ・カードからなることを特徴とする、請求項１２、１３または１４に記載のセキュア・ポータブル・オブジェクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号化方法のための電子鍵を生成するための方法およびこの方法を使用するセキュア・ポータブル・オブジェクトに関する。
本発明は、特に、ＲＳＡタイプの暗号化システムのための鍵の生成、およびセキュリティを必要とする用途でこれらの鍵を使用するためのセキュアオブジェクトへの格納に関する。
【背景技術】
【０００２】
本発明は、特に、チップ・カードの場合のような電気的にプログラム可能なメモリ、または強力な計算リソースのような大きなメモリ・リソースを有さないセキュアオブジェクトに適用される。
本発明の１つの用途は、携帯電話を使用する電子商取引である。この場合、鍵は電話機のＳＩＭカード上に記憶することができる。
【０００３】
あるアプリケーション・プログラムは、例えば、電子商取引コンテキストで秘密データを転送するためにこのような鍵を使用する。以下の説明においては、これらのアプリケーションは、サービス・プロバイダが提供するものと見なされる。
さらに、鍵の統合性を保証するために、証明機関が提供する証明書が、通常、これらの鍵に関連していることは周知である。
これらの公開鍵暗号化方法の中から、下記の記述は、ＲＳＡ（Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  ａｎｄ  Ａｄｌｅｍａｎ）暗号化プロトコルについて説明する。このプロトコルは、長い計算時間と大容量のメモリ空間を必要とする大きな素数を生成するステップを使用する。
【０００４】
このＲＳＡ暗号化プロトコルを使用すれば、情報の暗号化および／または２つのエンティティ間の認証および／またはメッセージの電子署名を行うことができることを思い起こされたい。
ＲＳＡ暗号化プロトコルは、最も頻繁に使用される。何故なら、このプロトコルは、暗号化および署名の生成の両方に使用することができる性質を有しているからである。
【０００５】
そのため、ＲＳＡ暗号化システムは、暗号化または署名確認機能を行うための「公開」アルゴリズムと、解読または署名生成機能を行う「秘密」アルゴリズムを備える。
このセキュリティは、大きな２つの秘密の素数ｐおよびｑの積である大きな公開整数Ｎの因数分解が難しいことをベースとしている。このペア（ｐ，ｑ）は、解読機能または署名計算機能が使用する秘密鍵ｄを計算する際に使用される。
【０００６】
以下に説明する問題をもっとよく理解してもらうために、ＲＳＡ暗号化スキームで使用するパラメータについて簡単に説明する。
１）公開指数ｅ：
この公開指数は、あるアプリケーションに特有なものであり、このアプリケーションにより提供される。それ故、この公開指数は、この同じアプリケーションのすべてのユーザに共通のものである。
２）パラメータｐおよびｑ：
これらのパラメータは、長い時間がかかる計算により生成される。これらのパラメータは、通常、同じ長さ（同じサイズ）を有する。この長さは従来５１２ビットである。セキュリティを高めるために、この長さを５１２ビットから２０４８ビットに延長することができる。２０４８ビットは、将来使用するためのものである。
【０００７】
３）Ｎは公開モジュラスであり、下記の関係から計算される。
Ｎ＝ｐ＊ｑ
このアルゴリズムの鍵は、公開モジュラスＮの長さが∝である場合、その長さが∝であると言われる。この長さはアプリケーション（またはサービス・プロバイダ）により設定される。
４）パラメータｅおよびＮは公開鍵を形成する。
５）秘密鍵ｄは、下記の関係から計算される。
ｄ＝１／ｅ［ｍｏｄ（ｐ−１）（ｑ−１）］；（１／ｅ＝ｅ−１）
すなわち、ｅｄ＝１［（ｍｏｄ  ｐｐｃｍ（ｐ−１，ｑ−１）］；ｐｐｃｍは、最小公倍数である。
【０００８】
秘密パラメータは、３つの数（ｄ，ｐ，ｑ）により形成される。
６）秘密鍵の「通常」の形は、
（ｄ，Ｎ）
である。
６）秘密鍵のＣＲＴ（中国人剰余定理）の形は、
この場合、秘密鍵は下記の５つのパラメータを含む。
ｐ，ｑ
ｄｐ（ｄｐ＝ｄ  ｍｏｄ（ｐ−１）の場合）
ｄｑ（ｄｑ＝ｄ  ｍｏｄ（ｑ−１）の場合）
Ｉｑ（Ｉｑ＝ｑ−１  ｍｏｄｐの場合）
【０００９】
それ故、ＲＳＡスキームによる鍵の生成の原理は、理解できると思うが、アプリケーションが設定する公開指数ｅ（または公開鍵）からの秘密鍵ｄの生成である。パラメータｐ，ｑは、ｐ＊ｑ＝Ｎになるように生成される。Ｎの長さ∝は一定である。
【００１０】
多数のアプリケーションが供給される場合、各サービス・プロバイダは、対応する秘密鍵ｄを生成することができるように、その公開指数ｅおよび公開モジュラスＮの長さを提供する。
それ故、ＲＳＡ鍵計算を行うためには、公開指数ｅおよびアルゴリズムの鍵の長さ∝、すなわちモジュラスＮの長さを知らなければならない。データｅおよび∝を入力しても、ｑが下記の条件を満足するように素数のペアｐおよびｑを生成しなければならない。
【００１１】
（ｉ）ｐ−１およびｑ−１はｅを含む素数であること。
（ｉｉ）Ｎ＝ｐ＊ｑは、長さ∝の整数であること。
これらの制約があるために計算に長い時間がかかる。
この点に関して、チップ・カードのようなポータブル・オブジェクトのための鍵の生成および記憶は、現在は下記の２つの方法で行われることを思い起こされたい。
【００１２】
第１の方法によれば、ＲＳＡ鍵の計算は、かなりの計算力を利用するために、サーバ上で行われる。セキュリティを高めるために、その個人化の段階でセキュアオブジェクト内の鍵によりダウンロードされる証明書が必要になる。
この方法は２つの欠点がある。
・一方では、個人化のセキュア・コンテキストのレベルは比較的高いが、サーバからセキュアオブジェクトに鍵を転送するために、鍵が盗まれたりまたはコピーされたりする恐れがある。
・他方では、各鍵は、最初の個人化の段階でオブジェクト内にロードされるが、その場合、将来の要件を予測することができるように、各オブジェクト内に最大数の鍵を提供しなければならない。
【００１３】
実際には、ポータブル・オブジェクト内には、これらの鍵を実際に後で使用するかどうか分からない状態で、使用するかも知れない各アプリケーションに対応する複数の組の鍵および証明書が記憶される。大容量のメモリ空間が必要もないのに使用される。例えば、１０２４ビットのモジュラスを有するＲＳＡ鍵の場合には０．３キロバイトが必要であるが、一方、現在のカードは、せいぜい３２キロバイトのプログラム可能なメモリしか有していない。さらに、多数の証明書が証明機関から購入されるが、これは高いものにつく。
【００１４】
最後に軽んじられない欠点は、現在の時点でおよび新しいアプリケーションが予測される場合でも、新しい鍵を追加できないことである。
第２の方法によれば、計算をセキュアオブジェクト内で行うことができる。そのため、上記方法の第１の欠点を克服することができるが、計算能力が低いセキュアオブジェクト内での処理量が増大する。
【００１５】
ＲＳＡ鍵の生成が、チップ・カードのようなポータブル・オブジェクトにより行われた場合には、ＲＳＡ鍵の必要な長さが２０４８ビットである場合、強力なアルゴリズムを使用しても計算に３０秒かかる。
所与のアプリケーションに対してＲＳＡ鍵を１回だけ生成すればよいので、ある種のアプリケーションの場合には、この計算時間は許容することができるが、携帯電話サービス（例えば、ＧＳＭ）の場合には満足できるものではない。何故なら、ＳＩＭカードを変更する度にこの動作を行わなければならないし、異なるアプリケーションの要件を満足するために、もっと多数の鍵を提供しなければならないからである。
【００１６】
かなりの計算リソースを必要とするために、種々のサービス・プロバイダから提供される公開指数ｅから個人化の段階で常に複数の鍵が生成される。この計算ステップは続けて実行することはできない。何故なら、オブジェクトが動作できなくなるからである。
実際には、この計算はカードにより行われない。何故なら、この計算は長い時間がかかり、個人化段階の速度が遅くなる恐れがあり、またこの個人化の時間の長さがさまざまであり、チップ・カードの個人化方法と両立しないことが分かっているからである。
さらに、この方法は、上記方法の第２の欠点を依然として有している。すなわちメモリ空間を必要とする。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
本発明の目的は、これらの問題を解決することである。
もっと正確に説明すると、本発明の目的は、鍵の生成の管理に関連する計算の複雑さの問題、および個人化段階での多数の鍵および証明書の最初のおよび決定的な記憶による柔軟性の欠如の問題を解決することである。
【課題を解決するための手段】
【００１８】
そのため、本発明の１つの目的は、下記の２つの別々の計算ステップを含むことを主として特徴とする電子デバイスを使用する公開鍵暗号化方法のための電子鍵ｄを生成するための方法に関する。
【００１９】
ステップＡ
１）素数のペア（ｐ，ｑ）または素数のペアを表す値を計算するステップ。この計算は、ｅが公開指数であり、ｌが暗号化方法の鍵の長さであり、また、ｌが上記方法のモジュラスＮの長さでもあるペア（ｅ，ｌ）の知識とは独立して行われる。
２）このようにして得られたペアまたは値を記憶するステップ。
【００２０】
ステップＢ
ステップＡの結果およびペア（ｅ，ｌ）の知識から鍵ｄを計算するステップ。
第１の例の場合には、ステップＡ−１）は、公開指数ｅまたは鍵の長さｌを知らないで、小さな素数の積であるパラメータΠを使用して、素数のペア（ｐ，ｑ）を計算するステップである。この方法の場合、ステップＡにより得られたペア（ｐ，ｑ）は、将来のペア（ｅ，ｌ）に対応することができる最大の確率を有し、ステップＢを実行した場合、鍵ｄを計算することができるようにする。
【００２１】
上記例に依存するもう１つの例の場合には、計算ステップＡ−１）は、また、ｅが組｛３，１７，．．．，２１６＋１｝の一部を形成する高い確率を有し、この使用のために、ペア（ｐ，ｑ）ではなく、ペア（ｐ，ｑ）の画像と呼ばれる表示値を計算することができるようにするシードσのステップＡの計算の際に作成されるという事実も考慮に入れる。
【００２２】
次に、記憶ステップＡ−２）は、この画像を記憶するステップである。そうすることにより、メモリ空間の入手が可能になる。何故なら、例えば、１２８バイトに対する３２バイトのように、画像は素数ｐまたはｑより小さいからである。
第３の例の場合には、ペア（ｐ，ｑ）の計算は、異なる可能性のあるペア（ｅ，ｌ）に対して行われる。実際には、パラメータΠは、例えば、３、１７のようなｅの通常の値を含む。
第４の例の場合には、ステップＡ−１）は、計算したペア（ｐ，ｑ）を圧縮する動作を含み、ステップＡ−２）は、このようにして得られた圧縮した値を記憶するステップである。
【００２３】
ステップＢは、所与のペア（ｅ，∝）に対する下記の条件を確認するステップを含む。
（ｉ）ｐ−１およびｑ−１は、ｅを含む素数であること。
（ｉｉ）Ｎ＝ｐ＊ｑは、長さ∝の整数であること。
ある好ましい実施形態によれば、ステップＡ−１）は、素数ｑの生成、および例えば、Ｂ０＝２５６ビットのように∝０≧Ｂ０になるように、生成対象の素数の長さ∝０に対する下限Ｂ０の選択を含み、また、下記のサブステップを含む。
【００２４】
１）下記の関係からパラメータｖおよびｗを計算し、これらのパラメータを記憶するサブステップ。
【００２５】
【数１】
2005530212.tif 000002
【００２６】
ここで、Πが記憶され、最も小さい素数ｆの積に対応する。ｆはΠ≦２Ｂｏになるように選択される。
２）整数｛ｖ，．．．，ｗ−１｝の範囲内のある数ｊを選択し、∝＝ｊΠを計算するサブステップ。
３）整数｛０，．．．，Π−１｝の範囲内のＲＳＡ鍵の長さより短い素数ｋを選択し、記憶するサブステップ。（ｋ，Π）は相互に素の関係にある。
４）ｑ＝ｋ＋∝を計算するサブステップ。
【００２７】
５）ｑが素数であるかどうかを確認するサブステップ。ｑが素数でない場合には下記のことを行う。
ａ）下記の関係を使用してｋに対する新しい値の選択。
ｋ＝ａｋ（ｍｏｄ  Π）；ａは整数モジュロΠの乗法グループＺ＊πに属する。
ｂ）サブステップ４）からのこの方法の反復。
都合のよいことに、ステップＢは、ステップＡで入手したペア（ｐ，ｑ）および所与のペア（ｅ，ｌ）に対して下記のことを行う。
【００２８】
・下記の条件の確認：
（ｉ）ｐ−１およびｑ−１は、ｅを含む素数であること。
（ｉｉ）Ｎ＝ｐ＊ｑは、長さ∝の整数であること。
・ペア（ｐ，ｑ）がこれらの条件を満足しない場合には：
・他のペアを選択、および適切なペアを発見するまでこの確認の反復。
・この確認の終わりのところで入手したペア（ｐ，ｑ）からの鍵ｄの計算。
【００２９】
本発明は、また、少なくとも下記のものを備えることを特徴とするＲＳＡタイプの暗号化アルゴリズムの電子鍵ｄを生成することができるセキュア・ポータブル・オブジェクトに関する。
・少なくとも１つのペア（ｅ，ｌ）を受信するための通信手段。
・ｅが公開指数であり、ｌが暗号化方法の鍵の長さであり、また、ｌが上記方法のモジュラスＮの長さであるペア（ｅ，ｌ）の知識とは独立して行われる素数のペア（ｐ，ｑ）または素数のペアを表す値を計算するステップからなるステップＡの結果を記憶するためのメモリ。
・ステップＡの結果およびペア（ｅ，ｌ）の知識から鍵ｄを計算するステップからなるステップＢを実施するためのプログラム。
セキュア・ポータブル・オブジェクトは、また、ステップＡを実施するためのプログラムを含む。ステップＡおよびＢは時間の点で独立している。
セキュア・ポータブル・オブジェクトは、チップ・カードであってもよい。
【発明を実施するための最良の形態】
【００３０】
本発明の方法を実行するためのシステムの構成を示す１枚の図面を参照しながら、本発明を制限するものではない下記の説明を読めば、本発明の他の特徴および利点をはっきりと理解することができるだろう。
説明の残りの部分は、チップ・カード・タイプのポータブル・オブジェクトに、本発明を適用する方法を説明している。説明を簡単にするために、以後ポータブル・オブジェクトをチップ・カードと呼ぶ。
【００３１】
本発明の方法によれば、鍵の生成は２つの別々のステップにより行われる。
第１のステップＡは、素数のペア（ｐ，ｑ）または画像と呼ぶ素数のペアを表す値の計算を含む。
入手したペア（ｐ，ｑ）は記憶される。
この計算は複雑であるが、従来の素数生成アルゴリズムを使用した場合にはさらに複雑になる。
本明細書においては、この計算をペア（ｅ，ｌ）の知識から独立して実行するように提案する。
【００３２】
以下に詳細に説明するように、このステップを実行するための１つの好ましい実施形態を使用すれば、計算を簡単にすることができ、これらペアの画像を記憶することにより、入手したペア（ｐ，ｑ）を記憶するために必要なメモリ空間が少なくてすむ。
第２のステップＢは、ステップＡの結果およびペア（ｅ，ｌ）の知識から、鍵ｄに固有な計算を含む。
【００３３】
この計算は、ステップＡで入手したペア（ｐ，ｑ）および所与のペア（ｅ，ｌ）に対する下記のことを含む。
・下記の条件の確認：
（ｉ）ｐ−１およびｑ−１は、ｅを含む素数であること。
（ｉｉ）Ｎ＝ｐ＊ｑは、長さ∝の整数であること。
・ペア（ｐ，ｑ）がこれらの条件を満足しない場合には、他のペアが選択され、ステップＡで入手したペアの中から適切なペアが発見されるまで、上記確認が反復して行われる。
・次に、この確認の終わりのところで入手したペア（ｐ，ｑ）から鍵ｄの計算に進むことができる。
【００３４】
第２のステップと比較した場合比較的複雑な計算に対応する第１のステップは、チップ・カード以外の素子、例えば、サーバにより実行することができる。この場合、この第１のステップの計算結果は、個人化中にチップ・カード上にロードすることができる。
ステップＡの計算は、また、任意の所与の瞬間にカード自身により行うことができ、この計算を行ってもこのカードのユーザに迷惑はかからない。例えば、この計算は、カードの個人化中に行うこともできるし、その後で行うこともできる。
【００３５】
実際には、カードの使用中に、サービスを受けるために、秘密鍵が必要な場合には、秘密鍵を生成するために、（まだカードに記憶していない場合には、おそらく遠隔地から）サービス・プロバイダにより公開鍵が供給される。この生成ステップ（計算ステップＢ）は、カードにより迅速に実行される。
それ故、秘密鍵ｄの計算を必要とする新しいアプリケーションをカードに対して提供することができることを理解することができるだろう。
【００３６】
また、証明書をペア（ｐ，ｑ）に関連づける必要がないことも理解することができるだろう。何故なら、ペアは秘密鍵と関連していないからである。
それ故、秘密鍵の生成は、ボード上ですなわちカード自身により、いままでの鍵生成方法と比較した場合、１／１０の実行時間で実行することができる。
【００３７】
以下の説明においては、ステップＡを実行するための１つの好ましい実施形態について説明する。この実施形態は、チップ・カード上で使用すると特に有利である。何故なら、この実施形態を使用すれば、メモリ空間および計算時間の両方を最適化することができるからである。
【００３８】
最初に、Ｎ＝ｐ＊ｑが確実に∝ビットの整数になるように、ｐが下記範囲内から選択される。
【００３９】
【数２】
2005530212.tif 000003
また、ｑが下記範囲内から選択される。
【００４０】
【数３】
2005530212.tif 000004
【００４１】
∝０の場合には、１と∝の間である。
それ故、ｍｉｎ（ｐ）ｍｉｎ（ｑ）は、２∝０−１とＮの間にあり、ｍａｘ（ｐ）ｍａｘ（ｑ）は、必要に応じてＮと２∝の間にある。
このようにして、上記条件ｉｉ）は、範囲内の素数を探索するだけになる。
【００４２】
【数４】
2005530212.tif 000005
【００４３】
本発明の方法は、パラメータΠを使用する。このパラメータΠは、特に３、１７、２１６＋１を発見することができる小さな素数の積である。上記素数は、通常、公開指数として使用される。それ故、ペア（ｐ，ｑ）が、すでに非常に大きい所与の将来のペア（ｅ，ｌ）に対応する確率は、Πがこのような値を含んでいる場合にはさらに高くなる。
【００４４】
最も小さい素数ｆが選択される。ｆはΠｉｐｉ≦２Ｂ０になるように選択される。Ｂ０は、∝０に対して選択した下限である。例えば、Ｂ０は、２５６ビットに等しくなるように選択することができる。
Πは、積２．３...．．１９１に等しく２２５６より小さい。
次に、この値Πは、例えば、プログラム読み出し専用メモリ内に定数としてカードに記憶することができる。
この方法の第１の段階は、整数｛０，．．．，Π−１｝の範囲内のＲＳＡ鍵の長さより短い長さの素数ｋの生成および記憶である。（ｋ，Π）は、相互に素の関係にある。すなわち、共通因数を有さない。
【００４５】
次に、第２の段階は、この数ｋからの、Πを有する相互に素の関係にあるという条件を満足する第１の候補ｑの生成である。
この第１の候補がこの条件を満足しない場合には、この第１の候補は更新される。すなわち条件を満足するｑの値が発見されるまで、他の候補の選択が行われる。
【００４６】
ここで、本発明によるＲＳＡ鍵の計算の際に使用する素数の生成のためのアルゴリズムの種々のステップについて説明する。
本発明のアルゴリズムは、生成対象の素数ｑに与えられた長さｌｏが何であれ使用することができる。
素数ｐの生成は同じである。展開するステップでｑをｐで置き換え、ｌｏをｌ−ｌｏで置き換えるだけでよい。
制限Ｂ０を設定した後で、下記の条件を満足する一意の素数ｖおよびｗの計算が行われる。
【００４７】
【数５】
2005530212.tif 000006
このことは、下記の関係によりｖおよびｗを計算することを意味する。
【００４８】
【数６】
2005530212.tif 000007
【００４９】
次に、整数モジュロΠの乗法グループＺ＊Πに属するｋを選択した後で、
ｑ＝ｋ＋ｊ（範囲［ｖ,ｗ−１］に属する任意のｊに対して）になるように第１の候補ｑが生成される。
ｋはｚ＊Πと一致するから、素数の第１の候補ｑを得る確率は高い。そうでない場合には、ｋをａｋ（ｍｏｄ  Π）に等しくすることによりｋが更新される。ａはグループｚ＊Πに属し、この方法は、素数に対応するｑの値が発見されるまで反復して行われる。
ある数が素数であるかどうかを試験する１つの方法は、例えば、ラビン−ミラーテスト（Ｒａｂｉｎ−Ｍｉｌｌｅｒ  ｔｅｓｔ）を使用する方法である。
【００５０】
本発明のアルゴリズムの種々のステップについて以下に詳細に説明する。
１）下記の関係からのパラメータｖおよびｗの計算と、これらのパラメータの記憶。
【００５１】
【数７】
2005530212.tif 000008
【００５２】
ここで、Πは記憶され、最も小さい素数ｆの積に対応する。ｆはΠ≦２Ｂｏになるように選択される。
２）整数｛ｖ，．．．，ｗ−１｝の範囲内のある数ｊの選択および∝＝ｊΠの計算。
３）整数｛０，．．．，Π−１｝の範囲内のＲＳＡ鍵の長さより短い素数ｋの選択および記憶。（ｋ，Π）は相互に素の関係にある。
４）ｑ＝ｋ＋∝の計算。
【００５３】
５）ｑが素数であるかどうかの確認。ｑが素数でない場合には、下記のことが行われる。
ａ）下記の関係を使用したｋに対する新しい値の選択。
ｋ＝ａｋ（ｍｏｄ  Π）；ａは整数モジュロΠの乗法グループＺ＊πに属する。
ｂ）ステップ４）からの上記方法の反復。
【００５４】
６）ｑを発見するために使用するためのａ、ｋ’ｊの記録と、その後でのＲＳＡ鍵を生成するための以降の計算の際のｑの使用。
ｑの値を記憶する代わりに、本発明の方法は下記のように有利に進む。
このアルゴリズムを実行するための簡単な方法は、予測したＲＳＡ鍵の各長さに対して、ｑを再生成するためにｋおよびｊの値を記憶することである。
ステップ２）に示す乱数ｊを選択する代わりに、他の実施形態は短い乱数からｊを生成することができる。
例えば、シードと呼ばれる６４ビットの長さを有するある数が選択され、σで示される。次に、このシードは、ｊの生成を可能にする疑似乱数発生器ＰＲＮＧの入力値として選択される。
【００５５】
次に、ｊがＰＲＮＧ１（σ）（ｍｏｄ（ｗ−ｖ）＋ｖ）として定義される。
この実施形態を使用すれば、メモリ空間の要件をかなり軽減することができる。何故なら、σおよびｋの値だけをＥＥＰＲＯＭメモリに記憶するだけでよいからである。Πの値は、（計算プログラム内の）読み出し専用メモリに記憶されている。
【００５６】
ｋ（ｏ）がグループｚ＊Πに属するｋの第１の値である場合には、生成した素数は、下記の形を有するということを認識することにより、メモリ空間の要件をさらに軽減することができる。
ｑ＝ａｆ−１ｋ（ｏ）ｍｏｄ  Π＋ｊΠ
ｆは、ステップ４）での試験の失敗の回数である。
【００５７】
グループｚ＊Πに属するこの値ｋ（ｏ）は、例えば、σのような短いランダム・シードから、λ（Π）と呼ばれるΠ２のカーマイケル関数を使用して容易に計算することができる。
この関数を使用することにより、下記の関係からｋ（ｏ）を表すことができる。
ｋ（ｏ）＝［ＰＲＮＧ２（σ）＋ｂＰＲＮＧ３（σ）（ＰＲＮＧ２（σ）λ（Π）−１）］（ｍｏｄΠ）
ｂは、ｚ×Πに属する位数λ（Π）の要素である。
【００５８】
これら２つの実施形態を使用すれば、メモリ空間の要件を軽減することができる。何故なら、この場合、シードσの値および所望の鍵の長さに対するｆの種々の値を記憶するだけでよいからである。
【００５９】
２０４８ビットより大きいモジュラスを有するＲＳＡ鍵の場合には、本発明者が行った数値による実験によりｆが２８に等しいことが分かった。このことは、ｆが１バイト、すなわち８オクテット上でコード化することができることを意味する。
【００６０】
例を挙げて説明すると、３２ビットの粒度を有する５１２乃至２０４８ビットの範囲内の長さのＲＳＡ鍵を生成するには、４９の可能な鍵の長さがある。それ故、カード上にσの値に対応する１ビット、すなわち８オクテットを記憶する必要がある。また、素数ｐおよびｑに対するｆの値、すなわち、２＊４９＝９８オクテットを記憶する必要がある。それ故、ＥＥＰＲＯＭメモリ内の全数は１０６バイト、すなわち８４８ビットになる。
【００６１】
メモリ空間を軽減することができる最後の実施形態は、計算プログラム、すなわち、プログラム・メモリ内に、種々の予測した鍵の長さに対する多数のΠの値およびλ（Π）の対応する値を記憶する。Πの値が大きいと、ｆに対する最小の値になることに気が付くことができるだろう。
【００６２】
すでに説明したように、今説明したばかりのアルゴリズムにより、ステップ４）により生成した素数ｑは下記の条件を満足する。
ｑ＝ａｆ−１ｋ（ｏ）ｍｏｄΠ＋ｊ＊Π
ｅでΠを割った場合、ｑを下式で表すことができる。
ｑ＝ａｆ−１ｋ（ｏ）ｍｏｄ（ｅ）
説明の冒頭で説明した条件（ｉ）を満足するために、ａはａ＝１（ｍｏｄ  ｅ）になるように選択しなければならないし、ｋは１（ｍｏｄ  ｅ）と強制的に異なるようにしなければならない。
【００６３】
このように入手した素数ｑは、１（ｍｏｄ  ｅ）とは異なる式ｑ＝ｋ（ｏ）を満足する。
素数ｐの生成は、展開され、ｌｏがｌ−ｌｏで置き換えられるステップでｑがｐにより置き換えられる点を除けば同じである。
すでに説明したように、カードの方法を実施するプログラムは、公開指数ｅを予め知る必要はない。それ故、この指数はカードにロードしたアプリケーションにより任意の瞬間に供給することができる。
【００６４】
しかし、大部分（９５％以上）のアプリケーションの場合、使用するｅの値は値｛３，１７，２１６＋１｝であることが分かっている。
最大の数のアプリケーションをカバーするために、好適には、ａ＝１ｍｏｄ（｛３，１７，２１６＋１｝）になるように選択することが好ましく、ｋ（ｏ）は、この値、すなわち、１ｍｏｄ（｛３，１７，２１６＋１｝）と異なるものでなければならない。
【００６５】
例えば、素数Ｒ＝２６４−２３２＋１は、ΠおよびＲの最大公約数が１に等しいという条件付きで、ａの可能な候補として選択される。
ｋ（ｏ）に対する必要な条件は、中国人剰余定理（Ｃｈｉｎｅｓｅ  Ｒｅｍａｉｎｄｅｒ  Ｔｈｅｏｒｅｍ）により入手することができる。
すでに説明したように、別の方法は、ステップＡ−１）の時点で、種々の可能なペア（ｅ，ｌ）に対する素数（ｐ，ｑ）のペアを計算する。
【００６６】
終わりに、本発明は、２つの別々のステップからなる方法を提案する。この場合、周知の方法と比較すると非常に迅速な第２のステップは、リアルタイムで実行することができる。この方法は、また、比較的小さな容量のメモリ空間を使用するだけですむ。
さらに、カードの個人化の時点で供給されない新しいアプリケーションの点で制限がない。
【図面の簡単な説明】
【００６７】
【図１】本発明の方法を実行するためのシステムの構成を示す図面である。
【図１】
2005530212.tif 000011
【国際調査報告】
2005530212.tif 000012
2005530212.tif 000013
2005530212.tif 000014
2005530212.tif 000015
2005530212.tif 000016
2005530212.tif 000017