(57)【要約】【課題】演算装置、演算方法及びプログラムにおいて、秘密情報の特定を難しすることを目的とする。【解決手段】べき指数を因数に因数分解し、前記指数分解手段で因数分解された因数を和の数列で表現し、前記和の数列をランダムな順序で演算して、前記因数の楕円演算のスカラー倍を加算演算で演算するように構成する。【選択図】図１
2014235384.tif 000002
【特許請求の範囲】
【請求項１】
べき指数を因数に因数分解する指数分解手段と
前記指数分解手段で因数分解された因数を和の数列で表現する総和表現手段と
前記和の数列の演算順序をランダムにして、前記因数の楕円演算のスカラー倍を加算演算で演算する加算手段
を有することを特徴とする、演算装置。
【請求項２】
前記指数分解手段は、素因数分解で因数分解を行うことを特徴とする、請求項１の演算装置。
【請求項３】
前記総和表現手段は、総和表現をフィボナッチ数列で行うことを特徴とする、請求項１または２の演算装置。
【請求項４】
前記指数分解手段で因数分解された因数の演算の結果を記憶手段の記憶領域にランダムな順序で記憶することを特徴とする、請求項１乃至３のいずれか１項記載の演算装置。
【請求項５】
前記指数分解手段で因数分解された因数の演算の結果が記憶手段に記憶されている記憶領域からランダムに読み出すことを特徴とする、請求項１乃至４のいずれか１項記載の演算装置。
【請求項６】
前記総和表現手段は、
整数値ｋｔに対して一般化フィボナッチ数列Ｆ（ｎ）により、Ｆ（ｎ＋１）＞ｋｔ＞Ｆ（ｎ）を演算し、演算したｋｔをｋｔ−Ｆ（ｎ）としてＦ（ｎ＋１）＞ｋｔ＞Ｆ（ｎ）の演算を繰り返すことを特徴とする、請求項１の演算装置。
【請求項７】
べき指数を因数に因数分解する指数分解手順と
前記指数分解手段で因数分解された因数を和の数列で表現する総和表現手順と
前記和の数列の演算順序をランダムにして、前記因数の楕円演算のスカラー倍を加算演算で演算する加算手順
を有することを特徴とする、演算方法。
【請求項８】
楕円曲線演算のスカラー倍演算をコンピュータに実行させるプログラムであって、
べき指数を因数に因数分解する指数分解手順と
前記指数分解手段で因数分解された因数を和の数列で表現する総和表現手順と
前記和の数列の演算順序をランダムにして、前記因数の楕円演算のスカラー倍を加算演算で演算する加算手順を
前記コンピュータに実行させることを特徴とする、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算装置、演算方法及びプログラムに関する。
【背景技術】
【０００２】
公開鍵暗号方式は、必要となる計算量が膨大であり数学的に求解が困難な問題に、安全性の根拠をおいている。離散対数問題は、このように数学的に求解が困難な問題の一例である。
【０００３】
離散対数問題は、ある群Ｇにおいて、その生成元ｇと、整数値ｅによるべき乗の値ｈ＝ｇｅから、元の整数値ｅを求めるという問題である。ここでいうべき乗は、群Ｇにおける群演算「・」をｈ＝ｇ・ｇ・  …  ・ｇのように、｛（べき指数）−１｝回だけ繰り返し適用する演算のことであり、群演算については以下同様に記載する。
【０００４】
このような離散対数問題を構成する群Ｇの一例として、有限体上に乗法群、楕円曲線上の点がなす加法群などが挙げられる。暗号装置は、離散対数問題を構成する群Ｇにおけるべき乗演算を行うことで暗号処理を実現できる。
【０００５】
離散対数問題に基づく暗号処理では、べき指数に秘密情報を設定することが多い。例えばべき乗演算する際に、暗号装置がサイドチャネル攻撃を受けて、べき指数が特定されてしまうと、秘密情報を取得されてしまう可能性がある。
【０００６】
例えば楕円曲線の演算には、楕円曲線スカラー倍算演算を用いることができる。楕円曲線スカラー倍算演算は、与えられた楕円曲線上の点と、楕円曲線のスカラー倍係数値を演算に用いる。しかし、暗号装置が楕円曲線スカラー倍算演算を実行する際に観測される消費電力または漏洩電波を解析して処理時間などを計測するサイドチャネル攻撃が行われたり、ソースコードを不正に入手して解読されたりすると、秘密情報である楕円曲線のスカラー倍係数値が特定されてしまう可能性がある。
【０００７】
従来、例えば楕円曲線のスカラー倍係数値をフィボナッチ（Ｆｉｂｏｎａｃｃｉ）数列による和の数列で表現することで、べき乗演算の際における楕円曲線のスカラー倍係数値の特定を難しくする手法が提案されている（例えば、特許文献１）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１１−８５７５０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、上述した提案手法では、楕円曲線スカラー倍算演算の演算結果を記憶領域へ記憶する際に、または、当該演算結果を記憶領域から読み出す際に、楕円曲線のスカラー倍係数値が特定される可能性があった。
【００１０】
本発明の１つの側面は、上述の課題に鑑みてなされたものであり、秘密情報の特定を難しくすることを目的とする。
【課題を解決するための手段】
【００１１】
一態様における演算装置は、べき指数を因数に因数分解する指数分解手段と、前記指数分解手段で因数分解された因数を和の数列で表現する総和表現手段と、前記和の数列の演算順序をランダムにして、前記因数の楕円演算のスカラー倍を加算演算で演算する加算手段を有する。
【発明の効果】
【００１２】
秘密情報の特定を難しくすることができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態における演算装置の機能構成の一例を説明する機能ブロック図である。
【図２】べき乗演算部による演算処理の流れの一例を示すフローチャートである。
【図３】初期化処理部による初期化処理の一例を示すフローチャートである。
【図４】べき乗演算制御部による和の数列に分解する処理の一例を示すフローチャートである。
【図５】インデックス変換部による処理の流れの一例を示すフローチャートである。
【図６】事前計算部による処理の一例の流れを示すフローチャートである。
【図７】総和計算処理部による処理の流れの一例を示すフローチャートである。
【図８】本発明の一実施形態における演算装置のハードウェア構成図の一例を説明するブロック図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について説明する。
【００１５】
図１は、本発明の一実施形態における演算装置の機能構成の一例を説明する機能ブロック図である。
【００１６】
図１に示す演算装置１０００は、楕円曲線演算のスカラー倍演算する演算装置の一例である。演算装置１０００は、制御部１１と、指数指数分解部１２と、計算結果記憶部１３と、べき乗演算部１４を有する。
【００１７】
制御部１１は、演算装置１０００に対するデータの入出力を制御する。例えば、制御部１１は、演算装置１０００と外部装置（図示せず）との間でデータを入出力するインタフェースを有してもよく、演算に必要なパラメータを演算装置１０００に入力したり、演算結果を外部装置へ出力したりする。
【００１８】
指数分解部１２は、べき指数を因数に因数分解する指数分解手段の一例である。指数分解部１２は、外部装置から制御部１１を介して入力された任意の値ｋを、例えば下記の（式１）のようにｓ個の項からなる乗算の数式に因数分解する。
【００１９】
ｋ＝ｋ１×ｋ２×ｋ３×・・×ｋｔ×・・×ｋｓ  （式１）
計算結果記憶部１３は、後述するべき乗演算部１４から出力される各演算結果を一時的に記憶する。
【００２０】
べき乗演算部１４は、楕円曲線のスカラー倍演算を行う。制御部１１から楕円曲線パラメータｒ、整数値ｋｔ、楕円曲線上の点Ｐの座標値などのパラメータが入力されると、入力されたパラメータから演算した結果Ｑを出力する。離散対数問題に基づく暗号系においては、群Ｇにおけるべき乗演算を行うことにより、その暗号処理を実現している。べき乗演算については後述する。
【００２１】
べき乗演算部１４は、初期化処理部１４１と、事前計算部１４２と、楕円曲線加算処理部１４３と、インデックス変換処理部１４４と、総和計算処理部１４５と、楕円曲線２倍算処理部１４６と、インデックス記憶部１４７と、事前計算結果記憶部１４８と、べき乗演算制御部１４９を有する。
【００２２】
初期化処理部１４１は、後述する、べき乗演算の初期化処理を行う。
【００２３】
事前計算部１４２は、楕円曲線演算の計算を行い、計算結果を事前計算結果記憶部１４８に記憶する。
【００２４】
楕円曲線加算処理部１４３は、和の数列をランダムな順序で演算して、楕円演算のスカラー倍を加算演算で演算する加算手段の一例である。楕円曲線加算処理部１４３は、後述するように、インデックス記憶部１４７と事前計算結果記憶部１４８に記憶されている計算結果に基づいて、楕円曲線スカラー倍演算を加算処理にて計算する。
【００２５】
インデックス変換処理部１４４は、後述する計算結果をインデックス記憶部１４７へ記憶する。
【００２６】
総和計算処理部１４５は、事前計算結果記憶部１４８に記憶されている楕円曲線計算結果を用いて後述する加算演算を行い、この加算演算の結果をべき乗計算部１４の出力とする。
【００２７】
楕円曲線２倍算処理部１４６は、楕円曲線演算の２倍演算を行い、計算結果を事前計算結果記憶部１４８に記憶する。
【００２８】
インデックス記憶部１４７は、後述するように、インデックス変換処理部１４４の計算結果を記憶する。
【００２９】
事前計算結果記憶部１４８は、後述するように、事前計算部１４２と楕円曲線２倍算処理部１４６の演算結果を記憶する。
【００３０】
べき乗演算制御部１４９は、指数指数分解部１２で因数分解された因数を和の数列で表現する総和表現手段の一例である。べき乗演算制御部１４９は、後述するように、入力されるべき指数を和の数列で表現し、和の数列で表現された各項の演算を行う。
【００３１】
なお、指数分解部１２が行う因数分解は、上述の（式１）右辺の各項が素数になるように行う素因数分解であってもよい。
＜べき乗演算部による演算＞
図２は、べき乗演算部１４による演算処理の流れの一例を説明するフローチャートである。この例では、べき乗演算部１４の演算処理は、以下に説明する工程Ｓ１１〜Ｓ１７を含む演算方法により実現できる。
【００３２】
図２に示すように、べき乗演算部１４は、べき乗演算が開始されると初期化を行う（Ｓ１１）。初期化は計算結果記憶部１３に記憶されている出力値Ｑの値を０する。
【００３３】
次に、指数分解部１２は、制御部１１から入力されてくるパラメータｋを上述の（式１）の形式になるように因数分解し、計算結果記憶部１３に記憶する（Ｓ１２）。パラメータｋは工程Ｓ１２で、（式１）よりｓ個の項からなる乗算で表され、因数分解された項ｋｔごとに、べき乗演算制御部１４９によって合計ｓ回のべき乗演算が繰り返し行われる（Ｓ１３）。
【００３４】
べき乗演算部１４は、係数ｋとする楕円曲線のスカラー倍演算をし（Ｓ１４）、工程Ｓ１４で計算された値を計算結果記憶部１３に記憶する（Ｓ１５）。
【００３５】
べき乗演算部１４は、ｓ回の演算を終了した後、計算結果Ｑを出力する（Ｓ１６）。
【００３６】
次に、べき乗演算部１４は、制御部１１から入力されたすべてのパラメータの処理が終了したか否か判断（Ｓ１７）し、処理が終了したと判断した場合には（Ｓ１７において、ＹＥＳ）、処理を終了する。また、演算装置１０００に続けて新たに入力があったなどで処理が継続すると判断した場合（Ｓ１７において、ＮＯ）、処理は工程Ｓ１１の処理に戻り、次の制御部１１から入力されたパラメータのべき乗演算を開始する。
＜初期化処理＞
図３は、初期化処理部による初期化処理の一例を説明するフローチャートである。
【００３７】
初期化処理は、上述のべき乗演算部１４によるべき乗演算のうち、べき乗演算制御部１４９による処理（Ｓ１４）が開始された際に、初期化処理部１４１によって行われる。ここでいう初期化処理は、工程Ｓ１１と異なり、後述する、べき指数の演算などに対する初期化処理をいう。
【００３８】
初期化処理が開始されると、初期化処理部１４１は、べき乗演算に必要なパラメータを読み出す（Ｓ３０１）。具体的には、楕円曲線ドメインパラメータｒ、スカラー倍の係数ｋｔ、楕円曲線上の座標点Ｐの値が読み出される。ここで、楕円曲線ドメインパラメータｒは、楕円曲線を（式２）とした場合の位数を示す。
【００３９】
【数１】
2014235384.tif 000003
次に、初期化処理部１４１は、入力されたｋｔが[ｒ／２]より大きい値か否かを判断する（Ｓ３０２）。ここで、[ｘ]はｘを超えない最大の整数値を示し、以下同様の表記を用いる。ｋｔは、スカラー倍演算時に演算回数を決めるパラメータであるが、小さい値であると計算回数が少なくなり、係数の特定が容易になってしまう。そこで、ｋｔの値の置き換えを行う（Ｓ３０３）。
【００４０】
ｋｔが[ｒ／２]より大きい値ではない場合（Ｓ３０２でＹＥＳ）、ｋｔとＰの置き換えを行う工程Ｓ３０３に進む。
【００４１】
ｋｔが[ｒ／２]より大きい値である場合（Ｓ３０２でＮＯ）、ｋｔの置き換えは行わず、入力されたｋｔで工程Ｓ３０４に進む。
【００４２】
下記（式３）が示すように、ｋｔをｒ−ｋｔ、Ｐを−Ｐと置き換えることが可能である。
【００４３】
【数２】
2014235384.tif 000004
例えばｋｔ＝３のように値が小さい場合、上記（式３）でｒ＝２０１１とすると、ｋｔの置き換え処理を行うとｋｔ＝２００８となる。
【００４４】
次に、初期化処理部１４１は、一般化フィボナッチ数列Ｆについて、Ｆ（ｎ＋１）＞ｋｔかつＦ（ｎ）＞ｋｔを満たすｎの値を求める（Ｓ３０４）。ここで、一般化フィボナッチ数列Ｆは下記（式４）の総和表現の数列で表される。
Ｆ（ｎ＋１）＝Ｆ（ｎ）＋Ｆ（ｎ−１）  （式４）
なお、一般的なフィボナッチ数列は初期値がＦ（１）＝１、Ｆ（２）＝１である。リュカ（Ｌｕｃａｓ）数は初期値がＦ（１）＝１、Ｆ（２）＝３である。
【００４５】
初期化処理部１４１は、工程Ｓ３０４で求めたｎから[（ｎ＋１）／２]を演算する（Ｓ３０５）。フィボナッチ数列での和の数列での表現では、隣り合う項、つまりＦ（ｎ＋１）とＦ（ｎ）が同時に現れることはないため、フィボナッチ数列での和の数列での表現で項の数は[（ｎ＋１）／２]となる。
【００４６】
（式４）より、一般化フィボナッチ数列Ｆの任意の項Ｆ（ｃ）は下記の（式４−１）で表すことができる。
Ｆ（ｃ）＝Ｆ（ｃ−１）＋Ｆ（ｃ−２）  （式４−１）
（式４−１）のＦ（ｃ−１）、Ｆ（ｃ−２）を同様に総和表現の数列で表していくことで、項の数を一定数である[（ｎ＋１）／２]にすることができる。
【００４７】
さらに、整数ｂについて、群Ｇの元ｘに対するべき乗演算ｙ＝ｘｂを考えると、Ｇのｘ（ｉ）について、ｘ（ｉ）＝ｘＦ（ｉ）として定める。すると、ｘ（ｉ）は、一般化フィボナッチ数列Ｆの（式４）より、ｘ（ｉ＋１）＝ｘ（ｉ）・ｘ（ｉ−１）として群演算により求めることができる。ｙ＝ｘｂを用いてｙ＝ｘｂ＝ΠｉｘＦ（ｉ）＝Πｉｘ（ｉ）とできるので、上述の通り、フィボナッチ数列での和の数列での表現では項の数を一定数である[（ｎ＋１）／２]にすることができるため、Πｉｘ（ｉ）の群演算の回数を一定にすることができる。
【００４８】
図４は、べき乗演算制御部１４９による和の数列に分解する処理の一例を説明するフローチャートである。
【００４９】
上述の（式４）で示したように、一般化フィボナッチ数列Ｆでｎ＋１番目の値を求めるにはｎ番目とｎ−１番目の値が必要となる。Ｆ（ｎ＋１）の値を求めるため、べき乗演算制御部１４９は、工程Ｓ１２で因数分解された各項の値を和の数列に分解する処理に用いる各変数の初期値を設定する（Ｓ４０１）。具体的には、工程Ｓ３０４で求めたｎを変数ｉに設定する。さらに変数ｖに０を、変数ｏｆｆｓに１を設定し、Ｆ（ｎ＋１）、Ｆ（ｎ）の値を配列Ｔ（２）、Ｔ（１）に、Ｔ（０）には０を設定する。
【００５０】
次に、べき乗演算制御部１４９は、ｉが０より大きい値か否かを判断する（Ｓ４０２）。ｉが０より大きい値と判断した場合（Ｓ４０２にてＹＥＳ）は工程Ｓ４０３の処理に進み、ｉが０より大きい値ではないと判断した場合（Ｓ４０２にてＮＯ）は後述する図５の処理に進む。
【００５１】
ｉが０より大きい値と判断した場合（Ｓ４０２にてＹＥＳ）、べき乗演算制御部１４９は、ｋｔがＴ（ｏｆｆｓ）より小さい値かを判断する（Ｓ４０３）。べき乗演算制御部１４９は、ｋｔがＴ（ｏｆｆｓ）より小さい値と判断した場合（Ｓ４０３にてＹＥＳ）は工程Ｓ４０４の処理に進み、ｋｔがＴ（ｏｆｆｓ）より小さい値ではないと判断した場合（Ｓ４０３にてＮＯ）は工程Ｓ４０５の処理に進む。
【００５２】
べき乗演算制御部１４９は、ｋｔがＴ（ｏｆｆｓ）より小さい値と判断した場合、変数ｆｌｇに０を設定する（Ｓ４０４）。
【００５３】
一方、べき乗演算制御部１４９は、ｋｔがＴ（ｏｆｆｓ）より小さい値ではないと判断した場合、変数ｆｌｇに１を設定する（Ｓ４０５）。
【００５４】
工程Ｓ４０４または工程Ｓ４０５の処理の後、べき乗演算制御部１４９は、ｋｔにｋｔ−Ｔ（ｆｌｇ×ｏｆｆｓ）の演算結果を代入してｋｔの値を演算する（Ｓ４０６）。前段の工程Ｓ４０４でｆｌｇ＝０であった場合は、工程Ｓ４０１でＴ（０）に０が設定されているため、この場合は工程Ｓ４０６においてｋｔの値は変更されない。
【００５５】
次に、べき乗演算制御部１４９は、変数ｔｍｐの値を、１または2の値を切り替える演算をする（Ｓ４０７）。ｏｆｆｓには、１または２の値が入力されているため、ｏｆｆｓの値を減算することで、ｏｆｆｓの数値に対応してｔｍｐの値を切り替える。
【００５６】
Ｔ（ｔｍｐ）−Ｔ（ｏｆｆｓ）は、Ｆ（ｎ＋１）−Ｆ（ｎ）の演算である。（式４）は下記の（式４−２）に変形することができる。
Ｆ（ｎ−１）＝Ｆ（ｎ＋１）−Ｆ（ｎ）  （式４−２）
したがって、Ｆ（ｎ＋１）とＦ（ｎ）の値からＦ（ｎ−１）の値を求めることができる（Ｓ４０８）。
【００５７】
次の工程Ｓ４０８の演算のために、べき乗演算制御部１４９は、ｏｆｆｓにｔｍｐの値を設定する（Ｓ４０９）。
【００５８】
べき乗演算制御部１４９は、工程Ｓ４０８で演算した結果を、インデックス記憶部１４７の記憶領域である配列ｉｎｄｅｘ、配列ｌｉｎｋに記憶する（Ｓ４１０）。
【００５９】
本実施形態では、工程Ｓ４０８までで演算した結果を、配列のアドレスをアドレス順（例えば、連続するアドレスの昇順）ではなく、ランダムな順に選択して記憶する。和の演算では四則演算の交換法則が成り立つので、下記（式５）を例えば（式６）のように、加算する順序を変更しても求まるＲの値は変わらない。
Ｒ＝Ｒ１＋Ｒ２＋Ｒ３  （式５）
Ｒ＝Ｒ２＋Ｒ１＋Ｒ３  （式６）
なお、以下の説明では、配列のランダムなアドレスに、演算の結果などのデータを記憶する関数をλとする。べき乗演算の演算結果を、配列のアドレスをランダムな順に選択して記憶することで、アルゴリズムの特定を難しくすることができる。
【００６０】
さらに、べき乗演算制御部１４９は、ｖにｖへｆｌｇを加算した値を設定し（Ｓ４１１）、ｉにｉから１を減算した値を設定し（Ｓ４１２）、工程Ｓ４０２の処理に戻る。
【００６１】
図５は、インデックス変換部１４４による処理の流れの一例を説明するフローチャートである。
【００６２】
インデックス変換部１４４は、図３の工程Ｓ３０５で求めたｍを変数ｊに設定する（Ｓ５０１）。
【００６３】
次に、インデックス変換部１４４は、ｊが０より大きい値か否かを判断する（Ｓ５０２）。ｊが０より大きい値と判断した場合（Ｓ５０２にてＹＥＳ）は工程Ｓ５０３の処理に進み、ｊが０より大きい値ではないと判断した場合（Ｓ５０２にてＮＯ）は後述する図６の処理に進む。
【００６４】
ｊが０より大きい値と判断した場合、インデックス変換部１４４は、ｊ＝ｍか否かを判断する（Ｓ５０３）。ｊ＝ｍと判断した場合（Ｓ５０３にてＹＥＳ）は工程Ｓ５０４の処理に進み、ｊ＝ｍでないと判断した場合（Ｓ５０３にてＮＯ）は工程Ｓ５０５の処理に進む。
【００６５】
ｊ＝ｍと判断した場合、インデックス変換部１４４は、変数ｆｌｇに０を設定する（Ｓ５０４）。ｊ＝ｍでないと判断した場合、インデックス変換部１４４は、変数ｆｌｇに１を設定する（Ｓ５０５）。工程Ｓ５０４または工程Ｓ５０５の処理の後、インデックス変換部１４４は、１〜ｖの範囲で乱数ｕを生成する（５０６）。
【００６６】
インデックス変換部１４４は、配列ｉｎｄｅｘ（λ（ｕ））に記憶するｉｎｄｅｘ（λ（ｕ））−ｆｌｇを演算し（Ｓ５０７）、配列ｉｎｄｅｘ（λ（ｖ＋１））に記憶するｉｎｄｅｘ（λ（ｕ））−ｆｌｇを演算する（Ｓ５０８）。インデックス変換部１４４は、配列ｌｉｎｋ（λ（ｖ＋１））に記憶するｌｉｎｋ（λ（ｕ））を演算し（Ｓ５０９）、配列ｌｉｎｋ（λ（ｕ））に記憶するｆｌｇ×λ（ｖ＋１）＋（１−ｆｌｇ）×ｌｉｎｋ（ｕ）を演算する（Ｓ５１０）。
【００６７】
インデックス変換部１４４は、工程Ｓ５０７、工程Ｓ５０８、工程Ｓ５０９、及び工程Ｓ５１０の演算結果をインデックス記憶部１４７に記憶する（Ｓ５１１）。さらに、インデックス変換部１４４は、ｖにｆｌｇを加算した値を設定し（Ｓ５１２）、ｊにｊから１を減算した値を設定し（Ｓ５１３）、工程Ｓ５０２の処理に戻る。
【００６８】
図６は、事前計算部１４２による処理の一例の流れを説明するフローチャートである。
【００６９】
事前計算部１４２は、図３の工程Ｓ３０１で読み込まれたＰの値を、事前計算結果記憶部１４８の記憶領域である配列ｐｒｅｃａｌｃに記憶する（Ｓ６０１）。
【００７０】
次に、楕円曲線２倍算処理部１４６がＰの２倍演算を演算し（Ｓ６０２）、演算した２Ｐの値を事前計算結果記憶部１４８に記憶する（Ｓ６０３）。
【００７１】
事前計算部１４２は、変数ｉに２を設定し（Ｓ６０４）、ｉがｎより大きい値か否かを判断する（Ｓ６０４）。事前計算部１４２は、ｉがｎより大きい値と判断した場合（Ｓ６０５にてＹＥＳ）は工程Ｓ６０６の処理に進み、ｉがｎより大きい値ではないと判断した場合（Ｓ６０５にてＮＯ）は図７の処理に進む。
【００７２】
事前計算部１４２は、工程Ｓ６０１と工程Ｓ６０３で初期値であるＰと２Ｐを用いて楕円曲線スカラー倍演算を加算処理にて計算する（Ｓ６０６）。例えば３Ｐであれば、２ＰとＰを加算して求めることができる。加算演算を繰り返して、加算演算でスカラー倍演算と同様の計算結果を得ることができる。加算する順序は四則演算の交換法則により、どのような順序でも計算結果は変わらないので、計算結果を配列ｐｒｅｃａｌｃのアドレス順ではなくランダムなアドレス順に記憶していく。
【００７３】
なお、配列のランダムなアドレスから、演算の結果などの記憶されているデータを読み出す関数をμとする。
【００７４】
さらに、ｉにｉへ１を加算した値を設定し（Ｓ６０７）、工程Ｓ６０５の処理に戻る。
【００７５】
図７は、総和計算処理部１４５による処理の流れの一例を説明する。
【００７６】
総和計算処理部１４５は、初期化の処理として、出力値Ｑに０を設定する（Ｓ７０１）。
【００７７】
総和計算処理部１４５は、図３の工程Ｓ３０５で求めたｍを変数ｚに設定し、変数ｗにλ（１）を設定する（Ｓ７０２）。
【００７８】
総和計算処理部１４５はｚが０より小さい値か否かを判断する（Ｓ７０３）。総和計算処理部１４５は、ｚが０より小さい値でないと判断した場合（Ｓ７０３にてＹＥＳ）は工程Ｓ７０４の処理に進み、ｚが０より小さい値であると判断した場合（Ｓ７０３にてＮＯ）は工程Ｓ７０７の処理に進む。
【００７９】
総和計算処理部１４５は、ｚが０より小さい値でないと判断した場合、Ｑに事前計算部１４２による処理で求められてある楕円曲線スカラー倍演算をインデックス変換処理部１４４で演算した配列ｉｎｄｅｘに格納されてある値に基づいて加算していく（Ｓ７０４）。
【００８０】
次に、総和計算処理部１４５は、ｗにインデックス変換処理部１４４で演算した配列ｌｉｎｋの値を設定し（Ｓ７０５）、ｚにｚから１減算した値を設定して（Ｓ７０６）、工程Ｓ７０３の処理に戻る。
【００８１】
総和計算処理部１４５は、ｚが０より小さい値であると判断した場合、Ｑを出力して（Ｓ７０７）処理を終了する。
【００８２】
上述の方法で楕円曲線加算の演算は、上述の工程Ｓ６０６の処理でｎ−２回と工程Ｓ７０４の処理で［（ｎ＋１）／２］−１回の合計ｎ＋［（ｎ＋１）／２］−３回行われる。
【００８３】
ｎは、楕円曲線の位数ｒに応じて一定となるため、楕円曲線加算の演算の回数を一定にすることができる。
【００８４】
また、楕円曲線のスカラー倍の演算を、楕円曲線の加算の演算を繰り返すことで、楕円曲線２倍算の演算を工程Ｓ６０２の処理を１回行うことで実現できる。この１回の楕円曲線２倍算の演算以外は、群演算の種類が一種類で済むため、群演算の演算の結果を記憶する順序、及び群演算の演算の順序をランダムに変えることで、サイドチャネル攻撃に対する耐性を持たせることやプログラムの解読を難しくすることができる。
【００８５】
群演算の演算の結果を配列に記憶するアドレスの順、または配列から群演算の演算の結果を読み出すアドレスの順の少なくとも一方をランダムにすることで、加算の演算順序をランダムにすることが実現できる。
【００８６】
＜ハードウェア構成＞
次に、上述した演算装置１０００の制御部１１、指数分解部１２、計算結果記憶部１３、及びべき乗演算部１４の機能を実現できるハードウェア構成の一例について説明するブロック図である。
【００８７】
図８は、本発明の一実施形態における演算装置のハードウェア構成図の一例である。図８に示す演算装置は、コンピュータの一例である情報処理装置により形成されている。情報処理装置は、出力装置１、入力装置２、プロセッサの一例であるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３、及び記憶手段の一例であるメモリ４がバス５により接続された構成である。
【００８８】
出力装置１は、演算結果などを表示するディスプレイなど形成可能である。
【００８９】
入力装置２は、演算に必要な値、コマンドなどを入力するキーボードなどで形成可能である。
【００９０】
ＣＰＵ３は、バス５を介して出力装置１、入力装置２、メモリ４と入出力を行う。
【００９１】
メモリ４は、ＣＰＵ３が実行するプログラム、ＣＰＵ３が実行する演算などの中間結果を含む各種データ、各種パラメータなどを記憶する。メモリ４は、コンピュータが読取可能な記憶媒体によっても形成可能である。プログラムは、情報処理装置を演算装置１０００として機能させるものであっても、べき乗演算部１４として機能させるものであってもよい。
【００９２】
図８に示す例では、情報処理装置の構成要素がバス５で接続された構成であるが、構成要素の構成がバスで接続された構成に限定されるものではない。
【００９３】
なお、情報処理装置に代えて、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）ボードなどを用いて、演算装置をファームウェアで実現してもよい。
【００９４】
また、上述のプログラムによる実行に代えて、同様の処理を実行できる回路を、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）またはＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）に実装して実現してもよい。
【００９５】
以上、本発明の好ましい実施例について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形、変更が可能である。
【符号の説明】
【００９６】
１  出力装置
２  入力装置
３  ＣＰＵ
４  メモリ
５  バス
１１  制御部
１２  指数分解部
１３  計算結果記憶部
１４  べき乗演算部
１４１  初期化処理部
１４２  事前計算部
１４３  楕円曲線加算処理部
１４４  インデックス変換処理部
１４５  総和計算処理部
１４６  楕円曲線２倍算処理部
１４７  インデックス記憶部
１４８  事前計算結果記憶部
１４９  べき乗演算制御部
１０００  演算装置
【図１】
2014235384.tif 000005
【図２】
2014235384.tif 000006
【図３】
2014235384.tif 000007
【図４】
2014235384.tif 000008
【図５】
2014235384.tif 000009
【図６】
2014235384.tif 000010
【図７】
2014235384.tif 000011
【図８】
2014235384.tif 000012