(57)【要約】【課題】  反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理方法を提供すること。【解決手段】  ウィンドウサイズが２である、反復的二進法の左から右への「倍加および加算」タイプアルゴリズムを用いる、データアイテムＰの倍数ｋを計算する、データ処理方法が提供される。少なくとも１つのＰの倍数を含む、データアイテムの選択肢が提供される。アルゴリズムの特定の反復において、アルゴリズムの「加算」部分において用いられるための、その反復に必要なＰの倍数が決定される。その後、必要な倍数に依存して倍数が選択肢から選択され、必要な倍数と選択された倍数との関係に依存して、調節インジケータが設定される。後に続く反復において、必要な倍数は、以前の反復からの調節インジケータに依存して、決定される。アルゴリズムの「倍加」部分において用いられる乗数は、４である。【選択図】  図１０
2005020735.tif 000002
【特許請求の範囲】
【請求項１】
反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理方法であって、ここで、ｂは、倍数ｋの底であり、ｗはウィンドウサイズであり、該方法は、
少なくとも１つのＰの倍数を含むデータアイテムの選択肢を提供するステップと、
該アルゴリズムの特定の反復について、その反復に必要なＰの倍数を決定し、該必要な倍数に依存して該選択肢から選択した倍数を用い、該必要な倍数と該選択された倍数との関係に依存して調節インジケータを設定するステップと、
後に続く反復において、前回の反復からの該調節インジケータに依存して該必要な倍数を決定するステップと
を包含する、方法。
【請求項２】
前記選択された倍数を、利用可能である場合、倍数の記憶場所から取り出し、そうでない場合、該選択された倍数を計算するステップをさらに包含する、請求項１に記載の方法。
【請求項３】
後に続く取り出しのため、前記倍数の記憶場所に新たに計算された倍数を格納するステップをさらに包含する、請求項２に記載の方法。
【請求項４】
前記選択肢内の少なくとも１つの倍数を事前計算するステップと、該少なくとも１つの事前計算された倍数を、後に続く取り出しのため、前記倍数の記憶場所に格納するステップをさらに包含する、請求項２または３に記載の方法。
【請求項５】
前記選択肢内の全ての前記倍数は、前記倍数の記憶場所から利用可能である、請求項２、３または４に記載の方法。
【請求項６】
前記倍数の記憶場所は、前記データアイテムＰを保持する別個の領域を含む、請求項２〜５のいずれか１つに記載の方法。
【請求項７】
前記選択肢は、反復において必要であると決定され得る倍数を全ては含まない、請求項１〜６のいずれか１つに記載の方法。
【請求項８】
前記選択肢が含む倍数は、ｂｗ個よりも少ない、請求項７に記載の方法。
【請求項９】
前記選択肢が含む倍数は、０．７５＊ｂｗ個よりも少ない、請求項８に記載の方法。
【請求項１０】
前記選択肢は、少なくとも０．５＊ｂｗ個の倍数を含む、請求項９に記載の方法。
【請求項１１】
前記選択肢は、最も近い整数個の倍数に切り上げられた、０．５＊ｂｗ個の倍数を含む、請求項１０に記載の方法。
【請求項１２】
前記選択肢は、交互の倍数を含む、請求項６〜１１のいずれか１つに記載の方法。
【請求項１３】
前記選択肢は、奇数の倍数のみを含む、請求項６〜１２のいずれか１つに記載の方法。
【請求項１４】
前記選択肢は、ゼロ倍数を含まない、請求項６〜１３のいずれか１つに記載の方法。
【請求項１５】
前記調節インジケータは、前記必要な倍数と前記選択された倍数との間の関係の有限集合のうちの１つを示すように設定可能であり、必要な倍数が前記選択肢から利用可能でない場合、該集合内の利用可能な関係インジケータに依存して前記選択肢から他の倍数が選択される、請求項６〜１４のいずれか１つに記載の方法。
【請求項１６】
前記選択肢内の前記倍数および前記関係インジケータの集合が、Ｐの任意の倍数ｋの正常な計算を可能にするために十分な個数である、請求項１５に記載の方法。
【請求項１７】
必要な倍数が前記選択肢から利用可能でない場合、該選択肢から利用可能な最も近い倍数が選択されるか、または、１つより多い倍数が同等に近い場合、最も近い倍数のうちより高い倍数が選択される、請求項６〜１６のいずれか１つに記載の方法。
【請求項１８】
必要な倍数が前記選択肢から利用可能でない場合、該選択肢から利用可能な次の最も高い倍数が選択される、請求項６〜１６のいずれか１つに記載の方法。
【請求項１９】
前記調節インジケータは、前記必要な倍数から前記選択された倍数を引いたものに等しい補正倍数を示すように設定される、請求項１〜１８のいずれか１つに記載の方法。
【請求項２０】
前記後に続く反復における前記必要な倍数は、前記補正倍数をｂｗでスケーリングして、その反復において考慮されるウィンドウ内の倍数ｋの値に加算することによって、決定される、請求項１９に記載の方法。
【請求項２１】
前記選択肢は、正の倍数のみを含むが、概念的には、対応する負の倍数を含むことも考えられる、請求項１〜２０のいずれか１つに記載の方法。
【請求項２２】
前記必要な倍数が負であるか、または、前記選択肢における最も小さい正の倍数よりも小さいことが決定される場合、該選択肢の概念上の負の倍数を考えることによって、該選択肢から倍数が選択される、請求項２１に記載の方法。
【請求項２３】
前記選択肢から選択された前記倍数が、前記概念上の負の倍数のうちの１つである場合、前記選択肢からの対応する正の倍数を用いて減算演算が行われる、請求項２１または２２に記載の方法。
【請求項２４】
最終反復において設定される調節インジケータに基づいて、最終調節を適用するステップをさらに包含する、請求項１〜２３に記載の方法。
【請求項２５】
１つ以上のデータアイテム倍数に関わる演算は、３種類の演算、すなわち、（ａ）ゼロでないデータアイテム倍数の倍加、（ｂ）ゼロでなく、等しくないデータ、逆数でないアイテム倍数の加算または減算、および（ｃ）ゼロデータアイテム倍数０．Ｐに関わる任意の演算のうちの１つに分類され得、最終ステップにおける演算分類のシーケンスは、前記最終反復において設定される前記調節インジケータから独立している、請求項２４に記載の方法。
【請求項２６】
前記反復的ｂｗ関連ウィンドウアルゴリズムは、左から右への（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）「ｂを乗算し、加算する」タイプのアルゴリズムであり、該アルゴリズムの該「ｂを乗算」する部分において用いられる乗数は、ｂｗであり、前記必要な倍数は、該アルゴリズムの「加算」部分において用いられる倍数である、請求項１〜２５のいずれか１つに記載の方法。
【請求項２７】
ｂが２に等しく、前記反復的ｂｗ関連ウィンドウアルゴリズムが、「倍加および加算」タイプのアルゴリズムであり、該アルゴリズムの「倍加」部分において用いられる乗数が２ｗである、請求項２６に記載の方法。
【請求項２８】
ｋは符号付きの二進数値であり、前記第１の反復において、ｋの先頭ビットは、前記必要な倍数を決定する場合、負の重みが付けられる、請求項２７に記載の方法。
【請求項２９】
ｋは符号付きの二進数値であり、ｋの先頭ビットを切り捨て、補償するために、前記第１の反復において調節インジケータを設定するステップをさらに包含する、請求項２７に記載の方法。
【請求項３０】
１つ以上のデータアイテム倍数に関わる演算は、３種類の演算、すなわち、（ａ）ゼロでないデータアイテム倍数の倍加、（ｂ）ゼロでなく、等しくなく、逆数でないデータアイテム倍数の加算または減算、および（ｃ）ゼロデータアイテム倍数０．Ｐに関わる任意の演算のうちの１つに分類され得、演算分類のシーケンスは、前記ｋの値から独立している、請求項１〜２９のいずれか１つに記載の方法。
【請求項３１】
１つ以上のデータアイテム倍数に関わる演算は、３種類の演算、すなわち、（ａ）ゼロでないデータアイテム倍数の倍加、（ｂ）ゼロでなく、等しくなく、逆数でないデータアイテム倍数の加算または減算、および（ｃ）ゼロデータアイテム倍数０．Ｐに関わる任意の演算のうちの１つに分類され得、演算分類のシーケンスは、前記ｋの値から独立しており、反復が、ｗ回の倍加演算および１回の加算／減算演算を含み、それぞれが、前記ｋの値とは無関係に生成される結果に寄与する、請求項２９に記載の方法。
【請求項３２】
前記ゼロ倍数データアイテム、すなわち、０．Ｐを用いるか、または０．Ｐが得られる演算が行われない、請求項１〜３１のいずれか１つに記載の方法。
【請求項３３】
倍加演算に等しい加算演算が行われない、請求項１〜３２のいずれか１つに記載の方法。
【請求項３４】
さらなるデータアイテムＱの倍数ｍも、前記反復アルゴリズムの間計算されて、２つの別個の調節インジケータを、進行中の乗算に対して１つずつ用いることによって、結果（ｋ．Ｐ＋ｍ．Ｑ）を生成する、請求項１〜３３のいずれか１つに記載の方法。
【請求項３５】
調節インジケータは、該インジケータが設定された反復の直後の反復において適用される、請求項１〜３４のいずれか１つに記載の方法。
【請求項３６】
前記データアイテムＰは、楕円曲線点である、請求項１〜３５のいずれか１つに記載の方法。
【請求項３７】
データを暗号化または復号する、暗号化データ処理方法におけるステップである、請求項１〜３６のいずれか１つに記載の方法。
【請求項３８】
反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理装置であって、ここで、ｂは、倍数ｋの底であり、ｗはウィンドウサイズであり、該装置は、
少なくとも１つのＰの倍数を含むデータアイテムの選択肢を提供するデータアイテム提供手段と、
該アルゴリズムの特定の反復について、その反復に必要なＰの倍数を決定する、決定手段と、
該必要な倍数に依存して該選択肢から倍数を選択する選択手段と、
該必要な倍数と該選択された倍数との間の関係に依存して調節インジケータを設定する設定手段と
を備え、
該決定手段が、後に続く反復において、前回の反復からの該調節インジケータに依存して該必要な倍数を決定するように動作可能である、装置。
【請求項３９】
反復的ｂｗ関連ウィンドウアルゴリズムを用いてデータアイテムＭのべき指数ｄを計算するデータ処理方法であって、ここで、ｂはべき指数ｄの底であり、ｗはウィンドウサイズであり、該方法は、
少なくとも１つのＭのべき指数を含むデータアイテムの選択肢を提供するステップと、
該アルゴリズムの特定の反復について、その反復に必要なべき指数Ｍを決定し、該必要なべき指数に依存して該選択肢から選択されるべき指数を用い、該必要なべき指数と該選択されたべき指数との間の関係に依存して、調節インジケータを設定するステップと、
後に続く反復において、以前の反復からの該調節インジケータに依存して該必要なべき指数を決定するステップと
を包含する、方法。
【請求項４０】
前記反復的ｂｗ関連ウィンドウアルゴリズムは、左から右への「ｂ乗して、乗算する」タイプのアルゴリズムであり、該アルゴリズムの「ｂ乗」する部分において用いられるべき指数は、ｂｗであり、必要なべき指数は、該アルゴリズムの「乗算」部分において用いられるべき指数である、請求項３９に記載の方法。
【請求項４１】
ｂが２に等しく、前記反復的ｂｗ関連ウィンドウアルゴリズムは、「二乗および乗算」タイプアルゴリズムであり、該アルゴリズムの「二乗」部分で用いられるべき指数は、２ｗである、請求項４０に記載の方法。
【請求項４２】
反復的ｂｗ関連ウィンドウアルゴリズムを用いてデータアイテムＭのべき指数ｄを計算するデータ処理装置であって、ここで、ｂはべき指数ｄの底であり、ｗはウィンドウサイズであり、該装置は、
少なくとも１つのＭのべき指数を含むデータアイテムの選択肢を提供するデータアイテム提供手段と、
該アルゴリズムの特定の反復について、その反復に必要なべき指数Ｍを決定する決定手段と、
該必要なべき指数に依存して該選択肢からべき指数を選択する選択手段と、
該必要なべき指数と該選択されたべき指数との間の関係に依存して、調節インジケータを設定する設定手段と
を備え、該決定手段は、後に続く反復において、前回の反復からの該調節インジケータに依存して該必要なべき指数を決定するように動作可能である、装置。
【請求項４３】
反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理装置に対する電力サイドチャネル攻撃に対する抵抗力を高める方法であって、ｂは、該倍数ｋの底であり、ｗはウィンドウサイズであり、請求項１〜３７のいずれか１つに記載のステップを含む、方法。
【請求項４４】
反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＭのべき指数ｄを計算するデータ処理装置に対する電力サイドチャネル攻撃に対する抵抗力を高める方法であって、ｂは、該べき指数ｄの底であり、ｗはウィンドウサイズであり、請求項３９〜４１のいずれか１つに記載のステップをさらに包含する、方法。
【請求項４５】
実質的に、図９〜２０を参照しながら説明したようなデータ処理装置。
【請求項４６】
実質的に、図９〜２０を参照しながら説明したようなデータ処理方法。
【請求項４７】
実質的に、図９〜２０を参照しながら説明したようなデータ処理装置に対する電力サイドチャネル攻撃に対する抵抗力を高める方法。
【請求項４８】
請求項３８、４２および４５のいずれか１つに記載のデータ処理装置を含むスマートカード。
【請求項４９】
データ処理デバイスにロードされる場合、該デバイスを、請求項３８、４２、および４５のいずれか１つに記載の装置、あるいは、請求項４８に記載のスマートカードにする、オペレーティングプログラム。
【請求項５０】
データ処理デバイス上で実行される場合、該デバイスに、請求項１〜３７、３９〜４１、４３、４４、４６および４７のいずれか１つに記載の方法を実行させる、オペレーティングプログラム。
【請求項５１】
キャリア媒体上に保持される、請求項４９または５０に記載のオペレーティングプログラム。
【請求項５２】
前記キャリア媒体は伝送媒体である、請求項５１に記載のオペレーティングプログラム。
【請求項５３】
前記キャリア媒体は格納媒体である、請求項５１に記載のオペレーティングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置における、例えば、データを秘密にするため暗号アルゴリズムを用いたスマートカードにおけるサイドチャネル攻撃防止に関する。
【背景技術】
【０００２】
添付の図面の図１は、集積回路カード（ＩＣＣ）として公知の代表的なスマートカードの主な部分を示すブロック図である。図１のスマートカード１は、メモリ部３、中央処理装置（ＣＰＵ）５、入力／出力（Ｉ／Ｏ）部７、および処理装置９を含む。ＣＰＵ５は、メモリ部３、Ｉ／Ｏ部７、および処理装置９と双方向通信を行う。これらの部分は、通常は、スマートカード１に埋め込まれた１つの集積回路内に含まれる。スマートカード１は接触式タイプであってもよいし、非接触式タイプであってもよい。
【０００３】
スマートカード１は、ＰＯＷＥＲ（電力）およびＣＬＫチャネルを介して外部デバイスと通信して、必要な電力およびクロック信号ＣＬＫを受信することができ（内部電源またはクロック源を有するスマートカードもあるが）、Ｉ／Ｏチャネルを介して外部デバイスと通信して、データをスマートカード１に通信し、スマートカード１から通信することができる。このような通信は、接触式カードのコンタクトピンを介する電気信号、あるいは、非接触式カードの電磁誘導性、容量性または光結合のいずれかによって行われる。
【０００４】
スマートカードは、カードに格納されたデータ、ならびに、カードに通信され、または、カードから通信されるデータのセキュリティおよびインテグリティが最も重要である場合に、多くの用途が見出される。例えば、スマートカードは、カード保持者の身元を証明するために用いられる身分証明書としての役割を果たし得る。スマートカードはまた、その人の病歴を全て格納した医療カードとしても用いられ得る。さらに、スマートカードは、オフライン取引ができるクレジット／デビットバンクカードとして用いられ得る。このような理由により、機密に関わるデータがＩ／Ｏチャネルを介してカードから出る前に暗号化されることができるように、スマートカードは暗号化／復号能力を有することが一般的である。
【０００５】
図１に示すスマートカード１において、このような暗号化は、処理装置９によって行われる。例えば、メモリ部３に格納されたデータがＩ／Ｏチャネルを介して外部のリクエストデバイスと通信する必要がある場合、このデータは、ＣＰＵ５によってメモリ部３からリクエストされ、入力データＤＩＮとして処理装置９に送信される。処理装置９は、入力データＤＩＮを暗号化して、暗号化された出力データＤＯＵＴを生成する。ＤＯＵＴは、ＣＰＵ５に返され、Ｉ／Ｏ部７に転送され、続いてＩ／Ｏチャネルで外部のリクエストデバイスに伝送される。
【０００６】
任意の適切な暗号化モデルが、暗号化を行うために処理装置９において用いられ得る。スマートカードにおいて用いられる暗号化アルゴリズムの例として、データ暗号化規格（ＤＥＳ）、トリプルＤＥＳ、アドバンスト暗号化規格（ＡＥＳ）、高速データ暗号化アルゴリズム（ＦＥＡＬ）および国際データ暗号化アルゴリズム（ＩＤＥＡ）などの対称（または秘密）鍵暗号がある。あるいは、リベスト−シャミール−アドレマン（ＲＳＡ）アルゴリズムおよびラビン暗号化方式などの非対称（または公開）鍵暗号化アルゴリズムの使用も可能である。
【０００７】
添付の図面の図２は、公開鍵暗号システムおよび秘密鍵暗号システムの両方を表す、従来の暗号化モデルを図示するブロック図である。このモデルにおいて、２つの当事者、ＸおよびＹは、暗号を用いて、公開チャネル１３にわたる非公開通信を行おうと試みる。当事者Ｘは、暗号化ユニットＥを用い、暗号化鍵ＫＸ（非対称暗号化モデルにおいては公開鍵であり、対称暗号化モデルにおいては秘密鍵である）を用いて、平文Ｔを暗号化して、当事者Ｙへと公開チャネル１３を介して通信される暗号文Ｃを生成する。当事者Ｙは、復号ユニットＤおよび鍵ＫＸに対応する秘密鍵ＫＹを用いて、暗号文Ｃを復号して、元の平文Ｔを再生する。
【０００８】
しかし、第三者ＺがＸとＹとの間の非公開なやりとりを、公開チャネル１３をモニタリングすることによって盗聴している。第三者Ｚは、用いられた暗号アルゴリズムについての全ての詳細を、秘密鍵ＫＸを除いて全て知り得、多くの暗号文のサンプルを持ち、いくつかの平文と暗号文との対を（他の何らかの手段によって当事者Ｘまたは当事者Ｙのいずれかから得られた平文とともに）有し得る。このように集められた情報は、その後、計算集約暗号解析にかけられて、用いられた暗号を復号して、暗号文を生成または復号するために用いられた秘密鍵を判定する。
【０００９】
しかし、現代の暗号化技術は、従来の方法で集められた情報の力任せの計算解析に基づく、このような従来の攻撃に対してより抵抗力があるように開発されている。従って、暗号化システムの物理的な実施に基づいてよりわかりにくい別の情報ソースの使用が最近注目されている。
【００１０】
実際には、暗号システムは、その環境とインタラクトし、その環境によって影響される物理デバイスにおいてインプリメントされる。ポケットベルおよびスマートカードのような電子デバイスは、動作する間、電力を消費し、放射線を発し、また、温度変化および電磁場に反応する。これらの物理インタラクションが、Ｚのような第三者によって操作され、モニタリングされて、暗号解析において有用な情報をもたらし得る。図２に示す従来の暗号モデルは、現実の世界において暗号を用いることの物理的副作用について考慮しておらず、より現実的なモデルは、添付の図面の図３に示すように「サイドチャネル」の概念を用いて説明され得る。サイドチャネルは、物理的インプリメンテーションに固有の情報のソースであり、このような情報を用いた攻撃は、「サイドチャネル攻撃」と呼ばれる。
【００１１】
例えば、暗号関数の計算にかかる時間量は、その関数が何をするかのみに依存するのではなく、どのような入力が通過するかにも依存する。暗号化されるべきメッセージに加えて、暗号化関数は、通常、入力として秘密鍵をとり、従って、秘密鍵の値は、公に観察できるタイミング特徴に影響を与え得る。タイミングサイドチャネル情報に基づくこのような攻撃は、非特許文献１という名前の記事において提案されている。この文献において、攻撃者がいくつかのＲＳＡ署名を計算するのにかかる時間の測定値を解析し、署名したエンティティの秘密鍵を推測することができる、暗号解析方法が概説されている。
【００１２】
さらに、電子デバイスは、動作中、電源から電流を引く。電子デバイスが引く電流の量、すなわち、電力消費は、暗号化アルゴリズムの演算の間に論理ゲート（通常は、ＣＭＯＳ）が切り替わるにつれて、変動する。電力消費は、行われている計算と相関するので、敵にとって有用である。電力解析に基づくサイドチャネル攻撃の中で最も脅威的なタイプのうちの１つは、非特許文献２において提案されている差動電力解析（ＤＰＡ）というタイプのものである。
【００１３】
サイドチャネル攻撃の他の形態として、暗号化システムに誤りを作為的に導入し、その誤りによって引き起こされた影響をその後モニタリングすることに基づくものがある。非特許文献３において、Ｂｏｎｅｈ、ＤｅＭｉｌｌｏおよびＬｉｐｔｏｎは、インプリメントされた暗号化アルゴリズムについてのハードウェアデバイスリーク情報において誘発されるエラーの観察に基づく、誤りを利用したサイドチャネル攻撃を紹介している。暗号化デバイスをイオン化またはマイクロ波放射にさらすことによって、誤りは、ＲＳＡ公開鍵暗号アルゴリズムの係数を因数分解するために用いられ得る、レジスタのうちの１つのランダムビット位置に導入され得る。ＢｉｈｉｍおよびＳｈａｍｉｒは、故障差分解析（ＤＦＡ）と呼ばれる誤りに基づくチャネル攻撃を、非特許文献４において提案した。この攻撃は、ＤＥＳなどの対称または秘密鍵暗号システムに対して有効である。ＤＦＡは、２００未満の暗号文（平文はなし）を用いて、最後のＤＥＳラウンド鍵を見つけることができ、さらに、スマートカードにインプリメントされた未知の暗号システムの構造を明らかにすることすらできる。もっとも良好なＤＥＳに対する非サイドチャネル攻撃は、６４テラバイトよりわずかに少ない平文および１つの鍵で暗号化された暗号文しか必要としない。
【００１４】
このようなサイドチャネル攻撃は、デバイスの物理的インプリメンテーションについての秘密情報を明らかにするために、幅広い種類のデータ処理デバイスに適用され得る。このようなサイドチャネル攻撃がさらに高度になってきたため、サイドチャネルに漏れる情報を可能な限り少なくし、誤りを導入することをより困難にし、試みられた攻撃を検出することによって、このような技術的課題に対処し、その攻撃からスマートカードのようなデータ処理デバイスを保護することが重要である。
【００１５】
当事者ＸがＲＳＡアルゴリズムを用いてメッセージｍを暗号化し、当事者Ｙが受け取って復号するとする。当事者Ｘは、まず、当事者Ｙの公開鍵（Ｎ、ｅ）を取得し、これに基づいて、暗号化されるメッセージｍを整数として間隔［０：Ｎ−１］で表す。その後、当事者Ｘは、メッセージｍを暗号化して、以下のアルゴリズムを用いて、暗号文ｃを生成する。
ｃ＝ｍｅ  ｍｏｄ  Ｎ
以下により詳細に説明される標準的な二乗および乗算技術を用いると、このアルゴリズムは、ｍにｍをｅ回乗算し、解をモジュロＮで表したものと等しい。
【００１６】
ｃから平文ｍを復元するため、当事者Ｙは、自身の秘密鍵ｄを用いて、以下のアルゴリズムを行う。
【００１７】
ｍ＝ｃｄ  ｍｏｄ  Ｎ
従って、この復号演算は、暗号化演算と同じモジュラ累乗法形式を用いる。
【００１８】
公開鍵（Ｎ、ｅ）を生成し、対応する秘密鍵ｄを生成するため、当事者Ｙによって用いられる方法は、以下の通りである。２つの大きな素数、ｐおよびｑが選択され、その積Ｎ＝ｐｑが計算される。ただし、Ｎは公開鍵係数を形成する。公開鍵からの値ｅは、Ｎより小さく、（ｐ−１）（ｑ−１）と互いに素になるように選択される。これは、ｅと（ｐ−１）（ｑ−１）とは、１以外に公約数を持たないことを意味する。ｄの値は、（ｅｄ−１）が（ｐ−１）（ｑ−１）によって乗算できるようになるように見うけられる。因子ｐおよびｑは、破棄されてもよいし、強化秘密鍵（ｄ、ｐ、ｑ）と共に保持されてもよい。さらなる詳細を、例えば、非特許文献５に見出すことができる。
【００１９】
送信されたデータを秘密にし、その後、対応する秘密鍵ｄを以降の復号に用いる公開鍵（Ｎ、ｅ）を用いることの代替例として、秘密鍵ｄは、署名の一形態として、メッセージｍを暗号化するために、代替的に用いられ得、そのことによって、受け取り側の当事者は、メッセージｍが本物であることと、改竄されていないこととの両方が保証され得る。このようにして、当事者Ｙは、ｓ＝ｍｄ  ｍｏｄ  Ｎを用いることによって、自身の秘密鍵ｄを用いてデジタル署名ｓを作成し得る。その後、当事者Ｙは、ｍとｓとの両方を当事者Ｙに送信し得る。署名を照合するため、当事者Ｘは、当事者Ｙの公開鍵（Ｎ、ｅ）を用いてｍ＝ｓｅ  ｍｏｄ  Ｎを計算し、元のメッセージｍが復元されたことをチェックする。
【００２０】
累乗法演算ｍｄは、以下の擬似コードに示すように、「二乗および乗算」方法を用いて、実行され得る。ただし、ｄｉは、ｄのｉ番目の二進数字である。
【００２１】
ａ＝１
ｆｏｒ  ｉ＝ｎ  ｄｏｗｎ  ｔｏ  ０
ａ＝ａ＊ａ
ｉｆ（ｄｉ＝＝１）  ｔｈｅｎ  ａ＝ａ＊ｍ
ｒｅｔｕｒｎ  ａ
効率化のため、このようなアルゴリズムにおいては、全体の結果のｍｏｄ  Ｎが全ての中間計算  ｍｏｄ  Ｎを軽減させる場合、乗算演算が「ａ＝（ａ＊ｍ）ｍｏｄ  Ｎ」になり、二乗演算がａ＝（ａ＊ａ）  ｍｏｄ  Ｎになるようにすることが一般的である。
【００２２】
従って、暗号化および認証は、秘密鍵を共有することなく行われる。それぞれが、他方の公開鍵または自身の秘密鍵のみを用いる。誰でも、暗号化されたメッセージを送信するか、または署名されたメッセージを照合することができるが、正確な秘密鍵を所有する者のみがメッセージを復号するか、または署名することができる。
【００２３】
ＲＳＡの中国人剰余定理（ＣＲＴ）バージョンは類似し、同じ結果をもたらす：
ｓ＝（ｍｄ  ｍｏｄ  ｐ＋ｐ＊（ｐ−１  ｍｏｄ  ｑ）＊（ｍｄ  ｍｏｄ  ｑ−ｍｄ  ｍｏｄ  ｐ））ｍｏｄ  ｐ＊ｑ。
【００２４】
このアルゴリズムの秘密鍵は、（ｄ、ｐ、ｑ）である。ただし、（ｐ＊ｑ）は、公開鍵係数Ｎと等しい。ＣＲＴバージョンにおいて、スピード効率（ｍｄ  ｍｏｄ  ｐ）は、（ｍｄ  ｍｏｄ  ｐ−１  ｍｏｄ  ｑ）として計算され、（ｍｄ  ｍｏｄ  ｑ）は（ｍｄ  ｍｏｄ  ｑ−１  ｍｏｄ  ｑ）として計算される。従って、２つの別個の累乗法演算が行われる。
【００２５】
ＲＳＡアルゴリズムに対してサイドチャネル攻撃を行うことをより困難にするため、可能な限り計算にランダムさを加えることが有用である。これは、低いレベルで、例えば、演算のタイミングをランダムにすること、ランダムな間隔にダミー演算を追加すること、または、場合によっては、中間のステップを計算する複数の異なる様式からランダムに選択することによって行われ得る。あるいは、入力および計算がランダムになるが、出力が正確であり続けるように、マスキングがＲＳＡなどのアルゴリズムの入力に追加され得る。本出願人の同時係属出願中の英国特許出願第０３０７１９７．４号は、結果に影響しない様態で、ブラインディングされた性質の値を偽装する、底、べき指数、および係数のうちの１つの「ブラインディング」を開示している。本出願人の同時係属出願中の英国特許出願第０３０５５９６．９号においては、２つの同一であるが、並列でない計算の結果が比較され、挿入された誤りが検出されることを可能にする。
【００２６】
公開鍵システムは、大きな有限群を用いた演算の性質を利用する。多くの方法、例えば、ＳＰＥＫＥ、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ、ＥｌＧａｍａｌ、およびＤＳＳなどにおいて、セキュリティは、２つの群演算、すなわち、累乗法および離散対数計算を行う相対的な困難さに直接依存する。累乗法演算は、その逆の演算である離散対数計算よりも計算が容易である。一般的に用いられる群において、整数のモジュラ乗算を用いると、離散対数計算のみが、係数が非常に大きい場合に困難である。このことは、累乗法を、効果的に「一方向」関数にする。しかし、大きな累乗法は高価であるので、効率的に動作する群を見出すことが重要である。
【００２７】
楕円曲線暗号化の技術は、より速く、より小さい鍵を用いて、同等レベルのセキュリティを提供する場合もあるバージョンの公開鍵方法を提供し得る。楕円曲線を用いることの利点は、公開鍵演算の異なる種類の数学的群を用いることから得られる。楕円曲線離散対数問題は、通常の群における離散対数演算とは異なり、ある程度難しい。インプリメンテーションは、この違いを利用して、あるレベルのセキュリティについて、速くなったスピードと、小さくなった鍵サイズとの両方を提供することができる。ＳＰＥＫＥ、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ、および多くの他の公開鍵方法は、利用可能なインプリメンテーションのうち、最も良好なものを利用するように、楕円曲線、または任意の適切な群を用いて動作するように調節され得る。
【００２８】
次に、楕円曲線の簡単な概略を以下に説明するが、楕円曲線暗号化についてのさらなる情報は、非特許文献６、非特許文献７にも見受けられ得る。
【００２９】
添付の図面の図４は、式ｙ２＋ｙ＝ｘ３−ｘ２によって定められる、簡単な楕円曲線を示す。水平および垂直方向の点線のグリッド線は、それぞれ、Ｘ座標およびＹ座標の整数値を表すので、グリッド線のそれぞれの交点は、一対の整数の（ｘ，ｙ）座標である。楕円は、ある有限数の（ｘ，ｙ）交点を交差し、これらの点は、図４において点で印がつけられている。
【００３０】
「加算」演算子は、３番目の位置を特定するために、任意の２点を結合するために定義され、これらの点についてのこの「加算」演算子は、数学的有限群を形成する。図４の楕円曲線は、５つの点の群を定義する。これは、暗号化の目的にとっては実用的でないが、点演算が楕円曲線とともにどのように働くのかを示すために有用である。
【００３１】
この曲線を通る全ての直線が正確に３点でこの曲線と交差するという事実を用いて、２点ｕおよびｖを加算する規則は、以下の通りである。（ｉ）ｕおよびｖを通る直線を引き、第３の交点ｗを見つける。その後、（ｉｉ）ｗを通る垂線を引いて他の交点ｚを見つける。和ｕ＋ｖ＝ｚである。
【００３２】
この規則が成立するためには、余分な想像上の点Ｏ（原点と呼ばれる）、すなわち、無限遠点が定義される必要がある。Ｏは、無限に高い「トップ」、全ての垂線が収束するとされるところに位置すると考えられ得る。点Ｏはまた、特定の（ｘ，ｙ）座標は持たないが、曲線上にあると定義される。従って、図４に示す曲線は、（０，０）（１，−１）、（１，０）（０，−１）、および、Ｏ、すなわち、｛ａ，ｂ，ｃ，ｄ，Ｏ｝を通る。
【００３３】
さらに、一点で接する接線は、その点を２回交差すると言われる（接線は、曲線上の２点が互いに近づいたときの極限である）。従って、図４に示す曲線において、ａおよびｂを通る線は、「第３の点」ｂを通り、この線は、［ａ，ｂ，ｂ］で表される。
【００３４】
上記で定義したようなさらなる規則を用いて、ａ＋ｂの和は、まず、点ａおよびｂを通る接線［ａ，ｂ，ｂ］を引いて、ｂが第３の交点であることを見出して、その後、ｂを通る垂線［Ｏ，ｃ，ｂ］を引き、他の交点、すなわちｃを見つけることによって、決定される。従って、ａ＋ｂ＝ｃである。
【００３５】
同様に、ａ＋ａ＝ｂである。これは、［ａ，ａ，ｃ］（点ａでの曲線の接線）によってｃが得られ、［Ｏ，ｃ，ｂ］によってｂが得られるからである。空想上の垂線［Ｏ，Ｏ，Ｏ］を使うことによって、その鏡像と加算された全ての点について、ａ＋ｄ＝Ｏ、ｃ＋ｂ＝Ｏなどである場合もある。ａ＋ｄ＝Ｏおよびｃ＋ｂ＝Ｏであるので、当然、ａ＝−ｄおよびｃ＝−ｂになる。
【００３６】
ある点のスカラー乗算は、その点自体を単に繰り返し加算することである。ａ＋ａ＝ｂ、およびａ＋ｂ＝ｃであることから、当然、３ａ＝ｃになる。点Ｏは、群識別要素である。これは、任意のｖについて、ｖ＋Ｏ＝ｖだからである。点Ｏを加算することは、乗算ｍｏｄ  ｐのもとで通常の整数群において、１を乗算することと類似する。
【００３７】
図２１は、楕円曲線の点の加算および倍加のさらなる例ならびに負の楕円曲線の点の概念を提供する、楕円曲線の他の例を示す図である。上記と同じ規則を用いて、図２１は、Ｒ＝Ｐ＋Ｑ；Ｕ＝−Ｒ（Ｕ＋Ｒ＝Ｏ）；Ｔ＝Ｐ＋Ｐ＝２．Ｐ；およびＳ＝−Ｔ（Ｓ＋Ｔ＝Ｏ）であることを示す。
【００３８】
楕円曲線における加算演算は、共通公開鍵暗号化システムにおけるモジュラ乗算に相当するものであり、倍数加算は、モジュラ累乗法に相当するものである。
【００３９】
従って、楕円曲線は、ある特定の代数的性質を有する点の特別な集合であると考えられ得る。これには、曲線の１点（または複数の点）を入力として取り、ある曲線の１点を返す、例えば、上記の加算演算のような特定の「点演算」の計算可能な定義が含まれる。点は、座標の順序が付けられたタプルとして表され得る。座標は、基礎をなす数学的フィールドの要素（例えば、点Ｐ＝＜ｘ，ｙ＞またはＰ＝＜ｘ，ｙ，ｚ＞）である。フィールドは、大きな素数を法とする整数の演算であってもよいし、または、固定された多項式を法とする多項式の係数と見なされる小さい整数のベクトルについての演算であってもよいし、あるいは、ＣＰＵまたはコプロセッサで計算可能な任意の他の表現であってもよい。点演算は、点座標についてのフィールド演算として定義される。
【００４０】
Ｐ、ＱおよびＲが固定された楕円曲線上の任意の点である場合、上述したように点は加算され得（表記：Ｐ＋Ｑ）、この加算演算は、曲線点の集合をアーベル群に変換する。「曲線群のオーダー」は、単に曲線における点の数である。Ｏと書かれる曲線上の特別な点は、加算演算においてゼロとして作用する。すなわち、Ｐ＋Ｏ＝Ｏ＋Ｐ＝Ｐである。ゼロ点は、通常のタプル空間の外側にあるので、通常、特別な表現を有する。加算は、結合可能（Ｐ＋（Ｑ＋Ｒ）＝（Ｐ＋Ｑ）＋Ｒ）であり、交換可能（Ｐ＋Ｑ＝Ｑ＋Ｐ）である。減算は、通常の方法で定義される。Ｐ＋Ｑ＝Ｒの場合、Ｐ−Ｒ＝Ｑである。記号−Ｑは、Ｏ−Ｑの簡略的表記である。点−Ｑは、通常、自明の計算であり、Ｐ−Ｑは、通常、Ｐ＋（−Ｑ）として計算される。
【００４１】
点Ｐ＋Ｐは、２．Ｐと書かれ得、これは、点の倍加と呼ばれる。これは、「点乗算」と一般化され得、従って、整数ｋについて、ｋ．Ｐは、点Ｐのｋ個のコピーの和に等しい（かつ、（−ｋ）．Ｐ＝ｋ．（−Ｐ）である）。通常、ｋが曲線上の点の数より少ないことを保証する。Ｏ．Ｐ＝Ｏであり、ｋ．Ｐ＋ｍ．Ｐ＝（ｋ＋ｍ）．Ｐであることに留意されたい。
【００４２】
点をそれ自体に加算すること、すなわち、点の倍加は、等しくない点の一般的な加算（または減算）とは、（フィールド演算において）非常に異なる計算を有し得る。すなわち、等しい点に対する通常の加算のためのアルゴリズムは、失敗する。同様に、点をそれ自体から減算すること（Ｏを生成すること）は、非常に異なるアルゴリズムを有し、Ｏ点を用いる演算は、異なるアルゴリズムを有する。
【００４３】
楕円曲線暗号化（ＥＣＣ）において、曲線上の点Ｐは、秘密の整数ｋで「乗算」され、新たな点ｋ．Ｐが得られる。点ｋ．Ｐは、ｋの二進数表現に依存するシーケンスにおいて、点を倍加（Ｄ）させることおよび加算（Ａ）することによって計算され得る。整数ｋは、代表的には、約２００ビットの長さであり、従って、乗算の効率的なインプリメンテーションを用いることが重要である。
【００４４】
左から右への（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）アルゴリズムの１つにおいて、Ｏは、アキュムレータＲに格納され、ｋのビットが、高いものから（左から右とは、高いビットから低いビットという意味である）一度に１つずつ取り出される。０ビットに達するとき、Ｄ（倍加）演算、すなわち、Ｒ：＝２．Ｒを行う。そうでない場合は、１ビットに達し、ＤおよびＡ（加算）演算、すなわち、Ｒ：＝（２．Ｒ）＋Ｐを行う。その後、全てのビットに達するまで、次のビットを用いて繰り返される。その時点で、Ｒは、ｋ．Ｐを含む。このアルゴリズムは、累乗法演算に関連して上述した「二乗および乗算」技術に密接に関連するが、「二乗および乗算」法ではなく、「倍加および加算」法である。これは、楕円曲線における加算演算とモジュラ乗算との対応、および、楕円曲線における倍数加算とモジュラ累乗法との関連のためである。
【００４５】
例えば、ｋが二進法で１０００１１（すなわち、十進法の３５）であるとする。演算のシーケンスは以下の通りである：
ビット識別子：  ６      ５      ４      ３      ２      １
ｋのビット：    １      ０      ０      ０      １      １
演算：          ＤＡ    Ｄ      Ｄ      Ｄ      ＤＡ    ＤＡ
基本的な「倍加および加算」法は、添付の図面の図５に示されている。図５は、整数ｋおよび点ｐを入力として取り、積ｋ．Ｐを返す、関数「ｐｏｉｎｔｍｕｌｔ」の擬似コードを示す。
【００４６】
図５、ならびに、以下の記載および図面において、以下の表記が用いられる。ｘおよびｙが整数の場合、ｘ＾ｙは、ｘのｙ乗を表す。ｘが二進法の数とする。ｘにおけるビットの数は、ｘの長さであり、│ｘ│で表される。ｘのｉ番目のビットは、ｘ＿ｉ（ｘに下付のｉ）と示される。最下位ビットはｘ＿０であり、最上位ビットはｘ＿｛ｎ−１｝である。ただし、ｎ＝│ｘ│である。
【００４７】
便宜上、関数「Ｂ」は、二進数の数から連続するサブシーケンスを取り出し、符号なし整数に変換すると定義される。関数Ｂ（ｘ，ｓ，ｔ）（ｎ＞ｓ＞＝ｔ＞＝０）は、（ｘ＿ｉ＊２＾（ｉ−ｔ））の整数値の和（ｉ＝ｓからｔまで）を表す。
【００４８】
例えば、ｘが二進数の数１０００１１（十進数で３５）である場合、│ｘ│＝６；ｘ＿５＝１；ｘ＿４＝ｘ＿３＝ｘ＿２＝０；ｘ＿１＝ｘ＿０＝１である。Ｂ（ｘ，３，１）＝１であり、これは、サブシーケンス「００１」の符号なし二進数値である。Ｂ（ｘ，５，４）＝２であり、これは、サブシーケンス「１０」の符号なし二進数値である。
【００４９】
添付の図面の図６は、ｋ＝３５（二進数で１０００１１）の場合の図５のアルゴリズムのウォークスルーを示す。点レジスタＲは、初期的には、値Ｏ、すなわち、ゼロ点に設定され、変数ｉは│ｋ│に設定される。ダミー加算を以下に説明する。
【００５０】
ｋがｎビットを有する（従って、ｋ＜２＾ｎである）場合、基本的な「倍加および加算」アルゴリズムは、ｎ倍加（Ｄ）演算および平均（ｎ／２）加算（Ａ）演算、３ｎ／２演算の総計、ならびに２点（ＰおよびＲ）の記憶を必要とする。
【００５１】
値ｋは、攻撃者が時間とお金とを使って得ようとする秘密の量であり得る（例えば、非特許文献８を参照のこと）。例えばスマートカードにおける安全なインプリメンテーションにおいて、ｋは、カード上で生成され、カードの外に出されることはない。ｋがランダムに生成され、各暗号化演算につき１回しか用いられない場合もある（例えば、ＥＣＤＳＡ署名生成）。攻撃者が、１回ごとにｋのうちの数ビットでも取得することができれば、それは、カードをクラッキングし、そのアイデンティティ、すなわち、秘密鍵を盗むために十分な情報となり得る（非特許文献９、非特許文献１０、ならびに非特許文献１１、非特許文献１２を参照されたい）。
【００５２】
上述したように、ＥＣＣ乗算を実行するデバイスは、乗数ｋについての情報を探そうとしている攻撃者によって、いくつかの方法、例えば、計算の時間を正確に計ること、デバイスの電力供給をモニタリングすること、または、電磁放射を観察することによって、観察され得る。これらの方法および他の方法（あるいは、これらの組合せ）は、「サイドチャネル攻撃」と呼ばれる。このようなことが起こるのは、殆どのプラットフォームにおいて、デバイスによって用いられる実際の電力が、デバイスが行っている演算、およびデバイスが演算を行っている値に依存するからである。全ての演算が同じ電力を用いるようにすることは、特に、スマートカードのような小型の低電力デバイスにおいて高価であり、他の方法が演算を隠すために見つけられる必要がある。
【００５３】
点倍加（Ｄ）の電力または放射トレースが、点加算（Ａ）の電力トレースと異なる場合、攻撃者は、ＤおよびＡのシーケンスをトレースして、ｋの値を読む。これは、ＳＰＡ（シンプル電力解析）と呼ばれる。アルゴリズムを隠すために何の手段もとられない場合、そのアルゴリズムは恐らく安全でない。攻撃者が点減算と点加算とを区別することを難しくすることは、フィールド演算が数学的に類似するので簡単である。しかし、攻撃者がＤとＡとを区別することは（フィールド演算がかなり異なるので）容易である。また、曲線のゼロ点（Ｏ）の加算または倍加は、一般的な点を加算することとは非常に異なる。ＥＣＣのインプリメンテーションにおいて、Ａ演算は、点の倍加を行うために用いられることができない。演算が異なり、Ａ演算の２つのオペランドは異なる必要がある。
【００５４】
基本的な「倍加および加算」法の変形は、各ビットにおいて、ＤおよびＡ演算の両方を行うことである。ビットが０である場合、Ａは、さらなる加算が実際に必要とされないので、ダミー演算に過ぎない。可能性の１つとして、Ｐをいくつかの他の点Ｑにダミー加算し、結果を無視することがある。これによって、ダミー演算を適切に隠すこと、すなわち、電力トレースの観点からは実際の演算のように見せかけることができるならば、ＳＰＡの問題が低減される。これに伴う主な問題は、以上のことが必要とされる、３つの点（Ｐ，Ｑ，Ｒ）の格納、および２．│ｋ│演算により各ビットにおいて２つの演算が必要とされるので、遅いということである。これらのダミー演算は、図６に示される。図６においては、ビット５、４および３のためのステップがダミー加算を必要とする。
【非特許文献１】Ｐａｕｌ  Ｋｏｃｈｅｒら著、「Ｔｉｍｉｎｇ  Ａｔｔａｃｋｓ  ｏｎ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ，ＲＳＡ，ＤＳＳ  ａｎｄ  Ｏｔｈｅｒ  Ｓｙｓｔｅｍｓ」、ＣＲＹＰＴＯ‘９６
【非特許文献２】Ｋｏｃｈｅｒら著、「Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ」、ＣＲＹＰＴＯ‘９９
【非特許文献３】Ｂｏｎｅｈ、ＤｅＭｉｌｌｏおよびＬｉｐｔｏｎ著、「Ｏｎ  ｔｈｅ  Ｉｍｐｏｒｔａｎｃｅ  ｏｆ  Ｃｈｅｃｋｉｎｇ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｆａｕｌｔｓ」、１９９７年
【非特許文献４】ＢｉｈｉｍおよびＳｈａｍｉｒ著、「Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｆａｕｌｔ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｓｅｃｒｅｔ  Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、ＣＲＹＰＴＯ’９７、
【非特許文献５】Ｍｅｎｅｚｅｓ著、「Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ」
【非特許文献６】Ａ．Ｍｅｎｅｚｅｓ著、「Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」  Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ  １９９３年
【非特許文献７】Ｉａｎ  Ｂｌａｋｅ、Ｇａｄｉｅｌ  Ｓｅｒｏｕｓｓｉ、Ｎｉｇｅｌ  Ｓｍａｒｔ著、「Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ」、Ｌｏｎｄｏｎ  Ｍａｔｈｅｍａｔｉｃａｌ  Ｓｏｃｉｅｔｙ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅ  Ｓｅｒｉｅｓ  ＬＭＳ  ２５６  Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ、１９９９年
【非特許文献８】「Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ｆｏｒ  ｔｈｅ  ｆｉｎａｎｃｉａｌ  ｓｅｒｖｉｃｅｓ  ｉｎｄｕｓｔｒｙ：  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ（ＥＣＤＳＡ）」、Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄｓ  Ｉｎｓｔｉｔｕｔｅ  ＡＮＳＩ  Ｘ９．６２−１９９８、１９９８年
【非特許文献９】Ｎ．Ｐ．ＳｍａｒｔおよびＮ．Ｈｏｗｇｒａｖｅ著、「Ｌａｔｔｉｃｅ  ａｔｔａｃｋｓ  ｏｎ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅｓ」  Ｇｒａｈａｍ、Ｄｅｓｉｇｎｓ，Ｃｏｄｅｓ  ａｎｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ、２３（３）：２８３−２９０、２００１年８月
【非特許文献１０】ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｂｒｉｓ．ａｃ．ｕｋ／Ｔｏｏｌｓ／Ｒｅｐｏｒｔｓ／Ａｂｓｔｒａｃｔｓ／２００１−ｓｍａｒｔ．ｈｔｍｌ
【非特許文献１１】Ｐ．ＮｇｕｙｅｎおよびＩ．Ｅ．Ｓｈｐａｒｌｉｎｓｋｉ著、「Ｔｈｅ  ｉｎｓｅｃｒｕｔｙ  ｏｆ  ｔｈｅ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ  ｗｉｔｈ  ｐａｒｔｉａｌｌｙ  ｋｎｏｗｎ  ｎｏｎｃｅｓ」、Ｐｒｅｐｒｉｎｔ、２０００、１−２０、２０００年
【非特許文献１２】ｈｔｔｐ：／／ｃｉｔｅｓｅｅｒ．ｎｊ．ｎｅｃ．ｃｏｍ／ａｒｔｉｃｌｅ／ｎｇｕｙｅｎ００ｉｎｓｅｃｕｒｉｔｙ．ｈｔｍｌ
【発明の開示】
【発明が解決しようとする課題】
【００５５】
本発明は、反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理方法を提供することを目的とする。ここで、ｂは、倍数ｋの底であり、ｗはウィンドウサイズである。本発明はまた、楕円曲線暗号に用いる、効果的であり、かつ、セキュアな点演算を提供することを目的とする。
【課題を解決するための手段】
【００５６】
本発明の第１の局面によると、反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理方法であって、ここで、ｂは、倍数ｋの底であり、ｗはウィンドウサイズであり、該方法は、少なくとも１つのＰの倍数を含むデータアイテムの選択肢を提供するステップと、該アルゴリズムの特定の反復について、その反復に必要なＰの倍数を決定し、該必要な倍数に依存して該選択肢から選択した倍数を用い、該必要な倍数と該選択された倍数との関係に依存して調節インジケータを設定するステップと、後に続く反復において、前回の反復からの該調節インジケータに依存して該必要な倍数を決定するステップとを包含する、方法が提供される。
【００５７】
前記方法は、前記選択された倍数を、利用可能である場合、倍数の記憶場所から取り出し、そうでない場合、該選択された倍数を計算するステップを包含し得る。後に続く取り出しのため、前記倍数の記憶場所に新たに計算された倍数が格納され得る。前記選択肢内の少なくとも１つの倍数が事前計算され、該少なくとも１つの事前計算された倍数が、後に続く取り出しのため、前記倍数の記憶場所に格納され得る。前記選択肢内の全ての前記倍数は前記倍数の記憶場所から利用可能であり、反復の間に倍数の計算が必要とされないことが好ましい。従って、計算を必要とする任意の倍数が、事前計算されることが好ましく、前記選択肢内の全ての倍数は反復の間の取り出しのために格納されることが好ましい。前記倍数の記憶場所は、前記データアイテムＰのための別個の領域を含み得る。例えば、データアイテムＰは、引数をデータ処理方法に渡すために用いられるレジスタに一時的に格納され、他の倍数は、記憶場所の別個の領域、例えば、データアイテムアレイに格納され得る。
【００５８】
前記選択肢は、反復において必要であると決定され得る倍数を全ては含まないことが好ましい。例えば、前記選択肢が含む倍数は、ｂｗ個よりも少なくてもよい。前記選択肢が含む倍数は、０．７５＊ｂｗ個よりも少なくてもよい。前記選択肢は、少なくとも０．５＊ｂｗ個の倍数を含むことが好ましい。前記選択肢は、最も近い整数の倍数に切り上げられた、０．５＊ｂｗ個の倍数を含み得る。
【００５９】
前記選択肢は、交互の倍数、例えば、奇数の倍数のみを含んでもよい。前記選択肢は、ゼロ倍数を含まないことが好ましい。
【００６０】
前記調節インジケータは、前記必要な倍数と前記選択された倍数との間の関係の有限集合のうちの１つを示すように設定可能であってもよく、必要な倍数が前記選択肢から利用可能でない場合、該集合内の利用可能な関係インジケータに依存して前記選択肢から他の倍数が選択されることが好ましい。前記選択肢内の前記倍数および前記関係インジケータの集合が、Ｐの任意の倍数ｋの正常な計算を可能にするために十分な個数であることが好ましい。
【００６１】
必要な倍数が前記選択肢から利用可能でない場合、該選択肢から利用可能な最も近い倍数が選択され得る。１つより多い倍数が同等に近い場合、より高い倍数が選択され得る。あるいは、必要な倍数が前記選択肢から利用可能でない場合、該選択肢から利用可能な次の最も高い倍数が選択され得る。
【００６２】
前記調節インジケータは、前記必要な倍数から前記選択された倍数を引いたものに等しい補正倍数を示すように設定され得る。前記後に続く反復における前記必要な倍数は、前記補正倍数をｂｗでスケーリングして、その反復において考慮されるウィンドウ内の倍数ｋの値に加算することによって、決定され得る。
【００６３】
前記選択肢は、正の倍数のみを含み得るが、概念的には、対応する負の倍数を含むことも考えられ得る。前記必要な倍数が負であるか、または、前記選択肢における最も小さい正の倍数よりも小さいことが決定される場合、該選択肢の概念上の負の倍数を考えることによって、該選択肢から倍数が選択され得る。前記選択肢から選択された前記倍数が、前記概念上の負の倍数のうちの１つである場合、前記負の倍数を用いて加算演算を行うのではなく、前記選択肢からの対応する正の倍数を用いて減算演算が行われ得る。
【００６４】
最終反復において設定される調節インジケータに基づいて、最終調節を適用するステップを含み得る。１つ以上のデータアイテム倍数に関わる演算は、３種類の演算、すなわち、（ａ）ゼロでないデータアイテム倍数の倍加、（ｂ）ゼロでなく、等しくなく、逆数でないデータアイテム倍数の加算または減算、および（ｃ）ゼロデータアイテム倍数０．Ｐに関わる任意の演算のうちの１つに分類され得、最終ステップにおける演算分類のシーケンスは、前記最終反復において設定される前記調節インジケータから独立していることが好ましい。
【００６５】
前記反復的ｂｗ関連ウィンドウアルゴリズムは、左から右への「ｂを乗算し、加算する」タイプのアルゴリズムであり得、該アルゴリズムの該「ｂを乗算」する部分において用いられる乗数は、ｂｗであり、必要な倍数は、該アルゴリズムの「加算」部分において用いられる倍数である。底ｂが２である場合、前記反復的ｂｗ関連ウィンドウアルゴリズムが、「倍加および加算」タイプアルゴリズムであり、該アルゴリズムの「倍加」部分において用いられる乗数が２ｗである。
【００６６】
倍数ｋは符号付きの二進数値であり得、第１の反復において、ｋの先頭ビットは、必要な倍数を決定する場合、負の重みが付けられる。あるいは、前記ｋの先頭ビットは、切り捨てられ得、補償するために、前記第１の反復において調節インジケータが設定され得る。
【００６７】
１つ以上のデータアイテム倍数に関わる演算は、３種類の演算、すなわち、（ａ）ゼロでないデータアイテム倍数の倍加、（ｂ）ゼロでなく、等しくなく、逆数でないデータアイテム倍数の加算または減算、および（ｃ）ゼロデータアイテム倍数０．Ｐに関わる任意の演算のうちの１つに分類され得、演算分類のシーケンスは、前記ｋの値から独立していることが好ましい。例えば、反復がｗ回の倍加演算および１回の加算／減算演算を含み得、それぞれが、前記ｋの値とは無関係に生成される結果に寄与する。この場合、ダミー演算は必要とされない。前記ゼロ倍数データアイテム、すなわち、０．Ｐを用いるか、０．Ｐが得られる演算が行われないことが好ましい。倍加演算に等しい加算演算が行われないことも好ましい。
【００６８】
さらなるデータアイテムＱの倍数ｍも、前記反復アルゴリズムの間計算され得、２つの別個の調節インジケータを、進行中の乗算に対して１つずつ用いることによって、結果（ｋ．Ｐ＋ｍ．Ｑ）を生成する。
【００６９】
調節インジケータは、前記インジケータが設定された反復の直後の反復において適用されることが好ましい。
【００７０】
データアイテムＰの一例は、楕円曲線点である。本発明の第１の局面の方法は、データを暗号化または復号する、暗号化データ処理方法におけるステップを形成する。
【００７１】
第１の局面の方法は、ｋ．Ｐの計算の一部のみの処理に用いられ、ｋ．Ｐの計算の他の部分の処理には他のアルゴリズムが用いられることが可能である。例えば、ある数のウィンドウまたは反復が本発明のある実施形態に従って行われ、後のウィンドウまたは反復が従来の方法に従って行われてもよい。あるいは、第１の局面による方法は、反復のたびに用いられもよい。また、異なる反復において、異なるウィンドウサイズを用いることも可能である。反復において行われる計算のシーケンスはまた、反復毎に異なっていてもよい。当業者にとって明らかなこれらの手段および他の手段は、攻撃を成功させることをより困難にすることにさらに役立ち得る。
【００７２】
本発明の第２の局面によると、反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理装置であって、ここで、ｂは、倍数ｋの底であり、ｗはウィンドウサイズであり、該装置は、少なくとも１つのＰの倍数を含むデータアイテムの選択肢を提供するデータアイテム提供手段と、該アルゴリズムの特定の反復について、その反復に必要なＰの倍数を決定する、決定手段と、該必要な倍数に依存して該選択肢から倍数を選択する選択手段と、該必要な倍数と該選択された倍数との間の関係に依存して調節インジケータを設定する設定手段とを備え、該決定手段が、後に続く反復において、前回の反復からの該調節インジケータに依存して該必要な倍数を決定するように動作可能である、装置が提供される。
【００７３】
本発明の第３の局面によると、反復的ｂｗ関連ウィンドウアルゴリズムを用いてデータアイテムＭのべき指数ｄを計算するデータ処理方法であって、ここで、ｂはべき指数ｄの底であり、ｗはウィンドウサイズであり、該方法は、少なくとも１つのＭのべき指数を含むデータアイテムの選択肢を提供するステップと、該アルゴリズムの特定の反復について、その反復に必要なべき指数Ｍを決定し、該必要なべき指数に依存して該選択肢からべき指数を用い、該必要なべき指数と該選択されたべき指数との間の関係に依存して、調節インジケータを設定するステップと、後に続く反復において、前回の反復からの該調節インジケータに依存して該必要なべき指数を決定するステップとを包含する、方法が提供される。
【００７４】
前記反復的ｂｗ関連ウィンドウアルゴリズムは、左から右への「ｂ乗して、乗算する」タイプのアルゴリズムであり得、該アルゴリズムの「ｂ乗」する部分において用いられるべき指数は、ｂｗであり、必要なべき指数は、該アルゴリズムの「乗算」部分において用いられるべき指数である。ｂが２に等しい場合、前記反復的ｂｗ関連ウィンドウアルゴリズムは、「二乗および乗算」タイプアルゴリズムであり、該アルゴリズムの「二乗」部分で用いられるべき指数は、２ｗである。
【００７５】
本発明の第４の局面によると、反復的ｂｗ関連ウィンドウアルゴリズムを用いてデータアイテムＭのべき指数ｄを計算するデータ処理装置であって、ここで、ｂはべき指数ｄの底であり、ｗはウィンドウサイズであり、該装置は、少なくとも１つのＭのべき指数を含むデータアイテムの選択肢を提供するデータアイテム提供手段と、該アルゴリズムの特定の反復について、その反復に必要なべき指数Ｍを決定する決定手段と、該必要なべき指数に依存して該選択肢からべき指数を選択する選択手段と、該必要なべき指数と該選択されたべき指数との間の関係に依存して、調節インジケータを設定する設定手段とを備え、該決定手段は、後に続く反復において、前回の反復からの該調節インジケータに依存して該必要なべき指数を決定するように動作可能である、装置が提供される。
【００７６】
本発明の第５の局面によると、反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理装置に対する電力サイドチャネル攻撃に対する抵抗力を高める方法であって、ｂは、該倍数ｋの底であり、ｗはウィンドウサイズであり、本発明の第１の局面によるステップを含む、方法が提供される。
【００７７】
本発明の第６の局面によると、反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＭのべき指数ｄを計算するデータ処理装置に対する電力サイドチャネル攻撃に対する抵抗力を高める方法であって、ｂは、該べき指数ｄの底であり、ｗはウィンドウサイズであり、本発明の第３の局面によるステップを含む、方法が提供される。
【００７８】
本発明の第７の局面によると、本発明の第２の局面または第４の局面によるデータ処理装置を含むスマートカードが提供される。
【００７９】
本発明の第８の局面によると、データ処理デバイスにロードされる場合、該デバイスを、本発明の第２の局面または第４の局面による装置、あるいは、本発明の第７の局面によるスマートカードにする、オペレーティングプログラムが提供される。
【００８０】
本発明の第９の局面によると、データ処理デバイス上で実行され、該デバイスに、本発明の第１の局面、第３の局面、第５の局面、または第６の局面による方法を実行させる、オペレーティングプログラムが提供される。
【００８１】
前記オペレーティングプログラムは、キャリア媒体上に保持され得、該キャリア媒体は、伝送媒体、または格納媒体であり得る。
【００８２】
本発明により、反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理方法であって、ここで、ｂは、倍数ｋの底であり、ｗはウィンドウサイズであり、該方法は、少なくとも１つのＰの倍数を含むデータアイテムの選択肢を提供するステップと、該アルゴリズムの特定の反復について、その反復に必要なＰの倍数を決定し、該必要な倍数に依存して該選択肢から選択した倍数を用い、該必要な倍数と該選択された倍数との関係に依存して調節インジケータを設定するステップと、後に続く反復において、前回の反復からの該調節インジケータに依存して該必要な倍数を決定するステップとを包含する、方法が提供され、これにより上記目的が達成される。
【００８３】
前記選択された倍数を、利用可能である場合、倍数の記憶場所から取り出し、そうでない場合、該選択された倍数を計算するステップをさらに包含してもよい。
【００８４】
後に続く取り出しのため、前記倍数の記憶場所に新たに計算された倍数を格納するステップをさらに包含してもよい。
【００８５】
前記選択肢内の少なくとも１つの倍数を事前計算するステップと、該少なくとも１つの事前計算された倍数を、後に続く取り出しのため、前記倍数の記憶場所に格納するステップをさらに包含してもよい。
【００８６】
前記選択肢内の全ての前記倍数は、前記倍数の記憶場所から利用可能であってもよい。
【００８７】
前記倍数の記憶場所は、前記データアイテムＰを保持する別個の領域を含んでもよい。
【００８８】
前記選択肢は、反復において必要であると決定され得る倍数を全ては含んでもよい。
【００８９】
前記選択肢が含む倍数は、ｂｗ個よりも少なくてもよい。
【００９０】
前記選択肢が含む倍数は、０．７５＊ｂｗ個よりも少なくてもよい。
【００９１】
前記選択肢は、少なくとも０．５＊ｂｗ個の倍数を含んでもよい。
【００９２】
前記選択肢は、最も近い整数個の倍数に切り上げられた、０．５＊ｂｗ個の倍数を含んでもよい。
【００９３】
前記選択肢は、交互の倍数を含んでもよい。
【００９４】
前記選択肢は、奇数の倍数のみを含んでもよい。
【００９５】
前記選択肢は、ゼロ倍数を含まなくてもよい。
【００９６】
前記調節インジケータは、前記必要な倍数と前記選択された倍数との間の関係の有限集合のうちの１つを示すように設定可能であり、必要な倍数が前記選択肢から利用可能でない場合、該集合内の利用可能な関係インジケータに依存して前記選択肢から他の倍数が選択されてもよい。
【００９７】
前記選択肢内の前記倍数および前記関係インジケータの集合が、Ｐの任意の倍数ｋの正常な計算を可能にするために十分な個数であってもよい。
【００９８】
必要な倍数が前記選択肢から利用可能でない場合、該選択肢から利用可能な最も近い倍数が選択されるか、または、１つより多い倍数が同等に近い場合、最も近い倍数のうちより高い倍数が選択されてもよい。
【００９９】
必要な倍数が前記選択肢から利用可能でない場合、該選択肢から利用可能な次の最も高い倍数が選択されてもよい。
【０１００】
前記調節インジケータは、前記必要な倍数から前記選択された倍数を引いたものに等しい補正倍数を示すように設定されてもよい。
【０１０１】
前記後に続く反復における前記必要な倍数は、前記補正倍数をｂｗでスケーリングして、その反復において考慮されるウィンドウ内の倍数ｋの値に加算することによって、決定されてもよい。
【０１０２】
前記選択肢は、正の倍数のみを含むが、概念的には、対応する負の倍数を含むことも考えられてもよい。
【０１０３】
前記必要な倍数が負であるか、または、前記選択肢における最も小さい正の倍数よりも小さいことが決定される場合、該選択肢の概念上の負の倍数を考えることによって、該選択肢から倍数が選択されてもよい。
【０１０４】
前記選択肢から選択された前記倍数が、前記概念上の負の倍数のうちの１つである場合、前記選択肢からの対応する正の倍数を用いて減算演算が行われてもよい。
【０１０５】
最終反復において設定される調節インジケータに基づいて、最終調節を適用するステップをさらに包含してもよい。
【０１０６】
１つ以上のデータアイテム倍数に関わる演算は、３種類の演算、すなわち、（ａ）ゼロでないデータアイテム倍数の倍加、（ｂ）ゼロでなく、等しくないデータ、逆数でないアイテム倍数の加算または減算、および（ｃ）ゼロデータアイテム倍数０．Ｐに関わる任意の演算のうちの１つに分類され得、最終ステップにおける演算分類のシーケンスは、前記最終反復において設定される前記調節インジケータから独立していてもよい。
【０１０７】
前記反復的ｂｗ関連ウィンドウアルゴリズムは、左から右への（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ）「ｂを乗算し、加算する」タイプのアルゴリズムであり、該アルゴリズムの該「ｂを乗算」する部分において用いられる乗数は、ｂｗであり、前記必要な倍数は、該アルゴリズムの「加算」部分において用いられる倍数であってもよい。
【０１０８】
ｂが２に等しく、前記反復的ｂｗ関連ウィンドウアルゴリズムが、「倍加および加算」タイプのアルゴリズムであり、該アルゴリズムの「倍加」部分において用いられる乗数が２ｗであってもよい。
【０１０９】
ｋは符号付きの二進数値であり、前記第１の反復において、ｋの先頭ビットは、前記必要な倍数を決定する場合、負の重みが付けられてもよい。
【０１１０】
ｋは符号付きの二進数値であり、ｋの先頭ビットを切り捨て、補償するために、前記第１の反復において調節インジケータを設定するステップをさらに包含してもよい。
【０１１１】
１つ以上のデータアイテム倍数に関わる演算は、３種類の演算、すなわち、（ａ）ゼロでないデータアイテム倍数の倍加、（ｂ）ゼロでなく、等しくなく、逆数でないデータアイテム倍数の加算または減算、および（ｃ）ゼロデータアイテム倍数０．Ｐに関わる任意の演算のうちの１つに分類され得、演算分類のシーケンスは、前記ｋの値から独立していてもよい。
【０１１２】
１つ以上のデータアイテム倍数に関わる演算は、３種類の演算、すなわち、（ａ）ゼロでないデータアイテム倍数の倍加、（ｂ）ゼロでなく、等しくなく、逆数でないデータアイテム倍数の加算または減算、および（ｃ）ゼロデータアイテム倍数０．Ｐに関わる任意の演算のうちの１つに分類され得、演算分類のシーケンスは、前記ｋの値から独立しており、反復が、ｗ回の倍加演算および１回の加算／減算演算を含み、それぞれが、前記ｋの値とは無関係に生成される結果に寄与してもよい。
【０１１３】
前記ゼロ倍数データアイテム、すなわち、０．Ｐを用いるか、または０．Ｐが得られる演算が行われなくてもよい。
【０１１４】
倍加演算に等しい加算演算が行われなくてもよい。
【０１１５】
さらなるデータアイテムＱの倍数ｍも、前記反復アルゴリズムの間計算されて、２つの別個の調節インジケータを、進行中の乗算に対して１つずつ用いることによって、結果（ｋ．Ｐ＋ｍ．Ｑ）を生成してもよい。
【０１１６】
調節インジケータは、該インジケータが設定された反復の直後の反復において適用されてもよい。
【０１１７】
前記データアイテムＰは、楕円曲線点であってもよい。
【０１１８】
データを暗号化または復号する、暗号化データ処理方法におけるステップであってもよい。
【０１１９】
本発明により、反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理装置であって、ここで、ｂは、倍数ｋの底であり、ｗはウィンドウサイズであり、該装置は、少なくとも１つのＰの倍数を含むデータアイテムの選択肢を提供するデータアイテム提供手段と、該アルゴリズムの特定の反復について、その反復に必要なＰの倍数を決定する、決定手段と、該必要な倍数に依存して該選択肢から倍数を選択する選択手段と、該必要な倍数と該選択された倍数との間の関係に依存して調節インジケータを設定する設定手段とを備え、該決定手段が、後に続く反復において、前回の反復からの該調節インジケータに依存して該必要な倍数を決定するように動作可能である、装置が提供され、これにより上記目的が達成される。
【０１２０】
本発明により、反復的ｂｗ関連ウィンドウアルゴリズムを用いてデータアイテムＭのべき指数ｄを計算するデータ処理方法であって、ここで、ｂはべき指数ｄの底であり、ｗはウィンドウサイズであり、該方法は、少なくとも１つのＭのべき指数を含むデータアイテムの選択肢を提供するステップと、該アルゴリズムの特定の反復について、その反復に必要なべき指数Ｍを決定し、該必要なべき指数に依存して該選択肢から選択されるべき指数を用い、該必要なべき指数と該選択されたべき指数との間の関係に依存して、調節インジケータを設定するステップと、後に続く反復において、以前の反復からの該調節インジケータに依存して該必要なべき指数を決定するステップとを包含する、方法が提供され、これにより上記目的が達成される。
【０１２１】
前記反復的ｂｗ関連ウィンドウアルゴリズムは、左から右への「ｂ乗して、乗算する」タイプのアルゴリズムであり、該アルゴリズムの「ｂ乗」する部分において用いられるべき指数は、ｂｗであり、必要なべき指数は、該アルゴリズムの「乗算」部分において用いられるべき指数であってもよい。
【０１２２】
ｂが２に等しく、前記反復的ｂｗ関連ウィンドウアルゴリズムは、「二乗および乗算」タイプアルゴリズムであり、該アルゴリズムの「二乗」部分で用いられるべき指数は、２ｗであってもよい。
【０１２３】
本発明により、反復的ｂｗ関連ウィンドウアルゴリズムを用いてデータアイテムＭのべき指数ｄを計算するデータ処理装置であって、ここで、ｂはべき指数ｄの底であり、ｗはウィンドウサイズであり、該装置は、少なくとも１つのＭのべき指数を含むデータアイテムの選択肢を提供するデータアイテム提供手段と、該アルゴリズムの特定の反復について、その反復に必要なべき指数Ｍを決定する決定手段と、該必要なべき指数に依存して該選択肢からべき指数を選択する選択手段と、該必要なべき指数と該選択されたべき指数との間の関係に依存して、調節インジケータを設定する設定手段とを備え、該決定手段は、後に続く反復において、前回の反復からの該調節インジケータに依存して該必要なべき指数を決定するように動作可能である、装置が提供され、これにより上記目的が達成される。
【０１２４】
反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理装置に対する電力サイドチャネル攻撃に対する抵抗力を高める方法であって、ｂは、該倍数ｋの底であり、ｗはウィンドウサイズであってもよい。
【０１２５】
反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＭのべき指数ｄを計算するデータ処理装置に対する電力サイドチャネル攻撃に対する抵抗力を高める方法であって、ｂは、該べき指数ｄの底であり、ｗはウィンドウサイズであり、請求項３９〜４１のいずれか１つに記載のステップをさらに包含してもよい。
【０１２６】
本発明により、実質的に、図９〜２０を参照しながら説明したようなデータ処理装置に対する電力サイドチャネル攻撃に対する抵抗力を高める方法が提供され、それにより、上記目的が達成される。。
【０１２７】
本発明により、適切な前記処理装置を含むスマートカードが提供され、それにより、上記目的が達成される。
【０１２８】
本発明により、データ処理デバイスにロードされる場合、該デバイスを、適切な前記装置のいずれか１つの装置、あるいは、適切な前記スマートカードにする、オペレーティングプログラムが提供され、それにより、上記目的が達成される。
【０１２９】
本発明により、データ処理デバイス上で実行される場合、該デバイスに、適切な前期方法のいずれか１つの方法を実行させる、オペレーティングプログラムが提供され、それにより、上記目的が達成される。
【０１３０】
キャリア媒体上に保持されてもよい。
【０１３１】
前記キャリア媒体は伝送媒体であってもよい。
【０１３２】
前記キャリア媒体は格納媒体であってもよい。
【発明の効果】
【０１３３】
以上により、本発明によれば、反復的ｂｗ関連ウィンドウアルゴリズムを用いて、データアイテムＰの倍数ｋを計算するデータ処理方法が提供される。ここで、ｂは、倍数ｋの底であり、ｗはウィンドウサイズである。これにより、楕円曲線暗号に用いる、効果的であり、かつ、セキュアな点演算が提供される。
【発明を実施するための最良の形態】
【０１３４】
例示のため、添付の図面が参照される。
【０１３５】
本発明の実施形態の詳細な説明の前に、上述した、楕円曲線点乗算アルゴリズムの効率およびセキュリティに関連する問題を軽減する、以前に考えられたいくつかの方法を説明する。以下の説明は、三種類の演算の考慮に限定されている。
【０１３６】
「Ｄ」：ゼロでない点の倍加、２．Ｐと書かれる、
「Ａ」：ゼロでなく、等しくなく、逆数でない点の加算または減算、Ｐ＋ＱまたはＰ−Ｑと書かれる、
「Ｚ」：ゼロを含む任意の演算、例えば、Ｐ＋Ｏ、Ｏ＋Ｐ、Ｏ−Ｐ、Ｐ−Ｏ、Ｐ−Ｐ、Ｐ＋（−Ｐ）または２．Ｏ。
【０１３７】
任意の２つのＤ演算を攻撃者が区別することはできないとする。同様に、任意の２つのＡ演算を攻撃者が区別することはできないとする。
【０１３８】
しかし、何の注意も払われない場合、Ａステップのように見えるステップ、例えば、「Ｒ：＝Ｐ＋Ｑ」は、実際に、Ｐ＝Ｑの場合、Ｄステップに、ＰおよびＱのいずれかまたは両方がゼロあるいはＱ＝（−Ｐ）である場合、Ｚ演算に変わり得る。
【０１３９】
各ステップにおいて、デバイスがどのように次の演算を選択するのかを考えることにも関連する。決定プロセスが、ｋに依存する時間量または電力量を用いる場合、攻撃者は、曲線演算間のギャップを観察することによって情報を取得し得る。実際には、この問題は、当業者であれば達成できるように、（ソフトウェアまたはハードウェアのステートマシンのいずれかにおける）注意深いコーディングによって対処され得る。
【０１４０】
ＳＰＡ攻撃が成功する機会を低減する他の方式を用いることが可能である。例えば、ランダム電力ノイズが追加されてもよいし、プロセッサ命令がランダムに遅延されてもよいし、各種の平衡回路を製造することによって電力消費が同じにされてもよい（ＷＯ９９／６７７６６「Ｂａｌａｎｃｅｄ  ｃｙｔｏｇｒａｐｈｉｃ  ｃｏｍｐｕｔａｔｉｏｎａｌ  ｍｅｔｈｏｄ  ａｎｄ  ａｐｐａｒａｔｕｓ  ｆｏｒ  ｌｅａｋ  ｍｉｎｉｍｉｚａｔｉｏｎ  ｉｎ  ｓｍａｒｔｃａｒｄｓ  ａｎｄ  ｏｔｈｅｒ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ」を参照されたい）。しかし、これらの方法は、概して、小さい低電力デバイス上に完全にインプリメントすると、性能を低減させるか、回路サイズを大きくするか、または利用される平均消費電力を増大させるため、高くつく。実際には、組み合わせた方法が用いられる。いくつかの試みが、電力を同じにし、実行をランダムにし、本明細書に記載の発明のように注意深くバランスが取られたアルゴリズムを提供するために行われる。本発明の実施形態は、以下に説明されるが、これらの他の方法とともに用いられ得る。
【０１４１】
より進んだ攻撃、例えばＤＰＡ（電力差分攻撃）もある。この攻撃は、いくつかの電力トレースを捕らえて、統計学的に解析することによって働く（「Ｒｅｓｉｓｔａｎｃｅ  ａｇａｉｎｓｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  ｆｏｒ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」Ｊｅａｎ−Ｓｅｂａｓｔｉｅｎ  Ｃｏｒｏｎ、ｈｔｔｐ：／／ｃｉｔｅｓｅｅｒ．ｎｊ．ｎｅｃ．ｃｏｍ／３９３４４３．ｈｔｍｌを参照されたい）。このような攻撃は、通常、ランダムな要素を計算に加えて、２つとして同じアルゴリズムの実行がないようにすることによって防御される（ＵＳ−Ａ−２００２０２９３４６「Ｍｅｔｈｏｄ  ａｎｄ  ａｐｐａｒａｔｕｓ  ｆｏｒ  ｍｉｎｉｍｉｚｉｎｇ  ｄｉｆｆｅｒｅｎｔｉａｌ  ｐｏｗｅｒ  ａｔｔａｃｋｓ  ｏｎ  ｐｒｏｃｅｓｓｏｒｓ」を参照されたい）。例えば、ｋ．Ｐ（ここで、ｋは秘密）を計算するため、まず乱数ｒが生成され、次に（ｋ−ｒ）Ｐ．＋ｒ．Ｐが計算され、同じ答えが返されるが、２つの本質的にランダムな乗数が用いられる。ランダム性はまた、点の表現、および点演算にも組み込まれ得る。本発明の実施形態は、以下に説明するように、これらの方法からは独立しており、これらの方法とともに用いられてもよい。
【０１４２】
基本的な楕円曲線点乗算方法をより効率的にする方法の１つとして、１度にｋのｗビットを処理する、「ｗビットウィンドウ法」を用いる方法がある。このようなアルゴリズムは、関数「ｗｉｎｄｏｗ＿ｐｏｉｎｔｍｕｌｔ」として図７に示される。「ｗｉｎｄｏｗ＿ｐｏｉｎｔｍｕｌｔ」は、図５を参照しながら上述した、基本的な「ｐｏｉｎｔｍｕｌｔ」関数と同様に、整数ｋおよび楕円曲線点Ｐを入力として取り、ｋ．Ｐを出力として返す。この基本的なウィンドウ法は、Ｐの倍数を０〜（２＾ｗ）−１まで、事前計算し、テーブルＴに格納する。すなわち、Ｔ［ｉ］＝ｉ．Ｐである。例えば、ｋのｊ−１〜ｊ−ｗのウィンドウのｗビットを処理するため、ビットは、ｗ−ビット整数として処理される。すなわち、ｖ＝Ｂ（ｋ，ｊ−１，ｊ−ｗ）である。各ループにおいて、倍加演算Ｒ：＝２．Ｒは、ｗ回行われて、元のＲの（２＾ｗ）倍が得られ、Ｒ：＝Ｒ＋Ｔ［ｖ］である。これは、（２＾ｗ）−２＋（１＋（１／ｗ））│ｋ│点演算を必要とする（事前計算２．Ｐ、３．Ｐなどは（２＾ｗ）−２演算を取り、各ループボディは、ｗ回のＤ演算および１回のＡ演算からなり、│ｋ│／ｗ反復がある）が、１＋（２＾ｗ）点を（２＾ｗ点をテーブルＴに、１をレジスタＲに）格納する必要があり、空間の面で高くつく。ＯをＲに加算して（ｖ＝０の場合）、情報をうっかり漏らしてしまうことを防止するため、基本的な加算Ｒ＋Ｔ［ｖ］は、ｖ＝０の場合、何らかの種類のダミー演算（例えば、結果が用いられない加算を行うこと）と置き換えられる。この場合、点ＯをテーブルＴに格納することは必要ない。
【０１４３】
図８は、図７のウィンドウ法の実行の一例を、ｋ＝３５（二進数で１０００１１）である場合について示す。点レジスタＲは、初期的に値Ｏ、すなわちゼロ点に設定され、変数ｉは、│ｋ│／ｗ＝３（ｋの二進数値が除算されて得られるウィンドウの数）に設定され、０〜（２＾ｗ）−１までの事前に計算されたＰの倍数はテーブルＴに格納される。ダミー演算は、２ビットの真ん中のウィンドウを処理する場合に必要とされる。
【０１４４】
図７および８を参照しながら上述されたウィンドウ法は、反復的ｂｗ関連ウィンドウアルゴリズムの一例である。ここで、ｂは、倍数ｋの底であり、ｗはウィンドウサイズである。具体的には、図７の方法は、反復的な左から右への二進数「倍加および加算」ウィンドウアルゴリズムである。これは、例えば、「Ａ  ｓｕｒｖｅｙ  ｏｆ  ｆａｓｔ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ  ｍｅｔｈｏｄｓ」（Ｄ．Ｍ．Ｇｏｒｄｏｎ、Ｊｏｕｒｎａｌ  ｏｆ  Ａｌｇｏｒｉｔｈｍｓ  ２７、ｐｐ．１２９−１４６）に記載されている。図７および８の例において、底ｂは２（二進法）であり、アルゴリズムは、反復二進数ウィンドウアルゴリズム、または左から右への倍加および加算アルゴリズムである。
【０１４５】
他の方法の群は、ｋのビットを記録することを含む。例えば、Ｂｏｏｔｈのアルゴリズムは、ｋを二乗で再表現するが、係数を＋１、０および−１とすることを可能にする（通常、二進数は−１を用いない）。Ｂｏｏｔｈのアルゴリズム（および類似の同系統のアルゴリズム）は、１の稠密ストリングを、殆ど０のストリングと、それから、１つの−１および１つの＋１と置き換える。０がＤ演算にのみ対応するので（１がＤおよび加算に対応し、−１がＤおよび減算に対応する）、これは、より効率的であり（２の格納、および４．│ｋ│／３演算）、これは、このタイプの最もあり得る方式であることが示され得る。しかし、これは、依然として電力消費を漏らし、０ビットは、再符号化されたシーケンスにおける＋１および−１ビットから区別され得る。これは、攻撃者にとって、かなりの量の情報であり、ダミー演算が必要とされ、効率は、基本的なアルゴリズムと同じ程度まで落ちる。
【０１４６】
他の種類の解決策は、いわゆる「Ｍｏｎｔｇｏｍｅｒｙ  Ｌａｄｄｅｒ」（ＷＯ００／２５２０４「Ｐｏｗｅｒ  ｓｉｇｎａｔｕｒｅ  ａｔｔａｃｋ  ｒｅｓｉｓｔａｎｔ  ｃｒｙｐｔｏｇｒａｐｈｙ」を参照されたい）に基づく。この方法は、各ステップにおいて、差が公知である２点の加算を単純化することよって、その速度を増す。ｋの隣接しない形態にも同様に用いられ得る（「Ａｎ  ｏｖｅｒｖｉｅｗ  ｏｆ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ」（ＬｏｐｅｚおよびＤａｈａｂら、ｈｔｔｐ：／／ｃｉｔｅｓｅｅｒ．ｎｊ．ｎｅｃ．ｃｏｍ／３３３０６６．ｈｔｍｌ）を参照されたい）。
【０１４７】
ランダム化された加算を用いる他の変形例が、「Ｒａｎｄｏｍｉｚｅｄ  ｓｉｇｎｅｄ−ｓｃａｌａｒ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ｏｆ  ＥＣＣ  ｔｏ  ｒｅｓｉｓｔ  ｐｏｗｅｒ  ａｔｔａｃｋｓ」（Ｊａｅ  Ｃｈｅｏｌ  Ｈａ、Ｓａｎｇ  Ｊａｅ  Ｍｏｏｎ、ＣＨＥＳ２００２  ｐｒｏｃｅｅｄｉｎｇｓ、ｐｐ５５１〜５６３、ＬＮＣＳ２５２３、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ  ２００２）に開示されている。開示されているアルゴリズムは、乱数の良好なソースを必要とする。
【０１４８】
点ｋ．Ｐ＋ｍ．Ｑを計算することが必要となる場合がある。ここで、ｋおよびｍは整数であり、ＰおよびＱは点である。同時にｋとｍとの両方に沿って反復することによって、「クロス乗積」ウィンドウ法が適用され得る。Ｒを２＾ｗでスケーリングすることは、両方の１つの倍数（ｋ．Ｐおよびｍ．Ｑ）に共通であり、反復される必要はない。各反復において、おおよそ２＾（ｗ＋１）の格納を用いて、事前計算される必要がある、Ｐのいくつかの倍数およびＱのいくつかの倍数が加算される必要がある。この速度は、おおよそ、２＾（ｗ＋１）（事前計算）に│ｋ│．（１＋２／ｗ）演算を加算した速度である。
【０１４９】
さらなる効率のため、全ての和（ｉ．Ｐ＋ｊ．Ｑ）が、０〜（２＾ｗ）−１の範囲の全てのｉおよびｊについて事前計算され（格納コストが約２＾（２ｗ）点である）、これらのうちの１つを反復のたびに加算する。速度は、大体、２＾（２ｗ）（事前計算）に│ｋ│．（１＋１／ｗ）演算を加算した速度である。
【０１５０】
この方式は、任意の数の項に拡張され得る。すなわち、ｋ１．Ｐ１＋ｋ２．Ｐ２＋．．．＋ｋｎ．Ｐｎである。
【０１５１】
図９は、本発明の実施形態によるデータ処理装置を示す。この装置は、初期化部２０と、事前調節倍数計算部２２と、調節計算部２４と、倍数事前計算部２６と、必要な倍数計算部２８と、倍数格納部３０と、倍数選択部３２と、計算部３４と、ディクリメント部３６とを含む。
【０１５２】
以下に、データ処理装置の動作を図１０および１２を参照しながら説明する。図１１は、図１０と同じであるが、方法がフローチャートの形式で示されている。図５および７を参照しながら説明した方法と同様に、図１０のデータ処理装置は、点Ｐの倍数ｋを計算する。この実施形態において、図７を参照しながら上述した、左から右へのウィンドウの倍加および加算アルゴリズムに密接に関連する、アルゴリズムが用いられる。この実施形態において、ウィンドウサイズｗは２であり、具体的な例示は、十進法でｋ＝３５、または二進法で１０００１１である場合について、図１２に示されている。
【０１５３】
メインループ、または反復の実行の前に、初期化部２０は、ローカル格納を宣言し、特定の変数を初期化する。アキュムレータレジスタＲは、ゼロ点Ｏを格納するように初期化され、調節インジケータ「繰り越し」は０に初期化され、ループカウンタｉは│ｋ│／２に初期化される。ここで、│ｋ│は、ｋ（の長さ）におけるビット数である。倍数ｋは、この実施形態において、符号なしであるとされ、偶数のビットであるとされる。ｋが奇数のビットを有する場合、先頭のゼロでパディングされて、│ｋ│が２で割ることができるようにされる必要がある。倍数事前計算部２６は、倍数３Ｐを事前計算し、事前計算された倍数３Ｐおよび点Ｐの両方を倍数格納部３０に格納する。これらの初期化ステップは、図１０において、参照符号Ｓ１で示される。図１２に示す例においては、ｋ＝１０００１１で、ｉは３に初期化される。
【０１５４】
その後、処理演算は、ループ段階に入り、以下のステップが行われる。事前調節倍数計算部２２は、ループｉの基本的な倍数を計算し、これらは、ただ、Ｂ（ｋ，２ｉ−１，２ｉ−２）、または、（２ｋ＿｛２ｉ−１｝−ｋ＿｛２ｉ−２｝）の値である。これは、図７を参照しながら説明された基本的なウィンドウ法において用いられる倍数と同じである。図１２に示す例において、ｉ＝３の第１のループにおいて、基本的な倍数は、２であると決定される。
【０１５５】
基本的なウィンドウ法とは異なり、調節計算部２４は、基本的な倍数に対して行われる調節を、（ある場合には）以前の反復から「繰り越された」値に基づいて決定する。ウィンドウ幅が２である場合、調節は、４＊繰り越しとして計算される。これは、１回目の反復においてはゼロである。その後、必要な倍数計算部２８は、事前調節倍数計算部２２からの基本的な倍数を調節計算部２４からの調節に加算することによって、反復に必要な倍数を決定し、従って、この実施形態において、必要な倍数は、４＊繰り越し＋（２ｋ＿｛２ｉ−１｝−ｋ＿｛２ｉ−２｝）であると決定される。これは、図１０に、ステップＳ２−２の一行目で示されている。図１２の例において、第１のループに必要な倍数は、２Ｐである。
【０１５６】
その後、倍数選択部３２は、必要な倍数が倍数格納部２６から利用可能であるか否かを決定する。この例において、倍数２Ｐは利用可能でなく、次に大きい利用可能な倍数３Ｐが、用いられるために倍数格納部２６から選択される。調節インジケータ「繰り越し」は、必要な倍数と選択された倍数（−Ｐ）との差を示すために−１に設定され、選択された倍数ＭＵＬは計算部３４に送られる。信号ＯＰＲも、選択された倍数が正であるので（調節計算部２４によって行われる調節に起因して、以下に説明するように、Ａ（加算）演算は実際には減算演算であってもよい）、加算演算が必要であることを示すために計算部３４に送られる。その後、計算部３４は、アキュムレータＲの値を用いて、基本的なウィンドウ法として同じ方法で、しかし、必要な倍数ではなく選択された倍数ＭＵＬを用いて、Ｄ（倍加）演算およびＡ（加算）演算を行う。これらの図１０に示すステップは、参照符号Ｓ２−１、および、参照符号Ｓ２−２の様々な場合（図１２の第１の反復のためのケース「２」）によって示される。図１２の例において、アキュムレータＲは、第１の反復後の値３Ｐを有し、調節インジケータ「繰り越し」は、−１である。その後、ディクリメント部３６は、ループカウンタｉをディクリメントし、処理は次の反復に続く。
【０１５７】
次の反復において、必要な倍数は、図１２の例を参照しながら以下に説明されるように、以前の反復からの調節インジケータ「繰り越し」に基づいて決定される。第２のループにおいて、事前調節倍数計算部２２からの基本的な倍数は、０（２Ｋ＿３＋ｋ＿２）であり、調節計算部２４からの倍数は、−４（４＊繰り越し）であり、従って、必要な倍数は、必要な倍数決定部２８によって、−４Ｐであると決定される。倍数格納部３０における倍数の群は、正の倍数Ｐおよび３Ｐのみを含むが、対応する負の倍数、−Ｐおよび−３Ｐを含むことも考えられ得る。第１の反復におけるルールと同じルールを用いて、格納部における次に大きい倍数は−３Ｐであり、−３Ｐ、または、正の倍数３Ｐは、倍数選択部３２によって選択され、信号ＭＵＬとして、計算部３４に送られる。このとき、ＯＰＲ信号が（必要な倍数が負なので）減算演算が必要とされることを示すように設定されている。調節インジケータ「繰り越し」はまた、−Ｐの必要な倍数と選択された倍数との間の差を示すように、−１に設定される。Ａ（加算）ステップにおいて負の倍数−３Ｐを加算する代わりに、正の倍数３Ｐは、ＯＰＲ信号によって示されるように、減算される。これは、図１０において、場合「−４」によって示される。減算演算の前の以前の反復から、２つのＤ（倍加演算）がアキュムレータＲ上で動作する状態で、アキュムレータＲは、「繰り越し」が−１に設定された状態で、第２の反復の終わりにおいて値９Ｐを保持する。
【０１５８】
最終的な反復において、必要な倍数が、第２の反復からの隣接するインジケータ「繰り越し」に依存して計算される。第３のループにおいて、事前調節倍数計算部２２からの基本的な倍数は３であり、調節計算部２４からの倍数は−４であり、必要な倍数は、必要な倍数決定部によって−Ｐであると決定される。上述したように、倍数事前計算部２６における値の群は、正の倍数Ｐおよび３Ｐ、ならびに対応する負の倍数、−Ｐおよび−３Ｐを含むと考えられ得る。従って、必要な倍数−Ｐは、格納部３０から利用可能であり、−Ｐ、または、正の倍数Ｐは、倍数選択部３２によって選択され、減算演算が必要とされることをＯＰＲ信号が示すように設定された状態で、信号ＭＵＬと共に、計算部３４に送られる。調節インジケータ「繰り越し」は、必要な倍数と選択された倍数との間に差がないことを示すように、０に設定される。Ａ（加算）ステップにおいて負の倍数−Ｐを加算するのではなく、ＯＰＲ信号によって示されるように、正の倍数Ｐが減算される。これは、図１０に場合「−１」として示されている。２つのＤ（倍加演算）が、減算演算の前の以前の反復からのアキュムレータＲ上で動作する状態で、アキュムレータＲは、「繰り越し」が０に設定された状態で、第２の反復の終わりに値３５Ｐを保持する。
【０１５９】
第３の反復後、「繰り越し」が０であるので、さらなる調節は必要なく、アキュムレータＲは、正確な最終値３５Ｐを保持し、３５Ｐは、リターンステップＳ４において、返され得る。しかし、ｋの他の値について、調節されるべき「繰り越し」のゼロでない値があり得、これは、図１０の最終的なステップＳ３によって行われる。最終的なステップは、繰り越しが−１である場合、Ｒ：＝Ｒ−Ｐを効率的に行うが、このような演算を実行するかまたは実行しないかは、ｋについての情報をうっかり漏らすことになり得る。従って、最終的な通常の反復後に「繰り越し」の値が何であるかに関わらず、倍加および２つの「加算が」行われるので、ＳＰＡに対して抵抗力がある、図１０に示す最終的なステップを含むことが好ましい。新たな点２Ｐは、最終ステップにおいて計算されるが、古い３Ｐの格納がもはや必要とされていないので用いることができる。従って、最終ステップ（ｉ＝０の場合）は、「繰り越し」がゼロでない場合、ＲからＰを減算するように意図される。ＳＰＡに対して安全にこれを行う方法は多い。図１０の方法は、３Ｐを格納するために用いられる空間を再利用し、代わりに２Ｐを格納する。あるいは、最終的なループ反復（ｉ＝１の場合）が、この調節を行うために変更されてもよい。
【０１６０】
格納部内の全ての倍数が、上記の実施形態においては事前計算されていたが、選択するために利用可能な群にどの倍数があるべきなのかを決定するが、これらの倍数を事前計算しないことも可能である。代わりに、その群のなかの倍数が格納部３０にないことが倍数選択部３２によって決定される場合、事前計算部２６に対して、後で用いられるための、格納部３０に格納され得る倍数を計算させるリクエストがされる。この可能性は、図９において、倍数選択部３２と事前計算部２６との間の点線で示されている。
【０１６１】
上述の実施形態の動作中、１つのループ反復のプロフィールは、プロフィールがＺＺＡである場合の第１のループ以外の全ての場合において、倍加演算が第１回目のあたりで最適化されない限り、（以前に決定された演算分類を用いて）ＤＤＡである。これにより問題は起きない。なぜなら、ｋおよびＰから独立しており、全てのトレースが、２つのこのようなＺ演算を示し、明らかにされる情報がないからである。
【０１６２】
図１３は、ウィンドウサイズがｗ＞＝２の一般的な場合、本発明を具現化する方法を示す。図１４は、図１３の方法をフローチャートの形式で示す。開始される前、ｋのサイズ（ビットの数）は、０ビットを事前にペンディングしておくことによって、ｗビットの倍数に切り上げられる。この実施形態において、格納部としてアレイ「Ｔ」が用いられ、Ｔ：Ｐ、３．Ｐ、５．Ｐ、７．Ｐ、．．．（（２＾ｗ）−１）．Ｐのウィンドウサイズまで、Ｐの奇数の倍数のみが格納される。従って必要な格納部は、基本的なｗビットウィンドウ法に必要な格納部の約半分である。Ｔの第１の要素は、インデックス０を有し、Ｔ［ｊ］は、ｊが０〜２＾（ｗ−１）−１の範囲内について、（２ｊ＋１）．Ｐに等しい。初期的にループカウンタｉは、（│ｋ│／ｗ）に設定される。上述したようにｗが│ｋ│を除算すると仮定されるので、これは全体の数を与える。レジスタＲは、「Ｒ：＝２．Ｒ」をｗ回行うことによって、各ループの始まりにおいて２＾ｗでスケーリングされる。繰り越しインジケータは、Ｒに格納されているＰの倍数が、任意のステップ後に、「大きすぎる」ようになることを可能にする。各反復における繰り越しインジケータは、１度にｗビットが考えられるので、（２＾ｗ）の重みを有する。当然、１つの繰り越しビットが用いられてもよく、ビット値１は−１の繰り越しを表し、ビット値０は繰り越しがないことを表す。
【０１６３】
従って、ケースステートメントは、値「ｖ」で切り替わり、（２＾ｗ）＊繰り越し＋Ｂ（ｋ，ｗ＊ｉ−１，ｗ＊ｉ−ｗ）として定義される。ｖの値に依存して、（２＾ｗ＋１）の場合がある。ｖが奇数である場合、「Ｒ：＝Ｒ＋ｖ．Ｐ；繰り越し＝０」が行われる。ｖが偶数である場合、「Ｒ：＝Ｒ＋（ｖ＋１）．Ｐ；繰り越し＝１」が行われる。いずれの場合においても、必要なＰの倍数は奇数であり、その倍数、またはその負の倍数が、テーブルＴのどこかに格納される。ｍが負である場合にＲ：＝Ｒ＋ｍ．Ｐを行うため、これは、Ｒ：＝Ｒ−（−ｍ）．Ｐと置き換えられる。
【０１６４】
従って、本発明を具現化するデータ処理方法が点（より一般的にはデータアイテム）Ｐの倍数ｋを、反復的ｍ関連ウィンドウアルゴリズムを用いて計算することが分かる。ここで、ｍは、倍数ｋの底である。データアイテムの群は、Ｐの少なくとも１つの倍数を含み、例えば、図９に示す格納部３０に格納する。アルゴリズムの特定の反復について、その反復に必要なＰの倍数が決定され、倍数が、その反復において用いられるために、必要な倍数に依存してその群から選択される。調節インジケータは、必要な倍数と選択された倍数との間の関係に依存して設定される。あとに続く反復において、必要な倍数は、以前の反復からの調節インジケータに依存して決定される。
【０１６５】
場合の選択は、各ステップにおいてどの分岐が選択されるのか攻撃者が判定できないような方法で行われる必要があり、この選択を隠すために、他の防御が必要である可能性がある。これは、一般的な問題であり、解決策は当業者にとって明白である。代表的には、ハードウェアインプリメンテーションにおいて達成することが、ソフトウェアインプリメンテーションよりも簡単である。これは、制御ステートマシンが、計算と並列して実行し、その放射が自然に隠されるからである。この選択は、数ビット（ｋの数ビットおよびいくつかの繰り越しビット）に依存するだけである。１つのサイクルにおいて、全ての分岐のためのテストを並列に（ハードウェアにおいて）計算し、デマルチプレクサを用いてテストに通った（一意的な）分岐を実行することも可能である。このインプリメンテーションの対称性および速度は、電力トレースから選択自体についての何らかの情報を得ることを非常に困難にする。
【０１６６】
ソフトウェアにおいて、インプリメンテーションは、ＣＰＵ命令セットの詳細およびプラットフォームのアーキテクチャに依存する。技術の１つは、中間の値を用いない、条件付き演算がない計算を行うことである。計算の結果は、必要な分岐数に関連させ、１つの分岐命令においてテーブルルックアップ内で用いられ得る。例えば、ｘの奇数および偶数の場合を、ＳＰＡに対して抵抗力がある状態で区別する。
【０１６７】
ｔａｒｇｅｔ［２］：＝［Ｅｖｅｎ，  Ｏｄｄ］；
ｉｎｔ  ｙ：＝ｘ＆１；／＊ｙは、ｘが偶数の場合、０、ｘが奇数の場合、１＊／
ｇｏｔｏ（ｔａｒｇｅｔ［ｙ］）；
Ｅｖｅｎ：  ．．．／＊ｘが偶数の場合はここに＊／
Ｏｄｄ：  ．．．／＊ｘが奇数の場合ここに＊／
本発明の実施形態の動作のさらなる例示が、ｗ＝３の場合について、図１５に示されている。最大値７（３の二進数ビットのウィンドウの場合）までのＰの奇数の倍数のみが、群、すなわち、Ｐ、３Ｐ、５Ｐ、７Ｐに含まれ、これは、図１５において、これらの倍数を囲む実線での輪郭で示されている。この群はまた、上述したように、概念的に、対応する負の倍数−Ｐ、−３Ｐ、−５Ｐおよび−７Ｐを含むと考えられ、これらは、これらの倍数を囲む破線の輪郭で示されている。ＯＰを含む、欠けている偶数の倍数は、破線の輪郭で囲まれた何も書いていない四角によって示されている。必要な倍数が−６、すなわち、群において利用可能でない数であると決定される場合、次に大きい倍数−５が、繰り越しインジケータ−１とともに、群から選択される。これは、選択された倍数が１大きく、次の反復において補正される必要があるからである。倍加（Ｄ）演算が、次の反復の始まりにおいて２回行われ、この繰り越しは、次の反復における−８Ｐ（−２＾３＊Ｐ）調節に変換される。５Ｐの正の倍数が、この群から選択され、アキュムレータ値から減算される。同様に、必要な倍数が、この群において利用可能でないＯＰであると決定される場合、次に大きい倍数１が、繰り越しインジケータ−１とともにこの群から選択される。これは、選択された倍数が１大きく、次の反復において補正される必要があるからである。必要な倍数が、この群において利用可能な５Ｐであると決定される場合、倍数は、次の反復において調節が必要ないので、繰り越しインジケータ０とともにこの群から選択される。
【０１６８】
図１５に示す方式は、ｗ＝３の場合に可能な唯一の方式ではない。図１６に、この群に適切な倍数のさらなる例を示す。図１６においては、奇数の倍数Ｐ、３Ｐ、５Ｐおよび７Ｐではなく、倍数２Ｐ、６Ｐ、１０Ｐおよび１４Ｐがこの群に含まれるように事前選択されている。倍数はさらに広がっているので、繰り越しインジケータは、より柔軟な調節を可能にする必要がある。従って、図１６に示す方式は、繰り越しが｛−１，０｝から選択されるのではなく、｛−２，−１，０，１｝から選択されることを必要とする。これらの繰り越し値は、次の反復に、｛−１６Ｐ，−８Ｐ，０Ｐ，＋８Ｐ｝として繰り越される。０Ｐ．．．７Ｐの基本的な倍数と共に、これによって、次の反復において、可能な、必要な倍数−１６Ｐ．．．＋１５Ｐが得られる。その範囲内の必要な倍数に基づいて、群｛−１４Ｐ，−１０Ｐ，−６Ｐ，−２Ｐ，２Ｐ，６Ｐ，１０Ｐおよび１４Ｐ｝において利用可能な倍数から選択することによって、前と同じ、集合｛−２，−１，０，１｝内の可能な繰り越しインジケータが得られる。従って、後に続く反復において、必要な倍数が利用可能でない場合、集合｛−２，−１，０，１｝内の他の可能な繰り越しを用いて、完全な調節がまた行われ得る。空間面でのコストは、図１５の例と同じ（４つの事前計算された値）であるが、完成ステップは、ここでは、完成および統一する異なる繰り越し状態が４つあるので、わずかに複雑である（しかし、当業者にとっては依然として容易に決定可能である）。
【０１６９】
図１５に示す例のように、奇数の倍数を事前計算し、格納することではなく、偶数の倍数２Ｐ、４Ｐ、６Ｐ、８Ｐを事前計算し、格納することも可能である。奇数の倍数が必要である場合、次に大きい偶数の倍数が選択され、次の反復において、繰り越しインジケータ−１を用いて前と同じように補正される。ゼロ倍数０Ｐが必要とされる場合、ダミー加算が、基本的なウィンドウ法の場合と同じように行われ得る。１つ小さい倍数を選んで上方向に調節するのではなく、１つ大きい倍数を選択し、後に続く反復において負の調節を行う理由は、以下の通りである。通常、ｗ＝３について、範囲０Ｐ．．．７Ｐにおける基本的な倍数が必要とされ得る。０Ｐまたは−８Ｐのいずれかの繰り越しを考慮すると、これは、−８Ｐ．．．＋７Ｐの範囲があり得る。従って、事前計算された倍数０Ｐ．．．７Ｐ、およびその負の数−７Ｐ．．．０Ｐが用いられ得るが、−８Ｐも得るために−Ｐの繰り越しを後回しにする可能性もある。繰り越しが０Ｐまたは＋８Ｐである場合、カバーされる必要がある範囲は、０Ｐ．．．１５Ｐである。事前計算された値の負の値を用いることは、この範囲を効率的に２倍にする。いくつかの状況においては、適切な調節ステップが取られるならば、基本的なウィンドウ法において用いられる倍数の数の半分よりも少ない倍数を用いることが可能である。
【０１７０】
まとめると、ｋの二進数インプリメンテーションを用いる本発明の実施形態は、基本的なウィンドウ法に必要とされ得る倍数の数の約半分の倍数を事前計算および格納することを可能にし得る。ある実施形態において、加算および減算は、ウィンドウ（２＾ｗの場合）を処理するために十分な別の動作を提供するために用いられ、余分な「繰り越し」表現は、次のウィンドウにおいて必要な調節を示すために用いられる。ある実施形態において、（２＾ｗ）−１までのＰの奇数の倍数のみが格納される。ｗビットのウィンドウのそれぞれにおいて、Ｒは、まず、（ｗ回のＤ演算を行うことによって）２＾ｗでスケーリングされ、奇数の倍数のうちの１つの加算または減算のいずれかが行われる（２＾ｗの起こり得る動作が得られ、全てＳＰＡ区別不能Ａ演算である）。奇数の倍数（例えば、ｖ．Ｐ）が必要とされる場合、ｖ．Ｐは（事前計算されており）、ｖが（それぞれ）正であるか負であるかに依存して、単に加算または減算される。Ｐの偶数の倍数（例えば、ｖ．Ｐ）が必要とされる場合、（ｖ＋１）．Ｐが代わりに加算され（ｖ＋１が負である場合において減算演算につながり得）、これが（スケーリング後に余分な（２＾ｗ）．Ｐを減算することによって）次のウィンドウにおいて補正される必要があることを示すために、「繰り越しフラグ」を−１に設定する。そうでない場合、繰り越しフラグは、０である。従って、任意のウィンドウにおいてＲに加算される倍数ｖ．Ｐは、ｖ＝（２＾ｗ）＊繰り越し＋「通常のウィンドウ法が加算したであろう値」として計算される。
【０１７１】
ウィンドウ幅がｗの一般的な場合において、図１３に示す実施形態の格納要件は、２＾（ｗ−１）点（二進法のｋの場合）であり、２＾ｗのオーダーの点の格納を必要とする、相当する基本的なウィンドウ法の要件の約半分である。
【０１７２】
この実施形態は、（２＾（ｗ−１）＋（１＋（１／ｗ））│ｋ│＋２点演算を必要とする（３．Ｐ、５．Ｐ．．．の事前計算は、２＾（ｗ−１）−１点演算を取り、各ループボディは、ｗ回のＤ演算および１つＡ演算からなり、│ｋ│／ｗの反復があり、示唆される最終ステップは３点演算を必要とする）。従って、本発明のこの実施形態は、Ｐの倍数の事前計算がより少ないので、（（２＾ｗ）−２＋（１＋（１／ｗ））│ｋ│点演算を必要とする）基本的なウィンドウ法よりも速い。
【０１７３】
本発明の実施形態における点演算分類（すなわち、「Ａ」、「Ｄ」、または「Ｚ」）のシーケンスは、ｋから完全に独立するようにされ得、任意のダミー演算（結果が計算されるが格納されない）の必要をなくすこともできる。これは、本発明の実施形態を、ＳＰＡに対する抵抗力があるインプリメンテーションに特に適するようにする。
【０１７４】
最初の反復において、ｗ「倍加」演算は、（ＲがＯなので）分類Ｚに含まれるが、これらの演算は、効率のために省かれ得る。省かれない場合でも、いずれにせよ、全てのｋに対して同じように起きるので、ｋについての情報をうっかり漏らすことはない。
【０１７５】
最初の反復の後、Ｒは、Ｏになることはない（ｋが曲線群のオーダーを法とする０とほぼ等しい、数少ないデジェネレートの場合を除く。Ｒが計算の後の段階でＯになり得る場合、実際にはこれは起こらず、いずれにせよ、この計算を行う前にｋが「適切」であることがチェックされ得る）。これは、Ｚ演算にデジェネレートされるＤまたはＡ演算がないことを意味する。これによって、本発明の実施形態は、ＳＰＡ防止に特に適するようになる。
【０１７６】
同様に、Ｒは、第１の反復（Ｒ＝Ｏの場合）においても、「Ｒ：＝（２＾ｗ）．Ｒ」ステップに従うＰの奇数の倍数になることはない。従って、奇数の倍数のみを事前選択された群に用いると、（例えば、Ｒがこの点においてＰまたは−Ｐに等しい場合のように）ＤまたはＺ演算にデジェネレートするＡ演算はない。これによって、本発明の実施形態は、ＳＰＡ防止に特に適するようになる。
【０１７７】
ある実施形態において、全ての条件付き格納は同じ位置で行われる（すなわち、全てレジスタＲに）。従って、格納を観察するための、電力情報がアドレスバス上にない。しかし、（可能性は非常に低いが）繰り越しフラグ、またはオペランド（Ｐ，３Ｐ，５Ｐ．．．）のソースアドレスを観察することによって漏れるデータがあり得る。この起こり得る漏れは、他の（ハードウェア）保護手段がとられる場合、ＳＰＡにとって見えなくなる。
【０１７８】
この対抗手段は、決定論的であるので、これをインプリメントするために、乱数は必要とされない。従って、乱数発生器をディセーブルまたはバイアシングしようと試みる攻撃に対しても抵抗力がある。
【０１７９】
ｗ＝２の場合、３．Ｐを事前計算し、格納することのみが必要であり、他の倍数（Ｐ自体以外）は必要ない。アキュムレータは、この結果について、いずれにせよ必要であり、そのＰは入力パラメータから変えられていないので、オーバーヘッドは、１点に過ぎないと考えられ得る。従って、３ＰまたはＰ自体は、Ｒから任意の時間で、加算または減算され得、４つの演算は、ＳＰＡにおいて区別不可能である。
【０１８０】
ｗ＝２の場合、本発明を具現化する方法は、２＋３│ｋ│／２＋３点演算のみを用いる。（３Ｐの事前計算は、２つの演算を必要とする。各ループボディは、２つのＤ演算および１つのＡ演算からなり、│ｋ│／２の反復がある。示唆されている最終ステップは、３つの演算ｗを取る。）
事前計算は、ループ反復と比較して、それほど時間がかからない（例えば、ｋは１６０ビットを有し得る）。このケースステートメントは、点演算と比較して、無視できるものである。従って、本発明の実施形態の主な利点は、順番に、（１）ＳＰＡ防止（２）空間および（３）速度であると見られ得る。ＳＰＡ防止の利点の一部は、実際に倍数を事前計算および格納することないが、必要に応じて計算を行って、達成され得る。従って、ＳＰＡ防止の利点は、空間および速度面の利点からは独立している。本発明の実施形態は、スマートカードに適用される場合、特に利点を有する。これは、スマートカードは安全である必要があるが、同時に、これを達成するためのリソースが限定されているので、改良されたＳＰＡ防止および低減されたスペース要件が組み合わせられた利点が特に有益だからである。
【０１８１】
本発明の実施形態は、例えば、安全なデバイス上の楕円曲線暗号法の分野に提供される。この文脈における安全なデバイスは、通常の計算システムに取りつけられたハードウェアモジュール、スマートカードチップのような安全なチップ、敵対的な環境における暗号化関数を行う独立型デバイス、セットトップボックスの一部、またはデジタル権管理装置の一部であり得る。リソース（メモリおよび電力）が限定されており、サイドチャネル攻撃に対するセキュリティが極めて重要なデバイスに特に適する。
【０１８２】
本発明の実施形態によって達成される空間面の利点は、基本ウィンドウ法において必要な倍数の数の半分よりも多い倍数が、事前計算され、格納される場合でも達成される。例えば、ｗ＝３の場合、Ｐ、２Ｐ、３Ｐ、５Ｐ、６Ｐ、７Ｐ（すなわち、０Ｐおよび４Ｐ以外全て）の値は、事前計算され、格納され得る。各ループにおいて、必要な倍数が事前格納されているか否かを調べるために単純なチェックがあり得、事前格納されていない場合（Ｏおよび４Ｐの場合）、次に大きい（Ｐおよび５Ｐ）が選択され、繰り越しインジケータは、差（両方の場合において−１）が設定される。
【０１８３】
本発明の実施形態はまた、２以外の底にも適用される。例えば、十進法でｋ＝７１３５であり、ウィンドウがｗ＝２である場合、ｋ＝（７１）（３５）である。例えば、７１Ｐ以外の全てのＰの倍数が事前格納されている場合、２回の反復が以下のように行われる。反復１：Ｒ＝０＊１０＊１０＋７２Ｐ＝７２Ｐ、繰り越しは−１（７１Ｐは利用可能でない）反復２：Ｒ＝７２Ｐ＊１０＊１０＋（３５＋［−１＊１０＊１０］）Ｐ＝７２００Ｐ−６５Ｐ＝７１３５Ｐ、繰り越しは０（６５Ｐは利用可能である）
本発明の実施形態はまた、（ｋ．Ｐ＋ｍ．Ｑ）の決定に拡張され得る。２つの別の繰り越しインジケータが、進行中の各乗算につき１つずつ、保持される。Ｒのスケーリング後、本発明の実施形態の有用なＡステップが２回、ｋのウィンドウについて１回（ｋ繰り越しを用いる、＋／−Ｐ，＋／−３Ｐ，．．．）、ｍのウィンドウについて１回（ｍ繰り越しを用いる、＋／−Ｑ，＋／−３Ｑ，．．．）適用される。これは、合計で約２＾ｗの格納（基本的なウィンドウ法の半分）と、ほぼ、２＾ｗ＋│ｋ│．（１＋２／ｗ）演算（事前計算が少ないので基本的なウィンドウ法よりも少ない）とを有する。
【０１８４】
これは、（基本的なウィンドウ法において用いられ得る方法と同じ方法で）必要とされ得る倍数の各種の組合せを事前計算し、格納することによって、最適化され得る。ｗ＝２の場合、これは、単に、Ｐ＋Ｑ、Ｐ−Ｑ、３Ｐ＋Ｑ、３Ｐ−Ｑ、Ｐ＋３Ｑ、Ｐ−３Ｑ、３Ｐ＋３Ｑ、３Ｐ−３Ｑである。−Ｐ−ＱまたはＱ−Ｐは、Ｐ＋ＱまたはＰ−Ｑをそれぞれ減算することによって得られ、格納される必要がないことに留意されたい。必要とされる格納は、２＾（２ｗ−１）、すなわち、基本的なウィンドウ法の格納の半分だけである。速度は、ほぼ、２＾（２ｗ−１）（事前計算）に│ｋ│．（１＋１／ｗ）演算を加えたものである。
【０１８５】
これは、十分な記憶装置が利用可能であれば、任意の数の項に一般化され得る。
【０１８６】
Ｐに符号付きの二進数値ｋを乗算することができれば有用である。この場合、ｋの最上位ビットは、明示的な負の符号を有するとみなされる。これは、符号付きの二進数値を表す標準的な方法である。この変化は、先頭ビットに負の重みを提供するために第１のループ反復において「ｖ」の計算を変更することによって、本発明のある実施形態に組み込まれ得、「繰り越し」は、最初の反復において常に０であるので、ウィンドウを符号付きの数として処理することは、ｖを、−（２＾ｗ）〜（２＾ｗ）−１までの範囲から出すことがないので、アルゴリズムは前と同じように機能する。
【０１８７】
あるいは、パディング前のｋのサイズｎ＝│ｋ│が、ｗの倍数よりも１大きい場合、繰り越しフラグは、初期的に、ゼロではなく、−ｋ＿｛ｎ−１｝に設定され得、ｋの先頭ビットを捨てた後の（符号なし）バージョンに続く。
【０１８８】
本発明のある実施形態は、ハードウェアまたはソフトウェア、あるいはこれらの組合せにおいてインプリメントされ得、上記で概説した技術的な利点は、このような場合の全てにおいて提供される。図１７は、少なくとも入力／出力、ＣＰＵ、ならびにいくつかのプログラム格納およびワークスペースのためのメモリを有する、スマートカード、または他の安全なプラットフォームにおけるハードウェアとソフトウェアとの間の処理の特定の部分の責任の、４つの異なった割り当て方を示す。暗号コプロセッサがあってもよいし、算術コプロセッサがあってもよいし、コプロセッサがなくてもよい。（ａ）に示すある実施形態において、コプロセッサは、本発明を具現化する方法全体を実行する。（ｂ）に示す他の実施形態において、コプロセッサは、点の倍加および点の加算（おそらくは、点の減算）を実行することができ、ＣＰＵが、外側ループ（ｋのビット）に対処し、本発明を具現化する方法に従って、シーケンスにおいて演算を実行するようにコプロセッサにリクエストする。（ｃ）に示す他の実施形態において、コプロセッサは、フィールド算術演算のみを実行する。ＣＰＵは、本発明を具現化する方法に従って、外側ループを行い、点演算によって必要とされる特定のフィールド演算を実行するようにコプロセッサにリクエストする。（ｄ）に示す他の実施形態においては、コプロセッサがなく、ＣＰＵが、本発明の方法を具現化する方法に従って、全ての関数を実行する。
【０１８９】
本発明を具現化するオペレーティングプログラムは、コンピュータ読み出し可能媒体に格納され得るが、例えば、インターネットウェブサイトから提供されるダウンロード可能なデータ信号のような信号において実現されてもよい。添付の特許請求の範囲は、コンピュータプログラム自体、媒体上の記録としてのコンピュータプログラム、または信号としてのコンピュータプログラム、あるいは任意の他の形態のコンピュータプログラムを含むと解釈される。
【０１９０】
以下は、乗数（ｋ）が秘密であるＥＣＣ点乗算を用いるアルゴリズムの例である。ＥｌＧａｍａｌ暗号法（演算を秘密に保つ必要があるので、ＳＰＡ防止が重要である）は、復号のために点乗算を用いる。ＥｌＧａｍａｌデジタル署名（演算を秘密に保つ必要があるので、ＳＰＡ防止が重要である）は、メッセージの署名のために点乗算を用いる。ＥＣＣＤＳＡも同様である。楕円曲線Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵交換は、対称鍵に一致させるためにＥＣＣ点乗算を用いる（ここでもＳＰＡ防止が重要である）。
【０１９１】
楕円曲線において点乗算は、整数のモジュラ累乗法に類似する。ただし、点倍加および点加算は、それぞれ、モジュラ二乗およびモジュラ乗算に対応する。従って、上記の本発明を具現化する方法および装置は、モジュラ累乗法用に（例えば、公開鍵暗号法システムＲＳＡにおいて用いられるように）容易に変更され得る。
【０１９２】
図１８は本発明のさらなる実施形態を示すブロック図である。図９における部材に厳密に対応する図１８の部材は、類似の参照符号（例えば、２０および２０’）が付けられ、図９の実施形態についての教示内容を図１８の実施形態にどのように適用するかは、当業者にとって明らかである。例えば、（Ｍ＾ｄ  ｍｏｄ  Ｎ）を計算する場合、用いられる方法は、同等であり、図９に関連する上記の記載が適用されるが、ＰがＭと置き換えられ、ｋがｄと置き換えられ、Ａ＋ＢがＡ＊Ｂ  ｍｏｄ  Ｎと置き換えられ、Ａ−ＢがＡ＊（１／Ｂ  ｍｏｄ  Ｎ）と置き換えられ、Ｒが１と初期化される。従って、図１８の詳細な説明は省かれる。
【０１９３】
図１９は、ウィンドウ幅が２である場合の図１８の実施形態の動作を示すフローチャートである。図２０は、ｄ＝３５の例について、図１９の方法の動作を示す図である。これらの２つの図に関する記載は、それぞれ、図１０および１２に関する記載に相当し、従って、これらの図の詳細な説明は省かれる。本発明の実施形態は、（Ｍ＾ｄ）の計算、すなわち、累乗法のみに同等適用可能であり、モジュラ累乗には適用されない。この場合、図１９および２０において行われているように、全てのｍｏｄステートメントが無視され得る。
【０１９４】
除算は、乗算ほど効率的でないので、様々な逆数が、事前計算され得、必要な場合、除数ではなく乗数が用いられる。従って、（１／Ｍ  ｍｏｄ  Ｎ）、（１／Ｍ３ｍｏｄ  Ｎ）、．．．（１／（Ｍ（２＾ｗ）−１）ｍｏｄ  Ｎ）が事前計算され、格納される。このような逆数の事前計算を用いて、この方法は、通常のウィンドウ法とほぼ同じくらい効率的である。しかし、ダミー乗算演算の必要はなくなる。楕円曲線実施形態において、減算は、加算とおなじくらい効率的であり、負の倍数を事前計算する必要はない。
【０１９５】
最終ステップの一部は、除算が遅いため、この適用例において有効でない。従って、「Ｒ：＝Ｒ−２Ｐ」を実行する必要がある１／２Ｐ  ｍｏｄ  Ｎを計算することは避けたい。このステートメントを、２つのモジュラ乗算に相当する「Ｒ：＝Ｒ−Ｐ；Ｒ：＝Ｒ−Ｐ」で置き換えることができる（逆数１／Ｐが事前計算され、２つの乗算演算が得られる）。１／２Ｐ  ｍｏｄ  Ｎの計算は、２Ｐが偶数であり、標準的な方法は失敗するので、困難である。
【０１９６】
モジュラ乗算は、しばしば、Ｍｏｎｔｇｏｍｅｒｙ空間を変換し、通常のモジュラ乗算ではなくＭｏｎｔｇｏｍｅｒｙ乗算を用いて、インプリメントされる。これも、本発明の実施形態を用いることによって可能である。
【０１９７】
楕円曲線上の点は、座標の順序付けられたタプルとして表現され得ることを上述した。これらの座標は、基礎を為す数学的フィールドの要素であり、大きな素数を法とする整数の演算であってもよいし、固定された多項式を法とする多項式の係数と見なされる小さい整数のベクトルの演算であってもよいし、ＣＰＵまたはコプロセッサで計算可能な任意の他の表現であってもよい。本発明の実施形態の有効性は、フィールドの選択または、そのフィールドにおいて定義される曲線の選択とは無関係である。
【０１９８】
以上のように、本発明の好ましい実施形態を用いて本発明を例示してきたが、本発明は、この実施形態に限定して解釈されるべきものではない。本発明は、特許請求の範囲によってのみその範囲が解釈されるべきであることが理解される。当業者は、本発明の具体的な好ましい実施形態の記載から、本発明の記載および技術常識に基づいて等価な範囲を実施することができることが理解される。本明細書において引用した特許、特許出願および文献は、その内容自体が具体的に本明細書に記載されているのと同様にその内容が本明細書に対する参考として援用されるべきであることが理解される。
（要旨）
本発明では、ウィンドウサイズが２である、反復的二進法の左から右への「倍加および加算」タイプアルゴリズムを用いる、データアイテムＰの倍数ｋを計算する、データ処理方法が提供される。少なくとも１つのＰの倍数を含む、データアイテムの選択肢が提供される（Ｓ１）。アルゴリズムの特定の反復において、アルゴリズムの「加算」部分において用いられるための、その反復に必要なＰの倍数が決定される（Ｓ２−２）。その後、必要な倍数に依存して倍数が選択肢から選択され、必要な倍数と選択された倍数との関係に依存して、調節インジケータが設定される（Ｓ２−２）。後に続く反復において、必要な倍数は、以前の反復からの調節インジケータに依存して、決定される（Ｓ２−２）。アルゴリズムの「倍加」部分において用いられる乗数（Ｓ２−１）は、４である。この方法は、ｋの他の底および他のウィンドウサイズに適用可能である。
【図面の簡単な説明】
【０１９９】
【図１】図１は、代表的なスマートカードの主要な部分を示すブロック図である。
【図２】図２は、従来の暗号化モデルを説明するために用いられる例示的なブロック図である。
【図３】図３は、サイドチャネルを含む暗号化モデルを説明するために用いられる例示的なブロック図である。
【図４】図４は、楕円曲線の概念を例示するために用いられる、単純な楕円曲線を示す図である。
【図５】図５は、楕円曲線点乗算の基本的な「倍加および加算」アルゴリズムを示す図である。
【図６】図６は、図５に示すアルゴリズムの演算の一例を示す図である。
【図７】図７は、楕円曲線点乗算を行う基本的なウィンドウ法を、ウィンドウサイズ＞＝２の場合について示す図である。
【図８】図８は、図７に示す方法の演算の一例を示す図である。
【図９】図９は、本発明のある実施形態によるデータ処理装置を示すブロック図である。
【図１０】図１０は、本発明のある実施形態による楕円曲線点乗算を行う方法を、ウィンドウサイズが２の場合について示す図である。
【図１１】図１１は、図１０の方法をフローチャートの形式で示す図である。
【図１２】図１２は、図１０および１１に示す方法の演算の一例を示す図である。
【図１３】図１３は、本発明のある実施形態による楕円曲線点乗算を行う方法を、ウィンドウサイズ＞＝２の場合について示す図である。
【図１４】図１４は、図１３の方法をフローチャートの形式で示す図である。
【図１５】図１５は、本発明のある実施形態における、倍数の選択および繰り越しインジケータの使用の一例を示す例示的な図である。
【図１６】図１６は、本発明のある実施形態における、倍数の選択および繰り越しインジケータの使用の他の例を示す例示的な図である。
【図１７】図１７は、本発明の異なる実施形態における、処理の割り当てを例示するために用いられるブロック図である。
【図１８】図１８は、本発明の他の実施形態によるデータ処理装置を示すブロック図である。
【図１９】図１９は、本発明のある実施形態による、累乗法を行う方法を、ウィンドウサイズ＞＝２の場合について示す図である。
【図２０】図２０は、図１９に示す方法の演算の一例を示す図である。
【図２１】図２１は、楕円曲線点加算および倍加、ならびに負の楕円曲線点を説明するために用いられる楕円曲線の他の例を示す図である。
【符号の説明】
【０２００】
１  スマートカード
２０  初期化部
２２  事前調節倍数計算部
２４  調節計算部
２６  倍数事前計算部
２８  必要な倍数決定部
３０  倍数格納部
３２  倍数選択部
３４  計算部
３６  ディクリメント部
【図１】
2005020735.tif 000003
【図２】
2005020735.tif 000004
【図３】
2005020735.tif 000005
【図４】
2005020735.tif 000006
【図５】
2005020735.tif 000007
【図６】
2005020735.tif 000008
【図７】
2005020735.tif 000009
【図８】
2005020735.tif 000010
【図９】
2005020735.tif 000011
【図１０】
2005020735.tif 000012
【図１１】
2005020735.tif 000013
【図１２】
2005020735.tif 000014
【図１３】
2005020735.tif 000015
【図１４】
2005020735.tif 000016
【図１５】
2005020735.tif 000017
【図１６】
2005020735.tif 000018
【図１７】
2005020735.tif 000019
【図１８】
2005020735.tif 000020
【図１９】
2005020735.tif 000021
【図２０】
2005020735.tif 000022
【図２１】
2005020735.tif 000023