演算装置及びプログラム
【課題】ｋｂビットの数Ａとｂビットの数ｒとを互いに加算して上位（ｋ−１）ｂビットの加算結果を得る場合に必要な事前計算テーブルのサイズを縮小する。
【解決手段】ｋｂビットの数Ａとｂビットの乱数ｒとの加算について、数Ａの下位ｂビットの数Ａ2の上位ｂ／２ビットの値ＡHと乱数ｒの上位ｂ／２ビットの値ｒHとの和ＡH＋ｒHと、数Ａ2の下位ｂ／２ビットの値ＡLと乱数ｒの下位ｂ／２ビットの値ｒLとの和ＡL＋ｒLとに基づいて、Ａ2＋ｒの桁上げの有無を示すように事前計算テーブルＣ’の要素データを設定したので、上記課題を解決できる。
【解決手段】ｋｂビットの数Ａとｂビットの乱数ｒとの加算について、数Ａの下位ｂビットの数Ａ2の上位ｂ／２ビットの値ＡHと乱数ｒの上位ｂ／２ビットの値ｒHとの和ＡH＋ｒHと、数Ａ2の下位ｂ／２ビットの値ＡLと乱数ｒの下位ｂ／２ビットの値ｒLとの和ＡL＋ｒLとに基づいて、Ａ2＋ｒの桁上げの有無を示すように事前計算テーブルＣ’の要素データを設定したので、上記課題を解決できる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、サイドチャネル解析への耐性を持たせるように算術的マスクをした被算術マスクデータを、論理的マスクをした被論理マスクデータに変換する場合に、必要な事前計算テーブルのサイズを縮小し得る演算装置及びプログラムに関する。
【背景技術】
【０００２】
近年の情報通信技術にとって、暗号技術は欠かせない技術となってきている。この種の暗号化技術には、例えば通信の暗号化技術であるＳＳＬ（Secure Socket Layer）や、メッセージの改ざんの有無を検出可能な電子署名などがある。これらはＰＫＩ（Public Key Infrastructure：公開鍵基盤）の一部として、社会の電子化を支えている。
【０００３】
しかしながら、暗号技術に対する攻撃手法も高度化してきている。その中でも、暗号プロセッサの処理時間や消費電力を測定し、測定結果から暗号プロセッサ内部の秘密情報を解析するというサイドチャネル解析が現実的な脅威となってきている。代表的なサイドチャネル解析としては、タイミング解析及び電力解析が知られている。
【０００４】
電力解析の例として、非特許文献１に記載のＤＥＳ（Data Encryption Standard）に対する解析方法を図面を用いて説明する。
【０００５】
図７はＤＥＳ暗号装置における最終１６段目のデータ変換部を示す模式図である。
【０００６】
１６段目のデータ変換部においては、２つの３２ビットの入力データＬ15、Ｒ15及び４８ビットの鍵データＫ16が入力されると、データ変換処理が実行され、２つの３２ビットの出力データＬ16、Ｒ16が出力される。
【０００７】
この出力データＬ16、Ｒ16をビット転置ＩＰ-1した結果がＤＥＳ暗号装置から出力される暗号文となる。ここで、暗号文及びビット転置ＩＰ-1は、それぞれ攻撃者に既知であるため、出力データＬ16、Ｒ16も攻撃者に既知となる。
【０００８】
１６段目のデータ変換部では、３２ビットの入力データＲ15をＥ転置により４８ビットのデータに拡大する。拡大後のデータは４８ビットの鍵データＫ16との排他的論理和が取られる。排他的論理和後の４８ビットのデータは６ビットの８個の分割データに分割され、各分割データがそれぞれＳボックス（S-box）Ｓ1，Ｓ2，…，Ｓ8に入力される。
【０００９】
各Ｓボックスは６ビット入力４ビット出力であり、全部で３２ビットの出力データが得られる。この３２ビットの出力データは、Ｐ転置により別の３２ビットのデータに変換された後、入力データＬ15との排他的論理和が取られて一方の出力データＬ16となる。他方の出力データＲ16は、入力データＲ15がそのまま出力されたものである。
【００１０】
このようなデータ変換処理において、攻撃者に未知のデータは４８ビットの鍵データＫ16のみである。攻撃者は、この４８ビットの値を、１６段目のデータ変換処理を実行中のＤＥＳ暗号装置の消費電力を解析して求める。
【００１１】
具体的には、攻撃者は入力平文Ｍiを取り替えながら１，０００サンプルのＤＥＳ処理に対する消費電力波形ｖi（ｔ）を収集する。ここで、ｔは離散的な時刻を表し、iはサンプル番号（但し、０≦ i ≦９９９）を表す。
【００１２】
１６段目のある１つのＳボックスｓの出力１ビットをターゲットビットとする。このＳボックスｓの６ビットの入力データｃは、出力データＬ16から逆にたどることで導出可能である。Ｓボックスの入力データｃとしては、入力データｃ以外に、入力データｃと排他的論理和される６ビットの部分鍵ｋjがある。この部分鍵ｋjを未知変数として、ターゲットとなるＳボックス出力１ビットをｓi（ｋj，ｃi）と書く。
【００１３】
収集した消費電力波形を基に、差分平均トレースＴj（ｔ）を次の式により計算する。
【数１】
【００１４】
部分鍵ｋjとして６ビット６４通りの全ての場合について差分平均トレースＴj（ｔ）を計算すると、６４通りの内の一つの部分鍵ｋjは、実際に使われている部分鍵ｋjと一致しており、その時の差分平均トレースＴj（ｔ）は値の偏りを示す。それ以外の６３通りの部分鍵の場合には部分平均トレースＴj（ｔ）は偏らない。この偏り特性により、６ビットの部分鍵ｋjを特定可能となっている。
【００１５】
この操作を他の７つのＳボックスｓにも適用することで４８ビットの部分鍵Ｋ16を見出すことが可能である。
【００１６】
このような電力解析においては、攻撃者が予想した未知変数ｋjの値と消費電力ｖi（ｔ）に相関があることが効いている。このことは未知変数の値と測定時間との相関を見るタイミング解析でも同様である。
【００１７】
従って、逆にこのような相関をなくせば、サイドチャネル解析から秘密情報の漏洩を阻止可能である。そこで、暗号装置が処理するデータと攻撃者が予想したデータとの相関を無くすため、暗号装置が処理するデータに乱数をマスクする手法が知られている。
【００１８】
マスク方法としては、主に論理的マスクと算術的マスクの２種類があり、暗号アルゴリズムを構成する演算を基に、いずれのマスクを使用するかを決定する。例えば、論理演算から構成される暗号アルゴリズムには論理的マスクを使用し、算術演算から構成される暗号アルゴリズムには算術マスクを使用する。マスクの際に用いる演算と暗号アルゴリズムの演算は、可換とすることが効率的に良い。すなわち、マスクされたデータに暗号アルゴリズムの演算を施す場合には、最後にマスクを外した後の演算結果が、最初からマスクをしなかった場合の演算結果と同じになるように、マスクの際に用いる演算を定める。一般に、共通鍵暗号方式は論理的マスクを使用し、公開鍵暗号方式は算術的マスクを使用することが多い。
【００１９】
共通鍵暗号方式やハッシュ関数の中には、１つのアルゴリズムの中で論理演算と算術演算の両方を用いるアルゴリズムが存在する。例えば共通鍵暗号方式ではＩＤＥＡ（International Data Encryption Algorithm）、ＳＥＥＤ、ハッシュ関数ではＳＨＡ−１（Secure Hash Algorithm - 1）などがある。これらのアルゴリズムにおいてデータをマスクするには、暗号アルゴリズムで論理演算を用いる部分では論理的マスクをする一方、算術演算を用いる部分では算術的マスクをする必要がある。
【００２０】
これらのアルゴリズムでは、処理単位（ワード）をｗビットとしたとき、ｗビットのデータｘをｗビットの数Ｒでマスクするには、論理的マスクの場合は排他的論理和を用いて、次式の演算を実行する。
【００２１】
ｘ’＝ｘ＾Ｒ （但し、＾は排他的論理和を表す記号）
算術的マスクの場合は剰余付き減算を用いて、次式の演算を実行する。
Ａ＝ｘ−Ｒ ｍｏｄ ２ｗ
上の暗号アルゴリズムの例ではｗ＝３２ビットである。
【００２２】
従って、暗号アルゴリズムにおける演算列において論理演算から算術演算に変わる場面では、論理的マスクが施されたデータ（以下、被論理マスクデータという）ｘ’から算術的マスクが施されたデータ（以下、被算術マスクデータという）Ａへデータを変換する必要がある。同様に、算術演算から論理演算に変わる場面では、被算術マスクデータＡから被論理マスクデータｘ’へ、データを変換する必要がある。
【００２３】
例えば被論理マスクデータｘ’から被算術マスクデータＡに変換する最も簡単な方法は、（ｘ’＾Ｒ）−Ｒ ｍｏｄ ２ｗ を演算する方式である。但し、この方式は、ｘ’＾Ｒ＝ｘであるから、マスクされていない状態のデータｘが演算中に出現するので、望ましくない。
【００２４】
データに常にマスクをつけた状態で被論理マスクデータｘ’と被算術マスクデータＡを変換する方法として、非特許文献２，３が知られている。非特許文献２では、被論理マスクデータｘ’から被算術マスクデータＡへ変換する方法と、被算術マスクデータＡから被論理マスクデータｘ’へ変換する方法が提案されている。後者の方法は効率が低いため、事前計算テーブルを用いて高速化を図る方法が非特許文献３で提案されている。
【００２５】
図８乃至図１０を用いて、非特許文献３での被算術マスクデータＡから被論理マスクデータｘ’への変換方法を説明する。演算を行う単位をｂビットとする。簡単のため、ｂはｗの約数であるとし、ある整数ｋにより、ｗ＝ｋ×ｂとかけるものとする。
【００２６】
始めに、論理的マスク及び算術的マスクがｂビットの場合（すなわちｗ＝ｂ、ｋ＝１）の事前計算テーブルＧを構成する。０から２b−１までの各整数Ｉに対して、事前計算テーブルを次式で定義する。
【００２７】
Ｇ［Ｉ］＝（（Ｉ＋ｒ） ｍｏｄ ２b）＾ｒ
ここで、便宜上、ｂビットの乱数をｒと記載している。ｗ＝ｂの場合、上記数Ｒとの関係はＲ＝ｒである。事前計算テーブルＧは、２b個の要素データからなるテーブルであり、各要素データがｂビットである。被算術マスクデータＡは、事前計算テーブルＧの要素データＧ［Ａ］を求めることで被論理的マスクｘ’に変換可能となっている。その理由は以下の通りである。
【００２８】
Ｇ［Ａ］＝（（Ａ＋ｒ） ｍｏｄ ２b）＾ｒ
＝（（ｘ−ｒ）＋ｒ ｍｏｄ ２ｗ）＾ｒ
＝（ｘ ｍｏｄ ２ｗ）＾ｒ
＝ｘ＾ｒ
＝ｘ’
図８に、ｗ＝ｂ＝４、ｒ＝３の場合の事前計算テーブルＧを示す。図の配列は、左側から順にＧ［０］，Ｇ［１］，…，Ｇ［１５］の値を１６進数表記で示している。例えばＧ［９］＝０ｘＦである。
【００２９】
図９にｋ＞１（すなわちｗ＞ｂ）の場合に、非特許文献３による被算術マスクデータＡから被論理マスクデータｘ’に変換するアルゴリズムを示す。このアルゴリズムはｗ＝ｋ×ｂビットの被算術マスクデータＡと数Ｒを入力したとき、ｗビットの被論理マスクデータｘ’を出力するアルゴリズムである。
【００３０】
始めに、整数ｍ及び被論理マスクデータｘ’をそれぞれｍ＝ｋ、ｘ’＝０とする（ステップＳ１１０、Ｓ１２０）。
【００３１】
次に、被算術マスクデータＡから乱数ｒをｍｏｄ ２ｍｂ の下で減算する（ステップＳ１３０）。
【００３２】
数ＲをＬＳＢ（Least Significant Bit：最下位ビット）からｂビット目の値で上位の数Ｒ1と下位の数Ｒ2に分割する（ステップＳ１４０）。すなわち上位の数Ｒ1は数Ｒの上位（ｍ−１）ｂビットであり、下位の数Ｒ2は下位ｂビットである。
【００３３】
被算術マスクデータＡに下位の数Ｒ2をｍｏｄ ２ｍｂ の下で加算する（ステップＳ１５０）。
【００３４】
次に、整数ｍについて、ｍ＝１か否かを判断する（ステップＳ１６０）。ｍ＝１の場合は上位の被論理マスクデータｘ’1を次式の通り計算する（ステップＳ１７０、Ｓ１８０）。
【００３５】
ｘ’1＝（Ｇ［Ａ］＾Ｒ2）＾ｒ
しかる後、得られた上位の被論理マスクデータｘ’1を被論理マスクデータｘ’の最上位ｂビットに配置して（ステップＳ１９０）アルゴリズムを終了する。
【００３６】
ｍ＞１の場合は、以下の処理を行う。
【００３７】
被算術マスクデータＡを数Ｒと同様に上位の被算術マスクデータＡ1と、下位の被算術マスクデータＡ2とに分割する（ステップＳ１６１）。
【００３８】
ステップＳ１３０とステップＳ１５０による桁上げ（Ａ2＋ｒにより生じるｂ＋１ビット目の値）を上位の被算術マスクデータＡ1に対応させるため、次式を計算する（ステップＳ１６２、Ｓ１６３）。なお、本明細書中、「桁上げ」は「キャリー」に読み替えてもよい。
【００３９】
Ａ1＝（Ａ1＋Ｃ［Ａ2］）−γ ｍｏｄ ２(m-1)b
続いて、下位の被論理マスクデータｘ’2を次式に示すように計算する（ステップＳ１６４、Ｓ１６５）。
【００４０】
ｘ’2＝（Ｇ［Ａ2］＾Ｒ2）＾ｒ
しかる後、下位の被論理マスクデータｘ’2を、被論理マスクデータｘ’の下位（ｋ−ｍ）ｂビット目に、当該下位の被論理マスクデータｘ’2の最下位ビットＬＳＢが合うように配置する（ステップＳ１６６）。
【００４１】
しかる後、整数ｍを、ｍ＝ｍ−１と更新し（ステップＳ１６７）、ステップＳ１３０からくり返す。
【００４２】
上記アルゴリズムにおいて、ステップＳ１３０とステップＳ１５０における下位桁からの桁上げ（キャリー）を調整する際に、桁上げ情報をマスクするために事前計算テーブルＣ及びｂビットの乱数γを利用している。事前計算テーブルＣは、０から２b−１までの各整数Ｉに対し、次のように定義される。
【００４３】
Ｃ［Ｉ］＝γ （Ｉ＋ｒ＜２bのとき）
Ｃ［Ｉ］＝γ＋１（Ｉ＋ｒ≧２bのとき）
ここで、事前計算テーブルＣは、２b個の要素データからなるテーブルであり、各要素データがｂビットである。
【００４４】
図１０に、ｂ＝４、ｒ＝３、γ＝９の場合の事前計算テーブルＣを示す。図の配列は、左側から順にＣ［０］，Ｃ［１］，…，Ｃ［１５］の値を１６進数表記で示している。例えばＣ［０ｘＥ］＝０ｘＡである。
【先行技術文献】
【非特許文献】
【００４５】
【非特許文献１】L. Goubin, J. Patarin, “DES and Differential Power Analysis - The Duplication Method”, CHES ’99, LNCS 1717, pp.158-172, 1999
【非特許文献２】L. Goubin, “A Sound Method for Switching between Boolean and Arithmetic Masking”, CHES 2001, LNCS 2162, pp.3-15, 2001
【非特許文献３】J-S, Coron, A. Tchulkine, “A New Algorithm for Switching from Arithmetic to Boolean Masking”, CHES 2003, LNCS 2779, pp.89-97, 2003
【発明の概要】
【発明が解決しようとする課題】
【００４６】
しかしながら、以上のような非特許文献３における被算術マスクデータＡから被論理マスクデータｘ’への変換方法では、事前計算テーブルＧ，Ｃを格納する領域として、２つのｂ×２bビットの格納領域が必要となる。例えばｂ＝４の場合には１２８ビット（＝１６バイト）の格納領域、ｂ＝８の場合には４，０９６ビット（＝５１２バイト）の格納領域でよいが、ｂ＝１６の場合には２，０９７，１５２ビット（＝２６２，１４４バイト）の格納領域が必要となり、非現実的である。
【００４７】
従って、実際にはｂ＝８程度の場合の格納領域が妥当な大きさではあるが、それでもＩＣカードのような記憶容量の小さい装置に実装する際には、５１２バイトの事前計算テーブルＧ，Ｃでも、リソースを圧迫するか、あるいは実装できないという問題がある。
【００４８】
本発明者の検討によれば、この問題は、ｋｂビットの数Ａとｂビットの数ｒとを互いに加算して上位（ｋ−１）ｂビットの加算結果を得る場合に必要な事前計算テーブルのサイズを縮小できれば、解消できると考えられる。すなわち、ステップＳ１３０とステップＳ１５０による桁上げ（Ａ2＋ｒにより生じるｂ＋１ビット目の値）を上位の被算術マスクデータＡ1に対応させる場合に必要な事前計算テーブルＣのサイズを縮小できれば、この問題を解消できると考えられる。
【００４９】
本発明は上記実情を考慮してなされたもので、ｋｂビットの数Ａとｂビットの数ｒとを互いに加算して上位（ｋ−１）ｂビットの加算結果を得る場合に必要な事前計算テーブルのサイズを縮小し得る演算装置及びプログラムを提供することにある。
【課題を解決するための手段】
【００５０】
本発明の一つの局面は、上位（ｋ−１）ｂビットの数Ａ1及び下位ｂビットの数Ａ2からなるｋｂビットの数Ａ（但し、ｂ＞４）と、ｂビットの数ｒとを加算して上位（ｋ−１）ｂビットの加算結果を得る処理の前に、（４×２b/2）個のインデックスｙ（但し、０≦ｙ＜４×２b/2）の各々により個別に読出可能な（４×２b/2）個のｂビットの要素データＣ’［ｙ］を備えた事前計算テーブルＣ’を生成し、前記加算する処理中に、前記数Ａ2と前記数ｒとの加算結果から前記数Ａ1への桁上げを前記事前計算テーブルＣ’に基づいて伝播可能な演算装置であって、前記ｂビットの乱数γを生成する手段と、前記各インデックスｙと、当該各インデックスｙに関連付けた各要素データＣ’［ｙ］とを備えた事前計算テーブルＣ’を記憶するための記憶手段と、前記記憶手段内の事前計算テーブルＣ’の１個目から２b/2個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記数ｒの上位ｂ／２ビットの数ｒHとに基づいて、Ｃ’［ｙ］＝２b/2 （但し、０≦ｙ＜２b/2−ｒH−１ ）、Ｃ’［ｙ］＝２×２b/2 （但し、ｙ＝２b/2−ｒH−１ ）、Ｃ’［ｙ］＝３×２b/2 （但し、２b/2−ｒH≦ｙ＜２b/2 ）、の値に設定する手段と、前記記憶手段内の事前計算テーブルＣ’の（２b/2＋１）個目から（２×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、Ｃ’［ｙ］＝γ （但し、２b/2≦ｙ＜２×２b/2）、の値に設定する手段と、前記記憶手段内の事前計算テーブルＣ’の（２×２b/2＋１）個目から（３×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γと前記数ｒの下位ｂ／２ビットの数ｒLとに基づいて、Ｃ’［ｙ］＝γ （但し、２×２b/2≦ｙ＜３×２b/2−ｒL）、Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2−ｒL≦ｙ＜３×２b/2）、の値に設定する手段と、前記記憶手段内の事前計算テーブルＣ’の（３×２b/2＋１）個目から（４×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2≦ｙ＜４×２b/2）の値に設定する手段と、前記数Ａから前記数Ａ1及び前記数Ａ2を抽出する第１抽出手段と、前記数Ａ2の上位ｂ／２ビットの数ＡH及び下位ｂ／２ビットの数ＡLを当該数Ａ2から抽出する第２抽出手段と、前記（４×２b/2）個の要素データＣ’［ｙ］の値を設定した後、前記抽出した数ＡHをインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第１の要素データＣ’［ＡH］を読み出す第１読出手段と、前記第１の要素データＣ’［ＡH］と前記抽出した数ＡLとの和をインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］を読み出す第２読出手段と、前記第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］、前記乱数γ、前記数Ａ1及び当該数Ａ1のビット数（ｋ−１）ｂに基づいて、Ａ1＋Ｃ’［Ｃ’［ＡH］＋ＡL］−γ ｍｏｄ ２(k-1)b を計算することにより、前記数Ａ1への桁上げを伝播する桁上げ伝播手段と、を備えた演算装置である。
【００５１】
なお、本発明の一つの局面は、装置として表現したが、装置に限らず、方法、プログラム、プログラムを記憶したコンピュータ読み取り可能な記憶媒体として表現してもよい。
【００５２】
（作用）
本発明の一つの局面においては、ｋｂビットの数Ａとｂビットの乱数ｒとの加算について、数Ａの下位ｂビットの数Ａ2の上位ｂ／２ビットの値ＡHと乱数ｒの上位ｂ／２ビットの値ｒHとの和ＡH＋ｒHと、数Ａ2の下位ｂ／２ビットの値ＡLと乱数ｒの下位ｂ／２ビットの値ｒLとの和ＡL＋ｒLとに基づいて、Ａ2＋ｒの桁上げの有無を示すように事前計算テーブルＣ’の要素データを設定したので、非特許文献３に記載の方法に比べ、ｋｂビットの数Ａとｂビットの数ｒとを互いに加算して上位（ｋ−１）ｂビットの加算結果を得る場合に必要な事前計算テーブルのサイズを縮小することができる。
【発明の効果】
【００５３】
以上説明したように本発明によれば、ｋｂビットの数Ａとｂビットの数ｒとを互いに加算して上位（ｋ−１）ｂビットの加算結果を得る場合に必要な事前計算テーブルのサイズを縮小できる。
【図面の簡単な説明】
【００５４】
【図１】本発明の第１の実施形態に係る演算装置の概略図である。
【図２】同実施形態における事前計算テーブルＣの生成手順を示すフローチャートである。
【図３】同実施形態における事前計算テーブルＣの一例を示す図である。
【図４】同実施形態における加算手順を示すフローチャートである。
【図５】本発明の第２の実施形態に係る演算装置に適用された算術的マスクから論理的マスクへの変換手順を示すフローチャートである。
【図６】本発明の概要を説明するためのフローチャートである。
【図７】一般的なＤＥＳのデータ変換部の１６段目を示す図である。
【図８】従来の事前計算テーブルＧの一例を示す図である。
【図９】従来の算術的マスクから論理的マスクへの変換手順を示すフローチャートである。
【図１０】従来の事前計算テーブルＣの一例を示す図である。
【発明を実施するための形態】
【００５５】
以下、本発明の各実施形態について図面を用いて説明するが、その前に本発明の概要を図６を参照して述べる。
事前計算テーブルＣ’を生成するときに、０から２b−１までの範囲内の整数Ａに対して、整数ｒでマスクした値Ａ＋ｒが２bより小さいか否かの判断（桁上げの有無の判断）を、上位ｂ／２ビットと下位ｂ／２ビットに分けて行う。
【００５６】
ここで、整数Ａの上位ｂ／２ビットの数をＡH、下位ｂ／２ビットの数をＡLと表すことにする。整数ｒについても同様に、上位ｂ／２ビットの数をｒH、下位ｂ／２の数をｒLと表す（例、ｒ＝0x19の場合、ｒH＝１、ｒL＝９）。
【００５７】
例えば、上位ｂ／２ビット同士ＡH，ｒHの加算結果がＡH＋ｒH＜２b/2−１であれば、ＡL，ｒLの値によらず、Ａ＋ｒ＜２bである（即ち、桁上げ無し）と判断できる。そのため、この桁上げ無しの場合には事前計算テーブルＣ’を参照したときに値γ（乱数）が読み出されるように事前計算テーブルＣ’を生成する。この場合は、具体的には、数ＡHをインデックスｙとしてｂビットの値Ｃ’［ＡH］を得る場合（但し、０≦ｙ＜２b/2−ｒH−１）の（２b/2−ｒH−１）個×ｂビットのサイズ（例、図３の０行目の１４個の値Ｃ’［0x00］，…，Ｃ’［0x1D］＝0x10，…，0x10のサイズ）と、このインデックスｙにより得られた値Ｃ’［ＡH］に数ＡLを加算した値（0x10＋ＡL）をインデックスｙとしてｂビットの値γを得る場合（但し、２b/2≦ｙ＜２×２b/2）の２b/2個×ｂビットのサイズ（例、図３の１行目の１６個の値Ｃ’［0x10］〜Ｃ’［0x1F］＝0x56，…，0x56のサイズ）とを必要とする。
【００５８】
次に、上位ｂ／２ビット同士ＡH，ｒHの加算結果がＡH＋ｒH≧２b/2 であれば、ＡL，ｒLの値によらず、Ａ＋ｒ≧２bである（即ち、桁上げ有り）と判断できる。そのため、この桁上げ有りの場合には事前計算テーブルＣ’を参照したときに値γ＋１（乱数付き桁上げ情報）が読み出されるように事前計算テーブルＣ’を生成する。この場合は、具体的には、数ＡHをインデックスｙとしてｂビットの値Ｃ’［ＡH］を得る場合（但し、２b/2−ｒH≦ｙ＜２b/2 ）のｒH個×ｂビットのサイズ（例、図３の０行目の１個の値Ｃ’［0x0F］＝0x30のサイズ）と、このインデックスｙにより得られた値Ｃ’［ＡH］に数ＡLを加算した値（0x30＋ＡL）をインデックスｙとしてｂビットの値γを得る場合（但し、３×２b/2≦ｙ＜４×２b/2）の２b/2個×ｂビットのサイズ（例、図３の３行目の１６個の値Ｃ’［0x30］，…，Ｃ’［0x3F］＝0x57，…，0x57のサイズ）とを必要とする。
【００５９】
最後に、上位ｂ／２ビット同士ＡH，ｒHの加算結果がＡH＋ｒH＝２b/2−１のときには、下位ｂ／２ビット同士ＡL，ｒLの加算結果がＡL＋ｒL＜２b/2であればＡ＋ｒ＜２bである（即ち、桁上げ無し）と判断でき、そうでなければＡ＋ｒ≧２bである（即ち、桁上げ有り）と判断できる。そのため、事前計算テーブルＣ’を参照したときに、桁上げ無しの場合には値γが読み出され、桁上げ有りの場合には値γ＋１が読み出されるように事前計算テーブルＣ’を生成する。これらの場合には、具体的には、数ＡHをインデックスｙとしてｂビットの値Ｃ’［ＡH］を得る場合（但し、ｙ＝２b/2−ｒH−１）の１個×ｂビットのサイズ（例、図３の０行目の１個の値Ｃ’［0x0E］＝0x20のサイズ）と、このインデックスｙにより得られた値Ｃ’［ＡH］に数ＡLを加算した値（0x20＋ＡL）をインデックスｙとしてｂビットの値γを得る場合（但し、２×２b/2≦ｙ＜３×２b/2−ｒL）の（２b/2−ｒL）個×ｂビットのサイズ（例、図３の２行目の７個の値Ｃ’［0x20］，…，Ｃ’［0x26］＝0x56，…，0x56のサイズ）と、値Ｃ’［ＡH］に数ＡLを加算した値（0x20＋ＡL）をインデックスｙとしてｂビットの値γ＋１を得る場合（但し、３×２b/2−ｒL≦ｙ＜３×２b/2）のｒL個×ｂビットのサイズ（例、図３の２行目の９個の値Ｃ’［0x27］，…，Ｃ’［0x2F］＝0x57，…，0x57のサイズ）とを必要とする。
【００６０】
このような事前計算テーブルＣ’のサイズは、これら全てのサイズを足し合わせた値となり、具体的には、（２b/2−ｒH−１）個×ｂビットのサイズと、２b/2個×ｂビットのサイズと、ｒH個×ｂビットのサイズと、２b/2個×ｂビットのサイズと、１個×ｂビットのサイズと、２b/2−ｒL個×ｂビットのサイズと、ｒL個×ｂビットのサイズとを足し合わせた値となる。すなわち、事前計算テーブルＣ’のサイズは、４×２b/2×ｂビット、即ち、４ｂ×２b/2ビットとなる。
【００６１】
このサイズを、従来の事前計算テーブルＣのサイズｂ×２bビットと比較すると縮小された割合は（４ｂ×２b/2）／（ｂ×２b）＝４／２b/2 である。この割合は、例えばｂ＝４の場合には１であるが、ｂ＞４であればｂの値に応じて１より縮小される。例えば、ｂ＝８の場合には１／４に縮小され、ｂ＝１６の場合には１／６４と顕著に縮小される。
【００６２】
以上により、非特許文献３の方法において、事前計算テーブルのサイズを縮小できる。このため、ＩＣカードのようなリソースに厳しい制約のある装置上へ実装することがより容易となる。
【００６３】
（第１の実施形態）
図１は本発明の第１の実施形態に係る演算装置の構成を示す概略図である。この演算装置１０１は、ＩＣカードなどの計算機の暗号処理部として構成されていて、ハードウェア又はソフトウェアによって暗号処理を行うものである。具体的にはＣＰＵ（中央演算装置）１０２、入出力部１０３、プログラム記憶部１０４、乱数生成部１０５、揮発性メモリ１０６及びバス１０７からなる。この演算装置１０１は、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から演算装置となるコンピュータにインストールされ、演算装置１０１の機能を実現させるためのプログラムが用いられる。ここでは、プログラム記憶部１０４に格納されたプログラムをＣＰＵ１０２で実行する形で、各機能を実現するものとしている。このプログラムは、データ加算のためのサブプログラムを少なくとも含んでいる。
【００６４】
ここで、ＣＰＵ１０２は、プログラム記憶部１０４に格納されたプログラムを実行することにより、図２、図４及び図５に示す処理を実行する機能をもっている。
【００６５】
入出力部１０３は、演算装置１０１内と外部との間のインターフェースであり、例えば、演算対象の数Ａ，ｒを演算装置１０１内に入力する機能と、ＣＰＵ１０２により得られた演算結果を演算装置１０１の外部に出力する機能とをもっている。
【００６６】
プログラム記憶部１０４は、ＣＰＵ１０２から読出可能な記憶装置であり、例えばＲＯＭ（リードオンリーメモリ）又はＥＥＰＲＯＭ（電気的に書換え可能なＲＯＭ）であって、図２、図４及び図５に示す処理のプログラムが記憶されている。なお、プログラム記憶部１０４は、プログラムを外部からインストールして保持する構成でもよい。
【００６７】
乱数生成部１０５は、ＣＰＵ１０２に制御されて乱数を生成するものであり、例えば、ｂビットの乱数γを生成する機能をもっている。なお、乱数生成部１０５は、独立のハードウェアで実現してもよいし、ＣＰＵ１０２とプログラムで実現してもよい。あるいは、乱数生成部１０５を演算装置１０１から省略し、外部で生成した乱数を入出力部１０３から入力する構成としてもよい。
【００６８】
揮発性メモリ１０６は、ＣＰＵ１０２から読出／書込可能な記憶装置であり、例えばＲＡＭ（ランダムアクセスメモリ）であって、例えば、事前計算テーブルＣ’、数Ａ、数ｒ、乱数γ及び加算結果のように、計算に必要なデータ、計算途中のデータ及び計算結果などを格納する。
【００６９】
次に、以上のように構成された演算装置の動作を図２乃至図４を用いて説明する。なお、この動作は、事前計算テーブルの生成処理、及び加算処理（桁上げ伝播処理）の順に説明する。
【００７０】
（事前計算テーブルＣ’の生成処理：図２）
入出力部１０３は、上位（ｋ−１）ｂビットの数Ａ1及び下位ｂビットの数Ａ2からなるｋｂビットの数Ａ（但し、ｂ＞４）と、ｂビットの数ｒと、これらの数Ａ，ｒに対する加算指令とを例えば図示しない暗号処理部から受けると、これらの数Ａ，ｒ及び加算指令をＣＰＵ１０２に入力する。なお、数Ａ，Ａ1，Ａ2は、それぞれ「被算術マスクデータ」とも呼ぶ。
【００７１】
ＣＰＵ１０２は、これらの数Ａ，ｒ及び加算指令を受けると、これらの数Ａ，ｒを加算して上位（ｋ−１）ｂビットの加算結果を得る処理の前に、図３に示す如き、事前計算テーブルＣ’を生成するため、乱数生成部１０５を起動する。
【００７２】
乱数生成部１０５は、ＣＰＵ１０２に起動されると、ｂビットの乱数γを生成する（ステップＳ２１０）。この乱数γはＣＰＵ１０２に送出され、ＣＰＵ１０２から揮発性メモリ１０６に格納される。なお、ステップＳ２１０は、最初に実行する場合を例に挙げて説明したが、これに限らず、乱数γを用いるステップＳ２５０、Ｓ２６０、Ｓ２７０及びＳ２８０よりも前であれば、任意のタイミングで実行可能である。また、以下の各ステップＳ２２０〜Ｓ２８０は、任意の順序で実行可能である。
【００７３】
次に、ＣＰＵ１０２は、（４×２b/2）個のインデックスｙ（但し、０≦ｙ＜４×２b/2）と、当該各インデックスｙに関連付けた各要素データＣ’［ｙ］とを備えた事前計算テーブルＣ’を揮発性メモリ１０６に書き込む。各要素データＣ’［ｙ］は（４×２b/2）個あり、インデックスｙの各々により個別に読出可能なｂビットの値である。但し、この段階では、各要素データＣ’［ｙ］の値は設定されていない。また、インデックスｙは整数である。
【００７４】
ＣＰＵ１０２は、揮発性メモリ１０６内の事前計算テーブルＣ’の１個目から２b/2個目までの要素データＣ’［ｙ］を、０≦ｙ＜２b/2 のインデックスｙと数ｒの上位ｂ／２ビットの数ｒHとに基づいて、以下の値に設定する（ステップＳ２２０〜Ｓ２４０）。
【００７５】
Ｃ’［ｙ］＝２b/2 （０≦ｙ＜２b/2−ｒH−１ ：即ちｙ＋ｒH＜２b/2−１）
Ｃ’［ｙ］＝２×２b/2 （ｙ＝２b/2−ｒH−１ ：即ちｙ＋ｒH＝２b/2−１）
Ｃ’［ｙ］＝３×２b/2 （２b/2−ｒH≦ｙ＜２b/2 ：即ちｙ＋ｒH＞２b/2−１）
ここで、インデックスｙには、後述する上位の被算出マスクデータＡHの値が入力されることを想定しており、上の３通りの要素データＣ’［ｙ］は、それぞれＡH＋ｒH＜２b/2−１、ＡH＋ｒH＝２b/2−１、ＡH＋ｒH≧２b/2の場合に対応している。
【００７６】
上の要素データＣ’［ｙ］の値は、上位の被算出マスクデータＡHの値に応じて次に事前計算テーブルのどの要素データＣ’［ ］を見ればよいのかを示しており、一番上の場合はＣ’［２b/2］、２番目の場合はＣ’［２×２b/2］、３番目の場合はＣ’［３×２b/2］を参照することを表している。
【００７７】
次に、ＣＰＵ１０２は、揮発性メモリ１０６内の事前計算テーブルＣ’の（２b/2＋１）個目から（２×２b/2）個目までの要素データＣ’［ｙ］を、２b/2≦ｙ＜２×２b/2 のインデックスｙと乱数γとに基づいて、以下の値に設定する（ステップＳ２５０）。
【００７８】
Ｃ’［ｙ］＝γ
ここで、ｙ−２b/2には、後述する下位の被算術マスクデータＡLの値が入力されることを想定しており、これはＡH＋ｒH＜２b/2−１の場合に、下位の被算術マスクデータＡLの値に関わらず、乱数γを返すことを示している。
【００７９】
次に、ＣＰＵ１０２は、揮発性メモリ１０６内の事前計算テーブルＣ’の（２×２b/2＋１）個目から（３×２b/2）個目までの要素データＣ’［ｙ］を、２×２b/2≦ｙ＜３×２b/2 のインデックスｙと乱数γと数ｒの下位ｂ／２ビットの数ｒLとに基づいて、以下の値に設定する（ステップＳ２６０、Ｓ２７０）。
Ｃ’［ｙ］＝γ （２×２b/2≦ｙ＜３×２b/2−ｒL：即ちｙ＋ｒL＜２b/2）、
Ｃ’［ｙ］＝γ＋１ （３×２b/2−ｒL≦ｙ＜３×２b/2：即ちｙ＋ｒL≧２b/2）、
ここで、ｙ−２×２b/2には、下位の被算術マスクデータＡLの値が入力されることを想定しており、上の２通りはそれぞれＡL＋ｒL＜２b/2、ＡL＋ｒL≧２b/2の場合に対応している。
【００８０】
最後に、ＣＰＵ１０２は、揮発性メモリ１０６内の事前計算テーブルＣ’の（３×２b/2＋１）個目から（４×２b/2）個目までの要素データＣ’［ｙ］を、３×２b/2≦ｙ＜４×２b/2 のインデックスｙと乱数γとに基づいて、以下の値に設定する（ステップＳ２８０）。
Ｃ’［ｙ］＝γ＋１
ここで、ｙ−３×２b/2には、下位の被算術マスクデータＡLの値が入力されることを想定しており、これはＡH−ｒH≧２b/2の場合に、下位の被算術マスクデータＡLの値に関わらず、乱数付き桁上げ情報γ＋１を返すことを示している。
【００８１】
このように構成した事前計算テーブルＣ’のサイズは４ｂ×２b/2ビットとなる。
【００８２】
図３に、ｂ＝８、ｒ＝０ｘ１９、γ＝０ｘ５６の場合の事前計算テーブルＣ’を示す。事前計算テーブルＣ’は１６進数表記である。図３の配列は、縦の列がインデックスの２b/2の倍数を、横の行が２b/2未満のインデックスを表している。例えば縦のインデックスが１で横のインデックスが５の場合は、事前計算テーブルＣ’の１×２b/2＋５（＝２１）番目の要素を指しており、Ｃ’［２１］＝０ｘ５６となる。
【００８３】
縦のインデックス０の行は、ｒH＝１であるため、２b/2−ｒH−１＝１４である。従って横のインデックスが１３（＝０ｘ０Ｄ）以下のものは事前計算テーブルＣ’の要素は２b/2＝０ｘ１０、１４（＝０ｘ０Ｅ）のものは２×２b/2＝０ｘ２０、１５以上（＝０ｘ０Ｆ）のもの（１５のみ）は３×２b/2＝０ｘ３０となる。
【００８４】
縦のインデックス１の行は、全ての要素データが乱数γ＝０ｘ５６となる。
【００８５】
縦のインデックス３の行は、全ての要素データが乱数付き桁上げ情報γ＋１＝０ｘ５７となる。
【００８６】
縦のインデックス２の行は、ｒL＝９であるため、２b/2−ｒL＝７である。従って、横のインデックスが６以下のものは事前計算テーブルＣ’の要素データが乱数γ＝０ｘ５６となり、横のインデックスが７以上のものは要素データが乱数付き桁上げ情報γ＋１＝０ｘ５７となる。
【００８７】
（加算処理：図４）
始めに、ＣＰＵ１０２は、入力された数Ａから数Ａ1，Ａ2を抽出する。具体的には、被算術マスクデータＡの上位（ｋ−１）ｂビットを上位の被算術マスクデータＡ1とし、下位ｂビットを下位の被算術マスクデータＡ2とする（ステップＳ３１０）。
【００８８】
加算結果Ａ＋ｒを求めるためには、加算結果の下位の被算術マスクデータＡ2←Ａ2＋ｒにおける桁上げ情報（ｂ＋１ビット目）を、加算結果の上位の被算術マスクデータＡ1に伝える必要がある。すなわち加算結果の下位の被算術マスクデータＡ2＋ｒの桁上げ情報がない場合には桁上げ情報“０”の加算Ａ1←Ａ1＋０を、桁上げ情報がある場合には桁上げ情報“１”の加算Ａ1←Ａ1＋１を行う必要がある。但し、桁上げ情報の有無によって加算が異なるため、サイドチャネル解析を阻止する観点から好ましくない。
【００８９】
そのため、ｂビットの乱数γを用い、それぞれ桁上げ情報がない場合には桁上げ情報“０”の加算Ａ1←（Ａ1＋γ）−γを、桁上げ情報がある場合には桁上げ情報“１”の加算Ａ1←（Ａ1＋γ＋１）−γを行う。
【００９０】
ここで、乱数γ又は乱数付き桁上げ情報γ＋１のいずれを加えるかはＡ2＋ｒ＜２b/2であるか否かに対応しており、これは事前計算テーブルＣ’を参照することで判定できる。
【００９１】
そこで、ＣＰＵ１０２は、数Ａ2の上位ｂ／２ビットの数ＡH及び下位ｂ／２ビットの数ＡLを当該数Ａ2から抽出する。すなわち、下位の被算術マスクデータＡ2の上位ｂ／２ビットを上位の被算術マスクデータＡHとし、下位ｂ／２ビットを下位の被算術マスクデータＡLとする（ステップＳ３２０）。なお、これらステップＳ３１０、Ｓ３２０は、説明の便宜上、前述したステップＳ２８０の後に実行したが、これに限らず、ステップＳ２１０〜Ｓ２８０の間の任意のタイミングで実行可能となっている。
【００９２】
次に、ＣＰＵ１０２は、抽出した数ＡHをインデックスｙとして揮発性メモリ１０６内の事前計算テーブルＣ’から第１の要素データＣ’［ＡH］を読み出す。なお、この第１の要素データＣ’［ＡH］を読み出す処理は、前述したステップＳ２８０よりも後に実行される。
【００９３】
ＣＰＵ１０２は、第１の要素データＣ’［ＡH］及び抽出した数ＡLの和をインデックスｙとして揮発性メモリ１０６内の事前計算テーブルＣ’から第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］を読み出す。
【００９４】
ＣＰＵ１０２は、第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］、乱数γ、数Ａ1及び当該数Ａ1のビット数（ｋ−１）ｂに基づいて、
Ａ1＋Ｃ’［Ｃ’［ＡH］＋ＡL］−γ ｍｏｄ ２(k-1)b
を計算することにより、数Ａ1への桁上げを伝播する（ステップＳ３３０、Ｓ３４０）。
【００９５】
上述したように第１の実施形態によれば、ｋｂビットの数Ａとｂビットの数ｒとを互いに加算して上位（ｋ−１）ｂビットの加算結果を得る場合に必要な事前計算テーブルのサイズを縮小することができる。
【００９６】
補足すると、ステップＳ３４０により生成された上位の被算術マスクデータＡ1は、加算結果Ａ＋ｒの上位（ｋ−１）ｂビットとなっており、下位ｂビットからの桁上げ伝播を事前計算テーブルＣ’に基づいて乱数γでマスクしながら実行したため、サイドチャネル解析に対して耐性を有している。さらに事前計算テーブルＣ’のサイズが４ｂ×２b/2ビットであるので、従来の事前計算テーブルＣのサイズｂ×２bビットと比較すると縮小された割合は（４ｂ×２b/2）／（ｂ×２b）＝４／２b/2である。この割合は、例えばｂ＝４の場合には１であるが、ｂ＝８の場合には１／４、ｂ＝１６の場合には１／６４と顕著になる。
【００９７】
また、第１の実施形態においては、非特許文献３の手法を踏襲しているため、サイドチャネル解析に対して耐性を有しつつ、事前計算テーブルサイズを縮小できるため、ＩＣカードのようなリソースに厳しい制約のある装置上へ実装することがより容易となる。
【００９８】
（第２の実施形態）
次に、本発明の第２の実施形態に係る演算装置について説明するが、図９と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【００９９】
本実施形態は、従来の算術的マスクから論理的マスクへの変換方法に第１の実施形態を適用したものである。演算装置１０１の構成のうち、ハードウェア構成は、図１に示した構成と同一であり、ソフトウェア構成は、プログラム記憶部１０４内に図５に示す処理を実行するためのプログラムが付加された構成となっている。
【０１００】
当該付加されたプログラムは、算術的マスクから論理的マスクへの変換処理を実行するためのプログラムであり、従来の図９に示したステップＳ１６２に代えて、後述するステップＳ１６２ａ（第１の実施形態の事前計算テーブルＣ’を用いる処理）を実行する内容となっている（なお、ステップＳ１６２ａ以外のステップは、従来の図９に示した各ステップと同様に実行される。）。
【０１０１】
補足すると、図５に示すステップＳ１６１〜Ｓ１６３は、第１の実施形態のステップＳ３１０〜Ｓ３４０に相当し、遅くともステップＳ１６２ａを実行する前に、第１の実施形態のステップＳ２１０〜Ｓ２８０（事前計算テーブルＣ’の生成処理）が予め実行される。なお、通常は、図５に示す最初のステップＳ１１０よりも前に、予めステップＳ２１０〜Ｓ２８０が実行される。
【０１０２】
いずれにしても図５に示す処理の実行に伴い、揮発性メモリ１０６は、第１の実施形態の記憶内容に加え、第２の事前計算テーブルＧ、整数ｍ及び被論理マスクデータｘ’を記憶するように用いられる。ここで、第２の事前計算テーブルＧは、図８に示したように、０から２b−１までの２b個のインデックスＩと、当該各インデックスＩにより個別に読出可能な２b個の要素データＧ［Ｉ］＝（（Ｉ＋ｒ） ｍｏｄ ２b）＾ｒ とを備えている。
【０１０３】
次に、以上のように構成された演算装置の動作を図５を用いて説明する。
【０１０４】
なお、ＣＰＵ１０２は、前述したステップＳ２１０〜Ｓ２８０の処理により、第１の実施形態に述べた事前計算テーブルＣ’を予め生成して揮発性メモリ１０６に書き込んでいるとする。また同様に、ＣＰＵ１０２は、０から２b−１までの２b個のインデックスＩ、乱数ｒ及びビット数ｂに基づいて第２の事前計算テーブルＧを生成し、当該第２の事前計算テーブルＧを揮発性メモリ１０６に書き込む。
【０１０５】
入出力部１０３においては、上位（ｋ−１）ｂビットの数Ａ1及び下位ｂビットの数Ａ2からなるｋｂビットの数Ａと、上位（ｍ−１）ｂビットの数Ｒ1及び下位ｂビットの数Ｒ2からなるｍｂビットの数Ｒとを演算装置１０１内に入力して揮発性メモリ１０６に書き込む。
【０１０６】
続いて、ＣＰＵ１０２は、整数ｍ及び被論理マスクデータｘ’をそれぞれｍ＝ｋ、ｘ’＝０に設定し、これら整数ｍ及び被論理マスクデータｘ’を揮発性メモリ１０６に書き込む（ステップＳ１１０〜Ｓ１２０）。
【０１０７】
ＣＰＵ１０２は、被算術マスクデータとしての数Ａから乱数ｒをｍｏｄ ２ｍｂ の下で減算する（ステップＳ１３０）。この減算により、減算結果Ａ←Ａ−ｒ ｍｏｄ ２ｍｂが得られる。
【０１０８】
この減算の後、ＣＰＵ１０２は、入力された数Ｒから上位（ｍ−１）ｂビットの数Ｒ1及び下位ｂビットの数Ｒ2を抽出する（ステップＳ１４０）。
【０１０９】
この抽出の後、ＣＰＵ１０２は、数Ａに数Ｒ2をｍｏｄ ２ｍｂ の下で加算する（ステップＳ１５０）。この加算により、加算結果Ａ←Ａ−Ｒ2 ｍｏｄ ２ｍｂが得られる。
【０１１０】
この加算の後、ＣＰＵ１０２は、揮発性メモリ１０６内の整数ｍについて、ｍ＝１か否かを判定する。
【０１１１】
ＣＰＵ１０２は、判定の結果、ｍ＝１の場合には加算後の数ＡをインデックスＩとして、揮発性メモリ１０６内の事前計算テーブルＧから要素データＧ［Ａ］を読み出す。しかる後、ＣＰＵ１０２は、この要素データＧ［Ａ］、数Ｒ2及び乱数ｒに基づいて、上位の被論理マスクデータｘ’1を、ｘ’1＝（Ｇ［Ａ］＾Ｒ2）＾ｒ の値に計算する手段（ステップＳ１７０〜Ｓ１８０）。
【０１１２】
ＣＰＵ１０２は、この計算により得られた上位の被論理マスクデータｘ’1を、揮発性メモリ１０６内の被論理マスクデータｘ’の最上位ｂビットに配置する（ステップＳ１９０）。
【０１１３】
一方、ステップＳ１６０による判定の結果、ｍ＞１の場合には、前述したステップＳ３１０〜Ｓ３４０と同様の処理として、ステップＳ１６１、Ｓ１６２ａ及びＳ１６３を順次実行する。
【０１１４】
詳しくは、ＣＰＵ１０２は、ステップＳ１５０による加算後の数Ａから数Ａ1，Ａ2を抽出する。具体的には、被算術マスクデータＡの上位（ｋ−１）ｂビットを上位の被算術マスクデータＡ1とし、下位ｂビットを下位の被算術マスクデータＡ2とする（ステップＳ１６１）。
【０１１５】
次に、ＣＰＵ１０２は、従来のステップＳ１６２とは異なり、以下のステップＳ１６２ａを実行する。
【０１１６】
すなわち、ＣＰＵ１０２は、前述同様に、数Ａ2の上位ｂ／２ビットの数ＡH及び下位ｂ／２ビットの数ＡLを当該数Ａ2から抽出する。
【０１１７】
次に、ＣＰＵ１０２は、抽出した数ＡHをインデックスｙとして揮発性メモリ１０６内の事前計算テーブルＣ’から第１の要素データＣ’［ＡH］を読み出す。
【０１１８】
また、ＣＰＵ１０２は、第１の要素データＣ’［ＡH］と抽出した数ＡLとの和をインデックスｙとして揮発性メモリ１０６内の事前計算テーブルＣ’から第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］を読み出す。
【０１１９】
ＣＰＵ１０２は、第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］、乱数γ、数Ａ1及び当該数Ａ1のビット数（ｍ−１）ｂに基づいて、
Ａ1←Ａ1＋Ｃ’［Ｃ’［ＡH］＋ＡL］−γ ｍｏｄ ２(m-1)b
の計算により、数Ａ1への桁上げを伝播する（ステップＳ１６２ａ、Ｓ１６３）。
【０１２０】
次に、ＣＰＵ１０２は、ステップＳ１６１で抽出した数Ａ2をインデックスＩとして、揮発性メモリ１０６内の事前計算テーブルＧから要素データＧ［Ａ2］を読み出す。しかる後、ＣＰＵ１０２は、この要素データＧ［Ａ2］、数Ｒ2及び乱数ｒに基づいて、下位の被論理マスクデータｘ’2を、ｘ’2＝（Ｇ［Ａ2］＾Ｒ2）＾ｒ の値に計算する（ステップＳ１６４、Ｓ１６５）。
【０１２１】
ＣＰＵ１０２は、この計算により得られた下位の被論理マスクデータｘ’2を、揮発性メモリ１０６内の被論理マスクデータｘ’の下位（ｋ−ｍ）ｂビット目に、当該下位の被論理マスクデータｘ’2の最下位ビットが合うように配置する（ステップＳ１６６）。
【０１２２】
この配置の後、ＣＰＵ１０２は、揮発性メモリ１０６内の整数ｍを、ｍ＝ｍ−１と更新してステップＳ１３０の処理に戻る（ステップＳ１６７）。
以下、ＣＰＵ１０２は、ステップＳ１３０以降の処理を再実行する。
【０１２３】
上述したように第２の実施形態によれば、従来の算術的マスクから論理的マスクへの変換方法に第１の実施形態を適用した構成により、被算術マスクデータを被論理マスクデータに変換する場合に必要な事前計算テーブルのサイズを縮小することができる。
【０１２４】
補足すると、第２の実施形態においては、第１の実施形態と同様に、非特許文献３の手法を踏襲しているためサイドチャネル解析に対して耐性を有しつつ、事前計算テーブルサイズをより小さくできるため、ＩＣカードのようなリソースに厳しい制約のある装置上へ実装することがより容易となる。
【０１２５】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１２６】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１２７】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１２８】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１２９】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１３０】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１３１】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１３２】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【符号の説明】
【０１３３】
１０１…演算装置、１０２…ＣＰＵ、１０３…入出力部、１０４…プログラム記憶部、１０５…乱数生成部、１０６…揮発性メモリ、１０７…バス。
【技術分野】
【０００１】
本発明は、例えば、サイドチャネル解析への耐性を持たせるように算術的マスクをした被算術マスクデータを、論理的マスクをした被論理マスクデータに変換する場合に、必要な事前計算テーブルのサイズを縮小し得る演算装置及びプログラムに関する。
【背景技術】
【０００２】
近年の情報通信技術にとって、暗号技術は欠かせない技術となってきている。この種の暗号化技術には、例えば通信の暗号化技術であるＳＳＬ（Secure Socket Layer）や、メッセージの改ざんの有無を検出可能な電子署名などがある。これらはＰＫＩ（Public Key Infrastructure：公開鍵基盤）の一部として、社会の電子化を支えている。
【０００３】
しかしながら、暗号技術に対する攻撃手法も高度化してきている。その中でも、暗号プロセッサの処理時間や消費電力を測定し、測定結果から暗号プロセッサ内部の秘密情報を解析するというサイドチャネル解析が現実的な脅威となってきている。代表的なサイドチャネル解析としては、タイミング解析及び電力解析が知られている。
【０００４】
電力解析の例として、非特許文献１に記載のＤＥＳ（Data Encryption Standard）に対する解析方法を図面を用いて説明する。
【０００５】
図７はＤＥＳ暗号装置における最終１６段目のデータ変換部を示す模式図である。
【０００６】
１６段目のデータ変換部においては、２つの３２ビットの入力データＬ15、Ｒ15及び４８ビットの鍵データＫ16が入力されると、データ変換処理が実行され、２つの３２ビットの出力データＬ16、Ｒ16が出力される。
【０００７】
この出力データＬ16、Ｒ16をビット転置ＩＰ-1した結果がＤＥＳ暗号装置から出力される暗号文となる。ここで、暗号文及びビット転置ＩＰ-1は、それぞれ攻撃者に既知であるため、出力データＬ16、Ｒ16も攻撃者に既知となる。
【０００８】
１６段目のデータ変換部では、３２ビットの入力データＲ15をＥ転置により４８ビットのデータに拡大する。拡大後のデータは４８ビットの鍵データＫ16との排他的論理和が取られる。排他的論理和後の４８ビットのデータは６ビットの８個の分割データに分割され、各分割データがそれぞれＳボックス（S-box）Ｓ1，Ｓ2，…，Ｓ8に入力される。
【０００９】
各Ｓボックスは６ビット入力４ビット出力であり、全部で３２ビットの出力データが得られる。この３２ビットの出力データは、Ｐ転置により別の３２ビットのデータに変換された後、入力データＬ15との排他的論理和が取られて一方の出力データＬ16となる。他方の出力データＲ16は、入力データＲ15がそのまま出力されたものである。
【００１０】
このようなデータ変換処理において、攻撃者に未知のデータは４８ビットの鍵データＫ16のみである。攻撃者は、この４８ビットの値を、１６段目のデータ変換処理を実行中のＤＥＳ暗号装置の消費電力を解析して求める。
【００１１】
具体的には、攻撃者は入力平文Ｍiを取り替えながら１，０００サンプルのＤＥＳ処理に対する消費電力波形ｖi（ｔ）を収集する。ここで、ｔは離散的な時刻を表し、iはサンプル番号（但し、０≦ i ≦９９９）を表す。
【００１２】
１６段目のある１つのＳボックスｓの出力１ビットをターゲットビットとする。このＳボックスｓの６ビットの入力データｃは、出力データＬ16から逆にたどることで導出可能である。Ｓボックスの入力データｃとしては、入力データｃ以外に、入力データｃと排他的論理和される６ビットの部分鍵ｋjがある。この部分鍵ｋjを未知変数として、ターゲットとなるＳボックス出力１ビットをｓi（ｋj，ｃi）と書く。
【００１３】
収集した消費電力波形を基に、差分平均トレースＴj（ｔ）を次の式により計算する。
【数１】
【００１４】
部分鍵ｋjとして６ビット６４通りの全ての場合について差分平均トレースＴj（ｔ）を計算すると、６４通りの内の一つの部分鍵ｋjは、実際に使われている部分鍵ｋjと一致しており、その時の差分平均トレースＴj（ｔ）は値の偏りを示す。それ以外の６３通りの部分鍵の場合には部分平均トレースＴj（ｔ）は偏らない。この偏り特性により、６ビットの部分鍵ｋjを特定可能となっている。
【００１５】
この操作を他の７つのＳボックスｓにも適用することで４８ビットの部分鍵Ｋ16を見出すことが可能である。
【００１６】
このような電力解析においては、攻撃者が予想した未知変数ｋjの値と消費電力ｖi（ｔ）に相関があることが効いている。このことは未知変数の値と測定時間との相関を見るタイミング解析でも同様である。
【００１７】
従って、逆にこのような相関をなくせば、サイドチャネル解析から秘密情報の漏洩を阻止可能である。そこで、暗号装置が処理するデータと攻撃者が予想したデータとの相関を無くすため、暗号装置が処理するデータに乱数をマスクする手法が知られている。
【００１８】
マスク方法としては、主に論理的マスクと算術的マスクの２種類があり、暗号アルゴリズムを構成する演算を基に、いずれのマスクを使用するかを決定する。例えば、論理演算から構成される暗号アルゴリズムには論理的マスクを使用し、算術演算から構成される暗号アルゴリズムには算術マスクを使用する。マスクの際に用いる演算と暗号アルゴリズムの演算は、可換とすることが効率的に良い。すなわち、マスクされたデータに暗号アルゴリズムの演算を施す場合には、最後にマスクを外した後の演算結果が、最初からマスクをしなかった場合の演算結果と同じになるように、マスクの際に用いる演算を定める。一般に、共通鍵暗号方式は論理的マスクを使用し、公開鍵暗号方式は算術的マスクを使用することが多い。
【００１９】
共通鍵暗号方式やハッシュ関数の中には、１つのアルゴリズムの中で論理演算と算術演算の両方を用いるアルゴリズムが存在する。例えば共通鍵暗号方式ではＩＤＥＡ（International Data Encryption Algorithm）、ＳＥＥＤ、ハッシュ関数ではＳＨＡ−１（Secure Hash Algorithm - 1）などがある。これらのアルゴリズムにおいてデータをマスクするには、暗号アルゴリズムで論理演算を用いる部分では論理的マスクをする一方、算術演算を用いる部分では算術的マスクをする必要がある。
【００２０】
これらのアルゴリズムでは、処理単位（ワード）をｗビットとしたとき、ｗビットのデータｘをｗビットの数Ｒでマスクするには、論理的マスクの場合は排他的論理和を用いて、次式の演算を実行する。
【００２１】
ｘ’＝ｘ＾Ｒ （但し、＾は排他的論理和を表す記号）
算術的マスクの場合は剰余付き減算を用いて、次式の演算を実行する。
Ａ＝ｘ−Ｒ ｍｏｄ ２ｗ
上の暗号アルゴリズムの例ではｗ＝３２ビットである。
【００２２】
従って、暗号アルゴリズムにおける演算列において論理演算から算術演算に変わる場面では、論理的マスクが施されたデータ（以下、被論理マスクデータという）ｘ’から算術的マスクが施されたデータ（以下、被算術マスクデータという）Ａへデータを変換する必要がある。同様に、算術演算から論理演算に変わる場面では、被算術マスクデータＡから被論理マスクデータｘ’へ、データを変換する必要がある。
【００２３】
例えば被論理マスクデータｘ’から被算術マスクデータＡに変換する最も簡単な方法は、（ｘ’＾Ｒ）−Ｒ ｍｏｄ ２ｗ を演算する方式である。但し、この方式は、ｘ’＾Ｒ＝ｘであるから、マスクされていない状態のデータｘが演算中に出現するので、望ましくない。
【００２４】
データに常にマスクをつけた状態で被論理マスクデータｘ’と被算術マスクデータＡを変換する方法として、非特許文献２，３が知られている。非特許文献２では、被論理マスクデータｘ’から被算術マスクデータＡへ変換する方法と、被算術マスクデータＡから被論理マスクデータｘ’へ変換する方法が提案されている。後者の方法は効率が低いため、事前計算テーブルを用いて高速化を図る方法が非特許文献３で提案されている。
【００２５】
図８乃至図１０を用いて、非特許文献３での被算術マスクデータＡから被論理マスクデータｘ’への変換方法を説明する。演算を行う単位をｂビットとする。簡単のため、ｂはｗの約数であるとし、ある整数ｋにより、ｗ＝ｋ×ｂとかけるものとする。
【００２６】
始めに、論理的マスク及び算術的マスクがｂビットの場合（すなわちｗ＝ｂ、ｋ＝１）の事前計算テーブルＧを構成する。０から２b−１までの各整数Ｉに対して、事前計算テーブルを次式で定義する。
【００２７】
Ｇ［Ｉ］＝（（Ｉ＋ｒ） ｍｏｄ ２b）＾ｒ
ここで、便宜上、ｂビットの乱数をｒと記載している。ｗ＝ｂの場合、上記数Ｒとの関係はＲ＝ｒである。事前計算テーブルＧは、２b個の要素データからなるテーブルであり、各要素データがｂビットである。被算術マスクデータＡは、事前計算テーブルＧの要素データＧ［Ａ］を求めることで被論理的マスクｘ’に変換可能となっている。その理由は以下の通りである。
【００２８】
Ｇ［Ａ］＝（（Ａ＋ｒ） ｍｏｄ ２b）＾ｒ
＝（（ｘ−ｒ）＋ｒ ｍｏｄ ２ｗ）＾ｒ
＝（ｘ ｍｏｄ ２ｗ）＾ｒ
＝ｘ＾ｒ
＝ｘ’
図８に、ｗ＝ｂ＝４、ｒ＝３の場合の事前計算テーブルＧを示す。図の配列は、左側から順にＧ［０］，Ｇ［１］，…，Ｇ［１５］の値を１６進数表記で示している。例えばＧ［９］＝０ｘＦである。
【００２９】
図９にｋ＞１（すなわちｗ＞ｂ）の場合に、非特許文献３による被算術マスクデータＡから被論理マスクデータｘ’に変換するアルゴリズムを示す。このアルゴリズムはｗ＝ｋ×ｂビットの被算術マスクデータＡと数Ｒを入力したとき、ｗビットの被論理マスクデータｘ’を出力するアルゴリズムである。
【００３０】
始めに、整数ｍ及び被論理マスクデータｘ’をそれぞれｍ＝ｋ、ｘ’＝０とする（ステップＳ１１０、Ｓ１２０）。
【００３１】
次に、被算術マスクデータＡから乱数ｒをｍｏｄ ２ｍｂ の下で減算する（ステップＳ１３０）。
【００３２】
数ＲをＬＳＢ（Least Significant Bit：最下位ビット）からｂビット目の値で上位の数Ｒ1と下位の数Ｒ2に分割する（ステップＳ１４０）。すなわち上位の数Ｒ1は数Ｒの上位（ｍ−１）ｂビットであり、下位の数Ｒ2は下位ｂビットである。
【００３３】
被算術マスクデータＡに下位の数Ｒ2をｍｏｄ ２ｍｂ の下で加算する（ステップＳ１５０）。
【００３４】
次に、整数ｍについて、ｍ＝１か否かを判断する（ステップＳ１６０）。ｍ＝１の場合は上位の被論理マスクデータｘ’1を次式の通り計算する（ステップＳ１７０、Ｓ１８０）。
【００３５】
ｘ’1＝（Ｇ［Ａ］＾Ｒ2）＾ｒ
しかる後、得られた上位の被論理マスクデータｘ’1を被論理マスクデータｘ’の最上位ｂビットに配置して（ステップＳ１９０）アルゴリズムを終了する。
【００３６】
ｍ＞１の場合は、以下の処理を行う。
【００３７】
被算術マスクデータＡを数Ｒと同様に上位の被算術マスクデータＡ1と、下位の被算術マスクデータＡ2とに分割する（ステップＳ１６１）。
【００３８】
ステップＳ１３０とステップＳ１５０による桁上げ（Ａ2＋ｒにより生じるｂ＋１ビット目の値）を上位の被算術マスクデータＡ1に対応させるため、次式を計算する（ステップＳ１６２、Ｓ１６３）。なお、本明細書中、「桁上げ」は「キャリー」に読み替えてもよい。
【００３９】
Ａ1＝（Ａ1＋Ｃ［Ａ2］）−γ ｍｏｄ ２(m-1)b
続いて、下位の被論理マスクデータｘ’2を次式に示すように計算する（ステップＳ１６４、Ｓ１６５）。
【００４０】
ｘ’2＝（Ｇ［Ａ2］＾Ｒ2）＾ｒ
しかる後、下位の被論理マスクデータｘ’2を、被論理マスクデータｘ’の下位（ｋ−ｍ）ｂビット目に、当該下位の被論理マスクデータｘ’2の最下位ビットＬＳＢが合うように配置する（ステップＳ１６６）。
【００４１】
しかる後、整数ｍを、ｍ＝ｍ−１と更新し（ステップＳ１６７）、ステップＳ１３０からくり返す。
【００４２】
上記アルゴリズムにおいて、ステップＳ１３０とステップＳ１５０における下位桁からの桁上げ（キャリー）を調整する際に、桁上げ情報をマスクするために事前計算テーブルＣ及びｂビットの乱数γを利用している。事前計算テーブルＣは、０から２b−１までの各整数Ｉに対し、次のように定義される。
【００４３】
Ｃ［Ｉ］＝γ （Ｉ＋ｒ＜２bのとき）
Ｃ［Ｉ］＝γ＋１（Ｉ＋ｒ≧２bのとき）
ここで、事前計算テーブルＣは、２b個の要素データからなるテーブルであり、各要素データがｂビットである。
【００４４】
図１０に、ｂ＝４、ｒ＝３、γ＝９の場合の事前計算テーブルＣを示す。図の配列は、左側から順にＣ［０］，Ｃ［１］，…，Ｃ［１５］の値を１６進数表記で示している。例えばＣ［０ｘＥ］＝０ｘＡである。
【先行技術文献】
【非特許文献】
【００４５】
【非特許文献１】L. Goubin, J. Patarin, “DES and Differential Power Analysis - The Duplication Method”, CHES ’99, LNCS 1717, pp.158-172, 1999
【非特許文献２】L. Goubin, “A Sound Method for Switching between Boolean and Arithmetic Masking”, CHES 2001, LNCS 2162, pp.3-15, 2001
【非特許文献３】J-S, Coron, A. Tchulkine, “A New Algorithm for Switching from Arithmetic to Boolean Masking”, CHES 2003, LNCS 2779, pp.89-97, 2003
【発明の概要】
【発明が解決しようとする課題】
【００４６】
しかしながら、以上のような非特許文献３における被算術マスクデータＡから被論理マスクデータｘ’への変換方法では、事前計算テーブルＧ，Ｃを格納する領域として、２つのｂ×２bビットの格納領域が必要となる。例えばｂ＝４の場合には１２８ビット（＝１６バイト）の格納領域、ｂ＝８の場合には４，０９６ビット（＝５１２バイト）の格納領域でよいが、ｂ＝１６の場合には２，０９７，１５２ビット（＝２６２，１４４バイト）の格納領域が必要となり、非現実的である。
【００４７】
従って、実際にはｂ＝８程度の場合の格納領域が妥当な大きさではあるが、それでもＩＣカードのような記憶容量の小さい装置に実装する際には、５１２バイトの事前計算テーブルＧ，Ｃでも、リソースを圧迫するか、あるいは実装できないという問題がある。
【００４８】
本発明者の検討によれば、この問題は、ｋｂビットの数Ａとｂビットの数ｒとを互いに加算して上位（ｋ−１）ｂビットの加算結果を得る場合に必要な事前計算テーブルのサイズを縮小できれば、解消できると考えられる。すなわち、ステップＳ１３０とステップＳ１５０による桁上げ（Ａ2＋ｒにより生じるｂ＋１ビット目の値）を上位の被算術マスクデータＡ1に対応させる場合に必要な事前計算テーブルＣのサイズを縮小できれば、この問題を解消できると考えられる。
【００４９】
本発明は上記実情を考慮してなされたもので、ｋｂビットの数Ａとｂビットの数ｒとを互いに加算して上位（ｋ−１）ｂビットの加算結果を得る場合に必要な事前計算テーブルのサイズを縮小し得る演算装置及びプログラムを提供することにある。
【課題を解決するための手段】
【００５０】
本発明の一つの局面は、上位（ｋ−１）ｂビットの数Ａ1及び下位ｂビットの数Ａ2からなるｋｂビットの数Ａ（但し、ｂ＞４）と、ｂビットの数ｒとを加算して上位（ｋ−１）ｂビットの加算結果を得る処理の前に、（４×２b/2）個のインデックスｙ（但し、０≦ｙ＜４×２b/2）の各々により個別に読出可能な（４×２b/2）個のｂビットの要素データＣ’［ｙ］を備えた事前計算テーブルＣ’を生成し、前記加算する処理中に、前記数Ａ2と前記数ｒとの加算結果から前記数Ａ1への桁上げを前記事前計算テーブルＣ’に基づいて伝播可能な演算装置であって、前記ｂビットの乱数γを生成する手段と、前記各インデックスｙと、当該各インデックスｙに関連付けた各要素データＣ’［ｙ］とを備えた事前計算テーブルＣ’を記憶するための記憶手段と、前記記憶手段内の事前計算テーブルＣ’の１個目から２b/2個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記数ｒの上位ｂ／２ビットの数ｒHとに基づいて、Ｃ’［ｙ］＝２b/2 （但し、０≦ｙ＜２b/2−ｒH−１ ）、Ｃ’［ｙ］＝２×２b/2 （但し、ｙ＝２b/2−ｒH−１ ）、Ｃ’［ｙ］＝３×２b/2 （但し、２b/2−ｒH≦ｙ＜２b/2 ）、の値に設定する手段と、前記記憶手段内の事前計算テーブルＣ’の（２b/2＋１）個目から（２×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、Ｃ’［ｙ］＝γ （但し、２b/2≦ｙ＜２×２b/2）、の値に設定する手段と、前記記憶手段内の事前計算テーブルＣ’の（２×２b/2＋１）個目から（３×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γと前記数ｒの下位ｂ／２ビットの数ｒLとに基づいて、Ｃ’［ｙ］＝γ （但し、２×２b/2≦ｙ＜３×２b/2−ｒL）、Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2−ｒL≦ｙ＜３×２b/2）、の値に設定する手段と、前記記憶手段内の事前計算テーブルＣ’の（３×２b/2＋１）個目から（４×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2≦ｙ＜４×２b/2）の値に設定する手段と、前記数Ａから前記数Ａ1及び前記数Ａ2を抽出する第１抽出手段と、前記数Ａ2の上位ｂ／２ビットの数ＡH及び下位ｂ／２ビットの数ＡLを当該数Ａ2から抽出する第２抽出手段と、前記（４×２b/2）個の要素データＣ’［ｙ］の値を設定した後、前記抽出した数ＡHをインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第１の要素データＣ’［ＡH］を読み出す第１読出手段と、前記第１の要素データＣ’［ＡH］と前記抽出した数ＡLとの和をインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］を読み出す第２読出手段と、前記第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］、前記乱数γ、前記数Ａ1及び当該数Ａ1のビット数（ｋ−１）ｂに基づいて、Ａ1＋Ｃ’［Ｃ’［ＡH］＋ＡL］−γ ｍｏｄ ２(k-1)b を計算することにより、前記数Ａ1への桁上げを伝播する桁上げ伝播手段と、を備えた演算装置である。
【００５１】
なお、本発明の一つの局面は、装置として表現したが、装置に限らず、方法、プログラム、プログラムを記憶したコンピュータ読み取り可能な記憶媒体として表現してもよい。
【００５２】
（作用）
本発明の一つの局面においては、ｋｂビットの数Ａとｂビットの乱数ｒとの加算について、数Ａの下位ｂビットの数Ａ2の上位ｂ／２ビットの値ＡHと乱数ｒの上位ｂ／２ビットの値ｒHとの和ＡH＋ｒHと、数Ａ2の下位ｂ／２ビットの値ＡLと乱数ｒの下位ｂ／２ビットの値ｒLとの和ＡL＋ｒLとに基づいて、Ａ2＋ｒの桁上げの有無を示すように事前計算テーブルＣ’の要素データを設定したので、非特許文献３に記載の方法に比べ、ｋｂビットの数Ａとｂビットの数ｒとを互いに加算して上位（ｋ−１）ｂビットの加算結果を得る場合に必要な事前計算テーブルのサイズを縮小することができる。
【発明の効果】
【００５３】
以上説明したように本発明によれば、ｋｂビットの数Ａとｂビットの数ｒとを互いに加算して上位（ｋ−１）ｂビットの加算結果を得る場合に必要な事前計算テーブルのサイズを縮小できる。
【図面の簡単な説明】
【００５４】
【図１】本発明の第１の実施形態に係る演算装置の概略図である。
【図２】同実施形態における事前計算テーブルＣの生成手順を示すフローチャートである。
【図３】同実施形態における事前計算テーブルＣの一例を示す図である。
【図４】同実施形態における加算手順を示すフローチャートである。
【図５】本発明の第２の実施形態に係る演算装置に適用された算術的マスクから論理的マスクへの変換手順を示すフローチャートである。
【図６】本発明の概要を説明するためのフローチャートである。
【図７】一般的なＤＥＳのデータ変換部の１６段目を示す図である。
【図８】従来の事前計算テーブルＧの一例を示す図である。
【図９】従来の算術的マスクから論理的マスクへの変換手順を示すフローチャートである。
【図１０】従来の事前計算テーブルＣの一例を示す図である。
【発明を実施するための形態】
【００５５】
以下、本発明の各実施形態について図面を用いて説明するが、その前に本発明の概要を図６を参照して述べる。
事前計算テーブルＣ’を生成するときに、０から２b−１までの範囲内の整数Ａに対して、整数ｒでマスクした値Ａ＋ｒが２bより小さいか否かの判断（桁上げの有無の判断）を、上位ｂ／２ビットと下位ｂ／２ビットに分けて行う。
【００５６】
ここで、整数Ａの上位ｂ／２ビットの数をＡH、下位ｂ／２ビットの数をＡLと表すことにする。整数ｒについても同様に、上位ｂ／２ビットの数をｒH、下位ｂ／２の数をｒLと表す（例、ｒ＝0x19の場合、ｒH＝１、ｒL＝９）。
【００５７】
例えば、上位ｂ／２ビット同士ＡH，ｒHの加算結果がＡH＋ｒH＜２b/2−１であれば、ＡL，ｒLの値によらず、Ａ＋ｒ＜２bである（即ち、桁上げ無し）と判断できる。そのため、この桁上げ無しの場合には事前計算テーブルＣ’を参照したときに値γ（乱数）が読み出されるように事前計算テーブルＣ’を生成する。この場合は、具体的には、数ＡHをインデックスｙとしてｂビットの値Ｃ’［ＡH］を得る場合（但し、０≦ｙ＜２b/2−ｒH−１）の（２b/2−ｒH−１）個×ｂビットのサイズ（例、図３の０行目の１４個の値Ｃ’［0x00］，…，Ｃ’［0x1D］＝0x10，…，0x10のサイズ）と、このインデックスｙにより得られた値Ｃ’［ＡH］に数ＡLを加算した値（0x10＋ＡL）をインデックスｙとしてｂビットの値γを得る場合（但し、２b/2≦ｙ＜２×２b/2）の２b/2個×ｂビットのサイズ（例、図３の１行目の１６個の値Ｃ’［0x10］〜Ｃ’［0x1F］＝0x56，…，0x56のサイズ）とを必要とする。
【００５８】
次に、上位ｂ／２ビット同士ＡH，ｒHの加算結果がＡH＋ｒH≧２b/2 であれば、ＡL，ｒLの値によらず、Ａ＋ｒ≧２bである（即ち、桁上げ有り）と判断できる。そのため、この桁上げ有りの場合には事前計算テーブルＣ’を参照したときに値γ＋１（乱数付き桁上げ情報）が読み出されるように事前計算テーブルＣ’を生成する。この場合は、具体的には、数ＡHをインデックスｙとしてｂビットの値Ｃ’［ＡH］を得る場合（但し、２b/2−ｒH≦ｙ＜２b/2 ）のｒH個×ｂビットのサイズ（例、図３の０行目の１個の値Ｃ’［0x0F］＝0x30のサイズ）と、このインデックスｙにより得られた値Ｃ’［ＡH］に数ＡLを加算した値（0x30＋ＡL）をインデックスｙとしてｂビットの値γを得る場合（但し、３×２b/2≦ｙ＜４×２b/2）の２b/2個×ｂビットのサイズ（例、図３の３行目の１６個の値Ｃ’［0x30］，…，Ｃ’［0x3F］＝0x57，…，0x57のサイズ）とを必要とする。
【００５９】
最後に、上位ｂ／２ビット同士ＡH，ｒHの加算結果がＡH＋ｒH＝２b/2−１のときには、下位ｂ／２ビット同士ＡL，ｒLの加算結果がＡL＋ｒL＜２b/2であればＡ＋ｒ＜２bである（即ち、桁上げ無し）と判断でき、そうでなければＡ＋ｒ≧２bである（即ち、桁上げ有り）と判断できる。そのため、事前計算テーブルＣ’を参照したときに、桁上げ無しの場合には値γが読み出され、桁上げ有りの場合には値γ＋１が読み出されるように事前計算テーブルＣ’を生成する。これらの場合には、具体的には、数ＡHをインデックスｙとしてｂビットの値Ｃ’［ＡH］を得る場合（但し、ｙ＝２b/2−ｒH−１）の１個×ｂビットのサイズ（例、図３の０行目の１個の値Ｃ’［0x0E］＝0x20のサイズ）と、このインデックスｙにより得られた値Ｃ’［ＡH］に数ＡLを加算した値（0x20＋ＡL）をインデックスｙとしてｂビットの値γを得る場合（但し、２×２b/2≦ｙ＜３×２b/2−ｒL）の（２b/2−ｒL）個×ｂビットのサイズ（例、図３の２行目の７個の値Ｃ’［0x20］，…，Ｃ’［0x26］＝0x56，…，0x56のサイズ）と、値Ｃ’［ＡH］に数ＡLを加算した値（0x20＋ＡL）をインデックスｙとしてｂビットの値γ＋１を得る場合（但し、３×２b/2−ｒL≦ｙ＜３×２b/2）のｒL個×ｂビットのサイズ（例、図３の２行目の９個の値Ｃ’［0x27］，…，Ｃ’［0x2F］＝0x57，…，0x57のサイズ）とを必要とする。
【００６０】
このような事前計算テーブルＣ’のサイズは、これら全てのサイズを足し合わせた値となり、具体的には、（２b/2−ｒH−１）個×ｂビットのサイズと、２b/2個×ｂビットのサイズと、ｒH個×ｂビットのサイズと、２b/2個×ｂビットのサイズと、１個×ｂビットのサイズと、２b/2−ｒL個×ｂビットのサイズと、ｒL個×ｂビットのサイズとを足し合わせた値となる。すなわち、事前計算テーブルＣ’のサイズは、４×２b/2×ｂビット、即ち、４ｂ×２b/2ビットとなる。
【００６１】
このサイズを、従来の事前計算テーブルＣのサイズｂ×２bビットと比較すると縮小された割合は（４ｂ×２b/2）／（ｂ×２b）＝４／２b/2 である。この割合は、例えばｂ＝４の場合には１であるが、ｂ＞４であればｂの値に応じて１より縮小される。例えば、ｂ＝８の場合には１／４に縮小され、ｂ＝１６の場合には１／６４と顕著に縮小される。
【００６２】
以上により、非特許文献３の方法において、事前計算テーブルのサイズを縮小できる。このため、ＩＣカードのようなリソースに厳しい制約のある装置上へ実装することがより容易となる。
【００６３】
（第１の実施形態）
図１は本発明の第１の実施形態に係る演算装置の構成を示す概略図である。この演算装置１０１は、ＩＣカードなどの計算機の暗号処理部として構成されていて、ハードウェア又はソフトウェアによって暗号処理を行うものである。具体的にはＣＰＵ（中央演算装置）１０２、入出力部１０３、プログラム記憶部１０４、乱数生成部１０５、揮発性メモリ１０６及びバス１０７からなる。この演算装置１０１は、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から演算装置となるコンピュータにインストールされ、演算装置１０１の機能を実現させるためのプログラムが用いられる。ここでは、プログラム記憶部１０４に格納されたプログラムをＣＰＵ１０２で実行する形で、各機能を実現するものとしている。このプログラムは、データ加算のためのサブプログラムを少なくとも含んでいる。
【００６４】
ここで、ＣＰＵ１０２は、プログラム記憶部１０４に格納されたプログラムを実行することにより、図２、図４及び図５に示す処理を実行する機能をもっている。
【００６５】
入出力部１０３は、演算装置１０１内と外部との間のインターフェースであり、例えば、演算対象の数Ａ，ｒを演算装置１０１内に入力する機能と、ＣＰＵ１０２により得られた演算結果を演算装置１０１の外部に出力する機能とをもっている。
【００６６】
プログラム記憶部１０４は、ＣＰＵ１０２から読出可能な記憶装置であり、例えばＲＯＭ（リードオンリーメモリ）又はＥＥＰＲＯＭ（電気的に書換え可能なＲＯＭ）であって、図２、図４及び図５に示す処理のプログラムが記憶されている。なお、プログラム記憶部１０４は、プログラムを外部からインストールして保持する構成でもよい。
【００６７】
乱数生成部１０５は、ＣＰＵ１０２に制御されて乱数を生成するものであり、例えば、ｂビットの乱数γを生成する機能をもっている。なお、乱数生成部１０５は、独立のハードウェアで実現してもよいし、ＣＰＵ１０２とプログラムで実現してもよい。あるいは、乱数生成部１０５を演算装置１０１から省略し、外部で生成した乱数を入出力部１０３から入力する構成としてもよい。
【００６８】
揮発性メモリ１０６は、ＣＰＵ１０２から読出／書込可能な記憶装置であり、例えばＲＡＭ（ランダムアクセスメモリ）であって、例えば、事前計算テーブルＣ’、数Ａ、数ｒ、乱数γ及び加算結果のように、計算に必要なデータ、計算途中のデータ及び計算結果などを格納する。
【００６９】
次に、以上のように構成された演算装置の動作を図２乃至図４を用いて説明する。なお、この動作は、事前計算テーブルの生成処理、及び加算処理（桁上げ伝播処理）の順に説明する。
【００７０】
（事前計算テーブルＣ’の生成処理：図２）
入出力部１０３は、上位（ｋ−１）ｂビットの数Ａ1及び下位ｂビットの数Ａ2からなるｋｂビットの数Ａ（但し、ｂ＞４）と、ｂビットの数ｒと、これらの数Ａ，ｒに対する加算指令とを例えば図示しない暗号処理部から受けると、これらの数Ａ，ｒ及び加算指令をＣＰＵ１０２に入力する。なお、数Ａ，Ａ1，Ａ2は、それぞれ「被算術マスクデータ」とも呼ぶ。
【００７１】
ＣＰＵ１０２は、これらの数Ａ，ｒ及び加算指令を受けると、これらの数Ａ，ｒを加算して上位（ｋ−１）ｂビットの加算結果を得る処理の前に、図３に示す如き、事前計算テーブルＣ’を生成するため、乱数生成部１０５を起動する。
【００７２】
乱数生成部１０５は、ＣＰＵ１０２に起動されると、ｂビットの乱数γを生成する（ステップＳ２１０）。この乱数γはＣＰＵ１０２に送出され、ＣＰＵ１０２から揮発性メモリ１０６に格納される。なお、ステップＳ２１０は、最初に実行する場合を例に挙げて説明したが、これに限らず、乱数γを用いるステップＳ２５０、Ｓ２６０、Ｓ２７０及びＳ２８０よりも前であれば、任意のタイミングで実行可能である。また、以下の各ステップＳ２２０〜Ｓ２８０は、任意の順序で実行可能である。
【００７３】
次に、ＣＰＵ１０２は、（４×２b/2）個のインデックスｙ（但し、０≦ｙ＜４×２b/2）と、当該各インデックスｙに関連付けた各要素データＣ’［ｙ］とを備えた事前計算テーブルＣ’を揮発性メモリ１０６に書き込む。各要素データＣ’［ｙ］は（４×２b/2）個あり、インデックスｙの各々により個別に読出可能なｂビットの値である。但し、この段階では、各要素データＣ’［ｙ］の値は設定されていない。また、インデックスｙは整数である。
【００７４】
ＣＰＵ１０２は、揮発性メモリ１０６内の事前計算テーブルＣ’の１個目から２b/2個目までの要素データＣ’［ｙ］を、０≦ｙ＜２b/2 のインデックスｙと数ｒの上位ｂ／２ビットの数ｒHとに基づいて、以下の値に設定する（ステップＳ２２０〜Ｓ２４０）。
【００７５】
Ｃ’［ｙ］＝２b/2 （０≦ｙ＜２b/2−ｒH−１ ：即ちｙ＋ｒH＜２b/2−１）
Ｃ’［ｙ］＝２×２b/2 （ｙ＝２b/2−ｒH−１ ：即ちｙ＋ｒH＝２b/2−１）
Ｃ’［ｙ］＝３×２b/2 （２b/2−ｒH≦ｙ＜２b/2 ：即ちｙ＋ｒH＞２b/2−１）
ここで、インデックスｙには、後述する上位の被算出マスクデータＡHの値が入力されることを想定しており、上の３通りの要素データＣ’［ｙ］は、それぞれＡH＋ｒH＜２b/2−１、ＡH＋ｒH＝２b/2−１、ＡH＋ｒH≧２b/2の場合に対応している。
【００７６】
上の要素データＣ’［ｙ］の値は、上位の被算出マスクデータＡHの値に応じて次に事前計算テーブルのどの要素データＣ’［ ］を見ればよいのかを示しており、一番上の場合はＣ’［２b/2］、２番目の場合はＣ’［２×２b/2］、３番目の場合はＣ’［３×２b/2］を参照することを表している。
【００７７】
次に、ＣＰＵ１０２は、揮発性メモリ１０６内の事前計算テーブルＣ’の（２b/2＋１）個目から（２×２b/2）個目までの要素データＣ’［ｙ］を、２b/2≦ｙ＜２×２b/2 のインデックスｙと乱数γとに基づいて、以下の値に設定する（ステップＳ２５０）。
【００７８】
Ｃ’［ｙ］＝γ
ここで、ｙ−２b/2には、後述する下位の被算術マスクデータＡLの値が入力されることを想定しており、これはＡH＋ｒH＜２b/2−１の場合に、下位の被算術マスクデータＡLの値に関わらず、乱数γを返すことを示している。
【００７９】
次に、ＣＰＵ１０２は、揮発性メモリ１０６内の事前計算テーブルＣ’の（２×２b/2＋１）個目から（３×２b/2）個目までの要素データＣ’［ｙ］を、２×２b/2≦ｙ＜３×２b/2 のインデックスｙと乱数γと数ｒの下位ｂ／２ビットの数ｒLとに基づいて、以下の値に設定する（ステップＳ２６０、Ｓ２７０）。
Ｃ’［ｙ］＝γ （２×２b/2≦ｙ＜３×２b/2−ｒL：即ちｙ＋ｒL＜２b/2）、
Ｃ’［ｙ］＝γ＋１ （３×２b/2−ｒL≦ｙ＜３×２b/2：即ちｙ＋ｒL≧２b/2）、
ここで、ｙ−２×２b/2には、下位の被算術マスクデータＡLの値が入力されることを想定しており、上の２通りはそれぞれＡL＋ｒL＜２b/2、ＡL＋ｒL≧２b/2の場合に対応している。
【００８０】
最後に、ＣＰＵ１０２は、揮発性メモリ１０６内の事前計算テーブルＣ’の（３×２b/2＋１）個目から（４×２b/2）個目までの要素データＣ’［ｙ］を、３×２b/2≦ｙ＜４×２b/2 のインデックスｙと乱数γとに基づいて、以下の値に設定する（ステップＳ２８０）。
Ｃ’［ｙ］＝γ＋１
ここで、ｙ−３×２b/2には、下位の被算術マスクデータＡLの値が入力されることを想定しており、これはＡH−ｒH≧２b/2の場合に、下位の被算術マスクデータＡLの値に関わらず、乱数付き桁上げ情報γ＋１を返すことを示している。
【００８１】
このように構成した事前計算テーブルＣ’のサイズは４ｂ×２b/2ビットとなる。
【００８２】
図３に、ｂ＝８、ｒ＝０ｘ１９、γ＝０ｘ５６の場合の事前計算テーブルＣ’を示す。事前計算テーブルＣ’は１６進数表記である。図３の配列は、縦の列がインデックスの２b/2の倍数を、横の行が２b/2未満のインデックスを表している。例えば縦のインデックスが１で横のインデックスが５の場合は、事前計算テーブルＣ’の１×２b/2＋５（＝２１）番目の要素を指しており、Ｃ’［２１］＝０ｘ５６となる。
【００８３】
縦のインデックス０の行は、ｒH＝１であるため、２b/2−ｒH−１＝１４である。従って横のインデックスが１３（＝０ｘ０Ｄ）以下のものは事前計算テーブルＣ’の要素は２b/2＝０ｘ１０、１４（＝０ｘ０Ｅ）のものは２×２b/2＝０ｘ２０、１５以上（＝０ｘ０Ｆ）のもの（１５のみ）は３×２b/2＝０ｘ３０となる。
【００８４】
縦のインデックス１の行は、全ての要素データが乱数γ＝０ｘ５６となる。
【００８５】
縦のインデックス３の行は、全ての要素データが乱数付き桁上げ情報γ＋１＝０ｘ５７となる。
【００８６】
縦のインデックス２の行は、ｒL＝９であるため、２b/2−ｒL＝７である。従って、横のインデックスが６以下のものは事前計算テーブルＣ’の要素データが乱数γ＝０ｘ５６となり、横のインデックスが７以上のものは要素データが乱数付き桁上げ情報γ＋１＝０ｘ５７となる。
【００８７】
（加算処理：図４）
始めに、ＣＰＵ１０２は、入力された数Ａから数Ａ1，Ａ2を抽出する。具体的には、被算術マスクデータＡの上位（ｋ−１）ｂビットを上位の被算術マスクデータＡ1とし、下位ｂビットを下位の被算術マスクデータＡ2とする（ステップＳ３１０）。
【００８８】
加算結果Ａ＋ｒを求めるためには、加算結果の下位の被算術マスクデータＡ2←Ａ2＋ｒにおける桁上げ情報（ｂ＋１ビット目）を、加算結果の上位の被算術マスクデータＡ1に伝える必要がある。すなわち加算結果の下位の被算術マスクデータＡ2＋ｒの桁上げ情報がない場合には桁上げ情報“０”の加算Ａ1←Ａ1＋０を、桁上げ情報がある場合には桁上げ情報“１”の加算Ａ1←Ａ1＋１を行う必要がある。但し、桁上げ情報の有無によって加算が異なるため、サイドチャネル解析を阻止する観点から好ましくない。
【００８９】
そのため、ｂビットの乱数γを用い、それぞれ桁上げ情報がない場合には桁上げ情報“０”の加算Ａ1←（Ａ1＋γ）−γを、桁上げ情報がある場合には桁上げ情報“１”の加算Ａ1←（Ａ1＋γ＋１）−γを行う。
【００９０】
ここで、乱数γ又は乱数付き桁上げ情報γ＋１のいずれを加えるかはＡ2＋ｒ＜２b/2であるか否かに対応しており、これは事前計算テーブルＣ’を参照することで判定できる。
【００９１】
そこで、ＣＰＵ１０２は、数Ａ2の上位ｂ／２ビットの数ＡH及び下位ｂ／２ビットの数ＡLを当該数Ａ2から抽出する。すなわち、下位の被算術マスクデータＡ2の上位ｂ／２ビットを上位の被算術マスクデータＡHとし、下位ｂ／２ビットを下位の被算術マスクデータＡLとする（ステップＳ３２０）。なお、これらステップＳ３１０、Ｓ３２０は、説明の便宜上、前述したステップＳ２８０の後に実行したが、これに限らず、ステップＳ２１０〜Ｓ２８０の間の任意のタイミングで実行可能となっている。
【００９２】
次に、ＣＰＵ１０２は、抽出した数ＡHをインデックスｙとして揮発性メモリ１０６内の事前計算テーブルＣ’から第１の要素データＣ’［ＡH］を読み出す。なお、この第１の要素データＣ’［ＡH］を読み出す処理は、前述したステップＳ２８０よりも後に実行される。
【００９３】
ＣＰＵ１０２は、第１の要素データＣ’［ＡH］及び抽出した数ＡLの和をインデックスｙとして揮発性メモリ１０６内の事前計算テーブルＣ’から第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］を読み出す。
【００９４】
ＣＰＵ１０２は、第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］、乱数γ、数Ａ1及び当該数Ａ1のビット数（ｋ−１）ｂに基づいて、
Ａ1＋Ｃ’［Ｃ’［ＡH］＋ＡL］−γ ｍｏｄ ２(k-1)b
を計算することにより、数Ａ1への桁上げを伝播する（ステップＳ３３０、Ｓ３４０）。
【００９５】
上述したように第１の実施形態によれば、ｋｂビットの数Ａとｂビットの数ｒとを互いに加算して上位（ｋ−１）ｂビットの加算結果を得る場合に必要な事前計算テーブルのサイズを縮小することができる。
【００９６】
補足すると、ステップＳ３４０により生成された上位の被算術マスクデータＡ1は、加算結果Ａ＋ｒの上位（ｋ−１）ｂビットとなっており、下位ｂビットからの桁上げ伝播を事前計算テーブルＣ’に基づいて乱数γでマスクしながら実行したため、サイドチャネル解析に対して耐性を有している。さらに事前計算テーブルＣ’のサイズが４ｂ×２b/2ビットであるので、従来の事前計算テーブルＣのサイズｂ×２bビットと比較すると縮小された割合は（４ｂ×２b/2）／（ｂ×２b）＝４／２b/2である。この割合は、例えばｂ＝４の場合には１であるが、ｂ＝８の場合には１／４、ｂ＝１６の場合には１／６４と顕著になる。
【００９７】
また、第１の実施形態においては、非特許文献３の手法を踏襲しているため、サイドチャネル解析に対して耐性を有しつつ、事前計算テーブルサイズを縮小できるため、ＩＣカードのようなリソースに厳しい制約のある装置上へ実装することがより容易となる。
【００９８】
（第２の実施形態）
次に、本発明の第２の実施形態に係る演算装置について説明するが、図９と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【００９９】
本実施形態は、従来の算術的マスクから論理的マスクへの変換方法に第１の実施形態を適用したものである。演算装置１０１の構成のうち、ハードウェア構成は、図１に示した構成と同一であり、ソフトウェア構成は、プログラム記憶部１０４内に図５に示す処理を実行するためのプログラムが付加された構成となっている。
【０１００】
当該付加されたプログラムは、算術的マスクから論理的マスクへの変換処理を実行するためのプログラムであり、従来の図９に示したステップＳ１６２に代えて、後述するステップＳ１６２ａ（第１の実施形態の事前計算テーブルＣ’を用いる処理）を実行する内容となっている（なお、ステップＳ１６２ａ以外のステップは、従来の図９に示した各ステップと同様に実行される。）。
【０１０１】
補足すると、図５に示すステップＳ１６１〜Ｓ１６３は、第１の実施形態のステップＳ３１０〜Ｓ３４０に相当し、遅くともステップＳ１６２ａを実行する前に、第１の実施形態のステップＳ２１０〜Ｓ２８０（事前計算テーブルＣ’の生成処理）が予め実行される。なお、通常は、図５に示す最初のステップＳ１１０よりも前に、予めステップＳ２１０〜Ｓ２８０が実行される。
【０１０２】
いずれにしても図５に示す処理の実行に伴い、揮発性メモリ１０６は、第１の実施形態の記憶内容に加え、第２の事前計算テーブルＧ、整数ｍ及び被論理マスクデータｘ’を記憶するように用いられる。ここで、第２の事前計算テーブルＧは、図８に示したように、０から２b−１までの２b個のインデックスＩと、当該各インデックスＩにより個別に読出可能な２b個の要素データＧ［Ｉ］＝（（Ｉ＋ｒ） ｍｏｄ ２b）＾ｒ とを備えている。
【０１０３】
次に、以上のように構成された演算装置の動作を図５を用いて説明する。
【０１０４】
なお、ＣＰＵ１０２は、前述したステップＳ２１０〜Ｓ２８０の処理により、第１の実施形態に述べた事前計算テーブルＣ’を予め生成して揮発性メモリ１０６に書き込んでいるとする。また同様に、ＣＰＵ１０２は、０から２b−１までの２b個のインデックスＩ、乱数ｒ及びビット数ｂに基づいて第２の事前計算テーブルＧを生成し、当該第２の事前計算テーブルＧを揮発性メモリ１０６に書き込む。
【０１０５】
入出力部１０３においては、上位（ｋ−１）ｂビットの数Ａ1及び下位ｂビットの数Ａ2からなるｋｂビットの数Ａと、上位（ｍ−１）ｂビットの数Ｒ1及び下位ｂビットの数Ｒ2からなるｍｂビットの数Ｒとを演算装置１０１内に入力して揮発性メモリ１０６に書き込む。
【０１０６】
続いて、ＣＰＵ１０２は、整数ｍ及び被論理マスクデータｘ’をそれぞれｍ＝ｋ、ｘ’＝０に設定し、これら整数ｍ及び被論理マスクデータｘ’を揮発性メモリ１０６に書き込む（ステップＳ１１０〜Ｓ１２０）。
【０１０７】
ＣＰＵ１０２は、被算術マスクデータとしての数Ａから乱数ｒをｍｏｄ ２ｍｂ の下で減算する（ステップＳ１３０）。この減算により、減算結果Ａ←Ａ−ｒ ｍｏｄ ２ｍｂが得られる。
【０１０８】
この減算の後、ＣＰＵ１０２は、入力された数Ｒから上位（ｍ−１）ｂビットの数Ｒ1及び下位ｂビットの数Ｒ2を抽出する（ステップＳ１４０）。
【０１０９】
この抽出の後、ＣＰＵ１０２は、数Ａに数Ｒ2をｍｏｄ ２ｍｂ の下で加算する（ステップＳ１５０）。この加算により、加算結果Ａ←Ａ−Ｒ2 ｍｏｄ ２ｍｂが得られる。
【０１１０】
この加算の後、ＣＰＵ１０２は、揮発性メモリ１０６内の整数ｍについて、ｍ＝１か否かを判定する。
【０１１１】
ＣＰＵ１０２は、判定の結果、ｍ＝１の場合には加算後の数ＡをインデックスＩとして、揮発性メモリ１０６内の事前計算テーブルＧから要素データＧ［Ａ］を読み出す。しかる後、ＣＰＵ１０２は、この要素データＧ［Ａ］、数Ｒ2及び乱数ｒに基づいて、上位の被論理マスクデータｘ’1を、ｘ’1＝（Ｇ［Ａ］＾Ｒ2）＾ｒ の値に計算する手段（ステップＳ１７０〜Ｓ１８０）。
【０１１２】
ＣＰＵ１０２は、この計算により得られた上位の被論理マスクデータｘ’1を、揮発性メモリ１０６内の被論理マスクデータｘ’の最上位ｂビットに配置する（ステップＳ１９０）。
【０１１３】
一方、ステップＳ１６０による判定の結果、ｍ＞１の場合には、前述したステップＳ３１０〜Ｓ３４０と同様の処理として、ステップＳ１６１、Ｓ１６２ａ及びＳ１６３を順次実行する。
【０１１４】
詳しくは、ＣＰＵ１０２は、ステップＳ１５０による加算後の数Ａから数Ａ1，Ａ2を抽出する。具体的には、被算術マスクデータＡの上位（ｋ−１）ｂビットを上位の被算術マスクデータＡ1とし、下位ｂビットを下位の被算術マスクデータＡ2とする（ステップＳ１６１）。
【０１１５】
次に、ＣＰＵ１０２は、従来のステップＳ１６２とは異なり、以下のステップＳ１６２ａを実行する。
【０１１６】
すなわち、ＣＰＵ１０２は、前述同様に、数Ａ2の上位ｂ／２ビットの数ＡH及び下位ｂ／２ビットの数ＡLを当該数Ａ2から抽出する。
【０１１７】
次に、ＣＰＵ１０２は、抽出した数ＡHをインデックスｙとして揮発性メモリ１０６内の事前計算テーブルＣ’から第１の要素データＣ’［ＡH］を読み出す。
【０１１８】
また、ＣＰＵ１０２は、第１の要素データＣ’［ＡH］と抽出した数ＡLとの和をインデックスｙとして揮発性メモリ１０６内の事前計算テーブルＣ’から第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］を読み出す。
【０１１９】
ＣＰＵ１０２は、第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］、乱数γ、数Ａ1及び当該数Ａ1のビット数（ｍ−１）ｂに基づいて、
Ａ1←Ａ1＋Ｃ’［Ｃ’［ＡH］＋ＡL］−γ ｍｏｄ ２(m-1)b
の計算により、数Ａ1への桁上げを伝播する（ステップＳ１６２ａ、Ｓ１６３）。
【０１２０】
次に、ＣＰＵ１０２は、ステップＳ１６１で抽出した数Ａ2をインデックスＩとして、揮発性メモリ１０６内の事前計算テーブルＧから要素データＧ［Ａ2］を読み出す。しかる後、ＣＰＵ１０２は、この要素データＧ［Ａ2］、数Ｒ2及び乱数ｒに基づいて、下位の被論理マスクデータｘ’2を、ｘ’2＝（Ｇ［Ａ2］＾Ｒ2）＾ｒ の値に計算する（ステップＳ１６４、Ｓ１６５）。
【０１２１】
ＣＰＵ１０２は、この計算により得られた下位の被論理マスクデータｘ’2を、揮発性メモリ１０６内の被論理マスクデータｘ’の下位（ｋ−ｍ）ｂビット目に、当該下位の被論理マスクデータｘ’2の最下位ビットが合うように配置する（ステップＳ１６６）。
【０１２２】
この配置の後、ＣＰＵ１０２は、揮発性メモリ１０６内の整数ｍを、ｍ＝ｍ−１と更新してステップＳ１３０の処理に戻る（ステップＳ１６７）。
以下、ＣＰＵ１０２は、ステップＳ１３０以降の処理を再実行する。
【０１２３】
上述したように第２の実施形態によれば、従来の算術的マスクから論理的マスクへの変換方法に第１の実施形態を適用した構成により、被算術マスクデータを被論理マスクデータに変換する場合に必要な事前計算テーブルのサイズを縮小することができる。
【０１２４】
補足すると、第２の実施形態においては、第１の実施形態と同様に、非特許文献３の手法を踏襲しているためサイドチャネル解析に対して耐性を有しつつ、事前計算テーブルサイズをより小さくできるため、ＩＣカードのようなリソースに厳しい制約のある装置上へ実装することがより容易となる。
【０１２５】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１２６】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１２７】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１２８】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１２９】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１３０】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１３１】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１３２】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【符号の説明】
【０１３３】
１０１…演算装置、１０２…ＣＰＵ、１０３…入出力部、１０４…プログラム記憶部、１０５…乱数生成部、１０６…揮発性メモリ、１０７…バス。
【特許請求の範囲】
【請求項１】
上位（ｋ−１）ｂビットの数Ａ1及び下位ｂビットの数Ａ2からなるｋｂビットの数Ａ（但し、ｂ＞４）と、ｂビットの数ｒとを加算して上位（ｋ−１）ｂビットの加算結果を得る処理の前に、（４×２b/2）個のインデックスｙ（但し、０≦ｙ＜４×２b/2）の各々により個別に読出可能な（４×２b/2）個のｂビットの要素データＣ’［ｙ］を備えた事前計算テーブルＣ’を生成し、前記加算する処理中に、前記数Ａ2と前記数ｒとの加算結果から前記数Ａ1への桁上げを前記事前計算テーブルＣ’に基づいて伝播可能な演算装置であって、
前記ｂビットの乱数γを生成する手段と、
前記各インデックスｙと、当該各インデックスｙに関連付けた各要素データＣ’［ｙ］とを備えた事前計算テーブルＣ’を記憶するための記憶手段と、
前記記憶手段内の事前計算テーブルＣ’の１個目から２b/2個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記数ｒの上位ｂ／２ビットの数ｒHとに基づいて、
Ｃ’［ｙ］＝２b/2 （但し、０≦ｙ＜２b/2−ｒH−１ ）、
Ｃ’［ｙ］＝２×２b/2 （但し、ｙ＝２b/2−ｒH−１ ）、
Ｃ’［ｙ］＝３×２b/2 （但し、２b/2−ｒH≦ｙ＜２b/2 ）、
の値に設定する手段と、
前記記憶手段内の事前計算テーブルＣ’の（２b/2＋１）個目から（２×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、
Ｃ’［ｙ］＝γ （但し、２b/2≦ｙ＜２×２b/2）、
の値に設定する手段と、
前記記憶手段内の事前計算テーブルＣ’の（２×２b/2＋１）個目から（３×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γと前記数ｒの下位ｂ／２ビットの数ｒLとに基づいて、
Ｃ’［ｙ］＝γ （但し、２×２b/2≦ｙ＜３×２b/2−ｒL）、
Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2−ｒL≦ｙ＜３×２b/2）、
の値に設定する手段と、
前記記憶手段内の事前計算テーブルＣ’の（３×２b/2＋１）個目から（４×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、
Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2≦ｙ＜４×２b/2）
の値に設定する手段と、
前記数Ａから前記数Ａ1及び前記数Ａ2を抽出する第１抽出手段と、
前記数Ａ2の上位ｂ／２ビットの数ＡH及び下位ｂ／２ビットの数ＡLを当該数Ａ2から抽出する第２抽出手段と、
前記（４×２b/2）個の要素データＣ’［ｙ］の値を設定した後、前記抽出した数ＡHをインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第１の要素データＣ’［ＡH］を読み出す第１読出手段と、
前記第１の要素データＣ’［ＡH］と前記抽出した数ＡLとの和をインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］を読み出す第２読出手段と、
前記第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］、前記乱数γ、前記数Ａ1及び当該数Ａ1のビット数（ｋ−１）ｂに基づいて、Ａ1＋Ｃ’［Ｃ’［ＡH］＋ＡL］−γ ｍｏｄ ２(k-1)b を計算することにより、前記数Ａ1への桁上げを伝播する桁上げ伝播手段と、
を備えたことを特徴とする演算装置。
【請求項２】
請求項１に記載の演算装置において、
０から２b−１までの２b個のインデックスＩと、当該各インデックスＩにより個別に読出可能な２b個の要素データＧ［Ｉ］＝（（Ｉ＋ｒ） ｍｏｄ ２b）＾ｒ とを備えた第２の事前計算テーブルＧを記憶するための第２の記憶手段（但し、＾は排他的論理和を表す記号）と、
前記インデックスＩ、前記乱数ｒ及びビット数ｂに基づいて前記第２の事前計算テーブルＧを生成し、当該第２の事前計算テーブルＧを前記第２の記憶手段に書き込む手段と、
整数ｍ及び被論理マスクデータｘ’を記憶するための第３の記憶手段と、
整数ｍ及び被論理マスクデータｘ’をそれぞれｍ＝ｋ、ｘ’＝０に設定し、これら整数ｍ及び被論理マスクデータｘ’を前記第３の記憶手段に書き込む手段と、
上位（ｍ−１）ｂビットの数Ｒ1及び下位ｂビットの数Ｒ2からなるｍｂビットの数Ｒを入力するための手段と、
被算術マスクデータとしての前記数Ａから前記乱数ｒをｍｏｄ ２ｍｂ の下で減算する減算手段と、
この減算の後、前記入力された数Ｒから前記数Ｒ1，Ｒ2を抽出する手段と、
この抽出の後、前記Ａに前記数Ｒ2をｍｏｄ ２ｍｂ の下で加算する手段と、
この加算の後、前記第３の記憶手段内の整数ｍについて、ｍ＝１か否かを判定する手段と、
前記判定の結果、ｍ＝１の場合には前記加算後の数ＡをインデックスＩとして、前記第２の記憶手段内の事前計算テーブルＧから要素データＧ［Ａ］を読み出す手段と、
この要素データＧ［Ａ］、前記数Ｒ2及び前記乱数ｒに基づいて、上位の被論理マスクデータｘ’1を、ｘ’1＝（Ｇ［Ａ］＾Ｒ2）＾ｒ の値に計算する手段と、
この計算により得られた上位の被論理マスクデータｘ’1を、前記第３の記憶手段内の被論理マスクデータｘ’の最上位ｂビットに配置する手段と、
前記判定の結果、ｍ＞１の場合には、前記第１抽出手段、前記第２抽出手段、前記第１読出手段、前記第２読出手段及び前記桁上げ伝播手段による処理を順次実行する手段と、
この桁上げ伝播手段による処理の実行後、前記加算後の数Ａの下位ｂビットの数Ａ2をインデックスＩとして、前記第２の記憶手段内の事前計算テーブルＧから要素データＧ［Ａ2］を読み出す手段と、
この要素データＧ［Ａ2］、前記数Ｒ2及び前記乱数ｒに基づいて、下位の被論理マスクデータｘ’2を、ｘ’2＝（Ｇ［Ａ2］＾Ｒ2）＾ｒ の値に計算する手段と、
この計算により得られた下位の被論理マスクデータｘ’2を、前記第３の記憶手段内の被論理マスクデータｘ’の下位（ｋ−ｍ）ｂビット目に、当該下位の被論理マスクデータｘ’2の最下位ビットが合うように配置する手段と、
この配置の後、前記第３の記憶手段内の整数ｍを、ｍ＝ｍ−１と更新し、前記減算手段の処理に戻る手段と、
を更に備えたことを特徴とする演算装置。
【請求項３】
上位（ｋ−１）ｂビットの数Ａ1及び下位ｂビットの数Ａ2からなるｋｂビットの数Ａ（但し、ｂ＞４）と、ｂビットの数ｒとを加算して上位（ｋ−１）ｂビットの加算結果を得る処理の前に、（４×２b/2）個のインデックスｙ（但し、０≦ｙ＜４×２b/2）の各々により個別に読出可能な（４×２b/2）個のｂビットの要素データＣ’［ｙ］を備えた事前計算テーブルＣ’を生成し、前記加算する処理中に、前記数Ａ2と前記数ｒとの加算結果から前記数Ａ1への桁上げを前記事前計算テーブルＣ’に基づいて伝播可能な演算装置のプログラムであって、
前記演算装置を、
前記ｂビットの乱数γを生成する手段、
前記各インデックスｙと、当該各インデックスｙに関連付けた各要素データＣ’［ｙ］とを備えた事前計算テーブルＣ’を前記演算装置の記憶手段に書き込む手段、
前記記憶手段内の事前計算テーブルＣ’の１個目から２b/2個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記数ｒの上位ｂ／２ビットの数ｒHとに基づいて、
Ｃ’［ｙ］＝２b/2 （但し、０≦ｙ＜２b/2−ｒH−１ ）、
Ｃ’［ｙ］＝２×２b/2 （但し、ｙ＝２b/2−ｒH−１ ）、
Ｃ’［ｙ］＝３×２b/2 （但し、２b/2−ｒH≦ｙ＜２b/2 ）、
の値に設定する手段、
前記記憶手段内の事前計算テーブルＣ’の（２b/2＋１）個目から（２×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、
Ｃ’［ｙ］＝γ （但し、２b/2≦ｙ＜２×２b/2）、
の値に設定する手段、
前記記憶手段内の事前計算テーブルＣ’の（２×２b/2＋１）個目から（３×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γと前記数ｒの下位ｂ／２ビットの数ｒLとに基づいて、
Ｃ’［ｙ］＝γ （但し、２×２b/2≦ｙ＜３×２b/2−ｒL）、
Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2−ｒL≦ｙ＜３×２b/2）、
の値に設定する手段、
前記記憶手段内の事前計算テーブルＣ’の（３×２b/2＋１）個目から（４×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、
Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2≦ｙ＜４×２b/2）
の値に設定する手段、
前記数Ａから前記数Ａ1及び前記数Ａ2を抽出する手段、
前記数Ａ2の上位ｂ／２ビットの数ＡH及び下位ｂ／２ビットの数ＡLを当該数Ａ2から抽出する手段、
前記（４×２b/2）個の要素データＣ’［ｙ］の値を設定した後、前記抽出した数ＡHをインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第１の要素データＣ’［ＡH］を読み出す手段、
前記第１の要素データＣ’［ＡH］と前記抽出した数ＡLとの和をインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］を読み出す手段、
前記第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］、前記乱数γ、前記数Ａ1及び当該数Ａ1のビット数（ｋ−１）ｂに基づいて、Ａ1＋Ｃ’［Ｃ’［ＡH］＋ＡL］−γ ｍｏｄ ２(k-1)b を計算することにより、前記数Ａ1への桁上げを伝播する手段、
として機能させるためのプログラム。
【請求項４】
請求項３に記載のプログラムにおいて、
前記演算装置を、
０から２b−１までの２b個のインデックスＩと、当該各インデックスＩにより個別に読出可能な２b個の要素データＧ［Ｉ］＝（（Ｉ＋ｒ） ｍｏｄ ２b）＾ｒ とを備えた第２の事前計算テーブルＧ（但し、＾は排他的論理和を表す記号）を、前記インデックスＩ、前記乱数ｒ及びビット数ｂに基づいて生成し、当該生成した第２の事前計算テーブルＧを前記演算装置の第２の記憶手段に書き込む手段、
整数ｍ及び被論理マスクデータｘ’をそれぞれｍ＝ｋ、ｘ’＝０に設定し、これら整数ｍ及び被論理マスクデータｘ’を前記演算装置の第３の記憶手段に書き込む手段、
上位（ｍ−１）ｂビットの数Ｒ1及び下位ｂビットの数Ｒ2からなるｍｂビットの数Ｒを入力するための手段、
被算術マスクデータとしての前記数Ａから前記乱数ｒをｍｏｄ ２ｍｂ の下で減算する減算手段、
この減算の後、前記入力された数Ｒから前記数Ｒ1，Ｒ2を抽出する手段、
この抽出の後、前記Ａに前記数Ｒ2をｍｏｄ ２ｍｂ の下で加算する手段、
この加算の後、前記第３の記憶手段内の整数ｍについて、ｍ＝１か否かを判定する手段、
前記判定の結果、ｍ＝１の場合には前記加算後の数ＡをインデックスＩとして、前記第２の記憶手段内の事前計算テーブルＧから要素データＧ［Ａ］を読み出す手段、
この要素データＧ［Ａ］、前記数Ｒ2及び前記乱数ｒに基づいて、上位の被論理マスクデータｘ’1を、ｘ’1＝（Ｇ［Ａ］＾Ｒ2）＾ｒ の値に計算する手段、
この計算により得られた上位の被論理マスクデータｘ’1を、前記第３の記憶手段内の被論理マスクデータｘ’の最上位ｂビットに配置する手段、
前記判定の結果、ｍ＞１の場合には、前記第１抽出手段、前記第２抽出手段、前記第１読出手段、前記第２読出手段及び前記桁上げ伝播手段による処理を順次実行する手段、
この桁上げ伝播手段による処理の実行後、前記加算後の数Ａの下位ｂビットの数Ａ2をインデックスＩとして、前記第２の記憶手段内の事前計算テーブルＧから要素データＧ［Ａ2］を読み出す手段、
この要素データＧ［Ａ2］、前記数Ｒ2及び前記乱数ｒに基づいて、下位の被論理マスクデータｘ’2を、ｘ’2＝（Ｇ［Ａ2］＾Ｒ2）＾ｒ の値に計算する手段、
この計算により得られた下位の被論理マスクデータｘ’2を、前記第３の記憶手段内の被論理マスクデータｘ’の下位（ｋ−ｍ）ｂビット目に、当該下位の被論理マスクデータｘ’2の最下位ビットが合うように配置する手段、
この配置の後、前記第３の記憶手段内の整数ｍを、ｍ＝ｍ−１と更新し、前記減算手段の処理に戻る手段、
として更に機能させるためのプログラム。
【請求項１】
上位（ｋ−１）ｂビットの数Ａ1及び下位ｂビットの数Ａ2からなるｋｂビットの数Ａ（但し、ｂ＞４）と、ｂビットの数ｒとを加算して上位（ｋ−１）ｂビットの加算結果を得る処理の前に、（４×２b/2）個のインデックスｙ（但し、０≦ｙ＜４×２b/2）の各々により個別に読出可能な（４×２b/2）個のｂビットの要素データＣ’［ｙ］を備えた事前計算テーブルＣ’を生成し、前記加算する処理中に、前記数Ａ2と前記数ｒとの加算結果から前記数Ａ1への桁上げを前記事前計算テーブルＣ’に基づいて伝播可能な演算装置であって、
前記ｂビットの乱数γを生成する手段と、
前記各インデックスｙと、当該各インデックスｙに関連付けた各要素データＣ’［ｙ］とを備えた事前計算テーブルＣ’を記憶するための記憶手段と、
前記記憶手段内の事前計算テーブルＣ’の１個目から２b/2個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記数ｒの上位ｂ／２ビットの数ｒHとに基づいて、
Ｃ’［ｙ］＝２b/2 （但し、０≦ｙ＜２b/2−ｒH−１ ）、
Ｃ’［ｙ］＝２×２b/2 （但し、ｙ＝２b/2−ｒH−１ ）、
Ｃ’［ｙ］＝３×２b/2 （但し、２b/2−ｒH≦ｙ＜２b/2 ）、
の値に設定する手段と、
前記記憶手段内の事前計算テーブルＣ’の（２b/2＋１）個目から（２×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、
Ｃ’［ｙ］＝γ （但し、２b/2≦ｙ＜２×２b/2）、
の値に設定する手段と、
前記記憶手段内の事前計算テーブルＣ’の（２×２b/2＋１）個目から（３×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γと前記数ｒの下位ｂ／２ビットの数ｒLとに基づいて、
Ｃ’［ｙ］＝γ （但し、２×２b/2≦ｙ＜３×２b/2−ｒL）、
Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2−ｒL≦ｙ＜３×２b/2）、
の値に設定する手段と、
前記記憶手段内の事前計算テーブルＣ’の（３×２b/2＋１）個目から（４×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、
Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2≦ｙ＜４×２b/2）
の値に設定する手段と、
前記数Ａから前記数Ａ1及び前記数Ａ2を抽出する第１抽出手段と、
前記数Ａ2の上位ｂ／２ビットの数ＡH及び下位ｂ／２ビットの数ＡLを当該数Ａ2から抽出する第２抽出手段と、
前記（４×２b/2）個の要素データＣ’［ｙ］の値を設定した後、前記抽出した数ＡHをインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第１の要素データＣ’［ＡH］を読み出す第１読出手段と、
前記第１の要素データＣ’［ＡH］と前記抽出した数ＡLとの和をインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］を読み出す第２読出手段と、
前記第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］、前記乱数γ、前記数Ａ1及び当該数Ａ1のビット数（ｋ−１）ｂに基づいて、Ａ1＋Ｃ’［Ｃ’［ＡH］＋ＡL］−γ ｍｏｄ ２(k-1)b を計算することにより、前記数Ａ1への桁上げを伝播する桁上げ伝播手段と、
を備えたことを特徴とする演算装置。
【請求項２】
請求項１に記載の演算装置において、
０から２b−１までの２b個のインデックスＩと、当該各インデックスＩにより個別に読出可能な２b個の要素データＧ［Ｉ］＝（（Ｉ＋ｒ） ｍｏｄ ２b）＾ｒ とを備えた第２の事前計算テーブルＧを記憶するための第２の記憶手段（但し、＾は排他的論理和を表す記号）と、
前記インデックスＩ、前記乱数ｒ及びビット数ｂに基づいて前記第２の事前計算テーブルＧを生成し、当該第２の事前計算テーブルＧを前記第２の記憶手段に書き込む手段と、
整数ｍ及び被論理マスクデータｘ’を記憶するための第３の記憶手段と、
整数ｍ及び被論理マスクデータｘ’をそれぞれｍ＝ｋ、ｘ’＝０に設定し、これら整数ｍ及び被論理マスクデータｘ’を前記第３の記憶手段に書き込む手段と、
上位（ｍ−１）ｂビットの数Ｒ1及び下位ｂビットの数Ｒ2からなるｍｂビットの数Ｒを入力するための手段と、
被算術マスクデータとしての前記数Ａから前記乱数ｒをｍｏｄ ２ｍｂ の下で減算する減算手段と、
この減算の後、前記入力された数Ｒから前記数Ｒ1，Ｒ2を抽出する手段と、
この抽出の後、前記Ａに前記数Ｒ2をｍｏｄ ２ｍｂ の下で加算する手段と、
この加算の後、前記第３の記憶手段内の整数ｍについて、ｍ＝１か否かを判定する手段と、
前記判定の結果、ｍ＝１の場合には前記加算後の数ＡをインデックスＩとして、前記第２の記憶手段内の事前計算テーブルＧから要素データＧ［Ａ］を読み出す手段と、
この要素データＧ［Ａ］、前記数Ｒ2及び前記乱数ｒに基づいて、上位の被論理マスクデータｘ’1を、ｘ’1＝（Ｇ［Ａ］＾Ｒ2）＾ｒ の値に計算する手段と、
この計算により得られた上位の被論理マスクデータｘ’1を、前記第３の記憶手段内の被論理マスクデータｘ’の最上位ｂビットに配置する手段と、
前記判定の結果、ｍ＞１の場合には、前記第１抽出手段、前記第２抽出手段、前記第１読出手段、前記第２読出手段及び前記桁上げ伝播手段による処理を順次実行する手段と、
この桁上げ伝播手段による処理の実行後、前記加算後の数Ａの下位ｂビットの数Ａ2をインデックスＩとして、前記第２の記憶手段内の事前計算テーブルＧから要素データＧ［Ａ2］を読み出す手段と、
この要素データＧ［Ａ2］、前記数Ｒ2及び前記乱数ｒに基づいて、下位の被論理マスクデータｘ’2を、ｘ’2＝（Ｇ［Ａ2］＾Ｒ2）＾ｒ の値に計算する手段と、
この計算により得られた下位の被論理マスクデータｘ’2を、前記第３の記憶手段内の被論理マスクデータｘ’の下位（ｋ−ｍ）ｂビット目に、当該下位の被論理マスクデータｘ’2の最下位ビットが合うように配置する手段と、
この配置の後、前記第３の記憶手段内の整数ｍを、ｍ＝ｍ−１と更新し、前記減算手段の処理に戻る手段と、
を更に備えたことを特徴とする演算装置。
【請求項３】
上位（ｋ−１）ｂビットの数Ａ1及び下位ｂビットの数Ａ2からなるｋｂビットの数Ａ（但し、ｂ＞４）と、ｂビットの数ｒとを加算して上位（ｋ−１）ｂビットの加算結果を得る処理の前に、（４×２b/2）個のインデックスｙ（但し、０≦ｙ＜４×２b/2）の各々により個別に読出可能な（４×２b/2）個のｂビットの要素データＣ’［ｙ］を備えた事前計算テーブルＣ’を生成し、前記加算する処理中に、前記数Ａ2と前記数ｒとの加算結果から前記数Ａ1への桁上げを前記事前計算テーブルＣ’に基づいて伝播可能な演算装置のプログラムであって、
前記演算装置を、
前記ｂビットの乱数γを生成する手段、
前記各インデックスｙと、当該各インデックスｙに関連付けた各要素データＣ’［ｙ］とを備えた事前計算テーブルＣ’を前記演算装置の記憶手段に書き込む手段、
前記記憶手段内の事前計算テーブルＣ’の１個目から２b/2個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記数ｒの上位ｂ／２ビットの数ｒHとに基づいて、
Ｃ’［ｙ］＝２b/2 （但し、０≦ｙ＜２b/2−ｒH−１ ）、
Ｃ’［ｙ］＝２×２b/2 （但し、ｙ＝２b/2−ｒH−１ ）、
Ｃ’［ｙ］＝３×２b/2 （但し、２b/2−ｒH≦ｙ＜２b/2 ）、
の値に設定する手段、
前記記憶手段内の事前計算テーブルＣ’の（２b/2＋１）個目から（２×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、
Ｃ’［ｙ］＝γ （但し、２b/2≦ｙ＜２×２b/2）、
の値に設定する手段、
前記記憶手段内の事前計算テーブルＣ’の（２×２b/2＋１）個目から（３×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γと前記数ｒの下位ｂ／２ビットの数ｒLとに基づいて、
Ｃ’［ｙ］＝γ （但し、２×２b/2≦ｙ＜３×２b/2−ｒL）、
Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2−ｒL≦ｙ＜３×２b/2）、
の値に設定する手段、
前記記憶手段内の事前計算テーブルＣ’の（３×２b/2＋１）個目から（４×２b/2）個目までの要素データＣ’［ｙ］を、前記インデックスｙと前記乱数γとに基づいて、
Ｃ’［ｙ］＝γ＋１ （但し、３×２b/2≦ｙ＜４×２b/2）
の値に設定する手段、
前記数Ａから前記数Ａ1及び前記数Ａ2を抽出する手段、
前記数Ａ2の上位ｂ／２ビットの数ＡH及び下位ｂ／２ビットの数ＡLを当該数Ａ2から抽出する手段、
前記（４×２b/2）個の要素データＣ’［ｙ］の値を設定した後、前記抽出した数ＡHをインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第１の要素データＣ’［ＡH］を読み出す手段、
前記第１の要素データＣ’［ＡH］と前記抽出した数ＡLとの和をインデックスｙとして前記記憶手段内の事前計算テーブルＣ’から第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］を読み出す手段、
前記第２の要素データＣ’［Ｃ’［ＡH］＋ＡL］、前記乱数γ、前記数Ａ1及び当該数Ａ1のビット数（ｋ−１）ｂに基づいて、Ａ1＋Ｃ’［Ｃ’［ＡH］＋ＡL］−γ ｍｏｄ ２(k-1)b を計算することにより、前記数Ａ1への桁上げを伝播する手段、
として機能させるためのプログラム。
【請求項４】
請求項３に記載のプログラムにおいて、
前記演算装置を、
０から２b−１までの２b個のインデックスＩと、当該各インデックスＩにより個別に読出可能な２b個の要素データＧ［Ｉ］＝（（Ｉ＋ｒ） ｍｏｄ ２b）＾ｒ とを備えた第２の事前計算テーブルＧ（但し、＾は排他的論理和を表す記号）を、前記インデックスＩ、前記乱数ｒ及びビット数ｂに基づいて生成し、当該生成した第２の事前計算テーブルＧを前記演算装置の第２の記憶手段に書き込む手段、
整数ｍ及び被論理マスクデータｘ’をそれぞれｍ＝ｋ、ｘ’＝０に設定し、これら整数ｍ及び被論理マスクデータｘ’を前記演算装置の第３の記憶手段に書き込む手段、
上位（ｍ−１）ｂビットの数Ｒ1及び下位ｂビットの数Ｒ2からなるｍｂビットの数Ｒを入力するための手段、
被算術マスクデータとしての前記数Ａから前記乱数ｒをｍｏｄ ２ｍｂ の下で減算する減算手段、
この減算の後、前記入力された数Ｒから前記数Ｒ1，Ｒ2を抽出する手段、
この抽出の後、前記Ａに前記数Ｒ2をｍｏｄ ２ｍｂ の下で加算する手段、
この加算の後、前記第３の記憶手段内の整数ｍについて、ｍ＝１か否かを判定する手段、
前記判定の結果、ｍ＝１の場合には前記加算後の数ＡをインデックスＩとして、前記第２の記憶手段内の事前計算テーブルＧから要素データＧ［Ａ］を読み出す手段、
この要素データＧ［Ａ］、前記数Ｒ2及び前記乱数ｒに基づいて、上位の被論理マスクデータｘ’1を、ｘ’1＝（Ｇ［Ａ］＾Ｒ2）＾ｒ の値に計算する手段、
この計算により得られた上位の被論理マスクデータｘ’1を、前記第３の記憶手段内の被論理マスクデータｘ’の最上位ｂビットに配置する手段、
前記判定の結果、ｍ＞１の場合には、前記第１抽出手段、前記第２抽出手段、前記第１読出手段、前記第２読出手段及び前記桁上げ伝播手段による処理を順次実行する手段、
この桁上げ伝播手段による処理の実行後、前記加算後の数Ａの下位ｂビットの数Ａ2をインデックスＩとして、前記第２の記憶手段内の事前計算テーブルＧから要素データＧ［Ａ2］を読み出す手段、
この要素データＧ［Ａ2］、前記数Ｒ2及び前記乱数ｒに基づいて、下位の被論理マスクデータｘ’2を、ｘ’2＝（Ｇ［Ａ2］＾Ｒ2）＾ｒ の値に計算する手段、
この計算により得られた下位の被論理マスクデータｘ’2を、前記第３の記憶手段内の被論理マスクデータｘ’の下位（ｋ−ｍ）ｂビット目に、当該下位の被論理マスクデータｘ’2の最下位ビットが合うように配置する手段、
この配置の後、前記第３の記憶手段内の整数ｍを、ｍ＝ｍ−１と更新し、前記減算手段の処理に戻る手段、
として更に機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−２１０９４０（Ｐ２０１０−２１０９４０Ａ）
【公開日】平成２２年９月２４日（２０１０．９．２４）
【国際特許分類】
【出願番号】特願２００９−５６８７３（Ｐ２００９−５６８７３）
【出願日】平成２１年３月１０日（２００９．３．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＥＥＰＲＯＭ
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
【公開日】平成２２年９月２４日（２０１０．９．２４）
【国際特許分類】
【出願日】平成２１年３月１０日（２００９．３．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＥＥＰＲＯＭ
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
[ Back to top ]