耐タンパーベキ乗演算方法
【課題】Brickellらのベキ乗演算方法にサイドチャネル解析への耐性を持たせた耐タンパーベキ乗演算方法を提供する
【解決手段】 サイドチャネル解析に耐性を持つベキ乗演算方法を提供する。暗号アルゴリズムでよく用いられるベキ乗演算は、サイドチャネル解析の対象となることが多く、それに対する耐性を持っていることが求められる。本発明では、演算に先立ってベキ指数部分を並べ替えて、ベキ乗演算時に演算列が一定になるようにする方法である。これにより、消費電力波形や処理時間から秘密情報であるベキ指数が推測されることを防ぐことができる。
【解決手段】 サイドチャネル解析に耐性を持つベキ乗演算方法を提供する。暗号アルゴリズムでよく用いられるベキ乗演算は、サイドチャネル解析の対象となることが多く、それに対する耐性を持っていることが求められる。本発明では、演算に先立ってベキ指数部分を並べ替えて、ベキ乗演算時に演算列が一定になるようにする方法である。これにより、消費電力波形や処理時間から秘密情報であるベキ指数が推測されることを防ぐことができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サイドチャネル解析による暗号プロセッサ内部における秘密情報の解析に耐性を有する耐タンパーベキ乗演算方法に関する。
【背景技術】
【０００２】
近年のコンピュータネットワークの発達に伴い、オンラインショッピング等、金銭授受を伴うサービスが拡大されてきている。その一方で、電子化された情報の盗聴や改竄によるいわゆるネットワーク犯罪の増加や、情報の流出などが大きな社会問題となっている。
【０００３】
これらの問題に対して、その解決に暗号技術が大きな役割を果たしている。情報の暗号化やディジタル署名技術を利用した認証システムなどがその例としてあげられ、さまざまな場面に導入されている。このように暗号技術は今日のネットワーク社会に必要不可欠な技術となっている。
【０００４】
しかしながら、暗号技術に対する攻撃（解読）手法も高度化してきている。その中でも、暗号の処理を実行するプロセッサ（以下、「暗号プロセッサ」ということもある）の処理時間や消費電力を測定し、それらの特徴から暗号プロセッサ内部の秘密情報を解析するというサイドチャネル解析が現実的な脅威となってきている。サイドチャネル解析として代表的なものは、タイミング解析、電力解析が知られている。
【０００５】
RSA方式についてサイドチャネル解析の例を挙げる。RSA方式は、現在最も広く使われている公開鍵暗号方式である。RSA方式の暗号化、ディジタル署名検証処理は、ベキ乗剰余算ME mod N（MのE乗をNで割った余り）を計算する。ここでMは対象のメッセージ、E、Nは公開鍵である。また、RSA方式の復号、ディジタル署名生成処理は、同じくベキ乗剰余算CD mod Nを計算する。ここでCは対象のメッセージ、Nは公開鍵、Dは秘密鍵である。
【０００６】
ベキ乗剰余算をバイナリ法で実装する場合、秘密鍵Dを二進数で表現したときの各ビットの値が0であるか1であるかによって、ベキ乗剰余算全体の演算列が異なるという性質がある。このような演算列の違いをベキ乗剰余算の処理時間から判断しようとする手法が非特許文献１に紹介されている。
【０００７】
一方、消費電力から判断しようとする手法が非特許文献２にて紹介されている。演算列の違いを判別できれば、Dの各ビットが0であるか1であるか判別でき、したがって秘密鍵Dのすべてのビットを決定できる。
【０００８】
また楕円曲線暗号の一種である、ECDSA方式についてのサイドチャネル解析についても例を挙げる。ECDSA方式は、楕円曲線上の点の演算および整数の演算から構成される。ECDSA方式のディジタル署名処理は、
kPのx座標をzで割った余りrを求め、
s = k - 1(M + xr) mod z
により、署名(r, s)を作成する。ここでPは楕円曲線上の点、zは楕円曲線上の点の位数、kはz未満の整数から選んだ乱数、Mは対象のメッセージ、xは署名者の秘密鍵である。攻撃者にとってxとk以外は既知情報であるため、もしkが分かれば秘密鍵xをsの式から求めることができる。
【０００９】
点Pをk回加える演算kPはベキ乗演算であり、通常スカラー倍算と呼ばれる。スカラー倍算をバイナリ法で実装する場合、RSA方式でのベキ乗剰余算と同様にkの値を推測することができる。
【００１０】
これらの攻撃を防ぐ方法も様々な技術が考案されている。その根底にあるアイディアは、演算処理列を秘密情報によらず一定にすることと、入力データに乱数を作用させて、暗号プロセッサの暗号処理中のデータをランダム化することの2種類に大別できる。
【００１１】
前者により、例えばRSA方式に対する攻撃手法で述べた、秘密鍵Dの各ビットの値が0であっても1であっても同じ演算列となるため、Dの値を判別できなくなる。このような方法は非特許文献３にて紹介されている。
【００１２】
後者は暗号プロセッサの処理時間や消費電力の特徴と暗号プロセッサ内部の秘密情報を無関係にすることで、サイドチャネル解析を防ぐ手法である。効率のよいベキ乗演算方法として、非特許文献４が知られている。この手法は次のようなものである。
【００１３】
楕円曲線上の点Pのスカラー倍算kPを考える。ここではkは160ビットとし、それを4ビットずつ40個のブロックに分けたものをMSB側から順にk39, k38, …, k1, k0とする。またi = 0, 1, 2, …, 39に対してTBL[i] = 216×iPを計算した40点の事前計算テーブルを保持しているものとする。
【非特許文献１】J. F. Dhem et al., A Practical Implementation of the Timing Attack（Proceedings of CARDIS ’98, Lecture Notes in Computer Science 1820, pp.167-182, Springer-Verlag, 1998）
【非特許文献２】T. S. Messerges et al., Investigation of Power Analysis Attacks on Smartcards（Proceedings of USENIX Workshop on Smartcard Technology ‘99）
【非特許文献３】J. S. Coron，Resistance Against Differential Power Analysis for Elliptic Curve Cryptosystems (Proceedings of Cryptographic Hardware and Embedded Systems ’99, Lecture Notes in Computer Science 1717, pp.292-302, Springer-Verlat, 1999)
【非特許文献４】E. F. Brickell et al., Fast Exponentiation with Precomputation (Proceedings of EUROCRYPT ’92, Lecture Notes in Computer Science 658, pp.200-207, Springer-Verlag, 1993)
【発明の開示】
【発明が解決しようとする課題】
【００１４】
このようなアイディアに基づく防御手法は、ベキ乗演算の様々なアルゴリズムに対してそれぞれ提案されている。しかし防御手法を施すことで、処理時間が増加したり、必要なメモリが増加したりすることを避けることはできないのが現状である。このことがサイドチャネル解析への防御手法全般の問題点となっている。
【００１５】
そこでなるべく効率のよいベキ乗演算方法について、そのサイドチャネル解析への防御手法を考案すれば、処理時間が増加してもその暗号プロセッサを利用する上で定められる許容時間内に処理できることが期待される。
【００１６】
上記非特許文献４で示したBrickellらのスカラー倍算方法を図9にフローチャートとして示す。まずステップ901、902で、途中結果を格納する領域A, Bをそれぞれ楕円曲線上の無限遠点と呼ばれる仮想的な点Oと初期化する。ステップ903から909はdを15から1まで1ずつ減じるループ処理である。ステップ904から907はiを39から0まで1ずつ減じるループ処理である。ステップ905でki = dかどうかの検査を行う。成立するときはBとTBL[i]を加算してBに格納する楕円曲線上の点の加算処理を行う（ステップ906）。成立しないときは何もしない、すなわちステップ906は行わずにステップ907に進む。ステップ907でiループが終了したとき、ステップ908に進む。ステップ908ではAとBを加算してAに格納する。ステップ909が終了したとき、A = kPとなってスカラー倍算が計算される。この計算では最大55回の楕円曲線上の点の加算でスカラー倍算を実行できる。
【００１７】
しかしこの手法はサイドチャネル解析に対して脆弱であるという問題がある。なぜならB ← B + TBL[i]の演算の前にki = dであるかの検査のループ回数はkに依存して決まり、それは暗号プロセッサの処理列の違いを発生する。したがって該ループ回数をサイドチャネル解析により判別できれば、各kiの値を決定できるため、kの値が露呈するからである。
【００１８】
本発明は、上記Brickellらのベキ乗演算方法にサイドチャネル解析への耐性を持たせた耐タンパーベキ乗演算方法を提供することを目的とする。
【課題を解決するための手段】
【００１９】
請求項1に対応する発明は、情報処理装置を利用して暗号処理中に出現するベキ乗剰余算c = mk mod Nを計算する方法であって、前記nビットの整数データkをLSB（Least Significant Bit、最下位ビット）から順にwビットずつのs個のブロック（sはn/w以上の最小の整数）に分ける手段と、前記データkのMSB（Most Significant Bit、最上位ビット）を含むブロックがwビットに満たない場合にMSB側に0をパディングして前記ブロックをwビットにする手段と、前記ブロックに分けられたデータkをks-1, ks-2, …, k1, k0としたとき、各ブロックをwビットの整数と見て大きい順に並び替えた場合に、対応する添え字をその順序で格納する手段と、前記添え字を格納する際に、前記kをwビットのブロックで大きい順に並び替えたときに大きさが変わる箇所に相当する添え字に印を付加する手段と、i = 1, 2, …, sに対しs個のデータTBL[i] = mw i mod Nからなる事前計算テーブルTBLを保持する手段と、2つの中間変数A, Bを1に初期化する手段と、ループカウンタdをs-1に初期化する手段と、前記格納された添え字を順番に参照し、添え字に印がない場合はB×TBL[d] mod Nを計算してBに格納し、添え字に印がある場合はB×A mod Nを計算してAに格納してdから1減じる手段と、を有することを特徴とする耐タンパーベキ乗演算方法である。
【００２０】
請求項2に対応する発明は、前記2つの中間変数A, BをそれぞれTBL[s], TBL[s+1]またはTBL[s+1], TBL[s]とすることを特徴とする請求項1記載の耐タンパーベキ乗演算方法である。
【００２１】
請求項3に対応する発明は、情報処理装置を利用して暗号処理中に出現する楕円曲線上の点のスカラー倍算Q = kPを計算する方法であって、前記nビットの整数データkをLSB（Least Significant Bit、最下位ビット）から順にwビットずつのs個のブロック（sはn/w以上の最小の整数）に分ける手段と、前記データkのMSB（Most Significant Bit、最上位ビット）を含むブロックがwビットに満たない場合にMSB側に0をパディングして前記ブロックをwビットにする手段と、前記ブロックに分けられたデータkをks-1, ks-2, …, k1, k0としたとき、各ブロックをwビットの整数と見て大きい順に並び替えた場合に、対応する添え字をその順序で格納する手段と、前記添え字を格納する際に、前記kをwビットのブロックで大きい順に並び替えたときに大きさが変わる箇所に相当する添え字に印を付加する手段と、i = 1, 2, …, sに対しs個のデータTBL[i] = wi Pからなる事前計算テーブルTBLを保持する手段と、2つの中間変数A, Bを1に初期化する手段と、ループカウンタdをs-1に初期化する手段と、前記格納された添え字を順番に参照し、添え字に印がない場合はB×TBL[d] mod Nを計算してBに格納し、添え字に印がある場合はB×A mod Nを計算してAに格納してdから1減じる手段と、を有することを特徴とする耐タンパーベキ乗演算方法である。
【００２２】
請求項4に対応する発明は、前記2つの中間変数A, BをそれぞれTBL[s], TBL[s+1]またはTBL[s+1], TBL[s]とすることを特徴とする請求項3記載の耐タンパーベキ乗演算方法である。
【００２３】
（作用）
請求項1に対応する発明は、以上のような手段を講じたことにより、Brickellらの方法でベキ乗剰余算を行う際に、kのブロックの値を先に整列しておくことで、剰余乗算を行う演算列を一定にすることができる。したがって演算の消費電力波形または処理時間からkの解析を困難にすることができる。
【００２４】
請求項2に対応する発明は、請求項1に対応する発明において、中間変数A, Bの格納位置を事前計算テーブルと同じ位置にすることにより、B ← B + TBL[i]およびA ← A + Bの演算を、入出力ともにTBLとできるため、より消費電力波形または処理時間からkの解析を困難にすることができる。
【００２５】
請求項3に対応する発明は、以上のような手段を講じたことにより、Brickellらの方法で楕円曲線上の点のスカラー倍算を行う際に、kのブロックの値を先に整列しておくことで、楕円曲線上の点の加算を行う演算列を一定にすることができる。したがって演算の消費電力波形または処理時間からkの解析を困難にすることができる。
【００２６】
請求項4に対応する発明は、請求項3に対応する発明において、中間変数A, Bの格納位置を事前計算テーブルと同じ位置にすることにより、B ← B + TBL[i]およびA ← A + Bの演算を、入出力ともにTBLとできるため、より消費電力波形または処理時間からkの解析を困難にすることができる。
【発明の効果】
【００２７】
以上説明したように本発明によれば、Brickellらの方法でベキ乗演算を行うときに、そのベキ指数を、電力解析またはタイミング解析による解析から困難にする耐タンパーベキ乗演算方法を提供できる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の各実施形態について図面を参照しながら説明する。
【００２９】
（第1の実施形態）
図1は本発明の第1の実施形態に係わる耐タンパーベキ乗剰余算方法を実施する装置の構成を示す模式図である。この耐タンパーベキ乗剰余算装置101は、ICカードなどの計算機のベキ乗剰余算演算部として構成されていて、ハードウェアまたはソフトウェアによってベキ乗剰余算を行うものである。具体的には制御部102、ROM（リードオンリーメモリ）103、RAM（ランダムアクセスメモリ）104、事前計算テーブル105、剰余乗算ユニット106からなる。
【００３０】
ROM103はベキ乗剰余算を行う際に必要なパラメータを格納している。例えばm, Nが固定値であるときは、m, Nである。またソフトウェアで実現されるときは、Brickellらの方法でベキ乗剰余算を行うプログラムを格納していることもある。RAM104はベキ乗剰余算の途中結果などの一時的なデータを格納する。事前計算テーブル105は、TBL[i] = mw i mod NからなるTBL[]を格納している。事前計算テーブル105はROM102に含まれていてもよい。剰余乗算ユニット106は、ROM103またはRAM104または事前計算テーブル105から制御部102の制御のもとに入力値x, yを受け、剰余乗算z = a×b mod Nを行って結果zをRAM104に返す。
【００３１】
図2、図3は本発明の第1の実施形態に関わる耐タンパーベキ乗剰余算方法を実現するフローチャートである。このフローチャートは図1に示す耐タンパーベキ乗剰余算装置で実行されるものとしてここでは説明するが、それに限定されるものではない。
【００３２】
図2、図3では、今日のベキ乗剰余算を利用した暗号方式の法は一般に1024ビットが使われていることから、nを1024ビット、wを8ビット、sをs = n/w = 128とした場合を示しているが、もちろん一般化することも容易である。
【００３３】
図2、図3を用いて、本発明の第1の実施形態を説明する。
【００３４】
まずkは8ビットずつ128ブロックに分けられているものとし、それをMSB側からk127, k126, …, k1, k0とする。これは図2には図示されていないが、ステップ201より前もしくはステップ201で行われるステップである。またnが1024ビットの場合を考えているので、MSBを含むブロックに0をパディングする必要がないが、必要に応じてここでkのMSB側に0をパディングしてブロックをwビットにしておく。
【００３５】
ステップ201では、k127, …, k0を大きい順に並べ替え、それに対応する添え字を領域Fに格納する。ステップ201を詳細に記述したフローチャートが図3である。ここでステップ201に対応する図3を説明する。
【００３６】
ステップ301において、添え字を格納する領域Fを0に初期化する。ステップ302から309はdを255（= 2w - 1）からd = 0まで1ずつ減じていくループ処理である。ステップ303から306はiを127（= s - 1）からi = 0まで１ずつ減じていくループ処理である。なおここはiを0から127まで1ずつ増加させていってもよい。ステップ304において、ki = dであるかを検査する。成立するときは添え字を格納する領域Fに1バイトのデータとしてiを連結する（ステップ305）。成立しないときは何もしない、すなわちステップ305を飛ばしてステップ306に進む。ステップ306のiループが終了したのちはステップ307に進み、i > 0か検査する。成立するときは領域Fに、dの値が変化する印をつける。ここでは0x80（10進数では128）という1バイトをその印としている（ステップ308）。成立しないときは何もしない、すなわちステップ308を飛ばしてステップ309に進む。ステップ309のdループが終了したとき、このフローチャートは終了する。
【００３７】
そこで図2のフローチャートに戻る。ステップ202、203で中間結果A、Bをそれぞれ1と設定する。ステップ204から208はiを0から382（= (2w - 1) + s - 1）まで1ずつ増加させていくループ処理である。ステップ205においてFのi番目の要素F[i]が0x80であるか検査する。成立する場合はB×A mod Nを実行してAに格納し（ステップ206）、ステップ208に進む。成立しない場合はB×TBL[F[i]] mod Nを実行してBに格納する（ステップ207）。ステップ208で終了したときに、Aにmk mod Nが格納されている。なぜならば、本実施例では、Brickellらの方法において、ki = dかの判定を処理の先頭で行っているのみで、剰余乗算の実行順序はBrickellらの方法と同じだからである。また、Brickellらの方法ではdのループはd = 0で行っていないが、本実施例（図3）ではd = 0の場合も行っている。しかしステップ307でi = 0の場合はFに0x80を連結していないため、d = 0に対応する図2での演算は、ステップ207が行われるのみで、ステップ206は行われない。したがってd = 0に対応する演算は、最終結果Aに影響を与えないため、Brickellらの方法と同じ最終結果を得ることができる。
【００３８】
このように本発明によれば、ステップ204から208までのループ内で、各ループごとに1回の剰余乗算のみが実行されるため、消費電力波形や処理時間からkの値を推測されるのを困難にすることができる。
【００３９】
また、ステップ201とステップ202は連続して実行される必要はなく、ステップ201を実行してFを格納したのち、別の処理をしてからステップ202以下を実行するようにすることもできる。このようにすると、ステップ201（図3）の処理とステップ202以下の処理の関連をさらに解析しにくくできる。
【００４０】
（第2の実施形態）
第2の実施形態は、第1の実施形態において、途中結果を格納するA, Bを事前計算テーブルTBLと同じ配列に格納することで、より解析を困難にするものである。
【００４１】
図4は本発明の第2の実施形態に関わる耐タンパーベキ乗剰余算方法を実現するフローチャートである。このフローチャートは図1に示す耐タンパーベキ乗剰余算装置で実行されるものとしてここでは説明するが、それに限定されるものではない。
【００４２】
また第2の実施形態では、事前計算テーブル105は書き込みができる必要がある。そのため、計算に先立ってRAM104に格納されているものとする。
【００４３】
図4では、今日のベキ乗剰余算を利用した暗号方式の法は一般に1024ビットが使われていることから、nを1024ビット、wを8ビット、sをs = n/w = 128とした場合を示しているが、もちろん一般化することも容易である。
【００４４】
図4、図2を用いて、本発明の第2の実施形態を説明する。
【００４５】
まずkは8ビットずつ128ブロックに分けられているものとし、それをMSB側からk127, k126, …, k1, k0とする。これは図4には図示されていないが、ステップ401より前もしくはステップ401で行われるステップである。またnが1024ビットの場合を考えているので、MSBを含むブロックに0をパディングする必要がないが、必要に応じてここでkのMSB側に0をパディングしてブロックをwビットにしておく。
【００４６】
ステップ401では、k127, …, k0を大きい順に並べ替え、それに対応する添え字を領域Fに格納する。ステップ401を詳細に記述したフローチャートは第1の実施例同様に図3であり、その流れは第1の実施例で説明した通りである。ステップ402、403で中間結果を格納する領域として事前計算テーブルからTBL[128], TBL[129]を選び、それぞれを1と設定する。ステップ404から406はiを0から382（= (2w - 1) + s - 1）まで1ずつ増加させていくループ処理である。ステップ405においてTBL[129-(F[i]>>7)] ← TBL[129]×TBL[F[i]] mod Nを実行する。この演算では、F[i] = 0x80の場合はTBL[128] ← TBL[129]×TBL[128] mod Nであり、A = TBL[128], B = TBL[129]とした場合の図2におけるステップ206に対応する。F[i]が0x80未満の場合はTBL[129] ← TBL[129]×TBL[F[i]] mod Nであり、B = TBL[129]とした場合の図2におけるステップ207に対応する。したがって図4のフローチャートは図2と同じ演算の流れとなっており、終了したときには、TBL[128]にmk mod Nが格納されている。
【００４７】
このように本発明によれば、ステップ404から406までのループ内で、分岐することなく一定の演算列でベキ乗剰余算が計算されていくため、消費電力波形や処理時間からkの値を推測されるのを困難にすることができる。
【００４８】
また、ステップ401とステップ402は連続して実行される必要はなく、ステップ401を実行してFを格納したのち、別の処理をしてからステップ402以下を実行することで、ステップ401（図3）の処理とステップ402以下の処理の関連をさらに解析しにくくできることは、第1の実施例と同様である。
【００４９】
（第3の実施形態）
図5は本発明の第3の実施形態に係わる耐タンパーベキ乗剰余算方法を実施する装置の構成を示す模式図である。この耐タンパーベキ乗剰余算装置501は、ICカードなどの計算機のベキ乗剰余算演算部として構成されていて、ハードウェアまたはソフトウェアによってベキ乗剰余算を行うものである。具体的には制御部502、ROM（リードオンリーメモリ）503、RAM（ランダムアクセスメモリ）504、事前計算テーブル505、楕円曲線上の点の加算ユニット506からなる。
【００５０】
ROM503はベキ乗剰余算を行う際に必要なパラメータを格納している。例えば楕円曲線のパラメータである。またソフトウェアで実現されるときは、Brickellらの方法で楕円曲線上の点のスカラー倍算を行うプログラムを格納していることもある。RAM504はベキ乗剰余算の途中結果などの一時的なデータを格納する。事前計算テーブル505は、TBL[i] = wiPからなるTBL[]を格納している。事前計算テーブル505はROM502に含まれていてもよい。楕円曲線上の点の加算ユニット506は、ROM503またはRAM504または事前計算テーブル505から制御部502の制御のもとに入力値x, yを受け、楕円曲線上の点の加算z = a + b を行って結果zをRAM504に返す。
【００５１】
図6、図7は本発明の第3の実施形態に関わる耐タンパーベキ乗演算（楕円曲線上のスカラー倍算）方法を実現するフローチャートである。このフローチャートは図5に示す耐タンパーベキ乗剰余算装置で実行されるものとしてここでは説明するが、それに限定されるものではない。
【００５２】
図6、図7では、今日の楕円曲線暗号方式の鍵長は一般に160ビットが使われていることから、nを160ビット、wを4ビット、sをs = n/w = 40とした場合を示しているが、もちろん一般化することも容易である。
【００５３】
図6、図7を用いて、本発明の第1の実施形態を説明する。
【００５４】
まずkは4ビットずつ40ブロックに分けられているものとし、それをMSB側からk39, k38, …, k1, k0とする。これは図6には図示されていないが、ステップ601より前もしくはステップ601で行われるステップである。またnが160ビットの場合を考えているので、MSBを含むブロックに0をパディングする必要がないが、必要に応じてここでkのMSB側に0をパディングしてブロックをwビットにしておく。
【００５５】
ステップ601では、k39, …, k0を大きい順に並べ替え、それに対応する添え字を領域Fに格納する。ステップ601を詳細に記述したフローチャートが図7である。ここでステップ601に対応する図7を説明する。
【００５６】
ステップ701において、添え字を格納する領域Fを0に初期化する。ステップ702から709はdを15（= 2w - 1）からd = 0まで1ずつ減じていくループ処理である。ステップ703から706はiを39（= s - 1）からi = 0まで１ずつ減じていくループ処理である。なおここはiを0から39まで1ずつ増加させていってもよい。ステップ704において、ki = dであるかを検査する。成立するときは添え字を格納する領域Fに1バイトのデータとしてiを連結する（ステップ705）。成立しないときは何もしない、すなわちステップ705を飛ばしてステップ706に進む。ステップ706のiループが終了したのちはステップ707に進み、i > 0か検査する。成立するときは領域Fに、dの値が変化する印をつける。ここでは0x80（10進数では128）という1バイトをその印としている（ステップ708）。成立しないときは何もしない、すなわちステップ708を飛ばしてステップ709に進む。ステップ709のdループが終了したとき、このフローチャートは終了する。
【００５７】
そこで図6のフローチャートに戻る。ステップ602、603で中間結果A、Bをそれぞれ楕円曲線上の無限遠点Oと設定する。ステップ604から608はiを0から54（= (2w - 1) + s - 1）まで1ずつ増加させていくループ処理である。ステップ605においてFのi番目の要素F[i]が0x80であるか検査する。成立する場合はB + Aを実行してAに格納し（ステップ606）、ステップ608に進む。成立しない場合はB + TBL[F[i]]を実行してBに格納する（ステップ607）。ステップ608で終了したときに、AにkPが格納されている。なぜならば、本実施例では、Brickellらの方法において、ki = dかの判定を処理の先頭で行っているのみで、剰余乗算の実行順序はBrickellらの方法と同じだからである。また、Brickellらの方法ではdのループはd = 0で行っていないが、本実施例（図7）ではd = 0の場合も行っている。しかしステップ707でi = 0の場合はFに0x80を連結していないため、d = 0に対応する図6での演算は、ステップ607が行われるのみで、ステップ606は行われない。したがってd = 0に対応する演算は、最終結果Aに影響を与えないため、Brickellらの方法と同じ最終結果を得ることができる。
【００５８】
このように本発明によれば、ステップ604から608までのループ内で、各ループごとに1回の楕円曲線上の点の加算のみが実行されるため、消費電力波形や処理時間からkの値を推測されるのを困難にすることができる。
【００５９】
また、ステップ601とステップ602は連続して実行される必要はなく、ステップ601を実行してFを格納したのち、別の処理をしてからステップ602以下を実行するようにすることもできる。このようにすると、ステップ601（図7）の処理とステップ602以下の処理の関連をさらに解析しにくくできる。
【００６０】
（第4の実施形態）
第4の実施形態は、第3の実施形態において、途中結果を格納するA, Bを事前計算テーブルTBLと同じ配列に格納することで、より解析を困難にするものである。
【００６１】
図8は本発明の第3の実施形態に関わる耐タンパーベキ乗剰余算方法を実現するフローチャートである。このフローチャートは図5に示す耐タンパーベキ乗剰余算装置で実行されるものとしてここでは説明するが、それに限定されるものではない。
【００６２】
また第4の実施形態では、事前計算テーブル505は書き込みができる必要がある。そのため、計算に先立ってRAM504に格納されているものとする。
【００６３】
図8では、今日の楕円曲線暗号方式の鍵長は一般に160ビットが使われていることから、nを160ビット、wを4ビット、sをs = n/w = 40とした場合を示しているが、もちろん一般化することも容易である。
【００６４】
図8、図6を用いて、本発明の第4の実施形態を説明する。
【００６５】
まずkは4ビットずつ40ブロックに分けられているものとし、それをMSB側からk39, k38, …, k1, k0とする。これは図8には図示されていないが、ステップ801より前もしくはステップ801で行われるステップである。またnが160ビットの場合を考えているので、MSBを含むブロックに0をパディングする必要がないが、必要に応じてここでkのMSB側に0をパディングしてブロックをwビットにしておく。
【００６６】
ステップ801では、k39, …, k0を大きい順に並べ替え、それに対応する添え字を領域Fに格納する。ステップ801を詳細に記述したフローチャートは第3の実施例同様に図7であり、その流れは第3の実施例で説明した通りである。ステップ802、803で中間結果を格納する領域として事前計算テーブルからTBL[40], TBL[41]を選び、それぞれを楕円曲線上の無限遠点Oと設定する。ステップ804から806はiを0から54（= (2w - 1) + s - 1）まで1ずつ増加させていくループ処理である。ステップ805においてTBL[41-(F[i]>>7)] ← TBL[41] + TBL[F[i]]を実行する。この演算では、F[i] = 0x80の場合はTBL[41] ← TBL[41] + TBL[40]であり、A = TBL[40], B = TBL[41]とした場合の図6におけるステップ606に対応する。F[i]が0x80未満の場合はTBL[41] ← TBL[41] + TBL[F[i]]であり、B = TBL[41]とした場合の図6におけるステップ607に対応する。したがって図8のフローチャートは図6と同じ演算の流れとなっており、終了したときには、TBL[40]にkPが格納されている。
【００６７】
このように本発明によれば、ステップ804から806までのループ内で、分岐することなく一定の演算列で楕円曲線上の点の加算が計算されていくため、消費電力波形や処理時間からkの値を推測されるのを困難にすることができる。
【００６８】
また、ステップ801とステップ802は連続して実行される必要はなく、ステップ801を実行してFを格納したのち、別の処理をしてからステップ802以下を実行することで、ステップ801（図7）の処理とステップ802以下の処理の関連をさらに解析しにくくできることは、第3の実施例と同様である。
【図面の簡単な説明】
【００６９】
【図１】本発明の第1、第2の実施形態に係る耐タンパーベキ乗剰余算装置
【図２】本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法
【図３】本発明の第1、第2の実施形態に係るkの符号化方法
【図４】本発明の第2の実施形態に係る耐タンパーベキ乗剰余算方法
【図５】本発明の第3、第4の実施形態に係る耐タンパースカラー倍算装置
【図６】本発明の第3の実施形態に係る耐タンパースカラー倍算方法
【図７】本発明の第3、第4の実施形態に係るkの符号化方法
【図８】本発明の第3の実施形態に係る耐タンパースカラー倍算方法
【図９】Brickellらによるベキ乗演算方法
【符号の説明】
【００７０】
101…耐タンパーベキ乗剰余算装置
102…制御部
103…ROM
104…ランダムアクセスメモリ
105…事前計算テーブル
106…剰余乗算ユニット
201…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第1ステップ
202…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第2ステップ
203…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第3ステップ
204…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第4ステップ
205…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第5ステップ
206…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第6ステップ
207…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第7ステップ
208…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第8ステップ
301…本発明の第1、2の実施形態に係るkの符号化方法の第1ステップ
302…本発明の第1、2の実施形態に係るkの符号化方法の第2ステップ
303…本発明の第1、2の実施形態に係るkの符号化方法の第3ステップ
304…本発明の第1、2の実施形態に係るkの符号化方法の第4ステップ
305…本発明の第1、2の実施形態に係るkの符号化方法の第5ステップ
306…本発明の第1、2の実施形態に係るkの符号化方法の第6ステップ
307…本発明の第1、2の実施形態に係るkの符号化方法の第7ステップ
308…本発明の第1、2の実施形態に係るkの符号化方法の第8ステップ
309…本発明の第1、2の実施形態に係るkの符号化方法の第9ステップ
401…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第1ステップ
402…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第2ステップ
403…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第3ステップ
404…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第4ステップ
405…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第5ステップ
406…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第6ステップ
501…耐タンパースカラー倍算装置
502…制御部
503…ROM
504…ランダムアクセスメモリ
505…事前計算テーブル
506…楕円曲線上の点の加算ユニット
601…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第1ステップ
602…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第2ステップ
603…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第3ステップ
604…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第4ステップ
605…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第5ステップ
606…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第6ステップ
607…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第7ステップ
608…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第8ステップ
701…本発明の第3、4の実施形態に係るkの符号化方法の第1ステップ
702…本発明の第3、4の実施形態に係るkの符号化方法の第2ステップ
703…本発明の第3、4の実施形態に係るkの符号化方法の第3ステップ
704…本発明の第3、4の実施形態に係るkの符号化方法の第4ステップ
705…本発明の第3、4の実施形態に係るkの符号化方法の第5ステップ
706…本発明の第3、4の実施形態に係るkの符号化方法の第6ステップ
707…本発明の第3、4の実施形態に係るkの符号化方法の第7ステップ
708…本発明の第3、4の実施形態に係るkの符号化方法の第8ステップ
709…本発明の第3、4の実施形態に係るkの符号化方法の第9ステップ
801…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第1ステップ
802…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第2ステップ
803…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第3ステップ
804…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第4ステップ
805…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第5ステップ
806…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第6ステップ
901…Brickellらによるベキ乗演算方法の第1ステップ
902…Brickellらによるベキ乗演算方法の第2ステップ
903…Brickellらによるベキ乗演算方法の第3ステップ
904…Brickellらによるベキ乗演算方法の第4ステップ
905…Brickellらによるベキ乗演算方法の第5ステップ
906…Brickellらによるベキ乗演算方法の第6ステップ
907…Brickellらによるベキ乗演算方法の第7ステップ
908…Brickellらによるベキ乗演算方法の第8ステップ
909…Brickellらによるベキ乗演算方法の第9ステップ
【技術分野】
【０００１】
本発明は、サイドチャネル解析による暗号プロセッサ内部における秘密情報の解析に耐性を有する耐タンパーベキ乗演算方法に関する。
【背景技術】
【０００２】
近年のコンピュータネットワークの発達に伴い、オンラインショッピング等、金銭授受を伴うサービスが拡大されてきている。その一方で、電子化された情報の盗聴や改竄によるいわゆるネットワーク犯罪の増加や、情報の流出などが大きな社会問題となっている。
【０００３】
これらの問題に対して、その解決に暗号技術が大きな役割を果たしている。情報の暗号化やディジタル署名技術を利用した認証システムなどがその例としてあげられ、さまざまな場面に導入されている。このように暗号技術は今日のネットワーク社会に必要不可欠な技術となっている。
【０００４】
しかしながら、暗号技術に対する攻撃（解読）手法も高度化してきている。その中でも、暗号の処理を実行するプロセッサ（以下、「暗号プロセッサ」ということもある）の処理時間や消費電力を測定し、それらの特徴から暗号プロセッサ内部の秘密情報を解析するというサイドチャネル解析が現実的な脅威となってきている。サイドチャネル解析として代表的なものは、タイミング解析、電力解析が知られている。
【０００５】
RSA方式についてサイドチャネル解析の例を挙げる。RSA方式は、現在最も広く使われている公開鍵暗号方式である。RSA方式の暗号化、ディジタル署名検証処理は、ベキ乗剰余算ME mod N（MのE乗をNで割った余り）を計算する。ここでMは対象のメッセージ、E、Nは公開鍵である。また、RSA方式の復号、ディジタル署名生成処理は、同じくベキ乗剰余算CD mod Nを計算する。ここでCは対象のメッセージ、Nは公開鍵、Dは秘密鍵である。
【０００６】
ベキ乗剰余算をバイナリ法で実装する場合、秘密鍵Dを二進数で表現したときの各ビットの値が0であるか1であるかによって、ベキ乗剰余算全体の演算列が異なるという性質がある。このような演算列の違いをベキ乗剰余算の処理時間から判断しようとする手法が非特許文献１に紹介されている。
【０００７】
一方、消費電力から判断しようとする手法が非特許文献２にて紹介されている。演算列の違いを判別できれば、Dの各ビットが0であるか1であるか判別でき、したがって秘密鍵Dのすべてのビットを決定できる。
【０００８】
また楕円曲線暗号の一種である、ECDSA方式についてのサイドチャネル解析についても例を挙げる。ECDSA方式は、楕円曲線上の点の演算および整数の演算から構成される。ECDSA方式のディジタル署名処理は、
kPのx座標をzで割った余りrを求め、
s = k - 1(M + xr) mod z
により、署名(r, s)を作成する。ここでPは楕円曲線上の点、zは楕円曲線上の点の位数、kはz未満の整数から選んだ乱数、Mは対象のメッセージ、xは署名者の秘密鍵である。攻撃者にとってxとk以外は既知情報であるため、もしkが分かれば秘密鍵xをsの式から求めることができる。
【０００９】
点Pをk回加える演算kPはベキ乗演算であり、通常スカラー倍算と呼ばれる。スカラー倍算をバイナリ法で実装する場合、RSA方式でのベキ乗剰余算と同様にkの値を推測することができる。
【００１０】
これらの攻撃を防ぐ方法も様々な技術が考案されている。その根底にあるアイディアは、演算処理列を秘密情報によらず一定にすることと、入力データに乱数を作用させて、暗号プロセッサの暗号処理中のデータをランダム化することの2種類に大別できる。
【００１１】
前者により、例えばRSA方式に対する攻撃手法で述べた、秘密鍵Dの各ビットの値が0であっても1であっても同じ演算列となるため、Dの値を判別できなくなる。このような方法は非特許文献３にて紹介されている。
【００１２】
後者は暗号プロセッサの処理時間や消費電力の特徴と暗号プロセッサ内部の秘密情報を無関係にすることで、サイドチャネル解析を防ぐ手法である。効率のよいベキ乗演算方法として、非特許文献４が知られている。この手法は次のようなものである。
【００１３】
楕円曲線上の点Pのスカラー倍算kPを考える。ここではkは160ビットとし、それを4ビットずつ40個のブロックに分けたものをMSB側から順にk39, k38, …, k1, k0とする。またi = 0, 1, 2, …, 39に対してTBL[i] = 216×iPを計算した40点の事前計算テーブルを保持しているものとする。
【非特許文献１】J. F. Dhem et al., A Practical Implementation of the Timing Attack（Proceedings of CARDIS ’98, Lecture Notes in Computer Science 1820, pp.167-182, Springer-Verlag, 1998）
【非特許文献２】T. S. Messerges et al., Investigation of Power Analysis Attacks on Smartcards（Proceedings of USENIX Workshop on Smartcard Technology ‘99）
【非特許文献３】J. S. Coron，Resistance Against Differential Power Analysis for Elliptic Curve Cryptosystems (Proceedings of Cryptographic Hardware and Embedded Systems ’99, Lecture Notes in Computer Science 1717, pp.292-302, Springer-Verlat, 1999)
【非特許文献４】E. F. Brickell et al., Fast Exponentiation with Precomputation (Proceedings of EUROCRYPT ’92, Lecture Notes in Computer Science 658, pp.200-207, Springer-Verlag, 1993)
【発明の開示】
【発明が解決しようとする課題】
【００１４】
このようなアイディアに基づく防御手法は、ベキ乗演算の様々なアルゴリズムに対してそれぞれ提案されている。しかし防御手法を施すことで、処理時間が増加したり、必要なメモリが増加したりすることを避けることはできないのが現状である。このことがサイドチャネル解析への防御手法全般の問題点となっている。
【００１５】
そこでなるべく効率のよいベキ乗演算方法について、そのサイドチャネル解析への防御手法を考案すれば、処理時間が増加してもその暗号プロセッサを利用する上で定められる許容時間内に処理できることが期待される。
【００１６】
上記非特許文献４で示したBrickellらのスカラー倍算方法を図9にフローチャートとして示す。まずステップ901、902で、途中結果を格納する領域A, Bをそれぞれ楕円曲線上の無限遠点と呼ばれる仮想的な点Oと初期化する。ステップ903から909はdを15から1まで1ずつ減じるループ処理である。ステップ904から907はiを39から0まで1ずつ減じるループ処理である。ステップ905でki = dかどうかの検査を行う。成立するときはBとTBL[i]を加算してBに格納する楕円曲線上の点の加算処理を行う（ステップ906）。成立しないときは何もしない、すなわちステップ906は行わずにステップ907に進む。ステップ907でiループが終了したとき、ステップ908に進む。ステップ908ではAとBを加算してAに格納する。ステップ909が終了したとき、A = kPとなってスカラー倍算が計算される。この計算では最大55回の楕円曲線上の点の加算でスカラー倍算を実行できる。
【００１７】
しかしこの手法はサイドチャネル解析に対して脆弱であるという問題がある。なぜならB ← B + TBL[i]の演算の前にki = dであるかの検査のループ回数はkに依存して決まり、それは暗号プロセッサの処理列の違いを発生する。したがって該ループ回数をサイドチャネル解析により判別できれば、各kiの値を決定できるため、kの値が露呈するからである。
【００１８】
本発明は、上記Brickellらのベキ乗演算方法にサイドチャネル解析への耐性を持たせた耐タンパーベキ乗演算方法を提供することを目的とする。
【課題を解決するための手段】
【００１９】
請求項1に対応する発明は、情報処理装置を利用して暗号処理中に出現するベキ乗剰余算c = mk mod Nを計算する方法であって、前記nビットの整数データkをLSB（Least Significant Bit、最下位ビット）から順にwビットずつのs個のブロック（sはn/w以上の最小の整数）に分ける手段と、前記データkのMSB（Most Significant Bit、最上位ビット）を含むブロックがwビットに満たない場合にMSB側に0をパディングして前記ブロックをwビットにする手段と、前記ブロックに分けられたデータkをks-1, ks-2, …, k1, k0としたとき、各ブロックをwビットの整数と見て大きい順に並び替えた場合に、対応する添え字をその順序で格納する手段と、前記添え字を格納する際に、前記kをwビットのブロックで大きい順に並び替えたときに大きさが変わる箇所に相当する添え字に印を付加する手段と、i = 1, 2, …, sに対しs個のデータTBL[i] = mw i mod Nからなる事前計算テーブルTBLを保持する手段と、2つの中間変数A, Bを1に初期化する手段と、ループカウンタdをs-1に初期化する手段と、前記格納された添え字を順番に参照し、添え字に印がない場合はB×TBL[d] mod Nを計算してBに格納し、添え字に印がある場合はB×A mod Nを計算してAに格納してdから1減じる手段と、を有することを特徴とする耐タンパーベキ乗演算方法である。
【００２０】
請求項2に対応する発明は、前記2つの中間変数A, BをそれぞれTBL[s], TBL[s+1]またはTBL[s+1], TBL[s]とすることを特徴とする請求項1記載の耐タンパーベキ乗演算方法である。
【００２１】
請求項3に対応する発明は、情報処理装置を利用して暗号処理中に出現する楕円曲線上の点のスカラー倍算Q = kPを計算する方法であって、前記nビットの整数データkをLSB（Least Significant Bit、最下位ビット）から順にwビットずつのs個のブロック（sはn/w以上の最小の整数）に分ける手段と、前記データkのMSB（Most Significant Bit、最上位ビット）を含むブロックがwビットに満たない場合にMSB側に0をパディングして前記ブロックをwビットにする手段と、前記ブロックに分けられたデータkをks-1, ks-2, …, k1, k0としたとき、各ブロックをwビットの整数と見て大きい順に並び替えた場合に、対応する添え字をその順序で格納する手段と、前記添え字を格納する際に、前記kをwビットのブロックで大きい順に並び替えたときに大きさが変わる箇所に相当する添え字に印を付加する手段と、i = 1, 2, …, sに対しs個のデータTBL[i] = wi Pからなる事前計算テーブルTBLを保持する手段と、2つの中間変数A, Bを1に初期化する手段と、ループカウンタdをs-1に初期化する手段と、前記格納された添え字を順番に参照し、添え字に印がない場合はB×TBL[d] mod Nを計算してBに格納し、添え字に印がある場合はB×A mod Nを計算してAに格納してdから1減じる手段と、を有することを特徴とする耐タンパーベキ乗演算方法である。
【００２２】
請求項4に対応する発明は、前記2つの中間変数A, BをそれぞれTBL[s], TBL[s+1]またはTBL[s+1], TBL[s]とすることを特徴とする請求項3記載の耐タンパーベキ乗演算方法である。
【００２３】
（作用）
請求項1に対応する発明は、以上のような手段を講じたことにより、Brickellらの方法でベキ乗剰余算を行う際に、kのブロックの値を先に整列しておくことで、剰余乗算を行う演算列を一定にすることができる。したがって演算の消費電力波形または処理時間からkの解析を困難にすることができる。
【００２４】
請求項2に対応する発明は、請求項1に対応する発明において、中間変数A, Bの格納位置を事前計算テーブルと同じ位置にすることにより、B ← B + TBL[i]およびA ← A + Bの演算を、入出力ともにTBLとできるため、より消費電力波形または処理時間からkの解析を困難にすることができる。
【００２５】
請求項3に対応する発明は、以上のような手段を講じたことにより、Brickellらの方法で楕円曲線上の点のスカラー倍算を行う際に、kのブロックの値を先に整列しておくことで、楕円曲線上の点の加算を行う演算列を一定にすることができる。したがって演算の消費電力波形または処理時間からkの解析を困難にすることができる。
【００２６】
請求項4に対応する発明は、請求項3に対応する発明において、中間変数A, Bの格納位置を事前計算テーブルと同じ位置にすることにより、B ← B + TBL[i]およびA ← A + Bの演算を、入出力ともにTBLとできるため、より消費電力波形または処理時間からkの解析を困難にすることができる。
【発明の効果】
【００２７】
以上説明したように本発明によれば、Brickellらの方法でベキ乗演算を行うときに、そのベキ指数を、電力解析またはタイミング解析による解析から困難にする耐タンパーベキ乗演算方法を提供できる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の各実施形態について図面を参照しながら説明する。
【００２９】
（第1の実施形態）
図1は本発明の第1の実施形態に係わる耐タンパーベキ乗剰余算方法を実施する装置の構成を示す模式図である。この耐タンパーベキ乗剰余算装置101は、ICカードなどの計算機のベキ乗剰余算演算部として構成されていて、ハードウェアまたはソフトウェアによってベキ乗剰余算を行うものである。具体的には制御部102、ROM（リードオンリーメモリ）103、RAM（ランダムアクセスメモリ）104、事前計算テーブル105、剰余乗算ユニット106からなる。
【００３０】
ROM103はベキ乗剰余算を行う際に必要なパラメータを格納している。例えばm, Nが固定値であるときは、m, Nである。またソフトウェアで実現されるときは、Brickellらの方法でベキ乗剰余算を行うプログラムを格納していることもある。RAM104はベキ乗剰余算の途中結果などの一時的なデータを格納する。事前計算テーブル105は、TBL[i] = mw i mod NからなるTBL[]を格納している。事前計算テーブル105はROM102に含まれていてもよい。剰余乗算ユニット106は、ROM103またはRAM104または事前計算テーブル105から制御部102の制御のもとに入力値x, yを受け、剰余乗算z = a×b mod Nを行って結果zをRAM104に返す。
【００３１】
図2、図3は本発明の第1の実施形態に関わる耐タンパーベキ乗剰余算方法を実現するフローチャートである。このフローチャートは図1に示す耐タンパーベキ乗剰余算装置で実行されるものとしてここでは説明するが、それに限定されるものではない。
【００３２】
図2、図3では、今日のベキ乗剰余算を利用した暗号方式の法は一般に1024ビットが使われていることから、nを1024ビット、wを8ビット、sをs = n/w = 128とした場合を示しているが、もちろん一般化することも容易である。
【００３３】
図2、図3を用いて、本発明の第1の実施形態を説明する。
【００３４】
まずkは8ビットずつ128ブロックに分けられているものとし、それをMSB側からk127, k126, …, k1, k0とする。これは図2には図示されていないが、ステップ201より前もしくはステップ201で行われるステップである。またnが1024ビットの場合を考えているので、MSBを含むブロックに0をパディングする必要がないが、必要に応じてここでkのMSB側に0をパディングしてブロックをwビットにしておく。
【００３５】
ステップ201では、k127, …, k0を大きい順に並べ替え、それに対応する添え字を領域Fに格納する。ステップ201を詳細に記述したフローチャートが図3である。ここでステップ201に対応する図3を説明する。
【００３６】
ステップ301において、添え字を格納する領域Fを0に初期化する。ステップ302から309はdを255（= 2w - 1）からd = 0まで1ずつ減じていくループ処理である。ステップ303から306はiを127（= s - 1）からi = 0まで１ずつ減じていくループ処理である。なおここはiを0から127まで1ずつ増加させていってもよい。ステップ304において、ki = dであるかを検査する。成立するときは添え字を格納する領域Fに1バイトのデータとしてiを連結する（ステップ305）。成立しないときは何もしない、すなわちステップ305を飛ばしてステップ306に進む。ステップ306のiループが終了したのちはステップ307に進み、i > 0か検査する。成立するときは領域Fに、dの値が変化する印をつける。ここでは0x80（10進数では128）という1バイトをその印としている（ステップ308）。成立しないときは何もしない、すなわちステップ308を飛ばしてステップ309に進む。ステップ309のdループが終了したとき、このフローチャートは終了する。
【００３７】
そこで図2のフローチャートに戻る。ステップ202、203で中間結果A、Bをそれぞれ1と設定する。ステップ204から208はiを0から382（= (2w - 1) + s - 1）まで1ずつ増加させていくループ処理である。ステップ205においてFのi番目の要素F[i]が0x80であるか検査する。成立する場合はB×A mod Nを実行してAに格納し（ステップ206）、ステップ208に進む。成立しない場合はB×TBL[F[i]] mod Nを実行してBに格納する（ステップ207）。ステップ208で終了したときに、Aにmk mod Nが格納されている。なぜならば、本実施例では、Brickellらの方法において、ki = dかの判定を処理の先頭で行っているのみで、剰余乗算の実行順序はBrickellらの方法と同じだからである。また、Brickellらの方法ではdのループはd = 0で行っていないが、本実施例（図3）ではd = 0の場合も行っている。しかしステップ307でi = 0の場合はFに0x80を連結していないため、d = 0に対応する図2での演算は、ステップ207が行われるのみで、ステップ206は行われない。したがってd = 0に対応する演算は、最終結果Aに影響を与えないため、Brickellらの方法と同じ最終結果を得ることができる。
【００３８】
このように本発明によれば、ステップ204から208までのループ内で、各ループごとに1回の剰余乗算のみが実行されるため、消費電力波形や処理時間からkの値を推測されるのを困難にすることができる。
【００３９】
また、ステップ201とステップ202は連続して実行される必要はなく、ステップ201を実行してFを格納したのち、別の処理をしてからステップ202以下を実行するようにすることもできる。このようにすると、ステップ201（図3）の処理とステップ202以下の処理の関連をさらに解析しにくくできる。
【００４０】
（第2の実施形態）
第2の実施形態は、第1の実施形態において、途中結果を格納するA, Bを事前計算テーブルTBLと同じ配列に格納することで、より解析を困難にするものである。
【００４１】
図4は本発明の第2の実施形態に関わる耐タンパーベキ乗剰余算方法を実現するフローチャートである。このフローチャートは図1に示す耐タンパーベキ乗剰余算装置で実行されるものとしてここでは説明するが、それに限定されるものではない。
【００４２】
また第2の実施形態では、事前計算テーブル105は書き込みができる必要がある。そのため、計算に先立ってRAM104に格納されているものとする。
【００４３】
図4では、今日のベキ乗剰余算を利用した暗号方式の法は一般に1024ビットが使われていることから、nを1024ビット、wを8ビット、sをs = n/w = 128とした場合を示しているが、もちろん一般化することも容易である。
【００４４】
図4、図2を用いて、本発明の第2の実施形態を説明する。
【００４５】
まずkは8ビットずつ128ブロックに分けられているものとし、それをMSB側からk127, k126, …, k1, k0とする。これは図4には図示されていないが、ステップ401より前もしくはステップ401で行われるステップである。またnが1024ビットの場合を考えているので、MSBを含むブロックに0をパディングする必要がないが、必要に応じてここでkのMSB側に0をパディングしてブロックをwビットにしておく。
【００４６】
ステップ401では、k127, …, k0を大きい順に並べ替え、それに対応する添え字を領域Fに格納する。ステップ401を詳細に記述したフローチャートは第1の実施例同様に図3であり、その流れは第1の実施例で説明した通りである。ステップ402、403で中間結果を格納する領域として事前計算テーブルからTBL[128], TBL[129]を選び、それぞれを1と設定する。ステップ404から406はiを0から382（= (2w - 1) + s - 1）まで1ずつ増加させていくループ処理である。ステップ405においてTBL[129-(F[i]>>7)] ← TBL[129]×TBL[F[i]] mod Nを実行する。この演算では、F[i] = 0x80の場合はTBL[128] ← TBL[129]×TBL[128] mod Nであり、A = TBL[128], B = TBL[129]とした場合の図2におけるステップ206に対応する。F[i]が0x80未満の場合はTBL[129] ← TBL[129]×TBL[F[i]] mod Nであり、B = TBL[129]とした場合の図2におけるステップ207に対応する。したがって図4のフローチャートは図2と同じ演算の流れとなっており、終了したときには、TBL[128]にmk mod Nが格納されている。
【００４７】
このように本発明によれば、ステップ404から406までのループ内で、分岐することなく一定の演算列でベキ乗剰余算が計算されていくため、消費電力波形や処理時間からkの値を推測されるのを困難にすることができる。
【００４８】
また、ステップ401とステップ402は連続して実行される必要はなく、ステップ401を実行してFを格納したのち、別の処理をしてからステップ402以下を実行することで、ステップ401（図3）の処理とステップ402以下の処理の関連をさらに解析しにくくできることは、第1の実施例と同様である。
【００４９】
（第3の実施形態）
図5は本発明の第3の実施形態に係わる耐タンパーベキ乗剰余算方法を実施する装置の構成を示す模式図である。この耐タンパーベキ乗剰余算装置501は、ICカードなどの計算機のベキ乗剰余算演算部として構成されていて、ハードウェアまたはソフトウェアによってベキ乗剰余算を行うものである。具体的には制御部502、ROM（リードオンリーメモリ）503、RAM（ランダムアクセスメモリ）504、事前計算テーブル505、楕円曲線上の点の加算ユニット506からなる。
【００５０】
ROM503はベキ乗剰余算を行う際に必要なパラメータを格納している。例えば楕円曲線のパラメータである。またソフトウェアで実現されるときは、Brickellらの方法で楕円曲線上の点のスカラー倍算を行うプログラムを格納していることもある。RAM504はベキ乗剰余算の途中結果などの一時的なデータを格納する。事前計算テーブル505は、TBL[i] = wiPからなるTBL[]を格納している。事前計算テーブル505はROM502に含まれていてもよい。楕円曲線上の点の加算ユニット506は、ROM503またはRAM504または事前計算テーブル505から制御部502の制御のもとに入力値x, yを受け、楕円曲線上の点の加算z = a + b を行って結果zをRAM504に返す。
【００５１】
図6、図7は本発明の第3の実施形態に関わる耐タンパーベキ乗演算（楕円曲線上のスカラー倍算）方法を実現するフローチャートである。このフローチャートは図5に示す耐タンパーベキ乗剰余算装置で実行されるものとしてここでは説明するが、それに限定されるものではない。
【００５２】
図6、図7では、今日の楕円曲線暗号方式の鍵長は一般に160ビットが使われていることから、nを160ビット、wを4ビット、sをs = n/w = 40とした場合を示しているが、もちろん一般化することも容易である。
【００５３】
図6、図7を用いて、本発明の第1の実施形態を説明する。
【００５４】
まずkは4ビットずつ40ブロックに分けられているものとし、それをMSB側からk39, k38, …, k1, k0とする。これは図6には図示されていないが、ステップ601より前もしくはステップ601で行われるステップである。またnが160ビットの場合を考えているので、MSBを含むブロックに0をパディングする必要がないが、必要に応じてここでkのMSB側に0をパディングしてブロックをwビットにしておく。
【００５５】
ステップ601では、k39, …, k0を大きい順に並べ替え、それに対応する添え字を領域Fに格納する。ステップ601を詳細に記述したフローチャートが図7である。ここでステップ601に対応する図7を説明する。
【００５６】
ステップ701において、添え字を格納する領域Fを0に初期化する。ステップ702から709はdを15（= 2w - 1）からd = 0まで1ずつ減じていくループ処理である。ステップ703から706はiを39（= s - 1）からi = 0まで１ずつ減じていくループ処理である。なおここはiを0から39まで1ずつ増加させていってもよい。ステップ704において、ki = dであるかを検査する。成立するときは添え字を格納する領域Fに1バイトのデータとしてiを連結する（ステップ705）。成立しないときは何もしない、すなわちステップ705を飛ばしてステップ706に進む。ステップ706のiループが終了したのちはステップ707に進み、i > 0か検査する。成立するときは領域Fに、dの値が変化する印をつける。ここでは0x80（10進数では128）という1バイトをその印としている（ステップ708）。成立しないときは何もしない、すなわちステップ708を飛ばしてステップ709に進む。ステップ709のdループが終了したとき、このフローチャートは終了する。
【００５７】
そこで図6のフローチャートに戻る。ステップ602、603で中間結果A、Bをそれぞれ楕円曲線上の無限遠点Oと設定する。ステップ604から608はiを0から54（= (2w - 1) + s - 1）まで1ずつ増加させていくループ処理である。ステップ605においてFのi番目の要素F[i]が0x80であるか検査する。成立する場合はB + Aを実行してAに格納し（ステップ606）、ステップ608に進む。成立しない場合はB + TBL[F[i]]を実行してBに格納する（ステップ607）。ステップ608で終了したときに、AにkPが格納されている。なぜならば、本実施例では、Brickellらの方法において、ki = dかの判定を処理の先頭で行っているのみで、剰余乗算の実行順序はBrickellらの方法と同じだからである。また、Brickellらの方法ではdのループはd = 0で行っていないが、本実施例（図7）ではd = 0の場合も行っている。しかしステップ707でi = 0の場合はFに0x80を連結していないため、d = 0に対応する図6での演算は、ステップ607が行われるのみで、ステップ606は行われない。したがってd = 0に対応する演算は、最終結果Aに影響を与えないため、Brickellらの方法と同じ最終結果を得ることができる。
【００５８】
このように本発明によれば、ステップ604から608までのループ内で、各ループごとに1回の楕円曲線上の点の加算のみが実行されるため、消費電力波形や処理時間からkの値を推測されるのを困難にすることができる。
【００５９】
また、ステップ601とステップ602は連続して実行される必要はなく、ステップ601を実行してFを格納したのち、別の処理をしてからステップ602以下を実行するようにすることもできる。このようにすると、ステップ601（図7）の処理とステップ602以下の処理の関連をさらに解析しにくくできる。
【００６０】
（第4の実施形態）
第4の実施形態は、第3の実施形態において、途中結果を格納するA, Bを事前計算テーブルTBLと同じ配列に格納することで、より解析を困難にするものである。
【００６１】
図8は本発明の第3の実施形態に関わる耐タンパーベキ乗剰余算方法を実現するフローチャートである。このフローチャートは図5に示す耐タンパーベキ乗剰余算装置で実行されるものとしてここでは説明するが、それに限定されるものではない。
【００６２】
また第4の実施形態では、事前計算テーブル505は書き込みができる必要がある。そのため、計算に先立ってRAM504に格納されているものとする。
【００６３】
図8では、今日の楕円曲線暗号方式の鍵長は一般に160ビットが使われていることから、nを160ビット、wを4ビット、sをs = n/w = 40とした場合を示しているが、もちろん一般化することも容易である。
【００６４】
図8、図6を用いて、本発明の第4の実施形態を説明する。
【００６５】
まずkは4ビットずつ40ブロックに分けられているものとし、それをMSB側からk39, k38, …, k1, k0とする。これは図8には図示されていないが、ステップ801より前もしくはステップ801で行われるステップである。またnが160ビットの場合を考えているので、MSBを含むブロックに0をパディングする必要がないが、必要に応じてここでkのMSB側に0をパディングしてブロックをwビットにしておく。
【００６６】
ステップ801では、k39, …, k0を大きい順に並べ替え、それに対応する添え字を領域Fに格納する。ステップ801を詳細に記述したフローチャートは第3の実施例同様に図7であり、その流れは第3の実施例で説明した通りである。ステップ802、803で中間結果を格納する領域として事前計算テーブルからTBL[40], TBL[41]を選び、それぞれを楕円曲線上の無限遠点Oと設定する。ステップ804から806はiを0から54（= (2w - 1) + s - 1）まで1ずつ増加させていくループ処理である。ステップ805においてTBL[41-(F[i]>>7)] ← TBL[41] + TBL[F[i]]を実行する。この演算では、F[i] = 0x80の場合はTBL[41] ← TBL[41] + TBL[40]であり、A = TBL[40], B = TBL[41]とした場合の図6におけるステップ606に対応する。F[i]が0x80未満の場合はTBL[41] ← TBL[41] + TBL[F[i]]であり、B = TBL[41]とした場合の図6におけるステップ607に対応する。したがって図8のフローチャートは図6と同じ演算の流れとなっており、終了したときには、TBL[40]にkPが格納されている。
【００６７】
このように本発明によれば、ステップ804から806までのループ内で、分岐することなく一定の演算列で楕円曲線上の点の加算が計算されていくため、消費電力波形や処理時間からkの値を推測されるのを困難にすることができる。
【００６８】
また、ステップ801とステップ802は連続して実行される必要はなく、ステップ801を実行してFを格納したのち、別の処理をしてからステップ802以下を実行することで、ステップ801（図7）の処理とステップ802以下の処理の関連をさらに解析しにくくできることは、第3の実施例と同様である。
【図面の簡単な説明】
【００６９】
【図１】本発明の第1、第2の実施形態に係る耐タンパーベキ乗剰余算装置
【図２】本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法
【図３】本発明の第1、第2の実施形態に係るkの符号化方法
【図４】本発明の第2の実施形態に係る耐タンパーベキ乗剰余算方法
【図５】本発明の第3、第4の実施形態に係る耐タンパースカラー倍算装置
【図６】本発明の第3の実施形態に係る耐タンパースカラー倍算方法
【図７】本発明の第3、第4の実施形態に係るkの符号化方法
【図８】本発明の第3の実施形態に係る耐タンパースカラー倍算方法
【図９】Brickellらによるベキ乗演算方法
【符号の説明】
【００７０】
101…耐タンパーベキ乗剰余算装置
102…制御部
103…ROM
104…ランダムアクセスメモリ
105…事前計算テーブル
106…剰余乗算ユニット
201…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第1ステップ
202…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第2ステップ
203…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第3ステップ
204…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第4ステップ
205…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第5ステップ
206…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第6ステップ
207…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第7ステップ
208…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第8ステップ
301…本発明の第1、2の実施形態に係るkの符号化方法の第1ステップ
302…本発明の第1、2の実施形態に係るkの符号化方法の第2ステップ
303…本発明の第1、2の実施形態に係るkの符号化方法の第3ステップ
304…本発明の第1、2の実施形態に係るkの符号化方法の第4ステップ
305…本発明の第1、2の実施形態に係るkの符号化方法の第5ステップ
306…本発明の第1、2の実施形態に係るkの符号化方法の第6ステップ
307…本発明の第1、2の実施形態に係るkの符号化方法の第7ステップ
308…本発明の第1、2の実施形態に係るkの符号化方法の第8ステップ
309…本発明の第1、2の実施形態に係るkの符号化方法の第9ステップ
401…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第1ステップ
402…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第2ステップ
403…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第3ステップ
404…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第4ステップ
405…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第5ステップ
406…本発明の第1の実施形態に係る耐タンパーベキ乗剰余算方法の第6ステップ
501…耐タンパースカラー倍算装置
502…制御部
503…ROM
504…ランダムアクセスメモリ
505…事前計算テーブル
506…楕円曲線上の点の加算ユニット
601…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第1ステップ
602…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第2ステップ
603…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第3ステップ
604…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第4ステップ
605…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第5ステップ
606…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第6ステップ
607…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第7ステップ
608…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第8ステップ
701…本発明の第3、4の実施形態に係るkの符号化方法の第1ステップ
702…本発明の第3、4の実施形態に係るkの符号化方法の第2ステップ
703…本発明の第3、4の実施形態に係るkの符号化方法の第3ステップ
704…本発明の第3、4の実施形態に係るkの符号化方法の第4ステップ
705…本発明の第3、4の実施形態に係るkの符号化方法の第5ステップ
706…本発明の第3、4の実施形態に係るkの符号化方法の第6ステップ
707…本発明の第3、4の実施形態に係るkの符号化方法の第7ステップ
708…本発明の第3、4の実施形態に係るkの符号化方法の第8ステップ
709…本発明の第3、4の実施形態に係るkの符号化方法の第9ステップ
801…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第1ステップ
802…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第2ステップ
803…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第3ステップ
804…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第4ステップ
805…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第5ステップ
806…本発明の第3の実施形態に係る耐タンパーベキ乗剰余算方法の第6ステップ
901…Brickellらによるベキ乗演算方法の第1ステップ
902…Brickellらによるベキ乗演算方法の第2ステップ
903…Brickellらによるベキ乗演算方法の第3ステップ
904…Brickellらによるベキ乗演算方法の第4ステップ
905…Brickellらによるベキ乗演算方法の第5ステップ
906…Brickellらによるベキ乗演算方法の第6ステップ
907…Brickellらによるベキ乗演算方法の第7ステップ
908…Brickellらによるベキ乗演算方法の第8ステップ
909…Brickellらによるベキ乗演算方法の第9ステップ
【特許請求の範囲】
【請求項１】
情報処理装置を利用して暗号処理中に出現するベキ乗剰余算c = mk mod Nを計算する方法であって、
nビットの整数データkをLSB（Least Significant Bit、最下位ビット）から順にwビットずつのs個のブロック（sはn/w以上の最小の整数）に分ける手段と、
前記データkのMSB（Most Significant Bit、最上位ビット）を含むブロックがwビットに満たない場合にMSB側に0をパディングして前記ブロックをwビットにする手段と、
前記ブロックに分けられたデータkをks-1, ks-2, …, k1, k0としたとき、各ブロックをwビットの整数と見て大きい順に並び替えた場合に、対応する添え字をその順序で格納する手段と、
前記添え字を格納する際に、前記kをwビットのブロックで大きい順に並び替えたときに大きさが変わる箇所に相当する添え字に印を付加する手段と、
i = 1, 2, …, sに対しs個のデータTBL[i] = mw i mod Nからなる事前計算テーブルTBLを保持する手段と、
2つの中間変数A, Bを1に初期化する手段と、
ループカウンタdをs-1に初期化する手段と、
前記格納された添え字を順番に参照し、添え字に印がない場合はB×TBL[d] mod Nを計算してBに格納し、添え字に印がある場合はB×A mod Nを計算してAに格納してdから1減じる手段と
を有することを特徴とする耐タンパーベキ乗演算方法。
【請求項２】
前記2つの中間変数A, BをそれぞれTBL[s], TBL[s+1]またはTBL[s+1], TBL[s]とすることを特徴とする請求項１記載の耐タンパーベキ乗演算方法。
【請求項３】
情報処理装置を利用して暗号処理中に出現する楕円曲線上の点のスカラー倍算Q = kPを計算する方法であって、
前記nビットの整数データkをLSB（Least Significant Bit、最下位ビット）から順にwビットずつのs個のブロック（sはn/w以上の最小の整数）に分ける手段と、
前記データkのMSB（Most Significant Bit、最上位ビット）を含むブロックがwビットに満たない場合にMSB側に0をパディングして前記ブロックをwビットにする手段と、
前記ブロックに分けられたデータkをks-1, ks-2, …, k1, k0としたとき、各ブロックをwビットの整数と見て大きい順に並び替えた場合に、対応する添え字をその順序で格納する手段と、
前記添え字を格納する際に、前記kをwビットのブロックで大きい順に並び替えたときに大きさが変わる箇所に相当する添え字に印を付加する手段と、
i = 1, 2, …, sに対しs個のデータTBL[i] = wi Pからなる事前計算テーブルTBLを保持する手段と、
2つの中間変数A, Bを1に初期化する手段と、
ループカウンタdをs-1に初期化する手段と、
前記格納された添え字を順番に参照し、添え字に印がない場合はB×TBL[d] mod Nを計算してBに格納し、添え字に印がある場合はB×A mod Nを計算してAに格納してdから1減じる手段と
を有することを特徴とする耐タンパーベキ乗演算方法。
【請求項４】
前記2つの中間変数A, BをそれぞれTBL[s], TBL[s+1]またはTBL[s+1], TBL[s]とすることを特徴とする請求項３記載の耐タンパーベキ乗演算方法。
【請求項１】
情報処理装置を利用して暗号処理中に出現するベキ乗剰余算c = mk mod Nを計算する方法であって、
nビットの整数データkをLSB（Least Significant Bit、最下位ビット）から順にwビットずつのs個のブロック（sはn/w以上の最小の整数）に分ける手段と、
前記データkのMSB（Most Significant Bit、最上位ビット）を含むブロックがwビットに満たない場合にMSB側に0をパディングして前記ブロックをwビットにする手段と、
前記ブロックに分けられたデータkをks-1, ks-2, …, k1, k0としたとき、各ブロックをwビットの整数と見て大きい順に並び替えた場合に、対応する添え字をその順序で格納する手段と、
前記添え字を格納する際に、前記kをwビットのブロックで大きい順に並び替えたときに大きさが変わる箇所に相当する添え字に印を付加する手段と、
i = 1, 2, …, sに対しs個のデータTBL[i] = mw i mod Nからなる事前計算テーブルTBLを保持する手段と、
2つの中間変数A, Bを1に初期化する手段と、
ループカウンタdをs-1に初期化する手段と、
前記格納された添え字を順番に参照し、添え字に印がない場合はB×TBL[d] mod Nを計算してBに格納し、添え字に印がある場合はB×A mod Nを計算してAに格納してdから1減じる手段と
を有することを特徴とする耐タンパーベキ乗演算方法。
【請求項２】
前記2つの中間変数A, BをそれぞれTBL[s], TBL[s+1]またはTBL[s+1], TBL[s]とすることを特徴とする請求項１記載の耐タンパーベキ乗演算方法。
【請求項３】
情報処理装置を利用して暗号処理中に出現する楕円曲線上の点のスカラー倍算Q = kPを計算する方法であって、
前記nビットの整数データkをLSB（Least Significant Bit、最下位ビット）から順にwビットずつのs個のブロック（sはn/w以上の最小の整数）に分ける手段と、
前記データkのMSB（Most Significant Bit、最上位ビット）を含むブロックがwビットに満たない場合にMSB側に0をパディングして前記ブロックをwビットにする手段と、
前記ブロックに分けられたデータkをks-1, ks-2, …, k1, k0としたとき、各ブロックをwビットの整数と見て大きい順に並び替えた場合に、対応する添え字をその順序で格納する手段と、
前記添え字を格納する際に、前記kをwビットのブロックで大きい順に並び替えたときに大きさが変わる箇所に相当する添え字に印を付加する手段と、
i = 1, 2, …, sに対しs個のデータTBL[i] = wi Pからなる事前計算テーブルTBLを保持する手段と、
2つの中間変数A, Bを1に初期化する手段と、
ループカウンタdをs-1に初期化する手段と、
前記格納された添え字を順番に参照し、添え字に印がない場合はB×TBL[d] mod Nを計算してBに格納し、添え字に印がある場合はB×A mod Nを計算してAに格納してdから1減じる手段と
を有することを特徴とする耐タンパーベキ乗演算方法。
【請求項４】
前記2つの中間変数A, BをそれぞれTBL[s], TBL[s+1]またはTBL[s+1], TBL[s]とすることを特徴とする請求項３記載の耐タンパーベキ乗演算方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００８−２２４８３０（Ｐ２００８−２２４８３０Ａ）
【公開日】平成２０年９月２５日（２００８．９．２５）
【国際特許分類】
【出願番号】特願２００７−５９９８６（Ｐ２００７−５９９８６）
【出願日】平成１９年３月９日（２００７．３．９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
【公開日】平成２０年９月２５日（２００８．９．２５）
【国際特許分類】
【出願日】平成１９年３月９日（２００７．３．９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
[ Back to top ]