(57)【要約】【課題】不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法において、実装攻撃に対する耐タンパ性を向上することを目的とする。【解決手段】複数の変化条件ルールに従って状態値生成回路で現在の状態値に対する状態遷移後の状態値を生成し、任意の１つの変化条件ルールに従って生成された状態遷移後の状態値と前記任意の１つの変化条件ルールを乱数に基づいて選択部から選択出力し、演算開始入力に基づいて状態値格納部に現在の状態値を格納すると共に選択部から選択出力される状態遷移後の状態値を格納し、状態値格納部の入出力に基づき状態遷移後の状態値と現在の状態値を状態値比較回路で比較し、状態遷移が前記任意の１つの変化条件ルールに従っていないと不正操作を検知して検知信号を出力し、前記複数の変化条件ルールは互いに異なり、且つ、同一固定ビット数の値変化を用いるルールであるように構成する。【選択図】図８
2013207414.tif 000002
【特許請求の範囲】
【請求項１】
互いに異なる複数の、状態値の変化条件ルールを出力する変化条件ルール出力回路と、
前記複数の変化条件ルールに従って現在の状態値に対する状態遷移後の状態値を生成する状態値生成回路と、
前記複数の変化条件ルールに従って前記状態値生成回路で生成された状態遷移後の状態値のうち、任意の１つの変化条件ルールに従って生成された状態遷移後の状態値と、前記変化条件ルール出力回路から出力された前記複数の変化条件ルールのうち、前記任意の１つの変化条件ルールを、乱数に基づいて選択出力する選択部と、
演算開始入力に基づいて前記現在の状態値を格納すると共に、前記選択部から選択出力される前記状態遷移後の状態値を格納する状態値格納部と、
前記状態値格納部の入出力に基づき前記状態遷移後の状態値と前記現在の状態値を比較し、状態遷移が前記選択部から選択出力される前記任意の１つの変化条件ルールに従っていないと不正操作を検知して検知信号を出力する状態値比較回路
を備え、
前記複数の変化条件ルールは、同一固定ビット数の値変化を用いるルールである
ことを特徴とする不正操作検知回路。
【請求項２】
前記複数の変化条件ルールは、いずれも１ビット値変化を用いるルールであることを特徴とする、請求項１記載の不正操作検知回路。
【請求項３】
前記状態値生成回路は、前記現在の状態値に対する前記複数の変化条件ルールに従った状態遷移後の状態値を生成するのに必要なデータを格納する複数の状態値テーブルを有し、
前記選択部は、前記複数の状態値テーブルを用いて生成された前記現在の状態値に対する状態遷移後の複数の状態値の１つを前記乱数入力に基づいて選択出力して前記状態値格納部及び前記状態値比較回路に入力するセレクタを有する
ことを特徴とする請求項１または２記載の不正操作検知回路。
【請求項４】
外部装置と通信して演算開始入力を受信する通信回路と、
プロセッサと、
不正操作検知回路
を備え、
前記不正操作検知回路は、
互いに異なる複数の、状態値の変化条件ルールを出力する変化条件ルール出力回路と、
前記複数の変化条件ルールに従って現在の状態値に対する状態遷移後の状態値を生成する状態値生成回路と、
前記複数の変化条件ルールに従って前記状態値生成回路で生成された状態遷移後の状態値のうち、任意の１つの変化条件ルールに従って生成された状態遷移後の状態値と、前記変化条件ルール出力回路から出力された前記複数の変化条件ルールのうち、前記任意の１つの変化条件ルールを、乱数に基づいて選択出力する選択部と、
前記演算開始入力に基づいて前記現在の状態値を格納すると共に、前記選択部から選択出力される前記状態遷移後の状態値を格納する状態値格納部と、
前記状態値格納部の入出力に基づき前記状態遷移後の状態値と前記現在の状態値を比較し、状態遷移が前記選択部から選択出力される前記任意の１つの変化条件ルールに従っていないと不正操作を検知して検知信号を前記プロセッサに出力する状態値比較回路
を備え、
前記複数の変化条件ルールは、同一固定ビット数の値変化を用いるルールである
ことを特徴とする装置。
【請求項５】
複数の変化条件ルールに従って状態値生成回路で現在の状態値に対する状態遷移後の状態値を生成し、任意の１つの変化条件ルールに従って生成された状態遷移後の状態値と、前記任意の１つの変化条件ルールを、乱数に基づいて選択部から選択出力するステップと、
演算開始入力に基づいて状態値格納部に前記現在の状態値を格納すると共に、前記選択部から選択出力される前記状態遷移後の状態値を格納するステップと、
前記状態値格納部の入出力に基づき前記状態遷移後の状態値と前記現在の状態値を状態値比較回路で比較し、状態遷移が前記任意の１つの変化条件ルールに従っていないと不正操作を検知して検知信号を出力するステップ
を不正操作検知回路で実行し、
前記複数の変化条件ルールは互いに異なり、且つ、同一固定ビット数の値変化を用いるルールである
ことを特徴とする不正操作検知方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法に関する。
【背景技術】
【０００２】
アルゴリズムの実行状態を状態（ステート）値により管理する装置の一例として、暗号機能を搭載したスマートカード（Smart Card）などが知られている。スマートカードは、チップカード（Chip Card）またはＩＣカード（ICC: Integrated Circuit Card）などと呼ばれることもある。暗号機能を搭載したスマートカードには、暗号回路内部の秘密鍵に対する攻撃を防ぐための耐タンパ技術が用いられているものがある。
【０００３】
暗号方式は共通鍵暗号方式と公開鍵暗号方式とに大別できる。共通鍵暗号方式は、暗号化と復号化で同一の秘密鍵を用いる方式であり、秘密鍵を送信者及び受信者以外の第三者にわからない秘密情報とすることで安全性を保つ。一方、公開鍵暗号方式は、暗号化と復号化で異なる鍵を用いる方式であり、暗号化を行うための公開鍵を一般に公開する代わりに、暗号文を復号するための秘密鍵を受信者のみの秘密情報とすることで安全性を保つ。
【０００４】
これらの暗号方式に対しては、秘密鍵を暗号文などの入手可能な情報から推定する様々な攻撃手法が存在する。これらの攻撃手法は、理論攻撃と実装攻撃とに大別できる。理論攻撃は、暗号アルゴリズムの入力データと出力データとの関係から秘密鍵を求める。理論攻撃は、攻撃対象となる暗号アルゴリズムの実装の形態に依存せず成功する可能性がある。一方、実装攻撃は、暗号アルゴリズムを実装した装置に対して、入力データと出力データの関係のみならず、装置に対して物理的なストレスを加えることで得られるエラー情報、入出力データ以外に装置から観測される情報などを利用することで秘密鍵を推定する。実装攻撃の成功の可否は、暗号アルゴリズムの実装形態に依存する。
【０００５】
暗号アルゴリズムが理論攻撃に対しては安全性を保てても、実装攻撃に対しては脆弱である場合があり、実装攻撃に対して安全性を保証できる暗号アルゴリズムが望まれている。実装攻撃に対する対策は、耐タンパ（Tamper-Proof）技術とも呼ばれる。
【０００６】
実装攻撃は、フォールト攻撃（Fault Attack）とサイドチャネル攻撃（Side Channel Attack）とに大別できる。フォールト攻撃は、スマートカードなどの装置に搭載された暗号回路の内部データ値に対して、意図的に異常を発生させた場合の暗号処理の出力結果と、正常な暗号処理の出力結果との差分情報を用いて、暗号回路の内部に格納されている秘密鍵を推定する。一方、サイドチャネル攻撃は、消費電力、電磁波、処理時間など、装置から漏洩する情報を用いて秘密鍵を推定する。サイドチャネル攻撃では、消費電力を用いた方法が最も良く知られており、電力解析攻撃（Power Analysis Attack）とも呼ばれる。電力解析攻撃は、装置の消費電力波形から秘密鍵を推定する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特表２００５−５０９９３６号公報
【特許文献２】特表２００９−５００７１０号公報
【特許文献３】特開２０１０−６８１３５号公報
【非特許文献】
【０００８】
【非特許文献１】Alfred J.Menezes et al., "HANDBOOK OF APPLIED CRYPTOGRAPHY"(CRC press), p.615, Algorithm 14.79 (http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf)
【非特許文献２】D. Boneh, R. A. DeMillo, R. J. Lipton, "On the Importance of Checking Cryptographic Protocols for Faults", Eurocrypt '97, pp.37-51, 1997
【非特許文献３】Benoit Feix and Louis Marcel, "Passive and Active Combined Attacks", 2007 Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2007
【非特許文献４】http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
【非特許文献５】Kouichi Itoh, Masahiko Takenaka, Naoya Torii, Syouji Temma, and Yasushi Kurihara,"Fast Implementation of Public-Key Cryptography on a DSP TMS320C6201", CHES '99, LNCS 1717, pp.61-72
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従来の暗号回路を備えた装置では、理論攻撃に対しては安全性を保てても、実装攻撃に対しては脆弱である場合がある。
【００１０】
そこで、本発明は、実装攻撃に対する耐タンパ性を向上可能な不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の一観点によれば、互いに異なる複数の、状態値の変化条件ルールを出力する変化条件ルール出力回路と、前記複数の変化条件ルールに従って現在の状態値に対する状態遷移後の状態値を生成する状態値生成回路と、前記複数の変化条件ルールに従って前記状態値生成回路で生成された状態遷移後の状態値のうち、任意の１つの変化条件ルールに従って生成された状態遷移後の状態値と、前記変化条件ルール出力回路から出力された前記複数の変化条件ルールのうち、前記任意の１つの変化条件ルールを、乱数に基づいて選択出力する選択部と、演算開始入力に基づいて前記現在の状態値を格納すると共に、前記選択部から選択出力される前記状態遷移後の状態値を格納する状態値格納部と、前記状態値格納部の入出力に基づき前記状態遷移後の状態値と前記現在の状態値を比較し、状態遷移が前記選択部から選択出力される前記任意の１つの変化条件ルールに従っていないと不正操作を検知して検知信号を出力する状態値比較回路を備え、前記複数の変化条件ルールは、同一固定ビット数の値変化を用いるルールであることを特徴とする不正操作検知回路が提供される。
【００１２】
本発明の一観点によれば、外部装置と通信して演算開始入力を受信する通信回路と、プロセッサと、不正操作検知回路を備え、前記不正操作検知回路は、互いに異なる複数の、状態値の変化条件ルールを出力する変化条件ルール出力回路と、前記複数の変化条件ルールに従って現在の状態値に対する状態遷移後の状態値を生成する状態値生成回路と、前記複数の変化条件ルールに従って前記状態値生成回路で生成された状態遷移後の状態値のうち、任意の１つの変化条件ルールに従って生成された状態遷移後の状態値と、前記変化条件ルール出力回路から出力された前記複数の変化条件ルールのうち、前記任意の１つの変化条件ルールを、乱数に基づいて選択出力する選択部と、前記演算開始入力に基づいて前記現在の状態値を格納すると共に、前記選択部から選択出力される前記状態遷移後の状態値を格納する状態値格納部と、前記状態値格納部の入出力に基づき前記状態遷移後の状態値と前記現在の状態値を比較し、状態遷移が前記選択部から選択出力される前記任意の１つの変化条件ルールに従っていないと不正操作を検知して検知信号を前記プロセッサに出力する状態値比較回路を備え、前記複数の変化条件ルールは、同一固定ビット数の値変化を用いるルールであることを特徴とする装置が提供される。
【００１３】
本発明の一観点によれば、複数の変化条件ルールに従って状態値生成回路で現在の状態値に対する状態遷移後の状態値を生成し、任意の１つの変化条件ルールに従って生成された状態遷移後の状態値と、前記任意の１つの変化条件ルールを、乱数に基づいて選択部から選択出力するステップと、演算開始入力に基づいて状態値格納部に前記現在の状態値を格納すると共に、前記選択部から選択出力される前記状態遷移後の状態値を格納するステップと、前記状態値格納部の入出力に基づき前記状態遷移後の状態値と前記現在の状態値を状態値比較回路で比較し、状態遷移が前記任意の１つの変化条件ルールに従っていないと不正操作を検知して検知信号を出力するステップを不正操作検知回路で実行し、前記複数の変化条件ルールは互いに異なり、且つ、同一固定ビット数の値変化を用いるルールであることを特徴とする不正操作検知方法。
【発明の効果】
【００１４】
開示の不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法によれば、実装攻撃に対する耐タンパ性を向上することが可能となる。
【図面の簡単な説明】
【００１５】
【図１】バイナリ法を用いた指数剰余演算のアルゴリズムを説明する図である。
【図２】バイナリ法の処理を説明する図である。
【図３】フォールト攻撃を説明する図である。
【図４】バイナリ法を用いるＲＳＡ暗号をベースとした電力解析への耐タンパ性を有するＲＳＡ暗号アルゴリズムを説明する図である。
【図５】図４のＲＳＡ暗号アルゴリズムを実装した装置におけるd=(10100...)2の場合の消費電力波形を示す図である。
【図６】フォールト攻撃による電力解析の対策機能を無効化する方法を説明する図である。
【図７】図６の状態値(0001)2をスキップしたＲＳＡ暗号アルゴリズムを実装した装置におけるd=(10100...)2の場合の消費電力波形を示す図である。
【図８】本発明の一実施例における不正操作検知回路の一例を示すブロック図である。
【図９】図８の不正操作検知回路においてサイドチャネルとして見える消費電力の動的変化の一例を示す図である。
【図１０】実施例における実装攻撃対策ハードウェアを搭載したスマートカードの一例の構成を示すブロック図である。
【図１１】実施例における不正操作検知方法の一例を説明するフローチャートである。
【図１２】実施例を共通鍵暗号方式へ適用した一例を説明する図である。
【図１３】実施例を公開鍵暗号方式へ適用した一例を説明する図である。
【図１４】ＮＯＰ挿入が必要な例を説明する図である。
【発明を実施するための形態】
【００１６】
開示の不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法では、状態値の変化条件ルールを変化条件ルール出力回路から出力し、複数の変化条件ルールに従って現在の状態値に対する状態遷移後の状態値を状態値生成回路で生成し、選択部から、複数の変化条件ルールに従って状態値生成回路で生成された状態遷移後の状態値のうち、１つの変化条件ルールに従って生成された状態遷移後の状態値と、変化条件ルール出力回路から出力された複数の変化条件ルールのうち、前記１つの変化条件ルールを、乱数に基づいて選択出力する。状態値格納部は、演算開始入力に基づいて現在の状態値を格納すると共に、選択部から選択出力される状態遷移後の状態値を格納する。状態値比較回路は、状態値格納部の入出力に基づき状態遷移後の状態値と現在の状態値を比較し、状態遷移が選択部から選択出力される前記１つの変化条件ルールに従っていないと不正操作を検知して検知信号を出力する。複数の変化条件ルールは、互いに異なるが、同一固定ビット数の値変化を用いるルールである。
【００１７】
以下に、開示の不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法の各実施例を図面と共に説明する。
【実施例】
【００１８】
先ず、ＲＳＡ暗号について説明する。ＲＳＡ暗号の復号処理では、指数剰余演算が行われる。指数剰余演算は、秘密鍵d、暗号文a、法nに対して、v=ad (mod n)により平文vを計算する。一般的に、ＲＳＡ暗号における秘密鍵dのビット長は、1024bit以上である。このため、d乗演算は単純な方法で実行すると、約21024回の乗算が必要となり、現実的な時間内に計算を完了することは難しい。
【００１９】
このd乗演算を効率的に行うためのアルゴリズムとしては、バイナリ法が知られている（例えば、非特許文献１参照）。バイナリ法を用いることで、d乗演算に必要な演算回数は、21024回から1024の定数倍（この定数は1.5以下の値）になり、効率的な演算を実現できる。
【００２０】
秘密鍵dをu-bit値とし、その2進表現をd=(du-1,du-2,...,d0)2と表記する。ただし、diはdの個々のビット値を表す。図１は、バイナリ法を用いた指数剰余演算のアルゴリズムを説明する図であり、図２は、バイナリ法の処理を説明する図である。図１のアルゴリズムでは、秘密鍵dのビット値diを、i=u-1からi=0の順番にチェックする。このチェックの結果がdi=1であると、２乗算と乗算の両方が実行される。チェックの結果がdi=0であると、２乗算のみが実行される。このような処理をi=u-1からi=0まで繰り返すことにより、バイナリ法はv=ad(mod n)を計算する。つまり、バイナリ法では、秘密鍵dのビットdiの値と、２乗算、乗算の実行パターンとが直接的に連動している。
【００２１】
図３はフォールト攻撃を説明する図である。特にレーザを用いたストレス印加法は、１ビット（以下、1-bitと言う）単位で正確にフォールトを発生させることができ、攻撃者が意図した通りのフォールトを発生させることができてしまう。代表的なフォールト攻撃は、例えば非特許文献２に記載されている。説明の便宜上、ＲＳＡ暗号に対するフォールト攻撃の概略について説明する。
【００２２】
ＲＳＡ暗号は、素数p, qに対しn=p×qを満たす合成数nを用いる。ＲＳＡ暗号の安全性は、素因数分解によりnから素数p, qを得ることが困難であるという仮定に基づいている。ただし、p, qは512-bit以上、nは1024-bit以上の大きな整数である。つまり、攻撃者が合成数nから素数p, qを得ることに成功してしまうと、ＲＳＡ暗号は解読されてしまう。
【００２３】
ＲＳＡ暗号に対するフォールト攻撃の目的は、素数pを得ることである。素数pを得ることができれば、割り算によりqも簡単に求めることができるので、p, qのいずれかを攻撃者が得ることができれば、ＲＳＡ暗号は解読されてしまう。
【００２４】
ＲＳＡ暗号に対するフォールト攻撃は、正常な出力値と、フォールトを発生させた場合の異常な出力値との２つを用いることで、pを解読する。攻撃者は、正常な出力値を得た後、後述の(mod q)のべき乗剰余計算における計算処理を実行している最中にフォールトを発生させる。
【００２５】
この結果、正常な処理の場合 mq=cqdq (mod q)を得るのに対し、フォールト発生の場合は計算値が異常な値となり、m'q≠mqを満たすm'qを得る（m'qの値は、mqと等しくなければどのような値でも攻撃が成功する）。このm'qを用いて最終的に計算された結果、攻撃者は出力m'を得る。攻撃者は、正常な出力mとフォールト発生時の出力m'を用いて、GCD(m' - n, n)を計算することで、p=GCD(m' - m, n)を得る。ただし、GCD(a,b)は整数a,bの最大公約数を計算する関数である。
【００２６】
この攻撃が成立する理由は、異常なm'qを用いて後述するm'の計算を行うことで、正しいmの値とm'の値との差分がpの整数倍、即ち、整数kに対してm' -m = kpとなるからであり、その結果、CD(m' - m, n)=GCD(kp, pq) = pを得られてしまう。
【００２７】
入力：c (暗号文)
dp  (秘密鍵dに対し、dp=d mod (p-1)を満たす秘密鍵)
dq  (秘密鍵dに対し、dq=d mod (q-1)を満たす秘密鍵)
p  (n=p×qを満たす素数p)
q  (n=p×qを満たす素数q)
u  (u= q-1 (mod p)を満たす整数)
出力：m   (平文)
ただし、eは暗号化用の公開鍵、 dは復号用秘密鍵であり、ed=1 mod (p-1)(q-1)を満たす。
【００２８】
＊正常な処理
1. cp= c mod p, cq = c mod q 
2. mp=cpdp (mod p)を計算
3. mq=cqdq (mod q)を計算
4. m = ( (mq - mp)×u (mod q) )×p + mp を計算
5. mを出力
＊Fault発生時の処理
1. cp= c mod p, cq = c mod q 
2. mp=cpdp (mod p)
3. mq=cqdq (mod q)計算中にfault発生、mqの代わりにm'q出力(mq'≠mq)
4. m = ( (m'q - mp)×u (mod q) )×p + mp を計算
5. m'を出力
上記の如きフォールト攻撃は、正常な出力値とフォールト発生時の出力値を比較することにより、ＲＳＡ暗号を解読するための秘密鍵である素数pを得る。ここでは説明の便宜上、フォールト発生時の電力波形を観察することで秘密鍵dを得るフォールト攻撃について説明する。
【００２９】
図４はバイナリ法を用いるＲＳＡ暗号をベースとした電力解析への耐タンパ性を有するＲＳＡ暗号アルゴリズムを説明する図である。図４の左側に記してある4ビット値１はＲＳＡ暗号アルゴリズムの実行状態を表す値であり、以下では「状態値」と呼ぶ。図４のＲＳＡ暗号アルゴリズムにおいては、(0000)2, (0001)2, ...., (1001)2が状態値である。図４のＲＳＡ暗号処理に限らず、状態値は、暗号処理を実行する装置において演算の実行状態を管理するために用いられる。
【００３０】
図４のＲＳＡ暗号アルゴリズムは、入力された暗号文c、秘密鍵d=(du-1,du-2,...,d0)2、法nから、平文m=cd (mod n)を計算し、電力解析により秘密鍵dが漏洩することを防ぐ耐タンパ機能（または、耐タンパ性）を有する。この耐タンパ機能について、図５を用いて説明する。
【００３１】
図５は、図４のＲＳＡ暗号アルゴリズムを実装した装置におけるd=(10100...)2の場合の消費電力波形を示す図である。図５は、d=(du-1,du-2,...,d0)2に対して、以下の処理をi=u-1,...,1,0の夫々について繰り替えし実行した場合の波形である。
【００３２】
di=1： R0=R0×R0で示される２乗算の後に、R0=R0×R1で示される乗算が実行される。
【００３３】
di=0： R0=R0×R0で示される２乗算が実行される。
【００３４】
つまり、図５ではdiのビット値に応じて、R0=R0×R0とR0=R0×R1との２種類の乗算が実行されている。仮に、これらの乗算の種類を消費電力波形により識別することが可能であると、diのビット値を判別でき、秘密鍵dを解読されてしまう。しかし、図４のＲＳＡ暗号アルゴリズムに対しては、上記のような識別は困難である。これは、R0,R1は図４の状態値(0001)2,(0010)2に記されている通り、初期値を乱数r1, r2により与えられ更新される常にランダムな値であるからである。
【００３５】
つまり、R0=R0×R0とR0=R0×R1との２種類の乗算は、いずれも(乱数)×(乱数)の乗算であり、このような乱数データ同士の乗算は、図５に示すように、消費電力波形で識別するのは困難である。このように、図４のＲＳＡ暗号アルゴリズムに対する電力解析は困難である。従って、図４のＲＳＡ暗号アルゴリズムを実行する装置は、電力解析に対して安全である。
【００３６】
図４のＲＳＡ暗号アルゴリズムに対して、フォールト攻撃を行うことで、電力解析に対する耐性を無効化できる攻撃法も存在する（例えば、非特許文献３参照）。ＲＳＡ暗号アルゴリズムに対して、フォールト攻撃を行うことで、電力解析に対する耐性を無効化できる攻撃法では、フォールト攻撃を行うことで、状態値の一部を強制的に変更し、電力解析への対策機能に必要となる処理をスキップし、対策機能を無効化させる。
【００３７】
図６は、フォールト攻撃による電力解析の対策機能を無効化する方法を説明する図である。図６に示すように、実行状態は基本的に状態値の状態遷移により管理される。正常な処理においては、この状態値は(0000)2→(0001)2→(0010)2→(0011)2...のように、１つずつ増加しながら遷移するので、図６に示す順番でＲＳＡ暗号アルゴリズムの処理が行われる。
【００３８】
図６に示したＲＳＡ暗号アルゴリズムの処理に対し、フォールト攻撃は状態値の値を強制的に変更することで、例えば(0000)2→ (0010)2→(0011)2...のように、一部の状態値（図６の例では(0001)2）を強制的にスキップさせる。このような精度の高いフォールト発生は、レーザを用いたストレス印加方法により実現できる。このように図６のＲＳＡ暗号アルゴリズムの処理に対し、フォールト攻撃により状態値(0001)2を強制的にスキップすることで、R0への乱数の書込み処理がスキップされるため、R0の値は初期値0となる。
【００３９】
図４及び図６のＲＳＡ暗号アルゴリズムにおいては、R0への乱数書込みが耐タンパ機能を保障する重要な条件であり、この処理がスキップされることで耐タンパ機能が無効化されてしまう。このような処理のスキップの結果、R0の値が0となった場合の消費電力波形を図７に示す。図７は、図６の状態値(0001)2をスキップしたＲＳＡ暗号アルゴリズムを実装した装置におけるd=(10100...)2の場合の消費電力波形を示す図である。
【００４０】
図７の例では、R0=R0×R0とR0=R0×R1の２種類の乗算が発生している。図５の消費電力波形においては、これら２種類の乗算は共に(乱数)×(乱数)である。しかし、図７の消費電力波形においては、フォールト発生によりR0の値がゼロであるので、夫々以下の乗算となる。
【００４１】
R0×R0：０×０
R0×R1：０×（乱数）
つまり、R0×R0は入力の両方がゼロである乗算である。R0×R1は入力の片方がゼロである乗算である。乗算の性質上、０を入力とする乗算の消費電力波形は、特殊な形状になることが知られている。このような特殊な波形は、０の入力が１個か、２個かに応じてさらに変化する場合がある。つまり、０の入力が１個である波形と、２個である波形は夫々に特徴がある。従って、図７に示すようにR0×R0の乗算とR0×R1の乗算とは、消費電力波形の形状によって識別できてしまう。これらの消費電力波形を識別することで、そのままdのビット値を識別できるので、図７の消費電力波形からは秘密鍵dをd=(10100..)2と解読されてしまう。
【００４２】
ＲＳＡ暗号アルゴリズムに対してフォールト攻撃を行うことで電力解析に対する耐性を無効化できる攻撃法を防ぐための対策技術は、従来から提案されている（例えば、特許文献１参照）。この対策技術は、回路の内部状態をチェックし、フォールト発生の有無の検知を行うフォールト検知による対策法である。フォールト検知を用いることで、フォールトが発生した場合でも、暗号装置の処理停止やデータ出力停止など、適切な防御方法を実施することができる。
【００４３】
従来のフォールト検知は、暗号装置の外側に状態値の外付けのカウンタを設置し、状態値の状態遷移が進む毎に、このカウンタを増加させ、このカウンタの値が期待通りの値であるかのチェックを定期的に行うことで、状態値の状態遷移が正しいかどうかのチェックを行う。つまり、従来のフォールト検知は、状態値の状態遷移が正しく行われているかどうかを、外付けのカウンタを用いて間接的にチェックする。しかし、このようなフォールト検知法では、基本的なフォールト攻撃を検知できるものの、より高度なフォールト攻撃が行われた場合、フォールト検知機能が無効化されてしまう。つまり、このようなフォールト検知法は、フォールト検知にリアルタイム性がないため、フォールトを１回発生させるフォールト攻撃に対しては有効であるが、フォールトを２回発生させるフォールト攻撃に対しては無効である。
【００４４】
そこで、状態値の状態遷移とフォールト検知を一体化することで、全ての状態遷移に関してフォールト検知を有効とし、フォールト検知のリアルタイム性を保障する不正操作検知回路が提案されている（例えば、特許文献３参照）。この提案されている不正操作検知回路では、状態値の変化条件ルールを複数準備し、どの変化条件ルールを用いるかを不正操作検知回路の内部で発生させた乱数によって選択することで、攻撃者がフォールト検知漏れとなる状態値のスキップのパターンを特定できないようにして、安全性を向上する。３種類の変化条件ルールを用いる場合、第１、第２、及び第３変化条件ルールは互いに異なるビット数を有し、夫々例えば１ビット、２ビット、及び３ビットである。この提案されている不正操作検知回路によれば、変化条件ルールに適合しない状態遷移を検出すると、フォールト検知信号が出力されるので、フォールト攻撃に対しては有効である。しかし、フォールト検知信号をゲイン毎に分類すると、フォールト検知信号のゲインの例えば最大値が同じ変化条件ルール内では変化しないものの、異なる変化条件ルール間では大きく変化するので、この変化に基づいて変化条件ルールが解読されてしまう可能性がある。つまり、この提案されている不正操作検知回路は、フォールト攻撃に対する耐タンパ技術であり、サイドチャネルとして見える不正操作検知回路の消費電力の動的変化の解析から変化条件ルールが解読されるサイドチャネル攻撃には脆弱である。
【００４５】
図８は、本発明の一実施例における不正操作検知回路の一例を示すブロック図である。
図８に示す不正操作検知回路３０は、状態値テーブル１１Ａ〜１１Ｃを有する状態値生成回路１１、状態値レジスタ１２、変化条件ルール出力回路１３Ａ〜１３Ｃ、状態値比較回路１４、セレクタ１５、及びセレクタ１６を有する。不正操作検知回路３０は、フォールト検知回路の機能を備えたステートマシン（State Machine）の一例である。
【００４６】
状態値レジスタ１２は、外部からの演算開始入力に基づいて、現在の状態値を格納する状態値格納部を形成する。状態値生成回路１１は、状態値テーブル１１Ａ〜１１Ｃを用いて、状態値レジスタ１２が格納している現在の状態値、即ち、状態値レジスタ１２の出力に基づいて状態遷移後の状態値を決定する。変化条件ルール出力回路１３Ａ〜１３Ｃは、フォールト攻撃が無い場合の正常な処理時における状態値の変化条件ルールType-A〜Type-Cを定める。変化条件ルールType-A, Type-B, Type-Cは、互いに異なるルールである。状態値比較回路１４は、状態値の状態遷移が正常であるか否かを判断し、状態値の状態遷移の異常からフォールト攻撃を検知するとフォールト検知信号を出力する。セレクタ１５は、状態値生成回路１１の状態値テーブル１１Ａ〜１１Ｃを用いて生成された現在の状態値に対する状態遷移後の３つの状態値の１つを、外部からの乱数入力に基づいて選択出力して状態値レジスタ１２及び状態値比較回路１４に入力する。状態値テーブル１１Ａ〜１１Ｃは、夫々現在の状態値に対する変化条件ルールType-A〜Type-Cに従った状態遷移後の状態値を生成するのに必要なデータ（即ち、変化条件ルールType-A〜Type-Cのデータ）を格納する。また、セレクタ１６は、変化条件ルール出力回路１３Ａ〜１３Ｃのうち１つの出力を、外部からの乱数入力に基づいて選択出力して状態値比較回路１４に入力する。なお、乱数は、不正操作検知回路３０内で発生しても良いことは言うまでもない。
【００４７】
セレクタ１５及びセレクタ１６は、乱数入力に基づいて連動している選択部を形成する。選択部は、変化条件ルールType-Aに従った状態値テーブル１１Ａを用いて生成された状態遷移後の状態値の出力が選択されるとき変化条件ルール出力回路１３Ａの変化条件ルールType-Aの出力が選択され、変化条件ルールType-Bに従った状態値テーブル１１Ｂを用いて生成された状態遷移後の状態値の出力が選択されるとき変化条件ルール出力回路１３Ｂの変化条件ルールType-Bの出力が選択され、変化条件ルールType-Cに従った状態値テーブル１１Ｃを用いて生成された状態遷移後の状態値の出力が選択されるとき変化条件ルール出力回路１３Ｃの変化条件ルールType-Cの出力が選択されるように動作する。
【００４８】
状態値比較回路１４は、状態値レジスタ１２の入力（即ち、現在の状態値）と出力（即ち、状態値生成回路１１で生成された現在の状態値に対する状態遷移後の状態値）を比較することで、セレクタ１６から出力される変化条件ルール（状態値生成回路１１で用いた変化条件ルールと同じ）に基づいてフォールト発生の有無を検知する。具体的には、状態値比較回路１４は、状態値レジスタ１２の入力と出力との関係が、セレクタ１６から出力される変化条件ルールに従っているか否かに基づいて、フォールト発生の有無を検知する。
【００４９】
状態値比較回路１４は、状態値レジスタ１２の入力と出力との関係が、セレクタ１６を介して与えられる変化条件ルールに従っている場合、フォールト発生の無い正常な処理であると判断する。一方、状態値レジスタ１２の入力と出力との関係が、セレクタ１６を介して与えられる変化条件ルールに従っていない場合、状態値比較回路１４はフォールトの発生した異常な処理であると判断してフォールト検知信号を出力する。
【００５０】
なお、セレクタ１５による状態値生成回路１１の状態値テーブル１１Ａ〜１１Ｃの何れか１つを用いて生成された状態値の出力を選択する処理と、セレクタ１６による変化条件ルール出力回路１３Ａ〜１３Ｃの何れか１つの出力を選択する処理とは、不正操作検知回路３０が動作する最初の演算開始入力による初期化処理で決定する。
【００５１】
図８に示す例では、変化条件ルール出力回路１３Ａの与える変化条件ルールが1-bit値変化のType-Aであり、変化条件ルール出力回路１３Ｂの与える変化条件ルールが1-bit値変化のType-Bであり、変化条件ルール出力回路１３Ｃの与える変化条件ルールが1-bit値変化のType-Cである。また、不正操作検知回路３０では、状態値テーブル１１Ａが変化条件ルールType-Aに基づいて遷移後の状態値を決定し、状態値テーブル１１Ｂが変化条件ルールType-Bに基づいて遷移後の状態値を決定し、状態値テーブル１１Ｃが変化条件ルールType-Cに基づいて遷移後の状態値を決定する。
【００５２】
なお、状態値のビット変化の確率が「１／３」であるということは、サイドチャネルとして見える不正操作検知回路３０の消費電力の動的変化の確率が「１」から「１／３」であることを意味する。図９は、図８の不正操作検知回路３０においてサイドチャネルとして見える消費電力の動的変化の一例を示す図である。図９中、縦軸は不正操作検知回路３０の消費電力を任意単位で示し、横軸は時間を任意単位で示す。この例では、変化条件ルール出力回路１３Ａの与える変化条件ルールが消費電力波形２６Ａの1-bit値変化のType-Aであり、変化条件ルール出力回路１３Ｂの与える変化条件ルールが消費電力波形２６Ｂの1-bit値変化のType-Bであり、変化条件ルール出力回路１３Ｃの与える変化条件ルールが消費電力波形２６Ｃの1-bit値変化のType-Cである。図９からもわかるように、不正操作検知回路３０の消費電力の動的変化（例えば、最大値の変化）は、互いに異なる変化条件ルール出力回路１３Ａ〜１３Ｃを用いていても、消費電力波形２６Ａ，２６Ｂ，２６Ｃから確認できないことがわかる。
【００５３】
不正操作検知回路３０は、３つの状態値テーブル１１Ａ〜１１Ｃを用いて現在の状態値に対する状態遷移後の３つの状態値を生成する状態値生成回路１１と、３つの変化条件ルール出力回路１３Ａ〜１３Ｃを備えるが、３つの変化条件ルールType-A〜Type-Cの中から乱数に基づいて選択される１つの変化条件ルールは、常に同一固定ビット数の値変化（この例では、1-bit値変化）である。このため、不正操作検知回路３０におけるビット値変化の確率「１」を最大「１／３」に下げることができる。
【００５４】
なお、図８の不正操作検知回路３０では、互いに異なる変化条件ルールの数が３つであるが、互いに異なる変化条件ルールの数は複数であれば特に限定されない。また、互いに異なる変化条件ルールは、同一固定ビット数の値変化を用いるルールであれば良く、1-bit値変化を用いるルールに限定されない。なお、1-bit値変化を用いる変化条件ルールを使用する場合、2-bit以上の値変化を用いる変化条件ルールを使用する場合と比べて回路構成が比較的簡単になり、且つ、消費電力を比較的低く抑えることができる。
【００５５】
図８の不正操作検知回路３０によれば、攻撃者は何回もフォールト攻撃を繰り返し試すような攻撃を行っても、秘密鍵を解読することができない。不正操作検知回路３０は、既知の攻撃に対して状態値のビット変化の確率「１」で防御を行い、さらに未知の攻撃（または、進化した攻撃）に対しても状態値のビット変化の確率「１」から「１／３」で防御することで、秘密鍵の漏洩を防止できる。この状態値のビット変化の確率は、使用する変化条件ルールの数を多くするほど「１」に近づけることができ、攻撃に対してより安全となる。
【００５６】
図１０は、本実施例における実装攻撃対策ハードウェアを搭載したスマートカードの一例の構成を示すブロック図である。スマートカード１００は、不正操作検知回路を備えた装置の一例である。図１０に示すスマートカード１００は、プロセッサの一例であるＣＰＵ（Central Processing Unit）１０１、記憶部の一例であるＲＯＭ（Read Only Memory）１０２、通信回路１０３、外部インターフェース回路１０４、実装攻撃対策ハードウェアの一例である不正操作検知回路１０５、記憶部の一例であるＲＡＭ（Random Access Memory）１０６、クロック生成回路１０７、電源回路１０８、及びバス１０９を有する。バス１０９は、ＣＰＵ１０１、ＲＯＭ１０２、通信回路１０３、不正操作検知回路１０５、及びＲＡＭ１０６を接続する。
【００５７】
ＣＰＵ１０１は、スマートカード１００全体の制御を司り、この例では周知の方法で乱数を発生する機能を有する。ＲＯＭ１０２は、ＣＰＵ１０１が実行するプログラム及び各種データを格納する。通信回路１０３は、外部インターフェース回路１０４を介して外部装置（図示せず）と有線及び無線の少なくとも一方の通信方式で通信し、例えば外部装置から演算開始入力を含む各種要求などを受信する。
【００５８】
なお、乱数は、不正操作検知回路１０５内で発生しても、スマートカード１００内のＣＰＵ１０１及び不正操作検知回路１０５以外の回路部で発生しても、スマートカード１００外で発生して不正操作検知回路１０５に入力しても良い。
【００５９】
図１０中、不正操作検知回路１０５は、図８に示す不正操作検知回路３０に相当する。図８に示す乱数入力は、例えばＣＰＵ１０１から不正操作検知回路１０５に入力され、図８に示す演算開始入力は、例えば通信回路１０３から不正操作検知回路１０５に入力される。演算開始入力は、例えば通信回路１０３からＣＰＵ１０１を介して不正操作検知回路１０５に入力されても良い。不正操作検知回路１０５は、上記の如き不正操作を検知すると、バス１０９経由でＣＰＵ１０１にフォールト検知信号（または、割り込み信号）を出力する。ＣＰＵ１０１は、フォールト検知信号を受信すると、秘密鍵データ消去処理、暗号装置の利用停止処理などを実行して、攻撃者がその後さらに実装攻撃をしても成功しないような適切な対策を取る。このような適切な対策には、周知の対策を採用可能である。
【００６０】
不正操作検知回路１０５は、ＲＳＡ暗号アルゴリズム、ＡＥＳ（Advanced Encryption Standard）暗号アルゴリズムなどの、任意の暗号アルゴリズムに対するフォールト攻撃及びサイドチャネル攻撃により、秘密鍵が攻撃者により推定されることを防ぐ。スマートカード１００は、不正操作検知回路１０５を備えることで、高い耐タンパ性を実現することができる。
【００６１】
ＲＡＭ１０６は、ＣＰＵ１０１が実行する演算の中間データを含む各種データを一時的に格納し、ＣＰＵ１０１のワークエリアを提供する。クロック生成回路１０７は、図１０に破線で示すように、スマートカード１００内のクロックを必要とする各部に供給するクロックを生成する。この例では、クロックはＣＰＵ１０１、ＲＯＭ１０２、通信回路１０３、外部インターフェース回路１０４、不正操作検知回路１０５、及びＲＡＭ１０６に供給される。クロック生成回路１０７は、外部装置から外部インターフェース回路１０４を介して供給される信号、クロックなどに基づいてクロックを生成する構成であっても良い。電源回路１０８は、スマートカード１００内の電源電圧を必要とする各部に電源電圧を供給する。電源回路１０８は、外部装置から外部インターフェース回路１０４を介して供給される信号に基づいて電源電圧を出力する構成であっても良い。スマートカード１００が例えば非接触ＩＣカードの場合、電源回路１０８は外部インターフェース回路１０４のアンテナで受信した、カードリーダ／ライタなどの外部装置が発生した電波を電力に変換して電源電圧を出力する構成であっても良い。また、外部インターフェース回路１０４は、端子を含む構成であっても良い。なお、図１０では説明の便宜上、電源回路１０８が供給する電源電圧の電源供給線の図示は省略する。
【００６２】
次に、本実施例における不正操作検知方法の一例を、図１１と共に説明する。図１１は、本実施例における不正操作検知方法の一例を説明するフローチャートである。図１１において、ステップＳ１で不正操作検知回路３０（または、不正操作検知回路１０５）の不正操作検知処理が開始されると、ステップＳ２では通信回路１０３からの演算開始入力を読込んで暗号処理を開始する。ステップＳ２の後、ステップＳ３ではフォールト検知及び攻撃対策処理を行う。ステップＳ３は、ステップＳ３１〜Ｓ３８を含む。
【００６３】
ステップＳ３１では、ＣＰＵ１０１からの乱数入力を読込む。ステップＳ３２では、乱数入力に基づいて変化条件ルールType-A〜Type-Cのいずれか１つの変化条件ルールが選択され、セレクタ１５，１６の出力が選択された変化条件ルールに応じて選択される。これにより、変化条件ルールType-Aが選択されると、ステップＳ３３Ａでは現在の状態値に対する状態遷移後の状態値を状態値テーブル１１Ａに基づいて決定（または、生成）する。変化条件ルールType-Bが選択されると、ステップＳ３３Ｂでは現在の状態値に対する状態遷移後の状態値を状態値テーブル１１Ｂに基づいて決定する。変化条件ルールType-Cが選択されると、ステップＳ３３Ｃでは現在の状態値に対する状態遷移後の状態値を状態値テーブル１１Ｃに基づいて決定する。セレクタ１５で選択された状態値生成回路１１の出力は状態値レジスタ１２に入力され、セレクタ１６で選択された変化条件ルール出力回路１３Ａ〜１３Ｃの何れか１つで定めた変化条件ルールが状態値比較回路１４に入力される。
【００６４】
ステップＳ３４では、セレクタ１５から出力された遷移後の状態値を次の状態値として状態値レジスタ１２に書込む。ステップＳ３５では、状態値比較回路１４が状態値レジスタ１２の入力（即ち、現在の状態値）をセレクタ１６から入力される変化条件ルールに従った暗号演算により１ステートの演算を行う。ステップＳ３６では、状態値比較回路１４が状態値レジスタ１２の入力（即ち、現在の状態値）と出力（即ち、状態値生成回路１１で生成された現在の状態値に対する状態遷移後の状態値）を比較することで、状態値レジスタ１２の入力と出力との関係が、セレクタ１６から出力される変化条件ルールに従った1-bitであるか否かを判定する。ステップＳ３６の判定結果がＮＯであると、ステップＳ３７では、状態値比較回路１４がフォールト発生を検知してフォールト検知信号を出力する。
【００６５】
一方、ステップＳ３６の判定結果がＹＥＳであると、ステップＳ３８では、状態値レジスタ１２に書き込まれた次の状態値を次の現在の状態値として書き込む。ステップＳ３９では、暗号演算による演算を終了するか否かを判定し、判定結果がＮＯであると所定はステップＳ３４へ戻る。ステップＳ３９の判定結果がＹＥＳであると、ステップＳ４では、１つの変化条件ルールについて、予め設定されている演算回数分の演算が終了したか否かを判定し、判定結果がＮＯであると処理はステップＳ３１へ戻る。ステップＳ４の判定結果がＹＥＳであると、ステップＳ５では処理が正常終了する。
【００６６】
図１２は、上記実施例を共通鍵暗号方式へ適用した一例を説明する図である。代表的な共通鍵暗号アルゴリズムは、ＡＥＳ（Advanced Encryption Standard）が、米国連邦標準（ＦＩＰＳ：Federal Information Standards）FIPS 197として公開している（例えば、非特許文献４参照）。
【００６７】
図１２は、非特許文献４の第15頁、Figure 5に記されたＡＥＳ暗号化処理に対して不正操作検知回路３０（または、１０５）を用いた場合の状態値の状態遷移を示す。図１２では、１３個の状態値を4-bitで表現している。状態値の変化条件ルールは、1-bit値変化であるため、正常な状態遷移である限り、状態値は常に1-bit変化を行う。
【００６８】
この例においても、不正操作検知回路３０の状態値比較回路１４は、状態値の状態遷移前と状態遷移後の値を比較し、セレクタ１６で選択された変化条件ルールに従った1-bit値の変化であればフォールト発生が無いと判定し、それ以外の変化であればフォールトが発生したと判定してフォールト信号を出力する。
【００６９】
図１３は、上記実施例を公開鍵暗号方式へ適用した一例を説明する図である。代表的な公開鍵暗号アルゴリズムとしては、ＲＳＡ暗号が知られている。ＲＳＡ暗号は、乗算剰余演算を繰り返すことで処理を行う公開鍵暗号である。ＲＳＡ暗号は、乗算剰余を効率的に実行するための方法として、整数A,B、法Nに対してREDC(A,B,N)=A×B×R-1 (mod N)を計算するモンゴメリ（Montgomery）乗算剰余という方法が一般的に知られている。ここで、RはNのビット長xに対して、R=2xで与えられる定数である。Montgomery乗算剰余の処理アルゴリズムとしては、様々な方法が知られている（例えば、非特許文献５参照）。
【００７０】
図１３は、非特許文献５の第65頁、Algorithm 4に記されたMontgomery乗算剰余に対して不正操作検知回路３０（または、１０５）を用いた場合の状態値の状態遷移を示す。図１３では、w-bit単位の変数をg個並べることで、ＲＳＡ暗号で用いられる1024-bit以上の数値を表現している。wは、一般的にw=16,32,64など、1024より小さな値である。w-bitの部分乗算を繰り返すことで、1024-bit以上の乗算剰余演算を行う。図１３では１７個の状態値を5-bitで表現している。状態値の変化条件ルールは、1-bit値変化であるため、正常な状態遷移である限り、状態値は常に1-bit変化を行う。
【００７１】
この例においても、不正操作検知回路３０の状態値比較回路１４は、状態値の状態遷移前と状態遷移後の値を比較し、セレクタ１６で選択された変化条件ルールに従った1-bit値の変化であればフォールト発生が無いと判定し、それ以外の変化であればフォールトが発生したと判定してフォールト信号を出力する。
【００７２】
図１２の例は、共通鍵暗号方式の適用例であり、条件分岐のパターンは、for文による１重ループと非常に簡潔な構造である。これに対し、図１３の示す公開鍵暗号方式の適用例においては条件分岐のパターンがより複雑となり、for文による２重ループと、if文による条件分岐とが組み合わさっている。条件分岐のパターンが複雑化することで、状態値の状態遷移パターンの構築はより困難となる。
【００７３】
この状態遷移パターンの困難さを解決するためには、補助的な手段が必要となるが、図１３の例ではその１つであるＮＯＰ（No OPeration）状態の挿入を条件分岐((11001)2-(10001)2の状態値)において用いている。ＮＯＰとは、何も処理を行わない状態を指す。ＮＯＰは何も処理を行わないため、冗長な処理であるが、状態値の状態遷移条件の制約下において、遷移パターンを構築するために用いることができる補助的な手段である。
【００７４】
図１４は、状態値の状態遷移条件が1-bit値変化である場合において、このＮＯＰ挿入が必要な例を説明する図である。状態値の変化条件ルールが1-bit値変化の場合は、状態値A,B,Cを用いて以下の処理を行う場合、状態値BとCとの間にＮＯＰを挿入する必要がある。
【００７５】
A  if (cond) then {
B    処理1}
C  処理2
変化条件ルールを1-bit値変化とした場合には、状態値A→B→Cの状態遷移を行うことを考える。状態値Aに含まれる「１」の個数をｋで表すと、変化条件ルールの制約により、状態値Bでは「１」の個数が１つ増えるか、減るかのいずれであるので、k-1あるいはk+1となる。同様に、状態値Bから状態値Cに遷移する場合は、「１」の個数はk-2、k、あるいはk+2となる。
【００７６】
以上により、変化条件ルールを1-bit値変化とした場合には、状態値A→B→Cの状態遷移を実現することができる。しかし、図１４（ａ）に示すように、A→Cの状態遷移を行う場合は、「１」の個数がk個からk-2, k, k+2となる。つまり、A→Cの状態遷移を行う場合はkの値に関係なく、状態値が2-bit値変化するか、0-bit値変化するかのいずれかでしかなく、1-bit値変化を実現できない。
【００７７】
そこで、例えばA→Cの状態遷移を行う場合でも1-bit値変化を実現するために、変化条件ルールを1-bit値変化とした場合には、図１４（ｂ）に示すように状態値BとCとの間にＮＯＰを挿入した以下の処理を行う。
【００７８】
A  if (cond) then {
B    処理1
C    NOP }
D  処理2
状態値BとCとの間にＮＯＰを挿入したことで、変化条件ルールを1-bit値変化とした場合には、状態値A→B→C→Dの状態遷移において、状態値CからDに遷移したときの「１」の個数を、k-1あるいはk+1とすることができる。このとき、状態値A→Dの状態遷移は1-bit値変化となる。つまり、状態値A→B→C→Dの状態遷移と、状態値A→Dの状態遷移とは、両方とも1-bit値変化という制約において実現することができる。
【００７９】
このように、ＮＯＰの挿入を含めた、状態値の状態遷移パターンの構築に利用できる補助的な手段を以下に説明する。なお、図１４は条件分岐に関する例を示すが、ループ分岐に対しても応用可能である。
【００８０】
例えば、状態値のビット長を拡大することで、状態値の選択の自由度が広がり、状態値の状態遷移パターンの構築が容易となる。例えば１５個の状態値が与えられている場合、それを表現するための最小のビット長は4-bitであるが、この4-bitより大きなビット長で１５個の状態値を表現することで、状態値の状態遷移パターンの構築が容易となる。
【００８１】
また、１重ループ、２重ループ、条件分岐など、基本的なフロー制御の種類に応じて状態値の構築のためのテンプレートを事前計算しておき、そのテンプレートを利用して状態値の構築を行うようにしても良い。この場合、ループ中の状態数、条件分岐の状態数に応じて多様なテンプレートを作成することで、様々な処理に対応できる。
【００８２】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
（付記１）
互いに異なる複数の、状態値の変化条件ルールを出力する変化条件ルール出力回路と、
前記複数の変化条件ルールに従って現在の状態値に対する状態遷移後の状態値を生成する状態値生成回路と、
前記複数の変化条件ルールに従って前記状態値生成回路で生成された状態遷移後の状態値のうち、任意の１つの変化条件ルールに従って生成された状態遷移後の状態値と、前記変化条件ルール出力回路から出力された前記複数の変化条件ルールのうち、前記任意の１つの変化条件ルールを、乱数に基づいて選択出力する選択部と、
演算開始入力に基づいて前記現在の状態値を格納すると共に、前記選択部から選択出力される前記状態遷移後の状態値を格納する状態値格納部と、
前記状態値格納部の入出力に基づき前記状態遷移後の状態値と前記現在の状態値を比較し、状態遷移が前記選択部から選択出力される前記任意の１つの変化条件ルールに従っていないと不正操作を検知して検知信号を出力する状態値比較回路
を備え、
前記複数の変化条件ルールは、同一固定ビット数の値変化を用いるルールである
ことを特徴とする不正操作検知回路。
（付記２）
前記複数の変化条件ルールは、いずれも１ビット値変化を用いるルールであることを特徴とする付記１記載の不正操作検知回路。
（付記３）
前記状態値生成回路は、前記現在の状態値に対する前記複数の変化条件ルールに従った状態遷移後の状態値を生成するのに必要なデータを格納する複数の状態値テーブルを有し、
前記選択部は、前記複数の状態値テーブルを用いて生成された前記現在の状態値に対する状態遷移後の複数の状態値の１つを前記乱数入力に基づいて選択出力して前記状態値格納部及び前記状態値比較回路に入力するセレクタを有する
ことを特徴とする付記１または２記載の不正操作検知回路。
（付記４）
外部装置と通信して演算開始入力を受信する通信回路と、
プロセッサと、
不正操作検知回路
を備え、
前記不正操作検知回路は、
互いに異なる複数の、状態値の変化条件ルールを出力する変化条件ルール出力回路と、
前記複数の変化条件ルールに従って現在の状態値に対する状態遷移後の状態値を生成する状態値生成回路と、
前記複数の変化条件ルールに従って前記状態値生成回路で生成された状態遷移後の状態値のうち、任意の１つの変化条件ルールに従って生成された状態遷移後の状態値と、前記変化条件ルール出力回路から出力された前記複数の変化条件ルールのうち、前記任意の１つの変化条件ルールを、乱数に基づいて選択出力する選択部と、
前記演算開始入力に基づいて前記現在の状態値を格納すると共に、前記選択部から選択出力される前記状態遷移後の状態値を格納する状態値格納部と、
前記状態値格納部の入出力に基づき前記状態遷移後の状態値と前記現在の状態値を比較し、状態遷移が前記選択部から選択出力される前記任意の１つの変化条件ルールに従っていないと不正操作を検知して検知信号を前記プロセッサに出力する状態値比較回路
を備え、
前記複数の変化条件ルールは、同一固定ビット数の値変化を用いるルールである
ことを特徴とする装置。
（付記５）
前記複数の変化条件ルールは、いずれも１ビット値変化を用いるルールであることを特徴とする付記４記載の装置。
（付記６）
前記状態値生成回路は、前記現在の状態値に対する前記複数の変化条件ルールに従った状態遷移後の状態値を生成するのに必要なデータを格納する複数の状態値テーブルを有し、
前記選択部は、前記複数の状態値テーブルを用いて生成された前記現在の状態値に対する状態遷移後の複数の状態値の１つを前記乱数の入力に基づいて選択出力して前記状態値格納部及び前記状態値比較回路に入力するセレクタを有する
ことを特徴とする付記４または５記載の装置。
（付記７）
アンテナを含む外部インターフェース回路を更に備え、
前記通信回路は、前記外部インターフェース回路を介して前記外部装置と無線の通信方式で通信し、
スマートカードを形成することを特徴とする付記４乃至６のいずれか１項記載の装置。
（付記８）
前記乱数は、前記装置内で発生されることを特徴とする付記４乃至７のいずれか１項記載の装置。
（付記９）
前記乱数は、前記不正操作検知回路内で発生されることを特徴とする付記８記載の装置。
（付記１０）
前記乱数は、前記プロセッサで発生されることを特徴とする付記８記載の装置。
（付記１１）
前記乱数は、前記不正操作検知回路外で発生されることを特徴とする付記８記載の装置。
（付記１２）
複数の変化条件ルールに従って状態値生成回路で現在の状態値に対する状態遷移後の状態値を生成し、任意の１つの変化条件ルールに従って生成された状態遷移後の状態値と、前記任意の１つの変化条件ルールを、乱数に基づいて選択部から選択出力するステップと、
演算開始入力に基づいて状態値格納部に前記現在の状態値を格納すると共に、前記選択部から選択出力される前記状態遷移後の状態値を格納するステップと、
前記状態値格納部の入出力に基づき前記状態遷移後の状態値と前記現在の状態値を状態値比較回路で比較し、状態遷移が前記任意の１つの変化条件ルールに従っていないと不正操作を検知して検知信号を出力するステップ
を不正操作検知回路で実行し、
前記複数の変化条件ルールは互いに異なり、且つ、同一固定ビット数の値変化を用いるルールである
ことを特徴とする不正操作検知方法。
（付記１３）
前記複数の変化条件ルールは、いずれも１ビット値変化を用いるルールであることを特徴とする、付記１２記載の不正操作検知方法。
（付記１４）
前記状態値生成回路において、前記複数の変化条件ルールに従った状態遷移後の状態値を生成するのに必要なデータを格納する複数の状態値テーブルを用いて前記現在の状態値に対する状態遷移後の状態値を生成することを特徴とする付記１２または１３記載の不正操作検知方法。
（付記１５）
前記演算開始入力を前記不正操作検知回路を有するスマートカードの通信回路から読込むステップと、
前記乱数を前記スマートカードのプロセッサから読込むステップ
を前記不正操作検知回路で更に実行することを特徴とする付記１２乃至１４のいずれか１項記載の不正操作検知方法。
【００８３】
以上、開示の不正操作検知回路、不正操作検知回路を備えた装置、及び不正操作検知方法を実施例により説明したが、本発明は上記実施例に限定されるものではなく、本発明の範囲内で種々の変形及び改良が可能であることは言うまでもない。
【符号の説明】
【００８４】
１１      状態値生成回路
１１Ａ〜１１Ｃ      状態値テーブル
１２      状態値レジスタ
１３Ａ〜１３Ｃ      変化条件ルール出力回路
１４      状態値比較回路
１５，１６      セレクタ
１００      スマートカード
１０１      ＣＰＵ
１０２      ＲＯＭ
１０３      通信回路
１０４      外部インターフェース回路
１０５      不正操作検知回路
１０６      ＲＡＭ
１０７      クロック生成回路
１０８      電源回路
１０９      バス
【図１】
2013207414.tif 000003
【図２】
2013207414.tif 000004
【図３】
2013207414.tif 000005
【図４】
2013207414.tif 000006
【図５】
2013207414.tif 000007
【図６】
2013207414.tif 000008
【図７】
2013207414.tif 000009
【図８】
2013207414.tif 000010
【図９】
2013207414.tif 000011
【図１０】
2013207414.tif 000012
【図１１】
2013207414.tif 000013
【図１２】
2013207414.tif 000014
【図１３】
2013207414.tif 000015
【図１４】
2013207414.tif 000016