(57)【特許請求の範囲】
【請求項１】
整数変数χを用いて、埋め込み次数ｋ＝12における標数ｐ、位数ｒ、フロベニウス自己準同型写像のトレースｔが、
p(χ)＝36χ4−36χ3＋24χ2−6χ＋1，
r(χ)＝36χ4−36χ3＋18χ2−6χ＋1＝p(χ)＋1−t(χ)，
t(χ)＝6χ2＋1，
として与えられる楕円曲線の有理点が成す加法群Ｅ(Ｆp)の有理点Ｐのスカラ倍算[s]Ｐを演算するスカラ倍算器であって、
ツイスト次数ｄを６とし、ｋ＝ｄ×ｅとなる正整数ｅを２として、
[p2]Ｐ＝φ'2(Ｐ),
となるフロベニウス写像φ'2を用い、
[6χ2−4χ＋1]Ｐ＝[(-2χ＋1)p2]Ｐ＝[-2χ＋1]φ'2(Ｐ)
であることから、6χ2−4χ＋1＝νとして前記スカラｓをν進数展開することにより
ｓ＝s1ν＋s2，s2＜ν，
とし、
ｓ≡(-2χ＋1)s1p2＋s2  mod r,
であることから、(-2χ＋1)s1部分をν進数展開して、
ｓ≡(s3ν＋s4)p2＋s2≡s5p4＋s4p2＋s2  mod r,
とし、p4≡p2−1  mod rであることから、
ｓ≡(s4＋s5)p2＋(s2−s5)  mod r,
であることを利用して、スカラ倍算[s]Ｐを、
[s]Ｐ＝([s4＋s5]φ'2＋[s2−s5])Ｐ,
として演算すべく、
前記スカラｓの値を記憶する記憶手段と、
前記係数s1,s2,s3,s4,s5をそれぞれ記憶する第１〜５補助記憶手段と
を設け、
前記スカラｓをν進数展開して得られた値を前記第１補助記憶手段と前記第２補助記憶手段に記憶させ、(-2χ＋1)s1をν進数展開して得られた値を前記第３補助記憶手段と前記第４補助記憶手段に記憶させ、(-2χ＋1)s3の値を前記第５補助記憶手段に記憶させているスカラ倍算器。
【請求項２】
整数変数χを用いて、埋め込み次数ｋ＝12における標数ｐ、位数ｒ、フロベニウス自己準同型写像のトレースｔが、
p(χ)＝36χ4−36χ3＋24χ2−6χ＋1，
r(χ)＝36χ4−36χ3＋18χ2−6χ＋1＝p(χ)＋1−t(χ)，
t(χ)＝6χ2＋1，
として与えられる楕円曲線の有理点が成す加法群Ｅ(Ｆp)の有理点Ｐのスカラ倍算[s]Ｐを、ＣＰＵを備えた電子計算機に演算させるスカラ倍算プログラムであって、
ツイスト次数ｄを６とし、ｋ＝ｄ×ｅとなる正整数ｅを２として、
[p2]Ｐ＝φ'2(Ｐ),
となるフロベニウス写像φ'2を用い、
[6χ2−4χ＋1]Ｐ＝[(-2χ＋1)p2]Ｐ＝[-2χ＋1]φ'2(Ｐ)
であることから、6χ2−4χ＋1＝νとして前記スカラｓをν進数展開することにより
ｓ＝s1ν＋s2，s2＜ν，
とし、
ｓ≡(-2χ＋1)s1p2＋s2  mod r,
であることから、(-2χ＋1)s1部分をν進数展開して、
ｓ≡(s3ν＋s4)p2＋s2≡s5p4＋s4p2＋s2  mod r,
とし、p4≡p2−1  mod rであることから、
ｓ≡(s4＋s5)p2＋(s2−s5)  mod r,
であることを利用して、スカラ倍算[s]Ｐを、
[s]Ｐ＝([s4＋s5]φ'2＋[s2−s5])Ｐ,
として前記電子計算機に演算させるべく、
前記スカラｓをν進数展開して得られる前記s1を第１のレジスタに格納させるとともに前記s2を第２のレジスタに格納させるステップと、
(-2χ＋1)s1をν進数展開して得られる前記s3を第３のレジスタに格納させるとともに前記s4を第４のレジスタに格納させるステップと、
(-2χ＋1)s3の値を前記s5の値として第５のレジスタに格納させるステップと、
を有するスカラ倍算プログラム。
【請求項３】
整数変数χを用いて、埋め込み次数ｋ＝8における標数ｐ、位数ｒ、フロベニウス自己準同型写像のトレースｔが、
p(χ)＝(81χ6＋54χ5＋45χ4＋12χ3＋13χ2＋6χ＋1)/4，
r(χ)＝9χ4＋12χ3＋8χ2＋4χ＋1，
t(χ)＝−9χ3−3χ2−2χ，
として与えられる楕円曲線の有理点が成す加法群Ｅ(Ｆp)の有理点Ｐのスカラ倍算[s]Ｐを演算するスカラ倍算器であって、
ツイスト次数ｄを４とし、ｋ＝ｄ×ｅとなる正整数ｅを２として、
[p2]Ｐ＝φ'2(Ｐ),
となるフロベニウス写像φ'2を用い、
[3χ2＋2χ]Ｐ＝[(-2χ−1)p2]Ｐ＝[-2χ−1]φ'2(Ｐ)
であることから、3χ2＋2χ＝νとして前記スカラｓをν進数展開することにより
ｓ＝s1ν＋s2，s2＜ν，
とし、
ｓ≡(-2χ−1)s1p2＋s2  mod r,
であることから、(-2χ−1)s1部分をν進数展開して、
ｓ≡(s3ν＋s4)p2＋s2≡s5p4＋s4p2＋s2  mod r,
とし、p4≡−1  mod rであることから、
ｓ≡s4p2＋(s2−s5)  mod r,
であることを利用して、スカラ倍算[s]Ｐを、
[s]Ｐ＝([s4]φ'2＋[s2−s5])Ｐ,
として演算すべく、
前記スカラｓの値を記憶する記憶手段と、
前記係数s1,s2,s3,s4,s5をそれぞれ記憶する第１〜５補助記憶手段と
を設け、
前記スカラｓをν進数展開して得られた値を前記第１補助記憶手段と前記第２補助記憶手段に記憶させ、(-2χ−1)s1をν進数展開して得られた値を前記第３補助記憶手段と前記第４補助記憶手段に記憶させ、(-2χ−1)s3の値を前記第５補助記憶手段に記憶させているスカラ倍算器。
【請求項４】
整数変数χを用いて、埋め込み次数ｋ＝8における標数ｐ、位数ｒ、フロベニウス自己準同型写像のトレースｔが、
p(χ)＝(81χ6＋54χ5＋45χ4＋12χ3＋13χ2＋6χ＋1)/4，
r(χ)＝9χ4＋12χ3＋8χ2＋4χ＋1，
t(χ)＝−9χ3−3χ2−2χ，
として与えられる楕円曲線の有理点が成す加法群Ｅ(Ｆp)の有理点Ｐのスカラ倍算[s]Ｐを、ＣＰＵを備えた電子計算機に演算させるスカラ倍算プログラムであって、
ツイスト次数ｄを４とし、ｋ＝ｄ×ｅとなる正整数ｅを２として、
[p2]Ｐ＝φ'2(Ｐ),
となるフロベニウス写像φ'2を用い、
[3χ2＋2χ]Ｐ＝[(-2χ−1)p2]Ｐ＝[-2χ−1]φ'2(Ｐ)
であることから、3χ2＋2χ＝νとして前記スカラｓをν進数展開することにより
ｓ＝s1ν＋s2，s2＜ν，
とし、
ｓ≡(-2χ−1)s1p2＋s2  mod r,
であることから、(-2χ−1)s1部分をν進数展開して、
ｓ≡(s3ν＋s4)p2＋s2≡s5p4＋s4p2＋s2  mod r,
とし、p4≡−1  mod rであることから、
ｓ≡s4p2＋(s2−s5)  mod r,
であることを利用して、スカラ倍算[s]Ｐを、
[s]Ｐ＝([s4]φ'2＋[s2−s5])Ｐ,
として前記電子計算機に演算させるべく、
前記スカラｓをν進数展開して得られる前記s1を第１のレジスタに格納させるとともに前記s2を第２のレジスタに格納させるステップと、
(-2χ−1)s1をν進数展開して得られる前記s3を第３のレジスタに格納させるとともに前記s4を第４のレジスタに格納させるステップと、
(-2χ−1)s3の値を前記s5の値として第５のレジスタに格納させるステップと、
を有するスカラ倍算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有理点Ｐのスカラ倍算[s]Ｐを行うスカラ倍算器及びスカラ倍算プログラムに関する。
【背景技術】
【０００２】
従来、インターネットなどの電気通信回線を利用して、インターネットバンキングや行政機関への電子申請などのような各種のサービスが提供されてきている。【０００３】
このようなサービスを利用する場合には、サービスの利用者が、成りすましや架空の人間などではなく、適正な利用者であることを確認するための認証処理が必要である。そこで、信頼性の高い認証方法として、公開鍵と秘密鍵を用いる公開鍵暗号をベースとした電子認証技術がよく利用されていた。【０００４】
昨今では、より多くの利用者を効率よく管理しやすくするために、ＩＤベース暗号やグループ署名を用いた認証システムが提案されている。【０００５】
ＩＤベース暗号やグループ署名では、ペアリング演算とともに、所要のべき乗算やスカラ倍算が行われており、認証処理に要する時間をできるだけ短縮させるには、これらの演算を高速に実行することが求められていた。【０００６】
そのため、べき乗算やスカラ倍算をバイナリ法やWindow法などを用いて高速化することが提案されていた。【０００７】
さらに、スカラ倍算においては、写像を利用することにより演算回数を削減して高速化する手法が提案されていた(例えば、特許文献１、特許文献２参照。)。
【特許文献１】特開２００４−２７１７９２号公報
【特許文献２】特開２００７−４１４６１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、単に写像を利用して演算回数を削減するだけでは高速化が十分ではなく、特に、１万人を超えるような利用者を対象とした認証処理を数秒以内で完了させることが困難であったため、実用に耐えないおそれがあった。【０００９】
本発明者らはこのような現状に鑑み、スカラ倍算を高速化することにより実用性を向上させるべく研究開発を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【００１０】
本発明のスカラ倍算器では、整数変数χを用いて、埋め込み次数ｋ＝12における標数ｐ、位数ｒ、フロベニウス自己準同型写像のトレースｔが、
p(χ)＝36χ4−36χ3＋24χ2−6χ＋1，
r(χ)＝36χ4−36χ3＋18χ2−6χ＋1＝p(χ)＋1−t(χ)，
t(χ)＝6χ2＋1，
として与えられる楕円曲線の有理点が成す加法群Ｅ(Ｆp)の有理点Ｐのスカラ倍算[s]Ｐを演算するスカラ倍算器であって、ツイスト次数ｄを６とし、ｋ＝ｄ×ｅとなる正整数ｅを２として、
[p2]Ｐ＝φ'2(Ｐ),
となるフロベニウス写像φ'2を用い、
[6χ2−4χ＋1]Ｐ＝[(-2χ＋1)p2]Ｐ＝[-2χ＋1]φ'2(Ｐ)
であることから、6χ2−4χ＋1＝νとして前記スカラｓをν進数展開することにより
ｓ＝s1ν＋s2，s2＜ν，
とし、
ｓ≡(-2χ＋1)s1p2＋s2  mod r,
であることから、(-2χ＋1)s1部分をν進数展開して、
ｓ≡(s3ν＋s4)p2＋s2≡s5p4＋s4p2＋s2  mod r,
とし、p4≡p2−1  mod rであることから、
ｓ≡(s4＋s5)p2＋(s2−s5)  mod r,
であることを利用して、スカラ倍算[s]Ｐを、
[s]Ｐ＝([s4＋s5]φ'2＋[s2−s5])Ｐ,
として演算すべく、前記スカラｓの値を記憶する記憶手段と、前記係数s1,s2,s3,s4,s5をそれぞれ記憶する第１〜５補助記憶手段とを設け、前記スカラｓをν進数展開して得られた値を前記第１補助記憶手段と前記第２補助記憶手段に記憶させ、(-2χ＋1)s1をν進数展開して得られた値を前記第３補助記憶手段と前記第４補助記憶手段に記憶させ、(-2χ＋1)s3の値を前記第５補助記憶手段に記憶させることとした。【００１１】
また、本発明のスカラ倍算プログラムでは、整数変数χを用いて、埋め込み次数ｋ＝12における標数ｐ、位数ｒ、フロベニウス自己準同型写像のトレースｔが、
p(χ)＝36χ4−36χ3＋24χ2−6χ＋1，
r(χ)＝36χ4−36χ3＋18χ2−6χ＋1＝p(χ)＋1−t(χ)，
t(χ)＝6χ2＋1，
として与えられる楕円曲線の有理点が成す加法群Ｅ(Ｆp)の有理点Ｐのスカラ倍算[s]Ｐを、ＣＰＵを備えた電子計算機に演算させるスカラ倍算プログラムであって、ツイスト次数ｄを６とし、ｋ＝ｄ×ｅとなる正整数ｅを２として、
[p2]Ｐ＝φ'2(Ｐ),
となるフロベニウス写像φ'2を用い、
[6χ2−4χ＋1]Ｐ＝[(-2χ＋1)p2]Ｐ＝[-2χ＋1]φ'2(Ｐ)
であることから、6χ2−4χ＋1＝νとして前記スカラｓをν進数展開することにより
ｓ＝s1ν＋s2，s2＜ν，
とし、
ｓ≡(-2χ＋1)s1p2＋s2  mod r,
であることから、(-2χ＋1)s1部分をν進数展開して、
ｓ≡(s3ν＋s4)p2＋s2≡s5p4＋s4p2＋s2  mod r,
とし、p4≡p2−1  mod rであることから、
ｓ≡(s4＋s5)p2＋(s2−s5)  mod r,
であることを利用して、スカラ倍算[s]Ｐを、
[s]Ｐ＝([s4＋s5]φ'2＋[s2−s5])Ｐ,
として前記電子計算機に演算させるべく、前記スカラｓをν進数展開して得られる前記s1を第１のレジスタに格納させるとともに前記s2を第２のレジスタに格納させるステップと、(-2χ＋1)s1をν進数展開して得られる前記s3を第３のレジスタに格納させるとともに前記s4を第４のレジスタに格納させるステップと、(-2χ＋1)s3の値を前記s5の値として第５のレジスタに格納させるステップとを有することとした。【００１２】
また、本発明のスカラ倍算器では、整数変数χを用いて、埋め込み次数ｋ＝8における標数ｐ、位数ｒ、フロベニウス自己準同型写像のトレースｔが、
p(χ)＝(81χ6＋54χ5＋45χ4＋12χ3＋13χ2＋6χ＋1)/4，
r(χ)＝9χ4＋12χ3＋8χ2＋4χ＋1，
t(χ)＝−9χ3−3χ2−2χ，
として与えられる楕円曲線の有理点が成す加法群Ｅ(Ｆp)の有理点Ｐのスカラ倍算[s]Ｐを演算するスカラ倍算器であって、
ツイスト次数ｄを４とし、ｋ＝ｄ×ｅとなる正整数ｅを２として、
[p2]Ｐ＝φ'2(Ｐ),
となるフロベニウス写像φ'2を用い、
[3χ2＋2χ]Ｐ＝[(-2χ−1)p2]Ｐ＝[-2χ−1]φ'2(Ｐ)
であることから、3χ2＋2χ＝νとして前記スカラｓをν進数展開することにより
ｓ＝s1ν＋s2，s2＜ν，
とし、
ｓ≡(-2χ−1)s1p2＋s2  mod r,
であることから、(-2χ−1)s1部分をν進数展開して、
ｓ≡(s3ν＋s4)p2＋s2≡s5p4＋s4p2＋s2  mod r,
とし、p4≡−1  mod rであることから、
ｓ≡s4p2＋(s2−s5)  mod r,
であることを利用して、スカラ倍算[s]Ｐを、
[s]Ｐ＝([s4]φ'2＋[s2−s5])Ｐ,
として演算すべく、前記スカラｓの値を記憶する記憶手段と、前記係数s1,s2,s3,s4,s5をそれぞれ記憶する第１〜５補助記憶手段とを設け、前記スカラｓをν進数展開して得られた値を前記第１補助記憶手段と前記第２補助記憶手段に記憶させ、(-2χ−1)s1をν進数展開して得られた値を前記第３補助記憶手段と前記第４補助記憶手段に記憶させ、(-2χ−1)s3の値を前記第５補助記憶手段に記憶させることとした。【００１３】
また、本発明のスカラ倍算プログラムでは、整数変数χを用いて、埋め込み次数ｋ＝8における標数ｐ、位数ｒ、フロベニウス自己準同型写像のトレースｔが、
p(χ)＝(81χ6＋54χ5＋45χ4＋12χ3＋13χ2＋6χ＋1)/4，
r(χ)＝9χ4＋12χ3＋8χ2＋4χ＋1，
t(χ)＝−9χ3−3χ2−2χ，
として与えられる楕円曲線の有理点が成す加法群Ｅ(Ｆp)の有理点Ｐのスカラ倍算[s]Ｐを、ＣＰＵを備えた電子計算機に演算させるスカラ倍算プログラムであって、ツイスト次数ｄを４とし、ｋ＝ｄ×ｅとなる正整数ｅを２として、
[p2]Ｐ＝φ'2(Ｐ),
となるフロベニウス写像φ'2を用い、
[3χ2＋2χ]Ｐ＝[(-2χ−1)p2]Ｐ＝[-2χ−1]φ'2(Ｐ)
であることから、3χ2＋2χ＝νとして前記スカラｓをν進数展開することにより
ｓ＝s1ν＋s2，s2＜ν，
とし、
ｓ≡(-2χ−1)s1p2＋s2  mod r,
であることから、(-2χ−1)s1部分をν進数展開して、
ｓ≡(s3ν＋s4)p2＋s2≡s5p4＋s4p2＋s2  mod r,
とし、p4≡−1  mod rであることから、
ｓ≡s4p2＋(s2−s5)  mod r,
であることを利用して、スカラ倍算[s]Ｐを、
[s]Ｐ＝([s4]φ'2＋[s2−s5])Ｐ,
として前記電子計算機に演算させるべく、前記スカラｓをν進数展開して得られる前記s1を第１のレジスタに格納させるとともに前記s2を第２のレジスタに格納させるステップと、(-2χ−1)s1をν進数展開して得られる前記s3を第３のレジスタに格納させるとともに前記s4を第４のレジスタに格納させるステップと、(-2χ−1)s3の値を前記s5の値として第５のレジスタに格納させるステップとを有することとした。
【発明の効果】
【００１４】
本発明によれば、スカラ倍算[s]Ｐを演算するに当たり、スカラｓをν進展開してスカラｓの大きさを小さくするとともに、
[p2]Ｐ＝φ'2(Ｐ)
を満たすフロベニウス写像φ'2(Ｐ)を用いることにより、スカラ倍算[s]Ｐの演算量をほぼ半減させることができ、スカラ倍算を高速化できる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施形態にかかるスカラ倍算器を備えた電子計算機の概略模式図である。
【図２】本発明の実施形態にかかるスカラ倍算プログラムのフローチャートである。
【符号の説明】
【００１６】
10  電子計算機
11  ＣＰＵ
12  記憶装置
13  メモリ装置
14  バス
110 スカラ値用レジスタ
111 第１のレジスタ
112 第２のレジスタ
113 第３のレジスタ
114 第４のレジスタ
115 第５のレジスタ5
【発明を実施するための最良の形態】
【００１７】
本発明の実施形態を説明するにあたり、最初に埋め込み次数ｋ＝12の場合について説明し、その後、埋め込み次数ｋ＝8の場合について説明する。【００１８】
本実施形態のスカラ倍算器及びスカラ倍算プログラムで実行されるスカラ倍算は、埋め込み次数ｋ＝12の場合、標数ｐ、位数ｒ、フロベニウス自己準同型写像のトレースｔが、
p(χ)＝36χ4−36χ3＋24χ2−6χ＋1，  ・・・（式１）
r(χ)＝36χ4−36χ3＋18χ2−6χ＋1＝p(χ)＋1−t(χ)，  ・・・（式２）
t(χ)＝6χ2＋1，  ・・・（式３）
として与えられる楕円曲線の有理点が成す加法群Ｅ(Ｆp)の有理点Ｐのスカラ倍算[s]Ｐである。この楕円曲線は、ペアリングフレンドリ曲線の１種としてBarreto-Naehrig曲線（以下、「ＢＮ曲線」という。）が知られているものである。【００１９】
このＢＮ曲線で表される楕円曲線に対しては、部分体ツイスト曲線が存在することが知られている。特に、埋め込み次数ｋ＝12の場合には、６次のツイスト曲線が知られており、
[p2]Ｐ＝φ'2(Ｐ),
となるフロベニウス写像φ'2が知られている。【００２０】
このフロベニウス写像φ'2を用いることにより、スカラ演算を高速化することができることを利用するとともに、本発明では、以下に説明する関係式を利用してスカラ演算を高速化している。【００２１】
まず、式２より下式が得られる。
36χ4−36χ3＋18χ2−6χ＋1≡0 mod r.  ・・・（式４）【００２２】
また、p≡t−１ mod rであるので、下式が得られる。
p2−6χp＋3p−6χ＋１≡0 mod r.  ・・・（式５）【００２３】
ここで、式５を変形することにより下式が得られる。
(−6χ＋3)p≡−p2＋6χ−１ mod r.  ・・・（式６）【００２４】
ここで、式６の両辺を平方することにより下式が得られる。
(−6χ＋3)2p2≡(p2−6χ＋１)2 mod r,
36χ2p2−36χp2＋９p2≡p4−12χp2＋2p2＋36χ2−12χ＋1 mod r.  ・・・（式７）【００２５】
さらに、p4＋１≡p2 mod rであることを利用して式７を変形することにより、下式が得られる。
36χ2p2−36χp2＋９p2≡−12χp2＋3p2＋36χ2−12χ mod r,
36χ2(p2−1)≡(24χ−6)p2−12χ mod r,
6χ2(p2−1)≡(4χ−1)p2−2χ mod r.  ・・・（式８）【００２６】
そして、式８の両辺に(p2−1)-1を掛ける際に、
p4−p2＋1≡0 mod r,  ・・・（式９）
であることから、
−p2(p2−1)≡1 mod r,  ・・・（式１０）
であるので、
(p2−1)-1≡−p2 mod r,  ・・・（式１１）
であることを利用して、式８を下式にように変形できる。
6χ2≡−(4χ−1)p4＋2χp2
≡−(4χ−1)(p2−1)＋2χp2 mod r.  ・・・（式１２）【００２７】
したがって、式１２を変形することにより下式が得られる。
6χ2−4χ＋1≡(−2χ−1)p2 mod r,  ・・・（式１３）【００２８】
これにより、下式のフロベニウス写像φ'2の関係式が得られる。
[6χ2−4χ＋1]Ｐ＝[(-2χ＋1)p2]Ｐ＝[-2χ＋1]φ'2(Ｐ),  ・・・（式１４）【００２９】
次いで、フロベニウス写像φ'2を用いたスカラ倍算[s]Ｐを考える。ここで、便宜上、
ν＝6χ2−4χ＋1,  ・・・（式１５）
とする。【００３０】
この場合、スカラｓのν進展開は下式のように表すことができる。
ｓ＝s1ν＋s2,s2＜ν.  ・・・（式１６）【００３１】
ここで、式１６は、式１５と式１４より、下式のように表すことができる。
ｓ≡(-2χ＋1)s1p2＋s2 mod r.  ・・・（式１７）【００３２】
なお、(-2χ＋1)s1はνより大きくなることがある。そこで、(-2χ＋1)s1をさらにν進展開して下式のように表すこととする。
ｓ≡(s3ν＋s4)p2＋s2 mod r.  ・・・（式１８）【００３３】
ここで式１４によりs3νp2≡(-2χ＋1)s3p4であるので、(-2χ＋1)s3＝s5とすることにより、式１８は下式のように表すことができる。
ｓ≡s5p4＋s4p2＋s2 mod r.  ・・・（式１９）【００３４】
この場合、s4とs2はνよりも小さい一方で、s5はνより小さくないかもしれないが、そのような場合でもそれほど大きくなることはなく、問題となることはない。【００３５】
式９よりp4≡p2−1 mod rであることから、式１９は下式のように変形できる。
ｓ≡s5(p2−1)＋s4p2＋s2≡(s4＋s5)p2＋(s2−s5) mod r.  ・・・（式２０）【００３６】
ここで、
Ａ＝s4＋s5,  ・・・（式２１）
Ｂ＝s2−s5,  ・・・（式２２）
とすると、スカラ倍算[s]Ｐは
[s]Ｐ＝([Ａ]φ'2＋[Ｂ])Ｐ,  ・・・（式２３）
として演算できる。【００３７】
したがって、たとえば、256ビットサイズのスカラｓに対するスカラ倍算を演算する際には、Ａ及びＢは128ビットサイズとなるので、演算量をほぼ半減させてスカラ倍算を高速化することができる。【００３８】
上述したスカラ倍算を行うスカラ倍算器は、図１に示すように電子計算機10で構成されるものであり、演算処理を実行するＣＰＵ11と、スカラ倍算プログラム及びスカラ倍算プログラムで使用する有理点のデータなどを記憶したハードディスクなどの記憶装置12と、スカラ倍算プログラムを展開して実行可能とするとともに、スカラ倍算プログラムの実行にともなって生成されたデータを一時的に記憶するＲＡＭなどで構成されたメモリ装置13を備えている。図１中、14はバスである。【００３９】
本実施形態では、ＣＰＵ11内にスカラｓの値を記憶するスカラ値用レジスタ110を記憶手段として設けることとしている。さらに、ＣＰＵ11内には、上述したようにスカラｓのν進数展開にともなって生じる係数s1,s2,s3,s4,s5の値をそれぞれ記憶する第１〜５のレジスタ111,112,113,114,115を第１〜５補助記憶手段として設けている。なお、スカラ値用レジスタ110で構成した記憶手段、及び第１〜５のレジスタ111,112,113,114,115で構成した第１〜５補助記憶手段は、ＣＰＵ11内にではなく、メモリ装置13などのＣＰＵ11以外の記憶手段に設けてもよい。【００４０】
スカラ倍算器として機能する電子計算機10では、スカラ倍算の実行が必要となった場合にスカラ倍算プログラムを起動して、スカラ倍算を実行している。【００４１】
すなわち、電子計算機10では、起動したスカラ倍算プログラムによって、図２に示すフローチャートに基づいてスカラ倍算を行い、演算結果を出力している。【００４２】
起動したスカラ倍算プログラムによって、電子計算機10では、ＣＰＵ11を入力手段として機能させて、記憶装置12またはメモリ装置13に記憶されている整数変数χのデータと、有理点Ｐのデータを読み出して、ＣＰＵ11の内部に設けている所定のレジスタにそれぞれ入力している(ステップＳ１)。【００４３】
さらに、電子計算機10では、スカラ倍算プログラムによってＣＰＵ11を入力手段として機能させて、スカラ倍算におけるスカラｓの値を入力させている。そして、ＣＰＵ11を記憶手段として機能させて、入力されたスカラｓの値をスカラ値用レジスタ110に記憶している(ステップＳ２)。【００４４】
次いで、電子計算機10では、スカラ倍算プログラムによってＣＰＵ11を演算手段として機能させて、上述したようにスカラｓをν進数展開して、ν進数展開の係数であるs1とs2を算出している(ステップＳ３)。すなわち、係数s1は、スカラｓをνで除した際の商であり、係数s2は、スカラｓをνで除した際の剰余である。【００４５】
算出されたν進数展開の係数であるs1とs2の値は、ＣＰＵ11を記憶手段として機能させて、第１のレジスタ111及び第２のレジスタ112にそれぞれ格納して、記憶させている(ステップＳ４)。【００４６】
次いで、電子計算機10では、ＣＰＵ11を演算手段として機能させて(-2χ＋1)s1の値を演算し(ステップＳ５)、上述したように(-2χ＋1)s1をν進数展開して、ν進数展開の係数であるs3とs4を算出している(ステップＳ６)。すなわち、係数s3は、(-2χ＋1)s1をνで除した際の商であり、係数s4は、(-2χ＋1)s1をνで除した際の剰余である。【００４７】
算出された(-2χ＋1)s1のν進数展開の係数であるs3とs4の値は、ＣＰＵ11を記憶手段として機能させて、第３のレジスタ113及び第４のレジスタ114にそれぞれ格納して、記憶させている(ステップＳ７)。【００４８】
次いで、電子計算機10では、ＣＰＵ11を演算手段として機能させて(-2χ＋1)s3の値を演算し(ステップＳ８)、この値を第５のレジスタ115にそれぞれ格納して、記憶させている(ステップＳ９)。【００４９】
次いで、電子計算機10では、ＣＰＵ11を演算手段として機能させて、第１〜５のレジスタ11,112,113,114,115に記憶された値を用いて、s4＋s5の値及びs2−s5の値を演算している(ステップＳ１０)。【００５０】
演算されたs4＋s5の値及びs2−s5の値は、それぞれ所定のレジスタに格納して、記憶させている。説明の便宜上、s4＋s5＝Ａ、s2−s5＝Ｂとする。【００５１】
次いで、電子計算機10では、ＣＰＵ11を演算手段として機能させて、スカラ倍算[s]Ｐを、[s]Ｐ＝([Ａ]φ'2＋[Ｂ])Ｐとして演算している(ステップＳ１１)。ここで、Ａ及びＢの値の大きさが、スカラｓの大きさの半分程度となることにより、演算時間を大きく削減できる。コンピュータシミュレーションでは、一般的なバイナリ法でのスカラ倍算と比較して、40％程度の高速化が可能であった。【００５２】
なお、ステップＳ１１で行っている[s]Ｐ＝([Ａ]φ'2＋[Ｂ])Ｐの演算は、具体的には、以下のように行っている。【００５３】
ここで、電子計算機10には、スカラ演算[s]Ｐの演算結果を記憶する演算結果用レジスタＲと、演算に必要となる値を一時的に記憶しておく第１補助レジスタＣと第２補助レジスタＤとを設けている。【００５４】
まず、電子計算機10は、初期化処理として、演算結果用レジスタＲを零元とし、第１補助レジスタＣにφ'2(Ｐ)を代入し、第２補助レジスタＤに有理点Ｐを代入している。【００５５】
また、上記のＡとＢをそれぞれ２進数表示した際のｉ番目の桁の値をAiとBiと表示するものとして、電子計算機10では、ＡとＢの全桁にわたって以下の演算ループを実行することとしている。【００５６】
ｉ番目の桁において、Ai＝１かつBi＝１の場合には、演算結果用レジスタＲに、演算結果用レジスタＲと第２補助レジスタＤの和を代入する。すなわち、Ｒ←Ｒ＋Ｄである。【００５７】
ｉ番目の桁において、Ai＝１かつBi＝０の場合には、演算結果用レジスタＲに、演算結果用レジスタＲと第１補助レジスタＣの和を代入する。すなわち、Ｒ←Ｒ＋Ｃである。【００５８】
ｉ番目の桁において、Ai＝０かつBi＝１の場合には、演算結果用レジスタＲに、演算結果用レジスタＲと有理点Ｐの和を代入する。すなわち、Ｒ←Ｒ＋Ｐである。【００５９】
そして、演算結果用レジスタＲに、演算結果用レジスタＲと演算結果用レジスタＲの和を代入する。すなわち、Ｒ←Ｒ＋Ｒである。【００６０】
その後、電子計算機10は、デクリメントまたはインクリメントを行って、AiとBiの桁をずらしながらＡとＢの全桁にわたって演算を行うことによりスカラ演算[s]Ｐの演算を行って、演算結果を出力可能としている。【００６１】
本実施形態の演算では、ＡとＢとを同時進行で演算していることにより、ＡとＢの値の大きさが、スカラｓの大きさの半分程度となることのメリットを最大限利用することができる。【００６２】
次に、埋め込み次数ｋ＝8の場合について説明する。【００６３】
埋め込み次数ｋ＝8の場合、標数ｐ、位数ｒ、フロベニウス自己準同型写像のトレースｔが、
p(χ)＝(81χ6＋54χ5＋45χ4＋12χ3＋13χ2＋6χ＋1)/4，
r(χ)＝9χ4＋12χ3＋8χ2＋4χ＋1，
t(χ)＝−9χ3−3χ2−2χ，
として与えられるＢＮ曲線の有理点が成す加法群Ｅ(Ｆp)の有理点Ｐでのスカラ倍算[s]Ｐとする。【００６４】
この場合でも、部分体ツイスト曲線が存在することが知られている。特に、埋め込み次数ｋ＝8の場合には、４次のツイスト曲線が知られており、
[p2]Ｐ＝φ'2(Ｐ),
となるフロベニウス写像φ'2が知られている。【００６５】
また、埋め込み次数ｋ＝8の場合には、上述した式１４の代わりに、
[3χ2＋2χ]Ｐ＝[(-2χ−1)p2]Ｐ＝[-2χ−1]φ'2(Ｐ),  ・・・（式２４）
の関係式があることを利用している。【００６６】
そして、埋め込み次数ｋ＝12の場合と同様に、3χ2＋2χ＝νとして前記スカラｓをν進数展開すると、下式のように表すことができる。
ｓ＝s1ν＋s2,s2＜ν.  ・・・（式２５）【００６７】
ここで、式２４より、式２５は下式のように表すことができる。
ｓ≡(-2χ−1)s1p2＋s2 mod r.  ・・・（式２６）【００６８】
なお、(-2χ−1)s1はνより大きくなることがある。そこで、(-2χ−1)s1をさらにν進展開して下式のように表すこととする。
ｓ≡(s3ν＋s4)p2＋s2 mod r.  ・・・（式２７）【００６９】
ここで式２４によりs3νp2≡(-2χ−1)s3p4であるので、(-2χ−1)s3＝s5とすることにより、式２７は下式のように表すことができる。
ｓ≡s5p4＋s4p2＋s2 mod r.  ・・・（式２８）【００７０】
この場合、s4とs2はνよりも小さい一方で、s5はνより小さくないかもしれないが、そのような場合でもそれほど大きくなることはなく、問題となることはない。【００７１】
埋め込み次数ｋ＝8の場合、p4≡−1 mod rであることから、式２８は下式のように変形できる。
ｓ≡−s5＋s4p2＋s2≡s4p2＋(s2−s5) mod r.  ・・・（式２９）【００７２】
ここで、
Ａ＝s4,  ・・・（式３０）
Ｂ＝s2−s5,  ・・・（式３１）
とすると、スカラ倍算[s]Ｐは、埋め込み次数ｋ＝12の場合と同様に
[s]Ｐ＝([Ａ]φ'2＋[Ｂ])Ｐ,
として演算できる。【００７３】
したがって、埋め込み次数ｋ＝8の場合には、埋め込み次数ｋ＝12の場合と比較して、第５のレジスタ115に格納される値の計算式、及び式３０のＡの値が異なるだけであり、埋め込み次数ｋ＝12の場合と同様に演算できる。【００７４】
そこで、埋め込み次数ｋ＝8の場合におけるスカラ演算器は、埋め込み次数ｋ＝12の場合におけるスカラ演算器と同じとし、図２に示したフローチャートのステップＳ８での計算式を(-2χ−1)s3とし、ステップＳ９でs5の値を(-2χ−1)s3とし、ステップＳ１０でＡ＝s4としている。【００７５】
これにより、埋め込み次数ｋ＝8の場合でも、Ａ及びＢの値の大きさが、スカラｓの大きさの半分程度となることにより、スカラ倍算[s]Ｐの演算時間を大きく削減できる。
【産業上の利用可能性】
【００７６】
本発明によれば、グループ署名の演算中に必要となるスカラ演算の速度を向上させて、グループ署名の処理の高速化をはかることができる。
【図１】
0005403630.tif 000002
【図２】
0005403630.tif 000003