楕円曲線ElGamal暗号の原理とPythonによる簡易実装

3 min read

ElGamal暗号は、離散対数問題の困難性を安全性の根拠とする公開鍵暗号の一つです。これを楕円曲線上で定義したものが、楕円曲線ElGamal暗号です。

鍵生成 (Key Generation)

  1. パラメータの選択: 楕円曲線 $E$ と、その曲線上の点であるベースポイント $G$（位数 $l$）を決定します。これらは公開されます。
  2. 秘密鍵の生成: 秘密鍵となる整数 $x$ を、$1 \le x < l$ の範囲からランダムに選択します。
  3. 公開鍵の計算: 秘密鍵 $x$ とベースポイント $G$ から、公開鍵となる点 $Y = xG$ を計算します。（$xG$ は楕円曲線上のスカラ倍算を表します）
  • 秘密鍵: $x$
  • 公開鍵: $(E, G, Y)$

暗号化 (Encryption)

平文 $m$ を暗号化するには、以下の手順を実行します。

  1. 一時的な乱数 $r$ を $1 \le r < l$ の範囲からランダムに選択します。
  2. $U = rG$ を計算します。
  3. $V = rY$ を計算します。この点 $V$ は送信者と受信者で共有される秘密情報となります。（$V = rY = r(xG) = x(rG) = xU$）
  4. $V$ のx座標 $v_x$ を使い、平文 $m$ をマスク（暗号化）します: $c = v_x \oplus m$ （$\oplus$ は排他的論理和）。
  5. 暗号文は、点の $U$ とマスクされたメッセージ $c$ のペア $(U, c)$ となります。

復号 (Decryption)

暗号文 $(U, c)$ を復号するには、以下の手順を実行します。

  1. 受信者は自身の秘密鍵 $x$ を使い、$V’ = xU$ を計算します。
  2. 暗号化の手順で見たように、$V’ = V$ となるため、計算した点 $V’$ のx座標 $v’_x$ は、暗号化に使われた $v_x$ と一致します。
  3. $m = v’_x \oplus c$ を計算し、元の平文 $m$ を復元します。

Pythonによる簡易実装

【注意】 以下のプログラムは、楕円曲線ElGamal暗号の基本的な概念を理解するために、大幅に簡略化されています。特に、モジュラ逆数の計算やスカラ倍算の実装は非常に非効率かつ単純な方法で行っており、実際の暗号通信には全く使用できません。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

# --- パラメータ設定（非常に小さい素数体上の楕円曲線） ---
# y^2 = x^3 + ax + b (mod l)
a = 0
b = 1
l = 5 # 法（素数）

# ベースポイント G
g = [2, 2]

# --- 鍵生成 ---
# 秘密鍵 (本来は大きな乱数)
private_key = 3

# --- ユーティリティ関数 ---
def mod(x, y):
    """正の剰余を計算する"""
    return x % y

def inv_mod(x, y):
    """
    モジュラ逆数を計算する (ブルートフォースによる非効率な実装)
    yが素数の場合、フェルマーの小定理 (x^(y-2) mod y) を使う方が効率的。
    一般的には拡張ユークリッドの互除法を用いる。
    """
    for i in range(1, y):
        if (x * i) % y == 1:
            return i
    return -1 # 見つからない場合

def point_double(p):
    """楕円曲線上の点の2倍算 (P + P)"""
    # 傾き s = (3*px^2 + a) / (2*py)
    s_num = 3 * p[0] * p[0] + a
    s_den = 2 * p[1]
    s = mod(s_num * inv_mod(s_den, l), l)
    
    # 新しい点の座標
    x = mod(s * s - 2 * p[0], l)
    y = mod(s * (p[0] - x) - p[1], l)
    return [x, y]

def scalar_mult(k, p):
    """
    スカラ倍算 k * P を計算する (加算を繰り返す非効率な実装)
    実際の暗号では、繰り返し二乗法（バイナリ法）を点の加算に応用した
    「ダブル・アンド・アッド法」が用いられる。
    """
    # 注意: この簡易実装は、k * P ではなく 2^k * P を計算します。
    # これはElGamal暗号の要件を満たしません。
    # 正しい k * P の計算には、点の加算関数と、ダブル・アンド・アッド法などの
    # 適切なスカラ倍算アルゴリズムの実装が必要です。
    # このコードは、デモンストレーション目的で、kが小さい固定値の場合にのみ動作します。
    res = p
    for _ in range(k - 1):
        res = point_double(res)
    return res

def encrypt(G, Y, m):
    r = 3 # 本来は大きな乱数
    U = scalar_mult(r, G)
    V = scalar_mult(r, Y)
    # XORでメッセージをマスク
    c = V[0] ^ m # x座標を使用
    return U, c

def decrypt(U, c, key):
    V = scalar_mult(key, U)
    m = V[0] ^ c # x座標を使用
    return m

def main():
    # 公開鍵 Y = xG を計算
    public_key = scalar_mult(private_key, g)
    print(f"秘密鍵 x: {private_key}")
    print(f"公開鍵 Y: {public_key}")
    
    # 平文
    message = 4
    print(f"平文 m: {message}")
    
    # 暗号化
    U, c = encrypt(g, public_key, message)
    print(f"暗号文 (U, c): ({U}, {c})")
    
    # 復号
    decrypted_message = decrypt(U, c, private_key)
    print(f"復号されたメッセージ: {decrypted_message}")

if __name__ == "__main__":
    main()