(57)【特許請求の範囲】
【請求項１】
通信ネットワークにおける第１及び第２の通信端末の間での認証方法であって、
前記第１の通信端末で、第１の長乱数と秘密鍵とに基づいて前記第１の長乱数より少ない桁数を有する第１の認証申込を発生する工程と、
前記第１の通信端末で、前記第１の認証申込と前記秘密鍵とに基づいて第１の応答期待値を計算する工程と、
前記第１の認証申込を前記第２の通信端末に提供する工程と、
前記第２の通信端末で、前記第１の認証申込と前記秘密鍵とに基づいて第１の応答値を計算する工程と、
を有することを特徴とする認証方法。
【請求項２】
前記第１の認証申込を発生する工程は、
前記第１の長乱数と前記秘密鍵とを暗号化アルゴリズムへの入力として供給し、その桁数が前記第１の長乱数の桁数と等しいまたはより大きい桁数を有する中間乱数を生成するする工程と、
前記中間乱数を減少させて、前記第１の長乱数の桁数より少ない桁数を有する前記第１の認証申込を生成する工程と、
を有することを特徴とする請求項１に記載の認証方法。
【請求項３】
前記中間乱数を減少させる工程は、前記中間乱数を圧縮する工程を有することを特徴とする請求項２に記載の認証方法。
【請求項４】
前記第１の応答期待値を計算する工程は、
前記第１の認証申込を伸張する工程と、
前記伸張された第１の認証申込を前記秘密鍵を使って暗号化して、修正された長乱数を生成する工程と、
前記修正された長乱数を鍵として使用し、前記秘密鍵を暗号化する工程と、
前記暗号化された秘密鍵を圧縮して、前記第１の応答期待値を生成する工程と、
を有することを特徴とする請求項３に記載の認証方法。
【請求項５】
前記第１の応答値を計算する工程は、
前記第１の認証申込を伸張する工程と、
前記伸張された第１の認証申込を前記秘密鍵を使って暗号化して、修正された長乱数を生成する工程と、
前記修正された長乱数を鍵として使用し、前記秘密鍵を暗号化する工程と、
前記暗号化された秘密鍵を圧縮して、前記第１の応答値を生成する工程と、
を有することを特徴とする請求項３に記載の認証方法。
【請求項６】
前記中間乱数を減少させる工程は、前記中間乱数から桁の部分集合を選択する工程を有することを特徴とする請求項２に記載の認証方法。
【請求項７】
前記第１の応答期待値を計算する工程は、
前記第１の認証申込を所望の桁数に増加する工程と、
前記増加した第１の認証申込を前記秘密鍵を使って暗号化して、修正された長乱数を生成する工程と、
前記修正された長乱数を鍵として使用し、前記秘密鍵を暗号化する工程と、
前記暗号化された秘密鍵から桁の部分集合を選択して、前記第１の応答期待値を生成する工程と、
を有することを特徴とする請求項６に記載の認証方法。
【請求項８】
前記第１の応答値を計算する工程は、
前記第１の認証申込を所望の桁数に増加する工程と、
前記増加した第１の認証申込を前記秘密鍵を使って暗号化して、修正された長乱数を生成する工程と、
前記修正された長乱数を鍵として使用し、前記秘密鍵を暗号化する工程と、
前記暗号化された秘密鍵から桁の部分集合を選択して、前記第１の応答値を生成する工程と、
を有することを特徴とする請求項６に記載の認証方法。
【請求項９】
前記記第１の応答期待値と前記第１の応答値との比較に基づいて、第１の認証表示信号を発生する工程を更に有することを特徴とする請求項１に記載の認証方法。
【請求項１０】
前記第１の認証表示信号を発生する工程は、
前記第１の通信端末から処理装置に前記第１の応答期待値を提供する工程と、
前記第２の通信端末から前記処理装置に前記第１の応答値を提供する工程と、
前記処理装置で、前記第１の応答期待値を前記第１の応答値と比較する工程と、
を有することを特徴とする請求項９に記載の認証方法。
【請求項１１】
前記処理装置は、前記第１の通信端末に付随することを特徴とする請求項１０に記載の認証方法。
【請求項１２】
前記処理装置は、前記通信ネットワーク内にあることを特徴とする請求項１０に記載の認証方法。
【請求項１３】
前記第１の応答期待値と前記第１の応答値とが等しい場合に、前記第１の通信端末は前記第２の通信端末のアイデンティティーを認証することを特徴とする請求項１０に記載の認証方法。
【請求項１４】
前記第２の通信端末で、第２の長乱数と前記秘密鍵とに基づいて、前記第２の長乱数よりも少ない桁数の第２の認証申込を発生する工程と、
前記第２の通信端末で、前記第２の認証申込と前記秘密鍵とに基づいて、第２の応答期待値を計算する工程と、
前記第２の認証申込を前記第１の通信端末に提供する工程と、
前記第１の通信端末で、前記第２の認証申込と前記秘密鍵とに基づいて、第２の応答値を計算する工程と、
を更に有することを特徴とする請求項１に記載の認証方法。
【請求項１５】
前記第２の認証申込を発生する工程は、
前記第２の長乱数と前記秘密鍵とを入力として暗号化アルゴリズムに供給し、その桁数が前記第２の長乱数の桁数と等しいまたはより大きい中間乱数を生成する工程と、
前記中間乱数を減少させて、前記第２の長乱数の桁数よりも少ない桁数の前記第２の認証申込を生成する工程と、
を有することを特徴とする請求項１４に記載の認証方法。
【請求項１６】
前記中間乱数を減少させる工程は、前記中間乱数を圧縮する工程を含むことを特徴とする請求項１５に記載の認証方法。
【請求項１７】
前記第２の応答期待値を算出する工程は、
前記第２の認証申込を伸張する工程と、
前記伸張された第２の認証申込を前記秘密鍵で暗号化して、修正された長乱数を生成する工程と、
前記修正された長乱数を鍵として使用し、前記秘密鍵を暗号化する工程と、
前記暗号化された秘密鍵を圧縮して前記第２の応答期待値を生成する工程と、
を有することを特徴とする請求項１６に記載の認証方法。
【請求項１８】
前記第２の期待値を算出する工程は、
前記第２の認証申込を伸張する工程と、
前記伸張された第２の認証申込を前記秘密鍵で暗号化して、修正された長乱数を生成する工程と、
前記修正された長乱数を鍵として使用し、前記秘密鍵を暗号化する工程と、
前記暗号化された秘密鍵を圧縮して前記第２の期待値を生成する工程と、
を有することを特徴とする請求項１６に記載の認証方法。
【請求項１９】
前記中間乱数を減少させる工程は、前記中間乱数から桁の部分集合を選択する工程を含むことを特徴とする請求項１５に記載の認証方法。
【請求項２０】
前記第２の応答期待値を計算する工程は、
前記第２の認証申込を所望の桁数に増加する工程と、
前記増加した第２の認証申込を前記秘密鍵を使って暗号化して、修正された長乱数を生成する工程と、
前記修正された長乱数を鍵として使用し、前記秘密鍵を暗号化する工程と、
前記暗号化された秘密鍵から桁の部分集合を選択して、前記第２の応答期待値を生成する工程と、
を有することを特徴とする請求項１９に記載の認証方法。
【請求項２１】
前記第２の応答値を計算する工程は、
前記第２の認証申込を所望の桁数に増加する工程と、
前記増加した第２の認証申込を前記秘密鍵を使って暗号化して、修正された長乱数を生成する工程と、
前記修正された長乱数を鍵として使用し、前記秘密鍵を暗号化する工程と、
前記暗号化された秘密鍵から桁の部分集合を選択して、前記第２の応答値を生成する工程と、
を有することを特徴とする請求項１９に記載の認証方法。
【請求項２２】
前記記第２の応答期待値と前記第２の応答値との比較に基づいて、第２の認証表示信号を発生する工程を更に有することを特徴とする請求項１５に記載の認証方法。
【請求項２３】
前記第２の認証表示信号を発生する工程は、
前記第２の通信端末から処理装置に前記第２の応答期待値を提供する工程と、
前記第１の通信端末から前記処理装置に前記第２の応答値を提供する工程と、
前記処理装置で、前記第２の応答期待値を前記第２の応答値と比較する工程と、
を有することを特徴とする請求項２２に記載の認証方法。
【請求項２４】
前記処理装置は、前記第２の通信端末に付随することを特徴とする請求項２３に記載の認証方法。
【請求項２５】
前記処理装置は、前記通信ネットワーク内にあることを特徴とする請求項２３に記載の認証方法。
【請求項２６】
前記第２の応答期待値と前記第２の応答値とが等しい場合に、前記第２の通信端末は前記第１の通信端末のアイデンティティーを認証することを特徴とする請求項２３に記載の認証方法。
【請求項２７】
前記第１の通信端末はネットワーク端末であり、前記第２の通信端末は加入者端末であることを特徴とする請求項１４に記載の認証方法。
【請求項２８】
前記第１の通信端末は加入者端末であり、前記第２の通信端末はネットワーク端末であることを特徴とする請求項１４に記載の認証方法。
【請求項２９】
前記第１の通信端末で、前記第１の認証申込と前記秘密鍵とに基づいて、第２の応答値を計算する工程と、
前記第２の応答値を前記第２の通信端末に送信する工程と、
前記第２の通信端末で、前記第１の認証申込と前記秘密鍵とに基づいて、第２の応答期待値を計算する工程と、
前記第２の通信端末で、前記第２の応答値を前記第２の応答期待値と比較する工程と、
を更に有することを特徴とする請求項１に記載の認証方法。
【請求項３０】
前記第２の応答値が前記第２の応答期待値と等しい場合に、前記第２の通信端末は前記第１の通信端末を認証することを特徴とする請求項２９に記載の認証方法。
【請求項３１】
前記第２の応答値が前記第２の応答期待値と等しい場合に、前記第２の通信端末は前記第１の通信端末に前記第１の応答値を提供することを特徴とする請求項３０に記載の認証方法。
【請求項３２】
前記第１の通信端末で、前記第１の応答期待値を前記第１の応答値と比較する工程を更に有することを特徴とする請求項３１に記載の認証方法。
【請求項３３】
前記第１の応答値が前記第１の応答期待値と等しい場合に、前記第１の通信端末は第２の通信端末を認証することを特徴とする請求項３２に記載の認証方法。
【請求項３４】
遠隔通信端末を認証する認証方法であって、
乱数と秘密鍵とに基づいて、前記遠隔通信端末に前記乱数よりも少ない桁数の認証申込を提供する工程と、
局所通信端末で、前記認証申込と前記秘密鍵とに基づいて応答期待値を算出する工程と、
前記遠隔通信端末で、前記認証申込と前記秘密鍵とに基づいて応答値を算出する工程と、
前記局所通信端末で、前記応答値を前記応答期待値と比較して、前記応答値が前記応答期待値と等しい場合に前記遠隔通信端末を認証する工程と、
を有することを特徴とする認証方法。
【請求項３５】
前記局所通信端末はネットワーク端末であることを特徴とする請求項３４に記載の認証方法。
【請求項３６】
前記遠隔通信端末はネットワーク端末であることを特徴とする請求項３４に記載の認証方法。
【請求項３７】
通信ネットワークにおける第１及び第２の通信端末の間での認証を行なう認証システムであって、
前記第１の通信端末が、
長乱数と秘密鍵とに基づいて前記長乱数より少ない桁数を有する認証申込を発生する手段と、
前記認証申込と前記秘密鍵とに基づいて応答期待値を計算する手段と、
前記認証申込を前記第２の通信端末に提供する手段とを有し、
前記第２の通信端末が、
前記認証申込と前記秘密鍵とに基づいて応答値を計算する手段を有することを特徴とする認証システム。
【請求項３８】
遠隔通信端末を認証する認証システムであって、
局所通信端末が、
乱数と秘密鍵とに基づいて、前記遠隔通信端末に前記乱数よりも少ない桁数の認証申込を提供する手段と、
前記認証申込と前記秘密鍵とに基づいて応答期待値を算出する手段と、
応答値を前記応答期待値と比較して、前記応答値が前記応答期待値と等しい場合に前記遠隔通信端末を認証する手段とを有し、
前記遠隔通信端末が、
前記認証申込と前記秘密鍵とに基づいて前記応答値を算出する手段を有することを特徴とする認証システム。
【発明の詳細な説明】
【０００１】
[発明の背景]
本発明は、遠隔通信、より詳細には多重アクセス遠隔通信に、更により詳細にはセルラー無線電話通信に関するものである。本発明によれば、アイデンティティー照合プロセスの副産物として提供される暗号鍵を使用して、第１パーティー及び第２パーティーが暗号化通信に携わる前に、第１パーティーが第２パーティーのアイデンティティー、ならびに第２パーティーが第１パーティーのアイデンティティーを電気的に検証することが可能になる。
【０００２】
通信セッションのセキュリティを保証するという問題は、セッションが音声、ビデオ、又は別の種類のデータを含むかどうかにかかわらず、今に始まった問題ではない。Abrahamらの米国特許第４７９９０６１号は、図１に示す通信システム中の構成要素を認証するためのシステムを記載している。第２パーティーとの通信を望む第１パーティーは、暗号化アルゴリズム１の入力として第１パーティーの秘密鍵と共に点Ａで印加される乱数を選ぶ。第１パーティーのアルゴリズム１は、秘密鍵に従って乱数を暗号化し、得られる暗号化乱数は、第１パーティーによって第２パーティーに送信される。第２パーティーは、受信した暗号化乱数を第２パーティー自身の秘密鍵と共に、暗号解読アルゴリズム２の入力として印加する。暗号解読アルゴリズム２は、第２パーティーの秘密鍵が第１パーティーの秘密鍵と同じであり、かつそれらのアルゴリズムが同じである場合にだけ、点Ａで第１パーティーによって印加された乱数を点Ｂで再現する。第２パーティーは、再現された乱数を第２パーティーの秘密鍵と共に、第２パーティーの暗号化アルゴリズム１の入力として印加する。第２パーティーのアルゴリズム１は、再現された乱数に従って第２パーティーの秘密鍵を暗号化し、得られる暗号化した第２パーティーの秘密鍵は、第２パーティーによって第１パーティーに送信される。第１パーティーは、その暗号解読アルゴリズム２の中で、第１パーティーの乱数を暗号解読鍵として使用して、受信した暗号化された第２パーティーの秘密鍵を暗号解読する。比較器３は、第１パーティーの秘密鍵及び暗号解読した第２パーティーの秘密鍵が同じかどうかを判定する。それらが同じである場合、第１パーティーは、第２パーティーを認証したことになる。すなわちこの状況の下では、どちらのパーティーも同じアルゴリズム及び鍵を使用しているということである。次いで、通信が、そのとき暗号化鍵及び暗号解読鍵としてどちらのパーティーも所有する乱数を使用して続行される。
【０００３】
Abrahamの特許中で記載されているシステムには、いくつかの欠点がある。点Ａで第１パーティーによって挿入されたのと同じ乱数を、点Ｂで第２パーティーが再現できるためには、ＡからＢへの送信が「情報可逆（information lossless）」でなければならない。情報可逆送信に伴う必然的結果の１つが、第１パーティーから第２パーティーに送信される暗号化乱数の桁数を、乱数の桁数よりも少なくすることができないということである。より少ない桁が送信される場合、必然的に乱数を再現するのに必要な情報よりも少ない情報しか送信されないことになる。実際、暗号アルゴリズムの特性において、十分な情報が暗号化乱数中に含まれない場合には、点Ｂで単一桁の乱数さえもエラー無しに再現することが保証されないほどである。
【０００４】
更に、Abrahamの特許は、送信用の第２パーティーの鍵を暗号化するために乱数を使用する。この送信が傍受され、乱数が鍵よりも少ない桁数を含む（すなわち、鍵よりも短い）場合、盗聴者が暗号を解読して秘密鍵を読むことは、秘密鍵自身を解読するよりも容易になる。したがって、システムのセキュリティが、乱数の長さによって決定されるセキュリティよりも勝ることはない。秘密鍵によってもたらされるセキュリティの程度が損なわれることを回避するために、乱数の長さは鍵の長さ以上でなければならず、したがって、第１パーティーから第２パーティーに送信される暗号化乱数も、鍵よりも長くなければならない。しかし、十分なセキュリティのために長い鍵を選ぶには、かなりの伝送時間が必要となる。例えば、セルラー電話システムなどの一部の通信システムでは、伝送時間は不足ぎみで高価な資源となっている。
【０００５】
しかしながら、セルラー電話などのフレキシブルなシステムでは、通信セキュリティが強く要望されている。米国では、セルラー電話による不正のための損失は数億ドルに達している。そのため、製造業者、サービス・プロバイダ、連邦通信委員会（ＦＣＣ:Federal Communications Commission）及び産業通商グループが、そのような不正を撃退するために多くの技術を開発することを余儀なくされている。１つの技術として、不正な存在への接続を回避するために、無線基地局及び移動局の両方、すなわち通信リンクの両端を認証するものがある。
【０００６】
セルラー通信システムの単純化したレイアウトを図２に示す。移動電話Ｍ１〜Ｍ１０は、セルラー基地局Ｂ１〜Ｂ１０に無線信号を送信し、かつそこから無線信号を受信することによって、公衆交換網の固定部分と通信する。セルラー基地局Ｂ１〜Ｂ１０は、移動体交換局（ＭＳＣ:Mobile Switching Center）を介して公衆交換網に接続されている。各基地局Ｂ１〜Ｂ１０は、対応する領域又は「セル」Ｃ１〜Ｃ１０内で信号を送信する。図２に示すように、基地局の理想化した配置編成においては、セルのオーバラップが最小限となる状態で、移動体通信が通常行われる領域（例えば大都市圏）が実質的にカバーされている。
【０００７】
ユーザがセル内で移動電話を活動させるとき、移動電話は、その移動電話の存在を示す信号をセルの基地局に送信する。移動電話は、各基地局によって連続的にモニタされる指定されたセットアップ・チャネル内に信号を送信するが、その信号は移動電話の電子シリアル番号（ＥＳＮ:electronic serial number）を含むことができる。基地局が移動電話の信号を受信したとき、基地局は、セル内の移動電話の存在を登録する。このプロセスは周期的に反復することができ、その結果、移動電話が別のセル内に移動した場合にも移動電話は適切に登録される。
【０００８】
移動電話番号がダイアルされたとき、電話会社の電話局は、その番号を移動電話として認識し、ＭＳＣに呼出しを転送する。ＭＳＣは、ダイアルされた移動電話番号及び現登録情報に基づいて、ある基地局にページング・メッセージを送信する。基地局のうちの１つ又は複数は、そのセットアップ・チャネル上にページを送信する。ダイアルされた移動電話は、セットアップ・チャネル上のそのアイデンティティーを認識し、基地局ページに応答する。移動電話は、割り当てられたボイス・チャネルに同調する命令にも追従し、次いでリンギングを開始する。移動体ユーザが通信を終了するとき、シグナル・トーンが基地局に送信され、両端はボイス・チャネルを解放する。
【０００９】
前述のオペレーションでは、移動電話は、一定のネットワークに永続的に接続されるのではなく、基地局とのいわゆる「エア・インターフェース（air interface）」を介して通信するものである。もちろん、これによってセルラー通信システムは使い勝手のよいものとなっている。それは、通信システムに物理的にリンクされるという制限なしに、ユーザが容易に移動電話を持ち運ぶことが可能になるからである。しかし、やはりこの同じ特徴により、セルラー電話システムを介して送信された情報を保護することを難しくしているのである。
【００１０】
例えば、通常の有線電話システムでは、電話機が物理的に接続されている通信回線を介して使用される場合、電話局は課金すべき特定の加入者を識別することができる。したがって、加入者のアカウントを不正に使用するには、通常加入者の回線に物理的に接続を行う必要がある。このことは、不正の意図があるユーザにとって発見されるリスクがあることを示すものである。
【００１１】
他方、セルラー遠隔通信システムでは、エア・インターフェースを介して通信するので、不正の意図があるユーザにとって、そのような接続の問題はない。保護方式が存在せず、ＥＳＮが、通信を確立し維持するために様々な時にネットワークに送信されるので、不正ユーザは、他の加入者のＥＳＮにアクセスすることによって別の加入者のアカウントを使用することができる。
【００１２】
標準セルラー接続を確立する際に、一般に移動電話によって２つの識別コードがシステムに送信される。これらは、移動体識別番号（ＭＩＮ:Mobile Identification Number）及びＥＳＮである。ＭＩＮは加入者を識別し、ＥＳＮは加入者が使用する実際のハードウェアを識別する。したがって、加入者が新しい装置を購入することにより、特定のＥＳＮに対応するＭＩＮが、時間の経過と共に変更される可能性があることが予想される。ＭＩＮは、１０桁のディレクトリ電話番号から導出される３４ビット２進数であり、ＥＳＮは、移動電話を一意的に識別する３２ビット２進数である。ＥＳＮは、一般に移動電話製造業者によって設定される。
【００１３】
例えば、拡張移動電話システム（ＡＭＰＳ）において通信をセットアップする際に使用される従来の認証方法を、図３のフローチャートに示す。この方法によれば、基地局は、ブロック２００で移動電話からＥＳＮ及びＭＩＮの両方を受信する。これらの識別コードは、移動電話から受信されたことを示す指定されたＥＳＮｍ及びＭＩＮｍである。次にブロック２０２で、基地局は、システム・メモリからＭＩＮｍに対応するＥＳＮｓｙｓを取り出す。次いでブロック２０４で、ＥＳＮｓｙｓはＥＳＮｍと比較される。２つのシリアル番号が同じである場合、フローはブロック２０６に進み、システム・アクセスが許可される。同じでない場合、システム・アクセスはブロック２０８で拒絶される。
【００１４】
このシステムの１つの欠点は、エア・インターフェース上で、又は他のソースから傍受することによって、不正ユーザが有効なＭＩＮ／ＥＳＮの組み合わせを組み上げることが比較的簡単であることである。移動電話から受信したＭＩＮ及びＥＳＮがシステム・メモリ中に格納されているものと一致した場合、この従来のシステムによるアクセスは有効であると推定されるので、不正アクセスのために必要な情報の全てを電子傍受によって得ることができる。
【００１５】
Dentの米国特許第５０９１９４２号、ならびにDentらの米国特許第５２８２２５０号、第５３９０２４５号、及び第５５５９８８６号は、セルラー電話システムなどのシステムでの通信セキュリティの問題を対象とし、これらの特許の全てを参照により本明細書に明白に組込まれる。これらの特許は、従来のセルラー電話方法及びAbrahamの特許の方法に伴う前述の問題を、図４に示す方法などによって解決する。
【００１６】
第１パーティーは、一般に通信を開始するパーティーであり、乱数ｒａｎｄを選び、ｒａｎｄを第２パーティーに送信する。加えて、第１パーティーは、認証アルゴリズム１０を使用して、第１パーティーの秘密鍵によりｒａｎｄを暗号化し、２つの部分ｒｅｓｐ１及びｒｅｓｐ２を有する暗号化乱数を生成する。第１パーティーは、第２パーティーにｒｅｓｐ２も送信する。第２パーティーは、認証アルゴリズム１０のそのローカル・バージョンで、受信したｒａｎｄを第２パーティーの秘密鍵により暗号化し、２つの部分ｒｅｓｐ１’及びｒｅｓｐ２’を有する暗号化乱数を生成する。第２パーティーは、比較器１１を使用してｒｅｓｐ２’がｒｅｓｐ２にマッチするかどうかを判定する。マッチは、第１パーティーがおそらく真正であり、応答に値することを第２パーティーに示す。第２パーティーから第１パーティーへの応答は、ｒｅｓｐ１’を含む。第１パーティーは、比較器１２を使用して、受信したｒｅｓｐ１’がｒｅｓｐ１にマッチするかどうかを判定する。マッチは、第２パーティーがおそらく真正であることを第１パーティーに示す。通信の両端のそのような認証は、双方向認証と呼ぶことができる。
【００１７】
従来方法とは対照的に、パーティーによって交換される量ｒａｎｄ、ｒｅｓｐ２、及びｒｅｓｐ１’の長さは、図４に示すシステムのセキュリティには重要ではない。実際、これらの量は、秘密鍵よりも少ない桁を有することができる。桁数は、第１パーティーと同じ秘密鍵を所有しない第２パーティーが、第１パーティーが予期する値ｒｅｓｐ１と等しいｒｅｓｐ１’を偶然に得る確率が無視できるほど小さく、第２パーティーによって計算されることになるｒｅｓｐ２’の値に等しい値ｒｅｓｐ２を第１パーティーが偶然に得る確率が無視できるほど小さければ、十分である。例えば、ｒｅｓｐ１及びｒｅｓｐ２の両方が、１６個の２進数（ビット）を有する場合、そのような値を偶然に正しく得る可能性は、わずか１／６５５３６であり、これは、多くの有用な通信システムに関して、謎解きゲームを無益なものとするのに足る十分小さい値である。更に、ｒｅｓｐ１及びｒｅｓｐ２を組合わせた秘密鍵よりもずっと短い長さを使用することは、たとえ全ての鍵を試行するのに十分なコンピューティング能力が利用可能である場合でも、鍵の一意的な決定を可能にするには不十分である情報が送信されることを意味する。それでも、図４の方法は、パーティー間で長い認証量を交換する送信時間オーバヘッドを招くことはないにしても、そのような計算を非実際的にするように長い鍵を選ぶ自由が残されている。
【００１８】
他方、図４の方法は、盗聴者が真正の第１パーティーからｒａｎｄとｒｅｓｐ２対のいくつかの組を集めることができ、次いでその組を使用して真正の第２パーティーをアドレス指定するか、又は秘密鍵の解読を試行することができる場合、弱められる可能性がある。上記で参照により組み込んだ特許は、ローリング・キーの使用を含めて、後者の弱点を抑える方式を開示する。Osbornによる「Ｓｙｓｔｅｍ  ｆｏｒ  Ｐｒｅｖｅｎｔｉｎｇ  Ｅｌｅｃｔｒｏｎｉｃ  Ｍｅｍｏｒｙ  Ｔａｍｐｅｒｉｎｇ」という名称の米国特許出願第０８／７０６５７４号は、前者の弱点に対処するものであり、この特許出願を参照により本明細書に明白に組込まれる。
【００１９】
しかし、送信オーバヘッドを最小に保ちながら、双方向認証手順のセキュリティを向上することが依然として重要である。これらの目的又は利点は、この出願で説明する認証方法を実施するときに得られる。
【００２０】
［発明の概要］
第２パーティーとの通信の開始を望む第１パーティーは、第１の桁数を有する乱数を生成する。次いで、第１パーティーは、秘密暗号鍵を使用して乱数を暗号化し、第１の桁数よりも多い、又は等しい桁の第２の桁数を有する暗号化乱数を得る。次いで、暗号化乱数の選択した第３の桁数が、第２パーティーに送信される。ただし、第３の桁数は第１の桁数よりも少ない。
【００２１】
第２パーティーは、第１パーティーから送信された桁を受信し、予め合意された方法で第３の桁数を伸長し、第２の桁数を得る。伸長プロセスは、ゼロなどの一定の桁で第３の桁数を引き伸ばすのと同様に、単純でよい。
【００２２】
次い、で第２パーティーは、第２パーティーの秘密鍵を使用して、得られた第２の数桁を暗号解読し、第１の桁数を得る。この第１の桁数は、第１パーティーによって選ばれた元の乱数と等しくない。次いで、そのように得られた第１の桁数は、第２パーティーの秘密鍵を暗号化するために暗号鍵として第２パーティーによって使用され、それによって第２の桁数を含む暗号化鍵を得る。次いで、第２の桁数よりも少ない第４の桁数が第２パーティーによって選択され、第１パーティーに送信される。
【００２３】
第１パーティーは、第１パーティーに送信した第３の桁数も予め合意された同じ方法で伸長し、第２の桁数を得、次いでこの得られた第２の桁数をその秘密鍵を使用して暗号解読し、もう一度第１の桁数を得る。次いで、第１パーティーは、第２パーティーと同じように、第１の桁数から第２の桁数よりも少ない第４の桁数を選択し、選択した第４の桁数を第２パーティーから受信した第４の桁数と比較する。完全なマッチングが検出された場合、第１パーティーは、第２パーティーが第１パーティー自身と同じ秘密鍵を所有していると検証したことになる。
【００２４】
次いで、第２パーティーによって選ばれた新しい乱数で開始される前述の手順を反復するか、又は第２パーティーから受信される桁及び第１パーティーの秘密鍵に基づいて、第１パーティーから第２パーティーに返すべき桁数を引き続き導出することによって、第２パーティーが第１パーティーのアイデンティティを検証することが可能となるように、役割を反転することができる。
【００２５】
前述のより一般的な実施例では、より多い桁数からより少ない桁数を選択するステップは、予め合意された圧縮アルゴリズムを使用して、より多い桁数からより少ない桁数を生成するステップによって置換することができる。この予め合意された圧縮アルゴリズムは、圧縮を実行するパーティーに利用可能な秘密鍵に依存できる。
【００２６】
加えて、計算労力の節約が達成されるなら、より少ない桁数のみで充分なときはいつでも、より多い桁数は全く必要としない。
【００２７】
本出願人の発明の特徴、目的、及び利点は、添付の図面と共にこの説明を読むことによって理解されよう。
【００２８】
［詳細な説明］
本発明は、セルラー基地局のグループなどの通信ネットワークからサービスを受信するのを要求する、セルラー電話などのユーザ端末を有する通信システムで適用可能である。
【００２９】
本発明の第１実施例は、図５を用いて説明することができる。図５は図４に基づいている。第１ケースでは、ネットワークが端末と通信の開始を望むと仮定する。そして、図４及び図５の第１パーティーはネットワークであり、第２パーティーである端末に対（ｒａｎｄ，ｒｅｓｐ２）を送信する。図５では、ネットワークは、「第１パーティー」秘密鍵について、図４のように第１パーティー自身の秘密鍵ではなく、真正の第２パーティー（ユーザ端末）にネットワークが割り当てた秘密鍵を使用する。第２パーティーは、図４及び５に示すように、受信したｒｅｓｐ２がそのローカルに計算したｒｅｓｐ２’にマッチする場合にだけ、ｒｅｓｐ１’で応答する。このようにして、ｒｅｓｐ２を計算することができない偽のネットワークは、真正の端末に値ｒｅｓｐ１’での応答を引き起こすことができず、図５で示すこの方法は、従来の認証方法に伴う問題を回避する。
【００３０】
原理上は、盗聴者は、以下の複合シーケンスを実行することによって、図５の方法に対してアタックすることができる。
【００３１】
１．ネットワークを介して真正の端末に呼出しを起こさせ、それによってネットワークが（ｒａｎｄ，ｒｅｓｐ２）対を真正の端末に送信するようにさせる。
【００３２】
２．ネットワークによって送信された（ｒａｎｄ，ｒｅｓｐ２）対を傍受する。その対を使用して、同じ真正の端末をアドレス指定して、端末がｒｅｓｐ１’で応答するようにさせる。（もちろん、盗聴者は、真正の端末がネットワークにｒｅｓｐ１’で応答するのを単に待機することもできる。）そして端末によって送信されたｒｅｓｐ１’を傍受する。
【００３３】
３．後は、ネットワークへの呼出しを開始し、認証チャレンジ（ｒａｎｄ，ｒｅｓｐ２）対を受信し、不正アクセスを得るために、ステップ２で得られたｒｅｓｐ１’で応答する。
【００３４】
この種の不正は、「真正の端末の助けを借りた不正」と呼ぶことができ、前述で参照により組み込んだ’９４２、’２５０、’２４５、及び’８８６特許に記載されている通り、電話システムに関しては、ダイヤルした数字を認証アルゴリズム１０への入力として含めることによって防止することができる。したがって、ネットワークが電話への呼出しを開始するとき、ｒｅｓｐ２の値は、乱数ｒａｎｄ、呼出し先パーティーに割当てられた秘密鍵、及び呼出し先パーティーの電話番号の全て又は一部に基づいて、図５のアルゴリズム１０によって生成される。
【００３５】
他方、電話がネットワークへの呼出しを開始するとき（図５の第１パーティーが呼出し元である）、ネットワーク（図５の第２パーティー）が認証のために必要とする値ｒｅｓｐ１’は、乱数ｒａｎｄ、呼出し元の秘密鍵、及び呼出し先パーティーの電話番号の全て又は一部に基づいて、ネットワーク及び呼出し元の両方によって生成される。したがって、盗聴者は、ステップ３で、自分自身を呼出すために有効なｒｅｓｐ１’しか所有しないことになり、第３パーティーへの呼出しを起こすことはできない。
【００３６】
図５に示した双方向認証方法は、従来方法に勝るいくつかの利点を有するものの、上記で引用した本出願人の’９４２特許に記載されているように、分散移動電話交換システムなどのある通信システムでの実用上の問題により、そのようなダイアルした桁の使用が妨害される可能性がある。したがって、別の双方向認証方法を以下で説明する。
【００３７】
本出願人の発明による双方向認証の別の方法を図６に示す。第１実施例では、例えば通信の開始を望む第１パーティーは、乱数を生成する。この乱数は長くすることがきる。すなわち、この乱数はどんな桁数を有することもできる。この乱数は、点Ａで暗号化アルゴリズム１００に印加される。暗号化アルゴリズム１００は、やはり暗号化アルゴリズム１００に印加される第１パーティーの秘密鍵により暗号化乱数を生成する。しかし、Abrahamの特許及び図１とは異なり、暗号化乱数は復号乱数と同じ桁を有する必要はなく、例えば暗号化アルゴリズム１００は、「情報不可逆（infprmation-lossy）」なアルゴリズムでよい。
【００３８】
暗号化アルゴリズム１００が「情報不可逆」なアルゴリズムでない場合、暗号化乱数は、選択／圧縮オペレーション１０１によって示すように、所定の桁を選択することによって、あるいはその他の方法で、所定の桁を切り捨てるか、又は圧縮することによって短縮することもできる。暗号化アルゴリズム１００と選択／圧縮オペレーション１０１とを組み合わせることによって、アルゴリズムの出力を逆変換してアルゴリズムへの入力すなわち乱数や秘密鍵を見つけ出すことが決してできないという点での、情報不可逆なアルゴリズムが形成される。
【００３９】
次いで、短縮暗号化乱数は、第１パーティーから第２パーティーに送信される。第２パーティーは、暗号解読アルゴリズム２００を使用して受信した値を暗号解読する。暗号化アルゴリズム１００の擬似的な逆処理として、暗号解読アルゴリズム２００が暗号化アルゴリズム１００によって生成された出力桁数に等しい入力桁数を必要とする場合、受信した短縮暗号化乱数は、必要に応じて挿入／伸長オペレーション２０１によって伸長される。短縮暗号化乱数は、伸長又はゼロなどの所定の桁を挿入されて、第２パーティーの暗号解読アルゴリズム２００に対する所望の入力桁数を得る。
【００４０】
第２パーティーの暗号解読アルゴリズム２００は、必要な場合伸長した暗号化乱数を、暗号解読して、点Ｂで修正乱数を生成する。修正乱数は、第１パーティーの乱数と同じ桁数を有することができるが、それらの桁のうちのどれも、第１パーティーの乱数と同じであることは保証されない。修正乱数は、データとして暗号化アルゴリズム１１０に印加される第２パーティーの秘密鍵を暗号化するために、暗号化鍵として第２パーティーの暗号化アルゴリズム１１０に印加される。
【００４１】
Abrahamの特許及び図１とは対照的に、暗号化アルゴリズム１１０は、暗号化アルゴリズム１００などの情報不可逆アルゴリズムでよく、必須ではないが、暗号化アルゴリズム１００と同じであってもよい。したがって、暗号化アルゴリズム１１０によって生成される暗号化した第２パーティーの秘密鍵の桁数は、修正乱数又は第２パーティーの秘密鍵のどちらの桁数よりも小さくすることができる。要望があれば、所定の出力桁を選択し、あるいは暗号化された第２パーティーの秘密鍵を圧縮する選択／圧縮オペレーション１０２によって桁数を更に減少させることもできる。前述のように、暗号化アルゴリズム１１０が情報可逆である場合であっても、暗号化アルゴリズム１１０と選択／圧縮オペレーション１０２とを組み合わせることによって、情報不可逆アルゴリズムが形成される。換言すれば、アルゴリズムの出力を逆変換し、暗号化アルゴリズム１１０への両方の入力を得ることは不可能であるということである。
【００４２】
第２パーティーは、暗号化された第２鍵を（要望があれば圧縮して）第１パーティーに送信する。Abrahamの特許及び図１とは対照的に、図６の第１パーティーは、点Ａからの乱数を暗号解読鍵として使用して受信した第２パーティーの暗号化鍵を暗号解読することができず、第１パーティーは、第２パーティーの鍵を第１パーティー自身の鍵と比較することができないことになる。その代わり、本出願人の発明によれば、第１パーティーが第２パーティーに送信した短縮乱数と、挿入／伸長オペレーション２０１，暗号解読アルゴリズム２００，暗号化アルゴリズム１１０，及び選択／圧縮オペレーション１０２のコピー３００と、第１パーティー自身の秘密鍵とを使用して、第１パーティーにより期待される値が生成される。比較器１２０は、コピー３００によって生成された値が第２パーティーから受信した値と同じかどうかを判定する。比較器１２０が完全な一致を示した場合、第２パーティーが第１パーティーと同じ秘密鍵を有する確率は高く、それによって第２パーティーを第１パーティーが認証する。
【００４３】
各パーティーは、エラー・フリー式に他のパーティーに情報を提供して、比較器の一致／不一致の表示が認証表示にもなることを理解されたい。例えば、パーティーは、セルラー通信システムのエア・インターフェースを介して送信されたメッセージによって情報を交換することができる。そのようなメッセージは、実質上エラー・フリー通信を保証するエラー修正コーディング及び自動反復要求（ＡＲＱ:automatic repeat request）技術によって、通常保護される。もちろん、セルラー・エア・インターフェースを使用する必要はない。各パーティーに必要な情報を提供する他の方法を利用することができる。
【００４４】
要望があれば、次いで第２パーティー及び第１パーティーの役割を反転することもでき、異なる乱数を使用して第１パーティーを第２パーティーに認証させ、それによって双方向認証を達成することができる。次いで、パーティーは、暗号化のためのそれらの秘密鍵又はその派生物を使用して暗号化通信を続行することができる。使用されるどんな派生物も、タイム／日付スタンプ、呼出し番号、呼出し先パーティーの電話番号、呼出し元の電話番号、修正乱数、及び２つのパーティーが共通に有する桁の全て、又は何らかの混合のうちの１つ又は複数を組み合わせるなどの相互合意プロセスによって、秘密鍵を導出しなければならない。そのような桁は、Hassanらの米国特許第５６０４８０６号及び第５７４５５７８号と、Hassanらによる米国特許出願第０８／５５５９６８号及び第０９／０１５７７４号などに記載されている方式で得ることができる。これらは、位相の短期相互関係（short-term reciprocity）及びラピッド・デコリレーション（rapid decorrelation）などの無線通信路の特性を使用して、暗号化通信のためのキー・シーケンスを確立することに関するものである。おそらく最も単純な場合では、呼出し又は通信セッションのための暗号化鍵として修正乱数を使用することができる。
【００４５】
図６でボックス３００内の詳細を省略した場合、図６は、容易に移動体通信規格用グローバル・システム（ＧＳＭ:Grobal Syatem for Mobile）規格の下で動作する通信システムで実施される認証方法と比較することができる。１つの明らかな違いは、ｒａｎｄ値を生成する本出願人の方法が、図６のブロック１００、１０１を含むことである。
【００４６】
’９４２、’２５０、’２４５、及び’８８６特許が開示するのは、好ましい双方向認証方法によれば、通信開始の試行を受信する側が、その試行を偽ソースから受信した場合に、応答を行ったり又は不適切なアクションをとるのを阻止する効果があることである。そのような真正のパーティーを通信に携わらせようとする偽のパーティーからの試行は、通常は何らかの不正行為を目的とするが、代わりに単にいやがらせ（nuisance）をすることを意図している場合もある。例えば、「ｎｏ」応答を不正信号に対し行うことさえハンドヘルド電話中のバッテリ・パワーを消費して、充電間のバッテリ寿命を減少させる可能性がある。したがって、通信開始側の第１パーティーから第２パーティーへの非常に高速な送信において、第２パーティーが応答する前に第１パーティーを認証することを可能とする情報が含まれることが好ましい。本出願人の発明によるそのような方法を図７に示す。
【００４７】
図７では、第１パーティーは、図６で同じ番号を付けたブロックに関連して説明したのと同様のブロック１００、１０１、２０１、２００、及び１１０のオペレーションを実行する。図６と図７の間の１つの違いは、図７のブロック１０３が、第１パーティーの暗号化秘密鍵に基づく２つの選択又は圧縮した出力値をもたらす修正選択／圧縮オペレーションを示すことである。’２５０及び’２４５特許で記載されている技術との比較を助けるために、これらの２つの値は、「ｒｅｓｐ１」及び「ｒｅｓｐ２」と呼ぶことができ、選択／圧縮オペレーション１０１によって生成された短縮暗号化乱数を「ｒａｎｄ」と呼ぶことができる。（オペレーション１０１が存在しない場合、暗号化乱数を「ｒａｎｄ」と呼ぶことができる）。次いで、第１パーティーは、ｒａｎｄとｒｅｓｐ２の両方を第２パーティーに送信する。
【００４８】
第２パーティーは、図６で同じ番号を付けたブロックに関連して説明したのと同様のブロック２０１、２００、及び１１０のオペレーションを実行する。しかし、図７では、第２パーティーは第１パーティーのブロック１０３の対応物を有する。このようにして、第２パーティーの秘密鍵を使用して、ｒｅｓｐ１及びｒｅｓｐ２の対応する値を得る。ｒｅｓｐ１及びｒｅｓｐ２は、第１パーティー及び第２パーティーが同じ秘密鍵を有する場合にだけ、第１パーティーの対応する値に等しくなることになる。比較器１３０は、第２パーティーの値ｒｅｓｐ２が第１パーティーから受信されたｒｅｓｐ２値にマッチするかどうかを判定し、マッチする場合、第１パーティーが真正である確率が高い。
【００４９】
第２パーティーが、第１パーティーを認証する場合にだけ、第２パーティーは、第１パーティーに第２パーティーのｒｅｓｐ１値を含む応答を送信することになる。次いで、第１パーティーは、比較器１２０を使用して、自身のｒｅｓｐ１値を、第２パーティーから受信したｒｅｓｐ１値と比較する。値がマッチする場合、第１パーティーは、第２パーティーがおそらく真正であることを確認したことになり、双方向認証プロセスを完了する。
【００５０】
要望があれば、別の双方向認証を第１パーティーと第２パーティーの役割を交換することによって行うことができ、異なる乱数を使用して、図７に示す双方向認証を再び実行することができる。これは、他のパーティーを認証することが望ましいパーティーに乱数を選ぶことを許可するときに、１度だけ実行される双方向認証手順を介して追加のセキュリティを提供して、以前に傍受された（ｒａｎｄ，ｒｅｓｐ１，ｒｅｓｐ２）値が盗聴者によって反復されるリスクを除去する。送信オーバヘッドを減少させるために、（双方向認証プロセスの第２反復で）第２パーティーから第１パーティーに送信される（ｒａｎｄ，ｒｅｓｐ２）対を、（第１反復での）ｒｅｓｐ１値の第２パーティーからの送信と組み合わせることができる。
【００５１】
図７でボックス３００内の詳細を省略した場合、図７は、図４などに示すような、’９４２、’２５０、’２４５、及び’８８６特許に記載されている方法と容易に比較することができる。１つの明らかな違いは、ｒａｎｄ値を生成する本出願人の方法が図７のブロック１００、１０１を含むことである。
【００５２】
図７に示す方法によって提供されるセキュリティは、第１パーティーから第２パーティーに送信される第１ｒａｎｄ値と、第２パーティーから第１パーティーに送信される第２ｒａｎｄ値の両方が、第２パーティーから第１パーティーに送信される値の第２（ｒｅｓｐ１，ｒｅｓｐ２）対に影響を与えることを可能にすることにより向上させることができる。このようにして、盗聴者は、傍受した値を使用して真正のパーティーとして装うために、２つのｒａｎｄの特定の組み合わせを事前に正確に傍受していなければならないことになる。このようにして、第２パーティーは、第１パーティーの真正性のより強力な表示を受信する。このことは、通常、不正者が開始パーティー又は第１パーティーとなるということに、不正の企てが関係しているということを念頭に置けば、理にかなっている。
【００５３】
本出願人の発明の１つの態様では、要望があれば、両方向でセキュリティを向上させるために偽チャレンジに対する応答を禁止する利点を犠牲にして、より高速な双方向認証を得ることができる。図７に示す方法のこの変形形態では、第１パーティー及び第２パーティーは、選ばれた乱数をそれぞれ交換し、それから各パーティーはその各秘密鍵及び他のパーティーから受信された乱数を使用して、応答（すなわちｒｅｓｐ１’値）をそれぞれ計算する。次いで、パーティーは、これらの応答を交換し、それらを、他のパーティーと同様にそれぞれ計算することができる期待される応答（すなわちｒｅｓｐ１値）と比較する。
【００５４】
第１パーティーＡ及び第２パーティーＢを呼出す際に、ＡからＢへの応答が、ＢからＡへの応答と同じである可能性を回避することが望ましい。そのような条件では、あるパーティーが単に他のパーティーの応答をエコーするのでないなら、正確に同じ瞬間に応答が交換される場合にのみ認証値を有するからである。したがって、Ａ及びＢは、異なる方式でその応答を計算すべきである。これは、一般に、一方向に対して使用される「Ａ−ｔｏ−Ｂ」アルゴリズムと、他方向に対して使用される「Ｂ−ｔｏ−Ａ」アルゴリズムとして理解することができる。
【００５５】
この識別可能性は、いくつかの方式で達成することができる。あるパーティーによって使用されるアルゴリズムは、そのパーティーのステータスに依存させることができる。例えば、Ａが通信ネットワーク、Ｂがネットワーク加入者端末でよい。別の例として、あるパーティーは、通信セッションを開始するときにあるアルゴリズムを使用し、別のパーティーによって開始されたセッションに応答するときに別のアルゴリズムを使用することができる。アルゴリズムを決定すると、アルゴリズムはその入力を変えることによって更に識別される。例えば、ＡからＢへの応答は、Ｂから受信した乱数の桁の順序を反転することによって計算することができる。別の例として、Ａ及び／又はＢは、乱数又は鍵のビットのうちの１つをＯＮＥからＺＥＲＯに変更することができる。もう１つの例としては、Ａ及びＢは、計算した応答値の奇数又は偶数ビット、又は奇数又は偶数桁を交換し、奇数値を一方向に送信し、偶数値を他方向に送信することができる。そのような識別をいくつか組み合わせて、互いに識別可能となるように、それぞれの方向に対するアルゴリズムを修正又は選ぶことができる。
【００５６】
本出願人の発明の別の態様は、認証のための送信オーバヘッドをより許容する通信システムにおいて有利な「累積認証(cumulative authentication)」と呼ぶことができる。累積認証では、Ａは、まず認証値の第１桁をＢにリリースし、Ｂは、この第１認証桁を検証する際にＡに第２認証桁をリリースし、そのときＡは、第２認証桁を検証した後にＢに第３認証桁をリリースし、以下同様である。そのような累積認証によれば、何らかの桁が誤りであると検出されて、偽のパーティーであることが示唆された際に、両方向に完全な応答をリリースすることが防止される。
【００５７】
本出願人の発明を特定の実施形態を参照して上記で説明した。本発明を前述の形態以外の形態で実施することが可能であることは、当業者には容易に明らかであろう。前述の特定の実施形態は、単に実例であって、決して限定的なものとみなすべきではない。本発明の範囲は、添付の請求の範囲によって決定され、請求の範囲内にある全ての変形形態及び均等物は、その中に含まれるものとする。
【図面の簡単な説明】
【図１】  通信システム中の構成要素認証用の従来のシステムを示す図である。
【図２】  セルラー通信システムの単純化したレイアウトを示す図である。
【図３】  従来の認証方法を示す図である。
【図４】  従来の双方向認証方法を示す図である。
【図５】  本発明による認証方法を示す図である。
【図６】  本発明による認証方法を示す図である。
【図７】  本発明による認証方法を示す図である。
【図１】
0004536934.tif 000002
【図２】
0004536934.tif 000003
【図３】
0004536934.tif 000004
【図４】
0004536934.tif 000005
【図５】
0004536934.tif 000006
【図６】
0004536934.tif 000007
【図７】
0004536934.tif 000008