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

  • 出席代わりに、塩田 ( shiota＠is.kochi-u.ac.jp ) 宛てにメールを出してください。
  • 件名は「アルゴリズム論特論第１２回出席」としてください。 $\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}}}$

今日のテーマ

  • Diffie-Hellman 鍵交換システム
  • 生成元の作り方
　前回勉強した離散対数問題を利用した公開鍵暗号の例として、 今日はDiffie-Hellman の鍵交換システムを紹介します。 後半ではその実装に必要な mod $p$ の生成元の作成方法を勉強します。

0. 前回の復習

  • $p$ が素数ならば $\znzc{p}$ は巡回群である。 すなわち、生成元と呼ばれる元 $g \in \znzc{p}$ が存在して、 $g$ のべき乗で $\znzc{p}$ の全ての要素が作れる
    $\langle\, g \,\rangle =\{\,g^0, g^1, g^2, \cdots\,\}=\znzc{p}.$
  • $y \in \znzc{p}$ に対し、
    $g^x = y$
    となるべき指数 $x$ を $x = \log_g y$ と表し、 mod $p$ での底 $g$ に対する $y$ の離散対数と呼ぶ。
  • $x = \log_g y$ は mod $(p-1)$ の数である。

1. ハイブリッド暗号

　公開鍵暗号は暗号化鍵を公開できるという強烈なメリットがある半面、 共通鍵暗号に比べて一般に 1000 倍程度以上の計算時間が掛かる、 というデメリットがあります。 そこで提案されたのが
Def.1　次のような暗号方式をハイブリッド暗号と呼ぶ。
  1. 前処理として、公開鍵暗号を用いて共通鍵暗号の鍵を交換する。
  2. 以後、通信は共通鍵暗号で行う。
　その名の通りこれは「いいとこ取り」で
  • 鍵交換は公開鍵暗号なので安全
  • 通信は共通鍵暗号なので高速
です。

2. Diffie-Hellman 鍵交換システム

　ハイブリッド暗号の 1° を実現する方法として 1976 年に提唱されたのが
Protocl 2（ Diffie-Hellman ）　
  1. 暗号センターが「みんなの公開鍵」として、 大きな素数 $p$ と、mod $p$ の生成元 $g$ を作り、これらを公開する。
  2. 各ユーザ $X$ は $1 \lt s_X \lt p-1$ の範囲で自分の秘密鍵 $s_X$ を決める。
  3. 各ユーザ $X$ は $k_X = g^{s_X}$ を計算し、$k_X$ を公開する。
  4. ユーザ $A$ と $B$ が共通鍵暗号で通信を行う際は、共通鍵として次の数を用いる。
    • $A$ は、$B$ の公開鍵 $k_B$ と自分の秘密鍵 $s_A$ を用いて計算した $(k_B)^{s_A}$ を用いる。
    • $B$ は、$A$ の公開鍵 $k_A$ と自分の秘密鍵 $s_B$ を用いて計算した $(k_A)^{s_B}$ を用いる。
同じ鍵になること
$(k_A)^{s_B}=(g^{s_A})^{s_B}=(g^{s_B})^{s_A}=(k_B)^{s_A}$
安全性　第三者が知りうる情報は
$p$, $g$, $k_A$, $k_B$
ですが、 離散対数問題の困難さから $s_A=\log_g(k_A)$, $s_B=\log_g(k_AB)$ は求められませんので、 共通鍵を求めることができ無いと考えられています。
Rem.3　Protocol 2 を用いて $n$ 人のユーザが互いに共通鍵暗号で通信するときも、 各自 1 組の鍵を作ればよい。
　ハイブリッドでない共通鍵暗号で $n$ 人が互いに通信するためには、
$\dps{\left(\begin{array}{c}n \\ 2 \end{array}\right)=\frac{n(n-1)}{2}}$ 個
の鍵が必要ですが、それがわずか $n$ 個で済む、というのも大きなメリットです。
Ex.4　
みんなの公開鍵 :
法 p = 16292009075775564755069608481562137642836392762267892941095960239720022389351286561904763483472145712070054625329770627945049345059408237015357509268714892813214058636215059222424254225746582060706237465194267515335163456262491739244406837528892301964959874895132988979964451194647353433219791889109214550848181033818200850884899784697040390726052156466143308701104406827718912905017106953213168279115617130959579470295652905104707334322195723508502741245560447070897586550082247478959562097989307169311407836515020865079807631050905074837398674510968402712818090292371526820325524923770695328586991536477845753606637 ( 2048-bit )
原始根 g = 2

A の秘密鍵 sA = 7738595088074923012721850632019677843612601620551516522482770467990347883844483544900818865929088525782192278872216246973410560005819627938867434164415648350118541174183431010612914591638543576147940295094353718801560831886383473253065702883002069542342887144037192906055610602057676826894201330181607047124948002836625266887382554215991536290149396621683315480074709759206870048969042998327736371391898819370494072933018865629997145080767301443116827540728347489040176654218640360326065863970979949695888313961696227981346781539268406775844394476421105948483699637296931657291288110682845377867890826848715381994820

B の秘密鍵 sB = 13747997446410507271723162309650861614076239119855049639787034975473701508324691453765457154792290138497291998007126335490835017180475564834961432146162300493750586377357912746272929260006511514066355865885522491436416375688161799578848661376329623720187983983845870630524727107861499152421165073296030608557005923125476762550251522727863045996240716943368053202982060599982358307179316657543647762292975940078185086784754374106261540920337928583264115607375056176581170504249693155435347858317486178189794948799135658913424754342785587415997483163494279489674373601257689493058391431671751892406922948327159209670599

A の公開鍵 kA = 16105023633185607952693566210834319531514551614799858576615241032115902853299558280658245592599512281263741456403290302869189541614313954755293222189924955427962963203939927279527756103289054219777875396542775658033818322383936989228998825308288358360686187380913450501005151172213873742526086992029653197514929663703541225950351110275204182635329297223394221293258766131688347965379440928112524099180855103931269423025900376077164932725468208991038512810090972870914103504943699996852112823329203445751704155739144023197322331240086493654779627459648568896123619124211781426268590082063185733233572772317982775599176

B の公開鍵 kB = 12425801222767478983482835405308557001612074153833193731016363342130855026065730186195317269727082337806457983374108090201110354055544001384577115047212675051718222681334278014624614547821239735918167164215304600291350138382686555325397407457283518021569314761731915760688889199732427130533654151812146399992553333993103164255606035433156318261678227606059723351279205761889430278053168071421368304654480933872741031288926397875163690639697972445081950992353680942769573288023518044587930957238504985526788637675484040999706311425885305106681420492580744699960239793029098315395948313445469315380379808555813359487241

A と B が共通鍵暗号で通信する場合の共通鍵 :

A による計算 kB^sA = 4178862039837598171259878691025693157778423960240279274275296535742306196898838217811431698502386263199420005327884602384455334671444357891657878061783009003209333665917045609858895413242489961663562547386852956099890965752373189364755149302418217151545432752892210733707707820980856304456142650032256077867052780902390623288025250016303282438916576856358453981197703229291843313114552708445193871209808651543490888885323906972662516969805959570283172904416786105383034394546320247689440457088525788880635422186656944062757976362028730919963753535320683671734536014363721026746701580818377048487486131986824707566914

B による計算 kA^sB = 4178862039837598171259878691025693157778423960240279274275296535742306196898838217811431698502386263199420005327884602384455334671444357891657878061783009003209333665917045609858895413242489961663562547386852956099890965752373189364755149302418217151545432752892210733707707820980856304456142650032256077867052780902390623288025250016303282438916576856358453981197703229291843313114552708445193871209808651543490888885323906972662516969805959570283172904416786105383034394546320247689440457088525788880635422186656944062757976362028730919963753535320683671734536014363721026746701580818377048487486131986824707566914
※　暗号通信そのものに離散対数問題を用いる公開鍵暗号としては ElGamal 暗号が有名です。 1985年に提唱されました。

3. 生成元 $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$ が素数であれば、 mod $p$ の生成元は高速に生成できます。
Algorithm 6（みんなの公開鍵）　
  • 入力：鍵長（ $p$ のビット数 ）$k$
  • 出力：$k$-ビットの素数 $p$ と、mod $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$ を出力し終了
　ただし、鍵長が大きくなると
$q$ も $2q+1$ も素数
となる $q$ が見つかりにくくなります。 そこで、もう少し探しやすい定理も書いておきましょう。
Th.7　$p-1=$ ( 小さな偶数 $m$ ) $\times$ ( 大きな素数 $q$ )　であれば
   $g$ が生成元であること 
    $\Leftrightarrow$  $g^m \neq 1$ かつ 「 $m$ の全ての素因子 $\ell$ について $g^{mq/\ell} \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$ と、mod $p$ の生成元 $g$
while True:
  $q=(k-10)$-ビットのランダムな素数
  $m=10\mbox{～}11$-ビットのランダムな偶数
  $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 のように書きました。

参考

  • 暗号ライブラリ crypto.py ... 以下のプログラムに引用
  • Diffie-Hellman 鍵交換システム DH.py

参考２

　最近気づいたのですが、 Python の組み込み関数 pow が pow(x,e,n) でべき乗剰余 $x^e\,\%\, n$ を求めてくれるのに対し、 math.pow は第３引数を受け付けません。 うっかり
from math import *
と書いてしまうと Python は pow と math.pow を混乱してしまいます。 ご注意ください。

自宅学習の例

  • サンプルプログラムを動かしてみる。

戻る