(57)【特許請求の範囲】
【請求項１】
以下の式で表わされ、Montgomery型楕円曲線E上の点P1=(x1,y1)を、アファイン座標系において2k倍(kは2以上の整数)した点P2k=(x2k,y2k)を求める演算装置であって、以下の要素を有する演算装置。
E：By2＝x3＋Ax2＋x mod p
（１）素数pと、素体Fp上の元A及び元Bと、点P1の座標x1及び座標y1と、整数kとを入力する入力手段、
（２）入力された素数pと、元Aと、元Bと、座標x1と、座標y1と、整数kとを記憶する記憶手段、
（３）元Aと、元Bと、素数pとを読み出し、C=AB mod pを求めるC演算手段、
（４）求めたCを記憶するC記憶手段、
（５）元Bと素数pとを読み出し、B2 mod pを求めるB2演算手段、
（６）求めたB2を記憶するB2記憶手段、
（７）座標x1と、元Bと、素数pとを読み出し、以下の式により、配列要素D0を求めるD0演算手段、
D0＝x1B mod p
（８）求めた配列要素D0を記憶するD0記憶手段、
（９）座標y1と、素数pとを読み出し、以下の式により、配列要素E0を求めるE0演算手段、
E0= y1 mod p
（１０）求めた配列要素E0を記憶するE0記憶手段、
（１１）座標x1と、元Aと、素数pとを読み出し、以下の式により、配列要素F0を求めるF0演算手段、
F0 = 1+x1(2A+3x1) mod p
（１２）求めた配列要素F0を記憶するF0記憶手段、
（１３）変数iを記憶するi記憶手段、
（１４）i記憶手段に、変数iの初期値1を設定するi初期値設定手段、
（１５）整数kと、変数iとを読み出し、変数iが整数kに達するまで変数iに順次1を加えて、i記憶手段に設定するiインクリメント手段、
（１６）i記憶手段に変数iが設定される度に、変数iと、素数pと、Cとを読み出し、更に、読み出した変数ｉにより特定される配列要素Di-1と、配列要素E0からEi-1と、配列要素Fi-1とを読み出し、以下の式により、配列要素Diを求めるDi演算手段、
【数１】
0004479135.tif 000014
（１７）求めた配列要素Diを記憶するDi記憶手段、
（１８）i記憶手段に変数1が設定された時、B2と、素数pと、配列要素D0とD1と、配列要素E0と、配列要素F0とを読み出し、以下の式により、配列要素E1を求めるE1演算手段、
E1 = -8B2E04+F0(4D0E02-D1) mod p
（１９）求めた配列要素E1を記憶するE1記憶手段、
（２０）i記憶手段に変数iが2以上に設定される度に、変数iと、素数pとを読み出し、更に読み出した変数iにより特定される配列要素Di-1とDiと、配列要素Ei-1と、配列要素Fi-1とを読み出し、以下の式により、配列要素Eiを求めるEi演算手段、
Ei = -8Ei-14+Fi-1(4Di-1Ei-12-Di) mod p
（２１）求めた配列要素Eiを記憶するEi記憶手段、
（２２）i記憶手段に変数iがｋ−１以下に設定される度に、変数iと、Cと、B2と、素数pとを読み出し、更に読み出した変数iにより特定される配列要素Diと、配列要素E0からEi-1とを読み出し、以下の式により、配列要素Fiを求めるFi演算手段、
【数２】
0004479135.tif 000015
（２３）求めた配列要素Fiを記憶するFi記憶手段、
（２４）整数kと、素数pと、元Bとを読み出し、更に読み出した整数kにより特定される配列要素Dkと、配列要素E0からEk-1とを読み出し、以下の式により、座標x2kを求めるx2k演算手段、
【数３】
0004479135.tif 000016
（２５）整数kと、素数pと、B2とを読み出し、更に読み出した整数kにより特定される配列要素E0からEkとを読み出し、以下の式により、座標y2kを求めるy2k演算手段、
【数４】
0004479135.tif 000017
（２６）求めた座標x2kと、座標y2kとを出力する出力手段。
【請求項２】
以下の式で表わされ、Montgomery型楕円曲線E上の点P1=(x1,y1)を、アファイン座標系において2k倍(kは2以上の整数)した点P2k=(x2k,y2k)を求める演算方法であって、以下の要素を有する演算方法。
E：By2＝x3＋Ax2＋x mod p
（１）素数pと、素体Fp上の元A及び元Bと、点P1の座標x1及び座標y1と、整数kとが入力手段に入力される入力工程、
（２）前記入力手段に入力された素数pと、元Aと、元Bと、座標x1と、座標y1と、整数kとを記憶手段に記憶する記憶工程、
（３）前記記憶手段から元Aと、元Bと、素数pとを読み出し、C演算手段でC=AB mod pを求めるC演算工程、
（４）前記C演算手段で求めたCをC記憶手段に記憶するC記憶工程、
（５）前記記憶手段から元Bと素数pとを読み出し、B2演算手段でB2 mod pを求めるB2演算工程、
（６）前記B2演算手段で求めたB2をB2記憶手段に記憶するB2記憶工程、
（７）前記記憶手段から座標x1と、元Bと、素数pとを読み出し、D0演算手段で、以下の式により、配列要素D0を求めるD0演算工程、
D0＝x1B mod p
（８）前記D0演算手段で求めた配列要素D0をD0記憶手段に記憶するD0記憶工程、
（９）前記記憶手段から座標y1と、素数pとを読み出し、E0演算手段で、以下の式により、配列要素E0を求めるE0演算工程、
E0= y1 mod p
（１０）前記E0演算手段で求めた配列要素E0をE0記憶手段に記憶するE0記憶工程、
（１１）前記記憶手段から座標x1と、元Aと、素数pとを読み出し、F0演算手段で、以下の式により、配列要素F0を求めるF0演算工程、
F0 = 1+x1(2A+3x1) mod p
（１２）前記F0演算手段で求めた配列要素F0をF0記憶手段に記憶するF0記憶工程、
（１３）i初期値設定手段により、i記憶手段に、変数iの初期値1が設定されるi初期値設定工程、
（１４）前記記憶手段から整数kを読み出し、前記i記憶手段から変数iを読み出し、iインクリメント手段により、変数iが整数kに達するまで変数iに順次1を加えて、前記i記憶手段に設定するiインクリメント工程、
（１５）前記i記憶手段に変数iが設定される度に、前記i記憶手段から変数iを読み出し、前記記憶手段から素数pを読み出し、前記C記憶手段からCを読み出し、読み出された変数ｉにより特定される配列要素Di-1と、配列要素E0からEi-1と、配列要素Fi-1とを読み出し、Di演算手段で、以下の式により、配列要素Diを求めるDi演算工程、
【数５】
0004479135.tif 000018
（１６）前記Di演算手段で求めた配列要素DiをDi記憶手段に記憶するDi記憶工程、
（１７）前記i記憶手段に変数1が設定された時、B2と、素数pと、配列要素D0とD1と、配列要素E0と、配列要素F0とを読み出し、E1演算手段で、以下の式により、配列要素E1を求めるE1演算工程、
E1 = -8B2E04+F0(4D0E02-D1) mod p
（１８）前記E1演算手段で求めた配列要素E1をE1記憶手段に記憶するE1記憶工程、
（１９）前記i記憶手段に変数iとして2以上が設定される度に、前記i記憶手段から変数iを読み出し、前記記憶手段から素数pを読み出し、読み出した変数iにより特定される配列要素Di-1とDiと、配列要素Ei-1と、配列要素Fi-1とを読み出し、Ei演算手段で、以下の式により、配列要素Eiを求めるEi演算工程、
Ei = -8Ei-14+Fi-1(4Di-1Ei-12-Di) mod p
（２０）前記Ei演算手段で求めた配列要素EiをEi記憶手段に記憶するEi記憶工程、
（２１）前記i記憶手段に変数iとしてｋ−１以下が設定される度に、前記i記憶手段から変数iを読み出し、前記C記憶手段からCを読み出し、前記B2記憶手段からB2を読み出し、前記記憶手段から素数pを読み出し、読み出した変数iにより特定される配列要素Diと、配列要素E0からEi-1とを読み出し、Fi演算手段で、以下の式により、配列要素Fiを求めるFi演算工程、
【数６】
0004479135.tif 000019
（２２）前記Fi演算手段で求めた配列要素FiをFi記憶手段に記憶するFi記憶工程、
（２３）前記記憶手段から整数kと、素数pと、元Bとを読み出し、読み出した整数kにより特定される配列要素Dkと、配列要素E0からEk-1とを読み出し、x2k演算手段で、以下の式により、座標x2kを求めるx2k演算工程、
【数７】
0004479135.tif 000020
（２４）前記記憶手段から整数kと、素数pを読み出し、前記B2記憶手段からB2を読み出し、読み出した整数kにより特定される配列要素E0からEkを読み出し、y2k演算手段で、以下の式により、座標y2kを求めるy2k演算工程、
【数８】
0004479135.tif 000021
（２５）前記x2k演算手段で求めた座標x2kと、前記y2k演算手段で求めた座標y2kとを出力手段から出力する出力工程。
【請求項３】
以下の式で表わされ、Montgomery型楕円曲線E上の点P1=(x1,y1)を、アファイン座標系において2k倍(kは2以上の整数)した点P2k=(x2k,y2k)を求める演算装置となるコンピュータに、以下の処理を実行させるためのプログラム。
E：By2＝x3＋Ax2＋x mod p
（１）素数pと、素体Fp上の元A及び元Bと、点P1の座標x1及び座標y1と、整数kとが入力手段に入力される入力処理、
（２）前記入力手段に入力された素数pと、元Aと、元Bと、座標x1と、座標y1と、整数kとを記憶手段に記憶する記憶処理、
（３）前記記憶手段から元Aと、元Bと、素数pとを読み出し、C演算手段でC=AB mod pを求めるC演算処理、
（４）前記C演算手段で求めたCをC記憶手段に記憶するC記憶処理、
（５）前記記憶手段から元Bと素数pとを読み出し、B2演算手段でB2 mod pを求めるB2演算処理、
（６）前記B2演算手段で求めたB2をB2記憶手段に記憶するB2記憶処理、
（７）前記記憶手段から座標x1と、元Bと、素数pとを読み出し、D0演算手段で、以下の式により、配列要素D0を求めるD0演算処理、
D0＝x1B mod p
（８）前記D0演算手段で求めた配列要素D0をD0記憶手段に記憶するD0記憶処理、
（９）前記記憶手段から座標y1と、素数pとを読み出し、E0演算手段で、以下の式により、配列要素E0を求めるE0演算処理、
E0= y1 mod p
（１０）前記E0演算手段で求めた配列要素E0をE0記憶手段に記憶するE0記憶処理、
（１１）前記記憶手段から座標x1と、元Aと、素数pとを読み出し、F0演算手段で、以下の式により、配列要素F0を求めるF0演算処理、
F0 = 1+x1(2A+3x1) mod p
（１２）前記F0演算手段で求めた配列要素F0をF0記憶手段に記憶するF0記憶処理、
（１３）i初期値設定手段により、i記憶手段に、変数iの初期値1が設定されるi初期値設定処理、
（１４）前記記憶手段から整数kを読み出し、前記i記憶手段から変数iを読み出し、iインクリメント手段により、変数iが整数kに達するまで変数iに順次1を加えて、前記i記憶手段に設定するiインクリメント処理、
（１５）前記i記憶手段に変数iが設定される度に、前記i記憶手段から変数iを読み出し、前記記憶手段から素数pを読み出し、前記C記憶手段からCを読み出し、読み出された変数ｉにより特定される配列要素Di-1と、配列要素E0からEi-1と、配列要素Fi-1とを読み出し、Di演算手段で、以下の式により、配列要素Diを求めるDi演算処理、
【数９】
0004479135.tif 000022
（１６）前記Di演算手段で求めた配列要素DiをDi記憶手段に記憶するDi記憶処理、
（１７）前記i記憶手段に変数1が設定された時、B2と、素数pと、配列要素D0とD1と、配列要素E0と、配列要素F0とを読み出し、E1演算手段で、以下の式により、配列要素E1を求めるE1演算処理、
E1 = -8B2E04+F0(4D0E02-D1) mod p
（１８）前記E1演算手段で求めた配列要素E1をE1記憶手段に記憶するE1記憶処理、
（１９）前記i記憶手段に変数iとして2以上が設定される度に、前記i記憶手段から変数iを読み出し、前記記憶手段から素数pを読み出し、読み出した変数iにより特定される配列要素Di-1とDiと、配列要素Ei-1と、配列要素Fi-1とを読み出し、Ei演算手段で、以下の式により、配列要素Eiを求めるEi演算処理、
Ei = -8Ei-14+Fi-1(4Di-1Ei-12-Di) mod p
（２０）前記Ei演算手段で求めた配列要素EiをEi記憶手段に記憶するEi記憶処理、
（２１）前記i記憶手段に変数iとしてｋ−１以下が設定される度に、前記i記憶手段から変数iを読み出し、前記C記憶手段からCを読み出し、前記B2記憶手段からB2を読み出し、前記記憶手段から素数pを読み出し、読み出した変数iにより特定される配列要素Diと、配列要素E0からEi-1とを読み出し、Fi演算手段で、以下の式により、配列要素Fiを求めるFi演算処理、
【数１０】
0004479135.tif 000023
（２２）前記Fi演算手段で求めた配列要素FiをFi記憶手段に記憶するFi記憶処理、
（２３）前記記憶手段から整数kと、素数pと、元Bとを読み出し、読み出した整数kにより特定される配列要素Dkと、配列要素E0からEk-1とを読み出し、x2k演算手段で、以下の式により、座標x2kを求めるx2k演算処理、
【数１１】
0004479135.tif 000024
（２４）前記記憶手段から整数kと、素数pを読み出し、前記B2記憶手段からB2を読み出し、読み出した整数kにより特定される配列要素E0からEkを読み出し、y2k演算手段で、以下の式により、座標y2kを求めるy2k演算処理、
【数１２】
0004479135.tif 000025
（２５）前記x2k演算手段で求めた座標x2kと、前記y2k演算手段で求めた座標y2kとを出力手段から出力する出力処理。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線上の点の演算を行う演算装置、演算方法および演算プログラムに関する。
【０００２】
【従来の技術】
従来の楕円曲線上の点の演算方法について説明する。従来のMontgomery型楕円曲線上の点の演算方法は、G.B.Agnew, R.C.Mullin, S.A.Vanstone著、“An Implementation of Elliptic Curve Cryptosystems Over F2155”、IEEE Journal on Selected Areas in Communications、vol.11、No.5 (1993)、pp 804-813に記載されている。また、楕円曲線を用いた暗号化方法については、岡本龍明、山本博資著、“現代暗号”、産業図書(1997)に記載されている。
【０００３】
まず本発明の技術的背景である公開鍵暗号、離散対数問題および楕円曲線について簡単に説明する。公開鍵暗号通信においては、利用者ごとに秘密鍵xと公開鍵yの組が用意され、秘密鍵xは、各利用者が秘密に保持しておく。公開鍵yは利用者自身以外の一般に公開する。利用者Bが利用者Aに秘密にデータを送りたい時は、利用者Bは利用者Aに対応する公開鍵yを用いてデータを暗号化する。この暗号文は、秘密鍵xを知る利用者Aにしか復号できない。
離散対数問題とは群G(加法が定義されているものとする)の２つの要素g1、g2に対して、g1= mg2を満たすようなmを求める問題である。群Gの要素の数が大きい場合、離散対数問題を解くことは、計算量的に非常に困難になることが知られている。この事実を利用して公開鍵暗号を設計することができる。
Montgomery型楕円曲線Eとは、By2 = x3 + Ax2 + x mod pと表される方程式である。楕円曲線上の有理点集合E(Fp)には加法が定義され、群となる。
【０００４】
図3は、従来のMontgomery型楕円曲線の演算方法を示すフローチャートである。図3は、Montgomery型楕円曲線において、アファイン座標系で2倍点を計算する方法を示すフローチャートである。図3において、まず楕円曲線(のパラメータ)と曲線上の点P1が入力される。S301はλを計算するステップ、S302はx2を計算するステップ、S303はy2を計算するステップであり、P1の2倍点P2が出力される。
【０００５】
次に動作を説明する。まずアファイン座標系における2倍点の計算方法を図3に基づいて説明する。素体Fp上の楕円曲線E: By2 = x3 + Ax2 + x mod pとE上の点P1=(x1,y1)がまず入力される。各ステップにおける演算は全て定義体Fp上の演算となる。この方法の演算量は、乗算5回、自乗算2回、逆元算1回である。
【０００６】
【発明が解決しようとする課題】
従来のMontgomery型楕円曲線の2倍点の計算方法は、以上のように構成されており、4倍点や8倍点、一般に2k倍点を直接計算する方法が与えられていない。従って、例えば4倍点を計算するためには、2倍算を2回繰り返さなければならず、演算量が多いという課題があった。特に、アファイン座標系における演算では、2倍算1回に対して定義体上の逆元算が1回必要である。一般に逆元算は乗算と比較して計算量が多い。
【０００７】
本発明の目的は、係る課題を解決するためになされたもので、2k倍点計算する時に、2倍算をk回繰り返すことなく直接計算し、高速な演算方法を得ることにある。
【０００８】
【課題を解決するための手段】
この発明に係る演算装置は、以下の式で表わされ、Montgomery型楕円曲線E上の点P1=（x1,y1)を、アファイン座標系において2k倍(kは2以上の整数)した点P2k=(x2k,y2k)を求める演算装置であって、以下の要素を有することを特徴とする。
E：By2 = x3 + Ax2 + x mod p
（１）素数pと、素体Fp上の元A及び元Bと、点P1の座標x1及び座標y1と、整数kとを入力する入力手段、
（２）入力された素数pと、元Aと、元Bと、座標x1と、座標y1と、整数kとを記憶する記憶手段、
（３）元Aと、元Bと、素数pとを読み出し、C=AB mod pを求めるC演算手段、
（４）求めたCを記憶するC記憶手段、
（５）元Bと素数pとを読み出し、B2 mod pを求めるB2演算手段、
（６）求めたB2を記憶するB2記憶手段、
（７）座標x1と、元Bと、素数pとを読み出し、以下の式により、配列要素D0を求めるD0演算手段、
D0＝x1B mod p
（８）求めた配列要素D0を記憶するD0記憶手段、
（９）座標y1と、素数pとを読み出し、以下の式により、配列要素E0を求めるE0演算手段、
E0= y1 mod p
（１０）求めた配列要素E0を記憶するE0記憶手段、
（１１）座標x1と、元Aと、素数pとを読み出し、以下の式により、配列要素F0を求めるF0演算手段、
F0 = 1+x1(2A+3x1) mod p
（１２）求めた配列要素F0を記憶するF0記憶手段、
（１３）変数iを記憶するi記憶手段、
（１４）i記憶手段に、変数iの初期値1を設定するi初期値設定手段、
（１５）整数kと、変数iとを読み出し、変数iが整数kに達するまで変数iに順次1を加えて、i記憶手段に設定するiインクリメント手段、
（１６）i記憶手段に変数iが設定される度に、変数iと、素数pと、Cとを読み出し、更に、読み出した変数ｉにより特定される配列要素Di-1と、配列要素E0からEi-1と、配列要素Fi-1とを読み出し、以下の式により、配列要素Diを求めるDi演算手段、
【数１３】
0004479135.tif 000002
（１７）求めた配列要素Diを記憶するDi記憶手段、
（１８）i記憶手段に変数1が設定された時、B2と、素数pと、配列要素D0とD1と、配列要素E0と、配列要素F0とを読み出し、以下の式により、配列要素E1を求めるE1演算手段、
E1 = -8B2E04+F0(4D0E02-D1) mod p
（１９）求めた配列要素E0を記憶するE0記憶手段、
（２０）i記憶手段に変数iが2以上に設定される度に、変数iと、素数pとを読み出し、更に読み出した変数iにより特定される配列要素Di-1とDiと、配列要素Ei-1と、配列要素Fi-1とを読み出し、以下の式により、配列要素Eiを求めるEi演算手段、
Ei = -8Ei-14+Fi-1(4Di-1Ei-12-Di) mod p
（２１）求めた配列要素Eiを記憶するEi記憶手段、
（２２）i記憶手段に変数iがｋ−１以下に設定される度に、変数iと、Cと、B2と、素数pとを読み出し、更に読み出した変数iにより特定される配列要素Diと、配列要素E0からEi-1とを読み出し、以下の式により、配列要素Fiを求めるFi演算手段、
【数１４】
0004479135.tif 000003
（２３）求めた配列要素Fiを記憶するFi記憶手段、
（２４）整数kと、素数pと、元Bとを読み出し、更に読み出した整数kにより特定される配列要素Dkと、配列要素E0からEk-1とを読み出し、以下の式により、座標x2kを求めるx2k演算手段、
【数１５】
0004479135.tif 000004
（２５）整数kと、素数pと、B2とを読み出し、更に読み出した整数kにより特定される配列要素E0からEkとを読み出し、以下の式により、座標y2kを求めるy2k演算手段、
【数１６】
0004479135.tif 000005
（２６）求めた座標x2kと、座標y2kとを出力する出力手段。
【０００９】
この発明に係る演算方法は、以下の式で表わされ、Montgomery型楕円曲線E上の点P1=(x1,y1)を、アファイン座標系において2k倍(kは2以上の整数)した点P2k=(x2k,y2k)を求める演算方法であって、以下の要素を有することを特徴とする。
E：By2＝x3＋Ax2＋x mod p
（１）素数pと、素体Fp上の元A及び元Bと、点P1の座標x1及び座標y1と、整数kとを入力する入力工程、
（２）入力された素数pと、元Aと、元Bと、座標x1と、座標y1と、整数kとを記憶する記憶工程、
（３）元Aと、元Bと、素数pとを読み出し、C=AB mod pを求めるC演算工程、
（４）求めたCを記憶するC記憶工程、
（５）元Bと素数pとを読み出し、B2 mod pを求めるB2演算工程、
（６）求めたB2を記憶するB2記憶工程、
（７）座標x1と、元Bと、素数pとを読み出し、以下の式により、配列要素D0を求めるD0演算工程、
D0＝x1B mod p
（８）求めた配列要素D0を記憶するD0記憶工程、
（９）座標y1と、素数pとを読み出し、以下の式により、配列要素E0を求めるE0演算工程、
E0= y1 mod p
（１０）求めた配列要素E0を記憶するE0記憶工程、
（１１）座標x1と、元Aと、素数pとを読み出し、以下の式により、配列要素F0を求めるF0演算工程、
F0 = 1+x1(2A+3x1) mod p
（１２）求めた配列要素F0を記憶するF0記憶工程、
（１３）変数iを記憶するi記憶工程、
（１４）i記憶手段に、変数iの初期値1を設定するi初期値設定工程、
（１５）整数kと、変数iとを読み出し、変数iが整数kに達するまで変数iに順次1を加えて、i記憶手段に設定するiインクリメント工程、
（１６）i記憶手段に変数iが設定される度に、変数iと、素数pと、Cとを読み出し、更に、読み出した変数ｉにより特定される配列要素Di-1と、配列要素E0からEi-1と、配列要素Fi-1とを読み出し、以下の式により、配列要素Diを求めるDi演算工程、
【数１７】
0004479135.tif 000006
（１７）求めた配列要素Diを記憶するDi記憶工程、
（１８）i記憶手段に変数1が設定された時、B2と、素数pと、配列要素D0とD1と、配列要素E0と、配列要素F0とを読み出し、以下の式により、配列要素E1を求めるE1演算工程、
E1 = -8B2E04+F0(4D0E02-D1) mod p
（１９）求めた配列要素E0を記憶するE0記憶工程、
（２０）i記憶手段に変数iが2以上に設定される度に、変数iと、素数pとを読み出し、更に読み出した変数iにより特定される配列要素Di-1とDiと、配列要素Ei-1と、配列要素Fi-1とを読み出し、以下の式により、配列要素Eiを求めるEi演算工程、
Ei = -8Ei-14+Fi-1(4Di-1Ei-12-Di) mod p
（２１）求めた配列要素Eiを記憶するEi記憶工程、
（２２）i記憶手段に変数iがｋ−１以下に設定される度に、変数iと、Cと、B2と、素数pとを読み出し、更に読み出した変数iにより特定される配列要素Diと、配列要素E0からEi-1とを読み出し、以下の式により、配列要素Fiを求めるFi演算工程、
【数１８】
0004479135.tif 000007
（２３）求めた配列要素Fiを記憶するFi記憶工程、
（２４）整数kと、素数pと、元Bとを読み出し、更に読み出した整数kにより特定される配列要素Dkと、配列要素E0からEk-1とを読み出し、以下の式により、座標x2kを求めるx2k演算工程、
【数１９】
0004479135.tif 000008
（２５）整数kと、素数pと、B2とを読み出し、更に読み出した整数kにより特定される配列要素E0からEkとを読み出し、以下の式により、座標y2kを求めるy2k演算工程、
【数２０】
0004479135.tif 000009
（２６）求めた座標x2kと、座標y2kとを出力する出力工程。
【００１０】
この発明に係るプログラムは、以下の式で表わされ、Montgomery型楕円曲線E上の点P1=(x1,y1)を、アファイン座標系において2k倍(kは2以上の整数)した点P2k=(x2k,y2k)を求める演算装置となるコンピュータに、以下の処理を実行させるためのプログラムであることを特徴とする。
E：By2＝x3＋Ax2＋x mod p
（１）素数pと、素体Fp上の元A及び元Bと、点P1の座標x1及び座標y1と、整数kとを入力する入力処理、
（２）入力された素数pと、元Aと、元Bと、座標x1と、座標y1と、整数kとを記憶する記憶処理、
（３）元Aと、元Bと、素数pとを読み出し、C=AB mod pを求めるC演算処理、
（４）求めたCを記憶するC記憶処理、
（５）元Bと素数pとを読み出し、B2 mod pを求めるB2演算処理、
（６）求めたB2を記憶するB2記憶処理、
（７）座標x1と、元Bと、素数pとを読み出し、以下の式により、配列要素D0を求めるD0演算処理、
D0＝x1B mod p
（８）求めた配列要素D0を記憶するD0記憶処理、
（９）座標y1と、素数pとを読み出し、以下の式により、配列要素E0を求めるE0演算処理、
E0= y1 mod p
（１０）求めた配列要素E0を記憶するE0記憶処理、
（１１）座標x1と、元Aと、素数pとを読み出し、以下の式により、配列要素F0を求めるF0演算処理、
F0 = 1+x1(2A+3x1) mod p
（１２）求めた配列要素F0を記憶するF0記憶処理、
（１３）変数iを記憶するi記憶処理、
（１４）i記憶手段に、変数iの初期値1を設定するi初期値設定処理、
（１５）整数kと、変数iとを読み出し、変数iが整数kに達するまで変数iに順次1を加えて、i記憶手段に設定するiインクリメント処理、
（１６）i記憶手段に変数iが設定される度に、変数iと、素数pと、Cとを読み出し、更に、読み出した変数ｉにより特定される配列要素Di-1と、配列要素E0からEi-1と、配列要素Fi-1とを読み出し、以下の式により、配列要素Diを求めるDi演算処理、
【数２１】
0004479135.tif 000010
（１７）求めた配列要素Diを記憶するDi記憶処理、
（１８）i記憶手段に変数1が設定された時、B2と、素数pと、配列要素D0とD1と、配列要素E0と、配列要素F0とを読み出し、以下の式により、配列要素E1を求めるE1演算処理、
E1 = -8B2E04+F0(4D0E02-D1) mod p
（１９）求めた配列要素E0を記憶するE0記憶処理、
（２０）i記憶手段に変数iが2以上に設定される度に、変数iと、素数pとを読み出し、更に読み出した変数iにより特定される配列要素Di-1とDiと、配列要素Ei-1と、配列要素Fi-1とを読み出し、以下の式により、配列要素Eiを求めるEi演算処理、
Ei = -8Ei-14+Fi-1(4Di-1Ei-12-Di) mod p
（２１）求めた配列要素Eiを記憶するEi記憶処理、
（２２）i記憶手段に変数iがｋ−１以下に設定される度に、変数iと、Cと、B2と、素数pとを読み出し、更に読み出した変数iにより特定される配列要素Diと、配列要素E0からEi-1とを読み出し、以下の式により、配列要素Fiを求めるFi演算処理、
【数２２】
0004479135.tif 000011
（２３）求めた配列要素Fiを記憶するFi記憶処理、
（２４）整数kと、素数pと、元Bとを読み出し、更に読み出した整数kにより特定される配列要素Dkと、配列要素E0からEk-1とを読み出し、以下の式により、座標x2kを求めるx2k演算処理、
【数２３】
0004479135.tif 000012
（２５）整数kと、素数pと、B2とを読み出し、更に読み出した整数kにより特定される配列要素E0からEkとを読み出し、以下の式により、座標y2kを求めるy2k演算処理、
【数２４】
0004479135.tif 000013
（２６）求めた座標x2kと、座標y2kとを出力する出力処理。
【００１１】
【発明の実施の形態】
実施の形態１．
図1は、実施の形態1におけるMontgomery型楕円曲線の、アファイン座標系における2k倍点の演算方法を示したフローチャートである。図において、まず楕円曲線(のパラメータ)と曲線上の点P1が入力される。S101はC、B2を演算するステップ、S102はD0、E0、F0を計算するステップ、S103は1≦i≦kに対してDi、Eiを、1≦i≦k-1に対してFiを演算するステップ、S104はx2k、y2kを演算するステップであり、P1のk倍点P2kが出力される。
【００１２】
次に動作を説明する。まず、160ビット程度の大きな素数pと、有限体Fp上の2つの元A、Bを選択する。その際、楕円曲線の有理点群E(Fp)の位数＃E(Fp)が大きな素数で割り切れるようにp、A、Bを選択する。以上によりMontgomery型楕円曲線E：By2 = x3 + Ax2 + x mod pが選択されたことになる。この楕円曲線Eと、E上の点P1=(x1,y1)を入力し、P1の2k倍点P2k=(x2k,y2k)を演算する。図の各ステップにおける演算は全て定義体Fp上の演算となる。この方法の演算量は、乗算8k+4回、自乗算4k-1回、逆元算1回である。
【００１３】
以上のように演算すれば、定義体上の逆元演算を1回行うだけで、2k倍点を計算することができ、高速に計算できる。尚、従来の演算方法では、2倍算をk回繰り返していたために、逆元演算がk回必要であった。
【００１４】
本演算方法を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００１５】
実施の形態２．
図2は、実施の形態2によるMontgomery型楕円曲線のアファイン座標系における2k倍点の演算装置を示した図である。本実施の形態における演算装置は、実施の形態1における演算方法を用いた装置である。図において、201は入力手段、202は記憶手段、203は法pでの乗算手段、204は法pでの自乗算手段、205は法pでの加算手段、206は法pでの減算手段、207は法pでの単精度整数との乗算手段、208は法pでの逆元算手段、209と210と211と212は演算手段、213は出力手段、214は装置全体を制御する制御手段である。202はメモリ、203〜212及び214はＣＰＵである。
【００１６】
次に動作を説明する。まず、Montgomery型楕円曲線Eのパラメータ(160ビット程度の大きな素数pと、有限体Fp上の2つの元A、B)と、E上の点P1=(x1,y1)と、正整数kが入力手段201に入力される。その際、楕円曲線の有理点群E(Fp)の位数＃E(Fp)が大きな素数で割り切れるようにp、A、Bはあらかじめ選択されている。この装置では、点P1=(x1,y1)の2k倍点P2k=(x2k,y2k)が演算される。
【００１７】
まず、演算手段209において、C、B2が演算される。各演算において、乗算は法p乗算手段203、自乗算は法p自乗算手段204、を用いて演算される。演算されたC、B2は、記憶手段202に記憶される。
【００１８】
次に、演算手段210において、D0、E0、F0が演算される。各演算において、乗算は法p乗算手段203、加算は法p加算手段205、整数2および3との乗算は法p単精度乗算手段207を用いて演算される。演算されたD0、E0、F0は、記憶手段202に記憶される。
【００１９】
次に、演算手段211において、Di、Ei、Fiが、i=1からkの順に演算される。ただしFiは、i=kの時は計算されない。Di、Ei、Fiを演算する際、Di-1、Ei-1、Fi-1を適宜記憶手段202から読み出して演算する。また、演算されたDi、Ei、Fiは、記憶手段202に記憶される。また、各演算において、法p乗算手段203、法p自乗算手段204、法p加算手段205、法p減算手段206、法p単精度演算手段207が使用される。演算手段211において最終的に演算されたDk、Ekは、記憶手段202に記憶される。
【００２０】
次に、演算手段212において、x2k、y2kが演算される。これまでと同様、各演算では、203〜207が使用される。なお、法pでの逆元は、法p逆元算手段208を用いて演算される。本装置において法p逆元算手段208が使用されるのは、この1回だけである。
【００２１】
最後に、演算されたx2k、y2kは出力手段213から出力される。
【００２２】
以上のようにx2k、y2kを演算すれば、定義体上Fpの逆元演算を1回行うだけで、2k倍点を演算することができ、高速に計算できる。尚、従来の演算方法では、2倍算をk回繰り返していたために、逆元演算がk回必要であった。
【００２３】
本演算装置を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００２４】
各実施の形態に関し、入力処理、記憶処理、読み出し処理、演算処理、初期値設定処理、出力処理等の処理を、コンピュータ読み取り可能なプログラムとして記録媒体に記録し、演算装置となるコンピュータがそのプログラムを読み取り、プログラムを記憶するメモリにロードし、プログラムに含まれる処理を順次読み出し実行することにより実現することが可能である。
また、入力手段、及び出力手段は、モジュールのインターフェースとして用いられる記憶手段であっても構わない。
【００２５】
【発明の効果】
以上のように、本発明による演算方法は、楕円曲線演算を高速に行うことができる。
また、本発明による演算方法を利用することにより、楕円曲線を用いた暗号化やディジタル署名を高速に行うことができる。
【００２６】
以上のようにx2k、y2kを演算すれば、定義体上Fpの逆元演算を1回行うだけで、2k倍点を演算することができ、高速に計算できる。尚、従来の演算方法では、2倍算をk回繰り返していたために、逆元演算がk回必要であった。
【図面の簡単な説明】
【図１】  本発明の演算方法を説明するフローチャートである。
【図２】  本発明の演算装置を説明する図である。
【図３】  従来の演算方法を説明するフローチャートである。
【符号の説明】
２０１  入力手段、２０２  記憶手段、２０３  法ｐ乗算手段、２０４  法ｐ自乗算手段、２０５  法ｐ加算手段、２０６  法ｐ減算手段、２０７  法ｐ単精度乗算手段、２０８  法ｐ逆元算手段、２０９，２１０，２１１，２１２  演算手段、２１３  出力手段、２１４  制御手段。
【図１】
0004479135.tif 000026
【図２】
0004479135.tif 000027
【図３】
0004479135.tif 000028