(57)【要約】【課題】  楕円曲線上で定義されるＴａｔｅペアリングの計算を行う際の演算負荷を軽減する。【解決手段】  （１）ｆ＝ｆ２ｇＶ，Ｖ（Ｑ）／ｇ２Ｖ（Ｑ）の計算の代わりに、ｌｇ２Ｖ（Ｑ）がペアリング演算の最後に行う（ｑ−１）／ｍ乗の過程で１となるｌを用いてｆ＝ｆ２ｇＶＶ（Ｑ）ｌを計算する。これにより逆元計算を削減することができる。（２）ｆ＝ｆｇＶ，Ｐ（Ｑ）／ｇＶ＋Ｐ（Ｑ）の計算の代わりに、ｌｇＶ＋Ｐ（Ｑ）がペアリング演算の最後に行う（ｑ−１）／ｍ乗の過程で１となるｌを用いてｆ＝ｆｇＶ，Ｐ（Ｑ）ｌを計算する。これにより逆元計算を削減することができる。（３）ｌの選択方法として、ｄをｄ｜ｋかつｄ＜ｋを満たす最大の整数、ｇＶ＋Ｐ（Ｑ）またはｇ２Ｖ（Ｑ）＝ｄ１ｘＱ＋ｄ０とした場合、  【数１】2005316267.tif 000011とする。【選択図】  図１
2005316267.tif 000002
【特許請求の範囲】
【請求項１】
有限体上の楕円曲線上で定義されるＴａｔｅペアリング演算装置であって、
楕円曲線パラメータおよび定義体情報として、
定義体Ｆｐ、Ｆｐのｋ次拡大体Ｆｑ（ｄをｄ｜ｋかつｄ＜ｋを満たす最大の整数としたときＦｐのｋ次拡大体Ｆｑは、Ｆｐのｋ／ｄ次拡大体としての構造を持つ）、
楕円曲線Ｅ：ｙ２＝ｘ３＋ａｘ＋ｂ、
以下の条件を満たすｍ「ｍはＥ（Ｆｐ）の位数＃Ｅ（Ｆｐ）を割り切る。ｍはｑ−１を割り切る。３．ｍはα＝１，２，．．．，ｋ−１に対してｐα−１を割り切らない」、
演算対象データとして、
ｍねじれ群Ｅ（Ｆｐ）［ｍ］の点Ｐ、
Ｅ（Ｆｑ）／ｍＥ（Ｆｑ）の点Ｑ
の入力を受け付ける入力データ受付手段と、
Ｔａｔｅペアリング演算ｅ（Ｐ，Ｑ）を行うペアリング演算手段と、
ペアリング演算結果を出力する出力手段とを備え、
前記ペアリング演算手段は、以下の処理を行なうことを特徴とするペアリング演算装置：
＜Ｓ１：ｍの２進展開＞
ｍの２進展開を行い、
ｍ＝ｍ０＋ｍ１２＋…＋ｍｒ２ｒ、ｍｊ∈｛０，１｝（０≦ｊ≦ｒ−１）、
ｍｒ≠０とおく。
＜Ｓ２：中間データｆおよびＶの初期化＞
ｆ＝１、Ｖ＝Ｑとおく。
＜Ｓ３：ｉの初期化＞
ｉ＝ｒ−１とおく。
＜Ｓ４：入力データＱのｘ座標に応じて最適な計算アルゴリズを選択＞
Ｑ＝（ｘＱ，ｙＱ）のｘ座標ｘＱがＦｑの部分群であるＦＰのｄ次拡大体の元かどうかを判定し、ｄ次拡大体の元であればＳ５に進み、そうでなければＳ２に進む。
＜Ｓ５：接線の方程式の計算、および、ｇＶ，Ｖ（Ｑ）の計算＞
ＶでＥ（Ｆｐ）と接する直線ｇＶ，Ｖ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、
ｇＶ，Ｖ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜Ｓ６：中間データｆの更新＞
ｆ＝ｆ２ｇＶ，Ｖ（Ｑ）を計算し、ｆの値を更新する。
＜Ｓ７：ｍｉの値による分岐＞
Ｖ＝２Ｖとおき、ｍｉ＝１であればＳ８に進み、ｍｉ＝０であればＳ１１に進む。
＜Ｓ８：２点を通る直線の計算、および、ｇＶ，Ｐ（Ｑ）の計算＞
ＶとＰとを通る直線ｇＶ，Ｐ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、
ｇＶ，Ｐ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜Ｓ９：中間データｆの更新＞
ｆ＝ｆｇＶ，Ｐ（Ｑ）を計算し、ｆの値を更新する。
＜Ｓ１０：Ｖの更新＞
Ｖ＝Ｖ＋Ｐとおく。
＜Ｓ１１：ｉの値による分岐＞
ｉ＝ｉ−１とおき、ｉ＝−１であればＳ２２に進み、異なればＳ６に進む。
＜Ｓ１２：従来例におけるｄに対してｄｈ（ｚ，ｗ）がべき乗の過程で１となるｈ（ｚ，ｗ）を求める際に用いる方程式ｈ（ｚ，ｗ）を求める＞
ｚ、ｗを変数とする多項式
【数１】
2005316267.tif 000010
を求める。
＜Ｓ１３：接線の方程式の計算、および、ｇＶ，Ｖ（Ｑ）の計算＞
ＶでＥ（Ｆｐ）と接する直線ｇＶ，Ｖ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、
ｇＶ，Ｖ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜Ｓ１４：２Ｖを通る垂線、および、従来例におけるｄに対してｄｈが（ｑ−１）／ｍ乗の過程で１となるｈを求める＞
２Ｖを通る垂線ｇ２Ｖ＝ｄ１ｘ＋ｄ０を求め、
垂線の係数ｄ、ｅを用いてｈ＝ｈ（ｄ１，ｄ０）を計算する。
＜Ｓ１５中間データｆの更新＞
ｆ＝ｆ２ｇＶ，Ｖ（Ｑ）ｈを計算し、ｆの値を更新する。
＜Ｓ１６：Ｖの更新、および、進みｍｉの値による分岐＞
Ｖ＝２Ｖとおき、ｍｉ＝１であればＳ１７に進み、ｍｉ＝０であればＳ２１に進む。
＜Ｓ１７：２点を通る直線の計算、および、ｇＶ，Ｐ（Ｑ）の計算＞
ＶとＰとを通る直線ｇＶ，Ｐ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、
ｇＶ，Ｐ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜Ｓ１８：Ｖ＋Ｐを通る垂線、および、従来例におけるｄに対して、ｄｈが（ｑ−１）／ｍ乗の過程で１になるｈを求める＞
Ｖ＋Ｐを通る垂線ｇＶ＋Ｐ＝ｄｘ＋ｅを求め、
垂線の係数ｄ、ｅを用いてｈ＝ｈ（ｄ，ｅ）を計算する。
＜Ｓ１９：中間データｆの更新＞
ｆ＝ｆｇＶ，Ｐ（Ｑ）ｈを計算し、ｆの値を更新する。
＜Ｓ２０：Ｖの更新＞
Ｖ＝Ｖ＋Ｐとおく。
＜Ｓ２１：ｉの値による分岐＞
ｉ＝ｉ−１とおき、ｉ＝−１であればＳ２２に進み、異なればＳ１３に進む。
＜Ｓ２２：べき乗の計算＞
ｅ＝ｆ（ｑ−１）／ｍを計算する。
【請求項２】
有限体上の楕円曲線上で定義されるＴａｔｅペアリング演算を行なう楕円曲線ペアリング演算装置であって、
演算対象となる楕円曲線および演算対象データの入力を受け付ける入力部と、
ペアリング演算を行なうペアリング演算部と、
演算結果を出力する出力部とを備え、
前記ペアリング演算部は、中間データを更新する際に逆元計算を行なわないことを特徴とするペアリング演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報セキュリティ技術としての暗号技術に関するものであり、特に、有限体上の楕円曲線を用いて定義されるＴａｔｅペアリングを用いて実現する任意の文字列を公開鍵として用いることが可能な公開鍵暗号およびデジタル署名技術において必要な楕円曲線ペアリング演算装置に関する。
【背景技術】
【０００２】
非特許文献１には、ｅ−ｍａｉｌアドレスのような特定の個人と結びつけられる文字列を公開鍵として用いることのできる公開鍵暗号方式として、ペアリングと呼ばれる双線形写像の性質を応用した方式が提案されている。
【０００３】
ここで、ペアリングの概要について説明する。位数がｑの２つの群をＧ１，Ｇ２とした時、Ｇ１×Ｇ１からＧ２への写像ｅで以下の性質を満たすものをペアリングと呼ぶ。
１．任意のＰ，Ｑ∈Ｇ１に対して、ｅはｅ（ａＰ，ｂＱ）＝ｅ（Ｐ，Ｑ）ａｂを満たす。
２．任意のＰ，Ｑ∈Ｇ１×Ｇ１に対して、ｅ（Ｐ，Ｑ）≠Ｇ２の単位元を満たす。
３．任意のＰ，Ｑ∈Ｇ１×Ｇ１に対して、ｅ（Ｐ，Ｑ）を計算する効率的なアルゴリズムが知られていること。
【０００４】
次に、非特許文献１で示されている公開鍵暗号方式について説明する。
【０００５】
この公開鍵暗号方式は、以下の（１）〜（４）の処理からなる。
（１）システムで共通に用いる群情報、ペアリング等を含む公開パラメータの生成処理、および、システムのユーザの秘密鍵を生成する際に必要となるマスター鍵の生成処理。
（２）ユーザのｅ−ｍａｉｌアドレス等のユーザと対応させることが可能な文字列である公開鍵に対して、マスター鍵を用いた秘密鍵の生成処理。
（３）公開パラメータおよびユーザの公開鍵を用いた暗号化処理。
（４）公開パラメータおよび秘密鍵を用いた復号処理。
【０００６】
なお、マスター鍵についてはシステム全体の安全性に関わるため、システムのユーザを含む外部に漏洩しないように厳重に保管する必要がある。
【０００７】
上記の各処理について説明を行う。
（１）公開パラメータおよびマスター鍵生成処理
入力：セキュリティパラメータ
出力：公開パラメータｐａｒａｍｓ、マスター鍵ｓ
１．セキュリティパラメータを用いて素数ｑ、位数がｑの２つの群Ｇ１、Ｇ２、ペアリングｅ：Ｇ１×Ｇ１→Ｇ２を生成し、Ｇ１の生成元Ｐを選択する。
２．ランダムにＺｑ＊の元ｓを選択し、Ｐｐｕｂ＝ｓＰとおく。
３．ハッシュ関数Ｈ１：｛０，１｝＊→Ｇ１＊を選択する。
４．ある整数ｎに対して、ハッシュ関数Ｈ２：Ｇ２→｛０，１｝ｎを選択する。
５．公開パラメータとして
ｐａｒａｍｓ＝＜ｑ，Ｇ１，Ｇ２，ｅ，ｎ，Ｐ，Ｐｐｕｂ，Ｈ１，Ｈ２＞、
マスター鍵としてｓを出力する。
（２）秘密鍵生成処理
入力：公開パラメータｐａｒａｍｓ、マスター鍵ｓ、公開鍵として用いる任意の文字列ＩＤ
出力：ＩＤに対応する秘密鍵ｄＩＤ
１．ＱＩＤ＝Ｈ１（ＩＤ）を計算する。
２．ｄＩＤ＝ｓＱＩＤを計算する。
３．秘密鍵としてｄＩＤを出力する。
（３）暗号化処理
入力：暗号化対象データＭ、公開パラメータをｐａｒａｍｓ、公開鍵ＩＤ
出力：暗号化データＣ＝（Ｃ１，Ｃ２）
１．ＱＩＤ＝Ｈ１（ＩＤ）∈Ｇ１＊を計算する。
２．ランダムにｒ∈Ｚｑ＊を選択する。
３．Ｃ１＝ｒＰを計算する。
４．ｇＩＤ＝ｅ（ＱＩＤ，Ｐｐｕｂ）を計算する。
５．ｈ＝Ｈ２（ｇＩＤｒ）を計算する。
６．
【０００８】
【数２】
2005316267.tif 000003
を計算する。
７．暗号化データＣ＝（Ｃ１，Ｃ２）を出力する。
（４）復号処理
入力：暗号化データＣ＝（Ｃ１，Ｃ２）、公開パラメータをｐａｒａｍｓ、秘密鍵ｄＩＤ
出力：復号データＭ
１．ｇ＝ｅ（ｄＩＤ，Ｃ１）を計算する。
２．ｈ＝Ｈ２（ｇ）を計算する。
３．
【０００９】
【数３】
2005316267.tif 000004
を計算する。
４．復号データＭを出力する。
【００１０】
上記各処理の手順で分かるように、ペアリングを用いた公開鍵暗号方式では、暗号化処理および復号処理においてペアリングの計算が必要となる。
【００１１】
非特許文献１では、ペアリングの例として楕円曲線上で定義されるＴａｔｅペアリングが示されている。
【００１２】
有限体Ｆｐ上の楕円曲線Ｅ（Ｆｐ）は、｛（ｘ，ｙ）∈Ｆｐ×Ｆｐ，ｙ２＝ｘ３＋ａｘ＋ｂ｝∪Ｏで定義され、Ｏを単位元として持つ群となる。楕円曲線上の異なる２点をＰ１＝（ｘ１，ｙ１）、Ｐ２＝（ｘ２，ｙ２）とした場合、楕円曲線上の加算Ｐ３＝Ｐ１＋Ｐ２＝（ｘ３，ｙ３）は、λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）を用いて、ｘ３＝λ２−ｘ１−ｘ２、ｙ３＝λ（ｘ１−ｘ３）−ｙ１で定義される。
【００１３】
また、２倍算Ｐ３＝２Ｐ１＝（ｘ３，ｙ３）は、λ＝（３ｘ１２＋ａ）／（２ｙ１）を用いて、ｘ３＝λ２−ｘ１−ｘ２、ｙ３＝λ（ｘ１−ｘ３）−ｙ１で定義される。
【００１４】
次に、楕円曲線上のＴａｔｅペアリングについて説明する。
【００１５】
有限体Ｆｐ上の楕円曲線をＥ（Ｆｐ）、ｍねじれ群Ｅ（Ｆｐ）［ｍ］をＥ（Ｆｐ）の点のうち、ｍ倍が楕円曲線上の単位元となる点集合とする。楕円曲線Ｅ（Ｆｐ）をＦｐのｋ次拡大体Ｆｑ上の楕円曲線とみなしたものをＥ（Ｆｑ）、そのｍねじれ群をＥ（Ｆｑ）［ｍ］とする。ただし、ｑはｑ＝ｐｋと表され、ｍおよびｋは、以下の条件を満たすものとする。
１．ｍは、Ｅ（Ｆｐ）の位数＃Ｅ（Ｆｐ）を割り切る。
２．ｍは、ｑ−１を割り切る。
３．ｍは、α＝１，２，．．．，ｋ−１に対してｐα−１を割り切らない。
【００１６】
このとき、Ｔａｔｅペアリングｅは、Ｅ（Ｆｑ）［ｍ］×Ｅ（Ｆｑ）／ｍＥ（Ｆｑ）からＦｑ＊／（Ｆｑ＊）ｍの写像で、Ｅ（Ｆｑ）［ｍ］の点Ｐ、単位元Ｏ、Ｅ（Ｆｑ）の点でＰの整数倍とはならない点Ｑに対してｍ（Ｐ）−ｍ（Ｏ）を因子として持つ関数ｆＰを用いてｅ（Ｐ，Ｑ）＝（ｆＰ（Ｑ））（ｑ−１）／ｍにより計算される。
【００１７】
非特許文献２には、Ｔａｔｅペアリングの具体的な計算方法が示されている。
【００１８】
楕円曲線上の２点Ｖ，Ｐを通る直線をｇＶ，Ｐ、Ｖで楕円曲線に接する接線をｇＶ，Ｖ、２Ｖを通る垂線をｇ２Ｖ、Ｖ＋Ｐを通る垂線をｇＶ＋Ｐとして、非特許文献２で示されている従来技術を説明する。
（従来技術）
入力：楕円曲線ｙ２＝ｘ３＋ａｘ＋ｂ、Ｐ∈Ｅ（Ｆｐ）［ｍ］、Ｑ∈ｍＥ（Ｆｑ）
出力：Ｔａｔｅペアリングｅ（Ｐ，Ｑ）
＜ステップ１＞
ｃ＝１、ｃ＝１、Ｖ＝Ｑとおく。
＜ステップ２＞
ｍの２進展開を行い、ｍ＝ｍ０＋ｍ１２＋…＋ｍｒ２ｒ、ｍｊ∈｛０，１｝（０≦ｊ≦ｒ−１）、ｍｒ≠０とおく。
＜ステップ３＞
ｉがｒ−１から０になるまで、以下の処理を繰り返す。
≪ステップ３．１≫
（１）ｃ＝ｃ２ｇＶ，Ｖ（Ｑ）とおく。
（２）ｄ＝ｄ２ｇ２Ｖ（Ｑ）とおく。
（３）Ｖ＝２Ｖとおく。
（４）ｍｉ＝１であれば３．２に進み異なればステップ３．３に進む。
≪ステップ３．２≫
（１）ｃ＝ｃｇＶ，Ｐ（Ｑ）とおく。
（２）ｄ＝ｄｇＶ＋Ｐ（Ｑ）とおく。
（３）Ｖ＝Ｖ＋Ｐとおく。
（４）ステップ３．３に進む。
≪ステップ３．３≫
ｉ＝ｉ−１とおく。
＜ステップ４＞
ｆ＝ｃ／ｄを計算する。
＜ステップ５＞
ｅ＝ｆ（ｑ−１）／ｍを計算する。
＜ステップ６＞
ｅを出力する。
【００１９】
さらに、非特許文献２には、ｄをｄ｜ｋかつｄ＜ｋを満たす最大の整数としたとき、Ｑのｘ座標がＦｐのｄ次拡大体の元であれば、≪ステップ３．１≫（２）、および、≪ステップ３．２≫（２）を削減可能であることが示されている。
【００２０】
【非特許文献１】D.Boneh, M.Franklin著「Identity-Based Encryption from the Weil PairingS」Springer-Verlag,2001年, Proceedings Asiacrypt 2001, Lecture Notes in Computer Science 2248,p-514-532
【非特許文献２】P.S.L.M.Barreto,B.Lynn,M.Scott著「On the Selection of Pairing-Friendly Groups」Springer-Verlag,2003年Selected Areas in Cryptograph SAC 2003, Lecture Notes in Computer Science
【発明の開示】
【発明が解決しようとする課題】
【００２１】
楕円曲線上で定義されるＴａｔｅペアリングを用いた公開鍵暗号方式では、ペアリング演算を行う演算装置が必須である。暗号化および復号の際のペアリング演算は負荷が大きいため、これを高速に行うことが望ましい。
【００２２】
従来技術で示したＴａｔｅペアリングの計算では、楕円曲線上の加算、２倍算を行うと同時にｆの値を更新していく必要があるが、この際、負荷の大きいＦｑ上の逆元計算を必ず行う必要がある。また、逆元計算の削減方法も示されているが、点Ｑに制限が加わるという欠点を持つ。
【００２３】
本発明は上述の問題点を踏まえて行われたもので、楕円曲線上で定義されるＴａｔｅペアリングの計算を行う際の演算負荷を軽減することを目的とする。
【課題を解決するための手段】
【００２４】
上記課題を解決するため、本発明によれば、
有限体上の楕円曲線上で定義されるＴａｔｅペアリング演算装置であって、
楕円曲線パラメータおよび定義体情報として、定義体Ｆｐ、Ｆｐのｋ次拡大体Ｆｑ（ｄをｄ｜ｋかつｄ＜ｋを満たす最大の整数としたときＦｐのｋ次拡大体Ｆｑは、Ｆｐのｋ／ｄ次拡大体としての構造を持つ）、楕円曲線Ｅ：ｙ２＝ｘ３＋ａｘ＋ｂ、以下の条件を満たすｍ「ｍはＥ（Ｆｐ）の位数＃Ｅ（Ｆｐ）を割り切る。ｍはｑ−１を割り切る。３．ｍはα＝１，２，．．．，ｋ−１に対してｐα−１を割り切らない」、演算対象データとして、ｍねじれ群Ｅ（Ｆｐ）［ｍ］の点Ｐ、Ｅ（Ｆｑ）／ｍＥ（Ｆｑ）の点Ｑの入力を受け付ける入力データ受付手段と、
Ｔａｔｅペアリング演算ｅ（Ｐ，Ｑ）を行うペアリング演算手段と、
ペアリング演算結果を出力する出力手段とを備え、
前記ペアリング演算手段は、以下の処理を行なうことを特徴とするペアリング演算装置：
＜Ｓ１：ｍの２進展開＞
ｍの２進展開を行い、ｍ＝ｍ０＋ｍ１２＋…＋ｍｒ２ｒ、ｍｊ∈｛０，１｝（０≦ｊ≦ｒ−１）、ｍｒ≠０とおく。
＜Ｓ２：中間データｆおよびＶの初期化＞
ｆ＝１、Ｖ＝Ｑとおく。
＜Ｓ３：ｉの初期化＞
ｉ＝ｒ−１とおく。
＜Ｓ４：入力データＱのｘ座標に応じて最適な計算アルゴリズを選択＞
Ｑ＝（ｘＱ，ｙＱ）のｘ座標ｘＱがＦｑの部分群であるＦＰのｄ次拡大体の元かどうかを判定し、ｄ次拡大体の元であればＳ５に進み、そうでなければＳ２に進む。
＜Ｓ５：接線の方程式の計算、および、ｇＶ，Ｖ（Ｑ）の計算＞
ＶでＥ（Ｆｐ）と接する直線ｇＶ，Ｖ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、ｇＶ，Ｖ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜Ｓ６：中間データｆの更新＞
ｆ＝ｆ２ｇＶ，Ｖ（Ｑ）を計算し、ｆの値を更新する。
＜Ｓ７：ｍｉの値による分岐＞
Ｖ＝２Ｖとおき、ｍｉ＝１であればＳ８に進み、ｍｉ＝０であればＳ１１に進む。
＜Ｓ８：２点を通る直線の計算、および、ｇＶ，Ｐ（Ｑ）の計算＞
ＶとＰとを通る直線ｇＶ，Ｐ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、ｇＶ，Ｐ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜Ｓ９：中間データｆの更新＞
ｆ＝ｆｇＶ，Ｐ（Ｑ）を計算し、ｆの値を更新する。
＜Ｓ１０：Ｖの更新＞
Ｖ＝Ｖ＋Ｐとおく。
＜Ｓ１１：ｉの値による分岐＞
ｉ＝ｉ−１とおき、ｉ＝−１であればＳ２２に進み、異なればＳ６に進む。
＜Ｓ１２：従来例におけるｄに対してｄｈ（ｚ，ｗ）がべき乗の過程で１となるｈ（ｚ，ｗ）を求める際に用いる方程式ｈ（ｚ，ｗ）を求める＞
ｚ、ｗを変数とする多項式
【００２５】
【数１】
2005316267.tif 000005
を求める。
＜Ｓ１３：接線の方程式の計算、および、ｇＶ，Ｖ（Ｑ）の計算＞
ＶでＥ（Ｆｐ）と接する直線ｇＶ，Ｖ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、ｇＶ，Ｖ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜Ｓ１４：２Ｖを通る垂線、および、従来例におけるｄに対してｄｈが（ｑ−１）／ｍ乗の過程で１となるｈを求める＞
２Ｖを通る垂線ｇ２Ｖ＝ｄ１ｘ＋ｄ０を求め、垂線の係数ｄ、ｅを用いてｈ＝ｈ（ｄ１，ｄ０）を計算する。
＜Ｓ１５中間データｆの更新＞
ｆ＝ｆ２ｇＶ，Ｖ（Ｑ）ｈを計算し、ｆの値を更新する。
＜Ｓ１６：Ｖの更新、および、進みｍｉの値による分岐＞
Ｖ＝２Ｖとおき、ｍｉ＝１であればＳ１７に進み、ｍｉ＝０であればＳ２１に進む。
＜Ｓ１７：２点を通る直線の計算、および、ｇＶ，Ｐ（Ｑ）の計算＞
ＶとＰとを通る直線ｇＶ，Ｐ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、ｇＶ，Ｐ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜Ｓ１８：Ｖ＋Ｐを通る垂線、および、従来例におけるｄに対して、ｄｈが（ｑ−１）／ｍ乗の過程で１になるｈを求める＞
Ｖ＋Ｐを通る垂線ｇＶ＋Ｐ＝ｄｘ＋ｅを求め、垂線の係数ｄ、ｅを用いてｈ＝ｈ（ｄ，ｅ）を計算する。
＜Ｓ１９：中間データｆの更新＞
ｆ＝ｆｇＶ，Ｐ（Ｑ）ｈを計算し、ｆの値を更新する。
＜Ｓ２０：Ｖの更新＞
Ｖ＝Ｖ＋Ｐとおく。
＜Ｓ２１：ｉの値による分岐＞
ｉ＝ｉ−１とおき、ｉ＝−１であればＳ２２に進み、異なればＳ１３に進む。
＜Ｓ２２：べき乗の計算＞
ｅ＝ｆ（ｑ−１）／ｍを計算する。
【００２６】
本発明では、（１）ｆ＝ｆ２ｇＶ，Ｖ（Ｑ）／ｇ２Ｖ（Ｑ）の計算の代わりに、ｌｇ２Ｖ（Ｑ）がペアリング演算の最後に行う（ｑ−１）／ｍ乗の過程で１となるｌを用いてｆ＝ｆ２ｇＶＶ（Ｑ）ｌを計算する。これにより逆元計算を削減することができる。
【００２７】
また、（２）ｆ＝ｆｇＶ，Ｐ（Ｑ）／ｇＶ＋Ｐ（Ｑ）の計算の代わりに、ｌｇＶ＋Ｐ（Ｑ）がペアリング演算の最後に行う（ｑ−１）／ｍ乗の過程で１となるｌを用いてｆ＝ｆｇＶ，Ｐ（Ｑ）ｌを計算する。これにより逆元計算を削減することができる。
【００２８】
さらに、（３）ｌの選択方法として、ｄをｄ｜ｋかつｄ＜ｋを満たす最大の整数、ｇＶ＋Ｐ（Ｑ）またはｇ２Ｖ（Ｑ）＝ｄ１ｘＱ＋ｄ０とした場合、
【００２９】
【数４】
2005316267.tif 000006
とする。
【００３０】
以上により、本発明では、点Ｑに制限を加えることなく、逆元計算を行わずに中間データｆを更新することが可能となる。これにより高速な暗号装置を提供することが可能となる。
【００３１】
すなわち、本発明によれば、上記従来技術で示したステップ３．１（２）およびステップ３．２（２）の削減効果がある。
【００３２】
ｄｈがステップ５のべき乗において１となるｈで、かつ乗算回数が０で計算できると仮定する。このとき本発明によりステップ３．１（２）およびステップ３．２（２）が削減され、ステップ３．１（１）およびステップ３．２（１）は以下のように修正される。
≪ステップ３．１≫
（１）ｃ＝ｈｃ２ｇＶ，Ｖ（Ｑ）とおく。
≪ステップ３．２≫
（１）ｃ＝ｈｃｇＶ，Ｐ（Ｑ）とおく。
この修正により、
１）ステップ３．１（１）での乗算回数が１回増加
２）ステップ３．２（１）での乗算回数が１回増加
３）ステップ３．１（２）での乗算回数２回削減
４）ステップ３．２（２）での乗算回数１回削減
よって、２倍算に関して乗算１回の削減効果が得られる。
【００３３】
次に具体例を用いて本発明の効果を説明する。Ｆｐ上（ｐ≡３  ｍｏｄ４）で定義される楕円曲線Ｅ（Ｆｐ）：ｙ２＝ｘ３＋ａｘを用いた場合、ｋ＝２となりＥ（Ｆｑ）上の点Ｑ＝（ｘＱ，ｙＱ）のｘ座標ｘＱは、ｉ２＝−１を満たすｉ、ｚ，ｗ∈Ｆｐを用いて、ｚ＋ｉｗと表すことができる。
【００３４】
このとき、ｌ＝（ｄ１ｘＱ＋ｄ０）Ｐ＝ｄｘＱＰ＋ｅ＝ｄ１（ｚ＋ｉｗ）Ｐ＋ｄ０＝ｄ１（ｚ−ｉｗ）＋ｄ０と計算できる。ｌの計算にかかる計算量は本来計算する必要のあるｄ１ｘＱ＋ｄ０の計算量と変わらないため、（ｄ１ｘＱ＋ｄ０）−１の代わりにｌを用いることにより計算量を増やすことなくＴａｔｅペアリングの計算速度に影響する逆元計算を削減できる。また、ｋ／ｄ＝２を満たす場合、同様にして逆元計算を、計算量の増加なしに削減することが可能となる。
【００３５】
本発明により高速な暗号化および復号を可能にする楕円曲線公開鍵暗号装置を実現することができるため、その実用的価値は大きい。
【発明を実施するための最良の形態】
【００３６】
本発明の実施の形態について図面を参照して説明する。
（楕円曲線ペアリング演算装置）
図１は、本発明を実現する楕円曲線ペアリング演算装置（以下、単に「演算装置」とも称する）１０１の機能構成を示すブロック図である。本図に示すように、演算装置１０１は、制御演算部１０２およびデータ保持部１０３を備えて構成される。
【００３７】
制御演算部１０２は、楕円曲線のパラメータ、定義体情報、演算対象データを入力し、演算結果としてＴａｔｅペアリングｅ（Ｐ，Ｑ）を出力する入出力部１０４、演算装置１０１全体を制御する制御部１０５、ペアリング演算を行うペアリング演算部１０６を備えて構成される。
【００３８】
データ保持部１０３は、入出力部１０４により入力された演算対象データである楕円曲線のｍねじれ群Ｅ（Ｆｐ）［ｍ］の点Ｐ、Ｅ（Ｆｑ）／ｍＥ（Ｆｑ）の点Ｑを保持する演算対象データ保持部１０７、楕円曲線のパラメータ、定義体情報を保持する楕円曲線情報保持部１０８、ペアリング演算部１０６で用いられる中間データを保持する中間データ保持部１０９、制御演算部１０２で計算された演算結果を保持する演算結果保持部１１０を備えて構成される。
【００３９】
次に、各々の動作は制御部１０５により制御されているものとして、動作の流れを説明する。
【００４０】
入出力部１０４により入力された演算対象データは、演算対象データ保持部１０７が保持する。また、入出力部１０４により入力された楕円曲線パラメータ、定義体情報は、楕円曲線情報保持部１０８が保持する。
【００４１】
次に、ペアリング演算部１０６が、演算対象データ保持部１０７および楕円曲線情報保持部１０８で保持されている情報を用いてペアリングを計算する。ペアリング演算における中間演算結果は、必要に応じて中間データ保持部１０９が保持する。なお、ペアリング演算は、図２に示すフローチャートに従って行われるものとする。
【００４２】
最後に、入出力部１０４が演算結果を出力する。
【００４３】
ここで、楕円曲線ペアリング演算装置１０１は、例えば、中央処理装置（ＣＰＵ）と、主記憶装置と、ハードディスク装置等の外部記憶装置と、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体からデータを読み取る読取装置と、キーボード、マウス等の入力装置と、ディスプレイ等の表示装置と、上述した各構成要素間のデータ送受信をつかさどるインタフェース等とを備えた、一般的な構成を有するサーバコンピュータ、パーソナルコンピュータ等の情報処理装置を用いて構成することができる。もちろん、これに限られない。例えば、楕円曲線ペアリング演算のための専用装置として構成することもできる。
【００４４】
楕円曲線ペアリング演算装置１０１の各処理部は、メモリにロードされたプログラムをＣＰＵが実行することで、情報処理装置上に具現化されるプロセスとして実現される。また、メモリあるいは外部記憶装置がデータ保持部１０３の各保持部１０７〜１１０として使用される。
【００４５】
また、情報処理装置を楕円曲線ペアリング演算装置１０１として機能させるためのプログラムは、例えば、ハードディスク等の外部記憶装置に格納することができる。また、これらのプログラムはＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体に記録されることで市場に流通することが可能である。記憶媒体に記録されたプログラムは、読取装置を介して読み込ませることにより、情報処理装置にインストールすることができる。また、通信回線を通じて情報処理装置に読み込ませるようにすることができる。
【００４６】
次に、図２のフロー図を参照して、楕円曲線ペアリング演算装置１０１のペアリング演算部１０６におけるペアリング演算処理を詳細に説明する。
＜ステップ２０１＞
楕円曲線の情報として定義体Ｆｐ、Ｆｐのｋ次拡大体Ｆｑ、
楕円曲線Ｅ：ｙ２＝ｘ３＋ａｘ＋ｂ、
以下の条件を満たすｍを入力する。
１．ｍはＥ（Ｆｐ）の位数＃Ｅ（Ｆｐ）を割り切る。
２．ｍはｑ−１を割り切る。
３．ｍはα＝１，２，．．．，ｋ−１に対してｐα−１を割り切らない。
【００４７】
また、ｄをｄ｜ｋかつｄ＜ｋを満たす最大の整数としたときＦｐのｋ次拡大体Ｆｑは、Ｆｐのｋ／ｄ次拡大体としての構造を持つものとする。
＜ステップ２０２＞
演算対象データとしてｍねじれ群Ｅ（Ｆｐ）［ｍ］の点Ｐ、
Ｅ（Ｆｑ）／ｍＥ（Ｆｑ）の点Ｑを入力する。
＜ステップ２０３＞
Ｔａｔｅペアリングｅ（Ｐ，Ｑ）を計算する。
＜ステップ２０４＞
演算結果ｅ（Ｐ，Ｑ）を出力する。
【００４８】
ここで、上記ステップ２０３、すなわち、ペアリング演算部１０６におけるＴａｔｅペアリングｅ（Ｐ，Ｑ）の計算を、図３に示すフロー図を参照して詳細に説明する。
＜ステップ３０１：ｍの２進展開＞
ｍの２進展開を行い、
ｍ＝ｍ０＋ｍ１２＋…＋ｍｒ２ｒ、ｍｊ∈｛０，１｝（０≦ｊ≦ｒ−１）、
ｍｒ≠０とおく。
＜ステップ３０２：中間データｆおよびＶの初期化＞
ｆ＝１、Ｖ＝Ｑとおく。
＜ステップ３０３：ｉの初期化＞
ｉ＝ｒ−１とおく。
＜ステップ３０４：入力データＱのｘ座標に応じて最適な計算アルゴリズを選択＞
Ｑ＝（ｘＱ，ｙＱ）のｘ座標ｘＱがＦｑの部分群であるＦＰのｄ次拡大体の元かどうかを判定し、ｄ次拡大体の元であればステップ３０５に進み、そうでなければステップ３１２に進む。
＜ステップ３０５：接線の方程式の計算、および、ｇＶ，Ｖ（Ｑ）の計算＞
ＶでＥ（Ｆｐ）と接する直線ｇＶ，Ｖ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、
ｇＶ，Ｖ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜ステップ３０６：中間データｆの更新＞
ｆ＝ｆ２ｇＶ，Ｖ（Ｑ）を計算し、ｆの値を更新する。
＜ステップ３０７：ｍｉの値による分岐＞
Ｖ＝２Ｖとおき、ｍｉ＝１であればステップ３０８に進み、ｍｉ＝０であればステップ３１１に進む。
＜ステップ３０８：２点を通る直線の計算、および、ｇＶ，Ｐ（Ｑ）の計算＞
ＶとＰとを通る直線ｇＶ，Ｐ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、
ｇＶ，Ｐ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜ステップ３０９：中間データｆの更新＞
ｆ＝ｆｇＶ，Ｐ（Ｑ）を計算し、ｆの値を更新する。
＜ステップ３１０：Ｖの更新＞
Ｖ＝Ｖ＋Ｐとおく。
＜ステップ３１１：ｉの値による分岐＞
ｉ＝ｉ−１とおき、ｉ＝−１であればステップ３２２に進み、異なればステップ３０６に進む。
＜ステップ３１２：従来例におけるｄに対してｄｈ（ｚ，ｗ）がべき乗の過程で１となるｈ（ｚ，ｗ）を求める際に用いる方程式ｈ（ｚ，ｗ）を求める＞
ｚ、ｗを変数とする多項式
【００４９】
【数１】
2005316267.tif 000007
を求める。
＜ステップ３１３：接線の方程式の計算、および、ｇＶ，Ｖ（Ｑ）の計算＞
ＶでＥ（Ｆｐ）と接する直線ｇＶ，Ｖ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、
ｇＶ，Ｖ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜ステップ３１４：２Ｖを通る垂線、および、従来例におけるｄに対してｄｈが（ｑ−１）／ｍ乗の過程で１となるｈを求める＞
２Ｖを通る垂線ｇ２Ｖ＝ｄ１ｘ＋ｄ０を求め、垂線の係数ｄ、ｅを用いて
ｈ＝ｈ（ｄ１，ｄ０）を計算する。
＜ステップ３１５中間データｆの更新＞
ｆ＝ｆ２ｇＶ，Ｖ（Ｑ）ｈを計算し、ｆの値を更新する。
＜ステップ３１６：Ｖの更新、および、進みｍｉの値による分岐＞
Ｖ＝２Ｖとおき、ｍｉ＝１であればステップ３１７に進み、ｍｉ＝０であればステップ３２１に進む。
＜ステップ３１７：２点を通る直線の計算、および、ｇＶ，Ｐ（Ｑ）の計算＞
ＶとＰとを通る直線ｇＶ，Ｐ＝ｃ０＋ｃ１ｘ＋ｃ２ｙを求め、
ｇＶ，Ｐ（Ｑ）＝ｃ０＋ｃ１ｘＱ＋ｃ２ｙＱを計算する。
＜ステップ３１８：Ｖ＋Ｐを通る垂線、および、従来例におけるｄに対して、ｄｈが（ｑ−１）／ｍ乗の過程で１になるｈを求める＞
Ｖ＋Ｐを通る垂線ｇＶ＋Ｐ＝ｄｘ＋ｅを求め、
垂線の係数ｄ、ｅを用いてｈ＝ｈ（ｄ，ｅ）を計算する。
＜ステップ３１９：中間データｆの更新＞
ｆ＝ｆｇＶ，Ｐ（Ｑ）ｈを計算し、ｆの値を更新する。
＜ステップ３２０：Ｖの更新＞
Ｖ＝Ｖ＋Ｐとおく。
＜ステップ３２１：ｉの値による分岐＞
ｉ＝ｉ−１とおき、ｉ＝−１であればステップ３２２に進み、異なればステップ３１３に進む。
＜ステップ３２２：べき乗の計算＞
ｅ＝ｆ（ｑ−１）／ｍを計算する。
＜ステップ３２３：計算結果の出力＞
ｅを出力する。
（公開パラメータおよびマスター鍵生成装置）
次に、公開鍵暗号を構成する際必要となる公開パラメータおよびマスター鍵を生成する装置について図４を参照して説明する。
【００５０】
図４は公開パラメータおよびマスター鍵生成装置（以下、単に「鍵生成装置」とも称する）の構成を示すブロック図である。本図に示すように、鍵生成装置４０１は、制御演算部４０２およびデータ保持部４０３を備えて構成される。
【００５１】
制御演算部４０２は、セキュリティパラメータを入力し、生成された公開パラメータおよびマスター鍵を出力する入出力部４０４、公開パラメータおよびマスター鍵生成装置４０１全体を制御する制御部４０５、楕円曲線の生成、ｍねじれ群および点Ｐを選択する楕円曲線生成部４０７、乱数を生成する乱数生成部４０８、マスター鍵を生成するマスター鍵生成部４０９、楕円曲線上の点の整数倍を計算する楕円曲線スカラー倍演算部４１０、ハッシュ関数を生成するハッシュ関数選択部４１１を備えて構成される。
【００５２】
データ保持部４０３は入出力部により入力された楕円曲線のパラメータ、ベースポイント及びその位数、定義体情報を保持する楕円曲線情報保持部４０８、制御演算部で生成されたマスター鍵を保持するマスター鍵保持部４１４、制御演算部で生成された公開パラメータを保持する公開パラメータ保持部４１５を備えて構成される。
【００５３】
以下に、各々の動作は制御部４０５により制御されているものとして動作の流れを説明する。
１）入出力部４０４により入力された情報は入力情報保持部４１２に保持される。
２）パラメータ生成部４０６において入力情報保持部４１２、ハッシュ情報保持部４１３で保持されている情報を用いて公開パラメータおよびマスター鍵生成処理を行い、公開パラメータおよびマスター鍵を生成する。公開パラメータおよびマスター鍵生成処理は図５に示すフロー図にしたがって行われるものとする。
３）マスター鍵ｓをマスター鍵保持部４１４において保持する。
４）公開パラメータ
ｐａｒａｍｓ＝＜ｍ，Ｅ（Ｆｑ）［ｍ］，Ｆｑ，ｎ，Ｐ，Ｐｐｕｂ，Ｈ１，Ｈ２＞
を公開パラメータ保持部４１５において保持する。
５）公開パラメータおよびマスター鍵生成装置４０１は入出力部４０４により公開パラメータｐａｒａｍｓおよびマスター鍵ｓを出力する。
【００５４】
次に、図５のフロー図を参照して、図４に示したパラメータ生成部５０６で行われる公開パラメータおよびマスター鍵生成処理の流れを説明する。
＜ステップ５０１＞
楕円曲線Ｅ（Ｆｐ）を生成し、ｍねじれ群Ｅ（Ｆｑ）［ｍ］およびその元
ｑ∈Ｅ（Ｆｇ）［ｍ］＼Ｅ（Ｆｇ）［ｍ］
を選択する。
＜ステップ５０２＞
ランダムにマスター鍵ｓ∈Ｚｍ＊を生成する。
＜ステップ５０３＞
Ｐｐｕｂ＝ｓＰを計算する。
＜ステップ５０４＞
ハッシュ関数Ｈ１：｛０，１｝＊→Ｅ（Ｆｐ）［ｍ］を選択する。
＜ステップ５０５＞
整数ｎに対して、ハッシュ関数Ｈ２：Ｆｑ→｛０，１｝ｎを選択する。
＜ステップ５０６＞
マスター鍵ｓを出力する。
＜ステップ５０７＞
公開パラメータ
ｐａｒａｍｓ＝＜ｍ，Ｅ（Ｆｑ）［ｍ］，Ｆｑ，ｎ，Ｐ，Ｐｐｕｂ，Ｈ１，Ｈ２＞
を出力する。
（秘密鍵生成装置）
次に、秘密鍵生成装置について図６を参照して説明する。
【００５５】
図６は秘密鍵生成装置の構成を示すブロック図である。本図に示すように、秘密鍵生成装置６０１は、制御演算部６０２およびデータ保持部６０３を備えて構成される。
【００５６】
制御演算部６０２は、公開パラメータｐａｒａｍｓおよびマスター鍵ｓ、任意の文字列である公開鍵ＩＤを入力し、ＩＤに対応する秘密鍵を出力する入出力部６０４、秘密鍵生成装置６０１全体を制御する制御部６０５、秘密鍵生成処理を行う秘密鍵生成部６０６、また秘密鍵生成部は公開パラメータで指定されているハッシュ関数Ｈ１を用いてハッシュ値を生成するハッシュ値生成部６０７、楕円曲線上の点の整数倍を計算する楕円曲線スカラー倍演算部６０８を備えて構成される。
【００５７】
データ保持部６０３は、入出力部６０４により入力された公開鍵ＩＤを保持する公開鍵情報保持部６０９、同様に入出力部により入力された公開パラメータｐａｒａｍｓを保持する公開パラメータ保持部６１０、秘密鍵生成に用いるマスター鍵ｓを保持するマスター鍵保持部６１１、秘密鍵生成部６０６で生成された秘密鍵を保持する秘密鍵保持部６１２を備えて構成される。
【００５８】
次に各々の動作は制御部６０５により制御されているものとして動作の流れを説明する。
１）入出力部６０４により入力された公開鍵は公開鍵保持部６０９に保持される。
２）入出力部６０４により入力された公開パラメータｐａｒａｍｓは公開パラメータ保持部６１０に保持される。
３）入出力部６０４により入力されたマスター鍵ｓはマスター鍵情報保持部６１１に保持される。
４）秘密鍵生成部６０６において、公開鍵保持部６０９、公開パラメータ保持部６１０、マスター鍵保持部６１１で保持されている情報を用いて秘密鍵生成処理を行い秘密鍵を生成する。秘密鍵生成処理は図７に示すフロー図にしたがって行われるものとする。
５）秘密鍵生成部６０６で作成された秘密鍵を秘密鍵保持部６１２に保持するとともに入出力部６０４より出力する。
【００５９】
次に、図７のフロー図を参照して、図６に示した秘密鍵生成部６０６で行われる秘密鍵生成処理の流れを説明する。以下では、公開鍵をＩＤ、マスター鍵をｓとして説明を行う。
＜ステップ７０１＞
ＱＩＤ＝Ｈ１（ＩＤ）を計算する。
＜ステップ７０２＞
ｄＩＤ＝ｓＱＩＤを計算する。
＜ステップ７０３＞
ｄＩＤを秘密鍵として出力する。
（暗号化装置）
次に、本発明を適用した暗号化装置について図８を参照して説明する。
【００６０】
図８は、暗号化装置の構成を示すブロック図である。本図に示すように、暗号化装置８０１は、制御演算部８０２およびデータ保持部８０３を備えて構成される。
【００６１】
なお、図示していないが、暗号化装置は、生成した暗号化データをコンピュータネットワーク等に送信するための通信部を備えている。
【００６２】
制御演算部８０２は、公開鍵、公開パラメータ、暗号化対象データを入力し、暗号化データを出力する入出力部８０４、暗号化装置８０１全体を制御する制御部８０５、暗号化を行う暗号化部８０６を備え、暗号化部８０６は、ハッシュ値生成部８０７、乱数を生成する乱数生成部８０８、楕円曲線上の点のスカラー倍を行う楕円曲線スカラー倍演算部８０９、楕円曲線上のＴａｔｅペアリングを計算するペアリング演算部８１０、および、排他的論理和を行う排他的論理和演算部８１１を備えて構成される。
【００６３】
データ保持部８０３は、入出力部８０４により入力された公開鍵を保持する公開鍵保持部８１２、入出力部８０４により入力された公開パラメータを保持する公開パラメータ保持部８１３、入出力部８０４により入力された暗号化対象データを保持する暗号化対象データ保持部８１４、暗号化部８０６において生成された暗号化データを保持する暗号化データ保持部８１４を備えて構成される。
【００６４】
以下に、各々の動作は制御部８０５により制御されているものとして動作の流れを説明する。
１）入出力部８０４により入力された公開鍵は公開鍵保持部８１２に保持される。
２）入出力部８０４により入力された公開パラメータは公開パラメータ保持部８１３に保持される。
３）入出力部８０４により入力された暗号化対象データは暗号化対象データ保持部８１４に保持される。
４）暗号化部８０６において、公開鍵保持部８１２、公開パラメータ保持部８１３、暗号化対象データ保持部８１４で保持されている情報を用いて暗号化処理を行い暗号化データを生成する。暗号化処理は図９に示すフロー図にしたがって行われるものとする。
５）暗号化部８０６において暗号化された暗号化データを暗号化データ保持部８１５に保持するとともに入出力部８０４より出力する。
【００６５】
次に、図９のフロー図を参照して、図８に示した暗号化部８０６で行われる暗号化処理の流れを説明する。以下では、公開鍵をＩＤ、暗号化対象データをＭとして説明を行う。
＜ステップ９０１＞
ＱＩＤ＝Ｈ１（ＩＤ）を計算する。
＜ステップ９０２＞
ランダムにｒを選択する。
＜ステップ９０３＞
Ｃ１＝ｒＰを計算する。
＜ステップ９０４＞
ｇＩＤ＝ｅ（ＱＩＤ，Ｐｐｕｂ）を計算する。
＜ステップ９０５＞
ｈ＝Ｈ２（ｇＩＤｒ）を計算する。
＜ステップ９０６＞
【００６６】
【数２】
2005316267.tif 000008
を計算する。
＜ステップ９０７＞
暗号化データＣ＝（Ｃ１，Ｃ２）を出力する。
（復号装置）
次に、本発明を適用した復号装置について図１０を参照して説明する。
【００６７】
図１０は復号装置の構成を示すブロック図である。本図に示すように、復号装置１００１は、制御演算部１００２およびデータ保持部１００３を備えて構成される。
【００６８】
なお、図示していないが、復号装置は、暗号化データをコンピュータネットワーク等から受信するための通信部を備えている。
【００６９】
制御演算部１００２は、秘密鍵、公開パラメータ、復号対象データを入力し、復号データを出力する入出力部１００４、復号装置１００１全体を制御する制御部１００５、復号を行う復号部１００６、また復号部はハッシュ値生成部１００７、楕円曲線上の点のスカラー倍を行う楕円曲線スカラー倍演算部１００８、楕円曲線上のＴａｔｅペアリングを計算するペアリング演算部１００９、および、排他的論理和を行う排他的論理和演算部１０１０を備えて構成される。
【００７０】
データ保持部１００３は入出力部１００４により入力された秘密鍵を保持する秘密鍵保持部１０１１、入出力部１００４により入力された公開パラメータを保持する公開パラメータ保持部１０１２、入出力部１００４により入力された復号対象データを保持する復号対象データ保持部１０１３、復号部１００６において復号された復号データを保持する復号データ保持部１０１４を備えて構成される。
【００７１】
以下に、各々の動作は制御部１００５により制御されているものとして動作の流れを説明する。
１）入出力部１００４により入力された秘密鍵は秘密鍵保持部１０１１に保持される。
２）入出力部１００４により入力された公開パラメータは公開パラメータ保持部１０１２に保持される。
３）入出力部１００４により入力された復号対象データは復号対象データ保持部１０１３に保持される。
４）復号部において秘密鍵保持部１０１１、公開パラメータ保持部１０１２、暗号化データ保持部１０１３で保持されている情報を用いて復号処理を行い復号結果を生成する。復号処理は図１１に示すフロー図にしたがって行われるものとする。
５）復号部１００６において復号された復号データを復号データ保持部１０１４に保持するとともに入出力部１００４より出力する。
【００７２】
次に、図１１のフロー図を参照して図１０に示した復号部１００６で行われる復号処理の流れを説明する。以下では、秘密鍵をｄＩＤ、復号対象データをＣ＝（Ｃ１，Ｃ２）として説明を行う。
＜ステップ１１０１＞
ｇ＝ｅ（ｄＩＤ，Ｃ１）を計算する。
＜ステップ１１０２＞
ｈ＝Ｈ２（ｇ）を計算する。
＜ステップ１１０３＞
【００７３】
【数３】
2005316267.tif 000009
を計算する。
＜ステップ１１０４＞
Ｍを出力する。
【図面の簡単な説明】
【００７４】
【図１】本発明のシステム機能構成を示すブロック図である。
【図２】本発明の動作を説明するフロー図である。
【図３】本発明による楕円曲線上のペアリング演算動作を説明するフロー図である。
【図４】公開パラメータおよびマスター鍵生成装置の構成を示すブロック図である。
【図５】公開パラメータおよびマスター鍵生成装置の動作を説明するフロー図である。
【図６】秘密鍵生成装置の構成を示すブロック図である。
【図７】本発明を用いた秘密鍵生成装置の動作を説明するフロー図である。
【図８】本発明を用いた暗号化装置の構成を示すブロック図である。
【図９】本発明を用いた暗号化装置の動作を説明するフロー図である。
【図１０】本発明を用いた復号装置の構成を示すブロック図である。
【図１１】本発明を用いた復号装置の動作を説明するフロー図である。。
【符号の説明】
【００７５】
１０１…楕円曲線ペアリング演算装置、１０２…制御演算部、１０３…データ保持部、１０４…入出力部、１０５…制御部、１０６…ペアリング演算部、１０７…演算対象データ保持部、１０８…楕円曲線情報保持部、１０９…中間データ保持部、１１０…演算結果保持部
４０１…公開パラメータおよびマスター鍵生成装置、４０２…制御演算部、４０３…データ保持部、４０４…入出力部、４０５…制御部、４０６…パラメータ生成部、４０７…楕円曲線生成部、４０８…乱数生成部、４０９…マスター鍵生成部、４１０…楕円曲線スカラー倍演算部、４１１…ハッシュ関数選択部、４１２…入力情報保持部、４１３…ハッシュ情報保持部、４１４…マスター鍵保持部、４１５…公開パラメータ保持部
６０１…秘密鍵生成装置、６０２…制御演算部、６０３…データ保持部、６０４…入出力部、６０５…制御部、６０６…秘密鍵生成部、６０７…ハッシュ演算部、６０８…楕円曲線スカラー倍演算部、６０９…公開鍵保持部、６１０…公開パラメータ保持部、６１１…マスター鍵保持部、６１３…秘密鍵保持部
８０１…暗号化装置、８０２…制御演算部、８０３…データ保持部、８０４…入出力部、８０５…制御部、８０６…暗号化部、８０７…ハッシュ値生成部、８０８…乱数生成部、８０９…楕円曲線スカラー倍演算部、８１０…ペアリング演算部、８１１…排他的論理和演算部、８１２…公開鍵保持部、８１３…公開パラメータ保持部、８１４…暗号化対象データ保持部、８１５…暗号化データ保持部
１００１…復号装置、１００２…制御演算部、１００３…データ保持部、１００４…入出力部、１００５…制御部、１００６…復号部、１００７…ハッシュ値生成部、１００８…楕円曲線スカラー倍演算部、１００９…ペアリング演算部、１０１０…排他的論理和演算部、１０１１…秘密鍵保持部、１０１２…公開パラメータ保持部、１０１３…復号対象データ保持部、１０１４…復号データ保持部
【図１】
2005316267.tif 000012
【図２】
2005316267.tif 000013
【図３】
2005316267.tif 000014
【図４】
2005316267.tif 000015
【図５】
2005316267.tif 000016
【図６】
2005316267.tif 000017
【図７】
2005316267.tif 000018
【図８】
2005316267.tif 000019
【図９】
2005316267.tif 000020
【図１０】
2005316267.tif 000021
【図１１】
2005316267.tif 000022