(57)【要約】      （修正有）【課題】サイドチャネル攻撃に強い耐タンパー性を有するスカラー倍算装置を比較的簡単な構成で得る。【解決手段】演算テーブル記憶部２は、分割スカラー値ｋ１〜ｋｎのビット情報の組合せに対応した複数の演算パラメータを有する演算テーブルＴＢを格納する。スカラー倍演算部３は入力座標点Ｐ及びＫＢビットのスカラー値ｋを受け、スカラー値ｋをビット列に沿って均等にｎ分割して得られる分割スカラー値ｋ１〜ｋｎを用いてスカラー倍算値ｋ×Ｐを得るスカラー倍算処理を行う。この際、スカラー倍演算部３は、演算テーブル記憶部２に格納された演算テーブルＴＢを参照することにより、分割スカラー値ｋ１〜ｋｎに対しビット単位に同時にスカラー倍算処理を実行している。【選択図】図１
2014191140.tif 000002
【特許請求の範囲】
【請求項１】
入力座標点及びスカラー値を受け、前記入力座標点のスカラー倍算値を得るスカラー倍算装置であって、
前記入力座標点及びＫＢビットの前記スカラー値を受け、該スカラー値をビット列に沿って均等にｎ分割して得られる第１〜第ｎスカラービット列を用いて前記スカラー倍算値を得るスカラー倍算処理を行うスカラー倍演算部と、
前記第１〜第ｎのスカラービット列のビット情報の組合せに対応した複数の演算パラメータを有する演算テーブルを格納した演算テーブル記憶部とを備え、
前記スカラー倍演算部は、前記演算テーブルを参照することにより、前記第１〜第ｎのスカラービット列に対しビット単位に同時に前記スカラー倍算処理を実行することを特徴とする、
スカラー倍算装置。
【請求項２】
請求項１記載のスカラー倍算装置であって、
前記第１〜第ｎのスカラービット列はＫＢビットのスカラー値を上位からＤ（ＫＢ／ｎ）ビット毎に分割されたビット列であり、
前記複数の演算パラメータは、前記第１〜第（ｎ−１）のスカラービット列それぞれの分割対象外の下位のビット列に対しオフセット演算することにより、第１〜第ｎのスカラービット列のビット情報による複数の組合せ内容に対応した、前記入力座標点における複数の事前倍算値である、
スカラー倍算装置。
【請求項３】
請求項１または請求項２記載のスカラー倍算装置であって、
前記スカラー倍演算部は、前記スカラー値の分割数ｎをさらに受け、
ＫＢビットの前記スカラー値をｎ分割して得られる前記第１〜第ｎのスカラービット列のビット情報の組合せに対応した前記複数の演算パラメータを算出し、該複数のパラメータを有する前記演算テーブルを前記演算テーブル記憶部に格納する演算テーブル作成部を有する、
スカラー倍算装置。
【請求項４】
入力座標点及びＫＢビットのスカラー値を受け、スカラー倍算値を得るスカラー倍算方法であって、
(a) 前記入力座標点及び前記スカラー値のビット数ＫＢに基づき、該スカラー値をビット列に沿って均等に分割して得られる第１〜第ｎスカラービット列のビット情報の組合せに対応した複数の演算パラメータを算出して、該複数の演算パラメータを有する演算テーブルを求めるステップと、
(b) 前記演算テーブルを参照して、前記第１〜第ｎのスカラービット列に対しビット単位に同時にスカラー倍算処理を実行することにより、前記入力座標点の前記スカラー倍算値を得るステップとを備える、
スカラー倍算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、入力座標点をスカラー倍算してスカラー倍算値を得るスカラー倍算装置及びスカラー倍算方法に関する。
【背景技術】
【０００２】
楕円曲線上の入力座標点をスカラー倍算してスカラー倍算値を得る楕円スカラー倍算装置におけるサイドチャネル攻撃として、差分電力解析攻撃と単純電力解析攻撃が一般的に知られている。
【０００３】
差分電力解析攻撃の対策として、非特許文献１及び非特許文献２では、楕円曲線上の点Ｐの楕円スカラー倍算値（ｋ×Ｐ）を求める際、楕円スカラー倍算処理を実行する毎に異なる乱数ｒを用いてスカラー値ｋを２つ(ｋ＝ｋ１＋ｋ２)に分離し、点Ｐを分離したスカラー値ｋ１，ｋ２でそれぞれ楕円スカラー倍算した後、これらの２点を加算している第１のスカラー倍算方法がある。
【０００４】
第１のスカラー倍算方法は、分離したスカラー値ｋ１，ｋ２は、楕円スカラー倍算を行う毎に変わるため、差分電力解析攻撃には有効である。
【０００５】
一方、特許文献１では、楕円曲線上の点Ｐの楕円スカラー倍算値ｋ×Ｐにおいて、除数ｒ'=｛αｒ mod ｎ｝とαを用いて、スカラー値ｋからスカラー値(ｋ mod r')とスカラー値[ｋ/r']αを生成し、生成した２つのスカラー値を２つのスカラー倍算装置を用いて、楕円スカラー倍算値(ｋ mod r')×P及び楕円スカラー倍算値[ｋ/r']α×Sを演算し、その後、２点を加算している第２のスカラー倍算方法がある。この際、位数の定義によりｎ×Ｐは無限遠点であることから、α×Ｓはｒ'×Ｐと変形できるため、上記演算結果とスカラー倍算値ｋ×Ｐとは等しくなる。
【０００６】
なお、上述したパラメータｎ，ｒ，Ｓ，α，について、ｎは点Ｐの位数であり、ｒは１＜ｒ＜ｎを満足する予め定められた整数であり、点Ｓは点Ｐをｒで楕円スカラー倍算した点、αは１＜α＜ｎの整数の乱数である。また、（Ｘ１ ｍｏｄ Ｘ２）はＸ１をＸ２で割った除数（余り）、[Ｘ１／Ｘ２]はＸ１をＸ２で割った商を意味する。
【０００７】
上述した第２のスカラー倍算方法において、２つのスカラー値(ｋ mod r')とスカラー値[ｋ/r']αは、単純電力解析攻撃を受けて値を解析されたとしても、整数ｒが読み出されない限り単純計算ではスカラー値ｋを復元することができないため、差分電力解析攻撃に加えて単純電力解析攻撃にも有効である。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００９−２１８９９１号公報
【非特許文献】
【０００９】
【非特許文献１】Christopher Clavier and Marc Joye, 「Universal Exponentiation Algorithm」, CHES 2001, volume 2162 of LNCS, Springer-Verlag, 2001, P.300-308
【非特許文献２】Christopher Clavier and Marc Joye, 「(Virtually) Free Randomization Techniques for Elliptic Curve Cryptography」, ICIS 2003, volume 2836 of LNCS, Springer-Verlag, 2003, P.348-359
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した第１のスカラー倍算方法では、スカラー値ｋから分けられた２つのスカラー値（k1，k2）それぞれにおけるスカラー倍算処理を行う時に、消費電力の増減があるため、単純電力解析攻撃に弱く、解析されてしまう可能性が高いという問題点があった。
【００１１】
一方、第２のスカラー倍算方法では、単純電力解析攻撃に対しても強い反面、楕円スカラー倍算装置を２つ使用する必要があるため、実現するための装置コストが大きいという問題点があった。
【００１２】
この発明は上記問題点を解決するためになされたもので、差分電力解析攻撃や単純電力解析攻撃等のサイドチャネル攻撃に強い耐タンパー性を有するストリーム暗号装置を比較的簡単な構成で得ることを目的とする。
【課題を解決するための手段】
【００１３】
この発明に係る請求項１記載のスカラー倍算装置は、入力座標点及びスカラー値を受け、前記入力座標点のスカラー倍算値を得るスカラー倍算装置であって、前記入力座標点及びＫＢビットの前記スカラー値を受け、該スカラー値をビット列に沿って均等にｎ分割して得られる第１〜第ｎスカラービット列を用いて前記スカラー倍算値を得るスカラー倍算処理を行うスカラー倍演算部と、前記第１〜第ｎのスカラービット列のビット情報の組合せに対応した複数の演算パラメータを有する演算テーブルを格納した演算テーブル記憶部とを備え、前記スカラー倍演算部は、前記演算テーブルを参照することにより、前記第１〜第ｎのスカラービット列に対しビット単位に同時に前記スカラー倍算処理を実行することを特徴とする。
【００１４】
請求項２の発明は、請求項１記載のスカラー倍算装置であって、前記第１〜第ｎのスカラービット列はＫＢビットのスカラー値を上位からＤ（ＫＢ／ｎ）ビット毎に分割されたビット列であり、前記複数の演算パラメータは、前記第１〜第（ｎ−１）のスカラービット列それぞれの分割対象外の下位のビット列に対しオフセット演算することにより、第１〜第ｎのスカラービット列のビット情報による複数の組合せ内容に対応した、前記入力座標点における複数の事前倍算値である。
【００１５】
請求項３の発明は、請求項１または請求項２記載のスカラー倍算装置であって、前記スカラー倍演算部は、前記スカラー値の分割数ｎをさらに受け、ＫＢビットの前記スカラー値をｎ分割して得られる前記第１〜第ｎのスカラービット列のビット情報の組合せに対応した前記複数の演算パラメータを算出し、該複数のパラメータを有する前記演算テーブルを前記演算テーブル記憶部に格納する演算テーブル作成部を有する。
【００１６】
この発明に係る請求項４記載のスカラー倍算方法は、入力座標点及びＫＢビットのスカラー値を受け、スカラー倍算値を得るスカラー倍算方法であって、(a) 前記入力座標点及び前記スカラー値のビット数ＫＢに基づき、該スカラー値をビット列に沿って均等に分割して得られる第１〜第ｎスカラービット列のビット情報の組合せに対応した複数の演算パラメータを算出して、該複数の演算パラメータを有する演算テーブルを求めるステップと、(b) 前記演算テーブルを参照して、前記第１〜第ｎのスカラービット列に対しビット単位に同時にスカラー倍算処理を実行することにより、前記入力座標点の前記スカラー倍算値を得るステップとを備える。
【発明の効果】
【００１７】
この発明におけるスカラー倍算装置におけるスカラー倍演算部は、演算テーブルを参照することにより、第１〜第ｎのスカラービット列に対しビット単位に同時にスカラー倍算処理を実行する特徴を有している。このため、スカラー倍算装置が実行するスカラー倍算処理内容に対し電力解析を行っても、第１〜第ｎのスカラービット列のうち、いずれのビット列のビット情報に対する演算処理を行ったかを識別することができないため、サイドチャネル攻撃に強い耐タンパー性を有するスカラー倍算装置を得ることができる。
【００１８】
さらに、スカラー倍算装置は、演算テーブルを格納する演算テーブル記憶部と、スカラー倍算処理を実行するスカラー倍演算部により構成されており、スカラー倍算処理を行う構成部を一つにした比較的簡単な装置構成で実現でき、装置の低コスト化を図ることができる。
【図面の簡単な説明】
【００１９】
【図１】実施の形態１（実施の形態２）のスカラー倍算装置の構成を示すブロック図である。
【図２】実施の形態１のスカラー倍算装置の演算内容を表形式で示す説明図である。
【図３】実施の形態１の演算テーブルの内容を表形式で示す説明図である。
【図４】実施の形態１のスカラー倍算処理におけるアルゴリズムのプログラム内容を示す説明図である。
【図５】図４のプログラム実行時における演算例を示す説明図である。
【図６】実施の形態１の比較例におけるプログラム内容を示す説明図である。
【図７】図６のプログラム実行時における演算回数を表形式で示す説明図である。
【図８】実施の形態２のスカラー倍算装置の演算内容を表形式で示す説明図（その１）である。
【図９】実施の形態２のスカラー倍算装置の演算内容を表形式で示す説明図（その２）である。
【図１０】実施の形態２のスカラー倍算装置の演算内容を表形式で示す説明図（その３）である。
【図１１】実施の形態２の演算テーブルの内容を表形式で示す説明図である。
【図１２】実施の形態２のスカラー倍算処理におけるアルゴリズムのプログラム内容を示す説明図である。
【図１３】図１２のプログラム実行時における演算回数を表形式で示す説明図である。
【図１４】実施の形態３のスカラー倍算装置の構成を示すブロック図である。
【図１５】従来のスカラー倍算処理の基本アルゴリズムのプログラム内容を示す説明図である。
【図１６】図１５のプログラム実行時における演算例を示す説明図である。
【発明を実施するための形態】
【００２０】
＜前提技術＞
まず、基本となる楕円スカラー倍算処理のアルゴリズムについて説明する。ここで、スカラー値ｋが｛k=0xAAD7;(k=16'b1010 1010 1101 0111)｝を満足する１６ビットである場合における、入力座標点Ｐに対するスカラー倍算値ｋ×Ｐを求める場合を想定する。
【００２１】
図１５は従来の基本アルゴリズムＡＲ５０のプログラム内容を示す説明図である。図１６は上記想定時における演算例ＥＸ５０を表形式で示す説明図である。
【００２２】
図１５に示すように、基本アルゴリズムＡＲ５０はＣ言語仕様で記述されている。基本アルゴリズムＡＲ５０は、最初に初期設定（k=0xAAD7,j=15）を行った後、サブルーチンＳＲ５１が実行される。
【００２３】
サブルーチンＳＲ５１では１６ビットのスカラー値ｋのビット情報が“１”となる最上位ビットを検出し、そのビット位置（ｊの値）で「Ｑ＝Ｐ」とし、変数ｊを１デクリメントして終了する。
【００２４】
図１６で示す演算例ＥＸ５０では、ビット情報が“１”となる最上位ビットはビット位置ｉ＝１５であるため、「ｊ＝１５」の状態で「Ｑ＝Ｐ」とした後、「ｊ＝１４」にしてサブルーチンＳＲ５１を終了する。
【００２５】
サブルーチンＳＲ５１の終了後、サブルーチンＳＲ５２によりＥＣＤＢＬ(Elliptic Curve Doubling）演算及びＥＣＡＤＤ(Elliptic Curve Addition）演算が、変数ｊで指示するビット位置から下位ビットにかけて順次実行され、最下位ビット（ｉ＝０）時のＥＣＡＤＤ演算（スキップされて実際には行われない場合を含む）後の結果がスカラー倍算値ｋ×Ｐとして得られる。
【００２６】
サブルーチンＳＲ５２において、ＥＣＤＢＬ演算はスカラー値ｋのビット毎に行われ、ＥＣＡＤＤ演算は対応するビット位置ｉにおけるスカラー値ｋのビット情報が“１”の場合のみ選択的に行われる。すなわち、ｋ［ｉ］をビット位置ｉにおけるスカラー値ｋのビット情報とすると、ｋ［ｉ］＝０のときＥＣＡＤＤ演算が実行されないためＱにＰが加算さることはなく、ｋ［ｉ］＝１のときＥＣＡＤＤ演算が実行されてＱにＰが加算される。
【００２７】
その結果、上記想定時において、図１６のｉ＝０の時のＥＣＡＤＤ演算後の値「４３７３５Ｐ」がスカラー倍算値ｋ×Ｐとして最終的に得られる。
【００２８】
このように、一般的な楕円スカラー倍算処理の基本アルゴリズムＡＲ５０では、ＥＣＡＤＤ演算はビット単位に選択的に行われているため、ＥＣＡＤＤ演算状況を電力解析することにより、スカラー値ｋにおいてビット情報が“１”となるビット位置が識別されてしまい、サイドチャネル攻撃に弱く耐タンパー性が低いという問題点を潜在的に有している。
【００２９】
＜実施の形態１＞
（基本構成）
図１は実施の形態１のスカラー倍算装置１の構成を示すブロック図である。同図に示すように、スカラー倍算装置１は入力座標点Ｐ(X,Y)及びスカラー値ｋを受け、入力座標点Ｐのスカラー倍算値ｋ×Ｐを得ている。
【００３０】
スカラー倍算装置１は演算テーブル記憶部２及びスカラー倍演算部３から構成されている。
【００３１】
スカラー倍演算部３は入力座標点Ｐ及びＫＢビットのスカラー値ｋを受け、スカラー値ｋをビット列に沿って均等にｎ分割して得られる分割スカラー値ｋ１〜ｋｎ（第１〜第ｎスカラービット列）を用いてスカラー倍算値ｋ×Ｐを得るスカラー倍算処理を行う。
【００３２】
演算テーブル記憶部２は、分割スカラー値ｋ１〜ｋｎのビット情報の組合せに対応した複数の演算パラメータを有する演算テーブルＴＢを格納している。
【００３３】
スカラー倍演算部３は、後に詳述するように、演算テーブル記憶部２に格納された演算テーブルＴＢを参照することにより、分割スカラー値ｋ１〜ｋｎに対しビット単位に同時にスカラー倍算処理を実行することを特徴としている。
【００３４】
なお、実施の形態１では、スカラー値ｋのビット数ＫＢが１６ビットであり、分割数ｎを“２”として、上位から８ビット（Ｄビット（Ｄ＝ＫＢ／ｎ））毎に分割して得られる分割スカラー値ｋ１及びｋ２を用いる態様を示している。そして、演算テーブルＴＢとして分割スカラー値ｋ１及びｋ２のビット情報の組合せに対応した演算テーブルＴＢ１を採用している。
【００３５】
（スカラー倍算の基本演算式）
図２は実施の形態１のスカラー倍算装置１の演算内容を表形式で示す説明図である。実施の形態１のスカラー倍算装置１において、スカラー値ｋを１６ビット構成の「k=16'b1010 1010 1101 0111」とし、スカラー値ｋの上位８ビットのビット列を分割スカラー値ｋ１｛k1=8'b1010 1010｝、スカラー値ｋの下位８ビットのビット列を分割スカラー値ｋ２｛k2=8'b1101 0111｝とした場合を例に挙げて、適宜、図２を参照して、実施の形態１のスカラー倍算装置１の演算内容を説明する。なお、本明細書中において「16'b，8'b，9'b」等はそれぞれビット列のビット数（16,8,9）を示している。
【００３６】
スカラー倍算値ｋ×Ｐとなる演算式ｋ×Ｐは以下の式(1)ように変形できる。なお、式(1)はスカラー値ｋを分割スカラー値ｋ２によって分解して表した式である。そして、式(1)の前半部分｛(ｋ-k2)×P）｝は図２(a)で示すようにして演算され、後半部分｛k2×P｝は図２(b)に示すように演算される。
【００３７】
【数１】
2014191140.tif 000003
【００３８】
ここで、（ｋ−ｋ２）は、下位８ｂｉｔのビット情報が全て“０”となるため、以下の式(2)に変形でき、式(2)は具体例を挙げて記述すると以下の式(3)のようになる。
【００３９】
【数２】
2014191140.tif 000004
【００４０】
【数３】
2014191140.tif 000005
【００４１】
式(3)の３行目の「8'b1010 1010」は、分割スカラー値ｋ１の値となる。すなわち、式(2)（式(3)）から、(ｋ-k2)は、図２(c)で示す８ビットのスカラー倍算処理後に得られた値（１７０Ｐ）を２８（＝２５６）のオフセット演算を行うことにより得られることがわかる。図２(c)からＰにオフセットとなる２８を演算すると、図２(d)に示すようになる。
【００４２】
そして、式(2)を式(1)に代入すると以下の式(4)が得られる。式(4)の(ｋ2×P)の部分は図２(e)に示すように、図２(b)で示す下位８ビットの状態から変化していない。
【００４３】
【数４】
2014191140.tif 000006
【００４４】
実施の形態１のスカラー倍算装置１では、上記した式(4)をスカラー倍算値ｋ×Ｐを求める基本演算式として採用する。
【００４５】
（演算テーブル）
図３は演算テーブル記憶部２内に格納された演算テーブルＴＢ１の内容を表形式で示す説明図である。
【００４６】
同図において、ｋ１［ｉ］及びｋ２［ｉ］は、ビット位置ｉにおける分割スカラー値ｋ１及びｋ２のビット情報を意味する。そして、２’ｂ００はｋ１［ｉ］及びｋ２［ｉ］が共に“０”、２’ｂ０１はｋ１［ｉ］が“０”で、ｋ２［ｉ］が“１”、２’ｂ１０はｋ１［ｉ］が“１”で、ｋ２［ｉ］が“０”、２’ｂ１１はｋ１［ｉ］及びｋ２［ｉ］が共に“１”の場合を示している。
【００４７】
図３に示すように、演算テーブルＴＢ１ではｋ１［ｉ］及びｋ２［ｉ］のビット情報の組合せに対応して入力座標点Ｐにおける複数の（４個の）事前倍数値（演算パラメータ）を設定している。具体的には、２’ｂ００の場合に事前倍数値“０”が設定され、２’ｂ０１の場合に事前倍数値Ｐが設定され、２’ｂ１０の場合に事前倍数値２５６Ｐ（２５６×Ｐ）が設定され、２’ｂ１１の場合に事前倍数値２５７Ｐ（２５６×Ｐ＋Ｐ）が設定される。
【００４８】
上述した演算テーブルＴＢ１における４個の事前倍数値（０．Ｐ．２５６Ｐ，２５７Ｐ）は、式(4)に基づき予め演算により求めることができる。このように、演算テーブルＴＢ１は、ｋ１［ｉ］が“１”の場合は２８のオフセット演算が行われることを事前に考慮にした事前倍数値（２５６Ｐ，２５７Ｐ）を有している。すなわち、演算テーブルＴＢ１は分割スカラー値ｋ１に関し下位のビット列に対しオフセット演算することにより得られる事前倍数値を有している。
【００４９】
（楕円スカラー倍算アルゴリズムＡＲ１）
図４は実施の形態１のスカラー倍算装置１のスカラー倍算処理として実行される楕円スカラー倍算アルゴリズムＡＲ１のプログラム内容を示す説明図である。図５は上記スカラー値ｋの２分割想定時（｛k=0xAAD7; (k1=8'b1010 1010) (k2=8'b1101 0111)｝)における演算例ＥＸ１を表形式で示す説明図である。
【００５０】
図４に示すように、楕円スカラー倍算アルゴリズムＡＲ１はＣ言語仕様で記述されている。楕円スカラー倍算アルゴリズムＡＲ１は、最初に初期設定（j=7）を行った後、サブルーチンＳＲ１１が実行される。
【００５１】
サブルーチンＳＲ１１では８ビットの分割スカラー値ｋ１及びｋ２のうち少なくとも一つのビット情報が“１”となる最上位ビットを検出し、そのビット位置（ｊの値）で「Ｑ＝ｔｂｌ（ｋ１[ｊ]，ｋ２［ｊ］）」を設定し、変数ｊを“１”デクリメントして終了する。
【００５２】
｛Ｑ＝ｔｂｌ（ｋ１[ｊ]，ｋ2［ｊ］）｝は、図３で示したｋ１［ｊ］及びｋ２［ｊ］の組合せに対応する事前倍数値をＱとして設定することを意味する。図５で示す演算例ＥＸ１では、ｊ＝７で、ｋ１[７]＝“１”、ｋ２［７］＝１となるため、Ｑ＝２５７Ｐに設定し、「ｊ＝６」に設定した後、サブルーチンＳＲ１１を終了する。
【００５３】
サブルーチンＳＲ１１の終了後、サブルーチンＳＲ１２によりＥＣＤＢＬ演算及びＥＣＡＤＤ演算が、分割スカラー値ｋ１及びｋ２に対し、変数ｊで示すビット位置から下位ビットにかけて順次実行され、最下位ビット（ｉ＝０）時のＥＣＡＤＤ演算後の結果がスカラー倍算値ｋ×Ｐとして得られる。
【００５４】
サブルーチンＳＲ１２において、ＥＣＤＢＬ演算は分割スカラー値ｋ１及びｋ２のビット毎に行われ、ＥＣＡＤＤ演算は対応するビット位置ｉにおける分割スカラー値ｋ１及びｋ２のビット情報の少なくとも一つが“１”の場合のみ選択に行われる。この際、ＥＣＡＤＤ演算は、図３で示した演算テーブルＴＢ１を参照して、Ｑにｔｂｌ（｛ｋ１[ｉ]，ｋ2［ｉ］｝）を加算する態様で行われる。
【００５５】
すなわち、サブルーチンＳＲ１２におけるＥＣＡＤＤ演算は、ｋ１［ｉ］が“１”の場合は２５６Ｐを加算し、“０”の場合は加算せず、ｋ２［ｉ］が“１”の場合はＰを加算し“０”の場合は加算しない態様のＥＣＡＤＤ演算を行う。
【００５６】
なお、サブルーチンＳＲ１２では、｛if((k1[i]=1)||(k2[i]=1))｝の分岐制御により、ｋ１［ｉ］及びｋ２［ｉ］が共に“０”場合はスキップさせることによりＥＣＡＤＤ演算自体の実行を省略しているが、演算テーブルＴＢ１において、２’ｂ００の場合に“０”が事前倍数値として設定されているため、上記分岐制御を省略しても良い。上記分岐制御を省略した場合ｋ１［ｉ］及びｋ２［ｉ］の全ての組合せでＥＣＡＤＤ演算が行われることになる。
【００５７】
その結果、サブルーチンＳＲ１２の終了時に、上記想定時において、図５のｉ＝０の時のＥＣＡＤＤ演算後の値「４３７３５Ｐ」がスカラー倍算値ｋ×Ｐとして得られる。
【００５８】
このように、実施の形態１のスカラー倍算装置１におけるスカラー倍演算部３は、演算テーブル記憶部２に格納された演算テーブルＴＢ１を参照することにより、分割スカラー値ｋ１及びｋ２（第１及び第２のスカラービット列）に対しビット単位に同時にスカラー倍算処理内におけるＥＣＡＤＤ演算を実行することを特徴としている。
【００５９】
実施の形態１のスカラー倍算装置１は、上記特徴を有することにより、スカラー倍算処理内容（ＥＣＡＤＤ演算）に対し電力解析を行っても、分割スカラー値ｋ１及びｋ２のうち、図５の矢印に示すように、いずれの分割スカラー値のビット情報に対するＥＣＡＤＤ演算であるか識別することができないため、サイドチャネル攻撃に強い耐タンパー性を有するという効果を奏する。
【００６０】
さらに、スカラー倍算装置１は、演算テーブルＴＢを格納する演算テーブル記憶部２と、スカラー倍算処理を実行するスカラー倍演算部３により構成されており、スカラー倍算処理を行う構成部を一つ（スカラー倍演算部３）にした比較的簡単な装置構成で実現でき、装置の低コスト化を図ることができる。
【００６１】
加えて、演算テーブル記憶部２に、入力座標点Ｐにおける複数の事前倍算値を有する演算テーブルＴＢ１を予め格納しておくことにより、スカラー倍演算部３によるスカラー倍算処理時に複数の事前倍算値の算出処理は不要となり、電力解析等から秘匿することができるため、効率的、かつ耐タンパー性の高いスカラー倍算装置を得ることができる。
【００６２】
（比較例）
図６は実施の形態１と同様にスカラー値ｋに対し分割スカラー値ｋ１及びｋ２によるスカラー倍算処理を演算テーブルＴＢ１を用いることなく実行する場合における楕円スカラー倍算アルゴリズムＡＲ１００のプログラム内容を示す説明図である。
【００６３】
図６に示すように、楕円スカラー倍算アルゴリズムＡＲ１００はＣ言語仕様で記述されている。楕円スカラー倍算アルゴリズムＡＲ１００は、最初に初期設定（j=7）を行った後、サブルーチンＳＲ１１１〜ＳＲ１１４が実行される。
【００６４】
サブルーチンＳＲ１１１〜ＳＲ１１３では８ビットの分割スカラー値ｋ１及びｋ２の少なくとも一つのビット情報が“１”となる最上位ビットを検出し、そのビット位置（ｊの値）におけるＱを求め、変数ｊをデクリメントしている。
【００６５】
この際、分割スカラー値ｋ１及びｋ２のビット情報が共に“１”の場合はサブルーチンＳＲ１１１が実行され、分割スカラー値ｋ１のビット情報が“０”であり分割スカラー値ｋ２のビット情報が“１”の場合はサブルーチンＳＲ１１２が実行され、分割スカラー値ｋ１のビット情報が“１”であり分割スカラー値ｋ２のビット情報が“０”の場合はサブルーチンＳＲ１１３が実行される。なお、分割スカラー値ｋ１及びｋ２が共に“０”の場合はビット位置が単にデクリメント（ｊ＝ｊ−１）された後、サブルーチンＳＲ１１１〜ＳＲ１１４の処理が続行される。
【００６６】
サブルーチンＳＲ１１１では、ＥＣＤＢＬ演算を８回繰り返し行った後、ＥＣＡＤＤ演算を１回行うことにより、Ｑ＝２５７Ｐ（２５６Ｐ＋Ｐ）に設定して、変数ｊをデクリメントして、サブルーチンＳＲ１１１〜ＳＲ１１４を終了させる。
【００６７】
サブルーチンＳＲ１１２では、ＥＣＡＤＤ演算を１回行うことにより、Ｑ＝Ｐに設定して、変数ｊをデクリメントした後、サブルーチンＳＲ１１１〜ＳＲ１１４を終了させる。
【００６８】
サブルーチンＳＲ１１３では、ＥＣＤＢＬ演算を８回繰り返し行うことにより、Ｑ＝２５６Ｐに設定して、変数ｊをデクリメントした後、サブルーチンＳＲ１１１〜ＳＲ１１４を終了させる。
【００６９】
サブルーチンＳＲ１１１〜ＳＲ１１４の処理の終了後、サブルーチンＳＲ２１１〜ＳＲ２１３が実行される。
【００７０】
サブルーチンＳＲ２１１〜ＳＲ２１３によりＥＣＤＢＬ演算及びＥＣＡＤＤ演算が、変数ｊで示すビット位置から下位ビットにかけて順次実行され、最下位ビット（ｉ＝０）時のＥＣＡＤＤ演算後の結果が最終的にスカラー倍算値ｋ×Ｐとして得られる。
【００７１】
サブルーチンＳＲ２１１〜ＳＲ２１３において、ＥＣＤＢＬ演算は分割スカラー値ｋ１及びｋ２のビット毎に行われ、ＥＣＡＤＤ演算は対応するビット位置ｉにおける分割スカラー値ｋ１及びｋ２のビット情報の少なくとも一つが“１”の場合のみ選択に行われる。
【００７２】
この際、分割スカラー値ｋ１及びｋ２のビット情報が共に“１”の場合はサブルーチンＳＲ２１１が実行され、分割スカラー値ｋ１のビット情報が“０”であり分割スカラー値ｋ２のビット情報が“１”の場合はサブルーチンＳＲ２１２が実行され、分割スカラー値ｋ１のビット情報が“１”であり分割スカラー値ｋ２のビット情報が“０”の場合はサブルーチンＳＲ２１３が実行される。なお、分割スカラー値ｋ１及びｋ２が共に“０”の場合はＥＣＡＤＤ演算が実行されない。
【００７３】
サブルーチンＳＲ２１１では、入力座標点Ｐに対するＥＣＤＢＬ演算を８回繰り返し行った後のＰ’（＝２５６Ｐ）を得て、Ｐ’によるＥＣＡＤＤ演算及びＰによるＥＣＡＤＤ演算をそれぞれ１回行うことにより、Ｑに２５７Ｐ（２５６Ｐ＋Ｐ）を加算する。
【００７４】
サブルーチンＳＲ２１２では、入力座標点Ｐに対するＥＣＡＤＤ演算を１回行うことにより、ＱにＰを加算する。
【００７５】
サブルーチンＳＲ２１３では、入力座標点Ｐに対するＥＣＤＢＬ演算を８回繰り返し行った後のＰ’（＝２５６Ｐ）を得て、ＱにＰ’（＝２５６Ｐ）を加算する。
【００７６】
すなわち、サブルーチンＳＲ２１１〜ＳＲ２１３におけるＥＣＡＤＤ演算は、ｋ１［ｉ］が“１”の場合は２５６Ｐを加算し、“０”の場合は加算せず、ｋ２［ｉ］が“１”の場合はＰを加算し“０”の場合は加算しない態様のＥＣＡＤＤ演算を行う。
【００７７】
その結果、実施の形態１と同様、上記想定時において、「４３７３５Ｐ」がスカラー倍算値ｋ×Ｐとして最終的に得られる。
【００７８】
図７はサブルーチンＳＲ１１１〜ＳＲ１１３及びサブルーチンＳＲ２１１〜ＳＲ２１３の実行時におけるＥＣＤＢＬ演算及びＥＣＡＤＤ演算の演算回数を表形式で示す説明図である。
【００７９】
単純電力解析によりＥＣＤＢＬ演算及びＥＣＡＤＤ演算の演算回数は観測できるため、演算回数の違いから、前半に実行されるサブルーチンＳＲ１１１〜ＳＲ１１３間の識別が可能となり、後半に実行されるサブルーチンＳＲ２１１〜ＳＲ２１３間の識別が可能となる。
【００８０】
したがって、サブルーチンＳＲ１１１及びＳＲ２１１の識別から分割スカラー値ｋ１及びｋ２のビット情報が共に“１”であることを特定できる。同様にして、サブルーチンＳＲ１１２及びＳＲ２１２の識別から分割スカラー値ｋ１のビット情報が“０”であり、分割スカラー値ｋ２のビット情報が“１”であることが特定でき、サブルーチンＳＲ１１３及びＳＲ２１３の識別から分割スカラー値ｋ１のビット情報が“１”で分割スカラー値ｋ２のビット情報が“０”であることが特定できる。
【００８１】
このように、演算テーブルＴＢ１を参照することなく、分割スカラー値ｋ１及びｋ２を用いたスカラー倍算処理を行う場合、単純電力解析に弱く、耐タンパー性が低い。また、２５６Ｐを求める際、ＥＣＤＢＬ演算を８回繰り返し実行する必要があるため、演算効率も悪い。
【００８２】
一方、実施の形態１のスカラー倍算装置１では、前述したように、演算テーブルＴＢ１を用いるにより、前述したように高い耐タンパー性があり、効率的なスカラー倍算処理を行える点で優位性を有する。
【００８３】
＜実施の形態２＞
（基本構成）
実施の形態２のスカラー倍算装置１Ｂは図１で示したスカラー倍算装置１の構成と同様である。ただし、実施の形態２では、スカラー値ｋのビット数ＫＢが１６ビットであり、分割数ｎを“４”として、上位から４ビット（Ｄビット（Ｄ＝ＫＢ／ｎ））毎に分割して得られる分割スカラー値ｋ１〜ｋ４を用いる態様を示している。そして、演算テーブル記憶部２に格納する演算テーブルＴＢとして４分割された分割スカラー値ｋ１〜ｋ４のビット情報の組合せに対応した演算テーブルＴＢ２を採用している。
【００８４】
（スカラー倍算の基本演算式）
図８〜図１０は実施の形態２のスカラー倍算装置１Ｂの演算内容を表形式で示す説明図である。実施の形態２のスカラー倍算装置１Ｂにおいて、スカラー値ｋを１６ビット構成の「k=16'b1010 1010 1101 0111」とし、スカラー値ｋの最上位４ビットのビット列を分割スカラー値ｋ１｛k1=4'b1010｝、次の上位４ビットのビット列を分割スカラー値ｋ２｛k2=4'b1010｝とし、下位８ビットのうち上位４ビットのビット列を分割スカラー値ｋ３｛k3=4'b1101｝とし、最下位４ビットのビット列を分割スカラー値ｋ４｛k4=4'b0111｝とする。また、説明の都合上、スカラー値ｋの上位８ビットのビット列を分割スカラー値ｋ１’｛k1'=8'b1010 1010｝、スカラー値ｋの下位８ビットのビット列を分割スカラー値ｋ３’｛k3'=8'b1101 0111｝とする。
【００８５】
上述のように、スカラー値ｋを均等に４分割した分割スカラー値ｋ１〜ｋ４によりスカラー倍算処理を行うのが実施の形態２のスカラー倍算装置１Ｂである。
【００８６】
以下、適宜、図８〜図１０を参照して、実施の形態２のスカラー倍算装置１Ｂの演算内容を説明する。
【００８７】
スカラー倍算値ｋ×Ｐとなる演算式ｋ×Ｐは以下の式(5)ように変形できる。なお、式(5)はスカラー値ｋを分割スカラー値ｋ３’によって分解して表した式である。そして、式(5)の前半部分｛(ｋ-k3')×P）｝は図８(a)で示すようにして演算され、後半部分｛k3'×P｝は図８(b)に示すように演算される。
【００８８】
【数５】
2014191140.tif 000007
【００８９】
ここで、(ｋ-k3')は、下位８ｂｉｔのビット情報が全て“０”となるため、以下の式(6)に変形でき、式(6)は具体例を挙げて記述すると以下の式(7)のようになる。
【００９０】
【数６】
2014191140.tif 000008
【００９１】
【数７】
2014191140.tif 000009
【００９２】
なお、式(7)の３行目の「8'b1010 1010」は、分割スカラー値ｋ１’の値となる。すなわち、式(6)から、(ｋ-k3')は、図８(c)で示す８ビットのスカラー倍算処理後に得られた値（１７０Ｐ）を２８（＝２５６）のオフセット演算を行うことにより得られることがわかる。図８(c)からＰにオフセットとなる２８を演算すると、図８(d)に示すようになる。
【００９３】
そして、式(6)を式(5)に代入すると以下の式(8)が得られる。なお、式(8)の(k3'×P)は図８(e)に示すように、図８(b)で示す下位８ビットの状態から変化していない。
【００９４】
【数８】
2014191140.tif 000010
【００９５】
さらに、分割スカラー値ｋ１’及び分割スカラー値ｋ３’について、それぞれ上位４ビット及び下位４ビットに分離することにより、以下の式(9)を得る。式(9)による４つの項が図９(a)〜(d)に示すようになる。
【００９６】
【数９】
2014191140.tif 000011
【００９７】
式(9)において、(k1'-k2)及び(k3'-k4)は、下位４ビットが全て“０”となるため、それぞれ式(10)及び式(11)で表される。そして、式(10)は具体例を挙げて記述する以下の式(12)のようになる。なお、式(12)の３行目の「4'b1010」は分割スカラー値ｋ１となる。
【００９８】
【数１０】
2014191140.tif 000012
【００９９】
【数１１】
2014191140.tif 000013
【０１００】
【数１２】
2014191140.tif 000014
【０１０１】
したがって、式(10)（式(12)）における｛（ｋ１’−ｋ２）＝ｋ１×２４｝は、図１０(a)で示す４ビットのスカラー倍算処理後に得られた値（２５６０Ｐ）を２４（＝１６）のオフセット演算を行うことにより得られることがわかる。図１０(a)からＰにオフセットとなる２４を演算すると、図１０(b)に示すようになる。一方、｛k2×256P｝については、図１０(c)に示すように、図９(b)で示す状態から変化しない。
【０１０２】
同様に、式(11)は具体例を挙げて記述する以下の式(13)のようになる。なお、式(13)の３行目の「4'b1101」は分割スカラー値ｋ３となる。
【０１０３】
【数１３】
2014191140.tif 000015
【０１０４】
したがって、式(11)（式(13)）における｛(k3'-k4)=k1×２４｝は、図１０(d)で示す４ビットのスカラー倍算処理後に得られた値（１３Ｐ）を２４（＝１６）のオフセット演算を行うことにより得られることがわかる。図１０(d)からＰにオフセットとなる２４を演算すると、図１０(e)に示すようになる。一方、｛k4×P｝については、図１０(f)に示すように、図９(d)で示す状態から変化しない。
【０１０５】
そして、式(10)及び式(11)を式(9)に代入することにより、以下の式(14)を得ることができる。
【０１０６】
【数１４】
2014191140.tif 000016
【０１０７】
実施の形態２のスカラー倍算装置１Ｂでは、上記した式(14)スカラー倍算値ｋ×Ｐを求める基本演算式として採用する。
【０１０８】
（演算テーブル）
図１１は実施の形態２のスカラー倍算装置１Ｂの演算テーブル記憶部２内に格納された演算テーブルＴＢ２の内容を表形式で示す説明図である。
【０１０９】
同図において、ｋ１［ｉ］〜ｋ４［ｉ］は、ビット位置ｉにおける分割スカラー値ｋ１〜ｋ４のビット情報を意味する。そして、４’ｂ(b1)(b2)(b3)(b4)において、(b1)はｋ１［ｉ］のビット情報、(b2)はｋ２［ｉ］のビット情報、(b3)は分割スカラー値ｋ３のビット情報、(b4)は分割スカラー値ｋ４のビット情報を意味する。例えば、４’ｂ(b1)(b2)(b3)(b4)が４’ｂ１００１の場合、ｋ１［ｉ］及びｋ４［ｉ］が“１”で、ｋ２［ｉ］及びｋ３［ｉ］が共に“０”の場合を示している。
【０１１０】
同図に示すように、演算テーブルＴＢ２ではｋ１［ｉ］〜ｋ４［ｉ］のビット情報の組合せに対応して入力座標点Ｐにおける複数の（１６個の）事前倍数値（演算パラメータ）を設定している。具体的には、２’ｂ００００〜１１１１の順で、１６個の事前倍数値として、０Ｐ，１Ｐ，１６Ｐ，１７Ｐ，２５６Ｐ，２５７Ｐ，２７２Ｐ，２７３Ｐ，４０９６Ｐ，４０９７Ｐ，４１１２Ｐ，４１１３Ｐ，４３５２Ｐ，４３５３Ｐ，４３６８Ｐ，及び４３６９Ｐが設定される。
【０１１１】
上述した演算テーブルＴＢ２における１６個の事前倍数値は、式(14)に基づき予め演算により求めることができる。このように、演算テーブルＴＢ２は、ｋ１［ｉ］〜ｋ３［ｉ］が“１”の場合は２１２，２８及び２４のオフセット演算がそれぞれ行われることを事前に考慮にした１６個の事前倍数値を有している。すなわち、演算テーブルＴＢ２は分割スカラー値ｋ１〜ｋ３に関しそれぞれの下位のビット列に対しオフセット演算することにより得られる事前倍数値を有している。
【０１１２】
（楕円スカラー倍算アルゴリズムＡＲ１）
図１２は実施の形態２のスカラー倍算装置１Ｂのスカラー倍算処理として実行される楕円スカラー倍算アルゴリズムＡＲ２のプログラム内容を示す説明図である。図１３はスカラー値ｋの４分割想定時（｛k=0xAAD7; (k1=4'b1010) (k2=4'b1010) (k3=4'b1101) (K4=4'b0111)｝)における演算例ＥＸ２を表形式で示す説明図である。
【０１１３】
図１２に示すように、楕円スカラー倍算アルゴリズムＡＲ２はＣ言語仕様で記述されている。楕円スカラー倍算アルゴリズムＡＲ２は、最初に初期設定（j=3）を行った後、サブルーチンＳＲ２１が実行される。
【０１１４】
サブルーチンＳＲ２１では４ビットの分割スカラー値ｋ１〜ｋ４のうち少なくとも一つのビット情報が“１”となる最上位ビットを検出し、そのビット位置（ｊの値）で「Ｑ＝ｔｂｌ（｛ｋ１[ｊ]，ｋ２［ｊ］，ｋ３［ｊ］，ｋ４［ｊ］｝）」とした後、変数ｊをデクリメントして終了する。
【０１１５】
｛Ｑ＝ｔｂｌ（｛ｋ１[ｊ]，ｋ2［ｊ］，ｋ３［ｊ］，ｋ４［ｊ］｝）｝は、図１１で示したｋ１［ｊ］〜ｋ４［ｊ］の組合せに対応する事前倍数値をＱとして設定することを意味する。図１３で示す演算例ＥＸ２では、ｊ＝３で、ｋ１[３]＝“１”、ｋ２［３］＝１，ｋ３［３］＝１，ｋ４［３］＝０となるため、Ｑ＝４３６８Ｐに設定して、サブルーチンＳＲ２１を終了する。
【０１１６】
サブルーチンＳＲ２１の終了後、サブルーチンＳＲ２２によりＥＣＤＢＬ演算及びＥＣＡＤＤ演算が、分割スカラー値ｋ１〜ｋ４に対し、変数ｊで示すビット位置から下位ビットにかけて順次実行され、最下位ビット（ｉ＝０）時のＥＣＡＤＤ演算後の結果がスカラー倍算値ｋ×Ｐとして得られる。
【０１１７】
サブルーチンＳＲ２２において、ＥＣＤＢＬ演算は分割スカラー値ｋ１〜ｋ４のビット毎に行われ、ＥＣＡＤＤ演算は対応するビット位置ｉにおける分割スカラー値ｋ１〜ｋ４のビット情報の少なくとも一つが“１”の場合のみ選択に行われる。この際、ＥＣＡＤＤ演算は、図１１で示した演算テーブルＴＢ２を参照して、Ｑにｔｂｌ（｛ｋ１[ｉ]，ｋ2［ｉ］，ｋ３［ｉ］，ｋ４［ｉ］｝）を加算する態様で行われる。
【０１１８】
すなわち、サブルーチンＳＲ２２におけるＥＣＡＤＤ演算は、ｋ１［ｉ］は“１”の場合は４０９６Ｐを加算し、“０”の場合は加算せず、ｋ２［ｉ］が“１”の場合は２５６Ｐを加算し“０”の場合は加算せず、ｋ３［ｉ］は“１”の場合は１６Ｐを加算し、“０”の場合は加算せず、ｋ４［ｉ］が“１”の場合はＰを加算し“０”の場合は加算しない態様のＥＣＡＤＤ演算を行う。
【０１１９】
なお、サブルーチンＳＲ２２では、｛if((k1[i]=1)||(k2[i]=1)||(k3[i]=1)||(k4[i]=1))｝の分岐制御により、ｋ１［ｉ］〜ｋ４［ｉ］が全て“０”場合はスキップさせることによりＥＣＡＤＤ演算自体の実行を省略しているが、演算テーブルＴＢ２において、４’ｂ００００の場合に“０”が事前倍数値として設定されているため、上記分岐制御を省略しても良い。
【０１２０】
その結果、上記想定時において、図１３のｉ＝０の時のＥＣＡＤＤ演算後の値「４３７３５Ｐ」がスカラー倍算値ｋ×Ｐとして得られる。
【０１２１】
このように、実施の形態２のスカラー倍算装置１Ｂにおけるスカラー倍演算部３は、演算テーブル記憶部２に格納された演算テーブルＴＢ２を参照することにより、分割スカラー値ｋ１〜ｋ４（第１〜第４のスカラービット列）に対しビット単位に同時にスカラー倍算処理内のＥＣＡＤＤ演算を実行することを特徴としている。
【０１２２】
実施の形態２のスカラー倍算装置１Ｂは、上記特徴を有することにより、スカラー倍算処理内容（ＥＣＡＤＤ演算）に対し電力解析を行っても、分割スカラー値ｋ１〜ｋ４のうち、図１３の矢印に示すように、いずれのスカラー値のビット情報に対するＥＣＡＤＤ演算であるか識別することができないため、サイドチャネル攻撃に強い耐タンパー性を有するという効果を奏する。
【０１２３】
さらに、スカラー倍算装置１Ｂを実現する構成は実質的にスカラー倍算装置１と同じでるため、スカラー倍算装置１Ｂは、スカラー倍算処理を行う構成部を一つ（スカラー倍演算部３）にした比較的簡単な装置構成で実現され、装置の低コスト化を図ることができる。る。
【０１２４】
加えて、演算テーブル記憶部２に、入力座標点Ｐにおける複数の事前倍算値を有する演算テーブルＴＢ２を予め格納しておくことにより、スカラー倍演算部３によるスカラー倍算処理時に複数の事前倍算値の算出処理は不要となり、電力解析等から秘匿することができるため、効率的、かつ耐タンパー性の高いスカラー倍算装置を得ることができる。
【０１２５】
さらに、実施の形態２のスカラー倍算装置１Ｂでは、スカラー値ｋを４分割した分割スカラー値ｋ１〜ｋ４を対するスカラー倍算処理をビット単位に同時に行っているため、実施の形態１のスカラー倍算装置１以上に耐タンパー性を高くすることができる。
【０１２６】
＜実施の形態３＞
図１４は実施の形態３のスカラー倍算装置１Ｃの構成を示すブロック図である。同図に示すように、スカラー倍算装置１Ｃは入力座標点Ｐ(X,Y)、ＫＢビットのスカラー値ｋ及びスカラー値ｋの分割数ｎを受け、入力座標点Ｐのスカラー倍算値ｋ×Ｐを得ている。
【０１２７】
スカラー倍算装置１Ｃは演算テーブル記憶部２及びスカラー倍演算部４から構成されており、スカラー倍演算部４は内部に演算テーブル作成部４１及びスカラー倍算実行部４２を有している。
【０１２８】
スカラー倍演算部４内の演算テーブル作成部４１は、入力座標点Ｐ及び分割数ｎに基づきＫＢビットの前記スカラー値をｎ分割して得られるｎ個の分割スカラー値（第１〜第ｎのスカラービット列の）のビット情報の組合せに対応した複数の事前倍数値（演算パラメータ）を算出し、複数の事前倍数値を有する演算テーブルＴＢを演算テーブル記憶部２に格納する。
【０１２９】
なお、演算テーブルＴＢとしては、スカラー値ｋのビット数ＫＢが１６ビットで分割数ｎが“２”の場合、図３で示す実施の形態１の演算テーブルＴＢ１となり、ビット数ＫＢが１６ビットで分割数ｎが“４”の場合、図１１で示す実施の形態２の演算テーブルＴＢ２となる。
【０１３０】
スカラー倍算実行部４２は、入力座標点Ｐ及びＫＢビットのスカラー値ｋを受け、スカラー値ｋをビット列に沿って均等にｎ分割して得られる分割スカラー値ｋ１〜ｋｎ（第１〜第ｎのスカラービット列）を用いてスカラー倍算値ｋ×Ｐを得るスカラー倍算処理を行う。
【０１３１】
スカラー倍算実行部４２は、実施の形態１及び実施の形態２と同様、演算テーブル記憶部２に格納された演算テーブルＴＢを参照することにより、分割スカラー値ｋ１〜ｋｎに対しビット単位に同時に上記スカラー倍算処理を実行する。
【０１３２】
このように、実施の形態３のスカラー倍算装置１Ｃは、スカラー倍演算部４内に演算テーブルＴＢを作成する演算テーブル作成部４１を有しているため、演算テーブルＴＢを作成して演算テーブル記憶部２に予め格納する処理をスカラー倍算装置１Ｃ自体によって行うことができる。
【０１３３】
（変形例）
実施の形態３では演算テーブル作成部４１が演算テーブルＴＢを全て作成する例を示したが、実施の形態１や実施の形態２のように、分割数ｎが固定である場合、分割数ｎに対応して、入力座標点Ｐを変数とした予備演算テーブルを予め準備しておき（図３及び図１１で示す演算テーブルＴＢ１及びＴＢ２のＰを変数としたテーブル）、実際に入力座標点Ｐが入力された後に予備演算テーブルに入力座標点Ｐを代入して演算テーブルＴＢを完成させる態様も考えられる。この変形例は実施の形態１及び実施の形態２にも適用可能である。
【０１３４】
＜スカラー倍算方法＞
実施の形態１〜実施の形態３で示したスカラー倍算装置１（１Ｂ，１Ｃ）を用いて行う、入力座標点Ｐ及びスカラー値ｋからスカラー倍算値ｋ×Ｐを得るスカラー倍算方法は以下のステップ(a) 及び(b)を実行することにより実現される。
【０１３５】
(a) 入力座標点Ｐ及びスカラー値ｋのビット数ＫＢに基づき、スカラー値ｋをビット列に沿って均等にｎ分割して得られる分割スカラー値ｋ１〜ｋｎ（第１〜第ｎのスカラービット列）のビット情報の組合せに対応した複数の事前倍数値（演算パラメータ）を有する演算テーブルＴＢを得る。
【０１３６】
(b) 演算テーブルＴＢを参照して、分割スカラー値ｋ１〜ｋｎに対しビット単位に同時にスカラー倍算処理を実行することにより、入力座標点Ｐのスカラー倍算値ｋ×Ｐを得る。
【０１３７】
ステップ(a)としては、実施の形態１及び実施の形態２のように、演算テーブル記憶部２に演算テーブルＴＢ１（ＴＢ２）を予め格納する処理として行っても良く、実施の形態３のようにスカラー倍算装置１Ｃ自体が演算テーブルＴＢも自動作成する処理として行っても良い。
【０１３８】
ステップ(b)としては、実施の形態１による２分割した分割スカラー値ｋ１及びｋ２に対するスカラー倍算処理や実施の形態２による４分割した分割スカラー値ｋ１〜ｋ４に対するスカラー倍算処理等がある。なお、分割数ｎについてはスカラー値ｋのビット数ＫＢを均等に分割可能であれば任意である。
【０１３９】
このように、スカラー倍算方法は、ステップ(b) で実行されるスカラー倍算処理内容（ＥＣＡＤＤ演算）に対し電力解析を行っても、分割スカラー値ｋ１〜ｋｎのうちいずれの分割スカラー値のビット情報に対するＥＣＡＤＤ演算であるか識別することができないため、サイドチャネル攻撃に強い耐タンパー性を有するという効果を奏する。
【０１４０】
加えて、ステップ(a) において、入力座標点Ｐにおける複数の事前倍算値を有する演算テーブルＴＢを獲ているため、ステップ(b) におけるスカラー倍算処理時に複数の事前倍算値の算出処理は不要となり、電力解析等から秘匿することができるため、効率的、かつ耐タンパー性の高いスカラー倍算方法を実現することができる。
【０１４１】
＜その他＞
実施の形態１のスカラー倍演算部３、実施の形態３のスカラー倍演算部４（演算テーブル作成部４１，スカラー倍算実行部４２）は、例えば、ソフトウェアに基づくＣＰＵを用いたプログラム処理によって実行される。
【０１４２】
なお、本発明は、その発明の範囲内において、各実施の形態を自由に組み合わせたり、各実施の形態を適宜、変形、省略したりすることが可能である。
【符号の説明】
【０１４３】
１，１Ｂ，１Ｃ  スカラー倍算装置
２  演算テーブル記憶部
３，４  スカラー倍演算
４１  演算テーブル作成部
４２  スカラー倍算実行部
ＴＢ，ＴＢ１，ＴＢ２  演算テーブル
【図１】
2014191140.tif 000017
【図２】
2014191140.tif 000018
【図３】
2014191140.tif 000019
【図４】
2014191140.tif 000020
【図５】
2014191140.tif 000021
【図６】
2014191140.tif 000022
【図７】
2014191140.tif 000023
【図８】
2014191140.tif 000024
【図９】
2014191140.tif 000025
【図１０】
2014191140.tif 000026
【図１１】
2014191140.tif 000027
【図１２】
2014191140.tif 000028
【図１３】
2014191140.tif 000029
【図１４】
2014191140.tif 000030
【図１５】
2014191140.tif 000031
【図１６】
2014191140.tif 000032