鍵交換プロトコル
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/23 09:10 UTC 版)
「超特異同種写像ディフィー・ヘルマン」の記事における「鍵交換プロトコル」の解説
アリスとボブが鍵交換をするとき、共通の楕円曲線 E からの同種写像をそれぞれが作る。そのために、同種写像の核空間(kernel)を定義するランダムな点（ R A {\displaystyle R_{A}} または R B {\displaystyle R_{B}} ）を生成する。 R A {\displaystyle R_{A}} は二点 P A , Q A {\displaystyle P_{A},Q_{A}} のランダムな線形結合であり、 R B {\displaystyle R_{B}} は P B , Q B {\displaystyle P_{B},Q_{B}} のランダムな線形結合である。異なる点のペアを使うことで、二人が選ぶ同種写像は必ず異なり、非可換である。 R A {\displaystyle R_{A}} （あるいは R B {\displaystyle R_{B}} ）から、アリス（あるいはボブ）はVeluの公式Velu's formulasを用いて同種写像 ϕ A {\displaystyle \phi _{A}} （あるいは ϕ B {\displaystyle \phi _{B}} ）を計算する。 さらに、ボブは二つの点 ϕ B ( P A ) {\displaystyle \phi _{B}(P_{A})} と ϕ B ( Q A ) {\displaystyle \phi _{B}(Q_{A})} を、アリスは ϕ A ( P B ) {\displaystyle \phi _{A}(P_{B})} と ϕ A ( Q B ) {\displaystyle \phi _{A}(Q_{B})} を得る。二人は、計算した二つの点を通信路を介して交換する。 次に、アリスとボブは、それぞれ受け取った二点から新たな同種写像を生成する。そのため、受け取った二点を上で用いたのと同じ係数を使って線形結合して、点 S B A {\displaystyle S_{BA}} と S A B {\displaystyle S_{AB}} を得る。ここでまた Veluの公式を使って S B A {\displaystyle S_{BA}} と S A B {\displaystyle S_{AB}} に対応する同種写像および新しい楕円曲線を計算する。 鍵交換を完了するには、アリスとボブはそれぞれ得られた楕円曲線の係数から j-不変量を計算する。通信路上でエラーが起こらない限り、二人が計算した j-不変量は等しくなる。 具体的には、プロトコルは以下のように動作する：（以下ではアリスはA、ボブはBと表記する） 1A. Aは二つのランダム整数 m A , n A ( < ( w A ) e A ) {\displaystyle m_{A},n_{A}(<(w_{A})^{e_{A}})} を選ぶ。 2A. Aは R A := m A ⋅ ( P A ) + n A ⋅ ( Q A ) {\displaystyle R_{A}:=m_{A}\cdot (P_{A})+n_{A}\cdot (Q_{A})} を計算する。 3A. Aは R A {\displaystyle R_{A}} を用いて同種写像 ϕ A : E → E A {\displaystyle \phi _{A}:E\rightarrow E_{A}} と、 E {\displaystyle E} と同種な楕円曲線 E A {\displaystyle E_{A}} を生成する。 4A. Aは ϕ A {\displaystyle \phi _{A}} を点 P B {\displaystyle P_{B}} と Q B {\displaystyle Q_{B}} に適用して、 E A {\displaystyle E_{A}} 上の二点 ϕ A ( P B ) {\displaystyle \phi _{A}(P_{B})} と ϕ A ( Q B ) {\displaystyle \phi _{A}(Q_{B})} を計算する。 5A. AはBに E A , ϕ A ( P B ) , ϕ A ( Q B ) {\displaystyle E_{A},\phi _{A}(P_{B}),\phi _{A}(Q_{B})} を送る。 1B - 4B: Bは、1A～4Aを、添え字AとBとを入れ替えて実行する。 5B. BはAに E B , ϕ B ( P A ) , ϕ B ( Q A ) {\displaystyle E_{B},\phi _{B}(P_{A}),\phi _{B}(Q_{A})} を送る。 6A. Aは m A , n A , ϕ B ( P A ) , ϕ B ( Q A ) {\displaystyle m_{A},n_{A},\phi _{B}(P_{A}),\phi _{B}(Q_{A})} から E B {\displaystyle E_{B}} 上の点 S B A := m A ( ϕ B ( P A ) ) + n A ( ϕ B ( Q A ) ) {\displaystyle S_{BA}:=m_{A}(\phi _{B}(P_{A}))+n_{A}(\phi _{B}(Q_{A}))} を計算する。 7A. Aは S B A {\displaystyle S_{BA}} を用いて E B {\displaystyle E_{B}} と同種な楕円曲線 E B A {\displaystyle E_{BA}} を生成する。 8A. Aは曲線 E B A {\displaystyle E_{BA}} の j-不変量 K A := j ( E B A ) {\displaystyle K_{A}:=j(E_{BA})} を計算する。 6B - 8B: Bは、6A～8Aを、添え字AとBを入れ替えて実行し、 K B := j ( E A B ) {\displaystyle K_{B}:=j(E_{AB})} を得る。 二つの曲線 E A B {\displaystyle E_{AB}} と E B A {\displaystyle E_{BA}} は同型であり、したがって必ず同じ j-不変量を持つため、 K := K A = K B {\displaystyle K:=K_{A}=K_{B}} が成り立つ。 K {\displaystyle K} を何らかの関数で変換したものを共有鍵として使用する。
※この「鍵交換プロトコル」の解説は、「超特異同種写像ディフィー・ヘルマン」の解説の一部です。
「鍵交換プロトコル」を含む「超特異同種写像ディフィー・ヘルマン」の記事については、「超特異同種写像ディフィー・ヘルマン」の概要を参照ください。
- 鍵交換プロトコルのページへのリンク
