JP2006201641A - 非線形演算装置及び暗号処理装置及び非線形演算方法及び非線形演算プログラム - Google Patents

Abstract

【課題】 非線形演算を用いた暗号処理方法において、電力解析への安全性を担保しつつ、乗算回数を削減することで、処理を高速に行うことを目的とする。
【解決手段】 非線形演算装置において、データ入力部１４０は分割入力Ｐを、乱数入力部１４１は補正乱数Ｍを入力する。乱数生成部１２８は任意の乱数Ｍ´、補正乱数Ｍと相関がない乱数Ｎを生成する。べき乗演算部１２７は分割入力Ｐ、補正乱数Ｍ、乱数Ｍ´、Ｎを入力とし、分割入力Ｐのべき乗Ｐ^ｅと、乱数Ｍ´と、補正乱数Ｍ、分割入力Ｐ、補正乱数Ｍと分割入力Ｐに含まれる暗号化すべきデータｘとが乗算されたＭｘのみで表現される式とを加算する多項式を用いて、出力データＦ_ｅ（Ｆ_ｅ＝ｘ^ｅ＋Ｍ´）を演算し、出力する。このとき、その演算において補正乱数Ｍ、乱数付加データＰ、乗算データＭｘのみで表現される式として乗算回数が少なくなるように変形されたものを用いる。
【選択図】 図４

Description

本発明は、非線形演算装置及び暗号処理装置及び非線形演算方法及び非線形演算プログラムに関するものである。

暗号処理をシステム上で実行する場合、実行中のシステムの消費電力の変化を観測し、暗号処理に使われている秘密情報である暗号鍵を推測する方法がある（例えば、非特許文献１）。この手法は電力解析と呼ばれている。電力解析に対して、解析が行われても暗号鍵を推測されないように暗号を実装する必要がある。

このような実装において、暗号化を行う入力（以降、「平文」という）と乱数との排他的論理和を求めたり（以降、この手法に係る乱数を「加算マスク」といい、この乱数との排他的論理和を求めることを「加算マスクを付加する」という）、平文と乱数とのガロア拡大体上の乗算を求めたりし（以降、この手法に係る乱数を「乗算マスク」といい、この乱数とのガロア拡大体上の乗算を求めることを「乗算マスクを施す」という）、その出力に対して暗号処理を行い、暗号処理後に乱数を取り除く操作を行う手法がある（例えば、特許文献１）。しかしながら多くの暗号では処理の過程に非線形処理を含む。よって上記手法の実現には、乱数を付加した平文に対して、平文のみを暗号化するための処理が必要となる。

多くの暗号では、非線形処理にガロア拡大体上のべき乗演算とアフィン変換とを組み合わせた構成を採用している。例えば、非特許文献２では、平文に加算マスクを付加し、ガロア拡大体上のべき乗演算を行う前に加算マスクをはずし、新たな乗算マスクを施し、べき乗演算後に乗算マスクをはずし、加算マスクを付加していた。また非特許文献３では、乱数を付加した平文と乱数そのものを入力とし、平文のみを処理できる２乗演算（以降、ＰＭＳ（Ｐｅｒｆｅｃｔｌｙ Ｍａｓｋｅｄ Ｓｑｕａｒｉｎｇ）という）と乗算演算（以降、ＰＭＭ（Ｐｅｒｆｅｃｔｌｙ Ｍａｓｋｅｄ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）という）を定義し、これらを組み合わせて平文の逆元を求めている。
特表２００２−５４０６５４号公報 Ｐ． Ｋｏｃｈｅｒ， Ｊ． Ｊａｆｆｅ， Ｂ． Ｊｕｎ， "Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ"， Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ： Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＣＲＹＰＴＯ’９９， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ， ｐ．３８８−３９７， １９９９ Ｊ． Ｄ． Ｇｏｌｉｃ， Ｃ． Ｔｙｍｅｎ， "Ｍｕｌｔｉｐｌｉｃａｔｉｖｅ Ｍａｓｋｉｎｇ ａｎｄ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ ｏｆ ＡＥＳ"， Ｐｒｏｃ． ｏｆ ＣＨＥＳ ２００２， ｐ．１９８−２１２， ２００２ Ｊ． Ｂｌｏｍｅｒ， Ｊ． Ｇ． Ｍｅｒｃｈａｎ， Ｖ． Ｋｒｕｍｍｅｌ， "Ｐｒｏｖａｂｌｙ Ｓｅｃｕｒｅ Ｍａｓｋｉｎｇ ｏｆ ＡＥＳ"， ［ｏｎｌｉｎｅ］， Ｃｒｙｐｔｏｌｏｇｙ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ， Ｒｅｐｏｒｔ ２００４／１０１， ２００４， インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００４／１０１／＞ Ｍ． Ａｋｋａｒ， Ｒ． Ｂｅｖａｎ， Ｌ． Ｇｏｕｂｉｎ， "Ｔｗｏ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ Ａｔｔａｃｋｓ ａｇａｉｎｓｔ Ｏｎｅ−Ｍａｓｋ Ｍｅｔｈｏｄｓ"， Ｐｒｏｃ． ｏｆ ＦＳＥ ２００４， ｐ．３３２−３４７， ２００４ 鈴木大輔、佐伯稔、市川哲也、「遷移確率を考慮したＤＰＡ対策手法の提案」、ＩＳＥＣ２００４、２００４年７月 森岡澄夫、秋下徹、「合成体を用いたＡＥＳ Ｓ−Ｂｏｘ回路に対するＤＰＡ攻撃」、ＣＳＳ２００４、ｐ．６７９−６８４、２００４年１０月 Ｔ． Ｉｔｏｈ， Ｓ． Ｔｓｕｊｉｉ， "Ａ Ｆａｓｔ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｃｏｍｐｕｔｉｎｇ Ｍｕｌｔｉｐｌｉｃａｔｉｖｅ Ｉｎｖｅｒｓｅ ｉｎ ＧＦ（２ｍ） ｕｓｉｎｇ Ｎｏｒｍａｌ Ｂａｓｅｓ"， Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔａｔｉｏｎ Ｖｏｌ．７８， Ｎｏ．３， ｐ．１７１−１７７， １９８８

非特許文献２に見られる手法では、べき乗演算を行う前に平文に対して乗算マスクを施す。このため、平文の値が０である場合には、乱数を付加しても付加後の出力が０となってしまい、電力解析により暗号鍵を推測されてしまうという課題があった。また、非特許文献３に見られる手法では、１回の非線形処理に対し、７回のＰＭＳと６回のＰＭＭを行う必要がある。１回のＰＭＭの実行に４回の乗算を必要とするため、１回の非線形処理で計算に時間がかかる乗算を２４回行う必要がある。このため、非線形処理の計算に時間がかかってしまうという課題があった。

本発明は、例えば、電力解析への安全性を担保しつつ、乗算回数を削減することで、処理を高速に行うことを目的とする。

本発明の非線形演算装置は、
乱数を生成する乱数生成処理と非線形演算を行い平文に対して生成した乱数を付加する非線形演算処理とを繰り返すことにより平文を暗号化する暗号処理装置に複数備えられ、前記乱数生成処理と前記非線形演算処理とを実行する非線形演算装置において、
前記平文の少なくとも一部を含む入力データｘに補正乱数Ｍが付加された乱数付加データＰ（Ｐ＝ｘ＋Ｍ）を入力するデータ入力部と、
前記補正乱数Ｍを入力する乱数入力部と、
任意の乱数Ｍ´を生成する乱数生成部と、
前記入力データｘのべき乗ｘ^ｅを第１の項とし、
（１）前記乱数入力部が入力した補正乱数Ｍと、（２）前記データ入力部が入力した乱数付加データＰと、（３）前記入力データｘと前記補正乱数Ｍとが乗算された乗算データＭｘとの少なくともいずれかで表現される式を乗算回数が減るように変形した式を第２の項とし、
前記データ入力部が入力した乱数付加データＰのガロア拡大体上のべき乗Ｐ^ｅを、前記第１の項と前記第２の項とを加算する第１の多項式に展開し、
展開した第１の多項式と前記乱数付加データＰのべき乗Ｐ^ｅとを等式の左右の辺としたときの両辺に前記乱数生成部が生成した任意の乱数Ｍ´を加算し、
前記等式を前記入力データｘのべき乗ｘ^ｅと前記乱数生成部が生成した任意の乱数Ｍ´とを加算した出力データＦ_ｅを一方の辺とする式に変形したときの他方の辺となる第２の多項式に基づいて、
前記出力データＦ_ｅを演算して出力するべき乗演算部とを備えることを特徴とする。

本発明では、非線形演算装置のべき乗演算部が、入力データｘに補正乱数Ｍが付加された乱数付加データＰのべき乗Ｐ^ｅと、任意の乱数Ｍ´と、補正乱数Ｍ、乱数付加データＰ、乗算データＭｘのみで表現される式とを加算する多項式を用いて出力データＦ_ｅを演算し、その演算において補正乱数Ｍ、乱数付加データＰ、乗算データＭｘのみで表現される式として乗算回数が少なくなるように変形されたものを用いることにより、非線形演算処理において必要な乗算回数を削減することができる。

本発明の実施の形態について説明する前に用語の定義について説明する。

ここでは、「多項式」とは複数の項を持つ式のことをいう（つまり、単項式を除く）。「式（又は数式）」とは単項式と多項式の両方を含み、定数と不定元の和（加算）と積（乗算）からなるものをいい、式（１）などの式番号を表すために使用する場合以外は等式を含まないこととする。「等式」とは、２つの式が同じ値を持つことを示すためにそれらの式を等号で結合した文字列のことをいう。

以下、本発明の実施の形態について、図を用いて説明する。

実施の形態１．
図１は本実施の形態に係る暗号処理装置の構成を示すブロック図である。暗号処理装置１は排他的論理和部１００、暗号部１０２、拡大鍵生成部１０１からなり、平文２００、乱数２０１、暗号鍵２０２を入力とし、暗号文２０３を出力する。

図２は図１における暗号部１０２の平文入力側部分の構成を示すブロック図である。また、図３は図１における暗号部１０２の暗号文出力側部分の構成を示すブロック図である。暗号部１０２は、非線形演算部１０３〜１１１、線形演算部１１２〜１１４、排他的論理和部１１５〜１１８、補正値演算部１１９〜１２２からなる。

図４は図２及び図３における非線形演算部１０３〜１１１の構成を示すブロック図である。それぞれの非線形演算部は、データ入力部１４０、乱数入力部１４１、べき乗演算部１２７、乱数生成部１２８からなる。

図６は図１に示した暗号処理装置１のハードウェア構成の一例を示す図である。暗号処理装置１は演算部１３０、記憶部１３１、入出力部１３２から構成されている。演算部１３０はＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｏｒ）等に相当する。記憶部１３１はメモリ、ＨＤＤ（ハードディスクドライブ）等に相当し、入出力部１３２はＩ／Ｏ（インプット／アウトプット）ポートに相当する。記憶部１３１はテーブル１３３を予め記憶している。

本実施の形態において、図４に示したべき乗演算部１２７は、演算部１３０の一部に実装される。

例えば、ＣＰＵは、バスを介して、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、通信ボード、表示装置、Ｋ／Ｂ（キーボード）、マウス、ＦＤＤ（Ｆｌｅｘｉｂｌｅ Ｄｉｓｋ Ｄｒｉｖｅ）、ＣＤＤ（コンパクトディスクドライブ）、磁気ディスク装置、光ディスク装置、プリンタ装置、スキャナ装置等と接続されている。

ＲＡＭは、揮発性メモリの一例である。ＲＯＭ、ＦＤＤ、ＣＤＤ、磁気ディスク装置、光ディスク装置は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。

暗号処理装置１が扱うデータや情報は、記憶装置あるいは記憶部に保存され、暗号処理装置１の各部により、記録され読み出されるものである。

また、通信ボードは、例えば、ＬＡＮ、インターネット、或いはＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）に接続されている。

磁気ディスク装置には、オペレーティングシステム（ＯＳ）、ウィンドウシステム、プログラム群、ファイル群（データベース）が記憶されている。

プログラム群は、ＣＰＵ、ＯＳ、ウィンドウシステムにより実行される。

暗号処理装置１の各部は、一部或いはすべてコンピュータで動作可能なプログラムにより構成しても構わない。或いは、ＲＯＭに記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェア或いは、ハードウェア或いは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実施されても構わない。

上記プログラム群には、実施の形態の説明において「〜部」として説明した処理をＣＰＵに実行させるプログラムが記憶される。これらのプログラムは、例えば、Ｃ言語などのコンピュータ言語により作成される。

また、上記プログラムは、磁気ディスク装置、ＦＤ（Ｆｌｅｘｉｂｌｅ Ｄｉｓｋ）、光ディスク、ＣＤ（コンパクトディスク）、ＭＤ（ミニディスク）、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）等のその他の記録媒体に記憶され、ＣＰＵにより読み出され実行される。

次に本実施の形態に係る暗号処理装置の動作について説明する。

図１において、拡大鍵生成部１０１は暗号鍵２０２を入力とし、暗号部１０２で用いる拡大鍵２０５〜２０７を作成する。排他的論理和部１００は平文２００と乱数２０１との排他的論理和を求め、乱数化平文２０４を生成する。暗号部１０２は乱数化平文２０４、乱数２０１、拡大鍵２０５〜２０７を用いて暗号文２０３を出力する。暗号文２０３は公知の暗号法により暗号鍵２０２を用いて平文２００に復号化することが可能なデータである。公知の暗号法としては、例えばＡＥＳ（Ａｄｖａｎｃｅｄ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）等の共通鍵暗号方式を、本実施の形態と合わせて暗号処理に用いることができる。

図２において、補正値演算部１１９は、乱数２０１を入力とし、補正乱数入力２１７〜２１９を出力する。補正値演算部１１９が使用する演算方法は、暗号法により異なる。補正値演算部１２０は、補正乱数出力２３５〜２３７を入力とし、補正乱数入力２２０〜２２２を出力する。乱数化平文２０４はｎビット単位でｋ個の分割入力２０８〜２１０に分けられる。ｎ、ｋの値は暗号法により異なる。非線形演算部１０３〜１０５は、各々の分割入力２０８〜２１０と補正乱数入力２１７〜２１９を入力とし、非線形出力２２６〜２２８と補正乱数出力２３５〜２３７を出力する。線形演算部１１２は非線形出力２２６〜２２８を入力とし、線形出力２４４を出力する。線形演算部１１２が使用する演算方法は、暗号法により異なる。ただし、線形演算部１１２と補正値演算部１１９は同じ演算方法を使用する。排他的論理和部１１５は線形出力２４４と拡大鍵２０５との排他的論理和を求める。排他的論理和部１１５の出力は分割入力２１１〜２１３に分けられる。このような処理を繰り返し、排他的論理和出力２４７と補正乱数出力２３８〜２４０を得る。

図３において、補正値演算部１２１は、補正乱数出力２３８〜２４０を入力とし、補正乱数入力２２３〜２２５を出力する。補正値演算部１２２は、補正乱数出力２４１〜２４３を入力とし、最終補正乱数２４８を出力する。排他的論理和出力２４７はｎビット単位でｋ個の分割入力２１４〜２１６に分けられる。非線形演算部１０９〜１１１は、各々の分割入力２１４〜２１６と補正乱数入力２２３〜２２５を入力とし、非線形出力２３２〜２３４と補正乱数出力２４１〜２４３を出力する。線形演算部１１４は非線形出力２３２〜２３４を入力とし、線形出力２４６を出力する。排他的論理和部１１７は線形出力２４６と拡大鍵２０７との排他的論理和を求める。排他的論理和部１１８は排他的論理和部１１７の出力と最終補正乱数２４８との排他的論理和を求め、暗号文２０３を出力する。

説明の便宜上、以降では、それぞれの非線形演算部において、分割入力２０８〜２１６を分割入力Ｐ、非線形出力２２６〜２３４を非線形出力Ｆ_ｅ、補正乱数入力２１７〜２２５を補正乱数入力Ｍ、補正乱数出力２３５〜２４３を補正乱数出力Ｍ´と表記する。また、分割入力Ｐを、乱数化平文２０４が８ビット単位（バイトごと）に分割されたデータとする（ｎ＝８）。

図４において、データ入力部１４０は分割入力Ｐを入力する。乱数入力部１４１は補正乱数入力Ｍを入力する。乱数生成部１２８は乱数Ｍ´、Ｎを生成する。ここで、乱数ＮはＭと相関がない必要があるが、乱数Ｍ´は任意でよい。

べき乗演算部１２７は分割入力Ｐ、補正乱数入力Ｍ、乱数Ｍ´、Ｎを入力とし、非線形出力Ｆ_ｅを出力する。ただし、Ｆ_ｅはＦ_ｅ＝ｘ^ｅ＋Ｍ´を満たす。ここで、ｘは分割入力Ｐに含まれる暗号化すべきデータ（入力データ）である。＋（プラス）は排他的論理和演算を示す。ｅの値は暗号法により異なる（特に、−１、２４７、２５１が使われる）。

本実施の形態では、ｅ＝−１（入力の逆元）として説明する。

以下に示すように、べき乗演算部１２７は指数ｅについて、（ｘ＋Ｍ）^ｅを多項式上に展開し、ｘ^ｅ以外の項について、ｘとＭを用いて表現した式を乗算回数が最少に（又は少なく）なるように変形した後（式（７））、ｘ^ｅをｘとＭを用いて表現し、両辺に乱数Ｍ´を付加した式（式（２））を用いる。

べき乗演算部１２７は、式（２）を演算する。ただし、全ての加算及び乗算はガロア拡大体ＧＦ（２^８）上で行う。

式（２）において、Ｍｘを求める際、単純にｘと乱数Ｍとを乗算すると、ｘの値が０の場合に電力解析に対して脆弱になってしまう。そこで、式（８）のようにＭｘのべき乗を求めてもよい。

電力解析への対策を行う上で、処理に関わる全ての演算による出力の分布が暗号化すべきデータｘに依存しないことが必要であるということが知られている（例えば、非特許文献３及び非特許文献４）。式（８）においては、Ｍ（ｘ＋Ｍ）を求める際、ｘが０のときとｘが０でないときとで値の分布に変化が生じるため、電力解析に対する安全性を担保することができない。そこで、本実施の形態では、べき乗演算部１２７は、式（８）の（ｘ＋Ｍ）に乱数Ｍと乱数Ｎとの和を付加した式（１）を演算する。

また、前述したように、ｘの値が０の場合に電力解析に対して脆弱になってしまうことを避けるため、式（２）における（ｘ＋Ｍ）^ａ＋（Ｍｘ）^ｂＧを計算する際に、（Ｍｘ）^ｂＧを２つ以上の項の和に分解した上で、その１つと（ｘ＋Ｍ）^ａとの加算を先に行う。ただし、Ｇは式（２）において、（Ｍｘ）^ｂより右にある多項式であるとする。さらに式（２）において、Ｍ´を加算する前にｘ^−１＋Ｍ^−１＋（Ｍｘ）^２Ｈは求めない。ここで、Ｈは式（２）において、（Ｍｘ）^２より右にある多項式を示す。

具体的には、べき乗演算部１２７は、以下の処理ステップを実行する。ステップ２〜８では、カッコ内の加算を先に行うものとする。

図６は本実施の形態に係る暗号処理装置のハードウェア構成の一例を示す図である。演算部１３０は定められた手順に従い、記憶部１３１及び入出力部１３２を駆動したり、演算を行ったりする。記憶部１３１は演算部１３０により、データの保持、読み出しを行う。入出力部１３２は暗号処理装置の外部からデータを入力し、演算結果を出力する。テーブル１３３は一入力一出力の演算について、全て又は一部の入力に対する出力を保持する表である。演算部１３０はこのような入力に対して、演算結果を出力するのではなく、テーブル１３３を参照して、入力に対応する値を取得し、この値を出力する。

本実施の形態では、テーブル１３３は入力の２乗、１２８乗、１３０乗、１９４乗、２２６乗、２４２乗、２５０乗及び逆元（−１乗）を計算して得られる結果を予め表として保持する。演算部１３０は、入力のべき乗を求めるために、テーブル１３３の求めるべき指数の計算結果を参照する。ここで、テーブル１３３の２乗の計算結果のみを用い、これを乗算と組み合わせることで入力のべき乗を求めることもできる。また、テーブル１３３が入力のべき乗の計算結果を一部だけ保持し、テーブル１３３にない値は演算部１３０が演算して求めてもよい。さらに、暗号処理装置１がテーブル１３３を持たず、演算部１３０が入力のべき乗をすべて演算して求めてもよい。

このように、本実施の形態では、べき乗演算部１２７は式（１）と式（２）の計算過程において、ｘ及びｘにのみ依存する演算結果を求めない。例えば、暗号化すべきデータｘを含む項にＰとＭ_Ｐがあるが、全ての演算過程において、常に乱数が付加された状態で演算される。よって、べき乗演算部１２７の計算過程において電力解析に対する安全性を保障できる。

また、本実施の形態では、べき乗演算部１２７中の全ての加算・乗算及びべき乗演算について、各オペランドに互いに独立な乱数成分が付加されるため、当該演算による出力の分布が暗号化すべきデータｘに依存しない。例えば、（ステップ１）のＰ_Ｎ＝Ｐ＋（Ｍ＋Ｎ）の右辺第１項と第２項との加算の入力については、一方にはＭが、他方にはＭ、Ｎが付加されている。また、Ｍ_Ｐ ^１＝ＭＰ_Ｎの乗算の入力については、一方にはＭが、他方にはＮが付加されている。他の全ての演算についても同様である。これによって、さらに、べき乗演算部１２７の計算過程において電力解析に対する安全性を保障できる。

本実施の形態では、べき乗演算部１２７が、分割入力Ｐのべき乗Ｐ^−１と、乱数Ｍ´と、補正乱数入力Ｍ、分割入力Ｐ、補正乱数入力Ｍと暗号化すべきデータｘを乗算したＭｘのみで表現される式とを加算する多項式を用いて出力データＦ_−１を演算し、その演算においてＭ、Ｐ、Ｍｘのみで表現される式として乗算回数が少なくなるように変形されたものを用いることにより、１回のべき乗計算に必要な乗算回数を削減することができる。

本実施の形態では、入力のべき乗を求める処理をテーブル１３３で実現することができるため、１回のべき乗計算に必要な乗算回数をさらに削減することができる。具体的には、べき乗演算部１２７が１回のべき乗計算に行う乗算回数は、非特許文献３の２４回に対して１４回に削減できる。テーブル１３３による値の参照は乗算に対して高速に実行可能であるため、べき乗計算を従来の技術より高速に行うことができる。例えば、非特許文献７では逆元の計算方法において乗算回数を削減する方式が開示されており、この方式を非特許文献３の方式と組み合わせる方法も考えられる（実施の形態７の説明を参照）が、本実施の形態に係る非線形演算方法ではこれよりもさらに乗算回数を削減することが可能である。

実施の形態２．
本実施の形態に係る暗号処理装置は、実施の形態１のものと同様である。実施の形態１と同様に、本実施の形態に係る暗号処理装置において、図４に示すべき乗演算部１２７が分割入力Ｐ、補正乱数入力Ｍ、乱数Ｍ´、Ｎを入力とし、非線形出力Ｆ_ｅを出力する。

本実施の形態では、ｅ＝２４７として説明する。

以下に示すように、べき乗演算部１２７は指数ｅについて、（ｘ＋Ｍ）^ｅを多項式上に展開し、ｘ^ｅ以外の項について、ｘとＭを用いて表現した式を乗算回数が最少に（又は少なく）なるように変形した後（式（９））、ｘ^ｅをｘとＭを用いて表現し、両辺に乱数Ｍ´を付加した式（式（３））を用いる。

べき乗演算部１２７は、式（３）を演算する。ただし、全ての加算及び乗算はガロア拡大体ＧＦ（２^８）上で行う。なおかつ、電力解析に対する安全性を担保するために、式（１）を演算する。

また、ｘの値が０の場合に電力解析に対して脆弱になってしまうことを避けるため、式（３）における（ｘ＋Ｍ）^ａ＋（Ｍｘ）^ｂＧ´を計算する際に、（Ｍｘ）^ｂＧ´を２つ以上の項の和に分解した上で、その１つと（ｘ＋Ｍ）^ａとの加算を先に行う。ただし、Ｇ´は式（３）において、（Ｍｘ）^ｂより右にある多項式であるとする。さらに式（３）において、Ｍ´を加算する前にｘ^２４７＋ＭＨ´は求めない。ここで、Ｈ´は式（３）において、Ｍより右にある多項式を示す。

具体的には、べき乗演算部１２７は、以下の処理ステップを実行する。ステップ２〜９では、カッコ内の加算を先に行うものとする。

本実施の形態では、図６に示したテーブル１３３は入力の２乗、４乗、８乗、１２８乗、１９２乗、２２４乗、２４０乗、２４４乗、２４６乗及び２４７乗を計算して得られる結果を予め表として保持する。図６の演算部１３０は、入力のべき乗を求めるために、テーブル１３３の求めるべき指数の計算結果を参照する。ここで、テーブル１３３の２乗の計算結果のみを用い、これを乗算と組み合わせることで入力のべき乗を求めることもできる。また、テーブル１３３が入力のべき乗の計算結果を一部だけ保持し、テーブル１３３にない値は演算部１３０が演算して求めてもよい。さらに、暗号処理装置１がテーブル１３３を持たず、演算部１３０が入力のべき乗をすべて演算して求めてもよい。

本実施の形態は、実施の形態１と同様の効果を奏する。

実施の形態３．
本実施の形態に係る暗号処理装置の構成及び動作は、図１に示した実施の形態１のものと同様である。暗号処理装置１の暗号部１０２の構成及び動作も、図２及び図３に示した実施の形態１のものと同様である。また、本実施の形態においても、図６に示したハードウェア構成により暗号処理装置１を実装することができる。以下では、主に本実施の形態における実施の形態１との差異について説明する。

図５は図２及び図３における非線形演算部１０３〜１１１の構成を示すブロック図である。それぞれの非線形演算部は、アフィン変換部１２３〜１２６、データ入力部１４０、乱数入力部１４１、べき乗演算部１２７、乱数生成部１２８からなる。

説明の便宜上、以降では、それぞれの非線形演算部において、分割入力２０８〜２１６を分割入力Ｐ、非線形出力２２６〜２３４を非線形出力Ｙ、補正乱数入力２１７〜２２５を補正乱数入力Ｍ、補正乱数出力２３５〜２４３を補正乱数出力Ｄ_Ｍ´と表記する。また、分割入力Ｐを、乱数化平文２０４が８ビット単位（バイトごと）に分割されたデータとする（ｎ＝８）。

図５において、データ入力部１４０は分割入力Ｐを入力する。乱数入力部１４１は補正乱数入力Ｍを入力する。分割入力Ｐはアフィン変換部１２３によりアフィン変換出力Ａ_Ｐに変換される。補正乱数入力Ｍはアフィン変換部１２４によりアフィン変換出力Ｂ_Ｍに変換される。乱数生成部１２８は乱数Ｍ´、Ｎを生成する。ここで、乱数ＮはＭと相関がない必要があるが、乱数Ｍ´は任意でよい。

アフィン変換部１２６はべき乗演算出力Ｆ_ｅを入力とし、非線形出力Ｙを出力する。

アフィン変換部１２５は乱数Ｍ´を入力とし、補正乱数出力Ｄ_Ｍ´を出力する。

べき乗演算部１２７はアフィン変換出力Ａ_Ｐ、Ｂ_Ｍ、乱数Ｍ´、Ｎを入力とし、べき乗演算出力Ｆ_ｅを出力する。ただし、Ｆ_ｅはＦ_ｅ＝（Ａ_ｘ）^ｅ＋Ｍ´を満たす。ここで、Ａ_ｘはｘをアフィン変換部１２３に入力した場合の出力であり、ｘは分割入力Ｐに含まれる暗号化すべきデータ（入力データ）である。＋（プラス）は排他的論理和演算を示す。ｅの値は暗号法により異なる。

本実施の形態では、ｅ＝−１（入力の逆元）として説明する。

以下に示すように、べき乗演算部１２７は指数ｅについて、（Ａ_ｘ＋Ｂ_Ｍ）^ｅを多項式上に展開し、Ａ_ｘ ^ｅ以外の項について、Ａ_ＰとＢ_Ｍを用いて表現した式を乗算回数が最少に（又は少なく）なるように変形した後、Ａ_ｘ ^ｅをＡ_ＰとＢ_Ｍを用いて表現し、両辺に乱数Ｍ´を付加した式（式（４）及び式（５））を用いる。

べき乗演算部１２７は、式（４）及び式（５）を演算する。ただし、全ての加算及び乗算はガロア拡大体ＧＦ（２^８）上で行う。なおかつ、電力解析に対する安全性を担保するために、式（４）においてアフィン変換出力Ａ_Ｐに乱数Ｂ_Ｍと乱数Ｎとの和を付加する。また、式（５）におけるＡ_Ｐ ^ａ＋（Ｍ_ｘ）^ｂＧを計算する際に、（Ｍ_ｘ）^ｂＧを２つ以上の項の和に分解した上で、その１つとＡ_Ｐ ^ａとの加算を先に行う。ただし、Ｇは式（５）において、（Ｍ_ｘ）^ｂより右にある多項式であるとする。さらに式（５）において、Ｍ´を加算する前にＡ_Ｐ ^−１＋Ｂ_Ｍ ^−１＋（Ｍ_ｘ）^２Ｈは求めない。ここで、Ｈは式（５）において、（Ｍ_ｘ）^２より右にある多項式を示す。

具体的には、べき乗演算部１２７は、以下の処理ステップを実行する。ステップ２〜８では、カッコ内の加算を先に行うものとする。

このように、本実施の形態では、べき乗演算部１２７は式（４）と式（５）の計算過程において、ｘ及びｘにのみ依存する演算結果を求めない。例えば、暗号化すべきデータｘを含む項にＡ_ＰとＭ_Ｐがあるが、全ての演算過程において、常に乱数が付加された状態で演算される。よって、べき乗演算部１２７の計算過程において電力解析に対する安全性を保障できる。

また、本実施の形態では、べき乗演算部１２７中の全ての加算・乗算及びべき乗演算について、各オペランドに互いに独立な乱数成分が付加されるため、当該演算による出力の分布が暗号化すべきデータｘに依存しない。例えば、（ステップ１）のＰ_Ｎ＝Ａ_Ｐ＋（Ｂ_Ｍ＋Ｎ）の右辺第１項と第２項との加算の入力については、一方にはＢ_Ｍが、他方にはＢ_Ｍ、Ｎが付加されている。また、Ｍ_Ｐ ^１＝Ｂ_ＭＰ_Ｎの乗算の入力については、一方にはＢ_Ｍが、他方にはＮが付加されている。他の全ての演算についても同様である。これによって、さらに、べき乗演算部１２７の計算過程において電力解析に対する安全性を保障できる。

以上のように、実施の形態３で説明した耐タンパ暗号処理方法は、
ガロア拡大体上のべき乗演算において、乱数を付加された入力のべき乗を多項式上に展開し、それを用いて、入力のべき乗を乱数及び乱数を付加された入力のみで表現し、展開した式を乗算回数が最小となるように変形し、変形した式を用いて演算を実行することを特徴とする。

上記耐タンパ暗号処理方法は、例えば、ガロア拡大体上のべき乗演算において、前述した式（４）及び式（５）を用いて、Ｆ_−１を計算することを特徴とする。

上記耐タンパ暗号処理方法は、Ｍ_ｘを計算する際に、Ａ_ＰにＢ_Ｍ＋Ｎを加算することを特徴とする。

上記耐タンパ暗号処理方法は、Ａ_Ｐ ^ａ＋（Ｍ_Ｘ）^ｂＧ_１を計算する際に、（Ｍ_Ｘ）^ｂＧ_１を２つ以上の項の和に分解した上で、その１つとＡ_Ｐ ^ａとの加算を先に行うことを特徴とする。ただし、Ｇ_１は式（５）において、（Ｍ_Ｘ）^ｎより右にある多項式である。

上記耐タンパ暗号処理方法は、Ａ_Ｐ、Ｍ´、Ｍ_Ｐ及びＭ_Ｎのべき乗の計算に、あらかじめ指数ごとに用意しておいた変換表を用いることを特徴とする。

上記耐タンパ暗号処理方法は、Ａ_Ｐ、Ｍ´、Ｍ_Ｐ及びＭ_Ｎのべき乗の計算に、例えば、入力の２乗を求める変換表と、その出力との乗算を組み合わせることを特徴とする。

実施の形態４．
本実施の形態に係る暗号処理装置は、実施の形態３のものと同様である。実施の形態３と同様に、本実施の形態に係る暗号処理装置において、図５に示すべき乗演算部１２７がアフィン変換出力Ａ_Ｐ、Ｂ_Ｍ、乱数Ｍ´、Ｎを入力とし、べき乗演算出力Ｆ_ｅを出力する。

本実施の形態では、ｅ＝２４７として説明する。

以下に示すように、べき乗演算部１２７は指数ｅについて、（Ａ_ｘ＋Ｂ_Ｍ）^ｅを多項式上に展開し、Ａ_ｘ ^ｅ以外の項について、Ａ_ＰとＢ_Ｍを用いて表現した式を乗算回数が最少に（又は少なく）なるように変形した後、Ａ_ｘ ^ｅをＡ_ＰとＢ_Ｍを用いて表現し、両辺に乱数Ｍ´を付加した式（式（４）及び式（６））を用いる。

べき乗演算部１２７は、式（４）及び式（６）を演算する。ただし、全ての加算及び乗算はガロア拡大体ＧＦ（２^８）上で行う。なおかつ、電力解析に対する安全性を担保するために、式（４）においてアフィン変換出力Ａ_Ｐに乱数Ｂ_Ｍと乱数Ｎとの和を付加する。また、式（６）におけるＡ_Ｐ ^ａ＋（Ｍ_ｘ）^ｂＧ´を計算する際に、（Ｍ_ｘ）^ｂＧ´を２つ以上の項の和に分解した上で、その１つとＡ_Ｐ ^ａとの加算を先に行う。ただし、Ｇ´は式（６）において、（Ｍ_ｘ）^ｂより右にある多項式であるとする。さらに式（６）において、Ｍ´を加算する前にＡ_Ｐ ^２４７＋Ｂ_ＭＨ´は求めない。ここで、Ｈ´はＭより右にある多項式を示す。

具体的には、べき乗演算部１２７は、以下の処理ステップを実行する。ステップ２〜９では、カッコ内の加算を先に行うものとする。

本実施の形態では、図６に示したテーブル１３３は入力の２乗、４乗、８乗、１２８乗、１９２乗、２２４乗、２４０乗、２４４乗、２４６乗及び２４７乗を計算して得られる結果を予め表として保持する。図６の演算部１３０は、入力のべき乗を求めるために、テーブル１３３の求めるべき指数の計算結果を参照する。ここで、テーブル１３３の２乗の計算結果のみを用い、これを乗算と組み合わせることで入力のべき乗を求めることもできる。また、テーブル１３３が入力のべき乗の計算結果を一部だけ保持し、テーブル１３３にない値は演算部１３０が演算して求めてもよい。さらに、暗号処理装置１がテーブル１３３を持たず、演算部１３０が入力のべき乗をすべて演算して求めてもよい。

本実施の形態は、実施の形態３と同様の効果を奏する。

以上のように、実施の形態４で説明した耐タンパ暗号処理方法は、
ガロア拡大体上のべき乗演算において、乱数を付加された入力のべき乗を多項式上に展開し、それを用いて、入力のべき乗を乱数及び乱数を付加された入力のみで表現し、展開した式を乗算回数が最小となるように変形し、変形した式を用いて演算を実行することを特徴とする。

上記耐タンパ暗号処理方法は、例えば、ガロア拡大体上のべき乗演算において、前述した式（４）及び式（６）を用いて、Ｆ_２４７を計算することを特徴とする。

上記耐タンパ暗号処理方法は、Ｍ_ｘを計算する際に、Ａ_ＰにＢ_Ｍ＋Ｎを加算することを特徴とする。

上記耐タンパ暗号処理方法は、Ａ_Ｐ ^ａ＋（Ｍ_Ｘ）^ｂＧ_２を計算する際に、（Ｍ_Ｘ）^ｎＧ_２を２つ以上の項の和に分解した上で、その１つとＡ_Ｐ ^ａとの加算を先に行うことを特徴とする。ただし、Ｇ_２は式（６）において、（Ｍ_Ｘ）^ｂより右にある多項式である。

上記耐タンパ暗号処理方法は、Ａ_Ｐ、Ｍ´、Ｍ_Ｐ及びＭ_Ｎのべき乗の計算に、あらかじめ指数ごとに用意しておいた変換表を用いることを特徴とする。

上記耐タンパ暗号処理方法は、Ａ_Ｐ、Ｍ´、Ｍ_Ｐ及びＭ_Ｎのべき乗の計算に、例えば、入力の２乗を求める変換表と、その出力との乗算を組み合わせることを特徴とする。

実施の形態５．
実施の形態１から４までに係る暗号処理装置は、図７に示すハードウェア構成により実装することもできる。図６の構成では記憶部１３１の内部にテーブル１３３を保持していたが、本実施の形態では演算部１３０の内部にテーブル演算部１３４を持つ。例えば、演算部１３０がＣＰＵであれば、ＣＰＵと同一チップ内にテーブル演算部１３４を実装する。図６に示したハードウェア構成の例は主に汎用計算機を対象としているが、図７に示したハードウェア構成の例は主に専用ハードウェアを対象としている。

本実施の形態において、図４に示したべき乗演算部１２７は、テーブル演算部１３４を含む演算部１３０の一部とに実装される。

テーブル演算部１３４は入力の２乗、４乗、８乗、１２８乗、１３０乗、１９２乗、１９４乗、２２４乗、２２６乗、２４０乗、２４２乗、２４４乗、２４６乗、２４７乗、２５０乗及び逆元（−１乗）を演算する回路である。演算部１３０は、入力のべき乗を求めるために、テーブル演算部１３４に求めるべき指数の計算をさせる。ここで、テーブル演算部１３４に２乗の計算のみをさせ、その計算結果を乗算と組み合わせることで入力のべき乗を求めることもできる。また、テーブル演算部１３４が入力のべき乗の計算を一部だけ行い、テーブル演算部１３４が計算しない値は演算部１３０が演算して求めてもよい。

本実施の形態では、テーブル演算部１３４をハードウェアとして演算部１３０に組み込むことでより高速の演算が可能となる。また、本実施の形態では、演算部１３０とテーブル演算部１３４とを１つのパッケージに封入することができる。これにより、プローブ解析に対する抗力が向上する。

実施の形態６．
実施の形態１から４までに係る暗号処理装置は、図８に示すハードウェア構成により実装することもできる。実施の形態５で説明した図７の構成では演算部１３０の内部にテーブル演算部１３４を持っていたが、本実施の形態ではテーブル演算部１３４を演算部１３０、記憶部１３１、入出力部１３２とは独立に実装する。図７に示したハードウェア構成の例は主に専用ハードウェアを対象としているが、図８に示したハードウェア構成の例は主にコプロセッサシステムを対象としている。

本実施の形態において、図４に示したべき乗演算部１２７は、演算部１３０の一部とテーブル演算部１３４に実装される。

本実施の形態では、テーブル演算部１３４をハードウェアで実現するとともに、演算部１３０と独立させた構成とすることでテーブル演算部１３４の変更を容易に行うことができる。

実施の形態７．
以下では、本実施の形態に係る暗号処理装置の「マスク付き入力の多項式展開によるガロア体上の逆元演算マスク法」について説明する。説明の一部は背景技術や他の実施の形態に関する記述と重複するが、本実施の形態の説明で使用する番号、記号、符号などは、説明が重複する部分においても異なるものを示す場合がある。例えば、実施の形態１と本実施の形態とのどちらの説明にも使用されている記号がある場合、この記号が実施の形態１で意味するものと本実施の形態で意味するものとは必ずしも同じとは限らない。また、逆に、同じものを示す場合であっても、異なる番号、記号、符号などを用いる場合がある。

ソフトウェア実装した暗号装置の電力解析等への対策として、暗号前の入力に乱数でマスクした上で暗号化を行い、出力にマスクをかけなおすことで、内部変数を推定されないようにする手法がある。これらの手法では、入力にマスクがかかっていても正しく計算が行えるよう、元のアルゴリズムを改良している。これらのアルゴリズムの改良においては、Ｓ−Ｂｏｘの演算法が課題となる。ＡＥＳをはじめとして、安全性を担保した多くの暗号では、Ｓ−Ｂｏｘにガロア体上の逆元演算とアフィン変換を組み合わせたものを用いている。乱数のマスクを考慮したＳ−Ｂｏｘの実装には、逆元演算の前に加算マスクから乗算マスクに変更する方法や、乱数の付加を考慮した二乗器と乗算器を提案し、それらを組み合わせて実装する方法などがある。しかしながら、特定の入力でマスクの効果が消えたり、多重の演算により計算コストが増大したりしている。本実施の形態では、入力と乱数を加算したものの逆元が多項式上でどのように展開されるかに着目し、展開した式を元に、それを安全に実装する手法を提案し、その有効性を検証する。

１．はじめに
１９９９年にＫｏｃｈｅｒらが提案した電力差分解析（ＤＰＡ）（非特許文献１）は、ソフトウェア実装・ハードウェア実装を問わず実行可能なため、近年、その対策法に注目が集まっている。ハードウェア実装においてはＲＳＬ（非特許文献５）をはじめとするゲートレベルでの対策を行う手法が確立しつつある。一方、ソフトウェア実装においては、暗号前の入力に乱数でマスクしたうえで暗号化を行い、出力にマスクをかけなおす手法が提案されているが、暗号中のＳ−Ｂｏｘの処理に課題がある。

ＡＥＳをはじめとして、安全性を担保した多くの暗号では、Ｓ−Ｂｏｘにガロア体上の逆元演算とアフィン変換を組み合わせたものを用いている。これまでに、入力に排他的論理和を行う加算マスクや入力にガロア体上の乗算を行う乗算マスクが提案されてきた。しかし、前者は逆元演算を通過させることが難しく、後者はアフィン変換を通過させることが困難となっている。

Ｇｏｌｉｃらは、加算マスクされた入力に対し、逆元演算の直前に乗算マスクに変換し、逆元演算の直前に加算マスクに変更する手法を提案した（非特許文献２）。しかし、乗算マスクには、「マスクされるデータが０である場合にデータがマスクされない」ことを利用した攻撃が可能であるという問題がある。また、Ｂｌｏｍｅｒらは、マスク付きの二乗演算と乗算演算を定義し、それらを組み合わせる手法を提案した（非特許文献３）。しかしながらこの手法では、多くの二乗演算と乗算演算、特に乗算を多く用いるため、演算コストがかさむ。

本実施の形態では、入力に加算マスクされた変数の逆元が多項式上でどのように展開されるかに着目し、それを基にした逆元演算法であるＳＭＤＭ（Ｓｅｃｕｒｅ Ｍａｓｋｉｎｇ ｗｉｔｈ ｔｈｅ Ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｆｕｎｃｔｉｏｎ ｏｆ Ｍａｓｋｅｄ ｉｎｐｕｔ）を提案する。提案法により、乗算回数を削減することで、演算の高速化を図る。

本実施の形態では、入力と乱数を加算したものの逆元が多項式上でどのように展開されるかについて示す。また、展開した式を元に、それを安全に実装する手法を提案し、その有効性を検証する。

２．従来の入力へのマスク付き逆元演算法
２．１．マスクのかけかえを行う逆元演算法
図９にＧｏｌｉｃらの提案した手法の概略を示す。マスクＭａにより加算マスクされた入力Ｘは、逆元演算を行う前に、マスクＭｂにより乗算マスクに変更され、逆元の演算が行われた後に再び加算マスクに変更される。

この手法の場合、Ｘ＝０の場合は任意のマスクＭｂに対して、ｘ^−１の直前の値が０になるため、そこを突いたＤＰＡが可能である。

２．２．マスク付きの二乗演算と乗算演算を組み合わせる手法
Ｂｌｏｍｅｒらは、マスク付きの二乗演算（Ｐｅｒｆｅｃｔｌｙ Ｍａｓｋｅｄ Ｓｑｕａｒｅ：ＰＭＳ）と乗算演算（Ｐｅｒｆｅｃｔｌｙ Ｍａｓｋｅｄ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ：ＰＭＭ）を定義し、それらを組み合わせる手法を提案した。ＰＭＳ・ＰＭＭと逆元の計算法を以下に示す。

Ｂｌｏｍｅｒらの手法では、ＰＭＳを７回、ＰＭＭを６回行っている。ＰＭＳを加算とテーブル参照で実装したとしても、１回の逆元の計算で加算を３８回、乗算を２４回行っていることになる。Ｂｌｏｍｅｒらの手法は、ハードウェア実装に向くように設計されている。しかしながら、ソフトウェア実装では、乗算に多大な演算コストがかかるため、できるだけ乗算回数を減らす必要がある。

これらに対し、本実施の形態では乱数でマスクされた入力の逆元を多項式上に展開するという観点からマスクつき入力の逆元を求める手法を提案する。また、全ての演算の値の確率分布がマスク前の入力に依存しないアルゴリズムを提案する。提案法では、乗算の代わりにメモリ参照と加算を演算の中心とすることで、乗算回数を削減し、処理の高速化を図る。

３．提案法
３．１．加算マスクの入った入力の逆元の展開
提案法を示す前に式入力ｘがＭにより加算マスクされた場合の逆元（ｘ＋Ｍ）^−１がどのように展開されるかを示す。（ｘ＋Ｍ）^−１＝（ｘ＋Ｍ）^２５４ ｏｖｅｒ ＧＦ（２^８）であるため、以降（ｘ＋Ｍ）^２５４について論じる。事前準備として補題１を示す。

証明は数学的帰納法により容易に行うことができるため、本実施の形態では省略する。さて、補題１より、（ｘ＋Ｍ）^２５４は式（１０）のように展開できる。

式（１０）はさらに式（１１）に変形できる。ただし、ρ（ｘ）は式（１２）となる。

式（１１）により、入力をＰ＝ｘ＋Ｍ、Ｍ、Ｍ_ｎｅｗとし、出力をｘ^−１＋Ｍ_ｎｅｗとする関数は式（１３）で記述できる。式（１３）中の（Ｍｘ）^２ｎを求める方法はいくつかあるが、例えば式（１４）で求めることができる。

３．２．Ｓｅｃｕｒｅ Ｍａｓｋｉｎｇ ｗｉｔｈ ｔｈｅ Ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｆｕｎｃｔｉｏｎ ｏｆ Ｍａｓｋｅｄ ｉｎｐｕｔ
３．１節では、式（１３）（１４）を計算することで、ｘ^−１を陽に計算せずにｘ^−１＋Ｍ_ｎｅｗを計算できることを示した。しかしながら、式（１３）（１４）を計算する場合、いくつかの問題点がある。

問題点１：（Ｍｘ）^ｎの演算結果をそのまま次の演算（乗算）に用いると、その部分をＺｅｒｏ−Ｖａｌｕｅ−Ａｔｔａｃｋにより解析される恐れがある。

問題点２：Ｍｘを式（１４）で計算した場合、ｘが０の場合とそうでない場合とで、ＭＰの取りうる値の分布が変化する。

そこで本実施の形態では、上記問題を解決すべく、式（１３）を安全性を担保しながら演算を行う手法Ｓｅｃｕｒｅ Ｍａｓｋｉｎｇ ｗｉｔｈ ｔｈｅ Ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｆｕｎｃｔｉｏｎ ｏｆ Ｍａｓｋｅｄ ｉｎｐｕｔ（ＳＭＤＭ）を提案する。以下にそのアルゴリズムを示す。アルゴリズム中にあるｒａｎｄ（）は乱数生成を示す。

提案法では、べき乗演算をテーブル参照で実現することで、１回の逆元の計算で加算を１６回、乗算を１４回で行うことができるため、高速な処理を期待できる。

３．３．提案アルゴリズムの安全性
本節では、３．２節において提案したアルゴリズムの安全性について考察する。

問題点１への対策として、（Ｍｘ）^ｋＴ_ｊ＝（Ｍ_Ｐ ^ｋ＋Ｍ_Ｎ ^ｋ）Ｔ_ｊをＭ_Ｐ ^ｋＴ_ｊとＭ_Ｎ ^ｋＴ_ｊとに分配して計算し、Ｍ_Ｐ ^ｋＴ_ｊとＰ^ｎとの加算を先に行うようにした。このことにより、任意の演算出力は、任意のマスク前の入力に対してマスクの影響を受けるようになる。

また、問題点２は特に乗算において注意する必要がある。その対策としてＰに対してマスクのかけ換えを行うようにした。これにより、全ての乗算において２つのオペランドに互いに独立な乱数がかかるため、問題点２を回避できるものと考える。

以下、各々の演算についてその安全性を議論する。議論に先立ち、補題２、補題３を示す（非特許文献３）。

（１）ＭＮ、Ｍ_Ｎ ^ｎ
ｘを含んでいないのでその分布はｘに依存しないのは明らかである。

（２）Ｐ_Ｎ
補題２よりその分布は一様分布を示す。

（３）ＭＰ_Ｎ
Ｍ、Ｎは独立であるため、補題３よりその分布はｘに依存しない。

（４）Ｍ_Ｐ ^ｎ、Ｔ_０（＝Ｐ^２）、Ｐ^ｎ
任意の指数計算は１入力１出力のテーブルで表現できる。よって、テーブル出力の分布はテーブル入力の分布とテーブル値に依存する。テーブルへの入力であるＭＰ_Ｎ、Ｐの分布はｘに依存しないため、テーブル出力の分布もｘに依存しない。

（５）Ｔ_ｋ＋１＝（Ｍ_Ｐ ^ｎＴ_ｋ＋Ｐ^ｍ）＋Ｍ_Ｎ ^ｎＴ_ｋ
この部分の安全性の議論には森岡らの判定法を用いることとする（非特許文献６）。

（ａ）提案アルゴリズムより、ＭａｓｋＳｅｔ（Ｍ_Ｐ ^ｎ）、ＭａｓｋＳｅｔ（Ｍ_Ｎ ^ｎ）、ＭａｓｋＳｅｔ（Ｐ^ｍ）はそれぞれ式（１６）（１７）（１８）となる。

（ｂ）ｋ＝０の場合、ＭａｓｋＳｅｔ（Ｔ_０）、ＭａｓｋＳｅｔ（Ｍ_Ｐ ^ｎＴ_０）、ＭａｓｋＳｅｔ（Ｍ_Ｎ ^ｎＴ_０）、ＭａｓｋＳｅｔ（Ｍ_Ｐ ^ｎＴ_０＋Ｐ^ｍ）、ＭａｓｋＳｅｔ（Ｔ_１）はそれぞれ式（１９）〜（２３）となる。式（２３）においてＭ_Ｐ ^ｎＴ_０とＭ_Ｎ ^ｎＴ_０が加算された時点でＮによる影響がなくなることに注意する。

（ｃ）ｋ＞０の場合、ＭａｓｋＳｅｔ（Ｔ_ｋ）＝｛Ｍ｝より、ｋ＝０の時と同様にＭａｓｋＳｅｔ（Ｔ_ｋ＋１）＝｛Ｍ｝となる。

以上より、０≦ｋにおいて、全ての演算過程ｆ（ｘ）においてＭａｓｋＳｅｔ（ｆ（ｘ））≠φとなるので、この部分の演算の出力分布はｘに依存しない。

（６）Ｏｕｔｐｕｔ＝（Ｍ´＋Ｍ_２５４）＋Ｔ_６
Ｍ´、Ｍ_２５４およびＴ_６がｘに依存しないため、Ｏｕｔｐｕｔの分布はｘに依存しない。

４．実験
４．１．速度比較
提案法の有効性を示すため、Ｂｌｏｍｅｒらの手法と実行速度の比較を行った。また、ＢｌｏｍｅｒらのＰＭＳ・ＰＭＭと伊東・辻井のアルゴリズム（非特許文献７）を組み合わせた手法についても比較を行った。実験条件を以下に示す。

条件１：ＣＰＵ：Ｉｎｔｅｌ（登録商標） Ｘｅｏｎ ３．２０ＧＨｚ、ＯＳ：Ｌｉｎｕｘ（登録商標）、コンパイラ：ｇｃｃ Ｖｅｒ ３．２
条件２：ＣＰＵ：Ｒｅｎｅｓａｓ（登録商標） ＳＨ（登録商標）−４、コンパイラ・シミュレータ：Ｒｅｎｅｓａｓ（登録商標） ＨＥＷ Ｖｅｒ ３．０．０５
演算回数を比較した結果を図１０の表に示す。今回の実験では、指数計算を全て１回のテーブル参照で実装した。

Ｂｌｏｍｅｒらの手法に対して、テーブル参照の回数は増加したが、加算回数および乗算回数は従来に比べ減少した。

また、速度を比較した結果を図１１の表に示す。テーブル参照が乗算に対して十分高速であることもあり、Ｘｅｏｎでは従来の１．５９倍、ＳＨ（登録商標）−４では従来の１．８５倍の性能を得ることができた。

伊東・辻井のアルゴリズムにＰＭＳ・ＰＭＭを組み合わせた手法に対しても、提案法は高速であったが、持つべきテーブル数と速度との兼ね合いを考慮すると、伊東・辻井のアルゴリズムにＰＭＳ・ＰＭＭを組み合わせた手法は、提案法よりコストパフォーマンスに優れていると考える。

４．２．提案法におけるテーブル数の削減
提案法では、Ｐ^２５４、Ｐ^２５０、Ｐ^２４２、Ｐ^２２６、Ｐ^１９４、Ｐ^１３０、Ｐ^２を計算する必要がある。これらをテーブル参照で実装した場合、持つべきテーブルサイズが約１．８ｋＢ程度となってしまう。そこで、持つべきテーブル数を削減する手法について検討する。テーブルを削減した場合、テーブル参照の一部を乗算で実行する必要がある。任意の指数計算はＰ^Ｅ（Ｅ＝２^ｎ）の組み合わせで表現できる。そこで、Ｐ^２のテーブルを用いてＰ^４、Ｐ^８、Ｐ^１６、Ｐ^３２、Ｐ^６４、Ｐ^１２８を求め、それらの組み合わせでＰ^１３０〜Ｐ^２５０を求めることでテーブル数を削減することとした。使用するテーブル数とテーブル参照により求める指数演算との関係を図１２の表に示す。そのときの各演算の回数を図１３の表に示す。指数の決定には、乗算回数および、テーブル参照回数が小さくなるように決定した。

図１４、図１５にはＸｅｏｎ、ＳＨ（登録商標）−４で行った場合の処理時間とテーブル数との関係を示す。図１４、図１５中のＢｌｏｍｅｒらの手法および伊東・辻井のアルゴリズムとＰＭＳ、ＰＭＭを組み合わせた手法では、テーブル数は常に１（Ｐ^２のみ）であるが参考のために示す。テーブル数が１の場合、図１４ではＢｌｏｍｅｒらの手法の方が高速であったが、テーブル数が２以上では提案法のほうが高速であった。

また、図１５ではテーブル数が１の場合でも、提案法のほうが高速であるという結果になったが、これはコンパイラの性能によるものと考える。

図１４、図１５において、テーブル数１と２の間が急峻に変化しているのは、Ｍ^２５４の演算を乗算で行う必要があったためである。

５．まとめ
本実施の形態では、加算マスクの入った入力の逆元を展開することで、入力にマスクがかかった状態でも、入力のみの逆元とマスクとの加算を求める手法を提案した。展開した数式を実装するアルゴリズムを提案し、その安全性についての考察を行った。また、提案法を実装した結果、Ｂｌｏｍｅｒらの手法に対して、Ｘｅｏｎでは１．５９倍、ＳＨ（登録商標）−４では１．８５倍の性能を得ることができた。

各実施の形態に係る暗号処理装置の構成を示すブロック図。 各実施の形態に係る暗号処理装置の暗号部の平文入力側構成を示すブロック図。 各実施の形態に係る暗号処理装置の暗号部の暗号文出力側構成を示すブロック図。 実施の形態１及び２に係る暗号処理装置の暗号部が有する非線形演算部の構成を示すブロック図（フロー図）。 実施の形態３及び４に係る暗号処理装置の暗号部が有する非線形演算部の構成を示すブロック図（フロー図）。 実施の形態１から４までに係る暗号処理装置のハードウェア構成の一例を示すブロック図。 実施の形態５に係る暗号処理装置のハードウェア構成の一例を示すブロック図。 実施の形態６に係る暗号処理装置のハードウェア構成の一例を示すブロック図。 従来のマスクのかけかえを行う逆元演算法。 演算回数の比較結果を示す表。 速度比較結果を示す表。 テーブル数とテーブル参照を行う演算の関係を示す表。 テーブル数毎の演算回数の比較結果を示す表。 テーブル数と処理速度の関係（Ｘｅｏｎ）を示すグラフ。 テーブル数と処理速度の関係（ＳＨ（登録商標）−４）を示すグラフ。

符号の説明

１ 暗号処理装置、１００，１１５，１１６，１１７，１１８ 排他的論理和部、１０１ 拡大鍵生成部、１０２ 暗号部、１０３，１０４，１０５，１０６，１０７，１０８，１０９，１１０，１１１ 非線形演算部、１１２，１１３，１１４ 線形演算部、１１９，１２０，１２１，１２２ 補正値演算部、１２３，１２４，１２５，１２６ アフィン変換部、１２７ べき乗演算部、１２８ 乱数生成部、１３０ 演算部、１３１ 記憶部、１３２ 入出力部、１３３ テーブル、１３４ テーブル演算部、１４０ データ入力部、１４１ 乱数入力部、２００ 平文、２０１ 乱数、２０２ 暗号鍵、２０３ 暗号文、２０４ 乱数化平文、２０５，２０６，２０７ 拡大鍵、２０８，２０９，２１０，２１１，２１２，２１３，２１４，２１５，２１６ 分割入力、２１７，２１８，２１９，２２０，２２１，２２２，２２３，２２４，２２５ 補正乱数入力、２２６，２２７，２２８，２２９，２３０，２３１，２３２，２３３，２３４ 非線形出力、２３５，２３６，２３７，２３８，２３９，２４０，２４１，２４２，２４３ 補正乱数出力、２４４，２４５，２４６ 線形出力、２４７ 排他的論理和出力、２４８ 最終補正乱数。

Claims (14)

1. 乱数を生成する乱数生成処理と非線形演算を行い平文に対して生成した乱数を付加する非線形演算処理とを繰り返すことにより平文を暗号化する暗号処理装置に複数備えられ、前記乱数生成処理と前記非線形演算処理とを実行する非線形演算装置において、
   前記平文の少なくとも一部を含む入力データｘに補正乱数Ｍが付加された乱数付加データＰ（Ｐ＝ｘ＋Ｍ）を入力するデータ入力部と、
   前記補正乱数Ｍを入力する乱数入力部と、
   任意の乱数Ｍ´を生成する乱数生成部と、
   前記入力データｘのべき乗ｘ^ｅを第１の項とし、
   （１）前記乱数入力部が入力した補正乱数Ｍと、（２）前記データ入力部が入力した乱数付加データＰと、（３）前記入力データｘと前記補正乱数Ｍとが乗算された乗算データＭｘとの少なくともいずれかで表現される式を乗算回数が減るように変形した式を第２の項とし、
   前記データ入力部が入力した乱数付加データＰのガロア拡大体上のべき乗Ｐ^ｅを、前記第１の項と前記第２の項とを加算する第１の多項式に展開し、
   展開した第１の多項式と前記乱数付加データＰのべき乗Ｐ^ｅとを等式の左右の辺としたときの両辺に前記乱数生成部が生成した任意の乱数Ｍ´を加算し、
   前記等式を前記入力データｘのべき乗ｘ^ｅと前記乱数生成部が生成した任意の乱数Ｍ´とを加算した出力データＦ_ｅを一方の辺とする式に変形したときの他方の辺となる第２の多項式に基づいて、
   前記出力データＦ_ｅを演算して出力するべき乗演算部とを備えることを特徴とする非線形演算装置。
2. 前記乱数生成部は、さらに、
   前記乱数入力部が入力した補正乱数Ｍと相関のない非相関乱数Ｎを生成し、
   前記べき乗演算部は、
   前記乱数生成部が生成した非相関乱数Ｎを用いて、前記乗算データＭｘを複数の項を加算する第３の多項式に変形し、変形した第３の多項式に基づいて前記乗算データＭｘを演算することを特徴とする請求項１に記載の非線形演算装置。
3. 前記第２の多項式の一部は、Ｐ^ａ＋（Ｍｘ）^ｂＧ（ここで、ａ、ｂは整数、Ｇは多項式とする）で表現され、
   前記べき乗演算部は、
   前記第２の多項式のＰ^ａ＋（Ｍｘ）^ｂＧで表現される部分のうち、（Ｍｘ）^ｂＧを前記第３の多項式に含まれる複数の項を用いて分解した式に含まれる項のいずれかと、Ｐ^ａとを先に加算することを特徴とする請求項２に記載の非線形演算装置。
4. 前記べき乗演算部は、
   前記第３の多項式として以下の式（１）を用いることを特徴とする請求項２又は３に記載の非線形演算装置。
   

   
5. 前記べき乗演算部は、
   前記第２の多項式として以下の式（２）を用いることを特徴とする請求項１から４までのいずれかに記載の非線形演算装置。
   

   
6. 前記べき乗演算部は、
   前記第２の多項式として以下の式（３）を用いることを特徴とする請求項１から４までのいずれかに記載の非線形演算装置。
   

   
7. 前記データ入力部は、
   前記乱数付加データＰをアフィン変換してアフィン変換データＡ_Ｐとして入力し、
   前記乱数入力部は、
   前記補正乱数Ｍをアフィン変換してアフィン変換補正乱数Ｂ_Ｍとして入力し、
   前記乱数生成部は、
   前記任意の乱数Ｍ´をアフィン変換して補正乱数出力Ｄ_Ｍ´として出力し、
   前記べき乗演算部は、
   前記出力データＦ_ｅをアフィン変換して非線形出力Ｙとして出力することを特徴とする請求項２又は３に記載の非線形演算装置。
8. 前記べき乗演算部は、
   前記第３の多項式として以下の式（４）を用いることを特徴とする請求項７に記載の非線形演算装置。
   

   
9. 前記べき乗演算部は、
   前記第２の多項式として以下の式（５）を用いることを特徴とする請求項７又は８に記載の非線形演算装置。
   

   
10. 前記べき乗演算部は、
    前記第２の多項式として以下の式（６）を用いることを特徴とする請求項７又は８に記載の非線形演算装置。
    

    
11. 乱数を生成する乱数生成処理と非線形演算を行い平文に対して生成した乱数を付加する非線形演算処理とを繰り返すことにより平文を暗号化する暗号処理装置において、
    前記乱数生成処理と前記非線形演算処理とを実行する非線形演算部を複数備え、
    各非線形演算部は、
    前記平文の少なくとも一部を含む入力データｘに補正乱数Ｍが付加された乱数付加データＰ（Ｐ＝ｘ＋Ｍ）を入力するデータ入力部と、
    前記補正乱数Ｍを入力する乱数入力部と、
    任意の乱数Ｍ´を生成する乱数生成部と、
    前記入力データｘのべき乗ｘ^ｅを第１の項とし、
    （１）前記乱数入力部が入力した補正乱数Ｍと、（２）前記データ入力部が入力した乱数付加データＰと、（３）前記入力データｘと前記補正乱数Ｍとが乗算された乗算データＭｘとの少なくともいずれかで表現される式を乗算回数が減るように変形した式を第２の項とし、
    前記データ入力部が入力した乱数付加データＰのガロア拡大体上のべき乗Ｐ^ｅを、前記第１の項と前記第２の項とを加算する第１の多項式に展開し、
    展開した第１の多項式と前記乱数付加データＰのべき乗Ｐ^ｅとを等式の左右の辺としたときの両辺に前記乱数生成部が生成した任意の乱数Ｍ´を加算し、
    前記等式を前記入力データｘのべき乗ｘ^ｅと前記乱数生成部が生成した任意の乱数Ｍ´とを加算した出力データＦ_ｅを一方の辺とする式に変形したときの他方の辺となる第２の多項式に基づいて、
    前記出力データＦ_ｅを演算して出力するべき乗演算部とを備えることを特徴とする暗号処理装置。
12. 前記暗号処理装置は、さらに、
    少なくとも１つの指数についてデータのべき乗の計算結果を予め記憶する記憶部を備え、
    各非線形演算部のべき乗演算部は、
    べき乗の計算を行う処理の少なくとも一部に前記記憶部に記憶された計算結果を用いることを特徴とする請求項１１に記載の暗号処理装置。
13. 乱数を生成する乱数生成処理と非線形演算を行い平文に対して生成した乱数を付加する非線形演算処理とを繰り返すことにより平文を暗号化する暗号処理装置に複数備えられ、前記乱数生成処理と前記非線形演算処理とを実行する非線形演算装置を用いる非線形演算方法において、
    前記平文の少なくとも一部を含む入力データｘに補正乱数Ｍが付加された乱数付加データＰ（Ｐ＝ｘ＋Ｍ）を入力するデータ入力ステップと、
    前記補正乱数Ｍを入力する乱数入力ステップと、
    任意の乱数Ｍ´を生成する乱数生成ステップと、
    前記入力データｘのべき乗ｘ^ｅを第１の項とし、
    （１）前記乱数入力ステップで入力した補正乱数Ｍと、（２）前記データ入力ステップで入力した乱数付加データＰと、（３）前記入力データｘと前記補正乱数Ｍとが乗算された乗算データＭｘとの少なくともいずれかで表現される式を乗算回数が減るように変形した式を第２の項とし、
    前記データ入力ステップで入力した乱数付加データＰのガロア拡大体上のべき乗Ｐ^ｅを、前記第１の項と前記第２の項とを加算する第１の多項式に展開し、
    展開した第１の多項式と前記乱数付加データＰのべき乗Ｐ^ｅとを等式の左右の辺としたときの両辺に前記乱数生成ステップで生成した任意の乱数Ｍ´を加算し、
    前記等式を前記入力データｘのべき乗ｘ^ｅと前記乱数生成ステップで生成した任意の乱数Ｍ´とを加算した出力データＦ_ｅを一方の辺とする式に変形したときの他方の辺となる第２の多項式に基づいて、
    前記出力データＦ_ｅを演算して出力するべき乗演算ステップとを備えることを特徴とする非線形演算方法。
14. 乱数を生成する乱数生成処理と非線形演算を行い平文に対して生成した乱数を付加する非線形演算処理とを繰り返すことにより平文を暗号化する暗号処理装置が実行する非線形演算プログラムにおいて、
    前記平文の少なくとも一部を含む入力データｘに補正乱数Ｍが付加された乱数付加データＰ（Ｐ＝ｘ＋Ｍ）を入力するデータ入力処理と、
    前記補正乱数Ｍを入力する乱数入力処理と、
    任意の乱数Ｍ´を生成する乱数生成処理と、
    前記入力データｘのべき乗ｘ^ｅを第１の項とし、
    （１）前記乱数入力部が入力した補正乱数Ｍと、（２）前記データ入力部が入力した乱数付加データＰと、（３）前記入力データｘと前記補正乱数Ｍとが乗算された乗算データＭｘとの少なくともいずれかで表現される式を乗算回数が減るように変形した式を第２の項とし、
    前記データ入力部が入力した乱数付加データＰのガロア拡大体上のべき乗Ｐ^ｅを、前記第１の項と前記第２の項とを加算する第１の多項式に展開し、
    展開した第１の多項式と前記乱数付加データＰのべき乗Ｐ^ｅとを等式の左右の辺としたときの両辺に前記乱数生成処理が生成した任意の乱数Ｍ´を加算し、
    前記等式を前記入力データｘのべき乗ｘ^ｅと前記乱数生成処理が生成した任意の乱数Ｍ´とを加算した出力データＦ_ｅを一方の辺とする式に変形したときの他方の辺となる第２の多項式に基づいて、
    前記出力データＦ_ｅを演算して出力するべき乗演算処理とをコンピュータに実行させることを特徴とする非線形演算プログラム。

Images