(57)【要約】      （修正有）【課題】暗号化の演算時間、演算コストの増大を抑制し、サイドチャネル攻撃等に対する耐性を向上させる。【解決手段】参照される要素の値を出力する表の各要素に、暗号化処理に関わる第１のビット数の値に、乱数生成手段で生成された第２のビット数の前記乱数を連結した値を設定する表生成手段と、第１のビット数の平文データに、前記乱数生成手段で生成された第２のビット数の乱数を連結した値を生成する乱数連結手段と、前記表の基準アドレスを指すポインタを更新するポインタ更新手段と、前記更新されたポインタを基準とし、前記第１のビット数のデータと第２のビット数の乱数との連結値をインデックスとして計算されるアドレスにて前記表を参照する処理を含む暗号化処理を行う暗号化手段と、前記暗号化手段の出力から乱数を除去する乱数削除手段を備える。【選択図】図５
2014115579.tif 000002
【特許請求の範囲】
【請求項１】
参照される要素の値を出力する表の各要素に、共通鍵暗号方式の暗号化処理に関わる第１のビット数の値に、乱数生成手段で生成された第２のビット数の乱数を連結した値を設定する表生成手段と、
第２のビット数の乱数を生成する前記乱数生成手段と、
第１のビット数の平文データに、前記乱数生成手段で生成された第２のビット数の乱数を連結した値を生成する乱数連結手段と、
前記表参照用の基準アドレスを指すポインタを更新するポインタ更新手段と、
前記更新されたポインタを基準とし、第１のビット数のデータと第２のビット数の乱数との連結値から計算されるアドレスにて前記表を参照する処理を含む暗号化手段と、
前記暗号化手段の出力から乱数を除去する乱数削除手段と、
を備える、ことを特徴とする暗号処理装置。
【請求項２】
前記第１のビット数をｎとし、
前記表は、ビット幅ｍ（ただし、１≦ｎ＜ｍ）の要素を２ｎ個備え、
前記第２のビット数をｓ（ただし、１≦ｓ＜（ｍ−ｎ））とし、
前記表生成手段は、前記表のｍビットの各要素において、下位ｎビットに、前記暗号化処理に関わる値を設定し、前記下位ｎビットよりも上位ビットに前記乱数生成手段で生成されたｓビットの乱数を設定し、
前記乱数連結手段は、ｎビットの平文データを下位ｎビットとし、その上位ビットに前記乱数生成手段で生成されたｓビットの乱数を連結した値を生成し、
前記ポインタ更新手段は、下位ｎビットのデータと上位ｓビットの前記乱数との連結値からなるインデックスの前記下位ｎビットを０とした値を、前記表の要素のアドレスに換算した値を、前記表の先頭アドレスを指すポインタから減算した値を、更新後のポインタとし、
前記暗号化手段は、前記更新後のポインタに、下位ｎビットのデータと上位ｓビットの乱数との連結値からなる前記インデックスのアドレス換算値を加算したアドレスにて、前記表の要素を参照し、前記表から出力されるｍビットの要素から、暗号化処理に関わるｎビットの値とｓビットの前記乱数とを連結した値を取得する、ことを特徴とする請求項１記載の暗号処理装置。
【請求項３】
前記暗号化手段は、前記表を参照する処理を含むラウンド処理を予め定められた回数行い、
前記乱数削除手段は、最終のラウンド処理の出力から乱数を削除する、ことを特徴とする請求項１又は２記載の暗号処理装置。
【請求項４】
参照される要素の値を出力する表を記憶する記憶装置を備えたデータ処理装置による暗号処理方法であって、
表作成処理では、前記表の各要素に、共通鍵暗号方式の暗号化処理に関わる第１のビット数の値に、乱数生成処理で生成された第２のビット数の前記乱数を連結した値を設定し、
乱数連結処理では、第１のビット数の平文データに、前記乱数生成処理で生成された第２のビット数の乱数を連結した値を生成し、
前記表参照用の基準アドレスを指すポインタを更新し、
前記暗号化処理では、前記更新されたポインタを基準とし、前記第１のビット数のデータと第２のビット数の乱数との連結値から求まるアドレスにて前記表を参照する処理を行い、
乱数削除処理では、前記暗号化処理の出力から乱数を除去する、
ことを特徴とする暗号処理方法。
【請求項５】
前記第１のビット数をｎとし、
前記表は、ビット幅ｍ（ただし、１≦ｎ＜ｍ）の要素を２ｎ個備え、
前記第２のビット数をｓ（ただし、１≦ｓ＜（ｍ−ｎ））とし、
前記表生成処理では、前記表のｍビットの各要素において、下位ｎビットに、前記暗号化処理に関わる値を設定し、前記下位ｎビットよりも上位ビットにｓビットの乱数を設定し、
前記乱数連結処理では、ｎビットの平文データを下位ｎビットとし、その上位ビットにｓビットの乱数を連結した値を生成し、
前記ポインタ更新処理では、下位ｎビットのデータと上位ｓビットの前記乱数との連結値からなるインデックスの前記下位ｎビット０とした値を、前記表の要素のアドレスに換算した値を、前記表の先頭アドレスを指すポインタから減算した値を、更新後のポインタとし、
前記暗号化処理では、前記更新後のポインタに、下位ｎビットのデータと上位ｓビットの乱数との連結値からなるインデックスのアドレス換算値を加算したアドレスにて、前記表の要素を参照し、前記表から出力されるｍビットの要素から、暗号化処理に関わるｎビットの値とｓビットの前記乱数とを連結した値を取得する、ことを特徴とする請求項４記載の暗号処理方法。
【請求項６】
前記暗号化処理では、前記表を参照する処理を含むラウンド処理を予め定められた回数行い、
前記乱数削除処理では、最終のラウンドの出力から乱数を削除する、ことを特徴とする請求項５記載の暗号処理方法。
【請求項７】
参照される要素の値を出力する表を記憶する記憶装置を備えたコンピュータに、
前記表の各要素に、共通鍵暗号方式の暗号化処理に関わる第１のビット数の値に、乱数生成処理で生成された第２のビット数の前記乱数を連結した値を設定する表生成処理と、
第２のビット数の前記乱数を生成する前記乱数生成処理と、
第１のビット数の平文データに、前記乱数生成処理で生成された第２のビット数の乱数を連結した値を生成する乱数連結処理と、
前記表の基準アドレスを指すポインタを更新するポインタ更新処理と、
前記更新されたポインタを基準とし、第１のビット数のデータと第２のビット数の乱数との連結値から求まるアドレスで前記表を参照する処理を含む暗号化処理と、
前記暗号化処理の出力から乱数を除去する乱数削除処理と、
を実行させるプログラム。
【請求項８】
前記第１のビット数をｎとし、
前記表は、ビット幅ｍ（ただし、１≦ｎ＜ｍ）の要素を２ｎ個備え、
前記第２のビット数をｓ（ただし、１≦ｓ＜（ｍ−ｎ））とし、
前記表生成処理では、前記表のｍビットの各要素において、下位ｎビットに、前記暗号化処理に関わる値を設定し、前記下位ｎビットよりも上位ビットにｓビットの乱数を設定し、
前記乱数連結処理では、ｎビットの平文データを下位ｎビットとし、その上位ビットにｓビットの乱数を連結した値を生成し、
前記ポインタ更新処理では、下位ｎビットのデータと上位ｓビットの前記乱数との連結値からなるインデックスの前記下位ｎビット０とした値を、前記表の要素のアドレスに換算した値を、前記表の先頭アドレスを指すポインタから減算した値を、更新後のポインタとし、
前記暗号化処理では、前記更新後のポインタに、下位ｎビットのデータと上位ｓビットの乱数との連結値からなるインデックスのアドレス換算値を加算したアドレスにて、前記表の要素を参照し、前記表から出力されるｍビットの要素から、暗号化処理に関わるｎビットの値とｓビットの前記乱数とを連結した値を取得する、ことを特徴とする請求項７記載のプログラム。
【請求項９】
前記暗号化処理では、前記表を参照する処理を含むラウンド処理を予め定められた回数行い、
前記乱数削除処理では、最終のラウンドの出力から乱数を削除する、ことを特徴とする請求項８記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理装置と方法並びに暗号処理プログラムに関する。
【背景技術】
【０００２】
記録媒体に蓄積されたデータや通信路上を流れるデータを盗聴などの脅威から保護するための技術として暗号化がある。暗号化されたデータは、暗号化に用いた鍵を知るもののみが正しく復号することができる。
代表的な暗号アルゴリズムとして、例えばＳＰＮ（substitution permutation network）構造のブロック暗号(block cipher)方式のＡＥＳ（Advanced Encryption Standard）がある。ＡＥＳは、代表的な暗号解読法（例えば、差分解読法(Differential cryptanalysis)や線形解読法（Linear cryptanalysis））に対して安全である。秘密鍵の全数探索(brute force attack)よりも効率的に鍵を求める方法は知られていない。そして、秘密鍵の全数探索には膨大な時間を要することから、ＡＥＳは安全である。
【０００３】
近年、暗号が実装された機器（暗号モジュール）において、暗号化機能が動作する際に暗号モジュールが消費する電力や、それに伴う電磁波を利用して暗号化鍵を搾取する攻撃法の脅威が指摘されている。これら副次的に得られる消費電力や電磁波に関する情報を「サイドチャネル情報」、それらを利用した攻撃は「サイドチャネル攻撃」と呼ばれる。
【０００４】
サイドチャネル攻撃の原理を説明する。
【０００５】
ｎビットデータｄのハミングウェイトh(d)は、
h(d)∈｛0,1,2,... ,n｝
である。ハミングウェイトとは、データを２進数表現したときの１の数である。例えば、ｎ＝８の場合、
h(00000000) = 0、
h(00001000) = 1、
h(00100011) = 3、
h(11111111) = 8
となる。
【０００６】
解析対象の暗号モジュールがハミングウェイトモデルに基づくならば、データのハミングウェイトと消費電力、漏洩電磁波は正比例すると仮定する。ハミングウェイトモデルに基づく、暗号アルゴリズムの解析手順（関連技術）について以下に説明する。図１は、ブロック長が２ｎビットのｒラウンドFeistel型暗号（関連技術）を説明する図である。
【０００７】
２ｎビットの平文Ｐはｎビットのデータｘ０Ｌ、ｘ０Ｒに分割される。第ｉラウンド（i=1,2,...,r-1）の処理は式(1)及び式(2)のとおりである。
【０００８】
ｘｉＲ＝ｘｉ−１Ｌ        ・・・(1)
【０００９】
2014115579.tif 000003
【００１０】
なお、
2014115579.tif 000004
はビット毎の排他的論理和（bitwise XOR）の演算子である。
【００１１】
最終のラウンド（第ｒラウンド）ではデータの左右のクロスを行わない。ｘｒＬ、ｘｒRは式(3)及び式(4)のとおりである。
【００１２】
ｘｒＬ＝ｘｒ−１Ｌ  ・・・(3)
【００１３】
2014115579.tif 000005
【００１４】
ｘｒＬとｘｒＲを連結した２ｎビットデータｘｒＬ||ｘｒＲが暗号文Ｃとなる。なお、||は連結（concatenation）演算子である。
【００１５】
図２は、図１のＦ関数１０の構成例（関連技術）を例示した図である。図２を参照すると、データｘｉＬと鍵Ｋｉを排他的論理和演算した結果を、非線形処理１１で演算Ｓを施し、出力データｚｉが生成される。つまり、
ｚｉ＝Ｓ（ｘｉＬ ^Ｋｉ）       ・・・(5)
である。なお、＾はC言語等で用いられる、ビット毎の排他的論理和（bitwise XOR）の演算子である（以下、排他的論理和演算子として＾を用いる）。
【００１６】
次に、サイドチャネル情報を用いて最終ラウンドの鍵Ｋｒ−１を求める手順を示す。解析はデータ収集フェーズと解析フェーズから成る。
【００１７】
データ収集フェーズでは、ｍ個の平文Ｐｊ（j=0, 1, ..., m-1）を暗号化し、ｍ個の暗号文Ｃｊを得る。このとき、オシロスコープやスペクトラムアナライザ等などの測定器（波形解析装置）を用いて暗号化処理中の消費電力を測定する。ここで、平文Ｐｊを暗号化するときに測定した電力波形をｗｊとする。
【００１８】
解析フェーズとして差分電力解析（Differential Power Analysis:ＤＰＡ）を例に説明する。
【００１９】
鍵Ｋｒ−１の候補は２ｎ通りあるので、ｎビットが全て０から順に仮定していく。
【００２０】
ｘｒ−１Ｌ（＝ｘｒＬ）は暗号文Ｃｊより既知であるから、鍵Ｋｒ−１を仮定することによりＦ関数の出力データｚｉを計算することができる。
【００２１】
ここで、ｚｉの特定の１ビットに注目し、当該ビットが０になった暗号文に対応する波形データと、当該ビットが１になった暗号文に対応する波形データとに分類する。当該ビットの値が０として分類された波形の集合をＷ０、当該ビットの値が１として分類された波形の集合をＷ１とする。
【００２２】
次にＷ０とＷ１のそれぞれについて消費電力値の平均Ｗ０avg、Ｗ１avgを計算する。
【００２３】
ハミングウェイトモデルに基づくならば、ｚｉの計算が実行された時刻のＷ０よりもＷ１の消費電力が大きくなる（残りのｎ−１ビットはノイズ成分となるが、多数の波形の平均をとることで平準化されると考える）。このため、ｚｉの特定の１ビットが０、１となった暗号文の波形集合への分類が正しく行われていれば、Ｗ１avgからＷ０avgを引くと顕著に差が現れる（図９（Ｂ）参照）。
【００２４】
しかし、鍵Ｋｒ−１の仮定が誤っている場合、正しく分類されない（Ｗ０（Ｗ１）にはビット値が１（０）となる波形が混在する）。このため、Ｗ０ａｖｇとＷ１ａｖｇの間に差が見られなくなる（図９（Ａ）参照）。
【００２５】
よって、平均波形のピーク値を調べることにより、鍵の仮定が正しいか否かを区別することができる。
【００２６】
一方、サイドチャネル攻撃に対する耐タンパ（tamper resistant）技術の一つとしてマスキング手法が挙げられる。図１の暗号化処理にマスキング手法を施した場合の動作の参考例を、図３を用いて説明する。なお、この参考例では、ソフトウェアで実装された暗号化処理を前提とする。
【００２７】
図３において、α１、α２、α３は、それぞれｎビットの乱数データであり、
α３＝α１＾α２      ・・・(6)
である。
【００２８】
そして、図２の非線形処理１１の代わりに、非線形処理３０を用いる。図３（Ｂ）に示すように、非線形処理３０では、入力データとα１との排他的論理和演算結果に対して非線形処理１１を行う。そして、非線形処理１１の出力データとα３との排他的論理和演算結果を非線形処理３０の出力データとする。
【００２９】
一般に、ソフトウェアによる実装の場合、非線形処理は例えば表（ルックアップテーブル）で実装される。非線形処理の入力データをｎビットとすると、表は、２ｎ個のエントリを持つ。入力データが表のインデックスとなり、表の各エントリに、入力データに対する演算結果を保持する。非線形処理時には、１回の表参照で演算結果（非線形処理結果）を得ることができる。
【００３０】
マスキング手法では、α１、α２を決定するごとに、表Ｓを基に、新たな表Ｓ’を生成する。
【００３１】
暗号化処理を行う場合、まず分割された平文ｘ０Ｌ、ｘ０Ｒに対してそれぞれα１、α２との排他的論理和をとる。
【００３２】
そして、ｘ０Ｌとα１との排他的論理和（ｘ０Ｌ＾α１）に対して鍵Ｋ０との排他的論理和をとり、非線形処理３０に入力する。非線形処理３０の入力データは、
（（ｘ０Ｌ＾α１）＾Ｋ０）＝（ｘ０Ｌ＾α１＾Ｋ０）    ・・・(7)
である。
【００３３】
図３（Ａ）において、非線形処理３０では、入力データとα１との排他的論理和をとるため、α１がキャンセルされ、非線形処理１１に入力されるデータは、等価的に、
（ｘ０Ｌ＾Ｋ０）      ・・・(8)
となる。
【００３４】
図３（Ａ）において、非線形処理３０の出力データｚ０は、図３（Ｂ）において、非線形処理１１の出力Ｓ(ｘ０Ｌ＾Ｋ０）に対してα３との排他的論理和をとったものである。
ｚ０＝（Ｓ(ｘ０Ｌ＾Ｋ０）＾α３）      ・・・(9)
【００３５】
図３（Ａ）において、排他的論理和３１では、
ｚ０＾（ｘ０Ｒ＾α２）      ・・・(10)
が行われる。このため、α３とα２の排他的論理和によりα１が生成される。すなわち、
（Ｓ(ｘ０Ｌ＾Ｋ０）＾α３）＾（ｘ０Ｒ＾α２）
＝Ｓ(ｘ０Ｌ＾Ｋ０）＾（α１＾α２）＾（ｘ０Ｒ＾α２）
＝Ｓ(ｘ０Ｌ＾Ｋ０）＾α１＾α２＾α２＾ｘ０Ｒ
＝Ｓ(ｘ０Ｌ＾Ｋ０）＾α１＾ｘ０Ｒ        ・・・(11)
【００３６】
式(11)のＳ(ｘ０Ｌ＾Ｋ０）＾ｘ０Ｒは、図１のｘ１Ｌに対応するため、式(11)は、
ｘ１Ｌ＾α１
と表される。
【００３７】
よって、第１ラウンドの出力データｘ１Ｌは、α１でマスクされた状態で生成される。
【００３８】
一方、
ｘ１Ｒ＝ｘ０Ｌ＾α１＾α３＝ｘ０Ｌ＾α２    ・・・(12)
である。
【００３９】
式(12)のｘ０Ｌは、図１のｘ１Rに対応するため、式(12)は、
ｘ１R＾α２
と表される。
【００４０】
このように、第(ｉ＋１)ラウンドの入力データ
ｘｉＬはα１でマスクされ、
ｘｉＲはα２でマスクされた状態となる。
【００４１】
最終ラウンドでのデータｘｒＬ、ｘｒＲは、それぞれ、
ｘｒ−１Ｌ＾α１                                  ・・・(13)
Ｓ(ｘｒ−１Ｌ＾Ｋｒ−１）＾α１＾ｘｒ−１Ｒ        ・・・(14)
となり、いずれもα１でマスクされる。
【００４２】
このため、(13)、(14)のそれぞれにα１と排他的論理和をとることで、ｘｒＬ、ｘｒＲは、式(15)、(16)となる。
【００４３】
ｘｒＬ＝（ｘｒ−１Ｌ＾α１）＾α１＝ｘｒ−１Ｌ      ・・・(15)
ｘｒＲ＝（Ｓ(ｘｒ−１Ｌ＾Ｋｒ−１）＾α１＾ｘｒ−１Ｒ）＾α１
＝（Ｓ(ｘｒ−１Ｌ＾Ｋｒ−１）＾ｘｒ−１Ｒ）    ・・・(16)
【００４４】
ｘｒＬ、ｘｒＲのいずれもマスクが解除され、暗号文Ｃ（=ｘｒ−１Ｌ||ｘｒＲ）が得られる。
【００４５】
このように、マスキング手法では、常に、乱数でマスクされているため、差分電力解析を適用しても、電力波形は乱数でマスクされたものになる。よって、乱数値が不明であれば、鍵仮定を行って計算した中間値と、実際の消費電力の相関が崩れるため、差分電力解析が困難になる。しかしながら、乱数値も同時に仮定すれば、差分電力解析による解析は可能となることから、乱数値を暗号化処理毎に変化させる必要がある。
【００４６】
なお、本件に関連して出願人が行った先行技術文献検索でサーチされた特許文献１には、暗号処理を実行する際の電力消費量を計測することで、暗号モジュールに埋め込まれている暗号鍵を解析する攻撃方法に対して安全な暗号化装置として前記鍵によって予め定められた処理がされた入力データに対して、乱数に依存して決まる予め定められた入力マスク値が加算されたランダム化入力データと前記入力マスク値とを受け付けて、前記入力マスク値の逆元である出力マスク値が、前記入力データの逆元に対して加算されたランダム化出力データを生成するランダム化８ビット逆元計算部を備えており、生成された当該ランダム化出力データから暗号文を生成する構成が開示されている。また差分電力解析（DPA）に対して安全な暗号化装置として特許文献２には暗号化装置は、乱数を発生する乱数発生器手段と、乱数に従ってｑ個の固定値の中の１つを選択する第１の選択器と、乱数に従ってｑ組の固定テーブルの中の１組を選択する選択器と、を備え、排他的論理和手段は、固定値と鍵の排他的論理和と入力の排他的論理和をとり、非線形変換手段は、１組の固定テーブルに従って非線形変換を行う構成が開示されている。特許文献３には、ＤＰＡまたはＥＭＡ（Electro-Magnetic Analysis）タイプの攻撃に対抗するための暗号回路として特許文献３には、暗号アルゴリズムを実行するための関数鍵ｋｃを含む暗号回路であって、前記回路はｋｃとは別の前記回路のそれぞれの例に特有の、回路のサイドチャネルを利用した攻撃から回路を保護することを可能とする第２の鍵ｋｉを含む構成が開示されている。
【先行技術文献】
【特許文献】
【００４７】
【特許文献１】特再公表ＷＯ２００８−１４６４８２号公報
【特許文献２】特開２００２−３６６０２９号公報
【特許文献３】特表２００２−５１６０９４号公報
【発明の概要】
【発明が解決しようとする課題】
【００４８】
以下に関連技術の分析を与える。
【００４９】
上記したように、ソフトウェア実装された暗号モジュールをサイドチャネル攻撃の脅威から保護するためには、マスキング手法が有効である。しかしながら、マスクに用いる乱数値を暗号化処理毎に変更しなければならない。乱数値を変更すると、非線形処理結果を保持している表を乱数に応じて生成する必要がある。この表の生成時間が、暗号化処理時間の増加原因となり、パフォーマンスの低下に繋がる。
【００５０】
なお、単一の表を用いる暗号アルゴリズムであっても、表参照毎に、マスク値が変わる場合、マスク値毎に、表を持つ必要がある。このため、メモリ領域が増加する。
【００５１】
本発明は、上記課題を解決するために創案されたものであって、その目的は、暗号化処理の演算時間、演算コストの増大を抑制し、且つサイドチャネル攻撃等に対する耐性を向上させる装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００５２】
本発明によれば、参照される要素の値を出力する表の各要素に、共通鍵暗号方式の暗号化処理に関わる第１のビット数の値に、乱数生成手段で生成された第２のビット数の乱数を連結した値を設定する表生成手段と、
第２のビット数の乱数を生成する前記乱数生成手段と、
第１のビット数の平文データに、前記乱数生成手段で生成された第２のビット数の乱数を連結した値を生成する乱数連結手段と、
前記表の基準アドレスを指すポインタを更新するポインタ更新手段と、
前記更新されたポインタを基準とし、前記第１のビット数のデータと第２のビット数の乱数との連結値から計算されるアドレスにて前記表を参照する処理を含む暗号化処理を行う暗号化手段と、
前記暗号化手段の出力から乱数を除去する乱数削除手段と、
を備える暗号処理装置が提供される。
【００５３】
本発明によれば、参照される要素の値を出力する表を記憶する記憶装置を備えたデータ処理装置による暗号処理方法であって、
表作成処理では、前記表の各要素に、共通鍵暗号方式の暗号化処理に関わる第１のビット数の値に、乱数生成処理で生成された第２のビット数の前記乱数を連結した値を設定し、
乱数連結処理では、第１のビット数の平文データに、前記乱数生成処理で生成された第２のビット数の乱数を連結した値を生成し、
ポインタ更新処理では、前記表の基準アドレスを指すポインタを更新し、
暗号化処理では、前記更新されたポインタを基準とし、第１のビット数のデータと第２のビット数の乱数との連結値から求まるアドレスで前記表を参照する処理を含む暗号化処理を行い、
乱数削除処理では、前記暗号化処理の出力から乱数を除去する、暗号処理方法が提供される。
【００５４】
本発明によれば、参照される要素の値を出力する表を記憶する記憶装置を備えたコンピュータに、
前記表の各要素に、共通鍵暗号方式の暗号化処理に関わる第１のビット数の値に、乱数生成処理で生成された第２のビット数の前記乱数を連結した値を設定する表生成処理と、
前記第２のビット数の前記乱数を生成する前記乱数生成処理と、
第１のビット数の平文データに、前記乱数生成処理で生成された第２のビット数の乱数を連結した値を生成する乱数連結処理と、
前記表の基準アドレスを指すポインタを更新するポインタ更新処理と、
前記更新されたポインタを基準とし、第１のビット数のデータと第２のビット数の乱数との連結値から求まるアドレスで前記表を参照する処理を含む暗号化処理を行う暗号化処理と、
前記暗号化処理の出力から乱数を除去する乱数削除処理と、
を実行させるプログラムが提供される。本発明によれば、該プログラムを記録した記録媒体（半導体メモリ、あるいは磁気／光ディスク等）が提供される。
【発明の効果】
【００５５】
本発明によれば、暗号化の演算時間、演算コストの増大を抑制し、サイドチャネル攻撃等に対する耐性を向上させることができる。
【図面の簡単な説明】
【００５６】
【図１】Feistel型暗号の一例を示す図である。
【図２】図１のＦ関数の構造を説明する図である。
【図３】図１に対するマスキング手法の適用例を説明する図である。
【図４】本発明の一実施形態の暗号処理装置の構成例を示す図である。
【図５】暗号化手段の構成例を示す図である。
【図６】図１に対する本発明の適用例を説明する図である。
【図７】暗号オリジナルの表と乱数を付与した表の例を示した図である。
【図８】本発明の一実施形態の処理手順をフローチャートにて示す図である。
【図９】（Ａ）は、差分電力解析を行った際の鍵の推定が誤っている場合、（Ｂ）は正しい場合の平均波形の例を説明する図である。
【発明を実施するための形態】
【００５７】
以下、本発明の実施形態について図面を参照して詳細に説明する。本発明によれば、乱数生成手段で生成した乱数と平文を連結したデータに暗号化処理を施し、その後乱数を削除する構成としたものである。
【００５８】
本発明は、以下に説明するように、データの通信や蓄積の際にデータを秘匿するための共通鍵ブロック暗号のサイドチャネル攻撃の耐タンパに適用して好適とされる。
【００５９】
本発明の形態によれば、参照される要素の値を出力する表（Ｓ’）の各要素に、共通鍵暗号方式の暗号化処理に関わる第１のビット数（ｎビット）の値に、乱数生成手段で生成された第２のビット数（ｓビット）の前記乱数を連結した値を設定する表生成手段（図５の７１）と、
第２のビット数の乱数を生成する前記乱数生成手段（図５の７０）と、
第１のビット数の平文データに、前記乱数生成手段（図５の７０）で生成された第２のビット数の乱数を連結した値を生成する乱数連結手段（図５の７２）と、
第１のビット数の暗号データと第２のビット数の前記乱数との連結値をインデックスとして前記表（Ｓ’）の参照が行えるように、前記表（Ｓ’）の基準アドレス（例えば先頭アドレス）を指すポインタ（S'addr）を更新するポインタ更新手段（図５の７４）と、
前記更新されたポインタ（S'addr）を基準とし、前記第１のビット数の暗号データと第２のビット数の乱数との連結値をインデックスとして計算されるアドレスにて前記表を参照する処理を含む暗号化処理を行う暗号化手段（図５の７３）と、
前記暗号化手段の出力から乱数を除去する乱数削除手段（図５の７５）と、を備える。
【００６０】
前記第１のビット数をｎとし、前記表（Ｓ’）は、ビット幅ｍ（ただし、１≦ｎ＜ｍ）の要素を２ｎ個備え、第２のビット数をｓ（ただし、１≦ｓ＜（ｍ−ｎ））とする。前記表生成手段（図５の７１）は、前記表（Ｓ’）のｍビットの各要素において、下位ｎビットに、暗号化処理に関わる値を設定し、前記下位ｎビットよりも上位ビットにｓビットの乱数（図７（Ｂ）のαｉ，ｉ＝０〜２ｎ−１）を設定する。前記乱数連結手段（図５の７２）は、ｎビットの平文データの上位ビットに、ｓビットの乱数を連結した値を生成する。前記ポインタ更新手段（図５の７４）は、例えば、下位ｎビットのデータと上位ｓビットの乱数との連結値（ｙ）の下位ｎビット０とする演算結果（ｙ∩１（ｍ−ｎ）||０（ｎ））を、前記表（Ｓ’）の要素のアドレスに換算した値（ｙ<<ｔ；<<ｔはｔビット左シフト演算、ｔは表１要素当りのバイト数）を、前記表の先頭アドレスを指すポインタから減算した値を、更新後のポインタ（S’addr）とする。前記暗号化手段（図５の７３）は、前記更新後のポインタ（S’addr）に、下位ｎビットのデータと上位ｓビットの乱数との連結値（ｙ）からなるインデックスをアドレスに換算した値(y<<t)を加算したアドレスにて、前記表（Ｓ’）の要素を参照し、前記表から出力されたｍビットの要素から、暗号化処理に関わるｎビットの値とｓビットの乱数とを連結した値を取得する。前記暗号化処理で扱う暗号は、共通鍵方式のブロック暗号である。
【００６１】
前記暗号化手段（図５の７３）は、前記表を参照する処理を含むラウンド処理を予め定められた回数行い、前記乱数削除手段（図５の７５）は、最終のラウンド処理の出力から乱数を削除する。前記乱数連結手段（図５の７２）は、入力された平文から、ｎビットの第１、第２の平文データ（ｘ０Ｌ、ｘ０Ｒ）の上位ビットにｓビットの第１、第２の乱数（β０、β１）を連結したｍビットの第１、第２のデータ（β１||ｘ０Ｌ、β０||ｘ０R）をそれぞれ生成する。特に制限されないが、暗号化手段（図５の７３）においては、前記第１のデータ（β１||ｘ０Ｌ）を、下位ｎビットのラウンド鍵（Ｋ０）と、上位（ｍ−ｎ）ビット０とを連結した値（０（m-n）||Ｋ０）で排他的論理和演算を施す第１の排他的論理和演算部と、前記排他的論理和演算結果を、前記インデックスとし、前記更新ポインタ（S’addr）を用いて、前記表（Ｓ’）を参照する非線形処理部（３０１）と、前記非線形処理部（３０１）のｍビットの出力(ｚ０)と、前記第２のデータ（β０||ｘ０R）との排他的論理和演算をとる第２の排他的論理和演算部を備え、前記第１データと、前記第２の排他的論理和演算部の出力をクロスさせて、次のラウンドの第１、第２のデータとする構成としてもよい。前記乱数削除手段（図５の７５）は、最終段のラウンドから出力されるβｒ||ｘｒＬの乱数βｒ、βｒ＋１||ｘｒRの乱数βｒ＋１を削除する。なお、前記表（Ｓ’）を参照するインデックスは、データとラウンド鍵との排他的論理和（鍵加算：Add-Round-Key）に制限されるものでないことは勿論である。例えばＡＥＳの各ラウンドのミックスカラム（Mix-Columns）等の処理において事前計算結果を表に実装する構成等にも適用可能である。
【００６２】
なお、上記特許文献１−３等には、乱数生成手段で生成した乱数と平文を連結したデータに暗号化処理を施し、その後乱数を削除することで、暗号化処理の演算コストの増大を抑制する構成は開示されていない。
【００６３】
図４を参照すると、一実施形態の暗号化装置１は、入出力装置２、ＣＰＵ（Central Processing Unit）３、ＲＡＭ(Random Access Memory)４、ＲＯＭ(Read Only Memory)５がバス６で接続された構成をとる。ＲＯＭ５には、暗号化処理プログラム７が格納されている。暗号化処理プログラムが実行される際には、ＲＯＭ５から暗号化処理プログラムが読み出されてＲＡＭ４にロードされる。ＣＰＵ３は、ＲＡＭ４からプログラムを読み込み（フェッチ）し、解釈、実行することで、暗号化処理が実行される。ただし、暗号化処理プログラムは、入出力装置２を介して外部からロードされ、ＲＡＭ４に展開される構成としてもよい。暗号化鍵は、ＲＯＭ５に格納しておく形態としてもよいし、あるいは入出力装置２より外部から入力する構成としてもよい。ＲＯＭ５は、電気的に書き換え消去可能な不揮発性メモリ（ＲＯＭ）であってもよい。あるいは、暗号化処理プログラム７はＨＤＤ（Hard Disk Drive)等の不揮発性の補助記憶装置等に記憶してもよいことは勿論である。
【００６４】
耐タンパ機能を施した暗号化処理プログラムの動作について以下に説明する。図５を参照すると、暗号化処理プログラム７は、乱数生成手段７０、表生成手段７１、乱数連結手段７２、暗号化手段７３、ポインタ更新手段７４、乱数削除手段７５にモジュール分割（あるいは機能分割）される。各手段の機能・動作について説明する。
【００６５】
乱数生成手段７０はｓビット（１≦ｓ＜ｍ−ｎ）の乱数を生成する。
【００６６】
表生成手段７１は、乱数生成手段７０で生成したｓビット（例えばｓ＝２２）の乱数を用いて、暗号化手段７３で参照する表の更新を行い、表Ｓ’を作成する。表Ｓ’は、暗号化装置１のＲＡＭ４に格納される。
【００６７】
具体例として、図７（Ａ）の表Ｓを用いて説明する。図７（Ａ）では、ｍ＝３２、ｎ＝８として説明を行う。表Ｓは、２５６（＝２８）個の要素で構成され、１つの要素は、３２ビットである。各要素の下位８ビットには、暗号化処理に関する値（図７は、16進数表記（1ヘキサデジット＝４ビット：０〜F）が設定されており、上位２４ビットはオール０である。なお、下位８ビットと上位２４ビットの間の記号||は連結（concatenation）を表しており、上位２４ビットと下位８ビットとを連結して３２ビットとなる。
【００６８】
多くの暗号アルゴリズムでは、何がしかの演算処理について事前計算を行い演算結果を表形式で保持する形態（ルックアップテーブル(Look Up Table: LUT)方式）がとられる。暗号化処理時に、演算前データを、表のインデックスとして、表参照を行うことで、演算結果を得る。
【００６９】
表生成手段７１は、乱数生成手段７０で生成したｓビットの乱数を、表の各要素の０が設定されている位置（下位ｎビットよりも上位の（ｍ−ｎ）の領域）に設定する。なお、設定する乱数は、表の要素ごとに異なっていてもよいし、全て同一であってもよい。図７（Ｂ）の表Ｓ’は、図７（Ａ）の表Ｓに対して、乱数生成手段７０で生成された乱数αｉ（ｉ∈｛0, 1, 2, ..., 255｝）を設定した後の表である。
【００７０】
乱数連結手段７２には、暗号化する平文データと、乱数生成手段７０で生成した乱数の２つが入力される。ｂ×ｎビットの平文は、ｂ個のｎビット平文データに分割され、各々が、ｍビット変数（ｍ＞ｎ、ｍ＝２４、ｎ＝８）に保持される。ｍビット変数の下位ｎビットに平文が設定され、上位ビット（ｍ−ｎ）の領域にｓビットの乱数が設定される。
【００７１】
暗号化手段７３とポインタ更新手段７４の処理について、図６を参照して説明する。図６は、図１と図２に示した暗号化処理を耐タンパ化したものに相当する。
【００７２】
図６において、β１||ｘ０Ｌ、β０||ｘ０Ｒは、乱数連結手段７２によって分割されたｎビット平文ｘ０Ｌ、ｘ０Ｒの上位ビットに、それぞれ、ｓビットの乱数β０、β１が連結されたデータである。
【００７３】
β１||ｘ０Ｌは、ｍビットの鍵０（ｍ−ｎ）||Ｋ０と排他的論理和演算され、演算結果が、非線形変換処理３０１によって変換される。なお、鍵０（ｍ−ｎ）||Ｋ０の上位（ｍ−ｎ）ビットは０、下位ｎビットがＫ０となる。
【００７４】
非線形変換処理３０１は、表生成手段７１で生成された表Ｓ’を参照することにより、ルックアップテーブル（LUT）方式で、非線形処理を実行する。
【００７５】
一般的な表参照の手順を示す。表は、メモリ上に連続的に配置されたデータであり、表の先頭アドレスのデータをポイントするポインタ(アドレスポインタ)Ｓaddrとして保持する。表のインデックスｘは、先頭アドレスからの変位となるため、ポインタにインデックスを加算し、当該データが保存されているメモリアドレスを得る。より正確には、表の要素が２ｔバイトのとき、先頭アドレスからの変位ｘは（ｘ<<ｔ）バイトとなる。<<は左シフト演算子（bit-wise left shift operator）である。例えば図７において要素は、32ビット＝4バイト＝22＝2ｔバイトから、ｔ＝2となる、インデクスｘ＝2（"00000010"）に対して左２ビットシフトした(2<<2)は、８（="00001000"）となる。インデクスｘ＝2に対して表の先頭アドレスから８バイト目の４バイト（１要素）がアクセスされる。したがって、インデックスｘで参照される表の要素のアクセスアドレスＸaddrは、式(17)で計算される。
【００７６】
Ｘaddr＝Ｓaddr＋（ｘ<<ｔ）  ・・・(17)
【００７７】
ここで、表のエントリ数（要素の総数）が２ｎ個であれば、インデックスｘは０≦ｘ≦２ｎ−１である。図７のｍ＝３２、ｎ＝８、ｔ＝２の場合、ＸaddrはＳaddr〜Ｓaddr＋1020となる。なお、表アクセスの基準となるアドレスを表の先頭アドレスでなく、表の最終要素（インデックス＝２ｎ−１）をポイントするアドレス（Ｓaddr）とした場合、インデックスｘ（０≦ｘ≦２ｎ−１）に対してアドレスＸaddrは、
Ｘaddr＝Ｓaddr−｛（２ｎ−1−ｘ）<<ｔ）｝  ・・・(17)’
で与えられる。
【００７８】
しかしながら、本実施形態のように、インデックスの上位ビットに０以外の値が設定されている場合には、上記手順では、正しく要素のアドレスを計算することができない。
【００７９】
図６において、β１||ｘ０Ｌと鍵０（ｍ−ｎ）||Ｋ０との排他的論理和演算結果β１||（ｘ０Ｌ＾Ｋ０）の上位（ｍ−ｎ）ビットには、ｓビットの乱数β１（０以外の値）が設定されている。β１||（ｘ０Ｌ＾Ｋ０）の下位ｎビットは、暗号化データｘ０Ｌ＾Ｋ０である。このβ１||（ｘ０Ｌ＾Ｋ０）が、非線形変換処理３０１に入力される。
【００８０】
そこで、ポインタ更新手段７４は、（乱数||暗号化データ）、例えば（β１||（ｘ０Ｌ＾Ｋ０））から、表Ｓ’の先頭アドレスのポインタを変更(更新)する。
【００８１】
ポインタ更新手段７４は、表参照を行う際のインデックスとなる変数ｙ（上記β１||（ｘ０Ｌ＾Ｋ０）のように、上位ビットに乱数、下位ｎビットは暗号化データ）を用いて、表参照が行えるように、上位ビットの乱数を残し下位ｎビットを０とした値を、ｔビット（ただし、ｔは表１要素のバイト数）左シフトしたデータを生成し、これを表の先頭アドレスを示すポインタＳａｄｄｒから減算した値を新たな先頭アドレスポインタとすることで、変数ｙ（上記β１||（ｘ０Ｌ＾Ｋ０）を用いて、暗号化データｘ０Ｌ＾Ｋ０に対応する表の各要素（０≦インデックス≦（２ｎ−１））がアクセスされる。
【００８２】
すなわち、式(18)によってＳaddrを更新し、ポインタＳ’addrを生成する。
【００８３】
Ｓ’addr＝Ｓaddr−（（ｙ∩１（ｍ−ｎ）||０（ｎ））<<ｔ）  ・・・（18）
【００８４】
式(18)において、∩はビット毎のAND演算を行う演算子である。１（ｍ−ｎ）||０（ｎ）の０（ｎ）は下位ｎビットの０データ、１（ｍ−ｎ）は上位（ｍ−ｎ）ビットの１データである。インデックスとなるｍビットの変数ｙ（上位（ｍ−n）ビットの領域に配置されたｓビットの乱数と下位ｎビットの暗号化データの連結）と、ｍビット情報１（ｍ−ｎ）||０（ｎ）とのビット毎のAND演算をとった結果（上位（ｍ−ｎ）ビットの領域にはｓビットの乱数、下位ｎビットは０）を、ｔビット左シフトした値をポインタＳaddrから減算することで、ポインタＳ’addrを求める。
【００８５】
非線形変換処理３０１において、ｙ＝β１||（ｘ０Ｌ＾Ｋ０）で表Ｓ’をアクセスする場合、インデックスｙで、参照される表の要素のアクセスアドレスＸaddrは以下で計算される。
【００８６】
Ｘaddr＝Ｓ’addr＋（ｙ<<ｔ）  ・・・(19)
【００８７】
暗号化手段７３において、表参照を行うたびに、ポインタ更新手段７４を呼び出し、変数に応じたポインタＳ’addrを生成する。Ｓ’addrを用いて表Ｓ’（図７（Ｂ）参照）の参照を行い、当該要素（αｉ||暗号化処理の値）がｚ０となる。
【００８８】
よって、第１ラウンドの出力β２||ｘ１Ｌは、
ｚ０＾（β０||ｘ０Ｒ）  ・・・（20）
で計算される。
【００８９】
このとき、ｚ０の上位（ｍ−ｎ）ビットの乱数αｉと、（β０||ｘ０Ｒ）の上位（ｍ−ｎ）ビットの乱数β０との排他的論理和がβ２となる。
【００９０】
β２＝β０＾αｉ  （0≦ｉ≦255）    ・・・（21）
【００９１】
以上の処理を、所定ラウンド数、繰り返す。
【００９２】
乱数削除手段７５は、最終ラウンド(第ｒラウンド)の出力データ：
βｒ||ｘｒＬ、
βｒ＋１||ｘｒＲ
からそれぞれ乱数βｒ、βｒ＋１を除去し（下位ｎビット：ｘｒＬ、ｘｒＲを抽出）、暗号文Ｃ＝ｘｒＬ||ｘｒＲを生成する。
【００９３】
図８は、本実施の形態の処理手順を表したものである。
【００９４】
乱数生成手段７０は、表に埋め込むための乱数を生成する（ステップＳ１）。
【００９５】
表生成手段７１は、乱数生成手段７０で生成された乱数を用いて表に乱数を埋め込む（ステップＳ２）。
【００９６】
乱数生成手段７０は、暗号化データ用の乱数を生成する（ステップＳ３）。
【００９７】
乱数連結手段７２は、平文を分割し、分割した各々に対して乱数を連結する（ステップＳ４）。
【００９８】
これより、暗号化手段７３によりラウンド処理が行われる。
【００９９】
なお、暗号化手段７３は、暗号アルゴリズム固有の処理であるため、説明は省略する。
【０１００】
暗号固有処理１は、例えば鍵データと暗号化データの排他的論理和演算等である（ステップＳ５）。
【０１０１】
表参照処理（ステップＳ７）の前に、ポインタ更新処理（ステップＳ６）を行う。これは、表参照を行う回数分実施する。
【０１０２】
暗号固有処理２（ステップＳ８）は、例えば、複数の表参照の結果どうしを混ぜ合わせる線形変換処理（具体的には、ＡＥＳのMixColumns処理）等である。
【０１０３】
暗号アルゴリズムで決定されるラウンド数（所定回数）、ラウンド処理が繰り返されていなければ、Ｓ５へ戻り、ラウンド処理を繰り返す。所定回数の繰り返しが行われていれば、Ｓ１０へ分岐する。
乱数削除手段７５は、データから乱数を取り除き、データを結合したものを暗号文とする（ステップＳ１０）。
【０１０４】
関連技術のマスキング手法では、表の再構成の演算コストが大きい。図３の対策済非線形処理３０を生成するためには、式（22）の演算を行う必要がある。なお、for文は、C言語の書法によるfor-loopであり、ｉ＝０からｉ＝２ｎ−１まで処理Ｓ’［ｉ］＝Ｓ［ｉ＾α１］＾α３を繰り返す。なお、＾はC言語における排他的論理和演算子、powは累乗関数であり、pow(2,n)は2nである。ｉ++は、ｉを1つ増加（increment）を意味する。
【０１０５】
ｆｏｒ（ｉ＝０；ｉ＜pow(2,n)；ｉ＋＋）  Ｓ’［ｉ］＝Ｓ［ｉ＾α１］＾α３        ・・・(22)
【０１０６】
この一連の処理では、
排他的論理和を２回、
Ｓ［］のロードを１回、
Ｓ’［］へのストアを１回実行する。
【０１０７】
一方、本実施形態による表生成処理（図７）では、
Ｓ’［］へのストアの１回で済む（乱数αをストア命令のサイズに一致させた場合）。
【０１０８】
表生成処理は、１ブロック分の暗号化処理毎に実施する必要があるため、処理コストが少ないほど耐タンパ機能がないものからの処理性能の低下が少ない、つまり高速な処理が行えるというメリットがある。
【０１０９】
また、関連技術では、α１が異なると、異なる表Ｓ’になってしまう。表Ｓが１種類であっても、複数回参照を行う暗号アルゴリズムであれば、その数分の表Ｓ’を持たねばならず、使用メモリ領域が増加するという問題もある。例えば、ＡＥＳのSubBytes処理では、１６回の表参照を行うため、最大１６倍の表を持つことになる。
【０１１０】
一方、実施形態の表Ｓ’は、連結する乱数の制限はないため、表Ｓ’の増加はない。このため、メモリコストの面でもメリットがある。
【０１１１】
なお、上記の特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１１２】
１  暗号化装置
２  入出力装置
３  ＣＰＵ
４  ＲＡＭ
５  ＲＯＭ
６  バス
７  暗号処理プログラム
１０  Ｆ関数
１１  非線形処理Ｓ
３０  乱数マスクをかけた非線形処理Ｓ
３１  排他的論理和
７０  乱数生成手段
７１  表生成手段
７２  乱数連結手段
７３  暗号化手段
７４  ポインタ更新手段
７５  乱数削除手段
３０１  非線形変換処理
【図１】
2014115579.tif 000006
【図２】
2014115579.tif 000007
【図３】
2014115579.tif 000008
【図４】
2014115579.tif 000009
【図５】
2014115579.tif 000010
【図６】
2014115579.tif 000011
【図７】
2014115579.tif 000012
【図８】
2014115579.tif 000013
【図９】
2014115579.tif 000014