JPH02217037A - 符号変換装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、暗号通信系で利用される符号変換装置、すな
わち乱数発生装置に関するものである。

〔従来の技術〕

情報化社会の進展に伴い、情報セキュリティを確保する
ための手段の一つである暗号化技術が急速に脚光を浴び
ており、これに応じて研究・開発活動が活発に進められ
ている。

暗号化方式は、ストリーム暗号とブロック暗号とに大別
されるが、特にストリーム暗号化方式の場合は、大量・
高速データのリアルタイム処理に適していることから、
現在はストリーム暗号化方式がその主流となっている。

ストリーム暗号化方式には、符号変換装置、すなわちキ
ーストリーム発生装置（乱数発生装置）が不可欠である
が、この符号変換装置によって発生される系列（キース
トリーム）は、■その一部から全体が解明されないこと
、すなわち難解性が高いこと、■長い周期を持つこと、
■統計的にランダムであること、■容易に発生でき、実
用性が高いこと、等が要求されている。

このストリーム暗号化方式の符号変換装置として従来量
も一般的に使用されているのは、例えば特公昭５０−２
２３６３号公報に示されているｎ段の線形フィードバッ
ク・シフトレジスタを利用したものである。この線形フ
ィードバック・シフトレジスタを利用した符号変換装置
は、通信文を線形フィードバック・シフトレジスタから
出力されるキーストリームに従って符号変換し、これを
信号として出力する。

〔発明が解決しようとする課題〕

上記した従来技術は、確かに発生される系列に対する要
求事項の内の■、■、■を満足することができるのであ
るが、現在では、暗号通信において最も要求度の高い要
求事項の■を充分に満たしているとは言い難いと云う問
題がある。

すなわち、段数が１桁の線形フィードバック・シフトレ
ジスタの場合、２ｎ−１ビツトのデータで秘密のパラメ
ータ（フィードバック係数および初期値）が解明され、
全キーストリームが再現されてしまう。

そこで、本発明は、上記した従来技術における問題点を
解消すべく創案されたもので、線形フィードバック・シ
フトレジスタを利用した符号変換装置における利点、す
なわち要求事項の■、■、■を満たすと云う利点を維持
したまま、要求事項の■を充分に満たすことを目的とす
る。

〔課題を解決するための手段〕

上記目的を達成するための本発明の手段は、暗号通信系
に使用されるストリーム暗号化方式の符号変換装置であ
ること、 ｎ段のシフトレジスタにＭ系列フィードバック結合回路
を組付けたｎ段の線形フィードバック・シフトレジスタ
を有すること、 この線形フィードバック・シフトレジスタからの対応す
るビット数の出力系列を入力し、この入力した出力系列
をロジックに従い同じビット数だけ非線形化してスタッ
ク・ロジック系列として出力するスタック・ロジック回
路を有すること、にある。

本発明の符号変換装置において、線形フィードバック・
シフトレジスタおよびスタック・ロジック回路の実際に
使用するビット数およびタップル数は特に限定されるこ
とはないのであるが、高い難解性を維持したままより大
量・高速データのリアルタイム処理を達成したい場合に
は、ビット数を大きく設定すると共に、タップル数を小
さく設定するのが良い。

〔作用および実施例〕

以下、本発明の作用を、本発明の実施例を示す図面を参
照しながら説明する。

第１図は、本発明装置の最も基本的な構成例を示すもの
で、ｎ段のシフトレジスタ２にＭ系列フィードバック結
合回路３を組付けて従来周知の線形フィードバック・シ
フトレジスタｌを構成し、この線形フィードバック・シ
フトレジスタ１の出力端子を出力ビツトラインＬ１を介
してスタック・ロジック回路４の入力端子に接続してい
る。この線形フィードバック・シフトレジスタ１とスタ
ック・ロジック回路４とは、別のビット設定ラインＬ２
により接続されていて、線形フィードバック・シフトレ
ジスタ１とスタック・ロジック回路４との使用されるビ
ット数が常に一致するようにしている。

このように、本発明による符号変換装置は、従来装置の
ように線形フィードバック・シフトレジスタ１をその主
要構成部分としているので、この線形フィードバック・
シフトレジスタ１が発揮する優れた作用、すなわち要求
事項の■、■、■を充分に満たすと云う作用効果を発揮
することは明らかであるので、本発明装置が発生する系
列、すなわちスタック・ロジック回路４の出力端子に接
続されたスタック・ロジック系列出力ラインＬ３に出力
されるスタック・ロジック系列の難解性の判断基準であ
る線形複雑度を説明する。

ｎ段線形フィードバック、シフトレジスタ１の内部状態
を（×１．・・・、Ｘｌ、・・・、ｘ７）で表す。

線形フィードバック、シフトレジスタ１の次の状態は（
Ｘｚ、　−、Ｘ−＋、−，Ｘ、　、Ｘ、、＋　）　ニ遷
移するが、その間には、 ｘ−−＋　＝１．　Ｃ，ｘ、−＋−ｔ　　　　・・・（
ｌ）なる線形再帰関係がある。

第１図に示すように、スタック・ロジック回路４を制御
する線形フィードバック・シフトレジスタ１の桁をｍ（
２≦ｍ≦ｎ）とすると、Ｘｌの値によりスタック・ロジ
ック回路４は、第２図に示すように、線形フィードバッ
ク・シフトレジスタ１から相応するビット数の系列（シ
フトレジスフ出力ｄビット）を入力し、ロジックに従っ
て同じビット数でシフトレジスタ出力ｄビットの順序を
逆転しただけの出力ｄビットであるスタック・ロジック
系列を出力する。このように、線形フィードバック・シ
フトレジスタ１から出力されて一定の線形を有する系列
は、スタック・ロジック回路４によりｄビットづつその
順序が逆転されてスタック・ロジック系列として出力さ
れるので、このスタック・ロジック系列は一定の線形を
持たないものとなる。

第２図において、スタック・ロジック回路４の深さをｎ
ビットとし、線形フィードバック・シフトレジスタ１の
ｍビット目の内容ＸＩＩの値によって、ｐｕｓｈおよび
ｐｏｐするビット数ｄが、次のように定まるものとする
。

または、 ｄ””ｄｏ　　（ｘ、＋１）＋ｄｌ　Ｘ、、１≦ｄ≦ｍ
・・・　（２） スタック・ロジック回路４は、（２）式で定まるｄビッ
トを線形フィードバック・シフトレジスタ１から取り込
んでｐｕｓｈおよび１）０１）　して、スタック・ロジ
ック系列として出力するのである。

符号変換装置をＳ　（ｎ＋ｍ＋ｄｏ＋ｄ＋　）発生装置
と呼ぶことにする。Ｓ　（ｎ、ｍ、Ｌｌ）発生装置は、
ｍの値の如何に関わらずオリジナルの線形フィードバッ
ク・シフトレジスタであることは自明である。

例として、Ｓ　（５，２，１，２）およびＳ　（５，５
，Ｌ２）の場合のレジスタと出力の遷移状態を示す表を
第３図として示す。

Ｓ　（ｎ５ｍ＋ｄｏ＋ｄ＋）発生装置において、−船釣
な、ｄ０≠ｄ１の条件を満たすＳ　（ｎ、ｍ、Ｌ２）を
例として説明する。まず、Ｓ　（ｎ、ｍ、１．２）発生
装置の出力ｙをＧＦ　（２）上の演算で表現すると、Ｇ
Ｆ（２）上任意のｐ変数関数、 ｙ＝　ｆ　（Ｌ、Ｘｚ、・・、”ｐ　）　、）’＋Ｘ＝
　ｅＧＦ（２）・・・　（３） はすべてＧＦ（２）上のｐ変数多項式として次のように
表される。

ｆ　（Ｘ、、Ｘ、、　　・・、Ｘｐ） ・　・　・　（４） ここで係数ａ　ｆｌ　ｒ＠　０．ｒｌは次のようにして
決まる。

ａ　ｉ、ｉ、０．ｉ、＝）：ｆ　（Ｘ′＋、　Ｘ’：、
　・・、　　Ｘ’ｐ　）・　・　・　（５） 総和は、ｉＪ≠０なるＸｊのそれぞれについてＧＦ　（
２）の元全体についてとる。例えば、ａ　ｏｏｏ、ｏ　
−ｆ　（０＋　　”　＋Ｏ）＋　ａ　Ｉｏ＝＋−Σｆ　
（Ｘｌ、　０．　”　Ｏ）、　　ａｌ、−１−Σｒ　（
ＸＩ、　　・・、Ｘｐ） 等である。

（３）式をスタック・ロジック系列の出力ｙの表現であ
ると考えることができる。係数ａのサフィックス（ｌ＋
＋　１２＋　　・・１ＩＩＮ＋　　・・、ｉ、）をｐタ
ップルと考え、これに出力ｙを対応させれば真理値表と
なる。第３図に示した二つの遷移表は、オール０−タッ
プルと０出力を付加すれば真理値表となる。

いま、ｐとしてｐ≧ｎなる範囲を考えると、系列生成の
論理から真理値表の出力ｙの列に含まれる１の個数は偶
数である。従って、（３）式の一般項（ａ　ｉ、　ｉ、
　０．＋ｙＸ２　Ｘ’２　　・・Ｘ”Ｇ　）　（’）う
ちｎ次以上のものの係数は０となり、（３）式の多項式
の次数は（ｎ−１）次以下である。

なお、Ｓ　（ｎ、ｍ、ｄｏ、ｄｌ）発生装置において、
ｄｏ＝ｄｌ＝ｄの場合は、系列をｄビット毎にデシメー
ションして得られる系列、もしくはｄビットを排他的論
理和として得られる系列を考えれば、線形複雑度はｎと
なり、（２ｎ−１）ｄビットの情報で全系列を再現でき
るから、自明のこととして対象外とする。

次に、後部の（ｎ−ｒｒ＋−１）−ビットがオール０で
ある（ｎ−１）−タップルを取り上げ、これを二つの場
合に分けて説明する。

（ケース１〕 （Ｌ、　Ｘｚ）　ノ２−タップルが（０，０）もしくは
（１，１） 制御条件およびＸ、の値に関わらず出力は同一である。

しかもこの条件を満たすタップルは、２　＋１１−１個
存在し、かつｍ≧２であるから出力の合計は偶数となる
。

〔ケース２〕 （ＸＩ、　ＸＺ）の２−タップルが（０，１）もしくは
（１，０） 最初の（ｍ−１）−タップルが同一でｍ桁目が異なる二
つのｍ−タップルを考える。つまり、（Ｘ、、ＸＺ、　
　・・、Ｘｍ−、，０）と（ＸＩ、Ｘｉ、　　・・、Ｘ
、Ｒ−１，１）これらのうち、（Ｘ３．Ｘｍ、・・＋Ｘ
Ｔ１−１　）の（ｍ−３）−タップルが（Ｌｌ、　　・
・、１）のようにオールｌの場合を除いて、ペアは同一
の出力値を持つ。

一方、オールｌの場合は、ｍが奇数であれば、（Ｘ　、
　、　ＸＺ）　−（０，１）である方のペアが異なる出
力を出す。従って、ａ　、、、、＝＝　１となり、Ｘ、
ＸＺ・・　χ□なるｍ次の項が存在する。

異なる出力を出すペアは唯一であり、そのうち１を出力
する（ｎ−１）−タップルは、後部の（ｎ−ｍ−１）桁
のうちから任意の１桁を選び、これを変数として付は加
えると１を出力する二つの（ｍ−１）−タップルとなる
。従って、Ｘ、ＸＺ　　・・ＸＩＩＸ＋ｔ　、ｎ−１≧
に５ｍ−１−１の係数は０となる。故に、ｍ＋１次以上
の項は存在しない。

以上のことから、本発明で得られるスタック・ロジック
系列を、シフトレジスタの内部状態を変数とする多項式
で表現すると、含まれる項の最高次数はｍ次となり、こ
れを線形複雑度＃して表現すると、 となる。原始多項式の種類によっては線形複雑度が縮退
することがあるが、応用にあたって制約になるほどのも
のではない。

例として、第３図に示したＳ　（５，２，１２）の場合
には、多項式関数は、 Ｖ＝Ｘ２　＋ＸＩ　ＸＳ となり、線形複雑度＃Ｌは、 ＃Ｌ；Σ５Ｃ４＝１５ １＋１ となり、５ｔａｉｒ−ｃａｓｅ−Ｐｒｏｆｉｌｅは第４
図のようになる。

具体的には、線形フィードバック・シフトレジスタの段
数を０桁とした場合、線形フィードバック・シフトレジ
スタ単体の場合は、２ｎ−１ビツトとなり、本発明の場
合は２ｎ−２であるので、ｎを最も一般的な段数６４と
すると、線形フィードバック・シフトレジスタ単体の場
合は１２７ビツトであるのに対して、本発明の場合は３
．７　Ｘｌ０Ｉ９ビツトとなり、線形複雑度＃Ｌすなわ
ち難解性は飛躍的に増大している。

次に、スタック・ロジック系列の周期に関して説明する
。

スタック・ロジック制御を行わない場合、すなわち線形
フィードバック・シフトレジスタから直接系列を出力し
た場合は、長さ２’−１のＭ系列が出力される。制御は
、レジスタのｍ桁目の内容によって、Ｍ系列の連続した
２ビツトの位置を入れ換えるのであるから、周期の長さ
には影響を及ぼさない、従って、スタック・ロジック系
列の周期長Ｐは、 Ｐ＝２ｒ′−１ となる。

スタック・ロジック系列のｒ−タップル分布に関して説
明する。

タップル長の範囲を１≦ｒ≦ｎとすると、■ｒ＝１の場
合は、周期の場合と同様に、理想的１−タップル分布を
する。すなわち、 ■ｒ≠１の場合は、ｍおよび原始規約多項式の種類によ
って分布が変化する。

例として、ｎ＝１３．　ｆ（ｘ）＝Ｘ”＋Ｘ’＋Ｘ’＋
Ｘ＋１　　（７）場合について、理想的なｒ−タップル
分布からの乗離度を×２計算した表を第５図として示す
。この第５図に示されるように、他の段数の場合も同様
であるが、ｍが大、ｒが小であると、理想的なｒクツプ
ル分布に近づくことになる。

〔発明の効果〕

以上の説明から明らかなように、本発明は、従来から一
般的に利用されている線形フィードバック・シフトレジ
スフ単体で構成された符号変換装置の持つ優れた特性、
すなわち長い周期を持つこと、統計的にランダムである
こと、容易に発生できて実用的であること、等の特性を
そのまま維持して、その最大の問題点である、その一部
から全体が解明されないと云う難解度が低い問題点を充
分に解消しているので、符号変換装置として極めて優れ
た機能を発揮するものである。

また、その構成は、従来からの線形フィードバック・シ
フトレジスタにスタック・ロジック回路を追加しただけ
の簡単なものであるので、その実施が容易であり、線形
フィードバック・シフトレジスタを利用した既設の符号
変換装置に対しても簡単に実施することかできる。

【図面の簡単な説明】

第１図は、本発明装置の最も基本的な構成例を示すブロ
ック図である。 第２図は、スタック・ロジック回路の動作を説明するだ
めの説明図である。 第３図は、Ｓ（５，２，Ｌ２）およびＳ　（５，５，１
，２）の場合のレジスタの出力の遷移状態を表に示した
図である。 第４図は、Ｓ　（５，２，１，２）の場合の５ｔａｉｒ
−ｃａｓｅＰｒｏｆｉｌｅを示す特性線図である。 第５図は、ｎ　＝１３．　ｆ（ｘ）＝Ｘ１３＋Ｘ’＋Ｘ
３＋Ｘ＋１（７）場合の理想的なｒ−タップル分布から
の乗離度を×２計算した結果を示す表図である。 符号の説明 １；線形フィードバック・シフトレジスタ、２；シフト
レジスタ、３；フィードバック結合回路、４；スタック
・ロジック回路、Ｌｌ；出力ビツトライン、Ｌ２ｉビッ
ト設定ライン、Ｌ３；スタック・ロジック系列出力ライ
ン。

Claims (2)

【特許請求の範囲】
1. （１）暗号通信系に使用される符号変換装置であって、
   ｎ段のシフトレジスタ（２）にＭ系列フィードバック結
   合回路（３）を組付けたｎ段の線形フィードバック・シ
   フトレジスタ（１）と、該線形フィードバック・シフト
   レジスタ（１）からの対応するビット数の出力系列を入
   力し、該入力した出力系列をロジックに従い同じビット
   数だけ非線形化してスタック・ロジック系列として出力
   するスタック・ロジック回路（４）とから構成された符
   号変換装置。
2. （２）ビット数を大きく設定すると共に、タップル数を
   小さく設定した請求項１記載の符号変換装置。