(57)【要約】【課題】スカラー倍算をさらに高速化すること。【解決手段】設定された楕円曲線上の点Ｐについて、設定された長さのビット列が取り得るビット値の組み合わせ毎に、ビット値の組み合わせに応じた楕円曲線上の点Ｐに対するスカラー倍算を実行する演算部１１と、スカラー倍算の結果を記憶する記憶部１２と、を有する情報処理装置１０が提供される。演算部１１は、ヤコビアン座標の１つが共通する楕円曲線上の第１の点Ｐ1と第２の点Ｐ2とを加算する加算演算に基づいてスカラー倍算を実行する。【選択図】図１
2015135363.tif 000002
【特許請求の範囲】
【請求項１】
設定された楕円曲線上の点について、設定された長さのビット列が取り得るビット値の組み合わせ毎に、前記ビット値の組み合わせに応じた前記楕円曲線上の点に対するスカラー倍算を実行する演算部と、
前記スカラー倍算の結果を記憶する記憶部と、
を有し、
前記演算部は、ヤコビアン座標の１つが共通する前記楕円曲線上の第１の点と第２の点とを加算する加算演算に基づいて前記スカラー倍算を実行する
情報処理装置。
【請求項２】
前記演算部は、
前記第１の点と前記第２の点とが異なる点である場合、前記加算演算の中で、前記第１の点と前記第２の点との楕円曲線加算により第３の点を計算すると共に、前記第３の点とヤコビアン座標の１つが共通する前記第１の点の座標を計算し、
前記第１の点と前記第２の点とが同じ点である場合、前記加算演算の中で、前記第１の点の楕円曲線２倍算により第４の点を計算すると共に、前記第４の点とヤコビアン座標の１つが共通する前記第１の点の座標を計算する
請求項１に記載の情報処理装置。
【請求項３】
前記演算部は、設定されたスカラー値と、前記設定された楕円曲線上の点とのスカラー倍算を計算する場合に、前記スカラー値を示すビット列を前記設定された長さの複数のビット列に分け、前記記憶部が記憶する前記スカラー倍算の結果を用いて前記設定されたスカラー値と前記設定された楕円曲線上の点とのスカラー倍算を計算する
請求項１又は２に記載の情報処理装置。
【請求項４】
記憶部を有するコンピュータが、
設定された楕円曲線上の点について、設定された長さのビット列が取り得るビット値の組み合わせ毎に、前記ビット値の組み合わせに応じた前記楕円曲線上の点に対するスカラー倍算を実行する処理、及び前記スカラー倍算の結果を前記記憶部に格納する処理を実行する情報処理方法であり、
前記スカラー倍算を実行する処理において、前記コンピュータが、ヤコビアン座標の１つが共通する前記楕円曲線上の第１の点と第２の点とを加算する加算演算に基づいて前記スカラー倍算を実行する
情報処理方法。
【請求項５】
記憶部を有するコンピュータに、
設定された楕円曲線上の点について、設定された長さのビット列が取り得るビット値の組み合わせ毎に、前記ビット値の組み合わせに応じた前記楕円曲線上の点に対するスカラー倍算を実行する処理、及び前記スカラー倍算の結果を前記記憶部に格納する処理を実行させるプログラムであり、
前記スカラー倍算を実行する処理において、前記コンピュータに、ヤコビアン座標の１つが共通する前記楕円曲線上の第１の点と第２の点とを加算する加算演算に基づいて前記スカラー倍算を実行させる
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、及びプログラムに関する。
【背景技術】
【０００２】
近年、様々な場面で暗号処理が利用されている。例えば、ネットワーク上を流れるデータ、スマートカードに格納された電子マネー情報、記録メディアに記録されたコンテンツデータなどに対する暗号化、復号、或いは、デジタル署名の処理を行う際に暗号処理が利用されている。暗号には、大きく分けて共通鍵暗号と公開鍵暗号とがある。共通鍵暗号は、暗号化と復号とで同じ鍵を利用する。一方、公開鍵暗号は、暗号化と復号とで異なる鍵を利用する。公開鍵暗号方式としては、例えば、ＲＳＡ暗号や楕円曲線暗号などがある。
【０００３】
ＲＳＡ暗号は、素因数分解の困難性を安全性の根拠とする暗号である。一方、楕円曲線暗号は、楕円曲線上で定義された加法群の離散対数問題（楕円曲線離散対数問題）の困難性を安全性の根拠とする暗号である。楕円曲線暗号に係る暗号化及び復号の処理には、楕円曲線スカラー倍算（以下、スカラー倍算）と呼ばれる演算が含まれる。スカラー倍算は、楕円曲線上の点Ｐ及びスカラー値ｄ（ｄは自然数）を入力として「ｄ×Ｐ＝Ｐ＋Ｐ＋…＋Ｐ」を出力する演算である。
【０００４】
楕円曲線暗号は、ＲＳＡ暗号に比べて短い鍵長で同等の安全性を確保できる。そのため、楕円曲線暗号に係る処理は、ＲＳＡ暗号に比べて低い処理能力で実行可能であり、小型の組み込みデバイスなどへの実装が広く検討されている。また、楕円曲線暗号に係る処理の更なる効率化について、いくつかの研究成果が報告されている。例えば、楕円曲線上の点をヤコビアン座標に変換してからスカラー倍算を行う方法が提案されている。また、ヤコビアン座標のＺ座標が同じ楕円曲線上の点同士を加算する方法が提案されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】H.Cohen, A.Miyaji, and T.Ono, “Efficient Elliptic Curve Exponentiation Using Mixed Coordinates”, Asiacrypt 1998, Lecture Notes in Computer Science vol.1514, pp.51-65, Springer-Verlag, 1998.
【非特許文献２】N.Meloni, “New Point Addition Formulae for ECC Applications”, WAIFI 2007, LNCS 4547, pp.189-201, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記の方法を適用することで適用前に比べてスカラー倍算が高速化される。しかし、スカラー倍算の更なる高速化が達成されれば、楕円曲線暗号の仕組みを実装可能なデバイスが増え、楕円曲線暗号の普及がさらに拡大すると期待される。
【０００７】
そこで、１つの側面によれば、本発明の目的は、スカラー倍算をさらに高速化することが可能な情報処理装置、情報処理方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
本開示の１つの側面によれば、設定された楕円曲線上の点について、設定された長さのビット列が取り得るビット値の組み合わせ毎に、ビット値の組み合わせに応じた楕円曲線上の点に対するスカラー倍算を実行する演算部と、スカラー倍算の結果を記憶する記憶部と、を有し、演算部は、ヤコビアン座標の１つが共通する楕円曲線上の第１の点と第２の点とを加算する加算演算に基づいてスカラー倍算を実行する情報処理装置が提供される。
【０００９】
また、本開示の他の１つの側面によれば、記憶部を有するコンピュータが、設定された楕円曲線上の点について、設定された長さのビット列が取り得るビット値の組み合わせ毎に、ビット値の組み合わせに応じた楕円曲線上の点に対するスカラー倍算を実行する処理、及びスカラー倍算の結果を記憶部に格納する処理を実行する情報処理方法であり、スカラー倍算を実行する処理において、コンピュータが、ヤコビアン座標の１つが共通する楕円曲線上の第１の点と第２の点とを加算する加算演算に基づいてスカラー倍算を実行する情報処理方法が提供される。
【００１０】
また、本開示の他の１つの側面によれば、記憶部を有するコンピュータに、設定された楕円曲線上の点について、設定された長さのビット列が取り得るビット値の組み合わせ毎に、ビット値の組み合わせに応じた楕円曲線上の点に対するスカラー倍算を実行する処理、及びスカラー倍算の結果を記憶部に格納する処理を実行させるプログラムであり、スカラー倍算を実行する処理において、コンピュータに、ヤコビアン座標の１つが共通する楕円曲線上の第１の点と第２の点とを加算する加算演算に基づいてスカラー倍算を実行させるプログラムが提供される。
【発明の効果】
【００１１】
本発明によれば、スカラー倍算をさらに高速化することが可能になる。
【図面の簡単な説明】
【００１２】
【図１】第１実施形態に係る情報処理装置の一例を示した図である。
【図２】第２実施形態に係るシステムの一例を示した図である。
【図３】楕円曲線暗号の適用例（楕円曲線エルガマル暗号方式）について説明するための図である。
【図４】第２実施形態に係る送信装置の機能を実現することが可能なハードウェアの例を示した図である。
【図５】楕円曲線加算ＥＣＡＤＤの定義について説明するための図である。
【図６】楕円曲線２倍算ＥＣＤＢＬの定義について説明するための図である。
【図７】ヤコビアン座標における楕円曲線加算ＥＣＡＤＤの計算方法について説明するためのフロー図である。
【図８】ヤコビアン座標における楕円曲線２倍算ＥＣＤＢＬの計算方法について説明するためのフロー図である。
【図９】バイナリ法によるスカラー倍算の計算について説明するためのフロー図である。
【図１０】スカラー倍算の計算（ウィンドウ法）について説明するための第１のフロー図である。
【図１１】スカラー倍算の計算（ウィンドウ法）について説明するための第２のフロー図である。
【図１２】第２実施形態に係る送信装置が有する機能の例を示したブロック図である。
【図１３】第２実施形態に係るスカラー倍算の計算について説明するための第１のフロー図である。
【図１４】第２実施形態に係るスカラー倍算の計算について説明するための第２のフロー図である。
【図１５】第２実施形態に係るスカラー倍算の計算について説明するための第３のフロー図である。
【図１６】第２実施形態に係る受信装置が有する機能の例を示したブロック図である。
【発明を実施するための形態】
【００１３】
以下に添付図面を参照しながら、本発明の実施形態について説明する。なお、本明細書及び図面において実質的に同一の機能を有する要素については、同一の符号を付することにより重複説明を省略する場合がある。
【００１４】
＜１．第１実施形態＞
図１を参照しながら、第１実施形態について説明する。なお、図１は、第１実施形態に係る情報処理装置の一例を示した図である。
【００１５】
図１に示すように、情報処理装置１０は、演算部１１及び記憶部１２を有する。情報処理装置１０は、第１実施形態に係る情報処理装置の一例である。
演算部１１は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサである。但し、演算部１１は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの電子回路であってもよい。また、記憶部１２は、ＲＡＭ（Random Access Memory）などの揮発性記憶装置、或いは、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性記憶装置である。演算部１１は、例えば、記憶部１２又は他のメモリに記憶されたプログラムを実行する。
【００１６】
演算部１１は、設定された楕円曲線上の点Ｐについて、設定された長さのビット列が取り得るビット値の組み合わせ毎に、ビット値の組み合わせに応じた楕円曲線上の点Ｐに対するスカラー倍算を実行する。また、記憶部１２は、スカラー倍算の結果を記憶する。但し、演算部１１は、ヤコビアン座標の１つが共通する楕円曲線上の第１の点Ｐ1と第２の点Ｐ2とを加算する加算演算に基づいてスカラー倍算を実行する。ヤコビアン座標の１つが共通する場合には加算演算の演算量が削減されるため、スカラー倍算が高速化される。
【００１７】
図１の例では、ビット列の長さが２ビットに設定されている。この場合、演算部１１は、先頭１ビット目から順にビット列のビット値を参照する。なお、演算部１１は、ビット列の末尾１ビット目から順にビット列のビット値を参照してもよい。まず、演算部１１は、一時変数Ｔに無限遠点∞を設定する。次いで、演算部１１は、１ビット目のビット値を参照し、ビット値が０である場合には一時変数Ｔを変更せず、ビット値が１である場合には一時変数Ｔに点Ｐを加算（楕円曲線加算「＋」）する。
【００１８】
次いで、演算部１１は、２ビット目のビット値を参照し、一時変数Ｔを２倍（楕円曲線２倍算「×２」）する。次いで、演算部１１は、２ビット目のビット値を参照し、ビット値が０である場合には一時変数Ｔを変更せず、ビット値が１である場合には一時変数Ｔに点Ｐを加算する。そして、演算部１１は、最終的に得られた一時変数Ｔを記憶部１２に格納する。
【００１９】
例えば、ビット列が「００」の場合、一時変数Ｔは∞となるため、演算部１１は、ビット列「００」に対応するスカラー倍算の結果Ｗ［０］として∞を記憶部１２に格納する。また、ビット列が「０１」の場合、一時変数ＴはＰとなるため、演算部１１は、ビット列「０１」に対応するスカラー倍算の結果Ｗ［１］としてＰを記憶部１２に格納する。
【００２０】
また、ビット列が「１０」の場合、一時変数Ｔは２×Ｐとなるため（（∞＋Ｐ）×２＝２×Ｐ）、演算部１１は、ビット列「１０」に対応するスカラー倍算の結果Ｗ［２］として２×Ｐを記憶部１２に格納する。また、ビット列が「１１」の場合、一時変数Ｔは３×Ｐとなるため（（∞＋Ｐ）×２＋Ｐ＝３×Ｐ）、演算部１１は、ビット列「１１」に対応するスカラー倍算の結果Ｗ［３］として３×Ｐを記憶部１２に格納する。
【００２１】
但し、演算部１１は、第１の点Ｐ1と第２の点Ｐ2とを加算する楕円曲線加算「＋」を実行する際に、ヤコビアン座標の１つ（Ｚ座標）が共通する第１の点Ｐ1と第２の点Ｐ2との楕円曲線加算ＥＣＡＤＤcoZにより第３の点Ｐ3を計算する。さらに、演算部１１は、楕円曲線加算ＥＣＡＤＤcoZの実行時に、第３の点Ｐ3とヤコビアン座標の１つ（Ｚ3）が共通する第１の点Ｐ1の座標を計算する。
【００２２】
上記のように、楕円曲線加算ＥＣＡＤＤcoZの実行により、ヤコビアン座標の１つ（Ｚ3）が共通する第１の点Ｐ1と第３の点Ｐ3とが得られる。そのため、第１の点Ｐ1と第３の点Ｐ3とを楕円曲線加算「＋」する場合に、楕円曲線加算ＥＣＡＤＤcoZを適用することができる。その結果、楕円曲線加算「＋」が高速化される。
【００２３】
また、演算部１１は、第１の点Ｐ1を２倍する楕円曲線２倍算「×２」（ＥＣＤＢＬcoZ）を実行して第４の点Ｐ4を計算する際、第４の点Ｐ4とヤコビアン座標の１つ（Ｚ4）が共通する第１の点Ｐ1の座標を計算する。楕円曲線２倍算ＥＣＤＢＬcoZの実行時にヤコビアン座標の１つ（Ｚ4）が共通する第１の点Ｐ1と第４の点Ｐ4とが得られると、第１の点Ｐ1と第４の点Ｐ4とを楕円曲線加算「＋」する場合に、楕円曲線加算ＥＣＡＤＤcoZを適用することができる。その結果、楕円曲線加算「＋」が高速化される。
【００２４】
演算部１１は、設定されたスカラー値ｄと設定された楕円曲線上の点Ｐとのスカラー倍算を計算する場合に、スカラー値ｄを示すビット列を、設定された長さの複数のビット列に分ける。そして、演算部１１は、記憶部１２が記憶するスカラー倍算の結果を用いて、設定されたスカラー値ｄと、設定された楕円曲線上の点Ｐとのスカラー倍算を計算する。
【００２５】
図１の例では、スカラー値ｄが２３に設定されている。この場合、スカラー値ｄは、ビット列０１０１１１と表現される。演算部１１は、このビット列を２ビットの長さを有する３つのビット列「０１」、「０１」、「１１」に分けてスカラー倍算を計算する。ビット列「０１」に対するスカラー倍算の結果Ｗ［１］（Ｐ）は、記憶部１２に格納されている。また、ビット列「１１」に対するスカラー倍算の結果Ｗ［３］（３×Ｐ）は、記憶部１２に格納されている。そのため、演算部１１は、Ｗ［１］、Ｗ［３］を利用してスカラー倍点ｄ×Ｐを求めるスカラー倍算を実行する。
【００２６】
上記のように、予め短いビット列についてスカラー倍算を計算しておき、その計算結果を利用して長いビット列についてスカラー倍算を計算することで、計算結果の使い回しができ、長いビット列に対するスカラー倍算を効率的に実行することができる。また、短いビット列に対するスカラー倍算の計算時に、上述した楕円曲線加算ＥＣＡＤＤcoZを有効に利用できることで演算量を削減することができる。上述したスカラー倍算の計算方法を楕円曲線暗号の暗号化処理や復号処理に適用することで、楕円曲線暗号に係る処理の高速化が実現される。
【００２７】
以上、第１実施形態について説明した。
＜２．第２実施形態＞
次に、第２実施形態について説明する。第２実施形態は、楕円曲線暗号に係る暗号化処理及び復号処理の中で実行されるスカラー倍算の処理を効率化する手法に関する。
【００２８】
［２−１．楕円曲線暗号方式について］
楕円曲線暗号方式について説明する。楕円曲線暗号方式は、楕円曲線上のベースポイントＰ及びスカラー倍点ｄ×Ｐからスカラー値ｄを求める問題（楕円曲線離散対数問題）の解答困難性に安全性の根拠をおく暗号方式の総称である。
【００２９】
（システムの例）
以下の説明において、簡単のために図２に例示したシステムを想定する。なお、図２は、第２実施形態に係るシステムの一例を示した図である。但し、第２実施形態に係る技術の適用範囲はこれに限定されず、楕円曲線暗号方式を採用する任意のシステムに対して適用可能である。例えば、記録媒体へ記録されるデータを秘匿するために楕円曲線暗号を利用するシステムなどへの適用も可能である。
【００３０】
図２に示すように、第２実施形態に係るシステムは、送信装置１００及び受信装置２００を含む。送信装置１００は、ネットワークＮＷを介して受信装置２００に接続されている。送信装置１００は、平文で記述されたメッセージを暗号化して暗号文を生成し、その暗号文を受信装置２００へと送信する。一方、受信装置２００は、送信装置１００から受信した暗号文を復号して平文で記述されたメッセージを復元する。なお、送信装置１００は、暗号化装置の一例である。また、受信装置２００は、復号装置の一例である。
【００３１】
（楕円曲線暗号の適用例：楕円曲線エルガマル暗号方式）
ここで、図３を参照しながら、楕円曲線エルガマル暗号方式の場合を例に挙げて送信装置１００及び受信装置２００の動作について説明する。なお、図３は、楕円曲線暗号の適用例（楕円曲線エルガマル暗号方式）について説明するための図である。
【００３２】
図３の例では、楕円曲線をＥ、楕円曲線Ｅ上のベースポイントをＰ、公開鍵をＳ、秘密鍵をｓ、ランダムに生成されたスカラー（乱数）をｒ、メッセージである平文をＭと表記している。但し、公開鍵Ｓは、秘密鍵ｓとベースポイントＰとのスカラー倍算（Ｓ＝ｓ×Ｐ）により定義されている。また、平文Ｍは、楕円曲線Ｅ上の点で表現されている。送信装置１００は、ベースポイントＰ及び公開鍵Ｓの情報を保持している。受信装置２００は、秘密鍵ｓの情報を保持している。この状況で、送信装置１００から受信装置２００へと平文Ｍを送信する場合について考える。
【００３３】
送信装置１００は、ランダムにスカラーｒを生成する（Ｓ１１）。次いで、送信装置１００は、スカラーｒとベースポイントＰとのスカラー倍算を実行し、そのスカラー倍算の結果Ｒ（Ｒ＝ｒ×Ｐ）を計算する（Ｓ１２）。次いで、送信装置１００は、スカラーｒと公開鍵Ｓとのスカラー倍算を実行し、そのスカラー倍算の結果に平文Ｍを加算して暗号文Ｃ（Ｃ＝ｒ×Ｓ＋Ｍ）を計算する（Ｓ１３）。そして、送信装置１００は、Ｒ、Ｃを受信装置２００へと送信する（Ｓ１４）。
【００３４】
Ｒ、Ｃを受信した受信装置２００は、秘密鍵ｓとＲとのスカラー倍算を実行してｓ×Ｒを計算する（Ｓ１５）。次いで、受信装置２００は、Ｃからｓ×Ｒを減算して（Ｃ−ｓ×Ｒ）を計算する（Ｓ１６）。下記の式（１）により、（Ｃ−ｓ×Ｒ）は、平文Ｍに等しい。つまり、受信装置２００は、暗号文Ｃから平文Ｍを得る。楕円曲線エルガマル暗号方式では、図３に例示したアルゴリズムにより平文Ｍの送受信が行われる。なお、ここで示した暗号化及び復号のロジックを変形してデジタル署名方式などへ応用することもできる。
【００３５】
Ｃ−ｓ×Ｒ＝（ｒ×Ｓ＋Ｍ）−ｓ×Ｒ
＝（ｒ×ｓ×Ｐ＋Ｍ）−ｓ×ｒ×Ｐ
＝Ｍ
…（１）
以上、楕円曲線暗号方式について説明した。
【００３６】
［２−２．ハードウェア］
上記のような送信装置１００の機能は、例えば、図４に例示したハードウェアを利用して実現可能である。つまり、送信装置１００が有する機能は、コンピュータプログラムを用いて図４に示すハードウェアを制御することにより実現される。図４は、第２実施形態に係る送信装置の機能を実現することが可能なハードウェアの例を示した図である。
【００３７】
図４に示すように、このハードウェアは、主に、ＣＰＵ９０２と、ＲＯＭ（Read Only Memory）９０４と、ＲＡＭ９０６と、ホストバス９０８と、ブリッジ９１０とを有する。さらに、このハードウェアは、外部バス９１２と、インターフェース９１４と、入力部９１６と、出力部９１８と、記憶部９２０と、ドライブ９２２と、接続ポート９２４と、通信部９２６とを有する。
【００３８】
ＣＰＵ９０２は、例えば、演算処理装置又は制御装置として機能し、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ＲＯＭ９０４は、ＣＰＵ９０２に読み込まれるプログラムや演算に用いるデータなどを格納する記憶装置の一例である。ＲＡＭ９０６には、例えば、ＣＰＵ９０２に読み込まれるプログラムや、そのプログラムを実行する際に変化する各種パラメータなどが一時的又は永続的に格納される。
【００３９】
これらの要素は、例えば、高速なデータ伝送が可能なホストバス９０８を介して相互に接続される。一方、ホストバス９０８は、例えば、ブリッジ９１０を介して比較的データ伝送速度が低速な外部バス９１２に接続される。また、入力部９１６としては、例えば、マウス、キーボード、タッチパネル、タッチパッド、ボタン、スイッチ、及びレバーなどが用いられる。さらに、入力部９１６としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラが用いられることもある。
【００４０】
出力部９１８としては、例えば、ＣＲＴ（Cathode Ray Tube）、ＬＣＤ（Liquid Crystal Display）、ＰＤＰ（Plasma Display Panel）、又はＥＬＤ（Electro-Luminescence Display）などのディスプレイ装置が用いられる。また、出力部９１８として、スピーカやヘッドホンなどのオーディオ出力装置、又はプリンタなどが用いられることもある。つまり、出力部９１８は、情報を視覚的又は聴覚的に出力することが可能な装置である。
【００４１】
記憶部９２０は、各種のデータを格納するための装置である。記憶部９２０としては、例えば、ＨＤＤなどの磁気記憶デバイスが用いられる。また、記憶部９２０として、ＳＳＤ（Solid State Drive）やＲＡＭディスクなどの半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイスなどが用いられてもよい。
【００４２】
ドライブ９２２は、着脱可能な記録媒体であるリムーバブル記録媒体９２８に記録された情報を読み出し、又はリムーバブル記録媒体９２８に情報を書き込む装置である。リムーバブル記録媒体９２８としては、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリなどが用いられる。
【００４３】
接続ポート９２４は、例えば、ＵＳＢ（Universal Serial Bus）ポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ（Small Computer System Interface）、ＲＳ−２３２Ｃポート、又は光オーディオ端子など、外部接続機器９３０を接続するためのポートである。外部接続機器９３０としては、例えば、プリンタなどが用いられる。
【００４４】
通信部９２６は、ネットワーク９３２に接続するための通信デバイスである。通信部９２６としては、例えば、有線又は無線ＬＡＮ（Local Area Network）用の通信回路、ＷＵＳＢ（Wireless USB）用の通信回路、光通信用の通信回路やルータ、ＡＤＳＬ（Asymmetric Digital Subscriber Line）用の通信回路やルータ、携帯電話ネットワーク用の通信回路などが用いられる。通信部９２６に接続されるネットワーク９３２は、有線又は無線により接続されたネットワークであり、例えば、インターネット、ＬＡＮ、放送網、衛星通信回線などを含む。
【００４５】
以上、送信装置１００の機能を実現可能なハードウェアについて説明した。なお、図４に示したハードウェアを用いることで、受信装置２００の機能も実現可能である。従って、受信装置２００の機能を実現可能なハードウェアについては説明を省略する。
【００４６】
［２−３．スカラー倍算の計算方法について］
次に、スカラー倍算の計算方法について説明する。既に説明したように、楕円曲線暗号方式に係る暗号化処理及び復号処理にはスカラー倍算が利用される。以下、楕円曲線加算ＥＣＡＤＤ及び楕円曲線２倍算ＥＣＤＢＬについて説明し、さらに、バイナリ法及びウィンドウ法と呼ばれるスカラー倍算の計算方法について説明する。
【００４７】
（楕円曲線Ｅと逆元−Ｐ）
楕円曲線加算ＥＣＡＤＤ及び楕円曲線２倍算ＥＣＤＢＬに用いる楕円曲線Ｅは、ｐを５以上の素数、ｍを１以上の整数とした場合に、要素数ｐmの有限体ＧＦ（ｐm）上で下記の式（２）を満たす点（ｘ，ｙ）の集合に無限遠点∞を加えた集合として定義される。なお、下記の式（２）に含まれる係数ａ、ｂは、有限体ＧＦ（ｐm）の要素である。
【００４８】
Ｅ：ｙ2＝ｘ3＋ａ×ｘ＋ｂ
…（２）
また、楕円曲線Ｅ上の点Ｐに対し、下記の式（３）及び式（４）により点Ｐの逆元−Ｐが定義される。
【００４９】
Ｐ＝∞  ならば  −Ｐ＝∞
…（３）
Ｐ＝（ｘ，ｙ）≠∞  ならば  −Ｐ＝（ｘ，−ｙ）
…（４）
（加算法則）
楕円曲線Ｅ上の点Ｐ1、Ｐ2を加算する演算について考える。点Ｐ1、Ｐ2の和Ｐ3（Ｐ3＝Ｐ1＋Ｐ2）は、下記の式（５）〜式（８）により定義される。但し、Ｐ1＝（ｘ1，ｙ1）、Ｐ2＝（ｘ2，ｙ2）、Ｐ3＝（ｘ3，ｙ3）である。但し、下記の式（８）に含まれるλ、νは、Ｐ1≠Ｐ2のとき下記の式（９）で定義され、Ｐ1＝Ｐ2のとき下記の式（１０）で定義される。
【００５０】
Ｐ1＝∞  ならば  Ｐ3＝Ｐ2
…（５）
Ｐ2＝∞  ならば  Ｐ3＝Ｐ1
…（６）
Ｐ1＝−Ｐ2  ならば  Ｐ3＝∞
…（７）
Ｐ1≠−Ｐ2  ならば  ｘ3＝λ2−ｘ1−ｘ2、ｙ3＝−λ×ｘ3−ν
…（８）
・Ｐ1≠Ｐ2のとき
λ＝（ｙ2−ｙ1）／（ｘ2−ｘ1）
ν＝（ｙ1×ｘ2−ｙ2×ｘ1）／（ｘ2−ｘ1）
…（９）
・Ｐ1＝Ｐ2のとき
λ＝（３×ｘ12＋ａ）／（２×ｙ1）
ν＝（−ｘ13＋ａ×ｘ1＋２×ｂ）／（２×ｙ1）
…（１０）
楕円曲線加算ＥＣＡＤＤは、Ｐ1≠Ｐ2のときにＰ1＋Ｐ2を計算する演算処理を言う。楕円曲線２倍算ＥＣＤＢＬは、Ｐ1＝Ｐ2のときにＰ1＋Ｐ2（＝２×Ｐ1）を計算する演算処理を言う。楕円曲線加算ＥＣＡＤＤ及び楕円曲線２倍算ＥＣＤＢＬは、有限体ＧＦ（ｐm）上の加算、減算、乗算、除算、平方算、逆元計算の組み合わせである。
【００５１】
なお、楕円曲線加算ＥＣＡＤＤは、図５に示すように、楕円曲線Ｅ上の点Ｐ1と点Ｐ2とを結ぶ直線Ｌ1が楕円曲線Ｅと交わる点をｘ軸で折り返した位置にある点Ｐ3を求める処理である。一方、楕円曲線２倍算ＥＣＤＢＬは、図６に示すように、楕円曲線Ｅ上の点Ｐ1の接線Ｌ3と楕円曲線Ｅとが交わる点をｘ軸で折り返した位置にある点Ｐ3を求める処理である。
【００５２】
なお、図５は、楕円曲線加算ＥＣＡＤＤの定義について説明するための図である。図５の例は、ａ＝−１、ｂ＝０の場合である。直線Ｌ2は、ｙ軸に平行な直線である。また、図６は、楕円曲線２倍算ＥＣＤＢＬの定義について説明するための図である。図６の例は、ａ＝−１、ｂ＝０の場合である。直線Ｌ4は、ｙ軸に平行な直線である。
【００５３】
ところで、楕円曲線加算ＥＣＡＤＤ、楕円曲線２倍算ＥＣＤＢＬ、スカラー倍算の計算時間は、多くの場合、有限体ＧＦ（ｐm）における乗算、平方算、逆元計算の計算時間の和によって見積もられる。これは有限体ＧＦ（ｐm）上の加算、減算の計算時間が、他の演算の計算時間に比べて無視できる程度に短いからである。有限体ＧＦ（ｐm）上の逆元計算は、乗算、平方算に比べて計算時間が長くかかる。そのため、第２実施形態では、楕円曲線Ｅ上の点をヤコビアン座標で表現し、逆元計算の回数を減らして計算時間を短縮する方法を採用する。
【００５４】
（ヤコビアン座標）
ヤコビアン座標において、有限体ＧＦ（ｐm）における楕円曲線Ｅの点（ｘ，ｙ）は、３つの要素を組み合わせた座標（Ｘ：Ｙ：Ｚ）で表現される。但し、ｒ≠０である有限体ＧＦ（ｐm）の要素ｒに対し、（Ｘ：Ｙ：Ｚ）と（ｒ2×Ｘ：ｒ3×Ｙ：ｒ×Ｚ）とは同じ点を表す。また、ｘ＝Ｘ／Ｚ2、ｙ＝Ｙ／Ｚ3である。この関係を上記の式（２）に代入すると、ヤコビアン座標で表現した楕円曲線Ｅは、下記の式（１１）のように表現される。なお、無限遠点∞は、∞＝（０：１：０）となる。
【００５５】
Ｅ：Ｙ2×Ｚ＝Ｘ3＋ａ×Ｘ×Ｚ4＋ｂ×Ｚ6
…（１１）
ここで、図７を参照しながら、ヤコビアン座標における楕円曲線加算ＥＣＡＤＤの計算方法について説明する。図７は、ヤコビアン座標における楕円曲線加算ＥＣＡＤＤの計算方法について説明するためのフロー図である。なお、説明の都合上、送信装置１００が楕円曲線加算ＥＣＡＤＤを実行する場合について説明するが、受信装置２００が楕円曲線加算ＥＣＡＤＤを実行する場合も同様である。
【００５６】
楕円曲線Ｅ上の点Ｐ1、Ｐ2（Ｐ1≠Ｐ2）を加算して点Ｐ３を求める楕円曲線加算ＥＣＡＤＤについて考える。但し、Ｐ1＝（Ｘ1：Ｙ1：Ｚ1）、Ｐ2＝（Ｘ2：Ｙ2：Ｚ2）、Ｐ3＝（Ｘ3：Ｙ3：Ｚ3）である。
【００５７】
図７に示すように、送信装置１００は、Ｘ1×Ｚ22を計算して一時変数Ｕ1に設定し、Ｘ2×Ｚ12を計算して一時変数Ｕ2に設定する（Ｓ２１）。次いで、送信装置１００は、Ｙ1×Ｚ23を計算して一時変数Ｖ1に設定し、Ｙ2×Ｚ13を計算して一時変数Ｖ2に設定する（Ｓ２２）。Ｓ２１、Ｓ２２の処理は入れ替え可能である。次いで、送信装置１００は、Ｕ2からＵ1を減算して一時変数Ｈに設定し、Ｖ2からＶ1を減算して一時変数Ｑに設定する（Ｓ２３）。
【００５８】
次いで、送信装置１００は、Ｑ2−Ｈ3−２Ｕ1×Ｈを計算してＸ3に設定する（Ｓ２４）。次いで、送信装置１００は、Ｑ×（Ｕ1×Ｈ2−Ｘ3）−Ｖ1×Ｈ3を計算してＹ3に設定する（Ｓ２５）。次いで、送信装置１００は、Ｚ1×Ｚ2×Ｈを計算してＺ3に設定する（Ｓ２６）。Ｓ２６の処理は、Ｓ２４、Ｓ２５の処理と入れ替え可能である。Ｓ２１〜Ｓ２６の処理により、点Ｐ3の座標Ｘ3、Ｙ3、Ｚ3が得られる。
【００５９】
次に、図８を参照しながら、ヤコビアン座標における楕円曲線２倍算ＥＣＤＢＬの計算方法について説明する。図８は、ヤコビアン座標における楕円曲線２倍算ＥＣＤＢＬの計算方法について説明するためのフロー図である。なお、説明の都合上、送信装置１００が楕円曲線２倍算ＥＣＤＢＬを実行する場合について説明するが、受信装置２００が楕円曲線２倍算ＥＣＤＢＬを実行する場合も同様である。
【００６０】
図８に示すように、送信装置１００は、３×Ｘ12＋ａ×Ｚ14を計算して一時変数Ｑに設定する（Ｓ３１）。次いで、送信装置１００は、４×Ｘ1×Ｙ12を計算して一時変数Ｖに設定する（Ｓ３２）。Ｓ３１、Ｓ３２の処理は入れ替え可能である。次いで、送信装置１００は、−２×Ｖ＋Ｑ2を計算して一時変数Ｔに設定する（Ｓ３３）。
【００６１】
次いで、送信装置１００は、一時変数ＴをＸ3に設定する（Ｓ３４）。次いで、送信装置１００は、−８×Ｙ14＋Ｑ×（Ｖ−Ｔ）を計算してＹ3に設定する（Ｓ３５）。次いで、送信装置１００は、２×Ｙ1×Ｚ1を計算してＺ3に設定する（Ｓ３６）。Ｓ３４、Ｓ３５、Ｓ３６の処理は相互に入れ替え可能である。Ｓ３１〜Ｓ３６の処理により、点Ｐ3の座標Ｘ3、Ｙ3、Ｚ3が得られる。
【００６２】
上記のようにしてヤコビアン座標を用いた場合、楕円曲線加算ＥＣＡＤＤの計算時間は１２Ｍ＋２Ｓとなる。また、楕円曲線２倍算ＥＣＤＢＬの計算時間は７Ｍ＋５Ｓになる。但し、１Ｍは、要素数ｐmの有限体ＧＦ（ｐm）上で乗算を１回計算するのにかかる計算時間である。また、１Ｓは、要素数ｐmの有限体ＧＦ（ｐm）上で平方算を１回計算するのにかかる計算時間である。なお、Ｚ座標が１の場合、楕円曲線加算ＥＣＡＤＤの計算時間は８Ｍ＋３Ｓとなる。
【００６３】
（バイナリ法によるスカラー倍算の計算）
次に、図９を参照しながら、バイナリ法によるスカラー倍算の計算について説明する。バイナリ法は、スカラー倍算に含まれる楕円曲線加算ＥＣＡＤＤと楕円曲線２倍算ＥＣＤＢＬとの組み合わせを定める方法の１つである。
【００６４】
なお、図９は、バイナリ法によるスカラー倍算の計算について説明するためのフロー図である。また、図９において、アルファベットの小文字はスカラー値を表し、大文字は楕円曲線Ｅ上の点を表す。また、説明の都合上、送信装置１００がスカラー倍算を実行する場合について説明するが、受信装置２００がスカラー倍算を実行する場合も同様である。
【００６５】
いま、ｎビットのスカラー値ｄが与えられた場合に、楕円曲線Ｅ上の点Ｐに対するスカラー倍算ｄ×Ｐを計算するアルゴリズムについて考える。スカラー値ｄは、下記の式（１２）に示すように、ｎ個のビット値ｄ［ｉ］（下位ｉビット目の値）を用いて表現できる。ビット値ｄ［ｉ］は０又は１である。また、ｄ［ｎ−１］＝１であるとする。
【００６６】
ｄ＝ｄ［ｎ−１］×２n-1＋ｄ［ｎ−２］×２n-2＋…＋ｄ［０］×２0
…（１２）
図９に示すように、送信装置１００は、楕円曲線Ｅ上の点Ｐを一時変数Ｔに設定する（Ｓ４１）。次いで、送信装置１００は、ｉをｎ−２に設定する（Ｓ４２）。Ｓ４１、Ｓ４２の処理は入れ替え可能である。次いで、送信装置１００は、ｉが０より小さいか否かを判定する（Ｓ４３）。ｉが０より小さい場合、処理はＳ４８へと進む。一方、ｉが０より小さくない場合、処理はＳ４４へと進む。
【００６７】
処理がＳ４４へと進んだ場合、送信装置１００は、一時変数Ｔに対して楕円曲線２倍算ＥＣＤＢＬを実行し、その結果を一時変数Ｔに設定する（Ｓ４４）。次いで、送信装置１００は、下位ｉビット目のビット値ｄ［ｉ］が１であるか否かを判定する（Ｓ４５）。ビット値ｄ［ｉ］が１である場合、処理はＳ４６へと進む。一方、ビット値ｄ［ｉ］が１でない場合（０である場合）、処理はＳ４７へと進む。
【００６８】
処理がＳ４６へと進んだ場合、送信装置１００は、一時変数Ｔと楕円曲線Ｅ上の点Ｐとを加算する楕円曲線加算ＥＣＡＤＤを実行し、その結果を一時変数Ｔに設定する（Ｓ４６）。Ｓ４６の処理が完了すると、処理はＳ４７へと進む。処理がＳ４７へと進んだ場合、送信装置１００は、ｉを１減らす（Ｓ４７）。Ｓ４７の処理が完了すると、処理はＳ４３へと進む。
【００６９】
処理がＳ４８へと進んだ場合、送信装置１００は、一時変数Ｔをスカラー倍算ｄ×Ｐの結果として出力する（Ｓ４８）。Ｓ４８の処理が完了すると、図９に示した一連の処理は終了する。
【００７０】
（例：ｎ＝５、ｄ＝２１の場合）
ｎ＝５、ｄ＝２１の場合、スカラー値ｄは、下記の式（１３）のように表現できる。
ｄ＝２１
＝１６＋４＋１
＝１×２4＋０×２3＋１×２2＋０×２1＋１×２0
＝（１０１０１）ヒ゛ット列
…（１３）
Ｓ４１の処理では、一時変数Ｔに楕円曲線Ｅ上の点Ｐが設定される。次いで、ｉ＝３，２，１，０についてＳ４４、Ｓ４５、Ｓ４６の処理が実行される。ｉが３の場合について、送信装置１００は、一時変数Ｔの楕円曲線２倍算ＥＣＤＢＬを実行し、その結果を一時変数Ｔに設定する（Ｓ４４）。Ｓ４４の処理後、一時変数Ｔは２×Ｐとなる。次いで、送信装置１００は、ビット値ｄ［３］が１であるか否かを判定する（Ｓ４５）。上記の式（１３）に示したようにｄ［３］＝０であるため、送信装置１００は、Ｓ４６の処理をスキップし、ｉを２に更新する。
【００７１】
次に、送信装置１００は、ｉが２の場合について、送信装置１００は、一時変数Ｔの楕円曲線２倍算ＥＣＤＢＬを実行し、その結果を一時変数Ｔに設定する（Ｓ４４）。Ｓ４４の処理後、一時変数Ｔは４×Ｐとなる。次いで、送信装置１００は、ビット値ｄ［２］が１であるか否かを判定する（Ｓ４５）。
【００７２】
上記の式（１３）に示したようにｄ［２］＝１であるため、送信装置１００は、一時変数Ｔと楕円曲線Ｅ上の点Ｐとを加算する楕円曲線加算ＥＣＡＤＤを実行し、その結果を一時変数Ｔに設定する（Ｓ４６）。Ｓ４６の処理後、一時変数Ｔは５×Ｐとなる。そして、送信装置１００は、ｉを１に更新する。
【００７３】
次に、送信装置１００は、ｉが１の場合について、送信装置１００は、一時変数Ｔの楕円曲線２倍算ＥＣＤＢＬを実行し、その結果を一時変数Ｔに設定する（Ｓ４４）。Ｓ４４の処理後、一時変数Ｔは１０×Ｐとなる。次いで、送信装置１００は、ビット値ｄ［１］が１であるか否かを判定する（Ｓ４５）。上記の式（１３）に示したようにｄ［１］＝０であるため、送信装置１００は、Ｓ４６の処理をスキップし、ｉを０に更新する。
【００７４】
次に、送信装置１００は、ｉが０の場合について、送信装置１００は、一時変数Ｔの楕円曲線２倍算ＥＣＤＢＬを実行し、その結果を一時変数Ｔに設定する（Ｓ４４）。Ｓ４４の処理後、一時変数Ｔは２０×Ｐとなる。次いで、送信装置１００は、ビット値ｄ［０］が１であるか否かを判定する（Ｓ４５）。
【００７５】
上記の式（１３）に示したようにｄ［０］＝１であるため、送信装置１００は、一時変数Ｔと楕円曲線Ｅ上の点Ｐとを加算する楕円曲線加算ＥＣＡＤＤを実行し、その結果を一時変数Ｔに設定する（Ｓ４６）。Ｓ４６の処理後、一時変数Ｔは２１×Ｐとなる。この一時変数Ｔがスカラー倍算の結果として出力される。
【００７６】
このようにバイナリ法では、楕円曲線加算ＥＣＡＤＤと楕円曲線２倍算ＥＣＤＢＬの組み合わせによりスカラー倍算が計算される。ビット毎に楕円曲線２倍算ＥＣＤＢＬが実行され、ビット値ｄ［ｉ］が１のときに楕円曲線加算ＥＣＡＤＤがさらに実行される。
【００７７】
スカラー値ｄがランダムに与えられた場合、ｄ［ｉ］＝１となる確率は０．５である。従って、スカラー倍算を計算するのにかかるビット当たりの計算時間ＴｉｍｅＰｅｒＢｉｔは、下記の式（１４）で与えられる。但し、Ｔｉｍｅ（ＥＣＤＢＬ）は、楕円曲線２倍算ＥＣＤＢＬを１回計算するのにかかる計算時間である。また、Ｔｉｍｅ（ＥＣＡＤＤ）は、楕円曲線加算ＥＣＡＤＤを１回計算するのにかかる計算時間である。
【００７８】
ＴｉｍｅＰｅｒＢｉｔ＝Ｔｉｍｅ（ＥＣＤＢＬ）＋０．５×Ｔｉｍｅ（ＥＣＡＤＤ）
…（１４）
ヤコビアン座標を用いた場合、Ｔｉｍｅ（ＥＣＡＤＤ）＝１２Ｍ＋２Ｓ、Ｔｉｍｅ（ＥＣＤＢＬ）＝５Ｍ＋２Ｓとなる。そのため、ＴｉｍｅＰｅｒＢｉｔは、１１Ｍ＋３Ｓとなる。１Ｓ＝０．８Ｍの場合、ＴｉｍｅＰｅｒＢｉｔは１３．４Ｍとなる。例えば、スカラー値ｄが１６０ビットの場合、Ｓ４４以降の処理は１５９回実行される。そのため、スカラー倍算の平均的な計算時間Ｔｉｍｅ（Ａｖｅ）は、１５９×１３．４Ｍ＝２１３０．６Ｍとなる。
【００７９】
（ウィンドウ法によるスカラー倍算の計算）
次に、図１０及び図１１を参照しながら、ウィンドウ法によるスカラー倍算の計算について説明する。
【００８０】
なお、図１０は、スカラー倍算の計算（ウィンドウ法）について説明するための第１のフロー図である。図１１は、スカラー倍算の計算（ウィンドウ法）について説明するための第２のフロー図である。また、図１０及び図１１において、アルファベットの小文字はスカラー値を表し、大文字は楕円曲線Ｅ上の点を表す。また、説明の都合上、送信装置１００がスカラー倍算を実行する場合について説明するが、受信装置２００がスカラー倍算を実行する場合も同様である。
【００８１】
図１０及び図１１には、スカラー値ｄが２１、ウィンドウ幅が４ビットの場合に、スカラー値ｄとベースポイントＰとのスカラー倍算を計算する処理が例示されている。また、スカラー値ｄを表すビット列の長さは、下記の式（１５）に示すように、送信装置１００によりウィンドウ幅の整数倍（この例では８ビット）に調整されているものとする。以下、調整後のビット列の長さをｎ（この例ではｎ＝８）と表記する。
【００８２】
ｄ＝２１
＝０×２7＋０×２6＋０×２5＋１×２4
＋０×２3＋１×２2＋０×２1＋１×２0
＝（０００１０１０１）ヒ゛ット列
…（１５）
図１０に示すように、送信装置１００は、無限遠点∞をＷ［０］に設定する（Ｓ５１）。Ｓ５１の処理は、全てのビット値が０である４ビットのビット列（ウィンドウ）が示すスカラー値とベースポイントＰとのスカラー倍算を実行し、その結果をＷ［０］に設定する処理に相当する。但し、このスカラー倍算の結果が∞になることが予め分かっているため、送信装置１００は、Ｓ５１の処理でＷ［０］に直接∞を設定している。
【００８３】
次いで、送信装置１００は、ベースポイントＰをＷ［１］に設定する（Ｓ５２）。Ｓ５２の処理は、下位１ビット目のビット値が１であり、他の全てのビット値が０である４ビットのビット列（ウィンドウ）が示すスカラー値とベースポイントＰとのスカラー倍算を実行し、その結果をＷ［１］に設定する処理に相当する。但し、このスカラー倍算の結果がＰになることが予め分かっているため、送信装置１００は、Ｓ５２の処理でＷ［１］に直接Ｐを設定している。
【００８４】
次いで、送信装置１００は、ｉを２に設定する（Ｓ５３）。次いで、送信装置１００は、ｉが１４より大きいか否かを判定する（Ｓ５４）。ｉが１４より大きい場合（ｉ＞１４）、処理は図１１のＳ５８へと進む。一方、ｉが１４より大きくない場合（ｉ≦１４）、処理はＳ５５へと進む。
【００８５】
処理がＳ５５へと進んだ場合、送信装置１００は、Ｗ［ｉ／２］に対する楕円曲線２倍算ＥＣＤＢＬを実行し、その結果をＷ［ｉ］に設定する（Ｓ５５）。次いで、送信装置１００は、Ｗ［ｉ］とベースポイントＰとを加算する楕円曲線加算ＥＣＡＤＤを実行し、その結果をＷ［ｉ＋１］に設定する（Ｓ５６）。次いで、送信装置１００は、ｉに２を加算する（Ｓ５７）。Ｓ５７の処理が完了すると、処理はＳ５４へと進む。
【００８６】
処理が図１１のＳ５８へと進んだ場合、送信装置１００は、Ｗ［ｄ［ｎ−１，ｎ−４］］を一時変数Ｔに設定する（Ｓ５８）。但し、ｄ［ｎ−１，ｎ−４］は、４つのビット値ｄ［ｎ−１］、ｄ［ｎ−２］、ｄ［ｎ−３］、ｄ［ｎ−４］を並べたビット列を表す。図１０及び図１１の例では、Ｗ［ｄ［７，４］］＝Ｗ［０００１］＝Ｐが一時変数Ｔに設定される。
【００８７】
次いで、送信装置１００は、ｉをｎ−５に設定する（Ｓ５９）。次いで、送信装置１００は、ｉが３より小さいか否かを判定する（Ｓ６０）。ｉが３より小さい場合（ｉ＜３）、処理はＳ６７へと進む。一方、ｉが３より小さくない場合（ｉ≧３）、処理はＳ６１へと進む。
【００８８】
処理がＳ６１へと進んだ場合、送信装置１００は、一時変数Ｔに対する楕円曲線２倍算ＥＣＤＢＬを実行し、その結果を一時変数Ｔに設定する（Ｓ６１）。また、送信装置１００は、一時変数Ｔに対する楕円曲線２倍算ＥＣＤＢＬを実行し、その結果を一時変数Ｔに設定する（Ｓ６２）。さらに、送信装置１００は、一時変数Ｔに対する楕円曲線２倍算ＥＣＤＢＬを実行し、その結果を一時変数Ｔに設定する（Ｓ６３）。そして、送信装置１００は、一時変数Ｔに対する楕円曲線２倍算ＥＣＤＢＬを実行し、その結果を一時変数Ｔに設定する（Ｓ６４）。
次いで、送信装置１００は、一時変数ＴとＷ［ｄ［ｉ，ｉ−３］］とを加算する楕円曲線加算ＥＣＡＤＤを実行し、その結果を一時変数Ｔに設定する（Ｓ６５）。但し、ｄ［ｉ，ｉ−３］は、４つのビット値ｄ［ｉ］、ｄ［ｉ−１］、ｄ［ｉ−２］、ｄ［ｉ−３］を並べたビット列を表す。ｉ＝３の場合、Ｗ［ｄ［３，０］］＝Ｗ［０１０１］＝５Ｐとなる。次いで、送信装置１００は、ｉから４を減算する（Ｓ６６）。Ｓ６６の処理が完了すると、処理はＳ６０へと進む。
【００８９】
処理がＳ６７へと進んだ場合、送信装置１００は、スカラー値ｄとベースポイントＰとのスカラー倍算の結果として一時変数Ｔを出力する（Ｓ６７）。Ｓ６７の処理が完了すると、図１０及び図１１に示した一連の処理は終了する。
【００９０】
上記のように、予めウィンドウ毎に計算したスカラー倍算の結果Ｗ［ｉ］を利用することで、スカラー値ｄとベースポイントＰとのスカラー倍算を効率的に実行することができる。図１０に示した処理（以下、前処理）には、楕円曲線加算ＥＣＡＤＤが７回、楕円曲線２倍算ＥＣＤＢＬが７回含まれる。そのため、前処理にかかる計算時間ＴｉｍｅＰｒｅは、下記の式（１６）のようになる。
【００９１】
ＴｉｍｅＰｒｅ＝７×Ｔｉｍｅ（ＥＣＤＢＬ）＋７×Ｔｉｍｅ（ＥＣＡＤＤ）
＝７×（４Ｍ＋６Ｓ）＋７×（８Ｍ＋３Ｓ）
＝８４Ｍ＋６３Ｓ
＝１３４．４Ｍ
…（１６）
但し、上記の式（１６）に示したＴｉｍｅＰｒｅは、ヤコビアン座標を利用すると共に、１Ｍ＝０．８Ｓとおいた場合の計算時間である。同様に、ウィンドウ幅をＮビットとした場合、前処理には（２N−２）／２回の楕円曲線２倍算ＥＣＤＢＬと（２N−２）／２回の楕円曲線加算ＥＣＡＤＤが含まれる。そのため、前処理にかかる計算時間ＴｉｍｅＰｒｅは、下記の式（１７）のようになる。
【００９２】
ＴｉｍｅＰｒｅ＝（２N−２）／２×（４Ｍ＋６Ｓ）
＋（２N−２）／２×（８Ｍ＋３Ｓ）
＝（２N−２）／２×（１２Ｍ＋９Ｓ）
＝９．６×（２N−２）Ｍ
…（１７）
また、図１１に示した処理（以下、後処理）の計算には、Ｓ６１〜Ｓ６６の計算１回当たり４回の楕円曲線２倍算ＥＣＤＢＬと１回の楕円曲線加算ＥＣＡＤＤとが含まれる。また、Ｓ６１〜Ｓ６６の計算は、（ｎ−４）／４回実行されるので、後処理の計算時間ＴｉｍｅＭａｉｎは、１Ｍ＝０．８Ｓとおくと、下記の式（１８）のようになる。従って、スカラー値ｄが１６０ビットの場合、スカラー倍算全体の平均的な計算時間Ｔｉｍｅは下記の式（１９）で与えられる。
【００９３】
ＴｉｍｅＭａｉｎ＝（（４Ｍ＋６Ｓ）×４＋（１２Ｍ＋４Ｓ））×（ｎ−４）／４
＝１２．６Ｍ×（ｎ−４）
…（１８）
Ｔｉｍｅ＝ＴｉｍｅＰｒｅ＋ＴｉｍｅＭａｉｎ
＝１３４．４Ｍ＋１２．６Ｍ×１５６
＝２１００Ｍ
…（１９）
以上、スカラー倍算の計算方法について説明した。ここではバイナリ法及びウィンドウ法を適用したアルゴリズムを紹介したが、第２実施形態に係る送信装置１００（及び受信装置２００）は、上記の計算時間をさらに短縮可能な新たなアルゴリズムを用いてスカラー倍算を計算する。
【００９４】
［２−４．送信装置１００の機能］
以下、スカラー倍算の計算時間を短縮可能な新たなアルゴリズムに係る送信装置１００の機能について説明する。
【００９５】
（機能ブロック）
まず、図１２を参照しながら、送信装置１００の機能について説明する。なお、図１２は、第２実施形態に係る送信装置が有する機能の例を示したブロック図である。
【００９６】
図１２に示すように、送信装置１００は、通信部１０１、記憶部１０２、及び演算部１０３を有する。なお、通信部１０１の機能は、上述した接続ポート９２４や通信部９２６などを用いて実現できる。記憶部１０２の機能は、上述したＲＡＭ９０６や記憶部９２０などを用いて実現できる。演算部１０３の機能は、上述したＣＰＵ９０２などを用いて実現できる。
【００９７】
通信部１０１は、ネットワークＮＷを介して受信装置２００と通信する要素である。例えば、通信部１０１は、ランダムに生成されたスカラー値ｒとベースポイントＰとのスカラー倍算の結果Ｒ及び暗号文Ｃを受信装置２００へと送信する。記憶部１０２は、ベースポイントＰ、公開鍵Ｓ、平文Ｍ（メッセージ）を記憶する。また、記憶部１０２には、後述するウィンドウ毎に計算されたスカラー倍算の結果Ｗ［ｉ］（ｉ＝０，１，…）が格納される。
【００９８】
演算部１０３は、ベースポイントＰ及び公開鍵Ｓに基づいて楕円曲線暗号方式により平文Ｍを暗号化して暗号文Ｃを生成する。演算部１０３は、前処理部１３１、及び後処理部１３２を有する。
【００９９】
前処理部１３１は、予め設定された長さのビット列（ウィンドウ）が取り得る全てのスカラー値について、スカラー値毎にベースポイントＰに対するスカラー倍算を実行する。このとき、前処理部１３１は、ヤコビアン座標のＺ座標が共通する楕円曲線Ｅ上の点を加算する楕円曲線加算ＥＣＡＤＤcoZ、及び、楕円曲線加算ＥＣＡＤＤcoZを効率良く適用できるようにする楕円曲線２倍算ＥＣＤＢＬcoZを利用する。そして、前処理部１３１は、ウィンドウ毎に計算したスカラー倍算の結果Ｗ［ｉ］（ｉ＝０，１，…）を記憶部１０２に格納する。
【０１００】
後処理部１３２は、記憶部１０２に格納されたスカラー倍算の結果Ｗ［ｉ］（ｉ＝０，１，…）を用いて、暗号文Ｃの生成時に現れるベースポイントＰに対するスカラー倍算を実行する。例えば、後処理部１３２は、スカラー値ｄをウィンドウ幅と同じ長さの複数のビット列に分け、ビット列毎のスカラー倍算の結果を組み合わせてスカラー値ｄとベースポイントＰとのスカラー倍算を実行する。このとき、後処理部１３２は、ビット毎のスカラー倍算の結果としてＷ［ｉ］（ｉ＝０，１，…）を利用する。
【０１０１】
（楕円曲線２倍算ＥＣＤＢＬcoZについて）
ここで、図１３を参照しながら、楕円曲線２倍算ＥＣＤＢＬcoZについて説明する。なお、図１３は、第２実施形態に係るスカラー倍算の計算について説明するための第１のフロー図である。図１３の例は、楕円曲線Ｅ上の点Ｐ１に対する楕円曲線２倍算ＥＣＤＢＬcoZのアルゴリズムを示す。
【０１０２】
図１３に示すように、前処理部１３１は、４×Ｘ1×Ｙ12を計算し、その結果を一時変数Ｑに設定する（Ｓ１３１）。次いで、前処理部１３１は、３×Ｘ12＋Ｑ×Ｚ14を計算し、その結果を一時変数Ｕに設定する（Ｓ１３２）。次いで、前処理部１３１は、−２×Ｑ＋Ｕ2を計算し、その結果をＸ3に設定する（Ｓ１３３）。次いで、前処理部１３１は、−８×Ｙ14＋Ｕ×（Ｑ−Ｘ3）を計算し、その結果をＹ3に設定する（Ｓ１３４）。次いで、前処理部１３１は、２×Ｙ1×Ｚ1を計算し、その結果をＺ3に設定する（Ｓ１３５）。
【０１０３】
Ｓ１３１〜Ｓ１３５の処理により、楕円曲線Ｅ上の点Ｐ1を２倍した２×Ｐ1に対応する点Ｐ3の座標（Ｘ3：Ｙ3：Ｚ3）が得られる。楕円曲線２倍算ＥＣＤＢＬcoZのアルゴリズムでは、さらにＳ１３６、Ｓ１３７の処理が実行される。Ｓ１３６の処理において、前処理部１３１は、一時変数ＱをＸ1pに設定する（Ｓ１３６）。次いで、前処理部１３１は、８×Ｙ14を計算し、その結果をＹ1pに設定する（Ｓ１３７）。座標（Ｘ1p：Ｙ1p：Ｚ3）を有する点Ｐ1pは、点Ｐ1と同じ楕円曲線Ｅ上の点である。
【０１０４】
上記のように、楕円曲線２倍算ＥＣＤＢＬcoZは、２×Ｐ1に対応する点Ｐ3を出力すると共に、点Ｐ3と同じＺ座標を有する点Ｐ1の座標を出力する。そのため、点Ｐ3を計算した後、さらに点Ｐ3と点Ｐ1とを加算する場合に、Ｚ座標が共通する２点Ｐ1、Ｐ3の座標を用いて演算を行うことが可能になる。
【０１０５】
（楕円曲線加算ＥＣＡＤＤcoZについて）
次に、図１４を参照しながら、楕円曲線加算ＥＣＡＤＤcoZについて説明する。なお、図１４は、第２実施形態に係るスカラー倍算の計算について説明するための第２のフロー図である。図１４の例は、楕円曲線Ｅ上の異なる２点Ｐ1、Ｐ2を加算する楕円曲線加算ＥＣＡＤＤcoZのアルゴリズムを示す。
【０１０６】
図１４に示すように、前処理部１３１は、（Ｘ2−Ｘ1）2を計算し、その結果を一時変数Ｑに設定する（Ｓ１４１）。次いで、前処理部１３１は、Ｘ1×Ｑを計算し、一時変数Ｕに設定する（Ｓ１４２）。次いで、前処理部１３１は、Ｘ2×Ｑを計算し、その結果を一時変数Ｖに設定する（Ｓ１４３）。次いで、前処理部１３１は、（Ｙ2−Ｙ1）2を計算し、その結果を一時変数Ｊに設定する（Ｓ１４４）。なお、Ｓ１４２、Ｓ１４３の処理は、順序を入れ替えることが可能である。また、Ｓ１４４の処理と、Ｓ１４１〜Ｓ１４３の処理とは順序を入れ替えることが可能である。
【０１０７】
次いで、前処理部１３１は、Ｊ−Ｕ−Ｖを計算し、その結果をＸ3に設定する（Ｓ１４５）。次いで、前処理部１３１は、（Ｙ2−Ｙ1）×（Ｕ−Ｘ3）−Ｙ1×（Ｖ−Ｕ）を計算し、Ｙ3に設定する（Ｓ１４６）。次いで、前処理部１３１は、Ｚ1×（Ｘ2−Ｘ1）を計算し、その結果をＺ3に設定する（Ｓ１４７）。
【０１０８】
Ｓ１４１〜Ｓ１４７の処理により、楕円曲線Ｅ上の異なる２点Ｐ1、Ｐ2を加算した点Ｐ3の座標（Ｘ3：Ｙ3：Ｚ3）が得られる。楕円曲線加算ＥＣＡＤＤcoZのアルゴリズムでは、さらにＳ１４８、Ｓ１４９の処理が実行される。Ｓ１３６の処理において、前処理部１３１は、一時変数ＵをＸ1pに設定する（Ｓ１４８）。次いで、前処理部１３１は、Ｙ1×（Ｖ−Ｕ）を計算し、その結果をＹ1pに設定する（Ｓ１４９）。座標（Ｘ1p：Ｙ1p：Ｚ3）を有する点Ｐ1pは、点Ｐ1と同じ楕円曲線Ｅ上の点である。
【０１０９】
上記のように、楕円曲線加算ＥＣＡＤＤcoZは、Ｐ1＋Ｐ2に対応する点Ｐ3を出力すると共に、点Ｐ3と同じＺ座標を有する点Ｐ1の座標を出力する。そのため、点Ｐ3を計算した後、さらに点Ｐ3と点Ｐ1とを加算する場合に、Ｚ座標が共通する２点Ｐ1、Ｐ3の座標を用いて演算を行うことが可能になる。また、Ｚ座標が共通する上記の加算演算は、既に説明した楕円曲線加算ＥＣＡＤＤに比べて高速に実行可能である。
【０１１０】
従って、楕円曲線加算ＥＣＡＤＤcoZを利用することで、スカラー倍算が高速化される。以下で述べるように、楕円曲線２倍算ＥＣＤＢＬcoZを利用して楕円曲線加算ＥＣＡＤＤcoZを有効に活用することにより、スカラー倍算を高速化することができる。
【０１１１】
（ＥＣＤＢＬcoZ、ＥＣＡＤＤcoZに基づくスカラー倍算）
ここで、図１５を参照しながら、楕円曲線２倍算ＥＣＤＢＬcoZ、及び楕円曲線加算ＥＣＡＤＤcoZに基づくスカラー倍算の計算について説明する。なお、図１５は、第２実施形態に係るスカラー倍算の計算について説明するための第３のフロー図である。図１５の例は、ウィンドウ幅が４ビットの場合を想定し、スカラー倍算により、楕円曲線Ｅ上の点Ｐについて０×Ｐ、１×Ｐ、２×Ｐ、…、１５×Ｐをそれぞれ計算する前処理の方法である。
【０１１２】
前処理を開始した前処理部１３１は、０×Ｐに対応する無限遠点∞をＷ［０］に設定し、Ｗ［０］を記憶部１０２に格納する。また、前処理部１３１は、１×Ｐに対応するＰをＷ［１］に設定し、Ｗ［１］を記憶部１０２に格納する。その後、前処理部１３１は、図１５に示す処理を順次実行する。
【０１１３】
図１５に示すように、前処理部１３１は、点Ｐに対する楕円曲線２倍算ＥＣＤＢＬcoZ（Ｐ1＝Ｐ、Ｐ3＝２×Ｐに対応）を実行する（Ｓ１５１）。Ｓ１５１の演算により、２×Ｐの座標が得られる。さらに、２×ＰとＺ座標が共通するＰの座標が得られる。前処理部１３１は、楕円曲線２倍算ＥＣＤＢＬcoZにより得られた２×Ｐの座標をＷ［２］に設定し、Ｗ［２］を記憶部１０２に格納する。さらに、前処理部１３１は、２×ＰとＺ座標が共通するＰの座標を記憶部１０２に格納する。
【０１１４】
次いで、前処理部１３１は、Ｓ１５２〜Ｓ１５８の処理を含む第１の処理群と、Ｓ１５９〜Ｓ１６４の処理を含む第２の処理群とを実行する。第１の処理群は、３以上の奇数×Ｐを計算する処理の集合である。一方、第２の処理群は、４以上の偶数×Ｐを計算する処理の集合である。第１の処理群と第２の処理群とは実行順序を入れ替えることが可能である。また、第２の処理群と第２の処理群とを並列に実行することが可能である。ここでは、第１の処理群、第２の処理群の順番で処理が実行される場合について考える。
【０１１５】
（第１の処理群）
前処理部１３１は、２×ＰにＰを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝Ｐ、Ｐ3＝３×Ｐに対応）を実行する（Ｓ１５２）。このとき、前処理部１３１は、２×ＰとＺ座標が共通するＰの座標及びＷ［２］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１５２の演算により、３×Ｐの座標が得られる。さらに、３×ＰとＺ座標が共通するＰの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた３×Ｐの座標をＷ［３］に設定し、Ｗ［３］を記憶部１０２に格納する。さらに、前処理部１３１は、３×ＰとＺ座標が共通する２×Ｐの座標を記憶部１０２に格納する。
【０１１６】
次いで、前処理部１３１は、３×Ｐに２×Ｐを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝３×Ｐ、Ｐ3＝５×Ｐに対応）を実行する（Ｓ１５３）。このとき、前処理部１３１は、３×ＰとＺ座標が共通する２×Ｐの座標及びＷ［３］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１５３の演算により、５×Ｐの座標が得られる。さらに、５×ＰとＺ座標が共通する２×Ｐの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた５×Ｐの座標をＷ［５］に設定し、Ｗ［５］を記憶部１０２に格納する。さらに、前処理部１３１は、５×ＰとＺ座標が共通する２×Ｐの座標を記憶部１０２に格納する。
【０１１７】
次いで、前処理部１３１は、５×Ｐに２×Ｐを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝５×Ｐ、Ｐ3＝７×Ｐに対応）を実行する（Ｓ１５４）。このとき、前処理部１３１は、５×ＰとＺ座標が共通する２×Ｐの座標及びＷ［５］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１５４の演算により、７×Ｐの座標が得られる。さらに、７×ＰとＺ座標が共通する２×Ｐの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた７×Ｐの座標をＷ［７］に設定し、Ｗ［７］を記憶部１０２に格納する。さらに、前処理部１３１は、７×ＰとＺ座標が共通する２×Ｐの座標を記憶部１０２に格納する。
【０１１８】
次いで、前処理部１３１は、７×Ｐに２×Ｐを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝７×Ｐ、Ｐ3＝９×Ｐに対応）を実行する（Ｓ１５５）。このとき、前処理部１３１は、７×ＰとＺ座標が共通する２×Ｐの座標及びＷ［７］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１５５の演算により、９×Ｐの座標が得られる。さらに、９×ＰとＺ座標が共通する２×Ｐの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた９×Ｐの座標をＷ［９］に設定し、Ｗ［９］を記憶部１０２に格納する。さらに、前処理部１３１は、９×ＰとＺ座標が共通する２×Ｐの座標を記憶部１０２に格納する。
【０１１９】
次いで、前処理部１３１は、９×Ｐに２×Ｐを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝９×Ｐ、Ｐ3＝１１×Ｐに対応）を実行する（Ｓ１５６）。このとき、前処理部１３１は、９×ＰとＺ座標が共通する２×Ｐの座標及びＷ［９］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１５６の演算により、１１×Ｐの座標が得られる。さらに、１１×ＰとＺ座標が共通する２×Ｐの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた１１×Ｐの座標をＷ［１１］に設定し、Ｗ［１１］を記憶部１０２に格納する。さらに、前処理部１３１は、１１×ＰとＺ座標が共通する２×Ｐの座標を記憶部１０２に格納する。
【０１２０】
次いで、前処理部１３１は、１１×Ｐに２×Ｐを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝１１×Ｐ、Ｐ3＝１３×Ｐに対応）を実行する（Ｓ１５７）。このとき、前処理部１３１は、１１×ＰとＺ座標が共通する２×Ｐの座標及びＷ［１１］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１５７の演算により、１３×Ｐの座標が得られる。さらに、１３×ＰとＺ座標が共通する２×Ｐの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた１３×Ｐの座標をＷ［１３］に設定し、Ｗ［１３］を記憶部１０２に格納する。さらに、前処理部１３１は、１３×ＰとＺ座標が共通する２×Ｐの座標を記憶部１０２に格納する。
【０１２１】
次いで、前処理部１３１は、１３×Ｐに２×Ｐを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝１３×Ｐ、Ｐ3＝１５×Ｐに対応）を実行する（Ｓ１５８）。このとき、前処理部１３１は、１３×ＰとＺ座標が共通する２×Ｐの座標及びＷ［１３］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１５８の演算により、１５×Ｐの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた１５×Ｐの座標をＷ［１５］に設定し、Ｗ［１５］を記憶部１０２に格納する。Ｓ１５８の処理では、１５×ＰとＺ座標が共通する２×Ｐの座標を計算しなくてもよい。
【０１２２】
（第２の処理群）
前処理部１３１は、２×Ｐを２倍する楕円曲線２倍算ＥＣＤＢＬcoZ（Ｐ1＝２×Ｐ、Ｐ3＝４×Ｐに対応）を実行する（Ｓ１５９）。このとき、前処理部１３１は、Ｗ［２］を用いて楕円曲線２倍算ＥＣＤＢＬcoZを実行する。Ｓ１５９の演算により、４×Ｐの座標が得られる。さらに、４×ＰとＺ座標が共通する２×Ｐの座標が得られる。前処理部１３１は、楕円曲線２倍算ＥＣＤＢＬcoZにより得られた４×Ｐの座標をＷ［４］に設定し、Ｗ［４］を記憶部１０２に格納する。さらに、前処理部１３１は、４×ＰとＺ座標が共通する２×Ｐの座標を記憶部１０２に格納する。
【０１２３】
次いで、前処理部１３１は、４×Ｐに２×Ｐを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝４×Ｐ、Ｐ3＝６×Ｐに対応）を実行する（Ｓ１６０）。このとき、前処理部１３１は、４×ＰとＺ座標が共通する２×Ｐの座標及びＷ［４］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１６０の演算により、６×Ｐの座標が得られる。さらに、６×ＰとＺ座標が共通する２×Ｐの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた６×Ｐの座標をＷ［６］に設定し、Ｗ［６］を記憶部１０２に格納する。さらに、前処理部１３１は、６×ＰとＺ座標が共通する２×Ｐの座標を記憶部１０２に格納する。
【０１２４】
次いで、前処理部１３１は、６×Ｐに２×Ｐを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝６×Ｐ、Ｐ3＝８×Ｐに対応）を実行する（Ｓ１６１）。このとき、前処理部１３１は、６×ＰとＺ座標が共通する２×Ｐの座標及びＷ［６］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１６１の演算により、８×Ｐの座標が得られる。さらに、８×ＰとＺ座標が共通する２×Ｐの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた８×Ｐの座標をＷ［８］に設定し、Ｗ［８］を記憶部１０２に格納する。さらに、前処理部１３１は、８×ＰとＺ座標が共通する２×Ｐの座標を記憶部１０２に格納する。
【０１２５】
次いで、前処理部１３１は、８×Ｐに２×Ｐを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝８×Ｐ、Ｐ3＝１０×Ｐに対応）を実行する（Ｓ１６２）。このとき、前処理部１３１は、８×ＰとＺ座標が共通する２×Ｐの座標及びＷ［８］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１６２の演算により、１０×Ｐの座標が得られる。さらに、１０×ＰとＺ座標が共通する２×Ｐの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた１０×Ｐの座標をＷ［１０］に設定し、Ｗ［１０］を記憶部１０２に格納する。さらに、前処理部１３１は、１０×ＰとＺ座標が共通する２×Ｐの座標を記憶部１０２に格納する。
【０１２６】
次いで、前処理部１３１は、１０×Ｐに２×Ｐを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝１０×Ｐ、Ｐ3＝１２×Ｐに対応）を実行する（Ｓ１６３）。このとき、前処理部１３１は、１０×ＰとＺ座標が共通する２×Ｐの座標及びＷ［１０］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１６３の演算により、１２×Ｐの座標が得られる。さらに、１２×ＰとＺ座標が共通する２×Ｐの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた１２×Ｐの座標をＷ［１２］に設定し、Ｗ［１２］を記憶部１０２に格納する。さらに、前処理部１３１は、１２×ＰとＺ座標が共通する２×Ｐの座標を記憶部１０２に格納する。
【０１２７】
次いで、前処理部１３１は、１２×Ｐに２×Ｐを加算する楕円曲線加算ＥＣＡＤＤcoZ（Ｐ1＝２×Ｐ、Ｐ2＝１２×Ｐ、Ｐ3＝１４×Ｐに対応）を実行する（Ｓ１６４）。このとき、前処理部１３１は、１２×ＰとＺ座標が共通する２×Ｐの座標及びＷ［１２］を用いて楕円曲線加算ＥＣＡＤＤcoZを実行する。Ｓ１６４の演算により、１４×Ｐの座標が得られる。前処理部１３１は、楕円曲線加算ＥＣＡＤＤcoZにより得られた１４×Ｐの座標をＷ［１４］に設定し、Ｗ［１４］を記憶部１０２に格納する。なお、Ｓ１６４の処理では、１４×ＰとＺ座標が共通する２×Ｐの座標を計算しなくてもよい。
【０１２８】
（演算量の評価）
上述した楕円曲線２倍算ＥＣＤＢＬcoZの計算時間は４Ｍ＋６Ｓである。また、上述した楕円曲線加算ＥＣＡＤＤcoZの計算時間は５Ｍ＋２Ｓである。また、図１５に例示した前処理は、楕円曲線２倍算ＥＣＤＢＬcoZを２回、楕円曲線加算ＥＣＡＤＤcoZを１２回含む。そのため、前処理にかかる計算時間ＴｉｍｅＰｒｅは、下記の式（２０）のようになる。従って、図１０に例示した前処理の計算時間に比べると、図１５に例示した方法を適用することで約２８％の高速化が実現できていることがわかる。
【０１２９】
ＴｉｍｅＰｒｅ＝２×（４Ｍ＋６Ｓ）＋１２×（５Ｍ＋２Ｓ）
＝９６．８Ｍ
…（２０）
また、ウィンドウ幅がＮビットの場合、上記の前処理には、２回の楕円曲線２倍算ＥＣＤＢＬcoZと、（２N−４）回の楕円曲線加算ＥＣＡＤＤcoZとが含まれる。従って、計算時間ＴｉｍｅＰｒｅは、下記の式（２１）のようになる。
【０１３０】
ＴｉｍｅＰｒｅ＝２×（４Ｍ＋６Ｓ）＋（２N−４）×（５Ｍ＋２Ｓ）
＝（５×２N−１２）Ｍ＋（２×２N＋４）Ｓ
＝（６．６×２N−８．８）Ｍ
…（２１）
Ｎ＝２の場合、上記の式（２１）により計算される計算時間ＴｉｍｅＰｒｅは、ＴｉｍｅＰｒｅ＝１７．６Ｍとなる。同様に、Ｎ＝３の場合、ＴｉｍｅＰｒｅ＝４４．０Ｍとなる。Ｎ＝４の場合、ＴｉｍｅＰｒｅ＝９６．８Ｍとなる。また、Ｎ＝５の場合、ＴｉｍｅＰｒｅ＝２０２．４Ｍとなる。
【０１３１】
上記の式（１７）（図１０に示した前処理に対応）で計算される計算時間ＴｉｍｅＰｒｅと比較すると、Ｎ＝２の場合で８．３％、Ｎ＝３の場合で２３．６％、Ｎ＝４の場合で２８．０％、Ｎ＝５の場合で２９．７％の高速化が実現できていることが確かめられる。つまり、第２実施形態に係る前処理の方法を適用することで、スカラー倍算の高速化、ひいては楕円曲線暗号に係る処理の高速化が実現される。
【０１３２】
以上、送信装置１００の機能について説明した。
［２−５．受信装置２００の機能］
次に、図１６を参照しながら、スカラー倍算の計算時間を短縮可能な新たなアルゴリズムに係る受信装置２００の機能について説明する。なお、図１６は、第２実施形態に係る受信装置が有する機能の例を示したブロック図である。
【０１３３】
図１６に示すように、受信装置２００は、通信部２０１、記憶部２０２、及び演算部２０３を有する。なお、通信部２０１の機能は、上述した接続ポート９２４や通信部９２６などを用いて実現できる。記憶部２０２の機能は、上述したＲＡＭ９０６や記憶部９２０などを用いて実現できる。演算部２０３の機能は、上述したＣＰＵ９０２などを用いて実現できる。
【０１３４】
通信部２０１は、ネットワークＮＷを介して送信装置１００と通信する要素である。例えば、通信部２０１は、ランダムに生成されたスカラー値ｒとベースポイントＰとのスカラー倍算の結果Ｒ及び暗号文Ｃを送信装置１００から受信する。記憶部２０２は、秘密鍵ｓを記憶する。また、記憶部２０２には、ウィンドウ毎に計算されたスカラー倍算の結果ＷR［ｉ］（ｉ＝０，１，…）が格納される。
【０１３５】
演算部２０３は、送信装置１００から受信したＲ及び秘密鍵ｓを利用して暗号文Ｃから平文Ｍを復元する。演算部２０３は、前処理部２３１、及び後処理部２３２を有する。
前処理部２３１は、予め設定された長さのビット列（ウィンドウ）が取り得る全てのスカラー値について、スカラー値毎に楕円曲線Ｅ上の点Ｒに対するスカラー倍算を実行する。このとき、前処理部２３１は、ヤコビアン座標のＺ座標が共通する楕円曲線Ｅ上の点を加算する楕円曲線加算ＥＣＡＤＤcoZ、及び、楕円曲線加算ＥＣＡＤＤcoZを効率良く適用できるようにする楕円曲線２倍算ＥＣＤＢＬcoZを利用する。そして、前処理部２３１は、ウィンドウ毎に計算したスカラー倍算の結果ＷR［ｉ］（ｉ＝０，１，…）を記憶部２０２に格納する。
【０１３６】
後処理部２３２は、記憶部２０２に格納されたスカラー倍算の結果ＷR［ｉ］（ｉ＝０，１，…）を用いて、楕円曲線Ｅ上の点Ｒに対するスカラー倍算を実行する。例えば、後処理部２３２は、スカラー値ｄをウィンドウ幅と同じ長さの複数のビット列に分け、ビット列毎のスカラー倍算の結果を組み合わせてスカラー値ｄと点Ｒとのスカラー倍算を実行する。このとき、後処理部２３２は、ビット毎のスカラー倍算の結果としてＷR［ｉ］（ｉ＝０，１，…）を利用する。
【０１３７】
なお、前処理部２３１及び後処理部２３２は、送信装置１００の演算部１０３が有する前処理部１３１及び後処理部１３２と同様に、楕円曲線２倍算ＥＣＤＢＬcoZ及び楕円曲線加算ＥＣＡＤＤcoZなどを用いて前処理のスカラー倍算を実行する。つまり、前処理部２３１は、図１５に例示した前処理と同様の処理を実行する。また、後処理部２３２は、図１１に例示した後処理と同様の処理を実行する。
【０１３８】
以上、第２実施形態について説明した。
＜３．付記＞
以上説明した実施形態に関し、さらに以下の付記を開示する。
【０１３９】
（付記１）設定された楕円曲線上の点について、設定された長さのビット列が取り得るビット値の組み合わせ毎に、前記ビット値の組み合わせに応じた前記楕円曲線上の点に対するスカラー倍算を実行する演算部と、
前記スカラー倍算の結果を記憶する記憶部と、
を有し、
前記演算部は、ヤコビアン座標の１つが共通する前記楕円曲線上の第１の点と第２の点とを加算する加算演算に基づいて前記スカラー倍算を実行する
情報処理装置。
【０１４０】
（付記２）前記演算部は、
前記第１の点と前記第２の点とが異なる点である場合、前記加算演算の中で、前記第１の点と前記第２の点との楕円曲線加算により第３の点を計算すると共に、前記第３の点とヤコビアン座標の１つが共通する前記第１の点の座標を計算し、
前記第１の点と前記第２の点とが同じ点である場合、前記加算演算の中で、前記第１の点の楕円曲線２倍算により第４の点を計算すると共に、前記第４の点とヤコビアン座標の１つが共通する前記第１の点の座標を計算する
付記１に記載の情報処理装置。
【０１４１】
（付記３）前記演算部は、設定されたスカラー値と前記設定された楕円曲線上の点とのスカラー倍算を計算する場合に、前記スカラー値を示すビット列を前記設定された長さの複数のビット列に分け、前記記憶部が記憶する前記スカラー倍算の結果を用いて前記設定されたスカラー値と前記設定された楕円曲線上の点とのスカラー倍算を計算する
付記１又は２に記載の情報処理装置。
【０１４２】
（付記４）記憶部を有するコンピュータが、
設定された楕円曲線上の点について、設定された長さのビット列が取り得るビット値の組み合わせ毎に、前記ビット値の組み合わせに応じた前記楕円曲線上の点に対するスカラー倍算を実行する処理、及び前記スカラー倍算の結果を前記記憶部に格納する処理を実行する情報処理方法であり、
前記スカラー倍算を実行する処理において、前記コンピュータが、ヤコビアン座標の１つが共通する前記楕円曲線上の第１の点と第２の点とを加算する加算演算に基づいて前記スカラー倍算を実行する
情報処理方法。
【０１４３】
（付記５）記憶部を有するコンピュータに、
設定された楕円曲線上の点について、設定された長さのビット列が取り得るビット値の組み合わせ毎に、前記ビット値の組み合わせに応じた前記楕円曲線上の点に対するスカラー倍算を実行する処理、及び前記スカラー倍算の結果を前記記憶部に格納する処理を実行させるプログラムであり、
前記スカラー倍算を実行する処理において、前記コンピュータに、ヤコビアン座標の１つが共通する前記楕円曲線上の第１の点と第２の点とを加算する加算演算に基づいて前記スカラー倍算を実行させる
プログラム。
【０１４４】
（付記６）暗号化装置又は暗号処理装置として機能する情報処理装置であって、前記演算部が、楕円曲線暗号方式に基づいてメッセージを暗号化する処理の中で前記スカラー倍算を実行する
付記３に記載の情報処理装置。
【０１４５】
（付記７）復号装置又は暗号処理装置として機能する情報処理装置であって、前記演算部が、楕円曲線暗号方式に基づいて暗号化された暗号文を復号する処理の中で前記スカラー倍算を実行する
付記３に記載の情報処理装置。
【０１４６】
（付記８）付記５に記載のプログラムが格納された、前記コンピュータにより読み取り可能な記録媒体。
（付記９）前記スカラー倍算を実行する処理において、前記コンピュータが、
前記第１の点と前記第２の点とが異なる点である場合、前記加算演算の中で、前記第１の点と前記第２の点との楕円曲線加算により第３の点を計算すると共に、前記第３の点とヤコビアン座標の１つが共通する前記第１の点の座標を計算し、
前記第１の点と前記第２の点とが同じ点である場合、前記加算演算の中で、前記第１の点の楕円曲線２倍算により第４の点を計算すると共に、前記第４の点とヤコビアン座標の１つが共通する前記第１の点の座標を計算する
付記４に記載の情報処理方法。
【０１４７】
（付記１０）前記コンピュータが、
設定されたスカラー値と前記設定された楕円曲線上の点とのスカラー倍算を計算する場合に、前記スカラー値を示すビット列を前記設定された長さの複数のビット列に分け、前記記憶部が記憶する前記スカラー倍算の結果を用いて前記設定されたスカラー値と前記設定された楕円曲線上の点とのスカラー倍算を計算する
付記４又は９に記載の情報処理方法。
【符号の説明】
【０１４８】
１０  情報処理装置
１１  演算部
１２  記憶部
ＥＣＤＢＬcoZ  楕円曲線２倍算
ＥＣＡＤＤcoZ  楕円曲線加算
Ｐ  設定された楕円曲線上の点
Ｐ1  第１の点
Ｐ2  第２の点
Ｐ3  第３の点
Ｐ4  第４の点
ｄ  スカラー値
【図１】
2015135363.tif 000003
【図２】
2015135363.tif 000004
【図３】
2015135363.tif 000005
【図４】
2015135363.tif 000006
【図５】
2015135363.tif 000007
【図６】
2015135363.tif 000008
【図７】
2015135363.tif 000009
【図８】
2015135363.tif 000010
【図９】
2015135363.tif 000011
【図１０】
2015135363.tif 000012
【図１１】
2015135363.tif 000013
【図１２】
2015135363.tif 000014
【図１３】
2015135363.tif 000015
【図１４】
2015135363.tif 000016
【図１５】
2015135363.tif 000017
【図１６】
2015135363.tif 000018