(57)【特許請求の範囲】
【請求項１】
通信回線をそれぞれに有する２つの通信システムがバックアップ用通信回線を共用する場合において、
送信側においては、
通常時に使用する通信回線が故障したことを検知したいずれか１の通信システムは転送すべきデータを自己の暗号鍵で暗号化し、
他方の通信システムは固定値データを自己の暗号鍵で暗号化し、
前記暗号化された２つのデータを、一方を平文、他方を暗号鍵として暗号化してバックアップ用通信回線に出力し、
受信側においては、
通信回線が故障したことを検知した当該通信システムは他方の通信システムの暗号鍵を入手して、バックアップ用通信回線から得た暗号化されたデータを自己の通信システムの暗号鍵及び入手した他方の通信システムの暗号鍵により復号化することを特徴とした
バックアップ用通信回線共用システム。
【請求項２】
暗号化および復号化が排他的論理和演算であることを特徴とする請求項１記載のバックアップ用通信回線共用システム。
【請求項３】
バックアップ用通信回線がいずれか一方の通信システムに組み込まれたことを特徴とする請求項１または請求項２記載のバックアップ用通信回線共用システム。
【請求項４】
データを送受信するための第一の送信手段および第一の受信手段と、第一の送信手段から第一の受信手段にデータを伝送する第一の通信回線および第一の通信回線に障害が発生したときに第一の通信回線に代わってデータを伝送するバックアップ用通信回線から構成される第一の通信システムと、
データを送受信するための第二の送信手段および第二の受信手段と、第二の送信手段から第二の受信手段にデータを伝送する第二の通信回線とから構成される第二の通信システムと、
第二の送信手段から第一の送信手段にデータを伝送する第三の通信回線と、
第一の受信手段から第二の受信手段にデータを伝送する第四の通信回線と、
第一の受信手段と第二の受信手段との間で暗号鍵データ及び回線障害情報を伝送する第五の通信回線と、
から構成される通信システムにおいて、
第一の送信手段は、
第一の通信回線が正常に機能する場合に入力データを第一の通信回線に出力し、第一の通信回線に障害が発生した場合は下記第一の暗号化手段に出力する第一の通信経路切替手段と、
第一の乱数を生成する第一の乱数生成手段と、
前記第一の乱数により、第一の通信経路切替手段の出力信号を暗号化する第一の暗号化手段と、
第一の暗号化手段の出力を下記第三の暗号化手段出力により暗号化し、又は下記第三の暗号化手段出力を第一の暗号化手段出力により暗号化し、バックアップ用通信回線に出力する第二の暗号化手段と、
から構成され、
第一の受信手段は、
第一の通信回線が正常に機能する場合に第一の通信回線から信号を取り込み第一の通信システムの外部に出力し、第一の通信回線に障害が発生した場合は下記第二の復号化手段から信号を取り込み第一の通信システムの外部に出力する第二の通信経路切替手段と、
第一の通信回線の回線障害を検出する第一の回線障害検出手段と、
前記第一の乱数と同一でかつ同期した第二の乱数を生成する第二の乱数生成手段と、
バックアップ用通信回線から得たデータを前記第二の乱数により復号化する第一の復号化手段と、
下記第一の復号化手段出力を下記第一の暗号鍵交換手段の出力信号により復号化する第二の復号化手段と、
前記第二の乱数と前記第一の回線障害検出手段出力と下記第二の暗号鍵交換手段から第五の通信回線を通じて得た情報を入力し、かつ、第一の通信回線が正常に機能する場合に第二の復号化手段に固定値データを出力し、第一の通信回線に障害が発生した場合に第二の復号化手段に下記第五の乱数を出力し、さらに、前記第二の乱数と前記第一の回線障害検出手段出力を第五の通信回線を通じて第二の暗号鍵交換手段に出力する第一の暗号鍵交換手段と、
から構成され、
第二の送信手段は、
第二の通信回線が正常に機能する場合に入力データを第二の通信回線に出力し、第二の通信回線に障害が発生した場合は下記第三の暗号化手段に出力する第三の通信経路切替手段と、
第四の乱数を生成する第四の乱数生成手段と、
前記第四の乱数により前記第三の通信経路切替手段出力を暗号化する第三の暗号化手段と、
から構成され、
第二の受信手段は、
第二の通信回線が正常に機能する場合に第二の通信回線から信号を取り込み第二の通信システムの外部に出力し、第二の通信回線に障害が発生した場合は第四の復号化手段から信号を取り込み第二の通信システムの外部に出力する第四の通信経路切替手段と、
第二の通信回線の回線障害を検出する第二の回線障害検出手段と、
前記第四の乱数と同一でかつ同期した第五の乱数を生成する第五の乱数生成手段と、
第四の通信回線を通じて得たバックアップ用通信回線からのデータを、前記第五の乱数により復号化する第三の復号化手段と、
前記第三の復号化手段出力を下記第二の暗号鍵交換手段出力信号により復号化し、第四の通信経路切替手段に出力する第四の復号化手段と、
前記第五の乱数と、前記第二の回線障害検出手段出力と、前記第一の暗号鍵交換手段から第五の通信回線を通じて得た情報を入力し、かつ、
第二の通信回線が正常に機能する場合に第四の復号化手段に固定値データを出力し、第二の通信回線が障害時には第四の復号化手段に前記第二の乱数を出力し、さらに、前記第五の乱数と第二の回線障害検出手段出力を、第五の通信回線を通じて第一の暗号鍵交換手段に出力する第二の暗号鍵交換手段と、
から構成されるバックアップ用通信回線共用システム。
【請求項５】
データを送受信するための第一の送信手段および第一の受信手段と、第一の送信手段から第一の受信手段にデータを伝送する第一の通信回線および第一の通信回線に障害が発生した場合に第一の通信回線に代わってデータを伝送するバックアップ用通信回線から構成される第一の通信システムと、
データを送受信するための第二の送信手段および第二の受信手段と、第二の送信手段から第二の受信手段にデータを伝送する第二の通信回線とから構成される第二の通信システムと、
第二の送信手段から第一の送信手段にデータを伝送する第三の通信回線と、
第一の受信手段から第二の受信手段にデータを伝送する第四の通信回線と、
第一の受信手段と第二の受信手段との間で暗号鍵データ及び回線障害情報を伝送する第五の通信回線と、
から構成される通信システムにおいて、
第一の送信手段は、
第一の通信回線が正常に機能する場合に入力データを第一の通信回線に出力し、第一の通信回線に障害が発生した場合は下記第一の暗号化手段に出力する第一の通信経路切替手段と、
第一の乱数を生成する第一の乱数生成手段と、
前記第一の乱数生成手段が乱数を生成する際のパラメータである第一の暗号鍵を生成する第一の鍵生成手段と、
前記第一の乱数により第一の通信経路切替手段出力を暗号化する第一の暗号化手段と、
第一の暗号化手段出力を下記第三の暗号化手段出力により暗号化し、又は下記第三の暗号化手段出力を第一の暗号化手段出力により暗号化し、バックアップ用通信回線に出力する第二の暗号化手段と、
から構成され、
第一の受信手段は、
第一の通信回線が正常に機能する場合に第一の通信回線から信号を取り込み第一の通信システムの外部に出力し、第一の通信回線に障害が発生した場合は下記第二の復号化手段から信号を取り込み第一の通信システムの外部に出力する第二の通信経路切替手段と、
第一の通信回線の回線障害を検出する第一の回線障害検出手段と、
第一の乱数生成手段が生成する第一の乱数と同一で、かつ同期した第二の乱数を生成する第二の乱数生成手段と、
第二の乱数生成手段が乱数を生成する際のパラメータである第二の暗号鍵を生成する鍵生成器であって、前記第一の鍵生成手段と同一でかつ同期した暗号鍵を生成する第二の鍵生成手段と、
乱数を生成する際のパラメータが下記第四の暗号鍵である場合に下記第四の乱数と同一でかつ同期した第三の乱数を生成する第三の乱数生成手段と、
バックアップ用通信回線から得たデータを、前記第二の乱数により復号化する第一の復号化手段と、
前記第三の乱数により第一の復号化手段出力を復号化し、第二の通信経路切替手段に出力する第二の復号化手段と、
前記第二の暗号鍵と、前記第一の回線障害検出手段出力と、下記第二の暗号鍵交換手段から第五の通信回線を通じて得た情報を入力し、かつ、
第一の通信回線が正常に機能する場合に固定値データを出力し、第一の通信回線に障害が発生した場合に乱数を生成する際のパラメータとして下記第四の暗号鍵を第三の乱数生成手段に出力し、さらに前記第二の暗号鍵と第一の回線障害検出手段出力を第五の通信回線を通じて第二の暗号鍵交換手段に出力する第一の暗号鍵交換手段と、
から構成され、
第二の送信手段は、
第二の通信回線が正常に機能する場合に入力データを第二の通信回線に出力し、第二の通信回線に障害が発生した場合は下記第三の暗号化手段に出力する、第三の通信経路切替手段と、
第三の暗号鍵を生成する第三の暗号鍵生成手段と、
前記第三の暗号鍵をパラメータとして第四の乱数を生成する第四の乱数生成手段と、
前記第四の乱数により第三の通信経路切替手段出力を暗号化し第三の通信回線に出力する第三の暗号化手段と、
から構成され、
第二の受信手段は、
第二の通信回線が正常に機能する場合に第二の通信回線から信号を取り込み第二の通信システムの外部に出力し、第二の通信回線に障害が発生した場合は下記第四の復号化手段から信号を取り込み第二の通信システムの外部に出力する第四の通信経路切替手段と、
第二の通信回線の回線障害を検出する第二の回線障害検出手段と、
前記第四の乱数と同一でかつ同期した第五の乱数を生成する第五の乱数生成手段と、
第五の乱数生成手段が乱数を生成する際のパラメータである第四の暗号鍵を生成する鍵生成器であって、第三の鍵生成手段と同期して同一の暗号鍵を生成する第四の鍵生成手段と、
乱数を生成する際のパラメータが前記第二の暗号鍵である場合に、前記第一の乱数と同一でかつ同期した第六の乱数を生成する第六の乱数生成手段と、
第四の通信回線を通じて得たバックアップ用通信回線からのデータを、前記第五の乱数により復号化する第三の復号化手段と、
前記第六の乱数により、第三の復号化手段出力を復号化し、第四の通信経路切替手段に出力する第四の復号化手段と、
前記第四の暗号鍵と、前記第二の回線障害検出手段出力と、前記第一の暗号鍵交換手段から第五の通信回線を通じて得た情報を入力し、かつ、
第二の通信回線が正常時には固定値データを出力し、第二の通信回線に障害が発生した場合に乱数を生成する際のパラメータとして前記第二の暗号鍵を第六の乱数生成手段に出力し、さらに第四の暗号鍵と第二の回線障害検出手段出力を第五の通信回線を通じて第一の暗号鍵交換手段に出力する第二の暗号鍵交換手段と、
から構成されるバックアップ用通信回線共用システム。
【請求項６】
暗号化手段および復号化手段が排他的論理和演算であることを特徴とする請求項４または請求項５記載のバックアップ用通信回線共用システム。
【請求項７】
暗号鍵及び回線障害情報の交換にＳｅｃｕｒｅ  Ｍｕｌｔｉｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ（ＳＭＣ）プロトコルを用いたことを特徴とする請求項１、請求項２、請求項３、請求項４、請求項５または請求項６記載のバックアップ用通信回線共用システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、相手方に通信の有無を知られずに回線を共有することができる通信システムに関するものである。
【背景技術】
【０００２】
通信事業者が遠隔の２地点間で通信サービスを提供する場合、通信回線の障害に備えてバックアップ用通信回線をあらかじめ用意し、信頼性を高めておくことは通常行われている。しかし、例えば、１回線で大容量通信サービスを提供する場合には同一の容量を有する通信回線を用意する必要があり、確率が極めて低い回線障害のためにバックアップ用通信回線に対して大きなコストを支払わなければならないという問題がある（回線数増加の問題）。
【０００３】
そこで、複数の通信事業者が２地点間で１本のバックアップ用通信回線を共用するという方法が考えられる。例えば、二つの通信事業者Ａ、Ｂが同一地域でサービスを提供している場合、通信事業者Ａがバックアップ用通信回線を用意し、通信事業者Ｂが必要時（事業者Ｂの回線が障害を起こしている場合）に通信事業者Ａのバックアップ用通信回線に通信トラフィックを中継してもらうことが考えられる。このとき、通信事業者Ａのバックアップ用通信回線のコストを各通信事業者が分担して負担すれば、バックアップ用通信回線にかかるコストを低減することが可能となる。このようなバックアップ方法は、通信事業者Ａ、Ｂの主回線が同時に障害を起こす確率は極めて小さく、現実的には無視でき、各地点において通信事業者Ａ、Ｂの通信装置を結ぶ回線は主回線と比較して極めて短くそのコストは相対的に無視できる場合に有効となる。
【０００４】
しかし、上記従来技術には通信事業者Ａが通信事業者Ｂの回線品質情報を入手できるという問題がある。バックアップ用通信回線は通信事業者Ａが提供するものであるから、事業者Bの主回線において、いつ・どの程度の期間に渡って障害が発生したかという詳細な回線品質の情報が、事業者Aに分かってしまう（バックアップ使用状況開示の問題）。通信設備の障害の頻度は通信サービス品質に直結することから、このような情報は通信事業者間の競争を左右する有用情報であり、これを競合相手である他の通信事業者に開示することは望ましくない。このため、バックアップ用通信回線を共用しながら、回線を保有している他の通信事業者に通信の有無を知られずにバックアップ用通信回線を使用する技術が必要となる。
【０００５】
従来、他者に通信の内容、あるいは通信の有無を知られずに通信データを相手方に伝送する技術として暗号技術が用いられている。基本的な暗号技術として対称暗号方式がある。対称暗号方式は、送信者と受信者があらかじめ鍵（共有鍵）を共有し、送信者が送信データを共有鍵により暗号化し、同じ共有鍵により受信者が復号化することにより第三者に通信の内容を秘匿する方式である。代表的な例として、ＤＥＳ、ＲＣ４、ＡＥＳ等を挙げることができる。
【０００６】
複数の者が互いに通信をすることで、各人の与える入力及び各人の受け取る出力を秘匿したまま任意の関数ｆを計算する方法としてＳｅｃｕｒｅ  Ｍｕｌｔｉｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ（ＳＭＣ）プロトコルが知られている（例えば、非特許文献１、非特許文献２参照）。例えば、Ａ、Ｂの二人が、２入力・２出力関数（Ｙａ，Ｙｂ）＝ｆ（Ｘａ，Ｘｂ）を計算する問題を考える。Ａは入力Ｘａを与え出力Ｙａを受け取り、Ｂは入力Ｘｂを与え出力Ｙｂを受け取るものとする。ＳＭＣプロトコルを用いると、この関数ｆを、それ以外の情報は各人に開示せずに（すなわち、AはＸｂ、Ｙｂを知ることなく、ＢはＸａ、Ｙａを知ることなく）計算することができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｇｏｌｄｒｅｉｃｈ，  Ｏ．Ｆｏｕｎｄａｔｉｏｎ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ，  ｖｏｌｕｍｅ  ２，  ＢａｓｉｃＡｐｐｌｉｃａｔｉｏｎｓ，  Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｃｉｔｙ  Ｐｒｅｓｓ，  ２００４．
【非特許文献２】Ｇｏｌｄｒｅｉｃｈ，  Ｏ．，Ｍｉｃａｌｉ，  Ｓ．，  ａｎｄ  Ｗｉｇｄｅｒｓｏｎ，  Ａ．  Ｈｏｗ  ｔｏ  ｐｌａｙ  ａｎｙｍｅｎｔａｌ  ｇａｍｅ．  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ｎｉｎｅｔｅｅｎｔｈ  ａｎｎｕａｌ  ＡＣＭｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  ｏｆ  ｃｏｍｐｕｔｉｎｇ（１９８７），  ＡＣＭ，  ｐｐ．２１８−２２９．
【非特許文献３】岡本龍明, 山本博資、「現代暗号」、ｐ．２２７−２３６、産業図書（１９９７／０７）
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は、異なる２の通信システムが１つのバックアップ用通信回線を共有することによりコスト低減を図り、さらに１の通信システムが当該バックアップ用通信回線を使用していることを当該他の通信システムが知ることができないバックアップ用通信回線共用システムを提供する。
【課題を解決するための手段】
【０００９】
本発明では、通信回線をそれぞれに有する異なる２つの通信システムが１本の他の通信回線をバックアップ用通信回線として共用する場合に１の通信システムがバックアップ用通信回線を使用したことを当該他の通信システムが知ることができないようにするために、通常時に使用する通信回線が故障したことを検知したいずれか１の通信システムの送信側では転送すべきデータを暗号化し、他方の通信システムは転送すべきデータとして固定値データを暗号化し、該暗号化された前記二つのデータを、一方を平文、他方を暗号鍵として暗号化してバックアップ用通信回線に出力し、通常時に使用する通信回線が故障したことを検知した通信システムの受信側では他方の通信システムの暗号鍵を入手して、バックアップ用通信回線から得た暗号化されたデータを自己の通信システムの暗号鍵及び入手した他方の通信システムの暗号鍵により復号して転送すべきデータを得ている。
【００１０】
さらに、前記の構成において、通信回線の故障を検知した通信システムの受信側で他の通信システムの暗号鍵を入手する際、Ｓｅｃｕｒｅ  Ｍｕｌｔｉｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ（ＳＭＣ）プロトコルを用いることにより他の通信システムの暗号鍵を入手することで、暗号鍵を入手したことを当該他の通信システムに知られないことを確実にすることができる。
【００１１】
また、暗号鍵を生成する乱数生成部を、送信情報より少ないビット列である秘密鍵生成部と、生成された秘密鍵をパラメータとして送信情報と同じ長さの乱数を生成する乱数生成部とから構成することで、通信システム間で受け渡す暗号鍵の長さを短縮することができ、ＳＭＣプロトコルによる遅延を小さくすることができる。
【発明の効果】
【００１２】
本発明を用いれば、２つの通信システムがバックアップ用通信回線を共用する場合に、バックアップ用通信回線に流れている信号は常に自システムの暗号鍵により暗号化されているため、バックアップ用通信回線を使用していない通信システムは、バックアップ用通信回線に流れている信号に他の通信システムの伝送情報が含まれているか否かは分からない。そのため、バックアップ使用状況開示の問題を解決しながらバックアップ用通信回線を共有することで回線数増加の問題をも解決することが可能となる。
【図面の簡単な説明】
【００１３】
【図１】本発明を説明する第一のシステム構成例である。
【図２】本発明の暗号化部の構成例である。
【図３】本発明の復号化部の構成例である。
【図４】暗号化器、復号化器を排他的論理和とした例である。
【図５】暗号鍵交換部の入出力信号の説明図である。
【図６】暗号鍵交換部の論理動作の説明図である。
【図７】暗号鍵交換部の構成例である。
【図８】入力信号の分割方法の一例である。
【図９】図８に示す分割方法のフロー（手順１）図である。
【図１０】ＮＯＴ演算処理フロー（手順２）図である。
【図１１】ＡＮＤ演算処理フロー（手順３）図である。
【図１２】出力処理フロー（手順４）図である。
【図１３】ＳＭＣプロトコルを実現する暗号鍵交換部の構成例である。
【図１４】バックアップ用通信回線が通信システム１に含まれている場合の本発明による第二のシステム構成例である。
【図１５】暗号化部を乱数生成器と暗号化器で構成した場合の本発明による第三のシステム構成例である。
【図１６】乱数生成器を暗号鍵で初期化する場合の本発明による第四のシステム構成例である。
【図１７】暗号鍵を初期値として乱数列を生成するＬＦＳＲの構成例を示す図である。
【図１８】暗号鍵を初期値として乱数列を生成する非線形フィードバックシフトレジスタの構成例を示す図である。
【図１９】暗号鍵を初期値として乱数列を生成する場合の動作タイミングを説明する図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施例を説明する。
【００１５】
図１に通信システム１と通信システム２が本発明によりバックアップ用通信回線を共用するバックアップ用通信回線共用システムの構成例を示す。
【００１６】
通信システムｎ（１，２）（ｎ＝１，２）は、送信装置ｎ（１１，２１）、受信装置ｎ（１２，２２）、通信回線ｎ（１３，２３）から構成されている。
【００１７】
送信装置ｎは、入力信号Ｍｎ（１４，２４）を回線障害検出部ｎ（１１１，２１２）からの信号に基づいて通信回線ｎまたは暗号化部ｎ（１１３，２１３）に出力する通信経路切替部ｎ（１１１，２１１）と、通信回線ｎの障害を検出してその結果を通信経路切替部ｎに出力する回線障害検出部ｎと、通信経路切替部ｎからの出力を暗号化する暗号化部ｎ（１１３，２１３）から構成される。
【００１８】
受信装置ｎは、通信回線ｎの回線障害を検出して通信経路切替部ｎ−１（１２１，２２１）と暗号鍵交換部ｎ（１２５，２２５）に出力する回線障害検出部ｎ−１（１２２，２２２）と、回線障害検出部ｎ−１からの信号に基づいて、通信回線ｎからの信号と、復号化部ｎ（１２３，２２３）及び復号化部ｎ−１（１２４，２２４）で処理したバックアップ用通信回線部（３）からの信号を選択する回線経路切替部ｎ−１と、バックアップ用通信回線部からの信号を入力して暗号化部ｎで暗号化した信号を復号する復号化部ｎと、復号化部ｎの出力信号を、暗号鍵交換部ｎから得た暗号鍵により復号する復号化部ｎ−１と、回線障害時に他の通信システムから暗号鍵を受け取り、暗号鍵を復号化部ｎ−１に出力する暗号鍵交換部ｎから構成される。
【００１９】
バックアップ用通信回線部は、通信システム１の暗号化部１、通信システム２の暗号化部２から暗号化された信号を入力して、一方を平文、他方を暗号鍵として暗号化する暗号化部３（３１）と、共用バックアップ用通信回線（３３）と、バックアップ用通信回線の信号を通信システム１、通信システム２に分配する分配部（３２）から構成される。
【００２０】
暗号化部ｎ（ｎ＝１，２）は、図２に示すように、乱数生成器ｎ（１１３２）と暗号化器ｎ（１１３１）により構成される。また、復号化部ｎは、図３に示すように、乱数生成器ｎ（１２３２）と復号化器ｎ（１２３１）により構成されている。暗号化部ｎの乱数生成器ｎと、復号化部ｎの乱数生成器ｎは同期して同一の乱数を生成する。同期方法は種々知られているが、例えば、送信装置と受信装置がＧＰＳ等で絶対時刻を共有して同期させる方法、絶対時刻とシステムクロックにより同期させる方法、スロット毎に同期させる方法等がある。通信システム１の乱数生成器１と通信システム２の乱数生成器２の出力乱数は、それぞれのシステムで個別に規定されるため、異なっている。また、通信システム１と通信システム２はそれぞれの乱数がお互いに知られないように保護しなければならない。
【００２１】
図２の暗号化器ｎは、入力データを乱数で暗号化（スクランブル）する。スクランブル方法の最も簡易な演算方式は、排他的論理和（ＥＸＯＲ）を用いた方法がある（図４）が、図３の復号化器ｎで同一の処理方法で復号できれば任意の演算でよい。一般的には、代数的な群を成す集合上に信号ａ、ｂがエンコードされていれば、合成はその群の演算ａ＋ｂ、分離は分離したい信号ｂの逆元−ｂとの合成演算（ａ＋ｂ）＋（−ｂ）＝ａで実現できる。
【００２２】
復号化部１−１、復号化部２−１へは、復号のための暗号鍵が暗号鍵交換部１、暗号鍵交換部２からそれぞれ入力される。復号動作については、前記復号化部と同じであるため説明は省略する。
【００２３】
暗号鍵交換部１は、通信システム１の通信回線１が故障している場合、通信システム２の暗号鍵交換部２を通じて復号化部２の乱数生成器２（図３）の乱数を取得し、復号化部１−１に引き渡す。暗号鍵交換部２は、通信システム２の通信回線２が故障している場合、通信システム１の暗号鍵交換部１を通じて復号化部１の乱数生成器１（図３）の乱数を取得し、復号化部２−１に引き渡す。
【００２４】
暗号鍵交換部１，暗号鍵交換部２の動作を以下に示す関数ｆで規定する。
【数１】
0005566322.tif 000002
Ｆｎ（ｎ＝１，２）は、回線障害検出部ｎ−１の出力信号であり、通信システムｎの通信回線ｎが故障した場合、すなわち、通信システム１がバックアップ用通信回線を使用する場合は「１」、故障していない場合は「０」である。Ｒｎは通信システムｎの復号化部ｎの乱数生成器ｎ（図３）の出力信号、出力値Ｐｎは復号化器ｎ−１へ復号鍵として出力される信号である。
【００２５】
図５に暗号鍵交換部１，暗号鍵交換部２の入出力信号を、図６に入出力動作を規定する論理値表を、図７に論理回路構成例を示す。
【００２６】
図５において、暗号鍵交換部１（１２５）にはＦ１、Ｒ１が入力され、Ｐ１が出力されている。暗号鍵交換部２（２２５）にはＦ２、Ｒ２が入力され、Ｐ２が出力されている。
【００２７】
図６において、Ｆｎ＝１の時、出力Ｐｎに相手方の暗号鍵（Ｒ１、又はＲ２）が出力されるが、Ｆｎが双方とも０又は１の場合は、暗号鍵は出力されない。ここで、Ｐｎに暗号鍵Ｒ１、Ｒ２が出力される場合以外の場合の信号値は、図６では「０」としているが、「１」でも良い。
【００２８】
図７で、ｖ１、ｖ２、ｗ１、ｗ２を出力とする論理素子（１２５１，２２５１，１２５２，２２５２）はＡＮＤゲートを表し、ｕ１、ｕ２を出力とする論理素子（１２５３，２２５３）はＮＯＴゲートを表している。
【００２９】
図１〜図７により本発明によるバックアップ用通信回線共用システムの動作を説明する。通信システム１の通信回線１と通信システム２の通信回線２の故障確率は非常に小さく、同時に故障する確率は無視できる程小さいものとする。また、各通信システムは時間を離散的に区切ったスロット単位でバックアップ用通信回線を使用する。
【００３０】
（１）通信システム１の通信回線１、通信システム２通信回線２がそれぞれ正常である場合
この場合は、通信システム１の送信装置１、通信システム２の送信装置２からバックアップ用通信回線へは入力データＭ１、Ｍ２をそれぞれ送出せず、通信経路切替部１から暗号化部１、通信経路切替部２の暗号化部２にはそれぞれ固定値データが出力される。通信システム１と通信システム２は、互いにどのような固定値データが出力されるかをあらかじめ知っている。固定値データは日時などに応じて変更しても良い。固定値データは例えば０又は１である（ここでは固定値データ「０」が出力されるものとする）。
【００３１】
図２において、暗号化部１（ｎ＝１）では乱数Ｒ１が暗号化器１に出力され、暗号化部２（ｎ＝２）では乱数Ｒ２が暗号化器２に出力される。暗号化器には、様々な方式が知られているが、ここでは図４に示すように排他的論理和（ＥＸＯＲ）を適用するものとすると、暗号化部１、暗号化部２出力は、乱数Ｒ１、乱数Ｒ２と固定値データ「０」の排他的論理和となるため、Ｒ１、Ｒ２がそのまま出力される。暗号化部１，暗号化部２出力は、バックアップ用通信回線部の暗号化部３に入力され、一方が平文、他方が暗号鍵（乱数）として暗号化（ここでは排他的論理和）される。排他的論理和演算を「＋」で表すと、暗号化部３の出力は、（Ｒ１＋Ｒ２）で表される。以下、「＋」は全て排他的論理和演算を表すものとする。
【００３２】
暗号化部３出力は、共用バックアップ用通信回線を通じて、分配部により通信システム１、通信システム２の復号化部１、復号化部２にそれぞれ入力される。復号化部１の乱数生成器１（図３）が出力する乱数、復号化部２の乱数生成器２（図３）が出力する乱数は、送信装置側の暗号化部１、暗号化部２の乱数Ｒ１、乱数Ｒ２（図２）と同一でかつ同期がとれた乱数である。このとき、通信システム１の復号化部１出力は入力信号とＲ１の排他的論理和となり、
Ｒ２＝（Ｒ１＋Ｒ２）＋Ｒ１
通信システム２の復号化部２出力は入力信号とＲ２の排他的論理和となり、
Ｒ１＝（Ｒ１＋Ｒ２）＋Ｒ２
がそれぞれ得られる。
【００３３】
復号化部１から乱数Ｒ１が暗号鍵交換部１に、復号化部２から乱数Ｒ２が暗号鍵交換部２に入力される。暗号鍵交換部１、暗号鍵交換部２は、図６に示すように、通信システム１の通信回線１、通信システム２の通信回線２に障害がない場合には、回線検出部出力Ｆ１、Ｆ２がそれぞれ「０」であるため、復号化部１−１、復号化部２−１には固定値データ（図６では固定値データ「０」）が出力される。
【００３４】
復号化部１−１は、暗号鍵交換部１からの出力値「０」と復号化部１の出力値Ｒ２との排他的論理和をとるため、Ｒ２が通信経路切替部１−１に入力される。また、復号化部２−１は、暗号鍵交換部２からの出力値「０」と復号化部２の出力値Ｒ１との排他的論理和をとるため、Ｒ１が通信経路切替部２−１に入力される。回線経路切替部１−１、回線経路切替部２−１では、通信回線１、通信回線２に障害がないため、バックアップ用通信回線からの入力信号は捨てられる。
【００３５】
通信システム１、通信システム２の受信側では、それぞれ相手側の乱数Ｒ１、Ｒ２がバックアップ用通信回線を通じて取得されるため、相手方がバックアップ用通信回線を使用しているか否かの情報は、バックアップ用通信回線からの情報からは取得することができない。
【００３６】
（２）通信システム１の通信回線１に障害があり、通信システム２の通信回線２が正常な場合
この場合は、通信システム１は、障害が発生した時点のスロットにおける入力信号Ｍ１を通信経路切替部１からバックアップ用通信回線に送出し、通信システム２の送信装置２は通信経路切替部２からバックアップ用通信回線へは入力信号Ｍ２を送出せず、固定値データを出力する。通信システム１は、通信システム２からどのような固定値データが出力されるかをあらかじめ知っている。固定値データは日時などに応じて変更しても良い。固定値データは例えば「０」又は「１」である（ここでは固定値データ「０」を出力するものとする）。
【００３７】
通信システム１の暗号化部１からは乱数Ｒ１と入力信号Ｍ１との排他的論理和（Ｒ１＋Ｍ１）が出力される。一方、通信システム２の暗号化部２からは、乱数Ｒ２がそのまま出力される。暗号化部１、暗号化部２出力は、バックアップ用通信回線部の暗号化部３に入力され、一方が平文、他方が暗号鍵（乱数）として暗号化（ここでは排他的論理和）されて（Ｒ１＋Ｒ２＋Ｍ１）となる。
【００３８】
暗号化部３出力は、共用バックアップ用通信回線を通じて分配部から復号化部１、復号化部２にそれぞれ入力される。復号化部１、復号化部２は、入力信号（Ｒ１＋Ｒ２＋Ｍ１）を復号化する。復号化部１出力は、入力信号とＲ１の排他的論理和であるから、
Ｒ２＋Ｍ１＝（Ｒ１＋Ｒ２＋Ｍ１）＋Ｒ１
となり、復号化部２出力は、
Ｒ１＋Ｍ１＝（Ｒ１＋Ｒ２＋Ｍ１）＋Ｒ２
となる。
【００３９】
暗号鍵交換部１には復号化部１から乱数Ｒ１が入力され、暗号鍵交換部２には復号化部２から乱数Ｒ２が入力される。暗号鍵交換部１は、図６に示すように、通信システム１の通信回線１に障害があり、通信システム２の通信回線２に障害がない場合には、回線障害検出部１出力Ｆ１は「１」、回線障害検出部２出力Ｆ２は「０」となるため、暗号鍵交換部１から復号化部１−１への出力は「Ｒ２」、暗号鍵交換部２から復号化部２−１への出力は固定値データ「０」となる。
【００４０】
復号化部１−１の入力は乱数Ｒ２と（Ｒ２＋Ｍ１）であるから、排他的論理和をとることにより、Ｍ１が得られる。復号化部２−１の入力は固定値データ「０」と（Ｒ１＋Ｍ１）であるから、排他的論理和をとることにより出力（Ｒ１＋Ｍ１）が得られる。
【００４１】
通信システム１の回線経路切替部１−１では通信回線１に障害があるため、復号化部１−１の出力Ｍ１が選択され、通信システム２の回線経路切替部２−１ではバックアップ用通信回線からの入力信号（Ｒ１＋Ｍ１）は捨てられる。
【００４２】
通信システム２の受信装置２では、（Ｒ１＋Ｍ１）が乱数であるため、通信システム１がバックアップ用通信回線を使用しているか否かの情報は、バックアップ用通信回線からの情報からは取得することができない。
【００４３】
（３）通信システム２の通信回線２に障害があり、通信システム１の通信回線１が正常である場合
この場合は、上記（２）の動作で通信システム１と通信システム２を入れ替えたものであるため詳細な説明は省略するが、通信システム２の送信装置２の入力データＭ２は暗号化されて（Ｒ１＋Ｒ２＋Ｍ２）となりバックアップ用通信回線に入力される。通信システム１の受信装置２の復号化部１−１出力は、（Ｒ１＋Ｍ２）、通信システム２の受信装置２の復号化部２−１出力はＭ２となる。通信システム１の受信装置１の通信経路切替部１−１は通信回線１からの信号を出力し、バックアップ用通信回線からの信号（Ｒ１＋Ｍ２）は捨てられる。通信システム２の受信装置２の通信経路切替部２−１はバックアップ用通信回線からの信号Ｍ２を出力する。この場合も、通信システム１は、バックアップ用通信回線から得られる信号が乱数（Ｒ１＋Ｍ２）であるため、通信システム２がバックアップ用通信回線を使用しているか否かの情報は、バックアップ用通信回線からの情報からは取得することができない。
【００４４】
次に、図５〜図７で例示した暗号鍵交換部について検討する。図７で示した論理回路からわかるように、通信システム１の暗号鍵交換部１は、通信システム２の暗号鍵交換部２からＦ２、Ｒ２の情報を受け取り、通信システム２の暗号鍵交換部２は、通信システム１の暗号鍵交換部１からＦ１、Ｒ１を受け取るため、通信システム１はＦ２から通信システム２の障害情報を、Ｒ２から通信システム２の乱数情報を得ることができる。このため、通信システム１、又は通信システム２の管理者が悪意でこれらの情報を取得し、利用することが可能である。そこで、暗号鍵交換部にＳｅｃｕｒｅ  Ｍｕｌｔｉｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ（ＳＭＣ）プロトコルを適用する。これにより、相手側システムの情報の取得を不可能にすることができる。
【００４５】
ＳＭＣプロトコルの詳細は非特許文献３に記載されている。これによると、通信システム１，通信システム２が互いの入出力を秘匿したまま関数
（Ｙ１，Ｙ２）＝ｆ（Ｘ１，Ｘ２）
を計算する手順は以下の通りである。最初に入力信号を手順１による分割処理を、次に関数ｆを表す論理回路中の各論理ゲートについて、ＮＯＴ演算に対して手順２を、ＡＮＤ演算に対して手順３を、全論理ゲートについて手順２、手順３を実行した後に出力値を得るための手順４を実行する。なお、全ての論理回路はＮＯＴゲートとＡＮＤゲートに変換できるため、ＮＯＴとＡＮＤが計算できれば任意の論理回路について計算できる。
【００４６】
（手順１）図８、図９に入力信号の分割処理回路及び処理フローを示す。
各通信システムの暗号鍵交換部は、各通信システムの入力Ｘｎの各ビットｘを、ｘ＝ｘ１＋ｘ２（＋はビットの排他的論理和）を満たす二つのビットに分割し、ｘ１は自身が保持し、ｘ２を他方の通信システムの暗号鍵交換部に送る。図８に、ｘ１、ｘ２を以下の演算によって求めた場合の実施例を示す。
ｘ１＝ｘ＋ｓ０１、ｘ２＝ｓ０１
ここで、ｓ０１は任意の乱数列Ｓ０１の各ビットを表している。
【００４７】
図９は図８の演算処理フローである。
【００４８】
（１）  乱数生成器から任意の乱数ｓ０１を取得する（Ｓ６０１）
【００４９】
（２）  ｘ１＝ｘ＋ｓ０１を算出し自身で保持する（Ｓ６０２）。
【００５０】
（３）ｘ２＝ｓ０１を他の暗号鍵交換部に送る（Ｓ６０３、Ｓ６０４）。
【００５１】
（手順２）図１０にＮＯＴ演算の処理フローを示す。
入力ビットｐ（＝ｐ１＋ｐ２）, 出力ビットｒ＝¬ｐ（＝ｒ１＋ｒ２）であるＮＯＴゲートに対しては、以下の手順によりｐ１＋ｐ２＝¬（ｒ１＋ｒ２）となるｒ１を暗号鍵交換部１が、ｒ２を暗号鍵交換部２が得る。
【００５２】
（１）暗号鍵交換部１はｐ１を持っている（Ｓ７０１）ので、ｒ１＝¬ｐ１とする（Ｓ７０２）。
【００５３】
（２）暗号鍵交換部２はｐ２を持っているの（Ｓ７０３）で、ｒ２=ｐ２とする（Ｓ７０４）。
【００５４】
（手順３）図１１に処理フローを示す。
入力ビットｐ（＝ｐ１＋ｐ２）、ｑ（＝ｑ１＋ｑ２）、出力ビットｒ=ｐ∧ｑ（＝ｒ１＋ｒ２）であるＡＮＤゲートに対しては、以下の手順によりｒ１＋ｒ２=（ｐ１＋ｐ２）∧（ｑ１＋ｑ２）となるｒ１、ｒ２を暗号鍵交換部１、暗号鍵交換部２が得る。
【００５５】
（１）  暗号鍵交換部１はｐ１、ｑ１を持っている（Ｓ８０１）。
【００５６】
（２）ランダムなビットｓ１を生成し（Ｓ８０２）、ｒ１=（ｐ１∧ｑ１）＋ｓ１とする（Ｓ８０３）。
【００５７】
（３）暗号鍵交換部１は４つの公開鍵秘密鍵ペアを生成し、そのうち４つの公開鍵ｋｉｊ（ｋ００，ｋ０１，ｋ１０，ｋ１１）を暗号鍵交換部２に送る（Ｓ８０４）。
【００５８】
（４）暗号鍵交換部２はｐ２、ｑ２を持っている（Ｓ８０７）。
【００５９】
（５）暗号鍵交換部２は１つの公開鍵秘密鍵ペアを生成し（Ｓ８０８）、その公開鍵ｋ’を暗号鍵交換部１から受け取った公開鍵のうちの一つで暗号化し、暗号鍵交換部１に送る（Ｓ８１０）。ｋ’を
【数２】
0005566322.tif 000003
で暗号化した信号を、
【数３】
0005566322.tif 000004
と表記する。
【００６０】
（６）暗号鍵交換部１は受け取った上記（数式３）を自身の４つの秘密鍵で復号化し（Ｓ８０５）、それぞれ鍵ｋ’ｉｊ（ｋ’００，ｋ’０１，ｋ’１０，ｋ’１１）とする（そのうち一つは正しく暗号鍵交換部２の公開鍵ｋ’に復号化され、残りの三つは鍵がマッチしていないため無意味な乱数に復号されるが、暗号鍵交換部１にはどれがｋ’か分からない）。暗号鍵交換部１は４つのｕ（ｉ，ｊ）= ｓ１＋（ｐ１∧ｉ）＋（ｑ１∧ｊ） （ただし、ｉ，ｊ∈｛０，１｝）をそれぞれｋ’ｉｊで暗号化した４つの暗号文を暗号鍵交換部２に送る（Ｓ８０６）。
【００６１】
（７）暗号鍵交換部２はｕ（ｉ，ｊ）を自身の秘密鍵で復号し（Ｓ８１１）、ｒ２＝（ｐ２∧ｑ２）＋ｕ（ｐ２，ｑ２）とする（Ｓ８１２）。
【００６２】
（手順４）図１２に処理フローを示す。
全ての論理ゲートに対して上記手順１〜手順３を実行した後、暗号鍵交換部ｎ（ｎ＝１，２）は以下の手順により出力Ｙｎを得る。
【００６３】
（１）  論理回路の出力全体Ｙ=（Ｙ１，Ｙ２）の各ビットを、ｋ、ｌを出力数として、
Ｙ１出力を
【数４】
0005566322.tif 000005
Ｙ２出力を
【数５】
0005566322.tif 000006
とし、通信システムｎの暗号鍵交換部ｎがＹ１出力、Ｙ２出力についてそれぞれ、
【数６】
0005566322.tif 000007
を保有しているものとすれば、
【数７】
0005566322.tif 000008
が成り立っている。
【００６４】
（２）暗号鍵交換部ｎは他通信システムの暗号鍵交換部の得るべき出力Ｙｎの各ビット
【数８】
0005566322.tif 000009
について、自分の持つ
【数９】
0005566322.tif 000010
を他通信システムの暗号鍵交換部に送る（Ｓ９０１，Ｓ９０４）。
【００６５】
暗号鍵交換部１は自身の得るべき出力Ｙ１の各ビット
【数１０】
0005566322.tif 000011
について、自身が持っている
【数１１】
0005566322.tif 000012
をロードし（Ｓ９０２）、暗号鍵交換部２から受け取った
【数１２】
0005566322.tif 000013
により、
【数１３】
0005566322.tif 000014
を復元する（Ｓ９０３）。暗号鍵交換部２は自身の得るべき出力Ｙ２の各ビット
【数１４】
0005566322.tif 000015
について、自身が持っている
【数１５】
0005566322.tif 000016
をロードし（Ｓ９０５）、暗号鍵交換部１から受け取った
【数１６】
0005566322.tif 000017
により、
【数１７】
0005566322.tif 000018
を復元する（Ｓ９０６）。
【００６６】
図１３にＳＭＣプロトコルを実現する暗号鍵交換部の実施例を示す。暗号鍵交換部は、入力信号Ｆｎ、Ｒｎ（ｎ＝１，２）とのインターフェースである入力Ｉ／Ｆ部（１２５００）と、外部へ信号Ｐｎを出力する出力Ｉ／Ｆ部（１２５０１）と、通信システム１と通信システム２の暗号鍵交換部との間でデータのやり取りをする暗号鍵交換部Ｉ／Ｆ部（１２５０２）と、暗号鍵（公開鍵、秘密鍵）、乱数を生成する暗号鍵乱数生成部（１２５０３）と、外部から取得した、又は前記暗号鍵乱数生成部から取得した暗号・復号鍵により暗号化・復号化を行う暗号化復号化部（１２５０４）と、ＳＭＣプロトコルのプログラムを記憶し、情報を一時的に又は永久的に記憶するメモリ（１２５０５）と、メモリからプログラムを読み出し、入力されたデータに基づいて各部を制御し、所定の動作を行う制御部（１２５０６）と、それら各部間でデータのやり取りをするバスライン（１２５０７）から構成される。
【００６７】
図１３の暗号鍵交換部の動作を図７の論理回路に適用した場合について説明する。
【００６８】
（１）入力信号の分割処理（手順１）
入力信号Ｆ１、Ｒ１、Ｆ２、Ｒ２のビットｆ１，ｒ１，ｆ２，ｒ２を図９により分割して得られる１組のデータ、
Ｆ１：（ｆ１１，ｆ１２），ｆ１＝ｆ１１＋ｆ１２
Ｒ１：（ｒ１１，ｒ１２），ｒ１＝ｒ１１＋ｒ１２
Ｆ２：（ｆ２１，ｆ２２），ｆ２＝ｆ２１＋ｆ２２
Ｒ２：（ｒ２１，ｒ２２），ｒ２＝ｒ２１＋ｒ２２
の各要素は、次式で表される。
ｆ１１＝ｆ１＋ｓ１１、ｆ１２＝ｓ１１、ｒ１１＝ｒ１＋ｓ１２、ｒ１２＝ｓ１２
ｆ２２＝ｆ２＋ｓ２１、ｆ２１＝ｓ２１、ｒ２２＝ｒ２＋ｓ２２、ｒ２１＝ｓ２２
ここで、ｓ１１、ｓ１２、ｓ２１、ｓ２２は任意の乱数である。
【００６９】
上記演算は図１３に示す回路では、次のように行われる。最初に、暗号鍵交換部１の制御部が入力Ｉ／Ｆ部から入力データｆ１、ｒ１を取得し、暗号鍵乱数生成部から乱数ｓ１１、ｓ１２を取得する。その後、制御部はｆ１、ｒ１とｓ１１、ｓ１２の排他的論理和演算をそれぞれとることでｆ１１、ｒ１１を算出し、メモリにストアする。また、ｓ１１をｆ１２、ｓ１２をｒ１２として、暗号鍵交換部Ｉ／Ｆに送る。暗号鍵交換部２の暗号鍵交換部Ｉ／Ｆは、入力信号があった旨を制御部に伝え、暗号鍵交換部２の制御部はｆ１２、ｒ１２をメモリにストアする。
同様にｆ２１，ｒ２１は暗号鍵交換部２から暗号鍵交換部１に送られ、暗号鍵交換部１の制御部がｆ２１，ｒ２１をメモリにストアする。
【００７０】
（２）ＮＯＴゲート（図７の１２５３、２２５３）の処理（手順２）
信号Ｆ１は、暗号鍵交換部１ではｆ１１が、暗号鍵交換部２ではｆ１２が、ＮＯＴゲート１２５３に入力されるから、手順２を適用すると、
ＮＯＴゲート１２５３の演算結果：ｕ１１＝¬ｆ１１（暗号鍵交換部１）、ｕ１２＝ｆ１２（暗号鍵交換部２）
が得られる。同様に、
ＮＯＴゲート２２５３の演算結果：ｕ２１＝ｆ２１（暗号鍵交換部１）、ｕ２２＝¬ｆ２２（暗号鍵交換部２）
が得られる。ここに、ｕ１＝ｕ１１＋ｕ１２、ｕ２＝ｕ２１＋ｕ２２である。
【００７１】
上記演算は図１３に示す回路では次のように行われる。
暗号鍵交換部１の制御部は、信号Ｆ１がＮＯＴゲートに入力されることから、ＮＯＴゲート１２５３の演算として手順２を実行する。手順２では、入力データｆ１１は暗号鍵交換部１の入力であるから、制御部はメモりから読み出しＮＯＴ処理を行い、
ｕ１１＝¬ｆ１１
をメモリにストアする。
【００７２】
暗号鍵交換部１の制御部はさらに、信号Ｆ２がＮＯＴゲート２２５３に入力されることから、ＮＯＴゲート２２５３の演算として手順２を実行し、入力データｆ２１は暗号鍵交換部２から送られてきた入力としてメモりから読み出し、
ｕ２１＝ｆ２１
をメモリにストアする。
【００７３】
暗号鍵交換部２の制御部についても同様に、
ｕ１２＝ｆ１２
ｕ２２＝¬ｆ２２
をメモリにストアする。
【００７４】
（３）ＡＮＤゲート１２５１の処理（手順３）
暗号鍵交換部１の制御部は、ＡＮＤゲート１２５１に対してｆ１１とｕ２１を入力とし、暗号鍵交換部２の制御部は、ＡＮＤゲート１２５１に対してｆ１２とｕ２２を入力とする。
【００７５】
これにより、ＡＮＤゲート１２５１の暗号鍵交換部１側の出力ｖ１１と暗号鍵交換部２側の出力ｖ１２は、
ｖ１＝ｖ１１＋ｖ１２
ｖ１１＝（ｆ１１∧ｕ２１）＋ｓ１３
ｖ１２＝（ｆ１２∧ｕ２２）＋ｕａ（ｆ１２，ｕ２２）
ここで、
ｓ１３は任意の乱数、ｕａ（ｆ１２，ｕ２２）＝ｓ１３＋（ｆ１１∧ｆ１２）＋（ｕ２１∧ｕ２２）は手順３に従って暗号鍵交換部１から暗号鍵交換部２に引き渡された値である。
【００７６】
上記演算は図１３に示す回路では、次のように行われる。暗号鍵交換部１の制御部は、信号Ｆ１とＮＯＴゲート２２５３出力がＡＮＤゲート１２５１に入力されることから、ＡＮＤゲート演算として手順３（図１１）を実行する。
【００７７】
手順３では、暗号鍵交換部１の制御部は、ｆ１１とｕ２１をメモリから読み出す（Ｓ８０１）。次に、暗号鍵乱数生成部から乱数ｓ１３を取得して（Ｓ８０２）、
ｖ１１＝（ｆ１１∧ｕ２１）＋ｓ１３
を算出してメモリにストアする（Ｓ８０３）。
【００７８】
さらに、暗号鍵交換部１の制御部は暗号鍵乱数生成部から、４つの公開鍵秘密鍵ペアを取得して、当該４つの公開鍵ｋｉｊ（ｋ００，ｋ０１，ｋ１０，ｋ１１）を暗号鍵交換部Ｉ／Ｆを通じて暗号鍵交換部２の暗号鍵交換部Ｉ／Ｆに送る（Ｓ８０４）。
【００７９】
暗号鍵交換部２の制御部は、ｆ１２とｕ２２をメモリから読み出す（Ｓ８０７）。また、１組の暗号鍵秘密鍵ペア（公開鍵ｋ’）を暗号鍵乱数生成部から取得する（Ｓ８０８）。
【００８０】
暗号鍵交換部２の暗号鍵交換部Ｉ／Ｆから、暗号鍵交換部１からの信号入力があったことの通知を受けた制御部は、暗号鍵交換部Ｉ／Ｆから４つの公開鍵を取得する。取得した４つの公開鍵から、そのうちの１つの公開鍵である、
【数１８】
0005566322.tif 000019
と、前記取得したｋ’を暗号化復号化部に引き渡し、ｋ’を上記（数式１８）で表された公開鍵で暗号化する。暗号化したｋ’を次のように表記する。
【数１９】
0005566322.tif 000020
制御部は上記（数式１９）で表されたデータを暗号鍵交換部Ｉ／Ｆに送出する（Ｓ８１０）。
【００８１】
暗号鍵交換部１の暗号鍵交換部Ｉ／Ｆから、暗号鍵交換部２からの信号入力があったことの通知を受けた制御部は、上記（数式１９）を暗号鍵交換部Ｉ／Ｆから取得して暗号化復号化部に引き渡して４つの公開鍵ｋｉｊに対応する秘密鍵で復号化し、ｋ’の候補であるｋ’ｉｊ（ｋ’００，ｋ’０１，ｋ’１０，ｋ’１１）を得る（Ｓ８０５）。
【００８２】
暗号鍵交換部１の制御部は、以下のｕａ（ｉ，ｊ）とｋ’ｉｊを暗号化復号化部に引き渡して暗号化した４つのデータを暗号鍵交換部Ｉ／Ｆに引き渡し、暗号鍵交換部２に送る（Ｓ８０６）。
ｕａ（ｉ，ｊ）＝ｓ１３＋（ｆ１１∧ｉ）＋（ｕ２１∧ｊ）（ただし、ｉ，ｊ∈｛０，１｝）
【００８３】
暗号鍵交換部２の制御部は、暗号鍵交換部Ｉ／Ｆから暗号化されたｕａ（ｉ，ｊ）を得、暗号化されたｕａ（ｆ１２，ｕ２２）を暗号化復号化部に引き渡して、公開鍵ｋ’に対応する秘密鍵で復号化することにより、ｕａ（ｆ１２，ｕ２２）を得て（Ｓ８１１）、
ｖ１２＝（ｆ１２∧ｕ２２）＋ｕａ（ｆ１２，ｕ２２）
を算出しメモリにストアする（Ｓ８１２）。
【００８４】
（４）ＡＮＤゲート２２５１の処理（手順３）
同様に、ＡＮＤゲート２２５１についてもｆ２、ｕ１が算出されているため手順３（図１１）を適用し、以下の出力ｖ２１、ｖ２２を得ることができる。
ｖ２＝ｖ２１＋ｖ２２
ｖ２２＝（ｆ２２∧ｕ１２）＋ｓ２４
ｖ２１＝（ｆ２１∧ｕ１１）＋ｕｂ（ｆ２１，ｕ１１）
ここに、ｕｂ（ｆ２１，ｕ１１）＝ｓ２４＋（ｆ２２∧ｆ２１）＋（ｕ１２∧ｕ１１）
図１３の動作については、前記（３）と同様であるので、説明を省略する。
【００８５】
（５）ＡＮＤゲート１２５２の処理（手順３）
ＡＮＤゲート１２５２については、入力ｖ１：（ｖ１１，ｖ１２）、Ｒ２：（ｒ２１，ｒ２２）が得られているので、手順３を適用することにより、以下の出力を得ることができる。
ｗ１＝ｗ１１＋ｗ２１
ｗ１１＝（ｖ１１∧ｒ２１）＋ｓ１４
ｗ２１＝（ｖ１２∧ｒ２２）＋ｕｃ（ｖ１２，ｒ２２）
ここに、
ｕｃ（ｖ１２，ｒ２２）＝ｓ１４＋（ｖ１１∧ｖ１２）＋（ｒ２１∧ｒ２２）
【００８６】
上記演算を図１３に示す回路で行う場合の動作については、上記（３）と同様であるため、説明を省略する。
【００８７】
（６）ＡＮＤゲート２２５２の処理（手順３）
ＡＮＤゲート２２５２については、入力ｖ２：（ｖ２１，ｖ２２）、Ｒ１：（ｒ１１，ｒ１２）が得られているので、手順３を適用することにより、以下の出力を得ることができる。
ｗ２＝ｗ２２＋ｗ１２
ｗ２２＝（ｖ２２∧ｒ１２）＋ｓ２５
ｗ１２＝（ｖ２１∧ｒ１１）＋ｕｄ（ｖ２１，ｒ１１）
ここに、
ｕｄ（ｖ２１，ｒ１１）＝ｓ２５＋（ｖ２２∧ｖ２１）＋（ｒ１２∧ｒ１１）
【００８８】
上記演算を図１３に示す回路で行う場合の動作については、上記（３）と同様であるため、説明を省略する。
【００８９】
（７）出力処理（手順４）
図７において、出力信号Ｐ１は暗号鍵交換部１が得るべき信号、出力信号Ｐ２は暗号鍵交換部２が得るべき信号である。暗号鍵交換部１は、出力信号Ｐ１、Ｐ２にそれぞれ対応する出力データｗ１、ｗ２について、ｗ１１、ｗ１２をそれぞれ持っている。暗号鍵交換部２は、出力データｗ１、ｗ２について、ｗ２１，ｗ２２をそれぞれ持っている。これにより、各暗号鍵交換部は、次の出力を算出することができる。
Ｐ１（暗号鍵交換部１）：ｗ１＝ｗ１１＋ｗ２１
Ｐ２（暗号鍵交換部２）：ｗ２＝ｗ１２＋ｗ２２
【００９０】
上記演算は図１３に示す回路では、次のように行われる。
暗号鍵交換部１の制御部は、ｗ１２をメモリから取り出し、暗号鍵交換部Ｉ／Ｆに引き渡して、暗号鍵交換部２に送る（Ｓ９０１）。同様に、暗号鍵交換部２の制御部は、ｗ２１をメモリから取り出し、暗号鍵交換部Ｉ／Ｆに引き渡して、暗号鍵交換部１に送る（Ｓ９０４）。
【００９１】
暗号鍵交換部１の制御部は、メモリからｗ１１を（Ｓ９０２）、暗号鍵Ｉ／Ｆからｗ２１を受け取って、ｗ１＝ｗ１１＋ｗ２１を求める（Ｓ９０３）。
【００９２】
同様に、暗号鍵交換部２の制御部は、メモリからｗ２２を（Ｓ９０５）、暗号鍵Ｉ／Ｆからｗ１２を受け取って、ｗ２＝ｗ１２＋ｗ２２を求める（Ｓ９０６）。
【００９３】
図１４に共用バックアップ用通信回線が通信システム１に含まれている請求項２に記載の発明の実施例を、図１５に請求項４に記載の発明の実施例を示す。システムの動作については図１の実施例と同様であるため、説明は省略する。
【００９４】
図１６に請求項５記載の発明の実施例を示す。図１の実施例との違いは、乱数生成器の構成、および暗号鍵交換部１と暗号鍵交換部２の間で引き渡される暗号鍵のみである。図１の実施例で説明した乱数生成器は送信装置と受信装置の乱数生成器が絶対時間で同期して同一の乱数列を生成し、それぞれが自走して乱数を生成するため、回線障害発生時には暗号鍵交換部は、相手方から送信情報と同一の長さの乱数列の暗号鍵を取得しなければならない。一方、図１６の乱数生成器は回線障害が継続している間は、スロット毎に鍵生成器からの鍵情報を初期値に設定して乱数を生成する。このような構成にすることで、暗号鍵交換部で交換する暗号鍵のデータ長を短縮することができ、暗号鍵交換部の処理時間を短縮することができる。
【００９５】
鍵情報を初期パラメータとして乱数を生成する方法には、線形フィードバックシフトレジスタ（Ｌｉｎｅａｒ  ｆｅｅｄｂａｃｋ  ｓｈｉｆｔ  ｒｅｇｉｓｔｅｒ：ＬＦＳＲ）、非線形フィードバックシフトレジスタ、等が知られている。乱数生成器の具体的構成例を図１７に示す。同図において、鍵生成器（７００）はｎビットレジスタ、乱数生成器（７０１）はｎビットシフトレジスタ（７０２）と排他的論理和（ＥＸＯＲ）演算器（７０３〜７０５）から構成される。鍵生成器（７００）はスロット毎に暗号鍵を生成し、それ自体が乱数生成器であってもよい。乱数生成器７０１はＬＦＳＲであり、ｎビットシフトレジスタ（７０２）は１クロック毎にデータが右に移動する。また、一部のレジスタからタップを出し、タップ出力、シフトレジスタ（ｒｎ）または前段のＥＸＯＲ出力との排他的論理和をとる。タップ位置により乱数の周期が決まり、ｎ＝１６の場合に最長周期の乱数が得られるタップ位置は、例えば、１１、１３、１４番目のレジスタとなる。
【００９６】
図１８に非線形フィードバックシフトレジスタの構成例を示す。非線形関数演算部は非線形関数ｙ＝ｆ（ｒ１，・・・，ｒｎ）により算出したｙをシフトレジスタの第一ビット（ｒ１）に帰還する。これらの技術は周知技術であるので詳細説明は省略する。
【００９７】
図１９に、回線障害が発生した場合の、鍵生成器と乱数生成器の動作タイミングを示す。通信回線に障害が発生した場合、鍵生成器は暗号鍵Ｋ１を生成しスロット１の開始タイミング直前に乱数生成器の初期値にＫ１をセットする。乱数生成器は、次のスロットの開始タイミング（スロット１の開始タイミング）で乱数の生成をスタートさせる。次のスロットでは鍵生成器は、暗号鍵Ｋ２を生成し、スロット２の開始タイミング直前にＫ２を乱数生成器のレジスタに初期値としてセットし、スロット２の開始時点で乱数の生成を始める、その後は同一の動作をとる。
【００９８】
図１６において、通信システム１（５）の通信回線１（５５）に障害が発生した場合について説明する。
【００９９】
鍵生成器１１（５１６）と鍵生成器１２（５２７）は同一の鍵Ｋ１１を生成し、乱数生成器１１（５１４）と乱数生成器１２（５２５）は同一の鍵Ｋ１１を初期値としてスロット毎に同一の乱数列を生成する。鍵生成器２１（６１５）と鍵生成器２２（６２７）は同一の鍵Ｋ２１を生成し、乱数生成器２１（６１４）と乱数生成器２２（６２６）は同一の鍵Ｋ２１を初期値としてスロット毎に同一の乱数列を生成する。
【０１００】
暗号化器１１（５１３）、暗号化器２１（６１３）による暗号化動作、復号化器１２（５２５）、復号化器２２（６２５）による復号化動作については、図１の動作と同様であるため説明を省略する。
【０１０１】
図１、図３において、通信システム１（１）の通信回線１（１３）に障害がある場合には通信システム１がバックアップ用通信回線を使用しているため、暗号鍵交換部１（１２５）から復号化部１−１（１２４）への出力は、通信システム２（２）の復号化部２の乱数生成器２からの乱数列Ｒ２（図３）となる。一方、図１６においては、通信システム２（６）の鍵生成器２２（６２７）の出力鍵Ｋ２２は暗号鍵交換部１から乱数生成器１３に出力されて、スロット開始直前に初期値に設定され、乱数を生成して復号化器１３（５２４）に出力する。乱数列Ｒ２は伝送すべきデータと同一の長さの乱数であるが、鍵Ｋ２２は乱数を生成するための初期パラメータであるため、伝送すべきデータより遙かに短い。このため、暗号鍵交換部１、暗号鍵交換部２の処理時間を短縮することができる。
【符号の説明】
【０１０２】
１、５  通信システム１
２、６  通信システム２
３  バックアップ用通信回線部
１１、２１、５１、６１  送信装置
１２、２２、５２、６２  受信装置
１３、２３、５５、５７、５８、６５、６６  通信回線
３３、５６  バックアップ用通信回線
１４、２４、５３、６３  送信ユーザデータ
１５、２５、５４、６４  受信ユーザデータ
１１１、２１１、１２１、２２１、５１１、５２１、６１１、６２１  通信経路切替部
１１２、２１２、１２２、２２２、５１２、５２２、６１２、６２２  回線障害検出部
３１、１１３、２１３、３１１  暗号化部
１２３、１２４、２２３、２２４  復号化部
１２５、２２５、５２３、６２３  暗号鍵交換部
３２、３１２、５２７  分配部
５１３、５１５、６１３、１１３１  暗号化器
５２４、５２５、６２４、６２５、１２３１  復号化器
５１６、６１５、５２７、６２７、７００  鍵生成器
５１４、６１４、５２６、６２６、６２８、７０１、１１３２、１２３２、１００３２、１２５１１  乱数生成器
７０３、７０４、７０５、１００３１、１２５１０  排他的論理和（ＥＸＯＲ）
７０２  シフトレジスタ
７０６  非線形関数演算部
１２５３、２２５３  ＮＯＴ素子
１２５１、１２５２、２２５１、２２５２  ＡＮＤ素子
１２５００  入力インターフェース
１２５０１  出力インターフェース
１２５０２  暗号鍵交換部インターフェース
１２５０３  暗号鍵・乱数生成部
１２５０４  暗号化・復号化部
１２５０５  メモリ
１２５０６  制御部
１２５０７  共通信号伝送路（バス）
【図１】
0005566322.tif 000021
【図２】
0005566322.tif 000022
【図３】
0005566322.tif 000023
【図４】
0005566322.tif 000024
【図５】
0005566322.tif 000025
【図６】
0005566322.tif 000026
【図７】
0005566322.tif 000027
【図８】
0005566322.tif 000028
【図９】
0005566322.tif 000029
【図１０】
0005566322.tif 000030
【図１１】
0005566322.tif 000031
【図１２】
0005566322.tif 000032
【図１３】
0005566322.tif 000033
【図１４】
0005566322.tif 000034
【図１５】
0005566322.tif 000035
【図１６】
0005566322.tif 000036
【図１７】
0005566322.tif 000037
【図１８】
0005566322.tif 000038
【図１９】
0005566322.tif 000039