WO2006030496A2

WO2006030496A2 - 楕円曲線暗号演算装置、楕円曲線を用いた演算装置の演算方法および楕円曲線上の点のスカラー倍演算をコンピュータに実行させるプログラム

Info

Publication number: WO2006030496A2
Application number: PCT/JP2004/013409
Authority: WO
Inventors: Katsuyuki Takashima
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 2004-09-15
Filing date: 2004-09-15
Publication date: 2006-03-23
Anticipated expiration: 2007-03-15
Also published as: JPWO2006030496A1; US20070053506A1

Description

明細書

楕円曲線暗号演算装置、楕円曲線を用いた演算装置の演算方法および楕円曲線上の点のスカラー倍演算をコンピュータに実行させるプログラム

技術分野

[0001] この発明は、楕円曲線暗号のスカラー倍演算を行う楕円曲線暗号演算装置と、楕円曲線暗号演算装置での楕円曲線暗号のスカラー倍の演算方法と、楕円曲線暗号のスカラー倍演算をコンピュータに実行させるプログラムとに関する。

背景技術

[0002] 楕円曲線暗号の演算を高速に行うためには、その中で頻繁に実行されるスカラー倍演算を高速ィ匕することが必須となる。これまでに、様々なスカラー倍演算の高速ィ匕手法が提案されてきた。近年の研究によって、効率的に計算可能な自己準同型写像である特殊準同型写像 Φを用いて、スカラー倍数 Kを K = k +k φ (又は k +k え、 λは点群上で Φが与えるスカラー倍数)と表現し、スカラー倍数 κによるスカラー倍演算を、 kと kとのスカラー倍演算に分割することで演算速度を高速ィ匕する方法が開発

1 2

されている (非特許文献 1を参照)。このように特殊準同型写像を用いて高速ィ匕したスカラー倍演算を提案者の頭文字をとつて、 GLV型スカラー倍演算と呼ぶ。

[0003] また、非特許文献 2には超楕円曲線に上記の方法を拡張した場合の結果が示されて、る (非特許文献 2を参照)。

[0004] また、非特許文献 4には楕円曲線 Eの積 E X Eと種数 2超楕円曲線 Cのヤコビ多様体との間の準同型写像が記述されている (非特許文献 4を参照)。

非特許文献 1 :R. P. Gallant, J. L. Lambert and S. A. Vanstone, "Faster point multiplication on elliptic curves with efficient endomorphisms ，，， Crypto 2001, Springer Verlag, (2001) , 190—200.

非特許文献 2 : F. Sica, M. Ciet, J.—J. Quisquater, "Analysis of the Galla nt— Lambert— Vanstone method based on efficient endomorphisms ： e lliptic and hyperelliptic curves", SAC 2002, Springer Verlag, (2002) , 21-36. 非特許文献 3 : M. Ciet, T. Lange, F. Sica, J.—J. Quisquater, "Improved Al gorithms for Efficient Arithmetic on Elliptic Curves using Fast En domorphisms", EUROCRYPT 2003, Springer Verlag, (2003) , 388—40 0.

非特許文献 4: P. R. Bending, "Curves of genus 2 with f2 Multiplicati on", http： / / www. math. uiuc. eduZ Algebraic— Number— Theory/ 発明の開示

発明が解決しょうとする課題

[0005] 近年の高度情報通信技術の実用化に伴い、楕円曲線暗号を含む公開鍵暗号も既に実用化段階に入っている。そのため、クロック周波数の低い CPU (Central Proc essing Unit)しか搭載して!/ヽな、、ある!/、は CPUを搭載することができな!/、ICカード上での暗号演算の実行や、ュビキタス環境での情報セキュリティを確保するために、計算リソースが制限された環境での楕円曲線暗号の使用も必要なものとなってきている。その結果、楕円曲線暗号の演算速度の向上が切に望まれている。

[0006] し力しながら、上記した従来技術である GLV型スカラー倍演算が適用できる楕円曲線は特殊なものに限られていた。現在、楕円曲線暗号に用いる楕円曲線はランダムに選択するのが一般的であり、それにより、楕円曲線暗号の安全性が保証されている。そのため、上記した GLV型スカラー倍演算を用いて楕円曲線暗号の演算速度を高速化できても、楕円曲線をランダムに選択することができないため、上記 ICカード上での暗号演算実行や、ュビキタス環境において使用するには安全性が問題とされてきた。

[0007] そこで、より広、範囲の楕円曲線に、上記した従来技術である GLV型スカラー倍演算を適用することを可能にすることを目的とする。

課題を解決するための手段

[0008] 楕円曲線暗号演算装置は、楕円曲線 Eを示す情報と楕円曲線 E上の点 Pと演算値 Kとを入力して記憶部に記憶する入力部と、記憶部に記憶された楕円曲線 E上の点 Pを読み込んで、楕円曲線 E上の点 Pを、その楕円曲線 Eに対応する代数曲線のヤコビ多様体へ写像して楕円曲線 E上の点 Pに対応する代数曲線のヤコビ多様体上の点を埋め込み点 Dとして求め、埋め込み点 Dを記憶部に記憶する埋め込み演算部と、記憶部に記憶された埋め込み点 Dを読み込んで、代数曲線のヤコビ多様体の準同型写像による写像をして写像点 ε Dを求め、写像点 ε Dを記憶部に記憶する準同型写像演算部と、記憶部に記憶された写像点 ε Dを読み込んで、楕円曲線 Εへ写像して楕円曲線の射影点 P'を求め、射影点 P'を記憶部に記憶する射影演算部と、記憶部に記憶された演算値 Κと射影点 P'とを読み込んで、演算値 Κと射影点 P'とを用いて計算を行い、計算結果を記憶部に記憶する計算処理部とを備えることとした。発明の効果

[0009] 楕円曲線暗号演算装置は、楕円曲線 Εを示す情報と楕円曲線 Ε上の点 Ρと演算値 Κとを入力して記憶部に記憶する入力部と、記憶部に記憶された楕円曲線 Ε上の点 Ρを読み込んで、楕円曲線 Ε上の点 Ρを、その楕円曲線 Εに対応する代数曲線のヤコビ多様体へ写像して楕円曲線 Ε上の点 Ρに対応する代数曲線のヤコビ多様体上の点を埋め込み点 Dとして求め、埋め込み点 Dを記憶部に記憶する埋め込み演算部と、記憶部に記憶された埋め込み点 Dを読み込んで、代数曲線のヤコビ多様体の準同型写像による写像をして写像点 ε Dを求め、写像点 ε Dを記憶部に記憶する準同型写像演算部と、記憶部に記憶された写像点 ε Dを読み込んで、楕円曲線 Εへ写像して楕円曲線の射影点 P'を求め、射影点 P'を記憶部に記憶する射影演算部と、記憶部に記憶された演算値 Κと射影点 P'とを読み込んで、演算値 Κと射影点 P'とを用いて計算を行い、計算結果を記憶部に記憶する計算処理部とを備えることができる。発明を実施するための最良の形態

[0010] ここでは、楕円曲線暗号演算装置においてスカラー倍演算の高速化を実現する実施の形態について説明する。なお、この実施の形態では、代数曲線として種数 2超楕円曲線 Cを用い、準同型写像として効率的に演算可能な準同型写像である 2倍演算を用いた場合について説明する。

[0011] まず、公開鍵暗号、離散対数問題、楕円曲線暗号および超楕円曲線暗号について簡単に説明する。

公開鍵暗号を用いた通信にぉ、ては、利用者ごとに秘密鍵 Xと公開鍵 yの組が用意され、秘密鍵 Xは、各利用者が秘密に保持しておく。公開鍵 yは利用者自身以外の一般に公開する。利用者 Bが利用者 Aに秘密にデータを送りたい時は、利用者 B は利用者 Aの公開鍵 yを用いてデータを暗号ィ匕する。利用者 Aは、自分だけしか知らない秘密鍵 Xを用いて暗号ィ匕したデータを復号する。この暗号文は、秘密鍵 Xを知る利用者 Aにし力復号できな、。

[0012] 離散対数問題とは代数群 G (加法が定義されているものとする）の 2つの要素 g , g

1 2 に対して、 g =mgを満たすような mを求める問題である。代数群 Gの要素の数が大

1 2

きい場合、多くの離散対数問題を解くことは、計算量的に非常に困難になることが知られて、る。この事実を利用して公開鍵暗号を設計することができる。

[0013] 離散対数型公開鍵暗号は多ぐ代数群 Gを定める式と gを公開鍵暗号パラメータと

2

し、 gをその公開鍵、 mをその秘密鍵とする。

[0014] 有限体 GF (qⁿ) (qは素数 pのべき乗）上の種数 g超楕円曲線 Cとは、 y² + h(x)y=f

(X) (h (x) , f (x)はそれぞれ GF (qⁿ)係数の高々 g次および、 2g+ l次多項式、かつ、 f (x)は最高次の係数が 1)と表される方程式である。また、超楕円曲線 Cのヤコビ多様体 (ヤコビアン)の有理点集合には加法が定義され、群となる。特に、種数 gが 1の時の超楕円曲線を楕円曲線といい、その場合は、楕円曲線自体に加法が定義されている。これらの群を利用した公開鍵暗号を超楕円曲線暗号 (g= lの時は、楕円曲線暗号）という。

[0015] つまり、楕円曲線暗号の場合には、方程式 y²+h(x)y=f (X)の係数とその上の点（ xO, yO)が楕円曲線暗号パラメータとなり、楕円曲線上の加算に従って計算される (X 1, yl) ( (xl, yl)は、 (xl, yl) =m- (xO, yO)を満たす）がその公開鍵、 mがその秘密鍵となる。

[0016] また、種数 gの超楕円曲線暗号の場合は、方程式 y²+h (x)y=f )の係数がその暗号パラメータの一部であることは同様である力その他に、暗号パラメータとして、その曲線のヤコビアン上の点（その曲線上の因子類） D1が必要であり、ヤコビアン上の加算に従って計算される D2 (D2は、 D2=m'Dlを満たす）がその公開鍵、 mがその秘密鍵となる。

[0017] 楕円曲線上の点（xO, yO)のスカラー倍数 Kでのスカラー倍演算 Κ· (xO, yO)を計算する時に、スカラー倍数 Kの値が大きいと、計算に時間がかかってしまう。例えば、楕円曲線暗号の場合、スカラー倍数 Kに 2進数で 160ビットの値を用いる。ここで、 1 60ビットの各位のビット値を順に楕円曲線暗号パラメータに加算して、つた場合に、相当な時間を要することになる。

[0018] GLV型スカラー倍演算では、スカラー倍数 Kを K=k +k φ (又は k +k λ、は

1 2 1 2 点群上で φが与えるスカラー倍数)と表現し、スカラー倍数 Κによるスカラー倍演算を

、 kと kとのスカラー倍演算に分割することで、 kあるいは kのビット数の計算量で済

1 2 1 2

むことになる。

[0019] 例えば、楕円曲線暗号パラメータである楕円曲線上の点を Pとすれば、スカラー倍演算は、 KP=k - P+k · λ Ρとなる。予め、 P+ P = Sとすると、所定の位のビット

1 2

値が k = l、k =0であれば、 Pを用いた計算となり、 k =0、k = 1であれば、 λ Ρを

1 2 1 2

用いた計算となり、 k = 1、 k = 1であれば、 Sを用いた計算となり、 k =0、 k =0であ

1 2 1 2 れば、計算が不要となる。したがって、各位について、 Pまたは、 λ Ρまたは、 Sを用いた計算となり、し力も、 kあるいは kのビット数の計算量で済むことになる。例えば、ス

1 2

カラー Kが楕円曲線有理点群の位数 nと同等なビット数を有するとした場合、 kと kと

1 2 のビット数が概ね近くに小さくなる。すなわち、それだけ、演算回数が減り、演算速度を高速化させることができる。

[0020] 以上を踏まえた上で、この実施の形態における楕円曲線暗号演算装置の構成を図 1を用いて説明する。

楕円曲線暗号演算装置は、楕円曲線 Eを示す情報と楕円曲線 E上の点 Pと演算値 Kとを入力して記憶部 1に記憶する入力部 2と、記憶部 1に記憶された楕円曲線 E上の点 Pを読み込んで、楕円曲線 E上の点 Pを、その楕円曲線 Eに対応する代数曲線のヤコビ多様体へ写像して楕円曲線 E上の点 Pに対応する代数曲線のヤコビ多様体上の点を埋め込み点 Dとして求め、埋め込み点 Dを記憶部 1に記憶する埋め込み演算部 3と、記憶部 1に記憶された埋め込み点 Dを読み込んで、代数曲線のヤコビ多様体の準同型写像による写像をして写像点 _ε Dを求め、写像点 ε Dを記憶部 1に記憶する準同型写像演算部 4と、記憶部 1に記憶された写像点 ε Dを読み込んで、楕円曲線 Εへ写像して楕円曲線の射影点 P'を求め、射影点 P'を記憶部 1に記憶する射影演算部 5と、記憶部 1に記憶された演算値 Κと射影点 P'とを読み込んで、演算値 Κ と射影点 P'とを用いて計算を行い、計算結果を記憶部 1に記憶する計算処理部 6とを備える。

[0021] また、楕円曲線暗号演算装置は、さらに、代数曲線を選択して記憶部 1に設定するとともに、楕円曲線 E上の点 Pを、代数曲線のヤコビ多様体へ写像するためのパラメータを記憶部 1に設定する初期設定部 7を備える。また、楕円曲線暗号演算装置は、スカラー倍演算した結果を出力する出力部 8とスカラー倍演算を制御する CPU (Cen tral Processing UnitJ 9とを備; ^る。

[0022] ここで、演算値 Kはスカラー倍数 Kのことである。以後、同様にスカラー倍数 Kを演算値 Kと記載することもある。また、ここでは代数曲線には種数 2超楕円曲線を用いる。この楕円曲線暗号演算装置では、入力部 2から入力したスカラー倍数 Kのスカラー倍演算を行う。その際、種数 2超楕円曲線 Cのヤコビ多様体上の演算を利用する。また、楕円曲線暗号演算装置の準同型写像演算部 4では、種数 2超楕円曲線 Cのヤコビ多様体の点を 2倍する演算を行う。

[0023] 記憶部 1は、楕円曲線暗号演算装置がスカラー倍演算を行う過程で利用する各値を記憶する。

[0024] 入力部 2は、楕円曲線 Eの式とその式を規定するパラメータとを入力する。また、楕円曲線 E上の点 P (z、 t)とスカラー倍数 Kとを入力する。

[0025] 入力部 2からは、楕円曲線 Εを示す情報として 2捩れ点を有する楕円曲線を示す情報を入力するか、または、楕円曲線 Εを示す情報として位数が素数になっている位数素数の楕円曲線を示す情報を入力することができる。

[0026] しかし、ここでは入力する楕円曲線 Εの式とその式を規定するパラメータを以下のように定める。

楕円曲線 Εは、位数 2の有理点を含む楕円曲線を（1)式で示される楕円曲線 (非特許文献 4を参照）に変換することにより定められる。

[0027] [数 1] _{( 1 )}

[0028] ここで、丁と aと Uとは楕円曲線を規定するパラメータである。

[0029] (1)式で示される楕円曲線は、 2捩れ点 (一 1, 0)を任意の素体に対して有するものである。

[0030] 位数 2の有理点を含む楕円曲線は、有限体 GF (q)の要素 δ、 a、 bによって決まる楕円曲線 T²= (Ζ- δ ) (Z² + aZ + b)について、 s= (7 δ ² + 3a δ— a² + 3b) / ( δ ² + a δ +b)としたときに決まる新しい楕円曲線 T² = Z³ + sZ² + sZ+ lである。

[0031] この新しぃ楕円曲線丁²=2³+ 32²+ 32+ 1と、（1)式とがー致するように U、 α、 Δ 、 Wの値を定める。この U、 α、 Δ、 Wが楕円曲線 Εのパラメータであり、これらの値で定まる（1)式が楕円曲線暗号演算装置で用いる楕円曲線 Εとなる。よって、入力部 2 から、楕円曲線の式である（1)式と（1)式のパラメータである U、 _α、 A、Wとを楕円曲線 Eを示す情報として入力する。

[0032] 初期設定部 7は、代数曲線として、超楕円曲線を選択することができ、例えば、楕円曲線暗号演算装置の初期設定部 7は、代数曲線として、種数 2超楕円曲線 Cを選択することができる。

[0033] ここでは、初期設定部 7は、代数曲線として種数 2超楕円曲線 Cを選択するものとする。

[0034] 埋め込み演算部 3は、楕円曲線 E力種数 2超楕円曲線 Cのヤコビ多様体への埋め込みを行う。具体的には、楕円曲線 E上の点 Pを、その楕円曲線 Eに対応する種数 2超楕円曲線 Cのヤコビ多様体へ写像して、楕円曲線 E上の点 Pに対応する種数 2超楕円曲線 Cのヤコビ多様体上の点を埋め込み点 Dとして求める。

[0035] 準同型写像演算部 4は、埋め込み点 Dから種数 2超楕円曲線 Cのヤコビ多様体の準同型写像による写像をして写像点 ε Dを求める。

[0036] 射影演算部 5は、種数 2超楕円曲線 Cのヤコビ多様体力楕円曲線への写像を行う。具体的には、写像点 ε Dを楕円曲線 Εへ写像して楕円曲線の射影点 P'を求める。

[0037] 計算処理部 6は、スカラー倍数 Κと射影点 P'とから GLV型スカラー倍演算を用いてスカラー倍演算を行う。

[0038] 次に、楕円曲線暗号演算装置でスカラー倍演算を行う動作について説明する。

楕円曲線を用いた演算装置の演算方法は、楕円曲線 Εを示す情報と楕円曲線 Ε上の点 Ρと演算値 Κとを入力して記憶部 1に記憶し、記憶部 1に記憶された楕円曲線 Ε 上の点 Ρを読み込んで、楕円曲線 Ε上の点 Ρを、その楕円曲線 Εに対応する代数曲線のヤコビ多様体へ写像して楕円曲線 Ε上の点 Ρに対応する代数曲線のヤコビ多様体上の点を埋め込み点 Dとして求め、埋め込み点 Dを記憶部 1に記憶し、記憶部 1に記憶された埋め込み点 Dを読み込んで、代数曲線のヤコビ多様体の準同型写像による写像をして写像点 ε Dを求め、写像点 ε Dを記憶部 1に記憶し、記憶部 1に記憶された写像点 ε Dを読み込んで、楕円曲線 Εへ写像して楕円曲線 Ε上の射影点 P'を求め、射影点 Ρ 'を記憶部 1に記憶し、記憶部 1に記憶された演算値 Κと射影点 Ρ 'とを読み込んで、演算値 Κと射影点 P'とを用いて計算を行い、計算結果を記憶部 1に feす ο

[0039] 楕円曲線暗号演算装置でのスカラー倍演算の動作を図 2に示すフローチャートを用いて説明する。

まず、入力部 2は楕円曲線 Εの式を設定し、その式のパラメータである U、 a、 Wを入力する。また、楕円曲線 E上の点 P (z、 t)とスカラー倍数 Kとを入力する。入力した楕円曲線 Eの式とパラメータ U、 a、 Δ、 Wと楕円曲線 E上の点 P (z、 t)とスカラー倍数 Kは、記憶部 1に記憶される (ステップ S 100)。

[0040] 次に、初期設定部 7は、記憶部 1から楕円曲線 Eを読み出し、以下に示す（2)式で定まる種数 2超楕円曲線 Cのヤコビ多様体に埋め込む処理を行う（ステップ S 101)。

[0041] [数 2]

Y² - a₂X - (ひ " ")) ( 2 )

ここで、 a 、 a はXの2次方程式X + ( (W(U—2) (U + 2) + 32)Z(4U) ) X+W

1 2

=0の 2根である。また、丁と aと Uとは楕円曲線を規定するパラメータ、 Xと Yは変数である。

[0043] 初期設定部 7による楕円曲線 Eの種数 2超楕円曲線 Cのヤコビ多様体への埋め込みは、楕円曲線 Eを種数 2超楕円曲線 Cのヤコビ多様体へ写像するパラメータを設定すること〖こより行われる。このパラメータは、用いる楕円曲線 Eを変更しない限り、楕円曲線暗号演算装置に一度設定すれば、演算を行う都度設定する必要がなぐ継続して利用することができる。したがって、ステップ S101は、次回から実行されなくてもよい。

[0044] 次に、埋め込み演算部 3は、楕円曲線 E上の点 P= (z、 t)を種数 2超楕円曲線じのヤコビ多様体の点 Dに写像する演算 (埋め込み演算）を行う (ステップ S102)。

[0045] ここでは埋め込み演算部 3は、楕円曲線 E上の点 P (z、 t)力も代数曲線のヤコビ多様体の埋め込み点 D (x、 y)を求める楕円曲線 Eが埋め込まれた代数曲線のヤコビ多様体への写像を (3)式と (4)式の関係式で定める。

[0046] [数 3] x + - 1

[0047] [数 4] t

[0048] ここで、 xは種数 2超楕円曲線 Cのヤコビ多様体の点の x座標、 yは種数 2超楕円曲線 Cのヤコビ多様体の点の y座標、 zは楕円曲線 E上の点 Pの X座標、 tは楕円曲線 E 上の点 Pの y座標、 aと Uとは楕円曲線 Eを規定するパラメータである。

[0049] 埋め込み演算部 3の動作を図 3に示すフローチャートを用いて説明する。

埋め込み演算部 3は、記憶部 1から楕円曲線 E上の点 P= (z、 t)を読み出す (ステツプ S300)。次に、楕円曲線 E上の点 Pの X座標である zの有限体 GF (q)内での平方根を rとし、 (2( t)、 2(1ΖΛ tZr³) )を楕円曲線の積 E X E上の点として、その楕円曲線の積 E X E上の点に種数 2超楕円曲線 Cのヤコビ多様体の点 D= (x、 y)— (x 、一 y)を対応させる (ステップ S 301)。ここで、 x、 yは（5)式と（6)式で定める。 [0050] [数 5]

[a - l)z + +1 ,「、

x=- '- (5)

-oz +1

[0051] 園、

y (6)

[0052] ここで、 aと Uとは楕円曲線 Eを規定するパラメータである。

[0053] 次に、点 D= (x、 y)— (x、一 y)を 2次多項式 U(x)と 1次多項式 V(x)の対として表し

、 U (X)と V (X)の対を記憶部 1に記憶する (ステップ S302)。

[0054] 以上、ステップ S300からステップ S302までが埋め込み演算部 3での動作である。

[0055] 図 2に戻って楕円曲線暗号演算装置におけるスカラー倍演算の動作の説明を続ける。

次に、準同型写像演算部 4は、代数曲線である種数 2超楕円曲線 Cのヤコビ多様体の点 Dを 2倍して写像点 ε Dを求める。

[0056] つまり、準同型写像演算部 4は、代数曲線として種数 2超楕円曲線 Cを用い、種数 2 超楕円曲線 Cのヤコビ多様体の点 Dを 2倍する演算を行い写像点 ε Dを得る (ステップ S 103)。

[0057] 準同型写像演算部 4は、代数曲線のヤコビ多様体の準同型写像として、代数曲線のヤコビ多様体力も代数曲線の Richelot双対曲線のヤコビ多様体への準同型写像と、代数曲線の Richelot双対曲線のヤコビ多様体力代数曲線のヤコビ多様体への準同型写像との合成で決まる代数曲線のヤコビ多様体上の自己準同型写像を用いる。

[0058] 前者の代数曲線のヤコビ多様体力代数曲線の Richelot双対曲線のヤコビ多様体への準同型写像は、代数曲線が種数 2超楕円曲線 Cである場合、（7)式と (8)式で定まる。

[0059] G (x)H (z)+G (x)H (z) =0 (7)

1 1 2 2

[0060] yt = AG (x)H (z ) (x— z ) (8)

k 1 l k k ただし、 k=l、 2

[0061] ここで、 xは種数 2超楕円曲線 Cのヤコビ多様体の点の x座標、 yは種数 2超楕円曲線 Cのヤコビ多様体の点の y座標、 zは代数曲線のヤコビ多様体の点の X座標、 G1と G2とは種数 2超楕円曲線 Cを定義する関数、 HIと H2とは種数 2超楕円曲線 Cの Ri chelot双対曲線を定義する関数、 zは zに関する（1)式の零点、 tは各 zについて（ k k k

2)式により定まる値、 AG1は tを定義する関数である。

k

[0062] また、後者の代数曲線の Richelot双対曲線のヤコビ多様体力代数曲線のヤコビ多様体への準同型写像は、代数曲線が種数 2超楕円曲線 Cである場合、（9)式で定める。

[0063] (x、y)→(2Zx、（4y)Zx³) (9)

[0064] ここで、 Xは種数 2超楕円曲線 Cのヤコビ多様体の点の X座標、 yは種数 2超楕円曲線 Cのヤコビ多様体の点の y座標、→は写像を示す記号である。

[0065] 準同型写像演算部 4で用いる準同型写像について具体的に説明する。

種数 2超楕円曲線 Cを Y²=AG (X)G (X)G (X)と 2次式の積で表し、 G (X) =

0 1 2 i

∑g X^j(i=0, 1, 2)とした時、（10)式により種数 2超楕円曲線 Cの Richelot双対曲，

線が定義される。

[0066] det(g )Τ²=ΔΗ (Ζ)Η (Ζ)Η (Ζ) (10)

i, j 0 1 2

[0067] ここで、 H (Z)=G， (Z)G (Z)— G， (Z)G (Z)とする。また、 G'は多項式 i i +1 i + 2 i + 2 i+1

Gを Zで微分した多項式を表す。

[0068] これにより、種数 2超楕円曲線 Cのヤコビ多様体力も種数 2超楕円曲線 Cの Richelo t双対曲線のヤコビ多様体への準同型写像 pは、（11)式のように定められる。

[0069] [(x、y)— P ]→[(z、t )— (z、一 t )] (11)

0 1 1 2 2

[0070] ここで、 Pは Gの零点を x座標とし、 y座標は 0である種数 2超楕円曲線 C上の点で

0 0

ある。 z (k=l, 2)は zに関する（12)式で示される 2次多項式の零点とする。

k

[0071] G (x)H (z)+G (x)H (z) (12)

1 1 2 2

[0072] 各 zに対して tを t二（AG (x)H (z ) (x— z；)) Zyで定める。

k k k 1 l k k

[0073] 以上、前者の種数 2超楕円曲線 Cのヤコビ多様体力も種数 2超楕円曲線 Cの Riche lot双対曲線のヤコビ多様体への準同型写像について説明した。 [0074] また、この時、種数 2超楕円曲線 Cの 2乗法写像 εは± t— ¹ pで与えられる。ここで _tは、（9)式で定義される種数 2超楕円曲線 C力も種数 2超楕円曲線 Cの Richelo t双対曲線への同型写像であり、 I— ¹が、後者の種数 2超楕円曲線 Cの Richelot双対曲線のヤコビ多様体力種数 2超楕円曲線 Cのヤコビ多様体への準同型写像となる。

[0075] 準同型写像演算部 4での動作を図 4に示すフローチャートを用いて説明する。

まず、準同型写像演算部 4は記憶部 1から埋め込み演算部 3が生成した U(x)と V(

X)の対を読み出し、これを種数 2超楕円曲線 C上の 0次因子の点 D= (x、 y)-(x\y

')とする (ステップ S 200)。

[0076] 次に、準同型写像演算部 4は、（x、 y)から、 G (x)H (z) +G (x)H (z) =0を満

1 1 2 2

たす z (k=l, 2)について、 t = AG (x)H (z ) (x-z )となる tを定める。同様に、（ k k I l k k k

x，、y，）から、 G (x)H (z)+G (x)H (z)=0を満たす z， (k=l, 2)について、 t，

1 1 2 2 k k 二 AG (x)H (z ) (x— z )となる t，を定める（ステップ S 201)。

1 l k k k

[0077] 次に、準同型写像演算部 4は、 ((z 、 t ) + (z 、 t ))一（(z，ゝ t， ) + (ζ' ゝ t， ))と

1 1 2 2 1 1 2 2 いう 0次因子を表す 2次多項式 U (z)と 1次多項式 V (z)とを計算する (ステップ S20

0 0

2)。これが Richelot双対曲線上の因子となる。

[0078] 次に、準同型写像演算部 4は、 Richelot双対曲線力も Cへの写像である（x、 y)→ ( 2/x、（4y)/x³)から決まるヤコビ多様体間の写像によって、 U (z)、V (z)を U(z)

0 0

、 V(z)に変換し (ステップ S203)、 U(z)、 V(z)を記憶部 1に記憶する (ステップ S20 4)。

[0079] 以上、ステップ S200からステップ S204までが準同型写像演算部 4での動作である

[0080] 図 2に戻って楕円曲線暗号演算装置におけるスカラー倍演算の動作の説明を続ける。

次に、射影演算部 5は、種数 2超楕円曲線 Cのヤコビ多様体の点 ε D= (x、 y)-(x '、 y' )を楕円曲線上の点 P'に写像する演算 (射影演算)を行う (ステップ S104)。

[0081] 射影演算部 5は、射影点 ε D= (x、 y)— (χ'、 y )から楕円曲線 E上の射影点 P' (z 、 t)を求める楕円曲線 Eへの写像を（ 13)式と（ 14)式との関係式で定める。 [0082] [数 7]

(13)

coc + a-.

[0083] [数 8]

[0084] ここで、 xは種数 2超楕円曲線 Cのヤコビ多様体の点の x座標、 yは種数 2超楕円曲線 Cのヤコビ多様体の点の y座標、 zは楕円曲線 E上の点 Pの X座標、 tは楕円曲線 E 上の点 Pの y座標、 aと Uとは楕円曲線 Eを規定するパラメータである。

[0085] 同様に、射影演算部 5では、 z'、 t 'を以下に示す（15)式と（16)式との関係式で定める。

[0086] [数 9]

(1 5)

ax +a

[0087] [数 10] t, 32 (ひ3一 8t/² 4 ² + 4t/ - 2θ) _{( l g)}

[0088] ここで、 x'は種数 2超楕円曲線 Cのヤコビ多様体の点の x座標、 y'は種数 2超楕円曲線 Cのヤコビ多様体の点の y座標、 z，は楕円曲線 E上の点 Pの X座標、 t，は楕円曲線 E上の点 Pの y座標、 aと Uとは楕円曲線 Eを規定するパラメータである。

[0089] そして、（z²、t)— (z，²、t，）で与えられる楕円曲線 E上の点 P，を対応させる。

[0090] 射影演算部 5での動作を図 5に示すフローチャートを用いて説明する。

射影演算部 5は、準同型写像演算部 4で生成した U(z)、 V(z)を記憶部 1から読み出し、種数 2超楕円曲線 Cのヤコビ多様体の点 (x、 y)-(x'、 y')とする (ステップ S40 0)。

[0091] 次に、射影演算部 5は、 z、 t、 z'、 t 'を上記した（14)式一（17)式で求め、（z²、 t)

(ζ' ²、 t' )で与えられる楕円曲線 E上の点 P'を得る (ステップ S401)。

[0092] 次に、射影演算部 5は、得られた楕円曲線 E上の点 P'を記憶部 1に記憶する (ステップ S402)。

[0093] 以上、ステップ S400からステップ S402までが射影演算部 5での動作である。

[0094] 図 2に戻って楕円曲線暗号演算装置におけるスカラー倍演算の動作の説明を続ける。

計算処理部 6は、ステップ S 100からステップ S104を行った後、記憶部 1から楕円曲線 E上の点 P'を読み出し、上記した GLV型スカラー倍演算を用いて、楕円曲線 E 上の点 P，のスカラー倍数 Kでのスカラー倍演算を行い、 KP，を得る（ステップ S 105) 。そして、計算により得た KP'を出力する (ステップ S106)。

[0095] 以上、この実施形態における楕円曲線暗号演算装置でのスカラー倍演算の方法をまとめる。まず、埋め込み演算部 3により、楕円曲線 E上の点 Pを種数 2超楕円曲線 C のヤコビ多様体の点 Dに変換する。次に、準同型写像演算部 4により、 2乗法写像 εを用いて ε Dを計算し、射影演算部 5により、 ε Dカゝら楕円曲線 Ε上の点を得る。ここでは、その点を φ (Ρ)と書くことにする。最後に、 φ (Ρ)を特殊準同型に用いて GL V型スカラー倍演算を行うことにより、スカラー倍数 Κでのスカラー倍演算を実現できる。

[0096] 上記したスカラー倍演算は、その方法をプログラムで記述することによりコンビユータに実行させることができる。

具体的には、楕円曲線 Ε上の点 Ρのスカラー倍 (Κ倍)演算をコンピュータに実行させるプログラムは、楕円曲線 Ε上の点 Ρを種数 2超楕円曲線 Cのヤコビ多様体上の点 Dに変換し、点 Dに対して、種数 2超楕円曲線 Cのヤコビ多様体の準同型写像による写像をして写像点 ε Dを求め、写像点 ε Dを楕円曲線 Ε上へ写像して楕円曲線の射影点 P'を求め、

演算値 Κと射影点 P'とを読み込んで、射影点 P'を Κ倍する計算を行い、計算結果を出力する。 [0097] この実施の形態によれば楕円曲線暗号演算装置は、楕円曲線 Eを示す情報と楕円曲線 E上の点 Pと演算値 Kとを入力して記憶部に記憶する入力部と、記憶部に記憶された楕円曲線 E上の点 Pを読み込んで、楕円曲線 E上の点 Pを、その楕円曲線 Eに対応する代数曲線のヤコビ多様体へ写像して楕円曲線 E上の点 Pに対応する代数曲線のヤコビ多様体上の点を埋め込み点 Dとして求め、埋め込み点 Dを記憶部に記憶する埋め込み演算部と、記憶部に記憶された埋め込み点 Dを読み込んで、代数曲線のヤコビ多様体の準同型写像による写像をして写像点 _ε Dを求め、写像点 ε Dを記憶部に記憶する準同型写像演算部と、記憶部に記憶された写像点 ε Dを読み込んで、楕円曲線 Εへ写像して楕円曲線の射影点 P 'を求め、射影点 P 'を記憶部に記憶する射影演算部と、記憶部に記憶された演算値 Κと射影点 P 'とを読み込んで、演算値 Κと射影点 P 'とを用いて計算を行い、計算結果を記憶部に記憶する計算処理部とを備えるので、楕円曲線暗号で行うスカラー倍演算を従来より速い処理速度で実行することが可能となる。

[0098] この実施の形態によれば楕円曲線暗号演算装置は、さらに、代数曲線を選択して記憶部に設定するとともに、楕円曲線 Ε上の点 Ρを、代数曲線のヤコビ多様体へ写像するためのパラメータを記憶部に設定する初期設定部を備えるので、用いる楕円曲線を変更することができ、多様な楕円曲線で楕円曲線暗号を実行することが可能となる。その結果、楕円曲線暗号演算装置で実行する楕円曲線暗号の安全性を向上させることができる。

[0099] この実施の形態によれば楕円曲線暗号演算装置の初期設定部は、代数曲線として超楕円曲線を選択し、さらに、代数曲線として種数 2超楕円曲線 Cを選択するので、楕円曲線 Ε上の点 Ρの種数 2超楕円曲線 Cのヤコビ多様体への写像を行うことにより、従来より速い処理速度で楕円曲線暗号で行うスカラー倍演算を実行することが可能となる。

[0100] この実施の形態によれば楕円曲線暗号演算装置の準同型写像演算部は、代数曲線のヤコビ多様体の点 Dを 2倍して写像点 ε Dを求めるので、 2倍して写像を行う効率的に計算可能な準同型写像を利用することが可能となる。

[0101] この実施の形態によれば楕円曲線暗号演算装置の入力部は、楕円曲線 Εを示す情報として 2捩れ点を有する楕円曲線を示す情報を入力するので、または、位数が素数になっている位数素数の楕円曲線を示す情報を入力するので、楕円曲線 E上の点 Pの種数 2超楕円曲線 Cのヤコビ多様体への写像を利用した従来より速、処理の速、スカラー倍演算を実行することが可能となる。

[0102] この実施の形態によれば楕円曲線暗号演算装置の準同型写像演算部は、代数曲線のヤコビ多様体の準同型写像として、代数曲線のヤコビ多様体力代数曲線の Ri chelot双対曲線のヤコビ多様体への準同型写像と、代数曲線の Richelot双対曲線のヤコビ多様体力代数曲線のヤコビ多様体への準同型写像との合成で決まる代数曲線のヤコビ多様体上の自己準同型写像を用いるので、この代数曲線のヤコビ多様体上の自己準同型写像をスカラー倍演算を効率的に計算することが可能な準同型写像として用いることができる。

[0103] この実施の形態によれば楕円曲線暗号演算装置の準同型写像演算部で用いる代数曲線のヤコビ多様体力代数曲線の Richelot双対曲線のヤコビ多様体への準同型写像は、代数曲線が種数 2超楕円曲線 Cである場合、上記した (7)式と (8)式とで定まり、また、楕円曲線暗号演算装置の準同型写像演算部で用いる代数曲線の Ric helot双対曲線のヤコビ多様体力代数曲線のヤコビ多様体への準同型写像は、代数曲線が種数 2超楕円曲線 Cである場合、上記した（9)式で定まるので、これらを合成した写像である代数曲線のヤコビ多様体上の自己準同型写像をスカラー倍演算を効率的に計算することが可能な準同型写像として用いることができる。

[0104] この実施の形態によれば楕円曲線暗号演算装置の埋め込み演算部は、楕円曲線 E上の点 P (z、 t)力も代数曲線のヤコビ多様体の埋め込み点 D (x、 y)を求める楕円曲線 Eが埋め込まれた代数曲線のヤコビ多様体への写像を上記した（3)式と (4)式との関係式で定めるので、楕円曲線 E上の点 Pを代数曲線のヤコビ多様体の点 Dへ写像することができる。

[0105] この実施の形態によれば楕円曲線暗号演算装置の射影演算部は、射影点 ε D (χ 、 y)から楕円曲線 Ε上の射影点 P ' (z、 t)を求める楕円曲線 Εへの写像を上記した（1 3)式一（16)式との関係式で定めるので、代数曲線のヤコビ多様体の点 ε Dを楕円曲線上の点 P 'に写像することができる。 [0106] この実施の形態によれば楕円曲線を用いた演算装置の演算方法として、楕円曲線 Eを示す情報と楕円曲線 E上の点 Pと演算値 Kとを入力して記憶部に記憶し、記憶部に記憶された楕円曲線 E上の点 Pを読み込んで、楕円曲線 E上の点 Pを、その楕円曲線 Eに対応する代数曲線のヤコビ多様体へ写像して楕円曲線 E上の点 Pに対応する代数曲線のヤコビ多様体上の点を埋め込み点 Dとして求め、埋め込み点 Dを記憶部に記憶し、記憶部に記憶された埋め込み点 Dを読み込んで、代数曲線のヤコビ多様体の準同型写像による写像をして写像点 _ε Dを求め、写像点 ε Dを記憶部に記憶し、記憶部に記憶された写像点 ε Dを読み込んで、楕円曲線 Εへ写像して楕円曲線 Ε上の射影点 P'を求め、射影点 P'を記憶部に記憶し、記憶部に記憶された演算値 Κと射影点 P'とを読み込んで、演算値 Κと射影点 P'とを用いて計算を行い、計算結果を記憶部に記憶するので、楕円曲線暗号で行うスカラー倍演算を従来より速い処理速度で実行することが可能となる。

[0107] この実施の形態によれば楕円曲線 Ε上の点 Ρを種数 2超楕円曲線 Cのヤコビ多様体上の点 Dに変換し、点 Dに対して、種数 2超楕円曲線 Cのヤコビ多様体の準同型写像による写像をして写像点 ε Dを求め、写像点 ε Dを楕円曲線 Ε上へ写像して楕円曲線の射影点 P'を求め、演算値 Κと射影点 P'とを読み込んで、射影点 P'を Κ倍する計算を行い、計算結果を出力することをプログラムに記載するので、楕円曲線 Ε 上の点 Ρのスカラー倍 (Κ倍)演算をコンピュータに実行させることができる。

[0108] この実施の形態によれば、従来の方法では、力なり特殊なタイプの楕円曲線 Εにしか適用することができな力つた楕円曲線暗号でのスカラー倍演算の高速ィ匕手法である GLV型スカラー倍演算を、力なり一般な楕円曲線 Εに適用することができるようになり、これにより楕円曲線暗号の安全性を実用上十分に保証されるようにした。

[0109] 以上、実施の形態について説明した。

なお、楕円曲線暗号演算装置は、楕円曲線をある種数 2超楕円曲線 Cのヤコビ多様体に埋め込む演算部と、楕円曲線上の点を種数 2超楕円曲線 Cのヤコビ多様体の点に写像する演算 (埋め込み演算）を行う演算部と、種数 2超楕円曲線 Cのヤコビ多様体の点を 2倍する演算を行う演算部と、種数 2超楕円曲線 Cのヤコビ多様体の点を楕円曲線上の点に写像する演算 (射影演算)を行う演算部とを備えたことを特徴とする。ここで、 2倍演算とは、非特許文献 4で記述された 2度行うと 2倍写像になる演算である。

[0110] また、楕円曲線暗号演算装置は、特殊準同型写像 φとして、次式で定まる Cのヤコビ多様体力も Cの Richelot双対曲線のヤコビ多様体への準同型写像と、

G (x)H (z) +G (x)H (z) =0、 yt = AG (x)H (z ) (x— z )

1 1 2 2 k l l k k

次式で定まる Cの Richelot双対曲線のヤコビ多様体力 Cのヤコビ多様体への準同型写像と、

(x、y)→(2/x、 (4y)/x³)

の合成で決まる種数 2超楕円曲線 Cのヤコビ多様体上の自己準同型写像を用いることを特徴とする。

[0111] 楕円曲線暗号演算装置では、楕円曲線 E力種数 2超楕円曲線 Cのヤコビ多様体への写像、種数 2超楕円曲線 Cのヤコビ多様体力楕円曲線 Eへの写像が、楕円曲線上の点（z、 t)と種数 2超楕円曲線 Cの点 (x、 y)の間の以下に示す関係式から定まることを特徴とする。

ζ=(χ— α— 1)/ ( αχ+ α— 1)

t = 32y(U³-8U² + 4U + 32+ a (U— 4) (U² + 4U~20) ) / ( (U~2) ( a x+ a— l))³

[0112] また、プログラムにより楕円曲線暗号演算装置の楕円曲線をある種数 2超楕円曲線 Cのヤコビ多様体に埋め込む演算部と、楕円曲線上の点を種数 2超楕円曲線 Cのャコビ多様体の点に写像する演算 (埋め込み演算)を行う演算部と、種数 2超楕円曲線 Cのヤコビ多様体の点を 2倍する演算を行う演算部と、種数 2超楕円曲線 Cのヤコビ多様体の点を楕円曲線上の点に写像する演算 (射影演算)を行う演算部とを用いる演算処理をコンピュータに実行させる。ここで、 2倍演算とは、非特許文献 4で記述された 2度行うと 2倍写像になる演算である。

[0113] また、プログラムにより楕円曲線暗号演算装置の特殊準同型写像 φとして、次式で定まる Cのヤコビ多様体力も Cの Richelot双対曲線のヤコビ多様体への準同型写像と、

G (x)H (z)+G (x)H (z)=0 yt = A G (x) H (z ) (x-z )

k 1 l k k

次式で定まる Cの Richelot双対曲線のヤコビ多様体力 Cのヤコビ多様体への準同型写像、

(x、 y)→(2Zx、 (4y) /x³)

の合成で決まる種数 2超楕円曲線 Cのヤコビ多様体上の自己準同型写像を用いる演算処理をコンピュータに実行させる。

[0114] また、プログラムにより楕円曲線暗号演算装置の楕円曲線 E力種数 2超楕円曲線 Cのヤコビ多様体への写像、種数 2超楕円曲線 Cのヤコビ多様体力楕円曲線 Eへの写像が、楕円曲線上の点 (z、 t)と種数 2超楕円曲線 Cの点 (x、 y)の間の以下に示す関係式力定まる演算処理をコンピュータに実行させる。

ζ= (χ— α— 1) / ( α χ+ α— 1)

t = 32y (U³-8U² + 4U + 32+ a (U— 4) (U² + 4U~20) ) / ( (U~2) ( a x+ a— l) ) ³

[0115] 以上、実施の形態において述べた楕円曲線暗号演算装置は、コンピュータにより実現することができる。図 6は、実施の形態における楕円曲線暗号演算装置をコンビユータにより実現した場合のハードウェア構成を示す図である。

[0116] 図 6において楕円曲線暗号演算装置は、プログラムを実行する CPU (Central Pr ocessing Unit) 911を備えて！/、る。 CPU911は、ノス 912を介して ROM (Read Only Memory) 913、 RAM (Random Access Memory) 914、通信ボード 91 5、表示装置 901、キーボード（KZB) 902、マウス 903、 FDD (Flexible Disk Dr ive) 904、磁気ディスク装置 920、 CDD (Compact Disk Drive) 905、プリンタ装置 906、スキャナ装置 907と接続されている。

[0117] RAM914は、揮発性メモリの一例である。 ROM913、 FDD904、 CDD905、磁気ディスク装置 920、光ディスク装置は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。

[0118] 磁気ディスク装置 920には、オペレーティングシステム（OS) 921、ウィンドウシステム 922、プログラム群 923、ファイル群 924が記憶されている。プログラム群 923は、 C PU911、 OS921、ウィンドウシステム 922により実行される。 [0119] プログラム群 923には、上記した実施の形態の説明において「一部」として説明した機能を実行するプログラムが記憶されている。プログラムは、 CPU911により読み出され実行される。

[0120] 上記した実施の形態の説明にお!/、て説明するフローチャートの矢印の部分は主としてデータの入出力を示し、そのデータの入出力のためにデータは、磁気ディスク装置 920、 FD (Flexible Disk)、光ディスク、 CD (Compact Disk)、 MD (Mini Di sk)、 DVD (Digital Versatile Disk)等のその他の記録媒体に記録される。あるいは、信号線やその他の伝送媒体により伝送される。

[0121] 上記した実施の形態の説明において「一部」として説明するものは、 ROM913に記憶されたファームウェアで実現されていても構わない。あるいは、ソフトウェアのみ、あるいは、ハードウェアのみ、あるいは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わな!/、。

[0122] 上記した実施の形態を実施するプログラムは、また、磁気ディスク装置 920、 FD (F1 exible Disk)、光ディスク、 CD (Compact Disk)、 MD (Mini Disk)、 DVD (Di gital Versatile Disk)等のその他の記録媒体による記録装置を用いて記憶されても構わない。

図面の簡単な説明

[0123] [図 1]実施の形態における楕円曲線暗号演算装置の構成を示す図である。

[図 2]実施の形態における楕円曲線暗号演算装置でのスカラー倍演算の動作を示すフローチャートである。

[図 3]実施の形態における楕円曲線暗号演算装置の埋め込み演算部の動作を示すフローチャートである。

[図 4]実施の形態における楕円曲線暗号演算装置の準同型写像演算部の動作を示すフローチャートである。

[図 5]実施の形態における楕円曲線暗号演算装置の射影演算部の動作を示すフロ一チャートである。

[図 6]実施の形態における楕円曲線暗号演算装置をコンピュータにより実現した場合のハードウェア構成を示す図である。符号の説明

1 記憶部、 2 入力部、 3 埋め込み演算部、 4 準同型写像演算部、 5 射影演算部、 6 計算処理部、 7 初期設定部、 901 表示装置、 902 キーボード (KZB)、 9 03 マウス、 904 FDD, 905 CDD、 906 プリンタ装置、 907 スキャナ装置、 91 1 CPU, 912 ノス、 913 ROM, 914 RAM, 915 通信ボード、 920 磁気ディスク装置、 921 OS、 922 ウィンドウシステム、 923 プログラム群、 924 フアイノレ群

Claims

請求の範囲

[1] 楕円曲線 Eを示す情報と楕円曲線 E上の点 Pと演算値 Kとを入力して記憶部に記憶する入力部と、

記憶部に記憶された楕円曲線 Ε上の点 Ρを読み込んで、楕円曲線 Ε上の点 Ρを、その楕円曲線 Εに対応する代数曲線のヤコビ多様体へ写像して楕円曲線 Ε上の点 Ρに対応する代数曲線のヤコビ多様体上の点を埋め込み点 Dとして求め、埋め込み点 D を記憶部に記憶する埋め込み演算部と、

記憶部に記憶された埋め込み点 Dを読み込んで、代数曲線のヤコビ多様体の準同型写像による写像をして写像点 ε Dを求め、写像点 ε Dを記憶部に記憶する準同型写像演算部と、

記憶部に記憶された写像点 ε Dを読み込んで、楕円曲線 Εへ写像して楕円曲線の射影点 P 'を求め、射影点 P 'を記憶部に記憶する射影演算部と、

記憶部に記憶された演算値 Κと射影点 P 'とを読み込んで、演算値 Κと射影点 P 'とを用いて計算を行い、計算結果を記憶部に記憶する計算処理部と

を備えたことを特徴とする楕円曲線暗号演算装置。

[2] 上記楕円曲線暗号演算装置は、さらに、

代数曲線を選択して記憶部に設定するとともに、楕円曲線 Ε上の点 Ρを、代数曲線のヤコビ多様体へ写像するためのパラメータを記憶部に設定する初期設定部を備えたこと

を特徴とする請求項 1記載の楕円曲線暗号演算装置。

[3] 上記初期設定部は、

代数曲線として、超楕円曲線を選択すること

を特徴とする請求項 2記載の楕円曲線暗号演算装置。

[4] 上記初期設定部は、

代数曲線として、種数 2超楕円曲線 Cを選択すること

を特徴とする請求項 2記載の楕円曲線暗号演算装置。

[5] 上記準同型写像演算部は、

代数曲線のヤコビ多様体の点 Dを 2倍して写像点 ε Dを求めることを特徴とする請求項 1記載の楕円曲線暗号演算装置。

[6] 上記入力部は、

楕円曲線 Eを示す情報として 2捩れ点を有する楕円曲線を示す情報を入力することを特徴とする請求項 1記載の楕円曲線暗号演算装置。

[7] 上記入力部は、

楕円曲線 Eを示す情報として、位数が素数になっている位数素数の楕円曲線を示す情報を入力すること

を特徴とする請求項 1記載の楕円曲線暗号演算装置。

[8] 上記準同型写像演算部は、

上記代数曲線のヤコビ多様体の準同型写像として、

代数曲線のヤコビ多様体力代数曲線の Richelot双対曲線のヤコビ多様体への準同型写像と、代数曲線の Richelot双対曲線のヤコビ多様体力も代数曲線のヤコビ多様体への準同型写像との合成で決まる代数曲線のヤコビ多様体上の自己準同型写像を用いること

を特徴とする請求項 1記載の楕円曲線暗号演算装置。

[9] 上記代数曲線のヤコビ多様体力も代数曲線の Richelot双対曲線のヤコビ多様体への準同型写像は、上記代数曲線が種数 2超楕円曲線 Cである場合、

G (x) H (z) +G (x) H (z) =0 (1)

1 1 2 2

yt = A G (x) H (z ) (x-z ) (2)

k 1 l k k

ただし、 k= l、 2

(ここで、 xは種数 2超楕円曲線 Cのヤコビ多様体の点の x座標、 yは種数 2超楕円曲線 Cのヤコビ多様体の点の y座標、 zは代数曲線のヤコビ多様体の点の X座標、 G1 と G2とは種数 2超楕円曲線 Cを定義する関数、 HIと H2とは種数 2超楕円曲線 Cの R ichelot双対曲線を定義する関数、 zは zに関する（1)式の零点、 tは各 zについて（

k k k

2)式により定まる値、 A G1は tを定義する関数である。 )

k

で定まること

を特徴とする請求項 8記載の楕円曲線暗号演算装置。

[10] 上記代数曲線の Richelot双対曲線のヤコビ多様体力も代数曲線のヤコビ多様体への準同型写像は、上記代数曲線が種数 2超楕円曲線 Cである場合、 (x、y)→(2Zx、 (4y) /x³)

(ここで、 Xは種数 2超楕円曲線 Cのヤコビ多様体の点の X座標、 yは種数 2超楕円曲線 Cのヤコビ多様体の点の y座標、→は写像を示す記号である。 )

で定まること

を特徴とする請求項 8記載の楕円曲線暗号演算装置。

[11] 上記埋め込み演算部は、

楕円曲線 E上の点 P (z、 t)力も代数曲線のヤコビ多様体の埋め込み点 D (x、 y)を求める上記楕円曲線 Eが埋め込まれた代数曲線のヤコビ多様体への写像を

[数 11] x - a - 1

z

+ —丄

[数 12]

, 32y^J³ - 8σ² + 4U + 32 + a(u - A^J² + 4U - 20 ))

(ここで、 xは種数 2超楕円曲線 Cのヤコビ多様体の点の x座標、 yは種数 2超楕円曲線 Cのヤコビ多様体の点の y座標、 zは楕円曲線 E上の点 Pの X座標、 tは楕円曲線 E上の点 Pの y座標、 αと Uとは楕円曲線 Eを規定するパラメータである。 ) という関係式で定めること

を特徴とする請求項 1記載の楕円曲線暗号演算装置。

[12] 上記射影演算部は、

射影点 ε D (x、 y)から楕円曲線 E上の射影点 P' (z、 t)を求める上記楕円曲線 Eへの写像を

[数 13] [数 14]

32 ³— 8t/² + 4t/ + 32 + c ((ひ一 4 + 4ひ一 20¾

((ひ -

+ α - 1))³

(ここで、 xは種数 2超楕円曲線 Cのヤコビ多様体の点の x座標、 yは種数 2超楕円曲線 Cのヤコビ多様体の点の y座標、 zは楕円曲線 E上の点 Pの X座標、 tは楕円曲線 E上の点 Pの y座標、 aと Uとは楕円曲線 Eを規定するパラメータ

である。 )

という関係式で定めること

を特徴とする請求項 1記載の楕円曲線暗号演算装置。

[13] 楕円曲線を用いた演算装置の演算方法において、

楕円曲線 Eを示す情報と楕円曲線 E上の点 Pと演算値 Kとを入力して記憶部に記し、

記憶部に記憶された楕円曲線 E上の点 Pを読み込んで、楕円曲線 E上の点 Pを、その楕円曲線 Eに対応する代数曲線のヤコビ多様体へ写像して楕円曲線 E上の点 Pに対応する代数曲線のヤコビ多様体上の点を埋め込み点 Dとして求め、埋め込み点 D を記憶部に記憶し、

記憶部に記憶された埋め込み点 Dを読み込んで、代数曲線のヤコビ多様体の準同型写像による写像をして写像点 ε Dを求め、写像点 ε Dを記憶部に記憶し、記憶部に記憶された写像点 ε Dを読み込んで、楕円曲線 Εへ写像して楕円曲線 Ε 上の射影点 P'を求め、射影点 P'を記憶部に記憶し、

記憶部に記憶された演算値 Κと射影点 P'とを読み込んで、演算値 Κと射影点 P'とを用いて計算を行い、計算結果を記憶部に記憶することを特徴とする演算方法。

[14] 楕円曲線 Ε上の点 Ρのスカラー倍 (Κ倍)演算をコンピュータに実行させるプログラムにおいて、

楕円曲線 Ε上の点 Ρを種数 2超楕円曲線 Cのヤコビ多様体上の点 Dに変換し、点 Dに対して、種数 2超楕円曲線 Cのヤコビ多様体の準同型写像による写像をして写像点 ε Dを求め、写像点 ε Dを楕円曲線 Ε上へ写像して楕円曲線の射影点 P'を求め、

演算値 Κと射影点 P'とを読み込んで、射影点 P'を Κ倍する計算を行い、計算結果を出力する

ことを特徴とするプログラム。