(57)【要約】  ＲＳＡおよびＤＳＡのような暗号化システムを、特にセーフエラーインジェクション攻撃に対して保護するためにモンゴメリ乗算の特性を使用する対策が開示される。提案されるアルゴリズムにおいて、２進べき剰余ｂ＝ａｄ  ｍｏｄ  ｎは、指数ｄの現行ビットｄｉがゼロと等しい場合にモンゴメリ乗算を使用して反復的に計算される。その場合、Ｒによるべき乗計算の実際の結果のモンゴメリ乗算が達成される。この対策により、計算中にフォールトインジェクションタイプの摂動が導入された場合、そのような攻撃が秘密鍵ｄの現行ビットｄｉを推定する上で役立たないようにする最終結果に可視の効果をもたらす。
2019515353.tif 000002
【特許請求の範囲】
【請求項１】
第１のメッセージａを受信するステップと、
べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算することにより、第２のメッセージｂを生成するステップを含む暗号化の方法であって、ｄは、変数ｄｉ∈｛０、１｝として、２進表現で
【数１】
2019515353.tif 000009
となるようなｄ＝（ｄｋ−１  ｄｋ−２  ．．．ｄ１ｄ０）２と表される整数であり、ｎは正の整数モジュラスであり、Ｒはｎよりも大きいｇの最小累乗として定義されたモンゴメリ定数であり、ｇはマシン語ベースであり、
べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算するステップは、
第１の変数をＲ  ｍｏｄｕｌｕｓ  ｎに初期化するステップと、
ｄｉが値ｄｋ−１、ｄｋ−２、．．．ｄ１、およびｄ０をそれぞれ続いてとる、反復プロセスをｋ回計算するステップと、を含み、前記反復プロセスの各反復は、
ｄｉが０と等しい場合、第１の変数を、前記第１の変数とＲとのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換える対策を挿入するステップを含む、暗号化の方法。
【請求項２】
べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算するステップが、モンゴメリ変換を使用し、
第１の変数および第２の変数をそれぞれ、Ｒ  ｍｏｄｕｌｕｓ  ｎおよびｃｘＲ  ｍｏｄｕｌｕｓ  ｎに初期化するステップと、
ｄｉが値ｄｋ−１、ｄｋ−２、．．．ｄ１、およびｄ０をそれぞれ続いてとる、反復プロセスをｋ回計算するステップであって、前記反復プロセスの各反復が、
第１の変数を、前記第１の変数と第１の変数とのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換えるステップ、
ｄｉが１と等しい場合、第１の変数を、前記第１の変数と第２の変数とのｍｏｄｕｌｕｓ  ｎでのモンゴメリに置き換えるステップ、および
ｄｉが０と等しい場合、第１の変数を、前記第１の変数とＲとのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換える対策を挿入するステップ、を含む、反復プロセスをｋ回計算するステップと、
第１の変数を、前記第１の変数と１とのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換えるステップとを含む、請求項１に記載の暗号化の方法。
【請求項３】
ＲＳＡ暗号化または復号演算の場合、ａが暗号化メッセージｃであり、ｂが平文メッセージｍである、請求項１に記載の暗号化の方法。
【請求項４】
ＤＳＡ暗号化システムの場合、ａが整数ｇであり、ｂが公開鍵ｙであり、指数ｄが秘密鍵ｘである、請求項１に記載の暗号化の方法。
【請求項５】
モジュラスｎが公開鍵暗号化システムの公開モジュラスである、請求項１または２に記載の暗号化の方法。
【請求項６】
整数ｄが公開鍵暗号化システムの秘密鍵である、請求項１から５のいずれか一項に記載の暗号化の方法。
【請求項７】
整数ｄが１６ビット長または３２ビット長のランダム整数である、請求項１から６のいずれか一項に記載の暗号化の方法。
【請求項８】
計算を高速化するためのスライディングウィンドウ最適化アルゴリズムの実施をさらに含む、請求項１から７のいずれか一項に記載の暗号化の方法。
【請求項９】
プロセッサへアクセス可能であり、プロセッサによって実行されるとき、プロセッサに請求項１から６のいずれか一項に記載の方法のステップを遂行させる命令の１つまたは複数の格納されたシーケンスを備える、コンピュータプログラム製品。
【請求項１０】
第１のメッセージａを受信するためのインターフェイス（３４）と、
べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算することにより、第２のメッセージｂを生成するように構成されたコンピュータユニット（３０）とを備える暗号化システムであって、ｄは、ｄｉ∈｛０、１｝として、２進表現で
【数２】
2019515353.tif 000010
となるようなｄ＝（ｄｋ−１、ｄｋ−２、．．．ｄ１ｄ０）２と表される整数であり、ｎは正の整数モジュラスであり、Ｒはｎよりも大きいｇの最小累乗として定義されたモンゴメリ定数であり、ｇはマシン語ベースであり、
コンピュータユニットは、べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算するために、
第１の変数をＲ  ｍｏｄｕｌｕｓ  ｎに初期化し、
ｄｉが値ｄｋ−１、ｄｋ−２、．．．ｄ１、およびｄ０をそれぞれ続いてとる、反復プロセスをｋ回計算するように構成され、前記反復プロセスの各反復は、
ｄｉが０と等しい場合、第１の変数を、前記第１の変数とＲとのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換える対策を挿入することを含む、暗号化システム。
【請求項１１】
コンピュータユニットが、べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算するためにモンゴメリ変換を使用するように構成され、
第１の変数および第２の変数をそれぞれ、Ｒ  ｍｏｄｕｌｕｓ  ｎおよびａｘＲ  ｍｏｄｕｌｕｓ  ｎに初期化することと、
ｄｉが値ｄｋ−１、ｄｋ−２、．．．ｄ１、およびｄ０をそれぞれ続いてとる、反復プロセスをｋ回計算することであって、前記反復プロセスの各反復が、
第１の変数を、前記第１の変数と前記第１の変数とのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換え、
ｄｉが１と等しい場合、第１の変数を、前記第１の変数と第２の変数とのｍｏｄｕｌｕｓ  ｎでのモンゴメリに置き換え、および
ｄｉが０と等しい場合、第１の変数を、前記第１の変数とＲとのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換える対策を挿入することを含む、反復プロセスをｋ回計算することと、
第１の変数を、前記第１の変数と１とのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換えることと
を行なうように構成される、請求項８に記載の暗号化システム。
【請求項１２】
マシン語ベースｇが２３２と等しい、請求項８および９のいずれか一項に記載の暗号化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化べき乗アルゴリズムへのセーフ−エラーフォールトインジェクション攻撃に対する対策に関する。
【０００２】
本発明は、特に、第１のメッセージａから第２のメッセージｂを、ｂ＝ａｄ  ｍｏｄｕｌｕｓ  ｎ、（ただしｄは秘密鍵であり、ｎは公開モジュラスである）となるように、生成するためのべき剰余計算を含む暗号化の方法に用途を見出す。本発明は、そのような用途において、セーフ−エラーフォールトインジェクション攻撃のような侵略的攻撃に対して暗号化の方法を保護するために使用され得る。さらに詳細には、本発明は、モンゴメリの計算に基づいて対策を使用することを提案する。
【背景技術】
【０００３】
このセクションで説明される手法は推進され得るが、必ずしも以前考案または推進された手法とは限らない。したがって、本明細書において特に指示のない限り、このセクションにおいて説明される手法は、本明細書の特許請求の範囲に対する従来技術ではなく、このセクションに含むことにより従来技術であると認められるものではない。
【０００４】
べき剰余は、特に、ＲＳＡまたはＤＳＡのような暗号システムにおいて使用される。ＲＳＡは、平文メッセージを暗号化して、暗号化メッセージを復号するために使用される暗号化技法であり、ＤＳＡは、所与のメッセージの署名を生成して、そのような署名の妥当性を検証するために使用される暗号化技法である。これらの技法は、公開鍵の論理を使用する。
【０００５】
ＲＳＡの場合、暗号化技法の効率性は、ハッカーにとって膨大な数を因数分解することの困難さに基づいている。ＲＳＡは、３名の発明者、すなわちＲｉｖｅｓｔ、Ｓｈａｍｉｒ、およびＡｄｌｅｍａｎの頭文字をとって命名されており、１９７７年に導入された（Ｒｉｖｅｓｔ、Ｒ．Ｌ、Ｓｈａｍｉｒ、Ａ．、Ａｄｅｌｍａｎ、Ｌ．Ｍ．：「Ａ  ｍｅｔｈｏｄ  ｆｏｒ  ｏｂｔａｉｎｉｎｇ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  ｐｕｂｌｉｃ−ｋｅｙ  ｃｙｐｔｏｓｙｓｔｅｍｓ」、Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＭＩＴ／ＬＣＳ／ＴＭ−８２、１９７７年、を参照）。ＲＳＡは、１９８３年に米国においてＭＩＴにより特許が取得された。米国特許は、２０００年９月２２日に期限切れとなった。
【０００６】
ＤＳＡ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ（デジタル署名アルゴリズム））は、米国においてＮＩＳＴにより標準化されたアルゴリズムである。このアルゴリズムは、１９９３年に実施されたＤＳＳ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｔａｎｄａｒｄ（デジタル署名規格））の一部である。
【０００７】
べき剰余は、ＲＳＡまたはＤＳＡのような公開鍵暗号システムにとって重要な演算である。このべき剰余の結果は、ｂ＝ａｄ  ｍｏｄ  ｎを計算することにより（ただし、指数ｄは秘密鍵に対応する非ゼロの整数であり、ｎは大きな整数の公開モジュラスである）、第２のメッセージｂを与える。実際には、攻撃者が知られている一組（ａ、ｂ）から非公開指数ｋを推定することは実現不可能であることが証明された。
【０００８】
暗号化アルゴリズムにおいてべき剰余を実施する１つの方法は、指数の２進分解を使用することを含む。この、いわゆる「２進べき乗」の方法はまた、「平方乗算」の方法としても知られている。この方法は、１９９７年にＫｎｕｔｈによって説明された。この方法の背後にある概念は、指数ｄの２進表現を使用してａｄを計算することである。したがって、べき乗演算は、一連の平方および乗算演算に分割される。ｋが指数ｄのビット長を示すと仮定すると、前記指数は、２進表現でｄ＝（ｄｋ−１  ｄｋ−２  ．．．ｄ１ｄ０）２および
【数１】
2019515353.tif 000003
と表されてもよい、ただしｄｉ∈｛０、１｝である。
【０００９】
２進べき乗の方法は、べき乗計算を高速化することができる。２進べき乗アルゴリズムは、以下の例示の擬似コードにより実施されてもよく、ここでべき乗は、指数ｄの最上位ビット（ＭＳＢ）から開始して、その最下位ビット（ＬＳＢ）まで進めることによって計算される。
【００１０】
【数２】
2019515353.tif 000004
【００１１】
このアルゴリズムの計算上の複雑さは、ａｄ  ｍｏｄ  ｎを評価するための２×（ｋ／２）＋１×（ｋ／２）＝１．５×ｋの乗算である。したがって、そのようなアルゴリズムはリソースに制限のあるデバイスに適している。
【００１２】
しかし、２進値「１」と等しい指数の各ビットごとに実行される計算は、秘密鍵ｄをハッカーに露呈させるおそれがある。これは、復号プロセスが実行されているときにデバイスの電力消費を解析することによって達成される可能性がある。実際、任意のコンピュータユニットによって計算が実行されている場合は、実行中の計算がない場合の電力消費量と比較すると、極めて高い電力が前記コンピュータユニットによって消費される。したがって、各瞬間において、２進べき乗実施の計算負荷は、処理されている指数の現行ビットの２進値に依存するので、計算器によるカレントシンクを監視することで、前記指数の各ビットを極めて容易に露呈させることができる。
【００１３】
この問題に対処するためのいくつかのオプションが検討されてきた。特に、署名が計算または検証されている間に生じる計算負荷の任意の変動がハッカーにより検出されることを回避するために、対策の導入が提案された。
【００１４】
したがって、「Ｓｑｕａｒｅ−Ａｎｄ−Ｍｕｌｔｉｐｌｙ−Ａｌｗａｙｓ（常時平方乗算）」として知られる、そのような攻撃に対する１つの手段は、スキャンされたビットが「０」である場合に、何も行なわない代わりに、ダミー計算を追加することを含む。そのようなダミー計算は、たとえば、メッセージａの、定数または乱数によるモジュラー乗算であってもよい。その場合、２次べき乗アルゴリズムの上記の擬似コードは、以下のようになる：
【００１５】
【数３】
2019515353.tif 000005
【００１６】
しかし、この対策は、「フォールトインジェクション攻撃」と呼ばれる別の種類の攻撃には脆弱である。フォールトインジェクション攻撃は、誤って計算された結果の数学的および統計的特性を解析することによって秘密鍵を識別するために、欠陥のあるデータを暗号化計算に導入するという概念に基づいている。実際、べき剰余の実行フローを摂動させることにより、（誤った）結果と予想される結果を比較することで、操作された秘密データに関する情報を露呈させることができる。
【００１７】
この攻撃は、秘密鍵の指数の現行ビットが０と等しい場合には、乗算がダミー演算であるのでステップ（２）の間のフォールトインジェクションは影響がない、という事実を使用する。したがって、攻撃は、潜在的なダミー乗算の間に一時的なランダム計算フォールトを導入することにより実行される。指数ビットは、出力の正確性を検査することによって取得されてもよい。
【００１８】
さらに詳細には、上記の例示の擬似コードによって実行されるプロセスのステップ（２）において摂動を導入することは、同所の乗算が実際にはダミー乗算であった場合には最終結果に影響を及ぼさない。同様の方法で、反復計算のステップ（２）において導入された摂動は、同所の乗算が実際の乗算であった場合には、最終結果に可視の影響を及ぼす。続いて以下のような状況になる：
−  最終結果が予想される結果とは異なる場合、それは摂動が実際の乗算中に行なわれており、スキャンされたビット「１」を露呈したことを意味しており、一方
−  最終結果が変更されていない場合、それは摂動がダミー乗算中に行なわれており、スキャンされたビット「０」を露呈したことを意味している。
【００１９】
そのような攻撃を指数の各ビットに繰り返すことにより、および最終結果の含意を解析することにより、ハッカーは指数全体を復元することができる。この指数がＲＳＡ秘密鍵のような重要データである場合、これは極めて有害なものになり得る。
【００２０】
「セーフエラーフォールトインジェクション」と呼ばれる、もう１つのタイプの攻撃があり、これはべき乗の出力を変更しない状態にしておくフォールトである。２次セーフエラー攻撃、つまり攻撃者が同一の計算中に２つのフォールトを注入し、結果が引き続き有効であるかどうかを観察する攻撃を検討してみる。攻撃者が、ｒを乱数としてべき乗ａｒのステップｉにおける乗算の間にフォールトを注入し、ｒ＊＝ｄ−ｒであるべき乗ａｒ＊のステップｉにおける乗算の間にもう１つのフォールトを注入すると仮定する。これらの２つのフォールトは、（ｒｉ、ｒ＊ｉ）＝（０、０）である限り計算に影響を及ぼすことはない。プロセスを繰り返すことにより、攻撃者は、自身の選んだ２進ランクｉのビットに対して（０、０）を得る確率の推定を取得する。この確率は、ビットｄｉの値と強い相関がある。この観察により、攻撃者は秘密指数を知ることができる。これについては、Ｊｏｙｅ、Ｔｕｎｓｔａｌｌによる論文「ＦＡＵＬＴ  ＡＮＡＬＹＳＩＳ  ＩＮ  ＣＲＹＰＴＯＧＲＡＰＨＹ」、第７／８章において詳細に説明されている。
【００２１】
もう１つの対策は、特許文献、国際公開第９８／５２３１９号パンフレット「ＩＭＰＲＯＶＥＤ  ＭＥＴＨＯＤ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＰＲＯＴＥＣＴＩＮＧ  ＰＵＢＬＩＣ  ＫＥＹ  ＳＣＨＥＭＥＳ  ＦＲＯＭ  ＴＩＭＩＮＧ  ＡＮＤ  ＦＡＵＬＴ  ＡＴＴＡＣＫＳ」に説明されているように指数をランダム化することを含む。ａｄ  ｍｏｄ  ｎを計算する代わりに、ａｄ＋ｋ．φ（ｎ）  ｍｏｄ  ｎを計算することができる、ただしｋはランダム整数であり、φはオイラーのφ関数である。ｎ＝ｐ．ｑがＲＳＡモジュラスである場合、これはφ（ｎ）＝（ｐ−１）×（ｑ−１）を与える。したがって、指数はｄ＋ｋ．φ（ｎ）となる。フォールトインジェクション攻撃を効率的に阻止するために、これは少なくとも３２ビット長のランダム整数ｋを使用して検討されてもよい。しかし、指数は非常に長くなり、そのためべき乗全体の計算をさらに多大な時間を要するものにしてしまう。
【００２２】
「ＣＲＹＰＴＯＧＲＡＰＨＩＣ  ＭＥＴＨＯＤ  ＡＮＤ  ＤＥＶＩＣＥ  ＦＯＲ  ＰＲＯＴＥＣＴＩＮＧ  ＰＵＢＬＩＣ−ＫＥＹ  ＳＯＦＴＷＡＲＥ  ＡＧＡＩＮＳＴ  ＦＡＵＬＴ  ＡＴＴＡＣＫＳ」と題する仏国特許ＦＲ２８８４０８８は、上記の計算を２つの別個の計算ステップに分解して、最終結果を最終的に再結合することを開示する。開示される方法によれば、指数は、ランダムな方法でｄ＝ｄ１＋ｄ２に分解され、一方ではａｄ１  ｍｏｄ  ｎ、もう一方ではａｄ２  ｍｏｄ  ｎが計算され、最後に２つの取得された結果が、最終結果を取得するために乗算される。しかし、これには２倍の計算が実行される必要がある。
【００２３】
その他の可能な対策は、加算チェーンの使用（「ＳＥＣＵＲＩＮＧ  ＲＳＡ  ＡＧＡＩＮＳＴ  ＦＡＵＬＴ  ＡＮＡＬＹＳＩＳ  ＢＹ  ＤＯＵＢＬＥ  ＡＤＤＩＴＩＯＮ  ＣＨＡＩＮ  ＥＸＰＯＮＥＮＴＩＡＴＩＯＮ」、Ｒｉｖａｉｎ、ｈｔｔｐｓ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００９／１６５．ｐｄｆ）を含む。これは、追加の一時変数を必要とするが、この変数は各ビットごとに他の変数と共に更新される。計算全体を通じて、これらの２つの変数は、べき乗プロセスの最後に検証され得る共通関係を満足する。関係が保持されない場合、計算は摂動されていることもあり、追加の措置が取られる必要がある。この対策は、第２の一時変数を記憶するためのもう１つのレジスタを必要とし、さらに最終チェック、ひいては追加の計算が必要になる。
【００２４】
「ＭＥＴＨＯＤ  ＡＮＤ  ＤＥＶＩＣＥ  ＦＯＲ  ＣＯＵＮＴＥＲＩＮＧ  ＦＡＵＬＴ  ＡＴＴＡＣＫＳ」と題する特許ＥＰ２２２２０１２は、結果が正しいことを検証するために公開指数「ｅ」を使用することを含む方法を開示する。これは言うまでもなく、加算べき乗および最終比較の計算を意味する。
【００２５】
「ＲＡＮＤＯＭＩＺＥＤ  ＲＳＡ−ＢＡＳＥＤ  ＣＲＹＰＴＯＧＲＡＰＨＩＣ  ＥＸＰＯＮＥＮＴＩＡＴＩＯＮ  ＲＥＳＩＳＴＡＮＴ  ＴＯ  ＳＩＤＥ  ＣＨＡＮＮＥＬ  ＡＮＤ  ＦＡＵＬＴ  ＡＴＴＡＣＫＳ」と題する特許ＵＳ８、１３９、７６３において説明される方法は、指数をランダム化することを含む。結果として得られるランダム化指数は、さらに大きく、さらに多くの計算ループを示唆する。
【００２６】
最後に、「ＲＳＡ  ＰＵＢＬＩＣ  ＫＥＹ  ＧＥＮＥＲＡＴＩＯＮ  ＡＰＰＡＲＡＴＵＳ、ＲＳＡ  ＤＥＣＲＹＰＴＩＯＮ  ＡＰＰＡＲＡＴＵＳ、ＡＮＤ  ＲＳＡ  ＳＩＧＮＡＴＵＲＥ  ＡＰＰＡＲＡＴＵＳ」と題する特許ＥＰ１５３１５７９に開示される方法の概念は、特別な（コストのかさむ）計算および最終チェックを追加することを含む。
【００２７】
追加の特別な演算を提案する上記の対策はすべて、パフォーマンスを著しく低下させることになる。フォールト故障解析攻撃の存在は、パフォーマンスを低下させることなく安全な暗号化アプリケーションを実施する際の特殊な対処の必要性を強調する。
【先行技術文献】
【特許文献】
【００２８】
【特許文献１】国際公開第９８／５２３１９号
【特許文献２】仏国特許発明第２８８４０８８号明細書
【特許文献３】欧州特許出願公開第２２２２０１２号明細書
【特許文献４】米国特許第８、１３９、７６３号明細書
【特許文献５】欧州特許出願公開第１５３１５７９号明細書
【非特許文献】
【００２９】
【非特許文献１】Ｒｉｖｅｓｔ、Ｒ．Ｌ、Ｓｈａｍｉｒ、Ａ．、Ａｄｅｌｍａｎ、Ｌ．Ｍ．：「Ａ  ｍｅｔｈｏｄ  ｆｏｒ  ｏｂｔａｉｎｉｎｇ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  ｐｕｂｌｉｃ−ｋｅｙ  ｃｙｐｔｏｓｙｓｔｅｍｓ」、Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＭＩＴ／ＬＣＳ／ＴＭ−８２、１９７７年
【非特許文献２】「ＦＡＵＬＴ  ＡＮＡＬＹＳＩＳ  ＩＮ  ＣＲＹＰＴＯＧＲＡＰＨＹ」、Ｊｏｙｅ、Ｔｕｎｓｔａｌｌ著、第７／８章
【非特許文献３】「ＳＥＣＵＲＩＮＧ  ＲＳＡ  ＡＧＡＩＮＳＴ  ＦＡＵＬＴ  ＡＮＡＬＹＳＩＳ  ＢＹ  ＤＯＵＢＬＥ  ＡＤＤＩＴＩＯＮ  ＣＨＡＩＮ  ＥＸＰＯＮＥＮＴＩＡＴＩＯＮ」、Ｒｉｖａｉｎ、ｈｔｔｐｓ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００９／１６５．ｐｄｆ
【非特許文献４】「ＨａｎｄＢｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ」Ｍｅｎｅｚｅｓ、ｖａｎ  ＯｏｒｓｃｈｏｔおよびＶａｎｓｔｏｎｅ、第１４章
【発明の概要】
【発明が解決しようとする課題】
【００３０】
前述の事項を考慮すれば、上記で提示されるような既存の解決策への簡単かつ効率的な代替策を提供することにより、セーフエラーインジェクションタイプの可能な攻撃に対する対策をさらに改善する必要がある。
【課題を解決するための手段】
【００３１】
この必要性に対処するため、本発明の第１の態様は、暗号化の方法を提案し、方法は：
第１のメッセージａを受信するステップと、
べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算することにより、第２のメッセージｂを生成するステップであって、ｄは、変数ｄｉ∈｛０、１｝として、２進表現で
【数４】
2019515353.tif 000006
となるようなｄ＝（ｄｋ−１、ｄｋ−２、．．．ｄ１ｄ０）２と表される整数であり、ｎは正の整数モジュラスであり、Ｒはｎよりも大きいｇの最小累乗として定義されたモンゴメリ定数であり、ｇはマシン語ベースである生成するステップとを含み、
べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算するステップは：
第１の変数をＲ  ｍｏｄｕｌｕｓ  ｎに初期化するステップと、
ｄｉが値ｄｋ−１、ｄｋ−２、．．．ｄ１、およびｄ０をそれぞれ続いてとる、反復プロセスをｋ回計算するステップと、を含み、前記反復プロセスの各反復は：
−  ｄｉが０と等しい場合、第１の変数を、前記第１の変数とＲとのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換える対策を挿入するステップを含む。
【００３２】
１つの実施形態において、べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算するステップは、モンゴメリ変換を使用し：
第１の変数および第２の変数をそれぞれ、Ｒ  ｍｏｄｕｌｕｓ  ｎおよびａｘＲ  ｍｏｄｕｌｕｓ  ｎに初期化するステップと、
ｄｉが値ｄｋ−１、ｄｋ−２、．．．ｄ１、およびｄ０をそれぞれ続いてとる、反復プロセスをｋ回計算するステップであって、前記反復プロセスの各反復は：
−  第１の変数を、前記第１の変数と前記第１の変数とのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換えるステップ、
−  ｄｉが１と等しい場合、第１の変数を、前記第１の変数と第２の変数とのｍｏｄｕｌｕｓ  ｎでのモンゴメリに置き換えるステップ、および
−  ｄｉが０と等しい場合、第１の変数を、前記第１の変数とＲとのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換える対策を挿入するステップ、を含む、反復プロセスをｋ回計算するステップと、
第１の変数を、前記第１の変数と１とのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換えるステップとを含む。
【００３３】
ＲＳＡ暗号化または復号演算の場合、メッセージａは暗号化メッセージｃであり、メッセージｂは平文メッセージｍである。
【００３４】
ＤＳＡ暗号化システムの場合、第１のメッセージａは整数ｈであり、第２のメッセージｂは公開鍵ｙであり、指数ｄは秘密鍵ｘである。
【００３５】
表現を変えると、いわゆる「常時平方乗算」の対策の場合のようにダミー乗算ｄｕｍｍｙ＝ｄｕｍｍｙ×ｃ  ｍｏｄ  ｎを計算するのではなく、本発明は、ｒｅｓｕｌｔ＝ＭｏｎｔＭｕｌ（ｒｅｓｕｌｔ、Ｒ、ｎ）を計算することを提案し、ここでＭｏｎｔＭｕｌはオペランドのセット（ｒｅｓｕｌｔ、Ｒ、ｎ）に適用されるモンゴメリ乗算演算を指定する。このようにして、任意のオペランドおよび／またはこの計算ステップの成果におけるわずかな摂動は、２進べき乗計算の最終結果の変更をもたらすことになる。
【００３６】
モンゴメリ乗算は、特に、「ＨａｎｄＢｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ」Ｍｅｎｅｚｅｓ、ｖａｎ  ＯｏｒｓｃｈｏｔおよびＶａｎｓｔｏｎｅ著、第１４章、において説明されている。
【００３７】
当業者は、モンゴメリ乗算の定義により、ダミー演算の代わりにこの演算を導入することで最終結果を変更することはないと理解するであろう。
【００３８】
それでもなお、この対策を加えることは、たとえばＲＳＡアルゴリズムにおけるべき剰余の間、べき乗アルゴリズムの任意の瞬間における任意の摂動が、結果として最終結果の変更をもたらすという影響を及ぼす。この利点は、この対策の演算が最終結果にリンクされているということに由来する。
【００３９】
表現を変えると、モンゴメリ乗算を使用することで、通常の場合には２進べき乗計算には影響を及ぼさないが、前述の特性は、この計算中に導入された任意のフォールトが、最終結果に可視の影響を及ぼすという結果をもたらす。
【００４０】
したがって、本発明は、（ＲＳＡ、ＤＳＡのような）任意の公開鍵暗号システムのべき乗演算中、べき剰余の計算にモンゴメリ乗算を使用することによって、セーフエラーインジェクションタイプの可能な攻撃を阻止するための単純かつ効率的な解決策を提供する。
【００４１】
そのような方法でモンゴメリ乗算を使用することは、たとえそれがべき剰余計算を高速化するために集中的に使用されていたとしても、新奇かつ非自明である。
【００４２】
有利なことに、提案される解決策の実施形態は、任意の公開鍵暗号システムにおいて使用可能な高速かつ軽量の復号プロセスを提供する。実際、本発明の解決策は、フォールトが攻撃者に何も露呈しないことを考えれば、計算中にセーフエラーフォールトが導入されていないことを保証するために特別なチェック演算を使用する必要を回避するので、既存の方法よりも高速である。加えて、この解決策は、アルゴリズムが追加のデータを記憶するための特別なレジスタを必要としないので、容易に使用可能な技法よりも軽量である。したがって、これはメモリが最適化されている。言い換えれば、提案される「モンゴメリ乗算」の対策は、計算パフォーマンスおよびメモリ容量の観点から非常にコストがかさむセーフエラーインジェクション攻撃に対障害弾力性のあるその他の対策の、有利な代替策である。
【００４３】
本発明はまた、たとえばスライディングウィンドウアルゴリズムのような、計算を高速化するために実施され得る追加の最適化にも適合する。
【００４４】
本発明の第２の態様は、プロセッサへアクセス可能であり、プロセッサによって実行されるとき、プロセッサに本発明の第１の態様の方法のステップを遂行させる命令の１つまたは複数の格納されたシーケンスを備えるコンピュータプログラム製品に関する。
【００４５】
最後に、本発明の第３の態様は、暗号化システムに関し、暗号化システムは：
第１のメッセージａを受信するためのインターフェイスと、
べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算することにより、第２のメッセージｂを生成するように構成されたコンピュータユニットであって、ｄは、ｄｉ∈｛０、１｝として、２進表現で
【数５】
2019515353.tif 000007
となるようなｄ＝（ｄｋ−１  ｄｋ−２  ．．．ｄ１ｄ０）２と表される整数であり、ｎは正の整数モジュラスであり、Ｒはｎよりも大きいｇの最小累乗として定義されたモンゴメリ定数であり、ｇはマシン語ベースであるコンピュータユニットとを備え、
コンピュータユニットは、べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算するために：
−  第１の変数をＲ  ｍｏｄｕｌｕｓ  ｎに初期化し、
−  ｄｉが値ｄｋ−１、ｄｋ−２、．．．ｄ１、およびｄ０をそれぞれ続いてとる、反復プロセスをｋ回計算するように構成され、前記反復プロセスの各反復は：
ｄｉが０と等しい場合、第１の変数を、前記第１の変数とＲとのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換える対策を挿入することを含む。
【００４６】
１つの実施形態において、コンピュータユニットは、べき剰余ｂ＝ａｄ  ｍｏｄ  ｎを計算するためにモンゴメリ変換を使用するように構成され：
第１の変数および第２の変数をそれぞれ、Ｒ  ｍｏｄｕｌｕｓ  ｎおよびａｘＲ  ｍｏｄｕｌｕｓ  ｎに初期化することと、
ｄｉが値ｄｋ−１、ｄｋ−２、．．．ｄ１、およびｄ０をそれぞれ続いてとる、反復プロセスをｋ回計算することであって、前記反復プロセスの各反復は：
−  第１の変数を、前記第１の変数と前記第１の変数とのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換え、
−  ｄｉが１と等しい場合、第１の変数を、前記第１の変数と第２の変数とのｍｏｄｕｌｕｓ  ｎでのモンゴメリに置き換え、および
−  ｄｉが０と等しい場合、第１の変数を、前記第１の変数とＲとのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換える対策を挿入することを含む、計算することと、
第１の変数を、前記第１の変数と１とのｍｏｄｕｌｕｓ  ｎでのモンゴメリ乗算に置き換えることと、を行なうように構成される。
【００４７】
そのような暗号化システムは、たとえば、ＲＳＡまたはＤＳＡ暗号システムであってもよい。
【００４８】
一部の実施形態において、マシン語ベースｇは２３２と等しくてもよい。
【００４９】
本発明の実施形態は、類似する参照番号が類似した要素を示す添付の図面の図解に、限定としてではなく、一例として示されている。
【図面の簡単な説明】
【００５０】
【図１】提案される「モンゴメリ乗算」の対策を行なわずに２進べき乗を計算するための「常時平方乗算」タイプのアルゴリズムのステップを示す流れ図である。
【図２】モンゴメリ乗算の対策による２進べき乗計算を計算するためのアルゴリズムのステップを示す流れ図である。
【図３】第２の態様によるコンピュータプログラム製品を実行するように構成された、本発明の第３の態様による暗号システムの実施形態を示すブロック図である。
【発明を実施するための形態】
【００５１】
図１の流れ図を参照すると、提案される「モンゴメリ乗算」の対策を用いずにべき乗ｂ＝ａｄ  ｍｏｄ  ｎを計算するための２進アルゴリズムの実施形態が最初に説明される。表現を変えると、図１は、たとえば「常時平方乗算」のような対策が２進べき乗プロセスに導入される方法の流れ図を示す。
【００５２】
ＲＳＡ暗号化または復号演算の場合、メッセージａは暗号化メッセージｃであり、メッセージｂは平文メッセージｍである。
【００５３】
ＤＳＡ暗号化システムの場合、第１のメッセージａは整数ｈであり、第２のメッセージｂは公開鍵ｙであり、指数ｄは秘密鍵ｘである。
【００５４】
示される実施形態によるアルゴリズムは、以下のステップ１１から１６を含む。
【００５５】
ステップ１１において、復号演算に使用されるさまざまな入力が定義され、それらの変数は、公開モジュラスｎ、秘密鍵ｄ、および第１のメッセージａを含む。
【００５６】
１つの実施形態において、公開モジュラスｎは、大きな数である。１つの例において、ｎは、素数であってもよい。しかし、本発明の実施形態がそのような例に限定されることを意図されていないことが、当業者には理解されよう。
【００５７】
秘密鍵ｄは、ｄ＝（ｄｋ−１  ｄｋ−２  ．．．ｄ１ｄ０）２のような２進表現で表されてもよい、ただしｋは１よりも大きい整数である。
【００５８】
ステップ１２において、変数のｒｅｓｕｌｔおよびｄｕｍｍｙは、いずれも１に初期化される、つまりｒｅｓｕｌｔ＝１、およびｄｕｍｍｙ＝１である。
【００５９】
ステップ１３において、反復ｆｏｒ−ｌｏｏｐプロセスが開始され、それぞれｋ−１から０までの範囲のインデックスｉについてｋ回実行される、つまり指数ｄのｋ個の２進要素（ビット）ｄｋ−１、ｄｋ−２、．．．ｄ１、およびｄ０の各１つごとに連続して実行され、たとえばＭＳＢ（最上位ビット）から始まりＬＳＢ（最下位ビット）で終了する。
【００６０】
ステップ１４において、変数ｒｅｓｕｌｔの平方計算が達成される。さらに具体的には、変数ｒｅｓｕｌｔは、ｒｅｓｕｌｔ  ×  ｒｅｓｕｌｔ  ｍｏｄ  ｎに置き換えられる。
【００６１】
指数の現行ビットｄｉが「１」と等しい場合、ステップ１５において、変数ｒｅｓｕｌｔは、ｒｅｓｕｌｔ  ×  ａ  ｍｏｄ  ｎに置き換えられる。
【００６２】
それ以外の場合、つまり指数の現行ビットｄｉが「０」と等しい場合、ステップ１６において、対策ｄｕｍｍｙ  ×  ａ  ｍｏｄ  ｎが挿入される。これは、変数ｒｅｓｕｌｔをｄｕｍｍｙ  ×  ａ  ｍｏｄ  ｎに置き換えることにより得られる。
【００６３】
本発明の背後にある概念は、ダミー演算を、最終結果ａｄ  ｍｏｄ  ｎに可視の影響を常に及ぼすその他の演算に置き換えることである。
【００６４】
簡単な方法は、ダミー演算を、１による乗算に置き換えることであろう。最終結果は、摂動がない場合には影響を受けることはなく、この計算の間の摂動は、高い確率で、最終結果の変更をもたらす。したがって、一部の場合においてはフォールトインジェクション攻撃に対抗することができる。しかし、「１」のハミング重みは１であるので、この１ビットの変更は、結果としてヌル出力をもたらすことになる。したがって、これは実行されている演算に関する情報を与えることになり、攻撃者が秘密鍵の値を推定することを手助けするおそれがある。
【００６５】
同じ結果を達成するさらに安全な方法は、実施形態によりモンゴメリ乗算を利用する。
【００６６】
べき剰余は、固有の乗算および除算演算により、複雑な算術演算であると見なされるが、数学者Ｐｅｔｅｒ  Ｌ．Ｍｏｎｔｇｏｍｅｒｙは、２つの整数（ｎ−剰余と称される）を、ｎによる除算を回避しながらモジュロｎで乗算するためのモジュラーリダクションアルゴリズムを導入した（１９８５年）。技術文献（たとえば「ＨａｎｄＢｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ」Ｍｅｎｅｚｅｓ、ｖａｎ  Ｏｏｒｓｃｈｏｔ、Ｖａｎｓｔｏｎｅ、第１４章を参照）において、モンゴメリ計算の特性は、べき乗に必要とされるモジュラー乗算および平方演算を高速化するために使用されてきた。これは、モンゴメリリダクションが後に続く単純長整数乗算として実施され、前記モンゴメリリダクションは、モンゴメリ変換のいわば「逆」演算である。
【００６７】
つまり、以下のように仮定すると：
−  ｎは大きな整数のモジュラスであり、
−  ｐは２ｎ未満の整数であり（つまり、ｐ＜２ｎ）、
−  Ｒはいわゆるモンゴメリ定数である、
すると、ａのモンゴメリ型は：ｐ×Ｒ  ｍｏｄ  ｎによって定義され、
モンゴメリリダクションは：ｐ×Ｒ−１  ｍｏｄ  ｎによって定義され、ただしＲ−１はＲの逆数であり、
モンゴメリ乗算ＭｏｎｔＭｕｌは入力（ｐ、ｑ、ｎ）で値ｐ×ｑ×Ｒ−１  ｍｏｄ  ｎを計算する。
【００６８】
図２の流れ図を参照して、これ以降、本発明の第１の態様の例示的な実施形態が説明される。この態様は、本発明の実施形態により提案されるモンゴメリ乗算の対策によりべき乗ａｄ  ｍｏｄｕｌｕｓ  ｎの計算を可能にするアルゴリズムに基づく暗号化方法に関連する。いわゆるモンゴメリ定数Ｒは、ｎよりも大きいｇの最小累乗として定義される、ただしｇはマシン語ベースである（３２ビットシステムで、たとえば、ｇ＝２３２）。１つの例において、ｇは２３２と等しい。しかし、ｇはまた、たとえば２１６または２６４とも等しい場合もあるので、これは単に例示にすぎない。
【００６９】
ステップ２１において、方法を実施するためにコンピュータ手段によって使用されるさまざまな入力：モジュラスｎ、２進表現でｄ＝（ｄｋ−１  ｄｋ−２  ．．．ｄ１ｄ０）２と表される秘密鍵ｄ、および第１のメッセージａが定義されるかまたは受信される。
【００７０】
ステップ２２において、変数ｒｅｓｕｌｔおよびａはそれぞれ、Ｒ  ｍｏｄ  ｎおよびａ×Ｒ  ｍｏｄ  ｎに初期化され、Ｒはｎよりも大きいｆの最小累乗である。
【００７１】
ステップ２３において、指数ｄのｋ個の２進要素、つまりビットのｋ−１から０までの反復を達成するｆｏｒループが開始される。さらに詳細には、この例において、指数ｄのｋビットは、ＭＳＢからＬＳＢまで処理される。ＬＳＢからＬＳＢへの計算を実行することもまた有効なオプションであることが、当業者には理解されよう。
【００７２】
ステップ２４において、平方された変数ｒｅｓｕｌｔ（つまりｒｅｓｕｌｔ×ｒｅｓｕｌｔ）のモンゴメリ乗算が実行される：ｒｅｓｕｌｔ×ｒｅｓｕｌｔ×Ｒ−１  ｍｏｄ  ｎ。
【００７３】
ステップ２５において、指数ｄのビットｄｉが「１」と等しい場合、ｒｅｓｕｌｔとａとのモンゴメリ乗算、つまりｒｅｓｕｌｔ×ａ×Ｒ−１ｍｏｄｕｌｕｓ  ｎが計算され、変数ｒｅｓｕｌｔはその値に更新される、つまりその値に置き換えられる。
【００７４】
指数の現行ビットが「０」と等しい場合、ステップ２６において、Ｒとのｒｅｓｕｌｔのモンゴメリ乗算を達成する対策が挿入される。さらに具体的には、変数ｒｅｓｕｌｔは、ｒｅｓｕｌｔ×Ｒ×Ｒ−１  ｍｏｄｕｌｕｓ  ｎに置き換えられる。
【００７５】
ステップ２７において、プロセスは、モンゴメリ型から通常の形に戻ることで終了する。これは、１との変数ｒｅｓｕｌｔのモンゴメリ乗算を計算することにより達成されてもよい。つまり、ｒｅｓｕｌｔは、ｒｅｓｕｌｔ×１×Ｒ−１  ｍｏｄｕｌｕｓ  ｎに置き換えられる。
【００７６】
当技術分野においてすでに知られている対策の１つは、ダミー乗算を２進べき乗アルゴリズムに追加することを含む。本発明の実施形態によれば、モンゴメリ乗算ＭｏｎｔＭｕｌ（ｒｅｓｕｌｔ、Ｒ、ｎ）を実行することによりこのダミー乗算を変更することが提案される。
【００７７】
この方法を使用して、この計算中の任意のオペランドおよび／または任意のステップの摂動は、これが最終結果の変更をもたらすことになるので、ハッカーに秘密鍵の現行ビットｄｉを識別させないようにする。したがって、提案される対策は、セーフエラーフォールトインジェクション攻撃に対して効率的である。
【００７８】
モンゴメリ乗算によるダミー乗算の変更は、通常の場合、つまりいかなるインジェクション攻撃もない場合に、最終結果を変更することはない。これは、以下の恒等特性を提供するモンゴメリ乗算の定義に起因する：
ＭｏｎｔＭｕｌ（ｒｅｓｕｌｔ、Ｒ、ｎ）＝ｒｅｓｕｌｔ×Ｒ×Ｒ−１  ｍｏｄ  ｎ＝ｒｅｓｕｌｔ  ｍｏｄ  ｎ
【００７９】
本発明の特に有利な効果は、方法が、モンゴメリ変換を使用してべき剰余が計算される間に使用される場合に達成される。実際に、モンゴメリ乗算の消費シグネチャは、モジュラー乗算のものとは異なることがあり、したがって、べき剰余がモンゴメリ変換を使用して計算される場合、提案される「モンゴメリ乗算」の対策を使用する利点は、ｄｉが「０」と等しい場合およびｄｉが「１」と等しい場合に実行される計算に対する電力消費のいかなる差も、この対策が完全に除去することである。
【００８０】
しかし、モンゴメリ変換を使用してべき剰余を計算することが必須ではないことが、当業者には理解されよう。実際、本発明の実施形態による「モンゴメリ乗算」の対策は、ｄｉが「０」と等しい場合に反復の処理を変更することのみによって実施され得る。そのような実施態様において、すべてのその他のステップは、標準の「ダミー計算」の対策が使用される図１のステップと同一である。特に、ｄｉが「１」と等しい場合の反復の処理は、標準のモジュラー乗算であってもよい。
【００８１】
実施形態において、提案される「モンゴメリ乗算」の対策によるべき乗アルゴリズムは、たとえば、以下の擬似コードによって実施されてもよい。
【００８２】
【数６】
2019515353.tif 000008
【００８３】
図３のブロック図を参照して、これ以降、本発明の第３の態様による暗号システムの実施形態が説明される。そのような暗号システムは、プロセッサへアクセス可能であり、プロセッサによって実行されるとき、プロセッサに暗号化の方法を遂行させる命令の１つまたは複数の格納されたシーケンスを備えるコンピュータプログラム製品を実行するように構成されたコンピュータユニットを備えることができる。
【００８４】
示される実施形態において、コンピュータユニット３０は、少なくとも１つのプロセッサ３１、プロセッサ３１による計算の実行中に使用されるデータを記憶するための少なくとも１つのメモリ３２、およびたとえば方法を適正に実行するための固有のパラメータまたは実行コマンドを記憶するために使用される少なくとも１つの再書き込み可能な不揮発性メモリ３３を備える。
【００８５】
メモリ３２は、たとえばＳＲＡＭ、ＤＲＡＭ、またはＳＤＲＡＭのような任意の適切なタイプのランダムアクセスメモリ（ＲＡＭ）であってもよい。メモリ３３は、たとえばＥＰＲＯＭまたはフラッシュメモリのような任意の適切なタイプの読み取り専用メモリ（ＲＯＭ）であってもよい。
【００８６】
暗号システムは、メッセージａ、たとえばＲＳＡのコンテキストで復号されるべきメッセージｃを受信するため、およびメッセージｂ、たとえば前記コンテキストで一度復号された平文ｍを送出するための、インターフェイス３４（Ｉ／Ｆ）をさらに備える。
【００８７】
本発明は、計算中にセーフエラーフォールトが導入されていないことを保証するために特別なチェックを使用する必要を回避する。これは、アルゴリズムの計算をさらに高速にすることができる。このアルゴリズムはまた、追加のデータを記憶するための特別なレジスタを必要としないので、メモリ最適化される。
【００８８】
これはまた、単純電力解析（ＳＰＡ：Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）に影響を受けない。ＳＰＡは、乗算と平方が結果として同じ電力消費をもたらすわけではないという自然なアイデアに基づいている。したがって、これは受動的な攻撃であり、ハッカーはべき剰余を実行している暗号化デバイスの電力トレースを監視する。実際に実行された平方および乗算のシーケンスを電力トレースから取り出して、そこから暗号システムに使用される重要な情報を推定しようとする者もいる。
【００８９】
本発明の実施形態は、ＲＳＡアルゴリズムの復号演算のコンテキスト内で上記で説明されてきた。しかし、本発明がこの例に限定されることはなく、本発明が、たとえばＤＳＡのようなその他の公開鍵暗号化システム（暗号システム）において具現されてもよいことに留意されたい。
【００９０】
加えて、本発明はまた、コンピューティングデバイスが、任意の変数ｅ、ｆ、Ｒ、ｎについてｅ×ｆ×Ｒ−１  ｍｏｄ  ｎの計算を計算する演算を実施する任意のアプリケーションにおいて使用されてもよい。その場合、デバイスは、モンゴメリ型の変数ｅおよびｆを変換するためにｅ’＝ｅ×Ｒ  ｍｏｄ  ｎおよびｆ’＝ｆ×Ｒ  ｍｏｄ  ｎを最初に計算し、次いでｅおよびｆの代わりに、それぞれｅ’およびｆ’を使用して上記で説明される演算を実行する。
【００９１】
最後に、提案される方法が、たとえばスライディングウィンドウアルゴリズムのような、計算を高速化するためのさまざまな知られている追加の最適化プロセスの実施と適合することが、当業者によってさらに理解されるであろう。
【図１】
2019515353.tif 000011
【図２】
2019515353.tif 000012
【図３】
2019515353.tif 000013
【国際調査報告】
2019515353.tif 000014
2019515353.tif 000015