プロトコルの内容
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/02/13 21:58 UTC 版)
「楕円曲線ディフィー・ヘルマン鍵共有」の記事における「プロトコルの内容」の解説
アリスがボブとの間に共通鍵を構築したいが、2人の通信には第三者に盗聴される危険がある回線しかないものとする。まず、2人の間で使用する楕円曲線(つまり、有限体K、曲線を決定する3次式、ベースポイント G {\displaystyle G} 、その位数 n {\displaystyle n} などのパラメータ)を決めておく。そして、両者はこの楕円曲線上で、秘密鍵の d {\displaystyle d} ( [ 1 , n − 1 ] {\displaystyle [1,n-1]} からランダムに選んだ整数)と公開鍵の Q {\displaystyle Q} ( Q = d G {\displaystyle Q=dG} 、つまり楕円曲線上での掛け算を行う)からなる鍵対を生成しておく。ここで、アリスの鍵対を ( d A , Q A ) {\displaystyle (d_{A},Q_{A})} 、ボブのものを ( d B , Q B ) {\displaystyle (d_{B},Q_{B})} とする。それから、公開鍵を互いに交換する。 次に、アリスは ( x k , y k ) = d A Q B {\displaystyle (x_{k},y_{k})=d_{A}Q_{B}} という計算を、ボブは ( x k , y k ) = d B Q A {\displaystyle (x_{k},y_{k})=d_{B}Q_{A}} という計算を行う。 d A Q B = d A d B G = d B d A G = d B Q A {\displaystyle d_{A}Q_{B}=d_{A}d_{B}G=d_{B}d_{A}G=d_{B}Q_{A}} であるので、アリスもボブも同じ x k {\displaystyle x_{k}} (楕円曲線上のx座標)を得ることができるので、これを共有する秘密とする。ECDHを元にしたほとんどの規格化プロトコルでは、この秘密を元に、ハッシュ関数などを利用して共通鍵を生成する。
※この「プロトコルの内容」の解説は、「楕円曲線ディフィー・ヘルマン鍵共有」の解説の一部です。
「プロトコルの内容」を含む「楕円曲線ディフィー・ヘルマン鍵共有」の記事については、「楕円曲線ディフィー・ヘルマン鍵共有」の概要を参照ください。
プロトコルの内容
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/12/26 14:11 UTC 版)
「ディフィー・ヘルマン鍵共有」の記事における「プロトコルの内容」の解説
この方式は以下のように行われる。まず大きな素数 p {\displaystyle p} と、 p − 1 {\displaystyle p-1} を割り切る大きな素数 q {\displaystyle q} を用意する。また、 g {\displaystyle g} を ( Z / p Z ) ∗ {\displaystyle ({\mathbb {Z} }/p{\mathbb {Z} })^{\ast }} の元であり、位数が q {\displaystyle q} である値とする。この p , q , g {\displaystyle p,q,g} の値は公開されているものとする。 いまアリスとボブが通信を行うとする。このときアリスとボブはお互い自分だけの知る秘密の値 a, b を選択する、この値は 0 以上 q−1 以下の中からランダムに選ぶ。(ここで、ゼロや小さな値(ga < p となる a 等)を選択すると安全性が損なわれるが、そのような確率は無視できるほど小さい。) アリスは以下の値 A を計算してそれをボブに送信する。 A = g a mod p {\displaystyle A=g^{a}{\bmod {p}}} ボブも同様に以下の値 B を計算してそれをアリスに送信する。 B = g b mod p {\displaystyle B=g^{b}{\bmod {p}}} アリスは自分だけの知る秘密の値 a とボブから送られてきて受信した値 B から以下の値を計算する。 K A = B a mod p {\displaystyle K_{A}=B^{a}{\bmod {p}}} ボブも自分だけの知る秘密の値 b とアリスから送られてきて受信した値 A から以下の値を計算する。 K B = A b mod p {\displaystyle K_{B}=A^{b}{\bmod {p}}} このときアリスとボブが計算した K A {\displaystyle K_{A}} と K B {\displaystyle K_{B}} は K A = K B = g a b mod p {\displaystyle K_{A}=K_{B}=g^{ab}{\bmod {p}}} となっていて一致するので、以後この値を共通鍵暗号方式の鍵 K {\displaystyle K} として使用する。 ここで第三者イブがこの二人の通信を傍受していて A と B の値を入手できたとしても、 A = g a mod p {\displaystyle A=g^{a}{\bmod {p}}} と B = g b mod p {\displaystyle B=g^{b}{\bmod {p}}} から K = g a b mod p {\displaystyle K=g^{ab}{\bmod {p}}} を多項式時間で計算できる方法はいまのところ存在しないので、第三者イブが秘密の共通鍵 K {\displaystyle K} を生成することは困難である。このためアリスとボブが安全に通信を行うことが可能になる。 しかしながらたとえば、イブがボブになりすましをしていて、そうとは知らずに上記の手順でアリスが(相手がボブだと思ってだまされて)相互に通信をして共通鍵 K {\displaystyle K} を作ったとすると、それ以降のアリスからボブを相手として想定して送った K {\displaystyle K} を共通鍵として暗号化された通信の内容すべては,イブによって容易に内容が解読されてしまうことに注意が必要である。 なお、ディフィーとヘルマンによる最初の論文においては、 g {\displaystyle g} として ( Z / p Z ) ∗ {\displaystyle ({\mathbb {Z} }/p{\mathbb {Z} })^{\ast }} の生成元を用いることが提案されているが、この場合、アリスが送った A {\displaystyle A} のルジャンドル記号を計算することによって、アリスの秘密情報 a {\displaystyle a} の最下位ビットが漏洩してしまう。
※この「プロトコルの内容」の解説は、「ディフィー・ヘルマン鍵共有」の解説の一部です。
「プロトコルの内容」を含む「ディフィー・ヘルマン鍵共有」の記事については、「ディフィー・ヘルマン鍵共有」の概要を参照ください。
- プロトコルの内容のページへのリンク