(57)【要約】【課題】共通鍵ブロック暗号における暗号強度評価処理を確実に実行する装置、方法を提供する。【解決手段】共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理関数の暗号強度解析において、上界により近い確率のパスを算出する。差分データの差分値がゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを入力し、暗号処理部をレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割し、各チェインに含まれるデータに基づく差分解析を実行して差分特性確率：ＤＣＰを計算し、最も高い値を持つ差分特性確率：ＤＣＰを、暗号強度指標値としての最大差分特性確率ＭＤＣＰＴとして算出する。【選択図】  図５
2004153733.tif 000002
【特許請求の範囲】
【請求項１】
暗号処理アルゴリズムの暗号強度指標算出方法であり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対して差分データ入力に基づく差分パス解析ステップを有し、
前記差分パス解析ステップは、
差分データの差分値がゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを入力するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パス入力ステップと、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割ステップと、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の線形変換部出力であるＹｉの半分の出力Ｙ２ｉ−１、次ラウンドへの入力値としてのＸｉの半分の入力値（Ｘ２ｉ）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ−１，ΔＸ２ｉ（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定ステップと、
前記等式設定ステップにおいて設定された等式に含まれるすべてのｎビット差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定ステップと、前記連立一次方程式設定ステップにおいて設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換えステップと、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出ステップと、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得ステップと、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出ステップと、
前記等式設定ステップ乃至解集合算出ステップをレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ，ΔＸ２ｉ−１（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出ステップと、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して差分特性確率：ＤＣＰを計算し、最も高い値を持つ差分特性確率：ＤＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスＴに対する最大差分特性確率ＭＤＣＰＴとして算出する最大差分特性確率算出ステップと、
を有することを特徴とする暗号強度指標算出方法。
【請求項２】
前記最大差分特性確率算出ステップにおいて、
トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分＝１が入力されるＳ−ｂｏｘの個数をａ個とし、それぞれＳ−ｂｏｘの入出力をΔｘｉ，Δｙｉ（ｉ≦ｉ≦ａ）としたとき、前記差分特性確率ＤＣＰを、下式、
【数１】
2004153733.tif 000019
（ただし、ＤＰｓ（ΔＡ，ΔＢ）をｓ−ｂｏｘに差分ΔＡが入力されたときに差分ΔＢが出力される確立とする）
によって算出することを特徴とする請求項１に記載の暗号強度指標算出方法。
【請求項３】
暗号処理アルゴリズムの暗号強度指標算出方法であり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対してマスク処理データ入力に基づく線形パス解析ステップを有し、
前記線形パス解析ステップは、
マスク処理データがゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値を入力するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パス入力ステップと、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割ステップと、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）入力であるＴｉの半分の入力（Ｔ２ｉ）、次ラウンドへの入力値としてのＺｉの半分の入力値（Ｚ２ｉ−１）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ−１，ΓＳ２ｉ−１（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΓＺ２ｉ−１［ｊ］，ΓＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、マスク値：ΓＰＲ［ｊ］，ΓＴ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定ステップと、
前記等式設定ステップにおいて設定された等式に含まれるすべてのｎビット差分：ΓＰＲ［ｊ］，ΓＳ２ｉ−１［ｊ］，ΓＴ２ｉ［ｊ］，ΓＺ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定ステップと、
前記連立一次方程式設定ステップにおいて設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換えステップと、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出ステップと、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得ステップと、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出ステップと、
前記等式設定ステップ乃至解集合算出ステップをレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ，ΓＳ２ｉ（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出ステップと、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して線形特性確率：ＬＣＰを計算し、最も高い値を持つ線形特性確率：ＬＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスＴに対する最大線形特性確率ＭＬＣＰＴとして算出する最大線形特性確率算出ステップと、
を有することを特徴とする暗号強度指標算出方法。
【請求項４】
前記最大線形特性確率算出ステップにおいて、
トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分＝１が入力されるＳ−ｂｏｘの個数をａ個とし、それぞれＳ−ｂｏｘの入出力をΓｘｉ，Γｙｉ（ｉ≦ｉ≦ａ）としたとき、前記差分特性確率ＬＣＰを、下式、
【数２】
2004153733.tif 000020
（ただし、ＬＰｓ（ΓＡ，ΓＢ）を
【数３】
2004153733.tif 000021
によって定義される確率とする）
によって算出することを特徴とする請求項３に記載の暗号強度指標算出方法。
【請求項５】
暗号処理アルゴリズムの暗号強度評価処理装置であり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔａｌ構造からなる暗号処理手段に対して差分データを入力し、データ解析を実行する差分パス解析手段を有し、
前記差分パス解析手段は、
差分データの差分値がゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを入力し、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割処理と、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の線形変換部出力であるＹｉの半分の出力Ｙ２ｉ−１、次ラウンドへの入力値としてのＸｉの半分の入力値（Ｘ２ｉ）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ−１，ΔＸ２ｉ（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定処理と、
前記等式設定処理において設定された等式に含まれるすべてのｎビット差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定処理と、
前記連立一次方程式設定処理において設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換え処理と、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出処理と、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得処理と、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出処理と、
前記等式設定処理乃至解集合算出処理をレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ，ΔＸ２ｉ−１（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出処理と、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して差分特性確率：ＤＣＰを計算し、最も高い値を持つ差分特性確率：ＤＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスＴに対する最大差分特性確率ＭＤＣＰＴとして算出する最大差分特性確率算出処理と、
を実行する構成であることを特徴とする暗号強度評価処理装置。
【請求項６】
前記差分パス解析手段は、
トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分＝１が入力されるＳ−ｂｏｘの個数をａ個とし、それぞれＳ−ｂｏｘの入出力をΔｘｉ，Δｙｉ（ｉ≦ｉ≦ａ）としたとき、前記差分特性確率ＤＣＰを、下式、
【数４】
2004153733.tif 000022
（ただし、ＤＰｓ（ΔＡ，ΔＢ）をｓ−ｂｏｘに差分ΔＡが入力されたときに差分ΔＢが出力される確立とする）
によって算出する処理を実行する構成であることを特徴とする請求項５に記載の暗号強度評価処理装置。
【請求項７】
暗号処理アルゴリズムの暗号強度評価処理装置であり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対してマスク処理データを入力し、データ解析を実行する線形パス解析手段を有し、
前記線形パス解析手段は、
マスク処理データがゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値を入力するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスを入力し、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割処理と、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）入力であるＴｉの半分の入力（Ｔ２ｉ）、次ラウンドへの入力値としてのＺｉの半分の入力値（Ｚ２ｉ−１）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ−１，ΓＳ２ｉ−１（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΓＺ２ｉ−１［ｊ］，ΓＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、マスク値：ΓＰＲ［ｊ］，ΓＴ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定処理と、
前記等式設定処理において設定された等式に含まれるすべてのｎビット差分：ΓＰＲ［ｊ］，ΓＳ２ｉ−１［ｊ］，ΓＴ２ｉ［ｊ］，ΓＺ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定処理と、
前記連立一次方程式設定処理において設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換え処理と、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出処理と、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得処理と、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出処理と、
前記等式設定処理乃至解集合算出処理をレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ，ΓＳ２ｉ（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出処理と、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して線形特性確率：ＬＣＰを計算し、最も高い値を持つ線形特性確率：ＬＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスＴに対する最大線形特性確率ＭＬＣＰＴとして算出する最大線形特性確率算出処理と、
を有することを特徴とする暗号強度評価処理装置。
【請求項８】
前記線形パス解析手段は、
トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分＝１が入力されるＳ−ｂｏｘの個数をａ個とし、それぞれＳ−ｂｏｘの入出力をΓｘｉ，Γｙｉ（ｉ≦ｉ≦ａ）としたとき、前記差分特性確率ＬＣＰを、下式、
【数５】
2004153733.tif 000023
（ただし、ＬＰｓ（ΓＡ，ΓＢ）を
【数６】
2004153733.tif 000024
によって定義される確率とする）
によって算出する処理を実行する構成であることを特徴とする請求項７に記載の暗号強度評価処理装置。
【請求項９】
暗号処理アルゴリズムの暗号強度指標算出処理を実行するコンピュータ・プログラムであり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対して差分データ入力に基づく差分パス解析ステップを有し、
前記差分パス解析ステップは、
差分データの差分値がゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを入力するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パス入力ステップと、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割ステップと、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の線形変換部出力であるＹｉの半分の出力Ｙ２ｉ−１、次ラウンドへの入力値としてのＸｉの半分の入力値（Ｘ２ｉ）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ−１，ΔＸ２ｉ（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定ステップと、
前記等式設定ステップにおいて設定された等式に含まれるすべてのｎビット差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定ステップと、前記連立一次方程式設定ステップにおいて設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換えステップと、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出ステップと、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得ステップと、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出ステップと、
前記等式設定ステップ乃至解集合算出ステップをレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ，ΔＸ２ｉ−１（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出ステップと、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して差分特性確率：ＤＣＰを計算し、最も高い値を持つ差分特性確率：ＤＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスＴに対する最大差分特性確率ＭＤＣＰＴとして算出する最大差分特性確率算出ステップと、
を含むことを特徴とするコンピュータ・プログラム。
【請求項１０】
暗号処理アルゴリズムの暗号強度指標算出処理を実行するコンピュータ・プログラムであり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対してマスク処理データ入力に基づく線形パス解析ステップを有し、
前記線形パス解析ステップは、
マスク処理データがゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値を入力するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パス入力ステップと、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割ステップと、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）入力であるＴｉの半分の入力（Ｔ２ｉ）、次ラウンドへの入力値としてのＺｉの半分の入力値（Ｚ２ｉ−１）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ−１，ΓＳ２ｉ−１（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΓＺ２ｉ−１［ｊ］，ΓＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、マスク値：ΓＰＲ［ｊ］，ΓＴ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定ステップと、
前記等式設定ステップにおいて設定された等式に含まれるすべてのｎビット差分：ΓＰＲ［ｊ］，ΓＳ２ｉ−１［ｊ］，ΓＴ２ｉ［ｊ］，ΓＺ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定ステップと、
前記連立一次方程式設定ステップにおいて設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換えステップと、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出ステップと、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得ステップと、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出ステップと、
前記等式設定ステップ乃至解集合算出ステップをレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ，ΓＳ２ｉ（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出ステップと、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して線形特性確率：ＬＣＰを計算し、最も高い値を持つ線形特性確率：ＬＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスＴに対する最大線形特性確率ＭＬＣＰＴとして算出する最大線形特性確率算出ステップと、
を含むことを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号強度指標算出方法、および暗号強度評価処理装置、並びにコンピュータ・プログラムに関する。さらに、詳細には、共通鍵ブロック暗号の安全性・強度を評価するための指標を算出する暗号強度指標算出方法、および暗号強度評価処理装置、並びにコンピュータ・プログラムに関する。
【０００２】
【従来の技術】
暗号処理アルゴリズムには様々なものがあるが、大きく分類すると、暗号化鍵と復号化鍵を異なる鍵、例えば公開鍵と秘密鍵として設定する公開鍵暗号方式と、暗号化鍵と復号化鍵を共通の鍵として設定する共通鍵暗号方式とに分類される。
【０００３】
共通鍵暗号方式にも様々なアルゴリズムがあるが、その１つに共通鍵をベースとして複数の鍵を生成して、生成した複数の鍵を用いて暗号処理を繰り返し実行する方式がある。このような鍵生成方式を適用したアルゴリズムの代表的なものが共通鍵ブロック暗号方式である。
【０００４】
共通鍵ブロック暗号のアルゴリズムは、主として、ラウンド関数部と鍵スケジュール部とに分けることができる。従来、共通鍵ブロック暗号を設計する際には、鍵関連攻撃等に対する安全性を確保するため、暗号の設計者は、ラウンド鍵間の単純な関係式が成立しないように、注意深く鍵スケジュール部の設計を行うことが要請されてきた。
【０００５】
共通鍵ブロック暗号に対する代表的な攻撃法である差分攻撃および線形攻撃に対する安全性を示すためには、それぞれ最大差分特性確率および最大線形特性確率と呼ばれる暗号系に固有の値を導出し安全性の根拠とする手段が有効である。高い特性確率が存在すると攻撃に利用されてしまうことから、低い特性確率しかもたないようなアルゴリズムを設計することが望まれている。しかしながら一般的にブロックサイズが大きくなるにつれてそれら特性確率を求める計算量が莫大になるため、安全性の評価が困難となっている。
【０００６】
ひとつの代替案としてより取り扱いの容易なトランケイテッド（Ｔｒｕｎｃａｔｅｄ）表現されたパスを使って最大差分確率および最大線形確率の上界を求める方法が提案されている。しかしその方式は安全性の下界を示しているもののあくまでも限度を示すものであり実際の暗号系の強度を十分に表現しているものとは言えなかった。またこのような評価法では具体的な値を持つ差分パス、線形近似を用いた攻撃に対する安全性評価が不可能であるという問題がある。
【０００７】
【発明が解決しようとする課題】
本発明は、上述の問題点に鑑みてなされたものであり、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを用いて上界が導出されたＳＰＮ型のＦ関数を持つ共通鍵ブロック暗号において、その上界に近い特性確率をもつような差分パス、線形近似の導出を可能とする暗号強度指標算出方法、および暗号強度評価処理装置、並びにコンピュータ・プログラム提供することを目的とする。
【０００８】
本発明ではトランケイテッド差分パスを活用して、具体的な値を持つ差分パス、線形近似を導出する。この手法のメリットとしては、上界に近い確率をもつ差分パス、線形近似を得ることが可能となることである。よって差分攻撃、線形攻撃に対する信頼性の高い安全性評価結果を示すことが可能となる。
【０００９】
【課題を解決するための手段】
本発明の第１の側面は、
暗号処理アルゴリズムの暗号強度指標算出方法であり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対して差分データ入力に基づく差分パス解析ステップを有し、
前記差分パス解析ステップは、
差分データの差分値がゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを入力するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パス入力ステップと、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割ステップと、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の線形変換部出力であるＹｉの半分の出力Ｙ２ｉ−１、次ラウンドへの入力値としてのＸｉの半分の入力値（Ｘ２ｉ）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ−１，ΔＸ２ｉ（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定ステップと、
前記等式設定ステップにおいて設定された等式に含まれるすべてのｎビット差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定ステップと、前記連立一次方程式設定ステップにおいて設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換えステップと、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出ステップと、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得ステップと、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出ステップと、
前記等式設定ステップ乃至解集合算出ステップをレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ，ΔＸ２ｉ−１（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出ステップと、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して差分特性確率：ＤＣＰを計算し、最も高い値を持つ差分特性確率：ＤＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスＴに対する最大差分特性確率ＭＤＣＰＴとして算出する最大差分特性確率算出ステップと、
を有することを特徴とする暗号強度指標算出方法にある。
【００１０】
さらに、本発明の暗号強度指標算出方法の一実施態様において、前記最大差分特性確率算出ステップにおいて、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分＝１が入力されるＳ−ｂｏｘの個数をａ個とし、それぞれＳ−ｂｏｘの入出力をΔｘｉ，Δｙｉ（ｉ≦ｉ≦ａ）としたとき、前記差分特性確率ＤＣＰを、下式、
【数７】
2004153733.tif 000003
（ただし、ＤＰｓ（ΔＡ，ΔＢ）をｓ−ｂｏｘに差分ΔＡが入力されたときに差分ΔＢが出力される確立とする）
によって算出することを特徴とする。
【００１１】
さらに、本発明の第２の側面は、
暗号処理アルゴリズムの暗号強度指標算出方法であり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対してマスク処理データ入力に基づく線形パス解析ステップを有し、
前記線形パス解析ステップは、
マスク処理データがゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値を入力するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パス入力ステップと、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割ステップと、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）入力であるＴｉの半分の入力（Ｔ２ｉ）、次ラウンドへの入力値としてのＺｉの半分の入力値（Ｚ２ｉ−１）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ−１，ΓＳ２ｉ−１（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΓＺ２ｉ−１［ｊ］，ΓＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、マスク値：ΓＰＲ［ｊ］，ΓＴ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定ステップと、
前記等式設定ステップにおいて設定された等式に含まれるすべてのｎビット差分：ΓＰＲ［ｊ］，ΓＳ２ｉ−１［ｊ］，ΓＴ２ｉ［ｊ］，ΓＺ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定ステップと、
前記連立一次方程式設定ステップにおいて設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換えステップと、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出ステップと、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得ステップと、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出ステップと、
前記等式設定ステップ乃至解集合算出ステップをレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ，ΓＳ２ｉ（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出ステップと、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して線形特性確率：ＬＣＰを計算し、最も高い値を持つ線形特性確率：ＬＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスＴに対する最大線形特性確率ＭＬＣＰＴとして算出する最大線形特性確率算出ステップと、
を有することを特徴とする暗号強度指標算出方法にある。
【００１２】
さらに、本発明の暗号強度指標算出方法の一実施態様において、前記最大線形特性確率算出ステップにおいて、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分＝１が入力されるＳ−ｂｏｘの個数をａ個とし、それぞれＳ−ｂｏｘの入出力をΓｘｉ，Γｙｉ（ｉ≦ｉ≦ａ）としたとき、前記差分特性確率ＬＣＰを、下式、
【数８】
2004153733.tif 000004
（ただし、ＬＰｓ（ΓＡ，ΓＢ）を
【数９】
2004153733.tif 000005
によって定義される確率とする）
によって算出することを特徴とする。
【００１３】
さらに、本発明の第３の側面は、
暗号処理アルゴリズムの暗号強度評価処理装置であり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔａｌ構造からなる暗号処理手段に対して差分データを入力し、データ解析を実行する差分パス解析手段を有し、
前記差分パス解析手段は、
差分データの差分値がゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを入力し、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割処理と、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の線形変換部出力であるＹｉの半分の出力Ｙ２ｉ−１、次ラウンドへの入力値としてのＸｉの半分の入力値（Ｘ２ｉ）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ−１，ΔＸ２ｉ（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定処理と、
前記等式設定処理において設定された等式に含まれるすべてのｎビット差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定処理と、
前記連立一次方程式設定処理において設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換え処理と、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出処理と、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得処理と、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出処理と、
前記等式設定処理乃至解集合算出処理をレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ，ΔＸ２ｉ−１（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出処理と、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して差分特性確率：ＤＣＰを計算し、最も高い値を持つ差分特性確率：ＤＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスＴに対する最大差分特性確率ＭＤＣＰＴとして算出する最大差分特性確率算出処理と、
を実行する構成であることを特徴とする暗号強度評価処理装置にある。
【００１４】
さらに、本発明の暗号強度評価処理装置の一実施態様において、前記差分パス解析手段は、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分＝１が入力されるＳ−ｂｏｘの個数をａ個とし、それぞれＳ−ｂｏｘの入出力をΔｘｉ，Δｙｉ（ｉ≦ｉ≦ａ）としたとき、前記差分特性確率ＤＣＰを、下式、
【数１０】
2004153733.tif 000006
（ただし、ＤＰｓ（ΔＡ，ΔＢ）をｓ−ｂｏｘに差分ΔＡが入力されたときに差分ΔＢが出力される確立とする）
によって算出する処理を実行する構成であることを特徴とする。
【００１５】
さらに、本発明の第４の側面は、
暗号処理アルゴリズムの暗号強度評価処理装置であり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対してマスク処理データを入力し、データ解析を実行する線形パス解析手段を有し、
前記線形パス解析手段は、
マスク処理データがゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値を入力するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスを入力し、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割処理と、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）入力であるＴｉの半分の入力（Ｔ２ｉ）、次ラウンドへの入力値としてのＺｉの半分の入力値（Ｚ２ｉ−１）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ−１，ΓＳ２ｉ−１（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΓＺ２ｉ−１［ｊ］，ΓＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、マスク値：ΓＰＲ［ｊ］，ΓＴ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定処理と、
前記等式設定処理において設定された等式に含まれるすべてのｎビット差分：ΓＰＲ［ｊ］，ΓＳ２ｉ−１［ｊ］，ΓＴ２ｉ［ｊ］，ΓＺ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定処理と、
前記連立一次方程式設定処理において設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換え処理と、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出処理と、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得処理と、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出処理と、
前記等式設定処理乃至解集合算出処理をレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ，ΓＳ２ｉ（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出処理と、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して線形特性確率：ＬＣＰを計算し、最も高い値を持つ線形特性確率：ＬＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスＴに対する最大線形特性確率ＭＬＣＰＴとして算出する最大線形特性確率算出処理と、
を有することを特徴とする暗号強度評価処理装置にある。
【００１６】
さらに、本発明の暗号強度評価処理装置の一実施態様において、前記線形パス解析手段は、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分＝１が入力されるＳ−ｂｏｘの個数をａ個とし、それぞれＳ−ｂｏｘの入出力をΓｘｉ，Γｙｉ（ｉ≦ｉ≦ａ）としたとき、前記差分特性確率ＬＣＰを、下式、
【数１１】
2004153733.tif 000007
（ただし、ＬＰｓ（ΓＡ，ΓＢ）を
【数１２】
2004153733.tif 000008
によって定義される確率とする）
によって算出する処理を実行する構成であることを特徴とする。
【００１７】
さらに、本発明の第５の側面は、
暗号処理アルゴリズムの暗号強度指標算出処理を実行するコンピュータ・プログラムであり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対して差分データ入力に基づく差分パス解析ステップを有し、
前記差分パス解析ステップは、
差分データの差分値がゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを入力するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パス入力ステップと、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割ステップと、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の線形変換部出力であるＹｉの半分の出力Ｙ２ｉ−１、次ラウンドへの入力値としてのＸｉの半分の入力値（Ｘ２ｉ）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ−１，ΔＸ２ｉ（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定ステップと、
前記等式設定ステップにおいて設定された等式に含まれるすべてのｎビット差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定ステップと、前記連立一次方程式設定ステップにおいて設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換えステップと、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出ステップと、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得ステップと、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出ステップと、
前記等式設定ステップ乃至解集合算出ステップをレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ，ΔＸ２ｉ−１（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出ステップと、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して差分特性確率：ＤＣＰを計算し、最も高い値を持つ差分特性確率：ＤＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスＴに対する最大差分特性確率ＭＤＣＰＴとして算出する最大差分特性確率算出ステップと、
を含むことを特徴とするコンピュータ・プログラムにある。
【００１８】
さらに、本発明の第６の側面は、
暗号処理アルゴリズムの暗号強度指標算出処理を実行するコンピュータ・プログラムであり、
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対してマスク処理データ入力に基づく線形パス解析ステップを有し、
前記線形パス解析ステップは、
マスク処理データがゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値を入力するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パス入力ステップと、
前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割ステップと、
ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）入力であるＴｉの半分の入力（Ｔ２ｉ）、次ラウンドへの入力値としてのＺｉの半分の入力値（Ｚ２ｉ−１）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ−１，ΓＳ２ｉ−１（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΓＺ２ｉ−１［ｊ］，ΓＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、マスク値：ΓＰＲ［ｊ］，ΓＴ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定ステップと、
前記等式設定ステップにおいて設定された等式に含まれるすべてのｎビット差分：ΓＰＲ［ｊ］，ΓＳ２ｉ−１［ｊ］，ΓＴ２ｉ［ｊ］，ΓＺ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定ステップと、
前記連立一次方程式設定ステップにおいて設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換えステップと、
前記行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出ステップと、
変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得ステップと、
前記自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出ステップと、
前記等式設定ステップ乃至解集合算出ステップをレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ，ΓＳ２ｉ（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出ステップと、
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して線形特性確率：ＬＣＰを計算し、最も高い値を持つ線形特性確率：ＬＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスＴに対する最大線形特性確率ＭＬＣＰＴとして算出する最大線形特性確率算出ステップと、
を含むことを特徴とするコンピュータ・プログラムにある。
【００１９】
【作用】
本発明の構成によれば、共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理関数の暗号強度解析において、上界により近い確率のパスを算出することが可能となる。
【００２０】
また、本発明の構成によれば、共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対して差分データ入力に基づく差分パス解析において、差分データの差分値がゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを入力し、暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割し、各チェインに含まれるデータに基づく差分解析を実行して差分特性確率：ＤＣＰを計算し、最も高い値を持つ差分特性確率：ＤＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスＴに対する最大差分特性確率ＭＤＣＰＴとして算出することが可能となる。
【００２１】
さらに、本発明の構成によれば、共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対して、マスク処理データがゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値を入力し、暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割し、各チェインに含まれるデータに基づく解析を実行して線形特性確率：ＬＣＰを計算し、最も高い値を持つ線形特性確率：ＬＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスＴに対する最大線形特性確率ＭＬＣＰＴとして算出することが可能となる。
【００２２】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能な汎用コンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記憶媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００２３】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【００２４】
【発明の実施の形態】
以下、本発明の暗号強度指標算出方法、および暗号強度評価処理装置、並びにコンピュータ・プログラムについて詳細に説明する。
【００２５】
［１．Ｆｅｉｓｔｅｌ構造］
まず、本発明における暗号強度評価処理対象となるＦｅｉｓｔｅｌ構造と呼ばれる代表的な共通鍵ブロック暗号の構造について、図１を参照して説明する。
【００２６】
Ｆｅｉｓｔｅｌ構造は、変換関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。平文の長さを２ｍｎビットとする。初めにｍｎビットの２つのデータＰＬ（Ｐｌａｉｎ−Ｌｅｆｔ），ＰＲ（Ｐｌａｉｎ−Ｒｉｇｈｔ）に分割し、これを入力値とする。
【００２７】
Ｆｅｉｓｔｅｌ構造はラウンド関数とよばれる基本構造の繰り返しで表現され、各ラウンドに含まれるデータ変換関数はＦ関数と呼ばれる。図１の構成では、ラウンド関数がｒ段繰り返された構成例を示している。
【００２８】
ｉ番目のラウンド関数では、前段から入力される２つの入力データＸｉ（＝Ｗｉ），Ｚｉのうち左側のデータＸｉ（＝Ｗｉ）と、鍵生成部（図示せず）から入力されるラウンド鍵ＫｉがＦ関数に入力され、Ｆ関数におけるデータ変換処理の後にデータＹｉを出力する。Ｆ関数の出力はもう片方の入力データＺｉと排他的論理和され、Ｘｉとともに次のラウンド関数へと出力とされる。この処理、すなわちラウンド関数を定められたラウンド数（ｒ）だけ繰り返し適用して暗号化処理が完了し、暗号文の分割データＣＬ（Ｃｉｐｈｅｒ−Ｌｅｆｔ）、ＣＲ（Ｃｉｐｈｅｒ−Ｒｉｇｈｔ）が出力される。
【００２９】
本発明の構成において、各ラウンド関数に設定されるＦ関数は、図２に示すようなＳＰＮ型の構成をもつものとする。ＳＰＮ型のＦ関数は、鍵加算部１２１、非線形変換部１２２、線形変換部１２３により構成される。
【００３０】
例えば、ｉ番目のラウンドのＦ関数に入力されたデータＷｉはまず、ｍ個のｎビットデータＷｉ［１］，Ｗｉ［２］，．．．，Ｗｉ［ｍ］に分割され、同様に分割された鍵データＫｉ［１］，Ｋｉ［２］，．．．，Ｋｉ［ｍ］と、鍵加算部１２１において、それぞれ排他的論理和されＴｉ［１］，Ｔｉ［２］，．．．，Ｔｉ［ｍ］となり、非線形変換部１２２に入力される。
【００３１】
つづいて非線形変換部１２２において、各ｎビットデータＴｉ［１］，Ｔｉ［２］，．．．，Ｔｉ［ｍ］はＳ−ｂｏｘと呼ばれるあらかじめ定められた置換表により変換され、Ｓｉ［１］，Ｓｉ［２］，．．．，Ｓｉ［ｍ］を線形変換部１２３に出力する。
【００３２】
Ｓｉ［１］，Ｓｉ［２］，．．．，Ｓｉ［ｍ］は線形変換部１２３において、線形変換処理が実行され、その出力がＦ関数の出力Ｙｉ［１］，Ｙｉ［２］，．．．，Ｙｉ［ｍ］となる。
【００３３】
線形変換部１２３の具体的線形変換処理例を図３に示す。非線形変換部から入力されたｍ個のｎビットデータＳｉ［１］，Ｓｉ［２］，．．．，Ｓｉ［ｍ］に対してあらかじめ定められた行列の演算の適用により線形変換が施されＹｉ［１］，Ｙｉ［２］，．．．，Ｙｉ［ｍ］に変換される。ただし、このとき各データの行列の要素に対する線形演算はあらかじめ定められた体ＧＦ（２ｎ）上で行われるものとする。
【００３４】
［２．差分パス］
次に、差分パスについて説明する。２つのデータを排他的論理和したときの値をその２つのデータの差分と呼び、本明細書においては、差分を表す場合にはΔ（デルタ）記号をつけて表す。
【００３５】
前述したように、非線形変換部１２２において、鍵加算部１２１からの出力データとしての各ｎビットデータＴｉ［１］，Ｔｉ［２］，．．．，Ｔｉ［ｍ］はＳ−ｂｏｘと呼ばれるあらかじめ定められた置換表により変換され、Ｓｉ［１］，Ｓｉ［２］，．．．，Ｓｉ［ｍ］を線形変換部１２３に出力する。
【００３６】
Ｓ−ｂｏｘには差分確率が定義される。ＤＰｓ（ΔＡ，ΔＢ）をＳ−ｂｏｘに差分ΔＡが入力されたときに差分ΔＢが出力される確率とし、それを差分確率と呼ぶ。ＤＰｓ（ΔＡ，ΔＢ）は実際のＳ−ｂｏｘの置換表を使って以下の（式１）のように計算される。なお、ここでは説明を簡単にするためＳ−ｂｏｘは一種類しか用いていないが、Ｓ−ｂｏｘが複数種類ある場合もそれぞれのＳ−ｂｏｘの置換表を用いて同様に定義される。
【００３７】
【数１３】
2004153733.tif 000009
【００３８】
図４に、ｒ段のラウンド関数からなる暗号化関数における差分の伝播を表現した差分パスの例を示す。１段目のラウンド関数２１０にΔＸ１，ΔＺ１で表される差分をもつ平文のペアを入力すると、１段目のラウンド関数２１０内のＦ関数２１１の非線形変換部に構成されるＳ−ｂｏｘの差分確率によって計算されるある差分確率ｐ１で差分ΔＸ２，ΔＺ２が次段のラウンド関数へ出力される。
【００３９】
ここではｐｉをｉラウンド目の差分確率と呼ぶ。２段目のラウンド関数２２０に、ΔＸ２，ΔＺ２が入力されると差分確率ｐ２で差分ΔＸ３，ΔＺ３へと遷移が起こる。このように暗号化関数全体に対して差分の遷移を具体的に表したものが差分パスとよばれ、各ラウンドにおける差分確率ｐｉ，（１≦ｉ≦ｒ）をすべて掛け合わせた値を差分特性確率：ＤＣＰと呼び差分暗号化関数に対してΔＸ１，ΔＺ１が入力されたときにΔＣＬ，ΔＣＲが出力される確率を近似的に表す確率として利用する。
【００４０】
しかし、上述の差分パスの適用構成では、暗号化ブロックのビットサイズが増大すると複数のラウンド間の接続関係を考慮して最大の差分特性確率をもつ差分パスを容易に求めることはできなくなる。
【００４１】
［３．トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パス］
次に本発明の実施例として、上述の差分パス手法の改善手法であるトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを適用した手法について説明する。
【００４２】
トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分とは差分データの表現手法の一つで、差分データをある決められたビット数で区切り、各差分データの差分値がゼロか非ゼロかによって０または１を割り当てたデータである。本明細書においては、δ（スモールデルタ）の記号をつけて表現する。
【００４３】
図５に、図４の差分パスをバイトごとに区切り、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）形式で表した例を示す。ここで注意すべき点は図４の差分パスとは具体的な差分値が異なっていてもトランケイテッド（Ｔｒｕｎｃａｔｅｄ）表現したときに図５のように表現されるパスは複数存在しているということである。それらをまとめて代表的に表現したものがトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスであるといえる。
【００４４】
トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスには具体的な値が存在しないのでラウンド関数に対する差分確率のような固有の確率は定義されない。しかしながら、各ラウンド関数内のＦ関数内部でトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分として１が入力されるＳ−ｂｏｘの個数により差分確率の上界を求めることが可能となる。
【００４５】
複数段のラウンド関数によって構成される暗号化関数全体についても同様にすべてのＳ−ｂｏｘのなかでトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分１が入力されるＳ−ｂｏｘの個数をカウントすることで、このトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスに含まれる差分パスのもつ差分確率の上界を導出することができる。具体的にはトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスの中に含まれるトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分として１が入力されるＳ−ｂｏｘの数をａとし、Ｓ−ｂｏｘの最大差分確率をｐｓｍａｘとすると、差分特性確率の上界Ｕは、以下の（式２）によって示される。
【００４６】
【数１４】
Ｕ＝ｐｓｍａｘａ    ．．．（式２）
【００４７】
このようにトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスから、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分として１が入力されるＳ−ｂｏｘの数［ａ］を調べることで差分特性確率の上界がわかり安全性の評価を得ることができる。
【００４８】
トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分を用いるメリットとしては通常の差分と比べてデータ量が格段に縮約されており、現実的に処理可能な時間で探索を行うアルゴリズムが構築できるという点である。
【００４９】
なお、ＳＰＮ型のＦ関数をもつＦｅｉｓｔｅｌ暗号の場合、数多くのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスの中からもっとも高い上界をもつトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスをもとめる効率的なアルゴリズムについては、例えば、Ｔ．  Ｓｈｉｒａｉ，  Ｓ．  Ｋａｎａｍａｒｕ  ａｎｄ  Ｇ．  Ａｂｅ，  ”Ｉｍｐｒｏｖｅｄ  Ｕｐｐｅｒ  Ｂｏｕｎｄｓ  ｏｆ  Ｄｉｆｆｅｒｅｎｔｉａｌａｎｄ  Ｌｉｎｅａｒ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ  Ｐｒｏｂａｂｉｌｉｔｙ  ｆｏｒ  Ｃａｍｅｌｌｉａ”，  Ｆａｓｔ  Ｓｏｆｔｗａｒｅ  Ｅｎｃｒｙｐｔｉｏｎ，  ＦＳＥ  ２００２，  ＬＮＣＳ２３６５（論文１）に記述されている。
【００５０】
［４．線形パス］
次に、線形パスについて説明する。あるデータに対して特定の位置のビットを抜き出してきて、抜き出されたビットすべての排他的論理和をとり１ビットの値を得る処理をマスク処理と呼び、そのとき特定の位置を表す情報をマスク値と呼ぶ。マスク値は対象データと同じ長さのビット列で表現され、取り出すビット位置に１を、取り出さない位置に０を対応させる。たとえばビット列［０１０１１０１１］に対してマスク値［１０１０１０１０］を施すと１，３，５，７番目のビットを取り出して排他的論理和するので、下式（式３）の結果が得られる。
【００５１】
【数１５】
2004153733.tif 000010
【００５２】
なお、本明細書においては、マスク値を表現するときにはΓ（ガンマ）を用いて表すものとする。各ラウンド関数のＦ関数における非線形変換部に設定されるＳ−ｂｏｘには線形確率が定義される。Ｓ−ｂｏｘの入力値にマスクΓＡが、出力値にマスクΓＢが施されたとき、それぞれの結果の排他的論理和が０となる確率をｌ（ΓＡ，ΓＢ）とすると、確率：ｌ（ΓＡ，ΓＢ）は、以下の（式４）に従って計算される。
【００５３】
【数１６】
2004153733.tif 000011
【００５４】
また、特にＳ−ｂｏｘの線形確率ＬＰ，（ΓＡ，ΓＢ）を以下の（式５）に示すように定義する。
【００５５】
【数１７】
2004153733.tif 000012
【００５６】
図６を参照して、複数段のラウンド関数によって構成される暗号化関数に対してマスク処理を施した処理、すなわち線形近似処理例を説明する。１段目のラウンド関数４１０の入力値に対してΓＸ１，ΓＺ１で表されるマスク処理を施されて得られる値と、１段目のラウンド関数の出力に対してΓＸ２，ΓＺ２で表されるマスク処理を施されて得られる結果を排他的論理和した値が０となる確率をｑ１としそのマスク値に対するの線形確率と呼ぶ。ｑ１は、１段目のラウンド関数４１０のＦ関数４１１の非線形変換部に構成されるＳ−ｂｏｘの線形確率から計算することができる。
【００５７】
また、同様に２段目のラウンド関数４２０の入力値に対してΓＸ２，ΓＺ２で表されるマスク処理を施されて得られる値と、２段目のラウンド関数の出力に対してΓＸ３ΓＺ３で表されるマスク処理を施されて得られる結果を排他的論理和した値が０となる確率をｑ２とすると、マスク値に対するの線形確率ｑ２は、２段目のラウンド関数４２０のＦ関数４２１の非線形変換部に構成されるＳ−ｂｏｘの線形確率から計算することができる。以降のラウンド関数のマスク値に対しても、それぞれｑｉが計算される。
【００５８】
このとき複数段のラウンド関数によって構成される暗号化関数全体に着目して、一段目のラウンド関数の入力値に対してマスク値ΓＸ１，ΓＺ１が施されて得られる値とｒ段目のラウンド関数の出力に対してマスク値ΓＣＬ，ΓＣＲが施されて得られる値を排他的論理和した値が０となる確率ｑは、各ラウンドで定義されたｑｉを利用すると以下の（式６）に示すようになる。
【００５９】
【数１８】
2004153733.tif 000013
【００６０】
また、線形特性確率ＬＣＰを、以下の（式７）に示すように定義する。
【００６１】
【数１９】
2004153733.tif 000014
【００６２】
このように複数段のラウンド関数によって構成される暗号化関数全体に対してマスク値の対応を具体的に表したものが線形近似とよばれ、線形特性確率は安全性の評価指標として利用される。
【００６３】
しかし、前述の差分特性確率と同様、暗号化ブロックのビットサイズが増大すると複数のラウンド間の接続関係を考慮して最大の線形特性確率をもつ線形近似を容易に求めることはできなくなる。
【００６４】
［５．トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パス］
次に本発明の実施例として、上述の線形パス手法の改善手法であるトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスクを適用した手法について説明する。
【００６５】
トランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスクとはマスク値の表現手法の一つで、マスク値をある決められたビット数で区切り、各マスク値がゼロか非ゼロかによって０または１を割り当てたデータである。本明細書においては、γ（スモールガンマ）の記号をつけて示すものとする。
【００６６】
図７に、図６の線形近似をバイトごとに区切ったトランケイテッド（Ｔｒｕｎｃａｔｅｄ）形式で表した図を示す。なお、図６の線形近似とは具体的なマスク値が異なっていてもトランケイテッド（Ｔｒｕｎｃａｔｅｄ）表現したときに図７のように表現される線形近似は複数存在している。それらをまとめて代表的に表現したものがトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスである。
【００６７】
トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスには具体的な値が存在しないのでラウンド関数に対する線形確率のような固有の確率は定義されない。しかし暗号化関数全体のＳ−ｂｏｘのなかでトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスクとして１が入力されるＳ−ｂｏｘの個数をカウントすることで、このトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスに含まれる線形パスのもつ差分特性確率の上界をもとめることができる。
【００６８】
具体的には、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスの中に含まれるトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスクとして１が入力されるＳ−ｂｏｘの数をｂとし、Ｓ−ｂｏｘの最大線形確率をｑｓｍａｘとすると、線形特性確率の上界Ｕは、下式（式８）によって定義される。
【００６９】
【数２０】
Ｕ＝ｑｓｍａｘｂ    ．．．（式８）
【００７０】
上記式に基づいて上界を知ることで安全性の評価を得ることができる。
【００７１】
トランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスクを用いるメリットとしては通常のマスク値と比べてデータ量が格段に縮約されており、現実的な時間で探索を行うアルゴリズムが構築できるという点である。なお、差分パスの場合と同様にＳＰＮ型のＦ関数をもつＦｅｉｓｔｅｌ暗号の場合、数多くのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスの中からもっとも高い上界をもつトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスをもとめる効率的なアルゴリズムが、前述の（論文１）に記載されている。
【００７２】
［６．具体的な差分パス、線形近似の導出法］
次に、本発明の実施例であるトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスと、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスからその上界に近い特性確率を持つ具体的な差分パスや線形近似を求めるアルゴリズム、すなわち、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスあるいは、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスに基づいて、暗号強度指標値を算出する処理アルゴリズムについて説明する。
【００７３】
図８、図９のフローチャートを参照して、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスに基づいて、暗号強度指標値を算出する処理アルゴリズムについて説明する。
【００７４】
まず、ステップＳ１０１において、複数段のラウンド関数部を持つ暗号処理関数に対して、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスＴを入力する。ステップＳ１０２において、ＳＰＮ型のＦ関数を持つ共通鍵ブロック暗号を左右の２つの部分に分割する。左部分をレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）、右部分をライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）と呼ぶ。
【００７５】
ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に含まれるデータは、右側半分の平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、同様に、各ラウンド関数のＦ関数内の線形変換部出力であるＹｉの半分の出力Ｙ２ｉ−１と、次ラウンドへの入力値としてのＸｉの半分の入力値（Ｘ２ｉ）である。同様に、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に含まれるデータは、左側半分の平文（ＰＬ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ）、同様に、各ラウンド関数のＦ関数内の線形変換部出力であるＹｉの半分の出力Ｙ２ｉと、次ラウンドへの入力値としてのＸｉの半分の入力値（Ｘ２ｉ−１）である。
【００７６】
すなわち、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に含まれるデータは、
ＰＲ，Ｓ２ｉ−１，Ｙ２ｉ−１，Ｘ２ｉ（１≦ｉ≦ｒ／２）、
レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に含まれるデータは、
ＰＬ，Ｓ２ｉ，Ｙ２ｉ，Ｘ２ｉ−１（１≦ｉ≦ｒ／２）である。
【００７７】
ステップＳ１０３において、ＳＰＮ型のＦ関数の性質に基づいて、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ−１，ΔＸ２ｉ（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΔＹ２ｉ−１［ｊ］，ΔＸ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いて以下の等式（式９）に示すように示す。なお、以下の等式の総数はｍｒ個である。
【００７８】
【数２１】
2004153733.tif 000015
【００７９】
ステップＳ１０４において、上記式に含まれるすべてのｎビット差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，ΔＹ２ｉ−１［ｊ］，ΔＸ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分が０となっている変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する。
【００８０】
ステップＳ１０５において、連立一次方程式を以下の式（式１０）に示すように係数行列Ｍと変数ベクトルνで表現する。
【００８１】
【数２２】
Ｍν＝０．．．．．（式１０）
【００８２】
ステップＳ１０６において、行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める。
なお、変換行列（ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）は、以下の条件を満足する行列である。
（条件１）０のみからなる行（もしあるならば）は行列の最下部にある。
（条件２）各行を左から見てはじめの非ゼロの行の要素は１である（この１をリーディング１（ｌｅａｄｉｎｇ１））。
（条件３）それぞれのリーディング１（ｌｅａｄｉｎｇ１）はそれより上の行にあるリーディング１（ｌｅａｄｉｎｇ１）１よりも右に存在する。
（条件４）リーディング１（ｌｅａｄｉｎｇ１）の含まれる列はそのリーディング１（ｌｅａｄｉｎｇ１）１以外の要素はすべて０である。
なお、任意の行列は行の有限回の基本変形により変換行列（ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）に変換することが可能である。
【００８３】
さらに、ステップＳ１０６では、得られた変換行列のランクをｒａｎｋ，行列の列数をｃとし、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する。
【００８４】
次に、ステップＳ１０７において、自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める。
【００８５】
さらに、ステップＳ１０８において、ステップＳ１０３〜Ｓ１０７の処理を、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ，ΔＸ２ｉ−１（１≦ｉ≦ｒ／２）について同様の処理を実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合Ｓ≡を取得する。
【００８６】
ステップＳ１０９において、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対し、以下のように差分特性確率：ＤＣＰを計算し、最も高い値を持つ差分特性確率：ＤＣＰを、そのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスＴに対する最大差分特性確率ＭＤＣＰＴとする。
【００８７】
なお、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分が１であるＳ−ｂｏｘの個数をａ個とし、それぞれＳ−ｂｏｘの入出力をΔｘｉ，Δｙｉ（ｉ≦ｉ≦ａ）とする。差分特性確率ＤＣＰは、下式（式１１）によって定義される。
【００８８】
【数２３】
2004153733.tif 000016
【００８９】
ステップＳ１１０において、最大差分特性確率ＭＤＣＰＴの値を暗号強度指標値とする。最大差分特性確率ＭＤＣＰＴの値が大きいほど、暗号解読が容易であり、暗号強度は弱く、最大差分特性確率ＭＤＣＰＴの値が小さいほど暗号解読が困難であり、暗号強度が高いと判定することができる。
【００９０】
図８、図９を参照して説明した処理は、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスに基づく解析処理である。これに対して、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスからその上界に近い特性確率を持つ具体的な線形近似を求める場合は、入力されるトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスＴ’を用いて、そのパスにおける最大線形特性確率ＭＬＣＰＴを、上記のアルゴリズムと同様の処理に従って計算することができる。
【００９１】
なお、その際、線形変換層におけるマスク値変換を行う行列を用い、マスク値ΓＰＲ［ｊ］，ΓＳ２ｉ−１［ｊ］，ΓＴ２ｉ［ｊ］，ΓＺ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）の間に成り立つ一次式を構成し、Ｓ−ｂｏｘの差分確率ＤＰｓ（Δｘｉ，Δｙｉ）をＳ−ｂｏｘの線形確率ＬＰｓ（Γｘｉ，Γｙｉ）に置き換えて処理を実行する。
【００９２】
共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対してマスク処理データを入力して、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスからその上界に近い特性確率を持つ具体的な線形近似を求める場合の処理について説明する。
【００９３】
線形パス解析ステップは、下記の処理ステップによって構成される。
（Ｓ０１）マスク処理データがゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値を入力するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パス入力ステップ、
（Ｓ０２）暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割ステップ、
【００９４】
（Ｓ０３）ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）入力であるＴｉの半分の入力（Ｔ２ｉ）、次ラウンドへの入力値としてのＺｉの半分の入力値（Ｚ２ｉ−１）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ−１，ΓＳ２ｉ−１（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΓＺ２ｉ−１［ｊ］，ΓＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、マスク値：ΓＰＲ［ｊ］，ΓＴ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する等式設定ステップ、
【００９５】
（Ｓ０４）等式設定ステップにおいて設定された等式に含まれるすべてのｎビット差分：ΓＰＲ［ｊ］，ΓＳ２ｉ−１［ｊ］，ΓＴ２ｉ［ｊ］，ΓＺ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する連立一次方程式設定ステップ、
【００９６】
（Ｓ０５）連立一次方程式設定ステップにおいて設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換えステップ、
（Ｓ０６）行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求める変換行列算出ステップ、
【００９７】
（Ｓ０７）変換行列算出ステップにおいて得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する変数取得ステップ、
（Ｓ０８）自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める解集合算出ステップ、
（Ｓ０９）等式設定ステップ乃至解集合算出ステップをレフトチェイン（ＬｅｆｔＣｈａｉｎ）のマスク値ΓＺ２ｉ，ΓＳ２ｉ（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める第２の解集合算出ステップ、
【００９８】
（Ｓ１０）ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して線形特性確率：ＬＣＰを計算し、最も高い値を持つ線形特性確率：ＬＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスＴに対する最大線形特性確率ＭＬＣＰＴとして算出する最大線形特性確率算出ステップである。
【００９９】
なお、最大線形特性確率算出ステップにおいて、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分＝１が入力されるＳ−ｂｏｘの個数をａ個とし、それぞれＳ−ｂｏｘの入出力をΓｘｉ，Γｙｉ（ｉ≦ｉ≦ａ）としたとき、前記差分特性確率ＬＣＰを、下式（式１２）によって定義される。
【０１００】
【数２４】
2004153733.tif 000017
【０１０１】
ただし、ＬＰｓ（ΓＡ，ΓＢ）は、下式（式１３）によって定義される確率とする。
【０１０２】
【数２５】
2004153733.tif 000018
【０１０３】
処理結果として取得される最大線形特性確率ＭＬＣＰＴを、暗号強度指標値とする。最大差分特性確率ＭＬＣＰＴの値が大きいほど、暗号解読が容易であり、暗号強度は弱く、最大差分特性確率ＭＬＣＰＴの値が小さいほど暗号解読が困難であり、暗号強度が高いと判定することができる。
【０１０４】
［システム構成例］
上述の実施例で述べた暗号強度指標算出処理に伴う一連の処理は、ハードウェア、ソフトウェアの組合わせにより行うことができる。即ち、汎用のコンピュータや、マイクロコンピュータにプログラムを実行させることにより行う構成とすることが可能である。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、例えば汎用のコンピュータや１チップのマイクロコンピュータ等にインストールされる。図１０は、上述した一連の処理を実行するプログラムをインストール子実行可能なコンピュータの一実施形態としての構成例を示している。
【０１０５】
図１０に示すシステム構成例は１つの例であり、システムは、ここに示すべての機能を必ずしも備えることが要求されるものではない。図１０に示すＣＰＵ（Ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）５０１は、上述したアルゴリズムに従ったプログラムやその他の各種アプリケーションプログラム、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）を実行するプロセッサである。ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ−Ｍｅｍｏｒｙ）５０２は、ＣＰＵ５０１が実行するプログラム、あるいは演算パラメータとしての固定データを格納する。ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５０３は、ＣＰＵ５０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用される。
【０１０６】
ＨＤＤ５０４はハードディスクの制御を実行し、ハードディスクに対する各種データ、プログラムの格納処理および読み出し処理を実行する。暗号処理手段５０５は、データの暗号処理、復号処理等を実行する。なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをＲＯＭ５０２に格納し、ＣＰＵ５０１がＲＯＭ格納プログラムを読み出して実行するように構成してもよい。メモリ（セキュアモジュール）５０６は例えば耐タンパ構造を持つメモリとして構成され、暗号処理に必要な鍵データ等の格納領域として使用可能である。なお、これらのデータは、他のメモリ領域、記憶媒体に格納することも可能である。
【０１０７】
バス５２１はＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｎｅｔ／Ｉｎｔｅｒｆａｃｅ）バス等により構成され、各モジュール、入出力インタフェース１２２を介した各入手力装置とのデータ転送を可能にしている。
【０１０８】
入力部５１１は、例えばキーボード、ポインティングデバイス、あるいはその他のデータ入力手段によって構成され、ＣＰＵ５０１に各種のデータあるいはコマンドを入力する。出力部５１２は、例えばＣＲＴ、液晶ディスプレイ等であり、各種情報をテキストまたはイメージ等により表示する。
【０１０９】
通信部５１３はシステムの接続したエンティテイ、例えば暗号データの通信エンティテイとの通信処理を実行し、ＣＰＵ５０１の制御の下に、各記憶部から供給されたデータ、あるいはＣＰＵ５０１によって処理されたデータ、暗号化されたデータ等を送信したり、他エンティテイからのデータを受信する処理を実行する。
【０１１０】
ドライブ５１４は、フレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  ＲｅａｄＯｎｌｙ  Ｍｅｍｏｒｙ），ＭＯ（Ｍａｇｎｅｔｏ  ｏｐｔｉｃａｌ）ディスク，ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、磁気ディスク、半導体メモリなどのリムーバブル記録媒体５１５の記録再生を実行するドライブであり、各リムーバブル記録媒体５１５からのプログラムまたはデータ再生、リムーバブル記録媒体５１５に対するプログラムまたはデータ格納を実行する。
【０１１１】
各記憶媒体に記録されたプログラムまたはデータを読み出してＣＰＵ５０１において実行または処理を行なう場合は、読み出したプログラム、データはインタフェース５２２、バス５２１を介して例えば接続されているＲＡＭ５０３に供給される。
【０１１２】
先にフロー図を参照した処理を実行するためのプログラムは例えばＲＯＭ５０２に格納されてＣＰＵ５０１によって処理されるか、あるいはハードディスクに格納され、ハードディスクから読み出されてＣＰＵ５０１により実行される。
【０１１３】
図１０に示すシステムを暗号強度評価処理装置として適用する場合には、ＣＰＵ５０１が差分パス解析手段、あるいは線形パス解析手段として機能する。例えばＣＰＵ５０１が差分パス解析手段として、データ解析処理を実行する場合のシステムにおける処理について説明する。
【０１１４】
図１０に示すシステムにおいて、共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理部を暗号処理手段５０５に設定し、その暗号処理部の強度解析を行なう場合を想定する。
【０１１５】
ＣＰＵ５０１の制御の下、差分データの差分値がゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを暗号処理手段５０５に入力する。次に、差分パス解析手段としてのＣＰＵ５０１の制御の下に、暗号処理手段５０５におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割する分割し、ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の線形変換部出力であるＹｉの半分の出力Ｙ２ｉ−１、次ラウンドへの入力値としてのＸｉの半分の入力値（Ｘ２ｉ）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ−１，ΔＸ２ｉ（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定し、設定等式に含まれるすべてのｎビット差分：ΔＰＲ［ｊ］，ΔＳ２ｉ−１［ｊ］，ΔＹ２ｉ−１［ｊ］，Ｘ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定し、連立一次方程式設定処理において設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえる行列置き換えを実行し、行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求め、変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得し、自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める。
【０１１６】
また、上述の等式設定乃至解集合算出処理をレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）の差分ΔＹ２ｉ，ΔＸ２ｉ−１（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求め、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して差分特性確率：ＤＣＰを計算し、最も高い値を持つ差分特性確率：ＤＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスＴに対する最大差分特性確率ＭＤＣＰＴとして算出する処理を実行する。
【０１１７】
また、ＣＰＵ５０１が線形パス解析手段として、データ解析処理を実行する場合には、図１０に示すシステムにおいて、共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理部を暗号処理手段５０５に設定し、マスク処理データがゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値を入力する。
【０１１８】
次に、前記暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割し、ライトチェインに含まれるデータ、すなわち、右側半分の入力平文（ＰＲ）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）出力であるＳｉの半分の出力（Ｓ２ｉ−１）、各ラウンド関数のＦ関数内の非線形変換部（Ｓ−ｂｏｘ）入力であるＴｉの半分の入力（Ｔ２ｉ）、次ラウンドへの入力値としてのＺｉの半分の入力値（Ｚ２ｉ−１）について、入力平文を２ｍｎビットとし、ラウンド数ｒとしたとき、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ−１，ΓＳ２ｉ−１（１≦ｉ≦ｒ／２）の各ｎビットデータ：ΓＺ２ｉ−１［ｊ］，ΓＳ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を、マスク値：ΓＰＲ［ｊ］，ΓＴ２ｉ［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を用いた等式としてｍｎ個の等式を設定する。
【０１１９】
次に、等式設定処理において設定された等式に含まれるすべてのｎビット差分：ΓＰＲ［ｊ］，ΓＳ２ｉ−１［ｊ］，ΓＴ２ｉ［ｊ］，ΓＺ２ｉ−１［ｊ］，（１≦ｉ≦ｒ／２，１≦ｊ≦ｍ）を変数とみなし、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスにおいて、各変数に対応するトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値が０となる変数を等式から削除し、変数消去後、等式の右辺をすべて左辺に移項して得られるｍｒ個の式を斉次連立一次方程式として設定する。
【０１２０】
さらに、連立一次方程式設定ステップにおいて設定した連立一次方程式を係数行列Ｍと変数ベクトルνで、Ｍν＝０と置きかえ、行列Ｍに対して行変形を行い変換行列（エセロンマトリックス：ｒｅｄｕｃｅｄ  ｒｏｗ−ｅｃｈｅｌｏｎ  ｍａｔｒｉｘ）を求め、得られた変換行列のランク（ｒａｎｋ）、変換行列の列数（ｃ）としたとき、（ｃ−ｒａｎｋ）個の自由変数とｒａｎｋ個の従属変数を取得する。さらに、自由変数の取りうる値によって得られる連立方程式の解の集合をＳとし、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓを求める。
【０１２１】
さらに、等式設定処理乃至解集合算出処理をレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）のマスク値ΓＺ２ｉ，ΓＳ２ｉ（１≦ｉ≦ｒ／２）データに対して実行し、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’を求める。
【０１２２】
さらに、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に対する解の集合：Ｓとレフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）に対する解の集合：Ｓ’すべての解の候補の組み合わせに対して線形特性確率：ＬＣＰを計算し、最も高い値を持つ線形特性確率：ＬＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスＴに対する最大線形特性確率ＭＬＣＰＴとして算出する処理を実行する。
【０１２３】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。
【０１２４】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【０１２５】
例えば、プログラムは記憶媒体としてのハードディスクやＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ），ＭＯ（Ｍａｇｎｅｔｏ  ｏｐｔｉｃａｌ）ディスク，ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０１２６】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記憶媒体にインストールすることができる。
【０１２７】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１２８】
【発明の効果】
以上、説明したように、本発明の構成によれば、共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理関数の暗号強度解析において、上界により近い確率のパスを算出することが可能となる。
【０１２９】
また、本発明の構成によれば、共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対して差分データ入力に基づく差分パス解析において、差分データの差分値がゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスを入力し、暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割し、各チェインに含まれるデータに基づく差分解析を実行して差分特性確率：ＤＣＰを計算し、最も高い値を持つ差分特性確率：ＤＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスＴに対する最大差分特性確率ＭＤＣＰＴとして算出することが可能となる。
【０１３０】
さらに、本発明の構成によれば、共通鍵ブロック暗号処理アルゴリズムを実行し、ＳＰＮ型のＦ関数を含む複数段のラウンド関数部を持つＦｅｉｓｔｅｌ構造からなる暗号処理手段に対して、マスク処理データがゼロであるか非ゼロであるかに応じて０または１を割り当てたトランケイテッド（Ｔｒｕｎｃａｔｅｄ）マスク値を入力し、暗号処理部におけるデータを左右の２つの部分、レフトチェイン（Ｌｅｆｔ  Ｃｈａｉｎ）と、ライトチェイン（Ｒｉｇｈｔ  Ｃｈａｉｎ）に分割し、各チェインに含まれるデータに基づく解析を実行して線形特性確率：ＬＣＰを計算し、最も高い値を持つ線形特性確率：ＬＣＰを、暗号強度指標値としてのトランケイテッド（Ｔｒｕｎｃａｔｅｄ）線形パスＴに対する最大線形特性確率ＭＬＣＰＴとして算出することが可能となる。
【図面の簡単な説明】
【図１】Ｆｅｉｓｔｅｌ構造と呼ばれる代表的な共通鍵ブロック暗号の構造について説明する図である。
【図２】各ラウンド関数に設定されるＦ関数としてのＳＰＮ型の構成を説明する図である。
【図３】線形変換部の具体的線形変換処理例を示す図である。
【図４】ｒ段のラウンド関数からなる暗号化関数における差分の伝播を表現した差分パスの例を示す図である。
【図５】図４の差分パスをバイトごとに区切り、トランケイテッド（Ｔｒｕｎｃａｔｅｄ）形式で表した例を示す図である。
【図６】複数段のラウンド関数によって構成される暗号化関数に対する線形近似による処理例を説明する図である。
【図７】図６の線形近似をバイトごとに区切ったトランケイテッド（Ｔｒｕｎｃａｔｅｄ）形式で表した図をである。
【図８】トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスに基づいて、暗号強度指標値を算出する処理アルゴリズムを示すフロー図である。
【図９】トランケイテッド（Ｔｒｕｎｃａｔｅｄ）差分パスに基づいて、暗号強度指標値を算出する処理アルゴリズムを示すフロー図である。
【図１０】暗号強度指標算出に伴う一連の処理を実行するシステム構成例を示す図である。
【符号の説明】
１２１  鍵加算部
１２２  非線形変換部
１２３  線形変換部
２１０  ラウンド関数
２１１  Ｆ関数
２２０  ラウンド関数
２２１  Ｆ関数
４１０  ラウンド関数
４１１  Ｆ関数
４２０  ラウンド関数
４２１  Ｆ関数
５０１  ＣＰＵ
５０２  ＲＯＭ
５０３  ＲＡＭ
５０４  ＨＤＤ
５０５  暗号処理手段
５０６  メモリ
５１１  入力部
５１２  出力部
５１３  通信部
５１４  リムーバブル記憶媒体
５２１  バス
５２２  入出力インタフェース
【図１】
2004153733.tif 000025
【図２】
2004153733.tif 000026
【図３】
2004153733.tif 000027
【図４】
2004153733.tif 000028
【図５】
2004153733.tif 000029
【図６】
2004153733.tif 000030
【図７】
2004153733.tif 000031
【図８】
2004153733.tif 000032
【図９】
2004153733.tif 000033
【図１０】
2004153733.tif 000034