(57)【要約】  本発明は、侵入型攻撃に対して冪剰余ｘ＝ｍＤｍｏｄＮの計算を保護する方法および電子装置に関する。本発明は、メッセージｍにマスクを適用すること、および冪剰余が実行された後に、マスクによって導入された特性のおかげで累乗が変更されなかったことを認証することを含む。【特許請求の範囲】
【請求項１】
侵入型攻撃に対して、ｍをメッセージ、Ｄを指数、Ｎを係数とする冪剰余ｘ＝ｍＤｍｏｄＮの計算を保護する方法であって、整数ｋが与えられ、ＲおよびＮが互いに素となるように整数Ｒが与えられたとき、
ａ．α＝１ｍｏｄＮ、α＝０ｍｏｄＲ、β＝０ｍｏｄＮ、およびβ＝１ｍｏｄＲとなるようにマスクαおよびマスクβを生成するステップと、
ｂ．マスクされたメッセージｍ’＝（ｍ＊α＋ｋ＊β）ｍｏｄ（Ｎ＊Ｒ）を計算することによって、マスクαおよびβでメッセージｍをマスクするステップと、
ｃ．冪剰余ｘ’＝ｍ’Ｄｍｏｄ（Ｎ＊Ｒ）を計算するステップと、
ｄ．（ｘ’−ｋＤ）ｍｏｄＲ＝０の場合、ｘ＝ｘ’ｍｏｄＮを出力するか、そうでなければ解決策を適用するステップと、を含むことを特徴とする、方法。
【請求項２】
整数ｋがゼロに等しく、マスクβを計算しないことによって方法が簡素化され、したがって、
ａ．α＝１ｍｏｄＮおよびα＝０ｍｏｄＲとなるようにマスクαを生成するステップと、
ｂ．マスクされたメッセージｍ’＝（ｍ＊α）ｍｏｄ（Ｎ＊Ｒ）を計算することによって、マスクαでメッセージｍをマスクするステップと、
ｃ．冪剰余ｘ’＝ｍ’Ｄｍｏｄ（Ｎ＊Ｒ）を計算するステップと、
ｄ．ｘ’ｍｏｄＲ＝０の場合、ｘ＝ｘ’ｍｏｄＮを出力するか、そうでなければ解決策を適用するステップと、を含む、請求項１に記載の方法。
【請求項３】
αが公式α＝（１−Ｎ＊（（１／Ｎ）ｍｏｄＲ）ｍｏｄ（Ｎ＊Ｒ）で計算される、請求項１または２に記載の方法。
【請求項４】
βが公式β＝（Ｎ＊（（１／Ｎ）ｍｏｄＲ））ｍｏｄ（Ｎ＊Ｒ）で計算される、請求項１、または請求項１による請求項３に記載の方法。
【請求項５】
冪剰余ｘ’＝ｍ’Ｄｍｏｄ（Ｎ＊Ｒ）の実行の前および／または後にｍ＝ｍ’ｍｏｄＮが認証され、そうでない場合には解決策が適用される、請求項１から４のいずれか一項に記載の方法。
【請求項６】
解決策（複数可）が、必要な冪剰余の結果をまったく出力しないステップを含む、請求項１から５のいずれか一項に記載の方法。
【請求項７】
Ｒが乱数である、請求項１から６のいずれか一項に記載の方法。
【請求項８】
各冪剰余に対して新しい乱数Ｒが生成される、請求項７に記載の方法。
【請求項９】
１より大きい整数ｉが与えられると、数Ｒは、Ｒ＝ｒｉとなるように数ｒをｉ乗することによって得られ、整数ｋは値ｋ＝１＋ｒに設定される、請求項２を除く請求項１から８のいずれか一項に記載の方法。
【請求項１０】
方法によって実行されるいくつかまたは全ての冪剰余に数Ｒおよび整数ｋが再利用され、マスクαおよびβが、値ｋＤｍｏｄＲと同様に、全ての前記冪剰余のために一度予備計算される、請求項１、３、４、５、６、７、または８に従属しない場合の９のいずれか一項による方法。
【請求項１１】
ｍをメッセージ、Ｄを指数、Ｎを係数とする冪剰余ｘ＝ｍＤｍｏｄＮを計算するように配置された電子装置であって、侵入型攻撃に対して冪剰余を保護するために、
ａ．α＝１ｍｏｄＮ、α＝０ｍｏｄＲ、β＝０ｍｏｄＮ、およびβ＝１ｍｏｄＲとなるようにマスクαおよびマスクβを生成する手段と、
ｂ．マスクされたメッセージｍ’＝（ｍ＊α＋ｋ＊β）ｍｏｄ（Ｎ＊Ｒ）を計算することによって、マスクαおよびβでメッセージｍをマスクする手段と、
ｃ．冪剰余ｘ’＝ｍ’Ｄｍｏｄ（Ｎ＊Ｒ）を計算する手段と、
ｄ．（ｘ’−ｋＤ）ｍｏｄＲ＝０か否かを判定する手段であって、
この条件が確認された場合には、ｘ＝ｘ’ｍｏｄＮを出力し、
そうでなければ、解決策を適用する手段を含み、ＲとＮとが互いに素となるように整数ｋおよび整数Ｒが与えられることを特徴とする、電子装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｂｅｌｌｃｏｒｅ攻撃などの侵入型攻撃に対して冪剰余の実行を保護する方法に関する。本発明はまた、そのような方法を実装する電子装置、特にスマートカードにも関する。
【背景技術】
【０００２】
本発明は、より具体的には、ＲＳＡ−ＣＲＴシステムのコンテキストで使用される冪剰余の保護に関する。ＲＳＡは、１９７７年にＲｉｖｅｓｔ、Ｓｈａｍｉｒ、およびＡｄｌｅｍａｎによって導入された（直接的モードのＲＳＡを記載している「Ｒｉｖｅｓｔ，Ｒ．Ｌ．，Ｓｈａｍｉｒ，Ａ．，Ａｄｅｌｍａｎ，Ｌ．Ｍ．：Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  ｏｂｔａｉｎｉｎｇ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  ｐｕｂｌｉｃ−ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ．Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＭＩＴ／ＬＣＳ／ＴＭ−８２（１９７７）」を参照）。ＲＳＡの使用は、非常に広まっている（通常、ウェブサイトに安全に接続するとき、バンクカードを使用するときなどはいつもＲＳＡを使用している）。
【０００３】
いわゆる直接モードにおいて、（Ｎ，ｅ）はＲＳＡ公開鍵および（Ｎ，ｄ）はＲＳＡ秘密鍵であって、Ｎ＝ｐ＊ｑとなり、ここでｐおよびｑは大きい素数整数、ｇｃｄ（（ｐ−１），ｅ）＝ｇｃｄ（（ｑ−１），ｅ）＝１、およびｄ＝ｅ−１ｍｏｄ（（ｐ−１）＊（ｑ−１））である。メッセージｍ＜ＮのＲＳＡ署名は、Ｓ＝ｍｄｍｏｄＮによって与えられる。
【０００４】
暗号化対応アーキテクチャの計算能力が向上するにつれて、ＲＳＡ鍵サイズは時間超過するほど膨れあがっている。２Ｋ−ＲＳＡ（２０４８ビット鍵を使用するＲＳＡ）が、現在では標準的な機能である。プロセッサが通常はほとんどＲＡＭメモリを持たず、数メガヘルツのクロック周波数で動作する組み込み装置にとって、これは強い制約である。ＲＳＡは、直接的モードよりも中国の剰余定理モードにおいて、より有効である。ＲＳＡ−ＣＲＴドメインは、ＲＳＡ公開鍵（Ｎ，ｅ）およびＲＳＡ秘密鍵（ｐ，ｑ，ｄｐ，ｄｑ，ｉｑ）からなり、ここでＮ＝ｐ＊ｑ、ｐおよびｑは大きい素数整数、ｇｃｄ（（ｐ−１），ｅ）＝ｇｃｄ（（ｑ−１），ｅ）＝１、ｄｐ＝ｅ−１ｍｏｄ（ｐ−１）、ｄｑ＝ｅ−１ｍｏｄ（ｑ−１）、およびｉｑ＝ｑ−１ｍｏｄｐである。ＲＳＡ係数サイズの半分のデータを扱うので、ＣＲＴを利用するＲＳＡは、理論的には約４倍の速度であり、したがって組み込み機器により適している。ＣＲＴモードでのＲＳＡ署名の単純なＣＲＴ実装は、図１に記載されている。
【０００５】
ハードウェア機器上の侵入型攻撃は通常、装置の予想される挙動を中断すること、および影響を受けやすいデータを推測するために異常動作させることからなる。このような攻撃は、９０年代後半に導入された。これらにより、通常は安全であると考えられているスマートカード、ＨＳＭなどの暗号装置に保存された鍵素材を攻撃者に回復させることができるので、これらは深刻な問題である。これにより、攻撃者は正当なユーザになりすますことができる（たとえばユーザの口座から金融取引を行う、ユーザの電話回線を使用する、ユーザの名義で違法行為を行うなど）。侵入型攻撃の負担を伴わずに、純粋なソフトウェア手段でコンピュータを破壊する、より簡単な方法が通常はたくさんあるので、過去にはこのような攻撃は、パーソナルコンピュータにとって深刻であるとは考えられていなかった。しかしながら、増加する詐欺のため、およびＴＰＭ（信頼済みプラットフォームモジュール、その仕様はＴｒｕｓｔｅｄ  Ｃｏｍｐｕｔｉｎｇ  Ｇｒｏｕｐによって管理される）などの部品の登場により、これが変化することができた。ＴＰＭは、可能性のある全ての製品の分類（ＰＤＡ、プリンタ、携帯電話など）に安全な暗号機能を導入するように意図され、特に企業向けＰＣで、またあらゆる種類の電子装置でも、ますます一般的になっている。そのため侵入型攻撃は、今や暗号装置または安全性の高いコンピュータ（たとえば高感度のサーバ）のみならず、以前よりもはるかに多くの装置にとって脅威となっている。ハードウェア製造者の技術的対応が展開されるにつれ、新たなハードウェア解決策が定期的に追加されている。しかしながら、これらは有効なソフトウェア対策が組み込まれている場合にのみ有効となり得ることは、広く信じられている。攻撃者がハードウェアを完全に手中に収めたとき、組み込み機器はこの種の攻撃に特に曝される。侵入型攻撃の典型的な例は、１つの偽署名に与えられたＲＳＡ秘密鍵を攻撃者に回復させる、当初のＢｅｌｌｃｏｒｅ攻撃である。
【０００６】
Ｂｅｌｌｃｏｒｅ攻撃は、１９９６年にＢｅｌｌｃｏｒｅ  Ｉｎｓｔｉｔｕｔｅによって導入された差分故障攻撃である。これは、「Ｂｏｎｅｈ，Ｄ．，Ｄｅｍｉｌｌｏ，Ｒ．Ａ．，Ｌｉｐｔｏｎ，Ｒ．Ｊ．：Ｏｎ  ｔｈｅ  ｉｍｐｏｒｔａｎｃｅ  ｏｆ  ｃｈｅｃｋｉｎｇ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  ｆａｕｌｔｓ．Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  １２３３（１９９７）３７〜５１」に記載されている。組み込みプラットフォーム上では、攻撃者は装置に完全にアクセスできるので、この攻撃は、通常は「容易」だと考えられる。Ｓｐ＝ｍｄｐｍｏｄｐまたはＳｑ＝ｍｄｑｍｏｄｑのいずれかの計算（図１に示されるステップ）の中断は、電圧グリッチ、レーザー、または温度変化などの方法で実現されることが可能である。一旦正確な中断が得られると攻撃は成功し、攻撃者は単一のｇｃｄ計算でＲＳＡ素因数を回復することができるようになる。実際、構造的に、Ｓ＝Ｓｑ＋ｑ＊（ｉｑ＊（Ｓｐ−Ｓｑ）ｍｏｄｐ）＝Ｓｐ＋ｐ＊（ｉｐ＊（Ｓｑ−Ｓｐ）ｍｏｄｑ）である。正しい署名Ｓおよび偽の署名Ｓ’に注目すると、ここでＳｐまたはＳｑのいずれか（ただし両方ではない）は同じ入力メッセージに対して不正であるが、ｇｃｄ（Ｓ−Ｓ’，Ｎ）はｑまたはｐのいずれかである。Ｂｅｌｌｃｏｒｅ攻撃の標準的な改善は、「Ｊｏｙｅ，Ｍ．，Ｌｅｎｓｔｒａ，Ａ．Ｋ．，Ｑｕｉｓｑｕａｔｅｒ，Ｊ．Ｊ．：Ｃｈｉｎｅｓｅ  ｒｅｍａｉｎｄｅｒｉｎｇ  ｂａｓｅｄ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ  ｉｎ  ｔｈｅ  ｐｒｅｓｅｎｃｅ  ｏｆ  ｆａｕｌｔｓ．Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ：ｔｈｅ  ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ａｓｓｏｃｉａｔｉｏｎ  ｆｏｒ  Ｃｒｙｐｔｏｌｏｇｉｃ  Ｒｅｓｅａｒｃｈ  １２（４）（１９９９）２４１〜２４５」に記載されており、ｐまたはｑとなるｇｃｄ（（Ｓ’ｅ−ｍ）ｍｏｄＮ，Ｎ）を計算することによって、本物の署名がなくてもＮの因数分解を回復できるようにする。このように、ＲＳＡ秘密要素ｐおよびｑが回復され、その結果、ＲＳＡ−ＣＲＴ秘密鍵全体が回復される。
【０００７】
Ｂｅｌｌｃｏｒｅによって導入されたような故障攻撃は、たとえばＲＳＡ署名の目的などで、冪剰余を実装する暗号製品にとって、やはり大きな脅威である。公開指数が知られると、出力する前に署名を認証することができ、それによってＢｅｌｌｃｏｒｅ攻撃を防止する。しかしながら、ほとんどの場合は組み込み機器上で、公開指数は知られておらず、故障攻撃への耐性を複雑な問題にしている。
【０００８】
Ｂｅｌｌｃｏｒｅ攻撃の発見以来、研究団体によって解決策が提案されてきた。１９９７年には、Ｓｈａｍｉｒが、ＣＲＴモードでＲＳＡ署名生成を実行している時に秘密指数ｄが知られると仮定して、洗練された解決策を提案した（ＥＵＲＯＣＲＹＰＴ’９７のランプセッションでも発表された、１９９９年１１月の米国特許第５，９９１，４１５号明細書、「Ｓｈａｍｉｒ，Ａ．：Ｍｅｔｈｏｄ  ａｎｄ  ａｐｐａｒａｔｕｓ  ｆｏｒ  ｐｒｏｔｅｃｔｉｎｇ  ｐｕｂｌｉｃ  ｋｅｙ  ｓｃｈｅｍｅｓ  ｆｒｏｍ  ｔｉｍｉｎｇ  ａｎｄ  ｆａｕｌｔ  ａｔｔａｃｋｓ」に記載）。しかしながら実際には、このパラメータはほとんど利用できない。ＲＳＡのＣＲＴ安全実装も提案された：
２００２年、Ａｕｍｕｌｌｅｒらによる（Ａｕｍｕｌｌｅｒ，Ｃ．，Ｂｉｅｒ，Ｐ．，Ｆｉｓｃｈｅｒ，Ｗ．，Ｈｏｆｒｅｉｔｅｒ，Ｐ．，Ｓｅｉｆｅｒｔ，Ｊ．Ｐ．：Ｆａｕｌｔ  ａｔｔａｃｋｓ  ｏｎ  ｒｓａ  ｗｉｔｈ  ｃｒｔ：Ｃｏｎｃｒｅｔｅ  ｒｅｓｕｌｔｓ  ａｎｄ  ｐｒａｃｔｉｃａｌ  ｃｏｕｎｔｅｒｍｅａｓｕｒｅｓ．Ｉｎ  Ｂ．Ｓ．Ｋａｌｉｓｋｉ  Ｊｒ．，ｃ．Ｋ．，Ｐａａｒ，Ｃ．，ｅｄｓ：Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ−ＣＨＥＳ  ２００２．Ｖｏｌｕｍｅ  ２５２３  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ．（２００２）２６０〜２７５）
２００３年、Ｂｌｏｍｅｒらによる（Ｂｌｏｍｅｒ，Ｊ．，Ｏｔｔｏ，Ｍ．，Ｓｅｉｆｅｒｔ，Ｊ．Ｐ．：Ａ  ｎｅｗ  ｃｒｔ−ｒｓａ  ａｌｇｏｒｉｔｈｍ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ｂｅｌｌｃｏｒｅ  ａｔｔａｃｋｓ．Ｉｎ：ＣＣＳ’０３：Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １０ｔｈ  ＡＣＭ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｓｅｃｕｒｉｔｙ，Ｎｅｗ  Ｙｏｒｋ，ＮＹ，ＵＳＡ，ＡＣＭ（２００３）３１１〜３２０）、
２００５年、ＪｏｙｅおよびＣｉｅｔによる（Ｊｏｙｅ，Ｍ．，Ｃｉｅｔ，Ｍ．：Ｐｒａｃｔｉｃａｌ  ｆａｕｌｔ  ｃｏｕｎｔｅｒｍｅａｓｕｒｅｓ  ｆｏｒ  ｃｈｉｎｅｓｅ  ｒｅｍａｉｎｄｅｒｉｎｇ  ｂａｓｅｄ  ｒｓａ．Ｉｎ  Ｂｒｅｖｅｇｌｉｅｒｉ，Ｌ．，Ｋｏｒｅｎ，Ｉ．，ｅｄｓ．：２ｎｄ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｆａｕｌｔ  Ｄｉａｇｎｏｓｉｓ  ａｎｄ  Ｔｏｌｅｒａｎｃｅ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ−ＦＤＴＣ  ２００５．（２００５））
２００５年、Ｇｉｒａｕｄによる（Ｇｉｒａｕｄ，Ｃ：Ｆａｕｌｔ  ｒｅｓｉｓｔａｎｔ  ｒｓａ  ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｉｎ  Ｂｒｅｖｅｇｌｉｅｒｉ，Ｌ．，Ｋｏｒｅｎ，Ｉ．，ｅｄｓ．：２ｎｄ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｆａｕｌｔ  Ｄｉａｇｎｏｓｉｓ  ａｎｄ  Ｔｏｌｅｒａｎｃｅ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ−ＦＤＴＣ  ２００５．（２００５）１４２〜１５１）、および
２００７年、ＫｉｍおよびＱｕｉｓｑｕａｔｅｒによる（Ｋｉｍ，Ｃ．Ｈ．，Ｑｕｉｓｑｕａｔｅｒ，Ｊ．Ｊ．：Ｈｏｗ  ｃａｎ  ｗｅ  ｏｖｅｒｃｏｍｅ  ｂｏｔｈ  ｓｉｄｅ  ｃｈａｎｎｅｌ  ａｎａｌｙｓｉｓ  ａｎｄ  ｆａｕｌｔ  ａｔｔａｃｋｓ  ｏｎ  ｒｓａ−ｃｒｔ？  Ｉｎ  Ｂｒｅｖｅｇｌｉｅｒｉ，Ｌ．，Ｇｕｅｒｏｎ，Ｓ．，Ｋｏｒｅｎ，Ｉ．，Ｎａｃｃａｃｈｅ，Ｄ．，Ｓｅｉｆｅｒｔ，Ｊ．Ｐ．，ｅｄｓ．：ＦＤＴＣ．（２００７）２１〜２９）
【０００９】
これらの解決策は、後により詳細に説明される。これらの解決策は全て、実行時間、メモリ消費量、または個人化管理制約のいずれかに対して、劇的な影響を有する。
【００１０】
Ｂｅｌｌｃｏｒｅ攻撃の発見の１年後にＳｈａｍｉｒによって提案された、洗練された解決策は、
【００１１】
【数１】
2011530093.tif 000002
および
【００１２】
【数２】
2011530093.tif 000003
を個別に計算すること、かつ
【００１３】
【数３】
2011530093.tif 000004
か否かを試験することによって
【００１４】
【数４】
2011530093.tif 000005
および
【００１５】
【数５】
2011530093.tif 000006
の整合性を確認することからなる。より効率的な変形は、ｒ素数を選択し、ｄモジュロ（ｐ−１）（ｒ−１）および（ｑ−１）（ｒ−１）を減少させるようにする。しかしながら、鍵素材は通常はＣＲＴフォーマットのみで与えられるので、ＣＲＴモードでＲＳＡ署名生成を実行しながら、ＲＳＡ直接的モード秘密指数ｄを要求することは、資源制約のある装置にとって、通常は非実用的である（後にさらにわかるとおりである）。このパラメータｄは、ほとんどの場合は知られておらず、各制約装置のためにｄを個人化することは許容されないことが多く、ｄはｐ、ｑ、ｄｐ、およびｄｑから計算されるが、しかしながら、通常はこれを保存するのに使用可能な鍵コンテナがないので、ｄの計算は、各ＲＳＡ署名に必須となる。この結果、（ｐ−１）モジュロ（ｑ−１）を反転する必要が出てくるため、不当な実行時間オーバーヘッドとなるが、これは具体的にはＪｏｙｅ，Ｍ．，Ｐａｉｌｌｉｅｒ，Ｐ．：Ｇｃｄ−ｆｒｅｅ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｃｏｍｐｕｔｉｎｇ  ｍｏｄｕｌａｒ  ｉｎｖｅｒｓｅｓ．Ｉｎ  Ｂ．Ｓ．Ｋａｌｉｓｋｉ  Ｊｒ．，ｃ．Ｋ．，Ｐａａｒ，Ｃ．，ｅｄｓ．：ＣＨＥＳ．（２００３）２４３〜２５３に記載されているとおりである。さらに、再結合中にｉｑに故障を注入することはｇｄｃ攻撃を許すので、ＣＲＴ再結合はまったく保護されない。
【００１６】
再結合の保護を含むＳｈａｍｉｒの方法のその他の改善は、後に提案された。一例として、上記の参考文献の中で、Ａｕｍｕｌｌｅｒらは２００２年にＣＲＴ再結合も保護する慎重な実装を提案した。Ａｕｍｕｌｌｅｒらは、オイラーのトーティエント関数の評価が自明な、小さい素数を使用する。一方では、この解決策は良好な性能を与える。他方では、無作為の素数の選択が現実の不都合を構成する。Ｓｈａｍｉｒの方法とは対照的に、ｄｐおよびｄｑのみ（ｄではなく）が必要とされる。アルゴリズムは、図２に全て記載されている。提案は、パラメータｔが素数である方法の効率的な変形を使用する。したがって、解決法は良好な性能を与える。ＲＳＡの単純なＣＲＴ実装と比較すると、わずか２つの付加的な累乗モジュロｔおよびわずかなモジュラー簡約（ｒｅｄｕｃｔｉｏｎｓ）のみが必要とされる。しかしこの解決法は、無作為の素数が選択される方法に関連する大きな欠点がある。これが固定されていたり、固定表から無作為に選択されたりすると、この素数が回復された場合、新たな弱点を表す可能性がある。装置ごとに異なれば、これは個人化管理に影響を与える。各署名に対して無作為に生成される場合には、許容不可能な減速を招く。
【００１７】
Ｓｈａｍｉｒの方法の一般化と伝染計算とを組み合わせた、その他の解決法が提案された。この組合せの主旨は、偽の署名Ｓ’、すなわちＳ’≠ＳｍｏｄｐおよびＳ’≠Ｓｍｏｄｑにおいてｇｃｄ攻撃が不可能となるように、故障が誘発されたらすぐに署名Ｓを感染させることからなる。この考えは、２００１年にＹｅｎ、Ｋｉｍ、Ｌｉｍ、およびＭｏｏｎによって導入された（Ｙｅｎ，Ｓ．Ｍ．，Ｋｉｍ，Ｓ．，Ｌｉｍ，Ｓ．，Ｍｏｏｎ，Ｓ．：Ｒｓａ  ｓｐｅｅｄｕｐ  ｗｉｔｈ  ｒｅｓｉｄｕｅ  ｎｕｍｂｅｒ  ｓｙｓｔｅｍ  ｉｍｍｕｎｅ  ａｇａｉｎｓｔ  ｈａｒｄｗａｒｅ  ｆａｕｌｔ  ｃｒｙｐｔａｎａｌｙｓｉｓ．Ｉｎ：ＩＣＩＳＣ’０１：Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  Ｓｅｏｕｌｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｃｒｙｐｔｏｌｏｇｙ，Ｌｏｎｄｏｎ，ＵＫ，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ（２００２）３９７〜４１３）。後に、Ｂｌｏｍｅｒ、Ｏｔｔｏ、およびＳｅｉｆｅｒｔが、２００３年に（既に上述された）伝染計算に基づく解決策を提案した。残念ながら、Ｓｈａｍｉｒの当初の方法については、ｄの利用可能性を必要とする。さらに、解決策に要するいくつかのパラメータｔ１およびｔ２は、かなり強力な特性を満たす必要がある：必要とされる特性の中でも、ｇｃｄ（ｔ１，ｔ２）＝ｇｃｄ（ｄ，φ（ｔ１））＝ｇｃｄ（ｄ，φ（ｔ２））＝１でなければならず、ここでφはオイラーのトーティエント関数を表す。ｔ１およびｔ２は通常は、ＲＳＡ鍵、および鍵の寿命を通じて使用される同じ値とともに一度だけ生成されるべきであるが、しかしｔ１およびｔ２は一般的に、強力な個人化制約のあるコンテキストに保存されることはできない。したがって、各署名におけるｔ１およびｔ２の生成は、無視できない。Ａｕｍｕｌｌｅｒらの解決策と比較すると、ＢＯＳアルゴリズムは、ｔ１およびｔ２の生成、ｔ１およびｔ２のトーティエント関数φの２つの評価、および２つの反転を必要とする。これは、簡潔さおよび実行時間の観点から、重要な欠点を構成する。
【００１８】
ＪｏｙｅおよびＣｉｅｔは、伝染計算に基づく洗練された解決策を打ち出した（上記参考文献を参照）。Ａｕｍｕｌｌｅｒらの解決策と比較すると、２つの乱数ｔ１およびｔ２についてφ（ｔ１）およびφ（ｔ２）を計算するだけでよいので、彼らによるＳｈａｍｉｒの方法の一般化は、ＢＯＳよりも効率的である。しかしながら、これらはｔ１およびｔ２の完全な因数分解を示唆しているので、評価は無視できないものである。結果として、ＪｏｙｅおよびＣｉｅｔの解決策は、実行時間の観点から満足のいくものではない。
【００１９】
２００７年に、ＫｉｍおよびＱｕｉｓｑｕａｔｅｒは、Ｓｈａｍｉｒの方法および伝染計算の組合せにも基づいて、ＲＳＡ無効化故障攻撃および全ての知られているサイドチャネル攻撃のＣＲＴ実装を提案した（上記参考文献を参照）。しかしながら、各署名で彼らが提案した方式は、１つの反転モジュロＮか、またはサイズ｜Ｎ｜の３つの異常にフォーマットされたパラメータを更新および保存することのいずれかを必要とする。残念ながら、そのようなパラメータの鍵コンテナは、典型的な資源制約のある装置の不揮発性メモリにおいては一般的に入手可能なものはなく、したがって、パラメータは一般的に毎回計算されなくてはならず、この解決法は、実行時間の観点からほとんど許容できなくなってしまう。
【００２０】
２００５年には、Ｇｉｒａｕｄが、故障攻撃に対してＣＲＴでＲＳＡを保護する有効な方法を提案した（上記参考文献を参照）。彼の解決策は、モンゴメリ−ラダー累乗法アルゴリズムの特性に基づいており、これは具体的には、Ｊｏｙｅ，Ｍ．，Ｙｅｎ，Ｓ．：Ｔｈｅ  ｍｏｎｔｇｏｍｅｒｙ  ｐｏｗｅｒｉｎｇ  ｌａｄｄｅｒ．Ｉｎ  Ｂ．Ｓ．Ｋａｌｉｓｋｉ  Ｊｒ．，ｃ．Ｋ．，Ｐａａｒ，Ｃ，ｅｄｓ．：Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ−ＣＨＥＳ  ２００２．Ｖｏｌｕｍｅ  ２５２３  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ．（２００２）２９１〜３０２に記載されている。この累乗法アルゴリズムを使用して、Ｇｉｒａｕｄは、
【００２１】
【数６】
2011530093.tif 000007
および
【００２２】
【数７】
2011530093.tif 000008
を連続して計算することを提案している。モンゴメリ−ラダーアルゴリズムは、故障が誘発されるとすぐに両方の結果を感染させる。２つの再結合値Ｓおよび
【００２３】
【数８】
2011530093.tif 000009
が計算され、最終認証Ｓ＝ｍＳ’がなされる。この解決法は、ＳＰＡが安全でもある。残念ながら、Ｓの計算中にＲＡＭにｍ、Ｓｐ、Ｓｑ、
【００２４】
【数９】
2011530093.tif 000010
および
【００２５】
【数１０】
2011530093.tif 000011
を保存する必要があるので、メモリ消費量が明らかに大きすぎる。大きなＲＳＡ鍵サイズでは、この解決策は、資源が限定された携帯用装置においてはほとんど実現不可能と思われる。
【先行技術文献】
【特許文献】
【００２６】
【特許文献１】米国特許第５，９９１，４１５号明細書
【非特許文献】
【００２７】
【非特許文献１】Ｒｉｖｅｓｔ，Ｒ．Ｌ．，Ｓｈａｍｉｒ，Ａ．，Ａｄｅｌｍａｎ，Ｌ．Ｍ．：Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  ｏｂｔａｉｎｉｎｇ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  ｐｕｂｌｉｃ−ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ．Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＭＩＴ／ＬＣＳ／ＴＭ−８２（１９７７）
【非特許文献２】Ｂｏｎｅｈ，Ｄ．，Ｄｅｍｉｌｌｏ，Ｒ．Ａ．，Ｌｉｐｔｏｎ，Ｒ．Ｊ．：Ｏｎ  ｔｈｅ  ｉｍｐｏｒｔａｎｃｅ  ｏｆ  ｃｈｅｃｋｉｎｇ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  ｆａｕｌｔｓ．Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  １２３３（１９９７）３７〜５１
【非特許文献３】Ｊｏｙｅ，Ｍ．，Ｌｅｎｓｔｒａ，Ａ．Ｋ．，Ｑｕｉｓｑｕａｔｅｒ，Ｊ．Ｊ．：Ｃｈｉｎｅｓｅ  ｒｅｍａｉｎｄｅｒｉｎｇ  ｂａｓｅｄ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ  ｉｎ  ｔｈｅ  ｐｒｅｓｅｎｃｅ  ｏｆ  ｆａｕｌｔｓ．Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ：ｔｈｅ  ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ａｓｓｏｃｉａｔｉｏｎ  ｆｏｒ  Ｃｒｙｐｔｏｌｏｇｉｃ  Ｒｅｓｅａｒｃｈ  １２（４）（１９９９）２４１〜２４５
【非特許文献４】Ａｕｍｕｌｌｅｒ，Ｃ．，Ｂｉｅｒ，Ｐ．，Ｆｉｓｃｈｅｒ，Ｗ．，Ｈｏｆｒｅｉｔｅｒ，Ｐ．，Ｓｅｉｆｅｒｔ，Ｊ．Ｐ．：Ｆａｕｌｔ  ａｔｔａｃｋｓ  ｏｎ  ｒｓａ  ｗｉｔｈ  ｃｒｔ：Ｃｏｎｃｒｅｔｅ  ｒｅｓｕｌｔｓ  ａｎｄ  ｐｒａｃｔｉｃａｌ  ｃｏｕｎｔｅｒｍｅａｓｕｒｅｓ．Ｉｎ  Ｂ．Ｓ．Ｋａｌｉｓｋｉ  Ｊｒ．，ｃ．Ｋ．，Ｐａａｒ，Ｃ．，ｅｄｓ：Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ−ＣＨＥＳ  ２００２．Ｖｏｌｕｍｅ  ２５２３  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ．（２００２）２６０〜２７５
【非特許文献５】Ｂｌｏｍｅｒ，Ｊ．，Ｏｔｔｏ，Ｍ．，Ｓｅｉｆｅｒｔ，Ｊ．Ｐ．：Ａ  ｎｅｗ  ｃｒｔ−ｒｓａ  ａｌｇｏｒｉｔｈｍ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ｂｅｌｌｃｏｒｅ  ａｔｔａｃｋｓ．Ｉｎ：ＣＣＳ’０３：Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １０ｔｈ  ＡＣＭ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｓｅｃｕｒｉｔｙ，Ｎｅｗ  Ｙｏｒｋ，ＮＹ，ＵＳＡ，ＡＣＭ（２００３）３１１〜３２０
【非特許文献６】Ｊｏｙｅ，Ｍ．，Ｃｉｅｔ，Ｍ．：Ｐｒａｃｔｉｃａｌ  ｆａｕｌｔ  ｃｏｕｎｔｅｒｍｅａｓｕｒｅｓ  ｆｏｒ  ｃｈｉｎｅｓｅ  ｒｅｍａｉｎｄｅｒｉｎｇ  ｂａｓｅｄ  ｒｓａ．Ｉｎ  Ｂｒｅｖｅｇｌｉｅｒｉ，Ｌ．，Ｋｏｒｅｎ，Ｉ．，ｅｄｓ．：２ｎｄ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｆａｕｌｔ  Ｄｉａｇｎｏｓｉｓ  ａｎｄ  Ｔｏｌｅｒａｎｃｅ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ−ＦＤＴＣ  ２００５．（２００５）
【非特許文献７】Ｇｉｒａｕｄ，Ｃ：Ｆａｕｌｔ  ｒｅｓｉｓｔａｎｔ  ｒｓａ  ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｉｎ  Ｂｒｅｖｅｇｌｉｅｒｉ，Ｌ．，Ｋｏｒｅｎ，Ｉ．，ｅｄｓ．：２ｎｄ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｆａｕｌｔ  Ｄｉａｇｎｏｓｉｓ  ａｎｄ  Ｔｏｌｅｒａｎｃｅ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ−ＦＤＴＣ  ２００５．（２００５）１４２〜１５１
【非特許文献８】Ｋｉｍ，Ｃ．Ｈ．，Ｑｕｉｓｑｕａｔｅｒ，Ｊ．Ｊ．：Ｈｏｗ  ｃａｎ  ｗｅ  ｏｖｅｒｃｏｍｅ  ｂｏｔｈ  ｓｉｄｅ  ｃｈａｎｎｅｌ  ａｎａｌｙｓｉｓ  ａｎｄ  ｆａｕｌｔ  ａｔｔａｃｋｓ  ｏｎ  ｒｓａ−ｃｒｔ？  Ｉｎ  Ｂｒｅｖｅｇｌｉｅｒｉ，Ｌ．，Ｇｕｅｒｏｎ，Ｓ．，Ｋｏｒｅｎ，Ｉ．，Ｎａｃｃａｃｈｅ，Ｄ．，Ｓｅｉｆｅｒｔ，Ｊ．Ｐ．，ｅｄｓ．：ＦＤＴＣ．（２００７）２１〜２９
【非特許文献９】Ｊｏｙｅ，Ｍ．，Ｐａｉｌｌｉｅｒ，Ｐ．：Ｇｃｄ−ｆｒｅｅ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｃｏｍｐｕｔｉｎｇ  ｍｏｄｕｌａｒ  ｉｎｖｅｒｓｅｓ．Ｉｎ  Ｂ．Ｓ．Ｋａｌｉｓｋｉ  Ｊｒ．，ｃ．Ｋ．，Ｐａａｒ，Ｃ．，ｅｄｓ．：ＣＨＥＳ．（２００３）２４３〜２５３
【非特許文献１０】Ｙｅｎ，Ｓ．Ｍ．，Ｋｉｍ，Ｓ．，Ｌｉｍ，Ｓ．，Ｍｏｏｎ，Ｓ．：Ｒｓａ  ｓｐｅｅｄｕｐ  ｗｉｔｈ  ｒｅｓｉｄｕｅ  ｎｕｍｂｅｒ  ｓｙｓｔｅｍ  ｉｍｍｕｎｅ  ａｇａｉｎｓｔ  ｈａｒｄｗａｒｅ  ｆａｕｌｔ  ｃｒｙｐｔａｎａｌｙｓｉｓ．Ｉｎ：ＩＣＩＳＣ’０１：Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  Ｓｅｏｕｌｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｃｒｙｐｔｏｌｏｇｙ，Ｌｏｎｄｏｎ，ＵＫ，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ（２００２）３９７〜４１３
【非特許文献１１】Ｊｏｙｅ，Ｍ．，Ｙｅｎ，Ｓ．：Ｔｈｅ  ｍｏｎｔｇｏｍｅｒｙ  ｐｏｗｅｒｉｎｇ  ｌａｄｄｅｒ．Ｉｎ  Ｂ．Ｓ．Ｋａｌｉｓｋｉ  Ｊｒ．，ｃ．Ｋ．，Ｐａａｒ，Ｃ，ｅｄｓ．：Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ−ＣＨＥＳ  ２００２．Ｖｏｌｕｍｅ  ２５２３  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ．（２００２）２９１〜３０２
【非特許文献１２】Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ  Ｉｎｃ．：Ｊａｖａｃａｒｄ  ２．２．２−ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｇｒａｍｍｉｎｇ  ｉｎｔｅｒｆａｃｅ．Ｔｅｃｈｎｉｃａｌ  ｒｅｐｏｒｔ（２００６）
【発明の概要】
【発明が解決しようとする課題】
【００２８】
過去数年間にわたり、このために安全な実装のためのいくつかの技術が公開されてきたが、これらは全て特定の組み込みプラットフォームが直面する制約による不十分さに悩まされてきた。
【００２９】
実際に、制約のある組み込みアーキテクチャにおいて、通常は、少なくとも以下を同時に最適化しようとする：
実行時間
安全なＲＳＡ−ＣＲＴ署名計算は、妥当な時間内で実行されなければならない。明確な範囲を与えずに解決策によって追加された時間オーバーヘッドは、全体的なＲＳＡ署名計算と比較して、可能な限り小さいままにすべきである。これは、特にわずか数メガヘルツのクロック周波数で動作するマイクロコントローラにとって、非常に重要である。
【００３０】
メモリ消費量
解決策は、セキュリティパラメータを保存するために、余分なＲＡＭメモリバッファを必要とする。２Ｋ  ＲＳＡが標準的な機能として一般的にサポートされ、現在の装置、特にあまり性能の良くない物（たとえば低価格スマートカード）では、総メモリ消費量が１Ｋｂから２Ｋｂ（キロバイト）の間のままであることが好ましい。
【００３１】
個人化管理
数百万人によって展開されるスマートカードなどの制約のある装置にとって、および各スマートカードが異なる場合には、個人化は、各スマートカードに含まれる、関連のある（かつ通常は異なる）情報（カードの持ち主の名前、銀行口座番号、特定のデータなど）をロードすることからなるタスクである。多くの分野において、いくつかの個人化態様は、公的機関または事実上のいずれかによって、標準化される。たとえば、携帯電話で使用されるＳＩＭカードのファイルシステムは、相互運用性の許容可能なレベルを保証するために高度に標準化されている（ほとんどのＳＩＭカードも、ほとんどの携帯電話においても動作する）。このような標準化は、とりわけ制約された装置に暗号素材が保存される方法に関わることが多い。したがって、入力鍵パラメータの利用可能性は、非常に厳しい制約である。頻繁に、ＲＳＡ操作のため、ＲＳＡ署名の実行中に、鍵要素ｐ、ｑ、ｄｐ、ｄｑ、ｉｑを含むＣＲＴ分解と同様に、入力メッセージｍのみが知られ、標準に準拠したままにしたい場合には、不揮発性メモリに余分な可変パラメータは保存されなくてもよい。このような制約は、大量生産要件にも起因しており、その場合に装置内で異常にフォーマットされた鍵の個人化は高価であって、そのため古典的なＲＳＡ−ＣＲＴ鍵セットとは異なるものを保存するために、不揮発性メモリ（たとえばＥＥＰＲＯＭまたはフラッシュ）において、カスタマイズ可能な鍵コンテナは通常利用可能ではなく、この一例は、「Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ  Ｉｎｃ．：Ｊａｖａｃａｒｄ  ２．２．２−ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｇｒａｍｍｉｎｇ  ｉｎｔｅｒｆａｃｅ．Ｔｅｃｈｎｉｃａｌ  ｒｅｐｏｒｔ（２００６）」に記載されている。その他のタイプの鍵セットは、非Ｊａｖａ環境（たとえば専用ＯＳ、．ＮＥＴ  ＯＳなど）において利用可能であるが、これらは通常、同じ種類の制約を有する。
【００３２】
コードサイズ
実行可能なコード用にわずかな保存スペースしか有していないマイクロコントローラ上で（通常はＲＯＭまたはフラッシュ）、コードサイズは大きな問題である。解決策によって追加された余分なコードサイズは、解決策によって保護される暗号操作（通常は署名）の総コードサイズと比較して、可能な限り小さいままにすべきである。
【００３３】
これは、Ｂｅｌｌｃｏｒｅ攻撃を食い止めて組み込みシステムの強い要求を満たすＲＳＡのＣＲＴ実装を考案することは難しい問題のままであることを示しており、専門家達は１０年以上にわたってこれを解決しようと試みてきたが、成功していない。
【００３４】
したがって、本発明の目的は、資源制約のある装置に適合する、冪剰余（および特にＲＳＡ署名）を安全に計算できるようにする、解決策を見出すことである。たとえ豊富な資源があっても、通常はその資源を無駄に浪費したくはないので、このような解決策は、当然ながら、より高性能な装置にも非常に良好に適合する。
【課題を解決するための手段】
【００３５】
本発明およびその利点は、添付図面を参照して、以下の明細書でより詳細に説明され、ここで「エラー！参照元が見つかりません」は単純なＲＳＡのＣＲＴ実装を示す。図２はＡｕｍｕｌｌｅｒらによるＲＳＡのＣＲＴ実装を示し、図３は本発明の好適な実施形態を示す。
【００３６】
本発明の好適な実施形態による方法において、冪剰余ｘ＝ｍＤｍｏｄＮが計算され、ここでｍはメッセージ、Ｄは指数、およびＮは係数である。当該技術分野において知られているように、メッセージｍは係数Ｎより小さくなるべきである。冪剰余は、いずれの整数環
【数１１】
2011530093.tif 000012
ここで
【数１２】
2011530093.tif 000013
においても計算可能である。冪剰余は、整数の環または有限フィールドで累乗法を必要とするいずれの暗号システムにも使用可能であり、具体的には：
Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有（Ｄｉｆｆｉｅ，Ｗ．，Ｈｅｌｌｍａｎ，Ｍ．Ｅ．：Ｎｅｗ  ｄｉｒｅｃｔｉｏｎｓ  ｉｎ  ｃｒｙｐｔｏｇｒａｐｈｙ．ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ＩＴ−２２（６）（１９７６）６４４〜６５４）、
Ｅｌ  Ｇａｍａｌ暗号解読（Ｅｌ  Ｇａｍａｌ，Ｔ．：Ａ  ｐｕｂｌｉｃ−ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍ  ａｎｄ  ａ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅ  ｂａｓｅｄ  ｏｎ  ｄｉｓｃｒｅｔｅ  ｌｏｇａｒｉｔｈｍｓ．Ｉｎ：ＣＲＹＰＴＯ．（１９８４）１０〜１８）、
ＲＳＡ直接的モード、
Ｓｃｈｎｏｒｒ（Ｓｃｈｎｏｒｒ，Ｃ．Ｐ．：Ｅｆｆｉｃｉｅｎｔ  ｓｉｇｎａｔｕｒｅ  ｇｅｎｅｒａｔｉｏｎ  ｂｙ  ｓｍａｒｔ  ｃａｒｄｓ．Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ  ４（３）（１９９１）１６１〜１７４）、
ＤＳＡ（Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ：Ｄｉｇｉｔａｌ  Ｓｔａｎｄａｒｄ  Ｓｉｇｎａｔｕｒｅ．Ｆｅｄｅｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｔａｎｄａｒｄｓ  Ｐｕｂｌｉｃａｔｉｏｎｓ  １８６（１９９４））、
ＫＣＤＳＡ（Ｌｉｍ，Ｌｅｅ：Ａ  ｓｔｕｄｙ  ｏｎ  ｔｈｅ  ｐｒｏｐｏｓｅｄ  ｋｏｒｅａｎ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅ  ａｌｇｏｒｉｔｈｍ．Ｉｎ：ＡＳＩＡＣＲＹＰＴ：Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＡＳＩＡＣＲＹＰＴ：Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ｔｈｅ  Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ，ＬＮＣＳ，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ（１９９８）１７５〜１８６）、
その他。
【００３７】
しかしながらそれは、ＣＲＴを備えるＲＳＡの場合に特に関連がある。
【００３８】
２つのパラメータ、すなわちｋ、およびＲとＮとが互いに素となるような整数Ｒが、使用される。ｋおよびＲは両方とも、好ましくはＮよりはるかに小さい。たとえばＲは３２ビットまたは６４ビット長でもよく、その一方でＮはたとえば１０２４ビット長であってもよい。整数ｋおよびＲはいずれの値にも設定可能であるが、ただしＲはＮと互いに素となるべきである。多くの場合、ＲがＮよりもはるかに短い場合には、ＮとＲは必ず互いに素であるので、素数性を試験する必要なく、いずれのＲが選択されることも可能である。たとえば、ＲＳＡの場合、Ｎは、Ｎのサイズのほぼ半分である２つの大きい素数の積である。したがって、Ｒはどの素数とも等しくなることが不可能であり（Ｒは短すぎるため）、そのためＲは必ず各素数と互いに素であり（素数性の定義による）、結果的にＲはＮとも互いに素である。ＲがＮと互いに素であるか否かを事前に知ることができないときには、相互素数性テストを利用することができる。たとえばＦｅｒｍａｔテスト、Ｍｉｌｌｅｒ−Ｒａｂｉｎテスト、Ｓｏｌｏｖａｙ−Ｓｔｒａｓｓｅｎテストなど、当該技術分野において多くの素数性テストが知られているが、しかし相互素数性テストを使用する方がより効率がよい。相互素数性テストは、２つの数のｇｃｄ（最大公約数）が一方と等しいか否かを検証するテストである。たとえばユークリッドおよびバイナリユークリッド法など、２つの数のｇｃｄを計算する方法はいくつかある。このようなテストは、ＲおよびＮが互いに素か否かを判断するために使用可能であり、そうでない場合には、パラメータＲはＮと互いに素になるまで変更されるべきである。Ｒを変更するためには、素数生成に通常使用される技術の１つに依存することが可能である（特にＲＳＡ鍵のペアを作成するときに適用される）。たとえば、新たなＲは無作為に選択されてもよく、または新たなＲは、たとえば関数Ｒ＝ｆ（Ｒ）によって、以前のＲから計算されてもよい。非常に単純な関数ｆの例は、以下を含む。Ｒが偶数の場合には、Ｒに／Ｒから１またはいずれかの奇数を加えるかまたは減じる。Ｒが奇数の場合には、Ｒに／Ｒから２を加えるかまたは減じる（またはいずれかの偶数を加えるかもしくは減じる）。最も単純な方法は、Ｒが奇数であることを確認し（そうでない場合には１を加え）、その後相互素数性テストがＮおよび新たに計算されたＲに適合するまで、２を加えることである。
【００３９】
冪剰余の計算は、以下のステップの実装によって侵入型攻撃から保護される。
ａ．α＝１ｍｏｄＮ、α＝０ｍｏｄＲ、β＝０ｍｏｄＮ、およびβ＝１ｍｏｄＲとなるようにマスクαおよびマスクβを生成する。マスクαの上記特性は、高い確率でメッセージｍの改ざんの検出を可能にするように設計されている。マスクβの上記特性は、高い確率で指数Ｄの改ざんの検出を可能にするように設計されている。
ｂ．マスクされたメッセージｍ’＝（ｍ＊α＋ｋ＊β）ｍｏｄ（Ｎ＊Ｒ）を計算することによって、マスクαおよびβでメッセージｍをマスクする。
ｃ．冪剰余ｘ’＝ｍ’Ｄｍｏｄ（Ｎ＊Ｒ）を計算する。
ｄ．（ｘ’−ｋＤ）ｍｏｄＲ＝０の場合、ｘ＝ｘ’ｍｏｄＮを出力するか、そうでなければ解決策を適用する。（ｘ’−ｋＤ）ｍｏｄＲ≠０の場合には、マスクは特性（ｘ’−ｋＤ）ｍｏｄＲ＝０が認証されるように設計されているので、どこかで侵入型攻撃が発生したに違いない。また、この特性を維持しながらｘ’の値を変更することは非常に難しいので、何らかの侵入型攻撃が発生した場合には特性はもはや認証されない可能性が非常に高い。したがって、（ｘ’−ｋＤ）ｍｏｄＲ＝０の場合には、攻撃がなかった可能性が最も高く、方法は、ｘ＝ｘ’ｍｏｄＮに等しい、指数の予想された結果を出力することができ、そうでなければ検出された攻撃に応えて解決策を適用するはずである。
【００４０】
この第一の実施形態の簡素化されたバージョンにおいて、整数ｋはゼロに等しく、このことはマスクβを計算する必要がないこと、および上記ステップがより簡単であることを意味する。この技術は、実装がより簡単であり、より少ないメモリを必要とし、少し高速であるが、しかしながら、特に攻撃が指数Ｄのみに影響する場合には、侵入型攻撃を検出する確率が少し低い。したがって、簡素化された方法は、以下のステップを含む：
ａ．α＝１ｍｏｄＮおよびα＝０ｍｏｄＲとなるようにマスクαを生成し、
ｂ．マスクされたメッセージｍ’＝（ｍ＊α）ｍｏｄ（Ｎ＊Ｒ）を計算することによって、マスクαでメッセージｍをマスクし、
ｃ．冪剰余ｘ’＝ｍ’Ｄｍｏｄ（Ｎ＊Ｒ）を計算し、
ｄ．ｘ’ｍｏｄＲ＝０の場合、ｘ＝ｘ’ｍｏｄＮを出力するか、そうでなければ解決策を適用する。
【００４１】
先の２つの実施形態の１つによる方法に対応する、第三の好適な実施形態による方法において、αは式α＝（１−Ｎ＊（（１／Ｎ）ｍｏｄＲ）ｍｏｄ（Ｎ＊Ｒ）で計算される。当然ながら、たとえばＮ＊Ｒの倍数を加えることによって、その他の値が使用されることも可能である。
【００４２】
第四の好適な実施形態において、マスクβを利用する上記の実施形態は、式β＝（Ｎ＊（（１／Ｎ）ｍｏｄＲ））ｍｏｄ（Ｎ＊Ｒ）でβを計算する。同様に、βにはその他の値が可能である（たとえばＮ＊Ｒの倍数を加える）。
【００４３】
第五の好適な実施形態において、先の実施形態は、以下のように改良される。冪剰余ｘ’＝ｍ’Ｄｍｏｄ（Ｎ＊Ｒ）を実行する前に、ｍ＝ｍ’ｍｏｄＮが認証され、そうでない場合には、解決策が適用される。冪剰余の後にｍ＝ｍ’ｍｏｄＮをもう一度認証することも、可能である。攻撃が発生したことがわかっている場合に冪剰余を実行しないために（解決策の結果、通常の出力手段を使用して出力が与えられなくても、これはある程度の情報を漏らす可能性がある）、冪剰余の前にｍ＝ｍ’ｍｏｄＮを認証することが有利である。攻撃が気付かれないままである可能性（ハッカーが冪剰余の最中になんとかしてｍ’を変更してテスト（ｘ’−ｋＤ）ｍｏｄＲ＝０をどうにか飛ばすか、またはたとえば侵入型攻撃によって、このテスト（ｘ’−ｋＤ）ｍｏｄＲ＝０を適切に認証させるという、ありそうもない状況）を最小限に抑えるために冪剰余の後に（上述のように）もう一度認証することも、理にかなっているかも知れない。ｍ≠ｍ’ｍｏｄＮの場合には、メッセージをマスクしている最中またはマスク後に攻撃が発生したに違いない。構造的に、オリジナルメッセージｍは、マスクされたメッセージｍ’モジュロＮに等しくなるべきである（単一のマスクαが使用されても、αおよびβの両方のマスクが使用されても）。この等式が認証されない場合には、攻撃があったに違いない（たとえばマスク操作中に誤作動を発生させる）。マスクされたメッセージｍ’の値が変更され、しかし同時に変更されたオリジナルメッセージｍがまだマスクされたメッセージｍ’モジュロＮに等しいように操作を中断させることは、ハッカーにとって非常に難しいので、攻撃が検出される可能性は高い。
【００４４】
第六の好適な実施形態において、先の実施形態の解決策は、必要とされる冪剰余のいずれの結果も出力しないことを含む。その代わりに、たとえば、エラー状態を出力することが可能である。（出力がないため）ハッカーは改ざんされた出力の解析を容易に実行できず、（方法をハッキングしようとする際に）エラーを生成したことが既にわかっているため、エラー状態からあまり有益な情報を推論することができないので、これは有利である。ハッカーが取得できる情報は、方法が彼の攻撃を検出したという事実のみである。あるいは、たとえば、無作為の結果を出力することが可能である。このようにすると、いくつかの数学的特性が、予想される偽出力と一致すべきであったが無作為出力と一致していないことを見出すことが出来ない限り、ハッカーは、彼の攻撃が検出されたか否かさえわからないが、方法中の解決策へのこの予想されない結果を突き止めることは、彼の攻撃中の故障を突き止めることよりも、彼にとって非常に難しい。好適な実施形態において、侵入型攻撃の検出は、侵入型攻撃の回数を計数すること、および計数が所定の閾値に到達した後に冪剰余を計算している実体を遮断することなど、別の解決策を始動させることができる。閾値は１とすることができ、すなわち攻撃が検出されるとすぐに、実体が遮断される。解決策は、関連する実体に攻撃が発生したことを知らせるために記録および／または報告手段を含むこともできる。冪剰余の最中またはその後に改ざん（具体的にはマスクされたメッセージ、または指数、またはその両方の改ざん）を検出するための解決策も、メッセージのマスキングの改ざんを検出するための追加解決策（マスク前、またはマスキング中にメッセージが変更されたか否か、または冪剰余が完了する前にマスクされたメッセージが変更されたか否かを確認するために好適な実施形態に追加された）も、同じ解決策であってもよい。あるいは、たとえば、メッセージのマスキング中に、または冪剰余中などもっと後の段階で、攻撃が検出されたか否かを記録することが可能である。
【００４５】
第七の好適な実施形態において、上述の実施形態は、整数Ｒに乱数を使用することによって改良される。Ｒは好ましくは超高性能乱数生成器（ＲＮＧ）で生成される。このような高性能ＲＮＧは、通常はハードウェア手段（チップ内のノイズのサンプリングなど）に、およびハードウェアソースから取得されたシードの後処理（後処理は通常はソフトウェア内で実行可能）に依存する。最初に高性能ＲＮＧで中間乱数を生成し、次にこの中間乱数を処理して乱数Ｒを処理することが可能である（たとえば、その統計的特性をさらに向上させるために中間乱数は暗号プロセッサを通過することができる）。
【００４６】
第八の好適な実施形態において、各冪剰余のために新しい乱数Ｒを生成することによって、第七の実施形態が改良されている。これは方法の解析をより難しくするので、有利である（ハッカーは決して同じパラメータＲを見つけることがなく、これはリバースエンジニアリングをより複雑にする）。
【００４７】
第九の実施形態において、先の実施形態（パラメータｋを含まない第二の実施形態を除く）は、以下のように改良される。整数ｉからなる、別のパラメータが使用される。整数ｉは、好ましくは２に等しいが、しかしこれより大きくてもよい。比較的小さい数であることが好ましい。整数Ｒは、Ｒ＝ｒｉとなるように整数ｒをｉ乗することによって得られる。整数ｒは、ｇｃｄ（Ｎ，ｒｉ）＝ｇｃｄ（Ｎ，ｒ）＝１、すなわちＮとｒとが互いに素となるような、いずれの値を有することもできる。ｒの長さは、好ましくは予想されるＲの長さをｉで割った商よりも大きい（たとえば、Ｒが６４ビットを有すると予想され、ｉ＝４である場合には、ｒは好ましくは少なくとも１６ビット長となるべきである）。ｒが予想されるＲの長さをｉで割った商よりも長いと役に立たないが、長い可能性がある。（たとえば、モジュロを用いて）Ｒは後に予想される長さまで圧縮されることが可能である。整数Ｒが、第七または第八の好適な実施形態により、乱数である場合、ｒは好ましくは高性能ＲＮＧで取得され、ｒのｉ乗が後処理の形式となり（上述）、したがってＲは高性能ＲＮＧから得られた乱数であると考えられる。しかしながら、Ｒは（ｉｔｈ乗根を有するため）いくつかの特性を呈し、そのためおそらくｒそのものほど無作為とは考えられないが、しかしその段階で、Ｒのこのような特性に依存する攻撃は想定されない。ｒｉがＮと互いに素ではない場合には、条件が合うまで別のｒを無作為に選択することができる（しかし上述のように、Ｒが短いという単純な事実は、たとえばＲＳＡ向けなど、多くの場合にＲとＮを互いに素とする）。値ｋ＝１＋ｒに整数ｋが設定される。これは、さもなければかなり長くなってしまう可能性のあるｋＤの計算の高速化を可能にするので、非常に有利である。実際、
【００４８】
【数１３】
2011530093.tif 000014
であり、結果は計算されたモジュロＲ、すなわちモジュロｒｉであるので、累乗がｉ−１より大きい和の全ての要素は、ゼロモジュロＲに等しい、したがって、
【００４９】
【数１４】
2011530093.tif 000015
となる。具体的には、好適な一実施形態において、ｉ＝２、および（１＋ｒ）Ｄ＝（１＋Ｄ＊ｒ）ｍｏｄＲとなり、したがってこれは自明に、かつ非常に迅速に計算されることが可能である。ｉが小さいと計算が速くなることを踏まえて、ｉにいずれか別の値を使用することも可能である。
【００５０】
変形例において、第十の改良型方法が提案されるが、ここで第一、第三、第四、第五、第六、第七、または第九（第九の実施形態が第八の実施形態によって実行されないとき）の実施形態のいずれか１つによる本方法は、秘密指数Ｄおよび関連する係数Ｎを用いる方法によって実行される、いくつかの冪剰余（たとえば、係数Ｎおよび関連する指数Ｄとともに呼び出される次の３２の冪剰余）に、または全ての冪剰余にさえも、数Ｒおよび整数ｋを再利用することによって、改良される。方法は、冪剰余のために数セットのパラメータを扱うことができる。たとえば、いくつかのＲＳＡ鍵が利用可能であって、どの鍵がＲＳＡ署名操作に使用されるかに依存する場合、異なるパラメータＮおよびＤが使用されることもあり得る（たとえば、重要な事柄には、中級もしくは上級Ｘ．５０９認証に関連するＲＳＡ鍵による署名、またはあまり重要ではない日常的な事柄にはより低性能なＸ．５０９認証に関する鍵による署名）。そのような場合、異なるパラメータ（たとえばＮおよびＤ）に対しても、同じＲおよびｋが使用されると決定されてもよい。あるいは、異なるパラメータ（たとえばＮおよびＤ）には異なるＲおよびｋが使用されてもよいが、しかし与えられたパラメータのセット（たとえばＮおよびＤ）について、Ｒおよびｋは変更されることはないか、またはたまにしか変更されない。この改良バージョンによれば、マスクαおよびβは、値ｋＤｍｏｄＲと同様に、多くの冪剰余のために一度予備計算される。特にｋＤｍｏｄＲを計算することは（αおよびβも）時間がかかり、事前にそれを行うことによって方法の性能が（実行速度の観点から）向上するので、これは有利である。ＲＳＡの場合には、ＮおよびＲを含むＲＳＡ鍵を生成した直後に、Ｒ、ｋ、ｋＤｍｏｄＲ、α、およびβも計算することが可能となり、ＲＳＡ署名の時には、これらのパラメータＲ、ｋ、ｋＤｍｏｄＲ、α、およびβはメモリから読み出されるだけでよく、いかなる計算も伴わない。この実施形態はより高速であるが、しかし同じ素材を数回再利用することによって攻撃が容易になるので、当然ながら、各指数に無作為のＲを生成するよりもわずかに安全性が劣る。
【００５１】
好適な実施形態において、上記の方法は、図３に示される乱数Ｒ１、Ｒ２、Ｒ３、およびＲ４などの乱数による内部マスキング操作も含む。
【図面の簡単な説明】
【００５２】
【図１】ＣＲＴモードでのＲＳＡ署名の単純なＣＲＴ実装を示す。
【図２】ＡｕｍｕｌｌｅｒらによるＲＳＡのＣＲＴ実装を示す。
【図３】本発明の好適な実施形態を示す。
【発明を実施するための形態】
【００５３】
本発明の好適な実施形態のより詳細な説明が、以下に記載される。
【００５４】
指数ｄモジュロＮに対するＮよりも小さいメッセージｍの一般的な累乗法を検討する。Ｒがたとえば６４ビットの整数乱数である、累乗モジュロＮＲを実行する。ＮとＲが互いに素、すなわちｇｃｄ（Ｎ，Ｒ）＝１であると仮定する。ＲＳＡでは、このような乱数がｐより小さくｑより小さければこの特性が自動的に認証され、６４ビットの乱数ではこれに該当する。
【００５５】
αを
【００５６】
【数１５】
2011530093.tif 000016
とし、βを
【００５７】
【数１６】
2011530093.tif 000017
とする。
【００５８】
中国の剰余定理を適用して、
【数１７】
2011530093.tif 000018
におけるαおよびβの存在および一意性を得る。Ｇａｒｎｅｒのアルゴリズムを使用して、これらの整数を作る：
α＝Ｒ・（Ｒ−１ｍｏｄＮ）＝１−［Ｎ・（Ｎ−１ｍｏｄＲ）］ｍｏｄＮＲ
β＝Ｎ・（Ｎ−１ｍｏｄＮ）＝１−［Ｒ・（Ｒ−１ｍｏｄＮ）］ｍｏｄＮＲ
ここでＲ＝ｒ２、ただしｒはたとえば３２ビットの乱数、となるようにＲを検討すると、以下の結果が得られる：
【００５９】
定理１（
【数１８】
2011530093.tif 000019
における累乗恒等式）。Ｎおよびｒをｇｃｄ（Ｎ，ｒ）＝１となるような整数とし、β＝Ｎ・（Ｎ−１ｍｏｄｒ２）およびα＝１−βｍｏｄＮｒ２とする。いずれの
【数１９】
2011530093.tif 000020
についてもいずれの
【数２０】
2011530093.tif 000021
についても、
（αｍ＋β・（１＋ｒ））ｄ＝αｍｄ＋β・（１＋ｄｒ）ｍｏｄＮｒ２
【００６０】
証明および関連する数学的詳細を求めて付録Ａを参照する。定理１は、いずれかの環
【数２１】
2011530093.tif 000022
【数２２】
2011530093.tif 000023
で安全な累乗を実行する方法を提供する。
【００６１】
安全な累乗法アルゴリズム
【数２３】
2011530093.tif 000024
に対する整数ｍ＜Ｎの累乗ｍｄを実行したい。Ｎと互いに素な整数乱数ｒを選択し、β＝Ｎ・（Ｎ−１ｍｏｄｒ２）およびα＝１−βｍｏｄＮｒ２を計算する。定理１を適用して、要素ｍを累乗し、中断が生じないことを確認するために、以下のように処理する：
１．
【数２４】
2011530093.tif 000025
を計算する、
２．
【数２５】
2011530093.tif 000026
であることを確認し、不等の場合には「エラー検出」を返す、
３．
【数２６】
2011530093.tif 000027
およびＳ＝ＳｒｍｏｄＮ（＝ｍｄｍｏｄＮ）を計算する、
４．Ｓｒ＝αＳ＋β・（１＋ｄｒ）ｍｏｄＮｒ２であることを確認し、不等の場合には「エラー検出」を返す。
【数２７】
2011530093.tif 000028
におけるβ＝β２およびαβ＝０の等式のため（αおよびβの構成による）、Ｓｒの整合性も、以下の判定のいずれか１つによって確認される：
１．βＳｒ＝β・（１＋ｄｒ）ｍｏｄＮｒ２
２．Ｎ・（Ｓｒ−β・（１＋ｄｒ））＝０ｍｏｄＮｒ２
３．Ｓｒ＝１＋ｄｒｍｏｄｒ２
最適な選択肢は、ハードウェアアーキテクチャおよびアルゴリズムのコンテキストによって異なる。この解決策は、累乗法
【数２８】
2011530093.tif 000029
【数２９】
2011530093.tif 000030
に基づくいずれの暗号方式にも適用されてもよい（ＲＳＡ［９］、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵共有［１４］、ＥｌＧａｍａｌ［１５］、・・・）。ここでＲＳＡのＣＲＴ実装へのその適用を強調しているが、これは特に関連性があるように思われる。
【００６２】
ＣＲＴを備えるＲＳＡへの適用
ｐおよびｑは素数なので、ｒは自動的にｐおよびｑと互いに素となり、以下のように定義する：βｐ＝ｐ・（ｐ−１ｍｏｄｒ２）、αｐ＝１−βｐｍｏｄｐｒ２、βｑ＝ｑ・（ｑ−１ｍｏｄｒ２）、およびαｑ＝１−βｐｍｏｄｑｒ２。図３は、ＣＲＴを備えるＲＳＡへの解決策の可能な適用を示す。累乗ＳｐｒおよびＳｑｒが
【数３０】
2011530093.tif 000031
および
【数３１】
2011530093.tif 000032
に対して実行される。以下を判定することにより、各累乗が中断されていないことを確認する：
【数３２】
2011530093.tif 000033
および
【数３３】
2011530093.tif 000034
２つの６４ビットの整数乱数Ｒ３およびＲ４を選択する。その後：
Ｓｐｒを
【数３４】
2011530093.tif 000035
に、Ｓｑｒを
【数３５】
2011530093.tif 000036
に、変換する。
次に、結果的に生じた署名が
【数３６】
2011530093.tif 000037
に再結合される：
【数３７】
2011530093.tif 000038
そして、最終整合性判定を実行する：
Ｓ＝Ｒ４＋ｑｉｑ・（Ｒ３−Ｒ４）ｍｏｄｒ２
全ての確認が正しければ、結果ＳｍｏｄＮを返す。
【００６３】
乱数生成器の性能を検証することが推奨される。ｉｑ≠０ｍｏｄｒになるようにｒを選択することも、推奨される。実際、（Ｓｐ−Ｓｑ）ｍｏｄ（ｐ＊ｒ２）の結果またはｑが変更されていても認証Ｎ＊［Ｓ−Ｒ４−ｑ＊ｉｑ＊（Ｒ３−Ｒ４）］＝０ｍｏｄ（Ｎ＊ｒ２）は真なので、ｒでｉｑを割ると、故障検出確率が低下する。そのため、ｒがｉｑを割る間に無作為のｒの生成を更新することを推奨する。無作為のｒは、ハードウェアアーキテクチャの制限内で可能な限り大きくすべきであり、Ｎと比較して好ましくは小さくすべきであることを踏まえる。ｒをセキュリティパラメータと見なすことができるので、これが大きいほど、故障検出確率は高くなる。実際、攻撃の最大成功確率は２−（｜ｒ｜−１）ｌｎ２である（さらなる詳細は、下記および付録Ｂを参照）。そのため、ｒは少なくとも３２ビットの整数乱数であることを推奨する。最後に、セキュリティレベルを最適化するために、１に等しい最上位ビットを有するｒを選択することが好ましい。反転の効率を最適化するために、奇数のｒを選択することも好ましい。
【００６４】
本発明は、冪剰余ｘ＝ｍＤｍｏｄＮを計算するように配置された電子装置にも関し、ここでｍはメッセージ、Ｄは指数、およびＮは係数である。装置は、以下を含むことにより、侵入型攻撃に対して冪剰余を保護するように設定され、
ａ．α＝１ｍｏｄＮ、α＝０ｍｏｄＲ、β＝０ｍｏｄＮ、およびβ＝１ｍｏｄＲとなるように、マスクαおよびマスクβを生成する手段と、
ｂ．マスクされたメッセージｍ’＝（ｍ＊α＋ｋ＊β）ｍｏｄ（Ｎ＊Ｒ）を計算することによって、マスクαおよびβでメッセージｍをマスクする手段と、
ａ．冪剰余ｘ’＝ｍ’Ｄｍｏｄ（Ｎ＊Ｒ）を計算する手段と、
ｂ．（ｘ’−ｋＤ）ｍｏｄＲ＝０か否かを判定する手段であって、
この条件が確認された場合にはｘ＝ｘ’ｍｏｄＮを出力し、
そうでなければ解決策を適用する、手段を含み、
ここで整数ｋおよび整数Ｒは、ＲとＮとが互いに素となるように与えられる。
【００６５】
電子装置は、パーソナルコンピュータ、サーバ、電話、ＰＤＡなどであってもよい。好適な実施形態において、電子装置はセキュリティ装置であり、具体的には、これはスマートカード、ＨＳＭ、ＵＳＢ鍵、またはいかなる形態の暗号トークンであってもよい。
【００６６】
装置は好ましくは、本発明による方法を実装する。方法のために上述された全ての変形例は、装置にも等しく適用される。
【００６７】
後に、図３の好適な実施形態について、故障攻撃に対する耐性の解析、サイドチャネル解析、および性能解析を提供する。
【００６８】
その後、付録ＡおよびＢにおいて、本発明で使用される定理および特性のいくつかの実証を提供する。
【００６９】
故障攻撃に対する耐性
以下の故障モデルは、仮定により、攻撃者ができることを定義する。装置を中断することにより、攻撃者は：
元の値と無相関な、まったく無作為の結果を取得するメモリ内で値を変更すること（恒久的故障として知られる）、
ローカルレジスタ内で操作されているとき、メモリ内の大域的な値を変更せずに値を変更することができるということを意味している。操作および取得された値は、攻撃者に対して完全に無作為であり、元の値とは無相関である（過渡故障として知られる）。
【００７０】
設計は、以下のことが可能な攻撃者には対応していない：
コード実行を変更すること。プロセッサ命令は、コードの実行中には置換または削除されることは不可能である。このような攻撃者は、ＥＥＰＲＯＭをダンプして秘密鍵を獲得する力を有している場合がある、
入力要素、メッセージｍ、ならびに鍵（ｐ、ｑ、ｄｐ、ｄｑ，ｉｑ）に恒久的故障を注入すること。署名中はいつでも認証され得る完全性値とともに入力要素が与えられると考える、
条件判定のブール型結果を変更すること。「ａ＝ｂの場合」という表現は、変更できない真または偽の結果を有する。ここでセキュリティのレベルに関して妥協した。実際、感染計算に基づくその他のいくつかの方法とは対照的に設計は条件判定を使用する。しかしながら、これらの判定を計算の無条件感染と置き換えることが可能である。
【００７１】
図３に記載されるＲＳＡのＣＲＴ実装を検討し、セクション３、４で説明された推奨に従ってきたと想定する。｜ａ｜がａのビットサイズでありａがａの故障値であることに留意して、いくつかの故障シナリオを再検討し、関連する成功確率を特定してみる（確率は、付録Ｂにおいてより詳述されている）：
ｐ’の計算中に過渡的な方法でｐもしくはｒを変更、または
【数３８】
2011530093.tif 000039
の判定の前に恒久的な方法でｐ’を変更する（ｑ’についても同様である）：
【数３９】
2011530093.tif 000040
【数４０】
2011530093.tif 000041
の判定の後、累乗の最中にのみ恒久的故障が発生する場合には：
【数４１】
2011530093.tif 000042
【数４２】
2011530093.tif 000043
の計算中に過渡的な方法でｍを変更、または判定の前に恒久的な方法で
【数４３】
2011530093.tif 000044
を変更する（
【００７２】
【数４４】
2011530093.tif 000045
についても同様である）：
【数４５】
2011530093.tif 000046
第一の累乗の後に恒久的な方法でｍを変更する（ｍが認証された完全性値と関連づけられていることも考慮してもよい）：
【数４６】
2011530093.tif 000047
【数４７】
2011530093.tif 000048
の判定の後に恒久的故障が発生した場合：
【数４８】
2011530093.tif 000049
ｉｐｒの計算中に過渡的な方法でｐもしくはｒ２を変更、または恒久的な方法でｉｐｒを変更（ｉｑｒについても同様である）：
【数４９】
2011530093.tif 000050
βｐの計算中に過渡的な方法でｐもしくはｉｐｒを変更、または恒久的な方法でβｐを変更（βｑについても同様である）：
【数５０】
2011530093.tif 000051
αｐの計算中に過渡的な方法でβｐもしくはｐ’を変更、または恒久的な方法でαｐを変更（αｑについても同様である）：
【数５１】
2011530093.tif 000052
【数５２】
2011530093.tif 000053
の計算中に過渡的な方法で（ｐ−１）もしくはｄｐを変更、または恒久的な方法で
【数５３】
2011530093.tif 000054
を変更（
【数５４】
2011530093.tif 000055
についても同様である）：
【数５５】
2011530093.tif 000056
Ｓｐｒの計算中に過渡的な方法で
【数５６】
2011530093.tif 000057
を変更（Ｓｑｒについても同様である）：
【数５７】
2011530093.tif 000058
Ｓｐｒの計算中に過渡的な方法で
【数５８】
2011530093.tif 000059
またはｐ’を変更（Ｓｑｒについても同様である）：
【数５９】
2011530093.tif 000060
【数６０】
2011530093.tif 000061
の計算中に過渡的な方法でＳｐｒ、
【数６１】
2011530093.tif 000062
、Ｒ３、もしくはｐ’を変更、または恒久的な方法で
【数６２】
2011530093.tif 000063
を変更（
【数６３】
2011530093.tif 000064
についても同様である）：
【数６４】
2011530093.tif 000065
再結合中に過渡的な方法で
【数６５】
2011530093.tif 000066
【数６６】
2011530093.tif 000067
ｐ’、ｑ、ｉｑ、または
【数６７】
2011530093.tif 000068
を変更：
【数６８】
2011530093.tif 000069
【００７３】
サイドチャネル解析
この研究ではサイドチャネル解析は調査されないが、設計は、サイドチャネル攻撃に対する適合した追加解決策と組み合わせられるべきである。
【００７４】
性能解析
実行時間
最も高コストなステップは、２つの反転である。これらは、ｒの長さの２倍の長さを有するパラメータ上で実行される。ｉｐｒ０＝ｐ−１ｍｏｄｒおよびｉｑｒ０＝ｑ−１ｍｏｄｒであることに留意して、ｉｐｒ０およびｉｑｒ０からｉｐｒおよびｉｑｒを計算するためのトリックを利用する。実際に、ｐ＝ｐ０＋ｐ１ｒｍｏｄｒ２およびｉｐｒ１＝［−ｉｐｒ０ｐ１−（（ｉｐｒ０ｐ０−１）／ｒ）］・ｉｐｒ０ｍｏｄｒとする。さらに、ｉｐｒ＝ｒｉｐｒ１＋ｉｐｒ０（ｉｑｒについても同様である）。このように、わずか２つの反転モジュロｒのみが、ｉｐｒおよびｉｑｒを計算するために必要とされる。ｒがたとえば３２ビット値であって、３２ビットチップのアーキテクチャ上で実装が行われる場合、アルゴリズムのループは３２ビット単精度データ上の比較、シフト、減算、および加算で構成されるので、ＳＰＡ安全拡張バイナリｇｃｄアルゴリズムは非常に効率的に実装されることが可能である。このコンテキストにおいて、解決策が追加された実行時間は、明らかにＡｕｍｕｌｌｅｒらの解決策［４］よりも低コストである。より小さいマイクロコントローラ上では、実行時間はハードウェアアーキテクチャに依存することになるが、しかし２つの反転はせいぜい２つの累乗モジュロｔ（｜ｔ｜＝｜ｒ｜の場合）と同程度のコストと考えられる状態に非常に近づいている。したがって、提案は、２つの付加的なトーティエント計算が必要とされるＪｏｙｅおよびＣｉｅｔの解決法［６］よりも効率的である。攻撃者が乗算から２乗を識別することができないような特性を我々の累乗アルゴリズムのみが有する場合、我々のアルゴリズムがＧｉｒａｕｄの解決策［７］とほぼ同じくらい効率的であるとも考えられる。累乗がマスクされる、ＣＲＴを備えるＲＳＡの場合には、累乗アルゴリズムは、モンゴメリ−ラダーアルゴリズム［１３］とは対照的に不安定になり得る。係数および指数が６４ビットの整数乱数によって無作為抽出されると考えた場合、各累乗に対して約
【００７５】
【数６９】
2011530093.tif 000070
および
【００７６】
【数７０】
2011530093.tif 000071
だけ少ないモジュラー乗算を、より大きい演算数で実行する。一例として、３２ビットアーキテクチャ上で実装が行われる場合、長さｋの３２ビットワードの２つの演算数での１つのモンゴメリモジュラー乗算は、理論上は２ｋ（ｋ＋１）の単精度乗算を必要とする。このように、１つのモンゴメリ−ラダー累乗は、明確なデータでの約１２８ｋ２（ｋ＋１）の単精度乗算を必要とするが、それに対して無作為抽出されたデータによる古典的な累乗では９６（ｋ＋２）２（ｋ＋３）である。結果として、６４０ビットより大きいｐおよびｑについて、アルゴリズムは、Ｇｉｒａｕｄの物よりもわずかに効率が良い。このサイズでは、正反対である。
【００７７】
メモリ消費量
解決策は、Ａｕｍｕｌｌｅｒらの［４］ならびにＪｏｙｅおよびＣｉｅｔの実装［６］とほぼ同程度のメモリを必要とする。明らかに、メモリ消費量が深刻な欠点であるＧｉｒａｕｄの提案［７］よりもはるかに少ないメモリを必要とする。図３において、ｉｐｒおよびｉｑｒはスタックに保存されることが可能なので、
【数７１】
2011530093.tif 000072
および
【数７２】
2011530093.tif 000073
の計算中にはβｐ、βｑはＲＡＭに保持されないと考えることができる。βｐおよびβｑは、必要なときに「オンザフライ」で計算されることが可能である。値ｍｐと同じように、ｍｐｍｏｄｒ２だけはスタックに保存されることが可能である。メモリ消費量が最大となる瞬間は、
【数７３】
2011530093.tif 000074
【数７４】
2011530093.tif 000075
がそれぞれ長さ｜ｐ｜＋２｜ｒ｜、および｜ｑ｜＋２｜ｒ｜を有する場合を除いて、再結合中に発生する（古典的なＲＳＡ−ＣＲＴ署名のときと同様）。最終的な結果は、長さ｜Ｎ｜＋２｜ｒ｜を有する。コプロセッサレジスタのサイズは２Ｋに制限されてもよいので、いくつかの暗号プロセッサは、Ｎが２Ｋ整数である場合、最終認証（Ｓ−Ｒ４−ｑｉｑ・（Ｒ３−Ｒ４））・Ｎ≡０ｍｏｄＮｒ２を実行することができない。この場合、最終認証は、Ｓ−Ｒ４−ｑｉｑ・（Ｒ３−Ｒ４）≡０ｍｏｄｒ２に置き換えられることが可能である。
【００７８】
個人化管理
提案された実装は、計算に必要な通常のパラメータ、入力メッセージｍおよび古典的なＲＳＡ−ＣＲＴ鍵セット（ｐ，ｑ，ｄｐ，ｄｑ，ｉｑ）のみを必要とする。
【００７９】
コードサイズ
解決策は、主にＲＳＡ−ＣＲＴ署名用に既に開発された算術演算に基づいている。やはり古典的な算術演算に基づくモジュラー反転のみが実装されるべきである。モジュラー反転のコードは、ＲＳＡ鍵生成を供給する際にＲＳＡ署名も供給する製品に含まれる場合が多い。モジュラー反転のコードが追加される必要があったとしても、これは許容可能なコードサイズオーバーヘッドを生じる。
【００８０】
Ａ．定理１の証明
主張
ＮおよびＲをｇｃｄ＝（Ｎ，Ｒ）＝１となるような整数とし、β＝（Ｎ・（Ｎ−１ｍｏｄＲ））およびα＝１−βｍｏｄＮＲとする。αおよびβは、以下の特性に従う非ゼロ要素である：
１．α２＝αｍｏｄＮＲ
２．β２＝βｍｏｄＮＲ
３．αβ＝０ｍｏｄＮＲ（αおよびβは
【数７５】
2011530093.tif 000076
のゼロ因子（ｄｉｖｉｓｏｒｓ）である）
【００８１】
証明
これは明らかに、αおよびβの定義から来ている。
【００８２】
補題１．
Ｎおよびｒをｇｃｄ＝（Ｎ，ｒ）＝１となるような整数とし、β＝Ｎ・（Ｎ−１ｍｏｄｒ２）およびα＝１−βｍｏｄＮｒ２とする。するといずれの
【数７６】
2011530093.tif 000077
およびいずれの
【数７７】
2011530093.tif 000078
ペアでも：
（αＡ＋βＢ）ｄ＝αＡｄ＋βＢｄｍｏｄＮｒ２      （１）
証明
Ｒ＝ｒ２とする。αβ＝０ｍｏｄＮｒ２なので、いずれの
【数７８】
2011530093.tif 000079
およびいずれの
【数７９】
2011530093.tif 000080
でも、以下が得られる：
（αＡ＋βＢ）ｄ＝（αＡ）ｄ＋（βＢ）ｄｍｏｄＮｒ２＝αＡｄ＋βＢｄｍｏｄＮｒ２
なぜならαｄ＝αおよびβｄ＝βモジュロＮｒ２である。
【００８３】
補題２．
Ｎおよびｒを互いに素である整数とし、β＝Ｎ・（Ｎ−１ｍｏｄｒ２）とする。いずれの
【数８０】
2011530093.tif 000081
でも、以下のようになる：
β・（１＋ｒ）ｄ＝β・（１＋ｄｒ）ｍｏｄＮｒ２  （２）
証明
β＝０ｍｏｄＮなので、式はモジュロＮを取る。β＝１ｍｏｄｒ２なのでこれはモジュロｒ２も取り、いずれの
【数８１】
2011530093.tif 000082
でも、（１＋ｒ）ｄ＝１＋ｄｒｍｏｄｒ２となる。したがって、中国の剰余定理により、式はモジュロＮｒ２を取る。
最後に、式（１）および（２）を組み合わせて、定理１の累乗恒等式を得ると、いずれの
【数８２】
2011530093.tif 000083
およびいずれの
【数８３】
2011530093.tif 000084
でも、以下のようになる：
（ａｍ＋β・（１＋ｒ））ｄ＝ａｍｄ＋β・（１＋ｄｒ）ｍｏｄＮｒ２
【００８４】
Ｂ．故障攻撃の成功確率に関する詳細
４．１において定義された故障モデルを検討してみる。攻撃者は値Ａ（Ａ＝ＢｍｏｄＣ）を変更し、Ａとは無相関の無作為の値Ａを取得すると仮定する。ここでテストＡ＝ＢｍｏｄＣに合格する成功確率の一般式を与えるが、ただしＣはｔビットの整数である。２ｔ−１＜Ｃ＜２ｔ，Ｃ＝１ｍｏｄ２とする。セクション３、４における推奨によれば、ｒは奇数で、その最上位ビットは１であり、ｐにも同じ特性を推測することができる。Ｃは一定であると考える。Ｅは故障が検出されない事象、Ｐｒ［Ｅ］はＥの全確率、Ｐｒ［Ｅ｜Ｃ］はＣを前提とするＥの確率、Ｐｒ［ｃ＝Ｃ］はｃ＝Ｃとなるように考慮された集合Ｓにおいて要素ｃを取る確率、とする。取得される無作為の結果は均一に分布するので、以下のことがわかる：
【数８４】
2011530093.tif 000085
Ｐｒ［Ｅ］を計算することを望む。Ｓ＝｛Ｃｓ．ｔ．２ｔ−１＜Ｃ＜２ｔａｎｄＣ＝１ｍｏｄ２｝としてみる。全確率の定理より、以下のようになる：
【数８５】
2011530093.tif 000086
Ｃは一定なので：
【数８６】
2011530093.tif 000087
恒等式（３）および（５）を式（４）に代入すると、以下が得られる：
【数８７】
2011530093.tif 000088
【数８８】
2011530093.tif 000089
とすると：
【数８９】
2011530093.tif 000090
【数９０】
2011530093.tif 000091
なので、以下のように概算してもよい：
【数９１】
2011530093.tif 000092
したがって：
【数９２】
2011530093.tif 000093
これにより、確率値２−（｜ｐ｜−１）ｌｎ２、２−（｜ｐ’｜−１）ｌｎ２、および２−（｜ｒ｜−１）ｌｎ２が説明される。
【００８５】
同じＣが与えられ、ここで攻撃者が値Ａ（Ａ＝ＢｍｏｄＣ２）を変更し、Ａとは無相関の無作為の値Ａを取得すると仮定する。同じ議論を適用し、テストＡ＝ＢｍｏｄＣ２に合格する成功確率を計算する。この場合、
【数９３】
2011530093.tif 000094
ここでもまだ恒等式（５）が適用される。したがって、恒等式（５）および（６）を式（４）に代入すると：
【数９４】
2011530093.tif 000095
【数９５】
2011530093.tif 000096
同様に、以下のように概算してもよい：
【数９６】
2011530093.tif 000097
したがって：
【数９７】
2011530093.tif 000098
この結果、確率値は２−（２｜ｒ｜＋１）となる。
【図１】
2011530093.tif 000099
【図２】
2011530093.tif 000100
【図３】
2011530093.tif 000101
【国際調査報告】
2011530093.tif 000102
2011530093.tif 000103