JP2009500710A

JP2009500710A - 攻撃又は解析に対してデータ処理装置を保護するための装置及び方法

Info

Publication number: JP2009500710A
Application number: JP2008519041A
Authority: JP
Inventors: ゲラルドゥスタルシシウスマリアフベルト
Original assignee: Koninklijke Philips NV; Koninklijke Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 2005-06-29
Filing date: 2006-06-23
Publication date: 2009-01-08
Also published as: EP1899803A2; WO2007000701A2; US20100287384A1; CN101213512A; WO2007000701A3

Abstract

特に秘密鍵を見出すことを目的とした、例えば電磁放射（ＥＭ）攻撃のような攻撃、又は例えば差分電力解析（ＤＰＡ）のような解析が安全に回避される、少なくとも１つのデータ処理装置、特に例えば少なくとも１つのチップカード又はスマートカードのような少なくとも１つの埋め込みシステムを、少なくとも１つの攻撃、特に例えば少なくとも１つの電流追跡解析のような少なくとも１つのサイドチャネル攻撃から保護するための装置及び方法であって、前記データ処理装置、特に前記データ処理装置の少なくとも１つの集積回路が、計算、特に暗号演算を実行する装置及び方法を更に発展させるため、少なくとも１つのランダム的な変数により、前記計算の全ての中間結果を隠蔽することが提案される。

Description

本発明は、一般的には、暗号解析を防ぐ技術分野に関し、特に少なくとも１つの攻撃に対して、例えば少なくとも１つの電磁（Electro Magnetic、ＥＭ）放射攻撃に対して、又は少なくとも１つの解析に対して、例えば少なくとも１つの差分電力解析（Differential Power Analysis、ＤＰＡ）に対して、少なくとも１つのデータ処理装置を保護する技術分野に関する。

更に詳細には、本発明は、少なくとも１つのデータ処理装置、特に例えば少なくとも１つのチップカード又はスマートカードのような少なくとも１つの埋め込みシステムを、少なくとも１つの攻撃、特に例えば少なくとも１つの電流追跡解析のような少なくとも１つのサイドチャネル攻撃から保護するための装置及び方法であって、前記データ処理装置、特に前記データ処理装置の少なくとも１つの集積回路が、計算、特に暗号演算を実行するための装置及び方法に関する。

特にチップカード又はスマートカードのような埋め込みシステムのようなデータ処理装置は、鍵を交換するために公開鍵基盤（ＰＫＩ）システムを利用し、秘密鍵を見出すことを目的とする幾つかの形態の攻撃に対して保護される必要がある。斯かる攻撃の１つは、
−チップ上の、特にむき出しの（従って光に敏感な）チップ上の、１以上の光源、又は
−チップ上の、何らかの種類の電磁（ＥＭ）放射源
を目標とすることにより、計算、特に暗号演算に影響を与えることである。

ＲＳＡ（Rivest-Shamir-Adleman）アルゴリズム及び／又は楕円曲線暗号（Elliptic Curve Cryptography、ＥＣＣ）アルゴリズムに基づく計算のためには、多くの乗算が必要とされる。通常これらの計算は、例えば電流追跡解析のような、サイドチャネル攻撃に対する保護なく実行される。

このことは、ＤＰＡ攻撃に対して脆弱であり得る。なぜなら、同一の乗算が実行される度に、攻撃者が多くの電流追跡を為し得るからである。これらの追跡を加算した後には、ノイズの殆どが除去される。攻撃者が異なる入力に対し同一のことを実行すると、該攻撃者は電流追跡を比較し、ビット毎に秘密鍵を知ることができる。

国際特許出願公開WO01/97009A1の先行技術文献は、モジュール型のべき乗ルーティンを有する暗号計算のための方法を開示している。該既知の方法は、中間結果を隠蔽するための２つのランダム的な変数を用いて動作する。これに関連して、国際特許出願公開WO01/97009A1の先行技術は、ランダム的な変数の加算を用いて動作するが、乗算演算のみが隠蔽される。

しかしながら、結果が次の計算のために利用される前に、該結果は最初に隠蔽されず、該結果はやはり脆弱になる。乗算はＤＰＡに対して敏感であるのみならず、隠蔽されていない結果のランダムアクセスメモリ（ＲＡＭ）のアクセスに対しても敏感である。

Jean-Sebastien Coron及びLouis Goubinによる先行技術の論文「On Boolean and Arithmetic Masking against Differential Power Analysis」は、ＤＰＡ攻撃を議論し、全ての入力及び出力をマスキングすることを提案している（第２頁、第４及び５段落）。第５段落は乗算によるＲＳＡのマスキングを議論しており、Thomas S. Messergesによる「Securing the AES Finalists Against Power Analysis Attacks」（FSE 2000、Springer-Verlag）に参照が為されている。

Radu Muresanによる先行技術の論文「Modeling and applications of current dynamics in a complex processor core」は、ＥＣＣを適用する前に楕円曲線上の点を隠蔽することを言及している（第33乃至37頁）。

本発明の技術的な背景に関して、更なる参照が、以下に対して為され得る：
−Luca Benini、Angelo Galati、Alberto Macii、Enrico Macii及びMassimo Poncinoによる先行技術の論文「Energy-Efficient Data Scrambling on Memory-Processor Interfaces」、
−Tom Lashによる先行技術の論文「A Study of Power Analysis and the Advanced Encryption Standard - Recommendations for Designing Power Analysis Resistant Devices」、
−欧州特許出願公開EP1267514A9、
−英国特許出願公開GB2345229A、
−米国特許出願公開US2003/0194086A1、
−国際特許出願公開WO00/42511A1、
−国際特許出願公開WO01/08012A1、
−国際特許出願公開WO02/50658A1、
−国際特許出願公開WO03/101039A1、及び
−Larry T. McDaniel IIIによる先行技術の論文「An Investigation of Differential Power Analysis Attacks on FPGA-based Encryption Systems」。

上述した欠点及び短所を発端とし、議論されたような先行技術を考慮に入れ、本発明の目的は、本技術分野における上述したような装置、及び本技術分野における上述したような種類の方法を更に発展させ、特に秘密鍵を見出すことを目的とした、例えばＥＭ放射攻撃のような攻撃、又は例えばＤＰＡのような解析を、安全に回避することを可能とすることにある。

本発明の目的は、請求項１の特徴を有する装置、及び請求項７の特徴を有する方法により達成される。本発明の有利な実施例及び好適な改良は、それぞれの従属請求項に開示される。

本発明は主に、非脆弱性、特にＤＰＡに対する非脆弱性を提供するため、中間結果を隠蔽するための装置及び方法を利用するという発想に基づく。とりわけ、斯かる隠蔽は、少なくとも１つのランダム的な変数を利用することにより、計算、特に暗号演算に含まれる乗算において利用される。

より具体的には、メッセージMが変数Vによって隠蔽されることができる。該変数Vは、ランダム的に選択された変数vから導出されることができる。このようにして、全ての中間結果もが隠蔽される。これら中間結果は、計算の終了まで、特に暗号演算の終了まで、隠蔽されたままとなる。

本発明の好適な実施例によれば、ＲＳＡ計算全体の間又はＥＣＣ計算の全体の間一定に保たれるが、新たな計算が開始されると変化させられるランダム的な変数によって、全ての中間結果が隠蔽される。これにより、全ての入力が同一である場合であっても、全ての電流追跡が変化させられる。なぜなら、ランダム的な変数は同一でないからである。

本発明の好適な実施例においては、モンゴメリ還元（Montgomery reduction）の原理が利用される。モンゴメリ還元は、Peter L. Montgomeryによって1985年に発表された、モジュール型計算における乗算のための効率的なアルゴリズムである。より具体的には、モンゴメリ還元は、c=ab・mod(n)を計算するための方法であり、ここでa、b及びnはkビットのバイナリ数である。

モンゴメリ還元は、ここでは特に暗号化に適用される。mを正の整数とし、R及びTをR>m、gcd(m,R)=1且つ0≦T<mRとなる整数とする。ここでgcdは最大公約数（greatest common divisor）である。古典的な方法を使わずにTR^-1mod(m)を算出することは、Rに対するTモジュロmのモンゴメリ還元と呼ばれる。Rの適切な選択により、モンゴメリ還元が効率的に計算されることができる。

有利にも、本発明はモンゴメリ還元に限定されるものではなく、本発明は他の還元原理にも適合されることができる。

本発明は、GF(p)及びGF(2ⁿ)の両方について適用可能である。本文脈において、アーキテクチャが素（p）拡大体及び二項（2ⁿ）拡大体の両方におけるオペランドで動作することが可能である場合、該アーキテクチャが統一されていると呼ぶ。

pが素数である場合、整数モジュロpは、GF(p)により示されるp個の元を持つ体を形成する。有限体は、有限の体の次数即ち有限個の元を持つ体であり、ガロア体（Galois Field）又はGFとも呼ばれる。有限体の次数は常に素数であるか又は素数のべき乗である。各素数のべき乗について、正確に１つの（「正確に１つ」は「同型を除いて（up to an isomorphism）正確に１つ」を意味するという通常の注意による）有限体GF()が存在する。GF(p)はp次の素体と呼ばれ、剰余類（residue class）モジュロpの体である。

n>1である場合、GF()は、係数がGF(p)に属する多項式の同値類（equivalence class）の体として表現され得る。いずれのn次の既約多項式もが、同型を除いて同一の体を導出する。

本発明は更に、計算、特に暗号演算を実行する少なくとも１つの集積回路を有する、データ処理装置、特に例えばチップカード又はスマートカードのような埋め込みシステムに関する。ここで前記集積回路は、
−少なくとも１つの攻撃に対して、特に少なくとも１つのＥＭ放射攻撃に対して、又は
−少なくとも１つの暗号解析に対して、特に少なくとも１つのＤＰＡに対して、
少なくとも１つのランダム的な変数によって、前記計算の全ての中間結果を隠蔽することにより、保護される。

本発明は最後に、ＤＰＡに対して保護されるべき上述したような少なくとも１つのデータ処理装置における、上述したような少なくとも１つの装置の使用、及び／又は上述したような方法の使用に関する。

既に上述したように、本発明の教示を有利な態様で実施化及び改善する幾つかの選択肢がある。この目的のため、請求項１に従属する及び請求項７に従属する請求項に参照が為される。本発明の更なる改善、特徴及び利点は、例として示される好適な実施例及び添付図面を参照しながら、以下により詳細に説明される。

データ処理装置の実施例、即ち暗号演算を実行する集積回路（ＩＣ）を有するチップカード又はスマートカードの形をとる埋め込みシステムは、ＰＫＩシステムを参照し、本発明の方法に従って動作する。即ち、保護装置１００（図１を参照）により不正使用及び／又は操作から保護される。

基本的に、変数X及びYが、X=X/v'mod(N)及びY=Y/v'mod(N)により隠蔽されることが想定される。本文脈においては、下線は変数が隠蔽されることを示す。

次いで、積X・Yが以下のように算出される：R=X・Y・v'mod(N)。Rは、X及びYと同様に隠蔽され、それ故Rは次の演算において使用されることができる。モンゴメリ還元により引き起こされる、後続するBによる除算を補償するため、v'により乗算する代わりに、v=v'B（B=2ⁿ、即ちBは2のべき乗）により乗算される。

しかしながら、隠蔽補正を可能な限り単純なものとするため、vは単一の語であることが望ましい。それ故、v'を選択する代わりに、vがランダム的な単一の語として選択され、ここでv'=v/Bmod(N)である。付加的な還元の可能性を低減させるため、vの幾つかの最上位ビット（ＭＳＢ）がゼロと選択され、積R・vを同数のビットだけ小さくする。

本発明は、オペランドの逆数を計算する能力を必要とする。

本集積回路の暗号計算は、ＲＳＡアルゴリズムに基づくものであっても良い（米国特許US4405829、又はRon Rivest、Adi Shamir及びLen Adlemanによる先行技術の論文「A Method for Obtaining Digital Signatures and Public-Key Cryptosystems」（Communications of the ACM、21(2)、120-126頁、1978年2月を参照）。該アルゴリズムは暗号化C=M^emod(N)を計算するためのものであり、ここで、
Mは暗号化されるべきメッセージであり、
N=p・qであり、
eは(p-1)(q-1)と互いに素であり、
dはx^edmod[(p-1)(q-1)]=1であるような数である。

復号化はM=C^dmod(N)を計算する。

M^e（又はC^d）を計算するための方法の１つは、以下のとおりである：
第１のステップ：R=1から始める。
第２のステップ：左から右へと指数eを走査する。
第３のステップ：R=R²mod(N)を常に計算する。
第４のステップ：eの走査されたビットが１である場合、R=R・M・mod(N)が更に計算される。

かくして、本計算は幾つかの二乗及び乗算を有する。

係数N及び全てのオペランドが、nビットから成る幾つかの語mを有すると仮定する。モジュール還元の後、変数はnビットから成るm個の語を有するが、最上位語（ＭＳＷ）は更に数ビットを持ち得る。モジュール還元の前に、結果は更なる語（通常は１又はｍ）を持つ。

最初の段階即ち初期隠蔽は、M=Mv'^-1=MBv^-1mod(N)を算出する。vは単一の語であるが、B・v^-1によるモジュール乗算はMの全ての語を完全に変化させる。初期隠蔽のみが、逆数演算を必要とする。

乗算X・Yを隠蔽する第２段階において、隠蔽されていない場合におけるように

が最初に計算される。次いで、

が計算される。本文脈において、

は、隠蔽されているが規定の方法で隠蔽されたものではないことは留意されるべきである。このことは、vの１つの語による完全な

の乗算、及び後続するモンゴメリ還元を必要とする。

本文脈において、最初にX=Xvを計算することは可能であるが効率的ではないことは、留意されるべきである。なぜなら、このことはオペランドの１つを非隠蔽化するからである。X及びYがn個の語を有する場合、X・Yの乗算及び還元は2n²+n個の乗算を必要とする。隠蔽補正演算は、2n+1個の乗算を更に必要とする。例えば64ビットから成るn=16個の語を用いる1024ビットのＲＳＡについては、このことは演算能力の約６パーセントを付加的に必要とする。

二乗X²を隠蔽する第３の段階において、隠蔽されていない場合におけるように

が最初に計算される。次いで、

が計算される。本文脈において、

の乗算、及び後続するモンゴメリ還元を必要とする。

モジュール二乗は、3/2(n²+n)個の乗算により実行されることができる。隠蔽補正演算は、2n+1個の乗算を更に必要とする。例えば64ビットから成るn=16個の語を用いる1024ビットのＲＳＡについては、このことは演算能力の約８パーセントを付加的に必要とする。

最後の段階即ち最終的な非隠蔽化において、全てのＲＳＡ計算が実行されたときに、最終結果Rが非隠蔽化される必要がある。該最終的な非隠蔽化は、モンゴメリ還元を用い、R=Rv・mod(N)を算出することにより為される。

ＥＣＣについては（M. Ernst、M. Jung、F. Madlenerらによる先行技術の論文「A Reconfigurable System on Chip Implementation for Elliptic Curve Cryptography over GF(2n)」、381-399頁を参照）、楕円曲線及び該曲線上の点Pが選択される。

第１のインスタンスＡにおいて、ランダム的な数aが選択される。公開鍵としてaPが計算され第２のインスタンスＢに送信される。第２のインスタンスＢにおいても、ランダム的な数bが選択される。公開鍵としてbPが計算され第１のインスタンスＡに送信される。次いで第１のインスタンスＡはK=a(bP)を計算し、第２のインスタンスＢはK'=b(aP)を計算する。ここでK=K'であり、このことは２つのインスタンスＡ及びＢの共通の秘密である。

基本的な演算は、スカラaによる点Pの乗算である。該乗算は、（a回）繰り返される点の加算：X=aP=P+P+...+Pである：
−R=Pで開始；
−スカラaを左から右へと走査：
−−R=2Rmod(N)を常に計算（所謂点倍算（point doubling））
−−aの走査されたビットが1である場合、R=R+Pmod(N)が更に算出される（所謂点加算（point addition））。

所謂点倍算のためのアルゴリズム及び所謂点加算のためのアルゴリズムは、XY±Zmod(N)及びX²±Zmod(N)のような演算を利用する（ＲＳＡアルゴリズムと同様であるが、第３のオペランドZが加算又は減算される）。

これらの演算は、ＲＳＡアルゴリズムについての方法と同一の方法で隠蔽される。

点倍算アルゴリズム及び点加算アルゴリズムはまた、X^-1を計算する逆数演算を必要とし、ここでXX^-1mod(N)=1である。

隠蔽補正（即ち結果の乗算）は、乗算又は二乗にのみ適用され、加算又は乗算には適用されない。それ故、最初にXYmod(N)又はX²mod(N)が計算される。

第１の段階即ち初期隠蔽において、点PのX座標及びY座標の両方が、最初に隠蔽される必要がある。初期隠蔽は、ＲＳＡアルゴリズムについて上述した方法と同一の方法で為される。

第２の段階、即ち乗算（R=XY±Z）及び二乗(R=X²±Z)において、最初に、積

又は二乗

が計算される。次いで、

が計算される。これに関連して、m=3及びn=64である192ビットのＥＣＣについて、隠蔽されていない乗算は21個の乗算を必要とし、隠蔽された乗算は27個の乗算、即ち28パーセント多い乗算を必要とすることは留意されるべきである。これらは共に付加的な還元を伴わない。隠蔽されていない二乗は18個の乗算を必要とし、隠蔽された二乗は24個の乗算、即ち33パーセント多い乗算を必要とする。

最後のステップ即ち反転において、隠蔽されていない反転がR=X^-1mod(N)を計算する。隠蔽された反転はR=(Xv²)^-1mod(N)を計算する。このことは以下のように理解される：R=R/v=X^-1/v=(Xv)^-1v^-1=(Xv²)^-1。

隠蔽されていない中間結果を与えるため、最初にXをvにより乗算し次いでまたvにより乗算することに比べ、最初にv²を計算し次いでv²をXにより乗算することが好ましい。

本発明の実装は、少なくとも部分的にソフトウェアベースであっても良い。これに関連して、ＲＳＡプログラミング及び／又はＥＣＣプログラミングに適したプロセッサが、上述した隠蔽を実装しても良い。

本発明による保護装置１００のハードウェア実装の例が、図１に示される。本実装の例は、以下を実行する能力を有する：
−それ自体知られた乗算器１０の実装を用いたXY+R+Cのタイプの乗算、及び
−それ自体知られた反転アルゴリズムの実装を用いたX^-1mod(N)タイプの逆数の計算。

乗算器１０及び反転器３０がそれぞれメモリ２０に接続され（図１における参照記号１２及び３２）、メモリ２０において全てのオペランドが保存される。前記結果もまた該メモリ２０に保存される。

更に状態機械４０が存在し、該状態機械４０は、
−必要とされるタイプの計算を実行するため乗算器１０を制御し、
−反転演算のため反転器３０を制御し、
−メモリ２０から入力オペランドを読み込み、
−結果をメモリ２０に書き込む。

本発明の方法よって動作する本発明による装置の実施例を模式的に示す。

符号の説明

１００装置
１０装置１００の乗算ユニット
１２乗算ユニット１０とメモリユニット２０との間の接続
２０装置１００のメモリユニット
３０装置１００の反転ユニット
３２反転ユニット３０とメモリユニット２０との間の接続
４０装置１００の状態機械

Claims

少なくとも１つのデータ処理装置、特に例えば少なくとも１つのチップカード又はスマートカードのような少なくとも１つの埋め込みシステムを、少なくとも１つの攻撃、特に例えば少なくとも１つの電流追跡解析のような少なくとも１つのサイドチャネル攻撃から保護するための装置であって、前記データ処理装置、特に前記データ処理装置の少なくとも１つの集積回路が、計算、特に暗号演算を実行する装置において、少なくとも１つのランダム的な変数により、前記計算の全ての中間結果を隠蔽することを特徴とする装置。
前記ランダム的な変数は、
前記計算の全体の間一定に保たれ、
新たな計算が開始されたときに変化させられる
ことを特徴とする、請求項１に記載の装置。
前記計算は、ＲＳＡアルゴリズム及び／又は楕円曲線暗号アルゴリズムに基づくことを特徴とする、請求項１又は２に記載の装置。
モンゴメリ還元又は他のタイプの還元を利用することを特徴とする、請求項１乃至３のいずれか一項に記載の装置。
前記オペランド、特に全てのオペランドと、前記計算の結果、特に全ての結果を保存するための、少なくとも１つのメモリユニットと、
前記メモリユニットに接続された少なくとも１つの乗算ユニットと、
前記メモリユニットに接続された少なくとも１つの反転ユニットと、
少なくとも１つの状態機械と、
を有し、前記状態機械は、
必要とされるタイプの計算を実行するために前記乗算ユニットを制御し、
反転演算のために前記反転ユニットを制御し、
前記メモリユニットから入力オペランドを読み取り、及び／又は
前記計算の結果、特に全ての結果を、前記メモリユニットに書き込むことを特徴とする、請求項１乃至４のいずれか一項に記載の装置。
データ処理装置、特に例えばチップカード又はスマートカードのような埋め込みシステムのようなデータ処理装置であって、計算、特に暗号演算を実行する少なくとも１つの集積回路を有するデータ処理装置において、請求項１乃至５のいずれか一項に記載の装置を有することを特徴とするデータ処理装置。
少なくとも１つのデータ処理システム、特に例えば少なくとも１つのチップカード又はスマートカードのような少なくとも１つの埋め込みシステムを、少なくとも１つの攻撃、特に例えば少なくとも１つの電流追跡解析のような少なくとも１つのサイドチャネル攻撃から保護するための方法であって、前記データ処理装置、特に前記データ処理装置の少なくとも１つの集積回路が、計算、特に暗号演算を実行する方法において、少なくとも１つのランダム的な変数により、前記計算の全ての中間結果を隠蔽することを特徴とする方法。
前記ランダム的な変数は、
前記計算の全体の間一定に保たれ、
新たな計算が開始されたときに変化させられる
ことを特徴とする、請求項７に記載の方法。
前記計算は、ＲＳＡアルゴリズム及び／又は楕円曲線暗号アルゴリズムに基づくことを特徴とする、請求項７又は８に記載の方法。
モンゴメリ還元又は他のタイプの還元を利用することを特徴とする、請求項７乃至９のいずれか一項に記載の方法。
差分電力解析から保護されるべき少なくとも１つの請求項６に記載のデータ処理装置における、請求項１乃至５のいずれか一項に記載の装置、及び／又は請求項７乃至１０のいずれか一項に記載の方法の使用。