図面 (/)

技術 対称鍵暗号のための線形変換

出願人 コーニンクレッカフィリップスエヌヴェ
発明者 ロエルセペトルスエルエー
出願日 2001年7月20日 (20年2ヶ月経過) 出願番号 2002-518682
公開日 2004年2月26日 (17年7ヶ月経過) 公開番号 2004-506246
状態 特許登録済
技術分野 暗号化・復号化装置及び秘密通信
主要キーワード 置換ボックス テスト行 部分線 スカラ乗算 線形変換行列 換ボックス 数学的構造 出力データブロック
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2004年2月26日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (4)

課題・解決手段

対象鍵暗号用の線形変換行列Aを生成する方法は、バイナリ[n, k, d]エラー訂正コードの生成を含み、ここで、k < n < 2kであり、dは前記バイナリ・エラー訂正コードの最小距離である。前記コードは、B ∈ Z2k×(n−k)を備える標準形G = (Ik ‖ B)の生成行列G ∈ Z2k×nによって表される。前記行列Bは、結果として生じる行列Cが非特異であるように2k−n個の列で拡大される。前記線形変換行列Aは、行列Cから導き出される。好ましくは、前記エラー訂正コードはXBCHコードに基づく。

概要

背景

デジタルオーディオ及び/又はビデオ著作権保護の分野における暗号のアプリケーションが、ますます重要になっている。これらのアプリケーションは、コンテンツの暗号化/復号及びアクセス管理の機能を含む。斯様なアプリケーションに対しては、ブロック暗号が用いられ得る。ブロック暗号のよく知られているファミリーはFeistel型暗号である。Feistel型暗号においては、入力データブロックが多数のラウンド(round)において処理される。各ラウンドにおいては、前記ブロックの2つのサブブロック(半分)が別個に作用される。第1サブブロックはラウンド関数の出力と組み合わされ、第2サブブロックは変更されないままである。ラウンドの最後には、2つのサブブロックがスワップされ、変更されていないサブブロックが次のラウンドにおいて処理されることを確実なものにする。ラウンド関数は入力として第2サブブロック及びラウンド鍵をとる。通常、ラウンド関数は、例えばXOR演算を用いて、ラウンド鍵を第2サブブロックと組み合わせる。そのうえ、ラウンド関数は第2サブブロックにおける非線形演算及び線形変換を行う。典型的には、非線形変換置換ボックス(substitution box) (S−box)層から成り、S−box層は、例えば4乃至8ビットのより小さなサブブロックに並列に作用する多数のS−boxから成る。S−box層の後には、線形演算が、個々のS−boxによってもたらされたビット変化が次のラウンドにおいて可能な限り多くのS−boxにわたって伝えられるように適当な拡散が行われることを確実なものにする。

概要

対象鍵暗号用の線形変換行列Aを生成する方法は、バイナリ[n, k, d]エラー訂正コードの生成を含み、ここで、k < n < 2kであり、dは前記バイナリ・エラー訂正コードの最小距離である。前記コードは、B ∈ Z2k×(n−k)を備える標準形G = (Ik ‖ B)の生成行列G ∈ Z2k×nによって表される。前記行列Bは、結果として生じる行列Cが非特異であるように2k−n個の列で拡大される。前記線形変換行列Aは、行列Cから導き出される。好ましくは、前記エラー訂正コードはXBCHコードに基づく。

目的

本発明の目的は、最適バイナリ線形エラー訂正コード(optimal binary linear error−correcting code)に基づいて、ビットレベルにおける保証された最適拡散特性を備える対称鍵暗号用の非特異バイナリ行列(non−singular binary matrix)によって表される可逆線形変換(invertible linear transformation)を提供する

効果

実績

技術文献被引用数
2件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

対象鍵暗号用の線形変換行列Aを生成する方法であり、−、k < n < 2kであり、dはバイナリエラー訂正コード最小距離であって、B ∈ Z2k×(n−k)を備える標準形G = (Ik ‖ B)の生成行列G ∈ Z2k×nによって表されるバイナリ[n, k, d]エラー訂正コードを生成するステップ、− 結果として生じるCが非特異であるように2k−n個の列で行列Bを拡大するステップ、及び− 行列Cから行列Aを導き出すステップを含む方法。

請求項2

前記2k−n個の列で行列Bを拡大するステップが、対話方式で、− 各々がk個のバイナリの要素を備える2k−n個の列を(疑似ランダムに生成するステップ、− 前記Bのn−k個の列及び生成された前記2k−n個の列から成るテスト行列を形成するステップ、及び− 非特異テスト行列が見つけられるまで前記テスト行列が非特異であるかどうかをチェックし、見つけられた前記テスト行列を行列Cとして用いるステップを含む請求項1に記載の方法。

請求項3

前記行列Cから行列Aを導き出すステップが、−生成行列(I ‖ P1CP2)によって表される[2k, k, d]エラー訂正コードにおける全てのコードワードが所定のマルチビット重みを持つように2つの置換行列P1, P2 ∈ Z2k×kを決定するステップ、及び− P1CP2を行列Aとして用いるステップを含む請求項1に記載の方法。

請求項4

前記対象鍵暗号が、mビットサブブロックに作用するS−boxを持つS−box層を備えるラウンド関数を含み、全ての非コードワードにわたって最小の前記所定のマルチビット重みが、所定のmビット重みと等しい請求項3に記載の方法。

請求項5

前記2つの置換行列P1及びP2を決定するステップが、(疑似)ランダム方式で前記行列を繰り返し生成するステップを含む請求項3に記載の方法。

請求項6

前記暗号が32ビットブロックに作用するラウンド関数を含み、前記[n, k, d]エラー訂正コードを生成するステップが、バイナリに拡張されたBose−Chaudhuri−Hocquenghem (XBCH)[64, 36, 12]コードを生成するステップ、及び4つの行を削除することによりこのコードを[60, 32, 12]縮小BCHコードへ縮小するステップを含む請求項1に記載の方法。

請求項7

プロセッサに請求項1に記載の方法を行わせるよう作用するコンピュータプログラムプロダクト

請求項8

入力データブロック出力データブロック暗号的に変換するシステムであり、前記データブロックはnデータビットを有し、当該システムは、− 前記入力データブロックを受け取る入力部、− 請求項1に記載の方法により生成される線形変換行列Aを記憶する記憶装置、− 前記入力データブロックにおける線形変換、又は前記線形変換行列Aを用いる前記入力データブロックの誘導を行う暗号プロセッサ、及び− 処理された前記入力データブロックを出力する出力部を含むシステム。

技術分野

0001

本発明は、バイナリエラー訂正コード(binary error−correcting code)に基づいて対称鍵暗号用の線形変換を生成する方法に関する。

0002

デジタルオーディオ及び/又はビデオ著作権保護の分野における暗号のアプリケーションが、ますます重要になっている。これらのアプリケーションは、コンテンツの暗号化/復号及びアクセス管理の機能を含む。斯様なアプリケーションに対しては、ブロック暗号が用いられ得る。ブロック暗号のよく知られているファミリーはFeistel型暗号である。Feistel型暗号においては、入力データブロックが多数のラウンド(round)において処理される。各ラウンドにおいては、前記ブロックの2つのサブブロック(半分)が別個に作用される。第1サブブロックはラウンド関数の出力と組み合わされ、第2サブブロックは変更されないままである。ラウンドの最後には、2つのサブブロックがスワップされ、変更されていないサブブロックが次のラウンドにおいて処理されることを確実なものにする。ラウンド関数は入力として第2サブブロック及びラウンド鍵をとる。通常、ラウンド関数は、例えばXOR演算を用いて、ラウンド鍵を第2サブブロックと組み合わせる。そのうえ、ラウンド関数は第2サブブロックにおける非線形演算及び線形変換を行う。典型的には、非線形変換置換ボックス(substitution box) (S−box)層から成り、S−box層は、例えば4乃至8ビットのより小さなサブブロックに並列に作用する多数のS−boxから成る。S−box層の後には、線形演算が、個々のS−boxによってもたらされたビット変化が次のラウンドにおいて可能な限り多くのS−boxにわたって伝えられるように適当な拡散が行われることを確実なものにする。

0003

Feistel型暗号のよく知られている例は、16ラウンドから成るDESである。各ラウンドにおいては、まず、データの右半分の32ビットが48ビットに拡大される。次に、鍵スケジュール処理アルゴリズム(key scheduling algorithm)を備える56ビットDES鍵から計算される48ビットラウンド鍵は、これらの48ビットに対してビットごとに非等価演算(add modulo two)をされる。次いで、S−boxの層はこのデータにおいて非線形演算をする。DESにおいて、S−box層は並列の8個の6−4ビットS−box(six−to−four bit S−box)から成り、即ち、S−boxの各々は、S−boxごとに1つの固定マッピングテーブル(fixed mappingtable)を用いて6ビット入力ブロックを4ビット出力ブロックに変換する。S−box層の出力は、32ビットデータブロックである。この32ビットデータブロックにおいて行われる線形変換は、S−boxによってもたらされたビット変化が次に続くラウンドにおいて多くの他のS−boxにわたって伝えられることを確実なものにするビットの並び替え(bit−permutation)である。DESの不利な点は、現在では高レベルセキュリティを提供するのに不十分であると考えられる56ビットという小さな鍵の大きさにある。しかしながら、しらみ潰しの鍵探索(exhaustive key search)は、16個の48ビットラウンド鍵を算出する別の鍵スケジュール処理アルゴリズムと組み合わされたより長い鍵を用いることによって防止され得る。公開文献で発表されているDESに対する2つの最も強力な攻撃(attack)は、幅広いブロック暗号に適用され得る一般的な攻撃である差分解読法(differential cryptanalysis)及び線形解読法(linear cryptanalysis)である。DESは、鍵長及び/又は鍵スケジュール処理アルゴリズムを変更することによってはこれらの攻撃に対してあまり強化され得ないことが示されている。しかしながら、アルゴリズムのラウンド関数における変更は、これらの攻撃に対する強度にかなり影響を及ぼし得る。

背景技術

0004

線形変換に対しては、該変換が良好な拡散特性を持つことが望まれる。最近、S. Vaudenaryが、線形変換を構成する(construct)ために線形エラー訂正コードを用いることを提案しており、説明は、”On the Need for Multi−Permutations: Cryptanalysis of MD4 and SAFER”, Fast Software Encryption (2nd), LNCS 1008, Springer, 1995, pp. 286−297において見出され得る。線形変換の拡散特性は、対応するエラー訂正コードの最小ハミング距離と関連しており、この距離が大きいほど、関連線形変換行列の拡散特性は良くなる。Vaudenaryは、所謂シングルトン限界(Singleton bound)に達し、それ故最適拡散を供給する、有限フィールド(finite fields)にわたっての最大距離分離(MDS)コードの使用を提案している。しかしながら、この構成は、結果として生じる線形変換が、解読において活用され得る、付加的な数学的構造(additional mathematical structure)、例えば、構成のために用いられた有限フィールド(及び全てのサブフィールド)にわたっての線形性(linearity)を含むという不利な点を持つ。

0005

本発明の目的は、最適バイナリ線形エラー訂正コード(optimal binary linear error−correcting code)に基づいて、ビットレベルにおける保証された最適拡散特性を備える対称鍵暗号用の非特異バイナリ行列(non−singular binary matrix)によって表される可逆線形変換(invertible linear transformation)を提供することにある。この変換は、解読において活用され得る結果として生じる線形変換の付加的な数学的構造が避けられるという意味で、より不規則であるMDS構成以上の利点を持つ。

0006

本発明の目的を満たすために、エラー訂正コードから導き出される行列は、前記コードの長さが2倍の大きさと等しく、線形変換のための基底(basis)として用いられ得る結果として生じる行列が非特異であるように多数の列で拡大される。このことは、ラウンド関数の非一様性(non−uniformity)に基づいて攻撃を防ぐ。

0007

従属項2の対策において規定されているように、新しい列は、適切な列を見つけるために(疑似ランダムに生成され得る。

0008

従属項3の対策において規定されているように、行列Cは、所定のマルチビット重み(multi−bit weight)を持つ関連線形エラー訂正コードを備える線形変換行列を見つけるために並び替えられる。従属項4の対策において規定されているように、このマルチビット重みは、暗号のS−boxにわたっての適当な拡散を確実なものにする。例えば、各S−boxがmビット出力を供給する並列に作用する多数のS−boxから成るS−box層に対しては、関連バイナリ・エラー訂正コード中のワードのmビット部分の拡散を調べるのが適切であり、このことは、全ての非コードワード(non−zero codeword)にわたっての最小mビット重みで表され得る。

課題を解決するための手段

0009

以下に図面に示されている実施例を参照して本発明のこれら及び他の特徴を説明し、明らかにする。

0010

本発明を説明する目的で、線形変換を用いる暗号システムを、電子コードブック(ECB)モードにおけるブロック暗号として記載する。当業者は同様に他のモードにおいて前記システムを使用することが出来るであろう。これらは、DESのための標準的なFIPSモード演算、即ち、暗号ブロック連鎖(CBC)、暗号フィードバック(CFB)及び出力フィードバック(OFB)のモードの演算を含む。更に、このシステムはまた、操作検出コード(Manipulation Detection Codes)(MDCs)、メッセージ認証コード(Message Authentication Codes)(MACs)及び疑似乱数生成器(pseudo−random number generator)のためのよく知られている構成においても用いられ得る。

0011

図1は、典型的な暗号装置100のブロック図を示している。暗号装置100はデジタル入力ブロックXを得るための入力部110を有する。デジタル入力ブロックXは任意の適切なサイズであり得る。この装置は、デジタル入力ブロックXをデジタル出力ブロックE(X)に変換するための暗号プロセッサ120を更に有する。好都合なことに、デジタル出力ブロックはデジタル入力ブロックと実質的に等しい長さを持つ。装置100は、デジタル出力ブロックを出力する出力部130を有する。好ましい実施例においては、暗号プロセッサが、デジタル入力ブロックを鍵ビットKと合成(merge)し、入力ブロックX及び鍵Kに非線形に依存する出力ブロックE(X, K)を作成することにより、デジタル入力ブロックをデジタル出力ブロックに変換する。鍵(又は鍵スケジューラに与えられる最初の鍵)を得るために、暗号装置は第2入力部140を有する。暗号装置は、PCなどの従来のコンピュータを用いて、又は専用の暗号化/復号装置を用いて実施され得ることを認識されたい。デジタル入力ブロックは、通信ネットワークを介して、ハードディスク若しくはフロッピー(R)ディスクなどのデータ記憶媒体から、又はユーザにより直接的に入力されるといった種々の方式で得られ得る。同様に、デジタル出力ブロックは、通信ネットワークを介して、データ記憶媒体に記憶される、又はユーザに対して表示されるといった種々の方式で出力され得る。好ましくは、この目的のために安全な手段(secure means)が用いられる。暗号プロセッサは、例えばパーソナルコンピュータにおいて用いられるような従来のプロセッサであっても良いが、専用の暗号プロセッサであっても良い。このプロセッサは、通常、本発明によるアルゴリズムのステップを行う適切なプログラムファームウェア)の制御のもとで動作される。このコンピュータプログラムプロダクトは、通常、ハードディスク又はROMなどのバックグラウンド記憶装置(background storage)からロードされる。コンピュータプログラムプロダクトは、CD−ROMのような記憶媒体において、又は公衆インターネット(public internet)のようなネットワークを介して配布された後にバックグラウンド記憶装置に記憶され得る。暗号化鍵のような機密データ(sensitive data)は、好ましくは安全な方式で配布され、記憶される。そうするための技術は、一般的に知られており、これ以上は記載しない。暗号装置は、スマートカードにおいて一部又は全部実施されうる。

0012

暗号プロセッサによって行われる本発明による線形変換を、典型的なアプリケーションとしてブロック暗号におけるラウンド関数fの形態で以下に記載する。本質的には、当業者は、同様に他の暗号システムにおいて前記線形変換を使用することが出来るであろうし、以下に詳細に記載する暗号以外の暗号において前記線形変換を使用することが出来るであろう。

0013

記号表示及び定義】
以下の記号表示が典型的なアルゴリズムの記載において用いられる。Z2nを、(排他論理和又はXORとも呼ばれる)座標式非等価演算(coordinate−wise addition modulo 2)として定義される加算
【数1】
を伴う長さn(n ≧ 1)の全てのバイナリベクトルのセットとする。 例えば、(1, 0, 1, 0)及び(0, 1, 1, 0)はZ24の要素であり、
【数2】
である。更に、スカラ乗算・: Z2 x Z2n → Z2nは、全てのx ∈ Z2nについて1・x = x且つ0・x = (0, 0, …, 0) ∈ Z2nとして定義される。nが偶数であり、且つx ∈ Z2nである場合には、x(L) ∈ Z2n/2及びx(R) ∈ Z2n/2が各々xの左半分及び右半分として定義される。例えば、x = (1, 0, 1, 1, 0, 0, 1, 0) ∈ Z28である場合には、x(L) = (1, 0, 1, 1) ∈ Z24であり、且つx(R) = (0, 0, 1, 0) ∈ Z24である。符号‖は、ベクトルの連結、例えばx = (x(L) ‖ x(R))を示すために用いられる。ベクトルx ∈ Z2nの(ビットとも呼ばれる)要素は、左から右へ0からn−1まで番号を付けられ、即ち、x =: (x0, x1, x2, …, xn−1)となる。2つの要素x ∈ Z2nとy ∈ Z2nとの間のハミング距離dH : Z2n x Z2n → Zは、2つのベクトルが相違する座標の数として定義され、即ち、dH(x, y) =#{xi≠yi | i = 0, 1, …, n−1}となる。要素x ∈ Z2nのハミング重みwH : Z2n → Zは非零座標の数として定義される。即ち、wH(x) =#{xi≠0 | i = 0, 1, …, n−1}となる。

0014

Z2についてのk×m行列(k, m ≧ 1)のセットはZ2k×mによって示される。Z2についてのk×k恒等行列はIkによって示される。符号‖はまた、同数の行を備える行列の連結を示すためにも用いられ、例えば、A ∈ Z24×6且つB ∈ Z24×8である場合には、C := (A ‖ B) ∈ Z24×14となる。

0015

(ブロック)長さnのバイナリ・エラー訂正コードCは、Z2nの部分線形空間である。この部分空間の要素は、コードワードと呼ばれる。部分空間の大きさがkである場合には、Cは[n, k]コードと呼ばれる。斯様なコードは、前記行がCのための基底を形成する生成行列G ∈ Z2k×nによって表され得る。即ち、C = {mG | ∈ Z2k}となる。コードの最小距離dは、全ての任意の2つの別個のコードワードの間の距離の中で最小のものとして定義され、即ち、d = min{dH(x, y) | x, y ∈ C且つx≠y}となる。最小ハミング距離dを備える[n, k]コードは[n, k, d]コードとも呼ばれる。
【数3】
であることに注意されたい。このことは、線形コードの最小ハミング距離が全非零コードワード中の最小ハミング重みと等しいことを意味する。

0016

【ブロック暗号の構造】
典型的なブロック暗号は、Feistel型暗号であり、(DESのように)16ラウンドから成る。ブロック長は64ビットと等しく、鍵長は128ビットと等しい。鍵K ∈ Z2128のもとでの暗号文C ∈ Z264への平文X ∈ Z264の電子コードブック(ECB)モードにおける暗号化はC = E(K, X)によって示される。

0017

ラウンド関数は、fによって示され、Z240 x Z232からZ232へのマッピングである。このラウンド関数は、本発明の線形変換を組み入れており、以下により詳細に記載する。ラウンド関数の第1入力引数(first input argument)はラウンド鍵Ki ∈ Z240である(ここで、iはラウンド数を示す。i = 1, 2, …, 16)。これらのラウンド鍵は、所謂鍵スケジュール処理アルゴリズムで128ビット鍵Kから算出される。任意の適切な鍵スケジュール処理アルゴリズムが用いられても良く、詳細には記載しない。第2入力引数は、ラウンドiの後の中間結果の右半分である。この中間結果は、X =: (X0(R) ‖ X0(L))を伴うXi ∈ Z264(i=0, 1, …, 16)によって示される。

0018

この表記法では、暗号文C ∈ Z264の算出は図2に示されているような以下のステップから成る。 1. i = 1, 2, …, 15に対して、
【数4】
を算出し、Xi(L) = Xi−1(R)と設定する。
【数5】
を算出し、X16(R) = X15(R)と設定する。暗号文はC := (X16(L) ‖ X16(R))と定義される。

0019

図2Aは最初の15ラウンド(i = 1, 2, …, 15)に対して用いられる暗号構造を示している。図2Bは最後の16番目のラウンドを示している。図2Aの前のラウンドと比べての図2Bにおける変則のスワップ(irregular swap)に注意されたい。これは、通常Feistel型構造において行われる。なぜなら、この場合には、復号アルゴリズム(即ち、X = E−1(K, C)の算出)が(逆順のラウンド鍵を備える)暗号化アルゴリズムと同じであるからである。それは暗号的意味(cryptographic sense)においてはなんの意味も持たない。

0020

【ラウンド関数】
図3は、ラウンド関数fの好ましい実施例の全体的なブロック図を示している。まず、ステップ310において例えば32ビットのラウンド鍵の一部がデータビットに加算される。次に、ステップ320においては、S−boxが、好ましくは差分解読法及び線形解読法に対する最適の(ローカルな)耐性(resistance)を提供する非線形の置換え(non−linear substitution)を行う。その上、好ましくは、所定の最大確率(maximum probability)を備えるトリビアルではない(non−trivial)(ローカルな)特性が、以下により詳細に記載されているように(ラウンド)鍵に依存して作られる。最後に、ステップ330においては、多数のラウンドにわたって高い拡散を供給するために線形変換が用いられる。エラー訂正コードから斯様な線形変換を生成する方法を以下により詳細に記載する。

0021

Feistel型構造は、ラウンド関数の全射性(surjectivity)に制限を設けない。しかしながら、好ましくは、ラウンド関数は、固定(ラウンド)鍵に対するあらゆる選択について全単射である。このことは、ラウンド関数の非一様性に基づいて攻撃を防ぐ。

0022

図4は、S−boxを組み入れる好ましい構成のより詳細を提供している。この典型的なシステムにおいて、ラウンド関数fはZ240 x Z232からZ232へのマッピングである。第1入力引数はラウンド鍵Ki ∈ Z240であり、第2入力引数は中間結果Xi−1の右半分である。出力は、f(Ki, Xi−1(R)) ∈ Z232によって示される。この図においては、Ki(1) ∈ Z232及びKi(2) ∈ Z28がKi =: (Ki(1) ‖Ki(2))として定義される。ステップ310においては、鍵加算が行われ、ステップ320の鍵依存置換ボックス(S−box)層が続く。この例においては、S−box層が、各々がデータブロックの1/8に作用する8個のより小さなS−box(S0, S1, S2, …, S7)から成る。S−box変換はZ28 x Z232からZ232へのマッピングであり、ラウンドiにおける第1入力引数はラウンド鍵Ki(2)であり、第2入力引数は鍵加算の結果、即ち
【数6】
である。S−box変換の32ビット出力は
【数7】
によって示される。以下にこのマッピングについて記載する。最後に、ステップ330においては、Z232からZ232への線形変換が適用される。入力は
【数8】
であり、その出力は
【数9】
によって示される。この表記法では、関数fが
【数10】
によって与えられる。

0023

【S−box】
原則的には、ブロック暗号においては任意の適切なS−box層が用いられ得る。本明細書に記載されている好ましい実施例においては、各S−boxが4ビットサブブロックに作用する。他のサイズのサブブロックも用いられ得ることを認識されたい。好ましくは、各S−boxに対して少なくとも2つの所定の並び替えのセットが用いられ、ここでは、S−boxを用いる前に毎度これらの並び替えのうちの1つが(疑似)ランダム方式で選択される。好ましくは、ラウンド鍵がこの選択のために用いられる。好ましい実施例においては、各S−boxが2つの並び替えと関連付けられており、ここでは、ラウンド鍵のうちのある所定のビットが、両並び替えのうちのどちらを用いるかを選択するために用いられる。4ビットサブブロックに作用するS−boxなどの相対的に小さなS−boxの使用は、通常、並列のS−boxの列を必要とし、各々が少なくとも2つの非線形の並び替えのセットの各々と関連付けられている。

0024

図4は、32ビットブロックに作用し、且つ4ビットS−boxを用いる、結果として8個のS−boxが並列に用いられることとなるブロック暗号の好ましい実施例を図示しており、前記S−boxの各々は2つの並び替えから成る。この実施例に対しては、以下の表記法を用いる。S−box変換の第1入力引数Ki(2)の中のビットは、kj(i)(j = 0, 1, …,7) によって示されるとする。即ち、Ki(2) =: (k0(i), k1(i), …, k7(i))となる。ベクトルNj(i) ∈ Z24 (j = 0, 1, …,7)は
【数11】
として定義される。S−boxマッピングは、8個のマッピングSj : Z2 x Z24 → Z24(j = 0, 1, …,7) の連結から成る。第1入力引数は、Sjのための2つの並び替えのうちどちらを用いるのかを選択する鍵ビットkj(i)である。第2入力引数は、Sjのための選択された4ビット並び替えに対する入力であるNj(i)である。この並び替えの対応4ビット出力は、S−boxの出力でもあり、Sj(kj(i), Nj(i))によって示される。この表記法では、関数Sが、
【数12】
によって与えられる。任意の適切なS−box層が用いられ得る。好ましくは、特許出願の欧州特許出願番号EP00202326.5(出願人整理番号:PHNL000365)によるS−boxが用いられる。

0025

【線形変換行列】
S−boxの置換作用の後には、線形変換Lが行われる。32ビットサブブロックを備える好ましい実施例においては、L : Z232 → Z232となる。上記の好ましいS−box構成を用いる場合、この線形変換に対する入力は、ベクトル
【数13】
である。このベクトルの座標は、yji(j = 0, 1, …,31) によって示されるであろう。即ち、
【数14】
となる。この場合には、マッピングLをベクトル行列乗算として表現することができ、この行列は、A ∈ Z232×32 :
【数15】
によって示される。

0026

【線形変換行列の構成】
L(x) = xAにより定義される線形変換Lは以下の基準を満たすように構成される。 1. Z2にわたっての線形性。 2.可逆性(invertibility)、即ち、行列AがZ2にわたって非特異である。 3. 高い拡散特性。

0027

関数Lの構成は、バイナリ線形エラー訂正コードに基づく。マッピングLは、バイナリ・エラー訂正コードのための生成行列G = (Ik ‖ A) ∈ Z2k×2kと関連付けられる。x ∈ Z2kを伴う全てのコードワード(x ‖ xA) ∈ Z22kについて、左半分のxがLに対する入力に対応する一方で、右半分のxAが出力に対応することに注意されたい。設計基準(i)は、全てのバイナリ・エラー訂正コードに対して満足される一方で、(ii)は、AがZ2にわたって非特異である場合に限り満足されることに注意されたい。基準(iii)は、コードワードの最小ハミング重みによって表され得る、即ち、この最小距離が大きいほど、拡散特性は良くなることにも注意されたい。

0028

32ビットブロック(即ち、k = 32且つA ∈ Z232×32)についてAの構成を以下に説明する、Aの構成は、12と等しい最小ハミング距離を備える[64, 32]コードの構成のための始点(starting point)としてXBCH(binary extended Bose−Chaudhuri−Hocquenghem)コードを用いる。斯様なコードが最適であること、即ち、任意のバイナリ[64, 32]コードが12以下の最小距離を持つことはよく知られている。前記コードが線形であることから、このことは、任意の非零コードワードの最小ハミング重みが少なくとも12であることを意味する。このことは、tビット(t > 0)の入力における(小さな)変化は出力における少なくともmax{0, 12−t}ビットの変化を意味するという点で、マッピングLの拡散特性がビットレベルにおいて最適であることを意味することに注意されたい。

0029

行列Aを含むバイナリ[64, 32, 12]コードのための生成行列は、図5に図示されているように、以下のように構成される。
(i)  ステップ510においては、バイナリ線形エラー訂正コードに対応する標準形の生成行列G’’ (即ち、B ∈ Z232×28を備えるG’’ = (I32 ‖ B))が取得される。斯様な生成行列G’’は、好ましくは、BCH(Bose−Chaudhuri−Hocquenghem)コードから始まり、以下のように構成される。
(a)ステップ512においては、生成行列G ∈ Z236×63が、生成多項式(generator polynomial)g(x) := x27 + x22 + x21 + x19 + x18 + x17 + x15 + x8 + x4 + x + 1を備えるバイナリ[63, 36, 11]BCHコードに対して構成され、ここで、Gの行j(j = 0, 1, …, 35)は多項式xjg(x)に対応する。より正確には、gi ∈ Z2を備えるg(x) =: Σi = 0, 1, …, 27gixiである場合に、行列の最初の行は(g0, g1, g2, …, g27, 0, 0, …, 0) ∈ Z263によって与えられる。生成行列の行j(j = 0, 1, …, 35)は、j位置にわたってのこの最初の行の右への循環シフト(cyclic shift)により与えられる。
(b)ステップ514においては、このコードが、Gの最後の4つの行及び列を削除することにより[59, 32, 11]コードへ縮小される。
(c)ステップ518においては、この縮小されたコードが、各コードワードにパリティチェック符号を加えることにより[60, 32, 12]コードへ拡大される。パリティチェックを加えることによる1つの列の付加は最小距離の増大をもたらすことに注意されたい。この[60, 32, 12]コードに対する32×60生成行列はG’によって示される。
(d)ステップ520においては、標準形の生成行列G’’、即ち、B ∈ Z232×28を備えるG’’ = (I32 ‖ B)を得るために、G’においてガウス消去が行われる。これは、縮小された[60, 32, 12]XBCHコードに対する生成行列であることに注意されたい。
(ii)  結果として生じる行列C ∈ Z232×32がZ2にわたって非特異であるようにBを4つの列でBを拡大する。好ましくは、この4つの列が疑似ランダムに選択される。
(a)各々が32個の(疑似)ランダムに選択されたバイナリの要素(binary element)を備える4つの列を作成する。
(b)新しい前記4つの列でBを拡大することによりテスト行列を作成する(本質的には、新たに加えられる列の列位置は重要ではない)。
(c)テスト行列が可逆であるかどうかをチェックする。このテストに対しては、任意の適切な方法、例えばガウス消去に基づく方法が用いられ得る。
(d)そうである場合には、プロセスを停止し(行列が見つけられており)、そうでない場合には、少なくとも1つの新しい列を生成することにより再始動する。

0030

前記4つの列の要素はまた、ランダム作成プロセスを用いる代わりに任意の他の適切な方式においても生成され得ることを認識されたい。

0031

マルチビットのS−boxを備えるラウンド関数の構成のため、このマルチビットレベルにおける良好な拡散特性も望ましい。4ビットS−boxに対しては、このことが以下のように表され得る(他のビット数の変形例は十分に当業者のスキルの範囲内にある)。コードワードc ∈ Z232の4ビットベクトルni(i = 0, 1, …, 7)がc =: (n0 ‖ n1 ‖…‖ n7)として定義される場合には、cのニブル重み(nibble weight)がNW(c) :=#{i ‖ ni≠(0, 0, 0, 0), i = 0, 1, …, 7}として定義される。ニブルレベルにおける拡散特性は、全ての非零コードワードにわたっての最小ニブル重みによって表され得る。即ち、この最小重みが大きいほど、ニブルレベルにおける拡散特性は良くなる。マルチビットレベルにおける(この例においてはニブルレベルにおける)高い拡散を達成するために、ステップ530においては、生成行列(I ‖ P1CP2)を備える[60, 32, 12]コードにおける全てのコードワードが高いニブル重みを持つように2つの置換行列P1, P2 ∈ Z232×32が選択される。最終的に求められる行列A := P1CP2は線形変換のために用いられる。好ましい実施例においては、置換行列P1及びP2が(疑似)ランダムに生成される。(I ‖ A)によって生成されるコードの最小ニブル重みは7と等しいことが確認され得る。

0032

以下の表においてこのように生成される線形変換行列Aの行を示す(a0は第1の行であり、a1は第2の行であり、…、a31は最後の行である)。ベクトル行列積(vector−matrix product)は、yk(i) = 1(k = 0, 1, …, 31)である行akのXORに対応することに注意されたい。

0033

【表1】

0034

【MDSコードとの比較】
対象鍵暗号におけるMDSコードに基づく線形変換の使用は、S. Vaudenay, “On the Need for Multi−Permutations: Cryptanalysis of MD4 and SAFER”, Fast Software Encryption (2nd), LNCS 1008, Springer, 1995, pp. 286−297から既知である。以下の表は、本発明によるXBCHベースの行列において用いられる構成のニブル重み分布をMDSコードの(ニブル)重み分布と比較している。エントリ(entry)は、所与のニブル重みを備える非零コードワードの数を表す。

発明を実施するための最良の形態

0035

【表2】

図面の簡単な説明

0036

この表から分るように、これら2つの構成のニブル重み分布は非常に類似している。XBCH構成の最小ニブル重みは、この基準に対して最適であることを示され得るMDS構成の最小重みより2つだけ少ない。しかしながら、MDS構成は、ブロック暗号の解読において活用され得る関連線形変換のF16(のサブフィールド)にわたっての線形性などの付加的な数学的構造を含むという不利な点を持つ。例えば、S−box(及び結果としての完成したブロック暗号(complete block cipher))は、F16 → F16からのマッピングによって記述され得る。更に、本明細書に記載の構成は、ビットレベルにおける最適な拡散を保証する。

【図1】
暗号システムのブロック図を示す。
【図2A】
線形変換を組み入れている暗号のあるラウンドを示す。
【図2B】
線形変換を取り入れている暗号のあるラウンドを示す。
図3
ラウンド関数のステップを図示する。
図4
S−box構成の好ましい構成を示す。
図5
線形変換行列を生成するステップを示す。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ