(57)【特許請求の範囲】
【請求項１】
複数のレジスタ群の値を読み出して、乗算系の演算処理を実行する乗算系演算手段と加算系の演算処理を実行する加算系演算手段とによって処理した演算結果を前記レジスタ群に格納する演算部によって、ｙ2＝ｘ3＋ａｘ＋ｂ（ｍｏｄ  ｐ）で表される素体上楕円曲線上の点（ｘ，ｙ）に乗数を乗算する際に、２進数系表現に変換された前記乗数に基づいて２倍算処理および加算処理を組み合わせて演算を行う方法であって、
前記演算部が、前記素体上楕円曲線上の点（ｘ，ｙ）を（ｘ，ｙ）＝（Ｘ／Ｚ2，Ｙ／Ｚ3）となるヤコビアン座標表現（Ｘ，Ｙ，Ｚ）に変換し、２倍算処理を連続して行う場合には、その連続した２倍算処理の時点（ｔ＋１）での演算結果（Ｘt+1，Ｙt+1，Ｚt+1）を現在のヤコビアン座標（Ｘt，Ｙt，Ｚt）を用いて、
Ｙt’＝２Ｙt
Ｍt＝３Ｘt2＋ａＺt4
Ｓt＝Ｘt（Ｙt’）2
Ｔt＝（Ｙt’）4／２
Ｘt+1＝Ｍt2−２Ｓt
Ｙt+1＝Ｍt（Ｓt−Ｘt+1）−Ｔt
Ｚt+1＝Ｙt’Ｚt
の演算処理を、加算、減算、２倍算、３倍算及び１／２算については加算系演算手段により実行し、その他の乗算及び指数演算は乗算系演算手段により実行することを特徴とする素体上楕円曲線上の点の演算方法。
【請求項２】
複数のレジスタ群の値を読み出して、乗算系の演算処理を実行する乗算系演算手段と加算系の演算処理を実行する加算系演算手段とによって処理した演算結果を前記レジスタ群に格納する演算部によって、ｙ2＝ｘ3＋ａｘ＋ｂ（ｍｏｄ  ｐ）で表される素体上楕円曲線上の点（ｘ，ｙ）に乗数を乗算する際に、２進数系表現に変換された前記乗数に基づいて２倍算処理および加算処理を組み合わせて演算を行う方法であって、
前記演算部が、前記素体上楕円曲線上の点（ｘ，ｙ）を（ｘ，ｙ）＝（Ｘ／Ｚ2，Ｙ／Ｚ3）となるヤコビアン座標表現（Ｘ，Ｙ，Ｚ）に変換し、２倍算処理を連続して行う場合には、初回は、
Ｙ0’＝２Ｙ0
Ｗ0＝ａＺ04
Ｍ0＝３Ｘ02＋Ｗ0
Ｓ0＝Ｘ0（Ｙ0’）2
Ｔ0＝（Ｙ0’）4
Ｘ1＝Ｍ02−２Ｓ0
Ｙ1’＝２Ｍ0（Ｓ0−Ｘ1）−Ｔ0
Ｚ1＝Ｙ0’Ｚ0
を演算し、２回目以降はその連続した２倍算処理の時点（ｔ＋１）での演算結果（Ｘt+1，Ｙt+1’，Ｚt+1）を現在の座標（Ｘt，Ｙt’，Ｚt）を用いて、
Ｗt＝Ｔt-1Ｗt-1
Ｍt＝３Ｘt2＋Ｗt
Ｓt＝Ｘt（Ｙt’）2
Ｔt＝（Ｙt’）4
Ｘt+1＝Ｍt2−２Ｓt
Ｙt+1’＝２Ｍt（Ｓt−Ｘt+1）−Ｔt
Ｚt+1＝Ｙt’Ｚt
として演算処理を行い、最終回には、Ｙt+1＝Ｙt+1’／２を演算する処理を、加算、減算、２倍算、３倍算及び１／２算については加算系演算手段により実行し、その他の乗算及び指数演算は乗算系演算手段により実行することを特徴とする素体上楕円曲線上の点の演算方法。
【請求項３】
連続した２倍算処理の時点（ｔ＋１）での演算処理において、前回の時点（ｔ）での演算結果（Ｘt，Ｙt’，Ｚt）を求める際に用いたＷt-1＝ａＺt-14とＴt-1＝（Ｙt-1’）4とを用いて２倍算処理を行うとともに、この２倍算処理において求めたＷt＝ａＺt4とＴt＝（Ｙt’）4とを記憶しておくことを特徴とする、請求項２に記載の素体上楕円曲線上の点の演算方法。
【請求項４】
連続した２倍算処理の時点（ｔ＋１）において、演算結果（Ｘt+1，Ｙt+1’，Ｚt+1）以外の情報を出力しないことを特徴とする、請求項２または３に記載の素体上楕円曲線上の点の演算方法。
【請求項５】
ｙ2＝ｘ3＋ａｘ＋ｂ（ｍｏｄ  ｐ）で表される素体上楕円曲線上の点（ｘ，ｙ）に対応して（ｘ，ｙ）＝（Ｘ／Ｚ2，Ｙ／Ｚ3）となるヤコビアン座標表現とした点（Ｘ，Ｙ，Ｚ）および乗数が格納される領域を有する記憶手段と、
乗算系の演算処理を実行する乗算系演算手段と加算系の演算処理を実行する加算系演算手段とを備え、前記記憶手段に格納された乗数を２進数系表現に変換し、この乗数に基づいて前記ヤコビアン座標に２倍算処理または加算処理と２倍算処理とを前記乗算系演算手段および加算系演算手段により選択的に行って次のヤコビアン座標を演算する演算手段と、
前記演算手段の乗算系演算手段および加算系演算手段による演算結果を一時的に格納するレジスタ群と、
前記演算手段により演算された次のヤコビアン座標を前記記憶手段に出力する出力手段と、
を備え、前記演算手段により演算されて前記記憶手段に記憶されたヤコビアン座標を用いて、前記乗数に基づく演算を連続的に行うとともに、前記演算手段による演算が連続する２倍算処理である場合には、初回は、
Ｙ0’＝２Ｙ0
Ｗ0＝ａＺ04
Ｍ0＝３Ｘ02＋Ｗ0
Ｓ0＝Ｘ0（Ｙ0’）2
Ｔ0＝（Ｙ0’）4
Ｘ1＝Ｍ02−２Ｓ0
Ｙ1’＝２Ｍ0（Ｓ0−Ｘ1）−Ｔ0
Ｚ1＝Ｙ0’Ｚ0
を演算し、２回目以降はその連続した２倍算処理の時点（ｔ＋１）での演算結果（Ｘt+1，Ｙt+1’，Ｚt+1）を現在の座標（Ｘt，Ｙt’，Ｚt）を用いて、
Ｗt＝Ｔt-1Ｗt-1
Ｍt＝３Ｘt2＋Ｗt
Ｓt＝Ｘt（Ｙt’）2
Ｔt＝（Ｙt’）4
Ｘt+1＝Ｍt2−２Ｓt
Ｙt+1’＝２Ｍt（Ｓt−Ｘt+1）−Ｔt
Ｚt+1＝Ｙt’Ｚt
として演算処理を行い、最終回には、Ｙt+1＝Ｙt+1’／２を演算する処理を、加算、減算、２倍算、３倍算及び１／２算については加算系演算手段により実行し、その他の乗算及び指数演算は乗算系演算手段により実行することを特徴とする素体上楕円曲線上の点の演算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、素体上楕円曲線上の点の演算方法、特に、楕円曲線上の点に乗数を乗算する際に、２進数系表現に変換された乗数に基づいて２倍算処理および加算処理を組み合わせて演算を行う演算方法およびこの演算方法を実現する素体上楕円曲線上の点の演算装置に関する。
【０００２】
【従来の技術】
近年のコンピュータネットワークの発達により、データベースの検索や電子メール、電子ニュースなどの電子化された情報をネットワークを経由して送受信する機会が急速の増加してきている。さらに、これらを利用して、オンラインショッピングなどのサービスも提供されつつある。しかし、それに伴って、ネットワーク上の電子化されたデータを盗聴したり、改竄したり、または他人になりすましてサービスを受けるなどの違法行為についての問題が浮上してきている。特に、無線を利用したネットワークにおいては、傍受が容易なためこれらを防止する対策が望まれている。
【０００３】
これらの問題に対して暗号技術（ｅｎｃｒｙｐｔｉｏｎ  ｔｅｃｈｎｏｌｏｇｙ）を応用した暗号化電子メールや利用者認証システムが提案され、種々のネットワークにも導入されつつあり、コンピュータネットワークにおいて暗号化は必須の技術となりつつある。この意味でコンピュータネットワークにおいては暗号化は必須の技術であるといえる。
【０００４】
暗号化方式は、大別すると秘密鍵暗号系と公開鍵暗号系の２つの分類することができる。
【０００５】
秘密鍵暗号系は、送信者と受信者が同じ鍵を持つことにより暗号通信を行う方式である。すなわち、秘密鍵暗号系では、あるメッセージを秘密の暗号鍵に基づいて暗号化し相手に送り、受け手はこの暗号鍵を用いて暗号分を複合化しもとのメッセージに戻して情報を入手する。
【０００６】
公開鍵暗号系は、送信者は公開されている受信者の公開鍵でメッセージを暗号化して送信し、受信者は自分の秘密鍵でその暗号化メッセージを復号することで通信を行う方式である。すなわち、公開鍵暗号系では、公開鍵は暗号化のための鍵、秘密鍵は公開鍵により暗号化された暗号を復号するための鍵であり、公開鍵で暗号化した暗号が秘密鍵でのみ復号することができる。
【０００７】
秘密鍵暗号系では、個人が秘密に保管しなければならない鍵の数が通信相手の数だけ必要であり、必要な総鍵数はｎ人のネットワークの場合、ｎ（ｎ−１）／２個である。また、はじめて通信をする相手に対しては、何らかの方法で秘密鍵の配送を行う必要があるという点で欠点がある。この問題を避けるために、大規模なネットワークでは、鍵管理センタを設置し、センタとの間の秘密鍵のみを保管し、暗号通信を行う場合はセンタから送信相手との秘密鍵を得る方法が用いられる。この場合秘密鍵の総数はｎとなる。
【０００８】
一方公開鍵暗号系では、個人が秘密に保管する鍵は自分の秘密鍵のみであり、必要な総秘密鍵数もｎ人のネットワークの場合、ｎ個である。また、はじめて通信する相手に対しては、公開鍵の配送を行えばよく、鍵管理センタを設置して、ユーザの公開鍵をｎ個公開簿に登録し、センタから送信相手の公開鍵を得る方法が用いられる。この場合、センタは公開鍵の改竄を防ぐだけで、秘密に保管する必要がない。ただし、公開鍵方式は秘密鍵方式に比べて鍵のビット数が大きいため保管に要するファイルサイズが大きくなるという問題を内包している。
【０００９】
また、認証の場合、秘密鍵暗号系では、例えば、送信するメッセージを秘密鍵で圧縮変換し、送信文に付加して送り、受信側では同様に圧縮変換して比較する方式がとられている。しかし、送受信が同じ鍵であるため受信者は認証データを偽造することができる。
【００１０】
これに対して、公開鍵暗号系では、秘密鍵で暗号化することができるのは本人だけであるという特徴を利用する。送信者はメッセージを圧縮変換して秘密鍵で暗号化し、送信文に付加して送り、受信者は送信者の公開鍵で付加されたデータを復号化し、同様に圧縮変換したものと比較する方式がとられている。この場合は受信者が不正できない。
【００１１】
このように、認証系では公開鍵暗号系の技術は必要不可欠であるといえる。しかし、公開鍵暗号系には、暗号化／復号化に大量の処理が必要であるという大きな欠点があるため、一般には処理の速い秘密鍵暗号系をメッセージの暗号化に、公開鍵暗号系は認証用にというように組み合わせて用いられる場合が多い。
【００１２】
公開鍵暗号系の中で、現在ＩＥＥＥ  Ｐ１３６３，  ＡＮＳＩ  Ｘ  ９．６２などで標準化が進んでいるものに、楕円曲線暗号（Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ）がある。これは、楕円曲線の離散対数問題に基づくもので、Ｎ．  Ｋｏｂｌｉｔｚ（”Ａ  ｃｏｕｒｓｅ  ｉｎ  ｎｕｍｂｅｒ  ｔｈｅｏｒｙ  ａｎｄ  ｃｒｙｐｔｏｇｒａｐｈｙ”，  Ｓｐｒｉｎｇ−Ｖｅｒｌａｇ，  １９９７）と、Ｖ．  Ｍｉｌｌｅｒ（”Ｕｓｅ  ｏｆ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ  ｉｎ  ｃｒｙｐｔｏｇｒａｐｈｙ”，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｃｒｙｐｔｏ  ’８５，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ２１８（１９８６），  Ｓｐｒｉｎｇ−Ｖｅｒｌａｇ，  ｐｐ  ４１７−４２６）により提案された。
〔楕円曲線暗号に用いる楕円曲線〕
楕円曲線暗号に用いる主な楕円曲線は、素体上の楕円曲線（標準形：ｙ２＝ｘ３＋ａｘ＋ｂ（ｍｏｄｐ），ｐ：素数，ａ，ｂ：ＧＦ（ｐ）の元）と、２の拡大体上の楕円曲線（標準形：ｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂ（ｍｏｄ  ｆ），ｆ：ｎ次既約多項式，ａ，ｂ：ＧＦ（２ｎ）の元）である。この楕円曲線上の点Ｐ（ｘ，ｙ）および単位元となる無限遠点Οの集合は、加算に関して群をなす。楕円曲線は、この点の演算による離散対数問題に基づく暗号である。
〔楕円曲線の点の演算と離散対数問題〕
楕円曲線上の点の演算は以下のものが定義されている。
加算：Ｒ＝Ｐ＋Ｑ＝Ｑ＋Ｐ
２倍算：Ｒ＝２Ｐ＝Ｐ＋Ｐ
減算：Ｒ＝Ｐ−Ｑ
零点：Ο（無限遠点）＝Ｐ−Ｐ
スカラー倍算：ｋＰ＝Ｐ＋Ｐ＋・・・＋Ｐ（ｋ個のＰの和）
ここで、ｋＰとＰからｋを計算することは困難である。このことは、楕円曲線の離散対数問題と呼ばれており、この離散対数問題に関連する計算の困難性に基づいて公開鍵系の暗号とすることができる。
【００１３】
たとえば、公開鍵暗号系と知られる（有限体上の）ディフィ−ヘルマン（Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）鍵交換と同様の鍵交換方式を実現することができる。楕円曲線上のベースポイントをＧとし、Ａの秘密鍵をｓａとしＰａ＝ｓａＧを演算して公開鍵とする。また、Ｂの秘密鍵をｓｂとし、Ｐｂ＝ｓｂＧを演算してこれを公開鍵とする。ＡはＢの公開鍵Ｐｂと自分の秘密鍵ｓａから、ＫＡＢ＝ｓａＰｂ＝ｓａｓｂＧを演算することによって共通鍵を得ることができる。また、同様にして、ＢはＡの公開鍵Ｐａと自分の秘密鍵ｓｂから、ＫＢＡ＝ｓｂＰａ＝ｓｂｓａＧを演算することによって共通鍵を得ることができる。この方式は、ＥＣＤＨ（Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）方式と呼ばれ、秘密鍵ｓａ，ｓｂをスカラー量として楕円曲線上の点Ｇ、Ｐａ、Ｐｂに乗算する必要があり、暗号化／復号化の際に大量の演算処理を必要とする。この他にＥＣＤＳＡ方式やＥＣＥＳ方式なども提案されているが、演算処理が大きくなる点については同様である。
〔楕円曲線上の点のスカラー倍算〕
楕円曲線上の点のスカラー倍算は上記のように定義されるが、ｋの値が大きくなると計算量が膨大となるため、通常は、加算と２倍算を組み合わせたバイナリメソッド（Ｂｉｎａｒｙ  Ｍｅｔｈｏｄ）や加算と２倍算、減算を組み合わせたサインドバイナリメソッド（Ｓｉｇｎｅｄ  Ｂｉｎａｒｙ  Ｍｅｔｈｏｄ）、事前計算表を用いて用いてバイナリメソッドを複数ビット単位で行うウィンドウメソッド（Ｗｉｎｄｏｗ  Ｍｅｔｈｏｄ）などを用いて計算を行うことが提案されている。
〔素体上楕円曲線上における点の加算〕
楕円曲線上の点のスカラー倍算を行うためにバイナリーメソッドやウィンドウメソッドを用いる場合、２進数系の表現に変換された乗数に基づいて、２倍算処理または加算処理と２倍算処理を行って、楕円曲線上の点を次々に演算していくことにより結果を得ることができる。
【００１４】
素体上の楕円曲線ｙ２＝ｘ３＋ａｘ＋ｂ（ｍｏｄ  ｐ）での点の演算を定義する。点Ｐ＝（ｘ０，ｙ０）、点Ｑ＝（ｘ１，ｙ１）、点Ｒ＝（ｘ２，ｙ２）、単位元Ο（無限遠点）とすると、点の加算は次のように定義される。但し、−Ｐ＝（ｘ０，−ｙ０）と定義される。
【００１５】
１．点Ｐと単位元Οとの加算
Ｒ＝Ｐ＋Ο＝Ο＋Ｐ＝Ｐ
２．単位元Οの２倍算
Ｒ＝Ο＋Ο＝２Ο＝Ο
３．点Ｐと点−Ｐとの加算
Ｒ＝Ｐ−Ｐ＝Ο
４．点Ｐと点Ｑ（≠Ｐ）との加算
Ｒ＝Ｐ＋Ｑ＝（ｘ２，ｙ２）
ｘ２＝（（ｙ１−ｙ０）／（ｘ１−ｘ０））２−ｘ０−ｘ１（ｍｏｄ  ｐ）
ｙ２＝（（ｙ１−ｙ０）／（ｘ１−ｘ０））（ｘ０−ｘ１）−ｙ０（ｍｏｄ  ｐ）
５．点Ｐの２倍算
Ｒ＝Ｐ＋Ｐ＝２Ｐ＝（ｘ２，ｙ２）
ｘ２＝（（３ｘ０２−ａ）／２ｙ０）２−２ｘ０  （ｍｏｄ  ｐ）
ｙ２＝（（３ｘ０２−ａ）／２ｙ０）（ｘ０−ｘ２）−ｙ０（ｍｏｄ  ｐ）
〔点の三次元表現と演算〕
上述の楕円曲線上の点の加算は、もっとも基本的な方式であり、加算ごとに素体上の逆数演算が必要となる。通常、素体上の逆数演算は大量の処理が必要となるため、楕円曲線上の点を三次元表現することで、逆数演算を行わずに加算処理を行う方式が、Ｄ．  Ｖ．  ＣｈｕｄｎｏｖｓｋｙとＧ．  Ｖ．  Ｃｈｕｄｎｏｖｓｋｙにより、”Ｓｅｑｕｅｎｃｅｓ  ｏｆ  Ｎｕｍｂｅｒｓ  Ｇｅｎｅｒａｔｅｄ  ｂｙ  Ａｄｄｉｔｉｏｎ  ｉｎ  Ｆｏｒｍａｌ  Ｇｒｏｕｐｓ  ａｎｄ  Ｎｅｗ  Ｐｒｉｍａｌｉｔｙ  ａｎｄ  Ｆａｃｔｏｒｉｚａｔｉｏｎ  Ｔｅｓｔｓ”，  Ａｄｖａｎｃｅｓ  ｉｎ  Ａｐｐｌｉｅｄ  Ｍａｔｈｅｍａｔｉｃｓ，  Ｖｏｌ．  ７，  １９８６に提案されている。このうち、ヤコビアン（Ｊａｃｏｂｉａｎ）座標を用いれば、楕円曲線上の点は、（ｘ，ｙ）＝（Ｘ／Ｚ２，Ｙ／Ｚ３）となる（Ｘ，Ｙ，Ｚ）に投影される。この場合の点の加算および２倍算は、ＩＥＥＥ  Ｐ１３６３に掲載されており、次のように示される。
【００１６】
４’．点Ｐと点Ｑ（≠Ｐ）との加算
Ｒ＝Ｐ＋Ｑ＝（Ｘ２，Ｙ２，Ｚ２）
Ｕ０＝Ｘ０Ｚ１２
Ｕ１＝Ｘ１Ｚ０２
Ｓ０＝Ｙ０Ｚ１３
Ｓ１＝Ｙ１Ｚ０３
Ｗ＝Ｕ０−Ｕ１
Ｔ＝Ｕ０＋Ｕ１
Ｒ＝Ｓ０−Ｓ１
Ｍ＝Ｓ０＋Ｓ１
Ｖ＝ＴＷ２−２Ｘ２
Ｘ２＝Ｒ２−ＴＷ２
Ｙ２＝（ＶＲ−ＭＷ３）／２
Ｚ２＝Ｚ０Ｚ１Ｗ
５’．点Ｐの２倍算
Ｒ＝Ｐ＋Ｐ＝２Ｐ＝（Ｘ２，Ｙ２，Ｚ２）
Ｍ＝３Ｘ０２＋ａＺ０４
Ｓ＝４Ｘ０Ｙ０２
Ｔ＝８Ｙ０４
Ｘ２＝Ｍ２−２Ｓ
Ｙ２＝Ｍ（Ｓ−Ｘ２）−Ｔ
Ｚ２＝２Ｙ０Ｚ０
【００１７】
【発明が解決しようとする課題】
出願人は、特願平１０−３１１３７９号に、ヤコビアン座標を用いた楕円曲線上の点の演算を行う際に、演算途中の計算結果を利用して点の２倍算を連続実行するようにした素体上楕円曲線上の点の演算方法を提案した。この演算方法のアルゴリズムを下に示す。
【００１８】
0003615405.tif 000002
この方法を用いることにより、２倍算が連続する場合の乗算回数を削減することができる。ＩＥＥＥ  Ｐ１３６３に記載されているヤコビアン座標を用いた点の加算および２倍算に必要な計算量および特願平１０−３１１３７９号におけるべき値ｍの場合のべき乗倍算に必要な計算量を表１に示す。
【００１９】
【表１】
0003615405.tif 000003
【００２０】
ここで、加算系とは、加算、減算、２倍算、１／２算、３倍算、４倍算、８倍算の総称である。加算、減算、２倍算、１／２算の計算量を１とし、加算と２倍算とを１回ずつ実行することで可能な３倍算および２倍算を２回実行することで可能な４倍算の計算量を２とし、２倍算を３回実行することで可能な８倍算の計算量を３とする。
【００２１】
点の２倍算が連続して行われる場合には、ＩＥＥＥ  Ｐ１３６３の方法では、１０×べき値ｍ回の乗算を必要とするのに対して、特開平１０−３１１３７９号のものでは８ｍ＋２回となり、べき値ｍが多くなればそれだけ乗算回数が削減されることとなる。しかしながら、加算系の演算回数については、べき値ｍが多くなるにつれてむしろ増加してしまう。
【００２２】
計算機において、加算系の演算処理は乗算処理に比して非常に負担の小さい処理とされていたが、ハードウェア乗算器を備えたプロセッサなどでは、乗算処理と比較して加算系の処理が無視できるほど小さいものではない場合が多い。特に、ＤＳＰなどの高速なハードウェア乗算器を持つプロセッサにおいて楕円曲線上の点の加算、２倍算を高速に処理するためには、乗算回数の最適化のみならず、加算系の回数の最適化が重要な課題となる。
【００２３】
本発明の目的は、素体上楕円曲線上の点を３次元に投影したヤコビアン座標を用いることで逆数演算を行うことなく加算処理を可能とし、かつ付加的な座標を追加せずに高速な処理を可能とする素体上楕円曲線上の点の演算方法およびその装置を提案することにある。
【００２４】
【課題を解決するための手段】
本発明は、複数のレジスタ群の値を読み出して、乗算系の演算処理を実行する乗算系演算手段と加算系の演算処理を実行する加算系演算手段とによって処理した演算結果を前記レジスタ群に格納する演算部によって、ｙ2＝ｘ3＋ａｘ＋ｂ（ｍｏｄ  ｐ）で表される素体上楕円曲線上の点（ｘ，ｙ）に乗数を乗算する際に、２進数系表現に変換された前記乗数に基づいて２倍算処理および加算処理を組み合わせて演算を行う方法であって、
前記演算部が、前記素体上楕円曲線上の点（ｘ，ｙ）を（ｘ，ｙ）＝（Ｘ／Ｚ2，Ｙ／Ｚ3）となるヤコビアン座標表現（Ｘ，Ｙ，Ｚ）に変換し、２倍算処理を連続して行う場合には、その連続した２倍算処理の時点（ｔ＋１）での演算結果（Ｘt+1，Ｙt+1，Ｚt+1）を現在のヤコビアン座標（Ｘt，Ｙt，Ｚt）を用いて、
Ｙt’＝２Ｙt
Ｍt＝３Ｘt2＋ａＺt4
Ｓt＝Ｘt（Ｙt’）2
Ｔt＝（Ｙt’）4／２
Ｘt+1＝Ｍt2−２Ｓt
Ｙt+1＝Ｍt（Ｓt−Ｘt+1）−Ｔt
Ｚt+1＝Ｙt’Ｚt
の演算処理を、加算、減算、２倍算、３倍算及び１／２算については加算系演算手段により実行し、その他の乗算及び指数演算は乗算系演算手段により実行することを特徴とする素体上楕円曲線上の点の演算方法である（ただし、計算式の記載順は、計算順を特定するものではない）。
【００２５】
ヤコビアン座標を用いた演算において、４Ｙ２の演算を、４×Ｙ２として演算すると、乗算１回および加算系２回の計算量を必要とする。これに対して、４Ｙ２の演算を（２Ｙ）２として演算を行った場合、乗算１回および加算系１回の計算量となり、前者の場合と比して加算系を１回削減することができる。上述した本発明の演算方法では、Ｙ座標の２倍の値であるＹ’の値を先に計算し、このＹ’の値を用いることによって、ヤコビアン座標の点の２倍算における加算系の回数を削減している。
【００２６】
また、本発明では、複数のレジスタ群の値を読み出して、乗算系の演算処理を実行する乗算系演算手段と加算系の演算処理を実行する加算系演算手段とによって処理した演算結果を前記レジスタ群に格納する演算部によって、ｙ2＝ｘ3＋ａｘ＋ｂ（ｍｏｄ  ｐ）で表される素体上楕円曲線上の点（ｘ，ｙ）に乗数を乗算する際に、２進数系表現に変換された前記乗数に基づいて２倍算処理および加算処理を組み合わせて演算を行う方法であって、
前記演算部が、前記素体上楕円曲線上の点（ｘ，ｙ）を（ｘ，ｙ）＝（Ｘ／Ｚ2，Ｙ／Ｚ3）となるヤコビアン座標表現（Ｘ，Ｙ，Ｚ）に変換し、２倍算処理を連続して行う場合には、初回は、
Ｙ0’＝２Ｙ0
Ｗ0＝ａＺ04
Ｍ0＝３Ｘ02＋Ｗ0
Ｓ0＝Ｘ0（Ｙ0’）2
Ｔ0＝（Ｙ0’）4
Ｘ1＝Ｍ02−２Ｓ0
Ｙ1’＝２Ｍ0（Ｓ0−Ｘ1）−Ｔ0
Ｚ1＝Ｙ0’Ｚ0
を演算し、２回目以降はその連続した２倍算処理の時点（ｔ＋１）での演算結果（Ｘt+1，Ｙt+1’，Ｚt+1）を現在の座標（Ｘt，Ｙt’，Ｚt）を用いて、
Ｗt＝Ｔt-1Ｗt-1
Ｍt＝３Ｘt2＋Ｗt
Ｓt＝Ｘt（Ｙt’）2
Ｔt＝（Ｙt’）4
Ｘt+1＝Ｍt2−２Ｓt
Ｙt+1’＝２Ｍt（Ｓt−Ｘt+1）−Ｔt
Ｚt+1＝Ｙt’Ｚt
として演算処理を行い、最終回には、Ｙt+1＝Ｙt+1’／２を演算する処理を、加算、減算、２倍算、３倍算及び１／２算については加算系演算手段により実行し、その他の乗算及び指数演算は乗算系演算手段により実行することを特徴とする素体上楕円曲線上の点の演算方法を提案する。
【００２７】
従来の方法においては、Ｔｔ＝８Ｙｔ４，Ｗｔ＝ａＺｔ４からＷｔ＝２Ｔｔ−１Ｗｔ−１を演算していたのに対し、この方法を用いることによって、Ｔｔ＝（Ｙｔ’）４＝１６Ｙｔ４の演算結果を利用して、Ｗｔ＝Ｔｔ−１Ｗｔ−１＝１６Ｙｔ４Ｗｔとして演算することができる。したがって、Ｔｔの２倍算が不要となり計算量を削減することが可能となる。
【００２８】
また、２倍算処理が連続する場合の従来の演算方法では、（Ｘ０，Ｙ０，Ｚ０）の２ｔ倍点（Ｘｔ，Ｙｔ，Ｚｔ）から２ｔ＋１倍点（Ｘｔ＋１，Ｙｔ＋１，Ｚｔ＋１）を計算していたが、上述の方法では、点（Ｘｔ，２Ｙｔ，Ｚｔ）から点（Ｘｔ＋１，２Ｙｔ＋１，Ｚｔ＋１）を計算することによって点の２のべき乗倍算ループ毎に必要なＹ座標の２倍値の計算を削減することができ、初回のＹ０→２Ｙ１の２倍算および最終回のＹ座標の１／２算が増加するものの、全体として計算量を削減することが可能となる。
【００２９】
ここで、連続した２倍算処理の時点（ｔ＋１）での演算処理において、前回の時点（ｔ）での演算結果（Ｘｔ，Ｙｔ’，Ｚｔ）を求める際に用いたＷｔ−１＝ａＺｔ−１４とＴｔ−１＝Ｙｔ−１４とを用いて２倍算処理を行うとともに、この２倍算処理において求めたＷｔ＝ａＺｔ４とＴｔ＝（Ｙｔ’）４とを記憶するように構成できる。
【００３０】
また、連続した２倍算処理の時点（ｔ＋１）において、演算結果（Ｘｔ＋１，Ｙｔ＋１’，Ｚｔ＋１）以外の情報を出力しないように構成できる。
【００３１】
本発明に係る素体上楕円曲線上の点の演算装置は、記憶手段と、演算手段と、レジスタ群と、出力手段とを備えている。記憶手段は、ｙ2＝ｘ3＋ａｘ＋ｂ（ｍｏｄ  ｐ）で表される素体上楕円曲線上の点（ｘ，ｙ）に対応して（ｘ，ｙ）＝（Ｘ／Ｚ2，Ｙ／Ｚ3）となるヤコビアン座標表現とした点（Ｘ，Ｙ，Ｚ）および乗数が格納される領域を有する。演算手段は、乗算系の演算処理を実行する乗算系演算手段と加算系の演算処理を実行する加算系演算手段とを備えており、記憶手段に格納された乗数を２進数系表現に変換し、この乗数に基づいて前記ヤコビアン座標に２倍算処理または加算処理と２倍算処理とを乗算系演算手段と加算系演算手段とにより選択的に行って次のヤコビアン座標を演算する。レジスタ群は、演算手段の乗算系演算手段および加算系演算手段による演算結果を一時的に格納する。出力手段は、演算手段により演算された次のヤコビアン座標を記憶手段に出力する。しかして、演算手段により演算されて記憶手段に記憶されたヤコビアン座標を用いて、前記乗数に基づく演算を連続的に行うとともに、演算手段による演算が連続する２倍算処理である場合には、初回は、
Ｙ0’＝２Ｙ0
Ｗ0＝ａＺ04
Ｍ0＝３Ｘ02＋Ｗ0
Ｓ0＝Ｘ0（Ｙ0’）2
Ｔ0＝（Ｙ0’）4
Ｘ1＝Ｍ02−２Ｓ0
Ｙ1’＝２Ｍ0（Ｓ0−Ｘ1）−Ｔ0
Ｚ1＝Ｙ0’Ｚ0
を演算し、２回目以降はその連続した２倍算処理の時点（ｔ＋１）での演算結果（Ｘt+1，Ｙt+1’，Ｚt+1）を現在の座標（Ｘt，Ｙt’，Ｚt）を用いて、
Ｗt＝Ｔt-1Ｗt-1
Ｍt＝３Ｘt2＋Ｗt
Ｓt＝Ｘt（Ｙt’）2
Ｔt＝（Ｙt’）4
Ｘt+1＝Ｍt2−２Ｓt
Ｙt+1’＝２Ｍt（Ｓt−Ｘt+1）−Ｔt
Ｚt+1＝Ｙt’Ｚt
として演算処理を行い、最終回には、Ｙt+1＝Ｙt+1’／２を演算する処理を、加算、減算、２倍算、３倍算及び１／２算については加算系演算手段により実行し、その他の乗算及び指数演算は乗算系演算手段により実行することを特徴とする。
【００３２】
この装置によれば、前述したような演算方法を実現することができ、たとえば、２倍算処理を連続して行う場合には、レジスタ群に残っているＷおよびＴの値を用いて演算を行うことによって演算回数を軽減することが可能となり、演算を高速化することができる。
【００３３】
【発明の実施の形態】
本発明に素体上楕円曲線上の点の演算装置の１実施形態を図１を用いて説明する。
【００３４】
この演算装置１は、通常のＣＰＵおよびメモリを搭載したコンピュータにより実現されるものであって、主に記憶手段２と演算部３とで構成される。
【００３５】
記憶手段２は、楕円曲線上の点に対応するヤコビアン座標（Ｘ，Ｙ，Ｚ）や乗数ｋが格納される。
【００３６】
演算部３は、ヤコビアン座標に変換された楕円曲線上の点に乗数ｋを乗算する際に、バイナリーメソッドやウィンドウメソッドなどを用いて２倍算処理または加算処理と２倍算処理を選択的に行って楕円曲線上の点を次のヤコビアン座標として演算する演算手段４を備えている。また、演算部３は、演算手段４における演算に必要な入力変数を一時的に格納しておくレジスタ群５を備えている。また、演算部３は、演算手段４の演算結果を一時的に格納する演算結果出力用レジスタ６を備えている。
【００３７】
演算手段４では、記憶手段２に格納された現時点でのヤコビアン座標（Ｘｔ，Ｙｔ，Ｚｔ）を２倍算処理するか加算処理と２倍算処理とを行うかを、乗数ｋの値に基づいて選択し、演算処理を行う。
【００３８】
加算処理を行う場合には、４’として示した前述のアルゴリズムと同様であり、ここでは省略する。
〔第１実施形態〕
２倍算処理が連続する、いわゆる２のべき乗倍算を行う際に、その連続した２倍算処理の時点（ｔ＋１）での演算結果（Ｘｔ＋１，Ｙｔ＋１，Ｚｔ＋１）を現在のヤコビアン座標（Ｘｔ，Ｙｔ，Ｚｔ）を用いて、
Ｙｔ’＝２Ｙｔ
Ｍｔ＝３Ｘｔ２＋ａＺｔ４
Ｓｔ＝Ｘｔ（Ｙｔ’）２
Ｔｔ＝（Ｙｔ’）４／２
Ｘｔ＋１＝Ｍｔ２−２Ｓｔ
Ｙｔ＋１＝Ｍｔ（Ｓｔ−Ｘｔ）−Ｔｔ
Ｚｔ＋１＝Ｙｔ’Ｚｔ
とする第１のアルゴリズムの場合について考える。このときの処理を表すフローチャートを図２に示す。
【００３９】
入力されるヤコビアン座標を（Ｘ０，Ｙ０，Ｚ０）、出力するヤコビアン座標を（Ｘ１，Ｙ１，Ｚ１）とし、計算過程におけるテンポラリ値を格納しておく場所をレジスタ群Ｆ１〜Ｆ５とする。
【００４０】
ステップＳ１００では、記憶手段２に格納されている（Ｘ０，Ｙ０，Ｚ０）および楕円パラメータａをレジスタ群５に読み出す。ステップＳ１０１では、２×Ｙ０、Ｘ０×Ｘ０、Ｚ０×Ｚ０を演算し、演算結果をそれぞれレジスタＦ１、Ｆ４、Ｆ３に格納する。このとき、Ｆ１＝Ｙ０’となっている。
【００４１】
ステップＳ１０２では、レジスタＦ３の値を読み出してＦ３×Ｆ３を演算し、この演算結果をレジスタＦ３に再度格納する。さらに、レジスタＦ４の値を読み出して２×Ｆ４を演算しこの演算結果をＦ５に格納する。ここでは、Ｆ３＝Ｚ０４、Ｆ４＝２Ｘ０２となっている。
【００４２】
ステップＳ１０３では、レジスタＦ３の値を読み出してａ×Ｆ３を演算しこの演算結果をレジスタＦ２に格納する。さらに、レジスタＦ４、Ｆ５の値を読み出してＦ４＋Ｆ５を演算しこの演算結果をレジスタＦ４に格納する。このとき、Ｆ２＝ａＺ０４、Ｆ４＝３Ｘ０２となっている。
【００４３】
ステップＳ１０４では、レジスタＦ４、Ｆ２の値を読み出してＦ４＋Ｆ２を演算しこの演算結果をレジスタＦ４に格納する。このとき、Ｆ４＝３Ｘ０２＋ａＺ０４＝Ｍとなっている。
【００４４】
ステップＳ１０５では、Ｚ０の値とレジスタＦ１の値を読み出してＺ０×Ｆ１を演算しこの演算結果をＺ１として演算結果出力用レジスタ６に出力する。また、レジスタＦ１の値を読み出してＦ１×Ｆ１を演算しこの演算結果をレジスタＦ３に格納する。このとき、Ｚ１＝Ｙ０’Ｚ０、Ｆ３＝（Ｙ０’）２となっている。
【００４５】
ステップＳ１０６では、Ｘ０の値とレジスタＦ３の値を読み出してＸ０×Ｆ３を演算しこの演算結果をレジスタＦ５に格納する。また、レジスタＦ４の値を読み出してＦ４×Ｆ４を演算しこの演算結果をレジスタＦ１に格納する。このとき、Ｆ５＝Ｘ０×（Ｙ０’）２＝Ｓ、Ｆ１＝Ｍ２となっている。
【００４６】
ステップＳ１０７では、レジスタＦ５の値を読み出して２×Ｆ５を演算しこの演算結果をＸ１として演算結果出力用レジスタ６に出力する。このとき、Ｘ１＝２Ｓになっている。
【００４７】
ステップＳ１０８では、レジスタＦ１の値とＸ１の値を読み出してＦ１−Ｘ１を演算しこの演算結果をＸ１として演算結果出力用レジスタ６に出力する。このとき、Ｘ１＝Ｍ２−２Ｓとなっている。
【００４８】
ステップＳ１０９では、レジスタＦ３の値を読み出してＦ３×Ｆ３の演算を行いこの演算結果をレジスタＦ１に格納する。また、レジスタＦ５の値およびＸ１の値を読み出してＦ５−Ｘ１の演算を行いこの演算結果をレジスタＦ５に格納する。このとき、Ｆ１＝（Ｙ０’）４、Ｆ５＝Ｓ−Ｘ１となっている。
【００４９】
ステップＳ１１０では、レジスタＦ１の値を読み出してＦ１／２の演算を行いこの演算結果をレジスタＦ１に格納する。また、レジスタＦ５、Ｆ４の値を読み出してＦ５×Ｆ４を演算しこの演算結果をＹ１として演算結果出力用レジスタ６に出力する。このとき、Ｆ１＝（Ｙ０’）４／２＝８Ｙ０４、Ｙ１＝Ｍ（Ｓ−Ｘ１）となっている。
【００５０】
ステップＳ１１１では、Ｙ１の値およびレジスタＦ１の値を読み出してＹ１−Ｆ１を演算しこの演算結果をＹ１として演算結果出力用レジスタ６に出力する。このとき、Ｙ１＝Ｍ（Ｓ−Ｘ１）−Ｔとなっている。
【００５１】
最終的に演算された（Ｘ１，Ｙ１，Ｚ１）は記憶手段２に出力される。
【００５２】
べき乗倍算がさらに続く場合には、この（Ｘ１，Ｙ１，Ｚ１）の値を入力（Ｘ０，Ｙ０，Ｚ０）として同じ動作を繰り返し行うことで続けて演算することが可能である。
〔第２実施形態〕
２倍算処理が連続する、いわゆる２のべき乗倍算を行う際に、初回には、
Ｙ０’＝２Ｙ０
Ｗ０＝ａＺ０４
Ｍ０＝３Ｘ０２＋Ｗ０
Ｓ０＝Ｘ０（Ｙ０’）２
Ｔ０＝（Ｙ０’）４
Ｘ１＝Ｍ０２−２Ｓ０
Ｙ１’＝２Ｍ０（Ｓ０−Ｘ１）−Ｔ０
Ｚ１＝Ｙ０’Ｚ０
を演算し、２回目以降にはその連続した２倍算処理の時点（ｔ＋１）での演算結果（Ｘｔ＋１，Ｙｔ＋１’，Ｚｔ＋１）を現在の座標（Ｘｔ，Ｙｔ’，Ｚｔ）を用いて、
Ｗｔ＝Ｔｔ−１Ｗｔ−１
Ｍｔ＝３Ｘｔ２＋Ｗｔ
Ｓｔ＝Ｘｔ（Ｙｔ’）２
Ｔｔ＝（Ｙｔ’）４
Ｘｔ＋１＝Ｍｔ２−２Ｓｔ
Ｙｔ＋１’＝２Ｍｔ（Ｓｔ−Ｘｔ）−Ｔｔ
Ｚｔ＋１＝Ｙｔ’Ｚｔ
として演算処理を行い、最終回には、Ｙｔ＋１＝Ｙｔ＋１’／２を演算する第２のアルゴリズムの場合について考える。このときの処理を表すフローチャートを図３に示す。
【００５３】
入力されるヤコビアン座標を（Ｘ０，Ｙ０，Ｚ０）、連続する２倍算の途中におけるヤコビアン座標を（Ｘｉ，Ｙｉ，Ｚｉ）とし、計算過程におけるテンポラリ値を格納しておく場所をレジスタ群Ｆ１〜Ｆ５とする。
【００５４】
ステップＳ２００では、記憶手段２に格納されている（Ｘ０，Ｙ０，Ｚ０）、べき数ｍおよび楕円パラメータａをレジスタ群５に読み出す。ステップＳ２０１では、連続した２倍算の演算回数をカウントするための計数ｉを初期化する。
【００５５】
ステップＳ２０２では、点の２倍算ルーチンを実行し、得られた（Ｘｉ，Ｙｉ，Ｚｉ）の値およびＦ１、Ｆ２の値をレジスタ群５内に出力する。
【００５６】
ステップＳ２０３では、現在の連続２倍算の演算回数ｉが今回行うべき数ｍに到達したか否かを判別する。現在の連続２倍算の演算回数ｉが今回行うべき数ｍに到達していない場合には、ステップＳ２０４に移行する。ステップＳ２０４では、点の２倍算ループルーチンを実行する。ここでは、レジスタ群５中の（Ｘｉ，Ｙｉ，Ｚｉ）の値およびＦ１、Ｆ２の値を入力Ｘ０，Ｙ０，Ｚ０，Ｔ０，Ｗ０とし、演算の結果得られる値を再度（Ｘｉ，Ｙｉ，Ｚｉ）、Ｆ１、Ｆ２の値としてレジスタ群５に出力する。
【００５７】
ステップＳ２０５では、現在の連続２倍算の演算回数ｉをインクリメントする。この後、ステップＳ２０３に移行する。
【００５８】
ステップＳ２０３において、現在の連続２倍算の演算回数ｉが今回行うべき数ｍに到達したと判断した場合には、ステップＳ２０６に移行する。ステップＳ２０６では、レジスタ群５よりＹｉの値を読み出してＹｉ／２を演算しこの演算結果をＹｉとしてレジスタ群５に出力する。ステップＳ２０７では、（Ｘｉ，Ｙｉ，Ｚｉ）の値を２ｍ（Ｘ０，Ｙ０，Ｚ０）として演算結果出力用レジスタ６に出力する。
【００５９】
ステップＳ２０２における点の２倍算ルーチンを図４に示す。
【００６０】
ステップＳ３００では、記憶手段２に格納されている（Ｘ０，Ｙ０，Ｚ０）および楕円パラメータａをレジスタ群５に読み出す。
【００６１】
ステップＳ３０１では、２×Ｙ０、Ｘ０×Ｘ０、Ｚ０×Ｚ０を演算し、演算結果をそれぞれレジスタＦ１、Ｆ４、Ｆ３に格納する。このとき、Ｆ１＝Ｙ０’、Ｆ４＝Ｘ０２、Ｆ３＝Ｚ０２となっている。
【００６２】
ステップＳ３０２では、レジスタＦ３の値を読み出してＦ３×Ｆ３を演算し、この演算結果をレジスタＦ３に再度格納する。さらに、レジスタＦ４の値を読み出して２×Ｆ４を演算しこの演算結果をＦ５に格納する。ここでは、Ｆ３＝Ｚ０４、Ｆ５＝２Ｘ０２となっている。
【００６３】
ステップＳ３０３では、レジスタＦ３の値を読み出してａ×Ｆ３を演算しこの演算結果をレジスタＦ２に格納する。さらに、レジスタＦ４、Ｆ５の値を読み出してＦ４＋Ｆ５を演算しこの演算結果をレジスタＦ４に格納する。このとき、Ｆ２＝ａＺ０４＝Ｗ０、Ｆ４＝３Ｘ０２となっている。
【００６４】
ステップＳ３０４では、レジスタＦ４、Ｆ２の値を読み出してＦ４＋Ｆ２を演算しこの演算結果をレジスタＦ４に格納する。このとき、Ｆ４＝３Ｘ０２＋ａＺ０４＝Ｍ０となっている。
【００６５】
ステップＳ３０５では、Ｚ０の値とレジスタＦ１の値を読み出してＺ０×Ｆ１を演算しこの演算結果をＺｉとして演算結果出力用レジスタ６に出力する。また、レジスタＦ１の値を読み出してＦ１×Ｆ１を演算しこの演算結果をレジスタＦ３に格納する。このとき、Ｚｉ＝Ｙ０’Ｚ０、Ｆ３＝（Ｙ０’）２となっている。
【００６６】
ステップＳ３０６では、Ｘ０の値とレジスタＦ３の値を読み出してＸ０×Ｆ３を演算しこの演算結果をレジスタＦ５に格納する。また、レジスタＦ４の値を読み出してＦ４×Ｆ４を演算しこの演算結果をレジスタＦ１に格納する。このとき、Ｆ５＝Ｘ０×（Ｙ０’）２＝Ｓ０、Ｆ１＝Ｍ０２となっている。
【００６７】
ステップＳ３０７では、レジスタＦ５の値を読み出して２×Ｆ５を演算しこの演算結果をＸｉとして演算結果出力用レジスタ６に出力する。このとき、Ｘｉ＝２Ｓ０になっている。
【００６８】
ステップＳ３０８では、レジスタＦ１の値とＸｉの値を読み出してＦ１−Ｘｉを演算しこの演算結果をＸｉとして演算結果出力用レジスタ６に出力する。このとき、Ｘｉ＝Ｍ０２−２Ｓ０となっている。
【００６９】
ステップＳ３０９では、レジスタＦ３の値を読み出してＦ３×Ｆ３の演算を行いこの演算結果をレジスタＦ１に格納する。また、レジスタＦ５の値およびＸｉの値を読み出してＦ５−Ｘｉの演算を行いこの演算結果をレジスタＦ５に格納する。このとき、Ｆ１＝（Ｙ０’）４＝Ｔ０、Ｆ５＝Ｓ−Ｘｉとなっている。
【００７０】
ステップＳ３１０では、レジスタＦ５、Ｆ４の値を読み出してＦ５×Ｆ４の演算を行いこの演算結果をＹｉとして演算結果出力用レジスタ６に出力する。このとき、Ｙｉ＝Ｍ０（Ｓ０−Ｘｉ）となっている。
【００７１】
ステップＳ３１１では、Ｙｉの値を読み出して２×Ｙｉを演算しこの演算結果をＹｉとして演算結果出力用レジスタ６に出力する。このとき、Ｙｉ＝２Ｍ０（Ｓ０−Ｘｉ）となっている。
【００７２】
ステップＳ３１２では、Ｙｉの値およびレジスタＦ１の値を読み出してＹｉ−Ｆ１を演算しこの演算結果をＹｉとして演算結果出力用レジスタ６に出力する。このとき、Ｙｉ＝２Ｍ０（Ｓ０−Ｘｉ）−Ｔ０となっている。
【００７３】
ステップＳ３１３では、最終的に演算されたＸｉ，Ｙｉ，Ｚｉ，Ｆ１，Ｆ２を記憶手段２に出力する。このあと、メインルーチンに復帰する。
【００７４】
この点の２倍算ルーチンでは、連続する２倍算の初回において、Ｙ０’＝２Ｙ０およびＷ０＝ａＺ０４を演算し、これらに基づいて演算した結果、出力される（Ｘｉ，Ｙｉ，Ｚｉ）の値は、実際のヤコビヤン座標（Ｘ１，Ｙ１，Ｚ１）に対して（Ｘ１，２Ｙ１，Ｚ１）となっている。
【００７５】
ステップＳ２０４の点の２倍算ループルーチンについて、図５により説明する。この２倍算ループルーチンでは、実際のヤコビヤン座標を（Ｘｔ，Ｙｔ，Ｚｔ）とすると、（Ｘｔ，２Ｙｔ，Ｚｔ）を入力として（Ｘｔ＋１，２Ｙｔ＋１，Ｚｔ＋１）を演算してこれを出力としている。
【００７６】
ステップＳ４００では、記憶手段２に格納されている（Ｘｉ，Ｙｉ，Ｚｉ）およびレジスタＦ１（＝Ｔｉ−１）、Ｆ２（＝Ｗｉ−１）の値を入力として読み出す。
【００７７】
ステップＳ４０１では、Ｆ１×Ｆ２を演算しその演算結果をレジスタＦ２に格納する。また、Ｘｉ×Ｘｉを演算しその演算結果をレジスタＦ３に格納する。このとき、Ｆ２＝Ｗｉ、Ｆ３＝Ｘｉ２となっている。
【００７８】
ステップＳ４０２では、レジスタＦ３の値を読み出して２×Ｆ３を演算しこの演算結果をＦ５に格納する。ここでは、Ｆ４＝２Ｘｉ２となっている。
【００７９】
ステップＳ４０３では、レジスタＦ５、Ｆ３の値を読み出してＦ５＋Ｆ３を演算しこの演算結果をレジスタＦ５に格納する。このとき、Ｆ５＝３Ｘｉ２となっている。
【００８０】
ステップＳ４０４では、レジスタＦ２、Ｆ５の値を読み出してＦ２＋Ｆ５を演算しこの演算結果をレジスタＦ５に格納する。このとき、Ｆ５＝３Ｘｉ２＋Ｗｉ＝Ｍｉとなっている。
【００８１】
ステップＳ４０５では、Ｙｉ，Ｚｉの値を読み出してＹｉ×Ｚｉを演算しこの演算結果をＺｉとして演算結果出力用レジスタ６に出力する。また、Ｙｉ×Ｙｉを演算しこの演算結果をレジスタＦ４に格納する。ここでは、入力されるＸｉ，Ｙｉ，Ｚｉに対してＺｉ＋１を演算してＺｉとして出力しており、演算としてはＺｉ＋１＝Ｙｉ’Ｚｉを実行したこととなる。また、レジスタＦ４に格納される値は、Ｆ４＝（Ｙｉ’）２となっている。
【００８２】
ステップＳ４０６では、Ｘｉの値とレジスタＦ４の値を読み出してＸｉ×Ｆ４を演算しこの演算結果をレジスタＦ３に格納する。また、レジスタＦ５の値を読み出してＦ５×Ｆ５を演算しこの演算結果をレジスタＦ１に格納する。このとき、Ｆ３＝Ｘｉ×（Ｙｉ’）２＝Ｓｉ、Ｆ１＝Ｍｉ２となっている。
【００８３】
ステップＳ４０７では、レジスタＦ３の値を読み出して２×Ｆ３を演算しこの演算結果をＸｉとして演算結果出力用レジスタ６に出力する。ここでは、入力されるＸｉ，Ｙｉ，Ｚｉに対してＸｉ＋１を演算してＸｉとして出力しており、演算としてはＸｉ＋１＝２Ｓｉを実行したこととなる。
【００８４】
ステップＳ４０８では、レジスタＦ１の値とＸｉの値を読み出してＦ１−Ｘｉを演算しこの演算結果をＸｉとして演算結果出力用レジスタ６に出力する。このとき、Ｘｉ＋１＝Ｍｉ２−２Ｓｉを演算したこととなる。
【００８５】
ステップＳ４０９では、レジスタＦ４の値を読み出してＦ４×Ｆ４の演算を行いこの演算結果をレジスタＦ１に格納する。また、レジスタＦ３の値およびＸｉの値を読み出してＦ３−Ｘｉの演算を行いこの演算結果をレジスタＦ３に格納する。このとき、Ｆ１＝（Ｙｉ’）４＝Ｔｉ、Ｆ３＝Ｓｉ−Ｘｉとなっている。
【００８６】
ステップＳ４１０では、レジスタＦ５、Ｆ３の値を読み出してＦ５×Ｆ３の演算を行いこの演算結果をＹｉとして演算結果出力用レジスタ６に出力する。ここでは、入力されるＸｉ，Ｙｉ，Ｚｉに対してＹｉ＋１を演算してＹｉとして出力しており、演算としてはＹｉ＋１＝Ｍｉ（Ｓｉ−Ｘｉ＋１）を実行したこととなる。
【００８７】
ステップＳ４１１では、Ｙｉの値を読み出して２×Ｙｉを演算しこの演算結果をＹｉとして演算結果出力用レジスタ６に出力する。このとき、Ｙｉ＋１＝２Ｍｉ（Ｓｉ−Ｘｉ＋１）を演算したこととなる。
【００８８】
ステップＳ４１２では、Ｙｉの値およびレジスタＦ１の値を読み出してＹｉ−Ｆ１を演算しこの演算結果をＹｉとして演算結果出力用レジスタ６に出力する。このとき、Ｙｉ＋１＝２Ｍｉ（Ｓｉ−Ｘｉ＋１）−Ｔｉを演算したこととなる。
【００８９】
ステップＳ４１３では、最終的に演算されたＸｉ，Ｙｉ，Ｚｉ，Ｆ１，Ｆ２を記憶手段２に出力する。このあと、メインルーチンに復帰する。
【００９０】
素体上楕円曲線上の点の演算に関して、その計算量を従来例による場合と本発明による場合とで比較したものを表２に示す。
【００９１】
【表２】
0003615405.tif 000004
【００９２】
点の２倍算の場合には、本発明の第１実施形態を採用することができる。この場合には、ＩＥＥＥ  Ｐ１３６３に記載されている従来例の場合と乗算回数は同じであるが、加算系の演算回数を１３回から９回に削減できる。
【００９３】
また、点の２ｍ倍算の場合には、本発明の第２実施形態を採用することができる。このとき、特願平１０−３１１３７９号に記載の従来例の場合と同様に乗算回数は８ｍ＋２となる。しかしながら、加算系の演算回数が従来例の場合、１４ｍ−１回であるのに対し、本発明の方法では８ｍ＋２回となり、大幅に計算量を削減することができる。
【００９４】
本発明の第２実施形態の方法を、ＤＳＰ（テキサスインスツルメンツ社製ＴＭＳ３２０Ｃ６ｘ）に実装したところ、特願平１０−３１１３７９号に記載の従来の方法に比して、楕円曲線上の任意点のスカラー倍算が６％高速化することがでい、この結果楕円曲線暗号を用いたＤＳＡ署名確認処理が従来法よりも５％高速化された。
【００９５】
【発明の効果】
本発明によれば、素体上楕円曲線上の点の演算において、加算系の演算処理を削減することができ、特に、２倍算処理が連続する場合に計算量を削減し、楕円曲線上の点のスカラー倍算を行った場合、演算の高速化を図ることが可能となる。
【図面の簡単な説明】
【図１】本発明の１実施形態の制御ブロック図。
【図２】第１実施形態の制御フローチャート。
【図３】第２実施形態の制御フローチャート。
【図４】２倍算ルーチンの制御フローチャート。
【図５】２倍算ループルーチンの制御フローチャート。
【符号の説明】
１  演算装置
２  記憶手段
３  演算部
４  演算手段
５  レジスタ群
６  演算結果出力用レジスタ
【図１】
0003615405.tif 000005
【図２】
0003615405.tif 000006
【図３】
0003615405.tif 000007
【図４】
0003615405.tif 000008
【図５】
0003615405.tif 000009