(57)【要約】【課題】秘密情報を保護し、かつ、効率的にシフト演算を実行できる演算装置、演算方法及び演算プログラムを提供すること。【解決手段】演算装置１は、所定のビット数の処理単位で実装された変数を並べ替えることにより、処理単位の倍数のビットシフトを行う並び替え処理部１１と、ビット長が処理単位の倍数の第１データに対して、処理単位未満のビットシフトを行った結果を示す第２データを対応付けた表を参照し、入力データをビットシフトした結果を示す出力データを抽出する表参照演算部１２と、を備え、並べ替え処理部１１及び表参照演算部１２の組み合わせにより、処理単位の倍数とは異なるビット数のシフト演算を行う。【選択図】図１
2019092030.tif 000002
【特許請求の範囲】
【請求項１】
所定のビット数の処理単位で実装された変数を並べ替えることにより、前記処理単位の倍数のビットシフトを行う並び替え処理部と、
ビット長が前記処理単位の倍数の第１データに対して、前記処理単位未満のビットシフトを行った結果を示す第２データを対応付けた表を参照し、入力データをビットシフトした結果を示す出力データを抽出する表参照演算部と、を備え、
前記並べ替え処理部及び前記表参照演算部の組み合わせにより、前記処理単位の倍数とは異なるビット数のシフト演算を行う演算装置。
【請求項２】
前記第１データは、前記処理単位の２倍のビット長であり、前記第２データは、処理単位のビット長である請求項１に記載の演算装置。
【請求項３】
前記第２データは、ビットシフトの前後にそれぞれ、逆関数が定義可能な関数が挿入された演算結果である請求項１又は請求項２に記載の演算装置。
【請求項４】
所定のビット数の処理単位で実装された変数を並べ替えることにより、前記処理単位の倍数のビットシフトを行う並び替え処理ステップと、
ビット長が前記処理単位の倍数の第１データに対して、前記処理単位未満のビットシフトを行った結果を示す第２データを対応付けた表を参照し、入力データをビットシフトした結果を示す出力データを抽出する表参照演算ステップと、
をコンピュータが組み合わせて実行し、前記処理単位の倍数とは異なるビット数のシフト演算を行う演算方法。
【請求項５】
所定のビット数の処理単位で実装された変数を並べ替えることにより、前記処理単位の倍数のビットシフトを行う並び替え処理ステップと、
ビット長が前記処理単位の倍数の第１データに対して、前記処理単位未満のビットシフトを行った結果を示す第２データを対応付けた表を参照し、入力データをビットシフトした結果を示す出力データを抽出する表参照演算ステップと、
をコンピュータに組み合わせて実行させ、前記処理単位の倍数とは異なるビット数のシフト演算を行わせるための演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、シフト演算を行う装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来、暗号プログラムを実行中に、攻撃者が全ての内部状態にアクセス可能な場合でも秘密鍵を秘匿可能な方式として、Ｗｈｉｔｅ−ｂｏｘ  Ｃｒｙｐｔｏｇｒａｐｈｙが提案されている。Ｗｈｉｔｅ−ｂｏｘ  Ｃｒｙｐｔｏｇｒａｐｈｙでは、全ての演算を表参照によって実現することで、内部状態に鍵、又は鍵を推定可能な値が現れないようにしている。
【０００３】
非特許文献１の方式では、まず、表参照で実装しやすいようにＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）の処理順序が並び替えられる。その後、鍵を含む演算については、鍵の情報を含んだ表から入力値に対応する演算結果が抽出される。例えば、入力をａ、鍵をｋとしたときに、２つの値の加算が必要な場合、全てのａに対してａ＋ｋを事前に計算した結果を格納した表を作成しておき、入力されたａと演算結果のａ＋ｋとが対応付けられる。
このとき、表のサイズが大きくなると、プログラムのサイズも大きくなるため、８ビット等の比較的小さい処理単位毎に表を複数構成することで暗号処理が実現される。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｓｔａｎｌｅｙ  Ｃｈｏｗ，  Ｐｈｉｌｉｐ  Ａ．  Ｅｉｓｅｎ，  Ｈａｒｏｌｄ  Ｊｏｈｎｓｏｎ，  Ｐａｕｌ  Ｃ．  ｖａｎ  Ｏｏｒｓｃｈｏｔ，  “Ｗｈｉｔｅ−Ｂｏｘ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  ａｎ  ＡＥＳ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，”  Ｒｅｖｉｓｅｄ  Ｐａｐｅｒｓ  ｆｒｏｍ  ｔｈｅ  ９ｔｈ  Ａｎｎｕａｌ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ，  ｐ．２５０−２７０，  Ａｕｇｕｓｔ  １５−１６，  ２００２．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ブロック暗号で用いられるシフト演算は、８ビット等の処理単位の倍数でビットをシフトする演算である。したがって、このようなシフト演算は、図４に示す８ビットの左シフトのように、処理単位毎に値の一部を抜き出して並び替えを行うことで実現される。
【０００６】
ところが、ストリーム暗号の場合、例えば１３ビット又は７ビットといった処理単位（例えば、８ビット、１６ビット等）とは異なるビット数のシフトが利用される場合（例えば、Ｓａｌｓａ２０、＜ｈｔｔｐｓ：／／ｊａ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｓａｌｓａ２０＞）があり、このようなシフト演算は、単純な並び替えのみでは実現できなかった。
また、このようなシフト演算を表参照のみで実現しようとした場合、例えば２４ビット入力８ビット出力といった大きいサイズの表が必要になるため、実装サイズが大きくなるという課題があった。
【０００７】
本発明は、秘密情報を保護し、かつ、効率的にシフト演算を実行できる演算装置、演算方法及び演算プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る演算装置は、所定のビット数の処理単位で実装された変数を並べ替えることにより、前記処理単位の倍数のビットシフトを行う並び替え処理部と、ビット長が前記処理単位の倍数の第１データに対して、前記処理単位未満のビットシフトを行った結果を示す第２データを対応付けた表を参照し、入力データをビットシフトした結果を示す出力データを抽出する表参照演算部と、を備え、前記並べ替え処理部及び前記表参照演算部の組み合わせにより、前記処理単位の倍数とは異なるビット数のシフト演算を行う。
【０００９】
前記第１データは、前記処理単位の２倍のビット長であり、前記第２データは、処理単位のビット長であってもよい。
【００１０】
前記第２データは、ビットシフトの前後にそれぞれ、逆関数が定義可能な関数が挿入された演算結果であってもよい。
【００１１】
本発明に係る演算方法では、所定のビット数の処理単位で実装された変数を並べ替えることにより、前記処理単位の倍数のビットシフトを行う並び替え処理ステップと、ビット長が前記処理単位の倍数の第１データに対して、前記処理単位未満のビットシフトを行った結果を示す第２データを対応付けた表を参照し、入力データをビットシフトした結果を示す出力データを抽出する表参照演算ステップと、をコンピュータが組み合わせて実行し、前記処理単位の倍数とは異なるビット数のシフト演算を行う。
【００１２】
本発明に係る演算プログラムは、所定のビット数の処理単位で実装された変数を並べ替えることにより、前記処理単位の倍数のビットシフトを行う並び替え処理ステップと、ビット長が前記処理単位の倍数の第１データに対して、前記処理単位未満のビットシフトを行った結果を示す第２データを対応付けた表を参照し、入力データをビットシフトした結果を示す出力データを抽出する表参照演算ステップと、をコンピュータに組み合わせて実行させ、前記処理単位の倍数とは異なるビット数のシフト演算を行わせるためのものである。
【発明の効果】
【００１３】
本発明によれば、秘密情報を保護し、かつ、効率的にシフト演算を実行できる。
【図面の簡単な説明】
【００１４】
【図１】実施形態に係る演算装置の機能構成を示す図である。
【図２】実施形態に係る演算で参照される表を例示する図である。
【図３】実施形態に係るビットシフトの演算手順を例示する図である。
【図４】従来の処理単位毎のビットシフトの演算手順を例示する図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態の一例について説明する。
図１は、本実施形態に係る演算装置１の機能構成を示す図である。
演算装置１は、制御部１０及び記憶部２０の他、各種の入出力インタフェースを備えた情報処理装置（コンピュータ）であり、制御部１０が記憶部２０に格納されたソフトウェア（演算プログラム）を実行することにより、本実施形態の各機能が実現される。
【００１６】
演算装置１は、例えばストリーム暗号方式を用いた暗号化及び復号の処理において、秘密情報（鍵情報）を秘匿した上で、各演算を、表参照を用いて処理する。
本実施形態では、参照する表のサイズを小さく保ったまま、任意のビット数のシフト演算を実現する。
制御部１０は、並び替え処理部１１と、表参照演算部１２とを備え、これらの組み合わせにより、指定されたビット数のシフト演算を行う。
【００１７】
並び替え処理部１１は、所定のビット数の処理単位で実装された変数を並べ替えることにより、処理単位の倍数のビットシフトを行う。
ここで、処理単位は通常、８ビットの倍数で実装され、例えば８ビット単位で変数がメモリ展開される。
【００１８】
表参照演算部１２は、ビット長が処理単位の倍数で設定された第１データに対して、処理単位未満のビット数のシフト演算を行った結果を示す第２データを対応付けた表を参照し、入力データをビットシフトした結果を示す出力データを抽出する。
参照される表は、記憶部２０に格納される。また、表に記述される第１データは、例えば、処理単位の２倍のビット長（例えば、１６ビット）であり、第２データは、処理単位のビット長（例えば、８ビット）である。
【００１９】
図２は、本実施形態に係る演算で参照される表を例示する図である。
この例では、３ビット右シフトの演算の入力となる１６ビットの第１データに対して、下位８ビットの演算結果が第２データとして格納されている。
表には、演算の入力として取り得る値が全て第１データに設定され、対応する演算結果が記憶される。したがって、第１データのビット数が増えるほど表のサイズが増大し、実装が困難となる。
【００２０】
ここで、表の第１データと第２データとの関係、すなわち演算の入出力の関係から秘密情報（鍵情報）が推定される場合があるため、第２データには、ビットシフトの前後にそれぞれ、逆関数が定義可能な関数が挿入された演算結果が格納される。
例えば、元のシフト演算をＴとしたとき、Ｔ’＝ｇ・Ｔ・ｆ−１（「・」は、関数の合成を表す。）のように置換することで、シフト演算Ｔにおける入出力の関係が秘匿され、メモリ展開される演算の入出力データは、演算Ｔ’の入力データとなる。
【００２１】
制御部１０は、並び替え処理部１１により処理単位（例えば、８ビット）の倍数のビットシフトを行った後、表参照演算部１２により処理単位未満のビットシフトを行うことで、あるいは、表参照演算部１２により処理単位未満のビットシフトを行った後、並び替え処理部１１により処理単位（例えば、８ビット）の倍数のビットシフトを行うことで、処理単位の倍数とは異なるビット数のシフト演算を実現する。
【００２２】
図３は、本実施形態に係るビットシフトの演算手順を例示する図である。
この例では、処理単位が８ビットの場合に、１３ビットの左シフトを、並び替え及び表参照により行う手順を示している。
【００２３】
ビット列「・・・ａｂｃｄｅｆｇｈｉｊｋｌｍｎｏｐ・・・」に対して、まず、８ビット（処理単位）の変数Ａ＝「ａｂｃｄｅｆｇｈ」及びＢ＝「ｉｊｋｌｍｎｏｐ」等を並べ替えることにより、左に１６ビットシフトさせたビット列が得られる。
【００２４】
次に、１６ビット入力８ビット出力の３ビット右シフトに相当する表参照を適用すると、変数Ａ＝「ａｂｃｄｅｆｇｈ」及びＢ＝「ｉｊｋｌｍｎｏｐ」を入力として、３ビット右シフトされた変数Ｘ＝「ｆｇｈｉｊｋｌｍ」が出力される。
同様に、変数Ｂ及びＣからは変数Ｙが出力され、このような組み合わせの演算を処理単位毎に繰り返すことで、ビット列全体を左に１３ビットシフトした結果が得られる。
【００２５】
なお、巡回シフトの場合、例えば左シフトであれば上位ビットを右シフトする必要があるが、並び替えの際に右に並び替えることで実現できる。
【００２６】
本実施形態によれば、演算装置１は、変数の並べ替えと表参照によるビットシフトとを組み合わせることにより、予め設けられる表は、処理単位未満のビットシフトに対応したサイズに抑えられる。これにより、演算装置１は、処理単位の倍数とは異なるビットシフトが要求される場合でも、秘密情報を秘匿した上で効率的に演算を実行できる。
特に、演算装置１は、ストリーム暗号を含む様々な暗号アルゴリズムにおいて、処理単位の倍数とは異なるシフト演算にＷｈｉｔｅ−ｂｏｘ実装を適用でき、ソフトウェアのみで鍵情報等の秘密情報を安全に保護できる。
【００２７】
演算装置１は、表参照で行うシフト演算の入力を処理単位（例えば、８ビット）の２倍のビット数とし、出力を処理単位（例えば、８ビット）とすることで、表参照演算を効率化し、並び替え処理との組み合わせにより任意のビット数のシフト演算をＷｈｉｔｅ−ｂｏｘ実装できる。
【００２８】
演算装置１は、並び替え及び表参照を含む各演算の内容を秘匿するために、各演算の入力データ及び出力データにそれぞれ、逆関数が定義可能な関数により変換を施す。特に、ビットシフトで用いられる表の第２データは、ビットシフトの前後にそれぞれ関数が挿入された演算結果であり、第１データと第２データとの関係から演算内容を推測することは困難である。
ストリーム暗号のプログラム全体に関数による変換が施されることにより、メモリ展開されるデータは関数により変換された値であり、実データが秘匿される。これにより、秘密情報の推定が防止される。
【００２９】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００３０】
本実施形態では、表参照によるシフト演算を、例えば１６ビットの入力から８ビットの出力のように、入力のビット長を出力の２倍として説明したが、これには限られない。
すなわち、ｍｎビットの入力からｌｎビットの出力を得る表（ただし、ｎは処理単位、ｍ及びｌはｍ＞ｌの自然数）が用いられてよい。具体的には、例えば、ｎ＝８、ｍ＝３、ｌ＝２の場合、つまり２４ビットの入力から１６ビットの出力を得る演算等であってもよい。
【００３１】
演算装置１による演算方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００３２】
１  演算装置
１０  制御部
１１  処理部
１２  表参照演算部
２０  記憶部
【図１】
2019092030.tif 000003
【図２】
2019092030.tif 000004
【図３】
2019092030.tif 000005
【図４】
2019092030.tif 000006