(57)【要約】対象鍵暗号用の線形変換行列Ａを生成する方法は、バイナリ［ｎ， ｋ， ｄ］エラー訂正コードの生成を含み、ここで、ｋ ＜ ｎ ＜ ２ｋであり、ｄは前記バイナリ・エラー訂正コードの最小距離である。前記コードは、Ｂ ∈ Ｚ２ｋ×（ｎ−ｋ）を備える標準形Ｇ ＝ （Ｉｋ ‖ Ｂ）の生成行列Ｇ ∈ Ｚ２ｋ×ｎによって表される。前記行列Ｂは、結果として生じる行列Ｃが非特異であるように２ｋ−ｎ個の列で拡大される。前記線形変換行列Ａは、行列Ｃから導き出される。好ましくは、前記エラー訂正コードはＸＢＣＨコードに基づく。
2004506246.tif 000002
【特許請求の範囲】
【請求項１】
対象鍵暗号用の線形変換行列Ａを生成する方法であり、
−、ｋ ＜ ｎ ＜ ２ｋであり、ｄはバイナリ・エラー訂正コードの最小距離であって、Ｂ ∈ Ｚ２ｋ×（ｎ−ｋ）を備える標準形Ｇ ＝ （Ｉｋ ‖ Ｂ）の生成行列Ｇ ∈ Ｚ２ｋ×ｎによって表されるバイナリ［ｎ， ｋ， ｄ］エラー訂正コードを生成するステップ、
− 結果として生じるＣが非特異であるように２ｋ−ｎ個の列で行列Ｂを拡大するステップ、及び
− 行列Ｃから行列Ａを導き出すステップを含む方法。
【請求項２】
前記２ｋ−ｎ個の列で行列Ｂを拡大するステップが、対話方式で、
− 各々がｋ個のバイナリの要素を備える２ｋ−ｎ個の列を（疑似）ランダムに生成するステップ、
− 前記Ｂのｎ−ｋ個の列及び生成された前記２ｋ−ｎ個の列から成るテスト行列を形成するステップ、及び
− 非特異テスト行列が見つけられるまで前記テスト行列が非特異であるかどうかをチェックし、見つけられた前記テスト行列を行列Ｃとして用いるステップを含む請求項１に記載の方法。
【請求項３】
前記行列Ｃから行列Ａを導き出すステップが、
− 生成行列（Ｉ ‖ Ｐ１ＣＰ２）によって表される［２ｋ， ｋ， ｄ］エラー訂正コードにおける全てのコードワードが所定のマルチビット重みを持つように２つの置換行列Ｐ１， Ｐ２ ∈ Ｚ２ｋ×ｋを決定するステップ、及び
− Ｐ１ＣＰ２を行列Ａとして用いるステップを含む請求項１に記載の方法。
【請求項４】
前記対象鍵暗号が、ｍビットのサブブロックに作用するＳ−ｂｏｘを持つＳ−ｂｏｘ層を備えるラウンド関数を含み、全ての非零コードワードにわたって最小の前記所定のマルチビット重みが、所定のｍビット重みと等しい請求項３に記載の方法。
【請求項５】
前記２つの置換行列Ｐ１及びＰ２を決定するステップが、（疑似）ランダム方式で前記行列を繰り返し生成するステップを含む請求項３に記載の方法。
【請求項６】
前記暗号が３２ビットブロックに作用するラウンド関数を含み、前記［ｎ， ｋ， ｄ］エラー訂正コードを生成するステップが、バイナリに拡張されたＢｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｃｑｕｅｎｇｈｅｍ （ＸＢＣＨ）［６４， ３６， １２］コードを生成するステップ、及び４つの行を削除することによりこのコードを［６０， ３２， １２］縮小ＸＢＣＨコードへ縮小するステップを含む請求項１に記載の方法。
【請求項７】
プロセッサに請求項１に記載の方法を行わせるよう作用するコンピュータプログラムプロダクト。
【請求項８】
入力データブロックを出力データブロックへ暗号的に変換するシステムであり、前記データブロックはｎデータビットを有し、当該システムは、
− 前記入力データブロックを受け取る入力部、
− 請求項１に記載の方法により生成される線形変換行列Ａを記憶する記憶装置、
− 前記入力データブロックにおける線形変換、又は前記線形変換行列Ａを用いる前記入力データブロックの誘導を行う暗号プロセッサ、及び
− 処理された前記入力データブロックを出力する出力部を含むシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、バイナリ・エラー訂正コード（ｂｉｎａｒｙ ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｎｇ ｃｏｄｅ）に基づいて対称鍵暗号用の線形変換を生成する方法に関する。
【０００２】
【従来の技術】
デジタルのオーディオ及び／又はビデオの著作権保護の分野における暗号のアプリケーションが、ますます重要になっている。これらのアプリケーションは、コンテンツの暗号化／復号及びアクセス管理の機能を含む。斯様なアプリケーションに対しては、ブロック暗号が用いられ得る。ブロック暗号のよく知られているファミリーはＦｅｉｓｔｅｌ型暗号である。Ｆｅｉｓｔｅｌ型暗号においては、入力データブロックが多数のラウンド（ｒｏｕｎｄ）において処理される。各ラウンドにおいては、前記ブロックの２つのサブブロック（半分）が別個に作用される。第１サブブロックはラウンド関数の出力と組み合わされ、第２サブブロックは変更されないままである。ラウンドの最後には、２つのサブブロックがスワップされ、変更されていないサブブロックが次のラウンドにおいて処理されることを確実なものにする。ラウンド関数は入力として第２サブブロック及びラウンド鍵をとる。通常、ラウンド関数は、例えばＸＯＲ演算を用いて、ラウンド鍵を第２サブブロックと組み合わせる。そのうえ、ラウンド関数は第２サブブロックにおける非線形演算及び線形変換を行う。典型的には、非線形変換は置換ボックス（ｓｕｂｓｔｉｔｕｔｉｏｎ ｂｏｘ） （Ｓ−ｂｏｘ）層から成り、Ｓ−ｂｏｘ層は、例えば４乃至８ビットのより小さなサブブロックに並列に作用する多数のＳ−ｂｏｘから成る。Ｓ−ｂｏｘ層の後には、線形演算が、個々のＳ−ｂｏｘによってもたらされたビット変化が次のラウンドにおいて可能な限り多くのＳ−ｂｏｘにわたって伝えられるように適当な拡散が行われることを確実なものにする。
【０００３】
Ｆｅｉｓｔｅｌ型暗号のよく知られている例は、１６ラウンドから成るＤＥＳである。各ラウンドにおいては、まず、データの右半分の３２ビットが４８ビットに拡大される。次に、鍵スケジュール処理アルゴリズム（ｋｅｙ ｓｃｈｅｄｕｌｉｎｇ ａｌｇｏｒｉｔｈｍ）を備える５６ビットＤＥＳ鍵から計算される４８ビットラウンド鍵は、これらの４８ビットに対してビットごとに非等価演算（ａｄｄ ｍｏｄｕｌｏ ｔｗｏ）をされる。次いで、Ｓ−ｂｏｘの層はこのデータにおいて非線形演算をする。ＤＥＳにおいて、Ｓ−ｂｏｘ層は並列の８個の６−４ビットＳ−ｂｏｘ（ｓｉｘ−ｔｏ−ｆｏｕｒ ｂｉｔ Ｓ−ｂｏｘ）から成り、即ち、Ｓ−ｂｏｘの各々は、Ｓ−ｂｏｘごとに１つの固定マッピングテーブル（ｆｉｘｅｄ ｍａｐｐｉｎｇ ｔａｂｌｅ）を用いて６ビット入力ブロックを４ビット出力ブロックに変換する。Ｓ−ｂｏｘ層の出力は、３２ビットデータブロックである。この３２ビットデータブロックにおいて行われる線形変換は、Ｓ−ｂｏｘによってもたらされたビット変化が次に続くラウンドにおいて多くの他のＳ−ｂｏｘにわたって伝えられることを確実なものにするビットの並び替え（ｂｉｔ−ｐｅｒｍｕｔａｔｉｏｎ）である。ＤＥＳの不利な点は、現在では高レベルのセキュリティを提供するのに不十分であると考えられる５６ビットという小さな鍵の大きさにある。しかしながら、しらみ潰しの鍵探索（ｅｘｈａｕｓｔｉｖｅ ｋｅｙ ｓｅａｒｃｈ）は、１６個の４８ビットラウンド鍵を算出する別の鍵スケジュール処理アルゴリズムと組み合わされたより長い鍵を用いることによって防止され得る。公開文献で発表されているＤＥＳに対する２つの最も強力な攻撃（ａｔｔａｃｋ）は、幅広いブロック暗号に適用され得る一般的な攻撃である差分解読法（ｄｉｆｆｅｒｅｎｔｉａｌ ｃｒｙｐｔａｎａｌｙｓｉｓ）及び線形解読法（ｌｉｎｅａｒ ｃｒｙｐｔａｎａｌｙｓｉｓ）である。ＤＥＳは、鍵長及び／又は鍵スケジュール処理アルゴリズムを変更することによってはこれらの攻撃に対してあまり強化され得ないことが示されている。しかしながら、アルゴリズムのラウンド関数における変更は、これらの攻撃に対する強度にかなり影響を及ぼし得る。
【０００４】
線形変換に対しては、該変換が良好な拡散特性を持つことが望まれる。最近、Ｓ． Ｖａｕｄｅｎａｒｙが、線形変換を構成する（ｃｏｎｓｔｒｕｃｔ）ために線形エラー訂正コードを用いることを提案しており、説明は、”Ｏｎ ｔｈｅ Ｎｅｅｄ ｆｏｒ Ｍｕｌｔｉ−Ｐｅｒｍｕｔａｔｉｏｎｓ： Ｃｒｙｐｔａｎａｌｙｓｉｓ ｏｆ ＭＤ４ ａｎｄ ＳＡＦＥＲ”， Ｆａｓｔ Ｓｏｆｔｗａｒｅ Ｅｎｃｒｙｐｔｉｏｎ （２ｎｄ）， ＬＮＣＳ １００８， Ｓｐｒｉｎｇｅｒ， １９９５， ｐｐ． ２８６−２９７において見出され得る。線形変換の拡散特性は、対応するエラー訂正コードの最小ハミング距離と関連しており、この距離が大きいほど、関連線形変換行列の拡散特性は良くなる。Ｖａｕｄｅｎａｒｙは、所謂シングルトンの限界（Ｓｉｎｇｌｅｔｏｎ ｂｏｕｎｄ）に達し、それ故最適拡散を供給する、有限フィールド（ｆｉｎｉｔｅ ｆｉｅｌｄｓ）にわたっての最大距離分離（ＭＤＳ）コードの使用を提案している。しかしながら、この構成は、結果として生じる線形変換が、解読において活用され得る、付加的な数学的構造（ａｄｄｉｔｉｏｎａｌ ｍａｔｈｅｍａｔｉｃａｌ ｓｔｒｕｃｔｕｒｅ）、例えば、構成のために用いられた有限フィールド（及び全てのサブフィールド）にわたっての線形性（ｌｉｎｅａｒｉｔｙ）を含むという不利な点を持つ。
【０００５】
【課題を解決するための手段】
本発明の目的は、最適バイナリ線形エラー訂正コード（ｏｐｔｉｍａｌ ｂｉｎａｒｙ ｌｉｎｅａｒ ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｎｇ ｃｏｄｅ）に基づいて、ビットレベルにおける保証された最適拡散特性を備える対称鍵暗号用の非特異バイナリ行列（ｎｏｎ−ｓｉｎｇｕｌａｒ ｂｉｎａｒｙ ｍａｔｒｉｘ）によって表される可逆線形変換（ｉｎｖｅｒｔｉｂｌｅ ｌｉｎｅａｒ ｔｒａｎｓｆｏｒｍａｔｉｏｎ）を提供することにある。この変換は、解読において活用され得る結果として生じる線形変換の付加的な数学的構造が避けられるという意味で、より不規則であるＭＤＳ構成以上の利点を持つ。
【０００６】
本発明の目的を満たすために、エラー訂正コードから導き出される行列は、前記コードの長さが２倍の大きさと等しく、線形変換のための基底（ｂａｓｉｓ）として用いられ得る結果として生じる行列が非特異であるように多数の列で拡大される。このことは、ラウンド関数の非一様性（ｎｏｎ−ｕｎｉｆｏｒｍｉｔｙ）に基づいて攻撃を防ぐ。
【０００７】
従属項２の対策において規定されているように、新しい列は、適切な列を見つけるために（疑似）ランダムに生成され得る。
【０００８】
従属項３の対策において規定されているように、行列Ｃは、所定のマルチビット重み（ｍｕｌｔｉ−ｂｉｔ ｗｅｉｇｈｔ）を持つ関連線形エラー訂正コードを備える線形変換行列を見つけるために並び替えられる。従属項４の対策において規定されているように、このマルチビット重みは、暗号のＳ−ｂｏｘにわたっての適当な拡散を確実なものにする。例えば、各Ｓ−ｂｏｘがｍビット出力を供給する並列に作用する多数のＳ−ｂｏｘから成るＳ−ｂｏｘ層に対しては、関連バイナリ・エラー訂正コード中のワードのｍビット部分の拡散を調べるのが適切であり、このことは、全ての非零コードワード（ｎｏｎ−ｚｅｒｏ ｃｏｄｅｗｏｒｄ）にわたっての最小ｍビット重みで表され得る。
【０００９】
以下に図面に示されている実施例を参照して本発明のこれら及び他の特徴を説明し、明らかにする。
【００１０】
【発明の実施の形態】
本発明を説明する目的で、線形変換を用いる暗号システムを、電子コードブック（ＥＣＢ）モードにおけるブロック暗号として記載する。当業者は同様に他のモードにおいて前記システムを使用することが出来るであろう。これらは、ＤＥＳのための標準的なＦＩＰＳモードの演算、即ち、暗号ブロック連鎖（ＣＢＣ）、暗号フィードバック（ＣＦＢ）及び出力フィードバック（ＯＦＢ）のモードの演算を含む。更に、このシステムはまた、操作検出コード（Ｍａｎｉｐｕｌａｔｉｏｎ Ｄｅｔｅｃｔｉｏｎ Ｃｏｄｅｓ）（ＭＤＣｓ）、メッセージ認証コード（Ｍｅｓｓａｇｅ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ Ｃｏｄｅｓ）（ＭＡＣｓ）及び疑似乱数生成器（ｐｓｅｕｄｏ−ｒａｎｄｏｍ ｎｕｍｂｅｒ ｇｅｎｅｒａｔｏｒ）のためのよく知られている構成においても用いられ得る。
【００１１】
図１は、典型的な暗号装置１００のブロック図を示している。暗号装置１００はデジタル入力ブロックＸを得るための入力部１１０を有する。デジタル入力ブロックＸは任意の適切なサイズであり得る。この装置は、デジタル入力ブロックＸをデジタル出力ブロックＥ（Ｘ）に変換するための暗号プロセッサ１２０を更に有する。好都合なことに、デジタル出力ブロックはデジタル入力ブロックと実質的に等しい長さを持つ。装置１００は、デジタル出力ブロックを出力する出力部１３０を有する。好ましい実施例においては、暗号プロセッサが、デジタル入力ブロックを鍵ビットＫと合成（ｍｅｒｇｅ）し、入力ブロックＸ及び鍵Ｋに非線形に依存する出力ブロックＥ（Ｘ， Ｋ）を作成することにより、デジタル入力ブロックをデジタル出力ブロックに変換する。鍵（又は鍵スケジューラに与えられる最初の鍵）を得るために、暗号装置は第２入力部１４０を有する。暗号装置は、ＰＣなどの従来のコンピュータを用いて、又は専用の暗号化／復号装置を用いて実施され得ることを認識されたい。デジタル入力ブロックは、通信ネットワークを介して、ハードディスク若しくはフロッピー（Ｒ）ディスクなどのデータ記憶媒体から、又はユーザにより直接的に入力されるといった種々の方式で得られ得る。同様に、デジタル出力ブロックは、通信ネットワークを介して、データ記憶媒体に記憶される、又はユーザに対して表示されるといった種々の方式で出力され得る。好ましくは、この目的のために安全な手段（ｓｅｃｕｒｅ ｍｅａｎｓ）が用いられる。暗号プロセッサは、例えばパーソナルコンピュータにおいて用いられるような従来のプロセッサであっても良いが、専用の暗号プロセッサであっても良い。このプロセッサは、通常、本発明によるアルゴリズムのステップを行う適切なプログラム（ファームウェア）の制御のもとで動作される。このコンピュータプログラムプロダクトは、通常、ハードディスク又はＲＯＭなどのバックグラウンド記憶装置（ｂａｃｋｇｒｏｕｎｄ ｓｔｏｒａｇｅ）からロードされる。コンピュータプログラムプロダクトは、ＣＤ−ＲＯＭのような記憶媒体において、又は公衆インターネット（ｐｕｂｌｉｃ ｉｎｔｅｒｎｅｔ）のようなネットワークを介して配布された後にバックグラウンド記憶装置に記憶され得る。暗号化鍵のような機密データ（ｓｅｎｓｉｔｉｖｅ ｄａｔａ）は、好ましくは安全な方式で配布され、記憶される。そうするための技術は、一般的に知られており、これ以上は記載しない。暗号装置は、スマートカードにおいて一部又は全部実施されうる。
【００１２】
暗号プロセッサによって行われる本発明による線形変換を、典型的なアプリケーションとしてブロック暗号におけるラウンド関数ｆの形態で以下に記載する。本質的には、当業者は、同様に他の暗号システムにおいて前記線形変換を使用することが出来るであろうし、以下に詳細に記載する暗号以外の暗号において前記線形変換を使用することが出来るであろう。
【００１３】
【記号表示及び定義】
以下の記号表示が典型的なアルゴリズムの記載において用いられる。Ｚ２ｎを、（排他論理和又はＸＯＲとも呼ばれる）座標式非等価演算（ｃｏｏｒｄｉｎａｔｅ−ｗｉｓｅ ａｄｄｉｔｉｏｎ ｍｏｄｕｌｏ ２）として定義される加算
【数１】
2004506246.tif 000003
を伴う長さｎ（ｎ ≧ １）の全てのバイナリベクトルのセットとする。 例えば、（１， ０， １， ０）及び（０， １， １， ０）はＺ２４の要素であり、
【数２】
2004506246.tif 000004
である。更に、スカラ乗算・： Ｚ２ ｘ Ｚ２ｎ → Ｚ２ｎは、全てのｘ ∈ Ｚ２ｎについて１・ｘ ＝ ｘ且つ０・ｘ ＝ （０， ０， …， ０） ∈ Ｚ２ｎとして定義される。ｎが偶数であり、且つｘ ∈ Ｚ２ｎである場合には、ｘ（Ｌ） ∈ Ｚ２ｎ／２及びｘ（Ｒ） ∈ Ｚ２ｎ／２が各々ｘの左半分及び右半分として定義される。例えば、ｘ ＝ （１， ０， １， １， ０， ０， １， ０） ∈ Ｚ２８である場合には、ｘ（Ｌ） ＝ （１， ０， １， １） ∈ Ｚ２４であり、且つｘ（Ｒ） ＝ （０， ０， １， ０） ∈ Ｚ２４である。符号‖は、ベクトルの連結、例えばｘ ＝ （ｘ（Ｌ） ‖ ｘ（Ｒ））を示すために用いられる。ベクトルｘ ∈ Ｚ２ｎの（ビットとも呼ばれる）要素は、左から右へ０からｎ−１まで番号を付けられ、即ち、ｘ ＝： （ｘ０， ｘ１， ｘ２， …， ｘｎ−１）となる。２つの要素ｘ ∈ Ｚ２ｎとｙ ∈ Ｚ２ｎとの間のハミング距離ｄＨ ： Ｚ２ｎ ｘ Ｚ２ｎ → Ｚは、２つのベクトルが相違する座標の数として定義され、即ち、ｄＨ（ｘ， ｙ） ＝＃｛ｘｉ≠ｙｉ ｜ ｉ ＝ ０， １， …， ｎ−１｝となる。要素ｘ ∈ Ｚ２ｎのハミング重みｗＨ ： Ｚ２ｎ → Ｚは非零座標の数として定義される。即ち、ｗＨ（ｘ） ＝＃｛ｘｉ≠０ ｜ ｉ ＝ ０， １， …， ｎ−１｝となる。
【００１４】
Ｚ２についてのｋ×ｍ行列（ｋ， ｍ ≧ １）のセットはＺ２ｋ×ｍによって示される。Ｚ２についてのｋ×ｋ恒等行列はＩｋによって示される。符号‖はまた、同数の行を備える行列の連結を示すためにも用いられ、例えば、Ａ ∈ Ｚ２４×６且つＢ ∈ Ｚ２４×８である場合には、Ｃ ：＝ （Ａ ‖ Ｂ） ∈ Ｚ２４×１４となる。
【００１５】
（ブロック）長さｎのバイナリ・エラー訂正コードＣは、Ｚ２ｎの部分線形空間である。この部分空間の要素は、コードワードと呼ばれる。部分空間の大きさがｋである場合には、Ｃは［ｎ， ｋ］コードと呼ばれる。斯様なコードは、前記行がＣのための基底を形成する生成行列Ｇ ∈ Ｚ２ｋ×ｎによって表され得る。即ち、Ｃ ＝ ｛ｍＧ ｜ ∈ Ｚ２ｋ｝となる。コードの最小距離ｄは、全ての任意の２つの別個のコードワードの間の距離の中で最小のものとして定義され、即ち、ｄ ＝ ｍｉｎ｛ｄＨ（ｘ， ｙ） ｜ ｘ， ｙ ∈ Ｃ且つｘ≠ｙ｝となる。最小ハミング距離ｄを備える［ｎ， ｋ］コードは［ｎ， ｋ， ｄ］コードとも呼ばれる。
【数３】
2004506246.tif 000005
であることに注意されたい。このことは、線形コードの最小ハミング距離が全非零コードワード中の最小ハミング重みと等しいことを意味する。
【００１６】
【ブロック暗号の構造】
典型的なブロック暗号は、Ｆｅｉｓｔｅｌ型暗号であり、（ＤＥＳのように）１６ラウンドから成る。ブロック長は６４ビットと等しく、鍵長は１２８ビットと等しい。鍵Ｋ ∈ Ｚ２１２８のもとでの暗号文Ｃ ∈ Ｚ２６４への平文Ｘ ∈ Ｚ２６４の電子コードブック（ＥＣＢ）モードにおける暗号化はＣ ＝ Ｅ（Ｋ， Ｘ）によって示される。
【００１７】
ラウンド関数は、ｆによって示され、Ｚ２４０ ｘ Ｚ２３２からＺ２３２へのマッピングである。このラウンド関数は、本発明の線形変換を組み入れており、以下により詳細に記載する。ラウンド関数の第１入力引数（ｆｉｒｓｔ ｉｎｐｕｔ ａｒｇｕｍｅｎｔ）はラウンド鍵Ｋｉ ∈ Ｚ２４０である（ここで、ｉはラウンド数を示す。ｉ ＝ １， ２， …， １６）。これらのラウンド鍵は、所謂鍵スケジュール処理アルゴリズムで１２８ビット鍵Ｋから算出される。任意の適切な鍵スケジュール処理アルゴリズムが用いられても良く、詳細には記載しない。第２入力引数は、ラウンドｉの後の中間結果の右半分である。この中間結果は、Ｘ ＝： （Ｘ０（Ｒ） ‖ Ｘ０（Ｌ））を伴うＸｉ ∈ Ｚ２６４（ｉ＝０， １， …， １６）によって示される。
【００１８】
この表記法では、暗号文Ｃ ∈ Ｚ２６４の算出は図２に示されているような以下のステップから成る。 １． ｉ ＝ １， ２， …， １５に対して、
【数４】
2004506246.tif 000006
を算出し、Ｘｉ（Ｌ） ＝ Ｘｉ−１（Ｒ）と設定する。
【数５】
2004506246.tif 000007
を算出し、Ｘ１６（Ｒ） ＝ Ｘ１５（Ｒ）と設定する。暗号文はＣ ：＝ （Ｘ１６（Ｌ） ‖ Ｘ１６（Ｒ））と定義される。
【００１９】
図２Ａは最初の１５ラウンド（ｉ ＝ １， ２， …， １５）に対して用いられる暗号構造を示している。図２Ｂは最後の１６番目のラウンドを示している。図２Ａの前のラウンドと比べての図２Ｂにおける変則のスワップ（ｉｒｒｅｇｕｌａｒ ｓｗａｐ）に注意されたい。これは、通常Ｆｅｉｓｔｅｌ型構造において行われる。なぜなら、この場合には、復号アルゴリズム（即ち、Ｘ ＝ Ｅ−１（Ｋ， Ｃ）の算出）が（逆順のラウンド鍵を備える）暗号化アルゴリズムと同じであるからである。それは暗号的意味（ｃｒｙｐｔｏｇｒａｐｈｉｃ ｓｅｎｓｅ）においてはなんの意味も持たない。
【００２０】
【ラウンド関数】
図３は、ラウンド関数ｆの好ましい実施例の全体的なブロック図を示している。まず、ステップ３１０において例えば３２ビットのラウンド鍵の一部がデータビットに加算される。次に、ステップ３２０においては、Ｓ−ｂｏｘが、好ましくは差分解読法及び線形解読法に対する最適の（ローカルな）耐性（ｒｅｓｉｓｔａｎｃｅ）を提供する非線形の置換え（ｎｏｎ−ｌｉｎｅａｒ ｓｕｂｓｔｉｔｕｔｉｏｎ）を行う。その上、好ましくは、所定の最大確率（ｍａｘｉｍｕｍ ｐｒｏｂａｂｉｌｉｔｙ）を備えるトリビアルではない（ｎｏｎ−ｔｒｉｖｉａｌ）（ローカルな）特性が、以下により詳細に記載されているように（ラウンド）鍵に依存して作られる。最後に、ステップ３３０においては、多数のラウンドにわたって高い拡散を供給するために線形変換が用いられる。エラー訂正コードから斯様な線形変換を生成する方法を以下により詳細に記載する。
【００２１】
Ｆｅｉｓｔｅｌ型構造は、ラウンド関数の全射性（ｓｕｒｊｅｃｔｉｖｉｔｙ）に制限を設けない。しかしながら、好ましくは、ラウンド関数は、固定（ラウンド）鍵に対するあらゆる選択について全単射である。このことは、ラウンド関数の非一様性に基づいて攻撃を防ぐ。
【００２２】
図４は、Ｓ−ｂｏｘを組み入れる好ましい構成のより詳細を提供している。この典型的なシステムにおいて、ラウンド関数ｆはＺ２４０ ｘ Ｚ２３２からＺ２３２へのマッピングである。第１入力引数はラウンド鍵Ｋｉ ∈ Ｚ２４０であり、第２入力引数は中間結果Ｘｉ−１の右半分である。出力は、ｆ（Ｋｉ， Ｘｉ−１（Ｒ）） ∈ Ｚ２３２によって示される。この図においては、Ｋｉ（１） ∈ Ｚ２３２及びＫｉ（２） ∈ Ｚ２８がＫｉ ＝： （Ｋｉ（１） ‖Ｋｉ（２））として定義される。ステップ３１０においては、鍵加算が行われ、ステップ３２０の鍵依存置換ボックス（Ｓ−ｂｏｘ）層が続く。この例においては、Ｓ−ｂｏｘ層が、各々がデータブロックの１／８に作用する８個のより小さなＳ−ｂｏｘ（Ｓ０， Ｓ１， Ｓ２， …， Ｓ７）から成る。Ｓ−ｂｏｘ変換はＺ２８ ｘ Ｚ２３２からＺ２３２へのマッピングであり、ラウンドｉにおける第１入力引数はラウンド鍵Ｋｉ（２）であり、第２入力引数は鍵加算の結果、即ち
【数６】
2004506246.tif 000008
である。Ｓ−ｂｏｘ変換の３２ビット出力は
【数７】
2004506246.tif 000009
によって示される。以下にこのマッピングについて記載する。最後に、ステップ３３０においては、Ｚ２３２からＺ２３２への線形変換が適用される。入力は
【数８】
2004506246.tif 000010
であり、その出力は
【数９】
2004506246.tif 000011
によって示される。この表記法では、関数ｆが
【数１０】
2004506246.tif 000012
によって与えられる。
【００２３】
【Ｓ−ｂｏｘ】
原則的には、ブロック暗号においては任意の適切なＳ−ｂｏｘ層が用いられ得る。本明細書に記載されている好ましい実施例においては、各Ｓ−ｂｏｘが４ビットサブブロックに作用する。他のサイズのサブブロックも用いられ得ることを認識されたい。好ましくは、各Ｓ−ｂｏｘに対して少なくとも２つの所定の並び替えのセットが用いられ、ここでは、Ｓ−ｂｏｘを用いる前に毎度これらの並び替えのうちの１つが（疑似）ランダム方式で選択される。好ましくは、ラウンド鍵がこの選択のために用いられる。好ましい実施例においては、各Ｓ−ｂｏｘが２つの並び替えと関連付けられており、ここでは、ラウンド鍵のうちのある所定のビットが、両並び替えのうちのどちらを用いるかを選択するために用いられる。４ビットサブブロックに作用するＳ−ｂｏｘなどの相対的に小さなＳ−ｂｏｘの使用は、通常、並列のＳ−ｂｏｘの列を必要とし、各々が少なくとも２つの非線形の並び替えのセットの各々と関連付けられている。
【００２４】
図４は、３２ビットブロックに作用し、且つ４ビットＳ−ｂｏｘを用いる、結果として８個のＳ−ｂｏｘが並列に用いられることとなるブロック暗号の好ましい実施例を図示しており、前記Ｓ−ｂｏｘの各々は２つの並び替えから成る。この実施例に対しては、以下の表記法を用いる。Ｓ−ｂｏｘ変換の第１入力引数Ｋｉ（２）の中のビットは、ｋｊ（ｉ）（ｊ ＝ ０， １， …，７） によって示されるとする。即ち、Ｋｉ（２） ＝： （ｋ０（ｉ）， ｋ１（ｉ）， …， ｋ７（ｉ））となる。ベクトルＮｊ（ｉ） ∈ Ｚ２４ （ｊ ＝ ０， １， …，７）は
【数１１】
2004506246.tif 000013
として定義される。Ｓ−ｂｏｘマッピングは、８個のマッピングＳｊ ： Ｚ２ ｘ Ｚ２４ → Ｚ２４（ｊ ＝ ０， １， …，７） の連結から成る。第１入力引数は、Ｓｊのための２つの並び替えのうちどちらを用いるのかを選択する鍵ビットｋｊ（ｉ）である。第２入力引数は、Ｓｊのための選択された４ビット並び替えに対する入力であるＮｊ（ｉ）である。この並び替えの対応４ビット出力は、Ｓ−ｂｏｘの出力でもあり、Ｓｊ（ｋｊ（ｉ）， Ｎｊ（ｉ））によって示される。この表記法では、関数Ｓが、
【数１２】
2004506246.tif 000014
によって与えられる。任意の適切なＳ−ｂｏｘ層が用いられ得る。好ましくは、特許出願の欧州特許出願番号ＥＰ００２０２３２６．５（出願人整理番号：ＰＨＮＬ０００３６５）によるＳ−ｂｏｘが用いられる。
【００２５】
【線形変換行列】
Ｓ−ｂｏｘの置換作用の後には、線形変換Ｌが行われる。３２ビットサブブロックを備える好ましい実施例においては、Ｌ ： Ｚ２３２ → Ｚ２３２となる。上記の好ましいＳ−ｂｏｘ構成を用いる場合、この線形変換に対する入力は、ベクトル
【数１３】
2004506246.tif 000015
である。このベクトルの座標は、ｙｊｉ（ｊ ＝ ０， １， …，３１） によって示されるであろう。即ち、
【数１４】
2004506246.tif 000016
となる。この場合には、マッピングＬをベクトル行列の乗算として表現することができ、この行列は、Ａ ∈ Ｚ２３２×３２ ：
【数１５】
2004506246.tif 000017
によって示される。
【００２６】
【線形変換行列の構成】
Ｌ（ｘ） ＝ ｘＡにより定義される線形変換Ｌは以下の基準を満たすように構成される。 １． Ｚ２にわたっての線形性。 ２． 可逆性（ｉｎｖｅｒｔｉｂｉｌｉｔｙ）、即ち、行列ＡがＺ２にわたって非特異である。 ３． 高い拡散特性。
【００２７】
関数Ｌの構成は、バイナリ線形エラー訂正コードに基づく。マッピングＬは、バイナリ・エラー訂正コードのための生成行列Ｇ ＝ （Ｉｋ ‖ Ａ） ∈ Ｚ２ｋ×２ｋと関連付けられる。ｘ ∈ Ｚ２ｋを伴う全てのコードワード（ｘ ‖ ｘＡ） ∈ Ｚ２２ｋについて、左半分のｘがＬに対する入力に対応する一方で、右半分のｘＡが出力に対応することに注意されたい。設計基準（ｉ）は、全てのバイナリ・エラー訂正コードに対して満足される一方で、（ｉｉ）は、ＡがＺ２にわたって非特異である場合に限り満足されることに注意されたい。基準（ｉｉｉ）は、コードワードの最小ハミング重みによって表され得る、即ち、この最小距離が大きいほど、拡散特性は良くなることにも注意されたい。
【００２８】
３２ビットブロック（即ち、ｋ ＝ ３２且つＡ ∈ Ｚ２３２×３２）についてＡの構成を以下に説明する、Ａの構成は、１２と等しい最小ハミング距離を備える［６４， ３２］コードの構成のための始点（ｓｔａｒｔｉｎｇ ｐｏｉｎｔ）としてＸＢＣＨ（ｂｉｎａｒｙ ｅｘｔｅｎｄｅｄ Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｃｑｕｅｎｇｈｅｍ）コードを用いる。斯様なコードが最適であること、即ち、任意のバイナリ［６４， ３２］コードが１２以下の最小距離を持つことはよく知られている。前記コードが線形であることから、このことは、任意の非零コードワードの最小ハミング重みが少なくとも１２であることを意味する。このことは、ｔビット（ｔ ＞ ０）の入力における（小さな）変化は出力における少なくともｍａｘ｛０， １２−ｔ｝ビットの変化を意味するという点で、マッピングＬの拡散特性がビットレベルにおいて最適であることを意味することに注意されたい。
【００２９】
行列Ａを含むバイナリ［６４， ３２， １２］コードのための生成行列は、図５に図示されているように、以下のように構成される。
（ｉ）　　ステップ５１０においては、バイナリ線形エラー訂正コードに対応する標準形の生成行列Ｇ’’ （即ち、Ｂ ∈ Ｚ２３２×２８を備えるＧ’’ ＝ （Ｉ３２ ‖ Ｂ））が取得される。斯様な生成行列Ｇ’’は、好ましくは、ＢＣＨ（Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｃｑｕｅｎｇｈｅｍ）コードから始まり、以下のように構成される。
（ａ）ステップ５１２においては、生成行列Ｇ ∈ Ｚ２３６×６３が、生成多項式（ｇｅｎｅｒａｔｏｒ ｐｏｌｙｎｏｍｉａｌ）ｇ（ｘ） ：＝ ｘ２７ ＋ ｘ２２ ＋ ｘ２１ ＋ ｘ１９ ＋ ｘ１８ ＋ ｘ１７ ＋ ｘ１５ ＋ ｘ８ ＋ ｘ４ ＋ ｘ ＋ １を備えるバイナリ［６３， ３６， １１］ＢＣＨコードに対して構成され、ここで、Ｇの行ｊ（ｊ ＝ ０， １， …， ３５）は多項式ｘｊｇ（ｘ）に対応する。より正確には、ｇｉ ∈ Ｚ２を備えるｇ（ｘ） ＝： Σｉ ＝ ０， １， …， ２７ｇｉｘｉである場合に、行列の最初の行は（ｇ０， ｇ１， ｇ２， …， ｇ２７， ０， ０， …， ０） ∈ Ｚ２６３によって与えられる。生成行列の行ｊ（ｊ ＝ ０， １， …， ３５）は、ｊ位置にわたってのこの最初の行の右への循環シフト（ｃｙｃｌｉｃ ｓｈｉｆｔ）により与えられる。
（ｂ）ステップ５１４においては、このコードが、Ｇの最後の４つの行及び列を削除することにより［５９， ３２， １１］コードへ縮小される。
（ｃ）ステップ５１８においては、この縮小されたコードが、各コードワードにパリティチェック符号を加えることにより［６０， ３２， １２］コードへ拡大される。パリティチェックを加えることによる１つの列の付加は最小距離の増大をもたらすことに注意されたい。この［６０， ３２， １２］コードに対する３２×６０生成行列はＧ’によって示される。
（ｄ）ステップ５２０においては、標準形の生成行列Ｇ’’、即ち、Ｂ ∈ Ｚ２３２×２８を備えるＧ’’ ＝ （Ｉ３２ ‖ Ｂ）を得るために、Ｇ’においてガウス消去が行われる。これは、縮小された［６０， ３２， １２］ＸＢＣＨコードに対する生成行列であることに注意されたい。
（ｉｉ）　　結果として生じる行列Ｃ ∈ Ｚ２３２×３２がＺ２にわたって非特異であるようにＢを４つの列でＢを拡大する。好ましくは、この４つの列が疑似ランダムに選択される。
（ａ）各々が３２個の（疑似）ランダムに選択されたバイナリの要素（ｂｉｎａｒｙ ｅｌｅｍｅｎｔ）を備える４つの列を作成する。
（ｂ）新しい前記４つの列でＢを拡大することによりテスト行列を作成する（本質的には、新たに加えられる列の列位置は重要ではない）。
（ｃ）テスト行列が可逆であるかどうかをチェックする。このテストに対しては、任意の適切な方法、例えばガウス消去に基づく方法が用いられ得る。
（ｄ）そうである場合には、プロセスを停止し（行列が見つけられており）、そうでない場合には、少なくとも１つの新しい列を生成することにより再始動する。
【００３０】
前記４つの列の要素はまた、ランダム作成プロセスを用いる代わりに任意の他の適切な方式においても生成され得ることを認識されたい。
【００３１】
マルチビットのＳ−ｂｏｘを備えるラウンド関数の構成のため、このマルチビットレベルにおける良好な拡散特性も望ましい。４ビットＳ−ｂｏｘに対しては、このことが以下のように表され得る（他のビット数の変形例は十分に当業者のスキルの範囲内にある）。コードワードｃ ∈ Ｚ２３２の４ビットベクトルｎｉ（ｉ ＝ ０， １， …， ７）がｃ ＝： （ｎ０ ‖ ｎ１ ‖…‖ ｎ７）として定義される場合には、ｃのニブル重み（ｎｉｂｂｌｅ ｗｅｉｇｈｔ）がＮＷ（ｃ） ：＝＃｛ｉ ‖ ｎｉ≠（０， ０， ０， ０）， ｉ ＝ ０， １， …， ７｝として定義される。ニブルレベルにおける拡散特性は、全ての非零コードワードにわたっての最小ニブル重みによって表され得る。即ち、この最小重みが大きいほど、ニブルレベルにおける拡散特性は良くなる。マルチビットレベルにおける（この例においてはニブルレベルにおける）高い拡散を達成するために、ステップ５３０においては、生成行列（Ｉ ‖ Ｐ１ＣＰ２）を備える［６０， ３２， １２］コードにおける全てのコードワードが高いニブル重みを持つように２つの置換行列Ｐ１， Ｐ２ ∈ Ｚ２３２×３２が選択される。最終的に求められる行列Ａ ：＝ Ｐ１ＣＰ２は線形変換のために用いられる。好ましい実施例においては、置換行列Ｐ１及びＰ２が（疑似）ランダムに生成される。（Ｉ ‖ Ａ）によって生成されるコードの最小ニブル重みは７と等しいことが確認され得る。
【００３２】
以下の表においてこのように生成される線形変換行列Ａの行を示す（ａ０は第１の行であり、ａ１は第２の行であり、…、ａ３１は最後の行である）。ベクトル行列積（ｖｅｃｔｏｒ−ｍａｔｒｉｘ ｐｒｏｄｕｃｔ）は、ｙｋ（ｉ） ＝ １（ｋ ＝ ０， １， …， ３１）である行ａｋのＸＯＲに対応することに注意されたい。
【００３３】
【表１】
2004506246.tif 000018
【００３４】
【ＭＤＳコードとの比較】対象鍵暗号におけるＭＤＳコードに基づく線形変換の使用は、Ｓ． Ｖａｕｄｅｎａｙ， “Ｏｎ ｔｈｅ Ｎｅｅｄ ｆｏｒ Ｍｕｌｔｉ−Ｐｅｒｍｕｔａｔｉｏｎｓ： Ｃｒｙｐｔａｎａｌｙｓｉｓ ｏｆ ＭＤ４ ａｎｄ ＳＡＦＥＲ”， Ｆａｓｔ Ｓｏｆｔｗａｒｅ Ｅｎｃｒｙｐｔｉｏｎ （２ｎｄ）， ＬＮＣＳ １００８， Ｓｐｒｉｎｇｅｒ， １９９５， ｐｐ． ２８６−２９７から既知である。以下の表は、本発明によるＸＢＣＨベースの行列において用いられる構成のニブル重み分布をＭＤＳコードの（ニブル）重み分布と比較している。エントリ（ｅｎｔｒｙ）は、所与のニブル重みを備える非零コードワードの数を表す。
【００３５】
【表２】
2004506246.tif 000019
【００３６】
この表から分るように、これら２つの構成のニブル重み分布は非常に類似している。ＸＢＣＨ構成の最小ニブル重みは、この基準に対して最適であることを示され得るＭＤＳ構成の最小重みより２つだけ少ない。しかしながら、ＭＤＳ構成は、ブロック暗号の解読において活用され得る関連線形変換のＦ１６（のサブフィールド）にわたっての線形性などの付加的な数学的構造を含むという不利な点を持つ。例えば、Ｓ−ｂｏｘ（及び結果としての完成したブロック暗号（ｃｏｍｐｌｅｔｅ ｂｌｏｃｋ ｃｉｐｈｅｒ））は、Ｆ１６ → Ｆ１６からのマッピングによって記述され得る。更に、本明細書に記載の構成は、ビットレベルにおける最適な拡散を保証する。
【図面の簡単な説明】
【図１】暗号システムのブロック図を示す。
【図２Ａ】線形変換を組み入れている暗号のあるラウンドを示す。
【図２Ｂ】線形変換を取り入れている暗号のあるラウンドを示す。
【図３】ラウンド関数のステップを図示する。
【図４】Ｓ−ｂｏｘ構成の好ましい構成を示す。
【図５】線形変換行列を生成するステップを示す。
【図３】
2004506246.tif 000020
【図４】
2004506246.tif 000021
【図５】
2004506246.tif 000022
【国際公開パンフレット】
2004506246.tif 000023
2004506246.tif 000024
2004506246.tif 000025
2004506246.tif 000026
2004506246.tif 000027
2004506246.tif 000028
2004506246.tif 000029
2004506246.tif 000030
2004506246.tif 000031
2004506246.tif 000032
2004506246.tif 000033
2004506246.tif 000034
2004506246.tif 000035
2004506246.tif 000036
2004506246.tif 000037
2004506246.tif 000038
2004506246.tif 000039
2004506246.tif 000040
【国際公開パンフレット（コレクトバージョン）】
2004506246.tif 000041
2004506246.tif 000042
【国際公開パンフレット（コレクトバージョン）】
2004506246.tif 000043
2004506246.tif 000044
【国際調査報告】
2004506246.tif 000045
2004506246.tif 000046
2004506246.tif 000047
2004506246.tif 000048