(57)【特許請求の範囲】
【請求項１】
楕円曲線がｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂである、２の拡大体上の楕円曲線暗号の実行方法であって、
乱数生成部により乱数ｋを生成するステップと、
２の拡大体上の座標ｘ０と前記生成された乱数ｋから射影座標変換部により［ｋ２ｘ０、ｋ］＝［Ｘ１、Ｚ１］＝［Ｘ４、Ｚ４］を求めるステップと、
前記［Ｘ１、Ｚ１］から２倍演算部により２倍点［Ｘ２、Ｚ２］を求めるステップと、
求めた前記［Ｘ１、Ｚ１］、［Ｘ２、Ｚ２］、［Ｘ４、Ｚ４］から加算演算部により加算点［Ｘ３、Ｚ３］を求めるステップと、
前記射影座標変換部、前記２倍演算部、前記加算演算部より求めた結果からスカラー倍部により座標ｘ０をスカラー倍するステップとを有することを特徴とする楕円曲線暗号の実行方法。
【請求項２】
請求項１記載の楕円曲線暗号実行方法において、前記加算演算部により［Ｘ１，Ｚ１］，［Ｘ２，Ｚ２］，［Ｘ４，Ｚ４］から前記加算点［Ｘ３，Ｚ３］を求めるステップは、
前記加算演算部により、Ｂ＝Ｘ１Ｚ２２＋Ｘ２Ｚ１２を計算するステップと、前記計算されたＢをＢ＝０であるか否かを判別するステップと、Ｂ＝０の場合は無限遠点を出力し、Ｂ＝０でない場合はＺ３＝Ｚ４Ｂを計算するステップと、前記計算されたＺ３からＸ３＝Ｘ４Ｚ３２＋Ｘ１Ｘ２Ｚ１２Ｚ２２Ｚ４２を計算するステップが実行されることを特徴とする請求項１記載の楕円曲線暗号の実行方法。
【請求項３】
請求項１記載の楕円曲線暗号実行方法において、前記加算演算部により［Ｘ１，Ｚ１］，［Ｘ２，Ｚ２］，［Ｘ４，Ｚ４］から前記加算点［Ｘ３，Ｚ３］を求めるステップは、
前記加算演算部により、Ｂ＝Ｘ１Ｚ２＋Ｘ２Ｚ１を計算するステップと、前記計算されたＢをＢ＝０であるか否かを判別するステップと、Ｂ＝０の場合は無限遠点を出力し、Ｂ＝０でない場合はＺ３＝Ｚ４２Ｂ２及びＸ３＝Ｘ４Ｂ２＋Ｘ１Ｘ２Ｚ１Ｚ２Ｚ４２を計算するステップとを有することを特徴とする請求項１記載の楕円曲線暗号の実行方法。
【請求項４】
楕円曲線がｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂである、２の拡大体上の楕円曲線暗号の実行方法であって、
乱数生成部により乱数ｋを生成するステップと、
２の拡大体上の座標ｘ０と前記生成された乱数ｋから射影座標変換部により［ｋｘ０、ｋ］＝［Ｘ１、Ｚ１］＝［Ｘ４、Ｚ４］を求めるステップと、
前記［Ｘ１、Ｚ１］から２倍演算部により２倍点［Ｘ２、Ｚ２］を求めるステップと、
求めた前記［Ｘ１、Ｚ１］、［Ｘ２、Ｚ２］、［Ｘ４、Ｚ４］から加算演算部により加算点［Ｘ３、Ｚ３］を求めるステップと、
前記射影座標変換部、前記２倍演算部、前記加算演算部より求めた結果からスカラー倍部により座標ｘ０をスカラー倍するステップとを有することを特徴とする楕円曲線暗号の実行方法。
【請求項５】
楕円曲線がｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂである、２の拡大体上の楕円曲線暗号の演算装置であって、乱数ｋを生成する乱数生成部と、２の拡大体上の座標ｘ０と前記乱数ｋとを入力し、射影座標［ｋｘ０，ｋ］＝［Ｘ１，Ｚ１］に変換する射影座標変換部と、前記［Ｘ１，Ｚ１］から２倍点を演算し出力する２倍演算部と、前記［Ｘ１，Ｚ１］から加算点を求め出力する加算演算部と、前記射影座標変換部と前記２倍演算部と前記加算演算部からの情報を得て、座標ｘ０をスカラー倍するスカラー倍部とを有することを特徴とする楕円曲線演算装置。
【請求項６】
楕円曲線がｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂである、２の拡大体上の楕円曲線暗号の演算装置であって、乱数ｋを生成する乱数生成部と、２の拡大体上の座標ｘ０と前記乱数ｋとを入力し、射影座標［ｋ２ｘ０，ｋ］＝［Ｘ１，Ｚ１］に変換する射影座標変換部と、前記［Ｘ１，Ｚ１］から２倍点を演算し出力する２倍演算部と、前記［Ｘ１，Ｚ１］から加算点を求め出力する加算演算部と、前記射影座標変換部と前記２倍演算部と前記加算演算部からの情報を得て、座標ｘ０をスカラー倍するスカラー倍部とを有することを特徴とする楕円曲線演算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータネットワークにおいてセキュリティを確保する技術に係り、特に楕円曲線暗号を実行する方法及び装置並びに記録媒体に関する。
【０００２】
【従来の技術】
楕円曲線暗号は、V.Miller, N.Koblitz両氏によって、独立に発明された公開鍵暗号である。公開鍵暗号技術において安全上からの要請として、他人に公開される公開鍵から、それに対応する秘密鍵を発見することが事実上不可能であることが求められる。その一方で、秘密鍵暗号方式に比べて基本的に暗号化や復号化に時間のかかる公開鍵暗号方式において、暗号化や復号化におけるより高速のものが求められている状況にある。このように、安全性と高速性という、ある意味で背反的な要請を実現する公開鍵暗号技術として、従来からのＲＳＡ暗号やエルガマル暗号に比べてより上述の性質を有する楕円曲線暗号が注目されてきている。
【０００３】
楕円曲線暗号は、有限素体上の楕円曲線の標準形ｙ２＝ｘ３＋ａｘ＋ｂ（４ａ３＋２７ｂ２≠０）や２の拡大体上の楕円曲線の標準形ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ（ｂ≠０）で表される。この曲線上の点に、無限遠点を加えると、アーベル群が成立する。このアーベル群演算を＋記号で表現する。相異なるＸ，Ｙ間の演算をＸ＋Ｙを加算演算と呼ぶ。また、Ｘ＋Ｘを２倍演算と呼び、２Ｘと表現する。
【０００４】
かかる楕円曲線は、その計算を容易にするためにアフィン座標における楕円曲線上の点（Ｘ，Ｙ）を射影座標で表現することもある。任意のλ≠０について，［Ｘ，Ｙ，Ｚ］＝  ［λ２Ｘ，λ３Ｙ，λＺ］となる射影座標を考えると、アフィン座標とこの射影座標の対応は以下で与えられる。すなわち、アフィン座標（ｘ，ｙ）は、射影座標［ｘ，ｙ，１］で表現され、射影座標［Ｘ，Ｙ，Ｚ］は、アフィン座標（Ｘ／（Ｚ）２，Ｙ／（Ｚ）３  ）となる。また、射影座標において−［Ｘ，Ｙ，Ｚ］＝［Ｘ，−Ｙ，Ｚ］である。
【０００５】
楕円曲線暗号は、有限体上の楕円曲線を用いて、その有限体となる点の集合を用いる。また、楕円曲線の位数は、楕円曲線の点の数である。以下、Ｐをｓ回加算（Ｐ＋Ｐ＋…＋Ｐ）した結果をＰのｓ倍点といい、これを求める演算をｓＰと書くと、楕円曲線上の点Ｐの位数は、ｎＰ＝０，１＜＝ｍ＜ｎ，ｍＰ  ≠０となるｎである１１２となる。
【０００６】
楕円曲線暗号の鍵は、楕円曲線、ベースポイント、公開鍵、秘密鍵から構成され、具体的には、楕円曲線の係数ａ，ｂ、位数が素数である点Ｐ（ベースポイント）、有限体要素ｄ（秘密鍵）、ベースポイントの秘密鍵倍の点Ｑ（公開鍵：Ｑ＝ｄＰ）である。ここで、楕円曲線、ベースポイント、公開鍵は公開情報である。また、公開鍵／秘密鍵は、ユーザ毎に異なる値であり、楕円曲線、ベースポイントは、ユーザ間共通の値である。
【０００７】
楕円曲線暗号における、データ暗号化、データ復号化、ディジタル署名作成、ディジタル署名検証は、任意の点Ｒのスカラ倍ｓＲ演算を用いる。これは、上記の加算演算と２倍演算の組合せで、求めることができる。ところが、上記の加算演算と２倍演算計算法においては、それぞれ１回の除算が必要であり、一般に有限体の除算は非常に時間がかかるため、これを避ける方法が求められる。
【０００８】
文献D.V.Chudnovsky, G.V.Chudnovsky "Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization Tests", Advances in Applied Mathematics, 7, 385-434,1986によれば、この有限体の除算を避けるため、射影空間で、加算演算、２倍演算の式を導出している。この場合、素体乗算と、素体加減算では素体乗算が通常、遥かに時間がかかるため、素体乗算演算数で、計算時間を評価できる。この場合、加算演算で、素体乗算（２乗算を含む）が１６回必要である。２倍演算において、１０回必要である、と述べている。また、楕円曲線の係数ａにおいても、ａ＝−３の場合、８回の乗算剰余演算となるとしている。
【０００９】
また、P.Montgomery,"Speeding the Pollard and Elliptic Curve Methods of Factorization", Mathematics of computation Vol.48,No.177,pp.243-264(1987)によれば、有限素体上の楕円曲線の標準形Ｂｙ２＝ｘ３＋Ａｘ２＋Ｂｘを用いて、点Ｐ０（ｘ０，ｙ０），Ｐ１（ｘ１，ｙ１）の加算をＰ３（ｘ３，ｙ３）、減算をＰ４（ｘ４，ｙ４）、すなわちＰ１＋Ｐ０＝Ｐ３、Ｐ１−Ｐ０＝Ｐ４とするとき、ｘ０，ｘ１，ｘ４から、ｘ３が高速に求まる。具体的には、素体の乗算６回で求まるとされている。また、Ｐ１の２倍点をＰ５（ｘ５，ｙ５）とするとき、ｘ５は、ｘ１のみから求まり、乗算５回である。これを利用して、点Ｒのスカラ倍（スカラー値ｄ）のｘ座標を以下のようにＲｘから求めることができる。
【００１０】
初期値を［Ｒ，２Ｒ］、ｍＲをＲのｍ倍のｘ座標とするとき、ｄを２進数展開し、ｄの上位ビットから、０の場合は、［ｍＲ，（ｍ＋１）Ｒ］→  ［２ｍＲ，（２ｍ＋１）Ｒ］となり、１の場合は、［ｍＲ，（ｍ＋１）Ｒ］→［（２ｍ＋１）Ｒ，２（ｍ＋１）Ｒ］となる。尚、（ｍ＋１）Ｒ−ｍＲ＝Ｒ、（ｍ＋１）Ｒ＋ｍＲ＝（２ｍ＋１）Ｒである。
【００１１】
従って、１ビットあたり、６＋５＝１０回の素体乗算（２乗算を含む）でスカラー倍ｓＰを求めることができる。これを以下、モンゴメリ法と呼ぶ。
【００１２】
一方、２の拡大体上の楕円曲線の標準形ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ（ｂ≠０）で表される。このスカラー倍演算も、加算演算、２倍演算の組合せで実現できる。IEEE P1363 / D2 Standard Specification for Public Key Cryptography(1998)では、加算演算と２倍演算規則を与えている。２の拡大体演算では、２乗算、加減算は相異なる乗算に比べて非常に速く演算できるので、（相異なる）乗算回数で評価できる。加算演算で１５回の乗算、２倍演算で５回の乗算が必要となる。しかし、２の拡大体楕円曲線暗号ではモンゴメリ法を用いる演算は知られていない。
【００１３】
安全な楕円曲線とするためには、楕円曲線の位数＃Ｅ（Ｆｑ）が大きな素因数ｒを持つパラメタａ，ｂを設定する必要がある。＃Ｅ（Ｆｑ）＝ｋｒで、ｋは小さな整数、ｒは大きな素数となる。そのが位数大きな素因数を持つ楕円曲線のパラメタの設定方法は、例えば文献Henri Cohen, "A Course in Computational Algebraic Number Theory", GTM138, Springer(1993) p.464 Atkin's Testで記述されている方法がある。
【００１４】
次に暗号のアタックと防御について述べる。近年、暗号のアタックは、理論的な暗号解読に加え、消費電流波形を統計的に処理して解読を試みるＤＰＡ(Differential Power Analysis)や暗号処理時間の違いから統計的に分析し解読を試みるタイミングアタック等、リーク情報を分析する攻撃とその防御が研究されはじめている。これらの防御研究の多くは、主にＩＣカードを分析する等のハードウェア回路そのものに防御機能を組み込むことが中心になっている。
【００１５】
【発明が解決しようとする課題】
上述したように２の拡大体の楕円曲線暗号ではモンゴメリ法を用いる演算は知られていない。また、楕円曲線暗号の研究においては、主に高速な実行方法、暗号解読の観点からの安全な楕円曲線生成の研究開発が中心であり、リーク情報分析型のアタックに対する防御開発は行われていない。楕円曲線暗号のデータ復号化処理では、与えられた楕円曲線上の点（ｘ，ｙ）の秘密鍵ｄから、（ｘ，ｙ）のｄ倍演算ｄ（ｘ，ｙ）を行う。ｄの偏差情報を消費電流波形や暗号処理時間に洩れる場合ＤＰＡやタイミングアタックへの手がかりを与えてしまう。本発明の第１の目的は、楕円曲線がｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ（ｂ≠０）である、２の拡大体上の楕円曲線暗号を高速に演算する方法及び装置を提供することにある。また、本発明の第２の目的は、楕円曲線暗号においてタイミングアタックやＤＰＡによる攻撃を防御するための、処理時間の偏差情報から秘密鍵情報がもれない方法を提供することにある。
【００１６】
【課題を解決するための手段】
本発明の第１の目的は、楕円曲線がｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ（ｂ≠０）である、２の拡大体上の楕円曲線暗号の実行方法であって、各座標成分が前記楕円曲線上の点である点Ｐ１（ｘ１，ｙ１），Ｐ２（ｘ２，ｙ２）の加算をＰ３（ｘ３，ｙ３）とし、点Ｐ１（ｘ１，ｙ１），Ｐ２（ｘ２，ｙ２）の減算をＰ４（ｘ４，ｙ４）とした場合、前記ｘ１を入力するステップと、前記入力されたｘ１を射影空間のＸ座標、Ｚ座標［Ｘ１，Ｚ１］に変換するステップと、前記射影空間の座標［Ｘ１，Ｚ１］を記憶するステップと、前記ｘ２を［Ｘ２，Ｚ２］に変換するステップと、前記［Ｘ２，Ｚ２］を記憶するステップと、前記ｘ４を［Ｘ４，Ｚ４］に変換するステップと、前記［Ｘ４，Ｚ４］を記憶するステップと、前記記憶された［Ｘ１，Ｚ１］，［Ｘ２  ，Ｚ２］，［Ｘ４，Ｚ４］から［Ｘ３，Ｚ３］を求めるステップと、前記［Ｘ３，Ｚ３］からｘ３に変換するステップと、前記ｘ３を出力するステップとからなり、点Ｐ１（ｘ１，ｙ１）のスカラー倍を計算することにより達成される。また、記憶された［Ｘ１，Ｚ１］，［Ｘ２，Ｚ２］，［Ｘ４，Ｚ４］からｘ３に変換できる［Ｘ３，Ｚ３］を求めるステップには、Ｂ＝Ｘ１Ｚ２２＋Ｘ２Ｚ１２を計算するステップと、前記計算されたＢを記憶するステップと、前記記憶されたＢをＢ＝０であるか否かをを判別するステップと、Ｂ＝０の場合は無限遠点を出力し、Ｂ＝０でない場合はＺ３＝Ｚ４Ｂを計算するステップと、前記計算されたＺ３を記憶するステップと、前記記憶されたＺ３からＸ３＝Ｘ４Ｚ３２＋Ｘ１Ｘ２Ｚ１２Ｚ２２Ｚ４２を計算するステップとを有することにより達成される。
【００１７】
本発明の第２の目的は、２の拡大体上の楕円曲線暗号の復号化処理時間において、処理時間の偏差情報から秘密鍵情報がもれない方法、すなわち楕円曲線がｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂである、２の拡大体上の楕円曲線暗号の実行方法であって、各座標成分が前記楕円曲線上の点である点Ｐ１（ｘ１，ｙ１），Ｐ２（ｘ２，ｙ２）の加算をＰ３（ｘ３，ｙ３）とし、点Ｐ１（ｘ１，ｙ１），Ｐ２（ｘ２，ｙ２）の減算をＰ４（ｘ４，ｙ４）とした場合、前記ｘ１を入力するステップと、前記入力されたｘ１を射影空間のＸ座標、Ｚ座標［Ｘ１，Ｚ１］に変換するステップと、前記射影空間の座標［Ｘ１，Ｚ１］を記憶するステップと、前記ｘ２を［Ｘ２，Ｚ２］に変換するステップと、前記［Ｘ２，Ｚ２］を記憶するステップと、前記ｘ４を［Ｘ４，Ｚ４］に変換するステップと、前記［Ｘ４，Ｚ４］を記憶するステップと、前記記憶された［Ｘ１，Ｚ１］，［Ｘ２  ，Ｚ２］，［Ｘ４，Ｚ４］から［Ｘ３，Ｚ３］を求めるステップと、前記［Ｘ３，Ｚ３］からｘ３に変換するステップと、前記ｘ３を出力するステップの他、さらに乱数ｋを生成するステップと、前記生成された乱数ｋを記憶するステップと、ｘ座標を射影座標に変換した後、射影空間の各座標成分と前記記憶された乱数ｋと演算させて、射影座標［ｋ２ｘ，ｋ］に変換するステップとを有することにより達成される。すなわち、２の拡大体の演算対象が乱数によって常に変更する方法を用いる。
【００１８】
また、乱数ｋを生成するステップと、前記生成された乱数ｋを記憶するステップと、ｘ座標を射影座標に変換した後、射影空間の各座標成分と前記記憶された乱数ｋと演算させて、射影座標［ｋｘ，ｋ］に変換するステップとを有することにより達成される。また、楕円曲線がｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂである、２の拡大体上の楕円曲線暗号の演算装置であって、乱数ｋを生成する乱数生成部と、２の拡大体上の座標ｘ０と前記乱数ｋとを入力し、射影座標［ｋｘ０，ｋ］＝［Ｘ１，Ｚ１］に変換する射影座標変換部と、前記［Ｘ１，Ｚ１］から２倍点を演算し出力する２倍演算部と、前記［Ｘ１，Ｚ１］から加算点を求め出力する加算演算部と、前記射影座標変換部と前記２倍演算部と前記加算演算部からの情報を得て、座標ｘ０をスカラー倍するスカラー倍部とを有することにより達成される。
【００１９】
また、楕円曲線がｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂである、２の拡大体上の楕円曲線暗号の実行方法を格納した記録媒体であって、前記楕円曲線暗号の実行方法は以下を含むことにより達成される。すなわち、各座標成分が前記楕円曲線上の点である点Ｐ１（ｘ１，ｙ１），Ｐ２（ｘ２，ｙ２）の加算をＰ３（ｘ３，ｙ３）とし、点Ｐ１（ｘ１，ｙ１），Ｐ２（ｘ２，ｙ２）の減算をＰ４（ｘ４，ｙ４）とした場合、前記ｘ１を入力するステップと、前記入力されたｘ１を射影空間のＸ座標、Ｚ座標［Ｘ１，Ｚ１］に変換するステップと、前記射影空間の座標［Ｘ１，Ｚ１］を記憶するステップと、前記ｘ２を［Ｘ２，Ｚ２］に変換するステップと、前記［Ｘ２，Ｚ２］を記憶するステップと、前記ｘ４を［Ｘ４，Ｚ４］に変換するステップと、前記［Ｘ４，Ｚ４］を記憶するステップと、前記記憶された［Ｘ１，Ｚ１］，［Ｘ２  ，Ｚ２］，［Ｘ４，Ｚ４］から［Ｘ３，Ｚ３］を求めるステップと、前記［Ｘ３，Ｚ３］からｘ３に変換するステップと、前記ｘ３を出力するステップとからなり、点Ｐ１（ｘ１，ｙ１）のスカラー倍を計算する。
【００２０】
また、上述した２の拡大体上の楕円曲線暗号の実行方法は、素体上の楕円曲線暗号の復号化処理時間において、処理時間の偏差情報から秘密鍵情報がもれない方法としても適用可能である。素体上の楕円曲線暗号において、上記課題（２）を解決するため、次の（ａ），（ｂ）を組合わせる。次の（ａ），（ｂ）を組合わせる。（ａ）楕円曲線のスカラー倍ｄ（ｘ，ｙ）において、素体上の楕円曲線の標準形Ｂｙ２＝ｘ３＋Ａｘ２＋Ｂｘの場合、モンゴメリのスカラー倍を用いる。（ｂ）スカラー倍ｄ（ｘ，ｙ）を計算する場合、このアフィン座標（ｘ，ｙ）を射影座標する際に、乱数ｋを生成し、（ｘ，ｙ）→［ｋｘ，ｋｙ，ｋ］または（ｘ，ｙ）→［ｋ２ｘ，ｋ３ｙ，ｋ］に変換する。このことにより、素体の演算対象が乱数によって常に変更する方法を用いる。
【００２１】
【発明の実施の形態】
２の拡大体上の楕円曲線の標準形ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ（ｂ≠０）のアフィン座標における演算規則を以下に示す。
【００２２】
１）０＋０＝０
２）（ｘ，ｙ）＋０＝（ｘ，ｙ）
３）（ｘ，ｙ）＋（ｘ，ｘ＋ｙ）＝０
４）可換性（ｘ０，ｙ０）＋（ｘ１，ｙ１）＝（ｘ１，ｙ１）＋（ｘ０，ｙ０）
５）加算演算（ｘ２，ｙ２）＝（ｘ１，ｙ１）＋（ｘ０，ｙ０）
ｘ２＝ａ＋λ２＋λ＋ｘ０＋ｘ１； ｙ２＝λ（ｘ１＋ｘ２）＋ｘ２＋ｙ１；
λ＝（ｙ０＋ｙ１）／（ｘ０＋ｘ１）
６）２倍演算（ｘ２，ｙ２）＝（ｘ１，ｙ１）＋（ｘ１，ｙ１）＝２（ｘ１，ｙ１）
ｘ２＝ａ＋λ２＋λ；ｙ２＝λ（ｘ１＋ｘ２）＋ｘ２＋ｙ１；λ＝ｘ１＋（ｙ１／ｘ１）
または、ｘ２＝（ｘ１）２＋ｂ／（ｘ１）２
かかる楕円曲線は、その計算を容易にするためにアフィン座標における楕円曲線上の点（Ｘ，Ｙ）を射影座標で表現することもある。任意のλ≠０について，［Ｘ，Ｙ，Ｚ］＝［λ２Ｘ，λ３Ｙ，λＺ］となる射影座標を考えると、アフィン座標とこの射影座標の対応は以下で与えられる。すなわち、アフィン座標（ｘ，ｙ）は、射影座標［ｘ，ｙ，１］で表現され、射影座標［Ｘ，Ｙ，Ｚ］は、アフィン座標（Ｘ／（Ｚ）２，Ｙ／（Ｚ）３）となる。また、射影座標において−［Ｘ，Ｙ，Ｚ］＝［Ｘ，ＸＺ＋Ｙ，Ｚ］である。
【００２３】
以下、本発明の実施例を図面を用いて具体的に説明する。図１０は、楕円曲線暗号システムの構成図である。入出力インターフェース１００１は暗号化する平文を入力するキーボード等の入力装置、復号化した平文を出力するディスプレー、プリンタ等の出力装置、平文を記憶するメモリ等の記憶装置などである。暗号化部１００２は、楕円曲線生成部１００３で生成された楕円曲線と、公開鍵、暗号鍵生成部１００４からの鍵とを入力し、平文を暗号化する。ここで、公開鍵、暗号鍵は対になっており、どちらの鍵を暗号化部１００２、復号化部１００６に与えるかは暗号システムの用途、即ち、秘密通信に用いるか、署名・認証と呼ばれる通信に用いるか等で使い分ける。暗号化された暗号文は接続インターフェース１００５から送信される。復号化部１００６は、暗号文を復号化し平文にする。
【００２４】
図１は、楕円曲線暗号システムにおける処理の流れを示す図である。楕円曲線生成部１０１では楕円曲線暗号に使用する楕円曲線を生成する。公開鍵／秘密鍵生成部１０２では、楕円曲線生成部１０１で生成した楕円曲線を入力し、これに基づいて公開鍵１１５と秘密鍵１１６を生成する。暗号化部１０３では、平文１１３、公開鍵１１５、楕円曲線を入力して暗号文１１２を出力する。復号化部１０４では、暗号文１１２、秘密鍵１１６、楕円曲線を入力し、平文１１４を出力するが、ここで出力する平文１１４は平文１１３と内容が同じものである。
【００２５】
楕円曲線生成部１０１では以下の手順で楕円曲線を生成する。原始多項式(primitive polynomials)設定１０５では、素体Ｆ２上の原始多項式ｆ（ｘ）を設定する。例えば、素体Ｆ２上の原始多項式は、A.Menezes, P.Oorschot, S.Vanstone, "Handbook of Applied Cryptography", CRC Press(1996)の第4.5.3 Primitive polynomialsに記述されている。
【００２６】
楕円曲線パラメタ設定１０６は、２の拡大体Ｆｑを定義体とする楕円曲線ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂのパラメタａ，ｂを設定する。安全な楕円曲線とするためには、楕円曲線の位数＃Ｅ（Ｆｑ）が大きな素因数ｒを持つ必要がある。＃Ｅ（Ｆｑ）＝ｋｒの場合、ｋを小さな整数とすることによって、ｒは大きな素数となる。大きな素因数ｒを位数に持つ楕円曲線を生成する方法として、文献Henri Cohen, "A Course in Computational Algebraic Number Theory",GTM138, Springer(1993) p.464 Atkin's Testで記述されている方法がある。なお、他の楕円曲線の位数が大きな素因数ｒを持つ楕円曲線パラメタ設定法を用いても本発明の実施は可能である。
【００２７】
ベースポイント生成部１０７は、楕円曲線上のアーベル群において、上記ｒを位数とする部分巡回群の生成元を求める。例えば、＃Ｅ（Ｆｑ）＝ｋｒの場合は、第１のステップでＥ（Ｆｑ）上の任意の点（ｘ１，ｙ１）を求める。次に第２のステップでｒ（ｘ１，ｙ１）＝０かつｋ（ｘ１，ｙ１）≠０の場合、Ｇ＝（ｘ１，ｙ１）をベースポイントとする。他の場合は、第１のステップへ戻る。
【００２８】
ここで、ｒ（ｘ１，ｙ１）は、（ｘ１，ｙ１）のスカラー倍（ｒ倍）演算を実行するという意味である。スカラー倍（ｒ倍）演算については楕円曲線演算部１０９で説明する。
【００２９】
以上、楕円曲線生成部１０１により、原始多項式ｆ（ｘ）、楕円曲線ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂのパラメタａ，ｂ、ベースポイントＧ、ベースポイントの位数ｒを生成した。これらは公開する情報である。
【００３０】
次に公開鍵／秘密鍵生成部１０２は、以下の手順で公開鍵と秘密鍵を生成する。入力を原始多項式ｆ（ｘ）、楕円曲線ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂのパラメタａ，ｂ、ベースポイントＧとし、出力を公開鍵Ｑ、秘密鍵ｄとすると、第１のステップで乱数２＜ｄ＜ｒ−１を生成し、第２のステップでＱ＝  ｄＧすなわちＧのスカラ倍（ｄ倍）点を求める。
【００３１】
公開鍵は、公開する情報であり、秘密鍵は秘密にする情報である。Ｑ，Ｇからｄを求める問題は、離散対数問題といわれるものであり、楕円曲線において、ベースポイントの位数ｒのビット長の指数オーダの計算量を必要とする。このため、ｒが大きな素数であれば例えば、ｒ＞２の１５９乗をとれば、事実上、Ｑ，Ｇからｄを求めることはできなくなる。これが楕円曲線暗号の原理である。なお、Ｑを計算する方法は、従来技術文献  D.V.Chudnovsky, G.V.Chudnovsky "Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization Tests", Advances in Applied Mathematics, 7, 385-434,1986で記載されている方法で求めることができる。
【００３２】
次に、暗号化部１０３では、以下の手順で平文１１３を暗号文１１４に変換する。入力を平文Ｍ、公開鍵Ｑ、原始多項式ｆ（ｘ）、楕円曲線ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂのパラメタｂ、ベースポイントＧとし、出力を暗号文Ｃとすると、第１のステップで乱数ｋを生成し（乱数生成部１０８）、第２のステップでベースポイントＧと第１のステップで生成した乱数ｋとを演算し、ｋＧすなわち（ｋｘ１，ｋｙ１）とする（楕円曲線演算部１０９）。第３のステップで公開鍵Ｑと第１のステップで生成した乱数ｋとを演算し、ｋＱすなわち（ｋｘ２，ｋｙ２）とする（楕円曲線演算部１０９）。第４のステップでＭ ｘｏｒ ｘ２を演算し、Ｍ'とする（データ暗号化１１０）。第５のステップでｘ１||ｙ１||Ｍ'を演算し暗号文Ｃとする（データ暗号化１１０）。
【００３３】
楕円曲線演算部１０９は、任意の点Ｒのスカラ倍ｋＲ演算を行いそのｘ座標を得る。これにより２の拡大体上の楕円曲線暗号の復号化処理時間において、処理時間の偏差情報から秘密鍵情報が漏れなくなる。以下にこのスカラー倍方法を説明する。図２、図３は、このスカラー倍方法の第１の実施例の説明図である。
【００３４】
＜第１実施例スカラー倍方法＞
Ｒのｘ座標の射影座標成分Ｘ０、スカラー値ｍを入力とし、Ｒのｍ倍の点のｘ座標の射影座標成分Ｘｍを出力とする。ｍ，Ｘ０を入力を入力し（ステップ２０２）、ステップ２０３から２０５では乱数を射影座標の各座標に乗算することにより、データを撹拌する。すなわち、乱数ｋを生成し（ステップ２０３）、乱数ｋとＸ０を演算してｋ２Ｘ０をＸ１に代入し、乱数ｋをＺ１に代入する（ステップ２０５）。ステップ２０６から２０８及び３０１ではスカラー倍の準備を行う。すなわち、［Ｘ１，Ｚ１］を［Ｘ４，Ｚ４］に代入し（ステップ２０６）、また［Ｘ１，Ｚ１］を２倍方法（図５）に入力し、出力を［Ｘ２，Ｚ２］へ代入する（ステップ２０７）。  ｍの２進数表現をｈｉｈｉ−１．．．ｈ０とする（ステップ２０８）。ただし、最上位ビットｈｌは１である。ｉをｌとする（ステップ３０１）。ステップ３０２から３０９ではｍの１ビットが０か１かによって加算方法や２倍方法を制御しスカラー倍を求める。すなわち、  ｉ−１をｉに代入し（ステップ３０２）、［Ｘ１，Ｚ１］、［Ｘ２，Ｚ２］、［Ｘ４，Ｚ４］を加算方法（図４）に入力し、出力を［Ｘ３，Ｚ３］へ代入する（ステップ３０３）。ここで、ｈｉ＝＝０ならば、ステップ３０４へ、１ならばステップ３０６へ進む（ステップ３０４）。［Ｘ１，Ｚ１］を２倍方法（図５）に入力し、出力を［Ｘ１，Ｚ１］に代入する（ステップ３０５）。［Ｘ３，Ｚ３］を［Ｘ２，Ｚ２］に代入し、ステップ３０８へいく（ステップ３０６）。［Ｘ２，  Ｚ２］を２倍方法（図５）に入力し、出力を［Ｘ２，Ｚ２］に代入する（ステップ３０７）。［Ｘ３，Ｚ３］を［Ｘ１，Ｚ１］に代入し、ステップ３０８へいく（ステップ３０８）。ｉ＞０ならばステップ３０２へ進む（ステップ３０９）。次は、射影座標から（ｘ，ｙ）座標のｘ座標へ変換する。Ｘ１／（Ｚ１）２をＸｍに代入し（ステップ３１０）、Ｘｍを出力する（ステップ３１１）。
【００３５】
次に、加算方法について説明する。楕円曲線上の点の射影空間座標として、任意のλ≠０について，［Ｘ，Ｙ，Ｚ］＝［λ２Ｘ，λ３Ｙ，λＺ］とする。ここで、楕円曲線上の点Ｐ０＝（ｘ０，ｙ０）＝［Ｘ０，Ｙ０，Ｚ０］；Ｐ１＝（ｘ１，ｙ１）＝［Ｘ１，Ｙ１，Ｚ１］とする。この和と差をＰ３＝（ｘ３，ｙ３）＝［Ｘ３，Ｙ３，Ｚ３］，Ｐ４＝（ｘ４，ｙ４）＝［Ｘ４，Ｙ４，Ｚ４］とする。
【００３６】
Ｐ１＋Ｐ０＝Ｐ３；
Ｐ１−Ｐ０＝Ｐ４；
ｘ３＝ａ＋（λ３）２＋λ３＋ｘ０＋ｘ１；λ３＝（ｙ０＋ｙ１）／（ｘ０＋ｘ１）；
ｘ４＝ａ＋（λ４）２＋λ４＋ｘ０＋ｘ１；λ４＝（ｘ０＋ｙ０＋ｙ１）／（ｘ０＋ｘ１）；
λ３＋λ４＝（ｘ０）／（ｘ０＋ｘ１）；
（λ３）２＋（λ４）２＝（ｘ０）２／（ｘ０＋ｘ１）２；
ｘ３＋ｘ４＝((x0)2+(x0)(x0+x1))／(x0+x1)2＝(x0x1)／(x0+x1)2；
以上により、ｘ３＋ｘ４＝（ｘ０ｘ１）／（ｘ０＋ｘ１）２  −−−−（１）
という関係式が得られた。
【００３７】
次に、射影座標での関係式を導出する。
【００３８】
ｘ１＝Ｘ１／（Ｚ１）２、ｘ０＝Ｘ０／（Ｚ０）２を（１）式に代入する。  Ｘ３／（Ｚ３）２＝X4/(Z4)2＋((X0/(Z0)2)( X1/(Z1)2))／( X0/(Z0)2+ X1/(Z1)2)2；
＝X4/(Z4)2＋((X0(Z0)2)( X1(Z1)2))／( X0(Z1)2+X1(Z0)2)2；＝（（Ｘ４β２）＋Ｚ４２（Ｘ０Ｚ０２）（  Ｘ１Ｚ１２））／（Ｚ４２β２）
ただし、β＝  Ｘ０Ｚ１２＋  Ｘ１Ｚ０２
これより、
Ｘ３＝Ｘ４β２＋Ｚ４２（Ｘ０Ｚ１２）（  Ｘ１Ｚ０２）；−−−−−（２）
Ｚ３＝Ｚ４β；−−−−−−−−−−−−−−−−−−−−−−（３）  を得た。
【００３９】
ここで、ｍＲ＝［Ｘ１，Ｙ１，Ｚ１］、（ｍ＋１）Ｒ＝［Ｘ２，Ｙ２，Ｚ２］、Ｒ＝［Ｘ４，Ｙ４，Ｚ４］、（２ｍ＋１）Ｒ＝［Ｘ３，Ｙ３，Ｚ３］とする。この導出式を利用した加算方法を以下に説明する。図４はこの方法の説明図である。
【００４０】
＜第１実施例加算方法＞
射影座標［Ｘ１，Ｚ１］，［Ｘ２，Ｚ２］，［Ｘ４，Ｚ４］を入力とし、［Ｘ３，Ｚ３］または無限遠点を出力とする。［Ｘ１Ｚ１］，［Ｘ２，Ｚ２］，［Ｘ４，Ｚ４］を入力し（ステップ４０２）、ステップ４０３から４０７では加算結果が無限遠点か判定するためにＸ１（Ｚ２）２＋    Ｘ２（Ｚ１）２を求める。さらに各中間結果Ｓ１、Ｓ２、Ｂは、上記式（２），（３）を求めるための準備である。すなわち、Ｘ１（Ｚ２）２をＳ１に代入し（ステップ４０３）、Ｘ２（Ｚ１）２をＳ２に代入し（ステップ４０４）、Ｓ１＋Ｓ２をＢに代入し（ステップ４０５）、Ｂ＝０の場合、ステップ４０７へ進み、成立しない場合ステップ４０８へ進む（ステップ４０６）。ステップ４０７では、無限遠点を出力し、ステップ４１３へいく。以下の４０８−４１１は上記式（２），（３）に従って［Ｘ３，Ｚ３］を求める。Ｚ４ＢをＺ３に代入し（ステップ４０８）、（Ｚ４）２Ｓ１Ｓ２をＳに代入し（ステップ４０９）、Ｘ４Ｚ３２をＭに代入し（ステップ４１０）、  Ｍ＋ＳをＸ３に代入し（ステップ４１１）、［Ｘ３，Ｚ３］を出力を出力する（ステップ４１２）。かかる方法により相異なる変数の乗算６回で加算演算を実行できる。すなわち、Ｘ１、Ｘ２、Ｘ４からＸ３を高速に演算できる。
【００４１】
次に、２倍計算方法について説明する。Ｐ１の２倍点をＰ２とし、Ｐ１＝（ｘ１，ｙ１）＝［Ｘ１，Ｙ１，Ｚ１］、Ｐ２＝（ｘ２，ｙ２）＝［Ｘ２，Ｙ２，Ｚ２］とする。２倍演算の演算式  ｘ２＝（ｘ１）２＋ｂ／（ｘ１）２より、ｘ１＝  Ｘ１／（Ｚ１）２、ｘ２＝Ｘ２／（Ｚ２）２をこの式に代入する。
【００４２】
X2/(Z2)2=(X1/(Z1)2)2+b/(X1/(Z1)2)2=X12/(Z1)4+(b(Z1)4)/(X1)2=(X14+b(Z1)8)/(X12Z14)
従って、
Ｘ２＝Ｘ１４＋ｂＺ１８−−−−−（４）
Ｚ２＝Ｘ１Ｚ１２−−−−−−−−（５）
この導出式を利用した２倍方法を以下に説明する。図５は、この説明図である。
【００４３】
＜第１実施例２倍計算方法＞
Ｑ＝［Ｘ１，Ｚ１］、ｂを入力とし、２Ｑ＝［Ｘ２，Ｚ２］または無限遠点を出力とする。Ｘ１，Ｚ１を入力し（ステップ５０２）、以下のステップ５０３から５０４は２倍結果が無限遠点を判定するためにＸ１＝＝０またはＺ１＝＝０の判定を行う。すなわち、Ｘ１＝＝０またはＺ１＝＝０の場合は、ステップ５０４へ。成立しない場合は、ステップ５０５へいく（ステップ５０３）。ステップ５０４では、無限遠点を出力する。以下のステップ５０５から５０７では上記式（４），（５）に従って［Ｘ２，Ｚ２］を求める。Ｚ１２をＳに代入し（ステップ５０５）、  Ｘ１ＳをＺ２に代入し（ステップ５０６）、Ｘ１４＋ｂ（Ｓ）４をＸ２に代入し（ステップ５０７）、［Ｘ２，Ｚ２］を出力する（ステップ５０８）。かかる方法により相異なる変数の乗算２回で加算演算を実行できる。従って、＜スカラー倍方法＞においてはスカラー値ｄのビットあたり、相異なる変数の乗算６＋２＝８回で実行できる。すなわち、Ｘ１、Ｘ２、Ｘ４からＸ３を高速に演算できる。
【００４４】
つぎに、復号化部１０４では、以下の手順で暗号文１１２を元の平文１１４に変換する。１１２と１１４は内容が同じ平文である。入力を暗号文Ｃ←ｘ１||ｙ１||Ｍ'、秘密鍵ｄ、原始多項式ｆ（ｘ）、楕円曲線ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂのパラメタ，ｂ、ベースポイントＧとし、出力を平文Ｍとする。
【００４５】
ステップ１：（ｘ２，ｙ２）←ｄ（ｘ１，  ｙ１）（楕円曲線演算部１１１）
ステップ２：平文Ｍ←Ｍ' ｘｏｒ ｘ２
ステップ１は図２、図３を用いて実行する。
【００４６】
以上により、与えられた座標（ｘ，ｙ）のｄスカラー倍のｘ座標を求める処理において、  ｄのビットパターンに依存せず、ｄの各ビットあたり８回の相異なる乗算処理で実現することができる。また、ｄの与えられたｘ座標に対して、乱数ｋにより［ｋｘ２，ｋ］をスカラー倍初期値とすることによって、常に演算対象を変動させることができる。さらに、これらの組合わせにより、ｄのビットパターンが、ｄ（ｘ，ｙ）処理時間の偏差に現れないため、ｄ（ｘ，ｙ）処理時間の偏差情報から秘密鍵情報がもれない方法を示した。また、この性質は暗号処理の電流、電圧、電力の偏差を用いて、暗号解読を行うＤＰＡ(Differential Power Analysis)に対して、ｄ（ｘ，ｙ）の処理電流（電圧、電力）の偏差情報から秘密鍵情報がもれない方法をも示している。
【００４７】
次に第１実施例を更に高速化を図ることが可能な第２実施例を説明する。アフィン座標から、射影座標への変換を（ｘ，ｙ）→［ｘ，ｙ，１］とする場合、Ｚ４＝１とできる。（２）、（３）式にＺ４＝１を代入すると、
X3=(X4β2)+(X0(Z1)2)( X0(Z1)2) ------------（６）
Z3=β -----------------------------------（７）
この式を利用してスカラー倍方法、加算方法を以下のように求めることができる。
【００４８】
＜第２実施例スカラー倍方法＞
これを図６、図７に示す。Ｒのｘ座標の射影座標成分Ｘ０、スカラー値ｍを入力とし、  Ｒのｍ倍の点のｘ座標の射影座標成分Ｘｍを出力とする。ｍ，Ｘ０を入力し（ステップ６０２）、以下のステップ６０３から６０４ではＸ０を射影座標に変換する。Ｘ０をＸ１に代入し（ステップ６０３）、１をＺ１に代入する（ステップ６０４）。ステップ６０５から６０７ではスカラー倍の準備を行う。すなわち、［Ｘ１，Ｚ１］を［Ｘ４，Ｚ４］に代入し（ステップ６０５）、［Ｘ１，Ｚ１］を２倍方法（図５）に入力し、出力を［Ｘ２，Ｚ２］へ代入する（ステップ６０６）。ｍの２進数表現をｈｉｈｉ−１．．．ｈ０とする（ステップ６０７）。ただし、最上位ビットｈｉは１である。１をｉに代入する（ステップ７０１）。以下のステップ７０２から７０９ではｍの１ビットが０か１かによって加算方法や２倍方法を制御しスカラー倍を求める。すなわち、ｉ−１をｉに代入し（ステップ７０２）、［Ｘ１，Ｚ１］、［Ｘ２，Ｚ２］、Ｘ０を加算方法（図８）に入力し、出力を［Ｘ３，Ｚ３］へ代入する（ステップ７０３）。ｈｉ＝＝０ならば、ステップ７０６へ、１ならばステップ７０８へ進む（ステップ７０４）。［Ｘ１，Ｚ１］  を２倍方法（図５）に入力し、出力を［Ｘ１，Ｚ１］に代入する（ステップ７０５）。［Ｘ３，  Ｚ３］を［Ｘ２，Ｚ２］に代入し、ステップ７１０へいく（ステップ７０６）。［Ｘ２，Ｚ２］を２倍方法（図５）に入力し、出力を［Ｘ２，Ｚ２］に代入する（ステップ７０７）。［Ｘ３，  Ｚ３］を［Ｘ１，Ｚ１］へ代入し、ステップ７１０へいく（ステップ７０８）。ｉ＞０ならばステップ７０３へ進む（ステップ７０９）。Ｘ１／（Ｚ１）２をＸｍに代入し（ステップ７１０）、Ｘｍを出力する（ステップ７１１）。
【００４９】
＜第２実施例加算方法＞
これを図８に示す。［Ｘ１，Ｚ１］，［Ｘ２，Ｚ２］，Ｘ４を入力とし、［Ｘ３，Ｚ３］または無限遠点を出力とする。［Ｘ１，Ｚ１］，［Ｘ２，Ｚ２］，Ｘ４を入力し（ステップ８０２）、以下のステップ８０３から８０７は加算結果が無限遠点か判定するためにＸ１（Ｚ２）２＋    Ｘ２（Ｚ１）２を求める。さらに各中間結果Ｓ１、Ｓ２、Ｂは、上記式（６），（７）を求めるための準備である。すなわち、Ｘ１Ｚ２２をＳ１に代入し（ステップ８０３）、Ｘ２Ｚ１２をＳ２に代入し（ステップ８０４）、Ｓ１＋Ｓ２をＢに代入する（ステップ８０５）。Ｂ＝＝０の場合は、ステップ８０７へ進み、成立しない場合ステップ８０８へ進む（ステップ８０６）。無限遠点を出力し、ステップ８１３へいく（ステップ８０７）。以下のステップ８０８から８１１は上記式（６），（７）に従って［Ｘ３，Ｚ３］を求める。すなわち、ＢをＺ３に代入し（ステップ８０８）、Ｓ１Ｓ２をＳに代入し（ステップ８０９）、Ｘ４Ｚ３２をＭに代入し（ステップ８１０）、Ｍ＋ＳをＸ３に代入し（ステップ８１１）、［Ｘ３，Ｚ３］を出力する（ステップ８１２）。
【００５０】
以上により、相異なる変数の乗算４回で加算演算を実行できる。このため、第１実施例の加算演算より、乗算回数を減らすことができる。なお、２倍演算は第１実施例の２倍演算を利用する。
【００５１】
上述した処理時間の偏差情報から秘密鍵情報が漏れない方法は、２の拡大体上の楕円曲線の場合の他、素体上の楕円曲線でも適用可能である。
【００５２】
次に第３実施例を説明する。素体上の楕円曲線Ｂｙ２＝ｘ３＋Ａｘ２＋Ｂｘの場合、モンゴメリ法を用いて、処理時間の偏差情報から秘密鍵情報がもれない方法を示す。
【００５３】
P.Montgomery,"Speeding the Pollard and Elliptic Curve Methods of Factorization", Mathematics of computation Vol.48,No.177,pp.243-264(1987)では、有限素体上の楕円曲線の標準形  Ｂｙ２＝ｘ３＋Ａｘ２＋Ｂｘを用いて、点Ｐ０（ｘ０，ｙ０），Ｐ１（ｘ１，ｙ１）の加算と、減算を
Ｐ３（ｘ３，ｙ３）；  Ｐ４（ｘ４，ｙ４）；
Ｐ１＋Ｐ０＝Ｐ３      ；
Ｐ１−Ｐ０＝Ｐ４    ；  とするとき、
ｘ０，ｘ１，ｘ４から、ｘ３が高速に求まる。具体的には、次のように素体の乗算６回で求まる。
【００５４】
（ｘ３，ｙ３）→［Ｘ３，Ｚ３］；（ｘ４，ｙ４）→［Ｘ４，Ｚ４］；
とするとき、
Ｘ３←Ｚ４［（Ｘ１−Ｚ１）（Ｘ０＋Ｚ０）＋（Ｘ１＋Ｚ１）（Ｘ０−Ｚ０）］２  ；
Ｚ３←Ｘ４［（Ｘ１−Ｚ１）（Ｘ０＋Ｚ０）−（Ｘ１＋Ｚ１）（Ｘ０−Ｚ０）］２  ；
また、２倍演算は、
Ｐ５＝２Ｐ１；（ｘ１，ｙ１）→［Ｘ１，Ｚ１］；
４Ｘ１Ｚ１←（Ｘ１＋Ｚ１）２−（Ｘ１−Ｚ１）２  ；
X5←(X1+Z1)2(X1-Z1)2；Z5←(4X1Z1)[(X1-Z1)2+((A+2)/4)(4X1Z1)] ；
また、Ｐ１の２倍点Ｐ５（ｘ５，ｙ５）とするとき、ｘ５は、ｘ１のみから求まり、乗算５回である。これを利用して、点Ｒのスカラ倍（スカラー値ｄ）のｘ座標を以下のようにＲｘから求める。
【００５５】
初期値を［Ｒ，２Ｒ］、ｍＲをＲのｍ倍のｘ座標とするとき、ｄを２進数展開し、ｄの上位ビットから、
０の場合、［ｍＲ，（ｍ＋１）Ｒ］→［２ｍＲ，（２ｍ＋１）Ｒ］
１の場合、［ｍＲ，（ｍ＋１）Ｒ］→［（２ｍ＋１）Ｒ，２（ｍ＋１）Ｒ］
（ｍ＋１）Ｒ−ｍＲ＝Ｒ
（ｍ＋１）Ｒ＋ｍＲ＝（２ｍ＋１）Ｒである。
【００５６】
＜第３実施例スカラー倍方法＞
Ｒのｘ座標の射影座標成分Ｘ０、スカラー値ｍを入力とし、Ｒのｍ倍の点のｘ座標の射影座標成分Ｘｍを出力とする。  ｍ，Ｘ０を入力を入力し（ステップ９０２）、ステップ９０３から９０５では乱数を射影座標の各座標に乗算することにより、データを撹拌する。すなわち、乱数ｋを生成し（ステップ９０３）、乱数ｋとＸ０を演算してｋＸ０をＸ１に代入し（ステップ９０４）、乱数ｋをＺ１に代入する（ステップ９０５）。次に、［Ｘ１，Ｚ１］を［Ｘ４，Ｚ４］に代入し（ステップ９０６）、［Ｘ１，Ｚ１］を２倍方法（モンゴメリの２倍演算）に入力し、出力を［Ｘ２，Ｚ２］へ代入する（ステップ９０７）。ｍの２進数表現をｈｉｈｉ−１．．．ｈ０とする（ステップ９０８）。ただし、最上位ビットｈｌは１である。ｉをｌとする（ステップ９０９）。ｉ−１をｉに代入し（ステップ９１０）、［Ｘ１，Ｚ１］、［Ｘ２，Ｚ２］、［Ｘ４，  Ｚ４］を加算方法（モンゴメリの加算演算）に入力し、出力を［Ｘ３，Ｚ３］へ代入する（ステップ９１１）。ここで、ｈｉ＝＝０ならば、ステップ９１２へ、１ならばステップ９１４へ進む（ステップ９１２）。［Ｘ１，Ｚ１］を２倍方法（モンゴメリの２倍演算）に入力し、出力を［Ｘ１，Ｚ１］に代入する（ステップ９１３）。［Ｘ３，Ｚ３］を［Ｘ２，Ｚ２］に代入し、ステップ９１６へいく（ステップ９１４）。［Ｘ２，Ｚ２］を２倍方法（モンゴメリの２倍演算）に入力し、出力を［Ｘ２，Ｚ２］に代入する（ステップ９１５）。［Ｘ３，  Ｚ３］を［Ｘ１，Ｚ１］に代入し、ステップ９１６へいく（ステップ９１６）。ｉ＞０ならばステップ９１０へ進む（ステップ９１７）。Ｘ１／Ｚ１をＸｍに代入し（ステップ９１８）、Ｘｍを出力する（ステップ９１９）。
【００５７】
以上により、与えられた座標（ｘ，ｙ）のｄスカラー倍のｘ座標を求める処理において、ｄの各ビットあたり１１回の相異なる乗算処理で実現し、与えられたｘ座標に対して、乱数ｋにより［ｋｘ，ｋ］をスカラー倍初期値とすることによって、ｄ（ｘ，ｙ）処理時間の偏差情報から秘密鍵情報がもれない方法を示した。また、この性質は暗号処理の電流、電圧、電力の偏差を用いて、暗号解読を行うＤＰＡに対して、ｄ（ｘ，ｙ）の処理電流（電圧、電力）の偏差情報から秘密鍵情報がもれない方法を示している。
【００５８】
さらに、素体上の楕円曲線ｙ２＝ｘ３＋ａｘ＋ｂの場合、Ｂｙ２＝ｘ３＋Ａｘ２＋Ｂｘとｙ２＝ｘ３＋ａｘ＋ｂの間に有理点がなすアーベル群が同型となる楕円曲線を構成し、素体上の楕円曲線ｙ２＝ｘ３＋ａｘ＋ｂで与えられた（ｘ，ｙ）をＢｙ２＝ｘ３＋Ａｘ２＋Ｂｘに変換し、上記発明の方法でスカラー倍を求め、結果をｙ２＝ｘ３＋ａｘ＋ｂに変換することにより本発明を利用することができる。
【００５９】
次に第４実施例を説明する。第１実施例では、射影座標を任意のλ≠０について，［Ｘ，Ｙ，Ｚ］＝［λ２Ｘ，λ３Ｙ，λＺ］とするものを説明したが、［Ｘ，Ｙ，Ｚ］＝［λＸ，λＹ，λＺ］とする射影座標で実施することもできる。
【００６０】
＜第４実施例スカラー倍方法＞
Ｒのｘ座標の射影座標成分Ｘ０、スカラー値ｍを入力とし、Ｒのｍ倍の点のｘ座標の射影座標成分Ｘｍを出力とする。ｍ，Ｘ０を入力し（ステップ１００２）、以下のステップ１００３から１００５では乱数を射影座標の各座標に乗算することにより、データを撹拌する。すなわち、乱数ｋを生成し（ステップ１００３）、ｋＸ０をＸ１に代入し（ステップ１００４）、乱数ｋをＺ１に代入する（ステップ１００５）。［Ｘ１，Ｚ１］を［Ｘ４，Ｚ４］に代入し（ステップ１００６）、［Ｘ１，Ｚ１］を２倍方法に入力し、出力を［Ｘ２，Ｚ２］へ代入する（ステップ１００７）。ｍの２進数表現をｈｉｈｉ−１．．．ｈ０とする（ステップ１００８）。ただし、最上位ビットｈｌは１である。ｉをｌとする（ステップ１００９）。ｉ−１をｉに代入し（ステップ１０１０）、［Ｘ１，Ｚ１］、［Ｘ２，Ｚ２］、［Ｘ４，Ｚ４］を加算方法に入力し、出力を［Ｘ３，Ｚ３］へ代入する（ステップ１０１１）。ここで、ｈｉ＝＝０ならば、ステップ１０１２へ、１ならばステップ１０１４へ進む（ステップ１０１２）。［Ｘ１，Ｚ１］を２倍方法に入力し、出力を［Ｘ１，Ｚ１］に代入する（ステップ１０１３）。［Ｘ３，Ｚ３］を［Ｘ２，Ｚ２］に代入し、ステップ１０１６へいく（ステップ１０１４）。［Ｘ２，Ｚ２］を２倍方法に入力し、出力を［Ｘ２，Ｚ２］に代入する（ステップ１０１５）。［Ｘ３，Ｚ３］を［Ｘ１，  Ｚ１］に代入し、ステップ１０１６へいく（ステップ１０１６）。ｉ＞０ならばステップ１０１０へ進む（ステップ１０１７）。Ｘ１／Ｚ１をＸｍに代入し（ステップ１０１８）、Ｘｍを出力する（ステップ１０１９）。
【００６１】
楕円曲線上の点の射影空間座標として、任意のλ≠０について，［Ｘ，Ｙ，Ｚ］＝［λＸ，  λＹ，λＺ］とする。ここで、楕円曲線上の点Ｐ０＝（ｘ０，ｙ０）＝［Ｘ０，Ｙ０，Ｚ０］；  Ｐ１＝（ｘ１，ｙ１）＝［Ｘ１，Ｙ１，Ｚ１］とする。この和と差をＰ３＝（ｘ３，ｙ３）＝［Ｘ３，Ｙ３，Ｚ３］，Ｐ４＝（ｘ４，ｙ４）＝［Ｘ４，Ｙ４，Ｚ４］とする。
【００６２】
Ｐ１＋Ｐ０＝Ｐ３；
Ｐ１−Ｐ０＝Ｐ４；
第１実施例の（１）式ｘ３＋ｘ４＝（ｘ０ｘ１）／（ｘ０＋ｘ１）２より射影座標での関係式を導出する。
【００６３】
ｘ１＝Ｘ１／Ｚ１、ｘ０＝Ｘ０／Ｚ０を（１）式に代入する。
Ｘ３／Ｚ３＝Ｘ４／Ｚ４＋（（Ｘ０／Ｚ０）（Ｘ１／Ｚ１））／（Ｘ０／Ｚ０＋Ｘ１／Ｚ１）２；
＝Ｘ４／（Ｚ４）２＋（（Ｘ０Ｚ０）（  Ｘ１Ｚ１））／（  Ｘ０Ｚ１＋  Ｘ１Ｚ０）２；
＝（（Ｘ４β２）＋Ｚ４２（Ｘ０Ｚ０）（  Ｘ１Ｚ１））／（Ｚ４２β２）
ただし、β＝  Ｘ０Ｚ１＋  Ｘ１Ｚ０
これより、Ｘ３＝（Ｘ４β２）＋Ｚ４２（Ｘ０Ｚ１）（  Ｘ１Ｚ０）；  −−（２）'
Ｚ３＝Ｚ４２β２；  −−−−−−−−−−−−−−−−−−−−−（３）'  を得た。
【００６４】
ここで、ｍＲ＝［Ｘ１，Ｙ１，Ｚ１］、（ｍ＋１）Ｒ＝［Ｘ２，Ｙ２，Ｚ２］、Ｒ＝［Ｘ４，Ｙ４，Ｚ４］、（２ｍ＋１）Ｒ＝［Ｘ３，Ｙ３，Ｚ３］とする。この導出式を利用した加算方法を以下に説明する。
【００６５】
＜第４実施例加算方法＞
射影座標［Ｘ１，Ｚ１］，［Ｘ２  ，Ｚ２］，［Ｘ４  ，  Ｚ４］を入力とし、［Ｘ３，Ｚ３］  または無限遠点を出力とする。［Ｘ１，Ｚ１］，［Ｘ２，Ｚ２］，［Ｘ４，Ｚ４］を入力し（ステップ１１０２）、Ｘ１Ｚ２をＳ１に代入し（ステップ１１０３）、Ｘ２Ｚ１をＳ２に代入し（ステップ１１０４）、Ｓ１＋Ｓ２をＢに代入する（ステップ１１０５）。Ｂ＝＝０の場合は、ステップ１１０７へ進み、成立しない場合ステップ１１０８へ進む（ステップ１１０６）。無限遠点を出力し、ステップ１１１３へいく（ステップ１１０７）。（Ｚ４）２Ｂ２をＺ３に代入し（ステップ１１０８）、（Ｚ４）２Ｓ１Ｓ２をＳに代入し（ステップ１１０９）、（Ｘ４Ｂ２）をＭに代入し（ステップ１１１０）、Ｍ＋ＳをＸ３に代入し（ステップ１１１１）、［Ｘ３，Ｚ３］を出力する（ステップ１１１２）。
【００６６】
以上により、相異なる変数の乗算６回で加算演算を実行できる。
【００６７】
次に、２倍計算方法について説明する。Ｐ１の２倍点をＰ２とし、Ｐ１＝（ｘ１，ｙ１）＝［Ｘ１，Ｙ１，Ｚ１］、Ｐ２＝（ｘ２，ｙ２）＝［Ｘ２，Ｙ２，Ｚ２］とする。２倍演算の演算式  ｘ２＝（ｘ１）２＋ｂ／（ｘ１）２より、ｘ１＝Ｘ１／Ｚ１、ｘ２＝Ｘ２／Ｚ２をこの式に代入する。
【００６８】
X2/Z2=(X1/Z1)2+b/(X1/Z1)2=X12/(Z1)2+(bZ12)/(X1)2=(X14+bZ14)/(X12Z12)
従って、
Ｘ２＝Ｘ１４＋ｂＺ１４−−−−−（４）'
Ｚ２＝Ｘ１２Ｚ１２−−−−−−−−−−（５）'
この導出式を利用した２倍方法を以下に説明する。
【００６９】
＜第４実施例２倍計算方法＞
Ｑ＝［Ｘ１  ，Ｚ１］，ｂを入力とし、２Ｑ＝［Ｘ２，Ｚ２］または無限遠点を出力する。Ｘ１，Ｚ１を入力し（ステップ１２０２）、Ｘ２＝＝０またはＺ２＝＝０の場合、ステップ１２０４へ。成立しない場合、ステップ１２０５へいく（ステップ１２０３）。ステップ１２０４では、無限遠点を出力する。Ｚ２＝Ｘ１２Ｚ１２とし（ステップ１２０５）、Ｓ＝ｂＺ１４とし（ステップ１２０６）、Ｘ１４＋ＳをＸ２に代入し（ステップ１２０７）、［Ｘ２，Ｚ２］を出力する（ステップ１２０８）。かかる方法により、相異なる変数の乗算２回で加算演算を実行できる。
【００７０】
以上により、与えられた座標（ｘ，ｙ）のｄスカラー倍のｘ座標を求める処理において、ｄの各ビットあたり８回の相異なる乗算処理で実現し、与えられたｘ座標に対して、乱数ｋにより［ｋｘ，ｋ］をスカラー倍初期値とすることによって、ｄ（ｘ，ｙ）処理時間の偏差情報から秘密鍵情報がもれない方法を示した。暗号解読ＤＰＡに対して、ｄ（ｘ，ｙ）の処理電流（電圧、電力）の偏差情報から秘密鍵情報がもれない方法を示している。
【００７１】
次に第５実施例を説明する。第２実施例では、射影座標を任意のλ≠０について，［Ｘ，Ｙ，Ｚ］＝［λ２Ｘ，λ３Ｙ，λＺ］とするものを説明したが、［Ｘ，Ｙ，Ｚ］＝［λＸ，λＹ，λＺ］とする射影座標で実施することもできる。
【００７２】
アフィン座標から、射影座標への変換を（ｘ，ｙ）→［ｘ，ｙ，１］とする場合、Ｚ４＝１  とできる。
【００７３】
＜第５実施例スカラー倍方法＞
Ｒのｘ座標の射影座標成分Ｘ０、スカラー値ｍを入力とし、Ｒのｍ倍の点のｘ座標の射影座標成分Ｘｍを出力とする。ｍ，Ｘ０を入力し（ステップ１３０２）、乱数ｋを生成し（ステップ１３０３）、ｋＸ０をＸ１に代入する（ステップ１３０４）。１をＺ１に代入する（ステップ１３０５）。［Ｘ１，Ｚ１］を［Ｘ４，Ｚ４］に代入し（ステップ１３０６）、［Ｘ１，Ｚ１］を２倍方法に入力し、出力を［Ｘ２，Ｚ２］へ代入する（ステップ１３０７）。ｍの２進数表現をｈｉｈｉ−１．．．ｈ０とする。ただし、最上位ビットｈｉは１である（ステップ１３０８）。１をｉに代入する（ステップ１３０９）。ｉ−１をｉに代入し（ステップ１３１０）、［Ｘ１，  Ｚ１］、［Ｘ２，Ｚ２］、Ｘ４を加算方法に入力し、出力を［Ｘ３，Ｚ３］へ代入する（ステップ１３１１）。ｈｉ＝＝０ならば、ステップ１３１２へ、１ならばステップ１３１４へ進む（ステップ１３１２）。［Ｘ１，Ｚ１］を２倍方法に入力し、出力を［Ｘ１，Ｚ１］に代入する（ステップ１３１３）。［Ｘ３，Ｚ３］を［Ｘ２，Ｚ２］へ代入し、ステップ１３１６へいく（ステップ１３１４）。［Ｘ２，Ｚ２］を２倍方法に入力し、出力を［Ｘ２，Ｚ２］に代入する（ステップ１３１５）。［Ｘ３，Ｚ３］を［Ｘ１，Ｚ１］へ代入し、ステップ１３１６へいく（ステップ１３１６）。ｉ＞０ならばステップ１３００へ進む（ステップ１３１７）。Ｘ１／Ｚ１をＸｍに代入し（ステップ１３１８）、Ｘｍを出力する（ステップ１３１９）。
【００７４】
＜第５実施例加算方法＞
［Ｘ１，Ｚ１］，［Ｘ２，Ｚ２］，Ｘ４を入力とし、［Ｘ３，Ｚ３］または無限遠点を出力とする。［Ｘ１，Ｚ１］，［Ｘ２，Ｚ２］，Ｘ４を入力する（ステップ１４０２）。Ｘ１Ｚ２をＳ１に代入し（ステップ１４０３）、Ｘ２Ｚ１をＳ２に代入し（ステップ１４０４）、Ｓ１＋Ｓ２をＢに代入する（ステップ１４０５）。Ｂ＝＝０の場合、ステップ１４０７へ、成立しない場合ステップ１４０８へ進む（ステップ１４０６）。無限遠点を出力し、ステップ１４１３へいく（ステップ１４０７）。次に、Ｂ２をＺ３に代入し（ステップ１４０８）、Ｓ１Ｓ２をＳに代入し（ステップ１４０９）、（Ｘ４Ｂ２）をＭに代入し（ステップ１４１０）、Ｍ＋ＳをＸ３に代入し（ステップ１４１１）し、［Ｘ３，Ｚ３］を出力する（ステップ１４１２）。以上により、相異なる変数の乗算４回で加算演算を実行できる。なお、２倍演算は、前述した実施例の２倍演算を利用する。尚、本実施例は２の拡大体上、素体上の楕円曲線どちらにも適用可能である。
【００７５】
次に第６実施例を説明する。図１の楕円曲線演算部を、図９における９０１の楕円曲線演算装置で実施する。９０１は点のｘ座標Ｘ０、スカラー値ｍ、２の拡大体上の楕円曲線の標準形ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂにおいけるｂを入力し（９０２）、ｍ倍の点のｘ座標をＸｍ出力する（９０３）。尚、本実施例は２の拡大体上の楕円曲線で説明するが、素体上の楕円曲線を用いた場合も同様の方法で実現可能である。
【００７６】
乱数生成部９０４は、乱数ｋを生成し、ｋを出力する（９０５）。射影座標変換部９０６には乱数生成部９０４からの乱数ｋの他、ｘ座標Ｘ０とスカラー値ｍ、ｂを入力し（９０５）、射影座標［ｋＸ０，ｋ］に変換する。これを［Ｘ１，Ｚ１］とする。スカラー倍部９０８は射影座標［Ｘ１，Ｚ１］とスカラー値ｍを入力し、［Ｘ１，Ｚ１］のｍ倍点を求め、そのｘ座標Ｘｍを出力する。ここで、スカラー倍部９０８は、先ず、［Ｘ１，Ｚ１］を［Ｘ４，Ｚ４］へ代入する。かかる［Ｘ４，Ｚ４］は、例えばスカラー倍部のメモリに予め記憶させておく。また［Ｘ１，Ｚ１］を９１３へ出力して、２倍点［Ｘ２，Ｚ２］を得る。次に、ｍを２進数展開して、上位ビットからビットが０の場合［Ｘ１，Ｚ１］を９１３に出力して９１３の出力である２倍点を［Ｘ１，Ｚ１］に代入する。その後［Ｘ１，Ｚ１］、［Ｘ２，Ｚ２］、［Ｘ４，Ｚ４］を９１０へ入力して出力である加算点を［Ｘ２，Ｚ２］に代入する。ビットが１の場合［Ｘ２，Ｚ２］を９１３に出力して９１３の出力である２倍点を［Ｘ２，Ｚ２］に代入する。その後［Ｘ１，Ｚ１］、［Ｘ２，Ｚ２］、［Ｘ４，Ｚ４］を９１０へ入力して出力である加算点を［Ｘ１，Ｚ１］に代入することによりｍ倍の点のＸｍ座標を得る。
【００７７】
加算演算部９１０では、［Ｘ１，Ｚ１］［Ｘ２，Ｚ２］［Ｘ４，Ｚ４］を入力し、［Ｘ３，Ｚ３］＝［Ｘ２，Ｚ２］＋［Ｘ１，Ｚ１］、［Ｘ４，Ｚ４］＝［Ｘ２，Ｚ２］−［Ｘ１，Ｚ１］となる［Ｘ３，Ｚ３］を以下のように求め出力する。
【００７８】
先ず、Ｓ１←Ｘ１Ｚ２２、Ｓ２←Ｘ２Ｚ１２、Ｂ←Ｓ１＋Ｓ２を計算する。ここでＢ＝＝０の場合、無限遠点を出力し終了となる。Ｂ＝０が成立しない場合、Ｚ３←Ｚ４Ｂ、Ｓ←Ｚ４２Ｓ１Ｓ２、Ｍ  ←Ｘ４Ｚ３２、Ｘ３←Ｍ＋Ｓを計算する。
【００７９】
２倍演算部９１３では、［Ｘ１，Ｚ１］、ｂを入力し、［Ｘ２，Ｚ２］＝［Ｘ１，Ｚ１］＋［Ｘ１，Ｚ１］となる［Ｘ２，Ｚ２］を以下のように求め出力する。すなわち、Ｘ１＝＝０またはＺ１  ＝＝０の場合、無限遠点を出力する。他の場合、Ｓ←Ｚ１２、Ｚ２←Ｘ１Ｓ、Ｘ２←Ｘ１４＋ｂ（Ｓ）４を計算する。
【００８０】
上記実施例では、ｘ座標Ｘ０を射影座標［ｋＸ０，ｋ］に変換した例を説明したが、射影座標［ｋ２Ｘ０，ｋ］に変換する場合にも適用可能である。
【００８１】
尚、上述した実施例にかかるプログラムは記録媒体に格納しておくことも可能である。
【００８２】
【発明の効果】
本発明により前記従来のより、高速に楕円曲線暗号処理を実行できる。また、楕円曲線暗号の実行方法において、ｄ（ｘ，ｙ）の処理時間がｄのビットパターンに依存しない処理方法を与えることによって、偏差情報から秘密鍵情報がもれずに処理できる。
【図面の簡単な説明】
【図１】本発明の楕円曲線暗号システムにおける処理の流れを示す図である。
【図２】本発明の第１の実施例を示す楕円曲線暗号実行方法及び装置においてスカラー倍方法を示すフローチャートである。
【図３】本発明の第１の実施例を示す楕円曲線暗号実行方法及び装置においてスカラー倍方法を示すフローチャートである。
【図４】本発明の第１の実施例を示す楕円曲線暗号実行方法及び装置を実行するための加算演算のフローチャートである。
【図５】本発明の第１の実施例を示す楕円曲線暗号実行方法及び装置を実行するための２倍演算のフローチャートである。
【図６】本発明の第２の実施例を示す楕円曲線暗号実行方法及び装置においてスカラー倍方法を示すフローチャートである。
【図７】本発明の第２の実施例を示す楕円曲線暗号実行方法及び装置においてスカラー倍方法を示すフローチャートである。
【図８】本発明の第２の実施例を示す楕円曲線暗号実行方法及び装置を実行するための加算演算のフローチャートである。
【図９】本発明の楕円曲線演算装置を構成図である。
【図１０】本発明の楕円曲線暗号システムの構成図である。
【符号の説明】
１０１  楕円曲線生成部、
１０２  公開鍵、秘密鍵生成部、
１０３  暗号化部、
１０４  復号化部、
１０５  素数生成部、
１０６  楕円曲線パラメタ設定、
１０７  ベースポイント生成部、
１０８  乱数生成部、
１０９  楕円曲線演算部、
１１０  データ暗号化処理部、
１１１  データ復号化処理部、
１１２  暗号文、
１１３  平文。
【図１】
0003796993.tif 000002
【図２】
0003796993.tif 000003
【図３】
0003796993.tif 000004
【図４】
0003796993.tif 000005
【図５】
0003796993.tif 000006
【図６】
0003796993.tif 000007
【図７】
0003796993.tif 000008
【図８】
0003796993.tif 000009
【図９】
0003796993.tif 000010
【図１０】
0003796993.tif 000011