(57)【特許請求の範囲】
【請求項１】
秘密鍵（Ｋ）式暗号化アルゴリズムを用いる電子構成部品内での差分解析による攻撃に対する対抗措置方法であって、その実施には、第一サイクル（Ｔ１）に適用された最初の入力データ（Ｌ０，Ｒ０）から、暗号化メッセージ（Ｃ）の作成を可能にする最後のサイクル（Ｔ１６）の出力の最終データ（Ｌ１６，Ｒ１６）を算出するための連続する複数の計算サイクル（Ｔ１，……Ｔ１６）が含まれ、各計算サイクルは、入力データ（Ｅ）から出力データ（Ｓ）を算出するための計算手段（ＴＣ）を使用し、前記計算手段は予測不可能なデータ（Ｓxor ｕ）を出力するために入力データ（Ｅ）及び出力データ（Ｓ）に第一の乱数（ｕ）を適用する方法であって、
該対抗措置方法が、
排他的論理和演算に従って、前記第一の入力データ（Ｌ０，Ｒ０）に第二の乱数（ｖ）を適用する手段、および、排他的論理和演算に従って、最後のサイクル（Ｔ１６）により算出された最終データに第二の乱数（ｖ）を適用する手段の使用、ならびに、
同じ暗号化メッセージ（Ｃ）を得るように、第一の乱数（ｕ）および第二の乱数（ｖ）に基づいて得られる計算手段の使用
を含むことを特徴とする方法。
【請求項２】
計算サイクルの計算手段が複数の計算手段（ＴＣＭ，ＴＣＭ’）からなることを特徴とする、請求項１に記載の対抗措置方法。
【請求項３】
各サイクルの出力で前記第一の乱数（ｕ）を消すために、各計算サイクルの終わりに補足演算（ＣＰ（ｐ（ｕ）））を含み、計算サイクルの計算手段が１つの計算手段（ＴＣＭ）からなることを特徴とする、請求項１に記載の対抗措置方法。
【請求項４】
前記計算手段（ＴＣM）は、入力データ（Ｅ）について対応する出力データ（Ｓ）を定義する第一の計算手段（ＴＣ0）から計算され、第一の計算手段の前記入力データ（Ｅxor ｅ（ｖ））に第二の乱数（ｖ）を適用し、前記出力データ（ｓxor ｕ）に第一の乱数（ｕ）を適用することを特徴とする、請求項３に記載の方法。
【請求項５】
計算手段（ＴＣ0，ＴＣM）が定数表であることを特徴とする、請求項４に記載の対抗措置方法。
【請求項６】
差分解析による攻撃に対する対抗措置方法を用いるセキュリティ電子構成部品であって、秘密鍵（Ｋ）式暗号化アルゴリズムを含み、その実施には、第一サイクル（Ｔ１）に適用された最初の入力データ（Ｌ０，Ｒ０）から、暗号化メッセージ（Ｃ）の作成を可能にする最後のサイクル（Ｔ１６）の出力の最終データ（Ｌ１６，Ｒ１６）を算出するための連続する複数の計算サイクル（Ｔ１，……Ｔ１６）が含まれ、各計算サイクルは、入力データ（Ｅ）から出力データ（Ｓ）を算出するための計算手段（ＴＣ）を使用し、前記計算手段は予測不可能なデータ（Ｓxor ｕ）を出力するために入力データ（Ｅ）及び出力データ（Ｓ）に第一の乱数（ｕ）を適用する構成部品であり、
第一の計算手段（ＴＣ0）が前記構成部品のプログラムメモリ（１）内に固定され、
前記セキュリティ電子構成部品が、
第二の乱数（ｖ）を生成し、排他的論理和演算に従って前記最初の入力データ（Ｌ０，Ｒ０）に該第二の乱数（ｖ）を適用し、排他的論理和演算に従って、最後のサイクル（Ｔ１６）により算出された最終データに該第二の乱数（ｖ）を適用する手段と、
各サイクル毎に用いられる計算手段（TCM）であって、同じ暗号化メッセージ（Ｃ）を得るように、アルゴリズムを新たに実行する都度第一の乱数（ｕ）および第二の乱数（ｖ）に基づいて計算されて、作業メモリ（３）内に記憶される計算手段（TCM）
を含むことを特徴とする構成部品。
【請求項７】
請求項６に記載のセキュリティ電子構成部品を備えたチップ
カード。
【発明の詳細な説明】
【０００１】
本発明は秘密鍵式暗号化アルゴリズムを用いる電子構成部品内の対抗措置方法に関するものである。それらはサービスまたはデータへのアクセスが厳しく管理されるアプリケーションで用いられる。それらはマイクロプロセッサとメモリを中心に形成されたアーキテクチャを有し、その中のプログラムメモリに秘密鍵が保存されている。
【０００２】
これらの構成部品は、チップカードの特定アプリケーションのために、特にチップカードの中で使用される。これらは、例えば、特定のデータバンクへのアクセス・アプリケーション、銀行アプリケーション、例えばテレビ、ガソリン販売、あるいはまた高速道路料金所通過のための、遠隔支払いアプリケーションである。
【０００３】
従って、これらの構成部品またはカードは、秘密鍵式暗号化アルゴリズムを用いるものであり、その中で最もよく知られているのがＤＥＳアルゴリズムである（英文ではData Encryption Standard）。他にも秘密鍵式アルゴリズムは存在し、ＲＣ５アルゴリズムまた更にＣＯＭＰ１２８アルゴリズムなどがある。もちろんこれで全てが含まれるわけではない。
【０００４】
一般的にまた簡潔に、これらのアルゴリズムは、ホストシステム（サーバー、銀行の現金支払機、・・・）によって（カードへの）入力に適用されたメッセージとカード内に含まれる秘密鍵とから暗号化されるメッセージを計算し、この暗号化メッセージをホストシステムに返す機能を有し、それによって、例えば、ホストシステムは構成部品またはカードを認証し、データを交換することなどが可能になる。
【０００５】
ところが、これらの構成部品またはこれらのカードは、消費電力を差分解析することからなる攻撃に弱く、悪意のある第三者が秘密鍵を見つけることができることがわかった。これらの攻撃は、英語の Differential Power Analysis の頭字語で、ＤＰＡ攻撃と呼ばれている。
【０００６】
これらのＤＰＡ攻撃の原理は、命令を実行するマイクロプロセッサの消費電力が、処理されるデータに従って変わるという事実に基づくものである。
【０００７】
特に、１ビットのデータを処理するマイクロプロセッサの命令は、このビットが「１」の値であるか「０」の値であるかによって、異なる２つの電力波形を発生させる。通常、命令によって「０」が処理されるなら、この実行の瞬間に消費電力の第一の振幅が得られ、命令によって「１」が処理されるなら、第一のものとは異なる消費電力の第二の振幅が得られる。
【０００８】
秘密鍵式暗号化アルゴリズムの特徴は既に知られたものである：実施される計算と、用いられるパラメータ。唯一分かっていないのは、プログラムメモリ内に保存されている秘密鍵である。この秘密鍵は、入力に適用されたメッセージと、返された暗号化メッセージが分かっているだけでは演繹できない。
【０００９】
しかしながら、暗号化アルゴリズムでは、幾つかの計算されるデータは、カードの入力に適用される平文メッセージと、カード内に保存されている秘密鍵だけに依存する。アルゴリズム内で計算されるその他のデータも、暗号化されたメッセージ（一般的にホストシステムへのカードの出力では、平文で与えられる）と、カード内に保存されている秘密鍵だけから再計算できる。もっと正確に言えば、これらの特定データの各ビットは、入力または出力メッセージと、鍵の限定された数の特定ビットとから決定できる。
【００１０】
例えば、特定データの各ビットは、鍵のビットの特定のグループによって形成された部分鍵が対応する。
【００１１】
予測できるこれらの特定データのビットを、以下に標的ビットと呼ぶ。
【００１２】
したがって、ＤＰＡ攻撃の基本的考え方は、命令が「１」を処理するか、「０」を処理するかによる、命令の消費電力波形の差分を利用し、アルゴリズムの命令によって、入力または出力の既知のメッセージと、対応する部分鍵についての推定とから標的ビットを計算する可能性を用いることにある。
【００１３】
したがって、ＤＰＡ攻撃の原理は、所与の部分鍵の推定を試験することにあり、攻撃者が知っている入力メッセージにそれぞれ関する多数の電力測定曲線に対して、ブール選択関数、つまり部分鍵の推定関数であり、標的ビットについての予測値によって曲線ごとに定義された関数を、適用することによる。
【００１４】
当該部分鍵を推定することによって、実際、所与の入力または出力メッセージについてこの標的ビットが取る値が「０」なのか「１」なのかを予測することができる。
【００１５】
このとき、これらの曲線を２つのパケットに選別するために、当該部分鍵を推定するために、標的ビットごとに予測値「０」または「１」を、選択ブール関数として適用することが可能である：部分鍵の推定に沿って、第一のパケットには標的ビットを「０」で処理した曲線が再グループ化され、第二のパケットには「１」で標的ビットを処理した曲線が再グループ化される。それぞれのパケット内の消費電力を平均して、第一のパケットについての平均消費曲線Ｍ０（ｔ）と、第二のパケットについての平均消費曲線Ｍ１（ｔ）が得られる。
【００１６】
部分鍵の推定が正しいとき、第一のパケットには、「０」で標的ビットを処理したＮ個の曲線の中の全ての曲線が現実に再グループ化され、第二のパケットには「１」で標的ビットを処理したＮ個の曲線の中の全ての曲線が現実に再グループ化される。このとき第一のパケットの平均消費曲線Ｍ０（ｔ）は、「０」で標的ビットを処理する特徴的な消費電力波形（波形0）で、クリティカル命令の実行の時点を除いたあらゆるところで平均的消費を示すことになる。言い換えれば、これら全ての曲線について、処理された全てのビットは、常に値が「０」であった標的ビットを除けば、「０」の値を取るのと、「１」の値を取るのと同じ確率を持っていた。このことは次式で表される：
Ｍ０（ｔ）＝［（波形0＋波形1）／２］t≠tci＋［波形0］tci      すなわち
Ｍ０（ｔ）＝［Ｖｍt］t≠tci＋［波形0］tci
ここでｔｃｉはクリティカル命令が実行された、クリティカル時点を表す。
【００１７】
同様に、第二のパケットの平均消費曲線Ｍ１（ｔ）は、「１」で標的ビットを処理する特徴的な消費電力波形（波形1）で、クリティカル命令の実行の時点を除いたあらゆるところでの平均的消費に対応する。これは次のように表される：
Ｍ１（ｔ）＝［（波形0＋波形1）／２］t≠tci＋［波形1］tci      すなわち
Ｍ１（ｔ）＝［Ｖｍt］t≠tci＋［波形1］tci
【００１８】
波形0と波形1の２つの波形が等しくないことが分かった。このとき曲線Ｍ０（ｔ）とＭ１（ｔ）の差分は、このビットを処理するクリティカル命令実行のクリティカル時点ｔｃｉにおいて、すなわち図１に示した例では場所ｔｃ０からｔｃ６において、波形0−波形1に振幅が等しくなるような、かつクリティカル時点以外では振幅がほぼゼロに等しくなるような信号ＤＰＡ（ｔ）が与えられる。
【００１９】
部分鍵の推定が間違っているとき、選別は現実に対応しない。統計的には、このときそれぞれのパケットの中には、「０」で標的ビットを実際に処理した曲線と、「１」で標的ビットを処理した曲線とが同数存在する。このとき結果としての平均曲線Ｍ０（ｔ）は、（波形0−波形1）／２＝Ｖｍで与えられる平均値の前後に位置するが、というのも各曲線について、標的ビットを含む処理される全てのビットは、「０」の値を取るのと「１」の値を取るのとが同じ確率だからである。
【００２０】
第二のパケットについても同じように推論すると、平均消費電力曲線Ｍ１（ｔ）の振幅が、（波形0−波形1）／２＝Ｖｍで得られる平均値の前後に位置する曲線が得られる。
【００２１】
差分Ｍ０（ｔ）−Ｍ１（ｔ）により算出される信号ＤＰＡ（ｔ）はこの場合ほぼゼロに等しい。部分鍵の推定が誤っている場合の信号ＤＰＡ（ｔ）は図２に示されている。
【００２２】
このように、ＤＰＡ攻撃は、処理されるビットの値に従って命令を実行する間の消費電力波形の差分を利用して、所与の部分鍵推定についてのブール選択関数に従って消費電力曲線の選別を実施する。得られた２つの曲線パケットの間の平均消費電力の差分解析を実施することによって、情報信号ＤＰＡ（ｔ）が得られる。
【００２３】
このときＤＰＡ攻撃は総体的に次のように展開される。
ａ−Ｎ個のランダムメッセージを抽出する（例えば、Ｎは１０００に等しい）
ｂ−毎回、（構成部品の電源端子で測定した）消費電力曲線を読み取って、Ｎ個のランダムメッセージのそれぞれについてカードによりアルゴリズムを実行させる
ｃ−部分鍵を推定する
ｄ−メッセージ（入力または出力）のビットと推定で取られた部分鍵とにしか依存しない値を有する標的ビットの一つが取る値を、ランダムメッセージのそれぞれについて予測してブール選択関数を得る
ｅ−このブール選択関数に従って（すなわち部分鍵推定の下でそれぞれの曲線についてのこの標的ビットに対する予測値「０」または「１」に従って）曲線を選別する
ｆ−それぞれのパケット内で結果としての平均消費電力曲線を計算する
ｇ−これらの平均曲線の差分を実行し、信号ＤＰＡ（ｔ）を得る
【００２４】
部分鍵の推定が正しいとき、ブール選択関数も正しく、第一のパケットの曲線は、入力または出力に与えられるメッセージがカード内で標的ビットを「０」とする曲線に現実に対応し、第二のパケットの曲線は、入力または出力に与えられるメッセージがカード内で標的ビットを「１」とする曲線に現実に対応する。
【００２５】
図１の場合：したがって、信号ＤＰＡ（ｔ）は、クリティカル命令（標的ビットを処理する命令）の実行に対応する時点ｔｃ０からｔｃ６においてゼロではない。
【００２６】
ここでわかるように、攻撃者はクリティカル時点を正確に知る必要はない。取得期間にクリティカル時点が少なくとも一回あれば十分である。
【００２７】
部分鍵の推定が正しくないとき、選別は現実に対応せず、それぞれのパケットの中には、「０」の標的ビットに現実に対応する曲線と、「１」の標的ビットに対応する曲線が、同数存在する。信号ＤＰＡ（ｔ）はどこでもほぼゼロである（図２に示した場合）。過程ｃ−に戻って部分鍵を新たに推定しなければならない。
【００２８】
推定が正しければ、最大限鍵を再現するまで、他の部分鍵の評価に移行することができる。例えば、ＤＥＳアルゴリズムでは、６４ビットの鍵を使用するが、そのうち有効なのは５６ビットにすぎない。ＤＰＡ攻撃では、有効な５６ビット中の少なくとも４８ビットが再現できる。
【００２９】
以下に、技術背景に関する２つの文献を引用する。それらは、ＮＡＫＡＯ  Ｙ  ＥＴ  ＡＬの《 THE SECURITY OF AN RDES CRYPTOSYSTEM AGAINST LINERA CRYPTANALYSIS（線形暗号解析に対するＲＤＥＳ暗号システムのセキュリティ）》IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS, COMMUNICATIONS AND COMPUTER SCIENCES, JP, INSTITUTE OF ELECTRONICS INFORMATION AND COMM. ENG. TOKYO, Ｅ７９−Ａ巻１号１２−１９頁XP000558714 ISSN :0916-8508を以下Ｄ１とし、公開公報ＷＯ  ００  ２７０６８をＤ２とする文献に関するものである。
【００３０】
文献Ｄ１は、セキュリティのためのＤＥＳを用いた暗号化システムに関する。
【００３１】
文献Ｄ２は、秘密鍵式アルゴリズムを用いた電子構成部品に関し、このアルゴリズムの使用には入力データ（Ｅ）から第１手段を用いて出力データを算出することが含まれる。
【００３２】
本発明は、部分鍵の推定が正しい場合でも、ゼロの信号ＤＰＡ（ｔ）を引き出す差分解析による攻撃に対する対抗措置方法を、電子構成部品内で用いることを目的とする。
【００３３】
そうすれば、部分鍵の推定が正しい場合と、部分鍵の推定が誤っている場合とが全く区別できない。この対抗措置によって電子構成部品をＤＰＡ攻撃から守ることができる。
【００３４】
ＧＥＭＰＬＵＳ社が２０００年５月５日に出願したフランス特許公開ＦＲ２  ７８５  ４７７に、その全体の内容が本願に組み込まれており、それによっても分かるように、所与の標的ビットに対して信号ＤＰＡ（ｔ）をゼロにするだけでは不十分である。
【００３５】
実際、クリティカル命令によって処理される同じデータについて複数の標的ビットが取る値を考えると、２つのパケットではなく、複数のパケットの曲線を選別しなければならなくなる。もはやバイナリの選択関数は一つではない。次にこれらのパケットをなんらかの仕方で再グループ化することによって、ただ一つの標的ビットついてバイナリの選択関数に従って選別した場合にはゼロになってしまうのに、部分鍵の推定が正しい場合にはゼロでない信号ＤＰＡ（ｔ）を得ることが可能であることを示すことができる。
【００３６】
例えば、同一のデータの２つの標的ビットを取る。これら２つの標的ビットは次の２2個の値を取ることができる：「００」，「０１」，「１０」，「１１」。
【００３７】
選択関数を、Ｎ＝１０００である測定消費電力曲線に適用して、４つのパケット曲線が得られる。選別が正しいとき、第一のパケットの約２５０曲線が値「００」に対応し、第二のパケットの約２５０曲線が値「０１」に対応し、第三のパケットの約２５０曲線が値「１０」に対応し、第四のパケットの約２５０曲線が値「１１」に対応する。
【００３８】
第一と第四のパケットを第一グループに再グループ化し、第二と第三のパケットを第二グループに再グループ化すると、等価ではない二つのグループが得られる。
【００３９】
第一グループでは、２つのビットが「００」の値を取るのと「１１」の値を取るのは同じ確率である。このグループの全ての消費曲線のクリティカル時点における平均値は次のように書ける：
Ｍ１（ｔci）＝［消費（「００」）＋消費（「１１」）］／２
【００４０】
第二グループでは、２つのビットが「０１」の値を取るのと「１０」の値を取るのは同じ確率である。このグループの全ての消費曲線のクリティカル時点における平均値は次のように書ける：
Ｍ２（ｔci）＝［消費（「０１」）＋消費（「１０」）］／２
【００４１】
これら２つの平均の差を取ると、ゼロでない信号ＤＰＡ（ｔ）が得られる。言い換えれば、平均消費を比較した２つのグループの中身は等しくない。
【００４２】
上記のフランス特許出願では、ＤＰＡ攻撃に対して意味を有するいかなる有効信号の取得をも阻止することが試みられた。取られた標的ビットの数に係わらず、また、平均消費の比較のために実施されたパケットの組み合わせに係わらず、信号ＤＰＡ（ｔ）は必ずゼロになる。このためには、対象標的ビットの数に係わらず、等価のパケットを得なければならない。
【００４３】
上記のフランス特許出願はこれらの様々な技術的課題に対する解決法として、アルゴリズムで用いられる計算手段の少なくとも出力データに排他的論理和演算において乱数を用いることを提案している。
【００４４】
かかる乱数を用いることによって、アルゴリズムの出力結果は正しいままであるが、クリティカル命令によって処理されるデータは予測できなくなる。
【００４５】
しかしながら、本発明では、アルゴリズム実行の所定の場所、特にアルゴリズムの入出力において、攻撃が成功し得ることに気づいた。
【００４６】
本発明は、これらの攻撃も不可能になる対抗措置方法を目的とする。本発明によれば、第二の乱数を用いて、これを排他的論理和演算において、暗号化アルゴリズムの入力パラメータに適用する。この第二の乱数は、アルゴリズム全体に伝播され、第一の乱数では保護されていなかったデータも第二の乱数によって保護される。
【００４７】
したがって、本発明によれば、アルゴリズム内での場所によって、データは、第一の乱数によって、又は第二の乱数によって、あるいはこれら二つの乱数の組み合わせによって保護される。
【００４８】
したがって、特徴として、本発明は秘密鍵式暗号化アルゴリズムを用いる電子部品内の対抗措置方法に関し、
その実施には、最初のサイクルに適用される最初の入力データから、暗号化メッセージの作成を可能にする最後のサイクルの出力の最終データを算出するための連続する複数の計算サイクルが含まれ、各計算サイクルごとに、入力データから出力データを算出するための計算手段が使用され、前記計算手段は、予測不可能なデータを出力するための第一の乱数（ｕ）を適用することを含む方法であって、排他的論理和演算に従って、前記第一の入力データに第二の乱数を適用する手段の使用が含まれることを特徴とする。
即ち、次の通りである。
第１に、秘密鍵（Ｋ）式暗号化アルゴリズムを用いる電子構成部品内での差分解析による攻撃に対する対抗措置方法であって、その実施には、第一サイクル（Ｔ１）に適用された最初の入力データ（Ｌ０，Ｒ０）から、暗号化メッセージ（Ｃ）の作成を可能にする最後のサイクル（Ｔ１６）の出力の最終データ（Ｌ１６，Ｒ１６）を算出するための連続する複数の計算サイクル（Ｔ１，……Ｔ１６）が含まれ、各計算サイクルは、入力データ（Ｅ）から出力データ（Ｓ）を算出するための計算手段（ＴＣ）を使用し、前記計算手段は予測不可能なデータ（Ｓxor ｕ）を出力するために入力データ（Ｅ）及び出力データ（Ｓ）に第一の乱数（ｕ）を適用する方法であって、
該対抗措置方法が、
排他的論理和演算に従って、前記第一の入力データ（Ｌ０，Ｒ０）に第二の乱数（ｖ）を適用する手段、および、排他的論理和演算に従って、最後のサイクル（Ｔ１６）により算出された最終データに第二の乱数（ｖ）を適用する手段の使用、ならびに、
同じ暗号化メッセージ（Ｃ）を得るように、第一の乱数（ｕ）および第二の乱数（ｖ）に基づいて得られる計算手段の使用
を含むことを特徴とする方法である。
第２に、計算サイクルの計算手段が複数の計算手段（ＴＣＭ，ＴＣＭ’）からなることを特徴とする、前記第１に記載の対抗措置方法である。
第３に、各サイクルの出力で前記第一の乱数（ｕ）を消すために、各計算サイクルの終わりに補足演算（ＣＰ（ｐ（ｕ）））を含み、計算サイクルの計算手段が１つの計算手段（ＴＣＭ）からなることを特徴とする、前記第１に記載の対抗措置方法である。
第４に、前記計算手段（ＴＣM）は、入力データ（Ｅ）について対応する出力データ（Ｓ）を定義する第一の計算手段（ＴＣ0）から計算され、第一の計算手段の前記入力データ（Ｅxor ｅ（ｖ））に第二の乱数（ｖ）を適用し、前記出力データ（ｓxor ｕ）に第一の乱数（ｕ）を適用することを特徴とする、前記第３に記載の方法である。
第５に、計算手段（ＴＣ0，ＴＣM）が定数表であることを特徴とする、前記第４に記載の対抗措置方法である。
第６に、差分解析による攻撃に対する対抗措置方法を用いるセキュリティ電子構成部品であって、秘密鍵（Ｋ）式暗号化アルゴリズムを含み、その実施には、第一サイクル（Ｔ１）に適用された最初の入力データ（Ｌ０，Ｒ０）から、暗号化メッセージ（Ｃ）の作成を可能にする最後のサイクル（Ｔ１６）の出力の最終データ（Ｌ１６，Ｒ１６）を算出するための連続する複数の計算サイクル（Ｔ１，……Ｔ１６）が含まれ、各計算サイクルは、入力データ（Ｅ）から出力データ（Ｓ）を算出するための計算手段（ＴＣ）を使用し、前記計算手段は予測不可能なデータ（Ｓxor ｕ）を出力するために入力データ（Ｅ）及び出力データ（Ｓ）に第一の乱数（ｕ）を適用する構成部品であり、
第一の計算手段（ＴＣ0）が前記構成部品のプログラムメモリ（１）内に固定され、
前記セキュリティ電子構成部品が、
第二の乱数（ｖ）を生成し、排他的論理和演算に従って前記最初の入力データ（Ｌ０，Ｒ０）に該第二の乱数（ｖ）を適用し、排他的論理和演算に従って、最後のサイクル（Ｔ１６）により算出された最終データに該第二の乱数（ｖ）を適用する手段と、
各サイクル毎に用いられる計算手段（TCM）であって、同じ暗号化メッセージ（Ｃ）を得るように、アルゴリズムを新たに実行する都度第一の乱数（ｕ）および第二の乱数（ｖ）に基づいて計算されて、作業メモリ（３）内に記憶される計算手段（TCM）
を含むことを特徴とする構成部品である。
第７に、前記第６に記載のセキュリティ電子構成部品を備えたチップカードである。
【００４９】
本発明のその他の特徴及び利点は付属の図面を参照して、例としてあげられた非制限的な下記の説明を読むことによっていっそう明らかになるだろう。
既に述べた図１及び２は、ＤＰＡ攻撃によって、秘密鍵Ｋの部分鍵の推定に応じて得ることができる信号ＤＰＡ（ｔ）を表している。
図３及び４は、従来技術による、ＤＥＳアルゴリズムの最初と最後のサイクルの詳細なフローチャートである。
図５は、図３及び４に示したようなＤＥＳアルゴリズム内で用いられた演算ＳＢＯＸのブロック図である。
図６は、図５に示した演算ＳＢＯＸで用いられる入出力の基本定数表の一例を示している。
図７及び８は、従来技術による対抗措置方法の適用例に対応する、ＤＥＳ実行フローチャートと、最初の数サイクルの詳細なフローチャートをそれぞれ示している。
図９は、本発明によるＤＥＳの実行フローチャートを示している。
図１０は、電子構成部品を含むチップカードの簡略ブロック図を表しており、該電子構成部品は、本発明による対抗措置方法を利用している。
【００５０】
本発明がよく理解できるように、対抗措置方法を採っていない、標準的なＤＥＳ秘密鍵式暗号化アルゴリズムを最初に説明する。このＤＥＳアルゴリズムは、図３及び４に示したごとく、Ｔ１からＴ１６で表した１６回の計算サイクルを含んでいる。
【００５１】
ＤＥＳは、入力メッセージＭに対する初期置換ＩＰから開始する（図３）。入力メッセージＭは６４ビットのワードｆである。置換後に得られた６４ビットのワードｅを２つに分割して、第一サイクル（Ｔ１）の入力パラメータＬ０とＲ０を形成する。Ｌ０は３２ビットのワードｄであり、ワードｅの重みのある方の３２ビットを含む。Ｒ０は３２ビットのワードｈであり、ワードｅの重みのない方の３２ビットを含む。
【００５２】
６４ビットのワードｑである秘密鍵Ｋも置換と圧縮を受けて、５６ビットのワードｒを算出する。
【００５３】
第一サイクルは、拡張と置換とから成る、パラメータＲ０に対する演算ＥＸＰ ＰＥＲＭを含み、４８ビットのワードｌを出力する。
【００５４】
このワードｌは、４８ビットのワードｂを算出するために、ＸＯＲで表される排他的論理和型の演算において、パラメータＫ１に組み合わされる。４８ビットのワードｍであるパラメータＫ１は、ある位置のシフト（図３及び４でＳＨＩＦＴで表される演算）によってワードｒから得られ、それに置換と拡張（ＣＯＭＰ ＰＥＲＭで表される演算）が適用される。
【００５５】
ワードｂはＳＢＯＸで表される演算に適用され、その出力では３２ビットのワードａが得られる。この特定の演算は、図５及び６との関連において後で詳述する。
【００５６】
ワードａは置換Ｐ ＰＥＲＭを受け、３２ビットのワードｃを出力する。
【００５７】
このワードｃは、ＸＯＲで表される、排他的論理和型の論理演算において、第一サイクルＴ１の入力パラメータＬ０に組み合わされ、３２ビットのワードｇを出力する。
【００５８】
第一サイクルのワードｈ（＝Ｒ０）は、次のサイクル（Ｔ２）の入力パラメータＬ１を算出し、第一サイクルのワードｇは、次のサイクルの入力パラメータＲ１を算出する。第一サイクルのワードｐは、次のサイクルの入力ｒを算出する。
【００５９】
他のサイクルＴ２からＴ１６も同様に展開するが、ただしシフト演算ＳＨＩＦＴは当該複数のサイクルに従って、一つまたは二つの位置で行われる。
【００６０】
このように、それぞれのサイクルＴｉは、入力にパラメータＬｉ−１、Ｒｉ−１、及びｒを受け取り、出力に次のサイクルＴｉ＋１のためのパラメータＬｉ、Ｒｉ、及びｒを算出する。
【００６１】
ＤＥＳアルゴリズムの最後に（図４）、暗号化されるメッセージは、最後の一サイクルＴ１６によって算出されたパラメータＬ１６とＲ１６から計算される。
【００６２】
この暗号化メッセージＣの計算は、実際には次の演算を含んでいる。
−  ワードＬ１６とＲ１６の位置を逆転させ、次にそれらを連結することによって、６４ビットのワードｅ’を形成する。
−  暗号化メッセージＣを形成する６４ビットのワードｆ’を得るために、ＤＥＳ開始の置換とは逆の置換ＩＰ-1を適用する。
【００６３】
演算ＳＢＯＸは図５及び６に詳述されている。演算には入力データｂに応じて出力データａを算出するための定数表ＴＣ0が含まれる。
【００６４】
実際には、この定数表ＴＣ0は、８つの基本定数表ＴＣ0１からＴＣ0８の形式を取り、それぞれが、ワードｂの６ビットだけを入力に受け、ワードａの４ビットだけを出力で算出する。
【００６５】
したがって、図６に示された基本定数表ＴＣ0１は、ワードｂのビットｂ１からｂ６を入力データとして受け取り、ワードａのビットａ１からａ４を出力として算出する。
【００６６】
実際にはこれら８つの基本定数表ＴＣ0１からＴＣ0８は、電子構成部品のプログラムメモリに記憶されている。
【００６７】
第一サイクルＴ１の演算ＳＢＯＸでは、定数表ＴＣ0の出力のデータａの特定の１ビットは、入力に適用されたデータｂの６ビットだけに、すなわち秘密鍵Ｋと入力データ（Ｍ）の６ビットだけに依存する。
【００６８】
最後のサイクルＴ１６の演算ＳＢＯＸでは、定数表ＴＣ0の出力のデータａの特定の１ビットは、秘密鍵Ｋと暗号化メッセージ（Ｃ）の６ビットだけから再計算できる。
【００６９】
しかるに、ＤＰＡ攻撃の原理に戻ると、出力ａのデータの一つまたは複数のビットを標的ビットに選んだときは、所与の入力メッセージ（Ｍ）または出力メッセージ（Ｃ）に対する一つまたは複数の標的ビットの値を予測するために、鍵Ｋの６ビットについてだけ推定すればよい。言い替えれば、ＤＥＳについては、６ビットの部分鍵についてだけ推定を立てればよい。
【００７０】
したがって、所与の基本定数表から得られた所与の全標的ビットについてのかかるアルゴリズムに対するＤＰＡ攻撃では、６４個の可能なものの中から部分鍵の正しい推定を判別しなければならない。
【００７１】
したがって、対応する標的ビットに対してＤＰＡ攻撃を行うことによって、８つの基本定数表ＴＣ0１からＴＣ0８の出力ビットから、秘密鍵の８×６＝４８ビットまで発見することができる。
【００７２】
したがって、ＤＥＳでは、アルゴリズムの最初と終わりにＤＰＡ攻撃に対するクリティカル命令が見いだされる。これらの命令はフランス特許出願ＦＲ９８  １３６０５に詳述されており、参照すれば有益となるであろう。
【００７３】
そしてクリティカル命令によって処理される全てのデータは、ＤＥＳの始めと終わりの演算ＳＢＯＸの出力データまたは出力データの派生データであることが分かる。
【００７４】
このＤＥＳアルゴリズムに適用された上述のフランス特許出願に記載の対抗措置方法は、クリティカル命令によって処理されるそれぞれのデータを予測不能にすることにある。したがって、使用される一つまたは複数の標的ビットを問わず、信号ＤＰＡ（ｔ）は常にゼロになる。この対抗措置方法は、ＤＥＳの始めのクリティカル命令と、ＤＥＳの終わりのクリティカル命令とに適用される。
【００７５】
演算ＳＢＯＸを、入力データＥ＝ｂから出力データＳ＝ａを算出するための最初の計算手段とすることによって、ＤＥＳアルゴリズムを適用し上述のフランス特許出願に記載の対抗措置方法は、出力データを予測不能にするために第一の計算手段の代わりに他の計算手段を用いることから成り、クリティカル命令によって処理されるこの出力データおよび／または派生データが全て予測不能になる。
【００７６】
これらの他の手段には異なる手段が含むことができる。それらは、第一の手段の入力データおよび出力データの一方および／または他方と乱数ｕ（あるいは派生乱数）との間で排他的論理和を取ることにより第一の手段から計算される。
【００７７】
この乱数ｕは、アルゴリズムの出力結果、すなわち暗号化メッセージＣが正しくなるように使用される。
【００７８】
図７及び８は、この対抗措置方法の応用例を示しており、上述のフランス特許出願の図１０に対応する。
【００７９】
ＤＥＳアルゴリズムの従来の実行では、先に見たごとく、各サイクルは、演算ＳＢＯＸで第一の手段ＴＣ0を使用する。
【００８０】
この例では、図７に示したごとく、最初の手段ＴＣ0の出力データと乱数ｕとの間で排他的論理和を取り、最初の手段ＴＣ0の入力データと派生値ｅ（ｐ（ｕ））との間で排他的論理和を取ることで他の手段を計算する。次に、これらの計算された他の手段を用いることから成るそれぞれのグループに、同一の実行シーケンスＳＥＱＡを適用する。
【００８１】
したがって、この方法では、３２ビットのデータである乱数ｕが用いられる。例えば、３２ビットの乱数を抽出することができるし、あるいは３２ビットの乱数を得るために４ビットの乱数を抽出して、それらを８回複写することができる。
【００８２】
ここで、ｅ（ｐ（ｕ））に等しい派生乱数を計算するが、ここで、ｐ（ｕ）は値ｕに適用した演算Ｐ ＰＥＲＭの結果に対応し、ｅ（ｐ（ｕ））は値ｐ（ｕ）に適用した演算ＥＸＰ ＰＥＲＭの結果である。
【００８３】
このとき、この対抗措置方法によって使用される他の手段が計算できる。
【００８４】
図７を参照して示した例では、これらの他の手段は第二の手段ＴＣ2と、ＣＰで示した補足的な排他的論理和演算を含んでいる。
【００８５】
第二の手段ＴＣ2は各サイクルごとに使用される。
【００８６】
それらは、入力データＥと派生乱数ｅ（ｐ（ｕ））との間で排他的論理和を取り、第一の手段ＴＣ0の出力データＳと乱数ｕとの間で排他的論理和を取ることで計算され、これは次のように書ける：
ＴＣ2＝（Ｅxor ｅ（ｐ（ｕ）），Ｓxor ｕ）
【００８７】
派生乱数ｅ（ｐ（ｕ））と補足的な排他的論理和演算ＣＰを行うことによって、第二の手段ＴＣ2の入力にデータｂxor ｅ（ｐ（ｕ））を得ることができる。この演算は図７及び８にＣＰ（ｅ（ｐ（ｕ）））で示されている。
【００８８】
変数ｅ（ｐ（ｕ））でのこの補足的な排他的論理和演算ＣＰは、演算ＥＸＰ ＰＥＲＭと演算ＸＯＲの間であれ、演算ＸＯＲと演算ＳＢＯＸの間であれ、最初と最後のサイクルの様々な場所に配置できる。この補足演算ＣＰ（ｐ（ｕ））を演算ＥＸＰ ＰＥＲＭの前に置くことで、補足的な排他的論理和演算ＣＰを派生乱数ｐ（ｕ）で代えることが可能である。したがって、入力でｌxor ｅ（ｐ（ｕ））、つぎにｂxor ｅ（ｐ（ｕ））が得られる。
【００８９】
図におけるこれら全ての場合、演算ＳＢＯＸの入力にデータｂxor ｅ（ｐ（ｕ））が得られる。
【００９０】
このとき計算プログラムは、アルゴリズム実行の始めに、例においては４ビットに対して、乱数ｕを抽出し、派生乱数ｅ（ｐ（ｕ））を計算し、次に実行シーケンスＳＥＱＡ内で使用された各種の手段を計算すること、すなわち第二の手段ＴＣ2を計算することから成る。
【００９１】
各グループの出力に、出力パラメータについての正しい結果が得られる。したがって、第一グループＧ１の出力パラメータＬ４とＲ４、第二グループＧ２のＬ８とＲ８、第三グループＧ３のＬ１２とＲ１２，第四グループＧ４のＬ１６とＲ１６は、抽出された乱数に係わらず正しくなる。
【００９２】
全てのサイクルが実行されたとき、正しいパラメータＬ１６とＲ１６が得られ、該パラメータによって正しい暗号化メッセージＣを計算することができる。
【００９３】
他方、グループの内部では、いくつかの中間結果は、使用したシーケンスによって同じ値を有さず、乱数ｕまたは派生乱数ｅ（ｐ（ｕ））での排他的論理和演算に対応する値を有するので、ＤＰＡ攻撃に対する保護が得られる。
【００９４】
図８は、シーケンスＳＥＱＡ内での、第一グループＧ１の４サイクルＴ１，Ｔ２，Ｔ３，Ｔ４の詳細なフローチャートを示しており、各サイクルで用いられる第二の手段ＴＣ2の役割が明らかになる。それらの定義：ＴＣ2＝Ｅxor ｅ（ｐ（ｕ）），Ｓxor ｕに従って、補足演算ＣＰにより、ランダムに変更されたデータｂxor ｅ（ｐ（ｕ））を入力に適用すると、ランダムに変更されたデータａxor ｕが出力に得られる。サイクルＴ１からサイクルＴ４の終わりまでこの推論を進め、ｐ（ｕ）xor ｐ（ｕ）＝０であることに着目すると、サイクルＴ４の出力に、変更されていないデータＬ４，Ｒ４が得られる。
【００９５】
かかる対抗措置方法では、ＤＥＳの最初に、乱数ｕの抽出と、実行シーケンスＳＥＱＡ内で使用された手段の計算を備えなければならない。ＤＥＳの実行ごとに計算されるこれらの手段については、実行時間が、作業メモリに記憶され、計算に用いられる最初の手段ＴＣ0が、プログラムメモリに記憶されている。
【００９６】
従来技術のこの対抗措置方法は、一般的に、乱数ｕをアルゴリズムの各サイクルにおいて用いられる計算手段の少なくとも出力に適用することから成るが、特定のデータは平文のままにしている。図７及び８において、入力データＬ０，Ｒ０、またそれに続く第一サイクルのデータｈ，ｌ，ｂは平文で用いられることが分かる。
【００９７】
同様に、データＲ３，Ｌ４，Ｒ４，Ｒ７，Ｌ８，Ｒ８，Ｒ１１，Ｌ１２，Ｒ１２，Ｒ１５，Ｌ１６およびＲ１６も、平文で用いられる。
【００９８】
一般的に、上述の従来技術の対抗措置方法の実施態様に係わらず、少なくとも入力データＬ０，Ｒ０と出力データＬ１６とＲ１６は、アルゴリズムにおいて平文で用いられる。前述の場合のように、その他の中間データもその可能性があり、例えば、従来技術の対抗措置方法の特定の実施態様に特に左右されるが、その図７と８は実施例の一つしか示していない。
【００９９】
実際には、明示的に用いられるこれらのデータに基づく攻撃が、さらにアルゴリズムに対して行われる可能性がある。
【０１００】
したがって、本発明は、アルゴリズムで用いられる全てのデータを、第一の乱数ｕによって、または第二の乱数ｖによって、あるいはこれら二つの組み合わせによって予測不能にすることを可能にする上述の対抗措置方法の完成を提案するものである。
【０１０１】
この方法の一つの実施例が図９に示されている。
【０１０２】
本発明によれば、ｖで示した第二の乱数が使用され、排他的論理和演算によって入力データＬ０とＲ０に適用される。
【０１０３】
従って、アルゴリズムの計算において実際に用いられる入力データは、Ｌ０xor ｖとＲ０xor ｖに等しい予測不能なデータである。
【０１０４】
この第二の乱数は、アルゴリズムの各サイクルの中を伝播する。したがって、第１６サイクルＴ１６の出力では、出力データとして、Ｌ１６xor ｖとＲ１６xor ｖに等しい予測不能なデータが得られる。
【０１０５】
暗号化メッセージＣを得ることを可能にする真の出力データＬ１６とＲ１６を発見するためには、これらのデータＬ１６xor ｖとＲ１６xor ｖのそれぞれに、第二の乱数ｖで排他的論理和演算を適用する。
【０１０６】
２つの乱数ｕとｖを組み合わせて用いることによって、対抗措置方法を実施するＤＥＳアルゴリズムを攻撃不能にする、完成された対抗措置方法を得ることができる。
【０１０７】
図９において、本発明による対抗措置方法の実際の使用例を詳細に示した。
【０１０８】
第一サイクルＴ１では、データＬ０xor ｖとＲ０xor ｖが入力され、それらに演算ＥＸＰ ＰＥＲＭと、ＸＯＲ（鍵Ｋ１で）を、連続して適用する。したがって、演算ＳＢＯＸの入力はデータｂxor ｖになる。
【０１０９】
この演算ＳＢＯＸに組み合わされる計算手段ＴＣMは、従来技術の対抗措置方法の場合と同様に、ＤＥＳアルゴリズムの元の定数表ＴＣ0から演繹された定数表から成る。
【０１１０】
図６との関連において見たように、この元の定数表をＴＣ0＝（Ｅ，Ｓ）で表し、次のようにして新しい計算手段ＴＣMを計算する：
ＴＣM＝（Ｅxor ｅ（ｖ），Ｓxor ｕ）
【０１１１】
この様にして、各サイクルの入力データに適用される第二の乱数ｖを計算に入れると、演算ＳＢＯＸの出力では、従来技術による第一の乱数ｕがやはり得られる。
【０１１２】
したがって、計算手段ＴＣMを用いる演算ＳＢＯＸの出力に、データａxor ｐ（ｕ）が得られ、それに演算Ｐ ＰＥＲＭを適用して、データｃxor ｐ（ｕ）が得られる。
【０１１３】
入力データＬ０xor ｖでの次の演算ＸＯＲにより、出力に、データｇxor ｐ（ｕ）xor ｖが算出される。
【０１１４】
先に述べたように（図８）、従来技術では、この段階で、第二サイクルＴ２の入力に使用されるデータｇxor ｐ（ｕ）が得られた。
【０１１５】
本発明による方法では、第二サイクル別の入力は、図９に示したごとく、データＬ１xor ｖ＝Ｒ０xor ｖである。
【０１１６】
したがって、第二の乱数ｖは、アルゴリズムの全サイクルに伝播する。
【０１１７】
第一サイクルの出力データ（Ｒ１xor （ｖ）xor ｐ（ｕ））の乱数ｕを消さない場合、ＴＣM’＝Ｅxor ｅ（ｖ）xor ｅ（ｐ（ｕ）），Ｓxor ｕによって定義される第二サイクルＴ２における別の計算手段ＴＣM’を使用しなければならない。
【０１１８】
本発明のこの実施はあまり有利ではないが、それは乱数ｕが、出力のみならず入力でも、表ＴＣM’内で適用されるので、新しい２つの定数表ＴＣMとＴＣM’の計算を必要とするからである。
【０１１９】
この様に、本発明によれば、また図９に示したごとく、本発明の実施に必要な計算を減らして２つの変数ｕとｖの使用を容易にするために、また、各サイクルで同じ演算を再現するために、各サイクルの終わりにＣＰ（ｐ（ｕ））で表される補足的な排他的論理和演算を備え、それぞれの新しいサイクルの入力で値ｐ（ｕ）を消すようにする。したがって、第二サイクルＴ１の入力にはデータＲ１xor ｖ＝（ｇxor ｐ（ｕ）xor ｖ）xor ｐ（ｕ）、すなわち
Ｒ１xor ｖ＝ｇxor ｖ  が得られる。
【０１２０】
このとき、同じ一連の計算演算を実行することによって、それぞれのサイクルが連続し、第１６サイクルの出力に、出力データとしてＬ１６xor ｖとＲ１６xor ｖが得られる。これら２つのデータのそれぞれと第二の乱数ｖとの間で排他的論理和演算を取ることで、暗号化メッセージＣの作成を可能にするデータＬ１６とＲ１６が得られる。
【０１２１】
各サイクルに備えられた計算手段内での第一の乱数ｕの使用と、入力に適用される第二の乱数の使用を組み合わせてから第一サイクルを実行する本発明による対抗措置方法を適用することによって、アルゴリズム内で用いられる全てのデータが予測不能になる。アルゴリズム内のどこに位置するかにより、本発明の対抗措置による保護は、第一の乱数ｕによって、または第二の乱数ｖによって、あるいはこれら二つの値の組み合わせによって保証される。
【０１２２】
実際には、また図９に示した応用例では、いわゆるＤＥＳアルゴリズムを実行する前に次の演算を実行しなければならない：
−乱数ｕとｖの抽出
−演算ＣＰ（ｐ（ｕ））のためのｐ（ｕ）の計算
−ｅ（ｖ）の計算
−ＴＣM＝Ｅxor ｅ（ｖ），Ｓxor ｕの計算
乱数ｖは、データＬ０およびＲ０と同じビット数を有するデータであり、この例では３２ビットである。したがって、この方法では、３２ビットデータである乱数ｖが用いられる。例えば、３２ビットの乱数を抽出するか、あるいは３２ビットの乱数を得るために４ビットの乱数を抽出して、それらを８回複写することができる（乱数ｕの場合と同様）。
【０１２３】
他の応用例を考えることも可能であり、特にそれぞれのサイクルを同一としないこともできる。開示された一般的に原理によって２つの乱数を使用するこれら全ての変型は、本発明を逸脱しない。
【０１２４】
ＤＥＳ秘密鍵式暗号化アルゴリズムにおける本発明による対抗措置方法を用いる電子構成部品１は、典型的には、図１０に示したごとく、マイクロプロセッサｍＰと、プログラムメモリ２と、作業メモリ３を含む。異なる計算手段ＴＣ0とＴＣMは、実際には、それぞれプログラムメモリ１と作業メモリ３内にそれぞれ記憶された定数表である。これらの計算手段の使用を管理できるように、乱数発生手段４が備えられ、図７及び１１のフローチャートを参照すると、当該乱数発生手段は、ＤＥＳを実行する毎に乱数ｕとｖを算出する。かかる構成部品はチップカード５の不可侵性を向上させるためにチップカードに特に使用することができる。
【図面の簡単な説明】
【図１】  図１は、ＤＰＡ攻撃によって、秘密鍵Ｋの部分鍵の推定に応じて得ることができる信号ＤＰＡ（ｔ）を表している。
【図２】  図２は、ＤＰＡ攻撃によって、秘密鍵Ｋの部分鍵の推定に応じて得ることができる信号ＤＰＡ（ｔ）を表している。
【図３】  図３は、従来技術による、ＤＥＳアルゴリズムの最初のサイクルの詳細なフローチャートである。
【図４】  図４は、従来技術による、ＤＥＳアルゴリズムの最後のサイクルの詳細なフローチャートである。
【図５】  図５は、図３及び４に示したようなＤＥＳアルゴリズム内で用いられた演算ＳＢＯＸのブロック図である。
【図６】  図６は、図５に示した演算ＳＢＯＸで用いられる入出力の基本定数表の一例を示している。
【図７】  図７は、従来技術による対抗措置方法の適用例に対応する、ＤＥＳ実行フローチャートを示している。
【図８】  図８は、従来技術による対抗措置方法の適用例に対応する、最初の数サイクルの詳細なフローチャートを示している。
【図９】  図９は、本発明によるＤＥＳの実行フローチャートを示している。
【図１０】  図１０は、電子構成部品を含むチップカードの簡略ブロック図を表しており、該電子構成部品は、本発明による対抗措置方法を利用している。
【図１】
0003733027.tif 000002
【図２】
0003733027.tif 000003
【図３】
0003733027.tif 000004
【図４】
0003733027.tif 000005
【図５】
0003733027.tif 000006
【図６】
0003733027.tif 000007
【図１０】
0003733027.tif 000008
【図７】
0003733027.tif 000009
【図８】
0003733027.tif 000010
【図９】
0003733027.tif 000011