アルゴリズム論特論（塩田）第12回 (2) Diffie-Hellman 鍵交換システム
前へ / 戻る / 次へ
$\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}}}$
ハイブリッド暗号
公開鍵暗号は暗号化鍵を公開できるという強烈なメリットがある半面、
共通鍵暗号に比べて一般に 1000 倍程度以上の計算時間が掛かる、
というデメリットがあります。
そこで提案されたのが
Def.1 次のような暗号方式をハイブリッド暗号と呼ぶ。
- 前処理として、公開鍵暗号を用いて共通鍵暗号の鍵を交換する。
- 以後、通信は共通鍵暗号で行う。
その名の通りこれは「いいとこ取り」で
- 鍵交換は公開鍵暗号なので安全
- 通信は共通鍵暗号なので高速
です。
Diffie-Hellman 鍵交換システム
ハイブリッド暗号の 1° を実現する方法として 1976 年に提唱されたのが
Protocol 2（ Diffie-Hellman ）
- 暗号センターが「みんなの公開鍵」として、
大きな素数 $p$ と、$\bmod\ p$ の生成元 $g$ を作り、これらを公開する。
- 各ユーザ $X$ は $1 \lt s_X \lt p-1$ の範囲で自分の秘密鍵 $s_X$ を決める。
- 各ユーザ $X$ は $k_X = g^{s_X}$ を計算し、$k_X$ を公開する。
- ユーザ $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 = g^sA = 16105023633185607952693566210834319531514551614799858576615241032115902853299558280658245592599512281263741456403290302869189541614313954755293222189924955427962963203939927279527756103289054219777875396542775658033818322383936989228998825308288358360686187380913450501005151172213873742526086992029653197514929663703541225950351110275204182635329297223394221293258766131688347965379440928112524099180855103931269423025900376077164932725468208991038512810090972870914103504943699996852112823329203445751704155739144023197322331240086493654779627459648568896123619124211781426268590082063185733233572772317982775599176
B の公開鍵 kB = g^sB = 12425801222767478983482835405308557001612074153833193731016363342130855026065730186195317269727082337806457983374108090201110354055544001384577115047212675051718222681334278014624614547821239735918167164215304600291350138382686555325397407457283518021569314761731915760688889199732427130533654151812146399992553333993103164255606035433156318261678227606059723351279205761889430278053168071421368304654480933872741031288926397875163690639697972445081950992353680942769573288023518044587930957238504985526788637675484040999706311425885305106681420492580744699960239793029098315395948313445469315380379808555813359487241
A と B が共通鍵暗号で通信する場合の共通鍵 :
A による計算 kB^sA = 4178862039837598171259878691025693157778423960240279274275296535742306196898838217811431698502386263199420005327884602384455334671444357891657878061783009003209333665917045609858895413242489961663562547386852956099890965752373189364755149302418217151545432752892210733707707820980856304456142650032256077867052780902390623288025250016303282438916576856358453981197703229291843313114552708445193871209808651543490888885323906972662516969805959570283172904416786105383034394546320247689440457088525788880635422186656944062757976362028730919963753535320683671734536014363721026746701580818377048487486131986824707566914
B による計算 kA^sB = 4178862039837598171259878691025693157778423960240279274275296535742306196898838217811431698502386263199420005327884602384455334671444357891657878061783009003209333665917045609858895413242489961663562547386852956099890965752373189364755149302418217151545432752892210733707707820980856304456142650032256077867052780902390623288025250016303282438916576856358453981197703229291843313114552708445193871209808651543490888885323906972662516969805959570283172904416786105383034394546320247689440457088525788880635422186656944062757976362028730919963753535320683671734536014363721026746701580818377048487486131986824707566914
※ 暗号通信そのものに離散対数問題を用いる公開鍵暗号としては ElGamal 暗号が有名です。
1985年に提唱されました。