JP2000321979A - 多項式演算装置、楕円曲線位数計算装置、楕円曲線生成装置及び楕円曲線暗号システム - Google Patents
多項式演算装置、楕円曲線位数計算装置、楕円曲線生成装置及び楕円曲線暗号システムInfo
- Publication number
- JP2000321979A JP2000321979A JP11133814A JP13381499A JP2000321979A JP 2000321979 A JP2000321979 A JP 2000321979A JP 11133814 A JP11133814 A JP 11133814A JP 13381499 A JP13381499 A JP 13381499A JP 2000321979 A JP2000321979 A JP 2000321979A
- Authority
- JP
- Japan
- Prior art keywords
- elliptic curve
- order
- unit
- calculating
- polynomial
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Abstract
(57)【要約】
【課題】 本発明は、高速な多項式演算装置を提供し、
それにより高速に安全な楕円曲線を生成することのでき
る楕円曲線生成装置を提供する。 【解決手段】 有限体GF(q)(q=p^n、p:素数)上の多項式
r(X)を法とする 1変数多項式剰余環R=GF(q)[X]/(r(X))
において、Rに属する多項式X、f(X)を入力とし、Rに属
する多項式X^q、f(X)^((q-1)/2)を出力する多項式演算
装置であって、前記多項式Xに対して、X^p、X^(2p)、X^
(3p)、...、X^((d-1)p)を計算する第1冪乗計算部と、f
(X)^((q-1)/2)を計算する第2冪乗計算部を備え、前記第
2冪乗計算手段は、前記第1冪乗計算手段から出力される
結果を用いる。
それにより高速に安全な楕円曲線を生成することのでき
る楕円曲線生成装置を提供する。 【解決手段】 有限体GF(q)(q=p^n、p:素数)上の多項式
r(X)を法とする 1変数多項式剰余環R=GF(q)[X]/(r(X))
において、Rに属する多項式X、f(X)を入力とし、Rに属
する多項式X^q、f(X)^((q-1)/2)を出力する多項式演算
装置であって、前記多項式Xに対して、X^p、X^(2p)、X^
(3p)、...、X^((d-1)p)を計算する第1冪乗計算部と、f
(X)^((q-1)/2)を計算する第2冪乗計算部を備え、前記第
2冪乗計算手段は、前記第1冪乗計算手段から出力される
結果を用いる。
Description
【０００１】
【発明の属する技術分野】本発明は情報セキュリテイ技
術としての暗号技術及び、誤り訂正技術に関するもので
あり、特に、楕円曲線を用いて実現する暗号及びデジタ
ル署名技術及び、楕円曲線を用いて実現する誤り訂正技
術に関するものである。
術としての暗号技術及び、誤り訂正技術に関するもので
あり、特に、楕円曲線を用いて実現する暗号及びデジタ
ル署名技術及び、楕円曲線を用いて実現する誤り訂正技
術に関するものである。
【０００２】
【従来の技術】秘密通信方式とは、特定の通信相手以外
に通信内容を漏らすことなく通信を行なう方式である。
またデジタル署名方式とは、通信相手に通信内容の正当
性を示したり、本人であることを証明する通信方式であ
る。この署名方式には公開鍵暗号とよばれる暗号方式を
用いる。公開鍵暗号は通信相手が多数の時、通信相手ご
とに異なる暗号鍵を容易に管理するための方式であり、
多数の通信相手と通信を行なうのに不可欠な基盤技術で
ある。簡単に説明すると、これは暗号化鍵と復号化鍵が
異なり、復号化鍵は秘密にするが、暗号化鍵を公開する
方式である。この公開鍵暗号の安全性の根拠に用いられ
るものに離散対数問題がある。離散対数問題には代表的
に、有限体上定義されるもの及び楕円曲線上定義される
ものがある。これはNeal Koblitz,"A Course in Number
theory and Cryptography",Springer-Verlag,1987に詳
しく述べられている。楕円曲線上の離散対数問題を以下
に述べる。
に通信内容を漏らすことなく通信を行なう方式である。
またデジタル署名方式とは、通信相手に通信内容の正当
性を示したり、本人であることを証明する通信方式であ
る。この署名方式には公開鍵暗号とよばれる暗号方式を
用いる。公開鍵暗号は通信相手が多数の時、通信相手ご
とに異なる暗号鍵を容易に管理するための方式であり、
多数の通信相手と通信を行なうのに不可欠な基盤技術で
ある。簡単に説明すると、これは暗号化鍵と復号化鍵が
異なり、復号化鍵は秘密にするが、暗号化鍵を公開する
方式である。この公開鍵暗号の安全性の根拠に用いられ
るものに離散対数問題がある。離散対数問題には代表的
に、有限体上定義されるもの及び楕円曲線上定義される
ものがある。これはNeal Koblitz,"A Course in Number
theory and Cryptography",Springer-Verlag,1987に詳
しく述べられている。楕円曲線上の離散対数問題を以下
に述べる。
【０００３】(楕円曲線上の離散対数問題)E(GF(q))を有
限体GF(q)(q=p^n)上定義された楕円曲線Eとし、Eの位数
が大きな素数で割れる元Gをベースポイントとする。こ
のとき、Eの与えられた元Yに対して、 Y=xG となる整数xが存在するならばxを求めよ。
限体GF(q)(q=p^n)上定義された楕円曲線Eとし、Eの位数
が大きな素数で割れる元Gをベースポイントとする。こ
のとき、Eの与えられた元Yに対して、 Y=xG となる整数xが存在するならばxを求めよ。
【０００４】楕円曲線上の離散対数問題には様々な解読
法が提案されており、それらに対して安全な楕円曲線を
構成する必要がある。現存するすべての解読法に対して
安全な楕円曲線は有限体GF(q)上の楕円曲線の場合、位
数がq-1,q,q+1でないこと及び位数が大きい素因数をも
つことである。このとき、解読に必要な計算時間は位数
の最大素因数に関する指数時間である(情報処理学会監
修,岡本龍明,太田和夫共編,"暗号・ゼロ知識証明,数
論",共立出版,1995,155ページ〜156ページ参照)。した
がって、位数が素数である楕円曲線を用いると暗号の安
全性が最大になる。楕円曲線の安全性は、その楕円曲線
の位数を調べることにより確認できる。
法が提案されており、それらに対して安全な楕円曲線を
構成する必要がある。現存するすべての解読法に対して
安全な楕円曲線は有限体GF(q)上の楕円曲線の場合、位
数がq-1,q,q+1でないこと及び位数が大きい素因数をも
つことである。このとき、解読に必要な計算時間は位数
の最大素因数に関する指数時間である(情報処理学会監
修,岡本龍明,太田和夫共編,"暗号・ゼロ知識証明,数
論",共立出版,1995,155ページ〜156ページ参照)。した
がって、位数が素数である楕円曲線を用いると暗号の安
全性が最大になる。楕円曲線の安全性は、その楕円曲線
の位数を調べることにより確認できる。
【０００５】楕円曲線の従来の構成法として、 (1)CM法を用いる構成法 (2)位数計算アルゴリズムを用いる構成法 がある。(1)は楕円曲線の構成が簡単であるが、ランダ
ムに楕円曲線を構成できない。これはA.Miyaji,"On Ord
inary Elliptic Curve Cryptosystems",ASIACRYPT'91,S
pringer-Verlag,1991,460ページ〜469ページが詳しい。
(2)はランダムに楕円曲線を構成できるが、構成時間が
長い。
ムに楕円曲線を構成できない。これはA.Miyaji,"On Ord
inary Elliptic Curve Cryptosystems",ASIACRYPT'91,S
pringer-Verlag,1991,460ページ〜469ページが詳しい。
(2)はランダムに楕円曲線を構成できるが、構成時間が
長い。
【０００６】(従来例1)図４は従来例1の位数計算アルゴ
リズムを用いる楕円曲線生成装置を示すブロック図であ
る。(N.Koblitz,"Ellitpic Curve Implementation of Z
ero-Knowledge Blobs",J.Cryptology,vol.4,No.3,1991,
207ページ〜213ページ参照)。従来例1の楕円曲線生成装
置は、乱数生成部101と、楕円曲線設定部102と、楕円曲
線位数計算部103からなる。以下、従来例1の動作を説明
する。 step1:乱数生成部101 乱数を発生する。 step2:楕円曲線設定部102 step1により生成した乱数に対して、楕円曲線を設定す
る。 step3:楕円曲線位数計算部103 step2の楕円曲線の位数を計算する。 step4:楕円曲線条件判定部104 step2の楕円曲線を与えられた条件で判定する。与えら
れた条件を満たすときのみ、楕円曲線のパラメ−タを出
力する。満たさないとき、step1に戻る。
リズムを用いる楕円曲線生成装置を示すブロック図であ
る。(N.Koblitz,"Ellitpic Curve Implementation of Z
ero-Knowledge Blobs",J.Cryptology,vol.4,No.3,1991,
207ページ〜213ページ参照)。従来例1の楕円曲線生成装
置は、乱数生成部101と、楕円曲線設定部102と、楕円曲
線位数計算部103からなる。以下、従来例1の動作を説明
する。 step1:乱数生成部101 乱数を発生する。 step2:楕円曲線設定部102 step1により生成した乱数に対して、楕円曲線を設定す
る。 step3:楕円曲線位数計算部103 step2の楕円曲線の位数を計算する。 step4:楕円曲線条件判定部104 step2の楕円曲線を与えられた条件で判定する。与えら
れた条件を満たすときのみ、楕円曲線のパラメ−タを出
力する。満たさないとき、step1に戻る。
【０００７】上記で述べたように位数計算アルゴリズム
を用いる構成法は計算時間が長い。上記従来例1で最も
計算時間を要する箇所がstep3の楕円曲線位数計算部で
ある。楕円曲線の位数を計算するアルゴリズムの一つに
Schoofのアルゴリズムがある。このアルゴリズムは多項
式時間で構成されるが、実用的な計算時間ではない。Sc
hoofのアルゴリズムはElkies,Atkinによって、SEAアル
ゴリズムとして改良されている。
を用いる構成法は計算時間が長い。上記従来例1で最も
計算時間を要する箇所がstep3の楕円曲線位数計算部で
ある。楕円曲線の位数を計算するアルゴリズムの一つに
Schoofのアルゴリズムがある。このアルゴリズムは多項
式時間で構成されるが、実用的な計算時間ではない。Sc
hoofのアルゴリズムはElkies,Atkinによって、SEAアル
ゴリズムとして改良されている。
【０００８】(従来例2)図５は従来例2のSEAアルゴリズ
ムによる楕円曲線位数計算装置の構成を示すブロック図
で、R.Lercier,F.Morain,"Counting the number of poi
nts on elliptic curves over finite fields: strateg
ies performances",EUROCRYPT'95,Springer-Verlag,199
5,79ページ〜94ページにあるものである。従来例2の楕
円曲線位数計算装置は、初期値設定部201と、楕円曲線
位数情報計算部202と、計算終了判定部203と、楕円曲線
位数決定部204からなる。以下、従来例2の動作を説明す
る。
ムによる楕円曲線位数計算装置の構成を示すブロック図
で、R.Lercier,F.Morain,"Counting the number of poi
nts on elliptic curves over finite fields: strateg
ies performances",EUROCRYPT'95,Springer-Verlag,199
5,79ページ〜94ページにあるものである。従来例2の楕
円曲線位数計算装置は、初期値設定部201と、楕円曲線
位数情報計算部202と、計算終了判定部203と、楕円曲線
位数決定部204からなる。以下、従来例2の動作を説明す
る。
【０００９】pを素数、q=p^nとし、GF(q)上の楕円曲線E
の方程式をy^2=x^3+ax+bとする。ここで、x^aはxのa乗
を示す。求める位数をmとし、tをm=q+1-tを満たすもの
とする。f(x)=x^3+ax+bとする。 step1:初期値設定部201 l:=2とする。 step2:楕円曲線位数情報計算部202 t mod lを求める。その際、Modular多項式Φl(T)の一変
数Tの多項式環GF(q)[T]における因数分解の一次因子の
数に対応して以下のように求める。 Modular多項式
は、R.Schoof,"Counting points on elliptic curve ov
er finite fields",Journal de Theorie des Nombres d
e Bordeux 7,1995,219ページ〜254ページに詳しく述べ
られている。
の方程式をy^2=x^3+ax+bとする。ここで、x^aはxのa乗
を示す。求める位数をmとし、tをm=q+1-tを満たすもの
とする。f(x)=x^3+ax+bとする。 step1:初期値設定部201 l:=2とする。 step2:楕円曲線位数情報計算部202 t mod lを求める。その際、Modular多項式Φl(T)の一変
数Tの多項式環GF(q)[T]における因数分解の一次因子の
数に対応して以下のように求める。 Modular多項式
は、R.Schoof,"Counting points on elliptic curve ov
er finite fields",Journal de Theorie des Nombres d
e Bordeux 7,1995,219ページ〜254ページに詳しく述べ
られている。
【００１０】step2-1.一次因子の数が2のとき t mod l を求める。さらに、Isogeny cycle 法により、
t mod l^n(n=2,3,...)を求める。Isogeny cycke法は、
J.M.Couveignes,F.Morain,"Schoof's algorithmand iso
geny cycles",ANTS-I,Lecture Notes in Compute Scien
ce 877,Springer-Verlag,1994,43ページ〜58ページに詳
しく述べられている。
t mod l^n(n=2,3,...)を求める。Isogeny cycke法は、
J.M.Couveignes,F.Morain,"Schoof's algorithmand iso
geny cycles",ANTS-I,Lecture Notes in Compute Scien
ce 877,Springer-Verlag,1994,43ページ〜58ページに詳
しく述べられている。
【００１１】step2-2.一次因子の数が1またはl+1のとき t mod l を求める。さらに、Isogeny cycle 法により、
t mod l^n(n=2,3,...)を求める。このとき、Isogeny cy
cle 法を適用可能であるか判定する。
t mod l^n(n=2,3,...)を求める。このとき、Isogeny cy
cle 法を適用可能であるか判定する。
【００１２】step2-3.一次因子の数が0のとき t mod lの取り得る値を集合[0,1,...,l-1]から絞り込
む。 step3:計算終了判定部203 l1^(n1)×l2^(n2)×...×lk^(nk)<4×q^(1/2)であると
き(l1,l2,...,lk は素数であり、lk=l)、l:=(lの次の素
数)として、step2に戻る。それ以外は次のstep4へ進
む。 step4:楕円曲線位数決定部204 match&sortアルゴリズムにより、位数を確定し、出力す
る。match&sortアルゴリズムは、R. Lercier,"Algorith
mique des courbes elliptiques dans les corps fini
s", These,Ecole Polytechnique-LIX,1997 に詳しく述
べられている。
む。 step3:計算終了判定部203 l1^(n1)×l2^(n2)×...×lk^(nk)<4×q^(1/2)であると
き(l1,l2,...,lk は素数であり、lk=l)、l:=(lの次の素
数)として、step2に戻る。それ以外は次のstep4へ進
む。 step4:楕円曲線位数決定部204 match&sortアルゴリズムにより、位数を確定し、出力す
る。match&sortアルゴリズムは、R. Lercier,"Algorith
mique des courbes elliptiques dans les corps fini
s", These,Ecole Polytechnique-LIX,1997 に詳しく述
べられている。
【００１３】step3の判定はstep2で小さい素数lkに対し
て、t mod lk^(nk)まで求めていると仮定している。ste
p2-1,step2-2ではt mod l^n(n=1,2,3,...)を求めるがこ
れはフロベニウス写像と呼ばれる写像の固有値を計算す
ることによってできる。具体的には楕円曲線E上のl等分
点(X,Y)を用いて、以下の式のkを求める。
て、t mod lk^(nk)まで求めていると仮定している。ste
p2-1,step2-2ではt mod l^n(n=1,2,3,...)を求めるがこ
れはフロベニウス写像と呼ばれる写像の固有値を計算す
ることによってできる。具体的には楕円曲線E上のl等分
点(X,Y)を用いて、以下の式のkを求める。
【００１４】(X^q,Y^q)=k(X,Y) ここで、k(X,Y)は点(X,Y)の楕円曲線上のk倍点であり、
Y^2=f(X)=X^3+aX+bである。上式の計算はXを変数とし、
GF(q)係数である多項式をある多項式を法とするXに関す
る1変数多項式剰余環上の楕円曲線演算によって行う。
上式のkを求めるため、上式左辺のX^qとY^q=Y×Y^(q-1)
を求める必要がある。このため、X^qとY^(q-1)=f(X)^
((q-1)/2)の計算を行う。これらの計算に最も時間を必
要とする。X^qは以下のアルゴリズムを用いて求められ
ることが知られている。
Y^2=f(X)=X^3+aX+bである。上式の計算はXを変数とし、
GF(q)係数である多項式をある多項式を法とするXに関す
る1変数多項式剰余環上の楕円曲線演算によって行う。
上式のkを求めるため、上式左辺のX^qとY^q=Y×Y^(q-1)
を求める必要がある。このため、X^qとY^(q-1)=f(X)^
((q-1)/2)の計算を行う。これらの計算に最も時間を必
要とする。X^qは以下のアルゴリズムを用いて求められ
ることが知られている。
【００１５】(従来例3)図６は従来例3の多項式演算装置
の構成を示すブロック図である。従来例3の多項式演算
装置は、第1冪乗計算部301と、第2冪乗計算部302からな
る。以下、従来例3の動作を説明する。
の構成を示すブロック図である。従来例3の多項式演算
装置は、第1冪乗計算部301と、第2冪乗計算部302からな
る。以下、従来例3の動作を説明する。
【００１６】法となる多項式をr(X)、その次数をdとす
る。 step1:第1冪乗計算部301 X^p、X^(2p)、X^(3p)、...、X^((d-1)p) mod r(X)を求
める。 step2:第2冪乗計算部302 X^(p^2)、X^(p^3)、...、X^(p^n)を求める。
る。 step1:第1冪乗計算部301 X^p、X^(2p)、X^(3p)、...、X^((d-1)p) mod r(X)を求
める。 step2:第2冪乗計算部302 X^(p^2)、X^(p^3)、...、X^(p^n)を求める。
【００１７】step2では、GF(q)係数である多項式g(X)に
対して、 (g(X))^p=g(X^p) となることを利用している(D.E.Knuth著,中川圭介訳,"
準数値算法/算術演算",KNUTH 第4分冊,サイエンス社,26
6ページ〜267ページ参照)。この性質より、g(X)のX,X^
2,...,X^(d-1)を第1冪計算部で求めたX^p,X^(2p),...,X
^((d-1)p)に置き換えることで、(g(X)^p)が得られる。
対して、 (g(X))^p=g(X^p) となることを利用している(D.E.Knuth著,中川圭介訳,"
準数値算法/算術演算",KNUTH 第4分冊,サイエンス社,26
6ページ〜267ページ参照)。この性質より、g(X)のX,X^
2,...,X^(d-1)を第1冪計算部で求めたX^p,X^(2p),...,X
^((d-1)p)に置き換えることで、(g(X)^p)が得られる。
【００１８】このように、X^qを求めるアルゴリズムは
存在するが、Y^(q-1)を求める有効なアルゴリズムが発
表されていないため、単に従来の冪乗算を用いた計算を
行う。しかし、冪乗算は計算量が大きいため、SEA アル
ゴリズムの計算量が大きくなるという問題がある。
存在するが、Y^(q-1)を求める有効なアルゴリズムが発
表されていないため、単に従来の冪乗算を用いた計算を
行う。しかし、冪乗算は計算量が大きいため、SEA アル
ゴリズムの計算量が大きくなるという問題がある。
【００１９】
【発明が解決しようとする課題】楕円曲線暗号システム
において、安全な楕円曲線パラメータを生成することは
重要である。そのために、楕円曲線生成装置を用いる。
において、安全な楕円曲線パラメータを生成することは
重要である。そのために、楕円曲線生成装置を用いる。
【００２０】位数計算アルゴリズムを用いる楕円曲線の
生成装置では、位数計算部の実行時間が長い。位数計算
アルゴリズムの従来技術であるSEAアルゴリズム(従来例
2)においては、多項式剰余環上の冪乗算の計算量が大き
いという欠点がある。
生成装置では、位数計算部の実行時間が長い。位数計算
アルゴリズムの従来技術であるSEAアルゴリズム(従来例
2)においては、多項式剰余環上の冪乗算の計算量が大き
いという欠点がある。
【００２１】本発明は、以上の従来技術における問題点
を鑑みて行われたもので、多項式環上の冪乗算の計算時
間を短縮することにより、楕円曲線の位数計算の計算時
間を短縮し、これにより安全な公開鍵暗号及び署名方式
を提供することを目的とする。
を鑑みて行われたもので、多項式環上の冪乗算の計算時
間を短縮することにより、楕円曲線の位数計算の計算時
間を短縮し、これにより安全な公開鍵暗号及び署名方式
を提供することを目的とする。
【００２２】
【課題を解決するための手段】請求項1における発明
は、予め与えられた有限体GF(p)の拡大体GF(q)(q=p^n)
上の予め与えられた多項式r(X)(次数d)を法とする1変数
多項式剰余環R=GF(q)[X]/(r(X))において、Rに属する多
項式X、f(X)を入力とし、Rに属する多項式X^q、f(X)^
((q-1)/2)を出力する多項式演算装置であって、前記多
項式Xに対して、X^p、X^(2p)、X^(3p)、...、X^((d-1)
p)を計算する第1冪乗計算手段と、f(X)^((q-1)/2)を計
算する第2冪乗計算手段を備え、前記第2冪乗計算手段
は、前記第1冪乗計算手段から出力される結果を用いる
ことを特徴とする(ただし、p^nはpのn乗を示す)。
は、予め与えられた有限体GF(p)の拡大体GF(q)(q=p^n)
上の予め与えられた多項式r(X)(次数d)を法とする1変数
多項式剰余環R=GF(q)[X]/(r(X))において、Rに属する多
項式X、f(X)を入力とし、Rに属する多項式X^q、f(X)^
((q-1)/2)を出力する多項式演算装置であって、前記多
項式Xに対して、X^p、X^(2p)、X^(3p)、...、X^((d-1)
p)を計算する第1冪乗計算手段と、f(X)^((q-1)/2)を計
算する第2冪乗計算手段を備え、前記第2冪乗計算手段
は、前記第1冪乗計算手段から出力される結果を用いる
ことを特徴とする(ただし、p^nはpのn乗を示す)。
【００２３】請求項2における発明は、請求項1の第2冪
乗計算手段は、f(X)^((p-1)/2)を計算する中間計算を行
ってから、前記第1冪乗計算手段から出力される結果を
用いて、f(X)^((p^2-1)/2)=(f(X)^((p-1)/2))^p×f(X)^
((p-1)/2)、f(X)^((p^3-1)/2)=(f(X)^((p^2-1)/2))^p×
f(X)^((p-1)/2)、...、f(X)^((p^n-1)/2)=(f(X)^((p^(n
-1)-1)/2)^p×f(X)^((p-1)/2)により計算することを特
徴とする。
乗計算手段は、f(X)^((p-1)/2)を計算する中間計算を行
ってから、前記第1冪乗計算手段から出力される結果を
用いて、f(X)^((p^2-1)/2)=(f(X)^((p-1)/2))^p×f(X)^
((p-1)/2)、f(X)^((p^3-1)/2)=(f(X)^((p^2-1)/2))^p×
f(X)^((p-1)/2)、...、f(X)^((p^n-1)/2)=(f(X)^((p^(n
-1)-1)/2)^p×f(X)^((p-1)/2)により計算することを特
徴とする。
【００２４】請求項3における発明は、予め与えられた
有限体GF(p)の拡大体GF(q)(q=p^n)上の楕円曲線を入力
とし、前記楕円曲線の位数を出力する楕円曲線位数計算
装置であって、予め与えられた初期値を設定する初期値
設定部と、位数の情報を求める楕円曲線位数情報計算部
と、前記楕円曲線位数情報計算部の終了判定を行う計算
終了判定部と、前記楕円曲線位数情報計算部から出力さ
れる情報を用いて楕円曲線の位数を決定する楕円曲線位
数決定部を備え、前記楕円曲線位数情報計算部は、請求
項1に記載の多項式演算装置を有することを特徴とす
る。
有限体GF(p)の拡大体GF(q)(q=p^n)上の楕円曲線を入力
とし、前記楕円曲線の位数を出力する楕円曲線位数計算
装置であって、予め与えられた初期値を設定する初期値
設定部と、位数の情報を求める楕円曲線位数情報計算部
と、前記楕円曲線位数情報計算部の終了判定を行う計算
終了判定部と、前記楕円曲線位数情報計算部から出力さ
れる情報を用いて楕円曲線の位数を決定する楕円曲線位
数決定部を備え、前記楕円曲線位数情報計算部は、請求
項1に記載の多項式演算装置を有することを特徴とす
る。
【００２５】請求項4における発明は、予め与えられた
有限体GF(p)の拡大体GF(q)(q=p^n)上の楕円曲線を入力
とし、前記楕円曲線の位数を出力する楕円曲線位数計算
装置であって、予め与えられた初期値を設定する初期値
設定部と、位数の情報を求める楕円曲線位数情報計算部
と、前記楕円曲線位数情報計算部の終了判定を行う計算
終了判定部と、前記楕円曲線位数情報計算部から出力さ
れる情報を用いて楕円曲線の位数を決定する楕円曲線位
数決定部を備え、前記楕円曲線位数情報計算部は、請求
項2に記載の多項式演算装置を有することを特徴とす
る。
有限体GF(p)の拡大体GF(q)(q=p^n)上の楕円曲線を入力
とし、前記楕円曲線の位数を出力する楕円曲線位数計算
装置であって、予め与えられた初期値を設定する初期値
設定部と、位数の情報を求める楕円曲線位数情報計算部
と、前記楕円曲線位数情報計算部の終了判定を行う計算
終了判定部と、前記楕円曲線位数情報計算部から出力さ
れる情報を用いて楕円曲線の位数を決定する楕円曲線位
数決定部を備え、前記楕円曲線位数情報計算部は、請求
項2に記載の多項式演算装置を有することを特徴とす
る。
【００２６】請求項5における発明は、予め与えられた
有限体GF(p)の拡大体GF(q)(q=p^n)上で定義され、予め
与えられた条件を満たす楕円曲線を出力する楕円曲線生
成装置であって、予め与えられた楕円曲線設定値に基づ
いて、楕円曲線を設定する楕円曲線設定部と、前記有限
体上の楕円曲線の位数を計算する楕円曲線位数計算部
と、前記楕円曲線設定部で設定した楕円曲線を、前記与
えられた条件で判定する楕円曲線条件判定部を備え、前
期楕円曲線位数計算部は、請求項3に記載の楕円曲線位
数計算装置を有することを特徴とする。
有限体GF(p)の拡大体GF(q)(q=p^n)上で定義され、予め
与えられた条件を満たす楕円曲線を出力する楕円曲線生
成装置であって、予め与えられた楕円曲線設定値に基づ
いて、楕円曲線を設定する楕円曲線設定部と、前記有限
体上の楕円曲線の位数を計算する楕円曲線位数計算部
と、前記楕円曲線設定部で設定した楕円曲線を、前記与
えられた条件で判定する楕円曲線条件判定部を備え、前
期楕円曲線位数計算部は、請求項3に記載の楕円曲線位
数計算装置を有することを特徴とする。
【００２７】請求項6における発明は、予め与えられた
有限体GF(p)の拡大体GF(q)(q=p^n)上で定義され、予め
与えられた条件を満たす楕円曲線を出力する楕円曲線生
成装置であって、予め与えられた楕円曲線設定値に基づ
いて、楕円曲線を設定する楕円曲線設定部と、前記有限
体上の楕円曲線の位数を計算する楕円曲線位数計算部
と、前記楕円曲線設定部で設定した楕円曲線を、前記与
えられた条件で判定する楕円曲線条件判定部を備え、前
期楕円曲線位数計算部は、請求項4に記載の楕円曲線位
数計算装置を有することを特徴とする。
有限体GF(p)の拡大体GF(q)(q=p^n)上で定義され、予め
与えられた条件を満たす楕円曲線を出力する楕円曲線生
成装置であって、予め与えられた楕円曲線設定値に基づ
いて、楕円曲線を設定する楕円曲線設定部と、前記有限
体上の楕円曲線の位数を計算する楕円曲線位数計算部
と、前記楕円曲線設定部で設定した楕円曲線を、前記与
えられた条件で判定する楕円曲線条件判定部を備え、前
期楕円曲線位数計算部は、請求項4に記載の楕円曲線位
数計算装置を有することを特徴とする。
【００２８】請求項7における発明は、予め与えられた
有限体GF(p)の拡大体GF(q)(q=p^n)上で定義され、予め
与えられた条件を満たす楕円曲線を用いる楕円曲線暗号
システムであって、予め与えられた楕円曲線設定値に基
づいて、楕円曲線を設定する楕円曲線設定部と、前記有
限体上の楕円曲線の位数を計算する楕円曲線位数計算部
と、前記楕円曲線設定部で設定した楕円曲線を、前記与
えられた条件で判定する楕円曲線条件判定部を備え、前
期楕円曲線位数計算部は、請求項3に記載の楕円曲線位
数計算装置を有する楕円曲線生成装置により、生成され
ることを特徴とする。
有限体GF(p)の拡大体GF(q)(q=p^n)上で定義され、予め
与えられた条件を満たす楕円曲線を用いる楕円曲線暗号
システムであって、予め与えられた楕円曲線設定値に基
づいて、楕円曲線を設定する楕円曲線設定部と、前記有
限体上の楕円曲線の位数を計算する楕円曲線位数計算部
と、前記楕円曲線設定部で設定した楕円曲線を、前記与
えられた条件で判定する楕円曲線条件判定部を備え、前
期楕円曲線位数計算部は、請求項3に記載の楕円曲線位
数計算装置を有する楕円曲線生成装置により、生成され
ることを特徴とする。
【００２９】請求項8における発明は、予め与えられた
有限体GF(p)の拡大体GF(q)(q=p^n)上で定義され、予め
与えられた条件を満たす楕円曲線を用いる楕円曲線暗号
システムであって、予め与えられた楕円曲線設定値に基
づいて、楕円曲線を設定する楕円曲線設定部と、前記有
限体上の楕円曲線の位数を計算する楕円曲線位数計算部
と、前記楕円曲線設定部で設定した楕円曲線を、前記与
えられた条件で判定する楕円曲線条件判定部を備え、前
期楕円曲線位数計算部は、請求項4に記載の楕円曲線位
数計算装置を有する楕円曲線生成装置により、生成され
ることを特徴とする。
有限体GF(p)の拡大体GF(q)(q=p^n)上で定義され、予め
与えられた条件を満たす楕円曲線を用いる楕円曲線暗号
システムであって、予め与えられた楕円曲線設定値に基
づいて、楕円曲線を設定する楕円曲線設定部と、前記有
限体上の楕円曲線の位数を計算する楕円曲線位数計算部
と、前記楕円曲線設定部で設定した楕円曲線を、前記与
えられた条件で判定する楕円曲線条件判定部を備え、前
期楕円曲線位数計算部は、請求項4に記載の楕円曲線位
数計算装置を有する楕円曲線生成装置により、生成され
ることを特徴とする。
【００３０】
【発明の実施の形態】図１は、本実施形態における多項
式演算装置の構成を示すブロック図である。
式演算装置の構成を示すブロック図である。
【００３１】この多項式演算装置は、従来例2のSEAアル
ゴリズムの多項式剰余環上の冪乗演算を実現するもので
あり、GF(q)(q=p^n、p:素数)を有限体、Xを変数とし、G
F(q)係数である予め与えられたr(X)(次数d)を法とする1
変数多項式剰余環R=GF(q)[X]/(r(X))において、Rに属す
る多項式Xとf(X)を入力とし、X^qとf(X)^((q-1)/2)を出
力するものである。
ゴリズムの多項式剰余環上の冪乗演算を実現するもので
あり、GF(q)(q=p^n、p:素数)を有限体、Xを変数とし、G
F(q)係数である予め与えられたr(X)(次数d)を法とする1
変数多項式剰余環R=GF(q)[X]/(r(X))において、Rに属す
る多項式Xとf(X)を入力とし、X^qとf(X)^((q-1)/2)を出
力するものである。
【００３２】多項式演算装置40は、第1冪乗計算部401
と、第2冪乗計算部402と、第3冪乗計算部403と、第4冪
乗計算部404を備える。
と、第2冪乗計算部402と、第3冪乗計算部403と、第4冪
乗計算部404を備える。
【００３３】第1冪乗計算部401は、Rに属するXを入力と
し、X^p、X^(2p)、X^(3p)、...、X^((d-1)p)を計算し、
出力する。
し、X^p、X^(2p)、X^(3p)、...、X^((d-1)p)を計算し、
出力する。
【００３４】第2冪乗計算部402は、Rに属するXと第1冪
乗計算部401から出力されたX^p,X^(2p),...,X^((d-1)p)
を入力とし、X^qを出力する。
乗計算部401から出力されたX^p,X^(2p),...,X^((d-1)p)
を入力とし、X^qを出力する。
【００３５】第3冪乗計算部404は、Rに属するf(X)と第1
冪乗計算部401から出力されたX^p,X^(2p),...,X^((d-1)
p)を入力とし、f(X)^((q-1)/2)を計算する。
冪乗計算部401から出力されたX^p,X^(2p),...,X^((d-1)
p)を入力とし、f(X)^((q-1)/2)を計算する。
【００３６】(第2冪乗計算部402の構成)図２は、第2冪
乗計算部402の構成を示すブロック図である。
乗計算部402の構成を示すブロック図である。
【００３７】第2冪乗計算部402は、Rに属するXと第1冪
乗計算部401から出力されたX^p,X^(2p),...,X^((d-1)p)
を入力とし、X^qを出力する多項式演算装置である。
乗計算部401から出力されたX^p,X^(2p),...,X^((d-1)p)
を入力とし、X^qを出力する多項式演算装置である。
【００３８】第2冪乗計算部402は、初期値設定部4021
と、多項式変換部4022と、終了判定部4023を備える。
と、多項式変換部4022と、終了判定部4023を備える。
【００３９】初期値設定部4021は、c=1(cはカウンタ)、
g(X)=X^pに設定する。
g(X)=X^pに設定する。
【００４０】多項式変換部4022は、g(X)と第1冪乗計算
部401から出力されたX^p,X^(2p),...,X^((d-1)p)を入力
とし、(g(X))^pを計算し、g(X)に改めておく。
部401から出力されたX^p,X^(2p),...,X^((d-1)p)を入力
とし、(g(X))^pを計算し、g(X)に改めておく。
【００４１】多項式変換部4022では以下の計算を行う。
【００４２】(g(X))^p=g0+g1X^p+g2X^(2p)+...+g(d-1)X
^((d-1)p) ここで、g(X)=g0+g1X+g2X^2+...+g(d-1)X^(d-1)(g0、g
1、...、g(d-1)はGF(q)の元)であると仮定している。
^((d-1)p) ここで、g(X)=g0+g1X+g2X^2+...+g(d-1)X^(d-1)(g0、g
1、...、g(d-1)はGF(q)の元)であると仮定している。
【００４３】終了判定部4023は、c=nであるか否かを判
定する。
定する。
【００４４】以下に、第2冪乗計算部402の動作を示す。
【００４５】初期値計算部4021は、カウンタc=1,g(X)=X
^pに設定し、多項式変換部4022にg(X)と第1冪乗計算部4
01から出力されたX^p,X^(2p),...,X^((d-1)p)を入力す
る。多項式変換部4022は、(g(X))^pを計算し、g(X)に改
めておく。終了判定部で4023は、c=nであるか否かを判
定し、c=nであるときは、g(X)を出力し、終了。それ以
外は、cにc+1を改めておき、多項式変換部4022に戻る。
^pに設定し、多項式変換部4022にg(X)と第1冪乗計算部4
01から出力されたX^p,X^(2p),...,X^((d-1)p)を入力す
る。多項式変換部4022は、(g(X))^pを計算し、g(X)に改
めておく。終了判定部で4023は、c=nであるか否かを判
定し、c=nであるときは、g(X)を出力し、終了。それ以
外は、cにc+1を改めておき、多項式変換部4022に戻る。
【００４６】(第3冪乗計算部403の構成)図３は、第3冪
乗計算部403の構成を示すブロック図である。
乗計算部403の構成を示すブロック図である。
【００４７】第3冪乗計算部403は、Rに属するf(X)と第1
冪乗計算部401から出力されたX^p,X^(2p),...,X^((d-1)
p)を入力とし、f(X)^((q-1)/2)を計算する多項式演算装
置である。
冪乗計算部401から出力されたX^p,X^(2p),...,X^((d-1)
p)を入力とし、f(X)^((q-1)/2)を計算する多項式演算装
置である。
【００４８】第3冪乗計算部403は、中間計算部4031と、
初期値設定部4032と、多項式変換部4033と、多項式乗算
部4034と、終了判定部4035を備える。
初期値設定部4032と、多項式変換部4033と、多項式乗算
部4034と、終了判定部4035を備える。
【００４９】中間計算部4031は、f(X)^((p-1)/2)を計算
する。
する。
【００５０】初期値設定部4032は、c=1、g(X)=f(X)^((p
-1)/2)に設定する。
-1)/2)に設定する。
【００５１】多項式変換部4033は、多項式変換部4022と
同一である。
同一である。
【００５２】多項式乗算部4034は、g(X)とf(X)^((p-1)/
2)を乗算する。
2)を乗算する。
【００５３】終了判定部4035は、c=nであるか否かを判
定する。
定する。
【００５４】以下に、第3冪乗計算部403の動作を示す。
【００５５】中間計算部4031は、f(X)^((p-1)/2)を計算
し、出力する。初期値計算部4032は、カウンタc=1,g(X)
=f(X)^((p-1)/2)に設定し、多項式変換部4033にg(X)と
第1冪乗計算部401から出力されたX^p,X^(2p),...,X^((d
-1)p)を入力する。多項式変換部4033は、(g(X))^pを計
算し、g(X)に改めておく。多項式乗算部4034で、g(X)と
f(X)^((p-1)/2)を乗算し、g(X)に改めておく。終了判定
部4035は、c=nであるか否かを判定し、c=nであるとき
は、g(X)を出力し、終了。それ以外は、cにc+1を改めて
おき、多項式変換部4033に戻る。
し、出力する。初期値計算部4032は、カウンタc=1,g(X)
=f(X)^((p-1)/2)に設定し、多項式変換部4033にg(X)と
第1冪乗計算部401から出力されたX^p,X^(2p),...,X^((d
-1)p)を入力する。多項式変換部4033は、(g(X))^pを計
算し、g(X)に改めておく。多項式乗算部4034で、g(X)と
f(X)^((p-1)/2)を乗算し、g(X)に改めておく。終了判定
部4035は、c=nであるか否かを判定し、c=nであるとき
は、g(X)を出力し、終了。それ以外は、cにc+1を改めて
おき、多項式変換部4033に戻る。
【００５６】以下に、本多項式演算装置40の動作を示
す。
す。
【００５７】本装置が起動されると、まず、第1冪乗計
算部401はX^p、X^(2p)、X^(3p)、...、X^((d-1)p)を計
算し出力する。第2冪乗計算部402は、第1冪乗計算部401
から出力されたX^p、X^(2p)、X^(3p)、...、X^((d-1)p)
とXを入力とし、X^qを計算し出力する。次に第3冪乗計
算部403は、第1冪乗計算部401から出力されたX^p、X^(2
p)、X^(3p)、...、X^((d-1)p)とXを入力とし、f(X)^((q
-1)/2)を計算し、X^qとf(X)^((q-1)/2)を出力する。
算部401はX^p、X^(2p)、X^(3p)、...、X^((d-1)p)を計
算し出力する。第2冪乗計算部402は、第1冪乗計算部401
から出力されたX^p、X^(2p)、X^(3p)、...、X^((d-1)p)
とXを入力とし、X^qを計算し出力する。次に第3冪乗計
算部403は、第1冪乗計算部401から出力されたX^p、X^(2
p)、X^(3p)、...、X^((d-1)p)とXを入力とし、f(X)^((q
-1)/2)を計算し、X^qとf(X)^((q-1)/2)を出力する。
【００５８】この例の計算量について説明する。本実施
形態は従来例2のSEAアルゴリズムで用いられる。以下
で、従来の方法との比較を行う。
形態は従来例2のSEAアルゴリズムで用いられる。以下
で、従来の方法との比較を行う。
【００５９】多項式乗算の計算量をPMulとする。従来の
方法では、f(X)^((q-1)/2)を単に冪乗を行うことによ
り、求めていた。この場合、計算量は3/2|q|×PMulであ
る(|q|はqのビット数)。それに対して、本実施形態で
は、中間計算部4031の計算量が、3/2|p|×PMul(|p|はp
のビット数)であり、多項式変換部4033の計算量は1×PM
ul、多項式乗算部4034の計算量は1×PMulであり、多項
式変換部4043と多項式乗算部4044は、n-1回繰り返すの
で、全体の計算量は、(3/2|p|+2×n-2)×PMulである。|
q|=160、|p|=32、n=5の場合、従来の方法では、f(X)^
((q-1)/2)を求める計算量は、240×PMulであり、本実施
形態1では、56×PMulである。したがって、f(X)^((p-1)
/2)の計算が高速な多項式演算装置の効果は大きい。な
お、本実施形態を用いた位数計算装置、楕円曲線生成装
置並びに、楕円曲線暗号システムが実現可能となる
方法では、f(X)^((q-1)/2)を単に冪乗を行うことによ
り、求めていた。この場合、計算量は3/2|q|×PMulであ
る(|q|はqのビット数)。それに対して、本実施形態で
は、中間計算部4031の計算量が、3/2|p|×PMul(|p|はp
のビット数)であり、多項式変換部4033の計算量は1×PM
ul、多項式乗算部4034の計算量は1×PMulであり、多項
式変換部4043と多項式乗算部4044は、n-1回繰り返すの
で、全体の計算量は、(3/2|p|+2×n-2)×PMulである。|
q|=160、|p|=32、n=5の場合、従来の方法では、f(X)^
((q-1)/2)を求める計算量は、240×PMulであり、本実施
形態1では、56×PMulである。したがって、f(X)^((p-1)
/2)の計算が高速な多項式演算装置の効果は大きい。な
お、本実施形態を用いた位数計算装置、楕円曲線生成装
置並びに、楕円曲線暗号システムが実現可能となる
【００６０】
【発明の効果】以上に説明したように本発明は、従来例
における問題点を鑑みて行われたもので、SEAアルゴリ
ズムにおいては、多項式環上の冪乗演算の計算時間を短
縮できた。
における問題点を鑑みて行われたもので、SEAアルゴリ
ズムにおいては、多項式環上の冪乗演算の計算時間を短
縮できた。
【００６１】以上により、高速に安全な暗号方式や署名
方式を可能にする楕円曲線生成装置を提供することがで
き，その実用的価値は大きい。
方式を可能にする楕円曲線生成装置を提供することがで
き，その実用的価値は大きい。
【図１】本発明の実施形態における多項式演算装置のブ
ロック図
ロック図
【図２】本発明の実施形態における第2冪乗計算部402の
構成を示すブロック図
構成を示すブロック図
【図３】本発明の実施形態における第3冪乗計算部403の
構成を示すブロック図
構成を示すブロック図
【図４】従来例1の楕円曲線生成装置のブロック図
【図５】従来例2のSEAアルゴリズムによる楕円曲線位数
計算装置のブロック図
計算装置のブロック図
【図６】従来例3の多項式演算装置のブロック図
１０ 従来例1の楕円曲線生成装置 １０１ 乱数生成部 １０２ 楕円曲線設定部 １０３ 楕円曲線位数計算部 １０４ 楕円曲線条件判定部 ２０ 従来例2のSEAアルゴリズムによる楕円曲線位数計
算装置 ２０１ 初期値設定部 ２０２ 楕円曲線位数情報計算部 ２０３ 計算終了判定部 ２０４ 楕円曲線位数決定部 ３０ 従来例3の多項式演算装置 ３０１ 第1冪乗計算部 ３０２ 第2冪乗計算部 ４０ 本発明の実施形態1の多項式演算装置 ４０１ 第1冪乗計算部 ４０２ 第2冪乗計算部 ４０２１ 初期値設定部 ４０２２ 多項式変換部 ４０２３ 終了判定部 ４０３ 第3冪乗計算部 ４０３１ 中間計算部 ４０３２ 初期値設定部 ４０３３ 多項式変換部 ４０３４ 多項式乗算部 ４０３５ 終了判定部
算装置 ２０１ 初期値設定部 ２０２ 楕円曲線位数情報計算部 ２０３ 計算終了判定部 ２０４ 楕円曲線位数決定部 ３０ 従来例3の多項式演算装置 ３０１ 第1冪乗計算部 ３０２ 第2冪乗計算部 ４０ 本発明の実施形態1の多項式演算装置 ４０１ 第1冪乗計算部 ４０２ 第2冪乗計算部 ４０２１ 初期値設定部 ４０２２ 多項式変換部 ４０２３ 終了判定部 ４０３ 第3冪乗計算部 ４０３１ 中間計算部 ４０３２ 初期値設定部 ４０３３ 多項式変換部 ４０３４ 多項式乗算部 ４０３５ 終了判定部
Claims (8)
- 【請求項１】 予め与えられた有限体GF(p)の拡大体GF
(q)(q=p^n)上の予め与えられた多項式r(X)(次数d)を法
とする1変数多項式剰余環R=GF(q)[X]/(r(X))において、
Rに属する多項式X、f(X)を入力とし、 Rに属する多項式X^q、f(X)^((q-1)/2)を出力する多項式
演算装置であって、 前記多項式Xに対して、X^p、X^(2p)、X^(3p)、...、X^
((d-1)p)を計算する第1冪乗計算手段と、f(X)^((q-1)/
2)を計算する第2冪乗計算手段とを備え、 前記第2冪乗計算手段は、前記第1冪乗計算手段から出力
される結果を用いることを特徴とする多項式演算装置
(ただし、p^nはpのn乗を示す)。 - 【請求項２】 前記第2冪乗計算手段は、f(X)^((p-1)/
2)を計算する中間計算を行ってから、前記第1冪乗計算
手段から出力される結果を用いて、 f(X)^((p^2-1)/2)=(f(X)^((p-1)/2))^p×f(X)^((p-1)/2) f(X)^((p^3-1)/2)=(f(X)^((p^2-1)/2))^p×f(X)^((p-1)/2) .... f(X)^((p^n-1)/2)=(f(X)^((p^(n-1)-1)/2)^p×f(X)^((p-1)/2) により計算することを特徴とする請求項1記載の多項式
演算装置。 - 【請求項３】 予め与えられた有限体GF(p)の拡大体GF
(q)(q=p^n)上の楕円曲線を入力とし、前記楕円曲線の位
数を出力する楕円曲線位数計算装置であって、予め与え
られた初期値を設定する初期値設定部と、位数の情報を
求める楕円曲線位数情報計算部と、前記楕円曲線位数情
報計算部の終了判定を行う計算終了判定部と、前記楕円
曲線位数情報計算部から出力される情報を用いて楕円曲
線の位数を決定する楕円曲線位数決定部とを備え、 前記楕円曲線位数情報計算部は、請求項1に記載の多項
式演算装置を有することを特徴とする楕円曲線位数計算
装置。 - 【請求項４】 予め与えられた有限体GF(p)の拡大体GF
(q)(q=p^n)上の楕円曲線を入力とし、前記楕円曲線の位
数を出力する楕円曲線位数計算装置であって、予め与え
られた初期値を設定する初期値設定部と、位数の情報を
求める楕円曲線位数情報計算部と、前記楕円曲線位数情
報計算部の終了判定を行う計算終了判定部と、前記楕円
曲線位数情報計算部から出力される情報を用いて楕円曲
線の位数を決定する楕円曲線位数決定部とを備え、 前記楕円曲線位数情報計算部は、請求項2に記載の多項
式演算装置を有することを特徴とする楕円曲線位数計算
装置。 - 【請求項５】 予め与えられた有限体GF(p)の拡大体GF
(q)(q=p^n)上で定義され、予め与えられた条件を満たす
楕円曲線を出力する楕円曲線生成装置であって、予め与
えられた楕円曲線設定値に基づいて楕円曲線を設定する
楕円曲線設定部と、前記有限体上の楕円曲線の位数を計
算する楕円曲線位数計算部と、前記楕円曲線設定部で設
定した楕円曲線を、前記与えられた条件で判定する楕円
曲線条件判定部とを備え、 前記楕円曲線位数計算部は、請求項3に記載の楕円曲線
位数計算装置を有することを特徴とする楕円曲線生成装
置。 - 【請求項６】 予め与えられた有限体GF(p)の拡大体GF
(q)(q=p^n)上で定義され、予め与えられた条件を満たす
楕円曲線を出力する楕円曲線生成装置であって、予め与
えられた楕円曲線設定値に基づいて、楕円曲線を設定す
る楕円曲線設定部と、前記有限体上の楕円曲線の位数を
計算する楕円曲線位数計算部と、前記楕円曲線設定部で
設定した楕円曲線を、前記与えられた条件で判定する楕
円曲線条件判定部とを備え、 前記楕円曲線位数計算部は、請求項4に記載の楕円曲線
位数計算装置を有することを特徴とする楕円曲線生成装
置。 - 【請求項７】 予め与えられた有限体GF(p)の拡大体GF
(q)(q=p^n)上で定義され、予め与えられた条件を満たす
楕円曲線を用いる楕円曲線暗号システムであって、予め
与えられた楕円曲線設定値に基づいて、楕円曲線を設定
する楕円曲線設定部と、前記有限体上の楕円曲線の位数
を計算する楕円曲線位数計算部と、前記楕円曲線設定部
で設定した楕円曲線を、前記与えられた条件で判定する
楕円曲線条件判定部とを備え、 前記楕円曲線位数計算部は、請求項3に記載の楕円曲線
位数計算装置を有する楕円曲線生成装置により生成され
ることを特徴とする楕円曲線暗号システム。 - 【請求項８】 予め与えられた有限体GF(p)の拡大体GF
(q)(q=p^n)上で定義され、予め与えられた条件を満たす
楕円曲線を用いる楕円曲線暗号システムであって、予め
与えられた楕円曲線設定値に基づいて、楕円曲線を設定
する楕円曲線設定部と、前記有限体上の楕円曲線の位数
を計算する楕円曲線位数計算部と、前記楕円曲線設定部
で設定した楕円曲線を、前記与えられた条件で判定する
楕円曲線条件判定部とを備え、 前記楕円曲線位数計算部は、請求項4に記載の楕円曲線
位数計算装置を有する楕円曲線生成装置により生成され
ることを特徴とする楕円曲線暗号システム。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP11133814A JP2000321979A (ja) | 1999-05-14 | 1999-05-14 | 多項式演算装置、楕円曲線位数計算装置、楕円曲線生成装置及び楕円曲線暗号システム |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP11133814A JP2000321979A (ja) | 1999-05-14 | 1999-05-14 | 多項式演算装置、楕円曲線位数計算装置、楕円曲線生成装置及び楕円曲線暗号システム |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2000321979A true JP2000321979A (ja) | 2000-11-24 |
Family
ID=15113672
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP11133814A Pending JP2000321979A (ja) | 1999-05-14 | 1999-05-14 | 多項式演算装置、楕円曲線位数計算装置、楕円曲線生成装置及び楕円曲線暗号システム |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2000321979A (ja) |
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2004533671A (ja) * | 2001-02-21 | 2004-11-04 | ミップス テクノロジーズ インコーポレイテッド | 多項式演算オペレーション |
| JP2005141198A (ja) * | 2003-10-14 | 2005-06-02 | Matsushita Electric Ind Co Ltd | データ変換装置およびその方法 |
| US7599981B2 (en) | 2001-02-21 | 2009-10-06 | Mips Technologies, Inc. | Binary polynomial multiplier |
| US7617388B2 (en) | 2001-02-21 | 2009-11-10 | Mips Technologies, Inc. | Virtual instruction expansion using parameter selector defining logic operation on parameters for template opcode substitution |
| US7860911B2 (en) | 2001-02-21 | 2010-12-28 | Mips Technologies, Inc. | Extended precision accumulator |
| KR101103443B1 (ko) | 2003-10-14 | 2012-01-09 | 파나소닉 주식회사 | 데이터 컨버터 |
-
1999
- 1999-05-14 JP JP11133814A patent/JP2000321979A/ja active Pending
Cited By (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2004533671A (ja) * | 2001-02-21 | 2004-11-04 | ミップス テクノロジーズ インコーポレイテッド | 多項式演算オペレーション |
| US7599981B2 (en) | 2001-02-21 | 2009-10-06 | Mips Technologies, Inc. | Binary polynomial multiplier |
| US7617388B2 (en) | 2001-02-21 | 2009-11-10 | Mips Technologies, Inc. | Virtual instruction expansion using parameter selector defining logic operation on parameters for template opcode substitution |
| JP2009282992A (ja) * | 2001-02-21 | 2009-12-03 | Mips Technologies Inc | 多項式演算オペレーション |
| US7711763B2 (en) | 2001-02-21 | 2010-05-04 | Mips Technologies, Inc. | Microprocessor instructions for performing polynomial arithmetic operations |
| US7860911B2 (en) | 2001-02-21 | 2010-12-28 | Mips Technologies, Inc. | Extended precision accumulator |
| US8447958B2 (en) | 2001-02-21 | 2013-05-21 | Bridge Crossing, Llc | Substituting portion of template instruction parameter with selected virtual instruction parameter |
| JP2005141198A (ja) * | 2003-10-14 | 2005-06-02 | Matsushita Electric Ind Co Ltd | データ変換装置およびその方法 |
| KR101103443B1 (ko) | 2003-10-14 | 2012-01-09 | 파나소닉 주식회사 | 데이터 컨버터 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7412062B2 (en) | Method and apparatus for elliptic curve scalar multiplication | |
| Gordon | A survey of fast exponentiation methods | |
| US6611597B1 (en) | Method and device for constructing elliptic curves | |
| US6266688B1 (en) | Scheme for arithmetic operations in finite field and group operations over elliptic curves realizing improved computational speed | |
| EP3276880A1 (en) | Efficient ecdsa signature and verification | |
| Boruah et al. | Implementation of ElGamal Elliptic Curve Cryptography over prime field using C | |
| EP0952697B1 (en) | Elliptic curve encryption method and system | |
| Granger et al. | On the discrete logarithm problem on algebraic tori | |
| Asbullah et al. | Analysis on the Rabin-p cryptosystem | |
| JP4354609B2 (ja) | 有限体上の連立方程式求解装置及び逆元演算装置 | |
| JP2000321979A (ja) | 多項式演算装置、楕円曲線位数計算装置、楕円曲線生成装置及び楕円曲線暗号システム | |
| Mohamed et al. | Improved fixed-base comb method for fast scalar multiplication | |
| KR101548174B1 (ko) | 모듈러스의 음의 역원을 구하는 방법 | |
| Knežević et al. | Speeding up bipartite modular multiplication | |
| KR101223498B1 (ko) | 타원 곡선 암호 방식에서 공개키를 생성하는 방법 및 상기방법을 수행하는 시스템 | |
| Rotaru et al. | A complete generalization of Atkin's square root algorithm | |
| JP3540852B2 (ja) | 暗号化システムにおける羃乗演算を含む暗号化方法及びその装置 | |
| Mohammadi et al. | Comparison of two Public Key Cryptosystems | |
| Wu et al. | Elliptic curve point multiplication by generalized Mersenne numbers | |
| JP3626315B2 (ja) | 剰余算装置、情報処理装置及び剰余算方法 | |
| RU2541938C1 (ru) | Способ шифрования с защитой от квантовых атак на основе циклов функций вебера | |
| JP4479135B2 (ja) | 演算装置及び演算方法及び演算プログラム | |
| Botes et al. | An implementation of an elliptic curve cryptosystem | |
| JPH0643809A (ja) | 楕円曲線に基づくデイジタル署名方式とその署名者装置及び検証者装置 | |
| Sanghi | New Digital Signature Scheme Based on MDLP and Multinacci Matrices |