(57)【特許請求の範囲】
【請求項１】
体上に定義された楕円曲線上の点Ｐのｋ倍を計算する場合において、暗号化システム上でタイミングアタックに対抗する方法であって、該方法は、プロセッサによって実行され、該暗号化システム上でタイミングアタックに対抗することは、ｋの異なる値に対して区別することが不可能な該プロセッサのパワーシグニチャー波形を生成するように該プロセッサを動作させることによって行われ、
該方法は、
ａ）数ｋを複数のビットｋiからなる二進ベクトルとして表現することと、
ｂ）該楕円曲線上の点Ｐ1、Ｐ2の順序対の表現を格納することであって、点Ｐ1、Ｐ2は、最大でＰだけ異なる、ことと、
ｃ）該複数のビットｋiの各々を順次選択し、該複数のビットｋiの各々に対して点Ｐ1′、Ｐ2′の組の新しい表現を計算することであって、該選択および該計算は、該複数のビットｋiの各々が選択され、かつ、該表現のうちの１つが点ｋＰの表現となるまで継続し、
該計算は、
ｋiが０である場合には、該プロセッサが、点Ｐ1の表現に対して第１の二倍演算を実行することにより、点Ｐ1′の表現を計算し、これにより、該二倍演算が、第１のパワーシグニチャーを生成し、該プロセッサが、点Ｐ1、Ｐ2の表現を加算する加算演算を実行することにより、点Ｐ2′の表現を計算し、これにより、該加算演算が、該第１のパワーシグニチャーとは異なる第２のパワーシグニチャーを生成することと、
ｋiが１である場合には、該プロセッサが、点Ｐ2の表現に対して第１の二倍演算を実行することにより、点Ｐ2′の表現を計算し、これにより、該第１のパワーシグニチャーを生成し、該プロセッサが、該点Ｐ1、Ｐ2の表現を加算する加算演算を実行することにより、点Ｐ1′の表現を生成し、これにより、該加算演算が、該第２のパワーシグニチャーを生成することと
に従って実行される、ことと
を含み、
該二倍演算および該加算演算は、常に、該複数のビットｋiの各々に対して同じ順序で実行され、これにより、該プロセッサは、該複数のビットの各々に対して、該第１のパワーシグニチャーおよび該第２のパワーシグニチャーの組み合わせからなる区別することが不可能なパワーシグニチャー波形を生成することにより、該暗号化システム上の該タイミングアタックに対抗する、方法。
【請求項２】
前記体が、Ｆ2mである、請求項１に記載の方法。
【請求項３】
前記体が、Ｆpである、請求項１に記載の方法。
【請求項４】
前記体が、Ｆｑであり、ｑは素数の累乗である、請求項１に記載の方法。
【請求項５】
体上に定義された楕円曲線上の点Ｐのｋ倍を計算するプロセッサであって、該プロセッサは、タイミングアタックに対抗するためにｋの異なる値に対して区別することが不可能なパワーシグニチャー波形を生成し、
該プロセッサは、
ａ）数ｋの表現を複数のビットｋiからなる二進ベクトルとして格納するレジスタと、
ｂ）該楕円曲線上の点Ｐ1、Ｐ2の順序対の表現を格納するメモリであって、点Ｐ1、Ｐ2は、最大でＰだけ異なる、メモリと、
ｃ）二倍演算算を実行することにより、第１のパワーシグニチャーを生成する第１の回路と、
ｄ）加算演算を実行することにより、該第１のパワーシグニチャーとは異なる第２のパワーシグニチャーを生成する第２の回路と、
ｅ）該レジスタから順に該二進ベクトルの該複数のビットｋiの各々を受信する評価器であって、該複数のビットｋiの各々に対して、該格納されている表現に対する該第１の回路および該第２の回路の動作を制御することにより、該メモリに格納されるべき点Ｐ1′、Ｐ2′の組の新しい表現を計算する評価器と
を含み、
該第１の回路および該第２の回路は、
該ビットｋiが０である場合には、該第１の回路が、点Ｐ1の表現に対して第１の二倍演算算を実行することにより、点Ｐ1′の表現を計算し、これにより、該二倍演算が、該第１のパワーシグニチャーを生成し、該第２の回路が、点Ｐ1、Ｐ2の表現を加算する加算演算を実行することにより、点Ｐ2′の表現を計算し、これにより、該加算演算が、該第１のパワーシグニチャーとは異なる該第２のパワーシグニチャーを生成することと、
該ビットｋiが１である場合には、該第１の回路が、点Ｐ2の表現に対して第１の二倍演算算を実行することにより、点Ｐ2′の表現を計算し、これにより、該第１のパワーシグニチャーを生成し、該第２の回路が、点Ｐ1、Ｐ2の表現を加算する加算演算を実行することにより、点Ｐ1′の表現を生成し、これにより、該加算演算が、該第２のパワーシグニチャーを生成することと
を行うように制御され、
該二倍演算および該加算演算が、常に、該複数のビットｋiの各々に対して同じ順序で実行されるように、該プロセッサが、該第１の回路および該第２の回路を制御し、これにより、該プロセッサが、該複数のビットの各々に対して区別することが不可能なパワーシグニチャー波形を生成することにより、該暗号化システム上のタイミングアタックに対抗する、プロセッサ。
【請求項６】
前記第１の回路および前記第２の回路は、並列に動作する、請求項５に記載のプロセッサ。
【請求項７】
体上に定義された楕円曲線上の点Ｐのｋ倍を計算する場合において、暗号化システム上でタイミングアタックに対抗する方法であって、該方法は、プロセッサによって実行され、該暗号化システム上でタイミングアタックに対抗することは、ｋの異なる値に対して区別することが不可能な該プロセッサのパワーシグニチャー波形を生成するように該プロセッサを動作させることによって行われ、
該方法は、
ａ）数ｋを複数のビットｋiからなる二進ベクトルとして表現することと、
ｂ）該楕円曲線上の点Ｐ1、Ｐ2の順序対の表現を格納することであって、点Ｐ1、Ｐ2は、最大でＰだけ異なる、ことと、
ｃ）該複数のビットｋiの各々を順次選択し、該複数のビットｋiの各々に対して点Ｐ1′、Ｐ2′の組の各点の新しい表現を計算することであって、該選択および該計算は、該複数のビットｋiの各々が選択され、かつ、該表現のうちの１つが点ｋＰの表現となるまで継続し、
該計算は、
ｋiが０である場合には、該プロセッサが、点Ｐ1の表現を二倍することにより、点Ｐ1′の表現を計算することによって、第１のパワーシグニチャーを生成し、該プロセッサが、点Ｐ1、Ｐ2の各々の表現を加算することにより、点Ｐ2′の表現を計算することによって、該第１のパワーシグニチャーとは異なる第２のパワーシグニチャーを生成することと、
ｋiが１である場合には、該プロセッサが、点Ｐ2の表現を二倍することにより、点Ｐ2′の表現を計算することによって、該第１のパワーシグニチャーを生成し、該プロセッサが、点Ｐ1、Ｐ2の各々の表現を加算することにより、点Ｐ1′の表現を生成することによって、該第２のパワーシグニチャーを生成することと
に従って実行される、ことと
を含み、
該二倍すること、または、該加算することは、常に、該複数のビットｋiの各々に対して同じ順序で実行され、これにより、該プロセッサが、該複数のビットｋiの各々に対して、該第１のパワーシグニチャーおよび該第２のパワーシグニチャーからなる区別することが不可能なパワーシグニチャー波形を生成することにより、該暗号化システム上の該タイミングアタックに対抗する、方法。
【発明の詳細な説明】
本発明は、暗号システムにおけるパワーシグニチャーアタック（power signature attack）をできるかぎり減少させる方法および装置に関するものである。
【０００１】
〔発明の背景〕
暗号システムは、通常、それなくしては、その機構を破壊することが不可能な特定の情報を機密に保持することによって、その安全性を維持している。この機密情報は、通常、暗号化プロセッサ中の保護領域に記憶される必要があり、これによって、アタッカーが直接それにアクセスすることを困難にしている。しかしながら、この機密情報を入手するために、様々な手法あるいはアタックが試行されている。これらの一つにタイミングあるいはパワーシグニチャーアタックがある。
【０００２】
タイミングアタック（あるいは、「サイドチャネルアッタク（side channel attack ）」）は、明らかに、暗号化動作期間中に遂行されたコンピュータの逐次演算の結果に基づくものである。このアタックは、通常、暗号化アルゴリズムの処理の一面を利用する。
【０００３】
例えば、最近の、ＲＳＡおよび楕円曲線（ＥＣ）等の公開かぎ暗号化手法は、以下の数学的群上で作用する。すなわち、ＲＳＡの
【０００４】
【数１】
0004582912.tif 000002
【０００５】
、有限体
【０００６】
【数２】
0004582912.tif 000003
【０００７】
における離散対数系、あるいはこれら有限体（finite field）上のＥＣ群（EC group）である。この群演算（group operation ）は、ＲＳＡでは、乗算モジュロｎ（multiplication modulo n ）、ＥＣでは、ポイント加算（addition of points）と呼ばれ、スカラ演算を実行するための特定の方法で逐次的に繰り返される。ＲＳＡでは、演算子は指数（exponent）と呼ばれ、演算はべき乗（exponentiation）と呼ばれ、そして、乗算法は一般的に、繰り返し二乗算−乗算（square-and-multiply ）として知られている。したがって、ナンバー
【０００８】
【数３】
0004582912.tif 000004
【０００９】
および整数０≦ｋ＜ｐが与えられると、上記指数は、その二進表現は
【００１０】
【数４】
0004582912.tif 000005
【００１１】
であるが、値ａk ｍｏｄ  ｎとして、「二乗算−乗算」アルゴリズム（Handbook of Applied Cryptography P.615参照）の繰り返し使用によって算出される。同様に、ｇ（ｘ）∈Ｆp ｍおよび整数０≦ｋ≦ｐm −１が与えられると、ｇ（ｘ）k ｍｏｄ  ｆ（ｘ）がこの方法で算出される。
【００１２】
一方、ＥＣでは、演算子はスカラ乗数（scalar multiplier ）であり、その演算はポイントスカラ乗算（scalar multiplication of a point）と呼ばれ、その方法は、「二倍算−加算（double-and-add）」として知られている。こうして、ｋが正の整数で、Ｐが楕円曲線ポイントである場合には、ｋＰは、「二倍算−加算」法で求められる。これら両方法とも従来公知であり、これ以上の説明は省略する。
【００１３】
前述のように、アタッカーが機密キーを一旦保持すれば（長期あるいはセッションにかかわらず）、アタックされた構成要素に対する署名および暗号解読機密メッセージを偽造することができる。このように、システム内の機密キーの機密性と保全性を維持することが最重要である。
【００１４】
機密キーを獲得するための多くの技術が提案されている。暗号化動作は、逐次的に動作される専用、あるいは汎用のプロセッサにおいて行われる。最近のアタック方法は、例えば、Paul Kochersの記事「Timing attacks on implementations of Diffie-Hellman,RSA,DSS and other systems 」に述べられているように、公開文書で提案されている。これらのアタックは、これらのプロセッサのタイミング分析、すなわち、「ブラックボックス」動作のタイミング分析に基づくものである。例を挙げれば、アタッカーは、機密キー動作中のプロセッサの瞬時の電力使用を補足することによって、パワーシグニチャー（power signature ）を獲得する。パワーシグニチャーは各クロックサイクル毎のゲート動作の数に関連する。上記のパラグラフで述べた各基本動作は、個別のタイミングパターンを発生する。瞬時の電力使用によらないパワーシグニチャー獲得のための他の方法も存在する。
【００１５】
忍耐を要する注意深い、端から端までの波形分析によって、加算−二倍算あるいは二乗算−乗算の演算の順序を分解することができる。標準アルゴリズムを使用すると、指数あるいはスカラ乗算のいずれかのビット毎に、それぞれ、二倍算あるいは二乗算のどちらかが発生する。したがって、二倍算波形が互いに隣接する箇所は、ゼロをもつビット位置を表し、加算波形が存在する箇所は１をもつビットを示す。したがって、これらのタイミング測定が分析され、機密キーの全体が発見されると、当該システムが危険にさらされることになる。
【００１６】
前述の「二乗算−乗算」あるいは「二倍算−加算」技術に加えて、ｋＰを算出する他の方法として、例えば、「二進ラダー（binary ladder ）」あるいはモンゴメリー（Montgomery）法（"Speeding the Pollard and Elliptic Curve Methods of Factorization" by Peter L. Montgomery 参照）が挙げられる。この方法では、一対の点（ｉＰ，（ｉ＋１）Ｐ）のｘ座標が演算される。モンゴメリー法は、例によってより明確に示されるように、モジュラ乗算を実行するための能率的な方法である。群Ｅ（Ｆp ）および楕円曲線上の点Ｐが与えられると、モンゴメリ法は他の点ｋＰを算出するため使用される。順序対である点（ｉＰ，（ｉ＋１）Ｐ）が与えられると、それから、ｋの二進表現である各ビットに、ビットｉが０ならば、次に算出される点セットは（２ｉＰ，（２ｉ＋１）Ｐ）となり、ビットｉが１ならば、次の点セットは（（２ｉ＋１）Ｐ，（２ｉ＋２）Ｐ）となる。すなわち、この対の一番目のものは、ビットが０であるか１であるかによって、二倍算あるいは加算することによって得られる。
【００１７】
プロセッサ中では、二倍算および加算の各々は独特なパワーシグニチャーを発生する乗算演算を伴う。図１（ａ）に概略して示すこれらパワーシグニチャーを観察することによって、アタッカーは、０の列（０ｓ）および１の列（１ｓ）のシーケンスを引出し、そして、使用されたスカラあるいは指数を引き出す。
【００１８】
モンゴメリ法は、前述のようなストレートな「二倍算−加算」による極めて高い能率性のため、ＥＣ暗号システムに好適に使用される。
【００１９】
上記のようなモンゴメリ法に基くアタックは、ＲＳＡ機密キー動作が行われている際に特に重大である。ダン・ボネー等（Dan Boneh et al.）によって出版された最近の文書（題名："An Attack On RSA Given A Small Fraction Of The Private Key Bits" ）によれば、低い公開指数（low public exponent ）を有するＲＳＡに対しては、機密キービット列の１／４が与えられると、敵は機密キー全体を確定できることが示されている。このアタックに上述のパワーシグニチャーアッタクを組み合わせると、ＲＳＡ法は非常に攻撃されやすいものになる。
【００２０】
そこで、本発明の目的は、特に、機密キー動作においてモンゴメリ法を使用する場合に、タイミングアッタク成功の危険を極力減少させることができるシステムを提供することにある。
【００２１】
〔本発明の概要〕
本発明によれば、体（field ）上に定義された楕円曲線上の点Ｐの倍数ｋ（multiple k）を算出する方法が提供されており、この方法は、以下のステップを含んでいる。すなわち、
ａ）ナンバーｋをビット列ｋi の二進ベクトル（binary vector ）として表し；
ｂ）点Ｐ1 およびＰ2 の順序対を形成し、点Ｐ1 およびＰ2 は最大でＰだけ異なり；そして、
ｃ）順次上記各ビット列ｋi を選択し、上記ｋi のそれぞれに対して；
i）ｋi が０のとき、
ii）点Ｐ1 ′、Ｐ2 ′の新しいセットを算出し、上記点Ｐ1 ′は一番目の点Ｐ1 を二倍算して得られたものであり；そして、
iii）上記点Ｐ2 ′は点Ｐ1 およびＰ2 を加算して得られたものであり；
あるいは、ｋi が１のとき、
iv）点Ｐ1 ′、Ｐ2 ′の新しいセットを算出し、上記点Ｐ2 ′は二番目の点Ｐ2 を二倍算して得られたものであり；そして、
v）上記点Ｐ1 ′は点Ｐ1 およびＰ2 を加算して得られたものである。
これにより、上記二倍算あるいは加算が、常に上記ビット列ｂi の各々に対して同じ順序で実行され、これによって上記方法におけるタイミングアタックを極小化する。
【００２２】
本発明の他の態様においては、上記体は、Ｆ2 m あるいはＦp である。
【００２３】
本発明のさらに他の態様においては、上記方法を実行するプロセッサのハードウェアが備えられている。
【００２４】
〔好適な実施形態の詳細な説明〕
本発明の好ましい実施形態についての上記および他の特徴点は、添付した図面を参照した以下の詳細な説明によって明白になるであろう。
【００２５】
図２に示すように、Ｆ2 m あるいはＦp の体（field ）上に定義された楕円曲線上の点の倍数（multiple）を算出するための一般化されたアルゴリズムは、符号２０によって一般的に示される。本実施形態では、点Ｐは本システムのパラメータである。このアルゴリズムは、点ｋＰの倍数を算出し、ここで、スカラｋは機密キーか他の機密値の場合がある。このスカラｋは、レジスタ中でビット列ｂI ２４を有する二進ベクトルとして表される。一対の要素（elements）（ａ，ｂ）が形成され、ここで、ａおよびｂは、最大でＰだけ異なる楕円曲線上の点であるか、あるいは、群Ｆp の場合には、ａおよびｂは倍数ｇだけ異なる要素ｇである。
【００２６】
本実施形態では、楕円曲線法を考慮するため、この要素ａおよびｂは、順序対である点ｉＰおよび（ｉ＋１Ｐ）のｘ座標に相当する。楕円曲線点のｘ座標を得てそれを利用するための改良モンゴメリ法（An improved Montgomery method ）は、当発明に参照のため取り入れられた、本出願人による継続中の米国特許出願Ｎｏ．０９／０４７，５１８に述べられている。スカラｋの二進表現の一番目のビットで始まるビットｂi が評価される。このビットの値によって、二つのアルゴリズム２６あるいは２８の一つが選択される。ブロック２５ａに示されたように、このビットが０である場合には、入力対（ａ，ｂ）の一番目の要素ａは二倍算され、出力対（ａ′，ｂ′）の一番目の要素ａに記憶される。一方、入力の一番目と二番目の要素が加算されａ＋ｂ、出力対（ａ′，ｂ′）の二番目の要素ｂ′に配置される。ブロック２５ｂに示されたように、このビットが１である場合には、入力対（ａ, ｂ）の二番目の要素ｂは二倍算され、出力対（ａ′，ｂ′）の二番目の要素ｂに記憶される。一方、一番目と二番目の入力要素が加算され、すなわち、ａ＋ｂ、出力対（ａ′，ｂ′）の一番目の要素ａ′に配置される。これらのステップは、スカラｋのすべてのビットに対して繰り返される。
【００２７】
こうして、図１（ｂ）に示すように、「二倍算」の演算に引き続いて「加算」の演算を各ビットに対して実行することにより、一貫したパワーシグニチャー波形が生成されるため、アタックを試みる者にほとんど情報を与えない。この動作は、反対の順序で遂行されてもよい。すなわち、一番目に「加算」の演算、ついで「二倍算」の演算を実行する。ＲＳＡ法では、同様の演算は、「二乗算と乗算」である。
【００２８】
より詳細には、「二進ラダー」法を使用してｋＰを算出するとすれば、いくつかの計算後、ｘ座標（ｉＰ，（ｉ＋１）Ｐ）を得る、すなわち、図４に概略して示すように、ｋの処理されたｉビット列を得る。処理すべき次のビットが０の場合には、ｘ座標（の順位対）（２ｉＰ，（２ｉ＋１Ｐ）Ｐ）を形成しなければならない。次のｂｉ＋ｂが１の場合には、ｘ座標（の順位対）（（２ｉ＋１）Ｐ，（２ｉ＋２）Ｐ）を形成しなければならない。
【００２９】
「二倍算」式は、入力にかかわらず、おおよそ同じ量の電力（および時間）を必要とすると考えられる。加算式は、入力にかかわらず、同じ量の電力（および時間）を必要とすると考えられる。しかしながら、二倍算式の実行には、加算式の実行と異なる量（通常のモンゴメリ式使用の場合には、より少ない量）の電力が必要とされる。
【００３０】
このことから、パワーバーをモニターすることによって、「二倍算」と「加算」とを区別することができる。ここで、これらの式を一貫した順序で実行すれば、処理中の１のパワーシグニチャーおよび処理中の０のパワーシグニチャーは、区別不可能となる。各々が「二倍算」のパワーシグニチャーと、それに続く「加算」のパワーシグニチャーからなる。
【００３１】
両方の場合において、評価の順序を逆転しても、パワーシグニチャーは、区別不可能である。
【００３２】
このことから、楕円曲線上のｋＰを算出する本方法は、電力消費の統計量を通じて整数ｋを明示することを避けるため、より好適である。「モンゴメリ」、「二倍算」および「加算」式を使用すると、本方法は、特に反転をさける射影形式を用いる場合にも有効になる。
【００３３】
効率の面においては、「二進ラダー」法の各ステップにおいて、二つの独立した演算が実行されねばならないことが、注目される。すなわち、「加算」式の結果は「二倍算」式に対して必要とされず、その逆も成り立つ。このことは、能率的な並列的ハードウエア処理を考慮に入れる。
【００３４】
そこで、図３を参照して、本方法の並列的ハードウエア処理の概略を符号３０によって示す。この処理においては、第一、第二専用プロセッサが備えられている。第一プロセッサ３２は、「二倍算」もしくは「二乗算」またはその両方の演算を行い、一方、第二プロセッサ３４は、「加算」もしくは「乗算」またはその両方の演算を行う。主プロセッサ３６は、３２と３４のどちらの専用プロセッサが起動されるかを決定する。
【００３５】
各プロセッサ３２および３４が同時に駆動される（ただし、回路が使用される時期は異なる）。これら回路の入力および出力は、上述の場合にしたがって、すなわち、ビットｂi ＝０あるいはビットｂi ＝1 を使用して、操作される。この簡単な例は、直列的処理に比べてほぼ２倍のスピードアップをもたらす。少なくとも従来の射影モンゴメリ式の場合には、加算回路は二倍算回路より時間が多くかかり、より複雑であることが注目される。二倍算回路を加算回路より速く終了させる必要はないので、より遅く設定してもよい。実際には、このことは二倍算回路をより安く構成できることを意味する。
【００３６】
本発明について、ある特定の実施形態に基づいて説明したが、特許請求の範囲として記載された本発明の精神および範囲内において、本実施形態が様々に変形されることは明白であろう。
【００３７】
本発明において、排他的独占権を求める具体的内容は、特許請求の範囲に記載した通りである。
【図面の簡単な説明】
【図１】  （ａ）および（ｂ）は、プロセッサのパワー使用シグニチャー（processor power usage signature ）を示す概略図である。
【図２】  本発明の一実施形態による方法を示すフロー図である。
【図３】  本発明の一実施形態による方法を実行する対称プロセッサ（symmetric processor ）を示す概略図である。
【図４】  二進の整数ｋを示す概略図である。
【図１】
0004582912.tif 000006
【図２】
0004582912.tif 000007
【図３】
0004582912.tif 000008
【図４】
0004582912.tif 000009