JP4510201B2 - Elliptic curve calculation device, elliptic curve order calculation device, elliptic curve construction device, elliptic curve application device, elliptic curve calculation method, elliptic curve order calculation method, elliptic curve construction method, recording medium on which an elliptic curve calculation program is recorded , Recording medium recording elliptic curve order calculation program, and recording medium recording elliptic curve configuration program - Google Patents

Description

【００５１】
ここで、（ｃ／ｐ）は、平方剰余記号であり、
ｃがｐを法とする平方剰余であるとき、 （ｃ／ｐ）＝＋１、
ｃがｐを法とする非平方剰余であるとき、（ｃ／ｐ）＝−１、
ｃ＝０のとき、 （ｃ／ｐ）＝０である。
次に、上記の位数計算式について、簡単に説明する。
【００５２】
１個の値ｎ（０〜ｐ１−１）について、ｎ＾３＋ａ＊ｎ＋ｂが０でない平方数である場合、楕円曲線上の点は２個存在する。ｎ＾３＋ａ＊ｎ＋ｂが０である場合、楕円曲線上の点は１個存在する。ｎ＾３＋ａ＊ｎ＋ｂが平方数でない場合、楕円曲線上の点は存在しない。楕円曲線：ｙ＾２＝ｘ＾３＋ａｘ＋ｂ上において、値ｎ（０〜ｐ１−１）をｘ座標とする点の数は、
【００５３】
【数２】

【００５４】
と表現できる。
従って、０〜ｐ１−１のｐ１個の値について、楕円曲線上の点の数の合計は、
【００５５】
【数３】

【００５６】
と表現できる。これにより、前記位数計算式が得られる。ここで、この計算式の最初の１は零点Ｏの数を表している。
なお、この位数の算出方法については、「Ｃｏｕｎｔｉｎｇ ｐｏｉｎｔｓ ｏｎ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅ ｏｖｅｒ ｆｉｎｉｔｅ ｆｉｅｌｄｓ」（Ｒ． Ｓｃｈｏｏｆ著、Ｊｏｒｎａｌ ｄｅ Ｔｈｅｏｒｉｅ ｄｅｓ Ｎｏｍｂｒｅｓ ｄｅ Ｂｏｒｄｅａｕｘ ７、１９９５年、以下文献Ｓｃｈ２と呼ぶ。）の２１９〜２２０ページに示されている。
【００５７】
次に、楕円曲線有限性判定部５０３は、計算した位数ｍ１と位数ｍ２とを用いて、位数ｍ１とｍ２が互いに素であるか判定し、位数ｍ１とｍ２が互いに素であるか否かを示す位数判定情報を制御部５０６へ出力する。
なお、素数ｐ１及びｐ２は、小さい値であるので、前記位数計算式を用いて位数を計算する場合において、その計算量は、実用的な範囲内である。
（２）位数ｍ１とｍ２が互いに素であることを判定する理由
有理数体上の楕円曲線Ｅについて以下の定理が成り立つ。この定理は、文献１の１７６ページに示されている。
［定理３］有理数体上の楕円曲線Ｅを素数ｐ１、ｐ２（ｐ１≠ｐ２）によって還元した楕円曲線をそれぞれＥｐ１、Ｅｐ２とする。楕円曲線Ｅｐ１、Ｅｐ２の位数をそれぞれｍ１、ｍ２とする。位数ｍ１と位数ｍ２が互いに素であるとき、楕円曲線Ｅは有限位数の点をもたない。
【００５８】
楕円曲線Ｅｐ１とＥｐ２の位数が互いに素である場合、Ｅが有限位数の点を持たないため、上記の事実２により、Ｅｐは素数位数を持つ楕円曲線になる確率が高い。逆に、楕円曲線Ｅｐ１とＥｐ２の位数が互いに素でない場合、Ｅが有限位数の点を持つため、上記の事実２により、Ｅｐは素数位数を持たない楕円曲線になる確率が高く、この楕円曲線の安全性は低くなる。このため、楕円曲線Ｅｐ１とＥｐ２の位数が互いに素でない場合には、この楕円曲線の採用は棄却する。
【００５９】
こうして、位数計算を行う前に、安全性の低い楕円曲線を棄却し、安全性の低い楕円曲線の位数計算を行わないようにすることができ、位数計算の計算量を削減することが可能となる。
なお、素数ｐ１、ｐ２は素数ｐより小さい素数であれば何でもよいが、上記に示すように、素数ｐ１＝５、素数ｐ２＝７とすればよい。この組合せが最も小さい素数の組合せであるので、このとき、位数の計算量が最も小さくなる。
【００６０】
また、素数ｐ１（又は素数ｐ２）を３としたとき、楕円曲線の判別式ＴＤが、ｍｏｄ ３を取れば、０になるので、Ｅｐ１（又はＥｐ２）が楕円曲線でなくなる。そのため、素数ｐ１（又は素数ｐ２）を３としてはならない。
１．６ 楕円曲線位数計算部５０４
楕円曲線位数計算部５０４は、次に示すようにして、有限体ＧＦ（ｐ）上の楕円曲線Ｅの位数を計算する。
１．６．１ ＳＥＡアルゴリズムによる位数の算出
楕円曲線位数計算部５０４は、ＳＥＡアルゴリズムにより楕円曲線の位数計算を行う。
【００６１】
楕円曲線Ｅの位数をｍとし、ｔを
ｍ＝ｐ＋１−ｔ
を満たすものとする。また、
ｆ（ｘ）＝ｘ＾３＋ａｘ＋ｂ
とする。
【００６２】
楕円曲線位数計算部５０４は、初期値として、整数変数Ｌ＝２とする。
楕円曲線位数計算部５０４は、Ｍｏｄｕｌａｒ多項式ΦＬ（Ｔ，ｊ（Ｅ））の一変数Ｔの多項式環ＧＦ（ｐ）［Ｔ］における因数分解の一次因子の数を算出する。
次に、楕円曲線位数計算部５０４は、算出した一次因子の数が２のとき、ｔ ｍｏｄ Ｌを求め、Ｉｓｏｇｅｎｙ ｃｙｃｌｅ法により、ｔ ｍｏｄ Ｌ＾ｎを求める。
【００６３】
算出した一次因子の数が１またはＬ＋１のとき、ｔ ｍｏｄ Ｌを求め、Ｉｓｏｇｅｎｙ ｃｙｃｌｅ法を適用可能であるか判定し、適用可能なら、Ｉｓｏｇｅｎｙ ｃｙｃｌｅ法により、ｔ ｍｏｄ Ｌ＾ｎ（ｎ＝２，３，．．．）を求める。
算出した一次因子の数が０のとき、ｔ ｍｏｄ Ｌの取り得る値を集合［０、１、・・・、Ｌ−１］から絞り込む。
【００６４】
次に、楕円曲線位数計算部５０４は、
Ｌ１＾（ｎ１）×Ｌ２＾（ｎ２）×・・・×Ｌｋ＾（ｎｋ）
＜ ４×ｐ＾（１／２）
（ここで、Ｌ１、Ｌ２、・・・、Ｌｋは素数であり、Ｌｋ＝Ｌ）
であるとき、Ｌ＝（Ｌの次に大きい素数）とし、再度前記一次因子の数の算出、一次因子の数毎の処理を、前記条件式を満たさなくなるまで繰り返す。
【００６５】
次に、前記条件式を満たさないとき、楕円曲線位数計算部５０４は、ｍａｔｃｈ＆ｓｏｒｔアルゴリズムにより、位数ｍを確定し、位数ｍを情報記憶部５０７へ書き込む。
なお、この位数計算方法については、「Counting the number of points on elliptic curves over finite fields: strategies performances」（R.Lercier、F.Morain著、EUROCRYPT'95、Springer-Verlag、１９９５年、７９ページ〜９４ページ）に詳しく説明されている。
【００６６】
また、ｍａｔｃｈ＆ｓｏｒｔアルゴリズムについては、「Algorithmique des courbes elliptiques dans les corps finis」（ Thesis, Ecole Polytechnique-LIX, (1997), in French, 195〜202ページ）、又は、「Elliptic Curves in Cryptography", London Mathematical Society, Lecture Note Series 265, CAMBRIDGE UNIVERSITY PRESS,(1999), 142〜144ページ)に説明されている。
１．６．２ ＳＥＡアルゴリズムによる位数の算出方法についての補足説明
ＳＥＡアルゴリズムによる位数の算出方法について、補足的に説明する。楕円曲線位数計算部５０４は、以下に説明する位数の算出を行う。
【００６７】
位数計算を行う対象となる楕円曲線をGF(p)上の楕円曲線を、
Ｅ：ｙ＾２＝ｆ（ｘ）
とする。ここで、ｆ（ｘ）＝ｘ＾３＋ａｘ＋ｂ である。
（１）固有方程式
（１−１）ＧＦ（ｐ）の代数的閉包Ｋ
ＧＦ（ｐ）の代数的閉包（ａｌｇｅｂｒａｉｃ ｃｌｏｓｕｒｅ）をＫとする。代数的閉包Ｋは、ＧＦ（ｐ）を含む体であり、Ｋの係数をもつ多項式は必ず、一次式に分解できる。
【００６８】
なお、他の代数的閉包の例として、実数体の代数的閉包である複素数体がある。複素数の係数をもつ多項式は必ず、一次式に分解できる。
（１−２）フロベニウス写像（Ｆｒｏｂｅｎｉｕｓ ｍａｐ）φｐ
楕円曲線上の点Ｐ＝（α、β）（α、β∈Ｋ）に対して、フロベニウス写像φｐを以下のように定義する。
【００６９】
φｐ：（α、β） → （α＾ｐ、β＾ｐ）
（α、β）は、Ｅ上の点であるので、
β＾２＝α＾３＋ａα＋ｂ
が成り立つ。両辺をｐ乗すると、
β＾（２ｐ）＝（α＾３＋ａα＋ｂ）＾ｐ
であり、この式の右辺は、「代数概論」（森田康夫著、数学選書９、裳華房、１９８７年）の１９３ページの記述により、

となる。なお、ａ、ｂがＧＦ（ｐ）の元であるので、ａ＝ａ＾ｐ、ｂ＝ｂ＾ｐである。
【００７０】
従って、
（β＾ｐ）＾２＝（α＾ｐ）＾３＋ａ（α＾ｐ）＋ｂ
となり、（α＾ｐ、β＾ｐ）も楕円曲線上の点となる。
（１−３）固有多項式（ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｐｏｌｙｎｏｍｉａｌ）
「Elliptic curves over finite fields and the computation of square roots mod p」（Ｒ．Ｓｃｈｏｏｆ著、Ｍａｔｈ．Ｃｏｍｐ．Ｖｏｌ４４、１９８５年）の４８５ぺージの記述によると、
楕円曲線上の点Ｐ＝（α、β）（α、β∈Ｋ）に対して、以下の式が成り立つ。
【００７１】
（φｐ）＾２（Ｐ） − ｔφｐ（Ｐ） ＋ ｐＰ ＝ Ｏ
ここで、Ｏは楕円曲線の群の零元である。また、ｔはトレースと呼ばれ、上式の＋、−は、楕円曲線上の加算、減算を示す記号である。
Ｈａｓｓｅの定理より、ｔから位数は以下の式より求められる。
位数＝ｐ＋１−ｔ
よって、トレースｔを求めることにより、位数を計算することができる。
【００７２】
点ＰをＥ上のＬ等分点（Ｌ：素数）、すなわち、ＬＰ＝Ｏを満たす点とするとき、以下の式が成り立つ。
（φｐ）＾２（Ｐ） − （ｔ ｍｏｄ Ｌ）φｐ（Ｐ）
＋ （ｐ ｍｏｄ Ｌ）Ｐ ＝ Ｏ
ＳＥＡアルゴリズムでは、この方程式から、ｔ ｍｏｄ Ｌを計算する。
【００７３】
ここで、φｐが固有値ｋをもつとは、あるＥ上のＬ等分点Ｐに対し、
φｐ（Ｐ） ＝ ｋＰ
が成り立つことである。ここで、ｋＰは、楕円曲線上の冪倍点である。
このとき、φｐの固有多項式は、
ｋ＾２ Ｐ − （ｔ ｍｏｄ Ｌ）ｋＰ
＋ （ｐ ｍｏｄ Ｌ）Ｐ ＝ Ｏ
となる。よって、固有値ｋが存在するとき、φｐの固有多項式は、
ｋ＾２ − （ｔ ｍｏｄ Ｌ）ｋ ＋ （ｐ ｍｏｄ Ｌ） ＝ ０
の形の変数ｋの２次方程式と考えられる。ＳＥＡアルゴリズムでは、この方程式のＧＦ（Ｌ）の根の有無により、以下の場合に分ける。
【００７４】
前記２次方程式が、異なる根ｋ１、ｋ２をもつ場合（Ｃａｓｅ１）
前記２次方程式が、重根をもつ場合（Ｃａｓｅ２）
前記２次方程式が、根をもたない場合（Ｃａｓｅ３）
以下において、３つのケースの処理について説明する。
（Ｃａｓｅ１）前記２次方程式が、異なる根ｋ１、ｋ２をもつ場合
前記２次方程式が、異なる根ｋ１、ｋ２をもつ場合には、
ｋ＾２ − （ｔ ｍｏｄ Ｌ）ｋ ＋（ｐ ｍｏｄ Ｌ）
＝ （ｋ−ｋ１）（ｋ−ｋ２）
とおくことができ、
ｋ１＋ｋ２ ＝ ｔ ｍｏｄ Ｌ、ｋ１＊ｋ２＝ｐ ｍｏｄ Ｌ
となる。したがって、ｋ１が求まれば、
ｔ ＝ ｋ１ ＋ ｐ／ｋ１ ＝ （ｋ１＾２＋ｐ）／ｋ１ ｍｏｄ Ｌ
より、ｔを求められる。
（Ｃａｓｅ２）前記２次方程式が、重根をもつ場合
前記２次方程式が、重根をもつ場合には、
ｋ１＾２＝ｐ ｍｏｄ Ｌ
であるので、ｋ は
± √（ｐ） ｍｏｄ Ｌ
のどちらかの値をもつ。これは、
φｐ Ｐ ＝ ±（√（ｐ） ｍｏｄ Ｌ） Ｐ
のどちらが成り立つかによりで確定する。
【００７５】
φｐの固有値によって、ｔは、
±２ √（ｐ） ｍｏｄ Ｌ
のどちらかの値になる。
（Ｃａｓｅ３）前記２次方程式が、根をもたない場合
前記２次方程式が、根をもたない場合には、
（（φｐ）＾２＋（ｐ ｍｏｄ Ｌ））Ｐと
（ｔ’ ｍｏｄ Ｌ）φｐＰとの座標比較を行い、一致する場合のｔ’を正しいｔ ｍｏｄ Ｌとする。
（１−４）ケースの判定
上記のＣａｓｅ１、Ｃａｓｅ２、Ｃａｓｅ３は、ｔ ｍｏｄ Ｌが分からないので、どのケースに該当するか本来は分からない。
【００７６】
しかしながら、Ｍｏｄｕｌａｒ多項式とよばれる多項式のＧＦ（ｐ）の根の数により、判定することができる。
Ｍｏｄｕｌａｒ多項式ΦＬ（Ｔ，ｊ（Ｅ））のＧＦ（ｐ）の根の数が２個の場合は、Ｃａｓｅ１に該当する。根の数が１個又はＬ＋１個の場合は、Ｃａｓｅ２に該当する。根の数が０個の場合は、Ｃａｓｅ３に該当する。
【００７７】
なお、詳細については、「Counting points on elliptic curve over finite fields」（R. Schoof 著、Jornal de Theorie des Nombres de Bordeaux 7 、1995年）の２３９ページに記載されているので、説明を省略する。
（１−５）Ｃａｓｅ３の場合の固有方程式の解き方
Ｃａｓｅ３の場合について、固有方程式の解き方について、説明する。
【００７８】
Ｌ等分点、すなわち、ＬＰ＝Ｏを満たすＥ上の点Ｐ全体のｘ座標を根としてもつ多項式を、Ｌ等分多項式といい、ｆＬ（α）で表す。このとき、「Ｐ＝（α，β）がＬ等分点である」と「ｆＬ（α）＝０」とは同値である。
ｆＬ（α）は漸化式を使用して求められる。なお、詳細については、「Elliptic curves over finite fields and the computation of square roots mod p」（Ｒ．Ｓｃｈｏｏｆ著、Ｍａｔｈ．Ｃｏｍｐ．、Ｖｏｌ４４、１９８５年）の４８５ページに記載されているので、説明を省略する。
（１−６）固有方程式の多項式表現
固有方程式から
（式１）
（φｐ）＾２（Ｐ）＋（ｐ ｍｏｄ Ｌ）Ｐ＝（ｔ ｍｏｄ Ｌ）φｐＰ
であることが分かる。点Ｐの座標を（α，β）とすると、点Ｐ（α，β）は、楕円曲線上の点であるので、
β＾２−α＾３−ａα−ｂ＝０
を満たし、Ｌ等分点であるので、
ｆＬ（α）＝０ を満たす。
【００７９】
ここで、式１の点Ｐの座標を、α，βを変数とする多項式剰余環
Ｒ＝ＧＦ（ｐ）［α，β］／（β＾２−α＾３−ａα−ｂ，ｆＬ（α））
で表す。
多項式剰余環Ｒでの演算は、「β＾２」を、「α＾３＋ａα＋ｂ」に書き換え、「ｆＬ（α）」を「０」にして行う。
【００８０】
以下において、ｉｎ Ｒと明記した場合、この多項式剰余環Ｒでの演算を行うものとする。
このとき、式１より、
（式２）
（α＾（ｐ＾２）、β＾（ｐ＾２）） ＋ （ｐ ｍｏｄ Ｌ）（α、β）
＝ （ｔ ｍｏｄ Ｌ） （α＾ｐ、β＾ｐ） ｉｎ Ｒ
が成り立つ。
（１−７）Ｃａｓｅ１の場合の固有方程式の解き方
Ｃａｓｅ１の場合の固有方程式の解き方について説明する。
【００８１】
Ｃａｓｅ１では、φｐ Ｐ ＝ ｋ Ｐ を満たす ｋ を求める。
このとき、前記Ｌ等分多項式ｆＬ（α）の因子ｈ（α）を用いる。すなわち、ｈ（α）はｆＬ（α）を割り切る。ｈ（α）の求め方については、「Counting points on elliptic curve over finite fields」（Ｒ．Ｓｃｈｏｏｆ著、Jornal de Theorie des Nombres de Bordeaux 7、１９９５年）の２４２〜２５３ページに記載されているので、説明を省略する。
（１−８）Ｃａｓｅ２の場合の固有方程式の解き方
Ｃａｓｅ２の場合の固有方程式の解き方について説明する。
【００８２】
Ｃａｓｅ２では、ｋ が ±√ｐ まで分かっているので、ｙ座標の比較を行い、符号を決定する。
なお、Ｃａｓｅ１、Ｃａｓｅ２の計算量に比べ、Ｃａｓｅ３の計算量が大きいため、Ｃａｓｅ３では、ｔ ｍｏｄ Ｌを求めない。ｔ ｍｏｄ Ｌの取りうる値の候補に絞り込む計算を行う。このようにすると、Ｃａｓｅ３の計算量は、Ｃａｓｅ１又はＣａｓｅ２の計算量とほぼ同じになる。
【００８３】
ただし、Ｌが小さい場合（Ｌ＜＝５）には、計算量が小さいため、正しいｔ ｍｏｄ Ｌを求める。
なお、絞り込み計算については、「Counting points on elliptic curve over finite fields」（Ｒ．Ｓｃｈｏｏｆ著、Jornal de Theorie des Nombres de Bordeaux 7、１９９５年）の２３９〜２４１ページに詳しく説明されている。
１．６．３ ｔ ｍｏｄ Ｌ＾ｎの算出
楕円曲線位数計算部５０４は、次に示すようにして、ｔ ｍｏｄ Ｌ＾ｎを算出する。
（１）ｔ ｍｏｄ Ｌ の算出
楕円曲線位数計算部５０４は、ｈ（α）を入力として、以下に示すようにして、ｔ ｍｏｄ Ｌを計算し、ｔ ｍｏｄ Ｌを出力する。
【００８４】
多項式剰余環Ｒを
Ｒ＝ＧＦ（ｐ）[α，β]／（β＾２−α＾３−ａα―ｂ，ｈ（α））
とする。ｔ ｍｏｄ Ｌを求めるには、
φｐ（（α，β））＝ｋ（α，β） ｉｎ Ｒ
を満たすｋを求める必要がある。
【００８５】
楕円曲線位数計算部５０４は、ｋ'を、０の値から（Ｌ−１）／２の値まで、順に変化させて、
φｐ（（α，β）） ｉｎ Ｒ のｘ座標と、
ｋ'（α，β） ｉｎ Ｒ のｘ座表とを算出し、
それぞれのｋ'について、
算出した φｐ（（α，β）） ｉｎ Ｒ のｘ座標と、
算出した ｋ'（α，β） ｉｎ Ｒ のｘ座標とを比較し、
初めて一致する場合に、
φｐ（（α，β）） ｉｎ Ｒ のｙ座標と、
ｋ'（α，β） ｉｎ Ｒ のｙ座標とを算出し、
φｐ（（α，β）） ｉｎ Ｒ のｙ座標と、
ｋ'（α，β） ｉｎ Ｒ のｙ座標とが一致する場合に、ｋ＝ｋ' ｍｏｄ Ｌとし、一致しない場合に、ｋ＝Ｌ−ｋ’ ｍｏｄ Ｌとする。
【００８６】
さらに、ｔ＝（ｋ＾２＋ｐ）／ｋ ｍｏｄ Ｌとし、ｔを出力する。
（２）Ｉｓｏｇｅｎｙ ｃｙｃｌｅ法によるｔ ｍｏｄ Ｌ＾ｎの算出
楕円曲線位数計算部５０４は、Ｉｓｏｇｅｎｙ ｃｙｃｌｅ法によりｔ ｍｏｄＬ＾ｎを求める。
Ｃａｓｅ１では、まず、楕円曲線位数計算部５０４は、ｎ＝２とし、ｋ ｍｏｄ Ｌとｈ（α）を基に多項式Ｈ（α）を求め、それを改めて、ｈ（α）とする。その多項式ｈ（α）を用いて、ｋ ｍｏｄ Ｌ＾ｎを求める。次に、多項式ｈ（α）の次数により、次に進むか否かを判定する。ｈ（α）の次数をｄｅｇ（ｈ（α））とする。そのとき、
（ｄｅｇ（ｈ）＾２）＊Ｌ＾２＊（Ｌ＾（２＊ｎ））
＞ （｜ｐ｜）＾３／１３５ であるか否かを判断する。ここで、｜ｐ｜はｐのビット数である。前記判断式が真であれば、
ｔ＝（ｋ＾２＋ｐ）／ｋ ｍｏｄ Ｌ＾ｎ
として、Ｉｓｏｇｅｎｙ ｃｙｃｌｅを終了する。偽であれば、ｎに１を加算して、前記不等式を満たすまで、前記処理を繰り返す。こうして、楕円曲線位数計算部５０４は、ｔ ｍｏｄ Ｌ＾ｎを求める。
【００８７】
なお、Ｃａｓｅ２の場合も、楕円曲線位数計算部５０４は、Ｃａｓｅ１と同様に行うが、必ずしもＩｓｏｇｅｎｙ ｃｙｃｌｅが行えるとは限らない。したがって、楕円曲線位数計算部５０４は、Ｉｓｏｇｅｎｙ ｃｙｃｌｅを行えるか否かの判定を行う。
次に、ｋ ｍｏｄ Ｌ＾ｎ（ｎ＞１の場合）の算出について、説明する。
【００８８】
ここで、ｋ＿ｉ＝ｋ ｍｏｄ Ｌ＾ｉ （１≦ｔ≦ｎ） とする。
楕円曲線位数計算部５０４は、ｋ ｍｏｄ Ｌ＾（ｎ−１）とｈ（α）を入力として、次に示すようにして、ｋ ｍｏｄ Ｌ＾ｎを算出する。
多項式剰余環Ｒを
Ｒ＝ＧＦ（ｐ）[α，β]／（β＾２−α＾３−ａα―ｂ，ｈ（α））
とする。ｋ ｍｏｄ Ｌ＾ｎを求めるには、
φｐ（（α，β））
＝ （ｋ＿（ｎ−１）＋Ｌ＾（ｎ−１）＊κ） （α，β） ｉｎ Ｒ
を満たすκを求める必要がある。
【００８９】
楕円曲線位数計算部５０４は、κ’を、０の値から（Ｌ−１）／２の値まで、順に変化させて、
φｐ（（α，β）） ｉｎ Ｒ のｘ座標と、
（ｋ＿（ｎ−１）＋Ｌ＾（ｎ−１）＊κ’） （α，β） ｉｎ Ｒ のｘ座表とを算出し、
それぞれのκ’について、
算出した φｐ（（α，β）） ｉｎ Ｒ のｘ座標と、
算出した （ｋ＿（ｎ−１）＋Ｌ＾（ｎ−１）＊κ’） （α，β） ｉｎ Ｒ のｘ座標とを比較し、
初めて一致する場合に、
ｋ＿ｎ＝ｋ＿（ｎ−１）＋Ｌ＾（ｎ−１）＊κ’ ｍｏｄ Ｌ＾ｎ
とし、ｋ＿ｎをｋ ｍｏｄ Ｌ＾ｎとする。
【００９０】
なお、これらの処理については、「Isogeny cycles and the Schoof-Elkies-Atkin algorithm」（J.M.Couveignes、L.Dewaghe及びF.Morain著、ＬＩＸ／ＲＲ／９６／０３、１９９６年）に詳しく説明されている。
１．６．４ 楕円曲線位数計算部５０４による終了判定
楕円曲線位数計算部５０４は、すでに説明したように、ΠＬｋ＾（ｎｋ） が４ √ｐ を超えるとき、ＳＥＡアルゴリズムによる繰返し計算の終了と判定し、位数を確定し、楕円曲線位数計算部５０４による計算を終了する。
【００９１】
しかしながら、楕円曲線位数計算部５０４は、楕円曲線条件判定部５０５により、安全な楕円曲線でないと判定される楕円曲線を予め排除して、計算時間を削減するために、楕円曲線位数計算部５０４内部において、楕円曲線の判定を行う。
具体的には、楕円曲線位数計算部５０４は、ｔ ｍｏｄ Ｌが確定した時点で、ｐ＋１−ｔ ｍｏｄ Ｌを算出し、ｐ＋１−ｔ ｍｏｄ Ｌ ＝ ０であるか否かを判断し、ｐ＋１−ｔ ｍｏｄ Ｌ ＝ ０である場合は、楕円曲線の位数が素数になり得ないので、当該楕円曲線の採用を棄却するために、楕円曲線棄却情報を制御部５０６へ出力し、楕円曲線位数計算部５０４による計算を終了する。
【００９２】
このように、楕円曲線位数計算部５０４において、ｔ ｍｏｄ Ｌが確定した時点で、安全性の低い楕円曲線を棄却するので、楕円曲線位数計算部５０４において、無駄な処理を行わないようにすることができる。
なお、この方法については、「Finding Good Random Elliptic Curves for Cryptosystems Defined over F_{2^n}」（Ｒ． Ｌｅｒｃｉｅｒ著、Advances in Cryptology-Proceedings of Eurocrypt'97、Lecture Notes in Computer Science、１２３３、１９９７年、Springer-Verlag）に記載されている。
１．６．５ 冪倍点の計算
上記に説明したように、φpの固有値を求めるには、楕円曲線の冪倍点演算が必要になる。以下では、冪倍点の計算方法について説明する。
（１）等分多項式を用いる方法
楕円曲線位数計算部５０４は、上記のｔ ｍｏｄ Ｌの算出において、次に示すようにして、冪倍点を計算する。
【００９３】
等分多項式ｆ＿ｎを用いると、ｎ （α，β）は以下のようになる。
ｎが偶数の場合、

ｎが奇数の場合、

これについては、「Elliptic curves over finite fields and the computation of square roots mod p」（R.Schoof著、Math.Comp.、４４、１９８５）の４８５〜４８６ページについて、記載されている。
（２）楕円曲線演算を用いる方法
楕円曲線位数計算部５０４は、上記のｔ ｍｏｄ Ｌ＾ｎの算出において、次に示すようにして、冪倍点を計算する。
【００９４】
ここで、前記等分多項式を用いると、ｆ＿１からｆ＿（Ｌ＾（ｎ−２））のような必要のない等分多項式を求める必要があり、効率的でない。そこで、楕円曲線位数計算部５０４は、楕円曲線演算によって、求める方法を採用する。
まず、有限体上の楕円曲線演算を適用することを考える。有限体上の演算の場合、２項組座標を用いた演算を採用すれば、除算が必要となる。しかし、除算は乗算に比べ、一般に計算量が大きいため（１０倍程度）、除算を使用しない３項組の演算について考える。多項式剰余環の場合も同様に３項組の場合を考える。
【００９５】
ここで、２項組の座標の第１、２成分をそれぞれ、ｘ座標，ｙ座標と呼ぶ。また、３項組の座標の第１、２、３成分をそれぞれ、Ｘ座標，Ｙ座標，Ｚ座標と呼ぶ。
有限体上のJacobian座標を適用する。入力と出力が同じ形をしていた方が計算しやすいので、多項式剰余環R上の楕円曲線を考え、その上の点の座標を、
(X(α):β*Y(α):Z(α))
として、入力と出力はこの形をしていると設定する。
【００９６】
さらに、以下の変換を使用し、入力と出力の形を変える。この場合にも、Jacobian座標である。
(X'(α):β*Y'(α):Z'(α)) → (β^2*X'(α):β^4*Y'(α):β*Z'(α))
ここで、β^2=f(α)であるので、
X(α)=f(α)*X'(α)
Y(α)=f(α)^2*Y'(α)
Z(α)=Z'(α)
とすると、変換先の点は、
(X(α):Y(α):β*Z(α))
の形をしている。
（２−１）楕円曲線上の点の射影
楕円曲線位数計算部５０４は、楕円曲線Ｅ上の点のアフィン座標
（φ（α）、β×ψ（α））を、
多項式Ｘ（α）＝ｆ（α）×φ（α）、
多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び
多項式Ｚ（α）＝１
により変換して射影座標
（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成する。
【００９７】
ここで、φ（α）及びψ（α）は多項式である。また、「（ ： ： ）」は、射影座標を示す。
（２−２）楕円曲線の演算（加算と２倍算）
次に、多項式剰余環上で定義された楕円曲線上の点の演算について説明する。
楕円曲線上の点の演算は、２倍算及び加算に分解することができる。例えば、楕円曲線上の点Ｐについて、１００×Ｐの計算は、
１００×Ｐ＝２（２（Ｐ＋２（２（２（Ｐ＋２Ｐ）））））と表すと、楕円曲線上の点による６回の２倍算と２回の加算により行える。
【００９８】
なお、２倍算及び加算への分解については、Signed Binary 法を用いて行う。
Signed Binary 法については、「Speeding up Elliptic Curve Cryptosystems by Using a Signed Binary Window Method」（K.Koyama, Y.Tsuruoka 著、Advances in Cryptology - CRYPTO'92, Lecture Notes in Computer Science, Vol. 740, Springer-Verlag, (1993), 345〜357ページ）に説明されている。
【００９９】
この楕円曲線の演算において、楕円曲線位数計算部５０４は、α、βを変数とし、有限体ＧＦ（ｐ）上の元を係数とする多項式
β＾２−ｆ（α）
と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする多項式剰余環上の楕円曲線
Ｅ：ｙ＾２＝ｆ（ｘ）
に対して、楕円曲線Ｅ上の点の座標を入力として演算を行い、演算結果として楕円曲線Ｅ上の点の座標を算出する。
（２−２−１）加算
ここでは、加算について説明する。
【０１００】
楕円曲線位数計算部５０４は、楕円曲線Ｅ上の点Ｐ、Ｑ（Ｐ≠±Ｑ）
Ｐ＝（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））、
Ｑ＝（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））
を入力とし、

を計算し、次に、

を計算する。
【０１０１】
次に、楕円曲線位数計算部５０４は、
β×Ｚ３
を計算し、
Ｐ＋Ｑ＝（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））
を楕円曲線Ｅ上の点ＰとＱとの加算結果とする。
【０１０２】
なお、上記に示す各演算式において、Ｘ１、Ｙ１、Ｚ１、Ｘ２、Ｙ２、Ｚ２、Ｘ３、Ｙ３、Ｚ３、Ｕ１、Ｕ２、Ｓ１、Ｓ２、Ｈ、ｒは、それぞれ変数αに関する多項式であるので、Ｘ１（α）、Ｙ１（α）、Ｚ１（α）などと表記すべきであるが、表記を簡単にするために、（α）を省略して記載しているので、注意を要する。
（２−２−２）２倍算
ここでは、２倍算について説明する。
【０１０３】
楕円曲線位数計算部５０４は、楕円曲線Ｅ上の点
Ｐ＝（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））
を入力とし、

を計算し、次に、

を計算する。
【０１０４】
次に、楕円曲線位数計算部５０４は、
β×Ｚ３
を計算し、
２Ｐ＝（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））
を楕円曲線Ｅ上の点Ｐの２倍算の結果とする。
【０１０５】
なお、上記に示す各演算式において、Ｘ１、Ｙ１、Ｚ１、Ｘ３、Ｙ３、Ｚ３、Ｓ、Ｍ、Ｔは、それぞれ変数αに関する多項式であるので、Ｘ１（α）、Ｙ１（α）、Ｚ１（α）などと表記すべきであるが、表記を簡単にするために、（α）を省略して記載しているので、注意を要する。
前記加算公式及び前記２倍算公式における乗算の回数は、演算子＊の出現回数を数えると分かるように、それぞれ、１６回、１０回である。多項式乗算の計算量をＰＭｕｌとするとき、前記加算公式及び前記２倍算公式による計算量はそれぞれ、１６×ＰＭｕｌ、１０×ＰＭｕｌである。
【０１０６】
このように、従来例３に示す加算公式の計算量と比較すると、多項式乗算の計算量は、１ＰＭｕｌ増加しており、従来例３に示す２倍算公式の計算量と比較すると、多項式乗算の計算量は２ＰＭｕｌ減少している。
通常、２倍算の演算回数は、加算の演算回数より多いので、２倍算の計算量の減少は、全体の計算量の減少に大きく貢献する。
（２−３）加算公式及び２倍算公式の導出
ここでは、前記加算公式及び前記２倍算公式の導出について説明する。
【０１０７】
有限体上のＪａｃｏｂｉａｎ座標の演算は以下のようになる。
ここで、Ｐ＝（ｘ１：ｙ１：ｚ１），Ｑ＝（ｘ２：ｙ２：ｚ２），Ｐ＋Ｑ＝Ｒ＝（ｘ３：ｙ３：ｚ３）とする。
（加算）（Ｐ≠±Ｑの場合）
加算は、次のようになる。
【０１０８】
ｘ３＝−Ｈ＾３−２＊Ｕ１＊Ｈ＾２＋ｒ＾２，
ｙ３＝−Ｓ１＊Ｈ＾３＋ｒ＊（Ｕ１＊Ｈ＾２−ｘ３），
ｚ３＝ｚ１＊ｚ２＊Ｈ
ここで、Ｕ１＝ｘ１＊ｚ２＾２，Ｕ２＝ｘ２＊ｚ１＾２，Ｓ１＝ｙ１＊ｚ２＾３，Ｓ２＝ｙ２＊ｚ１＾３，Ｈ＝Ｕ２−Ｕ１，ｒ＝Ｓ２−Ｓ１ である。
（２倍算）（Ｐ＝Ｑの場合）
２倍算は、次のようになる。
【０１０９】
ｘ３＝Ｔ，
ｙ３＝−８＊ｙ１＾４＋Ｍ＊（Ｓ−Ｔ），
ｚ３＝２＊ｙ１＊ｚ１
ここで、Ｓ＝４＊ｘ１＊ｙ１＾２，Ｍ＝３＊ｘ１＾２＋ａ＊ｚ１＾４，Ｔ＝−２＊Ｓ＋Ｍ＾２である。
【０１１０】
次に、この演算を多項式剰余環Ｒ上に適用する。
ここで、Ｐ＝（Ｘ１（α）：Ｙ１（α）：β＊Ｚ１（α）），Ｑ＝（Ｘ２（α）：Ｙ２（α）：β＊Ｚ２（α）），Ｐ＋Ｑ＝Ｒ＝（Ｘ３（α）：Ｙ３（α）：β＊Ｚ３（α））とする。
また、上記の演算に適用するため、
ｘ１＝Ｘ１（α），ｙ１＝Ｙ１（α），ｚ１＝β＊Ｚ１（α）
ｘ２＝Ｘ２（α），ｙ２＝Ｙ２（α），ｚ２＝β＊Ｚ２（α）
ｘ３＝Ｘ３（α），ｙ３＝Ｙ３（α），ｚ３＝β＊Ｚ３（α）
とおく。
（多項式剰余環Ｒ上の楕円曲線のＪａｃｏｂｉａｎ座標の加算）
多項式剰余環Ｒ上の楕円曲線のＪａｃｏｂｉａｎ座標の加算は、次のようになる。
【０１１１】
Ｕ１＝Ｘ１＊β＾２＊Ｚ２＾２，
Ｕ２＝Ｘ２＊β＾２＊Ｚ１＾２，
Ｓ１＝Ｙ１＊β＾３＊Ｚ２＾３，
Ｓ２＝Ｙ２＊β＾３＊Ｚ１＾３
ここで、Ｕ１’＝Ｕ１／β＾２，Ｕ２’＝Ｕ２／β＾２，Ｓ１’＝Ｓ１／β＾３，Ｓ２’＝Ｓ２／β＾３とすると、
Ｈ＝（Ｕ２’―Ｕ１’）＊β＾２，ｒ＝（Ｓ２’―Ｓ１’）＊β＾３ である。
【０１１２】

である。ここで、ｘ３’＝ｘ３／β＾６とおくと、

である。ここで、ｙ３’＝ｙ３／β＾９とおくと、
ｙ３’＝−Ｓ１’＊Ｈ’＾３＋ｒ’＊（Ｕ１’＊Ｈ’＾２−ｘ３’） であり、
ｚ３＝Ｚ１＊β＊Ｚ２＊β＊Ｈ’＊β＾２ である。
【０１１３】
ここで、ｚ３’＝ｚ３／β＾４とする。
このとき、
Ｘ３＝ｘ３’＊β＾６
Ｙ３＝ｙ３’＊β＾９
β＊Ｚ３＝ｚ３’＊β＾４
である。
【０１１４】
（Ｘ３：Ｙ３：β＊Ｚ３）＝（Ｘ３／β＾６：Ｙ３／β＾９：β＊Ｚ３／β＾４）
であるので、
（Ｘ３：Ｙ３：β＊Ｚ３）＝（ｘ３’：ｙ３’：β＊ｚ３’）
である。
【０１１５】
ここで、改めてｘ３’，ｙ３’，ｚ３’，Ｕ１’，Ｕ２’，Ｓ１’，Ｓ２’，Ｈ’，ｒ’を
それぞれ、Ｘ３，Ｙ３，Ｚ３，Ｕ１，Ｕ２，Ｓ１，Ｓ２，Ｈ，ｒとおくと、本発明の加算公式が導き出せる。
（多項式剰余環Ｒ上の楕円曲線のＪａｃｏｂｉａｎ座標の２倍算）
多項式剰余環Ｒ上の楕円曲線のＪａｃｏｂｉａｎ座標の２倍算は、次のようになる。
【０１１６】
Ｓ＝４＊Ｘ１＊Ｙ１＾２
Ｍ＝３＊Ｘ１＾２＋ａ＊Ｚ１＾４＊β＾４
である。β＾２＝ｆ（α）であるので、Ｍ＝３＊Ｘ１＾２＋ａ＊Ｚ１＾４＊ｆ（α）＾２ である。また、
ｘ３＝Ｔ
ｙ３＝−８＊Ｙ１＾４＋Ｍ＊（Ｓ−Ｔ）
ｚ３＝２＊Ｙ１＊Ｚ１＊β
である。
【０１１７】
Ｘ３＝ｘ３，Ｙ３＝ｙ３，Ｚ３＝ｚ３／β＝２＊Ｙ１＊Ｚ１であるので、本発明の２倍算公式が導き出せる。
１．７ 楕円曲線条件判定部５０５
楕円曲線条件判定部５０５は、情報記憶部５０７から、素数ｐ及び位数ｍを読み出し、読み出した位数ｍが素数であり、かつ位数ｍ≠素数ｐであるか否かを判定する。次に、読み出した位数ｍが素数であり、かつ位数ｍ≠素数ｐであるか否かを示す安全性判定情報を制御部５０６へ出力する。
１．８ 制御部５０６
制御部５０６は、入力部５０８から楕円曲線を構成する旨を示す構成指示と素数ｐを受け取る。
【０１１８】
制御部５０６は、前記構成指示を受け付けると、素数ｐを情報記憶部５０７へ書き込み、乱数生成部５０１に対して乱数生成の指示を出力する。
制御部５０６は、乱数生成部５０１、楕円曲線設定部５０２、楕円曲線有限性判定部５０３、楕円曲線位数計算部５０４、楕円曲線条件判定部５０５に対して、この順序で各構成部の処理を実行するように制御する。
【０１１９】
制御部５０６は、楕円曲線有限性判定部５０３から位数判定情報を受け取る。受け取った前記位数判定情報が、位数ｍ１とｍ２が互いに素であることを示す場合には、次に、楕円曲線位数計算部５０４に対してその処理を実行するように制御する。受け取った前記位数判定情報が、位数ｍ１とｍ２が互いに素でないことを示す場合には、次に、楕円曲線位数計算部５０４に対してその処理を中止し、乱数生成部５０１に対してその処理を実行するように制御する。
【０１２０】
制御部５０６は、楕円曲線位数計算部５０４から楕円曲線棄却情報を受け取る。制御部５０６は、楕円曲線棄却情報を受け取ると、楕円曲線条件判定部５０５に対してその処理を中止し、乱数生成部５０１に対してその処理を実行するように制御する。
制御部５０６は、楕円曲線条件判定部５０５から安全性判定情報を受け取る。受け取った安全性判定情報が、位数ｍが素数であり、かつ位数ｍ≠素数ｐであることを示す場合には、情報記憶部５０７からパラメタａ及びｂを読み出し、読み出したパラメタａ及びｂを出力部５０９へ出力する。受け取った安全性判定情報が、位数ｍが素数であり、かつ位数ｍ≠素数ｐであることを示さない場合には、再度、乱数生成部５０１に対してその処理を実行するように制御する。
１．９ 出力部５０９
出力部５０９は、制御部５０６からパラメタａ及びｂを受け取り、受け取ったパラメタａ及びｂをパラメタ記憶部５１０へ書き込む。
１．１０ パラメタ記憶部５１０
パラメタ記憶部５１０は、具体的には、ハードディスク１４から構成され、パラメタａ及びｂを記憶する。
２ 楕円曲線構成装置５００の動作
ここでは、楕円曲線構成装置５００の動作について説明する。
２．１ 楕円曲線構成装置５００の全体の動作
楕円曲線構成装置５００の全体の動作について、図７に示すフローチャートを用いて説明する。
【０１２１】
入力部５０８は、利用者から構成指示と素数ｐの入力を受け付け、制御部５０６は、前記構成指示と素数ｐとを受け取る（ステップＳ１００）。
制御部５０６は、乱数生成部５０１に対して乱数生成の指示を出力し、乱数生成部５０１は、乱数ｔを生成し、生成した乱数ｔを情報記憶部５０７へ書き込む（ステップＳ１０１）。
【０１２２】
楕円曲線設定部５０２は、乱数ｔを読み出し、パラメタａ＝−３と設定し、パラメタｂ＝乱数ｔと設定する（ステップＳ１０２）。
楕円曲線有限性判定部５０３は、素数ｐ１、ｐ２を選択し、有理数体上の楕円曲線を素数ｐ１、ｐ２を法として還元した楕円曲線Ｅｐ１、Ｅｐ２のそれぞれの位数ｍ１、ｍ２を計算、位数ｍ１とｍ２が互いに素であるか判定し（ステップＳ１０３）、制御部５０６は、位数ｍ１とｍ２が互いに素でない場合に（ステップＳ１０４）、ステップＳ１０１へ制御を戻す。
【０１２３】
制御部５０６は、位数ｍ１とｍ２が互いに素である場合に（ステップＳ１０４）、楕円曲線位数計算部５０４に対して位数計算をするように制御し、楕円曲線位数計算部５０４は位数計算をする（ステップＳ１０５）。
制御部５０６は、楕円曲線棄却情報を受け取った場合には（ステップＳ１０６）、ステップＳ１０１へ制御を戻す。
【０１２４】
制御部５０６が、楕円曲線棄却情報を受け取らない場合には（ステップＳ１０６）、
楕円曲線条件判定部５０５は、位数ｍが素数であり、かつ位数ｍ≠素数ｐであるか否かを判定し、「位数ｍが素数であり、かつ位数ｍ≠素数ｐ」である場合に（ステップＳ１０７）、制御部５０６は、出力部５０９に対してパラメタａ、ｂを出力するように制御し、出力部５０９はパラメタａ、ｂを出力する（ステップＳ１０８）。
【０１２５】
「位数ｍが素数であり、かつ位数ｍ≠素数ｐ」でない場合に（ステップＳ１０７）、制御部５０６は、ステップＳ１０１へ制御を戻す。
２．２ 楕円曲線位数計算部５０４の動作
楕円曲線位数計算部５０４の動作について、図８に示すフローチャートを用いて説明する。
【０１２６】
楕円曲線Ｅの位数をｍとし、ｔを
ｍ＝ｐ＋１−ｔ
を満たすものとする。また、
ｆ（ｘ）＝ｘ＾３＋ａｘ＋ｂ
とする。
【０１２７】
楕円曲線位数計算部５０４は、初期値として、整数変数Ｌ＝２とする（ステップＳ９１０）。
楕円曲線位数計算部５０４は、Ｍｏｄｕｌａｒ多項式ΦＬ（Ｔ，ｊ（Ｅ））の一変数Ｔの多項式環ＧＦ（ｐ）［Ｔ］における因数分解の一次因子の数を算出する（ステップＳ９１１）。
【０１２８】
楕円曲線位数計算部５０４は、算出した一次因子の数が２のとき（ステップＳ９１２）、ｔ ｍｏｄ Ｌを求め（ステップＳ９１３）、Ｉｓｏｇｅｎｙ ｃｙｃｌｅ法により、ｔ ｍｏｄ Ｌ＾ｎ（ｎ＝２、３、・・・）を求める（ステップＳ９１４）。
算出した一次因子の数が１またはＬ＋１のとき（ステップＳ９１２）、ｔ ｍｏｄ Ｌを求め（ステップＳ９１５）、Ｉｓｏｇｅｎｙ ｃｙｃｌｅ法を適用可能であるか判定し、適用可能なら（ステップＳ９１６）、Ｉｓｏｇｅｎｙ ｃｙｃｌｅ法により、ｔ ｍｏｄ Ｌ＾ｎ（ｎ＝２，３，．．．）を求める（ステップＳ９１７）。
【０１２９】
算出した一次因子の数が０のとき（ステップＳ９１２）、ｔ ｍｏｄ Ｌの取り得る値を集合［０、１、・・・、Ｌ−１］から絞り込む（ステップＳ９１８）。
次に、楕円曲線位数計算部５０４は、
Ｌ１＾（ｎ１）×Ｌ２＾（ｎ２）×・・・×Ｌｋ＾（ｎｋ）
＜ ４×ｐ＾（１／２）
（ここで、Ｌ１、Ｌ２、・・・、Ｌｋは素数であり、Ｌｋ＝Ｌ）
であるとき（ステップＳ９１９）、Ｌ＝（Ｌの次に大きい素数）とし（ステップＳ９２１）、ステップＳ９１１に戻る。
【０１３０】
そうでないとき（ステップＳ９１９）、楕円曲線位数計算部５０４は、ｍａｔｃｈ＆ｓｏｒｔアルゴリズムにより、位数ｍを確定し、位数ｍを情報記憶部５０７へ書き込む（ステップＳ９２０）。
２．３ 楕円曲線位数計算部５０４のｔ ｍｏｄ Ｌ＾ｎの算出の動作
楕円曲線位数計算部５０４のｔ ｍｏｄ Ｌ＾ｎの算出の動作について図９に示すフローチャートを用いて説明する。
【０１３１】
Ｃａｓｅ１では、まず、楕円曲線位数計算部５０４は、ｎ＝２とし（ステップＳ１３１）、ｋ ｍｏｄ Ｌとｈ（α）を基に多項式Ｈ（α）を求め（ステップＳ１３２）、それを改めて、ｈ（α）とする（ステップＳ１３３）。その多項式ｈ（α）を用いて、ｋ ｍｏｄ Ｌ＾ｎを求める（ステップＳ１３４）。次に、多項式ｈ（α）の次数により、次に進むか否かを判定する。ｈ（α）の次数をｄｅｇ（ｈ（α））とする。そのとき、
（ｄｅｇ（ｈ）＾２）＊Ｌ＾２＊（Ｌ＾（２＊ｎ））
＞ （｜ｐ｜）＾３／１３５ であるか否かを判断する。ここで、｜ｐ｜はｐのビット数である。前記判断式が真であれば（ステップＳ１３５）、
ｔ＝（ｋ＾２＋ｐ）／ｋ ｍｏｄ Ｌ＾ｎ
として（ステップＳ１３７）、Ｉｓｏｇｅｎｙ ｃｙｃｌｅを終了する。偽であれば（ステップＳ１３５）、ｎに１を加算して（ステップＳ１３６）、前記不等式を満たすまで、前記処理を繰り返す。
【０１３２】
こうして、楕円曲線位数計算部５０４は、ｔ ｍｏｄ Ｌ＾ｎを求める。
なお、Ｃａｓｅ２の場合も、楕円曲線位数計算部５０４は、Ｃａｓｅ１と同様に行うが、必ずしもＩｓｏｇｅｎｙ ｃｙｃｌｅが行えるとは限らない。したがって、楕円曲線位数計算部５０４は、Ｉｓｏｇｅｎｙ ｃｙｃｌｅを行えるか否かの判定を行う。
２．４ 楕円曲線位数計算部５０４による楕円曲線上の点の２倍算又は加算の動作
楕円曲線位数計算部５０４は、楕円曲線の冪倍点ｋＰの演算を行う場合、冪倍点ｋＰの演算を、楕円曲線上の点の２倍算又は加算に分解し、分解された２倍算又は加算を行うときに、以下に示す手順による。このとき、２倍算又は加算の種類と、２倍算又は加算の対象となる１個又は２個の楕円曲線上の点のアフィン座標とを以下の手順に対して出力し、下記手順を実施する。分解された２倍算又は加算について、下記手順を繰り返し実施することにより、楕円曲線の冪倍点ｋＰの演算が行われる。
【０１３３】
楕円曲線位数計算部５０４による楕円曲線上の点の２倍算又は加算の動作について、図１０に示すフローチャートを用いて説明する。
楕円曲線位数計算部５０４は、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行う。
【０１３４】
楕円曲線位数計算部５０４は、２倍算の演算対象となる楕円曲線Ｅ上の１個の点のアフィン座標と２倍算を示す演算情報とを取得し、又は、加算の演算対象となる楕円曲線Ｅ上の２個の異なる点のアフィン座標と、加算を示す演算情報とを受け取る。ここで、楕円曲線Ｅ上の２個の異なる点のアフィン座標は、
（Ｘ１（α）、β×Ｙ１（α））及び
（Ｘ２（α）、β×Ｙ２（α））であり、
楕円曲線Ｅ上の１個の点のアフィン座標は、
（Ｘ１（α）、β×Ｙ１（α））である（ステップＳ１２１）。
【０１３５】
次に、楕円曲線位数計算部５０４は、受け取った１個又は２個のアフィン座標に対して、座標変換を施して、それぞれ１個又は２個の射影座標を生成する。前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、
多項式Ｘ（α）＝ｆ（α）×φ（α）、
多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び
多項式Ｚ（α）＝１により変換して
射影座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成する。ここで、生成された２個の射影座標は、
（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び
（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））であり、
生成された１個の射影座標は、
（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））である（ステップＳ１２２）。
【０１３６】
次に、楕円曲線位数計算部５０４は、演算情報が加算であるか２倍算であるかを判定し、加算である場合に（ステップＳ１２３）、
演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、
演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、
演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、
演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、
演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び
演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い（ステップＳ１２４）、
次に、
演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、
演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び
演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行う（ステップＳ１２５）。
【０１３７】
楕円曲線位数計算部５０４は、２倍算である場合に（ステップＳ１２３）、
演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、
演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び
演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い（ステップＳ１２６）、次に、
演算Ｘ３（α）＝Ｔ（α）、
演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び
演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行う（ステップＳ１２７）。
【０１３８】
次に、楕円曲線位数計算部５０４は、射影座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出して出力する（ステップＳ１２８）。
３ まとめ
楕円曲線設定部は、あらかじめ安全性の高い楕円曲線を選択する確率が高いので、楕円曲線を選択しその安全性を判定するステップを何度も繰り返すことがなく、楕円曲線構成装置における計算量が減少する。
【０１３９】
また、楕円曲線有限性判定部により、位数計算を行う前に、楕円曲線が有限位数を有する点を持つか否かを判定することにより、前記楕円曲線の安全性が高いか否かを判定するので、位数計算を行うことなく、安全性の低い楕円曲線を棄却することができ、無駄な位数計算を省略して、楕円曲線構成装置における計算量が減少する。
【０１４０】
また、楕円曲線位数計算部における楕円曲線の冪倍点ｋＰの演算は、加算に比べ、２倍算の繰り返し回数が多い。一般に、ｋＰの計算量は、楕円曲線の加算演算の計算量をＥＡ、２倍算演算の計算量をＥＤとすると
｜ｋ｜×（ＥＤ＋ＥＡ／３）
で与えられる。ここで、｜ｋ｜はｋのビット数である。なお、これはＳｉｇｎｅｄ Ｂｉｎａｒｙ ｍｅｔｈｏｄという計算法を用いた場合である。この計算法を用いると、従来例３によるｋＰの計算量は１７×ＰＭｕｌ×｜ｋ｜であり、本発明によるｋＰの計算量は１５．３×ＰＭｕｌ×｜ｋ｜である。したがって、本発明によるｋＰの計算量の減少の効果は大きい。
４ その他の変形例
以上、本発明に係る楕円曲線構成装置について、実施の形態に基づいて説明したが、本発明はこれらの実施の形態に限られないことは勿論である。次のように構成してもよい。
（１）本発明は、上記に説明した楕円曲線構成装置を備える楕円曲線応用装置であるとしてもよい。楕円曲線応用装置の具体的な例は、暗号化装置及び暗号解読装置からなる暗号通信システム、デジタル署名装置及び署名検証装置からなるデジタル署名システム、誤り訂正符号送信装置及び誤り訂正装置誤りからなる訂正通信システムである。
【０１４１】
前記暗号通信システムは、楕円曲線を利用して、特定の通信相手以外に通信内容を漏らすことなく通信を行なう。前記デジタル署名システムは、楕円曲線を利用して、通信相手に通信内容の正当性を示したり、本人であることを証明する。前記誤り訂正通信システムは、楕円曲線を利用して、通信回線上で欠落した情報、変化した情報を回復して、元の情報を生成する。
（２）楕円曲線設定部５０２は、楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａｘ＋ｂにおけるパラメタａ、ｂについて、ａ＝−３と設定し、ｂ＝ｔと設定しているが、次のようにしてもよい。
【０１４２】
楕円曲線設定部５０２は、有理数体上の曲線Ｅ：ｙ＾２＝ｘ＾３＋ａｘ＋ｂ（ａ、ｂは整数）に対して、前述の判別式ＴＤを定義し、判別式ＴＤが平方因子を持つ確率が所定のしきい値より小さくなるように、パラメタａ、ｂを選択する。ここで、一例として、前記所定のしきい値は、０．００１である。この場合に、上記の実施の形態で説明したように、楕円曲線の安全性が高くなると期待できる。
（３）本発明は、楕円曲線位数計算部５０４に示す多項式剰余環上で定義された楕円曲線上の点の演算を行う楕円曲線演算装置であるとしてもよい。
（４）本発明は、楕円曲線位数計算部５０４に示す楕円曲線の位数を計算する楕円曲線位数計算装置であるとしてもよい。
（５）本発明は、本実施の形態に示す楕円曲線演算方法、楕円曲線位数計算方法及び楕円曲線構成方法であるとしてもよい。
【０１４３】
また、これらの楕円曲線演算方法、楕円曲線位数計算方法及び楕円曲線構成方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるデジタル信号であるとしてもよい。
また、本発明は、前記コンピュータプログラム又は前記デジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フロッピーディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、半導体メモリなど、に記録したものとしてもよい。また、これらの記録媒体に記録されている前記コンピュータプログラム又は前記デジタル信号であるとしてもよい。
【０１４４】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号を、電気通信回線、無線又は有線通信回線、インターネットを代表とするネットワーク等を経由して伝送するものとしてもよい。
（６）本発明は、上記に示す実施の形態、複数の変形例、又は上記実施の形態及び複数の変形例の一部を組み合わせるとしてもよい。
【０１４５】
【発明の効果】
上記に説明したように、本発明は、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行う楕円曲線演算装置であって、外部から楕円曲線Ｅ上の１個以上の点のアフィン座標と、２倍算又は加算の種類を示す演算情報とを取得する取得手段と、取得した１個以上のアフィン座標に対して、次に示す座標変換を施して、１個以上のＪａｃｏｂｉａｎ座標を生成する変換手段とを備え、前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、多項式Ｘ（α）＝ｆ（α）×φ（α）、多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び多項式Ｚ（α）＝１により変換してＪａｃｏｂｉａｎ座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成し、さらに、前記Ｊａｃｏｂｉａｎ座標上における２倍算及び加算を有し、前記生成された１個以上のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される前記２倍算又は前記加算を施して楕円曲線Ｅ上の１個のＪａｃｏｂｉａｎ座標を算出する演算手段を備える。
【０１４６】
ここで、前記取得手段は、楕円曲線Ｅ上の１個の点のアフィン座標と２倍算を示す演算情報とを取得し、又は、楕円曲線Ｅ上の２個の異なる点のアフィン座標と、加算を示す演算情報とを取得し、前記変換手段は、取得した１個又は２個のアフィン座標に対して、前記座標変換を施して、それぞれ１個又は２個のＪａｃｏｂｉａｎ座標を生成し、前記演算手段は、前記生成された１個又は２個のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される２倍算又は加算をそれぞれ施すように構成してもよい。
【０１４７】
ここで、前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は加算であり、前記取得手段は、楕円曲線Ｅ上の２個の異なる点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））並びに加算を示す演算情報を取得し、前記変換手段は、前記２個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））に対して、前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、前記演算手段は、演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、次に、演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１４８】
ここで、前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は２倍算であり、前記取得手段は、楕円曲線Ｅ上の１個の点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、前記変換手段は、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、前記演算手段は、演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、次に、演算Ｘ３（α）＝Ｔ（α）、演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１４９】
ここで、前記取得手段は、楕円曲線Ｅ上の２個の異なる点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））並びに加算を示す演算情報を取得し、又は、楕円曲線Ｅ上の１個の点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、前記変換手段は、前記２個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））に対して、前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、又は、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、前記演算手段は、取得した前記演算情報が加算を示す場合には、演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、次に、演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出し、取得した前記演算情報が２倍算を示す場合には、演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、次に、演算Ｘ３（α）＝Ｔ（α）、演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１５０】
これらの構成によると、従来例と比較して、加算公式の多項式乗算の計算量は、１ＰＭｕｌ増加し、２倍算公式の計算量は、２ＰＭｕｌ減少する。通常、２倍算の演算回数は、加算の演算回数より多いので、２倍算の計算量の減少は、全体の計算量の減少に大きく貢献し、楕円曲線演算装置における計算量が減少するという効果がある。
【０１５１】
また、本発明は、ＳＥＡアルゴリズムにより楕円曲線の位数計算を行う楕円曲線位数計算装置であって、前記楕円曲線位数計算装置は、上記の楕円曲線演算装置を含む。
ここで、前記楕円曲線位数計算装置は、上記の楕円曲線演算装置を含むように構成してもよい。
【０１５２】
ここで、前記楕円曲線位数計算装置は、上記の楕円曲線演算装置を含むように構成してもよい。
これらの構成によると、従来例と比較して、加算公式の多項式乗算の計算量は、１ＰＭｕｌ増加し、２倍算公式の計算量は、２ＰＭｕｌ減少する。通常、２倍算の演算回数は、加算の演算回数より多いので、２倍算の計算量の減少は、全体の計算量の減少に大きく貢献し、楕円曲線位数計算装置における計算量が減少するという効果がある。
【０１５３】
また、本発明は、ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定する楕円曲線構成装置であって、乱数を生成する乱数生成手段と、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、前記乱数を含む楕円曲線Ｅのパラメタを選択するパラメタ生成手段と、前記選択されたパラメタにより特定される楕円曲線Ｅが有理数体上において有限位数を有する点を持つか否かを判定する有限性判定手段と、前記楕円曲線Ｅが有限位数を有する点を持たないと判定された場合に、前記楕円曲線Ｅの位数ｍを計算する位数計算手段と、前記位数ｍが計算された場合に、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであるという条件を満たすか否かを判定する安全性判定手段と、前記安全性判定手段により、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定されるまで、前記乱数生成手段、前記パラメタ生成手段、前記有限性判定手段、前記位数計算手段及び前記安全性判定手段に対して、それぞれ、乱数生成、パラメタ生成、有限性判定、位数計算及び安全性判定をするように制御する繰返制御手段と、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定された場合に、前記選択されたパラメタを出力するパラメタ出力手段とを備える。
【０１５４】
この構成によると、パラメタ生成手段により、あらかじめ安全性の高い楕円曲線が選択される確率が高いので、楕円曲線を選択しその安全性を判定するステップを何度も繰り返すことがなく、楕円曲線構成装置における計算量が減少するという効果がある。
また、有限性判定手段により、位数計算を行う前に、楕円曲線が有限位数を有する点を持つか否かを判定することにより、前記楕円曲線の安全性が高いか否かを判定するので、位数計算を行うことなく、安全性の低い楕円曲線を棄却することができ、無駄な位数計算を省略し、楕円曲線構成装置における計算量が減少するという効果がある。
【０１５５】
ここで、前記楕円曲線Ｅは、ｙ＾２＝ｘ＾３＋ａｘ＋ｂにより示され、ここで、パラメタａ及びパラメタｂは定数であり、前記パラメタ生成手段は、パラメタａ＝−３とし、パラメタｂを前記生成された乱数として選択することにより、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、パラメタを選択するように構成してもよい。
【０１５６】
この構成によると、パラメタ生成手段は、あらかじめ安全性の高い楕円曲線として、楕円曲線Ｅ：ｙ＾２＝ｘ＾３−３ｘ＋ｂを選択するので、楕円曲線を選択しその安全性を判定するステップを何度も繰り返すことがなく、楕円曲線構成装置における計算量が減少するという効果がある。
ここで、前記有限性判定手段は、楕円曲線Ｅを有理数体上の楕円曲線ＥＱとみなし、２個の素数ｐ１、ｐ２をあらかじめ有し、ｐ１≠ｐ２であり、２個の素数ｐ１、ｐ２を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出し、算出された位数ｍ１、ｍ２が互いに素であることを判定し、互いに素であると判定する場合に、楕円曲線Ｅが有理数体上において有限位数の点を持たないと判定するように構成してもよい。
【０１５７】
この構成によると、有限性判定手段により、位数計算を行う前に、２個の素数ｐ１、ｐ２を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２が互いに素であることを判定することにより、前記楕円曲線の安全性が高いか否かを判定するので、位数計算を行うことなく、安全性の低い楕円曲線を棄却することができるので、無駄な位数計算を省略することができ、楕円曲線構成装置における計算量が減少するという効果がある。
【０１５８】
ここで、前記有限性判定手段は、素数ｐ１＝５及び素数ｐ２＝７をあらかじめ有し、２個の素数ｐ１＝５、ｐ２＝７を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出するように構成してもよい。
この構成によると、有限性判定手段は、素数ｐ１＝５及び素数ｐ２＝７を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２が互いに素であることを判定するので、判定に要する計算量を最も少なくすることができるという効果がある。
【０１５９】
ここで、前記位数計算手段は、ＳＥＡアルゴリズムにより楕円曲線の位数計算を行い、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の点に対して２倍算又は加算を施す楕円曲線演算手段を含み、前記楕円曲線演算手段は、上記の楕円曲線演算装置を含むように構成してもよい。
【０１６０】
これらの構成によると、従来例と比較して、加算公式の多項式乗算の計算量は、１ＰＭｕｌ増加し、２倍算公式の計算量は、２ＰＭｕｌ減少する。通常、２倍算の演算回数は、加算の演算回数より多いので、２倍算の計算量の減少は、全体の計算量の減少に大きく貢献し、楕円曲線構成装置における計算量が減少するという効果がある。
【０１６１】
また、本発明は、楕円曲線を用いて処理を行う楕円曲線応用装置であって、前記楕円曲線応用装置は、ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定する楕円曲線構成手段を含み、前記楕円曲線構成手段は、上記の楕円曲線構成装置を備えるように構成してもよい。
【０１６２】
この構成によると、楕円曲線応用装置は、前記楕円曲線構成装置と同様の効果を奏する。こうして、高速に安全な暗号方式や署名方式を可能にする楕円曲線応用装置を提供することができ，その実用的価値は大きい。
また、本発明は、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行い、取得手段と変換手段と演算手段とを備える装置で用いられる楕円曲線演算方法であって、前記取得手段により、外部から楕円曲線Ｅ上の１個以上の点のアフィン座標と、２倍算又は加算の種類を示す演算情報とを取得する取得ステップと、前記変換手段により、取得した１個以上のアフィン座標に対して、次に示す座標変換を施して、１個以上のＪａｃｏｂｉａｎ座標を生成する変換ステップとを含み、前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、多項式Ｘ（α）＝ｆ（α）×φ（α）、多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び多項式Ｚ（α）＝１により変換してＪａｃｏｂｉａｎ座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成し、さらに、前記Ｊａｃｏｂｉａｎ座標上における２倍算及び加算を有し、前記演算手段により、前記生成された１個以上のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される前記２倍算又は前記加算を施して楕円曲線Ｅ上の１個のＪａｃｏｂｉａｎ座標を算出する演算ステップを含む。
【０１６３】
この方法を用いると、前記楕円曲線演算装置と同様の効果を奏する。
また、本発明は、ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定し、乱数生成手段とパラメタ生成手段と有限性判定手段と位数計算手段と安全性判定手段と繰返制御手段とパラメタ出力手段とを備える楕円曲線構成装置で用いられる楕円曲線構成方法であって、前記乱数生成手段により、乱数を生成する乱数生成ステップと、前記パラメタ生成手段により、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、前記乱数を含む楕円曲線Ｅのパラメタを選択するパラメタ生成ステップと、前記有限性判定手段により、前記選択されたパラメタにより特定される楕円曲線Ｅが有理数体上において有限位数を有する点を持つか否かを判定する有限性判定ステップと、前記位数計算手段により、前記楕円曲線Ｅが有限位数を有する点を持たないと判定された場合に、前記楕円曲線Ｅの位数ｍを計算する位数計算ステップと、前記安全性判定手段により、前記位数ｍが計算された場合に、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであるという条件を満たすか否かを判定する安全性判定ステップと、前記安全性判定ステップにより、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定されるまで、前記乱数生成ステップ、前記パラメタ生成ステップ、前記有限性判定ステップ、前記位数計算ステップ及び前記安全性判定ステップに対して、それぞれ、乱数生成、パラメタ生成、有限性判定、位数計算及び安全性判定をするように、前記繰返制御手段により、制御する繰返制御ステップと、前記パラメタ出力手段により、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定された場合に、前記選択されたパラメタを出力するパラメタ出力ステップとを含む。
【０１６４】
この方法を用いると、前記楕円曲線構成装置と同様の効果を奏する。
また、本発明は、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行い、取得手段と変換手段と演算手段とを備える楕円曲線演算装置で用いられる楕円曲線演算プログラムを記録しているコンピュータ読み取り可能な記録媒体であって、前記プログラムは、前記取得手段により、外部から楕円曲線Ｅ上の１個以上の点のアフィン座標と、２倍算又は加算の種類を示す演算情報とを取得する取得ステップと 前記変換手段により、取得した１個以上のアフィン座標に対して、次に示す座標変換を施して、１個以上のＪａｃｏｂｉａｎ座標を生成する変換ステップとを含み、前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、多項式Ｘ（α）＝ｆ（α）×φ（α）、多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び多項式Ｚ（α）＝１により変換してＪａｃｏｂｉａｎ座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成し、さらに、前記Ｊａｃｏｂｉａｎ座標上における２倍算及び加算を有し、前記演算手段により、前記生成された１個以上のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される前記２倍算又は前記加算を施して楕円曲線Ｅ上の１個のＪａｃｏｂｉａｎ座標を算出する演算ステップを含む。
【０１６５】
ここで、前記取得ステップは、楕円曲線Ｅ上の１個の点のアフィン座標と２倍算を示す演算情報とを取得し、又は、楕円曲線Ｅ上の２個の異なる点のアフィン座標と、加算を示す演算情報とを取得し、前記変換ステップは、取得した１個又は２個のアフィン座標に対して、前記座標変換を施して、それぞれ１個又は２個のＪａｃｏｂｉａｎ座標を生成し、前記演算ステップは、前記生成された１個又は２個のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される２倍算又は加算をそれぞれ施すように構成してもよい。
【０１６６】
ここで、前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は加算であり、前記取得ステップは、楕円曲線Ｅ上の２個の異なる点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））並びに加算を示す演算情報を取得し、前記変換ステップは、前記２個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））に対して、前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、前記演算ステップは、演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、次に、演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１６７】
ここで、前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は２倍算であり、前記取得ステップは、楕円曲線Ｅ上の１個の点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、前記変換ステップは、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、前記演算ステップは、演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、次に、演算Ｘ３（α）＝Ｔ（α）、演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１６８】
ここで、前記取得ステップは、楕円曲線Ｅ上の２個の異なる点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））並びに加算を示す演算情報を取得し、又は、楕円曲線Ｅ上の１個の点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、前記変換ステップは、前記２個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））に対して、前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、又は、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、前記演算ステップは、取得した前記演算情報が加算を示す場合には、演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、次に、演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出し、取得した前記演算情報が２倍算を示す場合には、演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、次に、演算Ｘ３（α）＝Ｔ（α）、演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１６９】
このプログラムをコンピュータにより実行することにより、前記楕円曲線演算装置と同様の効果を奏する。
また、本発明は、ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定し、乱数生成手段とパラメタ生成手段と有限性判定手段と位数計算手段と安全性判定手段と繰返制御手段とパラメタ出力手段とを備えている楕円曲線構成装置で用いられる楕円曲線構成プログラムを記録しているコンピュータ読み取り可能な記録媒体あって、前記プログラムは、前記乱数生成手段により、乱数を生成する乱数生成ステップと、前記パラメタ生成手段により、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、前記乱数を含む楕円曲線Ｅのパラメタを選択するパラメタ生成ステップと、前記有限性判定手段により、前記選択されたパラメタにより特定される楕円曲線Ｅが有理数体上において有限位数を有する点を持つか否かを判定する有限性判定ステップと、前記位数計算手段により、前記楕円曲線Ｅが有限位数を有する点を持たないと判定された場合に、前記楕円曲線Ｅの位数ｍを計算する位数計算ステップと前記安全性判定手段により、前記位数ｍが計算された場合に、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであるという条件を満たすか否かを判定する安全性判定ステップと、前記安全性判定ステップにより、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定されるまで、前記乱数生成ステップ、前記パラメタ生成ステップ、前記有限性判定ステップ、前記位数計算ステップ及び前記安全性判定ステップに対して、それぞれ、乱数生成、パラメタ生成、有限性判定、位数計算及び安全性判定をするように、前記繰返制御手段により、制御する繰返制御ステップと、前記パラメタ出力手段により、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定された場合に、前記選択されたパラメタを出力するパラメタ出力ステップとを含む。
【０１７０】
ここで、前記楕円曲線Ｅは、ｙ＾２＝ｘ＾３＋ａｘ＋ｂにより示され、ここで、パラメタａ及びパラメタｂは定数であり、前記パラメタ生成ステップは、パラメタａ＝−３とし、パラメタｂを前記生成された乱数として選択することにより、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるようにパラメタを選択するように構成してもよい。
【０１７１】
ここで、前記有限性判定ステップは、楕円曲線Ｅを有理数体上の楕円曲線ＥＱとみなし、２個の素数ｐ１、ｐ２をあらかじめ有し、ｐ１≠ｐ２であり、２個の素数ｐ１、ｐ２を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出し、算出された位数ｍ１、ｍ２が互いに素であることを判定し、互いに素であると判定する場合に、楕円曲線Ｅが有理数体上において有限位数の点を持たないと判定するように構成してもよい。
【０１７２】
ここで、前記有限性判定ステップは、素数ｐ１＝５及び素数ｐ２＝７をあらかじめ有し、２個の素数ｐ１＝５、ｐ２＝７を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出するように構成してもよい。
このプログラムをコンピュータにより実行することにより、前記楕円曲線構成装置と同様の効果を奏する。
【図面の簡単な説明】
【図１】従来の楕円曲線の構成方法を示すフローチャートである。
【図２】従来のＬｅｒｃｉｅｒによる楕円曲線の構成方法を示すフローチャートである。図３へ続く。
【図３】従来のＬｅｒｃｉｅｒによる楕円曲線の構成方法を示すフローチャートである。図２から続く。
【図４】本発明に係る１の実施の形態としての楕円曲線構成装置５００の構成を示すブロック図である。
【図５】楕円曲線構成装置５００の具体的な構成を示すブロック図である。
【図６】楕円曲線構成装置５００の情報記憶部５０７に記憶されているデータの一例を示す。
【図７】楕円曲線構成装置５００の楕円曲線の構成の手順を示すフローチャートである。
【図８】楕円曲線構成装置５００の楕円曲線位数計算部５０４による楕円曲線の位数計算の手順を示すフローチャートである。
【図９】楕円曲線構成装置５００の楕円曲線位数計算部５０４によるｔ ｍｏｄ Ｌ＾ｎの算出の手順を示すフローチャートである。
【図１０】楕円曲線構成装置５００の楕円曲線上の点の加算又は２倍算の手順を示すフローチャートである。
【符号の説明】
５００ 楕円曲線構成装置
５０１ 乱数生成部
５０２ 楕円曲線設定部
５０３ 楕円曲線有限性判定部
５０４ 楕円曲線位数計算部
５０５ 楕円曲線条件判定部
５０６ 制御部
５０７ 情報記憶部
５０８ 入力部
５０９ 出力部
５１０ パラメタ記憶部５１０[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a calculation technique for an elliptic curve and an application technique for the elliptic curve.
[0002]
[Prior art]
In recent years, elliptic curves have been used in cryptographic communication technology. The basis of security in the cryptographic communication is a discrete logarithm problem.
As typical discrete logarithm problems, there are those defined on a finite field and those defined on an elliptic curve. These are described in detail in "A Course in Number theory and Cryptography" (Neal Koblitz, Springer-Verlag, 1987). The discrete logarithm problem on an elliptic curve is described below.
(Discrete logarithm problem on elliptic curve)
The discrete logarithm problem on an elliptic curve is
Let E (GF (p)) be an elliptic curve defined on the finite field GF (p), and if the order of the elliptic curve E is divisible by a large prime number, the element G on the elliptic curve E is the base point. Here, the order of the elliptic curve indicates the number of points on the elliptic curve whose coordinate components belong to GF (p). At this time, for a given element Y on the elliptic curve E,
Y = xG
If there is an integer x such that, the problem is to find the integer x.
[0003]
Here, p is a prime number, and the finite field GF (p) has p elements.
(Safe elliptic curve conditions)
Various cryptanalysis methods have been proposed for the discrete logarithm problem on an elliptic curve, and it is necessary to construct a safe elliptic curve for these cryptanalysis methods.
In this specification, “constituting an elliptic curve” means an elliptic curve.
y ^ 2 = x ^ 3 + ax + b
In this case, the values of parameters a and b are determined. Further, in this specification, the symbol ^ indicates an operation by power, for example, x ^ 3 indicates x to the third power.
[0004]
The safe elliptic curve condition for all existing cryptanalysis is the elliptic curve over the finite field GF (p):
(A) the order of the elliptic curve is not any of p-1, p and p + 1, and
(B) The elliptic curve has a large prime factor.
Thus, the safety of an elliptic curve can be confirmed by examining the order of the elliptic curve.
[0005]
According to "Cryptography / Zero Knowledge Proof, Number Theory" (pages 155-156, supervised by the Information Processing Society of Japan, Tatsuaki Okamoto and Kazuo Ota, Kyoritsu Shuppan, 1995) The calculation time required for is the exponential time for the maximum prime factor of the order.
(How to construct an elliptic curve)
As a method of constructing an elliptic curve,
(1) Configuration method using CM (Complex Multiplexing) method
(2) Configuration method using order calculation algorithm
There is.
[0006]
The configuration method shown in (1) has a characteristic that an elliptic curve can be easily configured, but has a property that an elliptic curve cannot be configured randomly. This construction method is described in detail in “On Ordinary Elliptic Curve Cryptosystems” (A. Miyaji, ASIACRYPT '91, Springer-Verlag, 1991, pages 460 to 469). In addition, the configuration method shown in (2) has a feature that an elliptic curve can be formed at random, but the time required for the configuration of the elliptic curve is long.
(Conventional example 1: Composition of elliptic curve by order calculation algorithm)
A method of constructing an elliptic curve by the order calculation algorithm will be described with reference to the flowchart shown in FIG. This configuration method is described in detail in “Ellitpic Curve Implementation of Zero-Knowledge Blobs” (N. Koblitz, J. Cryptology, vol. 4 No. 3, 1991, pages 207 to 213). .
[0007]
According to this configuration method, a random number is generated (step S901), a parameter for determining an elliptic curve is generated using the generated random number (step S902), and the order of the elliptic curve is calculated using the generated parameter. (Step S903). Next, the safety of the elliptic curve is determined by determining whether or not a given safe elliptic curve condition is satisfied using the calculated order. Only when the given condition is satisfied (step S904), the generated elliptic curve parameters are output. If not satisfied (step S904), the process returns to step S901 to generate random numbers, generate elliptic curve parameters, calculate the order of the elliptic curve, and determine the elliptic curve until the above condition is satisfied. And repeat.
[0008]
In the configuration method using the order calculation algorithm described above, the calculation time is long. In particular, it is the order calculation of an elliptic curve that requires a long calculation time.
One of the algorithms for calculating the order of an elliptic curve is the Schouch algorithm. This algorithm consists of a polynomial time algorithm. Here, the polynomial time algorithm is an algorithm whose calculation time is on the order of a polynomial. The calculation time according to the Schuch algorithm is not a practical calculation time.
(Conventional example 2: Order calculation method of elliptic curve by SEA algorithm)
Schoff's algorithm has been improved as an SEA algorithm by Elkies and Atkin.
[0009]
As for this order calculation method, “Counting the number of points on elliptic curves over finite fields: strategies performances” (R.Lercier, F.Morain, EUROCRYPT'95, Springer-Verlag, 1995, p. 79- 94 page).
In the SEA algorithm, t mod L ^ n (n = 1, 2, 3,...) Is obtained. This calculation can be performed by calculating an eigenvalue of a map called a Frobenius map. Specifically, k in the following equation is obtained using the L equally dividing point (α, β) on the elliptic curve E.
[0010]
(Α ^ p, β ^ p) = k (α, β)
Here, k (α, β) is a k-fold point on the elliptic curve of the point (α, β). The above equation is calculated by elliptic curve calculation on a polynomial remainder ring with respect to α and β modulo a polynomial β ^ 2-f (α) with α and β as variables and an element on GF (p) as a coefficient. Do. In this calculation, since the calculation amount of the inverse element of the polynomial is larger than the calculation amount of multiplication, ternary coordinate is used. Conventionally, projective coordinates are used as the trinomial coordinates. The use of this projective coordinate can be naturally inferred from the conventional use of the projective coordinate of an elliptic curve on a finite field. For conventional projective coordinates, see "Efficient elliptic curve exponentiation" (Miyaji, Ono, Cohen, Advances in cryptology-proceedings of ICICS'97, Lecture notes in computer science, 1997, Springer-verlag, pages 282-290. ).
(Conventional example 3: Calculation method of k times point (α, β) on elliptic curve)
The calculation of the k-fold point of the point (α, β) on the elliptic curve is performed by adding and doubling the calculation of the k-fold point as follows.
[0011]
(Α, β) is converted to (α: β: 1), and (X (α): β × Y (α): Z (α)) (X (α) = α, Y (α) = Z ( Consider α) = 1).
Here, “(,)” indicates affine coordinates, and “(: :)” indicates projective coordinates.
When placed in this way, the elliptic curve calculation is as follows.
[0012]
here,
P1 = (X1 (α): β × Y1 (α): Z1 (α)),
P2 = (X2 (α): β × Y2 (α): Z2 (α)),
P3 = P1 + P2 = (X3 (α): β × Y3 (α): Z3 (α))
far.
[0013]
In this specification, the operator x and the operator * in the addition formula or the doubling formula both indicate the same multiplication. When evaluating the number of multiplications in the addition formula or the doubling formula, the multiplication that appears for the first time is indicated by the operator *, and other multiplications are indicated by the operator x. In each formula, the number of multiplications can be calculated by counting the number of occurrences of the operator *.
(1) Addition formula
When P1 ≠ ± P2, it is an addition operation, and the addition formula is as follows.
[0014]
X3 = v * A
Y3 = u * (v ^ 2 * X1 * Z2-A) -v ^ 3 * (Y1 * Z2)
Z3 = v ^ 3 * (Z1 × Z2)
here,
u = Y2 * Z1-Y1 * Z2,
v = X2 * Z1-X1 * Z2,
A = u ^ 2 * f ([alpha]) * Z1 * Z2-v ^ 3-2 * v ^ 2 * X1 * Z2
= ((U * u) * f (α)) * (Z1 * Z2)
− (V * v) * v−2 × v ^ 2 * (X1 × Z2)
It is.
[0015]
Note that, in each arithmetic expression shown above, X1, Y1, Z1, X2, Y2, Z2, X3, Y3, Z3, u, v, and A are polynomials related to the variable α, so X1 (α), Y1 Although it should be expressed as (α), Z1 (α), etc., in order to simplify the description, (α) is omitted and attention is required.
(2) doubling formula
In the case of P1 = P2, a doubling operation is performed, and the doubling formula is as follows.
[0016]
X3 = 2 × h * (s × f (α))
Y3 = w * (4 * Bh) -8 * Y1 ^ 2 * s ^ 2 * f ([alpha]) ^ 2
= W * (4 × B−h)
−8 × (Y1 × s × f (α)) * (Y1 × s × f (α))
Z3 = 8 * s ^ 3 * f (α) ^ 2
= 8 × s * (s × f (α)) * (s × f (α))
here,
w = a * Z1 ^ 2 + 3 * X1 ^ 2
= A × (Z1 * Z1) + 3 × (X1 * X1),
s = Y1 * Z1,
B = X1 * (Y1 * (s * f (α))),
h = w ^ 2-8 × B
= W * w-8xB
It is.
[0017]
Here, f (x) = x ^ 3 + ax + b.
In each of the arithmetic expressions shown above, X1, Y1, Z1, X3, Y3, Z3, w, s, B, and h are polynomials related to the variable α, as in the case of the addition formula. For the sake of simplicity, (α) is omitted.
The number of multiplications in the addition formula and the doubling formula is 15 times and 12 times, respectively, as can be seen from counting the number of occurrences of the operator *. When the calculation amount of the polynomial multiplication is PMul, the calculation amounts by the addition formula and the doubling formula are 15 × PMul and 12 × PMul, respectively.
[0018]
In counting the number of multiplications, the amount of calculation by multiplication of (constant) × (polynomial), such as a × (Z1 ^ 2) or 3 × (X1 ^ 2), is (polynomial) × (polynomial). Since it is small compared with the amount of calculation by multiplication, the above-mentioned multiplication count is ignored. Further, when the same multiplication is repeated twice or more, the second and subsequent multiplications can be performed because the first multiplication result can be used. For this reason, the second and subsequent multiplications are not counted when counting the number of multiplications.
(Conventional example 4: Elliptic curve construction method using SEA algorithm)
Lercier is an elliptic curve using the SEA algorithm in “Finding Good Random Elliptic Curves for Cryptosystems Defined over F (2 ^ n)” (R.Lercier, EUROCRYPT'97, Springer-Verlag, 1997, pages 379-392). A configuration method is proposed. In this elliptic curve construction method, the given condition in the elliptic curve construction method shown in Conventional Example 1 is set as “the order of the elliptic curve is a prime number”.
[0019]
The elliptic curve construction method using the SEA algorithm by Lercier will be described with reference to the flowcharts shown in FIGS.
Here, p is a prime number and this is an input value. An elliptic curve on the finite field GF (p) is E, and a twist of the elliptic curve E is E ′. In this case, if the order of E is p + 1−t, the order of E ′ is p + 1 + t.
[0020]
The element u of the finite field GF (p) is randomly selected (step S931), the parameters of the elliptic curve E are determined based on the element u (step S932), and the flag flag # ell and the flag flag # twist are set as initial values. Is set to 1 (step S933).
Next, the orders of the elliptic curves E and E ′ are calculated using the SEA algorithm (step S934).
[0021]
When the order of E is divisible by L (step S935), flag # ell = 0 is set (step S936), and when the order of E ′ is divisible by L (step S937), flag # twist = 0 is set (step S938). , Flag # ell = 0 and flag # twist = 0 (step S940), the process returns to step S931. Otherwise (step S940), the process proceeds to the next step S941.
[0022]
Next, when flag # ell = 1 (step S941), the order of E is determined as a prime number. If the order of E is not a prime number (step S942), the process proceeds to step S943. If it is a prime number (step S942), the process proceeds to the next step S945. If flag # twist = 1 (step S943), the order of E ′ is determined as a prime number. If the order of E ′ is not a prime number (step S944), the process returns to step S931. If it is a prime number (step S944), the process proceeds to the next step S945. When flag # twist = 1 is not satisfied (step S943), the process proceeds to step S931.
[0023]
It is determined whether or not order = p, and when order = p (step S945), the process returns to step S931. When the order is not p (step S945), an elliptic curve parameter is output (step S946).
In the elliptic curve construction method by Lercier, the operation in step S933 is a technique used to shorten the calculation time. By doing this, the time required for the SEA algorithm is reduced. However, in step S932, since the elliptic curve parameters are determined including the possibility that the order of the elliptic curve E is a prime number, the number of times of repeating step S934 including the calculation process by the SEA algorithm is increased. . For this reason, the total calculation amount increases.
[0024]
[Problems to be solved by the invention]
As described above, the Schof's order calculation algorithm used in the construction of the elliptic curve is improved by the SEA algorithm, and Lercier proposes a method for further reducing the calculation amount required for the SEA algorithm. Furthermore, there is a demand for reducing the amount of calculation of elliptic curves.
[0025]
A first object of the present invention is to provide an elliptic curve calculation device capable of calculating points on an elliptic curve with a small amount of calculation.
A second object of the present invention is to provide an elliptic curve order calculator that can calculate the order of an elliptic curve with a small amount of calculation.
A third object of the present invention is to provide an elliptic curve construction device that can construct an elliptic curve with high safety with a small amount of calculation.
[0026]
A fourth object of the present invention is to provide an elliptic curve application device that applies an elliptic curve configured to increase safety with a small amount of calculation.
[0027]
[Means for Solving the Problems]
In order to achieve the above object, the present invention provides a polynomial β ^ 2-f (α) (where f (α) = α ^ 3 + aα + b, where a and b are constants) and a polynomial h (α ) (Where h (α) is a polynomial with respect to α) and the elliptic curve E on the two-variable polynomial remainder ring with respect to the variables α and β modulo: double over y ^ 2 = f (x) An elliptic curve calculation device that performs calculation or addition, an acquisition unit that acquires affine coordinates of one or more points on the elliptic curve E and calculation information indicating a type of doubling or addition from the outside; Conversion means for generating one or more Jacobiian coordinates by performing the following coordinate conversion on the one or more affine coordinates, and the coordinate conversion includes the affine coordinates ( φ (α), β × ψ (α)) (where φ (α) and ψ (α) are polynomials) X (α) = f (α) × φ (α), polynomial Y (α) = f (α) ^ 2 × ψ (α), and polynomial Z (α) = 1 are used to convert the Jacobian coordinates (X (α ): Y (α): β × Z (α)), and further having doubling and addition on the Jacobiian coordinates, and obtained for the generated one or more Jacobiian coordinates It is characterized by comprising a calculation means for calculating one Jacobian coordinate on the elliptic curve E by performing the doubling or the addition indicated by the calculation information.
[0028]
Here, the acquisition means acquires affine coordinates of one point on the elliptic curve E and calculation information indicating doubling, or affine coordinates of two different points on the elliptic curve E; Calculation information indicating addition, and the conversion means performs the coordinate conversion on the acquired one or two affine coordinates to generate one or two Jacobian coordinates, respectively, The calculation means may be configured to respectively perform doubling or addition indicated by the acquired calculation information on the generated one or two Jacobiian coordinates.
[0029]
Here, the calculation performed by the elliptic curve calculation device on the points on the elliptic curve E is addition, and the acquisition means is affine coordinates (X1 (α), β of two different points on the elliptic curve E). × Y1 (α)) and (X2 (α), β × Y2 (α)) and calculation information indicating addition, and the conversion means obtains the two affine coordinates (X1 (α), β × Y1). (Α)) and (X2 (α), β × Y2 (α)) are subjected to the coordinate transformation to obtain two Jacobian coordinates (X1 (α): Y1 (α): β × Z1 (α )) And (X2 (α): Y2 (α): β × Z2 (α)), and the calculation means calculates the calculation U1 (α) = X1 (α) × Z2 (α) ^ 2, the calculation U2 (Α) = X2 (α) × Z1 (α) ^ 2, operation S1 (α) = Y1 (α) × Z2 (α) ^ 3, operation S2 (α) = Y2 (α) × Z1 (α) ^ 3. Operation H (α) U2 (α) −U1 (α) and operation r (α) = S2 (α) −S1 (α) are performed, and then operation X3 (α) = − H (α) ^ 3−2 × U1 (α ) × H (α) ^ 2 + r (α) ^ 2, operation Y3 (α) = − S1 (α) × H (α) ^ 3 + r (α) × (U1 (α) × H (α) ^ 2-X3 (Α)) and the operation Z3 (α) = Z1 (α) × Z2 (α) × H (α), and then the Jacobiian coordinates (X3 (α): Y3 (α): β × Z3 (α)) ) May be calculated.
[0030]
Here, the calculation performed on the point on the elliptic curve E by the elliptic curve calculation device is doubling, and the acquisition means is affine coordinates of one point on the elliptic curve E (X1 (α), β × Y1 (α)) and calculation information indicating doubling are obtained, and the conversion means converts the coordinate conversion for the one affine coordinate (X1 (α), β × Y1 (α)). To generate one Jacobiian coordinate (X1 (α): Y1 (α): β × Z1 (α)), and the computing means computes S (α) = 4 × X1 (α) × Y1. (Α) ^ 2, operation M (α) = 3 × X1 (α) ^ 2 + a × Z1 (α) ^ 4 × f (α) ^ 2 and operation T (α) = − 2 × S (α) + M ( [alpha]) ^ 2, and then operation X3 ([alpha]) = T ([alpha]), operation Y3 ([alpha]) =-8 * Y1 ([alpha]) ^ 4 + M ([alpha]) * (S ([alpha])-T ([alpha]) ) And operation Z3 (α) = 2 × Y1 (α) × Z (Alpha) performed, then, Jacobian coordinates (X3 (α): Y3 (α): β × Z3 (α)) may be configured to calculate a.
[0031]
According to another aspect of the present invention, there is provided an elliptic curve order calculation device for calculating the order of an elliptic curve by an SEA algorithm, wherein the elliptic curve order calculation device includes the above-described elliptic curve calculation device.
Further, the present invention is an elliptic curve construction device for determining a parameter of an elliptic curve E having a high security and p defined as a finite field GF (p), and generating random numbers. Means, parameter generating means for selecting a parameter of the elliptic curve E including the random number, so that the probability that the discriminant of the elliptic curve E has a square factor is smaller than a predetermined threshold, and the selected parameter A finiteness determining means for determining whether or not the specified elliptic curve E has a point having a finite order on a rational number field, and when the elliptic curve E is determined not to have a point having a finite order In addition, the order calculating means for calculating the order m of the elliptic curve E, and when the order m is calculated, the order m is a prime number, and the order m is not a prime number p. Whether the condition is satisfied Until the order m is a prime number and the order m is not a prime number p, the random number generation means, the parameter generation means, the safety determination means, and the safety determination means Repetitive control means for controlling the finiteness determining means, the order calculating means and the safety determining means to perform random number generation, parameter generation, finiteness determination, order calculation and safety determination, respectively; And a parameter output means for outputting the selected parameter when it is determined that the order m is a prime number and the order m is not a prime number p.
[0032]
Here, the elliptic curve E is represented by y ^ 2 = x ^ 3 + ax + b, where parameter a and parameter b are constants, the parameter generation means sets parameter a = -3, and parameter b is By selecting as the generated random number, the parameter may be selected so that the probability that the discriminant of the elliptic curve E has a square factor is smaller than a predetermined threshold value.
[0033]
Here, the finiteness determining means regards the elliptic curve E as an elliptic curve EQ on a rational number field, has two prime numbers p1 and p2 in advance, and p1 ≠ p2, and the two prime numbers p1 and p2 are When the reduced elliptic curves Ep1 and Ep2 are calculated as the moduli, the orders m1 and m2 are respectively calculated, the calculated orders m1 and m2 are determined to be prime, and the elliptic curves are determined to be prime. You may comprise so that it may determine that E does not have a point of a finite order on a rational number field.
[0034]
Here, the finiteness determining means has primes p1 = 5 and primes p2 = 7 in advance, and the order m1 of elliptic curves Ep1, Ep2 reduced by modulo two primes p1 = 5 and p2 = 7, You may comprise so that m2 may be calculated, respectively.
The present invention also relates to an elliptic curve application device that performs processing using an elliptic curve, wherein p is a prime number and is defined on a finite field GF (p), and has high safety. And an elliptic curve forming unit for determining parameters of the elliptic curve E having the elliptic curve forming unit.
[0035]
DETAILED DESCRIPTION OF THE INVENTION
An elliptic curve constituting device 500 as one embodiment according to the present invention will be described.
1 Configuration of Elliptic Curve Constructing Device 500
When the prime curve p is given, the elliptic curve construction device 500 outputs parameters that define an elliptic curve that is defined on the finite field GF (p) and has a prime order (order ≠ p). Here, the safety of the configured elliptic curve is high.
[0036]
As shown in FIG. 4, the elliptic curve construction device 500 includes a random number generation unit 501, an elliptic curve setting unit 502, an elliptic curve finiteness determination unit 503, an elliptic curve order calculation unit 504, an elliptic curve condition determination unit 505, and a control unit. 506, an information storage unit 507, an input unit 508, an output unit 509, and a parameter storage unit 510. Specifically, as shown in FIG. 5, the elliptic curve forming device 500 includes a microprocessor 11, a ROM (Read Only Memory) 12, a RAM (Random Access Memory) 13, a hard disk 14, a keyboard 15, a display 16, and the like. The hard disk 14 stores a computer program. The random number generation unit 501, elliptic curve setting unit 502, elliptic curve finiteness determination unit 503, elliptic curve order calculation unit 504, elliptic curve condition determination unit 505, control unit 506, input unit 508, and output unit 509 are stored in the hard disk 14. The function is achieved by executing the stored computer program by the microprocessor 11.
1.1 Input unit 508
Specifically, the input unit 508 is configured by the keyboard 15 or the like, receives a configuration instruction to configure an elliptic curve from the user, and simultaneously receives an input of a prime number p (p ≠ 2). Here, the prime number p has a bit number of 160 bits.
[0037]
When receiving the configuration instruction, the input unit 508 outputs the configuration instruction and the prime number p to the control unit 506.
1.2 Information storage unit 507
As shown in FIG. 6, the information storage unit 507 has areas for storing a prime number p, a random number t, a parameter a, a parameter b, and an order m, and each area has a bit number of 160 bits. is doing. Specifically, the information storage unit 507 includes a RAM 13.
[0038]
Here, the parameters a and b are coefficients in the equation y ^ 2 = x ^ 3 + ax + b indicating the elliptic curve E defined on the finite field GF (p).
1.3 Random number generator 501
The random number generation unit 501 receives a random number generation instruction from the control unit 506.
Upon receiving the random number generation instruction, the random number generation unit 501 generates a random number t having a bit number of 160 bits and writes the generated random number t into the information storage unit 507.
1.4 Elliptic curve setting unit 502
(1) Function and configuration of elliptic curve setting unit 502
The elliptic curve setting unit 502 reads the random number t from the information storage unit 507. Further, regarding the parameters a and b in the elliptic curve E: y ^ 2 = x ^ 3 + ax + b
Set parameter a = -3,
Set parameter b = random number t.
[0039]
Therefore, the elliptic curve E is expressed as y ^ 2 = x ^ 3-3x + t.
The elliptic curve setting unit 502 writes the set parameters a and b to the information storage unit 507.
(2) Reason why the elliptic curve is set to y ^ 2 = x ^ 3-3x + t
Since the elliptic curve E: y ^ 2 = x ^ 3-3x + t has a high probability of having a prime order, as described below, the elliptic curve E set by the elliptic curve setting unit 502 is a safe elliptic curve. The probability of being is high.
[0040]
Next, the reason why the elliptic curve E: y ^ 2 = x ^ 3-3x + t has a high probability of having a prime order will be described below.
Curves over rational numbers
E: y ^ 2 = x ^ 3 + ax + b (a and b are integers)
In contrast, the discriminant TD is defined as follows.
TD = 4 * a ^ 3 + 27 * b ^ 2
In this case, E is an elliptic curve and this discriminant TD is not equal to 0. This is shown on page 50 of "The Arithmetic of Elliptic Curves" (JHSilverman, GTM106, Springer-verlag, 1986, hereinafter referred to as Document 1).
[0041]
In the following, it is assumed that the discriminant TD is not 0, that is, E is an elliptic curve.
The following theorem is shown on page 221 of Document 1.
[Theorem 1] When a point having a finite order exists on the elliptic curve E, its coordinates (x, y) are integers, and the discriminant TD is divisible by y ^ 2.
[0042]
From this theorem 1, at the point P = (x, y) on the elliptic curve E, when the discriminant TD is not divisible by y ^ 2, it can be said that the point P does not have a finite order. Therefore, if the discriminant TD does not have a square factor and a point (x, y) having a finite order exists on the elliptic curve E, y = 1 must be satisfied. Therefore, when there is no solution in mod p of 1 = x ^ 3 + ax + b, there is no point having a finite order on the elliptic curve E. Thus, the following facts are derived from Theorem 1.
[Fact 1] When the probability that the discriminant TD has a square factor is low, the probability that a point having a finite order exists on the elliptic curve E is low.
[0043]
Assume that the parameters a and b of the elliptic curve E are elements of GF (p), the coordinates of a point on the elliptic curve E are elements of GF (p), and the obtained elliptic curve is Ep. These operations are called reduction by the method p. The point P = (x, y) of the finite order r on the elliptic curve E is reduced to the point Pp = (x mod p, y mod p) on the Ep by modulus p. The point Pp does not move to the zero element O of the elliptic curve Ep, and the point Pp has an order of r or less.
[0044]
From group theory, the following Proposition 1 holds.
[Proposition 1] When the order of the point Pp on the elliptic curve Ep is r, the order of the elliptic curve Ep is divisible by r.
Let the order of the elliptic curve Ep be m. A point of finite order exists on the elliptic curve E on the rational number field, and its order is assumed to be r. When the order r is smaller than m, m is divisible by r. Therefore, the order of Ep is not a prime number. Considering this in reverse, the following facts can be derived.
[Fact 2] An elliptic curve Ep obtained by reducing an elliptic curve E on a rational number field having no finite order point by p has a high probability of having a prime order.
[0045]
Combining fact 1 and fact 2 leads to the following facts.
[Fact 3] When the discriminant TD of the elliptic curve E has a low probability of having a square factor, the elliptic curve Ep obtained by reducing E by p has a high probability of having a prime number.
In the following, the elliptic curve
E1: y ^ 2 = x ^ 3 + 3ux + 2u,
E2: y ^ 2 = x ^ 3-3x + t (t> 0)
For each discriminant TD. The discriminants TD for E1 and E2 are TD (E1) and TD (E2), respectively. At this time,
TD (E1) = 2 ^ 2 * 3 ^ 3 * u ^ 2 * (u + 1)
TD (E2) = 3 ^ 3 × (t ^ 2-4)
It is.
[0046]
The square factor of TD (E1) is at least 2, 3, 6, u, 2 × 3 × u.
Regarding the square factor of TD (E2), it can be seen from the following proof that t ^ 2-4 is not a square number.
(Proof)
Let t be an integer where t ≠ 0.
[0047]
Since t ≠ 0, t> 1. This is because t ^ 2-4 = -3 when t = 1.
In this case, it is assumed that t ^ 2-4 is a square number. That is, for a certain positive integer n> 0, t ^ 2-4 = n ^ 2.
At this time, (t−n) (t + n) = 4. The divisor of 4 is 1, 2 and 4. From t−n <t + n, the combinations of t−n and t + n are (t−n, t + n) = (1, 4), (2, 2), (4 1). In any combination, t and n are not integers. (End of proof)
As described above, since t ^ 2-4 is not a square number, TD (E2) has a low probability of having a square factor. Therefore, TD (E2) has a lower probability of having a square factor than TD (E1). If elliptic curves E1p and E2p obtained by reducing elliptic curves E1 and E2 with p are respectively elliptic curves E1p and E2p, it can be seen from fact 3 that elliptic curve E2p has a higher probability of having a prime order than elliptic curve E1p. .
[0048]
From the above, it can be seen that the elliptic curve E2p has a high probability of having a prime order.
Thus, the elliptic curve setting unit 502 may set the parameters a and b so that the probability that the elliptic curve discriminant TD has a square factor is smaller than a predetermined threshold.
Thus, since the elliptic curve setting unit 502 selects an elliptic curve with high safety in advance, the elliptic curve construction device 500 does not repeat the step of selecting an elliptic curve and determining its safety many times. The calculation amount in the elliptic curve construction device 500 is reduced.
1.5 Elliptic curve finiteness determination unit 503
(1) Function and configuration of elliptic curve finiteness determination unit 503
The elliptic curve finiteness determination unit 503 reads the parameters a and b of the elliptic curve E from the information storage unit 507.
[0049]
The elliptic curve finiteness determination unit 503 regards the parameters a and b of the elliptic curve E on the read finite field GF (p) as integers, and regards the elliptic curve E as an elliptic curve on rational numbers.
The elliptic curve finiteness determination unit 503 selects prime numbers p1 and p2 smaller than the prime number p. Here, p1 ≠ p2. As an example, prime number p1 = 5 and prime number p2 = 7. Next, the elliptic curves obtained by reducing the elliptic curve on the rational number field using the primes p1 and p2 as modulus are represented by Ep1 and Ep2, respectively, and the respective orders m1 and m2 of the elliptic curves Ep1 and Ep2 are expressed as follows: calculate. Here, the equation of the elliptic curve is assumed to be y ^ 2 = x ^ 3 + ax + b.
[0050]
[Expression 1]

[0051]
Here, (c / p) is a square remainder symbol,
When c is a quadratic residue modulo p, (c / p) = + 1,
When c is a non-square residue modulo p, (c / p) = − 1,
When c = 0, (c / p) = 0.
Next, the order calculation formula will be briefly described.
[0052]
For one value n (0 to p1-1), when n ^ 3 + a * n + b is a non-zero square number, there are two points on the elliptic curve. When n ^ 3 + a * n + b is 0, there is one point on the elliptic curve. If n ^ 3 + a * n + b is not a square number, there is no point on the elliptic curve. On the elliptic curve: y ^ 2 = x ^ 3 + ax + b, the number of points having the value n (0 to p1-1) as the x coordinate is
[0053]
[Expression 2]

[0054]
Can be expressed as
Therefore, for the p1 values from 0 to p1-1, the total number of points on the elliptic curve is
[0055]
[Equation 3]

[0056]
Can be expressed as Thereby, the order calculation formula is obtained. Here, the first 1 of this calculation formula represents the number of zeros O.
In addition, about the calculation method of this order, it is called "Counting points on electric curve over finite fields" (R. Schoff, Jornal de Theorie des Nombres de Bordeaux, 2 19 years, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th, 19th) Shown on the page.
[0057]
Next, the elliptic curve finiteness determination unit 503 determines whether the orders m1 and m2 are relatively prime using the calculated order m1 and order m2, and the orders m1 and m2 are relatively prime. Whether or not the order is determined is output to the control unit 506.
Since the prime numbers p1 and p2 are small values, when calculating the order using the above-mentioned order calculation formula, the amount of calculation is within a practical range.
(2) Reason for determining that the orders m1 and m2 are relatively prime
The following theorems hold for elliptic curves E over rational numbers. This theorem is shown on page 176 of document 1.
[Theorem 3] Elliptic curves obtained by reducing the elliptic curve E on the rational number field by prime numbers p1 and p2 (p1 ≠ p2) are denoted by Ep1 and Ep2, respectively. The orders of the elliptic curves Ep1 and Ep2 are m1 and m2, respectively. When the order m1 and the order m2 are relatively prime, the elliptic curve E has no finite order point.
[0058]
When the orders of the elliptic curves Ep1 and Ep2 are relatively prime, since E does not have a point of finite order, Ep has a high probability of becoming an elliptic curve having a prime order. On the other hand, when the orders of the elliptic curves Ep1 and Ep2 are not prime, since E has a point of finite order, the probability of Ep becoming an elliptic curve having no prime order is high due to the fact 2 above. This elliptic curve is less secure. For this reason, when the orders of the elliptic curves Ep1 and Ep2 are not prime, adoption of this elliptic curve is rejected.
[0059]
In this way, it is possible to reject the less secure elliptic curve before performing the order calculation, and to avoid performing the order calculation of the less secure elliptic curve, reducing the calculation amount of the order calculation. Is possible.
The prime numbers p1 and p2 may be any prime numbers that are smaller than the prime number p. However, as shown above, the prime numbers p1 = 5 and the prime numbers p2 = 7 may be used. Since this combination is the combination of the smallest prime numbers, at this time, the calculation amount of the order is the smallest.
[0060]
When the prime number p1 (or prime number p2) is 3, if the elliptic curve discriminant TD takes mod 3, it becomes 0, so Ep1 (or Ep2) is not an elliptic curve. Therefore, the prime number p1 (or prime number p2) should not be 3.
1.6 Elliptic curve order calculator 504
The elliptic curve order calculator 504 calculates the order of the elliptic curve E on the finite field GF (p) as follows.
1.6.1 Calculation of order by SEA algorithm
The elliptic curve order calculation unit 504 calculates the order of the elliptic curve by the SEA algorithm.
[0061]
The order of the elliptic curve E is m, and t is
m = p + 1−t
Shall be satisfied. Also,
f (x) = x ^ 3 + ax + b
And
[0062]
The elliptic curve order calculator 504 sets an integer variable L = 2 as an initial value.
The elliptic curve order calculation unit 504 calculates the number of primary factors of factorization in the polynomial ring GF (p) [T] of the variable T of the modular polynomial ΦL (T, j (E)).
Next, the elliptic curve order calculator 504 calculates t mod L when the calculated number of primary factors is 2, and calculates t mod L ^ n by the Isogeny cycle method.
[0063]
When the calculated number of primary factors is 1 or L + 1, t mod L is obtained, and it is determined whether the Isogeny cycle method is applicable. If applicable, t mod L ^ n (n = 2, n) by the Isogeny cycle method. 3, ...).
When the calculated number of primary factors is 0, possible values of t mod L are narrowed down from the set [0, 1,..., L−1].
[0064]
Next, the elliptic curve order calculation unit 504
L1 ^ (n1) * L2 ^ (n2) * ... * Lk ^ (nk)
<4 × p ^ (1/2)
(Where L1, L2,..., Lk are prime numbers, Lk = L)
When L = (L is the next largest prime number after L), the calculation of the number of primary factors and the processing for each number of primary factors are repeated until the conditional expression is not satisfied.
[0065]
Next, when the conditional expression is not satisfied, the elliptic curve order calculation unit 504 determines the order m by the match & sort algorithm, and writes the order m to the information storage unit 507.
As for this order calculation method, “Counting the number of points on elliptic curves over finite fields: strategies performances” (R.Lercier, F.Morain, EUROCRYPT'95, Springer-Verlag, 1995, p. 79- 94 page).
[0066]
As for the match & sort algorithm, “Algorithmique des courbes elliptiques dans les corps finis” (Thesis, Ecole Polytechnique-LIX, (1997), in French, pp. 195-202) or “Elliptic Curves in Cryptography”, London Mathematical Society Lecture Note Series 265, CAMBRIDGE UNIVERSITY PRESS, (1999), pages 142-144).
1.6.2 Supplementary explanation on how to calculate the order using the SEA algorithm
The order calculation method using the SEA algorithm will be supplementarily described. The elliptic curve order calculation unit 504 calculates the order described below.
[0067]
The elliptic curve on GF (p) is the target elliptic curve for order calculation.
E: y ^ 2 = f (x)
And Here, f (x) = x ^ 3 + ax + b.
(1) Eigen equation
(1-1) Algebraic closure K of GF (p)
Let K be the algebraic closure of GF (p). The algebraic closure K is a field containing GF (p), and a polynomial having a coefficient of K can always be decomposed into a linear expression.
[0068]
Another example of algebraic closure is a complex number field that is an algebraic closure of a real number field. Polynomials with complex coefficients can always be decomposed into linear equations.
(1-2) Frobenius map φp
For the point P = (α, β) (α, βεK) on the elliptic curve, the Frobenius map φp is defined as follows.
[0069]
φp: (α, β) → (α ^ p, β ^ p)
Since (α, β) is a point on E,
β ^ 2 = α ^ 3 + aα + b
Holds. If both sides are raised to the power p,
β ^ (2p) = (α ^ 3 + aα + b) ^ p
The right-hand side of this equation is based on the description on page 193 of “Overview of Algebra” (written by Yasuo Morita, Mathematics Selection 9, Kankabo, 1987).

It becomes. Since a and b are elements of GF (p), a = a ^ p and b = b ^ p.
[0070]
Therefore,
(Β ^ p) ^ 2 = (α ^ p) ^ 3 + a (α ^ p) + b
(Α ^ p, β ^ p) is also a point on the elliptic curve.
(1-3) eigenpolynomial (characteristic polynomial)
According to the description on page 485 of "Elliptic curves over finite fields and the computation of square roots mod p" (R. Schoff, Math. Comp. Vol 44, 1985),
For the point P = (α, β) (α, βεK) on the elliptic curve, the following equation holds.
[0071]
(Φp) ^ 2 (P) −tφp (P) + pP = O
Here, O is the zero element of the elliptic curve group. Further, t is called a trace, and + and − in the above expression are symbols indicating addition and subtraction on an elliptic curve.
From Hasse's theorem, the order from t can be obtained from the following equation.
Order = p + 1−t
Therefore, the order can be calculated by obtaining the trace t.
[0072]
When the point P is an L-equivalent point on E (L: prime number), that is, a point satisfying LP = O, the following equation holds.
(Φp) ^ 2 (P) − (t mod L) φp (P)
+ (P mod L) P = O
In the SEA algorithm, t mod L is calculated from this equation.
[0073]
Here, the fact that φp has an eigenvalue k means that for an L equipartition point P on a certain E,
φp (P) = kP
Is true. Here, kP is a multiplication point on the elliptic curve.
At this time, the intrinsic polynomial of φp is
k ^ 2 P − (t mod L) kP
+ (P mod L) P = O
It becomes. Thus, when there is an eigenvalue k, the eigenpolynomial of φp is
k ^ 2− (t mod L) k + (p mod L) = 0
It can be considered as a quadratic equation of a variable k of the form The SEA algorithm is divided into the following cases depending on the presence or absence of the root of GF (L) in this equation.
[0074]
When the quadratic equation has different roots k1 and k2 (Case 1)
When the quadratic equation has multiple roots (Case 2)
When the quadratic equation has no root (Case 3)
In the following, processing in three cases will be described.
(Case 1) When the quadratic equation has different roots k1 and k2.
When the quadratic equation has different roots k1 and k2,
k ^ 2− (t mod L) k + (p mod L)
= (K-k1) (k-k2)
You can leave
k1 + k2 = t mod L, k1 * k2 = p mod L
It becomes. Therefore, if k1 is obtained,
t = k1 + p / k1 = (k1 ^ 2 + p) / k1 mod L
Thus, t can be obtained.
(Case 2) When the quadratic equation has multiple roots
If the quadratic equation has multiple roots,
k1 ^ 2 = p mod L
So k is
± √ (p) mod L
One of the following values. this is,
φp P = ± (√ (p) mod L) P
It depends on which of the following holds.
[0075]
Depending on the eigenvalue of φp, t
± 2 √ (p) mod L
One of these values.
(Case 3) When the quadratic equation has no root
If the quadratic equation has no root,
((Φp) ^ 2 + (p mod L)) P and
(T ′ mod L) Coordinate comparison with φpP is performed, and t ′ when matching is set as correct t mod L.
(1-4) Case determination
Since Case 1, Case 2, and Case 3 do not know t mod L, it is not known which case corresponds to them.
[0076]
However, it can be determined by the number of roots of GF (p) of a polynomial called a modular polynomial.
When the number of roots of GF (p) of the modular polynomial ΦL (T, j (E)) is two, it corresponds to Case1. When the number of roots is 1 or L + 1, it corresponds to Case2. When the number of roots is 0, it corresponds to Case3.
[0077]
Details are described on page 239 of “Counting points on elliptic curve over finite fields” (R. Schoof, Journal de Theorie des Nombres de Bordeaux 7, 1995), and thus the description thereof is omitted.
(1-5) How to solve eigen equations in Case 3
In the case of Case 3, how to solve the eigen equation will be described.
[0078]
A polynomial having an L-division point, that is, an x coordinate of the entire point P on E satisfying LP = O as a root is called an L-equalization polynomial, and is represented by fL (α). At this time, “P = (α, β) is an L equality point” and “fL (α) = 0” are the same value.
fL (α) is obtained using a recurrence formula. The details are described on page 485 of “Elliptic curves over finite fields and the computation of square roots mod p” (R. Schof, Math. Comp., Vol 44, 1985), so the explanation is omitted. To do.
(1-6) Polynomial expression of eigen equation
From the eigen equation
(Formula 1)
(Φp) ^ 2 (P) + (p mod L) P = (t mod L) φpP
It turns out that it is. If the coordinates of the point P are (α, β), the point P (α, β) is a point on the elliptic curve.
β ^ 2-α ^ 3-aα-b = 0
And is the L equivalence point,
fL (α) = 0 is satisfied.
[0079]
Here, the coordinates of the point P in Equation 1 are represented by a polynomial remainder ring with α and β as variables.
R = GF (p) [α, β] / (β ^ 2-α ^ 3-aα-b, fL (α))
Represented by
The operation on the polynomial remainder ring R is performed by rewriting “β ^ 2” with “α ^ 3 + aα + b” and setting “fL (α)” to “0”.
[0080]
In the following, when in R is specified, it is assumed that the operation is performed with this polynomial remainder ring R.
At this time, from Equation 1,
(Formula 2)
(Α ^ (p ^ 2), β ^ (p ^ 2)) + (p mod L) (α, β)
= (T mod L) (α ^ p, β ^ p) in R
Holds.
(1-7) How to solve the eigen equation in Case 1
A method for solving the eigen equation in Case 1 will be described.
[0081]
In Case 1, k that satisfies φp P = k P is obtained.
At this time, the factor h (α) of the L-equalization polynomial fL (α) is used. That is, h (α) divides fL (α). The method for obtaining h (α) is described on pages 242-253 of “Counting points on elliptic curve over finite fields” (R. Schoff, Journal de Theorie des Nombres de Bordeaux 7, 1995). Description is omitted.
(1-8) How to solve eigen equations in Case 2
A method for solving the eigen equation in Case 2 will be described.
[0082]
In Case 2, since k is known up to ± √p, the y coordinate is compared to determine the sign.
Since the calculation amount of Case 3 is larger than the calculation amounts of Case 1 and Case 2, t mod L is not obtained in Case 3. Calculation to narrow down to candidates for possible values of t mod L is performed. In this way, the calculation amount of Case 3 is almost the same as the calculation amount of Case 1 or Case 2.
[0083]
However, when L is small (L <= 5), since the amount of calculation is small, the correct t mod L is obtained.
The refinement calculation is described in detail on pages 239 to 241 of “Counting points on elliptic curve over finite fields” (R. Schoff, Journal de Theorie des Nombres de Bordeaux 7, 1995).
1.6.3 Calculation of t mod L ^ n
The elliptic curve order calculation unit 504 calculates t mod L ^ n as follows.
(1) Calculation of t mod L
Elliptic curve order calculation unit 504 receives h (α) as input, calculates t mod L as follows, and outputs t mod L.
[0084]
Polynomial remainder ring R
R = GF (p) [α, β] / (β ^ 2-α ^ 3-aα-b, h (α))
And To find t mod L,
φp ((α, β)) = k (α, β) in R
It is necessary to find k that satisfies
[0085]
The elliptic curve order calculation unit 504 sequentially changes k ′ from a value of 0 to a value of (L−1) / 2,
φp ((α, β)) in R x coordinate,
k ′ (α, β) in R and the x coordinate table,
For each k '
The calculated x coordinate of φp ((α, β)) in R,
Compare the calculated x 'coordinate of k' (α, β) in R
If it matches for the first time,
φp ((α, β)) in R y coordinate,
k ′ (α, β) in R and the y coordinate are calculated,
φp ((α, β)) in R y coordinate,
When the y coordinate of k ′ (α, β) in R matches, k = k ′ mod L is set, and when they do not match, k = L−k ′ mod L is set.
[0086]
Further, t = (k ^ 2 + p) / k mod L and t is output.
(2) Calculation of t mod L ^ n by the Isogeny cycle method
The elliptic curve order calculation unit 504 obtains t mod L ^ n by the Isogeny cycle method.
In Case 1, first, the elliptic curve order calculation unit 504 sets n = 2, obtains a polynomial H (α) based on k mod L and h (α), and sets it to h (α) again. K mod L ^ n is determined using the polynomial h (α). Next, it is determined whether or not to proceed to the next based on the degree of the polynomial h (α). The order of h (α) is deg (h (α)). then,
(Deg (h) ^ 2) * L ^ 2 * (L ^ (2 * n))
> (| P |) ^ 3/135. Here, | p | is the number of bits of p. If the judgment formula is true,
t = (k ^ 2 + p) / k mod L ^ n
To finish the Isogeny cycle. If false, add 1 to n and repeat the process until the inequality is satisfied. Thus, the elliptic curve order calculation unit 504 obtains t mod L ^ n.
[0087]
In the case of Case 2 as well, the elliptic curve order calculation unit 504 performs the same operation as in Case 1, but does not necessarily perform Isogeny cycle. Therefore, the elliptic curve order calculation unit 504 determines whether or not the Isogeny cycle can be performed.
Next, calculation of k mod L ^ n (when n> 1) will be described.
[0088]
Here, k_i = k mod L ^ i (1 ≦ t ≦ n).
The elliptic curve order calculation unit 504 receives k mod L ^ (n−1) and h (α) as inputs, and calculates k mod L ^ n as follows.
Polynomial remainder ring R
R = GF (p) [α, β] / (β ^ 2-α ^ 3-aα-b, h (α))
And To find k mod L ^ n,
φp ((α, β))
= (K_ (n-1) + L ^ (n-1) * κ) (α, β) in R
It is necessary to find κ that satisfies
[0089]
The elliptic curve order calculation unit 504 sequentially changes κ ′ from a value of 0 to a value of (L−1) / 2,
φp ((α, β)) in R x coordinate,
(K_ (n−1) + L ^ (n−1) * κ ′) (α, β) Calculate the x coordinate of in R,
For each κ '
The calculated x coordinate of φp ((α, β)) in R,
The calculated (k_ (n−1) + L ^ (n−1) * κ ′) (α, β) in R is compared with the x coordinate,
If it matches for the first time,
k_n = k_ (n-1) + L ^ (n-1) * κ 'mod L ^ n
And k_n is k mod L ^ n.
[0090]
These processes are described in detail in “Isogeny cycles and the Schoof-Elkies-Atkin algorithm” (JMCouveignes, L. Dewaghe and F. Morain, LIX / RR / 96/03, 1996).
1.6.4 Termination Determination by Elliptic Curve Order Calculation Unit 504
As already described, the elliptic curve order calculation unit 504 determines that the iterative calculation by the SEA algorithm is completed when ΠLk ^ (nk) exceeds 4√p, determines the order, and calculates the elliptic curve order. The calculation by the unit 504 is terminated.
[0091]
However, the elliptic curve order calculation unit 504 eliminates the elliptic curve that is determined not to be a safe elliptic curve by the elliptic curve condition determination unit 505 in advance, and reduces the calculation time. The elliptic curve is determined inside 504.
Specifically, the elliptic curve order calculator 504 calculates p + 1−t mod L when t mod L is determined, determines whether p + 1−t mod L = 0, and p + 1− When t mod L = 0, the order of the elliptic curve cannot be a prime number. Therefore, in order to reject the adoption of the elliptic curve, the elliptic curve rejection information is output to the control unit 506, and the elliptic curve order is determined. The calculation by the calculation unit 504 ends.
[0092]
In this way, when the elliptic curve order calculation unit 504 determines t mod L, the elliptic curve with low safety is rejected, so that the elliptic curve order calculation unit 504 does not perform useless processing. can do.
As for this method, “Finding Good Random Elliptic Curves for Cryptosystems Defined over F_ {2 ^ n}” (R. Lercier, Advances in Cryptology-Proceedings of Eurocrypt '97, Lecture Notes in Computer Science, 1233, 1997) , Springer-Verlag).
1.6.5 Calculation of power points
As described above, to obtain the eigenvalue of φp, it is necessary to calculate the multiplication point of the elliptic curve. Below, the calculation method of a multiplication point is demonstrated.
(1) Method using an equipartition polynomial
In calculating t mod L, the elliptic curve order calculator 504 calculates the multiplication point as follows.
[0093]
Using the equipartition polynomial f_n, n (α, β) is as follows.
If n is an even number,

If n is odd,

This is described in pages 485 to 486 of “Elliptic curves over finite fields and the computation of square roots mod p” (R. Schoof, Math. Comp., 44, 1985).
(2) Method using elliptic curve calculation
The elliptic curve order calculation unit 504 calculates a multiplication point as follows in the calculation of the above t mod L ^ n.
[0094]
Here, when the above-described equality polynomial is used, it is necessary to obtain an unnecessary equality polynomial such as f_1 to f_ (L ^ (n-2)), which is not efficient. Therefore, the elliptic curve order calculation unit 504 employs a method of obtaining by elliptic curve calculation.
First, consider applying an elliptic curve calculation over a finite field. In the case of computation on a finite field, division is required if computation using binomial coordinates is employed. However, since division is generally more computationally intensive than multiplication (about 10 times), consider a ternary operation that does not use division. Similarly, in the case of polynomial remainder rings, consider the case of ternary groups.
[0095]
Here, the first and second components of the binomial coordinates are referred to as x-coordinate and y-coordinate, respectively. The first, second, and third components of the three-term set of coordinates are referred to as an X coordinate, a Y coordinate, and a Z coordinate, respectively.
Apply Jacobian coordinates over a finite field. Since it is easier to calculate if the input and output have the same shape, consider the elliptic curve on the polynomial remainder ring R, and the coordinates of the point above it,
(X (α): β * Y (α): Z (α))
Suppose that the input and output are in this form.
[0096]
In addition, the following transformations are used to change the form of input and output. Again, it is Jacobian coordinates.
(X '(α): β * Y' (α): Z '(α)) → (β ^ 2 * X' (α): β ^ 4 * Y '(α): β * Z' (α) )
Where β ^ 2 = f (α)
X (α) = f (α) * X '(α)
Y (α) = f (α) ^ 2 * Y '(α)
Z (α) = Z '(α)
Then the destination point is
(X (α): Y (α): β * Z (α))
It has the shape of
(2-1) Projection of points on elliptic curve
The elliptic curve order calculation unit 504 calculates the affine coordinates of the points on the elliptic curve E.
(Φ (α), β × ψ (α))
Polynomial X (α) = f (α) × φ (α),
Polynomial Y (α) = f (α) ^ 2 × ψ (α) and
Polynomial Z (α) = 1
Projective coordinates transformed by
(X (α): Y (α): β × Z (α)) is generated.
[0097]
Here, φ (α) and ψ (α) are polynomials. “(::)” Indicates projective coordinates.
(2-2) Elliptic curve calculation (addition and doubling)
Next, calculation of points on the elliptic curve defined on the polynomial remainder ring will be described.
The computation of points on the elliptic curve can be broken down into doubling and addition. For example, for a point P on an elliptic curve, the calculation of 100 × P is
100 × P = 2 (2 (P + 2 (2 (2 (P + 2P))))), it can be performed by 6 doublings and 2 additions by points on the elliptic curve.
[0098]
Note that the doubling and the decomposition into addition are performed using the Signed Binary method.
For the Signed Binary method, see “Speeding up Elliptic Curve Cryptosystems by Using a Signed Binary Window Method” (K. Koyama, Y. Tsuruoka, Advances in Cryptology-CRYPTO'92, Lecture Notes in Computer Science, Vol. 740, Springer- Verlag, (1993), pages 345-357).
[0099]
In this elliptic curve calculation, the elliptic curve order calculation unit 504 uses α and β as variables, and a polynomial having elements on the finite field GF (p) as coefficients.
β ^ 2-f (α)
And a polynomial h (α) (where h (α) is a polynomial for α) an elliptic curve on a polynomial remainder ring
E: y ^ 2 = f (x)
On the other hand, the calculation is performed with the coordinates of the point on the elliptic curve E as input, and the coordinates of the point on the elliptic curve E are calculated as the calculation result.
(2-2-1) Addition
Here, the addition will be described.
[0100]
The elliptic curve order calculation unit 504 is configured to calculate points P and Q on the elliptic curve E (P ≠ ± Q).
P = (X1 (α): Y1 (α): β × Z1 (α)),
Q = (X2 (α): Y2 (α): β × Z2 (α))
As input,

And then

Calculate
[0101]
Next, the elliptic curve order calculation unit 504
β × Z3
Calculate
P + Q = (X3 (α): Y3 (α): β × Z3 (α))
Is the addition result of the points P and Q on the elliptic curve E.
[0102]
In each of the arithmetic expressions shown above, X1, Y1, Z1, X2, Y2, Z2, X3, Y3, Z3, U1, U2, S1, S2, H, and r are polynomials related to the variable α. X1 (α), Y1 (α), Z1 (α), and the like should be written, but for the sake of simplicity, (α) is omitted and attention is required.
(2-2-2) doubling
Here, doubling will be described.
[0103]
The elliptic curve order calculation unit 504 is a point on the elliptic curve E.
P = (X1 (α): Y1 (α): β × Z1 (α))
As input,

And then

Calculate
[0104]
Next, the elliptic curve order calculation unit 504
β × Z3
Calculate
2P = (X3 (α): Y3 (α): β × Z3 (α))
Is the result of doubling the point P on the elliptic curve E.
[0105]
Note that, in each of the arithmetic expressions shown above, X1, Y1, Z1, X3, Y3, Z3, S, M, and T are polynomials related to the variable α, so X1 (α), Y1 (α), Z1 (α) should be written, but for the sake of simplicity, (α) is omitted and attention is required.
The numbers of multiplications in the addition formula and the doubling formula are 16 times and 10 times, respectively, as can be seen from counting the number of occurrences of the operator *. When the calculation amount of the polynomial multiplication is PMul, the calculation amounts by the addition formula and the doubling formula are 16 × PMul and 10 × PMul, respectively.
[0106]
Thus, when compared with the calculation amount of the addition formula shown in Conventional Example 3, the calculation amount of the polynomial multiplication is increased by 1 PMul, and when compared with the calculation amount of the doubling formula shown in Conventional Example 3, the multiplication amount of the polynomial multiplication is increased. The computational complexity is reduced by 2 PMul.
Usually, the number of operations for doubling is greater than the number of operations for addition, so a decrease in the amount of calculation for doubling greatly contributes to a decrease in the total amount of calculation.
(2-3) Derivation of addition formula and doubling formula
Here, the derivation of the addition formula and the doubling formula will be described.
[0107]
The calculation of the Jacobian coordinates on the finite field is as follows.
Here, P = (x1: y1: z1), Q = (x2: y2: z2), and P + Q = R = (x3: y3: z3).
(Addition) (when P ≠ ± Q)
The addition is as follows.
[0108]
x3 = −H ^ 3−2 * U1 * H ^ 2 + r ^ 2,
y3 = −S1 * H ^ 3 + r * (U1 * H ^ 2-x3),
z3 = z1 * z2 * H
Here, U1 = x1 * z2 ^ 2, U2 = x2 * z1 ^ 2, S1 = y1 * z2 ^ 3, S2 = y2 * z1 ^ 3, H = U2-U1, r = S2-S1.
(Doubling) (when P = Q)
The doubling is as follows.
[0109]
x3 = T,
y3 = -8 * y1 ^ 4 + M * (ST),
z3 = 2 * y1 * z1
Here, S = 4 * x1 * y1 ^ 2, M = 3 * x1 ^ 2 + a * z1 ^ 4, T = -2 * S + M ^ 2.
[0110]
Next, this operation is applied to the polynomial remainder ring R.
Here, P = (X1 (α): Y1 (α): β * Z1 (α)), Q = (X2 (α): Y2 (α): β * Z2 (α)), P + Q = R = ( X3 (α): Y3 (α): β * Z3 (α)).
Also, to apply to the above calculation,
x1 = X1 (α), y1 = Y1 (α), z1 = β * Z1 (α)
x2 = X2 (α), y2 = Y2 (α), z2 = β * Z2 (α)
x3 = X3 (α), y3 = Y3 (α), z3 = β * Z3 (α)
far.
(Addition of Jacobian coordinates of elliptic curve on polynomial remainder ring R)
The addition of the Jacobian coordinates of the elliptic curve on the polynomial remainder ring R is as follows.
[0111]
U1 = X1 * β ^ 2 * Z2 ^ 2,
U2 = X2 * β ^ 2 * Z1 ^ 2,
S1 = Y1 * β ^ 3 * Z2 ^ 3
S2 = Y2 * β ^ 3 * Z1 ^ 3
Here, if U1 ′ = U1 / β ^ 2, U2 ′ = U2 / β ^ 2, S1 ′ = S1 / β ^ 3, S2 ′ = S2 / β ^ 3,
H = (U2′−U1 ′) * β ^ 2, r = (S2′−S1 ′) * β ^ 3.
[0112]

It is. Here, if x3 ′ = x3 / β ^ 6,

It is. Here, if y3 ′ = y3 / β ^ 9,
y3 ′ = − S1 ′ * H ′ ^ 3 + r ′ * (U1 ′ * H ′ ^ 2−x3 ′)
z3 = Z1 * β * Z2 * β * H ′ * β ^ 2.
[0113]
Here, it is assumed that z3 ′ = z3 / β ^ 4.
At this time,
X3 = x3 ′ * β ^ 6
Y3 = y3 ′ * β ^ 9
β * Z3 = z3 ′ * β ^ 4
It is.
[0114]
(X3: Y3: β * Z3) = (X3 / β ^ 6: Y3 / β ^ 9: β * Z3 / β ^ 4)
So
(X3: Y3: β * Z3) = (x3 ′: y3 ′: β * z3 ′)
It is.
[0115]
Here, x3 ′, y3 ′, z3 ′, U1 ′, U2 ′, S1 ′, S2 ′, H ′, r ′ are newly changed.
If X3, Y3, Z3, U1, U2, S1, S2, H, r are respectively set, the addition formula of the present invention can be derived.
(Doubling the Jacobian coordinates of the elliptic curve on the polynomial remainder ring R)
The doubling of the Jacobian coordinates of the elliptic curve on the polynomial remainder ring R is as follows.
[0116]
S = 4 * X1 * Y1 ^ 2
M = 3 * X1 ^ 2 + a * Z1 ^ 4 * β ^ 4
It is. Since β ^ 2 = f (α), M = 3 * X1 ^ 2 + a * Z1 ^ 4 * f (α) ^ 2. Also,
x3 = T
y3 = -8 * Y1 ^ 4 + M * (ST)
z3 = 2 * Y1 * Z1 * β
It is.
[0117]
Since X3 = x3, Y3 = y3, Z3 = z3 / β = 2 * Y1 * Z1, the doubling formula of the present invention can be derived.
1.7 Elliptic curve condition determination unit 505
The elliptic curve condition determination unit 505 reads the prime number p and the order m from the information storage unit 507, and determines whether the read order m is a prime number and the order m ≠ the prime number p. Next, safety determination information indicating whether the read order m is a prime number and order m ≠ prime p is output to the control unit 506.
1.8 Control unit 506
The control unit 506 receives a configuration instruction indicating that an elliptic curve is to be configured and a prime number p from the input unit 508.
[0118]
Upon receiving the configuration instruction, the control unit 506 writes the prime number p to the information storage unit 507 and outputs a random number generation instruction to the random number generation unit 501.
The control unit 506 performs processing of each component unit in this order with respect to the random number generation unit 501, the elliptic curve setting unit 502, the elliptic curve finiteness determination unit 503, the elliptic curve order calculation unit 504, and the elliptic curve condition determination unit 505. Control to execute.
[0119]
The control unit 506 receives the order determination information from the elliptic curve finiteness determination unit 503. When the received order determination information indicates that the orders m1 and m2 are relatively prime, next, the elliptic curve order calculation unit 504 is controlled to execute the process. If the received order determination information indicates that the orders m1 and m2 are not prime, then the processing is stopped for the elliptic curve order calculation unit 504 and the random number generation unit 501 Control to execute the process.
[0120]
The control unit 506 receives elliptic curve rejection information from the elliptic curve order calculation unit 504. Upon receiving the elliptic curve rejection information, the control unit 506 controls the elliptic curve condition determination unit 505 to stop the process and the random number generation unit 501 to execute the process.
The control unit 506 receives the safety determination information from the elliptic curve condition determination unit 505. If the received safety determination information indicates that the order m is a prime number and the order m ≠ prime p, the parameters a and b are read from the information storage unit 507, and the read parameters a and b Is output to the output unit 509. When the received safety judgment information does not indicate that the order m is a prime number and the order m ≠ prime p, the random number generation unit 501 is controlled to execute the process again. To do.
1.9 Output unit 509
The output unit 509 receives the parameters a and b from the control unit 506 and writes the received parameters a and b to the parameter storage unit 510.
1.10. Parameter storage unit 510
The parameter storage unit 510 is specifically composed of the hard disk 14 and stores parameters a and b.
2 Operation of elliptic curve construction device 500
Here, the operation of the elliptic curve forming apparatus 500 will be described.
2.1 Overall Operation of Elliptic Curve Constructing Device 500
The overall operation of the elliptic curve construction device 500 will be described with reference to the flowchart shown in FIG.
[0121]
The input unit 508 receives a configuration instruction and a prime p from the user, and the control unit 506 receives the configuration instruction and the prime p (step S100).
The control unit 506 outputs a random number generation instruction to the random number generation unit 501, and the random number generation unit 501 generates a random number t and writes the generated random number t into the information storage unit 507 (step S101).
[0122]
The elliptic curve setting unit 502 reads the random number t, sets parameter a = −3, and sets parameter b = random number t (step S102).
The elliptic curve finiteness determination unit 503 selects the prime numbers p1 and p2, calculates the orders m1 and m2 of the elliptic curves Ep1 and Ep2 obtained by reducing the elliptic curve on the rational number field using the prime numbers p1 and p2 as modulus. It is determined whether the numbers m1 and m2 are relatively prime (step S103), and the control unit 506 returns the control to step S101 when the orders m1 and m2 are not prime (step S104).
[0123]
When the orders m1 and m2 are relatively prime (step S104), the control unit 506 controls the elliptic curve order calculation unit 504 to perform order calculation, and the elliptic curve order calculation unit 504 The order is calculated (step S105).
When receiving the elliptic curve rejection information (step S106), the control unit 506 returns the control to step S101.
[0124]
When the control unit 506 does not receive the elliptic curve rejection information (step S106),
The elliptic curve condition determining unit 505 determines whether the order m is a prime number and the order m ≠ prime p, and “the order m is a prime number and the order m ≠ prime p”. In some cases (step S107), the control unit 506 controls the output unit 509 to output the parameters a and b, and the output unit 509 outputs the parameters a and b (step S108).
[0125]
When “the order m is a prime number and the order m is not a prime number p” (step S107), the control unit 506 returns the control to step S101.
2.2 Operation of elliptic curve order calculator 504
The operation of the elliptic curve order calculator 504 will be described with reference to the flowchart shown in FIG.
[0126]
The order of the elliptic curve E is m, and t is
m = p + 1−t
Shall be satisfied. Also,
f (x) = x ^ 3 + ax + b
And
[0127]
The elliptic curve order calculator 504 sets an integer variable L = 2 as an initial value (step S910).
The elliptic curve order calculation unit 504 calculates the number of primary factors in factorization in the polynomial ring GF (p) [T] of the univariate T of the modular polynomial ΦL (T, j (E)) (step S911).
[0128]
When the calculated number of primary factors is 2 (step S912), the elliptic curve order calculation unit 504 obtains t mod L (step S913) and performs t mod L ^ n (n = 2, 3) using the Isogeny cycle method. ... (Step S914).
When the calculated number of primary factors is 1 or L + 1 (step S912), t mod L is obtained (step S915), it is determined whether or not the Isogeny cycle method is applicable (step S916), and the Isogeny cycle method is applied. To obtain t mod L ^ n (n = 2, 3,...) (Step S917).
[0129]
When the calculated number of primary factors is 0 (step S912), the possible values of t mod L are narrowed down from the set [0, 1, ..., L-1] (step S918).
Next, the elliptic curve order calculation unit 504
L1 ^ (n1) * L2 ^ (n2) * ... * Lk ^ (nk)
<4 × p ^ (1/2)
(Where L1, L2,..., Lk are prime numbers, Lk = L)
(Step S919), L = (L is the next largest prime number) (Step S921), and the process returns to Step S911.
[0130]
Otherwise (step S919), the elliptic curve order calculation unit 504 determines the order m by the match & sort algorithm, and writes the order m to the information storage unit 507 (step S920).
2.3 Operation of calculating t mod L ^ n by elliptic curve order calculator 504
The operation of calculating t mod L ^ n by the elliptic curve order calculator 504 will be described with reference to the flowchart shown in FIG.
[0131]
In Case 1, first, the elliptic curve order calculation unit 504 sets n = 2 (step S131), obtains a polynomial H (α) based on k mod L and h (α) (step S132), h (α) is set (step S133). K mod L ^ n is obtained using the polynomial h (α) (step S134). Next, it is determined whether or not to proceed to the next based on the degree of the polynomial h (α). The order of h (α) is deg (h (α)). then,
(Deg (h) ^ 2) * L ^ 2 * (L ^ (2 * n))
> (| P |) ^ 3/135. Here, | p | is the number of bits of p. If the determination formula is true (step S135),
t = (k ^ 2 + p) / k mod L ^ n
(Step S137), the Isogeny cycle is terminated. If false (step S135), 1 is added to n (step S136), and the process is repeated until the inequality is satisfied.
[0132]
Thus, the elliptic curve order calculation unit 504 obtains t mod L ^ n.
In the case of Case 2 as well, the elliptic curve order calculation unit 504 performs the same operation as in Case 1, but does not necessarily perform Isogeny cycle. Therefore, the elliptic curve order calculation unit 504 determines whether or not the Isogeny cycle can be performed.
2.4 Operation of doubling or adding points on elliptic curve by elliptic curve order calculator 504
When calculating the multiplication point kP of the elliptic curve, the elliptic curve order calculation unit 504 decomposes the calculation of the multiplication point kP into doubling or addition of points on the elliptic curve, and the divided double When calculating or adding, the following procedure is used. At this time, the type of doubling or addition and the affine coordinates of one or two points on the elliptic curve to be doubled or added are output for the following procedure, and the following procedure is performed. To do. For the resolved doubling or addition, the following procedure is repeated to calculate the multiplication point kP of the elliptic curve.
[0133]
The operation of doubling or adding points on the elliptic curve by the elliptic curve order calculator 504 will be described with reference to the flowchart shown in FIG.
The elliptic curve order calculation unit 504 includes a polynomial β ^ 2-f (α) (where f (α) = α ^ 3 + aα + b, where a and b are constants) and a polynomial h (α) (where , H (α) is a polynomial related to α) Elliptic curve E on the two-variable polynomial remainder ring related to α, β modulo and doubling or adding on y ^ 2 = f (x) Do.
[0134]
The elliptic curve order calculation unit 504 acquires the affine coordinates of one point on the elliptic curve E to be subjected to the doubling operation and the operation information indicating the doubling operation, or is the addition operation target. The affine coordinates of two different points on the elliptic curve E and the calculation information indicating the addition are received. Here, the affine coordinates of two different points on the elliptic curve E are
(X1 (α), β × Y1 (α)) and
(X2 (α), β × Y2 (α)),
The affine coordinates of one point on the elliptic curve E are
(X1 (α), β × Y1 (α)) (step S121).
[0135]
Next, the elliptic curve order calculation unit 504 performs coordinate transformation on the received one or two affine coordinates to generate one or two projective coordinates, respectively. In the coordinate transformation, the affine coordinates (φ (α), β × ψ (α)) of the point on the elliptic curve E (where φ (α) and ψ (α) are polynomials),
Polynomial X (α) = f (α) × φ (α),
Polynomial Y (α) = f (α) ^ 2 × ψ (α) and
Convert by polynomial Z (α) = 1
Projective coordinates (X (α): Y (α): β × Z (α)) are generated. Here, the two projected coordinates generated are:
(X1 (α): Y1 (α): β × Z1 (α)) and
(X2 (α): Y2 (α): β × Z2 (α)),
One projective coordinate generated is
(X1 (α): Y1 (α): β × Z1 (α)) (step S122).
[0136]
Next, the elliptic curve order calculation unit 504 determines whether the calculation information is addition or doubling, and if it is addition (step S123),
Operation U1 (α) = X1 (α) × Z2 (α) ^ 2,
Operation U2 (α) = X2 (α) × Z1 (α) ^ 2,
Operation S1 (α) = Y1 (α) × Z2 (α) ^ 3,
Operation S2 (α) = Y2 (α) × Z1 (α) ^ 3,
Operation H (α) = U2 (α) −U1 (α) and
Calculation r (α) = S2 (α) −S1 (α) is performed (step S124),
next,
Operation X3 (α) = − H (α) ^ 3−2 × U1 (α) × H (α) ^ 2 + r (α) ^ 2,
Operation Y3 (α) = − S1 (α) × H (α) ^ 3 + r (α) × (U1 (α) × H (α) ^ 2-X3 (α)) and
Calculation Z3 (α) = Z1 (α) × Z2 (α) × H (α) is performed (step S125).
[0137]
When the elliptic curve order calculation unit 504 performs doubling (step S123),
Operation S (α) = 4 × X1 (α) × Y1 (α) ^ 2,
Operation M (α) = 3 × X1 (α) ^ 2 + a × Z1 (α) ^ 4 × f (α) ^ 2 and
Calculation T (α) = − 2 × S (α) + M (α) ^ 2 is performed (step S126),
Operation X3 (α) = T (α),
Operation Y3 (α) = − 8 × Y1 (α) ^ 4 + M (α) × (S (α) −T (α)) and
Calculation Z3 (α) = 2 × Y1 (α) × Z1 (α) is performed (step S127).
[0138]
Next, the elliptic curve order calculator 504 calculates and outputs projected coordinates (X3 (α): Y3 (α): β × Z3 (α)) (step S128).
3 Summary
Since the elliptic curve setting unit has a high probability of selecting an elliptic curve with high safety in advance, the calculation amount in the elliptic curve construction device is reduced without repeating the step of selecting an elliptic curve and determining its safety many times. Decrease.
[0139]
Further, the elliptic curve finiteness determination unit determines whether the elliptic curve has high safety by determining whether the elliptic curve has a point having a finite order before performing the order calculation. Since the determination is made, an elliptic curve with low safety can be rejected without performing the order calculation, and unnecessary calculation of the order is omitted, and the amount of calculation in the elliptic curve constituting apparatus is reduced.
[0140]
In addition, the calculation of the multiplication point kP of the elliptic curve in the elliptic curve order calculator has a large number of repetitions of doubling compared to addition. In general, the calculation amount of kP is EA when the calculation amount of the addition operation of the elliptic curve is EA, and the calculation amount of the doubling operation is ED.
| K | × (ED + EA / 3)
Given in. Here, | k | is the number of bits of k. Note that this is a case where a calculation method called Signed Binary Method is used. When this calculation method is used, the calculation amount of kP according to the conventional example 3 is 17 × PMul × | k |, and the calculation amount of kP according to the present invention is 15.3 × PMul × | k |. Therefore, the effect of reducing the calculation amount of kP according to the present invention is great.
4 Other variations
Although the elliptic curve constituting device according to the present invention has been described based on the embodiments, it is needless to say that the present invention is not limited to these embodiments. You may comprise as follows.
(1) The present invention may be an elliptic curve application device including the elliptic curve constituting device described above. Specific examples of the elliptic curve application device include an encryption communication system comprising an encryption device and a decryption device, a digital signature system comprising a digital signature device and a signature verification device, an error correction code transmission device, and a correction comprising an error correction device error. It is a communication system.
[0141]
The encryption communication system uses an elliptic curve to perform communication without leaking communication contents to other than a specific communication partner. The digital signature system uses an elliptic curve to show the validity of the communication contents to the communication partner or prove the identity. The error correction communication system uses the elliptic curve to recover missing information and changed information on the communication line and generate original information.
(2) The elliptic curve setting unit 502 sets a = −3 and b = t for the parameters a and b in the elliptic curve E: y ^ 2 = x ^ 3 + ax + b. May be.
[0142]
The elliptic curve setting unit 502 defines the discriminant TD described above for the curve E on the rational number field: y ^ 2 = x ^ 3 + ax + b (a and b are integers), and the probability that the discriminant TD has a square factor Parameters a and b are selected so that becomes smaller than a predetermined threshold value. Here, as an example, the predetermined threshold is 0.001. In this case, as described in the above embodiment, the safety of the elliptic curve can be expected to increase.
(3) The present invention may be an elliptic curve calculation device that calculates points on an elliptic curve defined on the polynomial remainder ring shown in the elliptic curve order calculation unit 504.
(4) The present invention may be an elliptic curve order calculator that calculates the order of the elliptic curve shown in the elliptic curve order calculator 504.
(5) The present invention may be the elliptic curve calculation method, elliptic curve order calculation method, and elliptic curve construction method described in the present embodiment.
[0143]
The elliptic curve calculation method, the elliptic curve order calculation method, and the elliptic curve construction method may be a computer program that implements the computer, or may be a digital signal that includes the computer program.
Further, the present invention records the computer program or the digital signal on a computer-readable recording medium, for example, a floppy disk, a hard disk, a CD-ROM, an MO, a DVD, a DVD-ROM, a DVD-RAM, a semiconductor memory, etc. It is good also as what you did. Further, the present invention may be the computer program or the digital signal recorded on these recording media.
[0144]
In the present invention, the computer program or the digital signal may be transmitted via an electric communication line, a wireless or wired communication line, a network represented by the Internet, or the like.
(6) The present invention may be a combination of the above-described embodiment, a plurality of modified examples, or a part of the above-described embodiment and a plurality of modified examples.
[0145]
【The invention's effect】
As explained above, the present invention provides a polynomial β ^ 2-f (α) (where f (α) = α ^ 3 + aα + b, where a and b are constants) and a polynomial h (α) ( Here, h (α) is a polynomial relating to α) and an elliptic curve E on a two-variable polynomial remainder ring related to α and β modulo α: y ^ 2 = doubling on f (x) or An elliptic curve calculation device for performing addition, an acquisition means for acquiring affine coordinates of one or more points on the elliptic curve E from outside and calculation information indicating a type of doubling or addition, and acquired 1 Conversion means for generating one or more Jacobiian coordinates by performing the following coordinate transformation on the one or more affine coordinates, and the coordinate transformation includes the affine coordinates (φ ( α), β × ψ (α)) (where φ (α) and ψ (α) are polynomials) and polynomial X (α = F (α) × φ (α), polynomial Y (α) = f (α) ^ 2 × ψ (α), and polynomial Z (α) = 1, and the Jacobiian coordinates (X (α): Y ( α): β × Z (α)), and further includes doubling and addition on the Jacobiian coordinates, and for the one or more generated Jacobiian coordinates, Computation means for calculating one Jacobian coordinate on the elliptic curve E by performing the doubling or addition shown.
[0146]
Here, the acquisition means acquires affine coordinates of one point on the elliptic curve E and calculation information indicating doubling, or affine coordinates of two different points on the elliptic curve E; Calculation information indicating addition, and the conversion means performs the coordinate conversion on the acquired one or two affine coordinates to generate one or two Jacobian coordinates, respectively, The calculation means may be configured to respectively perform doubling or addition indicated by the acquired calculation information on the generated one or two Jacobiian coordinates.
[0147]
Here, the calculation performed by the elliptic curve calculation device on the points on the elliptic curve E is addition, and the acquisition means is affine coordinates (X1 (α), β of two different points on the elliptic curve E). × Y1 (α)) and (X2 (α), β × Y2 (α)) and calculation information indicating addition, and the conversion means obtains the two affine coordinates (X1 (α), β × Y1). (Α)) and (X2 (α), β × Y2 (α)) are subjected to the coordinate transformation to obtain two Jacobian coordinates (X1 (α): Y1 (α): β × Z1 (α )) And (X2 (α): Y2 (α): β × Z2 (α)), and the calculation means calculates the calculation U1 (α) = X1 (α) × Z2 (α) ^ 2, the calculation U2 (Α) = X2 (α) × Z1 (α) ^ 2, operation S1 (α) = Y1 (α) × Z2 (α) ^ 3, operation S2 (α) = Y2 (α) × Z1 (α) ^ 3. Operation H (α) U2 (α) −U1 (α) and operation r (α) = S2 (α) −S1 (α) are performed, and then operation X3 (α) = − H (α) ^ 3−2 × U1 (α ) × H (α) ^ 2 + r (α) ^ 2, operation Y3 (α) = − S1 (α) × H (α) ^ 3 + r (α) × (U1 (α) × H (α) ^ 2-X3 (Α)) and the operation Z3 (α) = Z1 (α) × Z2 (α) × H (α), and then the Jacobiian coordinates (X3 (α): Y3 (α): β × Z3 (α)) ) May be calculated.
[0148]
Here, the calculation performed on the point on the elliptic curve E by the elliptic curve calculation device is doubling, and the acquisition means is affine coordinates of one point on the elliptic curve E (X1 (α), β × Y1 (α)) and calculation information indicating doubling are obtained, and the conversion means converts the coordinate conversion for the one affine coordinate (X1 (α), β × Y1 (α)). To generate one Jacobiian coordinate (X1 (α): Y1 (α): β × Z1 (α)), and the computing means computes S (α) = 4 × X1 (α) × Y1. (Α) ^ 2, operation M (α) = 3 × X1 (α) ^ 2 + a × Z1 (α) ^ 4 × f (α) ^ 2 and operation T (α) = − 2 × S (α) + M ( [alpha]) ^ 2, and then operation X3 ([alpha]) = T ([alpha]), operation Y3 ([alpha]) =-8 * Y1 ([alpha]) ^ 4 + M ([alpha]) * (S ([alpha])-T ([alpha]) ) And operation Z3 (α) = 2 × Y1 (α) × Z (Alpha) performed, then, Jacobian coordinates (X3 (α): Y3 (α): β × Z3 (α)) may be configured to calculate a.
[0149]
Here, the acquisition means includes affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)) and addition of two different points on the elliptic curve E. Or the affine coordinates (X1 (α), β × Y1 (α)) of one point on the elliptic curve E and the calculation information indicating doubling, and the conversion means Performs the coordinate transformation on the two affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)) to obtain two Jacobians. Coordinates (X1 (α): Y1 (α): β × Z1 (α)) and (X2 (α): Y2 (α): β × Z2 (α)) are generated, or the one affine coordinate The coordinate transformation is performed on (X1 (α), β × Y1 (α)) to generate one Jacobian coordinate (X1 (α): Y1 (α): β × Z1 (α)). When the obtained calculation information indicates addition, the calculation means calculates calculation U1 (α) = X1 (α) × Z2 (α) ^ 2, calculation U2 (α) = X2 (α) × Z1 ( α) ^ 2, operation S1 (α) = Y1 (α) × Z2 (α) ^ 3, operation S2 (α) = Y2 (α) × Z1 (α) ^ 3, operation H (α) = U2 (α ) −U1 (α) and operation r (α) = S2 (α) −S1 (α), and then operation X3 (α) = − H (α) ^ 3−2 × U1 (α) × H (Α) ^ 2 + r (α) ^ 2, operation Y3 (α) = − S1 (α) × H (α) ^ 3 + r (α) × (U1 (α) × H (α) ^ 2-X3 (α) ) And Z3 (α) = Z1 (α) × Z2 (α) × H (α), and then calculate Jacobiian coordinates (X3 (α): Y3 (α): β × Z3 (α)). When the obtained calculation information indicates doubling, the calculation S (α) = 4 × X1 (Α) × Y1 (α) ^ 2, operation M (α) = 3 × X1 (α) ^ 2 + a × Z1 (α) ^ 4 × f (α) ^ 2 and operation T (α) = − 2 × S (Α) + M (α) ^ 2 is performed, and then calculation X3 (α) = T (α), calculation Y3 (α) = − 8 × Y1 (α) ^ 4 + M (α) × (S (α) −T (α)) and the operation Z3 (α) = 2 × Y1 (α) × Z1 (α), then the Jacobiian coordinates (X3 (α): Y3 (α): β × Z3 (α)) May be calculated.
[0150]
According to these configurations, compared to the conventional example, the calculation amount of the polynomial multiplication of the addition formula is increased by 1 PMul, and the calculation amount of the doubling formula is decreased by 2 PMul. Usually, the number of operations for doubling is greater than the number of operations for addition, so a decrease in the amount of calculation for doubling greatly contributes to a decrease in the total amount of calculation, and the amount of calculation in the elliptic curve calculation device decreases. effective.
[0151]
In addition, the present invention is an elliptic curve order calculator that calculates the order of an elliptic curve using a SEA algorithm, and the elliptic curve order calculator includes the above-described elliptic curve calculator.
Here, the elliptic curve order calculator may be configured to include the above elliptic curve calculator.
[0152]
Here, the elliptic curve order calculator may be configured to include the above elliptic curve calculator.
According to these configurations, compared to the conventional example, the calculation amount of the polynomial multiplication of the addition formula is increased by 1 PMul, and the calculation amount of the doubling formula is decreased by 2 PMul. Usually, the number of operations for doubling is greater than the number of operations for addition, so a decrease in the amount of calculation for doubling greatly contributes to a decrease in the total amount of calculation, and the amount of calculation in the elliptic curve order calculator decreases. There is an effect of doing.
[0153]
Further, the present invention is an elliptic curve construction device for determining a parameter of an elliptic curve E having a high security and p defined as a finite field GF (p), and generating random numbers. Means, parameter generating means for selecting a parameter of the elliptic curve E including the random number, so that the probability that the discriminant of the elliptic curve E has a square factor is smaller than a predetermined threshold, and the selected parameter A finiteness determining means for determining whether or not the specified elliptic curve E has a point having a finite order on a rational number field, and when the elliptic curve E is determined not to have a point having a finite order In addition, the order calculating means for calculating the order m of the elliptic curve E, and when the order m is calculated, the order m is a prime number, and the order m is not a prime number p. Whether the condition is satisfied Until the order m is a prime number and the order m is not a prime number p, the random number generation means, the parameter generation means, the safety determination means, and the safety determination means Repetitive control means for controlling the finiteness determining means, the order calculating means and the safety determining means to perform random number generation, parameter generation, finiteness determination, order calculation and safety determination, respectively; Parameter output means for outputting the selected parameter when it is determined that the order m is a prime number and the order m is not a prime number p.
[0154]
According to this configuration, since there is a high probability that the highly safe elliptic curve is selected in advance by the parameter generation means, the step of selecting the elliptic curve and determining its safety is not repeated many times. There is an effect that the amount of calculation in the apparatus is reduced.
Further, before performing the order calculation by the finiteness determination means, it is determined whether or not the elliptic curve has high safety by determining whether or not the elliptic curve has a point having a finite order. Therefore, an elliptic curve with low safety can be rejected without performing the order calculation, and there is an effect that the unnecessary order calculation is omitted and the amount of calculation in the elliptic curve constituting apparatus is reduced.
[0155]
Here, the elliptic curve E is represented by y ^ 2 = x ^ 3 + ax + b, where parameter a and parameter b are constants, the parameter generation means sets parameter a = -3, and parameter b is By selecting as the generated random number, the parameter may be selected so that the probability that the discriminant of the elliptic curve E has a square factor is smaller than a predetermined threshold value.
[0156]
According to this configuration, the parameter generation means selects the elliptic curve E: y ^ 2 = x ^ 3-3x + b as the highly safe elliptic curve in advance, and therefore the step of selecting the elliptic curve and determining its safety is performed. There is an effect that the calculation amount in the elliptic curve construction device is reduced without being repeated many times.
Here, the finiteness determining means regards the elliptic curve E as an elliptic curve EQ on a rational number field, has two prime numbers p1 and p2 in advance, and p1 ≠ p2, and the two prime numbers p1 and p2 are When the reduced elliptic curves Ep1 and Ep2 are calculated as the moduli, the orders m1 and m2 are respectively calculated, the calculated orders m1 and m2 are determined to be prime, and the elliptic curves are determined to be prime. You may comprise so that it may determine that E does not have a point of a finite order on a rational number field.
[0157]
According to this configuration, before the order calculation is performed by the finiteness determination means, it is determined that the orders m1 and m2 of the elliptic curves Ep1 and Ep2 reduced by modulo the two primes p1 and p2 are relatively prime. By doing so, it is determined whether or not the safety of the elliptic curve is high, so that it is possible to reject the elliptical curve with low safety without performing the order calculation, and therefore, useless order calculation is omitted. It is possible to reduce the amount of calculation in the elliptic curve construction device.
[0158]
Here, the finiteness determining means has primes p1 = 5 and primes p2 = 7 in advance, and the order m1 of elliptic curves Ep1, Ep2 reduced by modulo two primes p1 = 5 and p2 = 7, You may comprise so that m2 may be calculated, respectively.
According to this configuration, the finiteness determining means determines that the orders m1 and m2 of the elliptic curves Ep1 and Ep2 reduced by using the prime number p1 = 5 and the prime number p2 = 7 as modulo are prime. There is an effect that the amount of calculation can be minimized.
[0159]
Here, the order calculating means performs the order calculation of the elliptic curve by the SEA algorithm, and the polynomial β ^ 2-f (α) (where f (α) = α ^ 3 + aα + b, where a and b are An elliptic curve E on a two-variable polynomial remainder ring with respect to variables α and β modulo a constant h) and a polynomial h (α) (where h (α) is a polynomial with respect to α). It may include an elliptic curve calculation unit that performs doubling or addition on a point on = f (x), and the elliptic curve calculation unit may include the above elliptic curve calculation device.
[0160]
According to these configurations, compared to the conventional example, the calculation amount of the polynomial multiplication of the addition formula is increased by 1 PMul, and the calculation amount of the doubling formula is decreased by 2 PMul. Usually, the number of operations for doubling is greater than the number of operations for addition, so a decrease in the amount of calculation for doubling greatly contributes to a decrease in the total amount of calculation, and the amount of calculation in the elliptic curve construction device decreases. effective.
[0161]
The present invention also relates to an elliptic curve application device that performs processing using an elliptic curve, wherein p is a prime number and is defined on a finite field GF (p), and has high safety. The apparatus may include an elliptic curve forming unit that determines parameters of the elliptic curve E having the elliptic curve forming unit.
[0162]
According to this configuration, the elliptic curve application device has the same effects as the elliptic curve configuration device. Thus, it is possible to provide an elliptic curve application device that enables a secure encryption method and signature method at high speed, and its practical value is great.
The present invention also includes a polynomial β ^ 2-f (α) (where f (α) = α ^ 3 + aα + b, where a and b are constants) and a polynomial h (α) (where h ( α) is a polynomial related to α), and is obtained by performing doubling or addition on the elliptic curve E: y ^ 2 = f (x) on the two-variable polynomial remainder ring modulo α and β. An elliptic curve calculation method used in an apparatus comprising a means, a conversion means, and a calculation means, wherein the acquisition means performs an affine coordinate of one or more points on the elliptic curve E from the outside and doubling or adding An acquisition step of acquiring calculation information indicating the type, and a conversion step of generating one or more Jacobian coordinates by performing the following coordinate conversion on the one or more affine coordinates acquired by the conversion means: And the coordinate transformation is performed after the points on the elliptic curve E Coordinate (φ (α), β × ψ (α)) (where φ (α) and ψ (α) are polynomials), polynomial X (α) = f (α) × φ (α) , Polynomial Y (α) = f (α) ^ 2 × ψ (α) and polynomial Z (α) = 1, and Jacobian coordinates (X (α): Y (α): β × Z (α)) And the doubling and addition on the Jacobiian coordinates, and the doubling indicated by the obtained calculation information with respect to the one or more Jacobiian coordinates generated by the calculation means. A calculation step of calculating one Jacobian coordinate on the elliptic curve E by performing the calculation or the addition.
[0163]
When this method is used, the same effect as the elliptic curve calculation device is obtained.
In the present invention, p is a prime number, is defined on a finite field GF (p), determines a parameter of an elliptic curve E having high security, a random number generation unit, a parameter generation unit, a finiteness determination unit, An elliptic curve construction method used in an elliptic curve construction device comprising order calculation means, safety judgment means, repetition control means, and parameter output means, comprising: a random number generation step for generating random numbers by the random number generation means; A parameter generation step of selecting a parameter of the elliptic curve E including the random number so that the probability that the discriminant of the elliptic curve E has a square factor is smaller than a predetermined threshold by the parameter generation means; A finiteness determination step for determining whether or not the elliptic curve E specified by the selected parameter has a point having a finite order on the rational number field by the sex determination means. And an order calculation step for calculating the order m of the elliptic curve E when the order calculation means determines that the elliptic curve E does not have a point having a finite order; Safety judgment step for judging whether the order m is a prime number and the order m ≠ prime p is satisfied when the order m is calculated by the sex judgment means Until the order m is determined to be a prime number and the order m is not a prime number p, the random number generation step, the parameter generation step, and the finiteness determination step. The repetition control means controls the order calculation step and the safety determination step so as to perform random number generation, parameter generation, finiteness determination, order calculation and safety determination, respectively. Return control And a parameter output step of outputting the selected parameter when it is determined by the parameter output means that the order m is a prime number and the order m is not a prime number p. .
[0164]
When this method is used, the same effects as those of the elliptic curve construction device are obtained.
The present invention also includes a polynomial β ^ 2-f (α) (where f (α) = α ^ 3 + aα + b, where a and b are constants) and a polynomial h (α) (where h ( α) is a polynomial related to α), and is obtained by performing doubling or addition on the elliptic curve E: y ^ 2 = f (x) on the two-variable polynomial remainder ring modulo α and β. A computer-readable recording medium storing an elliptic curve calculation program used in an elliptic curve calculation device comprising means, conversion means, and calculation means, wherein the program is read from the outside by the acquisition means. An acquisition step for acquiring affine coordinates of one or more points above and calculation information indicating the type of doubling or addition; and for the one or more affine coordinates acquired by the conversion means, Apply coordinate transformation to one or more Jaco a transformation step of generating ian coordinates, wherein the coordinate transformation includes affine coordinates (φ (α), β × ψ (α)) of points on the elliptic curve E (where φ (α) and ψ (α ) Is a polynomial) by a polynomial X (α) = f (α) × φ (α), a polynomial Y (α) = f (α) ^ 2 × ψ (α) and a polynomial Z (α) = 1. Transform to generate Jacobiian coordinates (X (α): Y (α): β × Z (α)), and further includes doubling and addition on the Jacobiian coordinates, and the generation means performs the generation A calculation step of calculating one Jacobian coordinate on the elliptic curve E by performing the doubling or addition indicated by the acquired calculation information on the one or more Jacobiian coordinates.
[0165]
Here, the acquisition step acquires affine coordinates of one point on the elliptic curve E and calculation information indicating doubling, or affine coordinates of two different points on the elliptic curve E; Calculation information indicating addition, and the conversion step performs the coordinate conversion on the acquired one or two affine coordinates to generate one or two Jacobian coordinates, respectively, The calculation step may be configured to respectively perform doubling or addition indicated by the acquired calculation information on the generated one or two Jacobiian coordinates.
[0166]
Here, the calculation performed on the points on the elliptic curve E by the elliptic curve calculation device is addition, and the acquisition step includes the affine coordinates (X1 (α), β of two different points on the elliptic curve E). × Y1 (α)) and (X2 (α), β × Y2 (α)) and calculation information indicating addition, and the conversion step includes the two affine coordinates (X1 (α), β × Y1). (Α)) and (X2 (α), β × Y2 (α)) are subjected to the coordinate transformation to obtain two Jacobian coordinates (X1 (α): Y1 (α): β × Z1 (α )) And (X2 (α): Y2 (α): β × Z2 (α)), and the calculation step includes a calculation U1 (α) = X1 (α) × Z2 (α) ^ 2, a calculation U2 (Α) = X2 (α) × Z1 (α) ^ 2, operation S1 (α) = Y1 (α) × Z2 (α) ^ 3, operation S2 (α) = Y2 (α) × Z1 (α) ^ 3, The calculation H (α) = U2 (α) −U1 (α) and the operation r (α) = S2 (α) −S1 (α) are performed, and then the operation X3 (α) = − H (α) ^ 3 −2 × U1 (α) × H (α) ^ 2 + r (α) ^ 2, operation Y3 (α) = − S1 (α) × H (α) ^ 3 + r (α) × (U1 (α) × H ( α) ^ 2−X3 (α)) and the operation Z3 (α) = Z1 (α) × Z2 (α) × H (α), and then the Jacobiian coordinates (X3 (α): Y3 (α): (β × Z3 (α)) may be calculated.
[0167]
Here, the calculation performed by the elliptic curve calculation device on the points on the elliptic curve E is doubling, and the acquisition step includes the affine coordinates (X1 (α), β × Y1 (α)) and calculation information indicating doubling are acquired, and the conversion step performs the coordinate conversion on the one affine coordinate (X1 (α), β × Y1 (α)). To generate one Jacobian coordinate (X1 (α): Y1 (α): β × Z1 (α)), and the calculation step includes a calculation S (α) = 4 × X1 (α) × Y1. (Α) ^ 2, operation M (α) = 3 × X1 (α) ^ 2 + a × Z1 (α) ^ 4 × f (α) ^ 2 and operation T (α) = − 2 × S (α) + M ( [alpha]) ^ 2, and then operation X3 ([alpha]) = T ([alpha]), operation Y3 ([alpha]) =-8 * Y1 ([alpha]) ^ 4 + M ([alpha]) * (S ([alpha])-T ([alpha]) ) And operation Z3 (α) = 2 × Performed 1 (α) × Z1 (α), then, Jacobian coordinates (X3 (α): Y3 (α): β × Z3 (α)) may be configured to calculate a.
[0168]
Here, the acquisition step includes affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)) of two different points on the elliptic curve E and addition. Or the calculation information indicating the affine coordinates (X1 (α), β × Y1 (α)) and doubling of one point on the elliptic curve E is obtained, and the conversion step Performs the coordinate transformation on the two affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)) to obtain two Jacobians. Coordinates (X1 (α): Y1 (α): β × Z1 (α)) and (X2 (α): Y2 (α): β × Z2 (α)) are generated, or the one affine coordinate The coordinate transformation is applied to (X1 (α), β × Y1 (α)), and one Jacobian coordinate (X1 (α): Y1 (α): β × Z1 (α)) When the obtained calculation information indicates addition, the calculation step calculates calculation U1 (α) = X1 (α) × Z2 (α) ^ 2, calculation U2 (α) = X2 (α) × Z1 (α) ^ 2, operation S1 (α) = Y1 (α) × Z2 (α) ^ 3, operation S2 (α) = Y2 (α) × Z1 (α) ^ 3, operation H (α) = U2 (α) −U1 (α) and operation r (α) = S2 (α) −S1 (α) are performed, and then operation X3 (α) = − H (α) ^ 3−2 × U1 (α ) × H (α) ^ 2 + r (α) ^ 2, operation Y3 (α) = − S1 (α) × H (α) ^ 3 + r (α) × (U1 (α) × H (α) ^ 2-X3 (Α)) and the operation Z3 (α) = Z1 (α) × Z2 (α) × H (α), and then the Jacobiian coordinates (X3 (α): Y3 (α): β × Z3 (α)) ) And the obtained calculation information indicates doubling, the calculation S ( ) = 4 × X1 (α) × Y1 (α) ^ 2, operation M (α) = 3 × X1 (α) ^ 2 + a × Z1 (α) ^ 4 × f (α) ^ 2 and operation T (α) = −2 × S (α) + M (α) ^ 2, then operation X3 (α) = T (α), operation Y3 (α) = − 8 × Y1 (α) ^ 4 + M (α) × (S (α) −T (α)) and calculation Z3 (α) = 2 × Y1 (α) × Z1 (α) are performed, and then Jacobiian coordinates (X3 (α): Y3 (α): β × Z3 (α)) may be calculated.
[0169]
By executing this program by a computer, the same effects as the elliptic curve calculation device can be obtained.
In the present invention, p is a prime number, is defined on a finite field GF (p), determines a parameter of an elliptic curve E having high security, a random number generation unit, a parameter generation unit, a finiteness determination unit, A computer-readable recording medium for recording an elliptic curve construction program used in an elliptic curve construction device comprising order calculation means, safety judgment means, repetition control means, and parameter output means, the program The random number generation step for generating a random number by the random number generation means, and the random number generation step by the parameter generation means so that the probability that the discriminant of the elliptic curve E has a square factor is smaller than a predetermined threshold value. A parameter generation step of selecting parameters of the elliptic curve E to be included; and the elliptic curve E specified by the selected parameter by the finiteness determination means A finiteness determination step for determining whether or not the point has a finite order on the rational number field, and the order calculation means determines that the elliptic curve E does not have a point having a finite order In addition, when the order m is calculated by the order calculating step for calculating the order m of the elliptic curve E and the safety judging means, the order m is a prime number, and the order The safety determination step for determining whether or not the condition that m ≠ prime p is satisfied, and the order m is a prime number and the order m ≠ prime p by the safety determination step. Until the determination, the random number generation step, the parameter generation step, the finiteness determination step, the order calculation step, and the safety determination step, respectively, random number generation, parameter generation, finiteness determination, order The order m is a prime number and the order m is not a prime number p by the repeat control step controlled by the repeat control means and the parameter output means so as to perform calculation and safety judgment. A parameter output step of outputting the selected parameter when it is determined that there is a parameter.
[0170]
Here, the elliptic curve E is represented by y ^ 2 = x ^ 3 + ax + b, where parameter a and parameter b are constants, and the parameter generation step sets parameter a = -3, and parameter b is By selecting as the generated random number, the parameter may be selected so that the probability that the discriminant of the elliptic curve E has a square factor is smaller than a predetermined threshold value.
[0171]
Here, the finiteness determination step regards the elliptic curve E as an elliptic curve EQ on a rational number field, has two prime numbers p1 and p2 in advance, p1 ≠ p2, and the two prime numbers p1 and p2 are When the reduced elliptic curves Ep1 and Ep2 are calculated as the moduli, the orders m1 and m2 are respectively calculated, the calculated orders m1 and m2 are determined to be prime, and the elliptic curves are determined to be prime. You may comprise so that it may determine that E does not have a point of a finite order on a rational number field.
[0172]
Here, in the finiteness determination step, the orders m1 of the elliptic curves Ep1 and Ep2 reduced in advance by having prime numbers p1 = 5 and prime numbers p2 = 7 and modulo two prime numbers p1 = 5 and p2 = 7, You may comprise so that m2 may be calculated, respectively.
By executing this program by a computer, the same effects as those of the elliptic curve constituting apparatus can be obtained.
[Brief description of the drawings]
FIG. 1 is a flowchart showing a conventional method of constructing an elliptic curve.
FIG. 2 is a flowchart showing a conventional elliptic curve construction method by Lercier. Continue to FIG.
FIG. 3 is a flowchart showing a conventional method for constructing an elliptic curve by Lercier. Continuing from FIG.
FIG. 4 is a block diagram showing a configuration of an elliptic curve forming apparatus 500 as one embodiment according to the present invention.
FIG. 5 is a block diagram showing a specific configuration of an elliptic curve construction device 500;
6 shows an example of data stored in an information storage unit 507 of the elliptic curve construction device 500. FIG.
FIG. 7 is a flowchart showing a procedure for constructing an elliptic curve of the elliptic curve construction device 500;
FIG. 8 is a flowchart showing a procedure for calculating the order of an elliptic curve by the elliptic curve order calculator 504 of the elliptic curve construction device 500;
9 is a flowchart showing a procedure for calculating t mod L ^ n by an elliptic curve order calculator 504 of the elliptic curve construction device 500. FIG.
FIG. 10 is a flowchart showing a procedure for adding or doubling points on an elliptic curve of the elliptic curve construction device 500;
[Explanation of symbols]
500 Elliptic curve construction device
501 Random number generator
502 Elliptic curve setting part
503 Elliptic curve finiteness determination unit
504 Elliptic curve order calculator
505 Elliptic curve condition determination unit
506 Control unit
507 Information storage unit
508 input section
509 Output unit
510 Parameter storage unit 510

Claims (33)

Polynomial β ^ 2-f (α) (where f (α) = α ^ 3 + aα + b, a and b are constants) and polynomial h (α) (where h (α) is related to α An elliptic curve computing device that performs doubling or addition on a two-variable polynomial remainder ring with respect to variables α and β modulo (which is a polynomial), y ^ 2 = f (x),
Acquisition means for acquiring affine coordinates of one or more points on the elliptic curve E from outside and calculation information indicating a type of doubling or addition;
Conversion means for performing the following coordinate transformation on the obtained one or more affine coordinates to generate one or more Jacobian coordinates,
In the coordinate transformation, the affine coordinates (φ (α), β × ψ (α)) of the point on the elliptic curve E (where φ (α) and ψ (α) are polynomials),
Polynomial X (α) = f (α) × φ (α),
The Jacobian coordinates (X (α): Y (α): β × Z (α)) are converted by the polynomial Y (α) = f (α) ^ 2 × ψ (α) and the polynomial Z (α) = 1. Generate
Further, an elliptic curve is obtained by performing doubling or addition on the Jacobiian coordinates, and performing the doubling or addition indicated by the acquired operation information on the one or more generated Jacobiian coordinates. An elliptic curve calculation device comprising calculation means for calculating one Jacobiian coordinate on E. The acquisition means acquires affine coordinates of one point on the elliptic curve E and calculation information indicating doubling, or indicates addition of affine coordinates of two different points on the elliptic curve E. Get the calculation information and
The conversion means performs the coordinate conversion on the acquired one or two affine coordinates to generate one or two Jacobian coordinates, respectively.
2. The elliptic curve according to claim 1, wherein the calculation unit performs doubling or addition indicated by the acquired calculation information on the generated one or two Jacobiian coordinates, respectively. Arithmetic unit. The calculation that the elliptic curve calculation device performs on the points on the elliptic curve E is addition,
The acquisition means calculates affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)) and addition of two different points on the elliptic curve E. Get information,
The converting means is configured to calculate the two affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)).
By performing the coordinate transformation, two Jacobiian coordinates (X1 (α): Y1 (α): β × Z1 (α)) and (X2 (α): Y2 (α): β × Z2 (α)) are obtained. Generate
The computing means is
Operation U1 (α) = X1 (α) × Z2 (α) ^ 2,
Operation U2 (α) = X2 (α) × Z1 (α) ^ 2,
Operation S1 (α) = Y1 (α) × Z2 (α) ^ 3,
Operation S2 (α) = Y2 (α) × Z1 (α) ^ 3,
Perform operation H (α) = U2 (α) −U1 (α) and operation r (α) = S2 (α) −S1 (α),
next,
Operation X3 (α) = − H (α) ^ 3−2 × U1 (α) × H (α) ^ 2 + r (α) ^ 2,
Operation Y3 (α) = − S1 (α) × H (α) ^ 3 + r (α) × (U1 (α) × H (α) ^ 2−X3 (α)) and operation Z3 (α) = Z1 (α ) × Z2 (α) × H (α),
Next, the Jacobian coordinate (X3 (α): Y3 (α): β × Z3 (α)) is calculated. The calculation performed by the elliptic curve calculation device on the points on the elliptic curve E is doubling,
The acquisition means acquires affine coordinates (X1 (α), β × Y1 (α)) of one point on the elliptic curve E and calculation information indicating doubling,
The conversion means performs the coordinate conversion on the one affine coordinate (X1 (α), β × Y1 (α)),
Generate one Jacobian coordinate (X1 (α): Y1 (α): β × Z1 (α)),
The computing means is
Operation S (α) = 4 × X1 (α) × Y1 (α) ^ 2,
Perform operation M (α) = 3 × X1 (α) ^ 2 + a × Z1 (α) ^ 4 × f (α) ^ 2 and operation T (α) = − 2 × S (α) + M (α) ^ 2. ,
next,
Operation X3 (α) = T (α),
Calculation Y3 (α) = − 8 × Y1 (α) ^ 4 + M (α) × (S (α) −T (α)) and calculation Z3 (α) = 2 × Y1 (α) × Z1 (α) are performed. ,
Next, the Jacobian coordinate (X3 (α): Y3 (α): β × Z3 (α)) is calculated. The acquisition means includes
Obtain affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)) of two different points on the elliptic curve E and calculation information indicating addition,
Or, obtain affine coordinates (X1 (α), β × Y1 (α)) of one point on the elliptic curve E and calculation information indicating doubling,
The converting means includes
The two affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)) are subjected to the coordinate transformation, and two Jacobian coordinates ( X1 (α): Y1 (α): β × Z1 (α)) and (X2 (α): Y2 (α): β × Z2 (α))
Alternatively, the coordinate conversion is performed on the one affine coordinate (X1 (α), β × Y1 (α)),
Generate one Jacobian coordinate (X1 (α): Y1 (α): β × Z1 (α)),
The computing means is
When the obtained calculation information indicates addition,
Operation U1 (α) = X1 (α) × Z2 (α) ^ 2,
Operation U2 (α) = X2 (α) × Z1 (α) ^ 2,
Operation S1 (α) = Y1 (α) × Z2 (α) ^ 3,
Operation S2 (α) = Y2 (α) × Z1 (α) ^ 3,
Perform operation H (α) = U2 (α) −U1 (α) and operation r (α) = S2 (α) −S1 (α),
next,
Operation X3 (α) = − H (α) ^ 3−2 × U1 (α) × H (α) ^ 2 + r (α) ^ 2,
Operation Y3 (α) = − S1 (α) × H (α) ^ 3 + r (α) × (U1 (α) × H (α) ^ 2−X3 (α)) and operation Z3 (α) = Z1 (α ) × Z2 (α) × H (α),
Next, the Jacobian coordinates (X3 (α): Y3 (α): β × Z3 (α)) are calculated,
When the obtained calculation information indicates doubling,
Operation S (α) = 4 × X1 (α) × Y1 (α) ^ 2,
Perform operation M (α) = 3 × X1 (α) ^ 2 + a × Z1 (α) ^ 4 × f (α) ^ 2 and operation T (α) = − 2 × S (α) + M (α) ^ 2. ,
next,
Operation X3 (α) = T (α),
Calculation Y3 (α) = − 8 × Y1 (α) ^ 4 + M (α) × (S (α) −T (α)) and calculation Z3 (α) = 2 × Y1 (α) × Z1 (α) are performed. ,
Next, the Jacobian coordinate (X3 (α): Y3 (α): β × Z3 (α)) is calculated. An elliptic curve order calculator for calculating the order of an elliptic curve using a SEA algorithm,
The elliptic curve order calculation apparatus includes the elliptic curve calculation apparatus according to claim 1. The elliptic curve order calculation apparatus according to claim 6, wherein the elliptic curve order calculation apparatus includes the elliptic curve calculation apparatus according to claim 2. The elliptic curve order calculation apparatus according to claim 7, wherein the elliptic curve order calculation apparatus includes the elliptic curve calculation apparatus according to claim 5. p is a prime number, is defined on a finite field GF (p), and is an elliptic curve constructing device that determines parameters of an elliptic curve E having high security,
Random number generating means for generating a random number;
Parameter generating means for selecting a parameter of the elliptic curve E including the random number so that the probability that the discriminant of the elliptic curve E has a square factor is smaller than a predetermined threshold;
Finiteness determining means for determining whether or not the elliptic curve E specified by the selected parameter has a point having a finite order on the rational number field;
Order calculation means for calculating the order m of the elliptic curve E when the elliptic curve E is determined not to have a point having a finite order;
Safety judgment means for judging whether or not the condition that the order m is a prime number and the order m ≠ prime p is satisfied when the order m is calculated;
The random number generating means, the parameter generating means, the finiteness determining means, until the safety determining means determines that the order m is a prime number and the order m ≠ prime p. Repeat control means for controlling the order calculation means and the safety determination means to perform random number generation, parameter generation, finiteness determination, order calculation and safety determination, respectively.
An elliptic curve construction device comprising: parameter output means for outputting the selected parameter when it is determined that the order m is a prime number and the order m ≠ prime p . The elliptic curve E is represented by y ^ 2 = x ^ 3 + ax + b, where parameter a and parameter b are constants,
The parameter generation means sets parameter a = −3 and selects parameter b as the generated random number so that the probability that the discriminant of the elliptic curve E has a square factor is smaller than a predetermined threshold value. 10. The elliptic curve construction device according to claim 9, wherein a parameter is selected. The finiteness determining means regards the elliptic curve E as an elliptic curve EQ on a rational number, has two prime numbers p1 and p2 in advance, p1 ≠ p2, and reduces the two prime numbers p1 and p2 as a modulus. When the orders m1 and m2 of the elliptic curves Ep1 and Ep2 are calculated, respectively, it is determined that the calculated orders m1 and m2 are relatively prime, and the elliptic curve E is a rational number The apparatus according to claim 10, wherein it is determined that the point has no finite order on the field. The finiteness determining means has primes p1 = 5 and primes p2 = 7 in advance, and reduces the orders m1, m2 of elliptic curves Ep1, Ep2 reduced by modulo two primes p1 = 5, p2 = 7, respectively. The elliptic curve construction device according to claim 11, which is calculated. The order calculating means calculates the order of the elliptic curve by the SEA algorithm, and the polynomial β ^ 2-f (α) (where f (α) = α ^ 3 + aα + b, where a and b are constants. ) And a polynomial h (α) (where h (α) is a polynomial with respect to α) an elliptic curve E on a two-variable polynomial remainder ring with respect to variables α and β: y ^ 2 = f ( x) includes elliptic curve calculation means for doubling or adding to the upper point;
The elliptic curve construction device according to claim 11, wherein the elliptic curve computation means includes the elliptic curve computation device according to claim 1. The elliptic curve construction device according to claim 13, wherein the elliptic curve computation means includes the elliptic curve computation device according to claim 2. The elliptic curve construction device according to claim 14, wherein the elliptic curve computation means includes the elliptic curve computation device according to claim 5. An elliptic curve application device that performs processing using an elliptic curve,
The elliptic curve application device includes an elliptic curve constructing means for determining a parameter of an elliptic curve E having a high security, wherein p is a prime number and defined on a finite field GF (p),
The elliptic curve application device comprising the elliptic curve configuration device according to claim 9. The elliptic curve application device according to claim 16, wherein the elliptic curve configuration means includes the elliptic curve configuration device according to claim 10. The elliptic curve application device according to claim 17, wherein the elliptic curve configuration means includes the elliptic curve configuration device according to claim 11. The elliptic curve application device according to claim 18, wherein the elliptic curve configuration means includes the elliptic curve configuration device according to claim 12. The elliptic curve application device according to claim 18, wherein the elliptic curve configuration means includes the elliptic curve configuration device according to claim 13. The elliptic curve application device according to claim 20, wherein the elliptic curve configuration means includes the elliptic curve configuration device according to claim 14. The elliptic curve application device according to claim 21, wherein the elliptic curve configuration means includes the elliptic curve configuration device according to claim 15. Polynomial β ^ 2−f (α) (where f (α) = α ^ 3 + aα + b, a and b are constants) and polynomial h (α) (where h (α) is related to α An elliptic curve E on the two-variable polynomial remainder ring with respect to the variables α and β modulo (which is a polynomial) and doubling or adding over y ^ 2 = f (x), and obtaining means, converting means and computing An elliptic curve calculation method used in an apparatus comprising:
An acquisition step of acquiring, from the outside, affine coordinates of one or more points on the elliptic curve E and calculation information indicating a type of doubling or addition from the outside;
A conversion step of performing the following coordinate conversion on the acquired one or more affine coordinates by the conversion means to generate one or more Jacobiian coordinates;
In the coordinate transformation, the affine coordinates (φ (α), β × ψ (α)) of the point on the elliptic curve E (where φ (α) and ψ (α) are polynomials),
Polynomial X (α) = f (α) × φ (α),
The Jacobian coordinates (X (α): Y (α): β × Z (α)) are converted by the polynomial Y (α) = f (α) ^ 2 × ψ (α) and the polynomial Z (α) = 1. Generate
Further, it has doubling and addition on the Jacobiian coordinates, and the doubling or addition indicated by the obtained calculation information is performed on the one or more Jacobiian coordinates generated by the calculation means. And a calculation step of calculating one Jacobian coordinate on the elliptic curve E by applying an elliptic curve calculation method. p is a prime number, is defined on the finite field GF (p), determines parameters of the elliptic curve E having high security, random number generation means, parameter generation means, finiteness determination means, order calculation means, safety An elliptic curve construction method used in an elliptic curve construction device comprising sex determination means, repetition control means, and parameter output means,
A random number generating step for generating a random number by the random number generating means;
A parameter generating step of selecting a parameter of the elliptic curve E including the random number so that the probability that the discriminant of the elliptic curve E has a square factor is smaller than a predetermined threshold by the parameter generating means;
A finiteness determining step for determining whether or not the elliptic curve E specified by the selected parameter has a point having a finite order on the rational number field by the finiteness determining means;
An order calculation step of calculating the order m of the elliptic curve E when the order calculation means determines that the elliptic curve E does not have a point having a finite order;
Safety that determines whether the order m is a prime number and the order m ≠ prime p satisfies the condition when the order m is calculated by the safety judging means A determination step;
Until the order m is determined to be a prime number and the order m is not a prime number p, the random number generation step, the parameter generation step, the finiteness determination step, the safety determination step, Repeat control controlled by the repeat control means so as to perform random number generation, parameter generation, finiteness determination, order calculation and safety determination for the order calculation step and the safety determination step, respectively. Steps,
A parameter output step of outputting the selected parameter when the parameter output means determines that the order m is a prime number and the order m is not a prime number p. An elliptic curve construction method. Polynomial β ^ 2−f (α) (where f (α) = α ^ 3 + aα + b, a and b are constants) and polynomial h (α) (where h (α) is related to α An elliptic curve E on the two-variable polynomial remainder ring with respect to the variables α and β modulo (which is a polynomial) and doubling or adding over y ^ 2 = f (x), and obtaining means, converting means and computing A computer-readable recording medium recording an elliptic curve calculation program used in an elliptic curve calculation device comprising:
The program is
An acquisition step of acquiring affine coordinates of one or more points on the elliptic curve E from the outside and calculation information indicating a type of doubling or addition from the outside, and one or more acquired by the conversion unit A transformation step of performing the following coordinate transformation on the affine coordinates to generate one or more Jacobian coordinates,
In the coordinate transformation, the affine coordinates (φ (α), β × ψ (α)) of the point on the elliptic curve E (where φ (α) and ψ (α) are polynomials),
Polynomial X (α) = f (α) × φ (α),
The Jacobian coordinates (X (α): Y (α): β × Z (α)) are converted by the polynomial Y (α) = f (α) ^ 2 × ψ (α) and the polynomial Z (α) = 1. Generate
Further, it has doubling and addition on the Jacobiian coordinates, and the doubling or addition indicated by the obtained calculation information is performed on the one or more Jacobiian coordinates generated by the calculation means. And a calculation step of calculating one Jacobian coordinate on the elliptic curve E. The acquisition step acquires the affine coordinates of one point on the elliptic curve E and calculation information indicating doubling, or indicates the addition of affine coordinates of two different points on the elliptic curve E. Get the calculation information and
The transformation step performs the coordinate transformation on the obtained one or two affine coordinates to generate one or two Jacobian coordinates,
26. The recording medium according to claim 25, wherein the calculation step performs doubling or addition indicated by the acquired calculation information on the generated one or two Jacobiian coordinates, respectively. . The calculation that the elliptic curve calculation device performs on the points on the elliptic curve E is addition,
The acquisition step includes affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)) of two different points on the elliptic curve E and an operation indicating addition. Get information,
The conversion step is performed on the two affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)).
By performing the coordinate transformation, two Jacobiian coordinates (X1 (α): Y1 (α): β × Z1 (α)) and (X2 (α): Y2 (α): β × Z2 (α)) are obtained. Generate
The calculation step includes:
Operation U1 (α) = X1 (α) × Z2 (α) ^ 2,
Operation U2 (α) = X2 (α) × Z1 (α) ^ 2,
Operation S1 (α) = Y1 (α) × Z2 (α) ^ 3,
Operation S2 (α) = Y2 (α) × Z1 (α) ^ 3,
Perform operation H (α) = U2 (α) −U1 (α) and operation r (α) = S2 (α) −S1 (α),
next,
Operation X3 (α) = − H (α) ^ 3−2 × U1 (α) × H (α) ^ 2 + r (α) ^ 2,
Operation Y3 (α) = − S1 (α) × H (α) ^ 3 + r (α) × (U1 (α) × H (α) ^ 2−X3 (α)) and operation Z3 (α) = Z1 (α ) × Z2 (α) × H (α),
27. The recording medium according to claim 26, wherein Jacobiian coordinates (X3 (α): Y3 (α): β × Z3 (α)) are calculated. The calculation performed by the elliptic curve calculation device on the points on the elliptic curve E is doubling,
The acquisition step acquires affine coordinates (X1 (α), β × Y1 (α)) of one point on the elliptic curve E and calculation information indicating doubling,
The transformation step performs the coordinate transformation on the one affine coordinate (X1 (α), β × Y1 (α)),
Generate one Jacobian coordinate (X1 (α): Y1 (α): β × Z1 (α)),
The calculation step includes:
Operation S (α) = 4 × X1 (α) × Y1 (α) ^ 2,
Perform operation M (α) = 3 × X1 (α) ^ 2 + a × Z1 (α) ^ 4 × f (α) ^ 2 and operation T (α) = − 2 × S (α) + M (α) ^ 2. ,
next,
Operation X3 (α) = T (α),
Calculation Y3 (α) = − 8 × Y1 (α) ^ 4 + M (α) × (S (α) −T (α)) and calculation Z3 (α) = 2 × Y1 (α) × Z1 (α) are performed. ,
27. The recording medium according to claim 26, wherein Jacobiian coordinates (X3 (α): Y3 (α): β × Z3 (α)) are calculated. The obtaining step includes
Obtain affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)) of two different points on the elliptic curve E and calculation information indicating addition,
Or, obtain affine coordinates (X1 (α), β × Y1 (α)) of one point on the elliptic curve E and calculation information indicating doubling,
The converting step includes
The two affine coordinates (X1 (α), β × Y1 (α)) and (X2 (α), β × Y2 (α)) are subjected to the coordinate transformation, and two Jacobian coordinates ( X1 (α): Y1 (α): β × Z1 (α)) and (X2 (α): Y2 (α): β × Z2 (α))
Alternatively, the coordinate conversion is performed on the one affine coordinate (X1 (α), β × Y1 (α)),
Generate one Jacobian coordinate (X1 (α): Y1 (α): β × Z1 (α)),
The calculation step includes:
When the obtained calculation information indicates addition,
Operation U1 (α) = X1 (α) × Z2 (α) ^ 2,
Operation U2 (α) = X2 (α) × Z1 (α) ^ 2,
Operation S1 (α) = Y1 (α) × Z2 (α) ^ 3,
Operation S2 (α) = Y2 (α) × Z1 (α) ^ 3,
Perform operation H (α) = U2 (α) −U1 (α) and operation r (α) = S2 (α) −S1 (α),
next,
Operation X3 (α) = − H (α) ^ 3−2 × U1 (α) × H (α) ^ 2 + r (α) ^ 2,
Operation Y3 (α) = − S1 (α) × H (α) ^ 3 + r (α) × (U1 (α) × H (α) ^ 2−X3 (α)) and operation Z3 (α) = Z1 (α ) × Z2 (α) × H (α),
Next, the Jacobian coordinates (X3 (α): Y3 (α): β × Z3 (α)) are calculated,
When the obtained calculation information indicates doubling,
Operation S (α) = 4 × X1 (α) × Y1 (α) ^ 2,
Perform operation M (α) = 3 × X1 (α) ^ 2 + a × Z1 (α) ^ 4 × f (α) ^ 2 and operation T (α) = − 2 × S (α) + M (α) ^ 2. ,
next,
Operation X3 (α) = T (α),
Calculation Y3 (α) = − 8 × Y1 (α) ^ 4 + M (α) × (S (α) −T (α)) and calculation Z3 (α) = 2 × Y1 (α) × Z1 (α) are performed. ,
27. The recording medium according to claim 26, wherein Jacobiian coordinates (X3 (α): Y3 (α): β × Z3 (α)) are calculated. p is a prime number, is defined on the finite field GF (p), determines parameters of the elliptic curve E having high security, random number generation means, parameter generation means, finiteness determination means, order calculation means, safety A computer-readable recording medium that records an elliptic curve configuration program used in an elliptic curve configuration apparatus having sex determination means, repetition control means, and parameter output means,
The program is
A random number generating step for generating a random number by the random number generating means;
A parameter generating step of selecting a parameter of the elliptic curve E including the random number so that the probability that the discriminant of the elliptic curve E has a square factor is smaller than a predetermined threshold by the parameter generating means;
A finiteness determining step for determining whether or not the elliptic curve E specified by the selected parameter has a point having a finite order on the rational number field by the finiteness determining means;
An order calculation step of calculating the order m of the elliptic curve E when the order calculation means determines that the elliptic curve E does not have a point having a finite order;
Safety that determines whether the order m is a prime number and the order m ≠ prime p satisfies the condition when the order m is calculated by the safety judging means A determination step;
Until the order m is determined to be a prime number and the order m is not a prime number p, the random number generation step, the parameter generation step, the finiteness determination step, the safety determination step, Repeat control controlled by the repeat control means so as to perform random number generation, parameter generation, finiteness determination, order calculation and safety determination for the order calculation step and the safety determination step, respectively. Steps,
A parameter output step of outputting the selected parameter when the parameter output means determines that the order m is a prime number and the order m is not a prime number p. A recording medium. The elliptic curve E is represented by y ^ 2 = x ^ 3 + ax + b, where parameter a and parameter b are constants,
In the parameter generation step, parameter a = −3 and parameter b is selected as the generated random number so that the probability that the discriminant of elliptic curve E has a square factor is smaller than a predetermined threshold value. The recording medium according to claim 30, wherein a parameter is selected. The finiteness determination step regards the elliptic curve E as an elliptic curve EQ on a rational field, has two prime numbers p1 and p2 in advance, p1 ≠ p2, and reduces the two prime numbers p1 and p2 as a modulus. When the orders m1 and m2 of the elliptic curves Ep1 and Ep2 are calculated, respectively, it is determined that the calculated orders m1 and m2 are relatively prime, and the elliptic curve E is a rational number 32. The recording medium according to claim 31, wherein the recording medium is determined not to have a finite number of points on the body. In the finiteness determination step, the orders m1 and m2 of elliptic curves Ep1 and Ep2 obtained by reducing prime numbers p1 = 5 and p2 = 7 in advance and having prime numbers p1 = 5 and prime numbers p2 = 7, respectively. The recording medium according to claim 32, wherein the recording medium is calculated.

Images