JPH0769662B2

JPH0769662B2 - 二元擬似乱数発生器

Info

Publication number: JPH0769662B2
Application number: JP63194102A
Authority: JP
Inventors: なつめ松崎; 誠館林
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1988-08-03
Filing date: 1988-08-03
Publication date: 1995-07-31
Anticipated expiration: 2010-07-31
Also published as: JPH0243594A

Description

【発明の詳細な説明】産業上の利用分野本発明は例えばバーナム暗号発生装置等における二元擬
似乱数発生器に関する。

なお、バーナム暗号は送受信双方で同じ二元擬似乱数発
生器を動作させ、その出力である二元擬似乱数と入力デ
ータとの排他的論理和を計算して暗号化、復号化を行う
暗号方法である。

従来の技術従来、二元擬似乱数発生器としては二値の周期系列を発
生する複数の線形乱数発生器とそれらの出力を非線形に
結合する結合器を用いて構成するものが知られている。
すなわちゲッフェ（以下GEFFEと称する）の方法（アー
ル．ゲッフェ「ハウトゥプロテクトデータウィ
ズサイファズザッツアーリアリハードトゥ
ブレイク」エレクトロニクス/1973.1.4（R.GEFFE“How
to protect data with ciphers that are really hard
to break"Electronics/jan.4.1973））のように複数の
線形フィードバックシフトレジスタ（以降、LFSRと略し
て表現する）の出力ビットを論理積、排他的論理和、ス
イッチ等で構成した非線形結合関数に入力して二元擬似
乱数ビットを発生する方法である。

非線形要素を結合関数に含める理由は非線形要素によっ
て効率的に線形複雑度を増大しバーレカンプーマッセイ
（以下BERLEKAMP−MASSEYと称する）の方法（イー．ア
ール．パーレカンプ「アンジェブレイクコーディング
セオリ」マックグローヒル1968（E.R.Berlekamp“Alg
ebraic Coding Theory“McGraw−Hill1968））による出
力系列の解析を実質上不可能にするためである。

第３図にGEFFEの提案した二元擬似乱数発生器の構成図
を示す。11は第１のLFSR、12は第２のLFSR、13は第３図
のLFSRである。14は第２のLFSRの出力が１のときに第１
のLFSRの出力値を出力とするANDゲート、15は第２のLFS
Rの出力が０のときに第３のLFSRの出力値を出力とする
ゲート、16はゲート14と15の排他的論理和を計算するゲ
ートであり、このゲートの出力を二元擬似乱数列として
用いる。つまり、14,15,16のゲートで第２のLFSRの出力
をスイッチとしてこの値が１のときは第１のLFSRの出力
を二元擬似乱数ビットとし、０のときは第３のLFSRの出
力を二元擬似乱数ビットとする非線形の係合関数を実現
している。ただし、第1,第2,第３のLFSRは共通のクロッ
クで動作する。

第４図は線形フィードバックシフトレジスタLFSRの具体
的構成例を示している。この例では、初期値を“000
1"、最小多項式x⁴＋ｘ＋１＝０とする４ビットのLFSRを
示している。同図において“”は排他的論理和を示し
ている。４ビットのレジスタ値を｛e3,e2,e1,e0｝とし
てこのLFSRの動作を１クロックごとに説明すると次のよ
うになる。なお、このレジスタ値の値は特許請求の範囲
における二元周期系列生成器の“内部状態”の１つの例
を示している。ただし以降の記述において“∧”は排他
的論理和を、“−”は否定を、“＝”は代入を示す。

１初期値を代入する。｛e3,e2,e1,e0｝＝｛0,0,0,1｝２ temp＝e1^∧e0 e0＝e1 e1＝e2 e2＝e3 e3＝temp 従って、｛e3,e2,e1,e0｝＝｛1,0,0,0｝となる。

３２と同様に｛e3,e2,e1,e0｝＝｛0,1,0,0｝となる。

４以下同様に繰り返す。

以上のことより出力系列zi＝e0＝｛100010011……｝と
なる。特にLFSRの特性多項式が原始多項式の場合、出力
系列はＭ系列となる。

第５図はGEFFEの二元擬似乱数発生器（第３図）におけ
るLFSR（１）〜LFSR（３）を具体的に構成した小さな例
を示している。この例を用いて従来例の動作の説明を行
う。

LFSR（１）は｛a1,a0｝を初期値、x²＋ｘ＋１＝０を原
始多項式とするＭ系列生成LFSR,LFSR（２）は｛b2,b1,b
0｝を初期値、x³＋ｘ＋１＝０を原始多項式とするとＭ
系列生成LFSR,LFSR3は｛c4,c3,c2,c1,c0｝を初期値、x⁵
＋x³＋１＝０を原始多項式とするＭ系列生成LFSRであ
る。

LFSR（１）は｛a1,a0｝＝｛0,1｝を初期値とすると、 y¹ _i＝｛101101101101……｝を出力とする。（周期:3） LFSR（２）は｛b2,b1,b0｝＝｛0,0,1｝を初期値とする
と、 y² _i＝｛100101110010111001011……｝を出力とする。
（周期:7） LFSR（３）は｛c4,c3,c2,c1,c0｝＝｛0,0,0,0,1｝初期
値とすると、 y³ _i＝｛1000010101110110001111100110100 1000010101110110001111100110100 ……｝を出力とする。（周期:31）従って、出力系列z_i（＝y¹ _i・y² _i＋y³ _i・^-y² _i）は以上
のことより第８図のようになる。（800サンプル）以上説明した従来の二元擬似乱数発生器の一般的な構成
がレッペル「アナリシスアンドデザインオブス
トリームサイファズ」スプリンガ−ヴァラグ,1986（R
UEPPEL“Analysis and Design of Stream Ciphers"Spri
nger−Verlag1986）5,4章に示されている。第６図にLFS
Rを用いた従来の一般的な二元擬似乱数発生器の構成を
示す。211〜213はＮ個のLFSRである。221〜223は前記各
LFSRの格納値を入力として非線形操作を行うＮ個の非線
形ステートフィルタ（f1〜fN）、23は前記Ｎ個の非線形
ステートフィルタの出力系列の合計Ｎビットを入力とし
てこれに対して非線形の操作を行う非線形結合関数
（Ｆ）である。

特に長周期な二元擬似乱数を生成するため各LFSRその次
数が互いに素なＭ系列生成LFSRで実現することが多い。
また、二元擬似乱数発生器の鍵はLFSR211〜213の初期値
とする。

なお、文献（岡本、中村「非線形二元擬似乱数発生方式
の一案」昭和61電子通信学会全国大会）によればLFSRを
用いた二元擬似乱数発生器の安全性評価基準としては以
下のものが上げられている。

（１）非線形であること。

（２）線形複雑度がBERLEKAMP−MASSEYの解析が実質
不可能なほど高いこと。

（３）無相関性を満たすこと。

（４）長周期性を満たすこと。

（５） 0,1の出現頻度が等しいこと。

この各項目に沿って前記第５図の二元擬似乱数発生器の
出力（第８図）を評価すると以下のとおりになる。

（１）結合関数内にANDゲート14,15が含まれているた
め非線形である。

（２）線形複雑度＝（LFSR1のビット数）×（LFSR2の
ビット数）＋（LFSR3のビット数）×（LFSR2のビット数
＋１）＝２×３＋５×４＝26 （３）無相関性は十分ではない。（ティ．ジーゲンタ
ーラ“デクリプティングアクラスオブストリー
ムサイファズユージングサイファテキストオン
リ」アイトリプルイトランザクションオンコ
ンピュータ1985（T.SIEGENTHALER“Decryphting a Clas
s of Stream Ciphers Using Ciphertext only"IEEE Tra
ns.on Computer1985））（４）周期＝651 （５）１周期651サンプル中“0"の出現頻度:392回、
“1"の出現頻度:259回発明が解決しようとする課題しかしながら、従来の二元擬似乱数発生器において各LF
SRをＭ系列生成LFSRで構成し、さらに二元擬似乱数発生
器の鍵をそのLFSRの初期値とすると、鍵を変化しても二
元擬似乱数系列ziの位相のみが変化し、周期系列として
は同じであるという問題点が生じる。この理由を第６図
に示した一般的な構成で説明する。

（１）Ｍ系列生成LFSRはそのビット数で表現できるす
べての内部状態（S₁,…,S_m）をとる。なお、LFSRの状態
は１クロックごとにこの順番で周期的に遷移するものと
する。

（２）Ｍ系列生成LFSRに設定する初期値がA1の場合と
A2（≠A1）の場合を比較する。A1はLFSRのビットで表現
できるすべての内部状態（S₁,…,S_m）のうちのあるS_iの
同じである。従って、A1を初期値に設定した場合のLFSR
の出力系列は（S_i,S_i+1,…,S_m,S₁,…,S_i-1）となる。A2
はLFSRのビットで表現できるすべての内部状態（S₁,…,
S_m）のうちのあるS_j（≠S_i）と同じである。従って、A2
を初期値に設定した場合のLFSRの状態遷移は（S_j,S_j+1,
…,S_m,S₁,…,S_j-1）となる。

（３）メモリレスの非線形ステートフィルタはLFSRの
ある状態S_kに対して一意的に出力値t_kが決定する。（t_k
＝０または１）従って、LFSRの初期値にA1を代入した場
合の非線形ステートフィルタの状態遷移は（t_i,t_i+1,
…,t_m,t₁,…,t_i-1）LFSRの初期値にA2を代入した場合の
非線形ステートフィルタの出力系列は（t_j,t_j+1,…,t_m,
t₁,…,t_j-1）となる。従って２つの場合における非線形
ステートフィルタの出力系列は起点の位相のみが異なっ
ており周期系列そのものとしては同じである。

（４）メモリレスの非線形結合関数は各非線形ステー
トフィルタの出力値によって一意的に出力値（＝二元擬
似乱数）が決定する。従って、上記のことより２つの場
合の結合関数の出力系列は位相だけが異なる。

以上のことを第５図の例を用いて具体的に説明をする。
ただし、この例は従来の二元擬似乱数発生器の一般的な
構成（第６図）における非線形ステートフィルタを省い
た例である。

従来の技術の項で説明したように、第５図における鍵を｛a1,a0｝＝｛0,1｝、｛b2,b1,b0｝＝｛0,0,1｝、｛c4,c3,c2,c1,c0｝＝｛0,0,0,0,1｝としたときの出力
系列は第８図に示したとおりである。（800サンプル）同様に鍵を｛a1,a0｝＝｛0,1｝、｛b2,b1,b0｝＝｛0,0,1｝、｛c4,c3,c2,c1,c0｝＝｛0,0,0,1,0｝としたときの出力
系列を第９図に示す。（800サンプル）第８図の出力系列と第９図の出力系列を比較すると、第
９図の系列は第８図の系列を63ビット位置だけ遅延した
ものになっていることが分かる。

このように鍵の違いが出力系列の位相にのみ反映するな
らば例えば次のような危険性がある。それは、１回には
短い二元擬似乱数列しか手に入れる能力しかない解読者
にとっても入手した複数ブロックの二元擬似乱数列（鍵
は同じかもしれないし異なっているかもしれない）を組
み合わせることによって長い二元擬似乱数列を手に入れ
ることができるという可能性である。従って、鍵によっ
て位相だけではなく二元擬似乱数列そのものが変化する
ほうが望ましい。

本発明は掛かる点に鑑み、出力系列の周期、０と１の出
現頻度等統計的数値、線形複雑度における特性を劣化さ
せずに、鍵によって二元擬似乱数系列そのものが変化す
る二元擬似乱数発生器を実現することを目的とする。

課題を解決するための手段本発明はＮを正整数とするとき、内部状態の初期値が設
定可能であり、内部状態によって一意的に定まる二値の
値を出力とするＮ個の二元周期系列生成器と、初期設定
可能なＮ個の１ビットメモリと、ｉ番目の二元周期系列
生成器（ｉ＝１〜Ｎ）における時刻ｊの出力値Wⁱ _jとそ
のｉ番目の二元周期系列生成器に対応する前記メモリ格
納値との排他的論理和をとる各ｉに１個ずつ、合計Ｎ個
のゲートと、前記排他的論理和ゲートのＮ個の出力を入
力としてこれらを非線形に結合する結合器とを備えたこ
とを特徴とする二元疑似乱数発生器である。

作用本発明は前記した構成のＮ個の１ビットメモリに鍵の一
部を代入する。メモリに格納する鍵を変化することによ
って出力である二元乱数系列そのものが変化する。さら
に二元周期系列生成器の出力とメモリの各ビット値を排
他的論理和で結合しているため、排他的論理和の出力系
列は元来、二元周期系列生成器のもっている周期、統計
的性質、線形複雑度の特性を保存している。

従って、結合器においてこれらＮ個の系列を入力として
得られる二元擬似乱数は従来の二元擬似乱数の安全性に
関する特性が劣化せず、そのうえ鍵（＝初期状態）によ
って出力系列の起点の位相だけでなく周期系列自身が変
化する。

実施例第１図は本発明の一実施例における二元擬似乱数発生器
の構成図を示すものである。第１図において111〜113は
Ｎ個のLFSR、前記各LFSRの格納値を入力として非線形操
作を行うＮ個の非線形ステートフィルタ（f1〜fN）,3は
Ｎビットのレジスタ、41,42,43は前記非線形ステートフ
ィルタf1〜fNの各出力と前記レジスタの対応ビットとの
排他的論理和をとるゲート、５は前記ゲートの出力を入
力としてこれを非線形に結合する非線形結合関数Ｆであ
る。

この構成において鍵はLFSR（１）〜LFSR（Ｎ）の初期値
key（１）〜key（Ｎ）とＮビットのレジスタの格納値ke
y（０）である。key（０）を同じにしてkey（１）〜key
（Ｎ）を変化すると従来どおり出力系列の位相のみが変
化して系列そのものは変化しない。key（０）を変化す
ると出力系列そのものが変化する。したがって2^N通りの
出力系列がある。

第１図に示した構成のうちLFSRや非線形関数を具体的に
示した例を第２図に上げる。第２図は従来例のGEFFEの
二元擬似乱数発生器（第４図）に本発明のポイントであ
る。鍵を格納するレジスタ６と、その各ビットとLFSRの
出力値との排他的論理和7,8,9を付加したものである。

この二元擬似乱数発生器における鍵を key（１）＝｛a1,a0｝＝｛0,1｝ key（２）＝｛b2,b1,b0｝＝｛0,0,1｝ key（３）＝｛c4,c3,c2,c1,c0｝＝｛0,0,0,0,1｝ key（０）＝｛d2,d1,d0｝＝｛0,0,1｝とする。この場合の本二元擬似乱数発生器の動作を以下
に説明する。

LFSR1,LFSR2,LFSR3の出力系列y¹ _i y² _i,y³ _iはそれぞれ y¹ _i＝｛101101101101……｝ y² _i＝｛100101110010111001011……｝ y³ _i＝｛1000010101110110001111100110100 1000010101110110001111100110100……｝となる。レジスタ６の値は｛d2,d1,d0｝＝｛0,0,1｝で
あるので排他的論理和7,8,9の出力は以下のとおりにな
る。

u¹ _i＝y¹ _i d2＝y¹ _i “0"＝y¹ _i ＝｛101101101101……｝ u² _i＝y² _i d1＝y² _i “0"＝y² _i ＝｛100101110010111001011……｝ u³ _i＝y³ _i d0＝y³ _i “1"＝^-y³ _i ＝｛0111101010001001110000011001011 0111101010001001110000011001011……｝従って、出力系列zi（＝u¹ _i・u² _i＋u³ _i・^-u² _i）は表１
のとおりになる。

第７図は第８図，第９図に示している従来例の二元擬似
乱数系列とは明らかに異なっている。つまり、レジスタ
６の値を変えることによって二元擬似乱数系列自身が変
化する。

また、第７図の系列について従来例と同様に文献（岡
本，中村「非線形二元擬似乱数発生方式の一案」昭和61
年電子通信学会全国大会）による安全性評価基準に沿っ
て評価すると以下のとおりになる。

（１） ANDゲートが含まれているため非線形である。

（２）線形複雑度＝30 （３）無相関性は十分ではない。（従来例と同様）（４）周期＝651 （５）１周期651サンプル中“0"の出現頻度:268回、
“1"の出現頻度:383回これを従来例の二元擬似乱数系列第８図の特性と比較す
る。

・線形複雑度は増加している。これは第２図におけるu³
_iの線形複雑度がd0が“1"であるためにy³ _iに比べ１増加
しているためである。

・周期は１周期の間レジスタの格納値を一定にしている
ため従来と同じである。

・出力の“0"と“1"の出現頻度はGEFFEの方法の場合、
本発明の付加回路によって変化している。ところで、非
線形結合関数Ｆを入力系列の０と１の出現頻度が同じと
きに出力系列についてもその０と１の出現頻度が同じに
なるように設計する。例えばＦとして各入力の排他的論
理和を出力するものを考えるとこの条件は満たされる。
するとＦには各LFSRからＭ系列またはＭ系列の否定（ど
ちらも一周期中の０と１の出現頻度は等しい）が入力さ
れるため出力系列の0,1バランスは満たされる。

以上のことより本発明の付加回路は、従来の二元擬似乱
数発生器の安全性に関する特性を劣化しないことが分か
る。

以上のように本実施例によれば多少の回路を付け加える
だけで鍵によって二元擬似乱数系列自身を変えることが
できる。また、このことによって二元擬似乱数発生器の
安全性に関する性質が劣化していない。

なお、以上の実施例において単なるレジスタ６を付加し
たがこの部分をLFSR等で構成しても良い。ただし二元擬
似乱数発生器の安全性に関する性質を劣化しないことを
保証するため、LFSRで構成した場合にはそのシフトを出
力系列の１周期に１回（前期の例では651クロックに１
回）とするなどタイミングを考慮する必要がある。

また、実施例においては鍵を各LFSRの初期値と、レジス
タのみに代入するように仮定したが、鍵によってLFSRの
結合、非線形ステートフィルタ、非線形結合関数がコン
トロールできるようにしておいても良い。

また、第１図における実施例の非線形ステートフィルタ
ｆ（１）〜ｆ（Ｎ）は、前記でGEFFEの二元擬似乱数発
生器に本発明を適応した例のとおり、省略しても良い。

発明の効果以上説明したように本発明によれば、従来の構成にＮ個
の１ビットメモリとＮ個の排他的論理和ゲートという多
少の回路を付加するだけで、前記Ｎ個の１ビットメモリ
に格納する鍵によって二元擬似乱数系列の周期系列自身
を変化することができる。さらにこの付加回路によって
線形複雑度、周期、0,1バランス等の性質が劣化するこ
とはない。従って、その実用的効果は大きい。

【図面の簡単な説明】

第１図は本発明の一実施例の二元擬似乱数発生器の構成
図、第２図は本発明を具体的にGEFFEの方法に適応した
例の構成図、第３図はGEFFEの方法における構成図、第
４図はLFSRの具体的構成例、第５図はGEFFEの方法の具
体的構成例、第６図は従来の二元擬似乱数発生器の一般
的構成図、第７図は前記実施例における出力系列の例を
示すデータ図、第８図，第９図はGEFFEの方法による出
力系列の例を示すデータ図である。 111,112,113,11,12,13,211,212,213……LFSR、121,122,
123,221,222,223……非線形ステートフィルタ、3,6……
レジスタ、41,42,43,7,8,9,14,15,16……ゲート、5,23
……非線形結合関数。

Claims

【特許請求の範囲】

【請求項１】Ｎを正整数とするとき、内部状態の初期値
が設定可能であり、内部状態によって一意的に定まる二
値の値を出力とするＮ個の二元周期系列生成器と、初期
設定可能で前記二元周期系列生成器それぞれに対応する
Ｎ個の１ビットメモリと、ｉ番目の二元周期系列生成器
（ｉ＝１〜Ｎ）における時刻ｊの出力値Wⁱ _jとそのｉ番
目の二元周期系列生成器に対応する前記メモリの格納値
との排他的論理和を求める各ｉに１個ずつ、合計Ｎ個の
ゲートと、前記排他的論理和ゲートのＮ個の出力を入力
としてこれらを非線形に接続する結合器とを備えたこと
を特徴とする二元疑似乱数発生器。