JP2008508627A - 疑似ランダムデータシーケンスの生成 - Google Patents

Abstract

疑似ランダムデータシーケンス（３）を生成する方法であって、前記疑似ランダムデータシーケンス（３）は、Ｎビットの初期データシーケンス（９）における検索パターン（７）に対する検索をするための手順によって生成されることを特徴とし、前記検索手順は、一組の検索パターンの１つであるｒビットの特定の検索パターン（７）を前記初期データシーケンス（９）において検出する段階（Ｅ１）と、先行する段階（Ｅ１）の進行に依存する動作によってｋビットの出力パターン（２５）を判断する段階（Ｅ２）と、一連の出力パターン（２５）から疑似ランダムデータシーケンス（３）を連続して形成するために先行する段階（Ｅ１、Ｅ２）を反復する段階とを具備する。

Description

本発明は、符号化／復号化の分野に関し、疑似ランダムデータシーケンスを生成するシステム及び方法に関する。

本発明は、暗号化及び復号化が同一の秘密鍵を使用する対称暗号化を対象とするビットのシーケンスを生成することに供する点で、とても有利な用途を見出す。本発明は、暗号化動作及び復号化動作が同一である標準のストリーム暗号化方法に順応する。対称暗号化は通常、移動体通信（ＧＳＭ、ＵＭＴＳ等）、インターネット（ＳＳＬ等）、スマートカード（バンクカード）等のような、全種類の通信に使用される。

最も広く普及したストリーム暗号化方法は、ハードウェアを節約するために、線形フィードバックシフトレジスタを用いて暗号化されるべきメッセージに対して独立した一連の暗号化を生成する。

線形フィードバックシフトレジスタの主な欠点は、その線形性である。実際、レジスタ長に等しいレジスタの多数の出力ビットを知ること、及びレジスタに関連付けられたフィードバック多項式を知ることは、レジスタの出力ビットと全ての後続の状態とを判断することを可能にする。

従って、線形フィードバックシフトレジスタの線形性を“破る”ためには、例えば非線形ブール関数を用いて、複数のレジスタの出力を結合すること、及び場合によりその内部状態を結合することも標準的な習慣である。

図７は、第１線形フィードバックシフトレジスタ１１１ａと、第２線形フィードバックシフトレジスタ１１１ｂと、生成器１００の出力を選択するための手段１１２とを含む、欧州特許出願ＥＰ０６１９６５９で説明された“疑似ランダム数生成器（shrinking generator）”として知られる当該生成器１００を示す。

従って、各シフト上で、２つのレジスタ１１１ａ及び１１１ｂは、同時にシフトされる。第１レジスタ１１１ａの出力が１の場合、装置１００の出力は、第２レジスタ１１１ｂの出力に等しく、そうでない場合、出力されない。

疑似ランダム数生成器は、２つの線形フィードバックレジスタの出力だけでなく、より一般には任意の組の一連のビットを結合する。疑似ランダム数生成器は、１つの線形フィードバックレジスタが他の線形フィードバックレジスタを制御するストリーム暗号化方法の部類である。その目的は、レジスタの線形性を破るために、まず、採用された各種レジスタ間のシフト数、次に、２つの連続ビット間のシフト数を変更することにある。

“自動疑似ランダム数生成器”として知られる疑似ランダム数生成器の変形は、同一の原理に基づくが、単独のレジスタを使用する。レジスタの出力ビットは、２つずつ読み込まれる。第１ビットが１である場合にシステムの出力が第２ビットになり、そうでない場合に出力されないように、第１ビットは、第２ビットの出力を制御する。

線形フィードバックレジスタのみを使用することは、多数の欠点を有する。主な欠点は、装置の線形性から生じる脆弱性である。レジスタがブール関数を用いて結合される場合も不利である。ハードウェアレベルでは、これらの不利な点は、関数を実行する複雑性から生じる。また、この関数は、固定され、それを攻撃することを可能にする。

また、統計的方法は、疑似ランダム数生成器と他のクロック制御暗号化方法との所定の脆弱性を明らかにした。特に、疑似ランダム数生成器において、２つの出力ビット間で２つのレジスタによってもたらされるシフト数は、両レジスタに対して同じ量だけ変わる。

最後に、疑似ランダム数生成器の最後の欠点は、演算されるビット数に対する出力ビット数のその低い割合であり、平均して１／４に等しい。この割合は、自動疑似ランダム数生成器と同じであり、疑似ランダム数生成器の脆弱性の大部分を有する。

本発明の目的は、上記欠点を改善し、良好な品質の疑似ランダムデータシーケンスの生成を単純化することにある。

もう１つの目的は、出力ビット数と演算されたビット数との間の割合を１／４よりも高くする方法及び生成器を提案することにある。

さらにもう１つの目的は、低コストでかなり効率的な生成器を提供することにある。

上記目的は、疑似ランダムデータシーケンスを生成する方法を用いて達成され、前記疑似ランダムデータシーケンスは、Ｎビットの初期データシーケンスにおける検索パターンに対する検索の手順によって生成される。

故に、本発明による方法は、一つ以上のビットストリームの非線形結合により新たなビットストリームを得ることを可能にするパターンの検出に基づき疑似ランダムデータを生成する非線形方法に関する。

この方法は、容易に実施されるが、良好な品質の疑似ランダムデータシーケンスを生成するために、本質的な複雑性を有する。

検索手順は、
・一組の検索パターンの１つであるｒビットの特定の検索パターンを前記初期データシーケンスにおいて検出する段階と、
・先行する段階の進行に依存する動作によってｋビットの出力パターンを判断する段階と、
・一連の出力パターンから疑似ランダムデータシーケンスを連続して形成するために先行する段階を反復する段階とを具備する。

前記検索パターンを検出する段階と前記出力パターンを判断する段階とは、前記検索パターンを検出するために前記初期データシーケンス上でウィンドウをシフトするためのシフトモードを定義するための第１組の規則を含む一連の動作によってもたらされ、前記ウィンドウは、前記初期データシーケンス上で特定の初期位置と特定のビットサイズとを有する。

一連の動作は、前記初期データシーケンス上で前記ウィンドウのシフトを停止するための条件を判断する第２組の規則をさらに含む。

前記第２組の規則からの規則は、前記ウィンドウのシフト及び／又はコンテンツの関数として、前記１組の検索パターン及び／又は前記出力パターンの更新を管理する。

前記一連の動作は、所定の条件が満たされるまで反復される。

一連の動作は、各実行の後に有利に変更される。

本発明の特徴によると、一連の動作は、１ビットの検索パターンを検出するために、及び１ビットの出力パターンを判断するために、各実行の後に引続き同じ動作のままであり、ビット毎に連続して前記初期データシーケンス上で１ビットのウィンドウをシフトする。

本発明の第１実施形態において、一連の動作は、
・検索パターンにウィンドウからのビットを置く段階と、
・現在のビットから次のビットへ、ビット毎にウィンドウをシフトする段階と、
・ウィンドウのコンテンツが検索パターンのそれと等しい場合、第１法則に従い出力パターンを更新する段階と、
・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、第２法則に従い出力パターンを更新する段階と、
・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、次のビットへビット毎にウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけウィンドウをシフトする段階と、
・出力パターンを出力する段階とを含む。

第１実施形態において、第１法則は、出力パターンに特定値ｂを割り当て、第２法則は、前記特定値ｂ及び値１の２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てる。

第２実施形態において、第１法則は、特定値ｂ及び検索パターンの値Ｅの２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当て、第２法則は、前記特定値ｂと、検索パターンの値Ｅと、値１との２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てる。

第３実施形態において、一連の動作は、
・検索パターンに第１ウィンドウからのビットを置く段階と、
・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
・第１ウィンドウのコンテンツが検索パターンの値に等しい場合、第１特定値ｂ_１及び検索パターンの値Ｅの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第１ウィンドウのコンテンツが検索パターンの値Ｅに等しくない場合、前記第１特定値ｂ_１と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、次のビットへビット毎に第１ウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
・第２ウィンドウからのビットによって検索パターンの値を置き換える段階と、
・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しい場合、第２特定値ｂ_２と、出力パターンの現在の値ｓと、検索パターンの値Ｅとの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、出力パターンの現在の値ｓと、前記第２特定値ｂ_２と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、次のビットへビット毎に第２ウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
・出力パターンを出力する段階とを含む。

本発明の用途において、前記疑似ランダムデータシーケンスの各ビットは、暗号化されたデータシーケンスを形成するために、２を法とする加算によって暗号化されるべきメッセージのデータシーケンスの対応するビットに結合される。

また、本発明は、Ｎビットの初期データシーケンスにおける検索パターンに対する検索のための検索手段を含む疑似ランダムデータシーケンスの生成器を提供する。

生成器の検索手段は、
・一組の検索パターンの１つであるｒビットの特定の検索パターンを前記初期データシーケンスにおいて検出するための検出手段と、
・前記検索パターンの検出の進行に依存する動作に従いｋビットの出力パターンを判断するための判断手段と、
・一連の出力パターンから疑似ランダムデータシーケンスを生成するための反復手段とを含む。

検出手段は、前記初期データシーケンス上でシフトされるよう適合されたウィンドウと、前記初期データシーケンス上で前記ウィンドウのシフトを制御するための第１制御手段とを含む。

判断手段は、前記一組の検索パターン及び／又は前記出力パターンを更新するための第２制御手段を含む。

生成器は、Ｎビットの初期データシーケンスを生成するための初期手段（１１）をさらに含む。

初期手段は、線形フィードバックシフトレジスタを含む。

また、本発明は、上記特徴を有する生成器と、排他的ＯＲ論理ゲートを含む符号化装置とを目的とする。

また、本発明は、各々が符号化装置を含む少なくとも２つのエンティティを含むセキュアシステムを目的とする。

図１は、疑似ランダムデータシーケンス３を生成するための本発明による生成器１の一例を概略的に示す。

生成器１は、Ｎビットの初期データシーケンス９における検索パターン７に対して検索するための検索手段５を含む。検索パターンは、一組の検索パターンに含まれる。

“パターン”という用語は、０及び１以外からなる任意の単語を指すために以下で使用される。例えば、０、１１、０００、１０１０、００１１１は、１、２、３、４及び５の長さをそれぞれ備えたパターンである。また、“空”パターンは、空単語である。

Ｎビット（Ｎが整数）の初期データシーケンスは、最大周期の線形フィードバックシフトレジスタを含むことができる初期手段１１によって生成される。

線形フィードバックシフトレジスタは、フィードバック多項式と呼ばれる多項式によって表される、テーブル入力の線形結合が提供された有限長（レジスタ）のビットのテーブルである。各シフト上で、最高指数を備えたビットが出力され、全ての他のビットが１指数だけシフトされ、最低指数を備えたビットがシフトの前に線形結合の値を取る。

フィードバック多項式は、最大周期の線形シフトレジスタに対応する原始多項式、例えばＰが原始多項式である、Ｑ＝（ｘ^２＋１）Ｐの式の多項式にすることができる利点がある。

生成器１の検索手段５は、検出手段１３と、判断手段１５と、反復手段１７とを含む。

検出手段１３は、ｒがＮ未満の整数である、初期データシーケンスにおけるｒビットの検索パターン７を検出する。判断手段１５は、検出手段１３によって検出される検索パターン７が属する一組の検索パターンを定義する。

検出手段は、初期データシーケンス９上でシフトされるように適合されたウィンドウ１９と、初期データシーケンス９上でウィンドウ１９のシフトを制御するための第１制御手段２１とを含む。

各ウィンドウ１９は、初期データシーケンス９における特定の初期位置に置かれ、特定のビットサイズを有する。例えば、初期データシーケンス９上に置かれたサイズｔ（ｔは、Ｎ未満の整数である）のウィンドウ１９は、シーケンス９のまさにｔビットを各シフト上に曝すためにシーケンス９上でシフトされることができるマスクである。

判断手段１５は、接続２３を介して検出手段１３と交信する。判断手段１５は、検索パターン７に対する検索の進行に依存する動作によってｋビット（ｋは、Ｎ未満の整数である）の出力パターン２５を判断する。

実際、判断手段１５は、一組の検索パターン及び／又は出力パターン２５を定義又は更新するための第２制御手段２７を含む。

また、反復手段１７は、それぞれ接続２９及び３１を介して検出手段１３及び判断手段１５に接続される。

従って、所定の停止条件が満たされない場合、例えば出力パターン２５が丁度出力された旨の信号を判断手段１５から受信した場合、反復手段１７は、検出及び判断動作を再開するために検出手段１３及び判断手段１５に対して信号を交わすことができる。また、反復手段１７は、検出手段１３及び判断手段１５に対して信号を交わすことによって停止条件をテストすることができる。これは、一連の出力パターン２５を生成し、連続形式による疑似ランダムデータシーケンス３になる。

また、反復手段１７は、検出手段１３及び判断手段１５の第１又は第２制御手段２１又は２７に統合されうる点に留意すべきである。

図２は、インターネット、ＧＳＭ、ＵＭＴＳ等の種類の通信ネットワーク３５を介して相互接続された少なくとも２つのエンティティを含むセキュアシステム３１を示す。

この図の例は、第２エンティティ３３ｂへ通信ネットワーク３５を介して接続された第１エンティティ３３ａを示す。第１エンティティ３３ａ（それぞれ第２エンティティ３３ｂ）は、第１端末３７ａ（それぞれ第２端末３７ｂ）と、第１符号化装置３９ａ（それぞれ第２符号化装置３９ｂ）と、第１モデム４１ａ（それぞれ第２モデム４１ｂ）とを含み、モデム４１ａ及び４１ｂは、通信ネットワーク３５に対してインタフェースするための任意の装置からなる。

各第１及び第２符号化装置３９ａ、３９ｂは、上述のような疑似ランダムデータシーケンス３を生成するための生成器１と、排他的ＯＲ論理ゲートとを含む。

各符号化装置３９ａ、３９ｂは、ストリームの暗号化又は復号化を実行し、ビット毎にメッセージを暗号化又は復号化することにある。

この例において、第１符号化装置３９ａは、暗号化動作を実行する。従って、一連の暗号化と呼ばれる疑似ランダムデータシーケンス３は、第１モデム４１ａによって第２エンティティ３３ｂへその後送信される暗号化されたテキスト４７を取得するために、第１端末３７ａによって平文で送信されたメッセージ４５における対応する位置で各ビットに対して排他的ＯＲゲート４３によって結合される。故に、暗号化動作は、暗号化されたテキスト４７を取得するために、ビット毎にメッセージ４５の平文テキストへ一連の暗号化３を追加することにある。

第２符号化装置３９ｂは、平文でテキストメッセージ４５を再公式化するために、第１エンティティ３３ａによって送信された暗号化されたテキスト４７へビット毎に同一の一連の暗号化３を追加することにある復号化動作を実行する。

故に、暗号化及び復号化動作は、同一である。

図３から６は、疑似ランダムデータを生成する本発明による方法を示す。

この方法は、初期データシーケンス９における検索パターンに対する検索をするための手順から疑似ランダムデータシーケンス３を生成することにある。

従って、疑似ランダムデータシーケンスの要素の本発明に従う判断は、検索されたパターン及び検索の履歴、即ち実施された方法に依存することができる。

図３は、本発明に従う疑似ランダムデータシーケンス３を生成するための検索手順の一例を示す。

段階Ｅ１は、一組の検索パターンの１つであるｒビットの特定の検索パターン７の初期データシーケンス９における検出に関する。

段階Ｅ２は、先行の段階Ｅ１の進行に依存する動作によるｋビットの出力パターン２５の判断に関する。

実際、出力パターン２５の判断は、検索パターン７及び検索の履歴に依存することができ、特に初期データシーケンス９において問題のある検索パターン７を発見する前にもたらされた段階又は反復の数に依存することができる。

検索パターン７を検出する段階Ｅ１と出力パターン２５を判断する段階Ｅ２とは、一連の動作によってもたらされる。

この一連の動作は、検索パターン７を検出するために、シフトモードを定義して初期データシーケンス９上でウィンドウ１９をシフトするための生成器１の第１制御手段２１によって実施される第１組の規則を含む。

非ヌルサイズの１つ以上のウィンドウ１９は一般に、初期データシーケンス９上でシフトされる。検索手順の初めにおいて、各ウィンドウ１９は、初期シーケンス９上の初期位置に置かれる（例えば、それらは全て、初期シーケンス９の初めに置かれることができる）。（複数の）ウィンドウ１９における（複数の）ビットは、出力パターン２５を判断するために使用される。

第１組の規則は、シフト方向、シフト振幅又はウィンドウ１９をシフトする形式、例えば一部の初期データシーケンス９上で循環シフトを定義することができる。

例えば、第１組の規則は、以下のように定義された規則ｒ_１を含むことができる。
ｒ_１＝“１ビット右へシフト”

また、一連の動作は、初期データシーケンス９上でウィンドウ１９のシフトを停止するための条件を判断する生成器１の第２制御手段２７によって実施される第２組の規則を含む。

第２組の規則は、生成器１が出力パターン２５を配信する前に、特定の順番で適用されなければならない規則を含むことができる。故に、一連の出力パターン２５の生成器１による配信は、疑似ランダムデータシーケンス３を形成する。

例えば、第２組の規則は、以下のように定義された規則ｒ_２を含むことができる。
ｒ_２＝“ウィンドウ１９のコンテンツが一組の検索パターン７からのパターンではない間、規則ｒ_１に従ってウィンドウ１９をシフト” ここでｒ_１は、第１組の規則からの規則である。

また、この第２組の規則からのもう１つの規則は、所定の２進法に従って、及びウィンドウ１９のシフト及び／又はコンテンツの関数として、１組の検索パターン７及び／又は出力パターン２５の更新を管理する。

従って、検索パターン７は、ウィンドウ１９のコンテンツに依存して、又は第１及び第２組の規則を含む一連の動作の先行する実行に依存して、空、即ちパターンがないことがある。

同様に、出力パターン２５は、ウィンドウ１９のコンテンツに依存して、又は第１及び第２組の規則を含む一連の動作の先行する実行に依存して、空、即ちパターンがないことがある。

また、検索手順の段階Ｅ３は、連続によって一連の出力パターン２５から疑似ランダムデータシーケンス３を形成するために、引続き先行する２つの段階Ｅ１及びＥ２を反復する。

一連の動作は、所定の条件が満たされるまで反復されることができる点に留意すべきである。その条件は、それが有限である場合、初期データシーケンス９のウィンドウ１９のコンテンツにすることができる。また、ユーザによって定義された条件が満たされるまで一連の動作を反復することができる。

また、疑似ランダムデータシーケンス３の質をさらに高めるために、各実行の後に一連の動作を変更することができる。

従って、この方法は、疑似ランダムデータシーケンス３の各出力ビットが初期ストリーム９における一つ以上のパターン７に対する一つ以上の検索に依存するように、一つ以上のウィンドウ１９を用いて初期ビットストリーム（初期データシーケンス９）を走査することにある。また、検索されるべき（複数の）パターン７は、（複数の）ウィンドウ１９のコンテンツ及び／又はシフトに依存することができる。

図４から６は、本発明による方法の特定の実施形態を示す。

これらの例において、一連の動作は、各実行の後に引続き同じ動作のままであり、ウィンドウ１９は、“サイズ１”（即ち、各ウィンドウが１ビットを含む）であり、一組の検索パターン７は、１つの検索パターンを含み、（複数の）検索パターン７及び出力パターン２５も、サイズ１である。

また、ウィンドウ１９のシフトの振幅は、１ユニットに等しく、即ち各ウィンドウ１９は、例えば各反復上で、現在のビットから次のビットへ（即ち、左から右へ）、１ビットだけシフトされる。

従って、各初期データシーケンス９は、連続して、即ちビット毎に読み込まれることができ、とても実行しやすい実施形態をもたらす。

以下、Ｅは、検索パターン７の値を示し、ｓは、出力パターン２５の値を示し、ｆ、ｆ_１及びｆ_２は、ウィンドウ１９の値を示す。

まず、（複数の）検索パターン７及び出力パターン２５は、空のビットをそれらへ、即ちＥ←φ及びｓ←φへ割り当てることによって初期化され、ここでφは、空の組である。同様に、ｂ、ｂ_１及びｂ_２で示された２進数又は定数は、これらの実施形態の一連の動作の各アプリケーション上で同じままである、と定義される。

第１実施形態において、単独のウィンドウ１９は、初期データシーケンス９上でシフトされる。それは、初期データシーケンス９の第１ビット上で初めに固定されることができる。

第１実施形態の一連の動作は、以下のように定義されることができる。
・規則ｒ_１、１＝“１ビット右へシフト”を第１組の規則の唯一の規則として設定
・以下の規則を第２組の規則の規則として設定
・ｒ_２、１＝“検索パターンにウィンドウからのビットｆを置く（Ｅ←ｆ）”
・ｒ_２、２＝“ｒ_１、１に従いウィンドウを１回シフト”
・ｒ_２、３＝“ウィンドウのコンテンツが検索パターンのビットＥに等しい場合、その後出力パターンを更新 ｓ←ｂ”
・ｒ_２、４＝“ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、その後出力パターンを更新

・ｒ_２、５＝“ウィンドウのコンテンツｆが検索パターンではない間、規則ｒ_１、１に従いウィンドウをシフト“
・ｒ_２、６＝“ｒ_１、１に従いウィンドウを１回シフト”
・規則ｒ_２、１、ｒ_２、２、ｒ_２、３、ｒ_２、４、ｒ_２、５及びｒ_２、６をこの順序で適用
・出力パターンｓを出力

実際、図４のフローチャートは、上記一連の動作の実行を示す。

段階Ｅ１１は、検索パターン７にウィンドウ１９からのビットを置く。

段階Ｅ１２は、現在のビットから次のビットへ、１ビッドだけウィンドウ１９をシフトする。

段階Ｅ１３は、ウィンドウ１９のコンテンツを検索パターン７のそれと比較するテストである。

段階Ｅ１４は、ウィンドウ１９のコンテンツが検索パターン７のそれと等しい場合、第１法則に従い出力パターン２５を更新する。この例において、第１法則は、特定値ｂを出力パターン２５へ割り当てることに対応する（ｓ←ｂ）。

段階Ｅ１５は、ウィンドウ１９のコンテンツが検索パターン７のビットＥに等しくない場合、第２法則に従い出力パターン２５を更新する。この例において、第２法則は、特定値ｂ及び値１の２を法とする加算に対応し、この加算の結果を出力パターン２５へ割り当てる。

ウィンドウ１９のコンテンツが検索パターン７のビットＥに等しい場合、段階Ｅ１６及びＥ１７は、次のビットへビット毎にウィンドウ１９をシフトするループを形成する。

段階Ｅ１８は、現在のビットから次のビットへ、１ビットだけウィンドウ１９をシフトする。

最後に、段階Ｅ１９は、生成器１から出力パターンを出力する。

大まかに言って、一連の動作は、以下のように要約できる。初期データシーケンス９における現在のビットＥは、読み込まれ、その後ビットＥが発見されるまでシーケンス９上で右へシフトすることに続く。Ｅを発見するためのシフトが１つの指数だけであった場合、その後ｂが出力され、さもなければ

が出力される。その後、再開の前に右への１ビットのシフトがある。

もちろん、フローチャートは、所定の条件が満たされているか否かを判断するための停止テストを含むことができる（簡略化のために図に表されていない）。

例えば、上記段階は、ウィンドウ１９が初期データシーケンス９から退くまで、疑似ランダムデータシーケンスを形成するために反復されることができる。

図５は、第２実施形態の一連の動作の実行を示すフローチャートである。

この図のフローチャートは、段階Ｅ２４及びＥ２５のみ、図４のそれと異なる。

実際、段階Ｅ２４において、第１法則は、特定値ｂと検索パターン７の値Ｅとの２を法とする加算をもたらすことに対応し、この加算の結果を出力パターン２５に割り当てる。

その一方、段階Ｅ２５において、第２法則は、特定値ｂと、検索パターン７の値Ｅと、値１との２を法とする加算をもたらすことに対応し、この加算の結果を出力パターン２５に割り当てる。

従って、第２実施形態の一連の動作は、以下のように定義されることができる。
・規則ｒ_１、１＝“１ビット右へシフト”を第１組の規則の唯一の規則として設定
・以下の規則を第２組の規則の規則として設定
・ｒ_２、１＝“検索パターンにウィンドウからのビットｆを置く（Ｅ←ｆ）”
・ｒ_２、２＝“ｒ_１、１に従い１回ウィンドウをシフト”
・ｒ_２、３＝“ウィンドウのコンテンツが検索パターンのビットＥに等しい場合、その後出力パターンを更新”

・ｒ_２、４＝“ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、その後出力パターンを更新”

・ｒ_２、５＝“ウィンドウのコンテンツｆが検索パターンではない間、規則ｒ_１、１に従いウィンドウをシフト”
・ｒ_２、６＝“ｒ_１、１に従い１回ウィンドウをシフト”
・規則ｒ_２、１、ｒ_２、２、ｒ_２、３、ｒ_２、４、ｒ_２、５及びｒ_２、６をこの順序で適用
・出力パターンｓを出力

大まかに言って、第２実施形態の一連の動作は、以下のように要約できる。初期データシーケンス９における現在のビットＥは、読み込まれ、その後ビットＥが発見されるまでシーケンス上を右側へシフトすることに続く。Ｅを発見するためのシフトが１つの指数だけであった場合、その後

が出力され、さもなければ

が出力される。その後、再開の前に１ビットの右側へのシフトに続く。

図６は、第３実施形態の一連の動作を示すフローチャートである。

この第３実施形態において、２つのウィンドウ１９は、初期データシーケンス上でシフトされる。初めに、第１ウィンドウは、初期データシーケンス９の第１ビット上で固定され、初めに、第２ウィンドウは、そのシーケンスの第２ビット上で固定される。そのような状況下で、２つの定数が定義され、第１ビットはｂ_１を示し、第２ビットはｂ_２を示す。例えば、定数ｂ_１及びｂ_２は、同一値０を有する。

段階Ｅ３１は、検索パターン７に第１ウィンドウからのビットを置く。

段階Ｅ３２は、現在のビットから次のビットへ、１ビッドだけ第１ウィンドウをシフトする。

段階Ｅ３３は、第１ウィンドウのコンテンツを検索パターン７のそれと比較するテストである。

段階Ｅ３４は、第１ウィンドウのコンテンツが検索パターン７の値Ｅに等しくない場合、第１特定値ｂ_１と検索パターンの値Ｅとの２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。

段階Ｅ３５は、第１ウィンドウのコンテンツが検索パターンの値Ｅに等しくない場合、第１特定値ｂ_１と、検索パターン７の値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。

段階Ｅ３６及びＥ３７は、第１ウィンドウのコンテンツが検索パターン７のビットに等しくない場合、次のビットへビット毎に第１ウィンドウをシフトするループを形成する。

段階Ｅ３８は、現在のビットから次のビットへ、１ビッドだけ第１ウィンドウをシフトする。

段階Ｅ３９は、検索パターン７に第２ウィンドウからのビットを置く。

段階Ｅ４０は、現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする。

段階Ｅ４１は、第２ウィンドウのコンテンツを検索パターン７のそれと比較するテストである。

段階Ｅ４２は、第２ウィンドウのコンテンツが検索パターン７の値に等しい場合、第２特定値ｂ_２と、出力パターン２５の現在の値ｓと、検索パターン７の値Ｅとの２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。

段階Ｅ４３は、第２ウィンドウのコンテンツｆ_２が検索パターン７の値に等しくない場合、出力パターン２５の現在の値ｓと、前記第２特定値ｂ_２と、検索パターン７の値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。

段階Ｅ４４及びＥ４５は、第２ウィンドウのコンテンツが検索パターンのビットに等しくない場合、次のビットへビット毎に第２ウィンドウをシフトするループを形成する。

段階Ｅ４６は、現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする。

最後に、段階Ｅ４７は、生成器１から出力パターン２５を出力する。

従って、第３実施形態の一連の動作は、以下のように定義できる。
・規則ｒ_１、１＝“１ビット右へシフト”を第１組の規則の唯一の規則として設定
・以下の規則を第２組の規則の規則として設定
・ｒ_２、１＝“検索パターンにウィンドウからのビットｆ_１を置く（Ｅ←ｆ_１）”
・ｒ_２、２＝“ｒ_１、１に従い１回第１ウィンドウをシフト”
・ｒ_２、３＝“第１ウィンドウのコンテンツｆ_１が検索パターンのビットＥに等しい場合、その後

を更新“
・ｒ_２、４＝“第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、その後出力パターン

を更新”

・ｒ_２、５＝“第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない間、規則ｒ_１、１に従い第１ウィンドウをシフト”
・ｒ_２、６＝“ｒ_１、１に従い１回第１ウィンドウをシフト”
・ｒ_２、７＝“検索パターンの値を第２ウィンドウからのビットｆ_２に置き換える“
・ｒ_２、８＝“ｒ_１、１に従い１回第２ウィンドウをシフト”
・ｒ_２、９＝“第２ウィンドウのコンテンツｆ_２が検索パターンのビットＥに等しい場合、その後出力パターンを更新”

・ｒ_２、１０＝“第２ウィンドウのコンテンツｆ_２が検索パターンのビットＥに等しくない場合、その後出力パターンを更新”

・ｒ_２、１１＝“第２ウィンドウのコンテンツｆ_２が検索パターンのビットＥに等しくない場合、ｒ_１、１に従い第２ウィンドウをシフト”
・ｒ_２、１２＝“ｒ_１、１に従い１回第２ウィンドウをシフト“
・規則ｒ_２、１をｒ_２、１２へこの順序で適用する。
・出力パターンｓを出力

大まかに言って、第３実施形態は、第１に、第１ウィンドウが初期データシーケンス９の第１ビット上で初めに位置決めされる第２実施形態と、第２に、第２ウィンドウが初期データシーケンス９の第２ビット上で初めに位置決めされる第２実施形態とを並行して実行することによって得られた出力をビット毎に追加することになる。

これらの実施形態は、実行するのが簡単である。また、例えば初期データシーケンス９を提供する初期手段１１が線形フィードバックシフトレジスタである場合、出力ビット数及び演算されたビット数間のそれらの割合は、平均１／３である。

従って、本発明による方法は、対称ストリーム暗号化に用いることができる良好な品質の疑似ランダムビットシーケンスを生成する。

実際、疑似ランダムデータシーケンス３の各ビットは、暗号化されたデータシーケンス４７を形成するために、２を法とする加算によって暗号化されるべきメッセージ４５のデータシーケンスの対応するビットに結合されることができる（図２を参照）。

図１は、本発明による疑似ランダムデータシーケンス生成器の一例の概略図である。 図２は、図１からの生成器をふくむセキュアシステムを示す図である。 図３は、本発明に従う疑似ランダムデータシーケンスを生成するための検索手順の一例を示す図である。 図４は、本発明による方法の特定実施形態を示す図である。 図５は、本発明による方法の特定実施形態を示す図である。 図６は、本発明による方法の特定実施形態を示す図である。 図７は、従来技術の生成器の線図である。

符号の説明

Ｅ１ 検索パターンを検出
Ｅ２ 出力パターンを検出
Ｅ３ 最後の２つの段階を反復

Claims (19)

1. 疑似ランダムデータシーケンス（３）を生成する方法であって、
   前記疑似ランダムデータシーケンス（３）は、Ｎビットの初期データシーケンス（９）における検索パターン（７）に対する検索をするための手順によって生成され、
   前記検索手順は、
   ・一組の検索パターンの１つであるｒビットの特定の検索パターン（７）を前記初期データシーケンス（９）において検出する段階（Ｅ１）と、
   ・先行する段階（Ｅ１）の進行に依存する動作によってｋビットの出力パターン（２５）を判断する段階（Ｅ２）と、
   ・一連の出力パターン（２５）から疑似ランダムデータシーケンス（３）を連続して形成するために先行する段階（Ｅ１、Ｅ２）を反復する段階と
   を具備することを特徴とする方法。
2. 前記検索パターン（７）を検出する段階（Ｅ１）と前記出力パターン（２５）を判断する段階（Ｅ２）とは、前記検索パターン（７）を検出するために前記初期データシーケンス（９）上でウィンドウ（１９）をシフトするためのシフトモードを定義するための第１組の規則を含む一連の動作によってもたらされ、前記ウィンドウ（１９）は、前記初期データシーケンス（９）上で特定の初期位置と特定のビットサイズとを有することを特徴とする請求項１に記載の方法。
3. 一連の動作は、前記初期データシーケンス（９）上で前記ウィンドウ（１９）のシフトを停止するための条件を判断する第２組の規則をさらに含むことを特徴とする請求項２に記載の方法。
4. 前記第２組の規則からの規則は、前記ウィンドウのシフト及び／又はコンテンツの関数として、前記一組の検索パターン及び／又は前記出力パターンの更新を管理することを特徴とする請求項３に記載の方法。
5. 前記一連の動作は、所定の条件が満たされるまで反復されることを特徴とする請求項２及び３の何れか１項に記載の方法。
6. 一連の動作は、各実行の後に変更されることを特徴とする請求項２及び３の何れか１項に記載の方法。
7. 一連の動作は、１ビットの検索パターン（７）を検出するために、及び１ビットの出力パターン（２５）を判断するために、各実行の後に引続き同じ動作のままであり、ビット毎に連続して前記初期データシーケンス（９）上で１ビットのウィンドウ（１９）をシフトすることを特徴とする請求項２及び３の何れか１項に記載の方法。
8. 一連の動作は、
   ・検索パターンにウィンドウからのビットを置く段階と、
   ・現在のビットから次のビットへ、ビット毎にウィンドウをシフトする段階と、
   ・ウィンドウのコンテンツが検索パターンのそれと等しい場合、第１法則に従い出力パターンを更新する段階と、
   ・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、第２法則に従い出力パターンを更新する段階と、
   ・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、次のビットへビット毎にウィンドウをシフトする段階と、
   ・現在のビットから次のビットへ、１ビットだけウィンドウをシフトする段階と、
   ・出力パターンを出力する段階と
   を具備することを特徴とする請求項７に記載の方法。
9. 第１法則は、出力パターンに特定値ｂを割り当て、第２法則は、前記特定値ｂ及び値１の２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てることを特徴とする請求項８に記載の方法。
10. 第１法則は、特定値ｂ及び検索パターンの値Ｅの２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当て、第２法則は、前記特定値ｂと、検索パターンの値Ｅと、値１との２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てることを特徴とする請求項８に記載の方法。
11. 一連の動作は、
    ・検索パターンに第１ウィンドウからのビットを置く段階と、
    ・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
    ・第１ウィンドウのコンテンツが検索パターンの値に等しい場合、第１特定値ｂ_１及び検索パターンの値Ｅの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
    ・第１ウィンドウのコンテンツが検索パターンの値Ｅに等しくない場合、前記第１特定値ｂ_１と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
    ・第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、次のビットへビット毎に第１ウィンドウをシフトする段階と、
    ・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
    ・第２ウィンドウからのビットによって検索パターンの値を置き換える段階と、
    ・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
    ・第２ウィンドウのコンテンツが検索パターンの値に等しい場合、第２特定値ｂ_２と、出力パターンの現在の値ｓと、検索パターンの値Ｅとの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
    ・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、出力パターンの現在の値ｓと、前記第２特定値ｂ_２と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
    ・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、次のビットへビット毎に第２ウィンドウをシフトする段階と、
    ・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
    ・出力パターンを出力する段階と
    を具備することを特徴とする請求項７に記載の方法。
12. 前記疑似ランダムデータシーケンスの各ビットは、暗号化されたデータシーケンスを形成するために、２を法とする加算によって暗号化されるべきメッセージのデータシーケンスの対応するビットに結合されることを特徴とする請求項１から１１の何れか１項に記載の方法。
13. 疑似ランダムデータシーケンス（３）の生成器であって、Ｎビットの初期データシーケンス（９）における検索パターン（７）に対する検索のための検索手段（５）を含み、
    前記検索手段（５）は、
    ・一組の検索パターンの１つであるｒビットの特定の検索パターンを前記初期データシーケンス（９）において検出するための検出手段（１３）と、
    ・前記少なくとも１つの検索パターン（７）の検出の進行に依存する動作に従いｋビットの出力パターン（２５）を判断するための判断手段（１５）と、
    ・一連の出力パターン（２５）から疑似ランダムデータシーケンス（３）を生成するための反復手段（１７）と
    を具備することを特徴とする生成器。
14. 検出手段（１３）は、前記初期データシーケンス（９）上でシフトされるよう適合されたウィンドウ（１９）と、前記初期データシーケンス（９）上で前記ウィンドウのシフトを制御するための第１制御手段（２１）とを含むことを特徴とする請求項１３に記載の生成器。
15. 判断手段（１５）は、前記一組の検索パターン及び／又は前記出力パターンを更新するための第２制御手段（２７）を含むことを特徴とする請求項１３に記載の生成器。
16. Ｎビットの初期データシーケンスを生成するための初期手段（１１）をさらに含むことを特徴とする請求項１３から１５の何れか１項に記載の生成器。
17. 初期手段（１１）は、線形フィードバックシフトレジスタを含むことを特徴とする請求項１６に記載の生成器。
18. 請求項１３から１７の何れか１項に記載の生成器（１）をさらに含むことを特徴とする、排他的ＯＲ論理ゲート（４３）を含む符号化装置（３９）。
19. 少なくとも２つのエンティティ（３３ａ、３３ｂ）の各々は、請求項１８に記載の符号化装置（３９ａ、３９ｂ）を含むことを特徴とする、前記少なくとも２つのエンティティ（３３ａ、３３ｂ）を含むセキュアシステム。

Images