(57)【特許請求の範囲】
【請求項１】
楕円曲線上の所定の点Ｇのスカラー倍算を実施する楕円曲線暗号演算装置であって、
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に前記点Ｇを乗じた基本テーブル値に対して非ゼロのテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部と、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施する演算処理部と、
前記演算処理部の演算結果に対して前記テーブル補正値に応じた所定の補正値で補正を実施する補正部と、
を有し、
前記テーブル補正値をＦとし、前記索引値を前記ウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応する前記テーブル値が、
（ｙk-1×２k-1＋ｙk-2×２k-2＋・・・＋ｙ1×２1＋ｙ0×２0）Ｇ＋Ｆ
であり、
前記所定の補正値が、
（２k*0＋２k*1＋２k*2＋・・・＋２k*(┌n/k┐-1)）Ｆ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
であり、
前記担当ビット位置がｋビット連続しており且つ前記所定のビットシフト幅がｋビットである
楕円曲線暗号演算装置。
【請求項２】
楕円曲線上の所定の点Ｇのスカラー倍算を実施する楕円曲線暗号演算装置であって、
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に前記点Ｇを乗じた基本テーブル値に対して非ゼロのテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部と、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施する演算処理部と、
前記演算処理部の演算結果に対して前記テーブル補正値に応じた所定の補正値で補正を実施する補正部と、
を有し、
前記テーブル補正値をＦとし、前記索引値を前記ウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応する前記テーブル値が、
（ｙk-1×２┌n/k┐*(k-1)＋ｙk-2×２┌n/k┐*(k-2)＋・・・＋ｙ1×２┌n/k┐*1＋ｙ0×２┌n/k┐*0）Ｇ＋Ｆ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
であり、
前記所定の補正値が、
（２┌n/k┐−１）Ｆ
であり、
前記担当ビット位置が┌n/k┐−１ビットおきであり且つ前記所定のビットシフト幅が１ビットである
楕円曲線暗号演算装置。
【請求項３】
前記演算処理部が、
変数に格納されている値に対して前記楕円曲線上における２倍演算を実施して演算結果を当該変数に格納する２倍演算部と、
前記変数に格納されている値と読み出された前記テーブル値との、前記楕円曲線上における加算演算を実施して、演算結果を当該変数に格納する加算演算部と、
制御部と、
を有し、
前記制御部が、
前記スカラー値ｄの最上位ビットから、前記ウィンドウの各ビットの担当ビット位置のビット値を読み出して索引値を生成し、当該索引値で前記テーブル格納部に格納されている前記ウィンドウテーブルを検索して第１のテーブル値を読み出して、前記変数に格納し、
前記ウィンドウを所定のビットシフト幅だけ右シフトさせると共に、前記２倍演算部に、前記所定のビットシフト幅に応じた回数分前記変数に格納されている値に対して２倍演算を実施させ、前記加算演算部に、前記スカラー値ｄから前記ウィンドウの各ビットの担当ビット位置のビット値を読み出すことにより得られる索引値で前記ウィンドウテーブルを検索して得られる第２のテーブル値について加算演算を実施させる処理を、前記スカラー値ｄの全てのビットを処理するまで繰り返し行わせる
請求項１又は２記載の楕円曲線暗号演算装置。
【請求項４】
楕円曲線上の所定の点Ｇのスカラー倍算を実施する楕円曲線暗号演算装置であって、
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に前記点Ｇを乗じた基本テーブル値に対して前記点Ｇの第２のスカラー値ｘ倍のテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部と、
前記スカラー値ｄに対して前記第２のスカラー値ｘに応じた所定の補正値で補正を実施して、第３のスカラー値ｆを生成する補正部と、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記第３のスカラー値ｆから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施する演算処理部と、
を有する楕円曲線暗号演算装置。
【請求項５】
楕円曲線上の所定の点Ｇのスカラー倍算を実施する楕円曲線暗号演算装置であって、
スカラー値ｄのブロック毎に、当該ブロックに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記ブロック中の相対ビット位置及び前記スカラー値ｄ中の当該ブロックの相対位置に対応する値についての２のべき乗との積の和に前記点Ｇを乗じた基本テーブル値に対して非ゼロのブロックテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部と、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄの各前記ブロックから読み出すことにより索引値を生成して当該索引値で各前記ブロックの前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施する演算処理部と、
を有し、
各前記ブロックについての前記ブロックテーブル補正値の総和がゼロとなっていることを特徴とする
楕円曲線暗号演算装置。
【請求項６】
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して非ゼロのテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置により実行される楕円曲線暗号演算方法であって、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施するステップと、
前記演算処理部の演算結果に対して前記テーブル補正値に応じた所定の補正値で補正を実施するステップと、
を含み、
前記テーブル補正値をＦとし、前記索引値を前記ウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応する前記テーブル値が、
（ｙk-1×２k-1＋ｙk-2×２k-2＋・・・＋ｙ1×２1＋ｙ0×２0）Ｇ＋Ｆ
であり、
前記所定の補正値が、
（２k*0＋２k*1＋２k*2＋・・・＋２k*(┌n/k┐-1)）Ｆ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
であり、
前記担当ビット位置がｋビット連続しており且つ前記所定のビットシフト幅がｋビットである
楕円曲線暗号演算方法。
【請求項７】
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して非ゼロのテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置に、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施するステップと、
前記演算処理部の演算結果に対して前記テーブル補正値に応じた所定の補正値で補正を実施するステップと、
を実行させ、
前記テーブル補正値をＦとし、前記索引値を前記ウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応する前記テーブル値が、
（ｙk-1×２k-1＋ｙk-2×２k-2＋・・・＋ｙ1×２1＋ｙ0×２0）Ｇ＋Ｆ
であり、
前記所定の補正値が、
（２k*0＋２k*1＋２k*2＋・・・＋２k*(┌n/k┐-1)）Ｆ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
であり、
前記担当ビット位置がｋビット連続しており且つ前記所定のビットシフト幅がｋビットである
楕円曲線暗号演算プログラム。
【請求項８】
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して非ゼロのテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置により実行される楕円曲線暗号演算方法であって、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施するステップと、
前記演算処理部の演算結果に対して前記テーブル補正値に応じた所定の補正値で補正を実施するステップと、
を含み、
前記テーブル補正値をＦとし、前記索引値を前記ウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応する前記テーブル値が、
（ｙk-1×２┌n/k┐*(k-1)＋ｙk-2×２┌n/k┐*(k-2)＋・・・＋ｙ1×２┌n/k┐*1＋ｙ0×２┌n/k┐*0）Ｇ＋Ｆ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
であり、
前記所定の補正値が、
（２┌n/k┐−１）Ｆ
であり、
前記担当ビット位置が┌n/k┐−１ビットおきであり且つ前記所定のビットシフト幅が１ビットである
楕円曲線暗号演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、楕円曲線暗号技術に関する。
【背景技術】
【０００２】
情報化社会の発展に伴い、電子決済、住民基本台帳ネットワークなどの情報ネットワークを利用したサービスが普及すると予想される。これらのサービスを安全に運用するためには情報セキュリティ技術が必須であり、情報セキュリティの基盤技術として公開鍵暗号技術が用いられる。公開鍵暗号技術には様々な方式が知られているが、その中の主要な方式として楕円曲線暗号が知られている。公開鍵暗号技術を用いることで、暗号、デジタル署名又は認証機能といったサービスを実現し、個人情報に対する第三者からの不正なアクセスを防止することができる。
【０００３】
また、電子決済、住民基本台帳ネットワークなどのサービスにおけるエンドユーザ側のデバイスとして、スマートカードが知られている。スマートカードはＩＣ（Integrated Circuit）チップを搭載したカードであり、チップ内部のメモリ領域にユーザの秘密情報を格納している。スマートカードのＩＣチップには暗号、デジタル署名又は認証機能を搭載しており、これらの機能のための処理を実施する際には、ユーザの秘密情報が鍵として用いられる。ユーザの秘密情報はカード内部のメモリ領域に格納されるため、第三者からの不正な覗き見に対する安全性（耐タンパ性）が磁気記録型のカードに比べて飛躍的に向上すると考えられている。
【０００４】
しかし、１９９８年に電力解析攻撃（ＰＡ：Power Analysis。以下、ＰＡと呼ぶ）と呼ばれる解析方法が発見されたことで、スマートカードの耐タンパ性に対する脆弱性が認識されるようになった。スマートカードは、ユーザの秘密情報を鍵として用いて暗号処理を実施しているが、ＰＡは、暗号処理中のスマートカードの消費電力を測定し、測定されたデータを用いることでユーザの秘密情報を推定且つ解析するものである。
【０００５】
ＰＡは強力な解析法として知られており、ＰＡの防止策についての必要性については、各種国際標準に記載されている。例えば、セキュリティの国際標準であるＩＳＯ１５４０８のスマートカード向けプロテクションプロファイル（ＰＰ：Protection Profile）ではＰＡへの対策が必須とされている。さらに、この攻撃は電力を観察する攻撃であるため、攻撃対象はスマートカードに限定されない。ＰＤＡ（Personal Digital Assistant）デバイスに対して、電力消費時に発生する電磁波を測定するＰＡも知られており、ＰＡは電力を消費する組み込み機器全般が攻撃対象となる。
【０００６】
以下、公開鍵暗号技術の中で、楕円曲線暗号方式について基本的事項を説明すると共に、どのようにＰＡが実施されるかについて説明する。
【０００７】
［楕円曲線暗号］
楕円曲線暗号は、図１に示されるような楕円曲線における有理点の演算を用いた暗号である。楕円曲線には、素体と２べきの２種類が存在する。それぞれ、２つのパラメータであるａとｂとを用いて、以下の関係式のように表現可能である。
素体：ｙ2＝ｘ3＋ａｘ＋ｂ （mod ｐ）（ｘ，ｙ，ａ，ｂ∈ＧＦ(p)，ｐ：素体）
２べき：ｙ2＋ｙｘ＝ｘ3＋ａｘ2＋ｂ （mod ｆ(x)）（ｘ，ｙ，ａ，ｂ∈ＧＦ(2m)，ｆ(x)：ｍ次既約多項式）
【０００８】
以下では、素体の楕円曲線を対象に説明を行うが、以下の議論は２べきの楕円曲線に対しても同様に適用できる。
【０００９】
楕円曲線における有理点とは、楕円曲線の関係式を満たす（ｘ，ｙ）の集合である。楕円曲線では、任意の点に対し、「点の加算」と「点の２倍算」という２種類の演算が定義される。点は、二次元ベクトル（ｘ，ｙ）による表現（affine表現）と，三次元ベクトル（Ｘ，Ｙ，Ｚ）による表現（射影座標、Jacobian座標）によって表される。
【００１０】
図２は、２つの楕円曲線上の点Ｐ及びＱの加算を表している。点Ｐと点Ｑを加算した点Ｒは、以下のように定義される。すなわち、ＰとＱを結ぶ直線と楕円曲線の交点から垂線を引き、その垂線と楕円曲線の交点がＲと定義される。楕円曲線における点の加算では、一般的な整数の加算と同様に、交換則（Ａ＋Ｂ＝Ｂ＋Ａ）が成立する。３次元ベクトル表現において、点の加算を行う場合、２点のうちどちらかの点のＺ座標が１の場合、加算の高速化を実現可能となる。また、点の減算については、Ｐ＝Ｒ−Ｑとすることで、同様に定義される。すなわち、点Ｒから垂線を引き、その垂線と楕円曲線の交点と点Ｑを結ぶ直線を引く。その直線と楕円曲線の交点が点Ｐとなる。
【００１１】
Jacobian座標を用いた場合における点の加算の演算手順は、よく知られている。図３に詳細を示すが、素体における点Ａと点Ｂの加算Ｒ＝ＥＣＡＤＤ（Ａ，Ｂ）＝Ａ＋Ｂのためにステップ８００乃至８３５が必要であることが分かる。なお、ＥＣＤＢＬ（Ａ）＝Ａ＋Ａである。詳細な説明は省略するが、一般的に、点の加算、点の減算は、整数の加算や減算に比べると、時間のかかる演算であることが分かる。
【００１２】
また、図４は、楕円曲線上の点Ｐの２倍算を表している。点Ｐの２倍算は以下のように定義される。すなわち、楕円曲線上の点Ｐから接線を引き、その接線と楕円曲線の交点から垂線を引き、その垂線と楕円曲線の交点が２倍算の結果Ｒと定義される。
【００１３】
図５（ａ）及び（ｂ）は、マイナス点と無限遠点を表している。図５（ａ）に示すように、楕円曲線上の点Ｐのマイナス点「−Ｐ」は、点Ｐから垂線を引き、その垂線と楕円曲線の交点と定義される。また、図５（ｂ）に示すように、無限遠点は、点Ｐと点−Ｐを結ぶ直線と楕円曲線の交点と定義される。無限遠点Ｏは、一般的な整数の加算におけるゼロと同様の性質を持ち、Ａ＋Ｏ＝Ｏ＋Ａ＝Ａ，２Ｏ＝Ｏが成立する。
【００１４】
さらに、楕円曲線暗号では、点のスカラー倍算（Elliptic Scalar Multiplication）と呼ばれる処理を用いた演算が行われる。点のスカラー倍算は、楕円曲線上の点Ａ、スカラー値と呼ばれる整数ｘから、
Ｖ＝ｘＡ
を満たす楕円曲線上の点Ｖを計算する処理であり、ｘを秘密情報とした処理が行われる。図１、図２、図４及び図５（ａ）及び（ｂ）と同様な形で図示すると、点Ａのスカラーｄ倍は、図６のように示される。より具体的には、点のスカラー倍算は、上で述べた点の加算及び２倍算を基にして行われる。ＥＣＤＨ（Elliptic Curve Diffie Hellman）鍵交換の場合、通信相手の公開鍵となる楕円曲線上の点をＡ、個人鍵をｄとすると、
Ｖ＝ｄＡ
を満たす楕円曲線上の点Ｖを計算することで、安全な鍵共有を実現する。個人鍵ｄの値を知らない第三者は正しい共有鍵の値を算出することができない。ここでは、ｄが個人の秘密鍵であり、攻撃者などの不正な第三者に漏洩してはならない値である。すなわち、ｄの値の保護が重要な耐タンパ機能となる。数学的には、ｄ以外の値（すなわちＡ及びＶ）が既知だとしても、ｄを計算する計算量が大きすぎるため、現実的な時間内にｄを求めることが難しい問題として知られている（すなわち、楕円曲線上の離散対数問題。）。すなわち、楕円曲線パラメータ（Elliptic Curve Parameter）が１６０ビット以上の場合、ＡやＶの値を知っていたとしても、ｄの値を求めることが困難となる。
【００１５】
このように、数学的に求めることが困難な個人鍵ｄであるが、上で述べたＰＡを用いることで容易に解読することができることが知られている。ＰＡの基本メカニズムは、点のスカラー倍算の処理手順と大きな関連があり、ＰＡを用いることで、ｄを１ビット単位で解読できることが知られている。
【００１６】
楕円曲線上の点Ａのｄ倍点Ｖ（＝ｄＡ）は、上でも述べたように点の加算と２倍算を用いて算出される。このような演算手法は、楕円曲線上の演算に限らず、様々な場面で用いられる。具体的には、よく知られているバイナリ法、Window法、櫛型Window法などが挙げられる。以下では、Window法及び櫛型Window法を用いた点のスカラー倍算を説明する。
【００１７】
図７に、Window法を用いた、点のスカラー倍算のアルゴリズムを示す。ここでは、楕円曲線上の点Ｇ、スカラー値をｄ（例として１２ビット幅）として、Ａ＝ｄＧを求めるものとする。例として、Window法のWindow幅を３ビットとし、Windowテーブルの要素数を２3＝８個とする。具体的には、索引「０００」に対応付けて０Ｇ＝Ｏ（ゼロ点）を設定し、索引「００１」に対応付けて２0Ｇを設定し、索引「０１０」に対応付けて２1Ｇを設定し、索引「０１１」に対応付けて２1Ｇ＋２0Ｇを設定し、索引「１００」に対応付けて２2Ｇを設定し、索引「１０１」に対応付けて２2Ｇ＋２0Ｇを設定し、索引「１１０」に対応付けて２2Ｇ＋２1Ｇを設定し、索引「１１１」に対応付けて２2Ｇ＋２1Ｇ＋２0Ｇを設定するようになっている。
【００１８】
このようなWindowテーブルを用いた具体的な演算手順は以下のとおりである。最初に、手順（１）において、ｄの上位３ビットを索引として、Windowテーブルのテーブル値を読み出す。これを変数Ａに代入する。すなわち、（１）Ａ＝Ｔａｂ［ｄ11，ｄ10，ｄ9］（Ｔａｂ［ｘ］は、［ｘ］で指定されたテーブル値を表す）。
【００１９】
次に、手順（２）において、Windowのシフト幅である３ビットに応じて、２3Ａを算出する。すなわち、（２）Ａ＝２3Ａ。また、手順（３）において、ｄの次の３ビットを索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（３）Ａ＝Ａ＋Ｔａｂ［ｄ8，ｄ7，ｄ6］。さらに、手順（４）において、Windowのシフト幅である３ビットに応じて、２3Ａを算出する。すなわち、（４）Ａ＝２3Ａ。また、手順（５）において、ｄの次の３ビットを索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋Ｔａｂ［ｄ5，ｄ4，ｄ3］。
【００２０】
さらに、手順（６）において、Windowのシフト幅である３ビットに応じて、２3Ａを算出する。すなわち、（６）Ａ＝２3Ａ。最後に、手順（７）において、ｄの次の３ビットを索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（７）Ａ＝Ａ＋Ｔａｂ［ｄ2，ｄ1，ｄ0］＝ｄＧ。
【００２１】
図８に、ｄ＝(101011101001)2とした場合の具体例を図示する。なお、Windowテーブルは同じである。まず、手順（１）において、ｄの上位３ビット「１０１」を索引として、Windowテーブルのテーブル値を読み出す。これを変数Ａに代入する。すなわち、（１）Ａ＝Ｔａｂ［１０１］＝（２2＋２0）Ｇ。
【００２２】
次に、手順（２）において、Window幅である３ビットに応じて、２3Ａを算出する。すなわち、（２）Ａ＝２3Ａ＝（２5＋２3）Ｇ。また、手順（３）において、ｄの次の３ビット「０１１」を索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（３）Ａ＝Ａ＋Ｔａｂ［０１１］＝（２5＋２3＋２1＋２0）Ｇ。さらに、手順（４）において、Windowのシフト幅である３ビットに応じて、２3Ａを算出する。すなわち、（４）Ａ＝２3Ａ＝（２8＋２6＋２4＋２3）Ｇ。
【００２３】
また、手順（５）において、ｄの次の３ビット「１０１」を索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋Ｔａｂ［１０１］＝（２8＋２6＋２4＋２3＋２2＋２0）Ｇ。さらに、手順（６）において、Windowのシフト幅である３ビットに応じて、２3Ａを算出する。すなわち、（６）Ａ＝２3Ａ＝（２11＋２9＋２7＋２6＋２5＋２3）Ｇ。最後に、手順（７）において、ｄの次の３ビット「００１」を索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（７）Ａ＝Ａ＋Ｔａｂ［００１］＝（２11＋２9＋２7＋２6＋２5＋２3＋２0）Ｇ＝ｄＧ。
【００２４】
次に、図９を用いて櫛形Window法を用いた点のスカラー倍算を説明する。櫛形Window法では、その名前のとおり、櫛形にWindowテーブルを設定する。すなわち、通常のWindow法では、索引「１１１」に対応付けられているテーブル値が「（２2＋２1＋２0）Ｇ」のように連続する値であったが、櫛形Window法では、とびとびの値がWindowテーブルに登録されている。具体的には、索引「０００」に対応付けて０Ｇ＝Ｏ（ゼロ点）を設定し、索引「００１」に対応付けて２0Ｇを設定し、索引「０１０」に対応付けて２4Ｇを設定し、索引「０１１」に対応付けて２4Ｇ＋２0を設定し、索引「１００」に対応付けて２8Ｇを設定し、索引「１０１」に対応付けて２8＋２0Ｇを設定し、索引「１１０」に対応付けて２8＋２4を設定し、索引「１１１」に対応付けて２8＋２4＋２0を設定するようになっている。
【００２５】
このようなWindowテーブルを用いた具体的な演算手順は以下のとおりである。なお、Window法では、２3倍算を行う必要があるが、櫛形Window法では２倍算ですむ利点がある。これにより点のスカラー倍算全体における点の２倍算の回数が１／３となる。一般に、Window幅がｋビットの櫛型Window法では、２倍算の回数が１／ｋに削減できる。
【００２６】
まず、手順（１）において、３ビットおきにｄにおける３ビットを索引値として用いて、Windowテーブルのテーブル値を読み出す。これを変数Ａに代入する。すなわち、（１）Ａ＝Ｔａｂ［ｄ11，ｄ7，ｄ3］。  次に、手順（２）において、Windowのシフト幅１ビットに応じて、２Ａを算出する。すなわち、（２）Ａ＝２Ａ。また、手順（３）において、ｄにおいて手順（１）の状態からwindowを１ビット右シフトさせて得られる次の３ビットを索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（３）Ａ＝Ａ＋Ｔａｂ［ｄ10，ｄ6，ｄ2］。さらに、手順（４）において、Windowのシフト幅１ビットに応じて、２Ａを算出する。すなわち、（４）Ａ＝２Ａ。
【００２７】
また、手順（５）において、ｄにおいて手順（３）の状態からwindowを１ビット右シフトさせて得られる次の３ビットを索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋Ｔａｂ［ｄ9，ｄ5，ｄ1］。さらに、手順（６）において、Windowのシフト幅１ビットに応じて、２Ａを算出する。すなわち、（６）Ａ＝２Ａ。最後に、手順（７）において、ｄにおいて手順（５）の状態からwindowを１ビット右シフトさせて得られる次の３ビットを索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（７）Ａ＝Ａ＋Ｔａｂ［ｄ8，ｄ4，ｄ0］＝ｄＧ。
【００２８】
図１０に、ｄ＝(101011101001)2とした場合の具体例を図示する。なお、Windowテーブルは同じである。
【００２９】
まず、手順（１）において、最上位から３ビットおきにｄから得られる３ビット「１１１」を索引として、Windowテーブルのテーブル値を読み出す。これを変数Ａに代入する。すなわち、（１）Ａ＝Ｔａｂ［１１１］＝（２8＋２4＋２0）Ｇ。
【００３０】
次に、手順（２）において、Windowのシフト幅１ビットに応じて、２Ａを算出する。すなわち、（２）Ａ＝２Ａ＝（２9＋２5＋２1）Ｇ。また、手順（３）において、手順（１）から１ビット右シフトさせてｄから得られる次の３ビット「０１０」を索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（３）Ａ＝Ａ＋Ｔａｂ［０１０］＝（２9＋２5＋２4＋２1）Ｇ。さらに、手順（４）において、Windowのシフト幅１ビットに応じて、２Ａを算出する。すなわち、（４）Ａ＝２Ａ＝（２10＋２6＋２5＋２2）Ｇ。
【００３１】
また、手順（５）において、手順（３）から１ビット右シフトさせてｄから得られる次の３ビット「１１０」を索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋Ｔａｂ［１１０］＝（２10＋２8＋２6＋２5＋２4＋２2）Ｇ。さらに、手順（６）において、Windowのシフト幅１ビットに応じて、２Ａを算出する。すなわち、（６）Ａ＝２Ａ＝（２11＋２9＋２7＋２6＋２5＋２3）Ｇ。最後に、手順（７）において、手順（５）から１ビット右シフトさせてｄから得られる次の３ビット「００１」を索引として、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（７）Ａ＝Ａ＋Ｔａｂ［００１］＝（２11＋２9＋２7＋２6＋２5＋２3＋２0）Ｇ＝ｄＧ。このように図８と同じ結果が得られる。
【００３２】
上で述べた櫛型Window法では、Windowテーブルを１個用いる例を示した。ここでWindowテーブルを２個用いて記憶テーブルの領域を増大させる代わりに、２倍算の回数をさらに減少させて高速化を図る方式も存在する。このような櫛型Window法について図１１Ａ及び図１１Ｂを用いて説明する。
【００３３】
このような櫛形Window法では、ｄの上位半分のビットブロックのための上側テーブルと、ｄの下位半分のビットブロックのための下側テーブルとを用意する。以下では、ｄが１８ビットの例を示す。具体的には、上側テーブルには、索引「０００」に対応付けて０Ｇ＝Ｏ（ゼロ点）を設定し、索引「００１」に対応付けて２9Ｇを設定し、索引「０１０」に対応付けて２12Ｇを設定し、索引「０１１」に対応付けて２12Ｇ＋２9を設定し、索引「１００」に対応付けて２15Ｇを設定し、索引「１０１」に対応付けて２15＋２9Ｇを設定し、索引「１１０」に対応付けて２15＋２12を設定し、索引「１１１」に対応付けて２15＋２12＋２9を設定するようになっている。
【００３４】
一方、下側テーブルには、索引「０００」に対応付けて０Ｇ＝Ｏ（ゼロ点）を設定し、索引「００１」に対応付けて２0Ｇを設定し、索引「０１０」に対応付けて２3Ｇを設定し、索引「０１１」に対応付けて２3Ｇ＋２0を設定し、索引「１００」に対応付けて２6Ｇを設定し、索引「１０１」に対応付けて２6＋２0Ｇを設定し、索引「１１０」に対応付けて２6＋２3を設定し、索引「１１１」に対応付けて２6＋２3＋２0を設定するようになっている。
【００３５】
このようなWindowテーブルを用いた具体的な演算手順は以下のとおりである。最初に、手順（１）において、ｄの上位半分のビットブロックのうち２ビット間隔で３ビットを索引として抽出し、上側テーブルの該当するテーブル値を読み出す。これを変数Ａに代入する。すなわち、（１）Ａ＝ＴａｂH［ｄ17，ｄ14，ｄ11］。ＴａｂHについては、上側テーブルのテーブル値を表す。次に、手順（２）において、ｄの下位半分のビットブロックのうち２ビット間隔で３ビットを索引として抽出し、下側テーブルの該当するテーブル値を読み出し、Ａに加算する。すなわち、（２）Ａ＝Ａ＋ＴａｂL［ｄ8，ｄ5，ｄ2］。ＴａｂLについては、下側テーブルのテーブル値を表す。
【００３６】
そして、Windowのシフト幅１ビットに応じて、２Ａを算出する。すなわち、（３）Ａ＝２Ａ。また、手順（４）において、手順（１）の状態からwindowを１ビット右シフトさせて上位半分のビットブロックの次の３ビットを索引として抽出し、上側テーブルのテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋ＴａｂH［ｄ16，ｄ13，ｄ10］。また、手順（５）において、手順（２）の状態からwindowを１ビット右シフトさせて下位半分のビットブロックの次の３ビットを索引として抽出し、下側テーブルのテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋ＴａｂL［ｄ7，ｄ4，ｄ1］。さらに、手順（６）において、Windowのシフト幅１ビットに応じて、２Ａを算出する。すなわち、（６）Ａ＝２Ａ。
【００３７】
また、手順（７）において、手順（４）の状態からwindowを１ビット右シフトさせて上位半分の次の３ビットを索引として抽出し、上側テーブルのテーブル値を読み出し、Ａに加算する。すなわち、（７）Ａ＝Ａ＋ＴａｂH［ｄ15，ｄ12，ｄ9］。また、手順（８）において、手順（５）の状態からwindowを１ビット右シフトさせて下位半分のビットブロックの次の３ビットを索引として抽出し、下側テーブルのテーブル値を読み出し、Ａに加算する。すなわち、（８）Ａ＝Ａ＋ＴａｂL［ｄ6，ｄ3，ｄ0］＝ｄＧ。
【００３８】
このように、図９からｄのビット長が長くなったが、図９に示した３ビット幅からあたかも６ビット幅へ長くなったWindowテーブルを用いているので、２倍算の回数も削減されている。
【００３９】
上で述べたWindow法や櫛型Window法では、Windowテーブルの索引値が「０００」の場合、テーブル値がＯ（無限遠点）となる。スカラー倍算を実行しているデバイスの消費電力を測定すると、模式的には図１２（ａ）及び（ｂ）に示すようになる。すなわち、索引値が非０の場合（Ｃ＝Ａ＋Ｂ）には図１２（ａ）のような波形が得られ、０の場合（Ｃ＝Ａ＋Ｏ）には図１２（ｂ）のような波形が得られる。このように、明らかに異なった波形が得られる。これはＯ点との加算時には、特殊な演算処理を実行するためである。従って、消費電力波形より、秘密情報であるｄの部分的なビット値が０であるという情報が漏洩することになる。
【００４０】
このようなｄの部分的なビット値「０」を用いることで、秘密鍵ｄの全ビットを解読する数学的なアルゴリズムも知られている。また、スカラー倍算を署名生成に用いる場合、署名用の秘密鍵が漏洩するという問題も知られている。
【００４１】
このため、Ａ＝ｄＧを計算する際に、秘密情報であるｄの値を１ビットたりとも漏洩させないことが非常に重要である。
【００４２】
点のスカラー倍算を用いた楕円曲線暗号の代表的な処理として、ＥＣＤＳＡ（Elliptic Curve Digital Signature Algorithm）を用いた署名生成処理が知られている。この処理のアルゴリズムを、図１３に示す。この処理は、署名用の個人鍵ｓ及び署名対象データｈiを入力とし、一時的な乱数ｄiを生成し、点のスカラー倍算ｄiＧ（但し、Ｇはベースポイントと呼ばれる公開された点）を含む演算処理を行うことで、ｈi、署名データ（ｕi，ｖi）を出力する処理である。ただし、ｉは署名生成処理の処理回数を表す変数である。なお、ｒは、公開された素数値であり、ｄi-1は、ｄi-1×ｄi＝１ （mod r）を満たすような整数値である。
【００４３】
ＥＣＤＳＡ署名をスマートカードなどの装置に実装する場合、署名用の個人鍵ｓと一時的な乱数ｄiは外部から観察できない値である。特に、署名用の個人鍵ｓは重要な情報資産であり、厳重に保護する必要がある。しかし、Howgrave-Grahamらによる攻撃手法を用いることで、図１４に示すように、一時的な乱数ｄiの上位又は下位の数ビットのデータを攻撃者が多数集めることに成功した場合、この集めたデータと外部に対する出力データｈi及び（ｕi，ｖi）を組み合わせることで、署名用の個人鍵ｓを解読できる。
【００４４】
ｄiの値は通常は外部から観察されない値であるが、もしＳＰＡ（simple PA。単純な電力消費波形の解析。）による攻撃能力を有する攻撃者が、点のスカラー倍算ｄiＧの演算時にＳＰＡを用いた場合、ｄiの最上位又は最下位数ビットを解読することが可能である。この結果をHowgrave-Grahamらによる攻撃手法と組み合わせることで、攻撃者は個人鍵ｓを解読することができる。この攻撃の組み合わせを考慮すると、ｄiＧの演算にＳＰＡを適用した場合でも、ｄiに関する情報を１ビットも漏洩しないことがセキュリティ上必須である。
【００４５】
秘密情報であるｄの値を漏洩させないためには、索引値が非０の場合（Ｃ＝Ａ＋Ｂ）と、０の場合（Ｃ＝Ａ＋Ｏ）で、消費電力波形を同一にし、攻撃者に区別させない手法が考えられる。従来から知られている技術として、Coronらによって提案されたダミー演算法がある。図１５に、櫛型Window法におけるダミー演算法の概略を示す。基本的な動作は図９を用いて説明したとおりであるが、ダミー演算法では、手順（１）を除き、ｄから該当する索引値を決定すると、「０００」であるか否かを確認する処理を実施する。テーブルの索引値が「０００」の場合、計算結果を格納する本来の変数Ａではなく、ダミー用の変数Ｂに、非０のテーブル値を加算する。図１５の例では、手順（３）、（５）及び（７）において、索引値が「０００」であれば、ダミー用変数Ｂに、索引値が例えば「００１」（「０００」以外の他の値でも良い）のテーブル値とＡを加算した結果を格納する。このようにすることで、ダミー演算法では、索引値が「０００」の場合の消費電力波形を、非０の場合と同一にすることができ、秘密情報ｄの漏洩を防ぐことができる。
【００４６】
ダミー演算法では、何の対策も施さない場合と比較し、ＰＡに対して安全となり且つ計算量は増加しない。しかし、ダミー用の変数Ｂを必要とする。なぜなら、ダミー演算は変数Ａに格納されている中間データを破壊しないように実行する必要があるため、変数Ｂは変数Ａと別の記憶領域とする必要があるからである。よって、ＳＰＡ対策を施さない場合には、変数Ａのみを格納する記憶領域（ＲＡＭ：Random Access Memory）を必要としたのに対し、ダミー演算法では、変数Ａと変数Ｂを格納するＲＡＭが必要となる。すなわち、必要とするＲＡＭが２倍となってしまう。スマートカードのような実装形態において、ＲＡＭ資源はＲＯＭ資源に比べて容量が限られており、これを削減することは非常に重要な課題である。
【先行技術文献】
【非特許文献】
【００４７】
【非特許文献１】IEEE P1363/D13 (Draft Version 13, November 12, 1999) main document, Standard Specifications for Public Key Cryptography
【非特許文献２】P.Kocher, J,Jaffe and B.Jun "Differential Power Anaysis", Crypto'99, LNCS 1666, pp.388-397, Springer-Verlag, 1999.
【非特許文献３】Catherine H. Gebotys, Simon Ho, and C.C. Tiu, “EM Analysis of Rijndael and ECC on a Wireless Java-Based PDA”, Cryptographic Hardware and Embedded System, CHES 2005, pp.250-264, LNCS 3659.
【非特許文献４】N.A.Howgrave-Graham and N.P.Smart, “Lattice Attacks on Digital Signature Schemes”, Designs, Codes and Cryptography, vol.23, Issue3, 2001, pp.283-290.
【非特許文献５】IEEE 1363-2000: Standard Specifications For Public Key Cryptography
【発明の概要】
【発明が解決しようとする課題】
【００４８】
上で述べたように、スマートカードやＰＤＡといった小型機器のように使用できるハードウェア・リソースが限られている場合に、ＰＡ対策を行いつつ、ＲＡＭの記憶領域の使用を抑えることはできなかった。
【００４９】
従って、本技術の目的は、ＳＰＡに対する耐タンパ性を保持しつつ、メモリ特にＲＡＭの使用量を削減するための技術を提供することである。
【課題を解決するための手段】
【００５０】
第１の態様に係る楕円曲線暗号演算装置は、楕円曲線上の所定の点Ｇのスカラー倍算を実施する楕円曲線暗号演算装置であって、（Ａ）ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当するスカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に点Ｇを乗じた基本テーブル値に対して非ゼロのテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部と、（Ｂ）ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値をスカラー値ｄから読み出すことにより索引値を生成して当該索引値でウィンドウテーブルを検索してテーブル値を読み出し、読み出したテーブル値を用いて２倍演算及び加算演算を実施する演算処理部と、（Ｃ）演算処理部の演算結果に対してテーブル補正値に応じた所定の補正値で補正を実施する補正部とを有する。
【００５１】
第２の態様に係る楕円曲線暗号演算装置は、（Ａ）ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当するスカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に点Ｇを乗じた基本テーブル値に対して点Ｇの第２のスカラー値ｘ倍のテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部と、（Ｂ）スカラー値ｄに対して第２のスカラー値ｘに応じた所定の補正値で補正を実施して、第３のスカラー値ｆを生成する補正部と、（Ｃ）ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を第３のスカラー値ｆから読み出すことにより索引値を生成して当該索引値でウィンドウテーブルを検索してテーブル値を読み出し、読み出したテーブル値を用いて２倍演算及び加算演算を実施する演算処理部とを有する。
【００５２】
第３の態様に係る楕円曲線暗号演算装置は、（Ａ）ｎ（ｎは２以上の整数）ビットのスカラー値ｄのブロック毎に、当該ブロックに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当するブロック中の相対ビット位置及び前記スカラー値ｄ中の当該ブロックの相対位置に対応する値についての２のべき乗との積の和に前記点Ｇを乗じた基本テーブル値に対して非ゼロのブロックテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部と、（Ｂ）ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値をスカラー値ｄの各ブロックから読み出すことにより索引値を生成して当該索引値で各ブロックのウィンドウテーブルを検索してテーブル値を読み出し、読み出したテーブル値を用いて２倍演算及び加算演算を実施する演算処理部とを有する。そして、各ブロックについてのブロックテーブル補正値の総和がゼロとなっている。
【発明の効果】
【００５３】
ＳＰＡに対する耐タンパ性を保持しつつ、処理速度の低下を抑え且つメモリ特にＲＡＭの使用量を削減できるようになる。
【図面の簡単な説明】
【００５４】
【図１】図１は、楕円曲線を説明するための図である。
【図２】図２は、楕円曲線上の加算を説明するための図である。
【図３】図３は、楕円曲線上の加算演算の具体的アルゴリズムを表す図である。
【図４】図４は、楕円曲線上の２倍算を説明するための図である。
【図５】図５（ａ）は、楕円曲線上のマイナス点を説明するための図であり、図５（ｂ）は、無限遠点を説明するための図である。
【図６】図６は、楕円曲線上の点のスカラー倍を説明するための図である。
【図７】図７は、Ｗｉｎｄｏｗ法による点のスカラー倍算のアルゴリズムの概要を説明するための図である。
【図８】図８は、Ｗｉｎｄｏｗ法による点のスカラー倍算の具体例を説明するための図である。
【図９】図９は、櫛形Ｗｉｎｄｏｗ法による点のスカラー倍算のアルゴリズムの概要を説明するための図である。
【図１０】図１０は、櫛形Ｗｉｎｄｏｗ法による点のスカラー倍算の具体例を説明するための図である。
【図１１Ａ】図１１Ａは、Windowテーブルを２つ用いる櫛形Ｗｉｎｄｏｗ法による点のスカラー倍算のアルゴリズムを説明するための図である。
【図１１Ｂ】図１１Ｂは、Windowテーブルを２つ用いる櫛形Ｗｉｎｄｏｗ法による点のスカラー倍算のアルゴリズムを説明するための図である。
【図１２】図１２（ａ）は、索引値が非ゼロの場合の消費電力波形を表す図であり、図１２（ｂ）は、索引値がゼロの場合の消費電力波形を表す図である。
【図１３】図１３は、署名生成処理のアルゴリズムの一例を示す図である。
【図１４】図１４は、署名生成処理からビット値を盗み出す例を説明するための図である。
【図１５】図１５は、従来技術であるダミー演算法を説明するための図である。
【図１６】図１６は、楕円曲線暗号演算装置の一例であるスマートカードを示す図である。
【図１７】図１７は、実施の形態１−Ａに係る楕円曲線暗号演算装置の構成例を示す図である。
【図１８Ａ】図１８Ａは、実施の形態１−ＡにおけるWindowテーブルの具体例を示す図である。
【図１８Ｂ】図１８Ｂは、実施の形態１−Ａにおける演算処理の具体例を示す図である。
【図１９】図１９は、実施の形態１−Ａにおける一般化したWindowテーブルを示す図である。
【図２０】図２０は、実施の形態１−Ａにおける処理フローを示す図である。
【図２１】図２１は、実施の形態１−Ｂに係る楕円曲線暗号演算装置の構成例を示す図である。
【図２２】図２２は、実施の形態１−Ｂにおける処理フローを示す図である。
【図２３】図２３は、実施の形態２−Ａに係る楕円曲線暗号演算装置の構成例を示す図である。
【図２４Ａ】図２４Ａは、実施の形態２−ＡにおけるWindowテーブルの具体例を示す図である。
【図２４Ｂ】図２４Ｂは、実施の形態２−Ａにおける演算処理の具体例を示す図である。
【図２５】図２５は、実施の形態２−Ａにおける一般化したWindowテーブルを示す図である。
【図２６】図２６は、実施の形態２−Ａにおける処理フローを示す図である。
【図２７】図２７は、実施の形態２−Ｂに係る楕円曲線暗号演算装置の構成例を示す図である。
【図２８】図２８は、実施の形態２−Ｂにおける処理フローを示す図である。
【図２９】図２９は、実施の形態３に係る楕円曲線暗号演算装置の構成例を示す図である。
【図３０Ａ】図３０Ａは、実施の形態３におけるWindowテーブルの具体例を示す図である。
【図３０Ｂ】図３０Ｂは、実施の形態３における演算処理の具体例を示す図である。
【図３１】図３１は、実施の形態３における一般化したWindowテーブルを示す図である。
【図３２】図３２は、実施の形態３における処理フローを示す図である。
【図３３】図３３は、実施の形態４に係る楕円曲線暗号演算装置の構成例を示す図である。
【図３４Ａ】図３４Ａは、実施の形態４におけるWindowテーブルの具体例を示す図である。
【図３４Ｂ】図３４Ｂは、実施の形態４における演算処理の具体例を示す図である。
【図３５】図３５は、実施の形態４における一般化したWindowテーブルを示す図である。
【図３６】図３６は、実施の形態４における処理フローを示す図である。
【図３７】図３７は、実施の形態５に係る楕円曲線暗号演算装置の構成例を示す図である。
【図３８Ａ】図３８Ａは、実施の形態５におけるWindowテーブルの具体例を示す図である。
【図３８Ｂ】図３８Ｂは、実施の形態５における演算処理の具体例を示す図である。
【図３９】図３９は、実施の形態５における一般化したWindowテーブルを示す図である。
【図４０】図４０は、実施の形態５における一般化したWindowテーブルを示す図である。
【図４１】図４１は、実施の形態５における処理フローを示す図である。
【図４２】図４２は、実施の形態６に係る楕円曲線暗号演算装置の構成例を示す図である。
【図４３】図４３は、実施の形態６における処理フローを示す図である。
【図４４】図４４は、楕円曲線暗号演算装置の構成例を示す図である。
【図４５】図４５は、楕円曲線暗号演算装置の構成例を示す図である。
【発明を実施するための形態】
【００５５】
本技術の実施の形態に係る楕円曲線暗号演算装置１００は、図１６に示すように、例えばスマートカードとして実施される。また、携帯電話機、ＰＤＡその他の小型機器、場合によってはパーソナルコンピュータその他の機器として実施するようにしても良い。
【００５６】
［実施の形態１−Ａ］
本実施の形態に係る楕円曲線暗号演算装置１００の装置構成例を図１７に示す。楕円曲線暗号演算装置１００では、バス１に、ＣＰＵ（Central Processing Unit）３と、演算器５と、ＲＯＭ７と、ＲＡＭ９と、通信部１１とが接続されている。ＲＯＭ７は、以下で説明する処理をＣＰＵ３に実行させるための演算プログラム７１と、以下で述べる補正点データ７３と、通常のWindow法のWindowテーブルをベースとしたものであって以下で述べるWindowテーブル７５とが記録されている。演算器５は、従来から知られている楕円曲線上の点の加算ＥＣＡＤＤ（Ａ，Ｂ）を演算する加算演算部５１と、従来から知られている楕円曲線上の点の２倍演算ＥＣＤＢＬ（Ａ）を実施する２倍演算部５３とを有する。また、演算プログラム７１をＣＰＵ３が実行すると、制御部３１及び以下で述べるような演算結果の補正処理を実施する補正部３３が実現される。また、外部装置との通信を行うため通信部１１を設ける例を示しているが、他の機能を実現するための装置が設けられる場合もある。ＲＡＭ９は、ＣＰＵ３が各種処理を実施する際に用いるデータを格納するものであり、本実施の形態では、楕円曲線におけるベースポイントＧのスカラー値ｄ倍を算出するために用いる変数Ａのための領域が用意される。その他にも演算に必要なデータもＲＡＭ９には格納されるが、耐タンパ性を保持させるために追加で必要な領域は存在しない。
【００５７】
まず、本実施の形態１−Ａについての演算処理を具体的な例を用いて説明する。本具体例のためのWindowテーブル７５の内容を図１８Ａに示す。図１８Ａの例では、楕円曲線上の点Ｇのスカラー値ｄ倍を算出する場合を念頭に、スカラー値ｄが１２ビットであり、Window幅が３ビットであるものとする。従って、このWindowテーブル７５の要素数は２3＝８個である。そして、図７に示したＰＡ対策なしの場合と比較すると、各テーブル値にテーブル補正値Ｆが加えられていることが分かる。
【００５８】
具体的には、索引「０００」に対応付けて０Ｇ＋Ｆ＝Ｆを設定し、索引「００１」に対応付けて２0Ｇ＋Ｆを設定し、索引「０１０」に対応付けて２1Ｇ＋Ｆを設定し、索引「０１１」に対応付けて２1Ｇ＋２0Ｇ＋Ｆを設定し、索引「１００」に対応付けて２2Ｇ＋Ｆを設定し、索引「１０１」に対応付けて２2Ｇ＋２0Ｇ＋Ｆを設定し、索引「１１０」に対応付けて２2Ｇ＋２1Ｇ＋Ｆを設定し、索引「１１１」に対応付けて２2Ｇ＋２1Ｇ＋２0Ｇ＋Ｆを設定するようになっている。テーブル補正値Ｆは、楕円曲線上の点であるが、どのような点であっても良い。例えば、ｘをスカラー値とすると、ｘＧのような点であってもよい。但し、非ゼロでなければならない。
【００５９】
以下で一般的なテーブル値については数式で表すが、索引値の上位１ビットの値が２2Ｇに対応し、索引値の２番目のビットの値が２1Ｇに対応し、索引値の３番目のビットの値が２0Ｇに対応している。従って、索引値の各ビットの０又は１に応じて、２2Ｇ、２1Ｇ及び２0Ｇが加算されたりされなかったりする。なお、２のべき指数は、Window（すなわち索引値）において各ビットが担当する、スカラー値ｄにおける相対ビット位置に応じて設定される。すなわち、以下で述べるように、本実施の形態では、３ビット連続してスカラー値のビット値を読み出すので、Windowの最下位ビットについてのべき指数を「０」とすると、２番目のビットについてのべき指数は「１」となり、最上位のビットについてのべき指数は「２」となる。
【００６０】
このようなWindowテーブル７５を用いた具体的な演算手順は図１８Ｂに示すとおりである。最初に、手順（１）において、ｄの上位３ビットを索引として、Windowテーブル７５のテーブル値を読み出す。これを変数Ａに代入する。すなわち、（１）Ａ＝Ｔａｂ［ｄ11，ｄ10，ｄ9］（Ｔａｂ［］は、［］で指定されたテーブル値を表す）。
【００６１】
次に、手順（２）において、Windowのシフト幅である３ビットに応じて、２3Ａを算出する。すなわち、（２）Ａ＝２3Ａ。また、手順（３）において、ｄにおける次の３ビットを索引として、Windowテーブル７５のテーブル値を読み出し、Ａに加算する。すなわち、（３）Ａ＝Ａ＋Ｔａｂ［ｄ8，ｄ7，ｄ6］。さらに、手順（４）において、Windowのシフト幅である３ビットに応じて、２3Ａを算出する。すなわち、（４）Ａ＝２3Ａ。また、手順（５）において、ｄにおける次の３ビットを索引として、Windowテーブル７５のテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋Ｔａｂ［ｄ5，ｄ4，ｄ3］。
【００６２】
さらに、手順（６）において、Windowのシフト幅である３ビットに応じて、２3Ａを算出する。すなわち、（６）Ａ＝２3Ａ。手順（７）において、ｄの次の３ビットを索引として、Windowテーブル７５のテーブル値を読み出し、Ａに加算する。すなわち、（７）Ａ＝Ａ＋Ｔａｂ［ｄ2，ｄ1，ｄ0］。
【００６３】
ここまでは図７を用いて説明したものと同じであるが、当然ながらWindowテーブル７５の各テーブル値には（００１００１００１００１）2Ｆが加算されてしまっているので、手順（７）の演算結果にも余分にＦが加算されてしまっている。そこで、その分を手順（７）の結果から差し引かなければならない。本実施の形態のようにWindow法を採用する場合には、手順（８）においては、（００１００１００１００１）2Ｆを補正点データ７３として採用し、Ａ＝Ａ−（００１００１００１００１）2Ｆを算出する。
【００６４】
以上のように手順（８）を除き、基本的にはＰＡ対策なしの場合の演算処理と同じであるが、索引値「０００」に対してもテーブル値「Ｆ」が読み出されるので、ゼロの加算は絶対に行われない。すなわち、図１２（Ｂ）のような消費電力波形は出現しない。また、ダミー演算のように変数のためのＲＡＭ領域を増加させる必要もない。
【００６５】
次に、図１８Ａに示したWindowテーブル７５を一般化したものを図１９に示す。ここで、索引値ｙを（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）と表すものとする。そうすると、右からｘ番目のビットはｙx-1と表される。また、Window幅はｋビットとする。
【００６６】
そうすると、図１９に示すように、索引値ｙのテーブル値は、以下のように表される。
（ｙk-1×２k-1＋ｙk-2×２k-2＋・・・＋ｙ1×２1＋ｙ0×２0）Ｇ＋Ｆ
【００６７】
上でも述べたように、ｋビットの索引値の右からｊ番目のビットは、ｙj-1×２j-1に対応する。Window法の場合には、スカラー値ｄから連続したｋビットを読み出すので、ｋビットの索引値の右からｊ番目のビットについての２のべき指数は、当該ｊ番目のビットが担当する、スカラー値ｄにおける相対ビット位置（ｊ−１）となる。
【００６８】
従って、索引値「０」のテーブル値はテーブル補正値の「Ｆ」であり、索引値「１」のテーブル値は、ｙ0のみ「１」であるから２0Ｇ＋Ｆとなる。索引値「２」のテーブル値は、ｙ1のみ「１」であるから２1Ｇ＋Ｆとなる。さらに、索引値「２k−１」のテーブル値は、ｙk-1乃至ｙ0の全てが「１」であるから、（２k-1＋２k-2＋・・・＋２1＋２0）Ｇ＋Ｆとなる。
【００６９】
次に、図２０を用いて、楕円曲線暗号演算装置の処理フローについて説明する。まず、制御部３１は、ＲＡＭ９又はＲＯＭ７に格納されているｎビットのスカラー値ｄ及び楕円曲線上のベースポイントＧを読み出す（ステップＳ１）。そして、制御部３１は、スカラー値ｄの最上位ビットからｋビット幅のwindowで値を読み出して、索引値を取得する（ステップＳ３）。スカラー値ｄを｛ｄn-1||ｄn-2||・・・ｄ1||ｄ0｝のような形で表すとすると、ｄから読み出される値ｗ┌n/k┐-1は、以下のように表される。
ｗ┌n/k┐-1＝｛ｄk*(┌n/k┐-1)+(k-1)||・・・ｄk*(┌n/k┐-1)+1||ｄk*(┌n/k┐-1)+0｝
【００７０】
なお、┌n/k┐は、ｎ／ｋより大きい最小の整数を表す。例えばｎ＝１２で、ｋ＝３であれば、┌n/k┐-1＝３となる。また、ｋ＊（┌n/k┐-1）＋（ｋ−１）＝３＊３＋（３−１）＝１１となる。ｄが１２ビットの場合、１１は最上位ビットの番号である。
【００７１】
そして、制御部３１は、Windowテーブル７５から索引値ｗ┌n/k┐-1に対応するテーブル値を読み出し、変数Ａに設定する（ステップＳ５）。すなわち、以下のように表される。
Ａ＝Ｗ［ｗ┌n/k┐-1］
Ｗ［ｚ］は、Windowテーブル７５において索引値ｚに対応付けられているテーブル値である。
【００７２】
そして、制御部３１は、カウンタｉに、┌n/k┐−２を設定する（ステップＳ７）。
【００７３】
さらに、制御部３１は、スカラー値ｄにおいてカウンタｉで規定されるビット位置からｋビット幅のwindowで値を読み出して、索引値を取得する（ステップＳ９）。
【００７４】
ｄから読み出される値ｗiは、以下のように表される。
ｗi＝｛ｄk*i+(k-1)||・・・ｄk*i+1||ｄk*i+0｝
これによって、windowの位置がｋビット右シフトされることになる。
【００７５】
そして、制御部３１は、変数Ａの２倍演算を、windowの右シフト幅であるｋ回演算器５の２倍演算部５３に実施させる（ステップＳ１１）。図２０では、ＥＣＤＢＬ（Ａ）で、楕円曲線上におけるＡの２倍演算を表す。２倍演算自体は周知であるからこれ以上述べない。
【００７６】
さらに、制御部３１は、変数Ａと、索引値ｗiでWindowテーブル７５を検索することにより得られるテーブル値Ｗ[ｗi］との加算演算を、演算器５の加算演算部５１に実施させる（ステップＳ１３）。図２０では、ＥＣＡＤＤ（Ａ，Ｗ[ｗi］）で、ＡとＷ[ｗi］との、楕円曲線上における加算演算を表す。加算演算自体は周知であるからこれ以上述べない。
【００７７】
そして、制御部３１は、カウンタｉの値を１デクリメントし（ステップＳ１５）、ｉが０以上であるか判断する（ステップＳ１７）。ｉが０以上であればステップＳ９に戻る。すなわち、ｉが０未満になるまでステップＳ９乃至Ｓ１７を繰り返す。
【００７８】
ｉが０未満になると、補正部３３は、補正のための演算を実施する（ステップＳ１９）。すなわちＡ＝Ａ−補正点＝ｄＧであり、補正点は、上で述べたように、ｋビットの最下位ビットのみが「１」となっているビット列を┌n/k┐個並べた値（全部で┌n/k┐＊ｋビット）を楕円曲線上の点Ｆに乗じた値である。従って、補正点データ７３をＲＯＭ７から読み出して、上記演算に用いる。この演算は、補正部３３が演算器５を利用して実施するが、その詳細は周知であるからこれ以上述べない。
【００７９】
制御部３１は、このようにして得られた変数Ａの値を、指定された出力先に出力する（ステップＳ２１）。変数Ａの値は、例えば通信部１１から外部に出力される場合もあれば、他の演算プログラムに出力されて処理に用いられる。
【００８０】
以上述べたように、Windowテーブル７５において通常のテーブル値に非ゼロのテーブル補正値を加算しておき、ステップＳ１９でその分演算値に対して補正を行うことによって、どのようなスカラー値ｄに対しても同じ演算が繰り返されるようになる。すなわちＰＡが行われてもスカラー値ｄのビットを盗み取られることはない。また、処理としてはステップＳ１９だけが追加されているので、処理速度の面でもＰＡ対策なしの場合に比してパフォーマンスが大幅に落ちることはない。また、ＲＡＭ９において使用される容量は、ＰＡ対策なしの場合と同じである。ＲＯＭ７において使用される容量は、補正点データ７３の分だけ増加するが、増加量は大きくない。すなわち、ＲＯＭに比べてＲＡＭの容量が限られているスマートカードのような実装形態において、本実施の形態は特に有用となる。
【００８１】
［実施の形態１−Ｂ］
本実施の形態は、実施の形態１−Ａの変形である。本実施の形態に係る楕円曲線暗号演算装置１００の装置構成例を図２１に示す。図２１において、図１７と同じ構成要素については同じ参照番号が付されている。実施の形態１−Ａとの差は、ＲＯＭ７に、補正点データ７３が記録されていないことと、それに応じて必要な処理が異なるため演算プログラムが異なる点である。
【００８２】
すなわち、楕円曲線暗号演算装置１００では、バス１に、ＣＰＵ３と、演算器５と、ＲＯＭ７と、ＲＡＭ９と、通信部１１とが接続されている。ＲＯＭ７は、以下で説明する処理をＣＰＵ３に実行させるための演算プログラム７１ｂと、Windowテーブル７５とが記録されている。演算器５は、加算演算部５１と、２倍演算部５３とを有する。また、演算プログラム７１ｂをＣＰＵ３が実行すると、制御部３１及び以下で述べるような演算結果の補正処理を実施する補正部３３ｂが実現される。Windowテーブル７５に格納されるデータの内容は、実施の形態１−Ａと同じである。
【００８３】
次に、図２２を用いて、楕円曲線暗号演算装置の処理フローについて説明する。なお、図２０と同じ処理内容のステップについては同じステップ番号が付されている。まず、制御部３１は、ＲＡＭ９又はＲＯＭ７に格納されているｎビットのスカラー値ｄ及び楕円曲線上のベースポイントＧを読み出す（ステップＳ１）。そして、制御部３１は、スカラー値ｄの最上位ビットからｋビット幅のwindowで値を読み出して、索引値ｗ┌n/k┐-1を取得する（ステップＳ３）。
【００８４】
そして、制御部３１は、Windowテーブル７５から索引値ｗ┌n/k┐-1に対応するテーブル値を読み出し、変数Ａに設定する（ステップＳ５）。
【００８５】
さらに、制御部３１は、カウンタｉに、┌n/k┐−２を設定する（ステップＳ７）。
【００８６】
そして、制御部３１は、スカラー値ｄにおいてカウンタｉで規定されるビット位置からｋビット幅のwindowで値を読み出して、索引値ｗiを取得する（ステップＳ９）。windowの位置がｋビット右シフトされてビット値を読み出す。
【００８７】
その後、制御部３１は、変数Ａの２倍演算を、windowの右シフト幅であるｋ回演算器５の２倍演算部５３に実施させる（ステップＳ１１）。図２０と同様に、ＥＣＤＢＬ（Ａ）で、楕円曲線上におけるＡの２倍演算を表す。
【００８８】
さらに、制御部３１は、変数Ａと、索引値ｗiでWindowテーブル７５を検索することにより得られるテーブル値Ｗ[ｗi］との加算演算を、演算器５の加算演算部５１に実施させる（ステップＳ１３）。図２０と同様に、ＥＣＡＤＤ（Ａ，Ｗ[ｗi］）で、楕円曲線上におけるＡとＷ[ｗi］の加算演算を表す。
【００８９】
そして、制御部３１は、カウンタｉの値を１デクリメントし（ステップＳ１５）、ｉが０以上であるか判断する（ステップＳ１７）。ｉが０以上であればステップＳ９に戻る。すなわち、ｉが０未満になるまでステップＳ９乃至Ｓ１７を繰り返す。
【００９０】
ｉが０未満になると、補正部３３ｂは、補正点を算出する（ステップＳ１８）。補正点は、実施の形態１−Ａと同じであり、ｋビットの最下位ビットのみが「１」となっているビット列を┌n/k┐個並べた値（全部で┌n/k┐＊ｋビット）を楕円曲線上の点Ｆに乗じた値である。このような演算は、制御部３１が演算器５を利用して実施するが、その詳細は周知であるからこれ以上述べない。そして、補正部３３ｂは、算出した補正点を用いて補正のための演算を実施する（ステップＳ１９）。すなわちＡ＝Ａ−補正点を演算する。この演算は、補正部３３ｂが演算器５を利用して実施するが、その詳細は周知であるからこれ以上述べない。
【００９１】
制御部３１は、このようにして得られた変数Ａの値を、指定された出力先に出力する（ステップＳ２１）。変数Ａの値は、例えば通信部１１から外部に出力される場合もあれば、他の演算プログラムに出力されて処理に用いられる。
【００９２】
以上述べたように、Windowテーブル７５において通常のテーブル値に非ゼロのテーブル補正値を加算しておき、ステップＳ１９でその分演算値に対して補正を行うことによって、どのようなスカラー値ｄに対しても同じ演算が繰り返されるようになる。すなわちＰＡが行われてもスカラー値ｄのビットを盗み取られることはない。また、ＲＡＭ９において使用される容量は、ＰＡ対策なしの場合と同じである。ＲＯＭ７において使用される容量も、ＰＡ対策なしの場合と同じとなっている。すなわち、メモリ特にＲＡＭの容量が限られているスマートカードのような実装形態において、本実施の形態は特に有用となる。
【００９３】
［実施の形態２−Ａ］
本実施の形態に係る楕円曲線暗号演算装置１００の装置構成例を図２３に示す。図１７に示した楕円曲線暗号演算装置１００と同じ構成要素については同じ参照番号が付されている。本楕円曲線暗号演算装置では、バス１に、ＣＰＵ（Central Processing Unit）３と、演算器５と、ＲＯＭ７と、ＲＡＭ９と、通信部１１とが接続されている。ＲＯＭ７は、以下で説明する処理をＣＰＵ３に実行させるための演算プログラム７１ｃと、以下で述べる補正点データ７３ｃと、櫛形Window法のWindowテーブルをベースとしたものであって以下で述べるWindowテーブル７５ｃとが記録されている。
【００９４】
演算器５は、実施の形態１−Ａと同じ加算演算部５１及び２倍演算部５３とを有する。また、演算プログラム７１ｃをＣＰＵ３が実行すると、制御部３１ｃ及び以下で述べるような演算結果の補正処理を実施する補正部３３ｃが実現される。また、外部装置との通信を行うため通信部１１を設ける例を示しているが、他の機能を実現するための装置が設けられる場合もある。ＲＡＭ９は、ＣＰＵ３が各種処理を実施する際に用いるデータを格納するものであり、本実施の形態では、楕円曲線におけるベースポイントＧのスカラー値ｄ倍を算出するために用いる変数Ａのための領域が用意される。その他にも演算に必要なデータもＲＡＭ９には格納されるが、耐タンパ性を保持させるために追加で必要な領域は存在しない。
【００９５】
まず、本実施の形態２−Ａについての演算処理を具体的な例を用いて説明する。本具体例のためのWindowテーブル７５ｃの内容を図２４Ａに示す。図２４Ａの例では、楕円曲線上の点Ｇのスカラー値ｄ倍を算出する場合を念頭に、スカラー値ｄが１２ビットであり、Window幅が３ビットであるものとする。従って、このWindowテーブル７５ｃの要素数は２3＝８個である。そして、図９に示したＰＡ対策なしの場合と比較すると、各テーブル値にテーブル補正値Ｆが加えられていることが分かる。
【００９６】
具体的には、索引「０００」に対応付けて０Ｇ＋Ｆ＝Ｆを設定し、索引「００１」に対応付けて２0Ｇ＋Ｆを設定し、索引「０１０」に対応付けて２4Ｇ＋Ｆを設定し、索引「０１１」に対応付けて２4Ｇ＋２0Ｇ＋Ｆを設定し、索引「１００」に対応付けて２8Ｇ＋Ｆを設定し、索引「１０１」に対応付けて２8Ｇ＋２0Ｇ＋Ｆを設定し、索引「１１０」に対応付けて２8Ｇ＋２4Ｇ＋Ｆを設定し、索引「１１１」に対応付けて２8Ｇ＋２4Ｇ＋２0Ｇ＋Ｆを設定するようになっている。テーブル補正値Ｆは、楕円曲線上の点であるが、どのような点であっても良い。例えば、ｘをスカラー値とすると、ｘＧのような点であってもよい。但し、非ゼロでなければならない。
【００９７】
以下で一般的なテーブル値については数式で表すが、索引値の上位１ビットの値が２8Ｇに対応し、索引値の２番目のビットの値が２4Ｇに対応し、索引値の３番目のビットの値が２0Ｇに対応している。従って、索引値の各ビットの０又は１に応じて、２8Ｇ、２4Ｇ及び２0Ｇが加算されたりされなかったりする。なお、２のべき指数は、Window（すなわち索引値）において各ビットが担当する、スカラー値ｄにおける相対ビット位置に応じて設定される。すなわち、本実施の形態では、図９でも示したように（┌n/k┐−１）＝３ビットおきにスカラー値ｄのビット値を読み出すので、Windowの最下位ビットについてのべき指数を「０」とすると、２番目のビットについてのべき指数は「４」であり、最上位のビットについてのべき指数は「８」である。
【００９８】
このようなWindowテーブル７５ｃを用いた具体的な演算手順は図２４Ｂに示すとおりである。最初に、手順（１）において、スカラー値ｄの最上位ビットから３ビットおきにビット値を読み出すことによって索引値を得て、Windowテーブル７５ｃのテーブル値を読み出す。これを変数Ａに代入する。すなわち、（１）Ａ＝Ｔａｂ［ｄ11，ｄ7，ｄ3］（Ｔａｂ［］は、［］で指定されたテーブル値を表す）。
【００９９】
次に、手順（２）において、Windowのシフト幅である１ビットに応じて、２Ａを算出する。すなわち、（２）Ａ＝２Ａ。また、手順（３）において、スカラー値ｄの上位第２ビットから３ビットおきにビット値を読み出すことによって索引値を得て、Windowテーブル７５ｃのテーブル値を読み出し、Ａに加算する。すなわち、（３）Ａ＝Ａ＋Ｔａｂ［ｄ10，ｄ6，ｄ2］。さらに、手順（４）において、Windowのシフト幅である１ビットに応じて、２Ａを算出する。すなわち、（４）Ａ＝２Ａ。また、手順（５）において、スカラー値ｄの上位第３ビットから３ビットおきにビット値を読み出すことによって索引値を得て、Windowテーブル７５ｃのテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋Ｔａｂ［ｄ9，ｄ5，ｄ1］。
【０１００】
さらに、手順（６）において、Windowのシフト幅である１ビットに応じて、２Ａを算出する。すなわち、（６）Ａ＝２Ａ。そして、手順（７）において、スカラー値ｄの上位第４ビットから３ビットおきにビット値を読み出すことによって索引値を得て、Windowテーブル７５ｃのテーブル値を読み出し、Ａに加算する。すなわち、（７）Ａ＝Ａ＋Ｔａｂ［ｄ8，ｄ4，ｄ0］。
【０１０１】
ここまでは図９を用いて説明したものと同じであるが、当然ながらWindowテーブル７５ｃの各テーブル値には（１１１１）2Ｆが加算されてしまっているので、手順（７）の演算結果にも余分にＦが加算されてしまっている。そこで、その分を手順（７）の結果から差し引かなければならない。本実施の形態のように櫛形Window法を採用する場合には、手順（８）においては、（１１１１）2Ｆを補正点データ７３ｃとして採用し、Ａ＝Ａ−（１１１１）2Ｆを算出する。
【０１０２】
以上のように手順（８）を除き、基本的にはＰＡ対策なしの場合の演算処理と同じであるが、索引値「０００」に対してもテーブル値「Ｆ」が読み出されるので、ゼロの加算は絶対に行われない。すなわち、図１２（Ｂ）のような消費電力波形は出現しない。また、ダミー演算のように変数のためのＲＡＭ領域を増加させる必要もない。
【０１０３】
次に、図２４Ａに示したWindowテーブル７５ｃを一般化したものを図２５に示す。実施の形態１−Ａと同様に、索引値ｙを（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）と表すものとする。また、Window幅はｋビットとする。
【０１０４】
そうすると、図２５に示すように、索引値ｙのテーブル値は、以下のように表される。
（ｙk-1×２┌n/k┐*(k-1)＋ｙk-2×２┌n/k┐*(k-2)＋・・・＋ｙ1×２┌n/k┐*1＋ｙ0×２┌n/k┐*0）Ｇ＋Ｆ
【０１０５】
上でも述べたように、ｋビットの索引値の右からｊ番目のビットは、ｙj-1×２┌n/k┐*(j-1)に対応する。櫛形Window法の場合には、スカラー値ｄから（┌n/k┐−１）おきにｋビットを読み出すので、ｋビットの索引値の右からｊ番目のビットについての２のべき指数は、当該ｊ番目のビットが担当する、スカラー値ｄにおける相対ビット位置┌n/k┐＊（ｊ−１）となる。
【０１０６】
従って、索引値「０」のテーブル値はテーブル補正値の「Ｆ」であり、索引値「１」のテーブル値は、ｙ0のみ「１」であるから２0＋Ｆとなる。索引値「２」のテーブル値は、ｙ1のみ「１」であるから２┌n/k┐*1＋Ｆとなる。さらに、索引値「２k−１」のテーブル値は、ｙk-1乃至ｙ0の全てが「１」であるから、（２┌n/k┐*(k-1)＋２┌n/k┐*(k-2)＋・・・＋２┌n/k┐*1＋２┌n/k┐*0）Ｇ＋Ｆとなる。
【０１０７】
次に、図２６を用いて、楕円曲線暗号演算装置の処理フローについて説明する。まず、制御部３１ｃは、ＲＡＭ９又はＲＯＭ７に格納されているｎビットのスカラー値ｄ及び楕円曲線上のベースポイントＧを読み出す（ステップＳ３１）。そして、制御部３１ｃは、スカラー値ｄの最上位ビットから（┌n/k┐−１）ビットおきにｋビット幅のwindowでビット値を読み出して、索引値を取得する（ステップＳ３３）。スカラー値ｄを｛ｄn-1||ｄn-2||・・・ｄ1||ｄ0｝のような形で表すとすると、ｄから読み出される値ｗ┌n/k┐-1は、以下のように表される。
ｗ┌n/k┐-1＝｛ｄ┌n/k┐*(k-1)+┌n/k┐-1||・・・ｄ┌n/k┐*1+┌n/k┐-1||ｄ┌n/k┐*0+┌n/k┐-1｝
【０１０８】
そして、制御部３１ｃは、Windowテーブル７５ｃから索引値ｗ┌n/k┐-1に対応するテーブル値を読み出し、変数Ａに設定する（ステップＳ３５）。すなわち、以下のように表される。
Ａ＝Ｗ［ｗ┌n/k┐-1］
Ｗ［ｚ］は、Windowテーブル７５ｃにおいて索引値ｚに対応付けられているテーブル値である。
【０１０９】
そして、制御部３１ｃは、カウンタｉに、┌n/k┐−２を設定する（ステップＳ３７）。
【０１１０】
さらに、制御部３１ｃは、スカラー値ｄにおいてカウンタｉで規定されるビット位置からｋビット幅のwindowでビット値を（┌n/k┐−１）ビットおきに読み出して、索引値を取得する（ステップＳ３９）。
【０１１１】
ｄから読み出される値ｗiは、以下のように表される。
ｗi＝｛ｄk*i+(k-1)||・・・ｄk*i+1||ｄk*i+0｝
すなわち、Windowが１ビット右シフトされることになる。
【０１１２】
そして、制御部３１ｃは、変数Ａの２倍演算を、windowの右シフト幅である１回だけ演算器５の２倍演算部５３に実施させる（ステップＳ４１）。図２６では、ＥＣＤＢＬ（Ａ）で、楕円曲線上におけるＡの２倍演算を表す。２倍演算自体は周知であるからこれ以上述べない。
【０１１３】
さらに、制御部３１ｃは、変数Ａと、索引値ｗiでWindowテーブル７５ｃを検索することにより得られるテーブル値Ｗ[ｗi］との加算演算を、演算器５の加算演算部５１に実施させる（ステップＳ４３）。図２６は、ＥＣＡＤＤ（Ａ，Ｗ[ｗi］）で、楕円曲線上におけるＡとＷ[ｗi］の加算演算を表す。加算演算自体は周知であるからこれ以上述べない。
【０１１４】
そして、制御部３１ｃは、カウンタｉの値を１デクリメントし（ステップＳ４５）、ｉが０以上であるか判断する（ステップＳ４７）。ｉが０以上であればステップＳ３９に戻る。すなわち、ｉが０未満になるまでステップＳ３９乃至Ｓ４７を繰り返す。
【０１１５】
ｉが０未満になると、補正部３３ｃは、補正のための演算を実施する（ステップＳ４９）。すなわちＡ＝Ａ−補正点＝ｄＧであり、補正点は、上で述べたように、「１」を┌n/k┐ビット並べた値を楕円曲線上の点Ｆに乗じた値である。従って、補正点データ７３ｃをＲＯＭ７から読み出して、上記演算に用いる。この演算は、補正部３３ｃが演算器５を利用して実施するが、その詳細は周知であるからこれ以上述べない。
【０１１６】
制御部３１ｃは、このようにして得られた変数Ａの値を、指定された出力先に出力する（ステップＳ５１）。変数Ａの値は、例えば通信部１１から外部に出力される場合もあれば、他の演算プログラムに出力されて処理に用いられる。
【０１１７】
以上述べたように、Windowテーブル７５ｃにおいて通常のテーブル値に非ゼロのテーブル補正値を加算しておき、ステップＳ４９でその分演算値に対して補正を行うことによって、どのようなスカラー値ｄに対しても同じ演算が繰り返されるようになる。すなわちＰＡが行われてもスカラー値ｄのビットを盗み取られることはない。また、処理としてはステップＳ４９だけが追加されているので、処理速度の面でもＰＡ対策なしの場合に比してパフォーマンスが大幅に落ちることはない。また、ＲＡＭ９において使用される容量は、ＰＡ対策なしの場合と同じである。ＲＯＭ７において使用される容量は、補正点データ７３ｃの分だけ増加するが、増加量は大きくない。すなわち、ＲＯＭに比べてＲＡＭの容量が限られているスマートカードのような実装形態において、本実施の形態は特に有用となる。
【０１１８】
［実施の形態２−Ｂ］
本実施の形態は、実施の形態２−Ａの変形である。本実施の形態に係る楕円曲線暗号演算装置１００の装置構成例を図２７に示す。図２７において、図２３と同じ構成要素については同じ参照番号が付されている。実施の形態２−Ａとの差は、ＲＯＭ７に、補正点データ７３ｃが記録されていないことと、それに応じて必要な処理が異なるため演算プログラム７１ｃが異なる点である。
【０１１９】
すなわち、楕円曲線暗号演算装置１００では、バス１に、ＣＰＵ３と、演算器５と、ＲＯＭ７と、ＲＡＭ９と、通信部１１とが接続されている。ＲＯＭ７は、以下で説明する処理をＣＰＵ３に実行させるための演算プログラム７１ｄと、Windowテーブル７５ｃとが記録されている。演算器５は、加算演算部５１と、２倍演算部５３とを有する。また、演算プログラム７１ｄをＣＰＵ３が実行すると、制御部３１ｄ及び以下で述べるような演算結果の補正処理を実施する補正部３３ｄが実現される。Windowテーブル７５ｃに格納されるデータの内容は、実施の形態２−Ａと同じである。
【０１２０】
次に、図２８を用いて、楕円曲線暗号演算装置の処理フローについて説明する。なお、図２６と同じ処理内容のステップについては同じステップ番号が付されている。まず、制御部３１ｄは、ＲＡＭ９又はＲＯＭ７に格納されているｎビットのスカラー値ｄ及び楕円曲線上のベースポイントＧを読み出す（ステップＳ３１）。そして、制御部３１ｄは、スカラー値ｄの最上位ビットからｋビット幅のwindowでビット値を（┌n/k┐−１）ビットおきに読み出して、索引値ｗ┌n/k┐-1を取得する（ステップＳ３３）。
【０１２１】
そして、制御部３１ｄは、Windowテーブル７５ｃから索引値ｗ┌n/k┐-1に対応するテーブル値を読み出し、変数Ａに設定する（ステップＳ３５）。また、制御部３１ｄは、カウンタｉに、┌n/k┐−２を設定する（ステップＳ３７）。さらに、制御部３１ｄは、スカラー値ｄにおいてカウンタｉで規定されるビット位置からｋビット幅のwindowでビット値を（┌n/k┐−１）ビットおきに読み出して、索引値を取得する（ステップＳ３９）。上でも述べたようにwindowの１ビット右シフトが行われている。
【０１２２】
そして、制御部３１ｄは、変数Ａの２倍演算を、windowの右シフト幅である１回だけ演算器５の２倍演算部５３に実施させる（ステップＳ４１）。図２８では、ＥＣＤＢＬ（Ａ）で、楕円曲線上におけるＡの２倍演算を表す。
【０１２３】
さらに、制御部３１ｄは、変数Ａと、索引値ｗiでWindowテーブル７５ｃを検索することにより得られるテーブル値Ｗ[ｗi］との加算演算を、演算器５の加算演算部５１に実施させる（ステップＳ４３）。図２８では、ＥＣＡＤＤ（Ａ，Ｗ[ｗi］）で、楕円曲線上におけるＡとＷ[ｗi］の加算演算を表す。
【０１２４】
そして、制御部３１ｄは、カウンタｉの値を１デクリメントし（ステップＳ４５）、ｉが０以上であるか判断する（ステップＳ４７）。ｉが０以上であればステップＳ３９に戻る。すなわち、ｉが０未満になるまでステップＳ３９乃至Ｓ４７を繰り返す。
【０１２５】
ｉが０未満になると、補正部３３ｄは、補正点を算出する（ステップＳ４８）。実施の形態２−Ａと同様に、補正点は、「１」を┌n/k┐ビット並べた値を楕円曲線上の点Ｆに乗じた値である。この演算は、補正部３３ｄが演算器５を利用して実施する。
【０１２６】
その後、補正部３３ｄは、補正のための演算を実施する（ステップＳ４９）。すなわちＡ＝Ａ−補正点＝ｄＧを算出する。この演算は、補正部３３ｄが演算器５を利用して実施する。
【０１２７】
制御部３１ｄは、このようにして得られた変数Ａの値を、指定された出力先に出力する（ステップＳ５１）。変数Ａの値は、例えば通信部１１から外部に出力される場合もあれば、他の演算プログラムに出力されて処理に用いられる。
【０１２８】
以上述べたように、Windowテーブル７５ｃにおいて通常のテーブル値に非ゼロのテーブル補正値を加算しておき、ステップＳ４８及びＳ４９でその分演算値に対して補正を行うことによって、どのようなスカラー値ｄに対しても同じ演算が繰り返されるようになる。すなわちＰＡが行われてもスカラー値ｄのビットを盗み取られることはない。また、ＲＡＭ９において使用される容量は、ＰＡ対策なしの場合と同じである。ＲＯＭ７において使用される容量も、ＰＡ対策なしの場合と同じである。すなわち、メモリ特にＲＡＭの容量が限られているスマートカードのような実装形態において、本実施の形態は特に有用となる。
【０１２９】
［実施の形態３］
本実施の形態に係る楕円曲線暗号演算装置１００の装置構成例を図２９に示す。図２１に示した楕円曲線暗号演算装置１００と同じ構成要素については同じ参照番号が付されている。本楕円曲線暗号演算装置１００では、バス１に、ＣＰＵ（Central Processing Unit）３と、演算器５と、ＲＯＭ７と、ＲＡＭ９と、通信部１１とが接続されている。ＲＯＭ７は、以下で説明する処理をＣＰＵ３に実行させるための演算プログラム７１ｅと、通常のWindow法のWindowテーブルをベースとしたものであって以下で述べるWindowテーブル７５ｅとが記録されている。
【０１３０】
演算器５は、実施の形態１−Ａと同じ加算演算部５１及び２倍演算部５３とを有する。また、演算プログラム７１ｅをＣＰＵ３が実行すると、制御部３１ｅ及び以下で述べるようなスカラー値ｄの補正演算を実施する補正部３３ｅが実現される。また、外部装置との通信を行うため通信部１１を設ける例を示しているが、他の機能を実現するための装置が設けられる場合もある。ＲＡＭ９は、ＣＰＵ３が各種処理を実施する際に用いるデータを格納するものであり、本実施の形態では、楕円曲線におけるベースポイントＧのスカラー値ｄ倍を算出するために用いる変数Ａのための領域が用意される。その他にも演算に必要なデータもＲＡＭ９には格納されるが、耐タンパ性を保持させるために追加で必要な領域は存在しない。
【０１３１】
まず、本実施の形態３についての演算処理を具体的な例を用いて説明する。本具体例のためのWindowテーブル７５ｅの内容を図３０Ａに示す。図３０Ａの例では、楕円曲線上の点Ｇのスカラー値ｄ倍を算出する場合を念頭に、スカラー値ｄが１２ビットであり、Window幅が３ビットであるものとする。従って、このWindowテーブル７５ｅの要素数は２3＝８個である。そして、図９に示したＰＡ対策なしの場合と比較すると、各テーブル値にテーブル補正値ｘＧが加えられていることが分かる。なお、ｘは非ゼロである。
【０１３２】
具体的には、索引「０００」に対応付けてｘＧを設定し、索引「００１」に対応付けて２0Ｇ＋ｘＧを設定し、索引「０１０」に対応付けて２1Ｇ＋ｘＧを設定し、索引「０１１」に対応付けて２1Ｇ＋２0Ｇ＋ｘＧを設定し、索引「１００」に対応付けて２2Ｇ＋ｘＧを設定し、索引「１０１」に対応付けて２2Ｇ＋２0Ｇ＋ｘＧを設定し、索引「１１０」に対応付けて２2Ｇ＋２1Ｇ＋ｘＧを設定し、索引「１１１」に対応付けて２2Ｇ＋２1Ｇ＋２0Ｇ＋ｘＧを設定するようになっている。テーブル補正値にｘＧを採用することによって、以下で述べるように、スカラー値ｄを単純なスカラーの演算によって補正するだけで、楕円曲線上の演算を削減することができるようになる。
【０１３３】
以下で一般的なテーブル値については数式で表すが、索引値の上位１ビットの値が２2Ｇに対応し、索引値の２番目のビットの値が２1Ｇに対応し、索引値の３番目のビットの値が２0Ｇに対応している。従って、索引値の各ビットの０又は１に応じて、２2Ｇ、２1Ｇ及び２0Ｇが加算されたりされなかったりする。なお、２のべき指数は、Window（すなわち索引値）において各ビットが担当する、スカラー値ｄにおける相対ビット位置に応じて設定される。すなわち、本実施の形態では、図９でも示したように（┌n/k┐−１）＝３ビットおきにスカラー値ｄのビット値を読み出すので、Windowの最下位ビットについてのべき指数を「０」とすると、２番目のビットについてのべき指数は「１」であり、最上位のビットについてのべき指数は「２」である。
【０１３４】
このようなWindowテーブル７５ｅを用いた具体的な演算手順は図３０Ｂに示すとおりである。最初に、従来技術や実施の形態１−Ａ乃至２−Ｂとは異なり、手順（０）において、スカラー値ｄを、ｄ＝ｄ−ｘ（００１００１００１００１）2で補正する。ｘＧがそれぞれテーブル値に加算されているWindowテーブル７５ｅを用いて演算を実施すると、最終的に変数Ａに格納される値は、ｄＧ＋（００１００１００１００１）2×Ｇとなる。従って、スカラー値ｄから、予め（００１００１００１００１）2×ｘだけ減算しておけば、最終的に得られる結果がｄＧとなり、テーブル補正値の影響を相殺することができる。なお、このような補正を実施することによって、後から楕円曲線上の演算が不要になって、演算速度が速くなる。
【０１３５】
次に、手順（１）において、補正後のｄ（以下、本実施の形態では単純にｄと示す場合もある）の上位３ビットを索引として、Windowテーブル７５ｅのテーブル値を読み出す。これを変数Ａに代入する。すなわち、（１）Ａ＝Ｔａｂ［ｄ11，ｄ10，ｄ9］（Ｔａｂ［ｘ］は、［ｘ］で指定されたテーブル値を表す）。
【０１３６】
次に、手順（２）において、Windowのシフト幅である３ビットに応じて、２3Ａを算出する。すなわち、（２）Ａ＝２3Ａ。また、手順（３）において、補正後のｄの次の３ビットを索引として、Windowテーブル７５ｅのテーブル値を読み出し、Ａに加算する。すなわち、（３）Ａ＝Ａ＋Ｔａｂ［ｄ8，ｄ7，ｄ6］。さらに、手順（４）において、Windowのシフト幅である３ビットに応じて、２3Ａを算出する。すなわち、（４）Ａ＝２3Ａ。また、手順（５）において、補正後のｄの次の３ビットを索引として、Windowテーブル７５のテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋Ｔａｂ［ｄ5，ｄ4，ｄ3］。
【０１３７】
さらに、手順（６）において、Windowのシフト幅である３ビットに応じて、２3Ａを算出する。すなわち、（６）Ａ＝２3Ａ。手順（７）において、補正後のｄにおいて次の３ビットを索引として、Windowテーブル７５ｅのテーブル値を読み出し、Ａに加算する。すなわち、（７）Ａ＝Ａ＋Ｔａｂ［ｄ2，ｄ1，ｄ0］＝ｄＧ。
【０１３８】
このように手順（０）を除き、ＰＡ対策なしの場合の手順と同じになる。但し、索引値「０００」に対してもテーブル値「ｘＧ」が読み出されるので、ゼロの加算は絶対に行われない。すなわち、図１２（Ｂ）のような消費電力波形は出現しない。また、ダミー演算のように変数のためのＲＡＭ領域を増加させる必要もない。
【０１３９】
次に、図３０Ａに示したWindowテーブル７５ｅを一般化したものを図３１に示す。ここで、索引値ｙを（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）と表すものとする。そうすると、右からｘ番目のビットはｙx-1と表される。また、Window幅はｋビットとする。
【０１４０】
そうすると、図３１に示すように、索引値ｙのテーブル値は、以下のように表される。
（ｙk-1×２k-1＋ｙk-2×２k-2＋・・・＋ｙ1×２1＋ｙ0×２0）Ｇ＋ｘＧ
【０１４１】
上でも述べたように、ｋビットの索引値の右からｊ番目のビットは、ｙj-1×２j-1に対応する。Window法の場合には、スカラー値ｄから連続したｋビットを読み出すので、ｋビットの索引値の右からｊ番目のビットについての２のべき指数は、当該ｊ番目のビットが担当する、スカラー値ｄにおける相対ビット位置（ｊ−１）となる。
【０１４２】
従って、索引値「０」のテーブル値はテーブル補正値の「ｘＧ」であり、索引値「１」のテーブル値は、ｙ0のみ「１」であるから２0Ｇ＋ｘＧとなる。索引値「２」のテーブル値は、ｙ1のみ「１」であるから２1Ｇ＋ｘＧとなる。さらに、索引値「２k−１」のテーブル値は、ｙk-1乃至ｙ0の全てが「１」であるから、（２k-1＋２k-2＋・・・＋２1＋２0）Ｇ＋ｘＧとなる。
【０１４３】
次に、図３２を用いて、楕円曲線暗号演算装置の処理フローについて説明する。まず、制御部３１ｅは、ＲＡＭ９又はＲＯＭ７に格納されているｎビットのスカラー値ｄ及び楕円曲線上のベースポイントＧを読み出す（ステップＳ６１）。そして、補正部３３ｅは、スカラー値ｄの補正を実施する（ステップＳ６３）。すなわち、補正値としてｋビットのうち最下位ビットのみが「１」であるビット列が┌n/k┐個連結された補正値（００１００１００１．．．００１）（全┌n/k┐＊ｋビット）とスカラー値ｘの積を算出する。この処理は簡単な処理であるからＣＰＵ３で容易に実施することができる。その後、制御部３１ｅは、補正後のスカラー値ｄ（以下、本実施の形態において単にスカラー値ｄと略する場合がある）の最上位ビットからｋビット幅のwindowで値を読み出して、索引値を取得する（ステップＳ６５）。補正後のスカラー値ｄを｛ｄn-1||ｄn-2||・・・ｄ1||ｄ0｝のような形で表すとすると、ｄから読み出される値ｗ┌n/k┐-1は、以下のように表される。
ｗ┌n/k┐-1＝｛ｄk*(┌n/k┐-1)+(k-1)||・・・ｄk*(┌n/k┐-1)+1||ｄk*(┌n/k┐-1)+0｝
【０１４４】
なお、┌n/k┐は、ｎ／ｋより大きい最小の整数を表す。
【０１４５】
そして、制御部３１ｅは、Windowテーブル７５ｅから索引値ｗ┌n/k┐-1に対応するテーブル値を読み出し、変数Ａに設定する（ステップＳ６７）。すなわち、以下のように表される。
Ａ＝Ｗ［ｗ┌n/k┐-1］
Ｗ［ｚ］は、Windowテーブル７５ｅにおいて索引値ｚに対応付けられているテーブル値である。
【０１４６】
そして、制御部３１ｅは、カウンタｉに、┌n/k┐−２を設定する（ステップＳ６９）。
【０１４７】
さらに、制御部３１ｅは、補正後のスカラー値ｄからカウンタｉで規定されるビット位置からｋビット幅のwindowで値を読み出して、索引値を取得する（ステップＳ７１）。
【０１４８】
補正後のｄから読み出される値ｗiは、以下のように表される。
ｗi＝｛ｄk*i+(k-1)||・・・ｄk*i+1||ｄk*i+0｝
これによって、windowの位置がｋビット右シフトされることになる。
【０１４９】
そして、制御部３１ｅは、変数Ａの２倍演算を、windowの右シフト幅であるｋ回演算器５の２倍演算部５３に実施させる（ステップＳ７３）。図３２では、ＥＣＤＢＬ（Ａ）で、楕円曲線上におけるＡの２倍演算を表す。
【０１５０】
さらに、制御部３１ｅは、変数Ａと、索引値ｗiでWindowテーブル７５ｅを検索することにより得られるテーブル値Ｗ[ｗi］との加算演算を、演算器５の加算演算部５１に実施させる（ステップＳ７５）。図３２は、ＥＣＡＤＤ（Ａ，Ｗ[ｗi］）で、楕円曲線上におけるＡとＷ[ｗi］の加算演算を表す。
【０１５１】
そして、制御部３１ｅは、カウンタｉの値を１デクリメントし（ステップＳ７７）、ｉが０以上であるか判断する（ステップＳ７９）。ｉが０以上であればステップＳ７１に戻る。すなわち、ｉが０未満になるまでステップＳ７１乃至Ｓ７９を繰り返す。
【０１５２】
ｉが０未満になると、制御部３１ｅは、このようにして得られた変数Ａの値を、指定された出力先に出力する（ステップＳ８１）。変数Ａの値は、例えば通信部１１から外部に出力される場合もあれば、他の演算プログラムに出力されて処理に用いられる。
【０１５３】
以上述べたように、Windowテーブル７５ｅにおいて通常のテーブル値に非ゼロのテーブル補正値ｘＧを加算しておくことによって、どのようなスカラー値ｄに対しても同じ演算が繰り返されるようになる。すなわちＰＡが行われてもスカラー値ｄのビットを盗み取られることはない。また、処理としてはステップＳ６３だけが追加されているので、処理速度の面でもＰＡ対策なしの場合に比してパフォーマンスが大幅に落ちることはない。また、ＲＡＭ９において使用される容量は、ＰＡ対策なしの場合と同じである。ＲＯＭ７において使用される容量もＰＡなしの場合と同様である。すなわち、メモリ特にＲＡＭの容量が限られているスマートカードのような実装形態において、本実施の形態は特に有用となる。
【０１５４】
［実施の形態４］
本実施の形態は、実施の形態３の櫛形Window版である。本実施の形態に係る楕円曲線暗号演算装置１００の装置構成例を図３３に示す。図２９に示した楕円曲線暗号演算装置１００と同じ構成要素については同じ参照番号が付されている。本楕円曲線暗号演算装置１００では、バス１に、ＣＰＵ（Central Processing Unit）３と、演算器５と、ＲＯＭ７と、ＲＡＭ９と、通信部１１とが接続されている。ＲＯＭ７は、以下で説明する処理をＣＰＵ３に実行させるための演算プログラム７１ｆと、櫛形Window法のWindowテーブルをベースとしたものであって以下で述べるWindowテーブル７５ｆとが記録されている。
【０１５５】
演算器５は、実施の形態１−Ａと同じ加算演算部５１及び２倍演算部５３とを有する。また、演算プログラム７１ｆをＣＰＵ３が実行すると、制御部３１ｆ及び以下で述べるようなスカラー値ｄの補正処理を実施する補正部３３ｆが実現される。また、外部装置との通信を行うため通信部１１を設ける例を示しているが、他の機能を実現するための装置が設けられる場合もある。ＲＡＭ９は、ＣＰＵ３が各種処理を実施する際に用いるデータを格納するものであり、本実施の形態では、楕円曲線におけるベースポイントＧのスカラー値ｄ倍を算出するために用いる変数Ａのための領域が用意される。その他にも演算に必要なデータもＲＡＭ９には格納されるが、耐タンパ性を保持させるために追加で必要な領域は存在しない。
【０１５６】
まず、本実施の形態４についての演算処理を具体的な例を用いて説明する。本具体例のためのWindowテーブル７５ｆの内容を図３４Ａに示す。図３４Ａの例では、楕円曲線上の点Ｇのスカラー値ｄ倍を算出する場合を念頭に、スカラー値ｄが１２ビットであり、Window幅が３ビットであるものとする。従って、このWindowテーブル７５ｆの要素数は２3＝８個である。そして、図９に示したＰＡ対策なしの場合と比較すると、各テーブル値にテーブル補正値ｘＧが加えられていることが分かる。すなわち、ベースポイントＧのスカラー値ｘ倍である。
【０１５７】
具体的には、索引「０００」に対応付けて０Ｇ＋ｘＧ＝ｘＧを設定し、索引「００１」に対応付けて２0Ｇ＋ｘＧを設定し、索引「０１０」に対応付けて２4Ｇ＋ｘＧを設定し、索引「０１１」に対応付けて２4Ｇ＋２0Ｇ＋ｘＧを設定し、索引「１００」に対応付けて２8Ｇ＋ｘＧを設定し、索引「１０１」に対応付けて２8Ｇ＋２0Ｇ＋ｘＧを設定し、索引「１１０」に対応付けて２8Ｇ＋２4Ｇ＋ｘＧを設定し、索引「１１１」に対応付けて２8Ｇ＋２4Ｇ＋２0Ｇ＋ｘＧを設定するようになっている。テーブル補正値にｘＧを採用することによって、以下で述べるように、スカラー値ｄを単純なスカラーの演算によって補正するだけで、楕円曲線上の演算を削減することができるようになる。
【０１５８】
以下で一般的なテーブル値については数式で表すが、索引値の上位１ビットの値が２8Ｇに対応し、索引値の２番目のビットの値が２4Ｇに対応し、索引値の３番目のビットの値が２0Ｇに対応している。従って、索引値の各ビットの０又は１に応じて、２8Ｇ、２4Ｇ及び２0Ｇが加算されたりされなかったりする。なお、２のべき指数は、Window（すなわち索引値）において各ビットが担当する、スカラー値ｄにおける相対ビット位置に応じて設定される。すなわち、本実施の形態では、図９でも示したように（┌n/k┐−１）＝３ビットおきにスカラー値ｄのビット値を読み出すので、Windowの最下位ビットについてのべき指数を「０」とすると、２番目のビットについてのべき指数は「４」であり、最上位のビットについてのべき指数は「８」である。
【０１５９】
このようなWindowテーブル７５ｆを用いた具体的な演算手順は図３４Ｂに示すとおりである。最初に、従来技術や実施の形態１−Ａ乃至２−Ｂとは異なり、手順（０）において、スカラー値ｄを、ｄ＝ｄ−ｘ（１１１１）2で補正する。ｘＧがそれぞれテーブル値に加算されているWindowテーブル７５ｆを用いて演算を実施すると、最終的に変数Ａに格納される値は、ｄＧ＋（１１１１）2×Ｇとなる。従って、スカラー値ｄから、予め（１１１１）2×ｘだけ減算しておけば、最終的に得られる結果がｄＧとなり、テーブル補正値の影響を相殺することができる。なお、このような補正を実施することによって、後から楕円曲線上の演算が不要になって、演算速度が速くなる。
【０１６０】
そして、手順（１）において、補正後のスカラー値ｄ（以下、本実施の形態において単にスカラー値ｄと略する場合がある）の最上位ビットから３ビットおきにビット値を読み出すことによって索引値を得て、Windowテーブル７５ｆのテーブル値を読み出す。これを変数Ａに代入する。すなわち、（１）Ａ＝Ｔａｂ［ｄ11，ｄ7，ｄ3］（Ｔａｂ［］は、［］で指定されたテーブル値を表す）。
【０１６１】
次に、手順（２）において、Windowのシフト幅である１ビットに応じて、２Ａを算出する。すなわち、（２）Ａ＝２Ａ。また、手順（３）において、補正後のスカラー値ｄの上位第２ビットから３ビットおきにビット値を読み出すことによって索引値を得て、Windowテーブル７５ｆのテーブル値を読み出し、Ａに加算する。すなわち、（３）Ａ＝Ａ＋Ｔａｂ［ｄ10，ｄ6，ｄ2］。さらに、手順（４）において、Windowのシフト幅である１ビットに応じて、２Ａを算出する。すなわち、（４）Ａ＝２Ａ。また、手順（５）において、補正後のスカラー値ｄの上位第３ビットから３ビットおきにビット値を読み出すことによって索引値を得て、Windowテーブル７５ｆのテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋Ｔａｂ［ｄ9，ｄ5，ｄ1］。
【０１６２】
さらに、手順（６）において、Windowのシフト幅である１ビットに応じて、２Ａを算出する。すなわち、（６）Ａ＝２Ａ。そして、手順（７）において、スカラー値ｄの上位第４ビットから３ビットおきにビット値を読み出すことによって索引値を得て、Windowテーブル７５ｆのテーブル値を読み出し、Ａに加算する。すなわち、（７）Ａ＝Ａ＋Ｔａｂ［ｄ8，ｄ4，ｄ0］＝ｄＧ。
【０１６３】
このように手順（０）を除き、ＰＡ対策なしの場合の手順と同じになる。但し、索引値「０００」に対してもテーブル値「ｘＧ」が読み出されるので、ゼロの加算は絶対に行われない。すなわち、図１２（Ｂ）のような消費電力波形は出現しない。また、ダミー演算のように変数のためのＲＡＭ領域を増加させる必要もない。
【０１６４】
次に、図３４に示したWindowテーブル７５ｆを一般化したものを図３５に示す。実施の形態１−Ａなどと同様に、索引値ｙを（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）と表すものとする。そうすると、右からｘ番目のビットはｙx-1と表される。また、Window幅はｋビットとする。
【０１６５】
そうすると、図３５に示すように、索引値ｙのテーブル値は、以下のように表される。
（ｙk-1×２┌n/k┐*(k-1)＋ｙk-2×２┌n/k┐*(k-2)＋・・・＋ｙ1×２┌n/k┐*1＋ｙ0×２┌n/k┐*0）Ｇ＋ｘＧ
【０１６６】
上でも述べたように、ｋビットの索引値の右からｊ番目のビットは、ｙj-1×２┌n/k┐*(j-1)に対応する。櫛形Window法の場合には、スカラー値ｄから（┌n/k┐−１）おきにｋビットを読み出すので、ｋビットの索引値の右からｊ番目のビットについての２のべき指数は、当該ｊ番目のビットが担当する、スカラー値ｄにおける相対ビット位置┌n/k┐＊（ｊ−１）となる。
【０１６７】
従って、索引値「０」のテーブル値はテーブル補正値の「ｘＧ」であり、索引値「１」のテーブル値は、ｙ0のみ「１」であるから２0Ｇ＋ｘＧとなる。索引値「２」のテーブル値は、ｙ1のみ「１」であるから２┌n/k┐*1Ｇ＋ｘＧとなる。さらに、索引値「２k−１」のテーブル値は、ｙk-1乃至ｙ0の全てが「１」であるから、（２┌n/k┐*(k-1)＋２┌n/k┐*(k-2)＋・・・＋２┌n/k┐*1＋２┌n/k┐*0）Ｇ＋ｘＧとなる。
【０１６８】
次に、図３６を用いて、楕円曲線暗号演算装置の処理フローについて説明する。まず、制御部３１ｆは、ＲＡＭ９又はＲＯＭ７に格納されているｎビットのスカラー値ｄ及び楕円曲線上のベースポイントＧを読み出す（ステップＳ９１）。そして、補正部３３ｆは、スカラー値ｄの補正を実施する（ステップＳ９３）。すなわち、補正値として「１」が┌n/k┐個連結された補正値（１１１．．．１）とスカラー値ｘの積を算出する。この処理は簡単な処理であるからＣＰＵ３で容易に実施することができる。従って、ｄ＝ｄ−（１１１．．．１）ｘを算出する。
【０１６９】
また、制御部３１ｆは、スカラー値ｄの最上位ビットから（┌n/k┐−１）ビットおきにｋビット幅のwindowでビット値を読み出して、索引値を取得する（ステップＳ９５）。補正後のスカラー値ｄを｛ｄn-1||ｄn-2||・・・ｄ1||ｄ0｝のような形で表すとすると、ｄから読み出される値ｗ┌n/k┐-1は、以下のように表される。
ｗ┌n/k┐-1＝｛ｄ┌n/k┐*(k-1)+┌n/k┐-1||・・・ｄ┌n/k┐*1+┌n/k┐-1||ｄ┌n/k┐*0+┌n/k┐-1｝
【０１７０】
そして、制御部３１ｆは、Windowテーブル７５ｆから索引値ｗ┌n/k┐-1に対応するテーブル値を読み出し、変数Ａに設定する（ステップＳ９７）。すなわち、以下のように表される。
Ａ＝Ｗ［ｗ┌n/k┐-1］
Ｗ［ｚ］は、Windowテーブル７５ｆにおいて索引値ｚに対応付けられているテーブル値である。
【０１７１】
そして、制御部３１ｆは、カウンタｉに、┌n/k┐−２を設定する（ステップＳ９９）。
【０１７２】
さらに、制御部３１ｆは、補正後のスカラー値ｄからカウンタｉで規定されるビット位置からｋビット幅のwindowでビット値を（┌n/k┐−１）ビットおきに読み出して、索引値を取得する（ステップＳ１０１）。
【０１７３】
ｄから読み出される値ｗiは、以下のように表される。
ｗi＝｛ｄk*i+(k-1)||・・・ｄk*i+1||ｄk*i+0｝
すなわち、Windowが１ビット右シフトされることになる。
【０１７４】
そして、制御部３１ｆは、変数Ａの２倍演算を、windowの右シフト幅である１回だけ演算器５の２倍演算部５３に実施させる（ステップＳ１０３）。図３６では、ＥＣＤＢＬ（Ａ）で、楕円曲線上におけるＡの２倍演算を表す。
【０１７５】
さらに、制御部３１ｆは、変数Ａと、索引値ｗiでWindowテーブル７５ｆを検索することにより得られるテーブル値Ｗ[ｗi］との加算演算を、演算器５の加算演算部５１に実施させる（ステップＳ１０５）。図３６は、ＥＣＡＤＤ（Ａ，Ｗ[ｗi］）で、楕円曲線上におけるＡとＷ[ｗi］の加算演算を表す。
【０１７６】
そして、制御部３１ｆは、カウンタｉの値を１デクリメントし（ステップＳ１０７）、ｉが０以上であるか判断する（ステップＳ１０９）。ｉが０以上であればステップＳ１０１に戻る。すなわち、ｉが０未満になるまでステップＳ１０１乃至Ｓ１０９を繰り返す。
【０１７７】
ｉが０未満になると、制御部３１ｆは、このようにして得られた変数Ａの値を、指定された出力先に出力する（ステップＳ１１１）。変数Ａの値は、例えば通信部１１から外部に出力される場合もあれば、他の演算プログラムに出力されて処理に用いられる。
【０１７８】
以上述べたように、Windowテーブル７５ｆにおいて通常のテーブル値に非ゼロのテーブル補正値ｘＧを加算しておくことによって、どのようなスカラー値ｄに対しても同じ演算が繰り返されるようになる。すなわちＰＡが行われてもスカラー値ｄのビットを盗み取られることはない。また、処理としてはステップＳ９３だけが追加されているので、処理速度の面でもＰＡ対策なしの場合に比してパフォーマンスが大幅に落ちることはない。また、ＲＡＭ９において使用される容量は、ＰＡ対策なしの場合と同じである。ＲＯＭ７において使用される容量もＰＡなしの場合と同様である。すなわち、メモリ特にＲＡＭの容量が限られているスマートカードのような実装形態において、本実施の形態は特に有用となる。
【０１７９】
［実施の形態５］
本実施の形態では、最初に２つのWindowテーブルを用いてスカラー値ｄ又は演算結果の補正なしでＰＡ対策を実施する例を説明する。
【０１８０】
本実施の形態に係る楕円曲線暗号演算装置１００の装置構成例を図３７に示す。図１７に示した楕円曲線暗号演算装置１００と同じ構成要素については同じ参照番号が付されている。本楕円曲線暗号演算装置１００では、バス１に、ＣＰＵ（Central Processing Unit）３と、演算器５と、ＲＯＭ７と、ＲＡＭ９と、通信部１１とが接続されている。ＲＯＭ７は、以下で説明する処理をＣＰＵ３に実行させるための演算プログラム７１ｇと、櫛形Window法のWindowテーブルをベースとしたものであって以下で述べるWindowテーブルａ及びｂとが記録されている。
【０１８１】
演算器５は、実施の形態１−Ａと同じ加算演算部５１及び２倍演算部５３とを有する。また、演算プログラム７１ｇをＣＰＵ３が実行すると、制御部３１ｇが実現される。以下で詳細に述べるが、本実施の形態では、補正を行わない。
【０１８２】
また、外部装置との通信を行うため通信部１１を設ける例を示しているが、他の機能を実現するための装置が設けられる場合もある。ＲＡＭ９は、ＣＰＵ３が各種処理を実施する際に用いるデータを格納するものであり、本実施の形態では、楕円曲線におけるベースポイントＧのスカラー値ｄ倍を算出するために用いる変数Ａのための領域が用意される。その他にも演算に必要なデータもＲＡＭ９には格納されるが、耐タンパ性を保持させるために追加で必要な領域は存在しない。
【０１８３】
まず、本実施の形態５についての演算処理を具体的な例を用いて説明する。本具体例のためのWindowテーブルａ及びｂの内容を図３８Ａ（ａ）及び（ｂ）に示す。図３８Ａ（ａ）及び（ｂ）の例では、楕円曲線上の点Ｇのスカラー値ｄ倍を算出する場合を念頭に、スカラー値ｄが１８ビットであり、Window幅が３ビットであるものとする。また、スカラー値ｄの上位９ビットのブロックを、Windowテーブルａが担当し、下位９ビットのブロックを、Windowテーブルｂが担当する。従って、このWindowテーブルａ及びｂの要素数は各々２3＝８個である。そして、図１１に示したＰＡ対策なしの場合と比較すると、図３８Ａ（ａ）の上側テーブルの方は、各テーブル値にテーブル補正値−Ｆが加えられていることが分かる。また、図３８Ａ（ｂ）の下側テーブルの方は、各テーブル値にテーブル補正値＋Ｆが加えられていることが分かる。すなわち、上側テーブルのテーブル補正値−Ｆと下側テーブルの補正値＋Ｆによって、テーブル補正値が相殺されてゼロになるようにする。これによって、複数のWindowテーブルを用いる場合には、スカラー値ｄ又は演算結果の補正を実施せずとも、ＰＡ対策ができるようになる。
【０１８４】
具体的には、上側テーブルであるWindowテーブルａにおいては、索引「０００」に対応付けて０Ｇ−Ｆ＝−Ｆを設定し、索引「００１」に対応付けて２9Ｇ−Ｆを設定し、索引「０１０」に対応付けて２12Ｇ−Ｆを設定し、索引「０１１」に対応付けて２12Ｇ＋２9Ｇ−Ｆを設定し、索引「１００」に対応付けて２15Ｇ−Ｆを設定し、索引「１０１」に対応付けて２15Ｇ＋２9Ｇ−Ｆを設定し、索引「１１０」に対応付けて２15Ｇ＋２12Ｇ−Ｆを設定し、索引「１１１」に対応付けて２15Ｇ＋２12Ｇ＋２9Ｇ−Ｆを設定するようになっている。Windowテーブルａのテーブル補正値−Ｆは、Windowテーブルｂのテーブル補正値＋Ｆとの加算結果が「０」になればよい。ここで、補正値Ｆは、楕円曲線上の点である。
【０１８５】
また、下側テーブルであるWindowテーブルｂにおいては、索引「０００」に対応付けて０Ｇ＋Ｆ＝＋Ｆを設定し、索引「００１」に対応付けて２0Ｇ＋Ｆを設定し、索引「０１０」に対応付けて２3Ｇ＋Ｆを設定し、索引「０１１」に対応付けて２3Ｇ＋２0Ｇ＋Ｆを設定し、索引「１００」に対応付けて２6Ｇ＋Ｆを設定し、索引「１０１」に対応付けて２6Ｇ＋２0Ｇ＋Ｆを設定し、索引「１１０」に対応付けて２6Ｇ＋２3Ｇ＋Ｆを設定し、索引「１１１」に対応付けて２6Ｇ＋２3Ｇ＋２0Ｇ＋Ｆを設定するようになっている。
【０１８６】
以下で一般的なテーブル値については数式で表すが、上側テーブルであるWindowテーブルａにおける索引値の上位１ビットの値が２15Ｇに対応し、索引値の２番目のビットの値が２12に対応し、索引値の３番目のビットの値が２9に対応している。従って、索引値の各ビットの０又は１に応じて、２15、２12及び２9が加算されたりされなかったりする。なお、２のべき指数は、Window（すなわち索引値）において各ビットが担当する、スカラー値ｄのブロックにおける相対ビット位置、及びスカラー値ｄ中の当該ブロックの相対位置に応じて設定される。すなわち、下側テーブルであるWindowテーブルｂは、スカラー値ｄの下位９ビットの下位ブロックを担当しており、その中で、図１１でも示したように（┌n/2k┐−１）＝２ビットおきにスカラー値ｄのビット値を読み出すので、下側テーブルであるWindowテーブルｂについてのWindowの最下位ビットについてのべき指数が「０」とすると、２番目のビットについてのべき指数は「３」であり、最上位のビットについてのべき指数は「６」である。同様に、上側テーブルであるWindowテーブルａは、スカラー値ｄの上位９ビットの上位ブロックを担当しており、その中で、図１１でも示したように（┌n/2k┐−１）＝２ビットおきにスカラー値ｄのビット値を読み出すので、上側テーブルであるWindowテーブルａについてのWindowの最下位ビットについてのべき指数は「９」となり、２番目のビットについてのべき指数は「１２」となり、最上位のビットについてのべき指数は「１５」となる。
【０１８７】
このようなWindowテーブルａ及びｂを用いた具体的な演算手順は図３８Ｂに示すとおりである。最初に、手順（１）において、ｄの上位半分のうち２ビットおきにｄにおける３ビットを索引として抽出し、Windowテーブルａのテーブル値を読み出す。これを変数Ａに代入する。すなわち、（１）Ａ＝ＴａｂH［ｄ17，ｄ14，ｄ11］。ＴａｂHについては、上側テーブルであるWindowテーブルａのテーブル値を表す。次に、手順（２）において、ｄの下位半分のビットブロックのうち２ビットおきにｄにおける３ビットを索引として抽出し、Windowテーブルｂのテーブル値を読み出し、Ａに加算する。すなわち、（２）Ａ＝Ａ＋ＴａｂL［ｄ8，ｄ5，ｄ2］。ＴａｂLについては、下側テーブルであるWindowテーブルｂのテーブル値を表す。
【０１８８】
本実施の形態のようなテーブル補正値を採用すれば、手順（１）及び（２）で−Ｆ＋Ｆ＝０（ゼロ）で、テーブル補正値が相殺されている。
【０１８９】
そして、Windowのシフト幅１ビットに応じて、２Ａを算出する。すなわち、（３）Ａ＝２Ａ。また、手順（４）において、ｄにおいて手順（１）の状態からwindowを１ビット右シフトさせて上位半分のビットブロックの次の３ビットを索引として抽出し、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋ＴａｂH［ｄ16，ｄ13，ｄ10］。また、手順（５）において、ｄにおいて手順（２）の状態からwindowを１ビット右シフトさせて下位半分のビットブロックの次の３ビットを索引として抽出し、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（５）Ａ＝Ａ＋ＴａｂL［ｄ7，ｄ4，ｄ1］。
【０１９０】
手順（１）及び（２）と同様に、手順（３）及び（４）においてもテーブル補正値−Ｆ＋Ｆ＝０（ゼロ）で、テーブル補正値が相殺されている。
【０１９１】
さらに、手順（６）において、Windowのシフト幅１ビットに応じて、２Ａを算出する。すなわち、（６）Ａ＝２Ａ。また、手順（７）において、ｄにおいて手順（４）の状態からwindowを１ビット右シフトさせて上位半分のビットブロックの次の３ビットを索引として抽出し、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（７）Ａ＝Ａ＋ＴａｂH［ｄ15，ｄ12，ｄ9］。また、手順（８）において、ｄにおいて手順（５）の状態からwindowを１ビット右シフトさせて下位半分のビットブロックの次の３ビットを索引として抽出し、Windowテーブルのテーブル値を読み出し、Ａに加算する。すなわち、（８）Ａ＝Ａ＋ＴａｂL［ｄ6，ｄ3，ｄ0］＝ｄＧ。
【０１９２】
手順（１）及び（２）と同様に、手順（７）及び（８）においてもテーブル補正値−Ｆ＋Ｆ＝０（ゼロ）で、テーブル補正値が相殺されている。
【０１９３】
このように、スカラー値ｄ又は演算結果の補正を行わずとも、テーブル補正値が相殺されるので、演算処理が高速化される。なお、櫛形Windowを用いており且つWindowテーブルも２つ用いているので、より処理が高速化される。
【０１９４】
以上のように演算処理そのものは図１１で説明したものと同じであるが、Windowテーブルａ及びｂの構成を上で述べたように変更しているため、ゼロの加算は絶対に行われない。すなわち、図１２（Ｂ）のような消費電力波形は出現しない。また、ダミー演算のように変数のためのＲＡＭ領域を増加させる必要もない。
【０１９５】
次に、図３８に示したWindowテーブルａ及びｂを一般化したものを図３９及び図４０に示す。実施の形態１−Ａと同様に、索引値ｙを（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）と表すものとする。そうすると、右からｘ番目のビットはｙx-1と表される。また、Window幅は、各Windowテーブルについてｋビットとする。スカラー値ｄはｎビットであるものとする。
【０１９６】
そうすると、図４０に示すように、下側テーブルであるWindowテーブルｂにおける索引値ｙのテーブル値は、以下のように表される。
（ｙk-1×２┌n/2k┐*(k-1)＋ｙk-2×２┌n/2k┐*(k-2)＋・・・＋ｙ1×２┌n/2k┐*1＋ｙ0×２┌n/2k┐*0）Ｇ＋Ｆ
【０１９７】
下側テーブルであるWindowテーブルｂにおいて、ｋビットの索引値の右からｉ番目のビットは、ｙi-1×２┌n/2k┐*(i-1)に対応する。櫛形Window法の場合には、スカラー値ｄから（┌n/2k┐−１）おきにｋビットを読み出すので、ｋビットの索引値の右からｉ番目のビットについての２のべき指数は、当該ｉ番目のビットが担当する、スカラー値ｄの下位ビットブロックにおける相対ビット位置┌n/2k┐＊（ｉ−１）となる。
【０１９８】
一方、図３９に示すように、上側テーブルであるWindowテーブルａにおける索引値ｙのテーブル値は、以下のように表される。
（ｙk-1×２┌n/2k┐*k+┌n/2k┐*(k-1)+＋ｙk-2×２┌n/2k┐*k+┌n/2k┐*(k-2)＋・・・＋ｙ1×２┌n/2k┐*k+┌n/2k┐*1＋ｙ0×２┌n/2k┐*k+┌n/2k┐*0）Ｇ−Ｆ
【０１９９】
上側テーブルであるWindowテーブルａにおいて、ｋビットの索引値の右からｉ番目のビットは、ｙi-1×２┌n/2k┐*k+┌n/2k┐*(i-1)に対応する。Windowテーブル２つで櫛形Window法の場合には、スカラー値ｄから（┌n/2k┐−１）おきにｋビットを読み出し、上側テーブルの場合にはスカラー値ｄの上位ビットブロックを担当するので、ｋビットの索引値の右からｉ番目のビットについての２のべき指数は、下側テーブルの場合に比して┌n/2k┐＊ｋだけ上乗せされて、ｉ番目のビットが担当する、スカラー値ｄの上位ビットブロックにおける相対ビット位置┌n/2k┐＊ｋ＋┌n/2k┐＊（ｉ−１）となる。
【０２００】
次に、図４１を用いて、楕円曲線暗号演算装置の処理フローについて説明する。まず、制御部３１ｇは、ＲＡＭ９又はＲＯＭ７に格納されているｎビットのスカラー値ｄ及び楕円曲線上のベースポイントＧを読み出す（ステップＳ１２１）。そして、制御部３１ｇは、スカラー値ｄの上位ビットブロックにおける最上位ビットから（┌n/2k┐−１）ビットおきにｋビット幅のwindowでビット値を読み出して、上側テーブルであるWindowテーブルａのための索引値を取得する（ステップＳ１２３）。スカラー値ｄを｛ｄn-1||ｄn-2||・・・ｄ1||ｄ0｝のような形で表すとすると、ｄから読み出される値ｗ┌n/2k┐-1,1は、以下のように表される。
ｗ┌n/2k┐-1,1＝｛ｄ┌n/2k┐*(k-1)+┌n/2k┐-1+┌n/2┐||・・・ｄ┌n/2k┐*1+┌n/2k┐-1+┌n/2┐||ｄ┌n/2k┐*0+┌n/2k┐-1+┌n/2┐｝
【０２０１】
上でも述べたが、┌n/2k┐は、ｎ／２ｋより大きい最小の整数を表す。例えばスカラー値ｄは全体では１８ビットであるがテーブル２つで上位半分のビットブロックのビット数は９である。そして、ｋ＝３であれば、┌n/2k┐-1＝２となる。また、┌n/2k┐＊(k-1)＋┌n/2k┐−１＋┌n/2┐＝３＊２＋３−１＋９＝１７となる。１７は最上位ビットの番号である。
【０２０２】
また、制御部３１ｇは、スカラー値ｄの下位ビットブロックにおける最上位ビットから（┌n/2k┐−１）ビットおきにｋビット幅のwindowでビット値を読み出して、下側テーブルであるWindowテーブルｂのための索引値を取得する（ステップＳ１２５）。ｄから読み出される値ｗ┌n/2k┐-1,0は、以下のように表される。
ｗ┌n/2k┐-1,0＝｛ｄ┌n/2k┐*(k-1)+┌n/2k┐-1||・・・ｄ┌n/2k┐*1+┌n/2k┐-1||ｄ┌n/2k┐*0+┌n/2k┐-1｝
【０２０３】
例えばスカラー値ｄは全体では１８ビットであるがテーブル２つで上位半分のビットブロックのビット数は９である。そして、ｋ＝３であれば、┌n/2k┐-1＝２となる。また、┌n/2k┐＊(k-1)＋┌n/2k┐−１＝３＊２＋３−１＝８となる。８は下位ビットブロックの最上位ビットの番号である。
【０２０４】
そして、制御部３１ｇは、Windowテーブルａから索引値ｗ┌n/2k┐-1,1に対応するテーブル値を読み出し、変数Ａに設定する（ステップＳ１２７）。すなわち、以下のように表される。
Ａ＝Ｗ1［ｗ┌n/2k┐-1,1］
Ｗ1［ｚ］は、Windowテーブルａにおいて索引値ｚに対応付けられているテーブル値である。
【０２０５】
さらに、制御部３１ｇは、Windowテーブルｂにおいて索引値ｗ┌n/2k┐-1,0に対応するテーブル値Ｗ0と、変数Ａとの加算演算を、演算器５の加算演算部５１に実施させる（ステップＳ１２９）。図４１では、ＥＣＡＤＤ（Ａ，Ｗ0[ｗ┌n/2k┐-1,0］）で、楕円曲線上におけるＡとＷ0[ｗ┌n/2k┐-1,0］の加算演算を表す。
【０２０６】
そして、制御部３１ｇは、カウンタｉに、┌n/k┐−２を設定する（ステップＳ１３１）。
【０２０７】
さらに、制御部３１ｇは、スカラー値ｄの上位ビットブロックからカウンタｉで規定されるビット位置からｋビット幅のwindowでビット値を（┌n/2k┐−１）ビットおきに読み出して、索引値ｗi,1を取得する（ステップＳ１３３）。
【０２０８】
ｄから読み出される値ｗi,1は、以下のように表される。
ｗi,1＝｛ｄ┌n/2k┐*(k-1)+i+┌n/2┐||・・・ｄ┌n/2k┐*1+i+┌n/2┐||ｄ┌n/2k┐*0+i+┌n/2┐｝
すなわち、Windowが１ビット右シフトされることになる。
【０２０９】
また、制御部３１ｇは、スカラー値ｄの下位ビットブロックからカウンタｉで規定されるビット位置からｋビット幅のwindowでビット値を（┌n/2k┐−１）ビットおきに読み出して、索引値ｗi,0を取得する（ステップＳ１３５）。
【０２１０】
ｄから読み出される値ｗi,0は、以下のように表される。
ｗi,0＝｛ｄ┌n/2k┐*(k-1)+i||・・・ｄ┌n/2k┐*1+i||ｄ┌n/2k┐*0+i｝
【０２１１】
そして、制御部３１ｇは、変数Ａの２倍演算を、windowの右シフト幅である１回だけ演算器５の２倍演算部５３に実施させる（ステップＳ１３７）。図４１では、ＥＣＤＢＬ（Ａ）で、楕円曲線上におけるＡの２倍演算を表す。
【０２１２】
さらに、制御部３１ｇは、変数Ａと、索引値ｗi,1でWindowテーブルａを検索することにより得られるテーブル値Ｗ1[ｗi,1］との加算演算を、演算器５の加算演算部５１に実施させる（ステップＳ１３９）。
【０２１３】
また、制御部３１ｇは、変数Ａと、索引値ｗi,0でWindowテーブルｂを検索することにより得られるテーブル値Ｗ0[ｗi,0］との加算演算を、演算器５の加算演算部５１に実施させる（ステップＳ１４１）。
【０２１４】
そして、制御部３１ｇは、カウンタｉの値を１デクリメントし（ステップＳ１４３）、ｉが０以上であるか判断する（ステップＳ１４５）。ｉが０以上であればステップＳ１３３に戻る。すなわち、ｉが０未満になるまでステップＳ１３３乃至Ｓ１４５を繰り返す。
【０２１５】
ｉが０未満になると、制御部３１ｇは、このようにして得られた変数Ａの値を、指定された出力先に出力する（ステップＳ１４７）。変数Ａの値は、例えば通信部１１から外部に出力される場合もあれば、他の演算プログラムに出力されて処理に用いられる。
【０２１６】
以上述べたように、Windowテーブルａ及びｂにおいて通常のテーブル値に非ゼロのテーブル補正値を加算しておけば、どのようなスカラー値ｄに対しても同じ演算が繰り返されるようになる。すなわちＰＡが行われてもスカラー値ｄのビットを盗み取られることはない。一方、テーブル補正値は、２つのテーブルで相殺されるように設定されるので、演算処理はＰＡ対策なしの場合と完全に同じになっている。すなわち、処理速度の面で、ＰＡ対策なしと同じである。また、ＲＡＭ９において使用される容量は、ＰＡ対策なしの場合と同じである。ＲＯＭ７において使用される容量も同様に、ＰＡ対策なしの場合と同じである。すなわち、メモリ特にＲＡＭの容量が限られているスマートカードのような実装形態において、本実施の形態は特に有用となる。
【０２１７】
［実施の形態６］
実施の形態５では、２つのWindowテーブルａ及びｂを用いる例を示したが、テーブルの数は２に限定されるものではない。例えば、一般的にｔ個設ける場合について説明する。
【０２１８】
本実施の形態に係る楕円曲線暗号演算装置１００の装置構成例を図４２に示す。図１７に示した楕円曲線暗号演算装置１００と同じ構成要素については同じ参照番号が付されている。本楕円曲線暗号演算装置では、バス１に、ＣＰＵ３と、演算器５と、ＲＯＭ７と、ＲＡＭ９と、通信部１１とが接続されている。ＲＯＭ７は、以下で説明する処理をＣＰＵ３に実行させるための演算プログラム７１ｈと、櫛形Window法のWindowテーブルをベースとしたものであって以下で述べるWindowテーブル０乃至（ｔ−１）とが記録されている。
【０２１９】
演算器５は、実施の形態１−Ａと同じ加算演算部５１及び２倍演算部５３とを有する。また、演算プログラム７１ｈをＣＰＵ３が実行すると、制御部３１ｈが実現される。実施の形態５と同様に、本実施の形態においては補正を行わない。
【０２２０】
また、外部装置との通信を行うため通信部１１を設ける例を示しているが、他の機能を実現するための装置が設けられる場合もある。ＲＡＭ９は、ＣＰＵ３が各種処理を実施する際に用いるデータを格納するものであり、本実施の形態では、楕円曲線におけるベースポイントＧのスカラー値ｄ倍を算出するために用いる変数Ａのための領域が用意される。その他にも演算に必要なデータもＲＡＭ９には格納されるが、耐タンパ性を保持させるために追加で必要な領域は存在しない。
【０２２１】
Windowテーブル０乃至（ｔ−１）のうちのWindowテーブルｊに格納されるテーブル値は、以下のように表される。なお、索引値ｙを（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）と表すものとする。そうすると、右からｘ番目のビットはｙx-1と表される。また、Window幅は、各Windowテーブルについてｋビットとする。さらに、スカラー値ｄは、ｎビットであるものとする。
【０２２２】
【数１】
0005446678.tif 000002
Ｋ(n, k, m, t, j)＝┌n/(t*k)┐×ｋ×ｊ＋┌n/(t*k)┐×ｍ
なお、以下では、ｅ＝┌n/(t*k)┐を示すものとする。
【０２２３】
上記のＫ(n, k, m, t, j)において、┌n/(t*k)┐×ｋ×ｊの項は、同じWindowテーブルであれば同じである。すなわち、スカラー値ｄにおける該当ビットブロックの相対位置に応じた値になる。ｍはｙmに対応する。従って、┌n/(t*k)┐×ｍは、該当ビットブロックにおいてwindowの各ビットが担当する相対ビット位置に応じた値となる。
【０２２４】
本実施の形態では、各Windowテーブルについてのテーブル補正値Ｆjの総和がゼロ点となるように設定する。すなわち、以下のように表される。
Ｆ0＋Ｆ1＋・・・＋Ｆt-1＝０
【０２２５】
次に、図４３を用いて、楕円曲線暗号演算装置の処理フローについて説明する。まず、制御部３１ｈは、ＲＡＭ９又はＲＯＭ７に格納されているｎビットのスカラー値ｄ及び楕円曲線上のベースポイントＧを読み出す（ステップＳ１６１）。そして、制御部３１ｈは、Windowテーブル０乃至（ｔ−１）の各々が担当するスカラー値ｄのビットブロックの最上位ビットから（┌n/(t*k)┐−１)ビットおきにｋビット幅のwindowでビット値を読み出して、索引値ｗe-1,0乃至ｗe-1,t-1を取得する（ステップＳ１６３）。より具体的には、以下のように表される。
ｗe-1,0＝｛ｄe*k*0+e*(k-1)+e-1||ｄe*k*0+e*(k-2)+e-1||・・||ｄe*k*0+e*0+e-1｝
ｗe-1,j＝｛ｄe*k*j+e*(k-1)+e-1||ｄe*k*j+e*(k-2)+e-1||・・||ｄe*k*j+e*0+e-1｝
ｗe-1,t-1＝｛ｄe*k*(t-1)+e*(k-1)+e-1||ｄe*k*(t-1)+e*(k-2)+e-1||・・||ｄe*k*(t-1)+e*0+e-1｝
【０２２６】
また、制御部３１ｈは、スカラー値ｄの最下位ビットブロックを担当するWindowテーブル０から、索引値ｗe-1,0に対応するテーブル値Ｗ0［ｗe-1,0］を読み出し、変数Ａに設定する（ステップＳ１６５）。すなわち、以下のように表される。
Ａ＝Ａ＋Ｗ0［ｗe-1,0］
Ｗ0［ｗe-1,0］は、Windowテーブル０において索引値（ｅ−１）に対応付けられているテーブル値である。
【０２２７】
さらに、制御部３１ｈは、ｊ＝１からｊ＝t-1まで順番に、Windowテーブルｊにおいて索引値（ｅ−１）に対応付けられているテーブル値Ｗj［ｗe-1,j］と、変数Ａとの加算演算を、演算器５の加算演算部５１に繰り返し実施させる（ステップＳ１６７）。図４１は、ＥＣＡＤＤ（Ａ，Ｗj[ｗe-1,j］）で、楕円曲線上におけるＡとＷj[ｗe-1,j］の加算演算を表す。
【０２２８】
そして、制御部３１ｈは、カウンタｉに、ｅ−２を設定する（ステップＳ１６９）。これによって、windowが１ビット右シフトされたことになる。
【０２２９】
さらに、制御部３１ｈは、Windowテーブル０乃至（ｔ−１）の各々が担当するスカラー値ｄのビットブロックの次のビットから（┌n/(t*k)┐−１)ビットおきにｋビット幅のwindowでビット値を読み出して、索引値ｗi,0乃至ｗi,t-1を取得する（ステップＳ１７１）。より具体的には、以下のように表される。
ｗi,0＝｛ｄe*k*0+e*(k-1)+i||ｄe*k*0+e*(k-2)+i||・・||ｄe*k*0+e*0+i｝
ｗi,j＝｛ｄe*k*j+e*(k-1)+i||ｄe*k*j+e*(k-2)+i||・・||ｄe*k*j+e*0+i｝
ｗi,t-1＝｛ｄe*k*(t-1)+e*(k-1)+i||ｄe*k*(t-1)+e*(k-2)+i||・・||ｄe*k*(t-1)+e*0+i｝
【０２３０】
そして、制御部３１ｈは、変数Ａの２倍演算を、windowの右シフト幅である１回だけ演算器５の２倍演算部５３に実施させる（ステップＳ１７３）。図４３では、ＥＣＤＢＬ（Ａ）で、楕円曲線上におけるＡの２倍演算を表す。
【０２３１】
さらに、制御部３１ｈは、ｊ＝０からｊ＝t-1まで順番に、Windowテーブルｊにおいて索引値ｉに対応付けられているテーブル値Ｗj［ｗi,j］と、変数Ａとの加算演算を、演算器５の加算演算部５１に繰り返し実施させる（ステップＳ１７５）。
【０２３２】
また、制御部３１ｈは、カウンタｉの値を１デクリメントし（ステップＳ１７７）、ｉが０以上であるか判断する（ステップＳ１７９）。ｉが０以上であればステップＳ１７１に戻る。すなわち、ｉが０未満になるまでステップＳ１７１乃至Ｓ１７９を繰り返す。
【０２３３】
ｉが０未満になると、制御部３１ｈは、このようにして得られた変数Ａの値を、指定された出力先に出力する（ステップＳ１８１）。変数Ａの値は、例えば通信部１１から外部に出力される場合もあれば、他の演算プログラムに出力されて処理に用いられる。
【０２３４】
以上述べたように、Windowテーブル０乃至（ｔ−１）において通常のテーブル値に非ゼロのテーブル補正値を加算しておけば、どのようなスカラー値ｄに対しても同じ演算が繰り返されるようになる。すなわちＰＡが行われてもスカラー値ｄのビットを盗み取られることはない。一方、テーブル補正値は、ｔ個のテーブルで相殺されるように設定されるので、演算処理はＰＡ対策なしの場合と完全に同じになっている。すなわち、処理速度の面でもＰＡ対策なしの場合と同じである。また、ＲＡＭ９において使用される容量は、ＰＡ対策なしの場合と同じである。ＲＯＭ７において使用される容量も同様に、ＰＡ対策なしの場合と同じである。すなわち、メモリ特にＲＡＭの容量が限られているスマートカードのような実装形態において、本実施の形態は特に有用となる。
【０２３５】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば実施の形態５及び６については、櫛形Ｗｉｎｄｏｗ法を前提としているが、通常のＷｉｎｄｏｗ法を採用することも可能である。
【０２３６】
さらに、実施の形態５及び６で各ビットブロックに用いられるwindow幅については統一されていたが、異なるビット幅にしてもよい。また、ビットブロックのサイズを異なるようにしても良い。
【０２３７】
また、上で述べた楕円暗号演算装置では、演算器５をＣＰＵ３とは別に設ける例を示しているが、例えばＣＰＵ３によりその機能を実施するようにしても良い。さらに、ＣＰＵ３が複数設けられている場合には、演算器５が保持する機能を他のＣＰＵで実現するようにしても良い。さらに１つのＣＰＵ３で複数のコアを有する場合にも同様である。
【０２３８】
以上述べた本実施の形態をまとめると以下のようになる。
【０２３９】
第１の態様に係る楕円曲線暗号演算装置（図４４）は、楕円曲線上の所定の点Ｇのスカラー倍算を実施する楕円曲線暗号演算装置であって、（Ａ）ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当するスカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に点Ｇを乗じた基本テーブル値に対して非ゼロのテーブル補正値を加えたテーブル値が格納されているウィンドウテーブル（図４４の１１１０）を格納するデータ格納部（図４４の１１００）と、（Ｂ）ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値をスカラー値ｄから読み出すことにより索引値を生成して当該索引値でウィンドウテーブルを検索してテーブル値を読み出し、読み出したテーブル値を用いて２倍演算及び加算演算を実施する演算処理部（図４４の１２００）と、（Ｃ）演算処理部の演算結果に対してテーブル補正値に応じた所定の補正値で補正を実施する補正部（図４４の１３００）とを有する。
【０２４０】
このようなウィンドウテーブルを予め用意しておくことによって、どのような索引値であっても対応するテーブル値はゼロとならない。すなわち、補正部の処理以外は、ＰＡ対策無しの場合と同じ処理を実施しても、消費電力の波形はｄのビット値に応じて変化することはないので、ＳＰＡに対する耐タンパ性が保持できている。また、余分なＲＡＭ領域も必要ない。
【０２４１】
また、上で述べた演算処理部が、変数に格納されている値に対して楕円曲線上における２倍演算を実施して演算結果を当該変数に格納する２倍演算部と、変数に格納されている値と読み出されたテーブル値との、楕円曲線上における加算演算を実施して、演算結果を当該変数に格納する加算演算部と、制御部とを有するようにしても良い。そのような場合には、制御部が、スカラー値ｄの最上位ビットから、ウィンドウの各ビットの担当ビット位置のビット値を読み出して索引値を生成し、当該索引値で前記テーブル格納部に格納されているウィンドウテーブルを検索して第１のテーブル値を読み出して、上記変数に格納するようにしてもよい。そして、ウィンドウを所定のビットシフト幅だけ右シフトさせると共に、２倍演算部に、所定のビットシフト幅に応じた回数分上記変数に格納されている値に対して２倍演算を実施させ、加算演算部に、スカラー値ｄからウィンドウの各ビットの担当ビット位置のビット値を読み出すことにより得られる索引値でウィンドウテーブルを検索して得られる第２のテーブル値について加算演算を実施させる処理を、スカラー値ｄの全てのビットを処理するまで繰り返し行わせるようにしてもよい。
【０２４２】
２倍演算部及び加算演算部は、専用の回路であっても良いし、ＣＰＵとプログラムの組み合わせにて実施するようにしても良い。また、演算処理部については、ＣＰＵと専用の演算器とプログラムとの組み合わせにて実施されるようにしても良い。
【０２４３】
さらに、第１の態様において、テーブル補正値をＦとし、索引値をウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応するテーブル値を、以下のような値に設定するようにしても良い。
（ｙk-1×２k-1＋ｙk-2×２k-2＋・・・＋ｙ1×２1＋ｙ0×２0）Ｇ＋Ｆ
また、上で述べた所定の補正値を、以下のような値に設定するようにしても良い。
（２k*0＋２k*1＋２k*2＋・・・＋２k*(┌n/k┐-1)）Ｆ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
さらに、上で述べた担当ビット位置がｋビット連続しており且つ所定のビットシフト幅がｋビットである場合もある。
【０２４４】
例えば、通常のWindow法を採用する場合には、このような構成が必要となる。
【０２４５】
また、第１の態様において、テーブル補正値をＦとし、索引値をウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応するテーブル値を、以下のように設定しても良い。
（ｙk-1×２┌n/k┐*(k-1)＋ｙk-2×２┌n/k┐*(k-2)＋・・・＋ｙ1×２┌n/k┐*1＋ｙ0×２┌n/k┐*0）Ｇ＋Ｆ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
また、上で述べた所定の補正値を、以下のように設定するようにしても良い。
（２┌n/k┐−１）Ｆ
さらに、上で述べた担当ビット位置が┌n/k┐−１ビットおきであり且つ所定のビットシフト幅が１ビットであるようにしてもよい。
【０２４６】
例えば、櫛形Window法を採用する場合には、このような構成が必要となる。
【０２４７】
さらに、第１の態様において、所定の補正値が予め算出されており且つデータ格納部に格納されているようにしてもよい。このようにすれば、処理のパフォーマンスはあまり低下しない。また、その都度計算するようにしても良い。
【０２４８】
第２の態様に係る楕円曲線暗号演算装置（図４４）は、（Ａ）ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当するスカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に点Ｇを乗じた基本テーブル値に対して点Ｇの第２のスカラー値ｘ倍のテーブル補正値を加えたテーブル値が格納されているウィンドウテーブル（図４４の１１１０）を格納するデータ格納部（図４４の１１００）と、（Ｂ）スカラー値ｄに対して第２のスカラー値ｘに応じた所定の補正値で補正を実施して、第３のスカラー値ｆを生成する補正部（図４４の１３００）と、（Ｃ）ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を第３のスカラー値ｆから読み出すことにより索引値を生成して当該索引値でウィンドウテーブルを検索してテーブル値を読み出し、読み出したテーブル値を用いて２倍演算及び加算演算を実施する演算処理部（図４４の１２００）とを有する。
【０２４９】
このように、ウィンドウテーブルの基本テーブル値に加算するテーブル補正値が、点Ｇの第２のスカラー値ｘ倍である場合には、第１のスカラー値を補正することによって、楕円曲線上の演算が不要になって、補正の処理負荷を下げることができるようになる。なお、第１の態様においても、テーブル補正値をｘＧと設定することも可能である。当然、追加のＲＡＭも不要である。
【０２５０】
また、上で述べた演算処理部が、変数に格納されている値に対して楕円曲線上における２倍演算を実施して演算結果を当該変数に格納する２倍演算部と、変数に格納されている値と読み出されたテーブル値との、楕円曲線上における加算演算を実施し、演算結果を当該変数に格納する加算演算部と、制御部とを有するようにしてもよい。そのような場合、上で述べた制御部が、第３のスカラー値ｆの最上位ビットから、ウィンドウの各ビットの担当ビット位置のビット値を読み出して索引値を生成し、当該索引値でテーブル格納部に格納されているウィンドウテーブルを検索して第１のテーブル値を読み出して、変数に格納するようにしてもよい。さらに、ウィンドウを所定のビットシフト幅だけ右シフトさせると共に、２倍演算部に、所定のビットシフト幅に応じた回数分変数に格納されている値に対して２倍演算を実施させ、加算演算部に、第３のスカラー値ｆからウィンドウの各ビットの担当ビット位置のビット値を読み出すことにより得られる索引値でウィンドウテーブルを検索して得られる第２のテーブル値について加算演算を実施させる処理を、第３のスカラー値ｆの全てのビットを処理するまで繰り返し行わせるようにしてもよい。
【０２５１】
２倍演算部及び加算演算部については、第１の形態と同様に、従来から用いられているものが使用できる。ハードウエアで実装しても良いし、ソフトウエアで実装しても良い。制御部は、ＣＰＵとプログラムとの組み合わせにて実施される場合もある。
【０２５２】
また、第２の態様において、索引値をウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応するテーブル値を、以下のように設定するようにしてもよい。
（ｙk-1×２k-1＋ｙk-2×２k-2＋・・・＋ｙ1×２1＋ｙ0×２0）Ｇ＋ｘＧ
また、上で述べた所定の補正値を、以下のように設定するようにしてもよい。
（２k*0＋２k*1＋２k*2＋・・・＋２k*(┌n/k┐-1)）ｘ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
さらに、担当ビット位置がｋビット連続しており且つ所定のビットシフト幅がｋビットであるようにしてもよい。
【０２５３】
例えば、第２の態様において通常のWindow法を採用する場合にはこのような構成となる。
【０２５４】
さらに、第２の態様において、索引値をウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応するテーブル値を、以下のように設定してもよい。
（ｙk-1×２┌n/k┐*(k-1)＋ｙk-2×２┌n/k┐*(k-2)＋・・・＋ｙ1×２┌n/k┐*1＋ｙ0×２┌n/k┐*0）Ｇ＋ｘＧ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
また、上で述べた所定の補正値を、以下のように設定してもよい。
（２┌n/k┐−１）ｘ
さらに、担当ビット位置が┌n/k┐−１ビットおきであり且つ所定のビットシフト幅が１ビットであるようにしてもよい。
【０２５５】
例えば、第２の態様において櫛形Window法を採用する場合にはこのような構成が必要となる。
【０２５６】
第３の態様に係る楕円曲線暗号演算装置（図４５）は、（Ａ）スカラー値ｄのブロック毎に、当該ブロックに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当するブロック中の相対ビット位置及び前記スカラー値ｄ中の当該ブロックの相対位置に対応する値についての２のべき乗との積の和に前記点Ｇを乗じた基本テーブル値に対して非ゼロのブロックテーブル補正値を加えたテーブル値が格納されているウィンドウテーブル（図４５の１６１０）を格納するデータ格納部（図４５の１６００）と、（Ｂ）ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値をスカラー値ｄの各ブロックから読み出すことにより索引値を生成して当該索引値で各ブロックのウィンドウテーブルを検索してテーブル値を読み出し、読み出したテーブル値を用いて２倍演算及び加算演算を実施する演算処理部（図４５の１７００）とを有する。そして、各ブロックについてのブロックテーブル補正値の総和がゼロとなっている。
【０２５７】
このようなウィンドウテーブルを複数用意することによって、スカラー値ｄの補正も演算結果の補正も不要となるので、ＰＡ対策なしの場合と同様の処理負荷でＰＡ対策を行うことができるようになる。当然、追加のＲＡＭも不要である。
【０２５８】
また、上で述べた演算処理部が、変数に格納されている値に対して楕円曲線上における２倍演算を実施して演算結果を当該変数に格納する２倍演算部と、変数に格納されている値と読み出されたテーブル値との、楕円曲線上における加算演算を実施し、当該変数に格納する加算演算部と、制御部とを有するようにしても良い。そのような場合、上で述べた制御部が、スカラー値ｄの最上位ブロックの最上位ビットから、ウィンドウの各ビットの担当ビット位置のビット値を読み出して索引値を生成し、当該索引値でテーブル格納部に格納されている最上位ブロックについてのウィンドウテーブルを検索して第１のテーブル値を読み出して、上記変数に格納するようにしてもよい。さらに、上で述べた加算演算部に、スカラー値ｄの第２位ブロック以下の各ブロックの最上位ビットからウィンドウの各ビットの担当ビット位置のビット値を読み出すことにより得られる索引値により処理に係るブロックについてのウィンドウテーブルを検索して得られる第２のテーブル値と、変数に格納されている値との加算演算を最下位ブロックまで繰り返し実施させるようにしてもよい。そして、ウィンドウを所定のビットシフト幅だけ各ブロック内において右シフトさせると共に、上で述べた２倍演算部に、所定のビットシフト幅に応じた回数分変数に格納されている値に対して２倍演算を実施させ、加算演算部に、スカラー値ｄの各前記ブロックからウィンドウの各ビットの担当ビット位置のビット値を読み出すことにより得られる索引値により処理に係るブロックについてのウィンドウテーブルを検索して得られる第３のテーブル値についての加算演算を最下位ブロックまで繰り返し実施させる処理を、スカラー値ｄの全てのビットを処理するまで繰り返し行わせるようにしてもよい。
【０２５９】
なお、第３の態様においても、通常のWindow法を採用しても、櫛形Window法を採用してもよい。
【０２６０】
より具体的に、櫛形Window法を採用する場合には、ブロックの番号をｊとし、スカラー値はｎビットとし、ブロックの個数をｔとし、ブロックの番号ｊの前記テーブル補正値をＦjとし、索引値をウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応するテーブル値は、以下のように設定される。
【０２６１】
【数２】
0005446678.tif 000003
Ｋ(n, t, m, t, j)＝┌n/(t*k)┐×ｋ×ｊ＋┌n/(t*k)┐×ｍ
【０２６２】
（┌z┐は、z以上の最小の整数を表す）
また、担当ビット位置が┌n/(k*t)┐−１ビットおきであり且つ所定のビットシフト幅が１ビットである。
【０２６３】
第４の態様に係る楕円曲線暗号演算方法は、ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当するスカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して非ゼロのテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置により実行される。そして、本楕円曲線暗号演算方法は、（Ａ）ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値をスカラー値ｄから読み出すことにより索引値を生成して当該索引値でウィンドウテーブルを検索してテーブル値を読み出し、読み出したテーブル値を用いて２倍演算及び加算演算を実施するステップと、（Ｂ）演算処理部の演算結果に対してテーブル補正値に応じた所定の補正値で補正を実施するステップとを含む。
【０２６４】
第５の態様に係る楕円曲線暗号演算方法は、（Ａ）ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当するスカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して点Ｇの第２のスカラー値ｘ倍のテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置により実行される。そして、本楕円曲線暗号演算方法は、（Ｂ）スカラー値ｄに対して第２のスカラー値ｘに応じた所定の補正値で補正を実施して、第３のスカラー値ｆを生成するステップと、（Ｃ）ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を第３のスカラー値ｆから読み出すことにより索引値を生成して当該索引値でウィンドウテーブルを検索してテーブル値を読み出し、読み出したテーブル値を用いて２倍演算及び加算演算を実施するステップとを含む。
【０２６５】
第６の態様に係る楕円曲線暗号演算方法は、（Ａ）ｎ（ｎは２以上の整数）ビットのスカラー値ｄのブロック毎に、当該ブロックに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当するブロック中の相対ビット位置及びスカラー値ｄ中の当該ブロックの相対位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して非ゼロのブロックテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置により実行される。そして、本楕円曲線暗号演算方法は、（Ｂ）ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値をスカラー値ｄの各前記ブロックから読み出すことにより索引値を生成して当該索引値で各ブロックのウィンドウテーブルを検索してテーブル値を読み出すステップと、（Ｃ）読み出したテーブル値を用いて２倍演算及び加算演算を実施するステップとを含む。そして、各ブロックについてのブロックテーブル補正値の総和がゼロとなっている。
【０２６６】
なお、上で述べたような処理をスマートカードなどの装置に実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【０２６７】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０２６８】
（付記１）
楕円曲線上の所定の点Ｇのスカラー倍算を実施する楕円曲線暗号演算装置であって、
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に前記点Ｇを乗じた基本テーブル値に対して非ゼロのテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部と、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施する演算処理部と、
前記演算処理部の演算結果に対して前記テーブル補正値に応じた所定の補正値で補正を実施する補正部と、
を有する楕円曲線暗号演算装置。
【０２６９】
（付記２）
前記演算処理部が、
変数に格納されている値に対して前記楕円曲線上における２倍演算を実施して演算結果を当該変数に格納する２倍演算部と、
前記変数に格納されている値と読み出された前記テーブル値との、前記楕円曲線上における加算演算を実施して、演算結果を当該変数に格納する加算演算部と、
制御部と、
を有し、
前記制御部が、
前記スカラー値ｄの最上位ビットから、前記ウィンドウの各ビットの担当ビット位置のビット値を読み出して索引値を生成し、当該索引値で前記テーブル格納部に格納されている前記ウィンドウテーブルを検索して第１のテーブル値を読み出して、前記変数に格納し、
前記ウィンドウを所定のビットシフト幅だけ右シフトさせると共に、前記２倍演算部に、前記所定のビットシフト幅に応じた回数分前記変数に格納されている値に対して２倍演算を実施させ、前記加算演算部に、前記スカラー値ｄから前記ウィンドウの各ビットの担当ビット位置のビット値を読み出すことにより得られる索引値で前記ウィンドウテーブルを検索して得られる第２のテーブル値について加算演算を実施させる処理を、前記スカラー値ｄの全てのビットを処理するまで繰り返し行わせる
付記１記載の楕円曲線暗号演算装置。
【０２７０】
（付記３）
前記テーブル補正値をＦとし、前記索引値を前記ウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応する前記テーブル値が、
（ｙk-1×２k-1＋ｙk-2×２k-2＋・・・＋ｙ1×２1＋ｙ0×２0）Ｇ＋Ｆ
であり、
前記所定の補正値が、
（２k*0＋２k*1＋２k*2＋・・・＋２k*(┌n/k┐-1)）Ｆ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
であり、
前記担当ビット位置がｋビット連続しており且つ前記所定のビットシフト幅がｋビットである
付記１又は２記載の楕円曲線暗号演算装置。
【０２７１】
（付記４）
前記テーブル補正値をＦとし、前記索引値を前記ウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応する前記テーブル値が、
（ｙk-1×２┌n/k┐*(k-1)＋ｙk-2×２┌n/k┐*(k-2)＋・・・＋ｙ1×２┌n/k┐*1＋ｙ0×２┌n/k┐*0）Ｇ＋Ｆ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
であり、
前記所定の補正値が、
（２┌n/k┐−１）Ｆ
であり、
前記担当ビット位置が┌n/k┐−１ビットおきであり且つ前記所定のビットシフト幅が１ビットである
付記１又は２記載の楕円曲線暗号演算装置。
【０２７２】
（付記５）
前記所定の補正値が予め算出されており且つ前記データ格納部に格納されている付記１乃至４のいずれか１つ記載の楕円曲線暗号演算装置。
【０２７３】
（付記６）
楕円曲線上の所定の点Ｇのスカラー倍算を実施する楕円曲線暗号演算装置であって、
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に前記点Ｇを乗じた基本テーブル値に対して前記点Ｇの第２のスカラー値ｘ倍のテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部と、
前記スカラー値ｄに対して前記第２のスカラー値ｘに応じた所定の補正値で補正を実施して、第３のスカラー値ｆを生成する補正部と、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記第３のスカラー値ｆから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施する演算処理部と、
を有する楕円曲線暗号演算装置。
【０２７４】
（付記７）
前記演算処理部が、
変数に格納されている値に対して前記楕円曲線上における２倍演算を実施して演算結果を当該変数に格納する２倍演算部と、
前記変数に格納されている値と読み出された前記テーブル値との、前記楕円曲線上における加算演算を実施し、演算結果を当該変数に格納する加算演算部と、
制御部と、
を有し、
前記制御部が、
前記第３のスカラー値ｆの最上位ビットから、前記ウィンドウの各ビットの担当ビット位置のビット値を読み出して索引値を生成し、当該索引値で前記テーブル格納部に格納されている前記ウィンドウテーブルを検索して第１のテーブル値を読み出して、前記変数に格納し、
前記ウィンドウを所定のビットシフト幅だけ右シフトさせると共に、前記２倍演算部に、前記所定のビットシフト幅に応じた回数分前記変数に格納されている値に対して２倍演算を実施させ、前記加算演算部に、前記第３のスカラー値ｆから前記ウィンドウの各ビットの担当ビット位置のビット値を読み出すことにより得られる索引値で前記ウィンドウテーブルを検索して得られる第２のテーブル値について加算演算を実施させる処理を、前記第３のスカラー値ｆの全てのビットを処理するまで繰り返し行わせる
付記６記載の楕円曲線暗号演算装置。
【０２７５】
（付記８）
前記索引値を前記ウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応する前記テーブル値が、
（ｙk-1×２k-1＋ｙk-2×２k-2＋・・・＋ｙ1×２1＋ｙ0×２0）Ｇ＋ｘＧ
であり、
前記所定の補正値が、
（２k*0＋２k*1＋２k*2＋・・・＋２k*(┌n/k┐-1)）ｘ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
であり、
前記担当ビット位置がｋビット連続しており且つ前記所定のビットシフト幅がｋビットである
付記６又は７記載の楕円曲線暗号演算装置。
【０２７６】
（付記９）
前記索引値を前記ウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応する前記テーブル値が、
（ｙk-1×２┌n/k┐*(k-1)＋ｙk-2×２┌n/k┐*(k-2)＋・・・＋ｙ1×２┌n/k┐*1＋ｙ0×２┌n/k┐*0）Ｇ＋ｘＧ
（┌n/k┐は、ｎ／ｋ以上の最小の整数を表す）
であり、
前記所定の補正値が、
（２┌n/k┐−１）ｘ
であり、
前記担当ビット位置が┌n/k┐−１ビットおきであり且つ前記所定のビットシフト幅が１ビットである
付記６又は７記載の楕円曲線暗号演算装置。
【０２７７】
（付記１０）
楕円曲線上の所定の点Ｇのスカラー倍算を実施する楕円曲線暗号演算装置であって、
スカラー値ｄのブロック毎に、当該ブロックに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記ブロック中の相対ビット位置及び前記スカラー値ｄ中の当該ブロックの相対位置に対応する値についての２のべき乗との積の和に前記点Ｇを乗じた基本テーブル値に対して非ゼロのブロックテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部と、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄの各前記ブロックから読み出すことにより索引値を生成して当該索引値で各前記ブロックの前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施する演算処理部と、
を有し、
各前記ブロックについての前記ブロックテーブル補正値の総和がゼロとなっていることを特徴とする
楕円曲線暗号演算装置。
【０２７８】
（付記１１）
前記演算処理部が、
変数に格納されている値に対して前記楕円曲線上における２倍演算を実施して演算結果を当該変数に格納する２倍演算部と、
前記変数に格納されている値と読み出された前記テーブル値との、前記楕円曲線上における加算演算を実施し、当該変数に格納する加算演算部と、
制御部と、
を有し、
前記制御部が、
前記スカラー値ｄの最上位ブロックの最上位ビットから、前記ウィンドウの各ビットの担当ビット位置のビット値を読み出して索引値を生成し、当該索引値で前記テーブル格納部に格納されている前記最上位ブロックについてのウィンドウテーブルを検索して第１のテーブル値を読み出して、前記変数に格納し、
前記加算演算部に、前記スカラー値ｄの第２位ブロック以下の各ブロックの最上位ビットから前記ウィンドウの各ビットの担当ビット位置のビット値を読み出すことにより得られる索引値により処理に係る前記ブロックについてのウィンドウテーブルを検索して得られる第２のテーブル値と前記変数に格納されている値との加算演算を最下位ブロックまで繰り返し実施させ、
前記ウィンドウを所定のビットシフト幅だけ各前記ブロック内において右シフトさせると共に、前記２倍演算部に、前記所定のビットシフト幅に応じた回数分前記変数に格納されている値に対して２倍演算を実施させ、前記加算演算部に、前記スカラー値ｄの各前記ブロックから前記ウィンドウの各ビットの担当ビット位置のビット値を読み出すことにより得られる索引値により処理に係る前記ブロックについてのウィンドウテーブルを検索して得られる第３のテーブル値についての加算演算を最下位ブロックまで繰り返し実施させる処理を、前記スカラー値ｄの全てのビットを処理するまで繰り返し行わせる
付記１０記載の楕円曲線暗号演算装置。
【０２７９】
（付記１２）
前記ブロックの番号をｊとし、前記ブロックの個数をｔとし、前記スカラー値ｄはｎビットとし、前記ブロックの番号ｊの前記テーブル補正値をＦjとし、前記索引値を前記ウィンドウ幅ｋビットのｙ（ｙk-1||ｙk-2||・・・ｙ1||ｙ0）とすると、対応する前記テーブル値が、
【数３】
0005446678.tif 000004
Ｋ(n, k, m, t, j)＝┌n/(t*k)┐×ｋ×ｊ＋┌n/(t*k)┐×ｍ
（┌z┐は、z以上の最小の整数を表す）
であり、
前記担当ビット位置が┌n/2k┐−１ビットおきであり且つ前記所定のビットシフト幅が１ビットである
付記１０又は１１記載の楕円曲線暗号演算装置。
【０２８０】
（付記１３）
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して非ゼロのテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置により実行される楕円曲線暗号演算方法であって、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施するステップと、
前記演算処理部の演算結果に対して前記テーブル補正値に応じた所定の補正値で補正を実施するステップと、
を含む楕円曲線暗号演算方法。
【０２８１】
（付記１４）
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して前記点Ｇの第２のスカラー値ｘ倍のテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置により実行される楕円曲線暗号演算方法であって、
前記スカラー値ｄに対して前記第２のスカラー値ｘに応じた所定の補正値で補正を実施して、第３のスカラー値ｆを生成するステップと、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記第３のスカラー値ｆから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施するステップと、
を含む楕円曲線暗号演算方法。
【０２８２】
（付記１５）
ｎ（ｎは２以上の整数）ビットのスカラー値ｄのブロック毎に、当該ブロックに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記ブロック中の相対ビット位置及び前記スカラー値ｄ中の当該ブロックの相対位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して非ゼロのブロックテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置により実行される楕円曲線暗号演算方法であって、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄの各前記ブロックから読み出すことにより索引値を生成して当該索引値で各前記ブロックの前記ウィンドウテーブルを検索してテーブル値を読み出すステップと、
読み出した前記テーブル値を用いて２倍演算及び加算演算を実施するステップと、
を含み、
各前記ブロックについての前記ブロックテーブル補正値の総和がゼロとなっていることを特徴とする
楕円曲線暗号演算方法。
【０２８３】
（付記１６）
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して非ゼロのテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置に、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施するステップと、
前記演算処理部の演算結果に対して前記テーブル補正値に応じた所定の補正値で補正を実施するステップと、
を実行させるための楕円曲線暗号演算プログラム。
【０２８４】
（付記１７）
ｎ（ｎは２以上の整数）ビットのスカラー値ｄに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記スカラー値ｄ中の相対ビット位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して前記点Ｇの第２のスカラー値ｘ倍のテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置に、
前記スカラー値ｄに対して前記第２のスカラー値ｘに応じた所定の補正値で補正を実施して、第３のスカラー値ｆを生成するステップと、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記第３のスカラー値ｆから読み出すことにより索引値を生成して当該索引値で前記ウィンドウテーブルを検索してテーブル値を読み出し、読み出した前記テーブル値を用いて２倍演算及び加算演算を実施するステップと、
を実行させるための楕円曲線暗号演算プログラム。
【０２８５】
（付記１８）
ｎ（ｎは２以上の整数）ビットのスカラー値ｄのブロック毎に、当該ブロックに対するウィンドウのウィンドウ幅ｋ（ｋは２以上の整数）ビットと同じビット数の各索引値に対応付けて、当該索引値の各ビットの値と当該ビットが担当する前記ブロック中の相対ビット位置及び当該ブロックの前記スカラー値ｄ中の相対位置に対応する値についての２のべき乗との積の和に楕円曲線上の所定の点Ｇを乗じた基本テーブル値に対して非ゼロのブロックテーブル補正値を加えたテーブル値が格納されているウィンドウテーブルを格納するデータ格納部を有する装置に、
前記ウィンドウをシフトさせつつ当該ウィンドウの各ビットの担当ビット位置のビット値を前記スカラー値ｄの各前記ブロックから読み出すことにより索引値を生成して当該索引値で各前記ブロックの前記ウィンドウテーブルを検索してテーブル値を読み出すステップと、
読み出した前記テーブル値を用いて２倍演算及び加算演算を実施するステップと、
を実行させ、
各前記ブロックについての前記ブロックテーブル補正値の総和がゼロとなっていることを特徴とする
楕円曲線暗号演算プログラム。
【符号の説明】
【０２８６】
１  バス    ３  ＣＰＵ    ５  演算器
７  ＲＯＭ    ９  ＲＡＭ    １１  通信部
７１  演算プログラム    ７３  補正点データ
７５  Ｗｉｎｄｏｗテーブル    
５１  加算演算部    ５３  ２倍演算部
【図１】
0005446678.tif 000005
【図２】
0005446678.tif 000006
【図３】
0005446678.tif 000007
【図４】
0005446678.tif 000008
【図５】
0005446678.tif 000009
【図６】
0005446678.tif 000010
【図７】
0005446678.tif 000011
【図８】
0005446678.tif 000012
【図９】
0005446678.tif 000013
【図１０】
0005446678.tif 000014
【図１１Ａ】
0005446678.tif 000015
【図１１Ｂ】
0005446678.tif 000016
【図１２】
0005446678.tif 000017
【図１３】
0005446678.tif 000018
【図１４】
0005446678.tif 000019
【図１５】
0005446678.tif 000020
【図１６】
0005446678.tif 000021
【図１７】
0005446678.tif 000022
【図１８Ａ】
0005446678.tif 000023
【図１８Ｂ】
0005446678.tif 000024
【図１９】
0005446678.tif 000025
【図２０】
0005446678.tif 000026
【図２１】
0005446678.tif 000027
【図２２】
0005446678.tif 000028
【図２３】
0005446678.tif 000029
【図２４Ａ】
0005446678.tif 000030
【図２４Ｂ】
0005446678.tif 000031
【図２５】
0005446678.tif 000032
【図２６】
0005446678.tif 000033
【図２７】
0005446678.tif 000034
【図２８】
0005446678.tif 000035
【図２９】
0005446678.tif 000036
【図３０Ａ】
0005446678.tif 000037
【図３０Ｂ】
0005446678.tif 000038
【図３１】
0005446678.tif 000039
【図３２】
0005446678.tif 000040
【図３３】
0005446678.tif 000041
【図３４Ａ】
0005446678.tif 000042
【図３４Ｂ】
0005446678.tif 000043
【図３５】
0005446678.tif 000044
【図３６】
0005446678.tif 000045
【図３７】
0005446678.tif 000046
【図３８Ａ】
0005446678.tif 000047
【図３８Ｂ】
0005446678.tif 000048
【図３９】
0005446678.tif 000049
【図４０】
0005446678.tif 000050
【図４１】
0005446678.tif 000051
【図４２】
0005446678.tif 000052
【図４３】
0005446678.tif 000053
【図４４】
0005446678.tif 000054
【図４５】
0005446678.tif 000055