楕円曲線暗号におけるスカラー倍算計算方法、プログラム、及び装置
【課題】楕円曲線上の整数倍算とは異なる自己準同型写像Φを実行することができる楕円曲線を用いたスカラー倍計算装置において、高速性に優れた楕円曲線スカラー倍計算方法、プログラム、及び装置を提供する。
【解決手段】特性多項式Φ2+Φ+q（ｑは奇素数のべき）を持つ、定義体Fq上定義された楕円曲線上の整数倍算とは異なる自己準同型写像Φを実行することができる楕円曲線上の点とスカラー値からスカラー倍点を計算するスカラー倍計算装置において、スカラー値から第一の数値列であるΦ進展開を計算し、上記スカラー値のΦ進展開における隣り合う2桁を見て、予め定められた条件を満たさない場合に、前記2桁、及び、前記2桁と隣り合う1桁、または2桁のそれぞれに対して演算を行うことによって、スカラー値から第二の数値列を計算し、前記第二の数値列、及び、前記楕円曲線上の点とからスカラー倍計算を実行する。
【解決手段】特性多項式Φ2+Φ+q（ｑは奇素数のべき）を持つ、定義体Fq上定義された楕円曲線上の整数倍算とは異なる自己準同型写像Φを実行することができる楕円曲線上の点とスカラー値からスカラー倍点を計算するスカラー倍計算装置において、スカラー値から第一の数値列であるΦ進展開を計算し、上記スカラー値のΦ進展開における隣り合う2桁を見て、予め定められた条件を満たさない場合に、前記2桁、及び、前記2桁と隣り合う1桁、または2桁のそれぞれに対して演算を行うことによって、スカラー値から第二の数値列を計算し、前記第二の数値列、及び、前記楕円曲線上の点とからスカラー倍計算を実行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュリティ技術に係り、特に楕円曲線演算を用いたメッセージ処理技術に関する。
【背景技術】
【０００２】
楕円曲線暗号はN.Koblitz、V. S. Millerにより提案された公開鍵暗号の一種である。公開鍵暗号には、公開鍵（Public Key）と呼ばれる一般に公開してよい情報と、秘密鍵（Private Key）と呼ばれる秘匿しなければならない秘密情報がある。与えられたメッセージの暗号化や署名の検証には公開鍵を用い、与えられたメッセージの復号化や署名の生成には秘密鍵を用いる。
【０００３】
楕円曲線暗号における秘密鍵は、スカラー値が担っている。また、楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Pとそのスカラー倍の点dPが与えられた時、スカラー値dを求める問題である。楕円曲線上の点とは、楕円曲線の定義方程式を満たす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（乃至は加算）が定義される。そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の2倍算という。
【０００４】
楕円曲線上の2点の加法は次のようにして計算される。2点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とx軸に関して対称な点を、加法を行った結果の点とする。
【０００５】
例えば、ワイエルシュトラス型楕円曲線（以後、楕円曲線Eと呼ぶ。）の場合には、点（x1，y1）と点（x2，y2）とを加算した結果の点（x3，y3）（（x3，y3）=（x1，y1）+（x2，y2））は、
x3=λ2-x1-x2 （式1）
y3=（x1-x3）λ-y1 （式2）
λ=（y2-y1）/（x2-x1） （式3）
を計算することにより得られる。
【０００６】
ここで、楕円曲線Eの定義方程式は、
y2=x3+ax+b，（a，bはともに有限体Fqの元） （式4）
で与えられる。なお、点（x1，y1）と点（x2，y2）と点（x3，y3）はいずれも楕円曲線E上にある。すなわち、（式4）のx，yに各々xi，yi（i=1，2，3）を代入しても、（式4）の等式は成り立つ。
【０００７】
また、有限体Fqは（式4）で与えられる楕円曲線Eの定義体と呼ばれる。ここで、qは正の整数である。
【０００８】
以後、正の整数qは、ある自然数rを用いて、
q=pr （式5）
と表されるものとする。ここで、pは3以上の素数である。
【０００９】
また、以後、楕円曲線暗号に用いる可換群としてE（Fqm）を考える。
【００１０】
ただし、E（Fqm）は、（式4）の定義方程式で与えられる楕円曲線であり、楕円曲線上の各点P=（x，y）に対して、x，yがともにFqmの元であることを意味し、mは拡大次数と呼ばれる自然数である。
【００１１】
楕円曲線上の点の2倍算は次のようにして計算される。楕円曲線上の点における接線をひくと、その接線は楕円曲線上の他の一点において交わる。その交わった点とx座標に関して対称な点を、2倍算を行った結果の点とする。例えば、楕円曲線Eの場合には、点（x1，y1）の2倍算を行った結果の点（x3，y3）（（x3，y3）=2（x1，y1）=（x1，y1）+（x1，y1））は、（式1）、（式2）及び
λ=（3x12+a）/2y1 （式6）
を計算することにより得られる。
【００１２】
また、楕円曲線E上の点に対して、フロベニウス写像Φと呼ばれる自己準同型写像を施すことが可能である。点（x1，y1）に対してフロベニウス写像Φを施すとは、
Φ（x1，y1）=（x1q，y1q） （式7）
を計算することである。また、
（x2q，x2q）+q（x，y）=t（xq，yq） （式8）
が成り立つことが知られており、（式8）の性質によりΦを、
Φ2+q=tΦ （式9）
を満たす複素数と考えることができる。ここで、tは（式4）で与えられる楕円曲線Eのトレースと呼ばれる整数である。以下、トレースtは-1とする。
【００１３】
ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果の点をスカラー倍点、その回数のことをスカラー値という。
【００１４】
楕円曲線暗号においては、与えられたメッセージの暗号化、復号化、署名の生成、及び、その検証は、楕円曲線演算を用いて行う。その中で楕円曲線上のスカラー倍の計算は、上記の暗号化、復号化等の各処理において最も計算時間を要する計算である。そのため、楕円曲線暗号を高速に実行するためには、楕円曲線上のスカラー倍計算を高速に行う必要がある。
【００１５】
一般に楕円曲線上のスカラー倍計算では、エンコードされたスカラー値の各桁を見て、零でない（非零）場合に楕円曲線上の加算を行い、桁をずらすために楕円曲線上の2倍算を行う。ここで、スカラー値のエンコードとは、スカラー値の表現を小さな数値列に変換すること（以後、Φ進展開と呼ぶ。）である。ところが、楕円曲線上の2倍算は、楕円曲線上の加算、整数倍算とは異なる自己準同型写像と比べて処理が重い。
【００１６】
これに対し、整数倍算とは異なる自己準同型写像を実行することができる楕円曲線上のスカラー倍計算では、桁をずらすために楕円曲線上の2倍算を行う代わりに整数倍算とは異なる自己準同型写像を用いることができることが知られている。整数倍算とは異なる自己準同型写像は、楕円曲線暗号実装の際に、楕円曲線上の点を、正規基底を用いて実装した場合、シフト演算のみを用いて計算でき、2倍算に比べて処理が高速である。
【００１７】
従って、楕円曲線暗号実装の際に楕円曲線として、整数倍算とは異なる自己準同型写像を持つ楕円曲線を採用すれば、スカラー倍計算の高速化が可能となる。
【００１８】
この性質を利用して、楕円曲線上のスカラー倍計算を高速に行う手法の一つとして、楕円曲線暗号におけるスカラー値のΦ進展開表現の高速化を図る方法がある（例えば、特許文献1、及び非特許文献1、2、3参照。）。多項式基底、及び、正規基底については、例えば、非特許文献2に記載されている。
【００１９】
また、2倍算を減らすだけでなく、スカラー倍計算の際に必要な楕円曲線上の加算回数自体を低減することにより、スカラー倍計算は高速化できる。楕円曲線上のスカラー倍計算では、上述のように、非零の場合に加算が行われるため、非零濃度を最小とすることにより、高速化する方法がある。ここで、非零濃度とは、（非零桁の個数）/（桁長）の漸近的な値を指す。一般に、与えられたスカラー値に対して、ある展開における非零濃度が最小のとき、その展開を用いたスカラー倍計算は、スカラー倍計算に関して高速化されることは、上述のように知られている。
【００２０】
この性質を利用して楕円曲線上のスカラー倍計算を高速に行う手法の一つとして、与えられたスカラー値に対して、予め定められた整数を用いてエンコードした場合のスカラー値の非零濃度が最小となる展開（rNAF）を行うことにより、楕円曲線上のスカラー倍計算の高速化を図る方法がある（例えば、非特許文献4参照。）。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開2007-041461号公報
【非特許文献】
【００２２】
【非特許文献１】N. P. Smart,Elliptic Curve Cryptosystems over Small Fields of Odd Characteristic, Journalof Cryptology, Vol.12, No.2, pp.141–151, 1999.
【非特許文献２】J. A.Solinas, Efficient Arithmetic on Koblitz Curves, Designs, Codes andCryptography, Vol.19, No.2-3, Kluwer Academic Publishers, pp.195-249, 2000.
【非特許文献３】K. Hakuta, H.Sato, and T. Takagi, Efficient Arithmetic on Subfield Elliptic Curves overSmall Finite Fields of Odd Characteristic, In Information Security Practice andExperience Conference – ISPEC2008, Vol.4991 of Lecture Notes in Computer Science,pp.304-318, 2008.
【非特許文献４】T. Takagi, S.M. Yen, and B. C. Wu, Radix-r Non-adjacent Form, In Information SecurityConference - ISC2004, Vol.3225 of Lecture Notes in Computer Science, pp.99-110,2004.
【発明の概要】
【発明が解決しようとする課題】
【００２３】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証の為に暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも、処理速度やメモリ使用量などがある。しかし、一般に安全性、処理速度、メモリ使用量の間にはトレードオフの関係があり、全ての要件を満たすことは難しい。
【００２４】
一般に、暗号に用いられる鍵の長さ（鍵長）は安全性の指標とされ、長いほど安全性が高くなることが知られている。しかしながら、鍵長が長いほど処理に時間はかかる。
【００２５】
楕円曲線上の離散対数問題の求解の困難性は素因数分解の困難性に比べて高いため、素因数分解の困難性を安全性の根拠にしている暗号と比べて、楕円曲線暗号は鍵長を比較的短くすることができる。従って、楕円曲線暗号によれば、計算能力、メモリ容量などのリソースが比較的少なくても、素因数分解の困難性を利用する暗号処理と同等の安全性を有する暗号処理を短時間の処理、すなわち、リソースへの負担が少ない処理で実現することが可能である。
【００２６】
最近では、スマートカード（ICカードともいう）等、利用可能なリソースがかなり限られている環境においても、安全性の高い暗号処理の必要性が高まっている。スマートカードのようなリソースの少ない環境では、限られたリソース内で暗号処理の最適化を図る必要があり、安全性を高めるために鍵長を長くすると処理負担の増大が大きいため、さらにリソースへの負担の少ない高速な処理が求められている。
【００２７】
上記非特許文献1には、整数倍算とは異なる自己準同型写像を実行することができる全ての楕円曲線に対する、整数倍算とは異なる自己準同型写像を用いた楕円曲線スカラー倍計算方法が記載されている。しかし、スカラー倍計算の際に必要な楕円曲線上の加算回数の低減については考慮されていないため、充分な速度が得られない場合がある。
【００２８】
上記非特許文献2では、整数倍算とは異なる自己準同型写像を実行することができる楕円曲線の中で、特殊な定義方程式を持つ楕円曲線（Koblitz曲線）に関してのみ、スカラー倍計算の際の加算回数の低減について考察されている。しかし、一般的な定義方程式を持つ楕円曲線については考察がなされていないため、適用できる楕円曲線が限られる。
【００２９】
上記特許文献1、及び、上記非特許文献3では、整数倍算とは異なる自己準同型写像を実行することができる楕円曲線の中で、より広範な楕円曲線に関し、スカラー倍計算の際の加算回数の低減について考察されている。しかし、上記楕円曲線は、定義体上でトレースが1であるという条件があるため、その他のトレースをもつ楕円曲線では、上記特許文献1、及び、上記非特許文献3のスカラー倍計算方法が使用できない。
【００３０】
また、上記非特許文献4の技術は、与えられたスカラー値に対して、予め定められた整数を用いて非零濃度が最小となる展開（rNAF）について考察されている。しかし、整数以外の、例えば複素数を用いた展開に関するrNAFまでは考察されていない。
【００３１】
すなわち、従来の楕円曲線上でのスカラー倍計算においては、定義体Fq上定義された楕円曲線上の整数倍算とは異なる自己準同型写像Φを実行することができ、かつ上述のKoblitz曲線や整数倍算とは異なる自己準同型写像を実行することができるトレースが1かつ定義体の標数が奇数である楕円曲線以外の楕円曲線に対して、さらなる高速化を図ることに関しては不十分である。
【課題を解決するための手段】
【００３２】
本発明は、上記課題に鑑みてなされたもので、リソースが限られた環境で、安全性を低下させることなく、Koblitz曲線や整数倍算とは異なる自己準同型写像を実行することができるトレースが1かつ定義体の標数が奇数である楕円曲線以外の広範な楕円曲線に対して、従来の楕円曲線上のスカラー倍計算よりさらに高速に処理可能な楕円曲線演算技術を実現する。
【００３３】
本発明は、楕円曲線暗号におけるスカラー倍計算を高速化する。すなわち、スカラー値のエンコード処理を、通常のΦ進展開の桁集合より、桁集合を広げた際のΦ進展開表現が小さな非零濃度を持つように行うことにより、高速計算可能な楕円曲線演算装置を提供する。
【００３４】
本発明はさらに、上記楕円曲線演算装置を用いた暗号化処理装置、復号化処理装置、署名生成装置、署名検証装置、及び、データ共有装置を提供する。
【００３５】
具体的には、特性多項式Φ2+Φ+q（ｑは奇素数のべき）を持つ、定義体Fq上定義された楕円曲線上の整数倍算とは異なる自己準同型写像Φを実行することができる楕円曲線を用いて、スカラー値、及び、 楕円曲線上の点とからスカラー倍点を計算する楕円曲線暗号におけるスカラー倍計算方法であって、 楕円曲線の定義体はFqであり、 スカラー値を、第一の数値列（bn-1，bn-2，…，b0）（ｎは スカラー値を第一の数値列にエンコードした際の桁長）にエンコードする第一のステップと、 第一の数値列を、 第一の数値列とは異なる第二の数値列にエンコードする第二のステップと、
楕円曲線上の点から事前計算テーブルを作成する第三のステップと、 第二の数値列、及び、 事前計算テーブルから、
スカラー倍点を計算する第四のステップと、を備えることを特徴とするスカラー倍計算方法を提供する。
【００３６】
さらに、第一のステップは、前記スカラー値に対するΦ進展開を計算し、
第二のステップは、
bnとbn+1とbn+2とbn+3とを生成してそれぞれ0とするステップと（ｎはスカラー値に対するΦ進展開の桁長）、
iが0からnまでの間、
bi=0を満たすとき、biをbiとする変換を行った後iを1増加させ、
bi≠0、かつ、｜-qbi+1+bi｜≦（q2-1）/2を満たすとき、bi→-qbi+1+bi，bi+1→0，bi+2→-bi+1+bi+2とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi>（q2-1）/2を満たすとき、bi→- bi+1q+bi-q2，bi+1→0，bi+2→bi+2- bi+1-（q-1），bi+3→bi+3+1とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi<-（q2-1）/2を満たすとき、bi→- bi+1q+bi+q2，bi+1→0，bi+2→bi+2- bi+1+（q-1），
bi+3→bi+3-1とする変換を行った後iを2増加させる処理を繰り返す変換ステップと、を備えることを特徴とする。
【発明の効果】
【００３７】
本発明によれば、リソースが限られた環境で、安全性を低下させることなく、従来の楕円曲線演算よりさらに高速に処理可能な楕円曲線演算技術を実現することができる。
【図面の簡単な説明】
【００３８】
【図１】図1は、第一の実施形態の暗号通信システムのシステム構成を例示する図である。
【図２】図2は、第一の実施形態のコンピュータ内の各処理部間の情報の受け渡しを例示するための図である。
【図３】図3は、第一の実施形態のスカラー倍計算部の機能ブロック例である。
【図４】図4は、第一の実施形態のエンコード部の処理を例示するためのフローチャートである。
【図５】図5は、第一の実施形態の事前計算部の処理を例示するためのフローチャートである。
【図６】図6は、第一の実施形態の実計算部の処理を例示するためのフローチャートである。
【図７】図7は、第二の実施形態の署名検証システムのシステム構成を例示する図である。
【発明を実施するための形態】
【００３９】
以下、本発明を適用した第一の実施形態を図面により説明する。
【００４０】
図1は、本実施形態の暗号通信システムのシステム構成図である。本図に示すように、本実施形態の暗号通信システムは、ネットワーク142により接続されたコンピュータＡ101、コンピュータＢ121とを備える。
【００４１】
本実施形態の暗号通信システムにおいては、コンピュータＡ101でメッセージPmの暗号化を行い、コンピュータＢ121で暗号文の復号を行う。
【００４２】
kは乱数、dは秘密鍵を示す定数、Qは定点、dQは公開鍵を示す点とすると、コンピュータＡ101において、Pm+k（dQ）及びkQを計算して出力する。そして、コンピュータＢ121において、秘密鍵d、及び、kQより-d（kQ）を計算し、
（Pm+k（dQ））d（kQ） （式10）
を計算して出力する。
【００４３】
ここで、メッセージPmを復元するためには、kdQ、すなわちkQのd倍を計算する必要がある。ところが、暗号通信システムでは、ネットワーク142には、Pm+k（dQ）、kQが送信され、秘密鍵dは送信されないため、秘密鍵dを保持しているものだけが、Pmを復元できることになる。
【００４４】
図1において、コンピュータＡ101は、ＣＰＵ113やコプロセッサ114などの演算装置、ＲＡＭ103、ＲＯＭ106や外部記憶装置107などの記憶装置、コンピュータ外部とのデータ入出力を行う入出力インタフェース110を装備し、外部にはコンピュータＡ101をユーザが操作するためのディスプレイ108、キーボード109、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
【００４５】
更にコンピュータＡ101は、ＲＡＭ103、ＲＯＭ106や外部記憶装置107などの記憶装置によって、記憶部102を実現し、ＣＰＵ113やコプロセッサ114などの演算装置が、記憶部102に格納されたプログラムを実行することにより、データ処理部112、スカラー倍計算部115とそれらに含まれる各処理部を実現する。
【００４６】
データ処理部112は、本実施形態においては、暗号化処理部として機能し、入力されたメッセージの暗号化を行う。
【００４７】
スカラー倍計算部115は、データ処理部（暗号化処理部）112で暗号化を行うのに必要なパラメタを計算する。記憶部102は、定数104（例えば、楕円曲線の定義式や楕円曲線上の定点）、秘密情報105（例えば、秘密鍵）などを記憶している。
【００４８】
コンピュータＢ121は、コンピュータＡと同様のハードウェア構成を備え、ＣＰＵ133やコプロセッサ134などの演算装置、ＲＡＭ123、ＲＯＭ126や外部記憶装置127などの記憶装置、コンピュータ外部とのデータ入出力を行う入出力インタフェース130を装備し、外部にはコンピュータＢ101をユーザが操作するためのディスプレイ128、キーボード129、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
【００４９】
更にコンピュータＢ121は、ＲＡＭ123、ＲＯＭ126や外部記憶装置127などの記憶装置によって、記憶部122を実現し、ＣＰＵ133やコプロセッサ134などの演算装置が、記憶部122に格納されたプログラムを実行することにより、データ処理部132、スカラー倍計算部135とそれらに含まれる各処理部を実現する。
【００５０】
データ処理部132は、本実施形態においては、復号化処理部として機能し、暗号化されたメッセージである暗号文141の復号を行う。
【００５１】
スカラー倍計算部135は、データ処理部（復号化処理部）132で復号化を行うのに必要なパラメタを計算する。記憶部122は、定数124（例えば、使用する楕円曲線の定義式や楕円曲線上の定点）、秘密情報125（例えば、秘密鍵）などを記憶している。
【００５２】
なお、上記プログラムは、予め上記コンピュータ内の記憶部102、122に格納されていてもよいし、必要な時に、入出力インタフェース110、130および上記コンピュータが利用可能な媒体を介して、他の装置から上記記憶部102、122に導入されてもよい。媒体とは、例えば、入出力インタフェースに着脱可能な記憶媒体、または通信媒体（すなわち、ネットワークまたはネットワークを伝搬するディジタル信号や搬送波）を指す。
【００５３】
次に、メッセージの暗号化処理および復号化処理を行う場合の、それぞれ、コンピュータＡ101およびコンピュータＢ121内の各処理部間での情報の送受信について説明する。図2は、コンピュータＡ101、コンピュータＢ121の各処理部が行う情報の受け渡しを説明するための図である。
【００５４】
まず、コンピュータＡ101が、入力されたメッセージを暗号化する場合の動作について説明する。メッセージはディジタル化されたデータであればよく、テキスト、画像、映像、音などの種類は問わない。
【００５５】
データ処理部（暗号化処理部）112は、入出力インタフェース110を介して、平文メッセージ（入力メッセージ）を受け取ると（ステップ204）、入力された平文メッセージのビット長があらかじめ定めたビット長か否かを判断する。予め定めたビット長よりも長い場合には、予め定めたビット長となるように平文メッセージを区切る。以下、メッセージは、所定のビット長に区切られている部分メッセージ（単にメッセージと呼ぶ。）であるものとして説明する。
【００５６】
次に、データ処理部（暗号化処理部）112は、メッセージのビット列によって表される数値をx座標（x1）に持つ楕円曲線上の点Pmのy座標（y1）の値を計算する。
【００５７】
例えば、使用する楕円曲線をワイエルシュトラス型楕円曲線とすると、ワイエルシュトラス型楕円曲線は、a，bを定数とするとき、
y12=x13+ax1+b （式11）
で表されるので、本式によりy座標の値を求めることができる。
【００５８】
次に、データ処理部（暗号化処理部）112は、乱数kを生成する。そして記憶部102に格納されている定数104から公開鍵dQとQのx座標とを読み出す（ステップ205）。そして、読み出した公開鍵dQとQのx座標と、求めたy座標の値と、乱数kとをスカラー倍計算部115へ送る（ステップ206）。
【００５９】
スカラー倍計算部115は、Qのx座標、y座標の値、乱数kによるスカラー倍点（xd1，yd1）=kQと、公開鍵dQのx座標、y座標の値、乱数によるスカラー倍点（xd2，yd2）=k（dQ）とを計算し、計算したスカラー倍点をデータ処理部（暗号化処理部）112へ送る（ステップ207）。
【００６０】
データ処理部（暗号化処理部）112は、受け取ったスカラー倍点を用いて、暗号化処理を行う。例えば、ワイエルシュトラス型楕円曲線の場合、Pm+k（dQ）とkQを計算する。すなわち、
xe1=（（yd1-y1）/（xd1-x1））2-x1-xd1 （式12）
xe2=xd2 （式13）
を計算し、暗号化されたメッセージxe1，xe2を得る。
【００６１】
コンピュータＡ101はデータ処理部（暗号化処理部）112で暗号化された1つ以上の部分メッセージから暗号化された出力メッセージを組み立て、データ141として入出力インタフェース110より出力する（ステップ208）。データ141は、ネットワーク142を介してコンピュータＢ121へ転送される。
【００６２】
なお、図2において記憶部102からの情報の読み出し（ステップ205）は、スカラー倍計算部115へ当該情報を送る前であればよい。例えば、入力メッセージを受け付ける（ステップ204）前であってもよい。
【００６３】
次に、コンピュータＢ121が、暗号化されたメッセージであるデータ141を復号化する場合の動作について、同じく図2を用いて説明する。
【００６４】
データ処理部（復号化処理部）132は、入出力インタフェース110を介して、暗号化されたデータ141が入力メッセージとして入力されると（ステップ204）、データ141のビット長が予め定めたビット長か否かを判断する。予め定めたビット長よりも長い場合は、予め定めたビット長となるように暗号化されたデータを区切る。以下、メッセージは、所定のビット長に区切られている部分データ（単にデータともいう）であるものとして説明する。
【００６５】
データ処理部（復号化処理部）132は、データ141のビット列によって表される数値をx座標にもつ楕円曲線上のy座標の値を計算する。
【００６６】
暗号化されたメッセージがxe1，xe2のビット列であり、ワイエルシュトラス型楕円曲線の場合、y座標の値（ye1）は、
ye12=xe13+axe1+b （式14）
（ただし、a，bはそれぞれ（式11）と同じ定数である。）から得ることができる。
【００６７】
データ処理部（復号化処理部）132は、記憶部122に格納されている秘密情報125から秘密鍵dを読み出す（ステップ205）。そして、読み出した秘密鍵dと、x座標、y座標の値（xe2，ye2）を、スカラー倍計算部135へ送る（ステップ206）。
【００６８】
スカラー倍計算部135は、x座標、y座標の値、秘密情報125（秘密鍵ｄ）を用いてスカラー倍点（xd3，yd3）=d（xe2，ye2）を計算する。スカラー倍計算部135は、計算されたスカラー倍点をデータ処理部（復号化処理部）132へ送る（ステップ207）。データ処理部（復号化処理部）132は、送られたスカラー倍点を用いて、復号化処理を行う。
【００６９】
例えば、暗号化されたメッセージが、xe1，xe2のビット列であり、ワイエルシュトラス型楕円曲線の場合は、
（Pm+k（dQ））d（kQ）=（xe1，ye1）-（xd3，yd3） （式15）
を計算することにより達成できる。すなわち、
xf1=（（ye1+yd3）/（xe1-xd3））2-xe1-xd3 （式16）
を計算し、暗号化される前の部分メッセージx1に相当するxf1を得る。
【００７０】
コンピュータＢ121は、データ処理部（復号化処理部）132で復号された部分メッセージから平文メッセージを組み立て、入出力インタフェース110を介して、ディスプレイ108などから出力する（ステップ208）。
【００７１】
次に、本実施形態において、コンピュータＡ101が、暗号化処理を行う場合の、スカラー倍計算部115の処理を詳細に説明する。なお、コンピュータＢ101が復号化処理を行う場合のスカラー倍計算部135の処理も基本的に同様である。このため、以下においては、スカラー倍計算部115の処理を代表して説明する。
【００７２】
本実施形態のスカラー倍計算部115の機能ブロックを図3に示す。本図に示すように、本実施形態のスカラー倍計算部115は、エンコード部302と、事前計算部303と、実計算部304とを備える。
【００７３】
また、エンコード部302は、Φ進展開部321、δ剰余取得部322、ビット対判定部323、ビット対変換部324、桁上がり計算部325、繰り返し判定部326を備える。事前計算部303は、加算部331、2倍算部332、繰り返し判定部333を備える。実計算部304は、ビット値判定部341、加算部342、Φ倍算部343、繰り返し判定部344を備える。
【００７４】
スカラー倍計算部115が、これらの機能を用いて、スカラー値dと整数倍算とは異なる自己準同型写像Φを持つ楕円曲線上の点Pとから、楕円曲線におけるスカラー倍点dPを計算する第1の計算方法を説明する。
【００７５】
以下、本実施形態においては、自己準同型写像Φとして、例えば、フロベニウス写像を用いることができる。すなわち、本計算方法は、上記非特許文献1に記載されているスカラー値のフロベニウス展開に、上記非特許文献4に記載されている整数展開rNAFを適用したエンコード方法であり、以下、本エンコード方法をFrNAF（Frobenius - adic Radix-r Non - Adjacent Form）と呼ぶ。
【００７６】
スカラー値のフロベニウス展開にrNAFを適用するために、本実施形態では、特性多項式Φ2+Φ+q（ｑは奇素数のべき）を持つ、定義体Fq上定義された楕円曲線上の、整数倍算とは異なる自己準同型写像Φを実行することができる楕円曲線を選択する。
【００７７】
また、本楕円曲線上の点とスカラー値とからスカラー倍点を計算するにあたり、スカラー値を第一の数値列にエンコードした後、さらに、第一の数値列とは異なる第二の数値列にエンコードし、第二の数値列を用いてスカラー倍点を計算する。このとき、第一の数値列は、スカラー値をΦ進展開することにより得、第二の数値列は、前記第一の数値列の隣り合う２桁が予め定められた条件を満たすか否かに応じて変換を行う。すなわち、満たさない場合、その２桁と、当該２桁と隣り合う１桁、または２桁のそれぞれに対し演算を行い、変換後の数値列を第一の数値列とし、本処理を繰り返す。
【００７８】
この第二の数値列とこの楕円曲線上の点とを用いてスカラー倍計算を実行することにより、高速化を実現する。以下、上記計算方法を具体的に説明する。
【００７９】
まず、本実施形態のスカラー倍計算処理全体の概要を説明する。
【００８０】
スカラー倍計算部115が暗号化処理部112からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部302は、入力されたスカラー値dから値d’を計算し、値d’を数値列eiにエンコードする。すなわち、
d’=e0+e1Φ+e2Φ2+…+en+3Φn+3 （式17）
-（q2-1）/2≦ei≦（q2-1）/2 （式18）
ei mod q≠0（ei≠0のとき） （式19）
を満たすeiに、スカラー値d’を変換する。
【００８１】
ここで、d'は
δ=(Φn-1)/(Φ-1) （式20）
を満たす複素数δに対して
d=δQ+d' （式21）
を満たす整数であり、Qは複素数である。
また、（式17）の各iについて、隣り合う数値の対（ei+1, ei）は以下の条件
ei+1ei=0 （式22）
を満たし、kは
k≦[2logq2√|d'|]+4 （式23）
を満たす整数である。
【００８２】
なお、対（ei+1，ei）が、上記（式22）を満たすとき、対（ei+1，ei）は非隣接対であるという。
【００８３】
事前計算部303は、事前計算テーブルを作成する。事前計算テーブルは、
iP（i=1，…，（q2-1）/2） （式24）
を保持する。ただし、iは
i mod q≠0 （式25）
を満たす。
【００８４】
実計算部304は、エンコードされたスカラー値d=（en+3，en+2，…，e1，e0）と事前計算テーブルに保持されているデータとを用いてスカラー倍点dPを計算する。
【００８５】
次に、上記スカラー倍計算処理時のエンコード部302、事前計算部303、実計算部304の行う各処理について詳細に説明する。
【００８６】
まず、図4を用いて本実施形態のエンコード部302の行う処理について説明する。ここでは、スカラー値を第一の数値列にエンコードし、さらに、第一の数値列を第二の数値列にエンコードする処理を行う。図4は、本実施形態のエンコード部302の処理を説明するためのフローチャートである。
【００８７】
エンコード部302は、スカラー値dの入力を受ける（ステップ401）。
【００８８】
δ剰余取得部322は、受け取ったスカラー値dに対して、第一の実施形態の（式21）を満たす整数d'を計算する。そして、Φ進展開部321は、整数d'を、
d'=c0+c1Φ+…+cn-1Φn-1 （式26）
|ci|≦（q-1）/2 （式27）
に変換する（ステップ402）。
【００８９】
スカラー値dから整数d'を計算する方法、及び、整数d'を、（式26）、（式27）を満たすように展開する方法は、非特許文献1に記載されている。すなわち、以下の処理ｉ）、ｉｉ）を繰り返すことにより得られる。
ｉ）スカラー値dをδで割り、その余りをd'とする。
ｉｉ）整数d'をΦで割り、その余りをciとする。
【００９０】
次に、第一の数値列（c0，c1，c2，…cn-1）から（b0，b1，b2，…bn-1，bn，bn+1，bn+2，bn+3）を経て、第二の数値列（e0，e1，…en，en+1，en+2，en+3）を生成する。
【００９１】
まず、ビット対変換部324は、b0にc0を、b1にc1を、bnに0を、bn+1に0を、bn+2に0を、bn+3に0をそれぞれ代入する（ステップ403）。
【００９２】
繰り返し判定部326は、iに0を代入する（ステップ404）。
【００９３】
繰り返し判定部326は、i≦n+2であるかどうかを判定する（ステップ405）。i≦n+2が成立する場合、ステップ406へ行く。i≦n+2が成立しない場合、ステップ413へ行く。
【００９４】
ビット対判定部323は、bi=0であるかどうかを判定する（ステップ406）。bi=0である場合、ステップ407へ行く。bi=0でない場合、ステップ408へ行く。
【００９５】
桁上がり計算部325は、bi+2にci+2を代入し、格納部327は、eiに0を代入し、iにi+1を代入し、ステップ405へ行く（ステップ407）。
【００９６】
ビット対判定部323は、|-bi+1q+bi|≦（q2-1）/2であるかどうかを判定する（ステップ408）。|-bi+1q+bi|≦（q2-1）/2である場合、ステップ409へ行く。|-bi+1q+bi|≦（q2-1）/2でない場合、ステップ410へ行く。
【００９７】
桁上がり計算部325は、bi+3にci+3を、bi+2にci+2-bi+1をそれぞれ代入し、格納部327は、ei+1に0を、eiに-bi+1q+biを代入し、iにi+2を代入し、ステップ405へ行く（ステップ409）。
【００９８】
ビット対判定部323は、-bi+1q+bi<-（q2-1）/2であるかどうかを判定する（ステップ410）。-bi+1q+bi<-（q2-1）/2である場合、ステップ411へ行く。-bi+1q+bi<-（q2-1）/2でない場合、ステップ412へ行く。
【００９９】
桁上がり計算部325は、bi+3にci+3-1を、bi+2にci+2-bi+1+（q-1）をそれぞれ代入し、格納部327は、ei+1に0を、eiに-bi+1q+bi+q2を代入し、iにi+2を代入し、ステップ405へ行く（ステップ411）。
【０１００】
桁上がり計算部325は、bi+3にci+3+1を、bi+2にci+2-bi+1-（q-1）をそれぞれ代入し、格納部327は、ei+1に0を、eiに-bi+1q+bi-q2を代入し、iにi+2を代入し、ステップ405へ行く（ステップ412）。
【０１０１】
エンコード部302は、（en+3，en+2，…，e1，e0）を出力する（ステップ413）。
【０１０２】
なお、q≦5の場合、以下のステップを追加する。
【０１０３】
ステップ406でbi=0であるかどうかを判定する前に、biがqで割り切れるかどうかを判定する。biがqで割り切れる場合、bi+1にbi+1-bi/qを、bi+ 2にci+2-bi/qを、それぞれ代入し、iにi+1を代入する。
【０１０４】
次に図5を用いて本実施形態の事前計算部303の行う処理について説明する。図5は、本実施形態の事前計算部303の処理を説明するためのフローチャートである。ここでは、事前計算テーブルに保持するデータを生成する。事前計算テーブルに保持するデータは、上述のとおり、楕円曲線上の点Ｐの値、点Ｐのスカラー倍点の値2P、3P、…、((q2 - 1)/2)P（ただし、点iP(i = q， 2q ，…，((q - 1)/2)P)は含まれない。）である。
【０１０５】
事前計算部303は、Q1にPを代入し、2倍算部332は、点Pの2倍点2Pを計算し、事前計算部303は、Q2に2Pを代入する（ステップ501）。
【０１０６】
繰り返し判定部333は、iに2を代入する（ステップ502）。
【０１０７】
繰り返し判定部333は、i≦（q2-1）/2であるかどうかを判定する（ステップ503）。i≦（q2-1）/2である場合、ステップ504へ行く。i≦（q2-1）/2でない場合、ステップ508へ行く。
【０１０８】
剰余判定部334は、i mod q≡0であるかどうかを判定する（ステップ504）。i mod q≡0である場合、ステップ506へ行く。i mod q≡0でない場合、ステップ505へ行く。
【０１０９】
加算部331は、Qi+Pを計算し、事前計算部303は、その結果をQi+1に代入する（ステップ505）。
【０１１０】
加算部331は、Qi+Pを計算し、事前計算部303は、その結果をQi+2に代入する（ステップ506）。
【０１１１】
繰り返し判定部333は、iにi+1を代入し、ステップ503へ行く（ステップ507）。
【０１１２】
事前計算部303は、点Q1，…，Q（q2-1）/2を事前計算テーブルに格納する（ステップ508）。ただし、上記Qiで、iはqの倍数ではない。
【０１１３】
最後に、図6を用いて実計算部304の行う処理について説明する。ここでは、エンコード部302により得られたエンコードされたスカラー値と、事前計算部303で得られたデータとから、スカラー倍点dPを計算する。図6は、本実施形態の実計算部304の処理を説明するためのフローチャートである。
【０１１４】
繰り返し判定部344は、iにn+3を代入する（ステップ601）。
【０１１５】
ビット値判定部341は、ei≠0であるかどうかを判定する（ステップ602）。ei≠0である場合、ステップ603へ行く。ei≠0でない場合、ステップ604へ行く。
【０１１６】
繰り返し判定部344は、iにi-1を代入する（ステップ603）。
【０１１７】
加算部342は、QにeiPを代入する（ステップ604）。
【０１１８】
繰り返し判定部344は、iにi-1を代入する（ステップ605）。
【０１１９】
繰り返し判定部344は、i≧0であるかどうかを判定する（ステップ606）。i≧0である場合、ステップ607へ行く。i≧0でない場合、ステップ611へ行く。
【０１２０】
Φ倍算部343は、Φ（Q）を計算し、Qに代入する（ステップ607）。
【０１２１】
ビット値判定部341は、ei≠0であるかどうかを判定する。ei≠0である場合、ステップ609へ行く。ei≠0でない場合、ステップ610へ行く。（ステップ608）
加算部342は、Q+eiPを計算し、Qに代入する（ステップ609）。
【０１２２】
繰り返し判定部344は、iにi-1を代入し、ステップ606へ行く（ステップ610）。
【０１２３】
実計算部304は、Qを出力する（ステップ611）。
【０１２４】
以上の処理により、エンコード部302から出力されるeiは、（式17）を満たし、対（ei+1，ei）は、（式22）を満たす。この理由は次の通りである。
【０１２５】
ステップ406の直前で、bi+1，biはそれぞれ、|bi+1|≦（q-1）/2，|bi|≦q-1、または、|bi+1|≦（q+1）/2，|bi|≦2q-1（bi≠±q）を満たす。対（bi+1，bi）が隣接対のときは、ステップ407へ行く。対（bi+1，bi）が非隣接対の場合を考える。このとき、ステップ409、ステップ411、ステップ412の何れの場合も、ei+1=0となり、対（ei+1，ei）は（式22）を満たす。
【０１２６】
また、エンコード部302が行う処理により、整数d'のΦ進展開の長さは（式23）を満たす。これは、ステップ406からステップ412の処理ループにおいて、すべてのiに対して（式17）を満たすように整数d'を変換するため、整数d'のΦ展開の長さは（式23）を満たすことがわかる。
【０１２７】
実計算部304が出力する点Qはスカラー倍点dPに等しい。この理由は、（式17）、（式20）、（式23）から明らかである。
【０１２８】
整数d'のFrNAF表現は一意的である。この理由は通常のrNAF表現の一意性と同様である。
【０１２９】
以上の通り、本実施形態のスカラー倍計算方法によれば、Koblitz曲線や整数倍算とは異なる自己準同型写像を実行することができるトレースが1かつ定義体の標数が奇数である楕円曲線以外の楕円曲線を用い、非零濃度を小さくすることができ、スカラー倍計算処理を高速化することができる。また、楕円曲線の制限は、整数倍算とは異なる自己準同型写像Φを持つこと、及び、上記楕円曲線のトレースが-１であることであるため、幅広い楕円曲線を選択可能である。このため、より高い安全性が期待できる。
【０１３０】
すなわち、本実施形態によれば、楕円曲線暗号が持つ高い安全性とリソース利用効率の良さを保ちつつ、高速性に優れたメッセージ処理が可能になる。
【０１３１】
次に、本発明を適用した署名検証システムを第二の実施形態として説明する。
【０１３２】
図7は、本実施形態の署名検証システムのシステム構成図である。本図に示すように、本実施形態の署名検証システムは、スマートカード701と署名検証処理を行うコンピュータ721とを備える。
【０１３３】
スマートカード701は、第一の実施形態および第二の実施形態の図1のコンピュータＡ101と類似の構成を備える。すなわち、コンピュータＡ101の同名の構成は基本的に同じ機能を有する。ただし、スマートカード701は、ＣＰＵ713、コプロセッサ714などの演算装置が記憶部702に格納されているプログラムを実行することにより、データ処理部111とスカラー倍計算部115の代わりに、署名生成処理部712とスカラー倍計算部715とを実現する。なお、図1に示す外部記憶装置107、ディスプレイ108、キーボード109を備えなくてもよい。
【０１３４】
一方、コンピュータ721は、コンピュータＡ101と同様の構成を備える。すなわち、図1に示すコンピュータＡ101と同名の構成は、同様の機能を有する。ただし、ＣＰＵ733、コプロセッサ734などの演算装置が記憶部722に格納されているプログラムを実行することにより、データ処理部111とスカラー倍計算部115の代わりに、署名検証処理部732とスカラー倍計算部735とを実現する。
【０１３５】
なお、スカラー倍計算部715と735は、図1に示すスカラー倍計算部115または135と同様の機能を備える。
【０１３６】
本実施形態においても、第一の実施形態同様、コンピュータ721内の各プログラムは、予め、コンピュータ721内の記憶部722に格納されていても良いし、必要なときに、コンピュータ721が利用可能な媒体を介して、他の装置から記憶部722に導入されてもよい。
【０１３７】
さらに、スマートカード701内の各プログラムは、予め、スマートカード701内の記憶部702に格納されていても良いし、必要なときに、入出力インタフェース710を介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して、記憶部702に導入されてもよい。媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【０１３８】
次に、本実施形態の署名検証システムにおける署名生成と署名検証動作を、図2を参照して説明する。なお、本実施形態においては、図2のデータ処理部112、132は、署名生成処理部712、署名検証処理部732、スカラー倍計算部115、135は、スカラー倍計算部715、735、記憶部122、102は、記憶部702、722として以下、説明する。
【０１３９】
離散対数問題に基づくディジタル署名方法を楕円曲線上の離散対数問題に基づく方法に対応させて構成する楕円曲線ディジタル署名アルゴリズム（ECDSA）という署名方法がある。ECDSA署名については、例えば、
D. Johnson， A. Menezes, The Elliptic Curve Digital
Signature Algorithm (ECDSA), Technial Report CORR 99-34, Dept. of C&O,
University of Waterloo, Canada.
<URL>
http://www.cacr.math.uwaterloo.ca/techreports/1999/corr99-34.pdf
に記載されている。
【０１４０】
コンピュータ721は、ランダムに選んだ数値をチャレンジコード742として、インタフェースを介してスマートカード701に転送する。
【０１４１】
署名生成処理部712は、チャレンジコード742を入力メッセージとして受け付け（ステップ204）、チャレンジコード742のハッシュ値をとり、所定のビット長の数値fに変換する。
【０１４２】
署名生成処理部712は、乱数uを生成し、記憶部702に格納されている定数704から楕円曲線上の定点Qを読み出す（ステップ205）。生成した乱数uを読み出した楕円曲線上の定点Qとともにスカラー倍計算部715へ送る（ステップ206）。
【０１４３】
スカラー倍計算部715は、定点Q、乱数uを用いてスカラー倍点uQ=（xu，yu）を計算し、計算されたスカラー倍点を署名生成処理部712へ送る（ステップ207）。
【０１４４】
署名生成処理部712は、送られたスカラー倍点を用いて署名の生成を行う。例えば、上述のECDSA署名であれば、
s=xu mod q （式28）
t=u-1（f+ds） mod q （式29）
を計算することにより、チャレンジコード742に対応する署名（s，t）741を得る。
【０１４５】
ここで、qは定点Qの位数、すなわち、定点Qのq倍点qQが無限遠点になり、qより小さな数値mに対する定点Qのm倍点mQは無限遠点にはならない、という数値のことである。
【０１４６】
スマートカード701は、署名生成処理部712で生成した署名741を入出力インタフェース710より出力し（ステップ208）、インタフェースを介してコンピュータ721へ転送する。
【０１４７】
コンピュータ721の署名検証処理部732は、署名741が入力されると（ステップ204）、署名741の数値s，tが適切な範囲内すなわち1≦s，t<qであるかを調べる。
【０１４８】
数値s，tが上記範囲内になければチャレンジコード742に対する署名の検証結果として「無効」を出力し、スマートカード701を拒絶する（ステップ208）。
【０１４９】
一方、数値s，tが上記範囲内にあれば、署名検証処理部732は、
h=t-1 mod q （式30）
h1=fh mod q （式31）
h2=sh mod q （式32）
を計算する。
【０１５０】
署名検証処理部732は、記憶部722に格納されている定数724から公開鍵dQ及び定点Qを読み出す（ステップ205）。そして、読み出した公開鍵dQ及び定点Qと、計算したh1，h2とを、スカラー倍計算部735へ送る（ステップ206）。
【０１５１】
スカラー倍計算部735は、定点Qとh1とによるスカラー倍点h1Qと、公開鍵dQとh2とによるスカラー倍点h2dQとを計算し、計算されたスカラー倍点を署名検証処理部732へ送る（ステップ207）。
【０１５２】
署名検証処理部732は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ECDSAの署名検証であれば、点Rを以下の式により計算し、
R=h1Q+h2dQ （式33）
そのx座標をxRとしたとき、
s'=xR mod q （式34）
を計算し、s'=sであればチャレンジコード742に対する署名の検証結果として「有効」を出力し（ステップ208）、スマートカード701を認証し、受け入れる。
【０１５３】
一方、s'=sでなければ「無効」を出力し（ステップ208）、スマートカード701を拒絶する。
【０１５４】
上述のように、署名の生成および検証の処理において、スカラー倍点を計算する。従って、署名生成、及び、署名検証を行う際に、第一の実施形態のスカラー倍計算方法を用いることが可能である。この実施形態のスカラー倍計算方法を用いることにより、スマートカードといったリソースが限られた環境においても、高い安全性と高速な処理とを実現することができる。
【０１５５】
次に、本発明を楕円Diffie-Hellman鍵共有スキーム適用して実現する鍵交換システムを第三の実施形態として説明する。本実施形態の鍵交換システムのシステム構成は、図１と同様である。ただし、図1のデータ処理部112、132は、本実施形態においては、それぞれ鍵交換処理部112、132として機能する。
【０１５６】
以下、本実施形態の鍵交換システムのコンピュータＡ101が、入力されたデータ143から共有情報の導出を行う場合の動作について図1、図2を参照して説明する。図2においても、データ処理部112、132は、鍵交換処理部112、132として説明する。
【０１５７】
コンピュータＢ121の鍵交換処理部132は、記憶部122の秘密情報125から秘密鍵bを読み出し、コンピュータＢ121の公開鍵bQを計算する。そして、鍵交換処理部132は、ネットワーク142を介して、公開鍵bQをデータ143としてコンピュータＡ101に転送する（ステップ208）。
【０１５８】
コンピュータＡ101の鍵交換処理部112は、コンピュータＢ121の公開鍵bQのデータ143を入力メッセージとして受け付ける（ステップ204）。
【０１５９】
鍵交換処理部112は、記憶部102から秘密情報105であるコンピュータＡ101の秘密鍵dを読み出し（ステップ205）、秘密鍵dとコンピュータＢ121の公開鍵bQとをスカラー倍計算部115へ送る（ステップ206）。
【０１６０】
スカラー倍計算部115は、公開鍵bQによるスカラー倍点dbQを計算し、計算したスカラー倍点と秘密鍵dとを鍵交換処理部112へ送る（ステップ207）。
【０１６１】
鍵交換処理部112は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部102に秘密情報105として格納する。例えば、スカラー倍点dbQのx座標を、共有情報とする。
【０１６２】
次に、コンピュータＢ121が、入力されたデータ141から共有情報の導出を行う場合の動作について説明する。
【０１６３】
コンピュータＡ101の鍵交換処理部112は、記憶部102の秘密情報105から秘密鍵dを読み出しコンピュータＡ101の公開鍵dQを計算する。そして、ネットワーク142を介して、公開鍵dQをデータ141としてコンピュータＢ121に転送する（ステップ208）。
【０１６４】
コンピュータＢ121の鍵交換処理部132は、コンピュータＡ101の公開鍵dQであるデータ141を、入力メッセージ204として受け付ける（ステップ204）。
【０１６５】
鍵交換処理部132は、記憶部122の定数125から秘密情報125であるコンピュータＢ121の秘密鍵bを読み出し（ステップ205）、読み出した秘密鍵bとコンピュータＡ101の公開鍵dQとをスカラー倍計算部135へ送る（ステップ206）。
【０１６６】
スカラー倍計算部135は、公開鍵dQによるスカラー倍点bdQを計算し、計算されたスカラー倍点と秘密鍵bとを鍵交換処理部132へ送る（図2の207）。
【０１６７】
鍵交換処理部132は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部122に秘密情報125として格納する。例えば、スカラー倍点bdQのx座標を、共有情報とする。
ここで、数dbと数bdとは数値として同じなので、点dbQと点bdQとは同じ点となり、同じ情報が導出されたことになる。
【０１６８】
ネットワーク142には、点dQと点bQが送信される。しかし、点dbQ（もしくは点bdQ）を計算するためには、秘密鍵dもしくは秘密鍵bが必要である。すなわち、秘密鍵dもしくは秘密鍵bを知らなければ、共有情報を得ることはできない。従って、上記の方法で得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。
【０１６９】
本実施形態の鍵交換システムでは、受け取った点のスカラー倍点を計算する。従って、鍵交換を行う際に、第一の実施形態のスカラー倍計算方法を用いることが可能である。この実施形態のスカラー倍計算方法を用いることにより、高い安全性と高速な処理とを実現することができる。
【０１７０】
なお、上記各実施形態では、暗号化処理部、復号化処理部、署名生成処理部、署名検証処理部、鍵交換処理部を、ソフトウェアで実現するものとして説明したが、専用のハードウェアを用いて実現してもよい。また、スカラー倍計算部をコプロセッサまたはそれ以外の専用ハードウェアで実現しても良い。また、データ処理部は、上記暗号化処理、復号化処理、署名生成処理、署名検証処理、鍵交換処理のうち、任意の一つ以上の処理を行うことができるよう構成してもよい。
【符号の説明】
【０１７１】
101：コンピュータＡ、102：記憶部、103：RAM、104：定数、105:秘密情報、106：ROM、107：外部記憶装置、108：ディスプレイ、109：キーボード、110：入出力インタフェース、111：処理部、112：データ処理部、113：CPU、114：コプロセッサ、115：スカラー倍計算部、121：コンピュータＢ、122：記憶部、123：RAM、124：定数、125：秘密情報、126：ROM、127：外部記憶装置、128：ディスプレイ、129：キーボード、130：入出力インタフェース、131：処理部、132：データ処理部、133：CPU、134：コプロセッサ、135：スカラー倍計算部、141：データ、142：ネットワーク、143：データ、302：エンコード部、303：事前計算部、304：実計算部、321：Φ進展開部、322：δ剰余取得部、323：ビット対判定部、324：ビット対変換部、325：桁上がり計算部、326：繰り返し判定部、327：格納部、331：加算部、332：2倍算部、333：繰り返し判定部、341：ビット値判定部、342：加算部、343：Φ倍算部、344：繰り返し判定部、701：スマートカード、702：記憶部、703：RAM、704：定数、705：秘密情報、706：ROM、710：入出力インタフェース、711：処理部、712：署名生成処理部、713：CPU、714：コプロセッサ、715：スカラー倍計算部、721：コンピュータ、722：記憶部、723：RAM、724：定数、725：秘密情報、726：ROM、727：外部記憶装置、728：ディスプレイ、729：キーボード、730：入出力インタフェース、731：処理部、732：署名検証処理部、733：CPU、734：コプロセッサ、735：スカラー倍計算部、741：署名、742：チャレンジコード。
【技術分野】
【０００１】
本発明は、セキュリティ技術に係り、特に楕円曲線演算を用いたメッセージ処理技術に関する。
【背景技術】
【０００２】
楕円曲線暗号はN.Koblitz、V. S. Millerにより提案された公開鍵暗号の一種である。公開鍵暗号には、公開鍵（Public Key）と呼ばれる一般に公開してよい情報と、秘密鍵（Private Key）と呼ばれる秘匿しなければならない秘密情報がある。与えられたメッセージの暗号化や署名の検証には公開鍵を用い、与えられたメッセージの復号化や署名の生成には秘密鍵を用いる。
【０００３】
楕円曲線暗号における秘密鍵は、スカラー値が担っている。また、楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Pとそのスカラー倍の点dPが与えられた時、スカラー値dを求める問題である。楕円曲線上の点とは、楕円曲線の定義方程式を満たす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（乃至は加算）が定義される。そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の2倍算という。
【０００４】
楕円曲線上の2点の加法は次のようにして計算される。2点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とx軸に関して対称な点を、加法を行った結果の点とする。
【０００５】
例えば、ワイエルシュトラス型楕円曲線（以後、楕円曲線Eと呼ぶ。）の場合には、点（x1，y1）と点（x2，y2）とを加算した結果の点（x3，y3）（（x3，y3）=（x1，y1）+（x2，y2））は、
x3=λ2-x1-x2 （式1）
y3=（x1-x3）λ-y1 （式2）
λ=（y2-y1）/（x2-x1） （式3）
を計算することにより得られる。
【０００６】
ここで、楕円曲線Eの定義方程式は、
y2=x3+ax+b，（a，bはともに有限体Fqの元） （式4）
で与えられる。なお、点（x1，y1）と点（x2，y2）と点（x3，y3）はいずれも楕円曲線E上にある。すなわち、（式4）のx，yに各々xi，yi（i=1，2，3）を代入しても、（式4）の等式は成り立つ。
【０００７】
また、有限体Fqは（式4）で与えられる楕円曲線Eの定義体と呼ばれる。ここで、qは正の整数である。
【０００８】
以後、正の整数qは、ある自然数rを用いて、
q=pr （式5）
と表されるものとする。ここで、pは3以上の素数である。
【０００９】
また、以後、楕円曲線暗号に用いる可換群としてE（Fqm）を考える。
【００１０】
ただし、E（Fqm）は、（式4）の定義方程式で与えられる楕円曲線であり、楕円曲線上の各点P=（x，y）に対して、x，yがともにFqmの元であることを意味し、mは拡大次数と呼ばれる自然数である。
【００１１】
楕円曲線上の点の2倍算は次のようにして計算される。楕円曲線上の点における接線をひくと、その接線は楕円曲線上の他の一点において交わる。その交わった点とx座標に関して対称な点を、2倍算を行った結果の点とする。例えば、楕円曲線Eの場合には、点（x1，y1）の2倍算を行った結果の点（x3，y3）（（x3，y3）=2（x1，y1）=（x1，y1）+（x1，y1））は、（式1）、（式2）及び
λ=（3x12+a）/2y1 （式6）
を計算することにより得られる。
【００１２】
また、楕円曲線E上の点に対して、フロベニウス写像Φと呼ばれる自己準同型写像を施すことが可能である。点（x1，y1）に対してフロベニウス写像Φを施すとは、
Φ（x1，y1）=（x1q，y1q） （式7）
を計算することである。また、
（x2q，x2q）+q（x，y）=t（xq，yq） （式8）
が成り立つことが知られており、（式8）の性質によりΦを、
Φ2+q=tΦ （式9）
を満たす複素数と考えることができる。ここで、tは（式4）で与えられる楕円曲線Eのトレースと呼ばれる整数である。以下、トレースtは-1とする。
【００１３】
ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果の点をスカラー倍点、その回数のことをスカラー値という。
【００１４】
楕円曲線暗号においては、与えられたメッセージの暗号化、復号化、署名の生成、及び、その検証は、楕円曲線演算を用いて行う。その中で楕円曲線上のスカラー倍の計算は、上記の暗号化、復号化等の各処理において最も計算時間を要する計算である。そのため、楕円曲線暗号を高速に実行するためには、楕円曲線上のスカラー倍計算を高速に行う必要がある。
【００１５】
一般に楕円曲線上のスカラー倍計算では、エンコードされたスカラー値の各桁を見て、零でない（非零）場合に楕円曲線上の加算を行い、桁をずらすために楕円曲線上の2倍算を行う。ここで、スカラー値のエンコードとは、スカラー値の表現を小さな数値列に変換すること（以後、Φ進展開と呼ぶ。）である。ところが、楕円曲線上の2倍算は、楕円曲線上の加算、整数倍算とは異なる自己準同型写像と比べて処理が重い。
【００１６】
これに対し、整数倍算とは異なる自己準同型写像を実行することができる楕円曲線上のスカラー倍計算では、桁をずらすために楕円曲線上の2倍算を行う代わりに整数倍算とは異なる自己準同型写像を用いることができることが知られている。整数倍算とは異なる自己準同型写像は、楕円曲線暗号実装の際に、楕円曲線上の点を、正規基底を用いて実装した場合、シフト演算のみを用いて計算でき、2倍算に比べて処理が高速である。
【００１７】
従って、楕円曲線暗号実装の際に楕円曲線として、整数倍算とは異なる自己準同型写像を持つ楕円曲線を採用すれば、スカラー倍計算の高速化が可能となる。
【００１８】
この性質を利用して、楕円曲線上のスカラー倍計算を高速に行う手法の一つとして、楕円曲線暗号におけるスカラー値のΦ進展開表現の高速化を図る方法がある（例えば、特許文献1、及び非特許文献1、2、3参照。）。多項式基底、及び、正規基底については、例えば、非特許文献2に記載されている。
【００１９】
また、2倍算を減らすだけでなく、スカラー倍計算の際に必要な楕円曲線上の加算回数自体を低減することにより、スカラー倍計算は高速化できる。楕円曲線上のスカラー倍計算では、上述のように、非零の場合に加算が行われるため、非零濃度を最小とすることにより、高速化する方法がある。ここで、非零濃度とは、（非零桁の個数）/（桁長）の漸近的な値を指す。一般に、与えられたスカラー値に対して、ある展開における非零濃度が最小のとき、その展開を用いたスカラー倍計算は、スカラー倍計算に関して高速化されることは、上述のように知られている。
【００２０】
この性質を利用して楕円曲線上のスカラー倍計算を高速に行う手法の一つとして、与えられたスカラー値に対して、予め定められた整数を用いてエンコードした場合のスカラー値の非零濃度が最小となる展開（rNAF）を行うことにより、楕円曲線上のスカラー倍計算の高速化を図る方法がある（例えば、非特許文献4参照。）。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開2007-041461号公報
【非特許文献】
【００２２】
【非特許文献１】N. P. Smart,Elliptic Curve Cryptosystems over Small Fields of Odd Characteristic, Journalof Cryptology, Vol.12, No.2, pp.141–151, 1999.
【非特許文献２】J. A.Solinas, Efficient Arithmetic on Koblitz Curves, Designs, Codes andCryptography, Vol.19, No.2-3, Kluwer Academic Publishers, pp.195-249, 2000.
【非特許文献３】K. Hakuta, H.Sato, and T. Takagi, Efficient Arithmetic on Subfield Elliptic Curves overSmall Finite Fields of Odd Characteristic, In Information Security Practice andExperience Conference – ISPEC2008, Vol.4991 of Lecture Notes in Computer Science,pp.304-318, 2008.
【非特許文献４】T. Takagi, S.M. Yen, and B. C. Wu, Radix-r Non-adjacent Form, In Information SecurityConference - ISC2004, Vol.3225 of Lecture Notes in Computer Science, pp.99-110,2004.
【発明の概要】
【発明が解決しようとする課題】
【００２３】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証の為に暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも、処理速度やメモリ使用量などがある。しかし、一般に安全性、処理速度、メモリ使用量の間にはトレードオフの関係があり、全ての要件を満たすことは難しい。
【００２４】
一般に、暗号に用いられる鍵の長さ（鍵長）は安全性の指標とされ、長いほど安全性が高くなることが知られている。しかしながら、鍵長が長いほど処理に時間はかかる。
【００２５】
楕円曲線上の離散対数問題の求解の困難性は素因数分解の困難性に比べて高いため、素因数分解の困難性を安全性の根拠にしている暗号と比べて、楕円曲線暗号は鍵長を比較的短くすることができる。従って、楕円曲線暗号によれば、計算能力、メモリ容量などのリソースが比較的少なくても、素因数分解の困難性を利用する暗号処理と同等の安全性を有する暗号処理を短時間の処理、すなわち、リソースへの負担が少ない処理で実現することが可能である。
【００２６】
最近では、スマートカード（ICカードともいう）等、利用可能なリソースがかなり限られている環境においても、安全性の高い暗号処理の必要性が高まっている。スマートカードのようなリソースの少ない環境では、限られたリソース内で暗号処理の最適化を図る必要があり、安全性を高めるために鍵長を長くすると処理負担の増大が大きいため、さらにリソースへの負担の少ない高速な処理が求められている。
【００２７】
上記非特許文献1には、整数倍算とは異なる自己準同型写像を実行することができる全ての楕円曲線に対する、整数倍算とは異なる自己準同型写像を用いた楕円曲線スカラー倍計算方法が記載されている。しかし、スカラー倍計算の際に必要な楕円曲線上の加算回数の低減については考慮されていないため、充分な速度が得られない場合がある。
【００２８】
上記非特許文献2では、整数倍算とは異なる自己準同型写像を実行することができる楕円曲線の中で、特殊な定義方程式を持つ楕円曲線（Koblitz曲線）に関してのみ、スカラー倍計算の際の加算回数の低減について考察されている。しかし、一般的な定義方程式を持つ楕円曲線については考察がなされていないため、適用できる楕円曲線が限られる。
【００２９】
上記特許文献1、及び、上記非特許文献3では、整数倍算とは異なる自己準同型写像を実行することができる楕円曲線の中で、より広範な楕円曲線に関し、スカラー倍計算の際の加算回数の低減について考察されている。しかし、上記楕円曲線は、定義体上でトレースが1であるという条件があるため、その他のトレースをもつ楕円曲線では、上記特許文献1、及び、上記非特許文献3のスカラー倍計算方法が使用できない。
【００３０】
また、上記非特許文献4の技術は、与えられたスカラー値に対して、予め定められた整数を用いて非零濃度が最小となる展開（rNAF）について考察されている。しかし、整数以外の、例えば複素数を用いた展開に関するrNAFまでは考察されていない。
【００３１】
すなわち、従来の楕円曲線上でのスカラー倍計算においては、定義体Fq上定義された楕円曲線上の整数倍算とは異なる自己準同型写像Φを実行することができ、かつ上述のKoblitz曲線や整数倍算とは異なる自己準同型写像を実行することができるトレースが1かつ定義体の標数が奇数である楕円曲線以外の楕円曲線に対して、さらなる高速化を図ることに関しては不十分である。
【課題を解決するための手段】
【００３２】
本発明は、上記課題に鑑みてなされたもので、リソースが限られた環境で、安全性を低下させることなく、Koblitz曲線や整数倍算とは異なる自己準同型写像を実行することができるトレースが1かつ定義体の標数が奇数である楕円曲線以外の広範な楕円曲線に対して、従来の楕円曲線上のスカラー倍計算よりさらに高速に処理可能な楕円曲線演算技術を実現する。
【００３３】
本発明は、楕円曲線暗号におけるスカラー倍計算を高速化する。すなわち、スカラー値のエンコード処理を、通常のΦ進展開の桁集合より、桁集合を広げた際のΦ進展開表現が小さな非零濃度を持つように行うことにより、高速計算可能な楕円曲線演算装置を提供する。
【００３４】
本発明はさらに、上記楕円曲線演算装置を用いた暗号化処理装置、復号化処理装置、署名生成装置、署名検証装置、及び、データ共有装置を提供する。
【００３５】
具体的には、特性多項式Φ2+Φ+q（ｑは奇素数のべき）を持つ、定義体Fq上定義された楕円曲線上の整数倍算とは異なる自己準同型写像Φを実行することができる楕円曲線を用いて、スカラー値、及び、 楕円曲線上の点とからスカラー倍点を計算する楕円曲線暗号におけるスカラー倍計算方法であって、 楕円曲線の定義体はFqであり、 スカラー値を、第一の数値列（bn-1，bn-2，…，b0）（ｎは スカラー値を第一の数値列にエンコードした際の桁長）にエンコードする第一のステップと、 第一の数値列を、 第一の数値列とは異なる第二の数値列にエンコードする第二のステップと、
楕円曲線上の点から事前計算テーブルを作成する第三のステップと、 第二の数値列、及び、 事前計算テーブルから、
スカラー倍点を計算する第四のステップと、を備えることを特徴とするスカラー倍計算方法を提供する。
【００３６】
さらに、第一のステップは、前記スカラー値に対するΦ進展開を計算し、
第二のステップは、
bnとbn+1とbn+2とbn+3とを生成してそれぞれ0とするステップと（ｎはスカラー値に対するΦ進展開の桁長）、
iが0からnまでの間、
bi=0を満たすとき、biをbiとする変換を行った後iを1増加させ、
bi≠0、かつ、｜-qbi+1+bi｜≦（q2-1）/2を満たすとき、bi→-qbi+1+bi，bi+1→0，bi+2→-bi+1+bi+2とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi>（q2-1）/2を満たすとき、bi→- bi+1q+bi-q2，bi+1→0，bi+2→bi+2- bi+1-（q-1），bi+3→bi+3+1とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi<-（q2-1）/2を満たすとき、bi→- bi+1q+bi+q2，bi+1→0，bi+2→bi+2- bi+1+（q-1），
bi+3→bi+3-1とする変換を行った後iを2増加させる処理を繰り返す変換ステップと、を備えることを特徴とする。
【発明の効果】
【００３７】
本発明によれば、リソースが限られた環境で、安全性を低下させることなく、従来の楕円曲線演算よりさらに高速に処理可能な楕円曲線演算技術を実現することができる。
【図面の簡単な説明】
【００３８】
【図１】図1は、第一の実施形態の暗号通信システムのシステム構成を例示する図である。
【図２】図2は、第一の実施形態のコンピュータ内の各処理部間の情報の受け渡しを例示するための図である。
【図３】図3は、第一の実施形態のスカラー倍計算部の機能ブロック例である。
【図４】図4は、第一の実施形態のエンコード部の処理を例示するためのフローチャートである。
【図５】図5は、第一の実施形態の事前計算部の処理を例示するためのフローチャートである。
【図６】図6は、第一の実施形態の実計算部の処理を例示するためのフローチャートである。
【図７】図7は、第二の実施形態の署名検証システムのシステム構成を例示する図である。
【発明を実施するための形態】
【００３９】
以下、本発明を適用した第一の実施形態を図面により説明する。
【００４０】
図1は、本実施形態の暗号通信システムのシステム構成図である。本図に示すように、本実施形態の暗号通信システムは、ネットワーク142により接続されたコンピュータＡ101、コンピュータＢ121とを備える。
【００４１】
本実施形態の暗号通信システムにおいては、コンピュータＡ101でメッセージPmの暗号化を行い、コンピュータＢ121で暗号文の復号を行う。
【００４２】
kは乱数、dは秘密鍵を示す定数、Qは定点、dQは公開鍵を示す点とすると、コンピュータＡ101において、Pm+k（dQ）及びkQを計算して出力する。そして、コンピュータＢ121において、秘密鍵d、及び、kQより-d（kQ）を計算し、
（Pm+k（dQ））d（kQ） （式10）
を計算して出力する。
【００４３】
ここで、メッセージPmを復元するためには、kdQ、すなわちkQのd倍を計算する必要がある。ところが、暗号通信システムでは、ネットワーク142には、Pm+k（dQ）、kQが送信され、秘密鍵dは送信されないため、秘密鍵dを保持しているものだけが、Pmを復元できることになる。
【００４４】
図1において、コンピュータＡ101は、ＣＰＵ113やコプロセッサ114などの演算装置、ＲＡＭ103、ＲＯＭ106や外部記憶装置107などの記憶装置、コンピュータ外部とのデータ入出力を行う入出力インタフェース110を装備し、外部にはコンピュータＡ101をユーザが操作するためのディスプレイ108、キーボード109、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
【００４５】
更にコンピュータＡ101は、ＲＡＭ103、ＲＯＭ106や外部記憶装置107などの記憶装置によって、記憶部102を実現し、ＣＰＵ113やコプロセッサ114などの演算装置が、記憶部102に格納されたプログラムを実行することにより、データ処理部112、スカラー倍計算部115とそれらに含まれる各処理部を実現する。
【００４６】
データ処理部112は、本実施形態においては、暗号化処理部として機能し、入力されたメッセージの暗号化を行う。
【００４７】
スカラー倍計算部115は、データ処理部（暗号化処理部）112で暗号化を行うのに必要なパラメタを計算する。記憶部102は、定数104（例えば、楕円曲線の定義式や楕円曲線上の定点）、秘密情報105（例えば、秘密鍵）などを記憶している。
【００４８】
コンピュータＢ121は、コンピュータＡと同様のハードウェア構成を備え、ＣＰＵ133やコプロセッサ134などの演算装置、ＲＡＭ123、ＲＯＭ126や外部記憶装置127などの記憶装置、コンピュータ外部とのデータ入出力を行う入出力インタフェース130を装備し、外部にはコンピュータＢ101をユーザが操作するためのディスプレイ128、キーボード129、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
【００４９】
更にコンピュータＢ121は、ＲＡＭ123、ＲＯＭ126や外部記憶装置127などの記憶装置によって、記憶部122を実現し、ＣＰＵ133やコプロセッサ134などの演算装置が、記憶部122に格納されたプログラムを実行することにより、データ処理部132、スカラー倍計算部135とそれらに含まれる各処理部を実現する。
【００５０】
データ処理部132は、本実施形態においては、復号化処理部として機能し、暗号化されたメッセージである暗号文141の復号を行う。
【００５１】
スカラー倍計算部135は、データ処理部（復号化処理部）132で復号化を行うのに必要なパラメタを計算する。記憶部122は、定数124（例えば、使用する楕円曲線の定義式や楕円曲線上の定点）、秘密情報125（例えば、秘密鍵）などを記憶している。
【００５２】
なお、上記プログラムは、予め上記コンピュータ内の記憶部102、122に格納されていてもよいし、必要な時に、入出力インタフェース110、130および上記コンピュータが利用可能な媒体を介して、他の装置から上記記憶部102、122に導入されてもよい。媒体とは、例えば、入出力インタフェースに着脱可能な記憶媒体、または通信媒体（すなわち、ネットワークまたはネットワークを伝搬するディジタル信号や搬送波）を指す。
【００５３】
次に、メッセージの暗号化処理および復号化処理を行う場合の、それぞれ、コンピュータＡ101およびコンピュータＢ121内の各処理部間での情報の送受信について説明する。図2は、コンピュータＡ101、コンピュータＢ121の各処理部が行う情報の受け渡しを説明するための図である。
【００５４】
まず、コンピュータＡ101が、入力されたメッセージを暗号化する場合の動作について説明する。メッセージはディジタル化されたデータであればよく、テキスト、画像、映像、音などの種類は問わない。
【００５５】
データ処理部（暗号化処理部）112は、入出力インタフェース110を介して、平文メッセージ（入力メッセージ）を受け取ると（ステップ204）、入力された平文メッセージのビット長があらかじめ定めたビット長か否かを判断する。予め定めたビット長よりも長い場合には、予め定めたビット長となるように平文メッセージを区切る。以下、メッセージは、所定のビット長に区切られている部分メッセージ（単にメッセージと呼ぶ。）であるものとして説明する。
【００５６】
次に、データ処理部（暗号化処理部）112は、メッセージのビット列によって表される数値をx座標（x1）に持つ楕円曲線上の点Pmのy座標（y1）の値を計算する。
【００５７】
例えば、使用する楕円曲線をワイエルシュトラス型楕円曲線とすると、ワイエルシュトラス型楕円曲線は、a，bを定数とするとき、
y12=x13+ax1+b （式11）
で表されるので、本式によりy座標の値を求めることができる。
【００５８】
次に、データ処理部（暗号化処理部）112は、乱数kを生成する。そして記憶部102に格納されている定数104から公開鍵dQとQのx座標とを読み出す（ステップ205）。そして、読み出した公開鍵dQとQのx座標と、求めたy座標の値と、乱数kとをスカラー倍計算部115へ送る（ステップ206）。
【００５９】
スカラー倍計算部115は、Qのx座標、y座標の値、乱数kによるスカラー倍点（xd1，yd1）=kQと、公開鍵dQのx座標、y座標の値、乱数によるスカラー倍点（xd2，yd2）=k（dQ）とを計算し、計算したスカラー倍点をデータ処理部（暗号化処理部）112へ送る（ステップ207）。
【００６０】
データ処理部（暗号化処理部）112は、受け取ったスカラー倍点を用いて、暗号化処理を行う。例えば、ワイエルシュトラス型楕円曲線の場合、Pm+k（dQ）とkQを計算する。すなわち、
xe1=（（yd1-y1）/（xd1-x1））2-x1-xd1 （式12）
xe2=xd2 （式13）
を計算し、暗号化されたメッセージxe1，xe2を得る。
【００６１】
コンピュータＡ101はデータ処理部（暗号化処理部）112で暗号化された1つ以上の部分メッセージから暗号化された出力メッセージを組み立て、データ141として入出力インタフェース110より出力する（ステップ208）。データ141は、ネットワーク142を介してコンピュータＢ121へ転送される。
【００６２】
なお、図2において記憶部102からの情報の読み出し（ステップ205）は、スカラー倍計算部115へ当該情報を送る前であればよい。例えば、入力メッセージを受け付ける（ステップ204）前であってもよい。
【００６３】
次に、コンピュータＢ121が、暗号化されたメッセージであるデータ141を復号化する場合の動作について、同じく図2を用いて説明する。
【００６４】
データ処理部（復号化処理部）132は、入出力インタフェース110を介して、暗号化されたデータ141が入力メッセージとして入力されると（ステップ204）、データ141のビット長が予め定めたビット長か否かを判断する。予め定めたビット長よりも長い場合は、予め定めたビット長となるように暗号化されたデータを区切る。以下、メッセージは、所定のビット長に区切られている部分データ（単にデータともいう）であるものとして説明する。
【００６５】
データ処理部（復号化処理部）132は、データ141のビット列によって表される数値をx座標にもつ楕円曲線上のy座標の値を計算する。
【００６６】
暗号化されたメッセージがxe1，xe2のビット列であり、ワイエルシュトラス型楕円曲線の場合、y座標の値（ye1）は、
ye12=xe13+axe1+b （式14）
（ただし、a，bはそれぞれ（式11）と同じ定数である。）から得ることができる。
【００６７】
データ処理部（復号化処理部）132は、記憶部122に格納されている秘密情報125から秘密鍵dを読み出す（ステップ205）。そして、読み出した秘密鍵dと、x座標、y座標の値（xe2，ye2）を、スカラー倍計算部135へ送る（ステップ206）。
【００６８】
スカラー倍計算部135は、x座標、y座標の値、秘密情報125（秘密鍵ｄ）を用いてスカラー倍点（xd3，yd3）=d（xe2，ye2）を計算する。スカラー倍計算部135は、計算されたスカラー倍点をデータ処理部（復号化処理部）132へ送る（ステップ207）。データ処理部（復号化処理部）132は、送られたスカラー倍点を用いて、復号化処理を行う。
【００６９】
例えば、暗号化されたメッセージが、xe1，xe2のビット列であり、ワイエルシュトラス型楕円曲線の場合は、
（Pm+k（dQ））d（kQ）=（xe1，ye1）-（xd3，yd3） （式15）
を計算することにより達成できる。すなわち、
xf1=（（ye1+yd3）/（xe1-xd3））2-xe1-xd3 （式16）
を計算し、暗号化される前の部分メッセージx1に相当するxf1を得る。
【００７０】
コンピュータＢ121は、データ処理部（復号化処理部）132で復号された部分メッセージから平文メッセージを組み立て、入出力インタフェース110を介して、ディスプレイ108などから出力する（ステップ208）。
【００７１】
次に、本実施形態において、コンピュータＡ101が、暗号化処理を行う場合の、スカラー倍計算部115の処理を詳細に説明する。なお、コンピュータＢ101が復号化処理を行う場合のスカラー倍計算部135の処理も基本的に同様である。このため、以下においては、スカラー倍計算部115の処理を代表して説明する。
【００７２】
本実施形態のスカラー倍計算部115の機能ブロックを図3に示す。本図に示すように、本実施形態のスカラー倍計算部115は、エンコード部302と、事前計算部303と、実計算部304とを備える。
【００７３】
また、エンコード部302は、Φ進展開部321、δ剰余取得部322、ビット対判定部323、ビット対変換部324、桁上がり計算部325、繰り返し判定部326を備える。事前計算部303は、加算部331、2倍算部332、繰り返し判定部333を備える。実計算部304は、ビット値判定部341、加算部342、Φ倍算部343、繰り返し判定部344を備える。
【００７４】
スカラー倍計算部115が、これらの機能を用いて、スカラー値dと整数倍算とは異なる自己準同型写像Φを持つ楕円曲線上の点Pとから、楕円曲線におけるスカラー倍点dPを計算する第1の計算方法を説明する。
【００７５】
以下、本実施形態においては、自己準同型写像Φとして、例えば、フロベニウス写像を用いることができる。すなわち、本計算方法は、上記非特許文献1に記載されているスカラー値のフロベニウス展開に、上記非特許文献4に記載されている整数展開rNAFを適用したエンコード方法であり、以下、本エンコード方法をFrNAF（Frobenius - adic Radix-r Non - Adjacent Form）と呼ぶ。
【００７６】
スカラー値のフロベニウス展開にrNAFを適用するために、本実施形態では、特性多項式Φ2+Φ+q（ｑは奇素数のべき）を持つ、定義体Fq上定義された楕円曲線上の、整数倍算とは異なる自己準同型写像Φを実行することができる楕円曲線を選択する。
【００７７】
また、本楕円曲線上の点とスカラー値とからスカラー倍点を計算するにあたり、スカラー値を第一の数値列にエンコードした後、さらに、第一の数値列とは異なる第二の数値列にエンコードし、第二の数値列を用いてスカラー倍点を計算する。このとき、第一の数値列は、スカラー値をΦ進展開することにより得、第二の数値列は、前記第一の数値列の隣り合う２桁が予め定められた条件を満たすか否かに応じて変換を行う。すなわち、満たさない場合、その２桁と、当該２桁と隣り合う１桁、または２桁のそれぞれに対し演算を行い、変換後の数値列を第一の数値列とし、本処理を繰り返す。
【００７８】
この第二の数値列とこの楕円曲線上の点とを用いてスカラー倍計算を実行することにより、高速化を実現する。以下、上記計算方法を具体的に説明する。
【００７９】
まず、本実施形態のスカラー倍計算処理全体の概要を説明する。
【００８０】
スカラー倍計算部115が暗号化処理部112からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部302は、入力されたスカラー値dから値d’を計算し、値d’を数値列eiにエンコードする。すなわち、
d’=e0+e1Φ+e2Φ2+…+en+3Φn+3 （式17）
-（q2-1）/2≦ei≦（q2-1）/2 （式18）
ei mod q≠0（ei≠0のとき） （式19）
を満たすeiに、スカラー値d’を変換する。
【００８１】
ここで、d'は
δ=(Φn-1)/(Φ-1) （式20）
を満たす複素数δに対して
d=δQ+d' （式21）
を満たす整数であり、Qは複素数である。
また、（式17）の各iについて、隣り合う数値の対（ei+1, ei）は以下の条件
ei+1ei=0 （式22）
を満たし、kは
k≦[2logq2√|d'|]+4 （式23）
を満たす整数である。
【００８２】
なお、対（ei+1，ei）が、上記（式22）を満たすとき、対（ei+1，ei）は非隣接対であるという。
【００８３】
事前計算部303は、事前計算テーブルを作成する。事前計算テーブルは、
iP（i=1，…，（q2-1）/2） （式24）
を保持する。ただし、iは
i mod q≠0 （式25）
を満たす。
【００８４】
実計算部304は、エンコードされたスカラー値d=（en+3，en+2，…，e1，e0）と事前計算テーブルに保持されているデータとを用いてスカラー倍点dPを計算する。
【００８５】
次に、上記スカラー倍計算処理時のエンコード部302、事前計算部303、実計算部304の行う各処理について詳細に説明する。
【００８６】
まず、図4を用いて本実施形態のエンコード部302の行う処理について説明する。ここでは、スカラー値を第一の数値列にエンコードし、さらに、第一の数値列を第二の数値列にエンコードする処理を行う。図4は、本実施形態のエンコード部302の処理を説明するためのフローチャートである。
【００８７】
エンコード部302は、スカラー値dの入力を受ける（ステップ401）。
【００８８】
δ剰余取得部322は、受け取ったスカラー値dに対して、第一の実施形態の（式21）を満たす整数d'を計算する。そして、Φ進展開部321は、整数d'を、
d'=c0+c1Φ+…+cn-1Φn-1 （式26）
|ci|≦（q-1）/2 （式27）
に変換する（ステップ402）。
【００８９】
スカラー値dから整数d'を計算する方法、及び、整数d'を、（式26）、（式27）を満たすように展開する方法は、非特許文献1に記載されている。すなわち、以下の処理ｉ）、ｉｉ）を繰り返すことにより得られる。
ｉ）スカラー値dをδで割り、その余りをd'とする。
ｉｉ）整数d'をΦで割り、その余りをciとする。
【００９０】
次に、第一の数値列（c0，c1，c2，…cn-1）から（b0，b1，b2，…bn-1，bn，bn+1，bn+2，bn+3）を経て、第二の数値列（e0，e1，…en，en+1，en+2，en+3）を生成する。
【００９１】
まず、ビット対変換部324は、b0にc0を、b1にc1を、bnに0を、bn+1に0を、bn+2に0を、bn+3に0をそれぞれ代入する（ステップ403）。
【００９２】
繰り返し判定部326は、iに0を代入する（ステップ404）。
【００９３】
繰り返し判定部326は、i≦n+2であるかどうかを判定する（ステップ405）。i≦n+2が成立する場合、ステップ406へ行く。i≦n+2が成立しない場合、ステップ413へ行く。
【００９４】
ビット対判定部323は、bi=0であるかどうかを判定する（ステップ406）。bi=0である場合、ステップ407へ行く。bi=0でない場合、ステップ408へ行く。
【００９５】
桁上がり計算部325は、bi+2にci+2を代入し、格納部327は、eiに0を代入し、iにi+1を代入し、ステップ405へ行く（ステップ407）。
【００９６】
ビット対判定部323は、|-bi+1q+bi|≦（q2-1）/2であるかどうかを判定する（ステップ408）。|-bi+1q+bi|≦（q2-1）/2である場合、ステップ409へ行く。|-bi+1q+bi|≦（q2-1）/2でない場合、ステップ410へ行く。
【００９７】
桁上がり計算部325は、bi+3にci+3を、bi+2にci+2-bi+1をそれぞれ代入し、格納部327は、ei+1に0を、eiに-bi+1q+biを代入し、iにi+2を代入し、ステップ405へ行く（ステップ409）。
【００９８】
ビット対判定部323は、-bi+1q+bi<-（q2-1）/2であるかどうかを判定する（ステップ410）。-bi+1q+bi<-（q2-1）/2である場合、ステップ411へ行く。-bi+1q+bi<-（q2-1）/2でない場合、ステップ412へ行く。
【００９９】
桁上がり計算部325は、bi+3にci+3-1を、bi+2にci+2-bi+1+（q-1）をそれぞれ代入し、格納部327は、ei+1に0を、eiに-bi+1q+bi+q2を代入し、iにi+2を代入し、ステップ405へ行く（ステップ411）。
【０１００】
桁上がり計算部325は、bi+3にci+3+1を、bi+2にci+2-bi+1-（q-1）をそれぞれ代入し、格納部327は、ei+1に0を、eiに-bi+1q+bi-q2を代入し、iにi+2を代入し、ステップ405へ行く（ステップ412）。
【０１０１】
エンコード部302は、（en+3，en+2，…，e1，e0）を出力する（ステップ413）。
【０１０２】
なお、q≦5の場合、以下のステップを追加する。
【０１０３】
ステップ406でbi=0であるかどうかを判定する前に、biがqで割り切れるかどうかを判定する。biがqで割り切れる場合、bi+1にbi+1-bi/qを、bi+ 2にci+2-bi/qを、それぞれ代入し、iにi+1を代入する。
【０１０４】
次に図5を用いて本実施形態の事前計算部303の行う処理について説明する。図5は、本実施形態の事前計算部303の処理を説明するためのフローチャートである。ここでは、事前計算テーブルに保持するデータを生成する。事前計算テーブルに保持するデータは、上述のとおり、楕円曲線上の点Ｐの値、点Ｐのスカラー倍点の値2P、3P、…、((q2 - 1)/2)P（ただし、点iP(i = q， 2q ，…，((q - 1)/2)P)は含まれない。）である。
【０１０５】
事前計算部303は、Q1にPを代入し、2倍算部332は、点Pの2倍点2Pを計算し、事前計算部303は、Q2に2Pを代入する（ステップ501）。
【０１０６】
繰り返し判定部333は、iに2を代入する（ステップ502）。
【０１０７】
繰り返し判定部333は、i≦（q2-1）/2であるかどうかを判定する（ステップ503）。i≦（q2-1）/2である場合、ステップ504へ行く。i≦（q2-1）/2でない場合、ステップ508へ行く。
【０１０８】
剰余判定部334は、i mod q≡0であるかどうかを判定する（ステップ504）。i mod q≡0である場合、ステップ506へ行く。i mod q≡0でない場合、ステップ505へ行く。
【０１０９】
加算部331は、Qi+Pを計算し、事前計算部303は、その結果をQi+1に代入する（ステップ505）。
【０１１０】
加算部331は、Qi+Pを計算し、事前計算部303は、その結果をQi+2に代入する（ステップ506）。
【０１１１】
繰り返し判定部333は、iにi+1を代入し、ステップ503へ行く（ステップ507）。
【０１１２】
事前計算部303は、点Q1，…，Q（q2-1）/2を事前計算テーブルに格納する（ステップ508）。ただし、上記Qiで、iはqの倍数ではない。
【０１１３】
最後に、図6を用いて実計算部304の行う処理について説明する。ここでは、エンコード部302により得られたエンコードされたスカラー値と、事前計算部303で得られたデータとから、スカラー倍点dPを計算する。図6は、本実施形態の実計算部304の処理を説明するためのフローチャートである。
【０１１４】
繰り返し判定部344は、iにn+3を代入する（ステップ601）。
【０１１５】
ビット値判定部341は、ei≠0であるかどうかを判定する（ステップ602）。ei≠0である場合、ステップ603へ行く。ei≠0でない場合、ステップ604へ行く。
【０１１６】
繰り返し判定部344は、iにi-1を代入する（ステップ603）。
【０１１７】
加算部342は、QにeiPを代入する（ステップ604）。
【０１１８】
繰り返し判定部344は、iにi-1を代入する（ステップ605）。
【０１１９】
繰り返し判定部344は、i≧0であるかどうかを判定する（ステップ606）。i≧0である場合、ステップ607へ行く。i≧0でない場合、ステップ611へ行く。
【０１２０】
Φ倍算部343は、Φ（Q）を計算し、Qに代入する（ステップ607）。
【０１２１】
ビット値判定部341は、ei≠0であるかどうかを判定する。ei≠0である場合、ステップ609へ行く。ei≠0でない場合、ステップ610へ行く。（ステップ608）
加算部342は、Q+eiPを計算し、Qに代入する（ステップ609）。
【０１２２】
繰り返し判定部344は、iにi-1を代入し、ステップ606へ行く（ステップ610）。
【０１２３】
実計算部304は、Qを出力する（ステップ611）。
【０１２４】
以上の処理により、エンコード部302から出力されるeiは、（式17）を満たし、対（ei+1，ei）は、（式22）を満たす。この理由は次の通りである。
【０１２５】
ステップ406の直前で、bi+1，biはそれぞれ、|bi+1|≦（q-1）/2，|bi|≦q-1、または、|bi+1|≦（q+1）/2，|bi|≦2q-1（bi≠±q）を満たす。対（bi+1，bi）が隣接対のときは、ステップ407へ行く。対（bi+1，bi）が非隣接対の場合を考える。このとき、ステップ409、ステップ411、ステップ412の何れの場合も、ei+1=0となり、対（ei+1，ei）は（式22）を満たす。
【０１２６】
また、エンコード部302が行う処理により、整数d'のΦ進展開の長さは（式23）を満たす。これは、ステップ406からステップ412の処理ループにおいて、すべてのiに対して（式17）を満たすように整数d'を変換するため、整数d'のΦ展開の長さは（式23）を満たすことがわかる。
【０１２７】
実計算部304が出力する点Qはスカラー倍点dPに等しい。この理由は、（式17）、（式20）、（式23）から明らかである。
【０１２８】
整数d'のFrNAF表現は一意的である。この理由は通常のrNAF表現の一意性と同様である。
【０１２９】
以上の通り、本実施形態のスカラー倍計算方法によれば、Koblitz曲線や整数倍算とは異なる自己準同型写像を実行することができるトレースが1かつ定義体の標数が奇数である楕円曲線以外の楕円曲線を用い、非零濃度を小さくすることができ、スカラー倍計算処理を高速化することができる。また、楕円曲線の制限は、整数倍算とは異なる自己準同型写像Φを持つこと、及び、上記楕円曲線のトレースが-１であることであるため、幅広い楕円曲線を選択可能である。このため、より高い安全性が期待できる。
【０１３０】
すなわち、本実施形態によれば、楕円曲線暗号が持つ高い安全性とリソース利用効率の良さを保ちつつ、高速性に優れたメッセージ処理が可能になる。
【０１３１】
次に、本発明を適用した署名検証システムを第二の実施形態として説明する。
【０１３２】
図7は、本実施形態の署名検証システムのシステム構成図である。本図に示すように、本実施形態の署名検証システムは、スマートカード701と署名検証処理を行うコンピュータ721とを備える。
【０１３３】
スマートカード701は、第一の実施形態および第二の実施形態の図1のコンピュータＡ101と類似の構成を備える。すなわち、コンピュータＡ101の同名の構成は基本的に同じ機能を有する。ただし、スマートカード701は、ＣＰＵ713、コプロセッサ714などの演算装置が記憶部702に格納されているプログラムを実行することにより、データ処理部111とスカラー倍計算部115の代わりに、署名生成処理部712とスカラー倍計算部715とを実現する。なお、図1に示す外部記憶装置107、ディスプレイ108、キーボード109を備えなくてもよい。
【０１３４】
一方、コンピュータ721は、コンピュータＡ101と同様の構成を備える。すなわち、図1に示すコンピュータＡ101と同名の構成は、同様の機能を有する。ただし、ＣＰＵ733、コプロセッサ734などの演算装置が記憶部722に格納されているプログラムを実行することにより、データ処理部111とスカラー倍計算部115の代わりに、署名検証処理部732とスカラー倍計算部735とを実現する。
【０１３５】
なお、スカラー倍計算部715と735は、図1に示すスカラー倍計算部115または135と同様の機能を備える。
【０１３６】
本実施形態においても、第一の実施形態同様、コンピュータ721内の各プログラムは、予め、コンピュータ721内の記憶部722に格納されていても良いし、必要なときに、コンピュータ721が利用可能な媒体を介して、他の装置から記憶部722に導入されてもよい。
【０１３７】
さらに、スマートカード701内の各プログラムは、予め、スマートカード701内の記憶部702に格納されていても良いし、必要なときに、入出力インタフェース710を介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して、記憶部702に導入されてもよい。媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【０１３８】
次に、本実施形態の署名検証システムにおける署名生成と署名検証動作を、図2を参照して説明する。なお、本実施形態においては、図2のデータ処理部112、132は、署名生成処理部712、署名検証処理部732、スカラー倍計算部115、135は、スカラー倍計算部715、735、記憶部122、102は、記憶部702、722として以下、説明する。
【０１３９】
離散対数問題に基づくディジタル署名方法を楕円曲線上の離散対数問題に基づく方法に対応させて構成する楕円曲線ディジタル署名アルゴリズム（ECDSA）という署名方法がある。ECDSA署名については、例えば、
D. Johnson， A. Menezes, The Elliptic Curve Digital
Signature Algorithm (ECDSA), Technial Report CORR 99-34, Dept. of C&O,
University of Waterloo, Canada.
<URL>
http://www.cacr.math.uwaterloo.ca/techreports/1999/corr99-34.pdf
に記載されている。
【０１４０】
コンピュータ721は、ランダムに選んだ数値をチャレンジコード742として、インタフェースを介してスマートカード701に転送する。
【０１４１】
署名生成処理部712は、チャレンジコード742を入力メッセージとして受け付け（ステップ204）、チャレンジコード742のハッシュ値をとり、所定のビット長の数値fに変換する。
【０１４２】
署名生成処理部712は、乱数uを生成し、記憶部702に格納されている定数704から楕円曲線上の定点Qを読み出す（ステップ205）。生成した乱数uを読み出した楕円曲線上の定点Qとともにスカラー倍計算部715へ送る（ステップ206）。
【０１４３】
スカラー倍計算部715は、定点Q、乱数uを用いてスカラー倍点uQ=（xu，yu）を計算し、計算されたスカラー倍点を署名生成処理部712へ送る（ステップ207）。
【０１４４】
署名生成処理部712は、送られたスカラー倍点を用いて署名の生成を行う。例えば、上述のECDSA署名であれば、
s=xu mod q （式28）
t=u-1（f+ds） mod q （式29）
を計算することにより、チャレンジコード742に対応する署名（s，t）741を得る。
【０１４５】
ここで、qは定点Qの位数、すなわち、定点Qのq倍点qQが無限遠点になり、qより小さな数値mに対する定点Qのm倍点mQは無限遠点にはならない、という数値のことである。
【０１４６】
スマートカード701は、署名生成処理部712で生成した署名741を入出力インタフェース710より出力し（ステップ208）、インタフェースを介してコンピュータ721へ転送する。
【０１４７】
コンピュータ721の署名検証処理部732は、署名741が入力されると（ステップ204）、署名741の数値s，tが適切な範囲内すなわち1≦s，t<qであるかを調べる。
【０１４８】
数値s，tが上記範囲内になければチャレンジコード742に対する署名の検証結果として「無効」を出力し、スマートカード701を拒絶する（ステップ208）。
【０１４９】
一方、数値s，tが上記範囲内にあれば、署名検証処理部732は、
h=t-1 mod q （式30）
h1=fh mod q （式31）
h2=sh mod q （式32）
を計算する。
【０１５０】
署名検証処理部732は、記憶部722に格納されている定数724から公開鍵dQ及び定点Qを読み出す（ステップ205）。そして、読み出した公開鍵dQ及び定点Qと、計算したh1，h2とを、スカラー倍計算部735へ送る（ステップ206）。
【０１５１】
スカラー倍計算部735は、定点Qとh1とによるスカラー倍点h1Qと、公開鍵dQとh2とによるスカラー倍点h2dQとを計算し、計算されたスカラー倍点を署名検証処理部732へ送る（ステップ207）。
【０１５２】
署名検証処理部732は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ECDSAの署名検証であれば、点Rを以下の式により計算し、
R=h1Q+h2dQ （式33）
そのx座標をxRとしたとき、
s'=xR mod q （式34）
を計算し、s'=sであればチャレンジコード742に対する署名の検証結果として「有効」を出力し（ステップ208）、スマートカード701を認証し、受け入れる。
【０１５３】
一方、s'=sでなければ「無効」を出力し（ステップ208）、スマートカード701を拒絶する。
【０１５４】
上述のように、署名の生成および検証の処理において、スカラー倍点を計算する。従って、署名生成、及び、署名検証を行う際に、第一の実施形態のスカラー倍計算方法を用いることが可能である。この実施形態のスカラー倍計算方法を用いることにより、スマートカードといったリソースが限られた環境においても、高い安全性と高速な処理とを実現することができる。
【０１５５】
次に、本発明を楕円Diffie-Hellman鍵共有スキーム適用して実現する鍵交換システムを第三の実施形態として説明する。本実施形態の鍵交換システムのシステム構成は、図１と同様である。ただし、図1のデータ処理部112、132は、本実施形態においては、それぞれ鍵交換処理部112、132として機能する。
【０１５６】
以下、本実施形態の鍵交換システムのコンピュータＡ101が、入力されたデータ143から共有情報の導出を行う場合の動作について図1、図2を参照して説明する。図2においても、データ処理部112、132は、鍵交換処理部112、132として説明する。
【０１５７】
コンピュータＢ121の鍵交換処理部132は、記憶部122の秘密情報125から秘密鍵bを読み出し、コンピュータＢ121の公開鍵bQを計算する。そして、鍵交換処理部132は、ネットワーク142を介して、公開鍵bQをデータ143としてコンピュータＡ101に転送する（ステップ208）。
【０１５８】
コンピュータＡ101の鍵交換処理部112は、コンピュータＢ121の公開鍵bQのデータ143を入力メッセージとして受け付ける（ステップ204）。
【０１５９】
鍵交換処理部112は、記憶部102から秘密情報105であるコンピュータＡ101の秘密鍵dを読み出し（ステップ205）、秘密鍵dとコンピュータＢ121の公開鍵bQとをスカラー倍計算部115へ送る（ステップ206）。
【０１６０】
スカラー倍計算部115は、公開鍵bQによるスカラー倍点dbQを計算し、計算したスカラー倍点と秘密鍵dとを鍵交換処理部112へ送る（ステップ207）。
【０１６１】
鍵交換処理部112は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部102に秘密情報105として格納する。例えば、スカラー倍点dbQのx座標を、共有情報とする。
【０１６２】
次に、コンピュータＢ121が、入力されたデータ141から共有情報の導出を行う場合の動作について説明する。
【０１６３】
コンピュータＡ101の鍵交換処理部112は、記憶部102の秘密情報105から秘密鍵dを読み出しコンピュータＡ101の公開鍵dQを計算する。そして、ネットワーク142を介して、公開鍵dQをデータ141としてコンピュータＢ121に転送する（ステップ208）。
【０１６４】
コンピュータＢ121の鍵交換処理部132は、コンピュータＡ101の公開鍵dQであるデータ141を、入力メッセージ204として受け付ける（ステップ204）。
【０１６５】
鍵交換処理部132は、記憶部122の定数125から秘密情報125であるコンピュータＢ121の秘密鍵bを読み出し（ステップ205）、読み出した秘密鍵bとコンピュータＡ101の公開鍵dQとをスカラー倍計算部135へ送る（ステップ206）。
【０１６６】
スカラー倍計算部135は、公開鍵dQによるスカラー倍点bdQを計算し、計算されたスカラー倍点と秘密鍵bとを鍵交換処理部132へ送る（図2の207）。
【０１６７】
鍵交換処理部132は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部122に秘密情報125として格納する。例えば、スカラー倍点bdQのx座標を、共有情報とする。
ここで、数dbと数bdとは数値として同じなので、点dbQと点bdQとは同じ点となり、同じ情報が導出されたことになる。
【０１６８】
ネットワーク142には、点dQと点bQが送信される。しかし、点dbQ（もしくは点bdQ）を計算するためには、秘密鍵dもしくは秘密鍵bが必要である。すなわち、秘密鍵dもしくは秘密鍵bを知らなければ、共有情報を得ることはできない。従って、上記の方法で得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。
【０１６９】
本実施形態の鍵交換システムでは、受け取った点のスカラー倍点を計算する。従って、鍵交換を行う際に、第一の実施形態のスカラー倍計算方法を用いることが可能である。この実施形態のスカラー倍計算方法を用いることにより、高い安全性と高速な処理とを実現することができる。
【０１７０】
なお、上記各実施形態では、暗号化処理部、復号化処理部、署名生成処理部、署名検証処理部、鍵交換処理部を、ソフトウェアで実現するものとして説明したが、専用のハードウェアを用いて実現してもよい。また、スカラー倍計算部をコプロセッサまたはそれ以外の専用ハードウェアで実現しても良い。また、データ処理部は、上記暗号化処理、復号化処理、署名生成処理、署名検証処理、鍵交換処理のうち、任意の一つ以上の処理を行うことができるよう構成してもよい。
【符号の説明】
【０１７１】
101：コンピュータＡ、102：記憶部、103：RAM、104：定数、105:秘密情報、106：ROM、107：外部記憶装置、108：ディスプレイ、109：キーボード、110：入出力インタフェース、111：処理部、112：データ処理部、113：CPU、114：コプロセッサ、115：スカラー倍計算部、121：コンピュータＢ、122：記憶部、123：RAM、124：定数、125：秘密情報、126：ROM、127：外部記憶装置、128：ディスプレイ、129：キーボード、130：入出力インタフェース、131：処理部、132：データ処理部、133：CPU、134：コプロセッサ、135：スカラー倍計算部、141：データ、142：ネットワーク、143：データ、302：エンコード部、303：事前計算部、304：実計算部、321：Φ進展開部、322：δ剰余取得部、323：ビット対判定部、324：ビット対変換部、325：桁上がり計算部、326：繰り返し判定部、327：格納部、331：加算部、332：2倍算部、333：繰り返し判定部、341：ビット値判定部、342：加算部、343：Φ倍算部、344：繰り返し判定部、701：スマートカード、702：記憶部、703：RAM、704：定数、705：秘密情報、706：ROM、710：入出力インタフェース、711：処理部、712：署名生成処理部、713：CPU、714：コプロセッサ、715：スカラー倍計算部、721：コンピュータ、722：記憶部、723：RAM、724：定数、725：秘密情報、726：ROM、727：外部記憶装置、728：ディスプレイ、729：キーボード、730：入出力インタフェース、731：処理部、732：署名検証処理部、733：CPU、734：コプロセッサ、735：スカラー倍計算部、741：署名、742：チャレンジコード。
【特許請求の範囲】
【請求項１】
CPUがメモリに格納されたプログラムを実行することによりコンピュータ上に実現されるスカラー倍計算装置において、特性多項式Φ2+Φ+q（ｑは奇素数のべき）を持つ、定義体Fq上定義された楕円曲線上の整数倍算とは異なる自己準同型写像Φを実行することができる楕円曲線を用いて、スカラー値、及び、前記楕円曲線上の点とからスカラー倍点を計算する楕円曲線暗号におけるスカラー倍計算方法であって、
前記スカラー値を、第一の数値列（bn-1，bn-2，…，b0）（ｎは前記スカラー値を第一の数値列にエンコードした際の桁長）にエンコードする第一のステップと、
前記第一の数値列を、前記第一の数値列とは異なる第二の数値列にエンコードする第二のステップと、
前記楕円曲線上の点から事前計算テーブルを作成する第三のステップと、
前記第二の数値列、及び、前記事前計算テーブルから、前記スカラー倍点を計算する第四のステップと、を備える
ことを特徴とするスカラー倍計算方法。
【請求項２】
請求項１に記載のスカラー倍計算方法であって、
前記第一のステップは、前記スカラー値に対するΦ進展開を計算し、
前記第二のステップは、
bnとbn+1とbn+2とbn+3とを生成してそれぞれ0とするステップと（ｎは前記スカラー値に対するΦ進展開の桁長）、
iが0からnまでの間、
bi=0を満たすとき、biをbiとする変換を行った後iを1増加させ、
bi≠0、かつ、｜-qbi+1+bi｜≦（q2-1）/2を満たすとき、bi→-qbi+1+bi，bi+1→0，bi+2→-bi+1+bi+2とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi>（q2-1）/2を満たすとき、bi→-bi+1q+bi-q2，bi+1→0，bi+2→bi+2-bi+1-（q-1），bi+3→bi+3+1とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi<-（q2-1）/2を満たすとき、bi→-bi+1q+bi+q2，bi+1→0，bi+2→bi+2-bi+1+（q-1），
bi+3→bi+3-1とする変換を行った後iを2増加させる処理を繰り返す変換ステップと、を備える
ことを特徴とするスカラー倍計算方法。
【請求項３】
特性多項式Φ2+Φ+q（ｑは奇素数のべき）を持つ、定義体Fq上定義された楕円曲線上の整数倍算とは異なる自己準同型写像Φを実行することができる楕円曲線を用いて、スカラー値、及び、前記楕円曲線上の点とからスカラー倍点を計算する楕円曲線暗号におけるスカラー倍計算装置であって、
前記スカラー値を、第一の数値列（bn-1，bn-2，…，b0）（ｎは前記スカラー値を第一の数値列にエンコードした際の桁長）にエンコードする第一のエンコード手段と、
前記第一の数値列を、前記第一の数値列とは異なる第二の数値列にエンコードする第二のエンコード手段と、
前記楕円曲線上の点から事前計算テーブルを作成する事前計算手段と、
前記第二の数値列、及び、前記事前計算テーブルから、前記スカラー倍点を計算する実計算手段と、を備える
ことを特徴とするスカラー倍計算装置。
【請求項４】
請求項３に記載のスカラー倍計算装置であって、
前記第一のエンコード手段では、前記スカラー値に対するΦ進展開を計算することにより前記第一の数値列にエンコードし、
前記第二のエンコード手段では、
bnとbn+1とbn+2とbn+3とを生成してそれぞれ0とし、
iが0からnまでの間、
bi=0を満たすとき、biをbiとする変換を行った後iを1増加させ、
bi≠0、かつ、｜-qbi+1+bi｜≦（q2-1）/2を満たすとき、bi→-qbi+1+bi，bi+1→0，bi+2→-bi+1+bi+2とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi>（q2-1）/2を満たすとき、bi→-bi+1q+bi-q2，bi+1→0，bi+2→bi+2-bi+1-（q-1），bi+3→bi+3+1とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi<-（q2-1）/2を満たすとき、bi→-bi+1q+bi+q2，bi+1→0，bi+2→bi+2-bi+1+（q-1），
bi+3→bi+3-1とする変換を行った後iを2増加させる処理を繰り返すことにより、前記第一の数値列を前記第二の数値列にエンコードする
ことを特徴とするスカラー倍計算装置。
【請求項５】
請求項３または４に記載のスカラー倍計算装置であって、
前記自己準同型写像はフロベニウス写像である
ことを特徴とするスカラー倍計算装置。
【請求項６】
データから署名データを生成する署名生成処理部と、前記署名データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する署名生成装置であって、
前記スカラー倍計算部は、請求項３ないし請求項５いずれか一に記載のスカラー倍計算装置を用いてスカラー倍点を計算する手段を備える
ことを特徴とする署名生成装置。
【請求項７】
データから署名データを検証する署名部と、前記署名データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する署名検証装置であって、
前記スカラー倍計算部は、請求項３ないし請求項５いずれか一に記載のスカラー倍計算装置を用いてスカラー倍点を計算する手段を備える
ことを特徴とする署名生成装置。
【請求項８】
データから暗号化データを生成する暗号部と、前記暗号化データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する暗号化装置であって、
前記スカラー倍計算部は、請求項３ないし請求項５いずれか一に記載のスカラー倍計算装置を用いてスカラー倍点を計算する手段を備える
ことを特徴とする暗号化装置。
【請求項９】
暗号化データから復号化データを生成する復号部と、前記復号化データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する復号化装置であって、
前記スカラー倍計算部は、請求項３ないし請求項５いずれか一に記載のスカラー倍計算装置を用いてスカラー倍点を計算する手段を備える
ことを特徴とする復号化装置。
【請求項１０】
楕円Diffie-Hellman鍵共有スキームにおいて、秘密鍵から公開鍵を生成する生成部と、前記公開鍵を生成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する鍵生成装置であって、
前記スカラー倍計算部は、請求項３ないし請求項５いずれか一に記載のスカラー倍計算装置を用いてスカラー倍点を計算する手段を備える
ことを特徴とする鍵生成装置。
【請求項１】
CPUがメモリに格納されたプログラムを実行することによりコンピュータ上に実現されるスカラー倍計算装置において、特性多項式Φ2+Φ+q（ｑは奇素数のべき）を持つ、定義体Fq上定義された楕円曲線上の整数倍算とは異なる自己準同型写像Φを実行することができる楕円曲線を用いて、スカラー値、及び、前記楕円曲線上の点とからスカラー倍点を計算する楕円曲線暗号におけるスカラー倍計算方法であって、
前記スカラー値を、第一の数値列（bn-1，bn-2，…，b0）（ｎは前記スカラー値を第一の数値列にエンコードした際の桁長）にエンコードする第一のステップと、
前記第一の数値列を、前記第一の数値列とは異なる第二の数値列にエンコードする第二のステップと、
前記楕円曲線上の点から事前計算テーブルを作成する第三のステップと、
前記第二の数値列、及び、前記事前計算テーブルから、前記スカラー倍点を計算する第四のステップと、を備える
ことを特徴とするスカラー倍計算方法。
【請求項２】
請求項１に記載のスカラー倍計算方法であって、
前記第一のステップは、前記スカラー値に対するΦ進展開を計算し、
前記第二のステップは、
bnとbn+1とbn+2とbn+3とを生成してそれぞれ0とするステップと（ｎは前記スカラー値に対するΦ進展開の桁長）、
iが0からnまでの間、
bi=0を満たすとき、biをbiとする変換を行った後iを1増加させ、
bi≠0、かつ、｜-qbi+1+bi｜≦（q2-1）/2を満たすとき、bi→-qbi+1+bi，bi+1→0，bi+2→-bi+1+bi+2とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi>（q2-1）/2を満たすとき、bi→-bi+1q+bi-q2，bi+1→0，bi+2→bi+2-bi+1-（q-1），bi+3→bi+3+1とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi<-（q2-1）/2を満たすとき、bi→-bi+1q+bi+q2，bi+1→0，bi+2→bi+2-bi+1+（q-1），
bi+3→bi+3-1とする変換を行った後iを2増加させる処理を繰り返す変換ステップと、を備える
ことを特徴とするスカラー倍計算方法。
【請求項３】
特性多項式Φ2+Φ+q（ｑは奇素数のべき）を持つ、定義体Fq上定義された楕円曲線上の整数倍算とは異なる自己準同型写像Φを実行することができる楕円曲線を用いて、スカラー値、及び、前記楕円曲線上の点とからスカラー倍点を計算する楕円曲線暗号におけるスカラー倍計算装置であって、
前記スカラー値を、第一の数値列（bn-1，bn-2，…，b0）（ｎは前記スカラー値を第一の数値列にエンコードした際の桁長）にエンコードする第一のエンコード手段と、
前記第一の数値列を、前記第一の数値列とは異なる第二の数値列にエンコードする第二のエンコード手段と、
前記楕円曲線上の点から事前計算テーブルを作成する事前計算手段と、
前記第二の数値列、及び、前記事前計算テーブルから、前記スカラー倍点を計算する実計算手段と、を備える
ことを特徴とするスカラー倍計算装置。
【請求項４】
請求項３に記載のスカラー倍計算装置であって、
前記第一のエンコード手段では、前記スカラー値に対するΦ進展開を計算することにより前記第一の数値列にエンコードし、
前記第二のエンコード手段では、
bnとbn+1とbn+2とbn+3とを生成してそれぞれ0とし、
iが0からnまでの間、
bi=0を満たすとき、biをbiとする変換を行った後iを1増加させ、
bi≠0、かつ、｜-qbi+1+bi｜≦（q2-1）/2を満たすとき、bi→-qbi+1+bi，bi+1→0，bi+2→-bi+1+bi+2とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi>（q2-1）/2を満たすとき、bi→-bi+1q+bi-q2，bi+1→0，bi+2→bi+2-bi+1-（q-1），bi+3→bi+3+1とする変換を行った後iを2増加させ、
bi≠0、かつ、-qbi+1+bi<-（q2-1）/2を満たすとき、bi→-bi+1q+bi+q2，bi+1→0，bi+2→bi+2-bi+1+（q-1），
bi+3→bi+3-1とする変換を行った後iを2増加させる処理を繰り返すことにより、前記第一の数値列を前記第二の数値列にエンコードする
ことを特徴とするスカラー倍計算装置。
【請求項５】
請求項３または４に記載のスカラー倍計算装置であって、
前記自己準同型写像はフロベニウス写像である
ことを特徴とするスカラー倍計算装置。
【請求項６】
データから署名データを生成する署名生成処理部と、前記署名データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する署名生成装置であって、
前記スカラー倍計算部は、請求項３ないし請求項５いずれか一に記載のスカラー倍計算装置を用いてスカラー倍点を計算する手段を備える
ことを特徴とする署名生成装置。
【請求項７】
データから署名データを検証する署名部と、前記署名データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する署名検証装置であって、
前記スカラー倍計算部は、請求項３ないし請求項５いずれか一に記載のスカラー倍計算装置を用いてスカラー倍点を計算する手段を備える
ことを特徴とする署名生成装置。
【請求項８】
データから暗号化データを生成する暗号部と、前記暗号化データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する暗号化装置であって、
前記スカラー倍計算部は、請求項３ないし請求項５いずれか一に記載のスカラー倍計算装置を用いてスカラー倍点を計算する手段を備える
ことを特徴とする暗号化装置。
【請求項９】
暗号化データから復号化データを生成する復号部と、前記復号化データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する復号化装置であって、
前記スカラー倍計算部は、請求項３ないし請求項５いずれか一に記載のスカラー倍計算装置を用いてスカラー倍点を計算する手段を備える
ことを特徴とする復号化装置。
【請求項１０】
楕円Diffie-Hellman鍵共有スキームにおいて、秘密鍵から公開鍵を生成する生成部と、前記公開鍵を生成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する鍵生成装置であって、
前記スカラー倍計算部は、請求項３ないし請求項５いずれか一に記載のスカラー倍計算装置を用いてスカラー倍点を計算する手段を備える
ことを特徴とする鍵生成装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１１−７５５８７（Ｐ２０１１−７５５８７Ａ）
【公開日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願番号】特願２００９−２２３６１９（Ｐ２００９−２２３６１９）
【出願日】平成２１年９月２９日（２００９．９．２９）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願日】平成２１年９月２９日（２００９．９．２９）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]