(57)【要約】  本発明は、プリミティブを使用して第1の出力データ(s1)を生成する段階(102)と、保護パラメータを生成する段階(104)とを含む、秘密鍵の非対称暗号方式アルゴリズムを使用する電子コンポーネントにおける対策のための方法に関する。この方法は、第1のオペランドおよび第2のオペランドをそれぞれ与えるために、前記保護パラメータを使用して、秘密鍵、および第1の出力データ(s1)から得られる中間パラメータを含むセットの要素のうちの少なくとも1つを変換する段階(106)と、第1のオペランドおよび第2のオペランドが関係している演算から第2の出力データ(s2)を生成する段階(108、114)とをさらに含む。
2011510579.tif 000002
【特許請求の範囲】
【請求項１】
非対称秘密鍵暗号化アルゴリズムを実施する電子コンポーネントにおける対策方法であって、
- プリミティブを使用して第1の出力データ(s1)を生成する段階(102 ; 202)と、
- 保護パラメータ(a)を生成する段階(104 ; 204)と
を含み、
- 前記保護パラメータ(a)を使用して、前記秘密鍵(d)、および前記第1の出力データ(s1)から得られる中間パラメータからなるセットの要素のうちの少なくとも1つを変換して、第1のオペランドおよび第2のオペランドをそれぞれ与える段階(106 ; 206)と、
- 前記第1のオペランドおよび前記第2のオペランドを伴う演算から、第2の出力データ(s2)を生成する段階(108, 114 ; 208, 214)と
をさらに含む電子コンポーネントにおける対策方法。
【請求項２】
- 前記保護パラメータ(a)を使用して、前記秘密鍵(d)を変換する段階(106 ; 206)と、
- 前記中間パラメータおよび前記変換した秘密鍵を伴う第1の演算から、第1の中間データを生成し(108, ; 208)、前記中間パラメータおよび前記保護パラメータ(a)を伴う第2の演算から、第2の中間データを生成し(114 ; 214)、前記第1の中間データおよび前記第2の中間データを組み合わせて前記第2の出力データ(s1)を与える段階と
を含む、請求項1に記載の電子コンポーネントにおける対策方法。
【請求項３】
- 前記保護パラメータ(a)を使用して、前記第1の出力データ(s1)から得られる前記中間パラメータを変換する段階(106 ; 206)と、
- 前記変換した中間パラメータおよび前記秘密鍵(d)を伴う第1の演算から、第1の中間データを生成し(108, ; 208)、前記保護パラメータ(a)および前記秘密鍵(d)を伴う第2の演算から、第2の中間データを生成し、前記第1の中間データおよび前記第2の中間データを組み合わせて前記第2の出力データ(s2)を与える段階(114 ; 214)と
を含む、請求項1に記載の電子コンポーネントにおける対策方法。
【請求項４】
前記中間パラメータが、前記第1の出力データ(s1)である、請求項1から3のいずれかに記載の電子コンポーネントにおける対策方法。
【請求項５】
前記プリミティブが、DSAタイプの署名方式を用いて暗号化アルゴリズムを実施するための冪乗剰余である、請求項4に記載の電子コンポーネントにおける対策方法。
【請求項６】
前記プリミティブが、ECDSAタイプの署名方式を用いて暗号化アルゴリズムを実施するためのスカラ乗法である、請求項4に記載の電子コンポーネントにおける対策方法。
【請求項７】
フィアットシャミア法をゼロ知識証明プロトコルに適用することに本質があるタイプの署名方式を用いて非対称暗号化アルゴリズムを実施する、請求項1から6のいずれかに記載の電子コンポーネントにおける対策方法。
【請求項８】
前記保護パラメータ(a)を前記生成する段階(104 ; 204)が、
メモリ(16)に記憶された所定の少なくとも1つの秘密のパラメータ(S)に連続して適用することによって生成関数(20''a)を定める段階であって、前記秘密のパラメータ(S)および前記関数からのみ決定できる複数の値からなる列((An))の生成関数を定める段階と、
前記列の少なくとも1つの値から再現可能なやり方で前記保護パラメータ(a)を生成する段階と
を含む、請求項1から7のいずれかに記載の電子コンポーネントにおける対策方法。
【請求項９】
メモリ(16)に記憶された所定の少なくとも1つの対応する秘密のパラメータ(S)に連続して適用することによって複数の関数を定める段階であって、前記対応する秘密のパラメータ(S)および前記対応する関数からのみ決定できる複数の値からなる対応する列((A'n),(A''n))の各関数が生じる、複数の関数を定める段階と、
既定の関係を使用して、生成した複数の値からなる複数の前記列((A'n),(A''n) )を組み合わせて複数の値からなる新しい列((An))を生成する段階と、
前記新しい列((An))の少なくとも1つの値から再現可能なやり方で前記保護パラメータ(a)を生成する段階と
を含む、請求項8に記載の電子コンポーネントにおける対策方法。
【請求項１０】
メモリ(16)に記憶された所定の少なくとも1つの秘密のパラメータ(S)に連続して適用することによって生成関数を定める段階であって、前記秘密のパラメータ(S)および前記関数からのみ決定できる複数の値からなる列((A'n))の生成関数を定める段階と、
生成した複数の値からなる前記列((A'n))と前記暗号化アルゴリズムの公開パラメータを組み合わせることによって、複数の値からなる新しい列((An))を生成する段階と、
前記新しい列((An))の少なくとも1つの値から再現可能なやり方で前記保護パラメータ(a)を生成する段階と
を含む、請求項8に記載の電子コンポーネントにおける対策方法。
【請求項１１】
前記変換(106 ; 206)を行った後に、前記保護パラメータ(a)を再生成して、前記第2の出力データ(s2)を生成する前記段階(114 ; 214)の間に前記保護パラメータを使用する段階(110 ; 210)を含む、請求項8から10のいずれかに記載の電子コンポーネントにおける対策方法。
【請求項１２】
非対称秘密鍵暗号化アルゴリズムの対策方法を実施するためのマイクロプロセッサ(18)と、前記秘密鍵(d)を記憶するための少なくとも1つの安全なメモリ(16)と、保護パラメータ(a)を生成するためのデータ生成器(20, 20')とを備えるマイクロ回路デバイス(12', 12'')であって、
- プリミティブを使用して第1の出力データ(s1)を生成し(102 ; 202)、
- 前記保護パラメータ(a)を使用して、前記秘密鍵(d)、および前記第1の出力データ(s1)から得られる中間パラメータからなるセットの要素のうちの少なくとも1つを変換して、第1のオペランドおよび第2のオペランドをそれぞれ与え(106 ; 206)、
- 前記第1のオペランドおよび前記第2のオペランドを伴う演算から、第2の出力データ(s2)を生成する(108, 114 ; 208, 214)
ように構成されるマイクロ回路デバイス(12', 12'')。
【請求項１３】
- 前記保護パラメータ(a)を使用して、前記秘密鍵(d)を変換し(106 ; 206)、
- 前記中間パラメータおよび前記変換した秘密鍵を伴う第1の演算から、第1の中間データを生成し(108, ; 208)、前記中間パラメータおよび前記保護パラメータ(a)を伴う第2の演算から、第2の中間データを生成し(114 ; 214)、前記第1の中間データおよび前記第2の中間データを組み合わせて前記第2の出力データ(s2)を与える
ように構成される、請求項12に記載のマイクロ回路デバイス(12', 12'')。
【請求項１４】
- 前記保護パラメータ(a)を使用して、前記第1の出力データ(s1)から得られる前記中間パラメータを変換し(106 ; 206)、
- 前記変換した中間パラメータおよび前記秘密鍵(d)を伴う第1の演算から、第1の中間データを生成し(108, ; 208)、前記保護パラメータ(a)および前記秘密鍵(d)を伴う第2の演算から、第2の中間データを生成し(114 ; 214)、前記第1の中間データおよび前記第2の中間データを組み合わせて前記第2の出力データ(s2)を与える
ように構成される、請求項12に記載のマイクロ回路デバイス(12', 12'')。
【請求項１５】
前記中間パラメータが、前記第1の出力データ(s1)である、請求項12から14のいずれかに記載のマイクロ回路デバイス(12', 12'')。
【請求項１６】
前記プリミティブが、DSAタイプの署名方式を用いて暗号化アルゴリズムを行うための冪乗剰余である、請求項15に記載のマイクロ回路デバイス(12', 12'')。
【請求項１７】
前記プリミティブが、ECDSAタイプの署名方式を用いて暗号化アルゴリズムを行うためのスカラ乗法である、請求項15に記載のマイクロ回路デバイス(12', 12'')。
【請求項１８】
前記マイクロプロセッサ(18)が、フィアットシャミア法をゼロ知識証明プロトコルに適用することに本質があるタイプの署名方式を用いて非対称暗号化アルゴリズムを実施する、請求項12から17のいずれかに記載のマイクロ回路デバイス(12', 12'')。
【請求項１９】
前記データ生成器(20'')が、
メモリ(16)に記憶された所定の少なくとも1つの秘密のパラメータ(S)に連続して適用することによって生成関数(20''a)を定めるものであって、前記秘密のパラメータ(S)および前記関数からのみ決定できる複数の値からなる列((An))の生成関数(20''a)を定め、
前記列の少なくとも1つの値から再現可能なやり方で前記保護パラメータ(a)を生成することによって前記保護パラメータ(a)を生成する(104 ; 204)ように構成される、請求項12から18のいずれかに記載のマイクロ回路デバイス(12'')。
【請求項２０】
前記データ生成器(20'')が、
メモリ(16)に記憶された所定の少なくとも1つの対応する秘密のパラメータ(S)に連続して適用することによって複数の関数を定めるものであって、前記対応する秘密のパラメータ(S)および前記対応する関数からのみ決定できる複数の値からなる対応する列((A'n),(A''n))の各関数が生じる、複数の関数を定め、
既定の関係を使用して、生成した複数の値からなる複数の前記列((A'n),(A''n))を組み合わせて複数の値からなる新しい列((An))を生成し、
前記新しい列((An))の少なくとも1つの値から再現可能なやり方で前記保護パラメータ(a)を生成する
ように構成される、請求項19に記載のマイクロ回路デバイス(12'')。
【請求項２１】
前記データ生成器(20'')が、
メモリ(16)に記憶された所定の少なくとも1つの秘密のパラメータ(S)に連続して適用することによって生成関数を定めるものであって、前記秘密のパラメータ(S)および前記関数からのみ決定できる複数の値からなる列((A'n))の生成関数を定め、
生成した複数の値からなる前記列((A'n))と前記暗号化アルゴリズムの公開パラメータを組み合わせることによって、複数の値からなる新しい列((An))を生成し、
前記新しい列((An))の少なくとも1つの値から再現可能なやり方で前記保護パラメータ(a)を生成する
ように構成される、請求項19に記載のマイクロ回路デバイス(12'')。
【請求項２２】
前記変換(106 ; 206)を行った後に、前記保護パラメータ(a)を再生成して、前記第2の出力データ(s2)を生成する段階(114 ; 214)の間に前記保護パラメータを使用するように構成される(110 ; 210)、請求項19から21のいずれかに記載のマイクロ回路デバイス(12'')。
【請求項２３】
請求項12から22のいずれかに記載のマイクロ回路デバイス(12', 12'')を備えるポータブルデバイス、特にICカード(30)。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密鍵を発見することを目的とする攻撃に耐える、非対称秘密鍵暗号化アルゴリズムを実施する電子コンポーネントにおける対策方法に関するものである。本発明はそのような方法を実施するマイクロ回路デバイスおよびポータブルデバイス、詳細にはICカードにも関するものである。
【背景技術】
【０００２】
非対称秘密鍵暗号化は、プリミティブPの使用に基づき、このプリミティブPは通常、離散対数問題および楕円曲線離散対数問題などの一方向性の複雑な解明問題を利用する関数である。言い換えれば、入力データxを伴う非対称暗号化プリミティブPについては、y=F(x)を計算することは簡単であるが、yおよびプリミティブFを知っていても、xの値を見出すことは、《困難》である。本明細書では、用語「困難」は、「計算的に解決不可能」を意味する。有限フィールドにおいて、Fは、冪乗剰余であり、楕円曲線において、Fは、定められた楕円曲線の点のスカラ乗法である。
【０００３】
署名方式は、非対称暗号化の従来通りの使用を構成する。図1に示すように、秘密鍵dの使用を伴う、署名方式を用いた非対称暗号化のアルゴリズムアプリケーション10は一般に、秘密鍵を使用して、このメッセージの署名によってメッセージMの伝送を承認するためのマイクロ回路12によって実施される。秘密鍵dは、例えば、マイクロ回路12内に記憶されており、マイクロ回路12は、その目的のために設けられた安全なメモリ空間16を含むメモリ14と、非対称暗号化アルゴリズム10を実行するためのマイクロプロセッサ18とを備える。
【０００４】
暗号化アルゴリズムを実施するマイクロ回路デバイスは、使用される鍵のようにマイクロ回路デバイスが使用する秘密データ、およびことによると場合によっては実際のメッセージの情報を突き止めることを目的とする攻撃を時々受ける。特に、署名方式を用いる非対称暗号化アルゴリズムは、秘密鍵を発見することを目的とする攻撃を受ける。補助チャンネルによるこの攻撃は、暗号化アルゴリズムのソフトウェアまたはハードウェアの実装に関するいつくかの特性を利用する主要な一群の暗号化技法をもたらしている。
【０００５】
補助チャンネルを通じての知られた攻撃の中で、SPAタイプ(単純電力解析:Simple Power Analysis)の攻撃、またはDPAタイプ(差分電力解析:Differential Power Analysis)の攻撃は、非対称暗号化アルゴリズムの実行中にマイクロ回路の入出力電流および入出力電圧を測定し、それによりそこから秘密鍵を推定することに本質がある。この種の攻撃の実現可能性は、具体的にはAdvances in Cryptology - Crypto 99 Proceedings, Lecture Notes In Computer Science Vol. 1666, M. Wiener, ed., Springer-Verlag, 1999年に掲載されたP. Kocher、J. Jaffe、およびB. Junの表題「Differential Power Analysis」の論文で論証されている。
【０００６】
時間的攻撃(temporal attacks)は、いくつかの動作を実行するための時間を解析する。非対称暗号化アルゴリズムに対するそのような攻撃は、具体的にはAdvances in Cryptology - Crypto 96, 16th annual international cryptology conference, Aug. 18-22, 1996 Proceedingsに掲載されたP. Kocher、N. Koblitzの表題「Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems」の論文に説明されている。
【０００７】
フォールトインジェクション(fault injection)による攻撃も知られており、その中でDFA(差分故障解析:Differential Fault Analysis)により攻撃するものがあり、これは、暗号化アルゴリズムの実行中に、例えば暗号化アルゴリズムが実行されているマイクロ回路を乱すことによって自発的に故障を引き起こすことに本質がある。そのような乱れには、マイクロ回路を1回(または複数回)短時間照明すること、もしくは1つまたは複数の電圧ピークをマイクロ回路の接点のうちの1つに発生させることが含まれ得る。したがって、この乱れは、ある条件下で発生した計算エラーおよび挙動エラーを利用して求めている秘密鍵の一部またはさらには全部を得ることを可能にする。
【０００８】
性質が様々であるこれらの攻撃と戦うために、多数のとてもいろいろな解決策が、見出されてきた。より具体的には、本発明は、非対称秘密鍵dの暗号化アルゴリズムを実施する電子コンポーネントにおける対策方法であって、
- プリミティブを使用して第1の出力データを生成する段階と、
- 保護パラメータaを生成する段階と
を含む対策方法に関する解決策に関する。
【０００９】
一般に、これらのアルゴリズムは、生成した保護パラメータを使用してプリミティブの実行の修正を行う。
【００１０】
保護パラメータaは、従来から疑似ランダムデータ生成器20を使用して生成され、その結果、暗号化アルゴリズム10によるプリミティブの実行は、例えばマスキングと通常呼ばれる技法によって、ランダムにやはりさせられ、この技法は、保護パラメータaを使用してマイクロプロセッサ18の対策セクション22によって行われるときに使用される処理とは対照的にその処理が歪まされるので、データを変換し、またはデータを歪ませる方法と言い換えることもできる。このようにして、暗号化アルゴリズムの中間データ、および結果として、測定可能な電流は、ランダムな保護パラメータによって修正され、その観察により秘密鍵の真の値を見つけることを不可能にする。一方、マスキングは、実際のアルゴリズムを乱さず、したがって、それによりマスキングの有無にかかわらず同じ結果を与える。
【００１１】
例えば、(その著者Rivest、ShamirおよびAdlemanにちなんで)RSAという名で知られている非対称暗号化アルゴリズムの実行中に、冪乗剰余に本質があるプリミティブが、実行される。プリミティブの効果的な実施は、秘密鍵dの2進法表示を、この2進法表示の1ビットごとに反復を行うことによって使用する。各反復において、この計算がなされ、事実上、計算中のエネルギー消費は、関係しているビットの値に依存する。したがって、そのようなプリミティブの実行は、秘密鍵を前述の攻撃に対して特に脆弱にさせる。したがって、従来の対策は、保護パラメータを使用して秘密鍵を直接マスクすることに本質がある。
【００１２】
したがって、知られた署名方式は、秘密鍵dを指数として使用して冪乗剰余をメッセージMに適用することによってメッセージMを署名するためのこのRSAアルゴリズムを使用して保護され得る。この場合、署名は、冪乗剰余の直接の結果である。
【００１３】
一方、フィアットシャミア法(Fiat-Shamir heuristic)をゼロ知識証明プロトコル(zero-knowledge identification protocol)に適用することに本質がある別の知られた署名方式は、そのように保護され得ない。そのような署名方式は、知られており、例えばその定義は、Benoit Chevallier-Mamesにより、2006年11月16日、Ecole Normale Superieure、Parisにおいて、「Public key encryption: constructions and security proofs」と呼ばれる、より詳細には4.1.2  章および4.2.1章、27〜30頁の中で公に提示および定義された論文の中で言及され得る。同様に、Schnorrの認証プロトコル(Schnorr's identification protocol)ならびにエルガマル署名およびDSA署名(デジタル署名アルゴリズム(Digital Signature Algorithm))は、別のやり方で保護されるはずである。例えば、この他の署名方式を使用するDSAアルゴリズムは、
- 離散対数問題に基づくと共に、秘密鍵と異なるランダム変数を使用して適用されるプリミティブを使用して第1の出力データを生成する段階と、
- 第1の出力データおよび秘密鍵を伴う演算から、第2の出力データを生成する段階と、
- 第1の出力データおよび第2の出力データを署名として出力する段階と
を含む。
【００１４】
このアルゴリズムのための対策方法は、Proceedings of the 8th International Workshop on Theory and Practice in Public Key Cryptography 2005 (2005年1月23〜26日、Les Diablerets、Switzerland)、Lecture Notes in Computer Science、vol. 3386/2005、16〜28頁、Springer Edに掲載されたD. Naccacheらの論文、表題「Experimenting with faults, lattices and the DSA」に説明されている。
【００１５】
この文献には、フォールトインジェクションによる攻撃が、説明されている。この攻撃は、ランダム変数のある一定数の最下位ビットを0に切り替え、ある一定回数署名を計算することによって、秘密鍵の値を推定することを可能にする。
【００１６】
ランダム変数をマスクすることによってプリミティブの実行を保護することは、秘密鍵を見出すためにランダム変数の値を知ることが必要ではないので、このタイプのアルゴリズムにおけるフォールトインジェクションによる攻撃に対して効率的ではない。したがって、この論文は、例えば種々の技法を同時に組み合わせる、より複雑な方法を提供する。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】P. Kocher、J. Jaffe、およびB. Jun、「Differential Power Analysis」、Advances in Cryptology - Crypto 99 Proceedings, Lecture Notes In Computer Science Vol. 1666, M. Wiener, ed., Springer-Verlag, 1999年
【非特許文献２】P. Kocher、N. Koblitz、「Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems」、Advances in Cryptology - Crypto 96, 16th annual international cryptology conference, Aug. 18-22, 1996 Proceedings
【非特許文献３】Benoit Chevallier-Mames、2006年11月16日、Ecole Normale Superieure、Parisにおいて、「Public key encryption: constructions and security proofs」4.1.2  章および4.2.1章、27〜30頁
【非特許文献４】D. Naccacheら、「Experimenting with faults, lattices and the DSA」、Proceedings of the 8th International Workshop on Theory and Practice in Public Key Cryptography 2005 (2005年1月23〜26日、Les Diablerets、Switzerland)、Lecture Notes in Computer Science、vol. 3386/2005、16〜28頁、Springer Ed
【非特許文献５】Benoit Chevallier-Mames、2006年11月16日、Ecole Normale Superieure、Parisにおいて、「Public key encryption : constructions and security proofs」、より詳細には4.4章
【発明の概要】
【発明が解決しようとする課題】
【００１８】
したがって、具体的には、フィアットシャミア法をゼロ知識証明プロトコルに適用する署名方式を用いるアルゴリズムについて、前述のタイプの攻撃に耐える、実施するのが簡単である非対称暗号化の方法を提供することが望まれ得る。
【課題を解決するための手段】
【００１９】
本発明の一実施形態は、非対称秘密鍵暗号化アルゴリズムを実施する電子コンポーネントにおける対策方法であって、
- プリミティブを使用して第1の出力データを生成する段階と、
- 保護パラメータを生成する段階と
を含み、
- 保護パラメータを使用して、秘密鍵、および第1の出力データから得られる中間パラメータからなるセットの要素のうちの少なくとも1つを変換して、第1のオペランドおよび第2のオペランドをそれぞれ与える段階と、
- 第1のオペランドおよび第2のオペランドを伴う演算から、第2の出力データを生成する段階と
をさらに含む電子コンポーネントにおける対策方法に関する。
【００２０】
したがって、この保護パラメータを使用して、実際のプリミティブの実行ではなく、プリミティブの適用に続く演算の実行を保護する。実際には、この演算は、このタイプの署名方式を目標とする攻撃により多く利用される。
【００２１】
一実施形態によれば、この対策方法は、
- 保護パラメータを使用して、秘密鍵を変換する段階と、
- 中間パラメータおよび変換した秘密鍵を伴う第1の演算から、第1の中間データを生成し、中間パラメータおよび保護パラメータを伴う第2の演算から、第2の中間データを生成し、第1の中間データおよび第2の中間データを組み合わせて第2の出力データを与える段階と
を含む。
【００２２】
一実施形態によれば、この対策方法は、
- 保護パラメータを使用して、第1の出力データから得られる中間パラメータを変換する段階と、
- 変換した中間パラメータおよび秘密鍵を伴う第1の演算から、第1の中間データを生成し、保護パラメータおよび秘密鍵を伴う第2の演算から、第2の中間データを生成し、第1の中間データおよび第2の中間データを組み合わせて第2の出力データを与える段階と
を含む。
【００２３】
一実施形態によれば、この中間パラメータは、第1の出力データである。
【００２４】
一実施形態によれば、このプリミティブは、DSAタイプの署名方式を用いて暗号化アルゴリズムを行うための冪乗剰余である。
【００２５】
一実施形態によれば、このプリミティブは、ECDSAタイプの署名方式を用いて暗号化アルゴリズムを行うためのスカラ乗法である。
【００２６】
一実施形態によれば、この対策方法は、フィアットシャミア法をゼロ知識証明プロトコルに適用することに本質があるタイプの署名方式を用いて非対称暗号化アルゴリズムを実施する。
【００２７】
一実施形態によれば、保護パラメータの生成は、
- メモリに記憶された所定の少なくとも1つの秘密のパラメータに連続して適用することによって生成関数を定める段階であって、この秘密のパラメータおよびこの関数からのみ決定できる複数の値からなる列の生成関数を定める段階と、
- この列の少なくとも1つの値から再現可能なやり方で保護パラメータを生成する段階と
を含む。
【００２８】
一実施形態によれば、この対策方法は、
- メモリに記憶された所定の少なくとも1つの対応する秘密のパラメータに連続して適用することによって複数の関数を定める段階であって、対応する秘密のパラメータおよび対応する関数からのみ決定できる複数の値からなる対応する列の各関数が生じる、複数の関数を定める段階と、
- 既定の関係を使用して、生成した複数の値からなる複数の列を組み合わせて複数の値からなる新しい列を生成する段階と、
- この新しい列の少なくとも1つの値から再現可能なやり方で保護パラメータを生成する段階と
を含む。
【００２９】
一実施形態によれば、この対策方法は、
- メモリに記憶された所定の少なくとも1つの秘密のパラメータに連続して適用することによって生成関数を定める段階であって、秘密のパラメータおよび関数からのみ決定できる複数の値からなる列の生成関数を定める段階と、
- 生成した複数の値からなる列と暗号化アルゴリズムの公開パラメータを組み合わせることによって、複数の値からなる新しい列を生成する段階と、
- この新しい列の少なくとも1つの値から再現可能なやり方で保護パラメータを生成する段階と
を含む。
【００３０】
一実施形態によれば、この対策方法は、変換を行った後に、保護パラメータを再生成して、第2の出力データを生成する段階の間に保護パラメータを使用する段階を含む。
【００３１】
本発明の別の実施形態は、非対称秘密鍵暗号化アルゴリズムの対策方法を実施するためのマイクロプロセッサと、秘密鍵を記憶するための少なくとも1つの安全なメモリと、保護パラメータを生成するためのデータ生成器とを備えるマイクロ回路デバイスであって、
- プリミティブを使用して第1の出力データを生成し、
- 保護パラメータを使用して、秘密鍵、および第1の出力データから得られる中間パラメータからなるセットの要素のうちの少なくとも1つを変換して、第1のオペランドおよび第2のオペランドをそれぞれ与え、
- 第1のオペランドおよび第2のオペランドを伴う演算から、第2の出力データを生成する
ように構成されるマイクロ回路デバイスを提供することに本質がある。
【００３２】
一実施形態によれば、このマイクロ回路デバイスは、
- 保護パラメータを使用して、秘密鍵を変換し、
- 中間パラメータおよび変換した秘密鍵を伴う第1の演算から、第1の中間データを生成し、中間パラメータおよび保護パラメータを伴う第2の演算から、第2の中間データを生成し、第1の中間データおよび第2の中間データを組み合わせて第2の出力データを与える
ように構成される。
【００３３】
一実施形態によれば、このマイクロ回路デバイスは、
- 保護パラメータを使用して、第1の出力データから得られる中間パラメータを変換し、
- 変換した中間パラメータおよび秘密鍵を伴う第1の演算から、第1の中間データを生成し、保護パラメータおよび秘密鍵を伴う第2の演算から、第2の中間データを生成し、第1の中間データおよび第2の中間データを組み合わせて第2の出力データを与える
ように構成される。
【００３４】
一実施形態によれば、この中間パラメータは、第1の出力データである。
【００３５】
一実施形態によれば、このプリミティブは、DSAタイプの署名方式を用いて暗号化アルゴリズムを行うための冪乗剰余である。
【００３６】
一実施形態によれば、このプリミティブは、ECDSAタイプの署名方式を用いて暗号化アルゴリズムを行うためのスカラ乗法である。
【００３７】
一実施形態によれば、このマイクロプロセッサは、フィアットシャミア法をゼロ知識証明プロトコルに適用することに本質があるタイプの署名方式を用いて非対称暗号化アルゴリズムを実施する。
【００３８】
一実施形態によれば、このデータ生成器は、
- メモリに記憶された所定の少なくとも1つの秘密のパラメータに連続して適用することによって生成関数を定めるものであって、この秘密のパラメータおよびこの関数からのみ決定できる複数の値からなる列の生成関数を定め、
- この列の少なくとも1つの値から再現可能なやり方で保護パラメータを生成する
ことによって保護パラメータを生成するように構成される。
【００３９】
一実施形態によれば、このデータ生成器は、
- メモリに記憶された所定の少なくとも1つの対応する秘密のパラメータに連続して適用することによって複数の関数を定めるものであって、対応する秘密のパラメータおよび対応する関数からのみ決定できる複数の値からなる対応する列の各関数が生じる、複数の関数を定め、
- 既定の関係を使用して、生成した複数の値からなる複数の列を組み合わせて複数の値からなる新しい列を生成し、
- この新しい列の少なくとも1つの値から再現可能なやり方で保護パラメータを生成する
ように構成される。
【００４０】
一実施形態によれば、このデータ生成器は、
- メモリに記憶された所定の少なくとも1つの秘密のパラメータに連続して適用することによって生成関数を定めるものであって、秘密のパラメータおよび関数からのみ決定できる複数の値からなる列の生成関数を定め、
- 生成した複数の値からなる列と暗号化アルゴリズムの公開パラメータを組み合わせることによって、複数の値からなる新しい列を生成し、
- この新しい列の少なくとも1つの値から再現可能なやり方で保護パラメータを生成する
ように構成される。
【００４１】
一実施形態によれば、このマイクロ回路デバイスは、変換を行った後に、保護パラメータを再生成して、第2の出力データを生成する段階の間に保護パラメータを使用するように構成される。
【００４２】
本発明の別の実施形態は、前述のようなマイクロ回路デバイスを備えるポータブルデバイス、特にICカードを与えることに本質がある。
【００４３】
本発明の実施形態を、添付図面に関連して以下の詳細な説明の中でより詳細に説明するが、本発明の実施形態は、その添付図面に限定されるものではない。
【図面の簡単な説明】
【００４４】
【図１】前述の、従来タイプのマイクロ回路デバイスの構造の概略図である。
【図２】本発明の第1の実施形態によるマイクロ回路デバイスの構造の概略図である。
【図３】図2のデバイスを備えるICカードの概略図である。
【図４】図2のデバイスによって実施される第1の対策方法の連続するステップを示す図である。
【図５】図2のデバイスによって実施される第2の対策方法の連続するステップを示す図である。
【図６】本発明の第2の実施形態によるマイクロ回路デバイスの構造の概略図である。
【図７】図6のデバイスによって実施される対策方法の連続するステップを示す図である。
【発明を実施するための形態】
【００４５】
本発明の第1の実施形態。
図2に示すマイクロ回路デバイス12'は、図1に示したもののように、非対称暗号化のアルゴリズムアプリケーション10と、アプリケーション10によって使用されるためのものである具体的には秘密鍵dを記憶するための安全なメモリ空間16を含むメモリ14と、マイクロプロセッサ18と、保護パラメータaを与えるための疑似ランダムデータ生成器20とを備える。マイクロ回路デバイス12'は、対策セクション22'も含み、対策セクション22'により、既存の対策に、具体的には前述の対策セクション22に改善がもたらされる。
【００４６】
加えて、デバイス12'は、例えば、図3に示すように、具体的には安全なICカード30の形態でポータブルデバイスに組み入れられる。
【００４７】
アルゴリズムの暗号化アプリケーション10および対策セクション22'は、別個のように示されているが、アルゴリズムの暗号化アプリケーション10および対策セクション22'は、実際には、対策を含む非対称暗号化アルゴリズムの同じ実装のソフトウェアまたはハードウェアの中に十分に重なっていてもよいことに留意されたい。
【００４８】
マイクロ回路デバイス12'内で、非対称暗号化のアルゴリズムアプリケーション10は、フィアットシャミア法をゼロ知識証明プロトコルに適用することに本質があるタイプの署名方式の実施によりまさしく適している。したがって、非対称暗号化のアルゴリズムアプリケーション10は、
- プリミティブを適用して第1の出力データs1を生成するためのセクション10aと、
- 一方が、第1の出力データから得られ、場合によりセクション22'によって変換され、他方が、場合によってセクション22'によって変換される秘密鍵である、少なくとも2つのオペランドを伴う演算を実行して、第2の出力データs2を生成するためのセクション10bと
を備える。
【００４９】
この方式を使用する署名アプリケーションについては、第1の出力データおよび第2の出力データは、署名(s1、s2)を構成する。
【００５０】
デバイス12とは違って、デバイス12'では、対策セクション22'は、保護パラメータaを使用して、秘密鍵d、および/または第1の出力データから得られる中間パラメータを変換するように構成される。DSA署名の場合、中間パラメータは、実際の第1の出力データである。
【００５１】
本発明に従う種々の対策方法は、図2のデバイスによって実施することができる。網羅的でないそれらのいくつかを、図4および図5を参照して示すことにする。
【００５２】
メッセージMにDSAタイプの署名を作製するこのタイプの第1の方法を、図4によって示す。
【００５３】
一組の鍵(公開鍵および秘密鍵)を生成する第1のステップ100の間に、以下のもの、すなわち、
- Lビットの素数p、ただし、512≦L≦1024であり、Lは、64で割り切れる、
- p-1=qzであるように選ばれる160ビットの素数q、ただし、zは整数である、
- 数h、ただし、g=hZ mod p>1であるように選ばれる1<h<p-1、
- 0<d<qであるようなkビットの数d
がランダムに決定される。
【００５４】
これらの数を用いてe= gd mod pを計算する。
【００５５】
公開鍵は(p,q,g,e)である。秘密鍵はdである。
【００５６】
鍵の大きさがより大きくなることを可能にするDSA署名のバージョンは、NIST(米国標準技術局)の、Lが3072ビットの大きさであることについて言及する主題に関するいくつかの文献によって与えられることに留意されたい。
【００５７】
プリミティブを適用する第2のステップ102の間に、0<u<qであるように選ばれるランダム変数uが、生成される。次いで、セクション10aは、以下の冪乗剰余、すなわち、
s1=(gu mod p) mod q
を使用して第1の出力データs1を計算する。
【００５８】
ステップ104の間に、疑似ランダムデータ生成器20は、秘密鍵dの大きさに等しい2進法表示の大きさを有する保護パラメータaを生成する。代替として、生成器20は、dの大きさよりずっと小さい大きさを有するパラメータa'を生成するが、このパラメータa'の2進法表示は、必要に応じて何度でもそれ自体と連結されて、最終的に、dの大きさに等しい2進法表示の大きさを有する保護パラメータaを与える。また代替として、生成器20は、前もって決定されたqまたはs1のようなDSAアルゴリズムの他のパラメータに組み合わされるパラメータa'を生成し、関数COMBを使用して、保護パラメータa、すなわちa=COMB(a',q,s1, ...)を与える。生成器20によって生成したパラメータ(aまたはa')は、パラメータa'をDSAアルゴリズムの他のパラメータに組み合わせてaを形成するとき、パラメータa'についての検証パラメータとして具体的には任意のやり方でその後の使用のためにメモリに保持される。
【００５９】
以下のマスキングステップ106の間に、対策セクション22'は、秘密鍵dを、以下のように、すなわちd'=d+aに変換する。
【００６０】
第1の出力データs1および変換した秘密鍵d'を伴う演算を計算するステップ108の間に、以下の形の線形合同、すなわち、
A=u-1(H(M)+d'.s1) mod qが行われ、ただし、H(M)は、メッセージMに知られた関数SHA-1を用いた暗号ハッシュの結果である。
【００６１】
以下のステップは、ステップ104の間に、生成器20によって生成されたパラメータa'が、検証パラメータとしてメモリに保持された場合に行われる任意の検証ステップ110である。このステップ110の間に、パラメータaは、関数COMB、ならびに公開値および/またはこの関数によって使用されるメモリに保持した値(a',q,s1, ...)を使用して再び計算される。
【００６２】
aの値が、ステップ104とステップ110の間に変わった場合、それにより、2つのステップの間にフォールトインジェクションによる攻撃が発生したと結論付けることができる。次いで、暗号化アプリケーション10によって警報が送られると共に、暗号化アルゴリズムが停止し(112)、または種々のセキュリティの反応が、適用される。
【００６３】
aの値が、ステップ104とステップ110の間に変わらなかった場合、ステップ114が、行われ、このステップ114の間に以下の計算、すなわち、
B=(u-1.a.s1)mod q
が行われる。
【００６４】
関係s2=(A-B) mod qによって与えられる第2の出力データs2が、そこから最終的に推定される。
【００６５】
最終ステップ116の間に、暗号化アプリケーション10は、値(s1,s2)をメッセージMのDSA署名として出力する。
【００６６】
代替として、前述の第1の方法は、次の通り修正されてもよい。
【００６７】
マスキングステップ106の間に、対策セクション22'は、以下のように、すなわち、s1'=s1+aのように第1の出力データs1を変換する。
【００６８】
ステップ108の間に、線形合同の演算の計算は、第1の変換した出力データs1'および秘密鍵dを伴い、すなわち、
A=u-1(H(M)+d.s1') mod q
である。
【００６９】
ステップ114の間に、以下の計算、すなわち、
B=(u-1.d.a) mod q
が行われる。
【００７０】
第2の出力データs2は、関係s2=(A-B) mod qによって、そこから推定される。
【００７１】
やはり代替として、前述の第1の方法は、次の通り修正されてもよい。
【００７２】
ステップ108の間に、線形合同の演算の計算は、第1の出力データs1および変換した秘密鍵d'を伴い、すなわち、
A=(H(M)+d'.s1) mod q
である。
【００７３】
ステップ114の間に、以下の計算、すなわち、
B=(A-a.s1) mod q
が行われる。
【００７４】
第2の出力データs2は、関係s2=(u-1.B) mod qによって、そこから推定される。
【００７５】
代替としてまた、前述の第1の方法は、次の通り修正されてもよい。
【００７６】
マスキングステップ106の間に、対策セクション22'は、以下のように、すなわち、s1'=s1+aのように第1の出力データs1を変換する。
【００７７】
ステップ108の間に、線形合同の演算の計算は、第1の変換した出力データs1'および秘密鍵dを伴い、すなわち、
A=(H(M)+d.s1') mod q
である。
【００７８】
ステップ114の間に、以下の計算、すなわち、
B=(A-d.a) mod q
が行われる。
【００７９】
第2の出力データs2は、関係s2=(u-1.B) mod qによって、そこから推定される。
【００８０】
代替としてまた、前述の第1の方法は、次の通り修正されてもよい。
【００８１】
ステップ104の間に、疑似ランダムデータ生成器20は、dの大きさよりずっと小さい2進法表示の大きさを有する保護パラメータaを生成する。
【００８２】
マスキングステップ106の間に、対策セクション22'は、以下のように、すなわち、d'=d +a.qのように秘密鍵dを変換する。
【００８３】
ステップ108の間に、線形合同の演算の計算は、第1の変換した出力データs1および変換した秘密鍵d'を伴い、
A=(H(M)+d'.s1) mod q
である。
【００８４】
ステップ114の間に、第2の出力データの値を直接与える以下の計算、すなわち、
S2=(u-1.A) mod q
が行われる。
【００８５】
先の対策は、a=-aを選ぶことによって再生成することもできる。
【００８６】
メッセージMにECDSAタイプ(楕円曲線デジタル署名アルゴリズム)の署名を作製する、本発明に従う第2の方法を、図5によって示す。
【００８７】
Gを、qが、2160より大きい素数である次数qの楕円曲線の要素とする。この曲線は、濃度nのガロア域の要素である2つの要素aおよびbによっても定められる。
【００８８】
一組の鍵(公開鍵および秘密鍵)を生成する第1のステップ200の間に、kビットの数d、ただし0<d<qが、ランダムに決定される。
【００８９】
この数を使用して、Q=d.G mod pを計算し、ただし、演算「.」は、Gが属する楕円曲線上のスカラ積を指している。
【００９０】
公開鍵はQである。秘密鍵はdである。
【００９１】
プリミティブを適用する第2のステップ202の間に、0<u<qであるように選ばれるランダム変数uが、生成される。次いで、セクション10aは、以下のスカラ積、すなわちR=u.G=(xR,yR)を使用して、第1の出力データs1を計算する。実際には、Rの横座標xRの法の値qは、s1に割り当てられ、すなわちs1=xR mod qである。この値がゼロに等しい場合、ステップ202が再び行われ、別のランダム変数が生成される。
【００９２】
ステップ204の間に、疑似ランダムデータ生成器20は、秘密鍵dの大きさに等しい2進法表示の大きさを有する保護パラメータaを生成する。代替として、生成器20は、dの大きさよりずっと小さい大きさを有するパラメータa'を生成するが、このパラメータa'の2進法表示は、必要に応じて何度でもそれ自体と連結されて、最終的に、dの大きさに等しい2進法表示の大きさを有する保護パラメータaを与える。また代替として、生成器20は、前もって決定されたqまたはs1などのECDSAアルゴリズムの他のパラメータに組み合わされるパラメータa'を生成し、関数COMBを使用して、保護パラメータa、すなわちa=COMB(a',q,s1, ...)を与える。生成器20によって生成したパラメータ(aまたはa')は、パラメータa'をDSAアルゴリズムの他のパラメータに組み合わせてaを形成するとき、パラメータa'についての検証パラメータとして具体的には任意のやり方でその後の使用のためにメモリに保持される。
【００９３】
以下のステップ206〜216は、ステップ106〜116と同一である。したがって、ステップ206〜216は、詳述しないことにする。
【００９４】
同様に、前述の第1の方法の変形形態は、第2の方法に適用することもできる。
【００９５】
前述の署名(DSAおよびECDSA)以外の署名を作製する、本発明に従う他の方法が、実現され得る。これらの方法は、場合により、第1の出力データを得るためにそれらの方法がステップ102、202で実施するプリミティブにおいて、および第2の出力データを得ることを可能にするステップ108、114または208、214の演算において、前述の方法とは異なる。
【００９６】
例えば、本発明に従う別の方法は、Schnorrタイプの署名を実現することができる。その場合、第1の出力データの計算ステップは、ステップ102と同一である。一方、ハッシュ関数Gが、第1の出力データs1に適用されて、中間パラメータc=G(M,s1)を得る。中間パラメータcは、可能性のある変換について、s1の代わりに、アプリケーション10によって対策セクション22'に与えられる。加えて、ステップ108、114で適用される線形合同は、わずかに修正される。実際、DSA署名の線形合同は、本発明による適合以前より従来からs2= u-1(H(M)+d.s1) mod qであるのに対して、Schnorr署名の線形合同は、本発明による適合以前より従来からs2=(u+d.c) mod qである。したがって、本発明に従う方法を使用してSchnorr署名を実現するために、この演算の中で、dは、d'によって置き換えられてもよく、またはcは、c'によって置き換えられてもよい(例えば、c'=c+a)。
【００９７】
本発明に従う他の方法は、Benoit Chevallier-Mamesにより、2006年11月16日、Ecole Normale Superieure、Parisにおいて、「Public key encryption : constructions and security proofs」と呼ばれる、より詳細には4.4章の中で公に提示または定義された論文中に記載されたもののような従来の署名の同じような適合によって実現することもやはりできる。
【００９８】
本発明の第2の実施形態。
図6に示すマイクロ回路デバイス12''は、図2に示したもののように、非対称暗号化のアルゴリズムアプリケーション10と、安全なメモリ空間16を含むメモリ14と、マイクロプロセッサ18と、対策セクション22'とを備える。このデバイスは、例えば、図3に示すように、具体的には安全なICカード30の形態でポータブルデバイスに組み入れられる。しかし、アルゴリズムの暗号化アプリケーション10および対策セクション22'は、別個のように示されているが、実際にはアルゴリズムの暗号化アプリケーション10および対策セクション22'は、対策を含む暗号化アルゴリズムの同じ実装の中に十分に重なっていてもよいことに留意されたい。
【００９９】
マイクロ回路デバイス12'内と同じように、デバイス12''の非対称暗号化のアルゴリズムアプリケーション10は、フィアットシャミア法をゼロ知識証明プロトコルに適用することに本質があるタイプの署名方式の実施によりまさしく適している。したがって、非対称暗号化のアルゴリズムアプリケーション10は、
- プリミティブを適用して第1の出力データs1を生成するためのセクション10aと、
- 一方が、第1の出力データから得られ、場合により変換され、他方が、場合によって変換される秘密鍵である、少なくとも2つのオペランドを伴う演算を実行して、第2の出力データs2を生成するためのセクション10bと
を備える。
【０１００】
加えて、デバイス12''の対策セクション22'は、デバイス12'の対策セクション22'のように、保護パラメータaを使用して、秘密鍵d、および/または第1の出力データから得られる中間パラメータを変換するように構成される。DSA署名の場合、中間パラメータは、実際の第1の出力データである。
【０１０１】
デバイス12'とは違って、デバイス12''では、従来タイプの疑似ランダムデータ生成器20は、データ生成器20''によって置き換えられており、データ生成器20''は、
- 秘密のパラメータおよび関数Fからのみ決定できる複数の値からなる列を生成するために既定の関数Fに少なくとも1つの所定の秘密のパラメータSを適応するためのセクション20''aと、
- この列の少なくとも1つの値から再現可能なやり方で少なくとも1つの保護パラメータaを与えるためのセクション20''bと
を含む。
【０１０２】
実際には、セクション20''aは、関数Fのソフトウェアまたはハードウェアの実施である。
【０１０３】
秘密のパラメータSは、安全なメモリ16に記憶され、生成器20''のセクション20''aの入力において与えられ、一方、保護パラメータaは、セクション20''bの出力において対策セクション22'へ与えられる。
【０１０４】
したがって、この第2の実施形態では、パラメータaは、最新の文献に述べられた従来の意味のランダム変数ではない。パラメータaは、マイクロ回路12'が配置されるICカード30に固有であり得る少なくとも1つの秘密のパラメータSに基づいて生成器20''によって実行される関数Fの計算から生じる決定性の結果である。例えば、秘密のパラメータは、デバイス30の公開データから得られる。
【０１０５】
関数FをSに繰り返し適用することにより、要素が生成器によって与えられる保護パラメータの源である列(An)を生成する。全体的に、生成器は、カード30において実施される対策アプリケーションにより必要にされるのと同じくらい多くの、列(An)の値からもたらされるパラメータを与えることができる。この列(An)は、生成関数Fおよびその関数が使用する最初の決定性の要素(パラメータS)が分かるときのみ、再現することができる。
【０１０６】
各保護パラメータaは、列(An)の要素Anから直接もたらされ得るものであり、言い換えれば、a=Anである。代替として、要素Anは、パラメータaを与える前に処理を受けてもよい。例えば、aは、計算a=An XOR knの結果であり得るものであり、ここでknは、秘密の変換定数である。
【０１０７】
明らかに、列(An)が、要素の有限集合内において巡回でありおよび/または動作する場合、生成される値Anの空間は、攻撃に耐えるのに十分大きいものでなければならない。実際には、空間がより大きく考えられるほど、対策はより信頼できるものになる。
【０１０８】
まず、本発明の第2の実施形態による生成器20''によって与えられ得る、複数の値からなる列(An)のいくつかの非限定の例を示すことにする。次いで、具体的には図4および図5を参照して前述した両方の非対称暗号化の対策の適用例に保護パラメータを与えるために、複数の値からなるそのような列のいくつかの可能性のある使用を公表することにする。
【０１０９】
保護パラメータを与えるための複数の値からなる列の関数生成器の例
【０１１０】
1)等差等比数列に基づいた関数
【０１１１】
複数の値からなる列(An)が、式中qおよびrが、列の最初の要素A0を伴って前述の秘密のパラメータSを構成している、以下の関係、すなわち、
An+1=F(An)=q.An+r
による整数値関数Fを使用して定められる場合、等差等比数列からもたらされる保護パラメータを与えることができる。例えば、これらの保護パラメータは、列(An)の要素である。
【０１１２】
r=0の場合、列(An)は、等比列であり、暗号化の正確なステップ(precise step)で使用される列(An)の等比列の項Aiは、秘密のパラメータqおよびA0を使用して、以下のように見出すことができ、すなわち、Ai=qi.A0である。
【０１１３】
q=1の場合、列(An)は、等差数列であり、列(An)の項Aiは、秘密のパラメータrおよびA0を使用して、以下のように見出すことができ、すなわち、Ai=r.i+A0である。
【０１１４】
rがゼロに等しくなく、qが1と異なる場合、列(An)は、等差等比列であり、列(An)の項Aiは、秘密のパラメータq、rおよびA0を使用して、以下のように見出すことができ、すなわち、
Ai=qi.A0+r.(qi-1)/(q-1)
である。
【０１１５】
列(An)の要素の空間は、以下の関係式、すなわち、
An+1=F(An) modulo m=(q.An+r) modulo m
を使用して、整数mによって変形することもできる。
【０１１６】
mが素数である場合、この列は、有限フィールドGF(m)={0,1, ..., m-1}上で逆アフィン変換の群(group of reverse affine transformation)の形をとることに気づくことができよう。
【０１１７】
mは、複数ビットの定数で要素の列を生成するように2の累乗として選ぶこともできる。例えば、kビットのパラメータAiの列を生成することが望まれる場合、m=2kが、選ばれる。
【０１１８】
好ましくは、mは、デバイスの安全なメモリに保持される秘密のパラメータの一部である。
【０１１９】
2)巡回乗法群(cyclic multiplicative group)を定める関数
【０１２０】
GCをm個の要素を有する巡回群とし、値aを生成器の要素とし、および乗法を構成の内部原理(internal principle)として、すなわちGC={a,a2, ..., am}とする。複数の値からなる列(An)は、以下のように定めることができ、すなわち、
- 最初の要素A0は、群GCの構成の内部原理がk回適用される生成器の要素aであるように選ばれる
- 群GCの構成の内部原理は、要素Aiから要素Ai+1まで通過するのにk'回適用される
である。
【０１２１】
このとき、列(An)を生成するこの関数によって使用される秘密のパラメータSは、例えば、生成器の要素a、値k、k'およびmである。加えて、前のように、生成される保護パラメータは、例えば列(An)の要素である。
【０１２２】
3)フロベニウス群を定める関数
【０１２３】
GF(q)を、次数qが、kビットの素数である有限フィールドとする。この有限フィールド上の逆アフィン変換の群は、フロベニウス群である。フロベニウス群の興味深い特性は、非自明な要素が、2つ以上の点を固定することである。
【０１２４】
この文脈において、使用できるアフィン変換は、関数y=f(x)=b.x+cの形をとり、ただしb≠0であり、演算は、フィールドGF(q)内で行われる。したがって、所定の秘密のパラメータq、b、cおよびA0に適用する列(An)を生成する関数を定めることができる。例えば、q=216+1、16進法でb=0x4cd3、c=0x76bb、A0=0xef34を選ぶことによって、項A1=0xc6cf、A2=0x8baf、A3=0x620d、A4=0x0605、A5=0xe70c、A6=0x3049、A7=0xe069、A8=0x55eeなどから始まる列が得られる。
【０１２５】
4)線形フィードバックのシフトレジスタ(LFSRタイプのレジスタ)からもたらされる関数
【０１２６】
このタイプの関数は、例えば16ビットの秘密のパラメータA0を選び、LFSRシフトレジスタは、例えば16ビットの対応する出力を有する。LFSRレジスタの大きさが、mである場合、列(An)の項At+mは、
At+m=αm.At+αm-1.At+1+...+α1.At+m-1
のタイプの一次方程式を用いてm個の前の項によって決定され、ここで、αiは、値0または1をとる。
【０１２７】
5)周期的冗長検査(CRC:Cyclic Redundancy Check)の計算を定める関数
【０１２８】
このタイプの関数は、例えば16ビットの秘密のパラメータA0、および従来からCRCの計算で使用されているものの中で対応する多項式のCRC、例えば多項式のCRC-16(X16+X15+X2+1)または多項式のCRC CCITT V41 (X16+X12+X5+1)を選ぶ。列(An)の項An+1は、関係An+1=F(An)によって前の項Anに従って決定され、ここでFは、選ばれた多項式に基づいたCRCの計算を行うものである。
【０１２９】
6)複数の値からなる列の組み合わせ
【０１３０】
例えば、それぞれが、本明細書で詳述した方法のうちの1つに従う複数の値からなるいくつかの列を計算し、次いで既定の関数を使用して組み合わせ、保護パラメータとして使用される複数の値からなる新しい列を生成することも実際にできる。このようにして、列(An)は、各添え字nごとにAn=T(A'n,A''n)を計算することによって2つの他の列(A'n)および(A''n)に従って生成される。
【０１３１】
関係している関数Tは、複数の値からなる秘密のマトリックスであってもよく、このとき、値A'nおよびA''nはそれぞれ、このマトリックスの行列に言及している。
【０１３２】
7)複数の値からなる列および公開データを伴う組み合わせ
【０１３３】
列(An)は、第1の列(A'n)から、さらに対策を用いた、秘密でない、例えば暗号化アプリケーションの実行中に使用されるデータのような、公開データに従って生成されてよい。これらのデータの中で、この適用例により、(はっきり見えるまたは符号化された)メッセージM、公開鍵eなどが、引用することができる。次いで、保護パラメータとして使用される列の値が、これらのデータ全てを組み合わせる任意の関数COMB、すなわち、
An=COMB(A'n,M,e, ...)
を用いて計算される。
【０１３４】
この組み合わせの利点は、複数の値の列(An)を使用して、保護パラメータを暗号化アルゴリズムの対策アプリケーションに供給するだけでなく、(具体的には公開データで)フォールトインジェクションによる攻撃を検出できることである。実際には、例えば、暗号化アルゴリズムの実行の終わり、しかし再生成した保護パラメータを使用して最初の変換の逆演算を行う前に、秘密のパラメータ(S)を使用して列(A'n)を再生成し、次いで、実行の終わりに現れるようなこの再生成した列(A'n)および公開データを使用することによって、関数COMBのアプリケーションが、複数の値からなる同じ列(An)を生成しているかどうか、したがって公開データが、実行中に影響を受けたかどうか検査することができる。
【０１３５】
本発明の第2の実施形態による非対称暗号化の対策方法における前述の方法のうちの1つに従って生成される複数の値からなる列の使用の例
【０１３６】
1)第2の実施形態の一般的原理
【０１３７】
一般に、疑似ランダムデータ生成器20を使用する第1の実施形態に記載されていたように、アルゴリズムの対策を使用する度に、この対策により導入されるランダム変数を生成することが推奨される。図6を参照して述べるように、ランダム変数の生成は、少なくとも1つの秘密のパラメータを使用して得られる複数の値からなる1つまたは複数の列からもたらされるランダムでないパラメータ生成によって置き換えられてもよい。
【０１３８】
図7は、実行によってT個の保護パラメータa1, ... aTを使用する対策で非対称暗号化アルゴリズムの実行に適用される図6の第2の実施形態による方法によって行われるステップの例を示しており、全ての保護パラメータは、セクション20'aにより生成される複数の値からなる同じ列(An)から得ることができる。
【０１３９】
生成器20''によって行われる第1のステップINITの間に、カウンタiは、リセットされる。カウンタiは、別のリセットが行われない限りリセットステップINIT以来の非対称暗号化アルゴリズムが実行された回数をメモリに保持するためのものである。
【０１４０】
このステップの間に、複数の値からなる列の生成に必要な秘密のパラメータS(または2つ以上あるときにはこれらのパラメータS)が、定められる。秘密のパラメータSは、前のリセットから保持することができるが、リセットのときには新しい値に基づいて生成されてもよい。例えば、秘密のパラメータSは、デバイス30の公開データなどの固有の識別データから生成される。秘密のパラメータSは、ランダムであってよい所与の時間にマイクロ回路に関連しているパラメータまたは物理現象から生成されてもよい。ともかく、秘密のパラメータSは、安全なやり方でメモリに保持されて、マイクロ回路が、セクション20''aによって実施される関数を使用して複数の値の同じ列(An)をいつでも生成することを可能にする。
【０１４１】
リセットステップINITは、マイクロ回路のライフサイクルにおいて独特であり得るものであり、設計中には製造者によって行われ、または例えば定期的またはカウンタiが値imaxに到達する度に数回再び引き起こされる。
【０１４２】
対策を用いた非対称暗号化アルゴリズムの第1の実行EXE1の間に、生成器20''、より具体的にはセクション20''aは、秘密のパラメータSを既定の関数Fに適用するために1回または複数回要求され、それによって複数の値からなる列(An)のT個の要素、すなわちA1, ... ATを1回または複数回に生成する。これらT個の第1の要素から、T個の保護パラメータa1, ... aTが、生成される。
【０１４３】
例えば、1≦k≦T、ak=Akなどの任意のk個についてである。
【０１４４】
代替として、安全なメモリに保持される秘密のパラメータSの中にT個の追加の秘密の値Sec1, ... SecTがある場合、以下の追加の計算を行うことができ、すなわち、
1≦k≦Tのような任意のkについて、ak = Seck XOR Ak、またはak=Seck ADD Ak、またはak=Seck SUB Ak,であり、それにより使用されるパラメータを変換する(または歪ませ、もしくはマスクする)。
【０１４５】
その後、対策を用いた暗号化アルゴリズムのi番目の実行EXEiの間に、生成器20''、より具体的にはセクション20''aは、秘密のパラメータSを既定の関数Fに適用するためにやはり1回または複数回要求され、それによって複数の値からなる列(An)のT個の追加の要素、すなわち:AT(i-1)+1, ... ATiを1回または複数回で生成する。これらT個の追加の要素から、T個の保護パラメータa1, ... aTが、前のように生成される。
【０１４６】
例えば、1≦k≦T、ak=AT(i-1)+kなどの任意のk個についてである。
【０１４７】
代替として、T個の追加の秘密の値Sec1, ... SecTがある場合、以下の追加の計算を行うことができ、すなわち、
1≦k≦Tのような任意のkについて、ak=Seck XOR AT(i-1)+k、またはak=Seck ADD AT(i-1)+k、またはak=Seck SUB AT(i-1)+kであり、それにより使用されるパラメータを変換する(または歪ませ、もしくはマスクする)。
【０１４８】
保護パラメータの始めにある複数の値からなる列を生成するために使用される、この方法によって使用される方法および秘密の値が分かっている、メモリの中に前もってまたはメモリEEPROM中のマイクロ回路デバイスのライフサイクルのあるステップ中にロードされた最初のパラメータA0を含んだいかなる方法でも、デバイスのライフ中に生成および使用された保護パラメータをいつでも見出すことを可能にさせる。そこで、この特色により簡単および効果的なデバッグが行われ、フォールトインジェクションによる攻撃に対する抵抗が向上することを可能にすることが明らかであるように思われる。
【０１４９】
複数の値からなる列および保護パラメータを生成するために使用される方法の選択は、考えられるアプリケーションによって決まる。
【０１５０】
2)図4および図5を参照して説明した2つの方法への第2の実施形態の一般的原理の適用
【０１５１】
ステップ104および204の間に保護パラメータaまたはパラメータa'を生成するために図4および図5の第1の方法および第2の方法によって使用される方法は、第2の実施形態において推奨されるものの1つであり得る。したがって、このパラメータa'および保護パラメータaは、秘密のパラメータおよび関数Fによって決定される複数の値からなる列からいつでも見出すことができるので、このパラメータa'および保護パラメータaは、メモリに保持される必要はなくてもよい。これらのパラメータを再生成することに本質があるこのプロセスは、フォールトインジェクションによる攻撃に対して実施を保護するのに役立つステップでさえもある。したがって、パラメータa'は、ステップ104および204の実行中に前もってメモリに保持される必要なくステップ110および210で見出すことができる。これらのステップ110および210で、保護パラメータaは、その完全性、および保護パラメータaを生成するために使用されるパラメータの完全性が、保持されていることを検査するために見出すこともできる。このパラメータを使用するステップ112および212を行うためにaを再生成することも役立つ。
【０１５２】
前述の対策方法は、補助チャンネルまたはフォールトインジェクションによる攻撃に対して使用される秘密鍵を保護する非対称暗号化アプリケーションを実現することを可能にすることが明らかであるように思われる。
【０１５３】
加えて、本発明は、前述の実施形態に限定されず、多数の変形形態が示されたが、説明した変換以外の具体的には秘密鍵の他のタイプの変換、または上記で扱ったもの以外の他の非対称暗号化アプリケーションを与える他の形態も考えることができることに留意されたい。
【符号の説明】
【０１５４】
10  非対称暗号化のアルゴリズムアプリケーション
10a  セクション
10b  セクション
12  マイクロ回路
12'  マイクロ回路デバイス
12''  マイクロ回路デバイス
14  メモリ
16  安全なメモリ空間
18  マイクロプロセッサ
20  疑似ランダムデータ生成器
20''  データ生成器
20''a  セクション
20''b  セクション
22  対策セクション
22'  対策セクション
30  ICカード
106  マスキングステップ
108  計算するステップ
110検証ステップ
116  最終ステップ
a  保護パラメータ、要素
a'  パラメータ
(An)  列
An  要素
A0  最初の要素
b  要素
c  中間パラメータ
d  秘密鍵
d'  変換した秘密鍵
d  数、秘密鍵
e  公開鍵
F  関数、プリミティブ、生成関数
G  ハッシュ関数
h  数
i  カウンタ
m  整数
M  メッセージ
n  濃度
P  入力データ、プリミティブ
p  素数
q  素数、次数
S  パラメータ
s1  第1の出力データ
s1'  第1の変換した出力データ
s2  第2の出力データ
T  関数
u  ランダム変数u
xR  横座標
z  整数
【図１】
2011510579.tif 000003
【図２】
2011510579.tif 000004
【図３】
2011510579.tif 000005
【図４】
2011510579.tif 000006
【図５】
2011510579.tif 000007
【図６】
2011510579.tif 000008
【図７】
2011510579.tif 000009
【手続補正書】
【提出日】平成22年9月24日(2010.9.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
非対称秘密鍵暗号化アルゴリズムを実施する電子コンポーネントにおける対策方法であって、
- プリミティブを使用して第1の出力データを生成する段階と、
- 保護パラメータを生成する段階と
を含み、
- 前記保護パラメータを使用して、前記秘密鍵、および前記第1の出力データから得られる中間パラメータからなるセットの要素のうちの少なくとも1つを変換して、第1のオペランドおよび第2のオペランドをそれぞれ与える段階と、
- 前記第1のオペランドおよび前記第2のオペランドを伴う演算から、第2の出力データを生成する段階と
をさらに含む電子コンポーネントにおける対策方法。
【請求項２】
- 前記保護パラメータを使用して、前記秘密鍵を変換する段階と、
- 前記中間パラメータおよび前記変換した秘密鍵を伴う第1の演算から、第1の中間データを生成し、前記中間パラメータおよび前記保護パラメータを伴う第2の演算から、第2の中間データを生成し、前記第1の中間データおよび前記第2の中間データを組み合わせて前記第2の出力データを与える段階と
を含む、請求項1に記載の電子コンポーネントにおける対策方法。
【請求項３】
- 前記保護パラメータを使用して、前記第1の出力データから得られる前記中間パラメータを変換する段階と、
- 前記変換した中間パラメータおよび前記秘密鍵を伴う第1の演算から、第1の中間データを生成し、前記保護パラメータおよび前記秘密鍵を伴う第2の演算から、第2の中間データを生成し、前記第1の中間データおよび前記第2の中間データを組み合わせて前記第2の出力データを与える段階と
を含む、請求項1に記載の電子コンポーネントにおける対策方法。
【請求項４】
前記中間パラメータが、前記第1の出力データである、請求項1から3のいずれかに記載の電子コンポーネントにおける対策方法。
【請求項５】
前記プリミティブが、DSAタイプの署名方式を用いて暗号化アルゴリズムを実施するための冪乗剰余である、請求項4に記載の電子コンポーネントにおける対策方法。
【請求項６】
前記プリミティブが、ECDSAタイプの署名方式を用いて暗号化アルゴリズムを実施するためのスカラ乗法である、請求項4に記載の電子コンポーネントにおける対策方法。
【請求項７】
フィアットシャミア法をゼロ知識証明プロトコルに適用することに本質があるタイプの署名方式を用いて非対称暗号化アルゴリズムを実施する、請求項1から6のいずれかに記載の電子コンポーネントにおける対策方法。
【請求項８】
前記保護パラメータを前記生成する段階が、
メモリに記憶された所定の少なくとも1つの秘密のパラメータに連続して適用することによって生成関数を定める段階であって、前記秘密のパラメータおよび前記関数からのみ決定できる複数の値からなる列の生成関数を定める段階と、
前記列の少なくとも1つの値から再現可能なやり方で前記保護パラメータを生成する段階と
を含む、請求項1から7のいずれかに記載の電子コンポーネントにおける対策方法。
【請求項９】
メモリに記憶された所定の少なくとも1つの対応する秘密のパラメータに連続して適用することによって複数の関数を定める段階であって、前記対応する秘密のパラメータおよび前記対応する関数からのみ決定できる複数の値からなる対応する列の各関数が生じる、複数の関数を定める段階と、
既定の関係を使用して、生成した複数の値からなる複数の前記列を組み合わせて複数の値からなる新しい列を生成する段階と、
前記新しい列の少なくとも1つの値から再現可能なやり方で前記保護パラメータを生成する段階と
を含む、請求項8に記載の電子コンポーネントにおける対策方法。
【請求項１０】
メモリに記憶された所定の少なくとも1つの秘密のパラメータに連続して適用することによって生成関数を定める段階であって、前記秘密のパラメータおよび前記関数からのみ決定できる複数の値からなる列の生成関数を定める段階と、
生成した複数の値からなる前記列と前記暗号化アルゴリズムの公開パラメータを組み合わせることによって、複数の値からなる新しい列を生成する段階と、
前記新しい列の少なくとも1つの値から再現可能なやり方で前記保護パラメータを生成する段階と
を含む、請求項8に記載の電子コンポーネントにおける対策方法。
【請求項１１】
前記変換を行った後に、前記保護パラメータを再生成して、前記第2の出力データを生成する前記段階の間に前記保護パラメータを使用する段階を含む、請求項8から10のいずれかに記載の電子コンポーネントにおける対策方法。
【請求項１２】
非対称秘密鍵暗号化アルゴリズムの対策方法を実施するためのマイクロプロセッサと、前記秘密鍵を記憶するための少なくとも1つの安全なメモリと、保護パラメータを生成するためのデータ生成器とを備えるマイクロ回路デバイスであって、
- プリミティブを使用して第1の出力データを生成し、
- 前記保護パラメータを使用して、前記秘密鍵、および前記第1の出力データから得られる中間パラメータからなるセットの要素のうちの少なくとも1つを変換して、第1のオペランドおよび第2のオペランドをそれぞれ与え、
- 前記第1のオペランドおよび前記第2のオペランドを伴う演算から、第2の出力データを生成するように構成されるマイクロ回路デバイス。
【請求項１３】
- 前記保護パラメータを使用して、前記秘密鍵を変換し、
- 前記中間パラメータおよび前記変換した秘密鍵を伴う第1の演算から、第1の中間データを生成し、前記中間パラメータおよび前記保護パラメータを伴う第2の演算から、第2の中間データを生成し、前記第1の中間データおよび前記第2の中間データを組み合わせて前記第2の出力データを与える
ように構成される、請求項12に記載のマイクロ回路デバイス。
【請求項１４】
- 前記保護パラメータを使用して、前記第1の出力データから得られる前記中間パラメータを変換し、
- 前記変換した中間パラメータおよび前記秘密鍵を伴う第1の演算から、第1の中間データを生成し、前記保護パラメータおよび前記秘密鍵を伴う第2の演算から、第2の中間データを生成し、前記第1の中間データおよび前記第2の中間データを組み合わせて前記第2の出力データを与える
ように構成される、請求項12に記載のマイクロ回路デバイス。
【請求項１５】
前記中間パラメータが、前記第1の出力データである、請求項12から14のいずれかに記載のマイクロ回路デバイス。
【請求項１６】
前記プリミティブが、DSAタイプの署名方式を用いて暗号化アルゴリズムを行うための冪乗剰余である、請求項15に記載のマイクロ回路デバイス。
【請求項１７】
前記プリミティブが、ECDSAタイプの署名方式を用いて暗号化アルゴリズムを行うためのスカラ乗法である、請求項15に記載のマイクロ回路デバイス。
【請求項１８】
前記マイクロプロセッサが、フィアットシャミア法をゼロ知識証明プロトコルに適用することに本質があるタイプの署名方式を用いて非対称暗号化アルゴリズムを実施する、請求項12から17のいずれかに記載のマイクロ回路デバイス。
【請求項１９】
前記データ生成器が、
メモリに記憶された所定の少なくとも1つの秘密のパラメータに連続して適用することによって生成関数を定めるものであって、前記秘密のパラメータおよび前記関数からのみ決定できる複数の値からなる列の生成関数を定め、
前記列の少なくとも1つの値から再現可能なやり方で前記保護パラメータを生成することによって前記保護パラメータを生成するように構成される、請求項12から18のいずれかに記載のマイクロ回路デバイス。
【請求項２０】
前記データ生成器が、
メモリに記憶された所定の少なくとも1つの対応する秘密のパラメータに連続して適用することによって複数の関数を定めるものであって、前記対応する秘密のパラメータおよび前記対応する関数からのみ決定できる複数の値からなる対応する列の各関数が生じる、複数の関数を定め、
既定の関係を使用して、生成した複数の値からなる複数の前記列を組み合わせて複数の値からなる新しい列を生成し、
前記新しい列の少なくとも1つの値から再現可能なやり方で前記保護パラメータを生成する
ように構成される、請求項19に記載のマイクロ回路デバイス。
【請求項２１】
前記データ生成器が、
メモリに記憶された所定の少なくとも1つの秘密のパラメータに連続して適用することによって生成関数を定めるものであって、前記秘密のパラメータおよび前記関数からのみ決定できる複数の値からなる列の生成関数を定め、
生成した複数の値からなる前記列と前記暗号化アルゴリズムの公開パラメータを組み合わせることによって、複数の値からなる新しい列を生成し、
前記新しい列の少なくとも1つの値から再現可能なやり方で前記保護パラメータを生成する
ように構成される、請求項19に記載のマイクロ回路デバイス。
【請求項２２】
前記変換を行った後に、前記保護パラメータを再生成して、前記第2の出力データを生成する段階の間に前記保護パラメータを使用するように構成される、請求項19から21のいずれかに記載のマイクロ回路デバイス。
【請求項２３】
請求項12から22のいずれかに記載のマイクロ回路デバイスを備えるポータブルデバイス、特にICカード。
【国際調査報告】
2011510579.tif 000010
2011510579.tif 000011
2011510579.tif 000012
2011510579.tif 000013
2011510579.tif 000014
2011510579.tif 000015
2011510579.tif 000016
2011510579.tif 000017