(57)【特許請求の範囲】
【請求項１】
情報処理装置が実行する、１０進数の値ａの逆数である１０進数の値ｂを算出する方法であって、前記ａおよび前記ｂは奇数であり、
前記情報処理装置のプロセッサが、前記ａをビット列にするステップと、
前記プロセッサが、２の冪乗を法とする剰余体上の積算において、前記ａを２の冪乗倍した値を加算するか加算しないかを選択し、加算する場合には１とし加算しない場合には０としたビット列を前記ｂとするステップと、
前記プロセッサが、前記ｂを前記ａの逆数として算出するステップと
を含む方法。
【請求項２】
前記ａと前記ｂの積をｍとしたときに、前記ａと、前記ｂと、前記ｍとのそれぞれを複数の配列として、前記ａの逆数である前記ｂを算出する、請求項１に記載の方法。
【請求項３】
ホワイトボックス暗号方式のＡＥＳにおいて、前記ａの逆数である前記ｂを算出する、請求項１または２に記載の方法。
【請求項４】
プロセッサを備え、１０進数の値ａの逆数である１０進数の値ｂを算出する情報処理装置であって、前記ａおよび前記ｂは奇数であり、
前記プロセッサは、
前記ａをビット列にし、
２の冪乗を法とする剰余体上の積算において、前記ａを２の冪乗倍した値を加算するか加算しないかを選択し、加算する場合には１とし加算しない場合には０としたビット列を前記ｂとし、
前記ｂを前記ａの逆数として算出する、情報処理装置。
【請求項５】
１０進数の値ａの逆数である１０進数の値ｂを算出し、前記ａおよび前記ｂは奇数である情報処理装置に、
前記ａをビット列にする手順と、
２の冪乗を法とする剰余体上の積算において、前記ａを２の冪乗倍した値を加算するか加算しないかを選択し、加算する場合には１とし加算しない場合には０としたビット列を前記ｂとする手順と、
前記ｂを前記ａの逆数として算出する手順と
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、逆数算出方法、装置、およびプログラムに関する。
【背景技術】
【０００２】
従来、コンピュータによる種々のアルゴリズムにおいて、逆数の算出が用いられている（特許文献１）。
【０００３】
例えば、ホワイトボックス暗号方式（White-Box Cryptography）では、暗号鍵の値とアルゴリズムで決められている演算をルックアップテーブルへと合成する。その際、連続する演算間の入出力の部分に任意の変換と逆変換を挟み込み、変換を前の演算のルックアップテーブルに、逆変換を後の演算のルックアップテーブルに、それぞれ合成することで暗号鍵を難読化している。この難読化に適用可能な任意の変換と逆変換の演算の１つとして、積算と逆数の積算がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００２−１７５１８０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、昨今のＩｏＴ（Internet of Things）の普及により見られる計算パワーの小さい組込機器等では、積算値に対する逆数の算出の負荷が大きい。さらに、ＲＳＡ（Rivest, Shamir, Adleman）暗号等の素数を法とする剰余体上の積算では、積算後の値のビット数が積算前の値のビット数よりも増えるといった計算上の問題があった。
【０００６】
そこで、本発明の一実施形態では、バイナリデータにおいて１０進数の逆数を算出する性能を向上させることを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一実施形態に係る方法は、情報処理装置が実行する方法であって、２の冪乗を法とする剰余体上の積算において１０進数の逆数を算出する。
【発明の効果】
【０００８】
本発明の一実施形態によれば、バイナリデータにおいて１０進数の逆数を算出する性能を向上させることができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の一実施形態に係る逆数を算出する処理のフローチャートである。
【図２】本発明の一実施形態に係る逆数の算出の一例である。
【図３】本発明の一実施形態に係る逆数を算出する処理のフローチャートである。
【図４】本発明の一実施形態に係るＷｈｉｔｅ−ｂｏｘ  ＡＥＳへの適用例である。
【図５】本発明の一実施形態に係る情報処理装置のハードウェア構成の一例を示すブロック図である。
【発明を実施するための形態】
【００１０】
以下、図面に基づいて本発明の実施の形態を説明する。なお、情報処理装置１が、逆数を算出する処理を実行するものとする。
【００１１】
＜概略＞
本発明では、２の冪乗を法とする剰余体上での逆数が存在する条件を満たすため、積算値を奇数に限定する。対象の奇数を、１倍、２倍、４倍、・・・と２の冪乗倍したものを加算するまたは加算しないを、加算した値の下位側のビットから０（ゼロ）となるように選択していき、加算する（１）または加算しない（０）をビット列としたものを逆数とする。
【００１２】
積算値を奇数に限定した２の冪乗を法とする剰余体上の積算により以下が成り立つため、積算後の値は積算前の値と同じビット数で表現できる。
ｘ×ａ＝ｙ
ｙ×ｂ＝ｘ  （ｘ，ｙ，ａ，ｂは全てｎビット。ａ，ｂは奇数）
【００１３】
ｎビットの値ｘに対し、ｎビットの奇数ａを積算し、元の値と同じｎビットの値ｙに写像する。積算したｎビットの奇数ａの逆数ｂも同様にｎビットであり、積算後の値ｙにさらにこの逆数ｂを積算することで、元のｎビットの値ｘに逆変換される。積算値の逆数算出の計算量はＯ（ｎ）と小さく（ユークリッドの互除法の計算量は、０（Ｌｏｇ（２ｎ）２）である）、ブロック暗号で一般的に使われる１２８ビットのデータであったとしても、組込機器でも少ない計算負荷で逆数を算出できる。
【００１４】
＜方法＞
図１は、本発明の一実施形態に係る逆数を算出する処理のフローチャートである。
【００１５】
値ａの逆数ｂとの積をｍとする。ａ、ｂはｎビットの奇数であるとする（２の冪乗を法とする剰余体上で逆数が存在するためには、ａ、ｂは奇数である）。
【００１６】
ａ＊ａ−１ｍｏｄ２ｎ＝１（＝ｍ）
ｂ＝ａ−１＝２０ｂ０＋２１ｂ１＋２２ｂ２＋・・・  （ｂを２進数で表したものである）
ｂ０＝１  （固定（ｂは奇数であるので、ｂ０＝１である））
ｍ＝ａ＊ｂ＝ａ＊ｂ０＋２＊ａ＊ｂ１＋４＊ａ＊ｂ２＋８＊ａ＊ｂ３・・・
【００１７】
ｂ０以外の係数（上記のｂ１の係数"２＊ａ"、ｂ２の係数"４＊ａ"、ｂ３の係数"８＊ａ"、・・・）は最下位ビットが０（ゼロ）のため、ｍ０はｂ０以外とは独立している。つまり、ａ０＝ｂ０＝ｍ０＝１（固定）である。ｂ０確定下で、ｂ０、ｂ１以外の係数は下位２ビットが０（ゼロ）のため、ｍ1＝０となるｂ１は一意に算出可能である。そのため、ｂ０〜ｂ１確定下では、ｍｉ＋１＝０となるｂｉ＋１は一意に算出可能である。
【００１８】
情報処理装置１は、ｍが最終的に"１ｄ・・・ｄ０・・・０１"と下位ｎビットが最下位ビットを除いて０となるように、ｂの下位ビットから決定していく。なお、ｄは任意の値（０または１）であってよい。
【００１９】
ステップ１（Ｓ１）において、情報処理装置１は、ｍ＝ａ，ｂ０＝１とする。
【００２０】
ステップ２（Ｓ２）〜ステップ５（Ｓ５）において、情報処理装置１は、ｍｉについて、ｉ＝１からｎ−１まで順番に、
ｍｉ＝０の場合  ｂｉ＝０
ｍｉ＝１の場合  ｂｉ＝１，ｍ＝ｍ＋２ｉ＊ａ
とｍを更新しながらｂを決めていく。なお、aが奇数であるので、ｍ０＝１である。
【００２１】
例えば、ｍ1＝０の場合、ｍ1を０にする値を加算する必要はなく、ｂ1＝０と決定することができる。ｍ1＝１の場合、ｍ1を０にする値（ａを２倍した値）を加算する必要があり、ｂ1＝１と決定することができる。
【００２２】
＜算出例＞
図２は、本発明の一実施形態に係る逆数の算出の一例である。
【００２３】
図２では、１９（０００１００１１）×２７（０００１１０１１）＝１ｍｏｄ２５６（８ビットデータ），ａ＝１９，ｂ＝２７＝ａ−１の例を説明する。図２の各行は、ｉ＝０〜７のときの、乗算結果の計算過程、２ｉ×ａ、ｂｉを示す。逆数ｂの上位ビットは、乗算結果の下位ビットには影響を与えないので、最終の乗算結果が１となるよう、逆数の下位ビットから順に確定していく。
【００２４】
［ｉ＝０のとき］
図２の（１）において、ｂｉ（最下位）は、１で固定である。図２の（２）において乗算の結果が１となるために、逆数の最下位ビットは１であることが必須である。そのため、ａ×１の加算が行われる。
【００２５】
図２の（３）は、乗算結果の計算過程のｉビット目（太字）と一致している。
【００２６】
［ｉ＝１のとき］
図２の（４）において、乗算結果の１ビット目が０（ゼロ）となるよう、逆数の１ビット目は１を選択する。そのため、ａ×２の加算が行われる。
【００２７】
［ｉ＝２のとき］
図２の（５）において、２ビット目は既に０（ゼロ）なので、逆数の２ビット目は０を選択する。そのため、ａ×４の加算は行われない。
【００２８】
以下、同様に行われる。
【００２９】
［ｉ＝３のとき］
乗算結果の３ビット目が０（ゼロ）となるよう、逆数の３ビット目は１を選択する。そのため、ａ×８の加算が行われる。
【００３０】
［ｉ＝４のとき］
乗算結果の４ビット目が０（ゼロ）となるよう、逆数の４ビット目は１を選択する。そのため、ａ×１６の加算が行われる。
【００３１】
［ｉ＝５のとき］
５ビット目は既に０（ゼロ）なので、逆数の５ビット目は０を選択する。そのため、ａ×３２の加算が行われない。
【００３２】
［ｉ＝６のとき］
６ビット目は既に０（ゼロ）なので、逆数の６ビット目は０を選択する。そのため、ａ×６４の加算が行われない。
【００３３】
［ｉ＝７のとき］
７ビット目は既に０（ゼロ）なので、逆数の７ビット目は０を選択する。そのため、ａ×１２８の加算が行われない。図２の（６）において、下位８ビットの１０進数は１である。
【００３４】
＜レジスタでの演算＞
図３は、本発明の一実施形態に係る逆数を算出する処理のフローチャートである。なお、図１では本発明の概念を説明するために２のｉ乗を加算する形をとっているが、図３では実際の処理を想定し、都度２の冪乗を計算する処理やそれを格納するメモリを削減する形をとっている。
【００３５】
図１と同様に、値ａの逆数ｂとの積をｍとする。ａ、ｂは奇数であるとする。図３では、レジスタが３２ビット、値（ａ，ｂ，ｍ）が１２８ビットの場合を説明する。図３では、ａ，ｂ，ｍを３２ビットの４つの配列として扱う。
【００３６】
ａ＝ａ［３］（＝ａ１２７，ａ１２６，・・・，ａ９６），ａ［２］（＝ａ９５，・・・，ａ６４），ａ［１］（＝ａ６３，・・・，ａ３２），ａ［０］（＝ａ３１，・・・，ａ０）  なお、ｂ，ｍも同様である。
【００３７】
ステップ１１（Ｓ１１）において、情報処理装置１は、ｍ＝ａ，ｂ０＝１とする。
【００３８】
ステップ１２（Ｓ１２）〜ステップ１６（Ｓ１６）において、情報処理装置１は、ｍｉについて、ｉ＝１からｎ−１まで順番に、
ａ＝ａ×２
ｍｉ＝０の場合  ｂｉ＝０
ｍｉ＝１の場合  ｂｉ＝１，ｍ＝ｍ＋ａ
とａおよびｍを更新しながらｂを決めていく。なお、aの初期値が奇数であるので、ｍ０＝１である。
【００３９】
ｍに２の冪乗倍して加算するａについては、ｉの繰り返しにおいて都度２倍した値に更新しながらｍに加算する。
【００４０】
ステップ１３（Ｓ１３）において、以下のとおりである。
ａ＝ａ＊２：
ａ［３］＝ａ［３］＜＜１  ＯＲ  ａ［２］＞＞３１
ａ［２］＝ａ［２］＜＜１  ＯＲ  ａ［１］＞＞３１
ａ［１］＝ａ［１］＜＜１  ＯＲ  ａ［０］＞＞３１
ａ［０］＝ａ［０］＜＜１
【００４１】
ステップ１５（Ｓ１５）において、レジスタ単位での加算時の桁溢れはキャリーフラグを用いる。
ｍ＝ｍ＋ａ：
ｃｆ＝０
ｉ＝０〜３で以下繰り返し。
ｃｆｎ＝（ｍ［ｉ］＞＞１＋ａ［ｉ］＞＞１＋（ｍ［ｉ］ＡＮＤａ［ｉ］ＡＮＤ１））＞＞３１
ｍ［ｉ］＋＝ａ［ｉ］＋ｃｆ
ｃｆ＝ｃｆｎ
【００４２】
＜逆変換の証明＞
ここで、逆変換の証明について説明する。
【００４３】
ｎビットの任意の値ｘに値ａを積算し、その値にさらにａの逆数ｂを積算すると値ｘに戻ることを証明する。
【００４４】
前提：
ａ＊ｂ＝２ｎ＊Ｄ０＋１
ａにその逆数ｂを積算した値は、２の冪乗の剰余を計算すると１（Ｄは剰余計算で消える係数）となる。
【００４５】
ｘ＊ａ＝２ｎ＊Ｄ１＋ｙ
ｘにａを積算した値は、２の冪乗の剰余を計算するとｙとなる。
【００４６】
ｙ＊ｂ＝２ｎ＊Ｄ２＋ｚ
ｙに逆数ｂを積算した値は、２の冪乗の剰余を計算するとｚ（＝ｘ）となる。
【００４７】
計算プロセス比較：
ｘ＊（ａ＊ｂ）＝２ｎ＊Ｄ０＊ｘ＋ｘ
（ｘ＊ａ）＊ｂ＝２ｎ＊Ｄ１＊ｂ＋ｙ＊ｂ
＝２ｎ＊Ｄ１＊ｂ＋２ｎ＊Ｄ２＋ｚ
＝２ｎ＊（Ｄ１＊ｂ＋Ｄ２）＋ｚ
ｘに（ａ＊ｂ）を乗算したものと、（ｘ＊ａ）にｂを乗算したものは同じである。つまり、ｘ＝ｚである。
（（ｘ＊ａ）ｍｏｄ２ｎ）＊ｂ＝ｙ＊ｂ
＝２ｎ＊Ｄ２＋ｚ
【００４８】
（ｘ＊ａ）をｎビットの変数に格納（＝２の冪乗で剰余計算）した後でも、逆数ｂを積算した値に２の冪乗で剰余計算した値はｚである。
【００４９】
結論：計算過程で桁溢れが発生しても、積算・逆数積算の関係は成り立つ。
【００５０】
＜Ｗｈｉｔｅ−ｂｏｘ  ＡＥＳへの適用＞
図４は、本発明の一実施形態に係るＷｈｉｔｅ−ｂｏｘ  ＡＥＳへの適用例である。
【００５１】
図４に示されるように、本発明は、Ｗｈｉｔｅ−ｂｏｘ  ＡＥＳ（Advanced Encryption Standard）の変換ｇと逆変換ｇ−１へ適用することができる。
【００５２】
図４の（Ａ）は、入力値に逆数ｇ−１（難読化成分）を積算した値にＭｉｘＣｏｌｕｍｎｓ処理を行い、次の演算と対となる難読化成分を合成したルックアップテーブルである。
【００５３】
図４の（Ｂ）は、ＡｄｄＲｏｕｎｄＫｅｙ処理とＳｕｂＢｙｔｅｓ処理を行った後に積算値ｇ（難読化成分）を積算した値を出力するルックアップテーブルである。
【００５４】
＜効果＞
このように、従来の手法では、有効な逆数算出手段がない場合には逆数を全探索で求めていたが、本発明では、２の冪乗を法とする剰余体上で逆数を高速に算出可能である。また、本発明は暗号演算に適用可能であり、ｎビットのブロックデータにおいて、ｎ−１ビットのデータ量（上記の値ａの組み合わせ）の演算後のデータはｎビットであり、ビット数が増えない。
【００５５】
＜ハードウェア構成＞
図５は、本発明の一実施形態に係る情報処理装置１のハードウェア構成の一例を示すブロック図である。情報処理装置１は、ＣＰＵ（Central Processing Unit）１００１、ＲＯＭ（Read Only Memory）１００２、ＲＡＭ（Random Access Memory）１００３を有する。ＣＰＵ１００１、ＲＯＭ１００２、ＲＡＭ１００３は、いわゆるコンピュータを形成する。
【００５６】
また、情報処理装置１は、補助記憶装置１００４、表示装置１００５、操作装置１００６、Ｉ／Ｆ（Interface）装置１００７、ドライブ装置１００８を有することができる。なお、情報処理装置１の各ハードウェアは、バスＢを介して相互に接続されている。
【００５７】
ＣＰＵ１００１は、補助記憶装置１００４にインストールされている各種プログラムを実行する演算デバイスである。
【００５８】
ＲＯＭ１００２は、不揮発性メモリである。ＲＯＭ１００２は、補助記憶装置１００４にインストールされている各種プログラムをＣＰＵ１００１が実行するために必要な各種プログラム、データ等を格納する主記憶デバイスとして機能する。具体的には、ＲＯＭ１００２はＢＩＯＳ（Basic Input/Output System）やＥＦＩ（Extensible Firmware Interface）等のブートプログラム等を格納する、主記憶デバイスとして機能する。
【００５９】
ＲＡＭ１００３は、ＤＲＡＭ（Dynamic Random Access Memory）やＳＲＡＭ（Static Random Access Memory）等の揮発性メモリである。ＲＡＭ１００３は、補助記憶装置１００４にインストールされている各種プログラムがＣＰＵ１００１によって実行される際に展開される作業領域を提供する、主記憶デバイスとして機能する。
【００６０】
補助記憶装置１００４は、各種プログラムや、各種プログラムが実行される際に用いられる情報を格納する補助記憶デバイスである。
【００６１】
表示装置１００５は、情報処理装置１の内部状態等を表示する表示デバイスである。
【００６２】
操作装置１００６は、情報処理装置１の管理者が情報処理装置１に対して各種指示を入力する入力デバイスである。
【００６３】
Ｉ／Ｆ装置１００７は、ネットワークに接続し、他の装置と通信を行うための通信デバイスである。
【００６４】
ドライブ装置１００８は記憶媒体１００９をセットするためのデバイスである。ここでいう記憶媒体１００９には、ＣＤ−ＲＯＭ、フレキシブルディスク、光磁気ディスク等のように情報を光学的、電気的あるいは磁気的に記録する媒体が含まれる。また、記憶媒体１００９には、ＥＰＲＯＭ (Erasable Programmable Read Only Memory)、フラッシュメモリ等のように情報を電気的に記録する半導体メモリ等が含まれていてもよい。
【００６５】
なお、補助記憶装置１００４にインストールされる各種プログラムは、例えば、配布された記憶媒体１００９がドライブ装置１００８にセットされ、該記憶媒体１００９に記録された各種プログラムがドライブ装置１００８により読み出されることでインストールされる。あるいは、補助記憶装置１００４にインストールされる各種プログラムは、Ｉ／Ｆ装置１００７を介して、ネットワークよりダウンロードされることでインストールされてもよい。
【００６６】
以上、本発明の実施例について詳述したが、本発明は上述した特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００６７】
１００１  ＣＰＵ
１００２  ＲＯＭ
１００３  ＲＡＭ
１００４  補助記憶装置
１００５  表示装置
１００６  操作装置
１００７  Ｉ／Ｆ装置
１００８  ドライブ装置
１００９  記憶媒体
【要約】      （修正有）【課題】バイナリデータにおいて１０進数の逆数を算出する性能を向上させる逆数算出方法、装置およびプログラムを提供する。【解決手段】情報処理装置が実行する方法であって、２の冪乗を法とする剰余体上の積算において１０進数の逆数を算出する。【選択図】図１【図１】
0006973677.tif 000002
【図２】
0006973677.tif 000003
【図３】
0006973677.tif 000004
【図４】
0006973677.tif 000005
【図５】
0006973677.tif 000006