(57)【要約】  本発明は、初期データフロー（３）から擬似乱数データ列（１）を生成するための装置及び方法において、完全プレフィクス符号（５）を構成する符号語集合を定義する段階と、出力語集合（７）を定義する段階と、前記出力語集合（７）の出力語に、前記完全プレフィクス符号（５）の符号語を関連付ける非同期化関数（ｆ）を定義する段階と、初期データフロー（３）を、前記完全プレフィクス符号（５）に従って符号化された語の列（１１）に分解する段階と、前記擬似乱数データ列（１）を構成するために、前記符号化された語の列（１１）の語に、前記非同期化関数（ｆ）に従って対応する出力語を関連付ける段階とを具備することを特徴とする装置及び方法に関する。
2008542805.tif 000002
【特許請求の範囲】
【請求項１】
初期データフロー（３）から擬似乱数データ列（１）を生成するための方法において、
・完全プレフィクス符号（５）を構成する符号語集合を定義する段階と、
・出力語集合（７）を定義する段階と、
・前記出力語集合（７）からの出力語に、前記完全プレフィクス符号（５）の符号語を関連付ける非同期化関数（ｆ）を定義する段階と、
・初期データフロー（３）を、前記完全プレフィクス符号（５）に従って符号化された語の列（１１）に分解する段階と、
・前記擬似乱数データ列（１）を構成するために、前記符号化された語の列（１１）の語に、前記非同期化関数（ｆ）に従って対応する出力語を関連付ける段階と、
を具備することを特徴とする方法。
【請求項２】
前記非同期化関数（ｆ）は、擬似乱数データ列（１）の生成の間に値を修正可能である所定パラメータに依存するパラメータ化された関数であることを特徴とする請求項１に記載の方法。
【請求項３】
前記出力語集合（７）は、各出力語に対して相補的な出力語を具備することを特徴とする請求項１に記載の方法。
【請求項４】
前記完全プレフィクス符号（５）の符号語は、上限ｈによって制限された長さを具備するとともに、もし、出力語ｘと他の出力語ｙとが同一の長さを具備するならば、前記関数による出力語ｘの逆像の数は、前記関数による出力語ｙの逆像の数と等しいことを特徴とする請求項１〜３の何れか１項に記載の方法。
【請求項５】
前記完全プレフィクス符号（５）の語は、下限ｍによって制限された長さを具備するとともに、前記完全プレフィクス符号（５）の語の上限長さｌがあって、前記上限長さｌより小さい又は等しい任意の長さｋに対して、前記完全プレフィクス符号は２ｍ−１個の長さｋの語を具備することを特徴とする請求項４に記載の方法。
【請求項６】
・完全プレフィクス符号（５）は、ｈ≧２として次の形
【数１】
2008542805.tif 000041
を有する符号語集合Ｃ１で定義し、
・出力語集合（７）は、２進集合Ｅ１＝｛０，１｝からの語で定義し、
・パラメータ化された非同期化関数（ｆ）の所定パラメータｕは、成分が集合｛０，１｝に属するベクトル
【数２】
2008542805.tif 000042
であり、
・パラメータ化された非同期化関数ｆｕは、次の
【数３】
2008542805.tif 000043
のように定義することを特徴とする請求項４又は請求項５に記載の方法。
【請求項７】
・完全プレフィクス符号（５）は、次の形
【数４】
2008542805.tif 000044
の２バイトから構成される符号語集合Ｃ２で定義し、
・出力語集合（７）は、集合
【数５】
2008542805.tif 000045
からの語で定義し、
・パラメータ化された非同期化関数（ｆ）の所定パラメータνは、成分が集合｛０，１｝に属するベクトル 
【数６】
2008542805.tif 000046
であり、最初の８個の成分の値
【数７】
2008542805.tif 000047
は不変であるとともに、最後の成分の値
【数８】
2008542805.tif 000048
は変化するとともに、
・パラメータ化された非同期化関数
【数９】
2008542805.tif 000049
は、ｗ１ｗ２の形の任意の語に、
・もし、次の条件
【数１０】
2008542805.tif 000050
の１つが満たされるならばｗ１を、
・もし、次の条件
【数１１】
2008542805.tif 000051
の１つが満たされるならばｗ２を、
・もし、
【数１２】
2008542805.tif 000052
ならば空語εを、
関連付けることを特徴とする請求項４に記載の方法。
【請求項８】
初期データフロー（３）から擬似乱数データ列（１）を生成する生成器において、
メモリ（２５）と処理ユニット（２７）とを具備し、
前記メモリは完全プレフィクス符号（５）を構成する符号語集合と出力語集合（７）とを格納し、
前記処理ユニット（２７）は、初期データフロー（３）を読み込み可能であるとともに、前記初期データフローを前記完全プレフィクス符号（５）に従って符号化された語の列（１１）に分解可能であるとともに、前記擬似乱数データ列（１）を生成するために、非同期化関数（ｆ）に従って、前記符号化された語の列（１１）の語に対応する出力語を関連付け可能であることを特徴とする生成器。
【請求項９】
前記非同期化関数（９）を所定パラメータに依存させるとともに、擬似乱数データ列（１）の生成の間に前記所定パラメータ値を修正するパラメータ手段（２９）をさらに具備することを特徴とする請求項８に記載の生成器。
【請求項１０】
排他的論理和論理ゲート（４３）を具備する暗号化／暗号解除装置において、
請求項９又は請求項１０に記載の生成器（２１）をさらに具備することを特徴とする暗号化／暗号解除装置。
【請求項１１】
ネットワーク（３５）経由で接続された少なくとも２つの構成要素（３７ａ，３７ｂ）を具備するセキュアなシステムにおいて、
前記少なくとも２つの構成要素は、それぞれ請求項１０に記載の暗号化／暗号解除装置（３９ａ，３９ｂ）を具備することを特徴とするセキュアなシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化／暗号解除の分野に関するとともに、本発明は、擬似乱数データ列を生成するシステム及び方法に関する。
【０００２】
本発明は、暗号化及び暗号解除で同一の秘密鍵を使用する暗号化処理である、対称暗号化を目的としたビット列の生成に非常に好ましい応用を見出す。本発明の背景は、第１に、同一の長さの擬似乱数データ列にメッセージを１ビットずつ加算するフロー暗号化（ｆｌｏｗ  ｅｎｃｒｙｐｔｉｏｎ）方法であり、第２に、暗号化動作及び暗号解除動作が同一である方法である。対称暗号化は、携帯通信（ＧＳＭ，ＵＭＴＳ等）や、インターネット（ＳＳＬ等）や、マイクロチップカード（銀行カード）等の全タイプの通信に、等しく採用されている。
【背景技術】
【０００３】
最も基本的な対称暗号化技術は、フロー暗号化として公知である、同一の長さの乱数列に１ビットずつ平文メッセージを加算することである。この技術は、長い擬似乱数列を生成するという本質的かつ困難な問題を提起する。
【０００４】
最も良く用いられるフロー暗号化方法では、ハードウェアを節約するために、線形フィードバックシフトレジスタを採用して、暗号化すべきメッセージと独立に生成した擬似乱数列を使用する。
【０００５】
線形フィードバックシフトレジスタの重大な欠点は、それらが線形であることである。実際に、レジスタの長さに等しい数の前記レジスタの出力ビットと、前記レジスタに関連付けたフィードバック多項式とを知ると、出力ビット及び前記レジスタの全ての後続状態が決定可能である。
【０００６】
それ故に、線形フィードバックシフトレジスタの線形性を「破る」ために、例えば非線形ブール関数を使用して、複数のレジスタからの出力と、おそらくは前記レジスタの内部状態とを組み合わせるのが標準的な慣習である。
【０００７】
図５は、この種の生成器１２１を示している。これはヨーロッパ特許公開公報０  ６１９  ６５９で説明されているとともに、第１線形フィードバックシフトレジスタ１２３ａと、第２線形フィードバックシフトレジスタ１２３ｂと、生成器１２１の出力を選択する手段１２５とを具備する縮小暗号生成器（ｓｈｒｉｎｋｉｎｇ  ｇｅｎｅｒａｔｏｒ）として公知である。
【０００８】
それぞれのシフトでは、２つのレジスタ１２３ａ及び１２３ｂは同時にシフトされるとともに、もし第１レジスタ１２３ａの出力が「１」ならば、装置１２１の出力は、第２レジスタ１２３ｂの出力と等しく、そうでなければ、ビットを出力しない。
【０００９】
縮小暗号生成器では、２つの線形フィードバックシフトレジスタの出力だけでなく、より一般的に、ビット列の任意の組を結合可能である。縮小暗号生成器は、１つの線形フィードバックシフトレジスタが、他のレジスタを制御するストリーム暗号化システムのクラスに属する。種々の利用レジスタの間と、２つの連続するビットの間との両方でシフト数を変化させることでレジスタの線形性を破るのが着想である。
【００１０】
自己縮小暗号生成器（ｓｅｌｆ−ｓｈｒｉｎｋｉｎｇ  ｇｅｎｅｒａｔｏｒ）として公知である縮小暗号生成器の変形例は、同一の原理をベースとするが、ただ１つのレジスタを使用する。前記レジスタの出力ビットを２つずつ読み込むとともに、もし第１ビットが「１」であればシステムの出力は第２ビットであり、そうでなければビットを出力しないように、第１ビットが第２ビットの出力を制御する。
【００１１】
線形フィードバックレジスタをただ１つ使用することは、多くの欠点を有する。重大な欠点は、装置の線形性から生ずる脆弱性である。もしブール関数を利用してレジスタを結合するならば、同様に不都合が生ずる。ハードウェアレベルでは、これらの不都合は関数実装の複雑度から生ずる。さらに、関数は固定されるとともに、攻撃に対して無防備である。
【００１２】
さらに、もし擬似乱数生成器で使用するシフトレジスタのフィードバックが通常のもの又は容易に予想可能なものであるならば、前記生成器は、代数的攻撃に対して脆弱である。
【００１３】
さらに、統計的な方法によって、縮小乱数生成器の特定の弱点が示されている。特に、縮小乱数生成器では、２つのレジスタによって行うシフトの数は２つの出力ビット間で変化するが、両レジスタでは同一の値を有する。
【発明の開示】
【課題を解決するための手段】
【００１４】
本発明は、初期データフローから擬似乱数データ列を生成する方法であり、
・完全プレフィクス符号を構成する符号語集合を定義する段階と、
・出力語集合を定義する段階と、
・前記出力語集合からの出力語に、前記完全プレフィクス符号の任意の符号語を関連付ける非同期化関数を定義する段階と、
・初期データフローを、前記完全プレフィクス符号に従って符号化した語の列に分解する段階と、
・前記擬似乱数データ列を構成するために、前記符号化した語の列の語を、前記非同期化関数に従って対応する出力語に関連付ける段階と、
を具備する方法を構成する。
【００１５】
このようにして、完全プレフィクス符号によって、初期データフローが一意的に分解可能となるとともに、有限オートマトンによって簡単に生成可能となる。さらに、この方法は実施が簡単であるとともに、擬似乱数データ列を生成する初期データフロー非同期化関数を使用する。実際に、完全プレフィクス符号及び「非同期化成分」を使用することにより、保証された最小ビット数を生成するので、代数的攻撃を防止し、また同時に代数的攻撃を事実上無力化する。
対照的に、たとえ擬似乱数列生成器内で非同期化成分として縮小乱数生成器を使用したとしても、最小の保証レートは事実上０となる。
【００１６】
前記非同期化関数は、擬似乱数データ列の生成の間に値が修正可能である所定パラメータに依存するパラメータ化された関数であるのが好ましい。
【００１７】
非同期化が修正可能な初期化パラメータに依存することにより、初期データフローと擬似乱数データ列との間の関係の複雑度が増加し、擬似乱数データ列を予測するのがより困難になる。
【００１８】
本発明の特徴によると、前記出力語集合は、各出力語に対して、相補的な出力語を具備する。
【００１９】
例えば、これによって、所与の出力語の長さに対して、出力語集合中の「０」と「１」との数がバランスされる。
【００２０】
前記完全プレフィクス符号の符号語は、上限ｈで制限された長さを具備するとともに、前記符号は、もし出力語ｘが他の出力語ｙと同一の長さであれば、前記非同期化関数による出力語ｘの逆像の数は、前記非同期化関数による出力語ｙの逆像の数と同一であるようなものが好ましい。
【００２１】
このことは、擬似乱数データ列に統計学的に良い性質を与える一方で、初期データフローの特定の性質に依存しない最小レートが保証される。特に、このことにより、生成された出力擬似乱数データ列のハミング重さは、初期データ列に関していかなる情報も提供しないことが確実になる。換言すると、出力列内の値「０」を有するビットと値「１」を有するビットとは、初期データ列に関する同一の情報量を具備する。
【００２２】
前記完全プレフィクス符号の語は、下限ｍによって制限された長さを具備するのが好ましいとともに、前記完全プレフィクス符号の語に対して上限長さｌがあり、前記上限長さｌより小さいまたは等しい任意の長さｋに対して、前記完全プレフィクス符号は、２ｍ−１個の長さｋの語を具備するのが好ましい。
【００２３】
このことは、前記擬似乱数データ列の確率分布を最適化することによって、上記の統計学的性質をさらに向上する。
【００２４】
前記方法の第１構成は、
・ｈ≧２として、完全プレフィクス符号を、次の形
【数１】
2008542805.tif 000003
を具備する符号語集合Ｃ１で定義することと、
・出力語集合を、２進集合Ｅ１＝｛０，１｝からの語で定義することと、
・パラメータ化された非同期化関数の所定パラメータｕは、ベクトル
【数２】
2008542805.tif 000004
であり、ここで前記ベクトルの成分は、集合｛０，１｝に属することと、
・前記パラメータ化された非同期化関数ｆｕを、次の
【数３】
2008542805.tif 000005
で定義することと、
を特徴とする。
【００２５】
この構成は、実施が比較的安価であるとともに、ハードウェア型暗号化を構成するのに使用可能であるのが好ましい。さらに、出力ビット数（即ち擬似乱数データ列のビット数）と、入力ビット数（即ち初期データフローのビット数）との間の比率が１／３より厳密に大きいとともに、長さｈの入力に対する出力ビット数の保証最小値は１である。
【００２６】
前記方法の他の実施構成は、 
・完全プレフィクス符号を、次の形
【数４】
2008542805.tif 000006
の２バイトから生成する符号語集合Ｃ２で定義することと、
・出力語集合を、集合
【数５】
2008542805.tif 000007
からの語で定義することと、
・前記パラメータ化された非同期化関数の所定パラメータνは、成分が集合｛０，１｝に属するベクトル
【数６】
2008542805.tif 000008
であり、最初の８個の成分の値
【数７】
2008542805.tif 000009
は不変であるとともに、最後の成分の値
【数８】
2008542805.tif 000010
は可変であることと、
・前記パラメータ化された非同期化関数
【数９】
2008542805.tif 000011
は、ｗ１ｗ２の形の任意の語に、
・もし、次の条件
【数１０】
2008542805.tif 000012
の１つが満たされるならば、語ｗ１を、
・もし、次の条件
【数１１】
2008542805.tif 000013
の１つが満たされるならば、語ｗ２を、
・もし、
【数１２】
2008542805.tif 000014
ならば空語εを、
関連付けることと、
を特徴とする。
【００２７】
この実施は、ソフトウェア型暗号化に使用しうるのが好ましい。さらに、出力バイト数と、入力バイト数との間の比率が１／３より厳密に大きいとともに、長さｈバイトの入力に対する出力バイト数の保証最小値は１である。
【００２８】
本発明は、初期データフローから擬似乱数データ列を生成する生成器において、メモリと処理ユニットとを具備し、前記メモリは完全プレフィクス符号を構成する符号語集合及び出力語集合を格納し、前記処理ユニットは、初期データフローを読み込むとともに、前記初期データフローを前記完全プレフィクス符号に従って符号化された語の列に分解するとともに、前記擬似乱数データ列を生成するために、非同期化関数に従って前記符号化された語の列の語を対応する出力語に関連付けることが可能であることを特徴とする生成器を構成する。
【００２９】
このようにして、この生成器は、初期データフローの特定の性質に依存しない、最小レートを具備する擬似乱数データ列を生成する。さらに、この生成器は、効果的であるのと同様、実施が容易であるとともに、コストが比較的少ない。
【００３０】
前記生成器は、前記非同期化関数を所定パラメータに依存させるとともに、擬似乱数データ列の生成の間に前記所定パラメータの値を修正するパラメータ化手段をさらに具備するのが好ましい。
【００３１】
このようにすると、前記初期化パラメータの値又は前記初期化パラメータが変更された時刻を知らなければ、前記擬似乱数データ列を予測するのがより困難になる。
【００３２】
本発明はまた、排他的論理和論理ゲートと、上記の特徴を具備する生成器とを具備する暗号化／暗号解除装置を構成する。
【００３３】
この装置は、線形複雑度の高い暗号化データ列を構成するために、擬似乱数データ列の各ビットを、２を法とする加法によって、暗号化すべきメッセージのデータ列の対応するビットに結合する簡単な方法を構成する。
【００３４】
本発明はまた、ネットワーク経由で接続された少なくとも２つの構成要素を具備し、前記少なくとも２つの構成要素は、それぞれ上記の特徴を有する暗号化／暗号解除装置を具備することを特徴とするセキュアなシステムを構成する。
【００３５】
このように、前記セキュアなシステムは、実施が簡単であると同時に、本質的に複雑な機構を有する構造を具備している。
【００３６】
本発明の他の特徴及び利点は、添付図面を参照するとともに、非限定的な実施例を通して以下で与えられる説明を読めば明らかになる。
【発明を実施するための最良の形態】
【００３７】
図１は、本発明による初期データフロー３から擬似乱数データ列１を生成する方法の図式化された実施例を図示している。
【００３８】
用語「語」（又はパターン）は、以下では、任意のアルファベット、例えば０及び１のみを具備する２進集合のアルファベットからの文字の有限列をいう。次いで、各語は、所与の長さを具備する。例えば、０，１１，０００，１０１０，００１１１は、それぞれ長さ１，２，３，４及び５を有する語である。さらに、「空」語εは、０の長さを有する語（即ちいかなる文字も具備しない語）である。
【００３９】
初期データフロー３は、高い「線形複雑度」を具備するデータ列に対応する。例えば、初期データフロー３は、最長周期線形フィードバックシフトレジスタを具備する初期生成手段２３（図３Ａを参照）で生成しても良い。
【００４０】
実際に、無限個の線形フィードバックシフトレジスタによって、任意の周期列を生成可能である。これらのレジスタの１つは、他の全てより短い。この最短レジスタの長さを、フローの「線形複雑度」と呼ぶ。もし、初期データ列の線形複雑度がＬならば、長さ２Ｌの初期データ列の部分列からレジスタの初期状態（及び、実際には全ての列）を再構成するために、Ｂｅｒｌｅｋａｍｐ−Ｍａｓｓｅｙアルゴリズムを使用可能である。
【００４１】
このように、セキュアな擬似乱数データ列を生成するために、初期データフロー３は、高い線形複雑度を具備することを推奨する。実際に、現時点では、公知の最良アルゴリズムは、もし初期データフロー３の線形複雑度Ｌが１６０よりも小さいならば、初期データフロー３を２８０よりも少ない操作で再構成可能である。従って、１６０よりも大きいか又は等しい線形複雑度Ｌを具備するように、初期データフロー３を取るのが好ましい。
【００４２】
本発明によると、符号語集合５ａは、「完全プレフィクス符号」５を構成するように定義する。
【００４３】
一般的な用語「符号」は、特定のアルファベット上の語の集合をいう。次いで、符号の性質を、問題のアルファベットと関連付けて考察する。
【００４４】
Ａを任意の固定したアルファベットとする。Ａからの文字で構成される語を考察するとともに、ＣでＡ上の符号を表すものとする。すると、
１）語ｘは、もしｗ＝ｘｙ（この表記は、ｘがｙと連結されていることを表す）となるようなｙが存在するならば、語ｗの「プレフィクス」と呼ばれる。もし、符号Ｃ内に、前記符号の他の語のプレフィクスとなる前期符号の語が存在しないならば、Ｃは「プレフィクス符号（ｐｒｅｆｉｘ  ｃｏｄｅ）」と呼ばれる。
２）もし語ｗがＣの語の連結である、換言すると、もしＣ内の語ｗ１，ｗ２，…、ｗｎでｗ＝ｗ１ｗ２…ｗｎと書くことが可能ならば、語ｗはＣによって符号化されたという。次いで、もし任意の語ｗに対して、語ｗ’が存在してｗｗ’がＣで符号化されるならば、Ｃは「完全（ｃｏｍｐｌｅｔｅ）」という。任意の語ｗに対して、語ｗ’及びＣに属する符号語ｕが存在し、ｕが語ｗｗ’のプレフィクスとなる、即ち語ｗ’及びＣに属する符号語ｕ及び語ｕ’が存在し、ｗｗ’がｕｕ’に等しくなる場合に限って、符号Ｃは完全であることを示すことが可能である。
【００４５】
もしＣがプレフィクス符号及び完全符号の両方であるならば、Ｃは完全プレフィクス符号であるという。
【００４６】
さらに、Ｅで表す出力語７ａの集合７は、Ｅが｛０，１｝ｋ及び｛ε｝の和集合に含まれるように定義するとともに、非同期化関数ｆは、完全プレフィクス符号５の任意の符号語５ａを、出力語集合７からの出力語７ａに関連付けるように定義する。
【００４７】
例えば、出力語集合７は、集合Ｅ＝｛ε，０，１｝又は、Ｅ＝｛０，１｝又は、Ｅ＝｛ε｝と｛０，１｝８ｋ（ｋ≧１、即ち複数バイト）との和集合である。特に、所与の出力語の長さに対して、出力語集合内の「０」と「１」との数をバランスさせるために、ｓで記す任意の出力語７ａに対して、
【数１３】
2008542805.tif 000015
で記す相補的な出力語７ａを具備する出力語集合７を選択するのが好ましい。
【００４８】
さらに、非同期化関数ｆは、評価が比較的低いコストで実施可能である（例えば２を法とするビット毎の加法のような）基本的な動作である。
【００４９】
このように、本発明の方法は、入力として、完全プレフィクス符号５  Ｃと、出力語集合７  Ｅと、非同期化関数ｆとを採用する。
【００５０】
さらに、本発明による方法は、初期データフロー３を、前記完全プレフィクス符号５に従って符号化された語の列１１に分解する分解動作１０を具備する。実際に、完全プレフィクス符号５の使用は、初期データフロー３の一意的な分解を構成する。
【００５１】
完全プレフィクス符号５は、所与の語ｗに対し、語ｗが完全プレフィクス符号５内にあるか否かを判定する有限オートマトンで認識可能であるのが好ましい。
【００５２】
実際に、図２Ａ，２Ｂは、初期データフロー３を、符号化された語の列１１に分解するための有限オートマトン１３ａ，１３ｂの２つの実施例を図式的に示している。有限オートマトンは、完全プレフィクス符号５の各語が、Ｉと記された初期状態１５と、Ｆと記された終了状態１５との間で、パス集合１７によって定義可能となるような、パス又は矢印１７で接続されたノード又は状態の集合１５を具備する。このようにすると、ビットを読み込むと、前記ビットの値に対応するパス１７を取るとともに、終了状態Ｆに到達すると、完全プレフィクス符号５の語の読み込みが丁度終了したことを知るとともに、初期状態Ｉに戻ることによって、次の語を読み込み可能となる。
【００５３】
図２Ａの実施例では、Ｃ＝｛１０＊１，０１＊０｝で定義する完全プレフィクス符号５の符号語を認識する。ここで、１０＊１（又は０１＊０）は、ｋを整数として１０ｋ１（又は０１ｋ０）の形の語の集合を表す。１００１は、語１１に対応するとともに、０１００は、語００に対応することに留意されたい。このように、この有限オートマトン１３ａは、初期データフロー３を、１０…０１，０１…１０，１１及び００の形の語を具備する符号化された語の列１１に分解する。
【００５４】
さらに、図２Ｂの実施例では、符号Ｃ＝｛１０ｈ＋１，０１ｈ＋１，１０ｋ１，０１ｋ０，ｋ≦ｈ｝によって定義する完全プレフィクス符号５の上限ｈによって制限された長さを有する符号語を認識する。
【００５５】
さらに、本発明による方法は、符号化された語の列１１の語に、擬似乱数データ列１を構成するために非同期化関数ｆに従って対応する出力語７ａを関連付ける関連付け動作２０を具備する。
【００５６】
このように、本発明の機構の応用は、入力列(即ち初期データフロー３)の、迅速な完全プレフィクス符号５の語の列１１への分解１０に関する。完全プレフィクス符号５の語を認識する毎に、非同期化関数ｆによる当該語の像が出力語を生成する。この機構は、初期データフロー３の入力列の最後のビットに到達するまで、又は、ユーザーが決定した停止条件が満たされるまで、繰り返される。
【００５７】
暗号化アプリケーションの環境では、機構（符号５、関数ｆ）のデータのいくつか又は全てを、暗号化システムの秘密データとしておくことが可能であるのが好ましいことに留意する。
【００５８】
非同期化関数ｆは、擬似乱数データ列１の生成の間に修正可能な所定パラメータの値に依存するパラメータ化された関数であるのが好ましい。次いで、このパラメータ化された関数は、出力語７の集合Ｅからの元を、長さｍの任意の２進ベクトルν、即ち｛０，１｝ｍの任意の元νと、完全プレフィクス符号５  Ｃの任意の語ｘとに関連付ける
【数１４】
2008542805.tif 000016
の形である。
【００５９】
本発明の方法は、次いで、初期データフロー３と２進ベクトルνとを入力として受け取る。ベクトルνの選択は、初期化ベクトルに（非線形）操作を適用した結果でも良い。もちろん、ベクトルνは、所定値（例えばνがヌルベクトル）を取っても良い。ベクトルνは、処理の間に修正可能であるとともに、従って擬似乱数データ列１の生成に依存可能であるのが好ましい。
【００６０】
このようにすると、このパラメータによって、初期データフロー３と擬似乱数データ列１との間の関係の複雑度が向上し、擬似乱数データ列１を予測するのがより困難になる。
【００６１】
さらに、初期データフロー３の特定の性質に依存しない最小レートを保証するために、完全プレフィクス符号５の符号語は、上限ｈによって制限される長さを具備するとともに、もし出力語ｓ１と他の出力語ｓ２とが同一の長さであるならば、非同期化関数ｆによる出力語ｓ１の逆像の数は、同一の関数ｆによる出力語ｓ２の逆像の数と同一であるのが好ましい。
【００６２】
換言すると、完全プレフィクス符号５は、次の好ましい性質を具備する。
・ある整数ｈが存在して、完全プレフィクス符号５  Ｃの語全てがｈよりも小さい又は等しい長さを具備する。
・任意の整数ｋに対し、任意の集合
【数１５】
2008542805.tif 000017
からの任意の組（ｓ１，ｓ２）に対して、集合
【数１６】
2008542805.tif 000018
及び
【数１７】
2008542805.tif 000019
内の長さｋの元の数は、それぞれ等しい。
【００６３】
さらに、このことによって、生成された出力擬似乱数データ列１のハミング重さ（即ち値「１」のビットの数）が、初期データ列３のいかなる情報も供給しないことが確実となる。換言すれば、前記出力擬似乱数データ列１内の値「０」を有するビットと値「１」を有するビットとが、初期データ列３の同一の情報量を具備する。
【００６４】
完全プレフィクス符号５の語は、下限ｍによって制限された長さを具備するのが好ましいとともに、前記完全プレフィクス符号の語のより大きな長さｌが存在して、前記より大きな長さｌよりも小さい又は等しい任意の長さｋに対して、完全プレフィクス符号は、２ｍ−１個の長さｋの語を具備するのが好ましい。換言すると、関連付け関数ｆνは、次の性質を満たす。ある整数ｍが存在して、符号Ｃの考えうる全ての語が、ｍより大きい又は等しい長さを有するとともに、さらに、ある整数ｌ≧ｍが存在して、ｍより大きい又は等しく、かつｌより小さい又は等しい任意の整数ｋに対し、符号
【数１８】
2008542805.tif 000020
は、丁度２ｍ−１個の長さｋの語を具備する。
【００６５】
このようにすると、初期データフロー３の一様な分布に伴い、中間レートは、オーダー１／（ｍ＋１）となる。特に、擬似乱数データ列の所与のビットに対して、前記所与のビットが何（０又は１）であろうが、当該ビットを生成した符号語が長さｋとなる確率は、ｋの逆数に比例する。この確率分布の選択は、擬似乱数データ列１が満たさなければならない統計的性質に関して最適である。
【００６６】
本発明の特定の第１実施形態で、集合
【数１９】
2008542805.tif 000021
によって定義する完全プレフィクス符号を考察する。ここで、
【数２０】
2008542805.tif 000022
は、和集合記号を表す。ｈは固定された整数（ｈ≧２）であるとともに、例えば、出力語集合は、２進集合Ｅ１＝｛０，１｝の語によって定義する。
【００６７】
さらに、成分が集合｛０，１｝に属するベクトル
【数２１】
2008542805.tif 000023
を定義する。前記パラメータ化された関数ｆｕを次のように定義する。
【００６８】
【数２２】
2008542805.tif 000024
【００６９】
この実施形態では、初期データフロー３は、１ビットずつ読み込むとともに、符号Ｃ１の任意の語ｘに対して、語ｘの第１ビットと、値ｎ（
【数２３】
2008542805.tif 000025
の形の語に対して）、又は固定された値ｈ−１（
【数２４】
2008542805.tif 000026
の形の語に対して）とを知って、値ｆｕ（ｘ）を計算する。
【００７０】
この第１実施形態の機構を説明するために、
【数２５】
2008542805.tif 000027
とし、
【数２６】
2008542805.tif 000028
とする。さらに、フラグは値０で初期化するとともに、符号Ｃ１の語を認識した後のみ値１を取る。前記フラグの値は、各語の認識後にリセットする。各語の認識に対して、現在の語の第１ビットを変数ｃに一時的に格納するとともに、前記語の長さを変数「ｌｅｎｇｔｈ」内で更新する。出力ビットの値は、変数ｓに格納する。
【００７１】
例えば、この第１実施形態は、次の機構の反復を具備する。
【数２７】
2008542805.tif 000029
【００７２】
この実施形態は、実施が比較的安価であるとともに、ハードウェア内の電子回路で暗号化を実施するのに使用可能であるのが好ましい。さらに、中間レート、即ち出力ビット数（擬似乱数データ列１のビット数）と入力ビット数（初期データフロー３のビット数）との比率が１／３より厳密に大きい。さらに、長さｈの入力に対する、出力ビットの保証最小数が１である。
【００７３】
本発明の特定の第２実施形態では、次の形
【数２８】
2008542805.tif 000030
の２バイトからなる符号語集合Ｃ２によって、完全プレフィクス符号５を定義するとともに、出力語集合は、集合
【数２９】
2008542805.tif 000031
からの語によって定義する。
【００７４】
さらに、成分が集合｛０，１｝に属するベクトル
【数３０】
2008542805.tif 000032
を、最初の８個の成分の値
【数３１】
2008542805.tif 000033
が不変になるとともに、最後の成分の値
【数３２】
2008542805.tif 000034
が可変になるように定義する。
【００７５】
さらに、前記パラメータ化された関数
【数３３】
2008542805.tif 000035
は、ｗ１ｗ２の形の任意の語に、
・もし、次の条件
【数３４】
2008542805.tif 000036
の１つが満たされるならばｗ１を、
・もし、次の条件
【数３５】
2008542805.tif 000037
の１つが満たされるならばｗ２を、
・もし、
【数３６】
2008542805.tif 000038
ならば空語εを、
関連付ける。
【００７６】
この第２実施形態の機構を説明するために、整数ｈをｈ≧１となるように設定するとともに、フラグを値０で初期化するとともに符号Ｃ２の語を認識した後にのみ値１をとるようにする。各語の認識に対して、読み込んだ最後のバイトを一時的に変数ｃに格納するとともに、語の長さを変数「ｌｅｎｇｔｈ」内で更新する。出力バイトの値は、変数ｓに格納する。２つのバイトｗ１及びｗ２の連結を、
【数３７】
2008542805.tif 000039
と記す。
【００７７】
例えば、この第２実施形態は、次の機構の反復を具備する。
【００７８】
【数３８】
2008542805.tif 000040
【００７９】
第２実施形態では、ソフトウェア型の暗号化を使用可能であるのが好ましい。さらに、中間レート、即ち出力バイト数と入力バイト数との比率は、１／３より厳密に大きいとともに、長さｈバイトの入力に対する出力バイトの保証最小数は１である。
【００８０】
図３Ａは、擬似乱数データ列１を生成する生成器２１の実施例を非常に図式的に図示している。
【００８１】
生成器２１は、初期データフロー３を生成する少なくとも１つの最長周期線形フィードバックシフトレジスタを具備する初期生成手段２３を具備する。最長周期Ｔの列内では、長さｋ（ただしＴ＝２ｋ−１）の全ての語又はパターンが少なくとも１度現れることは公知である。線形フィードバックシフトレジスタは、フィードバック多項式と呼ばれる多項式で表される線形組み合わせ（ｌｉｎｅａｒ  ｃｏｎｂｉｎａｔｉｏｎ）を具備する有限長のビット（レジスタ）の表である。各シフトでは、最大添字を有するビットをシフトアウトするとともに、他の全ビットを１添字分だけシフトするとともに、最小添え字を有するビットはシフト前の線形組み合わせの値を取る。
【００８２】
フィードバック多項式は、例えば、最長周期列を生成する線形フィードバックシフトレジスタに対応する原始多項式、又は、Ｐを原始多項式として、Ｑ＝（ｘ２＋１）Ｐの形の多項式であるのが好ましい。
【００８３】
さらに、生成器２１は、メモリ２５と処理ユニット２７とを具備する。メモリ２５は、完全プレフィクス符号５と出力語集合７とを構成する符号語集合を格納する。
【００８４】
処理ユニット２７は、初期データフロー３を読み込むとともに、初期データフロー３を、完全プレフィクス符号５に従って符号化された語の列１１に分解するとともに、当該符号化された語の列１１の語を、擬似乱数データ列を生成するために、非同期化関数ｆに従って対応する出力語に関連付ける。非同期化関数ｆは、出力語集合７からの出力語を、完全プレフィクス符号５の任意の符号語に関連付ける。
【００８５】
処理ユニット２７は、分解動作１０及び関連付け動作２０を同時に実行可能であることに留意する。このように、処理ユニット２７は、初期データフロー３を１ビットずつ読み込むとともに、完全プレフィクス符号５の語が発見される度に、非同期化関数９によって当該語の像を計算する。
【００８６】
それゆえ、生成器は、実施が簡単であるとともに、入力初期データフロー３を一意的な方法で分解する分解手段（メモリ２５及び処理ユニット２７）と、初期データフロー３の特定の性質に依存しないような、最小レートを具備する擬似乱数データ列を生成する非同期化手段（メモリ２５及び処理ユニット２７）とを具備する。
【００８７】
図３Ｂは、擬似乱数データ列１を生成する生成器２１の他の実施例を図示している。前記実施例は、パラメータ設定手段２９をさらに具備するという理由で、図３Ａの実施例とは異なる。パラメータ設定手段２９は、非同期化関数ｆを、所定パラメータに依存させるとともに、擬似乱数データ列１を生成する間に、当該パラメータの値を修正する。
【００８８】
図４は、インターネット，ＧＳＭ，ＵＭＴＳ，ＷｉＦｉ，ＵｌｔｒａＷｉｄｅＢａｎｄ等のタイプの通信ネットワーク３５を経由して相互接続された少なくとも２つの構成要素を具備するセキュアなシステム３０を示している。
【００８９】
この図は、通信ネットワーク３５を経由して第２構成要素３３ｂに接続した第１構成要素３３ａを示している。
【００９０】
第１構成要素３３ａ（又は第２構成要素３３ｂ）は、第１端末３７ａ（又は第２端末３７ｂ）と、第１暗号化／暗号解除装置３９ａ（又は第２暗号化／暗号解除装置３９ｂ）と、第１モデム４１ａ（又は第２モデム４１ｂ）とを具備し、モデム４１ａ及び４１ｂは、通信ネットワーク３５とのインターフェースになることが可能である任意の装置である。
【００９１】
第１及び第２暗号化／暗号解除装置３９ａ，３９ｂは、それぞれ、上記で説明したような擬似乱数データ列１を生成する生成器２１と、排他的論理和論理ゲート４３とを具備する。
【００９２】
各暗号化／暗号解除装置３９ａ，３９ｂは、メッセージを１ビットずつ暗号化又は暗号解除することでフロー暗号化又は暗号解除を行う。
【００９３】
この実施例によると、第１暗号化／暗号解除装置３９ａは、暗号化動作を行う。このように、暗号化列と呼ばれる擬似乱数データ列１は、排他的論理和ゲート４３で、第１端末３７ａによって送信される平文メッセージ４５の対応する箇所の各ビットと結合する。これによって、第１モデム４１ａが次いで第２構成要素３３ｂに送信する暗号化テキスト４７を生成する。このようにして、暗号化動作は、メッセージ４５の平文テキストに１ビットずつ暗号化列を加算することによって、暗号化テキスト４７を取得する。
【００９４】
第２暗号化／暗号解除装置３９ｂは、メッセージ４５の平文テキストを取得するために、第１構成要素３３ａによって送信された暗号化テキスト４７に、同一の暗号化列１を１ビットずつ加算することにより暗号解除動作を行う。従って、暗号化及び暗号解除動作は、同一である。
【図面の簡単な説明】
【００９５】
【図１】図１は、擬似乱数データ列を生成するための本発明の方法を高度に図式化した説明図である。
【図２Ａ】図２Ａは、本発明に従って初期データフローを符号化された語の列に分解するための有限オートマトンの実施例を図式的に示している。
【図２Ｂ】図２Ｂは、本発明に従って初期データフローを符号化された語の列に分解するための有限オートマトンの実施例を図式的に示している。
【図３Ａ】図３Ａは、本発明の擬似乱数データ列生成器の実施例を図式化して説明している。
【図３Ｂ】図３Ｂは、本発明の擬似乱数データ列生成器の実施例を図式化して説明している。
【図４】図４は、図３Ａ又は図３Ｂの生成器を具備するセキュアなシステムを示している。
【図５】図５は、従来技術の生成器を図式化した図である。
【符号の説明】
【００９６】
１  出力擬似乱数データ列
３  初期データフロー
５  完全プレフィクス符号
５ａ  符号語集合
７  出力語集合
７ａ  出力語
１０  分解動作
１１  符号化列
２０  関連付け動作
【図１】
2008542805.tif 000053
【図２Ａ】
2008542805.tif 000054
【図２Ｂ】
2008542805.tif 000055
【図３Ａ】
2008542805.tif 000056
【図３Ｂ】
2008542805.tif 000057
【図４】
2008542805.tif 000058
【図５】
2008542805.tif 000059
【国際調査報告】
2008542805.tif 000060
2008542805.tif 000061
2008542805.tif 000062
2008542805.tif 000063