(57)【特許請求の範囲】
【請求項１】
状態ベクトルの初期値(V0)から反復的に生成される、サイズkの状態ベクトル(V)の一連の値によって形成される擬似ランダムデータシーケンス(3,13)を疑似ランダム生成器により生成する暗号化方法であって、それぞれの反復中に、前記それぞれの反復について前記状態ベクトルの現在値(Vn)を生成するために、前記方法は、
・前記疑似ランダム生成器による適用ステップであって、k以上のサイズk1の転置の所定の数dからなる複数の転置は、直前の反復で生成された状態ベクトルの直前の値(Vn-1)の少なくとも1つのセクションから形成されるサイズkの少なくとも1つの第1の中間ベクトル(Vint1)を含むサイズk1の仮ベクトル(Vprov)に対して連続して適用され、それぞれの転置は、サイズdの転置鍵(C)のビットに関連し、かつ、少なくとも前記ビットの値の関数として選択され、前記転置鍵は、前記第1の中間ベクトル(Vint1)のkビットからdビットを選択することの結果であるステップと、
・前記疑似ランダム生成器により前記状態ベクトルの前記現在値(Vn)を、前記適用ステップの結果ベクトル(Vres)の少なくとも1つのセクション(Vint2)から得るステップと、
を含むことを特徴とする擬似ランダムデータシーケンスを生成する暗号化方法。
【請求項２】
前記仮ベクトルは、前記第1の中間ベクトルのそれぞれのビットの1の補数を求めることによって得られるベクトルをさらに含むことを特徴とする請求項1に記載の擬似ランダムデータシーケンスを生成する暗号化方法。
【請求項３】
前記状態ベクトルの前記現在値は、前記適用ステップの前記結果ベクトルの前記セクション(Vint2)および前記状態ベクトルの前記直前の値に対して排他的論理和演算(327a,27a)を適用することの結果であることを特徴とする請求項1または請求項2に記載の擬似ランダムデータシーケンスを生成する暗号化方法。
【請求項４】
仮ベクトル(Vprov)および前記転置鍵(C)は、同じサイズであり、前記第1の中間ベクトル(Vint1)のサイズに等しいことを特徴とする請求項1または請求項3に記載の擬似ランダムデータシーケンスを生成する暗号化方法。
【請求項５】
それぞれの反復は、前記適用ステップの前に、前記状態ベクトルの前記直前の値(Vn-1)および入力データブロック(Un,Yn,Zn)からアプリケーション(AT)により計算される現在の中間値(Xα)を得るステップをさらに含み、
前記第1の中間ベクトルは、前記状態ベクトルの前記直前の値によって形成され、
セクション(Xn-1)は、前記現在の中間値(Xα)によって置換えられていることを特徴とする請求項1から4のいずれか1項に記載の擬似ランダムデータシーケンスを生成する暗号化方法。
【請求項６】
ハッシングデバイスにより、メッセージのダイジェスト(hash)を生成するために、擬似ランダムデータシーケンスを生成する請求項5に記載の暗号化方法を使用して、前記メッセージ(Mess)を暗号化ハッシングする方法であって、
前記メッセージは、所定の数Mのデータブロックを含み、
それぞれのデータブロックは、前記状態ベクトル(V)のMの値を生成するように擬似ランダムデータシーケンスを生成する暗号化方法の連続する反復中に、入力ブロック(Zn)として順番に使用され、
前記メッセージの前記ダイジェストは、前記状態ベクトルの生成された最新の値(VM)から得られることを特徴とする方法。
【請求項７】
暗号化デバイスによる、入力データシーケンスの暗号化方法であって、
状態ベクトル(V)の初期値(V0)および前記入力データシーケンスを形成する一連の入力ワード(Un,Yn)から、前記状態ベクトルの一連の値(Vn)および一連の出力ワード(Yn,Un)が反復的に生成され、それぞれの反復は、
・前記暗号化デバイスにより、前記それぞれの反復についての現在出力ワード(Yn, Un)が、現在入力ワード(Un,Yn)、および、直前の反復で生成された前記状態ベクトルの直前の値(Vn-1)に依存する可逆的アプリケーションによって計算される暗号化ステップと、
・前記暗号化デバイスにより、前記それぞれの反復について前記状態ベクトルの現在値(Vn)が、前記状態ベクトルの前記直前の値(Vn-1)に少なくとも依存する非可逆的アプリケーションによって計算される擬似ランダム生成ステップと、を含み、
前記可逆的アプリケーションは、少なくとも第1および第2の秘密鍵関数(35a、35c)を含み、秘密鍵は、前記状態ベクトルの前記直前の値の少なくとも1つのセクション(Xn-1,An-1,Bn-1)から生成され、
前記非可逆的アプリケーションは、前記状態ベクトルの前記直前の値(Vn-1)および前記現在入力ワード(Un,Yn)に依存し、かつ、前記第1の秘密鍵関数(35a)または前記第2の秘密鍵関数(35c)によって、前記入力ワード(Un,Yn)または前記出力ワード(Yn, Un)から隔離される現在中間値(Xα)にさらに依存することを特徴とする暗号化方法。
【請求項８】
前記第1および第2の秘密鍵関数の一方または両方は、前記関数の前記秘密鍵の少なくとも1つのセクション(An-1,Bn-1)によってセットされたパラメータを有する少なくとも1つの排他的論理和演算(41a,41c)を含むことを特徴とする請求項7に記載の暗号化方法。
【請求項９】
前記状態ベクトルは、サイズkであり、前記擬似ランダム生成ステップは、前記状態ベクトルの前記現在値を計算するために、
・適用ステップであって、前記状態ベクトルの前記直前の値のセクションおよび非可逆的アプリケーションに依存する現在中間値から形成されるサイズkの少なくとも1つの第1の中間ベクトルを含むk以上のサイズk1の仮ベクトルに対して、サイズk1の転置の所定の数dからなる複数の転置が連続して適用され、それぞれの転置は、それぞれ、サイズdの転置鍵のそれぞれの別個のビットに関連し、かつ、少なくとも前記転置鍵のビットの値の関数として選択され、前記鍵は、前記第1の中間ベクトルのkビットから別個のdビットを選択することによって得られるステップと、
・前記状態ベクトルの前記現在値(Vn)を、前記適用ステップの結果ベクトルの少なくとも1つのセクションから得るステップと、
を含むことを特徴とする請求項7または請求項8に記載の暗号化方法。
【請求項１０】
前記仮ベクトルは、前記第1の中間ベクトルのそれぞれのビットの1の補数を求めることによって得られるベクトルをさらに含むことを特徴とする請求項9に記載の暗号化方法。
【請求項１１】
前記状態ベクトルの前記現在値は、前記適用ステップの前記結果ベクトルの前記セクション(Vint2)および前記状態ベクトルの前記直前の値に適用された排他的論理和演算(27a,327a)の結果であることを特徴とする請求項9または請求項10に記載の暗号化方法。
【請求項１２】
前記入力ワード(Un,Yn)または前記出力ワードと、前記入力ワード(Un,Yn)および前記出力ワードの両方と、のいずれか一方は、前記反復の関数として可変のビット数(w)を含み、
前記状態ベクトルは、それぞれの反復において可変の前記ビット数を指示するセクションを含むことを特徴とする請求項7から11のいずれか1項に記載の暗号化方法。
【請求項１３】
それぞれの反復の前記擬似ランダム生成ステップは、前記状態ベクトルの前記現在値から、可変の前記ビット数がゼロであると判定されると、前記状態ベクトルの前記現在値に依存する非可逆的アプリケーションによって、前記状態ベクトルの前記現在値を置換える前記状態ベクトルの新しい現在値(Vtemp)を計算するステップをさらに含むことを特徴とする請求項12に記載の暗号化方法。
【請求項１４】
・前記擬似ランダム生成ステップは、第1の状態ベクトル(V1)の現在値(V1n)を形成する第1の擬似ランダム生成ステップであり、
・前記第1の擬似ランダム生成ステップは、第2の状態ベクトル(V2)の現在値(V2n)を形成する少なくとも1つの第2の擬似ランダム生成ステップと並列に組み合わされ、
・前記状態ベクトルの前記現在値(Vn)は、前記第1の状態ベクトルの前記現在値(V1n)および少なくとも前記第2の状態ベクトルの前記現在値(V2n)に対して排他的論理和演算(131)を適用することの結果であることを特徴とする請求項7から13のいずれか1項に記載の暗号化方法。
【請求項１５】
前記暗号化ステップは第1の暗号化ステップであり、前記第1の暗号化ステップにおいて、
・第1の現在入力ワード(U1n,Y1n)および前記状態ベクトルの前記直前の値(Vn-1)の少なくとも1つの第1のセクションに依存する第1の可逆的アプリケーションによって第1の現在出力ワード(Y1n,U1n)と、また、
・第1の現在中間値(X1α)と、が計算され、
前記方法は、少なくとも1つの第2の暗号化ステップをさらに含み、前記第2の暗号化ステップにおいて、
・第2の現在入力ワード(U2n,Y2n)および前記状態ベクトルの前記直前の値(Vn-1)の少なくとも1つの第2のセクションに依存する第2の可逆的アプリケーションによって第2の現在出力ワード(Y2n,U2n)と、また、
・第2の現在中間値(X2α)と、が計算され、
前記擬似ランダム生成ステップ中に使用される前記現在中間値は、前記第1の現在中間値(X1α)および少なくとも前記第2の現在中間値(X2α)を含むことを特徴とする請求項7から14のいずれか1項に記載の暗号化方法。
【請求項１６】
少なくとも2つの暗号化メッセージブロックを形成するために、平文の少なくとも2つのメッセージブロックの暗号的多重化をするステップをさらに含み、
平文のそれぞれのメッセージブロックは、一連の入力ワードに相当し、
前記少なくとも2つの暗号化メッセージブロックは、前記状態ベクトルの前記直前の値のセクションの関数としてそれぞれの反復において順序付けられることを特徴とする請求項15に記載の暗号化方法。
【請求項１７】
プログラムコード命令を含むコンピュータプログラムであって、
前記プログラムが、コンピュータまたはデータ処理システムにロードされ、前記コンピュータまたはデータ処理システムで実行されると、前記コンピュータ又は前記データ処理システムは疑似ランダム生成器を使用して、請求項1から5のいずれか1項に記載の、擬似ランダムデータシーケンスを生成する方法を実行することを特徴とするコンピュータプログラム。
【請求項１８】
プログラムコード命令を含むコンピュータプログラムであって、前記プログラムが、コンピュータまたはデータ処理システムにロードされ、前記コンピュータまたはデータ処理システムで実行されると、前記コンピュータ又は前記データ処理システムはハッシングデバイスを使用して、請求項6に記載の暗号化ハッシング方法を実行することを特徴とするコンピュータプログラム。
【請求項１９】
プログラムコード命令を含むコンピュータプログラムであって、前記プログラムが、コンピュータまたはデータ処理システムにロードされ、前記コンピュータまたはデータ処理システムで実行されると、前記コンピュータ又は前記データ処理システムは暗号化デバイスを使用して、請求項7から16のいずれか1項に記載の暗号化方法を実行することを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルセキュリティの全般的な分野に関し、より詳細には、暗号に関する。
【０００２】
本発明は、とりわけ、データシーケンスを対称暗号化するデバイスおよび方法を提案する。本発明はまた、擬似ランダムデータシーケンスを生成する暗号論的デバイスおよび暗号論的方法、ならびに、デジタルセキュリティの分野における、特に、データを暗号化し復号化するため、また、メッセージを暗号論的にハッシングするためのその有利な使用に関する。
【背景技術】
【０００３】
暗号化データは、対称暗号化アルゴリズムを使用して、高ビットレートでシステム的に交換される。
【０００４】
対称暗号化アルゴリズムの有効性は、暗号化される情報に適用される処理の複雑さに依存する暗号解読に対する耐性、脆弱性が無いこと、および暗号化鍵のサイズに依存するブルートフォース攻撃に対する耐性に基づいて評価される。
【０００５】
さらに、対称暗号化の有効性はまた、その実行速度に依存する。暗号化アルゴリズムが動作するビットレートは、暗号化される/復号化されることになる情報について関係するアプリケーションの最高ビットレートより高くなければならない。
【０００６】
相応して、高ビットレートのアプリケーションの場合、セキュアな解決策インテグレータは、暗号化アルゴリズムを選択するときに難局に直面する。それは、処理される情報のビットレートの増加に伴って、また、一定の計算パワーについて、情報を処理するために利用可能な時間が減少し、暗号解読耐性の点で折り合いがもたらされるからである。
【０００７】
対称暗号化を実施する従来技術のストリーム暗号化メカニズムは、連続する反復の過程で、連続してデータを暗号化し、また、データビットレートが高いとき、かつ/または、リアルタイムに暗号化すること/復号化することが必須であるとき、有利に使用されうる。
【０００８】
図15Aを参照すると、ストリーム暗号化メカニズムは、一般に、鍵Kおよび初期化ベクトルによってセットされたパラメータを有する(たとえば、シフトレジスタに基づく)擬似ランダムビット生成器Gの形態をとり、それによって、排他的論理和演算(
【０００９】
【数１】
0005551065.tif 000002
【００１０】
と書かれ、また、モジュロ2バイナリ加算に相当する)が、生成器の出力ビットkiおよび暗号化されるデータからのビットpiに適用され、そのため一般に、それぞれの反復iに関して単一出力ビットciの計算がもたらされる。
【００１１】
これらのストリーム暗号化方法は、その簡潔さおよび使用される命令セットの数の少なさのためにハードウェア実施態様において著しく高速であるが、いくつかの深刻な制限があり、いくつかの深刻な制限は、指定された高ビットレートの直接の結果であるため、一般に受容される。
【００１２】
第1に、これらのストリーム暗号化方法によって使用される擬似ランダム生成器は、一般に、線形または非線形シフトレジスタの使用に基づく。こうして使用されると、これらのシフトレジスタは、深刻な暗号論的欠点を有する。生成器の擬似ランダム挙動を暗号論的に受容可能にするために、結合関数を使用して、シフトレジスタを互いに結合することが知られている。これらの結合関数を供給する(feed)のに必要なレジスタの数の増加および結合関数それ自体の複雑さは、ハードウェア実施態様において要求されるコンポーネントの数に著しく影響を及ぼし、擬似ランダム生成アルゴリズムおよび暗号化方法の実行速度を制限する。
【００１３】
さらに、これらの擬似ランダム生成器は、非常に制限された数の出力ビット(通常、1ビット、おそらく8または16ビット)だけを一度に生成する。その結果、ストリーム暗号化方法のそれぞれの反復に関して暗号化されるビット数もまた、非常に制限され、方法によってデータが保護されるアプリケーションの実際の要求を必ずしも満たさない。
【００１４】
これらの欠点を解決するために、擬似ランダム生成のためにブロック暗号化アルゴリズムを使用するストリーム暗号化メカニズムが使用されうる。暗号フィードバック(cipher feedback)(CFB)モードでブロック暗号化アルゴリズムを使用するストリーム暗号化メカニズムの例は、図15Bに示され、「Applied Cryptography protocols, algorithms and source code in C」(第2版、1996年)という名称のB. Scheierによる文書に記載される。しかし、ストリーム暗号化方法において擬似ランダム生成のためのブロック暗号化アルゴリズムを使用することは、少なくとも2つの主要な欠点がある。すなわち、第1に、ハードウェア実施態様において全体のサイズが大きいこと、第2に、実行速度が遅いことである。
【００１５】
さらに、擬似ランダム生成器の出力ビットおよび暗号化されるメッセージのビットに排他的論理和演算を適用することに基づく、上述したストリーム暗号化メカニズムの設計は、図15Bに示すように、擬似ランダム生成器を、標準的な暗号解読の文脈で直接観測可能にし、また、CFBモードにおいて駆使可能にする。換言すれば、擬似ランダム生成器の出力の状態は、排他的論理和演算を使用して平文(in clear)のテキストと暗号化テキストを結合することによって直接アクセス可能になり、また、アルゴリズムの暗号解読に直接使用可能な情報を連続して提供する。相応して、図15Bに示すストリーム暗号化方法の例では、出力を観測し、暗号化方法の入力を駆使することによって、擬似ランダム生成器のシフトレジスタを予め規定された状態にもたらすことが可能であり、これが、主要な暗号論的脆弱性を構成する。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】「Applied Cryptography protocols, algorithms and source code in C」(第2版、1996)という名称のB. Scheierによる文書
【発明の概要】
【発明が解決しようとする課題】
【００１７】
その結果、ハードウェアとソフトウェアの両方における単純でかつ効率的な(特に、実行速度の点で)実施態様を確保しながら、任意の予め規定されたサイズのベクトルの暗号論的にセキュアな擬似ランダムシーケンスの高速生成についての解決策、擬似ランダム生成器の可観測性および駆使能力についてのこうした欠点がない暗号化/復号化解決策、ならびに、高いレベルのデジタルセキュリティの保証についての必要性が存在する。
【課題を解決するための手段】
【００１８】
本発明の第1の態様は、サイズkの状態ベクトルであって、状態ベクトルの初期値から反復的に生成される、サイズkの状態ベクトルの一連の値によって形成される擬似ランダムデータシーケンスを生成する暗号論的方法を提案することによって、この必要性に対処する。本発明によれば、暗号論的方法のそれぞれの反復中に、その反復について状態ベクトルの現在値を生成するために、所定の数dのk以上のサイズk1の転置が、直前の反復で生成された状態ベクトルの直前の値の少なくとも1つのセクションから形成されるサイズkの少なくとも1つの第1の中間ベクトルを含むサイズk1の仮ベクトルに対して連続して適用される。それぞれの転置は、サイズdの転置鍵の別個のビットにそれぞれ関連し、かつ、少なくともそのビットの値の関数として選択され、上記転置鍵は、第1の中間ベクトルのkビットから別個のdビットを選択することの結果である。状態ベクトルの現在値は、その後、この適用ステップの結果ベクトルの少なくとも1つのセクションから得られる。
【００１９】
以下の説明は、バイナリデータおよびバイナリベクトル、すなわち、その成分がビットであるデータおよびベクトルに関連する。そのため、サイズtのベクトルは、tビットからなるベクトルである。
【００２０】
本発明の意味で、表現「ベクトルVbを含むベクトルVa(vector Va comprising a vector Vb)」は、その成分の中に、(連続的にまたは非連続的に、同じ順序でまたは任意の順序で)ベクトルVbの成分の全てを含むベクトルVaを意味する。たとえば、ベクトルVb=(1,0,0,1)およびベクトルVa=(0,1,Vb)が考えられる場合、ベクトルVaは、ベクトルVbを含み、かつ、Va=(0,1,1,0,0,1)に等しいベクトルである。
【００２１】
さらに、本発明の意味で、表現「サイズtのベクトルのセクション(section of a vector of size t)」は、そのベクトルにおいて特定の位置を占めるそのベクトルのjビットのセットを意味し、jは1〜tの範囲内にある(1≦j≦t)。そのため、サイズtのベクトルのサイズtのセクションは、そのベクトルそれ自体を指す。
【００２２】
セクションのjビットによって占められる特定の位置は、好ましくは、予め決まっておりかつ固定される(たとえば、ベクトルの最初のjビットからなるセクションまたはベクトルの最後のjビットからなるセクション)。しかし、特定の位置は、たとえば、そのビットが予め決められかつ固定された位置を占めるベクトルのセクションの値の関数として同様に確定され、このため、必ずしも時間的に固定されないであろう。
【００２３】
こうして、それぞれの反復に関して、本発明は、生成される状態ベクトルの現在値から、状態ベクトルのサイズk以下の任意の数の擬似ランダムビットを生成し、kは、任意の値をとるパラメータである(考えられうるkの値に関して理論的限界は存在しない)。したがって、本発明は、いろいろなサイズ(必ずしも1ビットだけに制限されない)の擬似ランダムベクトルを必要とする様々なアプリケーションにおいて容易に使用され、目標のアプリケーションの要求に適合しうる。
【００２４】
さらに、本発明は、dの転置で構成され、かつ、擬似ランダムベクトルから抽出されるため、それ自体擬似ランダムである転置鍵によってセットされた(または、パラメータ化された)パラメータを有する転置関数を反復的に使用して、擬似ランダムデータシーケンスを生成することを提案する。dの転置のそれぞれは、少なくとも関連する転置鍵のビットの値の関数として、予め規定された転置対(その転置対は、転置ステージごとに変わるか、または、全てのステージについて同じままでありうる)から選択される。転置鍵のサイズd(d≦k)は、パラメータであり、転置されたデータのよりよいミキシングを保証するために比較的大きくされうる。
【００２５】
本発明で使用される転置関数は、有利には1方向関数である。それ自体知られているように、1方向関数は、1方向に容易に計算されるが、適度な時間内で(すなわち、適度な複雑さを持って)反転するのが難しいかまたはさらに不可能である。
【００２６】
本発明で使用される転置関数は、入力データベクトルの関数として出力データベクトルを計算することが、それぞれが1つの明示的な項を有するk1の等式の評価を必要とするようなものである。対照的に、出力データベクトルの関数として入力データベクトルを計算しようと試みることに関して、それぞれが、dの未知数で2d項を含むk1の方程式からなる多変量システム(すなわち、それぞれの項が、複数の未知数の結合である多変量システム)を解くことが必要である。そのため、こうした方程式システムは、それぞれの方程式内の項の数が方程式の数よりずっと多く、特に、dの高い値について著しく多いため、簡単には解きえないことが明らかである。
【００２７】
さらに、この数は、反復が進むにつれて増加する。すなわち、システムは「自己複雑系である(self-complicating)」。ハードウェアの点で、これの結果として得られることは、解かれる方程式のセットが、特に大きな鍵サイズについて、書き下せず、物理的に格納しえないことである。たとえば、サイズd=k=256の転置鍵の場合、それぞれが2256項を有する256の方程式を含む256の未知数の多変量システムが、最初の反復で解かれなければならない。
【００２８】
したがって、本発明で実施される1方向関数は、とりわけ配線の点で、転置の使用を通して比較的複雑でない実施態様を提供しながら、反転するのが特に難しく、ブルートフォース攻撃および暗号解読に対して頑健である(その数学的複雑さが非常に高い)。1方向関数は、したがって、低レベルのアーキテクチャを使用して実施されうり、少数の成分を必要とするためコンパクトであり、したがって、ハードウェアまたはソフトウェア実施態様において高速実行を提供する。
【００２９】
生成されたる擬似ランダムシーケンスの品質を高め、また、高品質のミキシングを得るために、考えられるサイズk1のdの転置は、有利には、以下の条件の少なくとも1つを満たす予め規定された転置対P0、P1(ビットが0に等しいときのビットに関連する転置を指定するP0、および、ビットが0に等しいときのビットに関連する転置を指定するP1)から選択されるであろう。以下の条件とは、
・鍵のそれぞれのビットについて、P0およびP1のそれぞれの構成によって得られる転置ならびにP1およびP0のそれぞれの構成によって得られる転置は、全ての点で異なること、
・全ての点で異なる転置P0およびP1の同一の対が、1方向関数のdのステージ(転置の適用に相当するステージ)のそれぞれで使用されること、
・全ての点で恒等転置と個々に異なる転置P0およびP1の対が、1方向関数のdのステージのそれぞれで使用され、こうして、転置鍵のそれぞれのビットが、転置される入力データの全てのビットに影響を及ぼすこと
である。
【００３０】
それぞれのステージで同一の転置対を使用することは、本発明の擬似ランダム生成方法のハードウェアの複雑さを低減するとう利点を有する。それぞれ2つの転置P0およびP1に相当する2つのモジュールだけが、ハードウェアで実施される必要がある。本発明を実施するために、これらのモジュールは、その後、連続して数回使用されうる。または、dの同一のモジュールが、それぞれの転置のために使用されるであろう(すなわち、全部で2dモジュール)。
【００３１】
しかし、これらの仮定は、他の転置が考えられうるため、本発明をいずれの点でも制限しない。特に、異なる転置ステージで(すなわち、鍵の別個のビットについて)別個の転置対(P0,P1)を考えることが可能である。
【００３２】
異なる実施態様では、仮ベクトルは、さらに、第1の中間ベクトルのそれぞれのビットの1の補数を求めることによって得られるベクトルを含む。そのため、たとえば、Vprovが仮ベクトルを指定し、Vint1が第1の中間ベクトルを指定する場合、
【００３３】
【数２】
0005551065.tif 000003
【００３４】
であると考えられうる。式中、
【００３５】
【数３】
0005551065.tif 000004
【００３６】
は、第1の中間ベクトルVint1のそれぞれのビットの1の補数を求めることによって得られるベクトルを指定する。
【００３７】
これは、dの値によらず、狭義のなだれ効果を生じる。すなわち、第1の中間ベクトルVint1の単一ビットを修正することは、1方向関数の適用から生じ、また、状態ベクトルの現在値の構築で使用されるベクトルのビットの半分の値に統計的に影響を及ぼす。これの結果として得られるものは、疎な(すなわち、ハミング重みが低い)第1の中間ベクトルの使用に関連する悪い影響を制限すること、および、本発明の暗号論的擬似ランダム生成方法のハードウェア攻撃に対する耐性を改善することである。プロセス内で達成される拡散は、そのため優れており、注目すべき暗号論的品質を構成する。
【００３８】
さらに、こうして得られる仮ベクトルは、第1の中間ベクトルの値が何であっても、kに等しい一定のハミング重みを有する。同様に、ハードウェア実施態様では、dの値およびVint1によらず1方向関数を実行することは、完全に一定の電力消費を有する。1方向関数の転置のそれぞれのステージにおいて、一定数の1のビットが存在し、1方向関数のそれぞれのステージの起動は、関係する鍵のビットが0であろうと、1であろうと、同じ数の論理ゲートを起動する。したがって、本発明の1方向関数はまた、電力消費解析に基づくハードウェア攻撃に感受性がない。
【００３９】
本発明の別の変形の実施態様では、仮ベクトルは、第1の中間ベクトルに等しいものとして考えられうる(k1=k)。
【００４０】
本発明の1つの特定の実施態様では、状態ベクトルの現在値は、適用ステップから生じるベクトルの前記セクションおよび状態ベクトルの直前の値に、排他的論理和演算を適用することの結果である。
【００４１】
この実施態様は、状態ベクトルの連続する擬似ランダム値を生成するプロセスの数学的複雑さを増加させる。排他的論理和演算は、状態ベクトルの初期値の重みに関する全ての情報を失い、そのため、状態ベクトルのハミング重みが、反復が進むにつれて修正される。
【００４２】
本発明の1つの特定の実施態様では、仮ベクトルおよび転置鍵は、同じサイズであり、第1の中間ベクトのサイズに等しい。
【００４３】
この実施形態では、説明は、矩形1方向関数と対照的に、四角形1方向関数に言及し、転置鍵は、1方向関数が適用される仮ベクトルのサイズk(k1≧k)と異なるサイズd(d≦k)である。
【００４４】
本発明の別の実施態様では、擬似ランダムデータのシーケンスを生成する上記暗号論的方法は、それぞれの反復が、適用ステップの前に、さらに、状態ベクトルの直前の値および入力データブロックから計算される現在中間値を得るステップを含むようなものであり、第1の中間ベクトルは、セクションが現在中間値で置換えられた状態ベクトルの直前の値によって形成される。
【００４５】
そのため、本発明によって生成される擬似ランダムデータシーケンスは、特定の期間を有さず、また、状態ベクトルの初期値だけの関数として予め確立されたサイクルに追従しない。状態ベクトルの現在値は、状態ベクトルの初期値および適用される入力データシーケンスの全体に依存する。これは、擬似ランダムデータシーケンスの動的エボリューションを保証する。
【００４６】
擬似ランダムデータシーケンスを生成するこの方法に適合する方法は、非常に有利な特性を有し、多数の暗号学的セキュリティアプリケーションのための潜在的な候補になる。
【００４７】
特に、本発明はまた、メッセージを暗号論的にハッシングして、メッセージのダイジェストを生成する方法において、擬似ランダムデータシーケンスを生成するこうした暗号論的方法を使用することを対象とし、ダイジェストは、所定の数Mのデータブロックを含み、所定の数Mのデータブロックは、状態ベクトルのMの値を生成するように擬似ランダムデータシーケンスを生成する暗号論的方法の連続する反復中に、現在中間値を計算するために入力データブロックとして順番に使用される。メッセージのダイジェストは、その後、こうして生成された状態ベクトルの最新の値から得られる。
【００４８】
こうして使用されるハッシング方法は、特に実施態様の頑健性および単純さの点で、本発明の擬似ランダム生成方法の全ての利点を有する。
【００４９】
さらに、本発明はまた、以下でより詳細に述べるように、入力データシーケンスを暗号化する方法において、擬似ランダムデータシーケンスを生成するこうした暗号論的方法の使用を対象とする。
【００５０】
本発明の第2の態様は、入力データシーケンスを対称暗号化する方法に関しており、方法において、状態ベクトルの初期値および上記入力シーケンスを形成する一連の入力ワードに基づいて、上記状態ベクトルの一連の値および一連の出力ワードが反復的に生成され、それぞれの反復は、
・それぞれの反復についての現在出力ワードが、現在入力ワード、および、直前の反復で生成される状態ベクトルの上記直前の値に依存する可逆的アプリケーションによって計算される暗号化ステップと、
・上記それぞれの反復について状態ベクトルの現在値が、少なくとも状態ベクトルの上記直前の値に依存する非可逆的アプリケーションによって計算される擬似ランダム生成ステップと、を含み、
上記方法は、
・上記可逆的アプリケーションが、少なくとも第1および第2の秘密鍵関数を含み、上記秘密鍵が、状態ベクトルの直前の値の少なくとも1つのセクションから生成され、
・上記非可逆的アプリケーションが、さらに、状態ベクトルの直前の値および現在入力ワードに依存し、かつ、それぞれ上記第1の秘密鍵関数、上記第2の秘密鍵関数によって、それぞれ、入力ワード、出力ワードから隔離される現在中間値に依存することを特徴とする。
【００５１】
本発明の意味で、表現「入力および出力ワードから隔離されたベクトル(vector isolated from the input and output words)」は、入力および出力ワードを使用してアクセス可能でない、すなわち、これらのワードによって駆使可能でなく、また、観測可能でないベクトルを指す。明らかに、
・入力、状態ベクトル、および出力を特徴とするシステムは、状態ベクトルが、有限な入力シーケンスの適用によって所定の値になりえない場合、駆使可能でない、
・入力、状態ベクトル、および出力を特徴とするシステムは、所与の時刻の状態ベクトルの値が、出力シーケンスの有限回の観測から推論されえない場合、観測可能でない。
【００５２】
当業者は知っているように、対称暗号化プロセスにおける状態ベクトルの初期値が秘密である。反復によって、状態ベクトルの直前の値が、駆使可能でなく、かつ、観測可能でない場合、本発明の暗号化方法において状態ベクトルの現在値を計算するのに使用される現在中間値は、それ自体駆使可能でなく、また、観測可能でない。その結果、得られる現在の状態ベクトルはまた、駆使可能でなく、また、観測可能でない、すなわち、入力および出力ワードから隔離される。これは、状態ベクトルの値の直接の観測、あるいは、状態ベクトルの一連の値の再構築またはパイロッティングを防止する。さらに、情報漏洩を回避するために状態ベクトルの初期値を修正することは必要でない(たとえば、第1の暗号化メッセージ
【００５３】
【数４】
0005551065.tif 000005
【００５４】
第2の暗号化メッセージ = 平文の第1のメッセージ
【００５５】
【数５】
0005551065.tif 000006
【００５６】
平文の第2のメッセージ)。
【００５７】
本発明の暗号化方法は、平文のメッセージを暗号化するため、または、暗号化メッセージを復号化するために、交換可能に使用されうることが特に有利であり、入力データシーケンスは、平文のメッセージに等しいとして考えられることがあり、また、暗号化メッセージに等しいとして考えられることがある。復号化は、暗号化の演算の反転である演算によって実施され、ハードウェア実施態様の観点から非常に有益である。同様に、説明の残りの部分において、表現「本発明の暗号化方法(encryption method of the invention)」は、入力データシーケンスを暗号化する方法および/または復号化する方法を指す。
【００５８】
そのため、ハードウェアおよびソフトウェアでの単純でかつ効率的な実施態様を保証すると同時に最適実行速度によって、任意のサイズの一連の入力ワードによって形成される入力データシーケンスを暗号化すること、および/または、復号化することが可能である。
【００５９】
状態ベクトルの連続する値は、状態ベクトルの初期値および入力データシーケンスの全体に依存する。結果として、状態ベクトルは、駆使可能でなく、また、観測可能でない動的エボリューションを有する。これは、非常にセキュアな暗号化/復号化を保証する。
【００６０】
1つの特定の実施態様では、第1の秘密鍵関数および/または第2の秘密鍵関数は、少なくとも1つの排他的論理和演算を含み、パラメータは、その関数の秘密鍵の少なくとも1つのセクションによって、すなわち、状態ベクトルの直前の値の少なくとも1つのセクションによってセットされる。
【００６１】
本発明の1つの特定の実施態様では、それぞれの状態ベクトルは、サイズkであり、擬似ランダム生成ステップ中、状態ベクトルの現在値を計算するために、状態ベクトルの直前の値のセクションおよび現在中間値から形成されるサイズkの少なくとも1つの第1の中間ベクトルを含むk以上のサイズk1の仮ベクトルに対して、所定の数dのサイズk1の転置が連続して適用され、それぞれの転置は、それぞれ、サイズdの転置鍵のそれぞれの別個のビットに関連し、かつ、少なくともそのビットの値の関数として選択され、上記転置鍵は、第1の中間値のkビットから別個のdビットを選択することの結果として得られ、状態ベクトルの現在値は、適用ステップから得られるベクトルの少なくとも1つのセクションから得られる。
【００６２】
そのため、本発明の暗号化方法は、上述した本発明の擬似ランダム生成方法と同じ利点を有する。本発明の暗号化方法は、さらに、異なる実施形態において、本発明の擬似ランダム生成方法について先に提案された異なる変形を含みうる。
【００６３】
ストリーム暗号化アルゴリズムにおいてこうした擬似ランダム生成方法を使用することは、ハードウェアおよびソフトウェアにおける単純でかつ効率的な(特に、実行速度の点で)実施態様を確保すると同時に、高いレベルのデジタルセキュリティを保証するという利点を有する。
【００６４】
本発明の特に有利な変形では、入力ワードおよび/または出力ワードは、反復の関数として可変の複数ビットを含む。そして、状態ベクトルは、それぞれの反復に関して可変のビットのこの数を示すセクションを含みうる。
【００６５】
状態ベクトルは擬似ランダム変数であるため、暗号化方法は、それぞれの反復に関して、可変サイズの暗号化される入力ワードを処理し、このサイズはまた、入力データシーケンスおよび状態ベクトルの初期値の関数として擬似ランダム方式で変わる。状態ベクトルは暗号化方法の入力および出力ワードから隔離されているため、暗号化方法中に、(サイズの観点から)どの細分が入力ワードのレベルで行われたかを判定することは不可能である。これは、暗号解読に対するさらに良好な保護を提供する。
【００６６】
本発明のこの特定の実施態様では、それぞれの反復の擬似ランダム生成ステップは、さらに、状態ベクトルの現在値から、上記可変ビット数がゼロであると判定されると、状態ベクトルの現在値に依存する非可逆的アプリケーションによる、状態ベクトルのその現在値を置換える状態ベクトルの新しい現在値の計算を含む。
【００６７】
そのため、状態ベクトルの一連の値は、暗号化ステップと相互作用することなく、入力または出力ワードのサイズが0に等しいままである限り、「空(empty)」が生成される。換言すれば、擬似ランダム生成ステップ中に行われる演算は、暗号化ステップ中に行われる演算と脱同期化され、さらに多くの保護を提供する。
【００６８】
本発明の1つの特定の実施態様では、
・擬似ランダム生成ステップは、第1の状態ベクトルの現在値を形成する第1の擬似ランダム生成ステップであり、
・上記第1の擬似ランダム生成ステップは、第2の状態ベクトルの現在値を形成する少なくとも1つの第2の擬似ランダム生成ステップと並列に結合され、
・状態ベクトルの現在値は、第1の状態ベクトルの現在値および少なくとも第2の状態ベクトルの現在値に対して排他的論理和演算を適用することの結果である。
【００６９】
そのため、異なる擬似ランダム状態ベクトルが結合され、益々大きなサイクルを生成することによって、連続する擬似ランダム生成データの数学的複雑さが増加する。
【００７０】
本発明の別の実施態様では、暗号化ステップは第1の暗号化ステップであり、第1の暗号化ステップにおいて、
・第1の現在入力ワードおよび状態ベクトルの直前の値の少なくとも1つの第1のセクションに依存する第1の可逆的アプリケーションによって第1の現在出力ワードが、また、
・第1の現在中間値が計算される。
【００７１】
さらに、方法は、さらに、少なくとも1つの第2の暗号化ステップを含み、第2の暗号化ステップにおいて、
・第2の現在入力ワードおよび状態ベクトルの直前の値の少なくとも1つの第2のセクションに依存する第2の可逆的アプリケーションによって第2の現在出力ワードが、また、
・第2の現在中間値が計算され、
・擬似ランダム生成ステップ中に使用される現在中間値は、第1の現在中間値および少なくとも第2の現在中間値を含む。
【００７２】
そのため、複数の信号が、同じ状態ベクトルによって多重化されうり、ハードウェアまたはソフトウェア実施態様を簡略化する。
【００７３】
本発明の別の実施態様では、暗号化方法は、さらに、少なくとも2つの暗号化メッセージブロックを形成するために、平文の少なくとも2つのメッセージブロックを暗号論的に多重化するステップをさらに含み、平文のそれぞれのメッセージブロックは、一連の入力ワードに相当し、上記少なくとも2つの暗号化メッセージブロックは、状態ベクトルの直前の値のセクションの関数としてそれぞれの反復において順序付けられる。
【００７４】
そのため、送信チャネルにおける、Mの暗号化ブロック(結合されたまたは結合されない)の、それぞれの反復に関する順序付けまたはミキシングは、擬似ランダムであり、状態ベクトルの初期値および入力シーケンスの全体に依存する。その結果、入力シーケンスのおける任意の修正がミキシングを修正し、そのため、最適な保護を提供する。
【００７５】
上述したように、本発明は、暗号解読およびブルートフォース攻撃に対して頑健性があり、高速で、ハードウェア実施態様が比較的複雑でない1方向関数に基づく擬似ランダム生成方法を提案する。
【００７６】
同様に、本発明は、さらに、サイズk1の入力ビットのベクトルから出力ビットのベクトルを生成するようになっている暗号論的モジュールを提供し、暗号論的モジュールは、
・入力ベクトルのビットから別個のdビットを選択することによって、所定のサイズdの転置鍵を形成する手段と、
・転置鍵のそれぞれのビットに、少なくともそれぞれのビットの値の関数として選択されるサイズk1の転置を関連付ける手段と、
・上記出力ビットベクトルを得るために、転置鍵のdビットに関連付けられたサイズk1のdの転置を、入力ベクトルに連続して適用する手段と、を含む。
【００７７】
本発明の暗号論的モジュールは、有利には、上述した1方向関数を使用する。
【００７８】
さらに、本発明はまた、サイズkの状態ベクトルであって、状態ベクトルの初期値から反復的に生成される、サイズkの状態ベクトルの一連の値から形成される擬似ランダムデータシーケンスの暗号論的生成器を提供し、上記生成器は、それぞれの反復について上記状態ベクトルの現在値を生成するために、それぞれの反復において、
・上述した暗号論的モジュールであって、直前の反復で生成される状態ベクトルの直前の値の少なくとも1つのセクションから形成されるサイズkの少なくとも1つの第1の中間ベクトルを含む、k以上のサイズk1の仮ベクトルから結果ベクトルを生成するようになっており、上記転置鍵はk以下のサイズdである、上述した暗号論的モジュールと、
・結果ベクトルの少なくとも1つのセクションから上記状態ベクトルの現在値を得る手段と
を使用する手段を含む。
【００７９】
一実施形態では、この生成器は、さらに、それぞれの反復において、
・状態ベクトルの直前の値および入力データブロックから計算される現在中間値を得る手段と、
・セクションが現在中間値によって置換えられた状態ベクトルの直前の値から上記第1の中間ベクトルを形成する手段と
を使用する。
【００８０】
本発明は、さらに、状態ベクトルの初期値および上記入力シーケンスを形成する一連の入力ワードから、状態ベクトルの一連の値および一連の出力ワードを反復的に生成するようになっている入力データシーケンスの暗号化デバイスを提供し、上記暗号化デバイスは、それぞれの反復において、
・現在入力ワードおよび直前の反復で生成された状態ベクトルの直前の値に依存する可逆的アプリケーションによって、上記それぞれの反復について現在出力ワードを計算するようになっている暗号化手段と、
・状態ベクトルの直前の値に少なくとも依存する非可逆的アプリケーションによって、上記それぞれの反復について状態ベクトルの現在値を計算するようになっている擬似ランダム生成器と、を使用する。
【００８１】
本発明によれば、上記暗号化デバイスは、
・可逆的アプリケーションが、少なくとも第1および第2の秘密鍵関数を含み、秘密鍵が、状態ベクトルの直前の値の少なくとも1つのセクションから生成され、
・非可逆的アプリケーションが、状態ベクトルの直前の値および現在入力ワードに依存し、かつ、上記第1の秘密鍵関数または上記第2の秘密鍵関数によって、入力ワードまたは出力ワードから隔離される現在中間値にさらに依存する、
といったものである。
【００８２】
一実施形態では、本発明の暗号化デバイスの擬似ランダム生成器は、上述したように、本発明の擬似ランダムデータシーケンスの暗号生成器である。
【００８３】
本発明の1つの特定の実施形態では、暗号化デバイスは、反復の関数として可変のビット数を含む入力ワードおよび/または出力ワードを処理するようになっており、さらに、状態ベクトルのセクションからそれぞれの反復において可変のビット数を確定する手段を含む。この実施形態では、暗号化デバイスの擬似ランダム生成器は、さらに、状態ベクトルの現在値から、上記可変のビット数がゼロであると判定されると、状態ベクトルの現在値に依存する非可逆的アプリケーションによって状態ベクトルの現在値を置換える状態ベクトルの新しい現在値を計算する手段を含む。
【００８４】
別の実施形態では、暗号化デバイスは、さらに、少なくとも2つの暗号化メッセージブロックを形成するために、平文の少なくとも2つのメッセージブロックを暗号論的に多重化するデバイスを含み、平文のそれぞれのメッセージブロックは、一連の入力ワードに対応し、上記少なくとも2つの暗号化メッセージブロックは、状態ベクトルの直前の値のセクションの関数としてそれぞれの反復において順序付けられる。
【００８５】
本発明は、さらに、所定の数Mのデータブロックを含むメッセージからダイジェストを生成するようになっている暗号論的ハッシングデバイスを提供し、上記ハッシングデバイスは、
・Mの連続する反復において状態ベクトルの一連のMの値を生成する、上述した本発明による暗号論的生成器と、
・Mの連続する反復のそれぞれの反復において、
・メッセージの現在データブロック、および、暗号論的生成器によって生成された状態ベクトルの直前の値から、それぞれの反復について現在中間値を計算し、
・現在中間値を暗号論的生成器に供給する
手段と、
・上記生成器によって生成された状態ベクトルの最新の値からメッセージのダイジェストを得る手段と、を含む。
【００８６】
さらに、1つの特定の実施形態では、本発明の暗号論的生成器および/または暗号化デバイスおよび/または暗号論的ハッシングデバイスは、データバスによって相互接続されたメモリ、入力ユニット、および出力ユニットを信号によって制御する中央プロセッサユニットを慣例的に含む1つまたは複数のデータ処理システムによって実施されうることが留意されるべきである。
【００８７】
そのため、本発明は、また、プログラムコード命令を含むコンピュータプログラムであって、上記プログラムが、コンピュータまたはデータ処理システムにロードされ、コンピュータまたはデータ処理システムで実行されると、上記特徴の任意の特徴を有する暗号論的方法を実行するための、コンピュータプログラム、プログラムコード命令を含むコンピュータプログラムであって、上記プログラムが、コンピュータまたはデータ処理システムにロードされ、コンピュータまたはデータ処理システムで実行されると、上記特徴の任意の特徴を有する暗号化方法を実行するための、コンピュータプログラム、および、上記プログラムが、コンピュータまたはデータ処理システムにロードされ、コンピュータまたはデータ処理システムで実行されると、上記特徴の任意の特徴を有する暗号論的ハッシング方法を実行するための、コンピュータプログラムを提供する。
【００８８】
これらのコンピュータプログラムは、コンピュータ読取り可能媒体上に格納され、また、マイクロプロセッサによって実行可能でありうる。
【００８９】
これらのコンピュータプログラムは、任意のプログラミング言語を使用し、また、部分的にコンパイルされた形態または任意の他の所望の形態などの、ソースコードの形態、オブジェクトコードの形態、またはソースコードとオブジェクトコードとの中間のコードの形態をとりうる。
【００９０】
本発明はまた、上述したコンピュータプログラム命令を含むコンピュータ読取り可能情報媒体を提供する。
【００９１】
本発明の他の特徴および利点は、非制限的な例証によって以下で与えられる説明を読むことによって、また、添付図面を参照して明らかになる。
【図面の簡単な説明】
【００９２】
【図１Ａ】擬似ランダムデータシーケンスを生成するための、本発明の1つの特定の実施形態における擬似ランダム生成器の線図である。
【図１Ｂ】擬似ランダムデータシーケンスを生成するための、本発明の1つの特定の実施形態における擬似ランダム生成器の線図である。
【図２】入力データシーケンスを暗号化するための、本発明の特定の実施形態のデバイスの例の線図である。
【図３】入力データシーケンスを暗号化するための、本発明の特定の実施形態のデバイスの例の線図である。
【図４】入力データシーケンスを暗号化するための、本発明の特定の実施形態のデバイスの例の線図である。
【図５】入力データシーケンスを暗号化するための、本発明の特定の実施形態のデバイスの例の線図である。
【図６】入力データシーケンスを暗号化するための、本発明の特定の実施形態のデバイスの例の線図である。
【図７】入力データシーケンスを暗号化するための、本発明の特定の実施形態のデバイスの例の線図である。
【図８】入力データシーケンスを暗号化するための、本発明の特定の実施形態のデバイスの例の線図である。
【図９Ａ】先の図からの擬似ランダム生成器または暗号化デバイス、または、図14からの暗号論的ハッシングデバイスで使用される転置の例を示す図である。
【図９Ｂ】先の図からの擬似ランダム生成器または暗号化デバイス、または、図14からの暗号論的ハッシングデバイスで使用される転置の例を示す図である。
【図９Ｃ】先の図からの擬似ランダム生成器または暗号化デバイス、または、図14からの暗号論的ハッシングデバイスで使用される転置の例を示す図である。
【図９Ｄ】先の図からの擬似ランダム生成器または暗号化デバイス、または、図14からの暗号論的ハッシングデバイスで使用される転置の例を示す図である。
【図９Ｅ】先の図からの擬似ランダム生成器または暗号化デバイス、または、図14からの暗号論的ハッシングデバイスで使用される転置の例を示す図である。
【図１０Ａ】図9Cの転置のハードウェア実施態様の例を示す図である。
【図１０Ｂ】図9Cの転置のハードウェア実施態様の例を示す図である。
【図１１Ａ】暗号論的多重化の例を示す図である。
【図１１Ｂ】暗号論的多重化の例を示す図である。
【図１１Ｃ】暗号論的多重化の例を示す図である。
【図１２】暗号論的多重化に対する本発明の暗号化デバイスの適用を示す図である。
【図１３】暗号論的多重化に対する本発明の暗号化デバイスの適用を示す図である。
【図１４】本発明の1つの特定の実施形態の暗号論的ハッシングデバイスの1つの例の線図である。
【図１５Ａ】(既に述べた)従来技術の2つの暗号化メカニズムの線図である。
【図１５Ｂ】(既に述べた)従来技術の2つの暗号化メカニズムの線図である。
【発明を実施するための形態】
【００９３】
予備的ノートおよび表記
特に有利である方法で、本発明は、構成可能な(または、パラメータ化可能な)転置関数P、すなわち、セットされうるパラメータを有する関数であって、以下で説明する様々な暗号論的アプリケーションで、特に、擬似ランダム生成のため、暗号化/復号化データのため、およびメッセージを暗号論的にハッシングするために使用されうる、セットされうるパラメータを有する関数を提案する。
【００９４】
この転置関数Pは、転置関数Pが適用されるデータのサイズの関数としてセットされたパラメータを有しうり、また、いわゆる転置鍵によってセットされたパラメータを有する。そのため、表記法
S=P(E,C)
が使用されて、転置鍵Cによってセットされたパラメータを有する転置関数Pが、出力データSを得るために入力データEに適用されることが指定される。
【００９５】
一般的に言えば、サイズeの入力データEおよびe以下のサイズpの転置鍵Cについて、転置関数Pは、サイズeの連続するpの転置を入力データEに適用することの結果であり、それぞれの転置は、転置鍵Cの1ビットに関連し、かつ、少なくともそのビットの値の関数として選択される。
【００９６】
たとえば、そのビットが0である場合に転置P0が、そのビットが1である場合に転置P1が、転置鍵のそれぞれのビットに、すなわち、転置関数の転置ステージに関連付けられる。
【００９７】
同じ転置対(P0,P1)が、転置関数Pの種々のステージにおいて考えられうる。そして、これらの転置P0およびP1は、好ましくは、互いに全ての点で異なるものとして、また、それぞれが全ての点で恒等転置と個々に異なるものとして規定される。しかし、これらの仮定は、本発明を制限するどんな状況下にもなく、また、異なる転置対が、転置関数のそれぞれのステージで考えられうり、または、たとえば、転置P0およびP1を構成することによって得られる転置は、転置P1およびP0を構成することによって得られる転置と全ての点で異ならなければならないという他の条件が、転置P0およびP1に適用される。
【００９８】
転置関数Pは、考えられる転置鍵に従って異なる特性を有する。
【００９９】
そのため、転置鍵Cが、転置関数Pが適用される入力データと独立のデータから形成される場合、全単射的な(または、鍵転置)関数が得られる。すなわち、関数Pは、転置鍵の値がわかっている、すなわち、この鍵によってセットされたパラメータを有する関数Pの入力データの値に対して、出力データのただ1つの値が対応する場合に限り可逆的である
【０１００】
転置関数Pのこの特性は、本発明の暗号化/復号化デバイスおよび暗号論的ハッシングデバイスに関連するいくつかの実施形態において特に考えられる。
【０１０１】
転置鍵Cが、転置関数Pが適用される入力データEから形成される場合(換言すれば、転置鍵が、入力データEの全体または一部に依存する場合)、1方向関数が得られる。すなわち、関数Pは、非可逆的である、換言すれば、1つの方向に計算することが容易であるが、適度な時間内で(すなわち、適度な複雑さを持って)反転することが難しいかまたはさらに不可能である。
【０１０２】
こうして(すなわち、転置関数が適用される入力データに依存する転置鍵によって)セットされたパラメータを有するこうした転置関数、ましてや、こうした転置関数に基づく1方向関数は、従来技術において提案されていない。
【０１０３】
転置関数Pのこの特性は、本発明の異なる実施形態において暗号論的モジュールおよび擬似ランダムシーケンスの暗号論的生成器(擬似ランダム生成器)のために特に考えられる。
【０１０４】
説明の残り部分において、転置関数Pの特性の関数としての転置関数Pの適用を区別するために、表現「全射的転置手段(surjective permutation means)」は、転置関数Pが1方向関数であるときに転置関数Pを実施する(implement)手段を指す(簡潔にするために以下で「全射的転置(surjective permutation)」とも呼ばれる)。その結果、全射的転置は、非可逆的である(すなわち、全単射的である)として理解されなければならない。それは、全射的転置が、1方向、すなわち、非可逆的関数の文脈で使用され、1方向関数の文脈で、異なる入力データE1、E2、…は、同じ出力S(たとえば、S=P(E1,E1)=P(E2,E2)=…、ただし、E1≠E2≠…)を有しうる。
【０１０５】
同様に、表現「全単射的転置手段(bijective permutation means)」は、転置関数Pが、全単射的関数、換言すれば、全単射的鍵転置であるときに転置関数Pを実施する手段を指す(簡潔にするために以下で「全単射的転置(bijective permutation)」とも呼ばれる)。
【０１０６】
転置関数Pの特徴および転置関数Pを実施する手段は、以下で、特に、図9A〜9E、10A、および10Bを参照してより詳細に説明される。これらの特徴および実施手段は、転置関数P(転置関数Pが1方向関数であれ、全単射的関数であれ)を使用する、以下で述べる種々のデバイスおよび手段に適用される。
【０１０７】
擬似ランダム生成方法および生成器
図1は、擬似ランダムデータシーケンス3を生成するための、本発明の擬似ランダム生成器1の例を線図で表す。図1Bは、この擬似ランダム生成器の1つの特定の実施形態を示す。図1Aおよび1Bはまた、擬似ランダムデータシーケンスを生成する本発明の方法の原理的なステップを示すことに留意されたい。
【０１０８】
擬似ランダム生成器1は、状態ベクトルVの初期値V0から始めて、状態ベクトルの一連の値V0、…、Vn-1、Vn、…の反復的な生成によって擬似ランダムデータシーケンス3を形成する計算手段5を含む。Vnは、n番目の反復に関して状態ベクトルVによってとられる値に相当することに留意されたい。同じ慣行が、他の変数について同様な方法で使用される。
【０１０９】
状態ベクトルVは、特定の数kのビットを含む(すなわち、状態ベクトルVはサイズkのベクトルであり、kは1以上の整数である)。
【０１１０】
擬似ランダム生成プロセスのそれぞれの反復nに関して、計算手段5は、状態ベクトルの直前の値Vn-1に依存する非可逆的アプリケーションを使用して状態ベクトルVの現在値Vnを計算する。この非可逆的アプリケーションは、サイズd≦kの転置鍵によってセットされたパラメータを有する1方向関数に基づく。
【０１１１】
本明細書で想定される例では、状態ベクトルは、有利には、それぞれの反復nに関して、別のアプリケーション、たとえば、状態ベクトルの直前の値Vn-1および入力データシーケンス(本発明の意味で入力データブロック)に属する現在入力ワードUnに依存しうるアプリケーションATによって計算される現在中間値Xαを供給される。本明細書で述べる例では、入力ワードUnは特定数mのビットを含む(サイズmのワード)。ここで、mは1以上の整数である。現在中間値Xαはmビットを含む(サイズmのベクトル)。
【０１１２】
アプリケーションATの例は、特に図2〜12(アプリケーションATは暗号化/復号化モジュールである)および図14(アプリケーションATは、暗号論的ハッシングデバイスのプレコンディショニングモジュールである)を参照して以下で述べられる。
【０１１３】
図1Bを参照すると、擬似ランダム生成器1および本発明の1つの特定の実施態様の擬似ランダム生成方法においてそれぞれ実行される主要な手段および主要なステップが、図1Bを参照して以下で述べられる。
【０１１４】
第1の反復に関して、擬似ランダム生成器1は、第1の入力ワードU1(現在中間値Xαを使用して)および状態ベクトルの初期値V0の関数として状態ベクトルVの第1の値V1を計算する。
【０１１５】
拡張によって、n番目の反復に関して、擬似ランダム生成器1は、現在入力ワードUn(現在中間値Xαを使用して)および状態ベクトルの直前の値Vn-1の関数として状態ベクトルVの現在値Vnを計算する。
【０１１６】
この例では、擬似ランダム生成器1は、送信手段321、受信手段323、ならびに計算手段325a、325b、325c、326、および327を含む。
【０１１７】
それぞれの反復に関して(たとえば、反復nに関して)、送信手段321は、アプリケーションATに状態ベクトルの直前の値Vn-1を送出する。受信手段323は、アプリケーションATから現在中間値Xαを受信する。
【０１１８】
第1の計算手段325aは、状態ベクトルの直前の値Vn-1のサイズmのセクションXn-1を現在中間値Xαで置換えて、第1の中間状態ベクトルVint1の値を形成する。
【０１１９】
本明細書で述べる例では、第2の計算手段325bは、第1の中間状態ベクトルVint1の現在値および第1の中間状態ベクトルVint1の、
【０１２０】
【数６】
0005551065.tif 000007
【０１２１】
と書かれる相補的ベクトルの現在値から、k以上のサイズk1の仮ベクトルVprovの現在値を形成する(すなわち、本発明の意味で、仮ベクトルVprovはベクトルVint1および
【０１２２】
【数７】
0005551065.tif 000008
【０１２３】
を含む)。当技術分野で知られているように、ベクトルの相補的ベクトルは、そのベクトルのそれぞれのビットの1の補数を求めることによって得られる。
【０１２４】
ここで、こうして得られる仮ベクトルの現在値は、
【０１２５】
【数８】
0005551065.tif 000009
【０１２６】
である。
【０１２７】
そして、仮ベクトルは、サイズk1=2kである。
【０１２８】
あるいは、この仮ベクトルは、Vint1に等しく(すなわち、第2の計算手段325bはなしで済まされうる)、サイズkでありうる。こうしたオプションに相当する実施形態は、特に図3Aに示され、以下でより詳細に述べられる。
【０１２９】
仮ベクトルの現在値は、その後、結果ベクトルVresの現在値を生成するために1方向関数を仮ベクトルの現在値に適用するようになっている全射的転置手段326aを備える第3の計算手段326に供給される。全射的転置手段326aによって適用される1方向関数は、k以下の所定のサイズd(すなわち、p=d)の転置鍵Cによってセットされたパラメータを有する、上述した構成可能な転置関数Pに基づく。ここで、行われる選択はd=kである。
【０１３０】
1方向関数の転置鍵Cの現在値は、第1の中間状態ベクトルの現在値から形成手段326bによって形成される。本明細書で述べる例では、現在値Cは、第1の中間状態ベクトルの現在値に等しいC=Vint1として考えられる。
【０１３１】
以下では、簡潔にするために、Cおよび用語「鍵(key)」は、反復nについての転置鍵の現在値および転置鍵それ自体(すなわち、ランダム変数)について交換可能に使用される(すなわち、ランダム変数)。
【０１３２】
あるいは、本発明の別の実施態様では、鍵のサイズdは、kより完全に小さくありうる。転置鍵Cは、その後、第1の中間ベクトルVint1のkビットから、別個のdビット(連続的かまたはそうでない)を選択する手段326bによって形成される。選択されるdビットの位置は、好ましくは予め規定されまた固定される。転置鍵のサイズdは、好ましくは、中間現在値Xαのサイズより大きくされ、選択されるdビットは、好ましくは、中間現在値Xαを含む。
【０１３３】
ここで、全射的転置手段326bによって適用される1方向関数は、したがって、サイズk1=2k(すなわち、e=k1=2k)のd=kの連続する転置を適用することの結果であり、それぞれの転置は、転置鍵C=Vint1の別個のビットに関連し、かつ、少なくともこのビットの値の関数として(たとえば、図10aおよび10bを参照して以下で述べるように、予め規定された転置テーブルにおいて)選択される。あるいは、1方向関数はまた、関係する転置ステージに依存しうる。
【０１３４】
転置鍵C=Vint1が、転置関数Pが適用されるデータに依存するため(
【０１３５】
【数９】
0005551065.tif 000010
【０１３６】
であるため)、Pは1方向関数を規定する。この適用ステップ後に得られる結果ベクトルVresはサイズk1=2kである。
【０１３７】
本発明の意味で、計算手段326は、したがって、暗号論的モジュールからなる。
【０１３８】
本明細書で述べる実施形態では、擬似ランダム生成器1の計算手段5は、さらに、第2の中間ベクトルVint2の現在値を形成するために、結果ベクトルVresの現在値のk1ビットからkビットのセクションを選択する第4の計算手段325cを含む。たとえば、第2の中間ベクトルVint2は、結果ベクトルVresの最初のkビットによって形成される。
【０１３９】
さらに、本明細書の擬似ランダム生成器1の計算手段5は、さらに、状態ベクトルの直前の値Vn-1と第2の中間状態ベクトルVint2の現在値を結合する排他的論理和ゲート327aを含む第5の計算手段327を含む。非可逆的であることに加えて、この排他的論理和演算は、擬似ランダム生成器1に関するより大きな拡散を与える。
【０１４０】
本発明の別の実施形態では、第5の計算手段327の排他的論理和ゲート327aは、第2の中間状態ベクトルVint2の現在値を第1の中間状態ベクトルVint1の現在値と結合する。
【０１４１】
本発明のさらなる実施形態では、状態ベクトルVの現在値Vnは、第2の中間状態ベクトルVint2の現在値に相当する。
【０１４２】
反復nの上記演算後に、状態ベクトルVの現在値Vnは、次の反復n+1について利用可能である。
【０１４３】
図1Bに示す例では、現在中間値Xαは、第1の中間状態ベクトルVint1の現在値を形成するために、状態ベクトルの直前の値Vn-1の連続するmビットからなるセクションXn-1を置換える。しかし、この仮定は、本発明を制限せず、また、第1の中間状態ベクトルVint1の現在値を形成するために、状態ベクトル内の、必ずしも連続的でない特定のmの位置を占めるVn-1のセクションXn-1のmビットを、現在中間値Xαのmの成分で置換えることがもちろん同様に可能である。
【０１４４】
暗号化方法およびデバイス
図2〜12は、図1A(その特定の実施態様が、図1Bに例として示される)で線図で示す擬似ランダム生成器1が、一連の入力ワードを暗号化する、かつ/または、復号化するために、暗号化/復号化モジュールと結合して使用されうることを示す。図2〜12はまた、入力データシーケンスを暗号化する方法の主要なステップを示すことに留意されたい。この状況では、現在中間値Xαは、擬似ランダム生成器の適用と独立の適用によって、暗号化/復号化モジュールによって計算されうる。
【０１４５】
図2は、本発明の1つの特定の実施形態において入力データシーケンス9(または15)を暗号化し(かつ/または復号化する)デバイス7を示す。このデバイス7は、状態ベクトルの初期値V0および入力シーケンスを形成する一連の入力ワードUn(またはYn)から状態ベクトルの一連の値13および一連の出力ワード15(または9)を反復的に生成する生成手段11を含む。
【０１４６】
状態ベクトルVは、サイズkの構成可能な暗号化/復号化鍵に相当する状態ベクトルの所定の数kのビットおよび初期値V0を含む。暗号化/復号化鍵のサイズkは、鍵のビット数、そのため、状態ベクトルVのビット数に相当する。
【０１４７】
さらに、入力または出力ワードUn/Ynは、それぞれの反復に関して暗号化/復号化モジュール17によって暗号化されるかまたは復号化されるビット数に相当するサイズmである。これらの値kおよびmは、予め規定されうる。
【０１４８】
入力または出力ワードのサイズが可変でありうる実施形態は、図7および8を参照して以下で詳細に述べられる。
【０１４９】
本明細書で想定される例では、生成手段11は、図1Aに示す本発明の擬似ランダム生成器1(たとえば、図1Bからの擬似ランダム生成器)および暗号化/復号化モジュール17を含む。あるいは、他の擬似ランダム生成器、たとえば、当業者に知られている、高度暗号化標準(advanced-encryption standard)(AES)アルゴリズムに基づく擬似ランダム生成器、ブラムブラムシャブ(Blum Blum Shub)(BBS)アルゴリズムに基づく擬似ランダム生成器、またはシフトレジスタに基づく擬似ランダム生成器が、本発明の暗号化デバイスおよび方法を実施するために使用されうる。
【０１５０】
相応して、それぞれの反復nに関して、擬似ランダム生成器1は、状態ベクトルの直前の値Vn-1、および、暗号化/復号化モジュール17によって実行される計算によって生成され、かつ、状態ベクトルの直前の値Vn-1および現在入力ワードUn(またはYn)に依存する現在中間値Xαに依存する非可逆的アプリケーションによって状態ベクトルの現在値Vnを計算し、暗号化/復号化モジュール17は、現在入力ワードUn(またはYn)および状態ベクトルの直前の値Vn-1に依存する可逆的アプリケーションによって現在出力値Yn(またはUn)を計算する。
【０１５１】
暗号化デバイス7は、暗号化および/または復号化のために可逆的に使用されうることに留意されたい。上述したように、本発明の暗号化方法は、入力ワードのシーケンスが、暗号化される平文にメッセージからのものであるとき暗号化モードで使用されうる、または、出力ワードのシーケンスが、復号化される暗号化メッセージからのものであるとき復号化モードで使用されうる
【０１５２】
本例では、それぞれの反復nに関して、擬似ランダム生成器1は、状態ベクトルに、暗号化/復号化モジュール17によって実行される計算によって生成され、かつ、状態ベクトルの直前の値Vn-1および現在入力ワードUn(またはYn)に依存する現在中間値Xαを供給する。
【０１５３】
上述したように、擬似ランダム生成器1は、転置鍵によってセットされたパラメータを有する1方向関数に基づく非可逆的アプリケーションを使用し、また、同じ方法で暗号化および復号化を実施するために使用されうる。さらに、暗号化/復号化モジュール17は、可逆的であり、したがって、逆の順序で行われる暗号化/復号化演算に関して使用されうる。そのため、暗号化中、入力ワードはUn(平文のデータ)が書かれ、出力ワードはYn(暗号化データ)が書かれ、一方、復号化中、入力ワードはYn(暗号化データ)が書かれ、出力ワードはUn(平文のデータ)が書かれる。
【０１５４】
より具体的には、本発明の暗号化方法による暗号化を開始する前に、暗号化鍵の値が、状態ベクトルVの初期値V0になる(V0=暗号化鍵)。
【０１５５】
第1の反復に関して、暗号化/復号化モジュール17は、第1の入力ワードU1(平文のワードに相当する)および状態ベクトルの初期値V0の関数として第1の出力ワードY1(暗号化ワードに相当する)を計算する。さらに、擬似ランダム生成器1は、第1の入力ワードU1および状態ベクトルの初期値V0の関数として状態ベクトルVの第1のベクトルV1を計算する。拡張によって、n番目の反復に関して、暗号化/復号化モジュール17は、現在入力ワードUnおよび状態ベクトルの直前の値Vn-1の関数として現在出力ワードYnを計算する。さらに、擬似ランダム生成器1は、現在入力ワードUnおよび状態ベクトルの直前の値Vn-1の関数として状態ベクトルVの現在値Vnを計算する。
【０１５６】
同じ方法で、本発明の暗号化方法による復号化を開始する前に、復号化鍵の値が、状態ベクトルVの初期値V0になる(V0=復号化鍵)。復号化鍵は、もちろん、データを暗号化するの(対称暗号化)に使用される暗号化鍵に等しいと考えられる。
【０１５７】
復号化プロセスの第1の反復に関して、暗号化/復号化モジュール17は、第1の入力ワードY1(暗号化ワードに相当する)および状態ベクトルの初期値V0の関数として第1の出力ワードU1(復号化ワードに相当する)を計算する。さらに、擬似ランダム生成器1は、第1の入力ワードY1および状態ベクトルの初期値V0の関数として状態ベクトルVの第1の値V1を計算する。拡張によって、n番目の反復に関して、暗号化/復号化モジュール17は、現在入力ワードYnおよび状態ベクトルの直前の値Vn-1の関数として現在出力ワードUnを計算する。さらに、擬似ランダム生成器1は、現在入力ワードYnおよび状態ベクトルの直前の値Vn-1の関数として状態ベクトルVの現在値Vnを計算する。
【０１５８】
本明細書で述べる例では、状態ベクトルVは、有利には、少なくとも、第1の状態変数X、第2の状態変数A、第3の状態変数B、およびおそらくは他の状態変数を含むセクションのセットを含む。これらの状態変数は、したがって、擬似ランダム変数である。たとえば、状態ベクトルVの現在値Vnは、
Vn=(…(Xn=(xn1…xnm))…(An=(an1…anm))…(Bn=(bn1…bnm))…)
であるように構築されうる。
【０１５９】
状態変数X、A、およびBの値はまた、本発明の意味で、状態値のセクションまたは状態ベクトルの値のセクションとして考えられることになる。
【０１６０】
この例では、状態変数X、A、およびBの値は、それぞれが連続するmビットからなるセクションである。第1の状態変数Xの現在値Xnは、mビットXn1、…、Xnmを含み、第2の状態変数Aの現在値Anは、mビットAn1、…、Anmを含み、第3の状態変数Bの現在値Bnは、mビットBn1、…、Bnmを含む。
【０１６１】
より具体的には、第1の状態変数Xの現在値Xnは、暗号化/復号化モジュール17によって次の反復で行われる計算によって生成される中間値Xαによって置換えられる前に、暗号化/復号化モジュール17の「隔離(isolation)」関数(または手段)と呼ばれる関数(または手段)によって次の反復において使用される。第2および第3の状態変数の値AnおよびBnもまた、暗号化/復号化モジュール17の隔離関数によって次の反復中に使用される(たとえば図3Aおよび3Bを参照されたい)。
【０１６２】
状態変数は、好ましくは、固定位置に位置するが、それ自体固定位置の状態変数を、状態ベクトルの1つまたは複数のセクションによってとられる1つまたは複数の値の関数として可変の位置に割当てることが可能である。状態変数の固定位置の解決策だけが以下で述べられる。
【０１６３】
さらに、状態変数のそれぞれに割当てられるセクタがオーバラップしないことが(必要ではないが)好ましい。状態ベクトルのサイズkは、したがって、相応して選択され、それぞれの状態変数は、制限されたサイズの(すなわち、状態ベクトルのサイズより完全に小さいサイズの)状態ベクトルのセクションに相当する。
【０１６４】
図3Aは、図2からの暗号化/復号化デバイス7の第1の例をより詳細に示す。
【０１６５】
この第1の例では、擬似ランダム生成器1は、送信手段21、受信手段23、ならびに計算手段25、26、およびおそらく27を含む。
【０１６６】
それぞれの反復に関して(たとえば、反復nに関して)、送信手段21は、暗号化/復号化モジュール17に、第1の状態変数Xの直前の値Xn-1、第2の状態変数Aの直前の値An-1、および第3の状態変数Bの直前の値Bn-1を少なくとも含む状態ベクトルの直前の値Vn-1を送出する。
【０１６７】
受信手段23は、暗号化/復号化モジュール17から現在中間値Xαを受信する。
【０１６８】
第1の計算手段25は、第1の中間状態ベクトルVint1の現在値を計算するために、第1の状態変数Xの直前の値Xn-1を、現在中間値Xαによって置換える。
【０１６９】
第2の計算手段26は、第2の中間状態ベクトルVint2を形成するために、第1の中間状態ベクトルVint1の現在値を含むサイズd=kの転置鍵C(C= Vint1)によってセットされたパラメータを有する1方向関数を、第1の中間状態ベクトルVint1に適用するようになっている全射的転置手段26aを備える。第2の計算手段26は、上述した計算手段326と同様の方法で(ベクトルのサイズは別にして)機能し、本発明の意味で暗号論的モジュールを構成する。
【０１７０】
計算手段26aによって適用される1方向関数は、上述した構成可能な転置関数Pに基づき(p=d=kおよびe=k)、したがってここでは、サイズkの連続するkの転置を適用することの結果であり、それぞれの転置は、転置鍵C=Vint1の別個のビットに関連し、かつ、少なくともそのビットの値の関数として選択される。
【０１７１】
相応して、手段26aは、第2の中間状態ベクトルVint2の現在値を形成するために、第1の中間状態ベクトルVint1の現在値によってセットされたパラメータを有する1方向関数P=(Vint1,Vint1)を、第1の中間状態ベクトルに適用する。この第1の例では、本発明の意味で、第1の中間値または(respectively)第2の中間値は、したがって、仮ベクトルまたは結果ベクトルを表す。ベクトルVint1およびVint2は共にサイズkであることに留意されたい。状態ベクトルVの現在値Vnは、したがって、第2の中間状態ベクトルVint2の現在値に相当する。
【０１７２】
(図3Aにおいて点線で示す)別の変形では、擬似ランダム生成器1の計算手段5は、さらに、第1の中間状態ベクトルVint1の現在値と第2の中間状態ベクトルVint2の現在値を結合する排他的論理和ゲート27aを含む第3の計算手段27を含む。
【０１７３】
別の変形(図示せず)では、第3の計算手段27は、状態ベクトルの直前の値Vn-1と第2の中間状態ベクトルVint2の現在値を結合する排他的論理和ゲート27aを含む
【０１７４】
そのため、擬似ランダム生成器1の計算手段5は、第1の中間状態ベクトルVint1に関して1方向(すなわち、非可逆的)関数を実行し、その結果が、任意選択で、この第1の中間状態ベクトルVint1または直前の反復の状態ベクトルに結合される。
【０１７５】
反復nの上記演算後に、状態ベクトルVの現在値Vnは、次の反復n+1について利用可能である。
【０１７６】
さらに、暗号化/復号化モジュール17は、受信手段33、隔離手段35aおよび35b、ならびに、本明細書で述べる例では、隔離手段35aと35bとの間の接続手段37を含む。
【０１７７】
受信手段33は、擬似ランダム生成器1から、第1の状態変数Xの直前の値Xn-1、第2の状態変数Aの直前の値An-1、および第3の状態変数Bの直前の値Bn-1を少なくとも含む状態ベクトルの直前の値Vn-1を受信する。
【０１７８】
隔離手段は、現在中間値Xαを隔離する少なくとも2つの隔離手段35aおよび35bを備える。
【０１７９】
隔離手段は、対称「秘密鍵(secret key)」関数を適用し、秘密鍵は、状態ベクトルの直前の値の少なくとも1つのセクションから得られる。当業者が知るように、対称秘密鍵関数は、入力の関数として出力を、また、出力の関数として入力を計算することが、秘密鍵が入手可能である場合容易であり、秘密鍵がわからない場合不可能である関数である。
【０１８０】
使用される秘密鍵関数は、好ましくは、少なくとも1つの排他的論理和演算を含む。すなわち、隔離手段は少なくとも1つの排他的論理和ゲートを含む。使用される秘密鍵関数は、さらに、全単射的転置手段を含む。
【０１８１】
本明細書で述べる例(図5Aを参照されたい)では、隔離手段は、それぞれ、排他的論理ゲートおよび2つの全単射的転置手段を含み、接続手段37は、排他的論理和ゲートを含む。そのため、本発明の意味でそれぞれの隔離手段で使用される秘密鍵関数は、それぞれが、状態ベクトルVn-1のサイズmのセクションによってセットされたパラメータを有する、2つの全単射的転置および1つの排他的論理和演算で構成される。この関数の秘密鍵は、第1の全単射的転置のパラメータをセットするセクション、排他的論理和演算のパラメータをセットするセクション、および第2の全単射的転置のパラメータをセットするセクションで構成される。
【０１８２】
そのため、暗号化デバイス7は、2つの相互接続された要素、すなわち、状態ベクトルVを初期化するのに使用される任意のサイズkの暗号化/復号化鍵によってセットされたパラメータを有する擬似ランダム生成器1、および、秘密鍵隔離関数を組込む暗号化/復号化モジュール17を含む。
【０１８３】
図3Bは、図1Bに示す擬似ランダム生成器1を使用する、図2からの暗号化デバイス7の第2の例を示す。このデバイス7の演算モードおよび関連する変形は、図3Aを参照して上述したものと同様である。
【０１８４】
図5Aおよび6Aは、図3Aの擬似ランダム生成器1が使用されるときに、入力データシーケンスを暗号化しまた復号化する方法をより詳細に示す。
【０１８５】
より具体的には、図5Aは、入力データシーケンスが平文のメッセージに相当し、一連の出力ワードが暗号化メッセージに相当する暗号化モードにある暗号化デバイス7を示す。本例では、第1の隔離手段35aと第2の隔離手段35bとの間の接続手段37は、中央排他的論理和ゲート41bを含む。
【０１８６】
第1の隔離手段35aは、第1の排他的論理和ゲート41aによって分離された第1および第2の全単射的転置手段39a、39bを含む。第2の隔離手段35bは、第2の排他的論理和ゲート41cによって分離された第3および第4の全単射的転置手段39c、39dを含む。
【０１８７】
本明細書で考えられる全単射的転置手段39a、39b、39c、39dはそれぞれ、状態ベクトルVn-1の状態変数によって、すなわち、状態ベクトルVn-1の状態変数に等しいサイズm(p=m)の転置鍵によってセットされたパラメータを有する、上述した転置関数Pを実施する。相応して、
・第1の全単射的転置手段39aは、第2の状態ベクトルAn-1の直前の値に等しい転置鍵によってセットされたパラメータを有する転置関数Pに相当する第1の全単射的転置を実施し、
・第2の全単射的転置手段39bは、第1の状態ベクトルXn-1の直前の値に等しい転置鍵によってセットされたパラメータを有する転置関数Pに相当する第2の全単射的転置を実施し、
・第3の全単射的転置手段39cは、第1の状態ベクトルXn-1の直前の値に等しい転置鍵によってセットされたパラメータを有する転置関数Pに相当する第3の全単射的転置を実施し、
・第4の全単射的転置手段39dは、第3の状態ベクトルBn-1の直前の値に等しい転置鍵によってセットされたパラメータを有する転置関数Pに相当する第4の全単射的転置を実施する。
【０１８８】
得られる転置関数Pが適用されるデータと独立である、全単射的転置手段39a、39b、39c、および39dにおける転置関数Pのパラメータをセットするのに使用される転置鍵が適用され、したがって、それぞれは、その反転関数が転置関数P-1である可逆的(全単射的)関数を実施する。この可逆的関数Pは、関係する転置鍵のそれぞれのビットの値の関数として選択されるサイズm(p=e=m)の連続するmの転置を適用することの結果である。
【０１８９】
そのため、この暗号化モードでは、反復nの間に現在出力ワードYnを計算することは、以下の演算を含む。
【０１９０】
第1の転置手段39aは、第1の全単射的転置を、現在入力ワードUnおよび第2の状態変数の直前の値An-1からなる対に適用することによって第1の中間ワードG1nを計算する:G1n=P(Un,An-1)。換言すれば、第1の転置手段39aは、現在入力ワードUnに、An-1によってセットされたパラメータを有する全単射的転置関数Pを適用することによって第1の中間ワードG1nを計算する。
【０１９１】
第1の排他的論理和ゲート41aは、排他的論理和演算を第1の中間ワードG1nおよび第2の状態変数の直前の値An-1に適用することによって第2の中間ワードG2nを計算する:
【０１９２】
【数１０】
0005551065.tif 000011
【０１９３】
。
【０１９４】
第2の転置手段39bは、第2の全単射的転置を、第2の中間ワードG2nおよび第1の状態変数の直前の値Xn-1からなる対に適用することによって第3の中間ワードG3nを計算する:G3n=P(G2n,Xn-1)。換言すれば、第2の転置手段39bは、第2の中間ワードG2nに、Xn-1によってセットされたパラメータを有する全単射的転置関数Pを適用することによって第3の中間ワードG3nを計算する。
【０１９５】
中央排他的論理和ゲート41bは、排他的論理和演算を、第3の中間ワードG3nおよび第1の状態変数の直前の値Xn-1に適用することによって現在中間値Xαを計算する:
【０１９６】
【数１１】
0005551065.tif 000012
【０１９７】
。この現在中間値Xαは、その後、擬似ランダム生成器1に送出される。
【０１９８】
第3の転置手段39cは、第3の全単射的転置を、現在中間値Xαおよび第1の状態変数の直前の値Xn-1からなる対に適用することによって第4の中間ワードG4nを計算する:G4n=P(Xα,Xn-1)。換言すれば、第3の転置手段39cは、現在中間値Xαに、Xn-1によってセットされたパラメータを有する全単射的転置関数Pを適用することによって第4の中間ワードG4nを計算する。
【０１９９】
第3の排他的論理和ゲート41cは、排他的論理和演算を、第4の中間ワードG4nおよび第3の状態変数の直前の値Bn-1に適用することによって第5の中間ワードG5nを計算する:
【０２００】
【数１２】
0005551065.tif 000013
【０２０１】
。
【０２０２】
最後に、第4の転置手段39dは、第4の全単射的転置を、第5の中間ワードG5nおよび第3の状態変数の直前の値Bn-1からなる対に適用することによって現在出力ワードYnを計算する:Yn=P(G5n,Bn-1)。換言すれば、第4の転置手段39dは、第5の中間ワードG5nに、Bn-1によってセットされたパラメータを有する全単射的転置関数Pを適用することによって現在出力ワードYnを計算する。
【０２０３】
図6Aは、入力データシーケンスが暗号化メッセージに相当し、一連の出力ワードが平文のメッセージに相当する復号化モードで使用される暗号化デバイスを示す。
【０２０４】
この復号化モードでは、反復nにおける現在出力ワードUnの計算は、以下の演算を含む。
【０２０５】
第4の転置手段39dは、第4の全単射的転置の反転である転置を、現在入力ワードYnおよび第3の状態変数の直前の値Bn-1によって形成される対に適用することによって第5の中間ワードG5nを計算する:G5n=P-1(Yn,Bn-1)。
【０２０６】
第3の排他的論理和ゲート41cは、排他的論理和演算を、第5の中間ワードG5nおよび第3の状態変数の直前の値Bn-1に適用することによって第4の中間ワードG4nを計算する:
【０２０７】
【数１３】
0005551065.tif 000014
【０２０８】
。
【０２０９】
第3の転置手段39cは、第3の全単射的転置の反転である転置を、第4の中間ワードG4nおよび第1の状態変数の直前の値Xn-1によって形成される対に適用することによって現在中間値Xαを計算する:Xα=P-1(G4n,Xn-1)。この現在中間値Xαは、その後、擬似ランダム生成器に送出される。
【０２１０】
中央排他的論理和ゲート41bは、排他的論理和演算を、現在中間値Xαおよび第1の状態変数の直前の値Xn-1に適用することによって第3の中間ワードG3nを計算する:
【０２１１】
【数１４】
0005551065.tif 000015
【０２１２】
。
【０２１３】
第2の転置手段39bは、第2の全単射的転置の反転である転置を、第3の中間ワードG3nおよび第1の状態変数の直前の値Xn-1によって形成される対に適用することによって第2の中間ワードG2nを計算する:G2n=P-1(G3n,Xn-1)。
【０２１４】
第1の排他的論理和ゲート41aは、排他的論理和演算を、第2の中間ワードG2nおよび第2の状態変数の直前の値An-1に適用することによって第1の中間ワードG1nを計算する:
【０２１５】
【数１５】
0005551065.tif 000016
【０２１６】
。
【０２１７】
最後に、第1の転置手段39aは、第1の全単射的転置の反転である転置を、第1の中間ワードG1nおよび第2の状態変数の直前の値An-1によって形成される対に適用することによって現在出力ワードUnを計算する:Un=P-1(G1n,An-1)。
【０２１８】
相応して、図5Aおよび6Aの例では、隔離関数または手段35aおよび35bは、それぞれ、第1の隔離手段35aの場合An-1およびXn-1によってセットされ、第2の隔離手段35bの場合Bn-1およびXn-1によってセットされたパラメータを有する2つの転置関数(本発明の意味で全単射的転置)、および、第1の隔離手段35aの場合An-1を有し、第2の隔離手段35bの場合Bn-1を有する排他的論理和で構成される。現在中間値Xαは、したがって、An-1、Xn-1、およびBn-1によってセットされたパラメータを有する4つの転置関数、および、入力および出力からそれ自体隔離される状態ベクトルVの状態変数An-1、Xn-1、およびBn-1を有する3つの排他的論理和演算の中央において入力ワードおよび出力ワードから隔離される(すなわち、入力ワードおよび出力ワードからアクセスできない)。これは、状態ベクトルVの自己隔離に等しい。
【０２１９】
図5Bおよび6Bは、図3Bの擬似ランダム生成器1を使用して入力データシーケンスを暗号化しまた復号化するモードを同様に示す。あるいは、他の擬似ランダム生成器が使用されるであろう。
【０２２０】
さらに、一実施形態では、暗号化/復号化演算の複雑さは、それぞれ、AnについてAn'およびAn''、BnについてBn'およびBn''、ならびにXnについてXn'およびXn''の同じサイズの2つの部分変数(sub-variable)(本発明の意味でセクション)によって、状態変数のそれぞれAn、Bn、Xnを置換えることによってさらに増加しうる。部分変数An'、Bn'、およびXn'は、転置PおよびP-1のパラメータをセットするのに使用されうり、部分変数An''、Bn''、およびXn''は、排他的論理和演算を計算するのに使用されうる。
【０２２１】
別の実施形態では、各状態部分変数、AnについてAn'およびAn''、BnについてBn'およびBn''、ならびにXnについてXn'およびXn''は、コンティギュアスでなく、それぞれ、サイズmでありうる。たとえば、
Vn=(Xn'An'Bn'Xn''An''Bn''…)
である。
【０２２２】
さらなる実施形態では、それぞれの状態変数は、たとえば、所定の位置を占める状態ベクトルVの必ずしも連続しないmビットを含みうる。
【０２２３】
並列の複数の擬似ランダム生成器の使用
さらに、本発明の1つの特定の実施形態では、同じ暗号化/復号化モジュールについて並列の複数の生成器を使用することが可能であることに留意されたい。
【０２２４】
たとえば、図4は、暗号化モードにおいて、かつ/または、復号化モードにおいて暗号化デバイス7と同様の方法で使用されうり、また、暗号化/復号化モジュール17および第1の実施形態について図3Aを参照して述べた擬似ランダム生成器と同様の2つの擬似ランダム生成器101、102(あるいは、他の擬似ランダム生成器、たとえば、図3Bに示す生成器と同様の2つの擬似ランダム生成器が考えられうる)を含む暗号化デバイス107を示す。
【０２２５】
第1の擬似ランダム生成器101は、第1の状態ベクトルV1の第1の現在値V1nを形成し、第2の擬似ランダム生成器102は、第2の状態ベクトルV2の第2の現在値V2nを形成する。
【０２２６】
2つの擬似ランダム生成器101、102は、たとえば、排他的論理和ゲートによって並列に結合されうる。そして、状態ベクトルの現在値Vnは、第1の状態ベクトルV1の第1の現在値V1nおよび第2の状態ベクトルV2の第2の現在値V2nに適用された排他的論理和演算の結果である。任意の他の結合が可能であることに留意されたい。たとえば、2つの擬似ランダム生成器101、102からもたらされる状態ベクトルの現在値Vnは、第1の状態ベクトルの第1の現在値V1nから引き出される第1のセクション、第2の状態ベクトルの第2の現在値V2nから引き出される第2のセクション、ならびに、第1および第2の状態ベクトルの第1および第2の現在値V1n、V2nの対応するセクションの任意の結合から引き出される第3のセクションから構成されうる。
【０２２７】
より具体的には、図4の例では、第1の擬似ランダム生成器101は、第1の初期値V10を供給され(fed)、第1の状態変数X1の第1の現在値X1n、第2の状態変数A1の第1の現在値A1n、および第3の状態変数B1の第1の現在値B1nを少なくとも含む第1の状態ベクトルV1の第1の現在値V1nを生成する。さらに、第2の擬似ランダム生成器102は、第2の初期値V20を供給され、第1の状態変数X2の第2の現在値X2n、第2の状態変数A2の第2の現在値A2n、および第3の状態変数B2の第2の現在値B2nを少なくとも含む第2の状態ベクトルV2の第2の現在値V2nを生成する。
【０２２８】
この特定の例では、暗号化/復号化モジュール17に送出される状態ベクトルの直前の値Vn-1は、第1の状態ベクトルの第1の状態変数X1の第1の直前の値X1n-1および第2の状態ベクトルの第1の状態変数X2の第2の直前の値X2n-1、第1の状態ベクトルの第2の状態変数A1の直前の値An-1=A1n-1および第2の状態ベクトルの第3の状態変数B1の直前の値Bn-1=B2n-1に適用された排他的論理和演算から生じる第1の状態変数Xの直前の値Xn-1によって形成される。さらに、2つの擬似ランダム生成器101、102は、暗号化/復号化モジュール107から同じ現在中間値Xαを供給される。
【０２２９】
そのため、一般的に言えば、同じ暗号化/復号化モジュールについて、並列のi(i=1〜h)の擬似ランダム生成器を実施することが可能である。iの擬似ランダム生成器は、その後全て、暗号化/復号化モジュールから同じ現在中間値Xαを供給される。iの生成器は、同じかまたは異なるサイズk1、…、khでありうる。初期値V10、…、Vh0は、そのサイズがk1、…、khの最大値に等しい同じ暗号化/復号化鍵から抽出されるかまたは計算されうる。AnおよびBnの値は、同じ生成器または異なる生成器からもたらされうる。Xnは、各Xinの全てを排他的論理和演算によって結合することの結果に相当しうる:
【０２３０】
【数１６】
0005551065.tif 000017
【０２３１】
。
【０２３２】
もちろん、並列の擬似ランダム生成器は、高品質の擬似ランダムシーケンスを生成するために、暗号化/復号化モジュールと独立に使用されうる。
【０２３３】
入力ワードおよび出力ワードのビット数を変えること
上記例では、状態ベクトルは、特定数kのビットを含み、それぞれの出力ワードまたは入力ワードは、状態ベクトルのビットの特定数kより小さい特定数mのビットを含む。
【０２３４】
本発明の1つの特定の実施形態では、それぞれの出力ワードまたは入力ワードは、有利には、状態ベクトルのビットの特定の数kより小さいままでありながら、それぞれの反復に関して変動しうるビットの数wを含みうる。
【０２３５】
図7は、本発明のこうした実施形態において可変数wのビットを暗号化するデバイスを示す。この図の擬似ランダム生成器は、図3Aに示す生成器である。もちろん、たとえば、図3Bに示す生成器の代わりに、異なる擬似ランダム生成器が考えられるであろう。
【０２３６】
本明細書では、状態ベクトルVは、有利には、転置(特に、関係する転置のサイズeおよび転置のステージ数p)に適合するために、それぞれの反復に関して可変であるビットのこの数wを指示する第4の状態変数Eと、転置手段によって実施される排他的論理和演算子と、この可変数wに対する暗号化/復号化モジュール17の排他的論理和ゲートを含みうる。
【０２３７】
相応して、暗号化/復号化モジュール17によって使用される転置関数P(暗号化用)、P-1(復号化用)および排他的論理和演算子
【０２３８】
【数１７】
0005551065.tif 000018
【０２３９】
は、任意の長さw(w≦m≦k)の入力および出力ワードUn/Ynに適合可能である。転置関数PおよびP-1を実施し、また、状態変数An-1、Xn-1、およびBn-1の最初のwビットに関して排他的論理和演算を行うために、wの全ての実行可能な値に相当する転置テーブルが予め規定される場合に限り、入力データを可変サイズwのブロックに分割し、また、暗号化/復号化モジュール17を使用してこれらのブロックを暗号化する、かつ/または、復号化することが可能である。
【０２４０】
反復nの間に暗号化される、かつ/または、復号化される入力ビットの数wを指示するパラメータは、第4の状態変数Eの直前の値En-1によって提供される。この第4の状態変数Eは、入力および出力から隔離され、かつ、暗号化/復号化鍵および適用される入力ワードUn/Ynのシーケンスの全体に依存する状態ベクトルのサイズrのセクションである。
【０２４１】
相応して、反復nの間に、処理されるサイズwn-1のブロックは、入力ワードUn/Ynまたは出力ワードYn/Unに、また、転置手段39a〜39dに、また、論理ゲート41a〜41cに送出されて、転置および排他的論理和演算がサイジングされる。
【０２４２】
それぞれの反復に関して暗号化されるビットの数は、したがって、暗号化/復号化鍵および適用される入力ワードUn/Ynのシーケンスの全体に応じて擬似ランダムである。したがって、入力ワードUn/Ynのシーケンスのどんなにわずかな修正も、その修正後のデータの細分の全体の修正をシステム的にもたらす。
【０２４３】
第4の状態変数Eの直前の値En-1から、反復nの間に暗号化する/復号化する数wのビットを抽出するために、wは、第4の状態変数の直前の値En-1のrビットに関してコード化されたデシマル値が割当てられうる:0≦w≦2r-1(=m)。あるいは、wは、第4の状態変数の直前の値En-1において1のビットの数の値が割当てられうる:0≦w≦r(=m)。
【０２４４】
本明細書で述べる例では、ビットの初期数は、慣行により、また、第4の状態変数Eの初期値E0によらず、w0=1にセットされることに留意されたい。そのため、第1の反復中に、1ビットだけがシステム的に暗号化される/復号化される。
【０２４５】
(たとえば、暗号化モジュールの入力および出力を観測することによって)行われる細分に関する情報の漏洩を防止するために、出力ワードYn/Unは、一定長さmだけの出力ブロックにおいて負担を軽くするために、有利には、グループ化されうる。同じ措置が、復号化の場合に入力ワードUn/Ynに適用されうる。
【０２４６】
図8は、図3Aに示す生成器と同様の擬似ランダム生成器1を含む暗号化デバイス(図7に示すような暗号化および/または復号化のために使用されうる)を示し、状態ベクトルの現在値に依存する非可逆的アプリケーションによって、状態ベクトルの現在値を置換える新しい現在値を計算するさらなる手段を含む。これらのさらなる手段は、擬似ランダム生成器1が、第4の状態変数Eによって指示される値wの関数として状態ベクトルVに関する「空(empty)」反復を行うことを可能にする。
【０２４７】
そのため、擬似ランダム生成器1は、さらなる全射的転置手段を含む第4の計算手段45を含む。こうして、それぞれの反復の擬似ランダム生成ステップは、さらなる第2の中間状態ベクトルV2insの現在値を形成するために、可変数wがゼロに等しいときに、状態ベクトルの現在値Vnに対する第4の計算手段45による全射的転置(ベクトルVnに等しい転置鍵によってセットされたパラメータを有する転置関数P)の適用を含む。第2のさらなる中間状態ベクトルV2insのこの現在値は、その後、状態ベクトルVの現在値Vnを置換える。
【０２４８】
あるいは、擬似ランダム生成器1は、排他的論理和演算を、第2のさらなる中間状態ベクトルV2insの現在値および状態ベクトルの現在値Vnに適用することによって状態ベクトルの新しい現在値Vtempを計算するためのさらなる排他的論理和ゲート47aを含む第5の計算手段47を含みうる。状態ベクトルのこの新しい現在値Vtempは、その後、状態ベクトルの現在値Vnを置換える。
【０２４９】
そのため、図8は、w=0であると判定されると、暗号化/復号化演算が入力ワードUn/Ynまたは出力ワードYn/Unに関して行われないため状態ベクトルVに現在中間値Xαを組込むことなく、wが0のままである限り、擬似ランダム生成器1が、状態ベクトルVに関する「空」反復を行う(換言すれば、0ビットが暗号化される/復号化される)ことを示す。
【０２５０】
より具体的には、暗号化プロセスを開始する前に、暗号化鍵の値は、状態ベクトルVの初期値V0になる:V0=暗号化鍵およびw0=1。
【０２５１】
第1の反復に関して、暗号化/復号化モジュール17は、暗号化される入力ワードU1の第1ビットをとり、U1および状態ベクトルVの初期値V0の関数として暗号化される出力ワードY1の第1ビットの値を計算する。擬似ランダム生成器1は、U1およびV0の関数として状態ベクトルVの第1の値V1を計算する。
【０２５２】
拡張によって、n番目の反復に関して、擬似ランダム生成器1が、wn-1=0であることを検出する場合、擬似ランダム生成器1は、wn-1=0である限り、状態ベクトルVの直前の値Vn-1に関して「空」反復を行う。
【０２５３】
対照的に、wn-1≠0である場合、暗号化/復号化モジュール17は、暗号化されるデータの次のwn-1ビットをとり(ブロックUn)、UnおよびVn-1の関数として出力ワードYnの値を計算する。擬似ランダム生成器1は、UnおよびVn-1の関数として状態ベクトルVの新しい値Vnを計算する。
【０２５４】
対称的に、復号化の前に、復号化鍵の値は、状態ベクトルVの初期値V0になる:V0=復号化鍵およびw0=1。
【０２５５】
第1の反復に関して、暗号化/復号化モジュール17は、復号化される入力ワードY1の第1ビットをとり、Y1および状態ベクトルVの初期値V0の関数として復号化される出力ワードU1の第1ビットの値を計算する。擬似ランダム生成器1は、Y1およびV0の関数として状態ベクトルVの第1の値V1を計算する。
【０２５６】
拡張によって、n番目の反復に関して、擬似ランダム生成器1が、wn-1=0であることを検出する場合、擬似ランダム生成器1は、wn-1=0である限り、状態ベクトルVの直前の値Vn-1に関して「空」反復を行う。
【０２５７】
対照的に、wn-1≠0である場合、暗号化/復号化モジュール17は、復号化されるデータの次のwn-1ビットをとり(ブロックYn)、YnおよびVn-1の関数として出力ワードUnの値を計算する。さらに、擬似ランダム生成器1は、YnおよびVn-1の関数として状態ベクトルVの新しい値Vnを計算する。
【０２５８】
相応して、図8の例の演算は、擬似ランダム生成器1によって行われる反復が、アクセス可能でない擬似ランダム変数(第4の状態変数E)、暗号化/復号化鍵、および適用される入力ワードUn/Ynのシーケンスの全体の関数として暗号化/復号化モジュール17によって行われる反復から脱同期化される。したがって、入力ワードUn/Ynのシーケンスのどんなにわずかな修正も、その修正後のデータの細分の全体の修正、したがって、擬似ランダム生成器1が、暗号化/復号化モジュール17から脱同期化される方法の修正をシステム的にもたらす。
【０２５９】
さらに、ストリームおよび空サイクルの脱同期化を回避するために、暗号化される/復号化されるブロックのサイズが、w=0である状況に対処する必要なしで、変更されうることに留意されたい。w=0であるこの状況では、1ビットだけが暗号化され/復号化されなければならない。
【０２６０】
暗号化される/復号化されるブロックのサイズを変更することなく、ストリーム脱同期化関数だけを保持することも可能である。擬似ランダム生成器1の空サイクルが、w=0である場合行われ、一方、wの任意の他の値について、固定サイズmの入力ワードUn/Ynまたは出力ワードYn/Unが暗号化される/復号化される。
【０２６１】
暗号論的多重化
本発明の暗号化方法およびデバイスの種々の実施形態は、高ビットレートストリーム暗号化アプリケーション(電気通信、保護されたマルチメディアコンテンツ放送、サーバにおけるデータのオンザフライ暗号化、パーソナルコンピュータ、およびソフトウェアアプリケーション)について使用されうる。さらに、暗号化プロセスの構造そのものが、暗号化プロセスを暗号論的多重化の分野のアプリケーションに適合させる。
【０２６２】
図11A〜11Cは、暗号論的多重化の例を示す。
【０２６３】
一般的に言えば、暗号論的多重化によって、暗号化される平文のMのメッセージ71が、Mの暗号化メッセージを生成する同じ暗号化デバイス207aに向かって収束する。これらのMの暗号化メッセージは、その後、結合され、同じチャネル73aを介して(図11A)、または、異なるチャネル73bを介して別々に(図11B)、メッセージが意図されるユーザまたはアプリケーションに送出される。
【０２６４】
図11Cは、混合された解決策が、利用可能な送信チャネル数およびこれらのチャネルのそれぞれの各ビットレートの関数として想定されうることを示す。この例では、第1のチャネル73cは、単一の暗号化メッセージを送出し、第2のチャネル73dは、結合されたM-1の暗号化メッセージを送出する。
【０２６５】
復号化モードで使用される暗号化デバイス207b(復号化デバイスとも呼ばれる)は、その後、Mの暗号化メッセージから平文のMのメッセージ75を再構築する。Mの暗号化メッセージが利用可能でない場合、平文のMのメッセージのうちの1つのメッセージだけを、または、その全てを再構築することは不可能である。この解決策は、暗号論的アプリケーションをプールし、また、1つまたは複数のセキュアでないチャネルを通じて経路指定されなければならない複数のコンテンツを保護するための単純でかつ効率的な解決策を提供する。
【０２６６】
本発明の暗号化方法は、相応してサイジングされた1つだけの擬似ランダム生成器および並列のMの暗号化/復号化モジュールを使用して、上述したように暗号論的多重化を行う。これは、速度および暗号解読耐性の点で暗号化方法の性能から利益を得る非常に単純なハードウェアまたはソフトウェア実施態様ならびに可変サイズブロック、空反復、およびMの異なるメッセージに適用されるストリーム脱同期化関数を可能にする。
【０２６７】
図12は、暗号論的多重化を実施し、1つだけの擬似ランダム生成器1および並列の2つの暗号化/復号化モジュール17a、17bを含む暗号化デバイス(暗号化モードおよび/または復号化モードで動作しうる)を示す。
【０２６８】
この状況では、擬似ランダム生成器1は、それぞれの反復に関して、状態変数セクションの第1のセットおよび状態変数セクションの少なくとも1つの第2のセットを含む状態ベクトルの現在値を計算する。
【０２６９】
一般的に言えば、M(図12ではM=2)のメッセージを多重化するために、擬似ランダム生成器1の状態ベクトルVの現在値Vnは、以下の形態
Vn=(…X1n,A1n,B1n,E1n,…,X2n,A2n,B2n,E2n,…,XMn,AMn,BMn,EMn,…)
をとる。
【０２７０】
さらに、第1の暗号化/復号化モジュール17aは、第1の現在入力ワードU1n/Y1nおよび状態ベクトルの直前の値Vn-1の第1のセクションのセットX1n-1、A1n-1、B1n-1、E1n-1に依存する第1の可逆的アプリケーションによって第1の現在出力ワードY1n/U1nを計算する。中間値X1αは、擬似ランダム生成器1に送出される。
【０２７１】
第2の暗号化/復号化モジュール17bは、現在入力ワードU2n/Y2nおよび状態ベクトルの直前の値Vn-1の第2のセクションのセットX2n-1、A2n-1、B2n-1、E2n-1に依存する第2の可逆的アプリケーションによって第2の現在出力ワードY2n/U2nを計算する。中間値X2αは、擬似ランダム生成器1に送出される。
【０２７２】
図13は、暗号論的多重化手段81を含む暗号化デバイス(暗号化モードおよび/または復号化モードで使用されうる)の例を線図で示す。
【０２７３】
この例では、暗号論的多重化手段81は、少なくとも2つの暗号化メッセージブロックを形成するために、少なくとも2つの平文のメッセージブロックを多重化しうり、それぞれの平文のメッセージブロックは、一連の入力ワードに相当する。暗号論的多重化手段81は、第5の状態変数Fを含む状態ベクトルによって、上記図に示すように擬似ランダム生成器1のパラメータをセットすることに相当する。相応して、擬似ランダム生成器1は、状態ベクトルの第5の状態変数の関数としてそれぞれの反復に関して暗号化される種々のメッセージブロックを順序付けしうる。
【０２７４】
その結果、送信チャネルにおけるそれぞれの反復に関して暗号化されるMブロック(結合されてもされなくても)の順序は、予め規定されうるか、または、暗号化モードの暗号化鍵(または復号化モードの復号化鍵)および適用される入力ワードのシーケンスに依存するアクセス可能でない擬似ランダム変数(状態ベクトルのセクション)の関数でありうる。たとえば、Mの暗号化ブロック(結合されてもされなくても)は、状態ベクトルに含まれる第5の状態変数Fによってセットされたパラメータを有する転置関数Pによって順序付けされうる。
【０２７５】
反復nの間に結合された暗号化メッセージのMブロックを順序付けするためのパラメータは、第5の状態変数Fの直前の値Fn-1によって供給され、Fn-1は、入力ワードおよび出力ワードから隔離され、かつ、暗号化鍵(または復号化鍵)および適用される入力ワードのシーケンスの全体に依存する状態ベクトルの直前の値Vn-1のサイズMのセクションである。
【０２７６】
それぞれの反復に関する暗号化メッセージのMブロック(結合されてもされなくても)の送信チャネルの順序は、したがって擬似ランダムであり、暗号化鍵(または復号化鍵)および適用される入力ワードのシーケンスの全体に依存する。入力ワードのシーケンスのどんなにわずかな修正も、その修正後、送信チャネルの暗号化メッセージのブロック(結合されてもされなくても)の順序の完全な修正をシステム的にもたらす。
【０２７７】
暗号論的ハッシング方法およびデバイス
図14は、図1Aに線図で示す擬似ランダム生成器1が同様に、メッセージのダイジェストを生成するために、本発明の暗号論的ハッシング(またはhash)デバイス内のプレコンディショニングモジュールと結合して使用されうることを示す。
【０２７８】
図14はまた、本発明の暗号論的ハッシング方法の主要なステップを示すことに留意されたい。
【０２７９】
本明細書で詳細に述べる実施形態では、状態ベクトルVは、所定の数kのビットを含み、状態ベクトルの初期値V0は、サイズkの構成可能なハッシング鍵に相当する。
【０２８０】
図14は、メッセージMessを暗号論的にハッシングする本発明の1つの特定の実施形態のデバイス407を示す。
【０２８１】
このデバイス407は、メッセージMessを、所定数Mの、所定のサイズのブロックZ1、Z2、…、ZM(たとえば、mビットのMブロック)に分割する手段を含む。当技術分野で知られているように、細分の最後のブロックが不完全である(すなわち、mビットを含まない)場合、不完全ブロックは、0のビットで完全にパッディングされる。
【０２８２】
デバイス407は、さらに、状態ベクトルの初期値V0から状態ベクトルVの一連のMの値を反復的に生成し、生成される状態ベクトルの最新の値VMからメッセージMessのダイジェストhashを得るための生成手段を含む。メッセージブロックZ1、Z2、…、ZMは、状態ベクトルのMの値を生成するために、連続する反復中に、生成手段によって順番に使用される。
【０２８３】
本明細書で想定される例では、生成手段は、本発明の擬似ランダム生成器1(たとえば、図1Bおよび3Bに示す擬似ランダム生成)およびプレコンディショニングモジュール417を含む。本発明の暗号論的ハッシング方法による暗号論的ハッシングが開始される前に、ハッシング鍵の値が、状態ベクトルVの初期値V0になる。
【０２８４】
それぞれの反復nに関して、擬似ランダム生成器1は、状態ベクトルの直前の値Vn-1およびプレコンディショニングモジュール417によって実行される計算によって生成される現在中間値Xαに依存する非可逆的アプリケーションを使用して状態ベクトルの現在値Vnを計算し、プレコンディショニングモジュール417は、状態ベクトルの直前の値Vn-1および現在メッセージブロックZn(本発明の意味で入力ブロック)に依存する可逆的アプリケーションを使用して現在中間値Xαを計算する。それぞれの反復nに関して、擬似ランダム生成器1は、状態ベクトルVnに、プレコンディショニングモジュール417からの現在中間値Xαを供給する。
【０２８５】
第1の反復に関して、プレコンディショニングモジュール417は、第1のメッセージブロックZ1および状態ベクトルの初期値V0の関数として反復1について現在中間値Xαを計算する。擬似ランダム生成器1は、第1のメッセージブロックZ1および状態ベクトルの初期値V0の関数として状態ベクトルVの第1の値V1を計算する。拡張によって、n番目の反復に関して、プレコンディショニングモジュール417は、現在メッセージブロックZnおよび状態ベクトルの直前の値Vn-1の関数として反復nについて現在中間値Xαを計算し、擬似ランダム生成器1は、現在メッセージブロックZn(現在中間値Xαを使用して)および状態ベクトルの直前の値Vn-1の関数として状態ベクトルVの現在値Vnを計算する。
【０２８６】
本明細書で述べる実施形態では、状態ベクトルVは、有利には、サイズmの1つの第1の状態変数Xおよび1つの第2の状態変数Aを少なくとも含むセクションのセットを含む。たとえば、状態ベクトルVの現在値Vnは、本発明の意味で、状態変数XおよびAが状態ベクトルのセクションである、すなわち、
Vn=(…(Xn=(xn1…xnm))…(An=(an1…anm))…)
である方法で構築されうる。
【０２８７】
この例では、第1の状態変数Xの現在値Xnは、mビットxn1,…,xnmを含み、第2の状態変数Aの現在値Anは、mビットan1,…,anmを含み、ここで、mはメッセージブロックZn,n=1,…,Mのサイズである。
【０２８８】
状態変数のロケーションは、予め規定され、好ましくは固定されるが、それ自体固定位置である状態ベクトルの1つまたは複数のセクションによってとられる1つまたは複数の値の関数として可変の位置に、状態変数のロケーションを割当てることが可能である。状態変数の固定位置の解決策だけが以下で述べられる。
【０２８９】
さらに、状態変数のそれぞれに割当てられたセクタがオーバラップしないことが(必要ではないが)好ましい。状態ベクトルのサイズkは、相応して選択され、それぞれの状態変数は、制限されたサイズの(すなわち、状態ベクトルのサイズより完全に小さいサイズの)状態ベクトルのセクションに相当する。
【０２９０】
もちろん、暗号化方法の文脈で上述した状態変数の変形が、本発明の暗号論的ハッシング方法の文脈で同様に適用可能である。
【０２９１】
第1の状態変数Xの値Xnは、プレコンディショニングモジュール417によって次の反復で実行される計算によって生成される中間値Xαで置換えられる前に、プレコンディショニングモジュール417の隔離関数によって後続の反復で使用される。第2の状態変数の値Anもまた、プレコンディショニングモジュール417の隔離関数によって次の反復で使用される。
【０２９２】
それぞれの反復に関して(たとえば、反復nに関して)、擬似ランダム生成器1の送信手段321は、プレコンディショニングモジュール417に、第1の状態変数Xの直前の値Xn-1および第2の状態変数Aの直前の値An-1を少なくとも含む状態ベクトルの直前の値Vn-1を送出する。
【０２９３】
擬似ランダム生成器1の受信手段323は、プレコンディショニングモジュール417から現在中間値Xαを受信する。
【０２９４】
第1の計算手段325aは、第1の中間状態ベクトルVint1の現在値を計算するために、第1の状態変数Xの直前の値Xn-1を現在中間値Xαで置換える。擬似ランダム生成器1の他のプロセスステップおよび手段は、図1B(およびズ3B)を参照して述べたものと同様であり、本明細書ではより詳細には述べられない。
【０２９５】
プレコンディショニングモジュール417は、受信手段433および現在中間値Xαをメッセージブロックから隔離する隔離手段435を含む。
【０２９６】
受信手段433は、擬似ランダム生成器1から、第1の状態変数Xの直前の値Xn-1および第2の状態変数Aの直前の値An-1を少なくとも含む状態ベクトルの直前の値Vn-1を受信する。
【０２９７】
隔離手段435は、それぞれのメッセージブロックZnに対称秘密鍵関数を適用するようになっており、秘密鍵は、状態ベクトルの直前の値の少なくとも1つのセクションから得られる。
【０２９８】
使用される秘密鍵関数は、好ましくは、少なくとも1つの排他的論理和演算を含む。すなわち、隔離手段435は、状態ベクトルの直前の値のサイズmのセクションによってセットされたパラメータを有する少なくとも1つの排他的論理和ゲートを含む。あるいは、使用される秘密鍵関数は、さらに、状態ベクトルの直前の値のサイズmのセクションによってセットされたパラメータを有する、本発明の意味での少なくとも1つの全単射的転置を含みうる。
【０２９９】
本明細書で述べる例では、隔離手段435によって使用される秘密鍵関数は、本発明の意味での2つの全単射的転置、および、それぞれが状態ベクトルVn-1のサイズmのセクションによってセットされたパラメータを有する2つの排他的論理和演算で構成される。この関数の秘密鍵は、第1の全単射的転置のパラメータをセットするセクション、第1の排他的論理和演算のパラメータをセットするセクション、第2の全単射的転置のパラメータをセットするセクション、および第2の排他的論理和演算のパラメータをセットするセクションで構成される。
【０３００】
そのため、隔離手段435は、第1の排他的論理和ゲート441aによって分離された第1および第2の全単射的転置手段439a、439bを含む。第2の排他的論理和ゲート441bは、第2の全単射的転置手段439bの出力を受信する。
【０３０１】
本明細書で考えられる全単射的転置手段439aおよび439bはそれぞれ、状態ベクトルVn-1のそれぞれ異なる状態変数によってセットされたパラメータを有する、上述した転置関数Pを使用する。換言すれば、上述した異なる全単射的転置手段は、状態ベクトルVn-1の状態変数に等しいサイズmの転置鍵を使用する。相応して、
・第1の全単射的転置手段439aは、第2の状態変数An-1の直前の値に等しい転置鍵によってセットされたパラメータを有する転置関数Pに相当する第1の全単射的転置を使用し、
・第2の全単射的転置手段439bは、第1の状態変数Xn-1の直前のちに等しい転置鍵によってセットされたパラメータを有する転置関数Pに相当する第2の全単射的転置を使用する。
【０３０２】
全単射的転置手段439aおよび439bにおいて転置関数Pのパラメータをセットするのに使用される転置鍵は、得られる転置関数Pが適用されるデータと独立であり、したがって、可逆的(全単射的)関数をそれぞれ使用する。この可逆的関数Pは、関係する転置鍵のそれぞれのビットの値の関数として選択されるサイズmの連続するmの転置を適用することの結果である。
【０３０３】
そのため、反復nにおいて現在中間値Xαを計算することは、以下の演算を含む。
・第1の転置手段439aは、第1の全単射的転置を、現在入力ブロックZnに適用することによって第1の中間ワードJ1nを計算し、その転置は、第2の状態変数の直前の値An-1によってセットされたパラメータを有する:J1n=P(Zn,An-1)。
・第1の排他的論理和ゲート441aは、排他的論理和演算を第1の中間ワードJ1nおよび第2の状態変数の直前の値An-1に適用することによって第2の中間ワードJ2nを計算する:
【０３０４】
【数１８】
0005551065.tif 000019
【０３０５】
。
【０３０６】
・第2の転置手段439bは、第2の全単射的転置を、第2の中間ワードJ2nに適用することによって第3の中間ワードJ3nを計算し、その転置は、第1の状態変数の直前の値Xn-1によってセットされたパラメータを有する:J3n=P(J2n,Xn-1)。
・第2の排他的論理和ゲート441bは、排他的論理和演算を、第3の中間ワードJ3nおよび第1の状態変数の直前の値Xn-1に適用することによって現在中間値Xαを計算する:
【０３０７】
【数１９】
0005551065.tif 000020
【０３０８】
。
【０３０９】
この現在中間値Xαは、その後、擬似ランダム生成器1に送出される。
【０３１０】
現在ブロックZn(ハッシングされているプロセスにおけるメッセージブロック)の1ビットを修正することは、擬似ランダム生成器1の計算手段325aによって状態ベクトルVn-1に組込まれる変数Xαのビットを修正して、反復nにおける第1の中間ベクトルVint1が形成されることであることに留意されたい。その結果、計算手段326によって実施される転置の選択は、1つの転置ステージに割当てられ、そのため結果として、状態ベクトルVnおよび後続の状態ベクトルの全体も修正されることになる(なだれ効果)。
【０３１１】
メッセージMessを構成するMメッセージブロックを使用する連続するMの反復後に、メッセージMessのダイジェスト(hash)が、擬似ランダム生成器1によって生成される最新の(すなわち、M番目の)状態ベクトルから暗号論的ハッシングデバイス407によって形成される:換言すれば、hash=VM。
【０３１２】
これは、擬似ランダム生成方法の速度および暗号解読耐性から利益を得る、暗号論的ハッシング方法およびデバイスの非常に単純なハードウェアまたはソフトウェア実施態様を可能にする。
【０３１３】
さらに、本発明の暗号化デバイスについて実施される原理と同様の原理によれば、反復の関数として可変のサイズのメッセージブロックZnを考えること(すなわち、メッセージMessを、反復が進むにつれて、そのサイズwが可変でかつ状態ベクトルのセクションにおいて指定されるブロックに細分すること)、および/または、プレコンディショニングモジュールおよび擬似ランダム生成器で行われる演算を(特に、暗号化デバイスについて述べられる「空反復(empty iterations)」を導入することによって)脱同期化することが可能である。
【０３１４】
さらに、本発明の1つの特定の実施形態では、暗号論的ハッシングの数学的複雑さを増すために、hのハッシングデバイスを順次に鎖状につなぐ(ハッシングデバイスの擬似ランダム生成器によって生成される状態ベクトルのセクションが、次のハッシングデバイスのプレコンディショニングモジュールに供給される)ことが同様に可能である。
【０３１５】
さらに、本発明の1つの特定の実施形態では、本発明の暗号化方法のアーキテクチャを使用してメッセージを暗号化する(または復号化する)ことと同時に、本発明のハッシング方法によって暗号論的ハッシングを行うことが可能である。
【０３１６】
転置関数Pの実施態様
上記例で使用される転置関数Pがどのように働くかは、図9A〜9Eを参照して以下でより詳細に述べられる。
【０３１７】
上述したように、本明細書において非常に有利である方法で、擬似ランダム生成器(および生成方法)、暗号化デバイス(および方法)、ならびに、暗号論的ハッシングデバイス(および方法)は、転置鍵によってセットされるパラメータ、および、関係する入力データおよび鍵のサイズの関数としてセットされうるパラメータを有する、本発明によって提案された同じ転置関数Pに依存する。
【０３１８】
そのため、これらの例の転置関数Pは、複数の要求に対処するという利点を有する。
【０３１９】
ある事例では、転置鍵のサイズは、(たとえば、暗号化または暗号論的ハッシングについて、しかし同様に、図3Aに示す例の擬似ランダム生成について)出力データのサイズに同様に等しい入力データのサイズに等しい。これは、「四角形(square)」転置関数と呼ばれる。
【０３２０】
別の事例では、転置鍵のサイズは、(たとえば、図1Bおよび3Bに示す例における擬似ランダム生成について)出力データのサイズに同様に等しい入力データのサイズより完全に小さい。これは、「矩形(rectangular)」転置と呼ばれる。
【０３２１】
さらなる事例では、転置関数Pは、サイズe(e=k1≧k-状態ベクトルVのサイズ)の入力データとサイズm(暗号化される/復号化されるデータU/Vのサイズ)の入力データの両方に適用されうるようにセットされたパラメータを有しうる。さらなる事例では、転置関数Pは、それぞれの反復に関して暗号化されるビット数を修正するための関数に対してアクセスを有効にする任意のサイズe=wの入力データに適用されうるようにセットされたパラメータを有しうる。
【０３２２】
図9Aは、ボックス61a〜61fを含む転置テーブルを示し、転置テーブルにおいて、それぞれのボックスは、関係するロケーションに現れるビットのソース位置を指示する。移動によって、それぞれのビットは、その値を保持する、すなわち、v(i)=関係するデータのi番目のビットのバイナリ値(0または1)。
【０３２３】
この例では、入力データの第1のビットは、出力データの3番目のロケーション(ボックス61c)にシフトし、その値v(1)を保持する。入力データの第2のビットは、出力データのk番目のロケーション(ボックス61f)にシフトし、その値v(2)を保持する。入力データの第3のビットは、出力データの4番目のロケーション(ボックス61d)にシフトし、その値v(3)を保持する。入力データの第4のビットは、出力データの1番目のロケーションにシフトし、その値v(4)を保持する。入力データの第kのビットは、出力データの2番目のロケーション(ボックス61d)にシフトし、その値v(k)を保持する。
【０３２４】
転置関数Pが適用される入力データに対する鍵について行われる選択によれば、転置関数Pは、
・転置鍵が入力データから生成される(たとえば、鍵=入力データである)場合、1方向関数であり、したがって、非可逆的(非反転可能)であり、これらの1方向関数特性が、擬似ランダム生成器1によって実行される演算および本発明の暗号論的モジュールにおいて利用される、または、
・全単射的関数(全単射的鍵転置)であり、全単射的関数は、したがって、転置鍵の値がわかっており、転置鍵が入力データに対して独立であるまたは固定される場合に限り可逆的であり、これらの全単射的関数特性は、暗号論的ハッシングデバイスの暗号化/復号化モジュール17またはプレコンディショニングモジュール417の隔離関数または手段において利用されうる。
【０３２５】
サイズpの転置鍵Cによってセットされたパラメータを有する転置関数Pを、サイズeの転置されるデータに適用するために、転置されるデータに対して、転置鍵のpビットの値によってセットされたパラメータを有するサイズeのpの転置が鎖状につながれる。すなわち、それぞれの転置は、転置鍵の別個のビットの値の関数として選択される。
【０３２６】
転置鍵のそれぞれのビットについて、転置は、それぞれの転置ステージについて予め規定されたサイズeの異なる転置の対(P0,P1)から選択される。たとえば、考えられる転置鍵のビットが0に等しい場合、転置P0が選択され、考えられる転置鍵のビットが1に等しい場合、転置P1が選択される。
【０３２７】
考えられるサイズeの転置は、特に、以下の条件の少なくとも1つを満たす転置の予め規定された対(P0,P1)から選択されうる。以下の条件とは、
・鍵のそれぞれのビットについて、P0およびP1をそれぞれ構成することによって得られる転置ならびにP1およびP0をそれぞれ構成することによって得られる転置は、全ての点で異なること、
・全ての点で異なる転置P0およびP1の同一の対が、転置関数のpのステージ(転置の適用に相当するステージ)のそれぞれで使用される、すなわち、任意のtについて、第1の転置についての出力におけるビットtの位置は、第2の転置についての出力におけるビットtの位置と異なること、
・それぞれのステージで転置の対(P0,P1)が使用され、それにより、転置P0およびP1が、全ての点で恒等転置と個々に異なる、すなわち、転置P0またはP1の適用前の位置tにあるビットは、転置P0または転置P1によって、出口に関してtと異なる位置に位置すること
である。
【０３２８】
あるいは、異なる転置の対(P0i,P1i)が、それぞれの転置ステージiで適用されうる。
【０３２９】
そのため、処理される任意のサイズeのデータについて、転置関数Pは、2つのステップで進む。すなわち、
・第1ステップでは、それぞれサイズeの2つの転置(P0,P1)のp列で構成されたサイズ(p,2e)のテーブルであって、ハードウェア実施態様において経路指定マトリクスの役もする、サイズ(p,2e)のテーブルが前もって計算され、
・第2ステップで、かつ、転置関数Pを使用するとき、このテーブルのそれぞれの列iは、2つの考えられる転置を提供し、これらの転置の一方または他方は、使用される転置鍵のi番目のビットの値vkey(i)の関数として選択される。
【０３３０】
そのため、所与の転置鍵の値について、転置関数Pは、入力データに対して、転置鍵のpビットのそれぞれの値によってセットされたパラメータをそれぞれ有するサイズeのpの転置を鎖状につなぐ。
【０３３１】
図9Bは、転置関数Pの5つの各転置ステージで使用され、かつ、関数P(四角形転置関数P)のサイズp=5の転置鍵のi番目のビットの値vkey(i)の関数として、サイズe=5の入力データに適用される、サイズe=5の連続する転置の5つの異なる対の例を示す。
【０３３２】
図9Cは、転置関数Pの5つの転置ステージのそれぞれについて使用され、かつ、関数P(四角形転置関数P)のサイズp=5の転置鍵のi番目のビットの値vkey(i)の関数として、サイズe=5の入力データに適用される、サイズe=5の5つの異なる転置の同一の対の例を示す。
【０３３３】
図9Dは、転置関数Pの5つの転置ステージでそれぞれ使用され、かつ、関数P(矩形転置関数P)のサイズp=5の転置鍵のi番目のビットの値vkey(i)の関数として、サイズe=7の入力データに適用される、サイズe=7の連続する転置の5つの異なる対の例を示す。
【０３３４】
図9Eは、転置関数Pの5つの転置ステージのそれぞれについて使用され、かつ、関数P(矩形転置関数P)のサイズp=5の転置鍵のi番目のビットの値vkey(i)の関数として、サイズe=7の入力データに適用される、サイズe=7の5つの異なる転置の同一の対の例を示す。
【０３３５】
上述した転置鍵Pの主要な利点は、「NOT」および「AND」論理関数だけを使用しうる非常に単純なハードウェア実施態様である。
【０３３６】
図10Aおよび10Bは、サイズpの転置鍵のそれぞれのビットvkey(i)(i=1,…,p)について、ビットvkey(i)の値の関数としてサイズe(転置されるデータのサイズ)の2つの予め規定された転置の一方を選択し、そのため、上記転置鍵のpビットのそれぞれの値によってセットされたパラメータを有するpの転置の鎖状つなぎを有効にするための論理ゲート63、65を含む転置手段を示す。
【０３３７】
図10Aの例は、「NOT」論理ゲート63および「AND」論理ゲート65を使用して、p=5およびe=5について、図9Cからの転置関数Pの第1の転置ステージの配線をより詳細に示す。
【０３３８】
AND論理ゲート65は、このアプリケーションでは、転置鍵のビットの値vkeyまたはその補数によって制御されるスイッチ(またはハードウェア実施態様ではトランジスタ)に相当する。したがって、スイッチは、鍵のビットの値vkeyまたはその補数の関数として開くかまたは閉じる(スイッチがトランジスタであるときは、ターンオンするかまたはターンオフする)。
【０３３９】
したがって、ステージは、次々に鎖状につながり、ステージh-1の出力69は、ステージhの入力67に供給される。
【０３４０】
転置されるべきデータのそれぞれのビットの各値を第1のステージの入力に、関連する鍵のビットの各値をそれぞれのステージの鍵入力に適用することによって、サイズeの入力データに関して行われ、かつ、サイズpの鍵によってセットされたパラメータを有する、サイズeのpの転置に相当する、pのステージ全てにわたる1回だけの演算で実行されうる論理関数が得られる。2つの異なる転置の同一の対が、pのステージのそれぞれについて使用される場合、pの同一のモジュールが使用される。
【０３４１】
図10Bは、図9Cに示すように、p=5について値vkey(i)の関数としてサイズe=5の入力データに適用されるp=5のステージのそれぞれについて使用される2つの異なる転置の同一の対のハードウェア実施態様の例を示す。
【０３４２】
ソフトウェア実施態様の場合、そのパラメータについて、入力データ、転置鍵、転置テーブル、および関係する転置ステージiを有する再帰的関数が使用されうる。転置関数Pは、i=pに関して以下の「再帰的関数(recursive function)」を呼び出すことによって著しく迅速に計算される。
Output data = recursive function (input data, key, permutation table, i)
If i=1; then
If Vkey(1) = 0; then
Output data = Permutation(1)_Vkey_0 (input data)
Else,
Output data = Permutation(1)_Vkey_1 (input data)
Endif
Else,
If Vkey(i) = 0; then
Output data = Permutation(i)_Vkey_0 (recursive function (input data, key, permutation table, i-1))
Else,
Output data = Permutation(1)_Vkey_1 (recursive function (input data, key, permutation table, i-1))
Endif
Endif
End of function
【０３４３】
上述したハードウェアおよびソフトウェア実施態様は、これらの実施態様が、関係する転置鍵の特質(すなわち、転置される入力データに依存するかまたは独立に)、すなわち、転置関数Pが1方向関数であるかどうか、または、転置関数Pが全単射的鍵関数であるかどうかによらず使用されうるという利点を有する。これは、上述したプロセスおよびデバイスを実施する複雑さを制限するという利点を有する。
【０３４４】
そのため、本発明は、(状態ベクトルの初期値として使用される)任意のサイズkの暗号化鍵によってセットされたパラメータを有する擬似ランダム生成器を提供し、擬似ランダム生成器は、暗号化/復号化モジュールからもたらされ、かつ、適用される入力シーケンスの全体に依存する中間結果を用いて、それぞれの反復で供給される状態ベクトルに関して反復を行う。暗号化/復号化モジュールは、擬似ランダム生成器の自己隔離関数を統合し(integrate)、それぞれの反復に関して、擬似ランダム生成器の状態ベクトルの複数のセクションの値の関数として、入力データの暗号化および/または復号化を実行する。
【０３４５】
そのため、本発明の暗号化デバイスは、特に、以下の利点を有する。
【０３４６】
暗号化/復号化モジュールは、ハードウェアで実施されようが、ソフトウェアで実施されようが可逆的である。したがって、暗号化/復号化機能について異なるプログラム/回路を有する必要はない。
【０３４７】
擬似ランダム生成器は非可逆的である。
【０３４８】
転置関数Pは、ハードウェアで実施されようが、ソフトウェアで実施されようが著しく高速の単一演算で行われ、擬似ランダム生成器では非可逆的形態P(data, key(data))(すなわち、鍵は転置されるデータに依存する)で、暗号化/復号化モジュールでは可逆的形態P(data, fixed_key)(すなわち、鍵は転置されるデータに対して固定される)で使用される。
【０３４９】
擬似ランダム生成器は、特定の期間を有さず、予め規定されたサイクルに追従しない。状態ベクトルの値は、暗号化/復号化鍵および適用される入力ワードシーケンス全体に依存し、それぞれの反復に関して、1つのアトラクタ(特定の入力シーケンスに固有のサイクル)から別のアトラクタへ切換わるため、確定的なサイクルを持たない。
【０３５０】
本発明によって提案される状態ベクトル擬似ランダム生成器は、状態ベクトルの値が、出力ワードのシーケンスを観測することによって再構築されえないか、または、入力ワードのシーケンスによって、意図的に、予め規定された値にされえないようなものである(非観察可能および非駆使可能な状態ベクトル)。状態ベクトルは、それ自身の状態変数のいくつかの値によってセットされたパラメータを有する隔離関数を使用して、入力ワードと出力ワードを隔離する(自己隔離)。暗号解読に対する耐性とは別に、この特性は、暗号化プロセスが開始されるたびに起こる初期化ベクトルの修正の問題をなくす。したがって、初期化ベクトルの役をする暗号化/復号化鍵は修正される必要がない。さらに、メッセージ番号タイプのNonce(1回だけ使用される番号)で始まるメッセージヘッダが使用されて、メッセージが同様のヘッダを有することに関する情報の漏洩が回避されうる。
【０３５１】
本発明は、アクセス可能でなく、かつ、暗号化/復号化鍵および適用される入力ワードのシーケンス全体に依存する擬似ランダム変数(状態ベクトルのセクション)の関数として、それぞれの反復に関して暗号化されるビット数を修正する可能性を提供する。
【０３５２】
別のオプションは、擬似ランダム生成器が、アクセス可能でなく、かつ、暗号化/復号化鍵および適用される入力ワードのシーケンス全体に依存する擬似ランダム変数(状態ベクトルのセクション)の関数として、「空サイクル(empty cycle)」(入力を暗号化することなく、状態ベクトルに関して行われる反復)を行うことであり、擬似ランダム生成器とデータ暗号化/復号化モジュールの脱同期化をもたらす。
【０３５３】
さらなるオプションは、暗号化される平文のMのメッセージが、Mの暗号化メッセージを生成する同じ暗号化デバイスに収束されるようにすることによって、暗号化デバイスを暗号論的多重化器として使用することである。Mの暗号化メッセージがアクセス可能でない場合、平文のMのメッセージの1つまたは全てを再構築することは不可能である。暗号化メッセージは、送信チャネルの数を減少させるために、互いに結合されうる。それぞれの反復に関する送信チャネルにおける暗号化ブロック(結合されてもされなくても)の順序は、予め規定されうるか、または、アクセス可能でなく、かつ、暗号化鍵および適用される入力ワードのシーケンスの全体に依存する擬似ランダム変数(状態ベクトルのセクション)の関数でありうる。
【０３５４】
本発明は、高いレベルのセキュリティ、ならびに、単純でかつ効率的なハードウェアまたはソフトウェアの実施態様を提供する、暗号論的ハッシングおよび対称暗号化/復号化を同時に可能にする点で非常に有利なアプリケーションを見出す。
【０３５５】
暗号論的ハッシングおよび対称暗号化は、移動体通信、インターネット、スマートカードなどのような全てのタイプの通信で日常的に使用されることに留意されたい。
【符号の説明】
【０３５６】
1  暗号論的生成器
3、13  擬似ランダムデータシーケンス
5  暗号論的モジュールと状態ベクトルの現在値を得る手段とを使用する手段
7  入力データシーケンスを暗号化するデバイス
17  暗号化手段
25、325a  第1の中間ベクトルを形成する手段
27a、41a、41c、131、327a  排他的論理和演算
35a、35c  秘密鍵関数
45  状態ベクトルの新しい現在値を計算する手段
323  現在中間値を得る手段
326  暗号論的モジュール
326a  入力ベクトルに転置を連続して適用する手段
326b  転置鍵を形成する手段
407  暗号論的ハッシングデバイス
C  サイズdの転置鍵
hash  ダイジェスト
Mess  メッセージ
V  サイズkの状態ベクトル
V0  状態ベクトルの初期値
Vn  状態ベクトルの現在値
Vn-1  状態ベクトルの直前の値
VM  状態ベクトルから生成される最新の値
Vprov  サイズkの仮ベクトル
Vint1  サイズkの第1の中間ベクトル
Vint2  適用ステップの結果ベクトルのセクション
Vres  適用ステップの結果ベクトル
Vtmp  状態ベクトルの新しい現在値
Xα  状態ベクトルの直前の値から計算される現在中間値
Xn-1、An-1、Bn-1  状態ベクトルの直前の値のセクション
Un、Yn、Zn  入力データブロック
w  可変のビット数
V1  第1の状態ベクトル
V2  第2の状態ベクトル
V1n  第1の状態ベクトルの現在値
V2n  第2の状態ベクトルの現在値
Y1n、U1n  第1の現在出力ワード
Y2n、U2n  第2の現在出力ワード
U2n、Y2n  第2の現在入力ワード
X1α  第1の現在中間値
X2α  第2の現在中間値
【図１Ａ】
0005551065.tif 000021
【図１Ｂ】
0005551065.tif 000022
【図２】
0005551065.tif 000023
【図３Ａ】
0005551065.tif 000024
【図３Ｂ】
0005551065.tif 000025
【図４】
0005551065.tif 000026
【図５Ａ】
0005551065.tif 000027
【図５Ｂ】
0005551065.tif 000028
【図６Ａ】
0005551065.tif 000029
【図６Ｂ】
0005551065.tif 000030
【図７】
0005551065.tif 000031
【図８】
0005551065.tif 000032
【図９Ａ】
0005551065.tif 000033
【図９Ｂ】
0005551065.tif 000034
【図９Ｃ】
0005551065.tif 000035
【図９Ｄ】
0005551065.tif 000036
【図９Ｅ】
0005551065.tif 000037
【図１０Ａ】
0005551065.tif 000038
【図１０Ｂ】
0005551065.tif 000039
【図１１Ａ】
0005551065.tif 000040
【図１１Ｂ】
0005551065.tif 000041
【図１１Ｃ】
0005551065.tif 000042
【図１２】
0005551065.tif 000043
【図１３】
0005551065.tif 000044
【図１４】
0005551065.tif 000045
【図１５Ａ】
0005551065.tif 000046
【図１５Ｂ】
0005551065.tif 000047