非対称暗号のための防護方法およびデバイス

专利摘要:
本発明は、秘密鍵の非対称暗号方式アルゴリズムを使用する電子コンポーネントにおける防護方法であって、保護パラメータを生成する段階(100)と、基本関数を使用して保護パラメータから中間データを計算する段階(104)とを含む防護方法に関する。この方法は、秘密鍵の２進表現をいくつかのバイナリユニットに分ける段階(110)と、保護パラメータを使用して各バイナリユニットを変換し(112)、変換されたバイナリユニットごとに、基本関数を使用して中間計算を行う段階(114)と、中間データを中間計算の結果(114)と組み合わせる(116)ことによって出力データを計算する段階(106〜122)とをさらに含む。
公开号:JP2011510578A
申请号:JP2010543543
申请日:2009-01-23
公开日:2011-03-31
发明作者:セバスチャン・ネロ；ブノワ・フェ；ブルーノ・ベンテオ
申请人:インサイド・コンタクトレス；
IPC主号:H04L9-08

专利说明:

[0001] 本発明は、秘密鍵を発見することを目的とする攻撃に耐える、非対称秘密鍵暗号アルゴリズムを実現する電子コンポーネントにおける防護方法に関する。また、本発明は、そのような方法を実現するマイクロ回路デバイスおよびポータブルデバイス、特にチップカードに関する。]
背景技術

[0002] 図１に示すように、秘密鍵dの使用を伴う非対称暗号アルゴリズムのアプリケーション10は、一般に、秘密鍵を使用して、メッセージの署名によってメッセージMの伝送を認証し、または、このメッセージを解読することによる暗号化されたメッセージMの受信を保護するマイクロ回路12によって実現される。秘密鍵dは、例えば、マイクロ回路12内に記憶されており、マイクロ回路12は、その目的のために設けられた安全なメモリ空間16を含むメモリ14と、非対称暗号アルゴリズム10を実行するマイクロプロセッサ18とを備える。] 図１
[0003] 暗号アルゴリズムを実現するマイクロ回路デバイスは、使用される鍵のようにマイクロ回路デバイスが使用する秘密データ、および、場合によっては実際のメッセージの情報を突き止めることを目的とする攻撃を時々受ける。特に、非対称暗号アルゴリズムは、その使用時に、秘密鍵を発見することを目的とする攻撃を受ける。サイドチャネルによるこの攻撃は、暗号アルゴリズムのソフトウェアまたはハードウェアの実装に関するいつくかの特性を利用する主要な一群の暗号技法を構成する。]
[0004] サイドチャネルを通じての知られた攻撃の中で、SPA型(単純電力解析:Simple Power Analysis)の攻撃、またはDPA型(差分電力解析:Differential Power Analysis)の攻撃は、非対称暗号アルゴリズムの実行中にマイクロ回路の入出力電流および入出力電圧を測定し、それによりそこから秘密鍵を推定することに本質がある。この種の攻撃の実現可能性は、具体的には非特許文献１の論文で論証されている。]
[0005] 時間的な攻撃(temporal attacks)は、いくつかの動作を実行するための時間を解析する。非対称暗号アルゴリズムに対するそのような攻撃は、具体的には非特許文献２の論文に説明されている。]
[0006] 故障注入(fault injection)による攻撃も知られており、その中でDFA(差分故障解析:Differential Fault Analysis)により攻撃するものがあり、これは、暗号アルゴリズムの実行中に、例えば暗号アルゴリズムが実行されているマイクロ回路を乱すことによって自発的に故障を引き起こすことに本質がある。そのような乱れには、マイクロ回路を１回(または複数回)短時間照明すること、または１つまたは複数の電圧ピークをマイクロ回路の接点のうちの１つに発生させることが含まれ得る。したがって、この乱れは、ある条件下で発生した計算エラーおよび挙動エラーを利用して求めている秘密鍵の一部またはさらには全部を得ることを可能にする。]
[0007] 具体的には、(その著者Rivest、Shamir、Adlemanにちなんで)RSAという名で知られている非対称暗号アルゴリズムの実行中に、べき乗剰余からなる基本関数が実行される。基本関数の効果的な実現は、秘密鍵dの２進表現を、この２進表現の１ビットごとに反復を行うことによって使用する。各反復において、この計算がなされ、事実上、計算中のエネルギー消費は、関係しているビットの値に依存する。したがって、そのような基本関数の実行は、秘密鍵を前述の攻撃に対して特に脆弱にさせる。同様に、楕円曲線を使用するこの非対称暗号アルゴリズムの適用の実行中に、スカラ乗算からなる基本関数が実行される。この基本関数の効果的な実現は、秘密鍵dの２進表現を、この２進表現の１ビットごとに反復を行うことによって使用する。同様に、各反復において、計算中のエネルギー消費は、関係しているビットの値に依存する。したがって、そのような基本関数の実行は、やはり安全上の理由から秘密鍵に採り入れることができるスカラ値を攻撃に対して特に脆弱にさせる。]
[0008] 性質が様々であるこれらの攻撃と戦うために、多数のとてもいろいろな解決策が、見出されてきた。より具体的には、本発明は、非対称秘密鍵暗号アルゴリズムを実現する電子コンポーネントにおける防護方法であって、
−保護パラメータを生成する段階と、
− 暗号アルゴリズムの基本関数を使用して入力データおよび保護パラメータに基づいて中間データを計算する段階と、
を含む防護方法を実現する解決策に関する。]
[0009] これらアルゴリズムは通常、生成された保護パラメータを用いて秘密鍵を変換して、変換された秘密鍵に基本関数を適用し、得られた結果を中間データと組み合わせることを行う。]
[0010] 一般的に、保護パラメータaは、従来から疑似ランダムデータ生成器20を使用して生成され、また、その結果、暗号アルゴリズム10による基本関数の実行は、例えばマスキングと通常呼ばれる技法によって、ランダムで、使用した秘密鍵から相関を失ったものにさせられ、この技法は、保護パラメータaを使用してマイクロプロセッサ18の防護セクション22によって行われるときに使用される処理とは対照的にその処理が歪まされるので、データを変換し、またはデータを歪ませる方法と言い換えることもできる。このようにして、暗号アルゴリズムの中間データ、および結果として、測定可能な電流は、ランダムな保護パラメータによって修正され、その観察により秘密鍵の真の値を見つけることを不可能にする。一方、マスキングは、実際のアルゴリズムを乱さず、したがって、それによりマスキングの有無にかかわらず同じ結果を与える。]
[0011] このタイプの方法は、例えば、特許文献１に記載されている。]
[0012] この文献には、RSA型の非対称暗号の分野の実施形態が、図３を参照して説明されている。公開鍵eおよび秘密鍵dにおいて、署名または暗号解読を行うために基本関数を実行するRSAアルゴリズムは、入力データMおよび秘密鍵dに基づいて出力データSを以下のように計算することからなり、すなわち、
S=Md mod Nであり、ここで、Nは、RSAの剰余、つまり２つの秘密の整数の積であり、式中eおよびdは、e・d=φ(N)の関係を検証し、この関数φ(・)は、オイラー指標関数(Euler indicator function)を表す。] 図３
[0013] [dn-1, ..., d0]2を秘密鍵dの２進表現とすると、この計算は、以下のように行うことができ、すなわち、
S=1
n-1から0まで変化するiについて、
S←S2 mod N
di=1の場合、S←S×M mod N
である。]
[0014] 特許文献１に記載された攻撃に耐えるRSAアルゴリズムの実施形態は、保護パラメータd1を以下のように生成する第1のステップ300を含み、ランダムに選ばれる素数kは、0最大公約数》関数である)であるようにランダムに選ばれる。]
[0015] 次いで、この秘密鍵は、以下のように、すなわち、d2=d×(d1-1 mod z) mod zに変換される。]
[0016] 入力データMを受け取った後に、新たな変換が、以下の２つの計算(ステップ345およびステップ350)、すなわち、
− S0=Md1 mod N(入力データMおよび保護パラメータd1に基づく中間データS0の基本関数からの計算)、
− S=S0d2 mod N(中間データS0と、変換された秘密鍵d2に基本関数を適用したものと組み合わせることによる出力データの計算)
を行う前に、d1およびd2に基づいて行われる。]
[0017] また、より簡単にではあるが特許文献１に記載された攻撃に耐えるRSAアルゴリズムの別の実施形態は、保護パラメータd1が0ランダムに選ばれる第１のステップを含む。]
[0018] 次いで、秘密鍵は、以下のように、すなわち、d2=d-d1で変換される。]
[0019] 入力データMを受け取った後に、新たな変換が、以下の２つの計算、すなわち、
− S1=Md1 mod N(入力データMおよび保護パラメータd1に基づく中間データS1の基本関数からの計算)、
− S2=Md2 mod N、S=S1・S2 mod N(中間データS1と、変換された秘密鍵d2に基本関数を適用したものS2と組み合わせることによる出力データSの計算)
を行う前に、d1およびd2に基づいて行われる。]
[0020] 米国特許第６，３８１，６９９号明細書]
先行技術

[0021] P. Kocher, J. Jaffe, B. Jun, “Differential Power Analysis”, Advances in Cryptology - Crypto 99 Proceedings, Lecture Notes In Computer Science, M. Wiener, ed., Springer-Verlag, 1999年, Vol. 1666
P. Kocher, N. Koblitz, “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, andothersystems”, Advances in Cryptology - Crypto 96, 16th annual international cryptology conference, Proceedings, 1996年8月18-22日]
発明が解決しようとする課題

[0022] 前述の２つの現状の技術の場合のそれぞれでは、秘密鍵dは、少なくとも２つの指数d1およびd2に分けられ、それらの大きさは、dの大きさと比較することができ、その結果、RSAアルゴリズムは、１つではなく少なくとも２つのべき乗剰余の実行を強いることによってより複雑にさせられる。このようにして、サイドチャネルによる一部の攻撃に耐える非対称暗号アルゴリズムが、実現されているが、実際には複雑さが倍になるので、実現について複雑さがかなり増加しているという代償を払っている。]
課題を解決するための手段

[0023] したがって、前述のタイプの攻撃に耐える、実現するのが簡単である非対称暗号の方法を提供することが望まれ得る。]
[0024] 本発明の一実施形態は、非対称秘密鍵暗号アルゴリズムを実現する電子コンポーネントにおける防護方法であって、
−保護パラメータを生成する段階と、
− 当該暗号アルゴリズムの基本関数を使用して入力データおよび保護パラメータから中間データを計算する段階と、
を含み、
−秘密鍵の２進表現をいくつかのバイナリブロックに分割する段階と、
− 保護パラメータを使用して各バイナリブロックを変換し、変換された各バイナリブロックについて基本関数を使用して中間計算を実行する段階と、
− 中間データを中間計算の結果と組み合わせることによって出力データを計算する段階と、
をさらに含む、電子コンポーネントにおける防護方法に関する。]
[0025] このようにして、秘密鍵の完全な２進表現ではなく、保護パラメータを使用してバイナリブロックを変換する。したがって、保護パラメータの２進表現の大きさは、明らかに、秘密鍵の２進表現の大きさよりも、すなわちバイナリブロックの大きさの程度、小さいものであり得る。基本関数の実行数が増加する場合でも、この実行は、より小さい大きさのバイナリデータで動作するので、したがって、計算が簡単化される。結局、このようにして、非対称暗号アルゴリズムの実行は、従来の防護方法に比べてその複雑さをかなり減少させることで保護できる。]
[0026] 一実施形態によれば、この防護方法は、各バイナリブロックの大きさが保護パラメータの２進表現の大きさより大きいか、または、等しいように、秘密鍵の２進表現を分割する段階を含む。]
[0027] 一実施形態によれば、この防護方法は、バイナリブロックの大きさの和が秘密鍵の２進表現の大きさより大きいように、秘密鍵の２進表現をいくつかのバイナリブロックに分割する段階を含む。]
[0028] 一実施形態によれば、この防護方法は、各バイナリブロックの値が保護パラメータの値より大きいように、各バイナリブロックの大きさを、反復してランダムに決定する段階を含む。]
[0029] 一実施形態によれば、この防護方法は、
− nが秘密鍵の２進表現の大きさであり、n=k・uである整数u≧2が存在するように、保護パラメータの２進表現の大きさkを選択する段階と、
− 秘密鍵の２進表現をそれぞれkビットのu個のバイナリブロックに分割する段階と、
を含む。]
[0030] 一実施形態によれば、この基本関数は、RSAまたはRSA CRT型の暗号アルゴリズムを実行するための秘密鍵による入力データのべき乗剰余である。]
[0031] 一実施形態によれば、この防護方法は、RSAの剰余および入力データを前もってマスクする段階を含む。]
[0032] 一実施形態によれば、この基本関数は、楕円曲線に基づく暗号アルゴリズムを実行するための秘密鍵による入力データのスカラ乗算であり、
入力データは、楕円曲線の予め決定された点である。]
[0033] 一実施形態によれば、この防護方法は、楕円曲線の予め決定された点を前もってマスクする段階を含む。]
[0034] 一実施形態によれば、この防護方法は、
−再現可能なやり方で、基本関数の実行前に少なくとも１つの検証パラメータを初期生成する段階と、
− 基本関数の実行中または実行後に検証パラメータを再生成し、再生成された検証パラメータを初期生成された検証パラメータと比較する段階と、
をさらに含む。]
[0035] 一実施形態によれば、この基本関数が変換されたバイナリブロックに適用されるときに、再生成および比較する段階が基本関数の反復ごとに実行される。]
[0036] 一実施形態によれば、この防護方法は、再生成および比較する段階が初期生成された検証パラメータと再生成された検証パラメータとの間の相違を示すならば、警報を引き起こし、少なくとも秘密鍵をスクランブルする段階を含む。]
[0037] 一実施形態によれば、保護パラメータおよび/または検証パラメータの生成を生成する段階は、
−生成関数を定める段階を含み、生成関数は、予め決定され、メモリに記憶された少なくとも１つの秘密パラメータに、当該秘密パラメータおよび当該関数からのみ決定できる値の列を連続して適用することによって定められ、
− 当該列の少なくとも１つの値から再現可能なやり方で保護パラメータおよび/または検証パラメータを生成する段階をさらに含む。]
[0038] 一実施形態によれば、この防護方法は、
− 複数の関数を定める段階を含み、各関数は、予め決定され、メモリに記憶された少なくとも１つの対応する秘密パラメータに、対応する秘密パラメータおよび対応する関数からのみ決定できる、対応する値の列を連続して適用することによって生成され、
− 予め定められた関係を使用して生成された値の複数の列を組み合わせて新たな値の列を生成する段階と、
− 当該列の少なくとも１つの値から再現可能なやり方で保護パラメータおよび/または検証パラメータを生成する段階と、
をさらに含む。]
[0039] 一実施形態によれば、この防護方法は、
−生成関数を定める段階を含み、生成関数は、予め決定され、メモリに記憶された少なくとも１つの秘密パラメータに、当該秘密パラメータおよび当該生成関数からのみ決定できる値の列を連続して適用することによって定められ、
− 生成された値の列を暗号アルゴリズムの公開パラメータと組み合わせることによって、新たな値の列を生成する段階と、
− この列の少なくとも１つの値から再現可能なやり方で保護パラメータおよび/または検証パラメータを生成する段階と、
をさらに含む。]
[0040] 本発明の別な実施形態は、非対称秘密鍵暗号アルゴリズムの防護方法を実現するマイクロプロセッサと、秘密鍵を記憶する少なくとも１つの安全なメモリと、保護パラメータを生成するデータ生成器とを備えるマイクロ回路デバイスであって、
− 暗号アルゴリズムの基本関数を使用して入力データおよび保護パラメータから中間データを計算し、
− 秘密鍵の２進表現をいくつかのバイナリブロックに分割し、
− 保護パラメータを使用して各バイナリブロックを変換し、変換された各バイナリブロックについて基本関数を使用して中間計算を実行し、
− 中間データを中間計算の結果と組み合わせることによって出力データを計算するように構成されたマイクロ回路デバイスを設けることを含む。]
[0041] 一実施形態によれば、マイクロプロセッサは、各バイナリブロックの値が保護パラメータの値より大きいように、各バイナリブロックの大きさを、反復してランダムに決定するように構成される。]
[0042] 一実施形態によれば、データ生成器は、nが秘密鍵の２進表現の大きさであり、n=k・uである整数u≧2が存在するように、保護パラメータの２進表現の大きさkを選択するように構成され、
マイクロプロセッサは、秘密鍵の２進表現をそれぞれkビットのu個のバイナリブロックに分割するように構成される。]
[0043] 一実施形態によれば、この基本関数は、RSAまたはRSA CRT型の暗号アルゴリズムを実行するための秘密鍵による入力データのべき乗剰余である。]
[0044] 一実施形態によれば、この基本関数は、楕円曲線に基づく暗号アルゴリズムを実行するための秘密鍵による入力データのスカラ乗算であり、
入力データは、楕円曲線の予め決定された点である。]
[0045] 一実施形態によれば、このマイクロ回路デバイスは、再現可能なやり方で、基本関数の実行前に少なくとも１つの検証パラメータを初期生成し、基本関数の実行中または実行後に検証パラメータを再生成し、再生成された検証パラメータを初期生成された検証パラメータと比較するようにさらに構成される。]
[0046] 一実施形態によれば、このデータ生成器は、
−生成関数を定め、生成関数は、予め決定され、メモリに記憶された少なくとも１つの秘密パラメータに、当該秘密パラメータおよび当該関数からのみ決定できる値の列を連続して適用することによって定められ、
− 当該列の少なくとも１つの値から再現可能なやり方で保護パラメータおよび/または検証パラメータを生成する
ことによって保護パラメータおよび/または検証パラメータを生成するように構成される。]
[0047] 一実施形態によれば、このデータ生成器は、
− 複数の関数を定め、各関数は、予め決定され、メモリに記憶された少なくとも１つの対応する秘密パラメータに、対応する秘密パラメータおよび対応する関数からのみ決定できる、対応する値の列を連続して適用することによって生成され、
− 予め定められた関係を使用して生成された複数の値の列を組み合わせて新たな値の列を生成し、
− 当該列の少なくとも１つの値から再現可能なやり方で保護パラメータおよび/または検証パラメータを生成する
ように構成される。]
[0048] 一実施形態によれば、このデータ生成器は、
−生成関数を定め、当該生成関数は、予め決定され、メモリに記憶された少なくとも１つの秘密パラメータに、当該秘密パラメータおよび当該生成関数からのみ決定できる値の列を連続して適用することによって定められ、
− 生成された値の列を暗号アルゴリズムの公開パラメータと組み合わせて新たな値の列を生成し、
− 当該列の少なくとも１つの値から再現可能なやり方で保護パラメータおよび/または検証パラメータを生成する
ように構成される。]
[0049] 本発明の別の実施形態は、前述のようなマイクロ回路デバイスを備えるポータブルデバイス、特にチップカードを与えることを含む。]
[0050] 本発明のこれらおよび他の目的、利点および特徴を、添付図面に関して以下の詳細な説明の中でより詳細に開示するが、本発明のこれらおよび他の目的、利点および特徴は、その添付図面に限定されるものではない。]
図面の簡単な説明

[0051] 前述の、従来型のマイクロ回路デバイスの構造の概略図である。
本発明の第１の実施形態によるマイクロ回路デバイスの構造の概略図である。
図２のデバイスを備えるチップカードの概略図である。
図２のデバイスによって実現される第１の防護方法の連続するステップを示す図である。
図２のデバイスによって実現される第２の防護方法の連続するステップを示す図である。
図２のデバイスによって実現される第３の防護方法の連続するステップを示す図である。
図２のデバイスによって実現される第４の防護方法の連続するステップを示す図である。
図２のデバイスによって実現される第５の防護方法の連続するステップを示す図である。
本発明の第２の実施形態によるマイクロ回路デバイスの構造の概略図である。
図９のデバイスによって実現される防護方法の連続するステップを示す図である。] 図２ 図９
実施例

[0052] ［本発明の第１の実施形態］
図２に示すマイクロ回路デバイス12'は、図１に示したもののように、非対称暗号アルゴリズムのアプリケーション10と、アプリケーション10によって使用されるためのものである具体的には秘密鍵dを記憶する安全なメモリ空間16を含むメモリ14と、マイクロプロセッサ18と、保護パラメータaを与える疑似ランダムデータ生成器20とを備える。マイクロ回路デバイス12'は、防護セクション22'も含み、防護セクション22'により、既存の防護、具体的には前述の防護セクション22に改善がもたらされる。] 図１ 図２
[0053] 加えて、デバイス12'は、例えば、図３に示すように、具体的には安全なチップカード30の形態でポータブルデバイスに組み入れられる。] 図３
[0054] 暗号アルゴリズムのアプリケーション10および防護セクション22'は、別個のように示されているが、暗号アルゴリズムのアプリケーション10および防護セクション22'は、実際には、防護を含む非対称暗号アルゴリズムの同じハードウェアまたはソフトウェアの実装の中に組み込まれていてもよいことに留意されたい。]
[0055] デバイス12とは違って、デバイス12'では、防護セクション22'は、
−秘密鍵dの２進表現を、例えば、大きさの和が秘密鍵の２進表現の大きさに等しいいくつかのバイナリブロックDu-1, ...,D0に分割するセクション22'aを備え、したがって、秘密鍵dの２進表現がdbin=[Du-1, ..., D0]2と書かれることが可能であり、
−保護パラメータaを使用して各バイナリブロックDiを変換し、変換された各バイナリブロックD'iについて基本関数を使用して中間計算を行うセクション22'bをさらに備える。]
[0056] より正確には、生成器20は、高々、秘密鍵dの２進表現の大きさの半分に等しい２進表現の大きさを有する保護パラメータaを生成するように設計されてもよい。同様に、セクション22'aは、各バイナリブロックの大きさが、保護パラメータの２進表現の大きさ以上であるように秘密鍵の２進表現を分割するように設計されてもよい。次いで、非対称暗号アルゴリズムのアプリケーション10は、dbinの大きさの半分を超えない大きさを有するデータを使用して基本関数を実行する。計算時間の利益は、大変十分なものである。]
[0057] 本発明に従う種々の防護方法が、図２のデバイスによって実現することができる。] 図２
[0058] メッセージMについて剰余NのRSA型の暗号を実現するこのタイプの第１の方法を図４に示す。従来、アルゴリズムRSAは、例えばn=1024ビットに等しい２進表現の大きさnを有する秘密鍵dを使用することを必要としている。diが、この２進表現のビットである場合、dbin=[dn-1, ..., d0]2である。] 図４
[0059] S=Exp(M,D,N,S)を以下の基本関数とすると、
j-1から0まで変化するiについて、
S←S2 mod N
Di=1の場合、S←S・M mod N
値Sを出力する
であり、ここで、MおよびSはそれぞれ、基本関数の入力データおよび出力データであり、NはRSAの剰余であり、Dは、D=[Dj-1, ...,D0]2などの大きさjの２進指数であり、ただし、DiはDの２進値である。]
[0060] 第１のステップ100の間に、疑似ランダムデータ生成器20は、nより十分に小さい２進表現の大きさk、例えばk=32ビットを有する保護パラメータaを生成する。]
[0061] 第２の任意選択のステップ102の間に、検証パラメータr1が、生成される。この検証パラメータr1は、例えば、所定の関数COMBを適用することによって、特に、生成器20によって生成されメモリに保持される値v、保護パラメータa、およびアルゴリズムRSAの他のパラメータを組み合わせることによって決定される。]
[0062] 同じ任意選択のステップ102の間に、メッセージMおよびRSAの剰余Nは、関数gおよびhを使用して、
N←h(N)、次いで、
M←g(M) mod N
に変換することもでき、ここでgおよびhは、例えば、g(x)=x+r2・Nおよびh(x)=r3・x、またはg(x)=r2・xおよびh(x)=xによって定められる関数であり、式中r2およびr3は、生成器20によって生成されメモリに保持されるランダム変数であり得る。]
[0063] 次いで、べき乗ステップ104の間に、データVが1に設定され、以下の計算、すなわち、
V=Exp(M,a,N,V)
が行われ、ここでVは、入力データMおよび保護パラメータaに基づく基本関数のExpを使用して計算した中間データを表す。]
[0064] リセットステップ106の間に、出力データSが1に設定され、カウンタiはn-1に設定される。]
[0065] 次いで、テストステップ108の間にカウンタの値iがテストされる。この値が狭義の正である場合、ステップ110が行われ、そうでなければ、任意選択のステップ120、続いて最終ステップ122が行われ、または直接に最終ステップ122が行われる。]
[0066] ステップ110の間に、整数jが、例えばランダムに決定され、そこでは、以下の条件、すなわち、
(a) k≦j(b) di・2j + di-1・2j-1 + ... + di-j・20 > a
を検証する。]
[0067] 加えて、jが、i-jカウンタの値iは、jに割り当てられる。]
[0068] 次いで、ステップ112の間に、値D = di・2j + di-1・2j-1 + ... + di-j・20 - aが計算される。この値Dは、aによって変換された秘密鍵dのバイナリブロックを表す。次いで、ステップ114の間に、バイナリブロックDを使用して以下の中間計算、すなわち、
S=Exp(M,D,N,S)
が行われる。]
[0069] 次いで、ステップ116の間に、中間値Vは、以下のように、すなわち、
S←S・V mod N
であるステップ114で得られる値Sと組み合わされる。]
[0070] 次いで、ステップ118の間に、値i-jが、カウンタiに割り当てられる。次いで、テストステップ108に戻る。]
[0071] カウンタの値iがゼロに等しいとき、かつ任意選択のステップ102が行われているならば、任意選択であるステップ120が、ステップ108に続く。ステップ120の間に、パラメータr1は、関数COMB、およびこの関数によって使用される、公開の、および/または、メモリに保持された値を使用して再び計算される。r1の値が、ステップ102とステップ120の間で変わる場合、２つのステップの間に故障注入による攻撃が発生したと結論付けることができる。暗号アプリケーション10によって警報が送られる。また、ステップ120の間に、出力データSは、入力データMをマスクするために使用された関数gおよびhによってアンマスク(unmask)される。暗号アプリケーション10によって送られた警報に従って、故障を用いて行われる逆変換(アンマスキング)により、故障注入による攻撃を阻止することが可能である。]
[0072] 最終的に、最後のステップ122の間に、暗号アプリケーション10は、値Sを出力する。]
[0073] 上記の第１の方法は、n+k回のべき乗の反復、すなわち、ステップ104の間にk回の反復、およびステップ108〜118のループ内のn回の反復を伴うことに留意されたい。kがnよりとても小さいとき(例えば、n=1024に対してk=32のとき)、アルゴリズムRSAに関する防護の追加コストは、とても少ない。ともかく、この追加コストは、少なくとも2n回のべき乗の反復を伴う現状の技術の解決策のものよりずっと少ない。]
[0074] 図２のデバイスによって実現することができ、また、メッセージMについて剰余NのRSA型の暗号を実現する本発明による第２の防護方法を図５によって示す。第２の防護方法は、第１の方法の変形形態であり、保護パラメータaの大きさkは、n=k・uのような整数uが存在し、値j(ステップ110)が、kで固定され、条件(b)が課されないように選ばれる。したがって、この防護方法は、簡単化される。] 図２ 図５
[0075] 第２の方法のステップ200、202(任意選択)、204は、前述のステップ100、102(任意選択)、104と同一である。]
[0076] 次いで、リセットステップ206の間に、出力データSが1に設定され、カウンタiがu-1に設定される。同じステップの間に、秘密鍵dの２進表現は、dbin=[Du-1, ...,D0]2などの、それぞれの大きさがkであるu個の連続するブロックDiに分割される。任意のi、0≦i２進桁上げ数(binary carry digits) C=[Cu-1, ..., C0]2のベクトルCが計算され、メモリに保持される。ベクトルCは、帰納法によって以下のように、すなわち、
− C0=0、
−Ci=(Di-a-Ci-1)/2k
によって計算される。]
[0077] 次いで、テストステップ208の間に、カウンタの値iがテストされる。この値が、狭義の正である場合、ステップ210が行われ、そうでなければ、任意選択のステップ218、続いて最終ステップ220が行われ、または直接に最終ステップ220が行われる。]
[0078] ステップ210の間に、値D'i=Di-a-Ciが計算される。アルゴリズムの良好な動作のために、i=u-1の場合およびCu-1=1の場合には、D'iは、aより小さく、その場合、D'i=Diが維持されることを意味する。この値D'iは、aによって変換された秘密鍵dのi番目バイナリブロックを表す。第２の方法の注目の１つは、ベクトルを記憶することだけを必要とし、変換されたブロックD'iを記憶することを必要としないことであることに留意されたい。]
[0079] 次いで、ステップ212の間に、バイナリブロックD'iを使用して以下の中間計算、すなわち、
S=Exp(M,D'i,N,S)
が行われる。]
[0080] 次いで、ステップ214の間に、中間値Vは、以下のように、すなわち
S←S・V mod N
であるステップ212で得られる値Sと組み合わされる。]
[0081] 次いで、ステップ216の間に、値i-jが、カウンタiに割り当てられる。次いで、テストステップ208に戻る。]
[0082] ステップ218およびステップ220は、前述のステップ120およびステップ122と同一である。]
[0083] 上記の第２の方法は、n+k回のべき乗の反復を伴うことにも留意されたい。]
[0084] 図２のデバイスによって実現することができ、メッセージMの剰余N=p・qのRSA CRT型(すなわち、中国の剰余定理を用いるRSAアルゴリズム)の暗号を実現する本発明による第３の防護方法を図６によって示す。従来から、アルゴリズムRSA CRTは、署名または暗号解読を行うためのアルゴリズムRSAに代わるものを構成しており、アルゴリズムRSA CRTは４倍速い。それは、以下のパラメータ、すなわち、
− dp=d mod (p-1)、
− dq=d mod (q-1)、
− A=p-1 mod q
を定める。] 図２ 図６
[0085] この場合、第３の防護方法は、Nの大きさに比べてpおよびqの大きさのため、Sp=Mdp mod pおよびSq=Mdq mod qの計算実行がずっと簡単な２つのべき乗の計算によってべき乗の計算S=Md mod Nを置き換えることを含む。最終的に、Sは、以下の式、すなわち、
S=[((Sq-Sp)・A mod q)・p+Sp] mod N
を使用して見出される。]
[0086] 第３の方法のステップ300、302(任意選択)は、前述のステップ100および200、102および202(任意選択)と同一である。]
[0087] 次いで、べき乗ステップ304の間に、データVpは1に設定され、以下の計算、すなわち、
Vp=Exp(M,a,p,Vp)
が行われ、ここでVpは、入力データMおよび保護パラメータaに基づく基本関数のExpを使用して計算した中間データを表す。]
[0088] ステップ304の後、一連のループのステップを含み、指数dpによるdの置き換え、および剰余pによるNの置き換えを除いてすでに説明したステップ106〜118、または206〜216に対応するステップ306の間に、計算Sp=Mdp mod pが行われる。]
[0089] べき乗ステップ308の間に、データVqは1に設定され、以下の計算、すなわち、
Vq=Exp(M,a,q,Vq)
が行われ、ここでVqは、入力データMおよび保護パラメータaに基づく基本関数のExpを使用して計算した中間データを表す。]
[0090] ステップ308の後、一連のループのステップを含み、指数dpによるdの置き換え、および剰余qによるNの置き換えを除いてすでに説明したステップ106〜118、またはステップ206〜216に対応するステップ310の間に、計算Sp=Mdp mod pが行われる。]
[0091] ステップ304〜310を実行する順序は固定されない。実際には、重要なことは、ステップ302の後にステップ304〜310が実行され、ステップ304は、ステップ306の前に実行され、ステップ308は、ステップ310の前に実行されることだけである。ループの出力、すなわちステップ306および310の終わりでは、任意選択のステップ312、続いて最終ステップ314が行われ、または直接に最終ステップ314が行われる。]
[0092] 任意選択のステップ312は、ステップ120と同一であり、任意選択のステップ302が実行された場合にのみ行われる。]
[0093] 最終ステップ314の間に、暗号アルゴリズム10は、前もって示されたSpおよびSqに基づいてSの値を計算し、この値を出力する。]
[0094] 次に、図２のデバイスによって実現することができ、メッセージMの楕円曲線型の暗号を実現する本発明に従う第４の防護方法を、図７を参照して示すことにする。従来、ECC(楕円曲線暗号系)とも呼ばれる非対称楕円曲線暗号アルゴリズムは、同等のセキュリティレベルのためにアルゴリズムRSAに必要な大きさより十分に小さい大きさnを有する秘密鍵dの使用を必要とする。一般に、秘密鍵dの２進表現は、n=160ビットに少なくとも等しいものでなければならない。] 図２ 図７
[0095] 署名または暗号解読を行うために秘密鍵dを用いるアルゴリズムECCでは、「基本関数を実行すること」は、以下のように、入力データPおよび秘密鍵dに基づいて出力データQを計算することを含み、すなわち、
Q=d・Pであり、ここでPおよびQは、有限体GF(p)上の所定の楕円曲線の点であり、式中pは、3を厳密に上回る素数であり(例えば、体GF(13)内の楕円曲線y2=x3+10x+5であり)、および式中、演算「・」は、ここでは点Pにスカラdを乗じるスカラ乗算である。]
[0096] [dn-1, ..., d0]2を秘密鍵dの２進表現とすると、この計算は、以下のように行うことができ、すなわち、
Q=0
n-1から0まで変化するiについて、
Q←2Q
di=1の場合、Q←Q+P
であり、ここで、「2Q」および「Q+P」はそれぞれ、点を2倍する演算および点を加算する演算であり、それらの公式は、選択した楕円曲線および体GF(p)の次数によって従来から求められており、本明細書では詳述しない。]
[0097] 以下の説明では、S=ScalarMult(P,D,Q)は、以下の基本関数、すなわち、
j-1から0まで変化するiについて
Q←2Q
Di=1の場合、Q←Q+P
値Qを出力する
ことを示しており、
ここで、PおよびQはそれぞれ、基本関数の入力データおよび出力データであり、Dは、D=[Dj-1, ...,D0]2などの大きさjの２進指数であり、ただし、Diは、Dの２進値である。]
[0098] 第１のステップ400の間に、疑似ランダムデータ生成器20は、nより十分に小さい２進表現の大きさk、例えばk=32ビットを有する保護パラメータaを生成する。]
[0099] 第２の任意選択のステップ402の間に、検証パラメータrが生成される。検証パラメータrは、例えば、所定の関数COMBを適用することによって、特に、生成器20によって生成されメモリに保持される値v、保護パラメータa、およびアルゴリズムECCの他のパラメータを組み合わせることによって決定される。]
[0100] この同じ任意選択のステップ402の間に、点Pの座標PxおよびPyを、座標に適用する関数gを用いて、すなわち、P←g(Px, Py) mod Nを用いて変換することもできる。]
[0101] 次いで、ステップ404の間に、データVは0に設定され、以下の計算、すなわち、
V=ScalarMult(P,a,V)
が行われ、ここでVは、入力データPおよび保護パラメータaに基づく基本関数ScalarMultを使用して計算した中間データを表す。]
[0102] リセットステップ406の間に、出力データQが0に設定され、カウンタiがn-1に設定される。]
[0103] 次いで、テストステップ408の間に、カウンタの値iがテストされる。この値が、狭義の正である場合、ステップ410が行われ、そうでなければ、任意選択のステップ420、続いて最終ステップ422が行われ、または直接に最終ステップ422が行われる。]
[0104] ステップ410の間に、整数jが、例えばランダムに決定され、それにより以下の条件、すなわち、
(a) k≦j < i、および
(b) di・2j + di-1・2j-1 + ... + di-j・20 > a
を検証する。]
[0105] 加えて、jが、i-jカウンタの値iはjに割り当てられる。]
[0106] 次いで、ステップ412の間に、値D = di・2j + di-1・2j-1 + ... + di-j・20 - aが計算される。この値Dは、aによって変換された秘密鍵dのバイナリブロックを表す。次いで、ステップ414の間に、バイナリブロックDを使用して以下の中間計算、すなわち、
Q=ScalarMult(P,D,Q)
が行われる。]
[0107] 次いで、ステップ416の間に、中間値Vは、以下のように、すなわち、
Q←Q+V
であるステップ414で得られる値Qと組み合わさる。]
[0108] 次いで、ステップ418の間に、値i-jがカウンタiに割り当てられる。次いで、テストステップ408に戻る。]
[0109] カウンタの値iがゼロに等しいとき、かつ任意選択のステップ402が行われているならば、任意選択であるステップ420が、ステップ408に続く。ステップ420の間に、パラメータrは、関数COMB、およびこの関数によって使用される、公開の、および/または、メモリに保持された値を使用して再び計算される。rの値が、ステップ402とステップ420の間で変わる場合、２つのステップの間に故障注入による攻撃が発生したと結論付けることができる。次いで、暗号アプリケーション10によって警報が送られる。また、ステップ420の間に、出力データQは、入力データPをマスクするために使用された関数gによってアンマスクされる。暗号アプリケーション10によって送られた警報に従って、故障を用いて行われる逆変換(アンマスキング)により、故障注入による攻撃を阻止することが可能である。]
[0110] 最終的に、最後のステップ422の間に、暗号アプリケーション10は、値Qを出力する。]
[0111] 上記の第４の方法は、n+k回のスカラ乗算の反復、すなわち、ステップ404の間にk回の反復、およびステップ408〜418のループ内のn回の反復を伴うことにも留意されたい。kがnよりとても小さいとき(例えば、n=160以上に対してk=32のとき)、アルゴリズムECCに関する防護の追加コストは、とても少ない。ともかく、追加コストは、少なくとも2n回のスカラ乗算の反復を伴う現状の技術の解決策のものよりずっと少ない。]
[0112] 代替として、ステップ404の間に、データVは0にリセットされ、以下の計算、すなわち、V=ScalarMult(-P,a,V)が行われる。この場合、ステップ412の間に、D = di・2j + di-1・2j-1 + ... + di-j・20 + aの値が計算される。このことは、aによる秘密鍵dの別の可能性のある変換を構成する。]
[0113] 図２のデバイスによって実現することができ、また、楕円曲線暗号を実現する本発明による第５の防護方法を図８によって示す。第５の防護方法は、第４の方法の変形形態であり、保護パラメータaの大きさkは、n=k・uのような整数uが存在し、jの値(ステップ410)がkで固定され、条件(b)が課されないように選ばれる。したがって、この防護方法は、簡単化される。] 図２ 図８
[0114] 第５の方法のステップ500、502(任意選択)、504は、前述のステップ400、402(任意選択)、404と同一である。]
[0115] 次いで、リセットステップ506の間に、出力データQが0に設定され、カウンタiがu-1に設定される。同じステップの間に、秘密鍵dの２進表現は、dbin=[Du-1, ...,D0]2などの、それぞれの大きさがkであるu個の連続するブロックDiに分割される。任意のi、0≦i２進桁上げ数C=[Cu-1, ..., C0]2のベクトルCが計算され、メモリに保持される。ベクトルCは、帰納法によって以下のように、すなわち、
− C0=0、
−Ci=(Di-a-Ci-1)/2k
によって計算される。]
[0116] 次いで、テストステップ508の間に、カウンタの値iがテストされる。この値が、狭義の正である場合、ステップ510が行われ、そうでなければ、任意選択のステップ518、続いて最終ステップ520が行われ、または直接に最終ステップ520が行われる。]
[0117] ステップ510の間に、値D'i=Di-a-Ciが計算される。アルゴリズムの良好な動作のために、i=u-1の場合およびCu-1=1の場合は、D'iはaより小さく、その場合、D'i=Diが維持されることを意味する。この値D'iはaによって変換された秘密鍵dのi番目バイナリブロックを表す。第２の方法の注目の１つは、２進桁上げ数Cのベクトルを記憶することだけを必要とし、変換されたブロックD'iを記憶することを必要としないことであることに留意されたい。]
[0118] 次いで、ステップ512の間に、バイナリブロックD'iを使用して以下の中間計算、すなわち、
Q=ScalarMult(P,D'i,Q)
が行われる。]
[0119] 次いで、ステップ514の間に、中間値Vは、以下のように、すなわち、
Q←Q+V
であるステップ512で得られる値Qと組み合わされる。]
[0120] 次いで、ステップ516の間に、値i-1がカウンタiに割り当てられる。次いで、テストステップ508に戻る。]
[0121] ステップ518およびステップ520は、前述のステップ420およびステップ422と同一である。]
[0122] 上記の第２の方法は、n+k回のスカラ乗算の反復を伴うことにも留意されたい。]
[0123] 第４の方法に関しては、代替として、ステップ504の間に、データVは0に設定され、以下の計算、すなわち、V=ScalarMult(-P,a,V)が行われる。この場合、ステップ506の間に、２進桁上げ数のベクトルの計算は、以下のように、すなわち、
− C0=0、
−Ci=(Di+a+Ci-1)/2k
のように修正される。]
[0124] この場合、ステップ510の間に、値D'i=Di+a+Ciが計算される。このことは、aによる秘密鍵dの別の可能性のある変換を構成する。]
[0125] ［本発明の第２の実施形態］
図９に示すマイクロ回路デバイス12''は、図２に示したもののように、暗号アルゴリズムのアプリケーション10と、安全なメモリ空間16を含むメモリ14と、マイクロプロセッサ18と、防護セクション22'とを備える。このデバイスは、例えば、図３に示すように、具体的には安全なチップカード30の形態でポータブルデバイスに組み込まれる。しかし、暗号アルゴリズムのアプリケーション10および防護セクション22'は、別個のように示されているが、実際には暗号アルゴリズムのアプリケーションおよび防護セクション22'は、防護を含む暗号アルゴリズムの同じ実装の中に組み込まれていてもよいことに留意されたい。] 図２ 図３ 図９
[0126] デバイス12''の防護セクション22'は、デバイス12'のもののように、
−秘密鍵dの２進表現を、例えば、大きさの和が秘密鍵の２進表現の大きさに等しいいくつかのバイナリブロックDu-1, ...,D0に分割するセクション22'aと、
−保護パラメータaを使用して各バイナリブロックDiを変換し、変換されたバイナリブロックD'iごとに、基本関数を使用して中間計算を行うセクション22'bと
を含む。]
[0127] デバイス12'とは違って、デバイス12''では、従来型の疑似ランダムデータ生成器20は、データ生成器20''によって置き換えられており、データ生成器20''は、
−秘密パラメータおよび関数Fからのみ決定できる値の列を生成するために、予め定義された関数Fを少なくとも１つの予め決定された秘密パラメータSに適用するセクション20''aと、
− この列の値から再現可能なやり方で少なくとも１つの保護パラメータaを与えるセクション20''bと
を含む。]
[0128] 実際には、セクション20''aは、関数Fのソフトウェアまたはハードウェアの実装である。]
[0129] 秘密パラメータSは、安全なメモリ16に記憶され、生成器20''のセクション20''aの入力において与えられるのに対して、保護パラメータaは、セクション20''bの出力において防護セクション22'へ与えられる。]
[0130] したがって、第２の実施形態では、パラメータaは、現状の技術の文献に述べられた従来の意味のランダム変数でない。パラメータaは、マイクロ回路12'が配置されるチップカード30に固有であり得る少なくとも１つの秘密パラメータSに基づいて生成器20''によって実行される関数の計算から生じる決定論的な結果である。例えば、秘密パラメータは、デバイス30の公開データから得られる。]
[0131] 関数FをSに繰り返し適用することにより、要素が生成器によって与えられる保護パラメータの源である列(An)を生成する。全体的に、生成器は、カード30において実現される防護アプリケーションにより必要にされるのと同じくらい多くの、列(An)の値からもたらされるパラメータを与えることができる。この列(An)は、生成関数Fおよびその関数が使用する最初の決定論的な要素(パラメータS)が分かるときのみ、再現することができる。]
[0132] 各保護パラメータaは、列(An)の要素Anから直接もたらされ得るものであり、言い換えれば、a=Anである。代替として、要素Anは、パラメータaを与える前に処理を受けてもよい。例えば、aは計算a=An XOR knの結果であり得るものであり、ここでknは秘密の変換定数である。]
[0133] 明らかに、列(An)が要素の有限集合内において巡回的である、かつ/または、動く場合、生成される値Anの空間は、攻撃に耐えるのに十分大きいものでなければならない。実際には、空間がより大きく考えられるほど、防護はより信頼できるものになる。]
[0134] まず、本発明の第２の実施形態による生成器20''によって与えられ得る、値の列(An)のいくつかの限定しない例を示すことにする。次いで、具体的には図４〜図８を参照して前述した５つの非対称暗号防護の適用例に保護パラメータを与えるために、そのような値の列のいくつかの可能性のある使用を開示する。] 図４ 図５ 図６ 図７ 図８
[0135] 保護パラメータを与えるための値の列を生成する関数の例]
[0136] 1)等差等比数列に基づいた関数]
[0137] 値の列(An)が、式中qおよびrは列の最初の要素A0とともに前述の秘密パラメータSを構成する秘密パラメータである、以下の関係、すなわち、
An+1=F(An)=q・An+r
による整数値関数Fを使用して定められる場合、等差等比数列からもたらされる保護パラメータを与えることができる。例えば、これらの保護パラメータは、列(An)の要素である。]
[0138] r=0の場合、列(An)は、等比数列であり、暗号の詳細なステップで使用される列(An)の等比数列の項Aiは、秘密パラメータqおよびA0を使用して次のように見出すことができ、すなわち、Ai=qi・A0である。]
[0139] q=1の場合、列(An)は等差数列であり、列(An)の項Aiは秘密パラメータrおよびA0を使用して次のように見出すことができ、すなわち、Ai=r・i+A0である。]
[0140] rがゼロに等しくなく、qが1と異なる場合、列(An)は等差等比数列であり、列(An)の項Aiは秘密パラメータq、rおよびA0を使用して次のように見出すことができ、すなわち、
Ai=qi・A0+r・(qi-1)/(q-1)
である。]
[0141] 列(An)の要素の空間は、以下の関係式、すなわち、
An+1=F(An) modulo m=(q・An+r) modulo m
を使用して、整数mによって変形することもできる。]
[0142] mが素数である場合、この列は、有限体GF(m)={0,1, ..., m-1}上で正則アフィン変換群の形をとることに気づくことができよう。]
[0143] mは、複数ビットの定数で要素の列を生成するように２のべき乗として選ぶこともできる。例えば、kビットでパラメータAiの列を生成することが望まれる場合、m=2kが、選ばれる。]
[0144] 好ましくは、mは、デバイスの安全なメモリに保持される秘密パラメータの一部である。]
[0145] 2)巡回乗法群(cyclic multiplicative group)を定める関数]
[0146] GCをm個の要素を有する巡回群とし、値aを生成元とし、および乗法を内部構成規則として、すなわちGC={a,a2, ..., am}とする。値の列(An)は、以下のように定めることができ、すなわち、
− 最初の要素A0は、群GCの内部構成規則がk回適用される生成元aであるように選ばれる。
− 群GCの内部構成規則は、要素Aiから要素Ai+1になるのにk'回適用される。]
[0147] このとき、列(An)を生成するこの関数によって使用される秘密パラメータSは、例えば、生成元a、値k、k'およびmである。加えて、前述のように、生成される保護パラメータは、例えば列(An)の要素である。]
[0148] 3)フロベニウス群を定める関数]
[0149] GF(q)を、次数qが、kビットの素数である有限体とする。この有限体上の正則アフィン変換群は、フロベニウス群である。フロベニウス群の興味深い特性は、非自明な要素は２つ以上の点を固定しないことである。]
[0150] この文脈において、使用できるアフィン変換は、関数y=f(x)=b・x+cの形をとり、ただしb≠0であり、演算は、体GF(q)内で行われる。したがって、所定の秘密パラメータq、b、cおよびA0に適用する列(An)を生成する関数を定めることができる。例えば、q=216+1、１６進表記でb=0x4cd3、c=0x76bb、A0=0xef34を選ぶことによって、項A1=0xc6cf、A2=0x8baf、A3=0x620d、A4=0x0605、A5=0xe70c、A6=0x3049、A7=0xe069、A8=0x55eeなどから始まる数列が得られる。]
[0151] 4)線形フィードバックのシフトレジスタ(LFSR型のレジスタ)からもたらされる関数]
[0152] このタイプの関数は、例えば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をとる。]
[0153] 5)巡回冗長検査(CRC:Cyclic Redundancy Check)の計算を定める関数]
[0154] このタイプの関数は、例えば16ビットの秘密パラメータA0、および従来からCRCの計算で使用されているものの中で対応する多項式のCRC、例えば多項式CRC-16 (X16+X15+X2+1)または多項式CRCCCITTV41 (X16+X12+X5+1)を選ぶ。列(An)の項An+1は、関係An+1=F(An)によって前の項Anに従って決定され、ここでFは、選ばれた多項式に基づいたCRCの計算を行うものである。]
[0155] 6)値の列の組み合わせ]
[0156] 例えば、それぞれが、本明細書で詳述した方法のうちの１つによる、いくつかの値の列を計算し、次いで予め定められた関数を使用して保護パラメータとして使用される新たな値の列を生成することも実際にできる。このようにして、列(An)は、各添え字nごとにAn=T(A'n,A''n)を計算することによって２つの他の列(A'n)および(A''n)に従って生成される。]
[0157] 関係している関数Tは、秘密の値の行列であってもよく、このとき、値A'nおよびA''nはそれぞれ、この行列の行と列を示す。]
[0158] 7)値の列および公開データを伴う組み合わせ]
[0159] 列(An)は、第１の列(A'n)から、さらに防護を用いた、秘密でない、例えば暗号アプリケーションの実行中に使用されるデータのような、公開データに従って生成されてよい。これらのデータの中で、この適用例により、(平文の、または、符号化された)メッセージM、公開鍵eなどを挙げることができる。次いで、保護パラメータとして使用される列の値が、これらのデータ全てを組み合わせる任意の関数COMB、すなわち、
An=COMB(A'n,M,e, ...)
を用いて計算される。]
[0160] この組み合わせの利点は、値の列(An)を使用して、保護パラメータを暗号アルゴリズムの防護アプリケーションに供給するだけでなく、(具体的には公開データで)故障注入による攻撃を検出できることである。実際には、例えば、暗号アルゴリズムの実行の終わり、しかし再生成された保護パラメータを使用して最初の変換の逆演算を行う前に、秘密パラメータを使用して列(A'n)を再生成し、次いで、実行の終わりに現れるようなこの再生成された列(A'n)および公開データを使用することによって、関数COMBのアプリケーションが、同じ値の列(An)を生成しているかどうか、したがって公開データが、実行中に影響を受けたか検査することができる。]
[0161] 本発明の第２の実施形態による非対称暗号の防護方法における前述の方法のうちの１つに従って生成される値の列の使用の例]
[0162] 1)第２の実施形態の一般的原理]
[0163] 一般に、疑似ランダムデータ生成器20を使用する第１の実施形態に記載されていたように、アルゴリズムの防護を使用する度に、この防護により導入されるランダム変数を生成することが推奨される。図９を参照して述べるように、ランダム変数の生成は、少なくとも１つの秘密パラメータを使用して得られる１つまたは複数の値の列からもたらされるランダムでないパラメータ生成によって置き換えられてもよい。] 図９
[0164] 図１０は、実行によってT個の保護パラメータa1, ... aTを使用する防護で非対称暗号アルゴリズムの実行に適用される図９の第２の実施形態による方法によって行われるステップの例を示しており、全ての保護パラメータは、セクション20'aにより生成される同じ値の列(An)から得ることができる。] 図１０ 図９
[0165] 生成器20''によって行われる第１のステップINITの間に、カウンタiは0に設定される。カウンタiは、別のリセットが行われない限りリセットステップINIT以後に非対称暗号アルゴリズムが実行された回数をメモリに保持するためのものである。]
[0166] このステップの間に、値の列の生成に必要な秘密パラメータS(または２つ以上あるときにはこれらのパラメータS)が定められる。秘密パラメータSは、リセット前から保持することができるが、リセットのときに新たな値に基づいて生成されてもよい。例えば、秘密パラメータSは、デバイス30の公開データなどの固有の識別データから生成される。秘密パラメータSは、ランダムであってよい所与の時間にマイクロ回路に関連しているパラメータまたは物理現象から生成されてもよい。ともかく、秘密パラメータSは、安全なやり方でメモリに保持されて、マイクロ回路が、セクション20''aによって実現される関数を使用して同じ値の列(An)をいつでも生成することを可能にする。]
[0167] リセットステップINITは、マイクロ回路のライフサイクルにおいて唯一であり得るものであり、設計中には製造者によって行われ、または例えば定期的またはカウンタiが値imaxに到達する度に数回再び引き起こされる。]
[0168] 防護を用いた非対称暗号アルゴリズムの第１の実行EXE1の間に、生成器20''、より具体的にはセクション20''aは、秘密パラメータSを予め定められた関数Fに適用するために1回または複数回要求され、それによって値の列(An)のT個の要素、すなわちA1, ... ATを1回または複数回で生成する。T個の保護パラメータa1, ... aTは、これらT個の第１の要素から生成される。]
[0169] 例えば、1≦k≦T、ak=Akなどの任意のk個についてである。]
[0170] 代替として、安全なメモリに保持される秘密パラメータSの中にT個の追加の秘密の値Sec1, ... SecTがある場合、以下の追加の計算を行うことができ、すなわち、
1≦k≦Tのような任意のkについて、ak=Seck XOR Ak、またはak=Seck ADDAk、またはak=SeckSUBAk,であり、それにより使用されるパラメータを変換する(または歪ませ、もしくはマスクする)。]
[0171] その後、防護を用いた暗号アルゴリズムのi番目の実行EXEiの間に、生成器20''、より具体的にはセクション20''aは、秘密パラメータSを予め定められた関数Fに適用するためにやはり1回または複数回要求され、それによって値の列(An)のT個の追加の要素、すなわち:AT(i-1)+1, ... ATiを1回または複数回で生成する。T個の保護パラメータa1, ... aTは、前のようにこれらT個の追加の要素から生成される。]
[0172] 例えば、1≦k≦T、ak=AT(i-1)+kなどの任意のk個についてである。]
[0173] 代替として、T個の追加の秘密の値Sec1, ... SecTがある場合、以下の追加の計算を行うことができ、すなわち、
1≦k≦Tのような任意のkについて、ak=Seck XOR AT(i-1)+k、またはak=Seck ADDAT(i-1)+k、またはak=SeckSUBAT(i-1)+kであり、それにより使用されるパラメータを変換する(または歪ませ、もしくはマスクする)。]
[0174] 保護パラメータのもとになる値の列を生成するために使用される方法が何であっても、メモリの中に前もってまたはメモリEEPROM中のマイクロ回路デバイスのライフサイクルのあるステップ中にロードされた最初のパラメータA0を含めて、この方法によって使用される方法および秘密の値が分かっていれば、デバイスの耐用期間中に生成および使用された保護パラメータをいつでも見出すことを可能にさせる。そこで、この特色により簡単および効果的なデバッグが行われ、故障注入による攻撃に対する抵抗が向上することを可能にすることが明らかであるように思われる。]
[0175] 値の列および保護パラメータを生成するために使用される方法の選択は、考えられるアプリケーションによって決まる。]
[0176] 2)図４〜図８を参照して説明した5つの方法の第２の実施形態の一般的原理の適用例] 図４ 図５ 図６ 図７ 図８
[0177] ステップ100、200、300の間に保護パラメータa、およびステップ102、202、302の間にパラメータv、r2、r3を生成するために図４、図５、図６の第１の方法、第２の方法、第３の方法によって使用される方法は、第２の実施形態において推奨されるものの１つであり得る。加えて、パラメータa、v、r2、r3は、同じバイナリサイズを有し、同じ値の列(T=4)からもたらされ得る。加えて、これらのパラメータは、秘密パラメータおよび関数Fによって決定される値の列からいつでも見出すことができるので、これらのパラメータは、メモリに保持される必要をなくすことができる。このようにして、パラメータv、および次いでr1、r2およびr3は、べき乗の実行中にメモリに保持されることを必ずしも必要とすることなくステップ120、218、312で見出すことができる。これらのステップ120、218、312において、保護パラメータaは、その完全性が、べき乗中に保持されていたことを検査するために見出されてもよい。] 図４ 図５ 図６
[0178] 同様に、ステップ400、500の間に保護パラメータa、およびステップ402、502の間にパラメータvを生成するために図７、図８の第４の方法、第５の方法によって使用される方法は、第２の実施形態において推奨されるものの１つであり得る。加えて、パラメータaおよびvは、同じバイナリサイズを有し、同じ値の列(T=2)からもたらされ得る。加えて、これらのパラメータは、秘密パラメータおよび関数Fによって決定される値の列からいつでも見出すことができるので、したがって、これらのパラメータは、メモリに保持される必要をなくすことができる。これらのパラメータを再生成することを含むこのプロセスは、故障注入による攻撃に対する実装の保護のための有用なステップでもある。したがって、パラメータvおよび次いでrは、スカラ乗算の実行中にメモリに保持されることを必ずしも必要とすることなくステップ420、518で見出すことができる。これらのステップ420、518において、保護パラメータaは、その完全性、および保護パラメータaを生成するために使用されるパラメータの完全性が、スカラ乗算中に保持されていたことを検査するために見出されてもよい。] 図７ 図８
[0179] 追加の保護が、前述の各方法において、基本関数の計算ループの実行中に加えられてもよい。検証パラメータは、上記の推奨された方法の１つにより前もって生成され、このパラメータは、パラメータa、v、r1、または、a、v、r1、r2、r3に加えられている。この計算ループにおける反復ごとに、例えば第１の方法のステップ118、第２の方法のステップ216、第３の方法のステップ306および310、第４の方法のステップ418、および第５の方法のステップ516で、sが見出され、メッセージMの２進表現または別の基数bによる表現の少なくとも一部の部分が、決定論的なやり方でパラメータを使用して(RSAまたはRSA CRTの場合)剰余N、秘密鍵dなどから得られる。次いで、この部分は、Ms、Ns、dsなどと示され、ことによると組み合わされて、検証データを形成する。この保護の原理は、反復ごとに、検証データの値が変わっていないことを検査することである。検証データが変わる場合、データM、N、dなどは、発見されないためにスクランブルされてもよく、警報が、引き起こされてもよい。M、Nおよびd以外の他のデータが使用されてもよく、ただしこれらのデータは、基本関数の実行中に使用される。]
[0180] 前述の防護方法は、サイドチャネルによる攻撃に対して使用される秘密鍵を保護する非対称暗号アプリケーションを実現し、一方で、計算時間の追加コストを大変適正なレベルで制限することを可能にすることが明らかであるように思われる。]
[0181] 加えて、本発明は、前述の実施形態に限定されず、多数の変形形態が示されたが、説明した変換以外の具体的には秘密鍵の他のタイプの変換、または扱ったもの以外の他の非対称暗号アプリケーションを与える他の形態も考えることができることに留意されたい。]
[0182] 10非対称暗号アルゴリズムのアプリケーション
12マイクロ回路
12'マイクロ回路デバイス
14メモリ
16 安全なメモリ空間
18マイクロプロセッサ
20疑似ランダムデータ生成器
20''データ生成器
20''aセクション
20''b セクション
22防護セクション
22' 防護セクション
22'a セクション
22'b セクション
30チップカード
a保護パラメータ
(An) 列
An 要素
d 秘密鍵]

权利要求:

請求項1
非対称秘密鍵暗号アルゴリズムを実現する電子コンポーネントにおける防護方法であって、保護パラメータを生成する段階と、前記暗号アルゴリズムの基本関数を使用して入力データおよび前記保護パラメータから中間データを計算する段階と、を含み、前記秘密鍵の２進表現をいくつかのバイナリブロックに分割する段階と、前記保護パラメータを使用して各バイナリブロックを変換し、変換された各バイナリブロックについて前記基本関数を使用して中間計算を実行する段階と、前記中間データと前記中間計算の結果とを組み合わせることによって出力データを計算する段階と、をさらに含む、電子コンポーネントにおける防護方法。
請求項2
各バイナリブロックの大きさが前記保護パラメータの２進表現の大きさより大きいか、または、等しいように、前記秘密鍵の２進表現を分割する段階を含む請求項１に記載の電子コンポーネントにおける防護方法。
請求項3
前記バイナリブロックの大きさの和が前記秘密鍵の２進表現の大きさより大きいように、前記秘密鍵の２進表現をいくつかのバイナリブロックに分割する段階を含む請求項１または２に記載の電子コンポーネントにおける防護方法。
請求項4
各バイナリブロックの値が前記保護パラメータの値より大きいように、各バイナリブロックの大きさを、反復してランダムに決定する段階を含む請求項１から３のいずれか一項に記載の電子コンポーネントにおける防護方法。
請求項5
nが前記秘密鍵の２進表現の大きさであり、n=k・uである整数u≧2が存在するように、前記保護パラメータの２進表現の大きさkを選択する段階と、前記秘密鍵の２進表現をそれぞれkビットのu個のバイナリブロックに分割する段階と、を含む請求項１から３のいずれか一項に記載の電子コンポーネントにおける防護方法。
請求項6
前記基本関数は、RSAまたはRSA CRT型の暗号アルゴリズムを実行するための前記秘密鍵による前記入力データのべき乗剰余である請求項１から５のいずれか一項に記載の電子コンポーネントにおける防護方法。
請求項7
RSAの剰余および前記入力データを前もってマスクする段階を含む請求項６に記載の電子コンポーネントにおける防護方法。
請求項8
前記基本関数は、楕円曲線に基づく暗号アルゴリズムを実行するための前記秘密鍵による前記入力データのスカラ乗算であり、前記入力データは、前記楕円曲線の予め決定された点である請求項１から５のいずれか一項に記載の電子コンポーネントにおける防護方法。
請求項9
前記楕円曲線の予め決定された点を前もってマスクする段階を含む請求項８に記載の電子コンポーネントにおける防護方法。
請求項10
再現可能なやり方で、前記基本関数の実行前に少なくとも１つの検証パラメータを初期生成する段階と、前記基本関数の実行中または実行後に前記検証パラメータを再生成し、前記再生成された検証パラメータを前記初期生成された検証パラメータと比較する段階と、をさらに含む請求項１から９のいずれか一項に記載の電子コンポーネントにおける防護方法。
請求項11
前記基本関数が変換されたバイナリブロックに適用されるときに、前記再生成および比較する段階は前記基本関数の反復ごとに実行される請求項１０に記載の電子コンポーネントにおける防護方法。
請求項12
前記再生成および比較する段階が前記初期生成された検証パラメータと前記再生成された検証パラメータとの間の相違を示すならば、警報を引き起こし、少なくとも前記秘密鍵をスクランブルする段階を含む請求項１０または１１に記載の電子コンポーネントにおける防護方法。
請求項13
前記保護パラメータおよび/または前記検証パラメータを生成する段階は、生成関数を定める段階を含み、前記生成関数は、予め決定され、メモリに記憶された少なくとも１つの秘密パラメータに、前記秘密パラメータおよび前記関数からのみ決定できる値の列を連続して適用することによって定められ、前記列の少なくとも１つの値から再現可能なやり方で前記保護パラメータおよび/または前記検証パラメータを生成する段階をさらに含む請求項１から１２のいずれか一項に記載の電子コンポーネントにおける防護方法。
請求項14
複数の関数を定める段階を含み、各関数は、予め決定され、メモリに記憶された少なくとも１つの対応する秘密パラメータに、前記対応する秘密パラメータおよび対応する関数からのみ決定できる、対応する値の列を連続して適用することによって生成され、予め定められた関係を使用して前記生成された複数の値の列を組み合わせて新たな値の列を生成する段階と、前記新たな列の少なくとも１つの値から再現可能なやり方で前記保護パラメータおよび/または前記検証パラメータを生成する段階と、を含む請求項１３に記載の電子コンポーネントにおける防護方法。
請求項15
生成関数を定める段階を含み、前記生成関数は、予め決定され、メモリに記憶された少なくとも１つの秘密パラメータに、前記秘密パラメータおよび前記生成関数からのみ決定できる値の列を連続して適用することによって定められ、前記生成された値の列を前記暗号アルゴリズムの公開パラメータと組み合わせて新たな値の列を生成する段階と、前記新たな列の少なくとも１つの値から再現可能なやり方で前記保護パラメータおよび/または前記検証パラメータを生成する段階と、を含む請求項１３に記載の電子コンポーネントにおける防護方法。
請求項16
非対称秘密鍵暗号アルゴリズムの防護方法を実現するマイクロプロセッサと、前記秘密鍵を記憶する少なくとも１つの安全なメモリと、保護パラメータを生成するデータ生成器とを備えるマイクロ回路デバイスであって、前記暗号アルゴリズムの基本関数を使用して入力データおよび前記保護パラメータから中間データを計算し、前記秘密鍵の２進表現をいくつかのバイナリブロックに分割し、前記保護パラメータを使用して各バイナリブロックを変換し、変換された各バイナリブロックについて前記基本関数を使用して中間計算を実行し、前記中間データと前記中間計算の結果とを組み合わせることによって出力データを計算するように構成されたマイクロ回路デバイス。
請求項17
前記マイクロプロセッサは、各バイナリブロックの値が前記保護パラメータの値より大きいように、各バイナリブロックの大きさを、反復してランダムに決定するように構成された請求項１６に記載のマイクロ回路デバイス。
請求項18
前記データ生成器は、nが前記秘密鍵の２進表現の大きさであり、n=k・uである整数u≧2が存在するように、前記保護パラメータの２進表現の大きさkを選択するように構成され、前記マイクロプロセッサは、前記秘密鍵の２進表現をそれぞれkビットのu個のバイナリブロックに分割するように構成された請求項１６に記載のマイクロ回路デバイス。
請求項19
前記基本関数は、RSAまたはRSA CRT型の暗号アルゴリズムを実行するための前記秘密鍵による前記入力データのべき乗剰余である請求項１６から１８のいずれか一項に記載のマイクロ回路デバイス。
請求項20
前記基本関数は、楕円曲線に基づく暗号アルゴリズムを実行するための前記秘密鍵による前記入力データのスカラ乗算であり、前記入力データは、前記楕円曲線の予め決定された点である請求項１６から１８のいずれか一項に記載のマイクロ回路デバイス。
請求項21
再現可能なやり方で、前記基本関数の実行前に少なくとも１つの検証パラメータを初期生成し、前記基本関数の実行中または実行後に前記検証パラメータを再生成し、前記再生成された検証パラメータを前記初期生成された検証パラメータと比較するようにさらに構成された請求項１６から２０のいずれか一項に記載のマイクロ回路デバイス。
請求項22
前記データ生成器は、生成関数を定め、前記生成関数は、予め決定され、メモリに記憶された少なくとも１つの秘密パラメータに、前記秘密パラメータおよび前記関数からのみ決定できる値の列を連続して適用することによって定められ、前記列の少なくとも１つの値から再現可能なやり方で前記保護パラメータおよび/または前記検証パラメータを生成することによって前記保護パラメータおよび/または前記検証パラメータを生成するように構成された請求項１６から２１のいずれか一項に記載のマイクロ回路デバイス。
請求項23
前記データ生成器は、複数の関数を定め、各関数は、予め決定され、メモリに記憶された少なくとも１つの対応する秘密パラメータに、前記対応する秘密パラメータおよび対応する関数からのみ決定できる、対応する値の列を連続して適用することによって生成され、予め定められた関係を使用して前記生成された複数の値の列を組み合わせて新たな値の列を生成し、前記新たな列の少なくとも１つの値から再現可能なやり方で前記保護パラメータおよび/または前記検証パラメータを生成するように構成された請求項２２に記載のマイクロ回路デバイス。
請求項24
前記データ生成器は、生成関数を定め、前記生成関数は、予め決定され、メモリに記憶された少なくとも１つの秘密パラメータに、前記秘密パラメータおよび前記生成関数からのみ決定できる値の列を連続して適用することによって定められ、前記生成された値の列を前記暗号アルゴリズムの公開パラメータと組み合わせて新たな値の列を生成し、前記新たな列の少なくとも１つの値から再現可能なやり方で前記保護パラメータおよび/または前記検証パラメータを生成するように構成された請求項２２に記載のマイクロ回路デバイス。
請求項25
請求項１６から２４のいずれか一項に記載のマイクロ回路デバイスを備えるポータブルデバイス、特にチップカード。