(57)【要約】【課題】  楕円曲線暗号において最も計算リソースを必要とする楕円曲線スカラー倍計算に関して、メモリ使用量が小さく、かつ高速に計算できる楕円曲線スカラー倍計算方法を提供すること。【解決手段】  スカラー値及び楕円曲線上の点からスカラー倍点を計算するスカラー倍計算方法において、スカラー値の変換処理を、スカラー値における連続する2ビットに対する演算を行うことにより、left-to-rightで実行し、それにより、高速計算および小メモリで計算可能となる。【選択図】図１
2005316038.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線において、スカラー値と楕円曲線上の点からスカラー倍を計算する楕円曲線暗号におけるスカラー倍計算方法であって、
前記スカラー値における連続する2ビットに対する演算を行うステップ、
を有するスカラー倍計算方法。
【請求項２】
請求項1記載のスカラー倍計算方法であって、さらに、
前記2ビットに対する演算は、2ビットの差分を計算する演算であるスカラー倍計算方法。
【請求項３】
請求項1記載のスカラー倍計算方法であって、さらに、
前記2ビットに対する演算は、2ビットの値を比較する演算であるスカラー倍計算方法。
【請求項４】
請求項1記載のスカラー倍計算方法であって、さらに、
前記2ビットに対する演算は、2ビットの排他的論理和を計算する演算であるスカラー倍計算方法。
【請求項５】
請求項1記載のスカラー倍計算方法であって、さらに、
前記スカラー値を数値列にエンコードするステップと、
前記エンコードした数値列及び前記楕円曲線上の点からスカラー倍を計算するステップと、を有し、
前記エンコードするステップは、
前記2ビットに対する演算を含むスカラー倍計算方法。
【請求項６】
請求項1記載のスカラー倍計算方法であって、さらに、
前記スカラー値を数値列にエンコードするステップと、
前記楕円曲線上の点から事前計算テーブルを作成するステップと、
前記エンコードした数値列及び前記事前計算テーブルからスカラー倍を計算するステップと、を有し、
前記エンコードするステップは、
前記2ビットに対する演算を含むスカラー倍計算方法。
【請求項７】
請求項1記載のスカラー倍計算方法であって、さらに、
前記楕円曲線上の点から事前計算テーブルを作成するステップと、
前記スカラー値及び前記事前計算テーブルからスカラー倍を計算するステップと、を有し、
前記スカラー倍を計算するステップは、
前記2ビットに対する演算を含むスカラー倍計算方法。
【請求項８】
請求項1記載のスカラー倍計算方法であって、
前記楕円曲線はワイエルシュトラス型楕円曲線、またはモンゴメリ型楕円曲線、または標数2の有限体上で定義された楕円曲線、またはOEF上で定義された楕円曲線であるスカラー倍計算方法。
【請求項９】
第1のデータから第2のデータを生成するデータ生成方法であって、
請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有するデータ生成方法。
【請求項１０】
データから署名データを生成する署名作成方法であって、
請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する署名作成方法。
【請求項１１】
データと署名データから署名データの妥当性を検証する署名検証方法であって、
請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する署名検証方法。
【請求項１２】
データから暗号化されたデータを生成する暗号化方法であって、
請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する暗号化方法。
【請求項１３】
暗号化されたデータから復号化されたデータを生成する復号化方法であって、
請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する復号化方法。
【請求項１４】
楕円曲線暗号における楕円曲線において、スカラー値及び楕円曲線上の点からスカラー倍点を計算するスカラー倍計算装置であって、
前記スカラー値における連続する2ビットに対する演算を行う変換部を有するスカラー倍計算装置。
【請求項１５】
請求項14記載のスカラー倍計算装置であって、さらに、
前記スカラー値を数値列にエンコードするエンコード部と、
前記エンコードした数値列及び前記楕円曲線上の点からスカラー倍を計算する実計算部と、を有し、
前記エンコード部は、前記変換部を有するスカラー倍計算装置。
【請求項１６】
請求項14記載のスカラー倍計算装置であって、さらに、
前記スカラー値を数値列にエンコードするエンコード部と、
前記楕円曲線上の点から事前計算テーブルを作成する前計算部と、
前記エンコードした数値列及び前記事前計算テーブルからスカラー倍を計算する実計算部と、を有し、
前記エンコード部は、前記変換部を有するスカラー倍計算装置。
【請求項１７】
請求項14記載のスカラー倍計算装置であって、さらに、
前記楕円曲線上の点から事前計算テーブルを作成する前計算部と、
前記スカラー値及び前記事前計算テーブルからスカラー倍を計算する実計算部と、を有し、
前記実計算部は、前記変換部を有するスカラー倍計算装置。
【請求項１８】
第1のデータから第2のデータを生成するデータ変換部と、前記データ変換部より依頼されてスカラー倍を計算するスカラー倍計算部とを有するデータ生成装置であって、
前記スカラー倍計算部は、請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有するデータ生成装置。
【請求項１９】
データから署名データを生成する署名作成処理部と、前記署名生成処理部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する署名生成装置であって、
前記スカラー倍計算部は、請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する署名生成装置。
【請求項２０】
データと署名データから署名データの妥当性を検証する署名検証処理部と、前記署名検証処理部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する署名検証装置であって、
前記スカラー倍計算部は、請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する署名検証装置。
【請求項２１】
データから暗号化されたデータを生成する暗号部と、前記暗号部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する暗号化装置であって、
前記スカラー倍計算部は、請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する暗号化装置。
【請求項２２】
暗号化されたデータから復号化されたデータを生成する復号部と、前記復号部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する復号化装置であって、
前記スカラー倍計算部は、請求項1に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する復号化装置。
【請求項２３】
請求項1に記載のスカラー倍計算方法を計算機に実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はセキュリティ技術に係り、特に楕円曲線演算を用いたメッセージ処理方法に関する。
【背景技術】
【０００２】
楕円曲線暗号はN.Koblitz, V.S. Millerにより提案された公開鍵暗号の一種である。公開鍵暗号には、公開鍵と呼ばれる一般に公開してよい情報と、秘密鍵(Private Key)と呼ばれる秘匿しなければならない秘密情報がある。与えられたメッセージの暗号化や署名の検証には公開鍵を用い、与えられたメッセージの復号化や署名の作成には秘密鍵を用いる。
【０００３】
楕円曲線暗号における秘密鍵は、スカラー値が担っている。また、楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Pとそのスカラー倍の点dPが与えられた時、スカラー値dを求める問題である。
【０００４】
楕円曲線上の点とは、楕円曲線の定義方程式をみたす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（加算ともいう）が定義される。そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の２倍算という。
【０００５】
楕円曲線上の２点の加法は次のようにして計算される。２点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とｘ軸に関して対称な点を、加法を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点(x1,y1)と点(x2,y2)の加算(x3,y3)=(x1,y1)+(x2,y2)は
x3=((y2-y1)/(x2-x1))2-x1-x2              （式1）
y3=((y2-y1)/(x2-x1))(x1-x3)-y1          （式2）
を計算することにより得られる。ここで、ワイエルシュトラス型楕円曲線の定義式は
y2=x3+ax+b                                （式3）
で与えられる。すなわち式３のx,yに各々xi,yi (i=1,2,3) を代入した場合に、式３の等式が成り立つ。
【０００６】
楕円曲線上の点の２倍算は次のようにして計算される。楕円曲線上の点における接線を引くと、その接線は楕円曲線上の他の点において交わる。その交わった点とｘ座標に関して対称な点を、２倍算を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点(x1,y1)の２倍算(x3,y3)=2(x1,y1)=(x1,y1)+(x1,y1)は
x3=((3x1 2+a)/(2y1))2-2x1                （式4）
y3=((3x1 2+a)/(2y1))(x1-x3)-y1          （式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でメッセージの暗号化を行なうには、Pm+k(aQ)及びkQを計算して出力し、コンピュータＢ121で暗号文の復号化を行なうには、秘密鍵a及びkQより-a(kQ)を計算し、
(Pm+k(aQ))-a(kQ)                        （式6）
を計算して出力すればよい。ここでPmはメッセージ、kは乱数、aは秘密鍵を示す定数、Qは定点、aQは公開鍵を示す点である。
【００２６】
ネットワーク142には、Pm+k(aQ), kQのみ送信され、メッセージPmを復元するためには、kaQ、すなわちkQのa倍を計算する必要がある。ところが、秘密鍵aはネットワーク142には送信されないため、秘密鍵aを保持しているものだけが、Pmを復元できることになる。
【００２７】
図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座標(x1)にもつ楕円曲線上の点Pmのy座標(y1)の値を計算する。
【００４０】
例えば、ワイエルシュトラス型楕円曲線は、A,Bを定数とするとき、
y1 2=x1 3 +Ax1+B                                （式7）
で表されるので、これよりy座標の値を求めることができる。
【００４１】
次に、暗号化処理部112は、乱数kを生成する。そして記憶部102に格納されている定数104から読み出した（図2の205）公開鍵aQとQのx座標と、求めたy座標の値と乱数kとをスカラー倍計算部115へ送る（図2の206）。
【００４２】
スカラー倍計算部115は、Qのx座標、y座標の値、乱数kによるスカラー倍点（xd1,yd1）=kQと、公開鍵aQのx座標、y座標の値、乱数によるスカラー倍点(xd2,yd2)=k(aQ)とを計算し、計算されたスカラー倍点を暗号化処理部112へ送る（図2の207）。
【００４３】
暗号化処理部112は、送られたスカラー倍点を用いて、暗号化処理を行なう。例えば、ワイエルシュトラス型楕円曲線については、Pm+k(aQ)とkQを計算する。すなわち、
xe1=((yd1-y1)/(xd1-x1))2-x1-xd1                （式8）
xe2=xd2                                        （式9）
を計算し、暗号化されたメッセージxe1,xe2を得る。
【００４４】
コンピュータＡ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座標の値を計算する。
【００５０】
暗号化されたメッセージがxe1,xe2のビット列であり、ワイエルシュトラス型楕円曲線の場合、y座標の値(ye1)は
ye1 2=xe1 3+Axe1+B                        （式10）
（ただし、A,Bはそれぞれ定数である）
から得ることができる。
【００５１】
復号化処理部132は、記憶部122（図2の102）に格納されている秘密情報125から読み出した（図2の205）秘密鍵aと、x座標、y座標の値（xe2,ye2）を、スカラー倍計算部135（図2の115）へ送る（図2の206）。
【００５２】
スカラー倍計算部135は、x座標、y座標の値、秘密情報a125からスカラー倍点(xd3,yd3)=a(xe2,ye2)を計算する。スカラー倍計算部135は、計算されたスカラー倍点を復号化処理部132へ送る（図2の207）。復号化処理部132は、送られたスカラー倍点を用いて、復号化処理を行う。
【００５３】
例えば、暗号化されたメッセージが、xe1,xe2のビット列であり、ワイエルシュトラス型楕円曲線の場合は、
(Pm+k(aQ))-a(kQ)=(xe1,ye1)-(xd3,yd3)                （式11）
を計算することにより達成する。すなわち、
xf1=((ye1+yd3)/(xe1-xd3))2-xe1-xd3                （式12）
を計算し、暗号化される前の部分メッセージx1に相当するxf1を得る。
【００５４】
コンピュータＢ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を数値列dw[j]にエンコードする。すなわち、
d=dw[n]2n+dw[n-1]2n-1+…+dw[j]2j+… +dw[0]         (式13)
-2w-1≦dw[j]≦2w-1, dw[j]=0 or 奇数                (式14)
をみたすdw[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をエンコードされた数値列dw[j]として出力する。すなわち、各jに対して、dw[j] = cmdjである。ただし、cmdjはcmdのjビット目の値とする。
【００６４】
次に図4を用いて、BinaryToMOF エンコード部305の行う処理について詳細に説明する。この処理は2d-dという変換を念頭において構成されている。ただし、この引き算はビットごとの引き算であり、負の値（-1）も取りうる。また、符号付バイナリ列mdにおいて、jビット目の値をmdj と表記する。
【００６５】
変換部352はmdn にdn-1 を代入する(401)。
【００６６】
変数iに初期値n-1を代入する（402）。
【００６７】
変換部352は、di-1  di を計算し、mdi に代入する(403)。
【００６８】
繰り返し判定部351は、i>1かどうかを判定する。i>1の場合はステップ411へ行く。i<=1の場合はステップ421へ行く(404)。
【００６９】
ステップ404でi>1の場合、
変数iを1減少させ、ステップ403へ戻る(411)。
【００７０】
ステップ404でi<=1の場合、
変換部352はmd0 にd0 を代入する(421)。
【００７１】
mdn, ..., md0 を変換された符号付バイナリ列mdとして出力する(422)。
【００７２】
なお、BinaryToMOFエンコード部305が出力するmdi は0,1,-1のいずれかの値のみを取りうる。なぜならば、mdi にはdiもしくはdi-1 -diのみが割当てられ、diはあり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ビット目の値をcmdj と表記する。
【００７５】
変数iをnで初期化する(501)。
【００７６】
変換部362は、(mdi, mdi-1)の値に応じて処理を振分ける。(mdi, mdi-1)=(1,-1)の場合はステップ511へ行く。(mdi, mdi-1)=(-1,1)の場合はステップ512へ行く。(mdi, mdi-1)がそれ以外の値の場合はステップ503へ行く(502)。
【００７７】
ステップ502で(mdi, mdi-1)=(1,-1)の場合、
変換部362はcmdiに0、cmdi-1に1を代入し、ステップ513へ行く(511)。
【００７８】
ステップ502で(mdi, mdi-1)=(-1,1)の場合、
変換部362はcmdiに0、cmdi-1に-1を代入し、ステップ513へ行く(512)。
【００７９】
変数iを2減少させ、ステップ505へ行く(513)。
【００８０】
ステップ502で(mdi, mdi-1)が(1,-1), (-1,1)以外の値の場合、
変換部362はcmdiにmdi を代入し、ステップ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はcmd0にmd0を代入し、ステップ508へ行く(507)。
【００８５】
cmdn, ..., cmd0 を変換された符号付バイナリ列cmdとして出力する(508)。
【００８６】
なお、MOFTo2cMOFエンコード部306が出力するcmdi は0,1,-1のいずれかの値のみを取りうる。なぜならば、cmdi には0,1,-1もしくはmdiのみが割当てられ、mdiはBinaryToMOFエンコード部305の出力であり0,1,-1のみ取りうるからである。
【００８７】
結果として、エンコード部302が出力するdw[j]は、0,1,-1のいずれかの値のみを取りうる。
【００８８】
本明細書では、この符号付バイナリ表現cmdを2cMOF表現と呼ぶ。
【００８９】
最後に、図6を用いて、実計算部304がエンコードされたスカラー値と楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
【００９０】
変数cに初期値nを代入する(601)。
【００９１】
dw[c]が0か0でないかを判定する。
【００９２】
dw[c]が0の場合はステップ603へ行く。0でなければステップ611へ行く(602)。
【００９３】
変数cを1減少させ、ステップ602へ戻る(603)。
【００９４】
ステップ602でdw[c]が0でない場合、点Qにdw[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は、dw[j]が0か0でないかを判定する。dw[j]が0の場合はステップ617へ行く。0でなければステップ616へ行く(615)。
【００９９】
ステップ615でdw[j]が0でない場合、
加算部342は、点Qとdw[j]PとをECADDにより加算する。ただし、dw[j]が負の場合は、(-dw[j])Pのy座標を反転したものを用いて加算を行う。その結果を点Qに格納し、ステップ617へ行く(616)。
なお、dw[j]が0でない場合は、dw[j]は1もしくは-1であり、dw[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が
(dw[c]2c-(j+1)+dw[c-1]2(c-1)-(j+1)+…+ dw[j+1]2(j+1)-(j+1))P            (式15)
と表されるとする。このとき、次にステップ613に来る時も点Qは式15をみたすことを示す。
【０１０６】
点Qはステップ614で2倍され、dw[j]が0でなければステップ616でdw[j]Pが加えられる。そのためステップ616の直後では、点Qの値は
(dw[c]2c-j+dw[c-1]2(c-1)-j+…+dw[j+1]2(j+1)-j+ dw[j]2j-j)P              (式16)
となる。したがってdw[j]=0の時も含めて、ステップ617の直前で、点Qは式16をみたす。ステップ617でjが1減少するので、式16のjにj+1を代入すると式15になる。すなわち、次にステップ613に来る時も点Qは式15をみたす。
【０１０７】
j>cに対するdw[j]の値は0であるので、ステップ621で出力される点Qの値は
(dw[n]2n+dw[n-1]2n-1+…+dw[0])P                                (式17)
に等しい。実計算部304に入力されるスカラー値は、エンコード部302によりエンコードされたdw[j]であるので、そのdw[j]は式13をみたす。したがって、Q=dPである。
【０１０８】
BinaryToMOFエンコード部305が出力する符号付バイナリ列mdは、
d = mdn2n+mdn-12n-1+…+ md0                                (式18)
をみたす。この理由は次の通りである。
ステップ401でmdnにdn-1が、ステップ403でmdiにdi-1-diが、ステップ421でmd0にd0が格納される。したがって、
mdn2n+mdn-12n-1+…+ md0 
= dn-12n +(dn-2dn-1)2n-1 +(dn-3dn-2)2n-2 +...+ (d0-d1)2 +d0
= dn-12n-1 +dn-22n-2 +...+ d12 +d0
= d                                                        （式19）
が成り立つ。
【０１０９】
MOFTo2cMOFエンコード部306が出力する符号付バイナリ列cmdは、
d = cmdn2n+cmdn-12n-1+…+ cmd0                                (式20)
をみたす。この理由は次の通りである。
ステップ502で(mdi, mdi-1)=(1,-1), (-1,1)の場合、ステップ511、ステップ512の変換により定まるcmdi, cmdi-1 とmdi, mdi-1の間には
cmdi2i +cmdi-12i-1 = mdi2i +mdi-12i-1                         （式21）
の関係が成り立つ。またステップ502で(mdi, mdi-1)=(1,-1), (-1,1)以外の場合、ステップ503の変換により定まるcmdi, とmdi, の間には
cmdi2i = mdi2i                                                 （式22）
の関係が成り立つ。ステップ507でcmd0にmd0が代入される。したがって、
cmdn2n+cmdn-12n-1+…+ cmd0 = mdn2n+mdn-12n-1+…+ md0        （式23）
が成り立つ。mdはBinaryToMOFエンコード部の305の出力であるため、式13をみたす。したがって、式18が成り立つ。
【０１１０】
結果として、エンコード部302が出力する数値列dw[j]は、式13をみたす。
【０１１１】
BinaryToMOFエンコード部305の行う処理はleft-to-rightである。なぜならば、ステップ401においてdn-1の値を用いてmdnの値を割当て、その後ステップ403において、順次iが大きい方からdi, di-1 を用いてmdi の値を決定し、最後にステップ421においてd0を用いてmd0の値を割当てるからである。
【０１１２】
なお、第1実施例ではBinaryToMOFエンコード部305の処理をleft-to-rightで行う場合を説明したが、right-to-leftでの処理や並列処理も可能である。なぜならば、各mdi はdi, di-1 から定まり、他のmdjの結果を用いないからである。そのため、right-to-left で処理を行う場合はiが小さい値から順次定めることにより、また並列で行う場合は対象とするmdi の計算を同時に行うことにより、計算することが可能である。
【０１１３】
MOFTo2cMOFエンコード部306の行う処理はleft-to-rightである。なぜならば、ステップ511、ステップ512、ステップ503において、順次iが大きい方からmdi, mdi-1 を用いてcmdi, cmdi-1 の値を決定し、最後にステップ507においてmd0を用いてcmd0 の値を割当てるからである。
【０１１４】
結果として、エンコード部302の行う処理はleft-to-rightである。
【０１１５】
BinaryToMOFエンコード部305の出力するmdは、その出現ビットの値の推移確率をして、以下のような推移確率を持つ。
0→0：1/2、 0→非零：1/2、 非零→0：1/2、 非零→非零：1/2        （式24）
すなわち、0と非零とは独立である。この理由は次の通りである。各mdi は、di-1 di より定まり、他のmdj には依存しない。di-1, di の値として0,1の各々二通りの場合を考えることにより、0と非零の値が各々1/2の確率となることが分かる。したがって、上記の推移確率を取ることが分かる。
【０１１６】
次に、MOFTo2cMOFエンコード部306が出力するcmdは、非零濃度が1/3となる。ここで非零濃度とは、(非零ビットの個数)/(ビット長) の漸近的な値を指す。この理由は次の通りである。
ステップ502-ステップ505の変換は、mdi, mdi-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をみたす数値列dw[j]にエンコードする。実計算部704は、エンコードされたスカラー値と入力された点Pを用いてスカラー倍点dPを計算する。第2実施例では特にw=2の場合について説明する。
【０１２３】
次にエンコード部702、実計算部704の行う各処理について詳細に説明する。
【０１２４】
まず、エンコード部702の行う処理について説明する。
【０１２５】
エンコード部702にバイナリ列dが入力されると、符号付バイナリ列cmdに変換する。エンコード部702は、この符号付バイナリ列cmdをエンコードされた数値列dw[j]として出力する。すなわち、各jに対して、dw[j] = cmdjである。ただし、cmdjはcmdのjビット目の値とする。
【０１２６】
次に実計算部704の行う処理について説明する。実計算部704の行う処理は、第1実施例の実計算部304の行う処理と同様の処理を行う。
【０１２７】
次に図8を用いて、エンコード部702の行う処理について詳細に説明する。
【０１２８】
変数iに初期値c+1を代入する。ただし、cはdの非零ビットのインデックスで最大のものとする。すなわち、dc!=0かつi>cに対してdi=0(801)。
【０１２９】
変換部722は、d-1に0を代入し、cmdn, ..., cmdc+1 に0を代入する(802)。
【０１３０】
繰り返し判定部721は、i>=1かどうかを判定する。i>=1の場合はステップ811へ行く。i<1の場合はステップ821へ行く(803)。
【０１３１】
ステップ803でi>=1の場合、
di-1 = di かどうかを判定する。di-1 = di の場合はステップ812へ行く。di-1 != di の場合はステップ813へ行く(811)。
【０１３２】
ステップ811でdi-1 = di の場合、
変換部722はcmdi に0を代入し、変数iを1減少させ、ステップ803へ戻る(812)。
【０１３３】
ステップ811でdi-1 != di の場合、
変換部722はcmdi に -di +di-2 を、cmdi-1 に di-2 +di-1 を代入し、変数iを2減少させ、ステップ803へ戻る(813)。
【０１３４】
ステップ803でi<1の場合、
i=0 かどうかを判定する。i=0 の場合はステップ822へ行く。i != 0の場合はステップ823へ行く(821)。
【０１３５】
ステップ821でi=0の場合、
変換部722はcmd0 に d0を代入し、ステップ823へ行く(822)。
【０１３６】
cmdn, ..., cmd0 を変換された符号付バイナリ列cmdとして出力する(823)。
【０１３７】
なお、エンコード部702が出力するdw[j]は、0,1,-1のいずれかの値のみを取りうる。なぜならば、スカラー値dの各ビットdi は0,1いずれかの値のみを取り、cmdj は0, -di もしくは、2つのdi の差分のいずれかが代入されるからである。
【０１３８】
エンコード部702が出力する符号付バイナリ列cmdは、
d = cmdn2n+cmdn-12n-1+…+ cmd0                                (式27)
をみたす。この理由は次の通りである。
ステップ803-ステップ813におけるループでは、di2i+1がキャリーとしてループでの不変量となる。まずステップ811の分岐処理によりステップ812へ行った場合を考える。ステップ812ではcmdiに0が代入される。
cmdi2i +di2i+1 = di2i +di2i
= di2i +di-12i                                                （式28）
したがって、diに対する項はdi2iとなり、キャリーdi-12iとなる。次にステップ811の分岐処理によりステップ813へ行った場合を考える。
cmdi2i +cmdi2i-1 +di2i+1 = (-di+di-2)2i +(di-2+di-1)2i-1 +di2i+1
= di2i +di-12i-1 +di-22i-1                                        （式29）
したがって、di, di-1に対する項はそれぞれdi2i, di-12i-1となり、キャリーdi-22i-1となる。したがって、di2i+1がキャリーとしてループでの不変量となることが分かった。最初にステップ803に来る時のiの値はi=c+1であり、
dc+12c+2 = 0                                                （式30）
であるのでキャリーは0となる。他方、ループを抜けたあとの処理では、キャリーの値はd02もしくはd-11となる。i=0の場合はステップ822の処理を行うため、いずれの場合もキャリーがキャンセルされる。以上をまとめると、
cmdn2n+cmdn-12n-1+…+ cmd0 = dn2n+dn-12n-1+…+ d0 =  d        （式31）
となる。
【０１３９】
エンコード部702の行う処理はleft-to-rightである。なぜならば、ステップ802においてcmdn,..., cmdc+2の値をクリアし、その後ステップ812, ステップ813において、順次iが大きい方からdi, di-1, di-2を用いてcmdi, cmdi-1の値を決定し、最後にステップ821においてd0を用いてcmd0の値を割当てるからである。
【０１４０】
エンコード部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の非零ビットのインデックスで最大のものとする。すなわち、dc!=0かつi>cに対してdi=0 (1001)。
【０１４９】
変換判定部941は、di-2=1かどうかを判定する。di-2=1の場合、ステップ1003へ行く。di-2!=1の場合、ステップ1004へ行く(1002)。
【０１５０】
ステップ1002でdi-2=1の場合、
2倍算部943は、点PをECDBLにより2倍し、点Qに格納し、ステップ1005へ行く(1003)。
【０１５１】
ステップ1002でdi-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かどうかを判定する。di-1=diの場合、ステップ1121へ行く。di-1!=diの場合、ステップ1112へ行く(1111)。
【０１５５】
ステップ1111でdi-1=diの場合、
2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する(1121)。
【０１５６】
変数iを1減少させ、ステップ1006へと戻る(1122)。
【０１５７】
ステップ1111でdi-1!=diの場合、
2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する(1112)。
【０１５８】
変換判定部941は、(di,di-2)の値に応じて処理を振分ける。(di,di-2)=(1,1)の場合、ステップ1114へ行く。(di,di-2)=(1,0)の場合、ステップ1115へ行く。(di,di-2)=(0,1)の場合、ステップ1116へ行く。(di,di-2)=(0,0)の場合、ステップ1117へ行く(1113)。
【０１５９】
ステップ1113で(di,di-2)=(1,1)の場合、
2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する。その後、加算部942は、点Qと点-PとをECADDにより加算し、点Qに格納する。その後、ステップ1118へ行く(1114)。
【０１６０】
ステップ1113で(di,di-2)=(1,0)の場合、
加算部942は、点Qと点-PとをECADDにより加算し、点Qに格納する。その後、2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する。その後、ステップ1118へ行く(1115)。
【０１６１】
ステップ1113で(di,di-2)=(0,1)の場合、
加算部942は、点Qと点PとをECADDにより加算し、点Qに格納する。その後、2倍算部943は、点QをECDBLにより2倍し、点Qに再び格納する。その後、ステップ1118へ行く(1116)。
【０１６２】
ステップ1113で(di,di-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の処理について考える。この場合、di=di-1が成り立っている。(di, di-2)=(1,1)の場合、ステップ1112、ステップ1114の処理により、実行される演算はcmdi=0, cmdi-1=-1が第2実施例の実計算部704に入力された時と同じとなる。また、第2実施例のエンコード部702は、入力が(di, di-1, di-2)=(1,1,1)の時、ステップ813の処理により (cmdi, cmdi-1) = (0,-1)を出力する。したがって、この場合の処理は、第3実施例と第2実施例で同じとなる。同様に、ステップ1112、ステップ1115の処理は、(cmdi, cmdi-1) = (-1,0)、ステップ1112、ステップ1116の処理は、(cmdi, cmdi-1) = (1,0)、ステップ1112、ステップ1117の処理は、(cmdi, cmdi-1) = (0,1)に、それぞれ相当し、ステップ813の処理と一致する。また同様に、di, != di-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をみたす数値列dw[j]にエンコードする。前計算部1203は、入力された楕円曲線上の点Pから事前計算テーブルを作成する。事前計算テーブルはP, 3P, …, (2w-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の各数値cmdiの取りうる値は、
-2w-1≦cmdi≦2w-1, cmdi=0 or 奇数                        (式32)
である。
【０１８１】
エンコード部1202は、MOFTowcMOFエンコード部1207が変換した数値列cmdをエンコードされた数値列dw[j]として出力する。すなわち、各jに対して、dw[j] = cmdjである。ただし、cmdjはcmdのjビット目の値とする。
【０１８２】
次に、BinaryToMOFエンコード部1205の行う処理について説明する。BinaryToMOFエンコード部1205の行う処理は、第1実施例のBinaryToMOFエンコード部305の行う処理と同様の処理を行う。
【０１８３】
次に、図13を用いて、MOFTowcMOFエンコード部1207の行う処理について説明する。
【０１８４】
変数iをnで初期化する(1301)。
【０１８５】
変換部1272は、mdi =0かどうかを判定する。mdi =0 の場合、ステップ1303へ行く。mdi !=0の場合、ステップ1311へ行く(1302)。
【０１８６】
ステップ1302でmdi =0 の場合、
変換部1272は、cmdi にmdi を代入する(1303)。
【０１８７】
変数iを1減少させ、ステップ1305へ行く(1304)。
【０１８８】
ステップ1302でmdi !=0 の場合、
変換部1272は、i >= j >= i-(w-1) の範囲のjで、mdj !=0をみたすもののうち、最小のものをjとする(1311)。
【０１８９】
変換部1272は、cmdi, ..., cmdi-j+1 に0を、cmdi-j に
mdi 2j +mdi-1 2j-1 +... +mdi-j                                （式33）
を、cmdi-j-1, ..., cmdi-(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で、mdj !=0をみたすもののうち、最小のものをjとする(1307)。
【０１９４】
変換部1272は、cmdi, ..., cmdi-j+1 に0を、cmdi-j に
mdi 2j +mdi-1 2j-1 +... +mdi-j                                （式34）
を、cmdi-j-1, ..., cmd0 に0を、それぞれ代入する(1308)。
【０１９５】
cmdn, ..., cmd0 を変換された数値列cmdとして出力する(1309)。
【０１９６】
本明細書では、この数値列cmdをwcMOF表現と呼ぶ。
【０１９７】
次に、図14を用いて、前計算部1203が楕円曲線上の点から、事前計算テーブルを作成する方法を説明する。
【０１９８】
2倍算部1232は、点PをECDBLにより2倍し、その結果を点2Pに格納する(1401)。
【０１９９】
変数jに初期値1を代入する(1402)。
【０２００】
繰り返し判定部1233は、jが2w-1より小さいかどうかを判定する。jが2w-1より小さい場合はステップ1204へ行く。2w-1以上の場合はステップ1411へ行く(1403)。
【０２０１】
ステップ1403でjが2w-1より小さい場合、
加算部1231は、点2Pと点(2j-1)PをECADDにより加算し、その結果を点(2j+1)Pに格納する(1404)。
【０２０２】
変数jを1増加させ、ステップ1403へ戻る(1405)。
【０２０３】
ステップ1403でjが2w-1以上の場合、
P, 3P, …, (2w-1-1)Pを事前計算テーブルとして出力する(1411)。
【０２０４】
また、楕円曲線上の点Q=(x,y)に対して、楕円曲線加算に関する逆元の点-Qは、-Q=(x,-y)と表されるため、点Qの座標が与えられていれば容易に計算できる。そのため、点P, 3P, …, (2w-1-1)Pのみを事前計算テーブルとして格納する。その後の実計算部1204が行う計算で必要となる点-P, -3P, …, -(2w-1-1)Pは、それらから導出すればよく、事前計算テーブルには格納する必要はない。
【０２０５】
なお、前計算部1203の行う事前計算テーブルの作成処理は、点P, 3P, …, (2w-1-1)Pが計算されればよい。そのため、非特許文献5の481ページに記載されているモンゴメリトリックを用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化をはかってもよい。
【０２０６】
最後に、図6を用いて、実計算部1204がエンコードされたスカラー値と楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
【０２０７】
変数cに初期値nを代入する(601)。
【０２０８】
dw[c]が0か0でないかを判定する。
【０２０９】
dw[c]が0の場合はステップ603へ行く。0でなければステップ611へ行く(602)。
【０２１０】
変数cを1減少させ、ステップ602へ戻る(603)。
【０２１１】
ステップ602でdw[c]が0でない場合、点Qにdw[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は、dw[j]が0か0でないかを判定する。dw[j]が0の場合はステップ617へ行く。0でなければステップ616へ行く(615)。
【０２１６】
ステップ615でdw[j]が0でない場合、
加算部1242は、点Qとdw[j]PとをECADDにより加算する。ただし、dw[j]が負の場合は(-dw[j])Pのy座標を反転したものを用いて加算を行う。その結果を点Qに格納し、ステップ617へ行く(616)。
なお、dw[j]が0でない場合は、dw[j]はエンコード部1202の出力であるので、1,3,..., 2w-1-1のいずれかの値である。そのため、dw[j]Pもしくは(-dw[j])Pのいずれかが、事前計算テーブルに必ず存在する。
【０２１７】
変数jを1減少させ、ステップ613へと戻る(617)。
【０２１８】
ステップ613でjが0より小さい場合、
点Qを出力する(621)。
【０２１９】
第1実施例で説明した通り、BinaryToMOFエンコード部1205が出力する符号付バイナリ列mdは、式18をみたす。また、mdi は0,1,-1のいずれかの値のみを取りうる。
【０２２０】
MOFTowcMOFエンコード部1207が出力する数値列cmdは、
d = cmdn2n+cmdn-12n-1+…+ cmd0                                        (式35)
をみたす。この理由は次の通りである。
ステップ1312で変換されるcmdi, ..., cmdi-(w-1) は、
cmdi2w-1+cmdi-12w-2+…+ cmdi-(w-1) = mdi2w-1+mdi-12w-2+…+ mdi-(w-1)      (式36)
をみたす。また、ステップ1308で変換されるcmdi, ..., cmdi-(w-1) も
cmdi2w-1+cmdi-12w-2+…+ cmd0 = mdi2w-1+mdi-12w-2+…+ md0                (式37)
をみたす。そのため、
cmdn2n+cmdn-12n-1+…+ cmd0 = mdn2n+mdn-12n-1+…+ md0                (式38)
が成り立つ。md はBinaryToMOFエンコード部1205の出力であるので、式18をみたす。したがって、式35が成り立つ。
【０２２１】
MOFTowcMOFエンコード部1207が出力する数値列cmdは、式32をみたす。なぜならば、ステップ1312でエンコードされるcmdi-j はmdがMOF表現であり、またjの取り方から必ず奇数となるからである。
【０２２２】
結果として、エンコード部1202が出力する数値列dw[j]は、式13、式14をみたす。
【０２２３】
そのため、第1実施例で説明した通り、実計算部1204が出力する点Qはスカラー倍点dPに等しい。
【０２２４】
第1実施例で説明した通り、BinaryToMOFエンコード部1205の行う処理はleft-to-rightである。
【０２２５】
MOFTowcMOFエンコード部1207の行う処理はleft-to-rightである。なぜならば、ステップ1312の変換では、順次iが大きい方からmdiを用いてcmdiの値を割当てるからである。
【０２２６】
結果として、エンコード部1202の行う処理はleft-to-rightである。
【０２２７】
MOFTo2cMOFエンコード部1207が出力するcmdは、非零濃度が1/(w+1)となる。この理由は次の通りである。
ステップ1302でmdi の値により処理を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をみたす数値列dw[j]にエンコードする。前計算部1503は、入力された楕円曲線上の点Pから事前計算テーブルを作成する。事前計算テーブルはP, 3P, …, (2w-1-1)Pにより構成される。実計算部1504は、エンコードされたスカラー値と事前計算テーブルを用いてスカラー倍点dPを計算する。
【０２３５】
なお、エンコード部1502の行うエンコード処理は、スカラー値dを受け取った後、および実計算部1504がスカラー倍点を計算する前であればよいことも、第4実施例と同様である。
【０２３６】
また、点Pが固定点である場合、前計算部1503の行う事前計算テーブルの作成処理は、ただ一度行えばよいことも、第4実施例と同様である。
【０２３７】
次に、エンコード部1502、前計算部1503、実計算部1504の行う各処理について詳細に説明する。
【０２３８】
まず、エンコード部1502の行う処理について説明する。
エンコード部1502は、バイナリ列dを数値列dw[j]に変換する。
【０２３９】
エンコード部1502にバイナリ列dが入力されると、エンコード用テーブル作成部1508は、エンコード用のテーブルを作成する。
【０２４０】
BinaryTowcMOFエンコード部1509は、エンコード用テーブル作成部1508が作成したエンコード用テーブルを用いて、入力されたバイナリ列dを、数値列cmdに変換する。
【０２４１】
エンコード部1502は、BinaryTowcMOFエンコード部1509が変換した数値列cmdをエンコードされた数値列dw[j]として出力する。すなわち、各jに対して、dw[j] = cmdjである。ただし、cmdjは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*2sde と、整数sdm, sdeを用いて表現することができる(1701)。このとき、整数sdm, sde は、
-2w-1≦sdm≦2w-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の要素数はともに2w個である。w+1ビットの非零バイナリ列dで上位2ビットが一致しないものに対して、sdm, sdeのj=d-2w-1 番目の要素sdm[j], sde[j]に対応するsdm, sdeを格納する。w=2の場合の対応を1703に、w=3の場合の対応を1704に示している。dはw+1ビットのバイナリ列dで上位2ビットが一致しないもの、ddecはその10進表現、ddec -2w-1 はエンコード用テーブルのインデックス、mdはdのwビットのMOF表現、mddecはその10進表現、sdmはdに対応する対応するsdm、sdeはdに対応するsde、cmdはMOF表現mdに対応するwcMOF表現を、それぞれ表す。
【０２４８】
次に、図16を用いて、エンコード用テーブル作成部1508の行う処理について説明する。
【０２４９】
変数dを2w-1で初期化する(1601)。
【０２５０】
繰り返し判定部1581は、d<=3*2w-1 かどうかを判定する。d<=3*2w-1 の場合、ステップ1603へ行く。d>3*2w-1 の場合、ステップ1621へ行く(1602)。
【０２５１】
ステップ1602でd<=3*2w-1 の場合、
変換部1582は、変数mdに(d&(2w-1))-(d>>1)を代入する(1603)。ただし、”&”はビット毎の論理積を、”>>”は右シフトを表す。これらの演算は、ほぼ全てのCPUに命令として具備されており、CPU上で効率的に実行することが可能である。
【０２５２】
変数jにd-2w-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*2w-1 の場合、
変換テーブルsde及びsdmを出力する(1621)。
【０２６０】
次に、図18を用いて、BinaryTowcMOFエンコード部1509の行う処理について説明する。
【０２６１】
変数iをnで初期化する。数値列cmdを0で初期化する。dnを0で初期化する(1801)。
【０２６２】
繰り返し判定部1591は、i>=1かどうかを判定する。i>=1の場合、ステップ1803へ行く。i<1の場合、ステップ1811へ行く(1802)。
【０２６３】
ステップ1802でi>=1の場合、
変換部1592は、di XOR di+1 =0かどうかを判定する。di XOR di+1 =0の場合、ステップ1807へ行く。di XOR di+1 !=0の場合、ステップ1804へ行く(1803)。なお、”XOR”は、排他的論理和を表す。この演算は、ほぼ全てのCPUに命令として具備されており、CPU上で効率的に実行することが可能である。
【０２６４】
ステップ1803でdi XOR di+1 =0の場合、
変数iを1減少させ、ステップ1802へ戻る(1807)。
【０２６５】
ステップ1803でdi XOR di+1 !=0の場合、
変換部1592は、変数jに、((d>>(i-w))&(2w+1-1))-2w-1 を代入する(1804)。
【０２６６】
変換部1592は、cmdi-w+1+sde[j] に sdm[j] を代入する(1805)。
【０２６７】
変数iをw減少させ、ステップ1802へ戻る(1806)。
【０２６８】
ステップ1802でi<1の場合、
i=0 & d0=0 かどうかを判定する。i=0 & d0=0の場合、ステップ1812へ行く。i!=0 | d0 !=0の場合、ステップ1813へ行く(1811)。なお、”|” は論理和を表す。
【０２６９】
ステップ1802でi=0 & d0=0の場合、
変換部1592は、cmd0 に-1を代入し、ステップ1813へ行く(1812)。
【０２７０】
cmdn, ..., cmd0 を数値列cmdとして出力する(1813)。
【０２７１】
次に、前計算部1503の行う処理について説明する。
前計算部1503の行う処理は、第4実施例の前計算部1203の行う処理と同様の処理を行う。
【０２７２】
最後に、実計算部1504の行う処理について説明する。
実計算部1504の行う処理は、第4実施例の実計算部1204の行う処理と同様の処理を行う。
【０２７３】
BinaryTowcMOFエンコード部1509が出力する数値列cmdは、
d = cmdn2n+cmdn-12n-1+…+ cmd0                                (式41)
をみたす。この理由は次の通りである。
ステップ1804、ステップ1805の処理は、該当するwビットの変換を行うものであり、図13のステップ1312の処理に相当する。そのため、式41が成り立つ。
【０２７４】
また、BinaryTowcMOFエンコード部1509が出力する数値列cmdは、第4実施例で説明したように、式32をみたす。
【０２７５】
結果として、エンコード部1502が出力する数値列dw[j]は、式13、式14をみたす。
【０２７６】
そのため、第1実施例で説明した通り、実計算部1504が出力する点Qはスカラー倍点dPに等しい。
【０２７７】
BinaryTowcMOFエンコード部1509の行う処理はleft-to-rightである。なぜならば、ステップ1804、ステップ1805の変換では、順次iが大きい方からcmdiの値を割当てるからである。
【０２７８】
結果として、エンコード部1502の行う処理はleft-to-rightである。
【０２７９】
エンコード部1502の出力する数値列dw[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, …, (2w-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は、di XOR di+1 =0かどうかを判定する。di XOR di+1 =0の場合、ステップ2012へ行く。di XOR di+1 !=0の場合、ステップ2131へ行く(2011)。
【０２９６】
ステップ2011でdi XOR di+1 =0の場合、
2倍算部1943は、点QをECDBLにより2倍し、点Qに再び格納する(2012)。
【０２９７】
変数iを1減少させ、ステップ2002に戻る(2013)。
【０２９８】
ステップ2011でdi XOR di+1 !=0の場合、
変換判定部1941は、変数jに((d>>(i-w))&(2w+1-1))-2w-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)。
【０３０９】
d0 =0かどうかを判定する。d0 =0 の場合、ステップ2024へ行く。d0 !=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をみたす数値列dw[j]にエンコードする。前計算部2203は、入力された楕円曲線上の点Pから事前計算テーブルを作成する。事前計算テーブルはP, 3P, …, (2w-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の各数値cmdiの取りうる値は、
-2w-1≦cmdi≦2w-1, cmdi=0 or 奇数                        (式42)
である。この変換はright-to-leftで行われる。
【０３２５】
エンコード部2202は、MOFTowNAFエンコード部2207が変換した数値列cmdをエンコードされた数値列dw[j]として出力する。すなわち、各jに対して、dw[j] = cmdjである。ただし、cmdjはcmdのjビット目の値とする。
【０３２６】
次に、BinaryToMOFエンコード部2205の行う処理について説明する。BinaryToMOFエンコード部2205の行う処理は、第1実施例のBinaryToMOFエンコード部305の行う処理と同様の処理を行う。
【０３２７】
次に、図23を用いて、MOFTowNAFエンコード部2207の行う処理について説明する。
【０３２８】
変数iを0で初期化する(2301)。
【０３２９】
変換部2272は、mdi =0かどうかを判定する。mdi =0 の場合、ステップ2303へ行く。mdi !=0の場合、ステップ2311へ行く(2302)。
【０３３０】
ステップ2302でmdi =0 の場合、
変換部2272は、cmdi にmdi を代入する(2303)。
【０３３１】
変数iを1増加させ、ステップ2305へ行く(2304)。
【０３３２】
ステップ2302でmdi !=0 の場合、
変換部1272は、cmdi に
mdi+w-1 2w-1 +mdi+w-2 2w-2 +... +mdi                                  （式43）
を、cmdi+1, ..., cmdi+w-1 に0を、それぞれ代入する(1311)。
【０３３３】
変数iをw増加させ、ステップ2305へ行く(2312)。
【０３３４】
繰り返し判定部2271は、i<=nかどうかを判定する。i<=nの場合、ステップ2302に戻る。i>nの場合、ステップ2321へ行く(2305)。
【０３３５】
ステップ2305でi<w-1の場合、
cmdn, ..., cmd0 を変換された数値列cmdとして出力する(2321)。
【０３３６】
本明細書では、この数値列cmdをwNAF表現と呼ぶ。
【０３３７】
次に、前計算部2203の行う処理について説明する。
前計算部2203の行う処理は、第4実施例の前計算部1203の行う処理と同様の処理を行う。
【０３３８】
最後に、実計算部2204の行う処理について説明する。
実計算部2204の行う処理は、第4実施例の実計算部1204の行う処理と同様の処理を行う。
【０３３９】
第1実施例で説明した通り、BinaryToMOFエンコード部2205が出力する符号付バイナリ列mdは、式18をみたす。また、mdi は0,1,-1のいずれかの値のみを取りうる。
【０３４０】
MOFTowNAFエンコード部2207が出力する数値列cmdは、
d = cmdn2n+cmdn-12n-1+…+ cmd0                                        (式44)
をみたす。この理由は次の通りである。
ステップ2311で変換されるcmdi, ..., cmdi+w-1 は、
cmdi2w-1+cmdi-12w-2+…+ cmdi-(w-1) = mdi2w-1+mdi-12w-2+…+ mdi-(w-1)      (式45)
をみたす。また、ステップ2303で変換されるcmdi は cmdi = mdi である。そのため、
cmdn2n+cmdn-12n-1+…+ cmd0 = mdn2n+mdn-12n-1+…+ md0                (式46)
が成り立つ。md はBinaryToMOFエンコード部2205の出力であるので、式18をみたす。したがって、式44が成り立つ。
【０３４１】
MOFTowNAFエンコード部2207が出力する数値列cmdは、式42をみたす。なぜならば、ステップ2311でエンコードされるcmdi はmdがMOF表現であり、またmdi !=0の場合にのみ ステップ2311が実行されるため、必ず奇数となるからである。
【０３４２】
結果として、エンコード部2202が出力する数値列dw[j]は、式13、式14をみたす。
【０３４３】
そのため、第1実施例で説明した通り、実計算部2204が出力する点Qはスカラー倍点dPに等しい。
【０３４４】
第1実施例で説明した通り、BinaryToMOFエンコード部2205の行う処理はleft-to-rightである。ところが、right-to-leftでも処理を行うことができる。なぜならば、各mdi はdi, di-1 からのみ定まるからである。すなわち、iが小さいものより順にmdi を定めることもできる。そのため、必要であれば、BinaryToMOFエンコード部2205の処理をright-to-left で行ってもよい。
【０３４５】
MOFTowNAFエンコード部2207の行う処理はright-to-leftである。なぜならば、ステップ2311、ステップ2303の変換では、順次iが小さい方からmdiを用いてcmdiの値を割当てるからである。
【０３４６】
結果として、エンコード部2202の行う処理はright-to-leftで行うことが可能である。
【０３４７】
MOFTowNAFエンコード部2207が出力するcmdは、非零濃度が1/(w+1)となる。この理由は次の通りである。
ステップ2302でmdi の値により処理を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をみたす数値列dw[j]にエンコードする。前計算部2403は、入力された楕円曲線上の点Pから事前計算テーブルを作成する。事前計算テーブルはP, 3P, …, (2w-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をエンコードされた数値列dw[j]として出力する。すなわち、各jに対して、dw[j] = cmdjである。ただし、cmdjはcmdのjビット目の値とする。
【０３６２】
次に、図25を用いて、BinaryToNAFエンコード部2407の行う処理について説明する。
【０３６３】
変数iをnで初期化する(2501)。
【０３６４】
dn, d-1, d-2 をそれぞれ0で初期化する(2502)。
【０３６５】
繰り返し判定部2471は、i>-1かどうかを判定する。i>-1の場合、ステップ2504へ行く。i<=-1の場合、ステップ2521へ行く(2503)。
【０３６６】
ステップ2503でi>-1の場合、
変換部2472は、bにdi-1 di を代入する(2504)。
【０３６７】
変換部2472は、b=0かどうかを判定する。b=0の場合、ステップ2506へ行く。b!=0の場合、ステップ2511へ行く(2505)。
【０３６８】
ステップ2505でb=0の場合、
変換部2472は、cmdi に0を代入する(2506)。
【０３６９】
変数iを1減少させ、ステップ2503に戻る(2507)。
【０３７０】
ステップ2505でb !=0 の場合、
変換部2472は、 di-j-1 = di-j となる最大のjを見つける(2511)。
【０３７１】
変換部2472は、jが奇数かどうかを判定する。jが奇数の場合、ステップ2514へ行く。jが偶数の場合、ステップ2513へ行く(2512)。
【０３７２】
ステップ2512でjが奇数の場合、
変換部2472は、cmdi, cmdi-1, cmdi-2, ..., cmdi-j+2, cmdi-j+1, cmdi-j に、それぞれb, 0, -b, ..., 0, -b, 0 を代入し、ステップ2515へ行く(2514)。
【０３７３】
ステップ2512でjが偶数の場合、
変換部2472は、cmdi, cmdi-1, ..., cmdi-j+2, cmdi-j+1, cmdi-j に、それぞれ0, b, ..., 0, b, 0 を代入し、ステップ2515へ行く(2513)。
【０３７４】
変数iをj+1減少させ、ステップ2503に戻る(2515)。
【０３７５】
ステップ2503でi<=-1の場合、
cmdn, ..., cmd0 を変換された数値列cmdとして出力する(2521)。
【０３７６】
なお、BinaryToNAFエンコード部2407の出力するcmdi は、0, 1, -1のいずれかの値のみを取りうる。なぜならば、bはdi-1 di で与えられ、cmdi には0, b, -b のいずれかの値のみが割当てられるからである。
【０３７７】
次に、前計算部2203の行う処理について説明する。
前計算部2203の行う処理は、第4実施例の前計算部1203の行う処理と同様の処理を行う。
【０３７８】
最後に、実計算部2204の行う処理について説明する。
実計算部2204の行う処理は、第4実施例の実計算部1204の行う処理と同様の処理を行う。
【０３７９】
BinaryToNAFエンコード部2407が出力する数値列cmdは、
d = cmdn2n+cmdn-12n-1+…+ cmd0                                        (式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が出力する数値列dw[j]は、式13、式14をみたす。
【０３８１】
そのため、第1実施例で説明した通り、実計算部2404が出力する点Qはスカラー倍点dPに等しい。
【０３８２】
BinaryToNAFエンコード部2407の行う処理はleft-to-rightである。なぜならば、ステップ2511-ステップ2514、ステップ2506の各変換では、順次iが大きい方からcmdiの値を割当てるからである。
【０３８３】
結果として、エンコード部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 | bi | ti |...| b2 | t2 | b1 | t1 | 0...0
を一つのブロックとして分割し、最上位のブロックからwNAF表現に変換することにより、一般のウィンドウ幅wに対してもエンコードを行うことが可能である。ただし、rは高々w-1ビットのMOF表現、各bj は高々w-2ビットの0値ビット（0値ビットが0個の場合も含む）、各tj はwビットのMOF表現を、それぞれ表し、ブロックの最初と最後の0値ビットは各々w-1個連続する。
【０３９０】
なお、第3実施例と同様に、エンコード処理を実計算部2404の行う処理に組み込んで行ってもよい。そうすることにより、メモリ使用量の更なる削減、更なる高速化、プログラムの更なる簡素化やハードウェア論理回路の小規模化といったメリットがある。
【０３９１】
以上、コンピュータＡ101が、入力メッセージを暗号化する場合のスカラー倍計算部115の動作を説明したが、コンピュータＢ121が暗号化されたデータ141を復号化する場合も同様である。
【０３９２】
その場合には、コンピュータＢ121のスカラー倍計算部135は、既に説明した楕円曲線上の点(xe2, ye2)、秘密情報a125によるスカラー倍点(xd3, yd3)を出力する。このとき、上記計算方法で説明したスカラー値dを秘密情報a125、楕円曲線上の点Pを楕円曲線上の点(xe2, ye2)として同様の処理を行うことにより、スカラー倍点を求めることができる。
次に、本発明を署名検証システムに適用する実施形態を、図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によるスカラー倍点(xu,yu)を計算し、計算されたスカラー倍点を署名生成処理部2612へ送る（図2の207）。
【０４０５】
署名生成部2612は、送られたスカラー倍点を用いて署名の生成を行う。例えば、非特許文献4に記載されているECDSA署名であれば、
s = xu 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）
h1 = fh mod q                                                        （式51）
h2 = sh mod q                                                        （式52）
を計算する。そして、記憶部2622（図2の102）に格納されている定数2624から読み出した（図2の205）公開鍵aQ及び定点Qと計算したh1,h2をスカラー倍計算部2635（図2の115）へ送る（図2の206）。
【０４１０】
スカラー倍計算部2635は、定点Qとh1によるスカラー倍点h1Qと、公開鍵aQとh2によるスカラー倍点h2aQとを計算し、計算されたスカラー倍点を署名検証処理部2632へ送る（図2の207）。
【０４１１】
署名検証処理部2632は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ECDSAの署名検証であれば、点R
R = h1Q+h2aQ                                                        （式53）
を計算し、そのx座標をxRとしたとき、
s' = xR mod q                                                        （式54）
を計算し、s'=sであればチャレンジコード2643に対する署名の検証結果として「有効」を出力し、スマートカード2601を認証し、受入れる（図2の208）。
【０４１２】
s'=sでなければ、「無効」を出力し、スマートカードを拒絶する（図2の208）。
【０４１３】
上記実施形態のスカラー倍計算部2615、2635は、図1のスカラー倍計算部115または135と同様の機能を備えるので、メモリ使用量が小さく、かつ高速に計算できるスカラー倍計算を実行できる。特に、式53の計算では、非特許文献1の方法を用いた場合、数十バイトの余分なRAM領域を必要としたが、本発明の方法を用いた場合、h1, h2 の値を数ビットずつ読み込むため、余分な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：変換部
【図１】
2005316038.tif 000003
【図２】
2005316038.tif 000004
【図３】
2005316038.tif 000005
【図４】
2005316038.tif 000006
【図５】
2005316038.tif 000007
【図６】
2005316038.tif 000008
【図７】
2005316038.tif 000009
【図８】
2005316038.tif 000010
【図９】
2005316038.tif 000011
【図１０】
2005316038.tif 000012
【図１１】
2005316038.tif 000013
【図１２】
2005316038.tif 000014
【図１３】
2005316038.tif 000015
【図１４】
2005316038.tif 000016
【図１５】
2005316038.tif 000017
【図１６】
2005316038.tif 000018
【図１７】
2005316038.tif 000019
【図１８】
2005316038.tif 000020
【図１９】
2005316038.tif 000021
【図２０】
2005316038.tif 000022
【図２１】
2005316038.tif 000023
【図２２】
2005316038.tif 000024
【図２３】
2005316038.tif 000025
【図２４】
2005316038.tif 000026
【図２５】
2005316038.tif 000027
【図２６】
2005316038.tif 000028