(57)【要約】本発明は、電子コンポネントにおいて計算手段を用いて暗号アルゴリズムを実行するための方法に関する。本発明は、以下のステップ、ａ）特定個の値ei（eiは整数）の中から値eを選択するステップと、ｂ）eiが所定の関係を満たすかどうかを検証し、満たす時、e=eiであり、暗号アルゴリズムの計算用にeを記憶するステップと、を実行することからなる。
2005504349.tif 000002
【特許請求の範囲】
【請求項１】
電子コンポネントにおいて計算手段を用いて暗号アルゴリズムを実行する方法であって、
ａ）所定数の値ei（eiは整数）から値eを選択するステップと、
ｂ）前記選択した値eiが所定の式を満たすかどうかをテストするステップと、からなり、
前記所定の式を満たし、e=eiである場合、前記暗号アルゴリズムの計算に使用するためにeを記憶し、
前記所定の式を満たさない場合、前記ステップを繰返して別の値eiを選択し、値eiをeに帰属できない場合、値eを使用する前記暗号アルゴリズムの計算が実行不可能であることを示すことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、
前記ステップｂ）以前に、範囲]0,N[内にある値Yを選択し、演算Yd modulo N（dおよびNは所定の整数）の結果を値Xに割当てるステップを含み、前記ステップb）の所定の式は
【数１】
2005504349.tif 000007
であることを特徴とする方法。
【請求項３】
請求項２に記載の方法において、
Y=2であることを特徴とする方法。
【請求項４】
請求項１乃至３の何れかに記載の方法において、
前記暗号アルゴリズムがRSAアルゴリズムに基づくことを特徴とする方法。
【請求項５】
請求項４に記載の方法において、
前記RSAアルゴリズムが標準モードまたはCRTモードであることを特徴とする方法。
【請求項６】
請求項１に記載の方法において、
前記ステップｂ）の所定の式は、eidp=1 (modulo λ(p))であり、ここでpおよびdpは所定の整数であり、λ(.)はカーマイケル関数であることを特徴とする方法。
【請求項７】
請求項６に記載の方法において、
dp=d (modulo λ(p))である（dは所定の整数）ことを特徴とする方法。
【請求項８】
請求項６または７に記載の方法において、
dqおよびqが所定の整数であり、hcf(p,q)=1である時、前記ステップｂ）が、
eidp=1 (modulo λ(p))であるか否かをテストし、
eidp=1 (modulo λ(p))であり、ei＜λ(p)でe=eiである場合、前記暗号アルゴリズムの計算に使用するためにeを記憶するステップと、
eidp=1 (modulo λ(p))であり、ei≧λ(p)である場合、eidq=1 (modulo λ(q))であるか否かをテストし、eidq=1 (modulo λ(q))でありe=eiである場合、前記暗号アルゴリズムの計算に使用するためにeを記憶するステップと、
前記２つのテストの１つが満たされない場合、別の値eiを使用して前記ステップを繰返し、値eiをeに帰属できない場合、値eを使用する前記暗号アルゴリズムの計算が実行不可能であることを示すステップと、からなることを特徴とする方法。
【請求項９】
請求項８に記載の方法において、
dq=d (modulo λ(q))である（dは所定の整数）ことを特徴とする方法。
【請求項１０】
請求項６乃至９の何れかに記載の方法において、
前記暗号アルゴリズムがCRTモードのRSAアルゴリズムに基づくことを特徴とする方法。
【請求項１１】
請求項１乃至１０の何れかに記載の方法において、
ei=216+1であることを特徴とする方法。
【請求項１２】
請求項１乃至１０の何れかに記載の方法において、
ei=3であることを特徴とする方法。
【請求項１３】
請求項１乃至１２の何れかに記載の方法において、
値eiがeに割当てられる時、前記RSAアルゴリズムの秘密鍵演算の終わりに、値Yから値Xを取得するステップを含み、前記値eを使用する前記計算は、y=xe modulo N（Nは所定の整数）であるか否かを確認するステップを含むことを特徴とする方法。
【請求項１４】
計算手段（２）と、プログラムメモリ（３）と、ワーキングメモリ（４）と、データ通信手段（５）と、を含む電子セキュリティコンポネントであって、請求項１乃至１３の何れかに記載の方法を実行することを特徴とする電子コンポネント。
【請求項１５】
請求項１４に記載の電子コンポネントを含むチップカード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子コンポネントにおいて暗号アルゴリズムを実行する方法に関する。
本発明は、また、そのような電子コンポネントにも関する。
【背景技術】
【０００２】
このような電子コンポネントは、サービスまたはデータへのアクセスを厳しく制御する場合に使用され、マイクロプロセッサおよびメモリを含むアーキテクチャを有する。メモリには、１または複数の秘密指数dを含むROMタイプのプログラムメモリなどが含まれる。
【０００３】
これらの電子コンポネントは、コンピュータシステムにおいてオンボードまたはオフボードで使用され、特に、特定アプリケーション用のチップカードにおいて使用される。これらのアプリケーションには、特定データバンクへのアクセスアプリケーション、バンキングアプリケーション、テレビ視聴、ガソリン購入、または高速道路通行料金などの遠隔決済アプリケーションなどが含まれる。
したがって、これらのコンポネントまたはカードは、秘密保持が必要な時に、送信データの暗号化および／または受信データの解読を保証する暗号アルゴリズムを使用する。
【０００４】
一般に、これら暗号アルゴリズムの機能は、特にメッセージの暗号化またはデジタル署名である。ホストシステム（サーバ、銀行ディスペンサなど）がインプットとしてカードに供給するこのメッセージと、カードに含まれる多くの秘密情報とから、カードは、例えば、ホストシステムがコンポネントまたはカードを認証してデータ交換等をできるようにする暗号化または署名されたメッセージを供給する。
【０００５】
暗号アルゴリズムの特徴である計算の実行やパラメータの使用は、知られていて、プログラムメモリの中に含まれる秘密指数だけが知られていない。暗号アルゴリズムの全セキュリティは、カードに含まれ、このカードの外部には知られていないこの秘密指数に関係する。この秘密指数はインプットとして供給されるメッセージや、返信される暗号化されたメッセージの知識のみからは推測不可能である。
【０００６】
しかし、外部攻撃により悪意のある第三者がカード内の秘密指数を知ることができることが明らかになった。特に、チップカードの分野では、いくつかの攻撃が存在し、その中の１つに“フォールト攻撃”がある。
このタイプの攻撃では、攻撃者は、暗号アルゴリズムの計算中にエラーを注入し、このエラーを利用して秘密情報を引き出す。
また、このエラーは、暗号アルゴリズムを実行するハードウェアが原因の計算エラーに起因することもあるが、いずれの場合もフォールト攻撃のケースと考えていい。
【０００７】
このタイプの攻撃は、特に、この分野のアプリケーションの暗号化に最もよく使用されるRSAアルゴリズムで見られる。RSAアルゴリズムの安全性は、大きな数の素因数分解が困難であることに基づいている。このアルゴリズムは、特に、d（秘密指数）のべき乗計算を使用する。
【０００８】
RSAアルゴリズムの主なステップを簡単に説明する。
２つの素数pおよびqの積である係数Nを定める（N=p.q）。公開指数すなわち公開鍵eおよび秘密指数すなわち秘密鍵dは式（１）e.d=1 (modulo λ(N))を満たす。λ(.)はカーマイケル関数である。
【０００９】
いわゆる標準RSAアルゴリズムの１つの実施例によれば、公開パラメータは(N,e)であり、秘密パラメータは(N,d)である。xが範囲]0,N[内にあると仮定すると、メッセージxの暗号化または署名xの照合などの、xについての公開鍵演算は、式（２）y=xe modulo Nを計算することからなる。
暗号化されたメッセージの解読または署名xの生成などの、対応する秘密鍵演算は、e.d=1 (modulo λ(N))よりx=yd modulo Nの場合に式（３）yd modulo Nを計算することからなる。
【００１０】
次に、中国人剰余定理（Chinese remainder theorem）に基づくためにCRTモードと呼ばれ、標準RSAアルゴリズムより４倍高速な別の演算モードを示す。このCRTモードRSAによれば、modulo Nの計算を直接行わず、まず第一にmodulo pおよびmodulo qの計算を行う。
公開パラメータは(N,e)であり、秘密パラメータは、(p,q,d)または(p,q,dp,dq,iq)である。この時dp=d modulo (p-1)、dq=d modulo (q-1)、およびiq=q-1 modulo pである。式（１）により、edp=1 modulo (p-1)およびedq=1 modulo (q-1)（式（４））を得る。
【００１１】
公開鍵演算は標準演算モードと同様の方法で行われるが、秘密鍵演算においては、まず、
【数１】
2005504349.tif 000003
および
【数２】
2005504349.tif 000004
を計算し、次に、中国人剰余定理を用いて、x=yd mod Nを式（５）x=CRT(xp,xq)=xq+q[iq(xp-xq) modulo p]により得る。
【００１２】
RSAアルゴリズムは、開示を簡単にするために２つの素数pおよびqを使用して示してきたが、Nがhcf(p,q)=1となるような２つの整数pおよびqの積である場合にも拡張できる。この場合、dp=d (modulo λ(p))、dq=d (modulo λ(q))、iqは前記の場合と同様、edp=1 (modulo λ(p))およびedq=1 (modulo λ(q))、xp、xqおよびxは同様である。
この拡張は、標準モードとCRTモードの両方に適用できる。
【００１３】
次に、同じメッセージの２つの署名の取得に基づくフォールト攻撃の一例について説明する。正しい署名をx、正しくない署名を^xとする。
正しくない署名は例えば以下のようにして得られる。攻撃者は、xqではなくxpの計算中に任意の方法でエラーを注入する。したがってxpの値は正しくなく、これを^xpで示す。一方xqの値は正しい。このため、値^xpとxqとが中国人剰余定理を適用することにより再結合される時、結果として生じる署名^xは正しくない。
【００１４】
攻撃者は公開パラメータ(N,e)も当然知っているので、Nとの最大公約数(hcf)、すなわちhcf(^x-x,N)を計算することができる。
しかし、hcf(^x-x,N)=qなので、攻撃者は秘密因数qを取得し、したがってp、dpおよびdqも取得する。このため、RSA暗号は効果的に解読される。
つまり、誰かがmodulo pの計算中にエラーを注入することができ、modulo qの計算が正しい場合か、または逆の場合、攻撃者はRSA暗号を完全に解読することができる。
【００１５】
また、知られているメッセージの正しくない署名を使用してRSA暗号を解読することもできる。フォールト攻撃のいくつかのケースは、刊行物“On the Importance of Checking Cryptographic Protocols for Faults”（D. Boneh, R.A. DeMillo and R.J. Lipton, Advance in Cryptology, EUROCRYPT‘97, pp. 37-51）に開示され、参照可能である。
【００１６】
このタイプのシナリオを回避するための第１の対抗手段は、全アルゴリズムを再計算することである。一連の計算の終わりで得た値どうしを比較する。これらが等しい場合、エラーが注入されなかったと仮定される。この方法の問題点は永久的フォールトを検出できないことである。例えば、注入されたエラーが常に0または1に固定されたメモリビット（“粘着性ビット”）の値からなるような攻撃を識別することは不可能である。
【００１７】
フォールト攻撃に対する別の対抗手段は、Shamirによる特許文献１に説明されている。
この対抗手段によれば、以下のアルゴリズムを開始する。
１．小さい値の乱数rを選択する。
２．xrp=yd modulo r.pとxrq=yd modulo r.qとを計算する。
３．xrp≠xrq(modulo r)の場合、（おそらく攻撃による）フォールト、したがってアルゴリズムの障害が存在し、そうでない場合、
４．xrpおよびxrqに中国人剰余定理を適用し、アウトプットとしてxを得る。
【００１８】
したがって、modulo pおよびmodulo qではなく、modulo r.pおよびmodulo r.qの各計算が行われる。次に、これらの計算から得た２つの値xrpおよびxrqもmodulo rであるか否かがチェックされる。これら２つの値が異なる場合、エラーが存在することは確実である。他方、２つの値が等しい場合、この仮定では誤っている1/rの確率でエラーが存在しないと仮定できる。
【特許文献１】
ＷＯ９８／５２３１９
【発明の開示】
【発明が解決しようとする課題】
【００１９】
この方法の１つの欠点は、確率的なことである。すなわち、エラーは１より小さい確率で検出され、結果としてすべてのエラーが検出されるわけではない。また、計算に時間がかかる。Shamirの方法の別な欠点は、CRTモードでしか機能しないことである。しかし、RSAアルゴリズムの標準モードを使用することにより予想できる。
【００２０】
フォールト攻撃から保護するための最良の防御は、秘密鍵演算（３）または（５）（RSAアルゴリズムの標準モードまたはCRTモードにより異なる）の実行中に得た値xが、公開鍵演算の式（２）y=xe modulo Nを満たすか否かをチェックすることからなる。これは、この式を満足する時、RSAアルゴリズムの秘密鍵演算の実行中にエラーがなかったことを確認できるからである。
【００２１】
しかし、秘密鍵演算を実行するコンポネントまたはデバイスは、特に、秘密鍵演算のみを実行する時、常に公開指数eを利用できるとは限らない。
以上の課題を解決するため、本発明は、先験的に知られていない公開指数eを使用して暗号アルゴリズムの各ステップを実行する方法を提案する。
【課題を解決するための手段】
【００２２】
本発明によれば、特にフォールト攻撃に対する対抗手段がもたらされ、公開指数eが知られていない場合でも最良の保護を提供できる。
本発明の目的は、電子コンポネントにおいて計算手段を使用して暗号アルゴリズムを実行する方法を提供することであり、この方法は、ａ）所定数の値ei（eiは整数）から値eを選択するステップと、ｂ）前記選択した値eiが所定の式を満たすかどうかをテストするステップと、からなり、前記所定の式を満たし、e=eiであれば、前記暗号アルゴリズムの計算に使用するためにeを記憶し、前記所定の式を満たさない場合、前記ステップを繰返して別の値eiを選択し、値eiをeに帰属できない場合、値eを使用した前記暗号アルゴリズムの計算が実行不可能であることを示すことを主として特徴とする。
【００２３】
本発明の１つの実施の形態によれば、前記ステップｂ）以前に、範囲]0,N[内にある値Yを選択し、演算Yd modulo N（dおよびNは所定の整数）の結果を値Xに割当てるステップを含み、前記ステップb）の所定の式は
【数３】
2005504349.tif 000005
である。
【００２４】
好ましくはY=2が選択される。
暗号アルゴリズムはRSAアルゴリズムに基づき、特に標準モードまたはCRTモードである。
【００２５】
本発明の別の実施の形態によれば、ステップｂ）の所定の式は、eidp=1 (modulo λ(p))であり、ここでpおよびdpは所定の整数であり、λ(.)はカーマイケル関数である。
dpはdp=d (modulo λ(p))により求め、dは所定の整数である。
【００２６】
本発明の１つの特徴によれば、dqおよびqが所定の整数であり、hcf(p,q)=1である時、前記ステップｂ）が、eidp=1 (modulo λ(p))であるか否かをテストし、eidp=1 (modulo λ(p))であり、ei＜λ(p)でe=eiである場合、前記暗号アルゴリズムの計算に使用するためにeを記憶するステップと、eidp=1 (modulo λ(p))であり、ei≧λ(p)である場合、eidq=1 (modulo λ(q))であるか否かをテストし、eidq=1 (modulo λ(q))でe=eiである場合、前記暗号アルゴリズムの計算に使用するためにeを記憶するステップと、前記２つのテストの１つが満たされない場合、別の値eiを使用して前記ステップを繰返し、値eiをeに帰属できない場合、値eを使用する前記暗号アルゴリズムの計算が実行不可能であることを示すステップとからなる。
【００２７】
dqは、dq=d (modulo λ(q))により求め、dは所定の整数である。
暗号アルゴリズムはCRTモードのRSAアルゴリズムに基づく。
好ましくは、ei=216+1またはei=3である。
【００２８】
本発明の１つの特徴によれば、値eiがeに割当てられる時、前記RSAアルゴリズムの秘密鍵演算の終わりに、値Yから値Xを取得するステップを含み、値eを使用する前記計算は、y=xe modulo N（Nは所定の整数）であるか否かを確認するステップを含む。
【００２９】
本発明の別の目的は、計算手段と、プログラムメモリと、ワーキングメモリと、データ通信手段とを含み、既述の方法を実行することを特徴とする電子セキュリティコンポネントを提供することである。
【００３０】
本発明は、特に、以上で説明した電子コンポネントを備えたチップカードに関する。
本発明の他の特徴および利点は、本明細書に記載の非限定的な実施例を読み、本発明を実施可能なチップカードの素子を概略的に示す添付の図１を見れば明らかになるだろう。
【００３１】
以下の実施の形態は、チップカードとの関連において説明するが、暗号計算手段を備える他の任意の電子セキュリティデバイスまたはコンポネントにも適用できる。
【発明を実施するための最良の形態】
【００３２】
図１に示すように、チップカード１は、固定メモリ（ROM）３およびランダムアクセスメモリ（RAM）４に接続するマイクロプロセッサ２を含み、アセンブリを構成する全体が、特に、暗号アルゴリズムの実行を可能にする。より正確には、マイクロプロセッサ２は、アルゴリズムに必要な算術計算手段と、メモリ３および４とのデータ転送用回路とを含む。固定メモリ３は、ソースコード形式の暗号アルゴリズムを実行するプログラムを含み、ランダムアクセスメモリ４は、計算結果を記憶する更新可能なレジスタを含む。
【００３３】
また、チップカード１は、外部環境とのデータ交換を可能にする、マイクロプロセッサ２に接続する通信インタフェース５を含む。通信インタフェース５は、“接触”型および／または“非接触”型であってよい。接触型の場合には、カード読取装置などの外部装置の接触器に接続するための１組の接触ピンが形成され、非接触型の場合、通信インタフェース５は、無線接続によるデータ伝送を可能にするアンテナおよび無線通信回路を含む。この接続は、カード１の回路に供給するエネルギの伝達をも可能にする。
【００３４】
先験的に知られていない公開指数eの値を検証する方法を以下で説明する。
この方法は、以下の観察結果に基づいている。つまり、90％のケースにおいてeの値はe0=216+1であり、5%のケースにおいてeの値はe1=3であり、その他のケースではeの値はその他である。
この方法は、e0を選択するステップと、e=e0を確認するステップとからなり、e≠e0の場合には、e1について試みる。
【００３５】
5%のその他のケースに該当する場合には、eがe0およびe1のどちらにも等しくないことが起こる。この場合、eの値はより一般的にeiで表す。結局、この方法は、予想した値eiから値eiを選択するステップと、e=eiを確認するステップとからなる。
【００３６】
RSAアルゴリズムの標準またはCRTモードに有効な第１の実施の形態について説明する。
範囲]0,N[内にある値Yを任意に選択する。
値eiを選択する。
【００３７】
X=Yd modulo Nの計算を、標準モードでは式（３）により、CRTモードでは式（５）により実行し、
【数４】
2005504349.tif 000006
の場合、e=eiであり、eを記憶し、そうでない場合には、eiに対して別の値が選択される。
式（３）または（５）に現れる指数計算Ydを加速するようY=2を有利に選択できる。これは、乗算の代わりに加算を行うことを意味する。
【００３８】
次に、式（４）に基づく別の実施の形態を説明する。この方法は、CRTモードにおいてのみ有効であるが、第１の実施の形態よりも効率的である。
値eiを選択する。
eidp=1 modulo(p-1)（または一般的なケースにおいては、eidp=1 (modulo λ(p))）であるか否かをテストする。
【００３９】
答えがイエスであり、ei＜p（または一般的なケースにおいては、ei＜λ(p)）ならば、
e=eiとeを記憶する。
答えがイエスであり、ei≧p（または一般的なケースにおいては、ei≧λ(p)）ならば、
およそ1-2/pの非常に高い確率でe=eiである。
【００４０】
ei≧p（または一般的なケースにおいては、ei≧λ(p)）の場合、eidq=1 modulo(q-1)（または一般的なケースにおいては、eidq=1 (modulo λ(q))）であるか否かをテストすることにより、確率１で曖昧さを取り除くことができる。このような場合、e=eiとeを記憶する。
【００４１】
しかし、たいてい（ei=216+1またはei=3）の場合、pは512ビット以上の大きさを持つので、ei＜p（または一般的なケースにおいては、ei＜λ(p)）である。
上記テストのうちの１つを満足しない場合、eiに対して別の値が選択される。
もし、上記第１または別の実施の形態について、e=eiとなるような値が値eiの中に存在しない場合、eを含む計算ができない。
【００４２】
上記第１または別の実施の形態を通じてeが知られている時、y=xe modulo Nであるか否かをチェックすることにより各秘密鍵演算（３）または（５）の結果を確認するか、またはより一般的には、記憶されている値eを使用して計算することができる。
以上に見られるように、本発明による方法は対抗手段にも適用可能である。
【００４３】
本発明による対抗手段は、アルゴリズムの全部を再計算する、つまり、指数d（dの大きさはN）に対して少なくとも第２の指数計算をするステップと、連続的な計算の終わりに得られる値を比較するステップとからなる従来技術による対抗手段より高速である。本発明による方法は、指数e（eは小さい）に対して第２の指数計算をするステップも含む。
この方法は、また永久的フォールトを検出することもできる。
本発明は、RSAアルゴリズムの標準モードと、CRTモードの両ケース、そして、両モードの派生モードにも適用できる。
【図面の簡単な説明】
【００４４】
【図１】本発明を実施可能にするチップカードの素子を概略的に示す図である。
【図１】
2005504349.tif 000008
【国際公開パンフレット】
2005504349.tif 000009
2005504349.tif 000010
2005504349.tif 000011
2005504349.tif 000012
2005504349.tif 000013
2005504349.tif 000014
2005504349.tif 000015
2005504349.tif 000016
2005504349.tif 000017
2005504349.tif 000018
2005504349.tif 000019
2005504349.tif 000020
2005504349.tif 000021
2005504349.tif 000022
2005504349.tif 000023
2005504349.tif 000024
2005504349.tif 000025
2005504349.tif 000026
2005504349.tif 000027
2005504349.tif 000028
2005504349.tif 000029
【国際調査報告】
2005504349.tif 000030
2005504349.tif 000031
2005504349.tif 000032
2005504349.tif 000033
2005504349.tif 000034
2005504349.tif 000035