説明

暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラム

【課題】 解析困難性を高めた、安全性の高い暗号処理装置および方法を実現する。
【解決手段】 非線形変換部および線形変換部を有するSPN型のF関数を、複数ラウンド繰り返し実行するFeistel型共通鍵ブロック暗号において、各ラウンドに対応するF関数の線形変換処理を比較的緩やかな制限条件を満足する行列を適用して実行する。本構成により差分攻撃や線形攻撃に対する耐性が向上する。また、制限が比較的緩やかであのので利用できる行列候補が増加し、アクティブS−box数を大きくできる。すなわち、暗号強度指標のひとつであるアクティブSボックスの最小数を大きくすることが可能となり、攻撃に対する耐性が向上し安全性の高い暗号処理が実現される。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムに関する。さらに詳細には、暗号解析処理、攻撃処理として知られる線形解析、差分解析に対する耐性を向上させた暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【0002】
昨今、ネットワーク通信、電子商取引の発展に伴い、通信におけるセキュリティ確保が重要な問題となっている。セキュリティ確保の1つの方法が暗号技術であり、現在、様々な暗号化手法を用いた通信が実際に行なわれている。
【0003】
例えばICカード等の小型の装置中に暗号処理モジュールを埋め込み、ICカードと、データ読み取り書き込み装置としてのリーダライタとの間でデータ送受信を行ない、認証処理、あるいは送受信データの暗号化、復号を行なうシステムが実用化されている。
【0004】
暗号処理アルゴリズムには様々なものがあるが、大きく分類すると、暗号化鍵と復号鍵を異なる鍵、例えば公開鍵と秘密鍵として設定する公開鍵暗号方式と、暗号化鍵と復号鍵を共通の鍵として設定する共通鍵暗号方式とに分類される。
【0005】
共通鍵暗号方式にも様々なアルゴリズムがあるが、その1つに共通鍵をベースとして複数の鍵を生成して、生成した複数の鍵を用いてブロック単位(64ビット,128ビットなど)のデータ変換処理を繰り返し実行する方式がある。このような鍵生成方式とデータ変換処理を適用したアルゴリズムの代表的なものが共通鍵ブロック暗号方式である。
【0006】
代表的な共通鍵ブロック暗号のアルゴリズムとしては、例えば米国標準暗号としてのDES(Data Encryption Standard)アルゴリズムがあり、様々な分野において広く用いられている。
【0007】
DESに代表される共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を実行するラウンド関数部と、ラウンド関数(F関数)部の各ラウンドで適用する鍵を生成する鍵スケジュール部とに分けることができる。ラウンド関数部の各ラウンドで適用するラウンド鍵(副鍵)は、1つのマスター鍵(主鍵)に基づいて、鍵スケジュール部に入力されて生成され、各ラウンド関数部で適用される。
【0008】
しかし、このような共通鍵暗号処理においては、暗号解析による鍵の漏洩が問題となっている。暗号解析または攻撃手法の代表的な手法として、ある差分を持つ入力データ(平文)とその出力データ(暗号文)を多数解析することにより各ラウンド関数における適用鍵を解析する差分解析(差分解読法または差分攻撃とも呼ばれる)や、平文と対応暗号文に基づく解析を行う線形解析(線形解読法または線形攻撃とも呼ばれる)が知られている。
【0009】
暗号解析による鍵の解析が容易であるということは、その暗号処理の安全性が低いということになる。従来のDESアルゴリズムにおいては、ラウンド関数(F関数)部の線形変換部において適用する処理(変換行列)が、各段のラウンドにおいて等しいものであったため解析が行いやすく、結果として鍵の解析の容易性を招いているという問題がある。
【発明の開示】
【発明が解決しようとする課題】
【0010】
本発明は、上記問題点に鑑みてなされたものであり、線形解析や差分解析に対する耐性の高い共通鍵ブロック暗号アルゴリズムを実現する暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【0011】
本発明の第1の側面は、
複数ビットの入出力を持つ複数の非線形変換層を並列に構成した非線形変換部と、
線形変換を施す線形変換層で構成した線形変換部とで構成されるFeistel型暗号処理を備える暗号処理装置において、
前記線形変換部は、前記線形変換に適応する行列の制約条件に基づいて処理を施すことを特徴とする暗号処理装置にある。
【0012】
さらに、本発明の暗号処理装置の一実施態様において、前記線形変換に適応する行列の制約条件は、r段各々に対応するF関数の線形変換部の満足する行列Miを適用した構成、すなわち、 n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hwn(α)+hwn(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、hwn(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BD1=min{B(Mi)|1≦i≦r},
BD2=min{B(Mi|Mi+2)|1≦i≦r−2},
ただし、A|Bは行列A,Bの連結により得られる行列、
とした場合において、
BD1,BD2のすべてが3以上になるような行列Miを適用した構成であることを特徴とする。
【0013】
さらに、本発明の第2の側面は、
暗号処理装置であり、
非線形変換部および線形変換部を有するSPN型のF関数を持つr段からなるFeistel型共通鍵ブロック暗号処理構成を有し、
前記r段各々に対応するF関数の線形変換部は下記条件を満足する行列Mを適用した構成、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
BD=min{B(M|Mi+2|Mi+4)|1≦i≦r−4},
ただし、A|Bは行列A,Bの連結により得られる行列、
とした場合において、
BD,BD,BDのすべてが3以上になるような行列Mを適用した構成であることを特徴とする暗号処理装置にある。
【0014】
さらに、本発明の第3の側面は、
暗号処理装置であり、
非線形変換部および線形変換部を有するSPN型のF関数を持つr段からなるFeistel型共通鍵ブロック暗号処理構成を有し、
前記r段各々に対応するF関数の線形変換部は下記条件を満足する行列Mを適用した構成、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BL=min{B(−1−1i+2)|1≦i≦r−2}
ただし、Mは行列の転置、
とした場合において、
BLが3以上になるような行列Mを適用した構成であることを特徴とする暗号処理装置にある。
【0015】
さらに、本発明の第4の側面は、
Feistel型共通鍵ブロック暗号処理を実行する暗号処理方法であり、
非線形変換部および線形変換部を有するSPN型のF関数をr段、繰り返し実行するステップを有し、
前記r段各々に対応するF関数の線形変換処理は下記条件を満足する行列Mを適用した線形変換処理、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
BD=min{B(M|Mi+2|Mi+4)|1≦i≦r−4},
ただし、A|Bは行列A,Bの連結により得られる行列、
とした場合において、
BD,BD,BDのすべてが3以上になるような行列Mを適用した線形変換処理によって実行することを特徴とする暗号処理方法にある。
【0016】
さらに、本発明の第5の側面は、
Feistel型共通鍵ブロック暗号処理を実行する暗号処理方法であり、
非線形変換部および線形変換部を有するSPN型のF関数をr段、繰り返し実行するステップを有し、
前記r段各々に対応するF関数の線形変換部は下記条件を満足する行列Mを適用した線形変換処理、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BL=min{B(−1−1i+2)|1≦i≦r−2}
ただし、Mは行列の転置、
とした場合において、
BLが3以上になるような行列Mを適用した線形変換処理によって実行することを特徴とする暗号処理方法にある。
【0017】
さらに、本発明の第6の側面は、
Feistel型共通鍵ブロック暗号処理をコンピュータ上において実行するコンピュータ・プログラムであり、
非線形変換部および線形変換部を有するSPN型のF関数をr段、繰り返し実行するステップを有し、
前記r段各々に対応するF関数の線形変換処理は下記条件を満足する行列Mを適用した線形変換処理、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
BD=min{B(M|Mi+2|Mi+4)|1≦i≦r−4},
ただし、A|Bは行列A,Bの連結により得られる行列、
とした場合において、
BD,BD,BDのすべてが3以上になるような行列Mを適用した線形変換処理によって実行することを特徴とするコンピュータ・プログラムにある。
【0018】
さらに、本発明の第7の側面は、
Feistel型共通鍵ブロック暗号処理をコンピュータ上において実行するコンピュータ・プログラムであり、
非線形変換部および線形変換部を有するSPN型のF関数をr段、繰り返し実行するステップを有し、
前記r段各々に対応するF関数の線形変換部は下記条件を満足する行列Mを適用した線形変換処理、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BL=min{B(−1−1i+2)|1≦i≦r−2}
ただし、Mは行列の転置、
とした場合において、
BLが3以上になるような行列Mを適用した線形変換処理によって実行することを特徴とするコンピュータ・プログラムにある。
【0019】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、CDやFD、MOなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【0020】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【0021】
本発明の構成によれば、非線形変換部および線形変換部を有するSPN型のF関数を、複数ラウンド繰り返し実行するFeistel型共通鍵ブロック暗号処理において、複数ラウンド各々に対応するF関数の線形変換処理を、比較的緩やかな制限によって特定される行列を適用して実行する構成により、共通鍵ブロック暗号における差分攻撃や線形攻撃に対する耐性が向上する。また、制限が比較的緩やかであり、利用できる行列の候補が増加するとともに、アクティブS−box数を十分大きく確保することが可能となる。すなわち、共通鍵ブロック暗号における攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブSボックスの最小数を大きくすることが可能となり、線形攻撃や、差分攻撃に対して耐性が向上し、より安全性の高い暗号処理が実現される。
【発明を実施するための最良の形態】
【0022】
以下、本発明の暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムの詳細について説明する。なお、説明は、以下の項目順に行う。
1.共通鍵ブロック暗号アルゴリズムにおける差分解析処理
2.共通鍵ブロック暗号アルゴリズムにおける線形解析処理
3.耐性を向上させた暗号処理アルゴリズム構成例
(3−a)差分攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例
(3−b)線形攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例
(3−c)差分攻撃および線形攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例
4.本発明に係る暗号処理アルゴリズム
(4a)構成例1
(4a.1)構成例1における差分攻撃に対する耐性の向上
(4a.2)構成例1における線形攻撃に対する耐性の向上
(4b)構成例1
(4b.1)構成例2における差分攻撃に対する耐性の向上
(4b.2)構成例2における線形攻撃に対する耐性の向上
【0023】
[1.共通鍵ブロック暗号アルゴリズムにおける差分解析処理]
まず、DES(Data Encryption Standard)暗号処理に代表される共通鍵ブロック暗号アルゴリズムにおける差分解析処理の概要について、一般化した共通鍵ブロック暗号モデルを用いて説明する。
【0024】
共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を実行するラウンド関数部と、ラウンド関数部の各ラウンドで適用する鍵を生成する鍵スケジュール部とに分けることができる。ラウンド関数部の各ラウンドで適用する鍵(副鍵)は、1つのマスター鍵(主鍵)に基づいて、鍵スケジュール部に入力されて生成され、各ラウンド関数部で適用される。この共通鍵暗号方式の代表的な方式に米国連邦標準暗号方式としてのDES(Data Encryption Standard)がある。
【0025】
Feistel構造と呼ばれる代表的な共通鍵ブロック暗号の構造について、図1を参照して説明する。
【0026】
Feistel構造は、変換関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。平文の長さを2mnビットとする。ただし、m,nは共に整数である。初めに、2mnビットの平文を、mnビットの2つの入力データP(Plain-Left)101,P(Plain-Right)102に分割し、これを入力値とする。
【0027】
Feistel構造はラウンド関数とよばれる基本構造の繰り返しで表現され、各ラウンドに含まれるデータ変換関数はF関数120と呼ばれる。図1の構成では、F関数(ラウンド関数)120がr段繰り返された構成例を示している。
【0028】
例えば第1番目のラウンドでは、mnビットの入力データXと、鍵生成部(図示せず)から入力されるmnビットのラウンド鍵K103がF関数120に入力され、F関数120におけるデータ変換処理の後にmnビットのデータYを出力する。出力はもう片方の前段からの入力データ(第1段の場合は入力データP)と排他的論理和部104において、排他的論理和演算がなされ、mnビットの演算結果が次のラウンド関数へと出力される。この処理、すなわちF関数を定められたラウンド数(r)だけ繰り返し適用して暗号化処理が完了し、暗号文の分割データC(Cipher-Left)、C(Cipher-Right)が出力される。以上の構成より、Feistel構造の復号処理はラウンド鍵を挿入する順序を逆にするだけでよく、逆関数を構成する必要がないことが導かれる。
【0029】
各ラウンドの関数として設定されるF関数120の構成について、図2を参照して説明する。図2(a)は、1つのラウンドにおけるF関数120に対する入力および出力を示す図であり、図2(b)は、F関数120の構成の詳細を示す図である。F関数120は、図2(b)に示すように、非線形変換層と線形変換層を接続したいわゆるSPN型の構成を有する。
【0030】
SPN型のF関数120は、図2(b)に示すように、非線形変換処理を実行する複数のSボックス(S−box)121を有する。ラウンド関数部の前段からのmnビットの入力値Xは、鍵スケジュール部から入力されるラウンド鍵Kと排他的論理和が実行され、その出力がnビットずつ非線形変換処理を実行する複数(m個)のSボックス121に入力される。各Sボックスでは、例えば変換テーブルを適用した非線形変換処理が実行される。
【0031】
Sボックス121からの出力データであるmnビットの出力値Zは、線形変換処理を実行する線形変換部122に入力されて、例えばビット位置の入れ替え処理などの線形変換処理が実行され、mnビットの出力値Yを出力する。この出力値Yが前段からの入力データと排他的論理和され、次のラウンドのF関数の入力値とされる。
【0032】
図2に示すF関数120は、入出力ビット長がm×n(m,n:整数)ビットであり、非線形変換層はnビットの入出力を持つ非線形変換層としてのSボックス121は、m個並列にならんだ構成を有し、線形変換層としての線形変換部122はn次の既約多項式で定義される2の拡大体GF(2)上の元を要素として持つm次の正方行列に基づく線形変換処理を実行する。
【0033】
線形変換部122における線形変換処理に適用する正方行列の例を図3に示す。図3に示す正方行列125は、n=8,m=8の場合の例である。非線形変換部(Sボックス121)から出力されたm個のnビットデータZ[1],Z[2],...,Z[m]に対してあらかじめ定められた正方行列125を適用した演算により線形変換が施され、F関数(ラウンド関数)出力としての、Y[1],Y[2],...,Y[m]が決定される。ただし、このとき各データの行列の要素に対する線形演算はあらかじめ定められた2の拡大体GF(2)上で行われる。
【0034】
これまでのFeistel型暗号では、すべての段のF関数に同じ線形変換層を用いているため、差分の伝播時に同時に複数の差分がキャンセルしてしまうという性質が存在した。背景技術の欄において説明したように、暗号解析手法の代表的な手法として、ある差分を持つ入力データ(平文)とその出力データ(暗号文)を多数解析することにより各ラウンド関数における適用鍵を解析する差分解析(あるいは差分解読法)が知られており、従来のDES暗号アルゴリズム等の共通鍵ブロック暗号においては、F関数120部の線形変換部122において適用する処理(変換行列)を、各段のラウンドにおいて等しいものに設定しているため、差分解析が行いやすく、結果として鍵の解析の容易性を招いている。
【0035】
差分の伝播時に、同時に複数の差分がキャンセルする例について、図4を参照して説明する。なお、本明細書においては、差分を表す場合にはΔ(デルタ)記号をつけて表す。
【0036】
図4はm=8,n=8の128bitブロック暗号における3段の同時差分キャンセルの様子を説明する図である。ただし、図中では64bitのデータをバイト単位で区切ってベクトルとして表現し、それぞれの要素を16進数で表記するものとする。
【0037】
3段構成を持つF関数での同時差分キャンセルは、例えば以下のデータ状態1〜4の設定メカニズムに基づいて発生する。以下に説明するメカニズムの発生するデータ状態は、多数の差分入力データを設定することで発生させることができるデータ状態であり、いわゆる差分解析における鍵(ラウンド鍵)の解析において発生し得る。
【0038】
(状態1)
iラウンドへの入力差分の左半分は、すべてゼロである入力差分(ΔXi−1=(00,00,00,00,00,00,00,00))であり、右半分の入力差分がただひとつのS−boxへの入力を除いてゼロである入力差分(ΔXi=(34,00,00,00,00,00,00,00))であるとする。このデータ状態は、多数の差分入力データを設定することで、iラウンドにおいて、このようなデータ状態を得ることができるということである。
【0039】
なお、ΔXi=(34,00,00,00,00,00,00,00)の8つの各要素は、F関数中に構成されるm個(m=8)のSボックス各々に対する入力差分に対応する。差分(34)が第1Sボックス(図4中の(S1))に入力され、(00)が、第2〜8Sボックスに対する入力差分である。
【0040】
なおゼロ(00)の入力差分を持つSボックスの出力差分はゼロ(00)であり、差分データに関する限り、ゼロ(00)の入力差分を持つSボックスは、何の作用も行なっていないものであり、アクティブでないすなわち非アクティブSボックスと呼ばれる。一方、非ゼロの入力差分(図4の例では差分:34)を持つSボックスは、非ゼロの入力差分に対応した非線形変換結果を出力差分として発生させるので、アクティブSボックス(Active S−box)と呼ばれる。
【0041】
図4の例では、非ゼロの入力差分(34)を入力する1つのアクティブSボックス(S1)の出力差分(b7)を発生させており、その他の非アクティブSボックスS2〜S8はゼロの入力差分(00)に基づいて出力差分(00)を発生させ、線形変換部の差分入力としている。
【0042】
(状態2)
iラウンドへの非ゼロの入力差分(図4の例では差分:34)を持つSボックス(以下、アクティブSボックス(Active S−box)と呼ぶ)からの出力差分は線形変換層で拡散されたのちF関数から出力(出力値=ΔYi)され、そのまま次のラウンドへの入力差分ΔXi+1となる。
【0043】
図4の例における線形変換は、各ラウンドのF関数において共通する例えば図5に示すある特定の正方行列125による線形変換が実行されiラウンドのF関数出力差分としてのΔYi=(98,c4,b4,d3,ac,72,0f,32)を出力する。図5に示す線形変換構成から理解されるように、出力差分ΔYi=(98,c4,b4,d3,ac,72,0f,32)は、1つのアクティブSボックス(S1)からの出力要素Z[1]=b7にのみ依存した値として決定される。
【0044】
このiラウンドのF関数出力差分としてのΔYi=(98,c4,b4,d3,ac,72,0f,32)は、図4に示す排他的論理和部131において、すべてゼロである入力差分(ΔXi−1=(00,00,00,00,00,00,00,00)と排他的論理和(XOR)演算が実行され、演算結果が、次のラウンド(i+1)への入力差分ΔXi+1となる。
【0045】
iラウンドのF関数出力差分としてのΔYi=(98,c4,b4,d3,ac,72,0f,32)と、すべてゼロである入力差分ΔXi−1=(00,00,00,00,00,00,00,00)との排他的論理和(XOR)結果は、ΔYiであるので、次のラウンド(i+1)への入力差分ΔXi+1=ΔYi=(98,c4,b4,d3,ac,72,0f,32)となる。
【0046】
(状態3)
i+1ラウンドのF関数からの出力差分ΔYi+1が、iラウンドでのActive S−boxの位置にのみ非ゼロ値をもつ。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。
【0047】
すなわち、ΔYi+1=(ad,00,00,00,00,00,00,00)であり、iラウンドと同様、非ゼロの差分値(図4の例では差分:34)を持つS−boxの位置(第1Sボックス(S1))にのみ非ゼロ値をもつ。なお、明らかにad≠00である。
【0048】
(状態4)
i+2ラウンドのアクティブSボックス(Active S−box)(S1)の出力差分がiラウンドでのアクティブSボックス(Active S−box)(S1)の出力差分と一致した場合、すなわち、図4に示すようにi+2ラウンドのアクティブSボックス((S1)の出力差分がb7となり、iラウンドでのアクティブSボックス(S1)の出力差分(b7)と一致する。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。
【0049】
このデータ状態が発生すると、i+2ラウンドのF関数の出力差分ΔYi+2=(98,c4,b4,d3,ac,72,0f,32)が、2つ前のラウンドであるiラウンドのF関数の出力差分ΔYi=(98,c4,b4,d3,ac,72,0f,32)と一致することになる。
【0050】
この結果、排他的論理和部133では、
ΔXi+1=ΔYi=(98,c4,b4,d3,ac,72,0f,32)と、
ΔYi+2=(98,c4,b4,d3,ac,72,0f,32)と、
の同一の値同士の排他的論理和演算が実行されることになり、排他的論理和演算結果としてオール0の値を出力する。
【0051】
その結果、次の段(ラウンドi+3)への出力差分の前段(i+2ラウンド)からの左の入力差分ΔXi+3=(00,00,00,00,00,00,00,00)となる。
【0052】
このラウンドi+3への左入力ΔXi+3=(00,00,00,00,00,00,00,00)は、ラウンドiへの左入力ΔXi−1=(00,00,00,00,00,00,00,00)と同様オールゼロであり、ラウンドi+3以降のラウンドにおいても、ラウンドi〜i+2と同様の処理が繰り返される可能性がある。
【0053】
この結果、ラウンド数の伸びに対してアクティブSボックスの数が増大せず、差分攻撃に対する強度がそれほど伸びないという問題を発生させる。
【0054】
共通鍵ブロック暗号において、差分攻撃に対する強度指標のひとつとして、暗号化関数全体でのアクティブSボックスの最小数が知られている。アクティブSボックス数の最小数が大きいほど差分攻撃に対する耐性が高いと判断される。
【0055】
前述したように、差分解析(差分攻撃)においては、ある差分を持つ入力データ(平文)とその出力データ(暗号文)を多数設定してこの対応を解析することにより各ラウンド関数における適用鍵を解析する手法であり、この差分解析において、アクティブSボックスの数を少なくできれば、解析が容易となり、解析プロセス数を削減できる。
【0056】
上述の図4を参照した例では、第1のSボックス(S1)のみがアクティブSボックスであるパターンの発生状態を提示したが、その他のSボックス(S2〜S8)についても、差分解析の入力データの設定によって、各SボックスのみをアクティブSボックスとした設定が可能であり、このような差分解析プロセスを実行することにより、各Sボックスの非線形変換処理の解析、さらにF関数に対して入力されるラウンド鍵の解析が可能となる。
【0057】
このような差分解析に対する耐性を向上させるためには、アクティブSボックスの数が常に多い状態を維持すること、すなわち、アクティブSボックスの最小数が多いことが必要である。
【0058】
図4を参照して説明した例において、右から左へ入力を行なうF関数、すなわち、第iラウンドと第i+2ラウンドのみをアクティブSボックス算出処理対象ラウンドとしてみた場合、アクティブSボックス数はわずか2であり、左から右へ入力を行なうF関数、すなわち、第i+1ラウンドではアクティブSボックス数が8であるものの、同時差分キャンセルにより第i+3ラウンドでのアクティブSボックス数が0となってしまうため、差分解析による各Sボックスの非線形変換処理の解析処理が容易となる。
【0059】
図4に示す共通鍵ブロック暗号アルゴリズムは、各ラウンドにおける線形変換部において適用する線形変換行列が等しいものであり、この構成に起因して、特に右から左へ入力を行うF関数におけるわずか2つのアクティブSボックスにより同時差分キャンセルの発生可能性を引き起こしている。従って、ラウンド数の伸びに対してアクティブSボックスの最小数が十分に増大せず、差分攻撃に対する強度がそれほど伸びないという問題がある。
【0060】
次に、同様に、同じ線形変換行列をすべての段(ラウンド)のF関数に用いる構成において、5ラウンドにまたがる同時差分キャンセルの発生メカニズムについて、図6を参照して説明する。
【0061】
図6はm=8,n=8の128bitブロック暗号における5段の同時差分キャンセルの様子を説明する図である。ただし、図中では64bitのデータをバイト単位で区切ってベクトルとして表現し、それぞれの要素を16進数で表記するものとする。
【0062】
5段構成を持つF関数での同時差分キャンセルは、例えば以下のデータ状態1〜7の設定メカニズムに基づいて発生する。以下に説明するメカニズムの発生するデータ状態は、多数の差分入力データを設定することで発生させることができるデータ状態であり、いわゆる差分解析における鍵(ラウンド鍵)の解析において発生し得る。
【0063】
(状態1)
iラウンドへの入力差分の左半分は、すべてゼロである入力差分(ΔXi−1=(00,00,00,00,00,00,00,00))であり、右半分の入力差分がただひとつのS−boxへの入力を除いてゼロである入力差分(ΔXi=(34,00,00,00,00,00,00,00))であるとする。このデータ状態は、多数の差分入力データを設定することで、iラウンドにおいて、このようなデータ状態を得ることができるということである。
【0064】
なお、ΔXi=(34,00,00,00,00,00,00,00)の8つの各要素は、F関数中に構成されるm個(m=8)のSボックス各々に対する入力差分に対応する。(34)が第1Sボックス(図6中の(S1))に入力され、(00)が、第2〜8Sボックスに対する入力差分である。
【0065】
なお前述したように、ゼロ(00)の入力差分を持つSボックスの出力差分はゼロ(00)であり、差分データに関する限り、ゼロ(00)の入力差分を持つSボックスは、何の作用も行なっていないものであり、アクティブでないすなわち非アクティブSボックスと呼ばれる。一方、非ゼロの入力差分(図6の例では差分:34)を持つSボックス(S1)のみが、非ゼロの入力差分に対応した非線形変換結果を出力差分として発生させるので、アクティブSボックス(Active S−box)である。
【0066】
図6の例では、非ゼロの入力差分(34)を入力する1つのアクティブSボックス(S1)の出力差分(b7)を発生させており、その他の非アクティブSボックスS2〜S8はゼロの入力差分(00)に基づいて出力差分(00)を発生させ、線形変換部の差分入力としている。
【0067】
(状態2)
iラウンドへの非ゼロの入力差分(図4の例では差分:34)を持つSボックス(以下、アクティブSボックス(Active S−box)と呼ぶ)からの出力差分は線形変換層で拡散されたのちF関数から出力(出力値=ΔYi)され、そのまま次のラウンドへの入力差分ΔXi+1となる。
【0068】
図6の例において、各ラウンドに共通の例えば図5に示すある特定の正方行列125による線形変換が実行されiラウンドのF関数出力差分としてのΔYi=(98,c4,b4,d3,ac,72,0f,32)を出力する。
【0069】
iラウンドのF関数出力差分としてのΔYi=(98,c4,b4,d3,ac,72,0f,32)は、図6に示す排他的論理和部141において、すべてゼロである入力差分(ΔXi−1=(00,00,00,00,00,00,00,00)と排他的論理和(XOR)演算が実行され、演算結果が、次のラウンド(i+1)への入力差分ΔXi+1となる。
【0070】
iラウンドのF関数出力差分としてのΔYi=(98,c4,b4,d3,ac,72,0f,32)と、すべてゼロである入力差分(ΔXi−1=(00,00,00,00,00,00,00,00)との排他的論理和(XOR)結果は、ΔYiであるので、次のラウンド(i+1)への入力差分ΔXi+1=ΔYi=(98,c4,b4,d3,ac,72,0f,32)となる。
【0071】
(状態3)
i+1ラウンドのF関数からの出力差分ΔYi+1が、iラウンドでのActive S−boxの位置にのみ非ゼロ値をもつ。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。
【0072】
すなわち、ΔYi+1=(34,00,00,00,00,00,00,00)であり、iラウンドと同様、非ゼロの差分値(図6の例では差分:34)を持つS−boxの位置(第1Sボックス(S1))にのみ非ゼロ値をもつ。
【0073】
(状態4)
i+2ラウンドのF関数に対する入力は、ΔXi=(34,00,00,00,00,00,00,00)と、ΔYi+1=(34,00,00,00,00,00,00,00)との排他的論理和部142における排他的論理和結果、すなわち、同一データ同士の排他的論理和であり、オールゼロの入力、ΔXi+2=(00,00,00,00,00,00,00,00)となり、その結果、i+2ラウンドのF関数からの出力差分も、オールゼロの出力差分、ΔYi+2=(00,00,00,00,00,00,00,00)となる。
【0074】
(状態5)
i+3ラウンドのF関数に対する入力は、ΔXi+1=(98,c4,b4,d3,ac,72,0f,32)と、オールゼロのi+2ラウンドのF関数出力差分ΔYi+2=(00,00,00,00,00,00,00,00)との排他的論理和部143における排他的論理和結果であり、i+3ラウンドのF関数に対する入力ΔXi+3=ΔXi+1=(98,c4,b4,d3,ac,72,0f,32)となる。
【0075】
(状態6)
i+3ラウンドのF関数出力差分が、ΔYi+3=(43,00,00,00,00,00,00,00)となり、オールゼロのΔXi+2=(00,00,00,00,00,00,00,00)との排他的論理和部144における排他的論理和の結果としてのΔXi+4=ΔYi+3=(43,00,00,00,00,00,00,00)がi+4ラウンドのF関数入力差分となる。
【0076】
(状態7)
i+4ラウンドのアクティブSボックス(Active S−box)(S1)の出力差分がiラウンドでのアクティブSボックス(Active S−box)(S1)の出力差分と一致した場合、すなわち、図6に示すようにi+4ラウンドのアクティブSボックス((S1)の出力差分がb7となり、iラウンドでのアクティブSボックス(S1)の出力差分(b7)と一致する。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。
【0077】
このデータ状態が発生すると、i+4ラウンドのF関数の出力差分ΔYi+4=(98,c4,b4,d3,ac,72,0f,32)が、2つ前のラウンドであるi+2ラウンドの排他的論理和部143の出力差分ΔXi+3=(98,c4,b4,d3,ac,72,0f,32)と一致することになる。
【0078】
この結果、排他的論理和部145では、
ΔXi+3=(98,c4,b4,d3,ac,72,0f,32)と、
ΔYi+4=(98,c4,b4,d3,ac,72,0f,32)と、
の同一の値同士の排他的論理和演算が実行されることになり、排他的論理和演算結果としてオール0の値を出力する。
【0079】
その結果、次の段(ラウンドi+5)への入力差分は、ΔXi+5=(00,00,00,00,00,00,00,00)として設定される。
【0080】
このラウンドi+5への左入力ΔXi+5=(00,00,00,00,00,00,00,00)は、ラウンドiへの左入力ΔXi−1=(00,00,00,00,00,00,00,00)と同様オールゼロであり、ラウンドi+5以降のラウンドにおいても、ラウンドi〜i+4と同様の処理が繰り返される可能性がある。
【0081】
この結果、ラウンド数の伸びに対してアクティブSボックスの数が増大せず、差分攻撃に対する強度がそれほど伸びないという問題を発生させる。
【0082】
前述したように、差分解析(差分攻撃)においては、ある差分を持つ入力データ(平文)とその出力データ(暗号文)を多数設定してこの対応を解析することにより各ラウンド関数における適用鍵を解析する手法であり、この差分解析において、アクティブSボックスの数を少なくできれば、解析が容易となり、解析プロセス数を削減できる。
【0083】
上述の図6を参照した例において、右から左へ入力を行なうF関数、すなわち、第iラウンドと第i+2ラウンド、第i+4ラウンドのみをアクティブSボックス算出処理対象ラウンドとしてみた場合、アクティブSボックス数は、第iラウンド=1、第i+2ラウンド=0、第i+4ラウンド=1の合計わずか2であり、左から右へ入力を行なうF関数、すなわち第i+1ラウンドおよび第i+3ラウンドではアクティブSボックス数が8であるものの、同時差分キャンセルにより第i+5ラウンドでのアクティブSボックス数が0となってしまうため、差分解析による各Sボックスの非線形変換処理の解析、および、F関数に対する入力ラウンド鍵の解析処理が比較的、容易となる。
【0084】
図6を参照した例では、第1のSボックス(S1)のみがアクティブSボックスであるパターンの発生状態を提示したが、その他のSボックス(S2〜S8)についても、差分解析の入力データの設定によって、各SボックスのみをアクティブSボックスとした設定が可能であり、このような差分解析プロセスを実行することにより、各Sボックスの非線形変換処理の解析、さらにF関数に対して入力されるラウンド鍵の解析が可能となる。
【0085】
図4および図6を参照して、3および5ラウンドの場合の同時差分キャンセルの発生例を説明したが、任意のラウンド数に一般化して同時差分キャンセルを定義すると以下のように定義することができる。図7を参照して、任意のラウンド数における同時差分キャンセルの定義について説明する。なお、図7は、フェイステル(Feistel)構造の共通鍵ブロック暗号を実行するフェイステル(Feistel)構造の1つおきのラウンド(i,i+2,i+4,・・・,i+2j)を示している。
【0086】
「定義」
フェイステル(Feistel)構造のラウンドiでの入力差分の半分(PLまたはPR)が0(図7において、ΔXi=(00,00,00,00,00,00,00,00))であり、そこにi+2jラウンド(j=0,1,2,...)のF関数の出力差分が排他的論理和部で演算されていく過程において、あるラウンドi+2kにおいて、排他的論理和の結果が0(図7において、ΔXi+2j+1=(00,00,00,00,00,00,00,00))になった場合を"同時差分キャンセル"と呼ぶ。
【0087】
その時、i,i+2,i+4,..,i+2kラウンドのF関数の中に存在するアクティブSボックス(Active S−box)のことを"同時差分キャンセルを発生させたアクティブSボックス"と呼ぶものとし、ベクトルAの非ゼロの要素数をハミングウェイトhw(A)と定義すると、同時差分キャンセルを発生させるアクティブSボックスの数aは、以下の式として表せる。
【数1】

【0088】
前述の3ラウンド、5ラウンドでの例ではともに同時差分キャンセルを発生させたアクティブSボックス数は2、すなわちa=2である。
【0089】
前述したように、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつが暗号化関数全体でのアクティブSボックスの最小数であり、アクティブSボックス数の最小数が大きいほど差分攻撃に対する耐性が高いと判断される。
【0090】
しかし、DESアルゴリズムのように同じ線形変換行列をすべての段のF関数に用いる構成では、図4、図6を参照して説明したように、わずか2つのアクティブSボックスにより同時差分キャンセルが発生してしまう可能性があった。そのような性質があるためラウンド数の伸びに対してアクティブSボックスの最小数が十分に増大せず、差分攻撃に対する強度がそれほど伸びないという問題があった。
【0091】
[2.共通鍵ブロック暗号アルゴリズムにおける線形解析処理]
差分解析処理は、上述したように、解析の実行者が一定の差分を持つ入力データ(平文)を容易し、その対応する出力データ(暗号文)を解析することが必要となる。線形解析処理は、一定の差分を持つ入力データ(平文)を準備する必要はなく、所定量以上の入力データ(平文)と対応する出力データ(暗号文)とに基づいて解析を行う。
【0092】
前述したように、共通鍵ブロック暗号アルゴリズムでは非線形変換部としてのSボックスを有し、入力データ(平文)と対応する出力データ(暗号文)との線形関係はないが、線形解析では、このSボックスの入出力を線形近似し、多数の入力データ(平文)と対応する出力データ(暗号文)の構成ビット値の線形関係を解析し、候補となる鍵を絞り込むことによって解析を行う。線形解析においては、特定の差分を持つ入力データを準備することが必要ではなく、多数の平文と対応暗号文を容易することで、解析が可能となる。
【0093】
[3.耐性を向上させた暗号処理アルゴリズム構成例]
次に、本発明の出願人が先に提案した暗号処理アルゴリズムについて説明する。以下で説明する暗号処理アルゴリズムは、本出願と同一出願人による特許出願、特願2003−339634、および特願2004−256465において説明しているアルゴリズムであり、上述した線形解析、差分解析等の攻撃に対する耐性を向上させた構成、すなわち、鍵解析の困難性を高め、安全性を向上させた構成を持つ。
【0094】
以下で説明する暗号処理アルゴリズムの1つの特徴は、従来のDESアルゴリズムの如く各ラウンドのF関数に構成される線形変換部に共通の処理(変換行列)を適用した構成とせず、複数の異なる正方MDS(Maximum Distance Separable)行列を設定した構成としたことである。具体的には、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方MDS行列を適用した線形変換処理を実行する構成を持つ。
【0095】
この暗号処理アルゴリズムは、正方MDS(Maximum Distance Separable)行列の性質を利用し、少ないアクティブSボックスに基づく同時差分キャンセルが起こらない、または起こりにくい構造を実現し、アクティブSボックスの最小数を増大させ、差分攻撃に対してより強い共通鍵ブロック暗号処理を実現する。あるいは、既知平文攻撃として行なわれる線形解析についての困難性も高めた構成を持つ。
【0096】
この暗号処理アルゴリズムは、図1、2を参照して説明したSPN型のF関数を有するFeistel構造と呼ばれる代表的な共通鍵ブロック暗号の構造、すなわち、非線形変換部および線形変換部を有するSPN型のF関数の複数ラウンドに渡る単純な繰り返しにより、平文を暗号文に変換する、あるいは暗号文を平文変換する構造を適用している。
【0097】
例えば、平文の長さを2mnビット(ただし、m,nは共に整数)として、2mnビットの平文を、mnビットの2つのデータPL(Plain-Left),PR(Plain-Right)に分割し、これを入力値として、各ラウンドにおいて、F関数を実行させるものであり、F関数は、図2を参照して説明したように、Sボックスからなる非線形変換部と、線形変換部を接続したSPN型を持つF関数である。
【0098】
この暗号処理アルゴリズムにおいては、F関数中の線形変換部において適用する線形変換処理のための行列として、複数の異なる正方MDS(Maximum Distance Separable)行列から選択された行列を各ラウンドのF関数の線形変換部において適用する行列として設定する。具体的には、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方MDS行列を適用する。
【0099】
正方MDS行列について説明する。正方MDS行列とは以下の(a),(b)の性質を満たす行列をいう。
(a)正方行列である
(b)行列に含まれるすべての部分行列(submatrix)の行列式(determinant)が0でない、すなわち、det(submatrix)≠0
【0100】
上記(a),(b)の条件を満足する行列を正方MDS行列と呼ぶ。
共通鍵ブロック暗号の各ラウンドで実行するF関数に対する入出力ビット長がm×n(m,n:整数)ビットであり、F関数内に構成される非線形変換部がnビットの入出力を持つm個のSボックスにより構成され、線形変換部がn次の既約多項式で定義される2の拡大体GF(2)上の元を要素として持つm次の正方行列に基づく線形変換処理を実行する場合の、正方MDS行列の一例を図8に示す。図8に示す正方MDS行列の例は、n=8,m=8の正方MDS行列の例である。
【0101】
上記(a),(b)を満足する正方MDS行列は、ベクトルAの非ゼロの要素数をハミングウェイトhw(A)とし、Mをm次の正方MDS行列とし、xを正方MDS行列Mへの入力ベクトルとした場合、以下の不等式(式1)を満たすことになる。
hw(x)+hw(Mx)≧m+1‥‥‥‥‥‥(式1)
【0102】
上記式(式1)は、正方MDS行列(M)によって線形変換される入力データxの非ゼロの要素数hw(x)と、正方MDS行列(M)によって線形変換された出力データMxの非ゼロの要素数hw(Mx)の総数が、正方MDS行列の次数mより大となるということを意味している。
【0103】
なお、正方MDS行列という名は正方MDS−code(Maximum Distance Separable Code)の生成行列の標準形の右半分が上記条件を満足していることから名づけているものである。
【0104】
1つの行列をすべてのF関数に組み込むという従来の構成でも線形変換行列に正方MDS行列を用いることで、正方MDS行列でない行列を用いる場合に比べてアクティブSボックス数の最小数を比較的高水準に保持することができるということは知られている。
【0105】
本アルゴリズムでは、各ラウンドのF関数には正方MDS行列の条件を満たす行列を利用し、さらにラウンドごとに異なる行列を設定する方法を提案する。具体的には、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方MDS行列を適用する。
【0106】
以下に、段数(ラウンド数)が2r(rは整数)のFeistel型共通鍵ブロック暗号において、差分攻撃に対する耐性をより高めた複数の構成例について説明する。
【0107】
なお、以下の説明において、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成のj段目のF関数における線形変換部で適用する線形変換行列をMLTjとして表すものとする。
【0108】
本アルゴリズムの構成では、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成における各段のF関数中の線形変換部において適用する線形変換処理のための行列として、複数の異なる正方MDS(Maximum Distance Separable)行列から選択された行列を各ラウンドのF関数の線形変換部において適用する行列として設定する。具体的には、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方MDS行列を適用する。
【0109】
具体的には、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成に対応して、r以下のq個の正方MDS行列:L1,L2,・・,Lqを生成し、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成における奇数段目のF関数中の線形変換部において適用する線形変換処理のための行列として、上位段のF関数から順にL1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定する。さらに、偶数段のF関数については、下位段のF関数から順に、L1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定する。
【0110】
本設定を適用した構成例を図9に示す。図9は、段数(ラウンド数)が2r=12、すなわちr=6のFeistel型共通鍵ブロック暗号処理構成とした場合、q=3、すなわち、12段のラウンド数を持つFeistel型共通鍵ブロック暗号処理構成において3種類の異なる正方MDS行列を配置した構成例として、各ラウンドのF関数部の線形変換部に設定する正方MDS行列(L1,L2,L3)を示している。
【0111】
図9の構成は、2mnビットの平文を、mnビットの2つのデータPL(Plain-Left),PR(Plain-Right)に分割し、これを入力値として、各ラウンドにおいて、F関数を実行させる構成であり、第1ラウンドのF関数401およびその他のラウンドのF関数も、すべて図2を参照して説明したように、Sボックスからなる非線形変換部と、線形変換部を接続したSPN型を持つF関数である。
【0112】
図9の設定例はr=6,q=3であり、各F関数内に示す記号Lnは正方MDS行列402を示している。すなわち、L1,L2,L3は、それぞれ異なる3種類の正方MDS行列を示し、各F関数の線形変部において線形変換処理に適用する正方MDS行列を示している。
【0113】
線形変換行列MLTjの設定処理シーケンスについて、図10を参照して説明する。
【0114】
[ステップS21]
ラウンド数2rの半数rに対してr以下の数q、すなわち、
q≦rとなる数qを選択する。ただし、qは2以上の整数である。
[ステップS22]
q個のGF(2)上のm次正方MDS行列L1,L2,...,Lqを生成する。q個のGF(2)上のm次正方MDS行列L1,L2,...,Lqの生成処理手法についての詳細は、後段で説明する。
【0115】
ステップS22において、q個のGF(2)上のm次正方MDS行列L1,L2,...,Lqが生成した後、次に、以下の正方MDS行列設定処理を実行する。
[ステップS23]
2i−1(1≦i≦r)段目の線形変換行列MLT2i−1にL(i−1modq)+1を設定する。
[ステップS24]
2i(1≦i≦r)段目の線形変換行列にMLT2にMLT2r−2i+1を設定する。
【0116】
例えば、図9に示す構成例、すなわち、12段(r=6)でありq=3とした場合は、
MLT1=L1, MLT2=L3
MLT3=L2, MLT4=L2
MLT5=L3, MLT6=L1
MLT7=L1, MLT8=L3
MLT9=L2, MLT10=L2
MLT11=L3, MLT12=L1
の設定となる。
【0117】
このように、このアルゴリズムを適用した暗号処理装置においては、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成に対応して、r以下のq個の正方MDS行列:L1,L2,・・,Lqを生成し、奇数段目については上位段のF関数から順にL1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定し、偶数段のF関数については、下位段のF関数から順に、L1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定する構成としている。
【0118】
次に、図10の処理フローにおけるステップS22のq個のGF(2)上のm次正方MDS行列L1,L2,...,Lqの生成処理およびF関数への設定構成の詳細について説明する。なお、説明は以下の項目に沿って行なう。
(3−a)差分攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例
(3−b)線形攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例
(3−c)差分攻撃および線形攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例
【0119】
[(3−a)差分攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例]
まず、差分攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例として、3つの処理例a1,a2,a3について説明する。
【0120】
(処理例a1)
差分攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例の第1の例について説明する。まず、図11に示すフローチャートを参照して正方MDS行列の生成処理について説明する。
【0121】
[ステップS101]
入力:必要な正方MDSの個数q,拡大次数:n,行列のサイズ:mとして、
GF(2)上で、q個のm次正方MDS行列L1,L2,...,Lqをランダムに生成する。なお、図11に示すフローでは、MDSの個数q=6,拡大次数:n=8,行列のサイズ:m=8の場合の処理例として示してある。
【0122】
[ステップS102]
q個のm次正方MDS行列L1,L2,...,Lqに含まれるqm個の列の任意のm個を取り出したときに、線形独立になっているかどうかをチェックする。チェックに通過したらステップS103に進む、そうでない場合はステップS101にもどる。
[ステップS103]
q個のm次正方MDS行列L1,L2,...,Lqを、ラウンド数2rのFeistel型共通鍵ブロック暗号に適用する正方MDS行列として出力する。
【0123】
以上のプロセスによって、q個のm次正方MDS行列L1,L2,...,Lqが生成される。なお、q≦rである。
【0124】
このようにして生成したq個のm次正方MDS行列L1,L2,...,Lqを、先に、図10を参照して説明した、[ステップS23]、[ステップS24]の処理に従って、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成の各段のF関数部の線形変換部の線形変換処理に適用する行列として設定する。すなわち、奇数段目については上位段から順にL1,L2,・・,Lq,L1,L2・・としてq個の正方MDS行列を繰り返し設定し、偶数段のF関数については、下位段のF関数から順に、L1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定する。
【0125】
このように、偶数ラウンドの正方MDS行列と奇数ラウンドの正方MDS行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【0126】
本構成により、
(a)各F関数の線形変換行列は正方MDSであること、
(b)暗号化関数内の奇数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが独立であること、
(c)偶数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが独立であること、
これら(a)〜(c)が保証されるため、複数段のラウンド数を持つFeistel型共通鍵ブロック暗号処理構成において、連続する2q−1ラウンドにおいて、m個以下のアクティブSボックスの寄与による同時差分キャンセルは発生しないことが保証される。よって暗号化関数全体のアクティブSボックス数の最小値が増大する。
【0127】
このように、本処理例によって、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブSボックスの最小数を大きくすることが可能となり、結果として、差分解析(差分攻撃)を行なった場合のアクティブSボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。
【0128】
(処理例a2)
差分攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例の第2の例について説明する。図12のフローチャートを参照して正方MDS行列の生成処理について説明する。
【0129】
[ステップS201]
入力:必要なMDSの個数q,拡大次数:n,行列のサイズ:mとして、
GF(2)上で、q個のm次正方MDS行列L1,L2,...,Lqをランダムに生成する。なお、図12に示すフローでは、MDSの個数q=6,拡大次数:n=8,行列のサイズ:m=8の場合の処理例として示してある。
【0130】
[ステップS202]
q個のm次正方MDS行列L1,L2,...,Lqに含まれるqm個の列の任意のm個を取り出したときに、正方MDS行列になっているかどうかをチェックする。チェックに通過したらステップS203に進む、そうでない場合はステップS201にもどる。
なお、正方MDS行列とは、前述したように以下の性質を満たす行列をいう。
(a)正方行列である
(b)行列に含まれるすべての部分行列(submatrix)の行列式(determinant)が0でない、すなわち、det(submatrix)≠0
[ステップS203]
q個のm次正方MDS行列L1,L2,...,Lqを、ラウンド数2rのFeistel型共通鍵ブロック暗号に適用する正方MDS行列として出力する。
【0131】
以上のプロセスによって、q個のm次正方MDS行列L1,L2,...,Lqが生成される。なお、q≦rである。
【0132】
前述の処理例a1における正方MDS行列生成処理においては、図11の処理シーケンスにおいて説明したように、ステップS102において、q個のm次正方MDS行列L1,L2,...,Lqに含まれるqm個の列の任意のm個を取り出したときの線形独立性を判定したが、この処理例a2における正方MDS行列生成処理においては、q個のm次正方MDS行列L1,L2,...,Lqに含まれるqm個の列の任意のm個を取り出したとき正方MDS行列になっているかどうかをチェックする。すなわち、より厳しいチェックが実行されることになる。
【0133】
この図12に示す処理シーケンスに従った正方MDS行列生成処理によって生成されたq個のm次正方MDS行列L1,L2,...,Lqが、先に説明した処理例a1と同様、先に、図10を参照して説明した、[ステップS23]、[ステップS24]の処理に従って、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成の各段のF関数部の線形変換部の線形変換処理に適用する行列として設定される。すなわち、奇数段目については上位段から順にL1,L2,・・,Lq,L1,L2・・としてq個の正方MDS行列を繰り返し設定し、偶数段のF関数については、下位段のF関数から順に、L1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定する。
【0134】
このように、偶数ラウンドの正方MDS行列と奇数ラウンドの正方MDS行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【0135】
本構成により、
(a)各F関数の線形変換行列は正方MDSであること、
(b)暗号化関数内の奇数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが正方MDS行列であること、
(c)偶数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが正方MDS行列であること、
これら(a)〜(c)が保証されるため、複数段のラウンド数を持つFeistel型共通鍵ブロック暗号処理構成において、連続する2q−1ラウンドにおいて、m個以下のアクティブSボックスの寄与による同時差分キャンセルは発生しないことが保証される。
さらに、
(d)正方MDSの性質から、a個(a≦m)のアクティブSボックスの寄与によって得られる差分値における非ゼロの要素数はm+1−a個以上になることが保証される。よって暗号化関数全体のアクティブSボックス数の最小値が増大する。
【0136】
このように、本処理例によって、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブSボックスの最小数を大きくすることが可能となり、結果として、差分解析(差分攻撃)を行なった場合のアクティブSボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。
【0137】
(処理例a3)
差分攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例の第3の例について説明する。図13のフローチャートを参照して正方MDS行列の生成処理について説明する。
【0138】
[ステップS301]
入力:必要なMDSの個数q,拡大次数:n,行列のサイズ:mとして、
GF(2)上で、1個のqm次正方MDS行列Mを生成する。なお、図13に示すフローでは、MDSの個数q=6,拡大次数:n=8,行列のサイズ:m=8の場合の処理例として示してある。
【0139】
[ステップS302]
1個のqm次正方MDS行列Mからm本の行を任意に選択抽出し、m行,qm列の行列M'を構成する。
[ステップS303]
m行,qm列の行列M'に含まれるqm本の列ベクトルを重複することなくm本の列ベクトルからなるq個のグループに任意に分割し、それぞれのグループに含まれる列ベクトルからm次の正方行列L1,L2,...,Lqを、ラウンド数2rのFeistel型共通鍵ブロック暗号に適用する正方MDS行列として出力する。
【0140】
以上のプロセスによって、q個のm次正方MDS行列L1,L2,...,Lqが生成される。なお、q≦rである。
【0141】
処理例a3における正方MDS行列生成手法3について、図14を参照して、より具体的に説明する。
[ステップS301]
GF(2)上で、1個のqm次正方MDS行列Mを生成する。図14に示すように、qm×qmの正方MDS行列Mを生成する。なお、このステップS301において生成する行列Mの次数はqm次より大きいものでもよい。
[ステップS302]
図14に示すように、qm次正方MDS行列Mからm本の行を任意に選択抽出し、m行,qm列の行列M'を構成する。なお、図に示す例では、連続するm本の行を選択抽出した例として示してあるが、m次正方MDS行列Mを構成する任意の離間した行をm本選択抽出して、m行,qm列の行列M'を構成してもよい。
[ステップS303]
m行,qm列の行列M'に含まれるqm本の列ベクトルを重複することなくm本の列ベクトルからなるx個のグループに任意に分割し、それぞれのグループに含まれる列ベクトルからm次の正方行列L1,L2,...,Lxを生成する。
【0142】
図13、図14を参照して説明した処理シーケンスに従った正方MDS行列生成処理によって生成されたq個のm次正方MDS行列L1,L2,...,Lqが、先に説明した処理例a1、a2と同様、先に、図10を参照して説明した、[ステップS23]、[ステップS24]の処理に従って、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成の各段のF関数部の線形変換部の線形変換処理に適用する行列として設定される。すなわち、奇数段目については上位段から順にL1,L2,・・,Lq,L1,L2・・としてq個の正方MDS行列を繰り返し設定し、偶数段のF関数については、下位段のF関数から順に、L1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定する。
【0143】
このように、偶数ラウンドの正方MDS行列と奇数ラウンドの正方MDS行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【0144】
本構成により、
(a)各F関数の線形変換行列は正方MDSであること、
(b)暗号化関数内の奇数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが独立であること、
(c)偶数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが独立であること、
これら(a)〜(c)が保証されるため、複数段のラウンド数を持つFeistel型共通鍵ブロック暗号処理構成において、連続する2q−1ラウンドにおいて、m個以下のアクティブSボックスの寄与による同時差分キャンセルは発生しないことが保証される。
さらに、
(d)正方MDSの性質から、a個(a≦m)のアクティブSボックスの寄与によって得られる差分値における非ゼロの要素数はm+1−a個以上になることが保証される。よって暗号化関数全体のアクティブSボックス数の最小値が増大する。
【0145】
なお、処理例a3が特に効果を発揮するのは、m,r,が大きくなり、前述した処理例a1,a2の行列決定処理方式にかかる時間的コストが莫大となり、現実的な時間内に行列を決定することが困難である場合である。そのような場合でも本処理例a3の正方MDS行列生成手法ならば比較的短時間での行列生成処理が可能となる。
【0146】
これは、処理例a3においては、大きなm,rに対しても現実的な時間で十分に処理可能な方式、例えばリードソロモン(Reed−Solomon)符号の生成行列の生成法を適用することが可能となるからである。
【0147】
この処理例a3においても、上述したように、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブSボックスの最小数を大きくすることが可能となり、結果として、差分解析(差分攻撃)を行なった場合のアクティブSボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。
【0148】
[(3−b)線形攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例]
次に、線形攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例として、2つの処理例b1,b2について説明する。
【0149】
(処理例b1)
線形攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例の第1の例について、説明する。図15に示すフローチャートを参照して正方MDS行列の生成処理について説明する。
【0150】
[ステップS401]
入力:必要な正方MDSの個数q,拡大次数:n,行列のサイズ:mとして、
GF(2)上で、q個のm次正方MDS行列M1,M2,...,Mqをランダムに生成する。なお、図14に示すフローでは、正方MDSの個数q=6,拡大次数:n=8,行列のサイズ:m=8の場合の処理例として示してある。
【0151】
[ステップS402]
q個のm次正方MDS行列M1,M2,...,Mqの逆行列M1−1,M2−1,...,Mq−1を算出し、隣り合う2つの逆行列に含まれる2mの行ベクトルから任意のm本の行ベクトルを取り出したときに、線形独立になっているかどうかをチェックする。図15中、Rは、行ベクトルの転置ベクトルを示すものである。チェックに通過したらステップS403に進む、そうでない場合はステップS401にもどる。ただし、M1−1とMq−1は、隣り合う行列とする。
[ステップS403]
q個のm次正方MDS行列L1,L2,...,Lqを、ラウンド数2rのFeistel型共通鍵ブロック暗号に適用する正方MDS行列として出力する。
【0152】
以上のプロセスによって、q個のm次正方MDS行列L1,L2,...,Lqが生成される。なお、q≦rである。
【0153】
このようにして生成したq個のm次正方MDS行列L1,L2,...,Lqを、先に、図10を参照して説明した、[ステップS23]、[ステップS24]の処理に従って、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成の各段のF関数部の線形変換部の線形変換処理に適用する行列として設定する。すなわち、奇数段目については上位段から順にL1,L2,・・,Lq,L1,L2・・としてq個の正方MDS行列を繰り返し設定し、偶数段のF関数については、下位段のF関数から順に、L1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定する。
【0154】
このように、偶数ラウンドの正方MDS行列と奇数ラウンドの正方MDS行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【0155】
本構成により、
(a)各F関数の線形変換行列は正方MDSであること、
(b)暗号化関数内の奇数ラウンド内に連続して含まれる線形変換行列、および偶数ラウンド内に連続して含まれる線形変換行列の逆行列の任意のm個の列ベクトルは独立であること、
が保証される。このことにより、線形攻撃における線形近似による解析困難性を高めることが可能となり、解析の困難性、すなわち鍵の解析の困難な安全性の高い暗号処理が実現される。
【0156】
(処理例b2)
線形攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例の第2の例について、説明する。図16に示すフローチャートを参照して正方MDS行列の生成処理について説明する。
【0157】
[ステップS501]
入力:必要な正方MDSの個数q,拡大次数:n,行列のサイズ:mとして、
GF(2)上で、q個のm次正方MDS行列M1,M2,...,Mqをランダムに生成する。なお、図16に示すフローでは、正方MDSの個数q=6,拡大次数:n=8,行列のサイズ:m=8の場合の処理例として示してある。
【0158】
[ステップS502]
q個のm次正方MDS行列M1,M2,...,Mqの逆行列M1−1,M2−1,...,Mq−1を算出し、隣り合う2つの逆行列に含まれる2mの行ベクトルから任意のm本の行ベクトルを取り出したときに、正方MDS行列になっているかどうかをチェックする。図16中、Rは、行ベクトルの転置ベクトルを示すものである。チェックに通過したらステップS503に進む、そうでない場合はステップS401にもどる。ただし、M1−1とMq−1は、隣り合う行列とする。
なお、正方MDS行列とは、前述したように以下の性質を満たす行列をいう。
(a)正方行列である
(b)行列に含まれるすべての部分行列(submatrix)の行列式(determinant)が0でない、すなわち、det(submatrix)≠0
【0159】
[ステップS503]
q個のm次正方MDS行列L1,L2,...,Lqを、ラウンド数2rのFeistel型共通鍵ブロック暗号に適用する正方MDS行列として出力する。
【0160】
以上のプロセスによって、q個のm次正方MDS行列L1,L2,...,Lqが生成される。なお、q≦rである。
【0161】
前述の処理例b1における正方MDS行列生成処理においては、図15の処理シーケンスにおいて説明したように、ステップS402において、q個のm次正方MDS行列のM1,M2,...,Mqの逆行列M1−1,M2−1,...,Mq−1に含まれるqm個の列の任意のm個を取り出したときの線形独立性を判定したが、この処理例b2における正方MDS行列生成処理においては、q個のm次正方MDS行列のM1,M2,...,Mqの逆行列M1−1,M2−1,...,Mq−1に含まれるqm個の列の任意のm個を取り出したとき正方MDS行列になっているかどうかをチェックする。すなわち、より厳しいチェックが実行されることになる。
【0162】
この図16に示す処理シーケンスに従った正方MDS行列生成処理によって生成されたq個のm次正方MDS行列L1,L2,...,Lqが、先に説明した処理例b1と同様、先に、図10を参照して説明した、[ステップS23]、[ステップS24]の処理に従って、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成の各段のF関数部の線形変換部の線形変換処理に適用する行列として設定される。すなわち、奇数段目については上位段から順にL1,L2,・・,Lq,L1,L2・・としてq個の正方MDS行列を繰り返し設定し、偶数段のF関数については、下位段のF関数から順に、L1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定する。
【0163】
このように、偶数ラウンドの正方MDS行列と奇数ラウンドの正方MDS行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【0164】
本構成により、
(a)各F関数の線形変換行列は正方MDSであること、
(b)暗号化関数内の奇数ラウンド内に連続して含まれる線形変換行列、および偶数ラウンド内に連続して含まれる線形変換行列の逆行列の任意のm個の列ベクトルが正方MDS行列となること、
が保証される。このことにより、線形攻撃における線形近似による解析困難性を高めることが可能となり、解析の困難性、すなわち鍵の解析の困難な安全性の高い暗号処理が実現される。
【0165】
[(3−c)差分攻撃および線形攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例]
次に、差分攻撃および線形攻撃に対する耐性向上を実現した正方MDS行列の生成およびF関数への設定例について説明する。
【0166】
差分攻撃に対する耐性を持つ暗号処理アルゴリズムは、先に、図10〜図13を参照して説明した処理、すなわち、F関数の線形処理部における線形変換に適用する正方MDS行列を前述の処理例a1(図11)〜a3(図13)のいずれかの処理を適用して設定することで実現される。また、線形攻撃に対する耐性を持つ暗号処理アルゴリズムは、先に、図10、および図14、図15を参照して説明した処理、すなわち、F関数の線形処理部における線形変換に適用する正方MDS行列を前述の処理例b1(図14)、b2(図15)のいずれかの処理を適用して設定することで実現される。
【0167】
差分攻撃および線形攻撃に対する耐性向上を実現した正方MDS行列は、
処理例a1(図11)〜a3(図13)のいずれかの処理と、
処理例b1(図14)、b2(図15)のいずれかの処理とを、
併せて実行して生成した正方MDS行列を、図10において説明した[ステップS23]、[ステップS24]の処理に従って、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成の各段のF関数部の線形変換部の線形変換処理に適用する行列として設定することで実現される。
【0168】
すなわち、
処理例a1と処理例b1、
処理例a1と処理例b2、
処理例a2と処理例b1、
処理例a2と処理例b2、
処理例a3と処理例b1、
処理例a3と処理例b2、
のいずれかの組み合わせによって、q個の正方MDS行列を生成し、2rのFeistel型共通鍵ブロック暗号処理構成の各段のF関数部の線形変換部の線形変換処理に適用する行列として設定する。奇数段目については上位段から順にL1,L2,・・,Lq,L1,L2・・としてq個の正方MDS行列を繰り返し設定し、偶数段のF関数については、下位段のF関数から順に、L1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定する。この設定により、差分攻撃および線形攻撃に対する耐性向上を実現した暗号処理が可能となる。
【0169】
図17を参照して、差分攻撃および線形攻撃に対する耐性向上を実現した暗号処理を実現するための正方MDS行列の生成処理の一例について説明する。この処理は、前述した処理例a2と、処理例b2との組み合わせである。
【0170】
[ステップS601]
入力:必要な正方MDSの個数q,拡大次数:n,行列のサイズ:mとして、
GF(2)上で、q個のm次正方MDS行列M1,M2,...,Mqをランダムに生成する。なお、図17に示すフローでは、正方MDSの個数q=6,拡大次数:n=8,行列のサイズ:m=8の場合の処理例として示してある。
【0171】
[ステップS602]
q個のm次正方MDS行列M1,M2,...,Mqに含まれるqm個の列の任意のm個を取り出したときに、正方MDS行列になっているかどうかをチェックする。チェックに通過したらステップS603に進む、そうでない場合はステップS601にもどる。
なお、正方MDS行列とは、前述したように以下の性質を満たす行列をいう。
(a)正方行列である
(b)行列に含まれるすべての部分行列(submatrix)の行列式(determinant)が0でない、すなわち、det(submatrix)≠0
【0172】
[ステップS603]
q個のm次正方MDS行列M1,M2,...,Mqの逆行列M1−1,M2−1,...,Mq−1を算出し、隣り合う2つの逆行列に含まれる2mの行ベクトルから任意のm本の行ベクトルを取り出したときに、正方MDS行列になっているかどうかをチェックする。図17中、Rは、行ベクトルの転置ベクトルを示すものである。チェックに通過したらステップS604に進む、そうでない場合はステップS601にもどる。ただし、M1−1とMq−1は、隣り合う行列とする。
【0173】
[ステップS604]
q個のm次正方MDS行列L1,L2,...,Lqを、ラウンド数2rのFeistel型共通鍵ブロック暗号に適用する正方MDS行列として出力する。
【0174】
以上のプロセスによって、q個のm次正方MDS行列L1,L2,...,Lqが生成される。なお、q≦rである。
【0175】
この図17に示す処理シーケンスに従った正方MDS行列生成処理によって生成されたq個のm次正方MDS行列L1,L2,...,Lqが、先に、図10を参照して説明した、[ステップS23]、[ステップS24]の処理に従って、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成の各段のF関数部の線形変換部の線形変換処理に適用する行列として設定される。すなわち、奇数段目については上位段から順にL1,L2,・・,Lq,L1,L2・・としてq個の正方MDS行列を繰り返し設定し、偶数段のF関数については、下位段のF関数から順に、L1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定する。
【0176】
このように、偶数ラウンドの正方MDS行列と奇数ラウンドの正方MDS行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【0177】
本構成により、
(a)各F関数の線形変換行列は正方MDSであること、
(b)暗号化関数内の奇数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが正方MDS行列であること、
(c)偶数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが正方MDS行列であること、
これら(a)〜(c)が保証されるため、複数段のラウンド数を持つFeistel型共通鍵ブロック暗号処理構成において、連続する2q−1ラウンドにおいて、m個以下のアクティブSボックスの寄与による同時差分キャンセルは発生しないことが保証される。
さらに、
(d)正方MDSの性質から、a個(a≦m)のアクティブSボックスの寄与によって得られる差分値における非ゼロの要素数はm+1−a個以上になることが保証される。よって暗号化関数全体のアクティブSボックス数の最小値が増大する。
さらに、
(e)暗号化関数内の奇数ラウンド内に連続して含まれる線形変換行列、および偶数ラウンド内に連続して含まれる線形変換行列の逆行列の任意のm個の列ベクトルが正方MDS行列となることが保証される。このことにより、線形攻撃における線形近似による解析困難性を高めることが可能となり、解析の困難性、すなわち鍵の解析の困難な安全性の高い暗号処理が実現される。
【0178】
このように、本処理例によって、差分攻撃および線形攻撃の双方の解析の困難性が向上し、鍵の解析の困難な安全性の高い暗号処理が実現される。なお、図17に示した例は、前述したように、先に説明した処理例a2と処理例b2の組み合わせによる正方MDS行列の生成例であるが、その他、処理例a1と処理例b1、処理例a1と処理例b2、処理例a2と処理例b1、処理例a3と処理例b1、処理例a3と処理例b2とを組み合わせてq個の正方MDS行列の生成を行い、段数(ラウンド数)が2rのFeistel型共通鍵ブロック暗号処理構成の各段のF関数部の線形変換部の線形変換処理に適用する行列として、奇数段目については上位段から順にL1,L2,・・,Lq,L1,L2・・としてq個の正方MDS行列を繰り返し設定し、偶数段のF関数については、下位段のF関数から順に、L1,L2,・・,Lq,L1,L2・・として、q個の正方MDS行列を繰り返し設定することによっても、差分攻撃および線形攻撃の双方の解析の困難性が高く、鍵の解析の困難な安全性の高い暗号処理が実現可能である。
【0179】
これまでの説明では、分かりやすさを優先して線形変換行列をGF(2)上で定義されるm×mの行列として、mnビットからmnビットへのデータ変換演算としてきたが、差分解析および線形解析に対する同様な効果がGF(2)上で定義されるmn×mnの行列を用いた場合でも有効である。実際、任意のGF(2)上の行列は同じ変換を表すGF(2)上の行列に一対一で対応させることができる。よってGF(2)上の行列はより一般的な表現を表しているといえる。GF(2)上では行と列の本数がmn本ずつと、GF(2)の場合と比べてn倍となる。このためGF(2)上の行列の1行目は、GF(2)上の行列の1からn行目に対応し、1列目は1からn列目に対応している。つまりi行目は(i−1)+1行目から(i−1)+n行目に対応し、i列目は(i−1)+1列目から(i−1)+n列目に対応している。よって、GF(2)上の行や列を取り出してくる操作には、GF(2)上で定義される行列を用いる場合は、対応するn行分もしくはn列分を取り出すという操作を対応させればよい。GF(2)上のm本の行や列を取り出す操作は、GF(2)上ではn本の行や列をm回取り出すことになり、結果としてmn×mnの行列を得ることができる。以上の対応付けにより、GF(2)上で定義される行列に容易に拡張することができる。
【0180】
[4.本発明に係る暗号処理アルゴリズム]
次に、本発明に係る暗号処理アルゴリズムについて説明する。
上述の項目[3.耐性を向上させた暗号処理アルゴリズム構成例]において説明したように、非線形変換部および線形変換部を有するSPN型のF関数の複数ラウンド繰り返し構成において、特定の条件を満足する正方MDS(Maximum Distance Separable)行列を適用した線形変換処理を行なう構成とすることで、暗号解析処理、攻撃処理として知られる線形解析、差分解析に対する耐性を向上させることが可能であることを説明した。
【0181】
しかし、上述した処理構成では、利用できる行列が限定されてしまうという問題がある。すなわち、前述した処理例a1〜a3において説明した差分攻撃に対する耐性向上を図るための各F関数に設定する線形変換行列の条件としては、
(A1)各F関数の線形変換行列は正方MDSであること、
(A2)暗号化関数内の奇数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが独立または正方MDS行列であること、
(A3)偶数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが独立または正方MDS行列であること、
これらの条件を満足させることが必要であった。
【0182】
また、前述した処理例b1〜b2において説明した線形攻撃に対する耐性向上を図るための各F関数の線形変換行列の条件としては、
(B1)各F関数の線形変換行列は正方MDSであること、
(B2)暗号化関数内の奇数ラウンド内に連続して含まれる線形変換行列、および偶数ラウンド内に連続して含まれる線形変換行列の逆行列の任意のm個の列ベクトルが正方MDS行列となること、
これらの条件を満足させることが必要であった。
【0183】
さらに、差分攻撃および線形攻撃の双方に対する耐性を持つ構成とするためには、上述した(A1)〜(A3)および(B1)〜(B2)のすべての条件を満足させることが必要となり、利用できる行列の候補数が絞られてしまうという問題がある。
【0184】
先に図1、図2を参照して説明したように、Feistel構造は、変換関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。初めに、2mnビットの平文を、mnビットの2つの入力データP(Plain-Left)101,P(Plain-Right)102に分割し、これを入力値として、F関数(ラウンド関数)120をr段繰り返す。
【0185】
例えば、図1に示す第1番目のラウンドでは、mnビットの入力データXと、鍵生成部(図示せず)から入力されるmnビットのラウンド鍵K103がF関数120に入力され、F関数120におけるデータ変換処理の後にmnビットのデータYを出力する。出力はもう片方の前段からの入力データ(第1段の場合は入力データP)と排他的論理和部104において、排他的論理和演算がなされ、mnビットの演算結果が次のラウンド関数へと出力される。この処理、すなわちF関数を定められたラウンド数(r)だけ繰り返し適用して暗号化処理が完了し、暗号文の分割データC(Cipher-Left)、C(Cipher-Right)が出力される。以上の構成より、Feistel構造の復号処理はラウンド鍵を挿入する順序を逆にするだけでよく、逆関数を構成する必要がないことが導かれる。
【0186】
各ラウンドの関数として設定されるF関数120の構成については、先に図2を参照して説明したように、非線形変換層と線形変換層を接続したいわゆるSPN型の構成を有する。SPN型のF関数120は、図2(b)に示すように、非線形変換処理を実行する複数のSボックス(S−box)121を有する。ラウンド関数部の前段からのmnビットの入力値Xは、鍵スケジュール部から入力されるラウンド鍵Kと排他的論理和が実行され、その出力がnビットずつ非線形変換処理を実行する複数(m個)のSボックス121に入力される。各Sボックスでは、例えば変換テーブルを適用した非線形変換処理が実行される。
【0187】
Sボックス121からの出力データであるmnビットの出力値Zは、線形変換処理を実行する線形変換部122に入力されて、例えばビット位置の入れ替え処理などの線形変換処理が実行され、mnビットの出力値Yを出力する。この出力値Yが前段からの入力データと排他的論理和され、次のラウンドのF関数の入力値とされる。
【0188】
図2に示すF関数120は、入出力ビット長がm×n(m,n:整数)ビットであり、非線形変換層はnビットの入出力を持つ非線形変換層としてのSボックス121は、m個並列にならんだ構成を有し、線形変換層としての線形変換部122はn次の既約多項式で定義される2の拡大体GF(2)上の元を要素として持つm次の正方行列に基づく線形変換処理を実行する。
【0189】
線形変換部122における線形変換処理に適用する正方行列は、例えば図3に示す構成を持ち、非線形変換部(Sボックス121)から出力されたm個のnビットデータZ[1],Z[2],...,Z[m]に対してあらかじめ定められた正方行列125を適用した演算により線形変換が施され、F関数(ラウンド関数)出力としての、Y[1],Y[2],...,Y[m]が決定される。ただし、このとき各データの行列の要素に対する線形演算はあらかじめ定められた2の拡大体GF(2)上で行われる。
【0190】
この線形変換処理に適用する正方行列について、上述した[3.耐性を向上させた暗号処理アルゴリズム構成例]において、特定の条件を満足する正方MDS(Maximum Distance Separable)行列を適用することで、暗号解析処理、攻撃処理として知られる線形解析、差分解析に対する耐性を向上させた構成を説明したが、上述したように、制約が多く利用できる行列の候補数が絞られてしまうという問題がある。
【0191】
以下においては、上記の問題を鑑み、線形変換に適用する行列の制約条件を弱めることにより利用可能な行列の候補数を増やし、かつアクティブS−boxの数を十分に大きく保つことのできるFeistel型共通鍵ブロック暗号の2つの構成例について説明する。
【0192】
(4a)構成例1
まず、本発明に係るFeistel型共通鍵ブロック暗号構成例1について説明する。
まず、線形変換の特殊な例として最適拡散変換(Optimal Diffusion Mappings)を以下のように定義する。
n×aビットデータからn×bビットデータへの線形変換を行う写像[θ]
θ:{0,1}na→{0,1}nb
に対して分岐数B(θ)を次のように定義する。
B(θ)=minα≠0{hw(α)+hw(θ(α))}
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値を表すものとし、hw(Y)はビット列Yをnビットごとに区切って表したときに、nビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数とする。
このとき、B(θ)がb+1であるような写像θを最適拡散変換と定義する。また便宜的に行列Mの分岐数をB(M)と表すものとする。
【0193】
SPN型のF関数を持つr段からなるFeistel暗号において、BD1〜3を以下のように定義する。
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
として定義する。
ただしA|Bは行列A,Bの連結により得られる行列を表すものとする。
【0194】
また、BLを以下のように定義する。
BL=min{B(−1−1i+2)|1≦i≦r−2}
とする。ただし、Mは行列の転置を表すものとする。
【0195】
本発明に従ったFeistel型暗号の第1の例においては、
(1)BD,BDが3以上になるような行列Mを選択することにより、差分攻撃に対する耐性を向上させ、かつ
(2)BLが3以上になるような行列Mを選択することにより、線形攻撃に対して耐性を向上させた。
【0196】
すなわち、本発明のFeistel型共通鍵ブロック暗号では、線形変換に適用する行列の制約条件は、上記条件(1)、(2)のみであり、前述した[3.耐性を向上させた暗号処理アルゴリズム構成例]において説明した適用可能な行列の制約条件に比較すると緩やかな制約となる。この緩やかな制約により利用可能な行列の候補数を増やし、かつアクティブS−boxの数を十分に大きく保つことのできるFeistel型共通鍵ブロック暗号が構成できる。すなわち、共通鍵ブロック暗号における攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブSボックスの最小数を大きくすることが可能となり、線形攻撃や、差分攻撃に対して耐性が向上し、より安全性の高い暗号処理が実現される。
【0197】
以下、上記条件(1)によって、差分攻撃に対する耐性が向上すること、および上記条件(2)によって、線形攻撃に対する耐性が向上することについての根拠および証明について、以下説明する。
【0198】
(4a.1)構成例1における差分攻撃に対する耐性の向上
まず、上記条件(1)、すなわち、BD,BDが3以上になるような行列Mを選択することにより、差分攻撃に対する耐性が向上する理由について説明する。
【0199】
SPN型のF関数を持つr段からなるFeistel暗号において、BD1〜3は、以下のように定義される。
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
ただしA|Bは行列A,Bの連結により得られる行列を表すものとする。
このとき
条件0)BD≧BD
という関係が存在する。
【0200】
次に、kラウンド目に存在するゼロでない入出力差分をもつS−box(差分アクティブS−box)の個数をDで表すものとする。この時、以下のことが成立する。
【0201】
ゼロでない入力差分をSPN型のF関数を持つFeistel暗号に与えたとき、以下の条件が成り立つ。
条件1)D=0ならば、Di−2≠0,Di−1≠0,Di+1≠0,Di+2≠0,
条件2)D=0ならば、Di−1=Di+1
条件3)Di+1≠0ならばD+Di+1+Di+2≧BD
条件4)D=0ならばDi+1+Di+2≧BD
条件5)Di+2=0ならばD+Di+1≧BD
条件6)D=0ならばDi+1+Di+3+Di+4≧BD
条件7)Di+4=0ならばD+Di+1+Di+3≧BD
である。
【0202】
この時、連続する6段に含まれる差分アクティブS−boxの総数T(=D+Di+1+Di+2+Di+3+Di+4+Di+5)について考察する。
【0203】
ケース1)Di+1≠0かつDi+4≠0の場合、
上記条件3より、D+Di+1+Di+2≧BDかつDi+3+Di+4+Di+5≧BDであるため、
≧2BD
となる。
【0204】
ケース2)Di+1=0の場合、
=D+Di+1+Di+2+Di+3+Di+4+Di+5
となり、上記条件2より、
=2Di+2+Di+3+Di+4+Di+5
が成立し、さらに、上記条件4および条件6に基づいて、
=(Di+2+Di+3)+(Di+2+Di+4+Di+5)≧BD+BD
となる。
【0205】
ケース3)Di+4=0の時、
上記ケース2と同様の証明により、
≧BD+BD
となる。
【0206】
従って、以上の結果をまとめ、条件0を考慮すると、
≧BD+BD
となる。
【0207】
この「6の倍数6R(R≧2)はR個の6の組に分解することができる」という性質により、6R段の差分アクティブS−box数の最小数を、上述の6段で保証される差分アクティブS−boxから計算することができる。
【0208】
つまり、ゼロでない入出力差分をもつS−box(差分アクティブS−box)の最小数はBD,BDを用いて表すことができることがわかる。従来において、BDのみをなるべく大きくするという設計方針は考えられていたが、すべての段に同じ行列を用いるという方法であるため、BD=2となってしまっており、差分アクティブS−boxの最小数は低く抑えられたままであった。
【0209】
しかし、上述した説明では、
BD≧BDという条件が存在し、BDを大きくとることにより、ゼロでない入出力差分をもつS−box(差分アクティブS−box)の最小数を底上げする効果がある。
【0210】
前述した[3.耐性を向上させた暗号処理アルゴリズム構成例]において説明した適用可能な行列の制約条件において、差分攻撃に対する耐性向上を図るための各F関数に設定する線形変換行列の条件としては、
(A1)各F関数の線形変換行列は正方MDSであること、
(A2)暗号化関数内の奇数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが独立または正方MDS行列であること、
(A3)偶数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが独立または正方MDS行列であること、
これらの条件を満足させることが必要であった。
【0211】
この条件は、前述の定義データBD1〜2、すなわち、
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
を用いて示すと、
BD=BD=m+1
となる条件に相当するものである。
【0212】
しかし、ここで説明したアルゴリズムにおいては、
BD≧BDという条件が存在しており、BDを大きくとることにより、最小数を底上げする効果があり、F関数の線形変換に適用する行列の候補数が増え、かつゼロでない入出力差分をもつ差分アクティブS−boxの数を十分に大きく確保できるというメリットがある。すなわち、共通鍵ブロック暗号における攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブSボックスの最小数を大きくすることが可能となり、差分攻撃に対して耐性が向上し、より安全性の高い暗号処理が実現される。
【0213】
(4a.2)構成例1における線形攻撃に対する耐性の向上
次に、前述した条件(2)、すなわち、BLが3以上になるような行列Mを選択することにより、線形攻撃に対して耐性が向上する理由について説明する。
【0214】
BLを以下のように定義される。
BL=min{B(−1−1i+2)|1≦i≦r−2}
とする。ただし、Mは行列の転置を表すものとする。
【0215】
次に、kラウンド目に存在するゼロでない入出力線形マスクをもつS−box(線形アクティブS−box)の個数をLで表すものとする。この時、以下のことが成立する。
【0216】
ゼロでない入力線形マスクをSPN型のF関数を持つFeistel暗号に与えたとき、
条件1)L+Li+1+Li+2≧BL
が常に成立する。
【0217】
3の倍数3R(R≧1)は3の組に分解することができる。この性質により、3R段の線形アクティブS−boxの最小数は、R×BLで保証することができる。従ってBLを大きくとることにより、最小数を底上げする効果がある。
【0218】
前述した[3.耐性を向上させた暗号処理アルゴリズム構成例]において説明した適用可能な行列の制約条件において、線形攻撃に対する耐性向上を図るための各F関数に設定する線形変換行列の条件としては、
(B1)各F関数の線形変換行列は正方MDSであること、
(B2)暗号化関数内の奇数ラウンド内に連続して含まれる線形変換行列、および偶数ラウンド内に連続して含まれる線形変換行列の逆行列の任意のm個の列ベクトルが正方MDS行列となること、
これらの条件を満足させることが必要であった。
この条件は、前述の定義データBL、すなわち、
BL=min{B(−1−1i+2)|1≦i≦r−2}
を用いて表すと、
BL=m+1
となる条件に相当するものである。
【0219】
しかし、ここで説明したアルゴリズムにおいては、
BLが3以上になるような行列Mを選択する
という条件を設定しているのみであり、3R段の線形アクティブS−boxの最小数は、R×BLで保証することができる。従ってBLを大きくとることにより、線形アクティブS−boxの最小数を底上げする効果がある。すなわち、共通鍵ブロック暗号における攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブSボックスの最小数を大きくすることが可能となり、線形攻撃に対して耐性が向上し、より安全性の高い暗号処理が実現される。
【0220】
なお、上述した条件、すなわち、
(1)BD,BDが3以上になるような行列Mを選択する
(2)BLが3以上になるような行列Mを選択する
これらの2つの条件は、独立に定義される条件であり、(1)の条件を満足させることで差分攻撃に対する耐性を向上し、(2)の条件を満足させることで、線形攻撃に対する耐性が向上する。
【0221】
これら、「差分攻撃に対する耐性を確保する条件(1)」と「線形攻撃に対する耐性を確保する条件(2)」はそれぞれ独立に定義される条件である。通常は、両方を同じレベルの強度になるような行列を選択する方針が考えられるが、暗号が利用される状況に応じては差分攻撃のみに対しては耐性を高めるが線形攻撃に対してはとくに条件を与えない設計や、その逆の設計を行って運用することも可能である。
【0222】
(4b)構成例2
次に、本発明に係るFeistel型共通鍵ブロック暗号構成例2について説明する。この構成例は、構成例1に比較して制約の多い構成例である。
まず、線形変換の特殊な例として最適拡散変換(Optimal Diffusion Mappings)を以下のように定義する。
n×aビットデータからn×bビットデータへの線形変換を行う写像[θ]
θ:{0,1}na→{0,1}nb
に対して分岐数B(θ)を次のように定義する。
B(θ)=minα≠0{hw(α)+hw(θ(α))}
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値を表すものとし、hw(Y)はビット列Yをnビットごとに区切って表したときに、nビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数とする。
このとき、B(θ)がb+1であるような写像θを最適拡散変換と定義する。また便宜的に行列Mの分岐数をB(M)と表すものとする。
【0223】
SPN型のF関数を持つr段からなるFeistel暗号において、BD1〜3を以下のように定義する。
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
BD=min{B(M|Mi+2|Mi+4)|1≦i≦r−4},
として定義する。
ただしA|Bは行列A,Bの連結により得られる行列を表すものとする。
【0224】
また、BLを以下のように定義する。
BL=min{B(−1−1i+2)|1≦i≦r−2}
とする。ただし、Mは行列の転置を表すものとする。
【0225】
本発明に従ったFeistel型暗号においては、
(1)BD,BD,BDが3以上になるような行列Mを選択することにより、差分攻撃に対する耐性を向上させ、かつ
(2)BLが3以上になるような行列Mを選択することにより、線形攻撃に対して耐性を向上させた。
【0226】
すなわち、本発明のFeistel型共通鍵ブロック暗号では、線形変換に適用する行列の制約条件は、上記条件(1)、(2)のみであり、前述した[3.耐性を向上させた暗号処理アルゴリズム構成例]において説明した適用可能な行列の制約条件に比較すると緩やかな制約となる。この緩やかな制約により利用可能な行列の候補数を増やし、かつアクティブS−boxの数を十分に大きく保つことのできるFeistel型共通鍵ブロック暗号が構成できる。すなわち、共通鍵ブロック暗号における攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブSボックスの最小数を大きくすることが可能となり、線形攻撃や、差分攻撃に対して耐性が向上し、より安全性の高い暗号処理が実現される。
【0227】
以下、上記条件(1)によって、差分攻撃に対する耐性が向上すること、および上記条件(2)によって、線形攻撃に対する耐性が向上することについての根拠および証明について、以下説明する。
【0228】
(4b.1)構成例2における差分攻撃に対する耐性の向上
まず、上記条件(1)、すなわち、BD,BD,BDが3以上になるような行列Mを選択することにより、差分攻撃に対する耐性が向上する理由について説明する。
【0229】
SPN型のF関数を持つr段からなるFeistel暗号において、BD1〜3は、以下のように定義される。
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
BD=min{B(M|Mi+2|Mi+4)|1≦i≦r−4},
ただしA|Bは行列A,Bの連結により得られる行列を表すものとする。
このとき
条件0)BD≧BD≧BD
という関係が存在する。
【0230】
次に、kラウンド目に存在するゼロでない入出力差分をもつS−box(差分アクティブS−box)の個数をDで表すものとする。この時、以下のことが成立する。
【0231】
ゼロでない入力差分をSPN型のF関数を持つFeistel暗号に与えたとき、以下の条件が成り立つ。
条件1)D=0ならば、Di−2≠0,Di−1≠0,Di+1≠0,Di+2≠0,
条件2)D=0ならば、Di−1=Di+1
条件3)Di+1≠0ならばD+Di+1+Di+2≧BD
条件4)D=0ならばDi+1+Di+2≧BD
条件5)Di+2=0ならばD+Di+1≧BD
条件6)D=0ならばDi+1+Di+3+Di+4≧BD
条件7)Di+4=0ならばD+Di+1+Di+3≧BD
条件8)D=Di+6=0ならばDi+1+Di+3+Di+5≧BD
である。
【0232】
この時、連続する6段に含まれる差分アクティブS−boxの総数T(=D+Di+1+Di+2+Di+3+Di+4+Di+5)について考察する。
【0233】
ケース1)Di+1≠0かつDi+4≠0の場合、
上記条件3より、D+Di+1+Di+2≧BDかつDi+3+Di+4+Di+5≧BDであるため、
≧2BD
となる。
【0234】
ケース2)Di+1=0の場合、
=D+Di+1+Di+2+Di+3+Di+4+Di+5
となり、上記条件2より、
=2Di+2+Di+3+Di+4+Di+5
が成立し、さらに、上記条件4および条件6に基づいて、
=(Di+2+Di+3)+(Di+2+Di+4+Di+5)≧BD+BD
となる。
【0235】
ケース3)Di+4=0の時、
上記ケース2と同様の証明により、
≧BD+BD
となる。
【0236】
従って、以上の結果をまとめ、条件0を考慮すると、
≧BD+BD
となる。
【0237】
次に、連続する9段に含まれる差分アクティブS−boxの総数、
=(D+Di+1+Di+2+Di+3+Di+4+Di+5+Di+6+Di+7+Di+8
について考察する。
【0238】
ケース1)Di+1≠0の場合、
上記条件3より、
+Di+1+Di+2≧BD
また、前述した6段の差分アクティブS−box数により、
i+3+Di+4+Di+5+Di+6+Di+7+Di+8≧BD+BD
が成立する。よって、
≧2BD+BD
となる。
【0239】
ケース2)Di+7≠0の場合、
ケース1と同様の証明により、
≧2BD+BD
となる。
【0240】
ケース3)Di+1=Di+7=0の場合、
=D+Di+1+Di+2+Di+3+Di+4+Di+5+Di+6+Di+7+Di+8
であり、さらに条件2より、
=2Di+2+Di+3+Di+4+Di+5+2Di+6
となり、さらに条件4,8,5より、
=(Di+2+Di+3)+(Di+2+Di+4+Di+6)+(Di+5+Di+6)≧2BD+BD
となる。
従って、以上の結果をまとめ、条件0を考慮すると、
≧2BD+BDとなる。
【0241】
6以上の任意の3の倍数3R(R≧2)は6と9の組に分解することができる。以下に例を示す。
例)6=6,9=9,12=6+6,15=6+9,18=6+6+6=9+9,
21=6+6+9,24=6+6+6+6=9+9+6,...
【0242】
この「6以上の任意の3の倍数3R(R≧2)は6と9の組に分解することができる」という性質により、3R段の差分アクティブS−box数の最小数を、上述の6段と9段で保証される差分アクティブS−boxから計算することができる。
【0243】
つまり、ゼロでない入出力差分をもつS−box(差分アクティブS−box)の最小数はBD,BD,BDを用いて表すことができることがわかる。従来において、BDのみをなるべく大きくするという設計方針は考えられていたが、すべての段に同じ行列を用いるという方法であるため、BD=BD=2となってしまっており、差分アクティブS−boxの最小数は低く抑えられたままであった。
【0244】
しかし、上述した説明では、
BD≧BD≧BDという条件を設定しているものであり、
BDを大きくとることにより、ゼロでない入出力差分をもつS−box(差分アクティブS−box)の最小数を底上げする効果がある。
【0245】
前述した[3.耐性を向上させた暗号処理アルゴリズム構成例]において説明した適用可能な行列の制約条件において、差分攻撃に対する耐性向上を図るための各F関数に設定する線形変換行列の条件としては、
(A1)各F関数の線形変換行列は正方MDSであること、
(A2)暗号化関数内の奇数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが独立または正方MDS行列であること、
(A3)偶数ラウンド内の少なくとも連続するq個のF関数に含まれる線形変換行列の任意のm個の列ベクトルが独立または正方MDS行列であること、
これらの条件を満足させることが必要であった。
【0246】
この条件は、前述の定義データBD1〜3、すなわち、
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
BD=min{B(M|Mi+2|Mi+4)|1≦i≦r−4},
を用いて示すと、
BD=BD=BD=m+1
となる条件に相当するものである。
【0247】
しかし、ここで説明したアルゴリズムにおいては、
BD≧BD≧BDという条件を設定しているのみであり、
BDを大きくとることにより、最小数を底上げする効果があり、F関数の線形変換に適用する行列の候補数が増え、かつゼロでない入出力差分をもつ差分アクティブS−boxの数を十分に大きく確保できるというメリットがある。すなわち、共通鍵ブロック暗号における攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブSボックスの最小数を大きくすることが可能となり、差分攻撃に対して耐性が向上し、より安全性の高い暗号処理が実現される。
【0248】
(4b.2)構成例2における線形攻撃に対する耐性の向上
次に、前述した条件(2)、すなわち、BLが3以上になるような行列Mを選択することにより、線形攻撃に対して耐性が向上する理由について説明する。
【0249】
BLは以下のように定義される。
BL=min{B(−1−1i+2)|1≦i≦r−2}
とする。ただし、Mは行列の転置を表すものとする。
【0250】
次に、kラウンド目に存在するゼロでない入出力線形マスクをもつS−box(線形アクティブS−box)の個数をLで表すものとする。この時、以下のことが成立する。
【0251】
ゼロでない入力線形マスクをSPN型のF関数を持つFeistel暗号に与えたとき、
条件1)L+Li+1+Li+2≧BL
が常に成立する。
【0252】
3の倍数3R(R≧1)は3の組に分解することができる。この性質により、3R段の線形アクティブS−boxの最小数は、R×BLで保証することができる。従ってBLを大きくとることにより、最小数を底上げする効果がある。
【0253】
前述した[3.耐性を向上させた暗号処理アルゴリズム構成例]において説明した適用可能な行列の制約条件において、線形攻撃に対する耐性向上を図るための各F関数に設定する線形変換行列の条件としては、
(B1)各F関数の線形変換行列は正方MDSであること、
(B2)暗号化関数内の奇数ラウンド内に連続して含まれる線形変換行列、および偶数ラウンド内に連続して含まれる線形変換行列の逆行列の任意のm個の列ベクトルが正方MDS行列となること、
これらの条件を満足させることが必要であった。
この条件は、前述の定義データBL、すなわち、
BL=min{B(−1−1i+2)|1≦i≦r−2}
を用いて表すと、
BL=m+1
となる条件に相当するものである。
【0254】
しかし、ここで説明したアルゴリズムにおいては、
BLが3以上になるような行列Mを選択する
という条件を設定しているのみであり、3R段の線形アクティブS−boxの最小数は、R×BLで保証することができる。従ってBLを大きくとることにより、線形アクティブS−boxの最小数を底上げする効果がある。すなわち、共通鍵ブロック暗号における攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブSボックスの最小数を大きくすることが可能となり、線形攻撃に対して耐性が向上し、より安全性の高い暗号処理が実現される。
【0255】
なお、上述した条件、すなわち、
(1)BD,BD,BDが3以上になるような行列Mを選択する
(2)BLが3以上になるような行列Mを選択する
これらの2つの条件は、独立に定義される条件であり、(1)の条件を満足させることで差分攻撃に対する耐性を向上し、(2)の条件を満足させることで、線形攻撃に対する耐性が向上する。
【0256】
これら、「差分攻撃に対する耐性を確保する条件(1)」と「線形攻撃に対する耐性を確保する条件(2)」はそれぞれ独立に定義される条件である。通常は、両方を同じレベルの強度になるような行列を選択する方針が考えられるが、暗号が利用される状況に応じては差分攻撃のみに対しては耐性を高めるが線形攻撃に対してはとくに条件を与えない設計や、その逆の設計を行って運用することも可能である。
【0257】
最後に、暗号処理を実行する暗号処理装置としてのICモジュール600の構成例を図18に示す。上述の処理は、例えばPC、ICカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図18に示すICモジュール600は、これら様々な機器に構成することが可能である。
【0258】
図18に示すCPU(Central processing Unit)601は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ602は、CPU601が実行するプログラム、あるいは演算パラメータとしての固定データを格納するROM(Read-Only-Memory)、CPU601の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるRAM(Random Access Memory)等からなる。また、メモリ602は暗号処理に必要な鍵データ等の格納領域として使用可能である。データ等の格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【0259】
暗号処理部603は、例えば上述したFeistel型共通鍵ブロック暗号処理アルゴリズムに従った暗号処理、復号処理等を実行する。なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをROMに格納し、CPU601がROM格納プログラムを読み出して実行するように構成してもよい。
【0260】
乱数発生器604は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。
【0261】
送受信部605は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ICモジュールとのデータ通信を実行し、ICモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【0262】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【0263】
更に、本発明の実施例では、2種類または3種類の行列式を用いて説明を行っているが、それに限定されるものではなく、複数種類の行列式を用いて、実施例の制約条件を満足させることができるならば、差分攻撃及び線形攻撃に対する耐性を向上させることは可能である。
【0264】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【0265】
例えば、プログラムは記録媒体としてのハードディスクやROM(Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、CD−ROM(Compact Disc Read Only Memory),MO(Magneto optical)ディスク,DVD(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納(記録)しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【0266】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、LAN(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【0267】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【0268】
上述したように、本発明の構成によれば、非線形変換部および線形変換部を有するSPN型のF関数を、複数ラウンド繰り返し実行するFeistel型共通鍵ブロック暗号処理において、複数ラウンド各々に対応するF関数の線形変換処理を、比較的緩やかな制限によって特定される行列を適用して実行する構成により、共通鍵ブロック暗号における差分攻撃や線形攻撃に対する耐性が向上する。また、制限が比較的緩やかであり、利用できる行列の候補が増加するとともに、アクティブS−box数を十分大きく確保することが可能となる。すなわち、共通鍵ブロック暗号における攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブSボックスの最小数を大きくすることが可能となり、線形攻撃や、差分攻撃に対して耐性が向上し、より安全性の高い暗号処理が実現される。
【図面の簡単な説明】
【0269】
【図1】Feistel構造を持つ代表的な共通鍵ブロック暗号の構成を示す図である。
【図2】ラウンド関数部として設定されるF関数の構成について説明する図である。
【図3】線形変換部において、線形変換処理に適用する正方行列の例を示す図である。
【図4】m=8,n=8の128bitブロック暗号における3段の同時差分キャンセルの様子を説明する図である。
【図5】F関数の線形変換部において、正方行列による線形変換が実行されて、F関数出力差分ΔYiを生成する具体例を説明する図である。
【図6】m=8,n=8の128bitブロック暗号における5段の同時差分キャンセルの様子を説明する図である。
【図7】共通鍵ブロック暗号における任意段の同時差分キャンセルの定義を説明する図である。
【図8】正方MDS行列の一例を示す図である。
【図9】共通鍵ブロック暗号処理アルゴリズムにおける各ラウンドのF関数の線形変換行列としての正方MDS行列設定例を説明する図である。
【図10】共通鍵ブロック暗号処理アルゴリズムにおける各ラウンドのF関数の線形変換行列としての正方MDS行列設定処理シーケンスを説明するフロー図である。
【図11】各ラウンドのF関数に設定する線形変換行列である正方MDS行列の生成手法として、差分攻撃に対する耐性向上を実現する正方MDS行列生成処理例a1を説明するフロー図である。
【図12】各ラウンドのF関数に設定する線形変換行列である正方MDS行列の生成手法として、差分攻撃に対する耐性向上を実現する正方MDS行列生成処理例a2を説明するフロー図である。
【図13】各ラウンドのF関数に設定する線形変換行列である正方MDS行列の生成手法として、差分攻撃に対する耐性向上を実現する正方MDS行列生成処理例a3を説明するフロー図である。
【図14】各ラウンドのF関数に設定する線形変換行列である正方MDS行列の生成処理例a3の具体的手法を説明する図である。
【図15】各ラウンドのF関数に設定する線形変換行列である正方MDS行列の生成手法として、線形攻撃に対する耐性向上を実現する正方MDS行列生成処理例b1を説明するフロー図である。
【図16】各ラウンドのF関数に設定する線形変換行列である正方MDS行列の生成手法として、線形攻撃に対する耐性向上を実現する正方MDS行列生成処理例b2を説明するフロー図である。
【図17】各ラウンドのF関数に設定する線形変換行列である正方MDS行列の生成手法として、差分攻撃および線形攻撃に対する耐性向上を実現する正方MDS行列生成処理例を説明するフロー図である。
【図18】本発明にかかる暗号処理を実行する暗号処理装置としてのICモジュールの構成例を示す図である。
【符号の説明】
【0270】
101 入力データP(Plain-Left)
102 入力データP(Plain-Right)
103 ラウンド鍵
104 排他的論理和部
120 F関数
121 Sボックス(S−box)
122 線形変換部
125 正方行列
131,133 排他的論理和部
141〜145 排他的論理和部
401 F関数
402 正方MDS行列
600 ICモジュール
601 CPU(Central processing Unit)
602 メモリ
603 暗号処理部
604 乱数発生器
605 送受信部

【特許請求の範囲】
【請求項1】
複数ビットの入出力を持つ複数の非線形変換層を並列に構成した非線形変換部と、
線形変換を施す線形変換層で構成した線形変換部とで構成されるFeistel型暗号処理を備える暗号処理装置において、
前記線形変換部は、前記線形変換に適応する行列の制約条件に基づいて処理を施すことを特徴とする暗号処理装置。
【請求項2】
前記線形変換に適応する行列の制約条件は、
r段各々に対応するF関数の線形変換部の満足する行列Miを適用した構成、すなわち、 n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hwn(α)+hwn(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、hwn(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BD1=min{B(Mi)|1≦i≦r},
BD2=min{B(Mi|Mi+2)|1≦i≦r−2},
ただし、A|Bは行列A,Bの連結により得られる行列、
とした場合において、
BD1,BD2のすべてが3以上になるような行列Miを適用した構成であることを特徴とする請求項1に記載の暗号処理装置。
【請求項3】
暗号処理装置であり、
非線形変換部および線形変換部を有するSPN型のF関数を持つr段からなるFeistel型共通鍵ブロック暗号処理構成を有し、
前記r段各々に対応するF関数の線形変換部は下記条件を満足する行列Mを適用した構成、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
BD=min{B(M|Mi+2|Mi+4)|1≦i≦r−4},
ただし、A|Bは行列A,Bの連結により得られる行列、
とした場合において、
BD,BD,BDのすべてが3以上になるような行列Mを適用した構成であることを特徴とする暗号処理装置。
【請求項4】
暗号処理装置であり、
非線形変換部および線形変換部を有するSPN型のF関数を持つr段からなるFeistel型共通鍵ブロック暗号処理構成を有し、
前記r段各々に対応するF関数の線形変換部は下記条件を満足する行列Mを適用した構成、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BL=min{B(−1−1i+2)|1≦i≦r−2}
ただし、Mは行列の転置、
とした場合において、
BLが3以上になるような行列Mを適用した構成であることを特徴とする暗号処理装置。
【請求項5】
Feistel型共通鍵ブロック暗号処理を実行する暗号処理方法であり、
非線形変換部および線形変換部を有するSPN型のF関数をr段、繰り返し実行するステップを有し、
前記r段各々に対応するF関数の線形変換処理は下記条件を満足する行列Mを適用した線形変換処理、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
BD=min{B(M|Mi+2|Mi+4)|1≦i≦r−4},
ただし、A|Bは行列A,Bの連結により得られる行列、
とした場合において、
BD,BD,BDのすべてが3以上になるような行列Mを適用した線形変換処理によって実行することを特徴とする暗号処理方法。
【請求項6】
Feistel型共通鍵ブロック暗号処理を実行する暗号処理方法であり、
非線形変換部および線形変換部を有するSPN型のF関数をr段、繰り返し実行するステップを有し、
前記r段各々に対応するF関数の線形変換部は下記条件を満足する行列Mを適用した線形変換処理、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BL=min{B(−1−1i+2)|1≦i≦r−2}
ただし、Mは行列の転置、
とした場合において、
BLが3以上になるような行列Mを適用した線形変換処理によって実行することを特徴とする暗号処理方法。
【請求項7】
Feistel型共通鍵ブロック暗号処理をコンピュータ上において実行するコンピュータ・プログラムであり、
非線形変換部および線形変換部を有するSPN型のF関数をr段、繰り返し実行するステップを有し、
前記r段各々に対応するF関数の線形変換処理は下記条件を満足する行列Mを適用した線形変換処理、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BD=min{B(M)|1≦i≦r},
BD=min{B(M|Mi+2)|1≦i≦r−2},
BD=min{B(M|Mi+2|Mi+4)|1≦i≦r−4},
ただし、A|Bは行列A,Bの連結により得られる行列、
とした場合において、
BD,BD,BDのすべてが3以上になるような行列Mを適用した線形変換処理によって実行することを特徴とするコンピュータ・プログラム。
【請求項8】
Feistel型共通鍵ブロック暗号処理をコンピュータ上において実行するコンピュータ・プログラムであり、
非線形変換部および線形変換部を有するSPN型のF関数をr段、繰り返し実行するステップを有し、
前記r段各々に対応するF関数の線形変換部は下記条件を満足する行列Mを適用した線形変換処理、すなわち、
n×aビットデータからn×bビットデータへの線形変換を行う写像θ:{0,1}na→{0,1}nbに対して、分岐数B(θ)を、
分岐数B(θ)=minα≠0{hw(α)+hw(θ(α))}、
ただし、minα≠0{Xα}は、α≠0を満たすすべてのXαのうちの最小値、
hw(Y)はビット列Yをnビットごとに区切って表したときにnビットのデータすべてが0ではない(非ゼロ)要素の数を返す関数、
とし、分岐数B(θ)がb+1である写像θを最適拡散変換と定義し、
さらに、行列Mの分岐数をB(M)と表したとき、
BL=min{B(−1−1i+2)|1≦i≦r−2}
ただし、Mは行列の転置、
とした場合において、
BLが3以上になるような行列Mを適用した線形変換処理によって実行することを特徴とするコンピュータ・プログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate