ロコリンの雑記

アニメ大好き社会人のロコリンのブログ。2015年卒(修士)の社会人。学生時代(2010年)から続けてるブログなのでエントリによっては学生ブログと社会人ブログになっています。時系列から察して。
 
 
このブログについて
ブログ内検索
カテゴリ
プロフィール

ロコリン

Author:ロコリン
2018年6月から会社員。2015年3月まで大学院生でした。
趣味:アニメ/Twitter/ゲーム/ニコ動
今(2015年2月更新):プリキュア/プリパラ/アイカツ/ごちうさ/艦これ

外部リンク
Twitter

スポンサーサイト 

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Diffie-Hellman 鍵交換法 

情報セキュリティスペシャリスト試験の勉強をしていて、いくつか面白い技術に出会いました。その1つとして Diffie-Hellman 鍵交換法を紹介します。

§1 Diffie-Hellman 鍵交換法

Diffie-Hellman 鍵交換法 (Diffie-Hellman Key Exchange, 以下 DH 法) は、盗聴されうる通信路上で安全に共通鍵を交換 (共有) する方法の1つです。離散対数問題の解析的な解法が見つかっていないことを安全性の根拠としています。

§1.1 DH 法の原理

A さんと B さんの 2 人がインターネット上で共通鍵を交換することを考えます。ここで考えるインターネットではパケット盗聴などの脅威が存在するものとします。
  1. まず、 2 人で次の 2 つの数を定めます (これらの数は盗聴されても良い。)。
    • p : 素数
    • r : 自然数, r < p
  2. 次に、 A さんと B さんはそれぞれ自分用の秘密の数 (自然数) を定めます。この数は 0 以上 p - 1 未満の数です。仮に A さんは sA 、 B さんは sB を秘密の数にしたとします。この数 sA, sB は相手に知らせてはいけません。盗聴されてはいけません。
    • A さんは p, r, sA を使って次の数 cA を計算します。
      cA = rsA mod p
    • B さんは p, r, sB を使って次の数 cB を計算します。
      cB = rsB mod p
    ここで、 m mod nmn で割った余りを表します。
  3. A さんと B さんは先ほど互いに計算した cAcB を共有します (これらの数は盗聴されても良い。)。
    • A さんは cB, sA, p を使って次の数を計算します。
      cBsA mod p
    • B さんは cA, sB, p を使って次の数を計算します。
      cAsB mod p
    これらの数は等しく
    k = cBsA mod p = cAsB mod p = rsA × sB mod p
    となります。
この計算で生成した k が 2 人の共通鍵です。なお、 p, r, cA, cB は盗聴されても問題はありません。これらが盗聴されたとしても、 k を求めるには次の方程式を満たす xy の組を少なくとも 1 組見つけなければなりません。 (それが sA, sB と一致するとは限りません。)
cBx mod p = cAy mod p
これを x, y について解くことは離散対数問題に帰着します。離散対数問題の有効な解法は 2011 年現在見つかっていません。よって、総当り法などを用いて O(p2) (かな?) の計算をしなければなりません。といっても、 p が小さければ大した計算量にはならないですね。

DH 法の安全性を保障するには p, sA, sB を十分大きくする必要があります。 2011 年現在では大きさは 2048 ビット (256 バイト) の整数 (0 ~ 22048 - 1 ≒ 3.2×10616) となっています。 double 型の近似でも 22048 は表現できませんね。正直こんなのを解析するにはスパコンを常時稼動させないと無理じゃないですか?

§1.2 DH 法の具体値例

§1.1 では文字式を用いて一般的に表しましたが、正直書いた私でも後で読み直すと混乱します。なので、適当な具体値をとって計算してみましょう。
  1. 共有する素数 (p) を 67, 自然数 (r) を 2 としてみます。
    p = 67
    r = 2
    • A さんは秘密の数 (sA) として 49 を選んだとします。
      sA = 49
      このとき B さんに送る数 (cA) は 57 となります。
      cA = rsA mod p = 249 mod 67 = 57
    • B さんは秘密の数 (sB) として 60 を選んだとします。
      sB = 60
      このとき A さんに送る数 (cB) は 22 となります。
      cB = rsB mod p = 260 mod 67 = 22
  2. A さんと B さんはそれぞれが計算した数 (cA = 57, cB = 22) を教え合います。
    • A さんは B さんから受け取った数 (cB = 22) と秘密の数 (sA = 49) を使ってキー (k) を計算します。
      k = cBsA mod p = 2249 mod 67 = 59
    • B さんは A さんから受け取った数 (cA = 57) と秘密の数 (sB = 60) を使ってキー (k) を計算します。
      k = cAsB mod p = 5760 mod 67 = 59
    こうして A さんと B さんは共通鍵 59 を共有することに成功しました。

通信路上で攻撃者 C さんがパケットを盗聴していました。 C さんは次の情報を盗みました。
p = 67, r = 2, cA = 57, cB = 22
これらから A さんと B さんの共通鍵 k を知りたいようです。
k を知るには次の方程式を満たす x, y の組を少なくとも 1 組求めなければなりません。 (それが sA, sB と一致するとは限りません。)
22x mod 67 = 57y mod 67
あなたは解けますか? 少なくとも解析的には求めようがないと思います。まあ、この程度なら総当り法を使えば (67 - 1)2 = 4356 回の計算で求まるので、プログラムを作れば見つかりますけどね。

§1.3 DH 法ごっこ

せっかくだから DH 法で遊んでみましょう。 JavaScript で簡単な DH 法をするプログラムを作りました。計算可能な数の範囲は狭いので実用性はありません。あくまで数遊び程度に思ってください。保障できる数の範囲は 2 ~ 46337 です。 (それ以上でもある程度は正しく共通鍵を得られているようです[*1]。 double 型の範囲のおかげでしょうか。)
共通設定
素数
基数
A
秘密の数
教える/教わる数
B
秘密の数
教える/教わる数
共通鍵
A
B


脚注
*1:
93847549 くらいまではうまくいっている模様。それより大きいとエラトステネスの篩をするときに配列のサイズが大きすぎてブラウザに止められて確認できませんでした。
2011年11月6日追記:素数判定アルゴリズムをフェルマーテスト (確率的アルゴリズム) にした結果、 94906703 くらいまでできるようになりました。
スポンサーサイト
コメント















 管理者にだけ表示を許可する

トラックバック
 
http://rexpit.blog29.fc2.com/tb.php/46-b2c8629b
最新記事
最新コメント
FC2カウンタ
欲しい
最近買ったもの
Amazon 検索
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。