(57)【要約】【課題】  逐次拡大に適した基底を得るための生成多項式を生成する。【解決手段】  生成多項式候補を生成する手順と、生成多項式候補ｆ（ｘ）の１つを選択する選択手順と、選択された候補ｆ（ｘ）が、既約であるか検査する検査手順とを行い、その検査手順が既約であると判定すると、生成多項式として上記選択された候補ｆ（ｘ）を出力し、既約でないと判定すると上記選択手順と上記検査手順とを繰返す。これにより、逐次拡大に適した基底を得るための生成多項式が生成できる。【選択図】        図２
2004355031.tif 000002
【特許請求の範囲】
【請求項１】
有限体ＧＦ（ｑi）（ｑiは素数又は素数のべき乗である）からＧＦ（ｑi+1）へのｍ次拡大を行うために用いる生成多項式を生成する装置であって、
生成多項式候補を生成する手段と、
生成多項式候補ｆ（ｘ）の１つを選択する選択手段と、
選択された候補ｆ（ｘ）が、既約であるか検査する検査手段と、
その検査手段が既約であると判定すると、生成多項式として上記選択された候補ｆ（ｘ）を出力する手段と、
上記検査手段が既約でないと判定すると上記選択手段と上記検査手段とを繰返させる手段とを備えることを特徴とする
多項式基底の生成多項式生成装置。
【請求項２】
請求項１記載の生成多項式生成装置において、
ＧＦ（ｑi）からＧＦ（ｑi+1）への２次拡大に用いられ、
上記生成多項式候補を生成する手段はｖ1が−１（ただし、ｖ0，ｖ1はＧＦ（ｑi）の元）であるｘ2＋ｖ1ｘ＋ｖ0なる生成多項式候補を生成する手段であることを特徴とする多項式基底の生成多項式生成装置。
【請求項３】
請求項１記載の生成多項式生成装置において、
ＧＦ（ｑi）からＧＦ（ｑi+1）への２次拡大に用いられ、
上記生成多項式候補を生成する手段はｖ1が０（ただし、ｖ0，ｖ1はＧＦ（ｑi）の元）であるｘ2＋ｖ1ｘ＋ｖ0なる生成多項式候補を生成する手段であることを特徴とする多項式基底の生成多項式生成装置。
【請求項４】
請求項３記載の生成多項式生成装置において、
上記生成多項式候補を生成する手段はｖ0がｕ2（ただし、ｕはＧＦ（ｑi）の元）と表すことが出来る生成多項式候補を生成する手段であることを特徴とする多項式基底の生成多項式生成装置。
【請求項５】
請求項１から４の何れかに記載の生成多項式生成装置としてコンピュータを機能させるためのプログラム。
【請求項６】
請求項１から４の何れかに記載の生成多項式生成装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば、情報セキュリティ技術（楕円曲線暗号／署名、素因数分解）を実現するために用いられる楕円曲線上の演算装置に関する。
【背景技術】
【０００２】
楕円曲線上で公開鍵暗号やデジタル署名を実現する場合、その処理時間のほとんどは楕円曲線上のｋ倍演算に費やされる。
一般に、暗号や署名には有限体ＧＦ（ｑ）上で定義される楕円曲線を使う。これをＥ／ＧＦ（ｑ）と表記する。ｑは素数または素数のべき乗である。従来の実装法ではｑに素数または２m を用いることが多かったが、この発明は一般の有限体の場合を考える。
楕円曲線上の点Ｐに対する加算を定義できる。通常の加算と区別するためにこれを、「楕円加算」「楕円２倍演算」と呼ぶ。いずれも、有限体ＧＦ（ｑ）上の加減乗除算を組み合わせることで行うことが出来る。
【０００３】
通常、ｋ倍演算を構成するために、「楕円加算」「楕円２倍演算」を組み合わせて行なう方法が用いられている。
したがって、楕円曲線上の演算は、有限体ＧＦ（ｑ）上の加減乗除算に帰着することが出来、これらを高速化することが、楕円曲線上の演算の高速化につながる。
楕円曲線演算を、ＧＦ（ｑn）上の有理式の列Ｒ（ｘ0，ｘ1，…）及びｘ0，ｘ1 ，…の値をＧＦ（ｑn）演算器に入力し、ＧＦ（ｑn-1）上の演算列とデータに帰着させるＧＦ（ｑn-1）演算器へ渡し、ＧＦ（ｑn-1）演算器は入力をＧＦ（ｑn-2）上の演算の列とデータに帰着させてＧＦ（ｑn-2）演算器に渡し、以下同様のことを繰返して、ＧＦ（ｑ0）演算器で計算した結果を出力するように、つまり逐次拡大させることにより、従来の楕円曲線演算より、乗算回数を減少することができることを特願平１１−２３０１２３号「逐次拡大を用いた楕円曲線演算装置及びプログラム記録媒体」で提案した。
【０００４】
この場合のＧＦ（ｑn-1）のｍ次拡大体ＧＦ（ｑn）＝ＧＦ（ｑn-1m）上のＧＦ（ｑn-1）演算器における自乗器として、入力Ａ＝（Ａ0，Ａ1）、出力Ａ2 ＝（Ｃ0 ，Ｃ1）を正規基底によるＧＦ（ｑn）＝ＧＦ（ｑn-1m）上の元のＧＦ（ｑn-1）上の元により表現し、基底をαおよびβ（ただしα＋β＝−ｖ1）とするとＡ＝Ａ0α＋Ａ1β，Ａ2＝Ｃ0α＋Ｃ1βを意味し、全ての基底を解にもつＧＦ（ｑn-1）上ｍ次既約多項式をｆ（ｘ）＝ｘ2＋ｖ1ｘ＋ｖ0とし、
Ａ2＝（−Ａ02ｖ1＋（Ａ0−Ａ1）2（ｖ0／ｖ1））α
＋（−Ａ12ｖ1＋（Ａ0−Ａ1）2（ｖ0／ｖ1））β
の演算を行うことが提案されている。つまり図９に示すようにＧＦ（ｑn-1）自乗器２７ＢでＡ02→Ｌ0を演算し、ＧＦ（ｑn-1）減算器２７ＣでＡ0−Ａ1→Ｌ1を演算し、ＧＦ（ｑn-1）自乗器２７ＤでＡ12→Ｌ2を演算し、ＧＦ（ｑn-1）自乗器２７ＥでＬ12→Ｌ3を演算し、ＧＦ（ｑn-1）定数倍器２７Ｆで−ｖ1Ｌ0→Ｌ4を演算し、ＧＦ（ｑn-1）定数倍器２７Ｇで（−ｖ1）-1（−ｖ0）Ｌ3→Ｌ5を演算し、ＧＦ（ｑn-1）定数倍器２７Ｈで−ｖ1Ｌ2 →Ｌ6 を演算し、ＧＦ（ｑn-1）加算器２７ＩでＬ4＋Ｌ5→Ｃ0を演算し、ＧＦ（ｑn-1）加算器２７ＪでＬ5＋Ｌ6→Ｃ1を演算してＡ2＝（Ｃ0，Ｃ1）を得る。
【０００５】
このようにすれば３回の自乗演算と３回の倍数演算で済む。
また前記逐次拡大を用いた楕円曲線演算ではＧＦ（ｑn-1）のｍ次拡大ＧＦ（ｑn）＝ＧＦ（ｑn-1m）を多項式基底を用いて行うが、その多項式基底に用いる生成多項式は既約でなければならない。また正規基底の場合は逐次的に拡大する時に、拡大ごとに高速演算に適した正規基底の生成元が定義されることによって、全ての基底を解に持つ既約多項式を定義して既約多項式の列を作る。従って、既約多項式を作る際、この解が正規基底になるものでなくてはならない。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
この発明の目的は逐次拡大を用いた楕円曲線演算装置において、逐次拡大に適した基底を得るための生成多項式を生成する装置を提供することにある。
【課題を解決するための手段】
【０００７】
生成多項式候補を生成する手順と、生成多項式候補ｆ（ｘ）の１つを選択する選択手順と、選択された候補ｆ（ｘ）が、既約であるか検査する検査手順とを行い、その検査手順が既約であると判定すると、生成多項式として上記選択された候補ｆ（ｘ）を出力し、既約でないと判定すると上記選択手順と上記検査手順とを繰返す。
【発明の効果】
【０００８】
逐次拡大楕円曲線演算においてその拡大に利用する多項式基底の生成多項式を生成することができる。
【発明を実施するための最良の形態】
【０００９】
自乗器（正規基底）
この装置はＧＦ（ｑn-1）のｍ次拡大ＧＦ（ｑn）＝ＧＦ（ｑn-1m）上の自乗器のＧＦ（ｑn-1）上演算装置による一構成例である。
この構成例はｍ＝２であり、全ての基底を解にもつＧＦ（ｑn-1）上ｍ次生成多項式をｆ（ｘ）＝ｘ2＋ｖ1ｘ＋ｖ0とした場合にｖ0＝ｕ2なるｕ∈ＧＦ（ｑn-1）が存在する場合の装置である。
【００１０】
この説明および、図１においてＡ＝（Ａ0，Ａ1）およびＡ2 ＝（Ｃ0，Ｃ1）は正規基底によるＧＦ（ｑn）＝ＧＦ（ｑn-1m）上の元のＧＦ（ｑn-1）上の元による表現であり、基底をαおよびβとするとそれぞれＡ＝Ａ0α＋Ａ1βおよびＡ2 ＝Ｃ0α＋Ｃ1βを意味している。
図に示す装置１００はＧＦ（ｑn）＝ＧＦ（ｑn-1m）上の元Ａ＝（Ａ0，Ａ1）の入力に対してＧＦ（ｑn）上の元Ａ2を出力する装置の構成の一例を表している。
【００１１】
この装置の動作をプログラムで実現する場合は、図５に示すフローに従って実行する。
このＧＦ（ｑn）自乗算器１００はＧＦ（ｑn-1）定数倍器と、ＧＦ（ｑn-1）加算器と、ＧＦ（ｑn-1）減算器と、ＧＦ（ｑn-1）乗算器とこれらを制御する制御器１１１と、メモリ１１２とで構成される。
ＧＦ（ｑn-1）減算器１０１はＡ0とＡ1を入力とし、ＧＦ（ｑn-1）定数倍器１０２は減算器１０１の出力Ｌ1を入力とし、ＧＦ（ｑn-1）加算器１０３はＡ0と定数倍器１０２の出力Ｌ5を入力し、ＧＦ（ｑn-1）減算器１０４はＡ0とＬ5 を入力とし、ＧＦ（ｑn-1）加算器１０５はＬ5 とＡ1 を入力とし、ＧＦ（ｑn-1）減算器１０６はＬ5とＡ1を入力とし、ＧＦ（ｑn-1）乗算器１０７は加算器１０３の出力と減算器１０４の出力を入力とし、ＧＦ（ｑn-1）定数倍器１０８は乗算器１０７を入力とし、ＧＦ（ｑn-1）乗算器１０９は加算器１０５の出力と減算器１０６の出力とを入力とし、ＧＦ（ｑn-1）定数倍器１１０は乗算器１０９の出力を入力とする。
【００１２】
この自乗器１００は以下のように動作する。
入力値Ａ＝（Ａ0，Ａ1）を入力し、メモリ１１２に一時格納され、以下において特に述べないが演算に必要なデータはメモリ１１２から読出され、演算結果はメモリ１１２に記憶される。
Ｓｔｅｐ１：ＧＦ（ｑn-1）減算器１０１は入力のＡ0 およびＡ1 に対して
Ｌ1 ←Ａ0−Ａ1 を計算してＬ1 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1）定数倍器１０２は入力のＬ1 に対して
Ｌ5 ←（ｕ／ｖ1）Ｌ1 を計算してＬ5 を出力する。
【００１３】
Ｓｔｅｐ３：ＧＦ（ｑn-1）加算器１０３は入力のＬ5，Ａ0に対して
Ｌ5 ＋Ａ0 を計算して出力する。
Ｓｔｅｐ４：ＧＦ（ｑn-1）減算器１０４は入力のＬ5，Ａ0に対して
Ｌ5−Ａ0を計算して出力する。
Ｓｔｅｐ５：ＧＦ（ｑn-1）加算器１０５は入力のＬ5，Ａ1に対して
Ｌ5 ＋Ａ1 を計算して出力する。
Ｓｔｅｐ６：ＧＦ（ｑn-1）減算器１０６は入力のＬ5，Ａ1に対して
Ｌ5 −Ａ1 を計算して出力する。
【００１４】
Ｓｔｅｐ７：ＧＦ（ｑn-1）乗算器１０７は入力の（Ｌ5＋Ａ0），（Ｌ5 −Ａ0）に対して
Ｔ0←（Ｌ5＋Ａ0）（Ｌ5−Ａ0）を計算して出力する。
Ｓｔｅｐ８：ＧＦ（ｑn-1）定数倍器１０８は入力の（Ｌ5＋Ａ0）（Ｌ5−Ａ0）に対して
−ｖ1（Ｌ5＋Ａ0）（Ｌ5−Ａ0）を計算してＣ0 として出力する。
Ｓｔｅｐ９：ＧＦ（ｑn-1）乗算器１０９は入力の（Ｌ5＋Ａ1），（Ｌ5−Ａ1）に対して
Ｔ1←（Ｌ5＋Ａ1）（Ｌ5−Ａ1）を計算して出力する。
Ｓｔｅｐ１０：ＧＦ（ｑn-1）定数倍器１１０は入力の（Ｌ5＋Ａ1）（Ｌ5−Ａ1）に対して
−ｖ1（Ｌ5 ＋Ａ1）（Ｌ5 −Ａ1）を計算してＣ1 として出力する。
Ｓｔｅｐ１１：（Ｃ0，Ｃ1）をＡ2として出力する。
【００１５】
生成多項式生成装置
図２に示す生成多項式生成装置はＧＦ（ｑn-1）のｍ次拡大ＧＦ（ｑn）＝ＧＦ（ｑn-1m) を多項式基底を用いて行なうのに用いる生成多項式を求める装置の一構成例である。この装置２００は制御装置２０１にメモリ２０２と既約性判定装置２０３とが接続されて構成される。
【００１６】
この装置の動作をプログラムで実現する場合は、図６に示すフローに従って実行する。
Ｓｔｅｐ０：制御装置２０１は入力有限体ＧＦ（ｑn-1）と拡大次数ｍを入力する。またｊ個の生成多項式候補ｆi（ｘ），（ｉ＝１，…，ｊ）を生成する。ｉを０に初期化する。
ｉ＝ｊかを調べｉがｊでなければ
Ｓｔｅｐ１：ｉを＋１して入力された有限体ＧＦ（ｑn-1）上の生成多項式候補ｆi（ｘ）を選ぶ。
Ｓｔｅｐ２：既約性判定装置２０３を用いてそのｆi（ｘ）が既約であるか検査する。
Ｓｔｅｐ３：既約であれば、生成多項式ｇ（ｘ）としてｆi（ｘ）を出力。既約でなければＳｔｅｐ１へもどってやりなおし。
既約性判定装置２０３の構成は後で述べる。
【００１７】
また、この装置の構成としては、以下のような構成、およびその組合せによる構成をすることもできる。
ｆ（ｘ）が２次多項式ｘ2＋ｖ1ｘ＋ｖ0の場合に多項式基底を用いた乗算を高速に行なうことを目的として、Ｓｔｅｐ０においてｖ1＝−１となる候補ｆi（ｘ）を生成する。
【００１８】
ｆ（ｘ）が２次多項式ｘ2＋ｖ1ｘ＋ｖ0の場合に多項式基底を用いた逆元や自乗を高速に行なうことを目的として、Ｓｔｅｐ０においてｖ1＝０となる候補ｆi（ｘ）を生成する。
ｆ（ｘ）が２次多項式ｘ2＋ｖ1ｘ＋ｖ0の場合に多項式基底を用いた自乗を高速に行なうことを目的として、Ｓｔｅｐ０においてｖ1＝０，ｖ0＝ｕ2とあらわすことができる候補ｆi（ｘ）を生成する。
【００１９】
正規多項式生成装置
図３に示す正規多項式生成装置はＧＦ（ｑn-1）のｍ次拡大ＧＦ（ｑn）＝ＧＦ（ｑn-1m）を正規基底を用いて行なうのに用いる正規多項式を求める装置の一構成例である。この装置３００は制御装置３０１にメモリ３０２、既約性判定装置３０３、正則判定装置３０４が接続されて構成される。
【００２０】
この装置の動作をプログラムで実現する場合は、図７に示すフローに従って実行する。
Ｓｔｅｐ０：有限体ＧＦ（ｑn-1）、拡大次数ｍを入力する。生成多項式候補ｆi（ｘ），（ｉ＝１，…，ｊ）を生成し、ｉを０に初期化した後、ｉ＝ｊかを判定し、ｉがｊでなければ、
Ｓｔｅｐ１：ｉを＋１して入力された有限体ＧＦ（ｑn-1）上の生成多項式候補ｆi（ｘ）を選ぶ。
Ｓｔｅｐ２：既約性判定装置３０３を用いてｆi（ｘ）が既約であるか検査する。
【００２１】
Ｓｔｅｐ３：既約でなければＳｔｅｐ１へもどってやりなおし。
Ｓｔｅｐ４：既約であれば正則判定装置３０４を用いてｆi（ｘ）が正則であるか検査する。（この検査の方法は、例えば「暗号・ゼロ知識証明・数論」岡本龍明・太田和夫著、共立出版ｐｐ．１６７などに述べられている）
Ｓｔｅｐ５：正則でなければＳｔｅｐ１へもどってやりなおし。正則であれば、生成多項式ｆ（ｘ）としてｆi（ｘ）を出力。
また、この装置の構成としては、以下のような構成をすることもできる。
ｆ（ｘ）が２次多項式ｘ2＋ｖ1ｘ＋ｖ0の場合に多項式基底を用いた自乗を高速に行なうことを目的として、Ｓｔｅｐ０においてｖ0＝ｕ2と表わすことができるｆ（ｘ）を生成する。
【００２２】
既約性判定装置
図４に示す既約性判定装置は図２，３に示した装置における、既約性判定装置２０３，３０３の一構成例である。この装置４００は制御装置４０１と多項式ユークリッド（Ｅｕｃｌｉｄ）互除装置４０２とよりなる。
【００２３】
この装置の動作をプログラムで実現する場合は、図８に示すフローに従って実行する。
定義体ＧＦ（ｑn-1）と候補ｆ（ｘ）、拡大次数ｍを入力する。
ｇ（ｘ）＝（ｘ＾ｑn-1m-1）−ｘを作る。ここでＡ＾ＢはＡBを表わす。次に多項式Ｅｕｃｌｉｄ互除法を用いて、入力された多項式ｆ（ｘ）とｇ（ｘ）＝（ｘ＾ｑn-1m-1）−ｘとの最大公約多項式を求め、
その最大公約多項式が０次式ならば、「既約」を、１次以上ならば「可約」を出力する。
【００２４】
上述において各装置をコンピュータによりプログラムを解読実行させて機能させることもできる。この場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００２５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００２６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
また、以上の処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図面の簡単な説明】
【００２７】
【図１】この発明のＧＦ（ｑn）自乗器の実施例を示すブロック図。
【図２】この発明の多項式基底の生成多項式生成装置を示すブロック図。
【図３】この発明の正規多項式生成装置を示すブロック図。
【図４】図２、図３に用いた既約性判定装置の構成を示すブロック図。
【図５】図１に示した実施例におけるＧＦ（ｑn）自乗処理手順を示す流れ図。
【図６】図２に示した実施例における多項式基底の生成多項式生成処理手順を示す流れ図。
【図７】図３に示した実施例における正規多項式生成処理手順を示す流れ図。
【図８】図４に示した装置の既約性判定処理手順を示す流れ図。
【図９】先に提案したＧＦ（ｑn）自乗器の機能構成を示す図。
【図１】
2004355031.tif 000003
【図２】
2004355031.tif 000004
【図３】
2004355031.tif 000005
【図４】
2004355031.tif 000006
【図５】
2004355031.tif 000007
【図６】
2004355031.tif 000008
【図７】
2004355031.tif 000009
【図８】
2004355031.tif 000010
【図９】
2004355031.tif 000011