(57)【要約】【課題】標数２の場合において、ツイスト楕円曲線上のスカラー倍演算を高速化する。【解決手段】σ１をＦｑ２ｎ上の（ｘ，ｙ）∈Ｅｔから（ｘ，ｙ＋αｘ）∈Ｅへ移す写像とし、πｑをＦｑ上の（ｘ，ｙ）∈Ｅから（ｘｑ，ｙｑ）∈Ｅへ移すフロベニウス写像とし、σ２をＦｑ２ｎ上の（ｘ，ｙ）∈Ｅから（ｘ，ｙ＋αｘ）∈Ｅｔへ移す写像とし、πｑｔを、Ｆｑ２ｎ上の（ｘ，ｙ）∈Ｅｔを写像σ１によって移し、その像をフロベニウス写像πｑによって移し、さらにその像を写像σ２によって移す写像とする。そして、Ｆｑｎ上の有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの入力を受け付け、入力された有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの写像πｑｔによる像（πｑｔ）Ｐを算出する。そして、入力された有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔのｋ倍点であるｋＰのフロベニウス展開式（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐに、算出した像（πｑｔ）Ｐを代入し、ｋＰを算出する。【選択図】        図１
2004271792.tif 000002
【特許請求の範囲】
【請求項１】
Ｆｑを要素数ｑの有限体とし、ｑ＝２ｍとし、ｍを自然数とし、Ｆｑ上で定義された楕円曲線Ｅをｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂとし、この楕円曲線Ｅに対応してＦｑｎ上で定義されたツイスト楕円曲線Ｅｔをｙ２＋ｘｙ＝ｘ３＋（ａ＋ｃ）ｘ２＋ｂとし、ｎを自然数とし、ａ，ｂ∈Ｆｑとし、ｃをｃ∈ＦｑｎであってＦｑｎにおける非平方とした場合における、Ｆｑｎ上の有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの入力を受け付ける有理点入力手段と、
α∈Ｆｑ２ｎがα２＋α＋ｃ＝０を満たすものとし、σ１をＦｑ２ｎ上の（ｘ，ｙ）∈Ｅｔから（ｘ，ｙ＋αｘ）∈Ｅへ移す写像とし、πｑをＦｑ上の（ｘ，ｙ）∈Ｅから（ｘｑ，ｙｑ）∈Ｅへ移すフロベニウス写像とし、σ２をＦｑ２ｎ上の（ｘ，ｙ）∈Ｅから（ｘ，ｙ＋αｘ）∈Ｅｔへ移す写像とし、πｑｔを、Ｆｑ２ｎ上の（ｘ，ｙ）∈Ｅｔを写像σ１によって移し、その像をフロベニウス写像πｑによって移し、さらにその像を写像σ２によって移す写像とした場合における、前記有理点入力手段において入力された前記有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの写像πｑｔによる像（πｑｔ）Ｐを算出する自己準同写像演算手段と、
前記有理点入力手段において入力された前記有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔのｋ倍点であるｋＰのフロベニウス展開式（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐに、前記自己準同写像演算手段によって算出された前記像（πｑｔ）Ｐを代入し、ｋＰを算出するスカラー倍演算手段と、
を有することを特徴とする楕円曲線上スカラー倍演算装置。
【請求項２】
前記自己準同写像演算手段は、
【数１】
2004271792.tif 000013
の演算を行って定数ｅｍを算出する第１の定数演算手段と、
１≦ｊ≦ｍ−１を満たす全ての自然数ｊについて、前記第１の定数演算手段によって算出された定数ｅｍを用いて
【数２】
2004271792.tif 000014
の演算を行い、Ｆｑｎ上の有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの写像（πｑｔ）ｊによる像（πｑｔ）ｊＰを算出する写像演算手段と、
を有する手段であり、
前記スカラー倍演算手段は、
ｋＰのフロベニウス展開（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐの各定数ｄｉを、０≦ｉ≦ｍについて算出する第２の定数演算手段と、
前記第２の定数演算手段において算出された定数ｄｉと、前記写像演算手段において算出された前記像（πｑｔ）ｊＰとを用い、（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐの演算を行ってｋＰを算出する展開式演算手段と、
を有することを特徴とする請求項１記載の楕円曲線上スカラー倍演算装置。
【請求項３】
前記自己準同写像演算手段は、
前記写像演算手段による処理の前に、
【数３】
2004271792.tif 000015
の演算によって定数ｈを算出する第３の定数演算手段をさらに有し、
前記写像演算手段は、
前記第３の定数演算手段によって算出された定数ｈを用いて
【数４】
2004271792.tif 000016
の演算を行い、前記像（πｑｔ）ｊＰを算出する手段であること、
を特徴とする請求項２記載の楕円曲線上スカラー倍演算装置。
【請求項４】
前記第２の定数演算手段は、
Ｒを前記ツイスト楕円曲線Ｅｔ上の任意の点とし、Ｏを無限遠点とした場合における（（πｑｔ）２−ｗ（πｑｔ）＋ｑ）Ｒ＝Ｏを満たすｗ、前記ｋ、及び前記要素数ｑの入力を受け付けるパラメータ入力手段と、
変数ｚ１に前記ｋを代入し、変数ｉ１、変数ｚ２、及びすべてのｉ２の変数ｄｉ２に０を代入する変数初期化手段と、
ｍ≦ｉ１≦２ｍ−１を満たした場合、変数ｚ３に（ｘ  ｍｏｄ  ｑ）−ｑの演算結果を代入し、ｎを（（πｑｔ）ｎ＋１）Ｒ＝Ｏを満たす自然数とした場合における、ｄ（ｉ１  ｍｏｄ  ｎ）にｄ（ｉ１  ｍｏｄ  ｎ）−ｚ３の演算結果を代入し、ｍ≦ｉ１≦２ｍ−１を満たさなかった場合、変数ｚ３に（ｘ  ｍｏｄ  ｑ）の演算結果を代入し、ｄ（ｉ１  ｍｏｄ  ｎ）にｄ（ｉ１  ｍｏｄ  ｎ）＋ｚ３の演算結果を代入する第１の変数代入手段と、
変数ｚ４に（ｚ１−ｚ３）／ｑを代入し、変数ｚ１にｗｚ４＋ｚ２を代入し、ｚ２に−ｚ４を代入し、ｉ１にｉ１＋１を代入する第２の変数代入手段と、
ｚ１＝ｚ２となった場合に、各ｄｉ１の値を前記定数ｄｉとして出力する定数出力手段と、
を有することを特徴とする請求項２又は３の何れかに記載の楕円曲線上スカラー倍演算装置。
【請求項５】
請求項１から４何れかに記載された楕円曲線上スカラー倍演算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、楕円曲線上でのスカラー倍演算を行う楕円曲線上スカラー倍演算装置、及びその機能をコンピュータ上で実行させる楕円曲線上スカラー倍演算プログラムに関し、特に、標数２の有限体におけるツイスト楕円曲線上でのスカラー倍演算を行う楕円曲線上スカラー倍演算装置、及びその機能をコンピュータ上で実行させる楕円曲線上スカラー倍演算プログラムに関する。
【０００２】
【従来の技術】
情報通信ネットワークの進展が進む昨今、電子情報の秘匿や認証に必要な暗号技術は不可欠な要素である。そして、この暗号技術の安全性と高速化の向上が今後の重大な課題となっている。
そのような中、電子商取引の時代を担う次世代暗号として楕円曲線暗号が注目を集めている。楕円曲線暗号は、楕円曲線上の離散対数問題の求解困難性を根拠に安全性を確保する暗号方式の一種であり、素因数分解の困難性を安全性の根拠にするＲＳＡ暗号等と比べ、遥かに短い鍵長で同等の安全性強度を実現することができるものである。
しかし、この楕円曲線暗号も、処理能力が制限されるスマートカードや、大量の暗号処理が行われるサーバ装置等においては、処理速度や安全性の面で課題があり、その高速化・安全性の研究が世界中で展開されている。
【０００３】
一般に、楕円曲線暗号を実現する場合、その処理時間のほとんどは楕円曲線上のスカラー倍演算に費やされる。すなわち、楕円曲線暗号に用いられる「楕円曲線上の離散対数問題」とは、楕円曲線上の点Ｐとそのスカラー倍の点ｋＰが与えられた時、スカラー値ｋを求める問題をいい、「楕円曲線上の点」とは、楕円曲線の定義方程式をみたす数の組をいうが、この楕円曲線上の離散対数問題生成時に行われるスカラー倍演算ｋＰを高速化することが、楕円曲線暗号の高速化を実現することとなる。
通常、スカラー倍演算ｋＰは、楕円曲線上の加法や２倍算を繰り返すことによって行われる。ここで、「楕円曲線上の加法」とは、楕円曲線上の点全体で定義された、無限遠点を単位元とした加法演算をいい、「楕円曲線上の２倍算」とは、同じ点同士の楕円曲線上の加法をいう。そして、この楕円曲線上の２点の加法は、これら２点を通る直線が再び楕円曲線と交わる他の点と、ｘ軸に関して対称な点を加法結果の点とする演算であり、楕円曲線上の点の２倍算は、この点の楕円曲線上の接線が再び楕円曲線と交わる他の点と、ｘ軸に関して対称な点を２倍算結果の点とする演算である。
【０００４】
また、スカラー倍演算ｋＰを高速演算する方法として、フロベニウス（Ｆｒｏｂｅｎｉｕｓ）写像を用いる方法がある。ここで、「フロベニウス写像」とは、要素数ｑの有限体Ｆｑ上で定義された楕円曲線上の点Ｐ＝（ｘ，ｙ）に対する自己準同型写像（（ｘ，ｙ）  →  （ｘｑ，ｙｑ））をいう。そして、このフロベニウス写像をπｑとすると、（πｑ２−ｗπｑ＋ｑ）Ｐ＝Ｏ  （−２√ｑ≦ｗ≦２√ｑ）を満たすことが知られており、この場合、スカラー倍演算ｋＰは、ｋＰ＝（ｄ０＋ｄ１πｑ＋…＋ｄｍ（πｑ）ｍ−１）Ｐと展開（フロベニウス展開）できることが知られている（非特許文献１参照。）。なお、Ｏは無限遠点を示す。この場合、スカラー倍演算ｋＰの演算は、展開式（ｄ０＋ｄ１πｑ＋…＋ｄｍ（πｑ）ｍ−１）Ｐの各要素の置き換えのみによって行うことができ、楕円曲線上の加法や２倍算によって演算を行う場合に比べ、一般に処理を高速化することができる。
また、非特許文献２では、標数５以上の場合において、Ｆｑｎ上で定義された有理点の数が素数となる楕円曲線上で、高速演算可能な自己準同型の写像を求め、ツイスト楕円曲線上でのスカラー倍算に、このフロベニウス展開を用いる方法が開示されている。以下に、その内容を概説する。なお、「標数」とは、有限体Ｆｑの要素数ｑがｑ＝βｍと表される場合におけるβの値をいい、一般にその数は素数である。
【０００５】
この非特許文献２の場合、Ｆｑ上で楕円曲線Ｅ：ｙ２＝ｘ３＋ａｘ＋ｂが定義され、Ｆｑｎ上でツイスト楕円曲線Ｅｔ：ｙ２＝ｘ３＋ａｃ２ｘ＋ｂｃ３が定義されている（ａ，ｂ∈Ｆｑ、ｃ∈ＦｑｎはＦｑｎで非平方）。ここで、「ツイスト楕円曲線」とは、Ｆｑｎ上では楕円曲線Ｅと非同型であるが、Ｆｑ２ｎ上では楕円曲線Ｅと同型となる曲線をいい、各楕円曲線Ｅにそれぞれ対応する関係にあるものである。
そして、写像πｑｔを、
【数５】
2004271792.tif 000003
のように定義し、この定義より、ツイスト楕円曲線Ｅｔ上の点Ｐ（ｘ，ｙ）∈Ｆｑｎの写像πｑｔによる像は、Ｐπｑｔ＝（ｃ１−ｑｘｑ，ｃ３（１−ｑ）／２ｙｑ）となる。ここで、σ１はＦｑ２ｎ上で同型となるツイスト楕円曲線Ｅｔから楕円曲線ＥへのＦｑ２ｎ上での写像であり、フロベニウス写像πｑは、楕円曲線Ｅ上での自己準同型の写像であり、σ２はＦｑ２ｎ上で同型となる楕円曲線Ｅからツイスト楕円曲線ＥｔへのＦｑ２ｎ上での写像である。従って、この写像πｑｔは、ツイスト楕円曲線Ｅｔ上の点をツイスト楕円曲線Ｅｔ上に写す自己準同型の写像である。なお、Ｅ（Ｆｑ２ｎ）、Ｅｔ（Ｆｑ２ｎ）は、Ｆｑ２ｎ上で定義された楕円曲線Ｅ、ツイスト楕円曲線Ｅｔをそれぞれ示す。
また、この写像πｑｔは、（（πｑｔ）２−ｗπｑｔ＋ｑ）Ｒ＝Ｏ  （−２√ｑ≦ｗ≦２√ｑ）を満たすため、ツイスト楕円曲線Ｅｔ上のスカラー倍演算ｋＰは、ｋＰ＝（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑ）ｍ−１）Ｐとフロベニウス展開でき（非特許文献１参照。）、前述のような高速演算が可能となる。なお、Ｒはツイスト楕円曲線Ｅｔ上の任意の点を意味する。
【０００６】
【非特許文献１】
Ｊ．Ａ．Ｓｏｌｉｎａｓ，  ”Ａｎ  Ｉｍｐｒｏｖｅｄ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ａｒｉｔｈｍｅｔｉｃ  ｏｎ  ａ  Ｆａｍｉｌｙ  ｏｆ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ”，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ’９７，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  １２９４，  ｐｐ．３５７−３７１，  Ｓｐｒｉｎｇｅｒ，  １９９７．
【非特許文献２】
Ｔ．Ｉｉｊｉｍａ，  Ｋ．Ｍａｔｓｕｏ，  Ｊ．Ｃｈａｏ，  Ｓ．Ｔｓｕｊｉｉ，  ”Ｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  Ｆｒｏｂｅｎｉｕｓ  ｍａｐｓ  ｏｆ  ｔｗｉｓｔｓ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ  ａｎｄ  ｉｔｓ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｅｌｌｉｐｔｉｃ  ｓｃａｌａｒ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ”，  ｓｃｉｓ２００２．
【０００７】
【発明が解決しようとする課題】
しかし、非特許文献２の方法は、標数５以上であることを前提としており、標数２の場合に適用できないという問題点がある。
つまり、非特許文献２の方法は、標数５以上であることを前提に定義されたツイスト楕円曲線上でのスカラー倍演算の高速化を目的としたものであり、この方法を標数２であることを前提に定義されたツイスト楕円曲線上でのスカラー倍演算に適用することはできない。そのため、非特許文献２の方法を、２進数としての取扱いが必要なワイヤードロジック等によって直接的に実現することはできない。
この発明はこのような点に鑑みてなされたものであり、標数２の場合において、ツイスト楕円曲線上のスカラー倍演算を高速化することが可能な楕円曲線上スカラー倍演算装置を提供することを目的とする。
また、この発明の他の目的は、標数２の場合において、ツイスト楕円曲線上のスカラー倍演算を高速化する機能をコンピュータ上で実行させるための楕円曲線上スカラー倍演算プログラムを提供することである。
【０００８】
【課題を解決するための手段】
この発明では上記課題を解決するために、まず、有理点入力手段において、Ｆｑｎ上の有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの入力を受け付ける。なお、ここでは、Ｆｑを要素数ｑの有限体とし、ｑ＝２ｍとし、ｍを自然数とし、Ｆｑ上で定義された楕円曲線Ｅをｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂとし、この楕円曲線Ｅに対応してＦｑｎ上で定義されたツイスト楕円曲線Ｅｔをｙ２＋ｘｙ＝ｘ３＋（ａ＋ｃ）ｘ２＋ｂとし、ｎを自然数とし、ａ，ｂ∈Ｆｑとし、ｃをｃ∈ＦｑｎであってＦｑｎにおける非平方としている。
次に、自己準同写像演算手段において、有理点入力手段において入力された有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの写像πｑｔによる像（πｑｔ）Ｐを算出する。なお、ここでは、α∈Ｆｑ２ｎがα２＋α＋ｃ＝０を満たすものとし、σ１をＦｑ２ｎ上の（ｘ，ｙ）∈Ｅｔから（ｘ，ｙ＋αｘ）∈Ｅへ移す写像とし、πｑをＦｑ上の（ｘ，ｙ）∈Ｅから（ｘｑ，ｙｑ）∈Ｅへ移すフロベニウス写像とし、σ２をＦｑ２ｎ上の（ｘ，ｙ）∈Ｅから（ｘ，ｙ＋αｘ）∈Ｅｔへ移す写像とし、πｑｔを、Ｆｑ２ｎ上の（ｘ，ｙ）∈Ｅｔを写像σ１によって移し、その像をフロベニウス写像πｑによって移し、さらにその像を写像σ２によって移す写像としている。
そして、有理点入力手段において入力された有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔのｋ倍点であるｋＰのフロベニウス展開式（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐに、自己準同写像演算手段によって算出された像（πｑｔ）Ｐを代入し、ｋＰを算出する。
【０００９】
ここで、σ１はＦｑ２ｎ上で同型となるツイスト楕円曲線Ｅｔから楕円曲線ＥへのＦｑ２ｎ上での写像であり、フロベニウス写像πｑは、楕円曲線Ｅ上での自己準同型の写像であり、σ２はＦｑ２ｎ上で同型となる楕円曲線Ｅからツイスト楕円曲線ＥｔへのＦｑ２ｎ上での写像である。従って、この写像πｑｔは、ツイスト楕円曲線Ｅｔ上の点をツイスト楕円曲線Ｅｔ上に写す自己準同型の写像である。
また、この写像πｑｔは、（（πｑｔ）２−ｗπｑｔ＋ｑ）Ｒ＝Ｏ  （−２√ｑ≦ｗ≦２√ｑ）を満たすため、ツイスト楕円曲線Ｅｔ上のスカラー倍演算ｋＰは、この写像πｑｔを用い、ｋＰ＝（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑ）ｍ−１）Ｐとフロベニウス展開できる（非特許文献１参照。）。なお、Ｒはツイスト楕円曲線Ｅｔ上の任意の点を意味し、Ｏは無限遠点を意味する。
従って、このスカラー倍演算ｋＰの演算は、展開式（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑ）ｍ−１）Ｐの各要素の置き換えのみによって行うことができ、楕円曲線上の加法や２倍算によって演算を行う場合に比べ、一般に処理を高速化することができる。
【００１０】
【発明の実施の形態】
以下、この発明の実施の形態を図面を参照して説明する。
なお、以下では、まず、この形態の全体について説明し、その後、その詳細について説明を行っていく。
図１は、公知のコンピュータに所定のプログラムが実行されることによって構成される、楕円曲線上スカラー倍演算装置１の全体構成を例示した機能ブロック図である。以下、この図に沿って、楕円曲線上スカラー倍演算装置１の全体構成及び処理動作を説明する。なお、以下の説明では、Ｆｑは要素数ｑの有限体を表すものとし、この例では、標数２の場合を取り上げるためｑ＝２ｍとする（ｍは自然数）。また、標数２においてＦｑ上で定義された楕円曲線Ｅをｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂとし、この楕円曲線Ｅに対応してＦｑｎ上で定義されたツイスト楕円曲線Ｅｔをｙ２＋ｘｙ＝ｘ３＋（ａ＋ｃ）ｘ２＋ｂとする（ｎは自然数、ａ，ｂ∈Ｆｑ、ｃはｃ∈ＦｑｎであってＦｑｎにおける非平方の数）。さらに、α∈Ｆｑ２ｎはα２＋α＋ｃ＝０を満たすものとし、ｋはスカラー値を表すものとし、Ｅ（Ｆｑ）、Ｅｔ（Ｆｑ）は、Ｆｑ上で定義された楕円曲線Ｅ、ツイスト楕円曲線Ｅｔをそれぞれ示すものとする。
【００１１】
楕円曲線上スカラー倍演算装置１によってスカラー倍演算を行う場合、まず、有理点入力部１０によって、Ｆｑｎ上の有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの入力を受け付け、入力された有理点Ｐ（ｘｐ，ｙｐ）を自己準同写像演算部２０に送る。
有理点Ｐ（ｘｐ，ｙｐ）が送られた自己準同写像演算部２０は、この有理点Ｐ（ｘｐ，ｙｐ）の以下の写像πｑｔによる像（πｑｔ）Ｐを算出する。
【数６】
2004271792.tif 000004
ここで、写像πｑｔは、Ｆｑ２ｎ上の（ｘ，ｙ）∈Ｅｔを写像σ１によって移し、その像をフロベニウス写像πｑによって移し、さらにその像を写像σ２によって移す写像である。また、σ１は、Ｆｑ２ｎ上の（ｘ，ｙ）∈Ｅｔを（ｘ，ｙ＋αｘ）∈Ｅへ移す写像であり、πｑは、Ｆｑ上の（ｘ，ｙ）∈Ｅを（ｘｑ，ｙｑ）∈Ｅへ移すフロベニウス写像であり、σ２は、Ｆｑ２ｎ上の（ｘ，ｙ）∈Ｅを（ｘ，ｙ＋αｘ）∈Ｅｔへ移す写像である。そして、σ１はＦｑ２ｎ上で同型となるツイスト楕円曲線Ｅｔから楕円曲線ＥへのＦｑ２ｎ上での写像であり、フロベニウス写像πｑは、楕円曲線Ｅ上での自己準同型の写像であり、σ２はＦｑ２ｎ上で同型となる楕円曲線Ｅからツイスト楕円曲線ＥｔへのＦｑ２ｎ上での写像である。従って、この写像πｑｔは、ツイスト楕円曲線Ｅｔ上の点をツイスト楕円曲線Ｅｔ上に写す自己準同型の写像である。
【００１２】
この写像πｑｔにおける有理点Ｐ（ｘｐ，ｙｐ）の像（πｑｔ）Ｐを求めるために、まず、有理点Ｐ（ｘｐ，ｙｐ）の写像σ１による像を求めると、（ｘｐ，ｙｐ＋αｘｐ）となる。そして、そのフロベニウス写像πｑによる像は（（ｘｐ）ｑ，（ｙｐ）ｑ＋αｑ（ｘｐ）ｑ）となり、さらにその写像σ２による像は（（ｘｐ）ｑ，（ｙｐ）ｑ＋（αｑ＋α）・（ｘｐ）ｑ）となる。
ここで、ｑ＝２ｍであるため、ｅｍ＝αｑ＋αおくと、ｅｍは
【数７】
2004271792.tif 000005
のように変換できる。そして、このｅｍを用い、像（πｑｔ）Ｐ＝（（ｘｐ）ｑ，（ｙｐ）ｑ＋ｅｍ・（ｘｐ）ｑ）…（１）と表すことができる。
また、有理点Ｐ（ｘｐ，ｙｐ）に写像πｑｔをｊ回適用すると、その像（πｑｔ）ｊＰは、
【数８】
2004271792.tif 000006
となる。以下に、その証明を示す。
【００１３】
ｊ＝１のときは、その代入結果は（πｑｔ）Ｐ＝（（ｘｐ）ｑ，（ｙｐ）ｑ＋ｅｍ・（ｘｐ）ｑ）となるため、成立することは自明である。また、ｊ＝Ｌで成立すると仮定すると
【数９】
2004271792.tif 000007
が成立し、式（１）より
【数１０】
2004271792.tif 000008
が成立する。これによりｊ＝Ｌ＋１でも成立することがいえるため、全ての自然数ｊについて成立することがいえる〔証明終わり〕。
自己準同写像演算部２０では、式（２）を用いて、１≦ｊ≦ｍ−１を満たす全ての自然数ｊについて像（πｑｔ）ｊＰを演算し、その結果をスカラー倍演算部３０に送る。
【００１４】
この演算結果を受け取ったスカラー倍演算部３０は、有理点入力部１０において入力された有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔのｋ倍点であるｋＰのフロベニウス展開式（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐに、自己準同写像演算部２０によって算出された像（πｑｔ）ｊＰを代入し、ｋＰを算出する。
すなわち、式（２）で表される像（πｑｔ）ｊＰは、（（πｑｔ）２−ｗπｑｔ＋ｑ）Ｒ＝Ｏ  （−２√ｑ≦ｗ≦２√ｑ）、及び  （（πｑｔ）ｎ＋１）Ｒ＝Ｏ  を満たすことになるが（Ｒ：ツイスト楕円曲線Ｅｔ上の任意の点、Ｏ：無限遠点）、この場合、非特許文献１に示したように、ツイスト楕円曲線Ｅｔ上のスカラー倍演算ｋＰは、ｋＰ＝（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑ）ｍ−１）Ｐとフロベニウス展開できる。そのため、自己準同写像演算部２０から受け取った（πｑｔ）ｊＰ  （１≦ｊ≦ｍ−１）の演算結果と、後述するアルゴリズムで求めた定数ｄｉ（０≦ｉ≦ｍ）とを用いてｄｉ（πｑｔ）ｉ−１Ｐ  （１≦ｊ≦ｍ）を計算し、それらを足し合わせることによりｋＰを高速に求めることができる。
【００１５】
次に、この形態の詳細について説明する。
図２の（ａ）は、この形態の楕円曲線上スカラー倍演算装置１のハードウェア構成を例示したブロック図である。
図２の（ａ）に例示するように、この例の楕円曲線上スカラー倍演算装置１は、キーボード等の入力装置１ａ、液晶ディスプレイ等の出力装置１ｂ、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１ｃ、ハードディスク等の記憶装置１ｄ、及び入力装置１ａ、出力装置１ｂ、ＣＰＵ１ｃ、記憶装置１ｄ間をデータのやり取りが可能なように接続するバス１ｅを有しており、記憶装置１ｄに記憶された所定のプログラムをＣＰＵ１ｃで実行することにより、その処理機能を実現する。
図２の（ｂ）は、図２の（ａ）に例示したハードウェア上で所定のプログラムを実行させることにより実現される自己準同写像演算部２０の機能構成の詳細を、図３は、スカラー倍演算部３０の機能構成の詳細を、それぞれ例示した図であり、図４は、楕円曲線上スカラー倍演算装置１の処理機能を説明するためのフローチャートである。以下、これらの図を用いて、楕円曲線上スカラー倍演算装置１の構成、及び処理機能の説明を行っていく。
【００１６】
楕円曲線上スカラー倍演算装置１においてスカラー倍演算を行う場合、まず、有理点入力部１０において、Ｆｑｎ上の有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの入力を受け付け、入力された有理点Ｐ（ｘｐ，ｙｐ）を自己準同写像演算部２０の写像演算部２４に送る（ステップＳ１）。
次に、自己準同写像演算部２０の定数演算部２２において、レジスタ２１からパラメータｃ，ｍを読み出す。なお、このパラメータｃは、ツイスト楕円曲線Ｅｔ（ｙ２＋ｘｙ＝ｘ３＋（ａ＋ｃ）ｘ２＋ｂ）の定数ｃであり、パラメータｍは、有限体Ｆｑの要素数ｑ＝２ｍを特定する自然数ｍであり、これらは予めレジスタ２１に格納されたデータである。パラメータｃ，ｍを読み出した定数演算部２２は、これらのパラメータｃ，ｍを
【数１１】
2004271792.tif 000009
に代入して定数ｅｍを算出し、算出した定数ｅｍを定数演算部２３に送る（ステップＳ２）。
【００１７】
定数ｅｍを受け取った定数演算部２３は、レジスタ２１からパラメータｑを読み出す。なお、このパラメータｑは、有限体Ｆｑの要素数ｑであり、予めレジスタ２１に格納されたデータである。パラメータｑを読み出した定数演算部２３は、受け取った定数ｅｍと、読み出したパラメータｑとを
【数１２】
2004271792.tif 000010
に代入して定数ｈを演算し、その演算結果である定数ｈを、パラメータｑとともに写像演算部２４に送る（ステップＳ３）。
写像演算部２４では、ステップＳ１で有理点入力部１０から送られた有理点Ｐ（ｘｐ，ｙｐ）と、ステップＳ３で定数演算部２３から送られた定数ｈ、及びパラメータｑを
【数１３】
2004271792.tif 000011
に代入して演算を行い、１≦ｊ≦ｍ−１を満たす全ての自然数ｊについて像（πｑｔ）ｊＰを算出する（ステップＳ４）。なお、この演算は、１≦ｊ≦ｍ−１を満たす全ての自然数ｊについて、定数演算部２２によって算出された定数ｅｍを用いて
【数１４】
2004271792.tif 000012
の演算を行い、Ｆｑｎ上の有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの写像（πｑｔ）ｊによる像（πｑｔ）ｊＰを算出することに該当する。また、写像演算部２４で算出された像（πｑｔ）ｊＰは、スカラー倍演算部３０の展開式演算部３１に送られる。
【００１８】
次に、スカラー倍演算部３０のパラメータ入力部３２ａにおいて、Ｒをツイスト楕円曲線Ｅｔ上の任意の点とし、Ｏを無限遠点とした場合における（（πｑｔ）２−ｗ（πｑｔ）＋ｑ）Ｒ＝Ｏを満たすｗ、スカラー値ｋ、要素数ｑの入力を受け付け、入力したこれらの情報をレジスタ３２ｂに格納する（ステップＳ５）。
その後、変数初期化部３２ｃにおいて、レジスタ３２ｂから、変数ｉ１，ｄｉ２，ｚ１，ｚ２、及び定数ｋを読み出し、変数ｚ１にｋを代入し、変数ｉ１、変数ｚ２、及びすべて変数ｄｉ２（∀ｉ２）に０を代入する（ステップＳ６）。なお、レジスタ３２ｂには、変数ｚ１，ｚ２，ｚ３，ｚ４，ｉ１，ｉ２，ｄｉ１、前述の定数ｑ，ｍ，ｋ，ｗ、有限体Ｆｑｎの要素数を特定し、（（πｑｔ）ｎ＋１）Ｒ＝Ｏを満たす自然数ｎが格納されているものとする。
次に、比較部３２ｄにおいて、レジスタ３２ｂから変数ｚ１，ｚ２を読み出し、読み出した変数がｚ１＝ｚ２となるか否かを判断し（ステップＳ７）、ｚ１，ｚ２となっていなかった場合、ステップＳ８の処理に進む。
【００１９】
ステップＳ８では、変数代入部３２ｅにおいて、まず、レジスタ３２ｂから定数ｑ，ｍ，ｄｉ１、及び変数ｉ１，ｚ１，ｚ３を読み出し、ｍ≦ｉ１≦２ｍ−１を満たすか否かを判断する。そして、ｍ≦ｉ１≦２ｍ−１を満たした場合、ｚ３に（ｚ１ｍｏｄ  ｑ）−ｑを、ｄ（ｉ１  ｍｏｄ  ｎ）にｄ（ｉ１  ｍｏｄ  ｎ）−ｚ３を代入し（ステップＳ９）、満たさなかった場合、ｚ３に（ｚ１ｍｏｄ  ｑ）を、ｄ（ｉ１  ｍｏｄ  ｎ）にｄ（ｉ１  ｍｏｄ  ｎ）＋ｚ３を代入する（ステップＳ１０）。
これらの代入結果ｚ３，ｄ（ｉ１  ｍｏｄ  ｎ）はレジスタ３２ｂに格納され、次に、変数代入部３２ｇにおいて、レジスタ３２ｂから定数ｑ，ｎ，ｗ、及び変数ｄｉ１，ｉ１，ｚ１，ｚ２，ｚ３，ｚ４を読み出し、変数ｚ４に（ｚ１−ｚ３）／ｑを代入し、変数ｚ１にｗｚ４＋ｚ２を代入し、ｚ２に−ｚ４を代入し、ｉ１にｉ１＋１を代入する（ステップＳ１１）。代入結果ｉ１，ｚ１，ｚ２，ｚ４は、レジスタ３２ｂに格納され、再び、ステップＳ７の処理に戻る。
【００２０】
ステップＳ７の処理において、比較部３２ｄがｚ１＝ｚ２であると判断した場合、比較部３２ｄは、その旨の情報を定数出力部３２ｈに送り、定数出力部３２ｈは、レジスタ３２ｂに格納されている変数ｄｉ１を読み出し、各ｄｉ１の値を定数ｄｉとして展開式演算部３１に出力する（ステップＳ１２）。なお、以上で説明したパラメータ入力部３２ａ、レジスタ３２ｂ、変数初期化部３２ｃ、比較部３２ｄ、変数代入部３２ｅ、３２ｇ、及び定数出力部３２ｈは、ｋＰのフロベニウス展開（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐの各定数ｄｉを０≦ｉ≦ｍについて算出する定数演算部３２を構成することになる。
定数演算部３２において算出され、出力された定数ｄｉ（ステップＳ５〜ステップＳ１２）と、自己準同像算出部２０の写像演算部２４において算出された像（πｑｔ）ｊＰ（ステップＳ４）とを受け取った展開式演算部３１は、これらのデータを用い、（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐの演算を行ってｋＰを算出し、その演算結果ｋＰを出力する（ステップＳ１３）。
【００２１】
このように、本形態では、有理点入力手段である有理点入力部１０において、Ｆｑｎ上の有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの入力を受け付け、自己準同写像演算手段である自己準同写像演算部２０において、α∈Ｆｑ２ｎがα２＋α＋ｃ＝０を満たすものとし、σ１をＦｑ２ｎ上の（ｘ，ｙ）∈Ｅｔから（ｘ，ｙ＋αｘ）∈Ｅへ移す写像とし、πｑをＦｑ上の（ｘ，ｙ）∈Ｅから（ｘｑ，ｙｑ）∈Ｅへ移すフロベニウス写像とし、σ２をＦｑ２ｎ上の（ｘ，ｙ）∈Ｅから（ｘ，ｙ＋αｘ）∈Ｅｔへ移す写像とし、πｑｔを、Ｆｑ２ｎ上の（ｘ，ｙ）∈Ｅｔを写像σ１によって移し、その像をフロベニウス写像πｑによって移し、さらにその像を写像σ２によって移す写像とした場合における、有理点入力部１０において入力された有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの写像πｑｔによる像（πｑｔ）Ｐを算出する。そして、スカラー倍演算手段であるスカラー倍演算部３０において、有理点入力部１０において入力された有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔのｋ倍点であるｋＰのフロベニウス展開式（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐに、自己準同写像演算部２０によって算出された像（πｑｔ）Ｐを代入し、ｋＰを算出することとした。
【００２２】
ここで、前述のように、この写像πｑｔは、ツイスト楕円曲線Ｅｔ上の点をツイスト楕円曲線Ｅｔ上に写す自己準同型の写像である。また、この写像πｑｔは、（（πｑｔ）２−ｗπｑｔ＋ｑ）Ｒ＝Ｏ  （−２√ｑ≦ｗ≦２√ｑ）を満たすため、ツイスト楕円曲線Ｅｔ上のスカラー倍演算ｋＰは、この写像πｑｔを用い、ｋＰ＝（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑ）ｍ−１）Ｐとフロベニウス展開できる。従って、この標数２におけるスカラー倍演算ｋＰの演算は、展開式（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑ）ｍ−１）Ｐの各要素の置き換えのみによって行うことができ、楕円曲線上の加法や２倍算によって演算を行う場合に比べ、一般に処理を高速化することができる。
【００２３】
また、この形態では、自己準同写像演算部２０は、式（３）の演算を行って定数ｅｍを算出する第１の定数演算手段である定数演算部２２、及び、１≦ｊ≦ｍ−１を満たす全ての自然数ｊについて、第１の定数演算部によって算出された定数ｅｍを用いて式（６）の演算を行い、Ｆｑｎ上の有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの写像（πｑｔ）ｊによる像（πｑｔ）ｊＰを算出する写像演算部２４を有することとした。さらに、スカラー倍演算部３０は、ｋＰのフロベニウス展開（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐの各定数ｄｉを、０≦ｉ≦ｍについて算出する第２の定数演算手段である定数演算部３２、及び、定数演算部３２において算出された定数ｄｉと、写像演算部において算出された像（πｑｔ）ｊＰとを用い、（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐの演算を行ってｋＰを算出する展開式演算手段である展開式演算部３１を有することとした。そのため、定数演算部３２において算出された定数ｄｉ、及び写像演算部において算出された像（πｑｔ）ｊＰを展開式（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑ）ｍ−１）Ｐへの各要素に代入するのみで、標数２におけるツイスト楕円曲線Ｅｔ上のスカラー倍ｋＰを高速に求めることができる。
【００２４】
さらに、自己準同写像演算部２０は、写像演算部２４による処理の前に、式（４）の演算によって定数ｈを算出する第３の定数演算手段である定数演算部２３を有し、写像演算部２４は、定数演算部２３によって算出された定数ｈを用いて式（５）の演算を行い、像（πｑｔ）ｊＰを算出することとした。この場合、式（５）に示すように、（πｑｔ）ｊ写像の演算コストは、Ｆｑｎ上のｑ乗の演算を２ｊ回（ｘｐｑをｊ回、ｙｐｑをｊ回）、乗算１回、加算１回のみである。そして、Ｆｑｎ上のｑ乗は一般に高速に演算できる。そのため、（πｑｔ）ｊ写像の演算コストは、楕円曲線上の加算等に比べると誤差の範囲となり、標数２におけるツイスト楕円曲線Ｅｔ上のスカラー倍ｋＰの演算をより高速に行うことが可能となる。
【００２５】
また、第２の定数演算部３２は、Ｒをツイスト楕円曲線Ｅｔ上の任意の点、Ｏを無限遠点とした場合における（（πｑｔ）２−ｗ（πｑｔ）＋ｑ）Ｒ＝Ｏを満たすｗ、前述したｋ及び要素数ｑの入力を受け付けるパラメータ入力手段であるパラメータ入力部３２ａ、変数ｚ１にｋを代入し、変数ｉ１、変数ｚ２、及びすべてのｉ２の変数ｄｉ２に０を代入する変数初期化手段である変数初期化部３２ｃ、ｍ≦ｉ１≦２ｍ−１を満たした場合、変数ｚ３に（ｘ  ｍｏｄ  ｑ）−ｑの演算結果を代入し、ｄ（ｉ１  ｍｏｄ  ｎ）にｄ（ｉ１  ｍｏｄ  ｎ）−ｚ３の演算結果を代入し、ｍ≦ｉ１≦２ｍ−１を満たさなかった場合、変数ｚ３に（ｘ  ｍｏｄ  ｑ）の演算結果を代入し、ｄ（ｉ１  ｍｏｄ  ｎ）にｄ（ｉ１  ｍｏｄ  ｎ）＋ｚ３の演算結果を代入する第１の変数代入手段である変数代入部３２ｅ、変数ｚ４に（ｚ１−ｚ３）／ｑを代入し、変数ｚ１にｗｚ４＋ｚ２を代入し、ｚ２に−ｚ４を代入し、ｉ１にｉ１＋１を代入する第２の変数代入手段である変数代入部３２ｇ、及びｚ１＝ｚ２となった場合に、各ｄｉ１の値を定数ｄｉとして出力する定数出力手段である定数出力部３２ｈを有することとした。そのため、これらを用いたステップＳ５〜Ｓ１３の処理により、ｋＰのフロベニウス展開（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐの各定数ｄｉを容易に求めることができ、標数２におけるツイスト楕円曲線Ｅｔ上のスカラー倍ｋＰを高速に求めることができる。
【００２６】
なお、この発明は上述の実施の形態に限定されるものではない。例えば、この形態では、ステップＳ３において式（４）を用いて定数ｈを算出し、その定数ｈを式（５）に代入することによって像（πｑｔ）ｊＰを算出したが（ステップＳ４）、定数ｈを求めず、式（３）と式（６）の演算のみで像（πｑｔ）ｊＰを算出することとしてもよい。
また、この実施の形態では、楕円曲線上スカラー倍演算装置の処理機能を、コンピュータに所定のプログラムを実行させることにより実現する構成としたが、これらの処理機能の少なくとも一部を電子回路によってハードウェア的に実現することとしてもよい。
また、上述の実施の形態で述べたように、上記の処理機能は、コンピュータによって実現することができる。この場合、楕円曲線上スカラー倍演算装置が有すべき機能の処理内容はプログラムによって記述され、このプログラムをコンピュータで実行することにより、上記処理機能をコンピュータ上で実現することができる。
【００２７】
また、この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、ＤＶＤ−ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＣＤ−Ｒ（Ｒｅｃｏｒｄａｂｌｅ）／ＲＷ（ＲｅＷｒｉｔａｂｌｅ）等を、光磁気記録媒体として、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｃ）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Ｅｌｅｃｔｒｏｎｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  ａｎｄ  Ｐｒｏｇｒａｍｍａｂｌｅ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）等を用いることができる。
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００２８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）型のサービスによって、上述の処理を実行する構成としてもよい。
なお、上記におけるプログラムとは、電子計算機に対する指令であって、一の結果を得ることができるように組合されたものをいい、その他電子計算機による処理の用に供する情報であってプログラムに準ずるものをも含むものとする。
【００２９】
【発明の効果】
以上説明したようにこの発明では、有理点入力部において、Ｆｑを要素数ｑの有限体とし、ｑ＝２ｍとし、ｍを自然数とし、Ｆｑ上で定義された楕円曲線Ｅをｙ２＋ｘｙ＝ｘ３＋ａｘ２＋ｂとし、この楕円曲線Ｅに対応してＦｑｎ上で定義されたツイスト楕円曲線Ｅｔをｙ２＋ｘｙ＝ｘ３＋（ａ＋ｃ）ｘ２＋ｂとし、ｎを自然数とし、ａ，ｂ∈Ｆｑとし、ｃをｃ∈ＦｑｎであってＦｑｎにおける非平方とした場合における、Ｆｑｎ上の有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの入力を受け付ける。次に、自己準同写像演算部において、α∈Ｆｑ２ｎがα２＋α＋ｃ＝０を満たすものとし、σ１をＦｑ２ｎ上の（ｘ，ｙ）∈Ｅｔから（ｘ，ｙ＋αｘ）∈Ｅへ移す写像とし、πｑをＦｑ上の（ｘ，ｙ）∈Ｅから（ｘｑ，ｙｑ）∈Ｅへ移すフロベニウス写像とし、σ２をＦｑ２ｎ上の（ｘ，ｙ）∈Ｅから（ｘ，ｙ＋αｘ）∈Ｅｔへ移す写像とし、πｑｔを、Ｆｑ２ｎ上の（ｘ，ｙ）∈Ｅｔを写像σ１によって移し、その像をフロベニウス写像πｑによって移し、さらにその像を写像σ２によって移す写像とした場合における、有理点入力部において入力された有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔの写像πｑｔによる像（πｑｔ）Ｐを算出する。そして、有理点入力部において入力された有理点Ｐ（ｘｐ，ｙｐ）∈Ｅｔのｋ倍点であるｋＰのフロベニウス展開式（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑｔ）ｍ−１）Ｐに、自己準同写像演算部によって算出された像（πｑｔ）Ｐを代入し、ｋＰを算出する。
【００３０】
ここで、写像πｑｔは、標数２の場合において、ツイスト楕円曲線Ｅｔ上の点をツイスト楕円曲線Ｅｔ上に写す自己準同型の写像であり、（（πｑｔ）２−ｗπｑｔ＋ｑ）Ｒ＝Ｏ  （−２√ｑ≦ｗ≦２√ｑ）を満たすものである。従って、標数２の場合におけるツイスト楕円曲線Ｅｔ上のスカラー倍演算ｋＰは、ｋＰ＝（ｄ０＋ｄ１πｑｔ＋…＋ｄｍ（πｑ）ｍ−１）Ｐとフロベニウス展開でき、この各要素の置き換えのみによって、このスカラー倍演算ｋＰを行うことができる。その結果、標数２の場合において、ツイスト楕円曲線上のスカラー倍演算を高速化することができる。
【図面の簡単な説明】
【図１】楕円曲線上スカラー倍演算装置の全体構成を例示した機能ブロック図。
【図２】（ａ）は、この形態の楕円曲線上スカラー倍演算装置１のハードウェア構成を例示したブロック図であり、（ｂ）は、自己準同写像演算部の機能構成の詳細を例示した図である。
【図３】スカラー倍演算部の機能構成の詳細を例示した図。
【図４】楕円曲線上スカラー倍演算装置の処理機能を説明するためのフローチャート。
【符号の説明】
１  楕円曲線上スカラー倍演算装置
１０  有理点入力部
２０  自己準同像算出部
３０  スカラー倍算出部
【図１】
2004271792.tif 000017
【図２】
2004271792.tif 000018
【図３】
2004271792.tif 000019
【図４】
2004271792.tif 000020