(57)【特許請求の範囲】
【請求項１】
暗号システムのプロセッサユニットによって、群の選択された群の元（Ｐ）に対して群演算を整数（ｂ）回実行する方法であって、前記プロセッサユニットは、ステートコントローラと、計算ユニットと、第１のレジスタと、第２のレジスタとを備え、
前記方法は、
前記第１のレジスタにおいて、前記整数（ｂ）を表す二進ベクトル（ｂｉ）として前記整数（ｂ）を受信するステップと、
前記第２のレジスタにおいて、中間元（Ｑ）を群の単位元へと初期化するステップと、
前記ステートコントローラが、前記第１のレジスタから前記ベクトルの連続するビットを選択し、前記選択されたビットのそれぞれについて、
前記計算ユニットが、前記第２のレジスタにおいて、前記中間元（Ｑ）に対して前記群演算を実行することにより、第１の新しい中間元を導出することと、
前記ステートコントローラが、前記第２のレジスタにおいて、前記中間元（Ｑ）を前記第１の新しい中間元に置き換えることと、
前記計算ユニットが、前記中間元（Ｑ）と、前記選択されたビットが１である場合の前記群の元（Ｐ）と前記選択されたビットが０である場合の前記群の元（Ｐ）の逆元とからなる群より選択された元とに対して前記群演算を実行することにより、第２の新しい中間元を導出することと、
前記ステートコントローラが、前記中間元（Ｑ）を前記第２の新しい中間元に置き換えることと
を実行するステップと、
前記計算ユニットが、前記中間元（Ｑ）と前記逆元とに対して前記群演算を実行することにより、結果を取得するステップであって、それによって、前記二進ベクトル（ｂｉ）の各ビットは、前記群演算が同じパワーを用いて同じ時間実行されるように処理され、それにより、前記暗号システムに対するタイミングアタックを最小化する、ステップと
を含む、方法。
【請求項２】
前記群は、乗算群Ｆｐ*であり、前記群の元（Ｐ）は、整数であり、前記群演算は、乗算であり、前記逆元は、前記群の元（Ｐ）の乗算逆数に対応する値を有する、請求項１に記載の方法。
【請求項３】
前記群は、楕円曲線の加算群
【数１】
0004699610.tif 000002
であり、前記群の元（Ｐ）は、前記楕円曲線上のポイントであり、前記群演算は、前記楕円曲線上のポイントの加算であり、前記逆元は、前記ポイントの負数（−Ｐ）である、請求項１に記載の方法。
【請求項４】
前記群は、楕円曲線の加算群Ｅ（Ｆｑ）であり、前記群の元は、前記楕円曲線上のポイントであり、前記群演算は、前記楕円曲線上のポイントの加算であり、前記逆元は、前記ポイントの負数（−Ｐ）である、請求項１に記載の方法。
【請求項５】
前記整数（ｂ）は、暗号において用いられるプライベートキーｋである、請求項１に記載の方法。
【請求項６】
前記ビットの所定数は、全体のベクトルを表す、請求項１に記載の方法。
【請求項７】
前記二進ベクトル（ｂｉ）は、複数のビットを含み、各ビットは、０を表す値を有するか、１を表す別の値を有する、請求項１に記載の方法。
【請求項８】
請求項１〜７のいずれか一項に記載の方法を実行するために構成された前記プロセッサユニットを備える暗号ユニット（１８、２０）。
【発明の詳細な説明】
本発明は、暗号システムの分野に関するものであり、特に暗号システムへのタイミングアタックを防止するための方法および装置に関する。
【０００１】
（発明の背景）
一般的に、暗号システムは、情報の特定の一部が秘密に保たれているという事実によって安全性を担保しており、この事実がなければ、スキーム（scheme）を破壊することはほとんど困難である。一般的に、当該秘密情報は安全境界内に蓄積されていなければならず、これによりアタッカー（attacker）が直接それに達することを困難にしている。しかし、上記秘密情報を獲得するために種々のスキームあるいはアタックが試みられてきた。これらのひとつが、タイミングアタック（timing  attack）である。
【０００２】
背景では、ＲＳＡおよび楕円曲線（elliptic  curve:EC）等の現行の公開鍵（パブリックキー）暗号スキームが数学の群Ｆ*PとＥ（Ｆｑ）とのそれぞれに作用する。ＲＳＡにおいて乗算モジューロ（modulo）ｐと称される群演算およびＥＣにおけるポイントの追加は、特定の方法で繰り返されることによりスカラー演算を実行する。ＲＳＡにおいては、オペランド（operand）は指数（exponent）と称され、該演算は指数化（exponentiation）と称され、乗算方法は、通常二乗および乗算を繰り返すものとして知られている。故に、ａ∈ＦPを満たす数ａ、および０≦ｋ＜ｐを満たす整数であって、二進法で表すとｋ＝Σti=0ｋi２iをみたす指数ｋについて、ａk  mod  ｐの値を二乗および乗算アルゴリズムを繰り返すことによって計算することができる。同様に、g(x)∈ＦPｍを満たす数g(x)、および０≦ｋ≦ｐm−１なる整数ｋについて、g(x)k  mod  f(x)をこの方法によって計算することができる。
【０００３】
一方、ＥＣにおいては、オペランドはスカラー乗算子であって、上記演算はポイントのスカラー乗算と称され、上記方法は二倍および加算法として知られている。故に、ａが正の整数であって、Ｐが楕円曲線ポイントである場合、ａＰを二倍および加算法によって求めることができる。これらの方法はいずれも当業者に良く知られたものであるので、これ以上の説明は行わない。
【０００４】
ＲＳＡにおいては、全ての指数化演算のうち半分がプライベートキー（private  key）を使用する。これに対してＥＣにおいては全てのスカラー乗算は、ロングタームプライベートキー（long  term  private  key）あるいはセッションプライベートキー（session  private  key）のいずれかを使用する。これらの場合の何れにおいても、指数化または乗算演算は万一の場合でも逆転させることが困難であるので、プライベートキーは安全である。これは、離散的ログ問題あるいは素因数分解の困難性の為である。上記したように、アタッカーは一旦プライベートキー（あるいはロングタームもしくはセッション）を所有すると、アタックの対象に対して、シグニチャー（signature）を偽造して秘密のメッセージを解読することができる。よって、システムにおけるプライベートキーの秘密性あるいは保全性を維持することが極めて重要である。
【０００５】
プライベートキーを得るための多くの技術が提案されてきた。コード化演算は、サイクリック（cyclic）な方法で動作する特定の目的あるいは一般的な目的のプロセッサーにおいて実行されている。公知文献に開示された近年のアタック方法は、これらのプロセッサーのタイミング分析あるいはいわゆる”ブラックボックス”演算のタイミング分析に基づく。一例では、プライベートキー演算を通じてプロセッサーの瞬間電力使用量を得ることによって、アタッカーはパワーシグニチャー（power  signature）を得る。上記パワーシグニチャーは、個々のクロックサイクルによって動作するゲート数に関する。上記段落で説明した各基本演算は、離散タイミングパターンを生成する。瞬間電力使用量以外にも、パワーシグニチャーを得るための方法が存在する。
【０００６】
波形の端点間の煩雑且つ慎重な分析により、加算および二倍演算あるいは二乗および乗算演算の順序を分解することができる。二倍あるいは二乗は、それぞれ指数あるいはスカラー乗算子のいずれのビットについても別個に発生しなければならない。それゆえ、二倍波形が互いに隣接する箇所においては、ゼロのビットポジションを示し、加算パターンのある箇所においては、１を示す。それゆえ、これらのタイミング測定を分析することによって、完全なシークレットキー（secret  key）を発見することができ、システムを妥協させることができる。ゆえに、タイミングアタックを成功させるリスクを最小限にするシステムが必要である。
【０００７】
（発明の概要）
本発明は、実行されている演算とは無関係に、一定の時間周期でプロセッサーによって暗号演算が実行され、個々のビットスカラーの処理あるいはあらゆる値の指数について一定量の時間を必要とする暗号システムを提供することを目的とする。
【０００８】
本発明は、群から選択された元について整数回実行される群演算の結果を決定するための方法であって、
（ａ）上記整数を二進ベクトルとして表現し、
（ｂ）中間元を群の単位元に初期化し、
（ｃ）もっとも左側のビットから開始して上記ベクトルの連続するビットを選択し、上記選択されたビットのそれぞれについて、
（ｉ）新しい中間元を導出する上記中間元に上記群演算を実行し、
（ｉｉ）上記中間元を上記新しい中間元に置き換え、
（ｉｉｉ）上記中間元、および上記選択されたビットが１である場合の上記群の元と上記選択されたビットがゼロである場合の上記群の元の逆元とから成る群から選択される元に対して上記群演算を実行し、
（ｉｖ）上記中間元を上記新しい中間元に置き換え、
（ｄ）上記中間値および上記最終の選択されたビットがゼロである場合の逆元に対して上記群演算を実行し；上記中間元を置き換えることにより結果を求め、上記合計の各ビットが実質的に同一の演算により処理されることにより上記暗号システムへのタイミングアタックを最小化するステップを含むことを特徴とする。
【０００９】
本発明の上記特徴点および他の特徴点は、添付する図面を参照しつつ例示することにより説明する。
【００１０】
（実施形態の詳細な説明）
図１に示すように、セキュアデータコミュニケーションシステム（secure  data  communication  system）１０は、コミュニケーションチャネル１６により接続された１対のコレスポンデント（correspondents）、すなわち送信者Ａ（１２）および受信者Ｂ（１４）を含む。各コレスポンデントＡおよびＢ（１２，１４）は暗号ユニット１８，２０を含み、各暗号ユニット１８，２０はそれぞれデジタル情報を処理するとともに、チャネル１６を介してそれを伝達するための準備をする。
【００１１】
一般的に、送信者Ａは、送信者のパブリックキーｙと、メッセージｍと、送信者のショートタームパブリックキーｋと、送信者ＡのシグニチャーＳとを含むデータストリングをアセンブルする。アセンブルされた後にデータストリングは所望の受信者Ｂに向けて送信され、受信者ＢはＡのパブリックキーを用いて該シグニチャーを確認する。このパブリックキー情報は、認証オーソリティ（certification  authority:ＣＡ）２４から獲得されるかもしれないし、場合によってはメッセージとともに送信されるかもしれない。
【００１２】
たとえば、ＲＳＡのパブリックキー暗号においては、ＢはＡに対するメッセージｍを暗号化し、Ａがメッセージｍを解読する。メッセージｍを暗号化するために、ＢはＡのパブリックキー（ｎ，ｅ）を得るとともに、メッセージを［０，ｍ−１］の間の整数として表現する。次に、Ｂはｃ＝ｍe  mod  ｎを算出し、暗号化テキストｃをＡに送信する。エンティティＡは、プライベートキーｄを用いることによりｍ＝ｃd  mod  ｎとしてｃからメッセージｍを復元する。ｃd  mod  ｎの計算（モジューロ指数化）は、公知の二乗および乗算アルゴリズムを使用することにより実行される。同様の計算がＲＳＡにおける符号化に要求され、符号化のために、ＥＣＣ等の離散的ログシステムにおける暗号化および解読が必要とされる。
【００１３】
計算で用いられる値はビットベクトルとして表現され、該ビットベクトルは、使用する特定の暗号化スキームに対応する暗号化プロセッサにより計算される。それゆえ、図２に示すように、１で終了するあらゆるビットベクトルは＋１および−１の項からなる全非ゼロベクトルとして記録される。ゼロで終了するエレメントについては、最後のゼロを記録された形式で維持するか、あるいは更に最後のゼロが上記のルールにより処理された後の修正として−１動作を実行する必要がある。後に明白になるように、修正動作を行うことが好ましい。
【００１４】
図３に、楕円曲線上のポイントＰにおける整数乗数ｂを計算するためのアルゴリズムステートマシンの具体例を参照番号３０として示す。本実施形態においては、処理されるビットベクトルｂはステートマシン３０に付与される。処理の結果は、値ｂＰであって、Ｐは楕円曲線上の座標（ｘ，ｙ）を有するポイントである。ステートマシン３０はカウンターｉとともに初期化され、該カウンターｉはベクトルｂのビット数Ｎおよびレジスタに蓄積された中間値Ｑにセットされている。ｂの第１ビット（ＭＳＢ）がエンカウンタされる（encountered）と（第１非ゼロビットではない）、ステートマシンのステートＨ０へのエントリが発生する。ステートＨ０においては、中間値Ｑのコンテンツ（contents）が二倍されるとともにベースポイントＰがそこに加えられる。ビットは連続して処理され、現在のステートＨ０に戻るか、あるいは次のステートＨ１に進むかのいずれかの変化を起こす。ステートＨ１においては、Ｑが二倍され、ベースポイントＰが減じられる。次のビットがゼロである場合、次のステートは常にＨ１である。次のビットが１である場合、次のステートは常にＨ０である。現在のステートがＨ０である場合は常に加算（＋Ｐ）が起こり、それ以外の場合には減算（−Ｐ）が起こる。すべてのビットが計算されると、ｂＰを結果とする終了ステートへと制御が進行する。Ｈ０中に出口条件に達する場合は、最後に結果から減算（−Ｐ）を行うことが必要である。
【００１５】
擬似コード形式のステートマシンの具体例は、Ｈステートのための汎用蓄積ビットを利用できることが必要である。図４は、汎用データおよび制御メカニズムが利用可能であるステートマシンの擬似コード具体例である。ループ内のすべての可能な実行パスについて実行時間およびパワーが同一であればタイミングアタックを防止することができる。本具体例では、ラインＬ５，Ｌ６およびＬ７からなる実行パスに要する時間は、ラインＬ５，Ｌ８およびＬ９からなる実行パスに要する時間と同一である。これは、分岐命令（ＩＦ）が、偽（false）および真（true）条件についても同様の時間で実行されなければならないことを示す。
【００１６】
更に、加算および減算演算は同じ時間で行わなければならない。Ｐの負の値を加算することにより、これはより明らかに可能である。アルゴリズムにおいてラインＬ１４およびＬ１５を除く他の全てのラインの実行時間は非クリティカル（non-critical）であって、タイミングアタックを防止できることについて注意されたい。これら２つのラインが実行される場合は必要時間が増加し、最終Ｈステートがゼロであったことが明らかになる。これは、スカラーの最終ビットがゼロであったことを明らかにすることに等しい。これは避けられないが、スカラー乗数のシングルビットを明らかにするのみである。
【００１７】
特定の計算装置の適用においては、汎用データ蓄積領域あるいは汎用割当ておよびテストオペレータが存在しない傾向がある。この場合、Ｈステート制御は通常の方法で加算されることができない。その代わり、離散コードパスを通じて分岐することによりステートを符号化することが必要である。
【００１８】
図５は”ステートの無い（state-less）”擬似コード具体例を示す。各コード実行パスは離散ステートに対応する。一般的にこれはコード膨張を引き起こすが、ここで必要なのは２つのショートパスのみである。ここにおいても上記したのと同様に、ループ内のすべての可能な実行パスについて実行時間およびパワーが同一であればタイミングアタックを防止することができる。本具体例においては、ラインＬＬ３，ＬＬ４およびＬＬ５からなる実行パスにはラインＬＬ６，ＬＬ７およびＬＬ８からなる実行パスと同様の時間が必要である。更に、ＬＬ９，ＬＬ１０およびＬＬ１６のパスは、ＬＬ９およびＬＬ１１のパスと同様の時間およびパワーで実行されなければならない。これは、（次のロケーションへの）フォールスルー（fall  through）と同様に（新しいロケーションへの）分岐について、条件分岐命令が同じ時間を必要とする構造については真であろう。ラインＬＬ１１，ＬＬ１２およびＬＬ１３は、ラインＬＬ１６，ＬＬ１７およびＬＬ１８と等しい実行時間およびパワーであることに注目されたい。これもまたタイミングアタックを防止するために必要である。他の場合は、Ｈステートインフォメーションが明らかにされる。上記具体例においては、ループがＨ０パスを終了したときにＬＬ１４における最終の修正減算が必要である。これにより最終Ｈパスあるいは同等のスカラーの最終ビットが明らかになる。
【００１９】
図６には、二乗および乗算演算の擬似コード具体例が参照番号６０で示されており、これに対応するステートマシン具体例が図７に示されている。本具体例では、指数ビットベクトルｂがステートマシン６０に付与される。処理の結果として、Ｍbなる値が計算される。再びカウンターはベクトルｂの長さＮに初期化されるとともに、累算器Ｑは１に初期化される。ステートマシンのステートＨ０へのエントリは、ビットベクトルｂのＭＳＢと共に開始する。上記したように、ビットは連続して処理され、現在のステートＨ０へ戻るか、あるいは次のステートＨ１に進むかのいずれかの遷移を生じる。ステートＨ０においては、累算器ＱのコンテンツはベースＭにより二乗および乗算される。ステートＨ１においては、累算器はベースＭにより二乗および除算される。次のビットが０である場合は、次のステートは常にＨ１であり、次のビットが１である場合は次のステートは常にＨ０である。現在の状態がＨ０である場合は常に乗算が発生し、それ以外は除算が発生する。上記したように、全てのビットが消費されると、制御は終了ステートにて終了する。Ｈ０中に出口条件に達する場合は、最終ラインをベースＭにより割ることが必要である。
【００２０】
図８は、ステートコントローラ８２が、上記したエステートコード（estate  code）を実行するようにプログラムされている一般的なプロセッサの具体例を示す。モジューロ演算および／または有限フィールド計算ユニット８４が、二乗および乗算の計算ならびにポイントの加算／減算のためにそれぞれ設けられている。カウンタ８６およびレジスタｂはコントローラ８２の連続オペレーションのタイミングのためのステートコントローラに結合されている。
【００２１】
本発明は特定の実施形態および特定の用途に関して記載されたが、添付する特許請求の範囲のような本発明の精神から外れることなく、種々の態様変更が発生することが可能である。
【００２２】
明細書中において使用した単語および表現は、記載の為の単語として用いられており、これに限定されるものではない。このような単語および表現は、記載された特徴の均等物を排除する目的で用いられるものではなく、本発明の特許請求の範囲の範囲内において種々の態様変更が可能である。
【図面の簡単な説明】
【図１】  図１は、データコミュニケーションシステムを説明する概要図である。
【図２】  図２は、二進数記録スキームを説明する概要図である。
【図３】  図３は、ポイントのスカラー乗算のコンパイリングを説明するステートマシンである。
【図４】  図４は、図３のステートマシンの擬似コード具体例である。
【図５】  図５は、非ステートマシン擬似コード具体例である。
【図６】  図６は、二乗および乗算スキームのための擬似コードおよびステートマシン具体例である。
【図７】  図７は、二乗および乗算スキームのための擬似コードおよびステートマシン具体例である。
【図８】  図８は、本発明の一具体例に係る方法を実施する装置の一般化構造ダイアグラムである。
【図１】
0004699610.tif 000003
【図２】
0004699610.tif 000004
【図３】
0004699610.tif 000005
【図４】
0004699610.tif 000006
【図５】
0004699610.tif 000007
【図６】
0004699610.tif 000008
【図７】
0004699610.tif 000009
【図８】
0004699610.tif 000010