(57)【特許請求の範囲】
【請求項１】
数式Ｒ＝ＸＹ  ｍｏｄ  Ｎにより定義されるモジュラべき乗演算アルゴリズムを実行する、メッセージ暗号化または解読方法であって、
前記Ｙはｋビットのサイズを有する指数であり、前記メッセージ暗号化方法では公開暗号指数であり、前記メッセージ解読方法では秘密解読指数であり、
前記Ｎはｋ'ビットのサイズを有する法であり、
前記Ｘはｋ”ビットのサイズを有する既知の変数であり、前記メッセージ暗号化方法では暗号化すべきメッセージであり、前記メッセージ解読方法では暗号化されたメッセージであり、
前記Ｒはモジュラべき乗演算の結果であり、かつｋ'ビットのサイズを有し、前記メッセージ暗号化方法では暗号化されたメッセージであり、前記メッセージ解読方法では解読されたメッセージであり、
前記メッセージ暗号化または解読方法は、
前記モジュラべき乗演算アルゴリズムにおいてレジスタＲ１およびＲ２、および結果が前記レジスタＲ１にあるときには０を示し、結果が前記レジスタＲ２にあるときには１を示すインジケータＩを使用するステップと、
マイクロプロセッサを使用して前記モジュラべき乗演算アルゴリズムを実行するステップとを含み、
前記アルゴリズムは、以下の実行ステップ、つまり初期設定ステップと呼ばれるステップａおよびｂ、つまり、
ａ）前記レジスタＲ１を１に、レジスタＺをＸに初期化するステップと、
ｂ）前記インジケータＩを０に初期化するステップと、
また、計算ステップと呼ばれるステップｃ、ｄ、およびｅ、つまり、
ｉが“０”から“ｋ−１”まで変わる、したがってＹの２進表現が最下位ビットＹ（０）から最上位ビットＹ（ｋ−１）まで推移するＹの２進表現のＹ（ｉ）の各ビットに対して、
ｃ）前記レジスタＺの値を自乗して格納する演算Ｚ：＝Ｚ２を実行するステップと、
ｄ）前記インジケータＩが０を示す場合、前記レジスタＲ１の値と前記レジスタＺの値とを乗算して前記レジスタＲ２に格納する演算Ｒ２：＝Ｒ１＊Ｚを実行し、また、前記インジケータＩが１を示す場合、前記レジスタＲ２の値と前記レジスタＺの値とを乗算して前記レジスタＲ１に格納する演算Ｒ１：＝Ｒ２＊Ｚを実行するステップと、
ｅ）Ｙ（ｉ）＝０の場合、前記インジケータＩの値を不変に保ち、Ｙ（ｉ）＝１の場合、前記インジケータＩの値の補数をとるステップとを含むことを特徴とするメッセージ暗号化または解読方法。
【請求項２】
数式Ｒ＝ＸＹ  ｍｏｄ  Ｎにより定義されるモジュラべき乗演算アルゴリズムを実行する、メッセージ暗号化または解読方法であって、
前記Ｙはｋビットのサイズを有する指数であり、前記メッセージ暗号化方法では公開暗号指数であり、前記メッセージ解読方法では秘密解読指数であり、
前記Ｎはｋ'ビットのサイズを有する法であり、
前記Ｘはｋ”ビットのサイズを有する既知の変数であり、前記メッセージ暗号化方法では暗号化すべきメッセージであり、前記メッセージ解読方法では暗号化されたメッセージであり、
前記Ｒはモジュラべき乗演算の結果であり、かつｋ'ビットのサイズを有し、前記メッセージ暗号化方法では暗号化されたメッセージであり、前記メッセージ解読方法では解読されたメッセージであり、
前記メッセージ暗号化または解読方法は、
前記モジュラべき乗演算アルゴリズムにおいてレジスタＲ１およびＲ２、および結果が前記レジスタＲ１にあるときには０を示し、結果が前記レジスタＲ２にあるときには１を示すインジケータＩを使用するステップと、
マイクロプロセッサを使用して前記モジュラべき乗演算アルゴリズムを実行するステップとを含み、
前記アルゴリズムは、以下の実行ステップ、つまり初期設定ステップと呼ばれるステップａおよびｂ、つまり、
ａ）前記レジスタＲ１を１に初期化するステップと、
ｂ）前記インジケータＩを０に初期化するステップと、
また、計算ステップと呼ばれるステップｃ、ｄ、ｅ、およびｆ、つまり、
ｉが“ｋ−１”から“０”まで変わる、したがってＹの２進表現が最上位ビットＹ（ｋ−１）から最下位ビットＹ（０）まで推移するＹの２進表現のＹ（ｉ）の各ビットに対して、
ｃ）前記インジケータＩが０を示す場合に、前記レジスタＲ１の値を自乗して前記レジスタＲ２に格納する演算Ｒ２＝（Ｒ１）２を実行し、前記インジケータＩが１を示す場合に、前記レジスタＲ２の値を自乗して前記レジスタＲ１に格納する演算Ｒ１＝（Ｒ２）２を実行するステップと、
ｄ）ステップｃのどちらの場合でも、前記インジケータＩの値の補数をとる、つまり、“０”から“１”へ、または“１”から“０”へ値を変えるステップと、
ｅ）前記インジケータＩについてテスト演算を繰り返し、前記インジケータＩが０を示す場合、前記レジスタＲ１の値とＸとを乗算して前記レジスタＲ２に格納する演算Ｒ２＝Ｒ１＊Ｘを実行し、前記インジケータＩが１を示す場合、前記レジスタＲ２の値とＸとを乗算して前記レジスタＲ１に格納する演算Ｒ１＝Ｒ２＊Ｘを実行するステップと、
ｆ）Ｙ（ｉ）が１に等しい場合、前記インジケータＩの値の補数をとるステップと、Ｙ（ｉ）が０に等しい場合、前記インジケータＩの値を不変に保つステップとを含むことを特徴とするメッセージ暗号化または解読方法。
【請求項３】
レジスタＲ１およびＲ２と、インジケータＩと、マイクロプロセッサとを含む電子構成品であって、
前記電子構成品は請求項１または２に記載の方法を実行することを特徴とする電子構成品。
【請求項４】
請求項３に記載の電子構成品において、チップカードタイプのポータブル電子機器であることを特徴とする電子構成品。
【請求項５】
レジスタＲ１およびＲ２と、インジケータＩと、マイクロプロセッサとを含む電子端末装置であって、
前記電子端末装置は請求項１または２に記載の方法を実行することを特徴とする電子端末装置。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は、公開鍵暗号アルゴリズムを用いる電子構成品におけるアンチＳＰＡ（シンプルパワーアタック）モジュラべき乗演算アルゴリズムに関するものである。
【０００２】
（背景技術）
公開鍵暗号アルゴリズムの特性は周知のものである。すなわち、計算され、パラメータが使用される。唯一知られていないのはプログラムメモリに含まれている秘密鍵である。これら暗号アルゴリズムの全体セキュリティは、カードに含まれており、このカードの外部には知られていないこの秘密鍵にある。この秘密鍵は、入力に用いられたメッセージの情報や、返事として供給された符号化メッセージの情報、あるいは公開鍵の情報などから単独に推定されることは不可能である。
【０００３】
しかし、カードのマイクロプロセッサが、メッセージの署名、あるいはメッセージの解読のために暗号アルゴリズムを実行している過程にある時に、電流消費あるいは電流消費の分析に基づく外部アタックによって、悪意ある第三者がこのカードに含まれる秘密鍵を探し当てることが可能となることが明らかになった。こうしたアタックはシングルパワー分析の頭文字をとってＳＰＡアタックと呼ばれている。
【０００４】
こうしたＳＰＡアタックの原理は、命令を実行するマイクロプロセッサの電流消費が、処理されるデータに応じて変わるという事実に基づいている。
特に、マイクロプロセッサで実行される命令はビットごとにデータアイテムを処理する必要があり、このビットが“１”か“０”のいずれであるかにより、異なる２つの電流プロファイルが存在する。一般に、マイクロプロセッサが“０”を処理している場合には、この実行の瞬間に第１消費電流振幅があり、また、マイクロプロセッサが“１”を処理している場合には、第１消費電流振幅とは異なる第２消費電流振幅がある。
【０００５】
このように、ＳＰＡアタックは、処理されるビットの値に応じて命令を実行する間の、カードにおける電流消費プロファイルの違いを利用するものである。ＳＰＡアタックの実行は、単純化されたやり方として、ビットごとにデータを処理する少なくとも１つの命令の実行を含むアルゴリズムが実行される１つまたはそれ以上の特定の周期を識別し、そして、一方が“０”に等しいビット処理に相当し、他方が“１”に等しいビット処理に相当する２つの異なる電流消費プロファイルを識別することから成る。分析は、ノイズを削除するために平均化された、アルゴリズムの同一ランニングのカーブ上、またはおそらくｎカーブ上にてなされる。
【０００６】
モジュラべき乗演算は次の数式で定義される。
Ｒ＝ＸＹ  ｍｏｄ  Ｎ
ここで、Ｙはｋビットのサイズを有する指数である。
Ｎはｋ’ビットのサイズを有する法である。
Ｘはｋ”ビットのサイズを有する、既知の変数である。
Ｒはモジュラべき乗演算の結果であり、ｋ’ビットのサイズを有する。
【０００７】
以下に記載の既知の従来アルゴリズムＡあるいはＢを用いることが出来る。
上記数式の計算に使用する従来アルゴリズムＡは以下のとおりである。
Ｒは１に初期化される。すなわち、Ｒ＝１；
Ｙの２進表現は、Ｙ（ｋ−１）で示される最上位ビットから最下位ビットＹ（０）まで推移する。
ｉが（ｋ−１）から０まで変わる、各ビットＹ（ｉ）について、追加演算Ｒ＝Ｒ２が実行される。
ビットＹ（ｉ）が１に等しい場合、次の演算から成る追加のステップが実行される。すなわち、Ｒ＝Ｒ*Ｘ。
例えば、Ｙが５に等しい場合、その２進表現は１０１となる。
【０００８】
上記のアルゴリズムが適用されると、
第１ビット［Ｙ（２）＝１］について、Ｒ＝Ｒ２が実行され、その後に演算Ｒ*Ｘ＝Ｘが実行され、すなわち結果は、Ｒ＝Ｘとなる；
第２ビット［Ｙ（１）＝０］について、演算Ｒ＝Ｒ２が実行され、すなわち結果は、Ｒ＝Ｘ２となり；
第３ビット［Ｙ（０）＝１］について、演算Ｒ＝（Ｒ２）２が実行され、その後に演算Ｒ＝Ｒ*Ｘが実行され、すなわち結果は、Ｒ＝（Ｘ２）２＝Ｘ５となる。
なお、上記Ｒは常に使用される。
当然、Ｙは５に等しいという例で説明した全ての数式はＮを法として実行される。これによって、ｋ’ビットのサイズを有するレジスタｒと連動することが可能になる。
【０００９】
上記で述べた数式を計算するために使用される従来のアルゴリズムＢは以下の通りである。
Ｒは１に初期化され、ＺはＸに初期化される。すなわち、Ｒ＝１、Ｚ＝Ｘ、ここでＺは変数である。
Ｙの２進表現は、最下位ビットＹ（０）から最上位ビットＹ（ｋ−１）まで推移する。
ｉが０から（ｋ−１）まで変わる、各ビットＹ（ｉ）について、ｉが０よりも大きいとき、追加演算Ｚ＝Ｚ２が実行される。
ビットＹ（ｉ）が１に等しい場合、次の演算から成る追加のステップが実行される。すなわち、Ｒ＝Ｒ*Ｚ。
例えば、Ｙが５に等しい場合、その２進表現は１０１となる。
【００１０】
上記アルゴリズムが適用されると、
第１ビット、Ｙ（０）＝１について、演算Ｚ*は実行されず（ｉ＝０であるため）、演算Ｒ＝Ｒ*Ｚ＝Ｘが実行される。
第２ビット［Ｙ（１）］＝０について、演算Ｚ２＝Ｘ２が実行される。Ｙ（１）＝０であるため、Ｒは変わらない。
第３ビット［Ｙ（２）＝１］について、演算Ｚ＝Ｚ２＝Ｘ４が実行される。そして、Ｙ（２）が１に等しいとき、演算Ｒ＝Ｒ*Ｚもまた実行される。ゆえに、Ｘ５が求められる。
なお、上記ＲおよびＺは常に使用される。
当然、Ｙは５に等しいという例で説明したすべての数式はＮを法として実行される。これによって、ｋ’ビットのサイズを有するレジスタｒおよびｚと連動することが可能になる。
しかし、このアルゴリズムＢはさらにメモリ（ｋ’ビットのサイズを有する追加レジスタｚ）を必要とすることから、チップカードタイプの電子構成品においてはあまり使用されない。
【００１１】
上記において説明した従来のアルゴリズムＡおよびＢに関して、Ｙの各ビットに従って、ビットが０の場合には１つの演算が実行され、ビットが１の場合には２つの演算が実行されることが理解される。これらのアルゴリズムＡおよびＢはＲＳＡに使用される。なお、ＲＳＡ暗号方式は最も広く用いられている公開鍵暗号方式である。これは暗号化の方法として、あるいは署名の方法として使用可能である。ＲＳＡ暗号方式はその特定用途向けチップカードにおいて使用される。チップカードにおいてＲＳＡの使用可能な用途に、データバンクへのアクセス、バンキングアプリケーション、例えば有料テレビなどの遠隔支払いアプリケーション、ガソリン販売、あるいは高速道路料金の支払い等があげられる。もちろん、これらの用途例は全てを網羅しているわけではない。
【００１２】
ＲＳＡ暗号方式の原理は以下の通りであり、３つの異なるパートに分けることが出来る。すなわち、
１）一組のＲＳＡキーの生成
２）平文で書かれたメッセージの暗号メッセージへの暗号化
３）暗号メッセージの平文メッセージへの解読
【００１３】
ＲＳＡ暗号化演算は、演算Ｃ＝Ｍｅ  ｍｏｄ  Ｎで表されるメッセージＭｅ  ｍｏｄ  Ｎに等しい暗号ｃを計算することから成る。ここで、ｅは公開暗号指数であり、Ｎは法である。
ＲＳＡ解読演算は、解読が正確に実行され、かつ次の演算Ｍ’＝Ｃｄ  ｍｏｄ  Ｎ（ここで、ｄは秘密解読指数であり、Ｎは法である。）で表される場合、Ｍに等しいメッセージＭ’を計算することから成る。
ＲＳＡはまさにモジュラべき乗演算であることが分かる。
【００１４】
ｄはプライベートであることから、これは秘密エレメントであることが判明する。ゆえに、ｄは、本説明の初めのほうで述べたようなアルゴリズムである、従来のアルゴリズムＡまたはＢにおけるＹに相当するものであることが分かる。しかし、ＲＳＡに使用されるこれらのアルゴリズムは、発明を実施する電子構成品の電流消費を調べることにより簡単にアタックされてしまう。
【００１５】
これは、Ｓ（ＳＱＵ）で示される、「２乗演算」と呼ばれるアルゴリズムＡの演算Ｒ２およびアルゴリズムＢの演算Ｚ２の署名Ｓが、Ｓ（ＭＵＬ）で示される、「乗算演算」と呼ばれるアルゴリズムＡの演算Ｒ*ＸおよびアルゴリズムＢの演算Ｚ*Ｒの署名Ｓとは異なると考えられる場合、上記のアルゴリズムＡまたはＢを実行している間の電流消費は、直接Ｙに基づく署名Ｓ（ＳＱＵ）およびＳ（ＭＵＬ）の連続より成るためである。
【００１６】
例えば、アルゴリズムＡの場合、５に等しいＹについて、次の連続する署名がある。
［Ｓ（ＳＱＵ），Ｓ（ＭＵＬ）］，［Ｓ（ＳＱＵ）］，［Ｓ（ＳＱＵ），Ｓ（ＭＵＬ）］、ここで、［Ｓ（ＭＵＬ）］が後に続く署名［Ｓ（ＳＱＵ）］の連なりは１に等しいビットであり、［Ｓ（ＳＱＵ）］が後に続く署名［Ｓ（ＳＱＵ）］は０に等しいビットである。
Ｓ（ＳＱＵ）とＳ（ＭＵＬ）を区別する方法が分かる場合に、簡単に電流消費を調べることで、Ｙの値全体を見つけ出すことが可能となる。このアタックの方法が上記のＲＳＡに適用されると、定義上秘密としておくべき秘密解読指数であるＹ＝ｄが見つけ出されてしまうので、不適当である。
【００１７】
本発明はこの重大な欠点を取り除くことを可能にする。
しかし、本発明の創作力を明確に強調するために、依然欠点のあるアルゴリズムＡおよびアルゴリズムＢの改良例をあげることが効果的である。
従来のアルゴリズムＡまたはＢにおいて、本発明を実施する構成品は、ＭＵＬで表される演算「乗算」よりも効果的にＲ２を計算する、ＳＱＵで表される「自乗」と呼ばれる最適演算を有すると考えられる。
【００１８】
アタックに対する最初の反撃は演算ＭＵＬのみを使用することから成る。この場合、演算「乗算」の署名が残るにすぎず、値Ｙに遡ることを可能にするどんな情報も区別することがもはや出来なくなる。さらに正確に言うと、数学的演算「乗算」は２つのオペランドＶおよびＷを有しており、次の式によって定義される。
ＭＵＬ（Ｖ，Ｗ）＝Ｖ*Ｗ
理論上は１つは保護されるが、しかし実際には演算ＭＵＬ（Ｖ，Ｖ）または演算ＭＵＬ（Ｖ，Ｗ）が用いられる。ゆえに、オペランドが異なるため、電流消費の違いが依然としてある。よって、これは信頼のおける解決法とはいえない。
【００１９】
（発明の開示）
本発明は、本アルゴリズムによりモジュラべき乗演算を実行し、上記のような欠点を回避することを可能にする。
２つのレジスタＲ１およびＲ２と、結果がレジスタＲ１にあることを意味する“０”に等しいか、または結果がレジスタＲ２にあることを意味する“１”に等しいインジケータＩとが使用される。このインジケータＩにより、どちらのレジスタに正確な結果があるかを示すことが可能になる。
【００２０】
アルゴリズムＡを使用する本発明のアルゴリズムは、以下の初期設定ステップであるステップａおよびｂ、そして、ｋ回（ｋはＹのサイズである）実行される計算ステップであるステップｃ、ｄ、ｅ、およびｆにより実行されることから成り、各ステップは以下の通りである。
ａ）Ｒ１＝１に初期化する。
ｂ）Ｉ＝０に初期化する。
Ｙの２進表現のビットＹ（ｉ）ごとに“ｋ−１”から“０”について次の４つのステップｃ、ｄ、ｅ、およびｆが実行される。Ｙの２進表現は最上位ビットＹ（ｋ−１）から最下位ビットＹ（０）まで推移する。
ｃ）Ｉ＝０の場合、演算Ｒ２＝（Ｒ１）２が実行され、Ｉ＝１の場合、演算Ｒ１＝（Ｒ２）２が実行される。
ｄ）Ｉは補数をとられる。すなわち、“０”から“１”へ、または“１”から“０”へ値を変える。
ｅ）Ｉについてテスト演算が繰り返され、Ｉ＝０の場合、演算Ｒ２＝Ｒ１＊Ｘが実行され、Ｉ＝１の場合、演算Ｒ１＝Ｒ２＊Ｘが実行される。
ｆ）Ｙ（ｉ）が１に等しい場合、Ｉは補数をとられ、Ｙ（ｉ）が０に等しい場合、Ｉは不変に保たれる。
【００２１】
このように、Ｙがどのような値でも、ＳＱＵ演算およびＭＵＬ演算は常に実行される。ゆえに、ステップｄにおいて、次の２つの署名の１つが存在する。Ｓ（Ｒ２＝ＳＱＵ（Ｒ１））またはＳ（Ｒ１＝ＳＱＵ（Ｒ２））。
また、ステップｆにおいて、次の２つの署名の１つが存在する。Ｓ（Ｒ１＝ＭＵＬ（Ｒ２，Ｘ））またはＳ（Ｒ２＝ＭＵＬ（Ｒ１，Ｘ））。
ステップｃの署名は等しくなる。なぜならば、これらは同一のオペランドを用い、そして同一演算（ＳＱＵ）を実行するからである。
ステップｅの署名は等しくなる。なぜならば、これらは同一のオペランドを用い、そして同一演算（ＭＵＬ）を実行するからである。
従って、値Ｙに遡ることはもはや不可能であり、演算（ＳＱＵ）および（ＭＵＬ）の連続となる。本発明のアプリケーションは、モジュラべき乗演算アルゴリズムを必要とする公開鍵アルゴリズムを用いる電子構成品において保護された方式でモジュラべき乗演算を実行することを可能にする。
【００２２】
従来のアルゴリズムＢを用いる本発明のアルゴリズムは、初期設定ステップである以下のステップａおよびｂ、そしてｋ回（ｋはＹのサイズである）実行される以下の計算ステップｃ、ｄ、およびｅにより実行されることから成る。
ａ）Ｒ１＝１およびＺ＝Ｘに初期化し、
ｂ）Ｉ＝０に初期化する。
Ｙの２進表現のＹ（ｉ）のビットごとに、３つのステップｃ、ｄ、およびｅが実行される。ｉは“０”から“ｋ−１”まで変わり、Ｙの２進表現は最下位ビットＹ（０）から最上位ビットＹ（ｋ−１）まで推移する。
ｃ）演算Ｚ：＝Ｚ２が実行され、
ｄ）Ｉ＝０の場合、演算Ｒ２：＝Ｒ１＊Ｚが実行され、Ｉ＝１の場合、演算Ｒ２：＝Ｒ２＊Ｚが実行される。
ｅ）Ｙ（ｉ）＝０の場合、Ｉは不変に保たれ、Ｙ（ｉ）＝１の場合、Ｉは補数をとられる。
【００２３】
このように、Ｙがどのような値でも、ＳＱＵ演算およびＭＵＬ演算は常に実行される。ゆえに、ステップｃにおいて署名Ｓ（ＳＱＵ）が存在する。
ステップｄにおいて、Ｓ（Ｒ１＝ＭＵＬ（Ｒ２，Ｚ））またはＳ（Ｒ２＝ＭＵＬ（Ｒ１，Ｚ））の２つの署名の１つが存在する。ステップｄの署名は等しくなる。なぜならば、これらは同一のオペランドを用い、そして同一の演算（ＭＵＬ）を実行するからである。
【００２４】
従って、値Ｙに遡ることはもはや不可能であり、演算（ＳＱＵ）と（ＭＵＬ）の連続となる、本発明のアプリケーションは、モジュラべき乗演算アルゴリズムを必要とする公開鍵アルゴリズムを用いる電子構成品において保護方式でモジュラべき乗演算を実行することを可能にする。
本発明の例として、シュノール・アンド・エルガマル（ＳｃｈｎｏｒｒおよびＥ１  Ｇａｍａｌ）署名アルゴリズムの変形であるＤＳＡ（ディジタル署名アルゴリズム）が使用される。
【００２５】
ステップｍに署名するために、次のステップが実行される。
１）乱数ｋの生成
２）ｒ＝（ｇｋｍｏｄｐ）ｍｏｄｑの計算、ここでｇ、ｐ、およびｑはチップカードの外の世界に知られている公開整数である。
３）ｓ＝（Ｋ−１（Ｈ（ｍ）＋ｘ＊ｒ））ｍｏｄｑの計算、ここでＨ（）はチョッピング関数であり、ｘは公開鍵である。
ペア（ｒ，ｓ）はメッセージｍの署名に対応する。
Ｋは秘密であることを注記する。
ステップ２は部分的にモジュラ冪法から成る。
ｒ’＝ｇｋｍｏｄｐおよびｒ＝ｒ’ｍｏｄｑ
【００２６】
モジュラ冪法が上記のような従来のアルゴリズムＡまたはＢとともに実行される場合、ＳＰＡアタックは値ｋに遡ることを可能にしてしまう。ｋが判明し、かつ、ｓ、ｍおよびｒが分かっているので、アタッカーは秘密鍵ｘを計算することが可能となる。こうして、アタッカーは署名の鍵を見つけ出し、システムは破壊される。ゆえに、本例のステップ２のモジュラ冪法を実行するために、本発明あるいは本発明の別形態を用いることが望ましい。
【００２７】
このように、本発明においては、アルゴリズムを計算する方法が、電流消費を調べることでｋを見つけ出すことを不可能にするため、アタッカーは秘密鍵ｘの値に遡ることができない。