(57)【要約】      （修正有）【課題】平文および暗号鍵をシンボルに変換した上でテーブル参照によって暗号化処理を行う場合にメモリ容量の増大を防ぐ。【解決手段】暗号化装置は、バイナリデータと所定のハミング重みのシンボルとの対応付けに従って平文および暗号鍵をシンボルに変換する手段１１００と、第１演算の入力シンボルが示すアドレスに第１演算の出力シンボルが格納された第１演算テーブル、および、第２演算の入力シンボルが示すアドレスに第２演算の出力シンボルが格納された第２演算テーブルを、一方の演算テーブルの未使用領域に他方の演算テーブルの使用領域を重ね合わせたテーブルとして保持する手段１４００と、シンボルで表された平分および暗号鍵ならびに重ね合わせたテーブルに基づいて第１演算および第２演算を行うことで、シンボルで表された暗号文を生成する手段１２００と、シンボルで表された暗号文をバイナリデータに変換する手段１３００と、を備える。【選択図】図２
2014116897.tif 000002
【特許請求の範囲】
【請求項１】
第１ビット幅のバイナリデータと所定のハミング重みの第２ビット幅のシンボルとの対応付けに従ってバイナリデータで表された平文および暗号鍵をシンボルで表された平文および暗号鍵に変換するシンボル変換手段と、
暗号化処理に含まれる第１演算の入力に相当するシンボルが示すアドレスに該第１演算の出力に相当するシンボルが格納された第１演算テーブル、および、該暗号化処理に含まれる第２演算の入力に相当するシンボルが示すアドレスに該第２演算の出力に相当するシンボルが格納された第２演算テーブルを、一方の演算テーブルの未使用領域に他方の演算テーブルの使用領域を重ね合わせたテーブルとして保持するテーブル保持手段と、
シンボルで表された平分および暗号鍵ならびに前記重ね合わせたテーブルに基づいて前記第１演算および前記第２演算を行うことで、シンボルで表された暗号文を生成するシンボル暗号化手段と、
シンボルで表された暗号文を前記対応付けに従ってバイナリデータで表された暗号文に変換する逆シンボル変換手段と、を備える、暗号化装置。
【請求項２】
前記重ね合わせたテーブルは、前記第１演算の入力に相当する複数のシンボルを連結したビット列が示すアドレスに前記第１演算の出力に相当するシンボルが格納され、前記第２演算の入力に相当する複数のシンボルを連結したビット列に所定のオフセットを加えたアドレスに前記第２演算の出力に相当するシンボルが格納されている、請求項１に記載の暗号化装置。
【請求項３】
前記シンボル変換手段は、第１ビット幅のバイナリデータと、所定の複数のハミング重みのいずれかを有する第２ビット幅のシンボルとの対応付けに従って、バイナリデータで表された平文および暗号鍵をシンボルで表された平文および暗号鍵に変換する、請求項１または２に記載の暗号化装置。
【請求項４】
前記第１演算および前記第２演算は、前記暗号化処理に含まれる排他的論理和、非線形変換、ガロア体上の乗算、および、算術加算の少なくともいずれかの演算である、請求項１ないし３のいずれか１項に記載の暗号化装置。
【請求項５】
前記暗号化処理は、ＡＥＳ（Advanced Encryption Standard）に基づく暗号化処理である、請求項１ないし４のいずれか１項に記載の暗号化装置。
【請求項６】
コンピュータが、第１ビット幅のバイナリデータと所定のハミング重みの第２ビット幅のシンボルとの対応付けに従ってバイナリデータで表された平文および暗号鍵をシンボルで表された平文および暗号鍵に変換する変換工程と、
暗号化処理に含まれる第１演算の入力に相当するシンボルが示すアドレスに該第１演算の出力に相当するシンボルが格納された第１演算テーブル、および、該暗号化処理に含まれる第２演算の入力に相当するシンボルが示すアドレスに該第２演算の出力に相当するシンボルが格納された第２演算テーブルを、一方の演算テーブルの未使用領域に他方の演算テーブルの使用領域を重ね合わせたテーブルとして記憶部に保持する保持工程と、
シンボルで表された平分および暗号鍵ならびに前記重ね合わせたテーブルに基づいて前記第１演算および前記第２演算を行うことで、シンボルで表された暗号文を生成する生成工程と、
シンボルで表された暗号文を前記対応付けに従ってバイナリデータで表された暗号文に変換する逆変換工程と、を含む、暗号化方法。
【請求項７】
前記重ね合わせたテーブルは、前記第１演算の入力に相当する複数のシンボルを連結したビット列が示すアドレスに前記第１演算の出力に相当するシンボルが格納され、前記第２演算の入力に相当する複数のシンボルを連結したビット列に所定のオフセットを加えたアドレスに前記第２演算の出力に相当するシンボルが格納されている、請求項６に記載の暗号化方法。
【請求項８】
前記変換工程において、第１ビット幅のバイナリデータと、所定の複数のハミング重みのいずれかを有する第２ビット幅のシンボルとの対応付けに従って、バイナリデータで表された平文および暗号鍵をシンボルで表された平文および暗号鍵に変換する、請求項６または７に記載の暗号化方法。
【請求項９】
第１ビット幅のバイナリデータと所定のハミング重みの第２ビット幅のシンボルとの対応付けに従ってバイナリデータで表された平文および暗号鍵をシンボルで表された平文および暗号鍵に変換する変換処理と、
暗号化処理に含まれる第１演算の入力に相当するシンボルが示すアドレスに該第１演算の出力に相当するシンボルが格納された第１演算テーブル、および、該暗号化処理に含まれる第２演算の入力に相当するシンボルが示すアドレスに該第２演算の出力に相当するシンボルが格納された第２演算テーブルを、一方の演算テーブルの未使用領域に他方の演算テーブルの使用領域を重ね合わせたテーブルとして記憶部に保持する保持処理と、
シンボルで表された平分および暗号鍵ならびに前記重ね合わせたテーブルに基づいて前記第１演算および前記第２演算を行うことで、シンボルで表された暗号文を生成する生成処理と、
シンボルで表された暗号文を前記対応付けに従ってバイナリデータで表された暗号文に変換する逆変換処理と、をコンピュータに実行させる、プログラム。
【請求項１０】
前記重ね合わせたテーブルは、前記第１演算の入力に相当する複数のシンボルを連結したビット列が示すアドレスに前記第１演算の出力に相当するシンボルが格納され、前記第２演算の入力に相当する複数のシンボルを連結したビット列に所定のオフセットを加えたアドレスに前記第２演算の出力に相当するシンボルが格納されている、請求項９に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化装置、暗号化方法およびプログラムに関し、特に、サイドチャネル攻撃を困難とする耐タンパー性を有する暗号化装置、暗号化方法およびプログラムに関する。
【背景技術】
【０００２】
情報の電子データ化が進む中で、情報の保護、秘匿な通信において、暗号は不可欠の技術となっている。暗号の安全性を保つためには、暗号鍵等の秘密情報が容易に推測できないようにする必要がある。暗号鍵の全数探索、数学的に解読を行う線形解読、差分解読等の暗号解析方法が知られているものの、現状では現実的な時間での解析は不可能である。
【０００３】
一方、携帯端末等の暗号機能を実装した装置（暗号モジュール）において、攻撃者が処理時間、消費電力、漏洩電磁波等のサイドチャネル情報を精密に測定できる場合には、サイドチャネル情報から秘匿情報の取得を試みるサイドチャネル攻撃への対策が必要となる。
【０００４】
サイドチャネル攻撃として、暗号モジュールの消費電力を測定し、消費電力から鍵等の秘密情報を解析する電力解析攻撃が知られている。電力解析攻撃の中でも、複数の消費電力波形に対して統計処理を施すことで解析を行う差分電力解析が特に強力な攻撃法とされている（非特許文献１）。
【０００５】
暗号モジュールにおいて、論理ゲートの遷移確率に偏りが生じる場合に、ビット列の中で１となるビットの個数（すなわち、ハミング重み）と消費電力との間に相関があることが指摘されている（非特許文献２）。また、予め規定された暗号化処理を所定回数実行して暗号文を生成する場合、暗号化処理前後でのレジスタのビット遷移（ハミング距離）と消費電力との間にも相関があることが指摘されている（非特許文献３）。
【０００６】
したがって、ハミング重みやハミング距離に着目することで、秘密鍵が解読されるおそれがある。
【０００７】
ハミング重みに着目した攻撃への対策手法として、一例として、ＤＲＬ（Dual Rail Logic）手法が提案されている（特許文献１）。ＤＲＬ手法では、オリジナルのデータを１ビット毎に分割し、１ビットの０、１のそれぞれを、所定のハミング重みを有する２ビットの０１、１０に変換し、ハミング重みが同数となる値を用いて暗号化処理および復号処理を行う。
【０００８】
以下では、所定のハミング重みを有する所定のビット幅のバイナリデータ（例えば、０１、１０）を「シンボル」といい、所定のビット幅のバイナリデータ（例えば、０、１）をシンボル（例えば、０１、１０）に変換することを「シンボル変換」という。
【０００９】
特許文献１に記載されたＤＲＬ手法によると、暗号化処理および復号処理に含まれる演算がシンボル変換後のシンボルで行われるため、データの相違による消費電力の差が生じない。したがって、ＤＲＬ手法によると、ハミング重みから秘密鍵を解析できなくなり、安全性が向上する。しかし、ＤＲＬ手法では、１ビット毎にシンボル変換し、シンボル単位で暗号化および復号の演算を行うため、データのビット幅分演算を繰り返す必要がある。すなわち、サイドチャネル攻撃の対策をＤＲＬ手法で行うと、暗号化処理および復号処理の処理時間が増大する。
【００１０】
なお、特許文献２には、１ビット毎にシンボル変換する代わりに、所定ビット毎にシンボル変換する技術が記載されている。特許文献２に記載された技術によると、平文を複数ビット毎にシンボル変換することにより演算回数の増加を防ぐことができ、特許文献１に記載された技術の問題点を解消することができる。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００５−２６０６５２号公報
【特許文献２】特開２０１０−１２４２７６号公報
【非特許文献】
【００１２】
【非特許文献１】P. Kocher, J. Jaffe and B. Jun, "Introduction to Differential Power Analysis and Related Attacks," [online], 1998, [平成24年11月22日検索], インターネット<URL:http://www.cryptography.com/public/pdf/DPATechInfo.pdf>.
【非特許文献２】佐々木明彦, 阿部公輝, "暗号回路への電力差分解析攻撃に対するアルゴリズムレベルでの耐性評価," 電気学会論文誌C(電子・情報・システム部門誌), Vol.126, No.10, pp.1221-1228, Oct. 2006.
【非特許文献３】E. Brier, C. Clavier, and F. Olivier, "Correlation Power Analysis with a Leakage Model," [online], 2004, [平成24年11月22日検索], インターネット<URL:http://www.iacr.org/archive/ches2004/31560016/31560016.pdf>.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
上記の特許文献および非特許文献の各開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。
【００１４】
特許文献２に記載された技術のようにハミング重みが一定なシンボルを多数用意することで平文および暗号鍵を複数ビット単位でシンボル変換を行う場合に、さらに、暗号化処理に含まれる演算をテーブル参照によって実現することが考えられる。
【００１５】
しかし、シンボルに変換された平文および暗号鍵に基づく暗号化処理をテーブル参照によって実現しようとすると、テーブル中に多数の未使用領域が生じ得る。なぜなら、シンボルは所定のハミング重みを有する所定ビット幅のバイナリデータであり、とびとびの不連続な値をとるため、シンボルをアドレスとしてテーブルを参照する場合、使用されるアドレス値もとびとびの不連続な値となるからである。特に、暗号化処理手順に複数の種類の演算が含まれる場合には、複数のテーブルをメモリに保持する必要があり、テーブルを保持するための記憶容量の増大が問題となる。
【００１６】
そこで、平文および暗号鍵をシンボルに変換した上でテーブル参照によって暗号化処理を行う場合に、テーブルを保持するための記憶容量の増大を防ぐことが望まれる。本発明の目的は、かかる要望に寄与する暗号化装置暗号化方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００１７】
本発明の第１の視点に係る暗号化装置は、
第１ビット幅のバイナリデータと所定のハミング重みの第２ビット幅のシンボルとの対応付けに従ってバイナリデータで表された平文および暗号鍵をシンボルで表された平文および暗号鍵に変換するシンボル変換手段と、
暗号化処理に含まれる第１演算の入力に相当するシンボルが示すアドレスに該第１演算の出力に相当するシンボルが格納された第１演算テーブル、および、該暗号化処理に含まれる第２演算の入力に相当するシンボルが示すアドレスに該第２演算の出力に相当するシンボルが格納された第２演算テーブルを、一方の演算テーブルの未使用領域に他方の演算テーブルの使用領域を重ね合わせたテーブルとして保持するテーブル保持手段と、
シンボルで表された平分および暗号鍵ならびに前記重ね合わせたテーブルに基づいて前記第１演算および前記第２演算を行うことで、シンボルで表された暗号文を生成するシンボル暗号化手段と、
シンボルで表された暗号文を前記対応付けに従ってバイナリデータで表された暗号文に変換する逆シンボル変換手段と、を備える。
【００１８】
本発明の第２の視点に係る暗号化方法は、
コンピュータが、第１ビット幅のバイナリデータと所定のハミング重みの第２ビット幅のシンボルとの対応付けに従ってバイナリデータで表された平文および暗号鍵をシンボルで表された平文および暗号鍵に変換する変換工程と、
暗号化処理に含まれる第１演算の入力に相当するシンボルが示すアドレスに該第１演算の出力に相当するシンボルが格納された第１演算テーブル、および、該暗号化処理に含まれる第２演算の入力に相当するシンボルが示すアドレスに該第２演算の出力に相当するシンボルが格納された第２演算テーブルを、一方の演算テーブルの未使用領域に他方の演算テーブルの使用領域を重ね合わせたテーブルとして記憶部に保持する保持工程と、
シンボルで表された平分および暗号鍵ならびに前記重ね合わせたテーブルに基づいて前記第１演算および前記第２演算を行うことで、シンボルで表された暗号文を生成する生成工程と、
シンボルで表された暗号文を前記対応付けに従ってバイナリデータで表された暗号文に変換する逆変換工程と、を含む。
【００１９】
本発明の第３の視点に係るプログラムは、
第１ビット幅のバイナリデータと所定のハミング重みの第２ビット幅のシンボルとの対応付けに従ってバイナリデータで表された平文および暗号鍵をシンボルで表された平文および暗号鍵に変換する変換処理と、
暗号化処理に含まれる第１演算の入力に相当するシンボルが示すアドレスに該第１演算の出力に相当するシンボルが格納された第１演算テーブル、および、該暗号化処理に含まれる第２演算の入力に相当するシンボルが示すアドレスに該第２演算の出力に相当するシンボルが格納された第２演算テーブルを、一方の演算テーブルの未使用領域に他方の演算テーブルの使用領域を重ね合わせたテーブルとして記憶部に保持する保持処理と、
シンボルで表された平分および暗号鍵ならびに前記重ね合わせたテーブルに基づいて前記第１演算および前記第２演算を行うことで、シンボルで表された暗号文を生成する生成処理と、
シンボルで表された暗号文を前記対応付けに従ってバイナリデータで表された暗号文に変換する逆変換処理と、をコンピュータに実行させる。
なお、プログラムは、非一時的なコンピュータ可読記録媒体（non-transitory computer-readable storage medium）に記録されたプログラム製品として提供することができる。
【発明の効果】
【００２０】
本発明に係る暗号化装置、暗号化方法およびプログラムによると、平文および暗号鍵をシンボルに変換した上でテーブル参照によって暗号化処理を行う場合に、テーブルの保持によるメモリ容量の増大を防ぐことが可能となる。
【図面の簡単な説明】
【００２１】
【図１】第１の実施形態に係る暗号化装置の構成を一例として示すブロック図である。
【図２】第１の実施形態に係る暗号化装置の暗号化部の構成を一例として示すブロック図である。
【図３】第１の実施形態に係る暗号化装置のシンボル変換部の構成を一例として示す図である。
【図４】第１の実施形態に係る暗号化装置における排他的論理和の入出力を表す図である。
【図５】第１の実施形態に係る暗号化装置における排他的論理和をシンボルによるテーブル実装したときの入出力を表す図である。
【図６】第１の実施形態に係る暗号化装置における非線形（２ｎビットＳｂｏｘ）変換の入出力を表す図である。
【図７】第１の実施形態に係る暗号化装置における非線形（２ｎビットＳｂｏｘ）変換をシンボルによるテーブル実装したときの入出力を表す図である。
【図８】第１の実施形態に係る暗号化装置における算術加算をシンボルによるテーブル実装したときの入出力を表す図である。
【図９】第１の実施形態に係る暗号化装置の逆シンボル変換部の構成を一例として示す図である。
【図１０】演算テーブルの重ね合わせについて説明するため図である。
【図１１】ＡＥＳ１２８のフロー図である。
【発明を実施するための形態】
【００２２】
はじめに、一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００２３】
図１および図２を参照すると、暗号化装置は、秘密鍵を用いて平文を暗号化して暗号文として出力する暗号化装置であって、平文およびラウンド鍵（以下、暗号鍵ともいう。）のシンボル変換を行うシンボル変換手段（１１００）と、シンボルを用いた暗号化を行うシンボル暗号化手段（１２００）と、暗号化処理に含まれる演算をテーブル参照に基づいて行うための演算テーブルを保持するテーブル保持手段（１４００）と、シンボルから暗号文への逆変換を行う逆シンボル変換手段（１３００）と、を備える。
【００２４】
シンボル変換手段（１１００）は、平文を所定のビット幅の複数のバイナリデータに分割し、各バイナリデータを所定のハミング重みを有する所定のビット幅のシンボルに変換する。シンボル暗号化手段（１２００）は、変換されたシンボルを用いて、テーブル保持部（１４００）が保持する演算テーブルによって暗号化の演算を行う。演算テーブルには、演算の入力に相当するシンボルが示すアドレス位置に、当該演算の出力に相当するシンボルが格納されている。また、複数の演算テーブルのそれぞれの未使用領域に対して、他の演算テーブルの使用領域を重ね合わせることによって、テーブル中の未使用領域を削減する。
【００２５】
かかる暗号化装置によると、暗号化処理における耐タンパー手法であるＤＲＬ（Dual Rail Logic）手法を複数ビット毎に行うことで、処理時間の増加を抑えつつ、演算のテーブル化によって増加する記憶領域（例えば、ＲＯＭ領域）をテーブルの重ね合わせによって削減することが可能となる。
【００２６】
シンボル変換手段（１１００）は、平文およびラウンド鍵を所定の複数のビット幅毎に分割し、シンボルに置換する。シンボルは平文と暗号文を分割したときのビット幅よりも大きい所定のビット幅を有し、かつ、所定の１または２以上のハミング重みを有する。平文と暗号文を分割したときのビット幅のバイナリデータが取り得る値の個数に応じてシンボルを用意し、バイナリデータとシンボルとの対応付けを行う。
【００２７】
シンボル暗号化手段（１２００）は、暗号化に含まれる演算を全てテーブル参照（テーブル引き）によって実現する。ここで、テーブルの入出に相当するシンボルおよび出力に相当するシンボルは、シンボル単体またはシンボルを連結したビット列のいずれかである。
【００２８】
逆シンボル変換手段（１３００）は、シンボルから成る暗号文をシンボルの幅毎に分割し、シンボルに対応するバイナリデータへ変換する。
【００２９】
かかる構成によると、消費電力の差を用いた解析を困難にすることができる。その理由は、演算に用いるバイナリデータを全て所定のハミング重みを有するシンボルに置換することにより、データの違いによる消費電力の差が発生しないからである。
【００３０】
また、かかる構成によると、平文を複数ビット毎にシンボル変換することにより、演算回数の増加を防ぐことができる。具体的には、１ビット毎にシンボル変換する場合と比較して、複数ビット毎にシンボル変換することにより、演算回数を削減することができる。その理由は、所定のハミング重みを有するシンボルを多数用意することで、多ビット単位でシンボル変換を行うことを可能としたからである。
【００３１】
また、シンボル暗号化手段（１２００）による暗号化の演算は、全て演算テーブルを参照することで行われる。演算テーブルの入出力は、シンボル単体またはシンボルを連結したものから構成されている。演算テーブルをアクセスする際のシンボルは不連続な値をとるため、演算テーブル中には多数の未使用領域が生じる。暗号化処理手順に複数の種類の演算が含まれる場合、演算テーブルも複数必要とされ、未使用領域の増大が問題となる。テーブル保持手段（１４００）は、各演算テーブルの始端をずらして重ね合わせることにより、一方の演算テーブルの未使用領域に他方の演算テーブルのデータを書き込む。
【００３２】
かかる構成を採用し、複数の演算テーブルを一つのテーブルに重ね合わせることにより、テーブルの未使用領域の増加を抑制することができる。
【００３３】
本発明によると、演算をテーブル実装することによってできるテーブル中の未使用領域の増加を抑制することができる。その理由は、未使用領域を多数含む複数の演算テーブルを１つに重ね合わせることによって、メモリの浪費を抑制することができるからである。
【００３４】
なお、本発明において、下記の形態が可能である。
［形態１］
前記第１の視点に係る暗号化装置のとおりである。
［形態２］
前記重ね合わせたテーブルは、前記第１演算の入力に相当する複数のシンボルを連結したビット列が示すアドレスに前記第１演算の出力に相当するシンボルが格納され、前記第２演算の入力に相当する複数のシンボルを連結したビット列に所定のオフセットを加えたアドレスに前記第２演算の出力に相当するシンボルが格納されていてもよい。
［形態３］
前記シンボル変換手段は、第１ビット幅のバイナリデータと、所定の複数のハミング重みのいずれかを有する第２ビット幅のシンボルとの対応付けに従って、バイナリデータで表された平文および暗号鍵をシンボルで表された平文および暗号鍵に変換してもよい。
［形態４］
前記第１演算および前記第２演算は、前記暗号化処理に含まれる排他的論理和、非線形変換、ガロア体上の乗算、および、算術加算の少なくともいずれかの演算であってもよい。
［形態５］
前記暗号化処理は、ＡＥＳ（Advanced Encryption Standard）に基づく暗号化処理であってもよい。
［形態６］
前記第２の視点に係る暗号化方法のとおりである。
［形態７］
前記暗号化方法において、前記重ね合わせたテーブルは、前記第１演算の入力に相当する複数のシンボルを連結したビット列が示すアドレスに前記第１演算の出力に相当するシンボルが格納され、前記第２演算の入力に相当する複数のシンボルを連結したビット列に所定のオフセットを加えたアドレスに前記第２演算の出力に相当するシンボルが格納されていてもよい。
［形態８］
前記変換工程において、第１ビット幅のバイナリデータと、所定の複数のハミング重みのいずれかを有する第２ビット幅のシンボルとの対応付けに従って、バイナリデータで表された平文および暗号鍵をシンボルで表された平文および暗号鍵に変換してもよい。
［形態９］
前記第３の視点に係るプログラムのとおりである。
［形態１０］
前記プログラムにおいて、前記重ね合わせたテーブルは、前記第１演算の入力に相当する複数のシンボルを連結したビット列が示すアドレスに前記第１演算の出力に相当するシンボルが格納され、前記第２演算の入力に相当する複数のシンボルを連結したビット列に所定のオフセットを加えたアドレスに前記第２演算の出力に相当するシンボルが格納されていてもよい。
［形態１１］
前記変換処理において、第１ビット幅のバイナリデータと、所定の複数のハミング重みのいずれかを有する第２ビット幅のシンボルとの対応付けに従って、バイナリデータで表された平文および暗号鍵をシンボルで表された平文および暗号鍵に変換してもよい。
［形態１２］
第１ビット幅のバイナリデータと所定のハミング重みの第２ビット幅のシンボルとの対応付けに従ってバイナリデータで表された暗号文および暗号鍵をシンボルで表された暗号文および暗号鍵に変換するシンボル変換手段と、
復号処理に含まれる第１演算の入力に相当するシンボルが示すアドレスに該第１演算の出力に相当するシンボルが格納された第１演算テーブル、および、該復号処理に含まれる第２演算の入力に相当するシンボルが示すアドレスに該第２演算の出力に相当するシンボルが格納された第２演算テーブルを、一方の演算テーブルの未使用領域に他方の演算テーブルの使用領域を重ね合わせたテーブルとして保持するテーブル保持手段と、
シンボルで表された暗号文および暗号鍵ならびに前記重ね合わせたテーブルに基づいて前記第１演算および前記第２演算を行うことで、シンボルで表された平文を生成するシンボル復号手段と、
シンボルで表された平文を前記対応付けに従ってバイナリデータで表された平文に変換する逆シンボル変換手段と、を備える、復号装置。
［形態１３］
コンピュータが、第１ビット幅のバイナリデータと所定のハミング重みの第２ビット幅のシンボルとの対応付けに従ってバイナリデータで表された暗号文および暗号鍵をシンボルで表された暗号文および暗号鍵に変換する変換工程と、
復号処理に含まれる第１演算の入力に相当するシンボルが示すアドレスに該第１演算の出力に相当するシンボルが格納された第１演算テーブル、および、該復号処理に含まれる第２演算の入力に相当するシンボルが示すアドレスに該第２演算の出力に相当するシンボルが格納された第２演算テーブルを、一方の演算テーブルの未使用領域に他方の演算テーブルの使用領域を重ね合わせたテーブルとして記憶部に保持する保持工程と、
シンボルで表された暗号文および暗号鍵ならびに前記重ね合わせたテーブルに基づいて前記第１演算および前記第２演算を行うことで、シンボルで表された平文を生成する生成工程と、
シンボルで表された平文を前記対応付けに従ってバイナリデータで表された平文に変換する逆変換工程と、を含む、復号方法。
［形態１４］
第１ビット幅のバイナリデータと所定のハミング重みの第２ビット幅のシンボルとの対応付けに従ってバイナリデータで表された暗号文および暗号鍵をシンボルで表された暗号文および暗号鍵に変換する変換処理と、
復号処理に含まれる第１演算の入力に相当するシンボルが示すアドレスに該第１演算の出力に相当するシンボルが格納された第１演算テーブル、および、該復号処理に含まれる第２演算の入力に相当するシンボルが示すアドレスに該第２演算の出力に相当するシンボルが格納された第２演算テーブルを、一方の演算テーブルの未使用領域に他方の演算テーブルの使用領域を重ね合わせたテーブルとして記憶部に保持する保持処理と、
シンボルで表された暗号文および暗号鍵ならびに前記重ね合わせたテーブルに基づいて前記第１演算および前記第２演算を行うことで、シンボルで表された平文を生成する生成処理と、
シンボルで表された平文を前記対応付けに従ってバイナリデータで表された平文に変換する逆変換処理と、をコンピュータに実行させる、プログラム。
【００３５】
（実施形態１）
第１の実施形態に係る暗号化装置について、図面を参照して説明する。
【００３６】
図１は、本実施形態に係る暗号化装置の構成を一例として示すブロック図である。図１を参照すると、暗号化装置は、暗号化部１０００および鍵生成部２０００を備える。なお、以下では、平文を暗号化して暗号文を生成する暗号化装置について説明するが、同様にして、暗号文を復号して平文を生成する復号装置を実現することができる。
【００３７】
鍵生成部２０００は、入力された秘密鍵をもとに、暗号化部１０００で使用するラウンド鍵Ｋｎを生成する。
【００３８】
暗号化部１０００は、入力された平文と鍵生成部２０００から受け取るラウンド鍵Ｋｎをもとに、データを暗号化し、暗号文を出力する。
【００３９】
図２は、暗号化部１０００の構成を一例として示すブロック図である。図２を参照すると、暗号化部１０００は、シンボル変換部１１００、シンボル暗号化部１２００、逆シンボル変換部１３００、および、テーブル保持部１４００を備える。
【００４０】
まず、シンボル変換部１１００は、平文をシンボルに変換する。
【００４１】
次に、シンボル暗号化部１２００は、暗号アルゴリズムに則して暗号化処理を行う。シンボル暗号化部１２００は、暗号化の演算方法として、テーブル保持部１４００が保持する演算テーブルをシンボルで参照し、演算結果をシンボルで受け取る。
【００４２】
シンボルでの暗号化が終了すると、逆シンボル変換部１３００は、シンボルから暗号文への変換を行う。
【００４３】
図３は、シンボル変換部１１００の構成を一例として示すブロック図である。図３を参照すると、シンボル変換部１１００は、ｎビットのバイナリデータとシンボルとの対応付けを示す変換テーブル１１０１を保持している。
【００４４】
シンボルとして、ｍビットから成るビット列であって所定の（一種または複数種の）ハミング重みを有するものを予め選んでおいて、ｎビットのバイナリデータに割り付ける。
【００４５】
シンボル変換部１１００は、入力された平文またはラウンド鍵をｎビット（１＜ｎ）毎に分割する。また、シンボル変換部１１００は、ｎビットに分割された入力値を、変換テーブル１１０１を参照してシンボルに変換する。
【００４６】
シンボルのビット幅ｍとして、ｎよりも大きく２ｎよりも小さい値を選択することが好ましい。また、シンボルのハミング重みの種類が少ないほうが、消費電力のばらつきは小さくなる。例えば、ハミング重みが１種類の場合、消費電力のばらつきはゼロとなる。消費電力のばらつきが小さくなるに従って、差分電力解析に基づく攻撃は困難となる。
【００４７】
シンボル暗号化部１２００は、シンボル変換部１１００で変換されたシンボルを入力とし暗号アルゴリズムに則して暗号化の演算を行う。シンボル暗号化部１２００は、暗号化処理に含まれる演算を、いずれも、テーブル保持部１４００に格納されたテーブルを参照することによって行う。テーブル保持部１４００は、当該暗号化アルゴリズムで必要な全ての演算の入出力をテーブル（演算テーブル）として保持している。
【００４８】
以下では、演算のテーブル化の例として、排他的論理和（ＸＯＲ）、非線形変換、ガロア体上の乗算、および、算術加算について説明する。
【００４９】
図４および図５を用いて、排他的論理和のテーブル実装例を示す。
【００５０】
図４は、排他的論理和の入出力を表した図である。シンボルのビット幅をｍビットとしたとき、排他的論理和はｍビット×ｘの入力１、入力２を入力とし、ｍビット×ｘの演算結果を出力する。図５は、排他的論理和をシンボルに基づくテーブルで実装した場合を示す。シンボル暗号化部１２００は、ｍビットの入力１と入力２とを連結したものを入力（添字、アドレス）とし、テーブル参照を行い、ｍビットの出力を得る。
【００５１】
シンボル暗号化部１２００は、これをｘ回繰り返して、出力を連結することで、ｍビット×ｘの出力を得る。
【００５２】
次に、図６および図７を用いて、シンボルのビット幅がｍビットであり、バイナリデータのビット幅をｎビットとしたとき、２ｎビットの非線形（Ｓｂｏｘ）変換のテーブル実装例を示す。
【００５３】
図６は、非線形（Ｓｂｏｘ）変換の入出力を表す。非線形変換は２ｎビットのデータを入力とし２ｎビットのデータを出力する。図７は、非線形変換をシンボルに基づくテーブルで実装した場合を示す。シンボル暗号化部１２００は、ｍビットのシンボル２つ分を連結したものを入力（添字）として２つのテーブル（上位ビットテーブル、下位ビットテーブル）を参照し、それぞれｍビットの出力を得る。シンボル暗号化部１２００は、これらの出力を連結して、２ｍビットの出力を得る。
【００５４】
ガロア体上の乗算の入出力の構造は、図６に示した非線形変換と同一である。暗号アルゴリズムに応じて２倍乗算、３倍乗算等の必要な乗算を用意する。なお、３倍乗算については、２倍乗算後に自身と排他的論理和をとる演算に置換することができる。
【００５５】
次に、図８を参照して、算術加算のテーブル実装について説明する。図８は、算術加算のテーブル実装１４３０を示す。シンボル暗号化部１２００は、算術加算を行う場合、入力をシンボルのビット幅（ｍビット）単位に分割し、下位側から処理する。シンボル暗号化部１２００は、ｍビットの入力１と入力２とを連結したものを入力（添字）とし、ｍビット内での算術加算用テーブルを参照し、ｍビットの出力を得る。また、シンボル暗号化部１２００は、ｍビットを越えた繰り上がり用テーブルを参照し、繰り上がりの有無を取得する。シンボル暗号化部１２００は、次のシンボル単位の算術加算を行う際、まず、前段の繰り上がり値と入力１とを算術加算し、この結果と入力２とを算術加算する。なお、ここでの２回の算術加算において、繰り上がりは最大でも１回しか発生しない。
【００５６】
また、算術加算を２回行う方法の他に、「入力１＋入力２＋１」のｍビット内での算術加算用テーブル、および、ｍビットを越えた繰り上がり用テーブルを用意しておいて、前段の繰り上がりの有無に応じて、参照するテーブルを切り替えるようにしてもよい。さらに、繰り上がりを表すシンボルとして、ｍビットのシンボルを用いる代わりに、０に対して０１、１に対して１０という２ビットのシンボルを用いてもよい。
【００５７】
図９は、逆シンボル変換部１３００の構成を一例として示すブロック図である。図９を参照すると、逆シンボル変換部１３００は、シンボル暗号化１２００の出力を受け取る。逆シンボル変換部１３００は、受け取ったデータをシンボルのビット幅（ｍビット）毎に分割し、シンボル変換部１１００の変換テーブル１１０１（図３）を逆引きして、シンボルからｎビットの暗号文に変換する。なお、シンボルから暗号文に変換するための逆引き用のテーブルを別途用意してもよい。
【００５８】
図１０は、複数の演算テーブルの重ね合わせについて説明するための図である。演算をテーブル実装したときの各演算テーブルは、いずれも同一のインタフェースを有する。すなわち、各演算テーブルは、シンボル２つ分のビット幅の入力と、シンボル１つ分の出力を有する。また、各演算テーブルはシンボルを添字（またはアドレス）としてアクセスされる。シンボルは所定の１または複数のハミング重みを有するため、不連続な値をとる。このとき、演算テーブルには、未使用領域が生じる。そこで、複数の演算テーブルの始点をオフセットすることによって、演算テーブルの未使用領域に他の演算テーブルのデータを代入する。なお、出力のビット幅がそろっていれば、テーブルの重ね合わせの対象となり得る。
【実施例】
【００５９】
第１の実施形態に係る暗号化装置の実施例を、暗号化処理として１２８ビットＡＥＳ（Advanced Encryption Standard）（ＡＥＳ１２８）を用いた場合について具体的に説明する。
【００６０】
本実施例では、４ビットのバイナリデータを、ハミング重みが３である６ビットのシンボルに割り当てるものとする。４ビットのバイナリデータが取り得る値は０から１５（０ｘＦ）の１６種である。一方、６ビットでハミング重みが３のシンボルは２０種である。これらの２０種のシンボルのうちの１６種に対して、バイナリデータ００００〜１１１１（すなわち、数値０から１５（０ｘＦ））を割り付ける。表１は、このときの変換テーブル１１０１を一例として示す。表１において、バイナリデータの欄が×のシンボルは未使用のシンボルである。
【００６１】
【表１】
2014116897.tif 000003
【００６２】
表１においては、シンボルが有するハミング重みを１つのみとしたが、シンボルが有するハミング重みの種類を複数としてもよい。例えば、ビット幅５のビット列のうちの、ハミング重みが２と３のものを選択してシンボルとしてもよい。表２は、このときの変換テーブル１１０１を一例として示す。表２において、バイナリデータの欄が×のシンボルは未使用のシンボルである。
【００６３】
【表２】
2014116897.tif 000004
【００６４】
シンボルが有するハミング重みの種類を増やすことで、ハミング重みに着目した攻撃への耐性は弱まるものの、シンボルを構成するビット数を削減することができ、暗号化処理をテーブル参照に基づいて実装する際のテーブルのサイズを小さくすることが可能となる。なお、以下では、表１に示した変換テーブル１１０１を用いる場合について説明する。
【００６５】
図２のシンボル変換部１１００は、読み込んだ平文を４ビット毎に分割し、シンボルに変換する。このとき、平文１２８ビット（＝３２×４ビット）は、１９２ビット（＝３２個のシンボル×６ビット）に変換される。
【００６６】
次に、シンボル暗号化部１２００は、シンボルで暗号化を行う。ＡｄｄＲｏｕｎｄＫｅｙ演算では、１２８ビットの平文と１２８のラウンド鍵の排他的論理和を行う。ここでは、シンボル（６ビット）毎に３２回のテーブル参照を行うことで、排他的論理和の演算結果を求める。
【００６７】
図５のテーブル実装１４１１の引数１が平文をシンボルに変換したものに相当し、引数２がラウンド鍵をシンボルに変換したものに相当する。シンボル暗号化部１２００は、これらの引数１と引数２とを連結し、連結した値で排他的論理和のテーブル（図５）を参照する。返却値は、シンボル変換する前の値を（４ビット分）排他的論理和したときの値に対応するシンボルである。シンボル暗号化部１２００は、このテーブル参照を３２回行い、結果を接続する。
【００６８】
ＳｕｂＢｙｔｅｓ演算では、中間文をシンボル２つ分ずつ処理する。図７のテーブル実装１４２１のＳ１、Ｓ２はオリジナルのＳｂｏｘ演算の値を上位４ビット、下位４ビットに分割しシンボルに変換したテーブルである。シンボル暗号化部１２００は、中間文のシンボル２つを用いてＳ１、Ｓ２のテーブルを参照し、返却値を連結する。
【００６９】
ＳｈｉｆｔＲｏｗｓ演算は、中間文のシンボル２つ分毎に区切っての並び替えである。一例として、ＳｕｂＢｙｔｅｓ演算等の演算結果を格納する際に並び替えが可能である。
【００７０】
ＭｉｘＣｏｌｕｍｎｓ演算は、ＳｕｂＢｙｔｅｓ演算と同様に中間文をシンボル２つ分ずつ処理する。シンボル暗号化部１２００は、ガロア体上の乗算テーブルを参照することでＭｉｘＣｏｌｕｍｎｓ演算を行う。
【００７１】
図１１に従って処理をラウンド数分繰り返すと、シンボルで構成された暗号文が得られる。
【００７２】
図９の逆シンボル変換１３００は、シンボルで構成された暗号文を、元のバイナリデータで構成された暗号文に変換する。
【００７３】
次に、暗号化処理における演算をテーブル実装したときのサイズについて説明する。
【００７４】
テーブルのインタフェースは全て共通で、２つのシンボル（６ビット×２）を連結した値を入力とし、１つのシンボル（６ビット）を返却する。
【００７５】
２つのシンボルを連結した値でアクセスするため、要素数は２＾１２（＝４０９６）必要となる。
【００７６】
１つのシンボルが取り得る値は１６通りであるため、２つのシンボルを連結したものが取り得る値は２５６（＝１６×１６）通りである。したがって、１つのテーブルで４０９６要素が必要となるものの、有効な値が設定されるのは２５６要素に過ぎない。
【００７７】
ＡＥＳでの排他的論理和（ＸＯＲ）演算、ＳｕｂＢｙｔｅｓ（Ｓｂｏｘ）演算、ＭｉｘＣｏｌｕｍｎｓ演算におけるガロア体上の２倍乗算をそれぞれテーブル実装する場合には、下記の５つの演算テーブル１〜５が必要となる。
【００７８】
演算テーブル１：ＸＯＲ演算
演算テーブル２：Ｓｂｏｘ演算（上位４ビット分用）
演算テーブル３：Ｓｂｏｘ演算（下位４ビット分用）
演算テーブル４：２倍乗算（上位４ビット分用）
演算テーブル５：２倍乗算（下位４ビット分用）
【００７９】
ここで、演算テーブル２〜５の始端を演算テーブル１の始端からそれぞれ１０，２０，６３６，６４６要素ずつ後方にずらして、演算テーブル１に重ね合わせることにより、未使用であった位置にそれぞれのデータを格納することができる。このとき、４７４２（＝４０９６＋６４６）要素中に１２８０（＝２５６×５）個のデータを格納することができる。
【００８０】
１つの要素に１つのシンボルを格納するため、１要素のサイズは１バイトとなる。したがって、５つの演算テーブルを保持するために４７４２バイトの記憶容量が必要となる。演算テーブルの重ね合わせを行わなかった場合には、２０４８０（＝４０９６×５）バイトの記憶容量が必要となることから、演算テーブルの重ね合わせにより、演算テーブルを保持するための記憶容量を１／４以下に削減することができる。
【００８１】
表３は、演算テーブルの重ね合わせを行わない場合と行った場合のそれぞれにおいて、演算テーブルを保持するのに必要とされる記憶容量を示す。表３を参照すると、複数の演算テーブルを重ね合わせることにより、演算テーブルを保持するための記憶領域を大幅に削減できることが分かる。
【００８２】
【表３】
2014116897.tif 000005
【００８３】
なお、演算テーブルの先頭から初めて有効な値が格納されている位置（４５６番目）までの要素と、最後に有効な値が格納された位置（後ろから４５６番目）から終端までの要素は、参照されない。したがって、これらの要素を削除することができる。これらの要素を削除することにより、演算テーブル単体では、記憶容量を３１８６（＝４０９６−４５５−４５５）バイトまで削減することができる。また、これらの要素を削除した場合、演算テーブルの重ね合わせを行わないときには、記憶容量は演算テーブル５つで１５９３０バイト必要となる。一方、演算テーブル５つを重ね合わせた場合には、記憶容量を３８３２（＝４７４２−４５５−４５５）バイトまで削減することができる（表４参照）。
【００８４】
【表４】
2014116897.tif 000006
【００８５】
なお、上記の特許文献等の先行技術文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【００８６】
１０００    暗号化部
１１００    シンボル変換部
１１０１    変換テーブル
１２００    シンボル暗号化部
１３００    逆シンボル変換部
１４００    テーブル保持部
１４１０    排他的論理和
１４１１    排他的論理和のテーブル実装
１４２０    非線形変換
１４２１    非線形変換のテーブル実装
１４３０    算術加算のテーブル実装
２０００    鍵生成部
３０００    演算テーブルの重ね合わせ
４０００    ＡＥＳ１２８フロー図
【図１】
2014116897.tif 000007
【図２】
2014116897.tif 000008
【図３】
2014116897.tif 000009
【図４】
2014116897.tif 000010
【図５】
2014116897.tif 000011
【図６】
2014116897.tif 000012
【図７】
2014116897.tif 000013
【図８】
2014116897.tif 000014
【図９】
2014116897.tif 000015
【図１０】
2014116897.tif 000016
【図１１】
2014116897.tif 000017