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

Description

本発明は、暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムに関する。さらに詳細には、暗号解析処理、攻撃処理として知られる差分解析に対する耐性を向上させた暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムに関する。

昨今、ネットワーク通信、電子商取引の発展に伴い、通信におけるセキュリティ確保が重要な問題となっている。セキュリティ確保の１つの方法が暗号技術であり、現在、様々な暗号化手法を用いた通信が実際に行なわれている。

例えばＩＣカード等の小型の装置中に暗号処理モジュールを埋め込み、ＩＣカードと、データ読み取り書き込み装置としてのリーダライタとの間でデータ送受信を行ない、認証処理、あるいは送受信データの暗号化、復号を行なうシステムが実用化されている。

暗号処理アルゴリズムには様々なものがあるが、大きく分類すると、暗号化鍵と復号鍵を異なる鍵、例えば公開鍵と秘密鍵として設定する公開鍵暗号方式と、暗号化鍵と復号鍵を共通の鍵として設定する共通鍵暗号方式とに分類される。

共通鍵暗号方式にも様々なアルゴリズムがあるが、その１つに共通鍵をベースとして複数の鍵を生成して、生成した複数の鍵を用いてブロック単位（６４ビット，１２８ビットなど）のデータ変換処理を繰り返し実行する方式がある。このような鍵生成方式とデータ変換処理を適用したアルゴリズムの代表的なものが共通鍵ブロック暗号方式である。

代表的な共通鍵ブロック暗号のアルゴリズムとしては、例えば米国標準暗号としてのＤＥＳ（Data Encryption Standard）アルゴリズムがあり、様々な分野において広く用いられている。

ＤＥＳに代表される共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を実行するラウンド関数部と、ラウンド関数（Ｆ関数）部の各ラウンドで適用する鍵を生成する鍵スケジュール部とに分けることができる。ラウンド関数部の各ラウンドで適用するラウンド鍵（副鍵）は、１つのマスター鍵（主鍵）に基づいて、鍵スケジュール部に入力されて生成され、各ラウンド関数部で適用される。

しかし、このような共通鍵暗号処理においては、暗号解析による鍵、あるいは暗号アルゴリズムの漏洩が問題となっている。暗号解析または攻撃手法の代表的な手法として、ある差分を持つ入力データ（平文）とその出力データ（暗号文）を多数解析することにより各ラウンド関数における適用鍵を解析する差分解析（あるいは差分解読法または差分攻撃とも呼ばれる）が知られている。

暗号解析による鍵の解析が容易であるということは、その暗号処理の安全性が低いということになる。従来のＤＥＳアルゴリズムにおいては、ラウンド関数（Ｆ関数）部の線形変換部において適用する処理（変換行列）が、各段のラウンドにおいて等しいものであったため、差分解析が行いやすく、結果として鍵の解析の容易性を招いているという問題がある。

本発明は、上記問題点に鑑みてなされたものであり、差分解析に対する耐性の高い共通鍵ブロック暗号アルゴリズムを実現する暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムを提供することを目的とする。

具体的には、本発明は、各ラウンド毎に異なる変換行列を適用した線形変換処理を実行することにより、差分解析に対する耐性の高い共通鍵ブロック暗号アルゴリズムを実現する暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムを提供する。

本発明の第１の側面は、
入力情報を非線形変換し、第１非線形変換情報を出力する第１非線形変換部と、当該第１非線形変換情報を線形変換して第１線形変換情報を出力する第１線形変換部とを有する第１暗号処理部と、
入力情報を非線形変換し、第２非線形変換情報を出力する第２非線形変換部と、当該第２非線形変換情報を線形変換して第２線形変換情報を出力する第２線形変換部とを有する第２暗号処理部と、
前記第２暗号処理部からの出力と、前記第１暗号処理部からの出力とが入力される排他的論理和部を備え、
前記第１非線形変換情報を第１列ベクトルで示すと共に前記第１線形変換情報を第２列ベクトルで示した場合に、当該第１列ベクトルを当該第２列ベクトルに変換する第１行列と、
前記第２非線形変換情報を第３列ベクトルで示すと共に前記第２線形変換情報を第４列ベクトルで示した場合に、当該第３列ベクトルを当該第４列ベクトルに変換する第２行列とは、
互いに異なる行列であることを特徴とする暗号処理装置にある。
さらに、本発明の暗号処理装置の一実施態様において、前記第１行列から選択した第１列ベクトルと、前記第２行列から選択した第２列ベクトルとは、いずれの列ベクトルを選択した場合であっても、互いに線形独立であることを特徴とする。
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理装置は、前記排他論理和部における排他論理和結果を前記前記第１暗号処理部または前記第２暗号処理部に再度入力し、前記第１暗号処理部および前記第２暗号処理部における暗号処理を繰り返し実行する構成であることを特徴とする。
さらに、本発明の暗号処理装置の一実施態様において、前記第１線形変換部および前記第２線形変換部は、ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理を実行する構成であり、前記第１線形変換部および前記第２線形変換部において線形変換に適用する前記第１行列と前記第２行列は、行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルが互いに線形独立となるｍ次行列であることを特徴とする。
さらに、本発明の第２の側面は、
Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理装置であり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行する構成を有し、
前記複数ラウンド各々に対応するＦ関数の線形変換部は、
正方行列を適用した線形変換処理を実行する構成であり、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方行列を適用した線形変換処理を実行する構成であることを特徴とする暗号処理装置にある。

さらに、本発明の暗号処理装置の一実施態様において、前記Ｆ関数の線形変換部は、全ての偶数ラウンドおよび全ての奇数ラウンドにおいて異なる正方行列をそれぞれ適用した線形変換処理を実行する構成であることを特徴とする。

さらに、本発明の暗号処理装置の一実施態様において、前記Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理のアルゴリズムは、ラウンド数Ｒの暗号処理アルゴリズムであり、前記Ｆ関数の線形変換部は、ｒ個の全ての偶数ラウンドおよびｒ個の全ての奇数ラウンドにおいてｒ種類の異なる正方行列を順次適用した線形変換処理を実行する構成であることを特徴とする。

さらに、本発明の暗号処理装置の一実施態様において、前記Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理のアルゴリズムは、ラウンド数Ｒの暗号処理アルゴリズムであり、前記Ｆ関数の線形変換部は、ｒ個の全ての偶数ラウンドおよびｒ個の全ての奇数ラウンドにおいて２≦ｑ＜ｒのｑ種類の異なる正方行列を順次繰り返し適用した線形変換処理を実行する構成であることを特徴とする。

さらに、本発明の暗号処理装置の一実施態様において、前記Ｆ関数の線形変換部は、ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理を実行する構成であり、前記Ｆ関数の線形変換部において適用する異なる複数の正方行列の各々は、前記複数の正方行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルによって構成する行列が線形独立である正方行列として設定したことを特徴とする。

さらに、本発明の暗号処理装置の一実施態様において、前記Ｆ関数の線形変換部は、ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理を実行する構成であり、前記Ｆ関数の線形変換部において適用する異なる複数の正方行列の各々は、前記複数の正方行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルによって構成する行列も正方行列となる正方行列として設定したことを特徴とする。

さらに、本発明の暗号処理装置の一実施態様において、前記Ｆ関数の線形変換部において適用する異なる複数の正方行列の各々は、前記異なる正方行列を構成する要素を全て含む正方行列Ｍから選択された行ベクトルによって構成される行列Ｍ'から抽出された列ベクトルによって構成される行列によって構成されていることを特徴とする。

さらに、本発明の暗号処理装置の一実施態様において、前記Ｆ関数の線形変換部において適用する異なる複数の正方行列の各々は、リードソロモン符号生成行列に基づいて生成された正方行列であることを特徴とする。

さらに、本発明の第３の側面は、
暗号処理装置において暗号処理を実行する暗号処理方法であり、
第１暗号処理部の第１非線形変換部において入力情報を非線形変換して第１非線形変換情報を出力し、第１暗号処理部の第１線形変換部において当該第１非線形変換情報を線形変換して第１線形変換情報を出力する第１暗号処理ステップと、
第２暗号処理部の第２非線形変換部において入力情報を非線形変換して第２非線形変換情報を出力し、第２暗号処理部の第２線形変換部において当該第２非線形変換情報を線形変換して第２線形変換情報を出力する第２暗号処理ステップと、
排他的論理和部が、前記第２暗号処理部からの出力と、前記第１暗号処理部からの出力とを入力して排他論理和処理を実行する排他的論理和ステップとを有し、
前記第１暗号処理ステップの第１線形変換処理は、前記第１非線形変換情報を第１列ベクトルで示すと共に前記第１線形変換情報を第２列ベクトルで示した場合に、当該第１列ベクトルを当該第２列ベクトルに変換する第１行列を適用した第１線形変換処理実行ステップであり、
前記第２暗号処理ステップの第２線形変換処理は、前記第２非線形変換情報を第３列ベクトルで示すと共に前記第２線形変換情報を第４列ベクトルで示した場合に、当該第３列ベクトルを当該第４列ベクトルに変換する第２行列を適用した第２線形変換処理実行ステップであり、
前記第１線形変換処理実行ステップにおいて適用する前記第１行列と第２線形変換処理実行ステップにおいて適用する前記第２行列とは互いに異なる行列であることを特徴とする暗号処理方法にある。
さらに、本発明の暗号処理方法の一実施態様において、前記第１行列から選択した第１列ベクトルと、前記第２行列から選択した第２列ベクトルとは、いずれの列ベクトルを選択した場合であっても、互いに線形独立であることを特徴とする。
さらに、本発明の暗号処理方法の一実施態様において、前記暗号処理方法は、前記排他論理和ステップにおける排他論理和結果を前記前記第１暗号処理部または前記第２暗号処理部に再度入力し、前記第１暗号処理ステップおよび前記第２暗号処理ステップの暗号処理を繰り返し実行することを特徴とする。
さらに、本発明の暗号処理方法の一実施態様において、前記第１線形変換部および前記第２線形変換部における線形変換処理は、ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理を実行するステップであり、前記第１線形変換部および前記第２線形変換部において線形変換に適用する前記第１行列と前記第２行列は、行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルが互いに線形独立さなるｍ次行列であることを特徴とする。
さらに、本発明の第４の側面は、
暗号処理装置においてＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理方法であり、
データ変換部が、非線形変換処理および線形変換処理を実行するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行し、
前記複数ラウンド各々に対応するＦ関数の線形変換処理は、
正方行列を適用した線形変換処理を実行するとともに、
少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方行列を適用した線形変換処理を実行することを特徴とする暗号処理方法にある。

さらに、本発明の暗号処理方法の一実施態様において、前記データ変換部が、前記複数ラウンド各々に対応するＦ関数の線形変換処理は、全ての偶数ラウンドおよび全ての奇数ラウンドにおいて異なる正方行列をそれぞれ適用した線形変換処理を実行することを特徴とする。

さらに、本発明の暗号処理方法の一実施態様において、前記暗号処理方法は、前記データ変換部が、ラウンド数ＲのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行し、前記複数ラウンド各々に対応するＦ関数の線形変換処理は、ｒ個の全ての偶数ラウンドおよびｒ個の全ての奇数ラウンドにおいてｒ種類の異なる正方行列を順次適用した線形変換処理を実行することを特徴とする。

さらに、本発明の暗号処理方法の一実施態様において、前記暗号処理方法は、前記データ変換部が、ラウンド数ＲのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行し、前記複数ラウンド各々に対応するＦ関数の線形変換処理は、ｒ個の全ての偶数ラウンドおよびｒ個の全ての奇数ラウンドにおいて２≦ｑ＜ｒのｑ種類の異なる正方行列を順次繰り返し適用した線形変換処理を実行することを特徴とする。

さらに、本発明の暗号処理方法の一実施態様において、前記データ変換部が実行する前記複数ラウンド各々に対応するＦ関数の線形変換処理は、ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理であり、前記複数ラウンド各々に対応するＦ関数の線形変換処理において適用する異なる複数の正方行列の各々は、該複数の正方行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルによって構成する行列が線形独立である正方行列であることを特徴とする。

さらに、本発明の暗号処理方法の一実施態様において、前記データ変換部が実行する前記複数ラウンド各々に対応するＦ関数の線形変換処理は、ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理であり、前記複数ラウンド各々に対応するＦ関数の線形変換処理において適用する異なる複数の正方行列の各々は、前記複数の正方行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルによって構成する行列も正方行列となる正方行列であることを特徴とする。

さらに、本発明の暗号処理方法の一実施態様において、前記データ変換部が実行する前記複数ラウンド各々に対応するＦ関数の線形変換処理において適用する異なる複数の正方行列の各々は、前記複数の正方行列を構成する要素を全て含む正方行列Ｍから選択された行ベクトルによって構成される行列Ｍ'から抽出された列ベクトルによって構成される行列によって構成されていることを特徴とする。

さらに、本発明の暗号処理方法の一実施態様において、前記データ変換部が、前記Ｆ関数の線形変換処理において適用する異なる複数の正方行列の各々は、リードソロモン符号生成行列に基づいて生成された正方行列であることを特徴とする。

さらに、本発明の第５の側面は、
暗号処理装置において暗号処理を実行させるコンピュータ・プログラムであり、
第１暗号処理部の第１非線形変換部に入力情報を非線形変換させて第１非線形変換情報を出力させ、第１暗号処理部の第１線形変換部に当該第１非線形変換情報を線形変換させて第１線形変換情報を出力させる第１暗号処理ステップと、
第２暗号処理部の第２非線形変換部に入力情報を非線形変換させて第２非線形変換情報を出力させ、第２暗号処理部の第２線形変換部に当該第２非線形変換情報を線形変換させて第２線形変換情報を出力させる第２暗号処理ステップと、
排他的論理和部に、前記第２暗号処理部からの出力と、前記第１暗号処理部からの出力とを入力して排他論理和処理を実行させる排他的論理和ステップとを実行させ、
前記第１暗号処理ステップの第１線形変換処理は、前記第１非線形変換情報を第１列ベクトルで示すと共に前記第１線形変換情報を第２列ベクトルで示した場合に、当該第１列ベクトルを当該第２列ベクトルに変換する第１行列を適用した第１線形変換処理を実行させるステップであり、
前記第２暗号処理ステップの第２線形変換処理は、前記第２非線形変換情報を第３列ベクトルで示すと共に前記第２線形変換情報を第４列ベクトルで示した場合に、当該第３列ベクトルを当該第４列ベクトルに変換する第２行列を適用した第２線形変換処理を実行させるステップであり、
前記第１線形変換処理実行ステップにおいて適用する前記第１行列と第２線形変換処理実行ステップにおいて適用する前記第２行列とは互いに異なる行列として設定したことを特徴とするコンピュータ・プログラムにある。
さらに、本発明の第６の側面は、
暗号処理装置においてＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行させるコンピュータ・プログラムであり、
データ変換部に、非線形変換処理および線形変換処理を実行するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行させ、
前記複数ラウンド各々に対応するＦ関数の線形変換処理は、
正方行列を適用した線形変換処理を実行させる処理であり、
少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方行列を適用した線形変換処理を実行させることを特徴とするコンピュータ・プログラムにある。

なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。

本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。

本発明の構成によれば、非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行するＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理において、複数ラウンド各々に対応するＦ関数の線形変換処理を、ＭＤＳ（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ）行列を適用した線形変換処理として実行するとともに、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なるＭＤＳ行列を適用した線形変換処理を実行する構成としたので、アクティブＳボックスの寄与による同時差分キャンセルの発生可能性が低減または解消することとなり、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最少数を大きくすることが可能となる。すなわち、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、暗号鍵等の解析困難性が高まることとなり、差分解析に対する耐性が高く、安全性の高い暗号処理が実現される。

本発明の構成によれば、非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行するＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理において、複数ラウンド各々に対応するＦ関数の線形変換処理を、ＭＤＳ（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ）行列を適用した線形変換処理として実行するとともに、ラウンド数２ｒの暗号処理アルゴリズムに対応してｒの異なるＭＤＳ行列を生成し、偶数ラウンドおよび奇数ラウンドの各々においてｒ個の異なるＭＤＳ行列を適用した線形変換処理を実行する構成とし、適用するＭＤＳ行列の列ベクトルによって構成される行列が線形独立性を示すか、またはＭＤＳ行列を構成することを確認した構成としたので、アクティブＳボックスの寄与による同時差分キャンセルの発生しないことが保証され、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最少数を大きくすることが可能となる。すなわち、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、暗号鍵等の解析困難性が高まることとなり、差分解析に対する耐性が高く、安全性の高い暗号処理が実現される。

本発明の構成によれば、非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行するＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理において、複数ラウンド各々に対応するＦ関数の線形変換処理を、ＭＤＳ（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ）行列を適用した線形変換処理として実行するとともに、ラウンド数２ｒの暗号処理アルゴリズムに対応して２≦ｑ＜ｒの整数ｑ個の異なるＭＤＳ行列を生成し、偶数ラウンドおよび奇数ラウンドの各々においてｑ個の異なるＭＤＳ行列を繰り返し適用した線形変換処理を実行する構成としたので、ラウンド数より少ないＭＤＳ行列の適用により、アクティブＳボックスの寄与による同時差分キャンセルの発生可能性が低減され、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最少数を大きくすることが可能となる。すなわち、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、暗号鍵等の解析困難性が高まることとなり、差分解析に対する耐性が高く、安全性の高い暗号処理が実現される。

以下、本発明の暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムの詳細について説明する。なお、説明は、以下の項目順に行う。
１．共通鍵ブロック暗号アルゴリズムにおける差分解析処理
２．本発明に基づく暗号処理アルゴリズム

［１．共通鍵ブロック暗号アルゴリズムにおける差分解析処理］
まず、ＤＥＳ（Data Encryption Standard）暗号処理に代表される共通鍵ブロック暗号アルゴリズムにおける差分解析処理の概要について、一般化した共通鍵ブロック暗号モデルを用いて説明する。

共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を実行するラウンド関数部と、ラウンド関数部の各ラウンドで適用する鍵を生成する鍵スケジュール部とに分けることができる。ラウンド関数部の各ラウンドで適用する鍵（副鍵）は、１つのマスター鍵（主鍵）に基づいて、鍵スケジュール部に入力されて生成され、各ラウンド関数部で適用される。この共通鍵暗号方式の代表的な方式に米国連邦標準暗号方式としてのＤＥＳ（Data Encryption Standard）がある。

Ｆｅｉｓｔｅｌ構造と呼ばれる代表的な共通鍵ブロック暗号の構造について、図１を参照して説明する。

Ｆｅｉｓｔｅｌ構造は、変換関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。平文の長さを２ｍｎビットとする。ただし、ｍ，ｎは共に整数である。初めに、２ｍｎビットの平文を、ｍｎビットの２つの入力データＰ_Ｌ（Plain-Left）１０１，Ｐ_Ｒ(Plain-Right)１０２に分割し、これを入力値とする。

Ｆｅｉｓｔｅｌ構造はラウンド関数とよばれる基本構造の繰り返しで表現され、各ラウンドに含まれるデータ変換関数はＦ関数１２０と呼ばれる。図１の構成では、Ｆ関数（ラウンド関数）１２０がｒ段繰り返された構成例を示している。

例えば第１番目のラウンドでは、ｍｎビットの入力データＸと、鍵生成部（図示せず）から入力されるｍｎビットのラウンド鍵Ｋ_１１０３がＦ関数１２０に入力され、Ｆ関数１２０におけるデータ変換処理の後にｍｎビットのデータＹを出力する。出力はもう片方の前段からの入力データ（第１段の場合は入力データＰ_Ｌ）と排他的論理和部１０４において、排他的論理和演算がなされ、ｍｎビットの演算結果が次のラウンド関数へと出力される。この処理、すなわちＦ関数を定められたラウンド数（ｒ）だけ繰り返し適用して暗号化処理が完了し、暗号文の分割データＣ_Ｌ（Cipher-Left）、Ｃ_Ｒ（Cipher-Right）が出力される。以上の構成より、Ｆｅｉｓｔｅｌ構造の復号処理はラウンド鍵を挿入する順序を逆にするだけでよく、逆関数を構成する必要がないことが導かれる。

各ラウンドの関数として設定されるＦ関数１２０の構成について、図２を参照して説明する。図２（ａ）は、１つのラウンドにおけるＦ関数１２０に対する入力および出力を示す図であり、図２（ｂ）は、Ｆ関数１２０の構成の詳細を示す図である。Ｆ関数１２０は、図２（ｂ）に示すように、非線形変換層と線形変換層を接続したいわゆるＳＰＮ型の構成を有する。

ＳＰＮ型のＦ関数１２０は、図２（ｂ）に示すように、非線形変換処理を実行する複数のＳボックス（Ｓ−ｂｏｘ）１２１を有する。ラウンド関数部の前段からのｍｎビットの入力値Ｘは、鍵スケジュール部から入力されるラウンド鍵Ｋ_ｉと排他的論理和が実行され、その出力がｎビットずつ非線形変換処理を実行する複数（ｍ個）のＳボックス１２１に入力される。各Ｓボックスでは、例えば変換テーブルを適用した非線形変換処理が実行される。

Ｓボックス１２１からの出力データであるｍｎビットの出力値Ｚは、線形変換処理を実行する線形変換部１２２に入力されて、例えばビット位置の入れ替え処理などの線形変換処理が実行され、ｍｎビットの出力値Ｙを出力する。この出力値Ｙが前段からの入力データと排他的論理和され、次のラウンドのＦ関数の入力値とされる。

図２に示すＦ関数１２０は、入出力ビット長がｍ×ｎ（ｍ，ｎ：整数）ビットであり、非線形変換層はｎビットの入出力を持つ非線形変換層としてのＳボックス１２１は、ｍ個並列にならんだ構成を有し、線形変換層としての線形変換部１２２はｎ次の既約多項式で定義される２の拡大体ＧＦ（２^ｎ）上の元を要素として持つｍ次の正方行列に基づく線形変換処理を実行する。

線形変換部１２２における線形変換処理に適用する正方行列の例を図３に示す。図３に示す正方行列１２５は、ｎ＝８，ｍ＝８の場合の例である。非線形変換部（Ｓボックス１２１）から出力されたｍ個のｎビットデータＺ［１］，Ｚ［２］，...，Ｚ［ｍ］に対してあらかじめ定められた正方行列１２５を適用した演算により線形変換が施され、Ｆ関数（ラウンド関数）出力としての、Ｙ［１］，Ｙ［２］，...，Ｙ［ｍ］が決定される。ただし、このとき各データの行列の要素に対する線形演算はあらかじめ定められた２の拡大体ＧＦ（２^ｎ）上で行われる。

これまでのＦｅｉｓｔｅｌ型暗号では、すべての段のＦ関数に同じ線形変換層を用いているため、差分の伝播時に同時に複数の差分がキャンセルしてしまうという性質が存在した。背景技術の欄において説明したように、暗号解析手法の代表的な手法として、ある差分を持つ入力データ（平文）とその出力データ（暗号文）を多数解析することにより各ラウンド関数における適用鍵を解析する差分解析（あるいは差分解読法）が知られており、従来のＤＥＳ暗号アルゴリズム等の共通鍵ブロック暗号においては、Ｆ関数１２０部の線形変換部１２２において適用する処理（変換行列）を、各段のラウンドにおいて等しいものに設定しているため、差分解析が行いやすく、結果として鍵の解析の容易性を招いている。

差分の伝播時に、同時に複数の差分がキャンセルする例について、図４を参照して説明する。なお、本明細書においては、差分を表す場合にはΔ（デルタ）記号をつけて表す。

図４はｍ＝８，ｎ＝８の１２８ｂｉｔブロック暗号における３段の同時差分キャンセルの様子を説明する図である。ただし、図中では６４ｂｉｔのデータをバイト単位で区切ってベクトルとして表現し、それぞれの要素を１６進数で表記するものとする。

３段構成を持つＦ関数での同時差分キャンセルは、例えば以下のデータ状態１〜４の設定メカニズムに基づいて発生する。以下に説明するメカニズムの発生するデータ状態は、多数の差分入力データを設定することで発生させることができるデータ状態であり、いわゆる差分解析における鍵（ラウンド鍵）の解析において発生し得る。

（状態１）
ｉラウンドへの入力差分の左半分は、すべてゼロである入力差分（ΔＸｉ−１＝（００，００，００，００，００，００，００，００））であり、右半分の入力差分がただひとつのＳ−ｂｏｘへの入力を除いてゼロである入力差分（ΔＸｉ＝（３４，００，００，００，００，００，００，００））であるとする。このデータ状態は、多数の差分入力データを設定することで、ｉラウンドにおいて、このようなデータ状態を得ることができるということである。

なお、ΔＸｉ＝（３４，００，００，００，００，００，００，００）の８つの各要素は、Ｆ関数中に構成されるｍ個（ｍ＝８）のＳボックス各々に対する入力差分に対応する。差分（３４）が第１Ｓボックス（図４中の（Ｓ１））に入力され、（００）が、第２〜８Ｓボックスに対する入力差分である。

なおゼロ（００）の入力差分を持つＳボックスの出力差分はゼロ（００）であり、差分データに関する限り、ゼロ（００）の入力差分を持つＳボックスは、何の作用も行なっていないものであり、アクティブでないすなわち非アクティブＳボックスと呼ばれる。一方、非ゼロの入力差分（図４の例では差分：３４）を持つＳボックスは、非ゼロの入力差分に対応した非線形変換結果を出力差分として発生させるので、アクティブＳボックス（Ａｃｔｉｖｅ Ｓ−ｂｏｘ）と呼ばれる。

図４の例では、非ゼロの入力差分（３４）を入力する１つのアクティブＳボックス（Ｓ１）の出力差分（ｂ７）を発生させており、その他の非アクティブＳボックスＳ２〜Ｓ８はゼロの入力差分（００）に基づいて出力差分（００）を発生させ、線形変換部の差分入力としている。

（状態２）
ｉラウンドへの非ゼロの入力差分（図４の例では差分：３４）を持つＳボックス（以下、アクティブＳボックス（Ａｃｔｉｖｅ Ｓ−ｂｏｘ）と呼ぶ）からの出力差分は線形変換層で拡散されたのちＦ関数から出力（出力値＝ΔＹｉ）され、そのまま次のラウンドへの入力差分ΔＸｉ＋１となる。

図４の例における線形変換は、各ラウンドのＦ関数において共通する例えば図５に示すある特定の正方行列１２５による線形変換が実行されｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）を出力する。図５に示す線形変換構成から理解されるように、出力差分ΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）は、１つのアクティブＳボックス（Ｓ１）からの出力要素Ｚ［１］＝ｂ７にのみ依存した値として決定される。

このｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）は、図４に示す排他的論理和部１３１において、すべてゼロである入力差分（ΔＸｉ−１＝（００，００，００，００，００，００，００，００）と排他的論理和（ＸＯＲ）演算が実行され、演算結果が、次のラウンド（ｉ＋１）への入力差分ΔＸｉ＋１となる。

ｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、すべてゼロである入力差分ΔＸｉ−１＝（００，００，００，００，００，００，００，００）との排他的論理和（ＸＯＲ）結果は、ΔＹｉであるので、次のラウンド（ｉ＋１）への入力差分ΔＸｉ＋１＝ΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）となる。

（状態３）
ｉ＋１ラウンドのＦ関数からの出力差分ΔＹｉ＋１が、ｉラウンドでのＡｃｔｉｖｅ Ｓ−ｂｏｘの位置にのみ非ゼロ値をもつ。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。

すなわち、ΔＹｉ＋１＝（ａｄ，００，００，００，００，００，００，００）であり、ｉラウンドと同様、非ゼロの差分値（図４の例では差分：３４）を持つＳ−ｂｏｘの位置（第１Ｓボックス（Ｓ１））にのみ非ゼロ値をもつ。なお、明らかにａｄ≠００である。

（状態４）
ｉ＋２ラウンドのアクティブＳボックス（Ａｃｔｉｖｅ Ｓ−ｂｏｘ）（Ｓ１）の出力差分がｉラウンドでのアクティブＳボックス（Ａｃｔｉｖｅ Ｓ−ｂｏｘ）（Ｓ１）の出力差分と一致した場合、すなわち、図４に示すようにｉ＋２ラウンドのアクティブＳボックス（（Ｓ１）の出力差分がｂ７となり、ｉラウンドでのアクティブＳボックス（Ｓ１）の出力差分（ｂ７）と一致する。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。

このデータ状態が発生すると、ｉ＋２ラウンドのＦ関数の出力差分ΔＹｉ＋２＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）が、２つ前のラウンドであるｉラウンドのＦ関数の出力差分ΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と一致することになる。

この結果、排他的論理和部１３３では、
ΔＸｉ＋１＝ΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、
ΔＹｉ＋２＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、
の同一の値同士の排他的論理和演算が実行されることになり、排他的論理和演算結果としてオール０の値を出力する。

その結果、次の段（ラウンドｉ＋３）への出力差分の前段（ｉ＋２ラウンド）からの左の入力差分ΔＸｉ＋３＝（００，００，００，００，００，００，００，００）となる。

このラウンドｉ＋３への左入力ΔＸｉ＋３＝（００，００，００，００，００，００，００，００）は、ラウンドｉへの左入力ΔＸｉ−１＝（００，００，００，００，００，００，００，００）と同様オールゼロであり、ラウンドｉ＋３以降のラウンドにおいても、ラウンドｉ〜ｉ＋２と同様の処理が繰り返される可能性がある。

この結果、ラウンド数の伸びに対してアクティブＳボックスの数が増大せず、差分攻撃に対する強度がそれほど伸びないという問題を発生させる。

共通鍵ブロック暗号において、差分攻撃に対する強度指標のひとつとして、暗号化関数全体でのアクティブＳボックスの最少数が知られている。アクティブＳボックス数の最少数が大きいほど差分攻撃に対する耐性が高いと判断される。

前述したように、差分解析（差分攻撃）においては、ある差分を持つ入力データ（平文）とその出力データ（暗号文）を多数設定してこの対応を解析することにより各ラウンド関数における適用鍵を解析する手法であり、この差分解析において、アクティブＳボックスの数を少なくできれば、解析が容易となり、解析プロセス数を削減できる。

上述の図４を参照した例では、第１のＳボックス（Ｓ１）のみがアクティブＳボックスであるパターンの発生状態を提示したが、その他のＳボックス（Ｓ２〜Ｓ８）についても、差分解析の入力データの設定によって、各ＳボックスのみをアクティブＳボックスとした設定が可能であり、このような差分解析プロセスを実行することにより、各Ｓボックスの非線形変換処理の解析、さらにＦ関数に対して入力されるラウンド鍵の解析が可能となる。

このような差分解析に対する耐性を向上させるためには、アクティブＳボックスの数が常に多い状態を維持すること、すなわち、アクティブＳボックスの最少数が多いことが必要である。

図４を参照して説明した例において、右から左へ入力を行なうＦ関数、すなわち、第ｉラウンドと第ｉ＋２ラウンドのみをアクティブＳボックス算出処理対象ラウンドとしてみた場合、アクティブＳボックス数はわずか２であり、左から右へ入力を行なうＦ関数、すなわち、第ｉ＋1ラウンドではアクティブＳボックス数が８であるものの、同時差分キャンセルにより第ｉ＋３ラウンドでのアクティブＳボックス数が０となってしまうため、差分解析による各Ｓボックスの非線形変換処理の解析処理が容易となる。

図４に示す共通鍵ブロック暗号アルゴリズムは、各ラウンドにおける線形変換部において適用する線形変換行列が等しいものであり、この構成に起因して、特に右から左へ入力を行うＦ関数におけるわずか２つのアクティブＳボックスにより同時差分キャンセルの発生可能性を引き起こしている。従って、ラウンド数の伸びに対してアクティブＳボックスの最少数が十分に増大せず、差分攻撃に対する強度がそれほど伸びないという問題がある。

次に、同様に、同じ線形変換行列をすべての段（ラウンド）のＦ関数に用いる構成において、５ラウンドにまたがる同時差分キャンセルの発生メカニズムについて、図６を参照して説明する。

図６はｍ＝８，ｎ＝８の１２８ｂｉｔブロック暗号における５段の同時差分キャンセルの様子を説明する図である。ただし、図中では６４ｂｉｔのデータをバイト単位で区切ってベクトルとして表現し、それぞれの要素を１６進数で表記するものとする。

５段構成を持つＦ関数での同時差分キャンセルは、例えば以下のデータ状態１〜７の設定メカニズムに基づいて発生する。以下に説明するメカニズムの発生するデータ状態は、多数の差分入力データを設定することで発生させることができるデータ状態であり、いわゆる差分解析における鍵（ラウンド鍵）の解析において発生し得る。

（状態１）
ｉラウンドへの入力差分の左半分は、すべてゼロである入力差分（ΔＸｉ−１＝（００，００，００，００，００，００，００，００））であり、右半分の入力差分がただひとつのＳ−ｂｏｘへの入力を除いてゼロである入力差分（ΔＸｉ＝（３４，００，００，００，００，００，００，００））であるとする。このデータ状態は、多数の差分入力データを設定することで、ｉラウンドにおいて、このようなデータ状態を得ることができるということである。

なお、ΔＸｉ＝（３４，００，００，００，００，００，００，００）の８つの各要素は、Ｆ関数中に構成されるｍ個（ｍ＝８）のＳボックス各々に対する入力差分に対応する。（３４）が第１Ｓボックス（図６中の（Ｓ１））に入力され、（００）が、第２〜８Ｓボックスに対する入力差分である。

なお前述したように、ゼロ（００）の入力差分を持つＳボックスの出力差分はゼロ（００）であり、差分データに関する限り、ゼロ（００）の入力差分を持つＳボックスは、何の作用も行なっていないものであり、アクティブでないすなわち非アクティブＳボックスと呼ばれる。一方、非ゼロの入力差分（図６の例では差分：３４）を持つＳボックス（Ｓ１）のみが、非ゼロの入力差分に対応した非線形変換結果を出力差分として発生させるので、アクティブＳボックス（Ａｃｔｉｖｅ Ｓ−ｂｏｘ）である。

図６の例では、非ゼロの入力差分（３４）を入力する１つのアクティブＳボックス（Ｓ１）の出力差分（ｂ７）を発生させており、その他の非アクティブＳボックスＳ２〜Ｓ８はゼロの入力差分（００）に基づいて出力差分（００）を発生させ、線形変換部の差分入力としている。

（状態２）
ｉラウンドへの非ゼロの入力差分（図４の例では差分：３４）を持つＳボックス（以下、アクティブＳボックス（Ａｃｔｉｖｅ Ｓ−ｂｏｘ）と呼ぶ）からの出力差分は線形変換層で拡散されたのちＦ関数から出力（出力値＝ΔＹｉ）され、そのまま次のラウンドへの入力差分ΔＸｉ＋１となる。

図６の例において、各ラウンドに共通の例えば図５に示すある特定の正方行列１２５による線形変換が実行されｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）を出力する。

ｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）は、図６に示す排他的論理和部１４１において、すべてゼロである入力差分（ΔＸｉ−１＝（００，００，００，００，００，００，００，００）と排他的論理和（ＸＯＲ）演算が実行され、演算結果が、次のラウンド（ｉ＋１）への入力差分ΔＸｉ＋１となる。

ｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、すべてゼロである入力差分（ΔＸｉ−１＝（００，００，００，００，００，００，００，００）との排他的論理和（ＸＯＲ）結果は、ΔＹｉであるので、次のラウンド（ｉ＋１）への入力差分ΔＸｉ＋１＝ΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）となる。

（状態３）
ｉ＋１ラウンドのＦ関数からの出力差分ΔＹｉ＋１が、ｉラウンドでのＡｃｔｉｖｅ Ｓ−ｂｏｘの位置にのみ非ゼロ値をもつ。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。

すなわち、ΔＹｉ＋１＝（３４，００，００，００，００，００，００，００）であり、ｉラウンドと同様、非ゼロの差分値（図６の例では差分：３４）を持つＳ−ｂｏｘの位置（第１Ｓボックス（Ｓ１））にのみ非ゼロ値をもつ。

（状態４）
ｉ＋２ラウンドのＦ関数に対する入力は、ΔＸｉ＝（３４，００，００，００，００，００，００，００）と、ΔＹｉ＋１＝（３４，００，００，００，００，００，００，００）との排他的論理和部１４２における排他的論理和結果、すなわち、同一データ同士の排他的論理和であり、オールゼロの入力、ΔＸｉ＋２＝（００，００，００，００，００，００，００，００）となり、その結果、ｉ＋２ラウンドのＦ関数からの出力差分も、オールゼロの出力差分、ΔＹｉ＋２＝（００，００，００，００，００，００，００，００）となる。

（状態５）
ｉ＋３ラウンドのＦ関数に対する入力は、ΔＸｉ＋１＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、オールゼロのｉ＋２ラウンドのＦ関数出力差分ΔＹｉ＋２＝（００，００，００，００，００，００，００，００）との排他的論理和部１４３における排他的論理和結果であり、ｉ＋３ラウンドのＦ関数に対する入力ΔＸｉ＋３＝ΔＸｉ＋１＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）となる。

（状態６）
ｉ＋３ラウンドのＦ関数出力差分が、ΔＹｉ＋３＝（４３，００，００，００，００，００，００，００）となり、オールゼロのΔＸｉ＋２＝（００，００，００，００，００，００，００，００）との排他的論理和部１４４における排他的論理和の結果としてのΔＸｉ＋４＝ΔＹｉ＋３＝（４３，００，００，００，００，００，００，００）がｉ＋４ラウンドのＦ関数入力差分となる。

（状態７）
ｉ＋４ラウンドのアクティブＳボックス（Ａｃｔｉｖｅ Ｓ−ｂｏｘ）（Ｓ１）の出力差分がｉラウンドでのアクティブＳボックス（Ａｃｔｉｖｅ Ｓ−ｂｏｘ）（Ｓ１）の出力差分と一致した場合、すなわち、図６に示すようにｉ＋４ラウンドのアクティブＳボックス（（Ｓ１）の出力差分がｂ７となり、ｉラウンドでのアクティブＳボックス（Ｓ１）の出力差分（ｂ７）と一致する。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。

このデータ状態が発生すると、ｉ＋４ラウンドのＦ関数の出力差分ΔＹｉ＋４＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）が、２つ前のラウンドであるｉ＋２ラウンドの排他的論理和部１４３の出力差分ΔＸｉ＋３＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と一致することになる。

この結果、排他的論理和部１４５では、
ΔＸｉ＋３＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、
ΔＹｉ＋４＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、
の同一の値同士の排他的論理和演算が実行されることになり、排他的論理和演算結果としてオール０の値を出力する。

その結果、次の段（ラウンドｉ＋５）への入力差分は、ΔＸｉ＋５＝（００，００，００，００，００，００，００，００）として設定される。

このラウンドｉ＋５への左入力ΔＸｉ＋５＝（００，００，００，００，００，００，００，００）は、ラウンドｉへの左入力ΔＸｉ−１＝（００，００，００，００，００，００，００，００）と同様オールゼロであり、ラウンドｉ＋５以降のラウンドにおいても、ラウンドｉ〜ｉ＋４と同様の処理が繰り返される可能性がある。

この結果、ラウンド数の伸びに対してアクティブＳボックスの数が増大せず、差分攻撃に対する強度がそれほど伸びないという問題を発生させる。

前述したように、差分解析（差分攻撃）においては、ある差分を持つ入力データ（平文）とその出力データ（暗号文）を多数設定してこの対応を解析することにより各ラウンド関数における適用鍵を解析する手法であり、この差分解析において、アクティブＳボックスの数を少なくできれば、解析が容易となり、解析プロセス数を削減できる。

上述の図６を参照した例において、右から左へ入力を行なうＦ関数、すなわち、第ｉラウンドと第ｉ＋２ラウンド、第ｉ＋４ラウンドのみをアクティブＳボックス算出処理対象ラウンドとしてみた場合、アクティブＳボックス数は、第ｉラウンド＝１、第ｉ＋２ラウンド＝０、第ｉ＋４ラウンド＝１の合計わずか２であり、左から右へ入力を行なうＦ関数、すなわち第ｉ＋1ラウンドおよび第ｉ＋３ラウンドではアクティブＳボックス数が８であるものの、同時差分キャンセルにより第ｉ＋５ラウンドでのアクティブＳボックス数が０となってしまうため、差分解析による各Ｓボックスの非線形変換処理の解析、および、Ｆ関数に対する入力ラウンド鍵の解析処理が比較的、容易となる。

図６を参照した例では、第１のＳボックス（Ｓ１）のみがアクティブＳボックスであるパターンの発生状態を提示したが、その他のＳボックス（Ｓ２〜Ｓ８）についても、差分解析の入力データの設定によって、各ＳボックスのみをアクティブＳボックスとした設定が可能であり、このような差分解析プロセスを実行することにより、各Ｓボックスの非線形変換処理の解析、さらにＦ関数に対して入力されるラウンド鍵の解析が可能となる。

図４および図６を参照して、３および５ラウンドの場合の同時差分キャンセルの発生例を説明したが、任意のラウンド数に一般化して同時差分キャンセルを定義すると以下のように定義することができる。図７を参照して、任意のラウンド数における同時差分キャンセルの定義について説明する。なお、図７は、フェイステル（Ｆｅｉｓｔｅｌ）構造の共通鍵ブロック暗号を実行するフェイステル（Ｆｅｉｓｔｅｌ）構造の１つおきのラウンド（ｉ，ｉ＋２，ｉ＋４，・・・，ｉ＋２ｊ）を示している。

「定義」
フェイステル（Ｆｅｉｓｔｅｌ）構造のラウンドｉでの入力差分の半分（ＰＬまたはＰＲ）が０（図７において、ΔＸｉ＝（００，００，００，００，００，００，００，００））であり、そこにｉ＋２ｊラウンド（ｊ＝０，１，２，...）のＦ関数の出力差分が排他的論理和部で演算されていく過程において、あるラウンドｉ＋２ｋにおいて、排他的論理和の結果が０（図７において、ΔＸｉ＋２ｊ＋１＝（００，００，００，００，００，００，００，００））になった場合を"同時差分キャンセル"と呼ぶ。

その時、ｉ，ｉ＋２，ｉ＋４，．．，ｉ＋２ｋラウンドのＦ関数の中に存在するアクティブＳボックス（Ａｃｔｉｖｅ Ｓ−ｂｏｘ）のことを"同時差分キャンセルを発生させたアクティブＳボックス"と呼ぶものとし、ベクトルＡの非ゼロの要素数をハミングウェイトｈｗ（Ａ）と定義すると、同時差分キャンセルを発生させるアクティブＳボックスの数ａは、以下の式として表せる。

前述の３ラウンド、５ラウンドでの例ではともに同時差分キャンセルを発生させたアクティブＳボックス数は２、すなわちａ＝２である。

前述したように、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつが暗号化関数全体でのアクティブＳボックスの最少数であり、アクティブＳボックス数の最少数が大きいほど差分攻撃に対する耐性が高いと判断される。

しかし、ＤＥＳアルゴリズムのように同じ線形変換行列をすべての段のＦ関数に用いる構成では、図４、図６を参照して説明したように、わずか２つのアクティブＳボックスにより同時差分キャンセルが発生してしまう可能性があった。そのような性質があるためラウンド数の伸びに対してアクティブＳボックスの最少数が十分に増大せず、差分攻撃に対する強度がそれほど伸びないという問題があった。

［２．本発明に基づく暗号処理アルゴリズム］
以下、少ないアクティブＳボックスに基づく同時差分キャンセルが起こらない、または、起こりにくい構造を実現して、差分攻撃に対する耐性を向上させた、すなわち、鍵解析の困難性を高め、安全性を向上させた本発明に係る共通鍵ブロック暗号処理アルゴリズムについて説明する。

本発明に係る暗号処理アルゴリズムの１つの特徴は、従来のＤＥＳアルゴリズムの如く各ラウンドのＦ関数に構成される線形変換部に共通の処理（変換行列）を適用した構成とせず、複数の異なるＭＤＳ（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ）行列を設定した構成としたことである。具体的には、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なるＭＤＳ行列を適用した線形変換処理を実行する構成を持つ。

本発明に係る暗号処理アルゴリズムは、ＭＤＳ（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ）行列の性質を利用し、少ないアクティブＳボックスに基づく同時差分キャンセルが起こらない、または起こりにくい構造を実現し、アクティブＳボックスの最小数を増大させ、差分攻撃に対してより強い共通鍵ブロック暗号処理である。

本発明の暗号処理アルゴリズムは、図１、２を参照して説明したＳＰＮ型のＦ関数を有するＦｅｉｓｔｅｌ構造と呼ばれる代表的な共通鍵ブロック暗号の構造、すなわち、非線形変換部および線形変換部を有するＳＰＮ型のＦ関数の複数ラウンドに渡る単純な繰り返しにより、平文を暗号文に変換する、あるいは暗号文を平文変換する構造を適用している。

例えば、平文の長さを２ｍｎビット（ただし、ｍ，ｎは共に整数）として、２ｍｎビットの平文を、ｍｎビットの２つのデータＰＬ（Plain-Left），ＰＲ(Plain-Right)に分割し、これを入力値として、各ラウンドにおいて、Ｆ関数を実行させるものであり、Ｆ関数は、図２を参照して説明したように、Ｓボックスからなる非線形変換部と、線形変換部を接続したＳＰＮ型を持つＦ関数である。

本発明の構成においては、Ｆ関数中の線形変換部において適用する線形変換処理のための行列として、複数の異なるＭＤＳ（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ）行列から選択された行列を各ラウンドのＦ関数の線形変換部において適用する行列として設定する。具体的には、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なるＭＤＳ行列を適用する。

ＭＤＳ行列について説明する。ＭＤＳ行列とは以下の（ａ），（ｂ）の性質を満たす行列をいう。
（ａ）正方行列である
（ｂ）行列に含まれるすべての部分行列（ｓｕｂｍａｔｒｉｘ）の行列式（ｄｅｔｅｒｍｉｎａｎｔ）が０でない、すなわち、ｄｅｔ（ｓｕｂｍａｔｒｉｘ）≠０

上記（ａ），（ｂ）の条件を満足する行列をＭＤＳ行列と呼ぶ。
共通鍵ブロック暗号の各ラウンドで実行するＦ関数に対する入出力ビット長がｍ×ｎ（ｍ，ｎ：整数）ビットであり、Ｆ関数内に構成される非線形変換部がｎビットの入出力を持つｍ個のＳボックスにより構成され、線形変換部がｎ次の既約多項式で定義される２の拡大体ＧＦ（２^ｎ）上の元を要素として持つｍ次の正方行列に基づく線形変換処理を実行する場合の、ＭＤＳ行列の一例を図８に示す。図８に示すＭＤＳ行列の例は、ｎ＝８，ｍ＝８のＭＤＳ行列の例である。

上記（ａ），（ｂ）を満足するＭＤＳ行列は、ベクトルＡの非ゼロの要素数をハミングウェイトｈｗ（Ａ）とし、Ｍをｍ次のＭＤＳ行列とし、ｘをＭＤＳ行列Ｍへの入力ベクトルとした場合、以下の不等式（式１）を満たすことになる。
ｈｗ（ｘ）＋ｈｗ（Ｍｘ）≧ｍ＋１‥‥‥‥‥‥（式１）

上記式（式１）は、ＭＤＳ行列（Ｍ）によって線形変換される入力データｘの非ゼロの要素数ｈｗ（ｘ）と、ＭＤＳ行列（Ｍ）によって線形変換された出力データＭｘの非ゼロの要素数ｈｗ（Ｍｘ）の総数が、ＭＤＳ行列の次数ｍより大となるということを意味している。

なお、ＭＤＳ行列という名はＭＤＳ−ｃｏｄｅ（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ Ｃｏｄｅ）の生成行列の標準形の右半分が上記条件を満足していることから名づけているものである。

１つの行列をすべてのＦ関数に組み込むという従来の構成でも線形変換行列にＭＤＳ行列を用いることで、ＭＤＳ行列でない行列を用いる場合に比べてアクティブＳボックス数の最少数を比較的高水準に保持することができるということは知られている。

本発明では、各ラウンドのＦ関数にはＭＤＳ行列の条件を満たす行列を利用し、さらにラウンドごとに異なる行列を設定する方法を提案する。具体的には、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なるＭＤＳ行列を適用する。

以下に、段数（ラウンド数）が２ｒ（ｒは整数）のＦｅｉｓｔｅｌ型共通鍵ブロック暗号において、差分攻撃に対する耐性をより高めた複数の構成例について説明する。

なお、以下の説明において、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成のｊ段目のＦ関数における線形変換部で適用する線形変換行列をＭＬＴｊとして表すものとする。

（線形変換行列ＭＬＴｊ設定例１）
線形変換行列ＭＬＴｊ設定例１は、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ個のＭＤＳ行列を生成して、偶数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列をすべて異なるＭＤＳ行列として設定するとともに、奇数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列もすべて異なるＭＤＳ行列として設定するものである。

本設定例を適用した構成例を図９に示す。図９は、段数（ラウンド数）が２ｒ＝１２、すなわちｒ＝６のＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成とした場合の、各ラウンドのＦ関数部の線形変換部に設定するＭＤＳ行列（Ｌ１，Ｌ２・・・Ｌ６）を示している。図中では明示していないが、各ラウンドには鍵スケジューリング部から入力される副鍵Ｋｉが入力されているものとする。

図９の構成は、２ｍｎビットの平文を、ｍｎビットの２つのデータＰＬ（Plain-Left），ＰＲ(Plain-Right)に分割し、これを入力値として、各ラウンドにおいて、Ｆ関数を実行させる構成であり、第１ラウンドのＦ関数３０１およびその他のラウンドのＦ関数も、すべて図２を参照して説明したように、Ｓボックスからなる非線形変換部と、線形変換部を接続したＳＰＮ型を持つＦ関数である。

図９において、各Ｆ関数内に示す記号Ｌｎは、ＭＤＳ行列３０２を示す。すなわちＬ１，Ｌ２・・・Ｌ６は、それぞれ異なる６種類のＭＤＳ行列を示し、各Ｆ関数の線形変部において線形変換処理に適用するＭＤＳ行列を示している。

線形変換行列ＭＬＴｊ設定例１の処理シーケンスについて、図１０を参照して説明する。

［ステップＳ１１］
ｒ個のＧＦ（２^ｎ）上のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｒを生成する。

ｒ個のＧＦ（２^ｎ）上のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｒの生成処理シーケンス（ＭＤＳ行列生成手法１）について、図１１を参照して説明する。

（ＭＤＳ行列生成手法１）
［ステップＳ１０１］
入力：必要なＭＤＳの個数ｘ，拡大次数：ｎ，行列のサイズ：ｍとして、
ＧＦ（２^ｎ）上で、ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘをランダムに生成する。
［ステップＳ１０２］
ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘに含まれるｘｍ個の列の任意のｍ個を取り出したときに、線形独立になっているかどうかをチェックする。チェックに通過したらステップＳ１０３に進む、そうでない場合はステップＳ１０１にもどる。
［ステップＳ１０３］
ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘを、ラウンド数２ｘのＦｅｉｓｔｅｌ型共通鍵ブロック暗号に適用するＭＤＳ行列として出力

以上のプロセスによって、ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘが生成される。なお、本例ではｘ＝ｒである。

図１０に戻り、線形変換行列ＭＬＴｊ設定例１の処理シーケンスについての説明を続ける。ステップＳ１１において、図１１を参照して説明したＭＤＳ行列の生成処理によってｒ個のＧＦ（２^ｎ）上のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｒが生成されると、次に、以下のＭＤＳ行列設定処理を実行する。
［ステップＳ１２］
２ｉ−１（１≦ｉ≦ｒ）段目の線形変換行列ＭＬＴ_２ｉ−１にＬ_ｉを設定する。
［ステップＳ１３］
２ｉ（１≦ｉ≦ｒ）段目の線形変換行列にＭＬＴ_２ｉにＭＬＴ_{２ｒ−２ｉ＋１}を設定する。

例えば、図９に示す１２段（ｒ＝６）の場合は、
ＭＬＴ１＝Ｌ１， ＭＬＴ２＝Ｌ６
ＭＬＴ３＝Ｌ２， ＭＬＴ４＝Ｌ５
ＭＬＴ５＝Ｌ３， ＭＬＴ６＝Ｌ４
ＭＬＴ７＝Ｌ４， ＭＬＴ８＝Ｌ３
ＭＬＴ９＝Ｌ５， ＭＬＴ１０＝Ｌ２
ＭＬＴ１１＝Ｌ６， ＭＬＴ１２＝Ｌ１
の設定となる。

すなわち、線形変換行列ＭＬＴｊ設定例１は、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ個のＭＤＳ行列を生成して、偶数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列をすべて異なるＭＤＳ行列として設定するとともに、奇数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列もすべて異なるＭＤＳ行列として設定するものである。また、偶数ラウンドのＭＤＳ行列と奇数ラウンドのＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証されている。

本構成により、
（ａ）各Ｆ関数の線形変換行列はＭＤＳであること、
（ｂ）暗号化関数内の奇数ラウンド内に含まれる線形変換行列の任意のｍ個の列ベクトルは独立であること、
（ｃ）偶数ラウンド内に含まれる線形変換行列の任意のｍ個の列ベクトルは独立であること、
これら（ａ）〜（ｃ）が保証されるため、ｍ個以下のアクティブＳボックスの寄与による同時差分キャンセルは発生しないことが保証される。よって暗号化関数全体のアクティブＳボックス数の最小値が増大する。

このように、本処理例によって、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最少数を大きくすることが可能となり、結果として、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。

（線形変換行列ＭＬＴｊ設定例２）
線形変換行列ＭＬＴｊ設定例２は、線形変換行列ＭＬＴｊ設定例１と同様、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ個のＭＤＳ行列を生成して、偶数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列をすべて異なるＭＤＳ行列として設定するとともに、奇数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列もすべて異なるＭＤＳ行列として設定するものであり、結果としては、線形変換行列ＭＬＴｊ設定例１と同様、図９に示すようなＭＤＳ行列（Ｌ１，Ｌ２・・・Ｌ６）設定構成となる。

本設定例２は、図１０を参照して説明した線形変換行列ＭＬＴｊ設定例１の実行シーケンス中、ステップＳ１１のＭＤＳ行列の生成手法として、設定例１とは異なる手法を適用した。

線形変換行列ＭＬＴｊ設定例１のＭＤＳ行列の生成手法は、先に説明したように、図１１の処理シーケンスに従った手法であったが、線形変換行列ＭＬＴｊ設定例２においては、図１２に示す従った処理シーケンスに従った手法（ＭＤＳ行列生成手法２）を適用する。ＭＤＳ行列生成手法２について、図１２を参照して説明する。

（ＭＤＳ行列生成手法２）
［ステップＳ２０１］
入力：必要なＭＤＳの個数ｘ，拡大次数：ｎ，行列のサイズ：ｍとして、
ＧＦ（２^ｎ）上で、ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘをランダムに生成する。
［ステップＳ２０２］
ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘに含まれるｘｍ個の列の任意のｍ個を取り出したときに、ＭＤＳ行列になっているかどうかをチェックする。チェックに通過したらステップＳ２０３に進む、そうでない場合はステップＳ２０１にもどる。
なお、ＭＤＳ行列とは、前述したように以下の性質を満たす行列をいう。
（ａ）正方行列である
（ｂ）行列に含まれるすべての部分行列（ｓｕｂｍａｔｒｉｘ）の行列式（ｄｅｔｅｒｍｉｎａｎｔ）が０でない、すなわち、ｄｅｔ（ｓｕｂｍａｔｒｉｘ）≠０
［ステップＳ２０３］
ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘを、ラウンド数２ｘのＦｅｉｓｔｅｌ型共通鍵ブロック暗号に適用するＭＤＳ行列として出力

以上のプロセスによって、ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘが生成される。なお、本例ではｘ＝ｒである。

線形変換行列ＭＬＴｊ設定例１におけるＭＤＳ行列生成処理においては、図１１の処理シーケンスにおいて説明したように、ステップＳ１０２において、ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘに含まれるｘｍ個の列の任意のｍ個を取り出したときの線形独立性を判定したが、この線形変換行列ＭＬＴｊ設定例２におけるＭＤＳ行列生成処理においては、ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘに含まれるｘｍ個の列の任意のｍ個を取り出したときＭＤＳ行列になっているかどうかをチェックする。すなわち、より厳しいチェックが実行されることになる。

この図１２に示す処理シーケンスに従ったＭＤＳ行列生成処理によって生成されたｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘが、先に説明した線形変換行列ＭＬＴｊ設定例１におけるＭＤＳ行列設定例と同様、
２ｉ−１（１≦ｉ≦ｒ）段目の線形変換行列ＭＬＴ_２ｉ−１にＬ_ｉを設定、
２ｉ（１≦ｉ≦ｒ）段目の線形変換行列にＭＬＴ_２ｉにＭＬＴ_{２ｒ−２ｉ＋１}を設定
して、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成が構築される。

結果としては、図９に示すように、１２段（ｒ＝６）の場合は、
ＭＬＴ１＝Ｌ１， ＭＬＴ２＝Ｌ６
ＭＬＴ３＝Ｌ２， ＭＬＴ４＝Ｌ５
ＭＬＴ５＝Ｌ３， ＭＬＴ６＝Ｌ４
ＭＬＴ７＝Ｌ４， ＭＬＴ８＝Ｌ３
ＭＬＴ９＝Ｌ５， ＭＬＴ１０＝Ｌ２
ＭＬＴ１１＝Ｌ６， ＭＬＴ１２＝Ｌ１
の設定となる。

すなわち、線形変換行列ＭＬＴｊ設定例２も、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ個のＭＤＳ行列を生成して、偶数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列をすべて異なるＭＤＳ行列として設定するとともに、奇数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列もすべて異なるＭＤＳ行列として設定するものである。ただし、線形変換行列ＭＬＴｊ設定例１と異なり、偶数段あるいは奇数段に設定される各ＭＤＳ行列は、ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘに含まれるｘｍ個の列の任意のｍ個を取り出したときＭＤＳ行列になっていることが保証されたものである。また、偶数ラウンドのＭＤＳ行列と奇数ラウンドのＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証されている。

本構成により、
（ａ）各Ｆ関数の線形変換行列はＭＤＳであること、
（ｂ）暗号化関数内の奇数ラウンド内に含まれる線形変換行列の任意のｍ個の列ベクトルはＭＤＳ行列であること、
（ｃ）偶数ラウンド内に含まれる線形変換行列の任意のｍ個の列ベクトルはＭＤＳ行列であること、
これら（ａ）〜（ｃ）が保証されるため、ｍ個以下のアクティブＳボックスの寄与による同時差分キャンセルは発生しないことが保証される。
さらに、
（ｄ）ＭＤＳの性質から、ａ個（ａ≦ｍ）のアクティブＳボックスの寄与によって得られる差分値における非ゼロの要素数はｍ＋１−ａ個以上になることが保証される。よって暗号化関数全体のアクティブＳボックス数の最小値が増大する。

このように、本処理例によって、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最少数を大きくすることが可能となり、結果として、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。

（線形変換行列ＭＬＴｊ設定例３）
線形変換行列ＭＬＴｊ設定例３は、線形変換行列ＭＬＴｊ設定例１，２と同様、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ個のＭＤＳ行列を生成して、偶数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列をすべて異なるＭＤＳ行列として設定するとともに、奇数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列もすべて異なるＭＤＳ行列として設定するものであり結果としては、線形変換行列ＭＬＴｊ設定例１と同様、図９に示すようなＭＤＳ行列（Ｌ１，Ｌ２・・・Ｌ６）設定構成となる。

本設定例２は、図１０を参照して説明した線形変換行列ＭＬＴｊ設定例１の実行シーケンス中、ステップＳ１１のＭＤＳ行列の生成手法として、設定例１，２とは異なる手法を適用した。

線形変換行列ＭＬＴｊ設定例３においては、図１３に示す従った処理シーケンスに従った手法（ＭＤＳ行列生成手法３）を適用する。ＭＤＳ行列生成手法３について、図１３を参照して説明する。

（ＭＤＳ行列生成手法３）
［ステップＳ３０１］
入力：必要なＭＤＳの個数ｘ，拡大次数：ｎ，行列のサイズ：ｍとして、
ＧＦ（２^ｎ）上で、１個のｘｍ次ＭＤＳ行列Ｍを生成する。
［ステップＳ３０２］
１個のｘｍ次ＭＤＳ行列Ｍからｍ本の行を任意に選択抽出し、ｍ行，ｘｍ列の行列Ｍ'を構成する。
［ステップＳ３０３］
ｍ行，ｘｍ列の行列Ｍ'に含まれるｘｍ本の列ベクトルを重複することなくｍ本の列ベクトルからなるｘ個のグループに任意に分割し、それぞれのグループに含まれる列ベクトルからｍ次の正方行列Ｌ１，Ｌ２，...，Ｌｘを、ラウンド数２ｘのＦｅｉｓｔｅｌ型共通鍵ブロック暗号に適用するＭＤＳ行列として出力

以上のプロセスによって、ｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘが生成される。なお、本例ではｘ＝ｒである。

ＭＤＳ行列生成手法３について、図１４を参照して、より具体的に説明する。
［ステップＳ３０１］
ＧＦ（２^ｎ）上で、１個のｘｍ次ＭＤＳ行列Ｍを生成する。図１４に示すように、ｘｍ×ｘｍのＭＤＳ行列Ｍを生成する。なお、このステップＳ３０１において生成する行列Ｍの次数はｘｍ次より大きいものでもよい。
［ステップＳ３０２］
図１４に示すように、ｘｍ次ＭＤＳ行列Ｍからｍ本の行を任意に選択抽出し、ｍ行，ｘｍ列の行列Ｍ'を構成する。なお、図に示す例では、連続するｍ本の行を選択抽出した例として示してあるが、ｍ次ＭＤＳ行列Ｍを構成する任意の離間した行をｍ本選択抽出して、ｍ行，ｘｍ列の行列Ｍ'を構成してもよい。
［ステップＳ３０３］
ｍ行，ｘｍ列の行列Ｍ'に含まれるｘｍ本の列ベクトルを重複することなくｍ本の列ベクトルからなるｘ個のグループに任意に分割し、それぞれのグループに含まれる列ベクトルからｍ次の正方行列Ｌ１，Ｌ２，...，Ｌｘを生成する。

図１３、図１４を参照して説明した処理シーケンスに従ったＭＤＳ行列生成処理によって生成されたｘ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｘが、先に説明した線形変換行列ＭＬＴｊ設定例１、２におけるＭＤＳ行列設定例と同様、
２ｉ−１（１≦ｉ≦ｒ）段目の線形変換行列ＭＬＴ_２ｉ−１にＬ_ｉを設定、
２ｉ（１≦ｉ≦ｒ）段目の線形変換行列にＭＬＴ_２ｉにＭＬＴ_{２ｒ−２ｉ＋１}を設定
して、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成が構築される。

結果としては、図９に示すように、１２段（ｒ＝６）の場合は、
ＭＬＴ１＝Ｌ１， ＭＬＴ２＝Ｌ６
ＭＬＴ３＝Ｌ２， ＭＬＴ４＝Ｌ５
ＭＬＴ５＝Ｌ３， ＭＬＴ６＝Ｌ４
ＭＬＴ７＝Ｌ４， ＭＬＴ８＝Ｌ３
ＭＬＴ９＝Ｌ５， ＭＬＴ１０＝Ｌ２
ＭＬＴ１１＝Ｌ６， ＭＬＴ１２＝Ｌ１
の設定となる。

すなわち、線形変換行列ＭＬＴｊ設定例３も、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ個のＭＤＳ行列を生成して、偶数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列をすべて異なるＭＤＳ行列として設定するとともに、奇数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列もすべて異なるＭＤＳ行列として設定するものである。また、偶数ラウンドのＭＤＳ行列と奇数ラウンドのＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証されている。

本構成により、
（ａ）各Ｆ関数の線形変換行列はＭＤＳであること、
（ｂ）暗号化関数内の奇数ラウンド内に含まれる線形変換行列の任意のｍ個の列ベクトルは独立であること、
（ｃ）偶数ラウンド内に含まれる線形変換行列の任意のｍ個の列ベクトルは独立であること、
これら（ａ）〜（ｃ）が保証されるため、ｍ個以下のアクティブＳボックスの寄与による同時差分キャンセルは発生しないことが保証される。
さらに、
（ｄ）ＭＤＳの性質から、ａ個（ａ≦ｍ）のアクティブＳボックスの寄与によって得られる差分値における非ゼロの要素数はｍ＋１−ａ個以上になることが保証される。よって暗号化関数全体のアクティブＳボックス数の最小値が増大する。

線形変換行列ＭＬＴｊ設定例３が特に効果を発揮するのは、ｍ，ｒ，が大きくなり、前述した処理例１，２の行列決定処理（方式１，２）にかかる時間的コストが莫大となり、現実的な時間内に行列を決定することが困難である場合である。そのような場合でも本処理例３のＭＤＳ行列生成手法ならば比較的短時間での行列生成処理が可能となる。

これは、ＭＤＳ行列生成手法３においては、大きなｍ，ｒに対しても現実的な時間で十分に処理可能な方式、例えばリードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号の生成行列の生成法を適用することが可能となるからである。

この線形変換行列ＭＬＴｊ設定例３においても、上述したように、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最少数を大きくすることが可能となり、結果として、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。

（線形変換行列ＭＬＴｊ設定例４）
上述した線形変換行列ＭＬＴｊ設定例１〜３においては、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ個のＭＤＳ行列を生成して、偶数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列をすべて異なるＭＤＳ行列として設定するとともに、奇数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列もすべて異なるＭＤＳ行列として設定したものであった。以下、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ個より少ないｑ個のＭＤＳ行列を生成して、上述した線形変換行列ＭＬＴｊ設定例１と同様の効果、すなわち、暗号化関数全体でのアクティブＳボックスの最少数を大きくすることを実現した構成例について説明する。

本設定例を適用した構成例を図１５に示す。図１５は、段数（ラウンド数）が２ｒ＝１２、すなわちｒ＝６のＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成とした場合、ｑ＝３、すなわち、１２段のラウンド数を持つＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成において３種類の異なるＭＤＳ行列を配置した構成例として、各ラウンドのＦ関数部の線形変換部に設定するＭＤＳ行列（Ｌ１，Ｌ２，Ｌ３）を示している。

図１５の構成は、２ｍｎビットの平文を、ｍｎビットの２つのデータＰＬ（Plain-Left），ＰＲ(Plain-Right)に分割し、これを入力値として、各ラウンドにおいて、Ｆ関数を実行させる構成であり、第１ラウンドのＦ関数４０１およびその他のラウンドのＦ関数も、すべて図２を参照して説明したように、Ｓボックスからなる非線形変換部と、線形変換部を接続したＳＰＮ型を持つＦ関数である。

図１５の設定例はｒ＝６，ｑ＝３であり、各Ｆ関数内に示す記号ＬｎはＭＤＳ行列４０２を示している。すなわち、Ｌ１，Ｌ２，Ｌ３は、それぞれ異なる３種類のＭＤＳ行列を示し、各Ｆ関数の線形変部において線形変換処理に適用するＭＤＳ行列を示している。

本処理例によれば、上述した線形変換行列ＭＬＴｊ設定例１〜３において必要としていた異なるＭＤＳ行列の数を削減した簡易な構成が実現される。

線形変換行列ＭＬＴｊ設定例４の処理シーケンスについて、図１６を参照して説明する。

［ステップＳ２１］
ラウンド数２ｒの半数ｒに対してｒより小さい数ｑ、すなわち、
ｑ＜ｒとなる数ｑを選択する。ただし、ｑは２以上の整数である。
［ステップＳ２２］
ｑ個のＧＦ（２^ｎ）上のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑを生成する

ｑ個のＧＦ（２^ｎ）上のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑの生成処理手法としては、ＭＤＳ行列生成手法１（図１１）を適用する。すなわち、ＧＦ（２^ｎ）上で、ｑ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑを生成し、生成したｑ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑに含まれるｑｍ個の列の任意のｍ個を取り出したときの線形独立性を判定して、各ラウンドのＦ関数部の線形変換部に設定するｑ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑとする。

ステップＳ２２において、ＭＤＳ行列生成手法１を適用したＭＤＳ行列の生成処理によってｑ個のＧＦ（２^ｎ）上のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが生成されると、次に、以下のＭＤＳ行列設定処理を実行する。
［ステップＳ２３］
２ｉ−１（１≦ｉ≦ｒ）段目の線形変換行列ＭＬＴ_２ｉ−１にＬ_{（ｉ−１ｍｏｄｑ）＋１}を設定する。
［ステップＳ２４］
２ｉ（１≦ｉ≦ｒ）段目の線形変換行列にＭＬＴ２_ｉにＭＬＴ_{２ｒ−２ｉ＋１}を設定する。

例えば、図１５に示す構成例、すなわち、１２段（ｒ＝６）でありｑ＝３とした場合は、
ＭＬＴ１＝Ｌ１， ＭＬＴ２＝Ｌ３
ＭＬＴ３＝Ｌ２， ＭＬＴ４＝Ｌ２
ＭＬＴ５＝Ｌ３， ＭＬＴ６＝Ｌ１
ＭＬＴ７＝Ｌ１， ＭＬＴ８＝Ｌ３
ＭＬＴ９＝Ｌ２， ＭＬＴ１０＝Ｌ２
ＭＬＴ１１＝Ｌ３， ＭＬＴ１２＝Ｌ１
の設定となる。

すなわち、線形変換行列ＭＬＴｊ設定例４においては、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒより少ないｑ個のＭＤＳ行列を生成して、偶数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列をｑ個の異なるＭＤＳ行列を順次設定するとともに、奇数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列についても、ｑ個の異なるＭＤＳ行列を順次設定する構成としたものである。また、偶数ラウンドのＭＤＳ行列と奇数ラウンドのＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証されている。

本構成により、
（ａ）各Ｆ関数の線形変換行列はＭＤＳであること、
が保証され、さらに、
（ｂ）暗号化関数内の奇数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが独立であること、
（ｃ）偶数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが独立であること、
これら（ａ）〜（ｃ）が保証されるため、複数段のラウンド数を持つＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成において、連続する２ｑ−１ラウンドにおいて、前述した線形変換行列ＭＬＴｊ設定例１に対応する効果が得られる。

すなわち、連続する２ｑ−１ラウンドにおいて、ｍ個以下のアクティブＳボックスの寄与による同時差分キャンセルは発生しないことが保証される。よって暗号化関数全体のアクティブＳボックス数の最小値が増大する。

このように、本処理例によって、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最少数を大きくすることが可能となり、結果として、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。

さらに、本処理例においては、暗号化関数に必要な行列の種類をｑ種類に減少させることができるためソフトウェアのコードサイズ、ハードウェアのゲート規模を減少させる効果がある。

（線形変換行列ＭＬＴｊ設定例５）
線形変換行列ＭＬＴｊ設定例５は、上述した線形変換行列ＭＬＴｊ設定例４と同様、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ個より少ないｑ個のＭＤＳ行列を生成して、上述した線形変換行列ＭＬＴｊ設定例２と同様の効果、すなわち、暗号化関数全体でのアクティブＳボックスの最少数を大きくすることを実現した構成例について説明する。

本設定例を適用した構成例は、設定例４と同様であり、例えばｒ＝６，ｑ＝３の場合、図１５に示すＭＤＳ行列（Ｌ１，Ｌ２，Ｌ３）設定となる。

本処理例は、図１６を参照して説明した線形変換行列ＭＬＴｊ設定例４の実行シーケンス中、ステップＳ２１のＭＤＳ行列の生成手法として、先に、図１２を参照して説明したＭＤＳ行列生成手法２を適用したものである。

すなわち、設定例４では、ＭＤＳ行列の生成において、ｑ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑに含まれるｑｍ個の列の任意のｍ個を取り出したときの線形独立性を判定したが、この線形変換行列ＭＬＴｊ設定例５では、ｑ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑに含まれるｑｍ個の列の任意のｍ個を取り出したときＭＤＳ行列になっているかどうかをチェックする。すなわち、より厳しいチェックが実行して、ｑ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑを生成する。

図１２に示す処理シーケンスに従ったＭＤＳ行列生成処理によって生成されたｑ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが、先に説明した線形変換行列ＭＬＴｊ設定例４におけるＭＤＳ行列設定例と同様の設定処理により設定される。すなわち、
２ｉ−１（１≦ｉ≦ｒ）段目の線形変換行列ＭＬＴ_２ｉ−１にＬ_{（ｉ−１ｍｏｄｑ）＋１}を設定し、
２ｉ（１≦ｉ≦ｒ）段目の線形変換行列にＭＬＴ_２ｉにＭＬＴ_{２ｒ−２ｉ＋１}を設定する。

この設定処理の結果として、例えば、図１５に示す構成例、すなわち、１２段（ｒ＝６）でありｑ＝３とした場合は、
ＭＬＴ１＝Ｌ１， ＭＬＴ２＝Ｌ３
ＭＬＴ３＝Ｌ２， ＭＬＴ４＝Ｌ２
ＭＬＴ５＝Ｌ３， ＭＬＴ６＝Ｌ１
ＭＬＴ７＝Ｌ１， ＭＬＴ８＝Ｌ３
ＭＬＴ９＝Ｌ２， ＭＬＴ１０＝Ｌ２
ＭＬＴ１１＝Ｌ３， ＭＬＴ１２＝Ｌ１
の設定となる。

すなわち、線形変換行列ＭＬＴｊ設定例５においても、線形変換行列ＭＬＴｊ設定例４と同様、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒより少ないｑ個のＭＤＳ行列を生成して、偶数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列をｑ個の異なるＭＤＳ行列を順次設定するとともに、奇数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列についても、ｑ個の異なるＭＤＳ行列を順次設定する構成としている。また、偶数ラウンドのＭＤＳ行列と奇数ラウンドのＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証されている。

本構成により、
（ａ）各Ｆ関数の線形変換行列はＭＤＳであること、
が保証され、さらに、
（ｂ）暗号化関数内の奇数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルがＭＤＳ行列であること、
（ｃ）偶数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルがＭＤＳ行列であること、
これら（ａ）〜（ｃ）が保証されるため、複数段のラウンド数を持つＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成において、連続する２ｑ−１ラウンドにおいて、前述した線形変換行列ＭＬＴｊ設定例２に対応する効果が得られる。

すなわち、連続する２ｑ−１ラウンドにおいて、ｍ個以下のアクティブＳボックスの寄与による同時差分キャンセルは発生しないことが保証され、さらに、
（ｄ）ＭＤＳの性質から、連続する２ｑ−１ラウンドにおいて、ａ個（ａ≦ｍ）のアクティブＳボックスの寄与によって得られる差分値における非ゼロの要素数はｍ＋１−ａ個以上になることが保証される。よって暗号化関数全体のアクティブＳボックス数の最小値が増大する。

このように、本処理例によって、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最少数を大きくすることが可能となり、結果として、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。

さらに、本処理例においては、暗号化関数に必要な行列の種類をｑ種類に減少させることができるためソフトウェアのコードサイズ、ハードウェアのゲート規模を減少させる効果がある。

（線形変換行列ＭＬＴｊ設定例６）
線形変換行列ＭＬＴｊ設定例６は、上述した線形変換行列ＭＬＴｊ設定例４、５と同様、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ個より少ないｑ個のＭＤＳ行列を生成して、上述した線形変換行列ＭＬＴｊ設定例３と同様の効果、すなわち、暗号化関数全体でのアクティブＳボックスの最少数を大きくすることを実現した構成例について説明する。

本設定例を適用した構成例は、設定例４、５と同様であり、例えばｒ＝６，ｑ＝３の場合、図１５に示すＭＤＳ行列（Ｌ１，Ｌ２，Ｌ３）設定となる。

本処理例は、図１６を参照して説明した線形変換行列ＭＬＴｊ設定例４の実行シーケンス中、ステップＳ２１のＭＤＳ行列の生成手法として、先に、図１３、図１４を参照して説明したＭＤＳ行列生成手法３を適用したものである。

すなわち、ＧＦ（２^ｎ）上で、１個のｑｍ次ＭＤＳ行列Ｍを生成し、１個のｑｍ次ＭＤＳ行列Ｍからｍ本の行を任意に選択抽出し、ｍ行，ｑｍ列の行列Ｍ'を構成し、その後、ｍ行，ｑｍ列の行列Ｍ'に含まれるｑｍ本の列ベクトルを重複することなくｍ本の列ベクトルからなるｑ個のグループに任意に分割し、それぞれのグループに含まれる列ベクトルからｍ次の正方行列Ｌ１，Ｌ２，...，Ｌｑを、Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号に適用するＭＤＳ行列として出力する。

図１３、図１４に示す処理シーケンスに従ったＭＤＳ行列生成処理によって生成されたｑ個のｍ次ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが、先に説明した線形変換行列ＭＬＴｊ設定例４におけるＭＤＳ行列設定例と同様設定される。すなわち、
２ｉ−１（１≦ｉ≦ｒ）段目の線形変換行列ＭＬＴ_２ｉ−１にＬ_{（ｉ−１ｍｏｄｑ）＋１}を設定し、
２ｉ（１≦ｉ≦ｒ）段目の線形変換行列にＭＬＴ_２ｉにＭＬＴ_{２ｒ−２ｉ＋１}を設定する。

この設定処理の結果として、例えば、図１５に示す構成例、すなわち、１２段（ｒ＝６）でありｑ＝３とした場合は、
ＭＬＴ１＝Ｌ１， ＭＬＴ２＝Ｌ３
ＭＬＴ３＝Ｌ２， ＭＬＴ４＝Ｌ２
ＭＬＴ５＝Ｌ３， ＭＬＴ６＝Ｌ１
ＭＬＴ７＝Ｌ１， ＭＬＴ８＝Ｌ３
ＭＬＴ９＝Ｌ２， ＭＬＴ１０＝Ｌ２
ＭＬＴ１１＝Ｌ３， ＭＬＴ１２＝Ｌ１
の設定となる。

すなわち、線形変換行列ＭＬＴｊ設定例６においても、線形変換行列ＭＬＴｊ設定例４、５と同様、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒより少ないｑ個のＭＤＳ行列を生成して、偶数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列をｑ個の異なるＭＤＳ行列を順次設定するとともに、奇数ラウンドのＦ関数のｒ個の線形変換部において適用する正方行列についても、ｑ個の異なるＭＤＳ行列を順次設定する構成としている。また、偶数ラウンドのＭＤＳ行列と奇数ラウンドのＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証されている。

本構成により、
（ａ）各Ｆ関数の線形変換行列はＭＤＳであること、
が保証され、さらに、
（ｂ）暗号化関数内の奇数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが独立であること、
（ｃ）偶数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが独立であること、
これら（ａ）〜（ｃ）が保証されるため、複数段のラウンド数を持つＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成において、連続する２ｑ−１ラウンドにおいて、前述した線形変換行列ＭＬＴｊ設定例３に対応する効果が得られる。
すなわち、連続する２ｑ−１ラウンドにおいて、ｍ個以下のアクティブＳボックスの寄与による同時差分キャンセルは発生しないことが保証され、さらに、
（ｄ）ＭＤＳの性質から、連続する２ｑ−１ラウンドにおいて、ａ個（ａ≦ｍ）のアクティブＳボックスの寄与によって得られる差分値における非ゼロの要素数はｍ＋１−ａ個以上になることが保証される。よって暗号化関数全体のアクティブＳボックス数の最小値が増大する。

このように、本処理例によって、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最少数を大きくすることが可能となり、結果として、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。

なお、線形変換行列ＭＬＴｊ設定例６は、先に説明した線形変換行列ＭＬＴｊ設定例３と同様、ｍ，ｒ，が大きくなり、行列生成手法１，２にかかる時間的コストが莫大となり、現実的な時間内に行列を決定することが困難である場合、比較的短時間での行列生成処理が可能となる。これは、前述したように、ＭＤＳ行列生成手法３においては、大きなｍ，ｒに対しても現実的な時間で十分に処理可能な方式、例えばリードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号の生成行列の生成法を適用することが可能となるからである。

本処理例においては、設定例４、５と同様、暗号化関数に必要な行列の種類をｑ種類に減少させることができるためソフトウェアのコードサイズ、ハードウェアのゲート規模を減少させる効果がある。

最後に、暗号処理を実行する暗号処理装置としてのＩＣモジュール６００の構成例を図１７に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図１７に示すＩＣモジュール６００は、これら様々な機器に構成することが可能である。

図１７に示すＣＰＵ(Central processing Unit)６０１は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ６０２は、ＣＰＵ６０１が実行するプログラム、あるいは演算パラメータとしての固定データを格納するＲＯＭ（Read-Only-Memory）、ＣＰＵ６０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるＲＡＭ（Random Access Memory）等からなる。また、メモリ６０２は暗号処理に必要な鍵データ等の格納領域として使用可能である。データ等の格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。

暗号処理部６０３は、例えば上述したＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理アルゴリズムに従った暗号処理、復号処理等を実行する。なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをＲＯＭに格納し、ＣＰＵ６０１がＲＯＭ格納プログラムを読み出して実行するように構成してもよい。

乱数発生器６０４は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。

送受信部６０５は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ＩＣモジュールとのデータ通信を実行し、ＩＣモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。

以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。

なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。

例えば、プログラムは記録媒体としてのハードディスクやＲＯＭ（Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)，ＭＯ(Magneto optical)ディスク，ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。

なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。

なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。

上述したように、本発明は、非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行するＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理において、複数ラウンド各々に対応するＦ関数の線形変換処理を、ＭＤＳ（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ）行列を適用した線形変換処理として実行するとともに、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なるＭＤＳ行列を適用した線形変換処理を実行する構成としたので、アクティブＳボックスの寄与による同時差分キャンセルの発生可能性が低減または解消することとなり、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最少数を大きくすることが可能となる。すなわち、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、暗号鍵等の解析困難性が高まることとなり、差分解析に対する耐性が高く、安全性の高い暗号処理が実現される。従って、鍵解析困難性を高め、安全性の要求される暗号処理実行装置において適用可能である。

Ｆｅｉｓｔｅｌ構造を持つ代表的な共通鍵ブロック暗号の構成を示す図である。 ラウンド関数部として設定されるＦ関数の構成について説明する図である。 線形変換部において、線形変換処理に適用する正方行列の例を示す図である。 ｍ＝８，ｎ＝８の１２８ｂｉｔブロック暗号における３段の同時差分キャンセルの様子を説明する図である。 Ｆ関数の線形変換部において、正方行列による線形変換が実行されて、Ｆ関数出力差分ΔＹｉを生成する具体例を説明する図である。 ｍ＝８，ｎ＝８の１２８ｂｉｔブロック暗号における５段の同時差分キャンセルの様子を説明する図である。 共通鍵ブロック暗号における任意段の同時差分キャンセルの定義を説明する図である。 ＭＤＳ行列の一例を示す図である。 本発明に係る共通鍵ブロック暗号処理アルゴリズムにおける各ラウンドのＦ関数の線形変換行列としてのＭＤＳ行列設定例を説明する図である。 本発明に係る共通鍵ブロック暗号処理アルゴリズムにおける各ラウンドのＦ関数の線形変換行列としてのＭＤＳ行列設定処理シーケンスを説明するフロー図である。 各ラウンドのＦ関数に設定する線形変換行列であるＭＤＳ行列の生成手法１を説明するフロー図である。 各ラウンドのＦ関数に設定する線形変換行列であるＭＤＳ行列の生成手法２を説明するフロー図である。 各ラウンドのＦ関数に設定する線形変換行列であるＭＤＳ行列の生成手法３を説明するフロー図である。 各ラウンドのＦ関数に設定する線形変換行列であるＭＤＳ行列の生成手法３の具体的手法を説明する図である。 本発明に係る共通鍵ブロック暗号処理アルゴリズムにおける各ラウンドのＦ関数の線形変換行列としてのＭＤＳ行列設定例を説明する図である。 本発明に係る共通鍵ブロック暗号処理アルゴリズムにおける各ラウンドのＦ関数の線形変換行列としてのＭＤＳ行列設定処理シーケンスを説明するフロー図である。 本発明にかかる暗号処理を実行する暗号処理装置としてのＩＣモジュールの構成例を示す図である。

符号の説明

１０１ 入力データＰ_Ｌ（Plain-Left）
１０２ 入力データＰ_Ｒ(Plain-Right)
１０３ ラウンド鍵
１０４ 排他的論理和部
１２０ Ｆ関数
１２１ Ｓボックス（Ｓ−ｂｏｘ）
１２２ 線形変換部
１２５ 正方行列
１３１，１３３ 排他的論理和部
１４１〜１４５ 排他的論理和部
３０１ Ｆ関数
３０２ ＭＤＳ行列
４０１ Ｆ関数
４０２ ＭＤＳ行列
６００ ＩＣモジュール
６０１ ＣＰＵ(Central processing Unit)
６０２ メモリ
６０３ 暗号処理部
６０４ 乱数発生器
６０５ 送受信部

Claims (26)

1. 入力情報を非線形変換し、第１非線形変換情報を出力する第１非線形変換部と、当該第１非線形変換情報を線形変換して第１線形変換情報を出力する第１線形変換部とを有する第１暗号処理部と、
   入力情報を非線形変換し、第２非線形変換情報を出力する第２非線形変換部と、当該第２非線形変換情報を線形変換して第２線形変換情報を出力する第２線形変換部とを有する第２暗号処理部と、
   前記第２暗号処理部からの出力と、前記第１暗号処理部からの出力とが入力される排他的論理和部を備え、
   前記第１非線形変換情報を第１列ベクトルで示すと共に前記第１線形変換情報を第２列ベクトルで示した場合に、当該第１列ベクトルを当該第２列ベクトルに変換する第１行列と、
   前記第２非線形変換情報を第３列ベクトルで示すと共に前記第２線形変換情報を第４列ベクトルで示した場合に、当該第３列ベクトルを当該第４列ベクトルに変換する第２行列とは、
   互いに異なる行列であることを特徴とする暗号処理装置。
2. 前記第１行列から選択した第１列ベクトルと、
   前記第２行列から選択した第２列ベクトルとは、
   いずれの列ベクトルを選択した場合であっても、互いに線形独立であることを特徴とする請求項１に記載の暗号処理装置。
3. 前記暗号処理装置は、
   前記排他論理和部における排他論理和結果を前記前記第１暗号処理部または前記第２暗号処理部に再度入力し、前記第１暗号処理部および前記第２暗号処理部における暗号処理を繰り返し実行する構成であることを特徴とする請求項１に記載の暗号処理装置。
4. 前記第１線形変換部および前記第２線形変換部は、ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理を実行する構成であり、
   前記第１線形変換部および前記第２線形変換部において線形変換に適用する前記第１行列と前記第２行列は、行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルが互いに線形独立となるｍ次行列であることを特徴とする請求項１に記載の暗号処理装置。
5. Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理装置であり、
   非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行する構成を有し、
   前記複数ラウンド各々に対応するＦ関数の線形変換部は、
   正方行列を適用した線形変換処理を実行する構成であり、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方行列を適用した線形変換処理を実行する構成であることを特徴とする暗号処理装置。
6. 前記Ｆ関数の線形変換部は、
   全ての偶数ラウンドおよび全ての奇数ラウンドにおいて異なる正方行列をそれぞれ適用した線形変換処理を実行する構成であることを特徴とする請求項５に記載の暗号処理装置。
7. 前記Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理のアルゴリズムは、ラウンド数Ｒの暗号処理アルゴリズムであり、
   前記Ｆ関数の線形変換部は、
   ｒ個の全ての偶数ラウンドおよびｒ個の全ての奇数ラウンドにおいてｒ種類の異なる正方行列を順次適用した線形変換処理を実行する構成であることを特徴とする請求項５に記載の暗号処理装置。
8. 前記Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理のアルゴリズムは、ラウンド数Ｒの暗号処理アルゴリズムであり、
   前記Ｆ関数の線形変換部は、
   ｒ個の全ての偶数ラウンドおよびｒ個の全ての奇数ラウンドにおいて２≦ｑ＜ｒのｑ種類の異なる正方行列を順次繰り返し適用した線形変換処理を実行する構成であることを特徴とする請求項５に記載の暗号処理装置。
9. 前記Ｆ関数の線形変換部は、ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理を実行する構成であり、
   前記Ｆ関数の線形変換部において適用する異なる複数の正方行列の各々は、
   前記複数の正方行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルによって構成する行列が線形独立である正方行列として設定したことを特徴とする請求項５に記載の暗号処理装置。
10. 前記Ｆ関数の線形変換部は、ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理を実行する構成であり、
    前記Ｆ関数の線形変換部において適用する異なる複数の正方行列の各々は、
    前記複数の正方行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルによって構成する行列も正方行列となる正方行列として設定したことを特徴とする請求項５に記載の暗号処理装置。
11. 前記Ｆ関数の線形変換部において適用する異なる複数の正方行列の各々は、
    前記異なる正方行列を構成する要素を全て含む正方行列Ｍから選択された行ベクトルによって構成される行列Ｍ'から抽出された列ベクトルによって構成される行列によって構成されていることを特徴とする請求項５に記載の暗号処理装置。
12. 前記Ｆ関数の線形変換部において適用する異なる複数の正方行列の各々は、
    リードソロモン符号生成行列に基づいて生成された正方行列であることを特徴とする請求項５に記載の暗号処理装置。
13. 暗号処理装置において暗号処理を実行する暗号処理方法であり、
    第１暗号処理部の第１非線形変換部において入力情報を非線形変換して第１非線形変換情報を出力し、第１暗号処理部の第１線形変換部において当該第１非線形変換情報を線形変換して第１線形変換情報を出力する第１暗号処理ステップと、
    第２暗号処理部の第２非線形変換部において入力情報を非線形変換して第２非線形変換情報を出力し、第２暗号処理部の第２線形変換部において当該第２非線形変換情報を線形変換して第２線形変換情報を出力する第２暗号処理ステップと、
    排他的論理和部が、前記第２暗号処理部からの出力と、前記第１暗号処理部からの出力とを入力して排他論理和処理を実行する排他的論理和ステップとを有し、
    前記第１暗号処理ステップの第１線形変換処理は、前記第１非線形変換情報を第１列ベクトルで示すと共に前記第１線形変換情報を第２列ベクトルで示した場合に、当該第１列ベクトルを当該第２列ベクトルに変換する第１行列を適用した第１線形変換処理実行ステップであり、
    前記第２暗号処理ステップの第２線形変換処理は、前記第２非線形変換情報を第３列ベクトルで示すと共に前記第２線形変換情報を第４列ベクトルで示した場合に、当該第３列ベクトルを当該第４列ベクトルに変換する第２行列を適用した第２線形変換処理実行ステップであり、
    前記第１線形変換処理実行ステップにおいて適用する前記第１行列と第２線形変換処理実行ステップにおいて適用する前記第２行列とは互いに異なる行列であることを特徴とする暗号処理方法。
14. 前記第１行列から選択した第１列ベクトルと、
    前記第２行列から選択した第２列ベクトルとは、
    いずれの列ベクトルを選択した場合であっても、互いに線形独立であることを特徴とする請求項１３に記載の暗号処理方法。
15. 前記暗号処理方法は、
    前記排他論理和ステップにおける排他論理和結果を前記前記第１暗号処理部または前記第２暗号処理部に再度入力し、前記第１暗号処理ステップおよび前記第２暗号処理ステップの暗号処理を繰り返し実行することを特徴とする請求項１３に記載の暗号処理方法。
16. 前記第１線形変換部および前記第２線形変換部における線形変換処理は、ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理を実行するステップであり、
    前記第１線形変換部および前記第２線形変換部において線形変換に適用する前記第１行列と前記第２行列は、行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルが互いに線形独立さなるｍ次行列であることを特徴とする請求項１３に記載の暗号処理方法。
17. 暗号処理装置においてＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理方法であり、
    データ変換部が、非線形変換処理および線形変換処理を実行するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行し、
    前記複数ラウンド各々に対応するＦ関数の線形変換処理は、
    正方行列を適用した線形変換処理を実行するとともに、
    少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方行列を適用した線形変換処理を実行することを特徴とする暗号処理方法。
18. 前記データ変換部が、前記複数ラウンド各々に対応するＦ関数の線形変換処理は、
    全ての偶数ラウンドおよび全ての奇数ラウンドにおいて異なる正方行列をそれぞれ適用した線形変換処理を実行することを特徴とする請求項１７に記載の暗号処理方法。
19. 前記暗号処理方法は、
    前記データ変換部が、ラウンド数ＲのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行し、
    前記複数ラウンド各々に対応するＦ関数の線形変換処理は、
    ｒ個の全ての偶数ラウンドおよびｒ個の全ての奇数ラウンドにおいてｒ種類の異なる正方行列を順次適用した線形変換処理を実行することを特徴とする請求項１７に記載の暗号処理方法。
20. 前記暗号処理方法は、
    前記データ変換部が、ラウンド数ＲのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行し、
    前記複数ラウンド各々に対応するＦ関数の線形変換処理は、
    ｒ個の全ての偶数ラウンドおよびｒ個の全ての奇数ラウンドにおいて２≦ｑ＜ｒのｑ種類の異なる正方行列を順次繰り返し適用した線形変換処理を実行することを特徴とする請求項１７に記載の暗号処理方法。
21. 前記データ変換部が実行する前記複数ラウンド各々に対応するＦ関数の線形変換処理は、
    ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理であり、
    前記複数ラウンド各々に対応するＦ関数の線形変換処理において適用する異なる複数の正方行列の各々は、該複数の正方行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルによって構成する行列が線形独立である正方行列であることを特徴とする請求項１７に記載の暗号処理方法。
22. 前記データ変換部が実行する前記複数ラウンド各々に対応するＦ関数の線形変換処理は、
    ｍ個の非線形変換部各々の出力するｎビット、総計ｍｎビットの入力に対する線形変換処理であり、
    前記複数ラウンド各々に対応するＦ関数の線形変換処理において適用する異なる複数の正方行列の各々は、前記複数の正方行列を構成する列ベクトルから任意に選択したｍ個の列ベクトルによって構成する行列も正方行列となる正方行列であることを特徴とする請求項１７に記載の暗号処理方法。
23. 前記データ変換部が実行する前記複数ラウンド各々に対応するＦ関数の線形変換処理において適用する異なる複数の正方行列の各々は、前記複数の正方行列を構成する要素を全て含む正方行列Ｍから選択された行ベクトルによって構成される行列Ｍ'から抽出された列ベクトルによって構成される行列によって構成されていることを特徴とする請求項１７に記載の暗号処理方法。
24. 前記データ変換部が、前記Ｆ関数の線形変換処理において適用する異なる複数の正方行列の各々は、
    リードソロモン符号生成行列に基づいて生成された正方行列であることを特徴とする請求項１７に記載の暗号処理方法。
25. 暗号処理装置において暗号処理を実行させるコンピュータ・プログラムであり、
    第１暗号処理部の第１非線形変換部に入力情報を非線形変換させて第１非線形変換情報を出力させ、第１暗号処理部の第１線形変換部に当該第１非線形変換情報を線形変換させて第１線形変換情報を出力させる第１暗号処理ステップと、
    第２暗号処理部の第２非線形変換部に入力情報を非線形変換させて第２非線形変換情報を出力させ、第２暗号処理部の第２線形変換部に当該第２非線形変換情報を線形変換させて第２線形変換情報を出力させる第２暗号処理ステップと、
    排他的論理和部に、前記第２暗号処理部からの出力と、前記第１暗号処理部からの出力とを入力して排他論理和処理を実行させる排他的論理和ステップとを実行させ、
    前記第１暗号処理ステップの第１線形変換処理は、前記第１非線形変換情報を第１列ベクトルで示すと共に前記第１線形変換情報を第２列ベクトルで示した場合に、当該第１列ベクトルを当該第２列ベクトルに変換する第１行列を適用した第１線形変換処理を実行させるステップであり、
    前記第２暗号処理ステップの第２線形変換処理は、前記第２非線形変換情報を第３列ベクトルで示すと共に前記第２線形変換情報を第４列ベクトルで示した場合に、当該第３列ベクトルを当該第４列ベクトルに変換する第２行列を適用した第２線形変換処理を実行させるステップであり、
    前記第１線形変換処理実行ステップにおいて適用する前記第１行列と第２線形変換処理実行ステップにおいて適用する前記第２行列とは互いに異なる行列として設定したことを特徴とするコンピュータ・プログラム。
26. 暗号処理装置においてＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行させるコンピュータ・プログラムであり、
    データ変換部に、非線形変換処理および線形変換処理を実行するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行させ、
    前記複数ラウンド各々に対応するＦ関数の線形変換処理は、
    正方行列を適用した線形変換処理を実行させる処理であり、
    少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方行列を適用した線形変換処理を実行させることを特徴とするコンピュータ・プログラム。

Images