DH鍵交換（Diffie-Hellman鍵交換）をpythonで確認

概要

DH鍵交換は、1976年にWhitfield DiffieとMartin Hellmanによって発表されたプロトコルである。このプロトコルでは、通信を行う2者がそれぞれ公開鍵と秘密鍵を生成し、公開鍵だけを相手に送信する。そして、自分の秘密鍵と受信した相手の公開鍵を使用して共通鍵を生成する。

このプロトコルを用いることにより、共通鍵を使い捨てすることができ、前方秘匿性を保持するために重要である。前方秘匿性とは、過去の通信から推測されることなく、将来の通信も安全に行えること。

アルゴリズム

import random

# 共通のパラメータ
g = 23  # 生成元
n = 5  # 素数

# アリスとボブがそれぞれ秘密の鍵を生成
p = 5  # 秘密の鍵のビット長
a = random.randint(1, (1 << p))  # アリスの秘密の鍵
b = random.randint(1, (1 << p))  # ボブの秘密の鍵

# アリスとボブが公開鍵を計算
A = (g ** a) % n
B = (g ** b) % n

# アリスとボブが共通の秘密鍵を計算
sA = (B ** a) % n
sB = (A ** b) % n

# 共通の秘密鍵を表示
print("共通の秘密鍵 sA:", sA)
print("共通の秘密鍵 sB:", sB)

公開鍵Aを盗聴できたとして攻撃者がaを計算しようとすると、総当たりにはo(2^p)の計算量が必要。

(a, g, n)からA=g^a mod nを求めるのは簡単だが、
(A, g, n)からg^a mod n = Aとなるaを求めるのは難しい。

g^a % n = A の逆変換を求めることが難しい性質を離散対数問題の性質とよぶ。

• アルゴリズム