情報処理装置およびその方法
【課題】 乗算剰余テーブルのエントリ数を低減して、べき乗剰余を演算する。
【解決手段】 初期分割部12は、べき指数eを1ビットからビット長wの範囲で分割して複数のワードeiにする。選択部13は、ワードeiから所定のワードexを選択する。数列生成部14は、ワードexを含み、項の総数が2w-1以下の条件を満たす数列Fkを生成する。再分割部15は、ワードeiのうち、数列Fkに含まれないワードを前回の分割における範囲よりも1ビット少ない範囲で再分割する。乗算剰余テーブル算出部16は、数列Fkの各項をべき指数に含む乗算剰余テーブルMFkを算出する。べき乗剰余演算部17は、ワードei、ワードej、および、乗算剰余テーブルMFkを用いて、べき指数eに対するべき乗剰余Cを演算する。
【解決手段】 初期分割部12は、べき指数eを1ビットからビット長wの範囲で分割して複数のワードeiにする。選択部13は、ワードeiから所定のワードexを選択する。数列生成部14は、ワードexを含み、項の総数が2w-1以下の条件を満たす数列Fkを生成する。再分割部15は、ワードeiのうち、数列Fkに含まれないワードを前回の分割における範囲よりも1ビット少ない範囲で再分割する。乗算剰余テーブル算出部16は、数列Fkの各項をべき指数に含む乗算剰余テーブルMFkを算出する。べき乗剰余演算部17は、ワードei、ワードej、および、乗算剰余テーブルMFkを用いて、べき指数eに対するべき乗剰余Cを演算する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、べき乗剰余を演算する情報処理に関する。
【背景技術】
【０００２】
べき乗剰余(C = Me mod N)は、一方向性関数的な性質を有し、公開鍵暗号方式に利用される。公開鍵暗号方式は、暗号化と復号にそれぞれ異なる鍵を使用し、データの暗号化、ディジタル署名、鍵配送などに利用される。代表的な公開鍵暗号には、素因数分解の困難性に基づくRSA暗号/署名、離散対数計算の困難性に基づくDSA署名、ディフィ・ヘルマン(Diffie-Hellman)鍵配送などがある。
【０００３】
べき乗剰余Cの最も簡単な演算方法は、Meの結果をNで割って余りCを求める。しかし、この計算方法は、公開鍵暗号のように、べき指数eに大きな値（例えば1024ビットの値）を与えると、Meが大きくなって実用的ではない。従って、Meを小さな値に分解し、乗算剰余演算を繰り返し実行して余りCを求める方法が一般的である。
【０００４】
ここで、乗算剰余演算を説明するが、Me mod Nを簡略化してMeと表記する。例えばC=M15を計算する場合、M→M2→…→M14→M15のように、Mを14回乗算剰余することでC=M15が得られる。
【０００５】
また、M→M2→M4→M5→M6→M7→M14→M15のように、計算途中において、乗算（二乗）剰余（M7×M7=M14）を計算し、さらにMの乗算剰余（M14×M＝M15）を行って、C=M15を得ることができる。後者の計算方法は7回の乗算剰余で済むため、前者の計算方法よりも高速である。
【０００６】
ここで、M→M2→…→M14→M15や、M→M2→M4→M5→M6→M7→M14→M15のような計算過程のべき指数に現れる数列(1→2→…→14→15)や(1→2→4→5→6→7→14→15)は加算鎖と呼ばれる。
【０００７】
加算鎖は、べき指数値がeの場合、a1=1から始まりan=eで終わる数列で、数列を構成する各項の数値aiは、下式に示すように、それ以前の項の二つの和になる性質をもつ。
ai = aj + ak …(1)
ここで、j ＜ i、 k ＜ i。
【０００８】
上述したe=15の例が示すように、a1=1から始まりan=eで終わる加算鎖は複数存在する。べき乗剰余演算は、加算鎖が最も短くなるように計算を行えば乗算剰余演算回数が最小になり、最高速になる。しかし、最短の加算鎖を見付ける方法はNP完全問題として知られ、加算鎖をできるだけ短くするアルゴリズムが望まれる。
【０００９】
非特許文献1が開示するThe Sliding Windows（登録商標）Method（以後、Sウィンドウ法）は、加算鎖を短くする一手法である。まず、べき乗剰余演算に使用する乗算剰余MFk（Fk = 2, 3, …, 2w-1, wはウィンドウ長）を計算し、各MFkをメモリに記録する。MFkの総数は2w-1個である。なお、べき乗剰余Cの演算過程においてM1も用いるが、M1=M mod Nであるため、M1の計算とメモリは必要としない。
【００１０】
次に、与えられたべき指数e（ビット長I）をΣi=0I-1ei×2i（ei=0 or 1）のように二進表現にする。入力をM、e、N、w、MFkとし、出力C=Me mod Nになるアルゴリズムは次のとおりである。
C = 1；
for (i = I - 1, 0, i--) {
if (ei == 0)
C = C×C (mod N)； # 処理2-1
if (ei == 1) {
C = Cpow2(L(p))×MFp (mod N)； # 処理2-2
i = i - L(p)；
}
}
return C； …(2)
ここで、Fpのpは、eiから始まりej=1となる、最長のビット列の値(p = ei ei-1 … ej)を指す（ただしi-j+1≦w）、
L(p)はpのビット長、
pow2(x)は2のx乗。
【００１１】
図1によりSウィンドウ法を使ってべき乗剰余を演算する過程を説明する。図1の例は、e=55の場合にウィンドウ長w=3ビットのSウィンドウを使って、べき乗剰余C=M55 mod Nを演算する過程を示す。
【００１２】
図1(a)に示すように、事前演算処理によってMFk(Fk=2、3、5、7)を計算したテーブルを用意し、図1(b)に示す実演算処理によってべき乗剰余Cを計算する。この場合、加算鎖は(1→2→3→5→6→7→12→24→48→55)になる。なお、加算鎖内の2、3、5、7に対するMFkは図1(a)のテーブルを得るために必要である。
【００１３】
Sウィンドウ法によれば、上記のアルゴリズムにおける処理2-2の乗算剰余演算回数が最大1/wに低減されるため、べき乗剰余Cを演算するための時間が小さくなる。一方、べき指数eの値によって、実演算処理では使用しない乗算剰余MFkがX個発生する。つまり、総数2w-1個の乗算剰余MFkうちX個について、その値を計算するための時間や、それを格納するメモリが無駄になる。上記の例では、図1(a)に示すテーブルのM2とM5は実演算処理に使用されないため、総数23-1=4個のうち、2個が無駄と言える。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】Cetin Kaya Koc「High Speed RSA Implementation」RSA Laboratories, RSA Data Security, Inc.、Ver. 2.0、1994年11月
【発明の概要】
【発明が解決しようとする課題】
【００１５】
本発明は、乗算剰余テーブルのエントリ数を低減して、べき乗剰余を演算することを目的とする。
【課題を解決するための手段】
【００１６】
本発明は、前記の目的を達成する一手段として、以下の構成を備える。
【００１７】
本発明にかかる情報処理は、べき指数を1ビットからビット長wの範囲で分割して複数のワードにし、前記複数のワードから所定のワードを選択し、前記選択されたワードを含み、項の総数が2w-1以下の条件を満たす数列を生成し、前記複数のワードのうち、前記数列に含まれないワードを前回の分割における範囲よりも1ビット少ない範囲で再分割し、前記数列の各項をべき指数に含む乗算剰余テーブルを算出し、前記分割されたワード、前記再分割されたワード、および、前記乗算剰余テーブルを用いて、前記べき指数に対するべき乗剰余演算を行うことを特徴とする。
【発明の効果】
【００１８】
本発明によれば、乗算剰余テーブルのエントリ数を低減して、べき乗剰余を演算することができる。
【図面の簡単な説明】
【００１９】
【図１】Sウィンドウ法を使ってべき乗剰余を演算する過程を説明する図。
【図２】実施例の情報処理装置の構成例を説明するブロック図。
【図３】ビットの分割例を説明する図。
【図４】べき乗剰余の演算処理を説明するフローチャート。
【図５】べき乗剰余を演算する過程を説明する図。
【図６】実施例2の情報処理装置の構成例を説明するブロック図。
【図７】実施例2のべき乗剰余の演算処理を説明するフローチャート。
【図８】実施例3の情報処理装置の構成例を説明するブロック図。
【図９】実施例3のべき乗剰余の演算処理を説明するフローチャート。
【発明を実施するための形態】
【００２０】
以下、本発明にかかる実施例の情報処理を図面を参照して詳細に説明する。
【実施例１】
【００２１】
［装置の構成］
図2のブロック図により実施例の情報処理装置の構成例を説明する。
【００２２】
入力部11は、ハードディスク、メモリカード、光ディスクなどの記憶メディアに格納された数値eを入力する。数値eは、例えば公開鍵暗号における公開鍵や秘密鍵に相当する。また、数値eは、情報処理装置のユーザインタフェイスを介して、ユーザが指定または入力することもできる。
【００２３】
初期分割部12は、入力された数値eを1ビットから最大分割ビット長wの範囲で分割する。この分割処理には、例えば非特許文献1の17頁から18頁に記載された方法を適用する。当該文献は、決定されたビット長固定で分割するconstant length nonzero windows (CLNW)、可変長かつ指定されたビット長を最大の分割長とするvariable length nonzero windows (VLNW)を記載する。例えばCLNWでは、状態ZWとNWを遷移しながらビット分割を行う。CLNWは最下位ビットから順に最上位ビットまでビット探索を行う。CLNWのアルゴリズムは以下のとおりである。
状態ZW：次のビットが‘0’ならば状態ZWに、‘0’でなければ状態NWに遷移する。
状態NW：予め指定されたビット長まで状態NWを維持し、次のビットが‘0’ならば状態ZWに、‘0’でなければ状態NWに遷移する。
【００２４】
図3によりビットの分割例を説明する。図3(b)は、e=12405733 (1011 1101 0100 1011 1110 0101)をCLNW（最大分割ビット長w=4）で分割した例を示す。図3(b)においてアポストロフィ「'」で囲んだ二進数値eiを以後ワードとして説明する。分割結果eiは、選択部13および再分割部15に供給される。
【００２５】
選択部13は、詳細は後述するが、初期分割部12によって分割された各ワードeiから所定のワードexを選択し、選択結果を数列生成部14に供給する。
【００２６】
数列生成部14は、詳細は後述するが、選択部13の選択結果に基づき、exを含む数列Fk（ex⊂Fk：k=1, 2, …, m）を生成し、数列Fkを再分割部15および乗算剰余テーブル算出部16に供給する。
【００２７】
再分割部15は、詳細は後述するが、分割結果eiのうち数列Fkに含まれないワードを、前回の分割における範囲よりも1ビット少ない範囲（例えば、1ビットからw-1ビット）で複数の数値ej（ej⊂Fk：j=1, 2, …）に再分割する。そして、分割結果eiおよび再分割結果ejをべき乗剰余演算部17に供給する。
【００２８】
乗算剰余テーブル算出部16は、詳細は後述するが、数列Fkに基づき、数列Fkの値が1の項(F1=1)を除くF2からFmまでの各項をべき指数に含む乗算剰余テーブルMFkを算出する。そして、乗算剰余テーブルMFkをべき乗剰余演算部17に供給する。
【００２９】
べき乗剰余演算部17は、分割結果ei、再分割結果ejおよび乗算剰余テーブルMFkを用いて、べき乗剰余C=Me mod Nを演算する。
【００３０】
出力部18は、べき乗剰余演算部17が演算したべき乗剰余Cを公開鍵暗号の暗号化部、復号部（例えばCODEC）などに供給する。
【００３１】
なお、図2に示す情報処理装置は、専用のハードウェアとして実現してもよい。あるいは、例えばコンピュータ機器にCODECのプログラムの一部として、べき乗剰余の演算プログラムを供給し、コンピュータ機器のCPUがRAMをワークメモリとして当該演算プログラムを実行することで、実施例の情報処理装置の機能が実現される。
【００３２】
［演算処理］
図4のフローチャートによりべき乗剰余の演算処理を説明する。なお、図4に示す処理は、図2に示す情報処理装置が行う処理である。
【００３３】
入力部11は数値eを入力する(S11)。数値eは、例えば1024ビット長の公開鍵である。ここでは、説明を簡単にするために、図3(a)に示すe=12405733 (1011 1101 0100 1011 1110 0101)を入力したとする。
【００３４】
次に、初期分割部12は、数値eを1ビットから最大分割ビット長wの範囲でワードeiに分割する(S12)。なお、最大分割ビット長wは、情報処理装置が実行するプログラムに指定されたものを用いてもよいし、ユーザが指定するものを用いてもよい。例えば図3(b)に示すように、数値eは'1'、'0'、'1111'、'0101'、'0'、'0101'、'1111'、'0'、'0101'に分割される
【００３５】
次に、選択部13は、分割された各ワードeiから所定のワードexを選択する(S13)。ここでは、説明を簡単にするため、出現頻度が最も高いワードを選択することにする。図3(b)に示す分割例の場合は最も出現頻度が高い'0101' (5)が選択される。なお、ワードexの選択方法は、出現頻度が二番目に高いワードを選択する、情報処理装置が実行するプログラムに指定された特定の値を選択するなど、任意の方法を用いることができる。
【００３６】
次に、数列生成部14は、ワードexを含む数列Fkを生成する(S14)。この数列は、加算鎖に相当し、例えば非特許文献1の22頁に記載された、バイナリ法(binary method)、オクタル法(octal method)、ファクタ法(factor method)などの方法によって数列を生成する。ワードex='0101'に対してオクタル法を適用すると、"5"を含む数列Fkとして{1, 2, 3, 4, 5}が算出される。
【００３７】
次に、数列生成部14は、生成した数列Fkの項数mと2w-1を比較して(S15)、m＞2w-1の場合は処理をステップS14に戻し、他の数列生成方法を適用する。上記の例ではFk={1, 2, 3, 4, 5}の項数mは5、図3(b)に示すように最大分割ビット長wは4であり、m＜24-1=15である。m≦2w-1の場合は、数列Fkを再分割部15と乗算剰余テーブル算出部16に供給し、処理をステップS16に進める。
【００３８】
次に、再分割部15は、ワードeiが数列Fkに含まれるか否かを判定し(S16)、ワードeiのすべてが数列Fkに含まれる場合は処理をステップS18へ進める。一方、数列Fkに含まれないワードeiが存在する場合、再分割部15は、数列Fkに含まれないeiを前回の分割における範囲よりも1ビット少ない範囲で複数の数値ejに再分割し(S17)、処理をステップS16に戻す。
【００３９】
図3(b)において、e2='1111' (15)は数列Fk={1, 2, 3, 4, 5}に含まれない。そこで、分割長を1ビットから3ビットとしてCLNWにより'1111'を再分割する。この再分割により、図3(c)に示すように、数値eは'1'、'0'、'1'、'111'、'0101'、'0'、'0101'、'1'、'111'、'0'、'0101'に分割される。
【００４０】
上記再分割によって得られるe2='111' (7)は数列Fk={1, 2, 3, 4, 5}に含まれない。そこで、分割長を1ビットから2ビットとしてCLNWにより'111'を再分割する。この再分割により、図3(d)に示すように、数値eは'1'、'0'、'1'、'1'、'11'、'0101'、'0'、'0101'、'1'、'1'、'11'、'0'、'0101'に分割される。この再分割によれば、ワードei、ejは'1' (1)、'11' (3)、'0101' (5)の何れかになり、つまりei, ej⊂Fkになる。
【００４１】
次に、乗算剰余テーブル算出部16は、数列Fkに基づき、F1＝1を除くF2からFmまでの各項をべき指数に含む乗算剰余テーブルMFkを算出して、MFkをメモリに格納する(S18)。
【００４２】
図5によりべき乗剰余を演算する過程を説明する。図5(a)は、数列Fk={1, 2, 3, 4, 5}から乗算剰余テーブルMFkを算出する過程を示す。式(1)に示した加算鎖の性質により、各MFiは、それ以前に算出した数値MFj×MFkにより演算可能である。なお、数列の種類によらず必ずF1=1、F2=2になるが、M1=M mod Nであり、M1の計算とメモリは不要である。
【００４３】
次に、べき乗剰余演算部17は、分割結果ei、ejおよび乗算剰余テーブルMFkを用いて、べき乗剰余C=Me mod Nを演算する(S19)。図3(d)が分割結果Wn (eii, ej⊂Wn)であるとする。入力をM、Wn、N、MFkとすると、べき乗剰余Cを演算するアルゴリズムは下のようになる。
C = 1；
for (i = n - 1, 0, i--) {
if (Wi == 0)
C = C×C (mod N)； # 処理3-1
if (Wi != 0)
C = Cpow2(L(Wi))×MFWi (mod N)； # 処理3-2
}
return C； …(3)
ここで、L(Wi)はWiのビット長、
pow2(x)は2のx乗。
【００４４】
図5(b)はべき乗剰余C=M12405733 mod Nを演算する過程を示す。べき乗剰余Cの演算が終了すると、出力部18は、べき乗剰余Cを出力する(S20)。
【００４５】
このように、MFkのFkとして奇数すべての候補を取るSウィンドウ法と比べ、MFkを計算するための時間やメモリの無駄を削減することができる。例えば、図5(a)に示す乗算剰余テーブルMFkは四つのエントリ（F1を除く）を有する。ウィンドウ幅w=4のSウィンドウ法によれば、乗算剰余テーブルMFkのエントリ数は24-1=8になる。また、図5において、実演算処理に使用されないエントリはM4だけであり、四つのエントリのうち無駄は一つだけである。
【００４６】
また、削減した処理時間を有効活用するために、初期分割における分割長（1ビットからwビット）の範囲を広くとれば、Me mod Nで必要になる乗算剰余演算回数を少なくすることができる。従って、べき乗剰余演算の全体の処理時間を削減することが可能になる。
【００４７】
上述した演算処理において、ステップS18、S19を除く各ステップは、べき乗剰余演算における指数eのみの処理である。べき指数eは、通常、公開鍵や秘密鍵であり、暗号処理中に鍵生成、鍵交換が必要な場合を除き、事前に取得することができる。言い換えれば、ステップS11からS17までの処理は、予め、べき乗剰余演算の処理時間に影響を与えることなく実行可能である。
【実施例２】
【００４８】
以下、本発明にかかる実施例2の情報処理を説明する。なお、実施例2において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００４９】
［装置の構成］
図6のブロック図により実施例2の情報処理装置の構成例を説明する。
【００５０】
実施例2の情報処理装置は、数列Fkを複数、予め格納する数列格納部21を有する。数列格納部21が格納する数列Fkは、項の総数mが2w-1以下の条件を満たす。
【００５１】
数列生成部14は、数列格納部21に格納された数列Fkから、選択部13が出力するワードexを含む数列Fk（ex⊂Fk）を選択し、選択した数列Fkを再分割部15、乗算剰余テーブル算出部16に供給する。
【００５２】
［演算処理］
図7のフローチャートにより実施例2のべき乗剰余の演算処理を説明する。なお、図7に示す処理は、図6に示す情報処理装置が行う処理である。ステップS11からS13、S16からS19は実施例1と同様の処理であり、それらの詳細説明を省略する。
【００５３】
数列生成部14は、選択部13の選択結果（ワードex）を含む数列を、数列格納部21が格納する数列Fkから選択する(S21)。ここでは、説明を簡単にするために、実施例1と同様に'0101' (5)が選択されたことにする。そして、数列生成部14が'0101'を含む数列としてFk={1, 2, 3, 5}を選択したことにする。なお、数列Fk={1, 2, 3, 5}の項の総数mは4であり、24-1=15以下の条件を満たす。
【００５４】
実施例2において選択される数列Fk={1, 2, 3, 5}は、実施例1において算出される数列Fk={1, 2, 3, 4, 5}よりも項数が少ない。実施例1と同様にC=M12405733 mod Nを演算する場合、実演算処理にかかるコストは実施例1と同様だが、乗算剰余テーブルMFkの算出コストはM4が不要な分、低減される。
【実施例３】
【００５５】
以下、本発明にかかる実施例3の情報処理を説明する。なお、実施例3において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００５６】
実施例3では、実施例1に示したべき乗剰余演算（以下、再分割法）の乗算剰余演算回数と、Sウィンドウ法などの他のべき乗剰余演算方法の乗算剰余演算回数を計算する。そして、それらの計算結果から、再分割法の実行、数列生成部14による数列Fkの再算出を含む再分割法の実行、および、Sウィンドウ法などの他のべき乗剰余演算方法（以下、他の演算法）の実行を選択的に制御する演算処理を説明する。
【００５７】
［装置の構成］
図8のブロック図により実施例3の情報処理装置の構成例を説明する。
【００５８】
演算回数計算部31は、再分割部15の分割結果ei、ejおよび数列生成部14が算出した数列Fkから、再分割法における乗算剰余演算回数S1、並びに、他の演算法を用いる場合の乗算剰余演算回数S2を計算する。
【００５９】
演算方法制御部32は、演算回数計算部31の計算結果に基づき、数列生成部14に新たな数列Fkを算出させて数値eの分割をやり直したり、再分割法および他の演算法を選択的に制御する。
【００６０】
第一の演算部であるべき乗剰余演算部17は、再分割法によりべき乗剰余演算を行う。また、第二の演算部であるべき乗剰余演算部33は、他の演算法によりべき乗剰余演算を行う。
【００６１】
［演算処理］
図9のフローチャートにより実施例3のべき乗剰余の演算処理を説明する。なお、図9に示す処理は、図8に示す情報処理装置が行う処理である。ステップS11からS19は実施例1と同様の処理であり、それらの詳細説明を省略する。
【００６２】
演算回数計算部31は、再分割部15の分割結果ei、ejおよび数列生成部14が算出した数列Fkを入力して、第一のべき乗剰余演算部17の乗算剰余演算回数S1と、第二のべき乗剰余演算部33の乗算剰余演算回数S2を計算する(S31)。
【００６３】
この計算は、実際の演算を行わずに、乗算剰余テーブル算出部16およびべき乗剰余演算部17の処理と同じアルゴリズムにおける乗算剰余演算の総数をカウントすることにより実現することができる。例えば、M12405733 mod N (Wn：n=0, …, 12)、数列Fk={1, 2, 3, 5}の場合、乗算剰余演算回数は12である。また、例えば、Sウィンドウ法をM12405733 mod Nにウィンドウ長4ビットを適用すると、乗算剰余演算回数は13になる。
【００６４】
演算方法制御部32は、乗算剰余演算回数S1とS2を比較して(S32)、S1＜S2であれば処理をステップS18に進める。つまり、乗算剰余テーブル算出部16の処理(S18)および第一のべき乗剰余演算部17の処理(S19)が実行される。
【００６５】
また、S1≧S2の場合、演算方法制御部32は、生成可能なすべての数列Fkを生成したか否かを数列生成部14に問い合わせる(S33)。そして、生成可能な数列Fkが残っている場合は、処理をステップS14に戻して、数列生成部14に数列Fkの再生成を行わせる。つまり、ステップS14からS32の処理が繰り返される。
【００６６】
また、生成可能な数列Fkが残っていない場合、演算方法制御部32は、処理をステップS34に進める。つまり、S1≧S2かつ数列生成部14が再生成可能な数列がない場合は第二のべき乗剰余演算部33の処理(S34)が実行される。
【００６７】
このように、再分割法によるべき乗剰余演算の演算コストが他の演算法よりも高い場合は、新たな数列により処理をやり直す、または、他の演算法を適用して、べき乗剰余演算の演算コストを極力抑えることができる。
【００６８】
なお、図8には、実施例1の情報処理装置の構成に演算回数計算部31、演算方法制御部32、第二のべき乗剰余演算部33を加える構成を示した。しかし、実施例2の情報処理装置の構成に演算回数計算部31、演算方法制御部32、第二のべき乗剰余演算部33を加える構成としてもよい。そのような構成によれば、演算方法制御部32は、S1≧S2の場合、選択可能なすべての数列Fkを選択したか否かを数列生成部14に問い合わせる(S33)。そして、選択可能な数列Fkが残っている場合は、処理をステップS21に戻して、数列生成部14に数列Fkの再選択を行わせる。
【００６９】
［変形例］
●数列Fkの選択方法
実施例2、3では、ワードexを含む数列Fk（ex⊂Fk）の選択を説明したが、ワードexは複数あってもよい。つまり、図3(b)に示す例の場合、'0101' (5)だけでなく、'1111' (15)を含む数列Fk（例えば{1, 2, 3, 5, 10, 15}）を選択すれば、より効率的に数列Fkの選択処理を行うことが可能になる。
【００７０】
●べき指数eの分割処理方法
上述した実施例では、べき指数eをCLNWで分割または再分割する例を説明した。分割または再分割に用いる分割アルゴリズムは、毎回、異なってもよい。図3に示す例の場合、'1111' (15)はCLNWによって最終的に図3(d)に示すように'1'、'1'、'11'に分割される。しかし、数列Fk={1, 2, 3, 5}を適用する場合、'11'、'11'に分割すれば乗算剰余演算回数を一回削減することができる。つまり、数列Fkに適応して分割アルゴリズムを変更すれば、乗算剰余演算回数の削減が可能になる。
【００７１】
［その他の実施例］
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステムあるいは装置のコンピュータ（又はCPUやMPU等）がプログラムを読み出して実行する処理である。
【技術分野】
【０００１】
本発明は、べき乗剰余を演算する情報処理に関する。
【背景技術】
【０００２】
べき乗剰余(C = Me mod N)は、一方向性関数的な性質を有し、公開鍵暗号方式に利用される。公開鍵暗号方式は、暗号化と復号にそれぞれ異なる鍵を使用し、データの暗号化、ディジタル署名、鍵配送などに利用される。代表的な公開鍵暗号には、素因数分解の困難性に基づくRSA暗号/署名、離散対数計算の困難性に基づくDSA署名、ディフィ・ヘルマン(Diffie-Hellman)鍵配送などがある。
【０００３】
べき乗剰余Cの最も簡単な演算方法は、Meの結果をNで割って余りCを求める。しかし、この計算方法は、公開鍵暗号のように、べき指数eに大きな値（例えば1024ビットの値）を与えると、Meが大きくなって実用的ではない。従って、Meを小さな値に分解し、乗算剰余演算を繰り返し実行して余りCを求める方法が一般的である。
【０００４】
ここで、乗算剰余演算を説明するが、Me mod Nを簡略化してMeと表記する。例えばC=M15を計算する場合、M→M2→…→M14→M15のように、Mを14回乗算剰余することでC=M15が得られる。
【０００５】
また、M→M2→M4→M5→M6→M7→M14→M15のように、計算途中において、乗算（二乗）剰余（M7×M7=M14）を計算し、さらにMの乗算剰余（M14×M＝M15）を行って、C=M15を得ることができる。後者の計算方法は7回の乗算剰余で済むため、前者の計算方法よりも高速である。
【０００６】
ここで、M→M2→…→M14→M15や、M→M2→M4→M5→M6→M7→M14→M15のような計算過程のべき指数に現れる数列(1→2→…→14→15)や(1→2→4→5→6→7→14→15)は加算鎖と呼ばれる。
【０００７】
加算鎖は、べき指数値がeの場合、a1=1から始まりan=eで終わる数列で、数列を構成する各項の数値aiは、下式に示すように、それ以前の項の二つの和になる性質をもつ。
ai = aj + ak …(1)
ここで、j ＜ i、 k ＜ i。
【０００８】
上述したe=15の例が示すように、a1=1から始まりan=eで終わる加算鎖は複数存在する。べき乗剰余演算は、加算鎖が最も短くなるように計算を行えば乗算剰余演算回数が最小になり、最高速になる。しかし、最短の加算鎖を見付ける方法はNP完全問題として知られ、加算鎖をできるだけ短くするアルゴリズムが望まれる。
【０００９】
非特許文献1が開示するThe Sliding Windows（登録商標）Method（以後、Sウィンドウ法）は、加算鎖を短くする一手法である。まず、べき乗剰余演算に使用する乗算剰余MFk（Fk = 2, 3, …, 2w-1, wはウィンドウ長）を計算し、各MFkをメモリに記録する。MFkの総数は2w-1個である。なお、べき乗剰余Cの演算過程においてM1も用いるが、M1=M mod Nであるため、M1の計算とメモリは必要としない。
【００１０】
次に、与えられたべき指数e（ビット長I）をΣi=0I-1ei×2i（ei=0 or 1）のように二進表現にする。入力をM、e、N、w、MFkとし、出力C=Me mod Nになるアルゴリズムは次のとおりである。
C = 1；
for (i = I - 1, 0, i--) {
if (ei == 0)
C = C×C (mod N)； # 処理2-1
if (ei == 1) {
C = Cpow2(L(p))×MFp (mod N)； # 処理2-2
i = i - L(p)；
}
}
return C； …(2)
ここで、Fpのpは、eiから始まりej=1となる、最長のビット列の値(p = ei ei-1 … ej)を指す（ただしi-j+1≦w）、
L(p)はpのビット長、
pow2(x)は2のx乗。
【００１１】
図1によりSウィンドウ法を使ってべき乗剰余を演算する過程を説明する。図1の例は、e=55の場合にウィンドウ長w=3ビットのSウィンドウを使って、べき乗剰余C=M55 mod Nを演算する過程を示す。
【００１２】
図1(a)に示すように、事前演算処理によってMFk(Fk=2、3、5、7)を計算したテーブルを用意し、図1(b)に示す実演算処理によってべき乗剰余Cを計算する。この場合、加算鎖は(1→2→3→5→6→7→12→24→48→55)になる。なお、加算鎖内の2、3、5、7に対するMFkは図1(a)のテーブルを得るために必要である。
【００１３】
Sウィンドウ法によれば、上記のアルゴリズムにおける処理2-2の乗算剰余演算回数が最大1/wに低減されるため、べき乗剰余Cを演算するための時間が小さくなる。一方、べき指数eの値によって、実演算処理では使用しない乗算剰余MFkがX個発生する。つまり、総数2w-1個の乗算剰余MFkうちX個について、その値を計算するための時間や、それを格納するメモリが無駄になる。上記の例では、図1(a)に示すテーブルのM2とM5は実演算処理に使用されないため、総数23-1=4個のうち、2個が無駄と言える。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】Cetin Kaya Koc「High Speed RSA Implementation」RSA Laboratories, RSA Data Security, Inc.、Ver. 2.0、1994年11月
【発明の概要】
【発明が解決しようとする課題】
【００１５】
本発明は、乗算剰余テーブルのエントリ数を低減して、べき乗剰余を演算することを目的とする。
【課題を解決するための手段】
【００１６】
本発明は、前記の目的を達成する一手段として、以下の構成を備える。
【００１７】
本発明にかかる情報処理は、べき指数を1ビットからビット長wの範囲で分割して複数のワードにし、前記複数のワードから所定のワードを選択し、前記選択されたワードを含み、項の総数が2w-1以下の条件を満たす数列を生成し、前記複数のワードのうち、前記数列に含まれないワードを前回の分割における範囲よりも1ビット少ない範囲で再分割し、前記数列の各項をべき指数に含む乗算剰余テーブルを算出し、前記分割されたワード、前記再分割されたワード、および、前記乗算剰余テーブルを用いて、前記べき指数に対するべき乗剰余演算を行うことを特徴とする。
【発明の効果】
【００１８】
本発明によれば、乗算剰余テーブルのエントリ数を低減して、べき乗剰余を演算することができる。
【図面の簡単な説明】
【００１９】
【図１】Sウィンドウ法を使ってべき乗剰余を演算する過程を説明する図。
【図２】実施例の情報処理装置の構成例を説明するブロック図。
【図３】ビットの分割例を説明する図。
【図４】べき乗剰余の演算処理を説明するフローチャート。
【図５】べき乗剰余を演算する過程を説明する図。
【図６】実施例2の情報処理装置の構成例を説明するブロック図。
【図７】実施例2のべき乗剰余の演算処理を説明するフローチャート。
【図８】実施例3の情報処理装置の構成例を説明するブロック図。
【図９】実施例3のべき乗剰余の演算処理を説明するフローチャート。
【発明を実施するための形態】
【００２０】
以下、本発明にかかる実施例の情報処理を図面を参照して詳細に説明する。
【実施例１】
【００２１】
［装置の構成］
図2のブロック図により実施例の情報処理装置の構成例を説明する。
【００２２】
入力部11は、ハードディスク、メモリカード、光ディスクなどの記憶メディアに格納された数値eを入力する。数値eは、例えば公開鍵暗号における公開鍵や秘密鍵に相当する。また、数値eは、情報処理装置のユーザインタフェイスを介して、ユーザが指定または入力することもできる。
【００２３】
初期分割部12は、入力された数値eを1ビットから最大分割ビット長wの範囲で分割する。この分割処理には、例えば非特許文献1の17頁から18頁に記載された方法を適用する。当該文献は、決定されたビット長固定で分割するconstant length nonzero windows (CLNW)、可変長かつ指定されたビット長を最大の分割長とするvariable length nonzero windows (VLNW)を記載する。例えばCLNWでは、状態ZWとNWを遷移しながらビット分割を行う。CLNWは最下位ビットから順に最上位ビットまでビット探索を行う。CLNWのアルゴリズムは以下のとおりである。
状態ZW：次のビットが‘0’ならば状態ZWに、‘0’でなければ状態NWに遷移する。
状態NW：予め指定されたビット長まで状態NWを維持し、次のビットが‘0’ならば状態ZWに、‘0’でなければ状態NWに遷移する。
【００２４】
図3によりビットの分割例を説明する。図3(b)は、e=12405733 (1011 1101 0100 1011 1110 0101)をCLNW（最大分割ビット長w=4）で分割した例を示す。図3(b)においてアポストロフィ「'」で囲んだ二進数値eiを以後ワードとして説明する。分割結果eiは、選択部13および再分割部15に供給される。
【００２５】
選択部13は、詳細は後述するが、初期分割部12によって分割された各ワードeiから所定のワードexを選択し、選択結果を数列生成部14に供給する。
【００２６】
数列生成部14は、詳細は後述するが、選択部13の選択結果に基づき、exを含む数列Fk（ex⊂Fk：k=1, 2, …, m）を生成し、数列Fkを再分割部15および乗算剰余テーブル算出部16に供給する。
【００２７】
再分割部15は、詳細は後述するが、分割結果eiのうち数列Fkに含まれないワードを、前回の分割における範囲よりも1ビット少ない範囲（例えば、1ビットからw-1ビット）で複数の数値ej（ej⊂Fk：j=1, 2, …）に再分割する。そして、分割結果eiおよび再分割結果ejをべき乗剰余演算部17に供給する。
【００２８】
乗算剰余テーブル算出部16は、詳細は後述するが、数列Fkに基づき、数列Fkの値が1の項(F1=1)を除くF2からFmまでの各項をべき指数に含む乗算剰余テーブルMFkを算出する。そして、乗算剰余テーブルMFkをべき乗剰余演算部17に供給する。
【００２９】
べき乗剰余演算部17は、分割結果ei、再分割結果ejおよび乗算剰余テーブルMFkを用いて、べき乗剰余C=Me mod Nを演算する。
【００３０】
出力部18は、べき乗剰余演算部17が演算したべき乗剰余Cを公開鍵暗号の暗号化部、復号部（例えばCODEC）などに供給する。
【００３１】
なお、図2に示す情報処理装置は、専用のハードウェアとして実現してもよい。あるいは、例えばコンピュータ機器にCODECのプログラムの一部として、べき乗剰余の演算プログラムを供給し、コンピュータ機器のCPUがRAMをワークメモリとして当該演算プログラムを実行することで、実施例の情報処理装置の機能が実現される。
【００３２】
［演算処理］
図4のフローチャートによりべき乗剰余の演算処理を説明する。なお、図4に示す処理は、図2に示す情報処理装置が行う処理である。
【００３３】
入力部11は数値eを入力する(S11)。数値eは、例えば1024ビット長の公開鍵である。ここでは、説明を簡単にするために、図3(a)に示すe=12405733 (1011 1101 0100 1011 1110 0101)を入力したとする。
【００３４】
次に、初期分割部12は、数値eを1ビットから最大分割ビット長wの範囲でワードeiに分割する(S12)。なお、最大分割ビット長wは、情報処理装置が実行するプログラムに指定されたものを用いてもよいし、ユーザが指定するものを用いてもよい。例えば図3(b)に示すように、数値eは'1'、'0'、'1111'、'0101'、'0'、'0101'、'1111'、'0'、'0101'に分割される
【００３５】
次に、選択部13は、分割された各ワードeiから所定のワードexを選択する(S13)。ここでは、説明を簡単にするため、出現頻度が最も高いワードを選択することにする。図3(b)に示す分割例の場合は最も出現頻度が高い'0101' (5)が選択される。なお、ワードexの選択方法は、出現頻度が二番目に高いワードを選択する、情報処理装置が実行するプログラムに指定された特定の値を選択するなど、任意の方法を用いることができる。
【００３６】
次に、数列生成部14は、ワードexを含む数列Fkを生成する(S14)。この数列は、加算鎖に相当し、例えば非特許文献1の22頁に記載された、バイナリ法(binary method)、オクタル法(octal method)、ファクタ法(factor method)などの方法によって数列を生成する。ワードex='0101'に対してオクタル法を適用すると、"5"を含む数列Fkとして{1, 2, 3, 4, 5}が算出される。
【００３７】
次に、数列生成部14は、生成した数列Fkの項数mと2w-1を比較して(S15)、m＞2w-1の場合は処理をステップS14に戻し、他の数列生成方法を適用する。上記の例ではFk={1, 2, 3, 4, 5}の項数mは5、図3(b)に示すように最大分割ビット長wは4であり、m＜24-1=15である。m≦2w-1の場合は、数列Fkを再分割部15と乗算剰余テーブル算出部16に供給し、処理をステップS16に進める。
【００３８】
次に、再分割部15は、ワードeiが数列Fkに含まれるか否かを判定し(S16)、ワードeiのすべてが数列Fkに含まれる場合は処理をステップS18へ進める。一方、数列Fkに含まれないワードeiが存在する場合、再分割部15は、数列Fkに含まれないeiを前回の分割における範囲よりも1ビット少ない範囲で複数の数値ejに再分割し(S17)、処理をステップS16に戻す。
【００３９】
図3(b)において、e2='1111' (15)は数列Fk={1, 2, 3, 4, 5}に含まれない。そこで、分割長を1ビットから3ビットとしてCLNWにより'1111'を再分割する。この再分割により、図3(c)に示すように、数値eは'1'、'0'、'1'、'111'、'0101'、'0'、'0101'、'1'、'111'、'0'、'0101'に分割される。
【００４０】
上記再分割によって得られるe2='111' (7)は数列Fk={1, 2, 3, 4, 5}に含まれない。そこで、分割長を1ビットから2ビットとしてCLNWにより'111'を再分割する。この再分割により、図3(d)に示すように、数値eは'1'、'0'、'1'、'1'、'11'、'0101'、'0'、'0101'、'1'、'1'、'11'、'0'、'0101'に分割される。この再分割によれば、ワードei、ejは'1' (1)、'11' (3)、'0101' (5)の何れかになり、つまりei, ej⊂Fkになる。
【００４１】
次に、乗算剰余テーブル算出部16は、数列Fkに基づき、F1＝1を除くF2からFmまでの各項をべき指数に含む乗算剰余テーブルMFkを算出して、MFkをメモリに格納する(S18)。
【００４２】
図5によりべき乗剰余を演算する過程を説明する。図5(a)は、数列Fk={1, 2, 3, 4, 5}から乗算剰余テーブルMFkを算出する過程を示す。式(1)に示した加算鎖の性質により、各MFiは、それ以前に算出した数値MFj×MFkにより演算可能である。なお、数列の種類によらず必ずF1=1、F2=2になるが、M1=M mod Nであり、M1の計算とメモリは不要である。
【００４３】
次に、べき乗剰余演算部17は、分割結果ei、ejおよび乗算剰余テーブルMFkを用いて、べき乗剰余C=Me mod Nを演算する(S19)。図3(d)が分割結果Wn (eii, ej⊂Wn)であるとする。入力をM、Wn、N、MFkとすると、べき乗剰余Cを演算するアルゴリズムは下のようになる。
C = 1；
for (i = n - 1, 0, i--) {
if (Wi == 0)
C = C×C (mod N)； # 処理3-1
if (Wi != 0)
C = Cpow2(L(Wi))×MFWi (mod N)； # 処理3-2
}
return C； …(3)
ここで、L(Wi)はWiのビット長、
pow2(x)は2のx乗。
【００４４】
図5(b)はべき乗剰余C=M12405733 mod Nを演算する過程を示す。べき乗剰余Cの演算が終了すると、出力部18は、べき乗剰余Cを出力する(S20)。
【００４５】
このように、MFkのFkとして奇数すべての候補を取るSウィンドウ法と比べ、MFkを計算するための時間やメモリの無駄を削減することができる。例えば、図5(a)に示す乗算剰余テーブルMFkは四つのエントリ（F1を除く）を有する。ウィンドウ幅w=4のSウィンドウ法によれば、乗算剰余テーブルMFkのエントリ数は24-1=8になる。また、図5において、実演算処理に使用されないエントリはM4だけであり、四つのエントリのうち無駄は一つだけである。
【００４６】
また、削減した処理時間を有効活用するために、初期分割における分割長（1ビットからwビット）の範囲を広くとれば、Me mod Nで必要になる乗算剰余演算回数を少なくすることができる。従って、べき乗剰余演算の全体の処理時間を削減することが可能になる。
【００４７】
上述した演算処理において、ステップS18、S19を除く各ステップは、べき乗剰余演算における指数eのみの処理である。べき指数eは、通常、公開鍵や秘密鍵であり、暗号処理中に鍵生成、鍵交換が必要な場合を除き、事前に取得することができる。言い換えれば、ステップS11からS17までの処理は、予め、べき乗剰余演算の処理時間に影響を与えることなく実行可能である。
【実施例２】
【００４８】
以下、本発明にかかる実施例2の情報処理を説明する。なお、実施例2において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００４９】
［装置の構成］
図6のブロック図により実施例2の情報処理装置の構成例を説明する。
【００５０】
実施例2の情報処理装置は、数列Fkを複数、予め格納する数列格納部21を有する。数列格納部21が格納する数列Fkは、項の総数mが2w-1以下の条件を満たす。
【００５１】
数列生成部14は、数列格納部21に格納された数列Fkから、選択部13が出力するワードexを含む数列Fk（ex⊂Fk）を選択し、選択した数列Fkを再分割部15、乗算剰余テーブル算出部16に供給する。
【００５２】
［演算処理］
図7のフローチャートにより実施例2のべき乗剰余の演算処理を説明する。なお、図7に示す処理は、図6に示す情報処理装置が行う処理である。ステップS11からS13、S16からS19は実施例1と同様の処理であり、それらの詳細説明を省略する。
【００５３】
数列生成部14は、選択部13の選択結果（ワードex）を含む数列を、数列格納部21が格納する数列Fkから選択する(S21)。ここでは、説明を簡単にするために、実施例1と同様に'0101' (5)が選択されたことにする。そして、数列生成部14が'0101'を含む数列としてFk={1, 2, 3, 5}を選択したことにする。なお、数列Fk={1, 2, 3, 5}の項の総数mは4であり、24-1=15以下の条件を満たす。
【００５４】
実施例2において選択される数列Fk={1, 2, 3, 5}は、実施例1において算出される数列Fk={1, 2, 3, 4, 5}よりも項数が少ない。実施例1と同様にC=M12405733 mod Nを演算する場合、実演算処理にかかるコストは実施例1と同様だが、乗算剰余テーブルMFkの算出コストはM4が不要な分、低減される。
【実施例３】
【００５５】
以下、本発明にかかる実施例3の情報処理を説明する。なお、実施例3において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００５６】
実施例3では、実施例1に示したべき乗剰余演算（以下、再分割法）の乗算剰余演算回数と、Sウィンドウ法などの他のべき乗剰余演算方法の乗算剰余演算回数を計算する。そして、それらの計算結果から、再分割法の実行、数列生成部14による数列Fkの再算出を含む再分割法の実行、および、Sウィンドウ法などの他のべき乗剰余演算方法（以下、他の演算法）の実行を選択的に制御する演算処理を説明する。
【００５７】
［装置の構成］
図8のブロック図により実施例3の情報処理装置の構成例を説明する。
【００５８】
演算回数計算部31は、再分割部15の分割結果ei、ejおよび数列生成部14が算出した数列Fkから、再分割法における乗算剰余演算回数S1、並びに、他の演算法を用いる場合の乗算剰余演算回数S2を計算する。
【００５９】
演算方法制御部32は、演算回数計算部31の計算結果に基づき、数列生成部14に新たな数列Fkを算出させて数値eの分割をやり直したり、再分割法および他の演算法を選択的に制御する。
【００６０】
第一の演算部であるべき乗剰余演算部17は、再分割法によりべき乗剰余演算を行う。また、第二の演算部であるべき乗剰余演算部33は、他の演算法によりべき乗剰余演算を行う。
【００６１】
［演算処理］
図9のフローチャートにより実施例3のべき乗剰余の演算処理を説明する。なお、図9に示す処理は、図8に示す情報処理装置が行う処理である。ステップS11からS19は実施例1と同様の処理であり、それらの詳細説明を省略する。
【００６２】
演算回数計算部31は、再分割部15の分割結果ei、ejおよび数列生成部14が算出した数列Fkを入力して、第一のべき乗剰余演算部17の乗算剰余演算回数S1と、第二のべき乗剰余演算部33の乗算剰余演算回数S2を計算する(S31)。
【００６３】
この計算は、実際の演算を行わずに、乗算剰余テーブル算出部16およびべき乗剰余演算部17の処理と同じアルゴリズムにおける乗算剰余演算の総数をカウントすることにより実現することができる。例えば、M12405733 mod N (Wn：n=0, …, 12)、数列Fk={1, 2, 3, 5}の場合、乗算剰余演算回数は12である。また、例えば、Sウィンドウ法をM12405733 mod Nにウィンドウ長4ビットを適用すると、乗算剰余演算回数は13になる。
【００６４】
演算方法制御部32は、乗算剰余演算回数S1とS2を比較して(S32)、S1＜S2であれば処理をステップS18に進める。つまり、乗算剰余テーブル算出部16の処理(S18)および第一のべき乗剰余演算部17の処理(S19)が実行される。
【００６５】
また、S1≧S2の場合、演算方法制御部32は、生成可能なすべての数列Fkを生成したか否かを数列生成部14に問い合わせる(S33)。そして、生成可能な数列Fkが残っている場合は、処理をステップS14に戻して、数列生成部14に数列Fkの再生成を行わせる。つまり、ステップS14からS32の処理が繰り返される。
【００６６】
また、生成可能な数列Fkが残っていない場合、演算方法制御部32は、処理をステップS34に進める。つまり、S1≧S2かつ数列生成部14が再生成可能な数列がない場合は第二のべき乗剰余演算部33の処理(S34)が実行される。
【００６７】
このように、再分割法によるべき乗剰余演算の演算コストが他の演算法よりも高い場合は、新たな数列により処理をやり直す、または、他の演算法を適用して、べき乗剰余演算の演算コストを極力抑えることができる。
【００６８】
なお、図8には、実施例1の情報処理装置の構成に演算回数計算部31、演算方法制御部32、第二のべき乗剰余演算部33を加える構成を示した。しかし、実施例2の情報処理装置の構成に演算回数計算部31、演算方法制御部32、第二のべき乗剰余演算部33を加える構成としてもよい。そのような構成によれば、演算方法制御部32は、S1≧S2の場合、選択可能なすべての数列Fkを選択したか否かを数列生成部14に問い合わせる(S33)。そして、選択可能な数列Fkが残っている場合は、処理をステップS21に戻して、数列生成部14に数列Fkの再選択を行わせる。
【００６９】
［変形例］
●数列Fkの選択方法
実施例2、3では、ワードexを含む数列Fk（ex⊂Fk）の選択を説明したが、ワードexは複数あってもよい。つまり、図3(b)に示す例の場合、'0101' (5)だけでなく、'1111' (15)を含む数列Fk（例えば{1, 2, 3, 5, 10, 15}）を選択すれば、より効率的に数列Fkの選択処理を行うことが可能になる。
【００７０】
●べき指数eの分割処理方法
上述した実施例では、べき指数eをCLNWで分割または再分割する例を説明した。分割または再分割に用いる分割アルゴリズムは、毎回、異なってもよい。図3に示す例の場合、'1111' (15)はCLNWによって最終的に図3(d)に示すように'1'、'1'、'11'に分割される。しかし、数列Fk={1, 2, 3, 5}を適用する場合、'11'、'11'に分割すれば乗算剰余演算回数を一回削減することができる。つまり、数列Fkに適応して分割アルゴリズムを変更すれば、乗算剰余演算回数の削減が可能になる。
【００７１】
［その他の実施例］
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステムあるいは装置のコンピュータ（又はCPUやMPU等）がプログラムを読み出して実行する処理である。
【特許請求の範囲】
【請求項１】
べき指数を1ビットからビット長wの範囲で分割して複数のワードにする分割手段と、
前記複数のワードから所定のワードを選択する選択手段と、
前記選択されたワードを含み、項の総数が2w-1以下の条件を満たす数列を生成する生成手段と、
前記複数のワードのうち、前記数列に含まれないワードを前回の分割における範囲よりも1ビット少ない範囲で再分割する再分割手段と、
前記数列の各項をべき指数に含む乗算剰余テーブルを算出する算出手段と、
前記分割されたワード、前記再分割されたワード、および、前記乗算剰余テーブルを用いて前記べき指数に対するべき乗剰余演算を行う第一の演算手段とを有することを特徴とする情報処理装置。
【請求項２】
前記生成手段は、前記条件を満たす複数の数列から、前記選択されたワードを含む数列を選択することを特徴とする請求項1に記載された情報処理装置。
【請求項３】
前記再分割手段は、前記再分割したワードのうち、前記数列に含まれないワードを前回の分割よりも1ビット少ない範囲で再分割することを特徴とする請求項1または請求項2に記載された情報処理装置。
【請求項４】
前記算出手段は、前記数列が含む値が1の項を除く各項をべき指数に含む前記乗算剰余テーブルを算出することを特徴とする請求項1から請求項3の何れか一項に記載された情報処理装置。
【請求項５】
さらに、前記第一の演算手段とは異なる方法により、前記分割されたワードおよび前記再分割されたワードを用いて前記べき指数に対するべき乗剰余演算を行う第二の演算手段と、
前記数列、前記分割されたワードおよび前記再分割されたワードから、前記算出手段と前記第一の演算手段の乗算剰余演算回数S1、および、前記第二の演算手段の乗算剰余演算回数S2を計算する計算手段と、
前記乗算剰余演算回数S1とS2を用いて、前記算出手段と前記第一の演算手段による前記べき乗剰余演算、および、前記第二の演算手段による前記べき乗剰余演算を選択的に制御する制御手段とを有することを特徴とする請求項1から請求項4の何れか一項に記載された情報処理装置。
【請求項６】
前記制御手段は、S1≧S2の場合、前記生成手段に前記数列を再生成させることを特徴とする請求項5に記載された情報処理装置。
【請求項７】
前記制御手段は、S1＜S2の場合は前記算出手段と前記第一の演算手段に前記べき乗剰余演算を実行させ、S1≧S2かつ前記生成手段が再生成可能な数列がない場合は前記第二の演算手段に前記べき乗剰余演算を実行させることを特徴とする請求項6に記載された情報処理装置。
【請求項８】
分割手段、選択手段、生成手段、再分割手段、算出手段、演算手段を有する情報処理装置の情報処理方法であって、
前記分割手段が、べき指数を1ビットからビット長wの範囲で分割して複数のワードにし、
前記選択手段が、前記複数のワードから所定のワードを選択し、
前記生成手段が、前記選択されたワードを含み、項の総数が2w-1以下の条件を満たす数列を生成し、
前記再分割手段が、前記複数のワードのうち、前記数列に含まれないワードを前回の分割における範囲よりも1ビット少ない範囲で再分割し、
前記算出手段が、前記数列の各項をべき指数に含む乗算剰余テーブルを算出し、
前記演算手段が、前記分割されたワード、前記再分割されたワード、および、前記乗算剰余テーブルを用いて、前記べき指数に対するべき乗剰余演算を行うことを特徴とする情報処理方法。
【請求項９】
コンピュータ装置を請求項1から請求項7の何れか一項に記載された情報処理装置の各手段として機能させることを特徴とするプログラム。
【請求項１】
べき指数を1ビットからビット長wの範囲で分割して複数のワードにする分割手段と、
前記複数のワードから所定のワードを選択する選択手段と、
前記選択されたワードを含み、項の総数が2w-1以下の条件を満たす数列を生成する生成手段と、
前記複数のワードのうち、前記数列に含まれないワードを前回の分割における範囲よりも1ビット少ない範囲で再分割する再分割手段と、
前記数列の各項をべき指数に含む乗算剰余テーブルを算出する算出手段と、
前記分割されたワード、前記再分割されたワード、および、前記乗算剰余テーブルを用いて前記べき指数に対するべき乗剰余演算を行う第一の演算手段とを有することを特徴とする情報処理装置。
【請求項２】
前記生成手段は、前記条件を満たす複数の数列から、前記選択されたワードを含む数列を選択することを特徴とする請求項1に記載された情報処理装置。
【請求項３】
前記再分割手段は、前記再分割したワードのうち、前記数列に含まれないワードを前回の分割よりも1ビット少ない範囲で再分割することを特徴とする請求項1または請求項2に記載された情報処理装置。
【請求項４】
前記算出手段は、前記数列が含む値が1の項を除く各項をべき指数に含む前記乗算剰余テーブルを算出することを特徴とする請求項1から請求項3の何れか一項に記載された情報処理装置。
【請求項５】
さらに、前記第一の演算手段とは異なる方法により、前記分割されたワードおよび前記再分割されたワードを用いて前記べき指数に対するべき乗剰余演算を行う第二の演算手段と、
前記数列、前記分割されたワードおよび前記再分割されたワードから、前記算出手段と前記第一の演算手段の乗算剰余演算回数S1、および、前記第二の演算手段の乗算剰余演算回数S2を計算する計算手段と、
前記乗算剰余演算回数S1とS2を用いて、前記算出手段と前記第一の演算手段による前記べき乗剰余演算、および、前記第二の演算手段による前記べき乗剰余演算を選択的に制御する制御手段とを有することを特徴とする請求項1から請求項4の何れか一項に記載された情報処理装置。
【請求項６】
前記制御手段は、S1≧S2の場合、前記生成手段に前記数列を再生成させることを特徴とする請求項5に記載された情報処理装置。
【請求項７】
前記制御手段は、S1＜S2の場合は前記算出手段と前記第一の演算手段に前記べき乗剰余演算を実行させ、S1≧S2かつ前記生成手段が再生成可能な数列がない場合は前記第二の演算手段に前記べき乗剰余演算を実行させることを特徴とする請求項6に記載された情報処理装置。
【請求項８】
分割手段、選択手段、生成手段、再分割手段、算出手段、演算手段を有する情報処理装置の情報処理方法であって、
前記分割手段が、べき指数を1ビットからビット長wの範囲で分割して複数のワードにし、
前記選択手段が、前記複数のワードから所定のワードを選択し、
前記生成手段が、前記選択されたワードを含み、項の総数が2w-1以下の条件を満たす数列を生成し、
前記再分割手段が、前記複数のワードのうち、前記数列に含まれないワードを前回の分割における範囲よりも1ビット少ない範囲で再分割し、
前記算出手段が、前記数列の各項をべき指数に含む乗算剰余テーブルを算出し、
前記演算手段が、前記分割されたワード、前記再分割されたワード、および、前記乗算剰余テーブルを用いて、前記べき指数に対するべき乗剰余演算を行うことを特徴とする情報処理方法。
【請求項９】
コンピュータ装置を請求項1から請求項7の何れか一項に記載された情報処理装置の各手段として機能させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−１７３５６９（Ｐ２０１２−１７３５６９Ａ）
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願番号】特願２０１１−３６３３５（Ｐ２０１１−３６３３５）
【出願日】平成２３年２月２２日（２０１１．２．２２）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願日】平成２３年２月２２日（２０１１．２．２２）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]