(57)【特許請求の範囲】
【請求項１】
かき混ぜ用のＦ関数を用いて暗号化または復号を行う暗号装置であって、
ｎ，１を自然数とし、ベクトルＵ，ＶをＵｓ，Ｖｔ（ｓ＝１〜ｎ，ｔ＝１〜ｎ）を各々要素とするベクトル（但し、Ｕｓ，Ｖｔは位数Ｎ（Ｎは１より大きな自然数）のガロア群の元）とし、
行列Ｍをｍｔｓ（ｓ＝１〜ｎ，ｔ＝１〜ｎ）を要素とするｎ×ｎの正方行列としたとき、ＵのＭによるべき乗Ｖ、即ちＶ＝ＵＭを、各々の要素を用いて、Ｖｔ＝Πs=1ｎＵsｍｔｓ(ｔ＝１〜ｎ）と定義したとき、
前記Ｆ関数がｎ個の要素から成るベクトル（各要素は位数Ｎ（Ｎは１より大きな自然数）のガロア群の元）から成る入力データＸ，鍵Ｋ、及び定ベクトルＢ、並びに、ｎ×ｎの正方行列Ａを用いて、ＦＫ（Ｘ）＝（Ａ・(ＸΘＫ)＋Ｂ)Ａ （但し、Θは排他オア演算を表す。）  で表され、
該Ｆ関数の値ＦＫ（Ｘ）を演算するために、入力データＸと鍵Ｋとによる排他オア演算で、（ＸΘＫ）を演算するための手段と、得られた（ＸΘＫ）と行列Ａとの乗算、及び得られた乗算値へのデータＢの加算により、（Ａ・（ＸΘＫ）＋Ｂ）を演算するための手段と、得られた（Ａ・（ＸΘＫ）＋Ｂ）の行列Ａによるべき乗により、（Ａ・（ＸΘＫ）＋Ｂ）Ａを演算するための手段、とを設けたことを特徴とする、暗号装置。
【請求項２】
前記正方行列Ａが正則で、要素ａtsが０または１からなることを特徴とする、請求項１の暗号装置。
【発明の詳細な説明】
【０００１】
【発明の利用分野】
この発明はＤＥＳ型のかき混ぜ関数を用いた暗号技術に関し、特に暗号化装置や復号装置に関する。
【０００２】
【従来技術】
ＤＥＳやＦＥＡＬなどの暗号システムが、種々提案されている。これらの暗号システムでは、かき混ぜ関数（Ｆ関数あるいはラウンド関数とも呼ばれる）がシステムの中心をなし、１６段程度のＦ関数での処理により、暗号化が行われる。このような暗号技術では鍵は秘密鍵であり、Ｆ関数は入力データと鍵とを用いて出力する。この種の暗号システムに対して、線形攻撃や差分攻撃が有望な攻撃方法として知られ、暗号強度が将来的にも充分であるか否かについて疑問が呈されている。
【０００３】
【発明の課題】
この発明は、暗号強度が高く、アルゴリズムがシンプルな暗号技術を提供することを目的とする。
【０００４】
【用語法他】
この明細書は、数学的アルゴリズムを用いた暗号の発生や復号に関するものであり、各用語は数学的に均等あるいは情報処理上で均等なものを含むように解釈されるものとする。また行列、ベクトル等の概念は、配列等の行列形式で記憶されているか、ベクトルの形式で扱われているか等よりも、処理のアルゴリズムにおいて行列やベクトルとして作用しているかが重要である。ベクトルの行列によるべき乗についても、添字の扱い方や配列の扱い方を変えればべき乗とは異なる処理のごとく表現できるが、そのようなことは重要ではない。
【０００５】
【発明の構成】
この発明は、かき混ぜ用のＦ関数を用いて暗号化または復号を行う暗号装置であって、
ｎ，１を自然数とし、ベクトルＵ，ＶをＵｓ，Ｖｔ（ｓ＝１〜ｎ，ｔ＝１〜ｎ）を各々要素とするベクトル（但し、Ｕｓ，Ｖｔは位数Ｎ（Ｎは１より大きな自然数）のガロア群の元）とし、
行列Ｍをｍｔｓ（ｓ＝１〜ｎ，ｔ＝１〜ｎ）を要素とするｎ×ｎの正方行列としたとき、ＵのＭによるべき乗Ｖ、即ちＶ＝ＵＭを、各々の要素を用いて、Ｖｔ＝Πs=1ｎＵsｍｔｓ(ｔ＝１〜ｎ）と定義したとき、
前記Ｆ関数がｎ個の要素から成るベクトル（各要素は位数Ｎ（Ｎは１より大きな自然数）のガロア群の元）から成る入力データＸ，鍵Ｋ、及び定ベクトルＢ、並びに、ｎ×ｎの正方行列Ａを用いて、ＦＫ（Ｘ）＝（Ａ・(ＸΘＫ)＋Ｂ)Ａ （但し、Θは排他オア演算を表す。）  で表され、
該Ｆ関数の値ＦＫ（Ｘ）を演算するために、入力データＸと鍵Ｋとによる排他オア演算で、（ＸΘＫ）を演算するための手段と、得られた（ＸΘＫ）と行列Ａとの乗算、及び得られた乗算値へのデータＢの加算により、（Ａ・（ＸΘＫ）＋Ｂ）を演算するための手段と、得られた（Ａ・（ＸΘＫ）＋Ｂ）の行列Ａによるべき乗により、（Ａ・（ＸΘＫ）＋Ｂ）Ａを演算するための手段、とを設けたことを特徴とする。
【０００６】
特に好ましくは、前記正方行列Ａが正則で、要素ａtsが０または１からなる。
【０００９】
【発明の作用と効果】
この発明では、Ｆ関数の出力は入力Ｘに対してランダムに近い程度に変化し、線形攻撃や差分攻撃に強い暗号が得られる。そしてＦ関数を全写として扱いやすくすため、好ましくは行列Ａは正則とし、べき乗の演算を容易にするため、その要素ａtsは好ましくは０または１とする。
【００１１】
また特に限定するものではないがこの発明は、ビット単位の排他オア演算や参照表による換字よりも、有限長もしくは有限体での演算により処理が行われるので、ソフトウエアによる実装に適している。そして実施例で例示するように、比較的高速での処理が行える。またＦ関数でのかき混ぜの程度は極めて著しく、Ｆ関数で入力と出力との線形な相関はほとんど失われるので、線形攻撃や差分攻撃に強い暗号系が得られる。以下に実施例を示すが、実施例はこの発明での処理の例であり、請求項で特に限定した点以外は、公知技術や周知技術を加味して変更できる。
【００１２】
【実施例】
図１〜図７に、実施例を示す。最初に、実施例での記号の意味を表１，表２に示す。なお平文Ｍや原始鍵Ｋは各１２８ビット長としたが、その長さは任意で、平文よりも語長の長い原始鍵を用いても良い。また後述のＦ関数を配置する段数は任意である。秘密鍵は原始鍵Ｋとこれから派生するもののみであるが、行列ＡやパラメーターＢ、ｑiも秘密鍵としても良い。
【００１３】
【表１】
0003729486.tif 000002
【００１４】
【表２】
0003729486.tif 000003
【００１５】
図１に、実施例の暗号化装置２を示す。この暗号化装置２は、入力４に平文Ｍを入力し、出力６から暗号文Ｃを取り出すもので、処理の順序を逆にすれば、復号装置としても使用できる。８はビット単位の排他オア演算子で、暗号化装置２には、１６段のラウンドＣ1〜Ｃ16が設けられ、各ラウンド（段）ではかき混ぜ用のＦ関数１０を用いて、入力Ｒiと鍵Ｋi+1とを処理して、その出力と入力Ｌiとを排他オア演算子８でビット単位の排他オア演算を行い、ラウンドの出力とする。１２は鍵生成部で、各ラウンドに６４ビット長の鍵Ｋ1〜Ｋ16を供給すると共に、暗号化の最初や最後に１２８ビット長の鍵Ｋf，Ｋeを供給する。鍵Ｋf，Ｋeは原始鍵Ｋをそのまま用いても良く、あるいは鍵Ｋ1〜Ｋ16と同様に発生させてもよい。ただし鍵長は２倍とする。図１の暗号化装置２は、ＤＥＳ（Data Encription Standard）に類似の暗号化装置に属し、ＤＥＳで用いられる初期転置処理部や最終転置処理部は省略した。なおこの発明の暗号化装置は、多段のラウンドを持ち、各段でＦ関数により入力を鍵により処理するものが好ましく、特に、各段で暗号化過程や復号過程のデータを左半部と右半部とに分割し、その一方の半部に対してＦ関数での処理を行い、Ｆ関数の出力を他方の半部と排他オア演算で処理するものが好ましい。
【００１６】
図２に実施例でのＦ関数１０の構造を示す。図２において、１４〜２０はメモリーで、メモリー１４は入力Ｒi（６４ビット長）を４分割して記憶し、４分割した各ブロックｘ1〜ｘ4をビット単位の排他オア演算子８へ出力する。メモリー１６は鍵Ｋi+1（６４ビット長）を同様に４分割して、ｈ1〜ｈ4として記憶し、排他オア演算子８へ出力する。この結果、排他オア演算子８の出力は、入力Ｒiと鍵Ｋi+1との間の、同じ番号のブロック同士の排他オア演算となる。メモリー１８は６４ビット長のパラメータＢを４分割してｂ1〜ｂ4として記憶し、４つの加算器２２に入力する。なお４つの加算器２２を区別するため、図２には符号Ａ1〜Ａ4を付した。メモリー２０は例えば４行×４列の正則行列Ａを記憶し、用いた正則行列Ａの値を図２の右側に示す。Ａは正則行列に限るものではないが、好ましくは正方行列とし、正則行列の中でも係数が０または１のみから成るものが、処理速度とＦ関数でのかき混ぜの程度との兼ね合いから好ましい。ここではデータＲi，Ｋi+1，Ｂを４分割して用い、これに伴って行列Ａを４行４列の行列としたが、４分割に限るものではなく、ｎ分割であれば、行列Ａはｎ行ｎ列の行列となる。
【００１７】
加算器２２は、入力Ｒiと鍵Ｋi+1との排他オア演算の出力に行列Ａを乗算したものに、パラメータＢを加算した形の出力をする。４つの加算器２２のうちで、ｓ番目の加算器の出力は、下式(1)で表される。
出力s＝Σｘt・ｈt＋ｂs                        (1)
ここにΣはｔ＝１からｎまでの和を意味し、ｔ＝ｓを除いて積算する。またｓは１〜ｎ（ｎはここでは４）とする。パラメータＢの役割は、(1)式でΣｘt・ｈtが０とならないように、ハミング重みを８程度持たせることにある。言い換えるとパラメータＢはハミング重みが、データ長の４０〜６０％が好ましい。加算器２２の出力は、剰余演算部２４でＮを法として剰余演算し、各１６ビットの４ブロックからなる出力Ｚ1〜Ｚ4を得る。出力Ｚ1〜Ｚ4を乗算器２６で相互に乗算もしくはべき乗し、ｔ番目の乗算器は、Ｚ1〜Ｚ4のうちで、Ｚtを除いた３個の入力を互いに乗算する。ｘ1〜ｘ4，ｈ1〜ｈ4等の各ブロックは１６ビット長で、これに対応して各ブロックはＮ＝２16の位数のガロア群の元と見なすことができる。また２16＋１（Ｎ＋１）をＰとすると、Ｐは素数であり、乗算器２６の出力はＰの倍数ではない。剰余演算部２８で、各乗算器２６の出力に対し、Ｎ＋１を法とする剰余演算を行う。剰余演算の出力は、１〜２16の範囲にある。続いて剰余演算部３０で、Ｎ＝２16を法とする剰余演算を行う。この演算は実際には２16を０とし、それ以外の値はそのままにする演算である。そして最後に暗号強度の強化のため、巡回置換部３２で出力に対する巡回置換を行う。例えばこの巡回置換は、所定ビット数の左巡回もしくは右巡回等とする。巡回置換部３２は設けなくても良い。
【００１８】
Ｆ関数１０での正則行列Ａの役割は、加算器２２への入力の組み合わせを定めることと、乗算器２６への入力の組み合わせを定めることである。図２では加算器２２や乗算器２６への入力はワイヤロジックで示したので、正則行列Ａの役割が直接には表れていない。第１番目の加算器は、行列Ａの第１行と４つの排他オア演算子の出力との積和の値にｂ1を加算しており、行列Ａの第１行が（０，１，１，１）なので、２番目〜４番目の排他オア演算子の出力が加算される。２番目の加算器では、行列Ａの第２行が（１，０，１，１）なので、２番目の排他オア演算子の出力を除いたものが加算される。同様にして３番目の加算器では、３番目の排他オア演算子の出力を除いたものが加算され、４番目の加算器では、４番目の排他オア演算子の出力を除いたものが演算される。なお剰余演算部２４は、各加算器毎の出力に対して剰余演算する。
【００１９】
乗算器２６は剰余演算部２４の出力（Ｚ1〜Ｚ4）に対して行列Ａによるべき乗を行う。このべき乗は(2)式で表される。
Ｙt＝Πs=1４Ｚsａｔｓ                                    (2)
べき乗演算でのｔ番目の出力ブロックＹtは、行列Ａのｔ行の値に従って入力Ｚ1〜Ｚ4をべき乗して、これらの積を求めたものとなる。例えば行列Ａの第１行は（０，１，１，１）なので、１番目の乗算器２６の出力はＺ2×Ｚ3×Ｚ4となる。同様に２番目の乗算器の出力はＺ1×Ｚ3×Ｚ4となり、３番目の乗算器の出力はＺ1×Ｚ2×Ｚ4、４番目の乗算器の出力はＺ1×Ｚ2×Ｚ3となる。行列Ａの各要素が０及び１以外の整数を含む場合、乗算器２６への入力を変更する。例えば行列Ａの要素に２が表れる場合、該当する乗算器に対して、Ｚ1〜Ｚ4の内で、対応するものを２回入力して、２乗を入力する。各乗算器２６の出力は４８ビット長のデータで、上位１６ビットをａ、中位の１６ビットをｂ、下位の１６ビットをｃとすると、Ｎ＋１を法とする剰余演算の結果は、ａ−ｂ＋ｃとなり、剰余演算は極めて簡単である。なおＮが２16以外の値の場合、Ｎ＋１が素数とならない場合がある。この場合、Ｎより大きい最初の素数を用いるのが好ましい。
【００２０】
図３に、Ｆ関数１０での処理を示す。Ａを例えば４行４列の正則行列とし、入力データＲiと鍵Ｋi+1とパラメータＢをそれぞれ１６ビットに４分割し、ｘsとｈsとを排他オア演算する。この演算値に対して行列Ａを乗算する。行列との乗算の結果は４ブロックからなり、ｔ番目のブロックの値は
Σs=1４ａts・（ｘsΘｈs）                                  (3)
で、これにｂを加算し、法をＮとしてモジュロを求める。得られる出力Ｚ1〜Ｚ4は
Ｚt＝Σs=1４ａts・（ｘsΘｈs）＋ｂt          mod（Ｎ）     (4)
となる。ここにｔは１〜４までの変数である。続いてブロックＺ1〜Ｚ4からなるベクトルＺを行列Ａでべき乗する。べき乗演算での各出力ブロックは前記の式(2)で表され、これをＮ＋１を法としてモジュロ演算し、次いでＮを法としてモジュロ演算し、巡回置換を施して、Ｆ関数１０の出力とする。
【００２１】
図４，図５に各ラウンドで用いる個別の鍵Ｋ1〜Ｋ16の発生を示す。図４に鍵Ｋ1〜Ｋ16の発生のための構成を示すと、１０は前記のＦ関数で、暗号化部や復号に用いたものと同じＦ関数を用いる。Ｆ関数を共通化することにより、暗号化システムの実装が容易になる。４０は４個のメモリーで、鍵生成データｒi〜ｒi+3を記憶し、ｑiは鍵生成用のパラメータで、例えば６４ビット長のデータとし、初期値ｑ0を１６進コードで例えば０１２３４５６７８９ａｂｃｄｅｆとする。そしてパラメータｑiは個別の鍵の生成毎に変化させることが好ましく、ここではｑi+1＝ｑi＋１（１段毎に１増加）とする。４２はスイッチで、原始鍵Ｋの前半Ｋaと後半Ｋbのいずれかを排他オア演算子８に入力する。
【００２２】
図４の構成では、鍵生成データｒ1に例えばデータＫaを代入し、ｒ2にデータＫbを代入する。ｒ3以降のデータは、Ｆ関数１０の出力にスイッチ４２で定まるデータＫaまたはＫbを、排他オア演算子８で排他オア演算したものを順次入力する。なお原始鍵Ｋの語長がより長ければ、例えばデータｒ3以降にも原始鍵の一部を入力し、Ｆ関数１０の出力のフィードバックを遅らせればよい。これらのため、Ｆ関数１０への入力は、鍵Ｋ1に対してはＫaΘＫbとなり、鍵Ｋ2に対してはＫbΘｒ3となり、以降はｒiΘｒi+1となる。Ｆ関数１０での処理には、データｒi（排他オア演算子８の出力を利用）の他に、鍵とパラメータＢと行列Ａとが必要で、パラメータＢや行列Ａには、例えば図２の構成で用いたパラメータＢや行列Ａを兼用する。鍵に代えて、図４ではＦ関数１０にパラメータｑiを入力する。そしてＦ関数の出力を、データＫaまたはＫbと排他オア演算して、次の鍵生成データとして記憶する。
【００２３】
図４で生成する鍵ＫiはＦ関数１０で処理されているので、各段毎の鍵に見かけ上相関が無く、暗号の強度が増す。またＦ関数１０の入力側に排他オア演算子８があるので、仮にあるラウンドでの鍵Ｋiが解読されても、その鍵の生成に用いた鍵生成データを求めるのは困難である。そして鍵生成データｒi〜ｒi+3は、Ｆ関数１０の出力ＫiとデータＫaまたはＫbの排他オア演算を経たものであるので、仮にあるラウンドでの鍵Ｋiを解読できても、それ以降の段の鍵生成データを求めることは困難である。これらのために、全体として各段毎に鍵がランダムに変化し、ある段の鍵が判明しても他の段の鍵を求めることができず、解読での最終目的の原始鍵Ｋを求めるのは極めて困難である。
【００２４】
図５に秘密の鍵Ｋ1〜Ｋ16の生成アルゴリズムを示す。原始鍵Ｋを前半部Ｋaと後半部Ｋbとに分割し、これらを鍵生成データの初期値ｒ1およびｒ2とする。同様にしてパラメータの初期値ｑ0を用意する。秘密鍵の生成ループでは、（ｉ番目の鍵Ｋiを生成させるものと仮定して説明する）、データｒiとｒi+1の排他オア演算を行い、Ｆ関数１０に入力して、その出力を秘密の鍵Ｋiとする。続いてスイッチ４２で定まるデータＫaまたはＫbとＫiと、鍵Ｋiとの排他オア演算を行い、その出力をｒi+3等として記憶する。これで１段分の鍵が生成したので、ｉを１増加し、パラメータｑiに代えて次のパラメータｑi+1を用い、次のラウンドの鍵Ｋi+1を生成する。
【００２５】
図６に、Ｆ関数１０を１段通過させた際の、入力データ（１６ビット長）に対する出力データの変化ビット数を示す。なお実施例では、６４ビット長のデータを１６ビットの４ブロックに分割してＦ関数１０を構成したが、図６ではシミュレーションを簡単にするため、１６ビット長のデータを４ビットの４ブロックに分割し、その他は同様にして、シミュレーション用のＦ関数を構成した。行列Ａは前記のもので、パラメータＢはハミング重みが８ビットになるように選び、原始鍵は１６ビット長である。なお図６のデータは、Ｆ関数の撹拌効果をシミュレーションしたものである。
【００２６】
図６の横軸は、Ｆ関数を１回通過した際に、１６ビットのデータ中で値が反転したビットの数であり、縦軸は各ビット変化数が占める割合である。図６にはＤＥＳのＦ関数の場合と、実施例の場合、並びに１６ビットのデータをランダムに変化させた場合（２項分布）、の３つのパターンを示す。実施例での変化ビット数のパターンは２項分布に近く、Ｆ関数を１回通過させることにより、見かけ上出力と入力との相関が断ち切られる。
【００２７】
図６から、実施例では線形攻撃や差分攻撃に強い暗号強度の高い暗号システムが得れることが予想される。また暗号化や復号化のアルゴリズムはシンプルであり、実装は容易である。さらにシミュレーションでは、ＤＥＳを２回繰り返して行う場合と同等の暗号化速度や復号速度が得られた。従って処理速度もＤＥＳに比べて大差がない。
【００２８】
図７に実施例の暗号化装置の応用を示す。図７において、５０は通信端末等のデジタル情報処理装置で、５２は暗号化プログラムや復号プログラム等を記憶した補助メモリーで、Ｆ関数を実現するためのＦ関数処理プログラム５６と、鍵生成系を実現するための鍵生成処理プログラム５８、Ｆ関数の実現と鍵の生成以外の暗号化や復号での処理を実現するための一般処理プログラム５４とを備えている。そしてこれらの処理プログラム５４〜５８は、デジタル情報処理装置５０に処理を実行させるためのプログラムとして記憶され、メモリー５２をデジタル情報処理装置５０にセットすると、この発明を実施できる。なお暗号化や復号のプログラムは、通信回線を介して搬送波などを媒体として、デジタル情報処理装置５０に与えても良く、ＲＯＭ等により当初からデジタル情報処理装置５０に記憶させても良い。なおラウンドの段数、データや鍵のブロック長等は任意である。
【図面の簡単な説明】
【図１】  実施例の暗号化装置のブロック図
【図２】  実施例でのＦ関数のブロック図
【図３】  実施例のＦ関数での処理を示すフローチャート
【図４】  実施例での鍵生成部のブロック図
【図５】  実施例での鍵生成のアルゴリズムを示すフローチャート
【図６】  実施例でのＦ関数×１回の処理による変化ビット数を示す特性図で、入力１６ビット中で値が反転したビットの数の分布を示す。
【図７】  実施例での暗号通信を示すブロック図
【符号の説明】
２          暗号化装置
４          入力
６          出力
８          排他オア演算子
Ｃ1〜Ｃ16     ラウンド
１０          Ｆ関数
１２          鍵生成部
１４〜２０    メモリー
２２          加算器
２４，２８，３０    剰余演算部
２６          乗算器
３２          巡回置換部
４０          メモリー
４２          スイッチ
５０          デジタル情報処理装置
５２          補助メモリー
５４          一般処理プログラム
５６          Ｆ関数処理プログラム
５８          鍵生成処理プログラム
【図１】
0003729486.tif 000004
【図２】
0003729486.tif 000005
【図３】
0003729486.tif 000006
【図４】
0003729486.tif 000007
【図５】
0003729486.tif 000008
【図６】
0003729486.tif 000009
【図７】
0003729486.tif 000010