(57)【要約】      （修正有）【課題】楕円曲線上の少なくとも二つの点の加算の像に対応する別の点の座標を取得するためのパフォーマンスのよいデータの暗号処理方法を提供する。【解決手段】有限環である代数構造上で定義される同じ楕円曲線に属する少なくとも二つの点の各点は、少なくとも二つの座標によって表現される。方法は、楕円曲線と別の楕円曲線との間の同型のパラメータ化を取得する、パラメータ化はいくつかの構成パラメータを定義し、各構成パラメータはある範囲の可能な値をもつ段階と、少なくとも二つの点の座標の値の関数の形で構成パラメータを決定し、決定された構成パラメータを与える段階と、同型を通じた少なくとも二つの点の加算の像に対応する別の点の座標を取得する、別の点は別の楕円曲線に属し、該取得は、決定された構成パラメータのおかげで、代数構造における逆元計算なしに実行される段階と、を含む。【選択図】図１
2015166867.tif 000002
【特許請求の範囲】
【請求項１】
電子デバイスによって実行される、データの暗号学的処理の方法であって、有限環である代数構造上で定義される同じ楕円曲線に属する少なくとも二つの点を得る段階を含み、各点は、少なくとも二つの座標によって表現され、当該方法は：
・前記楕円曲線と別の楕円曲線との間の同型のパラメータ化を取得する段階であって、前記パラメータ化はいくつかの構成パラメータを定義し、各構成パラメータはある範囲の可能な値をもつ、段階と；
・前記少なくとも二つの点の座標の値の関数として前記構成パラメータを決定し、決定された構成パラメータを与える段階と；
・前記同型を通じた前記少なくとも二つの点の加算の像に対応する別の点の座標を取得する段階であって、前記別の点は前記別の楕円曲線に属し、該取得は、前記決定された構成パラメータのため、前記代数構造における逆元計算なしに実行される、段階とを含むことを特徴とする、
方法。
【請求項２】
前記少なくとも二つの点が同一であるとき、前記加算が二倍演算であることを特徴とする、請求項１記載の方法。
【請求項３】
各点がアフィン座標系において表現されることを特徴とする、請求項１または２記載の方法。
【請求項４】
第一の楕円曲線に属する第一の点とのスカラー乗算演算において使用されることを特徴とする、請求項１ないし３のうちいずれか一項記載の方法。
【請求項５】
前記スカラー乗算演算の、最後の楕円曲線に属する出力点を、前記第一の楕円曲線に属する変換された出力点に変換する段階を含むことを特徴とする、請求項４記載の方法。
【請求項６】
前記代数構造が2に等しい標数をもつ有限体であることを特徴とする、請求項１ないし５のうちいずれか一項記載の方法。
【請求項７】
前記代数構造が3に等しい標数をもつ有限体であることを特徴とする、請求項１ないし５のうちいずれか一項記載の方法。
【請求項８】
前記代数構造が素数p＞3に等しい標数をもつ有限体であることを特徴とする、請求項１ないし５のうちいずれか一項記載の方法。
【請求項９】
コンピュータによって実行されたときに暗号学的計算のための方法を実装するためのコンピュータ実行可能な命令の集合を含むコンピュータ・プログラムを記憶しているコンピュータ可読であり非一過性の記憶媒体であって、前記命令は、実行されたときに請求項１ないし８のうちいずれか一項記載の方法を実行するようコンピュータを構成する命令を含む、記憶媒体。
【請求項１０】
データの暗号処理を実行するよう構成された電子デバイスであって、有限環である代数構造上で定義される同じ楕円曲線に属する少なくとも二つの点を得る手段を有しており、各点は、少なくとも二つの座標によって表現され、当該電子デバイスは：
・前記楕円曲線と別の楕円曲線との間の同型のパラメータ化を取得する手段であって、前記パラメータ化はいくつかの構成パラメータを定義し、各構成パラメータはある範囲の可能な値をもつ、手段と；
・前記少なくとも二つの点の座標の値の関数として前記構成パラメータを決定し、決定された構成パラメータを与える手段と；
・前記同型を通じた前記少なくとも二つの点の加算の像に対応する別の点の座標を取得する手段であって、前記別の点は前記別の楕円曲線に属し、該取得は、前記決定された構成パラメータのため、前記代数構造における逆元計算なしに実行される、手段とを有することを特徴とする、
電子デバイス。
【請求項１１】
前記少なくとも二つの点が同一であるとき、前記加算が二倍演算であることを特徴とする、請求項１０記載の電子デバイス。
【請求項１２】
各点がアフィン座標系において表現されることを特徴とする、請求項１０または１１記載の電子デバイス。
【請求項１３】
前記手段が、最初の楕円曲線に属する最初の点とのスカラー乗算演算を実行するために使用されることを特徴とする、請求項１０ないし１２のうちいずれか一項記載の電子デバイス。
【請求項１４】
前記スカラー乗算演算の、最後の楕円曲線に属する出力点を、前記最初の楕円曲線に属する変換された出力点に変換する手段を有することを特徴とする、請求項１３記載の電子デバイス。
【請求項１５】
前記代数構造が素数p＞3に等しい標数をもつ有限体であることを特徴とする、請求項１０ないし１４のうちいずれか一項記載の電子デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号に、より詳細には楕円曲線暗号に関する。本開示は数多くの応用をもち、組み込みデバイスにおいて使われるのに好適である。より一般には、楕円曲線の使用に基づくすべての暗号プロトコルおよびアルゴリズムに適用できる。
【背景技術】
【０００２】
本節は、以下で記述されるおよび／または特許請求される本発明のさまざまな側面に関係しうる技術のさまざまな側面を読者に紹介するために意図されたものである。この議論は、本発明のさまざまな側面のよりよい理解を容易にするために、読者に背景情報を提供する助けとなると信ずる。よって、これらの陳述は、従来技術の自認ではなく、この観点で読まれるべきであることは理解しておくべきである。
【０００３】
楕円曲線暗号（elliptic  curve  cryptography）は、通常のRSA暗号システム（指数関数より弱い安全性）に比べ、より小さな鍵サイズで高いレベルの安全性（指数関数的安全性）を提供する。ますます多くの人が小型電子装置に頼るにつれ、ECCの応用は日常生活において増加しつつある。より小さな鍵サイズはECCを、PDAやスマートカードのような制約されたデバイスにとって魅力的にする。ECCの効率性は、スカラー乗算（または点乗算）と呼ばれる演算によって支配される。問題は、（有限体または有限環上で定義される）楕円曲線上の点Pおよびスカラーkを与えられて、点kP、すなわちP＋……＋P（k−1回）をできるだけコスト効率よく生成するというものである。この問題は、冪乗の評価の自明な類推である。よって、ここでは、冪乗の高速評価の方法が、効率的な実装を得るために使用できる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】D.Bernstein  et  al.,  Explicit-Formulas  Database、ウェブサイトhttp://www.hyperelliptic.org/EFD
【発明の概要】
【発明が解決しようとする課題】
【０００５】
楕円曲線群演算は、定義環におけるいくつかの演算を用いて表現できる。決定的な問題は、環演算の数を最小にする仕方で楕円曲線を表現する正しいモデルを見出すことになる。実際、楕円曲線は双有理変換の自由度を除いたところまで定義されるので、その表現のためには多くの可能な選択がある。しかしながら、座標および演算の数を爆発させないために、実際上は、低次元空間にある楕円曲線のモデルのみが考慮される。
【０００６】
さらに、点加算公式に関わる基本演算（つまり環加算／減算、環乗算および環逆元計算）は互いに等価ではない。特に、環逆元計算は、全体的なパフォーマンスに著しく影響しうるので、特別な注意を要する。楕円曲線を使う暗号アプリケーションでは、根底にある有限環における乗算に対する逆元計算の比は3ないし30の範囲になる。そのため、逆元計算のない点加算公式が特に関心があることになる。これは、（広く使われている同次およびヤコビアン座標を含む）射影表現に頼ることによって古典的に達成される。
【０００７】
さまざまな座標系を使う楕円曲線の数多くの有用な形およびそれらのコストが、非特許文献１にまとめられている。
【０００８】
楕円曲線上の点を表現するためにアフィン座標系が使われるとき、現在のところ、有限環おける逆元計算を使うことを防ぐ技法はない。スカラー乗算における環逆元計算をなくすことが、本技法のねらいである。提案される技法は、もちろん、点間で基本演算（加算）のみが実行される他のコンテキスト（ECDSAアルゴリズムの検証など）に適用されることができる。
【課題を解決するための手段】
【０００９】
本明細書における「一つの実施形態」、「ある実施形態」、「例示的実施形態」への言及は、記載される実施形態が特定の特徴、構造または特性を含むことを示すことがあるが、必ずしもすべての実施形態がその特定の特徴、構造または特性を含むとは限らない。さらに、そのような句は必ずしも同じ実施形態を参照しているのではない。さらに、ある特定の特徴、構造または特性がある実施形態との関連で記述されるとき、明示的に記載されているか否かによらず、そのような特徴、構造または特性を他の実施形態との関連で実施することは、当業者の知識の範囲内である。
【００１０】
本発明は、電子デバイスによって実行される、データの暗号学的処理の方法であって、有限環である代数構造上で定義される同じ楕円曲線に属する少なくとも二つの点を得ることを含む、方法に向けられる。各点は、少なくとも二つの座標によって表現される。本方法は：
・前記楕円曲線と別の楕円曲線との間の同型のパラメータ化を取得する段階であって、前記パラメータ化はいくつかの構成パラメータを定義し、各構成パラメータはある範囲の可能な値をもつ、段階と；
・前記少なくとも二つの点の座標の値の関数の形で前記構成パラメータを決定し、決定された構成パラメータを与える段階と；
・前記同型を通じた前記少なくとも二つの点の加算の像に対応する別の点の座標を取得する段階であって、前記別の点は前記別の楕円曲線に属し、該取得は、前記決定された構成パラメータのおかげで、前記代数構造における逆元計算なしに実行される、段階とを含む点で注目すべきである。
【００１１】
よって、同型のパラメータ化の構成パラメータの選択に応じて、点の加算における逆元計算の実行を避けることができる。該選択は、点の座標の値の関数の形で実行される。当業者は構成パラメータについてランダムな値を使ったであろうという事実のため、構成パラメータの選択は自明ではなかったことを注意しておくべきである。
【００１２】
ある好ましい実施形態では、本方法は、前記少なくとも二つの点が同一であるとき、前記加算が二倍演算であるという点で注目すべきである。
【００１３】
ある好ましい実施形態では、本方法は、各点がアフィン座標系において表現されるという点で注目すべきである。
【００１４】
ある好ましい実施形態では、本方法は、第一の楕円曲線に属する第一の点とのスカラー乗算演算において使用されるという点で注目すべきである。
【００１５】
ある好ましい実施形態では、本方法は、前記スカラー乗算演算の、最後の楕円曲線に属する出力点を、前記第一の楕円曲線に属する変換された出力点に変換する段階を含むという点で注目すべきである。
【００１６】
よって、提案される技法は、現状技術におけるような逆元計算演算を使わない。提案される方法は、楕円曲線上でのスカラー乗算の効率的な実装を可能にする。提案される技法は、点加算公式における逆元の計算を避ける方法として、曲線同型の使用に依拠する。おもしろいことに、提案される技法は、楕円曲線を表わすために使われるモデルが何であろうと、点を表わすために使われる座標系が何であろうと適用される。よって、提案される技法はアフィン表現、ヤコビアン表現などに適用されることができる。
【００１７】
ある好ましい実施形態では、本方法は、前記代数構造が2に等しい標数（characteristic）をもつ有限体であるという点で注目すべきである。
【００１８】
ある好ましい実施形態では、本方法は、前記代数構造が3に等しい標数をもつ有限体であるという点で注目すべきである。
【００１９】
ある好ましい実施形態では、本方法は、前記代数構造が素数p＞3に等しい標数をもつ有限体であるという点で注目すべきである。
【００２０】
ある例示的な実装によれば、本方法の種々の段階は、コンピュータ・ソフトウェア・プログラム（単数または複数）によって実装され、該ソフトウェア・プログラムは、本開示に基づくリレー・モジュールのデータ・プロセッサによって実行されるよう設計され、本方法の種々の段階の実行を制御するよう設計されたソフトウェア命令によって実装される。
【００２１】
結果として、本開示のある側面は、コンピュータによってまたはデータ・プロセッサによって実行されるべきプログラムにも関する。このプログラムは、上述した方法の段階の実行を指令する命令を含む。
【００２２】
このプログラムは、いかなるプログラミング言語を使うこともでき、ソース・コード、オブジェクト・コードまたは部分的にコンパイルされた形のようなソース・コードとオブジェクト・コードの中間であるコードの形または他の任意の望ましい形であることができる。
【００２３】
本開示は、データ・プロセッサが読むことができ、上述したプログラムの命令を含む情報媒体にも関する。
【００２４】
情報媒体は、プログラムを記憶することのできるいかなるエンティティまたはデバイスであることもできる。たとえば、媒体は、ROM（これは「Read  Only  Memory（読み出し専用メモリ）」の略）、たとえばCD-ROM（これは「Compact  Disc-Read  Only  Memory（コンパクト・ディスク‐読み出し専用メモリ）」の略）またはマイクロ電子回路ROMのような、あるいはまた磁気記録手段、たとえばフロッピー（登録商標）ディスクまたはハードディスクドライブのような記憶手段を含むことができる。
【００２５】
さらに、情報媒体は、電気または光ケーブルを通じて伝達されることのできる電気または光信号のような伝送可能キャリアであってもよい。プログラムは、特に、インターネット型ネットワークにダウンロードされることができる。
【００２６】
あるいはまた、情報媒体はプログラムが組み込まれることのできる集積回路であることができる。該回路は、問題の方法を実行するまたは問題の方法の実行において使用されることに適応されている。
【００２７】
ある実施形態によれば、本開示のある実施形態は、ソフトウェアおよび／またはハードウェア・コンポーネントによって実装される。この観点から、本稿では、用語「モジュール」は、ソフトウェア・コンポーネントおよびハードウェア・コンポーネントの両方に、あるいはハードウェアおよびソフトウェア・コンポーネントのセットに対応することができる。
【００２８】
ソフトウェア・コンポーネントは、一つまたは複数のコンピュータ・プログラム、プログラムの一つまたは複数のサブプログラムまたはより一般には、当該モジュールについて以下に記載されるものに基づく機能または機能のセットを実装することのできるプログラムの任意の要素またはソフトウェア・プログラムに対応する。一つのそのようなソフトウェア・コンポーネントは、物理的なエンティティ（端末、サーバーなど）のデータ・プロセッサによって実行され、この物理的なエンティティのハードウェア資源（メモリ、記録媒体、通信バス、入出力電子基板、ユーザー・インターフェースなど）にアクセスすることができる。
【００２９】
同様に、ハードウェア・コンポーネントは、当該モジュールについて以下に記載されるものに基づく機能または機能のセットを実装することのできるハードウェア・ユニットの任意の要素に対応する。それは、プログラム可能なハードウェア・コンポーネントまたはソフトウェアの実行のための集積回路をもつコンポーネント、たとえば集積回路、スマートカード、メモリカード、ファームウェアなどを実行するための電子基板などであってもよい。ある変形では、ハードウェア・コンポーネントは、中央処理ユニットおよび／またはマイクロプロセッサおよび／または特定用途向け集積回路（ASIC:  Application-specific  integrated  circuit）および／または特定用途向け命令セット・プロセッサ（ASIP:  Application-specific  instruction-set  processor）および／またはグラフィクス処理ユニット（GPU:  graphics  processing  unit）および／または物理処理ユニット（PPU:  physics  processing  unit）および／またはデジタル信号プロセッサ（DSP:  digital  signal  processor）および／または画像プロセッサおよび／またはコプロセッサおよび／または浮動小数点ユニットおよび／またはネットワーク・プロセッサおよび／またはオーディオ・プロセッサおよび／またはマルチコア・プロセッサのような集積回路であるプロセッサを有する。さらに、ハードウェア・コンポーネントは、ベースバンド・プロセッサ（たとえばメモリ・ユニットおよびファームウェアを有する）および／または電波信号を受信もしくは送信する電波電子回路（アンテナを有することができる）を有することもできる。ある実施形態では、ハードウェア・コンポーネントは、ISO/IEC18092/ECMA-340、ISO/IEC21481/ECMA-352、GSMA、StoLPaN、ETSI/SCP（SmartCardPlatform［スマート・カード・プラットフォーム］）、グローバルプラットフォーム（GlobalPlatform）（すなわちセキュアな要素）のような一つまたは複数の標準に準拠する。ある変形では、ハードウェア・コンポーネントは電波周波数識別（RFID:  Radio-frequency  identification）タグである。ある実施形態では、ハードウェア・コンポーネントは、ブルートゥース通信および／またはWi-fi通信および／またはジグビー通信および／またはUSB通信および／またはファイアワイア通信を可能にする回路を有する。
【００３０】
本稿における要素／値を取得する段階が、電子デバイスのメモリ・ユニットにおけるそのような要素／値を読む段階または通信手段を介して別の電子デバイスからそのような要素／値を受領する段階として見ることができることをも注意しておくべきである。
【００３１】
もう一つの実施形態では、データの暗号処理を実行するよう構成された電子デバイスであって、有限環である代数構造上で定義される同じ楕円曲線に属する少なくとも二つの点を得る手段を有する、デバイスに向けられる。各点は、少なくとも二つの座標によって表現される。本電子デバイスは：
・前記楕円曲線と別の楕円曲線との間の同型のパラメータ化を取得する手段であって、前記パラメータ化はいくつかの構成パラメータを定義し、各構成パラメータはある範囲の可能な値をもつ、手段と；
・前記少なくとも二つの点の座標の値の関数の形で前記構成パラメータを決定し、決定された構成パラメータを与える手段と；
・前記同型を通じた前記少なくとも二つの点の加算の像に対応する別の点の座標を取得する手段であって、前記別の点は前記別の楕円曲線に属し、該取得は、前記決定された構成パラメータのおかげで、前記代数構造における逆元計算なしに実行される、手段とを有する点で注目すべきである。
【００３２】
ある変形では、本電子デバイスは、前記少なくとも二つの点が同一であるとき、前記加算が二倍演算であるという点で注目すべきである。
【００３３】
ある変形では、本電子デバイスは、各点がアフィン座標系において表現されるという点で注目すべきである。
【００３４】
ある変形では、本電子デバイスは、前記手段が、第一の楕円曲線に属する第一の点とのスカラー乗算演算を実行するために使用されるという点で注目すべきである。
【００３５】
ある変形では、本電子デバイスは、前記スカラー乗算演算の、最後の楕円曲線に属する出力点を、前記第一の楕円曲線に属する変換された出力点に変換する手段を有するという点で注目すべきである。
【００３６】
もう一つの実施形態では、本電子デバイスは、前記代数構造が素数p＞3に等しい標数をもつ有限体であるという点で注目すべきである。
【図面の簡単な説明】
【００３７】
本発明の上記および他の側面は、付属の図面を参照してのその例示的実施形態の以下の詳細な説明からより明白となるであろう。
【図１】本発明のある実施形態に基づく楕円曲線上でのスカラー乗算を示す図である。
【図２】楕円曲線上でのスカラー乗算を実行する二つの古典的方法（二倍して加算法と加算して二倍法）を示す図である。
【図３】本技法に基づく、楕円曲線上でのスカラー乗算を実行する二つの方法を示す図である。
【図４】本技法に基づく、楕円曲線上でのスカラー乗算を実行する方法のもう一つの実施形態を示す図である。
【図５】楕円曲線上でのスカラー乗算を実行する二つの古典的方法（モンゴメリー・ラダーおよびジョワ（Joye）の二倍‐加算ラダー）を示す図である。
【図６】本発明のある実施形態に基づく、図５に開示される楕円曲線上でのスカラー乗算を実行する方法の二つの修正を示す図である。
【図７】本発明のある実施形態に基づく、図５に開示される楕円曲線上でのスカラー乗算を実行するモンゴメリー・ラダー方法の修正を示す図である。
【図８】本稿に開示される方法の一つまたは複数の段階を実行するために使用できる装置を示す図である。
【発明を実施するための形態】
【００３８】
提案される方法を完全な一般性をもって記載する前に、まずヴァイエルシュトラス・モデルに対するいくつかのコメントをしておく。説明を簡単にするため、2または3とは異なる標数の環上で定義された楕円曲線に焦点を当てる。慣例通り、K*は
【００３９】
【数１】
2015166867.tif 000003
の乗法群を表わし〔本稿では便宜上上記のように通常の書体を使うことがある〕、Char(K)はKの標数を表わすものとする。
【００４０】
環K、Char(K)≠2,3上での、
E1：y2＝x3＋a・x＋b
によって与えられる楕円曲線E1を考える。
【００４１】
任意のu∈K*について、楕円曲線E1は楕円曲線：
Eu：y2＝x3＋a・u4・x＋bu6
に対して、逆のマッピング
【００４２】
【数２】
2015166867.tif 000004
を介してK同型である。E1上の二つの有限な点、点P1＝(x1,y1)および点P2＝(x2,y2)であって、P1≠±P2（すなわち、x1≠x2）であるようなものが与えられるとき、(x1−x2)∈K*であれば、それらの和はP3＝P1＋P2＝(x3,y3)によって与えられ、ここで
【００４３】
【数３】
2015166867.tif 000005
である。y1∈K*であれば、P1＝(x1,y1)の二倍は、P4＝2P1＝P1＋P1＝(x4,y4)によって与えられ、ここで
【００４４】
【数４】
2015166867.tif 000006
である。
【００４５】
本発明のある実施形態では、本技法は、次の性質を使う：φ:＝x1−x2を定義することによって、上記の加算公式（eq.1として参照される）から次を得る。
【００４６】
【数５】
2015166867.tif 000007
換言すれば、楕円曲線E1上に点P1およびP2が与えられるとき、同型な楕円曲線Eφ上で、点
【００４７】
【数６】
2015166867.tif 000008
を容易に得ることができる。チルダ付きのP3の評価において、逆元演算が必要とされないことは注目に値する。iADDが
【００４８】
【数７】
2015166867.tif 000009
を得る演算を表わすことにする。
【００４９】
同様の扱いが点二倍演算に当てはまることを注意しておくべきである。（二倍演算は、同一である二つの点の間の具体的な加算として見ることができる。しかしながら、点が同じであるまたは同じでない場合に加算を実行するために使われる公式は必ずしも同じではない。）ここでφ:＝2y1と定義すると、上記二倍公式（eq.2として参照される）から次を得る。
【００５０】
【数８】
2015166867.tif 000010
つまり、E1上の点P1を与えられたとき、楕円曲線Eφに属する点
【００５１】
【数９】
2015166867.tif 000011
を容易に得ることができる。上記点加算についてと同様に、チルダ付きのP4の評価において、逆元演算が必要とされないことは注目に値する。iDBLが
【００５２】
【数１０】
2015166867.tif 000012
を得る演算を表わすことにする。
【００５３】
E1を環K上での楕円曲線であるとする。何らかのパラメータ
【００５４】
【数１１】
2015166867.tif 000013
によってインデックス付けされる、同型
【００５５】
【数１２】
2015166867.tif 000014
のもとでの同型な楕円曲線の族
【００５６】
【数１３】
2015166867.tif 000015
を考える。
【００５７】
矢印→付きのφで表わされるパラメータは、同型の記述である（すなわち、同型を定義するパラメータ化である）。
【００５８】
【数１４】
2015166867.tif 000016
という記法を使う（Descはdescription〔記述〕の略）。すべての可能なパラメータの集合は
【００５９】
【数１５】
2015166867.tif 000017
で表わされる。
【００６０】
iADD、iADDUおよびiADDCと記される次の三つの加算演算は、次の式によって定義される。
【００６１】
【数１６】
2015166867.tif 000018
効率のため、→付きのφで表わされるパラメータは、E1上に二つの異なる点P1およびP2が与えられたときに、加算演算の出力が環逆元計算を必要としないように選ばれる。
【００６２】
また、次式によって定義される二つの二倍演算iDBLおよびiDBLUを与える。
【００６３】
【数１７】
2015166867.tif 000019
同様に、→付きのφで表わされるパラメータは、E1に属する点P1が与えられたときに、二倍演算の出力が環逆元計算を必要としないように選ばれる。
【００６４】
より一般には、
【００６５】
【数１８】
2015166867.tif 000020
と同型な二つの楕円曲線
【００６６】
【数１９】
2015166867.tif 000021
が与えられたとき、
【００６７】
【数２０】
2015166867.tif 000022
がこれらの楕円曲線の間の同型を表わすとすると、同様に、次の演算を定義する。
【００６８】
【数２１】
2015166867.tif 000023
演算子定義における添え字の→付きのφは、入力点が楕円曲線
【００６９】
【数２２】
2015166867.tif 000024
に属することを示す。
【実施例】
【００７０】
以下の例は上記の原理を例解する。環K（標数が何であれ）上で定義された一般的なヴァイエルシュトラス・モデルについて、次のようになる。
【００７１】
E1  :y2＋a1xy＋a3y＝x3＋a2x2＋a4x＋a6
ここで、パラメータa1、a2、a3、a4およびa6はKに属し、
【００７２】
【数２３】
2015166867.tif 000025
であり、ここで、同型の記述
【００７３】
【数２４】
2015166867.tif 000026
は四つのパラメータu,r,s,tによって与えられる。よって
【００７４】
【数２５】
2015166867.tif 000027
また、
【００７５】
【数２６】
2015166867.tif 000028
である。ここで、KはE1の定義環である。よって、同型
【００７６】
【数２７】
2015166867.tif 000029
は、
E1  :y2＋a1xy＋a3y＝x3＋a2x2＋a4x＋a6
の点Pの、楕円曲線
E'1  :y2＋a'1xy＋a'3y＝x3＋a'2x2＋a'4x＋a'6
に属する点へのマッピングを可能にする。ここで、パラメータa'1、a'2、a'3、a'4およびa'6はKに属する。対応する曲線パラメータは、下記の式によって関係付けられる。
【００７７】
【数２８】
2015166867.tif 000030
Kの標数が2でも3でもないとき、一般性を失うことなく、a1＝a2＝a3＝0と選ぶことができる。同様に、Kの標数が2であるとき、楕円曲線が非超特異（non-supersingular）であれば、a1＝1かつa3＝a4＝0と選ぶことができる。
【００７８】
以下の節では、2にも3にも等しくない標数をもつ環上で、短ヴァイエルシュトラス・モデルに従って定義される楕円曲線を用いて、演算子iADD、iADDU、iADDC、iDBLおよびiDBLUの出力を得るために実行される明示的な計算が与えられる。
【００７９】
より精密には、（2にも3にも等しくない標数をもつ環K上で定義される（短ヴァイエルシュトラス・モデルに基づく）楕円曲線E1  :y2＝x3＋ax＋bに属する）点P1およびP2から
【００８０】
【数２９】
2015166867.tif 000031
の評価は下記のようにできる：
・Kにおいてφ＝x1−x2を得る；
・KにおいてC＝φ2を得る；
・KにおいてW1＝x1Cを得る；
・KにおいてW2＝x2Cを得る；
・KにおいてD＝(y1−y2)2を得る；
・KにおいてA1＝(W1−W2)y1を得る；
すると、Kにおいて
【００８１】
【数３０】
2015166867.tif 000032
となる。
【００８２】
この一連の演算はiADD演算に対応する。これは4M＋2Sのグローバルなコストをもつ。ここで、MおよびSはそれぞれKにおける乗算および二乗のコストを表わす。
【００８３】
【数３１】
2015166867.tif 000033
の評価の間に、
【００８４】
【数３２】
2015166867.tif 000034
が自動的に得られることを注意しておくべきである。実際、
【００８５】
【数３３】
2015166867.tif 000035
を用いてただちに
【００８６】
【数３４】
2015166867.tif 000036
が得られる。
【００８７】
先述したように、チルダ付きのP1と一緒にチルダ付きのP3を得る演算はiADDUと記される。
【００８８】
（2にも3にも等しくない標数をもつ有限環K上で定義される楕円曲線E1  :y2＝x3＋ax＋bに属する）点P1およびP2から
【００８９】
【数３５】
2015166867.tif 000037
の評価は下記のようにできる：
・KにおいてW1＝x1Cを得る；
・KにおいてW2＝x2Cを得る；
・KにおいてA1＝(W1−W2)y1を得る；
すると、Kにおいて
【００９０】
【数３６】
2015166867.tif 000038
となる。
【００９１】
実際、−P2＝(x2,−y2)なので、P1−P2＝(x'3,y'3)が
【００９２】
【数３７】
2015166867.tif 000039
を満たすことがわかる。よって、iADDCと記される、ψφ(P1−P2)を得る演算は5M＋3Sしか必要としない。
【００９３】
（2にも3にも等しくない標数をもつ有限環K上で定義される楕円曲線E1  :y2＝x3＋ax＋bに属する）点P1から
【００９４】
【数３８】
2015166867.tif 000040
の評価は下記のようにできる：
・KにおいてB＝x12を得る；
・KにおいてE＝y12を得る；
・KにおいてL＝E2を得る；
・KにおいてM＝3B＋aを得る；
・KにおいてS＝2((x1＋E)2−B−L)を得る；
すると、Kにおいて
【００９５】
【数３９】
2015166867.tif 000041
となる。
【００９６】
【数４０】
2015166867.tif 000042
の評価はiDBLと記され、そのような演算は1M＋5Sしか必要としない。さらに、チルダ付きのP4の評価の間に、
【００９７】
【数４１】
2015166867.tif 000043
が自動的に得られる。実際、
【００９８】
【数４２】
2015166867.tif 000044
となる。チルダ付きのP4およびチルダ付きのP4を得ることからなる演算は、先述したように、iDBLUと記される。
【００９９】
楕円曲線を使う暗号方式において最もよく使われる演算の一つは、スカラー乗算である。
【０１００】
図１は、本発明のある実施形態に基づく、楕円曲線上でのスカラー乗算を示している。
【０１０１】
より精密には、このスカラー乗算は、スカラー乗算プロセスの間に決定される同型のチェーンまたは系列の使用を介して二倍および加算演算を使うことを含む。
【０１０２】
E(0)＝E1がもとの楕円曲線を表わすとし、
【０１０３】
【数４３】
2015166867.tif 000045
が段階Iにおける現在の楕円曲線を表わし、
【０１０４】
【数４４】
2015166867.tif 000046
が最後の楕円曲線を表わすとすると、
【０１０５】
【数４５】
2015166867.tif 000047
となる。
【０１０６】
段階iにおける現在の曲線ともとの曲線との間の同型は
【０１０７】
【数４６】
2015166867.tif 000048
によって与えられる。記法をやや拡張して、白丸記号を対応する記述に対する演算を表わすためにも使う。つまり、
【０１０８】
【数４７】
2015166867.tif 000049
となる。
【０１０９】
【数４８】
2015166867.tif 000050
なので、結果点Q＝k.P∈E(0)は
【０１１０】
【数４９】
2015166867.tif 000051
によって与えられる。「合成された」同型
【０１１１】
【数５０】
2015166867.tif 000052
は、
【０１１２】
【数５１】
2015166867.tif 000053
（すなわち、恒等マップ）として、
【０１１３】
【数５２】
2015166867.tif 000054
であることを観察することによって、逐次反復的に得られる。
【０１１４】
【数５３】
2015166867.tif 000055
なので、
【０１１５】
【数５４】
2015166867.tif 000056
が得られる。
【０１１６】
以下の例はそのような原理を例解する。一般的ヴァイエルシュトラス・モデルについて、
【０１１７】
【数５５】
2015166867.tif 000057
であるから、i≧1について
【０１１８】
【数５６】
2015166867.tif 000058
(U0,R0,S0,T0)＝(1,0,0,0)である。
【０１１９】
図２は、楕円曲線上でのスカラー乗算を実行する二つの古典的方法（二倍して加算法と加算して二倍法）を示している。
【０１２０】
Q＝kP（すなわち、楕円曲線上のスカラー乗算）を評価するための古典的方法は、スカラーkの二進表現k＝(kn-1,……,k0)2を考える。ここで、ki∈{0,1}、0≦i≦n−1である。有利なことに、これが必要とするのは最小数のレジスタであり、よって、スマートカードのようなメモリが制約されたデバイスに好適である。この方法は、kが偶数であれば
【０１２１】
【数５７】
2015166867.tif 000059
であり、kが奇数であれば
【０１２２】
【数５８】
2015166867.tif 000060
であるという自明な関係に依拠する。このプロセスを逐次反復すると、二倍して加算法（double-and-add  method）として知られる左から右へのスカラー乗算アルゴリズムが与えられる。そのような方法は、二つの（点）レジスタR0およびR1を必要とする。レジスタR0は累積器〔アキュムレーター〕として作用し、レジスタR1は入力点Pの値を記憶するために使われる。
【０１２３】
右から左の変形がある。加算して二倍法（add-and-double  method）として知られる結果として得られるアルゴリズムは、図２のアルゴリズム２に描かれている。これも二つの（点）レジスタR0およびR1を必要とするが、この場合は両方とも累積器〔アキュムレーター〕として作用する。
【０１２４】
図３は、本技法に基づく、楕円曲線上でのスカラー乗算を実行する二つの方法を示す図である。
【０１２５】
より精密には、図３に示されるアルゴリズムまたは方法は、本発明の一つの実施形態に基づく加算および二倍公式を用いての上記古典的方法のストレートな実装である。もとの曲線との現在の同型［の記述］を累積するために、矢印→付きのφで表わされる変数を使う。この変数は
【０１２６】
【数５９】
2015166867.tif 000061
（恒等マップIdに対応）に初期化される。先述したように、白丸記号は楕円曲線同型［の記述］の組成を表わす。
【０１２７】
図４は、本技法に基づく、楕円曲線上でのスカラー乗算を実行する方法のもう一つの実施形態を示している。
【０１２８】
そのような実施形態は、図３に描かれたものより効率的な、上記の左から右の方法の変形である。k1が1に等しいときはレジスタR1はレジスタR0に加えられ、レジスタR1の内容は計算を通じて不変なままである（R1は常に入力点Pを含んでいる）ことに注目すると、それを現在の楕円曲線上の点として常に更新することは必要ない。その代わり、反復工程iにおいて、現在の楕円曲線
【０１２９】
【数６０】
2015166867.tif 000062
上でのその代表が、入力点Pから
【０１３０】
【数６１】
2015166867.tif 000063
として計算されることができる。
【０１３１】
図５は、楕円曲線上でのスカラー乗算を実行する二つの古典的方法（モンゴメリー・ラダーおよびジョワ（Joye）の二倍‐加算ラダー）を示している。
【０１３２】
これらの古典的方法は、演算のいくつかの結果を記憶するために、三つのレジスタを使う（レジスタR0、レジスタR1およびレジスタT）。
【０１３３】
図６は、本発明のある実施形態に基づく、図５に開示される楕円曲線上でのスカラー乗算を実行する方法の二つの修正を示している。
【０１３４】
いくつかの楕円曲線モデルについては、二つの相異なる点の点加算公式は、曲線パラメータとは独立である。この場合、iADDUおよびiADDC演算の系列として書くことのできるスカラー乗算アルゴリズムに依拠することが有益である。
【０１３５】
主ループは、アルゴリズム６については、R1-b←Rb＋R1-bおよびRb←2Rb（ここでbは0または1に等しい）と読め、アルゴリズム７については、R1-b←Rb＋2R1-bと読める。したがって、アルゴリズム６およびアルゴリズム７は、本稿で提案される新たな演算を用いて簡単に適応されることができる。値kn-1＝1は、アルゴリズム６の最初の反復工程において、(R0,T)＝(P,P)に、次いでR1＝P＋Pにつながる。この最後の演算は点を二倍することである。潜在的な特殊なケースを扱う必要がないように、kn-1＝1とし、よってforループをi＝n−2において開始し、(R0,R1)を(P,2P)で初期化する。よりよいパフォーマンスのために、これは、iDBLU演算のおかげをもって達成される。同じ理由により、右から左アルゴリズムではk0＝1とする。アルゴリズム９において、forループをi＝2において開始し、(Rk1,R1-k1)を(P,3P)で初期化する。ここでもまた、これは上記の新たな演算を用いてできる。k0＝0であるときは、正しい結果を得るために、計算の最後に点Pが減算される必要がある。
【０１３６】
図７は、本発明のある実施形態に基づく、図５に開示される楕円曲線上でのスカラー乗算を実行するモンゴメリー・ラダー方法の修正を示す図である。
【０１３７】
もとのモンゴメリー・ラダーは、差R1−R0を不変に保つ。この差はPに等しい。等価だが、アルゴリズム６における変数T（←Rb−R1-b）は(−1)1-bPに等しい。したがって、反復工程i＝0において、モンゴメリー・ラダーの我々のバージョン（アルゴリズム８）における変数Rbは、行４において、
【０１３８】
【数６２】
2015166867.tif 000064
の値を含む。これにより、
【０１３９】
【数６３】
2015166867.tif 000065
の記述を、よって
【０１４０】
【数６４】
2015166867.tif 000066
の記述を、
【０１４１】
【数６５】
2015166867.tif 000067
として明示的に復元することができうる。結果として、現在の同型を追跡する必要がないモンゴメリー様アルゴリズムを得ることができる。iADDCおよびiADDU演算は点を返す必要があるだけであり、結果として得られる曲線の同型の記述、すなわちパラメータ
【０１４２】
【数６６】
2015166867.tif 000068
を返す必要はない。このことは、演算子に対する記号′で表わされている。モンゴメリー・ラダーのこの変形は、iADDCおよびiADDU演算が曲線パラメータから独立であることをも要求する。このことは、演算子において添え字
【０１４３】
【数６７】
2015166867.tif 000069
がないことによって示されている。
【０１４４】
図８は、本稿に開示される方法（またはアルゴリズム）の一つまたは複数の段階を実行するために使用できる装置を示している。
【０１４５】
８００で表わされるそのような装置は、８０１で表わされるコンピューティング・ユニット（たとえば「Central  Processing  Unit（中央処理ユニット）」の略であるCPU）と、８０２で表わされる一つまたは複数のメモリ・ユニット（たとえばコンピュータ・プログラム命令の実行の間に一時的に中間的な結果が記憶されることのできるRAM（「Random  Access  Memory（ランダム・アクセス・メモリ）」の略）ブロックまたは特にコンピュータ・プログラムが記憶されるROMブロックまたはEEPROM（「Electrically-Erasable  Programmable  Read-Only  Memory（電気的に消去可能なプログラム可能型読み出し専用メモリ）」）ブロックまたはフラッシュ・ブロック）とを有する。コンピュータ・プログラムは、コンピューティング・ユニットによって実行されることのできる命令で構成される。そのような装置８００は、装置８００が他の装置と通信できるようにする入出力インターフェースをなす、８０３で表わされる専用のユニットをも有することができる。特に、この専用のユニット８０３は、（コンタクトなしで通信を実行するために）アンテナを用いて、あるいは（通信「コンタクト」を担持する）シリアル・ポートを用いて接続されることができる。図８における矢印は、つながれているユニットがたとえば一緒に諸バスを通じてデータを交換できることを意味することを注意しておくべきである。
【０１４６】
ある代替的な実施形態では、先述した方法の段階の一部または全部がプログラム可能なFPGA（「Field  Programmable  Gate  Array（フィールド・プログラム可能なゲート・アレイ）」）コンポーネントまたはASIC（「Application-Specific  Integrated  Circuit（特定用途向け集積回路）」）コンポーネントにおけるハードウェアにおいて実装されることができる。
【０１４７】
ある代替的な実施形態では、先述した方法の段階の一部または全部が、図８に開示したもののような、メモリ・ユニットおよび処理ユニットを有する電子デバイスで実行されることができる。
【０１４８】
ある種のモデル（一般的なヴァイエルシュトラス・モデルを含む）については、中立要素（すなわち、無限遠にある点O）が特殊な扱いを必要とする。これは、初期化段階を十分に適応させることによって回避できる。古典的な左から右へのラダーについては、kn-1＝1と想定して、アルゴリズム３および５において、初期化段階で、forループをi＝n−2において開始し、R0←PおよびR1←Pと置くことができる。
【０１４９】
同様に、右から左へのラダーについては、k0＝1と想定して、アルゴリズム４において、forループをi＝1において開始し、R0←PおよびR1←2.Pと置くことができる。k0＝0のときは、同じことをするが、正しい結果を得るために計算の最後においてPを減算する。
【０１５０】
R＝2.P＋Qの評価のような組み合わされた演算が本技法に基づいて行なうことができることを注意しておくべきである。これは、二つの段階においてできる。まず、T←P＋Qを決定し、次いでP←P＋Tを決定する。点Rが更新された点Pとともに必要とされる場合には、これはiADDU演算の二つの相続く適用によって実行できる：
【０１５１】
【数６８】
2015166867.tif 000070
計算の終わりに点Rを更新された点Q（点Pでなく）とともにほしい場合には、物事はやや複雑になる。これはiADDUの評価およびそれに続くiADDCの評価によって実行できる：
【０１５２】
【数６９】
2015166867.tif 000071
最後に、同型楕円曲線に基づく提案される技法は、本技法の各実行における曲線ランダム化（curve  randomization）のようなサイドチャネル攻撃を防止する技法に準拠することを注意しておくべきである。
【図１】
2015166867.tif 000072
【図２】
2015166867.tif 000073
【図３】
2015166867.tif 000074
【図４】
2015166867.tif 000075
【図５】
2015166867.tif 000076
【図６】
2015166867.tif 000077
【図７】
2015166867.tif 000078
【図８】
2015166867.tif 000079
【外国語明細書】
2015166867000001.pdf