(57)【要約】【課題】  解析困難性を高めた、安全性の高い暗号処理装置および方法を実現する。【解決手段】  非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行するＦｅｉｓｔｅｌ型共通鍵ブロック暗号において、各ラウンドに対応するＦ関数の線形変換処理を比較的緩やかな制限条件を満足する行列を適用して実行する。本構成により差分攻撃や線形攻撃に対する耐性が向上する。また、制限が比較的緩やかであのので利用できる行列候補が増加し、アクティブＳ−ｂｏｘ数を大きくできる。すなわち、暗号強度指標のひとつであるアクティブＳボックスの最小数を大きくすることが可能となり、攻撃に対する耐性が向上し安全性の高い暗号処理が実現される。【選択図】  図１７
2006301567.tif 000002
【特許請求の範囲】
【請求項１】
複数ビットの入出力を持つ複数の非線形変換層を並列に構成した非線形変換部と、
線形変換を施す線形変換層で構成した線形変換部とで構成されるＦｅｉｓｔｅｌ型暗号処理を備える暗号処理装置において、
前記線形変換部は、前記線形変換に適応する行列の制約条件に基づいて処理を施すことを特徴とする暗号処理装置。
【請求項２】
前記線形変換に適応する行列の制約条件は、
ｒ段各々に対応するＦ関数の線形変換部の満足する行列Ｍｉを適用した構成、すなわち、  ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＤ１＝ｍｉｎ｛Ｂ（Ｍｉ）｜１≦ｉ≦ｒ｝，
ＢＤ２＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２）｜１≦ｉ≦ｒ−２｝，
ただし、Ａ｜Ｂは行列Ａ，Ｂの連結により得られる行列、
とした場合において、
ＢＤ１，ＢＤ２のすべてが３以上になるような行列Ｍｉを適用した構成であることを特徴とする請求項１に記載の暗号処理装置。
【請求項３】
暗号処理装置であり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を持つｒ段からなるＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成を有し、
前記ｒ段各々に対応するＦ関数の線形変換部は下記条件を満足する行列Ｍｉを適用した構成、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＤ１＝ｍｉｎ｛Ｂ（Ｍｉ）｜１≦ｉ≦ｒ｝，
ＢＤ２＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２）｜１≦ｉ≦ｒ−２｝，
ＢＤ３＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２｜Ｍｉ＋４）｜１≦ｉ≦ｒ−４｝，
ただし、Ａ｜Ｂは行列Ａ，Ｂの連結により得られる行列、
とした場合において、
ＢＤ１，ＢＤ２，ＢＤ３のすべてが３以上になるような行列Ｍｉを適用した構成であることを特徴とする暗号処理装置。
【請求項４】
暗号処理装置であり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を持つｒ段からなるＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成を有し、
前記ｒ段各々に対応するＦ関数の線形変換部は下記条件を満足する行列Ｍｉを適用した構成、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＬ２＝ｍｉｎ｛Ｂ（ｔＭ−１ｉ｜ｔＭ−１ｉ＋２）｜１≦ｉ≦ｒ−２｝
ただし、ｔＭは行列の転置、
とした場合において、
ＢＬ２が３以上になるような行列Ｍｉを適用した構成であることを特徴とする暗号処理装置。
【請求項５】
Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理方法であり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数をｒ段、繰り返し実行するステップを有し、
前記ｒ段各々に対応するＦ関数の線形変換処理は下記条件を満足する行列Ｍｉを適用した線形変換処理、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＤ１＝ｍｉｎ｛Ｂ（Ｍｉ）｜１≦ｉ≦ｒ｝，
ＢＤ２＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２）｜１≦ｉ≦ｒ−２｝，
ＢＤ３＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２｜Ｍｉ＋４）｜１≦ｉ≦ｒ−４｝，
ただし、Ａ｜Ｂは行列Ａ，Ｂの連結により得られる行列、
とした場合において、
ＢＤ１，ＢＤ２，ＢＤ３のすべてが３以上になるような行列Ｍｉを適用した線形変換処理によって実行することを特徴とする暗号処理方法。
【請求項６】
Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理方法であり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数をｒ段、繰り返し実行するステップを有し、
前記ｒ段各々に対応するＦ関数の線形変換部は下記条件を満足する行列Ｍｉを適用した線形変換処理、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＬ２＝ｍｉｎ｛Ｂ（ｔＭ−１ｉ｜ｔＭ−１ｉ＋２）｜１≦ｉ≦ｒ−２｝
ただし、ｔＭは行列の転置、
とした場合において、
ＢＬ２が３以上になるような行列Ｍｉを適用した線形変換処理によって実行することを特徴とする暗号処理方法。
【請求項７】
Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理をコンピュータ上において実行するコンピュータ・プログラムであり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数をｒ段、繰り返し実行するステップを有し、
前記ｒ段各々に対応するＦ関数の線形変換処理は下記条件を満足する行列Ｍｉを適用した線形変換処理、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＤ１＝ｍｉｎ｛Ｂ（Ｍｉ）｜１≦ｉ≦ｒ｝，
ＢＤ２＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２）｜１≦ｉ≦ｒ−２｝，
ＢＤ３＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２｜Ｍｉ＋４）｜１≦ｉ≦ｒ−４｝，
ただし、Ａ｜Ｂは行列Ａ，Ｂの連結により得られる行列、
とした場合において、
ＢＤ１，ＢＤ２，ＢＤ３のすべてが３以上になるような行列Ｍｉを適用した線形変換処理によって実行することを特徴とするコンピュータ・プログラム。
【請求項８】
Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理をコンピュータ上において実行するコンピュータ・プログラムであり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数をｒ段、繰り返し実行するステップを有し、
前記ｒ段各々に対応するＦ関数の線形変換部は下記条件を満足する行列Ｍｉを適用した線形変換処理、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＬ２＝ｍｉｎ｛Ｂ（ｔＭ−１ｉ｜ｔＭ−１ｉ＋２）｜１≦ｉ≦ｒ−２｝
ただし、ｔＭは行列の転置、
とした場合において、
ＢＬ２が３以上になるような行列Ｍｉを適用した線形変換処理によって実行することを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムに関する。さらに詳細には、暗号解析処理、攻撃処理として知られる線形解析、差分解析に対する耐性を向上させた暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【０００２】
昨今、ネットワーク通信、電子商取引の発展に伴い、通信におけるセキュリティ確保が重要な問題となっている。セキュリティ確保の１つの方法が暗号技術であり、現在、様々な暗号化手法を用いた通信が実際に行なわれている。
【０００３】
例えばＩＣカード等の小型の装置中に暗号処理モジュールを埋め込み、ＩＣカードと、データ読み取り書き込み装置としてのリーダライタとの間でデータ送受信を行ない、認証処理、あるいは送受信データの暗号化、復号を行なうシステムが実用化されている。
【０００４】
暗号処理アルゴリズムには様々なものがあるが、大きく分類すると、暗号化鍵と復号鍵を異なる鍵、例えば公開鍵と秘密鍵として設定する公開鍵暗号方式と、暗号化鍵と復号鍵を共通の鍵として設定する共通鍵暗号方式とに分類される。
【０００５】
共通鍵暗号方式にも様々なアルゴリズムがあるが、その１つに共通鍵をベースとして複数の鍵を生成して、生成した複数の鍵を用いてブロック単位（６４ビット，１２８ビットなど）のデータ変換処理を繰り返し実行する方式がある。このような鍵生成方式とデータ変換処理を適用したアルゴリズムの代表的なものが共通鍵ブロック暗号方式である。
【０００６】
代表的な共通鍵ブロック暗号のアルゴリズムとしては、例えば米国標準暗号としてのＤＥＳ（Data Encryption Standard）アルゴリズムがあり、様々な分野において広く用いられている。
【０００７】
ＤＥＳに代表される共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を実行するラウンド関数部と、ラウンド関数（Ｆ関数）部の各ラウンドで適用する鍵を生成する鍵スケジュール部とに分けることができる。ラウンド関数部の各ラウンドで適用するラウンド鍵（副鍵）は、１つのマスター鍵（主鍵）に基づいて、鍵スケジュール部に入力されて生成され、各ラウンド関数部で適用される。
【０００８】
しかし、このような共通鍵暗号処理においては、暗号解析による鍵の漏洩が問題となっている。暗号解析または攻撃手法の代表的な手法として、ある差分を持つ入力データ（平文）とその出力データ（暗号文）を多数解析することにより各ラウンド関数における適用鍵を解析する差分解析（差分解読法または差分攻撃とも呼ばれる）や、平文と対応暗号文に基づく解析を行う線形解析（線形解読法または線形攻撃とも呼ばれる）が知られている。
【０００９】
暗号解析による鍵の解析が容易であるということは、その暗号処理の安全性が低いということになる。従来のＤＥＳアルゴリズムにおいては、ラウンド関数（Ｆ関数）部の線形変換部において適用する処理（変換行列）が、各段のラウンドにおいて等しいものであったため解析が行いやすく、結果として鍵の解析の容易性を招いているという問題がある。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、上記問題点に鑑みてなされたものであり、線形解析や差分解析に対する耐性の高い共通鍵ブロック暗号アルゴリズムを実現する暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の第１の側面は、
複数ビットの入出力を持つ複数の非線形変換層を並列に構成した非線形変換部と、
線形変換を施す線形変換層で構成した線形変換部とで構成されるＦｅｉｓｔｅｌ型暗号処理を備える暗号処理装置において、
前記線形変換部は、前記線形変換に適応する行列の制約条件に基づいて処理を施すことを特徴とする暗号処理装置にある。
【００１２】
さらに、本発明の暗号処理装置の一実施態様において、前記線形変換に適応する行列の制約条件は、ｒ段各々に対応するＦ関数の線形変換部の満足する行列Ｍｉを適用した構成、すなわち、  ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＤ１＝ｍｉｎ｛Ｂ（Ｍｉ）｜１≦ｉ≦ｒ｝，
ＢＤ２＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２）｜１≦ｉ≦ｒ−２｝，
ただし、Ａ｜Ｂは行列Ａ，Ｂの連結により得られる行列、
とした場合において、
ＢＤ１，ＢＤ２のすべてが３以上になるような行列Ｍｉを適用した構成であることを特徴とする。
【００１３】
さらに、本発明の第２の側面は、
暗号処理装置であり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を持つｒ段からなるＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成を有し、
前記ｒ段各々に対応するＦ関数の線形変換部は下記条件を満足する行列Ｍｉを適用した構成、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＤ１＝ｍｉｎ｛Ｂ（Ｍｉ）｜１≦ｉ≦ｒ｝，
ＢＤ２＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２）｜１≦ｉ≦ｒ−２｝，
ＢＤ３＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２｜Ｍｉ＋４）｜１≦ｉ≦ｒ−４｝，
ただし、Ａ｜Ｂは行列Ａ，Ｂの連結により得られる行列、
とした場合において、
ＢＤ１，ＢＤ２，ＢＤ３のすべてが３以上になるような行列Ｍｉを適用した構成であることを特徴とする暗号処理装置にある。
【００１４】
さらに、本発明の第３の側面は、
暗号処理装置であり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を持つｒ段からなるＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成を有し、
前記ｒ段各々に対応するＦ関数の線形変換部は下記条件を満足する行列Ｍｉを適用した構成、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＬ２＝ｍｉｎ｛Ｂ（ｔＭ−１ｉ｜ｔＭ−１ｉ＋２）｜１≦ｉ≦ｒ−２｝
ただし、ｔＭは行列の転置、
とした場合において、
ＢＬ２が３以上になるような行列Ｍｉを適用した構成であることを特徴とする暗号処理装置にある。
【００１５】
さらに、本発明の第４の側面は、
Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理方法であり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数をｒ段、繰り返し実行するステップを有し、
前記ｒ段各々に対応するＦ関数の線形変換処理は下記条件を満足する行列Ｍｉを適用した線形変換処理、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＤ１＝ｍｉｎ｛Ｂ（Ｍｉ）｜１≦ｉ≦ｒ｝，
ＢＤ２＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２）｜１≦ｉ≦ｒ−２｝，
ＢＤ３＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２｜Ｍｉ＋４）｜１≦ｉ≦ｒ−４｝，
ただし、Ａ｜Ｂは行列Ａ，Ｂの連結により得られる行列、
とした場合において、
ＢＤ１，ＢＤ２，ＢＤ３のすべてが３以上になるような行列Ｍｉを適用した線形変換処理によって実行することを特徴とする暗号処理方法にある。
【００１６】
さらに、本発明の第５の側面は、
Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理方法であり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数をｒ段、繰り返し実行するステップを有し、
前記ｒ段各々に対応するＦ関数の線形変換部は下記条件を満足する行列Ｍｉを適用した線形変換処理、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＬ２＝ｍｉｎ｛Ｂ（ｔＭ−１ｉ｜ｔＭ−１ｉ＋２）｜１≦ｉ≦ｒ−２｝
ただし、ｔＭは行列の転置、
とした場合において、
ＢＬ２が３以上になるような行列Ｍｉを適用した線形変換処理によって実行することを特徴とする暗号処理方法にある。
【００１７】
さらに、本発明の第６の側面は、
Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理をコンピュータ上において実行するコンピュータ・プログラムであり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数をｒ段、繰り返し実行するステップを有し、
前記ｒ段各々に対応するＦ関数の線形変換処理は下記条件を満足する行列Ｍｉを適用した線形変換処理、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＤ１＝ｍｉｎ｛Ｂ（Ｍｉ）｜１≦ｉ≦ｒ｝，
ＢＤ２＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２）｜１≦ｉ≦ｒ−２｝，
ＢＤ３＝ｍｉｎ｛Ｂ（Ｍｉ｜Ｍｉ＋２｜Ｍｉ＋４）｜１≦ｉ≦ｒ−４｝，
ただし、Ａ｜Ｂは行列Ａ，Ｂの連結により得られる行列、
とした場合において、
ＢＤ１，ＢＤ２，ＢＤ３のすべてが３以上になるような行列Ｍｉを適用した線形変換処理によって実行することを特徴とするコンピュータ・プログラムにある。
【００１８】
さらに、本発明の第７の側面は、
Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理をコンピュータ上において実行するコンピュータ・プログラムであり、
非線形変換部および線形変換部を有するＳＰＮ型のＦ関数をｒ段、繰り返し実行するステップを有し、
前記ｒ段各々に対応するＦ関数の線形変換部は下記条件を満足する行列Ｍｉを適用した線形変換処理、すなわち、
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像θ：｛０，１｝ｎａ→｛０，１｝ｎｂに対して、分岐数Ｂ（θ）を、
分岐数Ｂ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝、
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値、
ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときにｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数、
とし、分岐数Ｂ（θ）がｂ＋１である写像θを最適拡散変換と定義し、
さらに、行列Ｍの分岐数をＢ（Ｍ）と表したとき、
ＢＬ２＝ｍｉｎ｛Ｂ（ｔＭ−１ｉ｜ｔＭ−１ｉ＋２）｜１≦ｉ≦ｒ−２｝
ただし、ｔＭは行列の転置、
とした場合において、
ＢＬ２が３以上になるような行列Ｍｉを適用した線形変換処理によって実行することを特徴とするコンピュータ・プログラムにある。
【００１９】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００２０】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００２１】
本発明の構成によれば、非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行するＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理において、複数ラウンド各々に対応するＦ関数の線形変換処理を、比較的緩やかな制限によって特定される行列を適用して実行する構成により、共通鍵ブロック暗号における差分攻撃や線形攻撃に対する耐性が向上する。また、制限が比較的緩やかであり、利用できる行列の候補が増加するとともに、アクティブＳ−ｂｏｘ数を十分大きく確保することが可能となる。すなわち、共通鍵ブロック暗号における攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最小数を大きくすることが可能となり、線形攻撃や、差分攻撃に対して耐性が向上し、より安全性の高い暗号処理が実現される。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムの詳細について説明する。なお、説明は、以下の項目順に行う。
１．共通鍵ブロック暗号アルゴリズムにおける差分解析処理
２．共通鍵ブロック暗号アルゴリズムにおける線形解析処理
３．耐性を向上させた暗号処理アルゴリズム構成例
（３−ａ）差分攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例
（３−ｂ）線形攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例
（３−ｃ）差分攻撃および線形攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例
４．本発明に係る暗号処理アルゴリズム
（４ａ）構成例１
（４ａ．１）構成例１における差分攻撃に対する耐性の向上
（４ａ．２）構成例１における線形攻撃に対する耐性の向上
（４ｂ）構成例１
（４ｂ．１）構成例２における差分攻撃に対する耐性の向上
（４ｂ．２）構成例２における線形攻撃に対する耐性の向上
【００２３】
［１．共通鍵ブロック暗号アルゴリズムにおける差分解析処理］
まず、ＤＥＳ（Data Encryption Standard）暗号処理に代表される共通鍵ブロック暗号アルゴリズムにおける差分解析処理の概要について、一般化した共通鍵ブロック暗号モデルを用いて説明する。
【００２４】
共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を実行するラウンド関数部と、ラウンド関数部の各ラウンドで適用する鍵を生成する鍵スケジュール部とに分けることができる。ラウンド関数部の各ラウンドで適用する鍵（副鍵）は、１つのマスター鍵（主鍵）に基づいて、鍵スケジュール部に入力されて生成され、各ラウンド関数部で適用される。この共通鍵暗号方式の代表的な方式に米国連邦標準暗号方式としてのＤＥＳ（Data Encryption Standard）がある。
【００２５】
Ｆｅｉｓｔｅｌ構造と呼ばれる代表的な共通鍵ブロック暗号の構造について、図１を参照して説明する。
【００２６】
Ｆｅｉｓｔｅｌ構造は、変換関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。平文の長さを２ｍｎビットとする。ただし、ｍ，ｎは共に整数である。初めに、２ｍｎビットの平文を、ｍｎビットの２つの入力データＰＬ（Plain-Left）１０１，ＰＲ(Plain-Right)１０２に分割し、これを入力値とする。
【００２７】
Ｆｅｉｓｔｅｌ構造はラウンド関数とよばれる基本構造の繰り返しで表現され、各ラウンドに含まれるデータ変換関数はＦ関数１２０と呼ばれる。図１の構成では、Ｆ関数（ラウンド関数）１２０がｒ段繰り返された構成例を示している。
【００２８】
例えば第１番目のラウンドでは、ｍｎビットの入力データＸと、鍵生成部（図示せず）から入力されるｍｎビットのラウンド鍵Ｋ１１０３がＦ関数１２０に入力され、Ｆ関数１２０におけるデータ変換処理の後にｍｎビットのデータＹを出力する。出力はもう片方の前段からの入力データ（第１段の場合は入力データＰＬ）と排他的論理和部１０４において、排他的論理和演算がなされ、ｍｎビットの演算結果が次のラウンド関数へと出力される。この処理、すなわちＦ関数を定められたラウンド数（ｒ）だけ繰り返し適用して暗号化処理が完了し、暗号文の分割データＣＬ（Cipher-Left）、ＣＲ（Cipher-Right）が出力される。以上の構成より、Ｆｅｉｓｔｅｌ構造の復号処理はラウンド鍵を挿入する順序を逆にするだけでよく、逆関数を構成する必要がないことが導かれる。
【００２９】
各ラウンドの関数として設定されるＦ関数１２０の構成について、図２を参照して説明する。図２（ａ）は、１つのラウンドにおけるＦ関数１２０に対する入力および出力を示す図であり、図２（ｂ）は、Ｆ関数１２０の構成の詳細を示す図である。Ｆ関数１２０は、図２（ｂ）に示すように、非線形変換層と線形変換層を接続したいわゆるＳＰＮ型の構成を有する。
【００３０】
ＳＰＮ型のＦ関数１２０は、図２（ｂ）に示すように、非線形変換処理を実行する複数のＳボックス（Ｓ−ｂｏｘ）１２１を有する。ラウンド関数部の前段からのｍｎビットの入力値Ｘは、鍵スケジュール部から入力されるラウンド鍵Ｋｉと排他的論理和が実行され、その出力がｎビットずつ非線形変換処理を実行する複数（ｍ個）のＳボックス１２１に入力される。各Ｓボックスでは、例えば変換テーブルを適用した非線形変換処理が実行される。
【００３１】
Ｓボックス１２１からの出力データであるｍｎビットの出力値Ｚは、線形変換処理を実行する線形変換部１２２に入力されて、例えばビット位置の入れ替え処理などの線形変換処理が実行され、ｍｎビットの出力値Ｙを出力する。この出力値Ｙが前段からの入力データと排他的論理和され、次のラウンドのＦ関数の入力値とされる。
【００３２】
図２に示すＦ関数１２０は、入出力ビット長がｍ×ｎ（ｍ，ｎ：整数）ビットであり、非線形変換層はｎビットの入出力を持つ非線形変換層としてのＳボックス１２１は、ｍ個並列にならんだ構成を有し、線形変換層としての線形変換部１２２はｎ次の既約多項式で定義される２の拡大体ＧＦ（２ｎ）上の元を要素として持つｍ次の正方行列に基づく線形変換処理を実行する。
【００３３】
線形変換部１２２における線形変換処理に適用する正方行列の例を図３に示す。図３に示す正方行列１２５は、ｎ＝８，ｍ＝８の場合の例である。非線形変換部（Ｓボックス１２１）から出力されたｍ個のｎビットデータＺ［１］，Ｚ［２］，...，Ｚ［ｍ］に対してあらかじめ定められた正方行列１２５を適用した演算により線形変換が施され、Ｆ関数（ラウンド関数）出力としての、Ｙ［１］，Ｙ［２］，...，Ｙ［ｍ］が決定される。ただし、このとき各データの行列の要素に対する線形演算はあらかじめ定められた２の拡大体ＧＦ（２ｎ）上で行われる。
【００３４】
これまでのＦｅｉｓｔｅｌ型暗号では、すべての段のＦ関数に同じ線形変換層を用いているため、差分の伝播時に同時に複数の差分がキャンセルしてしまうという性質が存在した。背景技術の欄において説明したように、暗号解析手法の代表的な手法として、ある差分を持つ入力データ（平文）とその出力データ（暗号文）を多数解析することにより各ラウンド関数における適用鍵を解析する差分解析（あるいは差分解読法）が知られており、従来のＤＥＳ暗号アルゴリズム等の共通鍵ブロック暗号においては、Ｆ関数１２０部の線形変換部１２２において適用する処理（変換行列）を、各段のラウンドにおいて等しいものに設定しているため、差分解析が行いやすく、結果として鍵の解析の容易性を招いている。
【００３５】
差分の伝播時に、同時に複数の差分がキャンセルする例について、図４を参照して説明する。なお、本明細書においては、差分を表す場合にはΔ（デルタ）記号をつけて表す。
【００３６】
図４はｍ＝８，ｎ＝８の１２８ｂｉｔブロック暗号における３段の同時差分キャンセルの様子を説明する図である。ただし、図中では６４ｂｉｔのデータをバイト単位で区切ってベクトルとして表現し、それぞれの要素を１６進数で表記するものとする。
【００３７】
３段構成を持つＦ関数での同時差分キャンセルは、例えば以下のデータ状態１〜４の設定メカニズムに基づいて発生する。以下に説明するメカニズムの発生するデータ状態は、多数の差分入力データを設定することで発生させることができるデータ状態であり、いわゆる差分解析における鍵（ラウンド鍵）の解析において発生し得る。
【００３８】
（状態１）
ｉラウンドへの入力差分の左半分は、すべてゼロである入力差分（ΔＸｉ−１＝（００，００，００，００，００，００，００，００））であり、右半分の入力差分がただひとつのＳ−ｂｏｘへの入力を除いてゼロである入力差分（ΔＸｉ＝（３４，００，００，００，００，００，００，００））であるとする。このデータ状態は、多数の差分入力データを設定することで、ｉラウンドにおいて、このようなデータ状態を得ることができるということである。
【００３９】
なお、ΔＸｉ＝（３４，００，００，００，００，００，００，００）の８つの各要素は、Ｆ関数中に構成されるｍ個（ｍ＝８）のＳボックス各々に対する入力差分に対応する。差分（３４）が第１Ｓボックス（図４中の（Ｓ１））に入力され、（００）が、第２〜８Ｓボックスに対する入力差分である。
【００４０】
なおゼロ（００）の入力差分を持つＳボックスの出力差分はゼロ（００）であり、差分データに関する限り、ゼロ（００）の入力差分を持つＳボックスは、何の作用も行なっていないものであり、アクティブでないすなわち非アクティブＳボックスと呼ばれる。一方、非ゼロの入力差分（図４の例では差分：３４）を持つＳボックスは、非ゼロの入力差分に対応した非線形変換結果を出力差分として発生させるので、アクティブＳボックス（Ａｃｔｉｖｅ  Ｓ−ｂｏｘ）と呼ばれる。
【００４１】
図４の例では、非ゼロの入力差分（３４）を入力する１つのアクティブＳボックス（Ｓ１）の出力差分（ｂ７）を発生させており、その他の非アクティブＳボックスＳ２〜Ｓ８はゼロの入力差分（００）に基づいて出力差分（００）を発生させ、線形変換部の差分入力としている。
【００４２】
（状態２）
ｉラウンドへの非ゼロの入力差分（図４の例では差分：３４）を持つＳボックス（以下、アクティブＳボックス（Ａｃｔｉｖｅ  Ｓ−ｂｏｘ）と呼ぶ）からの出力差分は線形変換層で拡散されたのちＦ関数から出力（出力値＝ΔＹｉ）され、そのまま次のラウンドへの入力差分ΔＸｉ＋１となる。
【００４３】
図４の例における線形変換は、各ラウンドのＦ関数において共通する例えば図５に示すある特定の正方行列１２５による線形変換が実行されｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）を出力する。図５に示す線形変換構成から理解されるように、出力差分ΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）は、１つのアクティブＳボックス（Ｓ１）からの出力要素Ｚ［１］＝ｂ７にのみ依存した値として決定される。
【００４４】
このｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）は、図４に示す排他的論理和部１３１において、すべてゼロである入力差分（ΔＸｉ−１＝（００，００，００，００，００，００，００，００）と排他的論理和（ＸＯＲ）演算が実行され、演算結果が、次のラウンド（ｉ＋１）への入力差分ΔＸｉ＋１となる。
【００４５】
ｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、すべてゼロである入力差分ΔＸｉ−１＝（００，００，００，００，００，００，００，００）との排他的論理和（ＸＯＲ）結果は、ΔＹｉであるので、次のラウンド（ｉ＋１）への入力差分ΔＸｉ＋１＝ΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）となる。      
【００４６】
（状態３）
ｉ＋１ラウンドのＦ関数からの出力差分ΔＹｉ＋１が、ｉラウンドでのＡｃｔｉｖｅ  Ｓ−ｂｏｘの位置にのみ非ゼロ値をもつ。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。
【００４７】
すなわち、ΔＹｉ＋１＝（ａｄ，００，００，００，００，００，００，００）であり、ｉラウンドと同様、非ゼロの差分値（図４の例では差分：３４）を持つＳ−ｂｏｘの位置（第１Ｓボックス（Ｓ１））にのみ非ゼロ値をもつ。なお、明らかにａｄ≠００である。
【００４８】
（状態４）
ｉ＋２ラウンドのアクティブＳボックス（Ａｃｔｉｖｅ  Ｓ−ｂｏｘ）（Ｓ１）の出力差分がｉラウンドでのアクティブＳボックス（Ａｃｔｉｖｅ  Ｓ−ｂｏｘ）（Ｓ１）の出力差分と一致した場合、すなわち、図４に示すようにｉ＋２ラウンドのアクティブＳボックス（（Ｓ１）の出力差分がｂ７となり、ｉラウンドでのアクティブＳボックス（Ｓ１）の出力差分（ｂ７）と一致する。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。
【００４９】
このデータ状態が発生すると、ｉ＋２ラウンドのＦ関数の出力差分ΔＹｉ＋２＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）が、２つ前のラウンドであるｉラウンドのＦ関数の出力差分ΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と一致することになる。
【００５０】
この結果、排他的論理和部１３３では、
ΔＸｉ＋１＝ΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、
ΔＹｉ＋２＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、
の同一の値同士の排他的論理和演算が実行されることになり、排他的論理和演算結果としてオール０の値を出力する。
【００５１】
その結果、次の段（ラウンドｉ＋３）への出力差分の前段（ｉ＋２ラウンド）からの左の入力差分ΔＸｉ＋３＝（００，００，００，００，００，００，００，００）となる。
【００５２】
このラウンドｉ＋３への左入力ΔＸｉ＋３＝（００，００，００，００，００，００，００，００）は、ラウンドｉへの左入力ΔＸｉ−１＝（００，００，００，００，００，００，００，００）と同様オールゼロであり、ラウンドｉ＋３以降のラウンドにおいても、ラウンドｉ〜ｉ＋２と同様の処理が繰り返される可能性がある。
【００５３】
この結果、ラウンド数の伸びに対してアクティブＳボックスの数が増大せず、差分攻撃に対する強度がそれほど伸びないという問題を発生させる。
【００５４】
共通鍵ブロック暗号において、差分攻撃に対する強度指標のひとつとして、暗号化関数全体でのアクティブＳボックスの最小数が知られている。アクティブＳボックス数の最小数が大きいほど差分攻撃に対する耐性が高いと判断される。
【００５５】
前述したように、差分解析（差分攻撃）においては、ある差分を持つ入力データ（平文）とその出力データ（暗号文）を多数設定してこの対応を解析することにより各ラウンド関数における適用鍵を解析する手法であり、この差分解析において、アクティブＳボックスの数を少なくできれば、解析が容易となり、解析プロセス数を削減できる。
【００５６】
上述の図４を参照した例では、第１のＳボックス（Ｓ１）のみがアクティブＳボックスであるパターンの発生状態を提示したが、その他のＳボックス（Ｓ２〜Ｓ８）についても、差分解析の入力データの設定によって、各ＳボックスのみをアクティブＳボックスとした設定が可能であり、このような差分解析プロセスを実行することにより、各Ｓボックスの非線形変換処理の解析、さらにＦ関数に対して入力されるラウンド鍵の解析が可能となる。
【００５７】
このような差分解析に対する耐性を向上させるためには、アクティブＳボックスの数が常に多い状態を維持すること、すなわち、アクティブＳボックスの最小数が多いことが必要である。
【００５８】
図４を参照して説明した例において、右から左へ入力を行なうＦ関数、すなわち、第ｉラウンドと第ｉ＋２ラウンドのみをアクティブＳボックス算出処理対象ラウンドとしてみた場合、アクティブＳボックス数はわずか２であり、左から右へ入力を行なうＦ関数、すなわち、第ｉ＋1ラウンドではアクティブＳボックス数が８であるものの、同時差分キャンセルにより第ｉ＋３ラウンドでのアクティブＳボックス数が０となってしまうため、差分解析による各Ｓボックスの非線形変換処理の解析処理が容易となる。
【００５９】
図４に示す共通鍵ブロック暗号アルゴリズムは、各ラウンドにおける線形変換部において適用する線形変換行列が等しいものであり、この構成に起因して、特に右から左へ入力を行うＦ関数におけるわずか２つのアクティブＳボックスにより同時差分キャンセルの発生可能性を引き起こしている。従って、ラウンド数の伸びに対してアクティブＳボックスの最小数が十分に増大せず、差分攻撃に対する強度がそれほど伸びないという問題がある。
【００６０】
次に、同様に、同じ線形変換行列をすべての段（ラウンド）のＦ関数に用いる構成において、５ラウンドにまたがる同時差分キャンセルの発生メカニズムについて、図６を参照して説明する。
【００６１】
図６はｍ＝８，ｎ＝８の１２８ｂｉｔブロック暗号における５段の同時差分キャンセルの様子を説明する図である。ただし、図中では６４ｂｉｔのデータをバイト単位で区切ってベクトルとして表現し、それぞれの要素を１６進数で表記するものとする。
【００６２】
５段構成を持つＦ関数での同時差分キャンセルは、例えば以下のデータ状態１〜７の設定メカニズムに基づいて発生する。以下に説明するメカニズムの発生するデータ状態は、多数の差分入力データを設定することで発生させることができるデータ状態であり、いわゆる差分解析における鍵（ラウンド鍵）の解析において発生し得る。
【００６３】
（状態１）
ｉラウンドへの入力差分の左半分は、すべてゼロである入力差分（ΔＸｉ−１＝（００，００，００，００，００，００，００，００））であり、右半分の入力差分がただひとつのＳ−ｂｏｘへの入力を除いてゼロである入力差分（ΔＸｉ＝（３４，００，００，００，００，００，００，００））であるとする。このデータ状態は、多数の差分入力データを設定することで、ｉラウンドにおいて、このようなデータ状態を得ることができるということである。      
【００６４】
なお、ΔＸｉ＝（３４，００，００，００，００，００，００，００）の８つの各要素は、Ｆ関数中に構成されるｍ個（ｍ＝８）のＳボックス各々に対する入力差分に対応する。（３４）が第１Ｓボックス（図６中の（Ｓ１））に入力され、（００）が、第２〜８Ｓボックスに対する入力差分である。
【００６５】
なお前述したように、ゼロ（００）の入力差分を持つＳボックスの出力差分はゼロ（００）であり、差分データに関する限り、ゼロ（００）の入力差分を持つＳボックスは、何の作用も行なっていないものであり、アクティブでないすなわち非アクティブＳボックスと呼ばれる。一方、非ゼロの入力差分（図６の例では差分：３４）を持つＳボックス（Ｓ１）のみが、非ゼロの入力差分に対応した非線形変換結果を出力差分として発生させるので、アクティブＳボックス（Ａｃｔｉｖｅ  Ｓ−ｂｏｘ）である。
【００６６】
図６の例では、非ゼロの入力差分（３４）を入力する１つのアクティブＳボックス（Ｓ１）の出力差分（ｂ７）を発生させており、その他の非アクティブＳボックスＳ２〜Ｓ８はゼロの入力差分（００）に基づいて出力差分（００）を発生させ、線形変換部の差分入力としている。
【００６７】
（状態２）
ｉラウンドへの非ゼロの入力差分（図４の例では差分：３４）を持つＳボックス（以下、アクティブＳボックス（Ａｃｔｉｖｅ  Ｓ−ｂｏｘ）と呼ぶ）からの出力差分は線形変換層で拡散されたのちＦ関数から出力（出力値＝ΔＹｉ）され、そのまま次のラウンドへの入力差分ΔＸｉ＋１となる。
【００６８】
図６の例において、各ラウンドに共通の例えば図５に示すある特定の正方行列１２５による線形変換が実行されｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）を出力する。
【００６９】
ｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）は、図６に示す排他的論理和部１４１において、すべてゼロである入力差分（ΔＸｉ−１＝（００，００，００，００，００，００，００，００）と排他的論理和（ＸＯＲ）演算が実行され、演算結果が、次のラウンド（ｉ＋１）への入力差分ΔＸｉ＋１となる。
【００７０】
ｉラウンドのＦ関数出力差分としてのΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、すべてゼロである入力差分（ΔＸｉ−１＝（００，００，００，００，００，００，００，００）との排他的論理和（ＸＯＲ）結果は、ΔＹｉであるので、次のラウンド（ｉ＋１）への入力差分ΔＸｉ＋１＝ΔＹｉ＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）となる。      
【００７１】
（状態３）
ｉ＋１ラウンドのＦ関数からの出力差分ΔＹｉ＋１が、ｉラウンドでのＡｃｔｉｖｅ  Ｓ−ｂｏｘの位置にのみ非ゼロ値をもつ。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。
【００７２】
すなわち、ΔＹｉ＋１＝（３４，００，００，００，００，００，００，００）であり、ｉラウンドと同様、非ゼロの差分値（図６の例では差分：３４）を持つＳ−ｂｏｘの位置（第１Ｓボックス（Ｓ１））にのみ非ゼロ値をもつ。
【００７３】
（状態４）
ｉ＋２ラウンドのＦ関数に対する入力は、ΔＸｉ＝（３４，００，００，００，００，００，００，００）と、ΔＹｉ＋１＝（３４，００，００，００，００，００，００，００）との排他的論理和部１４２における排他的論理和結果、すなわち、同一データ同士の排他的論理和であり、オールゼロの入力、ΔＸｉ＋２＝（００，００，００，００，００，００，００，００）となり、その結果、ｉ＋２ラウンドのＦ関数からの出力差分も、オールゼロの出力差分、ΔＹｉ＋２＝（００，００，００，００，００，００，００，００）となる。
【００７４】
（状態５）
ｉ＋３ラウンドのＦ関数に対する入力は、ΔＸｉ＋１＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、オールゼロのｉ＋２ラウンドのＦ関数出力差分ΔＹｉ＋２＝（００，００，００，００，００，００，００，００）との排他的論理和部１４３における排他的論理和結果であり、ｉ＋３ラウンドのＦ関数に対する入力ΔＸｉ＋３＝ΔＸｉ＋１＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）となる。
【００７５】
（状態６）
ｉ＋３ラウンドのＦ関数出力差分が、ΔＹｉ＋３＝（４３，００，００，００，００，００，００，００）となり、オールゼロのΔＸｉ＋２＝（００，００，００，００，００，００，００，００）との排他的論理和部１４４における排他的論理和の結果としてのΔＸｉ＋４＝ΔＹｉ＋３＝（４３，００，００，００，００，００，００，００）がｉ＋４ラウンドのＦ関数入力差分となる。
【００７６】
（状態７）
ｉ＋４ラウンドのアクティブＳボックス（Ａｃｔｉｖｅ  Ｓ−ｂｏｘ）（Ｓ１）の出力差分がｉラウンドでのアクティブＳボックス（Ａｃｔｉｖｅ  Ｓ−ｂｏｘ）（Ｓ１）の出力差分と一致した場合、すなわち、図６に示すようにｉ＋４ラウンドのアクティブＳボックス（（Ｓ１）の出力差分がｂ７となり、ｉラウンドでのアクティブＳボックス（Ｓ１）の出力差分（ｂ７）と一致する。このデータ状態は、多数の差分入力データを設定することで、このようなデータ状態を得ることができるということである。
【００７７】
このデータ状態が発生すると、ｉ＋４ラウンドのＦ関数の出力差分ΔＹｉ＋４＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）が、２つ前のラウンドであるｉ＋２ラウンドの排他的論理和部１４３の出力差分ΔＸｉ＋３＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と一致することになる。
【００７８】
この結果、排他的論理和部１４５では、
ΔＸｉ＋３＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、
ΔＹｉ＋４＝（９８，ｃ４，ｂ４，ｄ３，ａｃ，７２，０ｆ，３２）と、
の同一の値同士の排他的論理和演算が実行されることになり、排他的論理和演算結果としてオール０の値を出力する。
【００７９】
その結果、次の段（ラウンドｉ＋５）への入力差分は、ΔＸｉ＋５＝（００，００，００，００，００，００，００，００）として設定される。
【００８０】
このラウンドｉ＋５への左入力ΔＸｉ＋５＝（００，００，００，００，００，００，００，００）は、ラウンドｉへの左入力ΔＸｉ−１＝（００，００，００，００，００，００，００，００）と同様オールゼロであり、ラウンドｉ＋５以降のラウンドにおいても、ラウンドｉ〜ｉ＋４と同様の処理が繰り返される可能性がある。
【００８１】
この結果、ラウンド数の伸びに対してアクティブＳボックスの数が増大せず、差分攻撃に対する強度がそれほど伸びないという問題を発生させる。
【００８２】
前述したように、差分解析（差分攻撃）においては、ある差分を持つ入力データ（平文）とその出力データ（暗号文）を多数設定してこの対応を解析することにより各ラウンド関数における適用鍵を解析する手法であり、この差分解析において、アクティブＳボックスの数を少なくできれば、解析が容易となり、解析プロセス数を削減できる。
【００８３】
上述の図６を参照した例において、右から左へ入力を行なうＦ関数、すなわち、第ｉラウンドと第ｉ＋２ラウンド、第ｉ＋４ラウンドのみをアクティブＳボックス算出処理対象ラウンドとしてみた場合、アクティブＳボックス数は、第ｉラウンド＝１、第ｉ＋２ラウンド＝０、第ｉ＋４ラウンド＝１の合計わずか２であり、左から右へ入力を行なうＦ関数、すなわち第ｉ＋1ラウンドおよび第ｉ＋３ラウンドではアクティブＳボックス数が８であるものの、同時差分キャンセルにより第ｉ＋５ラウンドでのアクティブＳボックス数が０となってしまうため、差分解析による各Ｓボックスの非線形変換処理の解析、および、Ｆ関数に対する入力ラウンド鍵の解析処理が比較的、容易となる。
【００８４】
図６を参照した例では、第１のＳボックス（Ｓ１）のみがアクティブＳボックスであるパターンの発生状態を提示したが、その他のＳボックス（Ｓ２〜Ｓ８）についても、差分解析の入力データの設定によって、各ＳボックスのみをアクティブＳボックスとした設定が可能であり、このような差分解析プロセスを実行することにより、各Ｓボックスの非線形変換処理の解析、さらにＦ関数に対して入力されるラウンド鍵の解析が可能となる。
【００８５】
図４および図６を参照して、３および５ラウンドの場合の同時差分キャンセルの発生例を説明したが、任意のラウンド数に一般化して同時差分キャンセルを定義すると以下のように定義することができる。図７を参照して、任意のラウンド数における同時差分キャンセルの定義について説明する。なお、図７は、フェイステル（Ｆｅｉｓｔｅｌ）構造の共通鍵ブロック暗号を実行するフェイステル（Ｆｅｉｓｔｅｌ）構造の１つおきのラウンド（ｉ，ｉ＋２，ｉ＋４，・・・，ｉ＋２ｊ）を示している。
【００８６】
「定義」
フェイステル（Ｆｅｉｓｔｅｌ）構造のラウンドｉでの入力差分の半分（ＰＬまたはＰＲ）が０（図７において、ΔＸｉ＝（００，００，００，００，００，００，００，００））であり、そこにｉ＋２ｊラウンド（ｊ＝０，１，２，...）のＦ関数の出力差分が排他的論理和部で演算されていく過程において、あるラウンドｉ＋２ｋにおいて、排他的論理和の結果が０（図７において、ΔＸｉ＋２ｊ＋１＝（００，００，００，００，００，００，００，００））になった場合を"同時差分キャンセル"と呼ぶ。
【００８７】
その時、ｉ，ｉ＋２，ｉ＋４，．．，ｉ＋２ｋラウンドのＦ関数の中に存在するアクティブＳボックス（Ａｃｔｉｖｅ  Ｓ−ｂｏｘ）のことを"同時差分キャンセルを発生させたアクティブＳボックス"と呼ぶものとし、ベクトルＡの非ゼロの要素数をハミングウェイトｈｗ（Ａ）と定義すると、同時差分キャンセルを発生させるアクティブＳボックスの数ａは、以下の式として表せる。
【数１】
2006301567.tif 000003
【００８８】
前述の３ラウンド、５ラウンドでの例ではともに同時差分キャンセルを発生させたアクティブＳボックス数は２、すなわちａ＝２である。
【００８９】
前述したように、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつが暗号化関数全体でのアクティブＳボックスの最小数であり、アクティブＳボックス数の最小数が大きいほど差分攻撃に対する耐性が高いと判断される。
【００９０】
しかし、ＤＥＳアルゴリズムのように同じ線形変換行列をすべての段のＦ関数に用いる構成では、図４、図６を参照して説明したように、わずか２つのアクティブＳボックスにより同時差分キャンセルが発生してしまう可能性があった。そのような性質があるためラウンド数の伸びに対してアクティブＳボックスの最小数が十分に増大せず、差分攻撃に対する強度がそれほど伸びないという問題があった。
【００９１】
［２．共通鍵ブロック暗号アルゴリズムにおける線形解析処理］
差分解析処理は、上述したように、解析の実行者が一定の差分を持つ入力データ（平文）を容易し、その対応する出力データ（暗号文）を解析することが必要となる。線形解析処理は、一定の差分を持つ入力データ（平文）を準備する必要はなく、所定量以上の入力データ（平文）と対応する出力データ（暗号文）とに基づいて解析を行う。
【００９２】
前述したように、共通鍵ブロック暗号アルゴリズムでは非線形変換部としてのＳボックスを有し、入力データ（平文）と対応する出力データ（暗号文）との線形関係はないが、線形解析では、このＳボックスの入出力を線形近似し、多数の入力データ（平文）と対応する出力データ（暗号文）の構成ビット値の線形関係を解析し、候補となる鍵を絞り込むことによって解析を行う。線形解析においては、特定の差分を持つ入力データを準備することが必要ではなく、多数の平文と対応暗号文を容易することで、解析が可能となる。
【００９３】
［３．耐性を向上させた暗号処理アルゴリズム構成例］
次に、本発明の出願人が先に提案した暗号処理アルゴリズムについて説明する。以下で説明する暗号処理アルゴリズムは、本出願と同一出願人による特許出願、特願２００３−３３９６３４、および特願２００４−２５６４６５において説明しているアルゴリズムであり、上述した線形解析、差分解析等の攻撃に対する耐性を向上させた構成、すなわち、鍵解析の困難性を高め、安全性を向上させた構成を持つ。
【００９４】
以下で説明する暗号処理アルゴリズムの１つの特徴は、従来のＤＥＳアルゴリズムの如く各ラウンドのＦ関数に構成される線形変換部に共通の処理（変換行列）を適用した構成とせず、複数の異なる正方ＭＤＳ（Ｍａｘｉｍｕｍ  Ｄｉｓｔａｎｃｅ  Ｓｅｐａｒａｂｌｅ）行列を設定した構成としたことである。具体的には、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方ＭＤＳ行列を適用した線形変換処理を実行する構成を持つ。
【００９５】
この暗号処理アルゴリズムは、正方ＭＤＳ（Ｍａｘｉｍｕｍ  Ｄｉｓｔａｎｃｅ  Ｓｅｐａｒａｂｌｅ）行列の性質を利用し、少ないアクティブＳボックスに基づく同時差分キャンセルが起こらない、または起こりにくい構造を実現し、アクティブＳボックスの最小数を増大させ、差分攻撃に対してより強い共通鍵ブロック暗号処理を実現する。あるいは、既知平文攻撃として行なわれる線形解析についての困難性も高めた構成を持つ。
【００９６】
この暗号処理アルゴリズムは、図１、２を参照して説明したＳＰＮ型のＦ関数を有するＦｅｉｓｔｅｌ構造と呼ばれる代表的な共通鍵ブロック暗号の構造、すなわち、非線形変換部および線形変換部を有するＳＰＮ型のＦ関数の複数ラウンドに渡る単純な繰り返しにより、平文を暗号文に変換する、あるいは暗号文を平文変換する構造を適用している。
【００９７】
例えば、平文の長さを２ｍｎビット（ただし、ｍ，ｎは共に整数）として、２ｍｎビットの平文を、ｍｎビットの２つのデータＰＬ（Plain-Left），ＰＲ(Plain-Right)に分割し、これを入力値として、各ラウンドにおいて、Ｆ関数を実行させるものであり、Ｆ関数は、図２を参照して説明したように、Ｓボックスからなる非線形変換部と、線形変換部を接続したＳＰＮ型を持つＦ関数である。
【００９８】
この暗号処理アルゴリズムにおいては、Ｆ関数中の線形変換部において適用する線形変換処理のための行列として、複数の異なる正方ＭＤＳ（Ｍａｘｉｍｕｍ  Ｄｉｓｔａｎｃｅ  Ｓｅｐａｒａｂｌｅ）行列から選択された行列を各ラウンドのＦ関数の線形変換部において適用する行列として設定する。具体的には、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方ＭＤＳ行列を適用する。
【００９９】
正方ＭＤＳ行列について説明する。正方ＭＤＳ行列とは以下の（ａ），（ｂ）の性質を満たす行列をいう。
（ａ）正方行列である
（ｂ）行列に含まれるすべての部分行列（ｓｕｂｍａｔｒｉｘ）の行列式（ｄｅｔｅｒｍｉｎａｎｔ）が０でない、すなわち、ｄｅｔ（ｓｕｂｍａｔｒｉｘ）≠０
【０１００】
上記（ａ），（ｂ）の条件を満足する行列を正方ＭＤＳ行列と呼ぶ。
共通鍵ブロック暗号の各ラウンドで実行するＦ関数に対する入出力ビット長がｍ×ｎ（ｍ，ｎ：整数）ビットであり、Ｆ関数内に構成される非線形変換部がｎビットの入出力を持つｍ個のＳボックスにより構成され、線形変換部がｎ次の既約多項式で定義される２の拡大体ＧＦ（２ｎ）上の元を要素として持つｍ次の正方行列に基づく線形変換処理を実行する場合の、正方ＭＤＳ行列の一例を図８に示す。図８に示す正方ＭＤＳ行列の例は、ｎ＝８，ｍ＝８の正方ＭＤＳ行列の例である。
【０１０１】
上記（ａ），（ｂ）を満足する正方ＭＤＳ行列は、ベクトルＡの非ゼロの要素数をハミングウェイトｈｗ（Ａ）とし、Ｍをｍ次の正方ＭＤＳ行列とし、ｘを正方ＭＤＳ行列Ｍへの入力ベクトルとした場合、以下の不等式（式１）を満たすことになる。
ｈｗ（ｘ）＋ｈｗ（Ｍｘ）≧ｍ＋１‥‥‥‥‥‥（式１）
【０１０２】
上記式（式１）は、正方ＭＤＳ行列（Ｍ）によって線形変換される入力データｘの非ゼロの要素数ｈｗ（ｘ）と、正方ＭＤＳ行列（Ｍ）によって線形変換された出力データＭｘの非ゼロの要素数ｈｗ（Ｍｘ）の総数が、正方ＭＤＳ行列の次数ｍより大となるということを意味している。
【０１０３】
なお、正方ＭＤＳ行列という名は正方ＭＤＳ−ｃｏｄｅ（Ｍａｘｉｍｕｍ  Ｄｉｓｔａｎｃｅ  Ｓｅｐａｒａｂｌｅ  Ｃｏｄｅ）の生成行列の標準形の右半分が上記条件を満足していることから名づけているものである。
【０１０４】
１つの行列をすべてのＦ関数に組み込むという従来の構成でも線形変換行列に正方ＭＤＳ行列を用いることで、正方ＭＤＳ行列でない行列を用いる場合に比べてアクティブＳボックス数の最小数を比較的高水準に保持することができるということは知られている。
【０１０５】
本アルゴリズムでは、各ラウンドのＦ関数には正方ＭＤＳ行列の条件を満たす行列を利用し、さらにラウンドごとに異なる行列を設定する方法を提案する。具体的には、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方ＭＤＳ行列を適用する。
【０１０６】
以下に、段数（ラウンド数）が２ｒ（ｒは整数）のＦｅｉｓｔｅｌ型共通鍵ブロック暗号において、差分攻撃に対する耐性をより高めた複数の構成例について説明する。
【０１０７】
なお、以下の説明において、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成のｊ段目のＦ関数における線形変換部で適用する線形変換行列をＭＬＴｊとして表すものとする。
【０１０８】
本アルゴリズムの構成では、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成における各段のＦ関数中の線形変換部において適用する線形変換処理のための行列として、複数の異なる正方ＭＤＳ（Ｍａｘｉｍｕｍ  Ｄｉｓｔａｎｃｅ  Ｓｅｐａｒａｂｌｅ）行列から選択された行列を各ラウンドのＦ関数の線形変換部において適用する行列として設定する。具体的には、少なくとも連続する偶数ラウンドおよび連続する奇数ラウンドの各々において異なる正方ＭＤＳ行列を適用する。
【０１０９】
具体的には、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ以下のｑ個の正方ＭＤＳ行列：Ｌ１，Ｌ２，・・，Ｌｑを生成し、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成における奇数段目のＦ関数中の線形変換部において適用する線形変換処理のための行列として、上位段のＦ関数から順にＬ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定する。さらに、偶数段のＦ関数については、下位段のＦ関数から順に、Ｌ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定する。
【０１１０】
本設定を適用した構成例を図９に示す。図９は、段数（ラウンド数）が２ｒ＝１２、すなわちｒ＝６のＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成とした場合、ｑ＝３、すなわち、１２段のラウンド数を持つＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成において３種類の異なる正方ＭＤＳ行列を配置した構成例として、各ラウンドのＦ関数部の線形変換部に設定する正方ＭＤＳ行列（Ｌ１，Ｌ２，Ｌ３）を示している。
【０１１１】
図９の構成は、２ｍｎビットの平文を、ｍｎビットの２つのデータＰＬ（Plain-Left），ＰＲ(Plain-Right)に分割し、これを入力値として、各ラウンドにおいて、Ｆ関数を実行させる構成であり、第１ラウンドのＦ関数４０１およびその他のラウンドのＦ関数も、すべて図２を参照して説明したように、Ｓボックスからなる非線形変換部と、線形変換部を接続したＳＰＮ型を持つＦ関数である。
【０１１２】
図９の設定例はｒ＝６，ｑ＝３であり、各Ｆ関数内に示す記号Ｌｎは正方ＭＤＳ行列４０２を示している。すなわち、Ｌ１，Ｌ２，Ｌ３は、それぞれ異なる３種類の正方ＭＤＳ行列を示し、各Ｆ関数の線形変部において線形変換処理に適用する正方ＭＤＳ行列を示している。
【０１１３】
線形変換行列ＭＬＴｊの設定処理シーケンスについて、図１０を参照して説明する。
【０１１４】
［ステップＳ２１］
ラウンド数２ｒの半数ｒに対してｒ以下の数ｑ、すなわち、
ｑ≦ｒとなる数ｑを選択する。ただし、ｑは２以上の整数である。
［ステップＳ２２］
ｑ個のＧＦ（２ｎ）上のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑを生成する。ｑ個のＧＦ（２ｎ）上のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑの生成処理手法についての詳細は、後段で説明する。
【０１１５】
ステップＳ２２において、ｑ個のＧＦ（２ｎ）上のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが生成した後、次に、以下の正方ＭＤＳ行列設定処理を実行する。
［ステップＳ２３］
２ｉ−１（１≦ｉ≦ｒ）段目の線形変換行列ＭＬＴ２ｉ−１にＬ（ｉ−１ｍｏｄｑ）＋１を設定する。
［ステップＳ２４］
２ｉ（１≦ｉ≦ｒ）段目の線形変換行列にＭＬＴ２ｉにＭＬＴ２ｒ−２ｉ＋１を設定する。
【０１１６】
例えば、図９に示す構成例、すなわち、１２段（ｒ＝６）でありｑ＝３とした場合は、
ＭＬＴ１＝Ｌ１，    ＭＬＴ２＝Ｌ３
ＭＬＴ３＝Ｌ２，    ＭＬＴ４＝Ｌ２
ＭＬＴ５＝Ｌ３，    ＭＬＴ６＝Ｌ１
ＭＬＴ７＝Ｌ１，    ＭＬＴ８＝Ｌ３
ＭＬＴ９＝Ｌ２，    ＭＬＴ１０＝Ｌ２
ＭＬＴ１１＝Ｌ３，   ＭＬＴ１２＝Ｌ１
の設定となる。
【０１１７】
このように、このアルゴリズムを適用した暗号処理装置においては、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成に対応して、ｒ以下のｑ個の正方ＭＤＳ行列：Ｌ１，Ｌ２，・・，Ｌｑを生成し、奇数段目については上位段のＦ関数から順にＬ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定し、偶数段のＦ関数については、下位段のＦ関数から順に、Ｌ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定する構成としている。
【０１１８】
次に、図１０の処理フローにおけるステップＳ２２のｑ個のＧＦ（２ｎ）上のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑの生成処理およびＦ関数への設定構成の詳細について説明する。なお、説明は以下の項目に沿って行なう。
（３−ａ）差分攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例
（３−ｂ）線形攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例
（３−ｃ）差分攻撃および線形攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例
【０１１９】
［（３−ａ）差分攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例］
まず、差分攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例として、３つの処理例ａ１，ａ２，ａ３について説明する。
【０１２０】
（処理例ａ１）
差分攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例の第１の例について説明する。まず、図１１に示すフローチャートを参照して正方ＭＤＳ行列の生成処理について説明する。
【０１２１】
［ステップＳ１０１］
入力：必要な正方ＭＤＳの個数ｑ，拡大次数：ｎ，行列のサイズ：ｍとして、
ＧＦ（２ｎ）上で、ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑをランダムに生成する。なお、図１１に示すフローでは、ＭＤＳの個数ｑ＝６，拡大次数：ｎ＝８，行列のサイズ：ｍ＝８の場合の処理例として示してある。
【０１２２】
［ステップＳ１０２］
ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑに含まれるｑｍ個の列の任意のｍ個を取り出したときに、線形独立になっているかどうかをチェックする。チェックに通過したらステップＳ１０３に進む、そうでない場合はステップＳ１０１にもどる。
［ステップＳ１０３］
ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑを、ラウンド数２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号に適用する正方ＭＤＳ行列として出力する。
【０１２３】
以上のプロセスによって、ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが生成される。なお、ｑ≦ｒである。
【０１２４】
このようにして生成したｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑを、先に、図１０を参照して説明した、［ステップＳ２３］、［ステップＳ２４］の処理に従って、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成の各段のＦ関数部の線形変換部の線形変換処理に適用する行列として設定する。すなわち、奇数段目については上位段から順にＬ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・としてｑ個の正方ＭＤＳ行列を繰り返し設定し、偶数段のＦ関数については、下位段のＦ関数から順に、Ｌ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定する。
【０１２５】
このように、偶数ラウンドの正方ＭＤＳ行列と奇数ラウンドの正方ＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【０１２６】
本構成により、
（ａ）各Ｆ関数の線形変換行列は正方ＭＤＳであること、
（ｂ）暗号化関数内の奇数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが独立であること、
（ｃ）偶数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが独立であること、
これら（ａ）〜（ｃ）が保証されるため、複数段のラウンド数を持つＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成において、連続する２ｑ−１ラウンドにおいて、ｍ個以下のアクティブＳボックスの寄与による同時差分キャンセルは発生しないことが保証される。よって暗号化関数全体のアクティブＳボックス数の最小値が増大する。
【０１２７】
このように、本処理例によって、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最小数を大きくすることが可能となり、結果として、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。
【０１２８】
（処理例ａ２）
差分攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例の第２の例について説明する。図１２のフローチャートを参照して正方ＭＤＳ行列の生成処理について説明する。
【０１２９】
［ステップＳ２０１］
入力：必要なＭＤＳの個数ｑ，拡大次数：ｎ，行列のサイズ：ｍとして、
ＧＦ（２ｎ）上で、ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑをランダムに生成する。なお、図１２に示すフローでは、ＭＤＳの個数ｑ＝６，拡大次数：ｎ＝８，行列のサイズ：ｍ＝８の場合の処理例として示してある。
【０１３０】
［ステップＳ２０２］
ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑに含まれるｑｍ個の列の任意のｍ個を取り出したときに、正方ＭＤＳ行列になっているかどうかをチェックする。チェックに通過したらステップＳ２０３に進む、そうでない場合はステップＳ２０１にもどる。
なお、正方ＭＤＳ行列とは、前述したように以下の性質を満たす行列をいう。
（ａ）正方行列である
（ｂ）行列に含まれるすべての部分行列（ｓｕｂｍａｔｒｉｘ）の行列式（ｄｅｔｅｒｍｉｎａｎｔ）が０でない、すなわち、ｄｅｔ（ｓｕｂｍａｔｒｉｘ）≠０
［ステップＳ２０３］
ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑを、ラウンド数２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号に適用する正方ＭＤＳ行列として出力する。
【０１３１】
以上のプロセスによって、ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが生成される。なお、ｑ≦ｒである。
【０１３２】
前述の処理例ａ１における正方ＭＤＳ行列生成処理においては、図１１の処理シーケンスにおいて説明したように、ステップＳ１０２において、ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑに含まれるｑｍ個の列の任意のｍ個を取り出したときの線形独立性を判定したが、この処理例ａ２における正方ＭＤＳ行列生成処理においては、ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑに含まれるｑｍ個の列の任意のｍ個を取り出したとき正方ＭＤＳ行列になっているかどうかをチェックする。すなわち、より厳しいチェックが実行されることになる。
【０１３３】
この図１２に示す処理シーケンスに従った正方ＭＤＳ行列生成処理によって生成されたｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが、先に説明した処理例ａ１と同様、先に、図１０を参照して説明した、［ステップＳ２３］、［ステップＳ２４］の処理に従って、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成の各段のＦ関数部の線形変換部の線形変換処理に適用する行列として設定される。すなわち、奇数段目については上位段から順にＬ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・としてｑ個の正方ＭＤＳ行列を繰り返し設定し、偶数段のＦ関数については、下位段のＦ関数から順に、Ｌ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定する。
【０１３４】
このように、偶数ラウンドの正方ＭＤＳ行列と奇数ラウンドの正方ＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【０１３５】
本構成により、
（ａ）各Ｆ関数の線形変換行列は正方ＭＤＳであること、
（ｂ）暗号化関数内の奇数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが正方ＭＤＳ行列であること、
（ｃ）偶数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが正方ＭＤＳ行列であること、
これら（ａ）〜（ｃ）が保証されるため、複数段のラウンド数を持つＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成において、連続する２ｑ−１ラウンドにおいて、ｍ個以下のアクティブＳボックスの寄与による同時差分キャンセルは発生しないことが保証される。
さらに、
（ｄ）正方ＭＤＳの性質から、ａ個（ａ≦ｍ）のアクティブＳボックスの寄与によって得られる差分値における非ゼロの要素数はｍ＋１−ａ個以上になることが保証される。よって暗号化関数全体のアクティブＳボックス数の最小値が増大する。
【０１３６】
このように、本処理例によって、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最小数を大きくすることが可能となり、結果として、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。
【０１３７】
（処理例ａ３）
差分攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例の第３の例について説明する。図１３のフローチャートを参照して正方ＭＤＳ行列の生成処理について説明する。
【０１３８】
［ステップＳ３０１］
入力：必要なＭＤＳの個数ｑ，拡大次数：ｎ，行列のサイズ：ｍとして、
ＧＦ（２ｎ）上で、１個のｑｍ次正方ＭＤＳ行列Ｍを生成する。なお、図１３に示すフローでは、ＭＤＳの個数ｑ＝６，拡大次数：ｎ＝８，行列のサイズ：ｍ＝８の場合の処理例として示してある。
【０１３９】
［ステップＳ３０２］
１個のｑｍ次正方ＭＤＳ行列Ｍからｍ本の行を任意に選択抽出し、ｍ行，ｑｍ列の行列Ｍ'を構成する。
［ステップＳ３０３］
ｍ行，ｑｍ列の行列Ｍ'に含まれるｑｍ本の列ベクトルを重複することなくｍ本の列ベクトルからなるｑ個のグループに任意に分割し、それぞれのグループに含まれる列ベクトルからｍ次の正方行列Ｌ１，Ｌ２，...，Ｌｑを、ラウンド数２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号に適用する正方ＭＤＳ行列として出力する。
【０１４０】
以上のプロセスによって、ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが生成される。なお、ｑ≦ｒである。
【０１４１】
処理例ａ３における正方ＭＤＳ行列生成手法３について、図１４を参照して、より具体的に説明する。
［ステップＳ３０１］
ＧＦ（２ｎ）上で、１個のｑｍ次正方ＭＤＳ行列Ｍを生成する。図１４に示すように、ｑｍ×ｑｍの正方ＭＤＳ行列Ｍを生成する。なお、このステップＳ３０１において生成する行列Ｍの次数はｑｍ次より大きいものでもよい。
［ステップＳ３０２］
図１４に示すように、ｑｍ次正方ＭＤＳ行列Ｍからｍ本の行を任意に選択抽出し、ｍ行，ｑｍ列の行列Ｍ'を構成する。なお、図に示す例では、連続するｍ本の行を選択抽出した例として示してあるが、ｍ次正方ＭＤＳ行列Ｍを構成する任意の離間した行をｍ本選択抽出して、ｍ行，ｑｍ列の行列Ｍ'を構成してもよい。
［ステップＳ３０３］
ｍ行，ｑｍ列の行列Ｍ'に含まれるｑｍ本の列ベクトルを重複することなくｍ本の列ベクトルからなるｘ個のグループに任意に分割し、それぞれのグループに含まれる列ベクトルからｍ次の正方行列Ｌ１，Ｌ２，...，Ｌｘを生成する。
【０１４２】
図１３、図１４を参照して説明した処理シーケンスに従った正方ＭＤＳ行列生成処理によって生成されたｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが、先に説明した処理例ａ１、ａ２と同様、先に、図１０を参照して説明した、［ステップＳ２３］、［ステップＳ２４］の処理に従って、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成の各段のＦ関数部の線形変換部の線形変換処理に適用する行列として設定される。すなわち、奇数段目については上位段から順にＬ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・としてｑ個の正方ＭＤＳ行列を繰り返し設定し、偶数段のＦ関数については、下位段のＦ関数から順に、Ｌ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定する。
【０１４３】
このように、偶数ラウンドの正方ＭＤＳ行列と奇数ラウンドの正方ＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【０１４４】
本構成により、
（ａ）各Ｆ関数の線形変換行列は正方ＭＤＳであること、
（ｂ）暗号化関数内の奇数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが独立であること、
（ｃ）偶数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが独立であること、
これら（ａ）〜（ｃ）が保証されるため、複数段のラウンド数を持つＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成において、連続する２ｑ−１ラウンドにおいて、ｍ個以下のアクティブＳボックスの寄与による同時差分キャンセルは発生しないことが保証される。
さらに、
（ｄ）正方ＭＤＳの性質から、ａ個（ａ≦ｍ）のアクティブＳボックスの寄与によって得られる差分値における非ゼロの要素数はｍ＋１−ａ個以上になることが保証される。よって暗号化関数全体のアクティブＳボックス数の最小値が増大する。
【０１４５】
なお、処理例ａ３が特に効果を発揮するのは、ｍ，ｒ，が大きくなり、前述した処理例ａ１，ａ２の行列決定処理方式にかかる時間的コストが莫大となり、現実的な時間内に行列を決定することが困難である場合である。そのような場合でも本処理例ａ３の正方ＭＤＳ行列生成手法ならば比較的短時間での行列生成処理が可能となる。
【０１４６】
これは、処理例ａ３においては、大きなｍ，ｒに対しても現実的な時間で十分に処理可能な方式、例えばリードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号の生成行列の生成法を適用することが可能となるからである。
【０１４７】
この処理例ａ３においても、上述したように、共通鍵ブロック暗号における差分攻撃に対する強度指標のひとつである暗号化関数全体でのアクティブＳボックスの最小数を大きくすることが可能となり、結果として、差分解析（差分攻撃）を行なった場合のアクティブＳボックスの数が増大し、解析の困難性が高まることになる。従って鍵の解析の困難な安全性の高い暗号処理が実現される。
【０１４８】
［（３−ｂ）線形攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例］
次に、線形攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例として、２つの処理例ｂ１，ｂ２について説明する。
【０１４９】
（処理例ｂ１）
線形攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例の第１の例について、説明する。図１５に示すフローチャートを参照して正方ＭＤＳ行列の生成処理について説明する。
【０１５０】
［ステップＳ４０１］
入力：必要な正方ＭＤＳの個数ｑ，拡大次数：ｎ，行列のサイズ：ｍとして、
ＧＦ（２ｎ）上で、ｑ個のｍ次正方ＭＤＳ行列Ｍ１，Ｍ２，...，Ｍｑをランダムに生成する。なお、図１４に示すフローでは、正方ＭＤＳの個数ｑ＝６，拡大次数：ｎ＝８，行列のサイズ：ｍ＝８の場合の処理例として示してある。
【０１５１】
［ステップＳ４０２］
ｑ個のｍ次正方ＭＤＳ行列Ｍ１，Ｍ２，...，Ｍｑの逆行列Ｍ１−１，Ｍ２−１，...，Ｍｑ−１を算出し、隣り合う２つの逆行列に含まれる２ｍの行ベクトルから任意のｍ本の行ベクトルを取り出したときに、線形独立になっているかどうかをチェックする。図１５中、ｔＲは、行ベクトルの転置ベクトルを示すものである。チェックに通過したらステップＳ４０３に進む、そうでない場合はステップＳ４０１にもどる。ただし、Ｍ１−１とＭｑ−１は、隣り合う行列とする。
［ステップＳ４０３］
ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑを、ラウンド数２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号に適用する正方ＭＤＳ行列として出力する。
【０１５２】
以上のプロセスによって、ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが生成される。なお、ｑ≦ｒである。
【０１５３】
このようにして生成したｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑを、先に、図１０を参照して説明した、［ステップＳ２３］、［ステップＳ２４］の処理に従って、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成の各段のＦ関数部の線形変換部の線形変換処理に適用する行列として設定する。すなわち、奇数段目については上位段から順にＬ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・としてｑ個の正方ＭＤＳ行列を繰り返し設定し、偶数段のＦ関数については、下位段のＦ関数から順に、Ｌ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定する。
【０１５４】
このように、偶数ラウンドの正方ＭＤＳ行列と奇数ラウンドの正方ＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【０１５５】
本構成により、
（ａ）各Ｆ関数の線形変換行列は正方ＭＤＳであること、
（ｂ）暗号化関数内の奇数ラウンド内に連続して含まれる線形変換行列、および偶数ラウンド内に連続して含まれる線形変換行列の逆行列の任意のｍ個の列ベクトルは独立であること、
が保証される。このことにより、線形攻撃における線形近似による解析困難性を高めることが可能となり、解析の困難性、すなわち鍵の解析の困難な安全性の高い暗号処理が実現される。
【０１５６】
（処理例ｂ２）
線形攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例の第２の例について、説明する。図１６に示すフローチャートを参照して正方ＭＤＳ行列の生成処理について説明する。
【０１５７】
［ステップＳ５０１］
入力：必要な正方ＭＤＳの個数ｑ，拡大次数：ｎ，行列のサイズ：ｍとして、
ＧＦ（２ｎ）上で、ｑ個のｍ次正方ＭＤＳ行列Ｍ１，Ｍ２，...，Ｍｑをランダムに生成する。なお、図１６に示すフローでは、正方ＭＤＳの個数ｑ＝６，拡大次数：ｎ＝８，行列のサイズ：ｍ＝８の場合の処理例として示してある。
【０１５８】
［ステップＳ５０２］
ｑ個のｍ次正方ＭＤＳ行列Ｍ１，Ｍ２，...，Ｍｑの逆行列Ｍ１−１，Ｍ２−１，...，Ｍｑ−１を算出し、隣り合う２つの逆行列に含まれる２ｍの行ベクトルから任意のｍ本の行ベクトルを取り出したときに、正方ＭＤＳ行列になっているかどうかをチェックする。図１６中、ｔＲは、行ベクトルの転置ベクトルを示すものである。チェックに通過したらステップＳ５０３に進む、そうでない場合はステップＳ４０１にもどる。ただし、Ｍ１−１とＭｑ−１は、隣り合う行列とする。
なお、正方ＭＤＳ行列とは、前述したように以下の性質を満たす行列をいう。
（ａ）正方行列である
（ｂ）行列に含まれるすべての部分行列（ｓｕｂｍａｔｒｉｘ）の行列式（ｄｅｔｅｒｍｉｎａｎｔ）が０でない、すなわち、ｄｅｔ（ｓｕｂｍａｔｒｉｘ）≠０
【０１５９】
［ステップＳ５０３］
ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑを、ラウンド数２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号に適用する正方ＭＤＳ行列として出力する。
【０１６０】
以上のプロセスによって、ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが生成される。なお、ｑ≦ｒである。
【０１６１】
前述の処理例ｂ１における正方ＭＤＳ行列生成処理においては、図１５の処理シーケンスにおいて説明したように、ステップＳ４０２において、ｑ個のｍ次正方ＭＤＳ行列のＭ１，Ｍ２，...，Ｍｑの逆行列Ｍ１−１，Ｍ２−１，...，Ｍｑ−１に含まれるｑｍ個の列の任意のｍ個を取り出したときの線形独立性を判定したが、この処理例ｂ２における正方ＭＤＳ行列生成処理においては、ｑ個のｍ次正方ＭＤＳ行列のＭ１，Ｍ２，...，Ｍｑの逆行列Ｍ１−１，Ｍ２−１，...，Ｍｑ−１に含まれるｑｍ個の列の任意のｍ個を取り出したとき正方ＭＤＳ行列になっているかどうかをチェックする。すなわち、より厳しいチェックが実行されることになる。
【０１６２】
この図１６に示す処理シーケンスに従った正方ＭＤＳ行列生成処理によって生成されたｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが、先に説明した処理例ｂ１と同様、先に、図１０を参照して説明した、［ステップＳ２３］、［ステップＳ２４］の処理に従って、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成の各段のＦ関数部の線形変換部の線形変換処理に適用する行列として設定される。すなわち、奇数段目については上位段から順にＬ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・としてｑ個の正方ＭＤＳ行列を繰り返し設定し、偶数段のＦ関数については、下位段のＦ関数から順に、Ｌ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定する。
【０１６３】
このように、偶数ラウンドの正方ＭＤＳ行列と奇数ラウンドの正方ＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【０１６４】
本構成により、
（ａ）各Ｆ関数の線形変換行列は正方ＭＤＳであること、
（ｂ）暗号化関数内の奇数ラウンド内に連続して含まれる線形変換行列、および偶数ラウンド内に連続して含まれる線形変換行列の逆行列の任意のｍ個の列ベクトルが正方ＭＤＳ行列となること、
が保証される。このことにより、線形攻撃における線形近似による解析困難性を高めることが可能となり、解析の困難性、すなわち鍵の解析の困難な安全性の高い暗号処理が実現される。
【０１６５】
［（３−ｃ）差分攻撃および線形攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例］
次に、差分攻撃および線形攻撃に対する耐性向上を実現した正方ＭＤＳ行列の生成およびＦ関数への設定例について説明する。
【０１６６】
差分攻撃に対する耐性を持つ暗号処理アルゴリズムは、先に、図１０〜図１３を参照して説明した処理、すなわち、Ｆ関数の線形処理部における線形変換に適用する正方ＭＤＳ行列を前述の処理例ａ１（図１１）〜ａ３（図１３）のいずれかの処理を適用して設定することで実現される。また、線形攻撃に対する耐性を持つ暗号処理アルゴリズムは、先に、図１０、および図１４、図１５を参照して説明した処理、すなわち、Ｆ関数の線形処理部における線形変換に適用する正方ＭＤＳ行列を前述の処理例ｂ１（図１４）、ｂ２（図１５）のいずれかの処理を適用して設定することで実現される。
【０１６７】
差分攻撃および線形攻撃に対する耐性向上を実現した正方ＭＤＳ行列は、
処理例ａ１（図１１）〜ａ３（図１３）のいずれかの処理と、
処理例ｂ１（図１４）、ｂ２（図１５）のいずれかの処理とを、
併せて実行して生成した正方ＭＤＳ行列を、図１０において説明した［ステップＳ２３］、［ステップＳ２４］の処理に従って、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成の各段のＦ関数部の線形変換部の線形変換処理に適用する行列として設定することで実現される。
【０１６８】
すなわち、
処理例ａ１と処理例ｂ１、
処理例ａ１と処理例ｂ２、
処理例ａ２と処理例ｂ１、
処理例ａ２と処理例ｂ２、
処理例ａ３と処理例ｂ１、
処理例ａ３と処理例ｂ２、
のいずれかの組み合わせによって、ｑ個の正方ＭＤＳ行列を生成し、２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成の各段のＦ関数部の線形変換部の線形変換処理に適用する行列として設定する。奇数段目については上位段から順にＬ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・としてｑ個の正方ＭＤＳ行列を繰り返し設定し、偶数段のＦ関数については、下位段のＦ関数から順に、Ｌ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定する。この設定により、差分攻撃および線形攻撃に対する耐性向上を実現した暗号処理が可能となる。
【０１６９】
図１７を参照して、差分攻撃および線形攻撃に対する耐性向上を実現した暗号処理を実現するための正方ＭＤＳ行列の生成処理の一例について説明する。この処理は、前述した処理例ａ２と、処理例ｂ２との組み合わせである。
【０１７０】
［ステップＳ６０１］
入力：必要な正方ＭＤＳの個数ｑ，拡大次数：ｎ，行列のサイズ：ｍとして、
ＧＦ（２ｎ）上で、ｑ個のｍ次正方ＭＤＳ行列Ｍ１，Ｍ２，...，Ｍｑをランダムに生成する。なお、図１７に示すフローでは、正方ＭＤＳの個数ｑ＝６，拡大次数：ｎ＝８，行列のサイズ：ｍ＝８の場合の処理例として示してある。
【０１７１】
［ステップＳ６０２］
ｑ個のｍ次正方ＭＤＳ行列Ｍ１，Ｍ２，...，Ｍｑに含まれるｑｍ個の列の任意のｍ個を取り出したときに、正方ＭＤＳ行列になっているかどうかをチェックする。チェックに通過したらステップＳ６０３に進む、そうでない場合はステップＳ６０１にもどる。
なお、正方ＭＤＳ行列とは、前述したように以下の性質を満たす行列をいう。
（ａ）正方行列である
（ｂ）行列に含まれるすべての部分行列（ｓｕｂｍａｔｒｉｘ）の行列式（ｄｅｔｅｒｍｉｎａｎｔ）が０でない、すなわち、ｄｅｔ（ｓｕｂｍａｔｒｉｘ）≠０
【０１７２】
［ステップＳ６０３］
ｑ個のｍ次正方ＭＤＳ行列Ｍ１，Ｍ２，...，Ｍｑの逆行列Ｍ１−１，Ｍ２−１，...，Ｍｑ−１を算出し、隣り合う２つの逆行列に含まれる２ｍの行ベクトルから任意のｍ本の行ベクトルを取り出したときに、正方ＭＤＳ行列になっているかどうかをチェックする。図１７中、ｔＲは、行ベクトルの転置ベクトルを示すものである。チェックに通過したらステップＳ６０４に進む、そうでない場合はステップＳ６０１にもどる。ただし、Ｍ１−１とＭｑ−１は、隣り合う行列とする。
【０１７３】
［ステップＳ６０４］
ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑを、ラウンド数２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号に適用する正方ＭＤＳ行列として出力する。
【０１７４】
以上のプロセスによって、ｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが生成される。なお、ｑ≦ｒである。
【０１７５】
この図１７に示す処理シーケンスに従った正方ＭＤＳ行列生成処理によって生成されたｑ個のｍ次正方ＭＤＳ行列Ｌ１，Ｌ２，...，Ｌｑが、先に、図１０を参照して説明した、［ステップＳ２３］、［ステップＳ２４］の処理に従って、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成の各段のＦ関数部の線形変換部の線形変換処理に適用する行列として設定される。すなわち、奇数段目については上位段から順にＬ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・としてｑ個の正方ＭＤＳ行列を繰り返し設定し、偶数段のＦ関数については、下位段のＦ関数から順に、Ｌ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定する。
【０１７６】
このように、偶数ラウンドの正方ＭＤＳ行列と奇数ラウンドの正方ＭＤＳ行列を互いに逆順に配置することによって、暗号化処理と復号処理は鍵の順序を入れ替える処理を除き同一であることが保証される。
【０１７７】
本構成により、
（ａ）各Ｆ関数の線形変換行列は正方ＭＤＳであること、
（ｂ）暗号化関数内の奇数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが正方ＭＤＳ行列であること、
（ｃ）偶数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが正方ＭＤＳ行列であること、
これら（ａ）〜（ｃ）が保証されるため、複数段のラウンド数を持つＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成において、連続する２ｑ−１ラウンドにおいて、ｍ個以下のアクティブＳボックスの寄与による同時差分キャンセルは発生しないことが保証される。
さらに、
（ｄ）正方ＭＤＳの性質から、ａ個（ａ≦ｍ）のアクティブＳボックスの寄与によって得られる差分値における非ゼロの要素数はｍ＋１−ａ個以上になることが保証される。よって暗号化関数全体のアクティブＳボックス数の最小値が増大する。
さらに、
（ｅ）暗号化関数内の奇数ラウンド内に連続して含まれる線形変換行列、および偶数ラウンド内に連続して含まれる線形変換行列の逆行列の任意のｍ個の列ベクトルが正方ＭＤＳ行列となることが保証される。このことにより、線形攻撃における線形近似による解析困難性を高めることが可能となり、解析の困難性、すなわち鍵の解析の困難な安全性の高い暗号処理が実現される。
【０１７８】
このように、本処理例によって、差分攻撃および線形攻撃の双方の解析の困難性が向上し、鍵の解析の困難な安全性の高い暗号処理が実現される。なお、図１７に示した例は、前述したように、先に説明した処理例ａ２と処理例ｂ２の組み合わせによる正方ＭＤＳ行列の生成例であるが、その他、処理例ａ１と処理例ｂ１、処理例ａ１と処理例ｂ２、処理例ａ２と処理例ｂ１、処理例ａ３と処理例ｂ１、処理例ａ３と処理例ｂ２とを組み合わせてｑ個の正方ＭＤＳ行列の生成を行い、段数（ラウンド数）が２ｒのＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成の各段のＦ関数部の線形変換部の線形変換処理に適用する行列として、奇数段目については上位段から順にＬ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・としてｑ個の正方ＭＤＳ行列を繰り返し設定し、偶数段のＦ関数については、下位段のＦ関数から順に、Ｌ１，Ｌ２，・・，Ｌｑ，Ｌ１，Ｌ２・・として、ｑ個の正方ＭＤＳ行列を繰り返し設定することによっても、差分攻撃および線形攻撃の双方の解析の困難性が高く、鍵の解析の困難な安全性の高い暗号処理が実現可能である。
【０１７９】
これまでの説明では、分かりやすさを優先して線形変換行列をＧＦ（２ｎ）上で定義されるｍ×ｍの行列として、ｍｎビットからｍｎビットへのデータ変換演算としてきたが、差分解析および線形解析に対する同様な効果がＧＦ（２）上で定義されるｍｎ×ｍｎの行列を用いた場合でも有効である。実際、任意のＧＦ（２ｎ）上の行列は同じ変換を表すＧＦ（２）上の行列に一対一で対応させることができる。よってＧＦ（２）上の行列はより一般的な表現を表しているといえる。ＧＦ（２）上では行と列の本数がｍｎ本ずつと、ＧＦ（２ｎ）の場合と比べてｎ倍となる。このためＧＦ（２ｎ）上の行列の１行目は、ＧＦ（２）上の行列の１からｎ行目に対応し、1列目は１からｎ列目に対応している。つまりi行目は（i−１）＋１行目から（i−１）＋ｎ行目に対応し、i列目は（i−１）＋１列目から（i−１）＋ｎ列目に対応している。よって、ＧＦ（２ｎ）上の行や列を取り出してくる操作には、ＧＦ（２）上で定義される行列を用いる場合は、対応するｎ行分もしくはｎ列分を取り出すという操作を対応させればよい。ＧＦ（２ｎ）上のｍ本の行や列を取り出す操作は、ＧＦ（２）上ではｎ本の行や列をｍ回取り出すことになり、結果としてｍｎ×ｍｎの行列を得ることができる。以上の対応付けにより、ＧＦ（２）上で定義される行列に容易に拡張することができる。
【０１８０】
［４．本発明に係る暗号処理アルゴリズム］
次に、本発明に係る暗号処理アルゴリズムについて説明する。
上述の項目［３．耐性を向上させた暗号処理アルゴリズム構成例］において説明したように、非線形変換部および線形変換部を有するＳＰＮ型のＦ関数の複数ラウンド繰り返し構成において、特定の条件を満足する正方ＭＤＳ（Ｍａｘｉｍｕｍ  Ｄｉｓｔａｎｃｅ  Ｓｅｐａｒａｂｌｅ）行列を適用した線形変換処理を行なう構成とすることで、暗号解析処理、攻撃処理として知られる線形解析、差分解析に対する耐性を向上させることが可能であることを説明した。
【０１８１】
しかし、上述した処理構成では、利用できる行列が限定されてしまうという問題がある。すなわち、前述した処理例ａ１〜ａ３において説明した差分攻撃に対する耐性向上を図るための各Ｆ関数に設定する線形変換行列の条件としては、
（Ａ１）各Ｆ関数の線形変換行列は正方ＭＤＳであること、
（Ａ２）暗号化関数内の奇数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが独立または正方ＭＤＳ行列であること、
（Ａ３）偶数ラウンド内の少なくとも連続するｑ個のＦ関数に含まれる線形変換行列の任意のｍ個の列ベクトルが独立または正方ＭＤＳ行列であること、
これらの条件を満足させることが必要であった。
【０１８２】
また、前述した処理例ｂ１〜ｂ２において説明した線形攻撃に対する耐性向上を図るための各Ｆ関数の線形変換行列の条件としては、
（Ｂ１）各Ｆ関数の線形変換行列は正方ＭＤＳであること、
（Ｂ２）暗号化関数内の奇数ラウンド内に連続して含まれる線形変換行列、および偶数ラウンド内に連続して含まれる線形変換行列の逆行列の任意のｍ個の列ベクトルが正方ＭＤＳ行列となること、
これらの条件を満足させることが必要であった。
【０１８３】
さらに、差分攻撃および線形攻撃の双方に対する耐性を持つ構成とするためには、上述した（Ａ１）〜（Ａ３）および（Ｂ１）〜（Ｂ２）のすべての条件を満足させることが必要となり、利用できる行列の候補数が絞られてしまうという問題がある。
【０１８４】
先に図１、図２を参照して説明したように、Ｆｅｉｓｔｅｌ構造は、変換関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。初めに、２ｍｎビットの平文を、ｍｎビットの２つの入力データＰＬ（Plain-Left）１０１，ＰＲ(Plain-Right)１０２に分割し、これを入力値として、Ｆ関数（ラウンド関数）１２０をｒ段繰り返す。
【０１８５】
例えば、図１に示す第１番目のラウンドでは、ｍｎビットの入力データＸと、鍵生成部（図示せず）から入力されるｍｎビットのラウンド鍵Ｋ１１０３がＦ関数１２０に入力され、Ｆ関数１２０におけるデータ変換処理の後にｍｎビットのデータＹを出力する。出力はもう片方の前段からの入力データ（第１段の場合は入力データＰＬ）と排他的論理和部１０４において、排他的論理和演算がなされ、ｍｎビットの演算結果が次のラウンド関数へと出力される。この処理、すなわちＦ関数を定められたラウンド数（ｒ）だけ繰り返し適用して暗号化処理が完了し、暗号文の分割データＣＬ（Cipher-Left）、ＣＲ（Cipher-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)
６０２  メモリ
６０３  暗号処理部
６０４  乱数発生器
６０５  送受信部
【図１】
2006301567.tif 000004
【図２】
2006301567.tif 000005
【図３】
2006301567.tif 000006
【図４】
2006301567.tif 000007
【図５】
2006301567.tif 000008
【図６】
2006301567.tif 000009
【図７】
2006301567.tif 000010
【図８】
2006301567.tif 000011
【図９】
2006301567.tif 000012
【図１０】
2006301567.tif 000013
【図１１】
2006301567.tif 000014
【図１２】
2006301567.tif 000015
【図１３】
2006301567.tif 000016
【図１４】
2006301567.tif 000017
【図１５】
2006301567.tif 000018
【図１６】
2006301567.tif 000019
【図１７】
2006301567.tif 000020
【図１８】
2006301567.tif 000021