(57)【要約】【課題】共通鍵ブロック暗号における暗号強度評価処理を確実に実行する方法を提供する。【解決手段】共通鍵ブロック暗号アルゴリズムにおいて、鍵スケジュール部のアルゴリズムをベクトルと行列を用いて方程式で表現し、その行列方程式における非線形変換出力値及び初期値をユニタリ変換を利用して消去することにより、ラウンド鍵間の全ての線形関係式を求める。本方式によれば、鍵スケジュールの複雑性に拘わらず、共通鍵ブロック暗号方式におけるラウンド鍵間の線形関係式をすべて網羅することが可能となり、導出される線形関係式に基づいて、共通鍵ブロック暗号方式の暗号強度評価を実行することが可能となる。【選択図】　図１
2004072493.tif 000002
【特許請求の範囲】
【請求項１】
暗号処理アルゴリズムの暗号強度指標算出方法であり、
線形変換部と非線形変換部から成る鍵スケジュール部を有し、前記鍵スケジュール部の初期値がＵｉ，（ｉ＝１，２，．．．）、中間値がＺｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝０，１，２，．．．）、非線形変換部出力がＶｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）、前記中間値Ｚｉ，（ｉ＝１，２，．．．）、より生成されるラウンド鍵がＫｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）と表され、
マスター鍵から初期値Ｕｉ，（ｉ＝１，２，．．．）、を生成するステップと、初期値Ｕｉ，（ｉ＝１，２，．．．）、から中間値Ｚｉ（０），（ｉ＝１，２，．．．）を計算するステップと、中間値Ｚｉ（ｒ−１），（ｉ＝１，２，．．．）から中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．）を計算する複数のステップと、前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）、及び初期値Ｕｉ，（ｉ＝１，２，．．．）から非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を計算するステップと、前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）からラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を計算するステップとを有する共通鍵ブロック暗号処理アルゴリズムを暗号強度指標算出対象の暗号処理アルゴリズムとして設定するステップと、
前記ラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）が前記初期値Ｕｉ，（ｉ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）の線形結合で表記できるように前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）変数を消去するステップと、
前記線形結合式を、右辺が前記初期値Ｕｉ，（ｉ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）の項のみを有するように移項した連立線形方程式に変換するステップと、
前記連立線形方程式を行列方程式に変換するステップと、
前記行列方程式の両辺に、右辺の行列を階段行列に変形する行変形ユニタリ行列を左から乗じるステップと、
前記階段行列の行数から前記階段行列のｒａｎｋ値を減じた数をＮとしたとき、変換後の前記行列方程式の左辺の行列の下Ｎ行からなる新たな行列を生成するステップと、
前記ラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を要素とする列ベクトルを前記生成された新たな行列に乗ずることによってＮ個の線形関係式を求めるステップと、
を有することを特徴とする暗号強度指標算出方法。
【請求項２】
暗号処理アルゴリズムの暗号強度指標算出処理実行プログラムを記述したコンピュータ・プログラムであり、
線形変換部と非線形変換部から成る鍵スケジュール部を有し、前記鍵スケジュール部の初期値がＵｉ，（ｉ＝１，２，．．．）、中間値がＺｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝０，１，２，．．．）、非線形変換部出力がＶｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）、前記中間値Ｚｉ，（ｉ＝１，２，．．．）、より生成されるラウンド鍵がＫｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）と表され、
マスター鍵から初期値Ｕｉ，（ｉ＝１，２，．．．）、を生成するステップと、初期値Ｕｉ，（ｉ＝１，２，．．．）、から中間値Ｚｉ（０），（ｉ＝１，２，．．．）を計算するステップと、中間値Ｚｉ（ｒ−１），（ｉ＝１，２，．．．）から中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．）を計算する複数のステップと、前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）、及び初期値Ｕｉ，（ｉ＝１，２，．．．）から非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を計算するステップと、前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）からラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を計算するステップとを有する共通鍵ブロック暗号処理アルゴリズムを暗号強度指標算出対象の暗号処理アルゴリズムとして設定するステップと、
前記ラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）が前記初期値Ｕｉ，（ｉ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）の線形結合で表記できるように前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）変数を消去するステップと、
前記線形結合式を、右辺が前記初期値Ｕｉ，（ｉ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）の項のみを有するように移項した連立線形方程式に変換するステップと、
前記連立線形方程式を行列方程式に変換するステップと、
前記行列方程式の両辺に、右辺の行列を階段行列に変形する行変形ユニタリ行列を左から乗じるステップと、
前記階段行列の行数から前記階段行列のｒａｎｋ値を減じた数をＮとしたとき、変換後の前記行列方程式の左辺の行列の下Ｎ行からなる新たな行列を生成するステップと、
前記ラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を要素とする列ベクトルを前記生成された新たな行列に乗ずることによってＮ個の線形関係式を求めるステップと、
を有することを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号強度指標算出方法、およびコンピュータ・プログラムに関する。さらに、詳細には、共通鍵ブロック暗号の安全性・強度を評価するための指標を算出する暗号強度指標算出方法、およびコンピュータ・プログラムに関する。
【０００２】
【従来の技術】
暗号処理アルゴリズムには様々なものがあるが、大きく分類すると、暗号化鍵と復号化鍵を異なる鍵、例えば公開鍵と秘密鍵として設定する公開鍵暗号方式と、暗号化鍵と復号化鍵を共通の鍵として設定する共通鍵暗号方式とに分類される。
【０００３】
共通鍵暗号方式にも様々なアルゴリズムがあるが、その１つに共通鍵をベースとして複数の鍵を生成して、生成した複数の鍵を用いて暗号処理を実行する方式がある。複数の鍵の生成方式としてラウンド関数を用いる方式がある。これは、共通鍵に対してラウンド関数を作用させ、その出力値をもとに新たな鍵を生成し、さらに出力値にラウンド関数を作用させて得られる次の出力値をもとに次の鍵を生成するといった手順を繰り返して実行することによって複数の鍵を生成する方式である。このような鍵生成方式を適用したアルゴリズムの代表的なものが共通鍵ブロック暗号方式である。
【０００４】
共通鍵ブロック暗号のアルゴリズムは、主として、ラウンド関数部と鍵スケジュール部とに分けることができる。従来、共通鍵ブロック暗号を設計する際には、鍵関連攻撃等に対する安全性を確保するため、暗号の設計者は、ラウンド鍵間の単純な関係式が成立しないように、注意深く鍵スケジュール部の設計を行うことが要請されてきた。
【０００５】
このような指針に基づいて設計された暗号として、東芝が提案した共通鍵ブロック暗号「Ｈｉｅｒｏｃｒｙｐｔ」がある。Ｈｉｅｒｏｃｒｙｐｔについては、例えば「”Ｔｈｅ　Ｂｌｏｃｋ　Ｃｉｐｈｅｒ　Ｈｉｅｒｏｃｒｙｐｔ　”，Ｋ．Ｏｈｋｕｍａ，ｅｔ　ａｌ　Ｓｅｌｅｃｔｅｄ　ａｒｅａｓ　ｉｎ　ｃｒｙｐｔｏｇｒａｐｈｙ，　ＬＮＣＳ　２０１２，ｐｐ．７２−８８，２０００．」を参照されたい。Ｈｉｅｒｏｃｒｙｐｔの鍵スケジュール部は、Ｆｅｉｓｔｅｌ構造と呼ばれる繰り返し構造をもっているが、Ｆｅｉｓｔｅｌ構造の右半分の線形変換部に、ラウンド依存定数をＸＯＲ加算することによって鍵関連攻撃を回避することを試みている。
【０００６】
ところが、実際にはＨｉｅｒｏｃｒｙｐｔの作者が予期していなかったラウンド鍵間の線形関係式が成立することが、２００１年にＦｕｒｕｙａ等によって発見された。詳細については、例えば、「Ｓ．　Ｆｕｒｕｙａ　ａｎｄ　Ｖ．　Ｒｉｊｍｅｎ，　Ｏｂｓｅｒｖａｔｉｏｎｓ　ｏｎ　Ｈｉｅｒｏｃｒｙｐｔ−３／Ｌ１　Ｋｅｙ−ｓｃｈｅｄｕｌｉｎｇ　Ａｌｇｏｒｉｔｈｍｓ，　Ｓｅｃｏｎｄ　ＮＥＳＳＩＥ　ｗｏｒｋｓｈｏｐ，　２００１．」に述べられている。
【０００７】
【発明が解決しようとする課題】
しかし、上述のＦｕｒｕｙａ等によって行われた手法は、Ｈｉｅｒｏｃｒｙｐｔの鍵スケジュール部のアルゴリズムを試行錯誤で組み合わせることによってラウンド鍵間の線形関係式を導出するものであるため、発見された関係式が全てを網羅しているという保証はなかった。更に、試行錯誤的な方法では、鍵スケジュールが一層複雑になった場合、関係式を求めるのは困難を極める。
【０００８】
本発明は、鍵スケジュールの複雑性に拘わらず、共通鍵ブロック暗号方式におけるラウンド鍵間の線形関係式をすべて網羅することを可能としたものであり、導出される線形関係式に基づいて、共通鍵ブロック暗号方式の暗号強度評価を行なうことを可能とした暗号強度指標算出方法、およびコンピュータ・プログラムを提供することを目的とする。
【０００９】
【課題を解決するための手段】
本発明の第１の側面は、
暗号処理アルゴリズムの暗号強度指標算出方法であり、
線形変換部と非線形変換部から成る鍵スケジュール部を有し、前記鍵スケジュール部の初期値がＵｉ，（ｉ＝１，２，．．．）、中間値がＺｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝０，１，２，．．．）、非線形変換部出力がＶｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）、前記中間値Ｚｉ，（ｉ＝１，２，．．．）、より生成されるラウンド鍵がＫｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）と表され、
マスター鍵から初期値Ｕｉ，（ｉ＝１，２，．．．）、を生成するステップと、初期値Ｕｉ，（ｉ＝１，２，．．．）、から中間値Ｚｉ（０），（ｉ＝１，２，．．．）を計算するステップと、中間値Ｚｉ（ｒ−１），（ｉ＝１，２，．．．）から中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．）を計算する複数のステップと、前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）、及び初期値Ｕｉ，（ｉ＝１，２，．．．）から非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を計算するステップと、前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）からラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を計算するステップとを有する共通鍵ブロック暗号処理アルゴリズムを暗号強度指標算出対象の暗号処理アルゴリズムとして設定するステップと、
前記ラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）が前記初期値Ｕｉ，（ｉ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）の線形結合で表記できるように前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）変数を消去するステップと、
前記線形結合式を、右辺が前記初期値Ｕｉ，（ｉ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）の項のみを有するように移項した連立線形方程式に変換するステップと、
前記連立線形方程式を行列方程式に変換するステップと、
前記行列方程式の両辺に、右辺の行列を階段行列に変形する行変形ユニタリ行列を左から乗じるステップと、
前記階段行列の行数から前記階段行列のｒａｎｋ値を減じた数をＮとしたとき、変換後の前記行列方程式の左辺の行列の下Ｎ行からなる新たな行列を生成するステップと、
前記ラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を要素とする列ベクトルを前記生成された新たな行列に乗ずることによってＮ個の線形関係式を求めるステップと、
を有することを特徴とする暗号強度指標算出方法にある。
【００１０】
さらに、本発明の第２の側面は、
暗号処理アルゴリズムの暗号強度指標算出処理実行プログラムを記述したコンピュータ・プログラムであり、
線形変換部と非線形変換部から成る鍵スケジュール部を有し、前記鍵スケジュール部の初期値がＵｉ，（ｉ＝１，２，．．．）、中間値がＺｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝０，１，２，．．．）、非線形変換部出力がＶｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）、前記中間値Ｚｉ，（ｉ＝１，２，．．．）、より生成されるラウンド鍵がＫｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）と表され、
マスター鍵から初期値Ｕｉ，（ｉ＝１，２，．．．）、を生成するステップと、初期値Ｕｉ，（ｉ＝１，２，．．．）、から中間値Ｚｉ（０），（ｉ＝１，２，．．．）を計算するステップと、中間値Ｚｉ（ｒ−１），（ｉ＝１，２，．．．）から中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．）を計算する複数のステップと、前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）、及び初期値Ｕｉ，（ｉ＝１，２，．．．）から非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を計算するステップと、前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）からラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を計算するステップとを有する共通鍵ブロック暗号処理アルゴリズムを暗号強度指標算出対象の暗号処理アルゴリズムとして設定するステップと、
前記ラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）が前記初期値Ｕｉ，（ｉ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）の線形結合で表記できるように前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）変数を消去するステップと、
前記線形結合式を、右辺が前記初期値Ｕｉ，（ｉ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）の項のみを有するように移項した連立線形方程式に変換するステップと、
前記連立線形方程式を行列方程式に変換するステップと、
前記行列方程式の両辺に、右辺の行列を階段行列に変形する行変形ユニタリ行列を左から乗じるステップと、
前記階段行列の行数から前記階段行列のｒａｎｋ値を減じた数をＮとしたとき、変換後の前記行列方程式の左辺の行列の下Ｎ行からなる新たな行列を生成するステップと、
前記ラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を要素とする列ベクトルを前記生成された新たな行列に乗ずることによってＮ個の線形関係式を求めるステップと、
を有することを特徴とするコンピュータ・プログラムにある。
【００１１】
【作用】
本発明の構成によれば、鍵スケジュールの複雑性に拘わらず、共通鍵ブロック暗号方式におけるラウンド鍵間の線形関係式をすべて網羅することが可能となり、導出される線形関係式に基づいて、共通鍵ブロック暗号方式の暗号強度評価を実行することが可能となる。
【００１２】
本発明の構成によれば、暗号アルゴリズムのうち、鍵スケジュール部のアルゴリズムをベクトルと行列を用いて方程式で表現し、その行列方程式における非線形変換出力値及び初期値をユニタリ変換を利用して消去することにより、ラウンド鍵間の全ての線形関係式を求めることが可能となる。
【００１３】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能な汎用コンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記憶媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００１４】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【００１５】
【発明の実施の形態】
以下、本発明の暗号強度指標算出方法について詳細に説明する。まず、本発明の暗号強度指標算出処理の手順の概略について図１の処理フローを参照して説明する。その後、複数の具体的な共通鍵ブロック暗号アルゴリズムを例として、本発明の暗号強度指標算出処理を実行した例について説明する。
【００１６】
［暗号強度指標算出処理概要］
図１は、本発明の暗号強度指標算出処理の処理手順をフローチャートとして示した図である。各処理ステップの概略について説明する。
【００１７】
まず、ステップＳ１０１では、暗号強度指標算出処理対象となる暗号アルゴリズムを設定する。ここで暗号強度指標算出処理対象となる暗号アルゴリズムは、共通鍵ブロック暗号アルゴリズムである。
【００１８】
具体的には、線形変換部と非線形変換部から成る鍵スケジュール部を有し、前記鍵スケジュール部の初期値がＵｉ，（ｉ＝１，２，．．．）、中間値がＺｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝０，１，２，．．．）、非線形変換部出力がＶｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）、前記中間値Ｚｉ，（ｉ＝１，２，．．．）、より生成されるラウンド鍵がＫｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）と表され、マスター鍵から初期値Ｕｉ，（ｉ＝１，２，．．．）、を生成するステップと、初期値Ｕｉ，（ｉ＝１，２，．．．）、から中間値Ｚｉ（０），（ｉ＝１，２，．．．）を計算するステップと、中間値Ｚｉ（ｒ−１），（ｉ＝１，２，．．．）から中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．）を計算する複数のステップと、前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）、及び初期値Ｕｉ，（ｉ＝１，２，．．．）から非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を計算するステップと、前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）からラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を計算するステップとを有する共通鍵ブロック暗号処理アルゴリズムを暗号強度指標算出対象の暗号処理アルゴリズムとして設定する。
【００１９】
次に、ステップＳ１０２において、ステップＳ１０１において設定した共通鍵ブロック暗号処理アルゴリズムの中間変数を消去する。すなわち、ラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）が前記初期値Ｕｉ，（ｉ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）の線形結合で表記できるように前記中間値Ｚｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）変数を消去する処理を実行する。具体的な処理例については後述する。
【００２０】
次にステップＳ１０３において、変数移項処理を実行する。すなわち、前記線形結合式を、右辺が前記初期値Ｕｉ，（ｉ＝１，２，．．．）及び前記非線形変換部出力Ｖｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）の項のみを有するように移項した連立線形方程式に変換する処理を実行する。具体的な処理例については後述する。
【００２１】
次に、ステップＳ１０４において、行列方程式変換処理を実行する。すなわち、前記連立線形方程式を行列方程式に変換する処理を実行する。具体的な処理例については後述する。
【００２２】
次に、ステップＳ１０５において、ユニタリ変換処理を実行する。すなわち、前記行列方程式の両辺に、右辺の行列を階段行列に変形する行変形ユニタリ行列を左から乗じる処理を実行する。具体的な処理例については後述する。
【００２３】
次にステップＳ１０６において、小行列選択処理を実行する。すなわち、前記階段行列の行数から前記階段行列のｒａｎｋ値を減じた数をＮとしたとき、変換後の前記行列方程式の左辺の行列の下Ｎ行からなる新たな行列を生成する。具体的な処理例については後述する。
【００２４】
次にステップＳ１０７において、線形関係式生成処理を実行する。すなわち、前記ラウンド鍵Ｋｉ（ｒ），（ｉ＝１，２，．．．，ｒ＝１，２，．．．）を要素とする列ベクトルを前記生成された新たな行列に乗ずることによってＮ個の線形関係式を求める。具体的な処理例については後述する。
【００２５】
上述した処理によって求められた線形関係式の数：ＮをステップＳ１０１において設定した共通鍵ブロック暗号アルゴリズムの暗号強度指標とするものである。上述した処理フローは、ステップＳ１０１において設定した共通鍵ブロック暗号アルゴリズムのラウンド鍵間の線形関係式を網羅する線形関係式の数：Ｎを求める処理として実行され、線形関係式の数：Ｎが大であるほど暗号強度が弱く、小であるほど暗号強度が強いとの判定が可能である。従って、図１に示すフローに従って求められる線形関係式数：Ｎを共通鍵ブロック暗号アルゴリズムの暗号強度指標として適用することが可能となる。
【００２６】
図１に示す処理手順に従った処理によれば、暗号アルゴリズムのうち、鍵スケジュール部のアルゴリズムをベクトルと行列を用いて方程式で表現し、その行列方程式における非線形変換出力値及び初期値をユニタリ変換を利用して消去することでラウンド鍵間の全ての線形関係式を求めることが可能となる。
【００２７】
［暗号強度指標算出処理具体例１］
次に、本発明に係る暗号強度指標算出処理具体例として、東芝から提案されたブロック暗号「Ｈｉｅｒｏｃｒｙｐｔ−Ｌ１」に対して本発明に係る暗号強度評価方法を適用した処理例の詳細について説明する。Ｈｉｅｒｏｃｒｙｐｔ−Ｌ１は、ブロック長さ６４ｂｉｔ、鍵長１２８ｂｉｔの共通鍵ブロック暗号である。
【００２８】
まず、図１に示すステップＳ１０１の暗号処理アルゴリズムの設定ステップについて説明する。ここでは、東芝から提案されたブロック暗号「Ｈｉｅｒｏｃｒｙｐｔ−Ｌ１」の設定処理として実行する。
【００２９】
Ｏｎ，Ｉｎを各々ｎ行ｎ列の零行列、単位行列とする。これを用いて、行列Ｐ１６は以下のように定義される。
【００３０】
【数１】
2004072493.tif 000003
【００３１】
また、行列Ｐ１６Ｉを、行列Ｐ１６の逆行列とする。次に、行列Ｍ５、ＭＢを以下のように定義する。
【００３２】
【数２】
2004072493.tif 000004
【００３３】
さらに、行列Ｍ５、ＭＢを用いて、以下のように行列Ｍ５Ｂ、ＭＢ５を定義する。
【００３４】
【数３】
2004072493.tif 000005
【００３５】
次に、ラウンド依存定数ベクトルＧｉ（（ｉ＝０．．．７）を以下のように定義する。
【００３６】
【数４】
Ｇ０＝（ｈ０１，ｈ０２，ｈ０３，ｈ０４，０，０，０，０）
Ｇ１＝（ｈ１１，ｈ１２，ｈ１３，ｈ１４，０，０，０，０）
Ｇ２＝（ｈ２１，ｈ２２，ｈ２３，ｈ２４，０，０，０，０）
Ｇ３＝（ｈ３１，ｈ３２，ｈ３３，ｈ３４，０，０，０，０）
Ｇ４＝（ｈ４１，ｈ４２，ｈ４３，ｈ４４，０，０，０，０）
Ｇ５＝（ｈ４１，ｈ４２，ｈ４３，ｈ４４，０，０，０，０）
Ｇ６＝（ｈ３１，ｈ３２，ｈ３３，ｈ３４，０，０，０，０）
Ｇ７＝（ｈ２１，ｈ２２，ｈ２３，ｈ２４，０，０，０，０）
【００３７】
なお、上式で用いられている定数を要素とするベクトルＨＨを、以下のように定義しておく。
【００３８】
【数５】
ＨＨ＝（ｈ０１，ｈ０２，ｈ０３，ｈ０４，ｈ１１，ｈ１２，ｈ１３，ｈ１４，ｈ２１，ｈ２２，ｈ２３，ｈ２４，ｈ３１，ｈ３２，ｈ３３，ｈ３４，ｈ４１，ｈ４２，ｈ４３，ｈ４４）
【００３９】
具体的な、ｈ０１，ｈ０２，．．．，ｈ４４の値は、以下のように定義される。
【００４０】
【数６】
（ｈ０１，ｈ０１，ｈ０２，ｈ０３）＝（０ｘ５ａ，　０ｘ８２，　０ｘ７９，　０ｘ９９　）
（ｈ１１，ｈ１１，ｈ１２，ｈ１３）＝（０ｘ６ｅ，　０ｘｄ９，　０ｘｅｂ，　０ｘａ１　）
（ｈ２１，ｈ２１，ｈ２２，ｈ２３）＝（０ｘ８ｆ，　０ｘ１ｂ，　０ｘｂｃ，　０ｘｄｃ　）
（ｈ３１，ｈ３１，ｈ３２，ｈ３３）＝（０ｘｃａ，　０ｘ６２，　０ｘｃ１，　０ｘｄ６　）
（ｈ４１，ｈ４１，ｈ４２，ｈ４３）＝（　０ｘｆ７，　０ｘｄｅ，　０ｘｆ５，　０ｘ８ａ　）
【００４１】
次に、鍵スケジュール部の初期値の右半分から成るベクトルＺＺを、以下のように定義する。
【００４２】
【数７】
ＺＺ＝（ｚ３１，ｚ３２，ｚ３３，ｚ３４，ｚ４１，ｚ４２，ｚ４３，ｚ４４）
【００４３】
これらを用いて、共通鍵暗号アルゴリズムＨｉｅｒｏｃｒｙｐｔ−Ｌ１の鍵スケジュール部の右半分は、以下のように表せる。なお、演算子＋は、ガロア体ＧＦ（２）上の加法演算子である。
【００４４】
【数８】
Ｚ０＝Ｍ５Ｂ＊ＺＺ＋Ｇ０
Ｗ０＝Ｐ１６＊Ｚ０
Ｚ１＝Ｍ５Ｂ＊Ｗ０＋Ｇ１
Ｗ１＝Ｐ１６＊Ｚ１
Ｚ２＝Ｍ５Ｂ＊Ｗ１＋Ｇ２
Ｗ２＝Ｐ１６＊Ｚ２
Ｚ３＝Ｍ５Ｂ＊Ｗ２＋Ｇ３
Ｗ３＝Ｐ１６＊Ｚ３
Ｚ４＝Ｍ５Ｂ＊Ｗ３＋Ｇ４
Ｗ５＝ＭＢ５＊（Ｚ４＋Ｇ５）
Ｚ５＝Ｐ１６Ｉ＊Ｗ５
Ｗ６＝ＭＢ５＊（Ｚ５＋Ｇ６）
Ｚ６＝Ｐ１６Ｉ＊Ｗ６
Ｗ７＝ＭＢ５＊（Ｚ６＋Ｇ７）
Ｚ７＝Ｐ１６Ｉ＊Ｗ７
【００４５】
ここで、Ｚ０，Ｚ１，Ｚ２，Ｚ３，Ｚ４，Ｚ５，Ｚ６，Ｚ７，Ｗ０，Ｗ１，Ｗ２，Ｗ３，Ｗ５，Ｗ６，Ｗ７は、鍵スケジュール部の中間値の右半分を表す。
【００４６】
次に、これらの中間値を、下式、
【００４７】
【数９】
Ｚｎ＝Ｚｎ３｜｜ＺＮ４
Ｗｎ＝Ｗｎ１｜｜ＷＮ２
【００４８】
のように分割して表現する。但し記号“｜｜”は、ベクトルの連結を表す。
【００４９】
次に、各ラウンドの非線形変換部出力を、Ｖ０，Ｖ１，Ｖ２，Ｖ３，Ｖ４，Ｖ５，Ｖ６，Ｖ７とする。
但し、各々は、下記に示す４つの要素から成るベクトルである。
【００５０】
【数１０】
Ｖ０＝（ｖ０１，ｖ０２，ｖ０３，ｖ０４）
Ｖ１＝（ｖ１１，ｖ１２，ｖ１３，ｖ１４）
Ｖ２＝（ｖ２１，ｖ２２，ｖ２３，ｖ２４）
Ｖ３＝（ｖ３１，ｖ３２，ｖ３３，ｖ３４）
Ｖ４＝（ｖ４１，ｖ４２，ｖ４３，ｖ４４）
Ｖ５＝（ｖ５１，ｖ５２，ｖ５３，ｖ５４）
Ｖ６＝（ｖ６１，ｖ６２，ｖ６３，ｖ６４）
Ｖ７＝（ｖ７１，ｖ７２，ｖ７３，ｖ７４）
【００５１】
ここで、ベクトルＺ１、Ｚ２を下記のように設定する。
【００５２】
【数１１】
Ｚ１＝（ｚ１１，ｚ１２，ｚ１３，ｚ１４）
Ｚ２＝（ｚ２１，ｚ２２，ｚ２３，ｚ２４）
【００５３】
上記のように、ベクトルＺ１、Ｚ２を設定すると、Ｈｉｅｒｏｃｒｙｐｔ−Ｌ１の鍵スケジュール部の左半分は、以下のように表せる。
【００５４】
【数１２】
Ｚ０１＝Ｚ２
Ｚ０２＝Ｚ１＋Ｖ０
Ｚ１１＝Ｚ０２
Ｚ１２＝Ｚ０１＋Ｖ１
Ｚ２１＝Ｚ１２
Ｚ２２＝Ｚ１１＋Ｖ２
Ｚ３１＝Ｚ２２
Ｚ３２＝Ｚ２１＋Ｖ３
Ｚ４１＝Ｚ３２
Ｚ４２＝Ｚ３１＋Ｖ４
Ｚ５１＝Ｚ４２＋Ｖ５
Ｚ５２＝Ｚ４１
Ｚ６１＝Ｚ５２＋Ｖ６
Ｚ６２＝Ｚ５１
Ｚ７１＝Ｚ６２＋Ｖ７
Ｚ７２＝Ｚ６１
【００５５】
ここで、Ｚ０１，Ｚ０２，Ｚ１１，Ｚ１２，Ｚ２１，Ｚ２２，Ｚ３１，Ｚ３２，Ｚ４１，Ｚ４２，Ｚ５１，Ｚ５２，Ｚ６１，Ｚ６２，Ｚ７１，Ｚ７２は、鍵スケジュール部の中間値の左半分を表す。
【００５６】
こうして得られた中間値を用いて、ラウンド鍵：Ｋ１１，Ｋ１２，Ｋ１３，Ｋ１４，Ｋ２１，．．．，Ｋ７１，Ｋ７２は、以下のように表せる。
【００５７】
【数１３】
Ｋ１１＝Ｚ０１＋Ｖ１
Ｋ１２＝Ｚ１３＋Ｖ１
Ｋ１３＝Ｚ１４＋Ｖ１
Ｋ１４＝Ｚ０２＋Ｚ１４
Ｋ２１＝Ｚ１１＋Ｖ２
Ｋ２２＝Ｚ２３＋Ｖ２
Ｋ２３＝Ｚ２４＋Ｖ２
Ｋ２４＝Ｚ１２＋Ｚ２４
Ｋ３１＝Ｚ２１＋Ｖ３
Ｋ３２＝Ｚ３３＋Ｖ３
Ｋ３３＝Ｚ３４＋Ｖ３
Ｋ３４＝Ｚ２２＋Ｚ３４
Ｋ４１＝Ｚ３１＋Ｖ４
Ｋ４２＝Ｚ４３＋Ｖ４
Ｋ４３＝Ｚ４４＋Ｖ４
Ｋ４４＝Ｚ３２＋Ｚ４４
Ｋ５１＝Ｚ５１＋Ｚ４３
Ｋ５２＝Ｗ５１＋Ｖ５
Ｋ５３＝Ｗ５２＋Ｖ５
Ｋ５４＝Ｚ４１＋Ｗ５２
Ｋ６１＝Ｚ６１＋Ｚ５３
Ｋ６２＝Ｗ６１＋Ｖ６
Ｋ６３＝Ｗ６２＋Ｖ６
Ｋ６４＝Ｚ５１＋Ｗ６２
Ｋ７１＝Ｚ７１＋Ｚ６３
Ｋ７２＝Ｗ７１＋Ｖ７
Ｋ７３＝Ｗ７２＋Ｖ７
Ｋ７４＝Ｚ６１＋Ｗ７２
【００５８】
なお、Ｋ１１，Ｋ１２，Ｋ１３，Ｋ１４，Ｋ２１，．．．，Ｋ７１，Ｋ７２は、４つの要素から成るベクトルである。
【００５９】
次に、図１に示すステップＳ１０２の中間変数消去処理ステップについて説明する。上述の４つの要素から成るベクトルＫ１１，Ｋ１２，Ｋ１３，Ｋ１４，Ｋ２１，．．．，Ｋ７１，Ｋ７２について、実際に各値を代入して計算すると、以下のような式が得られる。
【００６０】
【数１４】
2004072493.tif 000006
2004072493.tif 000007
2004072493.tif 000008
2004072493.tif 000009
【００６１】
次に、ステップＳ１０３の変数移項処理を実行する。上記Ｋ１１，Ｋ１２，Ｋ１３，Ｋ１４，Ｋ２１，．．．，Ｋ７１，Ｋ７２の結果に基づいて、上記の連立線形方程式を変形し、右辺がｚｘｘ，ｖｘｘの項のみを含むように変形すると、以下のように表すことができる。
【００６２】
【数１５】
2004072493.tif 000010
2004072493.tif 000011
2004072493.tif 000012
2004072493.tif 000013
2004072493.tif 000014
【００６３】
次に、ステップＳ１０４の行列方程式変換処理を実行する。ここで、ベクトルＫ，Ｈ，Ｕ，Ｖを下記のように設定する。
【００６４】
【数１６】
Ｋ＝（ｋ１１１，Ｋ１１２，．．．，ｋ７２４）
Ｈ＝（ｈ０１，ｈ０２，．．．，ｈ４４）
Ｕ＝（ｚ１１，ｚ１２，．．．，ｚ４４）
Ｖ＝（ｖ０１，ｖ０２，．．．ｖ７４）
【００６５】
上記式のように、ベクトルＫ，Ｈ，Ｕ，Ｖを設定すると、上記連立線形方程式は以下のように行列方程式に変換できる。
【００６６】
【数１７】
2004072493.tif 000015
【００６７】
なお、上記式において、ＭＫＨ，ＭＵＶは、上記連立線形方程式の係数から成る　ＧＦ（２）上の行列である。
【００６８】
次に、ステップＳ１０５のユニタリ変換処理を実行する。
【００６９】
【数１８】
ｒａｎｋ（ＭＵＶ）＝Ｎｒ
【００７０】
とする。また、行列ＭＵＶの行数をＮｍとする。上記行列方程式の両辺に左から行変形ユニタリー行列Ｑを乗ずることによって、行列ＭＵＶを階段行列に変形することができる。このとき、ＱＭＵＶのうち、下Ｎｍ−Ｎｒ行から成る小行列は零行列になる。
【００７１】
次に、ステップＳ１０６の小行列選択処理を実行する。ＱＭＫＨの下Ｎｍ−Ｎｒ行の小行列をＭ＊ＫＨとおくと、Ｍ＊ＫＨはゼロ行列（Ｏ）であり、下記式によって示される。
【００７２】
【数１９】
Ｍ＊ＫＨ＝Ｏ
【００７３】
次にステップＳ１０７の線形関係式生成処理を実行する。この行列方程式を行毎の線形関係式に変換し、ｈ０１，ｈ０２，．．．，ｈ４４の具体的値を代入すると、以下のような関係式が得られる。
【００７４】
【数２０】
2004072493.tif 000016
2004072493.tif 000017
2004072493.tif 000018
2004072493.tif 000019
【００７５】
ここで、下記式が成立する。
【００７６】
【数２１】
ｒａｎｋ（Ｍ＊ＫＨ）＝Ｎｍ−Ｎｒ
【００７７】
従って、上記６０個の線形関係式は、互いに独立な線形関係式である。従って、これら６０個のＧＦ（２）上の任意を線形結合して得られる２６０−１個の線形関係式が成り立つことがわかる。この線形関係式が多ければ、暗号の設計者の意図しない新たな攻撃を招く恐れがあるので、上述した方法によって得られた線形関係式の総数を、暗号強度評価の一つの指標として用いることができる。
【００７８】
［暗号強度指標算出処理具体例２］
次に、本発明に係る暗号強度指標算出処理の第２の具体例として、東芝から提案されたブロック暗号「Ｈｉｅｒｏｃｒｙｐｔ−３」に対して本発明に係る暗号強度評価方法を適用した処理例の詳細について説明する。Ｈｉｅｒｏｃｒｙｐｔ−３は、ＡＥＳ互換の暗号であり、ブロック長は１２８ｂｉｔ、鍵長は、１２８，１９２，２５６　の何れかである。以下に説明する処理例は、鍵長が　２５６　ｂｉｔである場合についての処理例である。
【００７９】
まず、図１に示すステップＳ１０１の暗号処理アルゴリズムの設定ステップについて説明する。ここでは、東芝から提案されたブロック暗号「Ｈｉｅｒｏｃｒｙｐｔ−３」の設定処理として実行する。
【００８０】
まず、行列Ｐ３２は以下のように定義される。
【００８１】
【数２２】
2004072493.tif 000020
【００８２】
また、行列Ｐ３２Ｉを、行列Ｐ３２の逆行列とする。次に、行列Ｍ５１、Ｍ５２、ＭＢ１、ＭＢ２を以下のように定義する。
【００８３】
【数２３】
2004072493.tif 000021
2004072493.tif 000022
【００８４】
さらに、行列Ｍ５１、Ｍ５２、ＭＢ１、ＭＢ２を用いて、以下のように行列Ｍ５、ＭＢを定義する。
【００８５】
【数２４】
2004072493.tif 000023
【００８６】
次に、ラウンド依存定数ベクトルＧｉ（（ｉ＝０．．．９）を以下のように定義する。
【００８７】
【数２５】
2004072493.tif 000024
【００８８】
なお、上式で用いられている定数を要素とするベクトルＨＨは、先に［暗号強度指標算出処理具体例２］において説明したと同一である。
【００８９】
次に、鍵スケジュール部の初期値の右半分から成るベクトルＺＺを、以下のように定義する。
【００９０】
【数２６】
ＺＺ＝（ｚ３１，ｚ３２，ｚ３３，ｚ３４，ｚ３５，ｚ３６，ｚ３７，ｚ３８，ｚ４１，ｚ４２，ｚ４３，ｚ４４，ｚ４５，ｚ４６，ｚ４７，ｚ４８）
【００９１】
これらを用いて、共通鍵暗号アルゴリズムＨｉｅｒｏｃｒｙｐｔ−３の鍵スケジュール部の右半分は、以下のように表せる。なお、演算子＋は、ガロア体ＧＦ（２）上の加法演算子である。
【００９２】
【数２７】
Ｚ０Ｍ５＊ＺＺ＋Ｇ０
Ｗ０＝Ｐ３２＊Ｚ０
Ｚ１＝Ｍ５＊Ｗ０＋Ｇ１
Ｗ１＝Ｐ３２＊Ｚ１
Ｚ２＝Ｍ５＊Ｗ１＋Ｇ２
Ｗ２＝Ｐ３２＊Ｚ２
Ｚ３＝Ｍ５＊Ｗ２＋Ｇ３
Ｗ３＝Ｐ３２＊Ｚ３
Ｚ４＝Ｍ５＊Ｗ３＋Ｇ４
Ｗ４＝Ｐ３２＊Ｚ４
Ｚ５＝Ｍ５＊Ｗ４＋Ｇ５
Ｗ６＝ＭＢ＊（Ｚ５＋Ｇ６）
Ｚ６＝Ｐ３２Ｉ＊Ｗ６
Ｗ７＝ＭＢ＊（Ｚ６＋Ｇ７）
Ｚ７＝Ｐ３２Ｉ＊Ｗ７
Ｗ８＝ＭＢ＊（Ｚ７＋Ｇ８）
Ｚ８＝Ｐ３２Ｉ＊Ｗ８
Ｗ９＝ＭＢ＊（Ｚ８＋Ｇ９）
Ｚ９＝Ｐ３２Ｉ＊Ｗ９
【００９３】
ここで、Ｚ０，Ｚ１，Ｚ２，Ｚ３，Ｚ４，Ｚ５，Ｚ６，Ｚ７，Ｚ８，Ｚ９，Ｗ０，Ｗ１，Ｗ２，Ｗ３，Ｗ５，Ｗ６，Ｗ７，Ｗ８，Ｗ９は、鍵スケジュール部の中間値の右半分を表す。
【００９４】
次に、これらの中間値を、下式、
【００９５】
【数２８】
Ｚｎ＝Ｚｎ３｜｜ＺＮ４
Ｗｎ＝Ｗｎ１｜｜ＷＮ２
【００９６】
のように分割して表現する。但し記号“｜｜”は、ベクトルの連結を表す。
【００９７】
次に、各ラウンドの非線形変換部出力を、Ｖ０，Ｖ１，Ｖ２，Ｖ３，Ｖ４，Ｖ５，Ｖ６，Ｖ７，Ｖ８，Ｖ９とする。
但し、各々は、下記に示す８つの要素から成るベクトルである。
【００９８】
【数２９】
Ｖ０＝（ｖ０１，ｖ０２，ｖ０３，ｖ０４，ｖ０５，ｖ０６，ｖ０７，ｖ０８）
Ｖ１＝（ｖ１１，ｖ１２，ｖ１３，ｖ１４，ｖ１５，ｖ１６，ｖ１７，ｖ１８）
Ｖ２＝（ｖ２１，ｖ２２，ｖ２３，ｖ２４，ｖ２５，ｖ２６，ｖ２７，ｖ２８）
Ｖ３＝（ｖ３１，ｖ３２，ｖ３３，ｖ３４，ｖ３５，ｖ３６，ｖ３７，ｖ３８）
Ｖ４＝（ｖ４１，ｖ４２，ｖ４３，ｖ４４，ｖ４５，ｖ４６，ｖ４７，ｖ４８）
Ｖ５＝（ｖ５１，ｖ５２，ｖ５３，ｖ５４，ｖ５５，ｖ５６，ｖ５７，ｖ５８）
Ｖ６＝（ｖ６１，ｖ６２，ｖ６３，ｖ６４，ｖ６５，ｖ６６，ｖ６７，ｖ６８）
Ｖ７＝（ｖ７１，ｖ７２，ｖ７３，ｖ７４，ｖ７５，ｖ７６，ｖ７７，ｖ７８）
Ｖ８＝（ｖ８１，ｖ８２，ｖ８３，ｖ８４，ｖ８５，ｖ８６，ｖ８７，ｖ８８）
Ｖ９＝（ｖ９１，ｖ９２，ｖ９３，ｖ９４，ｖ９５，ｖ９６，ｖ９７，ｖ９８）
【００９９】
ここで、ベクトルＺ１、Ｚ２を下記のように設定する。
【０１００】
【数３０】
Ｚ１＝（ｚ１１，ｚ１２，ｚ１３，ｚ１４，ｚ１５，ｚ１６，ｚ１７，ｚ１８）
Ｚ２＝（ｚ２１，ｚ２２，ｚ２３，ｚ２４，ｚ２５，ｚ２６，ｚ２７，ｚ２８）
【０１０１】
上記のように、ベクトルＺ１、Ｚ２を設定すると、Ｈｉｅｒｏｃｒｙｐｔ−３の鍵スケジュール部の左半分は、以下のように表せる。
【０１０２】
【数３１】
Ｚ０１＝Ｚ２
Ｚ０２＝Ｚ１＋Ｖ０
Ｚ１１＝Ｚ０２
Ｚ１２＝Ｚ０１＋Ｖ１
Ｚ２１＝Ｚ１２
Ｚ２２＝Ｚ１１＋Ｖ２
Ｚ３１＝Ｚ２２
Ｚ３２＝Ｚ２１＋Ｖ３
Ｚ４１＝Ｚ３２
Ｚ４２＝Ｚ３１＋Ｖ４
Ｚ５１＝Ｚ４２
Ｚ５２＝Ｚ４１＋Ｖ５
Ｚ６１＝Ｚ５２＋Ｖ６
Ｚ６２＝Ｚ５１
Ｚ７１＝Ｚ６２＋Ｖ７
Ｚ７２＝Ｚ６１
Ｚ８１＝Ｚ７２＋Ｖ８
Ｚ８２＝Ｚ７１
Ｚ９１＝Ｚ８２＋Ｖ９
Ｚ９２＝Ｚ８１
【０１０３】
ここで、Ｚ０１，Ｚ０２，Ｚ１１，Ｚ１２，Ｚ２１，Ｚ２２，Ｚ３１，Ｚ３２，Ｚ４１，Ｚ４２，Ｚ５１，Ｚ５２，Ｚ６１，Ｚ６２，Ｚ７１，Ｚ７２，Ｚ８１，Ｚ８２，Ｚ９１，Ｚ９２は、鍵スケジュール部の中間値の左半分を表す。こうして得られた中間値を用いて、ラウンド鍵Ｋ１１，Ｋ１２，Ｋ１３，Ｋ１４，Ｋ２１，￥ｃｄｏｔｓ，Ｋ９１，Ｋ９２＄は、以下のように表せる。
【０１０４】
【数３２】
Ｋ１１＝Ｚ０１＋Ｖ１
Ｋ１２＝Ｚ１３＋Ｖ１
Ｋ１３＝Ｚ１４＋Ｖ１
Ｋ１４＝Ｚ０２＋Ｚ１４
Ｋ２１＝Ｚ１１＋Ｖ２
Ｋ２２＝Ｚ２３＋Ｖ２
Ｋ２３＝Ｚ２４＋Ｖ２
Ｋ２４＝Ｚ１２＋Ｚ２４
Ｋ３１＝Ｚ２１＋Ｖ３
Ｋ３２＝Ｚ３３＋Ｖ３
Ｋ３３＝Ｚ３４＋Ｖ３
Ｋ３４＝Ｚ２２＋Ｚ３４
Ｋ４１＝Ｚ３１＋Ｖ４
Ｋ４２＝Ｚ４３＋Ｖ４
Ｋ４３＝Ｚ４４＋Ｖ４
Ｋ４４＝Ｚ３２＋Ｚ４４
Ｋ５１＝Ｚ４１＋Ｖ５
Ｋ５２＝Ｚ５３＋Ｖ５
Ｋ５３＝Ｚ５４＋Ｖ５
Ｋ５４＝Ｚ４２＋Ｚ５４
Ｋ６１＝Ｚ６１＋Ｚ５３
Ｋ６２＝Ｗ６１＋Ｖ６
Ｋ６３＝Ｗ６２＋Ｖ６
Ｋ６４＝Ｚ５１＋Ｗ６２
Ｋ７１＝Ｚ７１＋Ｚ６３
Ｋ７２＝Ｗ７１＋Ｖ７
Ｋ７３＝Ｗ７２＋Ｖ７
Ｋ７４＝Ｚ６１＋Ｗ７２
Ｋ８１＝Ｚ８１＋Ｚ７３
Ｋ８２＝Ｗ８１＋Ｖ８
Ｋ８３＝Ｗ８２＋Ｖ８
Ｋ８４＝Ｚ７１＋Ｗ８２
Ｋ９１＝Ｚ９１＋Ｚ８３
Ｋ９２＝Ｗ９１＋Ｖ９
Ｋ９３＝Ｗ９２＋Ｖ９
Ｋ９４＝Ｚ８１＋Ｗ９２
【０１０５】
なお、Ｋ１１，Ｋ１２，Ｋ１３，Ｋ１４，Ｋ２１，．．．，Ｋ９１，Ｋ９２は、８つの要素成るベクトルである。
【０１０６】
次に、図１に示すステップＳ１０２の中間変数消去処理ステップについて説明する。上述の８つの要素から成るベクトルＫ１１，Ｋ１２，Ｋ１３，Ｋ１４，Ｋ２１，．．．，Ｋ９１，Ｋ９２について、実際に各値を代入して計算すると、以下のような式が得られる。
【０１０７】
【数３３】
2004072493.tif 000025
2004072493.tif 000026
2004072493.tif 000027
2004072493.tif 000028
2004072493.tif 000029
2004072493.tif 000030
2004072493.tif 000031
2004072493.tif 000032
2004072493.tif 000033
2004072493.tif 000034
2004072493.tif 000035
2004072493.tif 000036
2004072493.tif 000037
【０１０８】
次に、ステップＳ１０３の変数移項処理を実行する。上記Ｋ１１，Ｋ１２，Ｋ１３，Ｋ１４，Ｋ２１，．．．，Ｋ９１，Ｋ９２の結果に基づいて、上記の連立線形方程式を変形し、右辺がｚｘｘ，ｖｘｘの項のみを含むように変形すると、以下のように表せる。
【０１０９】
【数３４】
2004072493.tif 000038
2004072493.tif 000039
2004072493.tif 000040
2004072493.tif 000041
2004072493.tif 000042
2004072493.tif 000043
2004072493.tif 000044
2004072493.tif 000045
2004072493.tif 000046
2004072493.tif 000047
2004072493.tif 000048
2004072493.tif 000049
2004072493.tif 000050
【０１１０】
次に、ステップＳ１０４の行列方程式変換処理を実行する。ここで、ベクトルＫ，Ｈ，Ｕ，Ｖを下記のように設定する。
【０１１１】
【数３５】
Ｋ＝（ｋ１１１，Ｋ１１２，．．．，ｋ９２８）
Ｈ＝（ｈ０１，ｈ０２，．．．，ｈ４４）
Ｕ＝（ｚ１１，ｚ１２，．．．，ｚ４４）
Ｖ＝（ｖ０１，ｖ０２，．．．ｖ７４）
【０１１２】
上記式のように、ベクトルＫ，Ｈ，Ｕ，Ｖを設定すると、上記連立線形方程式は以下のように行列方程式に変換できる。
【０１１３】
【数３６】
2004072493.tif 000051
【０１１４】
なお、上記式において、ＭＫＨ，ＭＵＶは、上記連立線形方程式の係数から成る　ＧＦ（２）上の行列である。
【０１１５】
次に、ステップＳ１０５のユニタリ変換処理を実行する。
【０１１６】
【数３７】
ｒａｎｋ（ＭＵＶ）＝Ｎｒ
【０１１７】
とする。また、行列ＭＵＶの行数をＮｍとする。上記行列方程式の両辺に左から行変形ユニタリー行列Ｑを乗ずることによって、行列ＭＵＶを階段行列に変形することができる。このとき、ＱＭＵＶのうち、下Ｎｍ−Ｎｒ行から成る小行列は零行列になる。
【０１１８】
次に、ステップＳ１０６の小行列選択処理を実行する。ＱＭＫＨの下Ｎｍ−Ｎｒ行の小行列をＭ＊ＫＨとおくと、Ｍ＊ＫＨは零行列（Ｏ）であり、下記式によって示される。
【０１１９】
【数３８】
Ｍ＊ＫＨ＝Ｏ
【０１２０】
次にステップＳ１０７の線形関係式生成処理を実行する。この行列方程式を行毎の線形関係式に変換し、ｈ０１，ｈ０２，．．．，ｈ４４の具体的値を代入すると、以下のような関係式が得られる。
【０１２１】
【数３９】
2004072493.tif 000052
2004072493.tif 000053
2004072493.tif 000054
2004072493.tif 000055
2004072493.tif 000056
2004072493.tif 000057
2004072493.tif 000058
2004072493.tif 000059
2004072493.tif 000060
2004072493.tif 000061
2004072493.tif 000062
【０１２２】
ここで、下記式が成立する。
【０１２３】
【数４０】
ｒａｎｋ（Ｍ＊ＫＨ）＝Ｎｍ−Ｎｒ
【０１２４】
従って、上記１６８個の線形関係式は、互いに独立な線形関係式である。従って、これら１６８個のＧＦ（２）上の任意を線形結合して得られる２１６８−１個の線形関係式が成り立つことがわかる。この線形関係式が多ければ、暗号の設計者の意図しない新たな攻撃を招く恐れがあるので、上述した方法によって得られた線形関係式の総数を、暗号強度評価の一つの指標として用いることができる。
【０１２５】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。
【０１２６】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【０１２７】
例えば、プログラムは記憶媒体としてのハードディスクやＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ　Ｄｉｓｃ　Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ），ＭＯ（Ｍａｇｎｅｔｏ　ｏｐｔｉｃａｌ）ディスク，ＤＶＤ（Ｄｉｇｉｔａｌ　Ｖｅｒｓａｔｉｌｅ　Ｄｉｓｃ）、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０１２８】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ（Ｌｏｃａｌ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記憶媒体にインストールすることができる。
【０１２９】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１３０】
【発明の効果】
以上、説明したように、本発明の構成によれば、鍵スケジュールの複雑性に拘わらず、共通鍵ブロック暗号方式におけるラウンド鍵間の線形関係式をすべて網羅することが可能となり、導出される線形関係式に基づいて、共通鍵ブロック暗号方式の暗号強度評価を実行することが可能となる。
【０１３１】
本発明の構成によれば、暗号アルゴリズムのうち、鍵スケジュール部のアルゴリズムをベクトルと行列を用いて方程式で表現し、その行列方程式における非線形変換出力値及び初期値をユニタリ変換を利用して消去することにより、ラウンド鍵間の全ての線形関係式を求めることが可能となる。ラウンド鍵間に単純な依存関係が存在すると、実質的なラウンド鍵の数が減ってしまうことになるため、暗号の設計者は、このような関係式が多数存在することがないよう、注意する必要がある。本発明に係る方法によって、ラウンド鍵間の線形関係式の数が少なくなるよう、暗号鍵の強度を評価することによって、より安全な暗号を設計することが可能になる。
【図面の簡単な説明】
【図１】本発明を適用した暗号強度指標算出処理手順を説明するフローチャートを示す図である。
【図１】
2004072493.tif 000063