(57)【要約】  汎用的な利用の他、楕円曲線点乗算および暗号システムへの具体的な応用例も有する、奇整数および楕円曲線点乗算を記録するために構成されるシステムおよび方法が開示される。一実施例では、記録は、奇整数ｋを２進表現に変換することによって実行される。２進表現は、例えば、奇整数を表す２のベキの係数とすることができる。２進表現は、その後、どのビットカラムも符号付き奇整数になる、コームビットカラムとして構成される。別の実施例は、この記録方法を利用して、既知のコーム法と比べて楕円曲線点乗算をより効率的に計算し、保存点をよりわずかしかもたない、コーム法の変形を開示する。開示される点乗算方法は、その後、単純電力解析（ＳＰＡ）耐性となるように修正される。
2009500676.tif 000002
【特許請求の範囲】
【請求項１】
記録のためのコンピュータ実行可能命令を有する１つまたは複数のコンピュータ可読媒体であって、前記コンピュータ実行可能命令は、
奇整数ｋを２進表現に変換する命令と、
コームビットカラムの各々が符号付き奇整数であるコームビットカラムとして前記２進表現を構成する命令と
を有することを特徴とする１つまたは複数のコンピュータ可読媒体。
【請求項２】
前記構成する命令は、
各コームビットカラム
【数１】
2009500676.tif 000206
について、
【数２】
2009500676.tif 000207
および
【数３】
2009500676.tif 000208
、ｊ≠０に従って、前記２進表現を構成する命令を有すること
を特徴とする請求項１に記載の１つまたは複数のコンピュータ可読媒体。
【請求項３】
前記構成する命令は、
各ビットカラム内の最低位ビットが１または−１になるように、前記奇整数ｋの前記２進表現の最低位ｄビットの各ビットを変換する命令と、
第ｉ位置にある結果ビットが０または符号付き１になるように、ｄより大きい有効桁にある前記２進表現のビットを変換し、前記符号付き１は、第（ｉ  ｍｏｄ  ｄ）位置にあるビットに従って符号が定められる命令と
を有することを特徴とする請求項１に記載の１つまたは複数のコンピュータ可読媒体。
【請求項４】
前記最低位ｄビットの各ビットを変換する命令は、
インデックスｉが最低位ビットからより高位のビットに移動するループを構成する命令であって、ループ内において、前記最低位ｄビットは、
ｂｉ＝１ならば、
【数４】
2009500676.tif 000209
と設定し、
ｂｉ＝０ならば、
【数５】
2009500676.tif 000210
および
【数６】
2009500676.tif 000211
と設定すること
に従って設定される命令を有することを特徴とする請求項３に記載の１つまたは複数のコンピュータ可読媒体。
【請求項５】
ｄより大きい有効桁にあるビットを変換する前記命令は、
現在ビットの符号を同じコームビットカラム内の最低位ビットの符号と比較する命令を有し、
前記符号が異なり、かつ前記現在ビットが１である場合、前記現在ビットを
【数７】
2009500676.tif 000212
に設定し、ｋの値を維持するために、隣接するより高位のビットの値を１だけインクリメントすること
を特徴とする請求項３に記載の１つまたは複数のコンピュータ可読媒体。
【請求項６】
ｄより大きい有効桁にあるビットを変換する前記命令は、
ｅのための初期値を設定する命令と、
ループを構成する命令であって、ループ内において、
ｅが奇数であり、かつ
【数８】
2009500676.tif 000213
である場合、
【数９】
2009500676.tif 000214
および
【数１０】
2009500676.tif 000215
と設定し、
それ以外の場合、
【数１１】
2009500676.tif 000216
および
【数１２】
2009500676.tif 000217
と設定する命令と
を有することを特徴とする請求項３に記載の１つまたは複数のコンピュータ可読媒体。
【請求項７】
前記記録する命令は、楕円曲線点乗算での使用のために適合され、前記コンピュータ可読媒体は、
点Ｐおよび整数ｋを受け取る命令であって、ｋはさらに偶整数であり得る命令と、
少なくとも部分的にｋの値に基づいて、奇整数であるｋ’を設定する命令と、
前記変換および前記構成に従って、ｋ’に対応するコームビットカラムを計算する命令と、
値Ｑを計算するために前記コームビットカラムおよび前記点Ｐを処理する命令と、
ｋに基づいてＱを導くために、さらなる計算を実行する命令と、
Ｑを出力する命令と
をさらに有することを特徴とする請求項１に記載の１つまたは複数のコンピュータ可読媒体。
【請求項８】
ｋが偶数である場合、ｋ’＝ｋ＋１と設定し、それ以外の場合、ｋ’＝ｋと設定することに従って、ｋ’を設定する命令と、
無限の初期値にＱを設定する命令と、
ループを構成する命令であって、ループ内において、最初にＱが２倍にされ、次に前記点Ｐ倍されたコームビットカラムの量に加算される命令と、
ｋが偶数である場合、ＱからＰを減算する命令と
をさらに有することを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項９】
ｋ’を設定することは、ｋ  ｍｏｄ  ４の値に基づいて、ｋ’を設定する命令を有し、
前記コームビットカラムおよび前記点Ｐを処理することは、ｋ  ｍｏｄ  ４の値に従って、Ｑを設定する命令を有することを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１０】
ｋ’を設定することは、ｋが偶数である場合、ｋ’＝ｋ＋１とし、それ以外の場合、ｋ’＝ｋ＋２とすることに従って、ｋ’を設定する命令を有し、
Ｑを計算するために前記コームビットカラムおよび前記点Ｐを処理することは、ｋが偶数か、それとも奇数かに従って、Ｑを異なるように設定する命令を有することを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１１】
前記方法をＳＰＡ（単純電力解析）に対して耐性をもたせるために、ダミー演算を挿入する命令をさらに含むことを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１２】
ＤＰＡ（差分電力解析）に対する耐性を提供するために、ランダム化技法および楕円曲線の選択を利用する命令をさらに有すること
を特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１３】
奇数位数ρの点Ｐを受け取る命令と、
ρおよびｋの関数としてｋ’を設定する命令と、
Ｑを計算するために前記ビットカラムおよび前記点Ｐを処理する命令であって、前記処理における条件ステップは、ρおよびｋの値に基づいている命令と
をさらに有することを特徴とする請求項７に記載のコンピュータ可読媒体。
【請求項１４】
ｋが奇数である場合、ｋ’＝ｋと設定し、それ以外の場合、ｋ’＝ρ−ｋと設定することに従って、ｋ’を設定する命令と、
無限の初期値にＱを設定する命令と、
ループを構成する命令であって、ループ内において、最初にＱが２倍にされ、次に、ｋが奇数であるか、それとも偶数であるかに応じて、前記点Ｐ倍されたコームビットカラムの量が、Ｑに加算、またはＱから減算される命令と
をさらに有することを特徴とする請求項１３に記載のコンピュータ可読媒体。
【請求項１５】
【数１３】
2009500676.tif 000218
である場合、ｋ＊＝ρ−ｋと設定し、それ以外の場合、ｋ＊＝ｋと設定することに従って、ｋ＊を設定する命令と、
ｋ＊が偶数である場合、ｋ’＝ｋ＊＋１と設定し、それ以外の場合、ｋ’＝ｋ＊＋２と設定することに従って、ｋ’を設定する命令と、
無限の初期値にＱを設定する命令と、
ループを構成する命令であって、ループ内において、最初にＱが２倍にされ、次に、ｋが
【数１４】
2009500676.tif 000219
より大きいかどうかに応じて、前記点Ｐ倍されたコームビットカラムの量が、Ｑから減算、またはＱに加算される命令と、
Ｐ２＝２Ｐを計算する命令と、
ｋが
【数１５】
2009500676.tif 000220
より大きい場合、Δ＝１と設定し、それ以外の場合、Δ＝−１と設定することに従って、Δを設定する命令と、
ｋ＊が偶数である場合、ΔＰをＱに加算し、それ以外の場合、ΔＰ２をＱに加算することに従って、値をＱに加算する命令と
をさらに含むことを特徴とする請求項１３に記載のコンピュータ可読媒体。
【請求項１６】
記録のために構成されるコンピュータシステムであって、前記コンピュータシステムは、
奇整数ｋを受け取る手段と、
前記奇整数ｋを２進表現に変換する手段と、
コームビットカラムとして前記２進表現を構成する手段であって、前記コームビットカラムの各々が符号付き奇整数である手段と、
前記コームビットカラムを出力する手段と
を有することを特徴とするコンピュータシステム。
【請求項１７】
前記変換する手段は、
各コームビットカラム
【数１６】
2009500676.tif 000221
について、
【数１７】
2009500676.tif 000222
および
【数１８】
2009500676.tif 000223
、ｊ≠０に従って、前記２進表現を構成する手段を有することを特徴とする請求項１６に記載のコンピュータシステム。
【請求項１８】
前記変換する手段は、
最低位ｄビットの各ビットを変換する手段であって、インデックスｉが最低位ビットからより高位のビットに移動するループを構成し、ループ内において、前記最低位ｄビットは、
ｂｉ＝１ならば、
【数１９】
2009500676.tif 000224
と設定し、
ｂｉ＝０ならば、
【数２０】
2009500676.tif 000225
および
【数２１】
2009500676.tif 000226
と設定する
ことに従って設定されることを有する手段と、
ｄより大きい有効桁にあるビットを変換する手段であって、
ｅのための初期値を設定することと、
ループを構成し、ループ内において、
ｅが奇数であり、かつ
【数２２】
2009500676.tif 000227
である場合、
【数２３】
2009500676.tif 000228
および
【数２４】
2009500676.tif 000229
と設定し、
それ以外の場合、
【数２５】
2009500676.tif 000230
および
【数２６】
2009500676.tif 000231
と設定することとを有する手段と
を有することを特徴とする請求項１６に記載のコンピュータシステム。
【請求項１９】
楕円曲線点乗算のために構成されるコンピュータシステムであって、
点Ｐおよび偶整数または奇整数である整数ｋを受け取る手段と、
少なくとも部分的にｋの値に基づいて、奇整数であるｋ’を設定する手段と、
コームビットカラムを有する２進表現に前記奇整数ｋ’を変換する手段であって、前記コームビットカラムの各々は、符号付き奇整数である手段と、
値Ｑを計算するために前記コームビットカラムおよび前記点Ｐを処理する手段であって、Ｑは、ｋの異なる値に対して異なって設定され得る手段と、
Ｑを出力する手段と
を有することを特徴とするコンピュータシステム。
【請求項２０】
奇数位数ρの点Ｐを受け取る手段と、
ρおよびｋの関数としてｋ’を設定する手段と、
Ｑを計算するために前記ビットカラムおよび前記点Ｐを処理する手段であって、前記処理における条件ステップは、ρおよびｋの値に基づいている手段と
をさらに有することを特徴とする請求項１９に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線点乗算に関する。
【背景技術】
【０００２】
楕円曲線暗号システム（ＥＣＣ：ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｃｒｙｐｔｏｓｙｓｔｅｍ）は、公開鍵暗号システムの新たに出現したクラスを構成し、スマートカードおよび組み込みシステムなどの応用例において広く適用されている。大部分のＥＣＣの安全性は、楕円曲線上の点からなる群に基づいて離散対数問題（ｄｉｓｃｒｅｔｅ  ｌｏｇａｒｉｔｈｍ  ｐｒｏｂｌｅｍ）を解くことの困難さに基づいている。楕円曲線が正しく選択された場合、離散対数を見つけるために構成された周知の方法で最良のものは、指数関数的に増加する困難さをもつ。したがって、ＥＣＣは、楕円曲線上で離散対数問題を解くための準指数的方法（ｓｕｂ−ｅｘｐｏｎｅｎｔｉａｌ  ｍｅｔｈｏｄ）は存在しないという事実を利用する。ＲＳＡなどのその他の公開鍵暗号システムと比較して、ＥＣＣは、安全性が同じレベルならば、より短い鍵サイズを使用する。これは、記憶、メモリ、および計算能力に対する要求が少ないということになる。
【０００３】
残念なことに、ＥＣＣにおける演算の従来の方法は、サイドチャネル攻撃（ｓｉｄｅ−ｃｈａｎｎｅｌ  ａｔｔａｃｋ）に対して脆弱である。サイドチャネル攻撃は、暗号演算中のタイミングまたは電力消費などの観測可能なパラメータを測定して、暗号システム内の秘密情報の全部または一部を推定する。例えば、コーム法（ｃｏｍｂ  ｍｅｔｈｏｄ）およびその他の効率的な点乗算方法は、電力解析攻撃（ｐｏｗｅｒ−ａｎａｌｙｓｉｓ  ａｔｔａｃｋ）に対して脆弱である。電力解析攻撃は、システムによって消費される電力の解析に基づいている。システムによって使用される電力に関する情報は、攻撃者が、システムによって実行される演算に仮説を設け、最終的にシステム内に含まれる秘密について推測を行うことを支援する。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
スカラ乗算（ｓｃａｌａｒ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）、例えば、楕円曲線点乗算（ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｐｏｉｎｔ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）は、ＥＣＣにおいて重要な役割を果たす。事実、そのような乗算が実行される方法は、異なるサイドチャネル攻撃が有効かどうかにきわめて大きな影響を有する。したがって、改良された方法は、より安全なＥＣＣをもたらす。
【課題を解決するための手段】
【０００５】
汎用的な利用の他、楕円曲線点乗算および暗号システムへの具体的な応用例も有する、奇整数および楕円曲線点乗算を記録するために構成されるシステムおよび方法が開示される。一実施例では、記録は、奇整数ｋを２進表現に変換することによって実行される。２進表現は、例えば、奇整数を表す２のベキの係数とすることができる。２進表現は、その後、コームビットカラム（ｃｏｍｂ  ｂｉｔ−ｃｏｌｕｍｎ）として構成され、どのビットカラムも符号付き奇整数になる。別の実施例では、この記録方法を利用して、既知のコーム法と比べて楕円曲線点乗算をより効率的に計算し、保存点をよりわずかしかもたない、コーム法の変形を開示する。開示される点乗算方法は、その後、単純電力解析（ＳＰＡ：Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）耐性となるように修正される。
【発明を実施するための最良の形態】
【０００６】
詳細な説明が、添付の図面を参照して説明される。図面において、参照番号の左端の数字は、その参照番号が最初に出現した図面を識別する。異なる図面における同じ参照番号の使用は、類似または同一のアイテムを示す。
【０００７】
［概要］
汎用的な利用及び楕円曲線暗号システムへの具体的な応用例を有する、奇整数および楕円曲線点乗算の記録が開示される。一実施例では、奇数スカラを符号付き非ゼロ表現に変換する符号付き奇数限定記録方法（ｓｉｇｎｅｄ  ｏｄｄ−ｏｎｌｙ  ｒｅｃｏｄｉｎｇ  ｍｅｔｈｏｄ）が提示され、この記録方法では、どのコームビットカラム
【０００８】
【数１】
2009500676.tif 000003
【０００９】
も、符号付き奇整数になる。別の実施例では、この記録方法を利用して、既知のコーム法と比べて楕円曲線点乗算をより効率的に計算し、保存点（ｓａｖｅｄ  ｐｏｉｎｔｓ）をよりわずかしかもたない、コーム法の変形を開示する。開示される点乗算方法は、その後、点加算と点減算が楕円曲線システムにおいて実質的に同程度の計算の複雑さをもつという事実を利用することによって、単純電力解析（ＳＰＡ）耐性となるように修正される。開示されるＳＰＡ耐性コーム法は、コーム法の利点を継承するように構成され、事前計算点があらかじめまたは別のところで計算されるとき、その他のＳＰＡ耐性窓法（ＳＰＡ−ｒｅｓｉｓｔａｎｔ  ｗｉｎｄｏｗ  ｍｅｔｈｏｄ）よりもはるかに高速に動作する。ＳＰＡ耐性方法をＤＰＡ耐性方法に変換する技法と組み合わされると、開示されるＳＰＡ耐性コームの実施形態は、すべてのサイドチャネル攻撃に対して安全になる。したがって、本明細書で開示される実施例は、汎用的に有用であるが、特に電力およびコンピューティング資源が貴重であるスマートカードおよび組み込みアプリケーションでの使用に適合される。
【００１０】
［準備］
楕円曲線式は、楕円曲線暗号システム（ＥＣＣ）の主要な特徴である。体Ｋ上の楕円曲線は、そのワイエルシュトラス形式（Ｗｅｉｅｒｓｔｒａｓｓ  ｆｏｒｍ）によって、次のように表現できる。
【００１１】
Ｅ：ｙ２＋ａ１ｘｙ＋ａ３ｙ＝ｘ３＋ａ２ｘ２＋ａ４ｘ＋ａ６、ここで、ａｉ∈Ｆ
上の式および「無限遠点（ｐｏｉｎｔ  ａｔ  ｉｎｆｉｎｉｔｙ）」
【００１２】
【数２】
2009500676.tif 000004
【００１３】
を満たす点（ｘ，ｙ）∈Ｆ２の集合をＥ（Ｆ）によって示す。コードタンジェントプロセス（ｃｈｏｒｄ‐ｔａｎｇｅｎｔ  ｐｒｏｃｅｓｓ）を用いると、Ｅ（Ｆ）は、ゼロを無限遠点
【００１４】
【数３】
2009500676.tif 000005
【００１５】
とするアーベル群（Ａｂｅｌｉａｎ  ｇｒｏｕｐ）を形成する。Ｐ１（ｘ１，ｙ１）およびＰ２（ｘ２，ｙ２）をＥ上の２つの有限点とする。点加算Ｐ３（ｘ３，ｙ３）＝Ｐ１＋Ｐ２は、次のようにして計算される。
【００１６】
１．ｘ１＝ｘ２＝ｘかつｙ１＋ｙ２＝−（ａ１ｘ＋ａ３）ならば、
【００１７】
【数４】
2009500676.tif 000006
【００１８】
２．Ｐ１＝Ｐ２＝（ｘ，ｙ）かつ２ｙ≠−（ａ１ｘ＋ａ３）ならば、
【００１９】
【数５】
2009500676.tif 000007
【００２０】
３．Ｐ１≠±Ｐ２ならば、
【００２１】
【数６】
2009500676.tif 000008
【００２２】
いくつかの有限体Ｆ上の楕円曲線によって生成される群Ｅ（Ｆ）は、離散対数問題を解くのが非常に困難であるという公開鍵暗号要件を満たす。したがって、ＥＣＣは、多くの規格および応用で使用されている。暗号演算の速度を上げるため、楕円曲線点を表すのに射影座標（ｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅ）が使用される。ヤコビ射影座標（Ｊａｃｏｂｉａｎ  ｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅ）を使用することによって、ワイエルシュトラス式を次の形式で書くことができる。
【００２３】
Ｅ：Ｙ２＋ａ１ＸＹＺ＋ａ３ＹＺ３＝Ｘ３＋ａ２Ｘ２Ｚ２＋ａ４ＸＺ４＋ａ６Ｚ６
【００２４】
その場合、無限遠点
【００２５】
【数７】
2009500676.tif 000009
【００２６】
は、すべてのθ∈Ｆ＊について、（θ２，θ３，０）によって表される。アフィン点（ａｆｆｉｎｅ  ｐｏｉｎｔ）（ｘ，ｙ）は、すべてのθ∈Ｆ＊について、（θ２ｘ，θ３ｙ，θ）によって表され、射影点
【００２７】
【数８】
2009500676.tif 000010
【００２８】
は、アフィン点（Ｘ／Ｚ２，Ｙ／Ｚ３）に対応する。射影座標を使用すると、点加算は、より多くの体の乗法演算を行うことと引き換えに、コストのかかる体の逆元演算を行わずに計算することができる。体の乗法演算は、通常、体の逆元演算よりもはるかに高速であり、より高速な楕円曲線点加算を実現する。点がそれ自体に加算される特別な点加算は、２倍算（ｄｏｕｂｌｉｎｇ）と呼ばれる。点の２倍算のコストは、通常、一般的な点の加算のコストとは異なる。
【００２９】
暗号で使用される楕円曲線は、体
【００３０】
【数９】
2009500676.tif 000011
【００３１】
または体Ｆｐ上で定義される楕円曲線であり、ここで、ｍは大きな整数、ｐは大きな素数である。これら２種類の体の上では、楕円曲線のワイエルシュトラス式は、次のより簡単な形式、すなわち、
【００３２】
【数１０】
2009500676.tif 000012
【００３３】
上で定義される、
Ｅ：ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ
またはＦｐ上で定義される、
Ｅ：ｙ２＝ｘ３＋ａｘ＋ｂ
に変形されることができ、ここで、ｐは大きな素数である。これらの式は、点の加算および２倍算を簡単にし、「ショートワイエルシュトラス型（ｓｈｏｒｔ  Ｗｅｉｅｒｓｔｒａｓｓ  ｆｏｒｍ）」と呼ばれることがある。実際の暗号における応用では、楕円曲線は、通常、大きな素数位数ρの部分群を有することが必要とされる。楕円曲線暗号システムは、典型的には、Ｅ（Ｆ）のこの位数ρの部分群の点のみを利用する。
【００３４】
点Ｐをそれ自体にｋ回加算することは、スカラ乗算または点乗算と呼ばれ、ｋを正の整数として、Ｑ＝ｋＰと表される。スカラ乗算のための最も簡単で効率的な方法は、ｋを２進表現に展開する以下の２倍算および加算方法（ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ  ｍｅｔｈｏｄ）である。
【００３５】
図１は、ＥＣＣの文脈に適合可能なスカラ乗算の例示的な２倍算および加算方法１００を示している。ブロック１０２において、２倍算および加算方法１００への入力は、点Ｐと、ｂｉ∈｛０，１｝であるｎビット整数
【００３６】
【数１１】
2009500676.tif 000013
【００３７】
である。ブロック１０４において、点Ｑは、最初に、無限遠点に設定され、すなわち、
【００３８】
【数１２】
2009500676.tif 000014
【００３９】
である。ブロック１０６において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝ｎ−１から０まで−１を増分としてカウントダウンする。ループ内では、ブロック１０８において、Ｑ＝２Ｑと設定され、ブロック１１０において、ｂｉ＝＝１ならば、Ｑ＝Ｑ＋Ｐとする。ブロック１１２において、スカラ乗算の例示的な２倍算および加算方法１００は、Ｑ＝ｋＰの形式で、Ｑを返す。
【００４０】
整数ｋは、（２進）符号付き数字（ＳＤ：Ｓｉｇｎｅｄ  Ｄｉｇｉｔ）表現
【００４１】
【数１３】
2009500676.tif 000015
【００４２】
で表すことができ、ここで、ｓｉ∈｛−１，０，１｝である。非隣接形式（ＮＡＦ：Ｎｏｎ−Ａｄｊａｃｅｎｔ  Ｆｏｒｍ）と呼ばれる特別なＳＤ表現は、特に興味を引くものであり、非ゼロの数字が隣り合うことがなく、すなわち、すべてのｉ≧０について、ｓｉ×ｓｉ＋１＝０となる。どの整数ｋも、一意のＮＡＦを有し、ＮＡＦは、ｋのすべてのＳＤ表現の中で最も小さい重みを有する。２進表現の期待重みがｎ／２であるのに比べて、ｎビット長のＮＡＦの期待重みはｎ／３である。楕円曲線点減算は、点加算と実質的に同じコストを有する。したがって、図２の加算および減算方法（ａｄｄ−ａｎｄ−ｓｕｂｔｒａｃｔ  ｍｅｔｈｏｄ）２００は、ｋについてのＮＡＦを使用すると、２倍算および加算方法１００よりも効率的になる。
【００４３】
図２は、スカラ乗算（すなわち点乗算）のための加算および減算方法２００を示している。ブロック２０２において、加算および減算方法２００への入力は、点Ｐ、及びｓｉ∈｛−１，０，１｝であるｎビットＮＡＦ整数
【００４４】
【数１４】
2009500676.tif 000016
【００４５】
を含む。ブロック２０４において、点Ｑは、最初に、無限遠点に設定され、すなわち、
【００４６】
【数１５】
2009500676.tif 000017
【００４７】
である。ブロック２０６において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝ｎ−１から０まで−１を増分としてカウントダウンする。ループ内では、ブロック２０８において、Ｑ＝２Ｑと設定され、ブロック２１０において、ｓｉ＝＝１ならば、Ｑ＝Ｑ＋Ｐとし、ブロック２１２において、ｓｉ＝＝−１ならば、Ｑ＝Ｑ−Ｐとする。ブロック２１４において、Ｑ＝ｋＰである出力Ｑを返す。
【００４８】
整数ｋは、ｍ進表現に展開することができ、ここで、何らかの整数ｗ≧２として、ｍは通常２ｗに等しい。図３のｍ進方法（ｍ−ａｒｙ  ｍｅｔｈｏｄ）３００は、速度のために記憶を代償にして、スカラ乗算を事前計算ステージと評価ステージに分割する。２倍算および加算方法３００は、ｗ＝１の場合のこの方法の特殊なケースである。
【００４９】
図３は、スカラ乗算のためのｍ進方法３００を示している。ブロック３０２において、ｍ進方法３００への入力は、点Ｐ、及びａｉ∈｛０，１，．．．，ｍ−１｝である整数
【００５０】
【数１６】
2009500676.tif 000018
【００５１】
を含む。ブロック３０４〜３０８は、事前計算ステージを表す。ブロック３０４において、点Ｐ１＝Ｐと設定する。ブロック３０６において、ｉをインデックスとするｆｏｒループなどの、増分１のループ（ｏｎｅ−ｓｔｅｐ  ｌｏｏｐ）に入る。ループは、ｉ＝２からｍ−１までカウントする。増分１のループ内では、ブロック３０６において、Ｐｉ＝Ｐｉ−１＋Ｐと設定する。ブロック３０８において、点Ｑは、最初に、無限遠点に設定され、すなわち、
【００５２】
【数１７】
2009500676.tif 000019
【００５３】
である。ブロック３１０〜３１４は、評価ステージを表す。ブロック３１０において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝ｄ−１から０まで−１を増分としてカウントダウンする。ループ内では、ブロック３１２において、Ｑ＝ｍＱと設定され、これはｗの２倍算を必要とし、ブロック３１４において、
【００５４】
【数１８】
2009500676.tif 000020
【００５５】
と設定される。ブロック３１６において、Ｑ＝ｋＰであるＱを返す。
【００５６】
ｍ進方法の事前計算ステージは、入力点Ｐの記憶を含む、ｍ−１≡２ｗ−１個の点を記憶することを必要とする。本開示の記憶推定は、点Ｐの入力を含んで行われる。方法の時間コストの推定を行うことができる。コスト推定では、
【００５７】
【数１９】
2009500676.tif 000021
【００５８】
を伴う演算はカウントされない。事前計算ステージは、２Ｐ、３Ｐ、．．．、［２ｗ−１］Ｐを計算する必要がある。２倍算と加算の合計は同じままであり、応用例で一般に使用される射影座標を用いる場合、２倍算は加算よりも効率的であるので、２倍算演算の使用が、このステージでは一般に好まれる。効率的な方式は、次のような方法で計算するものである。
【００５９】
【数２０】
2009500676.tif 000022
【００６０】
この方式を使用すると、事前計算は、（２ｗ−１−１）Ｄ＋（２ｗ−１−１）Ａのコストがかかり、ここで、Ｄは点の２倍算を意味し、Ａは点の加算を意味する。評価ステージの時間コストに関しては、最高位の数字がゼロでない、すなわち、ａｄ−１≠０であると仮定すると、このステージの２倍算の数は、ｗ（ｄ−１）である。ａｉ＝０であるならば、ブロック３１４の加算は必要ない。ｋが一様に分布していると仮定すると、評価ステージにおける加算の平均数は、
【００６１】
【数２１】
2009500676.tif 000023
【００６２】
である。したがって、評価ステージにおける平均時間コストは、近似的に
【００６３】
【数２２】
2009500676.tif 000024
【００６４】
であり、平均総時間コストは、近似的に
【００６５】
【数２３】
2009500676.tif 000025
【００６６】
である。
【００６７】
ｍ進方法の修正は、この方法をより効率的にすることができる。例えば、ｍ進方法は、スライディングウィンドウ法（ｓｌｉｄｉｎｇ  ｗｉｎｄｏｗ  ｍｅｔｈｏｄ）に拡張することもできる。コーム法は、点乗算方法のさらなるカテゴリである。スカラ乗算も効率的に計算することができるコーム法が知られている。ｂｉ∈｛０，１｝として、ｎビット整数
【００６８】
【数２４】
2009500676.tif 000026
【００６９】
とする。整数ｗ≧２について、
【００７０】
【数２５】
2009500676.tif 000027
【００７１】
と設定する。その後、［ｂｗ−１，ｂｗ−２，．．．，ｂ１，ｂ０］≡ｂｗ−１２（ｗ−１）ｄ＋．．．＋ｂ１２ｄ＋ｂ０と定義し、ここで、
【００７２】
【数２６】
2009500676.tif 000028
【００７３】
である。これらの計算と一貫性のある方法で、図４のコーム法４００は、整数ｋを表すためにｗ行ｄ列の２進行列を使用し、行列を列方向に処理する。
【００７４】
図４は、スカラ乗算のための固定基底コーム法（ｆｉｘｅｄ−ｂａｓｅ  ｃｏｍｂ  ｍｅｔｈｏｄ）４００を示している。ブロック４０２において、固定基底コーム法４００への入力は、点Ｐ、ｂｉ∈｛０，１｝である整数
【００７５】
【数２７】
2009500676.tif 000029
【００７６】
及び窓幅ｗ≧２を含む。事前計算ステージは、ブロック４０４〜４０８に見られる。ブロック４０４において、すべての
【００７７】
【数２８】
2009500676.tif 000030
【００７８】
について、［ｂｗ−１，．．．，ｂ１，ｂ０］Ｐが計算される。ブロック４０６において、ｋ＝Ｋｗ−１‖．．．‖Ｋ１‖Ｋ０を決定し、ここで、各Ｋｊは長さｄのビット列である。この演算では、左側を１つまたは複数の０（ゼロ）でパディングする必要があることもある。
【００７９】
【数２９】
2009500676.tif 000031
【００８０】
がＫｊの第ｉビットを表すとする。
【００８１】
【数３０】
2009500676.tif 000032
と定義する。ブロック４０８において、点Ｑは、最初に、無限遠点に設定され、すなわち、
【００８２】
【数３１】
2009500676.tif 000033
【００８３】
と設定される。
【００８４】
ブロック４１０〜４１４は、評価ステージを表す。ブロック４１０において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝ｄ−１から０まで−１を増分としてカウントダウンする。ループ内では、ブロック４１２において、Ｑ＝２Ｑと設定され、ブロック４１４において、
【００８５】
【数３２】
2009500676.tif 000034
【００８６】
と設定される。ブロック４１６において、Ｑ＝ｋＰであるＱを返す。
【００８７】
コーム法は、事前計算ステージにおいて、２ｗ−１個の点を記憶する。コーム法の時間コストの推定を行うことができる。事前計算ステージにおいて、
【００８８】
【数３３】
2009500676.tif 000035
【００８９】
について、［ｂｗ−１，．．．，ｂ１，ｂ０］Ｐが計算される必要がある。これを達成するため、２ｄＰ、２２ｄＰ、．．．、２（ｗ−１）ｄＰが最初に計算され、これは、（ｗ−１）ｄ回の２倍算演算のコストがかかる。その後、２倍算演算の結果から、［ｂｗ−１，．．．，ｂ１，ｂ０］Ｐ内の２つのビットだけが非ゼロであるすべての可能な組合せが計算される。
【００９０】
【数３４】
2009500676.tif 000036
【００９１】
個のそのような組合せが存在する。各組合せは、１回の点加算を使用する。このステップにおいて、
【００９２】
【数３５】
2009500676.tif 000037
【００９３】
回の点加算が存在する。次のステップにおいて、３つのビットだけが非ゼロであるすべての組合せが計算される。
【００９４】
【数３６】
2009500676.tif 000038
【００９５】
個のそのような組合せが存在する。各々は、先に計算された結果から、１回の点加算を必要とする。したがって、このステップは、
【００９６】
【数３７】
2009500676.tif 000039
【００９７】
回の点加算のコストがかかる。この手続きは、すべてのビットが非ゼロであるものまで続けられる。事前計算ステージにおける点加算の総数は、したがって、
【００９８】
【数３８】
2009500676.tif 000040
【００９９】
である。
【０１００】
したがって、事前計算ステージにおける時間コストは、
｛（ｗ−１）ｄ｝Ｄ＋｛（２ｗ−ｗ−１）｝Ａ
である。
【０１０１】
評価ステージにおける時間コストを推定するため、
【０１０２】
【数３９】
2009500676.tif 000041
【０１０３】
の最高位桁がゼロでない、すなわち、
【０１０４】
【数４０】
2009500676.tif 000042
【０１０５】
であると仮定する。その場合、評価ステージにおける２倍算演算の数は、（ｄ−１）である。
【０１０６】
【数４１】
2009500676.tif 000043
【０１０７】
である場合、ブロック４１４の点加算は必要ない。ｋが一様に分布していると仮定すると、
【０１０８】
【数４２】
2009500676.tif 000044
【０１０９】
である確率は、
【０１１０】
【数４３】
2009500676.tif 000045
【０１１１】
であり、点加算の平均数は、
【０１１２】
【数４４】
2009500676.tif 000046
【０１１３】
である。したがって、評価ステージにおける平均時間コストは、近似的に
【０１１４】
【数４５】
2009500676.tif 000047
【０１１５】
である。このコストは、先に導かれたように
【０１１６】
【数４６】
2009500676.tif 000048
【０１１７】
であるｍ進方法の評価ステージにおける時間コストよりもはるかに小さい。評価ステージにおけるこの利得は、コーム法の事前計算ステージでのより高い時間コストを代償としている。コーム法の総時間コストは、
【０１１８】
【数４７】
2009500676.tif 000049
【０１１９】
である。
【０１２０】
［サイドチャネル攻撃および対策］
電力解析攻撃の２つのタイプは、単純電力解析（ＳＰＡ）と、差分電力解析（ＤＰＡ：Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）である。ＳＰＡは、スカラ乗算中の暗号装置における単一の電力消費トレースを解析する。記録された電力消費データから、分岐命令条件を識別することができる。これは、楕円曲線２倍算演算の継続を表す。２倍算および加算方法がスカラ乗算を計算する際に使用される場合、秘密の乗数ｋの各ビットの値ｂｉが、この攻撃によって暴かれる。スカラ乗算方法の場合、ＳＰＡは、加算および減算方法もしくはｍ進方法の各数字ｓｉもしくはａｉの値またはコーム法の
【０１２１】
【数４８】
2009500676.tif 000050
【０１２２】
の値を推定することはできないが、数字または
【０１２３】
【数４９】
2009500676.tif 000051
【０１２４】
がゼロかどうかを検出することができ、これは情報漏れに等しい。
【０１２５】
ＤＰＡは、スカラ乗算の多くの電力トレースを記録し、記録間の相関および誤り訂正技法を使用して、秘密ｋの一部または全部の数字を推定する。ＤＰＡは、ＳＰＡよりも複雑であるが強力である。ＳＰＡ耐性のあるスカラ乗算方法は、必ずしもＤＰＡ攻撃に耐性があるわけではないが、ＳＰＡ耐性方法をＤＰＡ耐性方法に変換するために、多くの対策を使用できる。対策は、実行を、ひいては、電力消費を同一の入力に対して異なるものにすることである。この結果を達成するために、通常は、ランダム化が利用される。射影座標における入力点のランダム化、指数パラメータ表現のランダム化、楕円曲線式のランダム化、および体表現のランダム化など、多くのランダム化手法が実現可能である。加えて、これらのランダム化手法の各々は、本明細書で開示されるＳＰＡ耐性方法をＤＰＡ攻撃に耐性があるように変換するために適用することができる。
【０１２６】
有効であるためには、ＥＣＣは、ＳＰＡ攻撃に対する対策を提供しなければならない。本明細書で開示されるＥＣＣを実施する特定の手法は、スカラ乗算の実行を、乗数ｋの特定の値とは独立にする。例えば、２倍算および加算方法をＳＰＡ攻撃に対して耐性のあるものにする簡単な方法は、ｂｉが０であるか、それとも１であるかに関係なく、同じ演算が適用されるように、方法内の分岐演算を除去することである。したがって、分岐なし２倍算および加算方法（ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ−ａｌｗａｙｓ  ｍｅｔｈｏｄ）を構成することができる。
【０１２７】
図５は、ＳＰＡ耐性を提供するための分岐なし２倍算および加算方法５００を示している。ブロック５０２において、分岐なし２倍算および加算方法５００への入力は、点Ｐ、およびｂｉ∈｛０，１｝であるｎビット整数
【０１２８】
【数５０】
2009500676.tif 000052
【０１２９】
を含む。ブロック５０４において、点Ｑ０は、最初に、無限遠点に設定され、すなわち、
【０１３０】
【数５１】
2009500676.tif 000053
【０１３１】
である。ブロック５０６において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝ｎ−１から０まで−１を増分としてカウントダウンする。ループ内では、ブロック５０８において、Ｑ０＝２Ｑ０と設定され、ブロック５１０において、Ｑ１＝Ｑ０＋Ｐと設定され、ブロック５１２において、
【０１３２】
【数５２】
2009500676.tif 000054
【０１３３】
と設定される。ブロック５１４において、Ｑ＝Ｑ０を返し、ここで、ＱはＱ＝ｋＰの形をとる。
【０１３４】
ＳＰＡ攻撃を防御する別の戦略は、図４のコーム法４００における
【０１３５】
【数５３】
2009500676.tif 000055
【０１３６】
を符号付き表現
【０１３７】
【数５４】
2009500676.tif 000056
【０１３８】
に拡張することであり、ここで、各
【０１３９】
【数５５】
2009500676.tif 000057
【０１４０】
は非ゼロである。次の手続きは、コーム法において
【０１４１】
【数５６】
2009500676.tif 000058
【０１４２】
、０≦ｉ＜ｄによって表される奇整数ｋに関するこの符号付き表現
【０１４３】
【数５７】
2009500676.tif 000059
【０１４４】
を獲得するために使用される。ｓ０＝１とし、残りを、Ｋｉ＝０ならば、
【０１４５】
【数５８】
2009500676.tif 000060
【０１４６】
、それ以外ならば、
【０１４７】
【数５９】
2009500676.tif 000061
【０１４８】
と設定することによって構成する。
【０１４９】
コーム法は、従来のコーム法にこの符号付き表現を使用して、ｋが偶数の場合には（ｋ＋１）Ｐを、ｋが奇数の場合には（ｋ＋２）Ｐを計算する。その後、点２Ｐが計算される。所望の点ｋＰを獲得するために、従来のコーム法の結果から、点Ｐまたは２Ｐが減算される。コーム法は、事前計算ステージにおいて、元のコーム法が有するのと同じ時間および空間コスト、すなわち、２ｗ−１個の点の記憶および｛（ｗ−１）ｄ｝Ｄ＋｛（２ｗ−ｗ−１）｝Ａを有する。評価ステージは、ｄ−１回の点加算およびｄ−１回の２倍算のコストがかかる。従来のコーム法の後の最後のステージは、１回の２倍算および１回の減算のコストがかかる。したがって、総コストは、（ｗ−１）ｄ＋（ｄ−１）＋１＝ｗｄ回の２倍算および（２ｗ−ｗ−１）＋（ｄ−ｌ）＋１＝２ｗ−ｗ＋ｄ−１回の加算演算である。図４の方法４００と比較すると、この方法は、同じ記憶コストと、わずかに高い時間コストを有する。
【０１５０】
ａｉ∈｛０，１，．．．，２ｗ−１｝である整数
【０１５１】
【数６０】
2009500676.tif 000062
【０１５２】
に関するさらなるＳＰＡ耐性ｍ進スカラ乗算方法は、最初に、ｋを、ａ’ｉ∈｛−２ｗ，±１，±２，．．．，±（２ｗ−１−１），２ｗ−１｝かつｄ’がｄまたはｄ＋１であるような別の表現
【０１５３】
【数６１】
2009500676.tif 000063
【０１５４】
に変換する。直観的に、この記録方法は、数字０を−２ｗによって置き換え、ｋを変化なく維持するために、隣接するより高位の桁を調整する。この記録方法は、０≦ｃｉ≦２および０≦ｔｉ≦２ｗ＋１である２つの補助値ｃｉおよびｔｉを用いて反復的に表現される。ｃ０＝０と設定する。その後、ｉ＝０，．．．，ｄ＋１について、ｔｉ＝ａｉ＋ｃｉとし、
＝  ｔｉ＝０ならば、（１，−２ｗ）
＝  ０＜ｔｉ＜２ｗ−１ならば、（０，ｔｉ）
（ｃｉ＋１，ａ’ｉ）＝  ２ｗ−１＜ｔｉ＜２ｗならば、（１，−２ｗ＋ｔｉ）
＝  ｔｉ＝２ｗならば、（２，−２ｗ）
＝  ｔｉ＝２ｗ＋１ならば、（１，１）
とする。
【０１５５】
式ｃｉ＋１・２ｗ＋ａ’ｉ＝ｔｉが常に成り立つことに留意されたい。
【０１５６】
変換後、このスカラ乗算方法は、事前計算ステージが、２Ｐ、３Ｐ、．．．、［２ｗ−１］Ｐ、および［−２ｗ］Ｐを計算する必要があることを除いて、ｍ＝２ｗである場合の図３のｍ進方法３００とまさに同じである。２倍算と加算の合計は同じままであり、応用例で一般に使用される射影座標を用いる場合、２倍算は加算よりも効率的であるので、このステージでは、２倍算をできるだけ多く使用したい。最も効率的な方式は、式１を使用して計算し、事前計算ステージのためのコスト（２ｗ−２＋１）Ｄ＋（２ｗ−２−１）Ａを得ることである。評価ステージは、ｄ’＝ｄであるならば、ｗ（ｄ−１）Ｄ＋（ｄ−１）Ａ、またはｄ’＝ｄ＋１であるならば、ｗｄＤ＋ｄＡのコストがかかる。したがって、総コストは、少なくとも（２ｗ−２＋ｗｄ−ｗ＋１）Ｄ＋（２ｗ−２＋ｄ−２）Ａである。加えて、事前計算ステージは、２ｗ−１＋１個の点を記憶する。
【０１５７】
さらなるＳＰＡ耐性奇数限定ｍ進スカラ乗算方法は、ａｉ∈｛０，１，．．．，２ｗ−１｝である奇整数
【０１５８】
【数６２】
2009500676.tif 000064
【０１５９】
を、ａ’ｉ∈｛±１，±３，．．．，±（２ｗ−１）｝であるような別の表現
【０１６０】
【数６３】
2009500676.tif 000065
【０１６１】
に変換するというアイデアに基づいている。これは、以下の記録方法を用いて達成することができる。
【０１６２】
図６は、奇数スカラのためのさらなるＳＰＡ耐性奇数限定ｍ進記録方法６００を示している。ブロック６０２において、奇数限定ｍ進記録方法６００への入力は、ａｉ∈｛０，１，．．．，２ｗ−１｝であるｎビット奇整数
【０１６３】
【数６４】
2009500676.tif 000066
【０１６４】
を含む。ブロック６０４において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝０からｄ−１まで１を増分としてカウントする。ループ内では、ブロック６０６において、ａｉが奇数であれば、ａ’ｉ＝ａｉと設定し、ブロック６０８において、ａｉが偶数であれば、ａ’ｉ＝ａｉ＋１およびａ’ｉ−１＝ａ’ｉ−１−２ｗと設定する。ブロック６１０において、
【０１６５】
【数６５】
2009500676.tif 000067
【０１６６】
である出力
【０１６７】
【数６６】
2009500676.tif 000068
【０１６８】
を返す。
【０１６９】
この変換を使用すると、ｋが偶数の場合には［ｋ＋１］Ｐを、ｋが奇数の場合には［ｋ＋２］Ｐを計算するために、図３のｍ進方法３００が、ｍ＝２ｗとして使用される。その後、所望のｋＰを獲得するために、図３の方法３００の結果から、Ｐまたは２Ｐが減算される。方法６００は、２ｗ−１個の点Ｐ、３Ｐ、５Ｐ、．．．、［２ｗ−１］Ｐを記憶する必要がある。これらの点は、事前計算ステージにおいて、最初に２Ｐを計算し、その後、残りを式［ｉ］Ｐ＝２Ｐ＋［ｉ−２］Ｐを用いて反復的に計算することによって、計算することができる。このステージにおけるコストは、１Ｄ＋（２ｗ−１−１）Ａである。評価ステージにおけるｆｏｒループは、ｗ（ｄ−１）Ｄ＋（ｄ−１）Ａのコストがかかり、後処理ステージは、２Ｐを計算する１回の２倍算と、Ｐまたは２Ｐを減算する１回の減算のコストがかかる。ＯＴの方法の総コストは、したがって、（ｗｄ−ｗ＋２）Ｄ＋（２ｗ−１＋ｄ−１）Ａである。
【０１７０】
［奇数限定コーム法］
奇数限定コーム法（ｏｄｄ−ｏｎｌｙ  ｃｏｍｂ  ｍｅｔｈｏｄ）は、ＥＣＣにおける既知のコーム法と比べて著しい向上を含む。奇数限定コームの実施形態は、スカラｋのすべてのコームビットカラム
【０１７１】
【数６７】
2009500676.tif 000069
【０１７２】
を、符号付き非ゼロ表現
【０１７３】
【数６８】
2009500676.tif 000070
【０１７４】
に変換する。既知の技法からの重大な相違において、生成されたどの
【０１７５】
【数６９】
2009500676.tif 000071
【０１７６】
も、符号付き奇整数である。より具体的には、この実施形態は、各コームビットカラム
【０１７７】
【数７０】
2009500676.tif 000072
【０１７８】
について、
【０１７９】
【数７１】
2009500676.tif 000073
【０１８０】
と、
【０１８１】
【数７２】
2009500676.tif 000074
【０１８２】
、ｊ≠０を生成し、ここで、
【０１８３】
【数７３】
2009500676.tif 000075
【０１８４】
は−１と定義される。有利なことに、事前計算ステージは、ＥＣＣにおける従来のコーム法の半数の点を計算し、保存しさえすればよい。
【０１８５】
図７は、奇数スカラのための符号付き奇数限定コーム記録方法７００の例示的な詳細を示している。方法７００は、コーム楕円曲線点乗算での使用のために適合された楕円曲線計算を実行する。この記録方法７００は、
【０１８６】
【数７４】
2009500676.tif 000076
【０１８７】
である窓幅ｗ≧２について構成される。方法７００への入力は、ｂｉ∈｛０，１｝であるｎビット奇整数
【０１８８】
【数７５】
2009500676.tif 000077
【０１８９】
を含む。方法からの出力は、
【０１９０】
【数７６】
2009500676.tif 000078
【０１９１】
を含み、ここで、各Ｋ’ｊは、ｄビット長のバイナリ列であり、必要ならば左側を０でパディングする。図７内では、
【０１９２】
【数７７】
2009500676.tif 000079
【０１９３】
は、Ｋ’ｊの第ｒビットを表すとし、すなわち、
【０１９４】
【数７８】
2009500676.tif 000080
【０１９５】
である。
【０１９６】
【数７９】
2009500676.tif 000081
【０１９７】
と定義する。出力は、ｊ≠０かつ０≦ｒ＜ｄについて、
【０１９８】
【数８０】
2009500676.tif 000082
【０１９９】
および
【０２００】
【数８１】
2009500676.tif 000083
【０２０１】
を満たす。
【０２０２】
図７を参照すると、奇数スカラのための符号付き奇数限定コーム記録方法７００の演算を理解することができる。ブロック７０２において、入力が、ｂｉ∈｛０，１｝である
【０２０３】
【数８２】
2009500676.tif 000084
【０２０４】
に従ってｎビット奇整数に設定される。ブロック７０４において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝０からｄ−１まで１を増分としてカウントする。ループ内では、ブロック７０６において、ｂｉ＝１ならば、
【０２０５】
【数８３】
2009500676.tif 000085
【０２０６】
と設定し、ブロック７０８において、ｂｉ＝０ならば、
【０２０７】
【数８４】
2009500676.tif 000086
および
【０２０８】
【数８５】
2009500676.tif 000087
【０２０９】
と設定する。ブロック７１０においてループを抜ける時、
【０２１０】
【数８６】
2009500676.tif 000088
【０２１１】
およびｉ＝ｄと設定する。ブロック７１２において、ｉをインデックスとする、ｉ＜ｗｄの間続くように構成されるｗｈｉｌｅループなどのループに入る。ループ内では、ブロック７１４において、ｅが奇数、かつ
【０２１２】
【数８７】
2009500676.tif 000089
【０２１３】
である状況は、
【０２１４】
【数８８】
2009500676.tif 000090
【０２１５】
および
【０２１６】
【数８９】
2009500676.tif 000091
【０２１７】
と設定することによって対処され、ブロック７１６において、それ以外の状況は、
【０２１８】
【数９０】
2009500676.tif 000092
【０２１９】
および
【０２２０】
【数９１】
2009500676.tif 000093
【０２２１】
と設定することによって対処される。ブロック７１８において、ｉ＝ｉ＋１と設定することによって、ｉがインクリメントされる。ブロック７２０において、各Ｋ’ｊが、成分ビットとして
【０２２２】
【数９２】
2009500676.tif 000094
【０２２３】
を有し、必要ならば左側を０でパディングしたｄビット長のバイナリ列である、出力
【０２２４】
【数９３】
2009500676.tif 000095
【０２２５】
が返される。
【０２２６】
方法７００は、最初に、
【０２２７】
【数９４】
2009500676.tif 000096
【０２２８】
という事実を利用して、最後（すなわち最低位）のｄビットの各ビットを、１または
【０２２９】
【数９５】
2009500676.tif 000097
【０２３０】
に変換する。言い換えると、Ｋ’０内の各ビット
【０２３１】
【数９６】
2009500676.tif 000098
【０２３２】
、０≦ｒ＜ｄは、１または
【０２３３】
【数９７】
2009500676.tif 000099
【０２３４】
である。記録方法の残りは、第ｄビットから最高位ビットまでの各ビットを処理する。現在のビットが１であり、同じコームビットカラム
【０２３５】
【数９８】
2009500676.tif 000100
【０２３６】
内の最低位ビットと異なる符号を有する場合、現在のビットは、
【０２３７】
【数９９】
2009500676.tif 000101
【０２３８】
に設定され、残りのより高位のビットからなる値は、ｋの値を変化なく維持するために、１を加算される。この処理は、ｎビット奇整数ｋを表すｗｄビット
【０２３９】
【数１００】
2009500676.tif 000102
【０２４０】
を生成する。
【０２４１】
したがって、図７の方法７００は、奇数スカラｋを与えられた場合、一連のビット列
【０２４２】
【数１０１】
2009500676.tif 000103
【０２４３】
と、
【０２４４】
【数１０２】
2009500676.tif 000104
【０２４５】
とを出力し、
【０２４６】
【数１０３】
2009500676.tif 000105
【０２４７】
であり、
【０２４８】
【数１０４】
2009500676.tif 000106
【０２４９】
については、
【０２５０】
【数１０５】
2009500676.tif 000107
【０２５１】
、および
【０２５２】
【数１０６】
2009500676.tif 000108
【０２５３】
、ｊ≠０かつ０≦ｒ＜ｄであり、ここで、
【０２５４】
【数１０７】
2009500676.tif 000109
【０２５５】
である。上述の言明は、次のようにして証明することができる。方法７００によって生成された各
【０２５６】
【数１０８】
2009500676.tif 000110
【０２５７】
が、
【０２５８】
【数１０９】
2009500676.tif 000111
【０２５９】
、および
【０２６０】
【数１１０】
2009500676.tif 000112
【０２６１】
、ｊ≠０という条件を満たすことは、ｋが奇数であり、ｂ０＝１であるので、明らかである。ブロック７０４〜７０８は、
【０２６２】
【数１１１】
2009500676.tif 000113
【０２６３】
内の最終ビット
【０２６４】
【数１１２】
2009500676.tif 000114
【０２６５】
を、１または
【０２６６】
【数１１３】
2009500676.tif 000115
【０２６７】
となるように設定する。したがって、
【０２６８】
【数１１４】
2009500676.tif 000116
【０２６９】
である。方法７００では、
【０２７０】
【数１１５】
2009500676.tif 000117
【０２７１】
である場合、
【０２７２】
【数１１６】
2009500676.tif 000118
【０２７３】
は、ブロック７１４によって、
【０２７４】
【数１１７】
2009500676.tif 000119
【０２７５】
に設定され、またはブロック７１６によって、０に設定される。
【０２７６】
【数１１８】
2009500676.tif 000120
【０２７７】
である場合、
【０２７８】
【数１１９】
2009500676.tif 000121
【０２７９】
は、ブロック７１６によって、０または１に設定される。これは、各
【０２８０】
【数１２０】
2009500676.tif 000122
【０２８１】
内の最低位ビットを除くすべてのビットが、０であるか、または最低位ビットと同じ値を有することを意味する。
【０２８２】
【数１２１】
2009500676.tif 000123
【０２８３】
を証明するため、最初に、
【０２８４】
【数１２２】
2009500676.tif 000124
【０２８５】
を証明する。
【０２８６】
これは、０≦ｊ＜ｄについて、
【０２８７】
【数１２３】
2009500676.tif 000125
【０２８８】
であることを証明する帰納法によって行うことができる。ｋは奇数であるので、ｊ＝０について、式は成り立つ。ｊ−１＜ｄについて、式が真である場合、方法７００のステップ２および３は、ｊ＜ｄについても、式が真であることを保証する。ｊ＝ｄ−１と設定することによって、所望の式が得られる。
【０２８９】
ブロック７１４の前で第ｉループに入る時のｅの値をｅｉで表し、ここで、ｉ＞ｄである。発明者らは、ｉ≧ｄについて、
【０２９０】
【数１２４】
2009500676.tif 000126
【０２９１】
が常に真であることを主張する。これは、帰納法によって行うことができる。式２を使用することによって、
【０２９２】
【数１２５】
2009500676.tif 000127
【０２９３】
を得る。これは、ｉ＝ｄについて、式３が成り立つことを証明する。ｉ＞ｄについて、式３が真であると仮定する。ｅｉが奇数、かつ
【０２９４】
【数１２６】
2009500676.tif 000128
【０２９５】
である場合、
【０２９６】
【数１２７】
2009500676.tif 000129
【０２９７】
、
【０２９８】
【数１２８】
2009500676.tif 000130
【０２９９】
、および
【０３００】
【数１２９】
2009500676.tif 000131
【０３０１】
を得る。
【０３０２】
同様の手続きが、ｅｉが偶数、かつ
【０３０３】
【数１３０】
2009500676.tif 000132
【０３０４】
である場合に、
【０３０５】
【数１３１】
2009500676.tif 000133
【０３０６】
を証明するために使用することができる。これは、ｉ＋１について、式３がやはり真であることを意味する。したがって、ｉ≧ｄについて、式３が成り立つ。
【０３０７】
証明の必要がある最後のことは、ｅｗｄ＝０である。ｋはｎビットの整数であるので、
【０３０８】
【数１３２】
2009500676.tif 000134
【０３０９】
は、ｎ−ｄビットの整数、すなわち、ｅｄ＜２ｎ−ｄである。ｎ≧ｉ≧ｄについて、
ｅｉ≦２ｎ−ｉ                                                          （４）
であることを証明するために、帰納法を使用したい。
【０３１０】
ｉ＝ｄのときは、すでに証明されている。ｎ＞ｉ≧ｄであるｉについて、真であると仮定する。ｅｉが奇数である場合、不等式は、ｅｉ≦２ｎ−ｉ−１であることを含意する。この場合、ブロック７１４〜７１６は、
【０３１１】
【数１３３】
2009500676.tif 000135
【０３１２】
を与え、すなわち、この場合、ｉ＋１について、式３は真である。ｅｉが偶数である場合、ブロック７１６から、
【０３１３】
【数１３４】
2009500676.tif 000136
【０３１４】
である。
【０３１５】
式３は、依然として成り立つ。言い換えると、ｉ＋１≦ｎについて、式４は真である。したがって、式（４）は、ｎ≧ｉ≧ｄについて、真であると証明される。式４は、ｅｎ≦２０＝１であることを導く。
【０３１６】
【数１３５】
2009500676.tif 000137
【０３１７】
であるので、ｎ＋１≦ｗｄを得る。ｎ＋１＝ｗｄである場合、ｅｗｄ−１≡ｅｎ≦１である。ｎ＋１＜ｗｄである場合、ブロック７１４〜７１６から、
【０３１８】
【数１３６】
2009500676.tif 000138
【０３１９】
である。このプロセスを継続すると、やはりｅｗｄ−１≦１を得る。言い換えると、常にｅｗｄ−１≦１を得る。ブロック７０６〜７０８から、
【０３２０】
【数１３７】
2009500676.tif 000139
【０３２１】
を得る。ブロック７１２〜７１８のループ内でｉ＝ｗｄ−１である場合、
【０３２２】
【数１３８】
2009500676.tif 000140
【０３２３】
であるので、ブロック７１６が実行され、すなわち、
【０３２４】
【数１３９】
2009500676.tif 000141
【０３２５】
である。この結果を式３に適用することで、所望の結果
【０３２６】
【数１４０】
2009500676.tif 000142
【０３２７】
が得られる。
【０３２８】
図７の記録方法７００は、奇数スカラを用いる場合に限って機能する。スカラｋが偶整数である場合、図８の方法８００が利用できる。図８では、最初に、奇数スカラｋ’＝ｋ＋１について点乗算を計算し、その後、結果からＰを減算して、所望の結果ｋＰを獲得する。
【０３２９】
図８は、符号付き奇数限定コーム法８００の演算を示している。ブロック８０２において、点Ｐおよび整数ｋ＞０を含む入力が受け取られる。事前計算ステージは、ブロック８０４〜８１０を含む。ブロック８０４において、すべての（ｂｗ−１，．．．，ｂ２，ｂ１）∈（Ｚ２）ｗ−１についての［ｂｗ−１，．．．，ｂ２，ｂ１，１］Ｐの計算を含む、事前計算の計算が行われる。ブロック８０６において、ｋが偶数である場合、ｋ’＝ｋ＋１と設定し、それ以外の場合、ｋ’＝ｋと設定する（ｋが偶数である場合、ｋ’＝ｋ−１と設定し、それ以外の場合、ｋ’＝ｋと設定することもできることに留意されたい）。ブロック８０８において、図７の方法７００が、ｋ’に適用されて、対応するコームビットカラム
【０３３０】
【数１４１】
2009500676.tif 000143
【０３３１】
を計算する。ブロック８１０において、点Ｑは、最初に、無限遠点に設定され、すなわち、
【０３３２】
【数１４２】
2009500676.tif 000144
【０３３３】
と設定される。ブロック８１２〜８１８は、評価ステージを構成する。ブロック８１２において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝ｄ−１から０まで−１を増分としてカウントダウンする。ループ内では、ブロック８１４において、Ｑ＝２Ｑと設定し、ブロック８１６において、
【０３３４】
【数１４３】
2009500676.tif 000145
【０３３５】
と設定する。ブロック８１８において、Ｑ＝ｋＰの形をとる出力が返され、ｋが偶数である場合、Ｑ−Ｐが返され、それ以外の場合、Ｑが返される（ｋ’＝ｋ−１である場合は、ｋが偶数のとき、Ｐを加算することに留意されたい）。
【０３３６】
【数１４４】
2009500676.tif 000146
【０３３７】
の最低位ビットが
【０３３８】
【数１４５】
2009500676.tif 000147
【０３３９】
である場合、
【０３４０】
【数１４６】
2009500676.tif 000148
【０３４１】
を得る。この場合、方法８００のブロック８１６は、実際には
【０３４２】
【数１４７】
2009500676.tif 000149
【０３４３】
を実行する。
【０３４４】
実際のＥＣＣ応用例では、大きな素数位数ρを有する部分群内の楕円曲線点のみが、実際に使用される。この場合、符号付き奇数限定コーム法８００は、ｋが偶数ならばρ−ｋは奇数であり、［ρ−ｋ］Ｐ＝−ｋＰであるという事実を利用して、後処理ブロック８１８を除去するように修正することができる。この修正方法は、図９で説明される。
【０３４５】
図９は、奇数位数の点のための符号付き奇数限定コーム法の演算を示している。ブロック９０２において、奇数位数ρの点Ｐおよび整数ｋ＞０を含む入力が受け取られる。事前計算ステージは、ブロック９０４〜９１０を含む。ブロック９０４において、事前計算の計算が行われる。例えば、［ｂｗ−１，．．．，ｂ２，ｂ１，１］Ｐが、すべての（ｂｗ−１，．．．，ｂ２，ｂ１）∈（Ｚ２）ｗ−１について計算される。ブロック９０６において、ｋ’が設定される。特に、ｋが奇数である場合、ｋ’＝ｋと設定し、それ以外の場合、ｋ’＝ρ−ｋと設定する。ブロック９０８において、図７の方法７００が、ｋ’に適用され、それによって、ｋ’に対応するコームビットカラム
【０３４６】
【数１４８】
2009500676.tif 000150
【０３４７】
を計算する。ブロック９１０において、点Ｑは、最初に、無限遠点に設定され、すなわち、
【０３４８】
【数１４９】
2009500676.tif 000151
【０３４９】
と設定される。ブロック９１２〜９１６は、評価ステージを構成する。ブロック９１２において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝ｄ−１から０まで−１を増分としてカウントダウンする。ループ内では、ブロック９１４において、Ｑ＝２Ｑと設定し、ブロック９１６において、
【０３５０】
【数１５０】
2009500676.tif 000152
【０３５１】
と設定する。ブロック９１８において、Ｑ＝ｋＰの形をとるＱが返される。上のブロック９１６において、Ｑは、ｋが奇数ならば、
【０３５２】
【数１５１】
2009500676.tif 000153
【０３５３】
、またはｋが偶数ならば、
【０３５４】
【数１５２】
2009500676.tif 000154
【０３５５】
に設定されることに留意されたい。
【０３５６】
図７の記録方法７００では、ｄは、図４の元の固定基底コーム法４００において使用された
【０３５７】
【数１５３】
2009500676.tif 000155
【０３５８】
の代わりに、
【０３５９】
【数１５４】
2009500676.tif 000156
【０３６０】
と定義される。ｎがｗで整除不能である場合、発明者らの記録方法におけるｄは、元のコーム法とまさに同じ、すなわち、
【０３６１】
【数１５５】
2009500676.tif 000157
【０３６２】
である。しかし、ｎがｗで整除可能である場合、発明者らの方法のｄは、方法４００で使用されたｄよりも１大きく、すなわち、
【０３６３】
【数１５６】
2009500676.tif 000158
【０３６４】
である。ｄを１だけ増やすことは、事前計算ステージにおけるｗ−１個の追加の２倍算と、評価ステージにおける１個の追加の加算および１個の追加の２倍算とを生じさせる。どのような追加の演算も望ましくない。幸いなことに、ｎがｗで整除可能である場合の追加の演算の大部分は、以下の修正コーム法において説明される考え抜かれた操作によって排除することができる。
【０３６５】
図１０は、ｗで整除可能なｎのための符号付き奇数限定コーム法の演算を示している。ブロック１００２において、点Ｐおよびｎビット整数ｋ＞０を含む入力が受け取られる。事前計算ステージは、ブロック１００４〜１０１０を含む。ブロック１００４において、事前計算の計算が行われる。例えば、［ｂｗ−１，．．．，ｂ２，ｂ１，１］Ｐが、すべての（ｂｗ−１，．．．，ｂ２，ｂ１）∈（Ｚ２）ｗ−１について計算される。ブロック１００６において、ｋ  ｍｏｄ  ４が評価され、ｋ’が設定される。特に、ｋ  ｍｏｄ  ４＝０の場合、ｋ’＝ｋ／２＋１と設定し、ｋ  ｍｏｄ  ４＝１の場合、
【０３６６】
【数１５７】
2009500676.tif 000159
【０３６７】
と設定し、ｋ  ｍｏｄ  ４＝２の場合、ｋ’＝ｋ／２と設定し、ｋ  ｍｏｄ  ４＝３の場合、
【０３６８】
【数１５８】
2009500676.tif 000160
【０３６９】
と設定する。ブロック１００８において、方法７００が、ｋ’に適用されて、対応するコームビットカラム
【０３７０】
【数１５９】
2009500676.tif 000161
【０３７１】
を計算する。ブロック１０１０において、点Ｑは、最初に、無限遠点に設定され、すなわち、
【０３７２】
【数１６０】
2009500676.tif 000162
【０３７３】
と設定される。評価ステージは、ブロック１０１２〜１０２６を含む。ブロック１０１２において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝ｄ−１から０まで−１を増分としてカウントダウンする。ループ内では、ブロック１０１４において、Ｑ＝２Ｑと設定し、ブロック１０１６において、
【０３７４】
【数１６１】
2009500676.tif 000163
【０３７５】
と設定する。ブロック１０１８において、ｋ  ｍｏｄ  ４＝０ならば、Ｑ＝Ｑ−Ｐと設定する。ブロック１０２０において、Ｑ＝２Ｑと設定する。ブロック１０２２において、ｋ  ｍｏｄ  ４＝１ならば、Ｑ＝Ｑ−Ｐと設定し、ブロック１０２４において、ｋ  ｍｏｄ  ４＝３ならば、Ｑ＝Ｑ＋Ｐと設定する。ブロック１０２６において、Ｑ＝ｋＰの形をとるＱが返される。
【０３７６】
ブロック１００６の結果、方法１０００で使用されるｄの値は、
【０３７７】
【数１６２】
2009500676.tif 000164
【０３７８】
に等しく、元のコーム法４００と同じである。方法８００と比較すると、方法１０００は、ｎがｗで整除可能である場合、事前計算ステージにおいて、ｗ−１個の２倍算を不要にする。この場合、ｋ  ｍｏｄ  ４＝２ならば、評価ステージにおいて、１個の加算も不要にされる。様々な方法のさらなる性能比較は、後ほど本明細書において与えられる。
【０３７９】
方法８００および１０００は、ＳＰＡ耐性ではない。両方の方法で、すべてのコームビットカラム
【０３８０】
【数１６３】
2009500676.tif 000165
【０３８１】
は非ゼロであるが、スカラｋの最終ビットの値は、ＳＰＡによって、図８のブロック８１８で検出可能であり、スカラｋの最終２ビットの情報は、ＳＰＡによって、図１０のブロック１０１６に続くステップから漏れることがある。すべての
【０３８２】
【数１６４】
2009500676.tif 000166
【０３８３】
であるので、３つのコーム法８００、９００、１０００のすべてについて、ｆｏｒループ内の演算は、点２倍算と点加算が交替する系列ＤＡＤＡ．．．ＤＡＤＡをなし、したがって、秘密スカラｋについての情報をＳＰＡに漏らさない。これは、ρを点Ｐの位数として、
【０３８４】
【数１６５】
2009500676.tif 000167
【０３８５】
ビットの整数として、すべてのスカラｋ（またはより具体的には、図９のブロック９０６におけるｋ’）をとるならば、方法９００がＳＰＡ耐性コーム法になることを含意する。それは、ＳＰＡ耐性方法を研究する際の一般的な仮定である。潜在的なダミー演算をｆｏｒループの後に挿入することによって、上記のＳＰＡ非耐性方法をＳＰＡ耐性方法に変換することができる。方法８００は、以下のＳＰＡ耐性コーム法に修正することができる。
【０３８６】
図１１は、ＳＰＡ耐性符号付き奇数限定コーム法１１００の演算を示している。ブロック１１０２において、入力の点Ｐおよび整数ｋ＞０が受け取られる。事前計算ステージは、ブロック１１０４〜１１１０を含む。ブロック１１０４において、事前計算の計算が行われる。例えば、［ｂｗ−１，．．．，ｂ２，ｂ１，１］Ｐが、すべての（ｂｗ−１，．．．，ｂ２，ｂ１）∈（Ｚ２）ｗ−１について計算される。ブロック１１０６において、ｋが偶数である場合、ｋ’＝ｋ＋１と設定し、それ以外の場合、ｋ’＝ｋ＋２と設定する。ブロック１１０８において、方法７００が、ｋ’に適用されて、対応するコームビットカラム
【０３８７】
【数１６６】
2009500676.tif 000168
【０３８８】
を計算する。ブロック１１１０において、点Ｑは、最初に、無限遠点に設定され、すなわち、
【０３８９】
【数１６７】
2009500676.tif 000169
【０３９０】
と設定される。評価ステージは、ブロック１１１２〜１１２０を含む。ブロック１１１２において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝ｄ−１から０まで−１を増分としてカウントダウンする。ループ内では、ブロック１１１４において、Ｑ＝２Ｑと設定し、ブロック１１１６において、
【０３９１】
【数１６８】
2009500676.tif 000170
【０３９２】
と設定し、ブロック１１１８において、Ｐ２＝２Ｐと設定する。ブロック１１２０において、Ｑ＝ｋＰの形をとる出力が返される。特に、ｋが偶数である場合、Ｑ−Ｐを返し、それ以外の場合、Ｑ−Ｐ２を返す。
【０３９３】
先に述べたように、ＳＰＡ耐性方法を研究する際、スカラは、ρを点Ｐの位数として、
【０３９４】
【数１６９】
2009500676.tif 000171
【０３９５】
ビットの整数と見なされ、すなわち、図７の方法７００では、
【０３９６】
【数１７０】
2009500676.tif 000172
【０３９７】
である。この場合、
【０３９８】
【数１７１】
2009500676.tif 000173
【０３９９】
がｗで整除可能ならば、図１１の方法１１００で使用されるｄの値は、図４の元のコーム法４００でのｄよりも１大きく、より高い計算の複雑さもたらす。次のＳＰＡ耐性方法１２００は、ｄを増加させず、したがって、増加する計算の複雑さを排除する。
【０４００】
図１２は、ｗで整除可能な
【０４０１】
【数１７２】
2009500676.tif 000174
【０４０２】
のためのＳＰＡ耐性符号付き奇数限定コーム法１２００の演算を示している。ブロック１２０２において、位数ρの点Ｐおよびｎビット整数ｋ＞０を含む入力が受け取られる。事前計算ステージは、ブロック１２０４〜１２１２を含む。ブロック１２０４において、事前計算の計算が行われる。例えば、［ｂｗ−１，．．．，ｂ２，ｂ１，１］Ｐが、すべての（ｂｗ−１，．．．，ｂ２，ｂ１）∈（Ｚ２）ｗ−１について計算される。ブロック１２０６において、
【０４０３】
【数１７３】
2009500676.tif 000175
【０４０４】
である場合、ｋ＊＝ρ−ｋと設定し、それ以外の場合、ｋ＊＝ｋと設定する。ブロック１２０８において、ｋ＊が偶数である場合、ｋ’＝ｋ＊＋１と設定し、それ以外の場合、ｋ’＝ｋ＊＋２と設定する。ブロック１２１０において、方法７００が、ｋ’に適用されて、対応するコームビットカラム
【０４０５】
【数１７４】
2009500676.tif 000176
【０４０６】
を計算する。ブロック１２１２において、点Ｑは、最初に、無限遠点に設定され、すなわち、
【０４０７】
【数１７５】
2009500676.tif 000177
【０４０８】
と設定される。評価ステージは、ブロック１２１４〜１２２６を含む。ブロック１２１４において、ｉをインデックスとするｆｏｒループなどのループに入る。ループは、ｉ＝ｄ−１から０まで−１を増分としてカウントダウンする。ループ内では、ブロック１２１６において、Ｑ＝２Ｑと設定し、ブロック１２１８において、
【０４０９】
【数１７６】
2009500676.tif 000178
【０４１０】
ならば、
【０４１１】
【数１７７】
2009500676.tif 000179
【０４１２】
と設定し、それ以外の場合、
【０４１３】
【数１７８】
2009500676.tif 000180
【０４１４】
と設定する。ブロック１２２０において、Ｐ２＝２Ｐと設定する。ブロック１２２２において、
【０４１５】
【数１７９】
2009500676.tif 000181
【０４１６】
ならば、Δ＝１と設定し、それ以外の場合、Δ＝−１と設定する。ブロック１２２４において、ｋ＊が偶数である場合、Ｑ＝Ｑ＋ΔＰと設定し、それ以外の場合、Ｑ＝Ｑ＋ΔＰ２と設定する。ブロック１２２６において、Ｑ＝ｋＰである出力として、Ｑが返される。
【０４１７】
図１２の方法１２００では、ブロック１２０６が、
【０４１８】
【数１８０】
2009500676.tif 000182
【０４１９】
以下のｋ＊を保証することに留意されたい。また、方法で使用されるｄが
【０４２０】
【数１８１】
2009500676.tif 000183
【０４２１】
に等しいことを保証するため、ｋ’は
【０４２２】
【数１８２】
2009500676.tif 000184
【０４２３】
ビットの整数であるべきである。そうでない場合、所望の結果を達成するため、ブロック１２０６において、ｋ＊が偶数ならば、ｋ’をｋ＊−１と設定し、ｋ＊が奇数ならば、ｋ＊−２と設定することができる。この場合、ブロック１２２２は、
【０４２４】
【数１８３】
2009500676.tif 000185
【０４２５】
ならば、Δを−１と設定し、それ以外の場合、１と設定する。
【０４２６】
［演算の安全性］
電力解析に対する開示された点乗算方法の安全性が、このセクションで説明される。ＳＰＡに対する安全性が、最初に検討され、続いて、開示された方法をどのように変換して、ＤＰＡ、２次ＤＰＡ（ｓｅｃｏｎｄ−ｏｒｄｅｒ  ＤＰＡ）、およびその他のサイドチャネル攻撃に耐性をもつようにするかが説明される。
【０４２７】
コーム法９００、１１００、１２００は、電力解析にとって点減算が点加算と実質的に同じであるという事実を利用する。加えて、開示されるコーム法は、点乗算を計算する各ループにおいて、１つの点加算（または点減算）および１つの２倍算を実行する。これは、すべてのスカラｋについて同じ系列が実行されることを意味する。したがって、ＳＰＡは、実行の電力消費を検査することによって、秘密ｋについてのどのような情報も抽出することができない。言い換えると、コーム法９００、１１００、１２００は、実際にＳＰＡ耐性である。
【０４２８】
しかし、ＳＰＡ耐性である点乗算方法が、必ずしもＤＰＡ攻撃に対して耐性があるとは限らない。ランダム化射影座標（ｒａｎｄｏｍｉｚａｔｉｏｎ  ｐｒｏｊｅｃｔｉｖｅ  ｃｏｏｒｄｉｎａｔｅ）またはランダム同型曲線（ｒａｎｄｏｍ  ｉｓｏｍｏｒｐｈｉｃ  ｃｕｒｖｅ）が、開示された方法をＤＰＡ耐性方法に変換するために使用することができる。
【０４２９】
すぐ上で述べられたランダム化方式が使用される場合、２次ＤＰＡ攻撃は、依然として、コーム法９００、１１００、１２００に有効に適用されることができる。そのような２次攻撃は、どの
【０４３０】
【数１８４】
2009500676.tif 000186
【０４３１】
がロードされたかを決定するために、電力消費とロードデータのハミング重みの相関を利用する。そのような２次ＤＰＡ攻撃を妨げるため、固定ハミング重みが存在しないように、すべての事前計算点をテーブルに入れた後でランダム化する方式を使用することができる。
【０４３２】
最近提案されたＤＰＡ攻撃は、多くのランダム化方式に対する改良された攻撃である。この攻撃は、座標成分の一方がゼロである特別な点を利用する。そのようなＤＰＡ攻撃は、開示されたスカラ乗算方法の応用例において、Ｆｐ（ｐ＞３）上で定義され、ｂがｐを法とする平方剰余（ｑｕａｄｒａｔｉｃ  ｒｅｓｉｄｕｅ）ではない楕円曲線Ｅ：ｙ２＝ｘ３＋ａｘ＋ｂを単に選択し、入力点として任意の点（ｘ，０）を拒否することによって、対処することができる。濃度＃Ｅ（Ｆｐ）が大きな素数である場合、点（ｘ，０）は、楕円曲線上にないので、適格な入力点になることができない。上述のランダム化技法および対策と組み合わせることで、開示されたコーム法は、電力解析攻撃を妨げることができる。
【０４３３】
［演算の効率性］
コーム法８００〜１２００は、２ｗ−１個の点を必要とする。これらのコーム法の事前計算ステージでは、２ｄＰ、２２ｄＰ、．．．、２（ｗ−１）ｄＰが、最初に計算される。これは、（ｗ−１）ｄ回の点２倍算のコストがかかる。その後、（ｂｗ−１，．．．，ｂ２，ｂ１）∈（Ｚ２）ｗ−１であるすべての可能な組合せ［ｂｗ−１，．．．，ｂ２，ｂ１，１］Ｐが、図４の方法４００の事前計算ステージと同様にして計算され、これは、２ｗ−１−１回の点加算のコストがかかる。事前計算ステージにおける開示されたコーム法の総コストは、したがって、｛（ｗ−１）ｄ｝Ｄ＋｛２ｗ−１−１｝Ａである。評価ステージにおける開示されたコーム法の時間コストは、ｆｏｒループ後の後処理のために少し異なる。スカラｋがランダムに分布していると仮定すると、評価ステージにおける平均コストは、図８の方法８００の場合、
【０４３４】
【数１８５】
2009500676.tif 000187
【０４３５】
、図９の方法９００の場合、（ｄ−１）Ｄ＋（ｄ−１）Ａ、図１０の方法１０００の場合、
【０４３６】
【数１８６】
2009500676.tif 000188
【０４３７】
、図１１の方法１１００および図１２の方法１２００の場合、ｄＤ＋ｄＡである。
【０４３８】
図８〜図１０の固定基底コーム法８００、９００、１０００と図４の元の固定基底コーム法４００との比較を行うことができる。表１は、これらの方法の空間および時間コストを一覧で示している。表１のコーム法８００〜１０００は、２ｗ−１を記憶し、これは、元のコーム法４００における２ｗ−１個の記憶点の約半数である。加えて、コーム法８００〜１０００は、事前計算ステージにおいて、図４の元のコーム法４００と比べて２ｗ−１−ｗ回の点加算を節約する。評価ステージは、表１の４つの方法すべてについて、類似した時間コストを有する。事前計算点のための記憶空間をほぼ同じに維持するため、方法８００〜１０００は、コーム法４００で使用される値ｗ＝ｗ１よりも１大きい、ｗ＝ｗ１＋１としてｗの値が選択されるような方法で利用されることができる。これは、コーム法４００と類似した記憶
【０４３９】
【数１８７】
2009500676.tif 000189
【０４４０】
をもたらすが、評価ステージでは、方法８００〜１０００で使用されるより小さなｄのおかげでより高速になる。
【０４４１】
図９、図１１、図１２の開示されたＳＰＡ耐性コーム法９００、１１００、１２００とＳＰＡ耐性である方法４００の修正との比較を行うことができる。これらのＳＰＡ耐性方法の空間および時間コストが、表２に一覧で示されている。やはり、ＳＰＡ耐性コーム法９００、１１００、１２００は、事前計算点のために修正コーム法４００の約半数の記憶を使用し、さらに事前計算ステージにおいて、２ｗ−１−ｗ回の点加算を節約する。方法１１００および１２００は、評価ステージにおいて、修正方法４００と同じ時間コストを有するが、開示された方法９００は、このステージにおいて、１回の点２倍算と１回の点加算を節約する。表２のデータから、ｎがｗで整除可能でない場合、方法９００が最も効率的なＳＰＡ耐性コーム法である。ｎがｗで整除可能である場合、この場合は
【０４４２】
【数１８８】
2009500676.tif 000190
【０４４３】
は
【０４４４】
【数１８９】
2009500676.tif 000191
【０４４５】
より１大きく、より高い時間コストをもたらすので、方法１２００が推奨される。
【０４４６】
【表１】
2009500676.tif 000192
【０４４７】
本明細書で開示されたＳＰＡ耐性実施形態とその他のＳＰＡ耐性点乗算方法の比較は有益である。２つのＳＰＡ耐性ｍ進スカラ乗算方法（一方はＳＰＡ耐性である拡張ｍ進方法、他方は図６の記録方法６００を使用するｍ進方法）に関する空間および時間コストが、表３の第２および第３列に一覧で示されている。表２および表３から、図９、図１１、図１２の開示されたＳＰＡ耐性コーム法９００、１１００、１２００は、記録方法６００を使用するｍ進方法と同数の事前計算点を記憶し、それは、その他のＳＰＡ耐性ｍ進方法より１点少ない。
【０４４８】
点乗算方法にＳＰＡ攻撃に対する耐性をもたせるため、ｋの特定の値に対する暗号実行手続きの依存性を除去する追加の演算が必要とされる。これは、ＳＰＡ耐性方法の効率が、類似手法の非ＳＰＡ耐性方法と比べて、一般に低下させられることを意味する。最も効率的な点乗算方法は、事前計算および評価ステージの両方を一括した総コストが検討された場合、非ＳＰＡ耐性の符号付きｍ進窓法である。符号付きｍ進窓法コストの空間および時間コストは、表３の第１列に一覧で示されている。この方法は、よりわずかな保存点しか必要としないが、すべてのＳＰＡ耐性方法よりも高速に動作する。空間および時間ペナルティは、セキュリティが最優先課題である多くの応用例ではあまり重要ではない。評価ステージのみが検討された場合、開示されたコーム法は、符号付きｍ進窓法よりも高速である。
【０４４９】
【表２】
2009500676.tif 000193
【０４５０】
【表３】
2009500676.tif 000194
【０４５１】
［応用例］
方法８００〜１２００は、多くのＥＣＣ応用例で使用することができる。それらは、事前計算が前もってまたは別の誰かによって計算され得る場合に特に効率的であり、多くの応用例でそのようにされている。このセクションは、２つのそのような応用シナリオについて説明する。１つの例は、別個のより強力なコンピューティングサブシステムが、その他の動作を担当する一方で、スマートカードが、秘密を記憶し、重要な暗号演算を実行するための、タンパー耐性（ｔａｍｐｅｒ−ｒｅｓｉｓｔａｎｔ）のある安全な環境を提供するために使用されるシステムである。セルラ電話および無線アプリケーションプロトコル（ＷＡＰ：ｗｉｒｅｌｅｓｓ  ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｔｏｃｏｌ）装置は、そのようなシステムの典型的な例である。セルラ電話では、加入者識別モジュール（ＳＩＭ：Ｓｕｂｓｃｒｉｂｅｒ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  Ｍｏｄｕｌｅ）カードが、重要な加入者情報と、無線ネットワークへの合法的アクセスを提供する責任を負う認証および暗号化方法とを、安全に記憶するためのスマートカードである。電話のＣＰＵ、メモリ、および記憶装置は、その他の動作を担当する。無線識別情報モジュール（ＷＩＭ：Ｗｉｒｅｌｅｓｓ  Ｉｄｅｎｔｉｔｙ  Ｍｏｄｕｌｅ）は、ＷＡＰ装置内で同様の役割を演じる。そのようなシステムでは、評価ステージを実行するのにスマートカードを使用する一方で、事前計算をより強力な装置のＣＰＵに委任することが、装置のＣＰＵによって計算される点が識別可能であってもタンパー可能でない場合は、可能であってよい。事前計算は、点自体が秘密でない限り、どのような秘密も含まないことに留意されたい。
【０４５２】
楕円曲線デジタル署名アルゴリズム（ＥＣＤＳＡ：Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ）が、別の例である。ＥＣＤＳＡは、デジタル署名規格と呼ばれる米国政府規格で指定されたデジタル署名アルゴリズム（ＤＳＡ：Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ）の楕円曲線による類似物である。ＥＣＤＳＡは、多くの規格で受け入れられている。ＥＣＤＳＡは、署名生成および検証を含む。Ｐを公知の楕円曲線点、ρを点Ｐの素数位数とする。署名は、以下のようにして生成および検証される。ＥＣＤＳＡ署名生成：メッセージｍに署名するため、鍵ペア（ｄ，Ｑ）に関連付けられた主体Ａは、以下のステップを実行する。
【０４５３】
１．１≦ｋ＜ρであるようなランダムまたは擬似ランダムな整数ｋを選択する。
【０４５４】
２．ｋＰ＝（ｘ１，ｙ１）およびｒ＝ｘ１  ｍｏｄ  ρを計算する。ｒ＝０ならば、ステップ１に戻る。
【０４５５】
３．ｋ−１  ｍｏｄ  ρを計算する。
【０４５６】
４．ｅ＝ＳＨＡ−１（ｍ）を計算し、ここで、ＳＨＡ−１は、セキュアハッシュ規格で指定されたセキュアハッシュアルゴリズム（ＳＨＡ：Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ）である。
【０４５７】
５．ｓ＝ｋ−１（ｅ＋ｄｒ）ｍｏｄ  ρを計算する。ｓ＝０ならば、ステップ１に戻る。
【０４５８】
６．メッセージｍに関してＡによって生成された署名は、（ｒ，ｓ）である。
【０４５９】
ＥＣＤＳＡ署名検証：メッセージｍ上のＡの署名（ｒ，ｓ）を検証するため、主体Ｂは、Ａの公開鍵Ｑを獲得し、以下のステップを実行する。
【０４６０】
１．ｒおよびｓが区間［１，ρ−１］内の整数であることを確認する。
【０４６１】
２．ｅ＝ＳＨＡ−１（ｍ）を計算する。
【０４６２】
３．ｗ＝ｓ−１  ｍｏｄ  ρを計算する。
【０４６３】
４．ｕ１＝ｅｗ  ｍｏｄ  ρおよびｕ２＝ｒｗ  ｍｏｄ  ρを計算する。
【０４６４】
５．Ｘ＝ｕ１Ｐ＋ｕ２Ｑ＝（ｘ１，ｙ１）を計算する。Ｘ＝０ならば、署名を拒否する。それ以外の場合、ｖ＝ｘ１  ｍｏｄ  ρを計算する。
【０４６５】
６．ｖ＝ｒである場合に限って、署名を承認する。
【０４６６】
ＥＣＤＳＡ署名の場合、Ｐ、ρ、およびｒ、ｓ、ｅは、公開された値である。スカラｋは、秘密に保たれなければならない。さもないと、私有鍵ｄを式ｓ＝ｋ−１（ｅ＋ｄｒ）ｍｏｄ  ρから導くことができる。したがって、私有鍵ｄおよびＥＣＤＳＡ署名生成は、安全に記憶され、実行されなければならない。これは、Ｐの事前計算点を記憶し、電力解析に対して耐性がある点乗算方法を使用してｋＰを計算する、スマートカードを用いて簡便に達成することができる。本明細書で開示されたＳＰＡ耐性コーム法は、署名を生成する際に評価ステージが実行されるだけなので、この応用例にとって理想的である。他方、ＥＣＤＳＡ署名検証は、どのような秘密鍵も使用しない。ＥＣＤＳＡ署名を検証する際、本明細書で開示された非ＳＰＡ耐性コーム法を、ｕ１Ｐを計算するために使用することができ、符号付きｍ進窓法が、ｕ２Ｑを計算するために使用される。これは、Ｐの事前計算点を前もって計算することができるので、点乗算方法の効率的な組合せであり、この場合、コーム法はその他の方法よりも効率的である。対照的に、公開鍵Ｑが主体毎に変化するので、Ｑの事前計算点を前もって計算することができない。この場合、符号付きｍ進窓法が適している。
【０４６７】
［例示的な方法］
図１３は、楕円曲線暗号システムの楕円曲線点乗算における使用のために適合され得る、記録システムの動作を示す一実施例１３００を示している。実施１３００は、スマートカード、セルラ電話、ワークステーション、またはメインフレームコンピューティング環境など、多くの異なるコンピューティング環境における使用のために構成される。ブロック１３０２において、奇整数ｋが、２進表現に変換される。２進表現は、例えば、２のベキの係数とすることができる。ブロック１３０２の変換は、ブロック１３０４〜１３０８で説明される例示的な変換など、多くの方法で実行されることができる。ブロック１３０４において、奇整数ｋの２進表現の最低位ｄビットの各ビットが変換される。変換は、各ビットカラム内の最低位ビットが１または
【０４６８】
【数１９０】
2009500676.tif 000195
【０４６９】
になるような方法で実行される。この変換は、図７のブロック７０４〜７０８で開示された方式で実行されることもできることに留意されたい。ブロック１３０６において、ｄより大きい有効桁にある２進表現のビットが、第ｉ位置にある結果ビットが０または符号付き１になるように変換され、符号付き１は、第（ｉ  ｍｏｄ  ｄ）位置にあるビットに従って符号が定められる。ブロック１３０６の変換は、図７のブロック７１２〜７１８またはブロック１３０８に示されるような様々な異なる方式で実行することができる。ブロック１３０８において、現在ビットの符号が、同じコームビットカラム内の最低位ビットの符号と比較される。符号が異なり、かつ現在ビットが１である場合、現在ビットは
【０４７０】
【数１９１】
2009500676.tif 000196
【０４７１】
に設定され、ｋの値を維持するために、隣接するより高位のビットの値が１だけインクリメントされる。ブロック１３１０において、２進表現が、どのビットカラムも符号付き奇整数であるコームビットカラムとして構成される。より具体的には、実施１３００は、各コームビットカラム
【０４７２】
【数１９２】
2009500676.tif 000197
【０４７３】
について、
【０４７４】
【数１９３】
2009500676.tif 000198
【０４７５】
および
【０４７６】
【数１９４】
2009500676.tif 000199
【０４７７】
、ｊ≠０を生成することができ、ここで、
【０４７８】
【数１９５】
2009500676.tif 000200
【０４７９】
は−１と定義される。
【０４８０】
図１４は、楕円曲線点乗算システムの動作１４００の一例を示している。ブロック１４０２において、点Ｐおよび整数ｋが受け取られ、ここで、ｋは偶整数または奇整数である。ブロック１４０４において、少なくとも部分的にｋの値に基づいて、ｋ’が設定され、ここで、ｋ’は奇整数である。例えば、図８のブロック８０６において、ｋの偶数または奇数の状態に基づいて、ｋ’が設定される。ブロック１４０６において、奇整数ｋ’が、どのビットカラムも符号付き奇整数である、ビットカラムを含む２進表現に変換される。例えば、これは、図７の方法７００に従って実行することができる。したがって、動作１４０６は、各コームビットカラム
【０４８１】
【数１９６】
2009500676.tif 000201
【０４８２】
について、
【０４８３】
【数１９７】
2009500676.tif 000202
【０４８４】
および
【０４８５】
【数１９８】
2009500676.tif 000203
【０４８６】
、ｊ≠０を生成することができ、ここで、
【０４８７】
【数１９９】
2009500676.tif 000204
【０４８８】
は−１と定義することができる。ブロック１４０８において、コームビットカラムおよび点Ｐが、値Ｑを計算するために処理され、ここで、Ｑは、ｋの異なる値に対して異なるように設定することができる。例えば、ブロック８１８、９１６、１０１８、１０２２〜１０２４、１１２０、１２２２〜１２２４はすべて、部分的にｋに基づいてＱを設定する。ブロック１４１０において、Ｑが出力され、ここで、ＱはｋＰを表す。
【０４８９】
本明細書で説明される方法はどれも、スマートカード、コンピュータシステム、または任意のデジタル処理装置および／もしくはコンポーネント上で実行することができる。例えば、方法は、プロセッサおよび／またはコンピュータ可読媒体上に定義された命令の実行によって実行されることができる。本明細書で使用される「プロセッサ可読媒体」とは、スマートカード上、コンピュータ上、または任意のコンピューティングもしくは計算装置および／もしくはコンポーネント上のいずれにおいてであれ、プロセッサによって使用または実行される命令を格納または保存することができる任意の手段とすることができる。プロセッサ可読媒体は、限定することなく、電子、磁気、光、電磁気、赤外線、または半導体システム、機器、装置、またはコンポーネントとすることができる。プロセッサ可読媒体のより具体的な例は、とりわけ、スマートカード上のメモリコンポーネント、ポータブルコンピュータディスケット、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能なプログラム可能読み取り専用メモリ（ＥＰＲＯＭまたはフラッシュメモリ）、光および／または磁気メモリ、再書き込み可能コンパクトディスク（ＣＤＲＷ）、ならびにポータブルコンパクトディスク読み取り専用メモリ（ＣＤＲＯＭ）を含む。
【０４９０】
１つまたは複数の方法が、フローチャートおよびフローチャートのブロックに関連する文によって開示されたが、ブロックはそれらが提示された順序で必ずしも実行される必要がなく、代替順序でも類似の利点をもたらすことができることを理解されたい。さらに、方法は排他的ではなく、単独または互いに組み合わされて実行されることができる。
【０４９１】
［例示的なコンピューティング環境］
図１５は、楕円曲線暗号システムを実施するのに適した例示的なコンピューティング環境を示している。１つの具体的な構成が示されているが、特定の応用例の必要を満たすために、任意のコンピューティング環境を代用することができる。コンピューティング環境１５００は、コンピュータ１５０２の形態をとる汎用コンピューティングシステムを含む。コンピュータ１５０２の構成要素は、１つまたは複数のプロセッサまたは処理ユニット１５０４と、システムメモリ１５０６と、プロセッサ１５０４を含む様々なシステム構成要素をシステムメモリ１５０６に結合するシステムバス１５０８とを含むが、これらに限定されない。システムバス１５０８は、メモリバスもしくはメモリコントローラ、周辺バス、周辺機器相互接続（ＰＣＩ）バス、アクセラレーテッドグラフィックスポート、および様々なバスアーキテクチャのいずれかを使用するプロセッサもしくはローカルバスを含む、複数のタイプのバス構造のうちの１つまたは複数を表す。
【０４９２】
コンピュータ１５０２は、典型的には、様々なコンピュータ可読媒体を含む。そのような媒体は、コンピュータ１５０２によってアクセス可能な任意の利用可能な媒体とすることができ、揮発性および不揮発性、着脱可能および固定式の媒体を含む。システムメモリ１５０６は、ランダムアクセスメモリ（ＲＡＭ）１５１０などの揮発性メモリおよび／または読み取り専用メモリ（ＲＯＭ）１５１２などの不揮発性メモリの形態をとるコンピュータ可読媒体を含む。基本入出力システム（ＢＩＯＳ）１５１４は、起動中などにコンピュータ１５０２内の要素間での情報伝送を助ける基本ルーチンを含み、ＲＯＭ１５１２内に保存される。ＲＡＭ１５１０は、典型的には、処理ユニット１５０４から即座にアクセス可能な、および／または処理ユニット１５０４が現在それに基づいて動作している、データおよび／またはプログラムモジュールを含む。
【０４９３】
コンピュータ１５０２は、その他の着脱可能／固定式、揮発性／不揮発性コンピュータ記憶媒体も含むことができる。例を挙げると、図１５は、固定式の不揮発性磁気媒体（図示されず）から読み取り、それに書き込むためのハードディスクドライブ１５１６と、着脱可能な不揮発性磁気ディスク１５２０（例えば「フロッピー（登録商標）ディスク」）から読み取り、それに書き込むための磁気ディスクドライブ１５１８と、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、またはその他の光媒体などの着脱可能な不揮発性光ディスク１５２４から読み取り、それに書き込むための光ディスクドライブ１５２２を示している。ハードディスクドライブ１５１６、磁気ディスクドライブ１５１８、および光ディスクドライブ１５２２は各々、１つまたは複数のデータ媒体インターフェース１５２５によって、システムバス１５０８に接続される。代替として、ハードディスクドライブ１５１６、磁気ディスクドライブ１５１８、および光ディスクドライブ１５２２は、ＳＣＳＩインターフェース（図示されず）によって、システムバス１５０８に接続することもできる。
【０４９４】
ディスクドライブおよび関連するコンピュータ可読媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータの不揮発性記憶を、コンピュータ１５０２に提供する。例はハードディスク１５１６、着脱可能な磁気ディスク１５１８、および着脱可能な光ディスク１５２４を示しているが、磁気カセット、またはその他の磁気記憶装置、フラッシュメモリカード、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、またはその他の光記憶、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、および電気的消去可能なプログラム可能読み取り専用メモリ（ＥＥＰＲＯＭ）など、コンピュータによってアクセス可能なデータを記憶することができるその他のタイプのコンピュータ可読媒体も、例示的なコンピューティングシステムおよび環境を実施するために利用され得ることを理解されたい。
【０４９５】
例を挙げると、オペレーティングシステム１５２６、１つまたは複数のアプリケーションプログラム１５２８、その他のプログラムモジュール１５３０、およびプログラムデータ１５３２を含む任意の数のプログラムモジュールが、ハードディスク１５１６、磁気ディスク１５２０、光ディスク１５２４、ＲＯＭ１５１２、および／またはＲＡＭ１５１０上に保存されることができる。そのようなオペレーティングシステム１５２６、１つまたは複数のアプリケーションプログラム１５２８、その他のプログラムモジュール１５３０、およびプログラムデータ１５３２の各々（またはそれらの何らかの組合せ）は、ユーザネットワークアクセス情報のためのキャッシュ方式の一実施形態を含むこともできる。
【０４９６】
コンピュータ１５０２は、通信媒体として識別される様々なコンピュータ／プロセッサ可読媒体を含むことができる。通信媒体は、典型的には、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータを、搬送波またはその他のトランスポート機構などの変調データ信号中に具現し、任意の情報伝達媒体を含む。「変調データ信号」という用語は、信号中に情報を符号化するような方式で設定または変更された１つまたは複数の特徴を有する信号を意味する。限定することなく例を挙げると、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体、ならびに音響、ＲＦ、赤外線、およびその他の無線媒体などの無線媒体を含む。上記の任意のものの組合せも、コンピュータ可読媒体の範囲内に含まれる。
【０４９７】
ユーザは、キーボード１５３４およびポインティングデバイス１５３６（例えば「マウス」）などの入力装置を介して、コンピュータシステム１５０２にコマンドおよび情報を入力することができる。その他の入力および／または周辺装置１５３８（具体的に図示されず）は、スマートカードおよび／もしくはスマートカードリーダ、マイクロフォン、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、シリアルポート、ならびに／またはスキャナを含むことができる。上記およびその他の入力装置は、システムバス１５０８に結合される入力／出力装置インターフェース１５４０を介して処理ユニット１５０４に接続されるが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）などのその他のインターフェースおよびバス構造によって接続されることもできる。
【０４９８】
モニタ１５４２またはその他のタイプの表示装置も、ビデオアダプタ１５４４などのインターフェースを介して、システムバス１５０８に接続される。モニタ１５４２に加えて、その他の出力周辺装置は、入力／出力装置インターフェース１５４０を介してコンピュータ１５０２に接続されることができる、スピーカ（図示されず）およびプリンタ１５４６など構成要素を含むことができる。
【０４９９】
コンピュータ１５０２は、リモートコンピューティング装置１５４８などの１つまたは複数のリモートコンピュータへの論理コネクションを使用して、ネットワーク環境で動作することができる。例を挙げると、リモートコンピューティング装置１５４８は、パーソナルコンピュータ、ポータブルコンピュータ、サーバ、ルータ、ネットワークコンピュータ、およびピア装置またはその他の共通ネットワークノードなどとすることができる。リモートコンピューティング装置１５４８は、コンピュータシステム１５０２に関して説明された要素および特徴の多くまたはすべてを含むことができるポータブルコンピュータとして示されている。
【０５００】
コンピュータ１５０２とリモートコンピュータ１５４８の間の論理コネクションは、ローカルエリアネットワーク（ＬＡＮ）１５５０および汎用ワイドエリアネットワーク（ＷＡＮ）１５５２として示されている。そのようなネットワーク環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、およびインターネットにおいて一般的である。ＬＡＮネットワーク環境で実施される場合、コンピュータ１５０２は、ネットワークインターフェースまたはアダプタ１５５４を介して、ローカルネットワーク１５５０に接続される。ＷＡＮネットワーク環境で実施される場合、コンピュータ１５０２は、典型的には、モデム１５５６またはＷＡＮ１５５２を介する通信を確立するためのその他の手段を含む。モデム１５５６は、コンピュータ１５０２に対して内蔵または外付けとすることができ、入力／出力装置インターフェース１５４０またはその他の適切な機構を介してシステムバス１５０８に接続される。示されたネットワーク接続は、例示的なものであり、コンピュータ１５０２および１５４８間の通信リンクを確立するその他の手段も利用されることができることを理解されたい。
【０５０１】
コンピューティング環境１５００を用いて説明されたようなネットワーク環境では、コンピュータ１５０２またはその部分に関して説明されたプログラムモジュールは、リモートメモリ記憶装置に保存されることができる。例を挙げると、リモートアプリケーションプログラム１５５８は、リモートコンピュータ１５４８のメモリ装置上に存在する。説明の目的で、アプリケーションプログラム、およびオペレーティングシステムなどのその他の実行可能プログラムコンポーネントは、本明細書では別個のブロックとして示されているが、そのようなプログラムおよびコンポーネントは、様々な時にコンピュータシステム１５０２の異なる記憶コンポーネント内に存在し、コンピュータのデータプロセッサによって実行されることは理解されよう。
【０５０２】
内部スマートカード１５６２を有するセルラ電話１５６０は、コーム法８００〜１４００が利用され得るさらなる環境を提供する。セルラ電話は、コンピュータ１５０２と通信するように構成され、コンピュータ１５０２は、セルラ電話通信事業者またはサービスに関連付けられることができる。そのような環境では、ＥＣＣ方法は、例えば、この場合はコンピュータ１５０２を運用するセルラサービスプロバイダの合法的顧客としての、セル電話１５６０の真正性を確立するために使用することができる。
【０５０３】
［結び］
図７の新規な符号付き奇数限定コーム記録方法７００は、奇整数のコームの系列のコームビットカラムを、符号付き奇数限定非ゼロ表現に変換する。この記録方法を使用して、図８〜図１２の複数の新規な非ＳＰＡ耐性およびＳＰＡ耐性のコーム法８００〜１２００が、楕円曲線暗号システムのための点乗算を計算するように構成される。開示されたコーム法は、既知の非ＳＰＡ耐性およびＳＰＡ耐性のコーム法と比べて、より少量の点しか記憶せず、より高速に動作する。加えて、開示された符号付き奇数限定コーム法は、コーム法の利点を継承し、事前計算点が前もってまたはどこかで計算される場合、窓法および非ＳＰＡ耐性符号付きｍ進窓法よりもはるかに高速に動作する。したがって、図８〜図１２の符号付き奇数限定コーム法８００〜１２００は、電力およびコンピューティング資源が貴重であるスマートカードおよび埋め込みシステムでの使用によく適している。楕円曲線およびパラメータを選択する際に、ランダム化技法および所定の事前対策と組み合わされた場合、ＳＰＡ耐性のコーム法は、すべてのサイドチャネル攻撃を妨げることができる。
【０５０４】
最後に、本開示の態様は、好ましい実施形態の構造的および／または方法的特徴を具体的に説明する言葉を含むが、添付の特許請求の範囲が、説明された具体的な特徴および動作に限定されないことを理解されたい。むしろ、具体的な特徴および動作は、例示的な実施としてのみ開示され、より一般的な概念の代表である。さらに、多くの特徴は、これらの特徴が対処し得る例示的な問題を最初に識別することによって、本明細書では説明された。こうした説明の方法は、他人が本明細書で指定された方法で問題を認識および／または表現していたことの承認を構成しない。当技術分野に存在する問題の認識および表現は、本発明の一部として理解されるべきである。より具体的には、本開示の「背景技術」セクションで説明された特徴が従来技術を構成することの承認は本明細書には存在しない。さらに、本開示の「課題を解決するための手段」セクションおよび要約書で説明された主題は、特許請求の範囲で説明される主題を限定しない。
【図面の簡単な説明】
【０５０５】
【図１】例示的な既存の楕円曲線点乗算方法を示す図である。
【図２】例示的な既存の楕円曲線点乗算方法を示す図である。
【図３】例示的な既存の楕円曲線点乗算方法を示す図である。
【図４】例示的な既存の楕円曲線点乗算方法を示す図である。
【図５】単純電力解析に対して耐性のある例示的な既存の楕円曲線点乗算方法または対応する記録方法示す図である。
【図６】単純電力解析に対して耐性のある例示的な既存の楕円曲線点乗算方法または対応する記録方法示す図である。
【図７】奇数スカラのための符号付き奇数限定コーム記録方法の一例を示す図である。
【図８】奇数または偶数スカラのための符号付き奇数限定コーム楕円曲線点乗算方法の一例を示す図である。
【図９】奇数位数の点のための符号付き奇数限定コーム楕円曲線点乗算方法の一例を示す図である。
【図１０】ｗで整除可能なｎのための符号付き奇数限定コーム楕円曲線点乗算方法の一例を示す図である。
【図１１】ＳＰＡ耐性をもつ符号付き奇数限定コーム楕円曲線点乗算方法の一例を示す図である。
【図１２】ｗで整除可能な
【０５０６】
【数２００】
2009500676.tif 000205
【０５０７】
のためのＳＰＡ耐性をもつ符号付き奇数限定コーム楕円曲線点乗算方法の一例を示す図である。
【図１３】汎用的利用を有する、またはコーム楕円曲線点乗算用もしくは暗号システム内で利用され得る記録の一実施形態例を示す図である。
【図１４】コーム楕円曲線点乗算システムの動作の一実施形態例を示す図である。
【図１５】コーム楕円曲線点乗算方法を実施するのに適した例示的なコンピューティング環境を示す図である。
【図１】
2009500676.tif 000232
【図２】
2009500676.tif 000233
【図３】
2009500676.tif 000234
【図４】
2009500676.tif 000235
【図５】
2009500676.tif 000236
【図６】
2009500676.tif 000237
【図７】
2009500676.tif 000238
【図８】
2009500676.tif 000239
【図９】
2009500676.tif 000240
【図１０】
2009500676.tif 000241
【図１１】
2009500676.tif 000242
【図１２】
2009500676.tif 000243
【図１３】
2009500676.tif 000244
【図１４】
2009500676.tif 000245
【図１５】
2009500676.tif 000246