JPH08505275A - 暗号ストリームを発生させるための装置及び方法 - Google Patents

Abstract

(57)【要約】 デジタルメッセージの暗号化又は復号化を行うためのシステムにおいて、疑似ランダムデータ系列を発生させるための線形駆動サブシステム(4)と、前記疑似ランダムデータ系列から暗号ストリームを生成するための非線形フィードバック・サブシステム(6)と、メッセージを前記暗号ストリームと結合することにより該メッセージの暗号化又は復号化を行うための暗号化処理装置(26)とを備え、前記非線形フィードバック・サブシステムが、フィードバック系列(12)を、前記疑似ランダムデータ系列のうちの少なくとも一つの値と前記フィードバック系列のうちの少なくとも一つの前の値とに非線形関数を適用することにより発生させるための非線形フィードバック処理手段(10)と、前記疑似ランダムデータ系列中の値の複数対であって該対の各要素間の系列中における位置の差が各対によって異なるように選択された対の積を前記フィードバック系列のうちの一つの値とともに足し合わせることにより前記暗号ストリームを発生させるための暗号ストリーム発生器(10)と、を有してなるシステム。

Description

【発明の詳細な説明】 暗号ストリームを発生させるための装置及び方法 本発明は、暗号ストリーム(cipher stream)を発生させるための装置及び方法 に関する。本発明の実施例は、遠距離通信やコンピュータ通信のシステム等にお けるデジタル・メッセージの暗号化にその用途を見つけることができる。 広帯域の統合デジタル通信ネットワーク（Ｂ−ＩＳＤＮ）のようなデジタル通 信システムでは、メッセージを傍受した者がその意味内容を調べることができな いように伝送デジタルメッセージを暗号化することが、多くの場合、好都合であ る。そこで、このネットワークの送信側において、平文テキストのメッセージは 、暗号化鍵による制御の下で、できれば秘密の復号化鍵を持っていない者には判 読できない暗号文テキストに変換される。そのネットワーク上の正当な受信側で は、その暗号文テキストは、秘密の復号化鍵による制御の下で、元の平文テキス トのメッセージに再変換される。このように行われる暗号方式は一般にブロック 暗号と逐次暗号とに分類される。 逐次暗号は平文テキストをキャラクタに分割することによって作用し、分割さ れた各キャラクタは、時間依存性が逐次暗号の内部状態に支配される時変関数(t ime varying function)を利用して暗号化される。この時変関数は、鍵ストリー ム発生器によって生成される。この鍵ストリーム発生器は、秘密にされている鍵 データによりデジタル暗号ストリームを発生させる。鍵ストリーム発生器は、生 成される暗号ストリームが循環的な疑似ランダムビット・ストリームではあるが 、与えられた鍵データの長さよりも十分に長い周期を有するものとなるように構 成される。逐次暗号では、暗号化された各キャラクタの後に装置の状態が或る規 則に従って変化するので、平文テキスト・メッセージにおいて同一キャラクタが 二つ出現しても、通常、暗号文テキストにおいて同一キャラクタにはならないよ うになっている。 逐次暗号の構成及びその効果的な実用のための評価基準については、広く文献 で論じられているところであり、例えば次の文献にそれらの記載を見ることがで きる。 [1]ベーカ、パイパー共著「Cipher systems-The Protection of Communicat ions（暗号化システム−通信の保護）」(H.Beker and F.Piper，Cipher systems - The Protection of Communications，Northwood Book，London，1982) [2]ルーペル著「Analysis and design of stream ciphers（逐次暗号の分析 と設計）」（R.A．Rueppel，Analysis and design of stream ciphers，Springe r-Verlag，Berlin，1986） [3]メイアー、スタフェルバーク共著「Nonlinearity criteria for cryptog raphic functions（暗号化関数のための非線形性の評価基準）」(W．Meier and O．Staffelbach，Nonlinearity criteria for cryptographic functions，Advan ces in Cryptology-Eurocrypt’89，Proceedings，Springer-Verlag，549-562) 要するに、逐次暗号の安全性は、出力される暗号鍵ストリームの「無作為性(r andomness)」に依存する。傍受者（暗号解読者）が平文テキスト・メッセージを 知っていると仮定すると、暗号解読者は、使用中の鍵ストリームの全てにアクセ スしているかもしれない。システムを安全たらしめるためには、暗号ストリーム は予想不可能なものでなければならない。すなわち、観測される暗号ストリーム のディジット数に拘らず、後続の暗号ストリームのディジットは全くランダムに 推定するより以上に良く予想できるものであってはならない。これは、暗号解読 者が暗号ストリームを確実に予想できるような真の鍵を決定することはできない ということを意味する。予測不能であるための必要条件は、暗号ストリームの周 期が長いことである。周期は線形再帰(linear recursion)を定めるものであり、 周期の値と最初の１周期分の暗号ストリームとがわかれば、その暗号ストリーム の残りが完全に確定する。所定のシーケンス（系列）を発生できる最短の非線形 フィードバック・シフトレジスタを見つけるのは一般には困難な作業であるが、 そのようなことを行うためのアルゴリズムまたは方法が存在する。したがって、 暗号ストリームが予想不能であるためには、その線形の複雑さ（linear complex ity）（これは、その暗号ストリームを生成できる最短の線形フィードバック・ シフトレジスタの長さである）もまた大きなものであることが必要である。また 予測不能であるためには、次の鍵暗号ディジットは先行ディジットに依存せず、 一様に分布したものから取り出されたように見えることが必要である。したがっ て、暗号ストリームは必ず統計上の数値が一様なものでなければならない。すな わち、１個のディジットからなるディジット群、１群が２個のディジットからな るディジット群、１群が３個のディジットからなるディジット群などの分布が一 様でなければならない。 最後に、線形の複雑さが大きくとも、暗号ストリームは予測可能な如何なる線 形形式（linear form）に近づくことさえないことが一般に好ましい。すなわち 、暗号ストリームは、如何なる線形形式にも互いに関係づけられるべきではない 。さらに、逐次暗号に関して頻繁には考慮されていない要素に、暗号化テキスト の完全性（integrity）がある。受信されて解読された平文化テキストが伝送さ れた元の平文テキストに一致するか否か、言い換えると暗号化テキストが伝送中 に変更されたか否かを、受信者が判断できるようにするために、平文テキスト・ メッセージの内容から定まるメッセージ認証コード（ＭＡＣ）が、しばしば暗号 化テキストとともに伝送される。しかし、或る暗号化方式では、たとえ傍受者が 変更された暗号化テキストの意味を確定することができないとしても、その変更 が受信者にはわからないように、暗号化テキスト・メッセージと暗号化されたＭ ＡＣの双方を変更することが可能であるかもしれない。したがって、検出を伴わ ずに伝送中におけるそのような変更が生じないようにする完全性検査（integrit y checking）を暗号化方式が備えていることもまた望ましい。 したがって、本発明は、暗号ストリームを発生させるためのデジタルデータ・ ストリーム発生装置であって、少なくとも一つの疑似ランダムデータ・ストリー ムを生成するフィードバック・シフトレジスタ構造体と、前記少なくとも一つの データ・ストリームから暗号ストリームを生成する処理構造体であって、少なく とも一つのデータ・ストリームの先行する複数の値から導出される結合値（comb in ation values）の系列を記憶する手段、及び、前記結合値の複数対について、各 対の結合値間の系列中の位置の差が異なるように乗算し、該乗算された複数対を 加算することにより前記暗号ストリームを生成する処理手段を有する処理構造体 と、で構成されたデジタルデータ・ストリーム装置を提供している。 また本発明は、暗号ストリームを発生させるためのデジタルデータ発生装置で あって、少なくとも一つの線形フィードバック・シフトレジスタ（ＬＦＳＲ）と 、前記少なくとも一つのＬＦＳＲの出力の総和の系列を生成するための加算手段 と、非線形値の系列を前記少なくとも一つのＬＦＳＲの出力と前記非線形出力値 の系列の少なくとも一つの前の値とにより生成するための非線形フィードバック 処理手段と、前記総和の系列の複数対と前記非線形値の系列の少なくとも一つと を利用してベント関数によりデータ・ストリームを発生させるための出力処理手 段とからなり、各対の要素の系列中の位置の差が各対によって異なっているデジ タルデータ発生装置を提供する。 また本発明は、デジタルメッセージの暗号化又は復号化を行うためのシステム であって、疑似ランダムデータ系列を発生させるための線形駆動サブシステムと 、前記疑似ランダムデータ系列から暗号ストリームを生成するための非線形フィ ードバック・サブシステムと、メッセージを前記暗号ストリームと結合すること により該メッセージの暗号化又は復号化を行うための暗号化処理装置とを備え、 前記非線形フィードバック・サブシステムが、フィードバック系列を、前記疑似 ランダムデータ系列のうちの少なくとも一つの値と前記フィードバック系列のう ちの少なくとも一つの前の値とに非線形関数を適用することにより発生させるた めの非線形フィードバック処理手段と、前記疑似ランダムデータ系列中の値の複 数対であって該対の各要素間の系列中における位置の差が各対によって異なるよ うに選択された対の積を前記フィードバック系列のうちの一つの値とともに足し 合わせることにより、前記暗号ストリームを発生させるための暗号ストリーム発 生器とで構成されてなるシステムを提供する。 また本発明は、暗号ストリームを発生させるための方法であって、疑似ランダ ムデータ・ストリーム系列を発生させるステップと、前記データ・ストリーム系 列 中の値の複数対であって該対の各要素間の系列中における位置の差が各対によっ て異なるように選択された対の積を前記データ・ストリーム系列からの値の非線 形フィードバック関数より導出される値とともに足し合わせることにより、暗号 ストリームを発生させるステップと、からなる方法を提供する。 さらに本発明は、デジタルメッセージの暗号化又は復号化を行うための方法で あって、疑似ランダムデータ・ストリーム系列を発生させるステップと、前記デ ータ・ストリーム系列に対して非線形フィードバック変換を行うステップと、前 記データ・ストリーム系列中の値の複数対であって該対の各要素間の系列中にお ける位置の差が各対によって異なるように選択された対の積を前記非線形フィー ドバック変換の値とともに足し合わせることにより、線形形式に対する相関が最 小化された暗号ストリームを発生させるステップと、前記暗号ストリームに基づ いて前記デジタルメッセージの暗号化又は復号化を行うステップと、からなる方 法を提供する。 好ましくは、前記疑似ランダムデータ・ストリーム又はビット・ストリームの 系列は、複数の線形フィードバック・シフトレジスタからの出力を結合すること により生成する。 好ましくは、前記非線形フィードバック変換の値は前記デジタルメッセージと 結合し、完全性関数（integrity function）を前記結合したものに適用して完全 性検査値（ＩＣＶ）を生成する。好ましくは、該完全性検査値を前記デジタルメ ッセージに付加し、それとともに暗号化する。 暗号ストリームを発生させる方法であって、疑似乱数ストリーム系列ｍｊを発 生させるステップと、非線形フィードバック方式により数値ストリーム系列ｓ_j を発生させるステップと、ｃ，ｄをｃ＜ｄ≦ｊなる予め決められた整数とし、ａ_k ，ｂ_kを全てのｅ，ｆε[ｃ，ｄ]に対して（ａ_e−ｂ_e）≠（ａ_f−ｂ_f）なるｊ以 下の整数とした場合での により、出力の暗号ストリーム系列ｚ_jを発生させるステップと、からなる方法 。 逐次暗号化装置であって、使用状態において少なくとも一つの疑似ランダムデ ータ・ストリームを発生させる線形駆動システムと、フィードバック・データ・ ストリームを有し、前記少なくとも一つの疑似ランダムデータ・ストリームに対 して非線形演算を行うことにより暗号ストリームを発生させる非線形結合システ ムと、使用状態においてデジタルメッセージを前記フィードバック・データ・ス トリームと結合し、完全性検査値を発生させるために該結合したものに完全性関 数を適用する完全性システムと、出力システムとからなり、前記完全性検査値を 前記デジタルメッセージに付加し、付加された検査値を前記暗号ストリームを用 いて暗号化するように構成した逐次暗号化装置。 添付図面を参照しながら、例示した本発明の好ましい実施例を以下において詳 細に説明する。この添付図面において、 図１は、暗号ストリーム発生装置のブロック図であり、 図２は、本発明の一実施例による暗号化装置のブロック図であり、 図３は、図２に示された装置の変形例のブロック図である。 まず、図１を参照すると、そこには、通常、線形駆動サブシステム４と非線形 結合サブシステム６とを備える暗号ストリーム発生装置２が示されている。線形 駆動サブシステム４は、予め鍵データｘ_amが格納された複数のｎの線形フィード バック・シフトレジスタ８を備えている。これらのＬＦＳＲ８からの出力は、非 線形結合サブシステム６の非線形処理装置１０によって受け取られる。非線形処 理装置１０は、記憶ビットｓ_jを有するフィードバック・サブシステム１２を備 えている。非線形結合サブシステム６は、暗号ストリームを含むデータ系列ｚ_j を出力する。暗号ストリーム発生装置の動作原理は、秘密鍵データｘ_amが逐次暗 号化装置２に与えられ、暗号ストリーム発生装置２が、ＬＦＳＲ８によって生成 された線形疑似ランダムデータ系列を結合して、それに対して非線形の変換を行 うということであり、暗号ストリームは、暗号化されるべきメッセージと結合す るために１４で示した箇所から出力される。暗号化されたメッセージを受信した 端末にも、暗号ストリームｚ_jと暗号化されたメッセージに関する変換とを利用 してそのメッセージを復号化できるように、暗号ストリーム発生装置２が備わっ ている。下記の式(1)及び(2)は、非線形結合サブシステム６によって実行される 機 能を一般的に定めたものである。 ｚ_j＝ｇ（x_1j，…，x_nj，s_j ¹，…，s_j ^m） in GF(2) （1） ｓ_j+1 ⁱ＝ｆ_i（x_1j，…，x_nj，s_j ¹，…，s_j ^m） in GF(2) （2） ビット・ストリームｚ_j，ｊ＝0,1,2,・・・,は、長さがそれぞれＬ₁,・・・,Ｌ_nであ るＬＦＳＲ８の出力（ｘ_1j,・・・,ｘ_nj）を結合することにより作成される。対応 するＬＦＳＲ８の結合多項式（connection polynomials）は、原始多項式であっ て互いに素次数（prime degree）となるように選ばれる。ｍ個の記憶ビットｓ_j ¹ ，・・・，ｓ_j ^mは、各ＬＦＳＲ８のｊ番目の桁段（phase）をｊ＋１番目の桁段と結 合するために使用される。 １ビットのメモリを有し、ｇがその独立変数の２進数和となるように選ばれた 、システム(1)及び(2)のサブクラスに着目することにより、下記の式(3)及び(4) によって定義されたシステムは、暗号的に健全な逐次暗号を構築する優れたフレ ームワークをもたらす多くの特性を持っていることがわかるであろう。 特に、適切に選ばれた関数ｆに対し、この方式は以下の特性を有する出力スト リームｚを生成することができる。 １／ Ｐの約数であるがおそらくＰである周期で最終的に周期性を有すること。 ここで、 Ｐ＝（２^L1−１）（２^L2−１）…（２^Ln−１） （5） であり、Ｌiはｘ_ijを出力するＬＦＳＲｉの長さである。 ２／ おそらくＰに近いであろう線形の複雑さを有する。 また、（ｘ_r0,ｘ_r1,ｘ_r2,・・・），１＜＝ｒ,＝ｎが独立であって、ランダムな 変数の一様に分布した系列であり、ｓ₀が一様に分布していれば、ｚ_jが次の特性 を有するようになる。 ３／ 以下の点で統計的に均衡がとれている。 prob(ｚ_j＝０)＝prob(z_j＝１)＝１／２ ４／ ｚ_jがｘ_j1,・・・,ｘ_njの如何なる線形形式とも相互に関連しない点で、相関 に対する最大限の免疫性（immunity）がある。 （ｘ_r0,ｘ_r1,ｘ_r2,・・・），１＜＝ｒ＜＝ｎの独立性及び一様性の仮定は、ＬＦ ＳＲの出力として現れたときのそのような仮定と厳格には矛盾がないわけではな いことに注意されたい。例えば、長さＬのＬＦＳＲは極くわずか１に片寄ってい て２^L-1個の１と(２^L-1−１)個の０とを生成する。しかし、この仮定は、もし、 対応する結合多項式が原始多項式であって互いに素次数であれば、また、その出 力の数がその周期よりも非常に少ないＬＦＳＲの挙動に対しては妥当であるよう に思われる。 式(4)から出力系列の線形の複雑さに対する限界を計算することが可能である 。これは、式(4)から同様の入力メモリｍを算出し、式(3)及び(4)のフィードバ ック・システムを入力メモリｍのフィード・フォアード構造に変換することによ り行うことができる。すると、主として、線形の複雑さの上限がＬＦＳＲ８の長 さＬ₁〜Ｌ₂の関数として計算される。 次の結果から、周期的な挙動が出る前の出力系列の最初の部分の項数の上限が 得られる。 ［定理１］式(4)を ｓ_j+1＝ｇ（x_1j，…，x_nj）＋ｓ_jｈ（x_1j，…，x_nj） in GF(2) （4'） という、より明確な形とする。 そして、最初のＭ個の項を無視すると式(1)及び(4')で定義された出力系列ｚ_j は、Ｐ（式(5)参照）の約数を周期とする周期性がある。ここで、 Ｍ＝ｈ（L₁，…，L_n） である。 ［証明］：添付文書を参照されたい。 一般に、式(3)及び(4)で定義されたシステムは、確実性のある予測をするのが 困難な周期を有している。しかし、関数g及びhが退化（degeneracies）（変数ｘ_ij を省略するようなもの）を回避するように選択されると、その周期がちょうど Ｐとなる可能性が極めて高くなる。 逐次暗号化装置の特定の例が、ｆを式(3)及び(4)における独立変数の和の最下 位キャリービットとして定義したいわゆる加算結合器（summation combiner）に よって与えられる。これは、次のように表現することができる。 式(6)及び(7)によって定義されたシステムにより算出された線形の複雑さを下 記のテーブル１に示す。このテーブルの各行は、長さＬ_iの２または３個のＬＦ ＳＲの結合を示している。Ｐの下の対応する数は、出力ストリームｚ_jの周期を 表している。MinCompは、与えられた長さの原始多項式の全ての組み合わせの中 で見られる最低の線形の複雑さを示している。最後に、％の下のデータは、Ｐと MinCompとの間の相違をＰに対する百分率として表している。各レジスタは全て １に初期化され、初期キャリーｓ₀は０に設定されることに注意されたい。式(6) 及び(7)によって定義される特定のシステムは、常に、可能な最大の周期Ｐを有 していることがわかる。 不運なことに、このようなシステムにおけるキャリーｓ_jには片寄りがある。 特に、キャリーは、Ｎが偶数のときは均衡しており、Ｎが奇数のときは片寄って いる。したがって例えば、Ｎ＝３に対する平均では、キャリーの最下位ビットは ２／３の（漸近）確率で１であり、一方、Ｎ＝５に対しては５／９の確率である 。また、このキャリーは同一の出力ディジット（equal output digits）の連な りについても片寄っている。これらの片寄りの効果は、Ｎが大きくなるにしたが って有意ではなくなるが、加算結合器の好ましくない特徴を表している。しかし 、この片寄りは、Ｎ＝２のＬＦＳＲの場合にのみ、その暗号化装置の暗号の強さ に対し重大な脅威となるように思われる。 関数ｆ_s（式(4)参照）の選択に際し、二つの条件を満たすべきである。第１に 、最大に近い線形の複雑さを暗号ストリームに与えるために、この関数は強い非 線形性を有すべきである。第２に、確率が既知の出力ディジットに条件づけられ ているとき、この関数は均衡がとれているべきである。 特に、既知の出力ディジットｚ_jで条件づけられた確率が Ｐｒ（ｓ_j+1＝１｜ｚ_j＝１）＝１／２ Ｐｒ（ｓ_j+1＝１｜ｚ_j＝０）＝１／２ Ｐｒ（ｓ_j+1＝０｜ｚ_j＝１）＝１／２ Ｐｒ（ｓ_j+1＝０｜ｚ_j＝０）＝１／２ のとき、関数ｆ_sは均衡がとれたものとなる。 例えば、 ｆ＝ａ_jｂ_j＋ａ_jｃ_j＋ｂ_jｃ_j＋ａ_jｓ_j＋ｂ_jｓ_j＋ｃ_jｓ_j （8） ｇ＝ａ_jｂ_j＋ａ_jｃ_j＋ｂ_jｃ_j＋ａ_jｂ_j（１＋ｃ_j）（１＋ｓ_j） ＋（１＋ａ_j）（１＋ｂ_j）ｃ_jｓ_j （9） ｋ＝ａ_jｂ_j＋ｂ_jｃ_j＋ｃ_jｓ_j＋（１＋ａ_j）（１＋ｃ_j）（１＋ｓ_j） ＋（１＋ｂ_j）（１＋ｃ_j）（１＋ｓ_j） （10） によって与えられる三つのメモリ関数（memory function）を考える。 ｆ（式(8)参照）はＮ＝３の場合での式(3)の加算結合器に対応することに注意 されたい。下記の表２は、ｆは片寄っており、ｇ及びｋは（全体として及び条件 付きの双方で）均衡がとれていることを示している。 ｇが均衡がとれた関数を規定していることを調べるために、この表の１６個の 横列のうち８個の横列に対してｚ_jが０又は１のいずれかの所定値を有している ことをチェックしてもよい。さらに、これら８個の横列の各集合に対応して、ｇ の下の縦列の値が４回ずつそれぞれ０と１になる。関数ｋについても同様である 。 下記の表３には、線形の複雑さのデータが関数ｇ及びｋに対して示されている （表１と比較されたい）。この表は、これらの関数が小さい原始結合多項式の範 囲に対する可能な最大周期（Max）に接近した周期を有していることを示してい る。これは、確率が既知の出力ディジットに条件づけられているときには、均衡 がとれているだけでなくほぼ最大の線形の複雑さを提供するメモリ関数を見つけ ることができる、ということを示唆している。 式(1)及び(2)で定義される形式の暗号システムの全てが共有する弱点部分は、 ｘ_ijの線形形式に対する出力の相関である。このように、この暗号は、或る線形 形式に対しては相関を有さないという点で相関に対する免疫性があるが、他の線 形形式に対しては相関を有しているに違いない。このような相関は、線形形式の 状態を決定し、それによって暗号を弱めるために利用されるかもしれない。これ は、その線形形式に等価なＬＦＳＲが短いか又は数個の項のみを持っている結合 多項式を有している場合には、特にそうである。 特に、ｘ_1j,ｘ_2j,ｘ_3j,・・・等が独立で一様に分布したランダムな変数の系列で あるとすると、メモリの無い結合器に対し、入力についての或る線形関数の相関 係数の２乗和が常に１である、ということを示すことができる。さらに、１ビッ トのメモリを有する結合器に対しても同様の結果が成立する。特に、式(3)及び( 4)によって定義された如何なる暗号に対しても、ｚ_jは という形式のランダム変数と相関がある。ただし、式(4)が ｓ_j+1＝ｆ（x_1j，…，x_nj）＋ｓ_j （12） という特別の形式である場合を除く。 しかし後者では、メモリの無い結合器によってｚ'_j＝ｚ_j＋ｚ_j-1が生成され、 このため線形形式(11)に対して相関を有し、同様にＬＦＳＲの系列に対しても相 関を有する。攻撃を行う者（攻撃者）はｚ_j＋ｚ_j-1を知ることによってｚ_j-1か らｚ_jを予測できるようになるため、これは暗号ストリームにとって好ましくな い特徴である。次の例は、加算結合器と入力についての線形関数との相関関係を 説明するものである。 ［例］ 式(8)、(9)及び(10)で定義された三つの暗号システムを考えると、表２ より、ａ、ｂ及びｃが独立で一様に分布したランダムな変数の系列であれば、各 システムは、 Prob(ｚ_j＝ａ_j＋ｂ_j＋ｃ_j＋ａ_j-1)＝５／８ を満足していることが容易に証明できる。このように、ｚはａ_j＋ｂ_j＋ｃ_j＋ａ_{j -1} を生成するＬＦＳＲと相関を有する。 任意の数の記憶ビットを有するシステムについて、入力の線形形式と出力系列 との間には相関が存在することも示されている。このように、結合関数において メモリを使用すると、出力系列の線形形式と入力ＬＦＳＲとの間に相関があるた め、暗号に免疫性を与えることができない。この結果を考慮すると、望み得る最 良のことは、既に前述した特性１〜４を維持するだけでなく、線形形式に対する 全ての相関を組織的にかつ効率よく最小化する暗号を設計することである。 本発明の好ましい実施例は、式(3)及び(4)によって定義されたシステムに基づ いており、出力暗号ストリームｚ_jの線形形式と入力項ｘ_lj〜ｘ_njとの間の相関 を一様に小さくする手段を備えている。これを達成するために好ましい実施例は 、以下の式で定義されるような非線形の結合サブシステムを用意している。 （ｘ_r0,ｘ_r1,ｘ_r2,…），１＜＝ｒ＜＝ｎが、ｎ個のＬＦＳＲ８の原始結合多 項式での出力であって互いに素な長さＬｒの出力として線形駆動サブシステム４ から供給されると、上記で論じたように、出力ｚはおそらく以下の特性を有する であろう。 １／ 最終的に周期Ｐでの周期性を有する。ここで、 Ｐ＝（２^L1−１）（２^L2−１）…（２^Ln−１） である。 ２／ Ｐに近い線形の複雑さを有する。 linz_jがｚの各時点（phases）の線形形式によって与えられるとすると、例えば 、 であり、（ｘ_r0,ｘ_r1,ｘ_r2,…），１＜＝ｒ＜＝ｎが独立で一様に分布したラン ダムな変数の系列であってｓ₀は一様に分布していると仮定すると、linz_jは次の 特性を有している。 ３／ 以下の点で統計的に均衡がとれている。 prob(linz_j＝０)＝prob(linz_j＝１)＝１／２ ４／ linz_jがｘ_j1,…,ｘ_njの如何なる線形形式とも相互に関連しない点で、相 関に対する最大限の免疫性がある。 ５／ 入力の線形形式と出力項との間の相関が一様に小さい。特に、linx_jがい ずれかの線形形式(11)であれば、 prob(linx_j＝linz_j)≦１／２＋１／２^k+1 特性３〜５に対する形式的な数学上の証明を以下に行うとする。 以下の事項を得るために、ｚ_jの各積項に現れる最初の項の係数を拡張して（ 式(13)参照）、次の式を得る。 そうすると、ｍ_jが上記の式の右辺に「単独」で現れ、かつｍ_jもｘ_lj,…ｘ_nj のいずれもがその式の残りには現れない上記の形式から、特性３及び４が導かれ る。 特性５：式linz_j＝linx_jはｘ_ijについての任意の線形形式とする。まず第１に 、ｉ＞１に対してｘ_ijを固定値（しかし任意である）とする。また、表記をより 簡単にするためにｘ_ljを単にｘ_jを書く。以下のような新たな変数ｕ₁,ｕ₂,…,ｕ_k 及びｖ₁,ｖ₂,…,ｖ_kを導入する。 ｕ₁＝ｍ_j-1 ｕ₂＝ｍ_j-3 ｕ₃＝ｍ_j-6 ・ ・ ｕ_k＝ｍ_{j-(1/2)k(k+1)} ｖ₁＝ｍ_j-2＋ｗ₁ ｖ₂＝ｍ_j-5＋ｗ₁ｍ_j-2＋ｗ₂ｍ_j-4＋ｗ₃ ｖ₃＝ｍ_j-9＋ｗ₁ｍ_j-4＋ｗ₃ｍ_j-8＋ｗ₄ｍ_j-5＋ｗ₅ｍ_j-7+ｗ₆ ・ ・ ｖ_k＝ｍ_{j-(1/2)k(k+3)}＋…＋ｗ_(1/2)k(k+1)（上記のように） さらに、j-1,j-3,j-6,…,j-(1/2)k(k+1)又はj-2,j-5,j-9,j-(1/2)k(k+3)のう ちのいずれでもないｉに対してｘ_iを固定値とする。そのとき上記より、或るブ ール定数（boolean constants）ａ₁,ａ₂,…,ａ_k及びb₁,ｂ₂,…,ｂ_kに対して次式 が得られる。 ｕ₁＝ｘ_j-1＋ａ₁， ｖ₁＝ｘ_j-2＋ｂ₁， ｕ₂＝ｘ_j-3＋ａ₂， ｖ₂＝ｘ_j-5＋ｗ₁ｘ_j-2＋ｂ₂， ｕ₃＝ｘ_j-6＋ａ₃， ｖ₃＝ｘ_j-9＋ｗ₄ｘ_j-5＋ｂ₃， ・ ・ ｕ_k＝ｘ_{j-(1/2)k(k+1)}＋ａ_k， ｖ_k＝ｘ_{j-(1/2)k(k+3)}＋…＋ｂ_k， ここで、固定値ではない各ｘ_jの項は、ｕ_j及びｖ_jについての線形形式として表 現することができる。例えば、 ｘ_j-2＝ｖ₁＋ｂ₁ ｘ_j-5＝ｖ₂＋ｗ₁(ｖ₁＋ｂ₁)＋ｂ₂＝ｖ₂＋ｗ₁ｖ₁＋(ｗ₁ｂ₁＋ｂ₂) ｘ_j-9＝ｖ₃＋ｗ₄(ｖ₂＋ｗ₁(ｖ₁＋ｂ₁)＋ｂ₂)＋ｂ₃ ＝ｖ₃＋ｗ₄ｖ₂＋ｗ₄ｗ₁ｖ₁＋(ｗ₄ｗ₁ｂ₁＋ｗ₄ｂ₂＋ｂ₃) 等である。 いま、linz_jの拡張から、項ｍ_j-1,ｍ_j-3,…,ｍ_{j-(1/2)k(k+1)}は示されている ようにのみ現れることに注意されたい。さらに、残余項におけるｓの項は、全て j-(1/2)k(k＋1)よりも小さい添字を持っている。したがって、式linz_j＝linx_jは 、ｍ及びｘの項に代入した後は、 ｕ₁ｖ₁＋ｕ₂ｖ₂＋…＋ｕ_kｖ_k＋ｆ（ｖ₁,ｖ₂,…,ｖ_k) ＝lin(ｕ₁,ｕ₂,…,ｕ_k,ｖ₁,ｖ₂,…,ｖ_k) となる。ここで、lin()は或る線形形式であり、ｆはｖ₁,ｖ₂,…,ｖ_kの或る関数 である。ベント関数（Bent functions）についての標準的な結果（standard res ults）より（メイアー（W．Meier）及びスタフェルバーク（O．Staffelbach）に よる「Correlation properties of Combiners with memory in stream ciphers （逐次暗号におけるメモリを有する結合器の相関特性）」,Journal of Crypto1o gy，Vol.4，No．5(1992)，pp.67-86を参照されたい）、この式が成立する確率は 高々 １／２＋１／２^k+1である。この結果は固定された全ての変数の組み合わ せに対して該当するため、これは全体としても該当するにちがいない。 ストリーム暗号発生装置２の暗号生成速度は、また、１サイクル当たり１ビッ トの割合の従来の出力よりも改善することができる。出力が１サイクル当たり１ ワード（例えば３２ビット）の割合で生成されれば、暗号化を行うことができる 速度が３２倍増大する。これを達成するために、各セルの変数が１ビットではな く１ワードであって、式(13)、(14)及び(15)におけるＧＦ(2)上の加算及び乗算 がワード間でビット毎に行われるように、ストリーム暗号発生装置２を修正する ことができる。この効果は、３２個の暗号化装置を並列に動作させて出力をまと めた場合と同一である。したがって、各出力ワードのｎ番目のビットは、１度に １ビットを操作する同様の暗号化装置の出力に相当する。これらのビット暗号化 装置のそれぞれは、構造において同一であり、ＬＦＳＲの初期ベクトルにおいて のみ相違する。各LＦＳＲの初期ベクトルを注意深く選択することにより、その 出力をサイクル当たり１ビットの所与の暗号化装置の全期間の出力に一致させる ことができる。ただし、出力ビットが簡単な方法で並べ替えられていることが唯 一の相違点である。この利点は、サイクル当たり１ワードの暗号化装置は１／３ ２のサイクル数で出力を生成できることである。 ブロック暗号に比べ、逐次暗号では、完全性を付与する確立された動作モード は存在しない。しかし、本発明の実施例に係る逐次暗号は、完全性検査値（ＩＣ Ｖ）を提供するメッセージ認証コード（ＭＡＣ）の実用に利用することができる 。 図２は、完全性検査機構の第１例を含む本発明の好ましい実施例のブロック図 を示している。特に、そこでは、既に説明され図１に示された暗号ストリーム発 生装置２を備えるメッセージ暗号化システム２０が示されている。暗号化システ ム２０は、また、完全性検査値発生器１８、暗号化処理装置２６、及び平文テキ スト・メッセージ源２２を有している。平文テキスト・メッセージ・データは、 完全性検査値発生器１８によってメッセージ源２２から受け取られる。完全性検 査値発生器１８では、メッセージ・データ・ストリームが非線形処理装置１０か らのメモリ・データ・ストリームと結合される。その後、完全性検査値（ＩＣＶ ）を得るために、結合されたストリームに完全性関数（integrity function）が 適用される。このＩＣＶは、暗号化処理装置２６に転送され、そこで、メッセー ジ源２２から暗号化処理装置２６へ更に転送された平文テキスト・メッセージの 終端に、メッセージ認証コードとして付け加えられる。このメッセージとＭＡＣ は、その後、出力１４からの暗号ストリームと結合されることにより暗号化され 、暗号化されたメッセージはライン３０に出力される。 図２の、完全性及び暗号化のシステムである１８及び２６の第１例を以下に説 明する。 上記で説明されたようにして実現された逐次暗号化装置２により、３２ビット ・ワードが各サイクル毎に生成される。メッセージＭがｋ個のワードＭ₁,Ｍ₂,Ｍ₃ ,…,Ｍ_qから構成されるものとする。完全性関数は、暗号（ｓ_j,ｓ_j+1,ｓ_j+2,… ）によって生成される記憶ビットが組み込まれたものである。メッセージＭに対 して暗号化を行い完全性を付与することに関わるステップの概要が以下で説明さ れる。そこでは、記号"^"はビット毎の排他的論理和を表し、”ｃ＜＜ｒ”はｒ ビットだけ巡回的にシフトさせたワードｃを表す。また、逐次暗号化装置がｊサ イクルだけ終了して状態ｊになっているものと仮定する。 ［ステップ１］：必要ならば、メッセージ・ストリームが少なくとも１６ワー ドを含むように、”ゼロ”のワードをメッセージ・ストリームに詰める。このよ う にして、メッセージ・ストリームはＭ₁,Ｍ₂,Ｍ₃,…Ｍ_qとなる。ただし、ｑ＞＝ １６である。 ［ステップ２］：暗号化装置をｑ＋１サイクルだけ動作させ、出力ｚ_j+1,ｚ_{j+ 2} ,…ｚ_j+q+1及びメモリ・ワードｓ_j+1,ｓ_j+2,…ｓ_j+qを記憶する。 ［ステップ３］：次のようになるようにメモリ・ストリームにメッセージ・ス トリームを加える。 Ｍ'_n＝Ｍ_n＾ｓ_j+n ただし、ｎ＝１,…,ｑ ［ステップ４］：最初の１６ワードを２回繰り返すことにより３２個の余分な ワードを新しいメッセージに詰める。したがって、 Ｍ'_q+16+n＝Ｍ'_q+n＝Ｍ'_n ただし、ｎ＝１…１６ である。 ［ステップ５］：２個のシフト配列shift1及びshift2を以下のように定義する 。 shift1[i]=i＋1 ただし、ｉ＝0,…,30 shift1[31]=1 shift2[i]=(i＋1)*11(mod32) ただし、i=0,…,30 shift2[31]=11 shift2の定義において、３２に対して互いに素な１と３０の間のいずれの数を １１の代わりに選んでもよいことに注意されたい。 ［ステップ６］：以下のように二つのラウンドにおいて完全性関数を適用する 。 a=0； b=0； c=0； d=0； icv=0； ラウンド１： i=1； while(i<=q+32)｛ a=d^((M'_i^(b&c))<<shft1[i&31])； x[i]=a； i=i＋1； b=a^((M'i^(c&d))<<shft1[i&31])； x[i]=b； i=i＋1； c=b^((M'_i^(d&a))<<shft1[i&31])； x[i]=c； i=i+1； d=c^((M'_i^(a&b))<<shft1[i&31])； x[i]=d； i=i+1； icv=icv^d； ｝ ラウンド２： i=1； while(i<=q+32)｛ a=d^((x[i]^M'_i^(b&c))<<shft2[i&31])； i=i+1； b=a^((x[i]^M'_i^(c&d))<<shft2[i&31])； i=i+1； c=b^((x[i]^M'_i^(d&a))<<shft2[i&31])； i=i+1； d=c^((x[i]^M'_i^(a&b))<<shft2[i&31])； i=i+1； icv=icv^d； ｝ ［ステップ７］：M_q+1＝icvとおくことにより元のメッセージＭにicvを加える 。 ［ステップ８］：暗号ストリームを下記のようになるように加えることにより そのメッセージを暗号化する。 Encrypt(M)=M₁^z_j+1,M₂^ｚ_j+2,…,M_q+1^z_j+q+1 完全性及び暗号化のシステム１８及び２６の変形例を以下においてアルゴリズ ムの形式で説明するとともに、図３においてブロック図として示す。この例にお いて、前述の例のためになされたものと同じ仮定が適用されるが、フィードバッ ク・ストリーム（ｓ_j,ｓ_j+1,ｓ_j+2…）に代えて記憶ビット（式(13)及び(14)参 照）が完全性関数に組み込まれる。 ［ステップ１］：必要ならば、１６ワードの整数倍を含むように、ゼロのワー ドをメッセージ・ストリームに詰める。このようにして、メッセージ・ストリー ムはＭ₁,Ｍ₂,Ｍ₃,…,Ｍ_nとなる。ただし、ｎ＝１６ｔ、ｔはｔ＞０なる整数であ る。 ［ステップ２］：暗号化装置をｎ＋１サイクルだけ動作させ、出力ｚ_j+1,ｚ_{j+ 2} ,…ｚ_j+n+1及びメモリ・ワード・ストリームｍ＝ｍ_j,ｍ_j+1,ｍ_j+2,…,ｍ_j+nを 記憶する。 ［ステップ３］：次のようになるようにメモリ・ストリームにメッセージ・ス トリームを加える。 Ｍ'_n＝Ｍ_n^ｍ_j+r ただし、ｒ＝１，…，ｎ ［ステップ４］：以下のように三つのラウンドにおいて完全性関数を適用する 。 icv=0； for(j=0 to t-1)｛ a=0； b=0； c=0； d=0； ラウンド１： i=1； while(i<=16)｛ a=d^((M'_16j+i^(b&c)^(~b&d))<<7)； i=i+1； b=a^((M'_16j+i^(c&d)^(~c&a))<<12)； i=i+1； c=b^((M'_16j+i^(d&a)^(~d&b))<<17)； i=i+1； d=c^((M'_16j+i^(a&b)^(~a&c))<<22)； i=i+1； ｝ ラウンド２： i=1； while(i<=16)｛ a=d^((M'_16j+i^(b&c)^(~b&d))<<5)； i=i+1； b=a^((M'_16j+i^(c_&d)^(~c&a))<<9)； i=i+1； c=b^((M'_16j+i^(d&a)^(~d&b))<<14)； i=i+1； d=c^((M'_16j+i^(a&b)^(~a&c))<<20)； i=i+1； ｝ ラウンド３： i=1； while(i<=16)｛ a=d^((M'_16j+i^(b&c)^(~b&d))<<4)； i=i+1； b=a^((M'_16j+i^(c&d)^(~c&a))<<11)； i=i+1； c=b^((M'_16j+i^(d&a)^(~d&b))<<16)； i=i+1； d=c^((M_'16j+i^(a&b)^(~a&c))<<23)； i=i+1； ｝ icv=icv^d； ｝ ［ステップ５］：Ｍ_n+1＝icvとおくことにより元のメッセージＭにicvを加え る。 ［ステップ６］：下記のようにしてそのメッセージを暗号化する。 Encrypt(M)=M₁^z_j+1,M₂^ｚ_j+2,…,M_n+1^ｚ_j+n+1 暗号化を伴わない完全性が必要とされる場合は、ステップ６においてＭ_n+1の みを暗号化することを除いて全く同じ手順を使用する。さらに、ステップ４の三 つのラウンドで利用される数列（7,12,17,22,5,…,23）は自由に選ばれたもので あるが、この数列は優れた完全性検査効果を生じることが実験的に示されている 。 上記で説明された完全性の機構は、どの二つのメッセージについても、ランダ ムなｊ（逐次暗号の位置）に対してicv（Ｍ）＝icv（Ｍ'）となる確率が１／２^w に近いという意味で理想的である。ただし、ｗはワードのサイズである。いわゆ る「誕生日攻撃（Birthday Attack）」（この攻撃では、或るメッセージに代え て同じicvを有する他のメッセージが用いられる）は完全性関数に対しては用い ることができない。この関数は逐次暗号化装置の状態とともに変化するからであ る。これは従来のメッセージ認証コードではそのようにならないことに注意され たい。 従来のメッセージ認証コードの弱点を強調するために、固定された鍵ｋがメッ セージ認証コード関数Macとともに使用されるものと仮定する。攻撃者は、送信 者Ｓと受信者Ｒとの間の通信線に侵入する。さらに、攻撃者は特定のメッセージ Ｍの内容を知っているものと仮定する。このとき、攻撃者がMacを獲得すること ができれば、Ｍ及びMac_k（Ｍ）を用いてMac鍵ｋを算出することができるかもし れない。彼は、彼自身のメッセージＭ'とMac（Ｍ'）を作成し、これを正当な送 信者Ｓから来たかのように受信者Ｒに送るかもしれない。たとえそのメッセージ ・ストリームが逐次暗号化装置によって暗号化されていても、攻撃者は次のよう にして攻撃をすることができる。Ｍ’及びMac（Ｍ’）の算出後、攻撃者は、後 続のメッセージＭ''の内容がわかると確信するまで待機する。その後、Ｍ''＋Ｍ 'をそのメッセージ.ストリームに加え、かつそのメッセージ。ストリーム中のMa cにMac_k（Ｍ'）を加えることにより、Ｍ''をＭ'で置き換える。 しかし、本完全性システム（integrity system）には、上記の種類の攻撃が効 果を発揮できない大きな理由がある。鍵ｋの長さは少なくとも５１２ビット長で あり、一方、icvは３２ビット長にすぎない。したがって、たとえMac関数が容易 に逆算できるものであっても、攻撃者がM及びMac_k（Ｍ）から正しいｋを算出で きる可能性は、２⁴⁸⁰（＞１０¹⁴⁴）回に１回程度にすぎない。このため、Ｍ及び Mac_k（Ｍ）からは、ｋについての無視できるような量の情報のみが得られるだけ である。攻撃者がＭからｚ_jを算出し、それによってｍ_iを見つけるかもしれない という主張がなされるかもしれないが、ｚ_jとｍ_jとの相関は低いため、このよう な攻撃は非現実的である。 第２に、Mac鍵ｋは暗号ストリーム発生装置の状態とともに絶えず変化してい るため、攻撃者は後のどの時点においてもメッセージＭ及び正しいicvを挿入す ることはできない。したがって、たとえ、攻撃者がＭ及びMac_k（Ｍ）を獲得し、 他のメッセージＭ'に対するＭ'及びMac_k（Ｍ'）を算出することができたとして も、彼は、実際の通信の流れの中で、ＭからＭ'への置き換えとMac_k（Ｍ）からM ac_k（Ｍ'）への置き換えと達成するために、このような計算を十分に速く行わな ければならない。 以上の詳細な記述は、説明のためにのみなされたものであり、この書面に添付 される請求の範囲において定義される発明を限定をすることを意図するものでは ない。 添付文書 ［定理の証明］ 証明の説明を簡単にするために、以下の表記を用いる。 ｇ^j＝ｇ（ｘ_lj,…,ｘ_nj） ｈ^j＝ｈ（ｘ_lj,…,ｘ_nj） 式（4'）から（3）への代入を続けることにより、 ｚ_jsum^j＋ｓ^j ＝sum^j＋ｇ^j-1＋ｈ^j-1ｓ_j-1 ＝sum^j＋ｇ^j-1＋ｈ^jー1（g^j-2＋ｈ^j-2ｓ_j-2） ＝sum^j＋g^j-1＋ｈ^j-1（g^j-2＋ｈ^j-2(g^j-3＋ｈ^j-3ｓ_j-3)） ……など となる。 いま、系列ｈ_jはＭ＝ｈ（Ｌ₁,…,Ｌ_n）という線形の複雑さを有しているため 、系列ｈ^jの高々Ｍ個の連続した値は１となり得る。ｊが少なくともＭ＋１であ れば、 ｚ_j=sum^j＋ｇ^j-1＋ｈ^j-1（g^j-2＋…＋ｈ^j-M(g^j-M-1)…） となる。このため、或る関数F及び少なくともＭ＋１であるｊに対して ｚ_j＝Ｆ（xik,ｉ＝１，２,…,ｎ,ｋ＝ｊ，ｊ−１,…,ｊ−Ｍ−１） となる。ＬＦＳＲの性質より、いずれの項xikも、ｘim，ｍ＝ｋ＋１,ｋ＋２,…, ｋ＋Ｌ_iの関数として表現できる。したがって、ｊが少なくともＭ＋１であれば 、或る関数Ｆ'に対して ｚ_j＝Ｆ'（xik_i,ｉ＝１,２,…,ｎ,ｋ_i＝ｊ,ｊ−１,…,ｊ=Ｌ_i） となる。いま、少なくともＭ＋１であるｊに対して、Ｆ'における２進数の変数 のベクトルは周期Ｐで同じ値を有している。ｚjは少なくともＭ＋１であるｊに 対してＰの約数である周期を有していることになる。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，Ｍ Ｃ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ，ＣＧ ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ，ＳＮ， ＴＤ，ＴＧ)，ＡＴ，ＡＵ，ＢＢ，ＢＧ，ＢＲ，ＢＹ， ＣＡ，ＣＨ，ＣＺ，ＤＥ，ＤＫ，ＥＳ，ＦＩ，ＧＢ，Ｈ Ｕ，ＪＰ，ＫＰ，ＫＲ，ＫＺ，ＬＫ，ＬＵ，ＬＶ，ＭＧ ，ＭＮ，ＭＷ，ＮＬ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ， ＲＵ，ＳＤ，ＳＥ，ＳＫ，ＵＡ，ＵＳ，ＵＺ，ＶＮ

Claims (1)

1. 【特許請求の範囲】 １．暗号ストリームを発生させるためのデジタルデータ・ストリーム発生装置に おいて、少なくとも一つの疑似ランダムデータ・ストリームを生成するフィード バック・シフトレジスタ構造体と、前記少なくとも一つのデータ・ストリームか ら暗号ストリームを生成する処理構造体であって、少なくとも一つのデータ・ス トリームの先行する複数の値から導出される結合値の系列を記憶する手段、及び 、前記結合値の複数対について、各対の結合値間の系列中の位置の差が異なるよ うに乗算し、該乗算された複数対を加算することにより前記暗号ストリームを生 成する処理手段を有する処理構造体と、を備えるデジタルデータ・ストリーム装 置。 ２．請求項１に記載のデジタルデータ・ストリーム発生装置において、前記処理 構造体は、記憶値の系列を前記少なくとも一つのデータ・ストリームの値と少な くとも一つの前の記憶値とから生成するための非線形フィードバック・システム を有し、該記憶値の少なくとも一つは前記暗号ストリームを生成するために前記 乗算された複数対と足し合わされるデジタルデータ・ストリーム発生装置。 ３．請求項１に記載のデジタルデータ・ストリーム発生装置において、前記フィ ードバック・シフトレジスタ構造体は、複数のｎの線形フィードバック・シフト レジスタを有し、各シフトレジスタは疑似ランダムデータ・ストリームを前記非 線形結合構造体に渡すデジタルデータ・ストリーム発生装置。 ４．請求項２に記載のデジタルデータ・ストリーム発生装置において、前記非線 形フィードバック・システムは、前記少なくとも一つのデータ・ストリームの値 と少なくとも一つの前の記憶値とに非線形関数を適用することにより記憶値を発 生させるデジタルデータ・ストリーム発生装置。 ５．請求項４に記載のデジタルデータ・ストリーム発生装置において、前記結合 値の各値は、前記少なくとも一つのデータ・ストリームからの値を足し合わせる ことにより導出されるデジタルデータ・ストリーム発生装置。 ６．請求項５に記載のデジタルデータ・ストリーム発生装置において、前記フィ ードバック・シフトレジスタ構造体は、ビットストリームｘ_1j・・・ｘ_njを生成す る ｎの線形フィードバック.シフトレジスタを有し、前記フィードバック・システ ムは、ｆを非線形関数とした場合でのｓ_j+1＝ｆ(ｘ_1j,・・・,ｘ_nj,ｓ_j)により記憶 ビットｓ_jの系列を生成するデジタルデータ・ストリーム発生装置。 ７．請求項６に記載のデジタルデータ・ストリーム発生装置において、前記結合 値は、 により作成されるデジタルデータ・ストリーム発生装置。 ８．請求項７に記載のデジタルデータ・ストリーム発生装置において、前記暗号 ストリームｚ_jは、ｋを１よりも大きい整数とした場合での により生成されるデジタルデータ・ストリーム発生装置。 ９．暗号ストリームを発生させるためのデジタルデータ発生装置において、少な くとも一つの線形フィードバック・シフトレジスタ（ＬＦＳＲ）と、前記少なく とも一つのＬＦＳＲの出力の総和の系列を生成するための加算手段と、非線形値 の系列を前記少なくとも一つのＬＦＳＲの出力と前記非線形出力値の系列の少な くとも一つの前の値とにより生成するための非線形フィードバック処理手段と、 前記総和の系列の複数対と前記非線形値の系列の少なくとも一つとを利用してベ ント関数によりデータ・ストリームを発生させるための出力処理手段とを備え、 各対の要素の系列中の位置の差が各対によって異なっているデジタルデータ発生 装置。 １０．デジタルメッセージの暗号化又は復号化を行うためのシステムにおいて、 疑似ランダムデータ系列を発生させるための線形駆動サブシステムと、前記疑似 ランダムデータ系列から暗号ストリームを生成するための非線形フィードバック ・サブシステムと、メッセージを前記暗号ストリームと結合することにより該メ ッセージの暗号化又は復号化を行うための暗号化処理装置とを備え、前記非線形 フィードバック・サブシステムが、フィードバック系列を、前記疑似ランダムデ ータ系列のうちの少なくとも一つの値と前記フィードバック系列のうちの少なく とも一つの前の値とに非線形関数を適用することにより発生させるための非線形 フィ ードバック処理手段と、前記疑似ランダムデータ系列中の値の複数対であって該 対の各要素間の系列中における位置の差が各対によって異なるように選択された 対の積を前記フィードバック系列のうちの一つの値とともに足し合わせることに より前記暗号ストリームを発生させるための暗号ストリーム発生器と、を有して なるシステム。 １１．請求項１０に記載のシステムにおいて、前記線形駆動サブシステムは、秘 密鍵データを予め格納している複数個の線形フィードバック・シフトレジスタで あって、前記疑似ランダムデータ系列を供給するために結合される別個のデータ 系列を発生させる線形フィードバック・シフトレジスタを有するシステム。 １２．請求項１１に記載のシステムであって、前記非線形フィードバック処理手 段は、使用状態において、前記フィードバック系列の以前の値とともに前記別個 のデータ系列からの値に前記非線形関数を適用することにより前記フィードバッ ク系列を発生させるシステム。 １３．請求項１２に記載のシステムであって、前記暗号化処置装置は、前記暗号 ストリームとともに前記メッセージ・ストリームに対しビット毎の排他的論理和 の演算を行うことにより平文テキスト・メッセージを暗号化するシステム。 １４．請求項１２に記載のシステムであって、前記暗号化処置装置は、前記暗号 ストリームとともに暗号化メッセージ・ストリームに対しビット毎の排他的論理 和の演算を行うことにより前記暗号化メッセージ・ストリームを復号化するシス テム。 １５．請求項１０乃至１４のいずれか一の請求項に記載のシステムであって、前 記フィードバック系列からの値を前記メッセージ・ストリームに結合してそれに 完全性関数を適用することにより平文テキスト・メッセージから完全性検査値を 発生させるための完全性検査サブシステムを更に備えるシステム。 １６．暗号ストリームを発生させるための方法において、疑似ランダムデータ・ ストリーム系列を発生させるステップと、前記データ・ストリーム系列中の値の 複数対であって該対の各要素間の系列中における位置の差が各対によって異なる ように選択された対の積を前記データ・ストリーム系列からの値の非線形フィー ドバック関数より導出される値とともに足し合わせることにより、暗号ストリー ムを発生させるステップと、を備える方法。 １７．請求項１６に記載の方法であって、前記疑似ランダムデータ・ストリーム 系列は、複数の線形フィードバック・シフトレジスタからの別個のデータ系列の 出力を足し合わせることにより生成される方法。 １８．請求項１７に記載の方法であって、前記非線形フィードバック関数は前記 別個のデータ系列の出力からの値に作用する方法。 １９．請求項１８に記載の方法において、前記別個のデータ系列の出力値はワー ドであって前記加算及び乗算がワード間でビット毎に行われる方法。 ２０．請求項１８に記載の方法において、前記疑似ランダムデータ系列ｍ_jは、 によりｎ個の前記別個のデータ系列の出力ｘ_ijから作成され、前記暗号ストリー ムｚ_jは、ｋを１よりも大きい整数とし、ｓ_jを前記非線形フィードバック関数ｆ の値であって ｓ_j+1＝ｆ（x_1j，…，x_nj，s_j） とした場合での により生成される方法。 ２１．請求項１６乃至２０のいずれか一の請求項に記載の方法であって、暗号化 されたメッセージストリームを生成するために平文テキスト・メッセージ・スト リームに前記暗号ストリームを加えるステップを含む方法。 ２２．請求項１６乃至２０のいずれか一の請求項に記載の方法であって、復号化 された平文テキスト・メッセージ・ストリームを得るために暗号化されたメッセ ージ・ストリームに前記暗号ストリームを加えるステップを含む方法。 ２３．請求項２１に記載の方法であって、前記非線形フィードバック関数より導 出される値を前記平文テキスト・メッセージ・ストリームと結合し、完全性検査 値を得るために該結合したものに完全性関数を適用するステップを含む方法。 ２４．請求項２３に記載の方法であって、前記平文テキスト・メッセージ・スト リームに前記暗号ストリームを加える前に前記平文テキスト・メッセージに完全 性検査値を付加するステップを含む方法。 ２５．請求項２２に記載の方法であって、前記非線形フィードバック関数により 導出される値を前記復号化された平文テキスト・メッセージ・ストリームと結合 し、完全性検査値を得るために該結合したものに完全性関数を適用するステップ を含む方法。 ２６．請求項２５に記載の方法であって、前記復号化された平文テキスト・メッ セージの完全性を判定するために、前記平文テキスト・メッセージ・ストリーム から得られた完全性検査値を前記平文テキスト・メッセージ・ストリームに付加 された値と比較するステップを含む方法。 ２７．デジタルメッセージを暗号化する方法において、疑似ランダムデータ・ス トリーム系列を発生させるステップと、前記データ・ストリーム系列に対して非 線形フィードバック変換を行うステップと、前記データ・ストリーム系列中の値 の複数対であって該対の各要素間の系列中における位置の差が各対によって異な るように選択された対の積を前記非線形フィードバック変換の値とともに足し合 わせることにより、線形形式に対する相関が最小化された暗号ストリームを発生 させるステップと、前記暗号ストリームに基づいて前記デジタルメッセージを暗 号化するステップと、を備える方法。 ２８．デジタルメッセージを暗号化する方法において、疑似ランダムデータ・ス トリーム系列を発生させるステップと、前記データ・ストリーム系列に対して非 線形フィードバック変換を行うステップと、前記データ・ストリーム系列中の値 の複数対であって該対の各要素間の系列中における位置の差が各対によって異な るように選択された対の積を前記非線形フィードバック変換の値に基づく関数と ともに足し合わせることにより、線形形式に対する相関が最小化された暗号スト リームを発生させるステップと、前記暗号ストリームに基づいて前記デジタルメ ッセージを復号化するステップと、を備える方法。 ２９．請求項２７又は２８に記載の方法であって、前記疑似ランダムデータ・ス トリーム系列は、複数の線形フィードバック・シフトレジスタからの出力を結合 することにより生成される方法。 ３０．請求項２７に記載の方法であって、前記非線形フィードバック変換により 導出された値は前記デジタルメッセージと結合され、前記デジタルメッセージを 暗号化する前に前記デジタルメッセージに付加される完全性検査値を生成するた めに前記結合されたものに完全性関数が適用される方法。 ３１．請求項２７に記載の方法であって、前記疑似ランダムデータ・ストリーム 系列中の値は前記デジタルメッセージと結合され、前記デジタルメッセージを暗 号化する前に前記デジタルメッセージに付加される完全性検査値を生成するため に前記結合されたものに完全性関数が適用される方法。 ３２．デジタル処理装置を利用して暗号ストリームを発生させる方法において、 疑似乱数ストリーム系列ｍｊを発生させるステップと、非線形フィードバック方 式により数値ストリーム系列ｓ_jを発生させるステップと、ｃ，ｄをｃ＜ｄ≦ｊ なる予め決められた整数とし、ａ_k，ｂ_kを全てのｅ，ｆε[ｃ，ｄ]に対して(ａ_e −ｂ_e)≠(ａ_f−ｂ_f)なるｊ以下の整数とした場合での により、出力の暗号ストリーム系列ｚ_jを発生させるステップと、を備える方法 。 ３３．逐次暗号化装置であって、使用状態において少なくとも一つの疑似ランダ ムデータ・ストリームを発生させる線形駆動システムと、フィードバック・デー タ・ストリームを有し、前記少なくとも一つの疑似ランダムデータ・ストリーム に対して非線形演算を行うことにより暗号ストリームを発生させる非線形結合シ ステムと、使用状態においてデジタルメッセージを前記フィードバック・データ ・ストリームと結合し、完全性検査値を発生させるために該結合したものに完全 性関数を適用する完全性システムと、出力システムとを備え、前記完全性検査値 を前記デジタルメッセージに付加し、付加された検査値を前記暗号ストリームを 用いて暗号化するように構成した逐次暗号化装置。