(57)【要約】本発明は暗号文Ｃに基づく平文Ｍを決定し、秘密鍵ｄを用いる方法に関し、秘密鍵ｄは２値形式として使用し平文Ｍは、対応するビットｄｉ のための各繰り返しステップiにおいて決定し、セこれと並列的にキュリティ変数Ｍｎ を決定し、この後、検証変数ｘを秘密鍵ｄのビットに準拠する（ビットコンパチブル）指数によって決定する。
2009532973.tif 000002
【特許請求の範囲】
【請求項１】
暗号文Ｃに基づいて平文Ｍを決定し、また秘密鍵を使う方法において、秘密鍵ｄを２値形式として使用し、また、平文Ｍを対応するビットｄｉ に対して各繰り返しステップｉで決定するのと並列的に、、セキュリティ変数Ｍｎ を決定し、、この後、検証変数ｘを秘密鍵ｄのビット準拠指数によって決定することを特徴とする方法。
【請求項２】
請求項１に記載の方法において、平文を指数（ｍｏｄ Ｎ）によって決定することを特徴とする方法。
【請求項３】
請求項１または２に記載の方法において、平文を決定するために乗算／２乗のアルゴリズムを使用することを特徴とする方法。
【請求項４】
請求項１〜３のうちいずれか一項に記載の方法において、平文を決定するために加算／２倍のアルゴリズムを用いることを特徴とする方法。
【請求項５】
請求項１〜３のうちいずれか一項に記載の方法において、平文を決定するために、ｄｉ ＝１に対して、Ｍ＝ｘ＊Ｍ ｍｏｄ Ｎを計算することを特徴とする方法。
【請求項６】
請求項５に記載の方法において、ｄｉ ＝０に対して、無効な乗算としてＭｎ＝Ｍｎ＊ｘ ｍｏｄ Ｎを計算することを特徴とする方法。
【請求項７】
以前の請求項１，２または４のいずれか一項に記載の方法において、平文を決定するために、ｄｉ ＝１に対してＭ＝ｘ＋Ｍを計算することを特徴とする方法。
【請求項８】
請求項５に記載の方法において、ｄｉ ＝０に対して無効な加算としてＭｎ＝ｘ＋Ｍｎを計算することを特徴とする方法。
【請求項９】
請求項１〜８のうちいずれか一項に記載の方法において、検証目的のために、Ｍ＊Ｍｎ ｍｏｄ Ｎ＝ｘを計算することを特徴とする方法。
【請求項１０】
請求項１〜９のうちいずれか一項に記載の方法において、検証目的のために、Ｍ＋Ｍｎ＝ｘを計算することを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号文に基づいて平文を決定する方法に関する。
【背景技術】
【０００２】
この種の方法は、たとえばＲＳＡ方法によって既知である。ＲＳＡ方法において、平文は公開鍵によって暗号化され、この暗号文は関連する秘密鍵によって再び解読することができる。暗号化されたデータは、通常極めて高い極秘性を有するにもかかわらず、公的にアクセスできるので、秘密鍵を探り出すことを目的として暗号化データは頻繁に攻撃を受け、復号解読データを悪用しようとして、暗号化されたデータが復号解読され、望んではいないのに決定されてしまう。
【０００３】
この種の攻撃はタイミング攻撃または差動故障解析（ＤＦＡ）攻撃として知られるようになったものであり、この種の方法の間に使われる秘密鍵を決定するために、操作中に計算に要する時間または実行時間または誤挙動を観測する。
【０００４】
このことから、逆ＲＳＡ関数、または第２ＲＳＡ計算による、相当多い計算量を用いてこのような操作を確認し、それら操作を無効化しようと試みる方法が創生されてきた。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、暗号文に基づいて平文を決定する方法を提供することにあり、タイミング攻撃および差動故障解析攻撃に影響を受けず、しかもそれに付随する付加的な労力が比較的少なくて済む方法を得るにある。
【０００６】
この目的は、暗号文Ｃに基づいて平文Ｍを決定し、また秘密鍵ｄを使用する本発明方法によって達成され、秘密鍵ｄを２値形式として使用し、平文Ｍを対応するビットｄｉ に対して各繰返しステップｉで決定するのと並列的にセキュリティ変数Ｍｎ を決定し、この後、検証変数ｘを秘密鍵ｄのビット準拠指数によって決定する。
【０００７】
都合のよい更なる発展形が、従属請求項に記載されている。
本発明を、以下に図面に示した実施例につき説明するが、しかし、本発明はこれに限定するものではない。
【実施例】
【０００８】
今日、暗号および復号の方法は極めて広く普及している。これは、極秘情報が極めて頻繁に使われ、またこれが公的にアクセス可能な方法により送信されていることによる。従来技術に基づくこのような暗号およびこれに付随する復号の実施を、以下にＲｉｖｅｓｔ、ＳｈａｍｉｒおよびＡｄｌｅｍａｎによるいわゆるＲＳＡ方法につき説明する。ＲＳＡ方法において、第１に、平文Ｍを、公開鍵ｇを使用して暗号文Ｃ、すなわち秘密テキストを形成するよう暗号化する。つぎに、この暗号化された暗号文Ｃを公開または送信することができる。これは、暗号文Ｃが秘密鍵ｄなしでは解読できないからである。平文Ｍの算出は、秘密鍵dを使用している暗号文Ｃのモジュラ累乗法（ｍｏｄ  Ｎ）によって行う。図１は、Ｍ=Ｃｄ ｍｏｄ ＮのＲＳＡ方法に基づく復号化を示す線図的説明図を示す。このため、図１は、ＲＳＡ復号を表すブロック２を示す。使用する入力変数は暗号文Ｃおよび秘密鍵ｄであり、その結果として、平文Ｍが得られる。
【０００９】
次式（数１）の方程式の実施は、一般的に、いわゆる「乗算および２乗」のアルゴリズムによって行う。この場合、秘密鍵ｄは、長さＬを有する２値形式で使用する。
【数１】
2009532973.tif 000003
この形式を用いる場合、結果は次式のような積の連鎖である。
【数２】
2009532973.tif 000004
もしｘi＝Ｃ２ｉであるとき、
【数３】
2009532973.tif 000005
であり、この中で変化し得るｘｉは以下のように反復して算出することができる。
【数４】
2009532973.tif 000006
「乗算および２乗」アルゴリズムは以下の擬似コードとして得られる。
Ｍ＝１；ｘ＝Ｃ；
ｆｏｒ  i＝０ｔｏＬ−１
ｉｆ  ｄ＝＝１
Ｍ＝Ｍ＊ｘ ｍｏｄ Ｎ
ｅｎｄ  ｉｆ
ｘ＝ｓｑｕａｒｅ（ｘ） ｍｏｄ Ｎ
ｅｎｄｆｏｒ
【００１０】
図２は、モジュラ累乗法の関連する手順１０をブロック図として示す。
【００１１】
この方法はブロック１１でスタートし、そして、ブロック１２で、この方法は、Ｍ＝１、ｘ＝Ｃおよびi＝０という値で初期化する。ブロック１３において、秘密鍵ｄのビットｄｉ が１に等しいか否かをチェックする。もし等しければ、この方法は、ブロック１４に続く。もしそうでなければ、この方法は、ブロック１５に続く。ブロック１４において、Ｍ＝ｘ＊Ｍ  ｍｏｄ Ｎを計算する。つぎに、この方法はまた、ブロック１５に続く。ブロック１５において、ｘ＝ｘ２ｍｏｄ Ｎを決定する。この後ブロック１６において、i＝Ｌ−１であるか否かをチェックする。もしそうであれば、この方法は、ブロック１８で終了する。もしそうでなければ、i＝i＋１をブロック１７で設定し、そして、方法は再びブロック１３に続く。Ｌサイクルは、各々の場合において秘密鍵ｄの一つのビットｄi が処理される毎に、実行する。
【００１２】
ＲＳＡ方法へのタイミング攻撃は、１９９８年に紹介された。これらの攻撃において、秘密鍵ｄは、それぞれのサイクルにおいて異なる実行時間または演算時間から導かれる。もしｄi ＝１であれば、ブロック１４における乗算が行われ、すなわち実行時間が長くなる。もしｄi＝０であれば、ブロック１４における乗算は行われず、結果として実行時間は短くなる。各サイクルの実行時間または演算時間の検出は、例えば電流消費量を評価する、またはＰＣアプリケーションのキャッシュ動作を記録する、または部品の電磁放射を測定することによって行う。
【００１３】
そのような、時間の関数としてのチップカード・マイクロコントローラの電流消費量は、図３において例として示され、これらのタイミング攻撃の動作モードを簡単に例示する。図３は時間の関数として、異なる電流消費量の領域を示す。そこにおいて、低い電流消費量の領域は２つの典型的幅、すなわち継続期間を有する。第１の領域２０は２乗の領域を示し、ここにおいてｘ＝ｘ２  ｍｏｄ Ｎが決定され、同時に領域２１は乗算の領域を示し、ここにおいてＭ＝ｘ＊ｍｏｄ Ｎが計算される。図２の方法に従う最後の計算は、部分ｄｉ＝１である場合のみであるので、そのとき現在のケースにおいてｄｉ は１と等しくてはならない。この後に領域２２、２３および２４が続き、ここにおいて乗算は実行されず、そのことからｄｉは０に等しくてはならない。このように、ｄｉ ＝０であるかまたはｄｉ ＝１であるかは、比較的簡単な方法で見破ることが出来る。ｄｉに対応する値を図３の最下行に示す。このように、「乗算」および「２乗」の実行時間の違いにより、電流曲線に基づいてそれぞれの鍵の一部ｄｉ を見破ることが可能である。これらの攻撃を予防するために、ｄｉ ＝０のとき、同一だが意味を成さない乗算を常に行い、これによりｄｉ ＝０またはｄｉ ＝１の時に一定になる、いわゆる「常に乗算および２乗」方法を利用する。したがって、付随する擬似コードは以下の様になる。
Ｍ＝１；ｘ＝Ｃ；
ｆｏｒ  i＝０ｔｏＬ−１
ｉｆ  ｄ＝＝１
Ｍ＝＝Ｍ＊ｘ ｍｏｄ Ｎ
ｅｌｓｅ
Ｍ＊ｘ ｍｏｄ Ｎ
ｅｎｄ  ｉｆ
ｘ＝ｓｑｕａｒｅ（ｘ） ｍｏｄ Ｎ
ｅｎｄｆｏｒ
【００１４】
図４は、この改良されたＲＳＡ方法を示すためのブロック図３０である。この方法はブロック３１でスタートし、ブロック３２でこの方法は対応するスタート値によって初期化する。ブロック３３において、ｄｉ ＝１であるか否かをチェックする。もしそうであれば、この方法はブロック３４に続く。もしそうでなければ、この方法はブロック３５に続く。ブロック３４において、Ｍ＝ｘ＊Ｍ ｍｏｄ Ｎを計算する。ブロック３５において、ｘ＊Ｍ ｍｏｄ Ｎを、いわゆる無効な乗算として実行する。この方法は、それからブロック３６に続き、そこにおいて、ｘ＝ｘ２ ｍｏｄ Ｎを決定する。その後ブロック３７において、i＝Ｌ−１であるか否かをチェックする。もしそうであれば、この方法はブロック３９で終了する。もしそうでなければ、ブロック３８においてｉ＝i＋１をセットし、方法は再びブロック３３に続く。Ｌサイクルは、各々の場合において秘密鍵ｄの一つのビットｄi が処理される毎に実行する。
【００１５】
改良されたＲＳＡ方法が実装された後、他のこのアルゴリズムへの攻撃、いわゆる差動故障解析（ＤＦＡ）攻撃が公知となった。それによれば、個々のサイクル中における乗算を、例えば光、電磁パルス、電源パルス等の物理的な影響により攪乱する。乗算の攪乱がその結果にいかなる影響を及ぼさない場合、関連するサイクルは上記の通りに無効な乗算を実行する。これに対応する秘密鍵の一つのビットｄｉは、ｄｉ＝０となる。しかし、この攪乱が結果を変える場合、その秘密鍵のビットは、したがってｄｉ ＝１である。もしこの方法が、このようにサイクル毎に攻撃されれば、秘密鍵ｄの全てを決定することができる。
【００１６】
この種の攻撃を予防するために、暗号の算出は、通常、Ｃ＝Ｍｅ による公開鍵ｅを使った逆ＲＳＡ関数、または第２のＲＳＡ計算によって検証する。第１の場合において、公開鍵ｅはシステムにおいて既知でなければならない。第２の場合においては、計算に要する時間は２倍になる。
【００１７】
上述のＤＦＡ攻撃から防御するための本発明による方法は、チェックサムによって、指数方程式Ｍ＝Ｃｅ の計算の検証を提供する。この場合、図４の方法に示される無効な乗算を利用する方法を実行する。図５によると、この目的で、ｄの２値形式での補完的な指数の暗号文Ｍｎを、無効な乗算が行われている間に計算する。図５で示す本発明による方法は、Ｍｎを算出することによって、「常に乗算および２乗」方法の検証を提供する。
【００１８】
図５は、ＤＦＡ攻撃に関して改善されたこの方法を示すためのブロック図４０である。この方法はブロック４１でスタートし、ブロック４２において、方法はスタート値で初期化する。ブロック４３において、ｄｉ ＝１であるか否かをチェックする。もしそうであれば、この方法はブロック４４に続く。もしそうでなければ、この方法はブロック４５に続く。ブロック４４において、Ｍ＝ｘ＊Ｍ ｍｏｄ Ｎを計算し、ブロック４５において、Ｍｎ＝ｘ＊Ｍｎ ｍｏｄ Ｎを計算する。この後、この方法は、それからブロック４６に続き、ｘ＝ｘ２ ｍｏｄ Ｎを決定する。つぎにブロック４７において、i＝Ｌ−１であるか否かをチェックする。もしそうであれば、この方法はブロック４９において終了する。もしそうでなければ、ブロック４８においてｉ＝i＋１を設定し、方法は再びブロック４３に続く。ブロック４９において、計算Ｃ＊Ｍ＊Ｍｎ ｍｏｄ Ｎ＝ｘか否かを、検証ブロック５３の一部としてチェックする。方程式が満たされる場合、計算が攪乱されていないことがブロック５１において認識され、対応する信号を返す。しかし、方程式が満たされない場合、計算が攪乱されたことがブロック５０において認識され、該当するエラー信号を返す。この方法は、ブロック５２において終了する。Ｌサイクルは、各々の場合において秘密鍵ｄの一つのビットｄi が処理される毎に実行する。
【００１９】
図５に基づいて、無効な乗算の間に計算Ｍｎ＝ｘ＊Ｍｎ ｍｏｄ Ｎを行う場合、次式が最後のサイクルの終わりに求める。
【数５】
2009532973.tif 000007
だだし、秘密鍵ｄの補集合
2009532973.tif 000008
は、次式の方程式で置換しなくてはならない。すなわち、
【数６】
2009532973.tif 000009
これは次式を与える。
【数７】
2009532973.tif 000010
もし、次式の積
【数８】
2009532973.tif 000011
を算出する場合、結果ｙを直接、補助変数ｘと比較することができる。それはサイクルＬ後にｘは同一の値、すなわち、
【数９】
2009532973.tif 000012
をとる。いわゆるＤＦＡ攻撃によるいかなる攪乱も、このように、ｘが計算結果ｙに等しくないことを引き起こす。
【００２０】
典型的な１０２４ビットＲＳＡ、すなわち１０２４回の乗算と１０２４回の２乗において、２回の乗算と１回の比較を行うことにおいては、この検証のための労力は小さい。
【００２１】
ＭｎをＣで初期化する場合、この計算はより有利である。これにより、最後のサイクル後におけるＣによる乗算の必要がなくなる。さらに、初期化後にＣを保存する必要がないことから、必要メモリは減じる。この種の方法を図６に示す。そこにおいて、累乗の前にＭｎ＝Ｃの初期化をすることにより、最適化が実行される。
【００２２】
図６は、ＤＦＡ攻撃に関して改善され、最適化されたこの方法を例示するためのブロック図６０である。この方法はブロック６１でスタートし、そしてブロック６２において、Ｍｎ ＝Ｃを含むスタート値によりこの方法を初期化する。ブロック６３において、ｄｉ ＝１であるか否かをチェックする。もしそうであれば、この方法はブロック６４に続く。もしそうでなければ、この方法はブロック６５に続く。ブロック６４において、Ｍ＝ｘ＊Ｍ ｍｏｄ Ｎを計算し、ブロック６５において、Ｍｎ＝ｘ＊Ｍｎ ｍｏｄ Ｎを計算する。この方法はそれからブロック６６に続き、ｘ＝ｘ２ ｍｏｄ Ｎを決定する。その後ブロック６７において、i＝Ｌ−１であるか否かをチェックする。もしそうであれば、この方法はブロック６９で終了する。もしそうでなければ、ブロック６８においてi＝i＋１をセットし、この方法は再びブロック６３に続く。ブロック６９において、検証ブロック７３の一部として計算Ｍ＊Ｍｎ ｍｏｄ Ｎ＝ｘか否かをチェックする。方程式が満たされる場合、ブロック７１において計算が攪乱されていないことが認識され、対応する信号を返す。しかし、方程式が満たされない場合、ブロック７０において計算が攪乱されていることが認識され、該当するエラー信号を返す。この方法は、ブロック７２において終了する。
【００２３】
しかし、本発明によれば、上述の方法は、他の方法または一般的な算術的構造、例えば「常に乗算および２乗」方法の処理に応用することができる。図７は、ＤＦＡ攻撃に関して改善されまた最適化された、対応する「常に乗算および２乗」方法、例えばＥＣＣまたはＨＥＣＣ方法などの方法を示すブロック図８０である。ＥＣＣ方法は、楕円カーブ暗号法の方法であり、ＨＥＣＣ方法は超楕円カーブ暗号法（hyperelliptical）である。この方法はブロック８１でスタートし、ブロック８２において、方法はスタート値で初期化する。ブロック８３において、ｄｉ ＝１であるか否かをチェックする。もしそうであれば、この方法はブロック８４に続く。もしそうでなければ、この方法はブロック８５に続く。ブロック８４において、Ｍ＝ｘ＋Ｍを計算する。ブロック８５において、Ｍｎ ＝ｘ＋Ｍｎを計算する。この方法はそれからブロック８６に続き、そこにおいて、ｘ＝２＊ｘを決定する。その後ブロック８７において、i＝Ｌ−１であるか否かをチェックする。もしそうであれば、この方法はブロック８９において終了する。もしそうでなければ、ブロック８８においてｉ＝i＋１をセットし、方法は再びブロック８３に続く。ブロック８９において、計算Ｍ＋Ｍｎ＝ｘか否かが、検証ブロック９３の一部としてチェックされる。方程式が満たされる場合、計算が攪乱されていないことがブロック９１において認識され、相当する信号を返す。しかし、方程式が満たされない場合、計算が攪乱されたことがブロック９０において認識され、相当するエラー信号を返す。この方法を、ブロック９２で終了する。
【００２４】
この検証方法は、一般の算術的集団（mathematical groups）に関してもまた用いることができる。（Ｇ，＋，Ｏ）を、Ｇ、中立要素Ｏ、および集団リンカー「＋」を含む集団とする。集団要素Ｐのｎ重の加算はｎ＊Ｐと表し、とくに、０＊Ｐ＝０、および（−ｎ）＊Ｐ＝ｎ＊（−Ｐ）とし、だだし「−Ｐ」はＰの逆要素とする。タイミング攻撃に対して、ビット長Ｌを有する、随意的でありしかも秘密のスカラー係数ｄ≧０を使用してｄ＊Ｐの演算を防御するために、「常に乗算および２乗」アルゴリズムは、「常に加算および２倍」アルゴリズムと同じように実行することができる。ＤＦＡ攻撃に対する上述の防御もまた、類似した方法で変換することができ、補助変数ｙは、終わりに次式のように算出される。
【数１０】
2009532973.tif 000013
その場合、ＤＦＡ攻撃が行われたのは、補助変数ｘに関して、ｘ≠ｙのときでありそのときのみ行われたことになる。
【図面の簡単な説明】
【００２５】
【図１】図１は、ＲＳＡ方法の線図的説明図である。
【図２】図２は、ＲＳＡ方法のブロック図である。
【図３】図３は、タイミング攻撃の説明図である。
【図４】図４は、「常に乗算および２乗」方法のブロック図を示す。
【図５】図５は、本発明による検証方法のブロック図である。
【図６】図６は、本発明による検証方法のブロック図である。
【図７】図７は、本発明による検証方法のブロック図である。
【符号の説明】
【００２６】
１  線図的説明図
２  線図的説明図１のブロック
１０  モジュラ累乗法の手順を示すブロック図
１１  ブロック図１０のブロック
１２  ブロック図１０のブロック
１３  ブロック図１０のブロック
１４  ブロック図１０のブロック 
１５  ブロック図１０のブロック
１６  ブロック図１０のブロック
１７  ブロック図１０のブロック
１８  ブロック図１０のブロック
２０  領域
２１  領域
２２  領域
２３  領域
２４  領域
３０  ブロック図
３１  ブロック図３０のブロック
３２  ブロック図３０のブロック
３３  ブロック図３０のブロック
３４  ブロック図３０のブロック
３５  ブロック図３０のブロック
３６  ブロック図３０のブロック
３７  ブロック図３０のブロック
３８  ブロック図３０のブロック
４０  ブロック図
４１  ブロック図４０のブロック 
４２  ブロック図４０のブロック
４３  ブロック図４０のブロック
４４  ブロック図４０のブロック
４５  ブロック図４０のブロック
４６  ブロック図４０のブロック
４７  ブロック図４０のブロック
４８  ブロック図４０のブロック
４９  ブロック図４０のブロック
５０  ブロック図４０のブロック
５１  ブロック図４０のブロック
５２  ブロック図４０のブロック
５３  ブロック図４０の検証ブロック
６０  ブロック図
６１  ブロック図６０のブロック
６２  ブロック図６０のブロック
６３  ブロック図６０のブロック
６４  ブロック図６０のブロック
６５  ブロック図６０のブロック
６６  ブロック図６０のブロック
６７  ブロック図６０のブロック
６８  ブロック図６０のブロック
６９  ブロック図６０のブロック
７０  ブロック図６０のブロック
７１  ブロック図６０のブロック
７２  ブロック図６０のブロック
７３  ブロック図６０のブロック
８０  ブロック図
８１  ブロック図８０のブロック
８２  ブロック図８０のブロック
８３  ブロック図８０のブロック
８４  ブロック図８０のブロック
８５  ブロック図８０のブロック
８６  ブロック図８０のブロック
８７  ブロック図８０のブロック
８８  ブロック図８０のブロック
８９  ブロック図８０のブロック
９０  ブロック図８０のブロック
９１  ブロック図８０のブロック
９２  ブロック図８０のブロック
９３  ブロック図８０の検証ブロック
【図１】
2009532973.tif 000014
【図２】
2009532973.tif 000015
【図３】
2009532973.tif 000016
【図４】
2009532973.tif 000017
【図５】
2009532973.tif 000018
【図６】
2009532973.tif 000019
【図７】
2009532973.tif 000020
【国際調査報告】
2009532973.tif 000021
2009532973.tif 000022
2009532973.tif 000023