疑似ランダムデータシーケンスの生成
疑似ランダムデータシーケンス（３）を生成する方法であって、前記疑似ランダムデータシーケンス（３）は、Ｎビットの初期データシーケンス（９）における検索パターン（７）に対する検索をするための手順によって生成されることを特徴とし、前記検索手順は、一組の検索パターンの１つであるｒビットの特定の検索パターン（７）を前記初期データシーケンス（９）において検出する段階（Ｅ１）と、先行する段階（Ｅ１）の進行に依存する動作によってｋビットの出力パターン（２５）を判断する段階（Ｅ２）と、一連の出力パターン（２５）から疑似ランダムデータシーケンス（３）を連続して形成するために先行する段階（Ｅ１、Ｅ２）を反復する段階とを具備する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化／復号化の分野に関し、疑似ランダムデータシーケンスを生成するシステム及び方法に関する。
【０００２】
本発明は、暗号化及び復号化が同一の秘密鍵を使用する対称暗号化を対象とするビットのシーケンスを生成することに供する点で、とても有利な用途を見出す。本発明は、暗号化動作及び復号化動作が同一である標準のストリーム暗号化方法に順応する。対称暗号化は通常、移動体通信（ＧＳＭ、ＵＭＴＳ等）、インターネット（ＳＳＬ等）、スマートカード（バンクカード）等のような、全種類の通信に使用される。
【背景技術】
【０００３】
最も広く普及したストリーム暗号化方法は、ハードウェアを節約するために、線形フィードバックシフトレジスタを用いて暗号化されるべきメッセージに対して独立した一連の暗号化を生成する。
【０００４】
線形フィードバックシフトレジスタの主な欠点は、その線形性である。実際、レジスタ長に等しいレジスタの多数の出力ビットを知ること、及びレジスタに関連付けられたフィードバック多項式を知ることは、レジスタの出力ビットと全ての後続の状態とを判断することを可能にする。
【０００５】
従って、線形フィードバックシフトレジスタの線形性を“破る”ためには、例えば非線形ブール関数を用いて、複数のレジスタの出力を結合すること、及び場合によりその内部状態を結合することも標準的な習慣である。
【０００６】
図７は、第１線形フィードバックシフトレジスタ１１１ａと、第２線形フィードバックシフトレジスタ１１１ｂと、生成器１００の出力を選択するための手段１１２とを含む、欧州特許出願ＥＰ０６１９６５９で説明された“疑似ランダム数生成器（shrinking generator）”として知られる当該生成器１００を示す。
【０００７】
従って、各シフト上で、２つのレジスタ１１１ａ及び１１１ｂは、同時にシフトされる。第１レジスタ１１１ａの出力が１の場合、装置１００の出力は、第２レジスタ１１１ｂの出力に等しく、そうでない場合、出力されない。
【０００８】
疑似ランダム数生成器は、２つの線形フィードバックレジスタの出力だけでなく、より一般には任意の組の一連のビットを結合する。疑似ランダム数生成器は、１つの線形フィードバックレジスタが他の線形フィードバックレジスタを制御するストリーム暗号化方法の部類である。その目的は、レジスタの線形性を破るために、まず、採用された各種レジスタ間のシフト数、次に、２つの連続ビット間のシフト数を変更することにある。
【０００９】
“自動疑似ランダム数生成器”として知られる疑似ランダム数生成器の変形は、同一の原理に基づくが、単独のレジスタを使用する。レジスタの出力ビットは、２つずつ読み込まれる。第１ビットが１である場合にシステムの出力が第２ビットになり、そうでない場合に出力されないように、第１ビットは、第２ビットの出力を制御する。
【００１０】
線形フィードバックレジスタのみを使用することは、多数の欠点を有する。主な欠点は、装置の線形性から生じる脆弱性である。レジスタがブール関数を用いて結合される場合も不利である。ハードウェアレベルでは、これらの不利な点は、関数を実行する複雑性から生じる。また、この関数は、固定され、それを攻撃することを可能にする。
【００１１】
また、統計的方法は、疑似ランダム数生成器と他のクロック制御暗号化方法との所定の脆弱性を明らかにした。特に、疑似ランダム数生成器において、２つの出力ビット間で２つのレジスタによってもたらされるシフト数は、両レジスタに対して同じ量だけ変わる。
【００１２】
最後に、疑似ランダム数生成器の最後の欠点は、演算されるビット数に対する出力ビット数のその低い割合であり、平均して１／４に等しい。この割合は、自動疑似ランダム数生成器と同じであり、疑似ランダム数生成器の脆弱性の大部分を有する。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明の目的は、上記欠点を改善し、良好な品質の疑似ランダムデータシーケンスの生成を単純化することにある。
【００１４】
もう１つの目的は、出力ビット数と演算されたビット数との間の割合を１／４よりも高くする方法及び生成器を提案することにある。
【００１５】
さらにもう１つの目的は、低コストでかなり効率的な生成器を提供することにある。
【課題を解決するための手段】
【００１６】
上記目的は、疑似ランダムデータシーケンスを生成する方法を用いて達成され、前記疑似ランダムデータシーケンスは、Ｎビットの初期データシーケンスにおける検索パターンに対する検索の手順によって生成される。
【００１７】
故に、本発明による方法は、一つ以上のビットストリームの非線形結合により新たなビットストリームを得ることを可能にするパターンの検出に基づき疑似ランダムデータを生成する非線形方法に関する。
【００１８】
この方法は、容易に実施されるが、良好な品質の疑似ランダムデータシーケンスを生成するために、本質的な複雑性を有する。
【００１９】
検索手順は、
・一組の検索パターンの１つであるｒビットの特定の検索パターンを前記初期データシーケンスにおいて検出する段階と、
・先行する段階の進行に依存する動作によってｋビットの出力パターンを判断する段階と、
・一連の出力パターンから疑似ランダムデータシーケンスを連続して形成するために先行する段階を反復する段階とを具備する。
【００２０】
前記検索パターンを検出する段階と前記出力パターンを判断する段階とは、前記検索パターンを検出するために前記初期データシーケンス上でウィンドウをシフトするためのシフトモードを定義するための第１組の規則を含む一連の動作によってもたらされ、前記ウィンドウは、前記初期データシーケンス上で特定の初期位置と特定のビットサイズとを有する。
【００２１】
一連の動作は、前記初期データシーケンス上で前記ウィンドウのシフトを停止するための条件を判断する第２組の規則をさらに含む。
【００２２】
前記第２組の規則からの規則は、前記ウィンドウのシフト及び／又はコンテンツの関数として、前記１組の検索パターン及び／又は前記出力パターンの更新を管理する。
【００２３】
前記一連の動作は、所定の条件が満たされるまで反復される。
【００２４】
一連の動作は、各実行の後に有利に変更される。
【００２５】
本発明の特徴によると、一連の動作は、１ビットの検索パターンを検出するために、及び１ビットの出力パターンを判断するために、各実行の後に引続き同じ動作のままであり、ビット毎に連続して前記初期データシーケンス上で１ビットのウィンドウをシフトする。
【００２６】
本発明の第１実施形態において、一連の動作は、
・検索パターンにウィンドウからのビットを置く段階と、
・現在のビットから次のビットへ、ビット毎にウィンドウをシフトする段階と、
・ウィンドウのコンテンツが検索パターンのそれと等しい場合、第１法則に従い出力パターンを更新する段階と、
・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、第２法則に従い出力パターンを更新する段階と、
・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、次のビットへビット毎にウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけウィンドウをシフトする段階と、
・出力パターンを出力する段階とを含む。
【００２７】
第１実施形態において、第１法則は、出力パターンに特定値ｂを割り当て、第２法則は、前記特定値ｂ及び値１の２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てる。
【００２８】
第２実施形態において、第１法則は、特定値ｂ及び検索パターンの値Ｅの２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当て、第２法則は、前記特定値ｂと、検索パターンの値Ｅと、値１との２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てる。
【００２９】
第３実施形態において、一連の動作は、
・検索パターンに第１ウィンドウからのビットを置く段階と、
・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
・第１ウィンドウのコンテンツが検索パターンの値に等しい場合、第１特定値ｂ１及び検索パターンの値Ｅの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第１ウィンドウのコンテンツが検索パターンの値Ｅに等しくない場合、前記第１特定値ｂ１と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、次のビットへビット毎に第１ウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
・第２ウィンドウからのビットによって検索パターンの値を置き換える段階と、
・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しい場合、第２特定値ｂ２と、出力パターンの現在の値ｓと、検索パターンの値Ｅとの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、出力パターンの現在の値ｓと、前記第２特定値ｂ２と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、次のビットへビット毎に第２ウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
・出力パターンを出力する段階とを含む。
【００３０】
本発明の用途において、前記疑似ランダムデータシーケンスの各ビットは、暗号化されたデータシーケンスを形成するために、２を法とする加算によって暗号化されるべきメッセージのデータシーケンスの対応するビットに結合される。
【００３１】
また、本発明は、Ｎビットの初期データシーケンスにおける検索パターンに対する検索のための検索手段を含む疑似ランダムデータシーケンスの生成器を提供する。
【００３２】
生成器の検索手段は、
・一組の検索パターンの１つであるｒビットの特定の検索パターンを前記初期データシーケンスにおいて検出するための検出手段と、
・前記検索パターンの検出の進行に依存する動作に従いｋビットの出力パターンを判断するための判断手段と、
・一連の出力パターンから疑似ランダムデータシーケンスを生成するための反復手段とを含む。
【００３３】
検出手段は、前記初期データシーケンス上でシフトされるよう適合されたウィンドウと、前記初期データシーケンス上で前記ウィンドウのシフトを制御するための第１制御手段とを含む。
【００３４】
判断手段は、前記一組の検索パターン及び／又は前記出力パターンを更新するための第２制御手段を含む。
【００３５】
生成器は、Ｎビットの初期データシーケンスを生成するための初期手段（１１）をさらに含む。
【００３６】
初期手段は、線形フィードバックシフトレジスタを含む。
【００３７】
また、本発明は、上記特徴を有する生成器と、排他的ＯＲ論理ゲートを含む符号化装置とを目的とする。
【００３８】
また、本発明は、各々が符号化装置を含む少なくとも２つのエンティティを含むセキュアシステムを目的とする。
【発明を実施するための最良の形態】
【００３９】
図１は、疑似ランダムデータシーケンス３を生成するための本発明による生成器１の一例を概略的に示す。
【００４０】
生成器１は、Ｎビットの初期データシーケンス９における検索パターン７に対して検索するための検索手段５を含む。検索パターンは、一組の検索パターンに含まれる。
【００４１】
“パターン”という用語は、０及び１以外からなる任意の単語を指すために以下で使用される。例えば、０、１１、０００、１０１０、００１１１は、１、２、３、４及び５の長さをそれぞれ備えたパターンである。また、“空”パターンは、空単語である。
【００４２】
Ｎビット（Ｎが整数）の初期データシーケンスは、最大周期の線形フィードバックシフトレジスタを含むことができる初期手段１１によって生成される。
【００４３】
線形フィードバックシフトレジスタは、フィードバック多項式と呼ばれる多項式によって表される、テーブル入力の線形結合が提供された有限長（レジスタ）のビットのテーブルである。各シフト上で、最高指数を備えたビットが出力され、全ての他のビットが１指数だけシフトされ、最低指数を備えたビットがシフトの前に線形結合の値を取る。
【００４４】
フィードバック多項式は、最大周期の線形シフトレジスタに対応する原始多項式、例えばＰが原始多項式である、Ｑ＝（ｘ２＋１）Ｐの式の多項式にすることができる利点がある。
【００４５】
生成器１の検索手段５は、検出手段１３と、判断手段１５と、反復手段１７とを含む。
【００４６】
検出手段１３は、ｒがＮ未満の整数である、初期データシーケンスにおけるｒビットの検索パターン７を検出する。判断手段１５は、検出手段１３によって検出される検索パターン７が属する一組の検索パターンを定義する。
【００４７】
検出手段は、初期データシーケンス９上でシフトされるように適合されたウィンドウ１９と、初期データシーケンス９上でウィンドウ１９のシフトを制御するための第１制御手段２１とを含む。
【００４８】
各ウィンドウ１９は、初期データシーケンス９における特定の初期位置に置かれ、特定のビットサイズを有する。例えば、初期データシーケンス９上に置かれたサイズｔ（ｔは、Ｎ未満の整数である）のウィンドウ１９は、シーケンス９のまさにｔビットを各シフト上に曝すためにシーケンス９上でシフトされることができるマスクである。
【００４９】
判断手段１５は、接続２３を介して検出手段１３と交信する。判断手段１５は、検索パターン７に対する検索の進行に依存する動作によってｋビット（ｋは、Ｎ未満の整数である）の出力パターン２５を判断する。
【００５０】
実際、判断手段１５は、一組の検索パターン及び／又は出力パターン２５を定義又は更新するための第２制御手段２７を含む。
【００５１】
また、反復手段１７は、それぞれ接続２９及び３１を介して検出手段１３及び判断手段１５に接続される。
【００５２】
従って、所定の停止条件が満たされない場合、例えば出力パターン２５が丁度出力された旨の信号を判断手段１５から受信した場合、反復手段１７は、検出及び判断動作を再開するために検出手段１３及び判断手段１５に対して信号を交わすことができる。また、反復手段１７は、検出手段１３及び判断手段１５に対して信号を交わすことによって停止条件をテストすることができる。これは、一連の出力パターン２５を生成し、連続形式による疑似ランダムデータシーケンス３になる。
【００５３】
また、反復手段１７は、検出手段１３及び判断手段１５の第１又は第２制御手段２１又は２７に統合されうる点に留意すべきである。
【００５４】
図２は、インターネット、ＧＳＭ、ＵＭＴＳ等の種類の通信ネットワーク３５を介して相互接続された少なくとも２つのエンティティを含むセキュアシステム３１を示す。
【００５５】
この図の例は、第２エンティティ３３ｂへ通信ネットワーク３５を介して接続された第１エンティティ３３ａを示す。第１エンティティ３３ａ（それぞれ第２エンティティ３３ｂ）は、第１端末３７ａ（それぞれ第２端末３７ｂ）と、第１符号化装置３９ａ（それぞれ第２符号化装置３９ｂ）と、第１モデム４１ａ（それぞれ第２モデム４１ｂ）とを含み、モデム４１ａ及び４１ｂは、通信ネットワーク３５に対してインタフェースするための任意の装置からなる。
【００５６】
各第１及び第２符号化装置３９ａ、３９ｂは、上述のような疑似ランダムデータシーケンス３を生成するための生成器１と、排他的ＯＲ論理ゲートとを含む。
【００５７】
各符号化装置３９ａ、３９ｂは、ストリームの暗号化又は復号化を実行し、ビット毎にメッセージを暗号化又は復号化することにある。
【００５８】
この例において、第１符号化装置３９ａは、暗号化動作を実行する。従って、一連の暗号化と呼ばれる疑似ランダムデータシーケンス３は、第１モデム４１ａによって第２エンティティ３３ｂへその後送信される暗号化されたテキスト４７を取得するために、第１端末３７ａによって平文で送信されたメッセージ４５における対応する位置で各ビットに対して排他的ＯＲゲート４３によって結合される。故に、暗号化動作は、暗号化されたテキスト４７を取得するために、ビット毎にメッセージ４５の平文テキストへ一連の暗号化３を追加することにある。
【００５９】
第２符号化装置３９ｂは、平文でテキストメッセージ４５を再公式化するために、第１エンティティ３３ａによって送信された暗号化されたテキスト４７へビット毎に同一の一連の暗号化３を追加することにある復号化動作を実行する。
【００６０】
故に、暗号化及び復号化動作は、同一である。
【００６１】
図３から６は、疑似ランダムデータを生成する本発明による方法を示す。
【００６２】
この方法は、初期データシーケンス９における検索パターンに対する検索をするための手順から疑似ランダムデータシーケンス３を生成することにある。
【００６３】
従って、疑似ランダムデータシーケンスの要素の本発明に従う判断は、検索されたパターン及び検索の履歴、即ち実施された方法に依存することができる。
【００６４】
図３は、本発明に従う疑似ランダムデータシーケンス３を生成するための検索手順の一例を示す。
【００６５】
段階Ｅ１は、一組の検索パターンの１つであるｒビットの特定の検索パターン７の初期データシーケンス９における検出に関する。
【００６６】
段階Ｅ２は、先行の段階Ｅ１の進行に依存する動作によるｋビットの出力パターン２５の判断に関する。
【００６７】
実際、出力パターン２５の判断は、検索パターン７及び検索の履歴に依存することができ、特に初期データシーケンス９において問題のある検索パターン７を発見する前にもたらされた段階又は反復の数に依存することができる。
【００６８】
検索パターン７を検出する段階Ｅ１と出力パターン２５を判断する段階Ｅ２とは、一連の動作によってもたらされる。
【００６９】
この一連の動作は、検索パターン７を検出するために、シフトモードを定義して初期データシーケンス９上でウィンドウ１９をシフトするための生成器１の第１制御手段２１によって実施される第１組の規則を含む。
【００７０】
非ヌルサイズの１つ以上のウィンドウ１９は一般に、初期データシーケンス９上でシフトされる。検索手順の初めにおいて、各ウィンドウ１９は、初期シーケンス９上の初期位置に置かれる（例えば、それらは全て、初期シーケンス９の初めに置かれることができる）。（複数の）ウィンドウ１９における（複数の）ビットは、出力パターン２５を判断するために使用される。
【００７１】
第１組の規則は、シフト方向、シフト振幅又はウィンドウ１９をシフトする形式、例えば一部の初期データシーケンス９上で循環シフトを定義することができる。
【００７２】
例えば、第１組の規則は、以下のように定義された規則ｒ１を含むことができる。
ｒ１＝“１ビット右へシフト”
【００７３】
また、一連の動作は、初期データシーケンス９上でウィンドウ１９のシフトを停止するための条件を判断する生成器１の第２制御手段２７によって実施される第２組の規則を含む。
【００７４】
第２組の規則は、生成器１が出力パターン２５を配信する前に、特定の順番で適用されなければならない規則を含むことができる。故に、一連の出力パターン２５の生成器１による配信は、疑似ランダムデータシーケンス３を形成する。
【００７５】
例えば、第２組の規則は、以下のように定義された規則ｒ２を含むことができる。
ｒ２＝“ウィンドウ１９のコンテンツが一組の検索パターン７からのパターンではない間、規則ｒ１に従ってウィンドウ１９をシフト” ここでｒ１は、第１組の規則からの規則である。
【００７６】
また、この第２組の規則からのもう１つの規則は、所定の２進法に従って、及びウィンドウ１９のシフト及び／又はコンテンツの関数として、１組の検索パターン７及び／又は出力パターン２５の更新を管理する。
【００７７】
従って、検索パターン７は、ウィンドウ１９のコンテンツに依存して、又は第１及び第２組の規則を含む一連の動作の先行する実行に依存して、空、即ちパターンがないことがある。
【００７８】
同様に、出力パターン２５は、ウィンドウ１９のコンテンツに依存して、又は第１及び第２組の規則を含む一連の動作の先行する実行に依存して、空、即ちパターンがないことがある。
【００７９】
また、検索手順の段階Ｅ３は、連続によって一連の出力パターン２５から疑似ランダムデータシーケンス３を形成するために、引続き先行する２つの段階Ｅ１及びＥ２を反復する。
【００８０】
一連の動作は、所定の条件が満たされるまで反復されることができる点に留意すべきである。その条件は、それが有限である場合、初期データシーケンス９のウィンドウ１９のコンテンツにすることができる。また、ユーザによって定義された条件が満たされるまで一連の動作を反復することができる。
【００８１】
また、疑似ランダムデータシーケンス３の質をさらに高めるために、各実行の後に一連の動作を変更することができる。
【００８２】
従って、この方法は、疑似ランダムデータシーケンス３の各出力ビットが初期ストリーム９における一つ以上のパターン７に対する一つ以上の検索に依存するように、一つ以上のウィンドウ１９を用いて初期ビットストリーム（初期データシーケンス９）を走査することにある。また、検索されるべき（複数の）パターン７は、（複数の）ウィンドウ１９のコンテンツ及び／又はシフトに依存することができる。
【００８３】
図４から６は、本発明による方法の特定の実施形態を示す。
【００８４】
これらの例において、一連の動作は、各実行の後に引続き同じ動作のままであり、ウィンドウ１９は、“サイズ１”（即ち、各ウィンドウが１ビットを含む）であり、一組の検索パターン７は、１つの検索パターンを含み、（複数の）検索パターン７及び出力パターン２５も、サイズ１である。
【００８５】
また、ウィンドウ１９のシフトの振幅は、１ユニットに等しく、即ち各ウィンドウ１９は、例えば各反復上で、現在のビットから次のビットへ（即ち、左から右へ）、１ビットだけシフトされる。
【００８６】
従って、各初期データシーケンス９は、連続して、即ちビット毎に読み込まれることができ、とても実行しやすい実施形態をもたらす。
【００８７】
以下、Ｅは、検索パターン７の値を示し、ｓは、出力パターン２５の値を示し、ｆ、ｆ１及びｆ２は、ウィンドウ１９の値を示す。
【００８８】
まず、（複数の）検索パターン７及び出力パターン２５は、空のビットをそれらへ、即ちＥ←φ及びｓ←φへ割り当てることによって初期化され、ここでφは、空の組である。同様に、ｂ、ｂ１及びｂ２で示された２進数又は定数は、これらの実施形態の一連の動作の各アプリケーション上で同じままである、と定義される。
【００８９】
第１実施形態において、単独のウィンドウ１９は、初期データシーケンス９上でシフトされる。それは、初期データシーケンス９の第１ビット上で初めに固定されることができる。
【００９０】
第１実施形態の一連の動作は、以下のように定義されることができる。
・規則ｒ１、１＝“１ビット右へシフト”を第１組の規則の唯一の規則として設定
・以下の規則を第２組の規則の規則として設定
・ｒ２、１＝“検索パターンにウィンドウからのビットｆを置く（Ｅ←ｆ）”
・ｒ２、２＝“ｒ１、１に従いウィンドウを１回シフト”
・ｒ２、３＝“ウィンドウのコンテンツが検索パターンのビットＥに等しい場合、その後出力パターンを更新 ｓ←ｂ”
・ｒ２、４＝“ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、その後出力パターンを更新
【００９１】
【数１】
【００９２】
・ｒ２、５＝“ウィンドウのコンテンツｆが検索パターンではない間、規則ｒ１、１に従いウィンドウをシフト“
・ｒ２、６＝“ｒ１、１に従いウィンドウを１回シフト”
・規則ｒ２、１、ｒ２、２、ｒ２、３、ｒ２、４、ｒ２、５及びｒ２、６をこの順序で適用
・出力パターンｓを出力
【００９３】
実際、図４のフローチャートは、上記一連の動作の実行を示す。
【００９４】
段階Ｅ１１は、検索パターン７にウィンドウ１９からのビットを置く。
【００９５】
段階Ｅ１２は、現在のビットから次のビットへ、１ビッドだけウィンドウ１９をシフトする。
【００９６】
段階Ｅ１３は、ウィンドウ１９のコンテンツを検索パターン７のそれと比較するテストである。
【００９７】
段階Ｅ１４は、ウィンドウ１９のコンテンツが検索パターン７のそれと等しい場合、第１法則に従い出力パターン２５を更新する。この例において、第１法則は、特定値ｂを出力パターン２５へ割り当てることに対応する（ｓ←ｂ）。
【００９８】
段階Ｅ１５は、ウィンドウ１９のコンテンツが検索パターン７のビットＥに等しくない場合、第２法則に従い出力パターン２５を更新する。この例において、第２法則は、特定値ｂ及び値１の２を法とする加算に対応し、この加算の結果を出力パターン２５へ割り当てる。
【００９９】
【数２】
【０１００】
ウィンドウ１９のコンテンツが検索パターン７のビットＥに等しい場合、段階Ｅ１６及びＥ１７は、次のビットへビット毎にウィンドウ１９をシフトするループを形成する。
【０１０１】
段階Ｅ１８は、現在のビットから次のビットへ、１ビットだけウィンドウ１９をシフトする。
【０１０２】
最後に、段階Ｅ１９は、生成器１から出力パターンを出力する。
【０１０３】
大まかに言って、一連の動作は、以下のように要約できる。初期データシーケンス９における現在のビットＥは、読み込まれ、その後ビットＥが発見されるまでシーケンス９上で右へシフトすることに続く。Ｅを発見するためのシフトが１つの指数だけであった場合、その後ｂが出力され、さもなければ
【０１０４】
【数３】
【０１０５】
が出力される。その後、再開の前に右への１ビットのシフトがある。
【０１０６】
もちろん、フローチャートは、所定の条件が満たされているか否かを判断するための停止テストを含むことができる（簡略化のために図に表されていない）。
【０１０７】
例えば、上記段階は、ウィンドウ１９が初期データシーケンス９から退くまで、疑似ランダムデータシーケンスを形成するために反復されることができる。
【０１０８】
図５は、第２実施形態の一連の動作の実行を示すフローチャートである。
【０１０９】
この図のフローチャートは、段階Ｅ２４及びＥ２５のみ、図４のそれと異なる。
【０１１０】
実際、段階Ｅ２４において、第１法則は、特定値ｂと検索パターン７の値Ｅとの２を法とする加算をもたらすことに対応し、この加算の結果を出力パターン２５に割り当てる。
【０１１１】
【数４】
【０１１２】
その一方、段階Ｅ２５において、第２法則は、特定値ｂと、検索パターン７の値Ｅと、値１との２を法とする加算をもたらすことに対応し、この加算の結果を出力パターン２５に割り当てる。
【０１１３】
【数５】
【０１１４】
従って、第２実施形態の一連の動作は、以下のように定義されることができる。
・規則ｒ１、１＝“１ビット右へシフト”を第１組の規則の唯一の規則として設定
・以下の規則を第２組の規則の規則として設定
・ｒ２、１＝“検索パターンにウィンドウからのビットｆを置く（Ｅ←ｆ）”
・ｒ２、２＝“ｒ１、１に従い１回ウィンドウをシフト”
・ｒ２、３＝“ウィンドウのコンテンツが検索パターンのビットＥに等しい場合、その後出力パターンを更新”
【０１１５】
【数６】
【０１１６】
・ｒ２、４＝“ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、その後出力パターンを更新”
【０１１７】
【数７】
【０１１８】
・ｒ２、５＝“ウィンドウのコンテンツｆが検索パターンではない間、規則ｒ１、１に従いウィンドウをシフト”
・ｒ２、６＝“ｒ１、１に従い１回ウィンドウをシフト”
・規則ｒ２、１、ｒ２、２、ｒ２、３、ｒ２、４、ｒ２、５及びｒ２、６をこの順序で適用
・出力パターンｓを出力
【０１１９】
大まかに言って、第２実施形態の一連の動作は、以下のように要約できる。初期データシーケンス９における現在のビットＥは、読み込まれ、その後ビットＥが発見されるまでシーケンス上を右側へシフトすることに続く。Ｅを発見するためのシフトが１つの指数だけであった場合、その後
【０１２０】
【数８】
【０１２１】
が出力され、さもなければ
【０１２２】
【数９】
【０１２３】
が出力される。その後、再開の前に１ビットの右側へのシフトに続く。
【０１２４】
図６は、第３実施形態の一連の動作を示すフローチャートである。
【０１２５】
この第３実施形態において、２つのウィンドウ１９は、初期データシーケンス上でシフトされる。初めに、第１ウィンドウは、初期データシーケンス９の第１ビット上で固定され、初めに、第２ウィンドウは、そのシーケンスの第２ビット上で固定される。そのような状況下で、２つの定数が定義され、第１ビットはｂ１を示し、第２ビットはｂ２を示す。例えば、定数ｂ１及びｂ２は、同一値０を有する。
【０１２６】
段階Ｅ３１は、検索パターン７に第１ウィンドウからのビットを置く。
【０１２７】
段階Ｅ３２は、現在のビットから次のビットへ、１ビッドだけ第１ウィンドウをシフトする。
【０１２８】
段階Ｅ３３は、第１ウィンドウのコンテンツを検索パターン７のそれと比較するテストである。
【０１２９】
段階Ｅ３４は、第１ウィンドウのコンテンツが検索パターン７の値Ｅに等しくない場合、第１特定値ｂ１と検索パターンの値Ｅとの２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。
【０１３０】
【数１０】
【０１３１】
段階Ｅ３５は、第１ウィンドウのコンテンツが検索パターンの値Ｅに等しくない場合、第１特定値ｂ１と、検索パターン７の値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。
【０１３２】
【数１１】
【０１３３】
段階Ｅ３６及びＥ３７は、第１ウィンドウのコンテンツが検索パターン７のビットに等しくない場合、次のビットへビット毎に第１ウィンドウをシフトするループを形成する。
【０１３４】
段階Ｅ３８は、現在のビットから次のビットへ、１ビッドだけ第１ウィンドウをシフトする。
【０１３５】
段階Ｅ３９は、検索パターン７に第２ウィンドウからのビットを置く。
【０１３６】
段階Ｅ４０は、現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする。
【０１３７】
段階Ｅ４１は、第２ウィンドウのコンテンツを検索パターン７のそれと比較するテストである。
【０１３８】
段階Ｅ４２は、第２ウィンドウのコンテンツが検索パターン７の値に等しい場合、第２特定値ｂ２と、出力パターン２５の現在の値ｓと、検索パターン７の値Ｅとの２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。
【０１３９】
【数１２】
【０１４０】
段階Ｅ４３は、第２ウィンドウのコンテンツｆ２が検索パターン７の値に等しくない場合、出力パターン２５の現在の値ｓと、前記第２特定値ｂ２と、検索パターン７の値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。
【０１４１】
【数１３】
【０１４２】
段階Ｅ４４及びＥ４５は、第２ウィンドウのコンテンツが検索パターンのビットに等しくない場合、次のビットへビット毎に第２ウィンドウをシフトするループを形成する。
【０１４３】
段階Ｅ４６は、現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする。
【０１４４】
最後に、段階Ｅ４７は、生成器１から出力パターン２５を出力する。
【０１４５】
従って、第３実施形態の一連の動作は、以下のように定義できる。
・規則ｒ１、１＝“１ビット右へシフト”を第１組の規則の唯一の規則として設定
・以下の規則を第２組の規則の規則として設定
・ｒ２、１＝“検索パターンにウィンドウからのビットｆ１を置く（Ｅ←ｆ１）”
・ｒ２、２＝“ｒ１、１に従い１回第１ウィンドウをシフト”
・ｒ２、３＝“第１ウィンドウのコンテンツｆ１が検索パターンのビットＥに等しい場合、その後
【０１４６】
【数１４】
【０１４７】
を更新“
・ｒ２、４＝“第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、その後出力パターン
【０１４８】
【数１５】
【０１４９】
を更新”
【０１５０】
・ｒ２、５＝“第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない間、規則ｒ１、１に従い第１ウィンドウをシフト”
・ｒ２、６＝“ｒ１、１に従い１回第１ウィンドウをシフト”
・ｒ２、７＝“検索パターンの値を第２ウィンドウからのビットｆ２に置き換える“
・ｒ２、８＝“ｒ１、１に従い１回第２ウィンドウをシフト”
・ｒ２、９＝“第２ウィンドウのコンテンツｆ２が検索パターンのビットＥに等しい場合、その後出力パターンを更新”
【０１５１】
【数１６】
【０１５２】
・ｒ２、１０＝“第２ウィンドウのコンテンツｆ２が検索パターンのビットＥに等しくない場合、その後出力パターンを更新”
【０１５３】
【数１７】
【０１５４】
・ｒ２、１１＝“第２ウィンドウのコンテンツｆ２が検索パターンのビットＥに等しくない場合、ｒ１、１に従い第２ウィンドウをシフト”
・ｒ２、１２＝“ｒ１、１に従い１回第２ウィンドウをシフト“
・規則ｒ２、１をｒ２、１２へこの順序で適用する。
・出力パターンｓを出力
【０１５５】
大まかに言って、第３実施形態は、第１に、第１ウィンドウが初期データシーケンス９の第１ビット上で初めに位置決めされる第２実施形態と、第２に、第２ウィンドウが初期データシーケンス９の第２ビット上で初めに位置決めされる第２実施形態とを並行して実行することによって得られた出力をビット毎に追加することになる。
【０１５６】
これらの実施形態は、実行するのが簡単である。また、例えば初期データシーケンス９を提供する初期手段１１が線形フィードバックシフトレジスタである場合、出力ビット数及び演算されたビット数間のそれらの割合は、平均１／３である。
【０１５７】
従って、本発明による方法は、対称ストリーム暗号化に用いることができる良好な品質の疑似ランダムビットシーケンスを生成する。
【０１５８】
実際、疑似ランダムデータシーケンス３の各ビットは、暗号化されたデータシーケンス４７を形成するために、２を法とする加算によって暗号化されるべきメッセージ４５のデータシーケンスの対応するビットに結合されることができる（図２を参照）。
【図面の簡単な説明】
【０１５９】
【図１】図１は、本発明による疑似ランダムデータシーケンス生成器の一例の概略図である。
【図２】図２は、図１からの生成器をふくむセキュアシステムを示す図である。
【図３】図３は、本発明に従う疑似ランダムデータシーケンスを生成するための検索手順の一例を示す図である。
【図４】図４は、本発明による方法の特定実施形態を示す図である。
【図５】図５は、本発明による方法の特定実施形態を示す図である。
【図６】図６は、本発明による方法の特定実施形態を示す図である。
【図７】図７は、従来技術の生成器の線図である。
【符号の説明】
【０１６０】
Ｅ１ 検索パターンを検出
Ｅ２ 出力パターンを検出
Ｅ３ 最後の２つの段階を反復
【技術分野】
【０００１】
本発明は、符号化／復号化の分野に関し、疑似ランダムデータシーケンスを生成するシステム及び方法に関する。
【０００２】
本発明は、暗号化及び復号化が同一の秘密鍵を使用する対称暗号化を対象とするビットのシーケンスを生成することに供する点で、とても有利な用途を見出す。本発明は、暗号化動作及び復号化動作が同一である標準のストリーム暗号化方法に順応する。対称暗号化は通常、移動体通信（ＧＳＭ、ＵＭＴＳ等）、インターネット（ＳＳＬ等）、スマートカード（バンクカード）等のような、全種類の通信に使用される。
【背景技術】
【０００３】
最も広く普及したストリーム暗号化方法は、ハードウェアを節約するために、線形フィードバックシフトレジスタを用いて暗号化されるべきメッセージに対して独立した一連の暗号化を生成する。
【０００４】
線形フィードバックシフトレジスタの主な欠点は、その線形性である。実際、レジスタ長に等しいレジスタの多数の出力ビットを知ること、及びレジスタに関連付けられたフィードバック多項式を知ることは、レジスタの出力ビットと全ての後続の状態とを判断することを可能にする。
【０００５】
従って、線形フィードバックシフトレジスタの線形性を“破る”ためには、例えば非線形ブール関数を用いて、複数のレジスタの出力を結合すること、及び場合によりその内部状態を結合することも標準的な習慣である。
【０００６】
図７は、第１線形フィードバックシフトレジスタ１１１ａと、第２線形フィードバックシフトレジスタ１１１ｂと、生成器１００の出力を選択するための手段１１２とを含む、欧州特許出願ＥＰ０６１９６５９で説明された“疑似ランダム数生成器（shrinking generator）”として知られる当該生成器１００を示す。
【０００７】
従って、各シフト上で、２つのレジスタ１１１ａ及び１１１ｂは、同時にシフトされる。第１レジスタ１１１ａの出力が１の場合、装置１００の出力は、第２レジスタ１１１ｂの出力に等しく、そうでない場合、出力されない。
【０００８】
疑似ランダム数生成器は、２つの線形フィードバックレジスタの出力だけでなく、より一般には任意の組の一連のビットを結合する。疑似ランダム数生成器は、１つの線形フィードバックレジスタが他の線形フィードバックレジスタを制御するストリーム暗号化方法の部類である。その目的は、レジスタの線形性を破るために、まず、採用された各種レジスタ間のシフト数、次に、２つの連続ビット間のシフト数を変更することにある。
【０００９】
“自動疑似ランダム数生成器”として知られる疑似ランダム数生成器の変形は、同一の原理に基づくが、単独のレジスタを使用する。レジスタの出力ビットは、２つずつ読み込まれる。第１ビットが１である場合にシステムの出力が第２ビットになり、そうでない場合に出力されないように、第１ビットは、第２ビットの出力を制御する。
【００１０】
線形フィードバックレジスタのみを使用することは、多数の欠点を有する。主な欠点は、装置の線形性から生じる脆弱性である。レジスタがブール関数を用いて結合される場合も不利である。ハードウェアレベルでは、これらの不利な点は、関数を実行する複雑性から生じる。また、この関数は、固定され、それを攻撃することを可能にする。
【００１１】
また、統計的方法は、疑似ランダム数生成器と他のクロック制御暗号化方法との所定の脆弱性を明らかにした。特に、疑似ランダム数生成器において、２つの出力ビット間で２つのレジスタによってもたらされるシフト数は、両レジスタに対して同じ量だけ変わる。
【００１２】
最後に、疑似ランダム数生成器の最後の欠点は、演算されるビット数に対する出力ビット数のその低い割合であり、平均して１／４に等しい。この割合は、自動疑似ランダム数生成器と同じであり、疑似ランダム数生成器の脆弱性の大部分を有する。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明の目的は、上記欠点を改善し、良好な品質の疑似ランダムデータシーケンスの生成を単純化することにある。
【００１４】
もう１つの目的は、出力ビット数と演算されたビット数との間の割合を１／４よりも高くする方法及び生成器を提案することにある。
【００１５】
さらにもう１つの目的は、低コストでかなり効率的な生成器を提供することにある。
【課題を解決するための手段】
【００１６】
上記目的は、疑似ランダムデータシーケンスを生成する方法を用いて達成され、前記疑似ランダムデータシーケンスは、Ｎビットの初期データシーケンスにおける検索パターンに対する検索の手順によって生成される。
【００１７】
故に、本発明による方法は、一つ以上のビットストリームの非線形結合により新たなビットストリームを得ることを可能にするパターンの検出に基づき疑似ランダムデータを生成する非線形方法に関する。
【００１８】
この方法は、容易に実施されるが、良好な品質の疑似ランダムデータシーケンスを生成するために、本質的な複雑性を有する。
【００１９】
検索手順は、
・一組の検索パターンの１つであるｒビットの特定の検索パターンを前記初期データシーケンスにおいて検出する段階と、
・先行する段階の進行に依存する動作によってｋビットの出力パターンを判断する段階と、
・一連の出力パターンから疑似ランダムデータシーケンスを連続して形成するために先行する段階を反復する段階とを具備する。
【００２０】
前記検索パターンを検出する段階と前記出力パターンを判断する段階とは、前記検索パターンを検出するために前記初期データシーケンス上でウィンドウをシフトするためのシフトモードを定義するための第１組の規則を含む一連の動作によってもたらされ、前記ウィンドウは、前記初期データシーケンス上で特定の初期位置と特定のビットサイズとを有する。
【００２１】
一連の動作は、前記初期データシーケンス上で前記ウィンドウのシフトを停止するための条件を判断する第２組の規則をさらに含む。
【００２２】
前記第２組の規則からの規則は、前記ウィンドウのシフト及び／又はコンテンツの関数として、前記１組の検索パターン及び／又は前記出力パターンの更新を管理する。
【００２３】
前記一連の動作は、所定の条件が満たされるまで反復される。
【００２４】
一連の動作は、各実行の後に有利に変更される。
【００２５】
本発明の特徴によると、一連の動作は、１ビットの検索パターンを検出するために、及び１ビットの出力パターンを判断するために、各実行の後に引続き同じ動作のままであり、ビット毎に連続して前記初期データシーケンス上で１ビットのウィンドウをシフトする。
【００２６】
本発明の第１実施形態において、一連の動作は、
・検索パターンにウィンドウからのビットを置く段階と、
・現在のビットから次のビットへ、ビット毎にウィンドウをシフトする段階と、
・ウィンドウのコンテンツが検索パターンのそれと等しい場合、第１法則に従い出力パターンを更新する段階と、
・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、第２法則に従い出力パターンを更新する段階と、
・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、次のビットへビット毎にウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけウィンドウをシフトする段階と、
・出力パターンを出力する段階とを含む。
【００２７】
第１実施形態において、第１法則は、出力パターンに特定値ｂを割り当て、第２法則は、前記特定値ｂ及び値１の２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てる。
【００２８】
第２実施形態において、第１法則は、特定値ｂ及び検索パターンの値Ｅの２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当て、第２法則は、前記特定値ｂと、検索パターンの値Ｅと、値１との２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てる。
【００２９】
第３実施形態において、一連の動作は、
・検索パターンに第１ウィンドウからのビットを置く段階と、
・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
・第１ウィンドウのコンテンツが検索パターンの値に等しい場合、第１特定値ｂ１及び検索パターンの値Ｅの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第１ウィンドウのコンテンツが検索パターンの値Ｅに等しくない場合、前記第１特定値ｂ１と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、次のビットへビット毎に第１ウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
・第２ウィンドウからのビットによって検索パターンの値を置き換える段階と、
・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しい場合、第２特定値ｂ２と、出力パターンの現在の値ｓと、検索パターンの値Ｅとの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、出力パターンの現在の値ｓと、前記第２特定値ｂ２と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、次のビットへビット毎に第２ウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
・出力パターンを出力する段階とを含む。
【００３０】
本発明の用途において、前記疑似ランダムデータシーケンスの各ビットは、暗号化されたデータシーケンスを形成するために、２を法とする加算によって暗号化されるべきメッセージのデータシーケンスの対応するビットに結合される。
【００３１】
また、本発明は、Ｎビットの初期データシーケンスにおける検索パターンに対する検索のための検索手段を含む疑似ランダムデータシーケンスの生成器を提供する。
【００３２】
生成器の検索手段は、
・一組の検索パターンの１つであるｒビットの特定の検索パターンを前記初期データシーケンスにおいて検出するための検出手段と、
・前記検索パターンの検出の進行に依存する動作に従いｋビットの出力パターンを判断するための判断手段と、
・一連の出力パターンから疑似ランダムデータシーケンスを生成するための反復手段とを含む。
【００３３】
検出手段は、前記初期データシーケンス上でシフトされるよう適合されたウィンドウと、前記初期データシーケンス上で前記ウィンドウのシフトを制御するための第１制御手段とを含む。
【００３４】
判断手段は、前記一組の検索パターン及び／又は前記出力パターンを更新するための第２制御手段を含む。
【００３５】
生成器は、Ｎビットの初期データシーケンスを生成するための初期手段（１１）をさらに含む。
【００３６】
初期手段は、線形フィードバックシフトレジスタを含む。
【００３７】
また、本発明は、上記特徴を有する生成器と、排他的ＯＲ論理ゲートを含む符号化装置とを目的とする。
【００３８】
また、本発明は、各々が符号化装置を含む少なくとも２つのエンティティを含むセキュアシステムを目的とする。
【発明を実施するための最良の形態】
【００３９】
図１は、疑似ランダムデータシーケンス３を生成するための本発明による生成器１の一例を概略的に示す。
【００４０】
生成器１は、Ｎビットの初期データシーケンス９における検索パターン７に対して検索するための検索手段５を含む。検索パターンは、一組の検索パターンに含まれる。
【００４１】
“パターン”という用語は、０及び１以外からなる任意の単語を指すために以下で使用される。例えば、０、１１、０００、１０１０、００１１１は、１、２、３、４及び５の長さをそれぞれ備えたパターンである。また、“空”パターンは、空単語である。
【００４２】
Ｎビット（Ｎが整数）の初期データシーケンスは、最大周期の線形フィードバックシフトレジスタを含むことができる初期手段１１によって生成される。
【００４３】
線形フィードバックシフトレジスタは、フィードバック多項式と呼ばれる多項式によって表される、テーブル入力の線形結合が提供された有限長（レジスタ）のビットのテーブルである。各シフト上で、最高指数を備えたビットが出力され、全ての他のビットが１指数だけシフトされ、最低指数を備えたビットがシフトの前に線形結合の値を取る。
【００４４】
フィードバック多項式は、最大周期の線形シフトレジスタに対応する原始多項式、例えばＰが原始多項式である、Ｑ＝（ｘ２＋１）Ｐの式の多項式にすることができる利点がある。
【００４５】
生成器１の検索手段５は、検出手段１３と、判断手段１５と、反復手段１７とを含む。
【００４６】
検出手段１３は、ｒがＮ未満の整数である、初期データシーケンスにおけるｒビットの検索パターン７を検出する。判断手段１５は、検出手段１３によって検出される検索パターン７が属する一組の検索パターンを定義する。
【００４７】
検出手段は、初期データシーケンス９上でシフトされるように適合されたウィンドウ１９と、初期データシーケンス９上でウィンドウ１９のシフトを制御するための第１制御手段２１とを含む。
【００４８】
各ウィンドウ１９は、初期データシーケンス９における特定の初期位置に置かれ、特定のビットサイズを有する。例えば、初期データシーケンス９上に置かれたサイズｔ（ｔは、Ｎ未満の整数である）のウィンドウ１９は、シーケンス９のまさにｔビットを各シフト上に曝すためにシーケンス９上でシフトされることができるマスクである。
【００４９】
判断手段１５は、接続２３を介して検出手段１３と交信する。判断手段１５は、検索パターン７に対する検索の進行に依存する動作によってｋビット（ｋは、Ｎ未満の整数である）の出力パターン２５を判断する。
【００５０】
実際、判断手段１５は、一組の検索パターン及び／又は出力パターン２５を定義又は更新するための第２制御手段２７を含む。
【００５１】
また、反復手段１７は、それぞれ接続２９及び３１を介して検出手段１３及び判断手段１５に接続される。
【００５２】
従って、所定の停止条件が満たされない場合、例えば出力パターン２５が丁度出力された旨の信号を判断手段１５から受信した場合、反復手段１７は、検出及び判断動作を再開するために検出手段１３及び判断手段１５に対して信号を交わすことができる。また、反復手段１７は、検出手段１３及び判断手段１５に対して信号を交わすことによって停止条件をテストすることができる。これは、一連の出力パターン２５を生成し、連続形式による疑似ランダムデータシーケンス３になる。
【００５３】
また、反復手段１７は、検出手段１３及び判断手段１５の第１又は第２制御手段２１又は２７に統合されうる点に留意すべきである。
【００５４】
図２は、インターネット、ＧＳＭ、ＵＭＴＳ等の種類の通信ネットワーク３５を介して相互接続された少なくとも２つのエンティティを含むセキュアシステム３１を示す。
【００５５】
この図の例は、第２エンティティ３３ｂへ通信ネットワーク３５を介して接続された第１エンティティ３３ａを示す。第１エンティティ３３ａ（それぞれ第２エンティティ３３ｂ）は、第１端末３７ａ（それぞれ第２端末３７ｂ）と、第１符号化装置３９ａ（それぞれ第２符号化装置３９ｂ）と、第１モデム４１ａ（それぞれ第２モデム４１ｂ）とを含み、モデム４１ａ及び４１ｂは、通信ネットワーク３５に対してインタフェースするための任意の装置からなる。
【００５６】
各第１及び第２符号化装置３９ａ、３９ｂは、上述のような疑似ランダムデータシーケンス３を生成するための生成器１と、排他的ＯＲ論理ゲートとを含む。
【００５７】
各符号化装置３９ａ、３９ｂは、ストリームの暗号化又は復号化を実行し、ビット毎にメッセージを暗号化又は復号化することにある。
【００５８】
この例において、第１符号化装置３９ａは、暗号化動作を実行する。従って、一連の暗号化と呼ばれる疑似ランダムデータシーケンス３は、第１モデム４１ａによって第２エンティティ３３ｂへその後送信される暗号化されたテキスト４７を取得するために、第１端末３７ａによって平文で送信されたメッセージ４５における対応する位置で各ビットに対して排他的ＯＲゲート４３によって結合される。故に、暗号化動作は、暗号化されたテキスト４７を取得するために、ビット毎にメッセージ４５の平文テキストへ一連の暗号化３を追加することにある。
【００５９】
第２符号化装置３９ｂは、平文でテキストメッセージ４５を再公式化するために、第１エンティティ３３ａによって送信された暗号化されたテキスト４７へビット毎に同一の一連の暗号化３を追加することにある復号化動作を実行する。
【００６０】
故に、暗号化及び復号化動作は、同一である。
【００６１】
図３から６は、疑似ランダムデータを生成する本発明による方法を示す。
【００６２】
この方法は、初期データシーケンス９における検索パターンに対する検索をするための手順から疑似ランダムデータシーケンス３を生成することにある。
【００６３】
従って、疑似ランダムデータシーケンスの要素の本発明に従う判断は、検索されたパターン及び検索の履歴、即ち実施された方法に依存することができる。
【００６４】
図３は、本発明に従う疑似ランダムデータシーケンス３を生成するための検索手順の一例を示す。
【００６５】
段階Ｅ１は、一組の検索パターンの１つであるｒビットの特定の検索パターン７の初期データシーケンス９における検出に関する。
【００６６】
段階Ｅ２は、先行の段階Ｅ１の進行に依存する動作によるｋビットの出力パターン２５の判断に関する。
【００６７】
実際、出力パターン２５の判断は、検索パターン７及び検索の履歴に依存することができ、特に初期データシーケンス９において問題のある検索パターン７を発見する前にもたらされた段階又は反復の数に依存することができる。
【００６８】
検索パターン７を検出する段階Ｅ１と出力パターン２５を判断する段階Ｅ２とは、一連の動作によってもたらされる。
【００６９】
この一連の動作は、検索パターン７を検出するために、シフトモードを定義して初期データシーケンス９上でウィンドウ１９をシフトするための生成器１の第１制御手段２１によって実施される第１組の規則を含む。
【００７０】
非ヌルサイズの１つ以上のウィンドウ１９は一般に、初期データシーケンス９上でシフトされる。検索手順の初めにおいて、各ウィンドウ１９は、初期シーケンス９上の初期位置に置かれる（例えば、それらは全て、初期シーケンス９の初めに置かれることができる）。（複数の）ウィンドウ１９における（複数の）ビットは、出力パターン２５を判断するために使用される。
【００７１】
第１組の規則は、シフト方向、シフト振幅又はウィンドウ１９をシフトする形式、例えば一部の初期データシーケンス９上で循環シフトを定義することができる。
【００７２】
例えば、第１組の規則は、以下のように定義された規則ｒ１を含むことができる。
ｒ１＝“１ビット右へシフト”
【００７３】
また、一連の動作は、初期データシーケンス９上でウィンドウ１９のシフトを停止するための条件を判断する生成器１の第２制御手段２７によって実施される第２組の規則を含む。
【００７４】
第２組の規則は、生成器１が出力パターン２５を配信する前に、特定の順番で適用されなければならない規則を含むことができる。故に、一連の出力パターン２５の生成器１による配信は、疑似ランダムデータシーケンス３を形成する。
【００７５】
例えば、第２組の規則は、以下のように定義された規則ｒ２を含むことができる。
ｒ２＝“ウィンドウ１９のコンテンツが一組の検索パターン７からのパターンではない間、規則ｒ１に従ってウィンドウ１９をシフト” ここでｒ１は、第１組の規則からの規則である。
【００７６】
また、この第２組の規則からのもう１つの規則は、所定の２進法に従って、及びウィンドウ１９のシフト及び／又はコンテンツの関数として、１組の検索パターン７及び／又は出力パターン２５の更新を管理する。
【００７７】
従って、検索パターン７は、ウィンドウ１９のコンテンツに依存して、又は第１及び第２組の規則を含む一連の動作の先行する実行に依存して、空、即ちパターンがないことがある。
【００７８】
同様に、出力パターン２５は、ウィンドウ１９のコンテンツに依存して、又は第１及び第２組の規則を含む一連の動作の先行する実行に依存して、空、即ちパターンがないことがある。
【００７９】
また、検索手順の段階Ｅ３は、連続によって一連の出力パターン２５から疑似ランダムデータシーケンス３を形成するために、引続き先行する２つの段階Ｅ１及びＥ２を反復する。
【００８０】
一連の動作は、所定の条件が満たされるまで反復されることができる点に留意すべきである。その条件は、それが有限である場合、初期データシーケンス９のウィンドウ１９のコンテンツにすることができる。また、ユーザによって定義された条件が満たされるまで一連の動作を反復することができる。
【００８１】
また、疑似ランダムデータシーケンス３の質をさらに高めるために、各実行の後に一連の動作を変更することができる。
【００８２】
従って、この方法は、疑似ランダムデータシーケンス３の各出力ビットが初期ストリーム９における一つ以上のパターン７に対する一つ以上の検索に依存するように、一つ以上のウィンドウ１９を用いて初期ビットストリーム（初期データシーケンス９）を走査することにある。また、検索されるべき（複数の）パターン７は、（複数の）ウィンドウ１９のコンテンツ及び／又はシフトに依存することができる。
【００８３】
図４から６は、本発明による方法の特定の実施形態を示す。
【００８４】
これらの例において、一連の動作は、各実行の後に引続き同じ動作のままであり、ウィンドウ１９は、“サイズ１”（即ち、各ウィンドウが１ビットを含む）であり、一組の検索パターン７は、１つの検索パターンを含み、（複数の）検索パターン７及び出力パターン２５も、サイズ１である。
【００８５】
また、ウィンドウ１９のシフトの振幅は、１ユニットに等しく、即ち各ウィンドウ１９は、例えば各反復上で、現在のビットから次のビットへ（即ち、左から右へ）、１ビットだけシフトされる。
【００８６】
従って、各初期データシーケンス９は、連続して、即ちビット毎に読み込まれることができ、とても実行しやすい実施形態をもたらす。
【００８７】
以下、Ｅは、検索パターン７の値を示し、ｓは、出力パターン２５の値を示し、ｆ、ｆ１及びｆ２は、ウィンドウ１９の値を示す。
【００８８】
まず、（複数の）検索パターン７及び出力パターン２５は、空のビットをそれらへ、即ちＥ←φ及びｓ←φへ割り当てることによって初期化され、ここでφは、空の組である。同様に、ｂ、ｂ１及びｂ２で示された２進数又は定数は、これらの実施形態の一連の動作の各アプリケーション上で同じままである、と定義される。
【００８９】
第１実施形態において、単独のウィンドウ１９は、初期データシーケンス９上でシフトされる。それは、初期データシーケンス９の第１ビット上で初めに固定されることができる。
【００９０】
第１実施形態の一連の動作は、以下のように定義されることができる。
・規則ｒ１、１＝“１ビット右へシフト”を第１組の規則の唯一の規則として設定
・以下の規則を第２組の規則の規則として設定
・ｒ２、１＝“検索パターンにウィンドウからのビットｆを置く（Ｅ←ｆ）”
・ｒ２、２＝“ｒ１、１に従いウィンドウを１回シフト”
・ｒ２、３＝“ウィンドウのコンテンツが検索パターンのビットＥに等しい場合、その後出力パターンを更新 ｓ←ｂ”
・ｒ２、４＝“ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、その後出力パターンを更新
【００９１】
【数１】
【００９２】
・ｒ２、５＝“ウィンドウのコンテンツｆが検索パターンではない間、規則ｒ１、１に従いウィンドウをシフト“
・ｒ２、６＝“ｒ１、１に従いウィンドウを１回シフト”
・規則ｒ２、１、ｒ２、２、ｒ２、３、ｒ２、４、ｒ２、５及びｒ２、６をこの順序で適用
・出力パターンｓを出力
【００９３】
実際、図４のフローチャートは、上記一連の動作の実行を示す。
【００９４】
段階Ｅ１１は、検索パターン７にウィンドウ１９からのビットを置く。
【００９５】
段階Ｅ１２は、現在のビットから次のビットへ、１ビッドだけウィンドウ１９をシフトする。
【００９６】
段階Ｅ１３は、ウィンドウ１９のコンテンツを検索パターン７のそれと比較するテストである。
【００９７】
段階Ｅ１４は、ウィンドウ１９のコンテンツが検索パターン７のそれと等しい場合、第１法則に従い出力パターン２５を更新する。この例において、第１法則は、特定値ｂを出力パターン２５へ割り当てることに対応する（ｓ←ｂ）。
【００９８】
段階Ｅ１５は、ウィンドウ１９のコンテンツが検索パターン７のビットＥに等しくない場合、第２法則に従い出力パターン２５を更新する。この例において、第２法則は、特定値ｂ及び値１の２を法とする加算に対応し、この加算の結果を出力パターン２５へ割り当てる。
【００９９】
【数２】
【０１００】
ウィンドウ１９のコンテンツが検索パターン７のビットＥに等しい場合、段階Ｅ１６及びＥ１７は、次のビットへビット毎にウィンドウ１９をシフトするループを形成する。
【０１０１】
段階Ｅ１８は、現在のビットから次のビットへ、１ビットだけウィンドウ１９をシフトする。
【０１０２】
最後に、段階Ｅ１９は、生成器１から出力パターンを出力する。
【０１０３】
大まかに言って、一連の動作は、以下のように要約できる。初期データシーケンス９における現在のビットＥは、読み込まれ、その後ビットＥが発見されるまでシーケンス９上で右へシフトすることに続く。Ｅを発見するためのシフトが１つの指数だけであった場合、その後ｂが出力され、さもなければ
【０１０４】
【数３】
【０１０５】
が出力される。その後、再開の前に右への１ビットのシフトがある。
【０１０６】
もちろん、フローチャートは、所定の条件が満たされているか否かを判断するための停止テストを含むことができる（簡略化のために図に表されていない）。
【０１０７】
例えば、上記段階は、ウィンドウ１９が初期データシーケンス９から退くまで、疑似ランダムデータシーケンスを形成するために反復されることができる。
【０１０８】
図５は、第２実施形態の一連の動作の実行を示すフローチャートである。
【０１０９】
この図のフローチャートは、段階Ｅ２４及びＥ２５のみ、図４のそれと異なる。
【０１１０】
実際、段階Ｅ２４において、第１法則は、特定値ｂと検索パターン７の値Ｅとの２を法とする加算をもたらすことに対応し、この加算の結果を出力パターン２５に割り当てる。
【０１１１】
【数４】
【０１１２】
その一方、段階Ｅ２５において、第２法則は、特定値ｂと、検索パターン７の値Ｅと、値１との２を法とする加算をもたらすことに対応し、この加算の結果を出力パターン２５に割り当てる。
【０１１３】
【数５】
【０１１４】
従って、第２実施形態の一連の動作は、以下のように定義されることができる。
・規則ｒ１、１＝“１ビット右へシフト”を第１組の規則の唯一の規則として設定
・以下の規則を第２組の規則の規則として設定
・ｒ２、１＝“検索パターンにウィンドウからのビットｆを置く（Ｅ←ｆ）”
・ｒ２、２＝“ｒ１、１に従い１回ウィンドウをシフト”
・ｒ２、３＝“ウィンドウのコンテンツが検索パターンのビットＥに等しい場合、その後出力パターンを更新”
【０１１５】
【数６】
【０１１６】
・ｒ２、４＝“ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、その後出力パターンを更新”
【０１１７】
【数７】
【０１１８】
・ｒ２、５＝“ウィンドウのコンテンツｆが検索パターンではない間、規則ｒ１、１に従いウィンドウをシフト”
・ｒ２、６＝“ｒ１、１に従い１回ウィンドウをシフト”
・規則ｒ２、１、ｒ２、２、ｒ２、３、ｒ２、４、ｒ２、５及びｒ２、６をこの順序で適用
・出力パターンｓを出力
【０１１９】
大まかに言って、第２実施形態の一連の動作は、以下のように要約できる。初期データシーケンス９における現在のビットＥは、読み込まれ、その後ビットＥが発見されるまでシーケンス上を右側へシフトすることに続く。Ｅを発見するためのシフトが１つの指数だけであった場合、その後
【０１２０】
【数８】
【０１２１】
が出力され、さもなければ
【０１２２】
【数９】
【０１２３】
が出力される。その後、再開の前に１ビットの右側へのシフトに続く。
【０１２４】
図６は、第３実施形態の一連の動作を示すフローチャートである。
【０１２５】
この第３実施形態において、２つのウィンドウ１９は、初期データシーケンス上でシフトされる。初めに、第１ウィンドウは、初期データシーケンス９の第１ビット上で固定され、初めに、第２ウィンドウは、そのシーケンスの第２ビット上で固定される。そのような状況下で、２つの定数が定義され、第１ビットはｂ１を示し、第２ビットはｂ２を示す。例えば、定数ｂ１及びｂ２は、同一値０を有する。
【０１２６】
段階Ｅ３１は、検索パターン７に第１ウィンドウからのビットを置く。
【０１２７】
段階Ｅ３２は、現在のビットから次のビットへ、１ビッドだけ第１ウィンドウをシフトする。
【０１２８】
段階Ｅ３３は、第１ウィンドウのコンテンツを検索パターン７のそれと比較するテストである。
【０１２９】
段階Ｅ３４は、第１ウィンドウのコンテンツが検索パターン７の値Ｅに等しくない場合、第１特定値ｂ１と検索パターンの値Ｅとの２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。
【０１３０】
【数１０】
【０１３１】
段階Ｅ３５は、第１ウィンドウのコンテンツが検索パターンの値Ｅに等しくない場合、第１特定値ｂ１と、検索パターン７の値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。
【０１３２】
【数１１】
【０１３３】
段階Ｅ３６及びＥ３７は、第１ウィンドウのコンテンツが検索パターン７のビットに等しくない場合、次のビットへビット毎に第１ウィンドウをシフトするループを形成する。
【０１３４】
段階Ｅ３８は、現在のビットから次のビットへ、１ビッドだけ第１ウィンドウをシフトする。
【０１３５】
段階Ｅ３９は、検索パターン７に第２ウィンドウからのビットを置く。
【０１３６】
段階Ｅ４０は、現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする。
【０１３７】
段階Ｅ４１は、第２ウィンドウのコンテンツを検索パターン７のそれと比較するテストである。
【０１３８】
段階Ｅ４２は、第２ウィンドウのコンテンツが検索パターン７の値に等しい場合、第２特定値ｂ２と、出力パターン２５の現在の値ｓと、検索パターン７の値Ｅとの２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。
【０１３９】
【数１２】
【０１４０】
段階Ｅ４３は、第２ウィンドウのコンテンツｆ２が検索パターン７の値に等しくない場合、出力パターン２５の現在の値ｓと、前記第２特定値ｂ２と、検索パターン７の値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって、出力パターン２５を更新する。
【０１４１】
【数１３】
【０１４２】
段階Ｅ４４及びＥ４５は、第２ウィンドウのコンテンツが検索パターンのビットに等しくない場合、次のビットへビット毎に第２ウィンドウをシフトするループを形成する。
【０１４３】
段階Ｅ４６は、現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする。
【０１４４】
最後に、段階Ｅ４７は、生成器１から出力パターン２５を出力する。
【０１４５】
従って、第３実施形態の一連の動作は、以下のように定義できる。
・規則ｒ１、１＝“１ビット右へシフト”を第１組の規則の唯一の規則として設定
・以下の規則を第２組の規則の規則として設定
・ｒ２、１＝“検索パターンにウィンドウからのビットｆ１を置く（Ｅ←ｆ１）”
・ｒ２、２＝“ｒ１、１に従い１回第１ウィンドウをシフト”
・ｒ２、３＝“第１ウィンドウのコンテンツｆ１が検索パターンのビットＥに等しい場合、その後
【０１４６】
【数１４】
【０１４７】
を更新“
・ｒ２、４＝“第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、その後出力パターン
【０１４８】
【数１５】
【０１４９】
を更新”
【０１５０】
・ｒ２、５＝“第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない間、規則ｒ１、１に従い第１ウィンドウをシフト”
・ｒ２、６＝“ｒ１、１に従い１回第１ウィンドウをシフト”
・ｒ２、７＝“検索パターンの値を第２ウィンドウからのビットｆ２に置き換える“
・ｒ２、８＝“ｒ１、１に従い１回第２ウィンドウをシフト”
・ｒ２、９＝“第２ウィンドウのコンテンツｆ２が検索パターンのビットＥに等しい場合、その後出力パターンを更新”
【０１５１】
【数１６】
【０１５２】
・ｒ２、１０＝“第２ウィンドウのコンテンツｆ２が検索パターンのビットＥに等しくない場合、その後出力パターンを更新”
【０１５３】
【数１７】
【０１５４】
・ｒ２、１１＝“第２ウィンドウのコンテンツｆ２が検索パターンのビットＥに等しくない場合、ｒ１、１に従い第２ウィンドウをシフト”
・ｒ２、１２＝“ｒ１、１に従い１回第２ウィンドウをシフト“
・規則ｒ２、１をｒ２、１２へこの順序で適用する。
・出力パターンｓを出力
【０１５５】
大まかに言って、第３実施形態は、第１に、第１ウィンドウが初期データシーケンス９の第１ビット上で初めに位置決めされる第２実施形態と、第２に、第２ウィンドウが初期データシーケンス９の第２ビット上で初めに位置決めされる第２実施形態とを並行して実行することによって得られた出力をビット毎に追加することになる。
【０１５６】
これらの実施形態は、実行するのが簡単である。また、例えば初期データシーケンス９を提供する初期手段１１が線形フィードバックシフトレジスタである場合、出力ビット数及び演算されたビット数間のそれらの割合は、平均１／３である。
【０１５７】
従って、本発明による方法は、対称ストリーム暗号化に用いることができる良好な品質の疑似ランダムビットシーケンスを生成する。
【０１５８】
実際、疑似ランダムデータシーケンス３の各ビットは、暗号化されたデータシーケンス４７を形成するために、２を法とする加算によって暗号化されるべきメッセージ４５のデータシーケンスの対応するビットに結合されることができる（図２を参照）。
【図面の簡単な説明】
【０１５９】
【図１】図１は、本発明による疑似ランダムデータシーケンス生成器の一例の概略図である。
【図２】図２は、図１からの生成器をふくむセキュアシステムを示す図である。
【図３】図３は、本発明に従う疑似ランダムデータシーケンスを生成するための検索手順の一例を示す図である。
【図４】図４は、本発明による方法の特定実施形態を示す図である。
【図５】図５は、本発明による方法の特定実施形態を示す図である。
【図６】図６は、本発明による方法の特定実施形態を示す図である。
【図７】図７は、従来技術の生成器の線図である。
【符号の説明】
【０１６０】
Ｅ１ 検索パターンを検出
Ｅ２ 出力パターンを検出
Ｅ３ 最後の２つの段階を反復
【特許請求の範囲】
【請求項１】
疑似ランダムデータシーケンス（３）を生成する方法であって、
前記疑似ランダムデータシーケンス（３）は、Ｎビットの初期データシーケンス（９）における検索パターン（７）に対する検索をするための手順によって生成され、
前記検索手順は、
・一組の検索パターンの１つであるｒビットの特定の検索パターン（７）を前記初期データシーケンス（９）において検出する段階（Ｅ１）と、
・先行する段階（Ｅ１）の進行に依存する動作によってｋビットの出力パターン（２５）を判断する段階（Ｅ２）と、
・一連の出力パターン（２５）から疑似ランダムデータシーケンス（３）を連続して形成するために先行する段階（Ｅ１、Ｅ２）を反復する段階と
を具備することを特徴とする方法。
【請求項２】
前記検索パターン（７）を検出する段階（Ｅ１）と前記出力パターン（２５）を判断する段階（Ｅ２）とは、前記検索パターン（７）を検出するために前記初期データシーケンス（９）上でウィンドウ（１９）をシフトするためのシフトモードを定義するための第１組の規則を含む一連の動作によってもたらされ、前記ウィンドウ（１９）は、前記初期データシーケンス（９）上で特定の初期位置と特定のビットサイズとを有することを特徴とする請求項１に記載の方法。
【請求項３】
一連の動作は、前記初期データシーケンス（９）上で前記ウィンドウ（１９）のシフトを停止するための条件を判断する第２組の規則をさらに含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記第２組の規則からの規則は、前記ウィンドウのシフト及び／又はコンテンツの関数として、前記一組の検索パターン及び／又は前記出力パターンの更新を管理することを特徴とする請求項３に記載の方法。
【請求項５】
前記一連の動作は、所定の条件が満たされるまで反復されることを特徴とする請求項２及び３の何れか１項に記載の方法。
【請求項６】
一連の動作は、各実行の後に変更されることを特徴とする請求項２及び３の何れか１項に記載の方法。
【請求項７】
一連の動作は、１ビットの検索パターン（７）を検出するために、及び１ビットの出力パターン（２５）を判断するために、各実行の後に引続き同じ動作のままであり、ビット毎に連続して前記初期データシーケンス（９）上で１ビットのウィンドウ（１９）をシフトすることを特徴とする請求項２及び３の何れか１項に記載の方法。
【請求項８】
一連の動作は、
・検索パターンにウィンドウからのビットを置く段階と、
・現在のビットから次のビットへ、ビット毎にウィンドウをシフトする段階と、
・ウィンドウのコンテンツが検索パターンのそれと等しい場合、第１法則に従い出力パターンを更新する段階と、
・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、第２法則に従い出力パターンを更新する段階と、
・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、次のビットへビット毎にウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけウィンドウをシフトする段階と、
・出力パターンを出力する段階と
を具備することを特徴とする請求項７に記載の方法。
【請求項９】
第１法則は、出力パターンに特定値ｂを割り当て、第２法則は、前記特定値ｂ及び値１の２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てることを特徴とする請求項８に記載の方法。
【請求項１０】
第１法則は、特定値ｂ及び検索パターンの値Ｅの２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当て、第２法則は、前記特定値ｂと、検索パターンの値Ｅと、値１との２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てることを特徴とする請求項８に記載の方法。
【請求項１１】
一連の動作は、
・検索パターンに第１ウィンドウからのビットを置く段階と、
・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
・第１ウィンドウのコンテンツが検索パターンの値に等しい場合、第１特定値ｂ１及び検索パターンの値Ｅの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第１ウィンドウのコンテンツが検索パターンの値Ｅに等しくない場合、前記第１特定値ｂ１と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、次のビットへビット毎に第１ウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
・第２ウィンドウからのビットによって検索パターンの値を置き換える段階と、
・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しい場合、第２特定値ｂ２と、出力パターンの現在の値ｓと、検索パターンの値Ｅとの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、出力パターンの現在の値ｓと、前記第２特定値ｂ２と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、次のビットへビット毎に第２ウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
・出力パターンを出力する段階と
を具備することを特徴とする請求項７に記載の方法。
【請求項１２】
前記疑似ランダムデータシーケンスの各ビットは、暗号化されたデータシーケンスを形成するために、２を法とする加算によって暗号化されるべきメッセージのデータシーケンスの対応するビットに結合されることを特徴とする請求項１から１１の何れか１項に記載の方法。
【請求項１３】
疑似ランダムデータシーケンス（３）の生成器であって、Ｎビットの初期データシーケンス（９）における検索パターン（７）に対する検索のための検索手段（５）を含み、
前記検索手段（５）は、
・一組の検索パターンの１つであるｒビットの特定の検索パターンを前記初期データシーケンス（９）において検出するための検出手段（１３）と、
・前記少なくとも１つの検索パターン（７）の検出の進行に依存する動作に従いｋビットの出力パターン（２５）を判断するための判断手段（１５）と、
・一連の出力パターン（２５）から疑似ランダムデータシーケンス（３）を生成するための反復手段（１７）と
を具備することを特徴とする生成器。
【請求項１４】
検出手段（１３）は、前記初期データシーケンス（９）上でシフトされるよう適合されたウィンドウ（１９）と、前記初期データシーケンス（９）上で前記ウィンドウのシフトを制御するための第１制御手段（２１）とを含むことを特徴とする請求項１３に記載の生成器。
【請求項１５】
判断手段（１５）は、前記一組の検索パターン及び／又は前記出力パターンを更新するための第２制御手段（２７）を含むことを特徴とする請求項１３に記載の生成器。
【請求項１６】
Ｎビットの初期データシーケンスを生成するための初期手段（１１）をさらに含むことを特徴とする請求項１３から１５の何れか１項に記載の生成器。
【請求項１７】
初期手段（１１）は、線形フィードバックシフトレジスタを含むことを特徴とする請求項１６に記載の生成器。
【請求項１８】
請求項１３から１７の何れか１項に記載の生成器（１）をさらに含むことを特徴とする、排他的ＯＲ論理ゲート（４３）を含む符号化装置（３９）。
【請求項１９】
少なくとも２つのエンティティ（３３ａ、３３ｂ）の各々は、請求項１８に記載の符号化装置（３９ａ、３９ｂ）を含むことを特徴とする、前記少なくとも２つのエンティティ（３３ａ、３３ｂ）を含むセキュアシステム。
【請求項１】
疑似ランダムデータシーケンス（３）を生成する方法であって、
前記疑似ランダムデータシーケンス（３）は、Ｎビットの初期データシーケンス（９）における検索パターン（７）に対する検索をするための手順によって生成され、
前記検索手順は、
・一組の検索パターンの１つであるｒビットの特定の検索パターン（７）を前記初期データシーケンス（９）において検出する段階（Ｅ１）と、
・先行する段階（Ｅ１）の進行に依存する動作によってｋビットの出力パターン（２５）を判断する段階（Ｅ２）と、
・一連の出力パターン（２５）から疑似ランダムデータシーケンス（３）を連続して形成するために先行する段階（Ｅ１、Ｅ２）を反復する段階と
を具備することを特徴とする方法。
【請求項２】
前記検索パターン（７）を検出する段階（Ｅ１）と前記出力パターン（２５）を判断する段階（Ｅ２）とは、前記検索パターン（７）を検出するために前記初期データシーケンス（９）上でウィンドウ（１９）をシフトするためのシフトモードを定義するための第１組の規則を含む一連の動作によってもたらされ、前記ウィンドウ（１９）は、前記初期データシーケンス（９）上で特定の初期位置と特定のビットサイズとを有することを特徴とする請求項１に記載の方法。
【請求項３】
一連の動作は、前記初期データシーケンス（９）上で前記ウィンドウ（１９）のシフトを停止するための条件を判断する第２組の規則をさらに含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記第２組の規則からの規則は、前記ウィンドウのシフト及び／又はコンテンツの関数として、前記一組の検索パターン及び／又は前記出力パターンの更新を管理することを特徴とする請求項３に記載の方法。
【請求項５】
前記一連の動作は、所定の条件が満たされるまで反復されることを特徴とする請求項２及び３の何れか１項に記載の方法。
【請求項６】
一連の動作は、各実行の後に変更されることを特徴とする請求項２及び３の何れか１項に記載の方法。
【請求項７】
一連の動作は、１ビットの検索パターン（７）を検出するために、及び１ビットの出力パターン（２５）を判断するために、各実行の後に引続き同じ動作のままであり、ビット毎に連続して前記初期データシーケンス（９）上で１ビットのウィンドウ（１９）をシフトすることを特徴とする請求項２及び３の何れか１項に記載の方法。
【請求項８】
一連の動作は、
・検索パターンにウィンドウからのビットを置く段階と、
・現在のビットから次のビットへ、ビット毎にウィンドウをシフトする段階と、
・ウィンドウのコンテンツが検索パターンのそれと等しい場合、第１法則に従い出力パターンを更新する段階と、
・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、第２法則に従い出力パターンを更新する段階と、
・ウィンドウのコンテンツが検索パターンのビットと等しくない場合、次のビットへビット毎にウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけウィンドウをシフトする段階と、
・出力パターンを出力する段階と
を具備することを特徴とする請求項７に記載の方法。
【請求項９】
第１法則は、出力パターンに特定値ｂを割り当て、第２法則は、前記特定値ｂ及び値１の２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てることを特徴とする請求項８に記載の方法。
【請求項１０】
第１法則は、特定値ｂ及び検索パターンの値Ｅの２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当て、第２法則は、前記特定値ｂと、検索パターンの値Ｅと、値１との２を法とする加算をもたらし、出力パターンに前記加算の結果を割り当てることを特徴とする請求項８に記載の方法。
【請求項１１】
一連の動作は、
・検索パターンに第１ウィンドウからのビットを置く段階と、
・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
・第１ウィンドウのコンテンツが検索パターンの値に等しい場合、第１特定値ｂ１及び検索パターンの値Ｅの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第１ウィンドウのコンテンツが検索パターンの値Ｅに等しくない場合、前記第１特定値ｂ１と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第１ウィンドウのコンテンツが検索パターンのビットＥに等しくない場合、次のビットへビット毎に第１ウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけ第１ウィンドウをシフトする段階と、
・第２ウィンドウからのビットによって検索パターンの値を置き換える段階と、
・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しい場合、第２特定値ｂ２と、出力パターンの現在の値ｓと、検索パターンの値Ｅとの２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、出力パターンの現在の値ｓと、前記第２特定値ｂ２と、検索パターンの値Ｅと、値１との２を法とする加算の結果をそれに割り当てることによって出力パターンを更新する段階と、
・第２ウィンドウのコンテンツが検索パターンの値に等しくない場合、次のビットへビット毎に第２ウィンドウをシフトする段階と、
・現在のビットから次のビットへ、１ビットだけ第２ウィンドウをシフトする段階と、
・出力パターンを出力する段階と
を具備することを特徴とする請求項７に記載の方法。
【請求項１２】
前記疑似ランダムデータシーケンスの各ビットは、暗号化されたデータシーケンスを形成するために、２を法とする加算によって暗号化されるべきメッセージのデータシーケンスの対応するビットに結合されることを特徴とする請求項１から１１の何れか１項に記載の方法。
【請求項１３】
疑似ランダムデータシーケンス（３）の生成器であって、Ｎビットの初期データシーケンス（９）における検索パターン（７）に対する検索のための検索手段（５）を含み、
前記検索手段（５）は、
・一組の検索パターンの１つであるｒビットの特定の検索パターンを前記初期データシーケンス（９）において検出するための検出手段（１３）と、
・前記少なくとも１つの検索パターン（７）の検出の進行に依存する動作に従いｋビットの出力パターン（２５）を判断するための判断手段（１５）と、
・一連の出力パターン（２５）から疑似ランダムデータシーケンス（３）を生成するための反復手段（１７）と
を具備することを特徴とする生成器。
【請求項１４】
検出手段（１３）は、前記初期データシーケンス（９）上でシフトされるよう適合されたウィンドウ（１９）と、前記初期データシーケンス（９）上で前記ウィンドウのシフトを制御するための第１制御手段（２１）とを含むことを特徴とする請求項１３に記載の生成器。
【請求項１５】
判断手段（１５）は、前記一組の検索パターン及び／又は前記出力パターンを更新するための第２制御手段（２７）を含むことを特徴とする請求項１３に記載の生成器。
【請求項１６】
Ｎビットの初期データシーケンスを生成するための初期手段（１１）をさらに含むことを特徴とする請求項１３から１５の何れか１項に記載の生成器。
【請求項１７】
初期手段（１１）は、線形フィードバックシフトレジスタを含むことを特徴とする請求項１６に記載の生成器。
【請求項１８】
請求項１３から１７の何れか１項に記載の生成器（１）をさらに含むことを特徴とする、排他的ＯＲ論理ゲート（４３）を含む符号化装置（３９）。
【請求項１９】
少なくとも２つのエンティティ（３３ａ、３３ｂ）の各々は、請求項１８に記載の符号化装置（３９ａ、３９ｂ）を含むことを特徴とする、前記少なくとも２つのエンティティ（３３ａ、３３ｂ）を含むセキュアシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公表番号】特表２００８−５０８６２７（Ｐ２００８−５０８６２７Ａ）
【公表日】平成２０年３月２１日（２００８．３．２１）
【国際特許分類】
【出願番号】特願２００７−５２４３６０（Ｐ２００７−５２４３６０）
【出願日】平成１６年８月２日（２００４．８．２）
【国際出願番号】ＰＣＴ／ＦＲ２００４／００２０７０
【国際公開番号】ＷＯ２００６／０２４７０５
【国際公開日】平成１８年３月９日（２００６．３．９）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【出願人】（５０７０３５０２０）ユニヴェルシテ・ドゥ・カン・バッス・ノルマンディ (1)
【Ｆターム（参考）】
【公表日】平成２０年３月２１日（２００８．３．２１）
【国際特許分類】
【出願日】平成１６年８月２日（２００４．８．２）
【国際出願番号】ＰＣＴ／ＦＲ２００４／００２０７０
【国際公開番号】ＷＯ２００６／０２４７０５
【国際公開日】平成１８年３月９日（２００６．３．９）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【出願人】（５０７０３５０２０）ユニヴェルシテ・ドゥ・カン・バッス・ノルマンディ (1)
【Ｆターム（参考）】
[ Back to top ]