JP4550232B2

JP4550232B2 - Arithmetic apparatus, arithmetic method, and computer-readable recording medium recording program

Info

Publication number: JP4550232B2
Application number: JP2000205635A
Authority: JP
Inventors: 康行酒井; 幸一櫻井
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 2000-07-06
Filing date: 2000-07-06
Publication date: 2010-09-22
Anticipated expiration: 2020-07-06
Also published as: JP2002023630A

Description

【０００１】
【発明の属する技術分野】
本発明は、楕円曲線上の点の演算方法およびそれを用いた暗号化方法に関する。
【０００２】
【従来の技術】
従来の楕円曲線上の点の演算方法について説明する。従来の楕円曲線上の点の演算方法は、Ｋｏｂｌｉｔｚ著、“ＡＣｏｕｒｓｅｉｎＮｕｍｂｅｒＴｈｅｏｒｙａｎｄＣｒｙｐｔｏｇｒａｐｈｙ”、ｓｐｒｉｎｇｅｒ、（１９９４）に記載されている。また、楕円曲線を用いた暗号化方法については、岡本龍明、山本博資著、“現代暗号”、産業図書（１９９７）に記載されている。
【０００３】
まず本発明の技術的背景である公開鍵暗号、離散対数問題および楕円曲線について簡単に説明する。公開鍵暗号通信においては、利用者ごとに秘密鍵ｘと公開鍵ｙの組が用意され、秘密鍵ｘは、各利用者が秘密に保持しておく。公開鍵ｙは利用者自身以外の一般に公開する。利用者Ｂが利用者Ａに秘密にデータを送りたい時は、利用者Ｂは利用者Ａに対応する公開鍵ｙを用いてデータを暗号化する。
この暗号文は、秘密鍵ｘを知る利用者Ａにしか復号できない。
離散対数問題とは群Ｇ（加法が定義されているものとする）の２つの要素ｇ₁，ｇ₂に対して、ｇ₁＝ｍｇ₂を満たすようなｍを求める問題である。群Ｇの要素の数が大きい場合、離散対数問題を解くことは、計算量的に非常に困難になることが知られている。この事実を利用して公開鍵暗号を設計することができる。
素体Ｆ_p上の楕円曲線Ｅとは、ｙ²＝ｘ³＋ａｘ＋ｂｍｏｄｐと表される方程式である。楕円曲線上の有理点集合Ｅ（Ｆ_p）には加法が定義され、群となる。
【０００４】
図５、図６は、従来の楕円曲線の演算方法を示すフローチャートである。図５は、素体上定義された楕円曲線において、アファイン座標系で２倍点を計算する方法、図６は、素体上定義された楕円曲線において、重み付き射影座標系で２倍点を計算する方法を示すフローチャートである。図５において、まず楕円曲線（のパラメータ）と曲線上の点Ｐ₁が入力される。Ｓ５０１はλを計算するステップ、Ｓ５０２はｘ₂を計算するステップ、Ｓ５０３はｙ₂を計算するステップであり、Ｐ₁の２倍点Ｐ₂が出力される。図６において、まず楕円曲線（のパラメータ）と曲線上の点Ｐ₁が入力される。Ｓ６０１はＭを計算するステップ、Ｓ６０２はＺ₂を計算するステップ、Ｓ６０３はＳを計算するステップ、Ｓ６０４はＸ₂を計算するステップ、Ｓ６０５はＴを計算するステップ、Ｓ６０６はＹ₂を計算するステップであり、Ｐ₁の２倍点Ｐ₂が出力される。
【０００５】
次に動作を説明する。まずアファイン座標系における２倍点の計算方法を図５に基づいて説明する。素体Ｆ_p上の楕円曲線Ｅ：ｙ²＝ｘ³＋ａｘ＋ｂｍｏｄｐとＥ上の点Ｐ₁＝（ｘ₁，ｙ₁）がまず入力される。各ステップにおける演算は全て定義体Ｆ_p上の演算となる。この方法の演算量は、自乗算２回、乗算２回、逆元算１回である。
次に重み付き射影座標系における２倍点の計算方法を図６に基づいて説明する。素体Ｆ_p上の楕円曲線Ｅ：ｙ²＝ｘ³＋ａｘ＋ｂｍｏｄｐとＥ上の点Ｐ₁＝（Ｘ₁，Ｙ₁，Ｚ₁）がまず入力される。各ステップにおける演算は全て定義体Ｆ_p上の演算となる。この方法の演算量は、自乗算６回、乗算４回である。
【０００６】
【発明が解決しようとする課題】
従来の素体Ｆ_p上の楕円曲線の２倍点の計算方法は、以上のように構成されており、４倍点や８倍点、一般に２^k倍点を直接計算する方法が与えられていない。従って、例えば４倍点を計算するためには、２倍算を２回繰り返さなければならず、演算量が多いという課題があった。特に、アファイン座標系における演算では、２倍算１回に対して定義体上の逆元算が１回必要である。一般に逆元算は乗算と比較して計算量が多い。
【０００７】
本発明の目的は、係る課題を解決するためになされたもので、２^k倍点計算する時に、２倍算をｋ回繰り返すことなく直接計算し、高速な演算方法を得ることにある。
【０００８】
【課題を解決するための手段】
この発明に係る演算装置は、以下の式で表わされ、素体Ｆ_p上定義された楕円曲線Ｅ上の点Ｐ₁＝（ｘ₁，ｙ₁）を、アファイン座標系において２^k倍（ｋは２以上の整数）した点Ｐ₂ ^k＝（ｘ₂ ^k，ｙ₂ ^k）を求める演算装置であって、以下の要素を有することを特徴とする。
Ｅ：ｙ²＝ｘ³＋ａｘ＋ｂｍｏｄｐ
（１）素数ｐと、素体Ｆ_p上の元ａ及び元ｂと、点Ｐ₁の座標ｘ₁及び座標ｙ₁と、整数ｋとを入力する入力手段、
（２）入力された素数ｐと、元ａと、元ｂと、座標ｘ₁と、座標ｙ₁と、整数ｋとを記憶する記憶手段、
（３）座標ｘ₁と、素数ｐとを読み出し、以下の式により、配列要素Ａ₁を求めるＡ₁演算手段、
Ａ₁＝ｘ₁ ｍｏｄｐ
（４）求めた配列要素Ａ₁を記憶するＡ₁記憶手段、
（５）座標ｘ₁と、元ａと、素数ｐとを読み出し、以下の式により、配列要素Ｂ₁を求めるＢ₁演算手段、
Ｂ₁＝３ｘ₁ ²＋ａｍｏｄｐ
（６）求めた配列要素Ｂ₁を記憶するＢ₁記憶手段、
（７）座標ｙ₁と、素数ｐとを読み出し、以下の式により、配列要素Ｃ₁を求めるＣ₁演算手段、
Ｃ₁＝−ｙ₁ ｍｏｄｐ
（８）求めた配列要素Ｃ₁を記憶するＣ₁記憶手段、
（９）変数ｉを記憶するｉ記憶手段、
（１０）ｉ記憶手段に、変数ｉの初期値２を設定するｉ初期値設定手段、
（１１）整数ｋと、変数ｉとを読み出し、変数ｉが整数ｋに達するまで変数ｉに順次１を加えて、ｉ記憶手段に設定するｉインクリメント手段、
（１２）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、素数ｐとを読み出し、更に、読み出した変数ｉにより特定される配列要素Ａ_i-1と、配列要素Ｂ_i-1と、配列要素Ｃ_i-1とを読み出し、以下の式により、配列要素Ａ_iを求めるＡ_i演算手段、
Ａ_i＝Ｂ_i-1 ²−８Ａ_i-1Ｃ_i-1 ² ｍｏｄｐ
（１３）求めた配列要素Ａ_iを記憶するＡ_i記憶手段、
（１４）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、元ａと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａ_iと、配列要素Ｃ₁からＣ_i-1を読み出し、以下の式により、配列要素Ｂ_iを求めるＢ_i演算手段、
【数１０】

（１５）求めた配列要素Ｂ_iを記憶するＢ_i記憶手段、
（１６）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａ_iとＡ_i-1と、配列要素Ｂ_i-1と、配列要素Ｃ_i-1とを読み出し、以下の式により、配列要素Ｃ_iを求めるＣ_i演算手段、
Ｃ_i＝−８Ｃ_i-1 ⁴−Ｂ_i-1（Ａ_i−４Ａ_i-1Ｃ_i-1 ²）ｍｏｄｐ
（１７）求めた配列要素Ｃ_iを記憶するＣ_i記憶手段、
（１８）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａ_kと、配列要素Ｂ_kと、配列要素Ｃ_kとを読み出し、以下の式により、数値Ｄ_kを求めるＤ_k演算手段、
Ｄ_k＝１２Ａ_kＣ_k ²−Ｂ_k ² ｍｏｄｐ
（１９）求めた数値Ｄｋを記憶するＤｋ記憶手段、
（２０）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａ_kと、配列要素Ｂ_kと、配列要素Ｃ₁からＣ_kとを読み出し、以下の式により、座標ｘ₂ ^kを求めるｘ₂ ^k演算手段、
【数１１】

（２１）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ｂ_kと、配列要素Ｃ₁からＣ_kと、配列要素Ｄ_kとを読み出し、以下の式により、座標ｙ₂ ^kを求めるｙ₂ ^k演算手段、
【数１２】

（２２）求めた座標ｘ₂ ^kと、座標ｙ₂ ^kとを出力する出力手段。
【０００９】
この発明に係る演算装置は、以下の式で表わされ、素体Ｆ_p上定義された楕円曲線Ｅ上の点Ｐ₁＝（Ｘ₁，Ｙ₁，Ｚ₁）を、重み付き射影座標系において４倍した点Ｐ₄＝（Ｘ₄，Ｙ₄，Ｚ₄）を求める演算装置であって、以下の要素を有することを特徴とする。
Ｅ：ｙ²＝ｘ³＋ａｘ＋ｂｍｏｄｐ
（１）素数ｐと、素体Ｆ_p上の元ａ及び元ｂと、点Ｐ₁の座標Ｘ₁、座標Ｙ₁及び座標Ｚ₁とを入力する入力手段、
（２）入力された素数ｐと、元ａと、元ｂと、座標Ｘ₁と、座標Ｙ₁と、座標Ｚ₁とを記憶する記憶手段、
（３）元ａと、座標Ｘ₁と、座標Ｚ₁と、素数ｐとを読み出し、以下の式により、数値Ａを求めるＡ演算手段、
Ａ＝３Ｘ₁ ²＋ａＺ₁ ⁴ ｍｏｄｐ
（４）求めた数値Ａを記憶するＡ記憶手段、
（５）数値Ａと、座標Ｘ₁と、座標Ｙ₁と、素数ｐとを読み出し、以下の式により、数値Ｂを求めるＢ演算手段、
Ｂ＝Ａ²−８Ｘ₁Ｙ₁ ² ｍｏｄｐ
（６）求めた数値Ｂを記憶するＢ記憶手段、
（７）数値Ａと、座標Ｘ₁と、座標Ｙ₁と、素数ｐとを読み出し、以下の式により、数値Ｃを求めるＣ演算手段、
Ｃ＝−８Ｙ₁ ⁴＋Ａ（１２Ｘ₁Ｙ₁ ²−Ａ²）ｍｏｄｐ
（８）求めた数値Ｃを記憶するＣ記憶手段、
（９）元ａと、数値Ｂと、座標Ｙ₁と、座標Ｚ₁と、素数ｐとを読み出し、以下の式により、数値Ｄを求めるＤ演算手段、
Ｄ＝１６ａＹ₁ ⁴Ｚ₁ ⁴＋３Ｂ² ｍｏｄｐ
（１０）求めた数値Ｄを記憶するＤ記憶手段、
（１１）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐとを読み出し、以下の式により、座標Ｘ₄を求めるＸ₄演算手段、
Ｘ₄＝−８ＢＣ²＋Ｄ² ｍｏｄｐ
（１２）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐを読み出し、以下の式により、座標Ｙ₄を求めるＹ₄演算手段、
Ｙ₄＝−８Ｃ⁴＋Ｄ（１２ＢＣ²−Ｄ²）ｍｏｄｐ
（１３）座標Ｙ₁と、座標Ｚ₁と、数値Ｃと、素数ｐとを読み出し、以下の式により、座標Ｚ₄を求めるＺ₄演算手段、
Ｚ₄＝４Ｙ₁Ｚ₁Ｃｍｏｄｐ
（１４）求めた座標Ｘ₄と、座標Ｙ₄と、座標Ｚ₄を出力する出力手段。
【００１０】
この発明に係る演算方法は、以下の式で表わされ、素体Ｆ_p上定義された楕円曲線Ｅ上の点Ｐ₁＝（ｘ₁，ｙ₁）を、アファイン座標系において２^k倍（ｋは２以上の整数）した点Ｐ₂ ^k＝（ｘ₂ ^k，ｙ₂ ^k）を求める演算方法であって、以下の要素を有することを特徴とする。
Ｅ：ｙ²＝ｘ³＋ａｘ＋ｂｍｏｄｐ
（１）素数ｐと、素体Ｆ_p上の元ａ及び元ｂと、点Ｐ₁の座標ｘ₁及び座標ｙ₁と、整数ｋとを入力する入力工程、
（２）入力された素数ｐと、元ａと、元ｂと、座標ｘ₁と、座標ｙ₁と、整数ｋとを記憶する記憶工程、
（３）座標ｘ₁と、素数ｐとを読み出し、以下の式により、配列要素Ａ₁を求めるＡ₁演算工程、
Ａ₁＝ｘ₁ ｍｏｄｐ
（４）求めた配列要素Ａ₁を記憶するＡ₁記憶工程、
（５）座標ｘ₁と、元ａと、素数ｐとを読み出し、以下の式により、配列要素Ｂ₁を求めるＢ₁演算工程、
Ｂ₁＝３ｘ₁ ²＋ａｍｏｄｐ
（６）求めた配列要素Ｂ₁を記憶するＢ₁記憶工程、
（７）座標ｙ₁と、素数ｐとを読み出し、以下の式により、配列要素Ｃ₁を求めるＣ₁演算工程、
Ｃ₁＝−ｙ₁ ｍｏｄｐ
（８）求めた配列要素Ｃ₁を記憶するＣ₁記憶工程、
（９）変数ｉの初期値２を設定するｉ初期値設定工程、
（１０）整数ｋと、変数ｉとを読み出し、変数ｉが整数ｋに達するまで変数ｉに順次１を加えて、設定するｉインクリメント工程、
（１１）変数ｉが設定される度に、変数ｉと、素数ｐとを読み出し、更に、読み出した変数ｉにより特定される配列要素Ａ_i-1と、配列要素Ｂ_i-1と、配列要素Ｃ_i-1とを読み出し、以下の式により、配列要素Ａ_iを求めるＡ_i演算工程、
Ａ_i＝Ｂ_i-1 ²−８Ａ_i-1Ｃ_i-1 ² ｍｏｄｐ
（１２）求めた配列要素Ａ_iを記憶するＡ_i記憶工程、
（１３）変数ｉが設定される度に、変数ｉと、元ａと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａ_iと、配列要素Ｃ₁からＣ_i-1を読み出し、以下の式により、配列要素Ｂ_iを求めるＢ_i演算工程、
【数１３】

（１４）求めた配列要素Ｂ_iを記憶するＢ_i記憶工程、
（１５）変数ｉが設定される度に、変数ｉと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａ_iとＡ_i-1と、配列要素Ｂ_i-1と、配列要素Ｃ_i-1とを読み出し、以下の式により、配列要素Ｃ_iを求めるＣ_i演算工程、
Ｃ_i＝−８Ｃ_i-1 ⁴−Ｂ_i-1（Ａ_i−４Ａ_i-1Ｃ_i-1 ²）ｍｏｄｐ
（１６）求めた配列要素Ｃ_iを記憶するＣ_i記憶工程、
（１７）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａ_kと、配列要素Ｂ_kと、配列要素Ｃ_kとを読み出し、以下の式により、数値Ｄ_kを求めるＤ_k演算工程、
Ｄ_k＝１２Ａ_kＣ_k ²−Ｂ_k ² ｍｏｄｐ
（１８）求めた数値Ｄｋを記憶するＤｋ記憶工程、
（１９）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａ_kと、配列要素Ｂ_kと、配列要素Ｃ₁からＣ_kとを読み出し、以下の式により、座標ｘ₂ ^kを求めるｘ₂ ^k演算工程、
【数１４】

（２０）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ｂ_kと、配列要素Ｃ₁からＣ_kと、配列要素Ｄ_kとを読み出し、以下の式により、座標ｙ₂ ^kを求めるｙ₂ ^k演算工程、
【数１５】

（２１）求めた座標ｘ₂ ^kと、座標ｙ₂ ^kとを出力する出力工程。
【００１１】
この発明に係る演算方法は、以下の式で表わされ、素体Ｆ_p上定義された楕円曲線Ｅ上の点Ｐ₁＝（Ｘ₁，Ｙ₁，Ｚ₁）を、重み付き射影座標系において４倍した点Ｐ₄＝（Ｘ₄，Ｙ₄，Ｚ₄）を求める演算方法であって、以下の要素を有することを特徴とする。
Ｅ：ｙ²＝ｘ³＋ａｘ＋ｂｍｏｄｐ
（１）素数ｐと、素体Ｆ_p上の元ａ及び元ｂと、点Ｐ₁の座標Ｘ₁、座標Ｙ₁及び座標Ｚ₁とを入力する入力工程、
（２）入力された素数ｐと、元ａと、元ｂと、座標Ｘ₁と、座標Ｙ₁と、座標Ｚ₁とを記憶する記憶工程、
（３）元ａと、座標Ｘ₁と、座標Ｚ₁と、素数ｐとを読み出し、以下の式により、数値Ａを求めるＡ演算工程、
Ａ＝３Ｘ₁ ²＋ａＺ₁ ⁴ ｍｏｄｐ
（４）求めた数値Ａを記憶するＡ記憶工程、
（５）数値Ａと、座標Ｘ₁と、座標Ｙ₁と、素数ｐとを読み出し、以下の式により、数値Ｂを求めるＢ演算工程、
Ｂ＝Ａ²−８Ｘ₁Ｙ₁ ² ｍｏｄｐ
（６）求めた数値Ｂを記憶するＢ記憶工程、
（７）数値Ａと、座標Ｘ₁と、座標Ｙ₁と、素数ｐとを読み出し、以下の式により、数値Ｃを求めるＣ演算工程、
Ｃ＝−８Ｙ₁ ⁴＋Ａ（１２Ｘ₁Ｙ₁ ²−Ａ²）ｍｏｄｐ
（８）求めた数値Ｃを記憶するＣ記憶工程、
（９）元ａと、数値Ｂと、座標Ｙ₁と、座標Ｚ₁と、素数ｐとを読み出し、以下の式により、数値Ｄを求めるＤ演算工程、
Ｄ＝１６ａＹ₁ ⁴Ｚ₁ ⁴＋３Ｂ² ｍｏｄｐ
（１０）求めた数値Ｄを記憶するＤ記憶工程、
（１１）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐとを読み出し、以下の式により、座標Ｘ₄を求めるＸ₄演算工程、
Ｘ₄＝−８ＢＣ²＋Ｄ² ｍｏｄｐ
（１２）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐを読み出し、以下の式により、座標Ｙ₄を求めるＹ₄演算工程、
Ｙ₄＝−８Ｃ⁴＋Ｄ（１２ＢＣ²−Ｄ²）ｍｏｄｐ
（１３）座標Ｙ₁と、座標Ｚ₁と、数値Ｃと、素数ｐとを読み出し、以下の式により、座標Ｚ₄を求めるＺ₄演算工程、
Ｚ₄＝４Ｙ₁Ｚ₁Ｃｍｏｄｐ
（１４）求めた座標Ｘ₄と、座標Ｙ₄と、座標Ｚ₄を出力する出力工程。
【００１２】
この発明に係るプログラムを記録したコンピュータ読み取り可能な記録媒体は、以下の式で表わされ、素体Ｆ_p上定義された楕円曲線Ｅ上の点Ｐ₁＝（ｘ₁，ｙ₁）を、アファイン座標系において２^k倍（ｋは２以上の整数）した点Ｐ₂ ^k＝（ｘ₂ ^k，ｙ₂ ^k）を求める演算装置となるコンピュータに、以下の処理を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であることを特徴とする。
Ｅ：ｙ²＝ｘ³＋ａｘ＋ｂｍｏｄｐ
（１）素数ｐと、素体Ｆ_p上の元ａ及び元ｂと、点Ｐ₁の座標ｘ₁及び座標ｙ₁と、整数ｋとを入力する入力処理、
（２）入力された素数ｐと、元ａと、元ｂと、座標ｘ₁と、座標ｙ₁と、整数ｋとを記憶する記憶処理、
（３）座標ｘ₁と、素数ｐとを読み出し、以下の式により、配列要素Ａ₁を求めるＡ₁演算処理、
Ａ₁＝ｘ₁ ｍｏｄｐ
（４）求めた配列要素Ａ₁を記憶するＡ₁記憶処理、
（５）座標ｘ₁と、元ａと、素数ｐとを読み出し、以下の式により、配列要素Ｂ₁を求めるＢ₁演算処理、
Ｂ₁＝３ｘ₁ ²＋ａｍｏｄｐ
（６）求めた配列要素Ｂ₁を記憶するＢ₁記憶処理、
（７）座標ｙ₁と、素数ｐとを読み出し、以下の式により、配列要素Ｃ₁を求めるＣ₁演算処理、
Ｃ₁＝−ｙ₁ ｍｏｄｐ
（８）求めた配列要素Ｃ₁を記憶するＣ₁記憶処理、
（９）変数ｉの初期値２を設定するｉ初期値設定処理、
（１０）整数ｋと、変数ｉとを読み出し、変数ｉが整数ｋに達するまで変数ｉに順次１を加えて、設定するｉインクリメント処理、
（１１）変数ｉが設定される度に、変数ｉと、素数ｐとを読み出し、更に、読み出した変数ｉにより特定される配列要素Ａ_i-1と、配列要素Ｂ_i-1と、配列要素Ｃ_i-1とを読み出し、以下の式により、配列要素Ａ_iを求めるＡ_i演算処理、
Ａ_i＝Ｂ_i-1 ²−８Ａ_i-1Ｃ_i-1 ² ｍｏｄｐ
（１２）求めた配列要素Ａ_iを記憶するＡ_i記憶処理、
（１３）変数ｉが設定される度に、変数ｉと、元ａと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａ_iと、配列要素Ｃ₁からＣ_i-1を読み出し、以下の式により、配列要素Ｂ_iを求めるＢ_i演算処理、
【数１６】

（１４）求めた配列要素Ｂ_iを記憶するＢ_i記憶処理、
（１５）変数ｉが設定される度に、変数ｉと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａ_iとＡ_i-1と、配列要素Ｂ_i-1と、配列要素Ｃ_i-1とを読み出し、以下の式により、配列要素Ｃ_iを求めるＣ_i演算処理、
Ｃ_i＝−８Ｃ_i-1 ⁴−Ｂ_i-1（Ａ_i−４Ａ_i-1Ｃ_i-1 ²）ｍｏｄｐ
（１６）求めた配列要素Ｃ_iを記憶するＣ_i記憶処理、
（１７）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａ_kと、配列要素Ｂ_kと、配列要素Ｃ_kとを読み出し、以下の式により、数値Ｄ_kを求めるＤ_k演算処理、
Ｄ_k＝１２Ａ_kＣ_k ²−Ｂ_k ² ｍｏｄｐ
（１８）求めた数値Ｄｋを記憶するＤｋ記憶処理、
（１９）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａ_kと、配列要素Ｂ_kと、配列要素Ｃ₁からＣ_kとを読み出し、以下の式により、座標ｘ₂ ^kを求めるｘ₂ ^k演算処理、
【数１７】

（２０）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ｂ_kと、配列要素Ｃ₁からＣ_kと、配列要素Ｄ_kとを読み出し、以下の式により、座標ｙ₂ ^kを求めるｙ₂ ^k演算処理、
【数１８】

（２１）求めた座標ｘ₂ ^kと、座標ｙ₂ ^kとを出力する出力処理。
【００１３】
この発明に係るプログラムを記録したコンピュータ読み取り可能な記録媒体は、以下の式で表わされ、素体Ｆ_p上定義された楕円曲線Ｅ上の点Ｐ₁＝（Ｘ₁，Ｙ₁，Ｚ₁）を、重み付き射影座標系において４倍した点Ｐ₄＝（Ｘ₄，Ｙ₄，Ｚ₄）を求める演算装置となるコンピュータに、以下の処理を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であることを特徴とする。
Ｅ：ｙ²＝ｘ³＋ａｘ＋ｂｍｏｄｐ
（１）素数ｐと、素体Ｆ_p上の元ａ及び元ｂと、点Ｐ₁の座標Ｘ₁、座標Ｙ₁及び座標Ｚ₁とを入力する入力処理、
（２）入力された素数ｐと、元ａと、元ｂと、座標Ｘ₁と、座標Ｙ₁と、座標Ｚ₁とを記憶する記憶処理、
（３）元ａと、座標Ｘ₁と、座標Ｚ₁と、素数ｐとを読み出し、以下の式により、数値Ａを求めるＡ演算処理、
Ａ＝３Ｘ₁ ²＋ａＺ₁ ⁴ ｍｏｄｐ
（４）求めた数値Ａを記憶するＡ記憶処理、
（５）数値Ａと、座標Ｘ₁と、座標Ｙ₁と、素数ｐとを読み出し、以下の式により、数値Ｂを求めるＢ演算処理、
Ｂ＝Ａ²−８Ｘ₁Ｙ₁ ² ｍｏｄｐ
（６）求めた数値Ｂを記憶するＢ記憶処理、
（７）数値Ａと、座標Ｘ₁と、座標Ｙ₁と、素数ｐとを読み出し、以下の式により、数値Ｃを求めるＣ演算処理、
Ｃ＝−８Ｙ₁ ⁴＋Ａ（１２Ｘ₁Ｙ₁ ²−Ａ²）ｍｏｄｐ
（８）求めた数値Ｃを記憶するＣ記憶処理、
（９）元ａと、数値Ｂと、座標Ｙ₁と、座標Ｚ₁と、素数ｐとを読み出し、以下の式により、数値Ｄを求めるＤ演算処理、
Ｄ＝１６ａＹ₁ ⁴Ｚ₁ ⁴＋３Ｂ² ｍｏｄｐ
（１０）求めた数値Ｄを記憶するＤ記憶処理、
（１１）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐとを読み出し、以下の式により、座標Ｘ₄を求めるＸ₄演算処理、
Ｘ₄＝−８ＢＣ²＋Ｄ² ｍｏｄｐ
（１２）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐを読み出し、以下の式により、座標Ｙ₄を求めるＹ₄演算処理、
Ｙ₄＝−８Ｃ⁴＋Ｄ（１２ＢＣ²−Ｄ²）ｍｏｄｐ
（１３）座標Ｙ₁と、座標Ｚ₁と、数値Ｃと、素数ｐとを読み出し、以下の式により、座標Ｚ₄を求めるＺ₄演算処理、
Ｚ₄＝４Ｙ₁Ｚ₁Ｃｍｏｄｐ
（１４）求めた座標Ｘ₄と、座標Ｙ₄と、座標Ｚ₄を出力する出力処理。
【００１４】
【発明の実施の形態】
実施の形態１．
図１は、実施の形態１における素体上定義された楕円曲線の、アファイン座標系における２^k倍点の演算方法を示したフローチャートである。図において、まず楕円曲線（のパラメータ）と曲線上の点Ｐ₁が入力される。Ｓ１０１はＡ₁、Ｂ₁、Ｃ₁を演算するステップ、Ｓ１０２は２≦ｉ≦ｋに対してＡ_i、Ｂ_i、Ｃ_iを演算するステップ、Ｓ１０３はＤ_kを演算するステップ、Ｓ１０４はｘ₂ ^k、ｙ₂ ^kを演算するステップであり、Ｐ₁のｋ倍点Ｐ₂ ^kが出力される。
【００１５】
次に動作を説明する。まず、１６０ビット程度の大きな素数ｐと、有限体Ｆ_p上の２つの元ａ、ｂを選択する。その際、楕円曲線の有理点群Ｅ（Ｆ_p）の位数＃Ｅ（Ｆ_p）が大きな素数で割り切れるようにｐ、ａ、ｂを選択する。以上により楕円曲線Ｅ：ｙ²＝ｘ³＋ａｘ＋ｂｍｏｄｐが選択されたことになる。この楕円曲線Ｅと、Ｅ上の点Ｐ₁＝（ｘ₁，ｙ₁）を入力し、Ｐ₁の２^k倍点Ｐ₂ ^k＝（ｘ₂ ^k，ｙ₂ ^k）を演算する。図の各ステップにおける演算は全て定義体Ｆ_p上の演算となる。この方法の演算量は、自乗算４ｋ＋１回、乗算４ｋ＋２回、逆元算１回である。
【００１６】
以上のように演算すれば、定義体上の逆元演算を１回行うだけで、２^k倍点を計算することができ、高速に計算できる。尚、従来の演算方法では、２倍算をｋ回繰り返していたために、逆元演算がｋ回必要であった。
【００１７】
本演算方法を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００１８】
実施の形態２．
図２は、実施の形態２における素体上定義された楕円曲線の重み付き射影座標系における４倍点の演算方法を示したフローチャートである。図において、まず楕円曲線（のパラメータ）と曲線上の点Ｐ₁が入力される。Ｓ２０１はＡ、Ｂ、Ｃ、Ｄを演算するステップ、Ｓ２０２はＸ₄、Ｙ₄、Ｚ₄を演算するステップであり、Ｐ₁の４倍点Ｐ₄が出力される。
【００１９】
次に動作を説明する。まず、１６０ビット程度の大きな素数ｐと、有限体Ｆ_p上の２つの元ａ，ｂを選択する。その際、楕円曲線の有理点群Ｅ（Ｆ_p）の位数＃Ｅ（Ｆ_p）が大きな素数で割り切れるようにｐ、ａ、ｂを選択する。以上により楕円曲線Ｅ：ｙ²＝ｘ³＋ａｘ＋ｂｍｏｄｐが選択されたことになる。この楕円曲線Ｅと、Ｅ上の点Ｐ₁＝（Ｘ₁，Ｙ₁，Ｚ₁）を入力し、Ｐ₁の４倍点Ｐ₄＝（ｘ₄，ｙ₄）を演算する。図の各ステップにおける演算は全て定義体Ｆ_p上の演算となる。この方法の演算量は、自乗算１０回、乗算９回である。
【００２０】
従来の演算方法では、４倍点を計算するために２倍算を２回繰り返していたため、自乗算１２回、乗算８回の演算が必要であった。したがって、本発明の演算方法の方が高速に演算できる。
【００２１】
本演算方法を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００２２】
実施の形態３．
図３は、実施の形態３による素体上定義された楕円曲線のアファイン座標系における２^k倍点の演算装置を示した図である。本実施の形態における演算装置は、実施の形態１における演算方法を用いた装置である。図において、３０１は入力手段、３０２は記憶手段、３０３は法ｐでの乗算手段、３０４は法ｐでの自乗算手段、３０５は法ｐでの加算手段、３０６は法ｐでの減算手段、３０７は法ｐでの単精度整数との乗算手段、３０８は法ｐでの逆元算手段、３０９と３１０と３１１と３１２は演算手段、３１３は出力手段、３１４は装置全体を制御する制御手段である。３０２はメモリ、３０３〜３１２及び３１４はＣＰＵである。
【００２３】
次に動作を説明する。まず、楕円曲線Ｅのパラメータ（１６０ビット程度の大きな素数ｐと、有限体Ｆ_p上の２つの元ａ、ｂ）と、Ｅ上の点Ｐ₁＝（ｘ₁，ｙ₁）と、正整数ｋが入力手段３０１に入力される。その際、楕円曲線の有理点群Ｅ（Ｆ_p）の位数＃Ｅ（Ｆ_p）が大きな素数で割り切れるようにｐ、ａ、ｂはあらかじめ選択されている。この装置では、点Ｐ₁＝（ｘ₁，ｙ₁）の２^k倍点Ｐ₂ ^k＝（ｘ₂ ^k，ｙ₂ ^k）が演算される。
【００２４】
まず、演算手段３０９において、Ａ₁、Ｂ₁、Ｃ₁が演算される。各演算において、自乗算は法ｐ自乗算手段３０４、加算は法ｐ加算手段３０５、減算は法ｐ減算手段３０６、整数３との乗算は法ｐ単精度乗算手段３０７を用いて演算される。演算されたＡ₁、Ｂ₁、Ｃ₁は、記憶手段３０２に記憶される。
【００２５】
次に、演算手段３１０において、Ａ_i、Ｂ_i、Ｃ_iが、ｉ＝２からｋの順に演算される。Ａ_j、Ｂ_j、Ｃ_jを演算する際、Ａ_j-1、Ｂ_j-1、Ｃ_j-1を適宜記憶手段３０２から読み出して演算する。また、演算されたＡ_j、Ｂ_j、Ｃ_jは、記憶手段３０２に記憶される。また、各演算において、法ｐ乗算手段３０３、法ｐ自乗算手段３０４、法ｐ加算手段３０５、法ｐ減算手段３０６、法ｐ単精度演算手段３０７が使用される。演算手段３１０において最終的に演算されたＡ_k、Ｂ_k、Ｃ_kは、記憶手段３０２に記憶される。
【００２６】
次に、演算手段３１１において、Ｄ_kが演算される。Ａ_k、Ｂ_k、Ｃ_kは記憶手段３０２から読み出され、整数“１２”との乗算は法ｐ単精度乗算手段３０７が使用され、乗算は法ｐ乗算手段３０３が使用され、自乗算は法ｐ自乗算手段３０４が使用され、減算は法ｐ減算手段３０６が使用される。演算されたＤ_kは記憶手段３０２に記憶される。
【００２７】
次に、演算手段３１２において、ｘ₂ ^k、ｙ₂ ^kが演算される。これまでと同様、各演算では、３０３〜３０７が使用される。なお、ｋΠ^k _i=1Ｃ_iの法ｐでの逆元は、法ｐ逆元算手段３０８を用いて演算される。本装置において法ｐ逆元算手段３０８が使用されるのは、この１回だけである。
【００２８】
最後に、演算されたｘ₂ ^k、ｙ₂ ^kは出力手段３１３から出力される。
【００２９】
以上のようにｘ₂ ^k、ｙ₂ ^kを演算すれば、定義体上Ｆ_pの逆元演算を１回行うだけで、２^k倍点を演算することができ、高速に計算できる。尚、従来の演算方法では、２倍算をｋ回繰り返していたために、逆元演算がｋ回必要であった。
【００３０】
本演算装置を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００３１】
実施の形態４．
図４は、実施の形態４による素体上定義された楕円曲線の重み付き射影座標系における４倍点の演算装置を示した図である。本実施の形態における演算装置は、実施の形態２における演算方法を用いた装置である。図において、４０１は入力手段、４０２は記憶手段、４０３は法ｐでの乗算手段、４０４は法ｐでの自乗算手段、４０５は法ｐでの加算手段、４０６は法ｐでの減算手段、４０７は法ｐでの単精度整数との乗算手段、４０８と４０９は演算手段、４１０は出力手段、４１１は装置全体を制御する制御手段である。４０２はメモリ、４０３〜４０９及び４１１はＣＰＵである。
【００３２】
次に動作を説明する。まず、楕円曲線Ｅのパラメータ（１６０ビット程度の大きな素数ｐと、有限体Ｆ_p上の２つの元ａ、ｂ）と、Ｅ上の点Ｐ₁＝（Ｘ₁，Ｙ₁，Ｚ₁）が入力手段４０１に入力される。その際、楕円曲線の有理点群Ｅ（Ｆ_p）の位数＃Ｅ（Ｆ_p）が大きな素数で割り切れるようにｐ、ａ、ｂはあらかじめ選択されている。この装置では、点Ｐ₁＝（Ｘ₁，Ｙ₁，Ｚ₁）の４倍点Ｐ₄＝（Ｘ₄，Ｙ₄，Ｚ₄）が演算される。
【００３３】
まず、演算手段４０８において、Ａ、Ｂ、Ｃ、Ｄが演算される。各演算において、乗算は法ｐ乗算手段４０３、自乗算は法ｐ自乗算手段４０４、加算は法ｐ加算手段４０５、減算は法ｐ減算手段４０６、単精度整数との乗算は法ｐ単精度乗算手段４０７を用いて演算される。演算されたＡ、Ｂ、Ｃ、Ｄは、記憶手段４０２に記憶される。
【００３４】
次に、演算手段４０９において、Ｘ₄、Ｙ₄、Ｚ₄が演算される。演算する際、Ａ、Ｂ、Ｃ、Ｄを適宜記憶手段４０２から読み出して演算する。また、各演算において、乗算は法ｐ乗算手段４０３、自乗算は法ｐ自乗算手段４０４、加算は法ｐ加算手段４０５、減算は法ｐ減算手段４０６、単精度整数との乗算は法ｐ単精度乗算手段４０７を用いて演算される。
【００３５】
最後に、演算されたＸ₄、Ｙ₄、Ｚ₄は出力手段４１０から出力される。
【００３６】
以上のように演算すれば、法ｐによる自乗算１０回、乗算９回で４倍点が計算できる。尚、従来の演算方法では、４倍点を計算するために２倍算を２回繰り返していたため、自乗算１２回、乗算８回の演算が必要であった。したがって、本発明の演算方法の方が高速に計算できる。
【００３７】
本演算装置を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００３８】
各実施の形態に関し、入力処理、記憶処理、読み出し処理、演算処理、初期値設定処理、出力処理等の処理を、コンピュータ読み取り可能なプログラムとして記録媒体に記録し、演算装置となるコンピュータがそのプログラムを読み取り、プログラムを記憶するメモリにロードし、プログラムに含まれる処理を順次読み出し実行することにより実現することが可能である。
また、入力手段、及び出力手段は、モジュールのインターフェースとして用いられる記憶手段であっても構わない。
【００３９】
【発明の効果】
以上のように、本発明による演算方法は、楕円曲線演算を高速に行うことができる。
また、本発明による演算方法を利用することにより、楕円曲線を用いた暗号化やディジタル署名を高速に行うことができる。
【００４０】
以上のようにｘ₂ ^k、ｙ₂ ^kを演算すれば、定義体上Ｆ_pの逆元演算を１回行うだけで、２^k倍点を演算することができ、高速に計算できる。尚、従来の演算方法では、２倍算をｋ回繰り返していたために、逆元演算がｋ回必要であった。
【００４１】
以上のように演算すれば、法ｐによる自乗算１０回、乗算９回で４倍点が計算できる。尚、従来の演算方法では、４倍点を計算するために２倍算を２回繰り返していたため、自乗算１２回、乗算８回の演算が必要であった。したがって、本発明の演算方法の方が高速に計算できる。
【図面の簡単な説明】
【図１】本発明の演算方法を説明するフローチャートである。
【図２】本発明の演算方法を説明するフローチャートである。
【図３】本発明の演算装置を説明する図である。
【図４】本発明の演算装置を説明する図である。
【図５】従来の演算方法を説明するフローチャートである。
【図６】従来の演算方法を説明するフローチャートである。
【符号の説明】
３０１，４０１入力手段、３０２，４０２記憶手段、３０３，４０３法ｐ乗算手段、３０４，４０４法ｐ自乗算手段、３０５，４０５法ｐ加算手段、３０６，４０６法ｐ減算手段、３０７，４０７法ｐ単精度乗算手段、３０８法ｐ逆元算手段、３０９，３１０，３１１，３１２，４０８，４０９演算手段、３１３，４１０出力手段、３１４，４１１制御手段。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a method for calculating points on an elliptic curve and an encryption method using the same.
[0002]
[Prior art]
A conventional method for calculating points on an elliptic curve will be described. A conventional method for calculating points on an elliptic curve is described by Koblitz, “A Course in Number Theory and Cryptography”, Springer, (1994). The encryption method using an elliptic curve is described in Tatsuaki Okamoto and Hiroshi Yamamoto, “Modern Crypto”, Sangyo Tosho (1997).
[0003]
First, public key cryptography, discrete logarithm problem and elliptic curve, which are the technical background of the present invention, will be briefly described. In public key encryption communication, a set of a secret key x and a public key y is prepared for each user, and the secret key x is kept secret by each user. The public key y is disclosed to the public other than the user himself. When user B wants to secretly send data to user A, user B encrypts the data using public key y corresponding to user A.
This ciphertext can only be decrypted by the user A who knows the secret key x.
For discrete two elements g ₁ of the logarithmic group problematic G (additive is assumed to be defined), g _2, a problem of finding the m that satisfies g ₁ = mg _2. It is known that when the number of elements of the group G is large, solving the discrete logarithm problem becomes very difficult in terms of computational complexity. Public key cryptography can be designed using this fact.
The elliptic curve E on the element body F _p is an equation expressed as y ² = x ³ + ax + b mod p. An addition is defined for the rational point set E (F _p ) on the elliptic curve to form a group.
[0004]
5 and 6 are flowcharts showing a conventional elliptic curve calculation method. FIG. 5 shows a method for calculating a double point in an affine coordinate system in an elliptic curve defined on a prime field, and FIG. 6 shows a double point in a weighted projective coordinate system in an elliptic curve defined on a prime field. It is a flowchart which shows the method to calculate. In FIG. 5, first, an elliptic curve (parameter thereof) and a point P ₁ on the curve are input. S501 is a step of calculating a lambda, S502 step of calculating x _2, S503 is a step of calculating y _2, 2-fold point P ₂ of P ₁ is output. In FIG. 6, first, an elliptic curve (parameter thereof) and a point P ₁ on the curve are input. S601 is a step of calculating M, the step of calculating the Z ₂ S602, step of calculating step, the step of calculating X ₂ S604, the step of calculating the T S605, S606 and the Y ₂ to calculate the S S603 And a double point P ₂ of P ₁ is output.
[0005]
Next, the operation will be described. First, a method of calculating the double point in the affine coordinate system will be described with reference to FIG. Elliptic curve E on element F _p : y ² = x ³ + ax + b mod p and point P ₁ = (x ₁ , y ₁ ) on E are first input. All operations in each step are operations on the definition field F _p . The calculation amount of this method is two times self-multiplication, two multiplications, and one inverse element calculation.
Next, a method for calculating the double point in the weighted projection coordinate system will be described with reference to FIG. Elliptic curve over a prime field _{^{F p E: y 2 = x}} 3 + ax + b mod p and P ₁ = a point on _{_{E (X 1, Y 1,}} Z 1) is first entered. All operations in each step are operations on the definition field F _p . The amount of calculation in this method is 6 times self multiplication and 4 times multiplication.
[0006]
[Problems to be solved by the invention]
Calculation of double points of an elliptic curve over a conventional prime field F _p is configured as described above, 4-multiplied point and 8-fold point, we have generally given way to calculate the 2 ^k times point directly Absent. Therefore, for example, in order to calculate a quadruple point, the doubling must be repeated twice, and there is a problem that the amount of calculation is large. In particular, in the calculation in the affine coordinate system, one inverse operation on the definition field is required for one doubling. In general, the inverse element calculation is more computationally intensive than the multiplication.
[0007]
An object of the present invention is to solve such a problem, and is to obtain a high-speed calculation method by directly calculating a doubling without repeating k times when calculating 2 ^k times.
[0008]
[Means for Solving the Problems]
The arithmetic unit according to the present invention is expressed by the following equation, and a point P ₁ = (x ₁ , y ₁ ) on the elliptic curve E defined on the prime field F _p is multiplied by 2 ^k ( k is an arithmetic unit for obtaining a point P ₂ ^k = (x ₂ ^k , y ₂ ^k ), which is an integer of 2 or more, and has the following elements.
E: y ² = x ³ + ax + b mod p
(1) Input means for inputting prime number p, element a and element b on prime field F _p , coordinate x ₁ and coordinate y _{1 of} point P ₁ , and integer k
(2) storage means for storing the input prime number p, element a, element b, coordinate x ₁ , coordinate y ₁ , and integer k;
(3) A ₁ calculation means for reading out the coordinate x ₁ and the prime number p and obtaining the array element A ₁ by the following equation:
A ₁ = x ₁ mod p
(4) A ₁ storage means for storing the obtained array element A ₁ ;
(5) B ₁ calculation means for reading the coordinate x ₁ , the element a, and the prime number p, and obtaining the array element B ₁ by the following equation:
B ₁ = 3x ₁ ² + a mod p
(6) B ₁ storage means for storing the obtained array element B ₁ ;
(7) C ₁ calculation means for reading the coordinate y ₁ and the prime number p and obtaining the array element C ₁ by the following equation:
C ₁ = −y ₁ mod p
(8) C ₁ storage means for storing the obtained array element C ₁ ;
(9) i storage means for storing variable i,
(10) i initial value setting means for setting the initial value 2 of the variable i in the i storage means;
(11) i increment means for reading integer k and variable i, sequentially adding 1 to variable i until variable i reaches integer k, and setting in i storage means;
(12) Each time the variable i is set in the i storage means, the variable i and the prime number p are read, and the array element A _i-1 specified by the read variable i and the array element B _i-1 When reads out the array element C _i-1, by the following equation, a _i arithmetic means for obtaining the array element a _i,
A _i = B _i-1 ² -8A _i-1 C _i-1 ² mod p
(13) A _i storage means for storing the obtained array element A _i ;
(14) Each time the variable i is set in the i storage means, the variable i, the element a, and the prime number P are read, and the array element A _i specified by the read variable _i and the array element C ₁ B _i computing means for reading C _i-1 and obtaining the array element B _i by the following equation:
[Expression 10]

(15) B _i storing means for storing the array elements B _i determined,
(16) Each time the variable i is set in the i storage means, the variable i and the prime number P are read, and the array elements A _i and A _i-1 and the array element B _i specified by the read variable i are read. _-1 and array element C _i-1 , C _i computing means for obtaining array element C _i by the following equation:
C _i = −8 C _i _-1 ⁴ -B _i-1 (A _i -4A _i-1 C _i-1 ² ) mod p
(17) C _i storage means for storing the obtained array element C _i ;
(18) Read integer k and prime number P, read array element A _k , array element B _k , and array element C _k specified by the read integer _k , and calculate numerical value D _k by the following equation: D _k computing means for obtaining
D _k = 12A _k C _k ² −B _k ² mod p
(19) Dk storage means for storing the obtained numerical value Dk,
(20) Read the integer k and the prime number P, and further read the array element A _k , the array element B _k, and the array elements C ₁ to C _k specified by the read integer k. X ₂ ^k computing means for obtaining coordinates x ₂ ^k ;
[Expression 11]

(21) Read integer k and prime number P, read array element B _k specified by read integer k, array elements C ₁ to C _k , and array element D _k, and Y ₂ ^k computing means for obtaining coordinates y ₂ ^k ;
[Expression 12]

(22) Output means for outputting the obtained coordinates x ₂ ^k and coordinates y ₂ ^k .
[0009]
The arithmetic unit according to the present invention is expressed by the following formula, and a point P ₁ = (X ₁ , Y ₁ , Z ₁ ) on the elliptic curve E defined on the prime field F _p is represented by a weighted projective coordinate system. Is a computing device for obtaining a point P ₄ = (X ₄ , Y ₄ , Z ₄ ) multiplied by ₄ and has the following elements.
E: y ² = x ³ + ax + b mod p
(1) Input means for inputting the prime number p, the _elements a and b on the prime field F _p , the coordinates X ₁ , the coordinates Y ₁ and the coordinates Z _{1 of} the point P ₁ ;
(2) storage means for storing the input prime number p, element a, element b, coordinate X ₁ , coordinate Y ₁ , and coordinate Z ₁ ;
(3) A calculation means for reading the element a, the coordinate X ₁ , the coordinate Z _1, and the prime number p, and obtaining the numerical value A by the following equation:
A = 3X ₁ ² + aZ ₁ ⁴ mod p
(4) A storage means for storing the obtained numerical value A,
(5) B calculation means for reading the numerical value A, the coordinate X ₁ , the coordinate Y _1, and the prime number p, and obtaining the numerical value B by the following equation:
B = A ² -8X ₁ Y ₁ ² mod p
(6) B storage means for storing the obtained numerical value B,
(7) C calculating means for reading the numerical value A, the coordinate X ₁ , the coordinate Y ₁ and the prime number p, and obtaining the numerical value C by the following equation:
C = −8Y ₁ ⁴ + A (12X ₁ Y ₁ ² −A ² ) mod p
(8) C storage means for storing the obtained numerical value C;
(9) D calculation means for reading the element a, the numerical value B, the coordinate Y ₁ , the coordinate Z _1, and the prime number p, and obtaining the numerical value D by the following equation:
D = 16aY ₁ ⁴ Z ₁ ⁴ + 3B ² mod p
(10) D storage means for storing the obtained numerical value D,
(11) X ₄ calculation means for reading the numerical value B, the numerical value C, the numerical value D, and the prime number p, and obtaining the coordinate X ₄ by the following equation:
X ₄ = −8BC ² + D ² mod p
(12) Y ₄ calculation means for reading the numerical value B, the numerical value C, the numerical value D, and the prime number p, and obtaining the coordinate Y ₄ by the following equation:
Y ₄ = −8C ⁴ + D (12BC ² −D ² ) mod p
(13) Z ₄ computing means for reading the coordinate Y ₁ , the coordinate Z ₁ , the numerical value C, and the prime number p, and obtaining the coordinate Z ₄ by the following equation:
Z ₄ = 4Y ₁ Z ₁ C mod p
(14) An output means for outputting the obtained coordinates X ₄ , coordinates Y ₄ , and coordinates Z ₄ .
[0010]
Calculation method according to the present invention is represented by the following formula, the element point F on the _p on an elliptic curve defined _{_{E P 1 = (x 1,}} y 1), 2 k times in affine coordinates ( k is an arithmetic method for obtaining a point P ₂ ^k = (x ₂ ^k , y ₂ ^k ), which is an integer of 2 or more, and has the following elements.
E: y ² = x ³ + ax + b mod p
(1) an input step of inputting a prime number p, _elements a and b on the prime field F _p , coordinates x ₁ and coordinates y _{1 of the} point P ₁ , and an integer k;
(2) a storage step of storing the input prime number p, element a, element b, coordinate x ₁ , coordinate y ₁ , and integer k;
(3) A ₁ calculation step of reading the coordinate x ₁ and the prime number p and obtaining the array element A ₁ by the following formula:
A ₁ = x ₁ mod p
(4) A ₁ storage step for storing the obtained array element A ₁ ;
(5) B ₁ calculation step of reading the coordinate x ₁ , the element a, and the prime number p, and obtaining the array element B ₁ by the following equation:
B ₁ = 3x ₁ ² + a mod p
(6) B ₁ storage step for storing the obtained array element B ₁ ;
(7) C ₁ calculation step of reading out the coordinate y ₁ and the prime number p and obtaining the array element C ₁ by the following equation:
C ₁ = −y ₁ mod p
(8) a C ₁ storage step for storing the obtained array element C ₁ ;
(9) i initial value setting step for setting initial value 2 of variable i;
(10) i increment step for reading integer k and variable i, sequentially adding 1 to variable i until variable i reaches integer k, and setting
(11) Each time the variable i is set, the variable i and the prime number p are read, and the array element A _i-1 , the array element B _i-1, and the array element specified by the read variable i are read. C _i-1 is read, and an A _i calculation step for obtaining an array element A _i by the following equation:
A _i = B _i-1 ² -8A _i-1 C _i-1 ² mod p
(12) A _i storing step of storing the obtained array element A _i ;
(13) Each time the variable i is set, the variable i, the element a, and the prime number P are read, and the array element A _i specified by the read variable _i and the array elements C ₁ to C _i-1 B _i calculation step for obtaining the array element B _i by the following equation:
[Formula 13]

(14) B _i storage step of storing the obtained array element B _i ,
(15) Each time the variable i is set, the variable i and the prime number P are read, and the array elements A _i and A _i-1 specified by the read variable i, the array element B _i-1 , C _i calculation step for reading array element C _i-1 and obtaining array element C _i by the following equation:
C _i = −8 C _i _-1 ⁴ -B _i-1 (A _i -4A _i-1 C _i-1 ² ) mod p
(16) C _i storage step for storing the obtained array element C _i ,
(17) Read integer k and prime number P, read array element A _k , array element B _k , and array element C _k specified by the read integer _k , and calculate numerical value D _k by the following equation D _k calculation step for obtaining
D _k = 12A _k C _k ² −B _k ² mod p
(18) A Dk storage step for storing the obtained numerical value Dk,
(19) Read integer k and prime number P, and further read array element A _k , array element B _k , and array elements C ₁ to C _k specified by the read integer k. X ₂ ^k calculation step for obtaining coordinates x ₂ ^k ;
[Expression 14]

(20) Read the integer k and the prime number P, and further read the array element B _k specified by the read integer k, the array elements C ₁ to C _k, and the array element D _k . Y ₂ ^k calculation step for obtaining coordinates y ₂ ^k ,
[Expression 15]

(21) An output step of outputting the obtained coordinates x ₂ ^k and coordinates y ₂ ^k .
[0011]
The calculation method according to the present invention is expressed by the following equation, and a point P ₁ = (X ₁ , Y ₁ , Z ₁ ) on the elliptic curve E defined on the prime field F _p is represented by a weighted projective coordinate system. Is a calculation method for obtaining the point P ₄ = (X ₄ , Y ₄ , Z ₄ ) multiplied by ₄ in which the following elements are included.
E: y ² = x ³ + ax + b mod p
(1) An input step of inputting the prime number p, the _elements a and b on the prime field F _p , the coordinates X ₁ , the coordinates Y ₁ and the coordinates Z _{1 of} the point P ₁ .
(2) A storage step of storing the input prime number p, element a, element b, coordinate X ₁ , coordinate Y ₁ , and coordinate Z ₁ ;
(3) An A operation step of reading the element a, the coordinate X ₁ , the coordinate Z _1, and the prime number p, and obtaining a numerical value A by the following equation:
A = 3X ₁ ² + aZ ₁ ⁴ mod p
(4) A storage step for storing the obtained numerical value A,
(5) A numerical value A, a coordinate X ₁ , a coordinate Y _1, and a prime number p are read, and a B operation step for obtaining the numerical value B by the following equation:
B = A ² -8X ₁ Y ₁ ² mod p
(6) B storage step for storing the obtained numerical value B,
(7) A numerical value A, a coordinate X ₁ , a coordinate Y _1, and a prime number p are read out, and a C operation step for obtaining the numerical value C by the following equation:
C = −8Y ₁ ⁴ + A (12X ₁ Y ₁ ² −A ² ) mod p
(8) C storing step for storing the obtained numerical value C,
(9) A D operation step of reading the element a, the numerical value B, the coordinate Y ₁ , the coordinate Z _1, and the prime number p, and obtaining the numerical value D by the following equation:
D = 16aY ₁ ⁴ Z ₁ ⁴ + 3B ² mod p
(10) D storage step for storing the obtained numerical value D,
(11) A numerical value B, a numerical value C, a numerical value D, and a prime number p are read, and an X ₄ calculation step for obtaining a coordinate X ₄ by the following equation:
X ₄ = −8BC ² + D ² mod p
(12) Y ₄ calculation step of reading the numerical value B, the numerical value C, the numerical value D, and the prime number p, and obtaining the coordinate Y ₄ by the following equation:
Y ₄ = −8C ⁴ + D (12BC ² −D ² ) mod p
(13) A Z ₄ calculation step of reading the coordinate Y ₁ , the coordinate Z ₁ , the numerical value C, and the prime number p, and obtaining the coordinate Z ₄ by the following equation:
Z ₄ = 4Y ₁ Z ₁ C mod p
(14) An output step of outputting the obtained coordinates X ₄ , coordinates Y ₄ , and coordinates Z ₄ .
[0012]
A computer-readable recording medium on which the program according to the present invention is recorded is represented by the following formula, and a point P ₁ = (x ₁ , y ₁ ) on the elliptic curve E defined on the elementary field F _p is expressed as follows: A program for executing the following processing is recorded in a computer that is a computing device for obtaining a point P ₂ ^k = (x ₂ ^k , y ₂ ^k ) multiplied by 2 ^k (k is an integer of 2 or more) in the affine coordinate system It is a computer-readable recording medium.
E: y ² = x ³ + ax + b mod p
(1) Input processing for inputting prime number p, element a and element b on prime field F _p , coordinate x ₁ and coordinate y _{1 of} point P ₁ , and integer k
(2) a prime number p that is input, the original a, the original b, or coordinates x _1, a coordinate y _1, the storage process of storing the integer k,
(3) the coordinates x _1, reads the prime p, the following equation, A ₁ arithmetic processing for obtaining the array element A _1,
A ₁ = x ₁ mod p
(4) A ₁ storage process for storing the obtained array element A ₁ ;
(5) Read out the coordinate x ₁ , the element a, and the prime number p, and perform B ₁ calculation processing to obtain the array element B ₁ by the following equation:
B ₁ = 3x ₁ ² + a mod p
(6) B ₁ storage processing for storing the obtained array element B ₁ ;
(7) C ₁ arithmetic processing for reading the coordinate y ₁ and the prime number p and obtaining the array element C ₁ by the following equation:
C ₁ = −y ₁ mod p
(8) C ₁ storage processing for storing the obtained array element C ₁ ;
(9) i initial value setting processing for setting initial value 2 of variable i;
(10) i-increment processing for reading out the integer k and the variable i and sequentially adding 1 to the variable i until the variable i reaches the integer k.
(11) Each time the variable i is set, the variable i and the prime number p are read, and the array element A _i-1 , the array element B _i-1, and the array element specified by the read variable i are read. C _i-1 is read out, and A _i calculation processing for obtaining the array element A _i by the following equation:
A _i = B _i-1 ² -8A _i-1 C _i-1 ² mod p
(12) A _i storage process for storing the obtained array element A _i ;
(13) Each time the variable i is set, the variable i, the element a, and the prime number P are read, and the array element A _i specified by the read variable _i and the array elements C ₁ to C _i-1 B _i calculation processing for obtaining the array element B _i by the following equation:
[Expression 16]

(14) B _i storage processing for storing the obtained array element B _i ,
(15) Each time the variable i is set, the variable i and the prime number P are read, and the array elements A _i and A _i-1 specified by the read variable i, the array element B _i-1 , C _i arithmetic processing for reading the array element C _i-1 and obtaining the array element C _i by the following equation:
C _i = −8 C _i _-1 ⁴ -B _i-1 (A _i -4A _i-1 C _i-1 ² ) mod p
(16) C _i storage processing for storing the obtained array element C _i ;
(17) Read integer k and prime number P, read array element A _k , array element B _k , and array element C _k specified by the read integer _k , and calculate numerical value D _k by the following equation D _k calculation processing for obtaining
D _k = 12A _k C _k ² −B _k ² mod p
(18) Dk storage processing for storing the obtained numerical value Dk,
(19) Read integer k and prime number P, and further read array element A _k , array element B _k , and array elements C ₁ to C _k specified by the read integer k. X ₂ ^k calculation processing for obtaining coordinates x ₂ ^k ,
[Expression 17]

(20) Read the integer k and the prime number P, and further read the array element B _k specified by the read integer k, the array elements C ₁ to C _k, and the array element D _k . Y ₂ ^k calculation processing for obtaining coordinates y ₂ ^k ,
[Formula 18]

(21) Output processing for outputting the obtained coordinates x ₂ ^k and coordinates y ₂ ^k .
[0013]
A computer-readable recording medium storing a program according to the present invention is represented by the following formula, P _₁ = (X ₁ point on the defined elliptic curve E that the body F _p, Y _{_1,} Z ₁ ) Is multiplied by four in the weighted projective coordinate system, and the computer is a computer readable recording a program for executing the following processing on the computer that obtains the point P ₄ = (X ₄ , Y ₄ , Z ₄ ) It is a characteristic recording medium.
E: y ² = x ³ + ax + b mod p
(1) Input processing for inputting the prime number p, the _elements a and b on the prime field F _p , the coordinates X ₁ , the coordinates Y ₁ and the coordinates Z _{1 of} the point P ₁ .
(2) Storage processing for storing the input prime number p, element a, element b, coordinate X ₁ , coordinate Y ₁ , and coordinate Z ₁ .
(3) A calculation process for reading the element a, the coordinate X ₁ , the coordinate Z _1, and the prime number p, and obtaining the numerical value A by the following equation:
A = 3X ₁ ² + aZ ₁ ⁴ mod p
(4) A storage process for storing the obtained numerical value A,
(5) B calculation processing for reading the numerical value A, the coordinate X ₁ , the coordinate Y _1, and the prime number p and obtaining the numerical value B by the following equation:
B = A ² -8X ₁ Y ₁ ² mod p
(6) B storage processing for storing the obtained numerical value B,
(7) C arithmetic processing for reading the numerical value A, the coordinate X ₁ , the coordinate Y _1, and the prime number p, and obtaining the numerical value C by the following equation:
C = −8Y ₁ ⁴ + A (12X ₁ Y ₁ ² −A ² ) mod p
(8) C storage processing for storing the obtained numerical value C,
(9) Read out the element a, the numerical value B, the coordinate Y ₁ , the coordinate Z ₁ and the prime number p, and calculate the numerical value D by the following formula:
D = 16aY ₁ ⁴ Z ₁ ⁴ + 3B ² mod p
(10) D storage process for storing the obtained numerical value D;
(11) X ₄ arithmetic processing for reading the numerical value B, the numerical value C, the numerical value D, and the prime number p, and obtaining the coordinate X ₄ by the following equation:
X ₄ = −8BC ² + D ² mod p
(12) A numerical value B, a numerical value C, a numerical value D, and a prime number p are read, and a Y ₄ calculation process for obtaining a coordinate Y ₄ by the following equation:
Y ₄ = −8C ⁴ + D (12BC ² −D ² ) mod p
(13) Z ₄ arithmetic processing for reading the coordinate Y ₁ , the coordinate Z ₁ , the numerical value C, and the prime number p, and obtaining the coordinate Z ₄ by the following equation:
Z ₄ = 4Y ₁ Z ₁ C mod p
(14) Output processing for outputting the obtained coordinate X ₄ , coordinate Y ₄ , and coordinate Z ₄ .
[0014]
DETAILED DESCRIPTION OF THE INVENTION
Embodiment 1 FIG.
FIG. 1 is a flowchart showing a method of calculating a 2 ^k- fold point in an affine coordinate system for an elliptic curve defined on a prime field in the first embodiment. In the figure, first, an elliptic curve (parameter thereof) and a point P ₁ on the curve are input. S101 is a step of calculating A ₁ , B ₁ , and C ₁ , S102 is a step of calculating A _i , B _i , and C _i for 2 ≦ i ≦ k, S103 is a step of calculating D _k , and S104 is x _This is a step of calculating ₂ ^k and y ₂ ^k , and a k-fold point P ₂ ^{k of} P ₁ is output.
[0015]
Next, the operation will be described. First, a large prime number p of about 160 bits and two elements a and b on the finite field F _p are selected. At this time, p, a, and b are selected so that the order #E (F _p ) of the rational point group E (F _p ) of the elliptic curve is divisible by a large prime number. Thus, the elliptic curve E: y ² = x ³ + ax + b mod p is selected. And the elliptic curve E, and enter a point on _{_{E P 1 = (x 1,}} y 1), 2 k times point _{^{_{^{P 2 k = (x 2 k}}}} , y 2 k) of P ₁ calculates the. All operations in each step in the figure are operations on the definition field F _p . The calculation amount of this method is self-multiplication 4k + 1 times, multiplication 4k + 2 times, and inverse element calculation 1 time.
[0016]
If the calculation is performed as described above, the 2 ^k- fold point can be calculated by performing the inverse element calculation on the definition body once, and the calculation can be performed at high speed. In the conventional calculation method, since the doubling operation is repeated k times, the inverse element calculation is required k times.
[0017]
This calculation method can also be used for encryption using an elliptic curve and digital signature.
[0018]
Embodiment 2. FIG.
FIG. 2 is a flowchart showing a quadruple point calculation method in the weighted projection coordinate system of the elliptic curve defined on the prime field in the second embodiment. In the figure, first, an elliptic curve (parameter thereof) and a point P ₁ on the curve are input. S201 is A, B, C, step of computing D, S202 is a step of computing the _{_{_{X 4, Y 4, Z 4}}} , 4 times points P ₁ P ₄ is output.
[0019]
Next, the operation will be described. First, a large prime number p of about 160 bits and two elements a and b on the finite field F _p are selected. At this time, p, a, and b are selected so that the order #E (F _p ) of the rational point group E (F _p ) of the elliptic curve is divisible by a large prime number. Thus, the elliptic curve E: y ² = x ³ + ax + b mod p is selected. The elliptic curve E and a point P ₁ = (X ₁ , Y ₁ , Z ₁ ) on E are input, and a quadruple point P ₄ = (x ₄ , y ₄ ) of P ₁ is calculated. All operations in each step in the figure are operations on the definition field F _p . The amount of calculation in this method is 10 times self multiplication and 9 times multiplication.
[0020]
In the conventional calculation method, the doubling operation is repeated twice in order to calculate the quadruple point, so that it is necessary to perform the self-multiplication 12 times and the multiplication 8 times. Therefore, the calculation method of the present invention can calculate at higher speed.
[0021]
This calculation method can also be used for encryption using an elliptic curve and digital signature.
[0022]
Embodiment 3 FIG.
FIG. 3 is a diagram showing an arithmetic unit for 2 ^k- fold points in an affine coordinate system of an elliptic curve defined on a prime field according to the third embodiment. The arithmetic device in the present embodiment is a device using the arithmetic method in the first embodiment. In the figure, 301 is input means, 302 is storage means, 303 is multiplication means in modulus p, 304 is self-multiplication means in modulus p, 305 is addition means in modulus p, 306 is subtraction means in modulus p, 307 is a multiplication means with a single precision integer in modulus p, 308 is an inverse element calculation means in modulus p, 309, 310, 311 and 312 are calculation means, 313 is an output means, 314 is a control means for controlling the entire apparatus It is. Reference numeral 302 denotes a memory, and 303 to 312 and 314 are CPUs.
[0023]
Next, the operation will be described. First, parameters of the elliptic curve E (a large prime number p of about 160 bits, two elements a and b on the finite field F _p ), a point P ₁ = (x ₁ , y ₁ ) on E, and a positive integer k is input to the input means 301. At that time, p, a, and b are selected in advance so that the order #E (F _p ) of the rational point group E (F _p ) of the elliptic curve is divisible by a large prime number. In this apparatus, a point P ₂ ^k = (x ₂ ^k , y ₂ ^k ) that is 2 ^k times the point P ₁ = (x ₁ , y ₁ ) is calculated.
[0024]
First, the arithmetic unit _{_{309, A 1, B 1,}} C 1 is calculated. In each calculation, the self-multiplication is calculated using the modulus p self-multiplication means 304, the addition is calculated using the modulus p addition means 305, the subtraction is calculated using the modulus p subtraction means 306, and the multiplication with the integer 3 is calculated using the modulus p single-precision multiplication means 307. The calculated A ₁ , B ₁ , C ₁ are stored in the storage unit 302.
[0025]
Then, the arithmetic unit 310, A _i, B _i, is C _i, is computed from i = 2 in the order of k. When calculating A _j , B _j , and C _j , A _j−1 , B _j−1 , and C _j−1 are appropriately read from the storage unit 302 and calculated. The calculated A _j , B _j , and C _j are stored in the storage unit 302. Further, in each calculation, the modulus p multiplication means 303, the modulus p own multiplication means 304, the modulus p addition means 305, the modulus p subtraction means 306, and the modulus p single precision calculation means 307 are used. A _k , B _k , and C _k finally calculated by the calculation unit 310 are stored in the storage unit 302.
[0026]
Next, D _k is calculated in the calculation means 311. A _k , B _k , and C _k are read from the storage unit 302, the multiplication with the integer “12” is performed using the modulus p single precision multiplication unit 307, the multiplication is performed using the modulus p multiplication unit 303, The modulus p own multiplication means 304 is used, and the modulus p subtraction means 306 is used for subtraction. The calculated D _k is stored in the storage unit 302.
[0027]
Next, the calculation means 312 calculates x ₂ ^k and y ₂ ^k . As before, 303 to 307 are used in each calculation. Note that the inverse element in the modulus p of kΠ ^k _{i = 1} C _i is calculated using the modulus p inverse element calculation means 308. In this apparatus, the modulus p inverse element calculation means 308 is used only once.
[0028]
Finally, the calculated x ₂ ^k and y ₂ ^k are output from the output means 313.
[0029]
If x ₂ ^k and y ₂ ^k are calculated as described above, the 2 ^k times point can be calculated by performing the inverse element calculation of F _p on the definition body once, and can be calculated at high speed. In the conventional calculation method, since the doubling operation is repeated k times, the inverse element calculation is required k times.
[0030]
This computing device can also be used for encryption using an elliptic curve and for digital signatures.
[0031]
Embodiment 4 FIG.
FIG. 4 is a diagram showing an arithmetic unit for quadruple points in the weighted projection coordinate system of the elliptic curve defined on the prime field according to the fourth embodiment. The arithmetic device in the present embodiment is a device using the arithmetic method in the second embodiment. In the figure, 401 is input means, 402 is storage means, 403 is multiplication means in modulus p, 404 is self-multiplication means in modulus p, 405 is addition means in modulus p, 406 is subtraction means in modulus p, Reference numeral 407 denotes multiplication means for single precision integers in the modulus p, 408 and 409 denote arithmetic means, 410 denotes output means, and 411 denotes control means for controlling the entire apparatus. Reference numeral 402 denotes a memory, and reference numerals 403 to 409 and 411 denote CPUs.
[0032]
Next, the operation will be described. First, parameters of the elliptic curve E (a large prime number p of about 160 bits and two elements a and b on the finite field F _p ) and a point P ₁ = (X ₁ , Y ₁ , Z ₁ ) on E are Input to the input means 401. At that time, p, a, and b are selected in advance so that the order #E (F _p ) of the rational point group E (F _p ) of the elliptic curve is divisible by a large prime number. In this apparatus, a point P ₄ = (X ₄ , Y ₄ , Z ₄ ) that is a quadruple point P ₁ = (X ₁ , Y ₁ , Z ₁ ) is calculated.
[0033]
First, A, B, C, and D are calculated in the calculation means 408. In each operation, multiplication is a modulo p multiplication means 403, self multiplication is a modulo p self multiplication means 404, addition is a modulo p addition means 405, subtraction is a modulo p subtraction means 406, and multiplication with a single precision integer is modulo p single precision multiplication. Calculation is performed using means 407. The calculated A, B, C, and D are stored in the storage unit 402.
[0034]
Next, the calculation means 409 calculates X ₄ , Y ₄ , and Z ₄ . When calculating, A, B, C, and D are read from the storage unit 402 as appropriate and calculated. In each operation, multiplication is the modulus p multiplication means 403, multiplication is the modulus p self multiplication means 404, addition is the modulus p addition means 405, subtraction is the modulus p subtraction means 406, and multiplication with a single precision integer is modulus p simple. Calculation is performed using the precision multiplication means 407.
[0035]
_{_{Finally, X 4, Y 4, Z}} 4 which computed is output from the output unit 410.
[0036]
By calculating as described above, a quadruple point can be calculated by self-multiplication 10 times and 9 multiplications by the modulus p. In the conventional calculation method, the doubling operation is repeated twice in order to calculate the quadruple point, so that it is necessary to calculate the self multiplication 12 times and the multiplication 8 times. Therefore, the calculation method of the present invention can be calculated faster.
[0037]
This computing device can also be used for encryption using an elliptic curve and for digital signatures.
[0038]
Regarding each embodiment, processing such as input processing, storage processing, reading processing, arithmetic processing, initial value setting processing, and output processing is recorded on a recording medium as a computer-readable program, and a computer serving as an arithmetic device performs the program. Can be realized by sequentially reading and executing the processes included in the program.
Further, the input means and the output means may be storage means used as a module interface.
[0039]
【The invention's effect】
As described above, the calculation method according to the present invention can perform elliptic curve calculation at high speed.
Also, by using the calculation method according to the present invention, encryption using an elliptic curve and digital signature can be performed at high speed.
[0040]
If x ₂ ^k and y ₂ ^k are calculated as described above, the 2 ^k times point can be calculated by performing the inverse element calculation of F _p on the definition body once, and can be calculated at high speed. In the conventional calculation method, since the doubling operation is repeated k times, the inverse element calculation is required k times.
[0041]
By calculating as described above, a quadruple point can be calculated by self-multiplication 10 times and 9 multiplications by the modulus p. In the conventional calculation method, the doubling operation is repeated twice in order to calculate the quadruple point, so that it is necessary to calculate the self multiplication 12 times and the multiplication 8 times. Therefore, the calculation method of the present invention can be calculated faster.
[Brief description of the drawings]
FIG. 1 is a flowchart illustrating a calculation method according to the present invention.
FIG. 2 is a flowchart illustrating a calculation method according to the present invention.
FIG. 3 is a diagram illustrating an arithmetic device according to the present invention.
FIG. 4 is a diagram illustrating an arithmetic device according to the present invention.
FIG. 5 is a flowchart illustrating a conventional calculation method.
FIG. 6 is a flowchart illustrating a conventional calculation method.
[Explanation of symbols]
301, 401 input means, 302, 402 storage means, 303, 403 method p multiplication means, 304, 404 method p self multiplication means, 305, 405 method p addition means, 306, 406 method p subtraction means, 307, 407 method p Single precision multiplication means, 308 method p inverse element calculation means, 309, 310, 311, 312, 312, 408, 409 calculation means, 313, 410 output means, 314, 411 control means.

Claims

A point P ₁ = (x ₁ , y ₁ ) on the elliptic curve E defined on the prime field F _p expressed by the following equation is multiplied by 2 ^k in the affine coordinate system (k is an integer of 2 or more). Arithmetic device for obtaining the point P ₂ ^k = (x ₂ ^k , y ₂ ^k ) and having the following elements: y ² = x ³ + ax + b mod p
(1) Input means for inputting prime number p, element a and element b on prime field F _p , coordinate x ₁ and coordinate y _{1 of} point P ₁ , and integer k
(2) storage means for storing the input prime number p, element a, element b, coordinate x ₁ , coordinate y ₁ , and integer k;
(3) A ₁ calculation means for reading out the coordinate x ₁ and the prime number p and obtaining the array element A ₁ by the following equation:
A ₁ = x ₁ mod p
(4) A ₁ storage means for storing the obtained array element A ₁ ;
(5) B ₁ calculation means for reading the coordinate x ₁ , the element a, and the prime number p, and obtaining the array element B ₁ by the following equation:
B ₁ = 3x ₁ ² + a mod p
(6) B ₁ storage means for storing the obtained array element B ₁ ;
(7) C ₁ calculation means for reading the coordinate y ₁ and the prime number p and obtaining the array element C ₁ by the following equation:
C ₁ = −y ₁ mod p
(8) C ₁ storage means for storing the obtained array element C ₁ ;
(9) i storage means for storing variable i,
(10) i initial value setting means for setting the initial value 2 of the variable i in the i storage means;
(11) i increment means for reading integer k and variable i, sequentially adding 1 to variable i until variable i reaches integer k, and setting in i storage means;
(12) Each time the variable i is set in the i storage means, the variable i and the prime number p are read, and the array element A _i-1 specified by the read variable i and the array element B _i-1 When reads out the array element C _i-1, by the following equation, a _i arithmetic means for obtaining the array element a _i,
A _i = B _i-1 ² -8A _i-1 C _i-1 ² mod p
(13) A _i storage means for storing the obtained array element A _i ;
(14) Each time the variable i is set in the i storage means, the variable i, the element a, and the prime number P are read, and the array element A _i specified by the read variable _i and the array element C ₁ B _i computing means for reading C _i-1 and obtaining the array element B _i by the following equation:

(15) B _i storing means for storing the array elements B _i determined,
(16) Each time the variable i is set in the i storage means, the variable i and the prime number P are read, and the array elements A _i and A _i-1 and the array element B _i specified by the read variable i are read. _-1 and array element C _i-1 , C _i computing means for obtaining array element C _i by the following equation:
C _i = −8 C _i _-1 ⁴ -B _i-1 (A _i -4A _i-1 C _i-1 ² ) mod p
(17) C _i storage means for storing the obtained array element C _i ;
(18) Read integer k and prime number P, read array element A _k , array element B _k , and array element C _k specified by the read integer _k , and calculate numerical value D _k by the following equation: D _k computing means for obtaining
D _k = 12A _k C _k ² −B _k ² mod p
(19) Dk storage means for storing the obtained numerical value Dk,
(20) Read the integer k and the prime number P, and further read the array element A _k , the array element B _k, and the array elements C ₁ to C _k specified by the read integer k. X ₂ ^k computing means for obtaining coordinates x ₂ ^k ;

(21) Read integer k and prime number P, read array element B _k specified by read integer k, array elements C ₁ to C _k , and array element D _k, and Y ₂ ^k computing means for obtaining coordinates y ₂ ^k ;

(22) Output means for outputting the obtained coordinates x ₂ ^k and coordinates y ₂ ^k .

Represented by the following formula, element point F on the _p on an elliptic curve defined _{_{E P 1 = (X 1,}} Y 1, Z 1) , and points were four times in weighted projective coordinates P ₄ = Arithmetic device for obtaining (X ₄ , Y ₄ , Z ₄ ) and having the following elements: E ² = x ³ + ax + b mod p
(1) Input means for inputting the prime number p, the _elements a and b on the prime field F _p , the coordinates X ₁ , the coordinates Y ₁ and the coordinates Z _{1 of} the point P ₁ ;
(2) storage means for storing the input prime number p, element a, element b, coordinate X ₁ , coordinate Y ₁ , and coordinate Z ₁ ;
(3) A calculation means for reading the element a, the coordinate X ₁ , the coordinate Z _1, and the prime number p, and obtaining the numerical value A by the following equation:
A = 3X ₁ ² + aZ ₁ ⁴ mod p
(4) A storage means for storing the obtained numerical value A,
(5) B calculation means for reading the numerical value A, the coordinate X ₁ , the coordinate Y _1, and the prime number p, and obtaining the numerical value B by the following equation:
B = A ² -8X ₁ Y ₁ ² mod p
(6) B storage means for storing the obtained numerical value B,
(7) C calculating means for reading the numerical value A, the coordinate X ₁ , the coordinate Y ₁ and the prime number p, and obtaining the numerical value C by the following equation:
C = −8Y ₁ ⁴ + A (12X ₁ Y ₁ ² −A ² ) mod p
(8) C storage means for storing the obtained numerical value C;
(9) D calculation means for reading the element a, the numerical value B, the coordinate Y ₁ , the coordinate Z _1, and the prime number p, and obtaining the numerical value D by the following equation:
D = 16aY ₁ ⁴ Z ₁ ⁴ + 3B ² mod p
(10) D storage means for storing the obtained numerical value D,
(11) X ₄ calculation means for reading the numerical value B, the numerical value C, the numerical value D, and the prime number p, and obtaining the coordinate X ₄ by the following equation:
X ₄ = −8BC ² + D ² mod p
(12) Y ₄ calculation means for reading the numerical value B, the numerical value C, the numerical value D, and the prime number p, and obtaining the coordinate Y ₄ by the following equation:
Y ₄ = −8C ⁴ + D (12BC ² −D ² ) mod p
(13) Z ₄ computing means for reading the coordinate Y ₁ , the coordinate Z ₁ , the numerical value C, and the prime number p, and obtaining the coordinate Z ₄ by the following equation:
Z ₄ = 4Y ₁ Z ₁ C mod p
(14) An output means for outputting the obtained coordinates X ₄ , coordinates Y ₄ , and coordinates Z ₄ .

A point P ₁ = (x ₁ , y ₁ ) on the elliptic curve E defined on the prime field F _p expressed by the following equation is multiplied by 2 ^k in the affine coordinate system (k is an integer of 2 or more). A calculation method for obtaining the point P ₂ ^k = (x ₂ ^k , y ₂ ^k ), which has the following elements E: y ² = x ³ + ax + b mod p
(1) an input step of inputting a prime number p, _elements a and b on the prime field F _p , coordinates x ₁ and coordinates y _{1 of the} point P ₁ , and an integer k;
(2) a storage step of storing the input prime number p, element a, element b, coordinate x ₁ , coordinate y ₁ , and integer k;
(3) A ₁ calculation step of reading the coordinate x ₁ and the prime number p and obtaining the array element A ₁ by the following formula:
A ₁ = x ₁ mod p
(4) A ₁ storage step for storing the obtained array element A ₁ ;
(5) B ₁ calculation step of reading the coordinate x ₁ , the element a, and the prime number p, and obtaining the array element B ₁ by the following equation:
B ₁ = 3x ₁ ² + a mod p
(6) B ₁ storage step for storing the obtained array element B ₁ ;
(7) C ₁ calculation step of reading out the coordinate y ₁ and the prime number p and obtaining the array element C ₁ by the following equation:
C ₁ = −y ₁ mod p
(8) a C ₁ storage step for storing the obtained array element C ₁ ;
(9) i initial value setting step for setting initial value 2 of variable i;
(10) i increment step for reading integer k and variable i, sequentially adding 1 to variable i until variable i reaches integer k, and setting
(11) Each time the variable i is set, the variable i and the prime number p are read, and the array element A _i-1 , the array element B _i-1, and the array element specified by the read variable i are read. C _i-1 is read, and an A _i calculation step for obtaining an array element A _i by the following equation:
A _i = B _i-1 ² -8A _i-1 C _i-1 ² mod p
(12) A _i storing step of storing the obtained array element A _i ;
(13) Each time the variable i is set, the variable i, the element a, and the prime number P are read, and the array element A _i specified by the read variable _i and the array elements C ₁ to C _i-1 B _i calculation step for obtaining the array element B _i by the following equation:

(14) B _i storage step of storing the obtained array element B _i ,
(15) Each time the variable i is set, the variable i and the prime number P are read, and the array elements A _i and A _i-1 specified by the read variable i, the array element B _i-1 , C _i calculation step for reading array element C _i-1 and obtaining array element C _i by the following equation:
C _i = −8 C _i _-1 ⁴ -B _i-1 (A _i -4A _i-1 C _i-1 ² ) mod p
(16) C _i storage step for storing the obtained array element C _i ,
(17) Read integer k and prime number P, read array element A _k , array element B _k , and array element C _k specified by the read integer _k , and calculate numerical value D _k by the following equation D _k calculation step for obtaining
D _k = 12A _k C _k ² −B _k ² mod p
(18) A Dk storage step for storing the obtained numerical value Dk,
(19) Read integer k and prime number P, and further read array element A _k , array element B _k , and array elements C ₁ to C _k specified by the read integer k. X ₂ ^k calculation step for obtaining coordinates x ₂ ^k ;

(20) Read the integer k and the prime number P, and further read the array element B _k specified by the read integer k, the array elements C ₁ to C _k, and the array element D _k . Y ₂ ^k calculation step for obtaining coordinates y ₂ ^k ,

(21) An output step of outputting the obtained coordinates x ₂ ^k and coordinates y ₂ ^k .

Represented by the following formula, element point F on the _p on an elliptic curve defined _{_{E P 1 = (X 1,}} Y 1, Z 1) , and points were four times in weighted projective coordinates P ₄ = A calculation method for obtaining (X ₄ , Y ₄ , Z ₄ ), which has the following elements: E ² = x ³ + ax + b mod p
(1) An input step of inputting the prime number p, the _elements a and b on the prime field F _p , the coordinates X ₁ , the coordinates Y ₁ and the coordinates Z _{1 of} the point P ₁ .
(2) A storage step of storing the input prime number p, element a, element b, coordinate X ₁ , coordinate Y ₁ , and coordinate Z ₁ ;
(3) An A operation step of reading the element a, the coordinate X ₁ , the coordinate Z _1, and the prime number p, and obtaining a numerical value A by the following equation:
A = 3X ₁ ² + aZ ₁ ⁴ mod p
(4) A storage step for storing the obtained numerical value A,
(5) A numerical value A, a coordinate X ₁ , a coordinate Y _1, and a prime number p are read, and a B operation step for obtaining the numerical value B by the following equation:
B = A ² -8X ₁ Y ₁ ² mod p
(6) B storage step for storing the obtained numerical value B,
(7) A numerical value A, a coordinate X ₁ , a coordinate Y _1, and a prime number p are read out, and a C operation step for obtaining the numerical value C by the following equation:
C = −8Y ₁ ⁴ + A (12X ₁ Y ₁ ² −A ² ) mod p
(8) C storing step for storing the obtained numerical value C,
(9) A D operation step of reading the element a, the numerical value B, the coordinate Y ₁ , the coordinate Z _1, and the prime number p, and obtaining the numerical value D by the following equation:
D = 16aY ₁ ⁴ Z ₁ ⁴ + 3B ² mod p
(10) D storage step for storing the obtained numerical value D,
(11) A numerical value B, a numerical value C, a numerical value D, and a prime number p are read, and an X ₄ calculation step for obtaining a coordinate X ₄ by the following equation:
X ₄ = −8BC ² + D ² mod p
(12) Y ₄ calculation step of reading the numerical value B, the numerical value C, the numerical value D, and the prime number p, and obtaining the coordinate Y ₄ by the following equation:
Y ₄ = −8C ⁴ + D (12BC ² −D ² ) mod p
(13) A Z ₄ calculation step of reading the coordinate Y ₁ , the coordinate Z ₁ , the numerical value C, and the prime number p, and obtaining the coordinate Z ₄ by the following equation:
Z ₄ = 4Y ₁ Z ₁ C mod p
(14) An output step of outputting the obtained coordinates X ₄ , coordinates Y ₄ , and coordinates Z ₄ .

A point P ₁ = (x ₁ , y ₁ ) on the elliptic curve E defined on the prime field F _p expressed by the following equation is multiplied by 2 ^k in the affine coordinate system (k is an integer of 2 or more). A computer-readable recording medium E that records a program for causing a computer serving as an arithmetic unit to obtain the point P ₂ ^k = (x ₂ ^k , y ₂ ^k ) to execute the following processing: y ² = x ³ + ax + b mod p
(1) Input processing for inputting prime number p, element a and element b on prime field F _p , coordinate x ₁ and coordinate y _{1 of} point P ₁ , and integer k
(2) a prime number p that is input, the original a, the original b, or coordinates x _1, a coordinate y _1, the storage process of storing the integer k,
(3) the coordinates x _1, reads the prime p, the following equation, A ₁ arithmetic processing for obtaining the array element A _1,
A ₁ = x ₁ mod p
(4) A ₁ storage process for storing the obtained array element A ₁ ;
(5) Read out the coordinate x ₁ , the element a, and the prime number p, and perform B ₁ calculation processing to obtain the array element B ₁ by the following equation:
B ₁ = 3x ₁ ² + a mod p
(6) B ₁ storage processing for storing the obtained array element B ₁ ;
(7) C ₁ arithmetic processing for reading the coordinate y ₁ and the prime number p and obtaining the array element C ₁ by the following equation:
C ₁ = −y ₁ mod p
(8) C ₁ storage processing for storing the obtained array element C ₁ ;
(9) i initial value setting processing for setting initial value 2 of variable i;
(10) i-increment processing for reading out the integer k and the variable i and sequentially adding 1 to the variable i until the variable i reaches the integer k.
(11) Each time the variable i is set, the variable i and the prime number p are read, and the array element A _i-1 , the array element B _i-1, and the array element specified by the read variable i are read. C _i-1 is read out, and A _i calculation processing for obtaining the array element A _i by the following equation:
A _i = B _i-1 ² -8A _i-1 C _i-1 ² mod p
(12) A _i storage process for storing the obtained array element A _i ;
(13) Each time the variable i is set, the variable i, the element a, and the prime number P are read, and the array element A _i specified by the read variable _i and the array elements C ₁ to C _i-1 B _i calculation processing for obtaining the array element B _i by the following equation:

(14) B _i storage processing for storing the obtained array element B _i ,
(15) Each time the variable i is set, the variable i and the prime number P are read, and the array elements A _i and A _i-1 specified by the read variable i, the array element B _i-1 , C _i arithmetic processing for reading the array element C _i-1 and obtaining the array element C _i by the following equation:
C _i = −8 C _i _-1 ⁴ -B _i-1 (A _i -4A _i-1 C _i-1 ² ) mod p
(16) C _i storage processing for storing the obtained array element C _i ;
(17) Read integer k and prime number P, read array element A _k , array element B _k , and array element C _k specified by the read integer _k , and calculate numerical value D _k by the following equation D _k calculation processing for obtaining
D _k = 12A _k C _k ² −B _k ² mod p
(18) Dk storage processing for storing the obtained numerical value Dk,
(19) Read integer k and prime number P, and further read array element A _k , array element B _k , and array elements C ₁ to C _k specified by the read integer k. X ₂ ^k calculation processing for obtaining coordinates x ₂ ^k ,

(20) Read the integer k and the prime number P, and further read the array element B _k specified by the read integer k, the array elements C ₁ to C _k, and the array element D _k . Y ₂ ^k calculation processing for obtaining coordinates y ₂ ^k ,

(21) Output processing for outputting the obtained coordinates x ₂ ^k and coordinates y ₂ ^k .

Represented by the following formula, element point F on the _p on an elliptic curve defined _{_{E P 1 = (X 1,}} Y 1, Z 1) , and points were four times in weighted projective coordinates P ₄ = A computer-readable recording medium E that records a program for causing a computer, which is an arithmetic unit to obtain (X ₄ , Y ₄ , Z ₄ ) to execute the following processing: y ² = x ³ + ax + b mod p
(1) Input processing for inputting the prime number p, the _elements a and b on the prime field F _p , the coordinates X ₁ , the coordinates Y ₁ and the coordinates Z _{1 of} the point P ₁ .
(2) Storage processing for storing the input prime number p, element a, element b, coordinate X ₁ , coordinate Y ₁ , and coordinate Z ₁ .
(3) A calculation process for reading the element a, the coordinate X ₁ , the coordinate Z _1, and the prime number p, and obtaining the numerical value A by the following equation:
A = 3X ₁ ² + aZ ₁ ⁴ mod p
(4) A storage process for storing the obtained numerical value A,
(5) B calculation processing for reading the numerical value A, the coordinate X ₁ , the coordinate Y _1, and the prime number p and obtaining the numerical value B by the following equation:
B = A ² -8X ₁ Y ₁ ² mod p
(6) B storage processing for storing the obtained numerical value B,
(7) C arithmetic processing for reading the numerical value A, the coordinate X ₁ , the coordinate Y _1, and the prime number p, and obtaining the numerical value C by the following equation:
C = −8Y ₁ ⁴ + A (12X ₁ Y ₁ ² −A ² ) mod p
(8) C storage processing for storing the obtained numerical value C,
(9) Read out the element a, the numerical value B, the coordinate Y ₁ , the coordinate Z ₁ and the prime number p, and calculate the numerical value D by the following formula:
D = 16aY ₁ ⁴ Z ₁ ⁴ + 3B ² mod p
(10) D storage process for storing the obtained numerical value D;
(11) X ₄ arithmetic processing for reading the numerical value B, the numerical value C, the numerical value D, and the prime number p, and obtaining the coordinate X ₄ by the following equation:
X ₄ = −8BC ² + D ² mod p
(12) A numerical value B, a numerical value C, a numerical value D, and a prime number p are read, and a Y ₄ calculation process for obtaining a coordinate Y ₄ by the following equation:
Y ₄ = −8C ⁴ + D (12BC ² −D ² ) mod p
(13) Z ₄ arithmetic processing for reading the coordinate Y ₁ , the coordinate Z ₁ , the numerical value C, and the prime number p, and obtaining the coordinate Z ₄ by the following equation:
Z ₄ = 4Y ₁ Z ₁ C mod p
(14) Output processing for outputting the obtained coordinate X ₄ , coordinate Y ₄ , and coordinate Z ₄ .