(57)【要約】【課題】相関アタックの精度と速度とを向上させるための方法および装置【解決手段】ストリーム暗号を復号するための方法および装置。ＳＳＣ２タイプのストリーム暗号は、ＬＦＧ出力の周期とＬＦＳＲ出力のＬＳＢの相関とを利用することによって復号される。特定のビットを反転すべきかどうかを決定するために、データストリームの各ビットに関する誤りの動的確率が計算される。
2005527993.tif 000002
【特許請求の範囲】
【請求項１】
ストリーム暗号を復号するための方法であって、
周期ＴＴを有するデータストリーム内の各ビットｉに関するパリティ検査方程式の数を決定し、
前記データストリーム内の各ビットｉに関する満足されたパリティ検査方程式の数を決定し、
各ビットｉに関するパリティ検査方程式の前記数と各ビットｉに関する満足されたパリティ検査方程式の前記数とに基づいて各ビットｉに関する誤りの動的確率を決定し、
各ビットｉの誤りの前記動的確率に基づいて各ビットｉを反転すべきかどうかを決定すること、
とを備える方法。
【請求項２】
周期ＴＴを有するデータストリーム内の各ビットｉに関するパリティ検査方程式の数を決定し、前記データストリーム内の各ビットｉに関する満足されたパリティ検査方程式の数を決定し、各ビットｉに関するパリティ検査方程式の前記数と各ビットｉに関する満足されたパリティ検査方程式の前記数とに基づいて各ビットｉに関する誤りの動的確率を決定し、各ビットｉの誤りの前記動的確率に基づいて各ビットｉを反転すべきかどうかを決定するプロセッサと、
コードとデータとを記憶するためのメモリと、
を備える装置。
【請求項３】
ストリーム暗号を復号するための方法を具体化するコンピュータ読取り可能な媒体であって、前記方法が、
周期ＴＴを有するデータストリーム内の各ビットｉに関するパリティ検査方程式の数を決定し、
前記データストリーム内の各ビットｉに関する満足されたパリティ検査方程式の数を決定し、
各ビットｉに関するパリティ検査方程式の前記数と各ビットｉに関する満足されたパリティ検査方程式の前記数とに基づいて各ビットｉに関する誤りの動的確率を決定し、
各ビットｉの誤りの前記動的確率に基づいて各ビットｉを反転すべきかどうかを決定することからなる方法である
媒体。
【請求項４】
前記データストリームはより大きなデータストリームから選択される請求項１に記載の方法。
【請求項５】
前記誤りの動的確率は二項確率分布に基づいて計算される請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（優先権の主張）
本特許出願は、２００１年８月２２日に出願され、この譲受人に譲渡され、参照してここに明白に組み込まれる、「相関アタックの精度と速度とを向上させるための方法および装置（METHOD AND APPARATUS FOR INCREASING THE ACCURACY AND SPEED OF CORRELATION ATTACKS）」と題する仮出願第６０／３１４，５２５号に対する優先権を主張するものである。
【０００２】
ここに開示される本実施形態は、一般的には通信の分野に関し、さらに具体的には暗号化アルゴリズムをアタックする（attacking）ことに関する。
【背景技術】
【０００３】
通信システムでは許可された相手だけがデータを理解できることを保証するために、機密保護目的でデータの暗号化が使用される。暗号化は、データ（平文とも称する）の暗号文への変換である。暗号文は、許可されていない人々によって容易には理解できない暗号化されたデータである。復号は、暗号化されたデータをその元の平文形式に再変換する処理である。
【０００４】
暗号化アルゴリズム（暗号とも呼ばれる）は、例えば計算能力不足のためにセルラーおよびパーソナル通信装置では制約される。したがって公開キー暗号といった計算集約的暗号化アルゴリズムは、セルラーおよびパーソナル通信装置には適当でない。
セルラーおよびパーソナル通信装置の制約を満たすために、ソフトウエア志向のストリーム暗号ＳＳＣ２が提案された。Ｍ．Ｚｈａｎｇ，Ｃ．ＣａｒｒｏｌｌおよびＡ．Ｃｈａｎのソフトウエア志向ストリーム暗号（Ｔｈｅ  Ｓｏｆｔｗａｒｅ−Ｏｒｉｅｎｔｅｄ  Ｃｉｐｈｅｒ）ＳＳＣ２、３１〜４８頁（２００１年）。ストリーム暗号は、あるアルゴリズムとキーとがデータストリーム内の各ビットに適用される暗号化アルゴリズムである。キーは、平文をロックし、すなわち平文を暗号文に変換し、また暗号化されたテキストをロック解除する、すなわち暗号文を平文に変換するアルゴリズムによって使用される値である。暗号という用語は、暗号化されたデータ、すなわち暗号文をも指す。
【０００５】
ＳＳＣ２は、二つの「半暗号（half-ciphers）」の出力の排他的論理和をとる（ＸＯＲをとる）ことによって動作するストリーム暗号である。第１の半暗号は、非線形フィルタ／関数（ＮＬＦ：non-linear filter/function）を有する線形フィードバックシフトレジスタ（ＬＦＳＲ：linear feedback shift register）から構成される。第２の半暗号は、遅延フィボナッチジェネレータ（ＬＦＧ：lagged Fibonacci generator）とフィボナッチレジスタ(Fibonacci register)から値を選択するマルチプレクサとから構成される。
【０００６】
暗号解析は、暗号を破る目的を持った暗号系、すなわち暗号化システムの解析を含む。言い換えれば暗号解析は、キーを知ることなく暗号文を復号するための暗号化方法の解析に関わる。暗号解析は、元の平文データを復元するために暗号化データに対して相関アタック（correlation attack）を実施する。相関アタックは、それによって暗号化データ内の相関が発見され、暗号化データから元の平文データの復元を可能にするアルゴリズムの暗号化データへの適用である。暗号解析は、それが正確で迅速であれば有用で実用的である。したがって元のデータを解析して復元する処理が高速であって、正確な結果を生成することが望まれている。
【０００７】
現在のところ、ＳＳＣ２に対する相関アタックのための正確で迅速な方法および装置は存在しない。したがって本技術には、ＳＳＣ２タイプの暗号系に対する相関アタックの精度と速度とを向上させるための効率的な方法と装置の必要性が存在する。
【発明の開示】
【課題を解決するための手段】
【０００８】
ここに開示される実施形態は、周期ＴＴを有するデータストリームを選択することと、前記データストリーム内の各ビットｉに関するパリティ検査方程式の数を決定することと、前記データストリーム内の各ビットｉに関する満足されたパリティ検査方程式の数を決定することと、各ビットｉに関するパリティ検査方程式の前記数と各ビットｉに関する満足されたパリティ検査方程式の前記数とに基づいて各ビットｉに関する誤りの動的確率を決定することと、各ビットｉの誤りの前記動的確率に基づいて各ビットｉを反転すべきかどうかを決定することとを備えるストリーム暗号を復号するための方法を開示することによって、前述の必要性に取り組むものである。
【発明を実施するための最良の形態】
【０００９】
用語「例示的」はここでは、「例、事例または例証として役立つ」ことを意味するために使用される。「例示的」としてここに述べられるいかなる実施形態も、必ずしも他の実施形態に対して好適あるいは有利であると解釈される必要はない。
ＳＳＣ２は、セルラーおよびパーソナル通信装置の制約を満足するために提案されたストリーム暗号である。ソフトウエア志向ストリーム暗号（Ｔｈｅ  Ｓｏｆｔｗａｒｅ−Ｏｒｉｅｎｔｅｄ  Ｓｔｒｅａｍ  Ｃｉｐｈｅｒ）ＳＳＣ２、３１〜４８頁（２００１年）。ＳＳＣ２は、ソフトウエア実現のために設計されており、きわめて高速である。
【００１０】
ＳＳＣ２は、線形フィードバックシフトレジスタ（ＬＦＳＲ）と遅延フィボナッチジェネレータ（ＬＦＧ）とに基づいている。ＬＦＳＲは、状態と呼ばれるビットの集合を記憶するレジスタと線形モジュロ２であるフィルタ関数とを含む。線形モジュロ２関数は、状態を１ビットずつ更新する。ＬＦＧは、整数の集合モジュロＮ（もう一度、状態と呼ばれる）を記憶するフィボナッチレジスタと線形モジュロＮである関数とを含む。線形モジュロＮ関数は、状態を１整数ずつ更新する。ＳＳＣ２では、モジュラスは、Ｎ＝２３２であって、整数はワードと呼ばれる３２ビットのブロックとして記憶される。
【００１１】
ＳＳＣ２は、３２ビット演算を使用することによってその速度を達成する。ストリームは、１２７ビットＬＦＳＲと１７ワードＬＦＧとＬＦＧのフィボナッチレジスタから値を選択するマルチプレクサとから導出される。ＬＦＳＲ用の１２７ビットレジスタは、４個の３２ビットワード内に記憶される（余分なビットは、フィルタ関数内で１にされる）。ＬＦＳＲとＬＦＧの状態が初期設定された後に、下記のステップが反復されて出力の各ワードを生成する：
１．ＬＦＳＲ状態の３２ビットが同時に更新される。非線形フィルタ／関数（ＮＬＦ）がＬＦＳＲの状態の４個のワードから３２ビット出力Ｎｉを計算する。
【００１２】
２．ＬＦＧ状態が更新される。ワードＹｉの上位１６ビットと下位６ビットとがスワップされてＬＦＧ出力Ｌｉを形成する。
３．マルチプレクサが、更新されたワードの４個の最上位ビット（ＭＳＢｓ：most significant bit）を使用して出力ＭｉとなるＬＦＧ状態内の１６個の値の一つを選択する。
【００１３】
４．暗号の出力は、Ｚｉ＝（Ｌｉ＋Ｍｉｍｏｄ２３２）(+)Ｎｉである。ここで(+)はＸＯＲを表す。
値ＮｉはＬＦＳＲ半暗号の出力と呼ばれ、Ｖｉ＝（Ｌｉ＋Ｍｉｍｏｄ２３２）はＬＦＧ半暗号の出力と呼ばれる。
ＬＦＳＲ半暗号
ＬＦＳＲ半暗号は、ＬＦＳＲとＮＬＦとを含む。
【００１４】
ＬＦＳＲ状態は、（Ｘｉ＋３，Ｘｉ＋２，Ｘｉ＋１，Ｘｉ）で表される４個の３２ビットワードとして記憶される。状態は、ＬＦＳＲ状態更新関数を計算することによって（Ｘｉ＋４，Ｘｉ＋３，Ｘｉ＋２，Ｘｉ＋１）に更新される。このＬＦＳＲ状態更新関数は、線形モジュロ２関数である。
【００１５】
Ｘｉ＋４＝Ｘｉ＋２(+)（Ｘｉ＋１＜＜３１）(+)（Ｘｉ＞＞１）
ここで「＜＜」はゼロ充填左シフトを表し、「＞＞」はゼロ充填右シフトを表し、数「３１」と「１」はシフトすべきビットの数を表す。したがって（ｘ＜＜３１）は、最右ビット３１ビットを左に移動させ、それによって最左ビットの右にゼロを充填して最右ビットを最左ビットすなわち最上位ビットにすることを意味する。同様に（ｘ＞＞１）は、すべてのビットを１ビットだけ右にシフトし、最左ビットをゼロにして置き、古い最右ビットを落とすことを意味する。Ｘｉの最下位ビットは、無視される。
【００１６】
もしこの系列がビットストリームｂｔに変換されれば、このビット系列は線形再帰を満足する：
ｂｔ＋１２７＝ｂｔ＋６３ｍｏｄ２
このビットストリームに対応する特性多項式は、Ｘ１２７＋Ｘ６３＋１である。この特性多項式は、既約モジュロ２であって、このビット系列が（２１２７−１）の周期を有することを意味する。ＬＦＳＲは、Ｘｉ＋３、・・・、Ｘｉを有する４ワードアレイＳ［１］・・・、Ｓ［４］を使用して実現される。１クロックごとにＬＦＳＲは、Ａ＝Ｓ［２］(+)（Ｓ［３］＜＜３１）(+)（Ｓ［４］＞＞１）を計算する。これらの値は、シフトアップされ（Ｓ［４］←Ｓ［３］、Ｓ［３］←Ｓ［２］、Ｓ［２］←Ｓ［１］）、Ｓ［１］の値はＡにセットされる。ＬＦＳＲが更新された後にＮＬＦ出力Ｎｉが計算される。ＮＬＦは種々の演算ＸＯＲ、モジュラー加算を使用する。ＳＷＡＰ（Ａ）：は、Ａの上位１６ビットと下位１６ビットとをスワップし、Ｘｉ∧は１にされた最下位ビット（ＬＳＢ）を有するワードＸｉを表す。
【００１７】
ＮＬＦアルゴリズムを下記に示す。
１．Ａ←Ｘｉ＋３＋Ｘｉ∧ｍｏｄ２３２、ｃ１←桁上げ；
２．Ａ←ＳＷＡＰ（Ａ）；
３．もし（ｃ１＝０）であれば、Ａ←．Ｘｉ＋２＋Ａｍｏｄ２３２、ｃ２←桁上げ；
４．さもなければ、Ａ←Ｘｉ＋２(+)Ｘｉ∧＋Ａｍｏｄ２３２、ｃ２←桁上げ；
５．Ｎｉ←（Ｘｉ＋１(+)Ｘｉ＋２）＋Ａ＋ｃ２ｍｏｄ２３２  。
【００１８】
ＬＦＧ半暗号
ＬＦＧ状態は、１７個のワード（Ｙｉ＋１６，・・・，Ｙｉ）からなる。状態は、漸化式：
Ｙｉ＋１７＝Ｙｉ＋１２＋Ｙｉｍｏｄ２３２        （１）
を使用して（Ｙｉ＋１７，・・・，Ｙｉ＋１）に更新される。
ＬＦＧは、１７ワードアレイＧ［１］、・・・、Ｇ［１７］を使用して実現される。キースケジューリングは、Ｇ［１］、・・・、Ｇ［１７］を値Ｙ１６、・・・、Ｙ０に初期設定し、２個のポインタｒ、ｓをそれぞれ１７と５に初期設定する。出力Ｌｉは、Ｌｉ＝ＳＷＡＰ（Ｙｉ）として定義される。ＬＦＧ状態は、
Ｇ［ｒ］＋Ｇ［ｓ］＝Ｙｉ＋Ｙｉ＋１２＝Ｙｉ＋１７ｍｏｄ２３２
を計算することと、Ｇ［ｒ］の値（Ｙｉであった）をＹｉ＋１７の値で置き換えることとによって更新される。それからｒとｓの値は１だけ減らされる。ｒの値がゼロに達したとき、ｒの値は１７にリセットされる。ｓの値がゼロに到達したとき、ｓの値は１７にリセットされる。出力Ｍｉは、
Ｍｉ＝Ｇ［１＋（ｓ＋（Ｙｉ＋１７＞＞２８）ｍｏｄ１６）］
と定義される。
【００１９】
縮小モジュロ１６の結果として、系列｛Ｙｉ｝によるＭｉに関する式は、ｉｍｏｄ１７の値にしたがって変化する。ＬｉとＭｉとＮｉとが計算された後にＳＳＣ２は、Ｚｉ＝（（Ｌｉ＋Ｍｉｍｏｄ２３２）(+)Ｎｉ）を出力し、ｉを増加させ、この処理を反復する。
【００２０】
ＬＦＳＲ半暗号をアタックすること：背景
ＳＳＣ２から出力されるある一定のワードの最下位ビット（ＬＳＢｓ）間には相関性が存在する。更に遅延フィボナッチジェネレータ半暗号は、１７・２３１・（２１７−１）≒２５２という小さな周期ＴＴを有する。したがって、もし距離ＴＴだけ離れたＳＳＣ２タイプの出力ストリームの二つのセグメントが排他論理和（ＸＯＲ）を取られれば、ＬＦＧ半暗号からの寄与は打ち消されて、解析すべき二つのフィルタリングされたＬＦＳＲストリームの排他論理和が残される。
【００２１】
Ｚ’ｉ＝Ｚｉ(+)Ｚｉ＋ＴＴ＝Ｎｉ(+)Ｎｉ＋ＴＴを計算することによって、ＬＦＳＲを分離してアタックすることが可能になる。Ｚ’ｉワードのＬＳＢ内の相関は、アタックがランダムビットストリームからＳＳＣ２の出力間を区別することを可能にする。このようにして一実施形態ではアタックは、この小さな周期ＴＴを利用する。一実施形態は、いかなる周期ＴＴを有するいかなるデータストリームでも復号できる。
【００２２】
Ｎｉは、４ワード状態Ｓｉのビットの線形関数に対する相関を示す。一実施形態では、状態Ｓｉの線形関数は、ｌ（Ｓ）＝Ｓ［１］１５(+)Ｓ［１］１６(+)Ｓ［２］３１、(+)Ｓ［３］０(+)Ｓ［４］１６と定義される。ここで下付き文字はワード(最下位ビットであるビット０を有する)の特定のビットを示す。そしてＰ（ＬＳＢ（Ｚｉ）＝ｌ（Ｓ１））＝５／８。直観的にｌ（Ｓ）項のうちの３個の項はＸＯＲを取られてＮｉの最下位ビットを形成し、他の二つの項は、ｌ（Ｓ）結果が桁上げ伝播によってどのように反転または影響され得るかに影響を与える桁上げビットに寄与する。
【００２３】
同様にＮｉ＋ＴＴは、状態Ｓｉ＋ＴＴと相関しているが、ＬＦＳＲ状態更新関数は完全に線形であるので、今度はＳｉ＋ＴＴのビットがＳｉのビットの線形関数となる。このようにしてＬＳＢ（Ｚ’ｉ）は、Ｌ（Ｓｉ）＝ｌ（Ｓｉ）(+)ｌ（Ｓｉ＋ＴＴ）に対する相関を示す。
【００２４】
ＬＦＳＲ状態のワードはビット系フィードバック多項式にしたがって更新されるが、ワードサイズ（３２ビット）が２の累乗なので、状態の全ワードも漸化式に従い、このフィードバック多項式の３２乗によって関係付けられる。
もし二つのストリームＺｉとＺｉ＋ＴＴとが独立であれば、相関確率はＰ（ＬＳＢ（Ｚ’ｉ）＝Ｌ（Ｓｉ））＝１７／３２となるであろう。これは１−１７／３２＝０．４６８７５という誤り確率を意味する。しかしながら、これらのストリームは独立ではなく、実際には誤り確率は予期された０．４６８７５より小さい。この幸運な事象は、一実施形態の高速相関アタックをより効率的にする。
【００２５】
一実施形態ではＬＦＳＲ半暗号に対するアタックは、その最下位ビットだけがアタックに利用されるワードＺ’ｉを最初に収集することによって進む。これは、ＴＴだけ離れた単一出力ストリームの二つのセグメントを必要とする。相関計算は、異なる量の入力に対する出力ストリームを「訂正する」ために行われる。一例示的実施形態では、入力の量は２９，０００，０００ビットと３２，０００，０００ビットの間で変化する。経験的にはこれらの試みの約２／３は終了して正しい出力Ｌ（Ｓｉ）を生成するであろう。これらのトライアルの一部は、大量の残った誤りを訂正せずに多数回の反復を行って「ボグダウンする（ｂｏｇ  ｄｏｗｎ）」、可能性がある。計算が「ボグダウンした」ときは、計算は多数回のラウンドの後に任意に終了する。一例示的実施形態では計算が「ボグダウンする」と、計算は１０００回のラウンドの後に任意に終了する。
【００２６】
いったんアタックが暗号出力を訂正したと考えられると、線形代数が使用されて訂正済み暗号出力を初期状態Ｓ０に関係付ける。Ｓ０が正しいことを検証するためにこの初期状態から系列Ｚ’ｉ＝Ｚｉ(+)Ｚｉ＋πが再構成できる。もしＳ０が正しくないか、アタックが「ボグダウン」すれば、異なる数の入力ビットを試すことができる。
【００２７】
一実施形態では、ＬＦＳＲ半暗号に対するアタックは、フィルタリングされた出力ワードすなわちＬＦＳＲ半暗号出力の最下位ビットと、ＬＦＳＲ状態ビットのうちの少なくとも５ビットとの間の相関を利用する高速相関アタックである。このアタックは、相関アタックがより少ない項を有する多項式に対して、より良く作用するので、ＬＦＳＲのフィードバック多項式が単に三項式Ｘ１２７＋Ｘ６３＋１であるという事実によって助けられる。
【００２８】
いかなる特定のＬＦＳＲでも、その「特性」多項式によって定義されるが、この「特性」多項式はＬＦＳＲのビットが満足するであろう最低次数の多項式である。ＬＦＳＲはまた、他の多項式、例えば特性多項式の自乗を満足するであろう。特性多項式は必ずしも三項式ではないが、ＳＳＣ２に関する特性多項式は三項式である。
【００２９】
もしＬＦＳＲ半暗号の非線形関数（ＮＬＦ）が完全であれば、ＬＦＳＲ半暗号の出力とＬＦＳＲ状態ビットの任意の線形関数との間には有用な相関は存在しないはずである。反対に、もしＬＦＳＲ半暗号の出力とＬＦＳＲ状態ビットの任意の線形結合との間に相関が存在すれば、この相関は、初期状態を復元するために高速相関アタックによって使用できる。
【００３０】
一実施形態ではＬＦＳＲ半暗号の出力ビット｛Ｂｉ｝は、確率Ｐ＜０．５を有する誤りビット｛Ｅｉ｝によって修正されたＬＦＳＲからの出力ビット｛Ａｉ｝の線形関数に等しい。誤り確率Ｐは、既知の相関の反対である。すなわち相関は（１−Ｐ）に等しい。簡単に言えば、一実施形態の高速相関アタックの手法は、誤りであることの高い確率を有するＬＦＳＲ半暗号の出力ストリーム内の特定のビットを識別するためにＡｉビットに対するＢｉビットの相関のせいでＢｉビットが従う漸化式を利用する。一旦ＬＦＳＲ半暗号の出力ストリーム内の特定のビットが、誤りであることの高い確率を有する（すなわちＡｉビットとは異なるＢｉビット）と識別されれば、これらのビットは訂正され、すなわち反転される。
【００３１】
ＬＦＳＲ半暗号をアタックすること
一実施形態の高速相関アタックに関する入力データストリーム（入力データセットとも呼ばれる）は、ＬＦＳＲ半暗号出力からのデータを含む。
一実施形態では高速相関アタックは、複数のラウンドを含む。各ラウンドでは、誤りであることの高い確率を有するＬＦＳＲ半暗号の出力ストリーム内の特定のビットが識別され、これらの識別されたビットは反転される。各ラウンドで高速相関アタックは、各漸化式Ａｊ＋Σｉ∈ＴＡｉ≡０（ｍｏｄ２）に対応する入力データセット（Ｂｊ＋（Σｉ∈ＴＢｉ）ｍｏｄ２）内の各ビット位置ｊに関して計算を行う。ここで集合Ｔは、特定の漸化方程式に関するインデックスの集合である。これらの漸化方程式は、パリティ検査方程式とも呼ばれる。この入力データセットは、暗号解析されるデータ、すなわちＳＳＣ２タイプの暗号化システムからの出力である。
【００３２】
与えられたビットに関して多くのパリティ検査方程式が存在する。例えば、ビットｊ＝１００が与えられたとすると、このビットに関する多くのパリティ検査方程式が存在する。一つのパリティ検査方程式は、集合Ｔ＝｛１２７，６３｝、すなわちＢ１２７＋Ｂ６３＋１を持つことができる。明らかに、第ｊ番目のビット（ｊ＝１００）が集合Ｔの要素の中央に在る場合に第ｊ番目ビットを加算することは、Ｂ１２７＋Ｂ１００＋Ｂ６３を与える。もう一つのパリティ検査方程式は、集合Ｔ＝｛２４３８４，１２３５１｝、すなわちＢ２４３８４＋Ｂ１２３５１＋１を持つことができる。明らかに、第ｊ番目のビット（ｊ＝１００）が集合Ｔの要素の左に在る場合に第ｊ番目ビットを加算することは、Ｂ１００＋Ｂ１２３５１＋Ｂ２４４８４を与える。
【００３３】
ビットｊに関する誤り確率Ｐ（Ｂｊ≠Ａｊ）は、満足された漸化式（Ｂｉ＋（Σｉ∈ＴＢｉ≡０（ｍｏｄ２）の数と満足されなかった漸化式の数とに基づいて計算される。全漸化方程式にモジュラスが適用される。もし合計ｍｏｄ２がゼロであれば、漸化式は満たされる。合計ｍｏｄ２の結果は、ゼロ（０）（パリティ検査を満足する）か１（１）(漸化式を満足しない)のいずれかになる。
【００３４】
もし所定の確率Ｐに関してＬＦＳＲ半暗号の出力ストリーム内に十分なビットが存在すれば、多数回のラウンドで満足されない方程式を計数してビットを訂正するという処理は最終的に、すべてのパリティ検査方程式が同時に満足されることを意味して無矛盾のＬＦＳＲ出力ストリームが残るまで収束するであろう。それから線形代数が使用されてＬＦＳＲの対応する初期状態が復元される。
【００３５】
各ラウンドで誤り確率Ｐは、相関アタックの速度と精度とを向上させるために動的に評価される。相関アタックアルゴリズムは、所定のラウンドに対する入力パラメータとして誤り確率Ｐを有する。誤り確率Ｐは、１ラウンドの計算の間中、一定に保たれる。ビット確率は、各ラウンドの初めにＰにリセットされる。各ラウンドで誤り確率を動的に評価することによって誤り確率は、誤りビットが訂正されるにつれてラウンドごとにますます減少する傾向にあり、これが成功した正確な相関アタックのより大きな可能性という結果をもたらす。更にパリティ検査方程式を満足するという収束は、動的に評価される誤り確率によって誤りビットがより速く訂正されそうであるという理由で、より高速になりそうである。
【００３６】
所定の誤り確率Ｐに関しては、入力データによって満足されると期待されるパリティ検査方程式の割合を計算することが単刀直入である。この処理はまた可逆的である。満足されたパリティ検査方程式の割合αがいったん決定されると、対応する誤り確率は計算できる：
δ＝１−２αとすると、Ｐ＝（１／２）（１−δ１／３）となる。
【００３７】
デルタは、中間変数であって、誤り確率０．５からの入力データの「偏り」である。Ｐに関して方程式を書き換えてδを消去すると：
Ｐ＝（１／２）（１−（１−２α）１／３）となる。
各ラウンドはパリティ検査方程式をカウントすることから始まるので、そのラウンドに関してＰを計算することは単純なことである。最初のデータセットに関しては、Ｐは０．５にかなり近い。ほぼ半数のビットが「誤り」であろう、すなわち誤りを有するであろうという理由で、ＬＦＳＲ半暗号の非線形関数が良好であるほど、Ｐは０．５に近いであろう。相関アタックアルゴリズムが進行するにつれて、ビットは訂正されてＰは減少する。
【００３８】
各ラウンドで、データの最初の通り越しは、各ビットに関して満足されないパリティ検査の数を計算（および記憶）する。満足されないパリティ検査の全比率からこのラウンドに関してＰが計算され、その計算されたＰから、閾値を超えていればビットが誤りとみなされる満足されないパリティ検査の数に関するその閾値がパリティ検査方程式の各々の数に関して計算される（データセット内の異なるビット位置では、パリティ検査方程式の数は、ある「データのエッジからのずれ」で僅かに異なるであろう)。Ｐ＜０．４のとき、満足されないパリティ検査の半数を超えるパリティ検査は、誤りビットの確率が０．５より大きくてそのビットは訂正すべきであることを意味するということはほぼ正しい。しかしながら、Ｐ＞０．４のときは、ビットを反転することが理論的に正当化される前に、更に多くの方程式が満足されないことが必要である。相関アタックアルゴリズムの最終的な成功は、これら初期の決定に極めて依存していることが知られている。それからデータの通過が行われ、反転を必要とするビットは反転される。反転される各ビットに関して、そのビットだけでなく、そのビットを有するパリティ検査方程式に含まれる各ビットに関しても満足されないパリティ検査のカウントが訂正される。訂正係数は、すべてのビットに効果的に同時に訂正が適用されるように、別のアレイに蓄積される。満足されないパリティ検査を持たないビットは、留意される。初期のラウンドではこの増分的手法は、あまり節約にならないが、１ラウンド当りの訂正ビットがより少ないので、計算の節約はかなり大きくなる。
【００３９】
相関アタックアルゴリズム：初期設定セクション
図１は、一例示的実施形態の相関アタックアルゴリズムの初期設定セクションの流れ図である。ステップ１００で、満足されたパリティ検査の総数はゼロに初期設定される。ステップ１０２で、データストリームのＮビットが入力される。ここでＢｉ：ｉ＝０、・・・、Ｎ。これらのＮ個のビットは、ＬＦＳＲ半暗号出力のＺ’ｉワードから取られる。
【００４０】
ステップ１０４で、Ｎ内の各ビットが検査される。ステップ１０６で、ビットｉに関して満足されたパリティ検査の数、すなわちＳｉはゼロに初期設定される。ステップ１０８で、インデックスｉがゼロであるかどうか決定するために検査が行われる。もしインデックスｉが、入力データストリームを通過して行く最初の反復であることを意味するゼロであれば、ステップ１１０で第ｉ番目のビットに関するパリティ検査の総数が決定される。このようにして第ｉ番目のビットに関するパリティ検査の総数Ｎｉは、一度だけ決定される。ビットｉに関するパリティ検査の総数は一定数である。ステップ１１０の後に制御の流れはステップ１１２に進む。ステップ１０８で、もしインデックスｉがゼロでなければ、制御の流れはステップ１１２に進む。
【００４１】
ステップ１１２で、ｉに近い集合Ｔ内の各要素が検査される。すなわち所定のビットｉに関する集合Ｔ内の各要素が検査される。ステップ１１４で、各ビットｉに関する満足されたパリティ検査の数がカウントされる。すなわちＳｉ＝Ｓｉ＋１となる。相関アタックアルゴリズムのコンテキストにおけるＳｉは、ビットｉに関する満足されたパリティ検査の数である。ステップ１１６で、集合Ｔのすべての要素が検査されたかどうかを決定するために検査が行われる。もし集合Ｔ内の要素すべてが検査されたのでなければ、制御の流れはステップ１１２に行く。そうでなければ制御の流れはステップ１１８に進む。
【００４２】
ステップ１１８で、すべてのビットｉに関する満足されたパリティ検査の総数が累計される。すなわちΣＳｉとなる。ステップ１２０で、Ｎ内の各ビットが検査されたかどうかを決定するために検査が行われる。もしＮ内の各ビットが検査されていなければ、制御の流れはステップ１０４に進む。すなわち相関アルゴリズムは、Ｎ個のビットのうちの次のビットを検査する。もしＮ内の各ビットが検査されていれば、制御の流れは図２のステップ２００に進む。
【００４３】
パリティ検査方程式
一例示的実施形態ではパリティ検査方程式は、特性多項式Ｘ１２７＋Ｘ６３＋１と下記の五つの多項式：
Ｘ１６１２９＋Ｘ４０３３＋１
Ｘ１２１６０＋Ｘ４１５９＋１
Ｘ１２２２４＋Ｘ８２５５＋１
Ｘ１６３８３＋Ｘ１２２８８＋１
Ｘ２４３８４＋Ｘ１２３５１＋１
とから生成される。
【００４４】
特性多項式とこれら５個の多項式はともに、これらが多項式を生成するために使用されるので、シード（ｓｅｅｄ）多項式と呼ばれる。
各多項式は、下記のような特定の集合Ｔを意味する。
Ｘ１２７＋Ｘ６３＋１＝＞Ｔ＝｛１２７，６３｝
Ｘ１６１２９＋Ｘ４０３３＋１＝＞Ｔ＝｛１６１２９，４０３３｝
Ｘ１２１６０＋Ｘ４１５９＋１＝＞Ｔ＝｛１２１６０，４１５９｝
Ｘ１２２２４＋Ｘ８２５５＋１＝＞Ｔ＝｛１２２２４，８２５５｝
Ｘ１６３８３＋Ｘ１２２８８＋１＝＞Ｔ＝｛１６３８３，１２２８８｝
Ｘ２４３８４＋Ｘ１２３５１＋１＝＞Ｔ＝｛２４３８４，１２３５１｝  。
【００４５】
与えられた第ｊ番目のビットを集合Ｔの要素の左と中央と右とに置くことによって、各多項式または集合Ｔから３個の潜在的に有用なパリティ検査方程式が生成される。
各多項式に関して、生成された３個のパリティ検査方程式はそれぞれ、ビットｊが集合Ｔのその他の項の左、中央あるいは右に在る場合に左パリティ検査方程式、中央パリティ検査方程式、右パリティ検査方程式と呼ばれる。
【００４６】
このようにしてｊ＝１００に関しては、
【００４７】
【数１】
2005527993.tif 000003
ビットｊ＝１００が左ビットであれば、パリティ検査方程式ｂ１００＋ｂ１６３＋ｂ２２７が生成される。ｂ１６３は、１００に６３を加算して１６３という結果を得ることによって導出できる。ｂ２２７は、１００に１２７を加算して２２７という結果を得ることによって導出できる。ビットｊ＝１００が中央ビットであれば、パリティ検査方程式ｂ３７＋ｂ１００＋ｂ１６４が生成される。ｂ３７は、１００から６３を減算して３７という結果を得ることによって導出できる。ｂ１６４は、３７に１２７を加算して１６４という結果を得ることによって導出できる。ビットｊ＝１００が右ビットであれば、パリティ検査方程式ｂ−２７＋ｂ３７＋ｂ１００が生成される。ｂ−２７は、１００から１２７を減算して−２７という結果を得ることによって導出できる。ｂ３６は、１００から６３を減算して３７という結果を得ることによって導出できる。
【００４８】
第３番目のパリティ検査方程式は入力データストリームのエッジをずらすので、この第３番目のパリティ検査方程式は有用ではない。したがって多項式Ｘ１２７＋Ｘ６３＋１から下記のように二つのパリティ検査式が生成された。
【００４９】
【数２】
2005527993.tif 000004
ある多項式が有用なパリティ検査方程式を生成すると、その多項式の二乗が生成される。このように、上記の例では多項式Ｘ１２７＋Ｘ６３＋１は有用なパリティ検査方程式を生成したので、多項式Ｘ１２７＋Ｘ６３＋１の二乗が生成される。実際に多項式Ｘ１２７＋Ｘ６３＋１は、二つの有用なパリティ検査方程式を生成した。
【００５０】
多項式Ｘ１２７＋Ｘ６３＋１の二乗は、多項式Ｘ２５４＋Ｘ１２６＋１であって、これは集合Ｔ＝｛２５４，１２６｝を意味する。ビットｊ＝１００が左ビットであれば、パリティ検査方程式ｂ１００＋ｂ２２６＋ｂ３５４が生成される。ｂ２２６は、１００に１２６を加算して２２６という結果を得ることによって導出できる。ｂ３５４は、１００に２５４を加算して３５４という結果を得ることによって導出できる。ビットｊ＝１００が中央ビットであれば、パリティ検査方程式ｂ−１２６＋ｂ１００＋ｂ１２８が生成されるが、これはデータストリームのエッジをずらす。したがって、このパリティ検査式ｂ−１２６＋ｂ１００＋ｂ１２８は有用でない。ｂ−１２６は、１００から２２６を減算して−１２６という結果を得ることによって導出できる。ｂ１２８は、−１２６に２５４を加算して１２８という結果を得ることによって導出できる。ビットｊ＝１００が右ビットであれば、パリティ検査方程式ｂ−１５４＋ｂ−２６＋ｂ１００が生成されるが、これはデータストリームのエッジをずらす。したがってこのパリティ検査方程式ｂ−１５４＋ｂ−２６＋ｂ１００は有用でない。ｂ−１５４は、１００から２５４を減算して−１５４という結果を得ることによって導出できる。ｂ−２６は、１００から１２６を減算して−２６という結果を得ることによって導出できる。二乗多項式が導出される多項式に関する右パリティ検査式は有用性を欠いているので、二乗多項式に関する右パリティ検査方程式は実際に生成される必要はない。
【００５１】
一旦、右パリティ検査方程式といったパリティ検査方程式が有用でないと分かると、多項式の将来の二乗のために右パリティ検査方程式を生成する必要はない。
二乗多項式のパリティ検査方程式の二つは有用でないので、二乗多項式の左パリティ検査方程式だけが有用である。中央パリティ検査方程式は有用でない。したがって、この二乗多項式が再び二乗されると、右パリティ検査方程式を生成することが不必要であることに加えて中央パリティ検査方程式を生成する必要性も存在しない。
【００５２】
【数３】
2005527993.tif 000005
多項式は、それが有用なパリティ検査方程式を生成しなくなるまで二乗され続ける。上記の例では、シード多項式Ｘ１２７＋Ｘ６３＋１からの多項式の生成は、ビットｊ＝１００に関しては、左パリティ検査方程式の右の項がデータストリームの右辺のエッジから外れるとき、停止するであろう。すなわち、上記の例ではシード多項式Ｘ１２７＋Ｘ６３＋１からの多項式の生成は、ビットｊ＝１００に関しては、左パリティ検査方程式の右の項がデータストリームの最右のインデックスより大きくなるときに、停止するであろう。
【００５３】
ビットｊは、データストリーム内の単に１／１００のビットであるから、この他のシード多項式は、他のシード多項式に関する生成されたパリティ検査方程式がデータストリームのエッジをずらすという理由でパリティ検査方程式に寄与しない。
多項式生成およびパリティ検査方程式の処理は、データストリーム内の各ビットｊに関して行われる。
【００５４】
相関アタックアルゴリズム：主要セクション
図２は、一例示的実施形態の相関アタックアルゴリズムの主要セクションの流れ図である。ステップ２００で、αと動的確率Ｐとｍａｘ（最大）Ｎｉとが決定される。αは、満足されたパリティ検査方程式の総数対パリティ検査方程式の総数の比率である。ｍａｘＮｉは、Ｎビットのビット列内のあるビットに関するパリティ検査の最大数である。言い換えれば、Ｎ個のビットのうちのパリティ検査の最大数を有するビットｉがｍａｘＮｉの下付き文字である。動的確率Ｐは、一旦αが決定されたときに決定される。
【００５５】
α＝ΣＳｉ/ΣＮｉ＝＞Ｐ
一旦ΣＳｉとΣＮｉとが決定されると、動的確率Ｐが暗示される、すなわちＰが決定できる。一例示的実施形態では、この動的確率Ｐは二項確立分布に基づいて計算される。
ステップ２０４で、相関アタックアルゴリズムは、Ｎ内の各ビットｉをループする。ｉの各反復が１ラウンドである。ステップ２０６で、ビットｉを反転すべきかどうかを決定する反転ルックアップテーブル（flipping lookup table）が作成される。この反転ルックアップテーブルは、１ラウンドごとに作成される。この表は、ｍａｘＮｉに関する表を作成することがより小さなＮｉを有するビットｉに関する表、すなわちより少数のパリティ検査方程式を有するビットｉに関する表を包含するので、ｍａｘＮｉに関して作成される。表１は、例示的反転ルックアップテーブルを示す。
【００５６】
反転ルックアップテーブル
Ｎi 閾値  Ｓi
・              ・
・              ・
・              ・
１０            ５
１１            ５
１２            ５
１３            ６
１４            ６
１５            ６
１６            ７
その他
表１  。
【００５７】
反転ルックアップテーブルを生成するために、各Ｎｉに関して閾値Ｓｉが計算される。この閾値Ｓｉは、ビットｉを反転するためにはＳｉがより小さくなければならない満足された方程式の数である。
閾値Ｓｉは、Ｐｉを計算することによって決定される。Ｐｉは、ビットｉが誤りであって反転すべきである確率である。Ｐｉは、ＰとＮｉとＳｉとの関数である。
【００５８】
入力データにおける各ビットが誤りであると観測される確率であるＰと、ある特定のビットに適用されるパリティ検査方程式の数であるＮとを与えれば、Ｎ個の方程式のうちのある数Ｓ個の方程式が満足される（定義により残りの方程式は満足されない）確率である確率ＰＳは計算できる。
【００５９】
Ｐｉ公式を単純化するためにわれわれは先ず、Ｐに対応する「バイアス」Ｂを計算する：
Ｂ＝１−（１−２Ｐ）２
二項確率分布により、Ｎ個の方程式のうちにＳ個の満足された方程式が存在する確率は
ＰＳ＝ＰＢＳ（１−Ｂ）Ｎ−Ｓ／｛ＰＢＳ（１−Ｂ）Ｎ−Ｓ＋（１−Ｐ）ＢＮ−Ｓ（１−Ｂ）Ｓ｝
閾値Ｓｉを決定するための最も単純なアルゴリズムは、閾値Ｓｉ変数をゼロから始めてＰｉが０．５より大きくなるまでＰｉの計算ごとに閾値Ｓｉ変数を増加させることである。Ｐｉが０．５以下になったとき、閾値Ｓｉ変数結果は反転ルックアップテーブル内の閾値Ｓｉに格納される。
【００６０】
単純な閾値Ｓｉアルゴリズムを下記に示す。
閾値Ｓｉ変数＝０〜Ｎｉに関して
Ｐｉを計算する
もしＰｉ≦０．５であれば、ループを退出する
ループの終了
閾値Ｓｉ＝閾値Ｓｉ変数
閾値Ｓｉアルゴリズムは、反転ルックアップテーブル内の各Ｎｉに関して実行される。
【００６１】
下記の擬似コードは、一旦反転ルックアップテーブルが作成されたときの相関アタックアルゴリズムの主要セクションの概要を与える。
各ｉに関して
＊  Ｓｉと所定のＮｉ関する閾値Ｓｉとを比較する
もし「Ｓｉ＜所定のＮｉに関する閾値Ｓｉ」であれば
そのビットを反転し
各パリティ検査方程式に関して、集合Ｔ内のその他の２ビットを検査し、
そして
それらのＳｉカウントを訂正する。
【００６２】
一旦ステップ２０６で反転ルックアップテーブルが作成されると、Ｓｉが所定のＮｉに関する閾値Ｓｉより小さいかどうかを決定するために検査が行われる。もしＳｉが所定のＮｉに関する閾値Ｓｉより小さければ、ビットｉを訂正すなわち反転する必要があるので、制御の流れはステップ２１４に進む。そうでなければ制御の流れはステップ２１０に進む。
【００６３】
ステップ２１４でビットｉは訂正される。ビットｉに関する満足された方程式の数は更新される。ビットｉに関する満足されたパリティ検査方程式の数は、ビットｉに関する満足されたパリティ検査方程式の前の数よりも小さいビットｉに関する満足されたパリティ検査方程式の数にセットされる。
【００６４】
ステップ２１６で相関アタックアルゴリズムは、ビットｉに関する各パリティ検査方程式をループする。ステップ２１８で相関アタックアルゴリズムは、所定のパリティ検査方程式に関するビットｉ以外の各ビットｊをループする。所定のパリティ検査方程式に関する集合Ｔ内の各ビットｊが検査される。
【００６５】
ステップ２２０でパリティ検査方程式は、この方程式が所定のビットｊに関して満足されるかどうかを決定するために検査される。もし所定のビットｊに関するこのパリティ検査方程式が満足されれば、この方程式はビットｉが一旦反転された場合にはもう満足されない。したがってステップ２２２でビットｊに関する満足されたこのパリティ検査方程式の数は減らされる。もし所定のビットｊに関するこのパリティ検査方程式が満足されなければ、この方程式はビットｉが一旦反転された場合には満足される。したがって、ステップ２２４でビットｊに関する満足されたこのパリティ検査方程式の数は増やされる。制御の流れは、ステップ２２２、２２４の後にステップ２２６に進む。
【００６６】
ステップ２２６で所定のパリティ検査方程式に関する集合Ｔ内のｊビットの数が枯渇したかどうかを決定するために検査が行われる。もし集合Ｔ内のｊビットすべてが検査されたのでなければ、ビットｉ以外の集合内の次のビットｊが検査されて、制御の流れはステップ２１８に進む。もし集合Ｔ内のｊビットすべてが検査されたのであれば、制御の流れはステップ２２８に進む。
【００６７】
ステップ２２８で所定のビットｉに関するパリティ検査方程式のすべてが検査されたかどうかを決定するために検査が行われる。もし所定のビットｉに関するパリティ検査方程式すべてが検査されたのでなければ、制御の流れ派ステップ２１６に行き、所定のビットｉに関する次のパリティ検査方程式が検査される。そうでなければ制御の流れは、ステップ２１０に進む。
【００６８】
ステップ２１０では、Ｎ内のすべてのビットｉが検査されたかどうかを決定するために検査が行われる。もしＮ内のすべてのビットｉが検査されたのであれば、制御の流れはステップ２１２に進む。もしＮ内のビットｉすべてが検査されたのでなければ、制御の流れはステップ２０４に行き、次のビットｉが検査される。
【００６９】
一旦Ｎ内のすべてのビットが検査されると、ステップ２１２で、無矛盾のＬＦＳＲ出力ストリームが作成されたかどうかを決定するために検査が行われる。もし無矛盾のＬＦＳＲ出力ストリームが作成されたのであれば、ステップ２１４で線形代数が使用されて、このＬＦＳＲ出力ストリームに対応するＬＦＳＲの初期状態が回復されて、この相関アタックアルゴリズムは完了する。もし無矛盾のＬＦＳＲ出力ストリームが作成されたのでなければ、この相関アタックアルゴリズムは、ＬＦＳＲ半暗号出力のＺ’ｉワードからの異なるＮビットから再び開始される。
【００７０】
図３は、相関アタックアルゴリズムを実現する装置を例示するブロック図である。ＬＦＳＲ半暗号出力のＺ’ｉワードが装置３００に入力される。プロセッサ３０２は相関アタックアルゴリズムを実行し、メモリ３０４は入力されたワード、変数、コード、およびプロセッサ３０２によって作成され使用される種々雑多なデータを記憶する。プロセッサ３０２とメモリ３０４との間の接続は、装置３００の任意の数のユニットを介して行うことができる。
【００７１】
当業者は、方法のステップが本発明の範囲から逸脱せずに相互交換できることを理解するであろう。
当業者は、情報と信号が種々の異なる技術と手法のどれを使用してでも表現できることを理解するであろう。例えば、上述の説明を通して参照され得るデータ、命令、コマンド、情報、信号、ビット、記号およびチップは、電圧、電流、電磁波、磁場または磁性粒子、光学的場または光学的粒子、あるいはこれらの任意の組合せによって表現できる。
【００７２】
当業者は更に、ここに開示された実施形態に関連して説明された種々の例示的アルゴリズムのステップが電子的ハードウエア、コンピュータソフトウエアあるいは両者の組合せとして実現可能であることを認めるであろう。ハードウエアとソフトウエアとのこの相互交換可能性を明確に例示するために、種々の例示的コンポーネント、ブロック、モジュール、回路およびステップが一般的に、それらの機能の点から上記に説明されてきた。このような機能がハードウエアまたはソフトウエアとして実現されるかどうかは、システム全体に課せられる特定のアプリケーション上、設計上の制約に依存する。熟練した技能者であれば、各々の特定のアプリケーションに関して種々の方法で上述の機能を実現できるが、このような実現の決定は、本発明の範囲からの逸脱を引き起こすものと解釈すべきでない。
【００７３】
ここに開示された実施形態に関連して説明された種々の例示的論理ブロックは、汎用プロセッサ、ディジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、利用者書込み可能ゲートアレイ（ＦＰＧＡ）またはその他のプログラム可能論理素子、個別ゲートまたはトランジスタ論理、個別ハードウエアコンポーネント、あるいはここに説明された機能を実行するように設計されたこれらの任意の組合せによって実現あるいは実行され得るものである。汎用プロセッサはマイクロプロセッサでも良いが、代替としてこのプロセッサは、任意の通常のプロセッサ、コントローラ、マイクロコントローラ、あるいは状態マシンでも良い。プロセッサはまた、計算装置の組合せ、例えばＤＳＰとマイクロプロセッサの組合せ、複数のマイクロプロセッサ、ＤＳＰコアと接続した一つ以上のマイクロプロセッサ、その他このような如何なる構成でも良い。
【００７４】
ここに開示した実施形態に関連して説明された方法あるいはアルゴリズムのステップは直接的に、ハードウエアで、またはプロセッサによって実行されるソフトウエアモジュールで、あるいはこれら両者の組合せで具体化できる。ソフトウエアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、取外し可能ディスク、ＣＤ−ＲＯＭ、その他本技術で既知の如何なる形式の記憶媒体にも常駐可能である。例示的記憶媒体は、プロセッサがこの記憶媒体から情報を読み取り、またこの記憶媒体に情報を書き込むことができるように、プロセッサに連結される。代替として記憶媒体は、プロセッサと一体化することができる。プロセッサと記憶媒体は、ＡＳＩＣ内に常駐可能である。
【００７５】
開示された実施形態の前述の説明は、当業者であれば誰でも本発明の実施形態を製造または使用可能にするために与えられている。当業者には、これらの実施形態に対する種々の修正が直ちに明らかになるであろうし、またここに記載の一般的原理は、本発明の精神あるいは範囲から逸脱せずに他の実施形態に適用可能である。したがって本発明は、ここに示した実施形態に限定することを意図しておらず、ここに開示された原理と新規な特徴に整合する最も広い範囲にしたがうものとする。
【図面の簡単な説明】
【００７６】
【図１】一例示的実施形態の相関アタックアルゴリズムの初期設定セクションの流れ図である。
【図２Ａ】一例示的実施形態の相関アタックアルゴリズムの主要セクションの流れ図である。
【図２Ｂ】一例示的実施形態の相関アタックアルゴリズムの主要セクションの流れ図である。
【図３】相関アタックアルゴリズムを実現する装置を例示するブロック図である。
【符号の説明】
【００７７】
３００…装置、  ３０２…プロセッサ、  ３０４…メモリ、
【図１】
2005527993.tif 000006
【図２Ａ】
2005527993.tif 000007
【図２Ｂ】
2005527993.tif 000008
【図３】
2005527993.tif 000009
【国際調査報告】
2005527993.tif 000010
2005527993.tif 000011