(57)【要約】【課題】  楕円曲線暗号は安全性が高く、鍵の桁数を小さくできるため、公開鍵暗号として有望視されているが、有限体における演算に時間がかかる。【解決手段】  入出力部１０は、楕円曲線上の点Ｐの座標、および整数倍算の倍数を与える整数ｋの入力を受け付ける。ｓ進展開部２８は、複数の基数ｓ毎に整数ｋのｓ進展開を求める。コスト評価部３０は、各ｓ進展開の非零桁の個数に基づいてｓ進法によりｋ倍算を行った場合の計算コストを求める。選択部３２は、最も計算コストが小さいｈ進法を選択する。予備計算部３４は、点Ｐについて（ｈ−１）倍以下の整数倍点をあらかじめ計算して記憶する。ｈ進法演算部３５は、ｈ倍算演算部３６による点Ｐのｈ倍算と、加算演算部３８による点Ｐの（ｈ−１）倍以下の整数倍点の加算を組み合わせたｈ進法により、点Ｐのｋ倍算を計算する。【選択図】        図１
2005148141.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線上の任意の点Ｐの整数倍演算ｋＰを行う楕円曲線整数倍演算装置であって、
整数ｋについて複数の基数ｓによるｓ進展開を求めるｓ進展開部と、
前記複数の基数ｓのそれぞれについて、前記点Ｐのｋ倍点Ｑをｓ倍算と加算の組み合わせにより算出するｓ進法の計算コストを評価するコスト評価部と、
前記計算コストに基づき、前記複数の基数ｓの中から一つの基数ｈを選択する選択部と、
選択された前記基数ｈによる前記整数ｋのｈ進展開に基づき、前記点Ｐのｋ倍点Ｑをｈ倍算と加算の組み合わせにより算出するｈ進法演算部とを含むことを特徴とする楕円曲線整数倍演算装置。
【請求項２】
前記ｈ進法演算部における前記ｈ進法の演算に必要な前記点Ｐの（ｈ−１）倍以下の整数倍点をあらかじめ計算する予備計算部と、
前記予備計算部により計算された前記（ｈ−１）倍以下の整数倍点を記憶する記憶部とをさらに含み、
前記ｈ進法演算部は、前記記憶部に記憶された前記（ｈ−１）倍以下の整数倍点を加算の際に利用することを特徴とする請求項１に記載の楕円曲線整数倍演算装置。
【請求項３】
前記コスト評価部は、前記ｓ進展開における非零桁の個数を用いた評価式に基づいて、各ｓ進法の計算コストを比較することを特徴とする請求項１または２に記載の楕円曲線整数倍演算装置。
【請求項４】
前記コスト評価部は、前記ｓ進展開における非零桁の個数をｓ進桁数で除算した相対重みを用いた評価式に基づいて、各ｓ進法の計算コストを比較することを特徴とする請求項１または２に記載の楕円曲線整数倍演算装置。
【請求項５】
前記コスト評価部は、前記ｓ進法における逆元算と乗算の計算コストの比の見積もり値を用いた評価式に基づいて、各ｓ進法の計算コストを比較することを特徴とする請求項３または４に記載の楕円曲線整数倍演算装置。
【請求項６】
楕円曲線上の基点Ｇとその位数ｎの入力を受け付ける入力部と、
０＜ｄ＜ｎを満たす乱数ｄを生成する乱数生成部と、
前記基点Ｇのｄ倍点Ｑを算出する整数倍演算部と、
前記乱数ｄを秘密鍵、前記ｄ倍点Ｑを公開鍵として生成する鍵生成部とを含み、
前記整数倍演算部は、楕円曲線上の任意の点Ｐの整数倍演算ｋＰを行うものであって、
整数ｋについて複数の基数ｓによるｓ進展開を求めるｓ進展開部と、
前記複数の基数ｓのそれぞれについて、前記点Ｐのｋ倍点Ｑをｓ倍算と加算の組み合わせにより算出するｓ進法の計算コストを評価するコスト評価部と、
前記計算コストに基づき、前記複数の基数ｓの中から一つの基数ｈを選択する選択部と、
選択された前記基数ｈによる前記整数ｋのｈ進展開に基づき、前記点Ｐのｋ倍点Ｑをｈ倍算と加算の組み合わせにより算出するｈ進法演算部とを含むことを特徴とする鍵生成装置。
【請求項７】
楕円曲線上の基点Ｇとその位数ｎ、公開鍵Ｑ、および平文Ｍの入力を受け付ける入力部と、
０＜ｒ＜ｎを満たす乱数ｒを生成する乱数生成部と、
前記基点Ｇのｒ倍点ｒＧと、前記公開鍵Ｑのｒ倍点ｒＱを算出する整数倍演算部と、
前記整数倍演算部による算出結果を用いて、第１暗号Ｃ１＝ｒＧと第２暗号Ｃ２＝ｒＱ＋Ｍを計算し、暗号文（Ｃ１、Ｃ２）を生成する暗号文生成部とを含み、
前記整数倍演算部は、楕円曲線上の任意の点Ｐの整数倍演算ｋＰを行うものであって、
整数ｋについて複数の基数ｓによるｓ進展開を求めるｓ進展開部と、
前記複数の基数ｓのそれぞれについて、前記点Ｐのｋ倍点Ｑをｓ倍算と加算の組み合わせにより算出するｓ進法の計算コストを評価するコスト評価部と、
前記計算コストに基づき、前記複数の基数ｓの中から一つの基数ｈを選択する選択部と、
選択された前記基数ｈによる前記整数ｋのｈ進展開に基づき、前記点Ｐのｋ倍点Ｑをｈ倍算と加算の組み合わせにより算出するｈ進法演算部とを含むことを特徴とする暗号化装置。
【請求項８】
秘密鍵ｄ、および楕円曲線による第１暗号Ｃ１と第２暗号Ｃ２を含む暗号文（Ｃ１、Ｃ２）の入力を受け付ける入力部と、
前記第１暗号Ｃ１のｄ倍点ｄＣ１を算出する整数倍演算部と、
前記整数倍演算部による算出結果を用いて、前記第２暗号Ｃ２から前記第１暗号Ｃ１のｄ倍点ｄＣ１を減算することにより、復号された平文Ｍを生成する平文生成部とを含み、
前記整数倍演算部は、楕円曲線上の任意の点Ｐの整数倍演算ｋＰを行うものであって、
整数ｋについて複数の基数ｓによるｓ進展開を求めるｓ進展開部と、
前記複数の基数ｓのそれぞれについて、前記点Ｐのｋ倍点Ｑをｓ倍算と加算の組み合わせにより算出するｓ進法の計算コストを評価するコスト評価部と、
前記計算コストに基づき、前記複数の基数ｓの中から一つの基数ｈを選択する選択部と、
選択された前記基数ｈによる前記整数ｋのｈ進展開に基づき、前記点Ｐのｋ倍点Ｑをｈ倍算と加算の組み合わせにより算出するｈ進法演算部とを含むことを特徴とする復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は楕円曲線暗号技術に関し、特に楕円曲線上の点の整数倍演算を行う楕円曲線整数倍演算装置、ならびにその装置を利用可能な鍵生成装置、暗号化装置および復号装置に関する。
【背景技術】
【０００２】
公開鍵暗号の一方式として、楕円曲線暗号（あるいは楕円暗号）がある。楕円曲線暗号は１９８５年頃、ＫｏｂｌｉｔｚとＭｉｌｌｅｒがほぼ同時期に独立に提案し、ＲＳＡ暗号に代わる次世代の公開鍵暗号と目されている有望な暗号である。この楕円曲線暗号は同じ安全性規準で比較すると、ＲＳＡ暗号に比して鍵の大きさは数分の一でよい、という特徴がある。しかしそれでも秘密鍵暗号に比べて計算に時間がかかり低速である、という問題点は解決されていない。そこで高速化の方法が種々の方面から検討されている。
【０００３】
楕円曲線暗号は有限体上で定義された楕円曲線上の点の間に適当な加法を定義すると、これら点たちが群をなすことを利用する。楕円曲線の上に基準となる１点Ｐを定め、これをｋ倍した点をＱ＝ｋＰとすると、Ｑを与えられても、これからｋを求めることは計算量的に難しい。これを楕円曲線上の離散対数問題の困難性という。楕円曲線暗号はこの性質を利用する暗号であり、楕円曲線暗号を利用するには、点のｋ倍算が必要になる。従来のｋ倍算の方法は、２倍算と加算の組合せ（いわゆる“ｄｏｕｂｌｅ−ａｎｄ−ａｄｄ”）による２進法である。この方法ではｌｏｇ２ｋ回の２倍算と平均（１／２）ｌｏｇ２ｋ回の加算が必要となる。これの改良法としてｍ進法がある。ただしｍは２のべき２ｒである。さらに加法と減法を併用する符号付き法、移動窓法などがある（たとえば、非特許文献１参照）。
【非特許文献１】イアン・Ｆ・ブラケ，ガディエル・セロッシ，ナイジェル・Ｐ・スマート著，鈴木治郎訳，「楕円曲線暗号」，初版，株式会社ピアソン・エデュケーション，２００１年１２月２０日
【発明の開示】
【発明が解決しようとする課題】
【０００４】
楕円曲線暗号は公開鍵暗号の現在の主流であるＲＳＡ暗号よりも鍵の大きさが小さくてもよいという利点があるが、暗号化と復号処理が遅いという欠点をもつ。一般に、公開鍵暗号では巨大数を使うので、有限体における演算にどうしても計算時間がかかり、処理が遅くなる。計算量の問題は、暗号システムを実用化する上で避けることができない深刻な課題であり、楕円曲線暗号の実用性をより一層高めるために、さらなる計算速度の向上が求められている。
【０００５】
本発明はこうした状況に鑑みてなされたものであり、その目的は、楕円曲線暗号の高速化を実現することのできる楕円曲線整数倍演算装置、ならびにその装置を利用可能な鍵生成装置、暗号化装置および復号装置を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様は楕円曲線整数倍演算装置に関する。この装置は、楕円曲線上の任意の点Ｐの整数倍演算ｋＰを行うものであって、整数ｋについて複数の基数ｓによるｓ進展開を求めるｓ進展開部と、前記複数の基数ｓのそれぞれについて、前記点Ｐのｋ倍点Ｑをｓ倍算と加算の組み合わせにより算出するｓ進法の計算コストを評価するコスト評価部と、前記計算コストに基づき、前記複数の基数ｓの中から一つの基数ｈを選択する選択部と、選択された前記基数ｈによる前記整数ｋのｈ進展開に基づき、前記点Ｐのｋ倍点Ｑをｈ倍算と加算の組み合わせにより算出するｈ進法演算部とを含む。
【０００７】
本発明の別の態様は鍵生成装置に関する。この装置は、楕円曲線上の基点Ｇとその位数ｎの入力を受け付ける入力部と、０＜ｄ＜ｎを満たす乱数ｄを生成する乱数生成部と、前記基点Ｇのｄ倍点Ｑを算出する整数倍演算部と、前記乱数ｄを秘密鍵、前記ｄ倍点Ｑを公開鍵として生成する鍵生成部とを含む。前記整数倍演算部として、上記の態様の楕円曲線整数倍演算装置を利用する。
【０００８】
本発明のさらに別の態様は暗号化装置に関する。この装置は、楕円曲線上の基点Ｇとその位数ｎ、公開鍵Ｑ、および平文Ｍの入力を受け付ける入力部と、０＜ｒ＜ｎを満たす乱数ｒを生成する乱数生成部と、前記基点Ｇのｒ倍点ｒＧと、前記公開鍵Ｑのｒ倍点ｒＱを算出する整数倍演算部と、前記整数倍演算部による算出結果を用いて、第１暗号Ｃ１＝ｒＧと第２暗号Ｃ２＝ｒＱ＋Ｍを計算し、暗号文（Ｃ１、Ｃ２）を生成する暗号文生成部とを含む。前記整数倍演算部として、上記の態様の楕円曲線整数倍演算装置を利用する。
【０００９】
本発明のさらに別の態様は復号装置に関する。この装置は、秘密鍵ｄ、および楕円曲線による第１暗号Ｃ１と第２暗号Ｃ２を含む暗号文（Ｃ１、Ｃ２）の入力を受け付ける入力部と、前記第１暗号Ｃ１のｄ倍点ｄＣ１を算出する整数倍演算部と、前記整数倍演算部による算出結果を用いて、前記第２暗号Ｃ２から前記第１暗号Ｃ１のｄ倍点ｄＣ１を減算することにより、復号された平文Ｍを生成する平文生成部とを含む。前記整数倍演算部として、上記の態様の楕円曲線整数倍演算装置を利用する。
【００１０】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、サーバ、システム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１１】
本発明によれば、楕円曲線上の任意の点の整数倍演算を高速化することができる。
【発明を実施するための最良の形態】
【００１２】
以下本発明を好適な実施の形態をもとに説明する。まず、実施の形態の基礎となる理論を前提技術として述べ、その後、具体的な実施の形態を説明する。
【００１３】
［前提技術］
［１］  概要
本発明は、有限体上の楕円曲線の点群における演算の高速化に関するものである。本発明の実施の形態の基礎技術は、点の加算と２倍算を組み合わせた従来の２進法に対して、加算と３倍算を組み合わせた３進法、さらには、その一般化として加算とｈ倍算を組み合わせたｈ進法（ｈ＞２）を導入し、少なくとも２つのｓ進法（ｓ≧２）を選択的に併用するものであり、計算量の削減を図り、それによって楕円曲線暗号の高速化を図る。
【００１４】
［２］  楕円曲線
以下、Ｎ．コブリッツ著，林彬訳，「暗号の代数理論」（シュプリンガー・フェアラーク東京，１９９９年１０月）の第６章の記載を適宜用いて説明する。
［２．１］  楕円曲線の方程式
体Ｆ上の楕円曲線Ｅは、次の形の方程式で与えられる曲線である。
Ｙ２＋ａ１ＸＹ＋ａ３Ｙ＝Ｘ３＋ａ２Ｘ２＋ａ４Ｘ＋ａ６，  ａｉ∈Ｆ      （１）
Ｅ（Ｆ）は、この方程式を満たす点（ｘ，ｙ）∈Ｆ２と、Ｏと表記する「無限遠点」の集合を表す。もしＫがＦの拡大体であるなら、Ｅ（Ｋ）は式（１）を満たす（ｘ，ｙ）∈Ｋ２とＯの集合を表す。曲線（１）が楕円曲線であるためには、滑らかでなければならない。これは両方の偏導関数がともに０になるようなＥ（Ｆ￣）の点がないことを意味する（Ｆ￣はＦの代数的閉包を表す）。言い換えれば、２つの方程式
ａ１Ｙ＝３Ｘ２＋２ａ２Ｘ＋ａ４，  ２Ｙ＋ａ１Ｘ＋ａ３＝０      （２）
は、どの（ｘ，ｙ）∈Ｅ（Ｆ￣）によっても、同時に満たされることがない。
【００１５】
集合Ｅ（Ｆ）は単位元がＯであるアーベル群をなす。Ｆの任意の拡大体Ｋに対し、集合Ｅ（Ｋ）は単位元がＯであるアーベル群をなす。
【００１６】
楕円曲線暗号のために使われる楕円曲線は、有限体Ｆｑ（ＧＦ（ｑ）と書かれることもある）の上で定義されるものである。そして楕円曲線の方程式は、Ｆｑの標数ｐの違いによって異なるので、以下、ｐ＝２，ｐ＝３，ｐ＞３のそれぞれの場合について別々に扱うことにする。
【００１７】
［２．２］  標数ｐ＝２の場合
１．非超特異の場合
これは式（１）の左辺がＹ２＋ａ１ＸＹの場合で、一般性を失うことなくａ１＝１としてよく、楕円曲線Ｅの方程式を次のように与えることができる。
Ｙ２＋ＸＹ＝Ｘ３＋ａ２Ｘ２＋ａ６，  ａ２，ａ６∈Ｆ．      （３）
２．超特異の場合
これは楕円曲線Ｅの方程式を次のように与えることができる場合である。
Ｙ２＋ａ３Ｙ＝Ｘ３＋ａ４Ｘ＋ａ６，  ａ３，ａ４，ａ６∈Ｆ．      （４）
【００１８】
［２．３］  標数３の場合
標数３の体Ｆ上の楕円曲線Ｅの方程式を次のように与える。
Ｙ２＝Ｘ３＋ａ２Ｘ２＋ａ４Ｘ＋ａ６，  ａ２，ａ４，ａ６∈Ｆ．      （５）
【００１９】
［２．４］  標数ｐ≠２，３の場合
体Ｆ上の楕円曲線Ｅは、Ｆの標数が２でも３でもないなら、一般性を失うことなく次の形の方程式によって与えられる。
Ｙ２＝Ｘ３＋ａＸ＋ｂ，  ａ，ｂ∈Ｆ，ｃｈａｒＦ≠２，３．      （６）
ただし、Ｘ３＋ａＸ＋ｂの判別式−（４ａ３＋２７ｂ２）≠０である。
【００２０】
［２．５］  加法則
集合Ｅ（Ｆ）は単位元がＯであるアーベル群をなすことは前に述べた。この群における演算は次の加法則で与えられる。ここでは幾何的イメージが湧きやすいように、実数体Ｒ上の楕円曲線として話を進める。
【００２１】
定義
Ｅを式（６）で与えられる実数体上の楕円曲線とし、ＰとＱをＥ上の２点とする。Ｐの負および和Ｐ＋Ｑを、次の規則に従って定義する。
１）もしＰが無限遠点Ｏなら、−ＰをＯと定義する。任意の点Ｑに対し、Ｏ＋ＱをＱと定義する。すなわち、Ｏは点の群の加法単位元（「零元」）としての役割を果たす。以下では、ＰもＱも無限遠点でないと仮定する。
２）負−Ｐは、ｘ座標がＰと同じで、ｙ座標が逆符号の点である。すなわち、−（ｘ，ｙ）＝（ｘ，−ｙ）である。（ｘ，ｙ）が曲線上にあれば、（ｘ，−ｙ）も曲線上にあることは、式（６）から明らかである。もしＱ＝−Ｐなら、Ｐ＋Ｑを無限遠点Ｏと定義する。
３）もしＰとＱが異なるｘ座標をもてば、直線ｌ＝ＰＱ（２点Ｐ、Ｑを結ぶ直線）は、曲線とちょうどもう一つの点Ｒで交わる（もし直線ｌが曲線にＰで接するなら、Ｒ＝Ｐ、あるいはＱで接するなら、Ｒ＝Ｑととるが、そうでないとする）。このとき、Ｐ＋Ｑを−Ｒ、すなわち第３の交点の（ｘ軸に関する）鏡像と定義する。
４）最後の可能性はＰ＝Ｑである。このとき直線ｌをＰにおける曲線への接線とし、Ｒを直線ｌと曲線のただ一つの他の交点として、２Ｐ＝−Ｒと定義する。（もし接線がＰで「２重の接線」をもつなら、換言すれば、もしＰが変曲点なら、ＲをＰにとる。）
【００２２】
上の規則の組は、次のように簡潔に要約できる。
直線が曲線と交わる３点の和は零である。
【００２３】
もし直線が無限遠点Ｏを通るなら、この関係はＰ＋Ｐ〜＋Ｏ＝Ｏの形をもつ（ここでＰとＰ〜は対称な点である）、すなわち、Ｐ〜＝−Ｐである。そうでないなら、Ｐ＋Ｑ＋Ｒ＝Ｏの形をもつ。ただし、Ｐ、ＱとＲは規則３）あるいは４）の３点である。
【００２４】
（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）でそれぞれＰ、Ｑ、Ｐ＋Ｑの座標を表す。ｘ３とｙ３をｘ１，ｙ１，ｘ２，ｙ２で表したい。上のＰ＋Ｑの定義の規則３）と４）の場合、直線ｌの方程式をｙ＝λｘ＋νとする。
Ｐ≠Ｑの場合（加算公式）
ｘ３＝λ２−（ｘ１＋ｘ２）
ｙ３＝λ（ｘ１−ｘ３）−ｙ１
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）      （７）
Ｐ＝Ｑの場合（２倍点公式）
λがＰにおける導関数ｄｙ／ｄｘの値である以外、Ｐ≠Ｑの場合と同様である。Ｐの２倍点の座標の式は次のとおりである。
ｘ３＝λ２−２ｘ１
ｙ３＝λ（ｘ１−ｘ３）−ｙ１
λ＝（３ｘ１２＋ａ）／（２ｙ１）      （８）
【００２５】
記法ｎＰによって、もしｎが正なら、Ｐをそれ自身ｎ回加えることを、またもしｎが負なら、−Ｐをそれ自身｜ｎ｜回加えることを表す。
【００２６】
［２．６］  加算の計算量
Ｐ＋Ｑ＝（ｘ３，ｙ３）の計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で乗算、逆元算のコストをそれぞれＭ、Ｉで表す。なお平方算のコストをＳで表すが、多くの場合平方算と乗算のコストはほぼ同等と考えることができるので、ここではＳ≒Ｍとした式も示す。
【００２７】
Ｐ≠Ｑの場合
１．λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）の計算：
（ｘ２−ｘ１）−１の計算に逆元算のコストＩ。
これにｙ２−ｙ１をかける計算に乗算のコストＭ。
２．ｘ３＝λ２−（ｘ１＋ｘ２）の計算：
λ２の計算に平方算のコストＳ≒Ｍ。
３．ｙ３＝λ（ｘ１−ｘ３）−ｙ１の計算：
λをｘ１−ｘ３にかける計算に乗算のコストＭ。
以上の合計コストｔＡ＝１Ｉ＋２Ｍ＋Ｓ≒１Ｉ＋３Ｍ。なおｔＡの添え字ＡはＡｄｄｉｔｉｏｎ（加算）のつもりである。
【００２８】
Ｐ＝Ｑの場合
１．λ＝（３ｘ１２＋ａ）／（２ｙ１）の計算：
（２ｙ１）−１の計算に逆元算のコストＩ。
ｘ１２の計算に平方算のコストＳ≒Ｍ。
これに（２ｙ１）−１をかける計算に乗算のコストＭ。
２．ｘ３＝λ２−２ｘ１の計算：
λ２の計算に平方算のコストＳ≒Ｍ。
３．ｙ３＝λ（ｘ１−ｘ３）−ｙ１の計算：
λをｘ１−ｘ３にかける計算に乗算のコストＭ。
以上の合計コストｔＤ＝１Ｉ＋２Ｍ＋２Ｓ≒１Ｉ＋４Ｍ。なおｔＤの添え字ＤはＤｏｕｂｌｉｎｇ（２倍算）のつもりである。
【００２９】
まとめ
以上をまとめると、ＦｑにおけるＰ＋Ｑの計算コストは次のとおりである。ただしＦｑの標数はｐ＞３であり、また計算にはアフィン座標系を使うものとする。
一般の加算の場合、計算量ｔＡ＝１Ｉ＋２Ｍ＋Ｓ≒．１Ｉ＋３Ｍ
２倍算の場合、計算量ｔＤ＝１Ｉ＋２Ｍ＋２Ｓ＝ｔＡ＋１Ｓ≒ｔＡ＋１Ｍ
【００３０】
［３］  ３倍点公式
我々の方法は点の３倍算を使う。よって３倍点３Ｐ＝（ｘｔ，ｙｔ）の座標をＰ＝（ｘ１，ｙ１）の座標で表したい。
［３．１］  ３倍点公式の導出
まず２倍点Ｐｄ＝２Ｐ＝２（ｘ１，ｙ１）＝（ｘｄ，ｙｄ）を求める。
ｘｄ＝λ２−２ｘ１
ｙｄ＝λ（ｘ１−ｘｄ）−ｙ１
λ＝（３ｘ１２＋ａ）／（２ｙ１）      （９）
【００３１】
次に３倍点を３Ｐ＝Ｐ＋Ｐｄとして求める。Ｐの３倍点３Ｐ＝（ｘｔ，ｙｔ）の座標は次で与えられる。式（７）においてｘ１，ｙ１，ｘ２，ｙ２，ｘ３，ｙ３，λをそれぞれｘ１，ｙ１，ｘｄ，ｙｄ，ｘｔ，ｙｔ，μで置き換える。その上でさらに、ｘｔの式の右辺のｘｄに式（９）の第１式を代入する。
ｘｔ＝μ２−（ｘ１＋ｘｄ）
＝μ２−λ２＋ｘ１
ｙｔ＝μ（ｘ１−ｘｔ）−ｙ１
μ＝（ｙｄ−ｙ１）／（ｘｄ−ｘ１）      （１０）
＝｛λ（ｘ１−ｘｄ）−ｙ１−ｙ１｝／（λ２−２ｘ１−ｘ１）
＝｛λ（ｘ１−λ２＋２ｘ１）−２ｙ１｝／（λ２−３ｘ１）
＝−λ−２ｙ１／（λ２−３ｘ１）      （１１）
【００３２】
３倍点公式：まとめ
ｘｔ＝μ２−λ２＋ｘ１
ｙｔ＝μ（ｘ１−ｘｔ）−ｙ１
λ＝（３ｘ１２＋ａ）／（２ｙ１），μ＝−λ−２ｙ１／（λ２−３ｘ１）      （１２）
【００３３】
［３．２］  ２進法と３進法の適用例
［例：１００Ｐ  の計算］
１００＝１１００１００（２）＝１０２０１（３）
２進法の場合
１）２Ｐ＋Ｐ＝３Ｐ
０）２（３Ｐ）＝６Ｐ
０）２（６Ｐ）＝１２Ｐ
１）２（１２Ｐ）＋Ｐ＝２５Ｐ
０）２（２５Ｐ）＝５０Ｐ
０）２（５０Ｐ）＝１００Ｐ
３進法の場合
０）３Ｐ
２）３（３Ｐ）＋２Ｐ＝１１Ｐ
０）３（１１Ｐ）＝３３Ｐ
１）３（３３Ｐ）＋Ｐ＝１００Ｐ
【００３４】
［３．３］  ３倍算の計算量
点Ｐの３倍算すなわち３Ｐを求める計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で乗算、逆元算のコストをそれぞれＭ、Ｉで表わす。なお平方算のコストをＳで表すが、ここではＳ≒Ｍとする式も示す。
１．λ＝（３ｘ１２＋ａ）／（２ｙ１）の計算：
（２ｙ１）−１の計算に逆元算のコストＩ。
ｘ１２の計算に平方算のコストＳ≒Ｍ。
これに（２ｙ１）−１をかける計算に乗算のコストＭ。
２．λ２の計算に平方算のコストＳ≒Ｍ。
３．μ＝−λ−２ｙ１／（λ２−３ｘ１）の計算：
（λ２−３ｘ１）−１の計算に逆元算のコストＩ。
これに２ｙ１をかける計算に乗算のコストＭがかかる。
４．μ２の計算：
平方算のコストＳ≒Ｍ。
５．ｙｔの計算：
μをｘ１−ｘｔにかける計算に乗算のコストＭ。
以上の合計コストｔＴ＝２Ｉ＋３Ｍ＋３Ｓ≒２Ｉ＋６Ｍ＝２ｔＡ。ここでｔＴの添え字ＴはＴｒｉｐｌｉｎｇ（３倍算）のつもりである。なお２Ｐを求めてからＰを加算して３Ｐを求めると、計算量はｔＴ’＝ｔＡ＋ｔＤ＝２ｔＡ＋１Ｓ＝ｔＴ＋１Ｍであることに注意する。したがって、３倍算公式の使用で計算量をＭだけ節約できる。
【００３５】
［４］  ｋ倍算の計算量：標数ｐ＞３の場合
２倍算公式を使うときと、３倍算公式を使うときの計算量を比較する。
【００３６】
［４．１］  ２進法とその計算量：標数ｐ＞３の場合
入力：点Ｐと整数ｋ
出力：点Ｑ＝ｋＰ
アルゴリズム：
１．ｋを２進展開する。ｋ＝ｋｌ−１ｋｌ−２…ｋ１ｋ０（２）。ただしｌ（エル）はｋのビット数でｋｌ−１＝１である。
２．Ｑ＝Ｐとしてｊ＝ｌ−２，…，０に対して次を行う。
（２ａ）Ｑ←２Ｑ
（２ｂ）ｋｊ＝１ならＱ←Ｑ＋Ｐ
【００３７】
２進法の計算量：
１．の２進展開のコストは無視する。
２．の（２ａ）は２倍算であるからその計算量はｔＤ＝ｔＡ＋１Ｓである。
２．の（２ｂ）は一般の加算であるからその計算量はｔＡ＝１Ｉ＋２Ｍ＋１Ｓである。
【００３８】
ところで２倍算はｌ−１回、加算はｗ−１回行うから、２進法によるｋＰの計算量ｔ２は次のとおりである。ただしｗはｋの２進展開におけるハミング重み（すなわち非零桁の個数）である。
ｔ２＝（ｌ−１）ｔＤ＋（ｗ−１）ｔＡ
＝（ｌ−１）（ｔＡ＋１Ｓ）＋（ｗ−１）ｔＡ
＝（ｌ＋ｗ−２）ｔＡ＋（ｌ−１）Ｓ
＝（ｌ＋ｗ−２）Ｉ＋（２ｌ＋２ｗ−４）Ｍ＋（２ｌ＋ｗ−３）Ｓ
≒（ｌ＋ｗ−２）Ｉ＋（４ｌ＋３ｗ−７）Ｍ      （１３）
ｌはｋのビット数だけで決まるがｗはｗ＝１からｗ＝ｌまであり得る。ゆえに
（ｌ−１）（ｔＡ＋Ｓ）≦ｔ２≦（ｌ−１）（２ｔＡ＋Ｓ）      （１４）
ｔＡ＋Ｓ≦ｔ２／（ｌ−１）≦２ｔＡ＋Ｓ      （１５）
である。また平均としてｗ＝ｌ／２とし、ｌ≫１とすれば
ｔ２￣＝（ｌ／２）（３ｔＡ＋２Ｓ）      （１６）
さらにｔＡ＝１Ｉ＋２Ｍ＋Ｓ、Ｓ≒Ｍとすれば
ｔ２￣＝（ｌ／２）（３Ｉ＋１１Ｍ）      （１７）
ここで典型的にＩ＝３Ｍならｔ２￣＝１０ｌＭ、Ｉ＝１１Ｍならｔ２￣＝２２ｌＭとなる。
【００３９】
［４．２］  ３進法とその計算量：標数ｐ＞３の場合
入力：点Ｐと整数ｋ
出力：点Ｑ＝ｋＰ
アルゴリズム：
０．Ｐｄ＝２Ｐを予め計算し記憶する。
１．ｋを３進展開する。ｋ＝ｈｉ−１ｈｉ−２…ｈ１ｈ０（３）。ただしｉはｋの３進桁数でｈｉ−１＞０である。
２．ｈｉ−１＝１ならＱ←Ｐ、ｈｉ−１＝２ならＱ←Ｐｄとしてｊ＝ｉ−２，…，０に対して次を行う。
（２ａ）Ｑ←３Ｑ
（２ｂ）ｈｊ＝１ならＱ←Ｑ＋Ｐ
（２ｃ）ｈｊ＝２ならＱ←Ｑ＋Ｐｄ
【００４０】
３進法の計算量：
０．Ｐｄ＝２Ｐの予備計算のコストは無視する。
１．の３進展開のコストは無視する。
２．の（２ａ）は３倍算であるからその計算量はｔＴ＝２Ｉ＋３Ｍ＋３Ｓ≒２ｔＡである。
２．の（２ｂ）、（２ｃ）は一般の加算であるからその計算量はｔＡ＝１Ｉ＋２Ｍ＋１Ｓである。
【００４１】
ところで３倍算はｉ−１回、加算はｗ−１回行うから、３進法によるｋＰの計算量ｔ３は次のとおりである。ただしｗはｋの３進展開におけるハミング重み（すなわち非零桁の個数）である。
ｔ３＝（ｉ−１）ｔＴ＋（ｗ−１）ｔＡ
＝（ｉ−１）（２Ｉ＋３Ｍ＋３Ｓ）＋（ｗ−１）（１Ｉ＋２Ｍ＋１Ｓ）
＝（２ｉ＋ｗ−３）Ｉ＋（３ｉ＋２ｗ−５）Ｍ＋（３ｉ＋ｗ−４）Ｓ
≒（２ｉ＋ｗ−３）（１Ｉ＋３Ｍ）≒（２ｉ＋ｗ−３）ｔＡ      （１８）
ｉはｋの３進桁数だけで決まるがｗはｗ＝１からｗ＝ｉまであり得る。ゆえにｔ３≒（２ｉ＋ｗ−３）ｔＡの近似を使えば、
２（ｉ−１）ｔＡ≦ｔ３≦３（ｉ−１）ｔＡ      （１９）
２ｔＡ≦ｔ３／（ｉ−１）≦３ｔＡ      （２０）
である。また平均としてｗ＝２ｉ／３とし、ｉ≫１とすれば
ｔ３￣＝（８ｉ／３）ｔＡ      （２１）
さらにｔＡ＝１Ｉ＋２Ｍ＋Ｓ、Ｓ≒Ｍとすれば
ｔ３￣＝（８ｉ／３）（１Ｉ＋３Ｍ）      （２２）
ここで典型的にＩ＝３Ｍならｔ３￣＝１６ｉＭ，Ｉ＝１１Ｍならｔ３￣＝（１１２ｉ／３）Ｍとなる。
【００４２】
［５］  ２進法と３進法の選択による高速化
これまでに２進法と３進法によるｋ倍算の計算量ｔ２とｔ３を見積もった。両者のどちらが小さいかはｋを展開したときの重みｗ２、ｗ３すなわち非零桁数に依存する。したがってｋが与えられるとき、まずこれを２進法と３進法とで展開し、ｔ２とｔ３の大小関係によって２進法と３進法のいずれかを選択することで高速化を図ることができると考えられる。
【００４３】
［５．１］  ２進法と３進法の計算量の比較
平均値の比較
平均値ｔ３￣とｔ２￣の比ｔ￣＝ｔ３￣／ｔ２￣は式（２２）、（１７）により次のとおりである。
ｔ￣＝ｔ３￣／ｔ２￣＝１６ｉ（１Ｉ＋３Ｍ）／｛３ｌ（３Ｉ＋１１Ｍ）｝
＝１６ｉ（ｄ＋３）／｛３ｌ（３ｄ＋１１）｝      （２３）
ただしｄ＝Ｉ／Ｍは逆元算と乗算の計算時間の比である。そこでｔ￣＜１となるｄ＝Ｉ／Ｍの条件を求めよう。ｃ＝ｌ／ｉ＝ｌｏｇ２３＝１．５８５を使うと
ｄ＝Ｉ／Ｍ＜（３３ｃ−４８）／（１６−９ｃ）＝２．４８０      （２４）
である。すなわちＩ＜２．４８０Ｍのとき、ｔ３￣＜ｔ２￣となる。
【００４４】
一般の場合の比較
ｔ３とｔ２の比ｔ＝ｔ３／ｔ２は式（１３）、（１８）により次のとおりである。ただしｗ２’＝ｗ２／ｌ、ｗ３’＝ｗ３／ｉは相対重みである。
ｔ＝ｔ３／ｔ２
＝（２ｉ＋ｗ３−３）（ｄ＋３）／｛（ｌ＋ｗ２−２）ｄ＋４ｌ＋３ｗ２−７｝
＝｛（２＋ｗ３’−３ｃ／ｌ）（ｄ＋３）／ｃ｝／｛（１＋ｗ２’−２／ｌ）ｄ＋４＋３ｗ２’−７／ｌ｝      （２５）
通常ｌは十分大きいから上の式で１／ｌの項を省略すると
ｔ＝｛（２＋ｗ３’）（ｄ＋３）／ｃ｝／｛（１＋ｗ２’）ｄ＋４＋３ｗ２’｝  （２６）
式（２６）でｔ＜１となるｗ２’、ｗ３’、ｄに関する条件を求めれば、ｔ３＜ｔ２となる数ｋを求めることができる。ただしｄは予め決まっている数である。式（２６）の近似を用いれば、
ｗ３’＜ｃｗ２’−｛（２−ｃ）ｄ＋６−４ｃ｝／（ｄ＋３）      （２７）
となる。
【００４５】
ここでは典型的なｄの値に対して、上の条件を求める。
ｄ＝３の場合：
ｔ＜１となるためには
ｗ３’＜ｃｗ２’＋（７／６）ｃ−２＝１．５８５ｗ２’−０．１５０９      （２８）
でなければならない。ただし０＜ｗ２’，ｗ３’≦１を考慮すると、ｔ＜１となる条件は
条件Ｔｅｒ
０．０９５２＜ｗ２’＜０．７２６１      （２９）
かつ式（２８）が成り立つ。      （３０）
【００４６】
ｄ＝１１の場合：
ｔ＜１となるためには
ｗ３’＜ｃｗ２’＋（１５／１４）ｃ−２＝１．５８５ｗ２’−０．３０１８    （３１）
でなければならない。０＜ｗ２’，ｗ３’≦１を考慮すると、ｔ＜１となる条件は
条件Ｔｅｒ
０．１９０＜ｗ２’＜０．８２１３      （３２）
かつ式（３１）が成り立つ。      （３３）
【００４７】
［５．２］  提案法−選択的２進・３進法
入力：点Ｐと整数ｋ
出力：点Ｑ＝ｋＰ
アルゴリズム：
１．ｋを２進および３進展開する。それぞれにおける桁数ｌとｉ、重みｗ２とｗ３、また相対重みｗ２’とｗ３’を求める。
２．（２ａ）条件Ｔｅｒが成立するなら３進法による計算を行う。
（２ｂ）条件Ｔｅｒが成立しないなら２進法による計算を行う。
【００４８】
［５．３］  ２進法と３進法の計算量の例
［例１：１００Ｐの計算］
１００＝１１００１００（２）＝１０２０１（３）
２進法の場合
２倍算Ｄと加算Ａの列はＤＡＤＤＤＡＤＤとなるから、
ｔ２＝２ｔＡ＋６ｔＤ＝２（１，２，１）＋６（１，２，２）＝（８，１６，１４）となる。ただし、コストを（Ｉ，Ｍ，Ｓ）で表記している。
３進法の場合
３倍算Ｔと加算Ａの列はＴＴＡＴＴＡとなるから、
ｔ３＝２ｔＡ＋４ｔＴ＝２（１，２，１）＋４（２，３，３）＝（１０，１６，１４）となる。
この例では３進法のほうが逆元算２回だけ多い。
【００４９】
［例２：９０Ｐの計算］
９０＝１０１１０１０（２）＝１０１００（３）
２進法の場合
２倍算Ｄと加算Ａの列はＤＤＡＤＡＤＤＡＤとなるから、
ｔ２＝３ｔＡ＋６ｔＤ＝３（１，２，１）＋６（１，２，２）＝（９，１８，１５）となる。
３進法の場合
３倍算Ｔと加算Ａの列はＴＴＡＴＴとなるから、
ｔ３＝２ｔＡ＋４ｔＴ＝（１，２，１）＋３（２，３，３）＝（７，１１，１０）となる。
この例では平方算を乗算とみなすと、３進法のほうが逆元算２回と乗算が１２回だけ少ない。計算量の削減率をδ＝（ｔ２−ｔ３）／ｔ３で表すと、ｄ＝Ｉ／Ｍ＝３のときδ＝３０％、ｄ＝Ｉ／Ｍ＝１１のときδ＝２５％となる。
【００５０】
［６］  楕円曲線：標数３の場合
標数３の体Ｆ上の楕円曲線Ｅの方程式を次のように与える。
Ｙ２＝Ｘ３＋ａ２Ｘ２＋ａ４Ｘ＋ａ６，  ａ２，ａ４，ａ６∈Ｆ．      （３４）
【００５１】
［６．１］  加法公式：標数３の場合
前と同じく（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）でそれぞれＰ、Ｑ、Ｐ＋Ｑの座標を表す。ｘ３とｙ３をｘ１，ｙ１，ｘ２，ｙ２で表したい。
Ｐ≠Ｑの場合（加算公式）
ｘ３＝λ２−ａ２−（ｘ１＋ｘ２）
ｙ３＝λ（ｘ１−ｘ３）−ｙ１
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）      （３５）
【００５２】
Ｐ＝Ｑの場合（２倍点公式）
λがＰにおける導関数ｄｙ／ｄｘの値である以外、Ｐ≠Ｑの場合と同様である。Ｐの２倍点の座標の式は次のとおりである。
ｘ３＝λ２−ａ２−２ｘ１＝λ２−ａ２＋ｘ１
ｙ３＝λ（ｘ１−ｘ３）−ｙ１
λ＝（３ｘ１２＋２ａ２ｘ１＋ａ４）／（２ｙ１）＝（ａ２ｘ１−ａ４）／ｙ１      （３６）
なお２倍点の座標であることを明示するために、この場合の（ｘ３，ｙ３）を（ｘｄ，ｙｄ）と表すこともある。
【００５３】
３倍点公式
Ｐ＝（ｘ１，ｙ１）、２Ｐ＝（ｘｄ，ｙｄ）、３Ｐ＝（ｘｔ，ｙｔ）として、３倍点３Ｐ＝（ｘｔ，ｙｔ）＝（ｘ１，ｙ１）＋（ｘｄ，ｙｄ）を求める。３Ｐの座標は次で与えられる。
ｘｔ＝μ２−λ２＋ｘ１
ｙｔ＝μ（ｘ１−ｘｔ）−ｙ１
λ＝（ａ２ｘ１−ａ４）／ｙ１，  μ＝−λ＋ｙ１／（λ２−ａ２）      （３７）
【００５４】
［６．２］  加算の計算量：標数３の場合
Ｐ＋Ｑ＝（ｘ３，ｙ３）の計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で平方算、乗算、逆元算のコストをそれぞれＳ、Ｍ、Ｉで表す。
Ｐ≠Ｑの場合
１．λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）の計算：
（ｘ２−ｘ１）−１の計算に逆元算のコストＩ。
これにｙ２−ｙ１をかける計算に乗算のコストＭ。
２．ｘ３＝λ２−ａ２−（ｘ１＋ｘ２）の計算：
λ２の計算に平方算のコストＳ．
３．ｙ３＝λ（ｘ１−ｘ３）−ｙ１の計算：
λをｘ１−ｘ３にかける計算に乗算のコストＭ。
以上の合計コストｔＡ＝１Ｉ＋２Ｍ＋１Ｓ。なおｔＡの添え字ＡはＡｄｄｉｔｉｏｎ（加算）のつもりである。
【００５５】
Ｐ＝Ｑの場合
１．λ＝（ａ２ｘ１−ａ４）／ｙ１の計算：
ｙ１−１の計算に逆元算のコストＩ。
ａ２ｘ１−ａ４の計算に乗算のコストＭ。
これにｙ１−１  をかける計算に乗算のコストＭ。
２．ｘ３＝λ２−ａ２＋ｘ１の計算：
λ２の計算に平方算のコストＳ。
３．ｙ３＝λ（ｘ１−ｘ３）−ｙ１の計算：
λをｘ１−ｘ３にかける計算に乗算のコストＭ。
以上の合計コストｔＤ＝１Ｉ＋３Ｍ＋１Ｓ。なおｔＤの添え字ＤはＤｏｕｂｌｉｎｇ（２倍算）のつもりである。
【００５６】
まとめ
以上をまとめると、標数３の有限体ＦｑにおけるＰ＋Ｑの計算コストは次のとおりである。計算にはアフィン座標系を使うものとする。
一般の加算の場合、計算量ｔＡ＝１Ｉ＋２Ｍ＋１Ｓ
２倍算の場合、計算量ｔＤ＝１Ｉ＋３Ｍ＋１Ｓ＝ｔＡ＋１Ｍ
Ｍ≒Ｓの場合には、標数＞３の場合と同じ計算量となることに注意する。
【００５７】
［６．３］  ３倍算の計算量
点Ｐの３倍算すなわち３Ｐを求める計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で乗算、逆元算のコストをそれぞれＭ、Ｉで表わす。なお平方算のコストをＳで表すが、ここではＳ≒Ｍとする。
１．λ＝（ａ２ｘ１−ａ４）／ｙ１の計算：
前出の通りコストは１Ｉ＋２Ｍ。
２．μ＝−λ＋ｙ１／（λ２−ａ２）の計算：
λ２の計算に平方算のコストＳ。
（λ２−ａ２）−１の計算に逆元算のコストＩ。
これにｙ＝１をかける計算に乗算のコストＭ。
３．ｘｔの計算：
μ２の計算に平方算のコストＳ。
４．ｙｔの計算：
μをｘ１−ｘｔにかける計算に乗算のコストＭ。
以上の合計コストｔＴ＝２Ｉ＋４Ｍ＋２Ｓ＝２ｔＡ。Ｍ≒Ｓの場合には、標数＞３の場合と同じ計算量となることに注意する。なお２Ｐを求めてからＰを加算して３Ｐを求めると、計算量はｔＴ’＝ｔＡ＋ｔＤ＝２ｔＡ＋Ｍ＝ｔＴ＋Ｍであり、この関係は標数＞３の場合と同じであることに注意する。
【００５８】
［７］  ｋ倍算の計算量：標数３の場合
２倍算公式を使うときと、３倍算公式を使うときの計算量を比較する。
【００５９】
［７．１］  ２進法とその計算量：標数３の場合
入力：点Ｐと整数ｋ
出力：点Ｑ＝ｋＰ
アルゴリズム：
１．ｋを２進展開する。ｋ＝ｋｌ−１ｋｌ−２…ｋ１ｋ０（２）。ただしｌはｋのビット数でｋｌ−１＝１である。
２．Ｑ＝０としてｊ＝ｌ−１，…，０に対して次を行う。
（２ａ）Ｑ←２Ｑ
（２ｂ）ｋｊ＝１ならＱ←Ｑ＋Ｐ
【００６０】
２進法の計算量：
１．の２進展開のコストは無視する。
２．の（２ａ）は２倍算であるからその計算量はｔＤ＝ｔＡ＋１Ｓである。
２．の（２ｂ）は一般の加算であるからその計算量はｔＡ＝１Ｉ＋２Ｍ＋１Ｓである。
【００６１】
ところで２倍算はｌ−１回、加算はｗ−１回行うから、２進法によるｋＰの計算量ｔ２は次のとおりである。
ｔ２＝（ｌ−１）ｔＤ＋（ｗ−１）ｔＡ
＝（ｌ−１）（ｔＡ＋１Ｍ）＋（ｗ−１）ｔＡ
＝（ｌ＋ｗ−２）ｔＡ＋（ｌ−１）Ｓ
＝（ｌ＋ｗ−２）Ｉ＋（３ｌ＋２ｗ−５）Ｍ＋（ｌ＋ｗ−２）Ｓ
≒（ｌ＋ｗ−２）Ｉ＋（４ｌ＋３ｗ−７）Ｍ      （３８）
ｌはｋのビット数だけで決まるがｗはｗ＝１からｗ＝ｌまであり得る。ゆえに
（ｌ−１）（ｔＡ＋Ｍ）≦ｔ２≦（ｌ−１）（２ｔＡ＋Ｍ）      （３９）
ｔＡ＋Ｍ≦ｔ２／（ｌ−１）≦２ｔＡ＋Ｍ      （４０）
である。また平均としてｗ＝ｌ／２とし、ｌ≫１とすれば
ｔ２￣＝（ｌ／２）（３ｔＡ＋２Ｍ）      （４１）
さらにｔＡ＝１Ｉ＋２Ｍ＋Ｓ、Ｓ≒Ｍとすれば
ｔ２￣＝（ｌ／２）（３Ｉ＋１１Ｍ）      （４２）
ここで典型的にＩ＝３Ｍならｔ２￣＝１０ｌＭ、Ｉ＝１１Ｍならｔ２￣＝２２ｌＭとなる。
【００６２】
［７．２］  ３進法とその計算量：標数３の場合
入力：点Ｐと整数ｋ
出力：点Ｑ＝ｋＰ
アルゴリズム：
０．Ｐｄ＝２Ｐを予め計算し記憶する。
１．ｋを３進展開する。ｋ＝ｈｉ−１ｈｉ−２…ｈ１ｈ０（３）。ただしｉはｋの３進桁数でｈｉ−１＞０である。
２．Ｑ＝０としてｊ＝ｉ−１，…，０に対して次を行う。
（２ａ）Ｑ←３Ｑ
（２ｂ）ｉｊ＝１ならＱ←Ｑ＋Ｐ
（２ｃ）ｉｊ＝２ならＱ←Ｑ＋Ｐｄ
【００６３】
３進法の計算量：
０．のＰｄ＝２Ｐの予備計算のコストは無視する。
１．の３進展開のコストは無視する。
２．の（２ａ）は３倍算であるからその計算量はｔＴ＝２Ｉ＋４Ｍ＋２Ｓ＝２ｔＡである。
２．の（２ｂ）、（２ｃ）は一般の加算であるからその計算量はｔＡ＝１Ｉ＋２Ｍ＋１Ｓである。
【００６４】
ところで３倍算はｉ−１回、加算はｗ−１回行うから、３進法によるｋＰの計算量ｔ３は次のとおりである。
ｔ３＝（ｉ−１）ｔＴ＋（ｗ−１）ｔＡ
＝（ｉ−１）２ｔＡ＋（ｗ−１）ｔＡ＝（２ｉ＋ｗ−３）ｔＡ
＝（２ｉ＋  ｗ−３）（１Ｉ＋２Ｍ＋１Ｓ）      （４３）
ｉはｋの３進桁数だけで決まるがｗはｗ＝１からｗ＝ｉまであり得る。
２（ｉ−１）ｔＡ≦ｔ３≦３（ｉ−１）ｔＡ      （４４）
２ｔＡ≦ｔ３／（ｉ−１）≦３ｔＡ      （４５）
である。また平均としてｗ＝２ｉ／３とし、ｉ≫１とすれば
ｔ３￣＝（８ｉ／３）ｔＡ      （４６）
さらにｔＡ＝１Ｉ＋２Ｍ＋Ｓ、Ｓ≒Ｍとすれば
ｔ３￣＝（８ｉ／３）（１Ｉ＋３Ｍ）      （４７）
ここで典型的にＩ＝３Ｍならｔ３￣＝１６ｉＭ、Ｉ＝１１Ｍならｔ３￣＝（１１２ｉ／３）Ｍとなる。
【００６５】
［７．３］  ２進法と３進法の選択による高速化
これまでに２進法と３進法によるｋ倍算の計算量ｔ２とｔ３を見積もった。両者のどちらが小さいかはｋを展開したときの重みｗ２、ｗ３すなわち非零桁数に依存する。したがってｋが与えられるとき、まずこれを２進法と３進法とで展開し、ｔ２とｔ３の大小関係によって２進法と３進法のいずれかを選択することで高速化を図ることができると考えられる。
【００６６】
［７．４］  ２進法と３進法の計算量の比較
平均値の比較（結果は標数３の場合と同じ）
平均値ｔ３￣とｔ２￣の比ｔ￣＝ｔ３￣／ｔ２￣は式（４２）、（４７）により次のとおりである。
ｔ￣＝ｔ３￣／ｔ２￣＝１６ｉ（１Ｉ＋３Ｍ）／｛３ｌ（３Ｉ＋１１Ｍ）｝
＝１６ｉ（ｄ＋３）／｛３ｌ（３ｄ＋１１）｝      （４８）
ゆえにｔ￣＜１となるｄ＝Ｉ／Ｍの条件を求め、ｃ＝ｌ／ｉ＝ｌｏｇ２３＝１．５８５を使うと
ｄ＝Ｉ／Ｍ＜（３３ｃ−４８）／（１６−９ｃ）＝２．４８０      （４９）
である。すなわちＩ＜２．４８０Ｍのとき、ｔ３￣＜ｔ２￣となる。
【００６７】
一般の場合の比較（結果は標数３の場合と同じ）
ｔ３とｔ２の比ｔ＝ｔ３／ｔ２は式（３８）、（４３）により次のとおりである。ただしｗ２’＝ｗ２／ｌ、ｗ３’＝ｗ３／ｉは相対重みである。
ｔ＝ｔ３／ｔ２
＝（２ｉ＋ｗ３−３）（ｄ＋３）／｛（ｌ＋ｗ２−２）ｄ＋４ｌ＋３ｗ２−７｝
＝｛（２＋ｗ３’−３ｃ／ｌ）（ｄ＋３）／ｃ｝／｛（１＋ｗ２’−２／ｌ）ｄ＋４＋３ｗ２’−７／ｌ｝      （５０）
通常ｌは十分大きいから上の式で１／ｌの項を省略すると
ｔ＝｛（２＋ｗ３’）（ｄ＋３）／ｃ｝／｛（１＋ｗ２’）ｄ＋４＋３ｗ２’｝  （５１）
式（５１）でｔ＜１となるｗ２’、ｗ３’、ｄに関する条件を求めれば、ｔ３＜ｔ２となる数ｋを求めることができる。ただしｄは予め決まっている数である。式（５１）の近似を用いれば、
ｗ３’＜ｃｗ２’−｛（２−ｃ）ｄ＋６−４ｃ｝／（ｄ＋３）      （５２）
となる。
【００６８】
ここでは典型的なｄの値に対して、上の条件を求める。
ｄ＝３の場合：
ｔ＜１となるためには
ｗ３’＜ｃｗ２’＋（７／６）ｃ−２＝１．５８５ｗ２’−０．１５０９      （５３）
でなければならない。ただし０＜ｗ２’，ｗ３’≦１を考慮すると、ｔ＜１となる条件は
条件Ｔｅｒ
０．０９５２＜ｗ２’＜０．７２６１      （５４）
かつ式（５３）が成り立つ。      （５５）
【００６９】
ｄ＝１１の場合：
ｔ＜１となるためには
ｗ３’＜ｃｗ２’＋（１５／１４）ｃ−２＝１．５８５ｗ２’−０．３０１８    （５６）
でなければならない。０＜ｗ２’，ｗ３’≦１を考慮すると、ｔ＜１となる条件は
０．１９０＜ｗ２’＜０．８２１３      （５７）
かつ式（５６）が成り立つ。      （５８）
【００７０】
［７．５］  提案法−選択的２進・３進法
入力：点Ｐと整数ｋ
出力：点Ｑ＝ｋＰ
アルゴリズム：
１．ｋを２進および３進展開する。それぞれにおける桁数ｌとｉ、重みｗ２とｗ３、また相対重みｗ２’とｗ３’を求める。
２．（２ａ）条件Ｔｅｒが成立するなら３進法による計算を行う。
（２ｂ）条件Ｔｅｒが成立しないなら２進法による計算を行う。
【００７１】
［８］  楕円曲線：標数２で非超特異の場合
標数２の体Ｆ上の非超特異な楕円曲線Ｅの方程式を次のように与える。
Ｙ２＋ＸＹ＝Ｘ３＋ａ２Ｘ２＋ａ６，  ａ２，ａ６∈Ｆ．      （５９）
【００７２】
［８．１］  非超特異の場合：加法公式
前と同じく（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）でそれぞれＰ、Ｑ、Ｐ＋Ｑの座標を表す。ｘ３とｙ３をｘ１，ｙ１，ｘ２，ｙ２で表したい。
Ｐ≠Ｑの場合（加算公式）
ｘ３＝λ２＋λ＋ｘ１＋ｘ２＋ａ２
ｙ３＝λ（ｘ１＋ｘ３）＋ｘ３＋ｙ１
λ＝（ｙ１＋ｙ２）／（ｘ１＋ｘ２）      （６０）
【００７３】
Ｐ＝Ｑの場合（２倍点公式）
λがＰにおける導関数ｄｙ／ｄｘの値である以外、Ｐ≠Ｑの場合と同様である。Ｐの２倍点の座標の式は次のとおりである。
ｘ３＝ｘ１２＋ａ６／ｘ１２
ｙ３＝ｘ１２＋λｘ３＋ｘ３
λ＝ｘ１＋ｙ１／ｘ１      （６１）
なお２倍点の座標であることを明示するために、この場合の（ｘ３，ｙ３）を（ｘｄ，ｙｄ）と表すこともある。
【００７４】
３倍点公式
Ｐ＝（ｘ１，ｙ１）、２Ｐ＝（ｘｄ，ｙｄ）、３Ｐ＝（ｘｔ，ｙｔ）として、３倍点３Ｐ＝（ｘｔ，ｙｔ）＝（ｘ１，ｙ１）＋（ｘｄ，ｙｄ）を求める。３Ｐの座標は次で与えられる。
ｘｔ＝μ２＋μ＋ｘ１＋ｘ１２＋ａ６／ｘ１２＋ａ２
ｙｔ＝μ（ｘ１＋ｘｔ）＋ｘｔ＋ｙ１
λ＝ｘ１＋ｙ１／ｘ１，  μ＝λ＋（ｘ１２＋ａ６）／（ｘ１＋ｘ１２＋ａ６）      （６２）
【００７５】
［８．２］  非超特異の場合：加算の計算量
Ｐ＋Ｑ＝（ｘ３，ｙ３）の計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で平方算、乗算、逆元算のコストをそれぞれＳ、Ｍ、Ｉで表す。
Ｐ≠Ｑの場合
１．λ＝（ｙ１＋ｙ２）／（ｘ１＋ｘ２）の計算：
（ｘ１＋ｘ２）−１の計算に逆元算のコストＩ。
これにｙ１＋ｙ２をかける計算に乗算のコストＭ。
２．ｘ３＝λ２＋λ＋ｘ１＋ｘ２＋ａ２の計算：
λ２の計算に平方算のコストＳ。
３．ｙ３＝λ（ｘ１＋ｘ３）＋ｘ３＋ｙ１の計算：
λをｘ１＋ｘ３にかける計算に乗算のコストＭ。
以上の合計コストｔＡ＝１Ｉ＋２Ｍ＋１Ｓ。なおｔＡの添え字ＡはＡｄｄｉｔｉｏｎ（加算）のつもりである。
【００７６】
Ｐ＝Ｑの場合
１．λ＝ｘ１＋ｙ１／ｘ１の計算：
ｘ１−１の計算に逆元算のコストＩ。
ｙ１／ｘ１の計算に乗算のコストＭ。
２．ｘ３＝ｘ１２＋ａ６／ｘ１２の計算：
ｘ１２の計算に平方算のコストＳ。
（ｘ１−１）２の計算に平方算のコストＳ。
これにａ６をかける計算に乗算のコストＭ。
３．ｙ３＝ｘ１２＋λｘ３＋ｘ３の計算：
λをｘ３にかける計算に乗算のコストＭ。
以上の合計コストｔＤ＝１Ｉ＋３Ｍ＋１Ｓ＝ｔＡ＋Ｍ。なおｔＤの添え字ＤはＤｏｕｂｌｉｎｇ（２倍算）のつもりである。
【００７７】
まとめ
以上をまとめると、標数２の有限体Ｆｑ上で定義された非超特異な楕円曲線におけるＰ＋Ｑの計算コストは次のとおりである。計算にはアフィン座標系を使うものとする。
一般の加算の場合、計算量ｔＡ＝１Ｉ＋２Ｍ＋１Ｓ
２倍算の場合、計算量ｔＤ＝１Ｉ＋３Ｍ＋１Ｓ＝ｔＡ＋１Ｍ
【００７８】
［８．３］  ３倍算の計算量：非超特異の場合
点Ｐの３倍算すなわち３Ｐを求める計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で乗算、逆元算のコストをそれぞれＭ、Ｉで表わす。なお平方算のコストをＳで表すが、ここではＳ≒Ｍとする。
１．λの計算：
前出の通りコストは１Ｉ＋１Ｍ。
２．μの計算：
コストは計１Ｉ＋２Ｍ＋２Ｓ。
３．ｘｔの計算：
μ２の計算に平方算のコストＳ。
４．ｙｔの計算：
μをｘ１＋ｘｔにかける計算に乗算のコストＭ。
以上の合計コストｔＴ＝２Ｉ＋４Ｍ＋３Ｓ＝２ｔＡ＋１Ｓ。なお２Ｐを求めてからＰを加算して３Ｐを求めると、計算量はｔＴ’＝ｔＡ＋ｔＤ＝２ｔＡ＋１Ｍ＋１Ｓ＝ｔＴ＋Ｍであることに注意する。
【００７９】
［９］  楕円曲線：標数２で超特異の場合
標数２の体Ｆ上の超特異な楕円曲線Ｅの方程式を次のように与える。
Ｙ２＋ａ３Ｙ＝Ｘ３＋ａ４Ｘ＋ａ６，  ａ３，ａ４，ａ６∈Ｆ．      （６３）
【００８０】
［９．１］  超特異の場合：加法公式
前と同じく（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）でそれぞれＰ、Ｑ、Ｐ＋Ｑの座標を表す。ｘ３とｙ３をｘ１，ｙ１，ｘ２，ｙ２で表したい。
Ｐ≠Ｑの場合（加算公式）
ｘ３＝λ２＋ｘ１＋ｘ２
ｙ３＝λ（ｘ１＋ｘ３）＋ｙ１＋ａ３
λ＝（ｙ１＋ｙ２）／（ｘ１＋ｘ２）      （６４）
【００８１】
Ｐ＝Ｑの場合（２倍点公式）
λがＰにおける導関数ｄｙ／ｄｘの値である以外、Ｐ≠Ｑの場合と同様である。Ｐの２倍点の座標の式は次のとおりである。
ｘ３＝（ｘ１４＋ａ４２）／ａ３２＝λ２
ｙ３＝λ（ｘ１＋ｘ３）＋ｙ１＋ａ３
λ＝（ｘ１２＋ａ４）／ａ３      （６５）
なお２倍点の座標であることを明示するために、この場合の（ｘ３，ｙ３）を（ｘｄ，ｙｄ）と表すこともある。
【００８２】
３倍点公式
Ｐ＝（ｘ１，ｙ１）、２Ｐ＝（ｘｄ，ｙｄ）、３Ｐ＝（ｘｔ，ｙｔ）として、３倍点３Ｐ＝（ｘｔ，ｙｔ）＝（ｘ１，ｙ１）＋（ｘｄ，ｙｄ）を求める。３Ｐの座標は次で与えられる。
ｘｔ＝μ２＋λ２＋ｘ１
ｙｔ＝μ（ｘ１＋ｘｔ）＋ｙ１＋ａ３
λ＝（ｘ１２＋ａ４）／ａ３，  μ＝λ＋ａ３／（ｘ１＋λ２）      （６６）
【００８３】
［９．２］  超特異の場合：加算の計算量
Ｐ＋Ｑ＝（ｘ３，ｙ３）の計算のコストを考える。ここで加算、減算、小さな定数の乗算は無視する。以下で平方算、乗算、逆元算のコストをそれぞれＳ、Ｍ、Ｉで表す。
Ｐ≠Ｑの場合
１．λ＝（ｙ１＋ｙ２）／（ｘ１＋ｘ２）の計算：
（ｘ１＋ｘ２）−１の計算に逆元算のコストＩ。
これにｙ１＋ｙ２をかける計算に乗算のコストＭ。
２．ｘ３＝λ２＋ｘ１＋ｘ２の計算：
λ２の計算に平方算のコストＳ。
３．ｙ３＝λ（ｘ１＋ｘ３）＋ｙ１＋ａ３の計算：
λをｘ１＋ｘ３にかける計算に乗算のコストＭ。
以上の合計コストｔＡ＝１Ｉ＋２Ｍ＋１Ｓ。なおｔＡの添え字ＡはＡｄｄｉｔｉｏｎ（加算）のつもりである。
【００８４】
Ｐ＝Ｑの場合
１．λ＝（ｘ１２＋ａ４）／ａ３の計算：
ｘ１２の計算に平方算のコストＳ。
ｘ１２＋ａ４にａ３−１をかける計算に乗算のコストＭ。
２．ｘ３＝λ２の計算：
λ２の計算に平方算のコストＳ。
３．ｙ３＝λ（ｘ１＋ｘ３）＋ｙ１＋ａ３の計算：
λ（ｘ１＋ｘ３）の計算に乗算の乗算のコストＭ。
以上の合計コスト合計ｔＤ＝２Ｍ＋２Ｓ。
【００８５】
まとめ
以上をまとめると、標数２の有限体Ｆｑ上で定義された超特異な楕円曲線におけるＰ＋Ｑの計算コストは次のとおりである。計算にはアフィン座標系を使うものとする。
一般の加算の場合、計算量ｔＡ＝１Ｉ＋２Ｍ＋１Ｓ
２倍算の場合、計算量ｔＤ＝２Ｍ＋２Ｓ
【００８６】
［９．３］  ３倍算の計算量：超特異の場合
点Ｐの３倍算すなわち３Ｐを求める計算のコストを考える。
１．λ＝（ｘ１２＋ａ４）／ａ３の計算：
前出の通りコストは１Ｍ＋１Ｓ。
２．μ＝λ＋ａ３／（ｘ１＋λ２）の計算：
λ２の計算に平方算のコストＳ。
（ｘ１＋λ２）−１の計算に逆元算のコストＩ。
これにａ３をかける計算に乗算のコストＭ。
３．ｘｔ＝μ２＋λ２＋ｘ１の計算：
μ２の計算に平方算のコストＳ。
４．ｙｔ＝μ（ｘ１＋ｘｔ）＋ｙ１＋ａ３の計算：
μをｘ１＋ｘｔにかける計算に乗算のコストＭ。
以上の合計コストｔＴ＝１Ｉ＋３Ｍ＋３Ｓ。なお２Ｐを求めてからＰを加算して３Ｐを求めると、計算量はｔＴ’＝ｔＡ＋ｔＤ＝１Ｉ＋４Ｍ＋３Ｓ＝ｔＴ＋Ｍであることに注意する。
【００８７】
［具体例］
実施の形態１
図１は、実施の形態１に係る楕円曲線整数倍演算装置１００の構成図である。これらの構成は、ハードウエア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウエア的にはメモリにロードされた暗号処理機能のあるプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者には理解されるところである。後述する鍵生成装置２００、暗号化装置３００、および復号装置４００の構成についても同様である。
【００８８】
入出力部１０は、楕円曲線を規定する標数や関数の係数などのパラメータ、楕円曲線上の点Ｐの座標、および整数倍算の倍数を与える整数ｋの入力を受け付ける。入力された楕円曲線を規定するパラメータは楕円曲線パラメータ１８として、点Ｐの座標と整数ｋは入力データ１２として主記憶装置や外部記憶装置などの記憶部に保持される。記憶部には、入力データ１２以外に、楕円曲線情報１５、中間データであるｓ進展開データ１４と予備計算データ２４、および最終データであるｋ倍算結果データ２６が記憶される。
【００８９】
楕円曲線情報１５には、楕円曲線パラメータ１８以外に、コスト評価式データ１６、加算公式データ２０、ｓ倍点公式データ２２が含まれる。コスト評価式データ１６、加算公式データ２０、およびｓ倍点公式データ２２は、楕円曲線の標数ｐによって、ｐ＝２で非超特異の場合、ｐ＝２で超特異の場合、ｐ＝３の場合、ｐ＞３の場合に分けて、あらかじめ用意された数式データであり、楕円曲線パラメータ１８として、具体的に楕円曲線の係数が与えられることで、計算が可能である。
【００９０】
ｓ進展開部２８は、入力データ１２の整数ｋについて複数の基数ｓによるｓ進展開を求め、各基数ｓ毎にｓ進展開データ１４として記憶する。
【００９１】
コスト評価部３０は、ｓ進展開データ１４を参照して、ｓ進展開の桁数、ｓ進展開の非零桁の個数を取得し、非零桁の個数を桁数で除算することにより、各ｓ進展開の相対重みを算出する。さらに、コスト評価部３０は、ｓ進法の計算量を相対重みの関数で表したコスト評価式データ１６を参照し、各ｓ進展開の相対重みに基づいてｓ進法によりｋ倍算を行った場合の計算コストを求める。
【００９２】
選択部３２は、コスト評価部３０によって求められた各ｓ進法の計算コストの内、もっとも小さい計算コストを選択し、その場合の基数ｈを出力して、予備計算部３４とｈ進法演算部３５に与える。
【００９３】
コスト評価部３０および選択部３２によってなされるコスト評価と最適なｈ進法の選択は、楕円曲線の標数ｐ＞３の場合は前提技術の［４］、［５］、標数ｐ＝３の場合は前提技術の［７］、標数ｐ＝２の場合は前提技術の［８］、［９］の記載に基づくものである。ただし、前提技術では、一例として、複数の基数ｓとして、ｓ＝２、３を用いた場合を説明しているが、基数ｓとして、ｓ＝２、３以外を用いてもよく、また、３つ以上の基数ｓを用いてもよい。
【００９４】
予備計算部３４は、入力データ１２に含まれる点Ｐについて（ｈ−１）倍以下の整数倍点をあらかじめ計算し、予備計算データ２４として記憶する。ｈ＝３であれば、２Ｐを求めて記憶する。ｈ＝４であれば、２Ｐ、３Ｐを求めて記憶する。ただし、ｈ＝２であれば、予備計算は不要である。
【００９５】
ｈ進法演算部３５は、記憶されている複数の基数ｓについてのｓ進展開データ１４の中から、選択部３２により選択された基数ｈについてのｈ進展開データを取得する。また、ｈ進法演算部３５は、楕円曲線パラメータ１８と、楕円曲線上で点の加算を求めるための加算公式データ２０を読み出す。さらに、ｈ進法演算部３５は、記憶されている複数の基数ｓについてのｓ倍点公式データ２２の中から、選択部３２により選択された基数ｈについてのｈ倍点公式データを取得する。
【００９６】
ｈ進法演算部３５は、ｈ進展開データ、楕円曲線パラメータ１８、加算公式データ２０、ｈ倍点公式データに基づき、入力データ１２の点Ｐのｋ倍算をｈ進法により計算し、得られたｋ倍点ｋＰをｋ倍算結果データ２６として記憶する。
【００９７】
ｈ進法演算部３５によってなされるｈ進法は、点Ｐのｈ倍算と、あらかじめ計算した点Ｐの（ｈ−１）倍以下の整数倍点の加算を組み合わせて、点Ｐのｋ倍算を計算するものである。点Ｐのｈ倍算は、ｈ倍算演算部３６によってなされ、点Ｐの（ｈ−１）倍以下の整数倍点の加算は、予備計算データ２４を用いて加算演算部３８によってなされる。加算演算部３８による加算結果はｈ倍算演算部３６の入力として与えられて、さらにｈ倍算される。ｈ倍算演算部３６および加算演算部３８によってなされるｈ進法演算は、２進法の場合は、前提技術［４．１］、［７．１］に記載のアルゴリズム、３進法の場合は、前提技術［４．２］、［７．２］に記載のアルゴリズムに基づくものであり、後にフローチャートを用いて詳細な動作を説明する。
【００９８】
最終的にｋ倍算結果データ２６として得られた点Ｐのｋ倍点Ｑ＝ｋＰは入出力部１０より出力される。
【００９９】
図２は、以上の構成の楕円曲線整数倍演算装置１００による整数倍演算手順を説明するフローチャートである。ここでは、一例として、２進法または３進法を選択して整数倍演算を行う場合を説明する。
【０１００】
入出力部１０は楕円曲線上の点Ｐと整数ｋの入力を受け付ける（Ｓ１０）。ｓ進展開部２８は、整数ｋの２進展開と３進展開を算出する（Ｓ１２）。
【０１０１】
コスト評価部３０は、整数ｋの２進展開における非零桁の個数ｗ２を２進展開の桁数ｌで除算した相対重みｗ２’と、整数ｋの３進展開における非零桁の個数ｗ３を３進展開の桁数ｉで除算した相対重みｗ３’を算出する（Ｓ１４）。
【０１０２】
選択部３２は、前提技術の［５．１］で説明した２進展開の相対重みｗ２’と３進展開の相対重みｗ３’に関する条件Ｔｅｒが成立するかどうかを調べる（Ｓ１６）。条件Ｔｅｒが成立するなら（Ｓ１６のＹ）、予備計算部３４およびｈ進法演算部３５は、３進法により点Ｐのｋ倍点ｋＰを算出する（Ｓ１８）。条件Ｔｅｒが成立しないなら（Ｓ１６のＮ）、ｈ進法演算部３５は、２進法により点Ｐのｋ倍点ｋＰを算出する（Ｓ２０）。入出力部１０は、こうして得られたｋ倍点Ｑ＝ｋＰを出力する（Ｓ２２）。
【０１０３】
図３は、ステップＳ１８の３進法によるｋ倍算の詳細な手順を説明するフローチャートである。
【０１０４】
予備計算部３４は、点Ｐの２倍点Ｐｄ＝２Ｐをあらかじめ計算して記憶する（Ｓ３０）。ｈ進法演算部３５は、整数ｋの３進展開ｋ＝ｈｉ−１ｈｉ−２…ｈ１ｈ０（３）を取得する（Ｓ３２）。ここで、ｉはｋの３進桁数であり、最上位桁ｈｉ−１は０ではない。Ｑの初期値として、ｈｉ−１＝１ならば、ＱにＰを代入し、ｈｉ−１＝２ならば、ＱにＰｄを代入する（Ｓ３４）。
【０１０５】
次に、ｈ進法演算部３５は、添え字ｊをｉ−２に設定する（Ｓ３６）。ｈ倍算演算部３６は、３倍算公式により現在のＱに対して３倍点３Ｑを求め、３ＱをＱに代入する（Ｓ３８）。加算演算部３８は、ｈｊ＝１ならば、現在のＱにＰを加算した値Ｑ＋Ｐを求め、その加算値をＱに代入し、ｈｊ＝２ならば、現在のＱにＰｄを加算した値Ｑ＋Ｐｄ求め、その加算値をＱに代入する（Ｓ４０）。なお、ここでｈｊ＝０のときは、加算演算部３８による加算は行わない。
【０１０６】
ｈ進法演算部３５は、添え字ｊにｊ−１を代入する、すなわち添え字ｊを１だけデクリメントする（Ｓ４２）。ｊ＜０であれば（Ｓ４４のＹ）、そのときのＱがＰのｋ倍点であり、ｋ倍算の手順を終了してリターンする。ｊ＜０でなければ（Ｓ４４のＮ）、ステップＳ３８に戻り、ｈ倍算演算部３６による３倍算演算と、加算演算部３８による加算が繰り返される。
【０１０７】
図４は、ステップＳ２０の２進法によるｋ倍算の詳細な手順を説明するフローチャートである。
【０１０８】
ｈ進法演算部３５は、整数ｋの２進展開ｋ＝ｋｌ−１ｋｌ−２…ｋ１ｋ０（２）を取得する（Ｓ５０）。ここで、ｌはｋの２進桁数であり、最上位桁ｈｌ−１は１である。Ｑの初期値として、ＱにＰを代入する（Ｓ５２）。
【０１０９】
次に、ｈ進法演算部３５は、添え字ｊをｌ−２に設定する（Ｓ５４）。ｈ倍算演算部３６は、２倍算公式により現在のＱに対して２倍点２Ｑを求め、２ＱをＱに代入する（Ｓ５６）。加算演算部３８は、ｈｊ＝１ならば、現在のＱにＰを加算した値Ｑ＋Ｐを求め、その加算値をＱに代入する（Ｓ５８）。なお、ここでｈｊ＝０のときは、加算演算部３８による加算は行わない。
【０１１０】
ｈ進法演算部３５は、添え字ｊにｊ−１を代入する、すなわち添え字ｊを１だけデクリメントする（Ｓ６０）。ｊ＜０であれば（Ｓ６２のＹ）、そのときのＱがＰのｋ倍点であり、ｋ倍算の手順を終了してリターンする。ｊ＜０でなければ（Ｓ６２のＮ）、ステップＳ５６に戻り、ｈ倍算演算部３６による２倍算演算と、加算演算部３８による加算が繰り返される。
【０１１１】
以上述べたように、実施の形態の楕円曲線整数倍演算装置１００によれば、楕円曲線上で任意の点Ｐのｋ倍点Ｑを求める際、複数の基数ｓについて整数ｋのｓ進展開を求め、ｓ進法の計算コストを評価し、計算コストの最も小さいｈ進法によりｋ倍演算を行う。これにより、単に２進法だけを用いる整数倍算に比べて、計算時間を短縮することができる。
【０１１２】
一般に、ｈ＞３として、ｈ倍算の計算量は、（ｈ−１）倍算と加算の組み合わせの計算量よりも多くなることはないといえる。なぜなら、ｈ倍点公式は、ｈＰ＝（ｈ−１）Ｐ＋Ｐの関係から式を整理して得られるため、式変形の結果、計算量が少なくなることがあり、また、最悪のケースでも、ｈ倍算を（ｈ−１）倍算と加算の組み合わせに置き換えて計算できるからである。したがって、２倍算だけでなく、ｈ倍算を利用することで、計算量をさらに少なくすることができる。もっとも、ｈ進展開したときに、非零桁の個数が多いと、ｈ倍算が利用できる回数が減るため、いつでもｈ進法が２進法よりも計算量が少ないとは限らない。そこで、実施の形態では、いくつかの基数ｓによるｓ進展開を求めて、非零桁の個数により計算量を評価し、複数のｓ進法の中から計算量の少ないものを選ぶことにより、最適なｈ進法を選択し、高速化を図っている。
【０１１３】
実施の形態２
図５は、実施の形態２に係る鍵生成装置２００の構成図である。鍵生成装置２００は、実施の形態１の楕円曲線整数倍演算装置１００を利用して秘密鍵と公開鍵のペアを生成するものである。
【０１１４】
鍵生成装置２００は、楕円曲線データ４２の入力を受け付け、生成された鍵データ４４を出力する入出力部４０と、乱数を生成する乱数生成部４６と、楕円曲線上の点の整数倍演算を行う楕円曲線整数倍演算部４８と、鍵データ４４を生成する鍵生成部５０を含む。楕円曲線整数倍演算部４８として、実施の形態１の楕円曲線整数倍演算装置１００を用いる。
【０１１５】
図６は、鍵生成装置２００による鍵生成手順を説明するフローチャートである。図６も参照しながら、図５の各構成の動作を説明する。
【０１１６】
入出力部４０は、楕円曲線パラメータ、楕円曲線上の基点Ｇおよびその位数ｎの入力を受け付ける（Ｓ２００）。これらのデータは楕円曲線データ４２として記憶部に記憶される。乱数生成部４６は、楕円曲線データ４２に含まれる位数ｎを参照して、０＜ｄ＜ｎを満たす乱数ｄを生成し、楕円曲線整数倍演算部４８に与える（Ｓ２１０）。
【０１１７】
楕円曲線整数倍演算部４８は、楕円曲線データ４２に含まれる基点Ｇの座標を読み出し、基点Ｇのｄ倍点Ｑ＝ｄＧを算出する（Ｓ２２０）。楕円曲線整数倍演算部４８は、ｄ倍点の算出に当たり、実施の形態１で述べたように、計算量が最も少ないｈ進法を選択して、ｈ進法によるｄ倍演算を行う。
【０１１８】
鍵生成部５０は、乱数生成部４６が生成した乱数ｄを秘密鍵、楕円曲線整数倍演算部４８が算出したｄ倍点Ｑを公開鍵とした鍵データ（ｄ，Ｑ）を生成して、鍵データ４４として記憶部に保持する（Ｓ２３０）。入出力部４０は、生成された鍵データ４４を出力する。
【０１１９】
本実施の形態の鍵生成装置２００によれば、楕円曲線暗号により秘密鍵と公開鍵のペアを生成する際、計算量の最も少ないｈ進法を利用することにより、鍵生成を高速化できる。
【０１２０】
実施の形態３
図７は、実施の形態３に係る暗号化装置３００の構成図である。暗号化装置３００は、実施の形態１の楕円曲線整数倍演算装置１００を利用して平文を暗号化するものである。
【０１２１】
暗号化装置３００は、楕円曲線データ６２、公開鍵データ６４および平文データ６６の入力を受け付け、生成された暗号文データ６８を出力する入出力部６０と、乱数を生成する乱数生成部７０と、楕円曲線上の点の整数倍演算を行う楕円曲線整数倍演算部７２と、平文データ６６を暗号化して暗号文データ６８を生成する暗号文生成部７４とを含む。楕円曲線整数倍演算部７２として、実施の形態１の楕円曲線整数倍演算装置１００を用いる。
【０１２２】
図８は、暗号化装置３００による暗号化手順を説明するフローチャートである。図８も参照しながら、図７の各構成の動作を説明する。
【０１２３】
入出力部６０は、楕円曲線パラメータ、楕円曲線上の基点Ｇおよびその位数ｎの入力を受け付ける（Ｓ３００）。これらのデータは楕円曲線データ４２として記憶部に記憶される。入出力部６０は、さらに公開鍵Ｑと平文Ｍの入力を受け付ける（Ｓ３１０）。これらのデータはそれぞれ公開鍵データ６４と平文データ６６として記憶される。乱数生成部７０は、楕円曲線データ４２に含まれる位数ｎを参照して、０＜ｒ＜ｎを満たす乱数ｒを生成し、楕円曲線整数倍演算部７２に与える（Ｓ３２０）。
【０１２４】
楕円曲線整数倍演算部７２は、楕円曲線データ６２に含まれる基点Ｇの座標を読み出して、基点Ｇのｒ倍点ｒＧを算出し、さらに、公開鍵データ６４に含まれる公開鍵Ｑを読み出して、公開鍵Ｑのｒ倍点ｒＱを算出する（Ｓ３３０）。楕円曲線整数倍演算部４８は、ｒ倍点の算出に当たり、実施の形態１で述べたように、計算量が最も少ないｈ進法を選択して、ｈ進法によるｒ倍演算を行う。楕円曲線整数倍演算部７２は、算出した２つのｒ倍点ｒＧ、ｒＱを暗号文生成部７４に与える。
【０１２５】
暗号文生成部７４は、平文データ６６に含まれる平文Ｍを読み出し、第１暗号Ｃ１＝ｒＧと第２暗号Ｃ２＝ｒＱ＋Ｍを算出し、暗号文（Ｃ１、Ｃ２）を生成する（Ｓ３４０）。生成された暗号文（Ｃ１、Ｃ２）は、暗号文データ６８として記憶され、入出力部６０により出力される。
【０１２６】
本実施の形態の暗号化装置３００によれば、楕円曲線暗号により平文を暗号化する際、計算量の最も少ないｈ進法を利用することにより、暗号化処理の高速化を図ることができる。
【０１２７】
実施の形態４
図９は、実施の形態４に係る復号装置４００の構成図である。復号装置４００は、実施の形態１の楕円曲線整数倍演算装置１００を利用して暗号文を復号するものである。
【０１２８】
復号装置４００は、楕円曲線データ８２、秘密鍵データ８４および暗号文データ８６の入力を受け付け、生成された平文データ８８を出力する入出力部８０と、楕円曲線上の点の整数倍演算を行う楕円曲線整数倍演算部９０と、暗号文データ８６を復号して平文データ８８を生成する平文生成部９２とを含む。楕円曲線整数倍演算部９０として、実施の形態１の楕円曲線整数倍演算装置１００を用いる。
【０１２９】
図１０は、復号装置４００による復号手順を説明するフローチャートである。図１０も参照しながら、図９の各構成の動作を説明する。
【０１３０】
入出力部８０は、楕円曲線パラメータの入力を受け付け、楕円曲線データ８２として記憶部に記憶する。入出力部６０は、さらに秘密鍵ｄと暗号文（Ｃ１、Ｃ２）の入力を受け付ける（Ｓ４００）。これらのデータはそれぞれ秘密鍵データ８４と暗号文データ８６として記憶される。
【０１３１】
楕円曲線整数倍演算部９０は、秘密鍵データ８４に含まれる秘密鍵ｄと、暗号文データ８６に含まれる第１暗号Ｃ１を読み出し、楕円曲線データ８２に基づいて、第１暗号Ｃ１のｄ倍点ｄＣ１を算出する（Ｓ４１０）。楕円曲線整数倍演算部９０は、ｄ倍点の算出に当たり、実施の形態１で述べたように、計算量が最も少ないｈ進法を選択して、ｈ進法によるｄ倍演算を行う。楕円曲線整数倍演算部９０は、算出したｄ倍点ｄＣ１を平文生成部９２に与える。
【０１３２】
平文生成部９２は、暗号文データ８６に含まれる第２暗号Ｃ２を読み出し、Ｍ＝Ｃ２−ｄＣ１の計算により平文Ｍを生成する（Ｓ４２０）。生成された平文Ｍは、平文データ８８として記憶され、入出力部８０により出力される。ここで、第２暗号Ｃ２は、暗号化装置３００によりｒＱ＋Ｍの演算で暗号化されたものであり、第１暗号Ｃ１は、暗号化装置３００により基点Ｇのｒ倍点ｒＧとして暗号化されたものであり、公開鍵Ｑは、鍵生成装置２００により基点Ｇのｄ倍点ｄＧとして生成されたものであることに注意すると、Ｃ２−ｄＣ１＝ｒＱ＋Ｍ−ｄ（ｒＧ）＝ｒ（ｄＧ）＋Ｍ−ｄ（ｒＧ）＝Ｍとなることから、平文Ｍの解読が保証されている。
【０１３３】
本実施の形態の復号装置４００によれば、楕円曲線暗号により暗号文を復号する際、計算量の最も少ないｈ進法を利用することにより、復号処理の高速化を図ることができる。
【０１３４】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下そのような変形例を説明する。
【０１３５】
上記の説明では、計算コストに基づき２進法と３進法を選択的に利用する方法を一例として説明したが、２進法、３進法以外を用いてもよく、３つ以上のｓ進法の中から計算量の少ないｈ進法を選択してもよい。
【０１３６】
上記の説明では、実施の形態１の楕円曲線整数倍演算装置１００の利用例として、鍵生成、暗号化および復号を説明したが、これ以外に、デジタル署名の生成と署名の検証に用いてもよい。また、一例として楕円曲線を利用したＥｌＧａｍａｌ暗号を説明したが、楕円曲線を利用した暗号方式は特にこれに限定されない。
【０１３７】
上記の説明では、演算にはアフィン座標系を用いたが、他の座標系、たとえば射影座標系を用いてもよい。特に、逆元算の計算コストが乗算に比べて高いとき、射影座標で演算することが効率的である。
【図面の簡単な説明】
【０１３８】
【図１】実施の形態１に係る楕円曲線整数倍演算装置の構成図である。
【図２】図１の楕円曲線整数倍演算装置による整数倍演算手順を説明するフローチャートである。
【図３】図２の３進法による整数倍算の詳細な手順を説明するフローチャートである。
【図４】図２の２進法による整数倍算の詳細な手順を説明するフローチャートである。
【図５】実施の形態２に係る鍵生成装置の構成図である。
【図６】図５の鍵生成装置による鍵生成手順を説明するフローチャートである。
【図７】実施の形態３に係る暗号化装置の構成図である。
【図８】図７の暗号化装置による暗号化手順を説明するフローチャートである。
【図９】実施の形態４に係る復号装置の構成図である。
【図１０】図９の復号装置による復号手順を説明するフローチャートである。
【符号の説明】
【０１３９】
２８  ｓ進展開部、  ３０  コスト評価部、  ３２  選択部、  ３４  予備計算部、  ３５  ｈ進法演算部、  ３６  ｈ倍算演算部、  ３８  加算演算部、  ４６、７０  乱数生成部、  ４８、７２、９０  楕円曲線整数倍演算部、  ５０  鍵生成部、  ７４  暗号文生成部、  ９２  平文生成部、  １００  楕円曲線整数倍演算装置、  ２００  鍵生成装置、  ３００  暗号化装置、  ４００  復号装置。
【図１】
2005148141.tif 000003
【図２】
2005148141.tif 000004
【図３】
2005148141.tif 000005
【図４】
2005148141.tif 000006
【図５】
2005148141.tif 000007
【図６】
2005148141.tif 000008
【図７】
2005148141.tif 000009
【図８】
2005148141.tif 000010
【図９】
2005148141.tif 000011
【図１０】
2005148141.tif 000012