(57)【特許請求の範囲】
【請求項１】
楕円曲線暗号に用いる楕円曲線上の点と、与えられたスカラー値と、からスカラー倍点を計算するスカラー倍計算装置であって、
前記スカラー値を数値列にエンコードするエンコード部と、
前記楕円曲線上の点から前計算テーブルを作成する前計算部と、
前記エンコードした数値列と、前記前計算テーブルと、から前記スカラー倍点を計算する実計算部と、
を具備し、
前記エンコード部は、
予め定められた個数m個(m=w１2w0-2であり、w０は正整数であり、w１=w-(w０-1)であり、wは予め定められた正有理数である)の数値からなり、{2w0-1+1,2w0-1+3,…,2w0-1}からランダムに選ばれた数値を含むインデックス集合を生成するインデックス集合生成部と、
前記スカラー値から第一の数値(前記第一の数値は、前記スカラー値の2w0+1による剰余から2w0を引いた値である)と第二の数値(前記第二の数値は、前記スカラー値の2w0による剰余から2w0-1を引いた値とする)とを生成する数値取得部と、
前記第一の数値の大きさが予め定められた大きさである2w0-1より小さい場合は、予め定めた確率により前記第一の数値もしくは前記第二の数値のいずれか一方を選択し、前記第一の数値の大きさが前記予め定められた大きさである2w0-1以上の場合であり、かつ、前記インデックス集合生成部が生成した前記数値のいずれかと前記第一の数値とが一致する場合は、前記第一の数値を選択し、前記第一の数値の大きさが前記予め定められた大きさである2w0-1以上の場合であり、かつ、前記インデックス集合生成部が生成した前記数値のいずれかと前記第一の数値とが一致しない場合は、前記第二の数値を選択する数値選択部と、を有し、
前記前計算部は、前記インデックス集合を構成する前記数値を用いて、前記前計算テーブルを作成し、
前記エンコード部は、前記スカラー値を前記数値列にエンコードする際に、前記数値取得部での前記第一の数値と前記第二の数値を生成する処理と、前記数値選択部での前記第一の数値又は前記第二の数値を選択する処理と、前記スカラー値を前記数値列にエンコードするための処理とを繰り返し、
前記エンコード部は、前記選択した数値を用いて前記スカラー値を前記数値列にエンコードするための処理の際には、u[i]に前記数値選択部で前記選択された数値を代入し、{0，0，…，0，u[i]}を数値列{dw[r+ri-1],dw[r+ri-2],…,dw[r+1],dw[r]}(rは変数であり、u[i]が前記第一の数値の場合riはw0であり、u[i]が前記第二の数値の場合riはw0-1である。iは処理が繰り返される毎に1ずつ増える変数である)に代入し、
前記エンコード部は前記各処理を繰り返すことにより得られた数値列を前記実計算部に出力する
ことを特徴とするスカラー倍計算装置。
【請求項２】
請求項１記載のスカラー倍計算装置であって、
前記前計算部は、前記前計算テーブルが読み出されるたびに、再びランダム化した数値を用いた前計算テーブルを作成する
ことを特徴とするスカラー倍計算装置。
【請求項３】
請求項１記載のスカラー倍計算装置であって、
前記前計算部は、一つのスカラー倍計算中に、参照する前計算テーブルを一度以上再作成する
ことを特徴とするスカラー倍計算装置。
【請求項４】
請求項１記載のスカラー倍計算装置であって、
前記インデックス集合生成部は、前記インデックス集合を構成する前記数値の個数を、外部から設定されるウィンドウ幅に基づいて決定する
ことを特徴とするスカラー倍計算装置。
【請求項５】
請求項１記載のスカラー倍計算装置であって、
楕円曲線としてワイエルシュトラス型楕円曲線、モンゴメリ型楕円曲線、標数2の有限体上で定義された楕円曲線、OEF上で定義された楕円曲線のいずれか一つを用いる
ことを特徴とするスカラー倍計算装置。
【請求項６】
第一のデータから第二のデータを生成するデータ変換部と、前記データ変換部より依頼されてスカラー倍を計算するスカラー倍計算部とを有するデータ生成装置であって、
前記スカラー倍計算部は、請求項１に記載のスカラー倍計算装置を用いてスカラー倍を計算する
ことを特徴とするデータ生成装置。
【請求項７】
データから署名データを生成する署名部と、前記署名部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する署名作成装置であって、
前記スカラー倍計算部は、請求項１に記載のスカラー倍計算装置を用いてスカラー倍を計算する
ことを特徴とする署名作成装置。
【請求項８】
暗号化されたデータから復号化されたデータを生成する復号部と、前記復号部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する復号化装置であって、
前記スカラー倍計算部は、請求項１に記載のスカラー倍計算装置を用いてスカラー倍を計算する
ことを特徴とする復号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はセキュリティ技術に係り、特に楕円曲線演算を用いたメッセージ処理方法に関する。
【０００２】
【従来の技術】
楕円曲線暗号はN. Koblitz, V. S. Millerにより提案された公開鍵暗号の一種である。公開鍵暗号には、公開鍵と呼ばれる一般に公開してよい情報と、秘密鍵(Private Key)と呼ばれる秘匿しなければならない秘密情報がある。与えられたメッセージの暗号化や署名の検証には公開鍵を用い、与えられたメッセージの復号化や署名の作成には秘密鍵を用いる。
【０００３】
楕円曲線暗号における秘密鍵は、スカラー値が担っている。また、楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Pとそのスカラー倍の点dPが与えられた時、スカラー値dを求める問題である。
【０００４】
楕円曲線上の点とは、楕円曲線の定義方程式をみたす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（乃至は加算）が定義される。そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の２倍算という。
【０００５】
楕円曲線上の2点の加法は次のようにして計算される。2点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とx軸に関して対称な点を、加法を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点(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)
で与えられる。すなわち、式3のx,yに各々xi,yi (i=1,2,3) を代入した場合に、式3の等式が成り立つ。
【０００６】
楕円曲線上の点の2倍算は次のようにして計算される。楕円曲線上の点における接線をひくと、その接線は楕円曲線上の他の点において交わる。その交わった点とx座標に関して対称な点を、2倍算を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点(x1,y1)の2倍算
(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)
を計算することにより得られる。
【０００７】
ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果をスカラー倍点、その回数のことをスカラー値という。
【０００８】
楕円曲線上の離散対数問題の求解の困難性が理論的に確立されてきている一方で、実際の実装においては秘密鍵等の秘密情報に関連する情報（計算時間や電力消費量など）が暗号処理において漏洩する場合があり、その漏洩情報をもとに秘密情報を復元するといった、サイドチャネル攻撃という攻撃法が提案されている。
【０００９】
楕円曲線暗号に対するサイドチャネル攻撃が、非特許文献１に記載されている。
【００１０】
楕円曲線暗号においては、与えられたメッセージの暗号化、復号化、署名の作成またはその検証は、楕円曲線演算を用いて行う必要がある。特に楕円曲線上のスカラー倍の計算は、秘密情報であるスカラー値を用いた暗号処理において用いられる。
【００１１】
楕円曲線暗号に対するサイドチャネル攻撃の防御法が、非特許文献２に記載されている。
【００１２】
【非特許文献１】
J.Coron, Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems, Cryptographic Hardware and Embedded Systems: Proceedings of CHES'99, LNCS 1717, Springer-Verlag, (1999) pp.292-302.
【非特許文献２】
K.Okeya, T.Takagi, The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks, RSA conference cryptographer's track (CT-RSA 2003), LNCS 2612, Springer-Verlag, (2003), pp.328-341.
【００１３】
【発明が解決しようとする課題】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証の為に暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも、処理速度や少ないメモリ使用量などがあるが、一般的に安全性、処理速度、メモリ使用量の間にはトレードオフの関係があり、全ての要件をみたすことは難しい。他方、楕円曲線上の離散対数問題が非常に困難である為に、素因数分解の困難性を安全性の根拠にしている暗号と比べて、楕円曲線暗号は鍵長を比較的短くすることができる。そのため計算能力、メモリ容量などのリソースが比較的少なくても暗号処理を行うことが可能である。しかしながら、スマートカード（ICカードともいう）等においては利用可能なリソースは少なく、限られたリソース内で最適な暗号処理を行うように処理速度やメモリ使用量をカスタマイズできる暗号処理が必要となる。
【００１４】
上記技術は、サイドチャネル攻撃を防ぐ方法として有効であるが、処理速度やメモリ使用量をカスタマイズするという点については考慮されていない。
【００１５】
【課題を解決するための手段】
本発明は、サイドチャネル攻撃を防ぐことができる、かつ処理速度とメモリ使用量をカスタマイズできる、楕円曲線演算方法を提供する。
【００１６】
本発明は更に、上記楕円曲線演算方法を用いた、暗号化処理方法、復号化処理方法、署名作成方法、署名検証方法、データ共有方法を提供する。
【００１７】
本発明は、楕円曲線演算において、スカラー値と楕円曲線上の点からスカラー倍点を計算するスカラー倍計算方法であって、上記スカラー値を数値列にエンコードするステップと、上記楕円曲線上の点から前計算テーブルを作成するステップと、上記エンコードした数値列及び前記前計算テーブルからスカラー倍点を計算するステップとを有し、上記前計算テーブルはランダムに選ばれた要素を含む。
【００１８】
本発明は、また、上記エンコードするステップは、前記スカラー値の剰余を選択するステップを含むように構成してもよい。
【００１９】
本発明は、また、上記エンコードするステップは、上記スカラー値に対する第1の剰余と第2の剰余からどちらか一方の剰余を選択するステップを含み、上記剰余を選択するステップは、上記第1の剰余の大きさが予め定められた大きさより小さい場合は、予め定めた確率により上記第1の剰余もしくは上記第2の剰余を選択するステップと、上記第1の剰余の大きさが上記大きさ以上の場合は、上記第1の剰余に付随する楕円曲線上の点が前計算テーブルに存在するか否かにより判定するステップとを含むように構成してもよい。
【００２０】
本発明は、また、上記スカラー倍点を計算するステップは、第1の演算を予め定められた回数を実行するステップと、第1の演算とは異なる第2の演算を実行するステップとを含むように構成してもよい。
【００２１】
本発明は、また、楕円曲線演算において、スカラー値と楕円曲線上の点からスカラー倍点を計算するスカラー倍計算方法であって、上記楕円曲線上の点から前計算テーブルを作成するステップと、上記スカラー値及び上記前計算テーブルからスカラー倍点を計算するステップとを有し、上記前計算テーブルはランダムに選ばれた要素を含むように構成してもよい。
【００２２】
以上のように本発明のスカラー倍計算方法によれば、前計算テーブルに格納する点の個数の選択範囲が広く、かつ前計算テーブルの要素はランダムに選ばれるため、サイドチャネル攻撃を防ぐことができ、かつ処理速度とメモリ使用量をカスタマイズできるスカラー倍計算方法が利用可能になる。
【００２３】
【発明の実施の形態】
以下、本発明の実施例を図面により説明する。
【００２４】
図1はネットワーク142によって接続された本発明による楕円曲線演算方法を適用したコンピュータＡ101、コンピュータＢ121がネットワーク142により接続されたシステム構成を示すものである。
【００２５】
図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、ＲＯＭ106や外部記憶装置107などの記憶装置によって、記憶部102を実現し、ＣＰＵ113やコプロセッサ114などの演算装置が、記憶部102に格納されたプログラムを実行することにより、データ処理部112、スカラー倍計算部115とそれらに含まれる各処理部を実現する。
【００２９】
データ処理部112は、本実施形態においては、暗号化処理部112として機能し、入力されたメッセージの暗号化を行う。
【００３０】
スカラー倍計算部115は、暗号処理部112で暗号化を行うのに必要なパラメタを計算する。記憶部102は、定数104（例えば、楕円曲線の定義式や楕円曲線上の定点である）、秘密情報105（例えば、秘密鍵である）などを記憶している。
【００３１】
コンピュータＢ121は、コンピュータＡ101と同様のハードウェア構成を備える。
【００３２】
更にコンピュータＢ121は、ＲＡＭ123、ＲＯＭ126や外部記憶装置107などの記憶装置によって、記憶部122を実現し、ＣＰＵ133やコプロセッサ134などの演算装置が、記憶部122に格納されたプログラムを実行することにより、データ処理部132、スカラー倍計算部135とそれらに含まれる各処理部を実現する。
【００３３】
データ処理部132は、本実施形態においては、復号化処理部132として機能し、暗号化されたメッセージである暗号文141の復号化を行う。
【００３４】
スカラー倍計算部135は、復号化処理部132で復号化を行うのに必要なパラメタを計算する。記憶部122は、定数124（例えば、楕円曲線の定義式や楕円曲線上の定点である。）、秘密情報125（例えば、秘密鍵である。）などを記憶している。
【００３５】
なお、上記各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、入出力インタフェース110と上記コンピュータ721が利用可能な媒体を介して、他の装置から上記記憶部に導入されてもよい。媒体とは、たとえば、入出力インタフェース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座標の値(xe1,ye1)を、スカラー倍計算部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)
を計算することにより達成する。すなわち、
xf1=((ye1＋yd3)/(xe1-xd3))2-xe1-xd3        (式11)
を計算し、暗号化される前の部分メッセージx1に相当するxf1を得る。
【００５４】
コンピュータＢ121は、復号化処理部132で復号化された部分メッセージから平文メッセージを組み立て(図2の208)、入出力インタフェース110を介して、ディスプレイ108などから出力する。
【００５５】
次に、コンピュータＢ121が、復号化処理を行う場合の、スカラー倍計算部135の処理を詳細に説明する。
【００５６】
第1実施例では、図3で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部115(図1の135)は、エンコード部302、前計算部303、実計算部304からなる。エンコード部302は、剰余取得部321、インデックス集合生成部322、剰余選択部323、繰り返し判定部324、格納部325からなる。前計算部303は、加算部331、2倍算部332、繰り返し判定部333からなる。実計算部304は、ビット値判定部341、加算部342、2倍算部343、繰り返し判定部344からなる。
【００５７】
スカラー倍計算部115がスカラー値d及び楕円曲線上の点Pから、楕円曲線におけるスカラー倍点dPを計算する第1の計算方法を説明する。
【００５８】
スカラー倍計算部115が復号化処理部132からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部302は、入力されたスカラー値dを数値列dw[j]にエンコードする。すなわち、
d=dw[n＋w0-1]2n＋w0-1＋dw[n＋w0-2]2n＋w0-2＋・・・＋dw[j]2j＋・・・ ＋dw[0]
(式12)
-2w0-1≦dw[j]≦2w0-1 or dw[j]∈B                            (式13)
をみたすdw[j]に、スカラー値dを変換する。ここで、nはスカラー値dを2進表記した場合のビット長であり、wはあらかじめ定めた小さな正有理数で、ウィンドウ幅と呼ばれる。w0は正整数であり、w0=ceil(w)をみたす。ただし、ceil(w)はw以上の最小の整数を表す。Bはランダムに選ばれたインデックス集合であり、
B={±b1,±b2,・・・,±bm}と表される。ただし、m個の相異なるb1,b2,・・・,bmは
{2w0-1＋1,2w0-1＋3,・・・,2w0-1}の範囲から選ばれる。
ここで、m=w12w0-2, w1=w-(w0-1)である。計算時間を優先する場合はwを大きな値とする。メモリ使用量を小さくする場合はwを小さな値にする。尚、ウィンドウ幅wはmが整数となるように定められる。正整数w0を固定し、ウィンドウ幅wを動かした場合、整数mは0から2w0-2までの値を取り得る。
【００５９】
前計算部303は、入力された楕円曲線上の点Pから、インデックス集合Bを用いて前計算テーブルを作成する。前計算テーブルはP, 3P, ・・・, (2w0-1-1)P及びbjP, j=1,・・・,mにより構成される。
【００６０】
実計算部304は、エンコードされたスカラー値と楕円曲線上の点Pから、前計算テーブルを用いてスカラー倍点dPを計算する。
【００６１】
次にエンコード部302、前計算部303、実計算部304の行う各処理について詳細に説明する。
【００６２】
まず、図4を用いて、エンコード部302がスカラー値dをエンコードする方法を説明する。
【００６３】
変数d'にスカラー値dを代入する。w0にceil(w)を、w1にw-(w0-1)をそれぞれ割り当てる(401)。
【００６４】
インデックス集合生成部322は、m=w12w0-2とし、m個の相異なる
b1,b2,・・・,bmを{2w0-1＋1,2w0-1＋3,・・・,2w0-1}よりランダムに選び、インデックス集合BをB={±b1,±b2,・・・,±bm}とする。確率を示す数値Pwにw1を割り当てる(402)。
【００６５】
変数rに初期値0を、変数iに初期値0をそれぞれ代入する(403)。
【００６６】
繰り返し判定部324は、変数d'が1より大きいかどうかを判定する。
【００６７】
d'が1より大きければステップ411へ行く。1以下であればステップ431へ行く(404)。
【００６８】
ステップ404でd'が1より大きい場合、
剰余取得部321は、スカラー値d'の2w0＋1による剰余から2w0を引いた値をx[i]に、スカラー値d'の2w0による剰余から2w0-1を引いた値をy[i]に、それぞれ格納する(411)。
【００６９】
剰余選択部323は、|x[i]|<2w0-1であるかどうかを判定する。ここで、|x[i]|はx[i]の絶対値を表す。|x[i]|<2w0-1であればステップ413へ行く。|x[i]|≧ 2w0-1であればステップ421へ行く(412)。
【００７０】
ステップ412で|x[i]|<2w0-1 の場合、
剰余選択部323は、確率Pwでriにw0を、u[i]にx[i]をそれぞれ格納し、確率1-Pwでriにw0-1を、u[i]にy[i]をそれぞれ格納し、ステップ414へ行く(413)。
【００７１】
ステップ412で|x[i]|≧ 2w0-1の場合、
剰余選択部323は、x[i]が集合Bに属するかどうかを判定する。x[i]がBに属する場合はステップ422へ行く。x[i]がBに属さない場合はステップ423へ行く(421)。
【００７２】
ステップ421でx[i]がBに属する場合、
剰余選択部323は、riにw0を、u[i]にx[i]をそれぞれ格納し、ステップ414へ行く(422)。
【００７３】
ステップ421でx[i]がBに属さない場合、
剰余選択部323は、riにw0-1を、u[i]にy[i]をそれぞれ格納し、ステップ414へ行く(423)。
【００７４】
剰余取得部321は、(d'-u[i])/2riを計算し、それを新たなd'とする(414)。
【００７５】
格納部325は、dw[r＋ri-1], dw[r＋ri-2], ・・・, dw[r]にそれぞれ、0,0,・・・,0,u[i]を格納する(415)。
【００７６】
変数rをriだけ増加させ、変数iを1増加させ、ステップ404へ戻る(416)。
【００７７】
ステップ404でd'が1以下であった場合、
格納部325は、dw[n＋w0-1],・・・,dw[r＋1],dw[r]にそれぞれ、0,・・・,0,1を格納する(431)。
【００７８】
エンコード部302は、dw[n＋w0-1],・・・,dw[0]及びBを実計算部304へ出力する(432)。
【００７９】
次に、図5を用いて、前計算部303が楕円曲線上の点から、インデックス集合Bを用いて前計算テーブルを作成する方法を説明する。
【００８０】
点PをECDBLにより2倍し、その結果を2Pに格納する(501)。
【００８１】
変数jに初期値1を代入する(502)。
【００８２】
繰り返し判定部333により、jが2w0-1より小さいかどうかを判定する。jが2w0-1より小さい場合はステップ504へ行く。jが2w0-1以上の場合はステップ511へ行く(503)。
【００８３】
ステップ503でjが2w0-1より小さい場合、
点jPと点2PをECADDにより加算し、その結果を(j＋2)Pに格納する(504)。
【００８４】
変数jを2増加させ、ステップ503へ戻る(505)。
【００８５】
ステップ503でjが2w0-1以上の場合、
点(2w0-1-1)Pと点PをECADDにより加算し、その結果を2w0-1Pに格納する(511)。
【００８６】
変数jに1を代入する(512)。
【００８７】
繰り返し判定部333により、jがm以下であるかどうかを判定する。jがm以下であればステップ514へ行く。jがmより大きい場合はステップ521へ行く(513)。
【００８８】
ステップ513でjがm以下の場合、
点2w0-1Pと点(bj-2w0-1)PをECADDにより加算し、その結果をbjPに格納する(514)。
【００８９】
変数jを1増加させ、ステップ513へ戻る(515)。
【００９０】
ステップ513でjがmより大きい場合、
P, 3P, ・・・, (2w0-1-1)P及びbjP, j=1,・・・,mを前計算テーブルとして出力する(521)。
【００９１】
ただし、ECADD, ECDBLはそれぞれ楕円曲線における加算、2倍算を表す。加算は式1,2を用いて、2倍算は式4,5を用いてそれぞれ計算される。なお、加算、2倍算の計算には式1,2、および式4,5を用いる以外にも、射影座標やヤコビアン座標における計算公式があり、
非特許文献3：Cohen, H., Miyaji, A., Ono, T., Efficient Elliptic Curve Exponentiation Using Mixed Coordinates, Advances in Cryptology - ASIACRYPT 1998, LNCS 1514, Springer-Verlag, (1998), pp.51-65.
に記載されている。
【００９２】
また、楕円曲線上の点Q=(x,y)に対して、楕円曲線加算に関する逆元の点-Qは、-Q=(x,-y)と表されるため、点Qの座標が与えられていれば容易に計算できる。そのため、
点P, 3P, ・・・, (2w0-1-1)P及びbjP, j=1,・・・,m のみを前計算テーブルとして格納する。その後の実計算部304が行う計算で必要となる
点-P, -3P, ・・・, -(2w0-1-1)P及び-bjP, j=1,・・・,m は、それらから導出すればよく、前計算テーブルには格納する必要はない。
【００９３】
なお、点-P, -3P, ・・・, -(2w-1)P及び-bjP, j=1,・・・,mの導出を省くために、それらの点のy座標の値のみを前計算テーブルに格納しておいてもよい。
【００９４】
なお、前計算部303の行う前計算テーブルの作成処理は、
点P, 3P, ・・・, (2w0-1-1)P及びbjP, j=1,・・・,mが計算されればよい。そのため、モンゴメリトリックを用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化をはかってもよい。
【００９５】
モンゴメリトリックによる逆元演算共通化方法が
非特許文献4：Cohen, H., A course in computational algebraic number theory, GTM138, Springer -Verlag, (1993).
の481ページに記載されている。
【００９６】
また、点Pが固定点である場合、前計算部303の行う前計算テーブルの作成処理のうち、
点P, 3P, ・・・, (2w0-1-1)Pの計算、すなわち、ステップ501からステップ511の処理は、ただ一度行えばよい。なぜならば、
点P, 3P, ・・・, (2w0-1-1)Pは、インデックス集合Bに依存していないからである。そのため、一旦
点P, 3P, ・・・, (2w0-1-1)Pを計算すれば、それ以降のスカラー倍計算では、
点P, 3P, ・・・, (2w0-1-1)Pを再計算する必要はなく、インデックス集合Bに依存する部分のみを再計算すればよい。
【００９７】
最後に、図6を用いて、実計算部304がエンコードされたスカラー値と楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
【００９８】
変数cに初期値n＋w0-1を代入する(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)。
【０１０４】
jが0より小さいかどうかを判定する。jが0より小さい場合はステップ621へ行く。0以上の場合はステップ614へ行く(613)。
【０１０５】
点QをECDBLにより2倍し、点Qに再び格納する(614)。
【０１０６】
dw[j]が0か0でないかを判定する。
【０１０７】
dw[j]が0の場合はステップ617へ行く。0でなければステップ616へ行く(615)。
【０１０８】
ステップ615でdw[j]が0でない場合、
点Qとdw[j]PとをECADDにより加算する。ただし、dw[j]が負の場合は(-dw[j])Pのy座標を反転したものを用いて加算を行う。その結果を点Qに格納し、ステップ617へ行く(616)。
なお、dw[j]が0でない場合は、dw[j]は式13をみたす奇数である。そのため、dw[j]Pもしくは(-dw[j])Pのいずれかが、前計算テーブルに必ず存在する。
【０１０９】
変数jを1減少させ、ステップ613へと戻る(617)。
【０１１０】
ステップ613でjが0より小さい場合、点Qを出力する(621)。
【０１１１】
エンコード部302が行う処理により出力されるdw[j]は、式12, 式13をみたす。この理由は次の通りである。
ステップ404からステップ416のループにおいて、i回目のd'の値をd'[i]とおく。すなわち、ステップ414で
d'[i＋1]=(d'[i]-u[i])/2ri        (式14)
が計算される。0回目のループでは
d=d'[0]                         (式15)
となる。1回目のループでは
d=d'[1]2r0＋u[0]                 (式16)
となる。以下同様にして、i回目のループでは
d=(・・・(d'[i]2ri＋u[i])2ri-1＋・・・＋u[1])2r0＋u[0]    (式48)
となる。ステップ414の計算は、d'[i]<2ri＋1のとき、
d'-((d'mod 2ri＋1)-2ri)=2ri        (式17)
となるため、d'[i＋1]=1となる。ステップ415で、dw[r]以外に0が割り当てられていることに注意すれば、dが式12をみたすことがわかる。
ステップ411で計算されるy[i]は、
-2w0-1≦y[i]≦2w0-1                (式18)
の範囲となることは容易にわかる。
x[i]が
-2w0-1≦x[i]≦2w0-1                (式19)
の範囲にある場合は特に問題はない。
x[i]が式19の範囲外の場合は、ステップ412の判定結果によりステップ421へ行く。ステップ421ではx[i]∈Bの場合に、ステップ422へ行き、x[i]が選択される。すなわち、
x[i]∈B                         (式20)
をみたす。u[i]はx[i],y[i]のいずれかが割り当てられ、0以外のdw[r]はu[i]が割り当てられる。
したがって、式13をみたす。
【０１１２】
エンコード部302が行う処理で計算されるu[i]はi=0を除き全て奇数となる。この理由は次の通りである。ステップ411で、d'[i]が奇数であれば、x[i],y[i]は奇数となる。そのため、d'[i]が奇数の場合、u[i]は奇数となる。一方、ステップ414で、d'[i＋1]=(d'[i]-u[i])/2riが計算される。
d'[i]-((d'[i] mod 2ri＋1)-2ri) mod 2ri＋1 = 2ri     (式21)
であるため、d'[i＋1]は奇数となる。したがって、i=0を除き、u[i]は全て奇数である。
【０１１３】
なお、u[0]も奇数とするためには、スカラー値dが奇数であればよい。そのためには、入力されたスカラー値dが偶数の時は、d＋1を改めてスカラー値d'としてエンコードする。すなわち、dを奇数に変換する。そして、スカラー倍点d'Pを計算する。
d'P=(d＋1)P=dP＋P            (式22)
であるので、d'Pから点Pを引き、その値をスカラー倍点dPとして出力すればよい。
【０１１４】
また、入力されたdが奇数の時は、d＋2を改めてスカラー値d'としてエンコードし、
d'P=(d＋2)P=dP＋2P            (式23)
を利用して、スカラー倍点dPを求めてもよい。この場合、dが奇数の場合も偶数の場合も、行う処理が一致するという利点がある。
【０１１５】
実計算部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
(式24)
と表されるとする。このとき、次にステップ613に来る時も点Qは式24をみたすことを示す。
【０１１７】
点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
(式25)
となる。したがってdw[j]=0の時も含めて、ステップ617の直前で、点Qは式25をみたす。ステップ617でjが1減少するので、式25のjにj＋1を代入すると式24になる。すなわち、次にステップ613に来る時も点Qは式24をみたす。
【０１１８】
j>cに対するdw[j]の値は0であるので、ステップ621で出力される点Qの値は
(dw[n]2n＋dw[n-1]2n-1＋・・・＋dw[0])P        (式26)
に等しい。実計算部304に入力されるスカラー値は、エンコード部302によりエンコードされたdw[j]であるので、そのdw[j]は式12をみたす。したがって、Q=dPである。
【０１１９】
上記スカラー倍におけるメモリ使用量は、前計算部303の前計算テーブルの大きさにより定まる。上記スカラー倍計算方法では、前計算テーブルは
P,3P,・・・,(2w0-1-1)P及びbjP, j=1,・・・,m により構成される。すなわち、格納する点の個数は(2w0-2＋m)個である。正整数w0を固定し、ウィンドウ幅wを動かした場合、整数mは0から2w0-2までの値を取り得る。そのため、ウィンドウ幅wを適切に選択することにより、格納する点の個数は任意の値にできる。一方、非特許文献2の方法では、前計算テーブルに格納する点の個数は1,2,4,8,・・・ と2ベキの値しか選択できない。そのため、上記スカラー倍計算方法は、非特許文献2の方法と比べて、前計算テーブルに格納する点の個数の選択範囲が広く、処理速度やメモリ使用量をカスタマイズすることができる。
【０１２０】
また、上記スカラー倍方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由は次の通りである。
【０１２１】
エンコード部302によりスカラー値dは数値列dw[j]にエンコードされる。この数値列dw[j]はパターン
|0・・・0x|0・・・0x|・・・|0・・・0x|    (式27)
をもつ。ここで各xは各々非0の値であり、それぞれu[i]に対応する。ここで0・・・0はri個、すなわちw0-1個もしくはw0-2個連続する。実計算部304がスカラー倍点を計算する際に、ステップ613-617の繰り返し処理において、|0・・・0x|のブロックに対応する楕円曲線演算は、|D・・・DA|、すなわちw0回もしくはw0-1回のDの後にAとなる。ただし、DはECDBLを、AはECADDをそれぞれ表す。一方riは、確率Pwでw0となり、確率1-Pwでw0＋1となる。
なぜならば、|x[i]|<2w0-1の場合、ステップ413において確率Pwでri=w0、確率1-Pwでri=w0＋1となる。
また|x[i]|≧2w0-1の場合、x[i]∈Bとなる確率は、
(Bの要素数)/(2w0-1≦|k|<2w0をみたす奇数kの個数)=w1であるので、Pwとなる。この場合、
x[i]∈Bの時にri=w0、そうでない時にri=w0-1となる。したがって、いずれの場合においても、riは、確率Pwでw0となり、確率1-Pwでw0-1となる。確率Pwは公開情報であるw1にのみ依存し、秘密情報には依存していない。結果として、全てのスカラー値に対して、実行する楕円曲線演算は
|D・・・DA|D・・・DA|・・・|D・・・DA|    (式28)
となり、Dの連続する回数は各々riであるが、この値は公開情報w1にのみ依存し、秘密情報には依存しない。特に、式28のみからは、スカラー値dに関する情報を引き出すことができない。
【０１２２】
なお、非特許文献1のランダム化射影座標を併用してスカラー倍計算を行ってもよい。そうすると、同じ点Pを入力しても実行毎に異なる値に変換してスカラー倍計算を行うので、攻撃者が中間値の値を予測できなくなる。
【０１２３】
また、前計算テーブルに格納されている点が読み出されるたびに、再びランダム化して、前計算テーブルに書き込んでもよい。そうすると、同じデータの再使用がなくなるため、より一層、サイドチャネル攻撃への耐性が増す。
【０１２４】
また、一つのスカラー倍計算中に一度以上、当該計算中に参照する前計算テーブルを再作成してもよい。そうすることにより、テーブルから引用される値がより頻繁に変更されることになり、サイドチャネル攻撃への耐性がさらに増す。
【０１２５】
また、任意回数のスカラー倍計算において、同一の前計算テーブルを再利用してもよい。そうすることにより、前計算テーブルの作成処理に掛かる時間を減らせるため、計算時間を短縮することができる。
【０１２６】
また、スカラー倍計算毎に、必要とされる計算速度、同時に使用する他のアプリケーションの優先度などの状況に応じて、前計算テーブルのサイズを変更してもよい。
【０１２７】
より具体的には、利用可能なワーク領域を調べて、そのワーク領域に応じた前計算テーブルサイズを選択し、スカラー倍を計算してもよい。そうすることにより、個別状況に応じたカスタマイズをより繊細に行うことができる。
【０１２８】
あるいは、スカラー倍以外のモジュールの処理に優先的にワーク領域を割り当てるために、前計算テーブルのサイズを小さくしてスカラー倍計算を行ってもよい。
【０１２９】
あるいは、スカラー倍計算を高速に行うため、前計算テーブルのサイズを大きくしてスカラー倍計算を行なってもよい。
【０１３０】
以上の通り、上記計算方法は、サイドチャネル攻撃に有用な情報を与えないので、サイドチャネル攻撃に対して耐性がある。また、前計算テーブルに格納する点の個数の選択範囲が広いため、処理速度やメモリ使用量をカスタマイズすることができる。
【０１３１】
なお、第1の計算方法では楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数2の有限体上で定義された楕円曲線や、OEF(Optimal Extension Field)上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよい。OEFについては、
非特許文献5:D.V. Bailey, C. Paar, Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms, Advances in Cryptology Crypto '98, LNCS 1462, (1998), 472-485.
に記載されている。
【０１３２】
第2実施例では、図7で示されるスカラー倍計算部の機能ブロックを用いる。スカラー倍計算部115(図1の135)は、前計算部703、実計算部704からなる。前計算部703は、加算部331、2倍算部332、繰り返し判定部333、インデックス集合生成部734からなる。実計算部304は、加算部342、2倍算部343、繰り返し判定部344、スカラー値表現変換部745、ウィンドウ幅選択部746からなる。
【０１３３】
スカラー倍計算部115がスカラー値d及び楕円曲線上の点Pから、楕円曲線におけるスカラー倍点dPを計算する第2の計算方法を説明する。第2の計算方法では、スカラー値dを数値列にエンコードすることなくスカラー倍点を計算するという特徴がある。
【０１３４】
スカラー倍計算部115が復号化処理部132からスカラー値dと楕円曲線上の点Pを受け取ると、前計算部703は、インデックス集合Bを生成し、入力された楕円曲線上の点Pとインデックス集合Bを用いて前計算テーブルを作成する。前計算テーブルは
P, 3P, ・・・, (2w0-1-1)P及びbjP, j=1,・・・,mにより構成されることは、第1の計算方法と同様である。インデックス集合Bが
B={±b1,±b2,・・・,±bm}と表され、m個の相異なるb1,b2,・・・,bmは
{2w0-1＋1,2w0-1＋3,・・・,2w0-1}の範囲から選ばれることも第1の計算方法と同様である。
【０１３５】
実計算部304は、入力されたスカラー値dと楕円曲線上の点Pから、インデックス集合と前計算テーブルを用いてスカラー倍点dPを計算する。
【０１３６】
次に前計算部703、実計算部704の行なう各処理について詳細に説明する。
【０１３７】
まず、図8を用いて、前計算部703が楕円曲線上の点から、前計算テーブル及びインデックス集合Bを作成する方法を説明する。
【０１３８】
点PをECDBLにより2倍し、その結果を2Pに格納する(801)。
【０１３９】
変数jに初期値1を代入する(802)。
【０１４０】
繰り返し判定部733により、jが2w0-1より小さいかどうかを判定する。jが2w0-1より小さい場合はステップ804へ行く。jが2w0-1以上の場合はステップ811へ行く(803)。
【０１４１】
ステップ803でjが2w0-1より小さい場合、
点jPと点2PをECADDにより加算し、その結果を(j＋2)Pに格納する(804)。
【０１４２】
変数jを2増加させ、ステップ803へ戻る(805)。
【０１４３】
ステップ803でjが2w0-1以上の場合、
点(2w0-1-1)Pと点PをECADDにより加算し、その結果を2w0-1Pに格納する(811)。
【０１４４】
インデックス集合Bに空集合を初期値として代入し、変数jに1を代入する(812)。
【０１４５】
繰り返し判定部733により、jがm以下であるかどうかを判定する。jがm以下であればステップ814へ行く。jがmより大きい場合はステップ821へ行く(813)。
【０１４６】
ステップ813でjがm以下の場合、
インデックス集合生成部734は、{2w0-1＋1,2w0-1＋3,・・・,2w0-1}の範囲よりbjをランダムに選ぶ(814)。
【０１４７】
インデックス集合生成部734により、bjがBの要素として既に含まれているかどうかを判定する。BjがBの要素として含まれていればステップ814へ戻る、bjがBの要素として含まれていなければステップ816へ行く(815)。
【０１４８】
点2w0-1Pと点(bj-2w0-1)PをECADDにより加算し、その結果をbjPに格納する(816)。
【０１４９】
インデックス集合生成部734は、インデックス集合Bにbjを要素として追加する(817)。
【０１５０】
変数jを1増加させ、ステップ813へ戻る(818)。
【０１５１】
ステップ813でjがmより大きい場合、
P, 3P, ・・・, (2w0-1-1)P及びbjP, j=1,・・・,mを前計算テーブルとして出力する。インデックス集合Bを出力する(821)。
【０１５２】
また、点P, 3P, ・・・, (2w-1)Pのみを前計算テーブルとして格納し、
点-P, -3P, ・・・, -(2w-1)Pを前計算テーブルには格納する必要はないことは第1の計算方法と同様である。
【０１５３】
なお、点-P, -3P, ・・・, -(2w-1)P及び-bjP, j=1,・・・,mの導出を省くために、それらの点のy座標の値のみを前計算テーブルに格納しておいてもよいことも第1の計算方法と同様である。
【０１５４】
点Pが固定点である場合、前計算部303の行う前計算テーブルの作成処理のうち、
点P, 3P, ・・・, (2w0-1-1)Pの計算、すなわち、ステップ801からステップ811の処理は、ただ一度行えばよいことは第1の計算方法と同様である。
【０１５５】
前計算部703の行う前計算テーブルの作成処理は、
点P, 3P, ・・・, (2w-1)Pが計算されればよい。そのため、モンゴメリトリックを用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化をはかってもよいことも、第1の計算方法と同様である。
【０１５６】
次に、図9、図10を用いて、実計算部704が入力されたスカラー値dと楕円曲線上の点Pから、インデックス集合Bと前計算テーブルを用いて楕円曲線におけるスカラー倍点を計算する方法を説明する。
【０１５７】
点Qに無限遠点を代入する(901)。
【０１５８】
スカラー値表現変換部745は、スカラー値dを1,-1により表現したd~に変換する(902)。すなわち、d~は整数としてdに等しく、かつ
d~=dn-1~2n-1＋dn-2~2n-2＋・・・＋d0~, di~=1 or -1           (式29)
と表される。この変換を達成するためには、スカラー値dを
d=dn-12n-1＋dn-22n-2＋・・・＋d0, di= 0 or 1         (式30)
と表したとき、
dn-1~=1                                   (式31)
di~=1  if di＋1 = 1 for i=0,・・・,n-2         (式32)
di~=-1 if di＋1 = 0 for i=0,・・・,n-2         (式33)
により変換すると、式29をみたす。尚、d~に変換できるのは、dが奇数の時のみである。
【０１５９】
変数iに初期値nを代入する(903)。
【０１６０】
繰り返し判定部733は、iがw0-1より大きいかどうかを判定する。iがw0-1よ大きい場合はステップ911へ行く。w0-1以下であればステップ1001へ行く(904)。
【０１６１】
ステップ904でiがw0-1より大きい場合、
ウィンドウ幅選択部746は、変数xに整数MSBw0(d~)を格納する(911)。ただし、MSBw0(d~)はd~の上位w0ビットにより構成される数値を表す。
【０１６２】
ウィンドウ幅選択部746は、変数xの値がインデックス集合Bの要素として含まれている場合はbに1を格納する。含まれていない場合はbに0を格納する(912)。
【０１６３】
ウィンドウ幅選択部746は、確率Pwでpに1を格納し、確率1-Pwでpを格納する(913)。
【０１６４】
ウィンドウ幅選択部746は、変数uに
1-|MSB2(d~)/2|を格納する(914)。
【０１６５】
ウィンドウ幅選択部746は、変数rに
w0-1＋((u∧p)∨((1-u)∧b))を代入する(915)。
【０１６６】
変数jに1を代入する(916)。
【０１６７】
点QをECDBLにより2倍し、点Qに再び格納する(917)。
【０１６８】
繰り返し判定部733は、jがr以上であるかどうかを判定する。jがr以上であればステップ921へ行く。rより小さければステップ919へ行く(918)。
【０１６９】
ステップ918でjがr以上の場合、変数jを1増加させ、ステップ917へ戻る(919)。
【０１７０】
ステップ918でjがrより小さい場合、点QとMSBr(d~)PとをECADDにより加算する。ただし、MSBr(d~)が負の場合は(-MSBr(d~))Pのy座標を反転したものを用いて加算を行う。その結果を点Qに格納する。(921)。
【０１７１】
変数iをr減少させ、ステップ904へ戻る(922)。
【０１７２】
ステップ904でiがw0-1以下の場合、
繰り返し判定部733は、iが0以下であるかどうかを判定する。iが0以下の場合はステップ1007へ行く。iが0より大きい場合はステップ1002へ行く(1001)。
【０１７３】
ステップ1001でiが0より大きい場合、
変数jに1を代入する(1002)。
【０１７４】
点QをECDBLにより2倍し、点Qに再び格納する(1003)。
【０１７５】
繰り返し判定部733は、jがi以上であるかを判定する。jがi以上であればステップ1006へ行く。iより小さければステップ1005へ行く(1005)。
【０１７６】
ステップ1004でjがiより小さい場合、
変数jを1増加させ、ステップ1003へ戻る(1005)。
【０１７７】
ステップ1004でjがi以上の場合、点Qとd~PとをECADDにより加算する。ただし、d~が負の場合は(-d~)Pのy座標を反転したものを用いて加算を行う。その結果を点Qに格納する。(1006)。
【０１７８】
点Qを出力する(1007)。
【０１７９】
実計算部704が行う処理により出力されるスカラー倍点はdPに一致する。この理由は次の通りである。
ステップ904からステップ922のループにおいて、k回目のループにおけるrの値をrkとおく。
ステップ901で楕円曲線上の点Qに無限遠点が代入される。
1回目のループ終了後では
Q=r1P                                (式34)
となる。2回目のループ終了後では
Q=(r12r2＋r2)P                         (式35)
となる。以下同様にして、k回目のループ終了後では
Q=((・・・(r12r2＋r2)2r3＋・・・＋rk-1)2rk＋rk)P      (式36)
となる。ステップ1002からステップ1006の処理も同様であることに注意すれば、ステップ1007における点QはQ=d~Pをみたすことがわかる。数値としてd=d~であるため、Q=dPとなる。
【０１８０】
実計算部704のステップ921の楕円加算で用いる点MSBr(d~)Pに対して、MSBr(d~)Pもしくは(-MSBr(d~))Pのいずれかが前計算テーブルに必ず存在する。この理由は次の通りである。まず、
MSBr(d~) mod 2 = 1であり、MSBr(d~)は奇数である。ステップ915で変数rにw0-1, w0のいずれかの値が代入される。r=w0-1の場合、前計算テーブルは
P,3P,・・・,(2w0-1-1)Pを含むので、MSBr(d~)Pもしくは(-MSBr(d~))Pのいずれかが前計算テーブルに必ず存在する。次にr=w0の場合を考える。r=w0となるためには、(u∧p)=1であるか、もしくは
((1-u)∧b)=1である必要がある。(u∧p)=1の時、u=1であるので、d~の最上位ビットの符号と上位2番目のビットの符号は異なる。そのため
-2w0-1≦MSBw0(d~)≦2w0-1              （式37）
となり、MSBr(d~)Pもしくは(-MSBr(d~))Pのいずれかが前計算テーブルに存在する。
((1-u)∧b)=1の時、b=1であるので、MSBw0(d~)はインデックス集合Bの要素である。そのため、MSBr(d~)Pもしくは(-MSBr(d~))Pのいずれかが前計算テーブルに存在する。結果として、いずれの場合も、MSBr(d~)Pもしくは(-MSBr(d~))Pのいずれかが前計算テーブルに必ず存在する。
【０１８１】
なお、dをd~に変換するためには、スカラー値dが奇数である必要がある。そのためには、入力されたスカラー値dが偶数の時は、d＋1を改めてスカラー値d'としてエンコードする。すなわち、dを奇数に変換する。そして、スカラー倍点d'Pを計算する。
d'P=(d＋1)P=dP＋P            (式38)
であるので、d'Pから点Pを引き、その値をスカラー倍点dPとして出力すればよい。
【０１８２】
また、入力されたdが奇数の時は、d＋2を改めてスカラー値d'としてエンコードし、
d'P=(d＋2)P=dP＋2P            (式39)
を利用して、スカラー倍点dPを求めてもよい。この場合、dが奇数の場合も偶数の場合も、行う処理が一致するという利点がある。
【０１８３】
上記スカラー倍におけるメモリ使用量は、前計算部703の前計算テーブルの大きさにより定まる。上記スカラー倍計算方法では、前計算テーブルは
P,3P,・・・,(2w0-1-1)P及びbjP, j=1,・・・,m により構成され、格納する点の個数は(2w0-2＋m)個である。正整数w0を固定し、ウィンドウ幅wを動かした場合、整数mは0から2w0-2までの値を取り得る。そのため、ウィンドウ幅wを適切に選択することにより、格納する点の個数は任意の値にできる。一方、非特許文献2が開示する従来の方法では、前計算テーブルに格納する点の個数は1,2,4,8,・・・ と2ベキの値しか選択できない。そのため、上記スカラー倍計算方法は、非特許文献2の方法と比べて、前計算テーブルに格納する点の個数の選択範囲が広く、高速処理性能やメモリ容量を考慮してカスタマイズすることができる。
【０１８４】
また、上記スカラー倍方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由は次の通りである。
【０１８５】
実計算部704がスカラー倍点を計算する際に、ステップ904-921の繰り返し処理において実行される楕円曲線演算は、一回のループにつき |D・・・DA| となる。すなわちw0回もしくはw0-1回のDの後にAとなる。ただし、DはECDBLを、AはECADDをそれぞれ表す。一方rは、確率Pwでw0となり、確率1-Pwでw0＋1となる。
【０１８６】
この理由について、まずu=1の場合について考察する。変数pは、ステップ913において確率Pwでp=1、確率1-Pwでp=0が割り当てられる。そのため、確率Pwでr=w0、確率1-Pwでr=w0-1となる。
【０１８７】
次にu=0の場合について考察する。変数bは、ステップにおいてxがBの要素であるときb=1、xがBの要素でないときb=0が割り当てられる。
|x|≧2w0-1の場合、x∈Bとなる確率は、
(Bの要素数)/(2w0-1≦|k|<2w0をみたす奇数kの個数)=w1であるので、Pwとなる。変数uは、ステップ914で
u=1-|MSB2(d~)/2|が割り当てられる。すなわち、u=0は|x|≧2w0-1と同値である。そのため、u=0の場合、確率Pwでr=w0、確率1-Pwでr=w0-1となる。
【０１８８】
したがって、いずれの場合においても、rは、確率Pwでw0となり、確率1-Pwでw0-1となる。確率Pwは公開情報であるw1にのみ依存し、秘密情報には依存していない。結果として、全てのスカラー値に対して、実行する楕円曲線演算は
|D・・・DA|D・・・DA|・・・|D・・・DA|    (式40)
となり、Dの連続する回数は各々w0もしくはw0-1であるが、どちらの値が選択されるかは公開情報w1にのみ依存し、秘密情報には依存しない。特に、式35のみからは、スカラー値dに関する情報を引き出すことができない。
【０１８９】
なお、第2の計算方法でも、第1の計算方法と同様に、非特許文献1のランダム化射影座標を併用してスカラー倍計算を行ってもよい。そうすると、同じ点Pを入力しても実行毎に異なる値に変換してスカラー倍計算を行うので、攻撃者が中間値の値を予測できなくなる。
【０１９０】
また、第1の計算方法と同様に、前計算テーブルに格納されている点が読み出されるたびに、再びランダム化して、前計算テーブルに書き込んでもよい。そうすると、同じデータの再使用がなくなるため、より一層、サイドチャネル攻撃への耐性が増す。
【０１９１】
以上の通り、第2の計算方法は、サイドチャネル攻撃に有用な情報を与えないので、サイドチャネル攻撃に対して耐性がある。また、前計算テーブルに格納する点の個数の選択範囲が広いため、処理速度やメモリ使用量をカスタマイズすることができる。
【０１９２】
なお、第2の計算方法では楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数2の有限体上で定義された楕円曲線や、OEF(Optimal Extension Field)上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよい。OEFについては非特許文献5に記載されている。
【０１９３】
以上、コンピュータＢ121が、暗号化されたデータ141を復号化する場合のスカラー倍計算部135の動作を説明したが、コンピュータＡ101が入力メッセージを暗号化する場合も同様である。
【０１９４】
その場合には、コンピュータＡ101のスカラー倍計算部115は、既に説明した楕円曲線上の点Q、乱数kによるスカラー倍点kQと、公開鍵aQと乱数kによるスカラー倍点k(aQ)を出力する。このとき、上記計算方法で説明したスカラー値dを乱数k、楕円曲線上の点Pを楕円曲線上の点Q、公開鍵aQとして同様の処理を行うことにより、それぞれのスカラー倍点を求めることができる。
【０１９５】
次に本発明を署名検証システムに適用する実施形態を、図11と図2を用いて説明する。
【０１９６】
図11の署名検証システムは、スマートカード1101と署名検証処理を行うコンピュータ1121とから成る。
【０１９７】
スマートカード1101は、図1のコンピュータＡ101と類似の構成を備え、ＣＰＵ113やコプロセッサ114などの演算装置とが記憶部102に格納されているプログラムを実行することにより、データ処理部112ではなく、署名生成処理部1112を実現する。ただし、図1に示す外部記憶装置107、ディスプレイ108、キーボード109を備えなくてもよい。
【０１９８】
コンピュータ1121は、コンピュータＡ101と同様の構成を備え、ＣＰＵ113がプログラムを実行することによりデータ処理部112ではなく、署名検証処理部1132を実現する。
【０１９９】
スカラー倍計算部1115と1135は、図1に示すスカラー倍計算部115または135と同様の機能を備える。
【０２００】
なお、本実施例において、コンピュータ1121内の各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、コンピュータ1121が利用可能な媒体を介して他の装置から上記記憶部に導入されてもよい。
【０２０１】
さらに、スマートカード1101内の各プログラムは、あらかじめ、上記スマートカード1101内の記憶部に格納されていても良いし、必要なときに、入出力インタフェースを介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して上記記憶部に導入されてもよい。
【０２０２】
媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【０２０３】
図11の署名検証システムにおける署名作成と署名検証動作を、図2を参照して説明する。
【０２０４】
コンピュータ1121は、ランダムに選んだ数値をチャレンジコード1143として、インタフェース1142を介してスマートカード1101に転送する。
【０２０５】
署名生成処理部1112(図2の112)は、チャレンジコード1143を受け付け、チャレンジコード1143のハッシュ値をとり、所定のビット長の数値fに変換する。
【０２０６】
署名生成処理部1112は、乱数uを生成し、記憶部1102(図2の102)に格納されている定数1104から読み出した(図2の205)楕円曲線上の定点Qとともにスカラー倍計算部1115(図2の115)へ送る(図2の206)。
【０２０７】
スカラー倍計算部1115は、定点Q、乱数uによるスカラー倍点(xu,yu)を計算し、計算されたスカラー倍点を署名生成処理部1112へ送る(図2の207)。
【０２０８】
署名生成処理部1112は、送られたスカラー倍点を用いて署名の生成を行う。例えば、ECDSA署名であれば、
s = xu mod q               (式41)
t = u-1(f＋ds) mod q        (式42)
を計算することによりチャレンジコード1143に対応する署名(s,t)を得る(図2の208)。
【０２０９】
ここで、qは定点Qの位数、すなわち定点Qのq倍点qQが無限遠点になり、qより小さな数値mに対する定点Qのm倍点mQは無限遠点にはならない、というような数値のことである。
【０２１０】
ECDSA署名については、例えば、
非特許文献6：ANSI X9.62 Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), (1998)
に記載されている。
【０２１１】
スマートカード1101は、署名生成処理部1112で作成した署名1141を入出力インタフェース1110より出力し、インタフェース1142を介してコンピュータ1121へ転送する。
【０２１２】
コンピュータ1121の署名検証処理部1132(図2の112)は、署名1141が入力される(図2の204)と、署名1141の数値s,tが適切な範囲内すなわち1≦s, t<qであるかを調べる。
【０２１３】
数値s, tが上記範囲内になければチャレンジコード1143に対する署名の検証結果として「無効」を出力し、スマートカード1101を拒絶する。数値s, tが上記範囲内にあれば、署名検証処理部1132は、
h  = t-1 mod q                (式43)
h1 = fh mod q                (式44)
h2 = sh mod q                (式45)
を計算する。そして、記憶部1122(図2の102)に格納されている定数1124から読み出した(図2の205)公開鍵aQ及び定点Qと計算したh1,h2をスカラー倍計算部1135(図2の115)へ送る(図2の206)。
【０２１４】
スカラー倍計算部1135は、定点Qとh1によるスカラー倍点h1Qと、公開鍵aQとh2によるスカラー倍点h2aQとを計算し、計算されたスカラー倍点を署名検証処理部1132へ送る(図2の207)。
【０２１５】
署名検証処理部1132は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ECDSAの署名検証であれば、点R
R=h1Q＋h2aQ                (式46)
を計算し、そのx座標をxRとしたとき、
s' = xR mod q                (式47)
を計算し、s'=sであればチャレンジコード1143に対する署名の検証結果として「有効」を出力し、スマートカード1101を認証し、受け入れる(図2の208)。
【０２１６】
s'=sでなければ「無効」を出力し、スマートカードを拒絶する(図2の208)。
【０２１７】
上記実施形態のスカラー倍計算部1115、1135は、図1のスカラー倍計算部115または135と同様の機能を備えるので、サイドチャネル攻撃を防ぐことができる、かつ処理速度やメモリ使用量をカスタマイズすることができるスカラー倍計算を実行できる。
【０２１８】
そのためスマートカード1101は署名作成処理を行う際に、コンピュータ1121は署名検証処理を行う際に、サイドチャネル攻撃を防ぐことができる、そのうえ処理速度やメモリ使用量をカスタマイズすることができる。
【０２１９】
次に本発明を鍵交換システムに適用する実施形態を説明する。本実施形態においては、図1のシステム構成が応用できる。
【０２２０】
図1のデータ処理部112、132は、本実施形態においては、それぞれ鍵交換処理部112、132として機能する。
【０２２１】
鍵交換システムのコンピュータＡ101が、入力されたデータ143から共有情報の導出を行う場合の動作について図1、図2を参照して説明する。
【０２２２】
コンピュータＢ121のデータ処理部132(図2の112)は、記憶部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の定数105から秘密鍵aを読み出しコンピュータＡ101の公開鍵aQを計算する。そして、ネットワーク142を介して、公開鍵aQをデータ141としてコンピュータＢ121に転送する。
【０２２８】
コンピュータＢ121の鍵交換処理部132(図2の112)はコンピュータＡ101の公開鍵aQの入力を受け付ける(図2の204)と、鍵交換処理部132は、記憶部122(図2の102)の定数125から読み出した(図2の205) 秘密情報125であるコンピュータＢ121の秘密鍵bと、コンピュータＡ101の公開鍵aQとをスカラー倍計算部135(図2の115)へ送る(図2の206)。
【０２２９】
スカラー倍計算部135は、秘密鍵bと、公開鍵aQによるスカラー倍点baQを計算し、計算されたスカラー倍点を鍵交換処理部132へ送る(図2の207)。
【０２３０】
鍵交換処理部132は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部122に秘密情報125として格納する。例えば、スカラー倍点baQのx座標を、共有情報とする。
【０２３１】
ここで、数abと数baは数値として同じなので、点abQと点baQは同じ点となり、同じ情報が導出されたことになる。
【０２３２】
ネットワーク142には、点aQと点bQが送信されるが、点abQ(もしくは点baQ)を計算するには秘密鍵aもしくは秘密鍵bを用いなければならない。すなわち、秘密鍵aもしくは秘密鍵bを知らなければ、共有情報を得ることができない。このようにして得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。
【０２３３】
本実施形態においても、スカラー倍計算部115、135は、上述の特徴を備えるので、サイドチャネル攻撃を防ぐことができる、そのうえ処理速度やメモリ使用量をカスタマイズすることができるような鍵交換処理が可能になる。
【０２３４】
また、上記各実施形態における暗号化処理部、復号化処理部、署名作成部、署名検証部、鍵交換処理部は、専用のハードウェアを用いて行ってもよい。また、スカラー倍計算部をコプロセッサまたはそれ以外の専用ハードウェアで実現しても良い。
【０２３５】
また、データ処理部は、上記暗号化処理、復号化処理、署名作成処理、署名検証処理、鍵交換処理のうち、任意の一つ以上の処理を行えるように構成してもよい。
【０２３６】
【発明の効果】
本発明によれば、サイドチャネル攻撃に対して安全で、かつ処理速度やメモリ使用量をカスタマイズすることができる、楕円曲線演算を用いたメッセージ処理が可能になる。
【図面の簡単な説明】
【図１】実施形態におけるシステム構成図である。
【図２】各実施形態における情報の受け渡しを示すシーケンス図である。
【図３】第1実施例の実施形態におけるスカラー倍計算部の構成図である。
【図４】第1実施例におけるエンコード部の行うエンコード方法を示すフローチャート図である。
【図５】第1実施例における前計算部の行う前計算方法を示すフローチャート図である。
【図６】第1実施例における実計算部の行う実計算方法を示すフローチャート図である。
【図７】第2実施例の実施形態におけるスカラー倍計算部の構成図である。
【図８】第2実施例における前計算部の行う前計算方法を示すフローチャート図である。
【図９】第2実施例における実計算部の行う実計算方法を示すフローチャート図である。
【図１０】第2実施例における実計算部の行う実計算方法を示すフローチャート図である。
【図１１】実施形態における署名検証システム構成図である。
【符号の説明】
101、121、1121：コンピュータ、1101：スマートカード、102、122、1102、1122：記憶部、111、131、1111、1131：処理部、115、135、1115、1135：スカラー倍計算部、112、132：データ処理部、1112：署名生成処理部、1132：署名検証処理部、104、124、1104、1124：定数、105、125、1105、1125：秘密情報、110、130、1110、1130：入出力インタフェース、108、128、1128：ディスプレイ、109、129、1129：キーボード、142：ネットワーク、1142：インタフェース、141、143：データ、302：エンコード部、303：前計算部、304：実計算部、321：剰余取得部、322：インデックス集合生成部、323：剰余選択部、324：繰り返し判定部、325：格納部、331：加算部、332：2倍算部、333：繰り返し判定部、341：ビット値判定部、342：加算部、343：2倍算部、344：繰り返し判定部、703：前計算部、704：実計算部、731：加算部、732：2倍算部、733：繰り返し判定部、734：インデックス集合生成部、742：加算部、743：2倍算部、744：繰り返し判定部、745：スカラー値表現変換部、746：ウィンドウ幅選択部。
【図１】
0004423900.tif 000002
【図２】
0004423900.tif 000003
【図３】
0004423900.tif 000004
【図４】
0004423900.tif 000005
【図５】
0004423900.tif 000006
【図６】
0004423900.tif 000007
【図７】
0004423900.tif 000008
【図８】
0004423900.tif 000009
【図９】
0004423900.tif 000010
【図１０】
0004423900.tif 000011
【図１１】
0004423900.tif 000012