JP2005316038A - 楕円曲線暗号におけるスカラー倍計算方法と、その装置およびプログラム - Google Patents

Abstract

【課題】
楕円曲線暗号において最も計算リソースを必要とする楕円曲線スカラー倍計算に関して、メモリ使用量が小さく、かつ高速に計算できる楕円曲線スカラー倍計算方法を提供すること。
【解決手段】
スカラー値及び楕円曲線上の点からスカラー倍点を計算するスカラー倍計算方法において、スカラー値の変換処理を、スカラー値における連続する2ビットに対する演算を行うことにより、left-to-rightで実行し、それにより、高速計算および小メモリで計算可能となる。
【選択図】図１

Description

本発明はセキュリティ技術に係り、特に楕円曲線演算を用いたメッセージ処理方法に関する。

楕円曲線暗号はN.Koblitz, V.S. Millerにより提案された公開鍵暗号の一種である。公開鍵暗号には、公開鍵と呼ばれる一般に公開してよい情報と、秘密鍵(Private Key)と呼ばれる秘匿しなければならない秘密情報がある。与えられたメッセージの暗号化や署名の検証には公開鍵を用い、与えられたメッセージの復号化や署名の作成には秘密鍵を用いる。

楕円曲線暗号における秘密鍵は、スカラー値が担っている。また、楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Pとそのスカラー倍の点dPが与えられた時、スカラー値dを求める問題である。

楕円曲線上の点とは、楕円曲線の定義方程式をみたす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（加算ともいう）が定義される。そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の２倍算という。

楕円曲線上の２点の加法は次のようにして計算される。２点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とｘ軸に関して対称な点を、加法を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点(x₁,y₁)と点(x₂,y₂)の加算(x₃,y₃)=(x₁,y₁)+(x₂,y₂)は
x₃=((y₂-y₁)/(x₂-x₁))²-x₁-x₂ （式1）
y₃=((y₂-y₁)/(x₂-x₁))(x₁-x₃)-y₁ （式2）
を計算することにより得られる。ここで、ワイエルシュトラス型楕円曲線の定義式は
y²=x³+ax+b （式3）
で与えられる。すなわち式３のx,yに各々x_i,y_i (i=1,2,3) を代入した場合に、式３の等式が成り立つ。

楕円曲線上の点の２倍算は次のようにして計算される。楕円曲線上の点における接線を引くと、その接線は楕円曲線上の他の点において交わる。その交わった点とｘ座標に関して対称な点を、２倍算を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点(x₁,y₁)の２倍算(x₃,y₃)=2(x₁,y₁)=(x₁,y₁)+(x₁,y₁)は
x₃=((3x₁ ²+a)/(2y₁))²-2x₁ （式4）
y₃=((3x₁ ²+a)/(2y₁))(x₁-x₃)-y₁ （式5）
を計算することにより得られる。

ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果の点をスカラー倍点、その回数のことをスカラー値という。

楕円曲線暗号においては、与えられたメッセージの暗号化、復号化、署名の作成またはその検証は、楕円曲線演算を用いて行う必要がある。特に楕円曲線上のスカラー倍の計算は、上記の暗号化、復号化等の各処理において、最も計算リソースを必要とする計算である。そのため、楕円曲線暗号を効率的に実行するためには、楕円曲線スカラー倍の計算を効率的に行う必要がある。

楕円曲線スカラー倍計算方法が、非特許文献1、非特許文献6に記載されている。

J.A. Solinas, "Efficient Arithmetic on Koblitz Curves," Designs, Codes and Cryptography, 19, Kluwer Academic Publishers, pp.195-249, (2000). H. Cohen, A. Miyaji, and T. Ono, "Efficient Elliptic Curve Exponentiation Using Mixed Coordinates," Advances in Cryptology - ASIACRYPT 1998, LNCS 1514, Springer-Verlag, pp.51-65, (1998). D.V. Bailey, C. Paar, "Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms," Advances in Cryptology Crypto '98, LNCS 1462, Springer-Verlag, pp.472-485, (1998). ANSI X9.62 Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), (1998) H. Cohen, "A course in computational algebraic number theory," GTM138, Springer-Verlag, (1993). M. Joye, and S.-M. Yen, "Optimal Left-to-Right Binary Signed-digit Exponent Recoding," IEEE Transactions on Computers 49(7), pp.740-748, (2000).

情報通信ネットワークの進展と共に電子情報に対する秘匿や認証のために暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、高速処理や少ないメモリ使用量などがある。他方、楕円曲線上の離散対数問題が非常に困難であるために、素因数分解の困難性を安全性の根拠にしている暗号と比べて、楕円曲線暗号は鍵長を短くすることができる。そのため計算能力、メモリ容量などのりソースが比較的少なくても暗号処理を行うことが可能である。しかしながら、スマートカード（ＩＣカードともいう）等においては利用可能なリソースは少なく、限られたリソース内で最適な暗号処理を行うように処理速度やメモリ使用量に優れる暗号処理が必要となる。

上記非特許文献1の技術は、一旦スカラー値の表現を変換し、その後 変換した表現を用いて暗号処理を実行するため、変換した表現を格納するメモリが必要となる。また、変換と暗号処理を同時に行うとすると、楕円加算の計算方法として高速な手法を用いることができない。これは、スカラー値の変換処理が最下位ビットから最上位ビットに向けて（right-to-left）処理が行われるのに対し、楕円加算の高速計算手法は最上位ビットから最下位ビットに向けて（left-to-right）処理が行われたときのみに適用可能だからである。したがって、上記技術はメモリ使用量の削減、処理速度の改善、といった点について十分に考慮されていない。

また上記非特許文献6の技術は、特殊なケースに対して、スカラー値の変換をleft-to-rightで行うことができるが、一般的な場合に対する考察がなされていない。

本発明は、スカラー値の変換処理をleft-to-rightで行う処理を提供することにより、高速計算および小メモリで計算可能な楕円曲線演算方法を提供する。

本発明は、更に、上記楕円曲線演算方法を用いた、暗号化処理方法、復号化処理方法、署名作成方法、署名検証方法、データ共有方法を提供する。

本発明は、楕円曲線演算において、スカラー値と楕円曲線上の点からスカラー倍を計算する楕円曲線暗号におけるスカラー倍計算方法であって、上記スカラー値における連続する2ビットに対する演算を行うステップと、を有する。

本発明は、また、上記2ビットに対する演算は、2ビットの差分を計算、ないしは2ビットの値を比較、ないしは2ビットの排他的論理和を、計算するようにしてもよい。

本発明は、また、上記スカラー値を数値列にエンコードするステップと、上記エンコードした数値列及び上記楕円曲線上の点からスカラー倍を計算するステップと、を有し、上記エンコードするステップは、上記2ビットに対する演算を含むように構成してもよい。

本発明は、また、上記スカラー値を数値列にエンコードするステップと、上記楕円曲線上の点から事前計算テーブルを作成するステップと、上記エンコードした数値列及び上記事前計算テーブルからスカラー倍を計算するステップと、を有し、上記エンコードするステップは、上記2ビットに対する演算を含むように構成してもよい。

本発明は、また、上記楕円曲線上の点から事前計算テーブルを作成するステップと、上記スカラー値及び上記事前計算テーブルからスカラー倍を計算するステップと、を有し、上記スカラー倍を計算するステップは、上記2ビットに対する演算を含むように構成してもよい。

以上のように、本発明のスカラー倍計算方法によれば、スカラー値の変換処理をleft-to-rightで実行でき、高速計算および小メモリでの計算が可能な楕円曲線演算方法が利用可能となる。

本発明によれば、スカラー値の変換処理をleft-to-rightで実行でき、高速および小メモリで計算することができる、楕円曲線演算を用いたメッセージ処理が可能となる。

以下、本発明の実施例を図面により説明する。

図1はネットワーク142によって接続された本発明による楕円曲線演算方法を適用したコンピュータＡ101、コンピュータＢ121がネットワークにより接続されたシステム構成を示すものである。

図1の暗号通信システムにおけるコンピュータＡ101でメッセージの暗号化を行なうには、P_m+k(aQ)及びkQを計算して出力し、コンピュータＢ121で暗号文の復号化を行なうには、秘密鍵a及びkQより-a(kQ)を計算し、
(P_m+k(aQ))-a(kQ) （式6）
を計算して出力すればよい。ここでP_mはメッセージ、kは乱数、aは秘密鍵を示す定数、Qは定点、aQは公開鍵を示す点である。

ネットワーク142には、P_m+k(aQ), kQのみ送信され、メッセージP_mを復元するためには、kaQ、すなわちkQのa倍を計算する必要がある。ところが、秘密鍵aはネットワーク142には送信されないため、秘密鍵aを保持しているものだけが、P_mを復元できることになる。

図1において、コンピュータＡ101は、ＣＰＵ113やコプロセッサ114などの演算装置、ＲＡＭ103、ＲＯＭ106や外部記憶装置107などの記憶装置、コンピュータ外部とのデータ入出力を行なう入出力インタフェース110を装備しており、外部にはコンピュータＡ101をユーザが操作するためのディスプレイ108、キーボード109、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。

更にコンピュータＡ101は、ＲＡＭ103、ROM106や外部記憶装置107などの記憶装置によって、記憶部102を実現し、ＣＰＵ113やコプロセッサ114などの演算装置が、記憶部102に格納されたプログラムを実行することにより、データ処理部112、スカラー倍計算部115とそれらに含まれる各処理部を実現する。

データ処理部112は、本実施形態においては、暗号化処理部として機能し、入力されたメッセージの暗号化を行なう。

スカラー倍計算部115は、暗号化処理部112で暗号化を行なうのに必要なパラメタを計算する。記憶部102は、定数104（例えば、楕円曲線の定義式や楕円曲線上の定点である）、秘密情報105（例えば、秘密鍵である）などを記憶している。

コンピュータＢ121は、コンピュータＡと同様のハードウェア構成を備える。

更にコンピュータＢ121は、ＲＡＭ123、ＲＯＭ126や外部記憶装置127などの記憶装置によって、記憶部122を実現し、ＣＰＵ133やコプロセッサ134などの演算装置が、記憶部122に格納されたプログラムを実行することにより、データ処理部132、スカラー倍計算部135とそれらに含まれる各処理部を実現する。

データ処理部132は、本実施形態においては、復号化処理部132として機能し、暗号化されたメッセージである暗号文141の復号化を行なう。

スカラー倍計算部135は、復号化処理部132で復号化を行なうのに必要なパラメタを計算する。記憶部122は、定数124（例えば、楕円曲線の定義式や楕円曲線上の定点である）、秘密情報125（例えば、秘密鍵である）などを記憶している。

なお、上記プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていてもよいし、必要なときに、入出力インタフェース110と上記コンピュータが利用可能な媒体を介して、他の装置から上記記憶媒部に導入されてもよい、媒体とは、例えば、入出力インタフェースに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波またはディジタル信号）を指す。

図2は、コンピュータＡ101、コンピュータＢ121の各処理部が行なう情報の受け渡しの様子を示したものである。

次に、図1のコンピュータＡ101が、入力されたメッセージを暗号化する場合の動作について説明する。メッセージはディジタル化されたデータであればよく、テキスト、画像、映像、音などの種類は問わない。

暗号化処理部112は、入出力インタフェース110を介して、平文メッセージ（図2の入力メッセージ204）を受け取ると、入力された平文メッセージのビット長があらかじめ定めたビット長か否かを判断する。あらかじめ定めたビット長よりも長い場合には、あらかじめ定めたビット長となるように平文メッセージを区切る。以下、所定のビット長に区切られている部分メッセージ（単にメッセージともいう）について説明する。

次に、暗号化処理部112は、メッセージのビット列によって表される数値をx座標(x₁)にもつ楕円曲線上の点P_mのy座標(y₁)の値を計算する。

例えば、ワイエルシュトラス型楕円曲線は、A,Bを定数とするとき、
y₁ ²=x₁ ³ +Ax1+B （式7）
で表されるので、これよりy座標の値を求めることができる。

次に、暗号化処理部112は、乱数kを生成する。そして記憶部102に格納されている定数104から読み出した（図2の205）公開鍵aQとQのx座標と、求めたy座標の値と乱数kとをスカラー倍計算部115へ送る（図2の206）。

スカラー倍計算部115は、Qのx座標、y座標の値、乱数kによるスカラー倍点（x_d1,y_d1）=kQと、公開鍵aQのx座標、y座標の値、乱数によるスカラー倍点(x_d2,y_d2)=k(aQ)とを計算し、計算されたスカラー倍点を暗号化処理部112へ送る（図2の207）。

暗号化処理部112は、送られたスカラー倍点を用いて、暗号化処理を行なう。例えば、ワイエルシュトラス型楕円曲線については、P_m+k(aQ)とkQを計算する。すなわち、
x_e1=((y_d1-y₁)/(x_d1-x₁))²-x₁-x_d1 （式8）
x_e2=x_d2 （式9）
を計算し、暗号化されたメッセージx_e1,x_e2を得る。

コンピュータＡ101は暗号化処理部112で暗号化された1つ以上の部分メッセージから暗号化された出力メッセージを組み立てる（図2の208）。

コンピュータＡ101は、暗号化されたメッセージをデータ141として入出力インタフェース110より出力し、ネットワーク142を介してコンピュータＢ121へ転送する。

なお、図2の記憶部102からの情報読出しは、スカラー倍計算部115へ当該当情報を送る前であれば、入力メッセージを受付ける前であってもよい。

次に、コンピュータＢ121が、暗号化されたメッセージ141を復号化する場合の動作について、図2を参照しつつ説明する。

復号化処理部132（図2のデータ処理部112）は、入出力インタフェース110を介して、暗号化されたデータ141（図2の入力メッセージ204）が入力されると、入力された暗号化されたデータ141のビット長があらかじめ定めたビット長か否かを判断する。あらかじめ定めたビット長よりも長い場合は、あらかじめ定めたビット長となるように暗号化されたデータを区切る。以下、所定のビット長に区切られている部分データ（単にデータともいう）について説明する。

データ141のビット列によって表される数値をx座標にもつ楕円曲線上のy座標の値を計算する。

暗号化されたメッセージがx_e1,x_e2のビット列であり、ワイエルシュトラス型楕円曲線の場合、y座標の値(y_e1)は
y_e1 ²=x_e1 ³+Ax_e1+B （式10）
（ただし、A,Bはそれぞれ定数である）
から得ることができる。

復号化処理部132は、記憶部122（図2の102）に格納されている秘密情報125から読み出した（図2の205）秘密鍵aと、x座標、y座標の値（x_e2,y_e2）を、スカラー倍計算部135（図2の115）へ送る（図2の206）。

スカラー倍計算部135は、x座標、y座標の値、秘密情報a125からスカラー倍点(x_d3,y_d3)=a(x_e2,y_e2)を計算する。スカラー倍計算部135は、計算されたスカラー倍点を復号化処理部132へ送る（図2の207）。復号化処理部132は、送られたスカラー倍点を用いて、復号化処理を行う。

例えば、暗号化されたメッセージが、x_e1,x_e2のビット列であり、ワイエルシュトラス型楕円曲線の場合は、
(P_m+k(aQ))-a(kQ)=(x_e1,y_e1)-(x_d3,y_d3) （式11）
を計算することにより達成する。すなわち、
x_f1=((y_e1+y_d3)/(x_e1-x_d3))²-x_e1-x_d3 （式12）
を計算し、暗号化される前の部分メッセージx₁に相当するx_f1を得る。

コンピュータＢ121は、復号化処理部132で復号化された部分メッセージから平文メッセージを組み立て（図2の208）、入出力インタフェース110を介して、ディスプレイ108などから出力する。

次に、コンピュータＡ101が、暗号化処理を行う場合の、スカラー倍計算部115の処理を詳細に説明する。

第1実施例では、図3で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部115（図1の115）は、エンコード部302、実計算部304からなる。エンコード部302は、BinaryToMOFエンコード部305、MOFTo2cMOFエンコード部306からなる。BinaryToMOFエンコード部305は、繰り返し判定部351、変換部352からなる。MOFTo2cMOFエンコード部306は、繰り返し判定部361、変換部362からなる。実計算部304は、ビット値判定部341、加算部342、2倍算部343、繰り返し判定部344からなる。

スカラー倍計算部115がスカラー値d及び楕円曲線上の点Pから、楕円曲線におけるスカラー倍点dPを計算する第1の計算方法を説明する。

スカラー倍計算部115が暗号化処理部112からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部302は、入力されたスカラー値dを数値列d_w[j]にエンコードする。すなわち、
d=d_w[n]2ⁿ+d_w[n-1]2^n-1+…+d_w[j]2^j+… +d_w[0] (式13)
-2^w-1≦d_w[j]≦2^w-1, d_w[j]=0 or 奇数 (式14)
をみたすd_w[j]に、スカラー値dを変換する。ここで、wはあらかじめ定めた小さな正整数で、ウィンドウ幅と呼ばれる。計算時間を優先する場合はwを大きな値とする。メモリ使用量を小さくする場合はwを小さな値にする。実計算部304は、エンコードされたスカラー値と入力された点Pを用いてスカラー倍点dPを計算する。第1実施例では特にw=2の場合について説明する。

次にエンコード部302、実計算部304の行う各処理について詳細に説明する。

まず、エンコード部302の行う処理について説明する。
エンコード部302は、バイナリ列dを符号付バイナリ列cmdに変換する。

エンコード部302にバイナリ列dが入力されると、BinaryToMOFエンコード部305はバイナリ列dを符号付バイナリ列mdに変換する。

MOFTo2cMOFエンコード部306は、BinaryToMOFエンコード部305が変換した符号付バイナリ列mdを別の符号付バイナリ列cmdに変換する。

エンコード部302は、MOFTO2cMOFエンコード部306が変換した符号付バイナリ列cmdをエンコードされた数値列d_w[j]として出力する。すなわち、各jに対して、d_w[j] = cmd_jである。ただし、cmd_jはcmdのjビット目の値とする。

次に図4を用いて、BinaryToMOF エンコード部305の行う処理について詳細に説明する。この処理は2d-dという変換を念頭において構成されている。ただし、この引き算はビットごとの引き算であり、負の値（-1）も取りうる。また、符号付バイナリ列mdにおいて、jビット目の値をmd_j と表記する。

変換部352はmd_n にd_n-1 を代入する(401)。

変数iに初期値n-1を代入する（402）。

変換部352は、d_i-1 d_i を計算し、md_i に代入する(403)。

繰り返し判定部351は、i>1かどうかを判定する。i>1の場合はステップ411へ行く。i<=1の場合はステップ421へ行く(404)。

ステップ404でi>1の場合、
変数iを1減少させ、ステップ403へ戻る(411)。

ステップ404でi<=1の場合、
変換部352はmd₀ にd₀ を代入する(421)。

md_n, ..., md₀ を変換された符号付バイナリ列mdとして出力する(422)。

なお、BinaryToMOFエンコード部305が出力するmd_i は0,1,-1のいずれかの値のみを取りうる。なぜならば、md_i にはd_iもしくはd_i-1 -d_iのみが割当てられ、d_iはあり0,1のみ取りうるからである。

本明細書では、この符号付バイナリ表現mdをMOF表現と呼ぶ。MOF表現では、非零ビットは、0値ビットを無視して隣接する非零ビットとは必ず異なる符号を持つ。例えば、ビット列1010011のMOF表現は、1,-1,1,-1,0,1,0,-1 となる。0値ビットを無視すると隣接する非零ビットの符号が反転していることが分かる。

次に図5を用いて、MOFTo2cMOFエンコード部306の行う処理について詳細に説明する。この処理は隣接する2ビットの値が(1,-1)もしくは(-1,1)であった場合、それぞれ(0,1), (0,-1)に変換するという処理を最上位ビット側から行うものである。なお、符号付バイナリ列cmdにおいて、jビット目の値をcmd_j と表記する。

変数iをnで初期化する(501)。

変換部362は、(md_i, md_i-1)の値に応じて処理を振分ける。(md_i, md_i-1)=(1,-1)の場合はステップ511へ行く。(md_i, md_i-1)=(-1,1)の場合はステップ512へ行く。(md_i, md_i-1)がそれ以外の値の場合はステップ503へ行く(502)。

ステップ502で(md_i, md_i-1)=(1,-1)の場合、
変換部362はcmd_iに0、cmd_i-1に1を代入し、ステップ513へ行く(511)。

ステップ502で(md_i, md_i-1)=(-1,1)の場合、
変換部362はcmd_iに0、cmd_i-1に-1を代入し、ステップ513へ行く(512)。

変数iを2減少させ、ステップ505へ行く(513)。

ステップ502で(md_i, md_i-1)が(1,-1), (-1,1)以外の値の場合、
変換部362はcmd_iにmd_i を代入し、ステップ504へ行く(503)。

変数iを1減少させ、ステップ505へ行く(504)。

繰り返し判定部361は、i>=1かどうかを判定する。i>=1の場合はステップ502へ戻る。i<1の場合はステップ506へ行く(505)。

ステップ505でi<1の場合、
i=0かどうかを判定する。i=0の場合はステップ507へ行く。i != 0の場合はステップ508へ行く(506)。

ステップ506でi=0の場合、
変換部362はcmd₀にmd₀を代入し、ステップ508へ行く(507)。

cmd_n, ..., cmd₀ を変換された符号付バイナリ列cmdとして出力する(508)。

なお、MOFTo2cMOFエンコード部306が出力するcmd_i は0,1,-1のいずれかの値のみを取りうる。なぜならば、cmd_i には0,1,-1もしくはmd_iのみが割当てられ、md_iはBinaryToMOFエンコード部305の出力であり0,1,-1のみ取りうるからである。

結果として、エンコード部302が出力するd_w[j]は、0,1,-1のいずれかの値のみを取りうる。

本明細書では、この符号付バイナリ表現cmdを2cMOF表現と呼ぶ。

最後に、図6を用いて、実計算部304がエンコードされたスカラー値と楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。

変数cに初期値nを代入する(601)。

d_w[c]が0か0でないかを判定する。

d_w[c]が0の場合はステップ603へ行く。0でなければステップ611へ行く(602)。

変数cを1減少させ、ステップ602へ戻る(603)。

ステップ602でd_w[c]が0でない場合、点Qにd_w[c]Pを代入する(611)。

変数jに初期値c-1を代入する(612)。

繰り返し判定部344は、jが0より小さいかどうかを判定する。jが0より小さい場合はステップ621へ行く。0以上の場合はステップ614へ行く(613)。

ステップ613でjが0以上の場合、
2倍算部343は、点QをECDBLにより2倍し、点Qに再び格納する(614)。

ビット値判定部341は、d_w[j]が0か0でないかを判定する。d_w[j]が0の場合はステップ617へ行く。0でなければステップ616へ行く(615)。

ステップ615でd_w[j]が0でない場合、
加算部342は、点Qとd_w[j]PとをECADDにより加算する。ただし、d_w[j]が負の場合は、(-d_w[j])Pのy座標を反転したものを用いて加算を行う。その結果を点Qに格納し、ステップ617へ行く(616)。
なお、d_w[j]が0でない場合は、d_w[j]は1もしくは-1であり、d_w[j]Pは、Pもしくは-Pのいずれかを表すことになる。

変数jを1減少させ、ステップ613へと戻る(617)。

ステップ613でjが0より小さい場合、
点Qを出力する(621)。

なお、楕円曲線上の点Q=(x,y)に対して、楕円曲線加算に関する逆元の点-Qは、-Q=(x,-y)と表されるため、点Qの座標が与えられていれば容易に計算できる。そのため、点Pのみを保持していれば、実計算部304が行う計算で必要となる点-Pは、それらから導出することが可能である。

また、ECADD, ECDBLはそれぞれ楕円曲線における加算、2倍算を表す。加算は式1,2を用いて、2倍算は式4,5を用いてそれぞれ計算される。なお、加算、2倍算の計算には式1,2、および式4,5を用いる以外にも、射影座標やヤコビアン座標における計算公式があり、非特許文献2に記載されている。特に、点Pをアフィン座標として表すことにより、高速に計算することが可能である。

実計算部304が出力する点Qはスカラー倍点dPに等しい。この理由は次の通りである。

ステップ613において点Qが
(d_w[c]2^c-(j+1)+d_w[c-1]2^(c-1)-(j+1)+…+ d_w[j+1]2^(j+1)-(j+1))P (式15)
と表されるとする。このとき、次にステップ613に来る時も点Qは式15をみたすことを示す。

点Qはステップ614で2倍され、d_w[j]が0でなければステップ616でd_w[j]Pが加えられる。そのためステップ616の直後では、点Qの値は
(d_w[c]2^c-j+d_w[c-1]2^(c-1)-j+…+d_w[j+1]2^(j+1)-j+ d_w[j]2^j-j)P (式16)
となる。したがってd_w[j]=0の時も含めて、ステップ617の直前で、点Qは式16をみたす。ステップ617でjが1減少するので、式16のjにj+1を代入すると式15になる。すなわち、次にステップ613に来る時も点Qは式15をみたす。

j>cに対するd_w[j]の値は0であるので、ステップ621で出力される点Qの値は
(d_w[n]2ⁿ+d_w[n-1]2^n-1+…+d_w[0])P (式17)
に等しい。実計算部304に入力されるスカラー値は、エンコード部302によりエンコードされたd_w[j]であるので、そのd_w[j]は式13をみたす。したがって、Q=dPである。

BinaryToMOFエンコード部305が出力する符号付バイナリ列mdは、
d = md_n2ⁿ+md_n-12^n-1+…+ md₀ (式18)
をみたす。この理由は次の通りである。
ステップ401でmd_nにd_n-1が、ステップ403でmd_iにd_i-1-d_iが、ステップ421でmd₀にd₀が格納される。したがって、
md_n2ⁿ+md_n-12^n-1+…+ md₀
= d_n-12ⁿ +(d_n-2d_n-1)2^n-1 +(d_n-3d_n-2)2^n-2 +...+ (d₀-d₁)2 +d₀
= d_n-12^n-1 +d_n-22^n-2 +...+ d₁2 +d₀
= d （式19）
が成り立つ。

MOFTo2cMOFエンコード部306が出力する符号付バイナリ列cmdは、
d = cmd_n2ⁿ+cmd_n-12^n-1+…+ cmd₀ (式20)
をみたす。この理由は次の通りである。
ステップ502で(md_i, md_i-1)=(1,-1), (-1,1)の場合、ステップ511、ステップ512の変換により定まるcmd_i, cmd_i-1 とmd_i, md_i-1の間には
cmd_i2ⁱ +cmd_i-12^i-1 = md_i2ⁱ +md_i-12^i-1 （式21）
の関係が成り立つ。またステップ502で(md_i, md_i-1)=(1,-1), (-1,1)以外の場合、ステップ503の変換により定まるcmd_i, とmd_i, の間には
cmd_i2ⁱ = md_i2ⁱ （式22）
の関係が成り立つ。ステップ507でcmd₀にmd₀が代入される。したがって、
cmd_n2ⁿ+cmd_n-12^n-1+…+ cmd₀ = md_n2ⁿ+md_n-12^n-1+…+ md₀ （式23）
が成り立つ。mdはBinaryToMOFエンコード部の305の出力であるため、式13をみたす。したがって、式18が成り立つ。

結果として、エンコード部302が出力する数値列d_w[j]は、式13をみたす。

BinaryToMOFエンコード部305の行う処理はleft-to-rightである。なぜならば、ステップ401においてd_n-1の値を用いてmd_nの値を割当て、その後ステップ403において、順次iが大きい方からd_i, d_i-1 を用いてmd_i の値を決定し、最後にステップ421においてd₀を用いてmd₀の値を割当てるからである。

なお、第1実施例ではBinaryToMOFエンコード部305の処理をleft-to-rightで行う場合を説明したが、right-to-leftでの処理や並列処理も可能である。なぜならば、各md_i はd_i, d_i-1 から定まり、他のmd_jの結果を用いないからである。そのため、right-to-left で処理を行う場合はiが小さい値から順次定めることにより、また並列で行う場合は対象とするmd_i の計算を同時に行うことにより、計算することが可能である。

MOFTo2cMOFエンコード部306の行う処理はleft-to-rightである。なぜならば、ステップ511、ステップ512、ステップ503において、順次iが大きい方からmd_i, md_i-1 を用いてcmd_i, cmd_i-1 の値を決定し、最後にステップ507においてmd₀を用いてcmd₀ の値を割当てるからである。

結果として、エンコード部302の行う処理はleft-to-rightである。

BinaryToMOFエンコード部305の出力するmdは、その出現ビットの値の推移確率をして、以下のような推移確率を持つ。
0→0：1/2、 0→非零：1/2、 非零→0：1/2、 非零→非零：1/2 （式24）
すなわち、0と非零とは独立である。この理由は次の通りである。各md_i は、d_i-1 d_i より定まり、他のmd_j には依存しない。d_i-1, d_i の値として0,1の各々二通りの場合を考えることにより、0と非零の値が各々1/2の確率となることが分かる。したがって、上記の推移確率を取ることが分かる。

次に、MOFTo2cMOFエンコード部306が出力するcmdは、非零濃度が1/3となる。ここで非零濃度とは、(非零ビットの個数)/(ビット長) の漸近的な値を指す。この理由は次の通りである。
ステップ502-ステップ505の変換は、md_i, md_i-1の値により 取りうる状態が4つある。すなわち、(a)00, (b)01, (c)10, (d)11である。ただし、ここでの1は非零を表している。ステップ513ではiを2減少させるので、もう一つの状態(e)を補う。MOF表現の推移確率は式24で与えられるので、これらの間の推移確率は、
(a)→(a)：1/2、(a)→(b)：1/2、
(b)→(c)：1/2、(b)→(d)：1/2、
(c)→(a)：1/2、(c)→(b)：1/2、
(d)→(e)：1、
(e)→(a)：1/4、(e)→(b)：1/4、(e)→(c)：1/4、(e)→(d)：1/4 （式25）
となる。この推移確率から定まる定常状態を計算すると、
(a)：1/4、(b)：1/4、(c)：1/6、(d)：1/6、(e)：1/6 （式26）
となる。非零ビットが出力されるのは、状態(c)(d)に対応するので、非零濃度は1/3となる。また、非特許文献1によれば、ウィンドウ幅wが2の場合、非零濃度1/3が最小であることが示されている。

したがって、エンコード部302の出力も非零濃度1/3となり、最小の非零濃度である。

実計算部304の加算部342が実行する楕円加算の回数は、エンコードされた符号付バイナリ列の非零ビットの個数となる。この非零ビットの個数は最小であるため、楕円加算の回数は最小となる。
以上の通り、上記計算方法は、エンコード処理をleft-to-rightで行うことが可能である。また、エンコードされた数値列は最小の非零濃度を持つため、楕円加算を行う回数が少なくてすみ、そのため、高速に計算することが可能である、という特徴がある。

なお、第1の計算方法では楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数2の有限体上で定義された楕円曲線や、非特許文献4に記載されているOEF(Optimal Extension Field)上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよい。

第2実施例では、第1実施例の2つのエンコード処理を同時に実行する方法に関して説明する。第2実施例では、図7で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部115（図1の115）は、エンコード部702、実計算部704からなる。エンコード部702は、繰り返し判定部721、変換部722からなる。実計算部704は、第1実施例の実計算部304と同様の構成を備える。

スカラー倍計算部115がスカラー値d及び楕円曲線上の点Pから、楕円曲線におけるスカラー倍点dPを計算する第2の計算方法を説明する。

スカラー倍計算部115が暗号化処理部112からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部702は、入力されたスカラー値dを式13, 式14をみたす数値列d_w[j]にエンコードする。実計算部704は、エンコードされたスカラー値と入力された点Pを用いてスカラー倍点dPを計算する。第2実施例では特にw=2の場合について説明する。

次にエンコード部702、実計算部704の行う各処理について詳細に説明する。

まず、エンコード部702の行う処理について説明する。

エンコード部702にバイナリ列dが入力されると、符号付バイナリ列cmdに変換する。エンコード部702は、この符号付バイナリ列cmdをエンコードされた数値列d_w[j]として出力する。すなわち、各jに対して、d_w[j] = cmd_jである。ただし、cmd_jはcmdのjビット目の値とする。

次に実計算部704の行う処理について説明する。実計算部704の行う処理は、第1実施例の実計算部304の行う処理と同様の処理を行う。

次に図8を用いて、エンコード部702の行う処理について詳細に説明する。

変数iに初期値c+1を代入する。ただし、cはdの非零ビットのインデックスで最大のものとする。すなわち、d_c!=0かつi>cに対してd_i=0(801)。

変換部722は、d-1に0を代入し、cmd_n, ..., cmd_c+1 に0を代入する(802)。

繰り返し判定部721は、i>=1かどうかを判定する。i>=1の場合はステップ811へ行く。i<1の場合はステップ821へ行く(803)。

ステップ803でi>=1の場合、
d_i-1 = d_i かどうかを判定する。d_i-1 = d_i の場合はステップ812へ行く。d_i-1 != d_i の場合はステップ813へ行く(811)。

ステップ811でd_i-1 = d_i の場合、
変換部722はcmd_i に0を代入し、変数iを1減少させ、ステップ803へ戻る(812)。

ステップ811でd_i-1 != d_i の場合、
変換部722はcmd_i に -d_i +d_i-2 を、cmd_i-1 に d_i-2 +d_i-1 を代入し、変数iを2減少させ、ステップ803へ戻る(813)。

ステップ803でi<1の場合、
i=0 かどうかを判定する。i=0 の場合はステップ822へ行く。i != 0の場合はステップ823へ行く(821)。

ステップ821でi=0の場合、
変換部722はcmd₀ に d₀を代入し、ステップ823へ行く(822)。

cmd_n, ..., cmd₀ を変換された符号付バイナリ列cmdとして出力する(823)。

なお、エンコード部702が出力するd_w[j]は、0,1,-1のいずれかの値のみを取りうる。なぜならば、スカラー値dの各ビットd_i は0,1いずれかの値のみを取り、cmd_j は0, -d_i もしくは、2つのd_i の差分のいずれかが代入されるからである。

エンコード部702が出力する符号付バイナリ列cmdは、
d = cmd_n2ⁿ+cmd_n-12^n-1+…+ cmd₀ (式27)
をみたす。この理由は次の通りである。
ステップ803-ステップ813におけるループでは、d_i2ⁱ⁺¹がキャリーとしてループでの不変量となる。まずステップ811の分岐処理によりステップ812へ行った場合を考える。ステップ812ではcmd_iに0が代入される。
cmd_i2ⁱ +d_i2ⁱ⁺¹ = d_i2ⁱ +d_i2ⁱ
= d_i2ⁱ +d_i-12ⁱ （式28）
したがって、d_iに対する項はd_i2ⁱとなり、キャリーd_i-12ⁱとなる。次にステップ811の分岐処理によりステップ813へ行った場合を考える。
cmd_i2ⁱ +cmd_i2^i-1 +d_i2ⁱ⁺¹ = (-d_i+d_i-2)2ⁱ +(d_i-2+d_i-1)2^i-1 +d_i2ⁱ⁺¹
= d_i2ⁱ +d_i-12^i-1 +d_i-22^i-1 （式29）
したがって、d_i, d_i-1に対する項はそれぞれd_i2ⁱ, d_i-12^i-1となり、キャリーd_i-22^i-1となる。したがって、d_i2ⁱ⁺¹がキャリーとしてループでの不変量となることが分かった。最初にステップ803に来る時のiの値はi=c+1であり、
d_c+12^c+2 = 0 （式30）
であるのでキャリーは0となる。他方、ループを抜けたあとの処理では、キャリーの値はd₀2もしくはd_-11となる。i=0の場合はステップ822の処理を行うため、いずれの場合もキャリーがキャンセルされる。以上をまとめると、
cmd_n2ⁿ+cmd_n-12^n-1+…+ cmd₀ = d_n2ⁿ+d_n-12^n-1+…+ d₀ = d （式31）
となる。

エンコード部702の行う処理はleft-to-rightである。なぜならば、ステップ802においてcmd_n,..., cmd_c+2の値をクリアし、その後ステップ812, ステップ813において、順次iが大きい方からd_i, d_i-1, d_i-2を用いてcmd_i, cmd_i-1の値を決定し、最後にステップ821においてd₀を用いてcmd₀の値を割当てるからである。

エンコード部702の出力する符号付バイナリ列cmdは、非零濃度が1/3となり、最小の非零濃度である。なぜならば、エンコード部702の出力は、第1実施例のエンコード部302の出力と一致するからである。

実計算部704の加算部742が実行する楕円加算の回数は、エンコードされた符号付バイナリ列の非零ビットの個数となる。この非零ビットの個数は最小であるため、楕円加算の回数は最小となる。

以上の通り、上記計算方法は、エンコード処理をleft-to-rightで行うことが可能である。また、エンコードされた数値列は最小の非零濃度を持つため、楕円加算を行う回数が少なくてすみ、そのため、高速に計算することが可能である、という特徴がある。また、第2実施例ではエンコード処理を1回で行うことにより、エンコード処理の高速化、プログラムの簡素化やハードウェア論理回路の小規模化といったメリットがある。

なお、第2の計算方法でも楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数2の有限体上で定義された楕円曲線や、OEF(Optimal Extension Field)上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよいことも、第1実施例と同様である。

第3実施例では、第1実施例、第2実施例でのエンコード処理を、実計算部の行う処理に組込み、楕円演算を行う際に逐次変換し用いる方法に関して説明する。第3実施例では、図9で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部115（図1の115）は、実計算部904からなる。実計算部904は、変換判定部941、加算部942、2倍算部943、繰り返し判定部944からなる。

スカラー倍計算部115がスカラー値d及び楕円曲線上の点Pから、楕円曲線におけるスカラー倍点dPを計算する第3の計算方法を説明する。

スカラー倍計算部115が暗号化処理部112からスカラー値dと楕円曲線上の点Pを受け取ると、実計算部904は、入力されたスカラー値と入力された点Pを用いてスカラー倍点dPを計算する。第3実施例では特にw=2の場合について説明する。

次に図10、図11を用いて、実計算部904の行う処理について詳細に説明する。

d_-1に0を、変数iにc+1を代入する。ただし、cはdの非零ビットのインデックスで最大のものとする。すなわち、d_c!=0かつi>cに対してd_i=0 (1001)。

変換判定部941は、d_i-2=1かどうかを判定する。d_i-2=1の場合、ステップ1003へ行く。d_i-2!=1の場合、ステップ1004へ行く(1002)。

ステップ1002でd_i-2=1の場合、
2倍算部943は、点PをECDBLにより2倍し、点Qに格納し、ステップ1005へ行く(1003)。

ステップ1002でd_i-2!=1の場合、
点Pを点Qに格納し、ステップ1005へ行く(1004)。

変数iを2減少させる(1005)。

繰り返し判定部944は、i>0かどうかを判定する。i>0の場合、ステップ1111へ行く。i<=0の場合、ステップ1007へ行く(1006)。

ステップ1006でi>0の場合、
変換判定部941は、di-1=dかどうかを判定する。d_i-1=d_iの場合、ステップ1121へ行く。d_i-1!=d_iの場合、ステップ1112へ行く(1111)。

ステップ1111でd_i-1=d_iの場合、
2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する(1121)。

変数iを1減少させ、ステップ1006へと戻る(1122)。

ステップ1111でd_i-1!=d_iの場合、
2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する(1112)。

変換判定部941は、(d_i,d_i-2)の値に応じて処理を振分ける。(d_i,d_i-2)=(1,1)の場合、ステップ1114へ行く。(d_i,d_i-2)=(1,0)の場合、ステップ1115へ行く。(d_i,d_i-2)=(0,1)の場合、ステップ1116へ行く。(d_i,d_i-2)=(0,0)の場合、ステップ1117へ行く(1113)。

ステップ1113で(d_i,d_i-2)=(1,1)の場合、
2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する。その後、加算部942は、点Qと点-PとをECADDにより加算し、点Qに格納する。その後、ステップ1118へ行く(1114)。

ステップ1113で(d_i,d_i-2)=(1,0)の場合、
加算部942は、点Qと点-PとをECADDにより加算し、点Qに格納する。その後、2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する。その後、ステップ1118へ行く(1115)。

ステップ1113で(d_i,d_i-2)=(0,1)の場合、
加算部942は、点Qと点PとをECADDにより加算し、点Qに格納する。その後、2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する。その後、ステップ1118へ行く(1116)。

ステップ1113で(d_i,d_i-2)=(0,0)の場合、
2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する。その後、加算部942は、点Qと点PとをECADDにより加算し、点Qに格納する。その後、ステップ1118へ行く(1117)。

変数iを2減少させ、ステップ1006へと戻る(1118)。

ステップ1006でi<=0の場合、
i=0かどうかを判定する。i=0の場合はステップ1008へ行く。i != 0の場合はステップ1009へ行く(1007)。

ステップ1007でi=0の場合、
2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する。その後、加算部942は、点Qと点-d0PとをECADDにより加算し、点Qに格納する。その後、ステップ1009へ行く(1008)。

点Qをスカラー倍点dPとして出力する(1009)。

実計算部904が出力する点Qはスカラー倍点dPに等しい。この理由は次の通りである。
まず、ステップ1112-ステップ1118の処理について考える。この場合、d_i=d_i-1が成り立っている。(d_i, d_i-2)=(1,1)の場合、ステップ1112、ステップ1114の処理により、実行される演算はcmd_i=0, cmd_i-1=-1が第2実施例の実計算部704に入力された時と同じとなる。また、第2実施例のエンコード部702は、入力が(d_i, d_i-1, d_i-2)=(1,1,1)の時、ステップ813の処理により (cmd_i, cmd_i-1) = (0,-1)を出力する。したがって、この場合の処理は、第3実施例と第2実施例で同じとなる。同様に、ステップ1112、ステップ1115の処理は、(cmd_i, cmd_i-1) = (-1,0)、ステップ1112、ステップ1116の処理は、(cmd_i, cmd_i-1) = (1,0)、ステップ1112、ステップ1117の処理は、(cmd_i, cmd_i-1) = (0,1)に、それぞれ相当し、ステップ813の処理と一致する。また同様に、d_i, != d_i-1 の場合、ステップ1121の処理はステップ812の処理に相当する。他の部分についても第2実施例のエンコード部702の処理と同様に対応がつく。したがって、実計算部904が出力する点Qはスカラー倍点dPに等しい。

また、第2実施例との対応関係により、実計算部904の行う処理はleft-to-rightとなる。

実計算部904の行う楕円加算の回数は最小である。なぜならば、実計算部904の変換判定部941の行う処理は、第2実施例のエンコード部702の処理と対応がつくからである。

以上の通り、上記計算方法は、スカラー倍計算をleft-to-rightで行うことができる。また、楕円加算の回数は最小となっているため、高速に計算することが可能である、という特徴がある。また、第3実施例ではエンコード処理と楕円演算を1度に行うため、エンコード結果を一旦メモリに格納する必要がなく、メモリ使用量を少なくすることができる。

なお、第3の計算方法でも楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数2の有限体上で定義された楕円曲線や、OEF(Optimal Extension Field)上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよいことも、第1実施例と同様である。

第4実施例では、第1実施例の計算方法を、一般のウィンドウ幅wに拡張した方法に関して説明する。第4実施例では、図12で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部115（図1の135）は、エンコード部1202、前計算部1203、実計算部1204からなる。エンコード部1202は、BinaryToMOFエンコード部1205、MOFTowcMOFエンコード部1207からなる。BinaryToMOFエンコード部1205は、第1実施例のBinaryToMOFエンコード部305と同様の構成を備える。MOFTowcMOFエンコード部1207は、繰り返し判定部1271、変換部1272からなる。前計算部1203は、加算部1231、2倍算部1232、繰り返し判定部1233からなる。実計算部1204は、第1実施例の実計算部304と同様の構成を備える。

スカラー倍計算部115がスカラー値d及び楕円曲線上の点Pから、楕円曲線におけるスカラー倍点dPを計算する第4の計算方法を説明する。

スカラー倍計算部115が暗号化処理部112からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部1202は、入力されたスカラー値dを式13、式14をみたす数値列d_w[j]にエンコードする。前計算部1203は、入力された楕円曲線上の点Pから事前計算テーブルを作成する。事前計算テーブルはP, 3P, …, (2^w-1-1)Pにより構成される。実計算部1204は、エンコードされたスカラー値と事前計算テーブルを用いてスカラー倍点dPを計算する。

なお、エンコード部1202の行うエンコード処理は、スカラー値dを受け取った後、および実計算部1204がスカラー倍点を計算する前であればよい。すなわち、前計算部1203が事前計算テーブルを作成する前に行っても、後に行ってもよい。

また、点Pが固定点である場合、前計算部1203の行う事前計算テーブルの作成処理は、ただ一度行えばよい。すなわち、一旦事前計算テーブルを作成すれば、それ以降のスカラー倍計算では事前計算テーブルを再作成する必要はない。

次に、エンコード部1202、前計算部1203、実計算部1204の行う各処理について詳細に説明する。

まず、エンコード部1202の行う処理について説明する。
エンコード部1202は、バイナリ列dを数値列cmdに変換する。

エンコード部1202にバイナリ列dが入力されると、BinaryToMOFエンコード部1205はバイナリ列dを符号付バイナリ列mdに変換する。

MOFTowcMOFエンコード部1207は、BinaryToMOFエンコード部1205が変換した符号付バイナリ列mdを数値列cmdに変換する。ただし、数値列cmdの各数値cmd_iの取りうる値は、
-2^w-1≦cmd_i≦2^w-1, cmd_i=0 or 奇数 (式32)
である。

エンコード部1202は、MOFTowcMOFエンコード部1207が変換した数値列cmdをエンコードされた数値列d_w[j]として出力する。すなわち、各jに対して、d_w[j] = cmd_jである。ただし、cmd_jはcmdのjビット目の値とする。

次に、BinaryToMOFエンコード部1205の行う処理について説明する。BinaryToMOFエンコード部1205の行う処理は、第1実施例のBinaryToMOFエンコード部305の行う処理と同様の処理を行う。

次に、図13を用いて、MOFTowcMOFエンコード部1207の行う処理について説明する。

変数iをnで初期化する(1301)。

変換部1272は、md_i =0かどうかを判定する。md_i =0 の場合、ステップ1303へ行く。md_i !=0の場合、ステップ1311へ行く(1302)。

ステップ1302でmd_i =0 の場合、
変換部1272は、cmd_i にmd_i を代入する(1303)。

変数iを1減少させ、ステップ1305へ行く(1304)。

ステップ1302でmd_i !=0 の場合、
変換部1272は、i >= j >= i-(w-1) の範囲のjで、md_j !=0をみたすもののうち、最小のものをjとする(1311)。

変換部1272は、cmd_i, ..., cmd_i-j+1 に0を、cmd_i-j に
md_i 2^j +md_i-1 2^j-1 +... +md_i-j （式33）
を、cmd_i-j-1, ..., cmd_i-(w-1) に0を、それぞれ代入する(1312)。

変数iをw減少させ、ステップ1305へ行く(1313)。

繰り返し判定部1271は、i>=w-1かどうかを判定する。i>=w-1の場合、ステップ1302へ戻る。i<w-1の場合、ステップ1306へ行く(1305)。

ステップ1305でi<w-1の場合、
i>=0かどうかを判定する。i>=0の場合、ステップ1307へ行く。i<0の場合、ステップ1309へ行く(1306)。

ステップ1306でi>=0の場合、
変換部1272は、j>=0 の範囲のjで、md_j !=0をみたすもののうち、最小のものをjとする(1307)。

変換部1272は、cmd_i, ..., cmd_i-j+1 に0を、cmd_i-j に
md_i 2^j +md_i-1 2^j-1 +... +md_i-j （式34）
を、cmd_i-j-1, ..., cmd₀ に0を、それぞれ代入する(1308)。

cmd_n, ..., cmd₀ を変換された数値列cmdとして出力する(1309)。

本明細書では、この数値列cmdをwcMOF表現と呼ぶ。

次に、図14を用いて、前計算部1203が楕円曲線上の点から、事前計算テーブルを作成する方法を説明する。

2倍算部1232は、点PをECDBLにより2倍し、その結果を点2Pに格納する(1401)。

変数jに初期値1を代入する(1402)。

繰り返し判定部1233は、jが2^w-1より小さいかどうかを判定する。jが2^w-1より小さい場合はステップ1204へ行く。2^w-1以上の場合はステップ1411へ行く(1403)。

ステップ1403でjが2^w-1より小さい場合、
加算部1231は、点2Pと点(2j-1)PをECADDにより加算し、その結果を点(2j+1)Pに格納する(1404)。

変数jを1増加させ、ステップ1403へ戻る(1405)。

ステップ1403でjが2^w-1以上の場合、
P, 3P, …, (2^w-1-1)Pを事前計算テーブルとして出力する(1411)。

また、楕円曲線上の点Q=(x,y)に対して、楕円曲線加算に関する逆元の点-Qは、-Q=(x,-y)と表されるため、点Qの座標が与えられていれば容易に計算できる。そのため、点P, 3P, …, (2^w-1-1)Pのみを事前計算テーブルとして格納する。その後の実計算部1204が行う計算で必要となる点-P, -3P, …, -(2^w-1-1)Pは、それらから導出すればよく、事前計算テーブルには格納する必要はない。

なお、前計算部1203の行う事前計算テーブルの作成処理は、点P, 3P, …, (2^w-1-1)Pが計算されればよい。そのため、非特許文献5の481ページに記載されているモンゴメリトリックを用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化をはかってもよい。

最後に、図6を用いて、実計算部1204がエンコードされたスカラー値と楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。

変数cに初期値nを代入する(601)。

d_w[c]が0か0でないかを判定する。

d_w[c]が0の場合はステップ603へ行く。0でなければステップ611へ行く(602)。

変数cを1減少させ、ステップ602へ戻る(603)。

ステップ602でd_w[c]が0でない場合、点Qにd_w[c]Pを代入する(611)。

変数jに初期値c-1を代入する(612)。

繰り返し判定部1244は、jが0より小さいかどうかを判定する。jが0より小さい場合はステップ621へ行く。0以上の場合はステップ614へ行く(613)。

ステップ613でjが0以上の場合、
2倍算部は、点QをECDBLにより2倍し、点Qに再び格納する(614)。

ビット値判定部1241は、d_w[j]が0か0でないかを判定する。d_w[j]が0の場合はステップ617へ行く。0でなければステップ616へ行く(615)。

ステップ615でd_w[j]が0でない場合、
加算部1242は、点Qとd_w[j]PとをECADDにより加算する。ただし、d_w[j]が負の場合は(-d_w[j])Pのy座標を反転したものを用いて加算を行う。その結果を点Qに格納し、ステップ617へ行く(616)。
なお、d_w[j]が0でない場合は、d_w[j]はエンコード部1202の出力であるので、1,3,..., 2^w-1-1のいずれかの値である。そのため、d_w[j]Pもしくは(-d_w[j])Pのいずれかが、事前計算テーブルに必ず存在する。

変数jを1減少させ、ステップ613へと戻る(617)。

ステップ613でjが0より小さい場合、
点Qを出力する(621)。

第1実施例で説明した通り、BinaryToMOFエンコード部1205が出力する符号付バイナリ列mdは、式18をみたす。また、md_i は0,1,-1のいずれかの値のみを取りうる。

MOFTowcMOFエンコード部1207が出力する数値列cmdは、
d = cmd_n2ⁿ+cmd_n-12^n-1+…+ cmd₀ (式35)
をみたす。この理由は次の通りである。
ステップ1312で変換されるcmd_i, ..., cmd_i-(w-1) は、
cmd_i2^w-1+cmd_i-12^w-2+…+ cmd_i-(w-1) = md_i2^w-1+md_i-12^w-2+…+ md_i-(w-1) (式36)
をみたす。また、ステップ1308で変換されるcmd_i, ..., cmd_i-(w-1) も
cmd_i2^w-1+cmd_i-12^w-2+…+ cmd₀ = md_i2^w-1+md_i-12^w-2+…+ md₀ (式37)
をみたす。そのため、
cmd_n2ⁿ+cmd_n-12^n-1+…+ cmd₀ = md_n2ⁿ+md_n-12^n-1+…+ md₀ (式38)
が成り立つ。md はBinaryToMOFエンコード部1205の出力であるので、式18をみたす。したがって、式35が成り立つ。

MOFTowcMOFエンコード部1207が出力する数値列cmdは、式32をみたす。なぜならば、ステップ1312でエンコードされるcmd_i-j はmdがMOF表現であり、またjの取り方から必ず奇数となるからである。

結果として、エンコード部1202が出力する数値列d_w[j]は、式13、式14をみたす。

そのため、第1実施例で説明した通り、実計算部1204が出力する点Qはスカラー倍点dPに等しい。

第1実施例で説明した通り、BinaryToMOFエンコード部1205の行う処理はleft-to-rightである。

MOFTowcMOFエンコード部1207の行う処理はleft-to-rightである。なぜならば、ステップ1312の変換では、順次iが大きい方からmd_iを用いてcmd_iの値を割当てるからである。

結果として、エンコード部1202の行う処理はleft-to-rightである。

MOFTo2cMOFエンコード部1207が出力するcmdは、非零濃度が1/(w+1)となる。この理由は次の通りである。
ステップ1302でmd_i の値により処理を2つに振分ける。MOF表現における各ビットの値の出現確率は、0、非零ともに1/2である。ステップ1303-ステップ1304の処理が実行された場合、処理ビット数は1で 非零ビットの数は0個である。そのため、非零ビットの出現する期待値は1/2である。ステップ1311-ステップ1313の処理が実行された場合、処理ビット数はwで非零ビット数は1である。そのため、非零ビットの出現する期待値は1/(2w)である。非零濃度はこれらの期待値の調和平均となるため、1/(2+2w) = 1/(w+1) となる。また、非特許文献1によれば、ウィンドウ幅wに対して、非零濃度1/(w+1)が最小であることが示されている。

したがって、エンコード部1202の出力も非零濃度1/(w+1)となり、最小の非零濃度である。

実計算部1204の加算部1242が実行する楕円加算の回数は、エンコードされた数値列の非零ビットの個数となる。この非零ビットの個数は最小であるため、楕円加算の回数は最小となる。

以上の通り、上記計算方法は、エンコード処理をleft-to-rightで行うことが可能である。また、エンコードされた数値列は最小の非零濃度を持つため、楕円加算を行う回数が少なくてすみ、そのため、高速に計算することが可能である、という特徴がある。また、第4実施例ではウィンドウ幅を自由に設定することができる。そのため、高速性を重視する場合には、ウィンドウ幅を大きく設定することにより、高速な演算を達成することができる。

なお、第4の計算方法でも楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数2の有限体上で定義された楕円曲線や、OEF(Optimal Extension Field)上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよいことも、第1実施例と同様である。

第5実施例では、第4実施例のエンコード処理を より効率的に行う方法について説明する。第5実施例では、図15で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部115（図1の135）は、エンコード部1502、前計算部1503、実計算部1504からなる。エンコード部1502は、エンコード用テーブル作成部1508、BinaryTowcMOFエンコード部1509からなる。エンコード用テーブル作成部1508は、繰り返し判定部1581、変換部1582からなる。BinaryTowcMOFエンコード部1509は、繰り返し判定部1591、変換部1592からなる。前計算部1503は、第4実施例の前計算部1203と同様の構成を備える。実計算部1204は、第1実施例の実計算部304と同様の構成を備える。

スカラー倍計算部115がスカラー値d及び楕円曲線上の点Pから、楕円曲線におけるスカラー倍点dPを計算する第5の計算方法を説明する。

スカラー倍計算部115が暗号化処理部112からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部1502は、入力されたスカラー値dを式13、式14をみたす数値列d_w[j]にエンコードする。前計算部1503は、入力された楕円曲線上の点Pから事前計算テーブルを作成する。事前計算テーブルはP, 3P, …, (2^w-1-1)Pにより構成される。実計算部1504は、エンコードされたスカラー値と事前計算テーブルを用いてスカラー倍点dPを計算する。

なお、エンコード部1502の行うエンコード処理は、スカラー値dを受け取った後、および実計算部1504がスカラー倍点を計算する前であればよいことも、第4実施例と同様である。

また、点Pが固定点である場合、前計算部1503の行う事前計算テーブルの作成処理は、ただ一度行えばよいことも、第4実施例と同様である。

次に、エンコード部1502、前計算部1503、実計算部1504の行う各処理について詳細に説明する。

まず、エンコード部1502の行う処理について説明する。
エンコード部1502は、バイナリ列dを数値列d_w[j]に変換する。

エンコード部1502にバイナリ列dが入力されると、エンコード用テーブル作成部1508は、エンコード用のテーブルを作成する。

BinaryTowcMOFエンコード部1509は、エンコード用テーブル作成部1508が作成したエンコード用テーブルを用いて、入力されたバイナリ列dを、数値列cmdに変換する。

エンコード部1502は、BinaryTowcMOFエンコード部1509が変換した数値列cmdをエンコードされた数値列d_w[j]として出力する。すなわち、各jに対して、d_w[j] = cmd_jである。ただし、cmd_jはcmdのjビット目の値とする。

なお、エンコード用テーブル作成部1508の行うエンコード用テーブルの作成処理は、与えられたウィンドウ幅wに対して ただ1度行えばよい。そのため、同じウィンドウ幅を用いる場合は、エンコード用テーブルを再作成する必要はない。

また、エンコード用テーブル作成処理は、BinaryToMOFエンコード部1509がエンコード処理を行う前であればよく、エンコード部1508にバイナリ列dが入力される前であってもよい。

次に、図17を用いて、エンコード用テーブルの構成について説明する。

第4実施例のエンコード部1202の行う変換では、入力されたバイナリ列の2ビットをスキャンし、それらビットが一致しない場合、w+1ビットをスキャンし、対応する数値に変換する、といった処理が行われている。したがって、w+1ビットのバイナリ列dで上位2ビットが一致しないものに対して、変換前後の対応を示したテーブルをエンコード用テーブルとして用意することにより、効率的な変換を行うことができる。

w+1ビットのバイナリ列dで上位2ビットが一致しないものが与えられたとき、対応するwビットのMOF表現mdを、md = sdm*2^sde と、整数sdm, sdeを用いて表現することができる(1701)。このとき、整数sdm, sde は、
-2^w-1≦sdm≦2^w-1, sdm=奇数 (式39)
0≦sde≦w-2 (式40)
の範囲となる。このsdm, sdeを用いることにより、変換後の数値列cmdは(0, ..., 0, sdm, 0, ..., 0)と表すことができる(1702)。そのため、このsdm,sdeを用いてエンコード用テーブルを構成すればよい。

エンコード用テーブルは、ウィンドウ幅wから定まり、sdm, sdeの2つの配列からなる。sdm, sdeの要素数はともに2^w個である。w+1ビットの非零バイナリ列dで上位2ビットが一致しないものに対して、sdm, sdeのj=d-2^w-1 番目の要素sdm[j], sde[j]に対応するsdm, sdeを格納する。w=2の場合の対応を1703に、w=3の場合の対応を1704に示している。dはw+1ビットのバイナリ列dで上位2ビットが一致しないもの、d_decはその10進表現、d_dec -2^w-1 はエンコード用テーブルのインデックス、mdはdのwビットのMOF表現、md_decはその10進表現、sdmはdに対応する対応するsdm、sdeはdに対応するsde、cmdはMOF表現mdに対応するwcMOF表現を、それぞれ表す。

次に、図16を用いて、エンコード用テーブル作成部1508の行う処理について説明する。

変数dを2^w-1で初期化する(1601)。

繰り返し判定部1581は、d<=3*2^w-1 かどうかを判定する。d<=3*2^w-1 の場合、ステップ1603へ行く。d>3*2^w-1 の場合、ステップ1621へ行く(1602)。

ステップ1602でd<=3*2^w-1 の場合、
変換部1582は、変数mdに(d&(2^w-1))-(d>>1)を代入する(1603)。ただし、”&”はビット毎の論理積を、”>>”は右シフトを表す。これらの演算は、ほぼ全てのCPUに命令として具備されており、CPU上で効率的に実行することが可能である。

変数jにd-2^w-1を代入する(1604)。

変換部1582は、変換テーブルの要素sde[j]を0で初期化する(1605)。

変換部1582は、(md&1)=0かどうかを判定する。(md&1)=0の場合、ステップ1611へ行く。(md&1)!=0の場合、ステップ1607へ行く(1606)。

ステップ1606で(md&1)=0の場合、
変換部1582は、変換テーブルの要素sde[j]を1増加させる(1611)。

変換部1582は、変数mdを1ビット右シフトし、ステップ1606へ戻る(1612)。

ステップ1606で(md&1)!=0の場合、
変換部1582は、変換テーブルの要素sdm[j] にmdを代入する(1607)。

変数dを1増加し、ステップ1602へ戻る(1608)。

ステップ1602でd>3*2^w-1 の場合、
変換テーブルsde及びsdmを出力する(1621)。

次に、図18を用いて、BinaryTowcMOFエンコード部1509の行う処理について説明する。

変数iをnで初期化する。数値列cmdを0で初期化する。d_nを0で初期化する(1801)。

繰り返し判定部1591は、i>=1かどうかを判定する。i>=1の場合、ステップ1803へ行く。i<1の場合、ステップ1811へ行く(1802)。

ステップ1802でi>=1の場合、
変換部1592は、d_i XOR d_i+1 =0かどうかを判定する。d_i XOR d_i+1 =0の場合、ステップ1807へ行く。d_i XOR d_i+1 !=0の場合、ステップ1804へ行く(1803)。なお、”XOR”は、排他的論理和を表す。この演算は、ほぼ全てのCPUに命令として具備されており、CPU上で効率的に実行することが可能である。

ステップ1803でd_i XOR d_i+1 =0の場合、
変数iを1減少させ、ステップ1802へ戻る(1807)。

ステップ1803でd_i XOR d_i+1 !=0の場合、
変換部1592は、変数jに、((d>>(i-w))&(2^w+1-1))-2^w-1 を代入する(1804)。

変換部1592は、cmd_i-w+1+sde[j] に sdm[j] を代入する(1805)。

変数iをw減少させ、ステップ1802へ戻る(1806)。

ステップ1802でi<1の場合、
i=0 & d₀=0 かどうかを判定する。i=0 & d₀=0の場合、ステップ1812へ行く。i!=0 | d₀ !=0の場合、ステップ1813へ行く(1811)。なお、”|” は論理和を表す。

ステップ1802でi=0 & d₀=0の場合、
変換部1592は、cmd₀ に-1を代入し、ステップ1813へ行く(1812)。

cmd_n, ..., cmd₀ を数値列cmdとして出力する(1813)。

次に、前計算部1503の行う処理について説明する。
前計算部1503の行う処理は、第4実施例の前計算部1203の行う処理と同様の処理を行う。

最後に、実計算部1504の行う処理について説明する。
実計算部1504の行う処理は、第4実施例の実計算部1204の行う処理と同様の処理を行う。

BinaryTowcMOFエンコード部1509が出力する数値列cmdは、
d = cmd_n2ⁿ+cmd_n-12^n-1+…+ cmd₀ (式41)
をみたす。この理由は次の通りである。
ステップ1804、ステップ1805の処理は、該当するwビットの変換を行うものであり、図13のステップ1312の処理に相当する。そのため、式41が成り立つ。

また、BinaryTowcMOFエンコード部1509が出力する数値列cmdは、第4実施例で説明したように、式32をみたす。

結果として、エンコード部1502が出力する数値列d_w[j]は、式13、式14をみたす。

そのため、第1実施例で説明した通り、実計算部1504が出力する点Qはスカラー倍点dPに等しい。

BinaryTowcMOFエンコード部1509の行う処理はleft-to-rightである。なぜならば、ステップ1804、ステップ1805の変換では、順次iが大きい方からcmd_iの値を割当てるからである。

結果として、エンコード部1502の行う処理はleft-to-rightである。

エンコード部1502の出力する数値列d_w[j]は、非零濃度が1/(w+1)となり、最小の非零濃度である。なぜならば、エンコード部1502の出力は、第4実施例のエンコード部1202の出力と一致するからである。

実計算部1504の加算部1542が実行する楕円加算の回数は、エンコードされた数値列の非零ビットの個数となる。この非零ビットの個数は最小であるため、楕円加算の回数は最小となる。

以上の通り、上記計算方法は、エンコード処理をleft-to-rightで行うことが可能である。また、エンコードされた数値列は最小の非零濃度を持つため、楕円加算を行う回数が少なくてすみ、そのため、高速に計算することが可能である、という特徴がある。また、第5実施例ではウィンドウ幅を自由に設定することができる。そのため、高速性を重視する場合には、ウィンドウ幅を大きく設定することにより、高速な演算を達成することができる。また、効率的なエンコード処理を行うことができ、プログラムの簡素化やハードウェア論理回路の小規模化といったメリットがある。

なお、第5の計算方法でも楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数2の有限体上で定義された楕円曲線や、OEF(Optimal Extension Field)上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよいことも、第1実施例と同様である。

第6実施例では、第5実施例のエンコード処理を、実計算部の行う処理に組込み、楕円演算を行う際に逐次変換し用いる方法に関して説明する。第6実施例では、図19で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部115（図1の135）は、エンコード用テーブル作成部1908、前計算部1903、実計算部1904からなる。エンコード用テーブル作成部1908は、第5実施例のエンコード用テーブル作成部1508と同様の構成を備える。前計算部1503は、第4実施例の前計算部1203と同様の構成を備える。実計算部1204は、変換判定部1941、加算部1942、2倍算部1943、繰り返し判定部1944からなる。

スカラー倍計算部115がスカラー値d及び楕円曲線上の点Pから、楕円曲線におけるスカラー倍点dPを計算する第6の計算方法を説明する。

スカラー倍計算部115が暗号化処理部112からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード用テーブル作成部1908は、エンコード用のテーブルを作成する。前計算部1903は、入力された楕円曲線上の点Pから事前計算テーブルを作成する。事前計算テーブルはP, 3P, …, (2^w-1-1)Pにより構成される。実計算部1904は、入力されたスカラー値、事前計算テーブルおよびエンコード用テーブルを用いてスカラー倍点dPを計算する。

なお、点Pが固定点である場合、前計算部1903の行う事前計算テーブルの作成処理は、ただ一度行えばよいことも、第4実施例と同様である。

また、エンコード用テーブル作成部1908の行うエンコード用テーブルの作成処理は、与えられたウィンドウ幅wに対して ただ1度行えばよいことも、第5実施例と同様である。

また、エンコード用テーブル作成処理は、実計算部1904がスカラー倍点を計算する前であればよい。すなわち、前計算部1903が事前計算テーブルの作成の前に行っても、後に行ってもよい。

次に、エンコード用テーブル作成部1908、前計算部1903、実計算部1904の行う各処理について詳細に説明する。

まず、エンコード用テーブル作成部1908の行う処理について説明する。
エンコード用テーブル作成部1908の行う処理は、第5実施例のエンコード用テーブル作成部1508の行う処理と同様の処理を行う。

次に、前計算部1903の行う処理について説明する。
前計算部1903の行う処理は、第4実施例の前計算部1203の行う処理と同様の処理を行う。

最後に、図20、図21を用いて、実計算部1904の行う処理について説明する。

変数iをnで、点Qを無限遠点Oで初期化する(2001)。ここで無限遠点Oとは、楕円加算に関する単位元であり、任意の点Pに対して、P+O=O+P=Pをみたす。

繰り返し判定部1944は、i>=1かどうかを判定する。i>=1の場合は、ステップ2011へ行く。i<1の場合は、ステップ2021へ行く(2002)。

ステップ2002でi>=1の場合、
変換判定部1941は、d_i XOR d_i+1 =0かどうかを判定する。d_i XOR d_i+1 =0の場合、ステップ2012へ行く。d_i XOR d_i+1 !=0の場合、ステップ2131へ行く(2011)。

ステップ2011でd_i XOR d_i+1 =0の場合、
2倍算部1943は、点QをECDBLにより2倍し、点Qに再び格納する(2012)。

変数iを1減少させ、ステップ2002に戻る(2013)。

ステップ2011でd_i XOR d_i+1 !=0の場合、
変換判定部1941は、変数jに((d>>(i-w))&(2^w+1-1))-2^w-1 を代入する(2131)。
変数kを1減少させる(2132)。

変換判定部1941は、k<=w-sde[j] かどうかを判定する。k<=w-sde[j] の場合、ステップ2134へ行く、k>w-sde[j]の場合、ステップ2141へ行く(2133)。

ステップ2133でk<=w-sde[j] の場合、
2倍算部1943は、点QをECDBLにより2倍し、点Qに再び格納する(2134)。

変数kを1増加させ、変数iを1減少させ、ステップ2133に戻る(2135)。

ステップ2133でk>w-sde[j] の場合、
加算部1942は、点Qと点sdm[j]PとをECADDにより加算し、点Qに格納する(2141)。

変数kに1を代入する(2142)。

変換判定部1941は、k<=sde[j] かどうかを判定する。k<=sde[j]の場合、ステップ2144へ行く。k>sde[j]の場合、ステップ2002に戻る(2143)。

ステップ2143でk<=sde[j]の場合、
2倍算部1943は、点QをECDBLにより2倍し、点Qに再び格納する(2144)。

変数kを1増加させ、変数iを1減少させ、ステップ2143に戻る(2145)。

ステップ2002でi<1の場合、
i=0かどうかを判定する。i=0の場合、ステップ2022へ行く。i !=0の場合、ステップ2025へ行く(2021)。

ステップ2021でi=0の場合、
2倍算部1943は、点QをECDBLにより2倍し、点Qに再び格納する(2022)。

d₀ =0かどうかを判定する。d₀ =0 の場合、ステップ2024へ行く。d₀ !=0の場合、ステップ2025へ行く(2023)。

点Qをスカラー倍点dPとして出力する(2025)。

実計算部1904が出力する点Qはスカラー倍点dPに等しい。なぜならば、ステップ2012、ステップ2131-ステップ2145の各処理は、図13のステップ1303、ステップ1311-ステップ1312の各処理に相当する楕円演算となるからである。

また、第5実施例との対応関係により、実計算部1904の行う処理はleft-to-rightとなる。

実計算部1904の行う楕円加算の回数は最小である。なぜならば、実計算部1904の変換判定部1941の行う処理は、第5実施例のエンコード部1502の処理と対応がつくからである。

以上の通り、上記計算方法は、スカラー倍計算をleft-to-rightで行うことができる。また、楕円加算の回数は最小であるため、高速に計算することが可能である、という特徴がある。また、第6実施例ではウィンドウ幅を自由に設定することができる。そのため、高速性を重視する場合には、ウィンドウ幅を大きく設定することにより、高速な演算を達成することができる。また、エンコード処理と楕円演算を1度に行うため、エンコード結果を一旦メモリに格納する必要がなく、メモリ使用量を少なくすることができる。

なお、第6の計算方法でも楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数2の有限体上で定義された楕円曲線や、OEF(Optimal Extension Field)上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよいことも、第1実施例と同様である。

第7実施例では、第4実施例のエンコード処理におけるMOFTowcMOFエンコード方法を、MOFTowNAFエンコード方法に置きかえることにより、非零濃度が小さい別の表現方式であるwNAF表現でエンコードされた数値列を生成し、楕円演算を効率的に実行する方法を説明する。第7実施例では、図22で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部115（図1の135）は、エンコード部2202、前計算部2203、実計算部2204からなる。エンコード部2202は、BinaryToMOFエンコード部2205とMOFTowNAFエンコード部からなる。BinaryToMOFエンコード部2205は、繰り返し判定部2251と変換部2252からなる。MOFTowNAFエンコード部2207は、繰り返し判定部2271と変換部2272からなる。前計算部2203は、第4実施例の前計算部1203と同様の構成を備える。実計算部2204は、第4実施例の実計算部1204と同様の構成を備える。

スカラー倍計算部115がスカラー値d及び楕円曲線上の点Pから、楕円曲線におけるスカラー倍点dPを計算する第7の計算方法を説明する。

スカラー倍計算部115が暗号化処理部112からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部2202は、入力されたスカラー値dを式13、式14をみたす数値列d_w[j]にエンコードする。前計算部2203は、入力された楕円曲線上の点Pから事前計算テーブルを作成する。事前計算テーブルはP, 3P, …, (2^w-1-1)Pにより構成される。実計算部2204は、エンコードされたスカラー値と事前計算テーブルを用いてスカラー倍点dPを計算する。

なお、エンコード部2202の行うエンコード処理は、スカラー値dを受け取った後、および実計算部2204がスカラー倍点を計算する前であればよいことも第4実施例と同様である。

また、点Pが固定点である場合、前計算部2203の行う事前計算テーブルの作成処理は、ただ一度行えばよいことも第4実施例と同様である。

次に、エンコード部2202、前計算部2203、実計算部2204の行う各処理について詳細に説明する。

まず、エンコード部2202の行う処理について説明する。
エンコード部2202は、バイナリ列dを数値列cmdに変換する。

エンコード部2202にバイナリ列dが入力されると、BinaryToMOFエンコード部2205はバイナリ列dを符号付バイナリ列mdに変換する。

MOFTowNAFエンコード部2207は、BinaryToMOFエンコード部2205が変換した符号付バイナリ列mdを数値列cmdに変換する。ただし、数値列cmdの各数値cmd_iの取りうる値は、
-2^w-1≦cmd_i≦2^w-1, cmd_i=0 or 奇数 (式42)
である。この変換はright-to-leftで行われる。

エンコード部2202は、MOFTowNAFエンコード部2207が変換した数値列cmdをエンコードされた数値列d_w[j]として出力する。すなわち、各jに対して、d_w[j] = cmd_jである。ただし、cmd_jはcmdのjビット目の値とする。

次に、BinaryToMOFエンコード部2205の行う処理について説明する。BinaryToMOFエンコード部2205の行う処理は、第1実施例のBinaryToMOFエンコード部305の行う処理と同様の処理を行う。

次に、図23を用いて、MOFTowNAFエンコード部2207の行う処理について説明する。

変数iを0で初期化する(2301)。

変換部2272は、md_i =0かどうかを判定する。md_i =0 の場合、ステップ2303へ行く。md_i !=0の場合、ステップ2311へ行く(2302)。

ステップ2302でmd_i =0 の場合、
変換部2272は、cmd_i にmd_i を代入する(2303)。

変数iを1増加させ、ステップ2305へ行く(2304)。

ステップ2302でmd_i !=0 の場合、
変換部1272は、cmd_i に
md_i+w-1 2^w-1 +md_i+w-2 2^w-2 +... +md_i （式43）
を、cmd_i+1, ..., cmd_i+w-1 に0を、それぞれ代入する(1311)。

変数iをw増加させ、ステップ2305へ行く(2312)。

繰り返し判定部2271は、i<=nかどうかを判定する。i<=nの場合、ステップ2302に戻る。i>nの場合、ステップ2321へ行く(2305)。

ステップ2305でi<w-1の場合、
cmd_n, ..., cmd₀ を変換された数値列cmdとして出力する(2321)。

本明細書では、この数値列cmdをwNAF表現と呼ぶ。

次に、前計算部2203の行う処理について説明する。
前計算部2203の行う処理は、第4実施例の前計算部1203の行う処理と同様の処理を行う。

最後に、実計算部2204の行う処理について説明する。
実計算部2204の行う処理は、第4実施例の実計算部1204の行う処理と同様の処理を行う。

第1実施例で説明した通り、BinaryToMOFエンコード部2205が出力する符号付バイナリ列mdは、式18をみたす。また、md_i は0,1,-1のいずれかの値のみを取りうる。

MOFTowNAFエンコード部2207が出力する数値列cmdは、
d = cmd_n2ⁿ+cmd_n-12^n-1+…+ cmd₀ (式44)
をみたす。この理由は次の通りである。
ステップ2311で変換されるcmd_i, ..., cmd_i+w-1 は、
cmd_i2^w-1+cmd_i-12^w-2+…+ cmd_i-(w-1) = md_i2^w-1+md_i-12^w-2+…+ md_i-(w-1) (式45)
をみたす。また、ステップ2303で変換されるcmd_i は cmd_i = md_i である。そのため、
cmd_n2ⁿ+cmd_n-12^n-1+…+ cmd₀ = md_n2ⁿ+md_n-12^n-1+…+ md₀ (式46)
が成り立つ。md はBinaryToMOFエンコード部2205の出力であるので、式18をみたす。したがって、式44が成り立つ。

MOFTowNAFエンコード部2207が出力する数値列cmdは、式42をみたす。なぜならば、ステップ2311でエンコードされるcmd_i はmdがMOF表現であり、またmd_i !=0の場合にのみ ステップ2311が実行されるため、必ず奇数となるからである。

結果として、エンコード部2202が出力する数値列d_w[j]は、式13、式14をみたす。

そのため、第1実施例で説明した通り、実計算部2204が出力する点Qはスカラー倍点dPに等しい。

第1実施例で説明した通り、BinaryToMOFエンコード部2205の行う処理はleft-to-rightである。ところが、right-to-leftでも処理を行うことができる。なぜならば、各md_i はd_i, d_i-1 からのみ定まるからである。すなわち、iが小さいものより順にmd_i を定めることもできる。そのため、必要であれば、BinaryToMOFエンコード部2205の処理をright-to-left で行ってもよい。

MOFTowNAFエンコード部2207の行う処理はright-to-leftである。なぜならば、ステップ2311、ステップ2303の変換では、順次iが小さい方からmd_iを用いてcmd_iの値を割当てるからである。

結果として、エンコード部2202の行う処理はright-to-leftで行うことが可能である。

MOFTowNAFエンコード部2207が出力するcmdは、非零濃度が1/(w+1)となる。この理由は次の通りである。
ステップ2302でmd_i の値により処理を2つに振分ける。MOF表現における各ビットの値の出現確率は、0、非零ともに1/2である。ステップ2303-ステップ2304の処理が実行された場合、処理ビット数は1で 非零ビットの数は0個である。そのため、非零ビットの出現する期待値は1/2である。ステップ2311-ステップ2312の処理が実行された場合、処理ビット数はwで非零ビット数は1である。そのため、非零ビットの出現する期待値は1/(2w)である。非零濃度はこれらの期待値の調和平均となるため、1/(2+2w) = 1/(w+1) となる。また、非特許文献1によれば、ウィンドウ幅wに対して、非零濃度1/(w+1)が最小であることが示されている。

したがって、エンコード部2202の出力も非零濃度1/(w+1)となり、最小の非零濃度である。

実計算部2204の加算部2242が実行する楕円加算の回数は、エンコードされた数値列の非零ビットの個数となる。この非零ビットの個数は最小であるため、楕円加算の回数は最小となる。

以上の通り、上記計算方法は、MOF表現を通じて、エンコード処理をright-to-leftで行うことが可能である。また、楕円加算の回数が最小であり、高速に計算することが可能である、という特徴がある。また、第7実施例ではウィンドウ幅を自由に設定することができる。そのため、高速性を重視する場合には、ウィンドウ幅を大きく設定することにより、高速な演算を達成することができる。

なお、第7の計算方法でも楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数2の有限体上で定義された楕円曲線や、OEF(Optimal Extension Field)上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよいことも、第1実施例と同様である。

なお、第7の計算方法では、BinaryToMOFエンコード部2205とMOFTowNAFエンコード部2207とにエンコード処理を分けて説明したが、第5実施例のように、2つのエンコード処理を合成してもよい。また、第5実施例のように変換テーブルを用いてもよい。さらに、第6実施例のように実計算部2204の行う処理に、エンコード処理を組み込んでもよい。そうすることにより、メモリ使用量の更なる削減、更なる高速化、プログラムの更なる簡素化やハードウェア論理回路の小規模化といったメリットがある。

第8実施例では、第7実施例の、wNAF表現へのエンコード処理を、left-to-rightで行う方法を説明する。第8実施例では、図24で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部115（図1の135）は、エンコード部2402、前計算部2403、実計算部2404からなる。エンコード部2402は、BinaryToNAFエンコード部2407からなる。BinaryToNAFエンコード部2407は、繰り返し判定部2471と変換部2472からなる。前計算部2403は、第4実施例の前計算部1203と同様の構成を備える。実計算部2404は、第4実施例の実計算部1204と同様の構成を備える。

スカラー倍計算部115がスカラー値d及び楕円曲線上の点Pから、楕円曲線におけるスカラー倍点dPを計算する第8の計算方法を説明する。

スカラー倍計算部115が暗号化処理部112からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部2402は、入力されたスカラー値dを式13、式14をみたす数値列d_w[j]にエンコードする。前計算部2403は、入力された楕円曲線上の点Pから事前計算テーブルを作成する。事前計算テーブルはP, 3P, …, (2^w-1-1)Pにより構成される。実計算部2404は、エンコードされたスカラー値と事前計算テーブルを用いてスカラー倍点dPを計算する。第8実施例では特にw=2の場合について説明する。

なお、エンコード部2402の行うエンコード処理は、スカラー値dを受け取った後、および実計算部2404がスカラー倍点を計算する前であればよいことは第4実施例と同様である。

また、点Pが固定点である場合、前計算部2403の行う事前計算テーブルの作成処理は、ただ一度行えばよいことも第4実施例と同様である。

次に、エンコード部2402、前計算部2403、実計算部2404の行う各処理について詳細に説明する。

まず、エンコード部2402の行う処理について説明する。
エンコード部2402は、バイナリ列dを数値列cmdに変換する。

エンコード部2402にバイナリ列dが入力されると、BinaryToNAFエンコード部2407はバイナリ列dを数値列cmdに変換する。

エンコード部2402は、BinaryToNAFエンコード部2407が変換した数値列cmdをエンコードされた数値列d_w[j]として出力する。すなわち、各jに対して、d_w[j] = cmd_jである。ただし、cmd_jはcmdのjビット目の値とする。

次に、図25を用いて、BinaryToNAFエンコード部2407の行う処理について説明する。

変数iをnで初期化する(2501)。

d_n, d_-1, d_-2 をそれぞれ0で初期化する(2502)。

繰り返し判定部2471は、i>-1かどうかを判定する。i>-1の場合、ステップ2504へ行く。i<=-1の場合、ステップ2521へ行く(2503)。

ステップ2503でi>-1の場合、
変換部2472は、bにd_i-1 d_i を代入する(2504)。

変換部2472は、b=0かどうかを判定する。b=0の場合、ステップ2506へ行く。b!=0の場合、ステップ2511へ行く(2505)。

ステップ2505でb=0の場合、
変換部2472は、cmd_i に0を代入する(2506)。

変数iを1減少させ、ステップ2503に戻る(2507)。

ステップ2505でb !=0 の場合、
変換部2472は、 d_i-j-1 = d_i-j となる最大のjを見つける(2511)。

変換部2472は、jが奇数かどうかを判定する。jが奇数の場合、ステップ2514へ行く。jが偶数の場合、ステップ2513へ行く(2512)。

ステップ2512でjが奇数の場合、
変換部2472は、cmd_i, cmd_i-1, cmd_i-2, ..., cmd_i-j+2, cmd_i-j+1, cmd_i-j に、それぞれb, 0, -b, ..., 0, -b, 0 を代入し、ステップ2515へ行く(2514)。

ステップ2512でjが偶数の場合、
変換部2472は、cmd_i, cmd_i-1, ..., cmd_i-j+2, cmd_i-j+1, cmd_i-j に、それぞれ0, b, ..., 0, b, 0 を代入し、ステップ2515へ行く(2513)。

変数iをj+1減少させ、ステップ2503に戻る(2515)。

ステップ2503でi<=-1の場合、
cmd_n, ..., cmd₀ を変換された数値列cmdとして出力する(2521)。

なお、BinaryToNAFエンコード部2407の出力するcmd_i は、0, 1, -1のいずれかの値のみを取りうる。なぜならば、bはd_i-1 d_i で与えられ、cmd_i には0, b, -b のいずれかの値のみが割当てられるからである。

次に、前計算部2203の行う処理について説明する。
前計算部2203の行う処理は、第4実施例の前計算部1203の行う処理と同様の処理を行う。

最後に、実計算部2204の行う処理について説明する。
実計算部2204の行う処理は、第4実施例の実計算部1204の行う処理と同様の処理を行う。

BinaryToNAFエンコード部2407が出力する数値列cmdは、
d = cmd_n2ⁿ+cmd_n-12^n-1+…+ cmd₀ (式47)
をみたす。この理由は次の通りである。
ステップ2511-ステップ2514の処理は、MOF表現から、次の変換を行うことに相当する。
0, 1, -1, 1, -1, ..., -1, 1, 0 → 0, 1, 0, -1, 0, ..., 0, -1, 0
0, -1, 1, -1, 1, ..., 1, -1, 0 → 0, -1, 0, 1, 0, ..., 0, 1, 0
0, 1, -1, 1, -1, ..., 1, -1, 0 → 0, 0, 1, 0, 1, ..., 0, 1, 0
0, -1, 1, -1, 1, ..., -1, 1, 0 → 0, 0, -1, 0, -1, ..., 0, -1, 0
したがって、式47が成り立つ。

結果として、エンコード部2402が出力する数値列d_w[j]は、式13、式14をみたす。

そのため、第1実施例で説明した通り、実計算部2404が出力する点Qはスカラー倍点dPに等しい。

BinaryToNAFエンコード部2407の行う処理はleft-to-rightである。なぜならば、ステップ2511-ステップ2514、ステップ2506の各変換では、順次iが大きい方からcmd_iの値を割当てるからである。

結果として、エンコード部2402の行う処理はleft-to-rightである。

BinaryToNAFエンコード部2407が出力するcmdは、非零濃度が1/3となる。なぜならば、BinaryToNAFエンコード部2407の出力は、ウィンドウ幅が2の時の、第7実施例のMOFTowNAFエンコード部2207の出力と一致し、その非零濃度は1/3だからである。

したがって、エンコード部2402の出力も非零濃度1/3となり、最小の非零濃度である。

実計算部2404の加算部2442が実行する楕円加算の回数は、エンコードされた数値列の非零ビットの個数となる。この非零ビットの個数は最小であるため、楕円加算の回数は最小となる。

以上の通り、上記計算方法は、エンコード処理をleft-to-rightで行うことが可能である。また、楕円加算の回数が最小であり、高速に計算することが可能である、という特徴がある。

なお、第8の計算方法でも楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数2の有限体上で定義された楕円曲線や、OEF(Optimal Extension Field)上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよいことも、第1実施例と同様である。

なお、第8の計算方法では、BinaryToNAFエンコード部2407の行うエンコード法としてw=2の場合を説明したが、入力されるバイナリ列に対するMOF表現を考え、そのMOF表現を、
0...0 | r | b_i | t_i |...| b₂ | t₂ | b₁ | t₁ | 0...0
を一つのブロックとして分割し、最上位のブロックからwNAF表現に変換することにより、一般のウィンドウ幅wに対してもエンコードを行うことが可能である。ただし、rは高々w-1ビットのMOF表現、各b_j は高々w-2ビットの0値ビット（0値ビットが0個の場合も含む）、各t_j はwビットのMOF表現を、それぞれ表し、ブロックの最初と最後の0値ビットは各々w-1個連続する。

なお、第3実施例と同様に、エンコード処理を実計算部2404の行う処理に組み込んで行ってもよい。そうすることにより、メモリ使用量の更なる削減、更なる高速化、プログラムの更なる簡素化やハードウェア論理回路の小規模化といったメリットがある。

以上、コンピュータＡ101が、入力メッセージを暗号化する場合のスカラー倍計算部115の動作を説明したが、コンピュータＢ121が暗号化されたデータ141を復号化する場合も同様である。

その場合には、コンピュータＢ121のスカラー倍計算部135は、既に説明した楕円曲線上の点(x_e2, y_e2)、秘密情報a125によるスカラー倍点(x_d3, y_d3)を出力する。このとき、上記計算方法で説明したスカラー値dを秘密情報a125、楕円曲線上の点Pを楕円曲線上の点(x_e2, y_e2)として同様の処理を行うことにより、スカラー倍点を求めることができる。
次に、本発明を署名検証システムに適用する実施形態を、図26と図2を用いて説明する。

図26の署名検証システムは、スマートカード2601と署名検証処理を行うコンピュータ2621とから成る。

スマートカード2601は、図1のコンピュータＡと類似の構成を備え、ＣＰＵ2613やコプロセッサ2614などの演算装置が記憶部2602に格納されているプログラムを実行することにより、データ処理部ではなく、署名生成処理部2612を実現する。ただし、図1に示す外部記憶装置107、ディスプレイ108、キーボード109を備えなくてもよい。

コンピュータ2621は、コンピュータＡと同様の構成を備え、ＣＰＵ2633がプログラムを実行することによりデータ処理部ではなく、署名検証処理部2632を実現する。

スカラー倍計算部2615と2635は図1に示すスカラー倍計算部115または135と同様の機能を備える。

なお、本実施例において、コンピュータ2621内の各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていてもよいし、必要なときに、コンピュータ2621が利用可能な媒体を介して他の装置から上記記憶部に導入されてもよい。

さらに、スマートカード2601内の各プログラムは、あらかじめ、上記スマートカード2601内の記憶部に格納されてもよいし、必要なときに、入出力インタフェース2610を介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して上記記憶部に導入されてもよい。

媒体とは、例えば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。

図26の署名検証システムにおける署名生成と署名検証動作を、図2を参照して説明する。

コンピュータ2621は、ランダムに選んだ数値をチャレンジコード2643として、スマートカード2601に転送する。

署名生成処理部2612（図2の112）は、チャレンジコード2643を受付け、チャレンジコード2643のハッシュ値をとり、所定のビット長の数値fに変換する。

署名生成処理部2612は、乱数uを生成し、記憶部2602（図2の102）に格納されている定数2604から読み出した（図2の205）楕円曲線上の定点Qとともにスカラー倍計算部2615（図2の115）へ送る（図2の206）。

スカラー倍計算部2615は、定点Q、乱数uによるスカラー倍点(x_u,y_u)を計算し、計算されたスカラー倍点を署名生成処理部2612へ送る（図2の207）。

署名生成部2612は、送られたスカラー倍点を用いて署名の生成を行う。例えば、非特許文献4に記載されているECDSA署名であれば、
s = x_u mod q （式48）
t = u^-1(f+ds) mod q （式49）
を計算することによりチャレンジコード2643に対応する署名(s,t)を得る（図2の208）。

ここで、qは定点Qの位数、すなわち定点Qのq倍点qQが無限遠点になり、qより小さな数値mに対する定点Qのm倍点mQは無限遠点にはならない、というような数値のことである。

スマートカード2601は、署名生成処理部2612で作成した署名2641を入出力インタフェース2610より出力し、コンピュータ2621へ転送する。

コンピュータ2621の署名検証処理部2632（図2の112）は、署名2641が入力される（図2の204）と、署名2641の数値s,tが適切な範囲内、すなわち1≦s,t<qであるかを調べる。

数値s,tが上記範囲内になければチャレンジコード2643に対する署名の検証結果として「無効」を出力し、スマートカード2601を拒絶する。数値s,tが上記範囲内にあれば、署名検証処理部2632は、
h = t-1 mod q （式50）
h₁ = fh mod q （式51）
h₂ = sh mod q （式52）
を計算する。そして、記憶部2622（図2の102）に格納されている定数2624から読み出した（図2の205）公開鍵aQ及び定点Qと計算したh₁,h₂をスカラー倍計算部2635（図2の115）へ送る（図2の206）。

スカラー倍計算部2635は、定点Qとh₁によるスカラー倍点h₁Qと、公開鍵aQとh₂によるスカラー倍点h₂aQとを計算し、計算されたスカラー倍点を署名検証処理部2632へ送る（図2の207）。

署名検証処理部2632は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ECDSAの署名検証であれば、点R
R = h₁Q+h₂aQ （式53）
を計算し、そのx座標をx_Rとしたとき、
s' = x_R mod q （式54）
を計算し、s'=sであればチャレンジコード2643に対する署名の検証結果として「有効」を出力し、スマートカード2601を認証し、受入れる（図2の208）。

s'=sでなければ、「無効」を出力し、スマートカードを拒絶する（図2の208）。

上記実施形態のスカラー倍計算部2615、2635は、図1のスカラー倍計算部115または135と同様の機能を備えるので、メモリ使用量が小さく、かつ高速に計算できるスカラー倍計算を実行できる。特に、式53の計算では、非特許文献1の方法を用いた場合、数十バイトの余分なRAM領域を必要としたが、本発明の方法を用いた場合、h₁, h₂ の値を数ビットずつ読み込むため、余分なRAM領域を必要としない。スマートカード2601は、一般的にRAM2603の大きさは小さいため、本発明の方法が特に有効である。

そのため、スマートカード2601は署名生成処理を行う際に、コンピュータ2621は署名検証処理を行う際に、メモリ使用量が小さく、かつ高速に計算ができる。
次に本発明を鍵交換システムに適用する実施形態を説明する。本実施形態においては、図1のシステム構成が応用できる。

図1のデータ処理部112、132は、本実施形態においては、それぞれ鍵交換処理部112、132として機能する。

鍵交換システムのコンピュータＡ101が、入力されたデータ143から共有情報の導出を行う場合の動作について図1、図2を参照して説明する。

コンピュータＢ121の鍵交換処理部132は、記憶部122（図2の102）の定数125から秘密鍵bを読み出し、コンピュータＢ121の公開鍵bQを計算する。そして、ネットワーク142を介して、公開鍵bQをデータ143としてコンピュータＡ101に転送する。

コンピュータＡ101の鍵交換処理部112（図2の112）は、コンピュータＢ121の公開鍵bQの入力を受付ける（図2の204）と、鍵交換処理部112は、記憶部102から読み出した（図2の205）秘密情報105であるコンピュータＡ101の秘密鍵aと、コンピュータＢ121の公開鍵bQとをスカラー倍計算部115へ送る（図2の206）。

スカラー倍計算部115は、秘密鍵aと、公開鍵bQによるスカラー倍点abQを計算し、計算されたスカラー倍点を鍵交換処理部112へ送る（図2の207）。

鍵交換処理部112は、送られたスカラー倍点を用いて共有情報の導出を行ない、記憶部102に秘密情報105として格納する。例えば、スカラー倍点abQのx座標を、共有情報とする。

次に、コンピュータＢ121が、入力されたデータ141から共有情報の導出を行なう場合の動作について説明する。

コンピュータＡ101の鍵交換処理部112は、記憶部102（図2の102）の定数105から秘密鍵aを読み出し、コンピュータＡ101の公開鍵aQを計算する。そして、ネットワーク142を介して、公開鍵aQをデータ141としてコンピュータＢ121に転送する。

コンピュータＢ121の鍵交換処理部132（図2の112）は、コンピュータＡ101の公開鍵aQの入力を受付ける（図2の204）と、鍵交換処理部132は、記憶部122から読み出した（図2の205）秘密情報125であるコンピュータＢ121の秘密鍵bと、コンピュータＡ101の公開鍵aQとをスカラー倍計算部135へ送る（図2の207）。

スカラー倍計算部135は、秘密鍵bと、公開鍵aQによるスカラー倍点baQを計算し、計算されたスカラー倍点を鍵交換処理部132へ送る（図2の207）。

鍵交換処理部132は、送られたスカラー倍点を用いて共有情報の導出を行ない、記憶部122に秘密情報125として格納する。例えば、スカラー倍点baQのx座標を、共有情報とする。

ここで、数abと数baは数値として等しいので、点abQと点baQは同一の点となり、同一の情報が導出されたことになる。

ネットワーク142には、点aQと点bQが送信されるが、点abQ（もしくはbaQ）は送信されない。点abQ（もしくはbaQ）を計算するためには秘密鍵aもしくは秘密鍵bを用いなけらばならない。すなわち、秘密鍵aもしくは秘密鍵bを知らなければ、共有情報を得ることができない。このようにして得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。

本実施形態においても、スカラー倍計算部115、135は、上述の特徴を備えるので、メモリ使用量が小さく、かつ高速に計算できるような鍵交換処理が可能となる。

また、上記各実施形態における暗号化処理部、復号化処理部、署名作成部、署名検証部、鍵交換処理部は、専用のハードウェアを用いて行ってもよい。また、スカラー倍計算部をコプロセッサまたはそれ以外の専用ハードウェアで実現してもよい。

また、データ処理部は、上記暗号化処理、復号化処理、署名生成処理、署名検証処理、鍵交換処理のうち、任意の一つ以上の処理を行えるように構成してもよい。

実施形態におけるシステム構成図である。 各実施形態における情報の受け渡しを示すシーケンス図である。 第1実施例の実施形態におけるスカラー倍計算部の構成図である。 第1、第4の各実施例におけるBinaryToMOFエンコード部の行うエンコード方法を示すフローチャート図である。 第1実施例におけるMOFTo2cMOFエンコード部の行うエンコード方法を示すフローチャート図である。 第1、第2、第4、第5の各実施例における実計算部の行う計算方法を示すフローチャート図である。 第2実施例の実施形態におけるスカラー倍計算部の構成図である。 第2実施例におけるエンコード部の行うエンコード方法を示すフローチャート図である。 第3実施例の実施形態におけるスカラー倍計算部の構成図である。 第3実施例における実計算部の行う計算方法を示すフローチャート図である。 第3実施例における実計算部の行う計算方法を示すフローチャート図である。 第4実施例の実施形態におけるスカラー倍計算部の構成図である。 第4実施例におけるMOFTowcMOFエンコード部の行うエンコード方法を示すフローチャート図である。 第4、第5の各実施例における前計算部の行う事前計算テーブル生成方法を示すフローチャート図である。 第5実施例の実施形態におけるスカラー倍計算部の構成図である。 第5実施例におけるエンコード用テーブル作成部の行うエンコード用テーブル作成方法を示すフローチャート図である。 第5実施例におけるエンコード用テーブル作成部の行うエンコード用テーブル作成方法において入出力データの関連を示す図である。 第5実施例におけるBinaryTowcMOFエンコード部の行うエンコード方法を示すフローチャート図である。 第6実施例の実施形態におけるスカラー倍計算部の構成図である。 第6実施例における実計算部の行う計算方法を示すフローチャート図である。 第6実施例における実計算部の行う計算方法を示すフローチャート図である。 第7実施例の実施形態におけるスカラー倍計算部の構成図である。 第7実施例におけるMOFTowNAFエンコード部の行うエンコード方法を示すフローチャート図である。 第8実施例の実施形態におけるスカラー倍計算部の構成図である。 第8実施例におけるBinaryToNAFエンコード部の行うエンコード方法を示すフローチャート図である。 実施形態における署名検証システム構成図である。

符号の説明

101、121、2621：コンピュータ、2101：スマートカード、102、122、2602、2121：記憶部、111、131、2111、2631：処理部、115、135、2615、2635：スカラー倍計算部、112、132：データ処理部、2612：署名生成処理部、2632：署名検証処理部、104、124、2104、2624：定数、105、125、2605、2625：秘密情報、110、130、2610、2630：入出力インタフェース、108、128、2628：ディスプレイ、109、129、2629：キーボード、142：ネットワーク、141、143：データ、2641：署名、2643：チャレンジコード、302、702、1202、1502、2202、2402：エンコード部、1203、1503、1903、2203、2403：前計算部、304、704、904、1204、1504、1904、2204、2404：実計算部、305、1205、2205：BinaryToMOFエンコード部、306：MOFTo2cMOFエンコード部、1207：MOFTowcMOFエンコード部、1508：エンコード用テーブル作成部、1509：BinaryTowcMOFエンコード部、2207：MOFtowNAFエンコード部、2407：BinaryToNAFエンコード部、341、741、1241、1541、2241、2441：ビット値判定部、342、742、942、1242、1542、1942、2242、2442：加算部、343、743、943、1243、1543、1943、2243、2443：2倍算部、344、744、1244、1544、1944、2244、2444：繰り返し判定部、351、1251、2251：繰り返し判定部、352、1252、2252：変換部、361：繰り返し判定部、362：変換部、721：繰り返し判定部、722：変換部、941：変換判定部、944：繰り返し判定部、1271：繰り返し判定部、1272：変換部、1231、1531、1931、2231、2431：加算部、1232、1532、1932、2232、2432：2倍算部、1233、1533、1933、2233、2433：繰り返し判定部、1581：繰り返し判定部、1582：変換部、1591：繰り返し判定部、1592：変換部、1941：変換判定部、2271：繰り返し判定部、2272：変換部、2471：繰り返し判定部、2472：変換部

Claims (23)

1. 楕円曲線において、スカラー値と楕円曲線上の点からスカラー倍を計算する楕円曲線暗号におけるスカラー倍計算方法であって、
   前記スカラー値における連続する2ビットに対する演算を行うステップ、
   を有するスカラー倍計算方法。
2. 請求項1記載のスカラー倍計算方法であって、さらに、
   前記2ビットに対する演算は、2ビットの差分を計算する演算であるスカラー倍計算方法。
3. 請求項1記載のスカラー倍計算方法であって、さらに、
   前記2ビットに対する演算は、2ビットの値を比較する演算であるスカラー倍計算方法。
4. 請求項1記載のスカラー倍計算方法であって、さらに、
   前記2ビットに対する演算は、2ビットの排他的論理和を計算する演算であるスカラー倍計算方法。
5. 請求項1記載のスカラー倍計算方法であって、さらに、
   前記スカラー値を数値列にエンコードするステップと、
   前記エンコードした数値列及び前記楕円曲線上の点からスカラー倍を計算するステップと、を有し、
   前記エンコードするステップは、
   前記2ビットに対する演算を含むスカラー倍計算方法。
6. 請求項1記載のスカラー倍計算方法であって、さらに、
   前記スカラー値を数値列にエンコードするステップと、
   前記楕円曲線上の点から事前計算テーブルを作成するステップと、
   前記エンコードした数値列及び前記事前計算テーブルからスカラー倍を計算するステップと、を有し、
   前記エンコードするステップは、
   前記2ビットに対する演算を含むスカラー倍計算方法。
7. 請求項1記載のスカラー倍計算方法であって、さらに、
   前記楕円曲線上の点から事前計算テーブルを作成するステップと、
   前記スカラー値及び前記事前計算テーブルからスカラー倍を計算するステップと、を有し、
   前記スカラー倍を計算するステップは、
   前記2ビットに対する演算を含むスカラー倍計算方法。
8. 請求項1記載のスカラー倍計算方法であって、
   前記楕円曲線はワイエルシュトラス型楕円曲線、またはモンゴメリ型楕円曲線、または標数2の有限体上で定義された楕円曲線、またはOEF上で定義された楕円曲線であるスカラー倍計算方法。
9. 第1のデータから第2のデータを生成するデータ生成方法であって、
   請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有するデータ生成方法。
10. データから署名データを生成する署名作成方法であって、
    請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する署名作成方法。
11. データと署名データから署名データの妥当性を検証する署名検証方法であって、
    請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する署名検証方法。
12. データから暗号化されたデータを生成する暗号化方法であって、
    請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する暗号化方法。
13. 暗号化されたデータから復号化されたデータを生成する復号化方法であって、
    請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する復号化方法。
14. 楕円曲線暗号における楕円曲線において、スカラー値及び楕円曲線上の点からスカラー倍点を計算するスカラー倍計算装置であって、
    前記スカラー値における連続する2ビットに対する演算を行う変換部を有するスカラー倍計算装置。
15. 請求項14記載のスカラー倍計算装置であって、さらに、
    前記スカラー値を数値列にエンコードするエンコード部と、
    前記エンコードした数値列及び前記楕円曲線上の点からスカラー倍を計算する実計算部と、を有し、
    前記エンコード部は、前記変換部を有するスカラー倍計算装置。
16. 請求項14記載のスカラー倍計算装置であって、さらに、
    前記スカラー値を数値列にエンコードするエンコード部と、
    前記楕円曲線上の点から事前計算テーブルを作成する前計算部と、
    前記エンコードした数値列及び前記事前計算テーブルからスカラー倍を計算する実計算部と、を有し、
    前記エンコード部は、前記変換部を有するスカラー倍計算装置。
17. 請求項14記載のスカラー倍計算装置であって、さらに、
    前記楕円曲線上の点から事前計算テーブルを作成する前計算部と、
    前記スカラー値及び前記事前計算テーブルからスカラー倍を計算する実計算部と、を有し、
    前記実計算部は、前記変換部を有するスカラー倍計算装置。
18. 第1のデータから第2のデータを生成するデータ変換部と、前記データ変換部より依頼されてスカラー倍を計算するスカラー倍計算部とを有するデータ生成装置であって、
    前記スカラー倍計算部は、請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有するデータ生成装置。
19. データから署名データを生成する署名作成処理部と、前記署名生成処理部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する署名生成装置であって、
    前記スカラー倍計算部は、請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する署名生成装置。
20. データと署名データから署名データの妥当性を検証する署名検証処理部と、前記署名検証処理部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する署名検証装置であって、
    前記スカラー倍計算部は、請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する署名検証装置。
21. データから暗号化されたデータを生成する暗号部と、前記暗号部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する暗号化装置であって、
    前記スカラー倍計算部は、請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する暗号化装置。
22. 暗号化されたデータから復号化されたデータを生成する復号部と、前記復号部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する復号化装置であって、
    前記スカラー倍計算部は、請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する復号化装置。
23. 請求項1に記載のスカラー倍計算方法を計算機に実行させるプログラム。
    

Images