JP2688659B2 - デジタルセルラ通信用暗号化システム - Google Patents

Description

【発明の詳細な説明】 関連出願に対する参照 本出願は、「セルラ通信システム用連続暗号同期」と
題された係属中の米国特許出願連番第556,102号、及び
「ハンドオフ時における暗号システムの再同期」と題さ
れた係属中の米国特許出願第556,103号、にも関連する
主題を含んでおり、これらは両方とも1990年７月20日に
出願され、また、1990年７月23日に出願された継続中の
米国特許出願第556,890号「デジタルセルラ通信のため
の照合システム」にも関連する主題を含んでいるこのよ
うな出願及びその中の開示を、以下参照のためにここに
組み入れることにする。

発明の背景 発明の分野 本発明はデジタルセルラ通信システムに関し、更に特
定すれば、このようなシステムにおいてデータ通信の暗
号化の方法及び装置に関するものである。

従来技術の歴史 セルラ無線通信は、恐らく、全世界の遠隔通信工業に
おいて最も急成長している分野である。セルラ無線通信
システムは、現在稼働中の遠隔通信システムの小さな断
片のみを含むものであるが、この断片は着実に増加し、
そう遠くない将来において遠隔通信市場全体の大部分を
代表するようになるだろうと、広く信じられている。こ
の確信は、ネットワーク内の加入者と接続するために、
主に配線技術に頼っている従来の電話通信ネットワーク
に固有な限界に、基づくものである。標準的家庭用また
は事務所用電話は、例えば、壁の引き出し口即ち電話ジ
ャックにある最大長の電話線を介して接続されている。
同様に、電線が電話の引き出し口を、電話会社の区間内
スイッチング事務所に接続している。したがって、電話
ユーザの行動範囲は、電話線の長さだけでなく、動作可
能な電話引き出し口、即ち区間内スイッチング事務所と
接続された引き出し口の使用可能によって、制限される
ことになる。実際、セルラ無線システムの発生は、これ
らの制限を克服し、電話ユーザに彼の効果的に他の人と
通信する可能性を犠牲にすることなく、動き回ったり、
または彼の家庭または事務所から移動する自由を与える
という希望に依るところが大きいのかもしれない。典型
的なセルラ通信システムでは、ユーザ、またはユーザの
車両が、比較的小さな無線装置を携帯し、これが基地局
と通信し、そしてシステム内の他の移動局及び公衆切り
換え式電話ネットワーク（PSTN）内の陸線側とユーザを
接続する。

既存のセルラ無線通信システムの重大な不利は、アナ
ログ無線伝送が傍受され得る容易性である。特に、移動
局と基地局との間の通信のいくらか或いは全ては、認証
なしで、単に通信の単一または複数の周波数に適切な電
子式受信機を同調させることによって、モニタすること
ができるのである。したがって、このような受信機への
アクセス及び盗聴に興味を有する者はだれでも、意志が
あれば、そして全く咎めなく、事実上通信のプライバシ
ーを侵害することができてしまう。電子的盗聴を違法と
する努力がなされて来たが、このような行動の秘匿性
は、盗聴の全てではなくとも殆どが発見されずに済んで
しまい、したがって罰せられることも、引止められるこ
ともないことを意味する。ある競合者即ち敵が、ある人
の表面上は個人的な電話での会話に「同調させる」こと
を決心する可能性は、これまでセルラ無線通信システム
の急増を妨げ、チェックされないままであり、このよう
なシステムの実業界及び政府での用途の育成力を脅かし
続けるであろう。

最近、未来のセルラ無線遠隔通信システムが、アナロ
グ技術よりむしろデジタルを用いて実施されるであろう
ことが明確になってきた。デジタルへの切り換えは、主
として、システムの速度及び容量に関連する考慮によっ
て、命じられたものである。単一のアナログ、または音
声の無線周波数（RF）チャンネルは、４ないし６の、デ
ジタルまたはデータの、RFチャンネルを収容することが
できる。したがって、音声チャンネルを介して伝送する
前に対話をデジタル化することによって、チャンネル容
量、そして結果的にシステム全体の容量は、音声チャン
ネルの帯域を増加させることなく、劇的に増加され得る
のである。当然の結果として、システムは、大幅に低い
コストで、かなりのより大きな数の移動局を扱うことが
できる。

アナログからデジタルセルラ無線システムへの切り換
えは、基地局と移動局との間の通信の機密性が欠除する
可能性をいくらか改善するが、電子的盗聴の危険性は、
根絶からはかけ離れている。デジタル信号をテコード
し、元の対話を発生できるデジタル受信機を構成するこ
とができるからである。アナログ伝送の場合より、ハー
ドウエアはより複雑となり、手間はより高価となるだろ
うが、デジタルセルラ無線システムにおいて非常に個人
的なまたは高度な慎重さを要する会話が第三者によって
傍受され、もしかすると用いられてシステムのユーザに
損害を与え得る可能性が存続する。更に、電話の会話を
第三者が盗聴する実際の可能性が、セルラ遠隔通信を特
定の政府の通信手段としては、排除してしまうことにな
る。特定のビジネスユーザも同様に、同様に機密性が欠
除する可能性にさえも敏感であるかもしれない。したが
って、セルラシステムを従来の電線ネットワークに実行
可能な代替物とするためには、通信の機密性が少なくと
もいくつかの回路上て得られなければならない。

種々の解決法が、極秘データの無線伝送によって生じ
る機密性の問題を軽減するために、提案されてきた。あ
る公知の解決法は、いくつかの既存の通信システムによ
って実施され、暗号アルゴリズム（cryptoalgorithm）
を用いて、伝送に先立ってデジタルデータを理解不能な
形状に暗号化（スクランブル）するものである。例え
ば、1990年６月付のリック グレハン（Rick Grehan）
による雑誌バイト内の「クローク及びデータ」という題
の論文の311−324ページは、暗号法システムの一般的な
議論に関するものである。現在入手可能なシステムの殆
どにおいて、スピーチは暗号化装置によってデジタル化
されかつ処理されて、それが許可された受信機において
暗号解読されるまで、事実上ランダム或いは疑似ランダ
ムとなって現われる通信信号を生成する。暗号化装置に
よって用いられる特定のアルゴリズムは、独占的なアル
ゴリズムであることも、パブリックドメインにおいて見
出されるアルゴリズムであることもある。このような技
術に対するその他の背景が、1979年８月付のサイエンテ
ィフィックアメリカ（Scientific America）の146−167
ページの、マーティン E.ヘルマン（Martin E.Hellman
n）の「公開キーを用いる暗号法の数学」と題された論
文にも、見出すことができる。

1977年、米国国立標準事務局（U.S.National Bureau
of Standards）は、データ暗号化標準（DES）として規
定された暗号アルゴリズムを発行した。国立技術情報サ
ービスの連邦情報処理標準刊行物（FIPS PUB 46）（197
7年）を参照されたい。DESの暗号化方法は、公知の数学
的アルゴリズムを利用しており、乱数のストリームと64
ビットの二進数から成るデータ暗号化キーとを生成する
ものである。典型的にアスキー（ASCII）フォーマット
のデジタルデータが、外見上ランダムなビット列に変換
される。64ビット二進数のいずれかである暗号化キーが
暗号化されたデータの受信者にも知られている場合にの
み、暗号化されたデータは、標準DES暗号解読手順にし
たがって、暗号解読される。DES暗号化及び暗号解読手
順は公知であるので、キーの機密性は、DESの効果的な
使用に対して重要である。

DES暗号化／暗号解除を実施した商用装置は、一般的
に、暗号化されるデータを第１の入力として、そして64
ビットのキーを第２の入力として受け入れる、集積回路
の形状となっている。殆どのこのような装置は、暗号化
されたデータが第３の入力としてDES装置に供給され、
暗号化されているデータが同一文字の反復する連続を含
む時に、反復する暗号化されたデータ列の送信を防止す
るようにした、暗号フィードバックモード（CFB）で動
作する。データのCFB暗号化の主な利点は、暗号化され
たデータの自己同期である。しかしながら、RFリンクを
通じて動作するCFB装置の主な不利は、受信機の感度に
関連するエラーの倍増に起因する、移動局の動作範囲の
減少である。すなわち、暗号化されたデータブロックの
送信における１つのエラーは、平均して、暗号解読され
たデータにおけるビットの半分にエラーを生じ、巨大に
拡大された送信エラー率を生じることとなる。したがっ
て、移動局は、十分に高い信号対ノイズ比を保持して送
信されたデータビットの誤った受信の回避を試みるため
には、基地局のある限られた範囲内に留っている必要が
ある。エラーの倍増がCFBモードで発生するのは、エラ
ーが伝搬し終り、そして結果的に受信機が再同期するま
で、誤って受信されたビットが連続的に暗号解読装置に
フィードバックされるからである。

CFB動作モードにおいて遭遇するエラー倍増の問題を
受けない、データ暗号化の別の既知の技術は、カウンタ
アドレッシング（CA）である。CA動作モードでは、キー
ストリーム発生器を用いて、複数のキーデータビットを
含む暗号化キーを処理することによって、疑似ランダム
キーストリームビットを生成する。次に、キーストリー
ムが暗号化装置によって用いられ、データ信号を暗号化
する。典型的に、キーストリームは、非他的オア（XO
R）論理ゲートによって、ビット毎にデータ信号と加算
され（モジュロ−２）、スクランブルされ二進データ信
号を生成する。このスクランブルされた信号は、同一二
進暗号化キーを用いて初期化した同一のキーストリーム
発生器によって、同時に発生された同一のキーストリー
ムを、前記スクランブルされた信号に加算する（モジュ
ロ−２）ことによって、デスクランブルされる。このよ
うにして、暗号化装置を、疑似ランダムカウンタによっ
て、「アドレス」することができる。したがって、CAモ
ードでは、定期的なキー発生器のデータ転送を必要とせ
ずにデスクランブラのキー発生器の適切な動作を行なわ
せるためには、スクランブラとデスクランブラとの間の
連続ビット同期が、必要とされる。残念ながら、セルラ
無線システムにおけるRFチャンネルを通じたビット同期
は、受信機器近傍の障害物からの反射によって発生され
るマルチ−パス干渉パターンによって起こされる、レイ
レイフェーディング現象によって、保持するのが非常に
困難である。暗号化回路と位相が外れている暗号解読回
路を介した送信における１つのエラービット、及び受信
機で生成される出力は、無意味である。CA技術は、一般
的に、ビット送信エラーに対してより強力でなければな
らない無線リンクの暗号化には、相応しいものではな
い。

連続ビット同期に伴う困難が、「タイムオブデイ」ま
たは「フレーム番号」で駆動するキーストリーム発生器
の使用に、導いてきた。このようなキーストリーム発生
器は、タイムオブデイカウンタ、即ち、時間、分及び
秒、或は単純な数値カウンタに同期させることができ、
そして暗号化及び暗号解読回路は、一方が他方との同期
から外れても、現在のカウントを送り続けることができ
る。

タイム−オブ−デイまたはフレーム番号で駆動される
キーストリーム発生器を利用したシステムにおいて、通
信の機密性を増加させるために、疑似ランダムキースト
リーム内の各ビットの値を、暗号化キー内の全てのキー
ビットの値の関数とすることが好ましい。このようにす
ると、暗号化された信号をデスクランブルしようとする
人は、約50から100ビット或いはそれ以上かもしれない
暗号化キーのビットの全てを「分解」即ち「解読」しな
くてはならない。このタイプのキーストリームは、通常
タイム−オブ−デイカウンタのカウントを組み込んだ、
選択されたアルゴリズムに応じて、数学的に暗号化キー
ワードを拡張することによって、生成される。しかしな
がら、暗号化キーの各ビットがキーストリーム内の各ビ
ットに影響を及ぼし、かつキーストリームが１つずつデ
ータストリームビットに加えらえるのであれば、１秒当
たり必要なキーワード拡張計算の数は、膨大であり、シ
ステムのリアルタイム計算能力を容易に超過し得るもの
である。必要とする計算の度合が、スーパーコンピュー
タの使用を示唆しているが、この目的のためにはスーパ
ーコンピュータのコストは法外である。したがって、従
来マイクロプロセッサを用い、かつ従来のマイクロプロ
セッサの速度でキーストリームの拡張を達成する方法及
び装置が必要とされている。

発明の概要 一観点において、本発明は、デジタルデータを暗号化
するのに用いるための疑似ランダムビット列を発生する
方法を備えるものである。この方法は、各々が前記選択
されたキービットの少なくともいくつかの関数である、
複数の多ビット値を発生することと、前記複数の多ビッ
ト値の各々をメモリ内の別個の位置に記憶することを、
含んでいる。各動作サイクルに応答して、前記レジスタ
内に含まれている現在値を増分することによって、数値
列がレジスタ内に発生される。第１の事前に選択された
アルゴリズムにしたがって、各々の値が前記メモリ内に
記憶された多ビット値の少なくとも１つ及び前記レジス
タに含まれる値の関数である、多ビット数値列が、巡回
的に計算される。各計算の結果として得られた値によっ
て、前記レジスタの内容が巡回的にリセットされ、そし
て各計算の結果として得られた値の関数である多ビット
キーワードが巡回的に抽出される。前記多ビットキーワ
ードが前記疑似ランダムビット列に、連続的に組み込ま
れる。一実施例では、発生された複数の多ビット値は、
各々選択されたキービット全ての関数である。

別の観点では、本発明は、２つのステージで疑似ラン
ダムキーストリームを発生するための秘密キーを用いた
キーストリーム発生器を備えた、暗号化サブシステムを
有する、セルラ通信システムを含んでいる。第１に、あ
るアルゴリズムにしたがって秘密キーが拡張されて、参
照テーブルを生成し、これがメモリ内に記憶される。第
２に、前記回路は、レジスタのカウントをキーと共に、
参照テーブル内に記憶されたデータと組み合わせて使用
し、疑似ランダムキーストリームを発生し、送信前にこ
れをデータと混合する。本発明のシステムは、タイムオ
ブデイ駆動のカウンタを、参照テーブル内に記憶したデ
ータと共に用いており、それら両方を使用してキースト
リームを発生する。送信機及び受信機両方においてこの
ようなカウンタは、同期外れが起こった場合、定期的に
再同期させることができる。

更に他の観点では、本発明は、基地局及び移動ユニッ
トによって送信及び受信されるデジタルデータストリー
ムが暗号的にエンコードされて遠隔通信の機密性を与え
る、デジタルセルラ通信システムを、含んでいる。本シ
ステムは、二進ビットの疑似ランダムキーストリーム
を、システムにおける各送信機及び受信機のデジタル信
号を搬送する情報に付加して、システム内で送信及び受
信されるデジタルデータストリームを作成する手段を組
み込んでいる。複数の選択された秘密キーの関数とし
て、前記二進ビットの疑似ランダムキーストリームを発
生する手段は、各々、選択されたキービットの少なくと
も幾つかの関数である、複数の多ビット値を発生する手
段を、前記複数の多ビット値の各々をメモリ内の別個の
位置に記憶する手段と共に備えている。レジスタ内に数
値列を発生する手段が、各動作サイクルに応答して、レ
ジスタ内に含まれている現在値を増分する。本システム
は、更に、各々、メモリ内に記憶された多ビット値の少
なくとも１つ、及びレジスタ内に含まれている値の関数
である、多ビット値の列を、第１の事前に選択されたア
ルゴリズムにしたがって、巡回的に計算する手段と、各
計算の結果として得られた値で、レジスタの内容を巡回
的にリセットする手段とを備えている。各計算の結果と
して得られた値の関数である多ビットキーワードが、巡
回的に抽出され、そして、送信及び受信されるデジタル
データストリームを暗号的にエンコード及びデコードす
るために用いられる二進ビットの疑似ランダムキースト
リームに、組み合わせられる。

図面の簡単な説明 次の図面を参照することによって、本発明はよりよく
理解され、その多数の目的及び利点は当業者には明白と
なろう。第１図は、移動切り換えセンタ、複数の基地局
及び複数の移動局を含む、セルラ無線通信システムの図
式表現である。第２図は、本発明のシステムの一実施例
にしたがって用いられる移動局の装備の概略ブロック図
である。

第３図は、本発明のシステムの一実施例にしたがって
用いられる基地局の装備の概略ブロック図である。

第４図は、従来技術のキーストリーム発生器の概略ブ
ロック図である。

第５図は、本発明にしたがって構成された暗号化シス
テムのキーストリーム発生回路の概略ブロック図であ
る。及び 第６図は、第５図に示されたキーストリーム発生器の
第２拡張ステージの概略ブロック図である。

好適実施例の詳細な説明 まず第１図を参照すると、そこには本発明が全体的に
関係するタイプの、従来のセルラ無線通信システムが図
示されている。第１図において、任意の地理的領域が、
複数の連続無線適用範囲、即ちセルC1−C10に分割され
たものと、見ることができる。第１図のシステムは10個
のセルのみを含むものとして示されているが、実際には
セル数はそれより遥かに多いことは、明確に理解されよ
う。

セルC1−C10の各々に関連し、その中に配置されてい
るのは、複数の基地局B1−B10の対応する１つとして示
された基地局である。基地局B1−B10の各々は、当該技
術においてよく知られているように、送信機、受信機及
び制御器を備えている。第１図では、基地局B1−B10
は、夫々セルC1−C10の中央に配置され、全方向性アン
テナを装備されている。しかしながら、セルラ無線シス
テムの別の構成では、基地局B1−B10は、周辺近くに、
またそうでなければ、セルC1−C10の中央から離して配
置されてもよく、全指向的または単一指向的にセルC1−
C10を無線信号で照明することができる。したがって、
第１図のセルラ無線システムの表現は、例示のみの目的
のためのものであり、セルラ無線システムの可能な実施
態様における制限として意図されたのではない。

第１図への参照を続けると、複数の移動局M1−M10
が、セルC1−C10の中に見出されよう。再び、10台の移
動局のみが第１図に示されるが、実用では移動局の実際
の数はそれよりかなり大きく、基地局の数を常に超過す
ることが、理解されよう。更に、セルC1−C10のいくつ
かには、移動局M1−M10が見出されないが、移動局M1−M
10がセルC1−C10のいずれか特定の１つに存在するかし
ないかは、１つのセル内のある位置から別の位置、或い
は１つのセルから隣接または近くのセルに徘徊する移動
局M1−M10の各々の個個の望みにしたがうものと、理解
されよう。移動局M1−M10の各々は、基地局B1−B10の１
つ以上、及び移動切り換えセンタMSCを介して、電話通
話を開始または受信することができる。移動切り換えセ
ンタMSCは、通信リンク、例えばケーブルによって、例
示的な基地局B1−B10の各々及び、図示しない固定公衆
切り換え電話ネットワーク（PSTN）、または統合された
システムデジタルネットワーク（ISDN）設備を備えた同
様の固定ネットワークに接続されている。移動切り換え
センタMSCと基地局B1−B10との間、または移動切り換え
センタMSCとPSTNまたはISDNとの間の関連する接続は、
第１図に完全には示されていないが、当業者にはよく知
られたものである。同様に、セルラ無線システムには、
１つ以上の移動切り換えセンタを備えていること、及び
各々の追加した移動切り換えセンタを、異なるグループ
の基地局及び他の移動切り換えセンタに、ケーブルまた
は無線リンクを介して、接続してあることも、公知であ
る。

セルC1−C10の各々を、複数の音声即ちスピーチチャ
ンネルと少なくとも１つのアクセスまたは制御チャンネ
ルとに、割り当てる。制御チャンネルは、それらのユニ
ットへ送信された及びから受信された情報によって、移
動局の動作を制御または監督するために、用いられる。
このような情報は、移動局が１つのセルの無線適用範囲
外に、そして別のセルの無線適用範囲内に移動する際
の、入来する通話信号、出立する通話信号、ページ信
号、ページ応答信号、位置登録信号、音声チャンネル割
り当て、保守指令、及び「ハンドオフ」指令を含むこと
ができる。制御または音声チャンネルは、アナログまた
はデジタルモード、またはそれらの組み合わせのいずれ
かで、動作することができる。デジタルモードでは、音
声または制御信号のようなアナログメッセージは、RFチ
ャンネルを通じた送信の前に、デジタル信号表現に変換
される。コンピュータによって或いはデジタル化された
音声装置によって発生されたもののような、純粋なデー
タメッセージは、デジタルチャンネルを通じて直接フォ
ーマット及び送信してもよい。

時分割多重（TDM）を用いているセルラ無線システム
では、複数のデジタルチャンネルが、共通のRFチャンネ
ルを共有することができる。RFチャンネルは、一連の
「タイムスロット」に分割され、各々異なるデータ源か
らの情報のバーストを含み、かつガードタイムによって
互いに分離されており、更にタイムスロットは、当該技
術ではよく知られているように、「フレーム」にグルー
プ化されている。フレーム当たりのタイムスロットの数
は、RFチャンネルによって収容されるよう試みられたデ
ジタルチャンネルの帯域に依存して変化する。フレーム
は、例えば３つのタイムスロットから成り、各々１つの
デジタルチャンネルに割り当てられる。ここで論じられ
る本発明の一実施例では、１フレームは、３つのタイム
スロットを含むように、指定されている。しかしなが
ら、本発明の教示は、フレーム当たりいかなる数のタイ
ムスロットを利用しているセルラ無線システムにでも、
同等に応用可能であることが、明確に理解されよう。

次に第２図を参照すると、そこには、本発明の一実施
例にしたがって使用される移動局の装備の概略ブロック
図が示されている。第２図に例示されている装備は、デ
ジタルチャンネルを通じた通信用に、用いられるもので
ある。マイクロフォン100によって検出され、移動局に
よる通信用に用いられる音声信号は、入力として、スピ
ーチコーダ101に与えられ、これがアナログ音声信号を
デジタルデータビットストリームに変換する。データビ
ットストリームは、次に、デジタル通信の時分割多重ア
クセス（TDMA）技術にしたがって、データパケット即ち
メッセージに分割される。高速関連制御チャンネル（FA
CCH）発生器102は、制御または監督メッセージを、セル
ラ無線システム内の基地局と交換する。従来のFACCH発
生器は、「ブランクアンドバースト」状に動作し、これ
によって、ユーザフレームのデータが無音化され、FACC
H発生器102によって発生された制御メッセージが高速度
で送信される。

FACCH発生器102のブランクアンドバースト動作とは対
照的に、低速関連制御チャンネル（SACCH）発生器103
は、連続的に制御メッセージを基地局と交換する。SACC
H発生器の出力は、固定バイト長、例えば、12ビットを
割り当てられ、そしてメッセージ列（フレーム）内に各
タイムスロットの一部として含まれる。チャンネルコー
ダ104、105、106は、スピーチコーダ101、FACCH発生器1
02及びSACCH発生器103に、夫々接続されている。チャン
ネルコーダ104、105、106の各々は、スピーチコーダ内
の重要なデータビットを保護する畳み込みエンコーディ
ングの技術と、７ビットのエラーチェックを計算するた
めに、スピーチコーダフレーム内の最上位ビット、例え
ば12ビットが用いられるサイクリックリダンダンシチェ
ック（CRC）を用いて入来データを操作することによっ
て、エラー検出及び回復を行なう。

再び第２図を参照して、チャンネルコーダ104、105
は、デジタル化した確認メッセージの、FACCH監督メッ
セージとの時分割多重化のために用いられ、マルチプレ
クサ107に接続されている。マルチプレクサ107の出力
は、２−バーストインターリーバに結合されており、こ
れが、移動局によって送信される各データメッセージ
（例えば、260ビットを含むメッセージ）を、２つの連
続タイムスロットに配置された２つの同等であるが別個
の部分（各部分は130ビットを含む）に分割する。この
ようにして、レイリー（Reyleigh）フェーディングの劣
化効果を大幅に減少させることができる。２−バースト
インターリーバ108の出力は、入力として、モジュロ−
２加算器109に与えられ、ここで、送信すべきデータ
は、以下に記載する本発明のシステムにしたがって発生
される、疑似ランダムキーストリームとの論理的モジュ
ロ−２の加算によって、ビット毎に暗号化される。チャ
ンネルコーダ106の出力は、入力として、22−バースト
インターリーバ110に与えられる。22−バーストインタ
ーリーバ110は、SACCHデータを、22個の連続タイムスロ
ットに分割するが、各々は12バイトの制御情報から成る
１バイトによって占められている。インターリーブされ
たSACCHデータは、バースト発生器111への入力の１つを
形成する。バースト発生器111への別の入力は、モジュ
ロ−２加算器109の出力によって与えられる。バースト
発生器111は、データの「メッセージバースト」を生成
するが、各々は、以下に更に説明するように、タイムス
ロット識別子（TI）、デジタル確認カラーコード（DVC
C）、制御または監督情報、及び送信すべきデータを含
んでいる。

１フレーム中のタイムスロットの各々にて送信される
のは、タイムスロットの識別及び受信機の同期に用いら
れるタイムスロット識別子（TI）と、適切なチャンネル
がデコードされていることを保証するデジタル音声カラ
ーコード（DVCC）である。本発明のフレーム例では、１
組の３つの異なる28ビットのTIが、各タイムスロットに
対して１つ定義され、一方、同一の８ビットDVCCが３つ
のタイムスロットの各々の中で送信される。TI及びDVCC
は、第２図に示すように、バースト発生器111に接続さ
れた同期語/DVCC発生器112によって、移動局内に与えら
れる。バースト発生器111は、モジュロ−２加算器109、
22−バーストインターリーバ110及び同期語/DVCC発生器
112の出力を組み合わせて、各々データ（260ビット）、
SACCH情報（12ビット）、TI（28ビット）、コード化さ
れたDVCC（12ビット）、及びEIA/TIA IS−54によって指
定されたタイムスロットフォーマットにしたがって統合
されることのできる合計324ビットに対する12の区切り
ビットから成る、一連のメッセージバーストを発生す
る。

メッセージバーストの各々は、先に論じたように、１
つのフレームに含まれる３つのタイムスロットの１つの
中で送信される。バースト発生器111は、イコライザ113
に接続され、これは１つのタイムスロットの送信を、他
の２つのタイムスロットの送信と同期させるのに必要な
タイミングを与える。イコライザ113は、基地局（マス
タ）から移動局（スレーブ）に送られるタイミング信号
を検出し、それによってバースト発生器111を同期させ
る。イコライザ113は、TI及びDVCCの値をチェックする
ために用いることもできる。バースト発生器111は、20m
sのフレームカウンタ114にも接続されており、これは、
20ms毎、即ち送信されるフレーム毎に、移動局によって
印加される暗号化コードを更新するのに用いられる。暗
号化コードは、数学アルゴリズムを用い、各移動局に対
して唯一であるキー116の制御の下に、暗号化ユニット1
15によって発生される。このアルゴリズムは、本発明に
したがって、そして更に以下に論ずるように、疑似ラン
ダムキーストリームを発生するのに用いることができ
る。

バースト発生器111によって生成されたメッセージバ
ーストは、RF変調器117に、入力として与えられる。RF
変調器117は、π/4−DQPSK技術（π/4シフトされた、差
動的エンコード直角位相シフトキー）にしたがって、搬
送波周波数を変調するために用いられる。この技術の使
用は、移動局によって送信される情報は、差動的にエン
コードされる、即ち、２つのビットシンボルが、位相の
４つの可能性のある変化、＋または−π/4及び＋または
−３π/4、として、送信されることを暗示している。選
択された送信チャンネルに対する搬送波周波数は、送信
周波数合成器118によって、RF変調器117に供給される。
RF変調器117のバースト変調された搬送波信号出力は、
出力増幅器119によって増幅され、そしてアンテナ120を
介して、基地局に送信される。

移動局は、受信機122に接続されているアンテナ121を
介して、基地局からのバースト変調された信号を受信す
る。選択された受信チャンネルに対する受信機搬送波周
波数は、受信周波数合成器123によって発生され、RF復
調器124に供給される。RF復調器124は、受信した搬送波
信号を中間周波数信号に復調するのに用いられる。この
中間周波数信号を、更にIF復調器125によって復調し、
π/4−DQPSK変調の前に存在していたような元のデジタ
ル情報を復元する。このデジタル情報は、次にイコライ
ザ113を通って、シンボル検出器126に達し、イコライザ
114によって与えられたデジタルデータの２−ビットシ
ンボルフォーマットを、単一ビットのデータストリーム
に変換する。

シンボル検出器126は、２つの別個の出力、即ち、デ
ジタル化されたスピーチデータとFACCHデータとから成
る第１の出力と、SACCHデータから成る第２の出力と
を、生成する。第１の出力は、２−バーストデインター
リーバ128に接続されているモジュロ−２加算器127に供
給される。モジュロ−２加算器127は、暗号化ユニット1
15に接続されており、データを暗号化するために基地局
内の送信機によって用いられる疑似ランダムキーストリ
ームを、ビット毎に、減算することによって、暗号化さ
れた送信されたデータを暗号解読するのに用いられる。
モジュロ−２加算器127及び２−バーストデインターリ
ーバ128は、２つの連続したフレームのデジタルデータ
から得られた情報を組み立てそして再構成するとによっ
て、スピーチ/FACCHデータを再構築する。２−バースト
デインターリーバ128は、２つのチャンネルデコーダ12
9、130に結合されており、これらはコード化と逆の過程
を用いて畳み込み状にエンコードされたスピーチ/FACCH
データをデコードし、サイクリックリダンダンシチェッ
ク（CRC）ビットをチェックして、エラーが発生してい
ないか判断する。チャンネルデコーダ129、130は、一方
でスピーチデータ、そして他方でいずれかのFACCHデー
タ間の相違を検出し、スピーチデータ及びFACCHデータ
を、スピーチ検出器131及びFACCH検出器132に、夫々差
し向ける。スピーチ検出器131は、チャンネルデコーダ1
29によって供給されたスピーチデータを、スピーチコー
ダアルゴリズム、例えばVSELPにしたがって処理し、そ
して基地局によって送信され移動局によって受信された
スピーチ信号を表わすアナログ信号を発生する。次に、
フィルタ処理技術を用いて、スピーカ133による同報通
信に先立って、前記アナログ信号の品質を高めることも
できる。FACCH検出器132によって検出されたいかなるFA
CCHメッセージも、マイクロプロセッサ134に送られる。

シンボル検出器126の第２の出力（SACCHデータ）は、
22−バーストデインターリーバ135に供給される。22−
バーストデインターリーバ135は、22の連続フレームに
わたって広げられたSACCHデータの再組み立て及び再構
成を行なう。22−バーストデインターリーバ135の出力
は、入力として、チャンネル検出器136に与えられる。S
ACCHメッセージは、SACCH検出器137によって検出され、
制御情報がマイクロプロセッサ134に転送される。

マイクロプロセッサ134は、移動局の活動、及び移動
局と基地局との間の通信を制御するものである。基地局
から受信したメッセージにしたがって、マイクロプロセ
ッサ134によって決定が行なわれ、そして移動局によっ
て測定が行なわれる。マイクロプロセッサ134は、端末
キーボード入力及び表示出力ユニット138も、備えてい
る。キーボード及び表示ユニット138は、移動局のユー
ザが、基地局と情報を交換できるようにするものであ
る。

次に、第３図を参照すると、本発明にしたがって用い
られる基地局の装備の概略ブロック図が示されている。
第２図に示された移動局の装備を、第３図に示された基
地局機器と比較すると、移動局及び基地局によって用い
られている装備の多くは、構造及び機能において、実質
的に同一であることが、示される。このような同一の装
備は、便宜上そして一貫性のために、第２図に関連して
用いたものと同一の参照番号を第３図に付番するが、第
３図ではダッシュ（′）を付加えることによって、区別
することにする。

しかしながら、移動局と基地局装備との間には幾らか
の細かい相違がある。例えば、基地局は、１本のみでは
なく、２本の受信アンテナ121′を有する。受信アンテ
ナ121′の各々に関連するのは、受信機122′、RF復調器
124′、そしてIF復調器125′である。更に、基地局は、
プログラマブル周波数組み合わせ器（combiner）118A′
を備えており、これは送信周波数合成器118′に接続さ
れている。周波数組み合わせ器118A′と送信周波数合成
器118′は、適用可能なセルラ周波数再使用計画にした
がって、基地局によって用いられるRFチャンネルの選択
を遂行する。基地局は、しかしながら、移動局にあるユ
ーザキーボード及び表示ユニット138に類似したユーザ
キーボード及び表示ユニットを備えていない。しかし、
これは、２つの受信機122′の各々から受信した信号を
測定するため、そしてマイクロプロセッサ134′に出力
を与えるために接続された信号レベルメータ100′を備
えている。移動局と基地局との間の装備におけるその他
の相違も存在するが、それは当該技術ではよく知られた
ものである。

これまでの議論は、本発明のシステムの動作環境に焦
点を当てたものであった。以下、本発明の特定実施例の
具体的な説明を記載する。先に開示し、以後用いられる
ように、「キーストリーム」という用語は、例えば、RF
チャンネルのような、送信または媒体への記憶に先立っ
てデジタル的にエンコードされた、無許可のアクセスを
受けやすい、メッセージまたはデータ信号を暗号化する
のに用いられる疑似ランダムな一連の二進ビットまたは
ビットブロックを意味する。「キーストリーム発生器」
は、複数のビットから成る秘密キーを処理することによ
って、キーストリームを発生する装置を意味する。暗号
化は、単に、キーストリームの暗号化されるデータへの
モジュロ−２加算によって、実行することができる。同
様に、暗号解読は、暗号化されたデータからのキースト
リームの同一コピーのモジュロ−２減算によって実行さ
れても良い。

総じて言えば、キーストリーム発生器は、夫々第２及
び第３図の要素115及び115′によって表わされる、比較
的小数の秘密ビット、即ち要素116及び116′で表わされ
る秘密キーを、送信（または記憶）に先立ってデータメ
ッセージを暗号化するのに用いられる、かなり大きな数
のキーストリームビットに拡張する機構を提供するもの
である。エンコードされたメッセージを暗号解読するに
は、受信機は、そのメッセージを暗号化するのに用いら
れたキーストリームビットへのインデックスを「知っ
て」いなければならない。言い換えれば、受信機は、同
一キーストリーム発生器を有し送信機と同一キーストリ
ームビットを生成するのみならず、メッセージを適切に
デコードする場合、受信機のキーストリーム発生器を送
信機のキーストリーム発生器と同期して動作させなけれ
ばならない。通常、同期は、キーストリームビットの発
生に参加したビット、ブロックまたはメッセージカウン
タのような、内部メモリ素子毎の内容を、エンコーディ
ングシステムからデコーディングシステムまで定期的に
送信することによって、達成される。しかしながら、同
期は、二進カウンタのような算術的ビットブロックカウ
ンタを用い、キーストリームビットの新しいブロックが
生成される毎にそれらのカウンタをある量だけ増分する
ことにより、簡素化することができる。このようなカウ
ンタは、リアルタイム、即ち、時間、分、秒、のクロッ
クチェーンの一部を形成することができる。後者の形式
のカウンタに頼るキーストリーム発生器は、先に引用し
た、「タイムオブデイ」駆動型キーストリーム発生器と
して知られている。

キーストリーム発生器のビット毎またはブロック毎の
前進（advancing）に用いられる正確な方法、及び送信
回路を受信回路と同期させるのに用いられる特定の方法
は、上述のように、「セルラ通信システム用連続暗号同
期」と題された係属中の特許出願連番第556,102号の主
題であることに注意されたい。本発明のシステムは、以
後詳細に述べるように、例えば、セルラ遠隔通信システ
ムにおけるRFチャンネルを通じたデジタル通信を防護す
るのに用いることができる、効果的な暗号化システムの
有効な実施に向けられたものである。この暗号化システ
ムは、秘密キーに含まれている複数のキービットに対し
て、毎秒多数のブール演算を行なうことにより、かなり
の数のキーストリームビットを生成する、キーストリー
ム発生器を備えている。本発明のキーストリーム発生器
は、簡素なマイクロプロセッサアーキテクチャを有する
集積回路を用いて、実施することができる。

次に第４図を参照すると、従来技術のキーストリーム
発生器の概略ブロック図をここで見ることができる。選
択的なブロックカウンタ201は、組み合わせ論理回路202
への第１の多ビット入力を与える。複数の１ビットメモ
リ素子、即ちフリップフロップM₁，M₂，M₃……M_Nが、組
み合わせ論理回路への第２の多ビット入力を与える。１
ビットの出力d₁，d₂，d₃……d_Nから成る組み合わせ論理
回路202の出力の一部は、フリップフロップM₁〜M_Nにフ
ィードバックされる。フリップフロップM₁〜M_Nに供給さ
れる一連のビットクロック入力パルス内の各クロックパ
ルスの後に、出力d₁〜d_Nは夫々フリップフロップM₁〜M_N
の次の状態となる。組み合わせ論理回路202の相応しい
構造によって、ストレート二進カウンタ、最大長シーケ
ンスを実行する線形フィードバックシフトレジスタ、ま
たはその他のいずれかの形式の線形または非線形連続カ
ウンタを形成するように、フリップフロップM₁〜M_Nを構
成することができる。いずれの場合でも、受信機端にお
けるフリップフロップM₁〜M_Nの状態の各々、及びブロッ
クカウンタの状態は、送信機端における対応する要素の
状態と同一としなければならない。リセットまたは同期
機構204が、受信機を送信機と同期させるのに用いられ
る。

第４図への参照を続けて、複数の秘密キービットk1、
k2、k3...knは、組み合わせ論理回路202への第３の多ビ
ット入力を形成している。秘密キービットの数ｎは、常
に100ビットプラスまたはマイナス（＋／−）２の因子
の領域にある。秘密キーk1−knの各々が、少なくとも、
キーストリーム内のビットの各々に影響を及ぼす可能性
を有することが望ましい。そうでないと、盗聴する場
合、暗号化されたデータを暗号解読しモニタするために
は、秘密キービットk1−knの僅かなサブセットのみを解
読すればよいことになる。不許可の傍受の危険性は、し
かしながら、キーストリーム内の各ビットの値（論理状
態）を、特定の秘密キービットの値だけでなく、全ての
他の秘密キービットの値、並びにブロックカウンタ201
の状態及び他の内部メモリ状態にも依存させるようにす
れば、大幅に減少させることができる。これまで、この
ような依存性の確立は、法外な数のブール演算を伴うも
のであった。例えば、秘密キーが、100個の秘密キービ
ットから成るものと仮定する。これら秘密キービットの
各々がキーストリーム内の各ビットに影響を与えると、
キーストリームビット当たり合計で100個の組み合わせ
演算が必要となろう。したがって、１万個のキーストリ
ームビットを生成するには、合計で100万個の組み合わ
せ演算が必要となり、更に各キーストリームビットを１
つ以上の内部メモリ状態にも依存させるとすると、その
数は更に大きなものとなろう。本発明の目的の１つは、
各キーストリームビットの秘密キービットの各々による
依存性を維持しつつ、キーストリームビット毎に必要と
される組み合わせ演算の数を大幅に減少させることであ
る。

本発明によれば、例えば、100個の秘密キービットか
らの、数千個の疑似ランダムキーストリームビットの生
成を、多段拡張過程として、見ることができる。複数の
拡張ステージが共に縦属されており、各々が連続的によ
り小さくなる拡張比を有している。最初のステージによ
る拡張は、キーストリームビット当たり必要な論理（ブ
ール）演算数を最小化するために、後続のステージによ
るものより、少ない頻度で実行される。加えて、最初の
拡張ステージは、秘密キービットに対する依存性が高い
複数の出力ビットを与えるように構成されており、後続
のステージで実行されなければならない論理演算数を更
に減少させている。

次に第５図を参照すると、本発明の教示にしたがって
構成された、キーストリーム発生器システムの概略ブロ
ック図がここに見られる。複数の機密キービットk1、k
2、k3...が、入力として第１ステージの拡張205に与え
られる。キービットk1、k2、k3...入力は、秘密キービ
ットk1、k2、k3...knの幾つか、しかし好ましくは全て
を含むこともできる。加えて、または随意的に、第１ス
テージの拡張205への入力は、メッセージカウンタやブ
ロックカウンタの出力、フレーム開始時の時間またはブ
ロックカウント数を表わすデート−タタイムスタンプ、
または送り手及び受け手によって同期される得るその他
の可変出力を、含むことができる。時間と共にゆっくり
と変化するいかなる内部メモリ出力でも、第１ステージ
の拡張205への入力として、用いることができる。第１
ステージの拡張205は、時たま、例えばメッセージ毎に
１回、実行されなければならないので、ゆっくりと変化
する入力が望ましい。

第１ステージの拡張205は、秘密キービットk1、k2、k
3...の数より、大幅に大きなサイズの拡張された出力を
発生する。この拡張された出力は、メモリ素子206内に
記憶され、組み合わせ論理回路207によってアクセスさ
れる。組み合わせ論理207は、以下に更に完全に記載す
るような、第２ステージの拡張を行なうものである。カ
ウンタ即ちレジスタ208の出力は、組み合わせ論理207へ
の入力を形成する。レジスタ208は、キーストリームビ
ットの各ブロックの発生に先立ち、新しい開始状態に初
期化される。初期値発生器209は、レジスタ208にその開
始状態を与える。この開始状態は、キーストリームビッ
トの各特定ブロックに対して異なるが、当該特定ブロッ
クのブロックナンバーの関数であり、そして、秘密キー
ビットk1〜knの内のある組合せの関数ともすることがで
きる。

組み合わせ論理207の第１の出力210は、レジスタ208
にフィードバックされる。出力210は、演算の各サイク
ル後に、レジスタ208の新しい状態となる。組み合わせ
論理207の第２の出力211は、先の第２及び３図に示した
ように、データストリームと混合されることになるキー
ストリームビットを形成する。出力211においてサイク
ル毎に生成されるキーストリームビットの数は、いずれ
かの２の倍数、即ち、８、16、32、56等とすることがで
きる。このようなビットを、まとめて「キーワード」と
呼ぶことにする。レジスタ208の再初期化の前に出力211
において生成されたキーワードのいくつかまたは全て
は、キーブロック212にグループ化される。キーブロッ
ク212は、例えば、レジスタ208の再初期化に先立って、
サイクル毎または１サイクルおきに生成される全てのキ
ーワードから成るものである。

第５図に描かれそして先に論じたキーストリーム発生
器システムの従来の実施は、多数の複雑な組み合わせ論
理回路が必要であり、これは複数の論理ゲート、即ちア
ンド（AND）、オア（OR）等を相互接続することによっ
て別個に実現されたとすると、非常に特定された用途に
のみ有用な、巨大で高価なチップとなることを、当業者
であれば認めるであろう。一方、算術及び論理ユニット
（ALU）は、種々の小型、低価格、そして多目的マイク
ロプロセッサの標準構成物である。本発明は、このよう
なALUを用いて、必要な組み合わせ論理機能の全てを実
現するための手段を提供するものである。

従来のALUは、プログラムの制御下で動作し、いずれ
か２つの８ビットまたは16ビット二進語間で、組み合わ
せ関数ADD、SUBTRACT、BITWISE EXCLUSIVE OR、AND、
ORを実行することができる。ALUが、第５図の装置にお
いて必要とされるブール関数の全てを連続的に実施する
のに用いられる場合、実行され得る１秒毎の完全サイク
ル数に関して測定されたALU動作速度は、大幅に減少さ
れていよう。本システムにおいて用いられる多段拡張
は、しかしながら、最も頻繁に実行される組み合わせ論
理207から第１ステージの拡張205における大量のキー依
存関数の頻繁でない定期的な計算までに対して、サイク
ル当たりのプログラム命令数、即ちALUを利用する回数
を最小化することによって、ALU速度の過度の減少を防
止する。先の文における単語「大きな」によって、例え
ば、秘密キービット数ｎより大きな程度の等級が意味さ
れる。

一旦レジスタ208が開始値で初期化されると、組み合
わせ論理207は、出力211にキーワードのストリームを発
生し、そしてレジスタ208がフィードバック値を出力210
において再びロードされる毎に、追加キーワードを発生
し続ける。しかしながら、キーワード発生過程の保全性
を密かに損い得る困難が生じることがある。例えば、レ
ジスタ208の内容が常にそれらの初期値に戻るとする
と、これまでに発生されたキーワード列が再び繰り返さ
れることになる。同様に、レジスタ208の内容が、現在
のキーブロックの発生において既に見出された値（初期
値である必要はない）に戻ると、システムは、「短絡サ
イクル」を行なっていると言われる。以前に示唆した理
由、例えば、不許可の暗号解読の容易さのため、単一の
キーブロックの発生において、キーワードの連続が繰り
返し始まること、または短絡サイクルが起こることは、
望ましいことではない。更に、レジスタ208の内容が、
ある点、例えばＭ番目のキーワードを発生した後に、別
のキーブロックの発生後に存在した或いは存在するであ
ろうある値と等しくなると、２つのキーブロックは、そ
の点以降、同一となり、これも望ましくない出来事であ
る。

したがって、組み合わせ論理207と関連するレジスタ2
08（「組み合わせ論理／レジスタの組み合わせ」）は、
ある回数連続的に動作する時、（ｉ）ブロック当たりの
キーワード数より短いサイクルを生成するのではなく、
そして（ii）レジスタ208の唯一の開始状態毎に唯一の
キーワード列を生成するべきである。後者の要件を満た
すためには、２つの異なる開始状態が、同一状態に収束
できないようにすればよい。更に、前述の要件の両方
は、メモリ206の内容には関係無く適用すればよい。以
下により詳細に説明するように、本発明はこれらの問題
を軽減し、そしてキーワード発生過程の保全性を強化す
るものである。

組み合わせ論理／レジスタの組み合わせの状態遷移図
が収束する分岐点を有する時、そのような組み合わせ
は、どちらの道を取るかについての曖味さのため、この
ような分岐点を介して逆に実行することはできない。し
たがって、組み合わせを処理する過程が曖味でないこ
と、または逆転可能であることが示されれば、収束分岐
点はその状態遷移図には存在しないことの証明となる。
このような過程を以下に記載し、かつ論じることにす
る。

次に第６図を参照すると、第５図に示したキーストリ
ーム発生器の第２拡張ステージの部分的概略ブロック図
が、ここに見られる。第５図のレジスタ208は、第６図
では３つのバイト長レジスタ208A、208B、208Cに分割さ
れている。レジスタ208A、208B、208Cは、例えば、８ビ
ットレジスタとすることができる。レジスタ208A、208
B、208Cの初期化に続いて、新しい状態値が、次の式か
ら計算される。

（１）Ａ′＝Ａ＃［Ｋ（Ｂ）＋Ｋ（Ｃ）］ （２）Ｂ′＝Ｂ＃Ｒ（Ａ） （３）Ｃ′＝Ｃ＋１ ここで、 Ａ′は、レジスタ208Aに対する新しい状態値であり、 Ｂ′は、レジスタ208Bに対する新しい状態値であり、 Ｃ′は、レジスタ208Cに対する新しい状態値であり、 Ａは、レジスタ208Aに対する現在の状態値であり、 Ｂは、レジスタ208Bに対する現在の状態値であり、 Ｃは、レジスタ208Cに対する現在の状態値であり、 ＋は、ワード長モジュロ加算、例えば、バイト側モジュ
ロ−256の加算を意味し、 ＃は、＋（上で定義したように）または、ビットワイズ
（bitwize）の排他的オア（XOR）を意味し、Ｋ（Ｂ）
は、第５図に示したメモリ206のアドレスＢに配置され
た値Ｋであり、 Ｋ（Ｃ）は、第５図に示したメモリ206のアドレスＣに
配置された値Ｋである。

注意：メモリ206に記憶された値Ｋの各々は、第５図に
示す第１ステージの拡張205によって、既に計算され、
全ての秘密キービットの複雑な関数となった。Ｒ（Ａ）
は、固定参照テーブルＲ内のアドレスＡに配置された値
である。また、Ａのビットは、入力として、出力Ｒを生
成する組み合わせ論理ブロックに供給される。参照テー
ブルＲ、またはその代わりに、組み合わせ論理ブロック
は、Ａのワード長以上で、Ｂのワード長以下の数の出力
ビットを与えるなければならない。Ａ及びＢが両方共８
ビットバイトである場合、例えば、Ｒも８ビットバイト
で、参照テーブルＲは256個の値を含むことになる。

値Ｒは、入力から出力に1:1のマッピングを有せねば
ならない。即ち、入力ビットの各可能性のある状態は、
唯一の出力値に割り付けなければならない。これは、Ｒ
関数が逆転可能であることを保証し、これが更に、全過
程を、以下にあげる関係によって、逆転できることを保
証するものである。

（１）Ｃ＝Ｃ−１ （２）Ｂ＝Ｂ＃＃Ｒ′（Ａ） （３）Ａ＝Ａ＃＃［Ｋ（Ｂ）＋Ｋ（Ｃ）］ ここで、 −は、ワード長のモジュロ減算を意味し、 ＃＃は、＃の逆演算、即ち、−（先に定義したような）
またはビットワイズXORを、意味し、及び Ｒ′は、1:1参照テーブル、または組み合わせ論理Ｒの
逆である。

この逆転可能性は、上述の組み合わせ論理／レジスタ
の組み合わせの状態遷移図には収束分岐点がないことを
示しており、したがって、全ての開始状態が唯一のキー
ワード列を発生することを保証している。更に、Ｃが１
ずつのみ増分され、そして2W回の繰り返しの後までその
初期値には戻らないので（Ｗは用いたワード長）、この
過程は、最小サイクル長を保証するものである。例え
ば、値Ａ、Ｂ、Ｃ、Ｒ及びＫの全てが８ビットバイトの
場合、最小サイクル長は256となる。各繰り返し（サイ
クル）毎に、１つのキーワード（バイト）が抽出される
と、列の中途半端な繰り返しの恐れがなく、合計256バ
イトを抽出することができる。一方、２度の繰り返し毎
に１回キーワードが抽出されると、列の中途半端な繰り
返しなしに、合計128個のキーワードを抽出することが
できる。前の２つの文における単語「抽出」によって、
キーワードの収集と、第５図におけるキーブロック212
のようなキーブロックへの配置を、意味する。本発明に
用いることができるキーワード抽出の特定の方法を、す
ぐ後に述べる。

第６図に関して、レジスタ208にフィードバックされ
る、組み合わせ論理267の出力210を計算するための過程
を述べた。一般的に言うと、中間量Ａ、ＢまたはＣのい
ずれか１つを、直接抽出し、各繰り返しにおいてキーワ
ードとして用いることもできる。Ｓ＝（Ａ、Ｂ、Ｃ）が
組み合わせ論理／レジスタの組み合わせの現在の状態を
表わすとすると、S0への初期化に続いて、一連の状態S
0、S1、S2、S3、S4、S5、S6、S7...というように遷移す
ることになろう。しかしながら、後続のキーブロックの
計算において、レジスタが例えばS2に初期化されると、
その結果の列S2、S3、S4、S5、S6、S7...は、２つのキ
ーワード（S0、S1）だけシフトした最初の列と同一とな
る。したがって、状態Ｓからの値Ａ、Ｂ、Ｃが直接キー
ワードとして用いられると、このような同一性が異なる
キーブロック間で表われるかもしれない。これを防止す
るために、本発明のシステムは、キーブロック内の値の
位置にしたがって抽出された値の各々を変更して、同一
値が別のブロック内の異なるキーワード位置に抽出され
た場合、異なるキーワードが得られるようにしている。
後者の目的を達成するための例示的方法を、以下に記載
する。

Ｎを現在計算中のキーブロック内のキーワードの数と
し、Ｓ＝（Ａ、Ｂ、Ｃ）をキーワードＮが抽出されよう
とする繰り返しにおけるレジスタ208の現在の状態とす
る。キーワードＷ（Ｎ）の値は、次のように計算するこ
とができる。

Ｗ（Ｎ）＝Ｂ＋′Ｋ［Ａ＋Ｎ］ ここで、 ＋は、XORを意味し、 ＋′は、＋（直前で定義した）またはワード長−モジュ
ロ加算のいずれかを意味する。

キーワード抽出のための他の相応しい例示的方法は、
次を含んでもよい。

Ｗ（Ｎ）＝Ｂ＋Ｋ［Ｒ（Ａ＋Ｎ）］または Ｗ（Ｎ）＝Ｒ［Ａ＋Ｎ］ Ｋ［Ｂ＋Ｎ］等。

キーワード抽出方法の正確な性質 （precise nature）は、本発明の動作に不可欠ではない
が、本発明のシステムにしたがって最良の暗号の特性を
得るためには、抽出されたキーワードの値は、キーブロ
ック内のそれらのそれぞれの位置の関数であることが、
推薦される。

上述の本発明のシステムの種々の実施例の説明から解
るように、他のパラメータの内、選択された数の秘密キ
ービットの関数であり、かつデジタル情報ストリームを
暗号化するために用いられる疑似ランダムビット列を、
発生するために必要とされる特定の論理ハードウエアの
量を減少するための方法及び手段が含まれている。本シ
ステムは、プログラム制御の下で、従来のマイクロプロ
セッサ集積回路チップにおいて一般的に見られる形式
の、汎用算術及び論理ユニット（ALU）のタイムシェア
リングを、伴うものである。本システムは、元の入力キ
ービットの数より数の上で大きな１組のデジタル値を事
前に計算し、そしてメモリに記憶することにより、キー
ビットに対する依存性の選択された複雑度に対して、出
力ビット毎に必要とされるALU動作の数を最小化する。
記憶されたデジタル値の各々は、キービットの異なりか
つ複雑な論理的関数であり、更に随意的に他のパラメー
タの関数にもなる。メモリ内に記憶されたデジタル値
は、多数の疑似ランダム出力ビットを生成するために多
数回実行される後続の計算ステップにおいて、参照テー
ブルとして用いられる。本発明のシステムの疑似ランダ
ムビット列発生器は、デジタル値の事前計算において、
秘密キーワードと共に多くの別の変数も用いることでき
ることは、理解されよう。例えば、次にあげるパラメー
タをこの目的のために用いることができる。メッセージ
番号、送信者の識別コードまたは電話番号、意図した受
信相手の識別コードまたは電話番号、タイムオブデイ、
日付、メッセージ開始時のカウンタ値、通話番号、対話
者の間で交換される乱数、または、送信者及び受信者が
有する同意手段に係るその他のビットまたは量である。

先の議論を基に、本システムは、１組の値の次の状態
を計算する組み合わせ論理回路への入力を形成する、あ
る数のフリップフロップまたはレジスタステージの状態
をまず初期化することによって、事前計算され記憶され
たデジタル値を用いることは、明白であろう。そして、
計算された値は、次の状態の計算完了時に、レジスタス
テージに転送され、それらの新しい値は、組み合わせ論
理によって新しい開始状態として用いられ、一連の付加
的状態を繰り返し発生し、その論理値を更に組み合わさ
れて所望の出力疑似ランダムビット列を形成する。

フリップフロップまたはレジスタステージは、少なく
とも、現在発生されている疑似ランダムビットのブロッ
クの識別コードまたはブロックカウント、そして随意的
に、秘密キービットのいくつかまたは全てのような、対
話者間で同意された他のパラメータに依存してもよい、
１つの値に初期化される。初期化値のこのような依存性
は、各唯一のブロック識別番号に対して唯一の初期レジ
スタ状態を生成することが好ましいが、必ずしもそうで
なくてもよい。

各連続状態間のレジスタ／組み合せ論理状態機械の各
遷移時に発生されるビットのサブグループは、レジスタ
状態のだけでなく、当該機械によって現在発生されつつ
ある疑似ランダムビットブロック内のサブグループの位
置の関数である。状態機械は、異なる開始状態が、ある
後続の繰り返しにおいて、同一中間状態になることがで
きないことを確実にすることにより、状態機械のレジス
タステージを初期化するのに用いられる各異なるブロッ
ク識別コードまたはブロック番号に対して、特定のブロ
ック内で唯一の疑似ランダムビット列を生成すること
を、保証されている。

先の説明から、本発明の状態機械は、組み合せ論理回
路に接続されたある数のレジスタステージで構成され、
そして任意の内容を有するキー依存型参照テーブルを採
用しており、連続的な繰り返しにおいて巡回的挙動を示
すことも、解るであろう。保証された最短サイクル長
は、レジスタステージのサブグループが、例えば、少な
くとも最短長の規則的に増分する二進カウントシーケン
スのような、定義された巡回シーケンスを実行すること
を規定することによって、確保される。

また、状態機械は、その中に１つ以上の固定参照テー
ブルを備えており、これに対話者が同意し、そして入力
アドレスから出力アドレスへの1:1マッピング特性を有
しているので、逆転可能なのである。

これまでの説明は、本発明のある特定の実施例のみを
示したものである。しかしながら、本発明の精神及び範
囲から実質的に逸脱することなく、多くの修正及び変更
が可能であることを、当業者は認めるであろう。したが
って、ここに記載された本発明の形式は、単に例示的な
ものであり、以下の請求の範囲に規定された本発明の範
囲に対する制限として意図したものではないことは、明
確に理解されるべきである。

Claims (27)

(57)【特許請求の範囲】
1. 【請求項１】デジタルデータの暗号化に用いるための疑
   似ランダムビット列を発生する方法であって、前記疑似
   ランダムビット列は複数の選択されたキービットの関数
   であり、 各々が少なくとも前記選択されたキービットの幾つかに
   ついての関数である第１の複数の多ビット値を発生する
   段階と、 前記第１の複数の多ビット値の各々をメモリに記憶する
   段階と、 第２の複数の多ビット値の各々を参照テーブルに記憶す
   る段階と、 動作の繰り返しの各々に応答してレジスタに含まれる現
   在値を変化させることによって、特定の時の現在値を有
   する前記レジスタにおいて数値の列を発生する段階と、 前記参照テーブルまたは前記メモリに記憶された複数の
   多ビット値の少なくとも１つと前記レジスタに含まれる
   前記発生された数値の少なくとも一部とについての関数
   である各々の値から成る多ビット値の列を、第１の事前
   に選択されたアルゴリズムに従って繰り返し計算する段
   階と、 前記レジスタに含まれる現在値を、各々の計算の結果と
   して得られる値を用いて繰り返しリセットする段階と、 各々の多ビット値計算の結果として得られる値の関数で
   ある多ビットキーワードを繰り返し計算する段階と、 少なくとも前記多ビットキーワードの幾つかを連続的に
   組み合わせて、前記疑似ランダムビット列を発生する段
   階と、 を含む前記方法。
2. 【請求項２】デジタルデータの暗号化のために用いる疑
   似ランダムビット列を発生する、請求項１記載の方法に
   おいて、第１の複数の多ビット値を発生する前記段階
   が、各々が前記選択されたキービットの全てについての
   関数である第１の複数の多ビット値を発生する段階を含
   む、前記方法。
3. 【請求項３】デジタルデータの暗号化のために用いる疑
   似ランダムビット列を発生する、請求項１記載の方法に
   おいて、前記レジスタに含まれる現在値を周期的に初期
   化する追加の段階を含む前記方法。
4. 【請求項４】デジタルデータの暗号化のために用いる疑
   似ランダムビット列を発生する、請求項１記載の方法に
   おいて、第１の複数の多ビット値を発生する前記段階
   が、前記選択されたキービットの少なくとも幾つかと、
   前記計算の繰り返しと比較して遅い速度で周期的に増分
   されるカウンタに含まれる値と、の両方についての関数
   である各々の値から成る第１の複数の多ビット値を発生
   する段階を含む、前記方法。
5. 【請求項５】送受信されるデジタルデータのストリーム
   が暗号的にエンコードされて遠隔通信の機密性を与える
   デジタル通信システムであって、 二進ビットの疑似ランダムキーストリームを、前記シス
   テム中の少なくとも１つの送信機及び少なくとも１つの
   受信機のデジタル信号を搬送する情報に付加して、前記
   システム内で送受信すべきデジタルデータのストリーム
   を作成する手段と、 前記二進ビットの疑似ランダムキーストリームを発生す
   るきーストリーム発生手段であって、 複数の多ビット値の各々を個別の位置に記憶する手段
   と、 各動作サイクルに応答してレジスタに含まれる現在値を
   変化させることによって、前記レジスタにおいて数値の
   列を発生する手段と、 前記記憶された複数の多ビット値の少なくとも１つと前
   記レジスタに含まれる数値とについての関数である各々
   の値から成る多ビット値の列を、第１の事前に選択され
   たアルゴリズムに従って繰り返し計算する手段と、 前記レジスタの内容を、各々の計算の結果として得られ
   た値を用いて繰り返しリセットする手段と、 各々の多ビット値計算の結果として得られた値の関数で
   ある多ビットキーワードを、繰り返し計算する手段と、 少なくとも前記多ビットキーワードの幾つかを連続的に
   組み合わせて、前記二進ビットの疑似ランダムキースト
   リームを発生する手段と、 を含む前記キーストリーム発生手段と、 を含む前記システム。
6. 【請求項６】請求項５記載のデジタル通信システムにお
   いて、 前記キーストリーム発生手段が、選択された複数の秘密
   キービットの関数として前記二進ビットの疑似ランダム
   キーストリームを発生する手段をさらに含み、 前記デジタル通信システムが、各々が少なくとも前記選
   択されたキービットの幾つかの関数である複数の多ビッ
   ト値を発生する手段をさらに含み、 複数の多ビット値の各々を個別の位置に記憶する前記手
   段が、前記発生された複数の多ビット値の各々を記憶す
   る手段を含む、 前記システム。
7. 【請求項７】請求項５記載のデジタル通信システムにお
   いて、前記レジスタの内容を周期的に初期化する手段を
   さらに含む前記システム。
8. 【請求項８】デジタル情報のストリームを暗号化するた
   めに用いられる疑似ランダムビット列を発生するために
   必要な論理ハードウエアの量を減少させる方法であっ
   て、前記疑似ランダムビット列は複数の選択されたキー
   ビットの関数であり、 選択されたキービットの数より数において大きなデジタ
   ル値の組であって、各々のデジタル値が少なくとも前記
   キービットの幾つかの論理関数である前記デジタル値の
   組をメモリに記憶する段階と、 前記メモリに記憶されたデジタル値の少なくとも１つの
   関数である各々の値から成る多ビット値の列を、プログ
   ラムによる制御の下で汎用マイクロプロセッサを用いて
   繰り返し計算する段階と、 少なくとも前記計算された多ビット値の列の一部を組み
   合わせて、前記疑似ランダムビット列を発生する段階
   と、 を含む前記方法。
9. 【請求項９】疑似ランダムビット列を発生するために必
   要な論理ハードウエアの量を減少させる、請求項８の方
   法において、メモリに記憶する前記段階が、 各々が少なくとも前記選択されたキービットの幾つかの
   関数である複数の多ビット値を発生する段階と、 前記複数の多ビット値の各々をメモリの個別の位置に記
   憶する段階と、 を含む、前記方法。
10. 【請求項１０】疑似ランダムビット列を発生するために
    必要な論理ハードウエアの量を減少させる、請求項９の
    方法において、複数の多ビット値を発生する前記段階
    が、各々が前記選択されたキービットの全てについての
    関数である複数の多ビット値を発生する段階を含む、前
    記方法。
11. 【請求項１１】疑似ランダムビット列を発生するために
    必要な論理ハードウエアの量を減少させる、請求項９の
    方法において、各動作サイクルに応答して前記レジスタ
    に含まれる現在値を変更することにより数値の列を発生
    する段階をさらに含む前記方法。
12. 【請求項１２】疑似ランダムビット列を発生するために
    必要な論理ハードウエアの量を減少させる、請求項11の
    方法において、多ビット値の列を繰り返し計算する前記
    段階が、 前記記憶されたデジタル値の少なくとも１つと前記レジ
    スタに含まれる前記発生された数値の少なくとも一部と
    についての関数である各々の値から成る多ビット値の列
    を、第１の事前に選択されたアルゴリズムに従って繰り
    返し計算する段階と、 前記レジスタに含まれる現在値を、各々の計算の結果と
    して得られる値を用いて繰り返しリセットする段階と、 を含む、前記方法。
13. 【請求項１３】疑似ランダムビット列を発生するために
    必要な論理ハードウエアの量を減少させる、請求項11の
    方法において、前記レジスタに含まれる現在値を周期的
    に初期化する付加的な段階を含む前記方法。
14. 【請求項１４】疑似ランダムビット列を発生するために
    必要な論理ハードウエアの量を減少させる、請求項９の
    方法において、複数の多ビット値を発生する前記段階
    が、前記選択されたキービットの少なくとも幾つかと、
    前記計算の周期的繰り返しと比較して遅い速度で周期的
    に増分されるカウンタに含まれる値と、の両方について
    の関数である各々の値から成る複数の多ビット値を発生
    する段階を含む、前記方法。
15. 【請求項１５】デジタルデータを暗号化するために用い
    られる疑似ランダムビット列を発生する方法であって、 複数の多ビット値を発生する段階と、 前記複数の多ビット値を個別の位置に記憶する段階と、 動作の繰り返しの各々に応答してレジスタに含まれる現
    在値を変更することによって、特定の時の現在値を有す
    る前記レジスタにおいて数値の列を発生する段階と、 前記記憶された多ビット値と前記発生された数値の少な
    くとも１つの関数である各々の値から成る多ビット値の
    列を、第１の事前に選択されたアルゴリズムに従って繰
    り返し計算する段階と、 前記現在値を、各々の多ビット値計算の結果として得ら
    れる値を用いて繰り返しリセットする段階と、 各々の多ビット値計算の結果として得られる値の関数で
    ある多ビットキーワードを繰り返し計算する段階と、 少なくとも前記多ビットキーワードの一部を連続的に組
    み合わせて、前記疑似ランダムビット列を発生する段階
    と、 を含む前記方法。
16. 【請求項１６】デジタルデータを暗号化するために用い
    られる疑似ランダムビット列を発生する、請求項15の方
    法において、 前記疑似ランダムビット列は、複数の選択されたキービ
    ットの関数であり、 前記方法は、各々が少なくとも前記選択されたキービッ
    トの幾つかについての関数である複数の多ビット値を発
    生する段階をさらに含み、 複数の多ビット値を個別の位置に記憶する前記段階が、
    前記発生された多ビット値の各々をメモリの個別の位置
    に記憶する段階を含む、 前記方法。
17. 【請求項１７】デジタルデータを暗号化するために用い
    られる疑似ランダムビット列を発生する、請求項16の方
    法において、複数の多ビット値を発生する前記段階が、
    各々が前記選択されたキービットの全てについての関数
    である複数の値を発生させる段階を含む、前記方法。
18. 【請求項１８】デジタルデータを暗号化するために用い
    られる疑似ランダムビット列を発生する、請求項15の方
    法において、前記レジスタに含まれる現在値を周期的に
    初期化する付加的な段階を含む前記方法。
19. 【請求項１９】デジタルデータを暗号化するために用い
    られる疑似ランダムビット列を発生する、請求項16の方
    法において、複数の多ビット値を発生する前記段階が、
    前記選択されたキービットの少なくとも幾つかと、前記
    計算の周期的繰り返しと比較して遅い速度で周期的に増
    分されるカウンタに含まれる値と、の両方についての関
    数である各々の値から成る複数の多ビット値を発生する
    段階を含む、前記方法。
20. 【請求項２０】通信システムにおいて使用される暗号法
    の変数を発生する方法であって、前記変数は複数の選択
    されたキービットの関数であり、 前記複数の選択されたキービットの数より数において大
    きな複数の多ビット値をメモリに記憶する段階と、 レジスタを選択された初期多ビット値に初期化する段階
    と、 前記レジスタのための新たな多ビット値を、あるアルゴ
    リズムに従って繰り返し計算する段階であって、各々の
    繰り返しにおいて計算される新たなレジスタ値の少なく
    とも幾つかのビットが、以前のレジスタ値の少なくとも
    幾つかのビットを前記メモリに記憶された複数の多ビッ
    ト値の１つの少なくとも幾つかのビットと組み合わせた
    結果得られたものである前記段階と、 少なくとも前記計算されたレジスタ値の一部を組み合わ
    せて、前記変数を発生する段階と、 を含む前記方法。
21. 【請求項２１】請求項20の方法において、前記メモリが
    参照テーブルを含む、前記方法。
22. 【請求項２２】請求項21の方法において、 前記レジスタが複数の８ビットレジスタを含み、 前記参照テーブルが256の値を含む、 前記方法。
23. 【請求項２３】請求項20の方法において、前記メモリに
    記憶された複数の多ビット値の少なくとも幾つかが、秘
    密データの機能を有している、前記方法。
24. 【請求項２４】暗号法の変数を発生するシステムであっ
    て、前記変数は複数の選択されたキービットの関数であ
    り、 前記複数の選択されたキービットの数より数において大
    きな複数の多ビット値をメモリに記憶する手段と、 レジスタを選択された初期多ビット値に初期化する手段
    と、 前記レジスタのための新たな多ビット値を、あるアルゴ
    リズムに従って繰り返し計算する手段であって、各々の
    繰り返しにおいて計算される新たなレジスタ値の少なく
    とも幾つかのビットが、以前のレジスタ値の少なくとも
    幾つかのビットを前記メモリに記憶された複数の多ビッ
    ト値の１つの少なくとも幾つかのビットと組み合わせた
    結果得られたものである前記手段と、 少なくとも前記計算されたレジスタ値の一部を組み合わ
    せて、前記変数を発生する手段と、 を含む前記システム。
25. 【請求項２５】請求項24のシステムにおいて、前記メモ
    リが参照テーブルを含む、前記システム。
26. 【請求項２６】請求項25のシステムにおいて、 前記レジスタが複数の８ビットレジスタを含み、 前記参照テーブルが256の値を含む、 前記システム。
27. 【請求項２７】請求項24のシステムにおいて、前記メモ
    リに記憶された複数の多ビット値の少なくとも幾つか
    が、秘密データの機能を有している、前記システム。