(57)【特許請求の範囲】
【請求項１】
かき混ぜ用のＦ関数を複数段に配置して、暗号化または復号を行うに際して、各段のＦ関数に鍵を供給するための、デジタル情報処理装置を用いた鍵の生成方法であって、
前記Ｆ関数が、  Ｆ＝（Ａ・（ＸΘＫ）＋Ｂ）Ａ  で表され、
Ｘが秘密の原始鍵に由来するｎブロックのデータで各ブロックをＸsとし、ｎブロックからなる鍵の生成パラメータをＫとし、Ａがｎ×ｎの正則行列でその要素ａｔｓが０または１からなり、Ｘの行列Ａによるべき乗ＸＡがｎブロックのデータからなり、そのｔ番目のブロック（ｔ＝１〜ｎ）を
ＸＡｔ＝Πs=1ｎＸsａｔｓ  とし、Ｂがｎブロックのデータで、Θは排他オア演算を表すものとして、
前記デジタル情報処理装置に、
行列Ａを記憶するためのメモリーと、データＸを記憶するためのメモリーと、鍵の生成パラメーターＫを記憶するためのメモリーと、データＢを記憶するためのメモリーと、
データＸと鍵の生成パラメーターＫとの排他オア演算を、前記ブロック単位で行うためのｎ個の排他オア演算手段を設けると共に、
ｎブロックからなるデータ（Ａ・（ＸΘＫ）＋Ｂ）を演算するための、ｎ個の加算手段により構成された手段を設けて、そのｉ番目（ｉ＝１〜ｎ）の加算手段を、前記ｎ個の排他オア演算手段中の、ｓ番目（ｓ＝１〜ｎ）の排他オア演算手段の出力を、行列Ａの要素ａｉｓの値が１で加算し０で加算しないようにすると共に、データＢのｉ番目のブロックｂｉを加算するようにし、
さらにデータ（Ａ・（ＸΘＫ）＋Ｂ）の行列Ａによるべき乗（Ａ・(ＸΘＫ）＋Ｂ）Ａを演算するための、ｎ個の乗算手段により構成された手段を設けて、そのｉ番目（ｉ＝１〜ｎ）の乗算手段を、前記ｎ個の加算手段中の、ｓ番目（ｓ＝１〜ｎ）の加算手段の出力を、行列Ａの要素ａｉｓの値が１で乗算し０で乗算しないようにして、
（Ａ・（ＸΘＫ）＋Ｂ）を演算させるステップと、
（Ａ・（ＸΘＫ）＋Ｂ）の行列Ａによるべき乗（Ａ・（ＸΘＫ）＋Ｂ）Ａを演算させるステップ、とを前記デジタル情報処理装置に実行させることにより、少なくとも１段分の鍵を生成させることを特徴とする、鍵の生成方法。
【請求項２】
生成した鍵を、前記Ｆ関数の入力側にフィードバックするステップを、前記デジタル情報処理装置に実行させて、以降の段の鍵の生成データとすることを特徴とする、請求項１の鍵の生成方法。
【請求項３】
前記鍵の生成データを複数段分記憶するステップと、段が異なる鍵の生成データ間で排他オア演算を施すステップと、該排他オア演算の結果を前記Ｆ関数に入力するステップとを、前記デジタル情報処理装置に実行させることを特徴とする、請求項２の鍵の生成方法。
【請求項４】
生成した鍵と原始鍵との排他オア演算を行うステップを前記デジタル情報処理装置に実行させて、該排他オア演算で得られた出力を前記鍵の生成データとすることを特徴とする、請求項２または３の鍵の生成方法。
【請求項５】
かき混ぜ用のＦ関数を複数段に配置して、暗号化または復号を行うに際して、各段のＦ関数に鍵を供給するための、デジタル情報処理装置を用いた鍵の生成装置であって、
前記Ｆ関数が、  Ｆ＝（Ａ・（ＸΘＫ）＋Ｂ）Ａ  で表され、
Ｘが秘密の原始鍵に由来するｎブロックのデータで各ブロックをＸsとし、ｎブロックからなる鍵の生成パラメータをＫとし、Ａがｎ×ｎの正則行列でその要素ａｔｓが０または１からなり、Ｘの行列Ａによるべき乗ＸＡがｎブロックのデータからなり、そのｔ番目のブロック（ｔ＝１〜ｎ）を
ＸＡｔ＝Πs=1ｎＸsａｔｓ  とし、Ｂがｎブロックのデータで、Θは排他オア演算を表すものとして、
前記デジタル情報処理装置に、
行列Ａを記憶するためのメモリーと、データＸを記憶するためのメモリーと、鍵の生成パラメーターＫを記憶するためのメモリーと、データＢを記憶するためのメモリーと、
データＸと鍵の生成パラメーターＫとの排他オア演算を、前記ブロック単位で行うためのｎ個の排他オア演算手段を設けると共に、
ｎブロックからなるデータ（Ａ・（ＸΘＫ）＋Ｂ）を演算するための、ｎ個の加算手段により構成された手段を設け、
そのｉ番目（ｉ＝１〜ｎ）の加算手段を、前記ｎ個の排他オア演算手段中の、ｓ番目（ｓ＝１〜ｎ）の排他オア演算手段の出力を、行列Ａの要素ａｉｓの値が１で加算し０で加算しないようにすると共に、データＢのｉ番目のブロックｂｉを加算するようにすることにより、
ｉ番目の加算手段の出力がデータ (Ａ・（ＸΘＫ）＋Ｂ）のｉ番目のブロックとなるようにし、
さらに、データ（Ａ・（ＸΘＫ）＋Ｂ）の行列Ａによるべき乗（Ａ・(ＸΘＫ）＋Ｂ）Ａを演算するための、ｎ個の乗算手段により構成された手段を設け、
そのｉ番目（ｉ＝１〜ｎ）の乗算手段を、前記ｎ個の加算手段中の、ｓ番目（ｓ＝１〜ｎ）の加算手段の出力を、行列Ａの要素ａｉｓの値が１で乗算し０で乗算しないようにすることにより、少なくとも１段分の鍵を生成させることを特徴とする鍵の生成装置。
【発明の詳細な説明】
【０００１】
【発明の利用分野】
この発明は秘密鍵暗号システムでの、Ｆ関数用の個別の鍵の生成に関する。
【０００２】
【従来技術】
種々の公開鍵暗号システムが知られ、これらは秘密の原始鍵を用いて各段のＦ関数で用いる個別の鍵を生成する。そしてＦ関数では、入力文を生成した個別の鍵と組み合わせて撹拌する。鍵の生成では、原始鍵の一部を取り出して巡回シフトし選択置換を施して個別の鍵とする（ＤＥＳ）、あるいは鍵の生成用に設けた専用の関数を用いる（ＦＥＡＬ）等のことが行われている。巡回シフトや選択置換による鍵の生成は簡単であるが、各段の鍵の１つが判明すれば、他の段の鍵の候補も絞られる。一方、鍵の生成用に専用の関数を設けるのでは、暗号化や復号のためのＦ関数と同程度の資源を鍵の生成に割り当てることになり、実装上の効率が低い。
【０００３】
【発明の課題】
この発明の課題は、１段毎に充分に撹拌できる新たなＦ関数を提供することにより、原始鍵から複雑に変化した鍵を生成させる方法や装置を提供することにある。
請求項３や請求項４の発明での追加の課題は、仮にある段で鍵が判明した場合でも、他の段の鍵が判明しないようにすることにある。
【０００４】
【発明の構成】
この発明では、かき混ぜ用のＦ関数を複数段に配置して、暗号化または復号を行うに際して、各段のＦ関数に鍵を供給するための、デジタル情報処理装置を用いた鍵の生成方法であって、
前記Ｆ関数が、  Ｆ＝（Ａ・（ＸΘＫ）＋Ｂ）Ａ  で表され、
Ｘが秘密の原始鍵に由来するｎブロックのデータで各ブロックをＸsとし、ｎブロックからなる鍵の生成パラメータをＫとし、Ａがｎ×ｎの正則行列でその要素ａｔｓが０または１からなり、Ｘの行列Ａによるべき乗ＸＡがｎブロックのデータからなり、そのｔ番目のブロック（ｔ＝１〜ｎ）を
ＸＡｔ＝Πs=1ｎＸsａｔｓ  とし、Ｂがｎブロックのデータで、Θは排他オア演算を表すものとして、
前記デジタル情報処理装置に、
行列Ａを記憶するためのメモリーと、データＸを記憶するためのメモリーと、鍵の生成パラメーターＫを記憶するためのメモリーと、データＢを記憶するためのメモリーと、
データＸと鍵の生成パラメーターＫとの排他オア演算を、前記ブロック単位で行うためのｎ個の排他オア演算手段を設けると共に、
ｎブロックからなるデータ（Ａ・（ＸΘＫ）＋Ｂ）を演算するための、ｎ個の加算手段により構成された手段を設けて、そのｉ番目（ｉ＝１〜ｎ）の加算手段を、前記ｎ個の排他オア演算手段中の、ｓ番目（ｓ＝１〜ｎ）の排他オア演算手段の出力を、行列Ａの要素ａｉｓの値が１で加算し０で加算しないようにすると共に、データＢのｉ番目のブロックｂｉを加算するようにし、
さらにデータ（Ａ・（ＸΘＫ）＋Ｂ）の行列Ａによるべき乗（Ａ・(ＸΘＫ）＋Ｂ）Ａを演算するための、ｎ個の乗算手段により構成された手段を設けて、そのｉ番目（ｉ＝１〜ｎ）の乗算手段を、前記ｎ個の加算手段中の、ｓ番目（ｓ＝１〜ｎ）の加算手段の出力を、行列Ａの要素ａｉｓの値が１で乗算し０で乗算しないようにして、
（Ａ・（ＸΘＫ）＋Ｂ）を演算させるステップと、
（Ａ・（ＸΘＫ）＋Ｂ）の行列Ａによるべき乗（Ａ・（ＸΘＫ）＋Ｂ）Ａを演算させるステップ、とを前記デジタル情報処理装置に実行させることにより、少なくとも１段分の鍵を生成させる。
【０００５】
好ましくは、生成した鍵をＦ関数の入力側にフィードバックし、以降の段の鍵の生成データとする。
より好ましくは、前記鍵の生成データを複数段分記憶し、段が異なる鍵の生成データ間で排他オア演算を施して、前記Ｆ関数に入力する。
また好ましくは、生成した鍵と原始鍵との排他オア演算の出力を、前記鍵の生成データとする。
【０００６】
この発明はまた、かき混ぜ用のＦ関数を複数段に配置して、暗号化または復号を行うに際して、各段のＦ関数に鍵を供給するための、デジタル情報処理装置を用いた鍵の生成装置であって、
前記Ｆ関数が、  Ｆ＝（Ａ・（ＸΘＫ）＋Ｂ）Ａ  で表され、
Ｘが秘密の原始鍵に由来するｎブロックのデータで各ブロックをＸsとし、ｎブロックからなる鍵の生成パラメータをＫとし、Ａがｎ×ｎの正則行列でその要素ａｔｓが０または１からなり、Ｘの行列Ａによるべき乗ＸＡがｎブロックのデータからなり、そのｔ番目のブロック（ｔ＝１〜ｎ）を
ＸＡｔ＝Πs=1ｎＸsａｔｓ  とし、Ｂがｎブロックのデータで、Θは排他オア演算を表すものとして、
前記デジタル情報処理装置に、
行列Ａを記憶するためのメモリーと、データＸを記憶するためのメモリーと、鍵の生成パラメーターＫを記憶するためのメモリーと、データＢを記憶するためのメモリーと、
データＸと鍵の生成パラメーターＫとの排他オア演算を、前記ブロック単位で行うためのｎ個の排他オア演算手段を設けると共に、
ｎブロックからなるデータ（Ａ・（ＸΘＫ）＋Ｂ）を演算するための、ｎ個の加算手段により構成された手段を設け、
そのｉ番目（ｉ＝１〜ｎ）の加算手段を、前記ｎ個の排他オア演算手段中の、ｓ番目（ｓ＝１〜ｎ）の排他オア演算手段の出力を、行列Ａの要素ａｉｓの値が１で加算し０で加算しないようにすると共に、データＢのｉ番目のブロックｂｉを加算するようにすることにより、
ｉ番目の加算手段の出力がデータ (Ａ・（ＸΘＫ）＋Ｂ）のｉ番目のブロックとなるようにし、
さらに、データ（Ａ・（ＸΘＫ）＋Ｂ）の行列Ａによるべき乗（Ａ・(ＸΘＫ）＋Ｂ）Ａを演算するための、ｎ個の乗算手段により構成された手段を設け、
そのｉ番目（ｉ＝１〜ｎ）の乗算手段を、前記ｎ個の加算手段中の、ｓ番目（ｓ＝１〜ｎ）の加算手段の出力を、行列Ａの要素ａｉｓの値が１で乗算し０で乗算しないようにすることにより、少なくとも１段分の鍵を生成させる。
請求項２の発明を実行する場合、さらにＦ関数の入力側に生成した鍵をフィードバックするための手段を設ける。
請求項３の発明を実行する場合、さらにＦ関数の入力側に複数段分の鍵の生成データの記憶部を設ける。
請求項４の発明を実行する場合、さらにＦ関数の出力側に排他オア演算手段を設けて、出力した個別の鍵と原始鍵との排他オア演算を行い、その出力を鍵の生成データとする。
【０００７】
【発明の作用と効果】
この発明では、原始鍵を、暗号化や復号に用いるＦ関数と同じＦ関数で処理して、少なくとも１段分の鍵を生成させるので、原始鍵からＦ関数で複雑に変化した鍵が得られる。また暗号化や復号と同じＦ関数を用いるので、実装が容易である。
【０００８】
請求項２の発明では、生成した鍵を以降の段の鍵の生成データとするので、原始鍵を鍵の生成データとして常時用いる場合よりも、原始鍵の秘匿性が高い。
請求項３の発明では、複数段分の鍵の生成データを排他オア演算してＦ関数に入力するので、仮にある段の鍵が判明しても、それ以前の段の鍵を解読するのが困難になる。
請求項４の発明では、生成した鍵と原始鍵との排他オア演算の出力を、以降の段のための鍵の生成データとするので、仮にある段の鍵が判明しても、それ以降の段の鍵の生成データを推定するのが困難になる。
【０００９】
この発明では、入力と鍵との排他オア演算の結果をベクトルと見なして、行列と乗算する。このため入力は複雑に撹拌される。この乗算値にパラメーターＢを加算し、Ｆ関数の入力や鍵が（０００…）等の脆弱な値になった場合でも、ハミング重みを充分大きくする。さらに得られたベクトルを行列によりべき乗し、ベクトルをさらに撹拌して出力する。このＦ関数は、ソフトウェアやＤＳＰ（デジタルシグナルプロセッサ）で実装した場合に、ＤＥＳ等と同定程度の速度で実行でき、アルゴリズムが明解で、実装が容易で、１段毎の撹拌が充分で、ランダムな出力との区別が難しいとの特徴がある。
【００１０】
【実施例】
図１〜図７に、実施例を示す。最初に、実施例での記号の意味を表１，表２に示す。なお平文Ｍや原始鍵Ｋは各１２８ビット長としたが、その長さは任意で、平文よりも語長の長い原始鍵を用いても良い。また後述のＦ関数を配置する段数は任意である。秘密の鍵は原始鍵Ｋとこれから派生する各段の鍵のみであるが、行列ＡやパラメーターＢ、ｑiも秘密鍵としても良い。
【００１１】
【表１】
記号     記号の意味                            
Ｍ            平文（１２８ビット長）
Ｃ            暗号文（１２８ビット長）
Ｒ，Ｌ        暗号化や復号の過程でのデータの右半部と左半部で、
各６４ビット長
Ｋ            原始鍵（１２８ビット長）
Ｋa，Ｋb      原始鍵の前半と後半  （各６４ビット長）
Ｋf ，Ｋ1  〜Ｋ16，Ｋe    鍵
Ｂ            パラメータ（６４ビット長）            ｜０１１１｜
Ａ            正則なパラメータ行列    例えば  Ａ＝  ｜１０１１｜
｜１１０１｜
｜１１１０｜
ｘ1〜ｘ4      Ｒiを４分割した１６ビット長データ
ｈ1〜ｈ4      Ｋi+1を４分割した１６ビット長データ
ｂ1〜ｂ4      Ｂを４分割した１６ビット長データ
なおＲi，Ｋi+1，Ｂ等は、（ｘ1〜ｘ4）、（ｈ1〜ｈ4）、（ｂ1〜ｂ4）等で構成される４次元等のベクトル空間の元と見なすこともできる。
Ｎ            ２１６  等の２のべき乗で、ｘ1〜ｘ4，ｈ1〜ｈ4，ｂ1〜ｂ4の属するガロア群の位数
Ｐ            Ｎ＋１，Ｎ＋３等のＮよりやや大きい素数でここではＮ＋１
ｒi〜ｒi+1    鍵生成データ
ｑｉ           鍵生成パラメータで例えばラウンド毎に１加算
【００１２】
【表２】
添字や演算等の意味  
ｎ            ブロック数を示す記号で、ここでは４
ｉ            ラウンドを示す添字
ｓ，ｔ        Ａの成分等を示す添字    （Ａのｓ行ｔ列成分がａst）
Θ            排他オア演算を示す記号
ＸＡ           ベクトルＸの行列Ａによるべき乗で、出力ＹはＸと同じブロック数ｎを持ち、そのｔ番目の成分を
Ｙt＝Πs=1ｎＸsａｔｓ  （ｔ＝１〜ｎで、ＹtはＹのｔ番目のブロック）
と定める。
Ａ・Ｘ        行列とベクトルの乗算で、乗算は通常の定義に従い、出力はＸと同じブロック数を持つ。
【００１３】
図１に、実施例の暗号化装置２を示す。この暗号化装置２は、入力４に平文Ｍを入力し、出力６から暗号文Ｃを取り出すもので、処理の順序を逆にすれば、復号装置としても使用できる。８はビット単位の排他オア演算子で、暗号化装置２には、１６段のラウンドＣ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     ラウンド
１０          Ｆ関数
１２          鍵生成部
１４〜２０    メモリー
２２          加算器
２４，２８，３０    剰余演算部
２６          乗算器
３２          巡回置換部
４０          メモリー
４２          スイッチ
５０          デジタル情報処理装置
５２          補助メモリー
５４          一般処理プログラム
５６          Ｆ関数処理プログラム
５８          鍵生成処理プログラム
【図１】
0004100864.tif 000002
【図２】
0004100864.tif 000003
【図３】
0004100864.tif 000004
【図４】
0004100864.tif 000005
【図５】
0004100864.tif 000006
【図６】
0004100864.tif 000007
【図７】
0004100864.tif 000008