(57)【要約】【課題】ＥＣＣに限らずＲＳＡ方式などの、べき乗演算を含む公開鍵暗号方式の演算処理を実行可能なマイコンまたはそれを搭載したスマートカードにおいて、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上する。【解決手段】累算値を格納するメモリと、非剰余演算器と、群演算器とを備え、以下の動作を実行可能に構成される。べき乗演算は、第１ステップと第２ステップとを含み、べき乗演算の指数の２進数表現における各桁に対応する少なくとも１回以上の繰り返しを含むループ処理によって演算される。第１ステップでは、累算値をメモリから読み出して任意値との積または和を求め、新たな累算値としてメモリに書き戻す。第２ステップでは、累算値をメモリから読み出して群演算器による演算の結果をメモリに書き戻すことにより累算値を更新する。このとき、任意値は、第１ステップにおいて累算値を異なる値に更新する値に設定される。【選択図】図１
2014145958.tif 000002
【特許請求の範囲】
【請求項１】
べき乗演算を含む公開鍵暗号方式の演算処理を実行可能な半導体装置であって、
累算値を格納可能な記憶装置と、非剰余演算器と、群演算器とを備え、
前記べき乗演算は、第１ステップと第２ステップとを含むループ処理であって、前記べき乗演算の指数の２進数表現における各桁に対応する少なくとも１回以上の繰り返しを含む前記ループ処理によって演算され、
前記第１ステップにおいて、前記累算値を前記記憶装置から読み出して任意値とともに前記非剰余演算器に入力し、出力される積または和を前記記憶装置に書き戻すことにより前記累算値を更新し、
前記第２ステップにおいて、前記累算値を前記記憶装置から読み出して前記群演算器に入力し、出力される群演算の結果を前記記憶装置に書き戻すことにより前記累算値を更新し、
前記任意値は、前記第１ステップにおいて前記累算値を異なる値に更新する値に設定される、半導体装置。
【請求項２】
請求項１において、前記公開鍵暗号方式はＲＳＡ方式またはＤＳＡ方式であり、前記非剰余演算器は加算器であり、前記群演算器は剰余演算を実行可能な剰余演算器であり、前記任意値は前記剰余演算の法の倍数であり、
前記第１ステップにおいて、前記任意値と前記累算値とを前記記憶装置から読み出して前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新する、半導体装置。
【請求項３】
請求項２において、前記記憶装置はさらにダミー累算値を格納可能であり、
前記ループ処理はさらに第３ステップを含み、前記べき乗演算の前記指数の２進数表現におけるビット数を繰り返し回数とし、
前記第３ステップにおいて、前記任意値と前記第２ステップで更新された前記累算値とを前記記憶装置から読み出して前記剰余演算器に入力し、前記剰余演算器からの出力を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む、半導体装置。
【請求項４】
請求項１において、前記公開鍵暗号方式はＲＳＡ方式またはＤＳＡ方式であり、前記非剰余演算器は加算器であり、前記群演算器は剰余演算を実行可能な剰余演算器であり、前記任意値は前記剰余演算の法に乱数を乗じた値であり、
前記第１ステップにおいて、前記任意値と前記累算値とを前記記憶装置から読み出して前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新する、半導体装置。
【請求項５】
請求項１において、前記公開鍵暗号方式はＲＳＡ方式またはＤＳＡ方式であり、前記任意値を第１任意値とし、前記記憶装置はさらにダミー累算値を格納可能であり、前記非剰余演算器は加算器であり、前記群演算器は剰余演算を実行可能な剰余演算器であり、
前記ループ処理は、さらに第４ステップと第５ステップと第６ステップと第７ステップとを含み、前記べき乗演算の前記指数の２進数表現におけるビット数を繰り返し回数とし、
前記第４ステップにおいて、前記剰余演算の法と第１乱数の積を前記第１任意値として算出し、
前記第１ステップにおいて、前記累算値を前記記憶装置から読み出して前記第１任意値とともに前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新し、
前記第５ステップにおいて、前記法と第２乱数の積を第２任意値として算出し、
前記第６ステップにおいて、前記累算値を前記記憶装置から読み出して前記第２任意値とともに前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新し、
前記第７ステップにおいて、前記累算値を前記記憶装置から読み出して前記剰余演算器に入力し、出力される剰余演算の結果を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む、半導体装置。
【請求項６】
請求項２において、前記記憶装置はさらにダミー累算値を格納可能であり、
前記ループ処理はさらに第８ステップと第９ステップとを含み、前記べき乗演算の前記指数の２進数表現におけるビット数を繰り返し回数とし、
前記第８ステップにおいて、前記累算値を前記記憶装置から読み出して前記任意値とともに前記加算器に入力し出力される和を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込み、
前記第９ステップにおいて、前記第２ステップで更新された前記累算値を前記記憶装置から読み出して前記任意値とともに前記剰余演算器に入力し、前記剰余演算器からの出力を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む、半導体装置。
【請求項７】
請求項２において、前記記憶装置はＲＡＭであり、前記加算器と前記剰余演算器を含むコプロセッサを備え、前記ＲＡＭは前記コプロセッサによりバスを介してアクセス可能に構成される、半導体装置。
【請求項８】
請求項１において、前記公開鍵暗号方式は楕円曲線暗号方式であり、前記非剰余演算器は乗算器であり、前記群演算器は剰余演算を実行可能な剰余演算器であり、前記累算値を第１累算値とし、前記記憶装置はさらに第２累算値を格納可能であり、
前記ループ処理は、前記第１ステップと前記第２ステップをサブステップとして含む第１０ステップと第１１ステップとを含み、前記べき乗演算の前記指数の２進数表現におけるビット数を繰り返し回数とし、
前記第１０ステップにおいて、前記第１累算値と前記第２累算値とを前記記憶装置から読み出して、楕円曲線点加算を行い、前記楕円曲線点加算の結果を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記記憶装置に書き戻すことにより前記第１累算値を更新するか、または、前記記憶装置に前記第２累算値として書き込み、
前記第１１ステップにおいて、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記第１累算値または前記第２累算値を読み出して、楕円曲線点２倍算を行って書き戻す、半導体装置。
【請求項９】
請求項８において、前記任意値を第１任意値とし、前記第１１ステップは、サブステップとして第１２ステップを含み、
前記第１ステップにおいて、前記第１０ステップの前記楕円曲線点加算における２つの入力点の座標の値のそれぞれに前記第１任意値を乗じ、
前記第１２ステップにおいて、前記第１１ステップの前記楕円曲線点２倍算における１つの入力点の座標の値のそれぞれに第２任意値を乗じる、半導体装置。
【請求項１０】
請求項８において、前記記憶装置はＲＡＭであり、前記乗算器と前記剰余演算器を含むコプロセッサを備え、前記ＲＡＭは前記コプロセッサによりバスを介してアクセス可能に構成される、半導体装置。
【請求項１１】
請求項１０において、ＣＰＵと前記ＣＰＵで実行可能なプログラムを格納する不揮発性メモリを備え、前記プログラムは、前記第１任意値と前記第２任意値をプログラムコードの一部に含む、半導体装置。
【請求項１２】
べき乗演算を含むＲＳＡ方式の演算処理を実行可能な半導体装置であって、
累算値を格納可能な記憶装置と、加算器と、剰余演算器とを備え、
前記べき乗演算は、第１ステップと第２ステップとを含むループ処理であって、前記べき乗演算の指数の２進数表現における各桁に対応する少なくとも１回以上の繰り返しを含む前記ループ処理によって演算され、
前記第１ステップにおいて、前記累算値を前記記憶装置から読み出して任意値とともに前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新し、
前記第２ステップにおいて、前記累算値を前記記憶装置から読み出して前記剰余演算器に入力し、出力される剰余演算の結果を前記記憶装置に書き戻すことにより前記累算値を更新し、
前記任意値は、前記第１ステップにおいて前記累算値を異なる値に更新する値に設定される、半導体装置。
【請求項１３】
請求項１２において、前記記憶装置はさらにダミー累算値を格納可能であり、
前記ループ処理はさらに第３ステップを含み、前記べき乗演算の前記指数の２進数表現におけるビット数を繰り返し回数とし、
前記第３ステップにおいて、前記任意値と前記第２ステップで更新された前記累算値とを前記記憶装置から読み出して前記剰余演算器に入力し、前記剰余演算器からの出力を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む、半導体装置。
【請求項１４】
請求項１２において、前記任意値は前記剰余演算の法に乱数を乗じた値であり、
前記第１ステップにおいて、前記任意値と前記累算値とを前記記憶装置から読み出して前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新する、半導体装置。
【請求項１５】
請求項１２において前記任意値を第１任意値とし、前記記憶装置はさらにダミー累算値を格納可能であり、前記ループ処理は、さらに第４ステップと第５ステップと第６ステップと第７ステップとを含み、前記べき乗演算の前記指数の２進数表現におけるビット数を繰り返し回数とし、
前記第４ステップにおいて、前記剰余演算の法と第１乱数の積を前記第１任意値として算出し、
前記第１ステップにおいて、前記累算値を前記記憶装置から読み出して前記第１任意値とともに前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新し、
前記第５ステップにおいて、前記法と第２乱数の積を第２任意値として算出し、
前記第６ステップにおいて、前記累算値を前記記憶装置から読み出して前記第２任意値とともに前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新し、
前記第７ステップにおいて、前記累算値を前記記憶装置から読み出して前記剰余演算器に入力し、出力される剰余演算の結果を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む、半導体装置。
【請求項１６】
請求項１２において、前記記憶装置はさらにダミー累算値を格納可能であり、
前記ループ処理はさらに第８ステップと第９ステップとを含み、前記べき乗演算の前記指数の２進数表現におけるビット数を繰り返し回数とし、
前記第８ステップにおいて、前記累算値を前記記憶装置から読み出して前記任意値とともに前記加算器に入力し出力される和を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込み、
前記第９ステップにおいて、前記第２ステップで更新された前記累算値を前記記憶装置から読み出して前記任意値とともに前記剰余演算器に入力し、前記剰余演算器からの出力を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む、半導体装置。
【請求項１７】
請求項１２において、前記記憶装置はＲＡＭであり、前記加算器と前記剰余演算器を含むコプロセッサを備え、前記ＲＡＭは前記コプロセッサによりバスを介してアクセス可能に構成される、半導体装置。
【請求項１８】
べき乗演算を含む楕円曲線暗号方式の演算処理を実行可能な半導体装置であって、
第１累算値と第２累算値を格納可能な記憶装置と、乗算器と、剰余演算器とを備え、
前記べき乗演算は、第１ステップと第２ステップとを含むループ処理であって、前記べき乗演算の指数の２進数表現における各桁に対応する少なくとも１回以上の繰り返しを含む前記ループ処理によって演算され、
前記第１ステップにおいて、前記第１累算値を前記記憶装置から読み出して任意値とともに前記非剰余演算器に入力し、出力される積を前記記憶装置に書き戻すことにより前記第１累算値を更新し、
前記第２ステップにおいて、前記第１累算値を前記記憶装置から読み出して前記群演算器に入力し、出力される群演算の結果を前記記憶装置に書き戻すことにより前記第１累算値を更新し、
前記任意値は、前記第１ステップにおいて前記第１累算値を異なる値に更新する値に設定される、半導体装置。
前記ループ処理は、前記第１ステップと前記第２ステップをサブステップとして含む第１０ステップと第１１ステップとを含み、前記べき乗演算の前記指数の２進数表現におけるビット数を繰り返し回数とし、
前記第１０ステップにおいて、前記第１累算値と前記第２累算値とを前記記憶装置から読み出して、楕円曲線点加算を行い、前記楕円曲線点加算の結果を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記記憶装置に書き戻すことにより前記第１累算値を更新するか、または、前記記憶装置に前記第２累算値として書き込み、
前記第１１ステップにおいて、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値に基づいて、前記第１累算値または前記第２累算値を読み出して、楕円曲線点２倍算を行って書き戻す、半導体装置。
【請求項１９】
請求項１８において、前記任意値を第１任意値とし、前記第１１ステップは、サブステップとして第１２ステップを含み、
前記第１ステップにおいて、前記第１０ステップの前記楕円曲線点加算における２つの入力点の座標の値のそれぞれに前記第１任意値を乗じ、
前記第１２ステップにおいて、前記第１１ステップの前記楕円曲線点２倍算における１つの入力点の座標の値のそれぞれに第２任意値を乗じる、半導体装置。
【請求項２０】
請求項１８において、前記記憶装置はＲＡＭであり、前記乗算器と前記剰余演算器を含むコプロセッサを備え、前記ＲＡＭは前記コプロセッサによりバスを介してアクセス可能に構成される、半導体装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号演算を行う半導体装置に関し、特に耐タンパー性の向上に好適に利用できるものである。
【背景技術】
【０００２】
スマートカードやそれに搭載されるセキュアマイコンのような耐タンパー機器には、サイドチャネル攻撃によってデータが漏洩することを防ぐ対策が求められている。サイドチャネル攻撃とは、暗号装置の動作を、消費電流や電磁輻射などの物理現象を観測し、データ処理することにより、秘匿されるべきデータ、特に暗号鍵を不正に知得しようとする攻撃である。一般的にサイドチャンネル波形は非常にノイズが多く、秘密データの情報を直ちに抽出することは非常に困難である。これに対し、特に差分電力解析と呼ばれる攻撃は、ノイズを減らし確実に目的のデータを抽出するために、重複漏洩測定や平均化技術（非特許文献１）を利用する。
【０００３】
差分電力解析に対抗する標準的な方法は、秘密データをランダム化する方法である。例えばＲＳＡ方式では、下式を用いてメッセージを復号する。
【０００４】
M = C^D mod N  ・・・・・・・・・・・・・・・・・・・・・ （式１）
【０００５】
ここで、記号「^」はべき乗演算、「mod」は剰余演算を表し、「×」と「＊」は非モジュラ乗算を表すものとし、（以下本明細書及び図面において同じ）、Ｍはメッセージ、Ｃは署名、Ｄは暗号鍵、Ｎは剰余の法である。耐タンパー性のためには、暗号鍵Ｄを漏洩から守ることが最も重要である。
【０００６】
特許文献１には、暗号鍵Ｄをランダム化する技術が開示されている。下式のとおり、式１の指数部をランダム化することができる。
【０００７】
M = C^（D+r1×Φ（N）） mod N  ・・・・・・・・・・・・・・（式２）
【０００８】
ここで、ｒ１は乱数、Φはオイラーのトーシェント関数であり、指数をランダム化しても全く同じ演算結果を得ることができる。
【０００９】
特許文献２には、さらに、式３のように、べき乗演算の基数Ｃと剰余の法Ｎをそれぞれランダム化する技術が開示されている。ランダム化されたメッセージＭ’は、式４によって復号される。
【００１０】
M’=（C+r3×N）^（D+r1×Φ（N）） mod （r2×N）  ・・・・（式３）
【００１１】
M = M’mod N  ・・・・・・・・・・・・・・・・・・・・・・・ （式４）
【００１２】
ここで、ｒ１、ｒ２、ｒ３は乱数であり、任意に変更することができるため、ランダム化された指数、法、及び基数が使用される回数を１回のみにすることができ、平均化技術を使った攻撃に対抗することができる。
【００１３】
平均化技術は、ノイズを減らすのに有効な攻撃であるが、同一のシーケンスが繰り返し出現することを前提としているため、以上のようなランダム化技術により、平均化技術を無効化し耐タンパー性を向上することができる。ところが、観測技術の向上によって、単発の現象を観測することが可能となり、暗号装置に「演算の間の衝突」と呼ばれる現象があると、秘密データの情報が漏洩する恐れがあることが指摘された（非特許文献２）。
【００１４】
ここでいう「演算の間の衝突」とは、べき乗演算などで同じ値のデータが異なった２つの地点（暗号装置内の場所やタイミング）で演算処理されることをいう。ＲＳＡやＤＳＡのような公開鍵暗号方式ではべき剰余演算を利用し、楕円曲線暗号（ＥＣＣ：Elliptic Curve Cryptography）でもべき乗演算を利用する。べき乗演算法の入力や出力に、異なったタイミングで同じデータが現れる、「演算の間の衝突」が発生したときに、暗号装置の単発の現象を観測することにより、演算の間の衝突が発生したことが検知される可能性がある。さらに、この発生のタイミングは、秘密データを推定するためのヒントになり得る。
【００１５】
非特許文献２には、ＥＣＣスカラー倍演算での演算の間の衝突に対する一部の対策が示されている。べき乗演算で処理されている中間データに乱数を乗じてランダム化することにより、演算の間の衝突の発生を回避している。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】米国特許第７５０６１６５号
【特許文献２】米国特許第５９９１４１５号
【非特許文献】
【００１７】
【非特許文献１】Paul Kocher，Joshua Jaffe，and Benjamin Jun: "Differential Power Analysis"，LNCS 1666，Springer-Verlag，1999.
【非特許文献２】Neil Hanley，HeeSeok Kim，and Michael Tunstall: "Exploiting Collisions in Addition Chain-based Exponentiation Algorithms"，Cryptology ePrint Archive，Report 2012/485，2012-08-22
【発明の概要】
【発明が解決しようとする課題】
【００１８】
特許文献１、２及び非特許文献１、２について本発明者が検討した結果、以下のような新たな課題があることがわかった。
【００１９】
すでに述べたように、特許文献１と２に記載される、べき乗演算の指数、基数、及び剰余の法をランダム化することによって、平均化技術を使った攻撃に対抗することができるが、単発の物理現象の観測まで考慮すると、演算の間の衝突が攻撃の対象となるおそれがある。非特許文献２に記載される技術によれば、演算の中間データにおける演算の間の衝突による問題の一部を解決するが、以下の問題がある。
【００２０】
一般に乱数の生成には時間を要するのに対し、非特許文献２に記載されている技術では、乱数が数多く使用されている。さらに、ランダム化のステップ自体に、演算の間の衝突が発生し、攻撃の対象となる恐れがある。非特許文献２はこの課題を指摘してはいるが、解決手段は示していない。
【００２１】
このような課題を解決するための手段を以下に説明するが、その他の課題と新規な特徴は、本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【００２２】
一実施の形態によれば、下記の通りである。
【００２３】
すなわち、べき乗演算を含む公開鍵暗号方式の演算処理を実行可能な半導体装置であって、累算値を格納可能な記憶装置と、非剰余演算器と、群演算器とを備え、以下の動作を実行可能に構成される。
【００２４】
べき乗演算は、第１ステップと第２ステップとを含むループ処理であって、べき乗演算の指数の２進数表現における各桁に対応する少なくとも１回以上の繰り返しを含むループ処理によって演算される。
【００２５】
第１ステップにおいて、累算値を記憶装置から読み出して任意値とともに非剰余演算器に入力し、出力される積または和を記憶装置に書き戻すことにより累算値を更新する。
【００２６】
第２ステップにおいて、累算値を記憶装置から読み出して群演算器に入力し、出力される群演算の結果を記憶装置に書き戻すことにより累算値を更新する。
【００２７】
このとき、任意値は、第１ステップにおいて累算値を異なる値に更新する値に設定される。
【発明の効果】
【００２８】
前記一実施の形態によって得られる効果を簡単に説明すれば下記のとおりである。
【００２９】
すなわち、ＥＣＣに限らずＲＳＡ方式などの、べき乗演算を含む公開鍵暗号方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上することができる。
【図面の簡単な説明】
【００３０】
【図１】図１は、代表的な実施の形態に係る半導体装置の構成を表すブロック図である。
【図２】図２は、代表的な実施の形態に係る半導体装置の動作を表すフローチャートである。
【図３】図３は、代表的な実施の形態に係る半導体装置の構成、及び、それをＲＳＡ暗号演算を行うスマートカードに搭載したシステムの構成例を表すブロック図である。
【図４】図４は、代表的な実施の形態に係る半導体装置を搭載した、ＲＳＡ暗号演算を行うスマートカードシステムの動作例を表す説明図である。
【図５】図５は、ＲＳＡ暗号演算におけるランダム化による保護動作を表すフローチャートである。
【図６】図６は、ＲＳＡ暗号演算におけるべき乗演算の動作を表すフローチャートである。
【図７】図７は、ＲＳＡ暗号演算のべき乗演算における演算の間の衝突を示す説明図である。
【図８】図８は、実施形態１のべき乗演算の動作を表すフローチャートである。
【図９】図９は、実施形態１のべき乗演算における演算の間の衝突を示す説明図である。
【図１０】図１０は、実施形態２のべき乗演算の動作を表すフローチャートである。
【図１１】図１１は、実施形態２のべき乗演算における演算の間の衝突を示す説明図である。
【図１２】図１２は、実施形態３のべき乗演算の動作を表すフローチャートである。
【図１３】図１３は、実施形態３のべき乗演算における演算の間の衝突を示す説明図である。
【図１４】図１４は、代表的な実施の形態に係る半導体装置の構成、及び、それをＥＣＣ演算を行うスマートカードに搭載したシステムの構成例を表すブロック図である。
【図１５】図１５は、ＥＣＣ演算におけるランダム化による保護動作を表すフローチャートである。
【図１６】図１６は、ＥＣＣ演算におけるべき乗演算の動作を表すフローチャートである。
【図１７】図１７は、ＥＣＣ演算の比較例のべき乗演算における演算の間の衝突を示す説明図である。
【図１８】図１８は、比較例のべき乗演算の動作を表すフローチャートであり、図１６における楕円曲線点加算ＥＣＡＤＤと楕円曲線点２倍算ＥＣＤＢＬの一般的な実装例である。
【図１９】図１９は、べき乗演算の動作を表すフローチャートであり、図１６における楕円曲線点加算ＥＣＡＤＤと楕円曲線点２倍算ＥＣＤＢＬの実施形態４による実施の形態である。
【発明を実施するための形態】
【００３１】
１．実施の形態の概要
先ず、本願において開示される代表的な実施の形態について概要を説明する。代表的な実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。
【００３２】
〔１〕＜演算の間の衝突を抑えたべき乗演算回路＞
べき乗演算を含む公開鍵暗号方式の演算処理を実行可能な半導体装置（１、１２０、６２０）であって、累算値（５、１７０、６７０）を格納可能な記憶装置（２、１２７、６２７）と、非剰余演算器（３、１４５、６４８）と、群演算器（４、１４０、１４１、６４０、６４１）とを備え、以下の動作を可能に構成される。
【００３３】
前記べき乗演算は、第１ステップ（１４、４３１、４１３、４１７、５１１、１００１、１０２１）と第２ステップ（１５、４３２、４１４、５１２、１００２、１０２２）とを含むループ処理であって、前記べき乗演算の指数（Ｄ’、ｄ）の２進数表現における各桁（dn-1，…d0）に対応する少なくとも１回以上の繰り返しを含む前記ループ処理によって演算される。
【００３４】
前記第１ステップにおいて、前記累算値を前記記憶装置から読み出して任意値（６、Ｎ’，Ｎ”，ａ、ｂ）とともに前記非剰余演算器に入力し、出力される積または和を前記記憶装置に書き戻すことにより前記累算値を更新する。
【００３５】
前記第２ステップにおいて、前記累算値を前記記憶装置から読み出して前記群演算器に入力し、出力される群演算の結果を前記記憶装置に書き戻すことにより前記累算値を更新する。
【００３６】
前記任意値は、前記第１ステップにおいて前記累算値を異なる値に更新する値に設定される。
【００３７】
これにより、ＥＣＣに限らずＲＳＡ方式などの、べき乗演算を含む公開鍵暗号方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上することができる。
【００３８】
〔２〕＜ＲＳＡ／ＤＳＡ公開鍵方式  C’[1]=C’[1]+N’＞
項１において、前記公開鍵暗号方式はＲＳＡ方式またはＤＳＡ方式であり、前記非剰余演算器は加算器（１４３）であり、前記群演算器は剰余演算を実行可能な剰余演算器（１４１）であり、前記任意値は前記剰余演算の法（１６１）の倍数である。
【００３９】
前記第１ステップ（４３１）において、前記任意値と前記累算値とを前記記憶装置から読み出して前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新する。
【００４０】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上することができる。
【００４１】
〔３〕＜ＲＳＡ／ＤＳＡ公開鍵方式  C’[di]=C’[1]*M’ mod N’＞
項２において、前記記憶装置はさらにダミー累算値（１７０）を格納可能に構成される。
【００４２】
前記ループ処理はさらに第３ステップ（４３３）を含み、前記べき乗演算の前記指数の２進数表現におけるビット数（ｎ）を繰り返し回数とする。
【００４３】
前記第３ステップにおいて、前記任意値と前記第２ステップで更新された前記累算値とを前記記憶装置から読み出して前記剰余演算器に入力する。前記剰余演算器からの出力を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む。
【００４４】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上することができる。
【００４５】
〔４〕＜ＲＳＡ／ＤＳＡ公開鍵方式  C’[1]=C’[1]+N”（乱数a）＞
項１において、前記公開鍵暗号方式はＲＳＡ方式またはＤＳＡ方式であり、前記非剰余演算器は加算器（１４３）であり、前記群演算器は剰余演算を実行可能な剰余演算器（１４１）であり、前記任意値（N”）は前記剰余演算の法（N’）に乱数（ａ）を乗じた値（N”=a×N’）である。
【００４６】
前記第１ステップ（４１３）において、前記任意値と前記累算値とを前記記憶装置から読み出して前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新する。
【００４７】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上することができる。
【００４８】
〔５〕＜ＲＳＡ／ＤＳＡ公開鍵方式  C’[1]=C’[1]+N”（乱数a，b）＞
項１において、前記公開鍵暗号方式はＲＳＡ方式またはＤＳＡ方式であり、前記任意値を第１任意値（ａ）とし、前記記憶装置はさらにダミー累算値を格納可能であり、前記非剰余演算器は加算器であり、前記群演算器は剰余演算を実行可能な剰余演算器であり、
前記ループ処理は、さらに第４ステップ（４１２）と第５ステップ（４１６）と第６ステップ（４１７）と第７ステップ（４１８）とを含み、前記べき乗演算の前記指数の２進数表現におけるビット数（ｎ）を繰り返し回数とする。
【００４９】
前記第４ステップ（４１２）において、前記剰余演算の法（Ｎ’）と第１乱数（ａ）の積を前記第１任意値（Ｎ”）として算出する。
【００５０】
前記第１ステップ（４１３）において、前記累算値を前記記憶装置から読み出して前記第１任意値とともに前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新する。
【００５１】
前記第５ステップ（４１６）において、前記法（Ｎ’）と第２乱数（ｂ）の積を第２任意値（Ｎ”）として算出する。
【００５２】
前記第６ステップ（４１７）において、前記累算値を前記記憶装置から読み出して前記第２任意値とともに前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新する。
【００５３】
前記第７ステップ（４１８）において、前記累算値を前記記憶装置から読み出して前記剰余演算器に入力し、出力される剰余演算の結果を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む。
【００５４】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上することができる。
【００５５】
〔６〕＜ＲＳＡ／ＤＳＡ公開鍵方式  C’[NOT（di）]=C’[1]+N’＞
項２において、前記記憶装置はさらにダミー累算値を格納可能に構成される。
【００５６】
前記ループ処理はさらに第８ステップ（５１３）と第９ステップ（５１４）とを含み、前記べき乗演算の前記指数の２進数表現におけるビット数（ｎ）を繰り返し回数とする。
【００５７】
前記第８ステップ（５１３）において、前記累算値を前記記憶装置から読み出して前記任意値とともに前記加算器に入力し出力される和を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む。
【００５８】
前記第９ステップ（５１４）において、前記第２ステップで更新された前記累算値を前記記憶装置から読み出して前記任意値とともに前記剰余演算器に入力する。さらにそのときの前記剰余演算器からの出力を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む。
【００５９】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上することができる。
【００６０】
〔７〕＜コプロセッサ＋バス＋ＲＡＭ＞
項２から項６のうちのいずれか１項において、前記記憶装置はＲＡＭ（Random Access Memory）（１２７）であり、前記加算器と前記剰余演算器を含むコプロセッサ（１２４）を備え、前記ＲＡＭは前記コプロセッサによりバス（１２８）を介してアクセス可能に構成される。
【００６１】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上した半導体装置を提供することができる。
【００６２】
〔８〕＜楕円曲線暗号（ＥＣＣ）＞
項１において、前記公開鍵暗号方式は楕円曲線暗号方式であり、前記非剰余演算器は乗算器（６４２）であり、前記群演算器は剰余演算を実行可能な剰余演算器（６４１）であり、前記累算値を第１累算値とし、前記記憶装置はさらに第２累算値を格納可能に構成される。
【００６３】
前記ループ処理は、前記第１ステップと前記第２ステップをサブステップとして含む第１０ステップ（８１１）と第１１ステップ（８１２）とを含み、前記べき乗演算の前記指数の２進数表現におけるビット数（ｎ）を繰り返し回数とする。
【００６４】
前記第１０ステップ（８１１）において、前記第１累算値と前記第２累算値とを前記記憶装置から読み出して、楕円曲線点加算（ＥＣＡＤＤ）を行う。前記楕円曲線点加算の結果を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記記憶装置に書き戻すことにより前記第１累算値を更新するか、または、前記記憶装置に前記第２累算値として書き込む。
【００６５】
前記第１１ステップ（８１２）において、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記第１累算値または前記第２累算値を読み出して、楕円曲線点２倍算（ＥＣＤＢＬ）を行って書き戻す。
【００６６】
これにより、べき乗演算を含むＥＣＣ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上することができる。
【００６７】
〔９〕＜楕円曲線暗号（ＥＣＣ）  ランダム化＞
項８において、前記任意値を第１任意値（ａ）とし、前記第１１ステップは、サブステップとして第１２ステップ（１０２１）を含む。
【００６８】
前記第１ステップ（１００１）において、前記第１０ステップの前記楕円曲線点加算（ＥＣＡＤＤ）における２つの入力点の座標の値のそれぞれに前記第１任意値（ａ）を乗じる。
【００６９】
前記第１２ステップ（１０２１）において、前記第１１ステップの前記楕円曲線点２倍算（ＥＣＤＢＬ）における１つの入力点の座標の値のそれぞれに第２任意値（ｂ）を乗じる。
【００７０】
これにより、べき乗演算を含むＥＣＣ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上することができる。
【００７１】
〔１０〕＜コプロセッサ＋バス＋ＲＡＭ＞
項８または項９において、前記記憶装置はＲＡＭ（６２７）であり、前記乗算器と前記剰余演算器を含むコプロセッサ（６２４）を備え、前記ＲＡＭは前記コプロセッサによりバス（６２８）を介してアクセス可能に構成される。
【００７２】
これにより、べき乗演算を含むＥＣＣ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上した半導体装置を提供することができる。
【００７３】
〔１１〕＜任意値ａ、ｂはハードコード＞
項１０において、ＣＰＵ（Central Processing Unit）（６２２）と前記ＣＰＵで実行可能なプログラム（６５０）を格納する不揮発性メモリ（６２５）を備え、前記プログラムは、前記第１任意値と前記第２任意値をプログラムコードの一部（６５０、６５１、または６５２）に含む。
【００７４】
これにより、べき乗演算を含むＥＣＣ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上した半導体装置を提供することができる。
【００７５】
〔１２〕＜ＲＳＡ／ＤＳＡ公開鍵方式  C’[1]=C’[1]+N’＞
べき乗演算を含むＲＳＡ方式の演算処理を実行可能な半導体装置であって、累算値を格納可能な記憶装置（１２７）と、加算器（１４３）と、剰余演算器（１４１）とを備え、以下の動作を可能に構成される。
【００７６】
前記べき乗演算は、第１ステップ（４３１、４１３、４１７、５１１）と第２ステップ（４３２、４１４、４１８、５１２）とを含むループ処理であって、前記べき乗演算の指数（Ｄ’）の２進数表現における各桁（dn-1，…d0）に対応する少なくとも１回以上の繰り返しを含む前記ループ処理によって演算される。
【００７７】
前記第１ステップにおいて、前記累算値を前記記憶装置から読み出して任意値（Ｎ’）とともに前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新する。
【００７８】
前記第２ステップにおいて、前記累算値を前記記憶装置から読み出して前記剰余演算器に入力し、出力される剰余演算の結果を前記記憶装置に書き戻すことにより前記累算値を更新する。
【００７９】
前記任意値は、前記第１ステップにおいて前記累算値を異なる値に更新する値に設定される。
【００８０】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上することができる。
【００８１】
〔１３〕＜ＲＳＡ／ＤＳＡ公開鍵方式  C’[di]=C’[1]*M’ mod N’＞
項１２において、前記記憶装置はさらにダミー累算値（１７０）を格納可能に構成される。
【００８２】
前記ループ処理はさらに第３ステップ（４３３）を含み、前記べき乗演算の前記指数の２進数表現におけるビット数（ｎ）を繰り返し回数とする。
【００８３】
前記第３ステップにおいて、前記任意値と前記第２ステップで更新された前記累算値とを前記記憶装置から読み出して前記剰余演算器に入力する。前記剰余演算器からの出力を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む。
【００８４】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上することができる。
【００８５】
〔１４〕＜ＲＳＡ／ＤＳＡ公開鍵方式  C’[1]=C’[1]+N”＞
項１２において、前記任意値（N”）は前記剰余演算の法（N’）に乱数（ａ）を乗じた値（N”=a×N’）である。
【００８６】
前記第１ステップ（４１３）において、前記任意値と前記累算値とを前記記憶装置から読み出して前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新する。
【００８７】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上することができる。
【００８８】
〔１５〕＜ＲＳＡ／ＤＳＡ公開鍵方式  C’[1]=C’[1]+N”＞
項１２において前記任意値を第１任意値（ａ）とし、前記記憶装置はさらにダミー累算値を格納可能に構成される。
【００８９】
前記ループ処理は、さらに第４ステップ（４１２）と第５ステップ（４１６）と第６ステップ（４１７）と第７ステップ（４１８）とを含み、前記べき乗演算の前記指数の２進数表現におけるビット数（ｎ）を繰り返し回数とする。
【００９０】
前記第４ステップ（４１２）において、前記剰余演算の法（Ｎ’）と第１乱数（ａ）の積を前記第１任意値（Ｎ”）として算出する。
【００９１】
前記第１ステップ（４１３）において、前記累算値を前記記憶装置から読み出して前記第１任意値とともに前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新する。
【００９２】
前記第５ステップ（４１６）において、前記法（Ｎ’）と第２乱数（ｂ）の積を第２任意値（Ｎ”）として算出する。
【００９３】
前記第６ステップ（４１７）において、前記累算値を前記記憶装置から読み出して前記第２任意値とともに前記加算器に入力し、出力される和を前記記憶装置に書き戻すことにより前記累算値を更新する。
【００９４】
前記第７ステップ（４１８）において、前記累算値を前記記憶装置から読み出して前記剰余演算器に入力し、出力される剰余演算の結果を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む。
【００９５】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上することができる。
【００９６】
〔１６〕＜ＲＳＡ／ＤＳＡ公開鍵方式  C’[NOT（di）]=C’[1]+N’＞
項１２において、前記記憶装置はさらにダミー累算値を格納可能に構成される。
【００９７】
前記ループ処理はさらに第８ステップ（５１３）と第９ステップ（５１４）とを含み、前記べき乗演算の前記指数の２進数表現におけるビット数（ｎ）を繰り返し回数とする。
【００９８】
前記第８ステップ（５１３）において、前記累算値を前記記憶装置から読み出して前記任意値とともに前記加算器に入力し出力される和を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む。
【００９９】
前記第９ステップ（５１４）において、前記第２ステップで更新された前記累算値を前記記憶装置から読み出して前記任意値とともに前記剰余演算器に入力する。さらにそのときの前記剰余演算器からの出力を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記記憶装置に書き戻すことにより前記累算値を更新するか、または、前記記憶装置に前記ダミー累算値として書き込む。
【０１００】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上することができる。
【０１０１】
〔１７〕＜コプロセッサ＋バス＋ＲＡＭ＞
項１２から項１６のうちのいずれか１項において、前記記憶装置はＲＡＭ（１２７）であり、前記加算器と前記剰余演算器を含むコプロセッサ（１２４）を備え、前記ＲＡＭは前記コプロセッサによりバス（１２８）を介してアクセス可能に構成される。
【０１０２】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上した半導体装置を提供することができる。
【０１０３】
〔１８〕＜楕円曲線暗号（ＥＣＣ）  ECADDとECDBL＞
べき乗演算を含む楕円曲線暗号方式の演算処理を実行可能な半導体装置（１）であって、第１累算値と第２累算値を格納可能な記憶装置（６２７）と、乗算器（６４２）と、剰余演算器（６４１）とを備え、以下の動作を可能に構成される。
【０１０４】
前記べき乗演算は、第１ステップ（１００１）と第２ステップ（１００２）とを含むループ処理であって、前記べき乗演算の指数（ｄ）の２進数表現における各桁（dn-1，…d0）に対応する少なくとも１回以上の繰り返しを含む前記ループ処理によって演算される。
【０１０５】
前記第１ステップにおいて、前記第１累算値を前記記憶装置から読み出して任意値（ａ）とともに前記非剰余演算器に入力し、出力される積を前記記憶装置に書き戻すことにより前記第１累算値を更新する。
【０１０６】
前記第２ステップにおいて、前記第１累算値を前記記憶装置から読み出して前記群演算器に入力し、出力される群演算の結果を前記記憶装置に書き戻すことにより前記第１累算値を更新する。
【０１０７】
前記任意値は、前記第１ステップにおいて前記第１累算値を異なる値に更新する値に設定される。
【０１０８】
前記ループ処理は、前記第１ステップと前記第２ステップをサブステップとして含む第１０ステップ（８１１）と第１１ステップ（８１２）とを含み、前記べき乗演算の前記指数の２進数表現におけるビット数（ｎ）を繰り返し回数とする。
【０１０９】
前記第１０ステップ（８１１）において、前記第１累算値と前記第２累算値とを前記記憶装置から読み出して、楕円曲線点加算（ＥＣＡＤＤ）を行なう。さらにその前記楕円曲線点加算の結果を、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記記憶装置に書き戻すことにより前記第１累算値を更新するか、または、前記記憶装置に前記第２累算値として書き込む。
【０１１０】
前記第１１ステップ（８１２）において、前記ループ処理における繰り返しに対応する前記べき乗演算の前記指数の２進数表現における桁の値（di）に基づいて、前記第１累算値または前記第２累算値を読み出して、楕円曲線点２倍算（ＥＣＤＢＬ）を行って書き戻す。
【０１１１】
これにより、べき乗演算を含むＥＣＣ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上することができる。
【０１１２】
〔１９〕＜楕円曲線暗号（ＥＣＣ）  ランダム化＞
項１８において、前記任意値を第１任意値（ａ）とし、前記第１１ステップは、サブステップとして第１２ステップ（１０２１）を含む。
【０１１３】
前記第１ステップ（１００１）において、前記第１０ステップの前記楕円曲線点加算（ＥＣＡＤＤ）における２つの入力点の座標の値のそれぞれに前記第１任意値（ａ）を乗じる。
【０１１４】
前記第１２ステップ（１０２１）において、前記第１１ステップの前記楕円曲線点２倍算（ＥＣＤＢＬ）における１つの入力点の座標の値のそれぞれに第２任意値（ｂ）を乗じる。
【０１１５】
これにより、べき乗演算を含むＥＣＣ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上することができる。
【０１１６】
〔２０〕＜コプロセッサ＋バス＋ＲＡＭ＞
項１８または項１９において、前記記憶装置はＲＡＭ（６２７）であり、前記乗算器と前記剰余演算器を含むコプロセッサ（６２４）を備え、前記ＲＡＭは前記コプロセッサによりバス（６２８）を介してアクセス可能に構成される、半導体装置。
【０１１７】
これにより、べき乗演算を含むＥＣＣ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上した半導体装置を提供することができる。
【０１１８】
２．実施の形態の詳細
実施の形態について更に詳述する。
【０１１９】
〔代表的な実施の形態〕
図１は、代表的な実施の形態に係る半導体装置の構成を表すブロック図であり、図２は、その動作を表すフローチャートである。
【０１２０】
半導体装置１は、累算値５を格納可能な記憶装置２と、非剰余演算器３と、群演算器４とを備え、以下の動作により、べき乗演算を含む公開鍵暗号方式の演算処理を実行可能に構成される。
【０１２１】
前記べき乗演算は、第１ステップ１４と第２ステップ１５とを含むループ処理であって、前記べき乗演算の指数（Ｄ’）の２進数表現における各桁（dn-1，…d0）に対応する少なくとも１回以上の繰り返しを含む前記ループ処理によって演算される。第１ステップ１４において、累算値５を記憶装置２から読み出して任意値６とともに非剰余演算器３に入力し、出力される積または和を記憶装置２に書き戻すことにより累算値５の値を更新する。第２ステップ１５において、累算値５を記憶装置２から読み出して群演算器４に入力し、出力される群演算の結果を記憶装置２に書き戻すことにより累算値５の値を更新する。任意値６は、第１ステップ１４において累算値５を異なる値に更新する値に設定される。
【０１２２】
公開鍵暗号方式の演算処理は、式１によって暗号化されたメッセージＭを受信したとき、下式によって署名Ｃを算出し、真正の署名と照合することによって認証する。
【０１２３】
C = M^D mod N  ・・・・・・・・・・・・・・・・・ （式５）
【０１２４】
ここで、式３に示したように、べき乗演算の基数Ｃと指数Ｄ及び剰余の法Ｎをランダム化することにより、耐タンパー性を向上する技術が、採用されている。そのため、署名生成のための演算は、下式となる。
【０１２５】
C’= M’^D’mod N’  ・・・・・・・・・・・・・・ （式６）
【０１２６】
ここで、Ｃ’、Ｍ’、Ｄ’、Ｎ’はそれぞれ、ランダム化された署名Ｃ、メッセージＭ、指数Ｄ、法Ｎである。
【０１２７】
従来の公開鍵暗号方式では、初めに署名Ｃ’に適当な初期値を与えて中間データとし、指数（Ｄ’）の２進数表現における各桁（dn-1，…d0）に対応するｎ回の下記のべき剰余演算を繰り返すことにより、ループ処理を終えた中間データＣ’が署名Ｃ’として算出される。
【０１２８】
C’= C’^2 mod N’  ・・・・・・・・・・・・・・・・ （式７）
【０１２９】
C’= M’×C’mod N’ if di=1・・・・・・・・・・・・ （式８）
【０１３０】
ここで、「×」または「＊」は群演算ではない通常の乗算（非モジュラ乗算）であり（全ての図面における記載も同様）、式７と式８は剰余乗算である。式８は指数（Ｄ’）の２進数表現における各桁（dn-1，…d0）の値に依存する演算で、di=1のときは中間データＣ’を式８の剰余乗算の結果によって置き換えて更新するが、di=0のときは式８の剰余乗算の結果は使われずに破棄される。この処理を実行するハードウェアでは、Ｃ’を累算値５として記憶装置２に記憶しておき、累算値５を記憶装置２から読み出して群演算器４に入力し、出力される群演算の結果を記憶装置２に書き戻すことにより累算値５の値を更新するステップを繰り返す、ループ処理によって演算される。
【０１３１】
ｉ回目のループにおいて、di=0のときは式８の剰余乗算の結果は使われずに破棄されるとすると、Ｃ’の値は変更されず、ｉ＋１回目のループにおけるＣ’の値はｉ回目のループにおけるＣ’の値と同じ値（演算の間の衝突）となる。Ｃ’が記憶装置２に記憶されており、ループの度に読み出される。ｉ回目のループとｉ＋１回目のループにおいて、記憶装置２から読み出される値は、di=1のときは異なる値となるが、di=0のときは同じ値（演算の間の衝突）となる。したがって、演算の間の衝突を利用した攻撃が行われると、演算の間の衝突が発生したか否かを検知することにより、指数（Ｄ’）の２進数表現における各桁（dn-1，…d0）の値が、探知されてしまう。
【０１３２】
これに対し、代表的な実施の形態に係る半導体装置においては、第１ステップ１４において、署名Ｃ’を求めるための中間データである、累算値５を記憶装置２から読み出して任意値６とともに非剰余演算器３に入力し、出力される積または和を記憶装置２に書き戻すことにより累算値５の値を更新する。任意値６は、第１ステップ１４において累算値５を異なる値に更新する値に設定されているので、累算値５は指数（Ｄ’）の２進数表現における各桁（dn-1，…d0）の値によらず、必ず異なる値に更新され、演算の間の衝突は発生しない。
【０１３３】
これにより、ＥＣＣに限らずＲＳＡ方式などの、べき乗演算を含む公開鍵暗号方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上することができる。
【０１３４】
半導体装置１は、公知の半導体製造技術を使って、例えば単一の半導体基板上の回路として実装することができる。また、その動作は、例えば同じ半導体装置１に搭載されたＣＰＵなどのプロセッサ上で動作するソフトウェアによって制御、実行されることができる。単一の半導体基板上に形成することにより、外部からの観測が困難となり、耐タンパー性を向上することができる。一方、複数のＬＳＩなどで構成された半導体装置に、本実施形態を適用することもできる。
【０１３５】
〔実施形態１〕＜ＲＳＡ暗号のセキュアなべき乗演算（中間データの改変）＞
図３は、代表的な実施の形態に係る半導体装置の構成、及び、それをＲＳＡ暗号演算を行うスマートカードに搭載したシステムの構成例を表すブロック図である。
【０１３６】
スマートカード１２０は、ＵＡＲＴ（Universal Asynchronous Receiver Transmitter）１２１をインターフェースとしてリーダライタ１００と接続され、通信を行う。非接触の場合は、ＵＡＲＴ１２１に代えて無線通信インターフェースを備えればよい。スマートカード１２０は、ＵＡＲＴ１２１、ＣＰＵ１２２、乱数発生器（ＲＮＧ）１２３、コプロセッサ１２４、ＲＯＭ（Read Only Memory）１２５、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read Only Memory）１２６、及び、ＲＡＭ１２７を備え、バス１２８を介して互いに接続されている。コプロセッサ１２４は、群演算を行う、べき剰余演算器１４０、剰余乗算器１４１、モジュラリダクション器１４４、及び、非モジュラ演算器１４５として乗算器１４２と加算器１４３とを備える。それぞれ独立のハードウェアとして備える必要はなく、より単純な演算ハードウェアを使うシーケンスによって、複雑な演算を実装しても良い。例えば、剰余乗算は非モジュラ加減算によるシーケンスで実装しても良い。このことは、他の実施形態についても同様である。ＲＯＭ１２５には、ＣＰＵ１２２で実行されるプログラム１５０、共通データ１５１、ＲＳＡのプログラム１５２が格納されている。これらは、ＣＰＵ１２２の制御により、コプロセッサ１２４にも供給されることができる。ＥＥＰＲＯＭ１２６には、スマートカードのデータ１６０、法（Ｎ）１６１、指数（Ｄ）１６２、ブラインディング要素Φ（Ｎ）１６３が格納されている。ＲＡＭ１２７には、ＲＳＡ演算の中間データ１７０が格納されている。中間データ１７０を格納する記憶装置は、本実施形態ではＲＡＭ１２７として実装したが、書き換え可能な記憶装置であればよく、例えばレジスタ、ラッチ、フリップフロップでもよい。このことは、他の実施形態についても同様である。
【０１３７】
スマートカード１２０はＵＡＲＴ１２１を介して、リーダライタ１００と通信する。例えば、リーダライタ１００がメッセージＭ１１０を送信し、スマートカードはＲＳＡの法Ｎ（１６１）と指数Ｄ（１６２）を使って、署名（１１１）C=M^D mod Nを生成する。ＲＳＡにおいてべき乗M^D mod Nは、群の演算、この場合は剰余乗算、の繰り返しによって実装される。署名Ｃ（１１１）の生成は、ＲＯＭ１２５に格納されているプログラム１５２を用い、コプロセッサ１２４を使用してＣＰＵ１２２によって実行される。また演算の中間データ１７０はＲＡＭ１２７に格納され、主にコプロセッサ１２４が、バス１２８を介してＲＡＭ１２７にアクセスして中間データ１７０を使う。ＲＳＡ演算は時間のかかる多倍長演算を伴うため、演算を速めるためにハードウェア演算器を備えた、コプロセッサ１２４が有効である。コプロセッサ１２４は群演算であるべき剰余演算１４０、剰余乗算１４１、モジュラリダクション１４４の他、多倍長の非モジュラ演算１４５として乗算器１４２と加算器１４３とを含んでいる。乱数発生器（ＲＮＧ：Random Number Generator）１２３は、サイドチャンネル攻撃に対するＲＳＡ実行を保護するため、ＲＳＡ指数のブラインディングのブラインディング要素Φ（N）１６３となる乱数を生成する。
【０１３８】
図４は、代表的な実施の形態に係る半導体装置を搭載した、ＲＳＡ暗号演算を行うスマートカードシステムの動作例を表す説明図である。ＲＳＡ演算は、ユーザ認証のためディジタル署名Ｃ（１１１）を生成し検証するために使われる。他の公開鍵暗号システムにも応用されている。図４では、スマートカード１２０を持つユーザが、アクセス制限によって保護されたリソースにアクセスしようとする例を示している。現実的な適用例としては、駅での電子切符改札などが挙げられる。保護されたリソースにアクセスするためには、スマートカードを持つユーザは、認証をうける必要があり、その認証プロトコルは、スマートカード１２０とリーダライタ１００との間で実行される。
【０１３９】
スマートカード１２０は、ＲＳＡの剰余の法Ｎ（１６１）と秘密指数Ｄ（１６２）とを保持しており、リーダライタ１００は、同じ法Ｎ（１６１）と公開指数Ｅ（１８０）とを保持している。ＲＳＡアルゴリズムの特徴により、０以上Ｎ−１以下の任意の整数Ｍについて、下式の関係が成り立つ。
【０１４０】
M =（M^D）^E mod N  ・・・・・・・・・・・・・・・・・ （式９）
【０１４１】
メッセージＭ（１１０）に対し、秘密指数Ｄ（１６２）を指数とするべき乗を施し、さらに公開指数Ｅ（１８０）を指数とするべき乗を施し、法Ｎ（１６１）の剰余を求めれば、元のメッセージＭ（１１０）が再現される。結果として、スマートカード１２０を持つユーザの秘密指数Ｄ（１６２）は、ディジタル署名Ｃ（１１１）を、C=M^D mod Nとして生成することができ、ディジタル署名Ｃ（１１１）は、V=C^E mod Nを計算し、算出されたVを元のメッセージＭ（１１０）と照合することによって、検証されることができる。真正のディジタル署名Ｃ（１１１）については、C^E＝（M^D）E＝M mod Nが成り立ち、秘密指数Ｄ（１６２）を知ることなく真正のディジタル署名を生成する方法は、知られていない。したがって、秘密指数Ｄを漏洩から守ることが、特に重要である。
【０１４２】
以下の認証プロトコルには、このような性質を利用することができる。まず、スマートカード１２０はアクセス要求プロトコルを送信する（ステップ１９０）。リーダライタ１００は、０以上Ｎ−１以下のランダムなメッセージＭ（１１０）を生成し（ステップ１９１）、スマートカード１２０に送信する。スマートカード１２０は、ディジタル署名Ｃ（１１１）を、C=M^D mod Nとして生成し、リーダライタ１００に送り返す。リーダライタ１００は、受信したディジタル署名Ｃ（１１１）から、V=C^E mod Nを計算し（ステップ１９３）、算出されたＶを元のメッセージＭ（１１０）と比較する（ステップ１９４）。スマートカード１２０からのアクセス要求は、算出されたＶと元のメッセージＭ（１１０）が等しいときにのみ許可され（ステップ１９６）、異なるときには拒否される（ステップ１９５）。
【０１４３】
ＲＳＡ演算を保護するためには、いくつかの対策が必要である。
【０１４４】
＜ＲＳＡ演算の比較例＞  実施形態１の詳細な説明の前に、比較例として、ＲＳＡ暗号演算における一般的な実装形態について説明する。
【０１４５】
図５は、ＲＳＡ暗号演算におけるランダム化による保護動作を表すフローチャートである。メッセージＭ（１１０）はべき剰余演算の基数として入力され、さらに、秘密指数Ｄ（１６２）と法Ｎ（１６１）、ブラインディング要素Φ（N）１６３が入力される（ステップ２００）。ＲＮＧ（乱数発生器）１２３により、３つの６４ビット乱数ｒ１、ｒ２、ｒ３を生成する（ステップ２０１）。その後、入力された基数Ｍ，指数Ｄ，法Ｎはそれぞれ以下のようにランダム化される。
【０１４６】
ステップ２０２；  ランダム化されたＤ’は、Ｄ’＝Ｄ＋ｒ１×Φ（Ｎ）として算出される。ここで、Φ（Ｎ）はブラインディング要素１６３である。ランダム化されたＤ’は、コプロセッサ１２４によって乗算器１４２と加算器１４３を使って算出され、中間データ１７０の１つとしてＲＡＭ１２７に格納される。
【０１４７】
ステップ２０３；  ランダム化されたＮ’は、Ｎ’＝ｒ３×Ｎとして、コプロセッサ１２４によって乗算器１４２を使って算出され、中間データ１７０の１つとしてＲＡＭ１２７に格納される。ランダム化されたＭ’は、Ｍ’＝Ｍ＋ｒ２×Ｎとして、コプロセッサ１２４によって乗算器１４２と加算器１４３を使って算出され、中間データ１７０の１つとしてＲＡＭ１２７に格納される。
【０１４８】
ステップ２０４；  ランダム化された署名Ｃ’は、Ｃ’＝Ｍ’＾Ｄ’ mod Ｎ’として、コプロセッサ１２４によってべき剰余１４０を使って算出され、結果はＲＡＭ１２７に格納される。
【０１４９】
ステップ２０５；  最終的には、ディジタル署名Ｃは、Ｃ＝Ｃ’ mod Ｎとして、コプロセッサ１２４によってモジュラリダクション１４４を使って算出される。算出されたディジタル署名Ｃは、ＵＡＲＴ１２１を介してリーダライタ１００に送信される。
【０１５０】
ステップ２０２と２０３におけるランダム化は、差分電力解析のような攻撃に対しては、耐性を持つことが、非特許文献１などによって知られている。しかし、非特許文献２に記述されている攻撃に対しては、耐性が十分ではない可能性がある。そこで、上記のＲＳＡ暗号演算におけるランダム化による保護動作について、さらに詳しく検討する。
【０１５１】
図６は、ＲＳＡ暗号演算におけるべき乗演算の動作を表すフローチャートである。これは、図５に示したＲＳＡ演算におけるステップ２０４の一般的な実装形態の一つである。べき乗演算はＲＡＭ１２７に中間データ１７０として格納されるＣ’［０］とＣ’［１］の二つのワークスペース変数を使用して実行される。Ｃ’［０］はダミー累算値であり、Ｃ’［１］はべき乗の累算値である。まず、Ｃ’［０］＝１、Ｃ’［１］＝１に初期化される（ステップ３０１）。ステップ３０２、３１０、３１３によって、ループカウンタをｉとするｎ回のループ処理が構成される。ここで、ｎは指数Ｄ’のビット長である。２進数表示された指数Ｄ’の各桁ｄｎ−１，ｄｎ−２，…ｄ１，ｄ０を走査（スキャン）する動作に対応する。ループ内では、以下の２つのステップの演算を実行する。
【０１５２】
ステップ３１１；  Ｃ’［１］＝Ｃ’［１］＾２  ｍｏｄ  Ｎ’
ステップ３１２；  Ｃ’［ｄｉ］＝Ｃ’［１］×Ｍ’  ｍｏｄ  Ｎ’
【０１５３】
ステップ３１２では、ｄｉ＝０のとき、演算結果がダミー累算値であるＣ’［０］に代入される。Ｃ’［０］は、以降、参照されることはなく演算結果は破棄されることになり、ステップ３１２の剰余乗算はダミーとして実行されたことになる。一方、ｄｉ＝１のときは結果がＣ’［１］に格納され、ステップ３１２の演算はダミーでない。指数Ｄ’の各桁の走査（スキャン）に対応するｎ回のループ処理が完了した時点で、Ｃ’［１］には、Ｍ’＾Ｄ’  ｍｏｄ  Ｎ’が算出され、格納されることになる（ステップ３２０）。
【０１５４】
このダミー演算のおかげで、アルゴリズムの実行タイミングは入力データから独立しているので、（例えば、ｄｉが０でも１でも同じ演算が実行されるので、）差分電力解析のような攻撃に対して耐性を持つ。しかし、この演算過程には、演算の間の衝突が発生することが分かった。このため、非特許文献２に記述されている攻撃に対しては、耐性が十分ではない可能性がある。その理由を以下に示す。
【０１５５】
図７は、ＲＳＡ暗号演算のべき乗演算における演算の間の衝突を示す説明図である。ループのステップｉと次のステップｉ−１について、図６のフローチャートのステップ３１１と３１２について、実行される演算の種類と入出力の値を示したものである。
【０１５６】
ステップｉでＣ’［１］＝Ｘ、Ｃ’［０］＝Ｙ、ｄｉ＝１と仮定すると、（ａ）に示されるように、ステップｉにおける剰余乗算（２乗）の入力はＸとＸであり、出力はＸ＾２である（ステップ３１１）。次の剰余乗算の入力はＸ＾２とＭ’であり、出力はＸ＾２×Ｍ’である。次のステップｉ−１における剰余乗算（２乗）の入力はＸ＾２×Ｍ’とＸ＾２×Ｍ’であり、出力は（Ｘ＾２×Ｍ’）＾２である（ステップ３１１）。
【０１５７】
これに対し、ステップｉでＣ’［１］＝Ｘ、Ｃ’［０］＝Ｙ、ｄｉ＝０と仮定すると、（ｂ）に示されるように、ステップｉにおける剰余乗算（２乗）の入力はＸとＸであり、出力はＸ＾２である（ステップ３１１）。次の剰余乗算の入力はＸ＾２とＭ’であり、出力はＸ＾２×Ｍ’である。しかし、この代入先は、Ｃ’［１］ではなく、ダミー累算値Ｃ’［０］でありから、次のステップｉ−１における剰余乗算（２乗）の入力はＸ＾２とＸ＾２であり、出力はＸ＾４である（ステップ３１１）。
【０１５８】
ステップｉの剰余乗算とステップｉ−１の剰余乗算（２乗）でｄｉ＝１のときは入力が異なり、ｄｉ＝０のときは入力が同じであることが分かる。剰余乗算器１４１の一方の入力値が連続する実行ステップで変化しない場合には、その２回目の演算のための消費電力は、通常より低くなる。これは、剰余乗算器１４１の入力はレジスタにラッチされており、剰余乗算器１４１の消費電力はラッチされている入力のうち何ビットが反転したかに依存して増減するからである。したがって、このような入力レジスタの内容が変化しない場合には、消費電力は低くなる。その結果、消費電力の大小を観測することができれば、ｄｉ＝１かｄｉ＝０か、即ち指数Ｄ’のｉ番目のビットの値を検知することができることになる。このような消費電力の大小が、検知可能か否かは、同時に実行されている処理による消費電力を含めた全体の消費電力に占める、剰余乗算器１４１の消費電力の比率に依存する。しかし、Ｃ’［０］とＣ’［１］が中間データ１７０としてＲＡＭ１２７に格納されており、それらが演算のために、コプロセッサ１２４に内蔵されるべき剰余演算器１４１に、バス１２８を介して転送されるとすれば、その消費電力は無視できる程度に小さいとは考えられず、外部から観測される可能性がある。このため、非特許文献２に記述されている攻撃に対しては、耐性が十分ではない可能性がある。
【０１５９】
＜解決手段；  ＲＳＡ暗号のセキュアなべき乗演算（中間データの改変）＞
以上述べてきた問題を解決するための、実施形態１に係る半導体装置１の構成とその動作について、詳細に説明する。
【０１６０】
べき乗演算を含むＲＳＡ方式の演算処理を実行可能な半導体装置であって、累算値Ｃ’［１］を格納可能な記憶装置１２７と、加算器１４３と、剰余演算器１４１とを備え、以下の動作を可能に構成される。
【０１６１】
前記べき乗演算は、第１ステップ４３１と第２ステップ４３２とを含むループ処理であって、前記べき乗演算の指数（Ｄ’）の２進数表現における各桁（dn-1，…d0）に対応する少なくとも１回以上の繰り返しを含む前記ループ処理によって演算される。第１ステップ４３１において、累算値Ｃ’［１］を記憶装置１２７から読み出して任意値Ｎ’とともに加算器１４３に入力し、出力される和を記憶装置１２７に書き戻すことにより累算値Ｃ’［１］を更新する。第２ステップ４３２において、累算値Ｃ’［１］を記憶装置１２７から読み出して剰余演算器１４１に入力し、出力される剰余演算の結果を記憶装置１２７に書き戻すことにより累算値Ｃ’［１］を更新する。任意値Ｎ’は、第１ステップ４３１において累算値Ｃ’［１］を異なる値に更新する値に設定される。
【０１６２】
図８は、実施形態１のべき乗演算の動作を表すフローチャートである。これは、図５に示したＲＳＡ演算におけるステップ２０４を実装する一つの実施形態であり、図６に示した一般的な実装形態で発生する問題を解決することができる。入力（ステップ４２０）、ダミー累算値Ｃ’［０］と累算値Ｃ’［１］の初期化（ステップ４２１）、ループ処理（ステップ４２２、４３０、４３４）、及び出力（ステップ４４０）は、図６に示した一般的な実装形態の対応するステップと同様である。一方、ループ処理内は下記の３ステップで構成される。
【０１６３】
ステップ４３１；  Ｃ’［１］＝Ｃ’［１］＋Ｎ’
ステップ４３２；  Ｃ’［１］＝Ｃ’［１］＾２  ｍｏｄ  Ｎ’
ステップ４３３；  Ｃ’［ｄｉ］＝Ｃ’［１］×Ｍ’  ｍｏｄ  Ｎ’
【０１６４】
ステップ４３２と４３３は、それぞれ、図６のステップ３１１と３１２と同様であるが、その前に、ステップ４３１を実行する。ステップ４３１は、非モジュラの加算器１４３によって実行される。ステップ４３１を実行することにより、累算値Ｃ’［１］の値を変化させる。Ｎ’は剰余の法であるから、これを累算値Ｃ’［１］に加算しても、ステップ４３２と４３３の演算結果には影響を与えない。即ち、一般に下式が成り立つ。
【０１６５】
（Ｘ＋Ｎ’）×Ｙ  ｍｏｄ  Ｎ’＝Ｘ×Ｙ  ｍｏｄ  Ｎ’ ・・・・・・ （式１０）
【０１６６】
換言すれば、法Ｎ’を剰余乗算器１４１の入力に加算しても、剰余乗算の演算結果には影響しない。一方、べき乗のステップの相互関係は、排除することができる。累算値Ｃ’［１］の値自体は、ループ毎に変化するので、上で指摘したような、連続するループで同じ値がべき剰余演算器１４１に入力されるという問題は、解決される。加算する値は剰余の法Ｎ’の倍数であれば、同様の効果を奏する。これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を向上することができる。しかし、発明者がさらに詳しく検討したところ、別の演算の間の衝突が残存していることがわかった。
【０１６７】
図９は、実施形態１のべき乗演算における演算の間の衝突を示す説明図である。ループのステップｉと次のステップｉ−１について、図８のフローチャートのステップ４３１からステップ４３３について、実行される演算の種類と入出力の値を示したものである。
【０１６８】
ステップｉでｄｉ＝１と仮定すると、（ａ）に示されるように、ステップｉにおける加算の入力はＸとＮ’であり（ステップ４３１）、剰余乗算（２乗）の２つの入力はＸ＋Ｎ’であり、出力はＸ＾２である（ステップ４３２）。次の剰余乗算の入力はＸ＾２とＭ’であり、出力はＸ＾２×Ｍ’である（ステップ４３３）。次のステップｉ−１における加算の入力はＸ＾２×Ｍ’とＮ’であり（ステップ４３１）、剰余乗算（２乗）の２つの入力はＸ＾２×Ｍ’＋Ｎ’であり、出力は（Ｘ＾２×Ｍ’）＾２である（ステップ４３２）。
【０１６９】
これに対し、ステップｉでｄｉ＝０と仮定すると、（ｂ）に示されるように、ステップｉにおける加算の入力はＸとＮ’であり（ステップ４３１）、剰余乗算（２乗）の２つの入力はＸ＋Ｎ’であり、出力はＸ＾２である（ステップ４３２）。次の剰余乗算の入力はＸ＾２とＭ’であり、出力はＸ＾２×Ｍ’である（ステップ４３３）。ｄｉ＝０であるので、出力Ｘ＾２×Ｍ’はダミー累算値Ｃ’［０］に書き込まれ、累算値Ｃ’［１］は更新されない。次のステップｉ−１における加算の入力はＸ＾２とＮ’であり（ステップ４３１）、剰余乗算（２乗）の２つの入力はＸ＾２＋Ｎ’であり、出力はＸ＾４である（ステップ４３２）。
【０１７０】
ステップｉでｄｉ＝０のとき、ステップｉの剰余乗算１４１の一方の入力と、ステップｉ−１の非モジュラ演算の加算器１４３の一方の入力が、ともに同じ値Ｘ＾２となって、演算の間の衝突が発生している。この場合は、入力値は同じ値であるが、実行される演算は異なる。したがって、コプロセッサ１２４の実際の実装状態に依存するとは言え、秘密データの漏洩が発生するか否かは定かではない。例えば、仮に加算器１４２と剰余乗算器１４１が同じレジスタを共有して入力値をラッチする場合、入力値が変化しないために加算器１４２の消費電力は低くなる。しかし、加算器１４２と剰余乗算器１４１が入力値をラッチするために同じレジスタを共有しない場合には、レジスタの消費電力は、衝突によって影響されることはなく、したがって、本実施形態によれば、非特許文献２に記述されている攻撃に対して、耐タンパー性を向上することができる。
【０１７１】
〔実施形態２〕＜ＲＳＡ暗号のセキュアなべき乗演算（中間データのランダム化）＞
図１０は、実施形態２のべき乗演算の動作を表すフローチャートである。これは、図５に示したＲＳＡ演算におけるステップ２０４のべき剰余演算を実装する別の実施形態であり、図６に示した一般的な実装形態で発生する問題を解決することができる。入力（ステップ４００）、ダミー累算値Ｃ’［０］と累算値Ｃ’［１］の初期化（ステップ４０１）、ループ処理（ステップ４０２、４１０、４１９）、及び出力（ステップ４２０）は、図６に示した一般的な実装形態の対応するステップと同様である。一方、ループ処理内において、図１０のステップ４１４の剰余２乗乗算は、図６のステップ３１１に対応し、図１０のステップ４１８の剰余乗算は、図６のステップ３１２に対応する。
【０１７２】
図６に示した一般的な実装形態との違いは以下の通りである。
【０１７３】
ステップ４１４の剰余２乗乗算の前に以下の３ステップが実行される。
【０１７４】
ステップ４１１；  ６４ビットの乱数ａを生成（ＲＮＧ１２３）
ステップ４１２；  Ｎ”＝ａ×Ｎ’（非モジュラ乗算器１４２）
ステップ４１３；  Ｃ’［１］＝Ｃ’［１］＋Ｎ”（加算器１４３）
【０１７５】
ステップ４１８の剰余乗算の前に以下の３ステップが実行される。
【０１７６】
ステップ４１５；  ６４ビットの乱数ｂを生成（ＲＮＧ１２３）
ステップ４１６；  Ｎ”＝ｂ×Ｎ’（非モジュラ乗算器１４２）
ステップ４１７；  Ｃ’［１］＝Ｃ’［１］＋Ｎ”（加算器１４３）
【０１７７】
図１１は、実施形態２のべき乗演算における演算の間の衝突を示す説明図である。ループのステップｉと次のステップｉ−１について、図１０のフローチャートのステップ４１２からステップ４１８について、実行される演算の種類と入出力の値を示したものである。ステップｉでｄｉ＝１と仮定したときの入出力値の変化を（ａ）に、ステップｉでｄｉ＝０と仮定したときの入出力値の変化を（ｂ）に、それぞれ示す。
【０１７８】
（ｂ）に示したｄｉ＝０のとき、ステップｉの剰余除算（ステップ４１８）の入力１と、ステップｉ−１の加算（ステップ４１３）の入力１がともにＸ＾２＋ｂ×Ｎ’となり、衝突が生じる。図８と図９に示した実施形態１の場合と比較すると、衝突の発生／不発生がｄｉの値に依存する点と、衝突したデータに対するコプロセッサ１２４の実行する演算の種類は同じであるが、演算の実行シーケンスに違いがある。図８と図９に示した実施形態１の場合は、コプロセッサ１２４は、衝突したデータに対する剰余乗算（ステップ４３３）と加算（ステップ４３１）を連続して実行するのに対し、図１０と図１１に示した本実施形態２では、衝突したデータに対する剰余除算（ステップ４１８）と加算（ステップ４１３）との間に非モジュラ乗算（ステップ４１２）が実行される点で異なる。仮に剰余除算（ステップ４１８）と加算（ステップ４１３）とが、同じレジスタを共有して入力値を保持する実装を採ったとしても、そのレジスタの値は、その２つの演算に挟まれる非モジュラ乗算（ステップ４１２）の入力ａによって、一旦書き換えられるので、演算の間の衝突による消費電力の低下は観測されない。
【０１７９】
これにより、べき乗演算を含むＲＳＡ／ＤＳＡ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性をさらに向上することができる。
【０１８０】
本実施形態２は、図１０と図１１に例示した形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。例えば、乱数ａとｂは、同じ値でもよく、ループの前に１度だけ生成されても良く、またさらに、予め生成された乱数をプログラムの中にハードコードとして埋め込んでおいてもよい。ａ＝ｂ＝１とした場合には、実施形態１となる。同様に、ステップ４１３と４１７の「＋ａ×Ｎ’」と「＋ｂ×Ｎ’」は、「＋Ｎ’」の繰り返しで実装してもよい。換言すれば、本実施形態は、繰り返しループの中の加算の回数を、１ループあたり１回または２回に限定するものではなく、任意の整数の非モジュラ乗算を含むこともできる。
【０１８１】
〔実施形態３〕＜ＲＳＡ暗号のセキュアなべき乗演算（ダミー中間データ）＞
実施形態３では、さらに耐タンパー性を向上した実施の形態を示す。
【０１８２】
まず、実施形態２によってもなお残存する問題点について、以下に説明する。
【０１８３】
実施形態２では、仮に演算の間の衝突が発生しても、その影響が観測不能とすることができるために、耐タンパー性を向上することができる実施形態を示した。しかしながら、衝突の発生自体を抑えるわけではないので、この実施形態では、ハードウェアのアーキテクチャによっては、なお秘密データを漏洩させる可能性が潜在する。例えば、この実施形態２では、コプロセッサ１２４の加算器１４３と剰余乗算器１４１は、共に、バス１２８を介してＲＡＭ１２７からデータをロードする。バス１２８がプリチャージバスである場合、ステップ４１８の剰余乗算のためのデータのロードと、ステップ４１３の加算のためのデータのロードは、その値が同じであるために、バス１２８の消費電力は同じ値となる。暗号演算の場合、データは多倍長であるため、データの転送には複数サイクルを要する。その結果、ステップ４１８とステップ４１３の入力データのロードのときに、消費電力に同じ波形、実際には自己相関の高い波形が観測される可能性がある。衝突の発生／不発生がｄｉの値に依存するため、観測された消費電力に発生する波形の自己相関が高いか否かによって、ｄｉの値を検知することができる。ステップ４１８とステップ４１３で自己相関が高い波形が観測されたときはｄｉ＝０であり、自己相関が高くない波形が観測されたときはｄｉ＝１であると、判断することができるからである。
【０１８４】
以上は、あくまでも実施形態２に内在する、データ漏洩の潜在的な可能性を示すに過ぎず、この可能性はハードウェアアーキテクチャに強く依存する点に注意すべきである。実施形態２において適切なハードウェアアーキテクチャを採用すれば、データ漏洩の潜在的な可能性を、実用上無視できる程度に低く抑えることができる。例えば、バスをランダム化または暗号化し、または加算器１４３と剰余乗算器１４１のデータの入出力のためのバスを、それぞれ独立に設けるなどの対策により、上述のような攻撃は、無効化することができる。
【０１８５】
図１２は、実施形態３のべき乗演算の動作を表すフローチャートである。これは、図５に示したＲＳＡ演算におけるステップ２０４を実装する別の実施形態であり、図８と図１０に示した実施形態1と実施形態２とをさらに改善するものである。図１２を引用して説明する実施形態３に係る実施の形態は、例えばバスのランダム化などの特別なハードウェアアーキテクチャを前提としない点で好適である。
【０１８６】
入力（ステップ５００）、ダミー累算値Ｃ’［０］と累算値Ｃ’［１］の初期化（ステップ５０１）、ループ処理（ステップ５０２、５１０、５１５）、及び出力（ステップ５２０）は、図６に示した一般的な実装形態の対応するステップと同様である。一方、ループ処理内において、図１２のステップ５１１、５１２及び５１４は、それぞれ図８のステップ４３１、４３２及び４３３に対応する。本実施形態３では、ステップ５１４の前に、ｄｉ＝１のときにはダミー累算値Ｃ’［０］をＣ’［０］＝Ｃ’［１］＋Ｎ’のように更新し、ｄｉ＝０のときには累算値Ｃ’［１］をＣ’［１］＝Ｃ’［１］＋Ｎ’のように更新する、ステップ５１３を追加している。
【０１８７】
図１３は、実施形態３のべき乗演算における演算の間の衝突を示す説明図である。ループのステップｉと次のステップｉ−１について、図１２のフローチャートのステップ５１１からステップ５１４について、実行される演算の種類と入出力の値を示したものである。ステップｉでｄｉ＝１と仮定したときの入出力値の変化を（ａ）に、ステップｉでｄｉ＝０と仮定したときの入出力値の変化を（ｂ）に、それぞれ示す。
【０１８８】
（ａ）に示したｄｉ＝１と（ｂ）に示したｄｉ＝０の両方で、ステップｉの加算（ステップ５１３）の入力１と剰余乗算（ステップ５１４）の入力１がともにＸ＾２となり、衝突が生じる。しかし、衝突はｄｉ＝１とｄｉ＝０のときの両方で生じるのでセキュリティには問題がない。
【０１８９】
また、下記のような演算の間の衝突がなお存在する。
【０１９０】
ｄｉ＝１（ａ）のとき、ステップｉの剰余除算（ステップ５１４）の出力と、ステップｉ−１の加算（ステップ５１１）の入力１がともにＸ＾２×Ｍ’となり、衝突が生じる。
【０１９１】
ｄｉ＝０（ｂ）のとき、ステップｉの加算（ステップ５１３）の出力と、ステップｉ−１の加算（ステップ５１１）の入力１がともにＸ＾２＋Ｎ’となり、衝突が生じる。
【０１９２】
しかしながら、これらの衝突を外部から観測することは実用上不可能であって、セキュリティには問題がない。その理由は、以下の３点である。
【０１９３】
非モジュラ演算の加算は、剰余乗算などのモジュラ演算に比べ非常に短く、それによって、攻撃の機会のウィンドウを縮小する。
【０１９４】
非モジュラ演算の加算と剰余乗算は本質的に異なり、またそれぞれ強相関を示さない異なったハードウェアによって演算される。
【０１９５】
メモリの入力動作と出力動作の物理的な違いによって、入力値と出力値の相関関係は消滅する。
【０１９６】
本実施形態３は、図１２と図１３に例示した形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。例えば、図１２においては、べき乗演算のためのループ１回あたり、累算値に対して２度の剰余の加算が実行されるが、実施形態１（図８）に示したように、１回だけの加算でもよく、２回以上の加算でも、さらに複数回の加算の代わりに剰余の倍数を加算してもよい。この複数回は乱数の回数であってよく、非モジュラ加算器による実装だけではなく、非モジュラ乗算器を使って実装される形態を含む。
【０１９７】
〔実施形態４〕＜ＥＣＣ暗号のセキュアなべき乗演算＞
図１４は、代表的な実施の形態に係る半導体装置の構成、及び、それをＥＣＣ演算を行うスマートカードに搭載したシステムの構成例を表すブロック図である。
【０１９８】
図３に示した実施形態１に係る半導体装置の構成、及び、それをＲＳＡ暗号演算を行うスマートカード１２０に搭載したシステムと同様に、スマートカード６２０は、ＵＡＲＴ６２１をインターフェースとしてリーダライタ６００と接続され、通信を行う。非接触の場合は、ＵＡＲＴ６２１に代えて無線通信インターフェースを備えればよい。スマートカード６２０は、スマートカード１２０と同様に、ＵＡＲＴ６２１、ＣＰＵ６２２、乱数発生器（ＲＮＧ）６２３、コプロセッサ６２４、ＲＯＭ６２５、ＥＥＰＲＯＭ６２６、及び、ＲＡＭ６２７を備え、バス６２８を介して互いに接続されている。ＲＳＡ演算の代わりに楕円曲線暗号（ＥＣＣ：Elliptic Curve Cryptography）を行う。数学的な慣例上、加法は乗法の代わりにＥＣＣ演算を表すために使われる。例えば、楕円曲線群の演算は「指数」よりも「べき乗」と「スカラー」よりも「乗算」、「２乗」と「スカラー倍演算」よりも「加算」または「２倍算」の楕円曲線点として参照されることがしばしばである。しかし、二つの表記法は等値であり、スカラー倍演算は実際、楕円曲線点によって構成される群ではべき乗である。ＥＣＣのついての詳細は、例えば下記の公知文献に記載されている。
【０１９９】
Darrel Hankerson，Alfred Menezes，Scott Vanstone: "Guide to Elliptic Curve Cryptography"，Springer
【０２００】
これに伴って、コプロセッサ６２４は、群演算を行う、べき剰余演算器６４０、剰余乗算器６４１、モジュラリダクション器６４４、及び、非モジュラ演算器６４８として乗算器６４２と加算器６４３とを備える他、さらに、ＥＣＣスカラー倍演算６４５、楕円曲線点加算（ＥＣＡＤＤ）６４６、及び、楕円曲線点２倍算（ＥＣＤＢＬ）６４７を実行可能に構成される。ＲＯＭ６２５には、ＣＰＵ６２２で実行されるプログラム６５０、共通データ６５１、ＥＣＣのプログラム６５２が格納されている。これらは、ＣＰＵ６２２の制御により、コプロセッサ６２４にも供給されることができる。ＥＥＰＲＯＭ６２６には、スマートカードのデータ６６０、スカラー（ｄ）６６１、法（ｐ）６６２、及び、曲線のパラメータ６６３が格納されている。ＲＡＭ６２７には、ＲＳＡ演算の中間データ６７０と中間データの一つである、共通点（Ｑ＝ｄ×Ｐ）６１１が格納されている。
【０２０１】
スマートカード６２０はＵＡＲＴ６２１を介して、リーダライタ６００と通信する。一例としてEC Diffie-Hellman（ECDH）式の鍵交換プロトコルについて説明する。リーダライタ６００は、公開鍵を表わす、点（Ｐ）６１０を送信する。スマートカード６２０は、ＥＥＰＲＯＭ６２６に格納されている、秘密鍵を表すECCスカラー（ｄ）６６１と、ECCパラメータである曲線のパラメータ６６３と、楕円曲線の定義体として用いている有限体（「体」は群論における演算によって定義される集合の一種、英語では“field”）の剰余の法（ｐ）６６２とを使用して、共有点（Q=d*P）６１１を生成する。生成された共有点（Q=d*P）６１１は、ＲＡＭ６２７に格納され、スマートカード６２０とリーダライタ６００で共有される共通鍵を導出するなどのさまざまな目的で、後に使用可能である。
【０２０２】
ＥＣＣ演算は、ＣＰＵ６２２がＲＯＭ６２５に格納されているプログラム６５２を実行することによって、コプロセッサ６２４を使用しながら実行する演算によって実現され、また、その演算途中の中間データ６７０はＲＡＭ６２７に格納される。ＥＣＣ演算は、時間のかかる多倍長演算を伴うため、演算を速めるためにコプロセッサ６２４を備えるのが好適であり、図３のコプロセッサ１２４にサポートされる演算に加え、ＥＣＣスカラー倍演算６４５、楕円曲線点加算（ＥＣＡＤＤ）６４６、及び、楕円曲線点２倍算（ＥＣＤＢＬ）６４７の各演算を実行可能に構成される。楕円曲線点加算（ＥＣＡＤＤ）６４６と楕円曲線点２倍算（ＥＣＤＢＬ）６４７は、図１９と図２０を引用して後述するように、剰余乗算６４１、モジュラ加減算６４９、及び非モジュラ演算６４８を使った、固定コードのシーケンスとして実装される。
【０２０３】
一般にＥＣＣ演算を保護するためには、いくつかの対策が必要である。
【０２０４】
＜ＥＣＣ演算の比較例＞  実施形態４の詳細な説明の前に、比較例として、ＥＣＣ演算における一般的な実装形態について説明する。
【０２０５】
図１５は、ＥＣＣ演算におけるランダム化による保護動作を表すフローチャートである。
【０２０６】
座標（ｘｐ，ｙｐ）で表される点（Ｐ）６１０がリーダライタ６００から入力され、スカラー（ｄ）６６１と法（ｐ）６６２がＥＥＰＲＯＭ６２６から読み出される（ステップ７００）。ＲＮＧ６２３を使ってランダムな座標ｚを生成する（ステップ７０１）。座標（ｘＰ，ｙＰ）はそれぞれランダムな座標ｚを乗じられ、ｐ（６６２）を法とする剰余演算により、ランダム化された射影座標（ｘＰ’，ｙＰ’）が算出される（ステップ７０２）。ランダム化された点Ｐ’の座標は（ｘＰ’，ｙＰ’，ｚ）となる（ステップ７０３）。
【０２０７】
次に共有点（Q=d*P）６１１の座標を算出する。コプロセッサ６２４によるスカラー倍演算６４５により、Ｑ’＝ｄ×Ｐ’＝（ｘＱ’，ｙＱ’，ｚＱ’）を求め、結果はＲＡＭ６２７に格納される（ステップ７０４）。Ｑ’が射影座標として表されるため、アフィン座標に変換されなければならない。モジュラ逆数１／ｚＱ  ｍｏｄ  ｐはモジュラべき乗６４０を使用して、ｚＱ’＾（ｐ−２）  ｍｏｄ  ｐとして演算される（ステップ７０５）。最後に、座標ｘＱ’とｙＱ’は、剰余乗算６４１を使用して逆数ｚＱ’を乗じられ、アフィン座標ｘＱとｙＱが求められ（ステップ７０６）、共有点Ｑ＝（ｘＱ，ｙＱ）＝ｄ×Ｐが出力される（ステップ７１０）。
【０２０８】
以上述べてきたランダム座標ｚによるランダム化は、差分電力解析のような攻撃に対しては、耐性を持つことが、非特許文献１などによって知られている。しかし、非特許文献２に記述されている攻撃に対しては、耐性が十分ではない可能性がある。そこで、上記のＥＣＣ演算におけるランダム化による保護動作について、さらに詳しく検討する。
【０２０９】
図１６は、ＥＣＣ演算におけるべき乗演算の動作を表すフローチャートである。これは、図１５に示したＥＣＣ演算におけるステップ７０４の一般的な実装形態の一つであり、モンゴメリラダー法のスカラー倍演算を基にしている。べき乗演算はＲＡＭ６２７に中間データ６７０として格納されるＱ’［０］とＱ’［１］の二つのワークスペース変数を使用して実行される。
【０２１０】
Ｑ’［０］とＱ’［１］はｘ，ｙ，ｚの３つの射影座標として表される楕円曲線点である。図６〜１３に記述のモジュラべき乗とは異なり、図１６のスカラー倍演算はダミー演算を使用しない。
【０２１１】
まず、Ｑ’［０］＝Ｐ’、Ｑ’［１］＝無限点∞に初期化される（ステップ８０１）。無限点はECDBL（∞）=∞とECADD（P,∞）=Pの楕円曲線の単位元である。
【０２１２】
ステップ８０２、８１０、８１３によって、ループカウンタをｉとするｎ回のループ処理が構成される。ここで、ｎはスカラーｄ（６６１）のビット長である。２進数表示されたスカラーｄ（６６１）の各桁ｄｎ−１，ｄｎ−２，…ｄ１，ｄ０を走査（スキャン）する動作に対応する。ループ内では、以下の２つのステップの演算を実行する。
【０２１３】
ステップ８１１；  Ｑ’［ｄｉ］＝ＥＣＡＤＤ（Ｑ’［ｄｉ］，Ｑ’［ＮＯＴ（ｄｉ）］）
ステップ８１２；  Ｑ’［ＮＯＴ（ｄｉ）］＝ＥＣＤＢＬ（Ｑ’［ＮＯＴ（ｄｉ）］）
【０２１４】
スカラービットｄｉ＝１の場合、ＥＣＡＤＤ６４６を使用して、Ｑ’［１］にはＱ’［０］が加算されてＲＡＭ６２７のＱ’［１］に再度格納され（ステップ８１１）、Ｑ’［０］はＥＣＤＢＬ６４７により２倍算され、ＲＡＭ６２７のＱ’［０］に再度格納される（ステップ８１２）。
【０２１５】
逆に、スカラービットｄｉ＝０の場合、ＥＣＡＤＤ６４６を使用して、Ｑ’［０］にはＱ’［１］が加算されてＲＡＭ６２７のＱ’［０］に再度格納され（ステップ８１１）、Ｑ’［１］はＥＣＤＢＬ６４７により２倍算され、ＲＡＭ６２７のＱ’［１］に再度格納される（ステップ８１２）。
【０２１６】
スカラーｄ（６６１）の各桁の走査（スキャン）に対応するｎ回のループ処理が完了した時点で、Ｑ’［１］には、ｄ×Ｐ’が算出され、格納されることになる（ステップ８２０）。
【０２１７】
この実装形態は、モンゴメリラダー法の特質から、タイミングは入力データから独立しており、いくつかの攻撃に対して耐性がある。しかし、この演算過程には、演算の間の衝突が発生することが分かった。このため、非特許文献２に記述されている攻撃に対しては、耐性が十分ではない可能性がある。その理由を以下に示す。
【０２１８】
図１７は、ＥＣＣ演算の比較例のべき乗演算における演算の間の衝突を示す説明図である。ループのステップｉと次のステップｉ−１について、図１６のフローチャートのステップ８１１と８１２について、実行される演算の種類と入出力の値を示したものである。ステップｉでｄｉ＝１、ｄｉ−１＝１と仮定したときの入出力値の変化を（ａ）に、ステップｉでｄｉ＝０、ｄｉ−１＝０と仮定したときの入出力値の変化を（ｂ）に、ステップｉでｄｉ＝１、ｄｉ−１＝０と仮定したときの入出力値の変化を（ｃ）に、ステップｉでｄｉ＝０、ｄｉ−１＝１と仮定したときの入出力値の変化を（ｄ）に、それぞれ示す。
【０２１９】
図６に示したべき剰余演算とは異なり、ｄｉとｄｉ−１のビットパターンに依存することなく発生するので、複数の入力の間の衝突は問題ではないが、入力と出力の間の衝突が問題となることがわかった。
【０２２０】
ｄｉとｄｉ−１の値が同じ値の場合、即ち、ｄｉ＝１、ｄｉ−１＝１（ａ）とｄｉ＝０、ｄｉ−１＝０（ｂ）の場合、以下の衝突が発生する。
【０２２１】
ステップｉのＥＣＡＤＤの出力とステップｉ−１のＥＣＡＤＤの入力１
ステップｉのＥＣＤＢＬの出力とステップｉ−１のＥＣＡＤＤの入力２及びＥＣＤＢＬの入力。
【０２２２】
ｄｉとｄｉ−１の値が異なる値の場合、即ち、ｄｉ＝１、ｄｉ−１＝０（ｃ）とｄｉ＝０、ｄｉ−１＝１（ｄ）の場合、以下の衝突が発生する。
【０２２３】
ステップｉのＥＣＡＤＤの出力とステップｉ−１のＥＣＡＤＤの入力２及びＥＣＤＢＬの入力
ステップｉのＥＣＤＢＬの出力とステップｉ−１のＥＣＡＤＤの入力１。
【０２２４】
ｄｉとｄｉ−１の値が同じ値か異なる値かによって、衝突の発生パターンが変わるので、逆に衝突の位置を観測することによって、ｄｉとｄｉ−１の値が同じ値か異なる値かを推測することができる。
【０２２５】
ＥＣＣ演算の状況は、ＲＳＡ演算に比べて、一見深刻ではないように見える。なぜなら、衝突は出力と入力の間で発生し、また、ＥＣＣのデータ長はＲＳＡの場合よりも短いため、衝突時間が短くなる。しかし、ＥＣＡＤＤとＥＣＤＢＬの実行シーケンスの内部をさらに詳しく解析すると、他の衝突の問題も発生することが分かった。
【０２２６】
通常のハードウェアアーキテクチャでは、入出力間の衝突を検出することは困難である。入力と出力とは、通常、同じハードウェア資源を共有しないからである。しかし、ＥＣＡＤＤとＥＣＤＢＬは、複雑な演算であって、複数のモジュラ演算のシーケンスとして実装されることが多い。特に、もしＥＣＡＤＤとＥＣＤＢＬのｘ、ｙ、ｚの３出力のうちの１つが、ＥＣＡＤＤとＥＣＤＢＬの実行シーケンスの内部では、モジュラ演算の入力として使われる場合には、実際の衝突は入出力間ではなく、複数の入力間の衝突となる。
【０２２７】
図１８は、比較例のべき乗演算の動作を表すフローチャートであり、図１６のステップ８１１と８１２におけるＥＣＡＤＤ６４６とＥＣＤＢＬ６４７の一般的な実装例である。この実装例は、剰余乗算器６４１とモジュラ加減算６４９を使う。モジュラ加減算６４９におけるモジュラ加算ｘ＋ｙ  ｍｏｄ  ｐは、下記のように非モジュラ加減算器６４３を使って実装することができる。
【０２２８】
サブステップ１：  ｗ＝ｘ＋ｙ
サブステップ２：  ｚ＝ｗ−ｐ
サブステップ３：  ｉｆ  ｚ＞＝０，ｔｈｅｎ  ｚを出力  ；  ｅｌｓｅ  ｗを出力
ｗが出力される場合には、サブステップ２は不要であり、ダミー演算となる。
【０２２９】
同様に、モジュラ減算ｘ−ｙ  ｍｏｄ  ｐは、下記のように非モジュラ加減算器６４３を使って実装することができる。
【０２３０】
サブステップ１：  ｗ＝ｘ−ｙ
サブステップ２：  ｚ＝ｗ＋ｐ
サブステップ３：  ｉｆ  ｗ＞＝０，ｔｈｅｎ  ｗを出力  ；  ｅｌｓｅ  ｚを出力
この場合も、ｗが出力される場合には、サブステップ２は不要であり、ダミー演算となる。
【０２３１】
また、同様の実装が剰余乗算にも適用することができ、その場合も最後の引き算は、結果的にダミー演算となる場合がある。
【０２３２】
図１８では、演算の間の衝突を丸印で示す。また、単純化のため、ＥＣＡＤＤの出力ｙＲと、ＥＣＡＤＤの入力ｙＰとｙＱ、及び、ＥＣＤＢＬの出力ｙＰとの間の衝突のみを示し、他の衝突は図示を省略する。
【０２３３】
ＥＣＡＤＤの出力ｙＲは、以下の複数の地点で使用される。
【０２３４】
ＥＣＤＢＬのステップ７における剰余乗算の入力１、
ＥＣＤＢＬのステップ８における剰余乗算の入力１、
ＥＣＤＢＬのステップ１４における剰余乗算の入力１と入力２、
ｄｉ＝１のときのＥＣＡＤＤのステップ７における剰余乗算の入力１、
ｄｉ＝０のときのＥＣＡＤＤのステップ７における剰余乗算の入力２。
【０２３５】
以上のように、出力値ｙＲがＥＣＡＤＤとＥＣＤＢＬの後続ステップにおける複数の入力値との間で、衝突を発生させることがわかる。さらに悪いことに、出力値ｙＲは出力値としてだけではなく、内部では入力値として使われることもある。例えば、ステップ９０２に、ＥＣＡＤＤのステップ２１におけるモジュラ減算６４９の非モジュラ加減算器６４３によるさらに詳細な実装例を示す。ステップ９０２のサブステップ３ではｙＲが正であればｗは破棄されるが、出力値ｙＲはサブステップ２の入力にも使われることになる。
【０２３６】
以上検討したように、ＲＳＡ演算とは異なり、ＥＣＣ演算では衝突は多数の地点で発生することがわかった。これは、ＥＣＣ演算ではデータ長が短いという優位性を減殺するものである。また、ＲＳＡ演算の場合と同様に、いくつかの演算の入力の間で、衝突が発生することがわかった。したがって、非特許文献２に記述されているような攻撃に対しては、ＥＣＣ演算はＲＳＡ演算と同様に、耐性が十分ではない可能性があることがわかった。
【０２３７】
＜解決手段；  ＥＣＣ暗号のセキュアなべき乗演算＞
以上述べてきた問題を解決するための、実施形態４に係る半導体装置１の構成とその動作について、詳細に説明する。実施形態４に係る半導体装置１の構成は図１４に示す通りであり、図１５に示したランダム化による保護も、そのまま適用することができる。
【０２３８】
図１９は、べき乗演算の動作を表すフローチャートであり、図１６のステップ８１１と８１２におけるＥＣＡＤＤ６４６とＥＣＤＢＬ６４７の実施形態４による実施の形態である。図１９に示すＥＣＡＤＤ６４６とＥＣＤＢＬ６４７の実施形態は、図１６に示すようなスカラー乗算アルゴリズムと組み合わせて実装される。図１８に示した一般的な実装の形態からの改善点は以下の通りである。
【０２３９】
ステップ１００１において、入力点Ｐ＝（ｘＰ，ｙＰ，ｚＰ）及びＱ＝（ｘＱ，ｙＱ，ｚＱ）の座標に、値ａが乗算される。群演算ＥＣＡＤＤ６４６に先立って、入力をａとする非モジュラ乗算６４２が実行される。
【０２４０】
同様にステップ１０２１において、入力点Ｐ＝（ｘＰ，ｙＰ，ｚＰ）の座標に、値ｂが乗算される。群演算ＥＣＤＢＬ６４７に先立って、入力をｂとする非モジュラ乗算６４２が実行される。
【０２４１】
ステップ１００２とステップ１０２２における全ての法ｐの剰余減算は、ダミー演算を含まない、値ｐの非モジュラ演算に、機械的に置き換えられている。例えばＥＣＡＤＤのステップ２１では、図１８の剰余除算ｙＲ＝ｙＲ−ｔ３  ｍｏｄ  ｐが、図１９のＥＣＡＤＤのステップ２１のように、ダミー演算を使わない非モジュラ演算ｙＲ＝ｙＲ−ｔ３＋ｐに置き換えられている。ＥＣＡＤＤのステップ３、１０、１４、１５、１６、１９、及び、ＥＣＤＢＬのステップ１７、１８、２０、２２も同様である。
【０２４２】
ステップ１００２とステップ１０２２における全ての法ｐの剰余加算は、非モジュラ演算に、機械的に置き換えられている。ＥＣＤＢＬのステップ４、５、６、９、１０がこれにあたる。
【０２４３】
前２者の改善点である、ステップ１００１とステップ１０２１において、それぞれ、座標に値ａとｂを乗じたことにより、出力と入力との衝突はなくなり、入力の間の衝突に限定することができる。図１８に示した比較例では、繰り返しステップｉの出力ｘＲ，ｙＲ，ｚＲが次のステップｉ−１の入力ｘＰ，ｙＰ，ｚＰと同じ値となる可能性があるので、衝突が発生していたが、座標に値ａ、ｂを乗じることにより、各ステップで必ず異なる座標値となるため、出力と入力の衝突は解消する。したがって、図１８に示した比較例に対して、より少ない地点のみで、衝突が発生することとなる。ここで、値ａとｂは、それぞれ、０か１以外の値であれば任意の固定値でよく、乱数である必要もないため、プログラムで定数として保持される固定値として実装することもできる。
【０２４４】
他の２つの改善点である、ダミー演算のない非モジュラ演算への置き換えにより、演算の間の衝突の発生を、ステップ１００２とステップ１０２２の剰余乗算の出力と、ステップ１００１とステップ１０２１の非モジュラ演算の入力の間でのみに抑えることができる。
【０２４５】
まとめると、以上の改善により、演算の間の衝突は、ごく限られた数のごく短時間の演算の期間に発生し、且つ、入出力間のみの発生に抑えることができる。
【０２４６】
これにより、べき乗演算を含むＥＣＣ方式の演算処理を実行可能な半導体装置において、演算の間の衝突を利用した攻撃に対する、耐タンパー性を著しく向上することができる。
【０２４７】
以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。例えば、値ａとｂは、毎回生成される乱数として与えてもよく、ａとｂは同じ値でも良い。また、他の実施形態と同様に、耐タンパー性の向上の効果は、ハードウェアアーキテクチャに依存するので、ステップ１００１とステップ１０２１を実装しない実施形態によっても、一定の効果を期待することができる。また、ステップ１００１とステップ１０２１において、非モジュラ乗算の代わりに法ｐ（６６２）またはｐの倍数の加算を用いても、同様の効果を得られる。
【符号の説明】
【０２４８】
１、１２０、６２０  半導体装置（ＬＳＩ、マイコン、スマートカード）
２、１２７、６２７  記憶装置（レジスタ、ＲＡＭ）
３、１４３、６４２  非剰余演算器（加算器、乗算器）
４、１４１、６４１  群演算器（剰余演算器）
５、１７０、６７０  累算値（中間データ）
６  任意値
７  ループ制御部
１００、６００  リーダライタ
１１０  メッセージＭ
６１０  点Ｐ
１１１  署名Ｃ
１２１、６２１  ＵＡＲＴ
１２２、６２２  ＣＰＵ
１２３、６２３  乱数発生器（ＲＮＧ）
１２４、６２４  コプロセッサ
１２５、６２５  ＲＯＭ
１２６、６２６  ＥＥＰＲＯＭ
１２７、６２７  ＲＡＭ
１２８、６２８  バス
【図１】
2014145958.tif 000003
【図２】
2014145958.tif 000004
【図３】
2014145958.tif 000005
【図４】
2014145958.tif 000006
【図５】
2014145958.tif 000007
【図６】
2014145958.tif 000008
【図７】
2014145958.tif 000009
【図８】
2014145958.tif 000010
【図９】
2014145958.tif 000011
【図１０】
2014145958.tif 000012
【図１１】
2014145958.tif 000013
【図１２】
2014145958.tif 000014
【図１３】
2014145958.tif 000015
【図１４】
2014145958.tif 000016
【図１５】
2014145958.tif 000017
【図１６】
2014145958.tif 000018
【図１７】
2014145958.tif 000019
【図１８】
2014145958.tif 000020
【図１９】
2014145958.tif 000021