DH鍵共有

• 鍵共有 のプロトコル

Setup

大きい素数 $p$, $g\in {{\mathbb{F}}_p}^{\times }$ , $g^{p-1}=1(\mathrm{mod}p)$

Protocol

alice	bob
$a\leftarrow \mathbb{Z}$	$b\leftarrow \mathbb{Z}$
$A:=g^a(\mathrm{mod}p)$	$B:=g^b(\mathrm{mod}p)$
send to bob	send to alice
key $K_A:=B^a(\mathrm{mod}p)$	key $K_b:=A^b(\mathrm{mod}p)$

$K_A\equiv g^{ab}\equiv K_B$ なので共有されている.
$A,B$ からは $K$ を $\mathcal{O}(poly)$ で計算できない

そのような群が暗号に使えるか

$\rho :G\to \mathrm{Aut}(X)$, $|X|$ が小さいと軌道を調べて(=線形で) 離散対数問題が解けてしまう.

$G={\mathbb{F}}_p^{\times }$, $p\ge 2^{1024}$

$G$: 楕円曲線 上の有理点のなす群, $\mathrm{ord}(G)\ge 2^{250}$

アルゴリズム論特論（塩田）　2020年度教材 第13回

参考文献

• 暗号と楕円曲線