(57)【要約】  それぞれK1, K2, …, Knビットからなるn個の鍵を乱数によりランダム化するランダム化回路と、前記ランダム化されたn個の鍵から１つの鍵を生成することにより圧縮して得られる圧縮鍵を出力する圧縮化回路と、前記圧縮鍵を用いて入力データを暗号化する暗号化回路とを含むように構成する。
2012131926.tif 000002
【特許請求の範囲】
【請求項１】
それぞれK１, K２, …, Kｎビットからなるｎ個の鍵を乱数によりランダム化するランダム化回路と、
前記ランダム化されたｎ個の鍵から１つの鍵を生成することにより圧縮して得られる圧縮鍵を出力する圧縮化回路と、
前記圧縮鍵を用いて入力データを暗号化する暗号化回路と、
を含むことを特徴とする暗号処理装置。
【請求項２】
第一の乱数と第二の乱数を入力し合成し前記乱数として出力する乱数合成回路を更に含む、
ことを特徴とする請求項１に記載の暗号処理装置。
【請求項３】
それぞれK１, K２, …, Kｎビットからなるｎ個の鍵を乱数によりランダム化し、
前記ランダム化されたｎ個の鍵から１つの鍵を生成することにより、圧縮して得られる圧縮鍵を生成し、
前記圧縮鍵を用いて認証する、
ことを特徴とする認証方法。
【請求項４】
第一の乱数と第二の乱数を入力し合成し前記乱数として出力する、
ことを特徴とする請求項３に記載の暗号処理方法。
【請求項５】
親機に相当する第１のコンピュータと子機に相当する第２のコンピュータとで前記ｎ個の鍵として秘密鍵Kを共有し、
前記第１のコンピュータにて、乱数rを生成し、
前記第１のコンピュータから前記第２のコンピュータに前記乱数rを送信し、
前記第２のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１のコンピュータから受信した前記乱数rとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータから受信した前記乱数rを暗号化することで暗号化された乱数ａを生成して前記第１のコンピュータに送信し、
前記第１のコンピュータにて、前記ｎ個の秘密鍵Kと前記乱数rとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、
前記第１のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第２のコンピュータの認証を行う、
ことを特徴とする請求項３または４のいずれか記載の認証方法。
【請求項６】
親機に相当する第１のコンピュータと子機に相当する第２のコンピュータとで前記ｎ個の鍵としてｎ個の秘密鍵Kを共有し、
前記第１のコンピュータにて、第１の乱数rを生成し、
前記第１のコンピュータから前記第２のコンピュータに前記第１の乱数rを送信し、
前記第２のコンピュータにて、第２の乱数sを生成し、
前記第２のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１のコンピュータから受信した前記第１の乱数rとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータから受信した前記第１の乱数rを暗号化することで第１の暗号化された乱数ａを生成して前記第２の乱数sとともに前記第１のコンピュータに送信し、
前記第１のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１の乱数rとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、
前記第１のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第２のコンピュータの認証を行い、
前記第１のコンピュータにて、前記認証に成功した場合に、前記圧縮鍵Kcmpを用いて前記第２のコンピュータから受信した前記第２の乱数sを暗号化することで第２の暗号化された乱数ｂを生成して前記第２のコンピュータに送信し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータの認証を行う、
ことを特徴とする請求項３または４のいずれか記載の認証方法。
【請求項７】
前記ｎ個の秘密鍵Kをそれぞれ、前記第１の乱数rのビット値に応じて巡回シフトし、
前記ｎ個の巡回シフトの結果を、ビット値ごとに排他論理和演算して前記圧縮鍵Kcmpを生成する、
ことを特徴とする請求項５または６のいずれかに記載の認証方法。
【請求項８】
前記ｎ個の秘密鍵Kをそれぞれ、前記第１の乱数rとビット値ごとにビット結合し、
前記ｎ個のビット結合の結果を、ビット値ごとに排他論理和演算し、
前記排他論理和演算の結果に対して、ガロア体ＧＦ(２g)上の剰余演算を行って前記圧縮鍵Kcmpを生成する、
ことを特徴とする請求項５または６のいずれかに記載の認証方法。
【請求項９】
前記ｎ個の秘密鍵Kをそれぞれ、前記第１の乱数rのビット値に応じて巡回シフトレジスタ処理し、
前記ｎ個の巡回シフトレジスタ処理の結果を、ビット値ごとに排他論理和演算して前記圧縮鍵Kcmpを生成する、
ことを特徴とする請求項５または６のいずれかに記載の認証方法。
【請求項１０】
前記ｎ個の秘密鍵Kのそれぞれについて、前記第１の乱数rとガロア体ＧＦ(２g)上の乗算(ｇ＜ｈ)を実行し、
前記ｎ個の乗算の結果を、ビット値ごとに排他論理和演算し、
前記排他論理和演算の結果に対して、ガロア体ＧＦ(２g)上の剰余演算を行って前記圧縮鍵Kcmpを生成する、
ことを特徴とする請求項５または６のいずれかに記載の認証方法。
【請求項１１】
親機に相当する第１のコンピュータと子機に相当する第２のコンピュータとで前記ｎ個の鍵としてｎ個の秘密鍵Kを共有し、
前記第１のコンピュータにて、第１の乱数rを生成し、
前記第１のコンピュータから前記第２のコンピュータに前記第１の乱数rを送信し、
前記第２のコンピュータにて、第２の乱数sを生成し、
前記第２のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１のコンピュータから受信した前記第１の乱数rと前記第２の乱数sとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータから受信した前記第１の乱数rを暗号化することで暗号化された乱数ａを生成して前記第２の乱数sとともに前記第１のコンピュータに送信し、
前記第１のコンピュータにて、前記ｎ個の秘密鍵Kと前記乱数rと前記第２のコンピュータから受信した乱数sとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、
前記第１のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第２のコンピュータの認証を行う、
ことを特徴とする請求項３または４のいずれか記載の認証方法。
【請求項１２】
親機に相当する第１のコンピュータと子機に相当する第２のコンピュータとで前記ｎ個の鍵としてｎ個の秘密鍵Kを共有し、
前記第１のコンピュータにて、第１の乱数rを生成し、
前記第１のコンピュータから前記第２のコンピュータに前記第１の乱数rを送信し、
前記第２のコンピュータにて、第２の乱数sを生成し、
前記第２のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１のコンピュータから受信した前記第１の乱数rと前記第２の乱数sとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータから受信した前記第１の乱数rを暗号化することで第１の暗号化された乱数ａを生成して前記第２の乱数sとともに前記第１のコンピュータに送信し、
前記第１のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１の乱数rと前記第２のコンピュータから受信した前記第２の乱数sとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、
前記第１のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第２のコンピュータの認証を行い、
前記第１のコンピュータにて、前記認証に成功した場合に、前記圧縮鍵Kcmpを用いて前記第２のコンピュータから受信した前記第２の乱数sを暗号化することで第２の暗号化された乱数ｂを生成して前記第２のコンピュータに送信し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータの認証を行う、
ことを特徴とする請求項３または４のいずれか記載の認証方法。
【請求項１３】
前記第１の乱数rと前記第２の乱数sをビット値ごとに排他論理和演算して合成された乱数を生成し、
前記ｎ個の秘密鍵Kをそれぞれ、前記合成された乱数のビット値に応じて巡回シフトし、
前記ｎ個の巡回シフトの結果を、ビット値ごとに排他論理和演算して前記圧縮鍵Kcmpを生成する、
ことを特徴とする請求項１１または１２のいずれかに記載の認証方法。
【請求項１４】
前記第１の乱数rと前記第２の乱数sをビット値ごとに排他論理和演算して合成された乱数を生成し、
前記ｎ個の秘密鍵Kをそれぞれ、前記合成された乱数とビット値ごとにビット結合し、
前記ｎ個のビット結合の結果を、ビット値ごとに排他論理和演算し、
前記排他論理和演算の結果に対して、ガロア体ＧＦ(２ｇ)上の剰余演算を行って前記圧縮鍵Kcmpを生成する、
ことを特徴とする請求項１１または１２のいずれかに記載の認証方法。
【請求項１５】
前記第１の乱数rと前記第２の乱数sをビット値ごとに排他論理和演算して合成された乱数を生成し、
前記ｎ個の秘密鍵Kをそれぞれ、前記合成された乱数のビット値に応じて巡回シフトレジスタ処理し、
前記ｎ個の巡回シフトレジスタ処理の結果を、ビット値ごとに排他論理和演算して前記圧縮鍵Kcmpを生成する、
ことを特徴とする請求項１１または１２のいずれかに記載の認証方法。
【請求項１６】
前記第１の乱数rと前記第２の乱数sをビット値ごとに排他論理和演算して合成された乱数を生成し、
前記ｎ個の秘密鍵Kのそれぞれについて、前記合成された乱数とガロア体ＧＦ(２g)上の乗算(ｇ＜ｈ)を実行し、
前記ｎ個の乗算の結果を、ビット値ごとに排他論理和演算し、
前記排他論理和演算の結果に対して、ガロア体ＧＦ(２g)上の剰余演算を行って前記圧縮鍵Kcmpを生成する、
ことを特徴とする請求項１１または１２のいずれかに記載の認証方法。
【請求項１７】
コンピュータに、
複数個の鍵のそれぞれを乱数によりランダム化し、
前記ランダム化された複数個の鍵を圧縮して得られる圧縮鍵を暗号処理のための鍵として出力する、
処理を実行させるためのプログラム。
【請求項１８】
コンピュータに、
第一の乱数と第二の乱数を入力し合成し前記乱数として出力する、
処理を実行させるための請求項１７に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理を実行する暗号処理装置、暗号処理に基づく認証処理を実行する認証方法およびプログラムに関する。
【背景技術】
【０００２】
認証機能を搭載した小型認証チップでは、暗号処理を用いた認証プロトコルにより、機器の正当性を確認する。認証チップの正当性は、チップ内部に格納されている暗号鍵によって証明されるため、この鍵が外部に漏洩するとチップを偽造できる。【０００３】
チップ偽造防止のためには、暗号鍵の漏洩防止が必須である。一般的な機器認証において、暗号鍵はチップ内部に格納され外部に読み出されることがないため安全であるが、サイドチャネル攻撃を用いることで、消費電力の測定データから、内部に格納された状態の暗号鍵を解読される危険性がある。サイドチャネル攻撃への対策は、認証機器における重要な課題である。【０００４】
従来のサイドチャネル攻撃対策は、専用の暗号化回路を用いることで対策が行われていた。専用の暗号化回路は、内部データのランダム化を行うことで消費電力をランダム化するため安全であるが、専用のランダム化つき暗号回路を導入することで回路規模が大きくなるという問題があった。暗号化回路は、チップ全体の3〜4割を占める大きな回路であるが、従来のランダム化つき暗号回路の場合、回路規模がさらに２倍となり、チップのコスト増に直結するという問題点を有していた。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００４−４８４７９号公報
【特許文献２】特開２００５−１６５６７１号公報
【非特許文献】
【０００６】
【非特許文献１】Paul C. Kocher ”Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems”, Advances in cryptology-CRYPTO 1996, Springer-Verlag, pp. 104-113
【非特許文献２】Thomas S.Messerges, Ezzy A.Dabbish and Robert H.Sloan ”Power Analysis Attacks of Modular Exponentitiation in Smartcards”, Cryptographic Hardware and Embedded Systems(CHES’99), Springer-Verlag, pp.144-157
【非特許文献３】Paul Kocher, Joshua Jaffe, and Benjamin Jun, “Differential Power Analysis,” in proceedings of Advances in Cryptology-CRYPTO’99, Springer-Verlag, 1999, pp. 388-397
【非特許文献４】S. Chari, C. Jutla, J.R. Rao, P. Rohatgi, “An Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards,”Second Advanced Encryption Standard Candidate Conference, March 1999
【非特許文献５】T. S. Messerge, Ezzy A. Dabbish and Robert H.Sloan ,“Investigations of Power Attacks on Smartcards”. Proceedings of USENIX Workshop on Smartcard Technology, Mar 1999.
【非特許文献６】Takeshi Shimoyama, Hitoshi Yanami, Kazuhiro Yokoyama, Masahiko Takenaka, Kouichi Itoh, Jun Yajima, Naoya Torii, Hidema Tanaka "The Block Cipher SC2000", Fast Software Encryption (FSE 2001), pp.312-327, LNCS vol.2355
【非特許文献７】M.Akkar, RBevan, P.Dischamp, and D. Moyart, "Power Analysis, What Is Now Possible... ", Asiacrypt 2000
【非特許文献８】Thomas S. Messerges, “Securing the AES Finalists Against Power Analysis Attacks,” in proceedings of Fast Software Encryption Workshop 2000, Springer-Verlag, April 2000.
【発明の開示】
【０００７】
そこで、本発明の1つの側面では、回路規模または処理量を増大させずに、サイドチャネル攻撃への耐性を有するランダム化つき暗号処理および認証処理を実現することを目的とする。
【０００８】
態様の一例では、それぞれK1, K2, …, Knビットからなるn個の鍵を乱数によりランダム化するランダム化回路と、前記ランダム化されたn個の鍵から１つの鍵を生成することにより圧縮して得られる圧縮鍵を出力する圧縮化回路と、前記圧縮鍵を用いて入力データを暗号化する暗号化回路とを含むように構成する。
【０００９】
以上の構成により、回路を２倍化することなく、小さい回路規模増または処理量増ながらも、サイドチャネル攻撃に安全な認証を実現することが可能となる。
【図面の簡単な説明】
【００１０】
【図１】チャレンジアンドレスポンス認証プロトコルの概要を示す図、
【図２】共通鍵暗号を用いた一般的なチャレンジアンドレスポンス認証(片側認証、暗号化・復号)の原理図である。
【図３】共通鍵暗号を用いた一般的に考えられるチャレンジアンドレスポンス認証(片側認証、暗号化のみ)の機能ブロック図である。
【図４】共通鍵暗号を用いた一般的に考えられるチャレンジアンドレスポンス認証(両側認証、暗号化・復号)の機能ブロック図である。
【図５】共通鍵暗号を用いた一般的に考えられるチャレンジアンドレスポンス認証(両側認証、暗号化のみ)の機能ブロック図である。
【図６】共通鍵暗号の一般的な処理(鍵XOR処理とテーブル変換の組み合わせ)のアルゴリズムを示す図である。
【図７】図６の処理についてwjの入出力に関係するビットを取り出した図である。
【図８】電力消費曲線の例を示す図である。
【図９Ａ】電力差分曲線(スパイクあり)の例を示す図である。
【図９Ｂ】電力差分曲線(スパイクなし)の例を示す図である。
【図１０】共通鍵暗号の一般的な処理(鍵XOR処理とテーブル変換と線形変換の組み合わせ)のアルゴリズムを示す図である。
【図１１】DPAによる秘密鍵推定が可能な条件の説明図である。
【図１２】DPA対策なしAES回路の機能ブロック図である。
【図１３】図11のDPA対策なしAES回路に対し、一般的に考えられる手法１のDPA対策を適用した回路の機能ブロック図である。
【図１４】単純な鍵のランダム化による認証プロトコルの例１(片側認証、暗号化・復号)の機能ブロック図である。
【図１５】単純な鍵のランダム化による認証プロトコルの例２(片側認証、暗号化・復号)の機能ブロック図である。
【図１６】サイドチャネル攻撃の成功要因(AESの構造)の説明図である。
【図１７】サイドチャネル攻撃の成功要因(乱数マスクなし、ありとの比較)の説明図である。
【図１８】各実施形態に適用される手法1の説明図である。
【図１９】各実施形態に適用される手法2の説明図である。
【図２０】第1の実施形態 (手法1＋片側認証、暗号化・復号)の機能ブロック図である。
【図２１】第2の実施形態 (手法1＋片側認証、暗号化のみ)の機能ブロック図である。
【図２２】第3の実施形態 (手法1＋両側認証、暗号化・復号)の機能ブロック図である。
【図２３】第4の実施形態 (手法1＋両側認証、暗号化のみ)の機能ブロック図である。
【図２４】第5の実施形態 (手法2＋片側認証、暗号化・復号)の機能ブロック図である。
【図２５】第6の実施形態 (手法2＋片側認証、暗号化のみ)の機能ブロック図である。
【図２６】第7の実施形態 (手法2＋両側認証、暗号化・復号)の機能ブロック図である。
【図２７】第8の実施形態 (手法2＋両側認証、暗号化のみ)の機能ブロック図である。
【図２８】手法1の鍵圧縮(Compress関数)回路の基本構造図である。
【図２９】手法2の鍵圧縮(Compress_2関数)回路の基本構造図である。
【図３０】鍵圧縮回路の第1の実施例(手法1その1)を示す図である。
【図３１】鍵圧縮回路の実施例の回路規模見積もり基準を示す図である。
【図３２】NANDゲートの回路規模見積(1ゲート)を示す図である。
【図３３】NORゲートの回路規模見積(1ゲート)を示す図である。
【図３４】NOTゲートの回路規模見積(0.5ゲート)を示す図である。
【図３５】レジスタの回路規模見積(11ゲート)を示す図である。
【図３６】XOR(排他論理和回路)の回路規模見積(3.5ゲート)を示す図である。
【図３７】セレクタの回路規模見積(3.5ゲート)を示す図である。
【図３８】加減算器の回路規模見積(15ゲート)を示す図である。
【図３９】シフトレジスタ／巡回シフトレジスタの回路規模見積(14.5ゲート)を示す図である。
【図４０】LSFR／剰余演算回路の回路規模見積(最大18ゲート)を示す図である。
【図４１】鍵圧縮回路の第1の実施例(手法1その1)の回路規模の見積表を示す図である。
【図４２】鍵圧縮回路の第2の実施例(手法1その2)を示す図である。
【図４３】鍵圧縮回路の第2の実施例(手法1その2)の回路規模の見積表を示す図である。
【図４４】鍵圧縮回路の第3の実施例(手法1その3)を示す図である。
【図４５】鍵圧縮回路の第3の実施例(手法1その3)の回路規模の見積表を示す図である。
【図４６】鍵圧縮回路の第4の実施例(手法1その4)を示す図である。
【図４７】鍵圧縮回路の第4の実施例(手法1その4)の回路規模の見積表を示す図である。
【図４８】鍵圧縮回路の第5の実施例(手法2その1)を示す図である。
【図４９】鍵圧縮回路の第5の実施例(手法2その1)の回路規模の見積表を示す図である。
【図５０】鍵圧縮回路の第6の実施例(手法2その2)を示す図である。
【図５１】鍵圧縮回路の第6の実施例(手法2その2)の回路規模の見積表を示す図である。
【図５２】鍵圧縮回路の第7の実施例(手法2その3)を示す図である。
【図５３】鍵圧縮回路の第7の実施例(手法2その3)の回路規模の見積表を示す図である。
【図５４】鍵圧縮回路の第8の実施例(手法2その4)を示す図である。
【図５５】鍵圧縮回路の第8の実施例(手法2その4)の回路規模の見積表を示す図である。
【図５６】本実施形態のシステムを実現可能なハードウェアシステムの構成図である。
【発明を実施するための形態】
【００１１】
以下、本発明を実施するための形態について図面を参照しながら詳細に説明する。
暗号方式は、公開鍵暗号方式と共通鍵暗号方式に大別される。公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵(公開鍵)を一般に公開する代わりに、暗号文を復号するための鍵(秘密鍵)を受信者のみの秘密情報とすることで安全性を保つ方式である。これに対し、共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵(秘密鍵)を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。いずれの暗号方式を用いた場合でも、秘密鍵が外部に漏洩しないことがセキュリティ上の大きな前提となる。
【００１２】
セキュリティ機能を備えた組み込み機器に求められる性質として、耐タンパ性(Tamper-proof)と呼ばれるものがある。耐タンパとは、覗き見防止の意味であり、組み込み機器の外部から観察された情報により、組み込み機器内部に格納された重要情報が漏洩しない性質を指す。暗号を用いた認証機器の場合、外部から観察された情報により秘密鍵が漏洩しない性質である。一般的な認証機器は、機器製造時に秘密鍵が内部に書き込まれ、製造後は鍵が外部に取り出されることは無いため、高い耐タンパ性を有すると考えられていた。しかし、1996年に発見されたサイドチャネル攻撃により、認証機器を含めた組み込み装置全般に対して、製造後は鍵を外部に取り出さない場合でも、秘密鍵が漏洩することが判明したため、サイドチャネル攻撃への対策が耐タンパ上の必須課題となった。
【００１３】
サイドチャネル攻撃とは、組み込み機器に対する物理破壊を伴わずに、外部から観察可能な情報を用いて秘密鍵を解読する攻撃である。1996年には、処理時間を観察するタイミング攻撃(非特許文献１)が提案されたが、対策も容易であったため大きな脅威とならなかった。しかし1998年に、消費電力を観察する電力解析攻撃(Power Analysis, 以下PA)と呼ばれる手法が提案され、大きな脅威として現在でも注目されている。PAとは、1998年にPaul Kocherによって考案された手法で、組み込み機器に様々な入力データを与えた時の電力消費データを収集・解析することで、内部の鍵情報を推定する手法である。特に、組み込み機器がスマートカードチップや認証チップなどの単体のLSIチップである場合、消費電力の測定が容易であるため、PA対策は耐タンパ上の大きな課題である。PAを用いることで、公開鍵暗号、秘密鍵暗号共に暗号プロセッサから秘密鍵を推定できることが知られている。
【００１４】
PAには、単純電力解析(Single Power Analysis, 以下SPA), 電力差分攻撃(Differential Power Analysis, 以下DPA)の2種類が存在する。SPAは暗号プロセッサにおける単一の電力消費データの特徴から秘密鍵の推定を行う方式、DPAは多数の電力消費データの差分を解析することで秘密鍵の推定を行う方式である。共通鍵に限定した場合、SPAは対策が容易であるためほとんど有効ではないが、DPAが有効な攻撃法として知られている。SPA、DPAを用いた解読技術としては代表的なものとして次のような論文が発表されている。RSAなどの公開鍵暗号に対するDPAを用いた解読法については、非特許文献２などの文献にて述べられている。また、共通鍵暗号方式において、旧来の標準として利用されているDES(Data Encryption Standards)に対するDPAを用いた解読法については、非特許文献３で述べられている。DESの他に、現在標準的に利用されているAESについては、非特許文献４などの文献でDPAを用いた解読の可能性が指摘されている。
【００１５】
PAを用いた解読技術は特に有効な方法として注目されており、様々な解読法が研究されている。また、解読技術のみならずPAによる解読を防ぐための対策技術も発展しており、解読技術と同様に重要な技術として注目されている。ただし、これらの対策技術を用いた場合、暗号処理を行う回路の回路規模が大きくなるという欠点も知られており、共通鍵暗号に対する専用の対策回路は、未対策の回路の２倍の回路規模が必要という問題がある。認証チップやスマートカードの小型チップにおいては、暗号回路の占める回路規模の割合は非常に大きいため、専用の対策回路を組み込むことはコスト増に直結する。
【００１６】
本実施形態は、専用の対策回路を用いる代わりに、暗号を利用する上位レイヤの認証プロトコルの改良を行うことで、専用の対策回路によるコスト増を招くことなく、未対策の回路と同程度の回路規模による対策つき認証チップを実現することができる。
【００１７】
＜チャレンジアンドレスポンス認証プロトコル＞
認証チップにおいては、機器の正当性を確認するために、チャレンジアンドレスポンス認証プロトコルと呼ばれる通信プロトコルが利用される。チャレンジアンドレスポンス認証プロトコルの概要を図１に示す。チャレンジアンドレスポンス認証とは、デジタル情報を用いた合言葉であり、認証を行う側(親機１０１)から認証される側(子機１０２)に対し、「チャンレジ」と呼ばれる乱数を送信する。これに対し、子機１０２側では「チャンレンジ」に対して「レスポンス」と呼ばれる応答を生成し、親機１０１に返信する。親機１０１は、「チャレンジ」に対する「レスポンス」の値を判断し、もし正しいならば、子機１０２が正当な機器であると判断する。
【００１８】
「チャレンジ」として乱数を用いることで、対応する「レスポンス」が毎回変化する。これにより、再送攻撃(Replay attack)に対する防御が行える。再送攻撃とは、過去に外部から観察された応答を繰り返すことで、正当な機器の成りすましを行う攻撃である。つまり、乱数を用いない場合、チャンレジとレスポンスのペアが完全に固定値になる。このため、攻撃者がこのペアを観察することで、チャレンジに対応する適切なレスポンスを知ることができ、このレスポンスを返すチップを製造することでチップ偽造が容易となるからである。例えるならば、「山」に対する「川」という合言葉しか用いないシステムであることを、悪意のある第三者が知ることができれば、常に「川」と応答することで成りすましが可能となる。
【００１９】
「チャレンジ」に対する「レスポンス」の生成は、暗号関数を用いた方法が一般的である。どの暗号関数を用いるかによってメリットとデメリットがあるが、認証チップの場合、回路規模の小ささを優先できるメリットがある共通鍵暗号を用いる方法が広く用いられている。図２は、共通鍵暗号を用いた一般的に考えられるチャレンジアンドレスポンス認証(片側認証、暗号化・復号)の機能ブロックである。図２に示す認証方式(プロトコル)は、親機１０１と子機１０２の認証チップ間で、秘密鍵Kを事前共有している。これは、チップの製造時にKの値を書き込むことで実現できる。この値が外部に漏洩しないことがセキュリティ上の重要な前提である。認証を行なう側の親機１０１は、乱数rを生成し、認証される側の子機１０２に送信する(図２のＳ２０１)。子機１０２は、乱数rに対し、秘密鍵Kによる暗号処理a=Enc(r, K)を実行し、応答aを生成し、親機１０１に返信する(図２のＳ２０２)。ただし、C=Enc(P,K)とは、共通鍵暗号を用いて、平文Pを鍵Kにより暗号化した結果が暗号文Cであることを表す。応答aを受け取った親機１０１は、秘密鍵Kによる復号処理r’=Dec(a,K)を実行し、復号結果r’を得る(図２のＳ２０３)。復号結果r'がrと一致するならば、親機１０１は子機１０２を正当な機器と認定する。乱数rに対応した正当なレスポンスaを生成できるのは、秘密鍵Kを有する場合に限られるので、親機１０１は子機１０２の正当性を確認することができる。図２は暗号化と復号の両方を利用した親機１０１のみによる片側認証であるが、暗号化のみによるチャンレジアンドレスポンス認証も可能であり、その方法は図３に示される。
【００２０】
図３は、共通鍵暗号を用いた一般的に考えられるチャレンジアンドレスポンス認証(片側認証、暗号化のみ)の機能ブロック図である。図３では、親機１０１と子機１０２の認証チップ間で、秘密鍵Kを事前共有しており、認証を行なう側の親機１０１は、乱数rを生成し、認証される側の子機１０２に送信する(図３のＳ３０１)。子機１０２は、乱数rに対し、秘密鍵Kによる暗号処理a=Enc(r, K)を実行し、応答aを生成し、親機１０１に返信する(図３のＳ３０２)。ここまでは図２と同じであるが、親機１０１が子機１０２の正当性を確認するために、応答aを復号する代わりに乱数rを暗号化しa’=Enc(r, K)、その処理結果a’が子機１０２からの応答aと一致するか判定する。そして、一致するならば子機１０２が正当であると判断する(図３のステップＳ３０３)。
【００２１】
図２、図３は、片側認証と呼ばれる、親機１０１が子機１０２の正当性を確認するための認証プロトコルである。これでは、子機１０２は親機１０１の正当性を確認することができないため、子機１０２は親機１０１の不正を防止できない。これを防ぐために、子機１０２も親機１０１の正当性を確認する手段が必要である。これを実現するのが両側認証と呼ばれる認証プロトコルであり、子機１０２が親機１０１にチャレンジを送信し、親機１０１からのレスポンスを確認する処理が行われる。
【００２２】
図２の認証プロトコルを両側認証に拡張した認証プロトコルを図４に示す。すなわち、図４は、共通鍵暗号を用いた一般的に考えられるチャレンジアンドレスポンス認証(両側認証、暗号化・復号)の機能ブロック図である。図２と同様、親機１０１が乱数rを子機１０２に送信し(図４のＳ４０１)、子機１０２がrを秘密鍵Kで暗号化した結果aを計算する(図４のＳ４０３)。図２との違いは、このとき子機１０２側でも乱数sを生成することである(図４のＳ４０２)。次にa,sが親機１０１に送信され、親機１０１はaを秘密鍵Kで復号し、rと一致するなら子機１０２が正当であると判断し、さらに秘密鍵Kを用いてsを暗号化した結果bを生成する(図４のＳ４０４)。このbが子機１０２に送られた後、子機１０２は親機１０１からの応答bを秘密鍵Kにより復号し、その結果がsと一致するならば親機１０１が正当であると判断する(図４のＳ４０５)。
【００２３】
図４は暗号化・復号を用いた両側認証であるが、暗号化のみの認証も可能であり、その機能ブロック図は図５に示される。親機１０１が乱数rを子機１０２に送信し(図５のＳ５０１)、子機１０２がrを秘密鍵Kで暗号化した結果aを計算しつつ、乱数sを生成し(図５のＳ５０２)、a,sを親機１０１に送信する(図５のＳ５０３)。親機１０１はrを秘密鍵Kで暗号化した結果a’が子機１０２からの応答aと一致するならば、子機１０２が正当であると判断した上で、子機１０２からの乱数sを秘密鍵Kにより暗号化した結果bを生成し、子機１０２に送信する(図５のＳ５０４)。子機１０２は、乱数sを秘密鍵Kにより暗号化した結果b’を生成し、bに一致するならば親機１０１が正当であると判断する(図５のＳ５０５)。
【００２４】
＜共通鍵暗号回路に対するDPAによる秘密鍵解読手法＞
図６は、共通鍵暗号の一般的な処理(鍵XOR処理とテーブル変換の組み合わせ)のアルゴリズムを示す図である。Mは平文(もしくは暗号文)などの入力データ、Kは拡大鍵である。図６に示すKは、拡大鍵と呼ばれる値であり、秘密鍵をもとに、特定の処理を行うことでビット長を拡大することで生成される値である。MとKの排他的論理和(XOR)した結果を、特定のビット長データごとに分割し、それぞれの分割されたデータに対し、Sboxと呼ばれる変換テーブル演算を行う。M,Kは共通鍵暗号によって異なり、例えばDESの場合48-bit(ビット), AESの場合128-bitである。Sboxのビット長は暗号に依存するが、例えばDESの場合6-bit入力4-bit出力、AESの場合8-bit入力8-bit出力である。a-bit入力b-bit出力のSboxの回路規模は、a×b×2aに比例して大きくなるため、Sbox入出力のビット長には上限があり、8-bit入出力Sboxが最も大きいものとして知られている。
【００２５】
図６の構成においてwj の入出力に関係するビットのみを取り出した構成を図７に示す。図７において、mjは平文などの既知の値、kjは未知の値、wjは既知のSboxテーブルであると仮定する。この仮定の下で、DPAにより拡大鍵Kの部分鍵kjを推定できることを示す。
【００２６】
DPAは電力消費データの測定と、電力差分データを用いた鍵の解析という２段階から構成される。電力消費データの測定において、ある平文を与えたときに暗号プロセッサが消費する電力消費データは、オシロスコープ等を用いれば、図８に示すような電力消費曲線として測定される。平文の値を様々に変えながらこのような測定を繰り返し、十分な回数の測定データが得られた時点で測定を終了する。この一連の測定で得られた電力消費曲線の集合をGとする。
【００２７】
次に電力消費曲線を用いた拡大鍵の解析について説明を行う。暗号処理内部で用いられている拡大鍵の部分鍵kjについて、kj =k’jであるという仮定を立てる。mj, wjが既知のため、このk’jの仮定に基づき、集合Gは以下のG0(k’j), G1(k’j)に示す2種類の集合に分類できる。
【数１】
2012131926.tif 000003
【００２８】
そして、以下に示す電力差分曲線DG(k’j)を作成する。
DG(k’i) = (集合G1に属する電力消費曲線の平均) - (集合G0に属する電力消費曲線の平均)  ・・・(3)
【００２９】
もしこの仮定が正しい、すなわちk’j＝kjである場合、図９上段に示すようなスパイクが現われる。もしこの仮定が誤り、すなわちk’j≠kjである場合、図９下段に示すようにスパイクが現れない平坦な曲線となる。よって、仮定したk’jから図９上段のような電力差分曲線が得られれば、拡大鍵の部分鍵kjを解読できたことになる。このようなkjの解読を各jについて行えば、最終的に図６における鍵Kの全てを解読することができる。拡大鍵K自身は、48-bitや128-bitの大きなビット長をもつため総当りによる解読が困難であるが、k’j, kjはSbox入力に関連する鍵のビット長であり、高々8-bitであるため、上記の手法による総当り解読は容易である。
【００３０】
この解読を、全ての拡大鍵0,拡大鍵1,…, 拡大鍵Nについて繰り返すことで、秘密鍵を解読することができる。なおAESの場合、アルゴリズムの性質上、拡大鍵の先頭の値がそのまま秘密鍵の値であるため、秘密鍵が128-bitならば拡大鍵0を、秘密鍵が192-bitもしくは256-bitならば拡大鍵0と拡大鍵1を解読すれば、秘密鍵全体を解読することができ、拡大鍵から秘密鍵の解読が容易である事が知られている。
【００３１】
次に、k’j=kjである場合、電力差分曲線DG(k’j)にスパイクが現れる理由について説明する。k’j=kjの場合、(1) 式および (2)式に従いG0(k’j), G1(k’j)の分類を行うことで、zjに関して(4)式が成立する。
(G1に属するzjの平均ハミングウェイト) - (G0に属するzjの平均ハミングウェイト) = 1  ・・・(4)
【００３２】
一方、k’j≠kjの場合(4)式は成立せず、ランダムな分類を行うことになるので(5)式が成立する。
(G1に属するzjの平均ハミングウェイト) - (G0に属するzjの平均ハミングウェイト)
= 0  ・・・(5)
ただし、ハミングウェイトとは、ある値をビット値で表現したときにビット値=’1’となる個数のことであり、例えばビット値(1101)2のハミングウェイトは3である。
【００３３】
よって、(4)式が成立する場合はG1(k’j)とG0(k’j)の間でのロード値zjの平均ハミングウェイトに差が生じるが、(5)式が成立する場合はG1(k’j)とG0(k’j)の間でのロード値zjの平均ハミングウェイトに差が生じない。
【００３４】
一般的に、消費電力はデータ値のハミングウェイトに比例すると考えられており、このことが正しいことを示した実験結果が非特許文献５などの文献にて示されている。
従って、k’j=kjである場合、(4)式が満たされることで消費電力の差が電力差分曲線上のスパイクという形になって現れるが、(5)式の場合はスパイクが現れず、平坦な曲線となる。
【００３５】
以上の説明では、最も簡単な図６の構造に対するDPAに関して述べたが、このような手法は、図１０に示すように、拡大鍵の前後に線形変換を挿入しても成立することが判明している。すなわち、図１０は、共通鍵暗号の一般的な処理(鍵XOR処理とテーブル変換と線形変換の組み合わせ)のアルゴリズムを示す図である。図１０は、図６を一般化した構造であり、鍵XOR処理の前後に2つの線形変換処理L1, L2を入れた処理構造である。例えば、L1は入力をそのまま出力する関数、L2をビット転置置換関数、wjをSC2000のB関数と呼ばれるSboxにすることで、図１０はSC2000と等価な構造を表す。なお、SC2000の仕様については、非特許文献６に詳細が開示されている。L2はビット置換関数であるので、wjの入出力に関係するビットのみを取りだした構造を考えることで、図１１と同一の処理に変換でき、前述と同様のDPAを用いることで、拡大鍵Kを解読することができる。
【００３６】
以上の手法では、非線形処理中のSbox出力に注目してDPAを適用しているが、そのほかにも、入力mjと鍵kjとのXOR直後の値(鍵XOR処理の出力値)やSboxへの入力値xjの値に注目してDPAを適用する手法が知られている(非特許文献７)。
【００３７】
上記を整理すると、次の条件を満たす場合にDPAにより秘密鍵が推定される。図１１は、DPAによる秘密鍵推定が可能な条件の説明図である。
DPA-1.：入力Mが既知かつ制御可能、拡大鍵Kは未知で固定、Sbox wjの変換が既知の場合、図１１のAの部分(Sbox wjの出力)の電力消費曲線を測定することでDPA可能。
DPA-2.：入力Mが既知かつ制御可能、拡大鍵Kは未知で固定の場合、図１１のBの部分(鍵XOR処理の出力の書き出し)の電力消費曲線を測定することでDPA可能。
DPA-3.：入力Mが既知かつ制御可能、拡大鍵Kは未知で固定の場合、図１１のCの部分(Sbox wjを索引するための入力値のロード)の電力消費曲線を測定することでDPA可能。
【００３８】
＜一般的に考えられるDPA対策手法＞
一般的に考えられるDPA対策法としては、暗号処理に対策を施し消費電力をランダム化する手法が存在する。この手法の代表的なものとして、masking method と呼ばれている手法が知られている(非特許文献８。以下「一般的に考えられる手法１」と呼ぶ)。DPA対策なしの暗号処理において計算されるデータをMとすると、非特許文献８に記載されているDPA対策は、データMを計算する代わりに、
2012131926.tif 000004
で表されるデータM’,Rを計算することで暗号処理を行う方法である。ただしRは乱数であり、暗号処理を実行する度に発生させる値である。この方法により、暗号処理のデータをランダムな値でマスクされる。よって、データがランダム化されることで消費電力もランダム化されるため、DPAに安全な処理を実現することができる。この方法の問題点は、M’, Rの両方を計算する必要があるため、対策なしの回路の２倍の回路規模を必要とすることである。
【００３９】
AESにおける非特許文献８の応用事例として、図１２のDPA未対策回路に対し、上記一般的に考えられる手法1を適用したAES回路を図１３に示す。この回路においては、図１２で計算しているデータMiの代わりに、乱数Riに対して
2012131926.tif 000005
を満たすMi’とRiの２つのランダムなデータを計算する。暗号化処理ごとに計算されるデータ値がランダムであるため、DPAに対して安全な処理を実現することができる。ただし、データをMi’とRiの両方について計算しなくてはならないため、回路規模が増大する。(図１２のおよそ２倍)。図１２ではAESのSubbyte処理を、固定データによる静的なSbox変換テーブルS[x] を用いたテーブル参照処理(0≦x≦255)によって行う。Subbyte処理で用いられる変換テーブルS[x]は、Sboxと呼ばれる。これに対して、図１３で用いられるSboxのテーブルデータS’[x]は、乱数Rin, Routに応じて
2012131926.tif 000006
に従ったS’[x]を、x=0,1,...,255それぞれに対して作成する必要がある。
【００４０】
このように一般的に考えられる手法１による対策法を、認証チップの共通鍵暗号回路に搭載することで、サイドチャネル攻撃に対する防御を実現できる。しかし、DPA対策無しの回路と比較して、回路規模が大きいという問題が発生する。
【００４１】
そこで、以下の各実施形態は、前述した一般的に考えられる手法1に示されるような専用の対策つき暗号回路を用いる代わりに、暗号より上位層の認証プロトコルへの改良によりサイドチャネル攻撃に安全な処理を実現する。暗号回路そのものは、未対策の回路をそのまま用いるため、前述した一般的に考えられる手法1が有する問題点を回避する。認証プロトコルは、乱数を伴う処理であるため、この乱数を適切に利用することで、サイドチャネル攻撃に対して安全となる方法が考えられる。すなわち、一般的なチャレンジアンドレスポンス認証では、前述した図２〜５に示されるように、固定の秘密鍵Kに対する暗号化処理が行われるが、これはサイドチャネル攻撃に対して脆弱な条件である。この欠点は、乱数を用いて秘密鍵をマスク化することで一見克服できそうであるが、発明者の分析によればこの方法もサイドチャネル攻撃に対して脆弱であることが判明した。
【００４２】
以下、基本概念1、基本概念2に基づく各実施形態について説明する前に、乱数を用いた単純な秘密鍵のランダム化法について説明する。そして、発明者の分析によりその方法が安全でないことを示したうえで、その問題点を克服した各実施形態について説明する。
【００４３】
＜単純な秘密鍵のランダム化(失敗事例)＞
図１４は、単純な鍵のランダム化による認証プロトコルの例１(片側認証、暗号化・復号)の機能ブロック図である。これは、図２をベースとしており、片側認証かつ暗号化・復号の両方を利用する認証プロトコルである。親機１０１側で生成した乱数rを子機１０２に送信し(図１４のＳ１４０１)、子機１０２はこの乱数rと秘密鍵Kによる暗号化処理を行ことでレスポンスaを生成する(図１４のＳ１４０２)。このレスポンスa生成の際、
2012131926.tif 000007
のように、鍵を乱数rでマスクした上で生成する。親機１０１に送信されたレスポンスは、親機１０１側で
2012131926.tif 000008
により復号され、r’がrと一致するか確認する(図１４のＳ１４０３)。
【００４４】
鍵Kをランダム化することで、サイドチャネル攻撃に一見安全そうであるが、脆弱であると結論付けられる。なぜなら、乱数rは親機１０１と子機１０２の間で共有するために送信される値であり、外部から容易に観察可能であるため、この観察された値を用いて、前述した(1)式および(2)式に示される部分鍵kj’を、攻撃者が推定した部分鍵に乱数rをXORされた値に置き換えることで、通常のサイドチャネル攻撃と同じ手順で鍵を解読できるからである。
【００４５】
同じ問題は、図１４をさらに拡張した図１５で発生する。図１５は、単純な鍵のランダム化による認証プロトコルの例２(片側認証、暗号化・復号)の機能ブロック図である。この図１５は、鍵をXORマスクする乱数r(図１５のＳ１５０１)が外部から観察可能であるため脆弱であった図１４の問題を解消するために、鍵をマスクする乱数の作成方法を変更し、rの代わりに
2012131926.tif 000009
を生成し、このmrを用いて秘密鍵Kをマスク化することでレスポンス
2012131926.tif 000010
を生成する(図１５のＳ１５０２、Ｓ１５０３)。mrが外部から観察できない値であるので、レスポンス生成がサイドチャネル攻撃に対して安全そうに見えるが、レスポンス生成の前段階の処理であり、mrを生成するときの処理の消費電力を測定することで、図１４と同様の手法により秘密鍵Kを解読することができる。
【００４６】
図１４、図１５の事例に示されるように、乱数を用いて鍵を単純にランダム化する手法だけでは、サイドチャネル攻撃に対して安全な認証プロトコルを実現することができない。以下の各実施形態はこの問題を解決し、対策つきの専用回路を用いなくともサイドチャネル攻撃に対して安全な認証プロトコルを実現する方式を示す。各実施形態について説明する前に、なぜ乱数を用いて鍵を単純にランダム化する手法だけでは安全でないかの理由を説明する。
【００４７】
図１６に、AES暗号回路を事例として、サイドチャネル攻撃が成功する要因の図を示す。128-bitの拡大鍵Kが、128-bit平文とXORされた後、8-bitごとに16分割され、それぞれのデータがSboxに入力される。攻撃者は、それぞれのSboxの消費電力データを利用することで、8-bitごとに分割された拡大鍵K=k15||…||k0に対し、8-bit部分鍵kjそれぞれの総当りを前述の(1)式および(2)式に従い実行する。つまり、128-bitの鍵の総当りには本来2128の手間が必要であるのに対し、サイドチャネル攻撃を用いることで28の手間を16回28×16=212に減らすことができる。すなわち、サイドチャネル攻撃に必要な手間は、Sboxの入力に関連した部分鍵のビット長によって決定する。このビット長は共通鍵暗号方式によって変動するが、既に説明したとおりAESの8-bitが最大である。つまりSbox入力の部分鍵ビット長が最も長いAESに対しても図１６の考えに基づいた攻撃が成功するならば、その他の共通鍵暗号ではさらに容易に成功することになる。これは、図１７に示すように、チャレンジアンドレスポンスの乱数で鍵をマスク化した場合でも同じである。鍵をマスク化した乱数が外部から観察可能であるので、乱数による鍵のマスク化の有無に関係なく、Sboxの入力に関連する部分鍵のビット長の総当りにより、鍵を解読することができる。
【００４８】
＜実施形態の基本概念＞
以上説明したように、チャレンジアンドレスポンスで用いる乱数をそのまま秘密鍵のマスクに用いても、サイドチャネル攻撃に対して安全な処理を実現することができない。この問題を克服するために、以下の各実施形態では、単純な秘密鍵のランダム化を行う代わりに、以下の３段階の手順を実行する。
(手順-1) 秘密鍵を複数個準備し
(手順-2) 乱数を用いて１つの鍵に圧縮し
(手順-3) (発明手法-2)で圧縮された鍵を、従来の認証プロトコルで用いられる秘密鍵Kの代わりに使用
【００４９】
単純なランダム化を実行する代わりに、(手順-2)に示されるようなランダムな鍵圧縮を実行することで、サイドチャネル攻撃に対する安全性と、小規模・高速な暗号処理を両立することができる(基本概念1)。
さらに、(手順-2)に示す乱数は、認証を行う側(片側認証における親機１０１側)で生成した乱数のみならず、認証される側(片側認証における子機１０２側)で生成した乱数を利用することで、さらに安全性を高めることができる(基本概念2)。基本概念1、基本概念2に共通する基本アイデアを図１８に示す。
【００５０】
図１８に示される通り、この基本アイデアでは、鍵を複数個(n個)準備し、それらを乱数を用いて1つに圧縮する。以下、乱数を用いて鍵を圧縮する処理をランダムな鍵圧縮と呼び、圧縮された鍵を圧縮鍵と呼ぶ。このアイデアは、チャレンジアンドレスポンス認証で用いる乱数は外部から観察されることは不回避であるという前提に基づくものであり、乱数が観察されたとしても、サイドチャネル攻撃における攻撃者の手間を増やすことが狙いである。ランダムな鍵圧縮は、以下の２条件を満たすものとする。
(cond-1)  n個の鍵と乱数の値が分かれば、圧縮鍵の値も分かる
(cond-2)  乱数とn個の鍵が全て分からない限り、圧縮鍵の値は分からない。
【００５１】
サイドチャネル攻撃においては、Sboxの入力する部分鍵のビット値が全て確定しないと、前述した(1)式および(2)式に示す攻撃を実施することはできない。この部分鍵は、図１８の圧縮鍵に相当する値である。しかし、上記の (cond-1)(cond-2)により、全ての圧縮鍵のビット値を確定するためには、乱数が外部に観察されたとしても、n個の部分鍵全ての値がわからない限り不可能となる。つまり、サイドチャネル攻撃を成功させるためには、一般的には一つの部分鍵に関する総当りを実施すればよかったのに対し、ランダムな鍵圧縮を用いることで、n個の部分鍵全てに関する総当りを実施する必要がある。例えばAESの場合、一般的に考えられる手法ならば28の手間で解読できたのに対し、ランダムな鍵圧縮を用いることで(28)nの手間となる。例えばn=8の場合264の手間となる。サイドチャネル攻撃における264は、現実的に不可能な計算量であるため、安全となる。
【００５２】
基本概念1は、ランダム鍵圧縮に用いる乱数として、チャレンジアンドレスポンスに用いる乱数をそのまま利用していた。チャレンジアンドレスポンスにおいては、暗号処理により応答を生成する機器と、応答生成に必要な乱数を生成するのは別の機器である。つまり、暗号処理を行う機器とは別の機器により乱数生成が行われる。もし、乱数生成をする側が不正行為を行い、常に変化すべき乱数を固定値として与えた場合、圧縮鍵が常に固定値となるため、攻撃に必要な手間が従来法と同じとなり、サイドチャネル攻撃を防ぐことができない。この攻撃を防ぐためには、応答を生成する側の機器から外部から受け取る乱数rに加えて、応答を生成する側の機器でも別の乱数sを生成し、これら２つの乱数r,sを用いて鍵圧縮を行うことである。これは基本概念2のアイデアであり、概要は図１９に示される。
【００５３】
認証機器は、認証プロトコルの通信相手から乱数rを受け取り、さらに自分自身でも乱数sを生成する。鍵圧縮処理はrとsの２つの乱数を用いて行うことで、外部入力乱数rが意図的に固定化された場合でも、内部生成された乱数sがランダムに変化することで、圧縮鍵が固定化されることを防ぎ、サイドチャネル攻撃に対する安全性を実現する。内部生成された乱数sは、外部出力され通信相手の認証機器に送信される。なぜなら、通信相手の機器も同じ圧縮鍵を生成する必要があるためであり、通信相手の機器は、自分自身が送信した乱数rと受け取ったsを元に、同じ圧縮鍵を生成する。 
【００５４】
基本概念1,2を、チャレンジアンド認証プロトコルに応用した認証プロトコルに関する第1から第8の実施形態を図２０から図２７に示す。図２０，図２１，図２２，図２３は、それぞれ基本概念1を図２，図３，図４，図５の認証プロトコルに応用したものである。また、図２４，図２５，図２６，図２７は、それぞれ基本概念2を図２，図３，図４，図５の認証プロトコルに応用したものである。
【００５５】
図２０から図２７の全てにおいて、親機１０１と子機１０２はn個の鍵K1, K2, …, Knを事前共有するものとする。図２０，図２１，図２２，図２３に示す基本概念1を用いた認証プロトコルは、基本的には図２，図３，図４，図５に示す認証プロトコルと同じである。図２０，図２１，図２２，図２３において、図２，図３，図４，図５の場合と同じ処理には、同じステップ番号(Ｓで始まる番号)を付してある。図２０，図２１，図２２，図２３が、図２，図３，図４，図５と異なる点は、親機１０１側で生成した乱数rと、n個の鍵K1, K2, …, Knを用いて、圧縮鍵Kcmpを生成し、この鍵を用いて暗号化処理を行う点である。子機１０２側では、図２０のＳ２００１、図２１のＳ２１０１、図２２のＳ２２０１、図２３のＳ２３０１の各処理である。親機１０１側では、図２０のＳ２００２、図２１のＳ２１０２、図２２のＳ２２０２、図２３のＳ２３０２の各処理である。図２０，図２１，図２２，図２３において、これらの鍵圧縮処理は
Kcmp = Compress(K1, K2, …, Kn, r)
と表現されており、圧縮処理を行うCompress関数はさまざまな実装形態が存在する。Compress関数の具体的な構成については、後述する。
【００５６】
図２４，図２５，図２６，図２７に示す基本概念2を用いた認証プロトコルは、基本的には図２，図３，図４，図５に示すプロトコルと同じである。図２４，図２５，図２６，図２７において、図２，図３，図４，図５の場合と同じ処理には、同じステップ番号(Ｓで始まる番号)を付してある。図２４，図２５，図２６，図２７が、図２，図３，図４，図５と異なる第一の相違点は、図２，図３では行っていなかった、子機１０２側の乱数sの生成処理が図２４，図２５で実行されている点である。図２４のＳ２４０１、図２５のＳ２５０１の各処理である。第二の相違点は、親機１０１側で生成した乱数rと、子機１０２側で生成した乱数s、およびn個の鍵K1, K2, …, Knを用いて、圧縮鍵Kcmpを生成し、この鍵を用いて暗号化処理を行う点である。子機１０２側では、図２4のＳ２４０２、図２５のＳ２５０２、図２６のＳ２６０１、図２７のＳ２７０１の各処理である。親機１０１側では、図２４のＳ２４０３、図２５のＳ２５０３、図２６のＳ２６０２、図２７のＳ２７０２の各処理である。図２４，図２５，図２６，図２７において、これらの鍵圧縮処理は
Kcmp = Compress_2(K1, K2, …, Kn, r,s)
と表現されており、圧縮処理を行うCompress_2関数はさまざまな実装形態が存在する。Compress_2関数の具体的な構成については、後述する。
【００５７】
＜Compress関数の基本構造＞
基本概念1の鍵圧縮に用いられるCompress関数の基本構造を図２８に示す。n個の鍵K1,...Knがそれぞれu-bitである。n個のu-bit鍵それぞれは、結線を用いたビット分割によりt個のg-bitブロックに分割される。鍵圧縮は、ブロック単位での実行をt回繰り返すことで実行される。すなわち、n個の鍵K1,...Knの1番目のブロックであるn個のg-bit値に対して、圧縮化回路２８０３で鍵圧縮処理を行った結果のg-bit値が、圧縮鍵Kcmpの1番目のk-bitブロック値となる。同様の処理を2番目からt番目のブロックについて繰り返すことで、圧縮鍵Kcmpの全てのブロック値が決定される。入力値のブロックの選択にはセレクタ(MUX)２８０１が、出力値のブロックの選択にはデマルチプレクサ(DEMUX)２８０４が用いられる。
【００５８】
圧縮化回路２８０３でのそれぞれのブロックの鍵圧縮処理においては、第一の乱数rによりn個のランダム化回路２８０２でランダム化処理が行われた結果、それぞれh-bitの中間出力値L1, ..., Lnを得る。ランダム化回路２８０２でのランダム化処理としては、さまざまな演算が適用可能である。回路規模が小さな演算としては、
・乱数と鍵の単純なビット結合 (g<h)
・乱数ビット値に応じた鍵の巡回シフト (g=h)
・乱数ビット値に応じて鍵に対する巡回シフトレジスタ(LFSR)処理の実行 (g=h)
・乱数と鍵のXOR (g==h)
・乱数と鍵のg-bit加算・減算(g==h)
・乱数と鍵のGF(2g)上の乗算(g<h)
が挙げられる。これらの演算を用いることで、乱数と鍵の全てのビットが、演算結果Liの値に対して影響を及ぼす。次に、中間出力値L1,...,Lnに対して、圧縮化回路２８０３圧縮処理を行うことで、g-bitの圧縮鍵Kcmpを出力する。この圧縮処理は、L1,...,Lnの全てのビットがKcmpに影響を及ぼす関数であれば、様々な演算が適用可能である。回路規模が小さな演算としては、
・全ての値のXOR(ランダム化処理がg==hの場合に限定)
・全ての値のg-bit加算(ランダム化処理がg==hの場合に限定)
・全ての値をXOR後、GF(2g)の剰余演算(ランダム化処理におけるg,hの制限なし)
・全ての値を加算後、GF(2g)の剰余演算(ランダム化処理におけるg,hの制限なし)
・全ての値をビット結合後、GF(2g)の剰余演算(ランダム化処理におけるg,hの制限なし)
が挙げられる。これらの処理を用いることで、L1,...,Lnの全てのビットがKcmpに影響を及ぼす。以上の２段階の処理を経ることで、前述した図１８および図１９の基本概念1,2の説明で示した(cond-1)(cond-2)が満たされた、ランダム鍵圧縮処理を実現できる。なぜなら、入力から一意に出力が決定されることで、(cond-1)が満たされ、また入力の全てのビットが出力に影響することで、(cond-2)が満たされるからである。
【００５９】
基本概念2の鍵圧縮に用いられるCompress_2関数の基本構造を図２９に示す。基本的には図２８と同じ構造である。図２９において、図２８の場合と同じ機能を実行する部分には同じ番号を付してある。図２９が図２８と異なる点は、第一の乱数rと第二の乱数sを入力することと、これらの乱数を乱数合成回路２９０１により1つの乱数に変換したうえで利用する点である。乱数合成回路２９０１は、第一の乱数rと第二の乱数sの全てのビット情報が出力に反映されるならば、様々な演算が適用可能である。回路規模が小さな演算としては、
・２つの乱数のXOR 
・２つの乱数のq-bit加算・減算
が挙げられる。ただし、qは乱数のビット長である。
【００６０】
図２８，図２９の「ランダム化回路２８０２」「圧縮回路２８０３」「乱数合成回路２９０１」として用いる回路によって、様々な実施例が存在する。具体例については、後述する。
【００６１】
以下に説明する鍵圧縮回路の第1から第8の実施例は、図２８、図２９の「ランダム化回路２８０２」「圧縮回路２８０３」「乱数合成回路２９０１」として用いる回路に関するものである。
【００６２】
それぞれの実施例で用いられる回路の組み合わせは以下の通りである。
＊基本概念1を用いた実施例
・第1の実施例
ランダム化回路２８０２：乱数ビット値に応じた鍵の巡回シフト
圧縮化回路２８０３：全ての値のXOR
・第2の実施例
ランダム化回路２８０２：乱数と鍵の単純なビット結合
圧縮回路２８０３：全ての値をXOR後、GF(2g)の剰余演算
・第3の実施例
ランダム化回路２８０２：乱数ビット値に応じて鍵に対するLFSR処理の実行
圧縮回路２８０３：全ての値のXOR
・第4の実施例
ランダム化回路２８０２：乱数と鍵のGF(2g)上の乗算 (g<h)
圧縮回路２８０３：全ての値をXOR後、GF(2g)の剰余演算
【００６３】
＊基本概念2を用いた実施例
・第5の実施例
ランダム化回路２８０２：乱数ビット値に応じた鍵の巡回シフト
圧縮化回路２８０３：全ての値のXOR
乱数合成回路２９０１：２つの乱数のXOR
・第6の実施例
ランダム化回路２８０２：乱数と鍵の単純なビット結合
圧縮回路２８０３：全ての値をXOR後、GF(2g)の剰余演算
乱数合成回路２９０１：２つの乱数のq-bit加算
・第7の実施例
ランダム化回路２８０２：乱数ビット値に応じて鍵に対するLFSR処理の実行
圧縮回路２８０３：全ての値をXOR後、GF(2g)の剰余演算
乱数合成回路２９０１：２つの乱数のXOR
・第8の実施例
ランダム化回路２８０２：乱数と鍵のGF(2g)上の乗算 (g<h)
圧縮回路２８０３：全ての値をXOR後、GF(2g)の剰余演算
乱数合成回路２９０１：２つの乱数のXOR
【００６４】
上記第1から第8の全ての実施例においては、128-bit共通鍵ブロック暗号において128-bit鍵を用いていると仮定する。すなわち、秘密鍵K1,…,Knのそれぞれは128-bitであり、乱数r,sは最大128-bitであるとする。全てのr,sのビットを鍵圧縮に用いる必要はない。
【００６５】
上記第1から第8のいずれの実施例も、必要な追加回路の回路規模を4.8Kgateから8.7Kgate(Kgateは1000ゲートを示す)と小さく抑えることができ、暗号回路規模を２倍以上大きくする一般的に考えられる手法1より優れた効果を発揮する。例えば、下記文献に記されるサイドチャネル攻撃対策なしのAES回路は、17.6Kgateを必要とするため、この回路が２倍化される構成と比較して、第1から第8の実施例は優れた効果を発揮する。
【００６６】
＜実施例１＞
図３０は、鍵圧縮回路の第1の実施例(基本概念1その1)を示す図である。図３０において、図２８の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。128-bit秘密鍵Ki(1≦i≦4)のそれぞれは、16-bitごとに8分割され、それぞれKi,7,…, Ki,0と表記される。4つのKiそれぞれは、外部から入力されるセレクト信号に従い、セレクタ(8-1MUX)２８０１により、8分割された16-bit部分鍵のいずれかをセレクトする。セレクトされた4つの16-bit部分鍵それぞれに対して、16-bit乱数を4分割した4-bit乱数に基づき、ランダム化回路２８０２である巡回シフト回路群により、巡回シフト処理が行われる。巡回シフトは16通りであるため、乱数は4-bitで十分である。４つの16-bit巡回シフト回路の出力は、圧縮化回路２８０３であるXOR(排他論理和回路)にてXORされることで1つの16-bit値を生成する。この16-bit値は、圧縮鍵Kcmpの16-bit部分鍵Kcmp,jである。ただし、Kcmp,jは、下位ビットから数えてj番目(j=0,...,7)の部分鍵を表す。セレクト信号を、8分割された部分鍵それぞれについて切り替えることで、デマルチプレクサ(8-1DEMUX)２８０４にて、j=0,1,…,7全ての圧縮鍵を生成する。
【００６７】
圧縮された部分鍵は、4つの16-bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、(216)4=264の手間が攻撃者にとって必要となるため、安全である。
【００６８】
上述の鍵圧縮回路の第1の実施例の回路規模の見積もりについて、以下に説明する。図３１は、鍵圧縮回路の実施例の回路規模見積もり基準の表を示す図である。
図３１の表は、1-bitあたりの回路規模(gate/bit)を示したものである。ここでは、回路規模を、2入力NAND(2入力NOR)換算ゲート数として示している。図３２および図３３は、回路規模の算定基準となるNANDゲートおよびNORゲートの回路規模見積を示す図である。図３２および図３３のように、2入力NANDゲートおよび2入力NORゲートのいずれも、４つのMOSFET(金属酸化絶縁膜半導体電界効果トランジスタ：Metal-Oxide-Semiconductor Field-Effect Transistor)によって1ゲートが構成されている。
【００６９】
図３４は、NOTゲートの回路規模見積を示す図である。NOTゲートは、図３４に示されるように2つのMOSFETから構成されるため、図３１に示されるように、ゲート数は0.5ゲートとなる。
【００７０】
図３５は、1入力D-フリップフロップによって構成されるレジスタの回路規模見積を示す図である。レジスタは、図３５に示されるように、4つのNANDゲート(図３２参照)と、1つのNORゲート(図３３参照)と、4つのNOTゲート(図３４参照)と、それぞれ1ゲートからなる4個のゲート単位とから構成される。このため、図３１に示されるように、レジスタのゲート数は、1*4+1*1+0.5*4+1*4=11ゲートとなる(“*”は乗算を示す)。
【００７１】
図３６は、2入力XOR(排他論理和回路)の回路規模見積を示す図である。XORは、図３６に示されるように、2つのNORゲート(図３３参照)と、1つのNANDゲート(図３２参照)と、1つのNOTゲート(図３４参照)とから構成される。このため、図３１に示されるように、XORのゲート数は、1*2+1*1+0.5*1=3.5ゲートとなる。
【００７２】
図３７は、2-1セレクタの回路規模見積を示す図である。図３７(ａ)はマルチプレクサ(MUX)、図３７(ｂ)はデマルチプレクサ(DEMUX)である。マルチプレクサ(MUX)は、図３７(ａ)に示されるように、3つのNANDゲート(図３２参照)と、1つのNOTゲート(図３４参照)とから構成される。このため、図３１に示されるように、2-1セレクタ(MUX)のゲート数は、1*3+0.5*1=3.5ゲートとなる。また、デマルチプレクサ(DEMUX)は、図３７(ｂ)に示されるように、2つのNANDゲート(図３２参照)と3つのNOTゲート(図３４参照)とから構成される。このため、図３１に示されるように、2-1セレクタ(DEMUX)のゲート数はやはり、1*2+0.5*3=3.5ゲートとなる。
【００７３】
図３８は、加減算器の回路規模見積を示す図である。加減算器は、図３８に示されるように、1つの3入力XORゲート(7gate/3入力XOR)(図３６参照)と、4つの3入力NANDゲート(2ゲート/3入力NAND)(図３２参照)とから構成される。このため、図３１に示されるように、加減算器のゲート数は、7*1+2*4=15ゲートとなる。
【００７４】
図３９は、シフト／巡回レジスタの回路規模見積(14.5ゲート)を示す図である。シフト／巡回レジスタは、図３９に示されるように、1つのセレクタ(MUX)(図３７（ａ）参照)と、1つのレジスタ(図３５参照)とから構成される(図３９では3段分が示されている）。このため、図３１に示されるように、シフト／巡回レジスタのゲート数は、3.5*1+11*1=14.5ゲートとなる。
【００７５】
図４０は、LSFR／剰余演算回路の回路規模見積を示す図である。LSFR／剰余演算回路は、図４０に示されるように、1つのセレクタ(MUX)(図３７（ａ）参照)と、1つのレジスタ(図３５参照)と、ビット位置に対応して0または1個のXORゲート(図３６参照)とから構成される(図４０では3段分が示されている）。このため、図３１に示されるように、LSFR／剰余演算回路のゲート数は高々、3.5*1+11*1+3.5*1=18ゲートとなる。
【００７６】
また、特には図示しないが、ANDゲートおよびORゲートのゲート数は、図３１に示されるように、それぞれ1.5ゲートとなる。
ここで、図３１は、1-bitあたりの回路規模を示したものであるため、8-bitレジスタならば11×8=88gate(ゲート)、16-bitシフトレジスタならば14.5×16=232gateと見積もられる。さらに、図３１は、2入力1出力(2-1と記される)の演算回路の規模を表すが、これはm入力1出力となった場合(m-1と記される)は、2入力1出力の演算回路の(m-1)倍の回路規模である。例えば、10-bit 2-1 XOR回路は3.5×10=35gateであるが、10-bit 4-1 XOR回路は回路規模が3倍となり3×3.5×10=105gateである。20-bit 4-1加算器の場合、(20×15)×3=900gateとなる。
【００７７】
図４１は、図３１に示される見積もり基準に基づいて計算される、図３０に示される鍵圧縮回路の第1の実施例(基本概念1その1)の回路規模の見積表を示す図である。ただし、図３０において、Kcmpを出力するレジスタは、暗号回路のレジスタと共用するため、評価に含まれない。図４１に示されるように、図３０において、鍵レジスタ部分が5.6Kgate、セレクタ(8-1MUX)２８０１の部分が1.6Kgate、ランダム化回路２８０２である巡回シフトレジスタ部分が0.93Kgateである。さらに、図３０において、圧縮化回路２８０３である4-1XORの部分が0.1Kgate、デマルチプレクサ(8-1DEMUX)２８０４の部分が0.4Kgateである。この結果、図３０の鍵圧縮回路全体の回路規模は、8.6Kgateとなり、従来の半分程度の回路規模で実現できることがわかる。
【００７８】
＜実施例２＞
図４２は、鍵圧縮回路の第2の実施例(基本概念1その2)を示す図である。図４２において、図２８の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。128-bit秘密鍵Ki(1≦i≦2)のそれぞれは、32-bitごとに4分割され、それぞれKi,3,…, Ki,0と表記される。２つのKiそれぞれは、外部から入力されるセレクト信号に従い、セレクタ(4-1MUX)２８０１が、4分割された32-bit部分鍵のいずれかをセレクトする。次に、ランダム化回路２８０２において、セレクトされた２つの32-bit部分鍵それぞれに対して、32-bit乱数を2分割した16-bit乱数がビット結合される。さらに、圧縮化回路２８０３の構成として、ランダム化回路２８０２でのビット結合結果の2つの48-bit値がXORされ、このXOR結果に対してGF(232)の剰余演算(GF(232)の剰余回路)が実行される。GF(232)の剰余演算は、例えばCRC符号で用いられる多項式、
x32+x28+x27+x26+x25+x23+x22+x20+x19+x18+x14+x13+x11+x10+x9+x8+x6+1
による剰余演算が適切である。剰余演算の結果の32-bitは、圧縮鍵Kcmpの32-bit部分鍵Kcmp,jである。ただし、Kcmp,jは、下位ビットから数えてj番目(j=0,...,3)の部分鍵を表す。セレクト信号を、4分割された部分鍵それぞれについて切り替えることで、デマルチプレクサ(4-1DEMUX)２８０４が、j=0,1,…,3全ての圧縮鍵を生成する。
【００７９】
圧縮された部分鍵は、2つの32-bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、(232)2=264の手間が攻撃者にとって必要となるため、安全である。
【００８０】
図４３は、図３１に示される見積もり基準に基づいて計算される、図４２に示される鍵圧縮回路の第2の実施例(基本概念1その2)の回路規模の見積表を示す図である。ただし、Kcmpを出力するレジスタは、暗号回路のレジスタと共用するため、評価に含まれない。図４３に示されるように、図４２において、鍵レジスタ部分が2.8Kgate、セレクタ(4-1MUX)２８０１の部分が0.67Kgate、圧縮化回路２８０３の一部である2-1XORの部分が0.12Kgateである。さらに、圧縮化回路２８０３の一部であるGF(232)剰余回路の部分が0.86Kgate、デマルチプレクサ(4-1DEMUX)２８０４の部分が0.34Kgateである。この結果、図４２の鍵圧縮回路全体の回路規模は、4.8Kgateとなり、従来の半分程度の回路規模で実現できることがわかる。
【００８１】
＜実施例３＞
図４３は、鍵圧縮回路の第3の実施例(基本概念1その3)を示す図である。図４３において、図２８の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。128-bit秘密鍵Ki(1≦i≦2)のそれぞれは、32-bitごとに4分割され、それぞれKi,3,…, Ki,0と表記される。２つのKiそれぞれは、外部から入力されるセレクト信号に従い、セレクタ(4-1MUX)２８０１が、4分割された32-bit部分鍵のいずれかをセレクトする。次に、ランダム化回路２８０２である32-bitLFSR(Linear Feedback Shift Register)が、セレクトされた２つの32-bit部分鍵それぞれに対して、16-bit乱数を2分割した8-bit乱数ビット値で与えられるシフト量に従ったLFSR処理を実行する。LFSR処理で用いられる多項式は様々なものが知られているが、例えば、
x32+x7+x5+x3+x2+x+1
が利用可能である。次に、圧縮化回路２８０３であるXOR(排他論理和回路)にて、２つのLFSR処理結果をXORすることで、圧縮鍵Kcmpの32-bit部分鍵Kcmp,jを得る。ただし、Kcmp,jは、下位ビットから数えてj番目(j=0,...,3)の部分鍵を表す。セレクト信号を、4分割された部分鍵それぞれについて切り替えることで、デマルチプレクサ(4-1DEMUX)２８０４にて、j=0,1,…,3全ての圧縮鍵を生成する。
【００８２】
圧縮された部分鍵は、2つの32-bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、(232)2=264の手間が攻撃者にとって必要となるため、安全である。
【００８３】
図４５は、図３１に示される見積もり基準に基づいて計算される、図４４に示される鍵圧縮回路の第3の実施例(基本概念1その3)の回路規模の見積表を示す図である。。ただし、Kcmpを出力するレジスタは、暗号回路のレジスタと共用するため、評価に含まれない。図４５に示されるように、図４４において、鍵レジスタ部分が2.8Kgate、セレクタ(4-1MUX)２８０１の部分が0.67Kgate、ランダム化回路２８０２であるLFSRの部分が1.15Kgateである。さらに、圧縮化回路２８０３である2-1XORの部分が0.1Kgate、デマルチプレクサ(4-1DEMUX)２８０４の部分が0.34Kgateである。この結果、図４４の鍵圧縮回路全体の回路規模は、5.0Kgateとなり、従来の半分程度の回路規模で実現できることがわかる。
【００８４】
＜実施例４＞
図４６は、鍵圧縮回路の第4の実施例(基本概念1その4)を示す図である。図４６において、図２８の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。128-bit秘密鍵Ki(1≦i≦2)のそれぞれは、32-bitごとに4分割され、それぞれKi,3,…, Ki,0と表記される。２つのKiそれぞれは、外部から入力されるセレクト信号に従い、セレクタ(4-1MUX)２８０１が、4分割された32-bit部分鍵のいずれかをセレクトする。次に、ランダム化回路２８０２において、セレクトされた２つの32-bit部分鍵それぞれに対して、64-bit乱数を2分割した32-bit乱数ビット値同士の多項式乗算を行い、２つの64-bit値を生成する。多項式乗算を
2012131926.tif 000011
と記した場合、多項式乗算は、乗数aを格納するシフトレジスタ1個と、被乗数bを格納するレジスタ1個と、32-bitXOR回路1個により実現できる。さらに、圧縮化回路２８０３の構成として、ランダム化回路２８０２での乗算の結果の２つの64-bitがXOR演算される。このXOR結果に対してGF(232)の剰余演算(GF(232)の剰余回路)が実行される。GF(232)の剰余演算は、例えばCRC符号で用いられる多項式、
x32+x28+x27+x26+x25+x23+x22+x20+x19+x18+x14+x13+x11+x10+x9+x8+x6+1
による剰余演算が適切である。剰余結果の32-bit値により、圧縮鍵Kcmpの32-bit部分鍵Kcmp,jを得る。ただし、Kcmp,jは、下位ビットから数えてj番目(j=0,...,3)の部分鍵を表す。セレクト信号を、4分割された部分鍵それぞれについて切り替えることで、デマルチプレクサ(4-1DEMUX)２８０４が、j=0,1,…,3全ての圧縮鍵を生成する。
【００８５】
圧縮された部分鍵は、2つの32-bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、(232)2=264の手間が攻撃者にとって必要となるため、安全である。
【００８６】
図４７は、図３１に示される見積もり基準に基づいて計算される、図４６に示される鍵圧縮回路の第4の実施例(基本概念1その4)の回路規模の見積表を示す図である。ただし、Kcmpを出力するレジスタは、暗号回路のレジスタと共用するため、評価に含まれない。図４７に示されるように、図４６において、鍵レジスタ部分が2.8Kgate、セレクタ(4-1MUX)２８０１の部分が0.67Kgate、ランダム化回路２８０２である多項式乗算器の一部を構成するシフトレジスタの部分が0.93Kgateである。同じく上記多項式乗算器の一部を構成するレジスタの部分が0.7Kgate、同じく上記多項式乗算器の一部を構成する2-1XORの部分が0.2Kgateである。また、圧縮化回路２８０３の一部である2-1XORの部分が0.12Kgateであり、圧縮化回路２８０３の一部であるGF(232)剰余回路の部分が1.15Kgate、デマルチプレクサ(4-1DEMUX)２８０４の部分が0.34Kgateである。この結果、図４６の鍵圧縮回路全体の回路規模は、7.0Kgateとなり、従来の半分程度の回路規模で実現できることがわかる。
【００８７】
＜実施例５＞
図４８は、鍵圧縮回路の第5の実施例(基本概念2その1)を示す図である。図４８において、図２９の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。図４８の構成は、基本的には図３０の第1の実施例の場合と同じであるが、2つの16-bit乱数r,sを乱数合成回路２９０１であるXORにより合成した結果の16-bit値を、ランダム化圧縮の乱数として用いるところが異なる。
【００８８】
圧縮された部分鍵は、4つの16-bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、(216)4=264の手間が攻撃者にとって必要となるため、安全である。
【００８９】
図４９は、図３１に示される見積もり基準に基づいて計算される、図４８に示される鍵圧縮回路の第5の実施例(基本概念2その1)の回路規模の見積表を示す図である。乱数圧縮回路２９０１の分だけゲート数が増加しているほかは、図４１に示される実施例1の場合と同じである。
【００９０】
＜実施例６＞
図５０は、鍵圧縮回路の第6の実施例(基本概念2その2)を示す図である。図５０において、図２９の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。２つの乱数の合成に乱数合成回路２９０１である加算器２９０１による加算を用いるほかは、図４２に示される第2の実施例の場合と同じである。
【００９１】
圧縮された部分鍵は、2つの32-bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、(232)2=264の手間が攻撃者にとって必要となるため、安全である。
【００９２】
図５１は、図３１に示される見積もり基準に基づいて計算される、図５０に示される鍵圧縮回路の第6の実施例(基本概念2その2)の回路規模の見積表を示す図である。乱数圧縮回路２９０１の分だけゲート数が増加しているほかは、図４３に示される実施例2の場合と同じである。
【００９３】
＜実施例７＞
図５２は、鍵圧縮回路の第7の実施例(基本概念2その3)を示す図である。図５２において、図２９の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。２つの乱数の合成に乱数合成回路２９０１であるXORを用いるほかは、図４４に示される第3の実施例の場合と同じである。
【００９４】
圧縮された部分鍵は、2つの32-bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、(232)2=264の手間が攻撃者にとって必要となるため、安全である。
【００９５】
図５３は、図３１に示される見積もり基準に基づいて計算される、図５２に示される鍵圧縮回路の第7の実施例(基本概念2その3)の回路規模の見積表を示す図である。乱数圧縮回路２９０１の分だけ増加しているほかは、図４５に示される第3の実施例の場合と同じである。
【００９６】
＜実施例８＞
図５４は、鍵圧縮回路の第8の実施例(基本概念2その4)を示す図である。図５４において、図２９の基本構造図の場合と同じ機能を有する部分には同じ番号を付してある。２つの乱数の合成に乱数合成回路２９０１であるXORを用いるほかは、図４６に示される第4の実施例の場合と同じである。
【００９７】
圧縮された部分鍵は、2つの32-bit部分鍵の全てのビット情報を含みながら圧縮されるので、乱数が外部に観察されたとしても、(232)2=264の手間が攻撃者にとって必要となるため、安全である。
【００９８】
図５５は、図３１に示される見積もり基準に基づいて計算される、図５４に示される鍵圧縮回路の第8の実施例(基本概念2その4)の回路規模の見積表を示す図である。乱数圧縮回路２９０１の分だけ増加しているほかは、図４７に示される第4の実施例の場合と同じである。
【００９９】
以上説明したように、各実施形態を用いることで、一般的に考えられる手法1のように、回路を２倍化することなく、小さい回路規模増ながらも、サイドチャネル攻撃に安全な暗号処理および認証処理を実現することが可能となる。
なお、上述の基本概念1,2に基づく処理は、認証処理のみならず、暗号処理一般にも適用することが可能である。
【０１００】
図５６は、上記システムをソフトウェア処理として実現できるコンピュータのハードウェア構成の一例を示す図である。
【０１０１】
図５６に示されるコンピュータは、ＣＰＵ５６０１、メモリ５６０２、入力装置５６０３、出力装置５６０４、外部記憶装置５６０５、可搬記録媒体５６０９が挿入される可搬記録媒体駆動装置５６０６、及び通信インタフェース５６０７を有し、これらがバス５６０８によって相互に接続された構成を有する。同図に示される構成は上記システムを実現できるコンピュータの一例であり、そのようなコンピュータはこの構成に限定されるものではない。
【０１０２】
ＣＰＵ５６０１は、当該コンピュータ全体の制御を行う。メモリ５６０２は、プログラムの実行、データ更新等の際に、外部記憶装置５６０５(或いは可搬記録媒体５６０９)に記憶されているプログラム又はデータを一時的に格納するＲＡＭ等のメモリである。ＣＵＰ５６０１は、プログラムをメモリ５６０２に読み出して実行することにより、全体の制御を行う。
【０１０３】
入出力装置５６０３は、ユーザによるキーボードやマウス等による入力操作を検出し、その検出結果をＣＰＵ５６０１に通知し、ＣＰＵ５６０１の制御によって送られてくるデータを表示装置や印刷装置に出力する。
【０１０４】
外部記憶装置５６０５は、例えばハードディスク記憶装置である。主に各種データやプログラムの保存に用いられる。
可搬記録媒体駆動装置５６０６は、光ディスクやＳＤＲＡＭ、コンパクトフラッシュ（登録商標）等の可搬記録媒体５６０９を収容するもので、外部記憶装置５６０５の補助の役割を有する。
【０１０５】
通信インターフェース５６０７は、例えばＬＡＮ(ローカルエリアネットワーク)又はＷＡＮ(ワイドエリアネットワーク)の通信回線を接続するための装置である。
上述した第1〜第8の実施形態によるシステムは、それらの機能を搭載したプログラムをＣＰＵ５６０１が実行することで実現される。そのプログラムは、例えば外部記憶装置５６０５や可搬記録媒体５６０９に記録して配布してもよく、或いはネットワーク接続装置５６０７によりネットワークから取得できるようにしてもよい。
【０１０６】
以上のようにして実行されるプログラムにより、小さい処理量増ながらも、サイドチャネル攻撃に安全な暗号処理および認証処理を実現することが可能となる。
【図１】
2012131926.tif 000012
【図２】
2012131926.tif 000013
【図３】
2012131926.tif 000014
【図４】
2012131926.tif 000015
【図５】
2012131926.tif 000016
【図６】
2012131926.tif 000017
【図７】
2012131926.tif 000018
【図８】
2012131926.tif 000019
【図９Ａ】
2012131926.tif 000020
【図９Ｂ】
2012131926.tif 000021
【図１０】
2012131926.tif 000022
【図１１】
2012131926.tif 000023
【図１２】
2012131926.tif 000024
【図１３】
2012131926.tif 000025
【図１４】
2012131926.tif 000026
【図１５】
2012131926.tif 000027
【図１６】
2012131926.tif 000028
【図１７】
2012131926.tif 000029
【図１８】
2012131926.tif 000030
【図１９】
2012131926.tif 000031
【図２０】
2012131926.tif 000032
【図２１】
2012131926.tif 000033
【図２２】
2012131926.tif 000034
【図２３】
2012131926.tif 000035
【図２４】
2012131926.tif 000036
【図２５】
2012131926.tif 000037
【図２６】
2012131926.tif 000038
【図２７】
2012131926.tif 000039
【図２８】
2012131926.tif 000040
【図２９】
2012131926.tif 000041
【図３０】
2012131926.tif 000042
【図３１】
2012131926.tif 000043
【図３２】
2012131926.tif 000044
【図３３】
2012131926.tif 000045
【図３４】
2012131926.tif 000046
【図３５】
2012131926.tif 000047
【図３６】
2012131926.tif 000048
【図３７】
2012131926.tif 000049
【図３８】
2012131926.tif 000050
【図３９】
2012131926.tif 000051
【図４０】
2012131926.tif 000052
【図４１】
2012131926.tif 000053
【図４２】
2012131926.tif 000054
【図４３】
2012131926.tif 000055
【図４４】
2012131926.tif 000056
【図４５】
2012131926.tif 000057
【図４６】
2012131926.tif 000058
【図４７】
2012131926.tif 000059
【図４８】
2012131926.tif 000060
【図４９】
2012131926.tif 000061
【図５０】
2012131926.tif 000062
【図５１】
2012131926.tif 000063
【図５２】
2012131926.tif 000064
【図５３】
2012131926.tif 000065
【図５４】
2012131926.tif 000066
【図５５】
2012131926.tif 000067
【図５６】
2012131926.tif 000068
【手続補正書】
【提出日】平成25年8月22日(2013.8.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
それぞれK１, K２, …, Kｎビットからなるｎ個の鍵を乱数によりランダム化するランダム化回路と、
前記ランダム化されたｎ個の鍵から１つの鍵を生成することにより圧縮して得られる圧縮鍵を出力する圧縮化回路と、
前記圧縮鍵を用いて入力データを暗号化する暗号化回路と、
を含むことを特徴とする暗号処理装置。
【請求項２】
第一の乱数と第二の乱数を入力し合成し前記乱数として出力する乱数合成回路を更に含む、
ことを特徴とする請求項１に記載の暗号処理装置。
【請求項３】
それぞれK１, K２, …, Kｎビットからなるｎ個の鍵を乱数によりランダム化し、
前記ランダム化されたｎ個の鍵から１つの鍵を生成することにより、圧縮して得られる圧縮鍵を生成し、
前記圧縮鍵を用いて認証する、
ことを特徴とする認証方法。
【請求項４】
第一の乱数と第二の乱数を入力し合成し前記乱数として出力する、
ことを特徴とする請求項３に記載の暗号処理方法。
【請求項５】
親機に相当する第１のコンピュータと子機に相当する第２のコンピュータとで前記ｎ個の鍵として秘密鍵Kを共有し、
前記第１のコンピュータにて、乱数rを生成し、
前記第１のコンピュータから前記第２のコンピュータに前記乱数rを送信し、
前記第２のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１のコンピュータから受信した前記乱数rとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータから受信した前記乱数rを暗号化することで暗号化された乱数ａを生成して前記第１のコンピュータに送信し、
前記第１のコンピュータにて、前記ｎ個の秘密鍵Kと前記乱数rとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、
前記第１のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第２のコンピュータの認証を行う、
ことを特徴とする請求項３または４のいずれか記載の認証方法。
【請求項６】
親機に相当する第１のコンピュータと子機に相当する第２のコンピュータとで前記ｎ個の鍵としてｎ個の秘密鍵Kを共有し、
前記第１のコンピュータにて、第１の乱数rを生成し、
前記第１のコンピュータから前記第２のコンピュータに前記第１の乱数rを送信し、
前記第２のコンピュータにて、第２の乱数sを生成し、
前記第２のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１のコンピュータから受信した前記第１の乱数rとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータから受信した前記第１の乱数rを暗号化することで第１の暗号化された乱数ａを生成して前記第２の乱数sとともに前記第１のコンピュータに送信し、
前記第１のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１の乱数rとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、
前記第１のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第２のコンピュータの認証を行い、
前記第１のコンピュータにて、前記認証に成功した場合に、前記圧縮鍵Kcmpを用いて前記第２のコンピュータから受信した前記第２の乱数sを暗号化することで第２の暗号化された乱数ｂを生成して前記第２のコンピュータに送信し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータの認証を行う、
ことを特徴とする請求項３または４のいずれか記載の認証方法。
【請求項７】
親機に相当する第１のコンピュータと子機に相当する第２のコンピュータとで前記ｎ個の鍵としてｎ個の秘密鍵Kを共有し、
前記第１のコンピュータにて、第１の乱数rを生成し、
前記第１のコンピュータから前記第２のコンピュータに前記第１の乱数rを送信し、
前記第２のコンピュータにて、第２の乱数sを生成し、
前記第２のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１のコンピュータから受信した前記第１の乱数rと前記第２の乱数sとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータから受信した前記第１の乱数rを暗号化することで暗号化された乱数ａを生成して前記第２の乱数sとともに前記第１のコンピュータに送信し、
前記第１のコンピュータにて、前記ｎ個の秘密鍵Kと前記乱数rと前記第２のコンピュータから受信した乱数sとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、
前記第１のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第２のコンピュータの認証を行う、
ことを特徴とする請求項３または４のいずれか記載の認証方法。
【請求項８】
親機に相当する第１のコンピュータと子機に相当する第２のコンピュータとで前記ｎ個の鍵としてｎ個の秘密鍵Kを共有し、
前記第１のコンピュータにて、第１の乱数rを生成し、
前記第１のコンピュータから前記第２のコンピュータに前記第１の乱数rを送信し、
前記第２のコンピュータにて、第２の乱数sを生成し、
前記第２のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１のコンピュータから受信した前記第１の乱数rと前記第２の乱数sとから前記圧縮鍵の生成に従って圧縮鍵Kcmpを生成し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータから受信した前記第１の乱数rを暗号化することで第１の暗号化された乱数ａを生成して前記第２の乱数sとともに前記第１のコンピュータに送信し、
前記第１のコンピュータにて、前記ｎ個の秘密鍵Kと前記第１の乱数rと前記第２のコンピュータから受信した前記第２の乱数sとから前記圧縮鍵の生成に従って前記圧縮鍵Kcmpを生成し、
前記第１のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第２のコンピュータの認証を行い、
前記第１のコンピュータにて、前記認証に成功した場合に、前記圧縮鍵Kcmpを用いて前記第２のコンピュータから受信した前記第２の乱数sを暗号化することで第２の暗号化された乱数ｂを生成して前記第２のコンピュータに送信し、
前記第２のコンピュータにて、前記圧縮鍵Kcmpを用いて前記第１のコンピュータの認証を行う、
ことを特徴とする請求項３または４のいずれか記載の認証方法。
【請求項９】
コンピュータに、
複数個の鍵のそれぞれを乱数によりランダム化し、
前記ランダム化された複数個の鍵を圧縮して得られる圧縮鍵を暗号処理のための鍵として出力する、
処理を実行させるためのプログラム。
【請求項１０】
コンピュータに、
第一の乱数と第二の乱数を入力し合成し前記乱数として出力する、
処理を実行させるための請求項９に記載のプログラム。
【国際調査報告】
2012131926.tif 000069
2012131926.tif 000070
2012131926.tif 000071
2012131926.tif 000072