JPS63308432A - 系列生成方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （監東上の利用分野） 本発明は、データ通信回線上のデータの盗聴等を防ぐ目
的で、コンピュータ或いは符号化された音声等の情報信
号を暗号化する暗号演算を行なうための系列生成方法に
関する。

（従来技術） 近年、データ回線等を介して行なう通信情報の盗聴、或
いは改ざんを防止するために１通信する当事者のみが知
る暗号鍵によってデータを暗号化して容易に情報内容を
解読でき々いよう圧する手段の会費性が高まって来た。

暗号方式に要求される事項は第一に暗号データが生のデ
ータの統計的性質が破壊され、結果として擬似ランダム
化されること。第２に、平文と対応する暗号文が第三者
に入手されたとしても容易に解読されないもの、即ち暗
号攻撃強度評価が高いこと、更には暗号アルゴリズムが
知られかつ暗号文が知られたとしても暗号鍵全数検査以
外に解読方法がなくかつ該暗号鍵全数ができるだけ膨大
であることが掲げられる。

暗号化方法としては、伝送すべき生の情報信号系列１例
えばテジタル信号のビット系列な所要の暗号鍵に従って
ランダム化するのが一般的であるが、従来この信号系列
をランダム化するための装置としては第２図（ａ）に示
す如く最大長系列（系列長２ｎ−１，ｎはシフトレジス
タのフリップフロップの数）を生成する線形シフトレジ
スタが使用されていた。

これはシフトレジスタ１の各フリラフフロップ出力をス
イッチ２へ入力し、この出力を排他的論理和３を抽出し
出力となしこの出力４を前記シフトレジスタＩＫフィー
ドバックせしめるとともに望む暗号信号として出力する
ものである。

このとき前記スイッチ２の０Ｎ−ＯＦＦのパターンを原
始既約多項式の係数に対応せしめることによって最大長
系列出力を得ることができる。

この方法は比較的簡単な装置構成によってデータを擬似
ランダムなる暗号データにすることができるが９反面ｐ
ｌａｎｅ　　ｔｅｘｔ　　ａｔｔａｃｋ　　に対しては
線形連立方程式によって極めて容易に暗号鍵に相当する
前記スイッチ２の０Ｎ−ＯＦＦ　　パターンが解読され
てしまうと云う問題があった。

又、原始既約多項式の数、即ち暗号鍵の数は第２図（ｂ
ｌ　Ｋ示す如くシフトレジスタの数ｎによって定まるが
、上述した方式では米国商務省（ＮＨ８）公認の暗号で
あるＤＢＳに於ける鍵の数的１０１６程度にするために
は前記シフトレジスタの数ｎを膨大なものとしなければ
ならず現実的でない。

この欠点を除去するために、従来第２図（ｃｌに示す如
く２ｎの系列長の全周期系列を生成するための装置を備
えることによって必要とするシフトレジスタの数を大幅
に削減しても所望の暗号鍵の数を得るようにしていた この方法は同図に示すように、シフトレジスタ７の出力
をＲＡＭ８へ入力し該ＲＡＭの出力を前記シフトレジス
タ７にフィードバックせしめると共に制御装＠９．記憶
装＆１０及び入力装置１１とを備え、入力装置からの信
号に従い記憶装置にメモリした複数の全周期系列の帰還
関数値を制御装置内に呼び出し前記シフトレジメタに対
しデータとクロック信号とを出力しかつ、ＲＡＭに対し
前記帰還関数をアドレスバスとデータバスとを介して曹
き込むよう構成したものである。また前記制御装置はシ
フトレジスタに初期値を与える働きを付加する。

この方式では帰還関数が非線形演算をもとにするためｐ
ｌａｎｅ　　ｔｅｘｔ　　ａｔｔａｃｋ　　に対して線
形連立方程式を用いることができず、又暗号鍵の９＝晶 数も２　　個と非常に多くなるから、暗号方式としての
前記各快求を済す極めて優れた方式と彦る。

この方式では一般に記憶装置１０には全周期系列に限ら
ず、０，１が１７２づつになるような非線形なる生成法
による系列の帰還関数値を入れておいてもよいこと明ら
かである。

しかしながら、上述したような従来の方法では、暗号鍵
に相当する系列を作るためには一般に２ｎの長さの系列
の帰還関数値のすべてをメモリしておく必要があるが、
その容量が制限される場合多くの系列をメモリできず暗
号鍵を多くできないと云う問題があった。

即ち、この方式では所望の暗号鍵を得るためにはそれに
応じて記憶装置の容量を膨大なものとし女ければならず
、装置が複雑高価なものとなっていた。

（発明の目的及び概要） 本発明は上述した事情に鑑みてなされたものであって、
僅かなパラメータを記憶しておくのみで暗号鍵に相当す
る系列を一定のアルゴリズムによって自動的に生成する
ことによって、記憶すべき情報が少なくて済み安価な暗
号装置をもたらしうる系列生成方法を提供することを目
的とする。

（実施例） 以下１本発明を図示した実施例に基づいて詳細に説明す
る。

第１図（ａ）は本発明に係かる系列生成装置の原理を説
明するためのブロック図であって、シフトレジスタ１２
の内部状態Ｘを帰還回路１３を介してその出力ｆ　（ｘ
ｉを前記シフトレジスタ１２ヘフィードバックするよう
構成したものである。

この場合の帰還シフトレジスタの状ｐｘと帰還関数ｆ　
（ｘｉとの関係の一例を第１図（ｂｌに示す。

同、この例は３ビツト系列の場合である。第１図（ｃｌ
　Ｉｄ　（ｂｌ図に基づいて帰還シフトレジスタの状態
の変化を説明した図であって、一般に状態遷移図と呼ば
れるものである。この図では遷移図中の各節点が夫々の
状態を示し、矢印機の数字は帰還関数値を示す。

第１図（ｄｉは第１図１（ｂｌに於ける状態Ｘについて
ｘ＝（０１０） ｘ　＝　（１００） の時の帰還関数値、ｆ（０１０）−〇　、ｆ（Ｚｏｏ）
−１の補数をとったもので 、１（ｏｉｏ）＝１ ｆ　（１００）＝０ とした図である。

第１図（ｅｌは、第１図（ｄｉの状態遷移図である。

第１図（ｃｌと第１図（ｅｌを比較するとＲ還関数を何
らかの規則で変換すれば異なる系列を生成できうろこと
明らかでろろう。

即ち、系列変換の規則を記憶しておき、入力パラメータ
によって給１図（ｂｌの帰還関数値を変換すればよい。

この実施例では系列変換規則は指定した帰還関数値の補
数を計算するようにしたものであυ、入力パラメータは
Ｘの値と個数である。

本実施例変換によると２例えば状態の初期値がＸ＝（１
１１）　　のとき第１図（ａ）の系列出力はすべて１で
ある。

この事実は１本系列生成方式を暗号手段として利用する
場合に次の制限な費することを意味する。

第１図げ）は同期型帰還シフトレジスタ方式の系列生成
装置の一実施例を示すブロック図である。

送信側装置１４は、シフトレジスタ１５の出力１６を帰
還回路１７へ入力し、該回路の出力ヲ前記シフトレ／ス
タ１５ヘフイードバソクすると共にこの出力と入力デー
タとを排他的論理和回路１８に入力し、この回路の出力
を暗号信号として出力するが、受信ｇＡ１１との同期を
とるために同期信号発生器１９の同期信号を混合器２゜
に於いて前記暗号信号出刃に重畳して伝送信号とする。

一方受信側装置２１では、シフトレジスタ２２の出力を
帰還回路２３を介して再び前記シフトレジスタ２２にフ
ィードバックするよう構成した閉ループ回路の前記シフ
トレジスタ２２の入力に、前記送信側装置から送られた
暗号信号のうちから同期信号を分離回路２４によって分
離し受信データ信号のみを入力し１分離した同期信号は
同期信号制御装置２５に入力する。又。

前記シフトレジスタ２２は同期信号制御装置によシ生成
した初期値及び同期信号によって制御され送信側装置と
の同期がはかられる。更に。

前記分離回路２４とシフトレジスタ２２の入力との間に
は排他的論理和回路２６を挿入し、暗号データ２７と前
記帰還（ロ）路２３の出力の排他的論理和を求め、これ
が復調信号出刃となる。

この方式は、平文データ列をＰｉ　、帰還シフトレジス
タ出力系列をＳｉ、暗号データ列をＣｉとすれば。

暗号化；　Ｃｉ＝Ｐ　ｉ　＋Ｓ　ｉ　　（ｍｏｄ２　）
復号化；Ｐｉ＝Ｃｉ＋Ｓｉ　　（ｍｏｄ２）となるため
、系列Ｓｉが初期値によって１例えば全て１となっては
暗号装置として利用できない。

そこで、この実施例では、第１図（ｇｌに示すような自
己同期型帰還シフトレジスタとして使用する。

第１図（ｇｌの構成は、送信（ｌｌＩ　装置２８では、
シフトレジスタ２９　、帰還回路３０及び排他的論理回
路３１とを前述の例と同様に接続したもので、受信１ｌ
ｌＩ装置３２も又同様にシフトレジスタ３３、帰還回路
３４及排他的論理回路３５とから構成したものであって
、前記第１図げ）と異なるのは同期信号を伝送しない構
成点である。

第１図（ｇｌは自己同期型帰還シフトレジスタを用いる
場合であって、これはシフトレジスタが自己で閉じてお
らず、外部からの信号との和が入力するのでシフトレジ
スタの状態は外部信号によって刻々と変化する。この時
、帰還関数値が１．０を１／２つつ持つ様にすれば、暗
号データは擬似ランタ゛ム化され、暗号データとして良
好な性質となる。

本実施例の系列生成の原理に基づき系列生成装置を構成
すると、第１図（ｈｌに示す様になる。

シフトレジスタ３６出力は切替装置３７へ入力され、切
替装置３７出カは一時記憶装置３８へ入力される。該出
力と入力データ３９は排他的論理和回路４０へ入力され
該出力系列４１として出力されかつシフトレジスタ３６
へｆ＠還される。制御装置４２は入力装置４３．記憶装
置４４及び演算装ｆｌｔ４５と接続され、シフトレジス
タ３７ヘクロツク４６とデータ４７を出力し、切替装置
１３７にアドレス４８及び切替信号４９を出力し、一時
記憶装置３８ヘテータ４５′を出力する。

次に本構成の動作を説明すると、制御装置４２は入力装
置４３より系列変換のパラメータを入力し、記憶装置４
４に記憶した。ただ１個の系列の帰還関数値と共に制御
装置４２に記憶した系列生成アルゴリズムによって、演
算装置４５を用いて系列変換する。次に生成した系列の
帰還関数値を切替装置３７をアドレス４８１１１１とし
て一時記憶装＆３８ヘデータ４５を通して書き込む。最
後に制御装置４２は切替装置３７をシフトレジスタ３６
０１１１に切替、データ４７を用いてシフトレジスタ３
６の初期値を入力し、クロック４６をシフトレジスタ３
６へ供給し、入力データ３９を暗号化した系列４１を作
る。

復号化回路は第１図（ｇｌの受信側に示した帰還シフト
レジスタを用いるよう構成される事上述した通りである
。

制御装置か記憶する系列生成アルゴリズムを第１図ｉに
記す。

先に述べた実施例は系列生成の一般論であったが、記憶
する系列の帰還関数値と入力パラメータを特別なものに
する事によって同期、非同期型帰還シフトレジスタのど
ちらにも使える系列生成法を構成する事ができる。

以下にこのことを図面を用いて詳細に説明する。

第１図（ｉｔでシフトレジスタ５０の状態Ｘは帰還回路
５１へ入力され、帰還回路５１出力をシフトレジスタ５
０へ帰還される。第１図ｊはシフトレジスタの状＆Ｘと
帰還関数値ｆ　（ｘｉの一例で、これは全周期系列（系
列長２ｎ、但しｎはシフトレジスタのフリップ７ａツブ
数）の１つである。

第１図（ｋｌは第１図Ｕ）の状態遷移図である。全周期
系列はシフトレジスタから作られる最大長の系列であシ
、状態は２ｎ個となって状態遷移図はただ１つの閉路と
して表現される。つまシいかなる初期値からはじまって
も常に状態Ｆｉ、１つの閉路内にあり、帰還関数値の０
．１が１７２づつとなっているため暗号回路として非同
期型帰還シフトレジスタとして使えるばかりでなく、同
期型帰還シフトレジスタとしても使用可能である。

次に全周期系列から別の全周期系列を生成するアルゴリ
ズムを説明する。

第１図（ｉｔはシフトレジスタ５０の状態ｘを帰還回路
５１へ入力し、帰還値ｆ　（ｘ）をシフトレジスタ５０
へ帰還すると共に系列出力５２を得るものである。第１
図Ｕ）は全周期系列の中の１つの状態と帰還関数ｆ　（
ｘｌのテーブルである。第１図（ｋｌ　Ｆｉ第１図（ｊ
ｌの状態遷移図である。同図（ｋｌを用いて別の全周期
系列を作る一例を示す。

、Ｎ＝＝２ｎ　ｎＦｉシフトレジスタのフリップフロッ
プ数）を計算する。

この場合、３＋２”／２＝７　　となる。次に帰還関数
ｆ（Ｘｉ）、　ｆ（Ｘｉ”）　　の補数を取ると了（ｘ
ｉ）＝Ｏ ｆｃＸｉ”）−１ となり、この様に帰還関数を変換する事で、状態遷移図
は、００１，０１０，１００，０００，００１及び１０
１，０１１，１１１，１１０，１０１　　なる２閉路に
分離される。次にＸ　Ｊ　、　Ｘ　＞”　（Ｘ　Ｊ″−
ｘ、＋Ｎ／２）がそれぞれ上記２閉路上にある様に選ぶ
。

たとえば。

Ｘｊ−２ ＸＪ“＝２＋２７２＝６ として 、ｆ（Ｘｊ）−１ 了（ｘＪ′）＝０ この様に前記２閉路を変換すると、状態Ｘと帰還関数ｆ
（幻の関係は第１図（ｌｌに示す様になり。

状態遷移図は第１図Ｈの様に再び１つの閉路。

すなわち全周期系列となる。前記アルゴリズムケまとめ
ると、第１図（ｎｌに示す様になる。

本実施例２の原理に基すいた自己周期型帰還シフトレジ
スタの構成は、実施例１に於ける第１図（ｈｌと基本的
に同様である。

更に同期型帰還シフトレジスタとするには。

第１図（０）の様な構成を取れば良い。すなわち。

シフトレジスタ５２の出力を切替装置５３へ入力し、切
替装置５３出力を一時記憶装置５４へ入力する。一時記
憶装置出力と、入力データ５５を排他論理和５６へ入力
し、出力系列５７とする。壕だ一時記憶装置５４出力は
シフトレジスタ５２へ帰還されろ。制御装置５８は記憶
装置５９、入力装置６０　、演算装＋ｗ６１．同期回路
６２、と接続され、この同期［Ｕ路６２出力を混合器に
よって前記出力系列信−号に重畳して暗号イｇ号として
伝送する。

以上の構成の動作及び操作は上述した第１図ｆｈｌげ）
に図示したものとほぼ同様でろる。

（発明の効果） 本発明は以上説明したように構成しかつ機能させるもの
であるから、Ｆ＠号化にあたっての全周期系夕１１或い
は全周期系列に限らず０．１が１／２づつになるような
非線形なる系列信号を簡単な′ＪｐＩ成によって極めて
効率よく生成することができるから極めて安価かつ簡単
な構成によってすぐれた暗号装置をもたらすうえで著効
を奏する。

【図面の簡単な説明】

あって、　（ａｌ　（ｇｌ　ｆｈｌｕへひ（りは暗号生
成装置の一部分を示すブロック図ｆｂｌ　ｆｄｌ　（ｊ
　ｌ　（／ｌ　ｒｊ：シフトレジスタの内容と帰還関数
との関係の一例を示す図、（Ｃ）（ｅｌ（ｋｌ−は状態
遷移図（ｐｉ　（ｎｌはアルゴリズムを説明するフロー
チャート図、第２図（ａｌ　（ｂｌ及び（Ｃ１は従来の
暗号生成方法を示すためのブロック図、フリッツフロノ
ブの内容と帰還関数との関係を示す図である。 １２．１５．２２，２９．３３．３６．５０・・・・・
・・・・シフトレジスタ。 １３．３（＋　、３４．１７．２３・・・・・・・・・
帰還回路。 ４３・・・・・・・・・入力装置。 特許出願人　　東洋通信機株式会社 ｏ　ｏｏｏ、、、、 第　　１　　ロ （Ｃン 第　　ｚ７ 手続補正書 １、事件の表示 昭和６１年　特許　願第１１１３４２　　号２、発明の
名称　　　　　　　系列生成方法３、補正をする者 事件との関係　　　出願人

Claims (2)

【特許請求の範囲】
1. （１）系列生成のために必要なパラメータを入力装置よ
   りとり込み、そのパラメータと記憶装置内に記憶した１
   つの系列を元に他の系列の帰還関数を生成する演算装置
   と、帰還関数値をフィードバックシフトレジスタの帰還
   回路に入力し、又装置全体を制御する制御装置によって
   フィードバックシフトレジスタから任意の系列を得るよ
   うにしたことを特徴とする系列生成方法。
2. （２）上記パラメータに制限を加え、記憶装置内の系列
   を全周期系列とすることによって、全周期系列を生成す
   ることを特徴とした特許請求の範囲第１項記載の系列生
   成方法。