(57)【要約】本発明は、とりわけ、一定の正の整数の区間［ｗｍ、ｗＭ］内に含まれる素数ｑから電子キーを生成する方法であって、主に、素数ｑが以下の演算を行うことによって得られることを特徴とする方法を対象とする。ａ）εｍがｗｍ／ηの大きな概数で、εＭは（ｗＭ−ｗｍ）／ηが小さな概数であるような、２つの正の素数εｍ及びεＭが存在するために、ｋを最大値とし、ηを最初のｋ個の素数の積であるとする、正の整数ηの選択。Π＝εＭ・η及びρ＝εｍ・ηの計算。ｃをΠをともなう素数とすると、モジュロ整数Πの乗法群Ｚ＊Πに属する正の整数ａ及びｃの生成ｑ＝ｃ＋ρの計算するｂ）ｑの一次性のテストｃ）一次性が検証された場合にｑを記憶するｄ）そうでない場合には：ａ．ｃ ｍｏｄ　Πを計算することでｃを修正する。新しい値ｑ＝ｃ＋ρによって、前記の演算をｂ）から繰り返す。本発明は暗号解読法に適用できる。【選択図】図２
2004502984.tif 000002
【特許請求の範囲】
【請求項１】
一定の正の整数の区間［ｗｍ，ｗＭ］内に含まれる素数ｑから電子キーを生成する方法であって、素数ｑが以下の演算を実施することによって得られる方法。
ａ）εｍ がｗｍ／ηの大きな概数で、εＭ が（ｗＭ−ｗｍ）／ηの小さな概数であるような、２つの正の整数εｍ 及びεＭ が存在するために、ｋを最大値とし、ηを最初のｋ個の素数の積とする、正の整数ηを選択する。
Π＝εＭ・η 及び ρ＝εｍ・η を計算する。
ｃをΠをともなう素数として、モジュロ整数Πの乗法群Ｚ＊Π に属する正の整数ａ及びｃ を生成する。
ｑ＝ｃ＋ρを計算する。
ｂ）ｑの一次性をテストする。
ｃ）一次性が検証された場合には、ｑを記憶する。
ｄ）そうでない場合には：ａ．ｃ ｍｏｄ Π を計算することでｃを修正する。
新しい値ｑ＝ｃ＋ρによって、前記の演算をｂ）から繰り返す。
【請求項２】
請求項１に記載の方法において、
ａ＝２ 及び Π＝（εＭ−１）・η である、ことを特徴とする方法。
【請求項３】
請求項１に記載の方法において、
ａ＝２１６＋１である、ことを特徴とする方法。
【請求項４】
請求項１から３のいずれか一項に記載の方法において、
この方法は、ＲＳＡ、Ｅｌ Ｇａｍａｌ、Ｓｃｈｎｏｒｒ、またはＦｉａｔ Ｓｈａｍｉｒのいずれかによる暗号キー生成方法に適用される、ことを特徴とする方法。
【請求項５】
モジュラ計算を行うことができる、算術プロセッサと関連プログラムメモリを備える電子装置であって、主に、以下の演算を行う、一定の正の整数の区間［Ｗｍ，ＷＭ］内に含まれる正の整数の一次性の検証プログラムを有する、ことを特徴とする装置。
ａ）εｍ がｗｍ／ηの大きな概数で、εＭ が（ｗＭ−ｗｍ）／ηの小さな概数であるような、２つの正の素数εｍ 及びεＭ が存在するために、ｋを最大値とし、ηを最初のｋ個の素数の積とする、正の整数ηを選択する。
Π＝εＭ・η 及び ρ＝εｍ・η を計算する。
ｃをΠをともなう素数とすると、モジュロ整数Πの乗法群Ｚ＊Π に属する２つの正の整数（ａ及びｃ）を生成する。
ｑ＝ｃ＋ρを計算する。
ｂ）ｑの一次性をテストする。
ｃ）一次性が検証された場合には、算術プロセッサがｑを保存する。
ｄ）そうでない場合には：ａ．ｃ ｍｏｄ Π を計算することでｃを修正する。
算術プロセッサが、ｑ＝ｃ＋ρによって、前記の演算をｂ）から繰り返す。
【請求項６】
請求項５に記載の装置において、
この装置はマイクロプロセッサ付チップカードによって構成される、ことを特徴とする装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一定の正の整数の区間［ｗｍ、ｗＭ］　に含まれる素数ｑから電子キーを生成する方法に関するものである。本発明はまた、この方法を実施する装置に関するものである。
本発明は、とりわけ、情報の暗号化及び／または２つのエンティティ間の認証及び／またはメッセージの電子シグネーチャのために使用される公開キーによる暗号プロトコルに適用される。
本発明は、特に、ＲＳＡ（Ｒｉｖｅｓｔ Ｓａｈｍｉｒ ＆ Ａｄｅｌｍａｎ）、Ｅｌ Ｇａｍａｌ、ＳｃｈｎｏｒｒまたはＦｉａｔ Ｓｈａｍｉｒプロトコルのような公開キー（鍵）による暗号解読技術に適用される。
【０００２】
【従来の技術】
このような適用の場合には、一つまたは複数のプロトコルのキーを形成するためには、大きな素数（たとえば５１２ビット以上とすることができる）の生成に頼っている。
素数の生成の「素朴な」第一の方法は、以下からなる。
−奇数から候補を選ぶ、
−その一次性をテストする、
−一次性が検証された場合には、その数が記憶され、そうでない場合には、その候補を２だけ増分することによって修正し、その新しい候補でテストを繰り返し、候補の一次性が検証されるまで以下同様に続ける。
【０００３】
この方法はとても時間がかかる。他の方法は、素数Πをともなう素数の中から一次性のテストの候補を選択するというものがある。２つの数は、その最大公約数（ｐｇｃｄ）が１である場合、また１である場合にのみ、互いに素であることまたは共素数であることを思い起こされたい。
【０００４】
この方法は以下からなる：
−ｋ個の最初の素数（多くの場合ｋ＝４）の積である数 Π＝２，３，５，７，・・・を対象として、Πをともなう素数ｐのような数ｐを選択する。
−ｐの一次性をテストする。
−ｐの一次性が検証されたら、この数を記憶する、そうでなければΠだけ増分させながらｐを修正する。この新しい候補ｐはまたΠをともなう素数である。実際に、以下が思い起こされる。
ｐｇｃｄ（ｐ＋Π，Π）＝ｐｇｃｄ（ｐ，Π）＝１
−この新しい候補でテストを繰り返し、素数である候補が見つかるまで以下同様に続ける。
この方法はより効果的である。
【０００５】
【発明が解決しようとする課題】
しかしながら、一般に、一定の区間内で素数を生成することが望ましい。というのも、たとえばＲＳＡ公開キーによる暗号プロトコルの場合には、２つの素数ｐ及びｑの１０２４ビットの積、すなわち ２５１１・√２＜ｐ，ｑ＜２５１２ が対象となる。離散ロガリズムに基づく他のプロトコルによれば、１０２４ビットの素数、すなわち ２１０２３＜ｐ＜＝２１０２４ を直接的に得ようとする。これらのプロトコルは、５１２ビット、さらには１０２４ビット、またはそれ以上の、通常の大きな規模の数については、性能があまり良くないし、マイクロプロセッサ付カード型の携帯装置でプログラミングするのは難しい。なぜなら複雑だからである。
【０００６】
【課題を解決するための手段】
本発明は、区間を［ｗｍ、ｗＭ］として、すべてに対していったんΠを決定し、候補の修正を提案し、その結果、新しい候補が、妥当な限界値内で、すなわち一次性のテスト数を限定しながら、これら新しい候補の計算時間を保ちながらも、当初に決定した区間内でΠと素の関係になるように保証することを目的とする。
Πの選択は図１に示されているが、ここには区間［ｗｍ、ｗＭ］内に含まれる整数の集合Ｉが示され、Πと素の関係にあるこの区間の整数の集合ＩΠが含まれ、この区間の素数の集合ＩＰが含まれる。その目的は、Πをともなう素整数の中間集合ＩΠ、すなわち候補の集合が、この区間の素数の小集合ＩＰにできるだけ近くなるように、Πを決定することにある。
【０００７】
本発明は、とりわけ、一定の正の整数の区間［ｗｍ、ｗＭ］内に含まれる素数ｑから電子キー（電子鍵）を生成する方法であって、主に、素数ｑが以下の演算を行うことによって得られることを特徴とする方法を対象とする。
ａ）εｍがｗｍ／ηの大きな概数（ｈｉｇｈｅｒ ｒｏｕｎｄｏｆｆ）で、εＭが（ｗＭ−ｗｍ）／ηの小さな概数（ｌｏｗｅｒ ｒｏｕｎｄｏｆｆ）であるような、２つの正の整数εｍ及びεＭが存在するために、ｋを最大値とし、ηを最初のｋ個の素数の積とする、正の整数ηを選択する。
Π＝εＭ・η 及び ρ＝εｍ・η の計算。
ｃをΠをともなう素数とすると、モジュロ整数Πの乗法群Ｚ＊Πに属する正の２つの整数ａ及びｃの生成。
ｑ＝ｃ＋ρ の計算。
ｂ）ｑの一次性のテスト
ｃ）一次性が検証された場合にｑを記憶する。
ｄ）そうでない場合には：
ａ．ｃ ｍｏｄ Π を計算することでｃを修正する。
新しい値ｑ＝ｃ＋ρ によって、前記の演算をｂ）から繰り返す。
【０００８】
本発明の特徴によれば、ａ＝２ 及び Π＝（εＭ−１）・η である。
他の特徴によればａ＝２１６＋１ である。
本発明は、ＲＳＡ、Ｅｌ Ｇａｍａｌ、ＳｃｈｎｏｒｒまたはＦｉａｔ Ｓｈａｍｉｒ暗号キーの生成方法に実施されて適用することができ、暗号解読法として利用できる。
【０００９】
本発明はまた、モジュラ計算を行うことができる、関連プログラムのメモリと算術プロセッサを備える携帯電子装置であって、主に、以下の演算を行う一定の正の整数の区間［ｗｍ，ｗＭ］内に含まれる正の整数の一次性の検証プログラムを有することを特徴とする装置を対象とする。
ａ）εｍがｗｍ／ηの大きな概数で、εＭが（ｗＭ−ｗｍ）／ηの小さな概数であるような、２つの正の素数εｍ及びεＭが存在するために、ｋを最大値とし、ηを最初のｋ個の素数の積とする、正の整数ηの選択。
Π＝εＭ・η 及び ρ＝εｍ・ηの計算。
ｃをΠをともなう素数すると、モジュロ整数Πの乗法群Ｚ＊Πに属する２つの正の整数ａ及びｃの生成。
ｑ＝ｃ＋ρの計算。
ｂ）ｑの一次性のテスト。
ｃ）一次性が検証された場合には、算術プロセッサがｑを保存する
ｄ）そうでない場合には：
ａ．ｃ ｍｏｄ Π を計算することでｃを修正する。
算術プロセッサが、ｑ＝ｃ＋ρ によって、前記の演算をｂ）から繰り返す。
そしてより有利な形態としては、携帯電子装置は、マイクロプロセッサ付チップカードによって構成されるとよい。
【００１０】
【発明の実施の形態】
添付の図面１〜３を参照して、以下に限定的でない例として説明することで、本発明の他の特徴及び利点が明らかになるだろう。
図１は、区間［ｗｍ、ｗＭ］内に含まれる整数の集合Ｉと、互いに素のｋの区間の整数の集合ＩΠと、さらにこの区間の素数の集合ＩＰを示す図である。
図２は、本発明による方法のフローチャートである。
図３は、本発明による方法を実施するためのチップカードのような携帯電子装置の原理図である。
【００１１】
本発明の目的は、まず第一に、図１に示されているΠをともなう素数の集合ＩΠが、区間の素数の小集合ＩＰにできるだけ近くなるように、Πを決定することにある。
本発明によれば、図２に示されている方法は、以下の方法で初期化される（第１段階）。
ｑ ∈［ｗｍ、ｗＭ］のような素数ｑを生成するために、
εｍ は ｗｍ／ηの大きな概数で、□ｗｍ／η□と記され、εＭ は（ｗＭ−ｗｍ）／ηの小さな概数で、□（ｗＭ−ｗｍ）／η□ と記されるような２つの正の整数εｍ 及びεＭ が存在するために、ｋ’を最大値として、２つの正の整数Πと同じ形態の数ηを選択する（ηはｋ’個の最初の素数の積である）。
【００１２】
こうして、Π＝εＭ・η とすることで Π が得られ、さらに ρ＝εｍ・η となる。
Πは、ｗＭ−ｗｍ の近似値だが ｗＭ−ｗｍ より小さく、ρは ｗｍの近似値だが ｗｍ より大きい。
ここで、新しい候補が常にＩΠに属するように、候補の修正を決定しなければならない。
モジュロ整数Πの環をＺΠ とし、ＺΠの乗法群をＺ＊Π とする。ここで、集合（ρ＋Ｚ＊Π）は、ＩΠ内に含まれ、ＩΠとほぼ等しくなり、すなわち候補の集合とほぼ等しくなる点が留意される。
【００１３】
こうして、この乗法群Ｚ＊Π に属する２つの正の整数ａ及びｃが生成され、この場合、ｃはΠをともなう素数であり（すなわちｐｇｃｄ（ｃ，Π）＝１）、候補ｑ＝ｃ＋ρと見なされる（第１段階）。ｃを生成するためには、関連文献に記載されているような共素数の生成アルゴリズムが使用される。
ρはｗｍ の近似値で、ｃ＜Πであることから、自動的にｗｍ＜ｑ＜ｗＭ であることが検証される。
さらに、ｐｇｃｄ（ｑ，Π）＝ｐｇｃｄ（ｃ＋ρ，Π）＝ｐｇｃｄ（ｃ，Π）＝１ である。このようにして、ｑは実際にＩΠに属することが検証される。
【００１４】
この初期化段階が終わると、候補ｑの一次性がテストされる（第２段階）。それが検証されるとｑが記憶される。そうでない場合には、ａ．ｃ ｍｏｄ Π を計算することよってｃを修正し、新しい候補ｑ＝ｃ＋ρを計算する（第３段階）。
新しい候補は、集合ＩΠに属する。とういのも、乗法群の特性によって、ａ及びｃはＺ＊Π に属し、積ａ．ｃはまたこの群Ｚ＊Π ならびにａ．ｃ ｍｏｄ Π に属するからである。
【００１５】
公開キーによる暗号プロトコルは、多くの場合、マイクロプロセッサ付チップカード上で使用される。たとえばＲＳＡプロトコルにおいては、キー（鍵）は、プロトコル実行中にマイクロプロセッサ付カードによってアトランダムに選択された数から生成される。そのために、マイクロプロセッサ付カードは、必要な規模の整数を与えることができる、乱数の生成装置を有する。
したがって、図３には、本発明による方法を実施することができるマイクロプロセッサ付カードのフローチャートが示されている。
【００１６】
カードＣは、処理用メインユニット１と、ユニット１に連結されたプログラムメモリ３及び４と、作業メモリ（ここには記されていない）を備える。このカードはまた、モジュラ計算を行うことができる算術プロセッサ２と、一次性が検証された候補ｑが保存される安全化メモリ６（外部からはアクセスできない）を備える。このカードは、さらに、乱整数の生成装置５を有する。
とりわけ、上述したようなマイクロプロセッサカードでこの方法が実施されることを考慮すると、この方法によって実施される処理（算術プロセッサ２によって実施される演算）の速度を高め、作業メモリ内の場所を解放することが望ましい。
【００１７】
その目的で、ａ＝２を選択し、数Πから２を除外することによって（Π＝３，５，７，・・・）、モジュラ計算をしないで済ますことができる。実際、ｃの修正は２ｃ ｍｏｄ Π となる。ところが、ｃはＺ＊Π の要素であるから、２ｃ ｍｏｄ Π＝２ｃまたは２ｃ−Πとなる。
しかし、このとき、新しい候補ｑは偶数である可能性もある。その場合には、新しい候補が常に集合ＩΠに属しながらも奇数になるような数をその新しい候補に加える。こうして、以下のようになる。
Π＝（εＭ−１）・η
ｑ＝ｃ＋ρ
ｑが偶数である場合には、ｑはｑ＋ηとなる。
別の代案によれば、最初に定義したようなΠをそのままにし、ａがΠをともなう素数となるようなａの独自の値を選択することもできる。たとえば、ａ＝２１６＋１を選択することができる。
【００１８】
本発明による方法は、８ビットのＣＰＵと１１００ビットの暗号プロセッサを備えたＩｎｆｅｎｅｏｎのチップカードＳＬＥ６６ＣＸ１６０Ｓのプラットフォームで実施された。ηとΠとρについては、以下の値が選択された。
η＝ｂ１６ｂｄ１ｅ０８４ａｆ６２８ｆｅ５０８９ｅ６ｄａｂｄ１６ｂ５ｂ８０ｆ６０６８１ｄ６ａ０９２ｆｃｂｌｅ８６ｄ８２８７６ｅｄ７１９２１０００ｂｃｆｄｄ０６３ｆｂ９０ｆ８１ｄｆｄ０７ａ０２１ａｆ２３ｃ７３５ｄ５２ｅ６３ｂｄ１ｃｂ５９ｃ９３ｃｂｂ３９８ａｆｄ１６，
Π＝１７２９・η
ρ＝４１８０・η
ａ＝２とすると、４秒以内に５１２ビットの素数が得られる。したがって、平均して８秒以内に１０２４ビットの素数を得ることができる。
【図面の簡単な説明】
【図１】区間［ｗｍ、ｗＭ］内に含まれる整数の集合Ｉと、互いに素のｋの区間の整数の集合ＩΠと、さらにこの区間の素数の集合ＩＰを示す図である。
【図２】本発明による方法のフローチャートである。
【図３】本発明による方法を実施するためのチップカードのような携帯電子装置の原理図である。
【図１】
2004502984.tif 000003
【図２】
2004502984.tif 000004
【図３】
2004502984.tif 000005
【国際公開パンフレット】
2004502984.tif 000006
2004502984.tif 000007
2004502984.tif 000008
2004502984.tif 000009
2004502984.tif 000010
2004502984.tif 000011
2004502984.tif 000012
2004502984.tif 000013
2004502984.tif 000014
2004502984.tif 000015
2004502984.tif 000016
2004502984.tif 000017
2004502984.tif 000018
2004502984.tif 000019
2004502984.tif 000020
2004502984.tif 000021
2004502984.tif 000022
【国際調査報告】
2004502984.tif 000023
2004502984.tif 000024