(57)【要約】本発明は、ｑ＝ａ ｄｉｖ ｂというタイプの整数除算および／またはｒ＝ａ ｍｏｄ ｂというタイプのモジュラ換算を実行するための暗号化方法である。ここで、ｑは商であり、ａはｍビットの数であり、ｂはｎビットの数であり、ｎはｍより小さく、ｂｎ−１はヌルでなく、数ｂの最上位ビットである。本発明は、整数除算および／またはモジュラ換算を行う前に数ａが乱数ρによりマスクされることを特徴とする。本発明は、また、上記方法を実施するための電子構成要素に関する。本発明は、隠れたチャネル攻撃、特に差分攻撃に対して安全なスマート・カードを作成するために使用することができる。【特許請求の範囲】
【請求項１】
ｑ＝ａ ｄｉｖ ｂというタイプの整数除算および／またはｒ＝ａ ｍｏｄ ｂというタイプのモジュラ換算を実行する暗号化方法であって、ｑは商、ａはｍビットの数、ｂはｎビットの数、ｎはｍより小さいかまたは等しい数、ｂｎ−１はゼロでなく、前記数ｂの最上位ビットであり、前記数ａが前記整数除算および／または前記モジュラ換算を行う前に乱数ρによりマスクされることを特徴とする暗号化方法。
【請求項２】
前記数ａをマスクするために、前記乱数ρをｂ倍したもの（ａ＜−ａ＋ｂ＊ρ）が前記数ａに加算されることを特徴とする請求項１に記載の方法。
【請求項３】
整数除算を実行した後で、前記乱数ρによる影響が前記整数除算の結果から除去されることを特徴とする請求項１または２に記載の方法。
【請求項４】
前記乱数ρによる影響を除去するために、前記乱数ρが前記整数除算の結果から差し引かれることを特徴とする請求項２と結合している請求項３に記載の方法。
【請求項５】
前記乱数ρが前記方法の実施の度に修正されることを特徴とする請求項１乃至４のいずれかに記載の方法。
【請求項６】
前記乱数ρが、前記方法の所定の実施回数の後で修正されることを特徴とする請求項１乃至４のいずれかに記載の方法。
【請求項７】
請求項１乃至６のいずれかに記載の方法を実施するための手段を備える電子構成要素であって、前記プログラムされた計算手段が、数ａおよびｂを記憶するための特定のいくつかのレジスタを備えることを特徴とする電子構成要素。
【請求項８】
請求項７に記載の構成要素を備えるチップ・カード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、カバート・チャネル攻撃、特に差分攻撃に対する安全な整数除算またはモジュラ換算方法に関する。本発明は、例えば秘密鍵または公開鍵暗号化方法など、より一般的な暗号化方法で除算を行うために使用することができる。このような暗号化方法は、例えば、チップ・カードのような電子デバイスで実施することができる。
【背景技術】
【０００２】
暗号化方法のセキュリティは、機密データまたは暗号化方法が操作する機密データから入手したデータを秘匿状態に維持する機能に依存する。
悪意のあるユーザは、おそらく暗号化方法を実行している計算デバイスが実行した処理動作の際に含まれ、また操作した特定の機密データを発見しようとして攻撃を行うこともあり得る。
【０００３】
最もよく知られている攻撃としては、単純または差分カバート・チャネル攻撃等がある。カバート・チャネル攻撃という用語は、デバイスの外部から測定することができる物理量に基づく攻撃を意味し、その直接分析（単純攻撃）または統計的方法による分析（差分攻撃）により、デバイスで行われた処理演算中に操作されたデータを発見することができる。Ｐａｕｌ Ｋｏｃｈｅｒが、特にこれらの攻撃について開示している（「暗号学における進歩−ＣＲＹＰＴＯ’９９」（Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ − ＣＲＹＰＴＯ'９９）、コンピュータ科学（Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ）における講義ノート、第１６６６巻、３８８乃至３９７ページ、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、１９９９年）。
【０００４】
これらの目的のために使用することができる物理量としては、実行時間、消費電流、計算を実行するために使用した構成要素の一部が発生する電磁場等がある。ある方法の実行中には、ビットの操作、すなわち特定の命令によるその処理は、このビットの値により、および／または命令により、当該物理量上に特定の痕跡を残す。すなわち、この方法を実行している構成要素が残した痕跡（すなわち、当該物理量の経過時間中の変化）は、１に等しいビットが操作されているのか、０に等しいビットが操作されているのかにより異なる。カバート・チャネル攻撃は、暗号化方法のこの弱点に基づくものである。
【０００５】
基本演算としてＹ＝ＸＤ（ここで、Ｘ，ＹおよびＤは整数である）というタイプのモジュラ累乗演算を使用する暗号化方法は、過去数年間の間に非常に幅広く研究されてきた。これらの研究としては、ＲＳＡ法、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎによる鍵交換またはＤＳＡ署名法等がある。カバート・チャネル攻撃からこれらの方法を保護するという点で有意の進歩があった。
【０００６】
一方、基本演算として、ｑ＝ａ ｄｉｖ ｂおよびｒ＝ａ ｍｏｄ ｂ（ここで、ａおよびｂは２つのオペランドであり、ｑおよびｒは、それぞれｂによるａの整数除算の商と余りである）というタイプの整数除算を使用する安全な暗号化方法の作成については何の研究も行われなかった。ａおよび／またはｂは、例えば、この方法の鍵の要素である秘密データである。例えば、Ｂａｒｒｅｔｔの方法（Ｐ．Ｂａｒｒｅｔの、「標準デジタル信号処理上でのＲＳＡ公開鍵暗号化アルゴリズムの実施」（Ｉｍｐｌｅｍｅｎｔｉｎｇ ｔｈｅ ＲＳＡ ｐｕｂｌｉｃ ｋｅｙ ｅｎｃｒｙｐｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｎ ａ ｓｔａｎｄａｒｄ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ）、コンピュータ科学（Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ）における講義ノート、第２６３巻、３１１乃至３２３ページ、Ｓｐｒｉｎｇｅｒ Ｖｅｒｌａｇ、１９８７年）、Ｑｕｉｓｑｕａｔｅｒの方法（１９９２年１１月出願の米国特許第５，１６６，９７８号）または中国人剰余定理により実施したＲＳＡ法（Ｊ．Ｊ．ＱｕｉｓｑｕａｔｅｒおよびＣ．Ｃｏｕｖｒｅｕｒの、「ＲＳＡ公開鍵暗号化システム用の高速解読アルゴリズム」（Ｆａｓｔ ｄｅｃｉｐｈｅｒｍｅｎｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ＲＳＡ ｐｕｂｌｉｃ ｋｅｙ ｃｒｙｐｔｏｓｙｓｔｅｍ）、Ｅｌｅｃｔｒｏｎｉｃｓ Ｌｅｔｔｅｒ、第１８巻、９９、９０５乃至９０７ページ、１９８２年１０月）が、整数除算を基本演算として使用している暗号化方法である。
【０００７】
整数除算法および／またはモジュラ換算法を使用するこのような暗号化方法は、下記の例に示すようにカバート・チャネル攻撃に弱い。
整数除算およびモジュラ換算の両方を使用する周知の方法は、いわゆる「紙／鉛筆」方法である。この方法は、実際に、手でこのような演算を行う場合に使用する方法を反復する。この方法については以下に説明する。
【０００８】
２つのデータ項目、すなわち、ｍビットのａ＝（ａｍ−１，．．．，ａ０）およびｎビットのｂ＝（ｂｎ−１，．．．，ｂ０）であり、ｎがｍより小さいかまたは等しく、ｂｎ−１ γ ０の場合には、いわゆる「紙／鉛筆」除算法は、商、すなわちｑ＝ａ ｄｉｖ ｂおよび余り、すなわちｒ＝ａ ｄｉｖ ｂを計算する。この目的のために、この方法は、ｎビットの整数ｂにより、ｎ＋１ビットの整数Ａを数回連続的に除算する。実際には、０［Ａ／ｂ＜２にならなければならず、ｂｎ−１ γ ０の場合にはこのようになる。
【０００９】
余りｒは、ｎビット以下の数である。何故なら、ｒ＜ｂであるからである。この部分に対する商ｑは、ｍ−ｎ＋１ビット以下の数である。何故なら、ｑ＝ａ ｄｉｖ ｂ［ａ ｄｉｖ （ｂｎ−１＊２ｎ−１）＝ａ ｄｉｖ ２ｎ−１＝（ａｍ−１，．．．， ａｎ−１）であるからであり、何故なら、ｂ μ ｂｎ−１＊２ｎ−１および（ａｍ−１，．．．， ａｎ−１）は、ｍ−ｎ＋１ビットの数であるからである。この除算法の最後に、商ｑは、最初に、数ａを含んでいるレジスタのｍ−ｎ＋１の最下位ビットに記憶される。余りｒの最上位ビットは、計算中にけた上げとして使用された１−ビット・レジスタに記憶され、余りｒのｎ−１の最下位ビットは、最初に数字ａを含んでいるレジスタのｎ−１の最上位ビット内に記憶される。
【００１０】
この作業は基数２で行われるので、整数除算Ａ ｄｉｖ ｂの商ビットは、２つの可能な値、すなわち０または１しか有することができない。それ故、演算Ａ ｄｉｖ ｂを行う簡単な方法は、Ａからｂを引き、次に結果を試験する方法である。Ａ−ｂの結果が正の数であれば、Ａ ｄｉｖ ｂ＝１であり、Ａ−ｂの結果が狭義に負の数である場合には、Ａ ｄｉｖ ｂ＝０である。
【００１１】
それ故、完全な除算方法は下記のように表すことができる。
入力：ａ＝（０，ａｍ−１，．．．，ａ０）
ｂ＝（ｂｎ−１，．．．，ｂ０）
出力：ｑ＝ａ ｄｉｖ ｂ およびｒ＝ａ ｍｏｄ ｂ
Ａ＝（０，ａｍ−１，．．．，ａｍ−ｎ＋１）
Ｆｏｒ ｊ＝１ ｔｏ （ｍ−ｎ＋１），ｄｏ：
ａ＜−ＳＨＬｍ−１（ａ，１）；σ＜−ｃａｒｒｙ
Ａ＜−ＳＵＢｎ（Ａ，ｂ）；σ＜−σ ＯＲ ｃａｒｒｙ
ｉｆ （¬σ＝ＴＲＵＥ） ｔｈｅｎ Ａ＜−ＡＤＤｎ（Ａ，ｂ）
ｉｆ ｎｏｔ ｌｓｂ（ａ）＝１
Ｅｎｄ Ｆｏｒ
【００１２】
方法１
この方法の場合、および下記の説明全体を通して下記の表記方法を使用する。
正確な言い方ではないが、特に分かりやすくするために、明示していない限り、レジスタおよびその内容を示すために同じ名前を使用する。それ故、レジスタＡは、データ項目Ａを含むレジスタを表すために使用する。
記号「＜−」および表記ｙ＜−ｘは、レジスタｘの内容をレジスタｙにロードするのを示すために使用する。レジスタｙの内容もｙと呼ばれる。
Ａは、最初にデータ項目ａを含んでいるレジスタのｎ個の最上位ビットの内容に対応するｎ個のビットの語である。Ａは、もちろん、最初にａを含んでいるレジスタのように、反復の度に修正される。
σは、減算がうまくいったのかいかなかったのか（すなわち、商ビットは０または１に等しいかどうか）を示す。
¬σは変数σの１に対する補数（否定とも呼ばれる）である。真は、ある例の場合には１に等しい定数である。
ｌｓｂ（ａ）は、数ａの最下位加重ビットであり、ａの最下位ビットとも呼ばれる。
【００１３】
ＳＨＬｍ＋１（ａ，１）は、データ項目ａを含んでいるｍ＋１ビットのレジスタ内での１ビットだけ左へのシフトである。レジスタから出るこのビットは、可変けた上げ内に記憶され、０に等しいビットは、最初にデータａを含んでいるレジスタの最下位ビットとして入力される。
ＡＤＤｎ（Ａ，ｂ）は、語Ａのｎ個のビットへの数ｂのｎ個のビットの加算である。演算ＳＨＬｎ（ａ，１）は、演算ＡＤＤｎ（ａ，ａ）に等しいことが分かるだろう。もちろん、加算ＡＤＤｎ（ａ，ｂ）は、適当な加算回路で、Ａおよびｂをそれぞれ含んでいる２つのレジスタの内容を加算することにより行われる。
ＳＵＢｎ（Ａ，ｂ）は、語Ａからの数ｂの減算である。もちろん、減算ＳＵＢｎ（Ａ，ｂ）は、適当な回路で、語Ａを含んでいるレジスタの内容から、データ項目ｂを含んでいるレジスタの内容を引くことにより行われる。
【００１４】
要するに、方法１は下記のステップを実行する。
・ａ＜−ＳＨＬｍ＋１（ａ，１）によりけた上げ（σ＝ｃａｒｒｙ＝１）が生じた場合には、ａｍ＝１（シフト前）およびそれ故そのｂをＡから引かなければならないことを意味する。
・ａｍ＝０（シフト前）であり、Ａ＜−ＳＵＢｎ（Ａ，ｂ）によりけた上げ（ｃａｒｒｙ＝１）が生じた場合には、減算の前はＡ−ｂ μ ０であり、それ故、ｂをＡから引かなければならないことを意味する。
・ａ＜−ＳＨＬｍ＋１（ａ，１）がけた上げを生じないで、またＡ＜−ＳＵＢｎ（Ａ，ｂ）もけた上げを生じない場合（すなわち、σを更新した後で、σが偽である場合）、または¬σが真である場合には、減算を行う前、Ａ−ｂ＜０であり、それ故、ｂをＡから引く必要がないことを意味する。この場合には、この方法は、Ａの値を復元するために加算演算Ａ＜−ＡＤＤｎ（Ａ，ｂ）を実行する。
【００１５】
方法１は、カバート・チャネル攻撃に弱い。何故なら、方法１の場合には、反復の度に、σの値により、すなわち現在の反復中に入手する商ビットの値により、加算ＡＤＤｎ（Ａ，ｂ）またはそのデータａを含むレジスタの最下位ビットの１への設定が行われるからである。これら２つの演算の使用方法および持続時間は異なっていて、その実施中に残す痕跡も異なる。それ故、１回の反復中に残す全痕跡は、上記反復中に入手した結果ビットにより異なる。例えば、完全な方法を実行した場合に構成要素が残した痕跡を測定し、研究することにより、ビット毎に結果ビットの値を決定することができる。
【００１６】
方法１を使用すれば、整数除算の結果（ｑ＝ａ ｄｉｖ ｂ）およびモジュラ換算の結果である、整数除算の余り（ｒ＝ａ ｍｏｄ ｂ）の両方を入手することができる。同じ欠点を持つ他の周知の方法は、モジュラ除算だけ、またはモジュラ換算だけを行う。通常、除算方法は、かなりモジュラ換算法に似ている。
【特許文献１】米国特許第５，１６６，９７８号
【非特許文献１】Ｐａｕｌ Ｋｏｃｈｅｒの、「暗号学における進歩−ＣＲＹＰＴＯ’９９」（Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ − ＣＲＹＰＴＯ'９９）、コンピュータ科学（Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ）における講義ノート、１６６６巻、３８８乃至３９７ページ、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、１９９９年
【非特許文献２】Ｊ．Ｊ．ＱｕｉｓｑｕａｔｅｒおよびＣ．Ｃｏｕｖｒｅｕｒの、「ＲＳＡ公開鍵暗号化システム用の高速解読アルゴリズム」（Ｆａｓｔ ｄｅｃｉｐｈｅｒｍｅｎｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ＲＳＡ ｐｕｂｌｉｃ ｋｅｙ ｃｒｙｐｔｏｓｙｓｔｅｍ）、Ｅｌｅｃｔｒｏｎｉｃｓ Ｌｅｔｔｅｒ、第１８巻、９９、９０５乃至９０７ページ、１９８２年１０月
【非特許文献３】Ｐ．Ｂａｒｒｅｔの、「標準デジタル信号処理上でのＲＳＡ公開鍵暗号化アルゴリズムの実施」（Ｉｍｐｌｅｍｅｎｔｉｎｇ ｔｈｅ ＲＳＡ ｐｕｂｌｉｃ ｋｅｙ ｅｎｃｒｙｐｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｎ ａ ｓｔａｎｄａｒｄ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ）、コンピュータ科学（Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ）における講義ノート、第２６３巻、３１１乃至３２３ページ、Ｓｐｒｉｎｇｅｒ Ｖｅｒｌａｇ、１９８７年
【発明の開示】
【発明が解決しようとする課題】
【００１７】
本発明の１つの目的は、除算および／またはモジュラ換算を実施する方法を攻撃から安全なものにすることである。
【課題を解決するための手段】
【００１８】
この目的のために、本発明は、ｑ＝ａ ｄｉｖ ｂというタイプの整数除算および／またはｒ＝ａ ｍｏｄ ｂというタイプのモジュラ換算を実行する暗号化方法を提案する。ここで、ｑは商であり、ａはｍビットの数であり、ｂはｎビットの数であり、ｎはｍより小さいかまたは等しく、ｂｎ−１はゼロでなく、数ｂの最上位ビットである。
【００１９】
本発明によれば、上記方法は、整数除算および／またはモジュラ換算を実行する前に乱数ρにより数ａがマスクされることを特徴とする。
乱数によりマスクされている数ａ、この方法の実行中に残った痕跡（例えば、消費エネルギー）は実行毎に異なる。そのため、差分カバート・チャネル攻撃をもはや行うことはできない。
【００２０】
本発明は、例えば、除算とモジュラ換算の両方を行う方法１に適用することができる。もっと一般的に、本発明は、これらの演算の一方または他方を実行する任意の方法に適用することができる。
乱数ρは、この方法の実行毎に修正することができ、または単にこの方法の所定の回数の実行の後で修正することができる。適用できる場合には、上記の予め定義した数は、好適には、例えば、３２乃至６４ビットの間のある数のような比較的小さな数にすることが好ましい。
【発明を実施するための最良の形態】
【００２１】
本発明の好ましい実施形態によれば、数ａをマスクするために、数ａに加算が行われ、乱数がｂ倍される（ａ＜−ａ＋ｂ＊ρ）。この目的のために、具体的に説明すると、レジスタｂの内容に乱数ρが掛けられ、次に、数ａに加算が行われ、加算の結果が最初に数ａを含んでいるレジスタに記憶される。
その後で、次に必要な整数除算および／またはモジュラ換算が行われる。
【００２２】
整数除算を行う場合には、ａ＋ｂ＊ρの形にマスクされた数ａにより行った整数除算の結果は、ａ ｄｉｖ ｂ＋ρに等しい。この場合、整数除算の後で、数ａに対する整数除算の予想された結果、すなわちａ ｄｉｖ ｂを発見するために、乱数ρによる影響が整数除算の結果から除去される。
モジュラ換算を行う場合には、この演算（ａ＋ｂ＊ρ）ｍｏｄ ｂの結果はａ ｍｏｄ ｂ、数ａに対するモジュラ換算の予想した結果に等しい。
【００２３】
本発明は、また、すでに説明した本発明による方法を実施するための手段を備える電子構成要素に関する。プログラムされた計算手段は、特に数ａおよびｂを記憶するためのいくつかのレジスタを備える。
最後に、本発明は、上記特性を有する構成要素を備えたチップ・カードに関する。
【国際調査報告】
2006509261.tif 000002
2006509261.tif 000003
2006509261.tif 000004
2006509261.tif 000005