JPH11510036A

JPH11510036A - 暗号化通信システムにおける再送信データの解読

Info

Publication number: JPH11510036A
Application number: JP9542379A
Authority: JP
Inventors: ドバーシュタイン、ケビン・ジー; パパス、スコット・ジェイ; ブライト、マイケル・ダブリュー
Original assignee: Motorola Inc
Current assignee: Motorola Solutions Inc
Priority date: 1996-05-17
Filing date: 1997-04-23
Publication date: 1999-08-31
Anticipated expiration: 2017-04-23
Also published as: EP0839417B1; PL182896B1; HK1016375A1; AU3203597A; WO1997044934A1; CN1194744A; EP0839417A1; US5809148A; BR9702266A; CA2226716C; PL324462A1; JP4124485B2; DE69722891D1; IL122521A; RU2146421C1; CA2226716A1; IL122521A0; EP0839417A4; CN1124718C; DE69722891T2

Abstract

(57)【要約】本方法は、一般に、メッセージ・インジケータ（１０１）および複数の暗号化ブロック（１０３〜１１１）からなるメッセージ（１００）を受信する段階（２０１）を含む。複数の暗号化ブロックの少なくとも一つのブロックがエラーで受信されると、第２メッセージが送信され（２１５）、この第２メッセージは前記少なくとも一つのブロックの再送信を要求する。前記少なくとも一つのブロックの再送信をエラーなしに受信すると、メッセージ・インジケータからキーストリームが生成され（２１９）、前記少なくとも一つのブロックはこのキーストリームを利用して解読される。

Description

【発明の詳細な説明】暗号化通信システムにおける再送信データの解読発明の分野本発明は、暗号化通信システムを含むがそれに限定されない、通信システムに関する。本発明と同じ譲受人で、Ｍichael Ｗ．Ｂrightらに代わって、本発明と同じ日付にて出願された米国特許第５，６９４，４７３号 ”ＤＥＣＲＹＰＴＩＯＮＯＦＲＥＴＲＡＮＳＭＩＴＴＥＤＤＡＴＡＩＮＡＮＥＮＣＲＹＰＴＥＤＣＯＭＭＵＮＩＣＡＴＩＯＮＳＹＳＴＥＭ”を参照されたい。発明の背景暗号化音声およびデータ・システムは周知である。これらのシステムの多くは、ユーザの間で一つまたはそれ以上の情報を共有することによって、機密通信を二人またはそれ以上のユーザの間で行い、この情報を知るユーザのみがメッセージを適切に解読できるようにする。一般に、音声およびデータ・メッセージを暗号化または解読するために、キー発生器（ＫＧ：key generator）が用いられる。ＫＧとは、初期開始ベクトルと、数学的関数を定義するキー変数とが与えられると、疑似ランダム・シーケンスを発生する非線形数学的関数のことである。ＫＧはキーストリーム(keystream)を出力し、このキーストリームは平文(plaintext)（暗号化されていない文）とＸＯＲ（当技術分野で周知な、排他的論理和（「ＯＲ」）関数）がとられ，暗号文(cipher text)を生成する。暗号文は、受信機に送信される。受信機は、受信した暗号文を、受信した情報に基づいて受信機によって決定されるキーストリームと排他的論理和をとり、送信装置からの平文を生成する。暗号装置および解読装置の両方は、暗号化メッセージを解読するために同じ暗号キーを有するだけでなく、同じでなければならない、すなわち、同じ暗号アルゴリズムを同じように、同じ（内部）暗号状態から同じ時間に実行しなければならない。同期データは通信チャネル上で送出され、解読装置が自身の暗号状態を暗号装置の暗号状態に同期することを可能にし、その後に着信メッセージの適切な解読が行われる。暗号同期データは、暗号化通信システムにおいて用いられる場合には、メッセージ・インジケータ（ＭＩ：message indicator）と呼ばれることが多い。暗号装置は、いくつかの動作モードのうちの一つで動作できる。暗号装置が用いる動作モードは、受信装置を送信装置に同期させる異なる方法を提供する。動作モードの一つは、出力フィードバック（ＯＦＢ：output feedback）として知られる。ＯＦＢでは、キーストリームを生成するために、同じ初期開始ベクトル（またはＭＩ）を送信側および受信側暗号装置の両方に印加する必要がある。送信機では、ＫＧはＭＩによって初期化される。暗号アルゴリズムは、キーストリームを生成するために実行される。次に、キーストリームは、キーストリームの次のブロックを生成するために、ＫＧの入力にフィードバックされる。また、フィードバックされた同じキーストリームは、データを暗号化するために用いられ、暗号文を生成する。送信機は、ＭＩおよび暗号文を受信機に送信する。受信機では、ＫＧは送信されたメッセージ・インジケータによって初期化される。暗号アルゴリズムは、キーストリームを生成するために実行される。次に、キーストリームはＫＧの入力にフィードバックされる。また、フィードバックされた同じキーストリームは、データを解読するために用いられる。データは、暗号アルゴリズムによって生成されたキーストリームと、解読すべきデータとの排他的論理和をとることによって解読される。第２の動作モードは、カウンタ・アドレッシング（ＣＡ：counter addressing ）または線形回帰(linear regression)という。ＣＡについて用いられる初期同期方法は、ＯＦＢと同じでもよい。ＣＡは、暗号装置（ＫＧ）への入力として、最長ＬＦＳＲ(maximal length linear feedback shift register)を利用する。ＣＡは、キーストリームを生成するために、同じ初期開始ベクトル（またはＭＩ）を送信側および受信側暗号装置の両方におけるＬＦＳＲに印加することを必要とする。送信機では、ＬＦＳＲはＭＩによって初期化され、生成多項式(g enerator polynomial)を実行する。ＬＦＳＲの出力は、暗号アルゴリズムの入力にフィードバックされる。暗号アルゴリズムは、キーストリームを生成するために実行される。次に、キーストリームは、暗号文を生成するために、暗号化されていない平文と排他的論理和がとられる。送信機は、ＭＩおよび暗号文を受信機に送信する。受信機では、ＬＦＳＲが送信されたＭＩで初期化される。ＬＦＳＲからの出力は、キーストリームを生成するために、暗号アルゴリズムの入力レジスタに入力される。次に、キーストリームは、データを解読するために暗号文と排他的論理和がとられる。多くのシステムでは、暗号化データと未暗号化データの両方について一貫したデータのスループット・レベルを有することが望ましい。ただし、データが受信されるとき、データがエラーで受信されることは珍しくない。多くの通信システムでは、エラーで受信されたデータ・ブロックの再送信を要求することが知られる。このようなデータの再送信は、暗号化データ・システムでは問題となる。暗号プロセスの同期性のため、選択的なリトライ・ブロックＮを解読しながら、Ｎ −１個のブロックを解読する必要がある。この特性は、暗号化データ・システムにおけるスループットを著しく低下させ、暗号化データと未暗号化データとの間でスループットに大きな差を生じさせる。一般的なシステム構成では、すべてのブロックがエラーなしに受信されるまで待ってから、メッセージを解読することが含まれる。このような方法は、最後のブロックの受信後に処理遅延を追加する。別の方法では、選択的なリトライ・ブロックＮを解読しながら、前回のＮ− １個のブロックを解読する。この方法は、選択的リトライ・ブロックＮを解読するために、（Ｎ−１）倍の解読時間がかかる。要するに、この方法は、一つのブロックを解読するために、既に解読したばかりのおそらくメッセージ全体を再度解読することを必要とする。再送信解読の問題に対する別の解決方法では、各データ・ブロックについて同期情報またはＭＩを送信する。このような方法は、メッセージを送受信するために要する時間およびエネルギを増加する。また、ＭＩの以降の再送信は、エラーで受信されて、更なる再送信を必要とすることがある。従って、解読プロセスに不必要な遅延を追加せずに、ブロックの一部の再送信が受信ユニットによって受信されてからデータを解読する方法が必要とされる。さらに、この方法は、暗号化データおよび未暗号化データの両方について一貫したデータ・スループット・レベルを提供すべきである。図面の簡単な説明第１図は、本発明による受信メッセージのブロック図である。第２図は、本発明により、メッセージの一つまたはそれ以上のブロックが再送信される場合に、メッセージを後で解読する方法を示すフローチャートである。第３図および第４図は、本発明により、メッセージの元の送信から生成されたキーストリームを保存することによって、メッセージを後で解読する方法を示すフローチャートである。第５図は、本発明により、暗号状態を周期的に保存することによって、メッセージを後で解読する方法を示すフローチャートである。第６図は、本発明により、暗号状態を計算することによって、メッセージを後で解読する方法を示すフローチャートである。好適な実施例の説明以下では、暗号化データの再送信を解読する方法について説明し、ここで再送信はメッセージ全体の送信をなさない。複数のブロックからなる暗号化データ・メッセージの最初の受信時に、受信されたブロックは、エラーであるかエラーでないかを判定される。キーストリームまたは暗号状態は、格納スペースおよび暗号時間に応じて、メッセージ全体またはメッセージの一部について生成および／または格納される。エラーで受信されたブロックの再送信の要求が行われる。再送信されたブロックがエラーなしに受信されると、キーストリームは格納から引き出されるか、あるいは暗号化データ・メッセージの初期受信から格納されたデータより生成される。このように、メッセージ全体が受信されるのを待ったり、あるいはメッセージ全体を解読するためにデータを再解読する必要がない。従って、メッセージの選択された部分の解読は、不必要な遅延または冗長な作業なく達成される。一実施例では、この方法は、メッセージ・インジケータおよび複数の暗号化ブロックからなるメッセージを受信する段階によって構成される。複数の暗号化ブロックのうちの少なくとも一つのブロックがエラーで受信されると、第２メッセージが送信され、この第２メッセージはこの少なくとも一つのブロックの再送信を要求する。この少なくとも１つのブロックの再送信をエラーなしに受信すると、メッセージ・インジケータからキーストリームが生成され、該少なくとも一つのブロックはこのキーストリームを利用して解読される。さらに、メッセージ・インジケータが初期化ベクトルを含む場合、Ｂ反復で乗じた出力フィードバック（ＯＦＢ）動作モードＮで動作する暗号アルゴリズムを実行することによって、キーストリームは生成される。メッセージ・インジケータが線形フィードバック・シフト・レジスタ（ＬＦＳＲ）ベクトルを含む場合、Ｂ反復で乗じたカウンタ・アドレッシング動作モードＮで動作する暗号アルゴリズムを実行することによって、キーストリームは生成される。ＮおよびＢはＮブロック・メッセージについて正の整数であり、Ｂはデータのビット数を表す。ブロックごとに受信されるエラーの数を含む受信メッセージのブロック図を第１図に示す。受信メッセージ１００は、一般にメッセージ・インジケータ（ＭＩ）１０１および複数の暗号化ブロック１０３〜１１１によって構成される。ＭＩ１０１は、キー発生器(key generator)またはＫＧという暗号装置の内部状態を同期するために用いられる。ブロック１（１０３）は、０エラーで受信される。ブロック２（１０５）は、１エラーで受信される。ブロック３（１０７）は、エラーなしで受信される。ブロック４（１０９）は、２エラーで受信される。ブロックＸ（１１１）は、エラーなしで受信され、ここではメッセージ１００において受信される暗号化メッセージの数を表す整数である。エラーのあるブロックを再送信することが要求されるシステムでは、再送信要求はエラーのあるブロックについて送信され、この場合、ブロック４とブロックＸとの間のすべてのブロックがエラーなしに受信されたと仮定すると、ブロック２（１０５）およびブロック４（１０９）である。メッセージの一つまたはそれ以上のブロックが通信ユニットに再送信されるときにメッセージを解読する方法を示すフローチャートを第２図に示す。この方法は、メッセージ１００が出力フィードバック（ＯＦＢ）またはカウンタ・アドレッシング（ＣＡ）暗号化モードを利用して暗号化されるときに実行される。ステップ２０１において、メッセージ１００は受信され、このメッセージはメッセージ・インジケータ１０１および複数の暗号化ブロック１０３〜１１１によって構成される。ステップ２０３において、メッセージの各ブロックは、このブロックがエラーで受信されたかどうかを判定するために調べられる。エラー検出は当技術分野で周知の機能であり、データがエラーであるいはエラーなしに受信されたことを検証するために、巡回冗長検査（ＣＲＣ）などのさまざまな手法の利用を含む。ステップ２０３においてブロックがエラーで受信されると、ステップ２０５においてこのブロックはエラーで受信されたとマークされ、プロセスはステップ２１１に進む。ステップ２０３において、ブロックがエラーなしに受信されると、プロセスはステップ２０７に進み、ここでエラーなしに受信されたブロックを即時に、すなわち、エラーで受信されたブロックの再送信を要求する前に、あるいはエラーで受信されたブロックのエラーのない再送信を受信する前に、解読すべきかどうかが判定される。ステップ２０７において、即時解読が行われる場合、プロセスはステップ２０９に進み、ここでＭＩ１０１からキーストリームが生成され、エラーなしに受信されたブロックは、ＭＩ１０１から生成されたキーストリームを利用して解読され、プロセスはステップ２１１に進む。ステップ２１１において、現在のブロックがメッセージにおける最後のブロックである場合、プロセスはステップ２１３に進み、それ以外の場合には、プロセスはステップ２０３に進む。ステップ２１５において、通信ユニットはエラーで受信されたブロックの再送信を要求する。ステップ２１７においてこのようなブロックの再送信（ＲＥ−ＴＸ）が一つまたはそれ以上のエラーで受信されると、プロセスはステップ２１５に進む。ステップ２１７においてこのようなブロックの再送信（ＲＥ−ＴＸ）がエラーなしに受信されると、プロセスはステップ２１９に進み、ここでキーストリームが生成され、ブロックは解読される。ステップ２２１において、ステップ２１５，２１７および／または２１７は必要に応じて反復される。ブロックの更なる再送信を解読する必要がある場合、プロセスはステップ２１９から反復する。更なるブロックを受信する必要がある場合、プロセスはステップ２１７から反復する。ステップ２０７において即時解読が行われなかった場合、すべてのブロックはステップ２１９において解読される。ステップ２０７において即時解読が行われた場合、以前解読されなかったすべてのブロック、すなわち通信ユニットに再送信されたブロックはステップ２１９において解読される。代替方法は、メッセージ・インジケータおよび複数の暗号化ブロックからなるメッセージを受信する段階によって構成される。キーストリームは、複数の暗号化ブロックを解読する際に用いられるメッセージ・インジケータから生成される。複数の暗号化ブロックのうち少なくとも一つのブロックがエラーで受信されると、第２メッセージが送信され、この第２メッセージはこの少なくとも一つのブロックの再送信を要求する。少なくとも１つのブロックの再送信をエラーなしに受信すると、この少なくとも一つのブロックはキーストリームを利用して解読される。メッセージの元の送信から生成されたキーストリームを保存することによって、メッセージを後で解読する代替方法を示すフローチャートを第３図のフローチャートに示す。第３図の方法を利用する場合、エラーなしに受信されたブロックは即時解読され、エラーで受信されたブロックは、元の送信されたメッセージで受信された情報から生成されるキーストリームを利用して、エラーなしに受信されたデータの再送信の受信時に解読される。ステップ３０１において、ＭＩ１０１および複数の暗号化ブロック１０３〜１１１を有するメッセージ１００が受信される。ステップ３０３において、メッセージ全体１００のキーストリームは上記のようにＭＩ１０１から生成され、必要に応じて一時的にあるいは永久に格納される。ステップ３０５において、ブロック・カウンタＮは初期化され、すなわち、Ｎは１に設定される。ステップ３０７において、ブロックＮが取り出される。ステップ３０９において、ブロックＮがエラーで受信されたかどうか判定される。ブロックＮがエラーで受信された場合、プロセスはステップ３１１に進み、ここでブロックＮはエラーで受信されたとマークされ、プロセスはステップ３１５に進む。ステップ３０９においてブロックＮがエラーなしに受信された場合、プロセスはステップ３１３に進み、ここでブロックＮは解読され、その結果が格納される。プロセスはステップ３１５に進み、ここでブロック・カウンタＮは１だけインクリメントされ、すなわち、Ｎ＝Ｎ＋１となる。ステップ３１７において、ブロックＮがメッセージ１００の最後のブロックでない場合、プロセスはステップ３０７に進む。ステップ３１７においてブロックＮがメッセージ１００の最後のブロックである場合、プロセスはステップ３１９に進む。ステップ３１９において、ステップ３０９でブロックがエラーで受信された場合、プロセスはステップ３２１に進み、それ以外の場合には、プロセスは終了する。ステップ３２１において、通信ユニットはエラーで受信されたブロックの再送信（ＲＥ−ＴＸ）を要求する。ステップ３２３においてこのブロックの再送信が一つまたはそれ以上のエラーで受信される場合、プロセスはステップ３２１に進む。ステップ３２３においてリトライ・ブロックの再送信（ＲＥ−ＴＸ）がエラーなしに受信される場合、プロセスはステップ３２５に進み、ここでリトライ・ブロックが取り出される。リトライ・ブロックとは、再送信が要求され、データ・ブロックの再送信がエラーなしに受信された、データのブロックのことである。ステップ３２７において、リトライ・ブロックはステップ３０３において生成されたキーストリームを利用して解読される。リトライ・ブロックは元の送信からのブロック番号を含み、この番号はリトライ・ブロックを解読するためにキーストリームのどの部分が必要なのかを判定するために用いられる。例えば、リトライ・ブロックがブロック９であり、各ブロックが２００ビットのデータを収容する場合、ブロック９すなわちリトライ・ブロックの前には１６００ビットのデータがある。ブロック９を解読するために用いられるキーストリームは、ブロック１の最初のビットを解読するために用いられたキーストリームの最初のビットからこのキーストリームへの１６００ビットである。ステップ３２９において、解読すべき一つまたはそれ以上のリトライ・ブロックがある場合、プロセスはステップ３２５に進み、それ以外の場合には、プロセスはステップ３３１に進む。ステップ３３１において、メッセージ１００からのすべてのブロックが適切に受信されている場合、プロセスは終了し、それ以外の場合には、プロセスはステップ３２１に進む。キーストリームは既に生成されているので、解読するステップ３１３および３２７は合成する段階、すなわち、受信された暗号文を生成／格納されたキーストリームと排他的論理和をとり、送信側装置によって当初暗号化された平文（暗号化されていない文）を生成する段階に過ぎない。排他的論理和プロセスはマイクロプロセッサ，デジタル信号プロセッサまたは第２図ないし第６図のフローチャートを実施する他の手段によって行うことができるので、受信された暗号文は解読のためにＫＧに入力する必要はない。この段階でＫＧの利用を避けることにより、かなりの時間を節約できる。なぜならば、ＫＧは、１ＭＨｚ以上のスピードで動作するマイクロプロセッサに比べてはるかに遅い（一般に６〜５０ｋＨｚ）スピードで動作するためである。メッセージの元の送信から生成されるキーストリームを保存することによって、メッセージを後で解読する特定の方法を示すフローチャートを第４図のフローチャートに示す。第４図の方法を利用するとき、メッセージ全体は、元の送信メッセージで受信された情報から生成されるキーストリームを利用して、エラーなしに受信されたデータの再送信の受信時に解読される。ステップ４０１において、ＭＩ１０１および複数の暗号化ブロック１０３〜１１１を有するメッセージ１００が受信される。ステップ４０３において、メッセージ全体１００のキーストリームは、上記のようにしてＭＩ１０１から生成され、必要に応じて一時的または永久的に格納される。ステップ４０５において、ブロック・カウンタＮは初期化され、すなわち、Ｎは１に設定される。ステップ４０７において、ブロックＮが取り出される。ステップ４０９において、ブロックＮがエラーで受信されたかどうか判定される。ブロックＮがエラーで受信された場合、プロセスはステップ４１１に進み、ここでブロックＮはエラーで受信されたとマークされ、プロセスはステップ４１３に進む。ステップ４０９においてブロックＮがエラーなしに受信された場合、プロセスはステップ４１３に進み、ここでブロック・カウンタＮは１だけインクリメントされ、すなわち、Ｎ＝Ｎ＋１となる。ステップ４１５において、ブロックＮがメッセージ１００の最後のブロックでない場合、プロセスはステップ４０７に進む。ステップ４１５においてブロックＮがメッセージ１００の最後のブロックである場合、プロセスはステップ４１７に進む。ステップ４１７において、ステップ４０９にてブロックがエラーで受信された場合、プロセスはステップ４１９に進み、それ以外の場合には、プロセスは終了する。ステップ４１９において、通信ユニットは、エラーで受信されたブロックの再送信（ＲＥ−ＴＸ）を要求する。ステップ４２１においてこのブロックの再送信（ＲＥ−ＴＸ）が一つまたはそれ以上のエラーで受信される場合、プロセスはステップ４１９に進む。ステップ４２１においてこのようなすべてのブロックの再送信（ＲＥ−ＴＸ）がエラーなしに受信されると、プロセスはステップ４２３に進み、ここでメッセージ全体１００は、ステップ４０３において生成されたキーストリームを利用して解読される。キーストリームは既に生成されているので、解読するステップ４２３は、合成する段階、すなわち、受信した暗号文を生成／格納されたキーストリームと排他的論理和をとり、送信装置によって当初暗号化された平文（暗合化されていない文）を生成する段階に過ぎない。従って、キーストリームは、キーストリームを再生成または再送信する必要なしに、あるいはキーストリームを生成しかつメッセージ全体を解読するためにメッセージ全体がエラーなしに受信されるの待たずに、メッセージの一部がリトライ後に受信されるとき、データ・メッセージの一部またはすべてを解読するために保存され、用いられる。同様に、選択的なリトライの解読は、メッセージ全体を再解読あるいはメッセージのすべての前回ブロックを解読する必要なしに可能となる。別の代替方法は、メッセージ・インジケータおよび複数の暗号化ブロックからなるメッセージを受信する段階によって構成される。暗号状態は、複数の暗号化ブロックのＫ番目のブロックごとに格納され、ここでＫは正の整数である。複数の暗号化ブロックの少なくとも一つのブロックがエラーで受信されると、この少なくとも一つのブロックの再送信を要求する第２メッセージを送信する。この少なくとも一つのブロックの再送信をエラーなしに受信すると、格納済み暗号状態からキーストリームを生成し、このキーストリームを利用してこの少なくとも一つのブロックを解読する。暗号状態を周期的に保存することによって、メッセージを後で解読する代替方法を示すフローチャートを第５図のフローチャートに示す。このフローチャートに示す方法は、格納スペースと解読時間との間のトレードオフとなる。この方法は、Ｋブロック毎に暗号状態を保存し、２つのバッファ、すなわち、受信済みブロックを保持するためのＮブロックの１つのバッファと、ＮをＫ暗号化状態で除した第２のバッファとを必要とする。この方法は、暗号状態を周期的に保存する。格納済み暗号状態は、再送信されたブロックを収容するメッセージの一部についてＫＧを再初期化するために用いられる。パラメータＫは、解読時間と格納すペーストの間のトレードオフとなる。Ｋが大きくなるにつれて、解読時間は長くなるが、格納スペースは少なくてすむ。第５図の方法を利用するとき、エラーなしに受信されたブロックは即時解読され、エラーで受信されたブロックは、エラーなしに受信されたデータの再送信の受信時に解読される。あるいは、すべてのブロックを保存しておき、すべてのリトライ・ブロックが適切に受信された後、例えば、メッセージが短い場合に、一度に解読してもよい。ステップ５０１において、ＭＩ１０１および複数の暗号化ブロック１０３〜１１１を有するメッセージ１００が受信される。ステップ５０３において、ＭＩ１０１はＫＧの暗号状態として設定される。一般に、暗号状態は、キーストリームとして知られる疑似ランダム・シーケンスの生成時におけるＫＧの内部ポイントのことである。暗号状態は、解読側ＫＧが暗号側ＫＧが暗号化したものを適切に解読できるように、２つの異なるＫＧをデータのストリーム中の同じ場所に置くために必要なすべての情報を含む。ＯＦＢ動作モードの暗号状態はＫＧ状態であり、これは以降のブロックを解読するうえでＫＧを適切に初期化するために必要な、前回解読されたブロックのキーストリームにおける最後のビット数からなる。好適な実施例では、６４ビットが用いられる。ＣＡ動作モードの暗号状態はＬＦＳＲ状態であり、これは以降のブロックを解読するうえでＬＦＳＲを適切に初期化するために必要なＬＦＳＲにおけるデータのことである。好適な実施例では、ＬＦＳＲにおける６４ビットが暗号状態として用いられる。ステップ５０５において、ブロック・カウンタＮは初期化され、すなわち、Ｎは１に設定される。ステップ５０７において、ブロックＮは取り出される。ステップ５０９において、ブロックＮは、ブロックＮのデータをＫＧに入力することによって解読される、すなわち通常の解読である。ステップ５１１において、ブロックＮがエラーで受信されたかどうか判定される。ブロックＮがエラーで受信された場合、プロセスはステップ５１３に進み、ここでブロックＮはエラーで受信されたとマークされ、解読済みブロックＮはステップ５１５において放棄される。ステップ５１１において、ブロックＮがエラーなしに受信された場合、プロセスはステップ５１７に進み、ここでブロックＮの解読の結果が格納される。ステップ５１９においてＮモジュロＫが０の場合、プロセスはステップ５２１に進み、ここでブロックＮを解読した後の暗号状態が保存される。ブロックＮを解読した後のＫＧ状態は、ブロックＮ＋１を解読するための初期状態である。ＯＦＢ動作モードでは、ＫＧ状態が格納される。ＣＡ動作モードでは、ＬＦＳＲ状態が格納される。ステップ５１９において、ＮモジュロＫがゼロに等しくない場合、プロセスはステップ５２３に進む。ステップ５２３において、ブロック・カウンタＮは１だけインクリメントされ、すなわちＮ＝Ｎ＋１となる。ステップ５２５において、ブロックＮがメッセージ１００の最後のブロックでない場合、プロセスはステップ５０７に進む。ステップ５２５において、ブロックＮがメッセージ１００の最後のブロックである場合、プロセスはステップ５２７に進む。ステップ５２７において、ステップ５１１にてブロックがエラーで受信された場合、プロセスはステップ５２９に進み、それ以外の場合には、プロセスは終了する。ステップ５２９において、通信ユニットは、エラーで受信されたブロックの再送信（ＲＥ−ＴＸ）を要求する。ステップ５３１において、このようなブロックの再送信（ＲＥ−ＴＸ）が一つまたはそれ以上のエラーで受信されると、プロセスはステップ５２９に進む。ステップ５３１において、すべてのリトライ・ブロックの再送信（ＲＥ−ＴＸ）がエラーなしに受信されると、プロセスはステップ５３３に進み、ここでリトライ・ブロックが取り出される。ステップ５３５において、暗号状態は、リトライ・ブロックのブロック番号以前の最も最近格納された値から取り出される。すなわち、Ｋ番目のブロック毎にＫＧ状態が格納される場合、ブロックＮを解読するために取り出されるべきＫＧ状態の番号は、次式によって与えられるように、このブロック番号の後に格納されたＫＧ状態である：Ｋ＊｛整数部（Ｎ−１）／Ｋ｝例えば、リトライ・ブロックがブロック３０であり、Ｋ＝４であり、ここでブロック２８およびブロック３０が保存されている場合、ブロック３０を解読するために取り出すべき暗号状態は、ブロック４＊｛整数部（３０−１）／４｝＝４＊７＝２８、すなわち、ブロック２８の暗号状態が取り出される。ステップ５３７において、ステップ５３５において取り出された暗号状態はＫＧに入力され、そしてＫブロックまで、取り出された状態のブロックからリトライ・ブロックまで、が通常に、すなわち、受信された暗号文をＫＧに入力することによって、解読される。Ｋ番目毎のブロックを保存することにより、解読すべき最悪の場合のブロック数はＫとなる。解読すべき実際のブロック数は、次式によって与えられる：ＮｍｏｄＫが０の場合、Ｋ；それ以外の場合、ＮｍｏｄＫステップ５３９において、解読すべき一つまたはそれ以上のリトライ・ブロックがある場合、プロセスはステップ５３３に進み、それ以外の場合には、プロセスはステップ５４１に進む。ステップ５４１において、メッセージ１００からのすべてのブロックが適切に受信された場合、プロセスは終了し、それ以外の場合には、プロセスはステップ５２９に進む。Ｋ＝３の場合のシステムに関する情報を示す表を以下に示し、ここで取り出し状態とはブロックＮを解読した後に格納された暗号状態のことである。さらに別の代替方法は、特にＣＡモードで動作する暗号装置を利用する場合に、メッセージ・インジケータおよび複数の暗号化ブロックからなるメッセージを受信する段階によって構成される。メッセージ・インジケータは格納される。複数の暗号化ブロックの少なくとも一つのブロックがエラーで受信されると、第２メッセージが送信され、この第２メッセージはこの少なくとも一つのブロックの再送信を要求する。この少なくとも一つのブロックの再送信をエラーなしに受信すると、暗号状態は格納済みメッセージ・インジケータから計算され、キーストリームはこの暗号状態から生成され、少なくとも一つのブロックはこのキーストリームを利用して解読される。暗号状態を計算することによって、メッセージを後で解読する代替方法を示すフローチャートを第６図のフローチャートに示す。第６図の方法を利用するとき、エラーなしで受信されたブロックは即時解読され、エラーで受信されたブロックは、エラーなしに受信されたデータの再送信の受信時に解読される。あるいは、すべてのブロックを保存しておき、すべてのリトライ・ブロックが適切に受信された後、例えば、メッセージが短い場合に、一度に解読してもよい。ステップ６０１において、ＭＩ１０１および複数の暗号化ブロック１０３〜１１１を有するメッセージ１００が受信される。ステップ６０３において、ＭＩ１０１は、第５図のステップ５０３で説明したように、ＫＧの暗号状態に設定される。ステップ６０５において、ブロック・カウンタＮは初期化され、すなわち、Ｎは１に設定される。ステップ６０７において、ブロックＮは取り出される。ステップ６０９において、ブロックＮは、ブロックＮのデータをＫＧに入力することにより解読される、すなわち通常の解読である。ステップ６１１において、ブロックがエラーで受信されたかどうか判定される。ブロックＮがエラーで受信された場合、プロセスはステップ６１３に進み、ここでブロックＮはエラーで受信されたとマークされ、解読済みブロックＮはステップ６１５において放棄される。あるいは、ステップ６０９の解読機能はステップ６１７に組み込むことができ、その場合、ステップ６０９は省かれる（ステップ６０７の次に、プロセスはステップ６１１に進む）。ステップ６１１において、ブロックＮがエラーなしに受信された場合、プロセスはステップ６１７に進み、ここでブロックＮの解読の結果が格納される。ステップ６１９において、ブロック・カウンタＮは１だけインクリメントされ、すなわち、Ｎ＝Ｎ＋１となる。ステップ６２１において、ブロックＮがメッセージ１００の最後のブロックでない場合、プロセスはステップ６０７に進む。ステップ６２１において、ブロックＮがメッセージ１００の最後のブロックである場合、プロセスはステップ６２３に進む。ステップ６２３において、ブロックがステップ６１１にてエラーで受信された場合、プロセスはステップ６２５に進み、それ以外の場合には、プロセスは終了する。ステップ６２５において、通信ユニットはエラーで受信されたブロックの再送信（ＲＥ−ＴＸ）を要求する。ステップ６２７においてこのようなブロックの再送信（ＲＥ−ＴＸ）が一つまたはそれ以上のエラーで受信される場合、プロセスはステップ６２５に進む。ステップ６２７においてリトライ・ブロックの再送信（ＲＥ−ＴＸ）がエラーなしに受信される場合、プロセスはステップ６２９に進み、ここでリトライ・ブロックが取り出される。ステップ６３１において、暗号状態が計算される。ＣＡ動作モードでは、暗号状態はＬＦＳＲ状態であり、これはＭＩと、ＬＦＳＲの生成多項式と、ブロック番号とを利用して計算される。ブロックＮを解読するために用いられるＬＦＳＲ状態は、ブロックＮ−１を解読するときに格納された初期状態である。ブロックＮの前のビット数は、ＬＦＳＲ状態を判定するために必要となる。各ブロックが同じビット数Ｂを有する場合、Ｎ＊Ｂ（ＮとＢの積）は、ブロックＮの前に受信されたビット総数であり、これはまた、ＭＩとブロックＮとの間で実行されるＬＦＳＲの生成多項式の反復回数を反映する。ＬＦＳＲ状態は、次式の剰余である：ｘ^N*B ÷ 生成多項式例えば、６４ビットＬＦＳＲの生成多項式は：ｘ⁶²＋ｘ⁴⁶＋ｘ³⁸＋ｘ²⁷＋ｘ¹⁵＋ｘ⁰ そのため上式は次のようになる：ｘ^N*B ÷ （ｘ⁶²＋ｘ⁴⁶＋ｘ³⁸＋ｘ²⁷＋ｘ¹⁵＋ｘ⁰）多項式除算の剰余のサンプルは：ｘ⁶³＋ｘ⁵⁹＋ｘ⁵¹＋ｘ⁴⁶＋ｘ⁴⁰＋ｘ³⁵ｘ＋ｘ³¹ ＋ｘ²⁶＋ｘ¹⁹＋ｘ¹⁴＋ｘ⁸＋ｘ⁰ となり、これはブロックＮのＬＦＳＲ状態である。ステップ６３３において、暗号状態はＫＧに格納される。ステップ６３５において、リトライ・ブロックは通常に解読される、すなわち、受信された暗号文をＫＧに入力することによって解読される。ステップ６３７において、解読すべき一つまたはそれ以上のリトライ・ブロックがある場合、プロセスはステップ６２９に進み、それ以外の場合には、プロセスはステップ６３９に進む。ステップ６３９において、メッセージ１００からのすべてのブロックが適切に受信される場合、プロセスは終了し、それ以外の場合には、プロセスはステップ６２５に進む。従来の暗号システムでは、解読は暗号化データ・ストリームをＫＧに印加することによって実行され、ＫＧは暗号動作モードについて適切なキーストリームを生成し、このキーストリームと暗号化メッセージとを合成（一般に、デジタル情報では排他的論理和をとる）して、平文（暗号化されていない文）を生成することによって、暗号化メッセージを即時解読する。一般的なＫＧは、ビット毎（あるいはシンボル毎）にメッセージを解読する、すなわち、ＫＧに暗号化データの１ビット（シンボル）を入力すると、１ビット（シンボル）のキーストリームが生成され、このキーストリームは入力ビット（シンボル）と合成されて、ＫＧによって出力される１ビット（シンボル）の解読済みデータとなる。この合成段階は、例えば１ＭＨｚで動作するマイクロプロセッサにおいて簡単かつ迅速に実行される。しかし、キーストリームの生成は、ＫＧが動作できる周波数、一般に６〜５０ＫＨｚに制限される。従って、キーストリームを生成し、かつ暗号化メッセージを解読する実際の時間は、ＫＧが動作できる最大周波数によって実質的に制限される。上記の方法およびその代替方法は、データの再送信が必要な場合に、メッセージ全体を受信・解読する時間を最小限に抑えるために、適切な情報を格納および／または生成することにより、従来の方法に比べて時間を節約する。ＫＧのクロック・スピードを増加することは、スループットを改善するための可能な解決方法である。ただし、このような解決方法では、ＫＧが必要とする電力量はクロック・スピードに比例するので、電力消費が問題となるようなシステムにおいて実施することは実際に不可能となる。

───────────────────────────────────────────────────── フロントページの続き (81)指定国ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ，ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ，ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＧＨ，ＫＥ，ＬＳ，ＭＷ，ＳＤ，ＳＺ，ＵＧ)，ＡＬ，ＡＭ，ＡＴ，ＡＵ，ＡＺ，ＢＡ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ，ＣＵ，ＣＺ，ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，ＧＥ，ＧＨ，ＨＵ，ＩＬ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ，ＬＣ，ＬＫ，ＬＲ，ＬＳ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ，ＴＪ，ＴＭ，ＴＲ，ＴＴ，ＵＡ，ＵＧ，ＵＺ，ＶＮ，ＹＵ (72)発明者ブライト、マイケル・ダブリューアメリカ合衆国イリノイ州アーリントン・ハイツ、ノース・ミッチェル・アベニュー 1339

Claims

【特許請求の範囲】１．メッセージ・インジケータおよび複数の暗号化ブロックからなるメッセージを受信する段階であって、前記複数の暗号化ブロックはＬ個のブロックからなり、Ｌは２より大きいか等しい整数である、受信段階；前記複数の暗号化ブロックの少なくともＮ番目のブロックがエラーで受信された場合に、少なくとも前記Ｎ番目のブロックの再送信を要求する第２メッセージを送信する段階であって、Ｎは１とＬとの間の値を有する整数である、送信段階；少なくとも前記Ｎ番目のブロックの再送信をエラーなしに受信すると、前記メッセージからキーストリームを生成し、かつ前記キーストリームを利用して前記Ｎ番目のブロックを解読する段階であって、前記キーストリームは、少なくとも前記Ｎ番目のブロックを解読するが、前記複数の暗号化ブロックのすべてを解読しない、解読段階；によって構成されることを特徴とする方法。２．前記メッセージ・インジケータは初期化ベクトルを収容し、またＮブロック・メッセージについて、Ｂ反復で乗じた、出力フィードバック動作モードＮで動作する暗号アルゴリズムを実行することによって、キーストリームを生成する段階であって、ＮおよびＢは正の整数である段階をさらに含んで構成されることを特徴とする請求項１記載の方法。３．前記メッセージ・インジケータは線形フィードバック・シフト・レジスタ・ベクトルを収容し、またＮブロック・メッセージについて、Ｂ反復で乗じた、カウンタ・アドレッシング動作モードＮで動作する暗号アルゴリズムを実行することによって、キーストリームを生成する段階であって、ＮおよびＢは正の整数である段階をさらに含んで構成されることを特徴とする請求項１記載の方法。４．メッセージ・インジケータおよび複数の暗号化ブロックからなるメッセージを受信する段階；前記複数の暗号化ブロックを解読する際に用いるために、前記メッセージ・インジケータからキーストリームを生成する段階；前記複数の暗号化ブロックの少なくとも一つのブロックがエラーで受信されたときに、前記少なくとも一つのブロックの再送信を要求する第２メッセージを送信する段階；前記少なくとも一つのブロックの再送信をエラーなしに受信すると、前記キーストリームを利用して前記少なくとも一つのブロックを解読する段階であって、前記複数の暗号化ブロックは順次暗号化され、前記基複数の暗号化ブロックは順次以外の順序で解読される、解読段階；によって構成されることを特徴とする方法。５．前記メッセージ・インジケータは初期化ベクトルを収容し、またＮブロック・メッセージについて、Ｂ反復で乗じた、出力フィードバック動作モードＮで動作する暗号アルゴリズムを実行することによって、キーストリームを生成する段階であって、ＮおよびＢは正の整数である段階をさらに含んで構成されることを特徴とする請求項４記載の方法。６．前記メッセージ・インジケータは線形フィードバック・シフト・レジスタ・ベクトルを収容し、またＮブロック・メッセージについて、Ｂ反復で乗じた、カウンタ・アドレッシング動作モードＮで動作する暗号アルゴリズムを実行することによって、キーストリームを生成する段階であって、ＮおよびＢは正の整数である段階をさらに含んで構成されることを特徴とする請求項４記載の方法。７．メッセージ・インジケータおよび複数の暗号化ブロックからなるメッセージを受信する段階；前記複数の暗号化ブロックのＫ番目のブロック毎に暗号状態を格納する段階であって、Ｋは正の整数である、格納段階；前記複数の暗号化ブロックの少なくとも一つのブロックがエラーで受信されたときに、前記少なくとも一つのブロックの再送信を要求する第２メッセージを送信する段階；前記少なくとも一つのブロックの再送信をエラーなしに受信すると：ａ）前記複数の暗号化ブロックのすべてについてキーストリームを生成せずに、前記格納済み暗号状態からキーストリームを生成し；ｂ）前記キーストリームを利用して前記少なくとも一つのブロックを解読する段階；によって構成されることを特徴とする方法。８．前記メッセージ・インジケータは初期化ベクトルを収容し、またＮブロック・メッセージについて、Ｂ反復で乗じた、出力フィードバック動作モードＮで動作する暗号アルゴリズムを実行することによって、キーストリームを生成する段階であって、ＮおよびＢは正の整数である段階をさらに含んで構成されることを特徴とする請求項７記載の方法。９．メッセージ・インジケータおよび複数の暗号化ブロックからなるメッセージを受信する段階；前記メッセージ・インジケータを格納する段階；前記複数の暗号化ブロックの少なくとも一つのブロックがエラーで受信されたときに、前記少なくとも一つのブロックの再送信を要求する第２メッセージを送信する段階；前記少なくとも一つのブロックの再送信をエラーなしに受信すると：ａ）前記格納済みメッセージ・インジケータから暗号状態を計算し；ｂ）前記暗号状態からキーストリームを生成し；ｃ）前記キーストリームを利用して前記少なくとも一つのブロックを解読する段階；によって構成され、前記複数の暗号化ブロックは順次暗号化され、前記複数の暗号化ブロックは順次以外の順序で解読されることを特徴とする方法。１０．前記複数の暗号化ブロックの第１ブロックがエラーなしに受信されるときに、前記キーストリームを利用して前記第１ブロックを解読する段階をさらに含んで構成されることを特徴とする請求項９記載の方法。