(57)【要約】【課題】本発明は、秘密鍵を有する電子式暗号化集合を、暗号解析的な攻撃から保護する方法に関する。【解決手段】本方法は、ａ）標準の暗号化計算方法を、標準の暗号化計算の結果とは別個の部分中間結果を用いて、いくつかの別個の並行処理段階に分割するステップと、ｂ）当該別個の部分中間結果から最終値を再構成するステップとからなる。本発明は、組み込みシステムなどの電子的な集合にとって有用である。【選択図】図２
2010072664.tif 000002
【特許請求の範囲】
【請求項１】
秘密鍵を用いる標準の暗号化計算方法を実現するコンピュータシステムを保護する方法であって、
ａ）前記標準の暗号化計算方法が、並行に実行され、前記標準の暗号化計算の結果とは別個の部分中間結果（ｖ１〜ｖｋ）を生成する、別個の複数の暗号化計算方法の部分（ＰＰＣ１〜ＰＰＣｋ）に分割され、
ｂ）分割することなく前記標準の暗号化計算によって得られる最終値（ｖ）を、前記別個の部分中間結果（ｖ１〜ｖｋ）から再構成することを特徴とする方法。
【請求項２】
前記標準の暗号化計算方法によって用いられる入力データ又は出力データに依存する中間変数又は中間結果（ｖ）の各々が、任意の数であるｋ個の部分中間変数（ｖ１〜ｖｋ）で置き換えられ、
前記中間変数（ｖ）と部分中間変数（ｖ１〜ｖｋ）が、関数ｆによってリンクされ、
ｖ＝ｆ（ｖ１、ｖ２、．．．、ｖｋ）によって、前記中間変数（ｖ）を再構成できることを特徴とする請求項１に記載の方法。
【請求項３】
前記部分中間変数（ｖ１〜ｖｋ）と前記中間変数（ｖ）をリンクする関数ｆが、前記中間変数（ｖ）の１つの値が分かっても、現存する（ｋ−１）項組（ｖ１、．．．、ｖｉ−１、ｖｉ＋１、．．．、ｖｋ）が、式ｆ（ｖ１、．．．、ｖｉ、．．．、ｖｋ）＝ｖを満たすように、特定の部分の値（ｖｉ）のすべてを演繹することが不可能な関数であることを特徴とする請求項２に記載の方法。
【請求項４】
前記関数ｆが、ビット毎の「排他的論理和」関数であり、前記中間変数又は中間結果（ｖ）と部分中間変数（ｖ１、．．．、ｖｉ、．．．、ｖｋ）が、関係式
【数１】
2010072664.tif 000016
を満たすことを特徴とする請求項３に記載の方法。
【請求項５】
ｎを法とする整数のすべてによって定義される乗法群Ｚ／ｎＺにおける値を有する中間変数（ｖ）に対して、前記関数ｆが、ｎを法とする積関数ｆ（ｖ１、．．．、ｖｋ）＝ｖ１・ｖ２・．．．・ｖｋ  ｍｏｄｕｌｏ  ｎであり、前記部分中間変数（ｖ１、．．．、ｖｉ、．．．、ｖｋ）が、前記乗法群Ｚ／ｎＺにおける値を有する変数であることを特徴とする請求項３に記載の方法。
【請求項６】
前記関数ｆが、前記部分中間変数（ｖ１、．．．、ｖｉ、．．．、ｖｋ）と前記中間変数（ｖ）をリンクし、並行に実行される別個の暗号化計算方法の部分（ＰＰＣ１〜ＰＰＣｋ）が、互いに独立しており、前記並行に実行される別個の暗号化計算方法の部分（ＰＰＣ１〜ＰＰＣｋ）が、前記標準の暗号化計算方法によって用いられる入力データ又は出力データに依存する中間変数（ｖ）を再構成することなく実行されることを特徴とする請求項３に記載の方法。
【請求項７】
分割が、並行に実行される２つの別個の部分に行われることを特徴とする請求項１に記載の方法。
【請求項８】
分割が、ｋ個の部分に行われ、
変換されたｎ個の出力ビットが、ｍ個の入力ビットの関数であるアドレスで読み取られる変換テーブルによって記載される、ｍ個のビットからｎ個のビットへの非線形変換を用いる標準の暗号化計算方法に対して、分割することなく標準の暗号化計算方法の中間変数に適用される非線形変換の各々が、前記部分中間変数のすべてに適用されるｋ×ｍ個のビットからｋ×ｎ個のビットへの部分非線形変換によって置き換えられ、
前記部分非線形変換が、前記変換されたｎ個の出力ビットが、前記ｋ×ｍ個の入力ビットの関数であるアドレスで読み取られるｋ個の部分変換テーブルで記載されることを特徴とする請求項１に記載の方法。
【請求項９】
前記ｋ個の部分変換テーブルの内、（ｋ−１）個の部分変換テーブルが、秘密ランダム変数を含んでいることを特徴とする請求項８に記載の方法。
【請求項１０】
各非線形変換テーブルを置き換えるように用いられるｋ個の部分変換テーブルの内、同じ（ｋ−１）個の秘密ランダムテーブルが、毎回用いられることを特徴とする請求項８に記載の方法。
【請求項１１】
分割が、ｋ個の部分に行われ、
前記変換されたｎ個の出力ビットが、前記ｍ個の入力ビットの関数であるアドレスで読み取られる変換テーブルによって記載されるｍ個のビットからｎ個のビットへの非線形変換を用いる標準の暗号化計算方法に対して、分割することなく前記標準の暗号化計算方法の中間変数に適用される非線形変換が、前記部分中間変数のすべてに適用されるｋ×ｍ個のビットからｋ×ｎ個のビットへの部分非線形変換によって置き換えられ、
前記変換された出力ビットの内の（ｋ−１）×ｎ個のビットが、前記ｋ×ｍ個の入力ビットの多項式関数として計算され、
前記出力ビットの内の残余のｎ個のビットが、前記ｋ×ｍ個の入力ビットの関数であるアドレスで読み取られる変換テーブルを読み取ることによって得られることを特徴とする請求項１に記載の方法。
【請求項１２】
分割が、ｋ個の部分に行われ、
前記変換されたｎ個の出力ビットが、前記ｍ個の入力ビットの関数であるアドレスで読み取られる変換テーブルによって記載されるｍ個のビットからｎ個のビットへの非線形変換を用いる標準の暗号化計算方法に対して、分割することなく前記標準の暗号化計算方法の中間変数に適用される各非線形変換が、前記部分中間変数のすべてに適用されるｋ×ｍ個のビットからｋ×ｎ個のビットへの部分非線形変換によって置き換えられ、
前記部分非線形変換が、ｋ個の変換テーブルによって記載され、
前記変換テーブルの各々が、関係式φｊ○ｆ（ｖ１、．．．、ｖｋ）、ｊ∈［１、ｋ］に従って、前記部分中間変数の関数ｆ（ｖ１、．．．、ｖｋ）に対して秘密全単射関数φ１を適用することによって得られる値を入力として受容し、
φｊ○ｆ（ｖ１、．．．、ｖｋ）の適用が、結果として生じる値を、直接的に評価することによって実行され、
前記結果として生じる値が、前記変換テーブルの入力に適用され、これによって、前記ｍ個の入力ビットの関数であるアドレスで、前記変換されたｎ個の出力ビットを読み取ることが可能であることを特徴とする請求項２に記載の方法。
【請求項１３】
前記ｋ個の部分変換テーブルの内、（ｋ−１）個の部分変換テーブルが、秘密ランダム値を包含することを特徴とする請求項１２に記載の方法。
【請求項１４】
各非線形変換テーブルを置き換えるように用いられるｋ個の部分変換テーブルの内、同じ（ｋ−１）個の秘密ランダム変換テーブルが、毎回用いられることを特徴とする請求項１２に記載の方法。
【請求項１５】
前記暗号化計算方法を複数の別個の暗号化計算方法の部分に分割したことに起因する様々な部分において実行される動作が、連続的に実行されることを特徴とする請求項１に記載の方法。
【請求項１６】
前記暗号化計算方法を複数の別個の暗号化計算方法の部分に分割したことに起因する様々な部分において実行される動作が、インタリーブ形式で実行されることを特徴とする請求項１に記載の方法。
【請求項１７】
前記暗号化計算方法を複数の別個の暗号化計算方法の部分に分割したことに起因する様々な部分において実行される動作が、マルチプログラミングの場合では、同時並行的に実行されることを特徴とする請求項１に記載の方法。
【請求項１８】
前記暗号化計算方法を複数の跋扈の暗号化計算方法の部分に分割したことに起因する様々な部分において実行される動作が、並行に動作する別々のプロセッサで同時に実行されることを特徴とする請求項１に記載の方法。
【請求項１９】
請求項１に記載の方法をスマートカードで利用することを特徴とする方法。
【請求項２０】
ＤＥＳ、トリプルＤＥＳ及びＲＳＡアルゴリズムによってサポートされる暗号化計算方法を保護するために、請求項１に記載の方法を利用することを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密鍵を用いた暗号化アルゴリズムを実現するコンピュータシステムを保護する方法に関する。より正確には、その方法の目的は、計算の実行中におけるコンピュータシステムの電力消費量の検討を通じて秘密鍵上の情報を得ることを目的とした「差分電力解析（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）」又は「高次差分電力解析（Ｈｉｇｈ−Ｏｒｄｅｒ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ）」として知られる特定のタイプの物理的攻撃に対して脆弱でないアルゴリズムのバージョンを提供することである。
【背景技術】
【０００２】
ここで考察される暗号化アルゴリズムは、出力情報を、入力情報の関数として計算する秘密鍵を用いる；これには、暗号化、復号化、署名、署名の検証、認証又は非拒絶の操作が含まれる。それらは、入力及び出力を知っている攻撃者が、秘密鍵それ自身上のいかなる情報も事実上演繹することができないような方法で構成される。
【０００３】
われわれは、「秘密鍵アルゴリズム」又は「対称アルゴリズム」という表現で以前から表されているクラスよりも大きいクラスに関わっている。特に本特許の応用例で説明される全てが、さらにいわゆる「公開鍵アルゴリズム」又は「非対称アルゴリズム」に適合し、当該アルゴリズムは、２つの鍵（一方は公開で、他方は個人又は非公開であり、後者は以下に説明される攻撃の目標となる鍵である）を含む。
【０００４】
ポール・コッヘル及びＣｒｙｐｔｏｇｒａｐｈｉｃ  Ｒｅｓｅａｒｃｈ社によって開発された電力解析（参照として本明細書に組み込まれる、ＵＲＬアドレスｈｔｔｐ：／／ｗｗｗ．ｃｒｙｐｔｏｇｒａｐｈｙ．ｃｏｍ／ｄｐａ／ｔｅｃｈｎｉｃａｌ／ｉｎｄｅｘ．ｈｔｍｌにおいてＨＴＭＬ文書として公開された、ポール・コッヘル、ジョシュア・ジャフィ、ベンジャミン・ジュン及びＣｒｙｐｔｏｇｒａｐｈｉｃ  Ｒｅｓｅａｒｃｈ社、カリフォルニア州９４１０２、サンフランシスコ、スーツ１００８、マーケットストリート８７０による文書「Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ」を参照）として知られるタイプの攻撃は、攻撃者（アタッカー）が、例えば、マイクロコントローラの電力消費量又は回路から発せられる電磁放射等の計算の実行中に、入力及び出力データ以外の情報を、事実上取得できるという観察に基づいている。
【０００５】
「ＤＰＡ」と略記される差分電力解析は、秘密鍵における多数の計算において電力消費量の測定を行うことにより、コンピュータシステム内に収容されるこの秘密鍵に関する情報を得ることを可能にする攻撃である。
【０００６】
非制限的な例として、われわれは、ＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ：データ暗号化基準）アルゴリズムの場合を考察するが、その説明は、以下の文書のいずれの中にも見出すことができる：
ＦＩＰＳ  ＰＵＢ４６−２、「Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ」、１９９４年；
ＦＩＰＳ  ＰＵＢ７４、「Ｇｕｉｄｌｉｎｅ  ｆｏｒ  Ｉｍｐｌｅｍｅｎｔｉｎｇ  ａｎｄ  Ｕｓｉｎｇ  ｔｈｅ  ＮＢＳ  Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ」、１９８１年；
ＡＮＳＩ  Ｘ３．９２「Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄ，  Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ」、１９８１年；
ＩＳＯ／ＩＥＣ８７３１、「Ｂａｎｋｉｎｇ−Ａｐｐｒｏｖｅｄ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ−パート１：Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ（ＤＥＡ）」、１９８７；
又は、以下の書籍の中に見出すことができる：
ブルース・シュナイヤー、「Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ」第２版、ジョン・ワイリー＆サン、１９９６年、２７０ページ。
【０００７】
上記の文書は、参照として本明細書に組み込まれる。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ＤＥＳアルゴリズムは、ラウンドとして周知の１６のステップにおいて実行される（図１ａを参照）。１６のラウンドのそれぞれにおいて、３２ビットへの変換Ｆが実行される。この変換Ｆは、６ビットから４ビットへの８つの非線形変換を用い、その各々は、「Ｓボックス」と呼ばれるテーブルにおいて符号化される（図１ｂを参照、そこにおいて、Ｓボックスは、Ｓ１、Ｓ２、…、ＳＳとマーク付けされている）。
【０００９】
ＤＥＳ上でのＤＰＡ攻撃は、以下の方法によって実行される：
第１ステップ：電力消費量の測定は、第１ラウンドにおいて、１，０００個のＤＥＳ計算に対して行われる。これら１，０００個の計算の入力値は、Ｅ［１］、…、Ｅ［１，０００］とマーク付けされる。これらの計算中に測定された対応する１，０００個の電力消費量曲線は、Ｃ［１］、…、Ｃ［１，０００］とマーク付けされる。１，０００個の消費量曲線の平均の曲線ＣＭが、さらに計算される。
【００１０】
第２ステップ：第１ラウンド中の第１のＳボックスからの出力の第１ビットが選択される。ｂをこのビットの値とする。ｂは、秘密鍵の６ビットによって決まるだけであることが容易に理解できる。攻撃者は、問題の６ビットに、ある仮説を立てる。攻撃者は、これらの６ビットおよびＥ［ｉ］から、ｂに対して、対応する理論値を計算する。これによって、１，０００個の入力Ｅ［１］、…、Ｅ［１，０００］を、２つのカテゴリ（ｂ＝０となるカテゴリ、及びｂ＝１となるカテゴリである）に分けることが可能となる。
【００１１】
第３ステップ：次に、第１のカテゴリすなわちｂ＝０となるカテゴリに対応する曲線の平均ＣＭ′が計算される。ＣＭ及びＣＭ′が著しく異なる場合には、６個の鍵ビットに保持されている値は、正しい値と見なされる。ＣＭ及びＣＭ′に、統計的な意味で、いかなる実質的な相違も認められない、すなわち測定されたノイズに起因する典型的な相違よりも明確に大きい相違が認められない場合は、６ビットに対する別の選択を行って、第２ステップが繰り返される。
【００１２】
第４ステップ：第２のＳボックス、第３のＳボックス、…、第８のＳボックスからの出力の目標ビットｂを伴って、ステップ２及び３が繰り返される。この様にして秘密鍵の４８ビットが最終的に得られる。
【００１３】
第５ステップ：徹底的探索によって、残りの８ビットを求めることが可能である。
【００１４】
この攻撃は、各命令の個々の電力消費量についての又はこれらの命令のそれぞれの時間的位置についてのいかなる知識をも必要としない。この攻撃は、攻撃者が、アルゴリズムの出力のいくつか及び対応する消費量曲線を知っていると仮定できる場合は、いつでも同じ方法で利用される。この攻撃は、次の基本的な仮定にだけ基づく。
【００１５】
基本的仮定：実際には３２ビットよりも少ない、いくつかの鍵ビットを知っていれば、２つの入力及びそれぞれ２つの出力が、中間変数について同じ値になるか否かを決定することが可能になるような、アルゴリズムの計算中に現れる中間変数が存在する。
【００１６】
実行の通常モードは、一般に、前記の仮定の範囲内に入ってしまうので、ＤＥＳのようなＳボックスを用いるアルゴリズムの全ては、ＤＰＡに対して潜在的に脆弱である。
【００１７】
「ＨＯ−ＤＰＡ」と略記される高次差分電力解析として知られる攻撃は、上に説明したＤＰＡ攻撃の一般化である。それらの攻撃は、いくつかの異なる情報源を用いることができる。電力消費量に加えて、それらの攻撃は、電磁放射及び温度等の測定結果を含むことができ、また単純な平均の概念よりもより洗練された統計的操作、及びより基本的でない（前記のビットｂを一般化した）中間変数を用いることができる。それでもやはり、それらの攻撃は、ＤＰＡと全く同じ基本的仮定に基づいている。
【００１８】
本発明の主題となる方法の目的は、秘密鍵又は個人鍵暗号化を用いるコンピュータにおけるＤＰＡ又はＨＯ−ＤＰＡ攻撃の危険を取除くことである。
【００１９】
従って、本発明の別の主題は、前記の基本的仮定がもはや満たされないような、言い換えれば、中間変数が個人又は秘密鍵の容易にアクセス可能なサブシステムの電力消費量に依存せず、従ってＤＰＡ又はＨＯ−ＤＰＡタイプの攻撃の効力を失わせるような、暗号化を用いて保護されたコンピュータシステムによって実行される暗号化計算方法の変更例である。
【課題を解決するための手段】
【００２０】
本発明の主題である秘密鍵を用いた標準の暗号化計算方法を実行するコンピュータシステムを保護する方法は、暗号化計算方法が、並行して実行されかつ標準の暗号化計算の結果とは別個の部分中間的結果を生成する、いくつかの別個の暗号化計算方法の部分に分割されるという点で、及び、分割することなく標準の暗号化計算によって得られる最終値が、別個の部分中間的結果から再構成されるという点で、注目に値する。「標準の暗号化計算方法」という用語は、暗号化された値、復号化された値、及び署名、署名の検証、認証、非拒絶の値を得ることを可能にする、全ての一連の又は連続した計算方法を意味することを意図したものである。このタイプの方法は、クレジットカード、ＡＴＭカード、アクセス管理カード又は類似の機能用のスマートカード等の暗号化計算機能を備える埋め込みシステムに対するＤＰＡ又はＨＯ−ＤＰＡタイプの攻撃を防止することを可能にする。
【００２１】
本発明は、下記の記述および図面の考察を読めば、よりよく理解できるであろう。
【図面の簡単な説明】
【００２２】
【図１ａ】ＤＥＳの暗号化／復号化方法、すなわち「Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ：データ暗号化基準」に関連する先行技術について表す。
【図１ｂ】ＤＥＳの暗号化／復号化方法、すなわち「Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ：データ暗号化基準」に関連する先行技術について表す。
【図２】本発明の主題となる方法を示すフローチャートを表す。
【図３ａ】本発明の主題となる方法の実行の非限定的なモードを示す例を表す。
【図３ｂ】ＤＥＳのような標準の暗号化計算方法に用いられる非線形変換に適用される、本発明の主題となる方法の特定の実行のフローチャートを示す例を表す。
【図３ｃ】図２に示したような本発明の主題となる方法の実行の変更例を表す。
【図３ｄ】ＤＥＳのような標準の暗号化計算方法に用いられる非線形変換に適用される秘密全単射変換に基づいた、本発明の主題となる方法の別の特定の実行のフローチャートを示す例を表す。
【図３ｅ】ＤＥＳのような標準の暗号化計算方法に用いられる非線形変換に適用される多項式関数に基づいた、本発明の主題となる方法の別の特定の実行のフローチャートを示す例を表す。
【発明を実施するための形態】
【００２３】
ここで、本発明の主題となる秘密鍵を用いる標準の暗号化計算方法を実行するコンピュータシステムを保護する方法のより詳細な説明を、図を参照して行う。
【００２４】
一般的に、本発明の主題となる方法は、秘密又は個人鍵Ｋを用いる標準の暗号化方法については、暗号化計算方法の変更からなり、そこにおいては、前記の基本的仮定は、もはや満たされず、本発明の主題となりかつ秘密鍵について容易にアクセス可能なサブシステムの知識に依存する方法に従って計算されるいかなる中間変数ももはや存在しない。
【００２５】
この目的のために、及び図２に表されるような本発明の主題となる方法によれば、ａ）標準の暗号化計算方法は、並行して実行される幾つかの別個の計算方法の部分ＰＰＣ１〜ＰＰＣｋに分割され、ｂ）分割することなく標準の暗号化計算方法により得られる値に対応する最終値ｖは、上記の別個の計算方法の部分ＰＰＣ１〜ＰＰＣｋを実行することにより得られた別個の部分結果ｖ１〜ｖｋから再構成される。
【００２６】
従って、計算方法の部分は、独立しているが、部分中間変数又は中間結果は、関連している。
【００２７】
この分割は、計算中に発生し、入力（又は出力）データによって決まる各中間変数ｖを、ｋ個の変数ｖ１、ｖ２、…、ｖｋで置き換えることによって実施される。必要に応じて、ｖ１、ｖ２、…、ｖｋは、ｖを再構成することを可能にする。より正確に言えば、これは、ｖ＝ｆ（ｖ１、ｖ２、…、ｖｋ）であるような関数ｆが存在することを意味する。さらに、ｆは、次の条件を満たすことが望ましいということに注意されたい。
【００２８】
（条件１）
ｉを、最も広い意味で、１及びｋの間の添字とする。ｖの値を知っていても、現存する（ｋ−１）項組（ｖｉ、…、ｖｉ−１、ｖｉ＋１、…、ｖｋ）が等式ｆ（ｖｉ、…、ｖｋ）＝ｖを満たすように、全てのｖｉ値の情報を演繹することは事実上不可能である。
（例１）
関数
【数１】
2010072664.tif 000003
を取る場合、条件１は、明らかに満たされる。その理由は、１とｋとの間の任意の添字ｉに対して、検討中のｖｉの集合は、全ての考えられる値を含み、従ってｖに依存しないからである。なお、以下の文章中では、記号
【数２】
2010072664.tif 000004
は、特に断りのない限りは「○＋」と記す。
【００２９】
（例２）
乗法群（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｇｒｏｕｐ）Ｚ／ｎＺにおける値、すなわち、ｎを法とする逆数を有するｎを法とする整数の全ての値を有する変数ｖを考える場合、新たな変数ｖ１、ｖ２、…、ｖｋが、さらに乗法群Ｚ／ｎＺにおける値を持つような、ｎを法とする関数ｆ（ｖｉ、…、ｖｋ）＝ｖ１・ｖ２・…・ｖｋを取り上げることができる。条件１は、やはり明らかに満たされる。その理由は、１とｋとの間の全ての添字ｉに対して、検討中のｖｉの集合は、全ての考えられる値を含み、従ってｖに依存しないからである。
【００３０】
本発明の主題となる方法の注目すべき態様によれば、入力（又は出力）データによって決まる各中間変数ｖを、ｋ個の変数ｖ１、ｖ２、…、ｖｋで置き換えることによって、アルゴリズムの「変換」が実行される。新たな形態に変更されたアルゴリズムの最大限のセキュリティを保証するために、関数ｆに対して、次の追加的な条件が課される。
【００３１】
（条件２）
関数ｆは、ｖに対して行われる通常の変換の代わりに、計算中に、ｖ１、ｖ２、…、又はｖｋに対して行われる変換が、ｖを再計算する必要なしに、実行可能である。
【００３２】
（第１の例：ＤＥＳ）
ＤＥＳの保護に関連した第１の例を、図３ａを参照して説明する。
【００３３】
この例では、ＤＥＳの特定の例が検討される。この場合、われわれは、計算中に発生し、入力又は出力データに依存する各中間変数ｖの２つの変数ｖ１及びｖ２への分割を選択する、すなわちｋ＝２とする。それ自身の構造において条件１を満たす、前記の例１の関数ｆ（ｖ１、ｖ２）＝ｖ＝ｖ１○＋ｖ２を検討する。アルゴリズムの構造から、ｖに対して実行する変換は、常に次の５つのカテゴリ内に入ることを理解するのは容易である。
ｖのビットの順列（ｐｅｒｍｕｔａｔｉｏｎ）；
ｖのビットの展開（ｅｘｐａｎｓｉｏｎ）；
ｖと、同タイプの別の変数ｖ′との排他的論理和；
ｖと、鍵又は副鍵だけに依存する変数ｃとの排他的論理和；
Ｓボックスによるｖの非線形変換。
【００３４】
最初の２つのカテゴリは、変数ｖのビットについての線形変換に対応する。従って、これらに対しては、条件２を満たすのは、非常に容易である。通常ｖに対して実行される変換の代りに、ｖ１そしてｖ２に対して順列又は展開を行うだけでよく、そして、変換前に「真」であった関係ｆ（ｖ１、ｖ２）＝ｖは、その後も依然として等しく「真」である。
【００３５】
第３の場合も同様に、ｖ″＝ｖ○＋ｖ′の計算を、ｖ″１＝ｖ１○＋ｖ′１及びｖ″２＝ｖ２○＋ｖ′２の計算で置き換えるだけでよい。関係式ｆ（ｖ１、ｖ２）＝ｖ及びｆ（ｖ′１、ｖ′２）＝ｖ′は、明確にｆ（ｖ″１、ｖ″２）＝ｖ″を生み出し、条件２は、再び満たされる。
【００３６】
ｖと、鍵又は副鍵だけによって決まる変数ｃとの排他的論理和において、条件２は、また非常に容易に満たされる。計算ｖ○＋ｃを、条件２を満たす計算ｖ１○＋ｃ又はｖ２○＋ｃで置き換えるだけでよい。
【００３７】
最後に、この例では、６ビットの入力を取り４ビットの出力を生じるＳボックスの形態で与えられる非線形変換ｖ′＝Ｓ（ｖ）の代りに、変換（ｖ′１、ｖ′２）＝Ｓ′（ｖ１、ｖ′２）が、２つの新たなＳボックスを用いて実行される。この場合、それぞれのＳボックスは、１２ビットから４ビットに変換する。等式ｆ（ｖ′１、ｖ′２）＝ｖ′を保証するために、以下を選択するだけでよい。
【数３】
2010072664.tif 000005
ここで、Ａは、１２ビットから４ビットへの「秘密ランダム変換（ｓｅｃｒｅｔ  ｒａｎｄｏｍ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ）」を表す。第１の（新たな）Ｓボックスは、（ｖ１、ｖ２）をＡ（ｖ１、ｖ２）と関連付ける「変換（ｖ１、ｖ２）→Ａ（ｖ１、ｖ２）」のテーブルに対応し、第２の（新たな）Ｓボックスは、（ｖ１、ｖ２）をＳ（ｖ１○＋ｖ２）○＋Ａ（ｖ１、ｖ２）と関連付ける「変換（ｖ１、ｖ２）→Ｓ（ｖ１○＋ｖ２）○＋Ａ（ｖ１、ｖ２）」のテーブルに対応する。ランダム関数Ａがあることによって、条件１の保証が可能となる。さらにテーブルを用いることによって、計算ｖ１○＋ｖ２の必要性が無くなり、従って条件２を満たすことが可能となる。
【００３８】
コンピュータシステムがスマートカードによって構成されている場合には、変換（ｔｒａｎｓｆｏｒｍａｔｉｏｎ又はｃｏｎｖｅｒｓｉｏｎ）テーブルは、スマートカード内のＲＯＭに記憶することができる。
【００３９】
こうして、ＤＥＳのような標準の暗号化計算方法によって用いられる非線形変換タイプの計算ステップに対して、図３ｂに示されるようなｋ個の部分への分割を行なうことができる。変換されたｎ個の出力ビットが、ｍ個の入力ビットの関数であるアドレスにおいて読み込まれる変換テーブルによって記述され、ｍ個のビットからｎ個のビットへの非線形変換を用いる標準の暗号化計算方法に対しては、分割されない標準の暗号化計算方法の入力変数Ｅの役割をする中間変数に適用される各非線形変換が、部分中間変数ｖ１〜ｖｋの全てに適用されるｋ×ｍ個のビットからｋ×ｎ個のビットへの部分非線形変換によって置き換えられる。本発明の主題である方法の特に注目すべき態様によれば、この部分非線形変換は、変換されたｎ個の出力ビットｖ′１、ｖ′２、…、又はｖ′ｋが、ｋ×ｍ個の入力ビットの関数であるアドレスにおいて読み込まれるｋ個の部分変換テーブルによって記述され実行される。
【００４０】
前記の第１の例において、及び図３ｂに関連して、ｋ＝２、ｎ＝４、及びｍ＝６と指示されている。
（第１の変更例）
ＲＯＭ内の記憶空間を節約するために、ＤＥＳの標準的記述の８個のＳボックスのそれぞれに対して標準的ランダム関数Ａを用いることが全く可能であり、従って１６個のＳボックスの代りに記憶のための新たなＳボックスを９個持つだけでよくなる。
【００４１】
別の第２の変更例を、図３ｃを参照して説明する。
（第２の変更例）
Ｓボックスを記憶するのに要するＲＯＭの大きさを縮小するために、次の方法を用いることがさらに可能である。（ＤＥＳの例では、６ビットの入力を取り４ビットの出力を生じる）Ｓボックスの形態で与えられる初期実行の各非線形変換ｖ′＝Ｓ（ｖ）の代りに、変換（ｖ′１、ｖ′２）＝Ｓ′（ｖ１、ｖ２）を２つのＳボックスを用いて実行することができる。この場合、それぞれのＳボックスが、６ビットから４ビットに変換する。ｖ′＝Ｓ（ｖ）の計算の初期実行は、次の２つの連続する計算によって置き換えられる：
【数４】
2010072664.tif 000006
ここで、φは、６ビットから６ビットへの「秘密全単射関数（ｓｅｃｒｅｔ  ｂｉｊｅｃｔｉｖｅ  ｆｕｎｃｔｉｏｎ）」であり、Ａは、６ビットから４ビットへ秘密ランダム変換を表す。第１の（新たな）Ｓボックスは、ｖ０をＡ（ｖ０）に関連付ける「変換ｖ０→Ａ（ｖ０）」のテーブルに対応し、第２の（新たな）Ｓボックスは、ｖ０をＳ（φ−１（ｖ０））○＋Ａ（ｖ０）に関連付ける「変換ｖ０→Ｓ（φ−１（ｖ０））○＋Ａ（ｖ０）」のテーブルに対応する。構造から、さらに等式ｆ（ｖ′１、ｖ′２）＝ｖ′を得る。ランダム関数Ａの存在によって、条件１の保証が可能となる。テーブルを用いることにより、φ−１（ｖ０）＝ｖ１○＋ｖ２を計算する必要が無くなる。
【００４２】
図３ｄは、第２の変更例に従って本発明の主題である方法により変更された、ＤＥＳ等の標準の暗号化計算方法の枠組みの中で用いられる非線形変換タイプの対応する計算ステップを表す。ｎ個の出力ビットが、ｍ個の入力ビットの関数であるアドレスにおいて読み込まれる変換テーブルによって記述される、ｍ個のビットからｎ個のビットへの非線形変換に対して、入力変数Ｅに適用されるｋ個の部分への分割に加えて、標準の暗号化計算方法の入力変数Ｅの役割を果たす中間変数に適用される各非線形変換は、部分中間変数ｖ１〜ｖｋの全てに適用されるｋ×ｍ個のビットからｋ×ｎ個のビットへの部分非線形変換によって置き換えられる。この部分非線形変換は、ｋ個の変換テーブルによって記述され実行される。変換テーブルの入力のそれぞれは、関係式φｊ○ｆ（ｖ１、…、ｖｋ）及びｊ∈［ｌ、ｋ］に従って、秘密全単射関数φｊを、部分中間変数の関数ｆ（ｖ１、…、ｖｋ）に適用することにより得られた値を受け取る。
【００４３】
本発明の主題である方法の特に注目すべき態様に従えば、上記の適用φｊ○ｆ（ｖ１、…、ｖｋ）は、対応する変換テーブル１〜ｋの入力に適用され、これらのｍ個の入力ビットの関数であるアドレスにおいて、変換ｖ′１又はｖ′２又は…ｖ′ｋのｎ個の出力ビットを読み込むことを可能にする結果として生じる値を、直接評価することによって実行される。
【００４４】
図３ｄを参照して説明された第１の例のように、第２の変更例については、ｋ＝２、ｍ＝６及びｎ＝４と指示されている。
【００４５】
さらに、単純化されたバージョンにおいては、全単射関数φ１及びφｋは同一である。
【００４６】
条件２が満たされるためには、ｖ０＝φ（ｖ１○＋ｖ２）の計算が、ｖ１○＋ｖ２を再計算する必要なしに行われ得るように、全単射変換φ又は全単射関数φ１〜φｋを選択することがさらに必要である。関数φのための２つの選択例を、以下に述べる。
【００４７】
（第１の実施形態：線形全単射関数φ）
６ビットから６ビットへの秘密全単射線形関数が、φに対して選択される。このような選択の枠内で、６ビット値は、すべて、２つのエレメントを持つ有限体Ｆ２中で、６というディメンジョンを持つベクトル空間と考えられる。実際には、φを選択するということは、０又は１という係数を持つランダム可逆６×６行列式を選択することである。φをこのように選択すると、条件２が満たされていることが容易に分かる。要するに、φ（ｖ１○＋ｖ２）を計算するには、φ（ｖ１）を計算して、次にφ（ｖ２）を計算して、最後にこの得られた２つの結果の「排他的論理和」を計算するだけでよい。
【００４８】
例えば、次の行列式：
【数５】
2010072664.tif 000007
は可逆である。これは、次式で定義される６ビットオーバー４ビットの線形全単射関数φに相当する。
【数６】
2010072664.tif 000008
ｖ１＝（ｖ１．１、ｖ１．２、ｖ１．３、ｖ１．４、ｖ１．５、ｖ１．６）であり、ｖ２＝（ｖ２．１、ｖ２．２、ｖ２．３、ｖ２．３、ｖ２．５、ｖ２．６）であることに注目すると、φ（ｖ１○＋ｖ２）を計算するには、次式を連続的に計算する：
【数７】
2010072664.tif 000009
これで、得られた２つの結果の「排他的論理和」が計算される。
【００４９】
（第２の実施形態：二次全単射関数φ）
６ビットから６ビットへの秘密全単射二次関数が、φに対して選択される。「二次」という用語は、この場合、関数φから出力された各々の値のビットは、有限体Ｆ３の６つのエレメントで識別される６個の入力ビットの内の２ビットで与えられる次数を持つ多項式関数によって表されることを意味する。実際には、式φ（ｘ）＝ｔ（ｓ（ｘ）５）で定義される関数φを選択することが可能であるが、ここで、ｓは（Ｆ２）６をＬに対して秘密全単射線形適用したものであり、ｔはＬを（Ｆ２）６に対して秘密全単射線形適用したものであり、Ｌは有限体Ｆ２の６次代数展開を示すものである。この関数φの全単射の性質は、ａ→ａ５が展開Ｌ（この逆がｂ→ｂ３８）に対する全単射関数であるという事実に由来する。条件２がまだ満たされているかどうかを確定するためには、次式が成立するかどうかを判断するだけでよい：
【数８】
2010072664.tif 000010
ここで、関数Ψは、Ψ（ｘ、ｙ）＝ｔ（ｓ（ｘ）４・ｓ（ｙ））によって定義される。
【００５０】
例えば、ＬがＦ２［Ｘ］／（Ｘ６＋Ｘ＋１）と同一視され、また、ｓとｔが、それぞれＦ２中のＬの基数（１、Ｘ、Ｘ２、Ｘ３、Ｘ４、Ｘ５）とＦ２における（Ｆ２）６の標準基数とに対する次の行列式とすると：
【数９】
2010072664.tif 000011
と次の６ビットから６ビットへの二次全単射関数φが得られる：
【数１０】
2010072664.tif 000012
φ（ｖ１○＋ｖ２）を計算するためには、１２ビットから６ビットへの関数Ψ（ｘ、ｙ）＝ｔ（ｓ（ｘ）４・ｓ（ｙ））を用いるが、これは次の規則に従って１２個の入力ビットの関数として６個の出力ビットを与えるものである：
【数１１】
2010072664.tif 000013
【００５１】
これらの式を用いて、次式を連続的に計算する：
【数１２】
2010072664.tif 000014
すると、得られた４つの結果の「排他的論理和」が計算される。
【００５２】
（第３の変更例）
再度、Ｓボックスを記憶するに必要なＲＯＭサイズを減少させるためには、また、先行の変更例である変更例１と変更例２の双方の概念を同時に適用すればよい。すなわち、変更例２を、Ｓボックスという形態で表現される各々の非線形変換を新たに実施する際に、前記と同じ秘密全単射関数φ（６ビットから６ビットへの関数）と同じ秘密ランダム関数Ａ（６ビットから６ビットへの関数）と共に用いる。
【００５３】
（第４の変更例）
この最後の変更例では、１つのＳボックスという形態で表現された初期実施の非線形変換ｖ′＝Ｓ（ｖ）を置換する２つのＳボックスによって、変換（ｖ′１、ｖ′２）＝Ｓ′（ｖ１、ｖ２）を実現する代わりに、ｖ′１とｖ′２それぞれの計算を、ｖ′１とｖ′２それぞれが有するビットが、ｖ１とｖ２のビットで与えられる合計次数が１又は２である多項式関数によって与えられる代数関数によって実行され、次に、ｖ′２とｖ′１それぞれが、テーブルによって計算される。これによって、また、ハードウエアの実行にとって必要なＲＯＭサイズを減少させることができる。
【００５４】
したがって、図３ｅに示すように、ＤＥＳなどの標準の暗号化計算方法によって実現される非線形変換タイプの計算ステップの場合、入力Ｅの役割を果たす中間変数ｖ１〜ｖｋのｋ個の部分に分割することに加えて、図３ｂと３ｄだけではなく、この標準の暗号化計算方法の場合も、当該非線形変換は、変換されたｎ個の出力ビットが、ｍ個の入力ビットの関数であるアドレスのところで読み取られる変換テーブルによって記載されている、ｍ個のビットからｎ個のビットへの非線形変換からなる。すなわち、本発明の手段であるこの方法によれば、分割を実行しない標準の暗号化計算方法の中間変数に適用される各非線形変換の代わりに、部分中間変数ｖ１〜ｖｋのすべての適用されるｋ×ｍ個のビットからｋ×ｎ個のビットへの部分非線形変換が用いられる。この場合、また、上記の実施形態２の変更例４を参照すると、この変換された（ｋ−１）×ｎ個の出力ビットは、次の関係式に従って、変数ｖ１、ｖ２、．．．、ｖｋのｋ×ｍ個の入力ビットの多項式関数として計算される：
【数１３】
2010072664.tif 000015
ここで、Ｐ１とＰｋ−１は、ｍビットからｎビットへの多項式変換関数を示している。
【００５５】
次に、出力変数のｎ個の残余のビットｖ′ｋが、例えば、これらのｎ個のビットがｋ×ｍ個の入力ビットの関数であるアドレスで読み取られる非線形変換テーブルを読むことによって得られる。
【００５６】
上記の実施形態の変更例４では、ｋ＝２、ｍ＝６、ｎ＝４が再現されている。
【００５７】
（第２の実施形態：トリプルＤＥＳ）
トリプルＤＥＳは、秘密鍵を用いて暗号化／復号化動作を連続的に実行することからなる。
【００５８】
トリプルＤＥＳアルゴリズムを説明するには、次の文書のどれかを参照すれば役に立つであろう：
ＩＳＯ／ＩＥＣ  ８７３２、「Ｂａｎｋｉｎｇ−Ｋｅｙ  Ｍａｎａｇｅｍｅｎｔ（Ｗｈｏｌｅｓａｌｅ）」、１９８７；
ＡＮＳＩ  Ｘ９．１７、「Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄ、Ｆｉｎａｎｃｉａｌ  Ｉｎｓｔｉｔｕｔｉｏｎ  Ｋｅｙ  Ｍａｎａｇｅｍｅｎｔ（Ｗｈｏｌｅｓａｌｅ）」、１９８５年。
又は、次の書籍を参照されたい：
ブルース・シュナイヤー、「Ａｐｐｌｉｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ」、第２版、ジョン・ワイリー＆サン、１９９６年、３５８ページ；
これらは、参照して本出願に組み込まれる。
【００５９】
この原理は、メッセージを暗号化するために、ＤＥＳアルゴリズムを連続して３回用いることからなる。すなわち、最初に鍵番号１を用いて暗号化モードでＤＥＳ動作を実行し、次に鍵番号２を用いて復号化モードでＤＥＳ動作を実行し、最後に鍵番号１を用いて暗号化モードでもう一度ＤＥＳ動作を実行する。ＤＰＡタイプの攻撃は、ＤＥＳの場合と同様に可能である。すなわち、最初のＤＥＳ動作の第１ラウンドに付いての消費電力測定値に基づいて、鍵番号１の４８ビットを発見し、次に、第２ラウンドを解析することによって、鍵番号１の残余の８ビットを発見する。鍵番号１が分かっているので、２番目のＤＥＳ動作の入力が分かり、従って、同じ攻撃を適用して鍵番号２を発見することができる。
【００６０】
このアルゴリズムの保護は、上記の第１の実施形態で説明した単純なＤＥＳの場合に動作し得る。すなわち、同じ関数ｆを用いて、中間変数の「分割」、したがってアルゴリズムの同じ変換を実行する。
【００６１】
（第３の実施形態：ＲＳＡ）
ＲＳＡは、最も有名な非対称暗号化アルゴリズムである。それは、１９７８年に、リベスト、シャミール及びアドルマンによって開発された。このアルゴリズムの詳細は、以下の文書を参照すれば役に立つであろう：
Ｒ．Ｌ．リベスト、Ａ．シャミール、Ｌ．Ｍ．アドルマン、「Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｂｔａｉｎｉｎｇ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ，  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，２１、第２号」、１２０〜１２６ページ、１９７８年；
又は、次の文書を参照されたい。
ＩＳＯ／ＩＥＣ  ９５９４−８／ＩＴＵ−Ｔ  Ｘ．５０９、「Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｅｃｈｎｏｌｏｇｙ−Ｏｐｅｎ  Ｓｙｓｔｅｍｓ  Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ−Ｔｈｅ  ｄｉｒｅｃｔｏｒｙ：Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｆｒａｍｅｗｏｒｋ」；
ＡＮＳＩ  Ｘ９．３１−１、「「Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄ、Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｕｓｉｎｇ  Ｒｅｖｅｒｓｉｂｌｅ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｔｈｅ  Ｆｉｎａｎｃｉａｌ  Ｓｅｒｖｉｃｅｓ  Ｉｎｄｕｓｔｒｙ」、１９９３年；
ＰＫＣＳ  ＃１、「ＲＳＡ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ，第２版」、１９９８年；  これは、次のアドレスで入手可能である。ｈｔｔｐ：／／ｆｔｐ．ｒｓａ．ｃｏｍ／ｐｕｂ／ｐｋｃｓ／ｄｏｃ／ｐｋｃｓ−１ｖ２．ｄｏｃ；
これらの文書又はそのＨＴＭＬページとしての公開内容は、参照して本明細書に組み込まれる。
【００６２】
ＲＳＡアルゴリズムは、２つの大きい素数ｐとｑの積である整数ｎと、ｐｐｃｍ（ｐ−１、  ｑ−１）と素である整数ｅを、ｅ≠±１  ｍｏｄ  ｐｐｃｍ（ｐ−１、  ｑ−１）となるように用いる。整数ｎとｅが、公開鍵を構成する。この公開鍵の計算には、  ｇ（ｘ）＝ｘｅ  ｍｏｄ  ｎで定義されるＺ／ｎＺに対して、Ｚ／ｎＺの関数ｇを用いる。秘密鍵計算は、関数ｇ−１（ｙ）＝ｙｄを用いるが、ここで、ｎ又はｄは、ｅｄ  ≡  １  ｍｏｄ  ｐｐｃｍ（ｐ−１、  ｑ−１）で定義される秘密成分（秘密鍵すなわち個人鍵とも呼ばれる）である。
【００６３】
ＤＰＡタイプ又はＨＯ−ＤＰＡタイプの攻撃もまた、ＲＳＡアルゴリズムの標準的実現に対する脅威となる。事実、後者は、極めてしばしば、いわゆる「二乗して乗算する」原理を用いて、ｘｄ  ｍｏｄ  ｎの計算を実行する。この原理とは、秘密成分ｄの内訳ｄ  ＝  ｄｍ−１・２ｍ−１  ＋  ｄｍ−２・２ｍ−２  ＋  …  ＋  ｄ１・２１  ＋  ｄ０・２０を、基数２に書き込んで、次のように計算することである。
１．  ｚ  ←  １；
次に、ｍ−１から０までの範囲のｉに対して、次の計算を実行する。
２．  ｚ  ←  ｚ２  ｍｏｄ  ｎ；
３．  ｄｉ＝１であれば、ｚ  ←  ｚ・ｘ  ｍｏｄ  ｎ。
【００６４】
この計算で、変数ｚが取る連続値の中で、素数は、秘密鍵ｄの数ビットに依存するだけであることに注意されたい。したがって、ＤＰＡ攻撃を許容する基本的仮定は満たされる。これで、例えば、ｍ−１からｍ−１０の範囲のｉに対応するアルゴリズムに付いての消費電力測定値を解析することによって、ｄについての１０個の高位ビットを推定することが可能となる。次に、ｍ−１１からｍ−２０の範囲のｉに対応するアルゴリズムの部分に付いての消費電力測定値を用いて攻撃を継続することが可能であり、これによって、ｄの次の１０ビットを、さらに次の１０ビットをという具合に発見することができる。最終的には、秘密成分ｄのすべてのビットが分かる。
【００６５】
本発明の主題であるこの方法はまた、ＲＳＡアルゴリズムの保護にも適用される。それは、乗法群Ｚ／ｎＺにおける値、すなわち、計算中に発生し、また、入力データ又は出力データに依存する、自身もｎを法とする逆数を有するｎを法とする整数のすべてを持つ各中間変数ｖを、２つの変数ｖ１とｖ２に分割する。ｋ＝２とし、また、関数ｆ（ｖ１、ｖ２）＝ｖ＝ｖ１・ｖ２  ｍｏｄ  ｎとする。上記の説明で示したように（実施形態２「アルゴリズムの保護」を参照）、この関数ｆによって条件１を満たすことができる。
【００６６】
したがって、ｘを（ｘ１、ｘ２）と置き換え、これで、ｘ＝ｘ１・ｘ２  ｍｏｄ  ｎとし、またｚを（ｚ１、ｚ２）と置き換え、これで、ｚ＝ｚ１・ｚ２  ｍｏｄ  ｎとなるようにする。実際、例えば、ｘ１をランダムに選択して、それからｘ２を演繹することが可能である。ここで、「二乗して乗算する」方法の３つのステップに戻ると、次の変換が実行される。
１．  ≪ｚ  ←  １≫を、≪ｚ１  ←１、ｚ２  ←  １≫で置き換える；
２．  ≪ｚ  ←  ｚ２  ｍｏｄ  ｎ≫を、≪ｚ１  ←  ｚ１２  ｍｏｄ  ｎ、ｚ２  ←  ｚ２２  ｍｏｄ  ｎ≫で置き換える；
３．  ≪ｚ  ←  ｚ・ｘ  ｍｏｄ  ｎ≫を、≪ｚ１  ←  ｚ１・ｘ１  ｍｏｄ  ｎ、ｚ２  ←  ｚ２・ｘ２  ｍｏｄ  ｎ≫で置き換える。
【００６７】
関係式Ｚ＝ｆ（ｚ１、ｚ２）が、計算全体にわたって「真」であることを満たすことは容易であり、これで、条件２が満たされることが分かる。
【００６８】
それぞれ変数ｚ１と変数ｚ２に対して実行される計算は、完全に独立していることに注意されたい。したがって、この２つの計算を、
連続的に、インターリーブ形式で、マルチプログラミングすれば同時並行して、又は、並行に動作する別々のプロセッサで同時に実行することが可能である。
【図１ａ】
2010072664.tif 000017
【図１ｂ】
2010072664.tif 000018
【図２】
2010072664.tif 000019
【図３ａ】
2010072664.tif 000020
【図３ｂ】
2010072664.tif 000021
【図３ｃ】
2010072664.tif 000022
【図３ｄ】
2010072664.tif 000023
【図３ｅ】
2010072664.tif 000024