アルゴリズム論特論(塩田)第12回 (3) 生成元 $g$ の作り方

前へ / 戻る / 次へ $\newcommand{\ol}[1]{\overline{#1}}$ $\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$ $\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$ $\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$

生成元 $g$ の作り方(シンプルなヴァージョン)

 $g$ が生成元であること
    $\Leftrightarrow$  初めて $g^e=1$ となる自然数 $e$ (位数)が $p-1$
    $\Leftrightarrow$  $g^1 \neq 1$, $g^2 \neq 1$, $\cdots$, $g^{p-2} \neq 1$
でした。 これを計算で確かめようとするとその計算量は $O(p\log^2 p)$ になり、 実用の鍵サイズでは実行不可能です。 $p$ を無条件で作ってしまうからいけないので、もっと「作為的」に $p$ を作ることにしましょう。
Th.5 $p-1=2\,\times$ ( 大きな素数 $q$ ) であれば
$g$ が生成元であること  $\Leftrightarrow$  $g^2 \neq 1$ かつ $g^q \neq 1$.
証明 $\Rightarrow$) は上の注意より。
$\Leftarrow$) $g$ の位数を $e$ とし、これが $p-1$ に等しいことを示します。 前回の Th.4 (1) より $e$ は $p-1=2q$ の約数ですから、$e=1$, $2$, $q$, $2q$ のいずれかです。 条件より $g^2 \neq 1$, $g^q \neq 1$ であり、これから $g \neq 1$ でもありますから、 $e \neq 1 ,2,q$. 従って $e=2q=p-1$ となり $g$ は生成元となります。(証明終)

 $g^q$ の計算量は高速べき乗法を用いれば $O(\log^3 p)$ でした。 さらに、この設定下では約 50% の剰余類が生成元であることがわかっています。 従って、$p=2\times$ ( 大きな素数 $q$ ) $+1$ が素数であれば、 $\bmod\ p$ の生成元は高速に生成できます。
Algorithm 6(みんなの公開鍵) 
  • 入力:鍵長( $p$ のビット数 )$k$
  • 出力:$k$-ビットの素数 $p$ と、$\bmod\ p$ の生成元 $g$
while True:
  $q=(k-1)$-ビットのランダムな素数
  $p=2q+1$
  if $p$ が素数:
    break
while True:
  $g=$ 乱数 ( $1 \lt g \lt p-1$ )
  if $g^2 \neq 1$ and $g^q \neq 1$:
    $p$, $g$ を出力し終了

生成元 $g$ の作り方(一般化されたヴァージョン)

 ただし、鍵長が大きくなると
$q$ も $2q+1$ も素数
となる $q$ が見つかりにくくなります。 そこで、もう少し探しやすい定理も書いておきましょう。
Th.7 $p-1=$ ( 小さな偶数 $m$ ) $\times$ ( 大きな素数 $q$ ) であれば
   $g$ が生成元であること 
    $\Leftrightarrow$  $g^m \neq 1$ かつ 「 $m$ の全ての素因子 $\ell$ について $g^{(m/\ell)q} \neq 1$ 」
 例えば $p-1=72q$ であれば
$g^{72} \neq 1$,   $g^{36q} \neq 1$,   $g^{24q} \neq 1$
を満たす $g$ は生成元になります。証明は Th.5 と同様です。 これを使えば
Algorithm 8(みんなの公開鍵) 
  • 入力:鍵長( $p$ のビット数 )$k$
  • 出力:$k$-ビットの素数 $p$ と、$\bmod\ p$ の生成元 $g$
while True:
  $q=((k-10)$-ビットのランダムな素数$)$
  $m=(10$-ビット程度のランダムな偶数$)$
  $p=mq+1$
  if $p$ が $k$-ビット:
    if $p$ が素数:
      break
while True:
  $g=$ 乱数 ( $1 \lt g \lt p-1$ )
  if $g^m \neq 1$ and 「 $m$ の全ての素因子 $\ell$ について $g^{mq/\ell} \neq 1$ 」:
    $p$, $g$ を出力し終了
Rem.9 実は、もっと簡潔に
$g$ が生成元であること  $\Leftrightarrow$  $p-1$ の全ての素因子 $\ell$ について $g^{(p-1)/\ell} \neq 1$
と書けるのですが、 セキュリティ上の配慮から $p-1$ には大きな素因子を持たせたいので Th.7 のように書きました。