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