JPH11224183A - 擬似乱数発生装置 - Google Patents

Abstract

(57)【要約】 【課題】 線形フィードバックシフトレジスタを用い
て、線形複雑度が理論的に所定値以上である高速にスト
リーム暗号方式の暗号を生成可能なフィルタジェネレー
タ（擬似乱数発生装置）を提供する。 【解決手段】 線形フィードバックレジスタ１０１と、
線形フィードバックレジスタの初段から連続する所定段
数のレジスタ値の論理積により構成される最高次の項を
有する非線形変換関数を用いて線形フィードバックレジ
スタの各レジスタ値を非線形変換して１ビットの擬似乱
数出力を同期信号毎に出力する非線形変換関数回路１０
２と、線形フィードバックレジスタ１０１に初期値を設
定する初期値設定端子１０４と、線形フィードバックレ
ジスタ１０１をに同期信号を入力する同期信号入力端子
１０５とを有する擬似乱数発生装置とした。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、音声や情報の通信
分野の暗号通信装置で用いられるストリーム暗号方式の
擬似乱数発生装置に関する。

【０００２】

【従来の技術】従来から、例えば、電話機や無線通信装
置やデータ通信装置のような通信システムにおいては、
その通信システムの両端の通信当事者以外の第３者がそ
の通信システムで伝送される情報を知ることができない
ようにするために、その通信システムで伝送される伝送
情報を暗号化することが行われている。この暗号化の方
式としては多種の方式が知られているが、高速なデータ
通信に利用可能な方式としてはストリーム暗号方式が有
る。以下に、ストリーム暗号装置の概略構成を示すブロ
ック図である図２を用いてストリーム暗号装置を説明す
る。ストリーム暗号装置２００は、入力するデータスト
リームを、後述する擬似乱数発生装置２０１により出力
された擬似乱数と、後述する排他的論理和演算素子２０
２で排他論理和演算して暗号出力として出力する暗号装
置である。擬似乱数発生装置２０１は、ストリーム暗号
装置２００における擬似乱数を発生するための装置であ
り、後述する初期設定用入力端子２０３とクロック入力
用端子２０４からの入力が有り、擬似乱数が出力され
る。排他的論理和演算素子２０２は、上記した擬似乱数
発生装置２０１から出力された擬似乱数と暗号化される
前の入力データストリームの排他的論理和演算を行うも
のである。初期値設定入力用端子２０３は、上記した擬
似乱数発生装置２０１に初期設定のための入力を行うた
めの端子である。クロック入力端子２０４は、同期入力
としてのクロック信号を上記擬似乱数発生装置２０１に
入力するための端子である。平文入力端子２０５は、暗
号化される前のデータストリーム信号（平文）が入力さ
れる端子である。暗号出力端子２０６は、ストリーム暗
号装置２００で暗号化されたデータストリーム信号が出
力される端子である。このストリーム暗号装置により、
平文のデータストリーム信号は、擬似乱数と１ビット単
位で排他的論理和演算されることで暗号化されて出力さ
れる。

【０００３】次に、上記した図２に示す擬似乱数発生装
置２０１の一例である、フィルタジェネレータの構成を
示すブロック図である図３を用いてフィルタジェネレー
タを説明する。擬似乱数発生装置３００は、上記したよ
うに図２に示す擬似乱数発生装置２０１の一例としての
フィルタジェネレータである。線形フィードバックシフ
トレジスタ３０１は、擬似乱数を発生させるための元に
なる数値を得るためのレジスタである。非線形変換関数
回路３０２は、上記線形フィードバックシフトレジスタ
３０１の各レジスタの値を入力として非線形変換関数に
より変換して擬似乱数を生成して出力する。シフトレジ
スタ初期値設定用入力端子３０３は、非線形フィードバ
ックシフトレジスタ３０１の各レジスタへ初期値を設定
するための入力端子である。クロック入力用端子３０４
は、線形フィードバックシフトレジスタ３０１へ同期用
のクロックを入力する入力端子である。擬似乱数出力端
子３０５は、非線形変換関数回路３０２から出力された
擬似乱数系列を出力する端子であり、その出力は、例え
ば、図２に示す排他的論理和演算回路２０２に入力され
るものである。ここで、図３に示すフィルタジェネレー
タの暗号学的強度を示す指標の１つである線形複雑度に
ついて説明する。線形複雑度は、擬似乱数出力端子３０
５からの擬似乱数系列の出力を模倣することが可能であ
る等価な線形フィードバックシフトレジスタのレジスタ
長で定義される。また、線形フィードバックシフトレジ
スタの初期値は、その線形フィードバックシフトレジス
タ内のある１個のレジスタの値をその線形フィードバッ
クシフトレジスタのレジスタ長の２倍分だけ特定できれ
ば、その特定値に基づいた連立１次方程式を解くことで
決定することができる。従って、レジスタ長で定義され
る線形複雑度の小さいフィルタジェネレータの擬似乱数
系列は、初期値を得るのに必要なそのレジスタ長の２倍
分のレジスタの値も少ないことになるので、擬似乱数系
列は容易に推定が可能で、暗号用としての使用は難し
い。線形フィードバックシフトレジスタのレジスタ長と
その中の１個のレジスタの値の関係については、更に、
レジスタ長がＬである線形フィードバックシフトレジス
タの１個のレジスタの値がクロック入力により変遷する
周期が２^L −１で繰り返されるときに、その周期的なレ
ジスタの値の系列をｍ系列であると言う。そして、ある
時刻ｔにおけるｍ系列のレジスタ値をｓ（ｔ）で表し、
数式（数１）の線形複雑度ｚ（ｔ）は、理論的に２項係
数の数式（数２）以上であることが、文献（Rainer A.
Rueppel 著の"Analysis and Design of stream Cipher
s," Springer-Verlagのp84-86）により証明されてい
る。但し、ｆの最高次数はｋ未満であり、且つ、次の数
式（数３）の最大公約数を満たすことが条件となってい
る。

【０００４】

【数１】

【０００５】

【数２】

【０００６】

【数３】 次に、上記図３に示す線形フィードバックシフトレジス
タ３０１について、線形フィードバックシフトレジスタ
の概略構成を示すブロック図である図４を用いて説明す
る。線形フィードバックシフトレジスタ４００は、上記
したように従来から図３に示すフィルタジェネレータ
（擬似乱数発生装置３００）で用いられているものであ
る。この図４に示す線形フィードバックシフトレジスタ
４００の各レジスタは、Ｄフリップフロップ素子４０２
で構成され、各Ｄフリップフロップ素子４０２の出力は
次段のＤフリップフロップ素子４０２に出力されると共
に各Ｄフリップフロップ素子毎に定められた所定の係数
により変換されて排他的論理和演算素子４０１で最終段
のＤフリップフロップ素子から順次排他的論理和演算素
子４０１で演算された値と排他的論理和の演算が行われ
る。この図４に示す線形フィードバックシフトレジスタ
の各レジスタの値を示すのが次の数式（数４）である。

【０００７】

【数４】 この図４に示す線形フィードバックシフトレジスタで上
記した線形複雑度ｚ（ｔ）を保証するためには、数式
（数４）の非線形関数の最高次数の項において、上記数
式（数３）を満たすδの間隔で連続するｋ個のレジスタ
により線形フィードバックシフトレジスタを構成すれ
ば、上記線形複雑度以上の複雑度が得られるので保証で
きることになる。一方、線形フィードバックシフトレジ
スタとして、図４に示したもの以外の構成のものでは図
５に示すものが知られている。この図５に示した線形フ
ィードバックシフトレジスタでは、図４に示したものよ
りも高速で動作が可能である。その高速動作が可能な理
由としては、次の理由による。線形フィードバックシフ
トレジスタ５００の各レジスタを構成するＤフリップフ
ロップ５０２の処理による遅延時間をｕ、Ｄフリップフ
ロップ５０２間の排他的論理和演算素子５０１の処理に
よる遅延時間をｖとし、比較するために、図４に示す線
形フィードバックシフトレジスタ４００の各レジスタを
構成するＤフリップフロップ４０２の処理による遅延時
間も図５に示すものと同様にｕ、排他的論理和演算素子
４０１の処理による遅延時間も図５に示すものと同様に
ｖとすると、図４に示す線形フィードバックシフトレジ
スタの場合には、各レジスタ間で最も遅延の起こる部分
は、最終段のＤフリップフロップＸ_L （ｔ）からＬ−１
個の排他的論理和演算素子を経て、初段のＤフリップフ
ロップＸ₁ （ｔ）に至るフィードバック経路であり、そ
の遅延時間は次の数式（数５）で示される。

【０００８】

【数５】 それに対して、図５に示す線形フィードバックシフトレ
ジスタにおいては、各レジスタ間で最も遅延の起こる部
分は、最終段から初段以外の各Ｄフリップフロップへ入
力される経路のどれかであり、何れも１個の排他的論理
和演算素子５０１が入るだけで同様である。その場合の
遅延時間は、次の数式（数６）に示すように１個のＤフ
リップフロップの処理による遅延ｕと１個の排他的論理
和演算素子の処理による遅延ｖの和となる。

【０００９】

【数６】 ここで、図３に示すフィルタジェネレータ（擬似乱数発
生装置３００）の同期用のクロック間隔の最大は、上記
したような最も遅延の起こる部分の遅延時間により決定
されるので、フィルタジェネレータの擬似乱数発生装置
では、図５に示す線形フィードバックシフトレジスタを
使用することは、高速にストリーム暗号方式の暗号を生
成するには有効であるように考えられる。

【００１０】

【発明が解決しようとする課題】しかしながら、図５に
示す線形フィードバックシフトレジスタの動作は、図４
に示す線形フィードバックシフトレジスタよりも複雑で
あり、初段以外の各レジスタの値も複雑になるため、上
記した線形複雑度の大きさを理論的に保証でき、且つ、
図５に示す線形フィードバックシフトレジスタを用いた
図３に示す非線形変換関数回路３０２に相当する非線形
変換関数回路の構成は知られておらず、そのため、図５
に示す線形フィードバックシフトレジスタを用いたフィ
ルタジェネレータにおいて、線形複雑度を数式（数２）
以上とする方法は知られていなかった。本発明では、上
記問題に鑑みて、図５に示す線形フィードバックシフト
レジスタを用いて、線形複雑度が理論的に上記数式（数
２）以上である高速にストリーム暗号方式の暗号を生成
可能なフィルタジェネレータ（擬似乱数発生装置）を提
供することを目的とする。

【００１１】

【課題を解決するための手段】上記目的を達成するため
に、本発明では、同期信号に同期して動作する複数段の
レジスタと各レジスタ間に排他的論理和演算素子を有
し、前記各レジスタに初期値の設定後、最終段のレジス
タの設定値と前記各排他的論理和演算素子毎に設定され
た所定値との論理積のフィードバック値を前記排他的論
理和演算素子に入力し、該排他的論理和演算素子では前
段のレジスタの出力値と前記フィードバック値の排他的
論理和演算を行い次段のレジスタに出力する線形フィー
ドバックレジスタと、前記線形フィードバックレジスタ
の初段から連続する所定段数のレジスタ値の論理積によ
り構成される最高次の項を有する非線形変換関数を用い
て前記線形フィードバックレジスタの各レジスタ値を非
線形変換して１ビットの擬似乱数出力を前記同期信号毎
に出力する非線形変換関数回路と、前記線形フィードバ
ックレジスタに初期値を設定する初期値設定手段と、前
記線形フィードバックレジスタに同期信号を入力する同
期信号入力手段とを有することを特徴とし、前記線形フ
ィードバックシフトレジスタに対応可能な非線形変換関
数回路を提供したことで、高速なストリーム暗号方式の
暗号の生成が可能になった。

【００１２】

【発明の実施の形態】以下に本発明の実施の形態を図を
用いて説明する。図１は、本発明の一実施形態の構成を
示すブロック図である。擬似乱数発生装置１００は、従
来技術の図５に示したタイプと同タイプの線形フィード
バックシフトレジスタ１０１と非線形変換関数回路１０
２を有する擬似乱数発生装置である。線形フィードバッ
クシフトレジスタ１０１における各レジスタの値は次の
数式（数７）のように表される。

【００１３】

【数７】 ここで、初段のレジスタの値ｘ１（ｔ）をｓ（ｔ）とお
くと、図１の各レジスタの値は次の数式（数８）のよう
になる。

【００１４】

【数８】 更に、この数式（数８）の最下段の式、即ち、線形フィ
ードバックシフトレジスタの初段の式の生成多項式を数
式（数９）とする。

【００１５】

【数９】 この数式（数９）が、根が原始根（原始元）の既約多項
式であるならば、そのある時刻ｔにおけるレジスタの値
ｓ（ｔ）はｍ系列になることを示すので、各レジスタの
値は、このｓ（ｔ）の時間遅延項の線形結合により表す
ことができる。この図１の線形フィードバックシフトレ
ジスタ１０１で、上記した線形複雑度の下限の数式（数
２）を満足させるには、数式（数８）における初段側の
レジスタから連続したｋ個のレジスタの値の論理積を生
成して、その生成値を非線形変換関数回路１０３の最高
次の項にする。実際の初段側のレジスタから連続したｋ
個のレジスタの値の論理積は、次の数式（数１０）のよ
うになる。

【００１６】

【数１０】 尚、数式（数１０）におけるＯ（ｋ−１）は、ｋ−１の
次以下の項の全てを表すものである。また、ｓ（ｔ−
α）ｓ（ｔ−α）＝ｓ（ｔ−α）である。上記のように
非線形変換回路を構成することにより、図１に示したよ
うに線形複雑度は理論的に数式（数２）以上であるフィ
ルタジェネレータ（擬似乱数発生装置）を構成すること
ができる。

【００１７】図１の構成による動作は以下のようにな
る。まず、線形フィードバックシフトレジスタ１０１内
のＤフリップフロップ１０７〜１１１に初期値設定用端
子１０４から初期値を入力して設定する。そして、クロ
ック入力用端子１０５からクロック入力が線形フィード
バックシフトレジスタ１０１に入ると、各Ｄフリップフ
ロップには最終段のＤフリップフロップ１１１に記憶さ
れていた値と所定値ａ_i の論理積をとった値と、前段の
Ｄフリップフロップに記憶されていた値の論理和が各々
の排他的論理和素子１１２〜１１４により生成されて記
憶される。尚、初段のＤフリップフロップ１０７には、
例外的に終段のＤフリップフロップ１１１に記憶されて
いた値がそのままで記憶される。非線形変換関数回路１
０２では、線形フィードバックシフトレジスタ１０１の
各レジスタの出力中で、初段のＤフリップフロップ１０
７から連続してｋ個のＤフリップフロップの入力を論理
演算素子１１６に入力してｋ次の論理積出力をその論理
積演算素子１１６から得る。一方、次数がｋ次未満の非
線形変換関数回路１０３では、線形フィードバックシフ
トレジスタ１０１の各レジスタ（Ｄフリップフロップ）
の出力を入力にして１ビットの非線形変換値を出力す
る。上記した論理積演算素子１１６からのｋ次の論理積
出力と、非線形変換関数回路１０３からの非線形変換値
は、排他的論理和演算素子１０６において排他的論理和
の演算が行われて擬似乱数として出力される。上記のよ
うに構成して動作させることで、図５（図１）の線形フ
ィードバックシフトレジスタを用いて、線形複雑度が理
論的に上記数式（数２）以上である高速にストリーム暗
号方式の暗号を生成可能なフィルタジェネレータ（擬似
乱数発生装置）を提供することを提供することができ
た。

【００１８】

【発明の効果】上記のように本発明では、同期信号に同
期して動作する複数段のレジスタと各レジスタ間に排他
的論理和演算素子を有し、各レジスタに初期値の設定
後、最終段のレジスタの設定値と各排他的論理和演算素
子毎に設定された所定値との論理積のフィードバック値
を排他的論理和演算素子に入力し、排他的論理和演算素
子では前段のレジスタの出力値とフィードバック値の排
他的論理和演算を行い次段のレジスタに出力する線形フ
ィードバックレジスタを用いて、線形フィードバックレ
ジスタの初段から連続する所定段数のレジスタ値の論理
積により構成される最高次の項を有する非線形変換関数
を用いて線形フィードバックレジスタの各レジスタ値を
非線形変換して１ビットの擬似乱数出力を同期信号毎に
出力する非線形変換関数回路により、高速で、且つ、暗
号用として安全に使用で擬似乱数発生装置を提供するこ
とができる。

【図面の簡単な説明】

【図１】本発明の一実施形態の構成を示すブロック図で
ある。

【図２】ストリーム暗号装置の概略構成を示すブロック
図である。

【図３】フィルタジェネレータの構成を示すブロック図
である。

【図４】線形フィードバックシフトレジスタの概略構成
を示すブロック図である。

【図５】図４と異なる線形フィードバックシフトレジス
タの概略構成を示すブロック図である。

【符号の説明】

１００、２０１、３００・・・擬似乱数発生装置、１０
１、３０１、４００、５００・・・線形フィードバック
シフトレジスタ、１０２、１０３、３０２、・・・非線
形変換関数回路、１０４、２０３、・・・初期値設定用
入力端子、１０５、２０４、３０４、・・・クロック入
力用端子、１０６、３０５・・・擬似乱数出力端子、１
０７〜１１１、４０２、５０２・・・Ｄフリップフロッ
プ素子、１１２〜１１５、２０２、４０１、５０１・・
・排他的論理和演算素子、１１６、・・・論理積演算素
子、２００・・・ストリーム暗号装置、２０５・・・平
文入力端子、２０６・・・暗号文出力端子、３０３・・
・シフトレジスタ初期値設定用入力端子

【手続補正書】

【提出日】平成１０年８月１２日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】０００３

【補正方法】変更

【補正内容】

【０００３】次に、上記した図２に示す擬似乱数発生装
置２０１の一例である、フィルタジェネレータの構成を
示すブロック図である図３を用いてフィルタジェネレー
タを説明する。擬似乱数発生装置３００は、上記したよ
うに図２に示す擬似乱数発生装置２０１の一例としての
フィルタジェネレータである。線形フィードバックシフ
トレジスタ３０１は、擬似乱数を発生させるための元に
なる数値を得るためのレジスタである。非線形変換関数
回路３０２は、上記線形フィードバックシフトレジスタ
３０１の各レジスタの値を入力として非線形変換関数に
より変換して擬似乱数を生成して出力する。シフトレジ
スタ初期値設定用入力端子３０３は、非線形フィードバ
ックシフトレジスタ３０１の各レジスタへ初期値を設定
するための入力端子である。クロック入力用端子３０４
は、線形フィードバックシフトレジスタ３０１へ同期用
のクロックを入力する入力端子である。擬似乱数出力端
子３０５は、非線形変換関数回路３０２から出力された
擬似乱数系列を出力する端子であり、その出力は、例え
ば、図２に示す排他的論理和演算回路２０２に入力され
るものである。ここで、図３に示すフィルタジェネレー
タの暗号学的強度を示す指標の１つである線形複雑度に
ついて説明する。線形複雑度は、擬似乱数出力端子３０
５からの擬似乱数系列の出力を模倣することが可能であ
る等価な線形フィードバックシフトレジスタのレジスタ
長で定義される。また、線形フィードバックシフトレジ
スタの初期値は、その線形フィードバックシフトレジス
タ内のある１個のレジスタの値をその線形フィードバッ
クシフトレジスタのレジスタ長の２倍分だけ特定できれ
ば、その特定値に基づいた連立１次方程式を解くことで
決定することができる。従って、レジスタ長で定義され
る線形複雑度の小さいフィルタジェネレータの擬似乱数
系列は、初期値を得るのに必要なそのレジスタ長の２倍
分のレジスタの値も少ないことになるので、擬似乱数系
列は容易に推定が可能で、暗号用としての使用は難し
い。線形フィードバックシフトレジスタのレジスタ長と
その中の１個のレジスタの値の関係については、更に、
レジスタ長がＬである線形フィードバックシフトレジス
タの１個のレジスタの値がクロック入力により変遷する
周期が２^Ｌ−１で繰り返されるときに、その周期的なレ
ジスタの値の系列をｍ系列であると言う。そして、ある
時刻ｔにおけるｍ系列のレジスタ値をｓ（ｔ）で表し、
数式（数１）の線形複雑度は、理論的に２項係数の数式
（数２）以上であることが、文献（ＲａｉｎｅｒＡ．Ｒ
ｕｅｐｐｅｌ著の“Ａｎａｌｙｓｉｓ ａｎｄ Ｄｅｓ
ｉｇｎｏｆ ｓｔｒｅａｍ Ｃｉｐｈｅｒｓ，”Ｓｐｒ
ｉｎｇｅｒ−Ｖｅｒｌａｇのｐ８４−８６）により証明
されている。但し、ｆの最高次数はｋ未満であり、且
つ、次の数式（数３）の最大公約数を満たすことが条件
となっている。

【手続補正２】

【補正対象書類名】明細書

【補正対象項目名】０００７

【補正方法】変更

【補正内容】

【０００７】

【数４】この図４に示す線形フィードバックシフトレジ
スタで上記した線形複雑度を保証するためには、数式
（数４）の非線形関数の最高次数の項において、上記数
式（数３）を満たすδの間隔で連続するｋ個のレジスタ
により線形フィードバックシフトレジスタを構成すれ
ば、上記線形複雑度以上の複雑度が得られるので保証で
きることになる。一方、線形フィードバックシフトレジ
スタとして、図４に示したもの以外の構成のものでは図
５に示すものが知られている。この図５に示した線形フ
ィードバックシフトレジスタでは、図４に示したものよ
りも高速で動作が可能である。その高速動作が可能な理
由としては、次の理由による。線形フィードバックシフ
トレジスタ５００の各レジスタを構成するＤフリップフ
ロップ５０２の処理による遅延時間をｕ、Ｄフリップフ
ロップ５０２間の排他的論理和演算素子５０１の処理に
よる遅延時間をｖとし、比較するために、図４に示す線
形フィードバックシフトレジスタ４００の各レジスタを
構成するＤフリップフロップ４０２の処理による遅延時
間も図５に示すものと同様にｕ、排他的論理和演算素子
４０１の処理による遅延時間も図５に示すものと同様に
ｖとすると、図４に示す線形フィードバックシフトレジ
スタの場合には、各レジスタ間で最も遅延の起こる部分
は、最終段のＤフリップフロップＸ_Ｌ（ｔ）からＬ−１
個の排他的論理和演算素子を経て、初段のＤフリップフ
ロップＸ_１（ｔ）に至るフィードバック経路であり、そ
の遅延時間は次の数式（数５）で示される。

Claims (1)

【特許請求の範囲】
1. 【請求項１】 同期信号に同期して動作する複数段のレ
   ジスタと各レジスタ間に排他的論理和演算素子を有し、
   前記各レジスタに初期値の設定後、最終段のレジスタの
   設定値と前記各排他的論理和演算素子毎に設定された所
   定値との論理積のフィードバック値を前記排他的論理和
   演算素子に入力し、該排他的論理和演算素子では前段の
   レジスタの出力値と前記フィードバック値の排他的論理
   和演算を行い次段のレジスタに出力する線形フィードバ
   ックシフトレジスタと、前記線形フィードバックシフト
   レジスタの初段から連続する所定段数のレジスタ値の論
   理積により構成される最高次の項を有する非線形変換関
   数を用いて前記線形フィードバックシフトレジスタの各
   レジスタ値を非線形変換して１ビットの擬似乱数出力を
   前記同期信号毎に出力する非線形変換関数回路と、前記
   線形フィードバックレジスタに初期値を設定する初期値
   設定手段と、前記線形フィードバックシフトレジスタに
   同期信号を入力する同期信号入力手段とを有することを
   特徴とする擬似乱数発生装置。