擬似ランダムストリングを生成するための方法及びデバイス
本発明は、暗号化手順において使用されることを意図したカージナルの有限体Ｋに属する項の擬似ランダムストリングを生成する方法に関する。前記方法は、有限体Ｋに属するｎ個の変数を有するｍ個の多項式のシステム（Γ）の反復計算を具備している。本発明によれば、各反復において、これらのｍ個の多項式の係数は再生成される。本発明はまた、この方法を実行することを意図された擬似ランダムストリングジェネレータに関する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所定のアルファベットに属するシンボルの擬似ランダムストリングを生成することに関する。特に、そのストリングは、一部の暗号化手順に使用される。
【背景技術】
【０００２】
擬似ランダムストリングは、決定性的に(deterministically)生成されるが、少なくとも適度な時間（適度な時間の意味は、明らかに、目的とするアプリケーション、及び、利用可能な演算力にリンクされている。）内に、各シンボルがアルファベットから完全にランダムに選択されているシンボルのストリングから、区別することが不可能な１つのストリングである。実際に、通常、擬似ランダムストリングは、秘密のパラメータ（コンテクストによってシード又は鍵と呼ばれる）を用いた適切なアルゴリズムを初期化することによって生成され、かつ、初期化ベクトルと呼ばれる、秘密か、又は、秘密ではない追加的なパラメータを使用している。
【０００３】
上記のアルファベットは、バイナリセット｛０，１｝、即ち、０から９の数字のセット、又は、これらの数字、大文字、小文字を具備しているアルファベットのセットである。本発明のコンテクストでは、アルファベットのシンボルは、有限体(finite body)Ｋ、又は、カージナル
【０００４】
【数１】
【０００５】
のガロア体ＧＦ（ｑ）に属している。
【０００６】
擬似ランダムストリングの重要なアプリケーションは、ストリーム暗号化である。この技術は、アルファベット値を有するクリア｛ｘｉ｝（ｉによってインデックス化された）のデータストリングを、同じアルファベット値の他のストリング｛ｚｉ｝によって、暗号化する（暗号的な意味において）ために使用されている。なお、｛ｚｉ｝は、擬似ランダムジェネレータによって生成されたストリングであり、同様にアルファベット値を有する暗号化されたストリング｛ｙｉ｝を生成する。換言すれば、アルファベットの範囲内の内部構成ｙｉ＝ｘｉ＊ｚｉの法則が選択される。例えば、アルファベットがバイナリアルファベット｛０，１｝である場合、この内部法則は、排他的論理和演算子である。ストリーム暗号化はまた、データブロックを処理する暗号化方法に対立するものとして、データワードが１つずつ暗号化されるため、オンザフライ暗号化として既知である。ブロック暗号化に比べて、ストリーム暗号化は、転送遅延問題、及び、データ格納問題を低減する利点を有している。しかし、明らかに、クリアデータのデータレートと、少なくとも同じ程度に高速な擬似ランダムシンボルデータレートを必要としている。したがって、ストリーム暗号化に対するアプリケーションには、比較的速い擬似ランダムストリームジェネレータが確保されている。
【０００７】
ストリーム暗号化は、ＴＬＳ（Transport Layer Security：トランスポート層セキュリティ）インターネットエクスチェンジプロテクションプロトコル（The TLS Protocol, T. Dierks, C. Allen, version 1.0, RFC 2246, 1999年1月参照）において使用され、ＲＣ４アルゴリズム（Linear Statistical Weakness of Alleged RC4 Keystream Generator, J.D. Golic, Advances in Cryptology - EUROCRYPT’97予稿集、226〜238ページ、W. Fumy編集、Lecture Notes in Computer Science vol. 1233, Springer-Verlag参照）のうちの最も広く使用されたストリーム暗号化アルゴリズムの１つであり、かつ、無線チャネル通信量、及び、アルゴリズムを用いたＧＳＭシステムにおける信号暗号化では、その中で、最も広く使用されたのは、Ａ５／１アルゴリズム（Real Time Cryptanalysis of A5/1 on a PC, A. Biryukov, A. Shamir, D. Wanger, FSE2000予稿集、1〜18ページ、B. Schneier編集、Springer-Verlag, 2000年参照）である。
【０００８】
例えば、確率論的計算、及び、公開鍵認証暗号化プロトコルなどの擬似ランダムストリングの他の重要なアプリケーションがある。
【０００９】
例えば、上記のＡ５／１アルゴリズムなどの多数のカレント(current)ストリームアルゴリズムは、非線形関数を用いて可能な限り組み合わせられた、線形フィードバックレジスタによって生成された反復性(recurrent)線形ストリングを使用している（Le chiffrement a la volee（オンザフライ暗号化）, A. Canteaut, Pour la Science レビュー特別号、86〜87ページ、パリ、2002年7〜10月参照）。これらのアルゴリズムは、高速擬似ランダムストリングジェネレータに実装することができる。しかし、完全にランダムなストリングから生成された擬似ランダムストリングを区別することの実施の不可能性に関して、高く信頼することができる強固なセキュリティアーギュメントを欠くので、注意がそのセキュリティに関して必要とされている。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
仏国特許出願第０５-０６０４１号明細書は、暗号化手順に使用されることを意図したカージナル
【００１１】
【数２】
【００１２】
の有限体(finite body)Ｋに属する項(term)の擬似ランダムストリングのジェネレータを開示している。このジェネレータは、Ｋ要素の初期化ｎ組(n-tuple)の
【００１３】
【数３】
【００１４】
から、Ｋ（ここで、i=1,2, ...）要素のｎ組の
【００１５】
【数４】
【００１６】
と、及び／又は、ｍ組のY(i)とを反復して計算するための手段を具備している。各ｎ組のX(i)は、Ｋ要素のｍ組の
【００１７】
【数５】
【００１８】
から、所定の方法で得られるとともに、前記擬似ストリングの項は、ｎ組のX(i)から、所定の方法で抽出される。このジェネレータは、ｉが１又は２以上の値をとる場合、ｎ組のX(i-1)の構成要素に、係数Ｋを有する所定の二次式(quadratic form)を適用することによって、１又は２以上のｍ組のY(i)の構成要素
【００１９】
【数６】
【００２０】
（ここで、k=1, 2, ..., m）を取得するための手段をさらに具備していることに注目しなければならない。
【００２１】
この擬似ランダムジェネレータは、有限体上の二次式のシステムを解く問題に困難さがあれば、高いレベルのセキュリティを提供するアルゴリズムを使用する。複雑性理論の一般に許容された推測Ｐ≠ＮＰの検証を条件として、所定の候補がこのシステムの式の解であるか否かに関する検証を多項式を解く時間(polynomial time)内に実行することができるとしても、取り扱われる有限体Ｋが何であっても、この問題を解くには、多項式を解く時間以上を必要とすることを示すことができる（この種の問題はＮＰ困難問題と呼ばれている）。さらに、比較的大きくないサイズのｍ及びｎ（例えば、１００以上のK=GF(2)，ｍ，ｎ）を対象としても、ｍ及びｎの値が十分に近い場合、この問題のランダムインスタンスを解く既知の有効な方法は、現在、存在しない。
【００２２】
このようにして、仏国特許出願第０５-０６０４１号明細書に基づく擬似ランダムジェネレータが十分に効果的であり得るか否か、即ち、生成されたストリングの各シンボルのために必要な演算リソース（時間、メモリなど）が、予想される産業的なスケールのこの種のジェネレータの使用に対して、十分に小さい（少なくとも大きくないパラメータ値に対して、しかし、さらに難しいと考えられる、まさに言及された問題に対してやはり十分に高い）か否かを決定することに関する問題が生じる。
【００２３】
特に、必要とされる演算リソースに関するこの問題は、このタイプの擬似ランダムジェネレータを、配線論理チップなどの低コストの電子システムに統合することの可能性に関係している。配線電子論理回路は、トランジスタ（ＮＡＮＤゲート及びＮＯＲゲートの２つのタイプの論理ゲートを使用して、プログラムの全ての論理機能を設計することが可能である）から生成された論理ゲートで構成されている。したがって、論理回路を実装するのに必要とされる論理ゲートの数は、特に、回路のサイズ、その電流消費、そのコストを反映している。
【００２４】
したがって、仏国特許公開第０５-０６０４１号明細書の擬似ランダムジェネレータにおいて実行される計算に関して、より詳細を検討しなければならない。
【００２５】
ジェネレータは、反復ｉにおいて、ｎ個の変数
【００２６】
【数７】
【００２７】
（ここで、j=1, 2, ..., n）を有する少なくとも１つの変数
【００２８】
【数８】
【００２９】
（ここで、k=1, 2, ..., m）に関する１又は２以上の二次式を反復して呼び出す。したがって、この関係は、入力値のｎ組のX=(x1, x2, ..., xn)を、出力値のｍ組のY=(y1, y2, ..., ym)に結び付ける、特定の関数「Ｇ」を具備している。したがって、この関数Ｇは、有限体Ｋ上のｍ個の多変量二次多項式（即ち、ｎ個の変数x1〜xnを有する（ここで、n>1））のシステム（Ｇ）に一致している。したがって、これらの多項式は、次の形となる。なお、係数はＫに属し、かつ、量ykもＫに属している。
【００３０】
【数９】
【００３１】
この種のジェネレータを実行する従来の方法では、これらの係数の値はメモリに格納されることになり、かつ、ｍ個の多項式の値は各々反復して計算されることになる。したがって、m.N（Nが各多項式の項の数である）に等しい係数の合計数を格納することが必要になる。ｎ個の変数を有する二次多項式のため、項のこの番号Nが、
【００３２】
【数１０】
【００３３】
に等しいことを検証することは簡単なことである。
【００３４】
さらに、難しいと考えられる、Ｋ上のｎ個の未知数において、ｍ個の二次式のシステムを解くには、ｍ及びｎの値が十分に大きく、かつ、それらの桁数が十分に近いことが望ましい。故に、ｎの高い値、及び、ｎの値と同じ桁数のｍの値に対して、格納される係数の数は、ｎ３のオーダーである。例えば、ｎが概ね１００に等しい場合、約１００万の係数が格納されなければならない。
【００３５】
結果として、仏国特許出願第０５-０６０４１号明細書に基づく擬似ランダムジェネレータの従来の実装には、配線論理チップにそれを組み込むことを予測することができるように、非常に多数の電子ゲートを必要とする。より高い次数の多項式は、計算リソースのコストをやや増大して、ジェネレータをよりセキュアにさせる利点を有するが、その一部が２より高いグローバル次数を有している多変量多項式のシステムを使用して、配線論理チップに擬似ランダムジェネレータを挿入することを予想し得る可能性は、さらに低いことは言うまでもない。
【課題を解決するための手段】
【００３６】
したがって、本発明は、暗号化手順において使用されることを意図したカージナル
【００３７】
【数１１】
【００３８】
の有限体Ｋに属する項の擬似ランダムストリングのジェネレータであって、有限体Ｋに属したｎ個の変数を有するｍ個の多項式のシステム（Γ）を反復して計算するための手段を具備するジェネレータに関する。この擬似ランダムストリングジェネレータは、前記ｍ個の多項式の係数が各反復において再生成されることに注目しなければならない。
【００３９】
故に、本発明のジェネレータが機能するために必要とされるメモリサイズが非常に少なくてすむように、本発明は、少数のパラメータに基づき各反復において多項式の係数を生成する（例えば、再計算する）。
【００４０】
発明者は、素朴に期待されることに比べて、本発明がもたらす追加的な計算負荷は、全体の計算時間に対してほとんどインパクトがないことを真に理解している。比較的高い次数の多項式のための計算時間が比較的短いので、周知の通り、それらの多数が存在し、かつ、それらが多数の変数の関数であるとしても、本発明は、高速であり（かつ、したがって、例えば、ストリーム暗号化に使用することができる）、かつ、低コスト計算デバイスに非常に適した擬似ランダムジェネレータを生成する。なお、これらの利点は、上記の高度化されたセキュリティに追加されている。
【００４１】
高速が主たる要求であれば、システムを形成している各前記多項式の大部分は２次であることが好ましい。
【００４２】
特定の特徴によれば、擬似ランダムストリングジェネレータは、線形シフトレジスタの形態で、係数ジェネレータモジュールを具備している。
【００４３】
又は、係数ジェネレータモジュールは、非線形シフトレジスタ又は有限状態マシーンの形をとることができる。
【００４４】
これらの特徴の手段によって、小規模な電子メモリを使用して、大規模な数の係数を生成することができる。
【００４５】
特定の特徴によれば、所定のｎ組の変数(x1, x2, ..., xn)に対して、多項式がＤ以下の全てのグローバル次数であるシステム（Γ）のｍ個の多項式によって、得られたｍ組の値(y1, y2, ..., ym)を計算するには、ジェネレータは、
・次数Ｄのｎ個の変数を有する一般的な多項式の所定のセットの項の処理オーダーを選択する手段と、
・処理された項のため、同じオーダーにおいて、変数の単項式(mononomial)を計算し、次いで、連続的に、ｍ個の多項式のためにその項の係数を生成し、かつ、前記単項式によってその係数を多重化するとともに、前記項の値を取得する手段と
を具備している。
【００４６】
これらの特徴の手段によって、変数のための各ファクタは、ｍ回ではなく、１回だけ計算される。
【００４７】
関連する方法では、本発明は、暗号化手順において使用されることを意図したカージナル
【００４８】
【数１２】
【００４９】
の有限体Ｋに属する、項の擬似ランダムストリングを生成する方法であって、有限体Ｋに属したｎ個の変数を有するｍ個の多項式のシステム（Γ）を反復して計算する方法に関する。この擬似ランダムストリングを生成する方法は、ｍ個の多項式の係数が各反復において再生成されることに注目しなければならない。
【００５０】
特定の特徴によれば、各前記多項式の大部分は２次である。
【００５１】
特定の特徴によれば、所定のｎ組の変数(x1, x2, ..., xn)に対して、多項式がＤ以下の全てのグローバル次数であるシステム（Γ）のｍ個の多項式によって、得られたｍ組の値(y1, y2, ..., ym)を計算するには、方法は、
・次数Ｄのｎ個の変数を有する一般的な多項式の所定のセットの項のため、処理オーダーを選択するステップと、
・処理された項のため、同じオーダーにおいて、変数の単項式を計算し、次いで、連続的に、ｍ個の多項式のためにその項の係数を生成し、かつ、前記単項式によってその係数を多重化するとともに、前記項の値を取得するステップと
を具備している。
【００５２】
これらの方法の利点は、上に簡潔に記載された関連する擬似ランダムシーケンスジェネレータの利点と本質的に同じである。
【００５３】
本発明はまた、
・上に簡潔に記載された任意の擬似ランダムストリングジェネレータを具備している、特に配線論理チップの電子回路
・上に簡潔に記載された擬似ランダムストリングを生成する任意の方法のステップを実行するためのコンピュータプログラムコード命令を具備している、取り外し不可能なデータ格納手段
・上に簡潔に記載された擬似ランダムストリングを生成する任意の方法のステップを実行するためのコンピュータプログラムコード命令を含んでいる、一部又は全体を取り外し可能なデータ格納手段
・前記プログラムがプログラム可能なデータ処理デバイスを制御するとき、前記命令によって、前記データ処理デバイスに、上に簡潔に記載された擬似ランダムストリングを生成する任意の方法を実行させるような命令を含んでいるコンピュータプログラム
を目的とする。
【００５４】
この電子回路、これらのデータ格納手段、及び、このコンピュータプログラムの利点は、前記方法の利点と本質的に同じである。
【発明を実施するための最良の形態】
【００５５】
本発明の他の態様及び利点は、非限定的な実施例として提供された特定の実施形態に関する次の詳細な説明から明らかになる。説明は添付図面を参照している。
【００５６】
上記したように、本発明の擬似ランダムストリングジェネレータのセキュリティ（即ち、第１番目のｉ項からの出力においてストリングの(i+1)番目の項を計算する「ハッカー」に対する不可能性）は、有限体Ｋ上のｎ個の未知数において、ｍ個の式を解く問題の困難さに基づいている。
【００５７】
１実施形態では、仏国特許出願第０５-０６０４１号明細書（記載を単純化するため、「二次式」及び「二次多項式」の表現は、ある式、それぞれのある多項式が線形である場合も使用される。即ち、システムの少なくとも１つの式、それぞれの少なくとも１つの多項式が、実際に二次であることが理解される。）にあるように、これらの式は全て二次式であり得る。この問題は、次のように、正確に公式で表すことができる。
・式
【００５８】
【数１３】
【００５９】
の有限体Ｋに属しているｎ個の未知数x1〜xnにおいて、ｍ個の二次式のシステム（Γ）が与えられる。
ここで、係数
【００６０】
【数１４】
【００６１】
及びγkはＫに属し、かつ、数量ykもＫに属している。
・解X=(x1, x2, …, xn)を見つける。
「Γ」は、式（Γ）のシステムによって記載された関数であり、入力値のｎ組のX=(x1, x2, …, xn)は、出力値のｍ組のY=(y1, y2, …, ym)に関係している。
【００６２】
擬似ランダムジェネレータは、ｎ個の変数
【００６３】
【数１５】
【００６４】
（ここで、j=1, 2, ... , n）を有する少なくとも１つの変数
【００６５】
【数１６】
【００６６】
（ここで、k=1, 2, ... , m）に関係している１又は２以上の二次式を反復して呼び出す。上記したように、パラメータｑ，ｍ，ｎは次のように選択されることが好ましい。
・Ｋ上のｎ個の未知数において、ｍ個の二次式のシステムを解くことは、難しいと考えることができ、それは、ｍ及びｎの値が十分に高く、かつ、その桁数が十分に近い（例えば、qn及びqmの両方が２８０及び２４００の間）ことを必要とする。
・計算は効率的に行うことができ、それはｑ，ｍ，ｎの値が十分に小さい（例えば、ｑは１００より小さく、ｍ及びｎは数百より小さい）ことを必要とする。
【００６７】
さらに、本発明によれば、これらの二次式の係数は各反復において再生成される（例えば、再計算される）。
【００６８】
係数が０より大きいほど計算は速いことは明らかである。それにも拘らず、実際に不可能な式のシステムを解くためには、二次項（以下、記号で
【００６９】
【数１７】
【００７０】
と表す）の係数の十分な数が０ではないことに注意しなければならない。実行速度を上げるため、一部の式（しかし、明らかにそれらの全てではない）が全ての変数に対して線形であれば、（理論的に）式のシステムを解くことはより容易である事実を補うために、係数を生成する方法が秘密のままであることが推奨される。
【００７１】
擬似ランダムストリングを生成するための本発明の方法に関係する実施形態が図１に示されている。この実施形態では、各値ｉのため、ｍ組のY(i)の全ての構成要素は、ｎ組のX(i-1)の構成要素に、Ｋにおける係数を有する二次式を適用することによって計算される。
【００７２】
まず、初期化ステップ中にｎ組のX(0)が構成される。ジェネレータの意図された使用によって、X(0)は、パブリックシード、秘密鍵、初期化ベクトル、又は、これらの要素の組み合わせに依存する。なお、初期化ベクトルは、追加的なパラメータであって、一般に秘密ではなく、１回以上使用される同じ秘密鍵によって、多くのさまざまな擬似ランダムストリングを生成することを可能にする。
【００７３】
次いで、反復ステップは、初期状態X(0)から、及び、以下に記載された方法によって、ｔ組のＫ要素（ここで、ｔは１からｍの定数である）からなる擬似ランダムストリングZ(i)（ここで、i=1, 2, ...）を生成するよう実行される。例えば、反復の合計数は、１から２５０の間である。
【００７４】
ｉ回目の反復では、ｎ組のＫ要素を構成する現在状態X(i-1)は、次のサブステップを実行するための入力値として取り込まれる。
１）Ｋ値のｍ組のY(i)は、上に定義された関数Γ、即ち、Y(i)=Γ(X(i-1))を使用して、X(i-1)から差し引かれる。
２）出力値Z(i)は、ペア(X(i-1), Y(i))に、選択された出力関数S、即ち、Z(i)=S(X(i-1), Y(i))を、適用することによって取得される。
３）ｎ組のＫ値を構成する新しい現在状態X(i)は、ペア(X(i-1), Y(i))に、選択されたフィードバック関数F、即ち、X(i)=F(X(i-1), Y(i))を適用することによって取得される。
【００７５】
この方法は、図１（２つの連続的な反復を対象とする）に、逐次的な方法で示されているが、同様に、ループ方法で十分に示すことができる。ここで注目する重要な点は、方法の連続的なステップを１つの電子回路によって実行することができることである。
【００７６】
上に参照されたフィードバック関数F及び出力関数Sのための可能な選択の実施例に関しては、仏国特許出願第０５-０６０４１号明細書を参照されたい。また、少なくともストリングZ(i)に基づく、出力におけるシンボル（例えば、バイナリシンボル）の種々の擬似ランダムストリングを構成するための手段の実施例に関するアプリケーションを参照されたい。
【００７７】
図２は、本発明の擬似ランダムストリングジェネレータの１実施形態を示すブロック図である。このジェネレータは次のモジュールを具備している。
・計算される多項式のシステムの入力変数の値を格納するためのメモリ（１００）
・計算の終了時に、計算される１又は２以上の多項式によって得られた値を格納し、かつ、同時に、中間値格納ユニットとして機能するためのメモリ（５００）
・計算される多項式のシステムに関係した、多様な単項式の値を生成する（所定のオーダーで）ためのモジュール（２００）であって、自身のメモリを選択的に有する単項式ジェネレータモジュール（２００）
・計算される多項式のシステムを定義する、係数のシーケンスを生成するためのモジュール（３００）であって、自身のメモリを有するモジュール（３００）
・係数、及び、単項式の値を多重化して、多項式の値を格納しているメモリ（５００）を更新するための組み合わせモジュール（４００）
【００７８】
上の係数ジェネレータモジュール（３００）の１つの特に有利な実施形態は以下に説明されるとおりである。
【００７９】
本発明の擬似ランダムジェネレータの正しい機能にとって、各反復において同じ関数Γを適用することは必ずしも必要ではないことに注意されたい。換言すれば、便利性を証明する場合、ｍ個の多項式の各係数の値が、１つの反復から他の反復に変化することを妨げることはない。本実施形態は、これをうまく使用している。
【００８０】
係数ジェネレータモジュール（３００）の第１実施形態は、線形フィードバックシフトレジスタ（ＬＦＳＲ）の形をとる。
【００８１】
ＬＦＳＲは、メモリal内に格納された値を除き、各メモリai内に格納された値をメモリai+1内に格納された値に置き換えることによって、各クロックパルスにおいてリフレッシュされた、１セットのｌメモリa1, a2, …, alを具備している。なお、それは、前のクロックパルスにおいて、多様なメモリ内に格納された値の所定の線形組み合わせによって置き換えられる。
【００８２】
線形シフトレジスタからの出力ビットは、従来、擬似ランダムビットストリングとして使用される。好ましくは、本発明によれば、ＬＦＳＲ出力データは、出力値Z(i)を直接生成するのではなく、ｍ個の多項式の係数を生成することに使用される。ＬＦＳＲは、メモリ内のｒビットだけから、ｒ個の論理ゲートのオーダーだけを含んでいる電子回路を使用して、長さ（２ｒ−１）の擬似ランダムストリングを生成する。
【００８３】
例えば、バイナリ体GF(2)上に、ｎ＝８０個の変数を有するとともに、ｍ＝８０個の多変量多項式を有する式（Γ）のシステムでは、ナイーブ(naive)実装の２５９２００ビットよりもむしろ、ｒ＝１８ビットを有する線形シフトレジスタから、
【００８４】
【数１８】
【００８５】
個のシステムの係数を生成することができる。
【００８６】
第２実施形態では、係数ジェネレータモジュール（３００）は、非線形フィードバックシフトレジスタ（ＮＬＦＳＲ）の形をとる。線形フィードバックシフトレジスタに比べて、これは、電子ゲートの数の形態で追加的コストをほとんど伴わないが、ジェネレータの出力において生成された項のストリングのランダム特性を顕著に改善する。
【００８７】
第３実施形態では、係数ジェネレータモジュール（３００）は、
・各クロックパルスにおいて更新されたメモリ
・メモリを更新するための回路
・メモリ内に格納されたデータを拡張するための拡張回路
を具備している有限状態マシーン(finite state machine)の形をとる。
【００８８】
メモリ内のｇビットからｆビット（ここで、ｆ＞ｇ）を生成するように適合された回路を「拡張回路」という表現で呼ぶ。例えば、ｆがｈの倍数である場合、ｆビットのセットは、各ｈビットのサブセットに分割することができ、その後、各ｈビットのこれらのサブセットがストリング混合器を通過し、かつ、生成されたビットのストリングが最終的に連結される。
【００８９】
有限状態マシーンでは、全てのメモリの値（拡張の前）が各クロックパルスにおいてリフレッシュされ、これに反して、シフトレジスタでは、メモリ内の１つの値だけが各クロックパルスにおいてリフレッシュされる。したがって、有限状態マシーンは、シフトレジスタに比べてより高速な計算を実行するが、電子ゲートの数にいくらかのコストを増す。
【００９０】
上の実施形態は、やはり、迅速に、かつ、少数の電子ゲートを使用して、各反復において、式（Γ）のシステムの係数を生成する。
【００９１】
単項式の値のジェネレータモジュール（２００）の異なる実施形態を予想することもできる。記述を単純化するため（xixjのタイプの（ここで、i及びjは１からｎに変化する。））、二次項の計算だけがここでは取り扱われる。
【００９２】
「ナイーブ」実装は変数の全てのペアを順々に検討する。したがって、計算はｎ２のクロックパルスを必要とする。
【００９３】
しかし、代わりに、単項式は次のように計算することができる。変数（x1, x2, ... , xn）の値の現在ストリングの２つのコピーがメモリ内に配置される。はじめに、「フェーシング(facing)」項を計算して、ｎ個の２乗
【００９４】
【数１９】
【００９５】
を生成する。次いで、１つの位置による循環配列は、変数（x1, x2, ... , xn）の値のストリングの１つに適用される。再び、「フェーシング」項を計算して、ｎ個の積x1x2, x2x3, ..., xnx1を生成する。ｎ×ｎの単項式を計算するこのプロセスは、ｎ２個の積が取得されるまで継続される。可換の乗算の最後には、ｎ／２クロックパルスだけ必要とされるが、このデバイスは、「ナイーブ」実装の２倍のメモリを必要とする。
【００９６】
最後に、モジュール（３００）における係数の生成と、モジュール（２００）における単項式の生成とを組み合わせて、次の項に移る前に、全ての多項式のために「並行して」同じタイプの各項を計算することによって、速度を上げ、かつ、メモリ容量を節約することができる。例えば、二次多項式のシステムでは、対応する変数（タイプxixj, xj又は１のそれぞれ）のために対応する単項式が計算され、その後、連続したｍ個の多項式のため、この項（各タイプ
【００９７】
【数２０】
【００９８】
又はγk）の係数が生成され、次いで、前記単項式によって多重化され、前記項の値を取得する。
【図面の簡単な説明】
【００９９】
【図１】図１は、擬似ランダムストリングを生成するための本発明の１実施形態に関する方法を示しているブロック図である。
【図２】図２は、本発明の１実施形態の擬似ランダムジェネレータを示しているブロック図である。
【符号の説明】
【０１００】
Ｘｉ−１，Ｘｉ，Ｘｉ＋１ 変数
Ｙｉ，Ｙｉ＋１ 変数
Ｚｉ，Ｚｉ＋１ 擬似ランダムストリング
Ｆ フィードバック関数
Γ 関数
Ｓ 出力関数
１００ メモリ
２００ モジュール
３００ モジュール
４００ 組み合わせモジュール
５００ メモリ
【技術分野】
【０００１】
本発明は、所定のアルファベットに属するシンボルの擬似ランダムストリングを生成することに関する。特に、そのストリングは、一部の暗号化手順に使用される。
【背景技術】
【０００２】
擬似ランダムストリングは、決定性的に(deterministically)生成されるが、少なくとも適度な時間（適度な時間の意味は、明らかに、目的とするアプリケーション、及び、利用可能な演算力にリンクされている。）内に、各シンボルがアルファベットから完全にランダムに選択されているシンボルのストリングから、区別することが不可能な１つのストリングである。実際に、通常、擬似ランダムストリングは、秘密のパラメータ（コンテクストによってシード又は鍵と呼ばれる）を用いた適切なアルゴリズムを初期化することによって生成され、かつ、初期化ベクトルと呼ばれる、秘密か、又は、秘密ではない追加的なパラメータを使用している。
【０００３】
上記のアルファベットは、バイナリセット｛０，１｝、即ち、０から９の数字のセット、又は、これらの数字、大文字、小文字を具備しているアルファベットのセットである。本発明のコンテクストでは、アルファベットのシンボルは、有限体(finite body)Ｋ、又は、カージナル
【０００４】
【数１】
【０００５】
のガロア体ＧＦ（ｑ）に属している。
【０００６】
擬似ランダムストリングの重要なアプリケーションは、ストリーム暗号化である。この技術は、アルファベット値を有するクリア｛ｘｉ｝（ｉによってインデックス化された）のデータストリングを、同じアルファベット値の他のストリング｛ｚｉ｝によって、暗号化する（暗号的な意味において）ために使用されている。なお、｛ｚｉ｝は、擬似ランダムジェネレータによって生成されたストリングであり、同様にアルファベット値を有する暗号化されたストリング｛ｙｉ｝を生成する。換言すれば、アルファベットの範囲内の内部構成ｙｉ＝ｘｉ＊ｚｉの法則が選択される。例えば、アルファベットがバイナリアルファベット｛０，１｝である場合、この内部法則は、排他的論理和演算子である。ストリーム暗号化はまた、データブロックを処理する暗号化方法に対立するものとして、データワードが１つずつ暗号化されるため、オンザフライ暗号化として既知である。ブロック暗号化に比べて、ストリーム暗号化は、転送遅延問題、及び、データ格納問題を低減する利点を有している。しかし、明らかに、クリアデータのデータレートと、少なくとも同じ程度に高速な擬似ランダムシンボルデータレートを必要としている。したがって、ストリーム暗号化に対するアプリケーションには、比較的速い擬似ランダムストリームジェネレータが確保されている。
【０００７】
ストリーム暗号化は、ＴＬＳ（Transport Layer Security：トランスポート層セキュリティ）インターネットエクスチェンジプロテクションプロトコル（The TLS Protocol, T. Dierks, C. Allen, version 1.0, RFC 2246, 1999年1月参照）において使用され、ＲＣ４アルゴリズム（Linear Statistical Weakness of Alleged RC4 Keystream Generator, J.D. Golic, Advances in Cryptology - EUROCRYPT’97予稿集、226〜238ページ、W. Fumy編集、Lecture Notes in Computer Science vol. 1233, Springer-Verlag参照）のうちの最も広く使用されたストリーム暗号化アルゴリズムの１つであり、かつ、無線チャネル通信量、及び、アルゴリズムを用いたＧＳＭシステムにおける信号暗号化では、その中で、最も広く使用されたのは、Ａ５／１アルゴリズム（Real Time Cryptanalysis of A5/1 on a PC, A. Biryukov, A. Shamir, D. Wanger, FSE2000予稿集、1〜18ページ、B. Schneier編集、Springer-Verlag, 2000年参照）である。
【０００８】
例えば、確率論的計算、及び、公開鍵認証暗号化プロトコルなどの擬似ランダムストリングの他の重要なアプリケーションがある。
【０００９】
例えば、上記のＡ５／１アルゴリズムなどの多数のカレント(current)ストリームアルゴリズムは、非線形関数を用いて可能な限り組み合わせられた、線形フィードバックレジスタによって生成された反復性(recurrent)線形ストリングを使用している（Le chiffrement a la volee（オンザフライ暗号化）, A. Canteaut, Pour la Science レビュー特別号、86〜87ページ、パリ、2002年7〜10月参照）。これらのアルゴリズムは、高速擬似ランダムストリングジェネレータに実装することができる。しかし、完全にランダムなストリングから生成された擬似ランダムストリングを区別することの実施の不可能性に関して、高く信頼することができる強固なセキュリティアーギュメントを欠くので、注意がそのセキュリティに関して必要とされている。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
仏国特許出願第０５-０６０４１号明細書は、暗号化手順に使用されることを意図したカージナル
【００１１】
【数２】
【００１２】
の有限体(finite body)Ｋに属する項(term)の擬似ランダムストリングのジェネレータを開示している。このジェネレータは、Ｋ要素の初期化ｎ組(n-tuple)の
【００１３】
【数３】
【００１４】
から、Ｋ（ここで、i=1,2, ...）要素のｎ組の
【００１５】
【数４】
【００１６】
と、及び／又は、ｍ組のY(i)とを反復して計算するための手段を具備している。各ｎ組のX(i)は、Ｋ要素のｍ組の
【００１７】
【数５】
【００１８】
から、所定の方法で得られるとともに、前記擬似ストリングの項は、ｎ組のX(i)から、所定の方法で抽出される。このジェネレータは、ｉが１又は２以上の値をとる場合、ｎ組のX(i-1)の構成要素に、係数Ｋを有する所定の二次式(quadratic form)を適用することによって、１又は２以上のｍ組のY(i)の構成要素
【００１９】
【数６】
【００２０】
（ここで、k=1, 2, ..., m）を取得するための手段をさらに具備していることに注目しなければならない。
【００２１】
この擬似ランダムジェネレータは、有限体上の二次式のシステムを解く問題に困難さがあれば、高いレベルのセキュリティを提供するアルゴリズムを使用する。複雑性理論の一般に許容された推測Ｐ≠ＮＰの検証を条件として、所定の候補がこのシステムの式の解であるか否かに関する検証を多項式を解く時間(polynomial time)内に実行することができるとしても、取り扱われる有限体Ｋが何であっても、この問題を解くには、多項式を解く時間以上を必要とすることを示すことができる（この種の問題はＮＰ困難問題と呼ばれている）。さらに、比較的大きくないサイズのｍ及びｎ（例えば、１００以上のK=GF(2)，ｍ，ｎ）を対象としても、ｍ及びｎの値が十分に近い場合、この問題のランダムインスタンスを解く既知の有効な方法は、現在、存在しない。
【００２２】
このようにして、仏国特許出願第０５-０６０４１号明細書に基づく擬似ランダムジェネレータが十分に効果的であり得るか否か、即ち、生成されたストリングの各シンボルのために必要な演算リソース（時間、メモリなど）が、予想される産業的なスケールのこの種のジェネレータの使用に対して、十分に小さい（少なくとも大きくないパラメータ値に対して、しかし、さらに難しいと考えられる、まさに言及された問題に対してやはり十分に高い）か否かを決定することに関する問題が生じる。
【００２３】
特に、必要とされる演算リソースに関するこの問題は、このタイプの擬似ランダムジェネレータを、配線論理チップなどの低コストの電子システムに統合することの可能性に関係している。配線電子論理回路は、トランジスタ（ＮＡＮＤゲート及びＮＯＲゲートの２つのタイプの論理ゲートを使用して、プログラムの全ての論理機能を設計することが可能である）から生成された論理ゲートで構成されている。したがって、論理回路を実装するのに必要とされる論理ゲートの数は、特に、回路のサイズ、その電流消費、そのコストを反映している。
【００２４】
したがって、仏国特許公開第０５-０６０４１号明細書の擬似ランダムジェネレータにおいて実行される計算に関して、より詳細を検討しなければならない。
【００２５】
ジェネレータは、反復ｉにおいて、ｎ個の変数
【００２６】
【数７】
【００２７】
（ここで、j=1, 2, ..., n）を有する少なくとも１つの変数
【００２８】
【数８】
【００２９】
（ここで、k=1, 2, ..., m）に関する１又は２以上の二次式を反復して呼び出す。したがって、この関係は、入力値のｎ組のX=(x1, x2, ..., xn)を、出力値のｍ組のY=(y1, y2, ..., ym)に結び付ける、特定の関数「Ｇ」を具備している。したがって、この関数Ｇは、有限体Ｋ上のｍ個の多変量二次多項式（即ち、ｎ個の変数x1〜xnを有する（ここで、n>1））のシステム（Ｇ）に一致している。したがって、これらの多項式は、次の形となる。なお、係数はＫに属し、かつ、量ykもＫに属している。
【００３０】
【数９】
【００３１】
この種のジェネレータを実行する従来の方法では、これらの係数の値はメモリに格納されることになり、かつ、ｍ個の多項式の値は各々反復して計算されることになる。したがって、m.N（Nが各多項式の項の数である）に等しい係数の合計数を格納することが必要になる。ｎ個の変数を有する二次多項式のため、項のこの番号Nが、
【００３２】
【数１０】
【００３３】
に等しいことを検証することは簡単なことである。
【００３４】
さらに、難しいと考えられる、Ｋ上のｎ個の未知数において、ｍ個の二次式のシステムを解くには、ｍ及びｎの値が十分に大きく、かつ、それらの桁数が十分に近いことが望ましい。故に、ｎの高い値、及び、ｎの値と同じ桁数のｍの値に対して、格納される係数の数は、ｎ３のオーダーである。例えば、ｎが概ね１００に等しい場合、約１００万の係数が格納されなければならない。
【００３５】
結果として、仏国特許出願第０５-０６０４１号明細書に基づく擬似ランダムジェネレータの従来の実装には、配線論理チップにそれを組み込むことを予測することができるように、非常に多数の電子ゲートを必要とする。より高い次数の多項式は、計算リソースのコストをやや増大して、ジェネレータをよりセキュアにさせる利点を有するが、その一部が２より高いグローバル次数を有している多変量多項式のシステムを使用して、配線論理チップに擬似ランダムジェネレータを挿入することを予想し得る可能性は、さらに低いことは言うまでもない。
【課題を解決するための手段】
【００３６】
したがって、本発明は、暗号化手順において使用されることを意図したカージナル
【００３７】
【数１１】
【００３８】
の有限体Ｋに属する項の擬似ランダムストリングのジェネレータであって、有限体Ｋに属したｎ個の変数を有するｍ個の多項式のシステム（Γ）を反復して計算するための手段を具備するジェネレータに関する。この擬似ランダムストリングジェネレータは、前記ｍ個の多項式の係数が各反復において再生成されることに注目しなければならない。
【００３９】
故に、本発明のジェネレータが機能するために必要とされるメモリサイズが非常に少なくてすむように、本発明は、少数のパラメータに基づき各反復において多項式の係数を生成する（例えば、再計算する）。
【００４０】
発明者は、素朴に期待されることに比べて、本発明がもたらす追加的な計算負荷は、全体の計算時間に対してほとんどインパクトがないことを真に理解している。比較的高い次数の多項式のための計算時間が比較的短いので、周知の通り、それらの多数が存在し、かつ、それらが多数の変数の関数であるとしても、本発明は、高速であり（かつ、したがって、例えば、ストリーム暗号化に使用することができる）、かつ、低コスト計算デバイスに非常に適した擬似ランダムジェネレータを生成する。なお、これらの利点は、上記の高度化されたセキュリティに追加されている。
【００４１】
高速が主たる要求であれば、システムを形成している各前記多項式の大部分は２次であることが好ましい。
【００４２】
特定の特徴によれば、擬似ランダムストリングジェネレータは、線形シフトレジスタの形態で、係数ジェネレータモジュールを具備している。
【００４３】
又は、係数ジェネレータモジュールは、非線形シフトレジスタ又は有限状態マシーンの形をとることができる。
【００４４】
これらの特徴の手段によって、小規模な電子メモリを使用して、大規模な数の係数を生成することができる。
【００４５】
特定の特徴によれば、所定のｎ組の変数(x1, x2, ..., xn)に対して、多項式がＤ以下の全てのグローバル次数であるシステム（Γ）のｍ個の多項式によって、得られたｍ組の値(y1, y2, ..., ym)を計算するには、ジェネレータは、
・次数Ｄのｎ個の変数を有する一般的な多項式の所定のセットの項の処理オーダーを選択する手段と、
・処理された項のため、同じオーダーにおいて、変数の単項式(mononomial)を計算し、次いで、連続的に、ｍ個の多項式のためにその項の係数を生成し、かつ、前記単項式によってその係数を多重化するとともに、前記項の値を取得する手段と
を具備している。
【００４６】
これらの特徴の手段によって、変数のための各ファクタは、ｍ回ではなく、１回だけ計算される。
【００４７】
関連する方法では、本発明は、暗号化手順において使用されることを意図したカージナル
【００４８】
【数１２】
【００４９】
の有限体Ｋに属する、項の擬似ランダムストリングを生成する方法であって、有限体Ｋに属したｎ個の変数を有するｍ個の多項式のシステム（Γ）を反復して計算する方法に関する。この擬似ランダムストリングを生成する方法は、ｍ個の多項式の係数が各反復において再生成されることに注目しなければならない。
【００５０】
特定の特徴によれば、各前記多項式の大部分は２次である。
【００５１】
特定の特徴によれば、所定のｎ組の変数(x1, x2, ..., xn)に対して、多項式がＤ以下の全てのグローバル次数であるシステム（Γ）のｍ個の多項式によって、得られたｍ組の値(y1, y2, ..., ym)を計算するには、方法は、
・次数Ｄのｎ個の変数を有する一般的な多項式の所定のセットの項のため、処理オーダーを選択するステップと、
・処理された項のため、同じオーダーにおいて、変数の単項式を計算し、次いで、連続的に、ｍ個の多項式のためにその項の係数を生成し、かつ、前記単項式によってその係数を多重化するとともに、前記項の値を取得するステップと
を具備している。
【００５２】
これらの方法の利点は、上に簡潔に記載された関連する擬似ランダムシーケンスジェネレータの利点と本質的に同じである。
【００５３】
本発明はまた、
・上に簡潔に記載された任意の擬似ランダムストリングジェネレータを具備している、特に配線論理チップの電子回路
・上に簡潔に記載された擬似ランダムストリングを生成する任意の方法のステップを実行するためのコンピュータプログラムコード命令を具備している、取り外し不可能なデータ格納手段
・上に簡潔に記載された擬似ランダムストリングを生成する任意の方法のステップを実行するためのコンピュータプログラムコード命令を含んでいる、一部又は全体を取り外し可能なデータ格納手段
・前記プログラムがプログラム可能なデータ処理デバイスを制御するとき、前記命令によって、前記データ処理デバイスに、上に簡潔に記載された擬似ランダムストリングを生成する任意の方法を実行させるような命令を含んでいるコンピュータプログラム
を目的とする。
【００５４】
この電子回路、これらのデータ格納手段、及び、このコンピュータプログラムの利点は、前記方法の利点と本質的に同じである。
【発明を実施するための最良の形態】
【００５５】
本発明の他の態様及び利点は、非限定的な実施例として提供された特定の実施形態に関する次の詳細な説明から明らかになる。説明は添付図面を参照している。
【００５６】
上記したように、本発明の擬似ランダムストリングジェネレータのセキュリティ（即ち、第１番目のｉ項からの出力においてストリングの(i+1)番目の項を計算する「ハッカー」に対する不可能性）は、有限体Ｋ上のｎ個の未知数において、ｍ個の式を解く問題の困難さに基づいている。
【００５７】
１実施形態では、仏国特許出願第０５-０６０４１号明細書（記載を単純化するため、「二次式」及び「二次多項式」の表現は、ある式、それぞれのある多項式が線形である場合も使用される。即ち、システムの少なくとも１つの式、それぞれの少なくとも１つの多項式が、実際に二次であることが理解される。）にあるように、これらの式は全て二次式であり得る。この問題は、次のように、正確に公式で表すことができる。
・式
【００５８】
【数１３】
【００５９】
の有限体Ｋに属しているｎ個の未知数x1〜xnにおいて、ｍ個の二次式のシステム（Γ）が与えられる。
ここで、係数
【００６０】
【数１４】
【００６１】
及びγkはＫに属し、かつ、数量ykもＫに属している。
・解X=(x1, x2, …, xn)を見つける。
「Γ」は、式（Γ）のシステムによって記載された関数であり、入力値のｎ組のX=(x1, x2, …, xn)は、出力値のｍ組のY=(y1, y2, …, ym)に関係している。
【００６２】
擬似ランダムジェネレータは、ｎ個の変数
【００６３】
【数１５】
【００６４】
（ここで、j=1, 2, ... , n）を有する少なくとも１つの変数
【００６５】
【数１６】
【００６６】
（ここで、k=1, 2, ... , m）に関係している１又は２以上の二次式を反復して呼び出す。上記したように、パラメータｑ，ｍ，ｎは次のように選択されることが好ましい。
・Ｋ上のｎ個の未知数において、ｍ個の二次式のシステムを解くことは、難しいと考えることができ、それは、ｍ及びｎの値が十分に高く、かつ、その桁数が十分に近い（例えば、qn及びqmの両方が２８０及び２４００の間）ことを必要とする。
・計算は効率的に行うことができ、それはｑ，ｍ，ｎの値が十分に小さい（例えば、ｑは１００より小さく、ｍ及びｎは数百より小さい）ことを必要とする。
【００６７】
さらに、本発明によれば、これらの二次式の係数は各反復において再生成される（例えば、再計算される）。
【００６８】
係数が０より大きいほど計算は速いことは明らかである。それにも拘らず、実際に不可能な式のシステムを解くためには、二次項（以下、記号で
【００６９】
【数１７】
【００７０】
と表す）の係数の十分な数が０ではないことに注意しなければならない。実行速度を上げるため、一部の式（しかし、明らかにそれらの全てではない）が全ての変数に対して線形であれば、（理論的に）式のシステムを解くことはより容易である事実を補うために、係数を生成する方法が秘密のままであることが推奨される。
【００７１】
擬似ランダムストリングを生成するための本発明の方法に関係する実施形態が図１に示されている。この実施形態では、各値ｉのため、ｍ組のY(i)の全ての構成要素は、ｎ組のX(i-1)の構成要素に、Ｋにおける係数を有する二次式を適用することによって計算される。
【００７２】
まず、初期化ステップ中にｎ組のX(0)が構成される。ジェネレータの意図された使用によって、X(0)は、パブリックシード、秘密鍵、初期化ベクトル、又は、これらの要素の組み合わせに依存する。なお、初期化ベクトルは、追加的なパラメータであって、一般に秘密ではなく、１回以上使用される同じ秘密鍵によって、多くのさまざまな擬似ランダムストリングを生成することを可能にする。
【００７３】
次いで、反復ステップは、初期状態X(0)から、及び、以下に記載された方法によって、ｔ組のＫ要素（ここで、ｔは１からｍの定数である）からなる擬似ランダムストリングZ(i)（ここで、i=1, 2, ...）を生成するよう実行される。例えば、反復の合計数は、１から２５０の間である。
【００７４】
ｉ回目の反復では、ｎ組のＫ要素を構成する現在状態X(i-1)は、次のサブステップを実行するための入力値として取り込まれる。
１）Ｋ値のｍ組のY(i)は、上に定義された関数Γ、即ち、Y(i)=Γ(X(i-1))を使用して、X(i-1)から差し引かれる。
２）出力値Z(i)は、ペア(X(i-1), Y(i))に、選択された出力関数S、即ち、Z(i)=S(X(i-1), Y(i))を、適用することによって取得される。
３）ｎ組のＫ値を構成する新しい現在状態X(i)は、ペア(X(i-1), Y(i))に、選択されたフィードバック関数F、即ち、X(i)=F(X(i-1), Y(i))を適用することによって取得される。
【００７５】
この方法は、図１（２つの連続的な反復を対象とする）に、逐次的な方法で示されているが、同様に、ループ方法で十分に示すことができる。ここで注目する重要な点は、方法の連続的なステップを１つの電子回路によって実行することができることである。
【００７６】
上に参照されたフィードバック関数F及び出力関数Sのための可能な選択の実施例に関しては、仏国特許出願第０５-０６０４１号明細書を参照されたい。また、少なくともストリングZ(i)に基づく、出力におけるシンボル（例えば、バイナリシンボル）の種々の擬似ランダムストリングを構成するための手段の実施例に関するアプリケーションを参照されたい。
【００７７】
図２は、本発明の擬似ランダムストリングジェネレータの１実施形態を示すブロック図である。このジェネレータは次のモジュールを具備している。
・計算される多項式のシステムの入力変数の値を格納するためのメモリ（１００）
・計算の終了時に、計算される１又は２以上の多項式によって得られた値を格納し、かつ、同時に、中間値格納ユニットとして機能するためのメモリ（５００）
・計算される多項式のシステムに関係した、多様な単項式の値を生成する（所定のオーダーで）ためのモジュール（２００）であって、自身のメモリを選択的に有する単項式ジェネレータモジュール（２００）
・計算される多項式のシステムを定義する、係数のシーケンスを生成するためのモジュール（３００）であって、自身のメモリを有するモジュール（３００）
・係数、及び、単項式の値を多重化して、多項式の値を格納しているメモリ（５００）を更新するための組み合わせモジュール（４００）
【００７８】
上の係数ジェネレータモジュール（３００）の１つの特に有利な実施形態は以下に説明されるとおりである。
【００７９】
本発明の擬似ランダムジェネレータの正しい機能にとって、各反復において同じ関数Γを適用することは必ずしも必要ではないことに注意されたい。換言すれば、便利性を証明する場合、ｍ個の多項式の各係数の値が、１つの反復から他の反復に変化することを妨げることはない。本実施形態は、これをうまく使用している。
【００８０】
係数ジェネレータモジュール（３００）の第１実施形態は、線形フィードバックシフトレジスタ（ＬＦＳＲ）の形をとる。
【００８１】
ＬＦＳＲは、メモリal内に格納された値を除き、各メモリai内に格納された値をメモリai+1内に格納された値に置き換えることによって、各クロックパルスにおいてリフレッシュされた、１セットのｌメモリa1, a2, …, alを具備している。なお、それは、前のクロックパルスにおいて、多様なメモリ内に格納された値の所定の線形組み合わせによって置き換えられる。
【００８２】
線形シフトレジスタからの出力ビットは、従来、擬似ランダムビットストリングとして使用される。好ましくは、本発明によれば、ＬＦＳＲ出力データは、出力値Z(i)を直接生成するのではなく、ｍ個の多項式の係数を生成することに使用される。ＬＦＳＲは、メモリ内のｒビットだけから、ｒ個の論理ゲートのオーダーだけを含んでいる電子回路を使用して、長さ（２ｒ−１）の擬似ランダムストリングを生成する。
【００８３】
例えば、バイナリ体GF(2)上に、ｎ＝８０個の変数を有するとともに、ｍ＝８０個の多変量多項式を有する式（Γ）のシステムでは、ナイーブ(naive)実装の２５９２００ビットよりもむしろ、ｒ＝１８ビットを有する線形シフトレジスタから、
【００８４】
【数１８】
【００８５】
個のシステムの係数を生成することができる。
【００８６】
第２実施形態では、係数ジェネレータモジュール（３００）は、非線形フィードバックシフトレジスタ（ＮＬＦＳＲ）の形をとる。線形フィードバックシフトレジスタに比べて、これは、電子ゲートの数の形態で追加的コストをほとんど伴わないが、ジェネレータの出力において生成された項のストリングのランダム特性を顕著に改善する。
【００８７】
第３実施形態では、係数ジェネレータモジュール（３００）は、
・各クロックパルスにおいて更新されたメモリ
・メモリを更新するための回路
・メモリ内に格納されたデータを拡張するための拡張回路
を具備している有限状態マシーン(finite state machine)の形をとる。
【００８８】
メモリ内のｇビットからｆビット（ここで、ｆ＞ｇ）を生成するように適合された回路を「拡張回路」という表現で呼ぶ。例えば、ｆがｈの倍数である場合、ｆビットのセットは、各ｈビットのサブセットに分割することができ、その後、各ｈビットのこれらのサブセットがストリング混合器を通過し、かつ、生成されたビットのストリングが最終的に連結される。
【００８９】
有限状態マシーンでは、全てのメモリの値（拡張の前）が各クロックパルスにおいてリフレッシュされ、これに反して、シフトレジスタでは、メモリ内の１つの値だけが各クロックパルスにおいてリフレッシュされる。したがって、有限状態マシーンは、シフトレジスタに比べてより高速な計算を実行するが、電子ゲートの数にいくらかのコストを増す。
【００９０】
上の実施形態は、やはり、迅速に、かつ、少数の電子ゲートを使用して、各反復において、式（Γ）のシステムの係数を生成する。
【００９１】
単項式の値のジェネレータモジュール（２００）の異なる実施形態を予想することもできる。記述を単純化するため（xixjのタイプの（ここで、i及びjは１からｎに変化する。））、二次項の計算だけがここでは取り扱われる。
【００９２】
「ナイーブ」実装は変数の全てのペアを順々に検討する。したがって、計算はｎ２のクロックパルスを必要とする。
【００９３】
しかし、代わりに、単項式は次のように計算することができる。変数（x1, x2, ... , xn）の値の現在ストリングの２つのコピーがメモリ内に配置される。はじめに、「フェーシング(facing)」項を計算して、ｎ個の２乗
【００９４】
【数１９】
【００９５】
を生成する。次いで、１つの位置による循環配列は、変数（x1, x2, ... , xn）の値のストリングの１つに適用される。再び、「フェーシング」項を計算して、ｎ個の積x1x2, x2x3, ..., xnx1を生成する。ｎ×ｎの単項式を計算するこのプロセスは、ｎ２個の積が取得されるまで継続される。可換の乗算の最後には、ｎ／２クロックパルスだけ必要とされるが、このデバイスは、「ナイーブ」実装の２倍のメモリを必要とする。
【００９６】
最後に、モジュール（３００）における係数の生成と、モジュール（２００）における単項式の生成とを組み合わせて、次の項に移る前に、全ての多項式のために「並行して」同じタイプの各項を計算することによって、速度を上げ、かつ、メモリ容量を節約することができる。例えば、二次多項式のシステムでは、対応する変数（タイプxixj, xj又は１のそれぞれ）のために対応する単項式が計算され、その後、連続したｍ個の多項式のため、この項（各タイプ
【００９７】
【数２０】
【００９８】
又はγk）の係数が生成され、次いで、前記単項式によって多重化され、前記項の値を取得する。
【図面の簡単な説明】
【００９９】
【図１】図１は、擬似ランダムストリングを生成するための本発明の１実施形態に関する方法を示しているブロック図である。
【図２】図２は、本発明の１実施形態の擬似ランダムジェネレータを示しているブロック図である。
【符号の説明】
【０１００】
Ｘｉ−１，Ｘｉ，Ｘｉ＋１ 変数
Ｙｉ，Ｙｉ＋１ 変数
Ｚｉ，Ｚｉ＋１ 擬似ランダムストリング
Ｆ フィードバック関数
Γ 関数
Ｓ 出力関数
１００ メモリ
２００ モジュール
３００ モジュール
４００ 組み合わせモジュール
５００ メモリ
【特許請求の範囲】
【請求項１】
暗号化手順において使用されることを意図したカージナル
【数１】
の有限体Ｋに属し、
前記有限体Ｋに属したｎ個の変数を有するｍ個の多項式のシステム（Γ）を反復して計算するための手段を具備する項の擬似ランダムストリングのジェネレータにおいて、
前記ｍ個の多項式の係数は、各反復において再生成される
ことを特徴とするジェネレータ。
【請求項２】
前記システム（Γ）を形成する各前記多項式の大部分は２次であることを特徴とする請求項１に記載の擬似ランダムストリングジェネレータ。
【請求項３】
線形シフトレジスタの形態で、係数ジェネレータモジュール（３００）を具備することを特徴とする請求項１乃至２のいずれか１項に記載の擬似ランダムストリングジェネレータ。
【請求項４】
非線形シフトレジスタの形態で、係数ジェネレータモジュール（３００）を具備することを特徴とする請求項１乃至２のいずれか１項に記載の擬似ランダムストリングジェネレータ。
【請求項５】
有限状態マシーンの形態で、係数ジェネレータモジュール（３００）を具備することを特徴とする請求項１乃至２のいずれか１項に記載の擬似ランダムストリングジェネレータ。
【請求項６】
所定のｎ組の変数(x1, x2, …, xn)に対して、前記多項式がＤ以下の全てのグローバル次数であるシステム（Γ）の前記ｍ個の多項式によって、得られたｍ組の値（y1, y2, …, ym）を計算するには、
前記ジェネレータは、
・次数Ｄのｎ個の変数を有する前記一般的な多項式の所定のセットの項の処理オーダーを選択する手段と、
・前記処理された項のため、同じオーダーにおいて、前記変数のために単項式を計算し、次いで、連続的に、前記ｍ個の多項式のためにその項の係数を生成し、かつ、前記単項式によってその係数を多重化するとともに、前記項の値を取得する手段と
を具備することを特徴とする請求項１乃至５のいずれか１項に記載の擬似ランダムストリングジェネレータ。
【請求項７】
請求項１乃至６のいずれか１項に基づく擬似ランダムストリングジェネレータを具備することを特徴とする電子回路。
【請求項８】
配線論理チップを具備することを特徴とする請求項７に記載の電子回路。
【請求項９】
暗号化手順において使用されることを意図したカージナル
【数２】
の有限体Ｋに属し、
前記有限体Ｋに属したｎ個の変数を有するｍ個の多項式のシステム（Γ）を反復して計算するステップを具備する項の擬似ランダムストリングの生成方法において、
前記ｍ個の多項式の係数は、各反復において再生成される
ことを特徴とする方法。
【請求項１０】
前記システム（Γ）を形成する各前記多項式の大部分は２次であることを特徴とする請求項９に記載の方法。
【請求項１１】
所定のｎ組の変数(x1, x2, …, xn)に対して、前記多項式がＤ以下の全てのグローバル次数であるシステム（Γ）の前記ｍ個の多項式によって、得られたｍ組の値（y1, y2, …, ym）を計算するには、
・次数Ｄのｎ個の変数を有する前記一般的な多項式の所定のセットの項の処理オーダーを選択するステップと、
・前記処理された項のため、同じオーダーにおいて、前記変数のために単項式を計算し、次いで、連続的に、前記ｍ個の多項式のためにその項の係数を生成し、かつ、前記単項式によってその係数を多重化するとともに、前記項の値を取得するステップと
を具備することを特徴とする請求項９乃至１０のいずれか１項に記載の方法。
【請求項１２】
請求項９乃至１１のいずれか１項に基づく方法の前記ステップを実行するためのコンピュータプログラムコード命令を具備する、取り外し不可能なデータ格納手段。
【請求項１３】
請求項９乃至１１のいずれか１項に基づく方法の前記ステップを実行するためのコンピュータプログラムコード命令を含む、一部又は全体を取り外し可能なデータ格納手段。
【請求項１４】
前記プログラムがプログラム可能なデータ処理デバイスを制御するとき、命令によって、前記データ処理デバイスに、請求項９乃至１１のいずれか１項に基づく方法を実行させる前記命令を含む、コンピュータプログラム。
【請求項１】
暗号化手順において使用されることを意図したカージナル
【数１】
の有限体Ｋに属し、
前記有限体Ｋに属したｎ個の変数を有するｍ個の多項式のシステム（Γ）を反復して計算するための手段を具備する項の擬似ランダムストリングのジェネレータにおいて、
前記ｍ個の多項式の係数は、各反復において再生成される
ことを特徴とするジェネレータ。
【請求項２】
前記システム（Γ）を形成する各前記多項式の大部分は２次であることを特徴とする請求項１に記載の擬似ランダムストリングジェネレータ。
【請求項３】
線形シフトレジスタの形態で、係数ジェネレータモジュール（３００）を具備することを特徴とする請求項１乃至２のいずれか１項に記載の擬似ランダムストリングジェネレータ。
【請求項４】
非線形シフトレジスタの形態で、係数ジェネレータモジュール（３００）を具備することを特徴とする請求項１乃至２のいずれか１項に記載の擬似ランダムストリングジェネレータ。
【請求項５】
有限状態マシーンの形態で、係数ジェネレータモジュール（３００）を具備することを特徴とする請求項１乃至２のいずれか１項に記載の擬似ランダムストリングジェネレータ。
【請求項６】
所定のｎ組の変数(x1, x2, …, xn)に対して、前記多項式がＤ以下の全てのグローバル次数であるシステム（Γ）の前記ｍ個の多項式によって、得られたｍ組の値（y1, y2, …, ym）を計算するには、
前記ジェネレータは、
・次数Ｄのｎ個の変数を有する前記一般的な多項式の所定のセットの項の処理オーダーを選択する手段と、
・前記処理された項のため、同じオーダーにおいて、前記変数のために単項式を計算し、次いで、連続的に、前記ｍ個の多項式のためにその項の係数を生成し、かつ、前記単項式によってその係数を多重化するとともに、前記項の値を取得する手段と
を具備することを特徴とする請求項１乃至５のいずれか１項に記載の擬似ランダムストリングジェネレータ。
【請求項７】
請求項１乃至６のいずれか１項に基づく擬似ランダムストリングジェネレータを具備することを特徴とする電子回路。
【請求項８】
配線論理チップを具備することを特徴とする請求項７に記載の電子回路。
【請求項９】
暗号化手順において使用されることを意図したカージナル
【数２】
の有限体Ｋに属し、
前記有限体Ｋに属したｎ個の変数を有するｍ個の多項式のシステム（Γ）を反復して計算するステップを具備する項の擬似ランダムストリングの生成方法において、
前記ｍ個の多項式の係数は、各反復において再生成される
ことを特徴とする方法。
【請求項１０】
前記システム（Γ）を形成する各前記多項式の大部分は２次であることを特徴とする請求項９に記載の方法。
【請求項１１】
所定のｎ組の変数(x1, x2, …, xn)に対して、前記多項式がＤ以下の全てのグローバル次数であるシステム（Γ）の前記ｍ個の多項式によって、得られたｍ組の値（y1, y2, …, ym）を計算するには、
・次数Ｄのｎ個の変数を有する前記一般的な多項式の所定のセットの項の処理オーダーを選択するステップと、
・前記処理された項のため、同じオーダーにおいて、前記変数のために単項式を計算し、次いで、連続的に、前記ｍ個の多項式のためにその項の係数を生成し、かつ、前記単項式によってその係数を多重化するとともに、前記項の値を取得するステップと
を具備することを特徴とする請求項９乃至１０のいずれか１項に記載の方法。
【請求項１２】
請求項９乃至１１のいずれか１項に基づく方法の前記ステップを実行するためのコンピュータプログラムコード命令を具備する、取り外し不可能なデータ格納手段。
【請求項１３】
請求項９乃至１１のいずれか１項に基づく方法の前記ステップを実行するためのコンピュータプログラムコード命令を含む、一部又は全体を取り外し可能なデータ格納手段。
【請求項１４】
前記プログラムがプログラム可能なデータ処理デバイスを制御するとき、命令によって、前記データ処理デバイスに、請求項９乃至１１のいずれか１項に基づく方法を実行させる前記命令を含む、コンピュータプログラム。
【図１】
【図２】
【図２】
【公表番号】特表２００９−５３３７０５（Ｐ２００９−５３３７０５Ａ）
【公表日】平成２１年９月１７日（２００９．９．１７）
【国際特許分類】
【出願番号】特願２００９−５０４７８９（Ｐ２００９−５０４７８９）
【出願日】平成１９年４月２日（２００７．４．２）
【国際出願番号】ＰＣＴ／ＦＲ２００７／０５１０５２
【国際公開番号】ＷＯ２００７／１１６１７１
【国際公開日】平成１９年１０月１８日（２００７．１０．１８）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
【出願人】（５９１０３４１５４）フランス テレコム ソシエテ アノニム (290)
【氏名又は名称原語表記】Ｆｒａｎｃｅ Ｔｅｌｅｃｏｍ ＳＡ
【Ｆターム（参考）】
【公表日】平成２１年９月１７日（２００９．９．１７）
【国際特許分類】
【出願日】平成１９年４月２日（２００７．４．２）
【国際出願番号】ＰＣＴ／ＦＲ２００７／０５１０５２
【国際公開番号】ＷＯ２００７／１１６１７１
【国際公開日】平成１９年１０月１８日（２００７．１０．１８）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
【出願人】（５９１０３４１５４）フランス テレコム ソシエテ アノニム (290)
【氏名又は名称原語表記】Ｆｒａｎｃｅ Ｔｅｌｅｃｏｍ ＳＡ
【Ｆターム（参考）】
[ Back to top ]