JP4828068B2

JP4828068B2 - コンピュータで効率的な線形フィードバック・シフト・レジスタ

Info

Publication number: JP4828068B2
Application number: JP2001549180A
Authority: JP
Inventors: ドリスコール，ケヴィン
Original assignee: Honeywell International Inc
Current assignee: Honeywell International Inc
Priority date: 1999-12-02
Filing date: 2000-12-01
Publication date: 2011-11-30
Anticipated expiration: 2020-12-01
Also published as: EP1234227A2; JP2004505289A; WO2001048594A3; CA2392706A1; US6763363B1; WO2001048594A2; AU4900401A

Description

【０００１】
（発明の分野）
本発明は、一般には、擬似乱数ジェネレータ（ＰＲＮＧ）に関し、より詳細には、平文と組み合わせることにより平文を暗号化して暗号文にするためのキーストリームや、暗号文と組み合わせることにより暗号文を解読して平文にするためのキーストリームなどの擬似ランダム・ビットのキーストリームを生成するために、線形フィードバック・シフト・レジスタを用いる秘密鍵ストリーム暗号の暗号システムなどのシステムに関する。
【０００２】
（発明の背景）
擬似乱数ジェネレータ（ＰＲＮＧ）は、暗号システム、モンテ・カルロ・シミュレーション・システム、ゲーム、およびヒューリスティックな設計システム（例えばゲート・アレイの配置やルーティングのシステム）など、各種のシステムで使用される。詳細には、暗号システムは、許可された受信者しかその暗号文を元の平文に変換できないように、暗号法を行って平文を暗号文に変換する。暗号化（ｅｎｃｒｙｐｔｉｏｎ、ｅｎｃｉｐｈｅｒｉｎｇ）は、平文を暗号文に変換するプロセスである。復号（ｄｅｃｒｙｐｔｉｏｎ、ｄｅｃｉｐｈｅｒｉｎｇ）は、暗号文を平文に変換するプロセスである。
【０００３】
暗号システムでは、暗号鍵と呼ばれるパラメータを用いて、平文が無許可の者によって容易に暴かれるのを妨げる。送信側は、所与の平文を、特定の暗号鍵によって選択される多種の可能な暗号文に変換する。暗号文を受信する側は、解読鍵と称されるパラメータを用いてその暗号文を解読する。公開鍵の暗号システムでは、暗号鍵は公開するが解読鍵は秘密のままにする。したがって、公開鍵暗号システムでは、解読鍵は、暗号鍵から推論することが計算上不可能でなくてはならない。秘密鍵の暗号システムでは、通例、送信側および受信側が、暗号化および解読の両方に使用される共通鍵を共用する。このような秘密鍵の暗号システムでは、共通鍵は変更することができ、また秘密の状態に保持しなければならない。
【０００４】
一般に、秘密鍵暗号システムは、ブロック暗号の暗号システムか、またはストリーム暗号の暗号システムとして実装される。ブロック暗号の暗号システムは平文をブロックに分割し、ステートレスな変換を使用して各ブロックを個別に暗号化する。ブロック暗号の暗号システムでは、１つの固定した共通秘密鍵を用いて特定の平文ブロックの異なる出現を暗号化した場合、それらの出現はすべて、同じ対応暗号文ブロックに暗号化される。したがって、ブロック・サイズは、暗号文ブロック間の各種パターンの出現頻度を分析する暗号解読者による攻撃を達成させないために、十分な大きさに選択することが好ましい。ブロック・サイズの例は、６４ビットおよび１２８ビットである。
【０００５】
ストリーム暗号の暗号システムでは、通例、暗号化の進行に従って展開するステートフルな変換を使用して、または単語単位で平文を暗号化する。暗号文のバイナリ・データ・シーケンスとして送信するために平文バイナリ・データ・シーケンスを暗号化する際、共通の秘密鍵は、擬似ランダム・ビット・ジェネレータを制御してキーストリームと呼ばれる長いバイナリ・データ・シーケンスを作成するパラメータである。ストリーム暗号の暗号システムは暗号コンバイナを含み、これはキーストリームと平文のシーケンスを組み合わせる。暗号コンバイナは、通例、ビットワイズのモジュロ２加算を実行する、排他的論理和（ＸＯＲ）のビットワイズ論理関数を用いて実装される。暗号コンバイナは、暗号文を生成する。受信側では、共通の秘密鍵が、受信側の擬似ランダム・ビット・ジェネレータを制御して解読キーストリームを生成する。解読キーストリームは解読コンバイナと組み合わされて、暗号文を解読し、受信者に平文を提供する。受信側の解読コンバイナの動作は、送信側の暗号コンバイナ動作の逆でなければならない。この理由から、最も一般的なコンバイナ動作は、それ自体の逆であるビットワイズのＸＯＲである。
【０００６】
ストリーム暗号の暗号システムの問題の１つは、短くランダムな鍵から、長く、統計的に均質で、予測することが不可能なキーストリーム中のバイナリ・データ・シーケンスを生成することが難しいことである。暗号法のキーストリームでは、そのデータの妥当な部分と十分なコンピュータ資源を与えられても、そのシーケンスについてそれ以上知ることを不可能にするためにそのようなシーケンスが望ましい。
【０００７】
暗号的にセキュアなキーストリームＰＲＮＧには、４つの一般的な要件がある。第１に、キーストリームの周期は、送信メッセージの長さに対応するのに十分な長さでなければならない。第２に、キーストリームの出力ビットは、良好な統計的プロパティを有さなければならない（例えば、値が均質に分散しているなど）。第３に、キーストリームの出力ビットは、生成が容易でなければならない。第４に、キーストリームの出力ビットは、予測が困難なものでなければならない。例えば、ＰＲＮＧと、最初のＮ個の出力ビットａ（０）、ａ（１）、．．．、ａ（Ｎ−１）を与えられた場合に、シーケンス中の（Ｎ＋１）番目のビットａ（Ｎ）を予測することが、５０％以上の確率で計算的に不可能でなければならない。すなわち、キーストリームの出力シーケンスの所与の部分を与えられた場合に、暗号解読者が、それより後の他のビットまたはそれより前の他のビットを生成することができてはならない。
【０００８】
ストリーム暗号の暗号システムで用いられるＰＲＮＧには、フィードバック・シフト・レジスタ（ＦＳＲ）をしばしば利用するが、このレジスタは、Ｎ個の記憶要素と、それより前に生成された要素ａ（ｔ−Ｎ）、ａ（ｔ−Ｎ＋１）、．．．、ａ（ｔ−１）との関係でシーケンスの新しい各要素ａ（ｔ）を表すフィードバック関数とを含む。ＦＳＲの個々の記憶要素はステージと呼ばれ、バイナリ信号ａ（０）、ａ（１）、ａ（２）、．．．．、ａ（Ｎ−１）が初期データとしてステージにロードされて、キーストリーム・シーケンスを生成する。ＦＳＲによって生成されるキーストリーム・シーケンスの周期は、ステージの数と、フィードバック関数の詳細の両者によって決まる。Ｎ個のステージを持つＦＳＲが正則のフィードバック関数を使用して生成するキーストリーム・シーケンスの最大の周期は２^Nであり、これはＮ個のステージを有するＦＳＲの可能な状態の数を表す。
【０００９】
フィードバック関数が線形であるか非線形であるかに応じて、ＦＳＲはそれぞれ、線形フィードバック・シフト・レジスタ（ＬＦＳＲ）、または非線形フィードバック・シフト・レジスタ（ＮＬＦＳＲ）と呼ばれる。
【００１０】
詳細には、ＬＦＳＲは、ストリーム暗号の暗号システム用の多くの擬似ランダム・ビット・ジェネレータで用いられる。長いシーケンス長と良好な統計が保証されたＬＦＳＲを設計するのに数学を利用することができるため、ＬＦＳＲは、大半の他のＰＲＮＧよりも好まれる。ＬＦＳＲのフィードバック関数は、
a(t)=c₁a(t-1)XORc₂a(t-2)XOR...XORc_N-1a(t-N+1)XORc_Na(t-N)
の形になり、ｃ_iはセット｛０，１｝の要素である。非ゼロのｃ_iと関連付けられる各ステージは、タップと称される。ＬＦＳＲのフィードバック関数は、次のフィードバック多項式と称されるもので形式的に表すことができる。
【００１１】
f(x)=1+c₁X+c₂X^N-2+...+c_N-1X^N-1+c_NX^N
ここで、中間にあるＸは、数学記号以外の意味を持たない。このフィードバック多項式により、キーストリーム出力シーケンスの周期と統計的振る舞いを決定する。自明の出力を回避するために、ゼロ状態は初期設定から排除すべきである。これにより、ＬＦＳＲの可能な最大周期が２^N−１に制限される。
【００１２】
一般に、出力シーケンスの可能な最大周期２^N−１を生成するには、ＬＦＳＲのフィードバック多項式ｆ（ｘ）を原始多項式にしなければならない。原始のフィードバック多項式を用いるＬＦＳＲによって生成されるシーケンスは、最大長ＬＦＳＲシーケンス、または単にｍ−シーケンスと呼ばれる。しかし、ｍ−シーケンスは、さらに暗号変換を行わないとキーストリームとして使用することができない。この暗号変換を行わないと、Ｎ個のステージを有するＬＦＳＲの秘密内容（すなわち、ＬＦＳＲの初期状態とＬＦＳＲのフィードバック関数）の鍵は、出力シーケンスの２Ｎ個の連続ビットだけから求めることができる。
【００１３】
所与の出力シーケンスを生成する最短のＬＦＳＲのフィードバック多項式を見つけるための効率的な総合（ｓｙｎｔｈｅｓｉｓ）手順が存在する。このようなＬＦＳＲの長さは、シーケンスの線形複雑度と称される。この結果、暗号システムで使用するのに適したＬＦＳＲは、ＬＦＳＲが生成するシーケンスの線形複雑度について、キーに依存しない、十分に大きな下限を保証しなければならない。
【００１４】
ソフトウェアに実装される従来のＬＦＳＲは特に動作が遅い。これは、新しい各１ビットの要素ａ（ｔ）を得、ＬＦＳＲの実装に応じてＬＦＳＲの各ビットを左または右にシフトすることにより、その新しい要素ａ（ｔ）をＬＦＳＲ中にシフトするのに比較的多数の命令を実行する必要があるためである。従来のＬＦＳＲに伴うこの問題の詳細な例は、本明細書の好ましい実施形態の項で提供する。
【００１５】
ソフトウェアに実装するＬＦＳＲは非常に動作が遅いため、各種の技術により、ソフトウェアに実装したＬＦＳＲの速度の向上が試みられた。例えば、行列乗算を使用して、複数ビット単位でＬＦＳＲを進める。別の速度向上技術は、パラレルのＬＦＳＲを実行するものである。しかし、パラレルのＬＦＳＲは初期化に時間がかかり、多くの場合それに対応するシリアルの実装に比べて多くのメモリを占める。従来の速度向上技術はいずれも、ＬＦＳＲをソフトウェアに実装する場合には著しい時間の短縮を提供しない。
【００１６】
上記のような理由と、本明細書の好ましい実施形態の説明の項に詳細に示すその他の理由から、ソフトウェアに実装されたＬＦＳＲを使用し、また、擬似乱数を生成するＬＦＳＲに使用される従来の速度向上技術に比べて大幅に速度の速いＰＲＮＧが望まれる。
【００１７】
（発明の概要）
本発明は、状態を有する線形フィードバック・シフト・レジスタＬＦＳＲを含む擬似乱数ジェネレータ（ＰＲＮＧ）を提供する。このＬＦＳＲは、Ｎビットのバイナリ・データを記憶するＮ個の記憶要素（ステージ）を含み、この記憶要素は、ワード長Ｍを有するｗ個のワードに分割される。Ｔ個のタップ・ソースが、ステージからバイナリ・データを提供する。各タップ・ソースは複数のビットを有するが、これはＭの倍数であり、Ｍの倍数であるステージで開始または終了する連続したＬＦＳＲステージから取られる。ＬＦＳＲはまた、Ｔ個のタップ・ソースに結合され、一時的な値を提供する線形フィードバック関数も含み、この一時的な値は、Ｍの倍数である複数ビットを有し、Ｔ個のタップ・ソースから提供されるバイナリ・データの線形関数である。ＬＦＳＲの状態は、記憶要素中のバイナリ・データをＭの倍数ビット単位でシフトし、シフトの結果そのままでは空になる記憶要素を埋める一時的な値を提供することによって進められる。したがって、ＬＦＳＲを進めるたびに、ＰＲＮＧシーケンス中にＭの倍数個の新しいビットが生成される。
【００１８】
各タップ・ソースの１ビットは、タップ・ビットである。このタップ・ビットは、ＬＦＳＲを左シフトした場合は最上位ビットとなり、ＬＦＳＲを右シフトした場合には最下位ビットとなる。
【００１９】
ＰＲＮＧの一実施形態では、ＬＦＳＲをソフトウェアに実装する。別の実施形態では、ＬＦＳＲをハードウェアに実装する。ＬＦＳＲのソフトウェア実装の一実施形態では、複数のコンピュータ・ワード・サイズにアクセスするコンピュータ・システムにＬＦＳＲを実装するが、この場合各コンピュータ・ワード・サイズはＭビットを含む。ＬＦＳＲのソフトウェア実装の一実施形態では、記憶要素中のバイナリ・データをＭの倍数のビットずつシフトするためにワードを移動する代わりに、レジスタまたは位置のリネームを使用する。
【００２０】
一実施形態では、Ｎは、Ｍの倍数よりも１小さい（例えば、Ｍ＝３２ビットの場合、Ｎ＝１２７またはＮ＝１５９）。この理由により、１回のクロック・パルスに応答してＬＦＳＲを左シフトする実施形態では、最下位のＬＦＳＲワードの最下位ビットはゼロになる。ＬＦＳＲは、右シフトのＬＦＳＲに実装することもできる。
【００２１】
一実施形態では、ＬＦＳＲの状態が進むたびに、一時的な値が１ビット左にシフトされ、ゼロがシフトされて最下位ビットになり、次いで最下位のＬＦＳＲワード中に記憶される。一時的な値を１ビットずつ左シフトした結果生じる損失ビットは、キャリーフラグに記憶される。次いで、下位から２番目のＬＦＳＲワードの最下位ビットにそのキャリーフラグを記憶して、その前の反復における一時的な値の左シフトによってゼロになった最下位ビットと入れ替える。この実施形態の一形態では、下位から２番目のＬＦＳＲワードの最下位ビット中にキャリーフラグを記憶することは、ＡＤＤＷＩＴＨＣＡＲＲＹ命令でそのワードにキャリーフラグを加えることによって行われる。
【００２２】
本発明によるストリーム暗号の暗号システムの一形態は、キーを受け取り、キーストリームを提供するＰＲＮＧを含む。このＰＲＮＧは、ワード長ＭのＬＦＳＲ出力ワードを提供するために、本発明によるワード単位でシフトするＬＦＳＲを含む。ストリーム暗号の暗号システムは、第１のバイナリ・データ・シーケンスとキーストリームを組み合わせて、第２のバイナリ・データ・シーケンスを提供する暗号コンバイナも含む。暗号化動作では、暗号コンバイナが暗号化コンバイナとなり、第１のバイナリ・データ・シーケンスが平文のバイナリ・データ・シーケンスとなり、第２のバイナリ・データ・シーケンスが暗号文のバイナリ・データ・シーケンスとなる。解読動作においては、暗号コンバイナが解読コンバイナとなり、第１のバイナリ・データ・シーケンスが暗号文のバイナリ・データ・シーケンスとなり、第２のバイナリ・データ・シーケンスが平文のバイナリ・データ・シーケンスとなる。
【００２３】
本発明によるＰＲＮＧはワード単位でシフトするＬＦＳＲを含み、これは、擬似乱数を生成するＬＦＳＲに使用される従来の速度向上技術に比べてはるかに高速のソフトウェアに実装することができる。
【００２４】
（好ましい実施形態の説明）
以下の好ましい実施形態の詳細な説明では、本明細書の一部をなす添付図面を参照するが、これらの図面には、本発明を実施することが可能な特定の実施形態を実例として示している。この他の実施形態を利用することができ、また、本発明の範囲から逸脱することなく構造的または論理的な変更を行ってよいことを理解されたい。したがって、以下の詳細な説明は制限的な意味に解釈すべきでなく、本発明の範囲は頭記の特許請求の範囲によって定義する。
【００２５】
本発明による秘密鍵ストリーム暗号による暗号システムを、ブロック図の形で図１の２０に概略的に示す。ストリーム暗号の暗号システム２０は、コンピュータ・システムなどの送信側２２、およびコンピュータ・システムなどの受信側４２を含む。
【００２６】
送信側２２は、擬似乱数ジェネレータ（ＰＲＮＧ）２４、および暗号化コンバイナ２６を含む。ＰＲＮＧ２４は秘密鍵３２を受け取り、これがＰＲＮＧ２４を制御することにより、暗号化コンバイナ２６に提供される暗号キーストリーム２８が生成される。図１に示す実施形態では、初期化ベクトル３４もＰＲＮＧ２４に提供され、複数のメッセージに対して同じ秘密鍵３２を使用してＰＲＮＧ２４を制御した場合でも、暗号キーストリーム２８が同じものにならないことが保証される。暗号化されたすべてのメッセージがわずかに異なることを保証するために、初期化ベクトル３４は真の乱数として実施することができる。
【００２７】
平文３０も暗号化コンバイナ２６に提供される。平文３０は、バイナリ・データ・シーケンスである。暗号化コンバイナ２６は、平文３０と暗号キーストリーム２８を組み合わせて暗号文３６を形成するが、この暗号文もバイナリ・データ・シーケンスである。一実施形態では、暗号化コンバイナ２６は、ビットワイズのモジュロ２加算を実行する排他的論理和（ＸＯＲ）のビットワイズ論理関数を用いて実装される。
【００２８】
受信側４２は、ＰＲＮＧ４４、および暗号化コンバイナ４６を含む。ＰＲＮＧ４４は秘密鍵３２’を受け取るが、これは秘密鍵３２と同じ秘密鍵である。ＰＲＮＧ４４は秘密鍵３２’によって制御されてキーストリーム４８を生成し、これが暗号化コンバイナ４６に提供される。図１に示す実施形態では、初期化ベクトル３４と同じ初期化ベクトルである初期化ベクトル３４’がＰＲＮＧ４４に提供され、所与の秘密鍵３２／３２’および初期化ベクトル３４／３４’について、暗号キーストリーム４８が暗号キーストリーム２８と同じものになることを保証する。
【００２９】
解読コンバイナ４６は暗号文３６を受け取り、暗号文３６と解読キーストリーム４８を組み合わせて平文３０’を生成するが、この平文は、平文３０と実質的に一致するバイナリ・データ・シーケンスである。暗号キーストリーム２８を使用して平文３０を暗号化して暗号文３６を形成し、暗号キーストリーム２８と同じものである解読キーストリーム４８を使用して、暗号文３６を解読して平文３０’を形成することができるように、解読コンバイナ４６は、暗号化コンバイナ２６のコンバイナ動作の逆のコンバイナ動作を有さなくてはならない。この理由により、最も一般的な暗号コンバイナの動作はビットワイズのＸＯＲになり、これは暗号化および解読どちらのコンバイナ動作にも使用することができる。
【００３０】
本明細書の発明の背景の項で述べたように、ＰＲＮＧ２４および４４は、暗号的にセキュアなキーストリーム２８および４８を生成するために、以下のような一般的特性を備えるとよい。第１に、キーストリームの周期は、送信メッセージの長さに対応するのに十分な大きさでなければならない。第２に、キーストリームの出力ビットは生成が容易でなければならない。第３に、キーストリームの出力ビットは予測が難しいものでなければならない。
【００３１】
図１の暗号システム２０の送信側２２または受信側４２を、図２にブロック図の形で概略的に示し、この図ではＰＲＮＧ２４／４４をより詳細に表している。本明細書では、本発明によるＰＲＮＧを利用する暗号システムとの関連で本発明を説明するが、本発明によるＰＲＮＧは、暗号システム、モンテ・カルロ・シミュレーション・システム、ゲーム、およびヒューリスティックな設計システム（例えばゲート・アレイの配置やルーティングのシステムなど）などの各種のシステムで使用することができる。ＰＲＮＧ２４／４４は、線形フィードバック・シフト・レジスタ（ＬＦＳＲ）１００を含む。ＬＦＳＲ１００は、Ｎ個の記憶要素１０２と、それまでに生成された要素ａ（ｔ−Ｎ）、ａ（ｔ−Ｎ＋１）、．．．、ａ（ｔ−１）との関係でシーケンスの新しい各要素ａ（ｔ）を表す線形フィードバック関数１０４とを含む。ＬＦＳＲの記憶要素１０２はステージと呼ばれ、バイナリ信号ａ（０）、ａ（１）、ａ（２）、．．．、ａ（Ｎ−１）が初期データとしてステージにロードされて、キーストリーム・シーケンスを生成する。
【００３２】
ＬＦＳＲの記憶要素１０２は、ＬＦＳＲ０、ＬＦＳＲ１、．．．、ＬＦＳＲ（ｗ−１）として表される、ワード長Ｍのｗ個のＬＦＳＲワードに分割される。ＬＦＳＲ０は、その最下位ビット（ＬＳＢ）に０ビットを含む。これは、ＬＦＳＲ１００が、良好な統計を有する最大長のシーケンスを提供するために、線形フィードバック関数１０４として表す原始多項式のフィードバック多項式ｆ（ｘ）を有さなくてはならないからである。周知の数学によると、原始多項式にするには、記憶要素の数Ｎは８の倍数であってはならない。各ワード長Ｍが３２ビットである場合、Ｎおよびｗの適切なサイズの例は、Ｎ＝１２７、ｗ＝４と、Ｎ＝１５９、ｗ＝５である。
【００３３】
ＬＦＳＲを使用する暗号システムの大半は、特定の平文に対する攻撃を防ぐために、ＬＦＳＲの出力を非線形にする手段を組み込んでいる。暗号解読者による平文攻撃は、特定の平文を知り、暗号テキストを観察してキーストリームに関する情報を取り出し、そこから逆をたどってＬＦＳＲの秘密内容（すなわち、ＬＦＳＲの初期状態と、ＬＦＳＲのフィードバック関数）の鍵を求めることによって行われる。ＬＦＳＲは線形であるので、十分な平文が暗号解読者に知られた場合には、初期状態と線形フィードバック関数を突き止めることが可能である。非線形化技術には、「クロック制御」（ＬＦＳＲを擬似ランダムに進める）、ＬＦＳＲ出力の非線形変換、および複数ＬＦＳＲの非線形の組み合わせなどがある。これらの手段のいずれか、またはすべてを本発明に使用することができる。図２で、任意選択の後処理プロセッサ１１０を用いて、非線形フィルタリングなどＬＦＳＲ１００の出力の後処理を行うことによりＬＦＳＲの出力を非線形化し、特定の平文攻撃を防止する。図２に示す実施形態では、ＬＦＳＲ１００からの出力は、最上位ワードＬＦＳＲ（ｗ−１）から提供される。他の実施形態では、ＬＦＳＲ１００の出力は、特定のＬＦＳＲ１００の特性に応じて、他のＬＦＳＲワード（すなわちＬＦＳＲ０、ＬＦＳＲ１、．．．、ＬＦＳＲ（ｗ−２））の選択されたものから得られる。
【００３４】
従来のビット単位のＬＦＳＲを、図３の２００に概略的に示す。従来のＬＦＳＲ２００は、Ｎ個の記憶要素２０２を含み、これはＬＦＳＲ０、ＬＦＳＲ１、．．．、ＬＦＳＲ（ｗ−１）として表す、ワード長Ｍのｗ個のワードに分割される。図３に示すＬＦＳＲ２００の実施形態では、ＸＯＲ論理関数２０４によって線形フィードバック関数が実行される。ＸＯＲ論理関数２０４は、使用されるビットが原始多項式を表すように、最上位ワードＬＦＳＲ（ｗ−１）の最上位ビット（ＭＳＢ）と、１つまたは複数の他のワードの１つまたは複数の他のビットにＸＯＲ論理演算を行う。ＬＦＳＲは左にシフトされ、ＸＯＲ論理関数２０４からの出力は、ＬＦＳＲ０の２番目に上位のＬＳＢに供給される。この場合も、最大の長さと良好な統計を提供するために、ＬＦＳＲ２００のフィードバック多項式ｆ（ｘ）が原始多項式でなければならないので、ＬＦＳＲ０は、そのＬＳＢ位置にゼロ・ビットを含む。したがって、記憶要素２０２の数Ｎは８の倍数であってはならない。
【００３５】
次の擬似ＣコードＩは、１２７ビット、２タップの従来のビット単位の左シフトＬＦＳＲ２００を、３２ビット・ワードのコンピュータ・システムに実装するものである。

上記の擬似ＣコードＩから分かるように、１２７ビット、２タップの従来型のビット単位のＬＦＳＲ２００を３２ビット・ワードのコンピュータ・システムに実装する場合、新しい各１ビット要素ａ（ｔ）を得て、その新しい要素ａ（ｔ）を左シフトして１２７ビットの従来型ビット単位ＬＦＳＲ２００に入れるには、およそ１７個の命令が必要となる。さらに、新しい３２ビット・ワードを得て、その全体を左シフトして従来のビット単位ＬＦＳＲ２００に入れるには、１ワードにつき３２ビット、１ビットにつき１７個の命令、すなわち５４４個の命令（およびループ・オーバーヘッド）が必要となる。したがって、上記の擬似Ｃコードで表すような従来のビット単位のＬＦＳＲ２００のソフトウェア実装は、きわめて動作が遅い。
【００３６】
本発明によるワード単位の左シフトＬＦＳＲを、図４の３００に概略的に示す。以下の説明ではワード単位の左シフトＬＦＳＲ３００について説明するが、本発明は、ワード単位の右シフトＬＦＳＲにも等しく該当する。ワード単位でシフトするＬＦＳＲ３００は、ＬＦＳＲ０、ＬＦＳＲ１、．．．、ＬＦＳＲ（ｗ−１）で表す、ワード長Ｍのｗ個のワードに分割されたＮ個の記憶要素３０２を含む。図４に示すＬＦＳＲ３００の実施形態では、ワード長Ｍのワード中のビット数Ｍに対応するＸＯＲ論理関数３０４ａ〜３０４ｍによって、線形フィードバック関数が実行される。本発明によるＬＦＳＲの代替実施形態は、否定排他的論理和（ＸＮＯＲ）の論理関数によって実行される線形フィードバック関数を含む。ＸＯＲ論理関数３０４ａ〜３０４ｍは、ＬＦＳＲ（ｗ−１）およびＬＦＳＲ１の対応するビットにＸＯＲ論理演算を行って、一時的な値すなわち記憶ワード３０６を提供する。例えば、ＬＦＳＲ（ｗ−１）のＭＳＢとＬＦＳＲ１のＭＳＢを、ＸＯＲ論理関数３０４ａで排他的論理和演算して、一時的記憶ワード３０６のＭＳＢを提供する。同様に、ＬＦＳＲ（ｗ−１）のＬＳＢを、ＸＯＲ論理関数３０４ｍによりＬＦＳＲ１のＬＳＢで排他的論理和演算して、一時的記憶ワード３０６のＬＳＢを提供する。その中間のビットにも同様に排他的論理和演算を行う。一時的記憶ワード３０６のＭＳＢは、これに対応するビット単位の実装を１ビットずつ進めるのに使用される値とちょうど同じ値を有する。一時的記憶ワード３０６のこれに次ぐ上位ビットは、これに対応するビット単位の実装を２番目のビットで進めるのに使用される値とちょうど同じ値を有する。以下同様に続き、一時的記憶ワード３０６のＬＳＢは、これに対応するビット単位の実装で生成されるＭ番目のビットと全く同じ値を有する。この場合も、良好な統計（すなわち、ＬＦＳＲ３００を最大長のＬＦＳＲとする）を提供するために、ＬＦＳＲ３００のフィードバック多項式ｆ（ｘ）を原始多項式にしなければならないので、ＬＦＳＲ０はそのＬＳＢの位置にゼロ・ビットを含む。したがって、記憶要素３０２の数Ｎは、８の倍数であってはならない。一実施形態では、ワード単位のＬＦＳＲ３００の状態は次の要領で進める。ＬＦＳＲ２の内容をＬＦＳＲ３に入れる。ＬＦＳＲ１の内容をＬＦＳＲ２に入れる。一時的記憶ワード３０６を１ビット位置で左シフトして、一時的記憶ワード３０６のＬＳＢにゼロをシフトする。一実施形態では、一時的記憶ワード３０６からＭＳＢを左シフトして、キャリーフラグに入れる。ＬＦＳＲ０の内容をＬＦＳＲ１のｍ−１のＭＳＢに入れ、キャリーフラグをＬＦＳＲ１のＬＳＢに入れる。次いで、一時的記憶ワード３０６の内容をＬＦＳＲ０に入れて、ＬＦＳＲ３００のワードの前進を完了する。
【００３７】
このように、ワード単位の左シフトＬＦＳＲ３００の状態は、一度にワード全体ずつ進む。ＸＯＲ関数３０４ａ〜３０４ｍを通じたＬＦＳＲのフィードバックは、記憶要素３０２のＴ個のタップ・ソースから選択されるが、各タップ・ソースは、コンピュータ・システムのワード・サイズＭの倍数である。８、１６、３２、または６４ビットのワードにアクセスできるＩｎｔｅｌ Pentium（Ｒ）Ｐｒｏｃｅｓｓｏｒなど、サイズＭが異なるワードにアクセスし、それを操作することができるコンピュータ・システムでは、利用可能なワード・サイズＭをいずれも使用することができる。ワード・サイズが大きいほど、ＬＦＳＲ３００の前進ごとに生成されるビットが多くなる。
【００３８】
ＬＦＳＲ３００の好ましい長さＮは、ワード・サイズＭのちょうど倍数よりも１小さくなるように選択する。ＬＦＳＲ記憶要素３０２の数Ｎは、ワード・ワイズＭのちょうど倍数にすることが望ましいが、上記のように、８の倍数であるサイズＮを有する最大長のＬＦＳＲは存在しない。
【００３９】
ワード・サイズよりも１少ないビットを使用するレジスタ（すなわちＬＦＳＲ０）（すなわちＬＦＳＲ０はＭ−１のステージ長を有する）に、一時的記憶ワード３０６に記憶された完全なワードを入れるには調整が必要である。この理由により、ＸＯＲ線形フィードバック関数３０４によって得られる一時的なワードは、まず一時的記憶ワード３０６に記憶され、その後、一時的記憶ワード３０６を１ビット左シフトしてゼロ・ビットをシフト・インし、ＭＳＢをキャリーフラグに入れる。次いでキャリーフラグがＬＦＳＲ１のＬＳＢに入れられ、その前の反復における左シフトでゼロになったそのワード中のビットに取って代わる。
【００４０】
次の擬似ＣコードＩＩは、３２ビット・ワードのコンピュータ・システムに、本発明による１２７ビット、２タップ（すなわちＴ＝２）、ワード単位の左シフトＬＦＳＲ３００を実装し、その前に説明した擬似ＣコードＩと全く同じ出力シーケンスを生成する。
擬似ＣコードＩＩ
temp = (LFSR[3]^LFSR[1])<<1; /*損失ビットをキャリーフラグに入れる*/
LFSR[3] = LFSR[2];
LFSR[2] = LFSR[1];
LFSR[1] = LFSR[0]+carry; /*ADD WITH CARRY命令を使用する*/
LFSR[0] = temp;
上記の、擬似ＣコードＩＩによる、３２ビット・ワードのコンピュータ・システムにおける、１２７ビット、ワード単位の左シフトＬＦＳＲ３００の実装から見てとれるように、本発明による、ワード単位のＬＦＳＲ３００中に左シフトされる新しい３２ビット・ワード全体を得るのに必要な命令はわずか約８個である。これは、１２７ビットの従来のビット単位のＬＦＳＲ２００に左シフトされる新しい３２ビット・ワード全体を得るのに必要とされる、上記の擬似ＣコードＩで表した５４５個以上の命令と比較する。１２７ビット、ワード単位の左シフトＬＦＳＲ３００を実装する上記の擬似ＣコードＩＩ中に記すように、左シフトを行う「ｔｅｍｐ」による損失ビットは、キャリーフラグに記憶される。したがって、ＬＦＳＲ［１］の内容をＬＦＳＲ［２］の内容に置き換える場合、現在のコンピュータの大半に存在するＡＤＤＷＩＴＨＣＡＲＲＹ命令によってキャリーフラグをＬＦＳＲ［０］の他にＬＦＳＲ［１］に加える。
【００４１】
ワード単位のＬＦＳＲ３００を実装する上記の擬似ＣコードＩＩをソフトウェア・ループで実行する場合、ソフトウェア・ループを展開して、１回の反復ごとに４つのＬＦＳＲワードをシフトすることができる。一実施形態では、「ＬＦＳＲ［］＝」演算ごとにワードを移動する代わりに、演算論理回路（ＡＬＵ）レジスタのリネームなど、レジスタまたは位置のリネームを使用する。この実施形態では、１２７ビットのＬＦＳＲとして実装された、ワード単位のＬＦＳＲ３００に左シフトされる３２ビット（あるいは任意の他のワード・サイズ）の新しいワード全体を得るのに必要な命令はわずか３つである。この３つの命令と、従来技術を使用して同じシーケンスを得るのに必要な５４４個以上の命令とを比較すると、この特定の１２７ビットＬＦＳＲの実装について、本発明のワード単位のＬＦＳＲは、従来技術によるビット単位のＬＦＳＲよりも１８０倍以上高速であることが理解できよう。６４ビット・ワードを使用すると、３つの命令で、全く同じＬＦＳＲシーケンスの６４の新しいビットを生成することができ、これはさらに２倍速くなる。
【００４２】
本発明によるワード単位のＬＦＳＲ３００はハードウェアにもソフトウェアにも実装することができるが、このワード単位のＬＦＳＲ３００は、他タイプの従来のソフトウェア実装のＬＦＳＲの代替とするのに特に有用である。
【００４３】
行列乗算演算（テーブル・ルックアップとして実装される）を用いてＬＦＳＲを複数ビット単位で進める従来の行列乗算速度向上技術は、３２ビットのワードを進めるのに１６ギガバイトのテーブルを必要とする。このテーブルは、周知のどのプロセッサの第１または第２レベルのキャッシュにも適合せず、アクセスが基本的にランダムになり、ほぼ大半のテーブル・フェッチでダブルのキャッシュ・ミスが発生する。さらに、１６ギガバイトのテーブルの初期化には長い時間がかかる。したがって、３２×３２行列乗算は、非常に多量のメモリを必要とし、上記の本発明によるワード単位のＬＦＳＲ３００よりもはるかに動作が遅くなる。
【００４４】
パラレルのＬＦＳＲを実行する従来の技術では、ワードの配列を初期化することになるので、本発明によるワード単位のＬＦＳＲ３００よりも初期化の動作がはるかに遅い。配列中のワードの数は、ステージの数と同じでなければならない。例えばステージが１２７個のＬＦＳＲは、１２７の記憶ワードを必要とする。さらに、１２７個のワードすべてをシフトしなければならないか、あるいは１２７のワードのアドレスに対してモジュラ計算（ｍｏｄ１２７）を行って、タップがあり、新しく生成されるワードが記憶されるアドレスを計算しなければならないので、新しい各出力ワードを生成する際、パラレルのＬＦＳＲは、ワード単位のＬＦＳＲ３００よりも遅くなる。
【００４５】
上記の理由により、本発明による、ソフトウェア実装のワード単位ＬＦＳＲ３００は、周知の従来型ＬＦＳＲのソフトウェア実装のいずれよりも大幅に動作が速い。したがって、本発明によるワード単位のＬＦＳＲ３００は、非常に高い周波数でビットを生成する必要がある、実時間の暗号システムで利用することができる。例えば、５００ＭＨｚのPentium（Ｒ）ＩｎｔｅｌＰｒｏｃｅｓｓｏｒで展開される上記の擬似ＣコードＩＩを実装する場合、このＬＦＳＲは、１秒につき１０ギガビット（Ｇｂｐｓ）を超える速度で進めることができる。
【００４６】
本明細書では、好ましい実施形態の説明のために、特定の実施形態を例示し、説明したが、本発明の範囲から逸脱することなく、これと同じ目的を達成すると予測される幅広い代替および／または同等の実装を、ここに示し記載した特定実施形態の代わりとすることができることは当業者には理解されよう。機械技術、電気機械技術、電気技術、およびコンピュータ技術の技術者は、本発明は各種の幅広い実施形態に実施してよいことを用意に認識されよう。本願は、本明細書で論じた好ましい実施形態の改変形態または変形形態を包含するものとする。したがって、本発明は、特許請求の範囲およびその同等物のみによって制限されるものと明白に企図する。
【図面の簡単な説明】
【図１】本発明による、秘密鍵ストリーム暗号の暗号システムのブロック図である。
【図２】擬似乱数ジェネレータをより詳細に表した、図１の暗号システムの送信側または受信側のブロック図である。
【図３】従来技術による線形フィードバック・シフト・レジスタのブロック図である。
【図４】本発明による線形フィードバック・シフト・レジスタのブロック図である。

Claims

擬似乱数ジェネレータであって、
状態を有する線形フィードバック・シフト・レジスタ（ＬＦＳＲ）であって、
ワード長Ｍを有するｗ個のワードに分割されたＮビットのバイナリ・データをともに記憶し、かつＴ個のタップ・ソースを含むＮ個の記憶要素であって、各タップ・ソースは、記憶要素からバイナリ・データを提供し、Ｍの倍数である複数のビットを有する記憶要素と、
該Ｔ個のタップ・ソースに結合され、Ｍの倍数である複数のビットを有する一時的な値を提供する線形フィードバック関数であって、一時的な値が、Ｔ個のタップ・ソースから提供されるバイナリ・データの線形関数である線形フィードバック関数と、
を含む線形フィードバック・シフト・レジスタを含み、
ＬＦＳＲの状態が、記憶要素中のバイナリ・データをＭの倍数ビット単位でシフトすることと、シフトの結果そのままでは空になる記憶要素を埋める一時的な値を提供することとによって進められ、一時的な値が１ビット左にシフトされ、ゼロが最下位ビット中にシフトされ、ついで最下位ＬＦＳＲワードに記憶される擬似乱数ジェネレータ。
ストリーム暗号の暗号システムであって、
鍵を受け取り、キーストリームを提供する擬似ランダム・ビット・ジェネレータであって、
状態を有する線形フィードバック・シフト・レジスタ（ＬＦＳＲ）であって
ワード長Ｍを有するｗ個のワードに分割されたＮビットのバイナリ・データをともに記憶し、かつＴ個のタップ・ソースを含むＮ個の記憶要素であって、各タップ・ソースが、Ｍの倍数である複数ビットを有するバイナリ・データを提供する記憶要素、および
Ｔ個のタップ・ソースに結合され、Ｔ個のタップ・ソースから提供されるバイナリ・データの線形関数である一時的記憶ワードを提供する線形フィードバック関数、
とを含み、
ＬＦＳＲの状態が、記憶要素中のバイナリ・データをＭの倍数ビット単位でシフトすることと、シフトの結果そのままでは空になる記憶要素を埋める一時的記憶ワードを提供することとによって進められ、一時的な値が１ビット左にシフトされ、ゼロが最下位ビット中にシフトされ、ついで最下位ＬＦＳＲワードに記憶される線形フィードバック・シフト・レジスタを含む擬似ランダム・ビット・ジェネレータと、第１のバイナリ・データ・シーケンスとキーストリームを組み合わせて、第２のバイナリ・データ・シーケンスを提供する暗号コンバイナと、
を含むストリーム暗号の暗号システム。
擬似乱数を生成する方法であって、
線形フィードバック・シフト・レジスタ（ＬＦＳＲ）の記憶位置にＮビットのバイナリ・データを記憶するステップであって、該Ｎビットのバイナリ・データが、ワード長Ｍを有するｗ個のワードに分割されるステップと、
該Ｎビットのバイナリ・データからバイナリ・データのＴ個のタップ・ソースを提供するステップであって、各タップ・ソースは、Ｍの倍数である複数ビットを有するバイナリ・データを提供するステップと、
Ｍの倍数である複数ビットを有し、Ｔ個のタップ・ソースから提供されるバイナリ・データの線形関数である一時的な値を提供するステップと、
記憶されたバイナリ・データを、Ｍの倍数ビット単位でシフトするステップと、
該シフト・ステップの結果そのままでは空になる記憶位置を埋める一時的な値を提供するステップであって、一時的な値が１ビット左にシフトされ、ゼロが最下位ビット中にシフトされ、ついで最下位ＬＦＳＲワードに記憶されるステップを含むステップとを含む方法。