(57)【要約】  本発明は、電子構成要素にＲＳＡタイプの暗号アルゴリズムを安全に適用するための方法に関する。方法によって、有望な値の所与の集合から公開指数ｅの値を、前記値を先験的に知ることなしに取得することができ、公開指数ｅの前記値を決定すると、エラー攻撃およびサイド・チャネル攻撃を遮断するために、ｅの値を使用する対策、特にＤＰＡおよびＳＰＡタイプを適用することができ、これは暗号アルゴリズムの秘密演算を適用して実行することができる。【特許請求の範囲】
【請求項１】
公開鍵暗号アルゴリズムを安全に実施するための方法であって、前記公開鍵が、２つの大きい素数ｐおよびｑの積である整数ｎと公開指数ｅとで構成され、前記方法が、前記公開指数ｅの値に対応可能である所定数の素数ｅｉを備える集合Ｅを決定することからなり、前記方法が、
ａ）Ｅに属する任意のｅｉについてΦ／ｅｉがΦ（ｎ）より小さくなるように、値
【数１】
2007500863.tif 000004
を計算するステップであって、ここで、Φはオイラーのトーシェント関数であるステップと、
ｂ）値Φを所定の計算に適用するステップと、
ｃ）各ｅｉについて、前記所定の計算の結果が値Φ／ｅｉと等しいかどうかを試験するステップであって、
−等しい場合は、値ｅｉをｅに帰し、前記暗号アルゴリズムの計算に使用するためにｅを記憶し、
−それ以外では、値ｅを使用した暗号アルゴリズムの計算が実行不可能であることを遵守するステップとを含むことを特徴とする方法。
【請求項２】
暗号アルゴリズムが、標準モードのＲＳＡタイプのアルゴリズムに基づくことを特徴とする、請求項１に記載の方法。
【請求項３】
前記ステップｂ）の前記所定の計算が、値Ｃ＝Φ．ｄ  ｍｏｄｕｌｏ  Φ（ｎ）の計算からなり、ここで、ｄは、ｅ．ｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）であるような前記ＲＳＡアルゴリズムの対応する秘密鍵であり、Φが前記オイラーのトーシェント関数であることを特徴とする、請求項２に記載の方法。
【請求項４】
前記ステップｂ）の前記所定の計算が、値Ｃ＝Φ．ｄ  ｍｏｄｕｌｏ  Φ（ｎ）の計算からなり、ここで、ｄは、ｅ．ｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）であるような前記ＲＳＡアルゴリズムの対応する秘密鍵であり、Φがカーマイケル関数であることを特徴とする、請求項２に記載の方法。
【請求項５】
前記暗号アルゴリズムが、ＣＲＴモードのＲＳＡタイプのアルゴリズムに基づくことを特徴とする、請求項１に記載の方法。
【請求項６】
前記ステップｂ）の所定の計算が、値Ｃ＝Φ．ｄｐ  ｍｏｄｕｌｏ  （ｐ−１）の計算からなり、ここで、ｄｐは、ｅ．ｄｐ＝１  ｍｏｄｕｌｏ  （ｐ−１）であるようなＲＳＡアルゴリズムの対応する秘密鍵であることを特徴とする、請求項５に記載の方法。
【請求項７】
前記ステップｂ）の前記所定の計算が、値Ｃ＝Φ．ｄｑ  ｍｏｄｕｌｏ  （ｑ−１）の計算からなり、ここで、ｄｑは、ｅ．ｄｑ＝１  ｍｏｄｕｌｏ  （ｑ−１）であるような前記ＲＳＡアルゴリズムの対応する秘密鍵であることを特徴とする、請求項５に記載の方法。
【請求項８】
前記ステップｂ）の前記所定の計算が、以下の２つの値Ｃ１およびＣ２の計算からなり、
Ｃ１＝Φ．ｄｐ  ｍｏｄｕｌｏ  （ｐ−１）、ここで、ｄｐは、ｅ．ｄｐ＝１  ｍｏｄｕｌｏ  （ｐ−１）であるような前記ＲＳＡアルゴリズムの対応する秘密鍵、
Ｃ２＝Φ．ｄｑ  ｍｏｄｕｌｏ  （ｑ−１）、ここで、ｄｑは、ｅ．ｄｑ＝１  ｍｏｄｕｌｏ  （ｑ−１）であるような前記ＲＳＡアルゴリズムの対応する秘密鍵、
前記試験ステップｃ）が、各ｅｉについて、Ｃ１および／またはＣ２が値Φ／ｅｉと等しいかどうかを試験することからなり、
−等しい場合は、値ｅｉをｅに帰し、前記暗号アルゴリズムの計算に使用するためにｅを記憶し、
−それ以外では、値ｅを使用した前記暗号アルゴリズムの計算が実行不可能であることを遵守することを特徴とする、請求項５に記載の方法。
【請求項９】
値ｅｉがｅに帰され、前記方法が、値ｅを使用する計算が、
ランダムな整数ｒを選択することと、
ｄ＊＝ｄ＋ｒ．（ｅ．ｄ−１）であるように、値ｄ＊を計算することと、
関係式ｘ＝ｙｄ＊  ｍｏｄｕｌｏ  ｎを適用することによって、値ｙから値ｘを得るアルゴリズムの秘密演算を実施することからなることを特徴とする、請求項３または４に記載の方法。
【請求項１０】
値ｅｉがｅに帰され、前記方法が、アルゴリズムの秘密演算の後、値ｙから値ｘを得ることからなり、値ｅを使用する計算が、ｘｅ＝ｙ  ｍｏｄｕｌｏ  ｎであるかをチェックすることからなることを特徴とする、請求項２乃至４の何れかに記載の方法。
【請求項１１】
値ｅｉがｅに帰され、前記方法が、アルゴリズムの秘密演算の後、値ｙから値ｘを得ることからなり、値ｅを使用する計算が、第一にｘｅ＝ｙ  ｍｏｄｕｌｏ  ｐであるか、第二にｘｅ＝ｙ  ｍｏｄｕｌｏ  ｑであるかをチェックすることからなることを特徴とする、請求項５乃至８の何れかに記載の方法。
【請求項１２】
前記集合Ｅが少なくとも以下のｅｉの値、すなわち３、１７、２１６＋１を含むことを特徴とする、請求項１乃至１１のいずれかに記載の方法。
【請求項１３】
請求項１乃至１２のいずれかに記載の方法を実施するための手段を備えることを特徴とする電子構成要素。
【請求項１４】
請求項１３に記載の電子構成要素を含むスマート・カード。
【請求項１５】
公開鍵暗号アルゴリズムを安全に実施するための方法であって、前記公開鍵が、２つの大きい素数ｐおよびｑの積である整数ｎと公開指数ｅとで構成され、前記方法が、公開指数ｅの値に対応可能である所定数の素数ｅｉを含む集合Ｅを決定することからなり、
ａ）集合Ｅの値から値ｅｉを選択するステップと、
ｂ）Φ（ｐ）＝Φ（ｑ）の場合、選択したｅｉの値が、関係式
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（Φ（ｎ）／２）＋１
または単純化した前記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（Φ（ｎ）／２）＋１
を満足させるかどうかを試験し、
Φ（ｐ）、Φ（ｑ）およびΦ（ｎ）が、それぞれ数ｐ、数ｑおよび数ｎをコード化するビットの数を与える関数であり、
それ以外では、ｐとｑが不均衡である場合に、選択したｅｉの値が以下の関係式
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１
または単純化した前記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１
を満足させるかどうかを試験するステップであって、
Φ（ｐ）およびΦ（ｑ）が分かっている場合は、ｇ＝ｍａｘ（Φ（ｐ），Φ（ｑ））、またはそれ以外では、ｇ＝Φ（ｎ）／２＋ｔであり、ここで、ｔが不均衡係数またはその係数の限界を示すステップと、
ｃ）前記ステップで適用された試験関係式を満し、したがってｅ＝ｅｉである場合は、前記暗号アルゴリズムの計算に使用するためにｅを記憶するステップであって、
−それ以外では、ｅｉの値をｅに帰すことができるまで、集合Ｅからｅｉの別の値を選択しながら前記ステップを繰り返し、ｅに帰すことができるｅｉの値がない場合は、ｅの値を使用する前記暗号アルゴリズムの計算が実行不可能であることを遵守するステップとを含むことを特徴とする方法。
【請求項１６】
ｉの全ての値でｅｉ≦２１６＋１であり、前記ステップｂ）が、別の試験ステップ、すなわち
ｂ）Φ（ｐ）＝Φ（ｑ）の場合は、選択したｅｉの値が関係式
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（Φ（ｎ）／２）＋１７
または単純化した前記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（Φ（ｎ）／２）＋１７
を満足させるかどうかを試験するステップで置換され、
ここで、Φ（ｐ）、Φ（ｑ）およびΦ（ｎ）が、それぞれ数ｐ、数ｑおよび数ｎをコード化するビットの数を与える関数であり、
それ以外では、ｐとｑが不均衡である場合には、選択したｅｉの値が以下の関係式
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１７
または単純化した前記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１７
を満足させるかどうかを試験するステップで置換され、
Φ（ｐ）およびΦ（ｑ）が分かっている場合は、ｇ＝ｍａｘ（Φ（ｐ），Φ（ｑ））、またはそれ以外では、ｇ＝Φ（ｎ）／２＋ｔであり、ここで、ｔが不均衡係数またはその係数の限界を示すことを特徴とする、請求項１５に記載の方法。
【請求項１７】
前記ステップｂ）が、
選択したｅｉの値が前記関係式を満たすかどうかを試験し、それにより、
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎの最初の最上位ビットがゼロであるか、
または単純化した前記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎの最初の最上位ビットがゼロであることからなる別の試験ステップで置換されることを特徴とする、請求項１５に記載の方法。
【請求項１８】
前記試験が最初の１２８の最上位ビットで実行されることを特徴とする、請求項１７に記載の方法。
【請求項１９】
前記暗号アルゴリズムが、標準モードのＲＳＡタイプのアルゴリズムに基づくことを特徴とする、請求項１５乃至１８の何れかに記載の方法。
【請求項２０】
ｅｉの値がｅに帰され、前記方法が、値ｅを使用する前記計算が、
ランダムな整数ｒを選択することと、
ｄ＊＝ｄ＋ｒ．（ｅ．ｄ−１）であるように、値ｄ＊を計算することと、
前記関係式ｘ＝ｙｄ＊  ｍｏｄｕｌｏ  ｎを適用することにより、値ｙから値ｘが得られるアルゴリズムの秘密演算を実施することからなることを特徴とする、請求項１５乃至１９の何れかに記載の方法。
【請求項２１】
ｅｉの値がｅに帰され、前記方法が、前記アルゴリズムの秘密演算の後、値ｙから値ｘを得ることからなり、値ｅを使用する前記計算が、ｘｅ＝ｙ  ｍｏｄｕｌｏ  ｎであるかをチェックすることからなることを特徴とする、請求項１５乃至１９の何れかに記載の方法。
【請求項２２】
集合Ｅが少なくとも以下のｅｉの値、すなわち３、１７、２１６＋１を含むことを特徴とする、請求項１５乃至２１の何れかに記載の方法。
【請求項２３】
集合Ｅの値から値ｅｉの好ましい選択が、以下の順序、すなわち２１６＋１、３、１７の順序で行われることを特徴とする、請求項２２に記載の方法。
【請求項２４】
請求項１５乃至２３の何れかに記載の方法を実施するための手段を備えることを特徴とする電子構成要素。
【請求項２５】
請求項２４に記載の電子構成要素を含むスマート・カード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子構成要素で暗号アルゴリズムを安全に実施するための方法に関し、特にリベスト・シャミール・アドレマン（ＲＳＡ）タイプの暗号アルゴリズムを安全に実施するための方法に関する。
本発明は、また、対応する電子構成要素に関する。
【背景技術】
【０００２】
このような構成要素は、特に、サービスまたはデータへのアクセスが厳格に制御されている用途で使用される。
１つまたは複数の秘密番号を含む電気消去可能プログラマブル読出し専用メモリ（ＥＥＰＲＯＭ）タイプの不揮発性メモリなど、マイクロプロセッサおよびメモリの周囲には、「ソフトウェア」アーキテクチャ、すなわちプログラム可能なアーキテクチャが形成される。アーキテクチャは、任意のアルゴリズムを実行するのに適切な非専門家アルゴリズムである。
【０００３】
このような構成要素は、コンピュータ・システムに実装されるか、他の方法で使用される。特にスマート・カードに、その特定の用途用に使用される。例えば、このような使用法とは、特定のデータバンクにアクセスする用途、バンキング用途、遠隔支払い用途、例えば、ＴＶショッピング、ガソリンの購入、または高速道路料金の支払いである。
それ故、このような構成要素またはカードは、送信されたデータの暗号化および／または受信データの解読、またはメッセージの認証またはディジタル署名のために、暗号アルゴリズムを実施する。
【０００４】
ホスト・システム（サーバ、現金自動預入支払機など）によってカードへの入力として適用されるこのようなメッセージに基づき、さらにカードに含まれる秘密番号に基づき、カードは、暗号化、認証または署名した状態でメッセージをホスト・システムへと戻し、これによってホスト・システムは、構成要素またはカードを認証し、データなどを交換することができる。
【０００５】
暗号アルゴリズムの特徴は、実行した計算、使用したパラメータによって知ることができる。唯一の未知の量は１つまたは複数の秘密番号である。このような暗号アルゴリズムの全体的セキュリティは、カードに含まれ、カードの外側の世界には知られていないこのような１つまたは複数の秘密番号に依拠する。秘密番号は、入力として与えられたメッセージ、および返報に送付される暗号化メッセージを知るだけでは演繹することができない。
【０００６】
残念ながら、構成要素が暗号アルゴリズムを実行する間に、構成要素の外側から測定可能な物理的大きさに基づいた外部からの攻撃によって、悪意のある人がカードに含まれる秘密番号を発見することが可能である。このような攻撃は、「サイド・チャネル攻撃」として周知である。このようなサイド・チャネル攻撃の中には、１つまたは複数の測定値に基づく単一電力解析（ＳＰＡ）攻撃、多くの測定値による統計学的解析に基づく差分電力解析（ＤＰＡ）攻撃がある。このようなサイド・チャネル攻撃の原理は、例えば、命令を実行するマイクロプロセッサの電流消費量は、取り扱い中の命令またはデータの関数として変動するという事実に基づく。
【０００７】
「故障攻撃」として知られる攻撃のタイプも存在する。このタイプの攻撃では、故障の存在を利用して、秘密情報を抽出するという目的で、暗号アルゴリズムが計算されている間に、攻撃者が任意の故障を投入する。
故障は、暗号アルゴリズムを実施しているハードウェアによる計算エラーに由来することもある。しかし、いずれの場合も、故障攻撃が発生したと見なされる。
様々なタイプの攻撃は、例えば、この用途分野で最も広く使用されているアルゴリズムであり、本発明が特に適用可能であるＲＳＡアルゴリズム（その著者であるリベスト、シャミールおよびアドレマンにちなんで命名された）などの公開鍵暗号アルゴリズムで、特に可能である。
【０００８】
ＲＳＡ公開鍵暗号システムの主要な特徴について、以下で簡単に思い起こす。
最初の公開鍵暗号および署名の体系は、１９７７年にリベスト、シャミールおよびアドレマンによって開発され、彼らはＲＳＡ暗号システムを発明した。ＲＳＡの安全性は、２つの素数の積である大きい数字を因数分解することの困難さに基づく。そのシステムは、最も広く使用されている公開鍵暗号システムである。これは、暗号法または署名法として使用することができる。
ＲＳＡ暗号システムの原理は、以下の通りである。これはまず、ＲＳＡキーの対を生成することで構成される。
【０００９】
それ故、各使用者は以下の５段階の方法を使用して、ＲＳＡ公開鍵および対応する秘密鍵を生成する。
１）２つの離散的素数ｐおよびｑを生成する。
２）ｎ＝ｐｑおよびΦ（ｎ）＝（ｐ−１）（ｑ−１）を計算する。ここで、Φはオイラーのトーシェント関数またはオイラーのファイ関数と呼ばれる。
３）ｐｇｃｄ（ｅ，Φ（ｎ））＝１になるように、ランダムに、または使用者の選択で１＜ｅ＜Φ（ｎ）である整数ｅを選択する。それ故、使用者はｅ＝２１６＋１またはｅ＝３またはｅ＝１７であるように、ｅを小さく選択することができる。
４）ｅ．ｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）            （１）
であるように、一意の整数ｄ（ただし、１＜ｄ＜Φ（ｎ））を計算する。
５）公開鍵は（ｎ，ｅ）であり、秘密鍵はｄまたは（ｄ，ｐ，ｑ）である。
整数ｅおよびｄはそれぞれ、「公開指数」および「秘密指数」と呼ばれる。整数ｎは「ＲＳＡ法」と呼ばれる。
【００１０】
公開および秘密パラメータが画定されると、ｘが０＜ｘ＜ｎである場合、
ｙ＝ｘｅ  ｍｏｄｕｌｏ  ｎ                    （２）
の計算に存し、ｘの公開演算は、例えば、メッセージｘの暗号であってもよい。
【００１１】
その場合、対応する秘密演算は、暗号化したメッセージｙを解読する演算であり、下式の計算である。
Ｙｄ  ｍｏｄｕｌｏ  ｎ                （３）
【００１２】
ｘの公開演算は、署名ｘの検証でもよく、下式の計算である。
ｙ＝ｘｅ  ｍｏｄｕｌｏ  ｎ            （２）
【００１３】
次に、対応する秘密演算は、ハッシュ関数または「埋め込み」関数μを適用することによって以前にコード化したメッセージｙに基づいて署名ｘを生成することであり、下式の計算である。
Ｙｄ  ｍｏｄｕｌｏ  ｎ              （３）
ここで、ｅ．ｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）であるので、ｘ＝ｙｄ  ｍｏｄｕｌｏ  ｎである。
【００１４】
中国人剰余定理（ＣＲＴ）モードとして知られる別の演算モードについて、以下で提示する。これは、標準的なＲＳＡアルゴリズムの演算モードより４倍速い。ＣＲＴモードでは、モジュロｎ計算を直接的に実行せず、モジュロｐおよびモジュロｑの計算を最初に実行する。
【００１５】
公開パラメータは（ｎ，ｅ）であるが、ＣＲＴのモードでは、秘密パラメータは（ｐ，ｑ，ｄ）または（ｐ，ｑ，ｄｐ，ｄｑ，ｉｑ）であり、ここで、
ｄｐ＝ｄ  ｍｏｄｕｌｏ  （ｐ−１）、ｄｑ＝ｄ  ｍｏｄｕｌｏ  （ｑ−１）
およびｉｑ＝ｑ−１  ｍｏｄｕｌｏ  ｐ
【００１６】
式（１）により、下式が得られる。
ｅｄｐ＝１  ｍｏｄｕｌｏ  (ｐ−１)および
ｅｄｑ＝１  ｍｏｄｕｌｏ  (ｑ−１)          （４）
【００１７】
公開演算は、標準的演算モードと同じ方法で実行される。これに対して、秘密演算の場合は下式を最初に計算する。
ｘｐ＝ｙｄｐ  ｍｏｄｕｌｏ  ｐおよびｘｑ＝ｙｄｑ  ｍｏｄｕｌｏ  ｑ
【００１８】
次に、中国人剰余定理を適用することによって、ｘ＝ｙｄ  ｍｏｄｕｌｏ  ｎが下式により得られる。
ｘ＝ＣＲＴ(ｘｐ，ｘｑ)＝ｘｑ＋ｑ［ｉｑ(ｘｐ−ｘｑ)  ｍｏｄｕｌｏ  ｐ］      （５）
【００１９】
それ故、ＲＳＡ暗号体系を使用する公開鍵暗号の分野の重要な態様は、上述した様々なあり得るタイプの攻撃、特にＤＰＡおよびＳＰＡ攻撃のようなサイド・チャネル攻撃、さらに攻撃者が、特定の場合に秘密データの特定の項目を演繹することが可能になる破損値を得る目的で、任意の方法を使用することによりＲＳＡアルゴリズムの秘密演算を計算中に故障を投入する「故障」攻撃に対して、ＲＳＡアルゴリズムの実施を安全なものにすることに存する。
【００２０】
最新技術では、様々なタイプの攻撃を回避するために、特定の対策方法が考案されている。
特に、標準モードのＲＳＡに対するＤＰＡ（およびＳＰＡ）タイプの攻撃を回避するために可能な１つの対策は、計算にランダム値を挿入することによってＲＳＡのランダムな秘密演算（署名または解読）を実行することに存する。
【００２１】
それ故、そのタイプの１つの対策方法は、以下の方法で標準モードの（３）ｘ＝ｙｄ  ｍｏｄｕｌｏ  ｎの秘密演算を計算することに存する。
ｘ＝ｙｄ−ｒ．ｙｒ  ｍｏｄｕｌｏ  ｎ
ここで、ｒはランダムな整数である。しかし、その対策方法の欠点は、計算時間が２倍になることである。
【００２２】
標準モードのＲＳＡに対するＤＰＡ（およびＳＰＡ）タイプの攻撃を回避するそのタイプの別の対策方法は、以下の方法で秘密演算（３）ｘ＝ｙｄ  ｍｏｄｕｌｏ  ｎを計算することに存する。
ｘ＝ｙ（ｄ＋ｒ．Φ（ｎ））  ｍｏｄｕｌｏ  ｎ
ここで、ｒはランダムな整数である。
【００２３】
しかし、その対策方法の欠点は、Φ（ｎ）の値を知る必要があることであり、これは秘密演算（署名または解読）を実施する暗号アルゴリズムには通常、知られていない。
それ故、Φ（ｎ）の値を知ることばかりでなく、公開指数ｅを知ることにも基づいて、その方法の変形が提案されている。（１）によってｅ．ｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）が与えられ、したがってｅ．ｄ−１＝ｋ．Φ（ｎ）になるような整数ｋが存在する。
【００２４】
それ故、式ｘ＝ｙ（ｄ＋ｒ．Φ（ｎ））  ｍｏｄｕｌｏ  ｎは、以下の形式で計算することができる。
ｘ＝ｙ（ｄ＋ｒ．（ｅｄ−１））  ｍｏｄｕｌｏ  ｎ
ここで、ｒはランダムな整数である。
【００２５】
それ故、この対策方法は、これが従う方法と計算上等しいが、Φ（ｎ）の値を知る必要がないという利点を提供する。Φ（ｎ）を維持しないという意味で、必要とするメモリが少なくなる。
しかし、実施するためには、この変形の対策は公開指数ｅの値を知る必要がある。残念ながら、多くの暗号用途で、ＲＳＡアルゴリズムの秘密演算を実施する構成要素またはデバイスは、特に秘密演算のみを実行する場合、常に公開指数ｅを有するとは限らない。それ故、その状況で、公開指数ｅは通常分からないか、使用不可能である。
【００２６】
上述した対策は主に、ＤＰＡタイプの攻撃を回避するためのものである。しかし、アルゴリズムの実行が決定論的ではない限り、ＳＰＡタイプの攻撃もさらに困難にする。
他の上述したタイプの攻撃、すなわち「故障」攻撃に関して、これを回避するために可能な最善の保護は、秘密演算を適用することによって取得した値ｘが実際に公開演算の関係式ｘｅ＝ｙ  ｍｏｄｕｌｏ  ｎを満足させるかどうか、標準モードで試験することに存する。満足させない場合は、暗号目的に使用されるのを防止するように、値ｙが戻されない。
【００２７】
ＣＲＴモードでは、保護は最初に関係式ｘｅ＝ｙ  ｍｏｄｕｌｏ  ｐおよびｘｅ＝ｙ  ｍｏｄｕｌｏ  ｑを実際に満足しているかどうかをチェックすることに存する。
これらの関係式が満足している場合は、ＲＳＡアルゴリズムの秘密演算を実行中に、エラーが発生しなかったことを確証することが可能である。
【００２８】
しかし、標準モードまたはＣＲＴモードで故障攻撃に対するこのようなチェックの実施を妨げる欠点は、このようなチェックの演算も公開指数ｅの以前の知識を必要とすることである。残念ながら、上記で説明したように標準モードまたはＣＲＴモードでＲＳＡアルゴリズムの秘密演算を実施する構成要素またはデバイスは、常に公開指数ｅを有しているとは限らない。秘密演算のみを実行する場合は、特にそうである。それ故その状況では、公開指数ｅは通常分からないか、使用不可能である。
【００２９】
そのために、フランス特許文献第ＦＲ  ２  ８３０  １４６号（Ｄ１）は、先験的に分かっていない公開指数ｅを使用して、特に標準モードまたはＣＲＴモードでＲＳＡタイプの暗号アルゴリズムの特定のステップを実行可能にする方法を提案している。
Ｄ１で開示された方法によって、特に、公開指数ｅが知られていない場合でも、上述したような最善の可能な保護を提供する対策、特に故障攻撃に対する対策を提供することが可能である。
【００３０】
そのために、（ｅ，ｄ）を、それぞれ公開および秘密のＲＳＡ指数の対応する対とし、ｎをＲＳＡの法であるとする。Ｄ１は、ケースの９５％で公開指数ｅの値が２１６＋１、３、１７の値から選択されるという以下の観察から開始する。標準モードに関して本明細書で簡単に説明するが、ＣＲＴモードにも等しく適用可能であるＤ１の方法は、関係式を満足させるまでｅｉ．ｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）であるかを連続的に試験することによって、ｅが実際に上記値の１つに等しいことをチェックすることに存する。ここで、ｅｉΦＥ＝｛２１６＋１，３，１７｝である。
【００３１】
１つのｅｉについて関係式が満足すると、ｅ＝ｅｉであることが分かる。この方法で公開指数ｅの値が決定されると、ＲＳＡアルゴリズムの対応する秘密演算を実行する間に故障攻撃のせいでエラーが発生していないことをチェックする目的で、ＲＳＡアルゴリズムの計算に使用するためにｅを記憶する。それ故、ｅが分かると、単に取得した値ｓが対応する公開演算の関係式ｓｅ＝μ（ｍ）  ｍｏｄｕｌｏ  ｎを満足させることをチェックするだけで、１に等しい確率で、例えば、署名ｓの生成に関する秘密演算がエラーなく実行されたと断言することが可能である。ここで、ｓ＝μ（ｍ）ｄ  ｍｏｄｕｌｏ  ｎであり、μ（ｍ）は埋め込み関数μを署名すべきメッセージｍに適用することによって得られる値である。
【００３２】
ｅｉのいずれの値もｅに帰すことが可能でなかった場合、Ｄ１では、故障攻撃に対して保護するために、値ｅを使用してＲＳＡアルゴリズムの計算を実行することができないことに留意する必要がある。
【００３３】
しかし、Ｄ１で提案された方法の欠点は、認識されるｅｉの値からの値ｅｉについて、関係式ｅｉｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）を満たすかどうかを決定するために連続的試験を実行する場合、複数のモジュラ計算を実行する必要があることである。それ故、この方法は計算時間および計算資源が法外に厳しい。
【特許文献１】フランス特許文献第ＦＲ  ２  ８３０  １４６号（Ｄ１）
【発明の開示】
【発明が解決しようとする課題】
【００３４】
それ故、生じた問題は、上述した欠点を軽減することである。
特に、本発明の目的は、ｅの上記値が先験的に分かっている場合に、計算速度および複雑さが法外に厳しくない方法で、１組の所定の推定値から公開指数ｅの値を決定することに存し、指数ｅは、標準モードまたはＣＲＴモードのＲＳＡタイプ暗号アルゴリズムの特定のステップで実装される。
【００３５】
それ故別の目的は、公開指数ｅの値が決定されると、特に暗号アルゴリズム、特にＲＳＡタイプのアルゴリズムの秘密演算の実施中に作成されるようなＤＰＡおよびＳＰＡタイプ、第一に「故障攻撃」を、第二に「サイド・チャネル攻撃」を回避することを目的として、公開指数ｅの値を使用して対策演算を実施することを可能にすることに存する。
【課題を解決するための手段】
【００３６】
これらの目的を達成することに鑑みて、本発明は、公開鍵暗号アルゴリズムを安全に実行する方法を提供し、公開鍵は２つの大きい素数ｐおよびｑの積である整数ｎと公開指数ｅとで構成され、上記方法は、公開指数ｅの値に対応することができる所定の数の値ｅｉを備えた集合Ｅを決定することに存し、ｅｉの値は素数であり、上記方法は、
ａ）Ｅに属する任意のｅｉについて、Φ／ｅｉがΦ（ｎ）より小さくなるように、値
【００３７】
【数１】
2007500863.tif 000002
【００３８】
を計算するステップであって、Φはオイラーのトーシェント関数であるステップと、
ｂ）値Φを所定の計算に適用するステップと、
ｃ）各ｅｉについて、上記所定の計算の結果が値Φ／ｅｉに等しいかどうかを試験するステップであって、
−等しい場合は、値ｅｉをｅに帰して、上記暗号アルゴリズムの計算に使用するためにｅを記憶し、
−それ以外の場合は、値ｅを使用した暗号アルゴリズムの計算が実行不可能であることを遵守するステップとを含むことを特徴とする。
それ故、利点はモジュラ乗算が１回だけであることが明白である。
【００３９】
第１の変形では、暗号アルゴリズムは標準モードのＲＳＡタイプのアルゴリズムに基づく。
上記第１変形に関して、ステップｂ）の所定の計算は、以下のような値Ｃの計算である。
Ｃ＝Φ．ｄ  ｍｏｄｕｌｏ  Φ（ｎ）
ここで、ｄは、ｅ．ｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）であるようなＲＳＡアルゴリズムの対応する秘密鍵であり、Φはオイラーのトーシェント関数である。
【００４０】
代替方法では、ステップｂ）の所定の計算は、以下のような値Ｃの計算である。
Ｃ＝Φ．ｄ  ｍｏｄｕｌｏ  Φ（ｎ）
ここで、ｄは、ｅ．ｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）であるようなＲＳＡアルゴリズムの対応する秘密鍵であり、Φはカーマイケル関数である。
【００４１】
第２の変形では、暗号アルゴリズムはＣＲＴモードのＲＳＡタイプのアルゴリズムに基づく。
上記第２変形に関して、ステップｂ）の所定の計算は、以下のような値Ｃの計算である。
Ｃ＝Φ．ｄｐ  ｍｏｄｕｌｏ  （ｐ−１）
ここで、ｄｐは、ｅ．ｄｐ＝１  ｍｏｄｕｌｏ  （ｐ−１）であるようなＲＳＡアルゴリズムの対応する秘密鍵である。
【００４２】
代替方法では、ステップｂ）の所定の計算は、以下のような値Ｃの計算である。
Ｃ＝Φ．ｄｑ  ｍｏｄｕｌｏ  （ｑ−１）
ここで、ｄｑは、ｅ．ｄｑ＝１  ｍｏｄｕｌｏ  （ｑ−１）であるようなＲＳＡアルゴリズムの対応する秘密鍵である。
【００４３】
別の代替方法では、ステップｂ）の所定の計算は、以下のような２つの値Ｃ１およびＣ２の計算である。
Ｃ１＝Φ．ｄｐ  ｍｏｄｕｌｏ  （ｐ−１）
ここで、ｄｐは、ｅ．ｄｐ＝１  ｍｏｄｕｌｏ  （ｐ−１）であるようなＲＳＡアルゴリズムの対応する秘密鍵である。
【００４４】
Ｃ２＝Φ．ｄｑ  ｍｏｄｕｌｏ  （ｑ−１）
ここで、ｄｑは、ｅ．ｄｑ＝１  ｍｏｄｕｌｏ  （ｑ−１）であるようなＲＳＡアルゴリズムの対応する秘密鍵である。
【００４５】
さらに、試験ステップｃ）は、各ｅｉについて、Ｃ１および／またはＣ２が値Φ／ｅｉと等しいかどうかを試験することに存し、
−等しい場合は、値ｅｉをｅに帰して、上記暗号アルゴリズムの計算に使用するためにｅを記憶し、
−それ以外の場合は、値ｅを使用した上記暗号アルゴリズムの計算が実行不可能であることを遵守する。
【００４６】
第１の変形では、値ｅｉがｅに帰されている場合、値ｅを使用する計算は、以下である。
ランダムな整数ｒを選択し、
ｄ＊＝ｄ＋ｒ．（ｅ．ｄ−１）であるように値ｄ＊を計算し、
関係式ｘ＝ｙｄ＊  ｍｏｄｕｌｏ  ｎを適用することによって、値ｙから値ｘを得るアルゴリズムの秘密演算を実施する。
【００４７】
第１の変形では、値ｅｉがｅに帰されている場合、値ｅを使用する計算は、アルゴリズムの秘密演算の後、値ｙから値ｘを得ることと、ｘｅ＝ｙ  ｍｏｄｕｌｏ  ｎであるかをチェックすることに存する。
第２の変形では、値ｅｉがｅに帰されている場合、値ｅを使用する計算は、アルゴリズムの秘密演算の後、値ｙから値ｘを得ることと、最初にｘｅ＝ｙ  ｍｏｄｕｌｏ  ｐであるか、第二にｘｅ＝ｙ  ｍｏｄｕｌｏ  ｑであるかをチェックすることに存する。
集合Ｅは、少なくとも以下のｅｉの値、すなわち３、１７、２１６＋１を備えることが好ましい。
【００４８】
本発明は、上記で定義したような方法を実施するための手段を備えることを特徴とする電子構成要素も提供する。
本発明は、定義されたような電子構成要素を含むスマート・カードも備える。
【００４９】
本発明は、また、公開鍵暗号アルゴリズムを安全に実施するための方法を提供し、公開鍵は、２つの大きい素数ｐおよびｑの積である整数ｎと公開指数ｅとで構成され、上記方法は、公開指数ｅの値に対応することができる所定数の値ｅｉを含む集合Ｅを決定することに存し、ｅｉの値は素数であり、上記方法は、
ａ）集合Ｅの値から値ｅｉを選択するステップと、
ｂ）Φ（ｐ）＝Φ（ｑ）である場合、選択されたｅｉの値が関係式、
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（Φ（ｎ）／２）＋１
または単純化した上記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（Φ（ｎ）／２）＋１
を満たすかどうかを試験し、
ここで、Φ（ｐ）、Φ（ｑ）およびΦ（ｎ）は、それぞれ数ｐ、数ｑおよび数ｎをコード化するビットの数を与える関数であり、
これ以外では、ｐおよびｑが不均衡である場合は、選択したｅｉの値が関係式
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１
または単純化した上記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１
を満たすかどうかを試験するステップとを含み、
Φ（ｐ）およびΦ（ｑ）が分かっている場合は、ｇ＝ｍａｘ（Φ（ｐ），Φ（ｑ））、またはそれ以外では、ｇ＝Φ（ｎ）／２＋ｔで、ｔが不均衡な係数またはその係数の限界を示し、さらに、
ｃ）先行するステップに適用された試験関係式を満たし、したがってｅ＝ｅｉである場合は、上記暗号アルゴリズムの計算に使用するためにｅを記憶するステップを含み、
それ以外では、ｅｉの値をｅに帰すことが可能になるまで、集合Ｅからｅｉの別の値を選択しながら、先行するステップを繰り返し、ｅに帰すことが可能なｅｉの値がない場合は、ｅの値を使用する上記暗号アルゴリズムの計算が実行不可能であることを遵守することを特徴とする。
【００５０】
ｅｉの値の順番を、現れた公開指数の確率の順番として選択することによって、時間を節約することが可能になる。それ故、次の順序、すなわちｅ０＝２１６＋１、ｅ１＝３、ｅ２＝１７を選択可能であることが好ましい。
【００５１】
変形では、ｉの全ての値についてｅｉ≦２１６＋１であり、ステップｂ）は下記に存する別の試験ステップで置換される。すなわち、
ここで、Φ（ｐ）＝Φ（ｑ）である場合は、選択したｅｉの値が以下の関係式、すなわち
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（Φ（ｎ）／２）＋１７
または単純化した上記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（Φ（ｎ）／２）＋１７
を満たすかどうかを試験し、
Φ（ｐ）、Φ（ｑ）およびΦ（ｎ）が、それぞれ数ｐ、数ｑおよび数ｎをコード化するビットの数を与える関数であり、
これ以外では、ｐおよびｑが不均衡である場合は、選択したｅｉの値が以下の関係式：
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１７
または単純化した上記関係式：
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１７
を満たすかどうかを試験し、
Φ（ｐ）およびΦ（ｑ）が分かっている場合は、ｇ＝ｍａｘ（Φ（ｐ），Φ（ｑ））で、すなわちそれ以外では、ｇ＝Φ（ｎ）／２＋ｔであり、ｔが不均衡な係数またはその係数の限界を示す。
【００５２】
別の変形では、ステップｂ）が以下に存する別の試験ステップで置換される、すなわち、
選択したｅｉの値が関係式を満たすかどうかを試験するステップを含み、それにより、
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎの最初の最上位ビットがゼロであるか、
単純化した上記関係式で、
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎの最初の最上位ビットがゼロである。
【００５３】
試験は、最初の１２８の最上位ビットで実行することが好ましい。
本発明の好ましい実施形態では、暗号アルゴリズムは標準モードのＲＳＡタイプのアルゴリズムに基づく。
１つの特徴によると、ｅｉの値がｅに帰されている場合、値ｅを使用する計算は、
ランダムな整数ｒを選択することと、
ｄ＊＝ｄ＋ｒ．（ｅ．ｄ−１）であるように値ｄ＊を計算することと、
関係式ｘ＝ｙｄ＊  ｍｏｄｕｌｏ  ｎを適用することによって値ｙから値ｘが得られるアルゴリズムの秘密演算を実施することとである。
【００５４】
別の特徴によると、ｅｉの値がｅに帰されている場合、本発明の方法は、アルゴリズムの秘密演算の後、値ｙから値ｘを得ることに存し、値ｅを使用する計算は、ｘｅ＝ｙ  ｍｏｄｕｌｏ  ｎであるかをチェックすることに存する。
好適には、集合Ｅは、少なくとも以下のｅｉの値、すなわち３、１７、２１６＋１を備えることが好ましい。
【００５５】
本発明は、上記で定義したような方法を実施するための手段を備えることを特徴とする電子構成要素も提供する。
本発明は、定義されたような電子構成要素を含むスマート・カードも提供する。
本発明の他の特徴および利点は、非制限的な表示によって与えられる以下の説明から、さらに明白になる。
【発明を実施するための最良の形態】
【００５６】
それ故、本発明は、先験的に分からない公開指数ｅの値の検証を可能にする様々な技術について説明する。これらの技術は、適切な暗号計算手段を装備した任意の電子構成要素またはデバイスによって、特にスマート・カードによって実施することができる。
本発明は、以下の観察結果に基づく。すなわち、集合Ｅが少なくとも以下のｅの値を備えるようにする。すなわちｅ０＝２１６＋１、ｅ１＝３、およびｅ２＝１７を備える。値のこの集合Ｅは、ＲＳＡタイプの暗号アルゴリズムの計算で一般的に使用する公開指数の値の約９５％を含む。
【００５７】
本発明で提示し、ＲＳＡアルゴリズムの標準モードで有効である第１の技術は、一般に、ｅ０を選択することと、ｅ＝ｅ０であるかをチェックすることに存し、ｅ≠ｅ０の場合はｅ１で試み、ｅ≠ｅ１である場合は、ｅ２で試みる。
５％という他のケースに対応する特定の用途では、ｅはｅ０にもｅ１にもｅ２にも等しくないことが可能である。それ故、ｅの値はｅ１によってさらに一般的に指定される。また、方法は最終的に、想起されるｅｉの値から値ｅｉを選択することと、ｅ＝ｅ１であるかをチェックすることに存する。
【００５８】
特に、ＲＳＡアルゴリズムの標準モードで有効であるｅの値を求める第１技術は、以下の推論に基づく。
標準モードでは、秘密アルゴリズム（メッセージに署名するか、これを解読する演算を実施する）が、モジュラスｎの値および秘密指数ｄの値を有する。
それ故、式（１）から、下式のような整数ｋが存在することになる。
ｅ．ｄ＝１＋ｋΦ（ｎ）
すなわち、１−ｅ．ｄ＝−ｋΦ（ｎ）＝−ｋ．（ｎ−ｐ−ｑ＋１）
【００５９】
式ｍｏｄｕｌｏ  ｎの両辺を引くことによって、下式が得られる。
１−ｅ．ｄ＝ｋ（ｐ＋ｑ−１）（ｍｏｄｕｌｏ  ｎ）
ｅが比較的小さい場合に、ｋ＜ｅが常に得られることに留意すると、上式は下式のように書くこともできる。
（１−ｅ．ｄ）  ｍｏｄｕｌｏ  ｎ＝ｋ（ｐ＋ｑ−１）      （６）
【００６０】
式（６）の左辺はモジュラスｎとほぼ同じサイズを有し、右辺は、ｐとｑが平衡している、すなわち同じサイズΦ（ｐ）＝Φ（ｑ）である場合に、下式に従い画定されるサイズを有する。
ｋ．（ｐ＋ｑ−１）＜ｅ．２（Φ（ｎ）／２）＋１
ここで、Φ（ｎ）、Φ（ｐ）、Φ（ｑ）は、それぞれ数ｎ、数ｐおよび数ｑをコード化するビットの数を与える関数である。
【００６１】
ｐとｑが同じサイズでない場合は、Φ（ｐ）およびΦ（ｑ）が分かれば、ｇ＝ｍａｘ（Φ（ｐ），Φ（ｑ））の関数、すなわちｐおよびｑの最大長さを与える関数を呼び出すか、そうでない場合は、ｇ＝Φ（ｎ）／２＋ｔを得る。ここで、ｔは不均衡係数を示し、あるいは他の場合ではその係数の限界を示す。ｐとｑが不均衡である場合、上式の公式は下式のようになる。
ｋ．（ｐ＋ｑ−１）＜ｅ．２１＋ｇ
【００６２】
ｎ＝ｐ．ｑであるので、ｐとｑが平衡している場合は式ｐ＋ｑ＜２（Φ（ｎ）／２）＋１が得られ、逆にｐとｑが不均衡である場合はｐ＋ｑ＜２１＋ｇになる。
それ故、集合Ｅの全ての可能なｅｉの値で、Φ（ｐ）＝Φ（ｑ）である場合は、試験を実施して、選択したｅｉ値が以下の所定の関係式を満たすかどうかを判断する。
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（Φ（ｎ）／２）＋１      （７）
【００６３】
これ以外では、試験を実施して、選択したｅｉの値が以下の所定の関係式を満たすかどうかを判断する。
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１            （７’）
適用した所定の試験関係式を満たす場合は、ｅ＝ｅｉであり、ｅが記憶される。
それ以外では、集合Ｅからｅｉのために別の値を選択し、先行するステップを繰り返す。
【００６４】
第１の変形では、ｅの値を求める試験は、ｐとｑが平衡しているかいないかに応じて、
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（Φ（ｎ）／２）＋１または
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１
を以下の試験で置換することができる。
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜Ｂ
ここで、Φ（ｐ）＝Φ（ｑ）である場合は、Ｂ＝［最大（ｅｉ）］２２（Φ（ｎ）／２）＋１
他の場合は、Ｂ＝［最大（ｅｉ）］２ｇ＋１
【００６５】
発明者の例では、Ｅ＝｛２１６＋１，３，１７｝である。それ故、ｉの全ての値についてｅｉ＝２１６＋１であり、先行する試験は、
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜Ｂ、ここで、Ｂ＝２（Φ（ｎ）／２）＋１７であり、Φ（ｐ）＝Φ（ｑ）である場合、
それ以外では、（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜Ｂ、ここで、Ｂ＝２ｇ＋１７
であるかをチェックすることに存する以下の方法で単純化することができる。
【００６６】
試験の第２の変形では、（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎの最上位ビット、例えば、１２８の最上位ビットがゼロであるかをチェックすることにより、先行する試験をさらに単純化することが可能である。
【００６７】
最後に、第１の技術について、最終的な単純化は、ｅｉの値に関する試験の所定の関係式を求めることに存し、関係式（６）の代わりに、以下の関係式で開始する。
（−ｅ．ｄ）  ｍｏｄｕｌｏ  ｎ＝ｋ（ｐ＋ｑ−１）−１
それ故、この単純化から、試験関係式（７、７’）について、以下の単純化が得られる。
Φ(ｐ)＝Φ(ｑ)の場合は、（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ２（Φ（ｎ）／２）＋１
それ以外では、（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１
【００６８】
第１の変形では、以下の単純化した試験が得られる。
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜Ｂ、ここで、Φ（ｐ）＝Φ（ｑ）の場合は、Ｂ＝２（Φ（ｎ）／２）＋１７、それ以外では、Ｂ＝２ｇ＋１７である。
また、試験の第２の変形では、（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎの第１最上位ビットがゼロであるかをチェックすることに存する以下の単純化した試験が得られる。
実施する変形に関係なく、これが単純化したタイプであっても、そうでなくても、ｅｉの値について試験を満足しない場合は、一致点を見いだすまで集合Ｅからｅｉの別の値を選択する。
【００６９】
上述した第１の技術に関するいずれの変形でも、ｅｉの値の中にｅ＝ｅｉであるような値が存在しない場合、ｅを伴う標準モードのＲＳＡ暗号アルゴリズムの計算を実行できないことが、そのままである。
逆に、いずれかの変形によって所定の値Ｅの集合の値ｅｉからｅの値を見いだした場合は、秘密演算を適用することによって値ｙに基づいて得られた値ｘが、関係式ｘｅ＝ｙ  ｍｏｄｕｌｏ  ｎを満足することを確保することによって、暗号アルゴリズム（メッセージの解読または署名の生成である）の各秘密演算（３）をチェックすることが可能である。これ以外では、任意の暗号解読を回避するように、解読したメッセージまたは署名を戻さない。
【００７０】
上記で説明したように、ｅが分かると、本発明の方法を、対策に、特に、上記ＤＰＡ（およびＳＰＡ）タイプの攻撃に対する対策にも適用することができる。それ故、このような方法は、ランダムな整数ｒを選択することと、ｄ＊＝ｄ＋ｒ．（ｅ．ｄ−１）であるように値ｄ＊を計算することと、関係式ｘ＝ｙｄ＊  ｍｏｄｕｌｏ  ｎを適用することによって値ｙから値ｘを得るアルゴリズムの秘密演算を実施することに存する。
【００７１】
最後に、本発明は、所定の値ｅｉの集合を備える集合Ｅから指数ｅの値を求める第２の技術に関する。以下で説明するように、この技術は、ＲＳＡアルゴリズムの標準モードとＣＲＴモードの両方に適用可能である。
【００７２】
上記技術は、特に、Ｄ１で提示された方法の改善である。それ故、以下のステップを実施する。
ａ）Ｅに属する任意のｅｉについて、Φ／ｅｉがΦ（ｎ）より小さくなるように、値
【００７３】
【数２】
2007500863.tif 000003
を画定する。ここで、Φは、オイラーのトーシェント関数である。
【００７４】
ｂ）値Φを所定の計算に適用する。
ｃ）各ｅｉについて、上記所定の計算結果が値Φ／ｅｉに等しいかどうかを試験する。
−等しい場合は、ｅｉをｅに帰し、暗号アルゴリズムの計算に使用するためにｅを記憶する。
−それ以外では、値ｅを使用する暗号アルゴリズムの計算を実行することができない。
【００７５】
標準モードでは、ステップｂ）の所定の計算は、以下のように値Ｃの計算である。
Ｃ＝Φ．ｄ  ｍｏｄｕｌｏ  Φ（ｎ）であり、ここで、ｄは、ｅ．ｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）であるように、標準モードのＲＳＡアルゴリズムの対応する秘密鍵である。
例えば、集合Ｅ＝｛ｅ０＝３，ｅ１＝１７，ｅ２＝２１６＋１｝にすると、Φ＝ｅ０．ｅ１．ｅ２＝３．１７．（２１６＋１）である。
【００７６】
それ故、Ｃ＝Φ．ｄ  ｍｏｄｕｌｏ  Φ（ｎ）では、
Ｃ＝１７．（２１６＋１）＝Φ／ｅ０であれば、ｅ＝ｅ０＝３であり、
Ｃ＝３．（２１６＋１）＝Φ／ｅ１であれば、ｅ＝ｅ１＝１７であり、
Ｃ＝３．１７＝Φ／ｅ２であれば、ｅ＝ｅ２＝（２１６＋１）である。
それ故、Ｃの値の取得を可能にする単一のモジュラ計算によって、上記計算の結果の関数として、集合Ｅから指数ｅの値を求めることが可能である。
【００７７】
代替方法では、ステップｂ）の所定の計算は、以下のように値Ｃを計算することに存する。
Ｃ＝Φ．ｄ  ｍｏｄｕｌｏ  Φ（ｎ）であり、ここで、ｄは、標準モードのＲＳＡアルゴリズムの対応する秘密鍵であるが、オイラーのトーシェント関数をモジュロとする代わりに、カーマイケル関数をモジュロとする上記代替法で計算され、それ故ｅ．ｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）であり、Φはカーマイケル関数である。
ｅの値を求め、記憶すると、ｅの値を実装する標準モードの暗号アルゴリズムの計算は、故障攻撃を回避することと、対策、特にＤＰＡ（およびＳＰＡ）タイプの攻撃に対する対策を設けることに存し、これは第１技術に関して説明した計算と同一である。
【００７８】
変形では、実施されるＲＳＡアルゴリズムがＣＲＴモードである場合は、ステップｂ）の所定の計算は、以下のように値Ｃの計算に存する。
Ｃ＝Φ．ｄｐ  ｍｏｄｕｌｏ  （ｐ−１）であり、ここで、ｄｐはｅ．ｄｐ＝１  ｍｏｄｕｌｏ  （ｐ−１）であるようなＲＳＡアルゴリズムの対応する秘密鍵である。
あるいは実際には、
Ｃ＝Φ．ｄｑ  ｍｏｄｕｌｏ  （ｑ−１）であり、ここで、ｄｑはｅ．ｄｑ＝１  ｍｏｄｕｌｏ  （ｑ−１）であるようなＲＳＡアルゴリズムの対応する秘密鍵である。
または実際にはその両方であり、さらに２つの試験のうち少なくとも一方によって与えられるｅを得ることに存する。
ｅの値を実際に求め、記憶すると、ｅの値を実装するＣＲＴモードの暗号アルゴリズムの計算は、故障攻撃を回避することに存する。
【００７９】
次に、ＣＲＴモードの秘密演算を適用することによって値ｙから取得した値ｘが、第一に関係式ｘｅ＝ｙ  ｍｏｄｕｌｏ  ｐ、第二に関係式ｘｅ＝ｙ  ｍｏｄｕｌｏ  ｑを満足させることを確保することによって、暗号アルゴリズム（メッセージの解読または署名の生成である）のＣＲＴモードの各秘密演算をチェックすることが可能である。
【手続補正書】
【提出日】平成18年4月3日(2006.4.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
公開鍵暗号アルゴリズムを安全に実施するための方法であって、前記公開鍵が、２つの大きい素数ｐおよびｑの積である整数ｎと公開指数ｅとで構成され、前記アルゴリズムが、秘密鍵を含み、前記方法が、前記公開指数ｅの値に対応可能である所定数の素数ｅｉを備える集合Ｅを決定することからなり、前記方法が、
ａ）Ｅに属する任意のｅｉについてΕ／ｅｉがΦ（ｎ）より小さくなるように、値
【数１】
2007500863.tif 000005
を計算するステップであって、Φはオイラーのトーシェント関数であるステップと、
ｂ）値Εを関係する所定の計算にモジュラ積として適用するステップであって、Εのモジュラ積のみが前記アルゴリズムの前記秘密鍵によって乗算されるステップと、
ｃ）各ｅｉについて、前記所定の計算の結果が値Ε／ｅｉと等しいかどうかを試験するステップであって、
−等しい場合は、値ｅｉをｅに帰し、前記暗号アルゴリズムの計算に使用するためにｅを記憶し、
−それ以外では、値ｅを使用した暗号アルゴリズムの計算が実行不可能であることを遵守するステップとを含むことを特徴とする方法。
【請求項２】
暗号アルゴリズムが、標準モードのＲＳＡタイプのアルゴリズムに基づくことを特徴とする、請求項１に記載の方法。
【請求項３】
前記ステップｂ）の前記所定の計算が、値Ｃ＝Ε．ｄ  ｍｏｄｕｌｏ  Φ（ｎ）の計算からなり、ここで、ｄは、ｅ．ｄ＝１  ｍｏｄｕｌｏ  Φ（ｎ）であるような前記ＲＳＡアルゴリズムの対応する秘密鍵であり、Φが前記オイラーのトーシェント関数であることを特徴とする、請求項２に記載の方法。
【請求項４】
前記ステップｂ）の前記所定の計算が、値Ｃ＝Ε．ｄ  ｍｏｄｕｌｏ  λ（ｎ）の計算からなり、ここで、ｄは、ｅ．ｄ＝１  ｍｏｄｕｌｏ  λ（ｎ）であるような前記ＲＳＡアルゴリズムの対応する秘密鍵であり、λがカーマイケル関数であることを特徴とする、請求項２に記載の方法。
【請求項５】
前記暗号アルゴリズムが、ＣＲＴモードのＲＳＡタイプのアルゴリズムに基づくことを特徴とする、請求項１に記載の方法。
【請求項６】
前記ステップｂ）の前記所定の計算が、値Ｃ＝Ε．ｄｐ  ｍｏｄｕｌｏ  （ｐ−１）の計算からなり、ここで、ｄｐは、ｅ．ｄｐ＝１  ｍｏｄｕｌｏ  （ｐ−１）であるようなＲＳＡアルゴリズムの対応する秘密鍵であることを特徴とする、請求項５に記載の方法。
【請求項７】
前記ステップｂ）の前記所定の計算が、値Ｃ＝Ε．ｄｑ  ｍｏｄｕｌｏ  （ｑ−１）の計算からなり、ここで、ｄｑは、ｅ．ｄｑ＝１  ｍｏｄｕｌｏ  （ｑ−１）であるような前記ＲＳＡアルゴリズムの対応する秘密鍵であることを特徴とする、請求項５に記載の方法。
【請求項８】
前記ステップｂ）の前記所定の計算が、以下の２つの値Ｃ１およびＣ２の計算、
Ｃ１＝Ε．ｄｐ  ｍｏｄｕｌｏ  （ｐ−１）、ここで、ｄｐは、ｅ．ｄｐ＝１  ｍｏｄｕｌｏ  （ｐ−１）であるような前記ＲＳＡアルゴリズムの対応する秘密鍵、
Ｃ２＝Ε．ｄｑ  ｍｏｄｕｌｏ  （ｑ−１）、ここで、ｄｑは、ｅ．ｄｑ＝１  ｍｏｄｕｌｏ  （ｑ−１）であるような前記ＲＳＡアルゴリズムの対応する秘密鍵、
からなり、
前記試験ステップｃ）が、各ｅｉについて、Ｃ１および／またはＣ２が値Ε／ｅｉと等しいかどうかを試験することからなり、
−等しい場合は、値ｅｉをｅに帰し、前記暗号アルゴリズムの計算に使用するためにｅを記憶し、
−それ以外では、値ｅを使用した前記暗号アルゴリズムの計算が実行不可能であることを遵守することを特徴とする、請求項５に記載の方法。
【請求項９】
値ｅｉがｅに帰され、前記方法が、値ｅを使用する計算が、
ランダムな整数ｒを選択することと、
ｄ＊＝ｄ＋ｒ．（ｅ．ｄ−１）であるように、値ｄ＊を計算することと、
関係式ｘ＝ｙｄ＊  ｍｏｄｕｌｏ  ｎを適用することによって値ｙから値ｘを得るアルゴリズムの秘密演算を実施することとからなることを特徴とする、請求項３または４に記載の方法。
【請求項１０】
値ｅｉがｅに帰され、前記方法が、アルゴリズムの秘密演算の後、値ｙから値ｘを得ることからなり、値ｅを使用する計算が、ｘｅ＝ｙ  ｍｏｄｕｌｏ  ｎであるかをチェックすることからなることを特徴とする、請求項２乃至４の何れかに記載の方法。
【請求項１１】
値ｅｉがｅに帰され、前記方法が、アルゴリズムの秘密演算の後、値ｙから値ｘを得ることからなり、値ｅを使用する計算が、第一にｘｅ＝ｙ  ｍｏｄｕｌｏ  ｐであるか、第二にｘｅ＝ｙ  ｍｏｄｕｌｏ  ｑであるかをチェックすることからなることを特徴とする、請求項５乃至８の何れかに記載の方法。
【請求項１２】
前記集合Ｅが少なくとも以下のｅｉの値、すなわち３、１７、２１６＋１を含むことを特徴とする、請求項１乃至１１のいずれかに記載の方法。
【請求項１３】
請求項１乃至１２のいずれかに記載の方法を実施するための手段を備えることを特徴とする電子構成要素。
【請求項１４】
請求項１３に記載の電子構成要素を含むスマート・カード。
【請求項１５】
公開鍵暗号アルゴリズムを安全に実施するための方法であって、前記公開鍵が、２つの大きい素数ｐおよびｑの積である整数ｎと公開指数ｅとで構成され、前記方法が、公開指数ｅの値に対応可能である所定数の素数ｅｉを含む集合Ｅを決定することからなり、
ａ）集合Ｅの値から値ｅｉを選択するステップと、
ｂ）δｎ、δ（ｐ）およびδ（ｑ）が、それぞれ数ｎ、数ｐ、および数ｑをコード化するビットの数を与える関数であり、δ（ｐ）＝δ（ｑ）の場合、選択したｅｉの値が、関係式
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（δ（ｎ）／２）＋１
または単純化した前記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（δ（ｎ）／２）＋１
を満足させるかどうかを試験するステップであって、
δ（ｐ）、δ（ｑ）およびδ（ｎ）が、それぞれ数ｐ、数ｑおよび数ｎをコード化するビットの数を与える関数であるステップと、
ｃ）前記ステップで適用された試験関係式を満たし、したがってｅ＝ｅｉである場合は、前記暗号アルゴリズムの計算に使用するためにｅを記憶するステップであって、
−それ以外では、ｅｉの値をｅに帰すことができるまで、集合Ｅからｅｉの別の値を選択しながら前記ステップを繰り返し、ｅに帰すことができるｅｉの値がない場合は、ｅの値を使用する前記暗号アルゴリズムの計算が実行不可能であることを遵守するステップとを含むことを特徴とする方法。
【請求項１６】
δ（ｐ）＃δ（ｑ）の場合に、すなわちｐとｑが不均衡である場合に、以下の方法で、選択したｅｉの値が以下の関係式
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１
または単純化した前記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１
を満足させるかどうかを試験して、ステップｂを実行することからなり、
δ（ｐ）およびδ（ｑ）が分かっている場合は、ｇ＝ｍａｘ（δ（ｐ），δ（ｑ））、またはそれ以外では、ｇ＝δ（ｎ）／２＋ｔであり、ここで、ｔが不均衡係数またはその係数の限界を示すことを特徴とする、請求項１５に記載の公開鍵暗号アルゴリズムを安全に実施するための方法。
【請求項１７】
ｉの全ての値でｅｉ＝２１６＋１であり、前記ステップｂ）が、別の試験ステップ、すなわち
ｂ）δ（ｐ）＝δ（ｑ）の場合は、選択したｅｉの値が関係式
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（δ（ｎ）／２）＋１７
または単純化した前記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２（δ（ｎ）／２）＋１７
を満足させるかどうかを試験するステップで置換され、
ここで、δ（ｐ）、δ（ｑ）およびδ（ｎ）が、それぞれ数ｐ、数ｑおよび数ｎをコード化するビットの数を与える関数であり、
それ以外では、ｐとｑが不均衡である場合には、選択したｅｉの値が以下の関係式
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１７
または単純化した前記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎ＜ｅｉ．２ｇ＋１７
を満足させるかどうかを試験するステップで置換され、
δ（ｐ）およびδ（ｑ）が分かっている場合は、ｇ＝ｍａｘ（δ（ｐ），δ（ｑ））、またはそれ以外では、ｇ＝δ（ｎ）／２＋ｔであり、ここで、ｔが不均衡係数またはその係数の限界を示すことを特徴とする、請求項１５または１６に記載の方法。
【請求項１８】
前記ステップｂ）が、
選択したｅｉの値が前記関係式を満たすかどうかを試験し、それにより、
（１−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎの最初の最上位ビットがゼロであるか、
または単純化した前記関係式
（−ｅｉ．ｄ）  ｍｏｄｕｌｏ  ｎの最初の最上位ビットがゼロであることからなる別の試験ステップで置換されることを特徴とする、請求項１５または１６に記載の方法。
【請求項１９】
前記試験が最初の１２８の最上位ビットで実行されることを特徴とする、請求項１８に記載の方法。
【請求項２０】
前記暗号アルゴリズムが、標準モードのＲＳＡタイプのアルゴリズムに基づくことを特徴とする、請求項１５乃至１９の何れかに記載の方法。
【請求項２１】
ｅｉの値がｅに帰され、前記方法が、値ｅを使用する計算が、
ランダムな整数ｒを選択することと、
ｄ＊＝ｄ＋ｒ．（ｅ．ｄ−１）であるように、値ｄ＊を計算することと、
関係式ｘ＝ｙｄ＊  ｍｏｄｕｌｏ  ｎを適用することにより、値ｙから値ｘが得られるアルゴリズムの秘密演算を実施することとからなることを特徴とする、請求項１５乃至２０の何れかに記載の方法。
【請求項２２】
ｅｉの値がｅに帰され、前記方法が、前記アルゴリズムの秘密演算の後、値ｙから値ｘを得ることからなり、値ｅを使用する計算が、ｘｅ＝ｙ  ｍｏｄｕｌｏ  ｎであるかをチェックすることからなることを特徴とする、請求項１５乃至２０の何れかに記載の方法。
【請求項２３】
集合Ｅが少なくとも以下のｅｉの値、すなわち３、１７、２１６＋１を含むことを特徴とする、請求項１５乃至２２の何れかに記載の方法。
【請求項２４】
集合Ｅの値から値ｅｉの好ましい選択が、以下の順序、すなわち２１６＋１、３、１７の順序で行われることを特徴とする、請求項２３に記載の方法。
【請求項２５】
請求項１５乃至２４の何れかに記載の方法を実施するための手段を備えることを特徴とする電子構成要素。
【請求項２６】
請求項２５に記載の電子構成要素を含むスマート・カード。
【国際調査報告】
2007500863.tif 000006
2007500863.tif 000007
2007500863.tif 000008
2007500863.tif 000009