(57)【特許請求の範囲】
【請求項１】
楕円曲線暗号システムにおいて、繰り返される点加算及び点２倍算により楕円曲線上の点のスカラー倍を右から左に計算する暗号化方法であって、
マイクロプロセッサによって、それぞれの点２倍算を、射影座標T1，T2，T3と少なくとも１つの更なる座標T4とを含む座標のセットを入力とすることで評価するステップと、
前記マイクロプロセッサによって、それぞれの点加算を、前記射影座標T1，T2，T3を入力とすることで評価するステップと、
前記マイクロプロセッサによって、次の点２倍算において使用するため、前記少なくとも１つの更なる座標T4をメモリに記憶するステップと
を含み、
点２倍算の出力座標は、次の点２倍算のための入力座標として使用され、
前記点２倍算は、
前記射影座標T1，T2，T3の値と、前記楕円曲線の第一パラメータをaとしてT4=aT34に初期化される前記更なる座標T4の値とを取得し、
中間変数
U=T12；
V=T22;
M=3U+T4;
W=V2;及び
S=2((T1+V)2-U-W)；
を計算し、
T3及びT4の新しい値
T3=2T2T3；
T4=16WT4
を計算し、
T1の新しい値
T1=M2-2S
を計算し、
T2の新しい値
T2=M(S-T1)-8W
を計算し、
少なくとも座標T1，T2，T3の値を出力する
ことで計算される、方法。
【請求項２】
前記楕円曲線は、２及び３とは異なる特性によるWeierstrass式
EIK：Y2＝X3＋aXZ4＋bZ6
により与えられ、bは、前記楕円曲線の第二のパラメータである、
請求項１記載の方法。
【請求項３】
前記スカラー倍は、非隣接形式（Non  Adjacent  Form）におけるスカラーを使用して計算される、
請求項１記載の方法。
【請求項４】
前記スカラー倍は、バイナリ表現におけるスカラーを使用して計算される、
請求項１記載の方法。
【請求項５】
前記点２倍算は、モディファイドヤコビアン座標を使用して実行され、前記点加算は、ヤコビアン座標を使用して実行される、
請求項１記載の方法。
【請求項６】
楕円曲線暗号システムにおいて楕円曲線上の点のスカラー倍を右から左に計算する装置であって、
当該装置は、メモリと、
繰り返される点２倍算及び点加算を行い、
射影座標T1，T2，T3と少なくとも１つの更なる座標T4とを含む座標のセットを入力としてそれぞれの点２倍算を評価し、
前記射影座標T1，T2，T3の組を入力としてそれぞれの点加算を評価し、
次の点２倍算において使用するため、前記少なくとも１つの更なる座標T4を前記メモリに記憶する
よう構成されるプロセッサとを備え、
点２倍算の出力座標は、次の点２倍算のための入力座標として使用され、
前記点２倍算は、
前記射影座標T1，T2，T3の値と、前記楕円曲線の第一パラメータをaとしてT4=aT34に初期化される前記更なる座標T4の値とを取得し、
中間変数
U=T12；
V=T22;
M=3U+T4;
W=V2;及び
S=2((T1+V)2-U-W)；
を計算し、
T3及びT4の新しい値
T3=2T2T3；
T4=16WT4
を計算し、
T1の新しい値
T1=M2-2S
を計算し、
T2の新しい値
T2=M(S-T1)-8W
を計算し、
少なくとも座標T1，T2，T3の値を出力する
ことで計算される、装置。
【請求項７】
マイクロプロセッサで実行されたとき、楕円曲線暗号システムにおいて、繰り返される点加算及び点２倍算により楕円曲線上の点のスカラー倍を右から左に計算する暗号化方法を実行するコンピュータプログラムを記憶した非一時的な媒体であって、
前記方法は、
マイクロプロセッサによって、それぞれの点２倍算を、射影座標T1，T2，T3と少なくとも１つの更なる座標T4とを含む座標のセットを入力とすることで評価するステップと、
前記マイクロプロセッサによって、それぞれの点加算を、前記射影座標T1，T2，T3を入力とすることで評価するステップと、
前記マイクロプロセッサによって、次の点２倍算において使用するため、前記少なくとも１つの更なる座標T4をメモリに記憶するステップと
を含み、
点２倍算の出力座標は、次の点２倍算のための入力座標として使用され、
前記点２倍算は、
前記射影座標T1，T2，T3の値と、前記楕円曲線の第一パラメータをaとしてT4=aT34に初期化される前記更なる座標T4の値とを取得し、
中間変数
U=T12；
V=T22;
M=3U+T4;
W=V2;及び
S=2((T1+V)2-U-W)；
を計算し、
T3及びT4の新しい値
T3=2T2T3；
T4=16WT4
を計算し、
T1の新しい値
T1=M2-2S
を計算し、
T2の新しい値
T2=M(S-T1)-8W
を計算し、
少なくとも座標T1，T2，T3の値を出力する
ことで計算される、非一時的な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号作成法に関し、より詳細には、楕円曲線の暗号システムの右から左へのスカラー乗算に関する。
【背景技術】
【０００２】
この節は、以下に記載され、及び／又は特許請求される本発明の様々な態様に関連する様々な当該技術分野の態様を読者に導入することが意図される。この説明は、本発明の背景情報を読者に提供することに役立つものと考えられる。したがって、これらの説明は、この点に照らして読まれるべきであって、従来技術の認定として読まれるべきではない。
【０００３】
楕円曲線暗号（ECC）は、対応するセキュリティレベルについてRSA（Rivest  Shamir  Adleman）鍵よりも大幅に短い鍵の長さのために、ますます広がりつつある。しかし、短い鍵の長さは、暗号システムを選択するときに考慮すべき唯一の要素ではなく、たとえば、比較的長い待ち時間が暗号システムを使用するユーザをいらいらさせる場合があるので、計算時間が考慮されなければならない。
【０００４】
楕円曲線暗号が任意の状況で実際に使用される場合がある一方で、ECCはRSAに基づく暗号化よりも少ないメモリ及び計算能力を必要とするので、埋め込みシステムでの使用に特に適している。
【０００５】
楕円曲線暗号の基本演算は、スカラー乗算であり、楕円曲線上の点P及びスカラーｄが得た得られた場合、点Q＝ｄP（すなわち、P＋P+．．．＋P、ｄ回）を計算する必要がある。どの方向でスカラーｄがスキャンされるかに依存して、スカラー演算方法の２つの主要なファミリが存在する。光から右への（left-to-right）方法及び右から左への（right-to-left）方法である。
【０００６】
左から右への方法は、良好なパフォーマンスを生じるのでしばしば使用されるが、低いセキュリティレベルを与えることが知られている。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
今まで、当業者は、ある程度まで、パフォーマンスとセキュリティとを選択することを強いられいる。したがって、従来技術の問題の少なくとも幾つかを克服するソリューションが必要とされる。
【０００８】
本発明は、２つのファミリ間のパフォーマンスにおける違いが減少するように、従来技術の右から左へのスカラー乗算を高速化するソリューションを提供するものである。
【０００９】
古典的な従来技術の右から左への方法に基づくスカラー乗算方法が以下に記載される。
【００１０】
Eを特性≠２，３のフィールドＫにわたる楕円曲線を示すとする。係る楕円曲線は、Weierstrass式EIK：Y2＝X3＋aXZ4＋bZ6により与えることができる。
【００１１】
楕円曲線上の点（X，Y，Z）のセットはアベール群を形成し、この場合、無限遠にある点と呼ばれるニュートラルエレメントはO＝（1，1，0）である。射影の点（X，Y，Z）はZ=0である場合にOに対応し、さもなければアフィン点（X/Z2，Y/Z3）に対応する。なお、射影点の射影座標は、固有ではない。これは、Kにおけるそれぞれの非ゼロについて（X，Y，Z）＝（t2X，t3Y，tZ）であるからである。
【００１２】
古典的な従来技術の右から左へのバイナリスカラー乗算方法は、スカラーｄ≧０及びパラメータａ及びｂをもつ楕円曲線E上の点P=（X，Y，Z）を入力として取得し、点Q＝ｄPを出力する。  
入力：ｄ，P＝（X，Y，Z）
出力：ｄP＝（X*，Y*，Z*）。
【００１３】
方法:
【数１】
0005553773.tif 000002
古典的な従来技術のNAFに基づくスカラー乗算方法は、スカラーｄ≧０及びパラメータａ及びｂをもつ楕円曲線E上の点P=（X，Y，Z）を入力として取得し、点Q＝ｄPを出力する。  
入力：ｄ，P＝（X，Y，Z）
出力：ｄP＝（X*，Y*，Z*）。
【００１４】
方法:
【数２】
0005553773.tif 000003
【課題を解決するための手段】
【００１５】
第一の態様では、本発明は、繰り返される点加算（point  addition）及び点２倍算（point  doubling）により、右から左に楕円曲線上の点のスカラー倍を計算する方法に向けられる。それぞれの点２倍算は、座標の拡張されたセットで評価され、それぞれの点加算は、座標の拡張されたセットの制限されたセットを入力として取得することで評価される。
【００１６】
第一の好適な実施の形態では、ある点加算の出力座標は、次の点２倍算の入力座標として使用される。
【００１７】
第二の好適な実施の形態では、楕円曲線は、２及び３とは異なる特性によるWeierstrass式EIK：Y2＝X3＋aXZ4＋bZ6により与えられ、a及びbは、楕円曲線の第一及び第二パラメータである。
【００１８】
座標T1，T2，T3の値、及びT4＝aT34に初期化される更なる座標T4の値を取得し、中間の変数U＝T12，V＝T22，M＝3U＋T4，W＝V2及びS＝2（（T1+V）2−U−W）を計算し、T3＝2T2T3，T4＝16WT4の新たな値を計算し、T1＝M2−2Sの新たな値を計算し、T2＝M（S−T1）−8Wの新たな値を計算し、少なくとも座標T1，T2，T3及びT4の値を出力することで、点２倍算が計算されることは有利であり、ここでaは、楕円曲線の第一パラメータである。
【００１９】
第三の好適な実施の形態では、スカラー乗算は、スカラーのNAF（Non  Adjacent  Form）を使用して実行される。
【００２０】
第四の好適な実施の形態では、スカラー乗算は、スカラーのバイナリ表現を使用して実行される。
【００２１】
第五の好適な実施の形態では、点２倍算は、モディファイド・ヤコビアン座標を使用して実行され、点加算は、ヤコビアン座標を使用して実行される。
【００２２】
第二の態様では、本発明は、右から左に楕円曲線上の点のスカラー倍を計算する装置に向けられる。本装置は、点２倍算及び点加算のために適合されるプロセッサを有する。プロセッサは、座標の拡張されたセットを使用してそれぞれの点２倍算を評価し、座標の拡張されたセットの制限されたセットを入力として取得することでそれぞれの点加算を評価するために適合される。
【００２３】
第三の態様では、本発明は、プロセッサで実行されたときに、繰り返される点２倍算及び点加算により右から左に楕円曲線上の点のスカラー倍を計算する方法を実行するコンピュータプログラムに向けられ、それぞれの点２倍算は、座標の拡張されたセットで評価され、それぞれの点加算は、座標の拡張されたセットの制限されたセットを入力として取得することで評価されることを特徴とする。
【００２４】
第五の態様では、本発明は、プロセッサで実行されたとき、繰り返される点２倍算及び点加算により右から左に楕円曲線上の点のスカラー倍を計算する方法を実行するコンピュータプログラムを記憶するコンピュータプログラムプロダクトに向けられ、それぞれの点２倍算は、座標の拡張されたセットで評価され、それぞれの点加算は、座標の拡張されたセットの制限されたセットを入力として取得することで評価されることを特徴とする。
【図面の簡単な説明】
【００２５】
本発明の好適な特徴は、添付図面を参照して例示により記載される。
【図１】本発明の好適な実施の形態に係る楕円曲線上の計算の装置を例示する図である。
【図２】本発明の好適な実施の形態に係る点２倍算の方法を例示する図である。
【発明を実施するための形態】
【００２６】
図１は、楕円曲線上の計算、特に、本発明の好適な実施の形態に係る点２倍算及びスカラー乗算を実行する装置１００を例示する。本装置１００は、以下に説明される方法の計算を実行するコンピュータプログラムを実行するために適合される少なくとも１つのプロセッサ１１０（以下「プロセッサ」）を有する。本装置１００は、プロセッサ１１０からの中間の計算結果のようなデータを記憶するために適合されるメモリ１２０を更に有する。また、本装置１００は、他の装置（図示せず）とのインタラクション用の少なくとも１つのインタフェース１３０（以下「インタフェース」）を有する。図１は、たとえばCD-ROMのような、プロセッサ１１０により実行されたとき、本発明の方法の好適な実施の形態に係るスカラー乗算を実行するコンピュータプログラムを記憶するコンピュータプログラムプロダクト１４０を例示する。
【００２７】
本発明の主要な考えは、右から左へのスカラー乗算方法において、正規の点２倍算の演算に関わる値をキャッシュに格納するために使用される更なる座標T4を使用することである。繰り返しの間、更なる座標T4は、メモリ１２０に記憶される。従来技術の方法のステップ３.ｃにおける２倍算が繰り返し実行され、この方法における他の何処かで変更されないので、キャシングは、この方法を高速化するのを可能にするが、これは、余分のメモリ空間の使用を擬制にして達成される。本発明は、速度、すなわち実行される演算（特に乗算）の数とリソース（特にメモリ）の使用との間の良好なトレードオフを発見することを意図する。
【００２８】
図２は、本発明の好適な実施の形態に係る点２倍算の方法を例示する。本方法は、従来技術の方法における２倍算のステップ３.ｃを有利に置き換える。本方法への入力は、値T1，T2，T3及びT4であり、この場合、T4は、本方法の最初の繰り返しにおいてaT34として初期化される。次いで、多数の有効な中間の変数U＝T12；V＝T22；M＝3U＋T4；W＝V2及びS＝2（（T1+V）2−U−W）は、ステップ２１０で定義される。
【００２９】
次いで、ステップ２２０で、T3，T4の新たな値T3＝2T2T3；T4＝16WT4が計算される。
【００３０】
T4の値は、既に言及されたように、次の繰り返しで必要とされるまで、メモリに記憶される。
【００３１】
ステップ２３０で、T1の新たな値T1＝M2−2Sが計算される。
【００３２】
最後に、ステップ２４０で、変数T2の残りの新たな値T2＝M（S−T1）−8Wが計算される。
【００３３】
なお、４つの出力変数は、２倍にされた点を表し、スカラー乗算方法における他のステップにおける更なる計算のためにステップ２５０で出力される場合がある。必要であれば、ステップ２１０〜２５０は、スカラー乗算方法の更なる繰り返しについて繰り返される。この値は点２倍算のためにのみ使用されるので、T4の値を出力することは必ずしも必要ではないことを理解されたい。その値は、点２倍算の次の繰り返しまでメモリに記憶される。
【００３４】
本発明の方法の利点は、特に計算速度に関して言えば、改善されたパフォーマンスを可能にすることである。
【００３５】
表１は、様々なシステムの点２倍算のコストを与え、表２は、点加算のコストを与える。これらの表は、D.J.Bernstein及びT.Langeによる“Faster  addition  and  doubling  on  elliptic  curves”  In:Advances  in  Cryptography-ASIACRYPT  2007,  LNCS,  pp.29-50,  Springer-Verlag,  2007に基づくものである。M,  S,  cは、それぞれ「乗算」、「二乗」及び「定数倍」を意味する。２つの最後の列は、（α，β）＝（１，１）及び（α，β）＝（0.8，0）についてS＝αM及びｃ＝βMのときの乗算の数を与える。
【００３６】
【表１】
0005553773.tif 000004
【００３７】
【表２】
0005553773.tif 000005
最良の全体のパフォーマンスは、点の表現についてヤコビアンの射影座標を使用したときに得られることがわかる。/をｄのビットレングスを示すとする。この場合、Q＝ｄPが古典的なNAFに基づく右から左へのバイナリスカラー乗算方法で評価された場合、期待される演算の数は、約/（1M＋8S＋1c）＋//3（11M＋5S）であり、これは、S＝c＝Mの場合、15.3/Mである。
【００３８】
しかし、本発明に係る方法は、あるタイプの座標を使用して点を加え、別のタイプの座標を使用して点を２倍にする場合がある。たとえば、点加算は、ヤコビアン座標を使用して行われ、点２倍算は、モディファイドヤコビアン座標を使用して行われる。これは、左から右へのスカラー乗算方法によっては非能率的であるか、不可能である。全てのこれらの方法は、共通して、繰り返し２倍にされるアキュムレータであって、入力点又はその倍点が繰り返し加算されるアキュムレータを使用する。これは、点２倍算及び点加算のルーチンの出力の表現が同じである必要があること、すなわちアキュムレータの座標系が同じである必要があることを意味する。
【００３９】
したがって、本発明に係る方法のコストは、約/（3M＋5S）＋//3（11M＋5S）であり、これは、S＝c＝Mという仮定の下で13.3/Mに等しい。したがって、ゲインは、13.3％のスピードアップファクタである。
【００４０】
更なる一時的な変数の使用により更なるメモリの要求を犠牲にして古典的な方法を高速化することが可能であるが、本発明に係る方法は、更に迅速である。高速化された古典的な方法は、14.3/Mに等しい約/（3M＋5S）＋//3（11M＋7S＋1c）でQ＝ｄPを評価するので、更に迅速である。したがって、本発明に係る方法は、更に高速である。
【００４１】
楕円曲線に関するスカラー乗算は、ある点の逆を容易に推定することができ、更なるメモリの要求を必要としないので、NAF（Non  Adjacent  Form）で表現されるスカラーｄで実行される。NAFは右から左に計算されるため、本発明の好適な実施の形態に係る方法を含めて、右から左へのスカラー乗算において、はじめにこれを計算し、次いで左から右へのスカラー乗算方法において行われたようなスカラー乗算を評価する必要がない。表現は、前もってNAF表現を計算及び記憶する必要なしに、オンザフライで計算される。
【００４２】
無限遠での点は、特別な取り扱いを必要とする場合がある。左から右への方法について、これは、先行ゼロがスキップされるべきであることを意味する。スカラーｄは右から左に処理されるので、本発明の好適な実施の形態に係る方法を含めて、右から左へのスカラー乗算により係る複雑さはない。
【００４３】
本発明に係る方法の別の利点は、曲線パラメータが２倍算に関与しないことである。これにより、ハードウェアの実装にとって特に有効である、本方法のハードコーディングを可能にする。
【００４４】
左から右へのスカラー乗算方法とは対照的に、本発明の好適な実施の形態の１つを含む右から左へのスカラー乗算方法は、２倍算のアタックに耐性がある。これらのアタックは、２つのパワー曲線から、秘密情報が十分に回復される場合があるので、非常にパワフルである。
【００４５】
さらに、本発明の方法は、様々なランダム化技術と組み合わせることができる。特に、古典的なDPA対抗手段（すなわち、ランダム化されたポイント表現又はランダム化された同型の曲線表現）を使用して、効率のペナルティが存在しない。
【００４６】
上記説明で開示されたそれぞれの特徴及び（必要であれば）特許請求の範囲及び図面は、独立に提供されるか又は適切な組み合わせで提供される場合がある。ハードウェアで実現されるように記載される特徴は、ソフトウェアで実現される場合もあり、逆に、ソフトウェアで実現されるように記載される特徴は、ハードウェアで実現される場合もある。コネクションは、適用される場合、無線通信又は有線通信として実現される場合があり、必ずしも、ダイレクト又は専用のコネクションである必要はない。
【図１】
0005553773.tif 000006
【図２】
0005553773.tif 000007