JP3638493B2 - 楕円曲線自乗演算装置、およびこのプログラム記録媒体 - Google Patents
楕円曲線自乗演算装置、およびこのプログラム記録媒体 Download PDFInfo
- Publication number
- JP3638493B2 JP3638493B2 JP2000016019A JP2000016019A JP3638493B2 JP 3638493 B2 JP3638493 B2 JP 3638493B2 JP 2000016019 A JP2000016019 A JP 2000016019A JP 2000016019 A JP2000016019 A JP 2000016019A JP 3638493 B2 JP3638493 B2 JP 3638493B2
- Authority
- JP
- Japan
- Prior art keywords
- outputting
- result
- outputs
- polynomial
- elliptic curve
- 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.)
- Expired - Lifetime
Links
Images
Landscapes
- Complex Calculations (AREA)
Description
【０００１】
【発明の属する技術分野】
この発明は、例えば、情報セキュリティ技術（楕円曲線暗号／署名、素因数分解）を実現するために用いられる楕円曲線上の演算装置に関する。
【０００２】
【従来の技術】
楕円曲線上で公開鍵暗号やデジタル署名を実現する場合、その処理時間のほとんどは楕円曲線上のｋ倍演算に費やされる。
一般に、暗号や署名には有限体ＧＦ（ｑ）上で定義される楕円曲線を使う。これをＥ／ＧＦ（ｑ）と表記する。ｑは素数または素数のべき乗である。従来の実装法ではｑに素数または２m を用いることが多かったが、この発明は一般の有限体の場合を考える。
【０００３】
楕円曲線上の点Ｐに対する加算を定義できる。通常の加算と区別するためにこれを、「楕円加算」「楕円２倍演算」と呼ぶ。いずれも、有限体ＧＦ（ｑ）上の加減乗除算を組み合わせることで行うことが出来る。
通常、ｋ倍演算を構成するために、「楕円加算」「楕円２倍演算」を組み合わせて行なう方法が用いられている。
したがって、楕円曲線上の演算は、有限体ＧＦ（ｑ）上の加減乗除算に帰着することが出来、これらを高速化することが、楕円曲線上の演算の高速化につながる。
【０００４】
楕円曲線演算を、ＧＦ（ｑn）上の有理式の列Ｒ（ｘ0，ｘ1，…）及びｘ0，ｘ1 ，…の値をＧＦ（ｑn）演算器に入力し、ＧＦ（ｑn-1）上の演算列とデータに帰着させるＧＦ（ｑn-1）演算器へ渡し、ＧＦ（ｑn-1）演算器は入力をＧＦ（ｑn-2）上の演算の列とデータに帰着させてＧＦ（ｑn-2）演算器に渡し、以下同様のことを繰返して、ＧＦ（ｑ0）演算器で計算した結果を出力するように、つまり逐次拡大させることにより、従来の楕円曲線演算より、乗算回数を減少することができることを特願平１１−２３０１２３号「逐次拡大を用いた楕円曲線演算装置及びプログラム記録媒体」で提案した。
【０００５】
この場合のＧＦ（ｑn-1）のｍ次拡大体ＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上のＧＦ（ｑn-1）演算器における自乗器として、入力Ａ＝（Ａ0，Ａ1）、出力Ａ2 ＝（Ｃ0 ，Ｃ1）を正規基底によるＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上の元のＧＦ（ｑn-1）上の元により表現し、基底をαおよびβ（ただしα＋β＝−ｖ1）とするとＡ＝Ａ0α＋Ａ1β，Ａ2＝Ｃ0α＋Ｃ1βを意味し、全ての基底を解にもつＧＦ（ｑn-1）上ｍ次既約多項式をｆ（ｘ）＝ｘ2＋ｖ1ｘ＋ｖ0とし、
Ａ2＝（−Ａ0 2ｖ1＋（Ａ0−Ａ1）2（ｖ0／ｖ1））α＋（−Ａ1 2ｖ1＋（Ａ0−Ａ1）2（ｖ0／ｖ1））β
の演算を行うことが提案されている。つまり図９に示すようにＧＦ（ｑn-1）自乗器２７ＢでＡ0 2→Ｌ0を演算し、ＧＦ（ｑn-1）減算器２７ＣでＡ0−Ａ1→Ｌ1を演算し、ＧＦ（ｑn-1）自乗器２７ＤでＡ1 2→Ｌ2を演算し、ＧＦ（ｑn-1）自乗器２７ＥでＬ1 2→Ｌ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-1 m）を多項式基底を用いて行うが、その多項式基底に用いる生成多項式は既約でなければならない。また正規基底の場合は逐次的に拡大する時に、拡大ごとに高速演算に適した正規基底の生成元が定義されることによって、全ての基底を解に持つ既約多項式を定義して既約多項式の列を作る。従って、既約多項式を作る際、この解が正規基底になるものでなくてはならない。
【０００７】
【発明が解決しようとする課題】
この発明の１目的はＧＦ（ｑn-1）のｍ次拡大体ＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上の自乗器のＧＦ（ｑn-1）演算器の乗算回数を更に減らし、より高速な演算を行うことができる楕円曲線自乗演算装置を提供することにある。
この発明の他の目的は逐次拡大を用いた楕円曲線演算装置において、逐次拡大に適した基底を得るための生成多項式を生成する装置を提供することにある。
【０００８】
【課題を解決するための手段】
この発明の楕円曲線自乗演算装置においては全ての基底を解にもつＧＦ（ｑn-1）上ｍ次既約多項式をｆ（ｘ）＝ｘ2＋ｖ1ｘ＋ｖ0とし、特にｖ0＝ｕ2，ｕ∈ＧＦ（ｑi-1）と表わせるものを用い、
を演算する装置である。
【０００９】
またこの発明による生成多項式生成装置は、生成多項式の候補を選び、その生成多項式候補が既約であるか検査し、既約でなければ次の生成多項式候補を選び同様のことを行い、既約であれば、これを用い、ＧＦ（ｑi）からＧＦ（ｑi+1）への拡大ごとに同様にして生成多項式を生成する。
【００１０】
【発明の実施の形態】
自乗器（正規基底）
この装置はＧＦ（ｑn-1）のｍ次拡大ＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上の自乗器のＧＦ（ｑn-1）上演算装置による一構成例である。
この構成例はｍ＝２であり、全ての基底を解にもつＧＦ（ｑn-1）上ｍ次生成多項式をｆ（ｘ）＝ｘ2＋ｖ1ｘ＋ｖ0とした場合にｖ0＝ｕ2なるｕ∈ＧＦ（ｑn-1）が存在する場合の装置である。
【００１１】
この説明および、図１においてＡ＝（Ａ0，Ａ1）およびＡ2 ＝（Ｃ0，Ｃ1）は正規基底によるＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上の元のＧＦ（ｑn-1）上の元による表現であり、基底をαおよびβとするとそれぞれＡ＝Ａ0α＋Ａ1βおよびＡ2 ＝Ｃ0α＋Ｃ1βを意味している。
図に示す装置１００はＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上の元Ａ＝（Ａ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-1 m) を多項式基底を用いて行なうのに用いる生成多項式を求める装置の一構成例である。この装置２００は制御装置２０１にメモリ２０２と既約性判定装置２０３とが接続されて構成される。
【００１８】
この装置の動作をプログラムで実現する場合は、図６に示すフローに従って実行する。
Ｓｔｅｐ０：制御装置２０１は入力有限体ＧＦ（ｑ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-1 m）を正規基底を用いて行なうのに用いる正規多項式を求める装置の一構成例である。この装置３００は制御装置３０１にメモリ３０２、既約性判定装置３０３、正則判定装置３０４が接続されて構成される。
【００２２】
この装置の動作をプログラムで実現する場合は、図７に示すフローに従って実行する。
Ｓｔｅｐ０：有限体ＧＦ（ｑn-1）、拡大次数ｍを入力する。生成多項式候補ｆi（ｘ），（ｉ＝１，…，ｊ）を生成し、ｉを０に初期化した後、ｉ＝ｊかを判定し、ｉがｊでなければ、
Ｓｔｅｐ１：ｉを＋１して入力された有限体ＧＦ（ｑn-1）上の生成多項式候補ｆi（ｘ）を選ぶ。
【００２３】
Ｓｔｅｐ２：既約性判定装置３０３を用いてｆi（ｘ）が既約であるか検査する。
Ｓｔｅｐ３：既約でなければＳｔｅｐ１へもどってやりなおし。
Ｓｔｅｐ４：既約であれば正則判定装置３０４を用いてｆi（ｘ）が正則であるか検査する。（この検査の方法は、例えば「暗号・ゼロ知識証明・数論」岡本龍明・太田和夫著、共立出版ｐｐ．１６７などに述べられている）
Ｓｔｅｐ５：正則でなければＳｔｅｐ１へもどってやりなおし。正則であれば、生成多項式ｆ（ｘ）としてｆi（ｘ）を出力。
【００２４】
また、この装置の構成としては、以下のような構成をすることもできる。
ｆ（ｘ）が２次多項式ｘ2＋ｖ1ｘ＋ｖ0の場合に多項式基底を用いた自乗を高速に行なうことを目的として、Ｓｔｅｐ０においてｖ0＝ｕ2と表わすことができるｆ（ｘ）を生成する。
既約性判定装置
図４に示す既約性判定装置は図２，３に示した装置における、既約性判定装置２０３，３０３の一構成例である。この装置４００は制御装置４０１と多項式ユークリッド（Ｅｕｃｌｉｄ）互除装置４０２とよりなる。
【００２５】
この装置の動作をプログラムで実現する場合は、図８に示すフローに従って実行する。
定義体ＧＦ（ｑn-1）と候補ｆ（ｘ）、拡大次数ｍを入力する。
ｇ（ｘ）＝（ｘ＾ｑn-1 m-1）−ｘを作る。ここでＡ＾ＢはＡBを表わす。次に多項式Ｅｕｃｌｉｄ互除法を用いて、入力された多項式ｆ（ｘ）とｇ（ｘ）＝（ｘ＾ｑn-1 m-1）−ｘとの最大公約多項式を求め、
その最大公約多項式が０次式ならば、「既約」を、１次以上ならば「可約」を出力する。
【００２６】
上述において各装置をコンピュータによりプログラムを解読実行させて機能させることもできる。
【００２７】
【発明の効果】
以上述べたようにこの発明の自乗演算装置によれば、２回の乗算と３回の定数倍演算とで済み、図９に示したものよりも、乗算回数が１回少なくて済み、それだけ高速に演算することができる。
また逐次拡大楕円曲線演算においてその拡大に利用する多項式基底の生成多項式を生成することができる。
【図面の簡単な説明】
【図１】この発明のＧＦ（ｑn）自乗器の実施例を示すブロック図。
【図２】この発明の多項式基底の生成多項式生成装置を示すブロック図。
【図３】この発明の正規多項式生成装置を示すブロック図。
【図４】図２、図３に用いた既約性判定装置の構成を示すブロック図。
【図５】図１に示した実施例におけるＧＦ（ｑn）自乗処理手順を示す流れ図。
【図６】図２に示した実施例における多項式基底の生成多項式生成処理手順を示す流れ図。
【図７】図３に示した実施例における正規多項式生成処理手順を示す流れ図。
【図８】図４に示した装置の既約性判定処理手順を示す流れ図。
【図９】先に提案したＧＦ（ｑn）自乗器の機能構成を示す図。
【発明の属する技術分野】
この発明は、例えば、情報セキュリティ技術（楕円曲線暗号／署名、素因数分解）を実現するために用いられる楕円曲線上の演算装置に関する。
【０００２】
【従来の技術】
楕円曲線上で公開鍵暗号やデジタル署名を実現する場合、その処理時間のほとんどは楕円曲線上のｋ倍演算に費やされる。
一般に、暗号や署名には有限体ＧＦ（ｑ）上で定義される楕円曲線を使う。これをＥ／ＧＦ（ｑ）と表記する。ｑは素数または素数のべき乗である。従来の実装法ではｑに素数または２m を用いることが多かったが、この発明は一般の有限体の場合を考える。
【０００３】
楕円曲線上の点Ｐに対する加算を定義できる。通常の加算と区別するためにこれを、「楕円加算」「楕円２倍演算」と呼ぶ。いずれも、有限体ＧＦ（ｑ）上の加減乗除算を組み合わせることで行うことが出来る。
通常、ｋ倍演算を構成するために、「楕円加算」「楕円２倍演算」を組み合わせて行なう方法が用いられている。
したがって、楕円曲線上の演算は、有限体ＧＦ（ｑ）上の加減乗除算に帰着することが出来、これらを高速化することが、楕円曲線上の演算の高速化につながる。
【０００４】
楕円曲線演算を、ＧＦ（ｑn）上の有理式の列Ｒ（ｘ0，ｘ1，…）及びｘ0，ｘ1 ，…の値をＧＦ（ｑn）演算器に入力し、ＧＦ（ｑn-1）上の演算列とデータに帰着させるＧＦ（ｑn-1）演算器へ渡し、ＧＦ（ｑn-1）演算器は入力をＧＦ（ｑn-2）上の演算の列とデータに帰着させてＧＦ（ｑn-2）演算器に渡し、以下同様のことを繰返して、ＧＦ（ｑ0）演算器で計算した結果を出力するように、つまり逐次拡大させることにより、従来の楕円曲線演算より、乗算回数を減少することができることを特願平１１−２３０１２３号「逐次拡大を用いた楕円曲線演算装置及びプログラム記録媒体」で提案した。
【０００５】
この場合のＧＦ（ｑn-1）のｍ次拡大体ＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上のＧＦ（ｑn-1）演算器における自乗器として、入力Ａ＝（Ａ0，Ａ1）、出力Ａ2 ＝（Ｃ0 ，Ｃ1）を正規基底によるＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上の元のＧＦ（ｑn-1）上の元により表現し、基底をαおよびβ（ただしα＋β＝−ｖ1）とするとＡ＝Ａ0α＋Ａ1β，Ａ2＝Ｃ0α＋Ｃ1βを意味し、全ての基底を解にもつＧＦ（ｑn-1）上ｍ次既約多項式をｆ（ｘ）＝ｘ2＋ｖ1ｘ＋ｖ0とし、
Ａ2＝（−Ａ0 2ｖ1＋（Ａ0−Ａ1）2（ｖ0／ｖ1））α＋（−Ａ1 2ｖ1＋（Ａ0−Ａ1）2（ｖ0／ｖ1））β
の演算を行うことが提案されている。つまり図９に示すようにＧＦ（ｑn-1）自乗器２７ＢでＡ0 2→Ｌ0を演算し、ＧＦ（ｑn-1）減算器２７ＣでＡ0−Ａ1→Ｌ1を演算し、ＧＦ（ｑn-1）自乗器２７ＤでＡ1 2→Ｌ2を演算し、ＧＦ（ｑn-1）自乗器２７ＥでＬ1 2→Ｌ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-1 m）を多項式基底を用いて行うが、その多項式基底に用いる生成多項式は既約でなければならない。また正規基底の場合は逐次的に拡大する時に、拡大ごとに高速演算に適した正規基底の生成元が定義されることによって、全ての基底を解に持つ既約多項式を定義して既約多項式の列を作る。従って、既約多項式を作る際、この解が正規基底になるものでなくてはならない。
【０００７】
【発明が解決しようとする課題】
この発明の１目的はＧＦ（ｑn-1）のｍ次拡大体ＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上の自乗器のＧＦ（ｑn-1）演算器の乗算回数を更に減らし、より高速な演算を行うことができる楕円曲線自乗演算装置を提供することにある。
この発明の他の目的は逐次拡大を用いた楕円曲線演算装置において、逐次拡大に適した基底を得るための生成多項式を生成する装置を提供することにある。
【０００８】
【課題を解決するための手段】
この発明の楕円曲線自乗演算装置においては全ての基底を解にもつＧＦ（ｑn-1）上ｍ次既約多項式をｆ（ｘ）＝ｘ2＋ｖ1ｘ＋ｖ0とし、特にｖ0＝ｕ2，ｕ∈ＧＦ（ｑi-1）と表わせるものを用い、
【０００９】
またこの発明による生成多項式生成装置は、生成多項式の候補を選び、その生成多項式候補が既約であるか検査し、既約でなければ次の生成多項式候補を選び同様のことを行い、既約であれば、これを用い、ＧＦ（ｑi）からＧＦ（ｑi+1）への拡大ごとに同様にして生成多項式を生成する。
【００１０】
【発明の実施の形態】
自乗器（正規基底）
この装置はＧＦ（ｑn-1）のｍ次拡大ＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上の自乗器のＧＦ（ｑn-1）上演算装置による一構成例である。
この構成例はｍ＝２であり、全ての基底を解にもつＧＦ（ｑn-1）上ｍ次生成多項式をｆ（ｘ）＝ｘ2＋ｖ1ｘ＋ｖ0とした場合にｖ0＝ｕ2なるｕ∈ＧＦ（ｑn-1）が存在する場合の装置である。
【００１１】
この説明および、図１においてＡ＝（Ａ0，Ａ1）およびＡ2 ＝（Ｃ0，Ｃ1）は正規基底によるＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上の元のＧＦ（ｑn-1）上の元による表現であり、基底をαおよびβとするとそれぞれＡ＝Ａ0α＋Ａ1βおよびＡ2 ＝Ｃ0α＋Ｃ1βを意味している。
図に示す装置１００はＧＦ（ｑn）＝ＧＦ（ｑn-1 m）上の元Ａ＝（Ａ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-1 m) を多項式基底を用いて行なうのに用いる生成多項式を求める装置の一構成例である。この装置２００は制御装置２０１にメモリ２０２と既約性判定装置２０３とが接続されて構成される。
【００１８】
この装置の動作をプログラムで実現する場合は、図６に示すフローに従って実行する。
Ｓｔｅｐ０：制御装置２０１は入力有限体ＧＦ（ｑ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-1 m）を正規基底を用いて行なうのに用いる正規多項式を求める装置の一構成例である。この装置３００は制御装置３０１にメモリ３０２、既約性判定装置３０３、正則判定装置３０４が接続されて構成される。
【００２２】
この装置の動作をプログラムで実現する場合は、図７に示すフローに従って実行する。
Ｓｔｅｐ０：有限体ＧＦ（ｑn-1）、拡大次数ｍを入力する。生成多項式候補ｆi（ｘ），（ｉ＝１，…，ｊ）を生成し、ｉを０に初期化した後、ｉ＝ｊかを判定し、ｉがｊでなければ、
Ｓｔｅｐ１：ｉを＋１して入力された有限体ＧＦ（ｑn-1）上の生成多項式候補ｆi（ｘ）を選ぶ。
【００２３】
Ｓｔｅｐ２：既約性判定装置３０３を用いてｆi（ｘ）が既約であるか検査する。
Ｓｔｅｐ３：既約でなければＳｔｅｐ１へもどってやりなおし。
Ｓｔｅｐ４：既約であれば正則判定装置３０４を用いてｆi（ｘ）が正則であるか検査する。（この検査の方法は、例えば「暗号・ゼロ知識証明・数論」岡本龍明・太田和夫著、共立出版ｐｐ．１６７などに述べられている）
Ｓｔｅｐ５：正則でなければＳｔｅｐ１へもどってやりなおし。正則であれば、生成多項式ｆ（ｘ）としてｆi（ｘ）を出力。
【００２４】
また、この装置の構成としては、以下のような構成をすることもできる。
ｆ（ｘ）が２次多項式ｘ2＋ｖ1ｘ＋ｖ0の場合に多項式基底を用いた自乗を高速に行なうことを目的として、Ｓｔｅｐ０においてｖ0＝ｕ2と表わすことができるｆ（ｘ）を生成する。
既約性判定装置
図４に示す既約性判定装置は図２，３に示した装置における、既約性判定装置２０３，３０３の一構成例である。この装置４００は制御装置４０１と多項式ユークリッド（Ｅｕｃｌｉｄ）互除装置４０２とよりなる。
【００２５】
この装置の動作をプログラムで実現する場合は、図８に示すフローに従って実行する。
定義体ＧＦ（ｑn-1）と候補ｆ（ｘ）、拡大次数ｍを入力する。
ｇ（ｘ）＝（ｘ＾ｑn-1 m-1）−ｘを作る。ここでＡ＾ＢはＡBを表わす。次に多項式Ｅｕｃｌｉｄ互除法を用いて、入力された多項式ｆ（ｘ）とｇ（ｘ）＝（ｘ＾ｑn-1 m-1）−ｘとの最大公約多項式を求め、
その最大公約多項式が０次式ならば、「既約」を、１次以上ならば「可約」を出力する。
【００２６】
上述において各装置をコンピュータによりプログラムを解読実行させて機能させることもできる。
【００２７】
【発明の効果】
以上述べたようにこの発明の自乗演算装置によれば、２回の乗算と３回の定数倍演算とで済み、図９に示したものよりも、乗算回数が１回少なくて済み、それだけ高速に演算することができる。
また逐次拡大楕円曲線演算においてその拡大に利用する多項式基底の生成多項式を生成することができる。
【図面の簡単な説明】
【図１】この発明のＧＦ（ｑn）自乗器の実施例を示すブロック図。
【図２】この発明の多項式基底の生成多項式生成装置を示すブロック図。
【図３】この発明の正規多項式生成装置を示すブロック図。
【図４】図２、図３に用いた既約性判定装置の構成を示すブロック図。
【図５】図１に示した実施例におけるＧＦ（ｑn）自乗処理手順を示す流れ図。
【図６】図２に示した実施例における多項式基底の生成多項式生成処理手順を示す流れ図。
【図７】図３に示した実施例における正規多項式生成処理手順を示す流れ図。
【図８】図４に示した装置の既約性判定処理手順を示す流れ図。
【図９】先に提案したＧＦ（ｑn）自乗器の機能構成を示す図。
Claims (2)
- 有限体ＧＦ（ｑn-1）（ｑn-1は素数又は素数のべき乗である）の２次拡大ＧＦ（ｑn）＝ＧＦ（ｑn-1 2）上の楕円曲線自乗演算装置であって、
入力Ａ＝（Ａ0，Ａ1）、出力Ａ2＝（Ｃ0，Ｃ1）は正規基底α，βによるＧＦ（ｑn）＝ＧＦ（ｑn-1 2）上の元が二つのＧＦ（ｑn-1）上の元より表現され、
Ａ＝Ａ0α＋Ａ1β、Ａ2＝Ｃ0α＋Ｃ1βであり、α，βを解にもつＧＦ（ｑn-1）上の２次生成多項式をｆ（ｘ）＝ｘ2＋ｖ1ｘ＋ｖ0とし、ｖ0＝ｕ2，ｕはＧＦ（ｑ n-1 ）上の元であって、
Ａ0とＡ1を入力してＡ0−Ａ1 の演算を行い、その演算結果をＬ 1 として出力する第１のＧＦ（ｑn-1）減算手段と、
Ｌ1を入力して（ｕ／ｖ1）Ｌ1 の演算を行い、その演算結果をＬ 2 として出力する第１のＧＦ（ｑn-1）定数倍手段と、
Ａ0とＬ2を入力してＡ0＋Ｌ2 の演算を行い、その演算結果をＬ 3 として出力する第１のＧＦ（ｑn-1）加算手段と、
Ａ0とＬ2を入力してＬ2−Ａ0 の演算を行い、その演算結果をＬ 4 として出力する第２のＧＦ（ｑn-1）減算手段と、
Ａ1とＬ2を入力してＡ1＋Ｌ2 の演算を行い、その演算結果をＬ 5 として出力する第２のＧＦ（ｑn-1）加算手段と、
Ａ1とＬ2を入力してＬ2−Ａ1 の演算を行い、その演算結果をＬ 6 として出力する第３のＧＦ（ｑn-1）減算手段と、
Ｌ3とＬ4を入力してＬ3×Ｌ4 の演算を行い、その演算結果をＬ 7 として出力する第１のＧＦ（ｑn-1）乗算手段と、
Ｌ5とＬ6を入力してＬ5×Ｌ6 の演算を行い、その演算結果をＬ 8 として出力する第２のＧＦ（ｑn-1）乗算手段と、
Ｌ7を入力して−ｖ1Ｌ7 の演算を行い、その演算結果をＣ 0 として出力する第２のＧＦ（ｑn-1）定数倍手段と、
Ｌ8を入力して−ｖ1Ｌ8 の演算を行い、その演算結果をＣ 1 として出力する第３のＧＦ（ｑn-1）定数倍手段と、
を具備する楕円曲線自乗演算装置。 - 入力Ａ＝（Ａ0，Ａ1）、出力Ａ2＝（Ｃ0，Ｃ1）が正規基底α，βによるＧＦ（ｑn）＝ＧＦ（ｑn-1 2）上の元が二つのＧＦ（ｑn-1）上の元により表現され（ｑnは素数又は素数のべき乗である）、Ａ＝Ａ0α＋Ａ1β，Ａ2＝Ｃ0α＋Ｃ1βであり、α，βを解にもつＧＦ（ｑn-1）上の２次生成多項式をｆ（ｘ）＝ｘ2＋ｖ1ｘ＋ｖ0とし、ｖ0＝ｕ2，ｕはＧＦ（ｑ n-1 ）上の元であってＡを入力し、Ａ2を出力する有限体ＧＦ（ｑn-1）の２次拡大ＧＦ（ｑn）＝ＧＦ（ｑn-1）上の楕円曲線自乗演算装置のコンピュータに、
第１のＧＦ（ｑn-1）減算手段が、Ａ0及びＡ1の入力を受け付け、Ａ0とＡ1からＡ0−Ａ1 を求め、その演算結果をＬ 1 として出力する処理と、
第１のＧＦ（ｑn-1）定数倍手段が、ｖ0とｖ1とＬ1とから（ｕ／ｖ1）Ｌ1 を求め、その演算結果をＬ 2 として出力する処理と、
第１のＧＦ（ｑn-1）加算手段が、Ｌ2とＡとからＬ2＋Ａ0 を求め、その演算結果をＬ 3 として出力する処理と、
第２のＧＦ（ｑn-1）減算手段が、Ｌ2とＡからＬ2−Ａ0 を求め、その演算結果をＬ 4 として出力する処理と、
第２のＧＦ（ｑn-1）加算手段が、Ａ1とＬ2とからＬ2＋Ａ1 を求め、その演算結果をＬ 5 として出力する処理と、
第３のＧＦ（ｑn-1）減算手段が、Ａ1とＬ2とからＬ2−Ａ1 を求め、その演算結果をＬ 6 として出力する処理と、
第１のＧＦ（ｑn-1）乗算手段が、Ｌ3とＬ4からＬ3Ｌ4 を求め、その演算結果をＬ 7 として出力する処理と、
第２のＧＦ（ｑn-1）乗算手段が、Ｌ5とＬ6からＬ5Ｌ6 を求め、その演算結果をＬ 8 として出力する処理と、
第２のＧＦ（ｑn-1）定数倍手段が、Ｌ7と−ｖ1から−ｖ1Ｌ7 を求め、その演算結果をＣ 0 として出力する処理と、
第３のＧＦ（ｑn-1）定数倍手段が、Ｌ8と−ｖ1から−ｖ1Ｌ8 を求め、その演算結果をＣ 1 として出力する処理と、
を実行させるプログラムを記録した記録媒体。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000016019A JP3638493B2 (ja) | 2000-01-25 | 2000-01-25 | 楕円曲線自乗演算装置、およびこのプログラム記録媒体 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000016019A JP3638493B2 (ja) | 2000-01-25 | 2000-01-25 | 楕円曲線自乗演算装置、およびこのプログラム記録媒体 |
Related Child Applications (2)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2004262980A Division JP3935902B2 (ja) | 2004-09-09 | 2004-09-09 | 生成多項式生成装置およびこれらのプログラム記録媒体 |
| JP2004262981A Division JP3935903B2 (ja) | 2004-09-09 | 2004-09-09 | 生成多項式生成装置およびこれらのプログラム記録媒体 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2001209315A JP2001209315A (ja) | 2001-08-03 |
| JP3638493B2 true JP3638493B2 (ja) | 2005-04-13 |
Family
ID=18543228
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000016019A Expired - Lifetime JP3638493B2 (ja) | 2000-01-25 | 2000-01-25 | 楕円曲線自乗演算装置、およびこのプログラム記録媒体 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3638493B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005284111A (ja) * | 2004-03-30 | 2005-10-13 | Japan Science & Technology Agency | 楕円曲線暗号の高速演算処理方法および装置 |
-
2000
- 2000-01-25 JP JP2000016019A patent/JP3638493B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JP2001209315A (ja) | 2001-08-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US20110161390A1 (en) | Modular multiplication processing apparatus | |
| JP2000187438A (ja) | 楕円曲線暗号実行方法及び装置並びに記録媒体 | |
| JP5182364B2 (ja) | サイドチャネル攻撃に対する耐タンパ性を有する暗号処理方法 | |
| JP3794266B2 (ja) | 楕円曲線スカラー倍計算方法及び装置並びに記憶媒体 | |
| KR101154845B1 (ko) | 스칼라 배산기 및 스칼라 배산프로그램 | |
| JP4354609B2 (ja) | 有限体上の連立方程式求解装置及び逆元演算装置 | |
| US20030026419A1 (en) | Elliptic curve encryption processing method, elliptic curve encryption processing apparatus, and program | |
| JP3638493B2 (ja) | 楕円曲線自乗演算装置、およびこのプログラム記録媒体 | |
| EP1600852B1 (en) | Method and apparatus for calculating a modular inverse | |
| JP3434220B2 (ja) | 逆元演算装置、及びそのプログラム記録媒体 | |
| JP4543143B2 (ja) | 楕円曲線暗号装置、楕円曲線暗号演算方法 | |
| KR101223498B1 (ko) | 타원 곡선 암호 방식에서 공개키를 생성하는 방법 및 상기방법을 수행하는 시스템 | |
| Anagreh et al. | Accelerate Performance for Elliptic Curve Scalar Multiplication based on NAF by Parallel Computing. | |
| JP3935903B2 (ja) | 生成多項式生成装置およびこれらのプログラム記録媒体 | |
| JP3935902B2 (ja) | 生成多項式生成装置およびこれらのプログラム記録媒体 | |
| JP3390966B2 (ja) | 平方数を法とした剰余演算装置及びそのプログラム記録媒体 | |
| JP4479135B2 (ja) | 演算装置及び演算方法及び演算プログラム | |
| JP3329440B2 (ja) | 事前計算を用いた複数生成元に対する演算装置及びそのプログラム記録媒体 | |
| JP4550232B2 (ja) | 演算装置及び演算方法及びプログラムを記録したコンピュータ読み取り可能な記録媒体 | |
| JP3966714B2 (ja) | 暗号処理方法、そのプログラム及びその記録媒体 | |
| JP4629972B2 (ja) | ベクトル演算装置及び分割値演算装置及び楕円曲線スカラー倍演算装置及び楕円暗号演算装置及びベクトル演算方法及びプログラム及びプログラムを記録したコンピュータ読み取り可能な記録媒体 | |
| JP3460798B2 (ja) | 楕円積和演算計算方法、楕円積和演算計算装置及び楕円積和演算計算プログラムを記録した記録媒体 | |
| JP2004205870A (ja) | 超楕円曲線スカラー倍演算方法及び装置 | |
| JPH076025A (ja) | 冪剰余演算方法および装置 | |
| JP2001194996A (ja) | 多項式の除算装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040713 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040909 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20041005 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20041112 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20041214 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050111 |
|
| R151 | Written notification of patent or utility model registration |
Ref document number: 3638493 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R151 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080121 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090121 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090121 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100121 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110121 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110121 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120121 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130121 Year of fee payment: 8 |
|
| S531 | Written request for registration of change of domicile |
Free format text: JAPANESE INTERMEDIATE CODE: R313531 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| EXPY | Cancellation because of completion of term |