JP4384728B2 - 内在的署名を用いた鍵一致及び輸送プロトコル - Google Patents

Description

本発明は、暗号鍵の転送及び認証のための鍵一致（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）α∈Ｚ^* _pとを真正であることが補償されるように、選択され公開される。通信者Ａは、長期の秘密鍵として１＜ａ＜ｐ−１であるランダムな整数ａを選択し、長期の公開鍵ｚ_A＝α^aｍｏｄｐを計算する。Ｂも、同様のｂとｚ_Bとを生成する。ＡとＢとは、相互の長期公開鍵の認証されたコピーへのアクセスを有することになる。
２．このプロトコルは、次のメッセージの交換を要求する。すなわち、
ＡからＢ：α^x ｍｏｄｐ （１）
ＢからＡ：α^y ｍｏｄｐ （２）
ｘ及びｙの値は、その送信の間は安全に保たれるが、その理由は、ｐが十分に大きくとられていれば、αの値と指数化とが知られているとしても、指数を決定するのは実際的ではないからである。
３．このプロトコルを実現するには、次のステップが、共有されている鍵が要求される度に実行される。
（ａ）Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、Ｂに向けて、メッセージ（１）、すなわち、α^xｍｏｄｐを送る。
（ｂ）Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、Ａに向けて、メッセージ（２）、すなわち、α^yｍｏｄｐを送る。
（ｃ）Ａは、鍵Ｋ＝（α^y）^aｚ_B ^xｍｏｄｐを計算する。
（ｄ）Ｂは、鍵Ｋ＝（α^x）^bｚ_A ^yｍｏｄｐを計算する。
（ｅ）両者は、鍵Ｋ＝α^bx+ayを共有する。
鍵Ｋを計算するためには、Ａは、自分の秘密鍵ａとランダムな整数ｘとを使わなければならない。これらは、共に、Ａ本人だけに知られているものである。同様にして、Ｂは、セッション鍵Ｋを計算するためには、自分の秘密鍵ｂとランダムな整数ｙとを使わなければならない。秘密鍵ａ及びｂが、危険にさらされていないと仮定すると、侵入者は、他方の通信者と同一のセッション鍵を生成することはできない。従って、任意の暗文は、どちらの通信者にも復号化が不可能である。
従って、このプロトコル及び関連するプロトコルは、鍵確立には十分なものであると考えられてきたし、従来型の盗聴や、中間者（man-in-the-middle）による攻撃に対して抵抗できると考えられてきた。
状況によっては、相手方が、一方の通信者を他方の通信者であるとミスリードするのが効果的である。
そのような攻撃では、アクティブな相手方、すなわち、侵入者Ｅは、ＡとＢとの間で交換されるメッセージを修正し、その結果として、Ｂは、Ｅと鍵Ｋを共有していると信じ、他方で、Ａは、同じ鍵をＢと共有していると信じることになる。ＥがＫの値を知らない場合であっても、通信者の識別（ＩＤ）に関する偽の情報が、有用となる。
そのような攻撃が成功するであろう実際的なシナリオは、次のようなものである。Ｂは、銀行の支店であり、Ａは、口座保持者であると仮定する。銀行の本部によって証明書が発行され、その証明書の中には、保持者の口座情報が書かれている。資金の電子的支払い（デポジット）のためのプロトコルは、相互認証された鍵一致を介して、銀行の支店との鍵の交換であると仮定する。Ｂがいったん送信者を認証すると、暗号化された資金がその証明書の口座番号に払い込まれる。それ以上の認証が暗号化された支払いメッセージにおいてなされない場合（これは、帯域幅を節約するためになされるかもしれない）には、支払いは、Ｅの口座になされる。
本発明の目的は、上述の短所が回避される又は解消されるようなプロトコルを提供することである。
従って、本発明によると、１対の通信者Ａ及びＢが相互に情報を交換することを認証する方法であって、前記通信者は、それぞれが、秘密鍵ａ及びｂと、生成元αと前記秘密鍵ａ及びｂのそれぞれとから導かれた公開鍵ｐ_A及びｐ_Bと、を有している方法が提供される。この方法は、
ｉ）前記通信者の第１の者Ａが、第１のランダムな整数ｘを選択し、前記生成元を含む関数ｆ（α）のｇ^(x)をベキとする指数関数を作ることにより、第１の指数関数ｆ（α）^g(x)を提供するステップと、
ｉｉ）前記第１の通信者Ａが、前記ランダムな整数ｘと前記指数関数ｆ（α）^g(x)とから第１の署名ｓ_Aを生成するステップと、
ｉｉｉ）前記第１の通信者Ａが、第２の通信者Ｂに向けて、前記第１の指数関数ｆ（α）^g(x)と署名ｓ_Aとを含むメッセージを送るステップと、
ｉｖ）前記通信者Ｂが、第２のランダムな整数ｙを選択し、前記生成元を含む関数ｆ’（α）のｇ^(y)をベキとする指数関数を作ることにより、第２の指数関数ｆ’（α）^g(y)と、前記第２の整数ｙと前記第２の指数関数ｆ（α）^g(x)とから得られるｓ_Bとを提供するステップと、
ｖ）前記第２の通信者Ｂが、第１の通信者Ａに向けて、前記第２の指数関数ｆ’（α）^g(y)と前記署名ｓ_Bとを含むメッセージを送るステップと、
ｖｉ）前記通信者のそれぞれが、受け取ったメッセージの中の前記署名と前記指数関数とから、前記指数関数と等しい値を計算し、前記計算された値と前記送信された値とを比較することによって、自分たちが受け取ったメッセージの真正を検証するステップと、
ｖｉｉ）前記通信者Ａ及びＢのそれぞれが、前記他方の通信者によって彼ら自身にとって秘密である前記ランダムな整数を用いて、公開された情報を指数化することによって、セッション鍵を構成するステップと、を含む。
従って、侵入者Ｅが自らの公開鍵ｐ_E＝α^acをメッセージの一部として送信の中に入れることはできるが、Ｂは、メッセージを認証する際には、ｐ_Aではなくｐ_Eを用いることになる。従って、指数関数の計算され送信された値は、対応しない。
本発明の実施例を次の添付した図面を参照することによって、これから説明することにする。
図１には、本発明による認証方法が用いられるデータ通信システムの概略図が示されている。
そこで、図１を参照すると、通信者Ａ及び通信者Ｂとして表される１対の通信者１０、１２が、通信チャネル１４上で情報を交換する（なお、この出願において通信者Ａ及び通信者Ｂ、通信者１０及び通信者１２などと表現されているのは、図１に示されているデータ通信システムの中に存在する通信機能を有するコンピュータである通信端末を意味する）。暗号ユニット１６、１８が、通信者１０、１２とチャネル１４とのそれぞれの間に配置されている。鍵２０は、暗号ユニット１６、１８のそれぞれに関連し、それぞれのユニット１６、１８とそれぞれの通信者１０、１２との間で運ばれる平文を、チャネル１４上で運ばれる暗文に変換する。
動作においては、Ａの通信者１０によって生成されるメッセージは、ユニット１６によって、鍵２０を用いて暗号化され、チャネル１４上の暗文として、ユニット１８まで送信される。
鍵２０は、ユニット１８において暗文に作用して、Ｂの通信者１２のために平文のメッセージを生成する。鍵２０が対応する場合には、通信者１２によって受け取られたメッセージは、通信者１０によって送られたものである。
図１に示されたシステムが動作するためには、鍵２０が同一であり、従って、公開的な態様での情報の移動を可能にする鍵一致（agreement）プロトコルが確立されていることが必要である。そのような鍵の生成には多数のプロトコルが利用可能であり、また、Diffie-Hellman鍵交換の変形も存在する。その目的は、当事者Ａ及びＢが秘密セッション鍵Ｋを確立することである。
これらのプロトコルのためのシステム・パラメータは、素数ｐと乗法群Ｚ^* _pの生成元αとである。通信者Ａは、秘密鍵ａと、公開鍵ｐ_A＝α^aとを有する。通信者Ｂは、秘密鍵ｂと、公開鍵ｐ_B＝α^bとを有する。以下で例を挙げるプロトコルでは、ｔｅｘｔ_Aは、当事者Ａを識別する情報のストリングを意味する。他方の当事者Ｂが通信者Ａの公開鍵の真正のコピーを有しており、更に、ｔｅｘｔ_AがＡの信用のおけるセンターによって発行された公開鍵証明書を含む場合には、通信者Ｂは、その信用のおけるセンターの公開鍵の真正のコピーを用いて、通信者Ａの証明書を検証でき、従って、通信者Ａの公開鍵の真正のコピーを得ることができる。
以下のそれぞれの例では、侵入者Ｅは、ＡからのメッセージがＥ自身から生じたものとして識別されることを望んでいると仮定する。これを達成するには、Ｅは、１≦ｅ≦ｐ−２であるランダムな整数ｅを選択し、ｐ_E＝（ｐ_A）ｅ＝α^ae ｍｏｄｐを計算し、これがＥ自身の公開鍵であることを証明させる。Ｅは、ｅを知ってはいるが、指数ａｅは知らない。ｔｅｘｔＡをｔｅｘｔＥによって代替することによって、通信者Ｂは、メッセージがＡからではなくＥからのものであると考え、Ｅの公開鍵を用いてセッション鍵Ｋを生成する。Ｅはまた、Ｂからのメッセージを中間奪取（インターセプト）し、その秘密のランダムな整数ｅを用いて、その内容を修正する。Ａは、次に、その情報を用いて、ＡがＢと通信できるようにする同じセッション鍵を生成する。
侵入者ＥがＢに、ＢはＥと通信しているということを信じさせようとしているのを妨害するには、次のプロトコルが採用される。
このプロトコルの目的は、当事者Ａ及びＢがセッション鍵Ｋを確立することである。ここで挙げたプロトコルは、役割対称的（role-symmetric）であり、対話的（interactive）ではない。
このプロトコルのためのシステム・パラメータは、素数ｐと乗法群Ｚ^* _pの生成元αとである。通信者Ａは、秘密鍵ａと、公開鍵ｐ_A＝α^aとを有する。通信者Ｂは、秘密鍵ｂと、公開鍵ｐ_B＝α^bとを有する。
第１のプロトコル
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒ_A＝α^xと、署名ｓ_A＝ｘ−ｒ_Aａα^aｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒ_A，ｓ_A，ｔｅｘｔ_A｝を送る。
２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、ｒ_B＝α^yと、署名ｓ_B＝ｙ−ｒ_Bｂα^bｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒ_B，ｓ_B，ｔｅｘｔ_B｝を送る。
３．Ａは、

を計算し、これが、ｒ_Bに等しいことを検証する。Ａは、次に、セッション鍵Ｋ＝（ｒ_B）^x＝α^xyを計算する。
４．Ｂは、

を計算し、これが、ｒ_Aに等しいことを検証する。Ｂは、次に、セッション鍵Ｋ＝（ｒ_A）^y＝α^xyを計算する。
Ｅが、ｔｅｘｔ_Aをｔｅｘｔ_Bに交換する場合には、Ｂは、ｒ_Aの送信された値には対応しない

を計算する。Ｂは、従って、侵入者Ｅに関する警告を受け、別のセッション鍵を開始することになる。
第１のプロトコルの短所は、完全な前方向の秘密性（守秘性）（perfect forward secrecy）が得られないことである。すなわち、相手側が当事者Ａの長期の秘密鍵ａを知る場合には、この相手側は、Ａの過去のセッション鍵すべてを導き出せることになる。完全な前方向の秘密性は、プロトコル１を次のようにして修正することによって、達成される。
修正された第１のプロトコル
ステップ１では、Ａはまた、

をＢに送る。ここで、ｘ₁は、Ａによって生成された第２のランダムな整数である。同様にして、上述のステップ２では、Ｂはまた、

をＡに送る。ここで、ｙ₁は、ランダムな整数である。Ａ及びＢは、鍵

を計算する。
第１のプロトコルの別の短所は、相手側がＡの秘密のランダムな整数ｘを知る場合には、この相手側は、当事者Ａの長期の秘密鍵を、方程式ｓ_A＝ｘ−ｒ_Aａα^aｍｏｄ（ｐ−１）から求めることができる点である。このプロトコルのうまく設計された実現例では、秘密の整数の開示は回避されるので、この短所は、基本的に理論的性格を有するものである。
第２のプロトコル
次に述べる第２のプロトコルは、これら２つの短所を解決する。
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、（ｐ_B）^xと、α^xと署名ｓ_A＝ｘ＋ａα^a（ｐ_B）^xｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛α^x，ｓ_A，ｔｅｘｔ_A｝を送る。
２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、（ｐ_A）^yと、α^yと署名ｓ_B＝ｙ＋ｂα^b（ｐ_A）^yｍｏｄ（ｐ−１）と、を計算する。Ｂは、Ａに向けて、｛α^y，ｓ_B，ｔｅｘｔ_B｝を送る。
３．Ａは、（α^y）^aを計算して、

であることを検証する。Ａは、次に、セッション鍵Ｋ＝α^ay（ｐ_B）^xを計算する。
４．Ｂは、（α^x）^bを計算して、

であることを検証する。Ａは、次に、セッション鍵Ｋ＝α^by（ｐ_A）^yを計算する。
第２のプロトコルが第１のプロトコルとの比較で優れているのは、それが、完全な前方向の秘密性（forward secrecy）を提供するからである。秘密であるランダムな整数ｘの開示によって、相手側が秘密鍵ａを知ることができるのではあるが、これは実際上は問題ではない。なぜならば、Ａは、自分がこのプロトコルのステップ１においてｘを用いた直後に、ｘを廃棄することができるからである。
ＡがＢの公開鍵の認証されたコピーを有していない場合には、Ｂは、自らの鍵の真正（certified）なコピーを、プロトコルの開始時に、Ａに送信しなければならない。この場合には、第２のプロトコルは、３パス・プロトコルである。
量Ｓ_Aは、値α^xに対して、Ａの署名として機能する。この署名は、当事者Ｂだけに確認が可能であるという新規な性質を有している。このアイデアは、ElGamalライクな署名方式のすべてに一般化できる。
上述の第１及び第２のプロトコルは、帯域幅の要件と、鍵一致の計算上の効率とを向上させるように修正が可能である。修正されたプロトコルは、次に、プロトコル１’及びプロトコル２’として、示してある。それぞれの場合に、Ａ及びＢは、共通鍵α^SASBを共有している。
プロトコル１’
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒ_A＝α^aと、ｓ_A＝ｘ＋ｒ_Aａα^aｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒ_A，ｔｅｘｔ_A｝を送る。
２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、ｒ_B＝α^yと、ｓ_B＝ｙ＋ｒ_Bｂα^bｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒ_B，ｔｅｘｔ_B｝を送る。
３．Ａは、

に等しい

を計算する。
４．Ｂは、

に等しい

を計算する。
このようにして、Ａ及びＢは、共通鍵を共有するが、署名ｓＡ及びｓＢは、送信される必要がないことに注意すべきである。
プロトコル２’
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、（ｐ_B）^xと、α^xと署名ｓ_A＝ｘ＋ａ（ｐ_B）^xｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛α^x，ｔｅｘｔ_A｝を送る。
２．Ｂは、１≦ｙ≦ｐ−２であるランダムな整数ｙを選び、（ｐ_A）^yと、α^yと署名ｓ_B＝ｙ＋ｂ（ｐ_A）^yｍｏｄ（ｐ−１）と、を計算する。Ｂは、Ａに向けて、｛α^y，ｔｅｘｔ_B｝を送る。
３．Ａは、（α^y）^aと、

を、すなわち、

を計算する。
４．Ｂは、（α^x）^bと、

を、すなわち、

を計算する。
従って、やはり、ｓ_A及びｓ_Bの送信が回避された。
Ａ及びＢがセッション鍵Ｋを確立するために、別のプロトコルが利用可能である。
第３のプロトコル
このプロトコルに対するシステム・パラメータは、乗法群Ｚ^* _pの素数ｐと生成元αである。ユーザＡは、秘密鍵ａと公開鍵ｐ_A＝α^aとを有している。ユーザＢは、秘密鍵ｂと公開鍵ｐ_B＝α^bとを有している。
１．Ａは、１≦ｘ，ｘ₁≦ｐ−２である２つのランダムな整数ｘ，ｘ₁を選び、

と、ｒ_A＝α^xと、

とを計算し、更に、署名

を計算する。Ａは、Ｂに向けて、

を送る。
２．Ｂは、１≦ｙ，ｙ₁≦ｐ−２である２つのランダムな整数ｙ，ｙ₁を選び、

と、ｒ_B＝α^yと、

とを計算し、更に、署名

を計算する。Ｂは、Ａに向けて、

を送る。
３．Ａは、

を計算し、これが、

に等しいことを確認する。Ａは、セッション鍵

を計算する。
４．Ｂは、

を計算し、これが、

に等しいことを確認する。Ｂは、セッション鍵

を計算する。
これらのプロトコルでは、（ｒ_A，ｓ_A）は、Ａだけがメッセージ

に署名できるという性質を有する

の署名であると考えることができる。
鍵輸送プロトコル
上述のプロトコルによれば、セッション鍵の確立と認証とが可能になる。Ａがセッション鍵を当事者Ｂに輸送（transport）することを可能にするプロトコルを確立することが望まれる。そのようなプロトコルを次に述べる。
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒ_A＝α^xと、署名ｓ_A＝ｘ−ｒ_Aａα^a ｍｏｄ（ｐ−１）と、を計算する。Ａは、Ｂに向けて、｛ｒ_A，ｓ_A，ｔｅｘｔ_A｝を送る。
２．Ｂは、

を計算し、この量が、ｒ_Aに等しいことを検証する。Ｂは、次に、セッション鍵Ｋ＝（ｒ_A）^bを計算する。
修正された鍵輸送プロトコル
上述のプロトコルは、署名ｓＡを送信する必要をなくすことによって、帯域幅を減少させるように修正が可能である。
１．Ａは、１≦ｘ≦ｐ−２であるランダムな整数ｘを選び、ｒ_A＝α^xと、署名ｓ_A＝ｘ−ｒ_Aａα^a ｍｏｄ（ｐ−１）と、を計算する。Ａは、更に、

を計算して、Ｂに向けて、｛ｒ_A，ｔｅｘｔ_A｝を送る。
２．Ｂは、

を計算し、この量が、ｒ_Aに等しいことを検証する。Ｂは、次に、セッション鍵Ｋ＝（α^x（ｐ_A）^-rAαa）^b＝α^bSAを計算する。
すべての１パス鍵輸送プロトコルは、次に述べるリプレイの問題を有する。１パス鍵輸送プロトコルを用いてセッション鍵ＫをＡからＢへ、このセッション鍵を用いて暗号化された何らかのテキストと共に送信することを考える。Ｅが、ＡからＢへの送信を記録すると仮定する。もし、Ｅが、後に、Ｂの復号化装置へのアクセス（ただし、Ｂの秘密鍵など、その装置の内部的な内容へのアクセスではない）を、その装置への送信をリプレイすることによって得ることになる場合には、Ｅは、元のテキストを回復することができる。この状況では、Ｅは、セッション鍵を知らない。
このリプレイによるアタックは、タイムスタンプの使用などの、通常の方法によって失敗させることができる。しかし、Ｂの計算資源が限定されていて、それぞれのセッションの開始時に、Ｂがランダムなビット・ストリングｋをＡに送信する方がより適切であるようなこともあり得る。テキストを暗号化するのに用いられるセッション鍵は、その場合には、ｋ▲＋▼ｋ、すなわち、ｋとｋとのＸＯＲを計算したものとなる。
署名（signing）方程式ｓ_A＝ｘ−ｒ_Aａα^aと、プロトコル２における鍵輸送プロトコルｒ_A＝α^xbとは、いくつかの変形例で代替することができる。いくつか例を挙げると、次の通りである。
ｒ_A＝ｓ_Aｘ＋ｚ
ｓ_A＝ｘα^a＋ａｒ_A
ｓ_A＝ｘｒ_A＋Ａα^a
１＝ａｒ_A＋ｘｓ_A
既に述べたプロトコルは、すべて、乗法群Ｚ^* _pの設定において、説明された。しかし、これらのプロトコルは、離散対数問題が困難を生じさせるように見える任意の有限群において機能するように容易に修正することができる。適切な選択肢としては、有限体の乗法群（特に、有限体ＧＦ（２ⁿ））、位数（order）ｑのＺ^* _pの部分群、有限体上で定義される楕円曲線上の点から成る群などがある。それぞれの場合に、適切な生成元（generator）αを用いて公開鍵を定義する。
上述したプロトコルは、また、直接的な方法で修正して、それぞれのユーザが自分自身のシステム・パラメータｐ及びα（又は、Ｚ^* _p以外の群が用いられる場合には、類似のパラメータ）を選択できるような状況を扱えるようにできる。
上述のプロトコルでは、一般形式ｓ_A＝ｘ＋ｒ_a・ａ・α^aの署名成分が用いられていた。これらのプロトコルは、安全性を損ねることなく、より単純な一般形式ｓ_A＝ｘ＋ｒ_a・ａの署名成分を用いるように修正が可能である。
これらのプロトコルの例を、同じ記号（notation）を用いて以下に与えるが、望むのであれば、別の記号を用いてこれらのプロトコルを表現することができることを理解すべきである。
プロトコル１”
このプロトコルは、乗法群Ｚ^* _pにおける次の記号を用いて説明される。
ｐは、素数である。
αは、Ｚ^* _pの生成元である。
ａ及びｂは、当事者Ａ及びＢのそれぞれの長期的な秘密鍵である。
α^a ｍｏｄ ｐは、当事者Ａの長期的な秘密鍵である。
α^b ｍｏｄ ｐは、当事者Ｂの長期的な秘密鍵である。
ｘは、Ａによって短期の秘密鍵として選択されるランダムな整数である。
ｒ_a＝α^x ｍｏｄ ｐは、当事者Ａの短期の公開鍵である。
ｙは、Ｂによって短期の秘密鍵として選択されるランダムな整数である。
ｒ^b＝α^y ｍｏｄ ｐは、当事者Ａの短期の公開鍵である。

は、ｒ_aから導かれる整数である。

は、ｒ_bから導かれる整数である。
プロトコルを実現するには、次のようにする。
１．Ａは、ｒ_aをＢに送る。
２．Ｂは、ｒ_bをＡに送る。
３．Ａは、

を計算する。
４．Ａは、セッション鍵

を計算する。
５．Ｂは、

を計算する。
６．Ｂは、セッション鍵

を計算する。
７．共有される秘密は、α^sAsBｍｏｄｐである。
このプロトコルでは、待機幅の要件が再び緩和されているが、署名成分は、通信者の短期及び長期の鍵を組み合わせて、侵入者からの攻撃を禁止している。
このプロトコルは、また、Ｚ^* _pの部分群を用いても実現できる。この場合には、ｑは、（ｐ−１）の素約数（prime divisor）であり、ｇは、Ｚ^* _pの中の位数ｐの要素である。
Ａ及びＢの公開鍵は、それぞれが、ｇ^a及びｇ^bの形式を有し、短期の鍵ｒ_a及びｒ_bは、ｇ^x及びｇ^yの形式を有している。
署名成分であるｓ_A及びｓ_Bは、ｍｏｄｑで計算され、セッション鍵は、従前のように、ｍｏｄｑで計算される。この場合には、共有の秘密は、

である。
既に述べたように、これらのプロトコルは、Ｚ^* _p以外の群においても実現が可能であり、特に、ローバスト（robust）群は、有限体上の楕円曲線上の点から成る群である。このような実現例は、次にプロトコル１”’として挙げてある。
プロトコル１”’
次の記号を用いる。
Ｅは、Ｆｑ上で定義される楕円曲線である。
Ｐは、Ｅ（Ｆｑ）内の素数位数の点である。
ｄ_a（１＜ｄ_a＜ｎ−１）は、当事者Ａの長期の秘密鍵である。
ｄ_b（１＜ｄ_b＜ｎ−１）は、当事者Ｂの長期の秘密鍵である。
Ｑ_a＝ｄ_aＰは、当事者Ａの長期の公開鍵である。
Ｑ_b＝ｄ_bＰは、当事者Ｂの長期の公開鍵である。
ｋ（１＜ｋ＜ｎ−１）は、当事者Ａの短期の秘密鍵である。
ｍ（１＜ｍ＜ｎ−１）は、当事者Ｂの短期の秘密鍵である。
ｒ_b＝ｍＰは、当事者Ｂの短期の公開鍵である。
ｒａ及びｒｂは、ビット・ストリングであり、例えば、ｒ_a及びｒ_bのｘ座標の８０最下位ビットである。
このプロトコルを実現するには、次のようにする。
１．Ａは、ｒ_aをＢに送る。
２．Ｂは、ｒ_bをＡに送る。
３．Ａは、

を計算する。
４．Ａは、セッション鍵

を計算する。
５．Ｂは、

を計算する。
６．Ｂは、セッション鍵

を計算する。
７．共有される秘密は、ｓ_aｓ_bＰである。
再び、通信者の間では署名成分ｓＡ及びｓＢを送る必要はないことに注意すべきである。しかし、通信者の短期及び長期の鍵が成分の形式で組み合わされる。
先の例におけるｘ及びｙに対して、記号ｍを用いているのは、曲線上の点の座標（ｘ，ｙ）との混乱を回避するためである。

Claims (11)

1. 公開鍵暗号化を採用しているデータ通信システムにおいて、通信チャネル（１４）を介して第１及び第２の通信端末（Ａ及びＢ）の間で情報を交換することを可能にするために、第１及び第２の通信端末間の鍵を設定する方法であって、第１の通信端末は、第１の秘密鍵ａと、生成元α及び該秘密鍵から導かれた第１の公開鍵ｐ_Aと、を有しており、第２の通信端末は、第２の秘密鍵ｂと、生成元α及び該秘密鍵から導かれた第２の公開鍵ｐ_Bと、を有しており、該方法は、
   ｉ）第１の通信端末（Ａ）において、第１のランダム整数ｘを選択して、該第１のランダム整数ｘを含む関数ｇ（ｘ）を、生成元αを含む第１の関数ｆ（α）のベキとする指数関数を作ることにより、第１の指数関数ｆ（α）^g(x)を提供するステップと、
   ｉｉ）第１の通信端末（Ａ）において、第１のランダム整数ｘ、第１の指数関数ｆ（α）^g(x)、及び第１の秘密鍵ａから、第１のランダム整数ｘと第１の秘密鍵ａとを組み合わせるために、第１の署名ｓ_Aを生成するステップと、
   ｉｉｉ）第１の通信端末（Ａ）から、第２の通信端末（Ｂ）に、第１の指数関数ｆ（α）^g(x)を含むメッセージを送るステップと、
   ｉｖ）第２の通信端末（Ｂ）において、第２のランダム整数ｙを選択して、該第２のランダム整数ｙを含む関数ｇ（ｙ）を、生成元αを含む第２の関数ｆ’（α）のベキとする指数関数を作ることにより、第２の指数関数ｆ’（α）^g(y)を提供し、第２のランダム整数ｙ、第２の指数関数ｆ’（α）^g(y)、及び第２の秘密鍵ｂから、第２のランダム整数ｙと第２の秘密鍵ｂとを組み合わせるために、第２の署名ｓ_Bを生成するステップと、
   ｖ）第２の通信端末（Ｂ）から、第１の通信端末（Ａ）に、第２の指数関数ｆ’（α）^g(y)を含むメッセージを送るステップと、
   ｖｉ）第１の通信端末（Ａ）において、第２の通信端末（Ｂ）によって公開された情報を、第１の通信端末に属する秘密情報により累乗することによって、セッション鍵Ｋを構築し、第２の通信端末（Ｂ）において、第１の通信端末（Ａ）によって公開された情報を、第２の通信端末に属する秘密情報により累乗することによって、セッション鍵Ｋを構築するステップであって、第１の通信端末（Ａ）においては第１の署名ｓ_A及び第２の署名ｓ_Bの一方用い、第２の通信端末（Ｂ）においてはこれら署名の他方を用いる、ステップと
   からなることを特徴とする方法。
2. 請求項１記載の方法において、第１の通信端末（Ａ）によって送られるメッセージは、該第１の通信端末のアイデンティフィケーション（ＩＤ）を含み、第２の通信端末（Ｂ）によって送られるメッセージは、該第２の通信端末のＩＤを含んでいることを特徴とする方法。
3. 請求項１又は２記載の方法において、生成元αを含む第１の関数ｆ（α）及び第２の関数ｆ’（α）はそれぞれ、生成元α自体であることを特徴とする方法。
4. 請求項１又は２記載の方法において、生成元αを含む第１の関数ｆ（α）は、第２の通信端末（Ｂ）の公開鍵ｐ_Bを含み、生成元αを含む第２の関数ｆ’（α）は、第１の通信端末（Ａ）の公開鍵ｐ_Aを含むことを特徴とする方法。
5. 請求項１〜３いずれかに記載の方法において、第１及び第２の署名ｓ_A及びｓ_Bは、
   ｓ_A＝ｘ−ｒ_Aａα^a ｍｏｄ （ｐ−１）
   ｓ_B＝ｙ−ｒ_Bｂα^b ｍｏｄ （ｐ−１）
   ただし、ｒ_A＝α^x＝ｆ（α）^g(x)
   ｒ_B＝α^y＝ｆ’（α）^g(y)
   ｐ：素数
   であることを特徴とする方法。
6. 請求項１、２又は４記載の方法において、第１及び第２の署名ｓ_A及びｓ_Bは、
   ｓ_A＝ｘ＋ａα^a（ｐ_B）^x ｍｏｄ （ｐ−１）
   ｓ_B＝ｙ＋ｂα^b（ｐ_A）^y ｍｏｄ （ｐ−１）
   ただし、ｐ：素数
   であることを特徴とする方法。
7. 請求項１〜３いずれかに記載の方法において、第１及び第２の署名ｓ_A及びｓ_Bは、
   ｓ_A＝ｘｒ_x1−（ｒ_A）^rx1ａα^a ｍｏｄ（ｐ−１）
   ｓ_B＝ｙｒ_y1−（ｒ_B）^ry1ｂα^b ｍｏｄ（ｐ−１）
   ただし、ｘ₁：第１の通信端末において選択された第２のランダム整数
   ｙ₁：第２の通信端末において選択された第２のランダム整数
   ｒ_x1＝α^x1
   ｒ_y1＝α^y1
   ｐ：素数
   であることを特徴とする方法。
8. 請求項１〜３いずれかに記載の方法において、該方法はさらに、
   第１の通信端末において、第３のランダム整数ｘ₁を選択してα^x1を生成し、該α^x1を第２の通信端末に送るステップと、
   第２の通信端末において、第４のランダム整数ｙ₁を選択してα^y1を生成し、該α^y1を第１の通信端末に送るステップと、
   第１及び第２の通信端末において、一対の鍵ｋ₁及びｋ₂を
   ｋ₁＝α^x・y
   ｋ₂＝α^x1・y1
   を計算するステップと
   を備え、これら鍵ｋ₁及びｋ₂のＸＯＲを計算することにより、セッション鍵Ｋを生成することを特徴とする方法。
9. 請求項１〜８いずれかに記載の方法において、第１の指数関数ｆ（α）^g(x)を含んでいるメッセージは第１の署名ｓ_Aをさらに含み、第２の指数関数ｆ’（α）^g(x)を含んでいるメッセージは第２の署名ｓ_Bをさらに含んでいることを特徴とする方法。
10. 請求項９記載の方法において、ステップｖｉ）はさらに、
    第１の通信端末（Ａ）において、該通信端末によって受信したメッセージの完全性（インテグリティ）の有効性を、該メッセージに含まれる第２の署名及び第２の指数関数から該第２の指数関数と等価な値を計算し、該計算された値を、受信したメッセージ中の第２の指数関数と対比することによって、評価するステップと、
    第２の通信端末（Ｂ）において、該通信端末によって受信したメッセージの完全性（インテグリティ）の有効性を、該メッセージに含まれる第１の署名及び第１の指数関数から該第１の指数関数と等価な値を計算し、該計算された値を、受信したメッセージ中の第１の指数関数と対比することによって、評価するステップと
    を備えていることを特徴とする方法。
11. 請求項１〜３いずれかに記載の方法において、第１の通信端末（Ａ）に属する秘密情報は第１の署名ｓ_Aであり、第２の通信端末（Ｂ）に属する秘密情報は第２の署名ｓ_Bであることを特徴とする方法。

Images