(57)【要約】      （修正有）【課題】不正盗聴に対処できるように、２つの通信端末におけるセッション鍵を生成する。【解決手段】通信端末Ａにおいて、ランダム整数ｘを選択し、指数関数ｆ（α）ｇ（ｘ）を提供し（αは生成元）、ランダム整数ｘ、指数関数ｆ（α）ｇ（ｘ）、及び秘密鍵ａから署名ｓＡを生成する。通信端末Ｂにおいて、ランダム整数ｙを選択し、別の指数関数ｆ’（α）ｇ（ｙ）を提供し、ランダム整数ｙ、指数関数ｆ’（α）ｇ（ｙ）、及び秘密鍵ｂから署名ｓＢを生成する。通信端末Ａ及びＢはそれぞれ、通信端子Ｂ及びＡに、指数関数ｆ（α）ｇ（ｘ）及び指数関数ｆ’（α）ｇ（ｙ）を含むメッセージを送る。通信端末Ａ及びＢにおいて、それぞれ、通信端末Ｂ及びＡによって公開された情報を、通信端末Ａ及びＢに属する秘密情報を用いて指数化することによってセッション鍵Ｋを構築する。【選択図】図１
2010011478.tif 000002
【特許請求の範囲】
【請求項１】
公開鍵暗号化を採用しているデータ通信システムにおいて、通信チャネル（１４）を介して第１及び第２の通信端末（Ａ及びＢ）の間で情報を交換することを可能にするために、第１及び第２の通信端末間の鍵を設定する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元αとこれら秘密鍵とからそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ｉ）第１の通信端末（Ａ）において第１のランダム整数ｘが選択され、生成元αを含む第１の関数ｆ（α）のｇ（ｘ）をベキとする指数関数を作ることにより、第１の指数関数ｆ（α）ｇ（ｘ）を提供するステップと、
ｉｉ）第１の通信端末（Ａ）において、第１のランダム整数ｘと第１の機密鍵ａとを組み合わせるために、第１のランダム整数ｘ、第１の指数関数ｆ（α）ｇ（ｘ）、及び第１の秘密鍵ａから第１の署名ｓＡを生成して、該第１の署名を保持するステップと、
ｉｉｉ）第１の通信端末（Ａ）から、第２の通信端子（Ｂ）に向けて、第１の指数関数ｆ（α）ｇ（ｘ）を含むメッセージを送るステップと、
ｉｖ）第２の通信端末（Ｂ）において、第２のランダム整数ｙを選択され、該第２のランダム整数ｙと第２の秘密鍵ｂとを組み合わせるために、生成元αを含む第２の関数ｆ’（α）のｇ（ｙ）をベキとする指数関数を作ることにより、第２の指数関数ｆ’（α）ｇ（ｙ）を提供し、第２のランダム整数ｙ、第２の指数関数ｆ’（α）ｇ（ｙ）、及び第２の秘密鍵ｂから第２の署名ｓＢを生成して、該第２の署名を保持するステップと、
ｖ）第２の通信端末（Ｂ）から、第１の通信端末（Ａ）に向けて、第２の指数関数ｆ’（α）ｇ（ｙ）を含むメッセージを送るステップと、
ｖｉ）第１の通信端末（Ａ）において、第２の通信端末（Ｂ）によって公開された情報を、第１の通信端末に属する秘密情報を用いて指数化することによって、セッション鍵Ｋを構築し、第２の通信端末（Ｂ）において、第１の通信端末（Ａ）によって公開された情報を、第２の通信端末に属する秘密情報を用いて指数化することによって、セッション鍵Ｋを構築するステップと
からなることを特徴とする方法。
【請求項２】
請求項１記載の方法において、第１の通信端末（Ａ）によって送られる情報は、該第１の通信端末の識別子を含み、第２の通信端末（Ｂ）によって送られる情報は、該第２の通信端末の識別子を含んでいることを特徴とする方法。
【請求項３】
請求項１又は２記載の方法において、生成元αを含む第１の関数ｆ（α）は、生成元α自体であり、生成元αを含む第２の関数ｆ’（α）は、生成元α自体であることを特徴とする方法。
【請求項４】
請求項１又は２記載の方法において、生成元αを含む第１関数ｆ（α）は、第２の通信端末（Ｂ）の公開鍵ｐＢを含み、生成元αを含む第２の関数ｆ’（α）は、第１の通信端末の公開鍵ｐＡを含むことを特徴とする方法。
【請求項５】
請求項１〜３いずれかに記載の方法において、第１の署名ｓＡは、第１の指数関数ｆ（α）ｇ（ｘ）から得られた整数ｒａ＊を用いて生成され、第２の署名ｓＢは、第２の指数関数ｆ’（α）ｇ（ｙ）から得られた整数ｒｂ＊を用いて生成されることを特徴とする方法。
【請求項６】
請求項５記載の方法において、第１の通信端末によって公開された情報は、第１の公開鍵ＰＡ、第１の指数関数ｆ（α）ｇ（ｘ）、及び整数ｒａ＊を組合せ、第２の通信端末によって公開された情報は、第２の公開鍵ＰＢ、第２の指数関数ｆ’（α）ｇ（ｙ）、及び整数ｒｂ＊を組み合わせることを特徴とする方法。
【請求項７】
請求項６記載の方法において、生成元αは、ｐを素数とする乗法群Ｚ＊ｐの要素であることを特徴とする方法。
【請求項８】
請求項５〜７いずれかに記載の方法において、第１の署名ｓＡ及び第２の署名ｓＢは、
ｓＡ＝ｘ＋ｒａ＊ａαａ  ｍｏｄ  （ｐ−１）
ｓＢ＝ｙ＋ｒｂ＊ｂαｂ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項９】
請求項８記載の方法において、
第１の通信端末によって、セッション鍵Ｋが、Ｋ＝（αｙ（αｂ）（ｒｂ＊））ｓＡ  ｍｏｄ  ｐとして計算され、
第２の通信端末によって、セッション鍵Ｋが、Ｋ＝（αｘ（αａ）（ｒａ＊））ｓＢ  ｍｏｄ  ｐとして計算されることを特徴とする方法。
【請求項１０】
請求項５〜９いずれかに記載の方法において、αは、ｑをｐ−１の素除数とした場合、群Ｚ＊ｐの位数ｑの部分群の生成元であることを特徴とする方法。
【請求項１１】
請求項５又は６記載の方法において、生成元αは、有限体Ｆｑ上で定義される楕円曲線上の位数ｎの点Ｐであり、該楕円曲線上のスカラ乗算によって、累乗が実行されることを特徴とする方法。
【請求項１２】
請求項１１記載の方法において、整数ｒａ＊及び整数ｒｂ＊は、第１及び第２の指数関数の座標のビット・ストリングスであることを特徴とする方法。
【請求項１３】
請求項１１又は１２記載の方法において、第１及び第２の署名ｓＡ及びｓＢは、
ｓＡ＝（ｘ＋（ｒａ＊）ａ）  ｍｏｄ  ｎ
ｓＢ＝（ｙ＋（ｒｂ＊）ｂ）  ｍｏｄ  ｎ
であることを特徴とする方法。
【請求項１４】
請求項１３記載の方法において、第２及び第１の通信端末において、セッション鍵Ｋはそれぞれ、
Ｋ＝ｓＡ（ｒｂ＋（ｒｂ＊）ＰＢ）
Ｋ＝ｓｂ（ｒａ＋（ｒａ＊）ＰＡ）
によって計算されることを特徴とする方法。
【請求項１５】
請求項１〜３いずれかに記載の方法において、第１及び第２の署名ｓＡ及びｓＢは、
ｓＡ＝ｘ＋ｒＡａαａ  ｍｏｄ  （ｐ−１）
ｓＢ＝ｙ＋ｒＢｂαｂ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項１６】
請求項４記載の方法において、第１及び第２の署名ｓＡ及びｓＢは、
ｓＡ＝ｘ＋ａ（ｐＢ）ｘ  ｍｏｄ  （ｐ−１）
ｓＢ＝ｙ＋ｂ（ｐＡ）ｙ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項１７】
通信チャネル（１４）を介して第１及び第２の通信端末（Ａ及びＢ）の間で情報を交換することを可能にするために、公開鍵通信システムにおいて、第１及び第２の通信端末間のセッション鍵Ｋを搬送する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元αとこれら秘密鍵とからそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ａ）第１の通信端末において第１のランダム整数ｘが選択され、該ランダム整数ｘと生成元αとから第１の値ｒＡを計算するステップと、
ｂ）第１の通信端末において、第１のランダム整数ｘと、第１の値ｒＡと、第１の秘密鍵ａとから第１の署名ｓＡを生成するステップと、
ｃ）第１の通信端末において、第１のランダム整数ｘと第２の通信端末に属する公開情報とからセッション鍵Ｋを計算するステップと、
ｄ）第１の通信端末から、第２の通信端子に向けて、第１の値ｒＡ及び第１の署名ｓＡを含むメッセージを送るステップと、
ｅ）第２の通信端末において、生成元α、第１の署名ｓＡ、第１の値ｒＡ、及び第１の通信端末に属する公開情報を用いて計算された値の有効性を検証するステップと、
ｆ）第２の通信端末において、第１の値ｒＡと、第２の通信端末に属する秘密情報であって、第２の通信端末に属する公開情報に関連している情報とから、セッション鍵Ｋを計算するステップと
からなることを特徴とする方法。
【請求項１８】
請求項１７記載の方法において、第１の値ｒＡは、生成元を含む第１の関数ｆ（α）を第１のランダム整数ｘをベキとするように指数化することによって計算されることを特徴とする方法。
【請求項１９】
請求項１８記載の方法において、第１の関数ｆ（α）は生成元αそのものであることを特徴とする方法。
【請求項２０】
請求項１７〜１９いずれかに記載の方法において、第１の署名ｓＡは、
ｓＡ＝ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項２１】
請求項１７〜１９いずれかに記載の方法において、第２の通信端末に属する公開情報は該通信端末の公開鍵ｐＢであり、第２の通信端末に属する秘密情報は該通信端末の秘密鍵ｂであり、第１の通信端末に属する公開情報は該通信端末の公開鍵ｐＡであることを特徴とする方法。
【請求項２２】
請求項２１記載の方法において、第１の通信端末によって計算されたセッション鍵Ｋは、（ｐＢ）ｘであることを特徴とする方法。
【請求項２３】
請求項２１又は２２記載の方法において、第２の通信端末によって有効性が検証される値は、αｓＡ（ｐＡ）ｒＡ・αａであることを特徴とする方法。
【請求項２４】
請求項２３記載の方法において、第２の通信端末によって計算されたセッション鍵Ｋは、（ｒＡ）ｂであることを特徴とする方法。
【請求項２５】
請求項１７〜２４いずれかに記載の方法において、第２の通信端末が、第１の通信端末にランダム・ビット・ストリングｋを送るステップを備えており、このステップは、セッション鍵Ｋと該セッション鍵Ｋで排他的論理和されたビット・ストリングｋとでメッセージを暗号化して、メッセージを暗号化するための短命鍵（ｋ＋Ｋ）を設定する前に、実行されることを特徴とする方法。
【請求項２６】
公開鍵データ通信システムにおいて、第１及び第２の通信端末間でセッション鍵を搬送して、これら通信端末の間で通信チャネルを介して情報を通信するための共通鍵を設定する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元α及びこれら秘密鍵からそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ｉ）第１の通信端末において第１のランダム整数ｘが選択され、生成元αを含む第１の関数ｆ（α）のｇ（ｘ）をベキとする指数関数を作ることにより、第１の指数関数ｆ（α）ｇ（ｘ）を提供するステップと、
ｉｉ）第１の通信端末において、第１のランダム整数ｘと第１の機密鍵ａとを組み合わせるために、第１のランダム整数ｘ、第１の記指数関数ｆ（α）ｇ（ｘ）、及び第１の秘密鍵ａから第１の署名ｓＡを生成して、該第１の署名を該第１の通信端末に属する秘密の署名として保持するステップと、
ｉｉｉ）第１の通信端末から、第２の通信端子に向けて、第１の指数関数ｆ（α）ｇ（ｘ）を含むメッセージを送るステップと、
ｉｖ）第１の通信端末において、第２の公開鍵ｐＢと第１の署名ｓＡとから第１のセッション鍵Ｋを計算するステップと、
ｖ）第２の通信端末において、第１の通信端末の公開鍵ｐＡと、メッセージ内の情報とを用いて、第１のセッション鍵Ｋに対応する第２のセッション鍵Ｋ’を計算するステップと
からなることを特徴とする方法。
【請求項２７】
請求項２６記載の方法において、第２の通信端末は、第１の指数関数ｆ（α）ｇ（ｘ）と第２の通信端末の秘密鍵ｂとを組み合わせることにより、第２のセッション鍵Ｋ’を生成することを特徴とする方法。
【請求項２８】
請求項２６又は２７記載の方法において、第１の通信端末は、第２の通信端末の第２の公開鍵ｐＢの関数を第１の署名ｓＡの関数で指数化することにより、セッション鍵Ｋを計算することを特徴とする方法。
【請求項２９】
請求項２６〜２８いずれかに記載の方法において、第１の通信端末の第１の署名ｓＡは、ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）であり、第２のセッション鍵Ｋ’は、Ｋ’＝（ｒＡ（ｐＡ）−ｒＡ・ｐＡ）ｂであることを特徴とする方法。
【請求項３０】
通信チャネル（１４）を介して第１及び第２の通信端末の間で情報を交換することを可能にするために、公開鍵通信システムにおいて、第１及び第２の通信端末の間でセッション鍵Ｋを搬送する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元αとこれら秘密鍵とからそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ａ）第１の通信端末において、第１のランダム整数ｘが選択され、該ランダム整数ｘと生成元αとから第１の値ｒＡを計算するステップと、
ｂ）第１の通信端末において、第１のランダム整数ｘと、第１の値ｒＡと、第１の秘密鍵ａとから第１の署名ｓＡを生成して、第１のランダム整数及び第１の秘密鍵ａを組み合わせるステップと、
ｃ）第１の通信端末において、第１のランダム整数ｘと第２の通信端末に属する公開情報とから、第２の通信端末によって計算可能であるセッション鍵Ｋを計算するステップと、
ｄ）第１の通信端末から、第２の通信端子に向けて、第１の値ｒＡ及び第１の署名ｓＡを含むメッセージを送るステップと
からなることを特徴とする方法。
【請求項３１】
請求項３０記載の方法において、第１の通信端末が、第２の通信端末からランダム・ビット・ストリングｋを受信するステップを備え、該ステップは、セッション鍵Ｋと該セッション鍵Ｋで排他的論理和されたビット・ストリングｋとでメッセージを暗号化して、メッセージを暗号化するための短命鍵（ｋ＋Ｋ）を設定する前に、実行されることを特徴とする方法。
【請求項３２】
通信チャネル（１４）を介して第１及び第２の通信端末の間で情報を交換することを可能にするために、公開鍵通信システムにおいて、第１及び第２の通信端末の間でセッション鍵Ｋを搬送する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元αとこれら秘密鍵とからそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ａ）第２の通信端末において、第１の通信端末から、第１の値ｒＡと第１の署名ｓＡとを受信するステップであって、第１の値ｒＡは、第１の通信端末において、第１のランダム整数ｘと生成元αとから計算され、第１の署名ｓＡは、第１の通信端末において、第１のランダム整数ｘと、第１の値ｒＡと、第１の秘密鍵ａとから生成されたものである、ステップと、
ｂ）第２の通信端末において、生成元、第１の署名ｓＡ、第１の値ｒＡ、及び第１の通信端末に属する公開鍵を用いて生成された値が、第１の通信端末から受信した第１の値ｒＡと等しいかどうかを判定するステップと、
ｃ）第２の通信端末において、該通信端末に属する秘密情報と第１の値ｒＡとからセッション鍵Ｋを計算するステップであって、該通信端末に属する秘密情報は、該通信端末に属する公開情報に関連しており、セッション鍵Ｋは、第１の通信端末においても計算可能である、ステップと
からなることを特徴とする方法。
【請求項３３】
請求項３２記載の方法において、第２の通信端末が、第１の通信端末にランダム・ビット・ストリングｋを送信するステップを備え、該ステップは、セッション鍵Ｋと該セッション鍵Ｋで排他的論理和されたビット・ストリングｋとでメッセージを暗号化して、メッセージを暗号化するための短命鍵（ｋ＋Ｋ）を設定する前に、実行されることを特徴とする方法。
【請求項３４】
請求項３０〜３３いずれかに記載の方法において、第１の値ｒＡは、生成元αを含む関数ｆ（α）を第１のランダム整数ｘをベキとする指数関数とすることにより計算されることを特徴とする方法。
【請求項３５】
請求項３４記載の方法において、生成元αを含む関数ｆ（α）は、生成元αそのものであることを特徴とする方法。
【請求項３６】
請求項３０〜３５いずれかに記載の方法において、第１の署名ｓＡは、ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）であることを特徴とする方法。
【請求項３７】
請求項３２〜３６いずれかに記載の方法において、第２の通信端末に属する公開情報は、第２の公開鍵ｐＢであり、第１の通信端末に属する公開情報は、第１の公開鍵ｐＡであり、第２の通信端末に属する秘密情報は、第２の秘密鍵ｂであることを特徴とする方法。
【請求項３８】
請求項３２、３３又は３７記載の方法において、第２の通信端末によって生成され判定された値は、αｓＡ（ｐＡ）ｒＡ・αａであることを特徴とする方法。
【請求項３９】
請求項３８記載の方法において、第２の通信端末によって計算されたセッション鍵Ｋは、（ｒＢ）ｂであることを特徴とする方法。
【請求項４０】
公開鍵データ通信システムにおいて、第１及び第２の通信端末間でセッション鍵を搬送して、これら通信端末の間で通信チャネルを介して情報を通信するための共通鍵を設定する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元α及びこれら秘密鍵からそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ｉ）第１の通信端末において、第１のランダム整数ｘが選択され、生成元αを含む第１の関数ｆ（α）のｇ（ｘ）をベキとする指数関数を作ることにより、第１の指数関数ｆ（α）ｇ（ｘ）を提供するステップと、
ｉｉ）第１の通信端末において、第１のランダム整数ｘと第１の機密鍵ａとを組み合わせるために、第１のランダム整数ｘ、第１の指数関数ｆ（α）ｇ（ｘ）、及び第１の秘密鍵ａから第１の署名ｓＡを生成して、該第１の署名を該第１の通信端末に属する秘密の署名として保持するステップと、
ｉｉｉ）第１の通信端末から、第２の通信端子に向けて、第１の指数関数ｆ（α）ｇ（ｘ）を含むメッセージを送るステップと、
ｉｖ）第１の通信端末において、第２の公開鍵ｐＢと第１の署名ｓＡとからセッション鍵Ｋを計算するステップであって、該セッション鍵Ｋは、第２の通信端末においても、第１の公開鍵ｐＡとメッセージ中の情報とを用いて計算可能である、ステップと
からなることを特徴とする方法。
【請求項４１】
請求項４０記載の方法において、第１の通信端末は、セッション鍵Ｋを、第２の公開鍵ｐＢの関数を第１の署名ｓＡで指数化することにより計算することを特徴とする方法。
【請求項４２】
請求項４０又は４１記載の方法において、第１の署名ｓＡは、ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）であることを特徴とする方法。
【請求項４３】
公開鍵データ通信システムにおいて、第１及び第２の通信端末間でセッション鍵を搬送して、これら通信端末の間で通信チャネルを介して情報を通信するための共通鍵を設定する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元α及びこれら秘密鍵からそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ｉ）第２の通信端末において、第１の通信端末から、第１の値ｒＡを含んでいるメッセージを受信するステップであって、第１の値ｒＡは、第１の通信端末において、第１のランダム整数ｘと生成元αとから計算されたものである、ステップと、
ｉｉ）第２の通信端末において、第１の値ｒＡ、第１の公開鍵ｐＡ、該通信端末に属する秘密情報から、セッション鍵Ｋを計算するステップであって、該通信端末に属する秘密情報は、該通信端末に属する公開情報に関連しており、セッション鍵は、第１の通信端末においても、第２の公開鍵ｐＢを用いて計算可能である、ステップと
からなることを特徴とする方法。
【請求項４４】
請求項４３記載の方法において、第２の通信端末に属する秘密情報は、第２の秘密鍵ｂであり、第２の通信端末に属する公開情報は、第２の公開情報ｐＢであることを特徴とする方法。
【請求項４５】
請求項４３又は４４記載の方法において、第２の通信端末は、セッション鍵Ｋを、Ｋ＝（ｒＡ（ｐＡ）−ｒＡ・ｐＡ）ｂによって計算することを特徴とする方法。
【請求項４６】
公開鍵暗号化を採用しているデータ通信システムにおいて、第１及び第２の通信端末間で鍵を搬送して、これら通信端末の間で通信チャネルを介して情報を通信するための共通鍵を設定する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元α及びこれら秘密鍵からそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ｉ）第１の通信端末において、第１のランダム整数ｘが選択され、生成元αを含む第１の関数ｆ（α）のｇ（ｘ）をベキとする指数関数を作ることにより、第１の指数関数ｆ（α）ｇ（ｘ）を提供するステップと、
ｉｉ）第１の通信端末において、第１のランダム整数ｘと第１の秘密鍵ａとを組み合わせるために、第１のランダム整数ｘ、第１の指数関数ｆ（α）ｇ（ｘ）、及び第１の秘密鍵ａから第１の署名ｓＡを生成するステップと、
ｉｉｉ）第１の通信端末において、第２の通信端末に、第１の指数関数ｆ（α）ｇ（ｘ）を送信するステップと、
ｉｖ）第１の通信端末において、第２の通信端末から、第２の指数関数ｆ’（α）ｇ（ｙ）を含んでいる情報を受信するステップであって、第２の指数関数ｆ’（α）ｇ（ｙ）は、第２の通信端末において、第２のランダム整数ｙが選択され、生成元αを含む関数ｆ’（α）のｇ（ｙ）をベキとする指数関数を作ることにより生成されたものである、ステップと、
ｖ）第１の通信端末において、第２の通信端末によって公開された情報を、第１の通信端末に属する秘密情報で指数化することによって、セッション鍵Ｋを構築するステップであって、第１の通信端末によって構築されたセッション鍵Ｋは、第２の通信端末においても、第１の通信端末によって公開された情報を、第２の通信端末に属する秘密情報で指数化することにより計算可能である、ステップと
からなることを特徴とする方法。
【請求項４７】
請求項４６記載の方法において、第１の通信端末から送信されるメッセージは、該通信端末の識別子を含んでおり、第２の通信端末から受信されるメッセージは、該通信端末の識別子を含んでいることを特徴とする方法。
【請求項４８】
請求項４６又は４７記載の方法において、生成元を含んでいる関数ｆ（α）は、生成元αそのものであることを特徴とする方法。
【請求項４９】
請求項４６又は４７記載の方法において、生成元を含んでいる関数ｆ（α）は、第２の公開鍵ｐＢを含んでいることを特徴とする方法。
【請求項５０】
請求項４６、４７又は４８記載の方法において、第１の通信端末の第１の署名ｓＡは、ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）であることを特徴とする方法。
【請求項５１】
請求項４６、４７又は４９記載の方法において、第１の通信端末の第１の署名ｓＡは、ｘ＋ａαａ（ｐＢ）ｘ  ｍｏｄ  （ｐ−１）であることを特徴とする方法。
【請求項５２】
請求項４６〜４８いずれかに記載の方法において、第１の通信端末の第１の署名ｓＡは、ｘｒｘ１−（ｒＡ）ｒｘ１ａαａ  ｍｏｄ  （ｐ−１）であり、ｘ１は、第１の通信端末によって選択された第２のランダム整数であり、ｒｘ１＝αｘ１であることを特徴とする方法。
【請求項５３】
請求項４６〜４９いずれかに記載の方法において、第１の通信端末において、第３のランダム整数ｘ１を選択し、第２の通信端末に、ｒＡ１＝αｘ１なるｒＡ１を送信し、第１の通信端末において、第２の通信端末から、ｒＢ１＝αｙ１なるｒＢ１を受信し、ｙ１は、第２の通信端末によって選択された第４のランダム整数であり、第１の通信端末が、αｘｙ及びαｘ１・ｙ１にそれぞれ等しい一対の鍵ｋ１及びｋ２を計算し、セッション鍵がｋ１及びｋ２の排他的論理和によって生成されることを特徴とする方法。
【請求項５４】
請求項４６〜５３いずれかに記載の方法において、第１の通信端末によって受信されたメッセージは、第２の通信端末によって生成された署名ｓＢを含んでいることを特徴とする方法。
【請求項５５】
請求項５４記載の方法において、該方法はさらに、第１の通信端末において、第２の署名ｓＢ及び第２の指数関数ｆ’（α）ｇ（ｙ）から該第２の指数関数ｆ’（α）ｇ（ｙ）に等しい値を計算し、該計算された値を第２の指数関数ｆ’（α）ｇ（ｙ）と対比することによって、第２の通信端末から受信したメッセージの完全性（インテグリティ）の有効性を評価することにより、セッション鍵を正規なものとして認証するステップを含んでいることを特徴とする方法。
【請求項５６】
請求項４６〜４９いずれかに記載の方法において、第１の署名ｓＡは、第１の指数関数ｆ（α）ｇ（ｘ）から得られた整数ｒａ＊を用いて生成されることを特徴とする方法。
【請求項５７】
請求項５６記載の方法において、第２の通信端末によって公開された情報は、第２の公開鍵ｐＢ、第１の指数関数ｆ（α）ｇ（ｘ）、第２の通信端末の整数ｒｂ＊を組み合わせたものであることを特徴とする方法。
【請求項５８】
請求項５７記載の方法において、生成元αは、乗法群Ｚｐ＊（ｐは素数）の要素であることを特徴とする方法。
【請求項５９】
請求項５６〜５８いずれかに記載の方法において、第１の署名ｓＡは、ｓＡ＝ｘ＋（ｒａ＊）ａ  ｍｏｄ  （ｎ−１）であることを特徴とする方法。
【請求項６０】
請求項５９記載の方法において、セッション鍵Ｋは、Ｋ＝（αｙ（αｂ）ｒｂ＊）ｓＡ  ｍｏｄ  ｐであることを特徴とする方法。
【請求項６１】
請求項５６〜６０いずれかに記載の方法において、生成元αは、ｐを素数とする乗法群Ｚｐ＊の位数ｑ（ｑは素除数）の部分群の要素であることを特徴とする方法。
【請求項６２】
請求項５６又は５７記載の方法において、生成元αは、有限体Ｆｑ上で定義される楕円曲線上の位数ｎの点Ｐであり、該楕円曲線上のスカラ乗算によって、累乗が実行されることを特徴とする方法。
【請求項６３】
請求項６２記載の方法において、整数ｒａ＊は、第１の指数関数ｆ（α）ｇ（ｘ）の座標のビット・ストリングスであることを特徴とする方法。
【請求項６４】
請求項６２又は６３記載の方法において、第１の署名ｓＡは、
ｓＡ＝（ｘ＋（ｒａ＊）ａ）  ｍｏｄ  ｎ
であることを特徴とする方法。
【請求項６５】
請求項６４記載の方法において、第１の通信端末において、セッション鍵Ｋは、
Ｋ＝ｓｂ（ｒａ＋（ｒａ＊）Ｐａ）
によって計算されることを特徴とする方法。
【請求項６６】
請求項４６〜４８いずれかに記載の方法において、第１の通信端末が、第１の署名ｓＡを自身に属する秘密のものとして保持することを特徴とする方法。
【請求項６７】
請求項６６記載の方法において、第１の署名ｓＡは、
ｓＡ＝ｘ＋ｒＡａαａ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項６８】
請求項６６記載の方法において、第１の署名ｓＡは、
ｓＡ＝ｘ＋ａ（ｐＢ）ｘ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項６９】
請求項６６記載の方法において、第１の署名ｓＡは、ｓＡ＝ｘｒＡ＋ａαａ
であることを特徴とする方法。
【請求項７０】
請求項６６記載の方法において、第１の署名ｓＡは、ｓＡ＝ｘαａ＋ａｒＡであることを特徴とする方法。
【請求項７１】
請求項１〜７０いずれかに記載の方法を実行することを特徴とするシステム。
【請求項７２】
コンピュータにより読み取り可能な記憶媒体であって、請求項１〜７０いずれかに記載の方法を実行するためのプログラムを記憶したことを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号鍵の転送及び認証のための鍵一致（key agreement）プロトコルに関する。
【背景技術】
【０００２】
情報の交換の際にプライバシを維持するために、鍵を用いてデータを暗号化することが、広く知られている。この鍵は、通信端末がメッセージを暗号化及び復号化できるが介入者にはメッセージの内容を判断できないように、選択されなければならない。
秘密鍵暗号プロトコルでは、通信端末は、彼らにとって秘密である共通鍵を共有（share）する。このためには、この鍵が通信端末の間で一致しており、この鍵の秘密性を維持するために条項（provision）が作成され、基礎となる安全性が万一危険にさらされた場合には、鍵の交換がなされることが要求される。
【０００３】
公開鍵暗号プロトコルは、１９７６年にDiffie-Hellmanによって最初に提案され、すべての潜在的な通信端末に利用可能とされている公開鍵と、意図された受信者にだけ知られている秘密鍵（private key）とを用いる。公開鍵と秘密鍵とは、受信者の公開鍵を用いて暗号化されたメッセージは、秘密鍵を用いて容易に復号化できるが、秘密鍵は、平文（plaintext）、暗号文（ciphertext）及び公開鍵の知識からは導くことはできないような、相互関係になっている。
【０００４】
鍵の確立（establishment）は、二人以上の当事者が、セッション（session）鍵と称される、共有される秘密鍵（secret key）を確立するプロセスである。セッション鍵は、プライバシなどの何らかの暗号上の目的を達成するために、後で用いられる。鍵一致プロトコルには、２つの種類が存在する。すなわち、鍵が第１の当事者によって作成され、第２の当事者に安全に送信されるという鍵輸送（transport）プロトコルと、両方の当事者が、共有される秘密鍵を共同して確立する情報を出し合う鍵一致プロトコルと、である。当事者の間で必要となるメッセージ交換の数は、パス数（number of passes）と称される。鍵確立プロトコルは、ある当事者が、特別に識別された第２の当事者以外のどの当事者もセッション鍵の値を知ることを許されないことが保証されている場合に、「内在的」（implicit）鍵認証（又は、単に、鍵認証）を提供すると称される。内在的鍵認証の性質は、第２の当事者が実際のセッション鍵を有していることを必ずしも意味しない。次に、鍵確立プロトコルは、ある当事者が、特別に識別された第２の当事者が特定のセッション鍵を実際に所持していることを保証されている場合には、鍵確認（confirmation）を提供すると称される。プロトコルに関係する両方の当事者に認証が提供される場合には、鍵認証は、相互的（mutual）と称され、一人の当事者にだけ提供される場合には、認証は、一方的（unilateral）と称される。
【０００５】
内在的な鍵認証を提供すると主張する提案は、これまでに、いくつかなされている。
例としては、鍵一致に関する、Nyberg-Rueppelによる１パス（one-pass）プロトコル、 Matsumoto-Takashima-Imai (MTI)及びGoss and Yacobiによる２パス・プロトコルがある。
従来の提案は、共通鍵を確立するための通信端末の間の送信が安全であり、侵入者がセッション鍵をリトリーブし暗号文を復号化することはでｆきないことを保証している。このようにして、資金の移動などの注意を要するトランザクションに対する安全性が提供されている。
【０００６】
例えば、MTI/A0鍵一致プロトコルでは、二人の通信端末に知られている、共有される秘密鍵を、次のようにして確立している。
１．当初の、一時的な（one-time）セットアップの間に、鍵の発生と公開とが、適切なシステム・プライム（system prime）ｐと生成元（generator）α∈Ｚ＊ｐとを真正であることが補償されるように、選択され公開される。通信端末Ａは、長期の秘密鍵として１＜ａ＜ｐ−１であるランダムな整数ａを選択し、長期の公開鍵ｚＡ＝αａ  ｍｏｄ  ｐを計算する。Ｂも、同様のｂとｚＢとを生成する。ＡとＢとは、相互の長期公開鍵の認証されたコピーへのアクセスを有することになる。
【０００７】
２．このプロトコルは、次のメッセージの交換を要求する。すなわち、
ＡからＢ：αｘ  ｍｏｄ  ｐ      （１）
ＢからＡ：αｙ  ｍｏｄ  ｐ      （２）
ｘ及びｙの値は、その送信の間は安全に保たれるが、その理由は、ｐが十分に大きくとられていれば、αの値と指数化とが知られているとしても、指数を決定するのは実際的ではないからである。
【０００８】
３．このプロトコルを実現するには、次のステップが、共有されている鍵が要求される度に実行される。
（ａ）Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、Ｂに向けて、メッセージ（１）、すなわち、αｘ  ｍｏｄ  ｐを送る。
（ｂ）Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、Ａに向けて、メッセージ（２）、すなわち、αｙ  ｍｏｄ  ｐを送る。
（ｃ）Ａは、鍵Ｋ＝（αｙ）ａｚＢｘ  ｍｏｄ  ｐを計算する。
（ｄ）Ｂは、鍵Ｋ＝（αｘ）ｂｚＡｙ  ｍｏｄ  ｐを計算する。
（ｅ）両者は、鍵Ｋ＝αｂｘ＋ａｙを共有する。
【０００９】
鍵Ｋを計算するためには、Ａは、自分の秘密鍵ａとランダムな整数ｘとを使わなければならない。これらは、共に、Ａ本人だけに知られているものである。同様にして、Ｂは、セッション鍵Ｋを計算するためには、自分の秘密鍵ｂとランダムな整数ｙとを使わなければならない。秘密鍵ａ及びｂが、危険にさらされていないと仮定すると、侵入者は、他方の通信端末と同一のセッション鍵を生成することはできない。従って、任意の暗文は、どちらの通信端末にも復号化が不可能である。
【００１０】
従って、このプロトコル及び関連するプロトコルは、鍵確立には十分なものであると考えられてきたし、従来型の盗聴や、中間者（man-in-the-middle）による攻撃に対して抵抗できると考えられてきた。
状況によっては、相手方が、一方の通信端末を他方の通信端末であるとミスリードするのが効果的である。
そのような攻撃では、アクティブな相手方、すなわち、侵入者Ｅは、ＡとＢとの間で交換されるメッセージを修正し、その結果として、Ｂは、Ｅと鍵Ｋを共有していると信じ、他方で、Ａは、同じ鍵をＢと共有していると信じることになる。ＥがＫの値を知らない場合であっても、通信端末の識別（ＩＤ）に関する偽の情報が、有用となる。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
そのような攻撃が成功するであろう実際的なシナリオは、次のようなものである。Ｂは、銀行の支店であり、Ａは、口座保持者であると仮定する。銀行の本部によって証明書が発行され、その証明書の中には、保持者の口座情報が書かれている。資金の電子的支払い（デポジット）のためのプロトコルは、相互認証された鍵一致を介して、銀行の支店との鍵の交換であると仮定する。Ｂがいったん送信者を認証すると、暗号化された資金がその証明書の口座番号に払い込まれる。それ以上の認証が暗号化された支払いメッセージにおいてなされない場合（これは、帯域幅を節約するためになされるかもしれない）には、支払いは、Ｅの口座になされる。
本発明の目的は、上述の短所が回避される又は解消されるようなプロトコルを提供することである。
【課題を解決するための手段】
【００１２】
従って、本発明によると、１対の通信端末Ａ及びＢが相互に情報を交換することを認証する方法であって、前記通信端末は、それぞれが、秘密鍵ａ及びｂと、生成元αと前記秘密鍵ａ及びｂのそれぞれとから導かれた公開鍵ｐＡ及びｐＢと、を有している方法が提供される。この方法は、
ｉ）前記通信端末の第１の者Ａが、第１のランダムな整数ｘを選択し、前記生成元を含む関数ｆ（α）のｇ（ｘ）をベキとする指数関数を作ることにより、第１の指数関数ｆ（α）ｇ（ｘ）を提供するステップと、
ｉｉ）前記第１の通信端末Ａが、前記ランダムな整数ｘと前記指数関数ｆ（α）ｇ（ｘ）とから第１の署名ｓＡを生成するステップと、
ｉｉｉ）前記第１の通信端末Ａが、第２の通信端末Ｂに向けて、前記第１の指数関数ｆ（α）ｇ（ｘ）と署名ｓＡとを含むメッセージを送るステップと、
ｉｖ）前記通信端末Ｂが、第２のランダムな整数ｙを選択し、前記生成元を含む関数ｆ’（α）のｇ（ｙ）をベキとする指数関数を作ることにより、第２の指数関数ｆ’（α）ｇ（ｘ）と、前記第２の整数ｙと前記第２の指数関数ｆ（α）ｇ（ｘ）とから得られるｓＢとを提供するステップと、
ｖ）前記第２の通信端末Ｂが、第１の通信端末Ａに向けて、前記第２の指数関数ｆ’（α）ｇ（ｙ）と前記署名ｓＢとを含むメッセージを送るステップと、
ｖｉ）前記通信端末のそれぞれが、受け取ったメッセージの中の前記署名と前記指数関数とから、前記指数関数と等しい値を計算し、前記計算された値と前記送信された値とを比較することによって、自分たちが受け取ったメッセージの真正を検証するステップと、
ｖｉｉ）前記通信端末Ａ及びＢのそれぞれが、前記他方の通信端末によって彼ら自身にとって秘密である前記ランダムな整数を用いて、公開された情報を指数化することによって、セッション鍵を構成するステップと、を含む。
【００１３】
従って、侵入者Ｅが自らの公開鍵ｐＥ＝αａｃをメッセージの一部として送信の中に入れることはできるが、Ｂは、メッセージを認証する際には、ｐＡではなくｐＥを用いることになる。従って、指数関数の計算され送信された値は、対応しない。
【図面の簡単な説明】
【００１４】
【図１】本発明にかかるデータ通信システムの概略図である。
【発明を実施するための実施形態】
【００１５】
本発明の実施例を次の添付した図面を参照することによって、これから説明することにする。
図１は、データ通信システムの概略図である。図１を参照すると、通信端末Ａ及び通信端末Ｂとして表される１対の通信端末１０、１２が、通信チャネル１４上で情報を交換する。暗号ユニット１６、１８が、通信端末１０、１２とチャネル１４とのそれぞれの間に配置されている。鍵２０は、暗号ユニット１６、１８のそれぞれに関連し、それぞれのユニット１６、１８とそれぞれの通信端末１０、１２との間で運ばれる平文を、チャネル１４上で運ばれる暗文に変換する。
【００１６】
動作においては、Ａの通信端末１０によって生成されるメッセージは、ユニット１６によって、鍵２０を用いて暗号化され、チャネル１４上の暗文として、ユニット１８まで送信される。
鍵２０は、ユニット１８において暗文に作用して、Ｂの通信端末１２のために平文のメッセージを生成する。鍵２０が対応する場合には、通信端末１２によって受け取られたメッセージは、通信端末１０によって送られたものである。
図１に示されたシステムが動作するためには、鍵２０が同一であり、従って、公開的な態様で情報の移動を可能にする鍵一致（agreement）プロトコルが確立されていることが必要である。そのような鍵の生成には多数のプロトコルが利用可能であり、また、Diffie-Hellman鍵交換の変形も存在する。その目的は、当事者Ａ及びＢが秘密セッション鍵Ｋを確立することである。
【００１７】
これらのプロトコルのためのシステム・パラメータは、素数ｐと乗法群Ｚ＊ｐの生成元αとである。通信端末Ａは、秘密鍵ａと、公開鍵ｐＡ＝αａとを有する。通信端末Ｂは、秘密鍵ｂと、公開鍵ｐＢ＝αｂとを有する。以下で例を挙げるプロトコルでは、ｔｅｘｔＡは、当事者Ａを識別する情報のストリングを意味する。他方の当事者Ｂが通信端末Ａの公開鍵の真正のコピーを有しており、更に、ｔｅｘｔＡがＡの信用のおけるセンターによって発行された公開鍵証明書を含む場合には、通信端末Ｂは、その信用のおけるセンターの公開鍵の真正のコピーを用いて、通信端末Ａの証明書を検証でき、従って、通信端末Ａの公開鍵の真正のコピーを得ることができる。
【００１８】
以下のそれぞれの例では、侵入者Ｅは、ＡからのメッセージがＥ自身から生じたものとして識別されることを望んでいると仮定する。これを達成するには、Ｅは、１≦ｅ≦ｐ−２であるランダムな整数ｅを選択し、ｐＥ＝（ｐＡ）ｅ＝αａｅ  ｍｏｄ  ｐを計算し、これがＥ自身の公開鍵であることを証明させる。Ｅは、ｅを知ってはいるが、指数ａｅは知らない。ｔｅｘｔＡをｔｅｘｔＥによって代替することによって、通信端末Ｂは、メッセージがＡからではなくＥからのものであると考え、Ｅの公開鍵を用いてセッション鍵Ｋを生成する。Ｅはまた、Ｂからのメッセージを中間奪取（インターセプト）し、その秘密のランダムな整数ｅを用いて、その内容を修正する。Ａは、次に、その情報を用いて、ＡがＢと通信できるようにする同じセッション鍵を生成する。
【００１９】
侵入者ＥがＢに、ＢはＥと通信しているということを信じさせようとしているのを妨害するには、次のプロトコルが採用される。
このプロトコルの目的は、当事者Ａ及びＢがセッション鍵Ｋを確立することである。ここで挙げたプロトコルは、役割対称的（role-symmetric）であり、対話的（interactive）ではない。
このプロトコルのためのシステム・パラメータは、素数ｐと乗法群Ｚ＊ｐの生成元αとである。通信端末Ａは、秘密鍵ａと、公開鍵ｐＡ＝αａとを有する。通信端末Ｂは、秘密鍵ｂと、公開鍵ｐＢ＝αｂとを有する。
【００２０】
第１のプロトコル
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒＡ＝αｘと、署名ｓＡ＝ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒＡ，ｓＡ，ｔｅｘｔＡ｝を送る。
２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、ｒＢ＝αｙと、署名ｓＢ＝ｙ−ｒＢｂαｂ  ｍｏｄ  （ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒＢ，ｓＢ，ｔｅｘｔＢ｝を送る。
３．Ａは、αｓＢ（ｐＢ）ｒＢ・αｂを計算し、これが、ｒＢに等しいことを検証する。Ａは、次に、セッション鍵Ｋ＝（ｒＢ）ｘ＝αｘｙを計算する。
４．Ｂは、αｓＡ（ｐＡ）ｒＡ・αａを計算し、これが、ｒＡに等しいことを検証する。Ｂは、次に、セッション鍵Ｋ＝（ｒＡ）ｙ＝αｘｙを計算する。
【００２１】
Ｅが、ｔｅｘｔＡをｔｅｘｔＢに交換する場合には、Ｂは、ｒＡの送信された値には対応しないαｓＡ（ｐＥ）ｒＡαａを計算する。Ｂは、従って、侵入者Ｅに関する警告を受け、別のセッション鍵を開始することになる。
第１のプロトコルの短所は、完全な前方向の秘密性（守秘性）（perfect forward secrecy）が得られないことである。すなわち、相手側が当事者Ａの長期の秘密鍵ａを知る場合には、この相手側は、Ａの過去のセッション鍵すべてを導き出せることになる。完全な前方向の秘密性は、プロトコル１を次のようにして修正することによって達成される。
【００２２】
修正された第１のプロトコル
ステップ１では、Ａはまた、αｘ１をＢに送る。ここで、ｘ１は、Ａによって生成された第２のランダムな整数である。同様にして、上述のステップ２では、Ｂはまた、αｙ１をＡに送る。ここで、ｙ１は、ランダムな整数である。Ａ及びＢは、鍵Ｋ＝αｘｙ＋αｘ１・ｙ１を計算する。
第１のプロトコルの別の短所は、相手側がＡの秘密のランダムな整数ｘを知る場合には、この相手側は、当事者Ａの長期の秘密鍵を、方程式ｓＡ＝ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）から求めることができる点である。このプロトコルのうまく設計された実現例では、秘密の整数の開示は回避されるので、この短所は、基本的に理論的性格を有するものである。
【００２３】
第２のプロトコル
次に述べる第２のプロトコルは、これら２つの短所を解決する。
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、（ｐＢ）ｘと、αｘと署名ｓＡ＝ｘ＋ａαａ（ｐＢ）ｘ  ｍｏｄ  （ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛αｘ，ｓＡ，ｔｅｘｔＡ｝を送る。
２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、（ｐＡ）ｙと、αｙと署名ｓＢ＝ｙ＋ｂαｂ（ｐＡ）ｙ  ｍｏｄ  （ｐ−１）と、を計算する。Ｂは、Ａに向けて、｛αｙ，ｓＢ，ｔｅｘｔＢ｝を送る。
３．Ａは、（αｙ）ａを計算して、αｓＢ（ｐＢ）−αｂ・αａｙ＝αｙであることを検証する。Ａは、次に、セッション鍵Ｋ＝αａｙ（ｐＢ）ｘを計算する。
４．Ｂは、（αｘ）ｂを計算して、αｓＡ（ｐＡ）−αａ・αｂｘ＝αｘであることを検証する。Ａは、次に、セッション鍵Ｋ＝αｂｙ（ｐＡ）ｙを計算する。
【００２４】
第２のプロトコルが第１のプロトコルとの比較で優れているのは、それが、完全な前方向の秘密性（forward secrecy）を提供するからである。秘密であるランダムな整数ｘの開示によって、相手側が秘密鍵ａを知ることができるのではあるが、これは実際上問題ではない。なぜならば、Ａは、自分がこのプロトコルのステップ１においてｘを用いた直後に、ｘを廃棄することができるからである。
【００２５】
ＡがＢの公開鍵の認証されたコピーを有していない場合には、Ｂは、自らの鍵の真正（certified）なコピーを、プロトコルの開始時に、Ａに送信しなければならない。この場合には、第２のプロトコルは、３パス・プロトコルである。
量ｓＡは、値αｘに対して、Ａの署名として機能する。この署名は、当事者Ｂだけに確認が可能であるという新規な性質を有している。このアイデアは、ElGamalライクな署名方式のすべてに一般化できる。
上述の第１及び第２のプロトコルは、帯域幅の要件と、鍵一致の計算上の効率とを向上させるように修正が可能である。修正されたプロトコルは、次に、プロトコル１’及びプロトコル２’として、示してある。それぞれの場合に、Ａ及びＢは、共通鍵αｓＡ・ｓＢを共有している。
【００２６】
プロトコル１’
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒＡ＝αａと、ｓＡ＝ｘ＋ｒＡａαａ  ｍｏｄ  （ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒＡ，ｔｅｘｔＡ｝を送る。
２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、ｒＢ＝αｙと、ｓＢ＝ｙ＋ｒＢｂαｂ  ｍｏｄ  （ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒＢ，ｔｅｘｔＢ｝を送る。
３．Ａは、αｓＡ・ｓＢに等しいＫ＝（ｒＢ（ｐＢ）ｒＢ・αｂ）ｓＡを計算する。
４．Ｂは、αｓＡ・ｓＢに等しいＫ＝（ｒＡ（ｐＡ）ｒＡ・αａ）ｓＢを計算する。
このようにして、Ａ及びＢは、共通鍵を共有するが、署名ｓＡ及びｓＢは、送信される必要がないことに注意すべきである。
【００２７】
プロトコル２’
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、（ｐＢ）ｘと、αｘと署名ｓＡ＝ｘ＋ａ（ｐＢ）ｘ  ｍｏｄ  （ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛αｘ，ｔｅｘｔＡ｝を送る。
２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、（ｐＡ）ｙと、αｙと署名ｓＢ＝ｙ＋ｂ（ｐＡ）ｙ  ｍｏｄ  （ｐ−１）と、を計算する。Ｂは、Ａに向けて、｛αｙ，ｔｅｘｔＢ｝を送る。
３．Ａは、（αｙ）ａと、Ｋ＝（αｙ（ｐＢ）αｂ・αａｙ）ｓＡを、すなわち、αｓＡ・ｓＢを計算する。
４．Ｂは、（αｘ）ｂと、Ｋ＝（αｘ（ｐＡ）αａ・αｂｘ）ＳＢを、すなわち、αｓＡ・ｓＢを計算する。
従って、やはり、ｓＡ及びｓＢの送信が回避された。
Ａ及びＢがセッション鍵Ｋを確立するために、別のプロトコルが利用可能である。
【００２８】
第３のプロトコル
このプロトコルに対するシステム・パラメータは、乗法群Ｚ＊ｐの素数ｐと生成元αである。ユーザＡは、秘密鍵ａと公開鍵ｐＡ＝αａとを有している。ユーザＢは、秘密鍵ｂと公開鍵ｐＢ＝αｂとを有している。
１．Ａは、１≦ｘ，ｘ１≦ｐ−２である２つのランダムな整数ｘ，ｘ１を選び、ｒｘ１＝αｘ１と、ｒＡ＝αｘと、（ｒＡ）ｒｘ１とを計算し、更に、署名ｓＡ＝ｘｒｘ１−（ｒＡ）ｒｘ１ａαａ  ｍｏｄ（ｐ−１）を計算する。Ａは、Ｂに向けて、｛ｒＡ，ｓＡ，αｘ１，ｔｅｘｔＡ｝を送る。
２．Ｂは、１≦ｙ，ｙ１≦ｐ−２である２つのランダムな整数ｙ，ｙ１を選び、ｒｙ１＝αｙ１と、ｒＢ＝αｙと、（ｒＢ）ｒｙ１とを計算し、更に、署名ｓＢ＝ｙｒｙ１−（ｒＢ）ｒｙ１ｂ  ｍｏｄ（ｐ−１）を計算する。Ｂは、Ａに向けて、｛ｒＢ，ｓＢ，αｙ１，ｔｅｘｔＢ｝を送る。
３．Ａは、αｓＢ（ｐＢ）（ｒＢ）ｒｙ１を計算し、これが、（ｒＢ）ｒｙ１に等しいことを確認する。Ａは、セッション鍵Ｋ＝（αｙ１）ｘ１＝αｘ１・ｙ１を計算する。
４．Ｂは、αｓＡ（ｐＡ）（ｒＡ）ｒｘ１を計算し、これが、（ｒＡ）ｒｘ１に等しいことを確認する。Ｂは、セッション鍵Ｋ＝（αｘ１）ｙ１＝αｘ１・ｙ１を計算する。
これらのプロトコルでは、（ｒＡ，ｓＡ）は、Ａだけがメッセージｒｘ１に署名できるという性質を有するｒｘ１の署名であると考えることができる。
【００２９】
鍵輸送プロトコル
上述のプロトコルによれば、セッション鍵の確立と認証とが可能になる。Ａがセッション鍵を当事者Ｂに輸送（transport）することを可能にするプロトコルを確立することが望まれる。そのようなプロトコルを次に述べる。
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒＡ＝αｘと、署名ｓＡ＝ｘ−ｒＡａαａ  ｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒＡ，ｓＡ，ｔｅｘｔＡ｝を送る。
２．Ｂは、αｓＡ（ｐＡ）ｒＡ・αａを計算し、この量が、ｒＡに等しいことを検証する。Ｂは、次に、セッション鍵Ｋ＝（ｒＡ）ｂを計算する。
【００３０】
修正された鍵輸送プロトコル
上述のプロトコルは、署名ｓＡを送信する必要をなくすことによって、帯域幅を減少させるように修正が可能である。
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒＡ＝αｘと、署名ｓＡ＝ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）と、を計算する。Ａは、更に、Ｋ＝（ｐＢ）ｓＡを計算して、Ｂに向けて、｛ｒＡ，ｔｅｘｔＡ｝を送る。
２．Ｂは、αｓＡ（ｐＡ）ｒＡ・αａを計算し、この量が、ｒＡに等しいことを検証する。Ｂは、次に、セッション鍵Ｋ＝（αｘ（ｐＡ）−ｒＡ・αａ）ｂ＝αｂ・ｓＡを計算する。
すべての１パス鍵輸送プロトコルは、次に述べるリプレイの問題を有する。１パス鍵輸送プロトコルを用いてセッション鍵ＫをＡからＢへ、このセッション鍵を用いて暗号化された何らかのテキストと共に送信することを考える。Ｅが、ＡからＢへの送信を記録すると仮定する。もし、Ｅが、後に、Ｂの復号化装置へのアクセス（ただし、Ｂの秘密鍵など、その装置の内部的な内容へのアクセスではない）を、その装置への送信をリプレイすることによって得ることになる場合には、Ｅは、元のテキストを回復することができる。この状況では、Ｅは、セッション鍵を知らない。
【００３１】
このリプレイによるアタックは、タイムスタンプの使用などの、通常の方法によって失敗させることができる。しかし、Ｂの計算資源が限定されていて、それぞれのセッションの開始時に、Ｂがランダムなビット・ストリングｋをＡに送信する方がより適切であるようなこともある。テキストを暗号化するのに用いられるセッション鍵は、その場合には、ｋ＋ｋ、すなわち、ｋとｋとのＸＯＲを計算したものとなる。
【００３２】
署名（signing）方程式ｓＡ＝ｘ−ｒＡａαａと、プロトコル２における鍵輸送プロトコルｒＡ＝αｘｂとは、いくつかの変形例で代替することができる。いくつか例を挙げると、次の通りである。
ｒＡ＝ｓＡｘ＋ｚ
ｓＡ＝ｘαａ＋ａｒＡ
ｓＡ＝ｘｒＡ＋Ａαａ
１＝ａｒＡ＋ｘｓＡ
【００３３】
既に述べたプロトコルは、すべて、乗法群Ｚ＊ｐの設定において、説明された。しかし、これらのプロトコルは、離散対数問題が困難を生じさせるように見える任意の有限群において機能するように容易に修正することができる。適切な選択肢としては、有限体の乗法群（特に、有限体ＧＦ（２ｎ））、位数（order）ｑのＺ＊ｐの部分群、有限体上で定義される楕円曲線上の点から成る群などがある。それぞれの場合に、適切な生成元（generator）αを用いて公開鍵を定義する。
【００３４】
上述したプロトコルは、また、直接的な方法で修正して、それぞれのユーザが自分自身のシステム・パラメータｐ及びα（又は、Ｚ＊ｐ以外の群が用いられる場合には、類似のパラメータ）を選択できるような状況を扱えるようにできる。
上述のプロトコルでは、一般形式ｓＡ＝ｘ＋ｒａ・ａ・αａの署名成分が用いられていた。これらのプロトコルは、安全性を損ねることなく、より単純な一般形式ｓＡ＝ｘ＋ｒａ・ａの署名成分を用いるように修正が可能である。
これらのプロトコルの例を、同じ記号（notation）を用いて以下に与えるが、望むのであれば、別の記号を用いてこれらのプロトコルを表現することができることを理解すべきである。
【００３５】
プロトコル１’’
このプロトコルは、乗法群Ｚ＊ｐにおける次の記号を用いて説明される。
ｐは、素数である。
αは、Ｚ＊ｐの生成元である。
ａ及びｂは、当事者Ａ及びＢのそれぞれの長期的な秘密鍵である。
αａ  ｍｏｄ  ｐは、当事者Ａの長期的な秘密鍵である。
αｂ  ｍｏｄ  ｐは、当事者Ｂの長期的な秘密鍵である。
ｘは、Ａによって短期の秘密鍵として選択されるランダムな整数である。
ｒａ＝αｘ  ｍｏｄ  ｐは、当事者Ａの短期の公開鍵である。
ｙは、Ｂによって短期の秘密鍵として選択されるランダムな整数である。
ｒｂ＝αｙ  ｍｏｄ  ｐは、当事者Ａの短期の公開鍵である。
ｒａ＊は、ｒａから導かれる整数である。
ｒｂ＊は、ｒｂから導かれる整数である。
【００３６】
プロトコルを実現するには、次のようにする。
１．Ａは、ｒａをＢに送る。
２．Ｂは、ｒｂをＡに送る。
３．Ａは、ｓＡ＝ｘ＋（ｒａ＊）・ａ  ｍｏｄ  （ｐ−１）を計算する。
４．Ａは、セッション鍵Ｋ＝（αｙ（αｂ）（ｒｂ＊））ｓＡ  ｍｏｄ  ｐを計算する。
５．Ｂは、ｓＢ＝ｙ＋（ｒｂ＊）・ｂ  ｍｏｄ  （ｐ−１）を計算する。
６．Ｂは、セッション鍵Ｋ＝（αｘ（αａ）（ｒａ＊））ｓＢ  ｍｏｄ  ｐを計算する。
７．共有される秘密は、αｓＡ・ｓＢ  ｍｏｄ  ｐである。
このプロトコルでは、待機幅の要件が再び緩和されているが、署名成分は、通信端末の短期及び長期の鍵を組み合わせて、侵入者からの攻撃を禁止している。
【００３７】
このプロトコルは、また、Ｚ＊ｐの部分群を用いても実現できる。この場合には、ｑは、（ｐ−１）の素約数（prime divisor）であり、ｇは、Ｚ＊ｐの中の位数ｐの要素である。
Ａ及びＢの公開鍵は、それぞれが、ｇａ及びｇｂの形式を有し、短期の鍵ｒａ及びｒｂは、ｇｘ及びｇｙの形式を有している。
署名成分であるｓＡ及びｓＢは、ｍｏｄ  ｑで計算され、セッション鍵は、従前のように、ｍｏｄ  ｑで計算される。この場合には、共有の秘密は、ｇｓＡ・ｓＢ  ｍｏｄ  ｐである。
既に述べたように、これらのプロトコルは、Ｚ＊ｐ以外の群においても実現が可能であり、特に、ローバスト（robust）群は、有限体上の楕円曲線上の点から成る群である。このような実現例は、次にプロトコル１’’’として挙げてある。
【００３８】
プロトコル１’’’
次の記号を用いる。
Ｅは、Ｆｑ上で定義される楕円曲線である。
Ｐは、Ｅ（Ｆｑ）内の素数位数の点である。
ｄａ（１＜ｄａ＜ｎ−１）は、当事者Ａの長期の秘密鍵である。
ｄｂ（１＜ｄｂ＜ｎ−１）は、当事者Ｂの長期の秘密鍵である。
Ｑａ＝ｄａＰは、当事者Ａの長期の公開鍵である。
Ｑｂ＝ｄｂＰは、当事者Ｂの長期の公開鍵である。
ｒａ＝ｋＰは、当事者Ａの短期の公開鍵である。
ｋ（１＜ｋ＜ｎ−１）は、当事者Ａの短期の秘密鍵である。
ｍ（１＜ｍ＜ｎ−１）は、当事者Ｂの短期の秘密鍵である。
ｒｂ＝ｍＰは、当事者Ｂの短期の公開鍵である。
ｒａ＊及びｒｂ＊は、ビット・ストリングであり、例えば、ｒａ及びｒｂのｘ座標の８０最下位ビットである。
【００３９】
このプロトコルを実現するには、次のようにする。
１．Ａは、ｒａをＢに送る。
２．Ｂは、ｒｂをＡに送る。
３．Ａは、ｓＡ＝（ｋ＋（ｒａ＊）・ｄａ）  ｍｏｄ  ｎを計算する。
４．Ａは、セッション鍵Ｋ＝ｓＡ（ｒｂ＋（ｒｂ＊）Ｑｂ）を計算する。
５．Ｂは、ｓＢ＝（ｍ＋（ｒｂ＊）ｄｂ）  ｍｏｄ  ｎを計算する。
６．Ｂは、セッション鍵Ｋ＝ｓｂ（ｒａ＋（ｒａ＊）Ｑａ）を計算する。
７．共有される秘密は、ｓａｓｂＰである。
【００４０】
再び、通信端末の間では署名成分ｓＡ及びｓＢを送る必要はないことに注意すべきである。しかし、通信端末の短期及び長期の鍵が成分の形式で組み合わされる。
先の例におけるｘ及びｙに対して、記号ｍを用いているのは、曲線上の点の座標（ｘ，ｙ）との混乱を回避するためである。
【図１】
2010011478.tif 000003
【手続補正書】
【提出日】平成21年9月7日(2009.9.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
公開鍵暗号化を採用しているデータ通信システムにおいて、通信チャネル（１４）を介して第１及び第２の通信端末（Ａ及びＢ）の間で情報を交換することを可能にするために、第１及び第２の通信端末間の鍵を設定する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元αとこれら秘密鍵とからそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ｉ）第１の通信端末（Ａ）において第１のランダム整数ｘが選択され、生成元αを含む第１の関数ｆ（α）のｇ（ｘ）をベキとする指数関数を作ることにより、第１の指数関数ｆ（α）ｇ（ｘ）を提供するステップと、
ｉｉ）第１の通信端末（Ａ）において、第１のランダム整数ｘと第１の機密鍵ａとを組み合わせるために、第１のランダム整数ｘ、第１の指数関数ｆ（α）ｇ（ｘ）、及び第１の秘密鍵ａから第１の署名ｓＡを生成して、該第１の署名を保持するステップと、
ｉｉｉ）第１の通信端末（Ａ）から、第２の通信端子（Ｂ）に向けて、第１の指数関数ｆ（α）ｇ（ｘ）を含むメッセージを送るステップと、
ｉｖ）第２の通信端末（Ｂ）において、第２のランダム整数ｙを選択され、該第２のランダム整数ｙと第２の秘密鍵ｂとを組み合わせるために、生成元αを含む第２の関数ｆ’（α）のｇ（ｙ）をベキとする指数関数を作ることにより、第２の指数関数ｆ’（α）ｇ（ｙ）を提供し、第２のランダム整数ｙ、第２の指数関数ｆ’（α）ｇ（ｙ）、及び第２の秘密鍵ｂから第２の署名ｓＢを生成して、該第２の署名を保持するステップと、
ｖ）第２の通信端末（Ｂ）から、第１の通信端末（Ａ）に向けて、第２の指数関数ｆ’（α）ｇ（ｙ）を含むメッセージを送るステップと、
ｖｉ）第１の通信端末（Ａ）において、第２の通信端末（Ｂ）によって公開された情報を、第１の通信端末に属する秘密情報を用いて指数化することによって、セッション鍵Ｋを構築し、第２の通信端末（Ｂ）において、第１の通信端末（Ａ）によって公開された情報を、第２の通信端末に属する秘密情報を用いて指数化することによって、セッション鍵Ｋを構築するステップと
からなることを特徴とする方法。
【手続補正書】
【提出日】平成21年9月28日(2009.9.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
公開鍵暗号化を採用しているデータ通信システムにおいて、通信チャネル（１４）を介して第１及び第２の通信端末（Ａ及びＢ）の間で情報を交換することを可能にするために、第１及び第２の通信端末間の鍵を設定する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元αとこれら秘密鍵とからそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ｉ）第１の通信端末（Ａ）において第１のランダム整数ｘが選択され、生成元αを含む第１の関数ｆ（α）のｇ（ｘ）をベキとする指数関数を作ることにより、第１の指数関数ｆ（α）ｇ（ｘ）を提供するステップと、
ｉｉ）第１の通信端末（Ａ）において、第１のランダム整数ｘと第１の機密鍵ａとを組み合わせるために、第１のランダム整数ｘ、第１の指数関数ｆ（α）ｇ（ｘ）、及び第１の秘密鍵ａから第１の署名ｓＡを生成して、該第１の署名を保持するステップと、
ｉｉｉ）第１の通信端末（Ａ）から、第２の通信端子（Ｂ）に向けて、第１の指数関数ｆ（α）ｇ（ｘ）を含むメッセージを送るステップと、
ｉｖ）第２の通信端末（Ｂ）において、第２のランダム整数ｙを選択され、該第２のランダム整数ｙと第２の秘密鍵ｂとを組み合わせるために、生成元αを含む第２の関数ｆ’（α）のｇ（ｙ）をベキとする指数関数を作ることにより、第２の指数関数ｆ’（α）ｇ（ｙ）を提供し、第２のランダム整数ｙ、第２の指数関数ｆ’（α）ｇ（ｙ）、及び第２の秘密鍵ｂから第２の署名ｓＢを生成して、該第２の署名を保持するステップと、
ｖ）第２の通信端末（Ｂ）から、第１の通信端末（Ａ）に向けて、第２の指数関数ｆ’（α）ｇ（ｙ）を含むメッセージを送るステップと、
ｖｉ）第１の通信端末（Ａ）において、第２の通信端末（Ｂ）によって公開された情報を、第１の通信端末に属する秘密情報を用いて指数化することによって、セッション鍵Ｋを構築し、第２の通信端末（Ｂ）において、第１の通信端末（Ａ）によって公開された情報を、第２の通信端末に属する秘密情報を用いて指数化することによって、セッション鍵Ｋを構築するステップと
からなることを特徴とする方法。
【請求項２】
請求項１記載の方法において、第１の通信端末（Ａ）によって送られる情報は、該第１の通信端末の識別子を含み、第２の通信端末（Ｂ）によって送られる情報は、該第２の通信端末の識別子を含んでいることを特徴とする方法。
【請求項３】
請求項１又は２記載の方法において、生成元αを含む第１の関数ｆ（α）は、生成元α自体であり、生成元αを含む第２の関数ｆ’（α）は、生成元α自体であることを特徴とする方法。
【請求項４】
請求項１又は２記載の方法において、生成元αを含む第１関数ｆ（α）は、第２の通信端末（Ｂ）の公開鍵ｐＢを含み、生成元αを含む第２の関数ｆ’（α）は、第１の通信端末の公開鍵ｐＡを含むことを特徴とする方法。
【請求項５】
請求項１〜３いずれかに記載の方法において、第１の署名ｓＡは、第１の指数関数ｆ（α）ｇ（ｘ）から得られた整数ｒａ＊を用いて生成され、第２の署名ｓＢは、第２の指数関数ｆ’（α）ｇ（ｙ）から得られた整数ｒｂ＊を用いて生成されることを特徴とする方法。
【請求項６】
請求項５記載の方法において、第１の通信端末によって公開された情報は、第１の公開鍵ＰＡ、第１の指数関数ｆ（α）ｇ（ｘ）、及び整数ｒａ＊を組合せ、第２の通信端末によって公開された情報は、第２の公開鍵ＰＢ、第２の指数関数ｆ’（α）ｇ（ｙ）、及び整数ｒｂ＊を組み合わせることを特徴とする方法。
【請求項７】
請求項６記載の方法において、生成元αは、ｐを素数とする乗法群Ｚ＊ｐの要素であることを特徴とする方法。
【請求項８】
請求項５〜７いずれかに記載の方法において、第１の署名ｓＡ及び第２の署名ｓＢは、
ｓＡ＝ｘ＋ｒａ＊ａαａ  ｍｏｄ  （ｐ−１）
ｓＢ＝ｙ＋ｒｂ＊ｂαｂ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項９】
請求項８記載の方法において、
第１の通信端末によって、セッション鍵Ｋが、Ｋ＝（αｙ（αｂ）（ｒｂ＊））ｓＡ  ｍｏｄ  ｐとして計算され、
第２の通信端末によって、セッション鍵Ｋが、Ｋ＝（αｘ（αａ）（ｒａ＊））ｓＢ  ｍｏｄ  ｐとして計算されることを特徴とする方法。
【請求項１０】
請求項５〜９いずれかに記載の方法において、αは、ｑをｐ−１の素除数とした場合、群Ｚ＊ｐの位数ｑの部分群の生成元であることを特徴とする方法。
【請求項１１】
請求項５又は６記載の方法において、生成元αは、有限体Ｆｑ上で定義される楕円曲線上の位数ｎの点Ｐであり、該楕円曲線上のスカラ乗算によって、累乗が実行されることを特徴とする方法。
【請求項１２】
請求項１１記載の方法において、整数ｒａ＊及び整数ｒｂ＊は、第１及び第２の指数関数の座標のビット・ストリングスであることを特徴とする方法。
【請求項１３】
請求項１１又は１２記載の方法において、第１及び第２の署名ｓＡ及びｓＢは、
ｓＡ＝（ｘ＋（ｒａ＊）ａ）  ｍｏｄ  ｎ
ｓＢ＝（ｙ＋（ｒｂ＊）ｂ）  ｍｏｄ  ｎ
であることを特徴とする方法。
【請求項１４】
請求項１３記載の方法において、第２及び第１の通信端末において、セッション鍵Ｋはそれぞれ、
Ｋ＝ｓＡ（ｒｂ＋（ｒｂ＊）ＰＢ）
Ｋ＝ｓｂ（ｒａ＋（ｒａ＊）ＰＡ）
によって計算されることを特徴とする方法。
【請求項１５】
請求項１〜３いずれかに記載の方法において、第１及び第２の署名ｓＡ及びｓＢは、
ｓＡ＝ｘ＋ｒＡａαａ  ｍｏｄ  （ｐ−１）
ｓＢ＝ｙ＋ｒＢｂαｂ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項１６】
請求項４記載の方法において、第１及び第２の署名ｓＡ及びｓＢは、
ｓＡ＝ｘ＋ａ（ｐＢ）ｘ  ｍｏｄ  （ｐ−１）
ｓＢ＝ｙ＋ｂ（ｐＡ）ｙ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項１７】
通信チャネル（１４）を介して第１及び第２の通信端末（Ａ及びＢ）の間で情報を交換することを可能にするために、公開鍵通信システムにおいて、第１及び第２の通信端末間のセッション鍵Ｋを搬送する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元αとこれら秘密鍵とからそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ａ）第１の通信端末において第１のランダム整数ｘが選択され、該ランダム整数ｘと生成元αとから第１の値ｒＡを計算するステップと、
ｂ）第１の通信端末において、第１のランダム整数ｘと、第１の値ｒＡと、第１の秘密鍵ａとから第１の署名ｓＡを生成するステップと、
ｃ）第１の通信端末において、第１のランダム整数ｘと第２の通信端末に属する公開情報とからセッション鍵Ｋを計算するステップと、
ｄ）第１の通信端末から、第２の通信端子に向けて、第１の値ｒＡ及び第１の署名ｓＡを含むメッセージを送るステップと、
ｅ）第２の通信端末において、生成元α、第１の署名ｓＡ、第１の値ｒＡ、及び第１の通信端末に属する公開情報を用いて計算された値の有効性を検証するステップと、
ｆ）第２の通信端末において、第１の値ｒＡと、第２の通信端末に属する秘密情報であって、第２の通信端末に属する公開情報に関連している情報とから、セッション鍵Ｋを計算するステップと
からなることを特徴とする方法。
【請求項１８】
請求項１７記載の方法において、第１の値ｒＡは、生成元を含む第１の関数ｆ（α）を第１のランダム整数ｘをベキとするように指数化することによって計算されることを特徴とする方法。
【請求項１９】
請求項１８記載の方法において、第１の関数ｆ（α）は生成元αそのものであることを特徴とする方法。
【請求項２０】
請求項１７〜１９いずれかに記載の方法において、第１の署名ｓＡは、
ｓＡ＝ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項２１】
請求項１７〜１９いずれかに記載の方法において、第２の通信端末に属する公開情報は該通信端末の公開鍵ｐＢであり、第２の通信端末に属する秘密情報は該通信端末の秘密鍵ｂであり、第１の通信端末に属する公開情報は該通信端末の公開鍵ｐＡであることを特徴とする方法。
【請求項２２】
請求項２１記載の方法において、第１の通信端末によって計算されたセッション鍵Ｋは、（ｐＢ）ｘであることを特徴とする方法。
【請求項２３】
請求項２１又は２２記載の方法において、第２の通信端末によって有効性が検証される値は、αｓＡ（ｐＡ）ｒＡ・αａであることを特徴とする方法。
【請求項２４】
請求項２３記載の方法において、第２の通信端末によって計算されたセッション鍵Ｋは、（ｒＡ）ｂであることを特徴とする方法。
【請求項２５】
請求項１７〜２４いずれかに記載の方法において、第２の通信端末が、第１の通信端末にランダム・ビット・ストリングｋを送るステップを備えており、このステップは、セッション鍵Ｋと該セッション鍵Ｋで排他的論理和されたビット・ストリングｋとでメッセージを暗号化して、メッセージを暗号化するための短命鍵（ｋ＋Ｋ）を設定する前に、実行されることを特徴とする方法。
【請求項２６】
公開鍵データ通信システムにおいて、第１及び第２の通信端末間でセッション鍵を搬送して、これら通信端末の間で通信チャネルを介して情報を通信するための共通鍵を設定する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元α及びこれら秘密鍵からそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ｉ）第１の通信端末において第１のランダム整数ｘが選択され、生成元αを含む第１の関数ｆ（α）のｇ（ｘ）をベキとする指数関数を作ることにより、第１の指数関数ｆ（α）ｇ（ｘ）を提供するステップと、
ｉｉ）第１の通信端末において、第１のランダム整数ｘと第１の機密鍵ａとを組み合わせるために、第１のランダム整数ｘ、第１の記指数関数ｆ（α）ｇ（ｘ）、及び第１の秘密鍵ａから第１の署名ｓＡを生成して、該第１の署名を該第１の通信端末に属する秘密の署名として保持するステップと、
ｉｉｉ）第１の通信端末から、第２の通信端子に向けて、第１の指数関数ｆ（α）ｇ（ｘ）を含むメッセージを送るステップと、
ｉｖ）第１の通信端末において、第２の公開鍵ｐＢと第１の署名ｓＡとから第１のセッション鍵Ｋを計算するステップと、
ｖ）第２の通信端末において、第１の通信端末の公開鍵ｐＡと、メッセージ内の情報とを用いて、第１のセッション鍵Ｋに対応する第２のセッション鍵Ｋ’を計算するステップと
からなることを特徴とする方法。
【請求項２７】
請求項２６記載の方法において、第２の通信端末は、第１の指数関数ｆ（α）ｇ（ｘ）と第２の通信端末の秘密鍵ｂとを組み合わせることにより、第２のセッション鍵Ｋ’を生成することを特徴とする方法。
【請求項２８】
請求項２６又は２７記載の方法において、第１の通信端末は、第２の通信端末の第２の公開鍵ｐＢの関数を第１の署名ｓＡの関数で指数化することにより、セッション鍵Ｋを計算することを特徴とする方法。
【請求項２９】
請求項２６〜２８いずれかに記載の方法において、第１の通信端末の第１の署名ｓＡは、ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）であり、第２のセッション鍵Ｋ’は、Ｋ’＝（ｒＡ（ｐＡ）−ｒＡ・ｐＡ）ｂであることを特徴とする方法。
【請求項３０】
通信チャネル（１４）を介して第１及び第２の通信端末の間で情報を交換することを可能にするために、公開鍵通信システムにおいて、第１及び第２の通信端末の間でセッション鍵Ｋを搬送する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元αとこれら秘密鍵とからそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ａ）第１の通信端末において、第１のランダム整数ｘが選択され、該ランダム整数ｘと生成元αとから第１の値ｒＡを計算するステップと、
ｂ）第１の通信端末において、第１のランダム整数ｘと、第１の値ｒＡと、第１の秘密鍵ａとから第１の署名ｓＡを生成して、第１のランダム整数及び第１の秘密鍵ａを組み合わせるステップと、
ｃ）第１の通信端末において、第１のランダム整数ｘと第２の通信端末に属する公開情報とから、第２の通信端末によって計算可能であるセッション鍵Ｋを計算するステップと、
ｄ）第１の通信端末から、第２の通信端子に向けて、第１の値ｒＡ及び第１の署名ｓＡを含むメッセージを送るステップと
からなることを特徴とする方法。
【請求項３１】
請求項３０記載の方法において、第１の通信端末が、第２の通信端末からランダム・ビット・ストリングｋを受信するステップを備え、該ステップは、セッション鍵Ｋと該セッション鍵Ｋで排他的論理和されたビット・ストリングｋとでメッセージを暗号化して、メッセージを暗号化するための短命鍵（ｋ＋Ｋ）を設定する前に、実行されることを特徴とする方法。
【請求項３２】
通信チャネル（１４）を介して第１及び第２の通信端末の間で情報を交換することを可能にするために、公開鍵通信システムにおいて、第１及び第２の通信端末の間でセッション鍵Ｋを搬送する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元αとこれら秘密鍵とからそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ａ）第２の通信端末において、第１の通信端末から、第１の値ｒＡと第１の署名ｓＡとを受信するステップであって、第１の値ｒＡは、第１の通信端末において、第１のランダム整数ｘと生成元αとから計算され、第１の署名ｓＡは、第１の通信端末において、第１のランダム整数ｘと、第１の値ｒＡと、第１の秘密鍵ａとから生成されたものである、ステップと、
ｂ）第２の通信端末において、生成元、第１の署名ｓＡ、第１の値ｒＡ、及び第１の通信端末に属する公開鍵を用いて生成された値が、第１の通信端末から受信した第１の値ｒＡと等しいかどうかを判定するステップと、
ｃ）第２の通信端末において、該通信端末に属する秘密情報と第１の値ｒＡとからセッション鍵Ｋを計算するステップであって、該通信端末に属する秘密情報は、該通信端末に属する公開情報に関連しており、セッション鍵Ｋは、第１の通信端末においても計算可能である、ステップと
からなることを特徴とする方法。
【請求項３３】
請求項３２記載の方法において、第２の通信端末が、第１の通信端末にランダム・ビット・ストリングｋを送信するステップを備え、該ステップは、セッション鍵Ｋと該セッション鍵Ｋで排他的論理和されたビット・ストリングｋとでメッセージを暗号化して、メッセージを暗号化するための短命鍵（ｋ＋Ｋ）を設定する前に、実行されることを特徴とする方法。
【請求項３４】
請求項３０〜３３いずれかに記載の方法において、第１の値ｒＡは、生成元αを含む関数ｆ（α）を第１のランダム整数ｘをベキとする指数関数とすることにより計算されることを特徴とする方法。
【請求項３５】
請求項３４記載の方法において、生成元αを含む関数ｆ（α）は、生成元αそのものであることを特徴とする方法。
【請求項３６】
請求項３０〜３５いずれかに記載の方法において、第１の署名ｓＡは、ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）であることを特徴とする方法。
【請求項３７】
請求項３２〜３６いずれかに記載の方法において、第２の通信端末に属する公開情報は、第２の公開鍵ｐＢであり、第１の通信端末に属する公開情報は、第１の公開鍵ｐＡであり、第２の通信端末に属する秘密情報は、第２の秘密鍵ｂであることを特徴とする方法。
【請求項３８】
請求項３２、３３又は３７記載の方法において、第２の通信端末によって生成され判定された値は、αｓＡ（ｐＡ）ｒＡ・αａであることを特徴とする方法。
【請求項３９】
請求項３８記載の方法において、第２の通信端末によって計算されたセッション鍵Ｋは、（ｒＢ）ｂであることを特徴とする方法。
【請求項４０】
公開鍵データ通信システムにおいて、第１及び第２の通信端末間でセッション鍵を搬送して、これら通信端末の間で通信チャネルを介して情報を通信するための共通鍵を設定する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元α及びこれら秘密鍵からそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ｉ）第１の通信端末において、第１のランダム整数ｘが選択され、生成元αを含む第１の関数ｆ（α）のｇ（ｘ）をベキとする指数関数を作ることにより、第１の指数関数ｆ（α）ｇ（ｘ）を提供するステップと、
ｉｉ）第１の通信端末において、第１のランダム整数ｘと第１の機密鍵ａとを組み合わせるために、第１のランダム整数ｘ、第１の指数関数ｆ（α）ｇ（ｘ）、及び第１の秘密鍵ａから第１の署名ｓＡを生成して、該第１の署名を該第１の通信端末に属する秘密の署名として保持するステップと、
ｉｉｉ）第１の通信端末から、第２の通信端子に向けて、第１の指数関数ｆ（α）ｇ（ｘ）を含むメッセージを送るステップと、
ｉｖ）第１の通信端末において、第２の公開鍵ｐＢと第１の署名ｓＡとからセッション鍵Ｋを計算するステップであって、該セッション鍵Ｋは、第２の通信端末においても、第１の公開鍵ｐＡとメッセージ中の情報とを用いて計算可能である、ステップと
からなることを特徴とする方法。
【請求項４１】
請求項４０記載の方法において、第１の通信端末は、セッション鍵Ｋを、第２の公開鍵ｐＢの関数を第１の署名ｓＡで指数化することにより計算することを特徴とする方法。
【請求項４２】
請求項４０又は４１記載の方法において、第１の署名ｓＡは、ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）であることを特徴とする方法。
【請求項４３】
公開鍵データ通信システムにおいて、第１及び第２の通信端末間でセッション鍵を搬送して、これら通信端末の間で通信チャネルを介して情報を通信するための共通鍵を設定する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元α及びこれら秘密鍵からそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ｉ）第２の通信端末において、第１の通信端末から、第１の値ｒＡを含んでいるメッセージを受信するステップであって、第１の値ｒＡは、第１の通信端末において、第１のランダム整数ｘと生成元αとから計算されたものである、ステップと、
ｉｉ）第２の通信端末において、第１の値ｒＡ、第１の公開鍵ｐＡ、該通信端末に属する秘密情報から、セッション鍵Ｋを計算するステップであって、該通信端末に属する秘密情報は、該通信端末に属する公開情報に関連しており、セッション鍵は、第１の通信端末においても、第２の公開鍵ｐＢを用いて計算可能である、ステップと
からなることを特徴とする方法。
【請求項４４】
請求項４３記載の方法において、第２の通信端末に属する秘密情報は、第２の秘密鍵ｂであり、第２の通信端末に属する公開情報は、第２の公開情報ｐＢであることを特徴とする方法。
【請求項４５】
請求項４３又は４４記載の方法において、第２の通信端末は、セッション鍵Ｋを、Ｋ＝（ｒＡ（ｐＡ）−ｒＡ・ｐＡ）ｂによって計算することを特徴とする方法。
【請求項４６】
公開鍵暗号化を採用しているデータ通信システムにおいて、第１及び第２の通信端末間で鍵を搬送して、これら通信端末の間で通信チャネルを介して情報を通信するための共通鍵を設定する方法であって、第１及び第２の通信端末はそれぞれ、第１及び第２の秘密鍵ａ及びｂと、生成元α及びこれら秘密鍵からそれぞれ導かれた第１及び第２の公開鍵ｐＡ及びｐＢと、を有しており、該方法は、
ｉ）第１の通信端末において、第１のランダム整数ｘが選択され、生成元αを含む第１の関数ｆ（α）のｇ（ｘ）をベキとする指数関数を作ることにより、第１の指数関数ｆ（α）ｇ（ｘ）を提供するステップと、
ｉｉ）第１の通信端末において、第１のランダム整数ｘと第１の秘密鍵ａとを組み合わせるために、第１のランダム整数ｘ、第１の指数関数ｆ（α）ｇ（ｘ）、及び第１の秘密鍵ａから第１の署名ｓＡを生成するステップと、
ｉｉｉ）第１の通信端末において、第２の通信端末に、第１の指数関数ｆ（α）ｇ（ｘ）を送信するステップと、
ｉｖ）第１の通信端末において、第２の通信端末から、第２の指数関数ｆ’（α）ｇ（ｙ）を含んでいる情報を受信するステップであって、第２の指数関数ｆ’（α）ｇ（ｙ）は、第２の通信端末において、第２のランダム整数ｙが選択され、生成元αを含む関数ｆ’（α）のｇ（ｙ）をベキとする指数関数を作ることにより生成されたものである、ステップと、
ｖ）第１の通信端末において、第２の通信端末によって公開された情報を、第１の通信端末に属する秘密情報で指数化することによって、セッション鍵Ｋを構築するステップであって、第１の通信端末によって構築されたセッション鍵Ｋは、第２の通信端末においても、第１の通信端末によって公開された情報を、第２の通信端末に属する秘密情報で指数化することにより計算可能である、ステップと
からなることを特徴とする方法。
【請求項４７】
請求項４６記載の方法において、第１の通信端末から送信されるメッセージは、該通信端末の識別子を含んでおり、第２の通信端末から受信されるメッセージは、該通信端末の識別子を含んでいることを特徴とする方法。
【請求項４８】
請求項４６又は４７記載の方法において、生成元を含んでいる関数ｆ（α）は、生成元αそのものであることを特徴とする方法。
【請求項４９】
請求項４６又は４７記載の方法において、生成元を含んでいる関数ｆ（α）は、第２の公開鍵ｐＢを含んでいることを特徴とする方法。
【請求項５０】
請求項４６、４７又は４８記載の方法において、第１の通信端末の第１の署名ｓＡは、ｘ−ｒＡａαａ  ｍｏｄ  （ｐ−１）であることを特徴とする方法。
【請求項５１】
請求項４６、４７又は４９記載の方法において、第１の通信端末の第１の署名ｓＡは、ｘ＋ａαａ（ｐＢ）ｘ  ｍｏｄ  （ｐ−１）であることを特徴とする方法。
【請求項５２】
請求項４６〜４８いずれかに記載の方法において、第１の通信端末の第１の署名ｓＡは、ｘｒｘ１−（ｒＡ）ｒｘ１ａαａ  ｍｏｄ  （ｐ−１）であり、ｘ１は、第１の通信端末によって選択された第２のランダム整数であり、ｒｘ１＝αｘ１であることを特徴とする方法。
【請求項５３】
請求項４６〜４９いずれかに記載の方法において、第１の通信端末において、第３のランダム整数ｘ１を選択し、第２の通信端末に、ｒＡ１＝αｘ１なるｒＡ１を送信し、第１の通信端末において、第２の通信端末から、ｒＢ１＝αｙ１なるｒＢ１を受信し、ｙ１は、第２の通信端末によって選択された第４のランダム整数であり、第１の通信端末が、αｘｙ及びαｘ１・ｙ１にそれぞれ等しい一対の鍵ｋ１及びｋ２を計算し、セッション鍵がｋ１及びｋ２の排他的論理和によって生成されることを特徴とする方法。
【請求項５４】
請求項４６〜５３いずれかに記載の方法において、第１の通信端末によって受信されたメッセージは、第２の通信端末によって生成された署名ｓＢを含んでいることを特徴とする方法。
【請求項５５】
請求項５４記載の方法において、該方法はさらに、第１の通信端末において、第２の署名ｓＢ及び第２の指数関数ｆ’（α）ｇ（ｙ）から該第２の指数関数ｆ’（α）ｇ（ｙ）に等しい値を計算し、該計算された値を第２の指数関数ｆ’（α）ｇ（ｙ）と対比することによって、第２の通信端末から受信したメッセージの完全性（インテグリティ）の有効性を評価することにより、セッション鍵を正規なものとして認証するステップを含んでいることを特徴とする方法。
【請求項５６】
請求項４６〜４９いずれかに記載の方法において、第１の署名ｓＡは、第１の指数関数ｆ（α）ｇ（ｘ）から得られた整数ｒａ＊を用いて生成されることを特徴とする方法。
【請求項５７】
請求項５６記載の方法において、第２の通信端末によって公開された情報は、第２の公開鍵ｐＢ、第１の指数関数ｆ（α）ｇ（ｘ）、第２の通信端末の整数ｒｂ＊を組み合わせたものであることを特徴とする方法。
【請求項５８】
請求項５７記載の方法において、生成元αは、乗法群Ｚｐ＊（ｐは素数）の要素であることを特徴とする方法。
【請求項５９】
請求項５６〜５８いずれかに記載の方法において、第１の署名ｓＡは、ｓＡ＝ｘ＋（ｒａ＊）ａ  ｍｏｄ  （ｎ−１）であることを特徴とする方法。
【請求項６０】
請求項５９記載の方法において、セッション鍵Ｋは、Ｋ＝（αｙ（αｂ）ｒｂ＊）ｓＡ  ｍｏｄ  ｐであることを特徴とする方法。
【請求項６１】
請求項５６〜６０いずれかに記載の方法において、生成元αは、ｐを素数とする乗法群Ｚｐ＊の位数ｑ（ｑは素除数）の部分群の要素であることを特徴とする方法。
【請求項６２】
請求項５６又は５７記載の方法において、生成元αは、有限体Ｆｑ上で定義される楕円曲線上の位数ｎの点Ｐであり、該楕円曲線上のスカラ乗算によって、累乗が実行されることを特徴とする方法。
【請求項６３】
請求項６２記載の方法において、整数ｒａ＊は、第１の指数関数ｆ（α）ｇ（ｘ）の座標のビット・ストリングスであることを特徴とする方法。
【請求項６４】
請求項６２又は６３記載の方法において、第１の署名ｓＡは、
ｓＡ＝（ｘ＋（ｒａ＊）ａ）  ｍｏｄ  ｎ
であることを特徴とする方法。
【請求項６５】
請求項６４記載の方法において、第１の通信端末において、セッション鍵Ｋは、
Ｋ＝ｓｂ（ｒａ＋（ｒａ＊）Ｐａ）
によって計算されることを特徴とする方法。
【請求項６６】
請求項４６〜４８いずれかに記載の方法において、第１の通信端末が、第１の署名ｓＡを自身に属する秘密のものとして保持することを特徴とする方法。
【請求項６７】
請求項６６記載の方法において、第１の署名ｓＡは、
ｓＡ＝ｘ＋ｒＡａαａ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項６８】
請求項６６記載の方法において、第１の署名ｓＡは、
ｓＡ＝ｘ＋ａ（ｐＢ）ｘ  ｍｏｄ  （ｐ−１）
であることを特徴とする方法。
【請求項６９】
請求項６６記載の方法において、第１の署名ｓＡは、ｓＡ＝ｘｒＡ＋ａαａ
であることを特徴とする方法。
【請求項７０】
請求項６６記載の方法において、第１の署名ｓＡは、ｓＡ＝ｘαａ＋ａｒＡであることを特徴とする方法。
【請求項７１】
請求項１〜７０いずれかに記載の方法を実行することを特徴とするシステム。
【請求項７２】
コンピュータにより読み取り可能な記憶媒体であって、請求項１〜７０いずれかに記載の方法を実行するためのプログラムを記憶したことを特徴とする記憶媒体。