ＲＳＡアルゴリズムにおける素数生成の保護
【課題】本発明は、例えば、電子回路の電力消費の分析等によるサイドチャネル攻撃、又は故障注入攻撃から電子回路における素数の生成を保護する方法を提供する。
【解決手段】連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護する方法において、前記候補数毎に、少なくとも１つの第１の乱数を含む参照数を計算し、累乗モジュールの計算に基づく少なくとも１つの素数判定を行い、前記素数判定により素数であると判定された候補数毎に、前記候補数と前記参照数との間の無矛盾性を判定する。
【解決手段】連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護する方法において、前記候補数毎に、少なくとも１つの第１の乱数を含む参照数を計算し、累乗モジュールの計算に基づく少なくとも１つの素数判定を行い、前記素数判定により素数であると判定された候補数毎に、前記候補数と前記参照数との間の無矛盾性を判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には電子回路に関し、具体的にはRSA タイプの非対称暗号化アルゴリズムを実行する電子回路に関する。本発明は、より具体的には、例えば、電子回路の電力消費の統計的分析（SPA-単純な電力分析）若しくは電子署名の統計的分析によるサイドチャネル攻撃又は故障注入攻撃に対する、電子回路における素数の生成中の保護に関する。
【０００２】
本発明は、素因数分解を用いたアルゴリズムを利用したあらゆる電子回路に適用され、具体的にはチップカードに適用される。
【背景技術】
【０００３】
RSA アルゴリズムは、最も一般的に使用される（公開鍵を備えた）非対称暗号化アルゴリズムの内の１つである。RSA アルゴリズムは、データを暗号化／復号するために、又はデータに署名してデータの認証を可能にするために用いられる。RSA アルゴリズムは、公開鍵及び秘密鍵である１対の鍵の使用に基づいている。暗号化／復号モードでは、公開鍵は、受信者に機密に通信されるべき暗号データのために送信者によって用いられており、受信者は、データを復号するためにプライベートキー、すなわち秘密鍵を用いる。認証のために、秘密鍵がデータに署名するために送信者によって使用される一方、公開鍵は署名を認証するために受信者によって用いられる。
【０００４】
送信者による暗号データの利用を可能にし、受信者による署名されたデータの利用を可能にするために、公開鍵は相対的に広くアクセス可能である。しかしながら、秘密鍵は、一対の鍵を生成した電子回路に保持されている。相手先にデータの処理を可能にさせるために、一対の鍵の保持者が相手先に公開鍵を直接伝送されてもよい。
【０００５】
一対の公開鍵及び秘密鍵を生成するために、相対的に大きなサイズ（一般的には、1,024 ビット又は2,048 ビット）の互いに異なる２つの素数「p 」及び「q 」の使用が必要となる。これらの素数p,q の積が、暗号化係数「n 」を表わす。数p-1 及び数q-1 が公開指数と呼ばれる数「e 」と素であるように、素数p 及び素数q が選択されており、そのため、公開指数「e 」は積n (φ(n) = (p-1)(q-1)) のオイラー関数「φ(n)」と素である。その結果、積e*d がφ(n)を法とした１と合同であるような整数「d 」が存在する。一対の暗号化係数n 及び数d が秘密鍵を表している一方、一対の暗号化係数n 及び公開指数e は公開鍵を表わす。秘密指数d は、(p-1)(q-1)を法とした公開指数e の逆数を表わす。素数p 及び素数q は、秘密鍵を含む電子回路にのみ存在する。
【０００６】
RSA アルゴリズムの頑強性は、素数p 及び素数q により決まる。公開鍵に基づいたRSA アルゴリズムを「解読する」ためには、暗号化係数n を因数分解し、それによって素数p 及び素数q を得ることが可能である必要がある。この因数分解が知られると、秘密指数d は公開指数e から計算され得る（秘密指数d は、(p-1)(q-1)を法とした公開指数e の逆数を計算することにより得られる）。現在、十分なサイズ（一般的には約1,500 ビット程度）の暗号化係数n を用いることにより、現在のアルゴリズムでは、適当な時間内での暗号化係数n の因数分解は不可能になるとみなされている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００３−９１２３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、素数p 及び素数q の電子回路への導入又は電子回路によるこれらの素数p,q の生成が、ハッカーにより発見されると、ハッカーに暗号化係数n の因数分解を提供することになるので、セキュリティの点で特に重要である。
【０００９】
RSA 鍵を生成するための第１の技術は、電子回路の外部でこれらの鍵を生成することを含んでいる。素数p 及び素数q は、カスタマイズ段階で電子回路に導入される。これらの鍵が実際の電子回路によって生成されないので、この技術は故障注入攻撃に反応しない。
【００１０】
公知である第２の技術は、安全な環境（実際には確保されたアクセスを有する保護された装置）で実際の電子回路に素数を生成させることを含んでいる。この技術では、攻撃は、素数生成中問題ではない。
【００１１】
しかしながら、電子回路がこのような安全な環境の外側でRSA 鍵を生成可能であることがますます求められている。これにより、例えば、今までの鍵が否認された場合（鍵のハッキングが想定される場合）に新たな鍵を再生することが可能になる。このような新たな鍵の生成は、例えば、安全ではない環境で電子回路をカスタマイズする際、又は（例えば、署名計算に使用される電子回路若しくは電子識別装置を）初めて使用する際に行われる。電子パスポートへの適用例によれば、パスポートが一度保持者の側に渡ると、鍵はパスポートに含まれる電子チップによって生成されることが求められる。従って、このような鍵は、パスポートの認証手続で予め使用されることは不可能である。
【００１２】
公開指数e は、公開鍵基盤(PKI) のパラメータであってもよく、全ての鍵に対して同一である。公開指数e は、例えば、（ROM 内の）電子回路の製造中、又は（EEPROM内の）電子回路のカスタマイズ段階中に電子回路に導入される。
【００１３】
公開指数e も、例えば、乱数を選択することにより電子回路によって生成されてもよく、その後、電子回路が通信する必要がある要素に伝送されてもよい。
【００１４】
従って、公開鍵（公開指数e 及び暗号化係数n ）は、受信者（署名）若しくは送信者（暗号化）により知られているか、又は秘密鍵を保持する電子回路によって（処理毎に一度だけ）受信者若しくは送信者に伝送される。公開鍵は、更に一般的には認証される必要がある。
【００１５】
大きな素数の生成は、時間及び計算の点でコストがかかる。特に、ある数が素数特性を有するか否かを判定することが可能ないわゆる素数判定法（例えば、いわゆるミラー−ラビン素数判定法）が、一般的には、著しい量の計算を必要とする累乗モジュールを実行する。これは、比較的小さな素数で既に素数であると判定された候補数に対してのみこのような判定を行なうことが求められているためである。このような判定は、比較的小さな素数での除算、又は素数表との比較に対応する。例えば、ミラー−ラビン素数判定法は小さな基数（例えば、２）で行われることが可能であり、又は最大公約数の計算が行なわれてもよい（例えば、255 を法としたバイトを加算し、255 未満の結果を得て、次に、この結果と255 との最大公約数を計算し、計算した最大公約数が１とは異なる場合、一度の判定により、その数が255 の３つの因数、すなわち３，５及び１７で割り切れないことが分かる）。
【００１６】
素数が安全ではない環境で電子回路によって生成される場合、電子回路は、入出力若しくは電子回路の電力消費の分析を利用した故障注入攻撃（電源妨害、レーザー攻撃等）を受けるか、又はサイドチャネル攻撃（SPA 若しくはDPA 又は電磁気分析）を受ける可能性が高い。
【００１７】
電子回路による素数の生成の別の危険性は、最終的に選択された素数を修正しようとする攻撃である。ミラー−ラビン素数判定法の終わりでの攻撃は、アルゴリズムによって考慮された素数を修正するために使用される場合がある。素数p 又は素数q の内の一方が素でない場合、暗号化係数n は因数分解し易く、RSA アルゴリズムのセキュリティを低下させる。
【００１８】
前記素数がこのような鍵を利用する電子回路によって生成されるとき、素数の生成、ひいては、素因数分解を用いたアルゴリズムの鍵の生成を保護することが求められる。
【００１９】
素数生成処理によって与えられる素数の修正を検出することが可能であることを更に求められる。
【００２０】
素数生成を隠蔽することが可能であることが更に求められる。
【課題を解決するための手段】
【００２１】
これらの目的及び他の目的の全て又は一部を達成するために、本発明は、連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護する方法において、
前記候補数毎に、
少なくとも１つの乱数を含む参照数を計算し、
累乗モジュールの計算に基づく少なくとも１つの素数判定を行い、
該素数判定により素数であると判定された候補数毎に、
該候補数と前記参照数との間の無矛盾性を判定することを特徴とする方法を提供する。
【００２２】
本発明の実施形態によれば、前記参照数は、前記乱数に応じた数を前記候補数に加えるか又は前記乱数に応じた数を前記候補数から減じることにより得られる。
【００２３】
本発明の実施形態によれば、前記累乗モジュールの計算に基づく素数判定の前に、前記各候補数に対して、第１の閾値と第２の閾値との間の素数と同数の要素を備えるふるい分けテーブルに基づく少なくとも１つの素数判定が行われ、第１の候補数が、前記第１の閾値以下の素数の第１の積と任意の数とを掛けることにより得られる。
【００２４】
本発明の実施形態によれば、一候補数から次の候補数へ移る際、現在の候補数及び参照数に、前記第１の積を夫々加える。
【００２５】
本発明の実施形態によれば、一候補数から次の候補数へ移る際、前記第１の積の乗算の結果を現在の候補数及び参照数に夫々加え、前記乗数は、前記第１の閾値と第２の閾値との間の素数の第２の積と、少なくとも１つの乱数との関数である。
【００２６】
本発明の実施形態によれば、前記乗数は、更に、RSA アルゴリズムの公開指数の関数である。
【００２７】
本発明の実施形態によれば、前記ふるい分けテーブルは、前記参照数に基づいている。
【００２８】
本発明の実施形態によれば、前記ふるい分けテーブルは、例えば新しい候補数毎に、関連した要素を法とした前記第１の積を前記ふるい分けテーブルの要素に夫々加えることにより更新される。
【００２９】
本発明の実施形態によれば、前記累乗モジュールの計算に基づく素数判定の前に、各候補数に対して、RSA アルゴリズムの公開指数と整合するか否かの判定が行われる。
【００３０】
本発明の実施形態によれば、前記累乗モジュールの計算に基づく素数判定は、ミラー−ラビン判定である。
【００３１】
本発明は、更に、上述された方法を実現するための手段を備えた電子回路を提供する。
【００３２】
本発明は、更に、連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護する方法において、
前記候補数毎に、
前記電子回路の計算部が、少なくとも１つの乱数を含む参照数を計算し、
前記電子回路の判定部が、累乗モジュールの計算に基づく少なくとも１つの素数判定を行い、
前記判定部は、該素数判定により素数であると判定された候補数毎に、該候補数と前記参照数との間の無矛盾性を判定することを特徴とする方法を提供する。
【００３３】
本発明は、更に、連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護するシステムにおいて、
前記候補数毎に、少なくとも１つの乱数を含む参照数を計算する計算部と、
前記候補数毎に、累乗モジュールの計算に基づく少なくとも１つの素数判定を行う判定部とを備え、
前記判定部は、該素数判定により素数であると判定された候補数毎に、該候補数と前記参照数との間の無矛盾性を判定することを特徴とするシステムを提供する。
【００３４】
本発明の前述及び他の目的、特徴及び利点を、添付図面を参照して本発明を限定するものではない特定の実施形態について以下に詳細に説明する。
【図面の簡単な説明】
【００３５】
【図１】本発明が実施例として適用されるタイプの電子回路の実施形態を示すブロック図である。
【図２Ａ】RSA アルゴリズムによる暗号化を非常に概略的に示す図である。
【図２Ｂ】RSA アルゴリズムによる復号を概略的に示す図である。
【図３】暗号化されたデータの伝送システムを示すブロック図である。
【図４】RSA タイプのアルゴリズムを実行する電子回路内で素数を生成する通常のステップを示すフローチャートである。
【図５】本実施形態に係る素数生成法のステップを示すフローチャートである。
【図６】素数生成法の別の実施形態を部分的に示すフローチャートである。
【発明を実施するための形態】
【００３６】
明瞭化のために、同一の要素は異なる図面において同一の参照番号で示されている。更に、本発明の理解に有用なステップ及び要素のみが示され、説明されている。特に、素数に基づく鍵を用いたアルゴリズムに関する電子回路によりどのような利用がなされるのかは詳述されておらず、本発明は、生成された素数のあらゆる通常の利用（暗号化及び署名計算）に適合する。
【００３７】
本発明は、暗号化／復号に用いられるRSA アルゴリズムへの適用例に関連して以下に説明される。しかしながら、本発明は、生成された素数に基づくRSA アルゴリズムを用いたあらゆる利用法にも適用されるものとする。本発明は、特にRSA 署名に適用される。更に一般的には、本発明は、素因数分解により決まる鍵を有するあらゆるアルゴリズム、例えばいわゆるラビン暗号システムに適用される。
【００３８】
図１は、本発明が適用されるタイプの電子回路1 （例えばスマートカード）の例をブロック形式で非常に概略的に示す。このような電子回路1 は、一又は複数のデータ、アドレス及び制御バス12を介して以下に示す様々な要素と通信可能な処理部11(PU)（判定部）と、該要素として、一般的にはプログラムの全て又は一部を含むROM 及びRSA 鍵を含むためのEEPROMである一又は複数の不揮発性メモリ13(NVM) と、（一般的にはRAM タイプの）一又は複数の揮発性メモリ14と、電子回路1 の外部との通信を可能にするインターフェース回路15(I/O) とを備えている。本発明が特に目的とした適用例では、電子回路1 は、暗号化又は署名計算プロセッサ16(CP)（計算部）を更に備えている。電子回路1 は、点線でブロック17(FCT) によって表されたハードウェア要素及び／又はソフトウェア要素（機能部）によって行なわれる様々な機能を実行することが可能である。ブロック18(PN GEN)によって表されたこれらの機能の内の１つが、RSA タイプのアルゴリズムに基づく、鍵として用いられるべき素数の生成である。他の要素及び電子回路が、目的に応じて電子回路1 を備えてもよい。更に、データ、アドレス及び／又は制御信号を交換するために、電子回路1 の組立部品間の直接リンク（不図示）が設けられてもよい。
【００３９】
図2A及び2Bは、RSA タイプのアルゴリズムの実行を示す。RSA 計算セルが、図2Aにブロック20によって（暗号化側として）表されており、図2Bにブロック21によって（復号側として）表されている。これらの計算セル20,21 は、ソフトウェアセルであれハードウェアセルであれ、実際には同一であってもよい。
【００４０】
整数として示されたデータメッセージM が、公開鍵の暗号化係数n 及び公開指数e を含むか又は受信するRSA 計算セル20に導入されて暗号化される。整数M は、暗号化係数n より小さい。RSA 計算セル20は、暗号化係数n 及び公開指数e に基づく累乗モジュールを計算して、Me mod nを表す暗号化メッセージC を与える。
【００４１】
秘密鍵(n,d) を保持する電子回路1 による復号では、暗号化メッセージC に対して、秘密指数d 及び暗号化係数n に基づく累乗モジュールが行われる、すなわち、RSA 計算セル21は、Cd mod nを表すメッセージM を計算する。
【００４２】
図３は、任意のデジタルコンテンツを表すデータ（ブロック24）の送信者22から受信者23への伝送の一例を示すブロック図である。受信者23がRSA 鍵を有しており、受信者23のRSA 鍵の所有が送信者22に知らされていない場合、公開鍵、すなわち暗号化係数n （因数分解モジュール）及び公開指数e を送信者22に送信することにより開始する。これにより、送信者22に、データを暗号化させ、暗号化されたデータを暗号化メッセージC の形態で送信させることが可能になる。受信者23は、秘密鍵(n,d) を用いてメッセージC を復号してデータ（ブロック25）を得る。
【００４３】
送信は、暗号化係数n の因数分解を発見しようとするハッキング行為を受けることが多い。本発明は、一対の鍵が生成されたときのこのような攻撃を対象としておらず、一度（又は新たな一対の鍵の生成毎に）のみ生じる素数生成中に発生することが多い攻撃を対象としている。
【００４４】
素数の生成は、候補数が素になるまで候補数を修正することを含んでいる。既に示されているように、候補数が大きな数に適した素数判定を受ける前に、簡易化された判定が、候補数が比較的小さな数と素であるか否かを判定するために行なわれる。大きな数に適した判定は、一般的にはフェルマーの定理に基づいており、フェルマーの定理によれば、「u 」が素数である場合、vu-1は、任意の整数「v 」に対してu を法として１と合同である、すなわち、1 又はu 以外の整数による数「u 」の因数分解はあり得ない。現在、素数生成に最も使用されている素数判定法は、いわゆるミラー−ラビン判定法である。この判定法は、候補数が１以外の数によって割り切れないことを確認するために累乗モジュールの計算を実行しており、例えば、エー．メネザス（A.Menezes ）、ピー．バン．オールシュホット（P.van Oorshchot ）及びエス．バンストーン（S.Vanstone）共著，「応用暗号学のハンドブック（Handbook of Applied Cryptography）」1996年，シーアールシープレス（CRC プレス），４章，項目4.2.3 ，頁138-140 に説明されている。実際、素数判定法は完全でないが、エラー確率が十分に低いので、候補数を素であると見なすことが可能である。
【００４５】
図４は、RSA アルゴリズムに基づく暗号化係数n （因数分解モジュール）のための２つの素数の内の１つを表わすことを意図しており、（任意にはp として示される）素数を生成するための通常の方法のステップを示すフローチャートである。図４に示された方法は、一般的には、素数p 及び素数q を得るために連続して２度実行される。
【００４６】
任意の数k が、まず、例えばランダムに選択される（ステップ31）。その後、この数k は、第１の閾値n1以下の素数によって割り切れない候補数を得るために修正される。
【００４７】
実施例によれば、電子回路1 のプロセッサ16（又は機能部17）により、数k が第１の閾値n1以下の素数biの積A1と掛けられる（ステップ32）（i は、1 とm1との間にあり、m1はグループ[1,n1]の素数の数を表わす）。第１の閾値n1は、比較的に小さな値が選択される。例えば、n1=3、A1=6（m1=3 及びb1=1、b2=2、b3=3）。n1=5である場合、A1=30（m1=4及びb1=1、b2=2、b3=3、b4=5）。その後、n1=3である例では、計算された積が２でも３でも割り切れないように、電子回路1 のプロセッサ16（又は機能部17）により、計算された積に１が加えられるか又は該積から１が減じられる（ステップ32′）。数２及び数３と素である第１の候補数a=k.A1±１が得られる。
【００４８】
素数p 及び素数q に求められるサイズが設定される。従って、候補数a のサイズが、素数p 及び素数q に求められるサイズに対応する必要がある。従って、数k のサイズが、積A1のサイズに応じて決定される。上記の実施例では、1024ビットの候補数a 及び30である積A1に対して、数k は1019ビットを超えたビットが選択される。
【００４９】
別の実施例によれば、数k は、数k を積A1で割り切れるようにするために、演算 k = k-(k mod A1)を行なうことにより修正される。その後、積A1と素である数のテーブルから任意に選択された数が加えられる。その後、第１の閾値n1以下の素数と素である候補数a が得られる。この実施例では、数k は、候補数a に求められるサイズと同一のサイズを有する。
【００５０】
次のステップ（ステップ33）は、ふるい分けテーブルSTを構築することを含んでおり、ふるい分けテーブルSTは、第１の閾値n1と該第１の閾値n1より大きな第２の閾値n2との間に含まれる素数の内の１つの素数での候補数a の除算の結果を表す項目を複数有する。これは、第１の閾値n1と第２の閾値n2との間の素数bi（従って、m1及びm2間のi ）に関して値a mod biでふるい分けテーブルSTを埋めることになる。このように埋めるには、候補数を導く除算が用いられ、該除算はサイドチャネル攻撃に反応し易い。第２の閾値n2は、ふるい分けテーブルSTが大きくなり過ぎることを回避するように選択されており、それ故、続いて候補数毎に行なわれる計算が、各候補数に対するミラー−ラビン判定法より（計算に必要な時間及び電力の点で）より消費が少なく維持される。例えば、第２の閾値n2は128 又は256 に等しい。単純化のために、第１の閾値n1は両方のグループ[1,n1]及び[n1,n2] の一部とみなされるが、実際には、第１の閾値n1が通常素数であるので、第１の閾値n1は、判定の繰り返しを省くために、これらのグループの内の一方の一部に過ぎないとみなされる。
【００５１】
ふるい分けテーブルSTが初期化されると、候補数a が、RSA アルゴリズムの実行に許容可能な素数に相当しない限り、次の演算が行われる。
【００５２】
前記演算は、候補数a が間隔[n1,n2] に含まれる全ての数と素であるか否かを判定することにより開始される。これは、ふるい分けテーブルSTが零の値を含んでいないか否かを電子回路1 の処理部11（又は機能部17）により判定することになる（ステップ35）。零の値の存在は、候補数a がふるい分けテーブルST内の対応する素数の倍数であることを意味する。
【００５３】
判定35により、候補数a が間隔[n1,n2] 内の全ての数と素であることが確認され（ステップ35の出力N ）、候補数a がRSA アルゴリズムの実行に適切であるか否かが電子回路1 の処理部11（又は機能部17）により判定される（ステップ37）。このために、数a-1 が公開指数e と素であるか否かが確認される必要がある。実際には、値a mod e （候補数a を公開指数e で割った剰余）が１に等しいか否かが確認される。値a mod e が１に等しくなければ、候補数a はRSA アルゴリズムに適合する、すなわち、RSA アルゴリズムは、公開指数e がオイラー関数(p-1)(q-1)と素である整数であるという条件に合っている。
【００５４】
判定37を通過すると（ステップ37の出力N ）、候補数a に対して、最終的に、ミラー−ラビン素数判定法の複数の実行（一般的には数実行乃至数十の実行）が電子回路1 の処理部11（又は機能部17）により行われる（ステップ38）。候補数a がミラー−ラビン素数判定を通過する場合（ステップ38の出力Y ）、候補数a は、素数p として与えられる（ステップ39）。
【００５５】
判定35、判定37又は判定38の内の１つが、候補数a が適切ではないと示すと（ステップ35若しくはステップ37の出力Y 又はステップ38の出力N ）、新たな候補数が選択される。このために、適切ではないとみなされた候補数a に積A1を加えることにより開始される（ステップ36）。その後、ふるい分けテーブルSTが更新される。ふるい分けテーブルSTの更新は、電子回路1 のプロセッサ16（又は機能部17）がふるい分けテーブルSTの（i によって識別される）要素の夫々に値A1 mod bi を加えることにより行われて（ステップ34）、処理はステップ35に戻される。ここには示されていないが、後で判定37に用いられる値a mod e を含む変数も更新される。
【００５６】
第１の素数p が得られると、RSA アルゴリズムを実行するために必要な第２の素数q を選択するために、方法が再度実行される。その後、図４に示されていない追加のステップが、第１の素数p と第２の素数q とが互いに素であるか否かを判定することを含んでいる。これらの素数p,q が夫々素数であるので、これらの素数p,q が異なることを確認するだけで十分である。
【００５７】
連続した素数生成ステップが、特に、サイドチャネル攻撃又は故障注入攻撃に反応し易い。このような攻撃は、生成された素数を発見すること、又は強制的に非素数を生成させることを目的としている場合がある。どちらの場合も、ハッカーに秘密鍵を発見させ得るかもしれない。
【００５８】
図５は、生じ得るサイドチャネル攻撃（電力分析若しくは電磁気応答分析）又は故障注入攻撃から保護される素数生成方法の実施形態を示すフローチャートである。このフローチャートは、図４のフローチャートと比較される。
【００５９】
既に述べられているように、素数判定に用いられる積A1を条件付ける第１の閾値n1を選択することにより開始される。例えば、第１の閾値n1が３である（m1=3）か又は５（m1=4）であり、積A1が６又は３０である。第１の閾値n1に他の値が選択されてもよい。
【００６０】
その後、任意の数k が、選択されて（ステップ31）、第１の閾値n1以下の素数によって割り切れなくするために修正される。従って、既に述べられているように、数k のサイズが積A1のサイズに応じて決定される。例えば、電子回路1 のプロセッサ16（又は機能部17）により、数k が積A1と掛けられて、その結果に１が加えられて候補数a が生成される（ステップ32）。変形例として、１がこの結果から減じられてもよい。第１の候補数a を生成する他の方法が、用いられてもよい。
【００６１】
次のステップは、電子回路1 のプロセッサ16（又は機能部17）が参照数w を生成することを含んでおり（ステップ41）、参照数w は、候補数a が妨害されていないことを確認し、サイドチャネル攻撃から小さな素数での除算を保護するために、生成処理の終わりに用いられる。
【００６２】
参照数w は、例えば、候補数a から値e.r2.A2を減じることにより得られる。ここで、e が公開指数（例えば、32ビット又は64ビットを超えたビット）を表し、r2が乱数を表し、A2が間隔[n1,n2] 内の素数の積を表す。第２の閾値n2は、既に述べられているように、続いてふるい分けテーブルSTの生成に用いられる閾値を表わす。例えば、第２の閾値n2は、128 又は256 に等しい値が選択される。第２の閾値n2に他の値が選択されてもよい。
【００６３】
乱数r2のサイズは、公開指数e のサイズ及び積A2のサイズを減じることにより候補数a のサイズと等しくなる。従って、減じられた乱数r2は、候補数a と同一のサイズを有する。
【００６４】
従って、本実施形態は、公開指数e が（数百ビットより小さい）比較的小さなサイズである場合に適用される。しかしながら、本発明は、（例えば、生成されるべき素数と同一のサイズの）より大きな公開指数e にも適用される。この場合（不図示）、公開指数e はミラー−ラビン判定に先立つ素数判定を考慮されておらず、選択された候補数a と素であることが（除算による）特定の判定によってこの判定法の終わりに確認される。
【００６５】
その後、公開指数e が素数p 及び素数q の生成において考慮されるほど十分小さいことが想定される。このことは、公開指数e の完全な素数判定を回避する。
【００６６】
参照数w の生成の次のステップは、参照数w に基づくふるい分けテーブルSTを生成することを含んでいる（ステップ43）。図６を参照すると、ふるい分けテーブルSTが、候補数a に基づいて生成されてもよいことが分かる。
【００６７】
図５の実施形態では、ふるい分けテーブルSTは、間隔[n1,n2] 内の素数biと同数の要素を含む。各要素は、対応する素数biでの参照数w の除算に対応し、値a mod biに等しい。公開指数e 及び積A2の乗算結果を候補数a から減じることにより生成されるべき参照数w により、ふるい分けテーブルSTの値が、両方の結果w mod bi及びa mod biを表すことが可能になる。
【００６８】
その後、許容可能な候補数が見つけられていない場合、以下のステップが繰り返し実行される。
【００６９】
許容可能な候補数が見つけられていない場合のステップは、候補数a 及び参照数w が間隔[n1,n2] 内の全ての素数biと素であるか否かを電子回路1 の処理部11（又は機能部17）が判定することにより開始される（ステップ35）。このために、ふるい分けテーブルSTの要素の内の１つが零であるか否かが判定される。ふるい分けテーブルSTの要素の内の１つが零でなければ、電子回路1 の処理部11（又は機能部17）が候補数a の公開指数e との適合性を確認するために、次の判定（ステップ37）に進められる。
【００７０】
候補数a が前の判定35,37 を全て通過している場合（ステップ37の出力N ）、候補数a は電子回路1 の処理部11（又は機能部17）によるミラー−ラビン判定（ステップ38）を受ける。
【００７１】
判定35、判定37又は判定38の内の１つが、候補数a が適格ではないことを示すと（ステップ35若しくはステップ37の出力Y 又はステップ38の出力N ）、新たな候補数及び新たな参照数が、電子回路1 のプロセッサ16（又は機能部17）による積A1の前回の値への加算により計算される（ステップ46）。その後、ふるい分けテーブルSTは、電子回路1 のプロセッサ16（又は機能部17）がbiを法としたふるい分けテーブルSTの全ての要素に積A1を加えることにより更新される（ステップ34）。実際には、値a mod e を含む（従って判定37に用いられる）変数が、値a mod e + A1に更新される。
【００７２】
その後、新たな候補数は、判定35、判定37及び判定38を受ける（判定35及び判定37の順序は重要ではない）。
【００７３】
候補数が適格である場合（ステップ38の出力Y ）、追加のステップにより、電子回路1 の処理部11（又は機能部17）が、計算の始めにおける候補数の完全性、すなわち、参照数w との無矛盾性を判定することが可能になる（ステップ44）。例えば、値e.r2.A2 が、参照数w に加えられて、その結果が候補数a と等しいか否かが判定される（ステップ44）。その結果が候補数a と等しい場合（ステップ44の出力Y ）、候補数a が素数p として与えられる（ステップ39）。その結果が候補数a と等しくない場合（ステップ44の出力N ）、これは、妨害が素数生成の際生じたことを意味する。その後、電子回路はエラー処理に進む。変形例として、ステップ44で、積A2での値a-w の除算結果が判定されてもよい。このような変形例により、乱数r2を記憶することが回避され得る。別の変形例によれば、ステップ41が加算と置き換えられて、ステップ44が減算と置き換えられる。
【００７４】
エラー処理は、例えば、生成された素数の無効化（処理がステップ31から再開される）又は電子回路の不能化である。ハッキングの試みが検出された場合に講じられるこのような処置自体は従来からあり、複数の解決法が適用例に応じて存在する。
【００７５】
ミラー−ラビン判定後に、無矛盾性又は完全性に関する判定44により、候補数a とは異なる数を強いる攻撃を回避することが可能になる。
【００７６】
第１の素数p が生成されると、素数p 及び素数q が互いに素であることを確認する一方、第２の素数q を生成する処理が再開される。最後に、RSA アルゴリズムを実行するために、暗号化係数n が、計算されて（n=p.q ）、公開鍵を形成するために、公開鍵を必要とする可能性のある任意の相手先に（公開指数e と共に）送信される。素数p 及び素数q は電子回路1 にのみ記憶される。
【００７７】
（候補数a の代わりに）参照数w に基づくふるい分けテーブルSTを構築することにより、この構築を隠蔽することが可能になる。
【００７８】
図６は、別の実施形態を示すフローチャートである。図５に対して変更されたステップのみが示されている。
【００７９】
前の実施形態と比較すると、ふるい分けテーブルSTが候補数a に基づいている。従って、間隔[n1,n2] 内の値a mod biで初期化される（ステップ43′）。積A1の加算によるふるい分けテーブルSTの更新結果を保存するために、一候補数から次の候補数に加えられるべき数f 、及び一参照数から次の参照数に加えられるべき数f が、数f が値A1mod bi 及び値A1 mod eに等しいように電子回路1 のプロセッサ16（又は機能部17）により計算される（ステップ46′）。例えば、乱数r1が、乱数r2と無関係に選択されて、積e.A2と掛けられる。乱数r1は、積r1.e.A2 のサイズが、生成されるべき素数に必要な長さより（数バイト乃至数十バイト）小さいようなサイズを有する。このため、一候補数から別の候補数への移行が大きなビット数の修正を伴うことを可能にする。その後、１が積に加えられる。従って、図６に示されるように、新しい候補数及び新しい参照数が、値f.A1を前回の値に加える（ステップ46′）ことにより得られる。尚、値f は、f=e.r1.A2+1で表される。新しい候補数及び参照数は、第１の閾値n1以下の素数と素のままである。積A2がbiを法として零に等しいので、積（e.r1.A2+1 ）は値1 mod biと等しい。その後、前の実施形態と同様に、関連した要素である素数biを法とした要素の各々に積A1を加えることにより、ふるい分けテーブルSTが更新され得る（ステップ34）。
【００８０】
様々な変形例を有する様々な実施形態が上記に説明されている。当業者が、いかなる進歩性も示さずに、これらの様々な実施形態及び変形例の様々な要素を組み合わせてもよいものとする。更に、上記に与えられた機能的な表示に基づく本発明の実際的な実行は、当業者の技能の範囲内にあり、ハードウェアによる実行であってもソフトウェアによる実行であってもよい。
【００８１】
特に、ミラー−ラビン判定に先行する判定に用いられる第１の閾値n1及び第２の閾値n2は、適用例と、素数生成中のミラー−ラビン判定に与えられ得る時間とに応じて選択される。例えば、計算を節約するために、ふるい分けテーブルが、第１の閾値以下の素数に基づいていないことが好ましいが、これは必要不可欠ではない。
【００８２】
更に、乱数のサイズの選択は、素数p 及び素数q に求められるサイズに応じて適合されており、従って、RSA アルゴリズムの累乗モジュールにおける暗号化係数n に適合されている。
【００８３】
更に、本発明は、単一のふるい分けテーブルを実行する方法に関連して説明されているが、複数のふるい分けテーブルを使用して、次のふるい分けテーブルの前に各ふるい分けテーブルの素数判定（ステップ34及びステップ35）を介在することが想定され得る。各ふるい分けテーブルは、連続した閾値によって定義されている隣接した範囲内の素数に対して候補数が素であるか否かを判定する機能を有する。このような変形例は、最適化のために、前回のふるい分けテーブルに基づく素数判定により候補数が素であると判定された場合、ふるい分けテーブルを更新するためだけに用いられてもよい。
【００８４】
言うまでもなく本発明は、当業者に容易に想起される様々な変更、修正及び改良がなされ得る。このような変更、調整及び改良は、本開示の一部であると意図されており、本発明の趣旨及び範囲内であると意図される。従って、上述した説明は単なる一例であり、本発明を制限することを意図していない。本発明は、以下の請求項及びその均等物に定義されているようにのみ制限されている。
【符号の説明】
【００８５】
1 電子回路
ST ふるい分けテーブル
【技術分野】
【０００１】
本発明は、一般的には電子回路に関し、具体的にはRSA タイプの非対称暗号化アルゴリズムを実行する電子回路に関する。本発明は、より具体的には、例えば、電子回路の電力消費の統計的分析（SPA-単純な電力分析）若しくは電子署名の統計的分析によるサイドチャネル攻撃又は故障注入攻撃に対する、電子回路における素数の生成中の保護に関する。
【０００２】
本発明は、素因数分解を用いたアルゴリズムを利用したあらゆる電子回路に適用され、具体的にはチップカードに適用される。
【背景技術】
【０００３】
RSA アルゴリズムは、最も一般的に使用される（公開鍵を備えた）非対称暗号化アルゴリズムの内の１つである。RSA アルゴリズムは、データを暗号化／復号するために、又はデータに署名してデータの認証を可能にするために用いられる。RSA アルゴリズムは、公開鍵及び秘密鍵である１対の鍵の使用に基づいている。暗号化／復号モードでは、公開鍵は、受信者に機密に通信されるべき暗号データのために送信者によって用いられており、受信者は、データを復号するためにプライベートキー、すなわち秘密鍵を用いる。認証のために、秘密鍵がデータに署名するために送信者によって使用される一方、公開鍵は署名を認証するために受信者によって用いられる。
【０００４】
送信者による暗号データの利用を可能にし、受信者による署名されたデータの利用を可能にするために、公開鍵は相対的に広くアクセス可能である。しかしながら、秘密鍵は、一対の鍵を生成した電子回路に保持されている。相手先にデータの処理を可能にさせるために、一対の鍵の保持者が相手先に公開鍵を直接伝送されてもよい。
【０００５】
一対の公開鍵及び秘密鍵を生成するために、相対的に大きなサイズ（一般的には、1,024 ビット又は2,048 ビット）の互いに異なる２つの素数「p 」及び「q 」の使用が必要となる。これらの素数p,q の積が、暗号化係数「n 」を表わす。数p-1 及び数q-1 が公開指数と呼ばれる数「e 」と素であるように、素数p 及び素数q が選択されており、そのため、公開指数「e 」は積n (φ(n) = (p-1)(q-1)) のオイラー関数「φ(n)」と素である。その結果、積e*d がφ(n)を法とした１と合同であるような整数「d 」が存在する。一対の暗号化係数n 及び数d が秘密鍵を表している一方、一対の暗号化係数n 及び公開指数e は公開鍵を表わす。秘密指数d は、(p-1)(q-1)を法とした公開指数e の逆数を表わす。素数p 及び素数q は、秘密鍵を含む電子回路にのみ存在する。
【０００６】
RSA アルゴリズムの頑強性は、素数p 及び素数q により決まる。公開鍵に基づいたRSA アルゴリズムを「解読する」ためには、暗号化係数n を因数分解し、それによって素数p 及び素数q を得ることが可能である必要がある。この因数分解が知られると、秘密指数d は公開指数e から計算され得る（秘密指数d は、(p-1)(q-1)を法とした公開指数e の逆数を計算することにより得られる）。現在、十分なサイズ（一般的には約1,500 ビット程度）の暗号化係数n を用いることにより、現在のアルゴリズムでは、適当な時間内での暗号化係数n の因数分解は不可能になるとみなされている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００３−９１２３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、素数p 及び素数q の電子回路への導入又は電子回路によるこれらの素数p,q の生成が、ハッカーにより発見されると、ハッカーに暗号化係数n の因数分解を提供することになるので、セキュリティの点で特に重要である。
【０００９】
RSA 鍵を生成するための第１の技術は、電子回路の外部でこれらの鍵を生成することを含んでいる。素数p 及び素数q は、カスタマイズ段階で電子回路に導入される。これらの鍵が実際の電子回路によって生成されないので、この技術は故障注入攻撃に反応しない。
【００１０】
公知である第２の技術は、安全な環境（実際には確保されたアクセスを有する保護された装置）で実際の電子回路に素数を生成させることを含んでいる。この技術では、攻撃は、素数生成中問題ではない。
【００１１】
しかしながら、電子回路がこのような安全な環境の外側でRSA 鍵を生成可能であることがますます求められている。これにより、例えば、今までの鍵が否認された場合（鍵のハッキングが想定される場合）に新たな鍵を再生することが可能になる。このような新たな鍵の生成は、例えば、安全ではない環境で電子回路をカスタマイズする際、又は（例えば、署名計算に使用される電子回路若しくは電子識別装置を）初めて使用する際に行われる。電子パスポートへの適用例によれば、パスポートが一度保持者の側に渡ると、鍵はパスポートに含まれる電子チップによって生成されることが求められる。従って、このような鍵は、パスポートの認証手続で予め使用されることは不可能である。
【００１２】
公開指数e は、公開鍵基盤(PKI) のパラメータであってもよく、全ての鍵に対して同一である。公開指数e は、例えば、（ROM 内の）電子回路の製造中、又は（EEPROM内の）電子回路のカスタマイズ段階中に電子回路に導入される。
【００１３】
公開指数e も、例えば、乱数を選択することにより電子回路によって生成されてもよく、その後、電子回路が通信する必要がある要素に伝送されてもよい。
【００１４】
従って、公開鍵（公開指数e 及び暗号化係数n ）は、受信者（署名）若しくは送信者（暗号化）により知られているか、又は秘密鍵を保持する電子回路によって（処理毎に一度だけ）受信者若しくは送信者に伝送される。公開鍵は、更に一般的には認証される必要がある。
【００１５】
大きな素数の生成は、時間及び計算の点でコストがかかる。特に、ある数が素数特性を有するか否かを判定することが可能ないわゆる素数判定法（例えば、いわゆるミラー−ラビン素数判定法）が、一般的には、著しい量の計算を必要とする累乗モジュールを実行する。これは、比較的小さな素数で既に素数であると判定された候補数に対してのみこのような判定を行なうことが求められているためである。このような判定は、比較的小さな素数での除算、又は素数表との比較に対応する。例えば、ミラー−ラビン素数判定法は小さな基数（例えば、２）で行われることが可能であり、又は最大公約数の計算が行なわれてもよい（例えば、255 を法としたバイトを加算し、255 未満の結果を得て、次に、この結果と255 との最大公約数を計算し、計算した最大公約数が１とは異なる場合、一度の判定により、その数が255 の３つの因数、すなわち３，５及び１７で割り切れないことが分かる）。
【００１６】
素数が安全ではない環境で電子回路によって生成される場合、電子回路は、入出力若しくは電子回路の電力消費の分析を利用した故障注入攻撃（電源妨害、レーザー攻撃等）を受けるか、又はサイドチャネル攻撃（SPA 若しくはDPA 又は電磁気分析）を受ける可能性が高い。
【００１７】
電子回路による素数の生成の別の危険性は、最終的に選択された素数を修正しようとする攻撃である。ミラー−ラビン素数判定法の終わりでの攻撃は、アルゴリズムによって考慮された素数を修正するために使用される場合がある。素数p 又は素数q の内の一方が素でない場合、暗号化係数n は因数分解し易く、RSA アルゴリズムのセキュリティを低下させる。
【００１８】
前記素数がこのような鍵を利用する電子回路によって生成されるとき、素数の生成、ひいては、素因数分解を用いたアルゴリズムの鍵の生成を保護することが求められる。
【００１９】
素数生成処理によって与えられる素数の修正を検出することが可能であることを更に求められる。
【００２０】
素数生成を隠蔽することが可能であることが更に求められる。
【課題を解決するための手段】
【００２１】
これらの目的及び他の目的の全て又は一部を達成するために、本発明は、連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護する方法において、
前記候補数毎に、
少なくとも１つの乱数を含む参照数を計算し、
累乗モジュールの計算に基づく少なくとも１つの素数判定を行い、
該素数判定により素数であると判定された候補数毎に、
該候補数と前記参照数との間の無矛盾性を判定することを特徴とする方法を提供する。
【００２２】
本発明の実施形態によれば、前記参照数は、前記乱数に応じた数を前記候補数に加えるか又は前記乱数に応じた数を前記候補数から減じることにより得られる。
【００２３】
本発明の実施形態によれば、前記累乗モジュールの計算に基づく素数判定の前に、前記各候補数に対して、第１の閾値と第２の閾値との間の素数と同数の要素を備えるふるい分けテーブルに基づく少なくとも１つの素数判定が行われ、第１の候補数が、前記第１の閾値以下の素数の第１の積と任意の数とを掛けることにより得られる。
【００２４】
本発明の実施形態によれば、一候補数から次の候補数へ移る際、現在の候補数及び参照数に、前記第１の積を夫々加える。
【００２５】
本発明の実施形態によれば、一候補数から次の候補数へ移る際、前記第１の積の乗算の結果を現在の候補数及び参照数に夫々加え、前記乗数は、前記第１の閾値と第２の閾値との間の素数の第２の積と、少なくとも１つの乱数との関数である。
【００２６】
本発明の実施形態によれば、前記乗数は、更に、RSA アルゴリズムの公開指数の関数である。
【００２７】
本発明の実施形態によれば、前記ふるい分けテーブルは、前記参照数に基づいている。
【００２８】
本発明の実施形態によれば、前記ふるい分けテーブルは、例えば新しい候補数毎に、関連した要素を法とした前記第１の積を前記ふるい分けテーブルの要素に夫々加えることにより更新される。
【００２９】
本発明の実施形態によれば、前記累乗モジュールの計算に基づく素数判定の前に、各候補数に対して、RSA アルゴリズムの公開指数と整合するか否かの判定が行われる。
【００３０】
本発明の実施形態によれば、前記累乗モジュールの計算に基づく素数判定は、ミラー−ラビン判定である。
【００３１】
本発明は、更に、上述された方法を実現するための手段を備えた電子回路を提供する。
【００３２】
本発明は、更に、連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護する方法において、
前記候補数毎に、
前記電子回路の計算部が、少なくとも１つの乱数を含む参照数を計算し、
前記電子回路の判定部が、累乗モジュールの計算に基づく少なくとも１つの素数判定を行い、
前記判定部は、該素数判定により素数であると判定された候補数毎に、該候補数と前記参照数との間の無矛盾性を判定することを特徴とする方法を提供する。
【００３３】
本発明は、更に、連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護するシステムにおいて、
前記候補数毎に、少なくとも１つの乱数を含む参照数を計算する計算部と、
前記候補数毎に、累乗モジュールの計算に基づく少なくとも１つの素数判定を行う判定部とを備え、
前記判定部は、該素数判定により素数であると判定された候補数毎に、該候補数と前記参照数との間の無矛盾性を判定することを特徴とするシステムを提供する。
【００３４】
本発明の前述及び他の目的、特徴及び利点を、添付図面を参照して本発明を限定するものではない特定の実施形態について以下に詳細に説明する。
【図面の簡単な説明】
【００３５】
【図１】本発明が実施例として適用されるタイプの電子回路の実施形態を示すブロック図である。
【図２Ａ】RSA アルゴリズムによる暗号化を非常に概略的に示す図である。
【図２Ｂ】RSA アルゴリズムによる復号を概略的に示す図である。
【図３】暗号化されたデータの伝送システムを示すブロック図である。
【図４】RSA タイプのアルゴリズムを実行する電子回路内で素数を生成する通常のステップを示すフローチャートである。
【図５】本実施形態に係る素数生成法のステップを示すフローチャートである。
【図６】素数生成法の別の実施形態を部分的に示すフローチャートである。
【発明を実施するための形態】
【００３６】
明瞭化のために、同一の要素は異なる図面において同一の参照番号で示されている。更に、本発明の理解に有用なステップ及び要素のみが示され、説明されている。特に、素数に基づく鍵を用いたアルゴリズムに関する電子回路によりどのような利用がなされるのかは詳述されておらず、本発明は、生成された素数のあらゆる通常の利用（暗号化及び署名計算）に適合する。
【００３７】
本発明は、暗号化／復号に用いられるRSA アルゴリズムへの適用例に関連して以下に説明される。しかしながら、本発明は、生成された素数に基づくRSA アルゴリズムを用いたあらゆる利用法にも適用されるものとする。本発明は、特にRSA 署名に適用される。更に一般的には、本発明は、素因数分解により決まる鍵を有するあらゆるアルゴリズム、例えばいわゆるラビン暗号システムに適用される。
【００３８】
図１は、本発明が適用されるタイプの電子回路1 （例えばスマートカード）の例をブロック形式で非常に概略的に示す。このような電子回路1 は、一又は複数のデータ、アドレス及び制御バス12を介して以下に示す様々な要素と通信可能な処理部11(PU)（判定部）と、該要素として、一般的にはプログラムの全て又は一部を含むROM 及びRSA 鍵を含むためのEEPROMである一又は複数の不揮発性メモリ13(NVM) と、（一般的にはRAM タイプの）一又は複数の揮発性メモリ14と、電子回路1 の外部との通信を可能にするインターフェース回路15(I/O) とを備えている。本発明が特に目的とした適用例では、電子回路1 は、暗号化又は署名計算プロセッサ16(CP)（計算部）を更に備えている。電子回路1 は、点線でブロック17(FCT) によって表されたハードウェア要素及び／又はソフトウェア要素（機能部）によって行なわれる様々な機能を実行することが可能である。ブロック18(PN GEN)によって表されたこれらの機能の内の１つが、RSA タイプのアルゴリズムに基づく、鍵として用いられるべき素数の生成である。他の要素及び電子回路が、目的に応じて電子回路1 を備えてもよい。更に、データ、アドレス及び／又は制御信号を交換するために、電子回路1 の組立部品間の直接リンク（不図示）が設けられてもよい。
【００３９】
図2A及び2Bは、RSA タイプのアルゴリズムの実行を示す。RSA 計算セルが、図2Aにブロック20によって（暗号化側として）表されており、図2Bにブロック21によって（復号側として）表されている。これらの計算セル20,21 は、ソフトウェアセルであれハードウェアセルであれ、実際には同一であってもよい。
【００４０】
整数として示されたデータメッセージM が、公開鍵の暗号化係数n 及び公開指数e を含むか又は受信するRSA 計算セル20に導入されて暗号化される。整数M は、暗号化係数n より小さい。RSA 計算セル20は、暗号化係数n 及び公開指数e に基づく累乗モジュールを計算して、Me mod nを表す暗号化メッセージC を与える。
【００４１】
秘密鍵(n,d) を保持する電子回路1 による復号では、暗号化メッセージC に対して、秘密指数d 及び暗号化係数n に基づく累乗モジュールが行われる、すなわち、RSA 計算セル21は、Cd mod nを表すメッセージM を計算する。
【００４２】
図３は、任意のデジタルコンテンツを表すデータ（ブロック24）の送信者22から受信者23への伝送の一例を示すブロック図である。受信者23がRSA 鍵を有しており、受信者23のRSA 鍵の所有が送信者22に知らされていない場合、公開鍵、すなわち暗号化係数n （因数分解モジュール）及び公開指数e を送信者22に送信することにより開始する。これにより、送信者22に、データを暗号化させ、暗号化されたデータを暗号化メッセージC の形態で送信させることが可能になる。受信者23は、秘密鍵(n,d) を用いてメッセージC を復号してデータ（ブロック25）を得る。
【００４３】
送信は、暗号化係数n の因数分解を発見しようとするハッキング行為を受けることが多い。本発明は、一対の鍵が生成されたときのこのような攻撃を対象としておらず、一度（又は新たな一対の鍵の生成毎に）のみ生じる素数生成中に発生することが多い攻撃を対象としている。
【００４４】
素数の生成は、候補数が素になるまで候補数を修正することを含んでいる。既に示されているように、候補数が大きな数に適した素数判定を受ける前に、簡易化された判定が、候補数が比較的小さな数と素であるか否かを判定するために行なわれる。大きな数に適した判定は、一般的にはフェルマーの定理に基づいており、フェルマーの定理によれば、「u 」が素数である場合、vu-1は、任意の整数「v 」に対してu を法として１と合同である、すなわち、1 又はu 以外の整数による数「u 」の因数分解はあり得ない。現在、素数生成に最も使用されている素数判定法は、いわゆるミラー−ラビン判定法である。この判定法は、候補数が１以外の数によって割り切れないことを確認するために累乗モジュールの計算を実行しており、例えば、エー．メネザス（A.Menezes ）、ピー．バン．オールシュホット（P.van Oorshchot ）及びエス．バンストーン（S.Vanstone）共著，「応用暗号学のハンドブック（Handbook of Applied Cryptography）」1996年，シーアールシープレス（CRC プレス），４章，項目4.2.3 ，頁138-140 に説明されている。実際、素数判定法は完全でないが、エラー確率が十分に低いので、候補数を素であると見なすことが可能である。
【００４５】
図４は、RSA アルゴリズムに基づく暗号化係数n （因数分解モジュール）のための２つの素数の内の１つを表わすことを意図しており、（任意にはp として示される）素数を生成するための通常の方法のステップを示すフローチャートである。図４に示された方法は、一般的には、素数p 及び素数q を得るために連続して２度実行される。
【００４６】
任意の数k が、まず、例えばランダムに選択される（ステップ31）。その後、この数k は、第１の閾値n1以下の素数によって割り切れない候補数を得るために修正される。
【００４７】
実施例によれば、電子回路1 のプロセッサ16（又は機能部17）により、数k が第１の閾値n1以下の素数biの積A1と掛けられる（ステップ32）（i は、1 とm1との間にあり、m1はグループ[1,n1]の素数の数を表わす）。第１の閾値n1は、比較的に小さな値が選択される。例えば、n1=3、A1=6（m1=3 及びb1=1、b2=2、b3=3）。n1=5である場合、A1=30（m1=4及びb1=1、b2=2、b3=3、b4=5）。その後、n1=3である例では、計算された積が２でも３でも割り切れないように、電子回路1 のプロセッサ16（又は機能部17）により、計算された積に１が加えられるか又は該積から１が減じられる（ステップ32′）。数２及び数３と素である第１の候補数a=k.A1±１が得られる。
【００４８】
素数p 及び素数q に求められるサイズが設定される。従って、候補数a のサイズが、素数p 及び素数q に求められるサイズに対応する必要がある。従って、数k のサイズが、積A1のサイズに応じて決定される。上記の実施例では、1024ビットの候補数a 及び30である積A1に対して、数k は1019ビットを超えたビットが選択される。
【００４９】
別の実施例によれば、数k は、数k を積A1で割り切れるようにするために、演算 k = k-(k mod A1)を行なうことにより修正される。その後、積A1と素である数のテーブルから任意に選択された数が加えられる。その後、第１の閾値n1以下の素数と素である候補数a が得られる。この実施例では、数k は、候補数a に求められるサイズと同一のサイズを有する。
【００５０】
次のステップ（ステップ33）は、ふるい分けテーブルSTを構築することを含んでおり、ふるい分けテーブルSTは、第１の閾値n1と該第１の閾値n1より大きな第２の閾値n2との間に含まれる素数の内の１つの素数での候補数a の除算の結果を表す項目を複数有する。これは、第１の閾値n1と第２の閾値n2との間の素数bi（従って、m1及びm2間のi ）に関して値a mod biでふるい分けテーブルSTを埋めることになる。このように埋めるには、候補数を導く除算が用いられ、該除算はサイドチャネル攻撃に反応し易い。第２の閾値n2は、ふるい分けテーブルSTが大きくなり過ぎることを回避するように選択されており、それ故、続いて候補数毎に行なわれる計算が、各候補数に対するミラー−ラビン判定法より（計算に必要な時間及び電力の点で）より消費が少なく維持される。例えば、第２の閾値n2は128 又は256 に等しい。単純化のために、第１の閾値n1は両方のグループ[1,n1]及び[n1,n2] の一部とみなされるが、実際には、第１の閾値n1が通常素数であるので、第１の閾値n1は、判定の繰り返しを省くために、これらのグループの内の一方の一部に過ぎないとみなされる。
【００５１】
ふるい分けテーブルSTが初期化されると、候補数a が、RSA アルゴリズムの実行に許容可能な素数に相当しない限り、次の演算が行われる。
【００５２】
前記演算は、候補数a が間隔[n1,n2] に含まれる全ての数と素であるか否かを判定することにより開始される。これは、ふるい分けテーブルSTが零の値を含んでいないか否かを電子回路1 の処理部11（又は機能部17）により判定することになる（ステップ35）。零の値の存在は、候補数a がふるい分けテーブルST内の対応する素数の倍数であることを意味する。
【００５３】
判定35により、候補数a が間隔[n1,n2] 内の全ての数と素であることが確認され（ステップ35の出力N ）、候補数a がRSA アルゴリズムの実行に適切であるか否かが電子回路1 の処理部11（又は機能部17）により判定される（ステップ37）。このために、数a-1 が公開指数e と素であるか否かが確認される必要がある。実際には、値a mod e （候補数a を公開指数e で割った剰余）が１に等しいか否かが確認される。値a mod e が１に等しくなければ、候補数a はRSA アルゴリズムに適合する、すなわち、RSA アルゴリズムは、公開指数e がオイラー関数(p-1)(q-1)と素である整数であるという条件に合っている。
【００５４】
判定37を通過すると（ステップ37の出力N ）、候補数a に対して、最終的に、ミラー−ラビン素数判定法の複数の実行（一般的には数実行乃至数十の実行）が電子回路1 の処理部11（又は機能部17）により行われる（ステップ38）。候補数a がミラー−ラビン素数判定を通過する場合（ステップ38の出力Y ）、候補数a は、素数p として与えられる（ステップ39）。
【００５５】
判定35、判定37又は判定38の内の１つが、候補数a が適切ではないと示すと（ステップ35若しくはステップ37の出力Y 又はステップ38の出力N ）、新たな候補数が選択される。このために、適切ではないとみなされた候補数a に積A1を加えることにより開始される（ステップ36）。その後、ふるい分けテーブルSTが更新される。ふるい分けテーブルSTの更新は、電子回路1 のプロセッサ16（又は機能部17）がふるい分けテーブルSTの（i によって識別される）要素の夫々に値A1 mod bi を加えることにより行われて（ステップ34）、処理はステップ35に戻される。ここには示されていないが、後で判定37に用いられる値a mod e を含む変数も更新される。
【００５６】
第１の素数p が得られると、RSA アルゴリズムを実行するために必要な第２の素数q を選択するために、方法が再度実行される。その後、図４に示されていない追加のステップが、第１の素数p と第２の素数q とが互いに素であるか否かを判定することを含んでいる。これらの素数p,q が夫々素数であるので、これらの素数p,q が異なることを確認するだけで十分である。
【００５７】
連続した素数生成ステップが、特に、サイドチャネル攻撃又は故障注入攻撃に反応し易い。このような攻撃は、生成された素数を発見すること、又は強制的に非素数を生成させることを目的としている場合がある。どちらの場合も、ハッカーに秘密鍵を発見させ得るかもしれない。
【００５８】
図５は、生じ得るサイドチャネル攻撃（電力分析若しくは電磁気応答分析）又は故障注入攻撃から保護される素数生成方法の実施形態を示すフローチャートである。このフローチャートは、図４のフローチャートと比較される。
【００５９】
既に述べられているように、素数判定に用いられる積A1を条件付ける第１の閾値n1を選択することにより開始される。例えば、第１の閾値n1が３である（m1=3）か又は５（m1=4）であり、積A1が６又は３０である。第１の閾値n1に他の値が選択されてもよい。
【００６０】
その後、任意の数k が、選択されて（ステップ31）、第１の閾値n1以下の素数によって割り切れなくするために修正される。従って、既に述べられているように、数k のサイズが積A1のサイズに応じて決定される。例えば、電子回路1 のプロセッサ16（又は機能部17）により、数k が積A1と掛けられて、その結果に１が加えられて候補数a が生成される（ステップ32）。変形例として、１がこの結果から減じられてもよい。第１の候補数a を生成する他の方法が、用いられてもよい。
【００６１】
次のステップは、電子回路1 のプロセッサ16（又は機能部17）が参照数w を生成することを含んでおり（ステップ41）、参照数w は、候補数a が妨害されていないことを確認し、サイドチャネル攻撃から小さな素数での除算を保護するために、生成処理の終わりに用いられる。
【００６２】
参照数w は、例えば、候補数a から値e.r2.A2を減じることにより得られる。ここで、e が公開指数（例えば、32ビット又は64ビットを超えたビット）を表し、r2が乱数を表し、A2が間隔[n1,n2] 内の素数の積を表す。第２の閾値n2は、既に述べられているように、続いてふるい分けテーブルSTの生成に用いられる閾値を表わす。例えば、第２の閾値n2は、128 又は256 に等しい値が選択される。第２の閾値n2に他の値が選択されてもよい。
【００６３】
乱数r2のサイズは、公開指数e のサイズ及び積A2のサイズを減じることにより候補数a のサイズと等しくなる。従って、減じられた乱数r2は、候補数a と同一のサイズを有する。
【００６４】
従って、本実施形態は、公開指数e が（数百ビットより小さい）比較的小さなサイズである場合に適用される。しかしながら、本発明は、（例えば、生成されるべき素数と同一のサイズの）より大きな公開指数e にも適用される。この場合（不図示）、公開指数e はミラー−ラビン判定に先立つ素数判定を考慮されておらず、選択された候補数a と素であることが（除算による）特定の判定によってこの判定法の終わりに確認される。
【００６５】
その後、公開指数e が素数p 及び素数q の生成において考慮されるほど十分小さいことが想定される。このことは、公開指数e の完全な素数判定を回避する。
【００６６】
参照数w の生成の次のステップは、参照数w に基づくふるい分けテーブルSTを生成することを含んでいる（ステップ43）。図６を参照すると、ふるい分けテーブルSTが、候補数a に基づいて生成されてもよいことが分かる。
【００６７】
図５の実施形態では、ふるい分けテーブルSTは、間隔[n1,n2] 内の素数biと同数の要素を含む。各要素は、対応する素数biでの参照数w の除算に対応し、値a mod biに等しい。公開指数e 及び積A2の乗算結果を候補数a から減じることにより生成されるべき参照数w により、ふるい分けテーブルSTの値が、両方の結果w mod bi及びa mod biを表すことが可能になる。
【００６８】
その後、許容可能な候補数が見つけられていない場合、以下のステップが繰り返し実行される。
【００６９】
許容可能な候補数が見つけられていない場合のステップは、候補数a 及び参照数w が間隔[n1,n2] 内の全ての素数biと素であるか否かを電子回路1 の処理部11（又は機能部17）が判定することにより開始される（ステップ35）。このために、ふるい分けテーブルSTの要素の内の１つが零であるか否かが判定される。ふるい分けテーブルSTの要素の内の１つが零でなければ、電子回路1 の処理部11（又は機能部17）が候補数a の公開指数e との適合性を確認するために、次の判定（ステップ37）に進められる。
【００７０】
候補数a が前の判定35,37 を全て通過している場合（ステップ37の出力N ）、候補数a は電子回路1 の処理部11（又は機能部17）によるミラー−ラビン判定（ステップ38）を受ける。
【００７１】
判定35、判定37又は判定38の内の１つが、候補数a が適格ではないことを示すと（ステップ35若しくはステップ37の出力Y 又はステップ38の出力N ）、新たな候補数及び新たな参照数が、電子回路1 のプロセッサ16（又は機能部17）による積A1の前回の値への加算により計算される（ステップ46）。その後、ふるい分けテーブルSTは、電子回路1 のプロセッサ16（又は機能部17）がbiを法としたふるい分けテーブルSTの全ての要素に積A1を加えることにより更新される（ステップ34）。実際には、値a mod e を含む（従って判定37に用いられる）変数が、値a mod e + A1に更新される。
【００７２】
その後、新たな候補数は、判定35、判定37及び判定38を受ける（判定35及び判定37の順序は重要ではない）。
【００７３】
候補数が適格である場合（ステップ38の出力Y ）、追加のステップにより、電子回路1 の処理部11（又は機能部17）が、計算の始めにおける候補数の完全性、すなわち、参照数w との無矛盾性を判定することが可能になる（ステップ44）。例えば、値e.r2.A2 が、参照数w に加えられて、その結果が候補数a と等しいか否かが判定される（ステップ44）。その結果が候補数a と等しい場合（ステップ44の出力Y ）、候補数a が素数p として与えられる（ステップ39）。その結果が候補数a と等しくない場合（ステップ44の出力N ）、これは、妨害が素数生成の際生じたことを意味する。その後、電子回路はエラー処理に進む。変形例として、ステップ44で、積A2での値a-w の除算結果が判定されてもよい。このような変形例により、乱数r2を記憶することが回避され得る。別の変形例によれば、ステップ41が加算と置き換えられて、ステップ44が減算と置き換えられる。
【００７４】
エラー処理は、例えば、生成された素数の無効化（処理がステップ31から再開される）又は電子回路の不能化である。ハッキングの試みが検出された場合に講じられるこのような処置自体は従来からあり、複数の解決法が適用例に応じて存在する。
【００７５】
ミラー−ラビン判定後に、無矛盾性又は完全性に関する判定44により、候補数a とは異なる数を強いる攻撃を回避することが可能になる。
【００７６】
第１の素数p が生成されると、素数p 及び素数q が互いに素であることを確認する一方、第２の素数q を生成する処理が再開される。最後に、RSA アルゴリズムを実行するために、暗号化係数n が、計算されて（n=p.q ）、公開鍵を形成するために、公開鍵を必要とする可能性のある任意の相手先に（公開指数e と共に）送信される。素数p 及び素数q は電子回路1 にのみ記憶される。
【００７７】
（候補数a の代わりに）参照数w に基づくふるい分けテーブルSTを構築することにより、この構築を隠蔽することが可能になる。
【００７８】
図６は、別の実施形態を示すフローチャートである。図５に対して変更されたステップのみが示されている。
【００７９】
前の実施形態と比較すると、ふるい分けテーブルSTが候補数a に基づいている。従って、間隔[n1,n2] 内の値a mod biで初期化される（ステップ43′）。積A1の加算によるふるい分けテーブルSTの更新結果を保存するために、一候補数から次の候補数に加えられるべき数f 、及び一参照数から次の参照数に加えられるべき数f が、数f が値A1mod bi 及び値A1 mod eに等しいように電子回路1 のプロセッサ16（又は機能部17）により計算される（ステップ46′）。例えば、乱数r1が、乱数r2と無関係に選択されて、積e.A2と掛けられる。乱数r1は、積r1.e.A2 のサイズが、生成されるべき素数に必要な長さより（数バイト乃至数十バイト）小さいようなサイズを有する。このため、一候補数から別の候補数への移行が大きなビット数の修正を伴うことを可能にする。その後、１が積に加えられる。従って、図６に示されるように、新しい候補数及び新しい参照数が、値f.A1を前回の値に加える（ステップ46′）ことにより得られる。尚、値f は、f=e.r1.A2+1で表される。新しい候補数及び参照数は、第１の閾値n1以下の素数と素のままである。積A2がbiを法として零に等しいので、積（e.r1.A2+1 ）は値1 mod biと等しい。その後、前の実施形態と同様に、関連した要素である素数biを法とした要素の各々に積A1を加えることにより、ふるい分けテーブルSTが更新され得る（ステップ34）。
【００８０】
様々な変形例を有する様々な実施形態が上記に説明されている。当業者が、いかなる進歩性も示さずに、これらの様々な実施形態及び変形例の様々な要素を組み合わせてもよいものとする。更に、上記に与えられた機能的な表示に基づく本発明の実際的な実行は、当業者の技能の範囲内にあり、ハードウェアによる実行であってもソフトウェアによる実行であってもよい。
【００８１】
特に、ミラー−ラビン判定に先行する判定に用いられる第１の閾値n1及び第２の閾値n2は、適用例と、素数生成中のミラー−ラビン判定に与えられ得る時間とに応じて選択される。例えば、計算を節約するために、ふるい分けテーブルが、第１の閾値以下の素数に基づいていないことが好ましいが、これは必要不可欠ではない。
【００８２】
更に、乱数のサイズの選択は、素数p 及び素数q に求められるサイズに応じて適合されており、従って、RSA アルゴリズムの累乗モジュールにおける暗号化係数n に適合されている。
【００８３】
更に、本発明は、単一のふるい分けテーブルを実行する方法に関連して説明されているが、複数のふるい分けテーブルを使用して、次のふるい分けテーブルの前に各ふるい分けテーブルの素数判定（ステップ34及びステップ35）を介在することが想定され得る。各ふるい分けテーブルは、連続した閾値によって定義されている隣接した範囲内の素数に対して候補数が素であるか否かを判定する機能を有する。このような変形例は、最適化のために、前回のふるい分けテーブルに基づく素数判定により候補数が素であると判定された場合、ふるい分けテーブルを更新するためだけに用いられてもよい。
【００８４】
言うまでもなく本発明は、当業者に容易に想起される様々な変更、修正及び改良がなされ得る。このような変更、調整及び改良は、本開示の一部であると意図されており、本発明の趣旨及び範囲内であると意図される。従って、上述した説明は単なる一例であり、本発明を制限することを意図していない。本発明は、以下の請求項及びその均等物に定義されているようにのみ制限されている。
【符号の説明】
【００８５】
1 電子回路
ST ふるい分けテーブル
【特許請求の範囲】
【請求項１】
連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護する方法において、
前記候補数毎に、
少なくとも１つの乱数を含む参照数を計算し、
累乗モジュールの計算に基づく少なくとも１つの素数判定を行い、
該素数判定により素数であると判定された候補数毎に、
該候補数と前記参照数との間の無矛盾性を判定することを特徴とする方法。
【請求項２】
前記参照数は、前記乱数に応じた数を前記候補数に加えるか又は前記乱数に応じた数を前記候補数から減じることにより得られることを特徴とする請求項１に記載の方法。
【請求項３】
前記累乗モジュールの計算に基づく素数判定の前に、前記各候補数に対して、第１の閾値と第２の閾値との間の素数と同数の要素を備えるふるい分けテーブルに基づく少なくとも１つの素数判定が行われ、
第１の候補数が、前記第１の閾値以下の素数の第１の積と任意の数とを掛けることにより得られることを特徴とする請求項２に記載の方法。
【請求項４】
一候補数から次の候補数へ移る際、現在の候補数及び参照数に、前記第１の積を夫々加えることを特徴とする請求項３に記載の方法。
【請求項５】
一候補数から次の候補数へ移る際、前記第１の積の乗算の結果を現在の候補数及び参照数に夫々加え、
前記乗数は、前記第１の閾値と第２の閾値との間の素数の第２の積と、少なくとも１つの乱数との関数であることを特徴とする請求項３に記載の方法。
【請求項６】
前記乗数は、更に、RSA アルゴリズムの公開指数の関数であることを特徴とする請求項５に記載の方法。
【請求項７】
前記ふるい分けテーブルは、前記参照数に基づいていることを特徴とする請求項３に記載の方法。
【請求項８】
前記ふるい分けテーブルは、新しい候補数毎に、関連した要素を法とした前記第１の積を前記ふるい分けテーブルの要素に夫々加えることにより更新されることを特徴とする請求項３に記載の方法。
【請求項９】
前記累乗モジュールの計算に基づく素数判定の前に、各候補数に対して、RSA アルゴリズムの公開指数と整合するか否かの判定が行われることを特徴とする請求項１に記載の方法。
【請求項１０】
前記累乗モジュールの計算に基づく素数判定は、ミラー−ラビン判定であることを特徴とする請求項１に記載の方法。
【請求項１１】
請求項１に記載の方法を実行するための手段を備えた電子回路。
【請求項１２】
連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護する方法において、
前記候補数毎に、
前記電子回路の計算部が、少なくとも１つの乱数を含む参照数を計算し、
前記電子回路の判定部が、累乗モジュールの計算に基づく少なくとも１つの素数判定を行い、
前記判定部は、該素数判定により素数であると判定された候補数毎に、該候補数と前記参照数との間の無矛盾性を判定することを特徴とする方法。
【請求項１３】
連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護するシステムにおいて、
前記候補数毎に、少なくとも１つの乱数を含む参照数を計算する計算部と、
前記候補数毎に、累乗モジュールの計算に基づく少なくとも１つの素数判定を行う判定部とを備え、
前記判定部は、該素数判定により素数であると判定された候補数毎に、該候補数と前記参照数との間の無矛盾性を判定することを特徴とするシステム。
【請求項１】
連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護する方法において、
前記候補数毎に、
少なくとも１つの乱数を含む参照数を計算し、
累乗モジュールの計算に基づく少なくとも１つの素数判定を行い、
該素数判定により素数であると判定された候補数毎に、
該候補数と前記参照数との間の無矛盾性を判定することを特徴とする方法。
【請求項２】
前記参照数は、前記乱数に応じた数を前記候補数に加えるか又は前記乱数に応じた数を前記候補数から減じることにより得られることを特徴とする請求項１に記載の方法。
【請求項３】
前記累乗モジュールの計算に基づく素数判定の前に、前記各候補数に対して、第１の閾値と第２の閾値との間の素数と同数の要素を備えるふるい分けテーブルに基づく少なくとも１つの素数判定が行われ、
第１の候補数が、前記第１の閾値以下の素数の第１の積と任意の数とを掛けることにより得られることを特徴とする請求項２に記載の方法。
【請求項４】
一候補数から次の候補数へ移る際、現在の候補数及び参照数に、前記第１の積を夫々加えることを特徴とする請求項３に記載の方法。
【請求項５】
一候補数から次の候補数へ移る際、前記第１の積の乗算の結果を現在の候補数及び参照数に夫々加え、
前記乗数は、前記第１の閾値と第２の閾値との間の素数の第２の積と、少なくとも１つの乱数との関数であることを特徴とする請求項３に記載の方法。
【請求項６】
前記乗数は、更に、RSA アルゴリズムの公開指数の関数であることを特徴とする請求項５に記載の方法。
【請求項７】
前記ふるい分けテーブルは、前記参照数に基づいていることを特徴とする請求項３に記載の方法。
【請求項８】
前記ふるい分けテーブルは、新しい候補数毎に、関連した要素を法とした前記第１の積を前記ふるい分けテーブルの要素に夫々加えることにより更新されることを特徴とする請求項３に記載の方法。
【請求項９】
前記累乗モジュールの計算に基づく素数判定の前に、各候補数に対して、RSA アルゴリズムの公開指数と整合するか否かの判定が行われることを特徴とする請求項１に記載の方法。
【請求項１０】
前記累乗モジュールの計算に基づく素数判定は、ミラー−ラビン判定であることを特徴とする請求項１に記載の方法。
【請求項１１】
請求項１に記載の方法を実行するための手段を備えた電子回路。
【請求項１２】
連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護する方法において、
前記候補数毎に、
前記電子回路の計算部が、少なくとも１つの乱数を含む参照数を計算し、
前記電子回路の判定部が、累乗モジュールの計算に基づく少なくとも１つの素数判定を行い、
前記判定部は、該素数判定により素数であると判定された候補数毎に、該候補数と前記参照数との間の無矛盾性を判定することを特徴とする方法。
【請求項１３】
連続した候補数の素数特性の判定に基づく電子回路による少なくとも１つの素数の生成を保護するシステムにおいて、
前記候補数毎に、少なくとも１つの乱数を含む参照数を計算する計算部と、
前記候補数毎に、累乗モジュールの計算に基づく少なくとも１つの素数判定を行う判定部とを備え、
前記判定部は、該素数判定により素数であると判定された候補数毎に、該候補数と前記参照数との間の無矛盾性を判定することを特徴とするシステム。
【図１】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１０−２７７０８５（Ｐ２０１０−２７７０８５Ａ）
【公開日】平成２２年１２月９日（２０１０．１２．９）
【国際特許分類】
【出願番号】特願２０１０−１２０８３５（Ｐ２０１０−１２０８３５）
【出願日】平成２２年５月２６日（２０１０．５．２６）
【出願人】（５０９１８６３０６）プロトン ワールド インターナショナル エヌ．ヴィ． (5)
【出願人】（５０９０９６１５３）エス テ マイクロエレクトロニクス（ローセット）エス アー エス (15)
【Ｆターム（参考）】
【公開日】平成２２年１２月９日（２０１０．１２．９）
【国際特許分類】
【出願日】平成２２年５月２６日（２０１０．５．２６）
【出願人】（５０９１８６３０６）プロトン ワールド インターナショナル エヌ．ヴィ． (5)
【出願人】（５０９０９６１５３）エス テ マイクロエレクトロニクス（ローセット）エス アー エス (15)
【Ｆターム（参考）】
[ Back to top ]