JP3689595B2 - Encryption device, decryption device, encryption communication method, and automatic fee collection system - Google Patents

Description

【００５７】
差分解読法に対する安全性を評価する場合、データランダム化部全体の平均差分確率を計算することは困難である。そこで、厳密な意味で安全性を保証するものではないが、差分解読法に対する安全性の必要条件として、最大差分特性確率が利用されている。例えばデータランダム化部の一部となっている非線型関数の平均差分確率を計算する。次に各非線型関数の平均差分確率がすべて独立であると仮定したうえで、これらの平均差分確率を用いてデータランダム化部全体の確率を計算する。このような条件付き確率が最大差分特性確率となる。実際の計算方法は、データランダム化部の構造に依存する。なお、差分解読に必要な平文・暗号文のペアの数は、平均差分確率の逆数として求めることができる。
【００５８】
一方、線形解読法とは、１９９３年に松井によって提案された解読法である((M.Matsui, Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology, EUROCRYPTO'93 proceedings, Lecture Notes in Computer Science Vol. 765, Springer-Verlag, 1993.), (M.Matsui, The First Experimental Cryptanalysis of the Data Encryption Standard, Advances in Cryptology, CRYPTO'94 proceedings, Lecture Note in Computer Science Vol. 839, Springer-Verlag, 1994.)。平文と暗号文のｂｉｔ値の間に線形関係を持つ確率が１／２から離れている場合、その線形関係を利用して候補となる鍵を推定し解読を行う方法である。実際に解読を行う場合には、任意の平文・暗号文のペアを多数入手する必要がある。
【００５９】
線形解読に対する安全性の尺度として、平均線形確率が提案されている(K.Nyberg, Linear Approximation of Block Ciphers, Advances in Cryptology, - CRYPTO'94, Lecture Notes in Computer Science Vol.950, Springer-Verlag, 1995.)。非線型関数の入出力データのｂｉｔ間で線形関係を持つ確率をすべての鍵について計算し、その中で最も発生確率が高くなる線形関係を見つける。このような線形関係が生じる確率が平均線形確率である。平均線形確率が小さいほど、線形解読法に対する安全性は高くなる。平均線形確率は以下のように定義される。
【００６０】
【数２】

【００６１】
線形解読法に対する安全性を評価する場合、差分解読法の場合と同様にデータランダム化部全体の平均線形確率を評価することは困難である。そこで差分解読法の場合と同様に最大線形特性確率という指標を用いる。たとえば、まずデータランダム化部の一部になっている非線型関数の平均線形確率を計算する。次に、各非線型関数が独立であると仮定した上で、これらの平均線形確率を基に、データランダム化部全体の確率を計算する。実際の計算方法はデータランダム化部の構造に依存する。なお、線形解読法による解読で実際に必要となる平文・暗号文のペアの数は、線形確率の逆数として求まる。
【００６２】
本発明者等は、上記（１）の条件を満たすように、各換字転置変換部２１_nのアルゴリズム鍵Ｇ_nのシフト値を設定することで、換字転置変換部の段数すなわちラウンド数Ｎを増やさなくても、差分解読法および線形解読法による攻撃に対する強度を向上させることが可能になることを見出した。その根拠については後述する。
【００６３】
また、上記（２）に示す条件は、スライド攻撃に対抗するためのものである。スライド攻撃とは、段数（ラウンド数）に依存しない選択平文型攻撃方法のことである。スライド攻撃による暗号解読については、ＢｉｒｙｕｋｏｖとＷａｇｎｅｒによりＦＳＥ９９（Fast Software Encription work shop 1999）にて発表された論文「Slide Attacks」に詳しく記載されている。
【００６４】
さらに、本実施形態では、以下の条件を満たすようにアルゴリズム鍵Ｇ_nを設定している。
【００６５】
いま、鍵変換部２３で生成される変換鍵Ｋ１、Ｋ２を固定とし、全ての換字転置変換部２１₁〜２１_Nから連続する２以上の換字転置変換部２１_i〜２１_i+j（１≦ｉ、ｉ＋ｊ≦Ｎ）を任意に選んで、同一のデータを入力値として変換する場合を考える。この場合、変換結果は、選択した換字転置変換部２１_i〜２１_i+jで用いるアルゴリズム鍵Ｇ_i〜Ｇ_i+jにより決定される。本実施形態では、上述した全ての組み合わせにおいて、異なった変換結果が得られるようなアルゴリズム鍵のみを用いるものとする。このようにすることで、換字転置変換部を繰り返し用いた暗号変換に周期性が現れないようにすることができ、これにより、暗号の強度を向上させることができる。
【００６６】
なお、暗号化部１１がＡＳＩＣやＦＰＧＡなどの集積ロジックＩＣによりハード的に実現される場合、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3nの組み合わせとして、全てのアルゴリズム鍵Ｇ₁〜Ｇ_Nに共通の３つの値の組み合わせを用い、加算値Ａ_1n、Ａ_2n、Ａ_3nの組み合わせとして、全てのアルゴリズム鍵Ｇ₁〜Ｇ_Nに共通の３つの値の組み合わせを用いるようにしてもよい。このようにすることで、ハード構成が複雑になるのを防ぐことができる。
【００６７】
次に、データ受信機２の復号化部３１について説明する。
【００６８】
図６は、図１に示す復号化部３１の概略構成図である。この復号化部３１は、上述した図２の暗号化部１１を用いて暗号変換された暗号文を、元の平文に復号するものである。なお、図６に示す復号化部３１の各構成要素は、図２に示す暗号化部１１と同様、ＡＳＩＣやＦＰＧＡなどの集積ロジックＩＣによりハード的に実現されるものでもよいし、あるいは、ＤＳＰなどの計算機によりソフトウエア的に実現されるものでもよい。
【００６９】
鍵変換部４３は、図２に示す暗号化部１１の鍵変換部２３と同様の処理を行う。すなわち、鍵共有部３２より、４０ビットあるいは６４ビットの暗復号用の鍵と１ビットの鍵長データとを受け取り、これらを基に、３２ビットの変換鍵Ｋ１、Ｋ２を生成する。ここで、鍵長データの値は、鍵が４０ビットならば０とし、６４ビットならば１とする。
【００７０】
復号変換部４０は、入力された２つの３２ビットデータＬ_i、Ｒ_i（０≦ｉ≦Ｎ）に、変換鍵Ｋ１、Ｋ２を作用させて、換字転置変換処理を行い、その結果を、次の段に入力すべき２つの３２ビットデータＬ_i-1、Ｒ_i-1として出力するＮ段の換字転置変換部４１₁〜４１_Nと、通信処理部３４を介してデータ送信機１より受け取った６４ビットの暗号文を、上位３２ビットデータＬ_Nと下位３２ビットデータＲ_Nに分割して、最初の段の換字転置変換部４１_Nに入力する分割部４５ａと、最後の段の換字転置変換部４１₁から出力された２つの３２ビットデータＬ₀、Ｒ₀を、データＬ₀を上位ビットデータ、データＲ₀を下位ビットデータとして結合し、６４ビットの平文を得る結合部４５ｂとを有する。ここで、換字転置変換部４１_n（１≦ｎ≦Ｎ）の変換アルゴリズムは、アルゴリズム鍵保持部４４に保持されているアルゴリズム鍵Ｇ_nにより決定される。アルゴリズム鍵保持部４４は、図２に示す暗号化部１１のアルゴリズム鍵保持部２４が保持するアルゴリズム鍵Ｇ₁〜Ｇ_Nと同じアルゴリズム鍵を保持している。
【００７１】
さて、上記構成の復号変換部４０に、通信処理部３４を介してデータ送信機１より受け取った６４ビットの暗号文が入力されると、分割部４５ａにより上位３２ビットデータＬ_N（図２に示す最終段の換字転置変換部２１_Nより出力される３２ビットデータＬ_Nと一致）と下位３２ビットデータＲ_N（図２に示す最終段の換字転置変換部２１_Nより出力される３２ビットデータＲ_Nと一致）に分割されて、換字転置変換部４１_Nに入力される。そこで、変換鍵Ｋ１、Ｋ２を用いて、第１回目の暗号変換が行われる。続いて、換字転置変換部４１_Nでの暗号変換の結果得られた３２ビットデータＬ_N-1と３２ビットデータＲ_N-1が次の段の換字転置変換部４１_N-1に入力されると、そこで、変換鍵Ｋ１、Ｋ２を用いて、第２回目の暗号変換が行われる。換字転置変換部４１_N-1での暗号変換の結果得られた３２ビットデータＬ_N-2と３２ビットデータＲ_N-2は、次の段の換字転置変換部４１₃に入力され、そこで同様の処理がなされる。以上のような暗号変換をＮ回繰り返し、最終の段の換字転置変換部４１₁での暗号変換の結果得られた３２ビットデータＬ₀と３２ビットデータＲ₀が結合部４５ｂで結合されることにより、元の平文が得られる。以降、復号変換の総繰り返し数Ｎを、暗号変換の場合と同様、ラウンド数と呼ぶものとする。
【００７２】
図７は、図６に示す換字転置変換部４１_n（１≦ｎ≦Ｎ）の概略構成図である。ここで、図４に示す暗号化部１１の換字転置変換部２１_nと同じ機能を有するものには同じ符号を付している。
【００７３】
図示するように、換字転置変換部４１_nは、ビット列変換部６１と、排他的論理和演算部６２とからなり、入力された３２ビットデータＬ_nと３２ビットデータＲ_nを、変換鍵Ｋ１とＫ２を用いて、３２ビットデータＬ_n-1と３２ビットデータＲ_n-1に変換する。
【００７４】
換字転置変換部４１_nは、まず、入力された３２ビットデータＬ_n-1をビット列変換部６１に入力する。ビット列変換部６１は、アルゴリズム鍵Ｇ_nにより決定される変換アルゴリズムにしたがい、変換鍵Ｋ１とＫ２を用いて、入力された３２ビットデータＲ_nにビット列変換処理を加える。
【００７５】
排他的論理和演算部６２は、ビット列変換部６１よりの出力と、換字転置変換部４１_nに入力された３２ビットデータＬ_nとの排他的論理和を計算する。そして、その結果を、次の段の換字転置変換部４１_n-1に入力すべき３２ビットデータＲ_n-1として出力する。一方、換字転置変換部４１_nに入力された３２ビットデータＲ_nを、次の段の換字転置変換部４１_n-1に入力すべき３２ビットデータＬ_n-1として出力する。
【００７６】
換字転置変換部４１_nでの変換をまとめると、以下のように表せる。
【００７７】
R_n-1=L_n(+)FG_n(K1,K2,R_n)
L_n-1=R_n
この変換は、先に図４、５を用いて説明した、暗号変換部２０の換字転置変換部４１_nにおける変換の逆変換に相当する。
【００７８】
図６に示すように、アルゴリズム鍵Ｇ_n（１≦ｎ≦Ｎ）は、最初の段の換字転置変換部４１_Nに設定されるアルゴリズム鍵Ｇ_Nが図２に示す暗号変換部２０の最後の段の換字転置変換部２１_Nに設定されるアルゴリズム鍵Ｇ_Nと一致し、最後の段の換字転置変換部４１₁に設定されるアルゴリズム鍵Ｇ₁が図２に示す暗号変換部２０の最初の段の換字転置変換部２１₁に設定されるアルゴリズム鍵Ｇ₁と一致するように、復号変換部４０の換字転置変換部４１₁〜４１_Nと暗号変換部２０の換字転置変換部２１₁〜２１_Nとの間で、段の順番上逆順に設定されている。
【００７９】
したがって、復号化部３１が暗号化部１１との間で同じ暗復号用の鍵を共有すれば、暗号化部１１が暗号化したデータを復号化することができる。
【００８０】
以上、本発明の一実施形態について説明した。
【００８１】
本実施形態では、上述したように、データ送信機１が送信する暗号文は、当該データ送信機１が用いる暗復号用の鍵およびアルゴリズム鍵と同じ暗復号用の鍵およびアルゴリズム鍵を保持するデータ受信機２しか復号化することができない。そして、暗復号用の鍵に加えて、アルゴリズム鍵も秘密情報としているので、第三者による通信路上を流れる暗号文の解読攻撃をより困難にすることができる。
【００８２】
また、本実施形態では、上述したように、アルゴリズム鍵Ｇ_n（１≦ｎ≦Ｎ）のシフト値Ｓ_1n、Ｓ_2n、Ｓ_3nとして、全てが奇数、あるいはＳ_1nおよびＳ_2nのいずれか一方が２で残り２つが奇数の値となるように設定している。このようにすることで、換字転置変換部の段数すなわちラウンド数Ｎを増やさなくても、差分解読法および線形解読法による攻撃に対する強度を向上させることができる。
【００８３】
本発明者等は、差分解読法および線形解読法による暗号解読に対する強度評価実験を以下の要領で行った。
【００８４】
１．差分解読法による暗号解読に対する強度評価
（１）準備
図５に示すビット列変換部６１において、変換鍵Ｋ１＝Ｋ２＝０、加算値Ａ_1n＝１、Ａ_2n＝Ａ_3n＝０とした場合に得られる変換を、入力差分がΔＸ、出力差分がΔＹで与えられるＦ関数とし、当該Ｆ関数の差分確率ｄｐ（ΔＸ→ΔＹ）を以下のように定義する。
【００８５】
dp(ΔX→ΔY)=prob{F(U(+)ΔX)(+)F(U)=ΔY}
ここで、ｐｒｏｂ｛Ａ＝Ｂ｝はＡ＝Ｂとなる確率（Ａ＝Ｂとなる出現回数／サンプル数）を意味する。
【００８６】
差分確率を求めるための評価パターンとして、図８（ａ）に示す評価パターンを用意した。ここで、図８（ａ）は差分２段繰り返し型の評価パターンであり、１段目の関数Ｆ₁は入力差分ΔＸ＝０で出力差分ΔＹ＝０、２段目の関数Ｆ₂は入力差分ΔＸ＝Δａで出力差分ΔＹ＝０である。この評価パターンを用いたのは、差分２段繰り返し型の評価パターンにおける２段目の関数Ｆ₂の差分確率
dp(Δa→0)=prob{F₂(U(+)Δa)(+)F(U)=0}
が最も大きくなるからである。
【００８７】
（２）関数Ｆの入力Ｕのビット幅が１６ビット以下の場合の評価
関数Ｆの入力Ｕのビット幅（すなわち、関数Ｆで処理されるデータのビット幅）を２^e（ｅ＝２、３、４）とし、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3nの全ての組み合わせ（但し、入力Ｕのビット幅が２^eであるので、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3nは１〜２^eの範囲の値をとる）に対して、差分２段繰り返し型評価パターンの２段目の関数Ｆ₂の差分確率
dp(Δa→0)=prob{F₂(U(+)Δa)(+)F(U)=0}
を評価した。関数Ｆの入力Ｕのビット幅を２⁴＝１６としたときの評価結果を図９、１０に示す。図９では、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3n各々と入力Ｕのビット幅１６との最大公約数をそれぞれａ、ｂ、ｃとすると、ａ、ｂ、ｃの最大値ｍａｘ（ａ，ｂ，ｃ）は８、４、２、１のいずれかの値をとることに着目し、ｍａｘ（ａ，ｂ，ｃ）の値の大きい順に示した。また、ｍａｘ（ａ，ｂ，ｃ）各々において、出力差分０を導く入力差分のうち、最大差分確率を与えるシフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）を、当該最大差分確率の大きい順に示した。図１０は、図９に示すｍａｘ（ａ，ｂ，ｃ）＝２の場合の結果のうち、シフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）が（２、奇数、奇数）あるいは（奇数、２、奇数）の場合の結果を抜き出したものである。
【００８８】
図９に示すように、ｍａｘ（ａ，ｂ，ｃ）が小さい程、近似の確率が低下する。したがって、ｍａｘ（ａ，ｂ，ｃ）が１のとき、つまり、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3n各々の、入力Ｕのビット幅との最大公約数が１のとき、いいかえれば、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3nがすべて奇数のとき、最良差分確率が２^-4.75〜２^-6.68程度と最も低くなり、差分解読法による攻撃に対する耐性を最も高くすることができることがわかった。また、ｍａｘ（ａ，ｂ，ｃ）が２の場合でも、図１０に示すように、シフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）が（２、奇数、奇数）あるいは（奇数、２、奇数）の場合は、最良差分確率が２^-3.71〜２^-4.79程度と、ｍａｘ（ａ，ｂ，ｃ）が２の場合におけるその他の場合に比べて低くなり、差分解読法による攻撃に対する耐性を高くすることができることがわかった。なお、ここでは、入力Ｕのビット幅が１６の場合についてのみ結果を表示しているが、入力Ｕのビット幅が４、８の場合についても、シフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）として、任意の値（但し、１≦Ｓ_1n、Ｓ_2n、Ｓ_3n＜入力Ｕのビット幅）をピックアップし、評価した結果も、同様の傾向を示した。したがって、本発明者等は、上記の実施形態で用いる換字転置変換部２１_n、４１_nのビット列変換部６１に設定するアルゴリズム鍵Ｇ_nのシフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）として、（奇数、奇数、奇数）、（２、奇数、奇数）あるいは（奇数、２、奇数）となるように設定することで、差分解読法による攻撃に対する強度を向上させることができることを見出した。
【００８９】
（３）関数Ｆの入力Ｕのビット幅が３２ビットの場合の評価
上記（２）での結果を踏まえ、上記の実施形態で用いる換字転置変換部２１_n、４１_nのビット列変換部６１に設定するアルゴリズム鍵Ｇ_nのシフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）として、（２、奇数、奇数）あるいは（奇数、２、奇数）となるように設定し、入力Ｕのビット幅を２⁵＝３２とした場合における差分２段繰り返し型評価パターンの２段目の関数Ｆ₂の差分確率
dp(Δa→0)=prob{F₂(U(+)Δa)(+)F(U)=0}
を評価した。結果を図１１に示す。この結果からわかるように、入力Ｕのビット幅３２の場合、シフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）が（２、奇数、奇数）あるいは（奇数、２、奇数）であれば、最良差分確率は２^-7.69〜２^-8.70程度であった。
【００９０】
２．線形解読法による暗号解読に対する強度評価
（１）準備
図５に示すビット列変換部６１において、変換鍵Ｋ１＝Ｋ２＝０、加算値Ａ_1n＝１、Ａ_2n＝Ａ_3n＝０とした場合に得られる変換を、入力マスクがΓＸ、出力マスクがΓＹで与えられるＦ関数とし、当該Ｆ関数の線形近似確率ｌｐ（ΓＸ→ΓＹ）を以下のように定義する。
【００９１】
lp(ΓX→ΓY)=|2prob{F(U)・ΓY=X・ΓX}−1|²
ここで、Ａ・Ｂは、Ａについて、Ｂのビット列において値「１」のビットのビット位置と同じビット位置のビットの値が「１」であるビットの数を調べ、そのビット数のｍｏｄ２をとる意味である。
【００９２】
線形近似確率を求めるための評価パターンとして、図８（ｂ）に示す評価パターンを用意した。ここで図８（ｂ）は線形２段繰り返し型の評価パターンであり、１段目の関数Ｆ₁は入力マスクΓＸ＝０で出力マスクΓＹ＝０、２段目の関数Ｆ₂は入力マスクΓＸ＝０で出力マスクΓＹ＝Γａである。この評価パターンを用いたのは、線形２段繰り返し型の評価パターンにおける２段目の関数Ｆ₂の線形近似確率
lp(0→Γa)=|2prob{F₂(U)・Γa=U・0}−1|²
が最も大きくなるからである。
【００９３】
（２）関数Ｆの入力Ｕのビット幅が１６ビット以下の場合の評価
関数Ｆの入力Ｕのビット幅（すなわち、関数Ｆで処理されるデータのビット幅）を２^e（ｅ＝２、３、４）とし、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3nの全ての組み合わせ（但し、入力Ｕのビット幅が２^eであるので、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3nは１〜２^e-1の範囲の値をとる）に対して、線形２段繰り返し型の評価パターンの２段目の関数Ｆ₂の線形近似確率
lp(0→Γa)=|2prob{F₂(U)・Γa=U・0}−1|²
を評価した。図１２、１３に、関数Ｆの入力Ｕのビット幅を２⁴＝１６としたときの評価結果を示す。図１２では、図９と同様、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3n各々について、入力Ｕのビット幅１６との最大公約数をそれぞれａ、ｂ、ｃとすると、ａ、ｂ、ｃの最大値ｍａｘ（ａ，ｂ，ｃ）が８、４、２、１のいずれかの値をとることに着目し、ｍａｘ（ａ，ｂ，ｃ）の値の大きい順に示した。また、ｍａｘ（ａ，ｂ，ｃ）各々において、入力マスク０となる出力マスクのうち最大線形近似確率を与えるシフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）を、当該最大線形近似確率の大きい順に示した。図１２は、図１１に示すｍａｘ（ａ，ｂ，ｃ）＝２の場合の結果のうち、シフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）が（２、奇数、奇数）あるいは（奇数、２、奇数）の場合の結果を抜き出したものである。
【００９４】
図１２に示すように、ｍａｘ（ａ，ｂ，ｃ）が小さい程、近似の確率が低下する。したがって、ｍａｘ（ａ，ｂ，ｃ）が１のとき、つまり、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3n各々の、入力Ｕのビット幅との最大公約数が１のとき、いいかえれば、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3nがすべて奇数のとき、最良線形近似確率が２^-5.24〜２^-7.18程度と最も低くなり、線形解読法による攻撃に対する耐性を最も高くすることができることがわかった。また、ｍａｘ（ａ，ｂ，ｃ）が２の場合でも、図１３に示すように、シフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）が（２、奇数、奇数）あるいは（奇数、２、奇数）の場合は、最良線形近似確率が２^-3.44〜２^-5.58程度と、ｍａｘ（ａ，ｂ，ｃ）が２の場合におけるその他の場合に比べて低くなり、線形解読法による攻撃に対する耐性を高くすることができることがわかった。なお、ここでは、入力Ｕのビット幅が１６の場合についてのみ結果を表示しているが、入力Ｕのビット幅が４、８の場合についても、シフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）として、任意の値（但し、１≦Ｓ_1n、Ｓ_2n、Ｓ_3n＜入力Ｕのビット幅）をピックアップし、評価した結果も、同様の傾向を示した。したがって、本発明者等は、上記の実施形態で用いる換字転置変換部２１_n、４１_nのビット列変換部６１に設定するアルゴリズム鍵Ｇ_nのシフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）として、（奇数、奇数、奇数）、（２、奇数、奇数）あるいは（奇数、２、奇数）となるように設定することで、線形解読法による攻撃に対する強度を、差分解読法による攻撃に対する場合と同様、向上させることができることを見出した。
【００９５】
（３）関数Ｆの入力Ｕのビット幅が３２ビットの場合の評価
上記（２）での結果を踏まえ、上記の実施形態で用いる換字転置変換部２１_n、４１_nのビット列変換部６１に設定するアルゴリズム鍵Ｇ_nのシフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）として、（２、奇数、奇数）あるいは（奇数、２、奇数）となるように設定し、入力Ｕのビット幅を２⁵＝３２とした場合における線形２段繰り返し型評価パターンの２段目の関数Ｆ₂の差分確率
lp(0→Γa)=|2prob{F₂(U)・Γa=U・0}−1|²
を評価した。結果を図１４に示す。この結果からわかるように、入力Ｕのビット幅３２の場合、シフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）が（２、奇数、奇数）あるいは（奇数、２、奇数）であれば、最良線形近似確率は２^-7.36〜２^-10.78程度であった。
【００９６】
３．総合評価
本発明者等は、上記１および２での結果を踏まえ、上記の実施形態で用いる換字転置変換部２１_n、４１_nのビット列変換部６１に設定するアルゴリズム鍵Ｇ_nのシフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）として、（２、奇数、奇数）あるいは（奇数、２、奇数）となるように設定し、図８に示す差分および線形近似確率を求めるための評価パターンの段数を１８段および２１段に増加させた場合における確率を推定した。この段数（１８段、２１段）は、実際の暗復号処理に用いられるラウンド数を考慮して決定した値である。推定は以下の前提に基づいて行っている。
【００９７】
▲１▼差分解読法：評価パターンの段数が２ｒの場合、この最良差分確率は、図８（ａ）に示す差分２段繰り返し型の最良差分確率dp(Δa→0)に対し、dp(Δa→0)^rで与えられる。
【００９８】
▲２▼線形解読法：評価パターンの段数が２ｒの場合、この最良差分確率は、図８（ｂ）に示す線形２段繰り返し型の最良線形近似確率lp(0→Γa)に対し、lp(0→Γa)^rで与えられる。
【００９９】
結果を図１５、１６に示す。これらの結果からわかるように、上記の実施形態で用いる換字転置変換部２１_n、４１_nのビット列変換部６１に設定するアルゴリズム鍵Ｇ_nのシフト値（Ｓ_1n、Ｓ_2n、Ｓ_3n）として、（２、奇数、奇数）あるいは（奇数、２、奇数）となるように設定した場合、入力Ｕのビット幅が２⁵＝３２であれば、確率は２^-70前後となる。したがって、差分解読法および線形解読法による攻撃に対して、計算量的に十分な強度を持った暗号アルゴリズムを構築することができる。
【０１００】
なお、上記の実施形態では、暗号変換部２０および復号変換部４０として、それぞれ図２、６に示すように、ラウンド数Ｎ分の換字転置変換部２１₁〜２１_N、４１₁〜４１_Nを有するものについて説明した。しかしながら、本発明はこれに限定されるものではなく、１つの換字転置変換部に、換字転置変換処理を、アルゴリズム鍵を変えながら、ラウンド数Ｎ回実行させるように構成してもよい。
【０１０１】
また、上記の実施形態では、データ送信機１およびデータ受信機２間で共有する暗復号用の鍵として４０ビットあるいは６４ビットを用い、鍵長が４０ビットおよび６４ビットのいずれであるかを示すための鍵長データとして１ビットのものを用いた場合について説明した。しかしながら、本発明はこれに限されるものではない。
【０１０２】
たとえば、暗号鍵を４０ビットから１２８ビットまで変更可能とし、鍵長データはこれらを選択できるように７ビットとしてもよい。この場合、鍵変換部２３、４３では、２個の３２ビット長である変換鍵Ｋ１、Ｋ２を生成できるように、入力された鍵長データの値に応じて、レジスタ２６に格納された暗復号用の鍵から抽出するビット列位置を変更できるようにセレクタを増加させればよい。また、暗復号用の鍵を６４以上とし、４個の３２ビット長である変換鍵を生成させ、Ｎ個の換字転置変換部を２組に分け、２個ずつ供給するような構成にしてもよい。
【０１０３】
あるいは、暗号変換で用いた換字転置変換部２１_n（１≦ｎ≦Ｎ）を複数個用いて、暗復号用の鍵から複数個の変換鍵を生成するようにしてもよい。
【０１０４】
図１７は、データ送信機１およびデータ受信機２の鍵変換部２３、４３の変形例を示す図である。この例では、６４ビットの暗復号用の鍵から８個の変換鍵からなる２５６ビットのシステム鍵を生成している。
【０１０５】
図示するように、鍵変換部２３ａ、４３ａは、拡張鍵保持部１００と、８段の換字転置変換部２１₁〜２１₈を有する。
【０１０６】
拡張鍵保持部１００には、鍵共有部１２、３２によりデータ送信機１およびデータ受信機２間で共有している２５６ビットの拡張鍵を保持する。この２５６ビットの拡張鍵は、図１において、データ送信機１の鍵情報保持部１５が、鍵管理機関３より、鍵長情報に代えて受け取り保持するようにすればよい。この場合、データ送信機１において、鍵情報保持部１５が拡張鍵保持部１００として機能するようにしてもよい。鍵拡張保持部１００は、自身が保持する２５６ビットの拡張鍵を８個の３２ビットの拡張鍵ＫＥ₁〜ＫＥ₈に分割し、図１７に示すように、２個づつ順番に、換字転置変換部２１₁〜２１₈に投入する。
【０１０７】
さて、上記構成の鍵変換部２３ａ、４３ａに、暗復号用の鍵（６４ビット）が入力されると、上位３２ビットデータＬ₀と下位３２ビットデータＲ₀に分割されて、換字転置変換部２１₁に入力される。そこで、拡張鍵ＫＥ₁、ＫＥ₂を用いて、第１回目の変換が行われ、その結果得られた３２ビットデータＬ₁と３２ビットデータＲ₁が次の段の換字転置変換部２１₂に入力される。また、３２ビットデータＬ₁は変換鍵Ｋ１として取り出される。次に、換字転置変換部２１₂にて、拡張鍵ＫＥ₃、ＫＥ₄を用いて、第２回目の変換が行われ、その結果得られた３２ビットデータＬ₂と３２ビットデータＲ₂が次の段の換字転置変換部２１₃に入力される。また、３２ビットデータＬ₂は変換鍵Ｋ２として取り出される。以上のような変換を順次行い、最終の段の換字転置変換部２１₈での変換の結果得られた３２ビットデータＬ₈を、変換鍵Ｋ８として取り出す。これにより、８個の３２ビットの変換鍵Ｋ１〜Ｋ８からなる２５６ビットシステム鍵が生成される。
【０１０８】
図１８は、図２に示す暗号化部１１において、鍵変換部２３に代えて図１７に示す鍵変換部２３ａを用いた場合の変形例を示す図である。
【０１０９】
図１８において、暗号変換部２０に平文（６４ビット）が入力されると、分割部２５ａにより上位３２ビットデータＬ₀と下位３２ビットデータＲ₀に分割されて、換字転置変換部２１₁に入力される。そこで、変換鍵Ｋ１、Ｋ２を用いて、第１回目の変換が行われ、その結果得られた３２ビットデータＬ₁と３２ビットデータＲ₁が次の段の換字転置変換部２１₂に入力される。このような変換が順次行われ、換字転置変換部２１₄にて、変換鍵Ｋ７、Ｋ８を用いた第４回目の変換が行われ、その結果得られた３２ビットデータＬ₄と３２ビットデータＲ₅が次の段の換字転置変換部２１₅に入力されると、使用する変換鍵をＫ１、Ｋ２とし、上記の要領で変換を繰り返す。
【０１１０】
図１９は、図６に示す復号化部３１において、鍵変換部４３に代えて図１７に示す鍵変換部４３ａを用いた場合の変形例を示す図である。
【０１１１】
図１９において、復号変換部４０に暗号文（６４ビット）が入力されると、分割部４５ａにより上位３２ビットデータＬ_Nと下位３２ビットデータＲ_Nに分割されて、換字転置変換部４１_Nに入力される。そこで、変換鍵Ｋ８、Ｋ７を用いて、第１回目の変換が行われ、その結果得られた３２ビットデータＬ_N-1と３２ビットデータＲ_N-1が次の段の換字転置変換部４１_N-1に入力される。このような変換が順次行われ、換字転置変換部４１_N-3にて、変換鍵Ｋ２、Ｋ１を用いた第４回目の変換が行われ、その結果得られた３２ビットデータＬ_N-4と３２ビットデータＲ_N-4が次の段の換字転置変換部４１_N-4に入力されると、使用する変換鍵をＫ８、Ｋ７とし、上記の要領で変換を繰り返す。この変換は、図１８を用いて説明した暗号変換の逆変換に相当する。
【０１１２】
また、上記の実施形態では、図５に示すビット列変換部６１のビット列変換器８２、８３、８５として、それぞれ、巡回シフト演算部９１、９２、９３と、加算演算部９５、９６、９８とでなるものを用いた場合について説明した。しかしながら、本発明はこれに限定されるものではなく、加算演算部９５、９６、９８各々の前段に乗算演算部を設けるようにしてもよい。
【０１１３】
図２０は、本実施形態で用いるビット列変換部６１の変形例を示す図である。この図に示すビット列変換部６１ａが図５に示すビット列変換部６１と異なる点は、加算演算部９５、９６、９８各々の前段に乗算演算部９５ａ、９６ａ、９８ａを設けた点である。
【０１１４】
図５に示すビット列変換部６１のビット列変換器８２、８３、８５各々について、入力をＸ、出力をＹとして変換を式で表わすと、
Y=X+(X<<<S_in)+A_in
但し、i=1,2,3、1≦n≦ラウンド数N
となる。
【０１１５】
一方、図２０に示すビット列変換部６１ａのビット列変換器８２、８３、８５各々について、入力をＸ、出力をＹとし変換を式で表わすと、
Y=B_inX+(X<<<S_in)+A_in
但し、i=1,2,3、1≦n≦ラウンド数N
となる。
【０１１６】
ここで、処理ビット幅（入出力Ｘ、Ｙのビット長）をｍとした場合、２^Sin＋Ｂ_inと２^m−１とが互いに素となる値となるように、Ｂ_inとＳ_inを設定することで、ビット列変換部６１ａのビット列変換器８２、８３、８５各々での関数を全単射関数に近づけることができる。これにより、差分解読法および線形解読法による攻撃する強度をさらに強化することができる。なお、乗算演算部９５ａ、９６ａ、９８ａでの乗算値Ｂ_1n、Ｂ_2n、Ｂ_3nは、シフト値Ｓ_1n、Ｓ_2n、Ｓ_3nや加算値Ａ_1n、Ａ_2n、Ａ_3nと同様、アルゴリズム鍵Ｇｎに含まれるパラメータとして、アルゴリズム鍵保持部２４、４４に保持させるようにすればよい。
【０１１７】
次に、上記説明した本実施形態の暗号通信システムの自動料金徴収システムへの適用例について説明する。
【０１１８】
ここで、自動料金徴収システムとは、自動車が有料道路を通過する時に、有料道路上に設置されている路側機により、自動車を停止させることなく、運転手のＩＣカードから通行料金を電子決済によって徴収するシステムのことである。自動料金徴収システムは、有料道路の料金所での渋滞解消や、ＩＣカードでの電子決済化による利便性の向上など、様々な期待が寄せられている。
【０１１９】
図２１に自動料金徴収システムの概略構成を示す。
【０１２０】
図示するように、自動料金徴収システムは、自動車２００に搭載された車載機２０２と、ＩＣカード２０３と、路側機２０１とからなる。
【０１２１】
車載機２０２は、ＩＣカード２０３が装着自在に構成されている。ＩＣカード２０３は、たとえば自動車２００の運転手により、運転時に車載機２０２に装着される。
【０１２２】
路側機２０１は、たとえば有料道路の料金ゲートに設置されるものであり、自動車２００が通過する際に、通行料金を徴収する機能を有している。
【０１２３】
ＩＣカード２０３には、予め自動料金徴収システムの契約情報（ＩＣカードの持ち主の情報や決済方法に関する情報（たとえば、クレジット決済にするかあるいは電子マネーによる現金決済にするかなど）が格納されており、自動車２００が路側機２０１を通過する時に、ＩＣカード２０３が挿入されている車載機２０２を介した無線通信により、路側機２０１にこの契約情報を転送する。そして、その後、路側機２０１から経路情報や決済情報を受信する。
【０１２４】
これらの処理を安全および正確に行うためには、契約情報、経路情報および決済情報の正当性の検証と、不正な改竄や盗聴を防止する機能が必要である。したがって、ＩＣカード２０３と車載機２０２との間、および、車載機２０２と路側機２０１との間において、通信相手を正当であると認識するための相手認証処理や、交換データの暗復号化のために用いる鍵の共有処理や、共有した鍵を用いた暗号通信のための処理を行う必要がある。この相手認証処理、鍵共有処理および暗号通信に、上記の実施形態で説明した暗号通信システムにおける暗復号処理を適用することができる。
【０１２５】
以上の処理を実現するために、車載機２０２、ＩＣカード２０３および路側機２０１には、鍵管理機関２０４が発行した、共通のアルゴリズム鍵とライセンス鍵とを、秘密情報として、事前に保持しておく。たとえば、製造時に各々の内部に埋め込んでおく。
【０１２６】
ここで、アルゴリズム鍵の詳細およびアルゴリズム鍵によって定まる暗号変換および復号変換の詳細は前述した通りである。
【０１２７】
また、ライセンス鍵は、相手認証処理および鍵共有処理を正しく行うために用いる。たとえば、ＩＣカード２０３と車載機２０２が通信を行うために、ＩＣカード２０３が正当な機器であることを、車載機２０２が確認する場合を考える。このためには、ＩＣカード２０３は、自分が保持しているライセンス鍵が正しいことを、車載機２０２に証明すればよい。ここで、ライセンス鍵は秘密情報であるので、ＩＣカード２０３は自分のライセンス鍵を明かすことなく、それが正しいことを、車載機２０２に証明しなければならない。この証明は、暗号通信技術を用いることで実現できる。たとえば、対称鍵暗号方式を用いた手法が、セキュリティメカニズムの国際規格であるＩＳＯ９７９８−２で説明されている。この対称鍵暗号方式の具体例として、上記の実施形態で説明した暗号通信システムにおける暗復号処理を適用することができる。
【０１２８】
次に、図２１に示す路側機２０１、車載機２０２およびＩＣカード２０３各々の構成要素について説明する。
【０１２９】
路側機２０１は、無線通信部２３２と、暗号化・復号化部２３０と、相手認証・鍵共有処理部２３３と、データ保持部２３４と、主制御部２３５とを有する。
【０１３０】
車載機２０２は、無線通信部２１２と、暗号化・復号化部２１０と、、ＩＣカード通信部２１１と、相手認証・鍵共有処理部２１３と、データ保持部２１４と、主制御部２１５とを有する。
【０１３１】
ＩＣカード２０３は、ＩＣカード通信部２２１と、暗号化・復号化部２２０と、相手認証・鍵共有処理部２２３と、データ保持部２２４と、主制御部２２５とを有する。
【０１３２】
ここで、暗号化・復号化部２１０、２２０、２３０は、上記の実施形態で説明した暗号通信システムの暗号化部１１および復号化部３１（図１参照）の両方を備えており、データの暗号化および復号化を行うことが可能である。
【０１３３】
また、ＩＣカード通信部２１１、２２１は、車載機２０２とＩＣカード２０３との間の通信処理を行うために用いられ、無線通信部２１２、２３２は、車載機２０２と路側機２０１との間の無線通信処理を行うために用いられる。
【０１３４】
さらに、認証・鍵共有処理部２１３、２２３、２３３は、通信相手を正当であると認識するために行う相手認証処理と、データの暗復号化のために用いる鍵の共有処理を行う。
【０１３５】
認証・鍵共有処理部２１３は、暗号化・復号化部２１０が提供する暗号変換機能および復号変換機能を用いて、暗号通信技術を用いた相手認証処理および鍵共有処理を行う。同様に、認証・鍵共有処理部２２３は、暗号化・復号化部２２０が提供する暗号変換機能および復号変換機能を用いて、暗号通信技術を用いた暗号相手認証処理および鍵共有処理を行い、認証・鍵共有処理部２３３は、暗号化・復号化部２３０が提供する暗号変換機能および復号変換機能を用いて、暗号通信技術を用いた暗号相手認証処理および鍵共有処理を行う。
【０１３６】
データ保持部２１４、２２４、２３４は、鍵管理機関２０４から取得した、アルゴリズム鍵およびライセンス鍵を保持しておくのに用いられる。また、契約情報や経路情報や決済情報も保持できるのもとする。
【０１３７】
図２２は、図２１に示す自動料金徴収システムの通信フローを示す図である。
【０１３８】
図示するように、まず、ＩＣカード２０３が車載機２０２に装着されると、ＩＣカード２０３と車載機２０２との間で、相手認証・鍵共有処理２４０が行われる。そして、相手認証・鍵共有処理２４０が成功した後、ＩＣカード２０３は、契約情報を車載機２０２に転送するために暗号通信２４１を行う。車載機２０２は、ＩＣカード２０３の契約情報を取得すると、車載機２０２内のデータ保持部２１４に秘密に保持しておく。
【０１３９】
次に、車載機２０２を搭載した自動車２００が路側機２０１を通過すると、車載機２０２と路側機２０１の間で、相手認証・鍵共有処理２５０が行われる。そして、相手認証・鍵共有処理２５０が成功した後、車載機２０２は、先にＩＣカード２０３から取得しデータ保持部２１４に秘密に保持して契約情報を、路側機２０１に転送するために、暗号通信２５１を行う。路側機２０１は、車載機２０２から契約情報を受け取ると、当該契約情報にしたがい、当該契約情報により特定されるＩＣカード２０３の持ち主より通行料金を徴収し、決済を行う。暗号通信２５１は、路側機２０１から車載機２０２に、この決済情報や経路情報（たとえば決済を行った路側機２０１（料金を徴収した有料道路上の場所）を特定するための情報）を転送するためにも用いられる。
【０１４０】
次に、車載機２０２は、路側機２０１から得た決済情報や経路情報をＩＣカード２０３に転送するために、暗号通信２６１を行う。
【０１４１】
ここで、道路通行料金の決済はＩＣカード２０３と路側機２０１との間で行われるが、ＩＣカード２０３と路側機２０１1とは、車載機２０２を介さないと通信が行えない。この場合、車載機２０２が不正処理を行うことで、不正な決済が行われてしまう可能性も考えられる。このような事態に備え、路側機２０1は、ＩＣカード２０３との決済で用いた車載機２０２を特定できるようにしておく必要がある。たとえば、車載機２０２に識別番号を割り当て、車載機２０２は、ＩＣカード２０３との相手認証・鍵共有処理２４０の中で、車載機２０２の識別番号をＩＣカード２０３に転送するようにする。ＩＣカード２０３は、車載機２０２の識別番号とＩＣカード２０３の決済履歴の両方に対する、デジタル署名を生成して返送する。そして、車載機２０２は、自分の識別番号と、ＩＣカード２０３から取得したデジタル署名を、路側機２０１に、相手認証・鍵共有処理２５０の中で転送するようにする。その後、路側機２０１は、ＩＣカード２０３が生成したデジタル署名を検証することで、車載機２０２がいつ用いられたかを特定することが可能になる。
【０１４２】
また、暗号通信２４１、２５１、２６１において、通信路上を流れる暗号化データを第三者に改竄されないようにしておく必要がある。これを実現するためには、受信したメッセージが正当であることを判定できる、メッセージ認証を行う必要がある。メッセージ認証を行うためには、送信者と受信者が予めメッセージ認証鍵を秘密に共有しておく。メッセージ認証鍵の共有は、たとえば図１２に示した相手認証・鍵共有処理２５０内で行う。そして、送信者が、転送するメッセージとメッセージ認証鍵から、メッセージ認証子（MAC: Message Authentication Code）と呼ばれるデータを生成する。送信者は、メッセージと一緒にメッセージ認証子を、受信者に転送する。受信者は、受信したメッセージ認証子を、メッセージ認証鍵を用いて検証する。この検証によって、受信したメッセージが改竄されているかどうかを判定できる。メッセージ認証に関しては、たとえば対称鍵暗号方式を用いた手法が、セキュリティメカニズムの国際規格であるＩＳＯ９７９７で説明されている。この対称鍵暗号方式の具体例として、上記の実施形態で説明した暗号通信システムにおける暗復号化処理を適用することができる。
【０１４３】
図２３は、図２２の暗号通信２４１において、メッセージ認証を含めた例の詳細フローを示している。
【０１４４】
図示するように、まず、ＩＣカード２０３は、メッセージ認証子の生成を、ＭＡＣ生成処理２６１で行う。次に、転送メッセージとメッセージ認証子を結合する結合処理２６２を行う。その後、転送メッセージとメッセージ認証子を結合したデータを暗号化する暗号処理２６３を行って暗号化データを生成する。
【０１４５】
一方、車載機２０２は、ＩＣカードより暗号化データを受信すると、まず復号化処理２６４を行う。その後、分離処理２６５を行うことで、ＩＣカードが転送した転送メッセージとメッセージ認証子とを復元する。次に、復元されたメッセージ認証子を検証するＭＡＣ検証処理２６６を行って、受信した転送メッセージの正当性を検証する。
【０１４６】
これによって、課金情報や経路情報などの盗聴や改竄されてはならないデータを安全に交換することが可能になる。
【０１４７】
以上の処理を行うことにより、通行料金をＩＣカード２０３に課金し、さらに路側機２０１で課金情報を管理することができる。
【０１４８】
【発明の効果】
以上説明したように、本発明によれば、変換の繰り返し回数を増やすことなく、暗号解読に強い高速な暗号・復号変換を実現することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態が適用された暗号通信システムの概略構成図である。
【図２】図１に示す暗号化部１１の概略構成図である。
【図３】図２に示す鍵変換部２３の概略構成図である。
【図４】図２に示す換字転置変換部２１_n（１≦ｎ≦ラウンド数Ｎ）の概略構成図である。
【図５】図４に示すビット列変換部６１の概略構成図である。
【図６】図１に示す復号化部３１の概略構成図である。
【図７】図６に示す換字転置変換部４１_n（１≦ｎ≦ラウンド数Ｎ）の概略構成図である。
【図８】差分解読法および線形解読法による暗号解読に対する強度評価実験に用いた評価パターンを示す図である。
【図９】図５に示すビット列変換部６１において、変換鍵Ｋ１＝Ｋ２＝０、加算値Ａ_1n＝１、Ａ_2n＝Ａ_3n＝０とした場合に得られる変換を関数Ｆ、当該関数Ｆの入力Ｕのビット幅を１６とし、図８に示す差分２段繰り返し型評価パターンを用いた場合の評価結果を示す図である。
【図１０】図５に示すビット列変換部６１において、変換鍵Ｋ１＝Ｋ２＝０、加算値Ａ_1n＝１、Ａ_2n＝Ａ_3n＝０とした場合に得られる変換を関数Ｆ、当該関数Ｆの入力Ｕのビット幅を１６とし、図８に示す差分２段繰り返し型評価パターンを用いた場合の差分確率の評価結果を示す図である。
【図１１】図５に示すビット列変換部６１において、変換鍵Ｋ１＝Ｋ２＝０、加算値Ａ_1n＝１、Ａ_2n＝Ａ_3n＝０とした場合に得られる変換を関数Ｆ、当該関数Ｆの入力Ｕのビット幅を３２とし、図８に示す差分２段繰り返し型評価パターンを用いた場合の差分確率の評価結果を示す図である。
【図１２】図５に示すビット列変換部６１において、変換鍵Ｋ１＝Ｋ２＝０、加算値Ａ_1n＝１、Ａ_2n＝Ａ_3n＝０とした場合に得られる変換を関数Ｆ、当該関数Ｆの入力Ｕのビット幅を１６とし、図８に示す線形２段繰り返し型評価パターンを用いた場合の線形近似確率の評価結果を示す図である。
【図１３】図５に示すビット列変換部６１において、変換鍵Ｋ１＝Ｋ２＝０、加算値Ａ_1n＝１、Ａ_2n＝Ａ_3n＝０とした場合に得られる変換を関数Ｆ、当該関数Ｆの入力Ｕのビット幅を１６とし、図８に示す線形２段繰り返し型評価パターンを用いた場合の線形近似確率の評価結果を示す図である。
【図１４】図５に示すビット列変換部６１において、変換鍵Ｋ１＝Ｋ２＝０、加算値Ａ_1n＝１、Ａ_2n＝Ａ_3n＝０とした場合に得られる変換を関数Ｆ、当該関数Ｆの入力Ｕのビット幅を３２とし、図８に示す線形２段繰り返し型評価パターンを用いた場合の線形近似確率の評価結果を示す図である。
【図１５】図８に示す差分および線形近似確率を求めるための評価パターンの段数を１８段および２１段に増加させた場合における差分確率および線形近似確率を推定値を示す図である。
【図１６】図８に示す差分および線形近似確率を求めるための評価パターンの段数を１８段および２１段に増加させた場合における差分確率および線形近似確率を推定値を示す図である。
【図１７】図１に示すデータ送信機１およびデータ受信機２の鍵変換部２３、４３の変形例を示す図である。
【図１８】図２に示す暗号化部１１において、鍵変換部２３に代えて図１７に示す鍵変換部２３ａを用いた場合の変形例を示す図である。
【図１９】図６に示す復号化部３１において、鍵変換部４３に代えて図１７に示す鍵変換部４３ａを用いた場合の変形例を示す図である。
【図２０】図５に示すビット列変換部６１の変形例を示す図である。
【図２１】本発明の一実施形態である暗号通信システムが適用された自動料金徴収システムの概略構成図である。
【図２２】図２１に示す自動料金徴収システムの通信フローを示す図である。
【図２３】図２２の暗号通信２４１において、メッセージ認証を含めた例の詳細フローを示す図である。
【符号の説明】
１…データ送信機
２…データ受信機
３、２０４…鍵管理機関
１１、１１ａ…暗号化部
１２、３２…鍵共有部
１３、３３…データ処理部
１４、３４…通信処理部
１５…鍵長情報保持部
２０…暗号変換部
２１₁〜２１_N、４１₁〜４１_N…換字転置変換部
２３、２３ａ、４３、４３ａ…鍵変換部
２４、４４…アルゴリズム鍵保持部
２５ａ、４５ａ…分割部
２５ｂ、４５ｂ…結合部
２６…レジスタ
２７…マルチプレクサ
２８、９５、９６、９８…加算演算部
３１、３１ａ…復号化部
４０…復号変換部
６１、６１ａ…ビット列変換部
６２、９４、９７…排他的論理和演算部
８１〜８５…ビット列変換器
９１〜９３…巡回シフト演算部
９５ａ、９６ａ、９８ａ…乗算演算部
１００…拡張鍵保持部
２００…自動車
２０１…路側機
２０２…車載機
２０３…ＩＣカード
２１０、２２０、２３０…暗号化・復号化部
２１１、２２１…ＩＣカード通信部
２１２、２３２…無線通信部
２１３、２２３、２３３…相手認証・鍵共有処理部
２１４、２２４、２３４…データ保持部
２１５、２２５、２３５…主制御部[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an encryption / decryption technique for digital data transmitted between a computer, an information home appliance, an automatic fee collection device, and the like.
[0002]
[Prior art]
In general, in digital information home appliances, an encryption technique for preventing unauthorized copying of digital data is essential. For example, when digital video data received by a digital broadcast receiver is digitally recorded on a digital recording device, if the digital video data has a copyright, a function for protecting the digital video data is required for each device.
[0003]
In order to realize such a copyright protection system, it is necessary to prevent data tampering and unauthorized copying by using encryption techniques such as digital data copy restrictions, device authentication, and real-time digital data encryption. I must.
[0004]
As a conventional example of encryption technology, for example, a common key encryption method represented by DES encryption disclosed in Japanese Patent Laid-Open No. 51-108701 can be cited. Many of the common key cryptosystems are characterized in that complex encryption conversion is configured by repeatedly performing simple conversion. Various attempts have been made to make these ciphers more secure. For example, by increasing the number of simple conversion iterations, the statistical characteristics of the ciphertext can be further disturbed, making cryptanalysis difficult.
[0005]
[Problems to be solved by the invention]
However, increasing the number of conversion iterations increases the processing time required for cryptographic conversion. Therefore, there is a problem that the security enhancement measure by increasing the number of times of simple conversion is not suitable for the real-time encryption process in the copyright protection system described above.
[0006]
The present invention has been made on the basis of the above circumstances, and an object of the present invention is to realize high-speed encryption / decryption conversion that is resistant to cryptanalysis without increasing the number of repetitions of conversion.
[0007]
[Means for Solving the Problems]
To achieve the above object, the encryption device of the present invention is an encryption device that encrypts plaintext data using an encryption key,
The cryptographic process is performed by applying the encryption key to the input first and second data, and the result is output a plurality of times as the first and second data to be input next time. Cryptographic conversion means;
Dividing the plaintext data into two, and outputting the result as first and second data to be input to the first cryptographic operation processing of the cipher conversion means;
Combining the first and second data output from the cryptographic operation processing of the last round of the cryptographic conversion means, and the cryptographic combining means for outputting the result as encrypted data,
The cryptographic operation processing is
Cryptographic bit string conversion process for performing bit string conversion of input first data and Cryptographic exclusive logic for calculating an exclusive OR of output data of the encryption bit string conversion process and input second data A sum operation process,
The output data of the exclusive OR operation for encryption is set as the first data to be input next time, and the input first data is output as the second data to be input next time,
The encryption bit string conversion process includes:
A first exclusive OR operation process for calculating an exclusive OR of the input data and the first key data generated from the encryption key or a part thereof;
Shift number S in the input data₁A first cyclic shift calculation process for performing the cyclic shift calculation process, and a first addition calculation process for adding the input data and the output data of the first cyclic shift calculation process. 1 logical operation processing;
Shift number S in the input data₂The second cyclic shift calculation process for performing the cyclic shift calculation process and the second addition calculation process for performing the addition calculation process of the input data and the output data of the second cyclic shift calculation process. A second logical operation process;
A second exclusive OR operation process for calculating an exclusive OR of the input data and the second key data generated from the encryption key or a part thereof;
Shift number S in the input data_ThreeA third cyclic shift calculation process for performing the cyclic shift calculation process, and a third addition calculation process for performing an addition calculation process of the input data and the output data of the third cryptographic cyclic shift calculation process; And a third logical operation process consisting of:
Shift number S in the encryption bit string conversion process₁, S₂And S_ThreeAre all odd or S₁And S₂Is set to be an odd value and the remaining two are set to odd numbers, and S₁, S₂And S_ThreeThe values are set so as not to match each other.
[0008]
Here, the shift number S in the encryption bit string conversion process₁, S₂And S_ThreeIs set to N (N is 2 or more) times of the cryptographic operation processing executed continuously.₁, S₂And S_ThreeThe pattern of the value of S is set to N times of the cryptographic operation processing executed successively following the N times of the cryptographic operation processing.₁, S₂And S_ThreeIt may be set not to match the pattern of the value of.
[0009]
Further, the shift number S in the encryption bit string conversion process₁, S₂And S_ThreeThe combination of the values may be a combination of three values common to each of the cryptographic operation processes executed a plurality of times.
[0010]
Next, the decryption device of the present invention is a decryption device that decrypts and converts encrypted data generated by the encryption device into plaintext data using a decryption key that is common with the encryption key used in the encryption device,
Decryption operation processing is performed by applying the decryption key to the input first and second data and performing the operation processing as first and second data to be input next time. Decryption conversion means for performing the same number of times as the cryptographic operation processing of the encryption conversion means,
A splitting unit for decryption that divides the encrypted data into two, and outputs the result as first and second data to be input to the decryption calculation process of the first round of the decryption conversion unit;
A decoding combining unit that combines the first and second data output from the decoding calculation process of the last round of the decoding conversion unit, and outputs the result as equal data;
The decryption calculation process is:
A decryption bit string conversion process for performing the same process as the encryption bit string conversion process in the cryptographic operation process of the cipher conversion unit and an output data of the decryption bit string conversion process are input to the input second data. And an exclusive OR operation process for decoding for calculating an exclusive OR with the first data,
The output data of the exclusive OR operation for decoding is the second data to be input next time, and the input second data is output as the first data to be input next time,
Shift number S in the decoding bit string conversion process₁, S₂And S_ThreeIs the number of shifts S set in the last cipher operation processing of the cipher conversion means is the value set in the first cipher operation processing of the decryption conversion means₁, S₂And S_ThreeThe value set in the last decryption calculation process of the decryption conversion means is the number of shifts S set in the first encryption calculation process of the cipher conversion means₁, S₂And S_ThreeIn order of execution between each of the decryption operation processes executed by the decryption conversion means a plurality of times and each of the encryption operation processes executed a plurality of times by the encryption conversion means so as to match each of the values of The reverse order is set.
[0011]
DETAILED DESCRIPTION OF THE INVENTION
Embodiments of the present invention will be described below with reference to the drawings.
[0012]
FIG. 1 is a schematic configuration diagram of a cryptographic communication system to which an embodiment of the present invention is applied. As shown in the figure, the cryptographic communication system of the present embodiment creates a ciphertext (points to data that has undergone cryptographic conversion processing) by cipher-converting plaintext (points to data that has not been subjected to cryptographic transformation processing). A data transmitter 1 for transmission and a data receiver 2 for obtaining a plaintext by decrypting and converting the ciphertext transmitted from the data transmitter 1. In FIG. 1, a key management organization 3 is an organization for providing an algorithm key (which will be described later) for determining various parameters used for encryption / decryption conversion to the data transmitter 1 and the data receiver 2.
[0013]
As shown in the figure, the data transmitter 1 includes a data processing unit 13 that performs predetermined processing on data to generate plaintext, and an encryption unit that encrypts plaintext output from the data processing unit and creates ciphertext 11, a key sharing unit 12 that generates a key used for encryption / decryption processing and performs processing for sharing the key with the data receiver 2, and a key length that determines the key length of the key generated by the key sharing unit 32 A key length information holding unit 15 that holds data and a communication processing unit 14 that communicates with the data receiver 2 are included.
[0014]
On the other hand, the data receiving device 2 includes a communication processing unit 34 that communicates with the data transmitter 1, and a decryption unit 31 that decrypts and converts the ciphertext received from the data transmitter 1 via the communication processing unit 34. A key processing unit for sharing a key used for encryption / decryption processing between the data processing unit 33 that performs predetermined data processing on the plaintext output from the decryption unit 31 and the key sharing unit 12 of the data transmitter 1 32.
[0015]
Here, as the data transmitter 1 and the data receiver 2, for example, a digital broadcast transmitter and a digital broadcast receiver can be considered. In this case, the data processing units 13 and 33 handle digital program data such as the MPEG2-TS (Transport Stream) format distributed by the digital broadcasting service. That is, the data processing unit 13 performs processing such as compression / multiplexing of digital program data, and the data processing unit 33 performs processing such as demultiplexing / decompression of digital program data.
[0016]
When performing cryptographic communication between the data transmitter 1 and the data receiver 2, the data transmitter 1 and the data receiver 2 first share data called a key necessary for encrypting and decrypting data. Do. Key sharing is performed when the key sharing unit 12 of the data transmitter 1 and the key sharing unit 32 of the data receiver 2 exchange messages with each other via the communication processing unit 14 and the communication processing unit 34. . At this time, the key length of the shared key is determined based on the key length data held in the key length information holding unit 15 of the data transmitter 1.
[0017]
The key sharing performed between the data transmitter 1 and the data receiver 2 is performed between the two parties periodically or every occurrence of a predetermined event, for example, every time encryption communication is performed or every predetermined communication time. It is desirable to change the shared key. This is because the ciphertext generated is different for different keys, making it difficult for a third party to decrypt the ciphertext. There are various methods for sharing the key. For example, the key sharing method of Deffy Hellman (for example, Tatsuaki Okamoto et al., “Modern Crypto”, published by Sangyo Tosho Co., Ltd., pages 200 to 202). Described in detail). If this is used, even if a third party eavesdrops on messages exchanged for key sharing, it becomes very difficult to estimate the key from them, and it becomes possible to share different keys securely each time. .
[0018]
After the key sharing is completed, the data transmitter 1 processes the data to be transmitted by the data processing unit 12 to generate plain text, and inputs this into the encryption unit 11. The encryption unit 11 includes an encryption conversion unit 20, a key conversion unit 23, and an algorithm key holding unit 24. The key conversion unit 23 receives a key shared with the data receiver 2 and key length data indicating the key length from the key sharing unit 12, and based on this, a plurality of data called conversion keys are received. Generate. The algorithm key holding unit 24 holds a plurality of data called algorithm keys. The conversion algorithm performed by the cryptographic conversion unit 20 is determined by an algorithm key. The cipher conversion unit 20 performs cipher conversion on the plain text using the conversion key generated by the key conversion unit 23 and the algorithm key held by the algorithm key holding unit 24, and outputs the cipher text. The ciphertext output from the encryption unit 11 is transmitted to the data receiving device 2 via the communication processing unit 14.
[0019]
On the other hand, the data receiver 2 receives the ciphertext transmitted from the data transmitter 1 by the communication processing unit 34 and inputs it to the decryption unit 31. The decryption unit 31 includes a decryption conversion unit 40, a key conversion unit 43, and an algorithm key holding unit 44. The key conversion unit 43 has the same configuration as the key conversion unit 23 included in the encryption unit 11 of the data transmitter 2 described above, and a key shared with the data transmitter 1 and a key indicating the key length thereof. Long data is received from the key sharing unit 32, and based on this, the same conversion key as the conversion key generated by the key conversion unit 23 included in the encryption unit 11 of the data transmitter 2 is generated. The algorithm key holding unit 44 holds the same algorithm key as the algorithm key held by the algorithm key holding unit 24 included in the encryption unit 11 of the data transmitter 2 described above. The conversion algorithm performed by the decryption conversion unit 40 is determined by the algorithm key. The decryption conversion unit 40 decrypts and converts the ciphertext using the conversion key generated by the key conversion unit 43 and the algorithm key held by the algorithm key holding unit 44, and outputs a plaintext. The plain text output from the decryption unit 31 is input to the data processing unit 33, where data processing is performed.
[0020]
In order to perform cryptographic communication between the data transmitter 1 and the data receiver 2, as described above, an algorithm key for determining a conversion algorithm used in the encryption conversion unit 20 of the encryption unit 11 of the data transmitter 1 and The algorithm key for determining the conversion algorithm used in the decoding conversion unit 40 of the decoding unit 31 of the data receiver 2 must be the same. Therefore, by treating this algorithm key as secret information, it is possible to realize encrypted communication having an authentication function. In other words, if only a legitimate device holds the correct algorithm key, encrypted communication can be performed only when the communication partner is a legitimate device.
[0021]
In this embodiment, a key management organization 3 for generating and centrally managing algorithm keys is provided as shown in FIG. 1 so that only valid devices hold correct algorithm keys. Legitimate devices (here, the data transmitter 1 and the data receiver 2) obtain the algorithm key from the key management organization 3 safely so as not to leak outside. For example, the algorithm key managed by the key management organization 3 at the time of manufacturing the data transmitter 1 and the data receiver 2 is stored in advance in the algorithm key storage unit 24 and the algorithm key storage unit 44. At this time, key length data is also stored in the key length information holding unit 15 of the data receiver 1.
[0022]
By doing so, ciphertext transmitted by a legitimate device holding the correct algorithm key can be decrypted only by a legitimate device holding the correct algorithm key. Moreover, since the algorithm key is also secret information in addition to the key, it is possible to make it more difficult for a third party to decipher the ciphertext flowing on the communication path.
[0023]
Further, the data transmitter 1 obtains the key length data from the key management organization 3, and generates the encryption / decryption key shared with the data receiver 2 based on the key length data, so the key length of the key is updated. It becomes possible. For example, if the updated key length data is embedded in a newly manufactured data transmitter 1, a key with an updated key length may be used in encrypted communication with the newly manufactured data transmitter 1. It becomes possible. As a result, the key length of the encryption / decryption key can be lengthened in the future, and the security can be further improved. It is also possible to change the key length according to the region where the product is shipped.
[0024]
Next, more detailed configurations of the encryption unit 11 of the data transmitter 1 and the decryption unit 31 of the data receiver 2 will be described.
[0025]
First, the encryption unit 11 of the data transmitter 1 will be described.
[0026]
FIG. 2 is a schematic configuration diagram of the encryption unit 11 shown in FIG. Each component of the encryption unit 11 shown in FIG. 2 may be realized in hardware by an integrated logic IC such as an ASIC (Application Specific Integrated Circuits) or an FPGA (Field Programmable Gate Array), or It may be realized by software by a computer such as a DSP (Digital Signal Processor).
[0027]
The key conversion unit 23 receives a 40-bit or 64-bit encryption / decryption key and 1-bit key length data from the key sharing unit 15, and generates 32-bit conversion keys K1 and K2 based on these keys. . Here, the value of the key length data is 0 if the key is 40 bits, and 1 if the key is 64 bits.
[0028]
FIG. 3 is a schematic configuration diagram of the key conversion unit 23 shown in FIG.
[0029]
As illustrated, the key conversion unit 23 includes a 64-bit register 26, a multiplexer 27, and an addition operation unit 28. The key received from the key sharing unit 12 is first stored in the register 26. Here, if the key length is 40 bits, the value is stored in the lower 40 bits of the register 26. If the key length is 64 bits, the value is stored in all the registers 26. Stored. Next, the lower 32 bits of the register 26 are set as the conversion key K1. Next, if the value of the key length data received from the key sharing unit 12 is 0, 32 bits from the lower 9th bit to the lower 40th bit of the register 26 are selected as the output value of the multiplexer 27, and the output value is added. The unit 28 adds 32 bits to the conversion key K1, and the result is the conversion key K2. On the other hand, if the value of the key length data received from the key sharing unit 12 is 1, the upper 32 bits of the register 26 are selected as the output value of the multiplexer 27, and the output value is added to the conversion key K1 and the 32-bit value by the addition operation unit 28. The result is the conversion key K2. Here, 32-bit addition means that the normal addition result is 2³²This is the arithmetic processing that results from the remainder divided by.
[0030]
Returning to FIG. 2, the cryptographic conversion unit 20 receives the input two 32-bit data L_i, R_iThe conversion keys K1 and K2 are applied to (0 ≦ i ≦ N) to perform the substitution transposition conversion process, and the result is input to the two 32-bit data L to be input to the next stage._{i + 1}, R_{i + 1}N-stage substitution transposition converter 21 that outputs as₁~ 21_NAnd the 64-bit plaintext output from the data processing unit 13 is converted into the upper 32-bit data L₀And lower 32 bits data R₀Into the first-stage substitution transpose conversion unit 21₁The dividing unit 25a to be input to the subordinate, and the substitution transposition conversion unit 21 at the last stage_NTwo 32-bit data L output from_N, R_NThe data L_NIs the upper bit data, data R_NAre combined as lower-order bit data, and a combining unit 25b for obtaining a 64-bit ciphertext. Here, the substitution transposition conversion unit 21_nThe conversion algorithm of (1 ≦ n ≦ N) is an algorithm key G held in the algorithm key holding unit 24._nDetermined by.
[0031]
When the 64-bit plaintext output from the data processing unit 13 is input to the encryption conversion unit 20 having the above configuration, the upper 32 bit data L is output by the dividing unit 25a.₀And lower 32 bits data R₀Into a transliteration conversion unit 21₁Is input. Therefore, the first encryption conversion is performed using the conversion keys K1 and K2. Subsequently, the substitution transposition conversion unit 21₁32-bit data L obtained as a result of cryptographic conversion₁And 32-bit data R₁Is the substitution transposition conversion unit 21 in the next stage.₂Then, the second encryption conversion is performed using the conversion keys K1 and K2. Substitution transpose conversion unit 21₂32-bit data L obtained as a result of cryptographic conversion₂And 32-bit data R₂Is the substitution transposition conversion unit 21 of the next stage._ThreeThe same processing is performed there. The cipher conversion as described above is repeated N times, and the last-stage transliteration conversion unit 21_N32-bit data L obtained as a result of cryptographic conversion_NAnd 32-bit data R_NAre combined by the combining unit 25b to obtain a ciphertext. Hereinafter, the total number N of cryptographic conversion repetitions is referred to as the number of rounds.
[0032]
FIG. 4 shows the substitution transposition conversion unit 21 shown in FIG._nIt is a schematic block diagram of (1 <= n <= N).
[0033]
As shown in the figure, the substitution transposition conversion unit 21_nIs composed of a bit string conversion unit 61 and an exclusive OR operation unit 62, and the input 32-bit data L_n-1And 32-bit data R_n-1Is converted to 32-bit data L using the conversion keys K1 and K2._nAnd 32-bit data R_nConvert to
[0034]
Substitution transpose conversion unit 21_nFirst, the input 32-bit data L_n-1Is input to the bit string converter 61. The bit string conversion unit 61 uses the algorithm key G_nThe input 32-bit data L using the conversion keys K1 and K2 in accordance with the conversion algorithm determined by_n-1Add bit string conversion processing to. The bit string conversion process can be expressed by the following formula using the input value of the bit string conversion unit 61 as U and the output value as Z.
[0035]
Z = FG_n(K1, K2, U)
Here, the function FG_n(X) is the algorithm key G_nRepresents the conversion of the bit string conversion unit 61 determined by. Algorithm key G_nConsists of the following data.
[0036]
G_n= (A_1n, A_2n, A_3n, S_1n, S_2n, S_3n)
Where A_1n, A_2n, A_3nIs an addition value used for the addition operation and is 32-bit data. S_1n, S_2n, S_3nIs a shift value used for the left cyclic shift calculation, and all take values of 1 to 31.
[0037]
FIG. 5 is a schematic configuration diagram of the bit string converter 61 shown in FIG.
[0038]
As shown in the figure, the bit string conversion unit 61 includes five bit string converters 81 to 85.
[0039]
The bit string converter 81 includes an exclusive OR unit 94, and the 32-bit data L input to the bit string converter 61._n-1And an exclusive OR of the conversion key K1. As shown, the input of the bit string converter 81 (that is, the 32-bit data L_n-1) Is U and the output value is V, the conversion of the bit string converter 81 can be expressed as follows.
[0040]
V = K1 (+) U
Here, the notation X (+) Y indicates an exclusive OR operation between X and Y.
[0041]
The bit string converter 82 includes a cyclic shift calculation unit 91 and an addition calculation unit 95. The cyclic shift calculation unit 91 outputs the output from the bit string converter 81 to the algorithm key G_nShift value S_1n(1 ≦ S_1nCyclic shift to the left by ≦ 31). The addition operation unit 95 outputs the output from the bit string converter 81, the output from the cyclic shift operation unit 91, and the algorithm key G_nAddition value A_1nThe 32-bit addition operation is performed. As shown in the figure, if the input of the bit string converter 82 (that is, the output of the bit string converter 81) is V and the output value is W, the conversion of the bit string converter 82 can be expressed as follows.
[0042]
W = V + (V <<< S_1n) + A_1n
Here, the notation X <<<< Y represents data obtained by cyclically shifting X to the left by Y bits.
[0043]
The bit string converter 83 includes a cyclic shift calculation unit 92 and an addition calculation unit 96. The cyclic shift operation unit 92 outputs the output from the bit string converter 82 to the algorithm key G_nShift value S_2n(1 ≦ S_2nCyclic shift to the left by ≦ 31). The addition calculation unit 96 outputs the output from the bit string converter 82, the output from the cyclic shift calculation unit 92, and the algorithm key G_nAddition value A_2nThe 32-bit addition operation is performed. As shown in the figure, if the input of the bit string converter 83 (that is, the output of the bit string converter 82) is W and the output value is X, the conversion of the bit string converter 82 can be expressed as follows.
[0044]
X = W + (W <<< S_2n) + A_2n
The bit string converter 84 includes an exclusive OR unit 97, and calculates an exclusive OR of the output from the bit string converter 83 and the conversion key K2. As shown in the figure, if the input of the bit string converter 84 (that is, the output of the bit string converter 83) is X and the output value is Y, the conversion of the bit string converter 84 can be expressed as follows.
[0045]
Y = K2 (+) X
The bit string converter 85 includes a cyclic shift calculation unit 93 and an addition calculation unit 98. The cyclic shift operation unit 93 outputs the output from the bit string converter 84 to the algorithm key G_nShift value S_3n(1 ≦ S_3nCyclic shift to the left by ≦ 31). The addition operation unit 98 outputs the output from the bit string converter 84, the output from the cyclic shift operation unit 93, and the algorithm key G_nAddition value A_3nThe 32-bit addition operation is performed. As shown in the figure, if the input of the bit string converter 85 (that is, the output of the bit string converter 84) is Y and the output value is Z, the conversion of the bit string converter 82 can be expressed as follows.
[0046]
Z = Y + (Y <<< S_3n) + A_3n
As described above, the bit string conversion unit 61 performs bit string conversion by causing the five bit string converters 81 to 85 to act on data. The order in which the five bit string converters 81 to 85 operate on the data is not limited to that shown in FIG. In FIG. 5, data is applied to the data in the order of bit string converter 81 → bit string converter 82 → bit string converter 83 → bit string converter 84 → bit string converter 85. For example, bit string converter 84 → bit string converter The data may be applied to the data in the order of 83 → bit string converter 81 → bit string converter 85 → bit string converter 82.
[0047]
Returning to FIG. 4, the exclusive OR operation unit 62 outputs the output from the bit string converter 83 and the substitution transposition conversion unit 21._n32-bit data R input to_n-1And the exclusive OR. Then, the result is converted to the next-stage substitution transposition conversion unit 21._{n + 1}32-bit data L to be input to_nOutput as. On the other hand, the substitution transposition conversion unit 21_n32-bit data L input to_n-1, The substitution transposition conversion unit 21 of the next stage_{n + 1}32-bit data R to be input to_nOutput as.
[0048]
Substitution transpose conversion unit 21_nThe conversions in can be summarized as follows:
[0049]
L_n= R_n-1(+) FG_n(K1, K2, L_n-1)
R_n= L_n-1
Here, the substitution transposition conversion unit 21_nAlgorithm key G set to (1 ≦ n ≦ N, where N is the number of rounds)_nWill be described.
[0050]
As described above with reference to FIG. 5, the algorithm key G_nIs an addition value A used for the addition calculation in the addition calculation units 95, 96, and 98._1n, A_2n, A_3n(32-bit data) and the shift value S used for the left cyclic shift calculation in the cyclic shift calculation units 91, 92, 93._1n, S_2n, S_3n(1 ≦ S_1n, S_2n, S_3n≦ 31). Of these, the shift value S_1n, S_2n, S_3nIn this embodiment, the following conditions are set.
[0051]
(1) Shift value S_1n, S_2n, S_3nAre all odd or S_1nAnd S_2nEither one of these is set to 2 and the remaining two are set to odd numbers. In addition, the continuous two-stage substitution transposition conversion unit 21_i, 21_{i + 1}In (1 ≦ i ≦ N−1), the corresponding shift values are set so as not to match. That is, S_1i≠ S_{1i + 1}, S_2i≠ S_{2i + 1}, S_3i≠ S_{3i + 1}Set to be.
[0052]
(2) L (2 ≦ L) continuous substitution transposing unit 21_i~ 21_{i + L-1}The shift value pattern to be set to the next consecutive L-stage substitution transpose conversion unit 21_{i + L}~ 21_{i + 2L-1}The shift value pattern is set so as not to match (1 ≦ i, i + 2L−1 ≦ N). For example, a continuous two-stage substitution transposition conversion unit 21_i, 21_{i + 1}If the pattern of the shift value to be set to BC is BC, the next consecutive two-stage substitution transposition conversion unit 21_{i + 2}, 21_{i + 3}So that the pattern of shift values to be set to BC does not become BC, that is, S_1i≠ S_{1i + 2}, S_{1i + 1}≠ S_{1i + 3}, S_2i≠ S_{2i + 2}, S_{2i + 1}≠ S_{2i + 3}, S_3i≠ S_{3i + 2}, S_{3i + 1}≠ S_{3i + 3}Set to be.
[0053]
The condition shown in the above (1) is found from the strength evaluation for the cryptanalysis by the differential cryptanalysis and the linear cryptanalysis performed by the present inventors.
[0054]
Here, differential cryptanalysis is a cryptanalysis proposed by Biham and Shamir in 1990 ((E. Biham, A. Shamir, Differential Cryptanalysis of DES-like Cryptosystems (Extended Abstract), Advances in Cryptology, CRYPTO '90 proceedings, Lecture Notes in Computer Science Vol. 537, Springer-Verlag, 1990.), (E. Biham, A. Shamir, Differential Cryptanalysis of the Full 16-round DES, Advances in Cryptology, CRYPTO'92 proceedings, Lecture Notes in Computer Science Vol. 740, Springer-Verlag, 1992.)). When the probability that a plaintext / ciphertext pair having a specific difference is generated is high, a candidate key is narrowed down using the plaintext / ciphertext pair. For example, for a certain F function, a difference ΔY of output data generated with a high probability with respect to a certain input data difference ΔX is examined in advance, and then, for an F function with a fixed key K, It is checked whether the difference between the output data generated with respect to the input data having the difference of ΔX is biased toward ΔY. If the fixed key K is a true value, the output data should be ΔY with a high probability. Therefore, if the difference is biased to ΔY, the probability that the key K is a true key increases. Using this principle, key candidates are narrowed down.
[0055]
Mean differential probabilities have been proposed as a strict security measure for differential cryptanalysis (X. Lai, L. Massey and S. Murphy, Markov Cipher and Differential Cryptanalysis, EUROCRYPTO'91 proceedings, Lecture Notes in Computer Science Vol. 547, Springer-Verlag, 1991.). The probability that each difference pair occurs in the input / output data of the nonlinear function is calculated for all keys, and the difference pair having the highest occurrence probability is found among them. The probability that such a difference pair occurs is the average difference probability. The smaller the average difference probability, the higher the security for differential cryptanalysis. The average difference probability is defined as follows.
[0056]
[Expression 1]

[0057]
When evaluating the security against differential cryptanalysis, it is difficult to calculate the average differential probability of the entire data randomizing unit. Therefore, although the security is not guaranteed in a strict sense, the maximum differential characteristic probability is used as a necessary condition of security for differential cryptanalysis. For example, the average difference probability of the nonlinear function that is a part of the data randomizing unit is calculated. Next, assuming that the average difference probabilities of each nonlinear function are all independent, the probability of the entire data randomizing unit is calculated using these average difference probabilities. Such a conditional probability becomes the maximum difference characteristic probability. The actual calculation method depends on the structure of the data randomizing unit. Note that the number of plaintext / ciphertext pairs necessary for differential decryption can be obtained as the reciprocal of the average differential probability.
[0058]
On the other hand, linear cryptanalysis is a cryptanalysis proposed by Matsui in 1993 ((M. Matsui, Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology, EUROCRYPTO'93 proceedings, Lecture Notes in Computer Science Vol. 765 , Springer-Verlag, 1993.), (M. Matsui, The First Experimental Cryptanalysis of the Data Encryption Standard, Advances in Cryptology, CRYPTO'94 proceedings, Lecture Note in Computer Science Vol. 839, Springer-Verlag, 1994.). When the probability of having a linear relationship between the plaintext and the ciphertext bit value is away from 1/2, this is a method of using the linear relationship to estimate a candidate key and decrypting it. When doing so, it is necessary to obtain a large number of arbitrary plaintext / ciphertext pairs.
[0059]
Mean linear probability has been proposed as a measure of security against linear cryptanalysis (K. Nyberg, Linear Approximation of Block Ciphers, Advances in Cryptology,-CRYPTO'94, Lecture Notes in Computer Science Vol. 950, Springer-Verlag, 1995.). The probability of having a linear relationship between the bits of the input / output data of the nonlinear function is calculated for all the keys, and the linear relationship having the highest occurrence probability is found among them. The probability that such a linear relationship occurs is the average linear probability. The smaller the average linear probability, the higher the security for linear cryptanalysis. The mean linear probability is defined as:
[0060]
[Expression 2]

[0061]
When evaluating the security against linear cryptanalysis, it is difficult to evaluate the average linear probability of the entire data randomizing unit as in the case of differential cryptanalysis. Therefore, as in the case of differential cryptanalysis, an index called the maximum linear characteristic probability is used. For example, first, the average linear probability of the nonlinear function that is a part of the data randomizing unit is calculated. Next, assuming that each nonlinear function is independent, the probability of the entire data randomizing unit is calculated based on these average linear probabilities. The actual calculation method depends on the structure of the data randomizing unit. Note that the number of plaintext / ciphertext pairs actually required for decryption by linear cryptanalysis is obtained as the reciprocal of the linear probability.
[0062]
The inventors of the present invention have each substitution / translation conversion unit 21 so as to satisfy the condition (1)._nAlgorithm key G_nIt has been found that the strength against attacks by differential cryptanalysis and linear cryptanalysis can be improved without increasing the number of stages of the substitution transposition conversion unit, that is, the number of rounds N. The reason will be described later.
[0063]
Further, the condition shown in (2) above is for combating a slide attack. The slide attack is a selected plaintext attack method that does not depend on the number of stages (number of rounds). Decryption by slide attack is described in detail in a paper “Slide Attacks” published by Fry 99 and Fast Software Encription work shop 1999 by Biryukov and Wagner.
[0064]
Furthermore, in the present embodiment, the algorithm key G is set so as to satisfy the following conditions:_nIs set.
[0065]
Now, the conversion keys K1 and K2 generated by the key conversion unit 23 are fixed, and all the substitution transposition conversion units 21 are used.₁~ 21_N2 or more substitution transposition conversion unit 21 consecutive from_i~ 21_{i + j}Consider a case where (1 ≦ i, i + j ≦ N) is arbitrarily selected and the same data is converted as an input value. In this case, the conversion result is the selected substitution transposition conversion unit 21._i~ 21_{i + j}Algorithm key G used in_i~ G_{i + j}Determined by. In the present embodiment, it is assumed that only algorithm keys that can obtain different conversion results are used in all the combinations described above. By doing in this way, it is possible to prevent periodicity from appearing in the cipher conversion that repeatedly uses the substitution transposition conversion unit, thereby improving the strength of the cipher.
[0066]
Note that when the encryption unit 11 is implemented in hardware by an integrated logic IC such as an ASIC or FPGA, the shift value S_1n, S_2n, S_3nAs a combination of all algorithm keys G₁~ G_NUsing a combination of three common values, and adding value A_1n, A_2n, A_3nAs a combination of all algorithm keys G₁~ G_NA combination of three common values may be used. By doing so, it is possible to prevent the hardware configuration from becoming complicated.
[0067]
Next, the decoding unit 31 of the data receiver 2 will be described.
[0068]
FIG. 6 is a schematic configuration diagram of the decoding unit 31 shown in FIG. The decrypting unit 31 decrypts the ciphertext that has been cipher-converted by using the encrypting unit 11 of FIG. 2 described above into the original plaintext. Each component of the decryption unit 31 shown in FIG. 6 may be realized by hardware using an integrated logic IC such as an ASIC or FPGA, as in the encryption unit 11 shown in FIG. It may be realized in software by a computer such as
[0069]
The key conversion unit 43 performs the same processing as the key conversion unit 23 of the encryption unit 11 illustrated in FIG. That is, a 40-bit or 64-bit encryption / decryption key and 1-bit key length data are received from the key sharing unit 32, and 32-bit conversion keys K1 and K2 are generated based on these. Here, the value of the key length data is 0 if the key is 40 bits, and 1 if the key is 64 bits.
[0070]
The decoding conversion unit 40 inputs the two 32-bit data L_i, R_iThe conversion keys K1 and K2 are applied to (0 ≦ i ≦ N) to perform the substitution transposition conversion process, and the result is input to the two 32-bit data L to be input to the next stage._i-1, R_i-1N-stage substitution transposition conversion unit 41 that outputs as₁~ 41_NAnd the 64-bit ciphertext received from the data transmitter 1 via the communication processing unit 34 is converted into the upper 32 bit data L_NAnd lower 32 bits data R_N, And the first stage substitution transpose conversion unit 41_NThe dividing unit 45a that is input to the subordinate and the substitution transposition conversion unit 41 at the last stage₁Two 32-bit data L output from₀, R₀The data L₀Is the upper bit data, data R₀Are combined as lower-order bit data, and a combining unit 45b for obtaining 64-bit plaintext is included. Here, the substitution transposition conversion unit 41_nThe conversion algorithm of (1 ≦ n ≦ N) is an algorithm key G held in the algorithm key holding unit 44._nDetermined by. The algorithm key holding unit 44 is an algorithm key G held by the algorithm key holding unit 24 of the encryption unit 11 shown in FIG.₁~ G_NHolds the same algorithm key.
[0071]
When the 64-bit ciphertext received from the data transmitter 1 via the communication processing unit 34 is input to the decryption conversion unit 40 configured as described above, the upper 32 bit data L is divided by the division unit 45a._N(Substitution transposition conversion unit 21 at the last stage shown in FIG._N32-bit data L output from_NAnd lower 32-bit data R_N(Substitution transposition conversion unit 21 at the last stage shown in FIG._N32-bit data R output from_NAnd the transpose conversion unit 41._NIs input. Therefore, the first encryption conversion is performed using the conversion keys K1 and K2. Subsequently, the substitution transposition conversion unit 41_N32-bit data L obtained as a result of cryptographic conversion_N-1And 32-bit data R_N-1Is the substitution transposition conversion unit 41 in the next stage._N-1Then, the second encryption conversion is performed using the conversion keys K1 and K2. Substitution transpose conversion unit 41_N-132-bit data L obtained as a result of cryptographic conversion_N-2And 32-bit data R_N-2Is the substitution transposition conversion unit 41 of the next stage._ThreeThe same processing is performed there. The cipher conversion as described above is repeated N times, and the last-stage transliteration conversion unit 41₁32-bit data L obtained as a result of cryptographic conversion₀And 32-bit data R₀Are coupled by the coupling unit 45b to obtain the original plaintext. Hereinafter, the total repetition number N of decryption conversion is called the number of rounds as in the case of encryption conversion.
[0072]
FIG. 7 shows the substitution transposition conversion unit 41 shown in FIG._nIt is a schematic block diagram of (1 <= n <= N). Here, the substitution transposition conversion unit 21 of the encryption unit 11 shown in FIG._nThose having the same functions are denoted by the same reference numerals.
[0073]
As shown in the figure, the substitution transposition conversion unit 41_nIs composed of a bit string conversion unit 61 and an exclusive OR operation unit 62, and the input 32-bit data L_nAnd 32-bit data R_nIs converted to 32-bit data L using the conversion keys K1 and K2._n-1And 32-bit data R_n-1Convert to
[0074]
Substitution transpose conversion unit 41_nFirst, the input 32-bit data L_n-1Is input to the bit string converter 61. The bit string conversion unit 61 uses the algorithm key G_nThe input 32-bit data R using the conversion keys K1 and K2 in accordance with the conversion algorithm determined by_nAdd bit string conversion processing to.
[0075]
The exclusive OR operation unit 62 outputs the output from the bit string conversion unit 61 and the substitution transposition conversion unit 41._n32-bit data L input to_nAnd the exclusive OR. Then, the result is converted to the next-stage transliteration conversion unit 41._n-132-bit data R to be input to_n-1Output as. On the other hand, the substitution transposition conversion unit 41_n32-bit data R input to_n, The substitution transposition conversion unit 41 of the next stage_n-132-bit data L to be input to_n-1Output as.
[0076]
Substitution transpose conversion unit 41_nThe conversions in can be summarized as follows:
[0077]
R_n-1= L_n(+) FG_n(K1, K2, R_n)
L_n-1= R_n
This conversion is performed by using the substitution transposition conversion unit 41 of the encryption conversion unit 20 described above with reference to FIGS._nIt corresponds to the inverse transformation of the transformation in.
[0078]
As shown in FIG._n(1 ≦ n ≦ N) is the first-stage substitution transposition conversion unit 41_NAlgorithm key G set to_NIs the transliteration conversion unit 21 at the last stage of the encryption conversion unit 20 shown in FIG._NAlgorithm key G set to_N, And the last stage substitution transpose conversion unit 41₁Algorithm key G set to₁Is the substitution transposition conversion unit 21 in the first stage of the cryptographic conversion unit 20 shown in FIG.₁Algorithm key G set to₁So as to match with the substitution transposition conversion unit 41 of the decoding conversion unit 40₁~ 41_NAnd the transliteration conversion unit 21 of the encryption conversion unit 20₁~ 21_NAre set in the reverse order of the order of the steps.
[0079]
Therefore, if the decryption unit 31 shares the same encryption / decryption key with the encryption unit 11, the data encrypted by the encryption unit 11 can be decrypted.
[0080]
The embodiment of the present invention has been described above.
[0081]
In the present embodiment, as described above, the ciphertext transmitted by the data transmitter 1 is data having the same encryption / decryption key and algorithm key as the encryption / decryption key and algorithm key used by the data transmitter 1. Only the receiver 2 can decode. Since the algorithm key is also used as the secret information in addition to the encryption / decryption key, it is possible to make it more difficult for a third party to decipher the ciphertext flowing on the communication path.
[0082]
In the present embodiment, as described above, the algorithm key G_nShift value S of (1 ≦ n ≦ N)_1n, S_2n, S_3nAll are odd or S_1nAnd S_2nOne of these is set to 2 and the remaining two are set to odd values. By doing in this way, the intensity | strength with respect to the attack by a differential cryptanalysis method and a linear cryptanalysis can be improved, without increasing the stage number of the substitution transposition conversion part, ie, the number N of rounds.
[0083]
The present inventors conducted a strength evaluation experiment for cryptanalysis by differential cryptanalysis and linear cryptanalysis as follows.
[0084]
1. Strength evaluation for cryptanalysis by differential cryptanalysis
(1) Preparation
In the bit string converter 61 shown in FIG. 5, the conversion key K1 = K2 = 0, the added value A_1n= 1, A_2n= A_3nA conversion obtained when = 0 is defined as an F function in which an input difference is ΔX and an output difference is ΔY, and a difference probability dp (ΔX → ΔY) of the F function is defined as follows.
[0085]
dp (ΔX → ΔY) = prob {F (U (+) ΔX) (+) F (U) = ΔY}
Here, prob {A = B} means the probability that A = B (number of appearances / number of samples where A = B).
[0086]
An evaluation pattern shown in FIG. 8A was prepared as an evaluation pattern for obtaining the difference probability. Here, FIG. 8A shows an evaluation pattern of a two-stage difference difference type, and the function F at the first stage.₁Is the input difference ΔX = 0 and the output difference ΔY = 0, the second stage function F₂Is the input difference ΔX = Δa and the output difference ΔY = 0. This evaluation pattern is used because the second-stage function F in the evaluation pattern of the difference two-stage repetition type is used.₂Differential probability of
dp (Δa → 0) = prob {F₂(U (+) Δa) (+) F (U) = 0}
Is the largest.
[0087]
(2) Evaluation when the bit width of the input U of the function F is 16 bits or less
The bit width of the input U of the function F (that is, the bit width of the data processed by the function F) is 2^e(E = 2, 3, 4) and the shift value S_1n, S_2n, S_3nAll combinations (however, the input U has a bit width of 2)^eTherefore, the shift value S_1n, S_2n, S_3n1-2^eThe second stage function F of the difference two-stage iterative evaluation pattern.₂Differential probability of
dp (Δa → 0) = prob {F₂(U (+) Δa) (+) F (U) = 0}
Evaluated. Set bit width of input U of function F to 2^FourThe evaluation results when = 16 are shown in FIGS. In FIG. 9, the shift value S_1n, S_2n, S_3nAssuming that the greatest common divisors of each and the bit width 16 of the input U are a, b, and c, respectively, the maximum value max (a, b, c) of a, b, and c is 8, 4, 2, or 1 The values are shown in order from the largest value of max (a, b, c). In each of max (a, b, c), a shift value (S) that gives the maximum difference probability among the input differences leading to the output difference 0_1n, S_2n, S_3n) In descending order of the maximum difference probability. FIG. 10 shows the shift value (S) among the results in the case of max (a, b, c) = 2 shown in FIG._1n, S_2n, S_3n) Is an extracted result when (2, odd, odd) or (odd, 2, odd).
[0088]
As shown in FIG. 9, the smaller the max (a, b, c), the lower the probability of approximation. Therefore, when max (a, b, c) is 1, that is, the shift value S_1n, S_2n, S_3nWhen the greatest common divisor with the bit width of each input U is 1, in other words, the shift value S_1n, S_2n, S_3nIf all are odd, the best differential probability is 2^-4.75~ 2^-6.68It was found that the resistance to attacks by differential cryptanalysis could be maximized. Even when max (a, b, c) is 2, as shown in FIG._1n, S_2n, S_3n) Is (2, odd, odd) or (odd, 2, odd), the best differential probability is 2^-3.71~ 2^-4.79It was found that the degree and the max (a, b, c) are lower than the other cases in the case of 2, and the resistance to the attack by the differential cryptanalysis can be increased. Here, the result is displayed only when the bit width of the input U is 16, but the shift value (S) is also obtained when the bit width of the input U is 4 or 8._1n, S_2n, S_3n) As an arbitrary value (however, 1 ≦ S_1n, S_2n, S_3nThe result of picking up and evaluating <bit width of input U) also showed a similar tendency. Therefore, the present inventors have used the substitution transposition conversion unit 21 used in the above embodiment._n, 41_nKey G set in the bit string converter 61 of_nShift value (S_1n, S_2n, S_3n) As (odd number, odd number, odd number), (2, odd number, odd number) or (odd number 2, odd number), it is found that the strength against attacks by differential cryptanalysis can be improved. It was.
[0089]
(3) Evaluation when the bit width of the input U of the function F is 32 bits
Based on the result of (2) above, the substitution transposition conversion unit 21 used in the above embodiment._n, 41_nKey G set in the bit string converter 61 of_nShift value (S_1n, S_2n, S_3n) To be (2, odd, odd) or (odd, 2, odd), and the bit width of the input U is 2^Five= Second-stage function F of the difference two-stage repetitive evaluation pattern when = 32₂Differential probability of
dp (Δa → 0) = prob {F₂(U (+) Δa) (+) F (U) = 0}
Evaluated. The results are shown in FIG. As can be seen from this result, the shift value (S_1n, S_2n, S_3n) Is (2, odd, odd) or (odd, 2, odd), the best difference probability is 2^-7.69~ 2^-8.70It was about.
[0090]
2. Strength evaluation for cryptanalysis by linear cryptanalysis
(1) Preparation
In the bit string converter 61 shown in FIG. 5, the conversion key K1 = K2 = 0, the added value A_1n= 1, A_2n= A_3nThe transformation obtained when = 0 is defined as the F function given by ΓX as the input mask and ΓY as the output mask, and the linear approximation probability lp (ΓX → ΓY) of the F function is defined as follows.
[0091]
lp (ΓX → ΓY) = | 2prob {F (U) ・ ΓY = X ・ ΓX} −1 |²
Here, A · B examines the number of bits having the bit value “1” at the same bit position as the bit position of the bit “1” in the bit string of B in A, and sets mod2 of the number of bits. It means to take.
[0092]
An evaluation pattern shown in FIG. 8B was prepared as an evaluation pattern for obtaining a linear approximation probability. Here, FIG. 8B is a linear two-stage repetitive evaluation pattern, and the first-stage function F₁Is input mask ΓX = 0 and output mask ΓY = 0, second stage function F₂Is an input mask ΓX = 0 and an output mask ΓY = Γa. This evaluation pattern is used because the function F at the second stage in the linear two-stage repetition type evaluation pattern is used.₂Linear approximation probability of
lp (0 → Γa) = | 2prob {F₂(U) ・ Γa = U ・ 0} −1 |²
Is the largest.
[0093]
(2) Evaluation when the bit width of the input U of the function F is 16 bits or less
The bit width of the input U of the function F (that is, the bit width of the data processed by the function F) is 2^e(E = 2, 3, 4) and the shift value S_1n, S_2n, S_3nAll combinations (however, the input U has a bit width of 2)^eTherefore, the shift value S_1n, S_2n, S_3n1-2^e-1For the second-stage function F of the linear two-stage iterative evaluation pattern.₂Linear approximation probability of
lp (0 → Γa) = | 2prob {F₂(U) ・ Γa = U ・ 0} −1 |²
Evaluated. 12 and 13, the bit width of the input U of the function F is 2^FourThe evaluation result when = 16 is shown. In FIG. 12, the shift value S is the same as in FIG._1n, S_2n, S_3nFor each, if the greatest common divisor with the bit width 16 of the input U is a, b, c respectively, the maximum value max (a, b, c) of a, b, c is any of 8, 4, 2, 1 Focusing on taking these values, the values are shown in descending order of the value of max (a, b, c). In each of max (a, b, c), a shift value (S) that gives the maximum linear approximation probability among the output masks that become the input mask 0._1n, S_2n, S_3n) In the descending order of the maximum linear approximation probability. FIG. 12 shows the shift value (S) among the results in the case of max (a, b, c) = 2 shown in FIG._1n, S_2n, S_3n) Is an extracted result when (2, odd, odd) or (odd, 2, odd).
[0094]
As shown in FIG. 12, the smaller the max (a, b, c), the lower the probability of approximation. Therefore, when max (a, b, c) is 1, that is, the shift value S_1n, S_2n, S_3nWhen the greatest common divisor with the bit width of each input U is 1, in other words, the shift value S_1n, S_2n, S_3nWhen all are odd, the best linear approximation probability is 2^-5.24~ 2^-7.18It was found that the resistance to attacks by linear cryptanalysis could be maximized. Even when max (a, b, c) is 2, as shown in FIG._1n, S_2n, S_3n) Is (2, odd, odd) or (odd, 2, odd), the best linear approximation probability is 2.^-3.44~ 2^-5.58It was found that the degree and the max (a, b, c) are lower than the other cases in the case of 2, and the resistance to the attack by the linear cryptanalysis can be increased. Here, the result is displayed only when the bit width of the input U is 16, but the shift value (S) is also obtained when the bit width of the input U is 4 or 8._1n, S_2n, S_3n) As an arbitrary value (however, 1 ≦ S_1n, S_2n, S_3nThe result of picking up and evaluating <bit width of input U) also showed a similar tendency. Therefore, the present inventors have used the substitution transposition conversion unit 21 used in the above embodiment._n, 41_nKey G set in the bit string converter 61 of_nShift value (S_1n, S_2n, S_3n) As (Odd, Odd, Odd), (2, Odd, Odd) or (Odd, 2, Odd). As in the case, it has been found that it can be improved.
[0095]
(3) Evaluation when the bit width of the input U of the function F is 32 bits
Based on the result of (2) above, the substitution transposition conversion unit 21 used in the above embodiment._n, 41_nKey G set in the bit string converter 61 of_nShift value (S_1n, S_2n, S_3n) To be (2, odd, odd) or (odd, 2, odd), and the bit width of the input U is 2^FiveFunction F in the second stage of the linear two-stage iterative evaluation pattern when = 32₂Differential probability of
lp (0 → Γa) = | 2prob {F₂(U) ・ Γa = U ・ 0} −1 |²
Evaluated. The results are shown in FIG. As can be seen from this result, the shift value (S_1n, S_2n, S_3n) Is (2, odd, odd) or (odd, 2, odd), the best linear approximation probability is 2^-7.36~ 2^-10.78It was about.
[0096]
3. Comprehensive evaluation
Based on the results in 1 and 2 above, the present inventors have used the substitution transposition conversion unit 21 used in the above embodiment._n, 41_nKey G set in the bit string converter 61 of_nShift value (S_1n, S_2n, S_3n) To be (2, odd, odd) or (odd, 2, odd), and the number of evaluation pattern stages for obtaining the difference and linear approximation probability shown in FIG. 8 is increased to 18 and 21 stages. The probability in the case of letting it be estimated. The number of stages (18 stages, 21 stages) is a value determined in consideration of the number of rounds used in the actual encryption / decryption process. The estimation is based on the following assumptions.
[0097]
(1) Differential decryption method: When the number of stages of the evaluation pattern is 2r, this best differential probability is dp (Δa (→ 0)^rGiven in.
[0098]
(2) Linear decoding method: When the number of stages of the evaluation pattern is 2r, this best differential probability is lp (0 (0 → Γa)^rGiven in.
[0099]
The results are shown in FIGS. As can be seen from these results, the substitution transposition conversion unit 21 used in the above embodiment._n, 41_nKey G set in the bit string converter 61 of_nShift value (S_1n, S_2n, S_3n) As (2, odd, odd) or (odd, 2, odd), the bit width of the input U is 2^Five= 32, the probability is 2^-70Before and after. Therefore, it is possible to construct an encryption algorithm having sufficient computational strength against attacks by differential cryptanalysis and linear cryptanalysis.
[0100]
In the above-described embodiment, as the encryption conversion unit 20 and the decryption conversion unit 40, as shown in FIGS.₁~ 21_N, 41₁~ 41_NThe thing which has was demonstrated. However, the present invention is not limited to this, and one substitution / translation conversion unit may be configured to execute substitution / transposition conversion processing N times for the number of rounds while changing the algorithm key.
[0101]
In the above embodiment, 40 bits or 64 bits are used as the encryption / decryption key shared between the data transmitter 1 and the data receiver 2, and the key length is indicated as 40 bits or 64 bits. The case where 1-bit data is used as the key length data has been described. However, the present invention is not limited to this.
[0102]
For example, the encryption key may be changed from 40 bits to 128 bits, and the key length data may be 7 bits so that these can be selected. In this case, the encryption / decryption stored in the register 26 according to the value of the input key length data so that the key conversion units 23 and 43 can generate two conversion keys K1 and K2 having a 32-bit length. The selector may be increased so that the bit string position extracted from the key for use can be changed. Also, the encryption / decryption key is set to 64 or more, four conversion keys having a 32-bit length are generated, and the N substitution transpose conversion units are divided into two sets and supplied in pairs. Good.
[0103]
Alternatively, the substitution transposition conversion unit 21 used in the cryptographic conversion_nA plurality of conversion keys may be generated from the encryption / decryption key using a plurality of (1 ≦ n ≦ N).
[0104]
FIG. 17 is a diagram illustrating a modification of the key conversion units 23 and 43 of the data transmitter 1 and the data receiver 2. In this example, a 256-bit system key composed of eight conversion keys is generated from a 64-bit encryption / decryption key.
[0105]
As shown in the figure, the key conversion units 23a and 43a include the extended key holding unit 100 and the 8-stage substitution transposition conversion unit 21.₁~ 21₈Have
[0106]
The extended key holding unit 100 holds a 256-bit extended key shared between the data transmitter 1 and the data receiver 2 by the key sharing units 12 and 32. In FIG. 1, the 256-bit extended key may be received and held by the key information holding unit 15 of the data transmitter 1 from the key management organization 3 instead of the key length information. In this case, in the data transmitter 1, the key information holding unit 15 may function as the extended key holding unit 100. The key expansion holding unit 100 converts the 256-bit extended key held by itself into eight 32-bit extended keys KE.₁~ KE₈, And as shown in FIG.₁~ 21₈In
[0107]
When the encryption / decryption key (64 bits) is input to the key conversion units 23a and 43a having the above configuration, the upper 32 bits data L₀And lower 32 bits data R₀Into a transliteration conversion unit 21₁Is input. Therefore, the extended key KE₁, KE₂Is used for the first conversion, and the resulting 32-bit data L₁And 32-bit data R₁Is the substitution transposition conversion unit 21 in the next stage.₂Is input. Also, 32-bit data L₁Is extracted as a conversion key K1. Next, the substitution transposition conversion unit 21₂The extended key KE_Three, KE_FourIs used for the second conversion, and the resulting 32-bit data L₂And 32-bit data R₂Is the substitution transposition conversion unit 21 in the next stage._ThreeIs input. Also, 32-bit data L₂Is extracted as a conversion key K2. The conversion as described above is sequentially performed, and the substitution transposition conversion unit 21 in the final stage.₈32-bit data L obtained as a result of conversion in₈As a conversion key K8. As a result, a 256-bit system key composed of eight 32-bit conversion keys K1 to K8 is generated.
[0108]
18 is a diagram showing a modification in the case where the key conversion unit 23a shown in FIG. 17 is used in place of the key conversion unit 23 in the encryption unit 11 shown in FIG.
[0109]
In FIG. 18, when plaintext (64 bits) is input to the encryption conversion unit 20, the upper 32 bit data L is generated by the dividing unit 25 a.₀And lower 32 bits data R₀Into a transliteration conversion unit 21₁Is input. Therefore, the first conversion is performed using the conversion keys K1 and K2, and the resulting 32-bit data L₁And 32-bit data R₁Is the substitution transposition conversion unit 21 in the next stage.₂Is input. Such conversion is sequentially performed, and the substitution transposition conversion unit 21._FourThe fourth conversion using the conversion keys K7 and K8 is performed, and the resulting 32-bit data L_FourAnd 32-bit data R_FiveIs the substitution transposition conversion unit 21 in the next stage._FiveIs input, the conversion keys to be used are K1 and K2, and the conversion is repeated as described above.
[0110]
FIG. 19 is a diagram illustrating a modification of the decryption unit 31 illustrated in FIG. 6 in which the key conversion unit 43 a illustrated in FIG. 17 is used instead of the key conversion unit 43.
[0111]
In FIG. 19, when the ciphertext (64 bits) is input to the decryption / conversion unit 40, the division unit 45a causes the upper 32-bit data L_NAnd lower 32 bits data R_NInto a transliteration conversion unit 41._NIs input. Therefore, the first conversion is performed using the conversion keys K8 and K7, and the resulting 32-bit data L_N-1And 32-bit data R_N-1Is the substitution transposition conversion unit 41 in the next stage._N-1Is input. Such conversion is sequentially performed, and the substitution transposition conversion unit 41._N-3The fourth conversion using the conversion keys K2 and K1 is performed, and the resulting 32-bit data L_N-4And 32-bit data R_N-4Is the substitution transposition conversion unit 41 in the next stage._N-4Is input, the conversion keys to be used are K8 and K7, and the conversion is repeated as described above. This conversion corresponds to the reverse conversion of the cryptographic conversion described with reference to FIG.
[0112]
In the above embodiment, as the bit string converters 82, 83, 85 of the bit string converter 61 shown in FIG. 5, the cyclic shift calculators 91, 92, 93 and the addition calculators 95, 96, 98 are respectively used. The case where what is used was demonstrated. However, the present invention is not limited to this, and a multiplication operation unit may be provided in the preceding stage of each of the addition operation units 95, 96, and 98.
[0113]
FIG. 20 is a diagram illustrating a modification of the bit string conversion unit 61 used in the present embodiment. The bit string conversion unit 61a shown in this figure is different from the bit string conversion unit 61 shown in FIG. 5 in that multiplication operation units 95a, 96a, and 98a are provided in front of the addition operation units 95, 96, and 98, respectively.
[0114]
For each of the bit string converters 82, 83, and 85 of the bit string converter 61 shown in FIG.
Y = X + (X <<< S_in) + A_in
However, i = 1,2,3, 1 ≦ n ≦ number of rounds N
It becomes.
[0115]
On the other hand, for each of the bit string converters 82, 83, and 85 of the bit string converter 61a shown in FIG.
Y = B_inX + (X <<< S_in) + A_in
However, i = 1,2,3, 1 ≦ n ≦ number of rounds N
It becomes.
[0116]
Here, when the processing bit width (bit length of input / output X and Y) is m, 2^Sin+ B_inAnd 2^mB-1 so that −1 is a relatively prime value._inAnd S_inIs set, the functions of the bit string converters 82, 83, and 85 of the bit string converter 61a can be brought close to bijective functions. As a result, the strength of attack by differential cryptanalysis and linear cryptanalysis can be further enhanced. Note that the multiplication value B in the multiplication operation units 95a, 96a, and 98a._1n, B_2n, B_3nIs the shift value S_1n, S_2n, S_3nAnd addition value A_1n, A_2n, A_3nSimilarly to the above, the algorithm key holding units 24 and 44 may hold the parameters included in the algorithm key Gn.
[0117]
Next, an application example of the encryption communication system of the present embodiment described above to the automatic fee collection system will be described.
[0118]
Here, the automatic toll collection system means that when a car passes through a toll road, the roadside machine installed on the toll road allows the toll from the driver's IC card by electronic payment without stopping the car. It is a collecting system. The automatic toll collection system has various expectations such as the elimination of traffic congestion at toll gates on toll roads and the improvement of convenience by electronic payment using IC cards.
[0119]
FIG. 21 shows a schematic configuration of the automatic fee collection system.
[0120]
As shown in the figure, the automatic fee collection system includes an in-vehicle device 202 mounted on an automobile 200, an IC card 203, and a roadside device 201.
[0121]
The in-vehicle device 202 is configured so that the IC card 203 can be mounted. The IC card 203 is attached to the in-vehicle device 202 during driving by a driver of the automobile 200, for example.
[0122]
The roadside machine 201 is installed at a toll gate on a toll road, for example, and has a function of collecting a toll when the automobile 200 passes.
[0123]
The IC card 203 stores in advance contract information for the automatic fee collection system (information on the owner of the IC card and information on the settlement method (for example, whether to use credit settlement or cash settlement using electronic money)). When the automobile 200 passes through the roadside machine 201, the contract information is transferred to the roadside machine 201 by wireless communication via the in-vehicle machine 202 in which the IC card 203 is inserted. Receive information and payment information.
[0124]
In order to perform these processes safely and accurately, it is necessary to verify the validity of contract information, route information and payment information, and to prevent unauthorized tampering and wiretapping. Therefore, between the IC card 203 and the vehicle-mounted device 202, and between the vehicle-mounted device 202 and the roadside device 201, the other party authentication process for recognizing the communication partner as valid and the encryption / decryption of the exchange data Therefore, it is necessary to perform a process for sharing a key used for encryption and a process for encrypted communication using the shared key. The encryption / decryption process in the encryption communication system described in the above embodiment can be applied to the partner authentication process, the key sharing process, and the encryption communication.
[0125]
In order to realize the above processing, the in-vehicle device 202, the IC card 203, and the roadside device 201 hold in advance the common algorithm key and license key issued by the key management organization 204 as secret information. deep. For example, it is embedded in each interior during manufacture.
[0126]
Here, details of the algorithm key and details of encryption conversion and decryption conversion determined by the algorithm key are as described above.
[0127]
The license key is used for correctly performing the partner authentication process and the key sharing process. For example, consider a case where the in-vehicle device 202 confirms that the IC card 203 is a valid device in order for the IC card 203 and the in-vehicle device 202 to communicate. For this purpose, the IC card 203 only has to prove to the in-vehicle device 202 that the license key held by itself is correct. Here, since the license key is secret information, the IC card 203 must prove to the in-vehicle device 202 that it is correct without revealing its own license key. This proof can be realized by using a cryptographic communication technique. For example, a technique using a symmetric key cryptosystem is described in ISO 9798-2, which is an international standard for security mechanisms. As a specific example of this symmetric key encryption method, the encryption / decryption processing in the encryption communication system described in the above embodiment can be applied.
[0128]
Next, the components of the roadside device 201, the vehicle-mounted device 202, and the IC card 203 shown in FIG. 21 will be described.
[0129]
The roadside device 201 includes a wireless communication unit 232, an encryption / decryption unit 230, a partner authentication / key sharing processing unit 233, a data holding unit 234, and a main control unit 235.
[0130]
The in-vehicle device 202 includes a wireless communication unit 212, an encryption / decryption unit 210, an IC card communication unit 211, a partner authentication / key sharing processing unit 213, a data holding unit 214, and a main control unit 215. Have.
[0131]
The IC card 203 includes an IC card communication unit 221, an encryption / decryption unit 220, a partner authentication / key sharing processing unit 223, a data holding unit 224, and a main control unit 225.
[0132]
Here, the encryption / decryption units 210, 220, and 230 include both the encryption unit 11 and the decryption unit 31 (see FIG. 1) of the cryptographic communication system described in the above embodiment, It is possible to perform encryption and decryption.
[0133]
The IC card communication units 211 and 221 are used to perform communication processing between the in-vehicle device 202 and the IC card 203, and the wireless communication units 212 and 232 are provided between the in-vehicle device 202 and the roadside device 201. Used to perform wireless communication processing.
[0134]
Further, the authentication / key sharing processing units 213, 223, and 233 perform partner authentication processing for recognizing that the communication partner is valid, and key sharing processing for data encryption / decryption.
[0135]
The authentication / key sharing processing unit 213 uses the encryption conversion function and the decryption conversion function provided by the encryption / decryption unit 210 to perform partner authentication processing and key sharing processing using encryption communication technology. Similarly, the authentication / key sharing processing unit 223 performs encryption partner authentication processing and key sharing processing using encryption communication technology using the encryption conversion function and the decryption conversion function provided by the encryption / decryption unit 220, The authentication / key sharing processing unit 233 uses the encryption conversion function and the decryption conversion function provided by the encryption / decryption unit 230 to perform encryption partner authentication processing and key sharing processing using an encryption communication technique.
[0136]
The data holding units 214, 224, and 234 are used to hold algorithm keys and license keys acquired from the key management organization 204. It is also assumed that contract information, route information, and settlement information can be held.
[0137]
FIG. 22 is a diagram showing a communication flow of the automatic fee collection system shown in FIG.
[0138]
As shown in the figure, first, when the IC card 203 is mounted on the in-vehicle device 202, a partner authentication / key sharing process 240 is performed between the IC card 203 and the in-vehicle device 202. After the partner authentication / key sharing process 240 is successful, the IC card 203 performs encrypted communication 241 to transfer the contract information to the in-vehicle device 202. When the in-vehicle device 202 acquires the contract information of the IC card 203, the in-vehicle device 202 holds it secretly in the data holding unit 214 in the in-vehicle device 202.
[0139]
Next, when the vehicle 200 equipped with the vehicle-mounted device 202 passes through the roadside device 201, a partner authentication / key sharing process 250 is performed between the vehicle-mounted device 202 and the roadside device 201. Then, after the partner authentication / key sharing process 250 is successful, the in-vehicle device 202 is first obtained from the IC card 203 and kept secretly in the data holding unit 214 to transfer the contract information to the roadside device 201. Encrypted communication 251 is performed. When receiving the contract information from the in-vehicle device 202, the roadside device 201 collects a toll fee from the owner of the IC card 203 specified by the contract information and performs settlement according to the contract information. The encryption communication 251 transfers the payment information and route information (for example, information for specifying the roadside device 201 (the place on the toll road where the fee was collected) from which payment was made) from the roadside device 201 to the in-vehicle device 202. Also used for.
[0140]
Next, the in-vehicle device 202 performs encryption communication 261 in order to transfer settlement information and route information obtained from the roadside device 201 to the IC card 203.
[0141]
Here, the settlement of the road toll is performed between the IC card 203 and the roadside device 201. However, the IC card 203 and the roadside device 2011 cannot communicate with each other unless the vehicle-mounted device 202 is interposed. In this case, there is a possibility that the in-vehicle device 202 performs an illegal process and thus an illegal settlement is performed. In preparation for such a situation, the roadside device 201 needs to be able to identify the in-vehicle device 202 used for settlement with the IC card 203. For example, an identification number is assigned to the in-vehicle device 202, and the in-vehicle device 202 transfers the identification number of the in-vehicle device 202 to the IC card 203 in the partner authentication / key sharing process 240 with the IC card 203. The IC card 203 generates and returns a digital signature for both the identification number of the in-vehicle device 202 and the settlement history of the IC card 203. Then, the in-vehicle device 202 transfers its own identification number and the digital signature acquired from the IC card 203 to the roadside device 201 in the partner authentication / key sharing process 250. Thereafter, the roadside device 201 can identify when the in-vehicle device 202 is used by verifying the digital signature generated by the IC card 203.
[0142]
Further, in the encrypted communication 241, 251 and 261, it is necessary to prevent the encrypted data flowing on the communication path from being tampered with by a third party. In order to realize this, it is necessary to perform message authentication that can determine that the received message is valid. In order to perform message authentication, the sender and the receiver share a message authentication key in secret in advance. The message authentication key is shared, for example, in the partner authentication / key sharing process 250 shown in FIG. Then, the sender generates data called a message authentication code (MAC) from the message to be transferred and the message authentication key. The sender forwards the message authenticator along with the message to the recipient. The receiver verifies the received message authenticator using the message authentication key. This verification can determine whether the received message has been tampered with. Regarding message authentication, for example, a technique using a symmetric key cryptosystem is described in ISO9797, which is an international standard for security mechanisms. As a specific example of this symmetric key cryptosystem, the encryption / decryption processing in the cryptographic communication system described in the above embodiment can be applied.
[0143]
FIG. 23 shows a detailed flow of an example including message authentication in the encrypted communication 241 of FIG.
[0144]
As shown in the figure, first, the IC card 203 generates a message authenticator by a MAC generation process 261. Next, a combining process 262 for combining the forward message and the message authenticator is performed. Thereafter, encryption processing 263 is performed to encrypt data obtained by combining the transfer message and the message authenticator to generate encrypted data.
[0145]
On the other hand, when the in-vehicle device 202 receives the encrypted data from the IC card, the in-vehicle device 202 first performs a decryption process 264. Thereafter, the separation process 265 is performed to restore the transfer message and the message authenticator transferred by the IC card. Next, a MAC verification process 266 for verifying the restored message authenticator is performed to verify the validity of the received transfer message.
[0146]
This makes it possible to safely exchange data that should not be wiretapped or tampered with such as billing information and route information.
[0147]
By performing the above processing, the toll is charged to the IC card 203 and the charging information can be managed by the roadside device 201.
[0148]
【The invention's effect】
As described above, according to the present invention, it is possible to realize high-speed encryption / decryption conversion that is strong against cryptanalysis without increasing the number of conversion repetitions.
[Brief description of the drawings]
FIG. 1 is a schematic configuration diagram of a cryptographic communication system to which an embodiment of the present invention is applied.
FIG. 2 is a schematic configuration diagram of an encryption unit 11 shown in FIG.
FIG. 3 is a schematic configuration diagram of a key conversion unit 23 shown in FIG. 2;
4 is a substitution transposition conversion unit 21 shown in FIG._nIt is a schematic block diagram of (1 <= n <= round number N).
5 is a schematic configuration diagram of a bit string converter 61 shown in FIG. 4. FIG.
6 is a schematic configuration diagram of a decoding unit 31 shown in FIG.
7 is a substitution transposition conversion unit 41 shown in FIG._nIt is a schematic block diagram of (1 <= n <= round number N).
FIG. 8 is a diagram showing evaluation patterns used in strength evaluation experiments for cryptanalysis by differential cryptanalysis and linear cryptanalysis.
9 shows a conversion key K1 = K2 = 0 and an addition value A in the bit string conversion unit 61 shown in FIG._1n= 1, A_2n= A_3nIt is a figure which shows the evaluation result at the time of setting the conversion obtained when it is set to 0 to the function F, the bit width of the input U of the said function F being 16, and using the difference 2 step | paragraph repetitive evaluation pattern shown in FIG.
10 shows a conversion key K1 = K2 = 0 and an addition value A in the bit string conversion unit 61 shown in FIG._1n= 1, A_2n= A_3nThe figure which shows the evaluation result of the difference probability when the conversion obtained when = 0 is set to the function F, the bit width of the input U of the function F is 16, and the difference two-stage repetitive evaluation pattern shown in FIG. 8 is used It is.
11 shows a conversion key K1 = K2 = 0 and an addition value A in the bit string conversion unit 61 shown in FIG._1n= 1, A_2n= A_3nThe figure which shows the evaluation result of the difference probability when the conversion obtained when = 0 is set to the function F, the bit width of the input U of the function F is 32, and the difference two-stage repeated evaluation pattern shown in FIG. 8 is used It is.
12 shows a conversion key K1 = K2 = 0 and an addition value A in the bit string conversion unit 61 shown in FIG._1n= 1, A_2n= A_3n8 shows the evaluation result of the linear approximation probability when the conversion obtained in the case of = 0 is the function F, the bit width of the input U of the function F is 16, and the linear two-stage repetitive evaluation pattern shown in FIG. 8 is used. FIG.
FIG. 13 shows a conversion key K1 = K2 = 0 and an addition value A in the bit string conversion unit 61 shown in FIG._1n= 1, A_2n= A_3n8 shows the evaluation result of the linear approximation probability when the conversion obtained when = 0 is assumed to be the function F, the bit width of the input U of the function F is 16, and the linear two-stage repetitive evaluation pattern shown in FIG. 8 is used. FIG.
14 shows a conversion key K1 = K2 = 0 and an addition value A in the bit string conversion unit 61 shown in FIG._1n= 1, A_2n= A_3n8 shows the evaluation result of the linear approximation probability when the conversion obtained in the case of = 0 is the function F, the bit width of the input U of the function F is 32, and the linear two-stage repetitive evaluation pattern shown in FIG. 8 is used. FIG.
15 is a diagram showing estimated values of the difference probability and the linear approximation probability when the number of stages of the evaluation pattern for obtaining the difference and the linear approximation probability shown in FIG. 8 is increased to 18 stages and 21 stages.
16 is a diagram showing estimated values of the difference probability and the linear approximation probability when the number of stages of the evaluation pattern for obtaining the difference and the linear approximation probability shown in FIG. 8 is increased to 18 and 21. FIG.
17 is a diagram illustrating a modification of the key conversion units 23 and 43 of the data transmitter 1 and the data receiver 2 illustrated in FIG.
18 is a diagram showing a modification when the key conversion unit 23a shown in FIG. 17 is used in place of the key conversion unit 23 in the encryption unit 11 shown in FIG.
19 is a diagram showing a modification in the case where the key conversion unit 43a shown in FIG. 17 is used in place of the key conversion unit 43 in the decryption unit 31 shown in FIG.
20 is a diagram showing a modification of the bit string conversion unit 61 shown in FIG.
FIG. 21 is a schematic configuration diagram of an automatic fee collection system to which an encryption communication system according to an embodiment of the present invention is applied.
22 is a diagram showing a communication flow of the automatic fee collection system shown in FIG. 21. FIG.
23 is a diagram showing a detailed flow of an example including message authentication in the encrypted communication 241 of FIG.
[Explanation of symbols]
1 ... Data transmitter
2 ... Data receiver
3, 204 ... Key management organization
11, 11a: Encryption unit
12, 32 ... Key sharing part
13, 33 ... Data processing unit
14, 34 ... Communication processing unit
15 ... Key length information holding unit
20 ... encryption conversion part
21₁~ 21_N, 41₁~ 41_N... Substitution transpose converter
23, 23a, 43, 43a ... key conversion unit
24, 44 ... Algorithm key holding unit
25a, 45a ... division part
25b, 45b ... coupling part
26: Register
27. Multiplexer
28, 95, 96, 98 ... Addition calculation unit
31, 31a ... Decoding unit
40: Decoding conversion unit
61, 61a: Bit string converter
62, 94, 97 ... exclusive OR operation part
81-85 ... Bit string converter
91-93 ... cyclic shift operation part
95a, 96a, 98a ... Multiplication calculation unit
100: Extended key holding unit
200 ... car
201 ... roadside machine
202 ... In-vehicle device
203 ... IC card
210, 220, 230 ... encryption / decryption unit
211, 221 ... IC card communication section
212, 232 ... Wireless communication unit
213, 223, 233 ... Partner authentication / key sharing processing unit
214, 224, 234 ... Data holding unit
215, 225, 235 ... main control unit

Claims (13)

An encryption device that encrypts plaintext data using an encryption key,
The cryptographic process is performed by applying the encryption key to the input first and second data, and the result is output a plurality of times as the first and second data to be input next time. Cryptographic conversion means;
Dividing the plaintext data into two, and outputting the result as first and second data to be input to the first cryptographic operation processing of the cipher conversion means;
Combining the first and second data output from the cryptographic operation processing of the last round of the cryptographic conversion means, and the cryptographic combining means for outputting the result as encrypted data,
The cryptographic operation processing is
Cryptographic bit string conversion process for performing bit string conversion of input first data and Cryptographic exclusive logic for calculating an exclusive OR of output data of the encryption bit string conversion process and input second data A sum operation process,
The output data of the exclusive OR operation for encryption is set as the first data to be input next time, and the input first data is output as the second data to be input next time,
The encryption bit string conversion process includes:
A first exclusive OR operation process for calculating an exclusive OR of the input data and the first key data generated from the encryption key or a part thereof;
A first cyclic shift calculation process for performing a cyclic shift calculation process with a shift number S1 on the input data, and a first calculation for adding the input data and the output data of the first cyclic shift calculation process A first logical operation process comprising: an addition operation process;
A second cyclic shift calculation process for performing a cyclic shift calculation process with a shift number S2 on the input data, and a second calculation process for adding the input data and the output data of the second cyclic shift calculation process. A second logical operation process comprising:
A second exclusive OR operation process for calculating an exclusive OR of the input data and the second key data generated from the encryption key or a part thereof;
A third cyclic shift calculation process for performing a cyclic shift calculation process with a shift number S3 on the input data, and an addition calculation process of the input data and the output data of the third cryptographic cyclic shift calculation process are performed. A third addition operation process, and a third logical operation process including the third addition operation process in a predetermined order,
The shift numbers S1, S2 and S3 in the encryption bit string conversion process are all set to be odd numbers, or one of S1 and S2 is 2 and the remaining two are odd values, and A cryptographic apparatus, wherein the values of S1, S2 and S3 are set so as not to coincide with each other between the cryptographic computation processes executed successively. The encryption device according to claim 1,
The number of shifts S1, S2 and S3 in the cryptographic bit string conversion process is the pattern of the values of S1, S2 and S3 set in N (N is 2 or more) of the cryptographic operation processes executed continuously. It is set so as not to match the pattern of values of S1, S2 and S3 set in N times of the cryptographic operation processing executed successively following the N times of the cryptographic operation processing. Cryptographic device. The encryption device according to claim 1 or 2 ,
The first addition operation processing further performs addition or exclusive OR operation of the addition result of the input data and the output data of the first cyclic shift operation processing and the parameter A1,
The second addition operation processing further performs addition or exclusive OR operation of the addition result of the input data and the output data of the second cyclic shift operation processing and the parameter A2,
The third addition operation processing performs addition or exclusive OR operation of the addition result of the input data and the output data of the third cyclic shift operation processing and the parameter A3. apparatus. The encryption device according to claim 1, 2, or 3 ,
It further comprises algorithm parameter setting means for setting various parameters used for calculation in each of the cryptographic calculation processes executed a plurality of times, including at least the shift numbers S1, S2 and S3 in the cryptographic bit string conversion process. A cryptographic device. A decryption device that decrypts and converts encrypted data generated by the encryption device according to claim 1 or 2 into plaintext data using a decryption key that is common to the encryption key used in the encryption device,
Decryption operation processing is performed by applying the decryption key to the input first and second data and performing the operation processing as first and second data to be input next time. Decryption conversion means for performing the same number of times as the cryptographic operation processing of the encryption conversion means
A splitting unit for decryption that divides the encrypted data into two, and outputs the result as first and second data to be input to the decryption calculation process of the first round of the decryption conversion unit;
A decoding combining unit that combines the first and second data output from the decoding calculation process of the last round of the decoding conversion unit, and outputs the result as equal data;
The decryption calculation process is:
A decryption bit string conversion process for performing the same process as the encryption bit string conversion process in the cryptographic operation process of the cipher conversion unit and an output data of the decryption bit string conversion process are input to the input second data. And an exclusive OR operation process for decoding for calculating an exclusive OR with the first data,
The output data of the exclusive OR operation for decoding is the second data to be input next time, and the input second data is output as the first data to be input next time,
As for the shift numbers S1, S2 and S3 in the decryption bit string conversion process, the values set in the first decryption operation process of the decryption conversion means are set in the last encryption operation process of the encryption conversion means The values set in the last decryption operation process of the decryption / conversion means are set in the first encryption operation process of the encryption / conversion means and match the values of the shift numbers S1, S2 and S3 respectively. Each of the decryption calculation processes executed a plurality of times by the decryption conversion means and the cryptographic calculation processes executed a plurality of times by the encryption conversion means so as to match the values of the shift numbers S1, S2 and S3 respectively The decoding apparatus is characterized in that it is set in reverse order with respect to the execution order. A decryption device that decrypts and converts encrypted data generated by the encryption device according to claim 3 into plaintext data using a decryption key that is common to the encryption key used in the encryption device,
Decryption operation processing is performed by applying the decryption key to the input first and second data and performing the operation processing as first and second data to be input next time. Decryption conversion means for performing the same number of times as the cryptographic operation processing of the encryption conversion means,
A splitting unit for decryption that divides the encrypted data into two, and outputs the result as first and second data to be input to the decryption calculation process of the first round of the decryption conversion unit;
A decoding combining unit that combines the first and second data output from the decoding operation process of the last round of the decoding conversion unit, and outputs a result as equal data; ,
A decryption bit string conversion process for performing the same process as the encryption bit string conversion process in the cryptographic operation process of the cipher conversion unit and an output data of the decryption bit string conversion process are input to the input second data. And an exclusive OR operation process for decoding for calculating an exclusive OR with the first data,
The output data of the exclusive OR operation for decoding is the second data to be input next time, and the input second data is output as the first data to be input next time,
As for the shift numbers S1, S2 and S3 and the parameters A1, A2 and A3 in the decryption bit string conversion process, the values set in the first decryption operation process of the decryption conversion means are the last times of the encryption conversion means. The shift numbers S1, S2 and S3 set in the encryption calculation process of FIG. 4 coincide with the values of the parameters A1, A2 and A3, respectively, and the value set in the decryption calculation process of the last round of the decryption conversion means is The decryption and conversion means executes a plurality of times so that the shift numbers S1, S2 and S3 set in the first cryptographic operation processing of the encryption conversion means coincide with the values of the parameters A1, A2 and A3, respectively. Between each of the decryption operation processes and each of the encryption operation processes executed a plurality of times by the encryption conversion means, the execution order is set in the reverse order. Decoding device. The decoding device according to claim 5 or 6 , comprising:
Algorithm parameter setting means for setting various parameters used for the calculation in each of the decoding calculation processes executed a plurality of times by the decoding conversion means, including at least the shift numbers S1, S2 and S3 in the decoding bit string conversion process The decoding device further comprising: An encryption device having an encryption conversion means, an encryption division means, and an encryption combination means encrypts plaintext data using an encryption key, transmits the result as encryption data, and receives a decryption conversion means, a decryption division means and a decryption means A decryption device having a combining means is an encryption communication method for decrypting and converting the encrypted data into plaintext data using a decryption key common to the encryption key,
In the encryption device,
An encryption division step in which the encryption dividing means divides the plaintext data into two;
The cipher conversion means uses the two pieces of data obtained in the cipher division step as the first and second data to be inputted to the first cipher operation step, and the encryption key is added to the inputted first and second data. A cryptographic conversion step of performing a plurality of cryptographic computation steps to output the results as first and second data to be input to the next cryptographic computation step;
The cryptographic combining means includes a cryptographic combining step of combining the first and second data output by the last cryptographic operation processing in the cryptographic conversion step to generate the cryptographic data;
The cryptographic operation step includes
An encryption bit string conversion step for converting a bit string of input first data, and an exclusive logic for encryption for calculating an exclusive OR of the output data of the encryption bit string conversion step and the input second data A sum operation step,
The output data of the encryption exclusive OR operation step is set as first data to be input to the next encryption operation step, and the input first data is input to the next encryption operation step. Output as data,
The encryption bit string conversion step includes:
A first exclusive OR operation step of calculating an exclusive OR of the input data and the first key data generated from the encryption key or a part thereof;
A first cyclic shift operation step for performing a cyclic shift operation process with a shift number S _{1 on} the input data, and a first operation for adding the input data and the output data of the first cyclic shift operation process A first logical operation step consisting of:
The performing a second cyclic shift calculating step performs cyclic shift processing of the shift number S ₂ to the input data, the addition operation processing of the output data of the with the received data a second cyclic shift calculating step A second logical operation step comprising: 2 addition operation steps;
A second exclusive OR operation step of calculating an exclusive OR of the input data and the second key data generated from the encryption key or a part thereof;
A third cyclic shift operation step of performing cyclic shift processing of shifting the number S ₃ to the input data, the addition operation processing of the output data of the with the input data the third cyclic shift operation steps for encryption Performing a third addition operation step, and a third logical operation step comprising:
The shift numbers S ₁ , S ₂ and S ₃ in the encryption bit string conversion step are all set to be odd numbers, or one of S ₁ and S ₂ is 2 and the remaining two are odd values. And the values of S ₁ , S ₂ and S ₃ are set so as not to coincide with each other between two cryptographic operation steps executed in succession,
In the decoding device,
A decryption and dividing step in which the decryption dividing means divides the encrypted data into two;
The decryption conversion means uses the decryption key as the first and second data inputted as the first and second data to be inputted to the first decryption calculation step with the two data obtained by the decryption division step. A decryption conversion step for performing the same number of times as the encryption operation step, a decryption operation step for outputting the result as first and second data to be input to the next decryption operation step;
The decryption combining means includes a decryption combining step of combining the first and second data output by the last decryption calculation step in the decryption conversion step to generate the plaintext data;
The decoding operation step includes
A decryption bit string conversion step for performing the same processing as the encryption bit string conversion step in the encryption operation step on the input second data, and output data of the decryption bit string conversion step and the input first data Performing an exclusive OR operation step for decoding to calculate an exclusive OR with:
The output data of the decoding exclusive OR operation step is set as second data to be input to the next decoding calculation step, and the input second data is input to the next decoding calculation step. Output as data,
The number of shifts S ₁ , S _2, and S ₃ in the decryption bit string conversion step is the value set in the decryption operation step in the first round of the decryption conversion step. Each of the shift numbers S ₁ , S _2, and S ₃ set in the step matches the value,
The value set in the decryption calculation step in the last round of the decryption conversion step is the same as the values of the shift numbers S ₁ , S ₂ and S ₃ set in the cryptographic calculation step in the first round of the cryptographic conversion step, respectively. Set in reverse order in execution order between each of the decryption operation steps executed a plurality of times in the decryption conversion step and each of the encryption operation steps executed a plurality of times in the encryption conversion step so as to coincide with each other A cryptographic communication method characterized by the above. The encryption communication method according to claim 8 , wherein
An encryption communication method comprising: a key sharing step for holding a common key as an encryption key by the encryption device and holding the common key as a decryption key by the decryption device. It is equipped with an in-vehicle device that is used by being mounted on a vehicle, an IC card that is configured to be freely mounted on the in-vehicle device, and a roadside device that is installed and used on a road.
When the IC card is attached to the in-vehicle device, the contract information stored in the IC card is transmitted to the in-vehicle device by encrypted communication, and the vehicle equipped with the in-vehicle device passes through the roadside device installed on the road. Then, the contract information of the IC card stored in the in-vehicle device is transmitted to the roadside device by encrypted communication, the settlement is performed according to the contract information received from the in-vehicle device in the roadside device, and the settlement information is An automatic fee collection system that transmits to the in-vehicle device by encrypted communication and transmits settlement information from the roadside device received by the in-vehicle device to the IC card by encrypted communication,
The IC card, the in-vehicle device, and the roadside device are each sent from a communication partner and an encryption unit that encrypts plaintext data, which is information to be transmitted to the communication partner, into encrypted data using an encryption key. A decryption unit that decrypts and converts the encrypted data into plaintext data using a decryption key that is common to the encryption key of the communication partner;
The encryption unit is
The cryptographic process is performed by applying the encryption key to the input first and second data, and the result is output a plurality of times as the first and second data to be input next time. Cryptographic conversion means;
Dividing the plaintext data into two, and outputting the result as first and second data to be input to the first cryptographic operation processing of the cipher conversion means;
A cryptographic combining unit that combines the first and second data output from the cryptographic calculation process of the last round of the cryptographic conversion unit, and outputs the result as cryptographic data; ,
Cryptographic bit string conversion process for performing bit string conversion of input first data and Cryptographic exclusive logic for calculating an exclusive OR of output data of the encryption bit string conversion process and input second data A sum operation process,
The output data of the exclusive OR operation for encryption is set as the first data to be input next time, and the input first data is output as the second data to be input next time,
The encryption bit string conversion process includes:
A first exclusive OR operation process for calculating an exclusive OR of the input data and the first key data generated from the encryption key or a part thereof;
A first cyclic shift calculation process for performing a cyclic shift calculation process with a shift number S1 on the input data, and a first calculation for adding the input data and the output data of the first cyclic shift calculation process A first logical operation process comprising: an addition operation process;
A second cyclic shift calculation process for performing a cyclic shift calculation process with a shift number S2 on the input data, and a second calculation process for adding the input data and the output data of the second cyclic shift calculation process. A second logical operation process comprising:
A second exclusive OR operation process for calculating an exclusive OR of the input data and the second key data generated from the encryption key or a part thereof;
A third cyclic shift calculation process for performing a cyclic shift calculation process with a shift number S3 on the input data, and an addition calculation process of the input data and the output data of the third cryptographic cyclic shift calculation process are performed. A third addition operation process, and a third logical operation process including the third addition operation process in a predetermined order,
The shift numbers S1, S2 and S3 in the encryption bit string conversion process are all set to be odd numbers, or one of S1 and S2 is 2 and the remaining two are odd values, and The values of S1, S2 and S3 are set so as not to coincide with each other between the cryptographic computation processes executed successively,
The decoding unit
Decryption operation processing is performed by applying the decryption key to the input first and second data and performing the operation processing as first and second data to be input next time. Decryption conversion means for performing the same number of times as the cryptographic operation processing of the encryption conversion means
A splitting unit for decryption that divides the encrypted data into two, and outputs the result as first and second data to be input to the decryption calculation process of the first round of the decryption conversion unit;
A decoding combining unit that combines the first and second data output from the decoding operation process of the last round of the decoding conversion unit, and outputs a result as equal data; ,
A decryption bit string conversion process for performing the same process as the encryption bit string conversion process in the cryptographic operation process of the cipher conversion unit and an output data of the decryption bit string conversion process are input to the input second data. And an exclusive OR operation process for decoding for calculating an exclusive OR with the first data,
The output data of the exclusive OR operation for decoding is the second data to be input next time, and the input second data is output as the first data to be input next time,
As for the shift numbers S1, S2 and S3 in the decryption bit string conversion process, the values set in the first decryption operation process of the decryption conversion means are set in the last encryption operation process of the encryption conversion means The values set in the decryption calculation process of the last round of the decryption / conversion means are set in the cipher calculation process of the first round of the cipher conversion means, which respectively match the values of the shift numbers S1, S2 and S3 Each of the decryption calculation processes executed a plurality of times by the decryption conversion means and the cryptographic calculation processes executed a plurality of times by the encryption conversion means so as to match the values of the shift numbers S1, S2 and S3 respectively An automatic fee collection system characterized in that it is set in reverse order with respect to each other. An IC card used for the automatic fee collection system according to claim 10 . The vehicle-mounted apparatus used for the automatic fee collection system of Claim 10 . The roadside machine used for the automatic fee collection system of Claim 10 .

Images