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

楕円曲線ElGamal暗号の鍵生成・暗号化・復号を、DDH仮定への安全性帰着、展性（malleability）とIND-CCA2非充足の実演、メッセージ符号化問題まで含めて解説。Pythonで実際に攻撃コードを実行して検証します。

18 min read

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

本記事では、鍵生成・暗号化・復号の手順に加えて、次の3点を実際に動くコードで確認します。

  1. なぜ安全なのか: 意味論的安全性 (IND-CPA) が DDH (Decisional Diffie-Hellman) 仮定にどう帰着するか、帰着の議論そのものを追う。
  2. なぜ「それだけでは」安全とはいえないのか: EC ElGamalは展性 (malleability) を持ち、IND-CCA2安全ではない。秘密鍵を知らない攻撃者が暗号文を「意味のある形で」改ざんできることを、実際に攻撃コードを実行して示す。
  3. メッセージ符号化の落とし穴: 平文を曲線上の点として符号化する方式と、共有点をハッシュしてXORマスクする方式（ECIESに近い実務的な方式）の違いと、それぞれの脆弱性。

鍵生成 (Key Generation)

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

を計算します（\(xG\) は楕円曲線上のスカラ倍算）。

  • 秘密鍵: \(x\)
  • 公開鍵: \((E, G, Y)\)

暗号化：2つの方式

EC ElGamalには、平文の扱い方が異なる2つの標準的な変種があります。この違いが、後述する展性攻撃の形にも直結するので、両方を区別して扱います。

方式A: メッセージを点として符号化する古典的ElGamal

平文そのものを曲線上の点 \(M\) として符号化できたと仮定すると、暗号化は次の通りです。

  1. 一時的な乱数 \(r\) を \(1 \le r < n\) の範囲からランダムに選択します。
  2. \(C_1 = rG\) を計算します。
  3. 共有点 \(rY\) を計算し、平文の点に加算します:
\[ C_2 = M + rY \tag{2} \]
  1. 暗号文は \((C_1, C_2)\) のペアです。

復号は、受信者が秘密鍵 \(x\) を使って共有点を再現し、引き算で \(M\) を取り戻します。

\[ M = C_2 - xC_1 \tag{3} \]

これは \(xC_1 = x(rG) = r(xG) = rY = \) 暗号化時に足した点、という関係（可換性）から成り立ちます。

この方式の特徴は、暗号文が平文の点としての加法構造をそのまま保持する（\(C_2\) が \(M\) に対して線形）ことです。これは効率的な準同型演算を可能にする一方、後述するように展性の温床になります。

方式B: 共有点をハッシュしてXORマスクする方式（実務でよく使われる）

任意の長さ・任意の内容のバイト列を暗号化したい場合、平文を曲線上の点に符号化するのは（後述するように）自明ではありません。そこで実務では、共有点から擬似ランダムなマスクを導出し、平文とXORする方式がよく使われます（ECIES: Elliptic Curve Integrated Encryption Schemeに近い構成）。

  1. 一時的な乱数 \(r\) を選び、\(C_1 = rG\) を計算します。
  2. 共有点 \(V = rY\) を計算します（\(V = rY = r(xG) = x(rG) = xC_1\) ）。
  3. \(V\) から鍵導出関数（KDF、ここではSHA-256）でマスクを作ります:
\[ \text{mask} = \mathrm{SHA256}(V_x) \tag{4} \]
  1. 平文 \(m\) （バイト列）をマスクとXORします:
\[ C_2 = m \oplus \text{mask} \tag{5} \]
  1. 暗号文は \((C_1, C_2)\) です。

この記事の初版のコードは、\(V\) のx座標 \(v_x\) を「そのまま」マスクとして使い (\(c = v_x \oplus m\) )、ハッシュを挟んでいませんでした。 これは危険です。x座標は群の構造を反映した代数的な値であり、一様ランダムなビット列であるという保証がありません（例えば特定のビットにバイアスがある、あるいは複数の暗号文間で相関が漏れる可能性がある）。ハッシュ関数を挟むことで、ランダムオラクルモデルの下で「予測不可能な一様ランダム値」とみなせるようになります。本記事の実装ではこの点を修正し、SHA-256を経由したマスクを使います。

復号 (Decryption)

暗号文 \((C_1, c)\) を復号するには、以下の手順を実行します（方式B）。

  1. 受信者は自身の秘密鍵 \(x\) を使い、\(V' = xC_1\) を計算します。
  2. 暗号化の手順で見たように \(V' = V\) となるため、\(\text{mask}' = \mathrm{SHA256}(V'_x) = \text{mask}\) です。
  3. \(m = c \oplus \text{mask}'\) を計算し、元の平文 \(m\) を復元します。

方式Aの復号は式 (3) の通りです。

安全性：なぜDDHに帰着するのか

IND-CPA（選択平文攻撃に対する識別不可能性）

「意味論的に安全」とは、直感的には「暗号文を見ても、平文について（長さ以外）何もわからない」ということです。これを次のゲームで形式化します。

  1. チャレンジャーが鍵ペア \((x, Y=xG)\) を生成し、\(Y\) を攻撃者 \(\mathcal{A}\) に渡す。
  2. \(\mathcal{A}\) は2つの平文（点）\(M_0, M_1\) をチャレンジャーに送る。
  3. チャレンジャーはビット \(b \in \{0,1\}\) と乱数 \(r\) を選び、\(C_1 = rG,\ C_2 = M_b + rY\) を \(\mathcal{A}\) に返す。
  4. \(\mathcal{A}\) は \(b\) の推測値 \(b'\) を出力する。

\(\mathcal{A}\) のアドバンテージを

\[ \mathrm{Adv}^{\text{IND-CPA}}_{\mathcal{A}} = \left| \Pr[b' = b] - \frac{1}{2} \right| \tag{6} \]

と定義し、これがすべての効率的な \(\mathcal{A}\) に対して無視できるほど小さいとき、方式はIND-CPA安全と呼びます。

DDH仮定

DDH (Decisional Diffie-Hellman) 仮定とは、\(G\) を生成元とする位数 \(n\) の群において、次の2つの分布

\[ (G,\ aG,\ bG,\ abG) \quad \text{と} \quad (G,\ aG,\ bG,\ W) \tag{7} \]

（\(a, b\) は一様ランダムな整数、\(W\) は群上の一様ランダムな点）を効率的なアルゴリズムでは識別できない、という仮定です。ここで重要なのは、これは計算量的な仮定（\(abG\) を計算する CDH 仮定）よりも強い、識別（decisional）に関する仮定だという点です。CDHが破れなくても、\(abG\) かどうかを「当てる」ことだけならできてしまう群も存在しうるため、意味論的安全性の証明にはCDHではなくDDHが必要になります。

帰着の議論

主張: 方式Aの EC ElGamal が IND-CPA を破られるなら、DDHも解ける（対偶として、DDHが困難なら方式AはIND-CPA安全）。

IND-CPAを優位性 \(\varepsilon\) で破る攻撃者 \(\mathcal{A}\) が存在すると仮定し、これを使ってDDH識別器 \(\mathcal{D}\) を構成します。

  1. \(\mathcal{D}\) はDDHチャレンジ \((G, A=aG, B=bG, W)\) を受け取る（\(W\) は \(abG\) か一様ランダムな点のいずれか、\(\mathcal{D}\) はどちらか知らない）。
  2. \(\mathcal{D}\) は公開鍵を \(Y := A\) とおき（\(x = a\) に相当。\(\mathcal{D}\) 自身は \(a\) を知らなくてよい）、\(\mathcal{A}\) に \(Y\) を渡す。
  3. \(\mathcal{A}\) が平文 \(M_0, M_1\) を返す。
  4. \(\mathcal{D}\) はビット \(b\) を一様ランダムに選び、\(C_1 := B\) （\(r = b\) に相当。ここでも \(b\) の値自体は不要）、
\[ C_2 := M_b + W \tag{8} \]

とした暗号文 \((C_1, C_2)\) を \(\mathcal{A}\) に渡す。

  1. \(\mathcal{A}\) が推測 \(b'\) を返す。\(b' = b\) なら \(\mathcal{D}\) は「\(W = abG\) （実DHタプル）」と判定し、そうでなければ「\(W\) はランダム」と判定する。

解析:

  • \(W = abG\) の場合: \(C_1 = B = rG\) 、\(C_2 = M_b + abG = M_b + a(bG) = M_b + xC_1 = M_b + rY\) となり、これは正真正銘のElGamal暗号文です。したがって \(\mathcal{A}\) の視点は本物のIND-CPAゲームと完全に一致し、\(\Pr[b'=b \mid W \text{real}] = \frac{1}{2} + \varepsilon\) 。
  • \(W\) が一様ランダムな点の場合: \(C_2 = M_b + W\) は、\(W\) が \(M_b\) と独立な一様ランダム点であるため、\(b\) の値によらずそれ自体が一様ランダムな点になります（群上の「ワンタイムパッド」）。よって \(C_2\) は \(b\) について一切の情報を持たず、\(\Pr[b'=b \mid W \text{random}] = \frac{1}{2}\) ちょうど。

したがって \(\mathcal{D}\) のDDHに対するアドバンテージは

\[ \left|\Pr[b'{=}b \mid \text{real}] - \Pr[b'{=}b \mid \text{random}]\right| = \left|\left(\frac{1}{2}+\varepsilon\right) - \frac{1}{2}\right| = \varepsilon \tag{9} \]

となり、\(\mathcal{A}\) の優位性 \(\varepsilon\) がそのまま \(\mathcal{D}\) のDDH優位性に転写されます。DDHが困難（\(\varepsilon\) が無視できるほど小さい）と仮定する限り、IND-CPAを破る攻撃者は存在し得ません。これがDDHへの帰着の中身です。

方式B（ハッシュXOR）の安全性は、ランダムオラクルモデルの下でのHash-DH仮定（\(\mathrm{SHA256}(rY)\) がDHタプルの一部から作られていることを利用しても一様ランダムから識別できない、というDDHの強化版）に帰着します。実務のECIESの安全性証明もこの形をとります。

展性 (Malleability) とIND-CCA2非充足

上の議論は「暗号文を見ても平文が分からない」（IND-CPA）ことしか保証しません。「暗号文を、平文の情報を知らないまま、意味のある形で改ざんできるか」は全く別の問題です。EC ElGamalは、方式A・方式Bともにこの意味で展性 (malleable) を持ちます。

IND-CCA2とは

IND-CCA2（適応的選択暗号文攻撃に対する識別不可能性）は、IND-CPAゲームに加えて、攻撃者が（チャレンジ暗号文以外の）任意の暗号文を復号オラクルに投げて平文を得られる、という強い攻撃モデルです。ElGamalはこのモデルの下では安全ではありません。理由は単純で、方式Aは加法に関して準同型だからです。

なぜ展性を持つか：準同型構造

方式Aの暗号文 \((C_1, C_2) = (rG,\ M + rY)\) に対し、秘密鍵を知らない攻撃者が、任意の既知の点 \(\Delta\) を選んで

\[ C_2' = C_2 + \Delta \tag{10} \]

とすると、\((C_1, C_2')\) は \(M + \Delta\) の正当な暗号文になります。復号すると

\[ C_2' - xC_1 = (C_2 + \Delta) - xC_1 = (M + rY - xC_1) + \Delta = M + \Delta \tag{11} \]

となり、受信者は改ざんに気づかず \(M + \Delta\) を正しい平文として受け取ってしまいます。攻撃者は \(M\) の値を一切知らずに、これを行えます。

方式Bも同様の問題を持ちます。\(C_2 = m \oplus \text{mask}\) に対し、攻撃者が既知のビット列 \(e\) を選んで \(C_2' = C_2 \oplus e\) とすると、復号結果は \(m \oplus e\) になります。XORはビットごとに独立なので、攻撃者はメッセージの特定のビットだけを狙って反転できます。これは古典的な「MACなしのストリーム暗号／ワンタイムパッド」に共通する脆弱性で、パディングオラクル攻撃系統の遠い親戚です（後述）。

これらは実際にコードで再現できます（後述の実装セクション参照）。この性質があるため、生のElGamalは決してそのまま使ってはいけません。実務では、MAC（メッセージ認証コード）を付与するか、Fujisaki-Okamoto変換のようなIND-CCA2化変換を通してから使う必要があります。

メッセージ符号化の問題

方式Aを使うには、平文を曲線上の点として符号化する必要があります。しかし、任意のビット列を曲線上の点へ単射的かつ効率的に埋め込む一般的な方法は存在しません。

曲線 \(y^2 = x^3+ax+b \pmod p\) 上の点の数はおよそ \(p\) 個ですが、与えられた \(x\) 座標候補に対して \(x^3+ax+b\) が平方剰余（QR）である確率はおよそ \(1/2\) です。つまり、素朴に \(x\) 座標を平文の数値として使おうとしても、約半数の値は曲線上に対応する点を持ちません。

Koblitzの確率的符号化法は、この問題への古典的な対処法です。平文 \(m\) を直接 \(x\) 座標にする代わりに、\(x = mK + j\) （\(K\) は十分大きな定数、\(j = 0, 1, 2, \dots\) ）を順に試し、曲線上に点が存在する最初の \(j\) を使います。失敗確率はおよそ \(2^{-j}\) で指数的に減少するため、\(j\) を数十試せば実用上ほぼ確実に成功します。ただし、\(m\) を復元するには \(x\) 座標から \(\lfloor x/K \rfloor\) を計算するだけでよく、\(j\) の情報は捨てられます。この方式は実装が煩雑な上、\(K\) の選び方次第でメッセージ空間が制限されるという欠点があります。

これに対し、方式B（ハッシュXOR、ECIES的アプローチ）は、平文を曲線上の点として符号化する必要が一切ないという実務上の大きな利点があります。共有点はあくまで「マスクを導出するための種」として使われ、平文は任意のバイト列のままで構いません。トレードオフは、方式Aが持っていた（暗号文どうしの）代数的な加法構造を失う代わりに、任意長・任意内容のデータを直接扱える柔軟性を得る、という点です。

落とし穴: 方式Bにパディング（例えばPKCS#7のようなブロックパディング）を後付けし、かつ「パディングが正しいかどうか」を復号側がエラーとして外部に漏らしてしまうと、古典的なパディングオラクル攻撃が成立します。攻撃者は、上述のビット反転による展性を使って暗号文を少しずつ改ざんし、パディング検証の成否（エラーの有無や応答時間の違い）をオラクルとして使うことで、MACなしに平文を1バイトずつ復元できてしまいます（Vaudenay型攻撃の一般形）。教訓は同じです：整合性検証（MAC）なしに暗号文を復号処理に通してはならない、特にその結果（成功/失敗、平文の中身、タイミング）を外部に一切漏らしてはいけません。

Pythonによる実装

素朴な実装（学習用・注意点）

以下のプログラムは、楕円曲線ElGamal暗号の基本的な概念を理解するために、大幅に簡略化された最初のバージョンです。この実装のスカラ倍算 scalar_mult は、点の加算を実装していないため、実際には \(k \cdot P\) ではなく \(2^k \cdot P\) を計算しています。 暗号化と復号の両方が同じ（誤った）関数を使っているために、たまたま一貫した結果が得られているだけで、一般の \(k\) に対して正しいスカラ倍算にはなっていません。モジュラ逆数の計算もブルートフォースの非効率な実装であり、実際の暗号通信には全く使用できません。

# --- パラメータ設定（非常に小さい素数体上の楕円曲線） ---
# 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()

正しい実装：点加算とダブル・アンド・アッド法

以降のすべての検証（正しいラウンドトリップ・展性攻撃・ビット反転攻撃）では、上記の問題を修正し、実在の曲線 secp256k1（Bitcoin/Ethereumで使われる曲線）上で、点加算とダブル・アンド・アッド法による正しいスカラ倍算を実装したものを使います。

import hashlib
import secrets

# --- secp256k1 のドメインパラメータ（実際に使われている曲線） ---
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G = (Gx, Gy)
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # Gの位数

INF = None  # 無限遠点

def point_add(P, Q):
    """曲線 y^2 = x^3 + a*x + b (mod p) 上の点の加算"""
    if P is INF:
        return Q
    if Q is INF:
        return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return INF
    if P == Q:
        s = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
    else:
        s = (y2 - y1) * pow((x2 - x1) % p, -1, p) % p
    x3 = (s * s - x1 - x2) % p
    y3 = (s * (x1 - x3) - y1) % p
    return (x3, y3)

def scalar_mult(k, P):
    """ダブル・アンド・アッド法で k*P を計算する。O(log k) 回の点演算で済む。"""
    result = INF
    addend = P
    while k:
        if k & 1:
            result = point_add(result, addend)
        addend = point_add(addend, addend)
        k >>= 1
    return result

def is_on_curve(P):
    if P is INF:
        return True
    x, y = P
    return (y * y - (x * x * x + a * x + b)) % p == 0

assert is_on_curve(G)
assert scalar_mult(n, G) is INF  # Gの位数がnであることの確認

鍵生成とラウンドトリップ検証（方式B: ハッシュXOR）

x = 0xBB15EA4851F6292D93631DB76DF9DDC9A76869A2EDAAABBE8835EF96C04F7DD  # 秘密鍵（実運用ではsecrets.randbelow(n-1)+1で生成）
Y = scalar_mult(x, G)  # 公開鍵 Y = xG

print(f"private key x   = {hex(x)}")
print(f"public key  Y   = ({hex(Y[0])},\n                   {hex(Y[1])})")
print(f"Y on curve?     = {is_on_curve(Y)}")

def kdf(point):
    """共有点からSHA-256で擬似ランダムなマスクを導出"""
    return hashlib.sha256(point[0].to_bytes(32, "big")).digest()

def encrypt_xor(G, Y, message: bytes, r):
    C1 = scalar_mult(r, G)
    shared = scalar_mult(r, Y)          # V = rY
    mask = kdf(shared)
    full_mask = (mask * (len(message)//len(mask)+1))[:len(message)]
    C2 = bytes(m ^ k for m, k in zip(message, full_mask))
    return C1, C2

def decrypt_xor(C1, C2: bytes, x):
    shared = scalar_mult(x, C1)         # V' = xC1 = x(rG) = r(xG) = rY
    mask = kdf(shared)
    full_mask = (mask * (len(C2)//len(mask)+1))[:len(C2)]
    return bytes(c ^ k for c, k in zip(C2, full_mask))

plaintext = b"ATTACK AT DAWN!!"
r1 = 0xF6EB57BB07D59B72AEBAF7CEEB88833FC893E2D8728C4FFAC2954C4D56BD852F  # 一時乱数（実運用では毎回 secrets.randbelow(n-1)+1 で生成）
C1, C2 = encrypt_xor(G, Y, plaintext, r1)
recovered = decrypt_xor(C1, C2, x)

print(f"plaintext           = {plaintext!r}")
print(f"C1 = rG             = ({hex(C1[0])[:20]}..., {hex(C1[1])[:20]}...)")
print(f"C2 = m XOR H(rY)    = {C2.hex()}")
print(f"decrypted           = {recovered!r}")
print(f"round trip correct? = {recovered == plaintext}")

実行結果（実際にこのコードを動かした出力）:

private key x   = 0xbb15ea4851f6292d93631db76df9ddc9a76869a2edaaabbe8835ef96c04f7dd
public key  Y   = (0xdd6a3777a2a834f2afe8a8488141d67e4e6f43692db6e9e628c066b495e3c981,
                   0x40e790c06c66f9a8ea6653ccaab2b25a4ec99eecc006b194d1de86c5c1d9bfc8)
Y on curve?     = True

plaintext            = b'ATTACK AT DAWN!!'
C1 = rG              = (0xe61b9dc468b76bcbde..., 0xa8358318f6eb4e8a66...)
C2 = m XOR H(rY)     = 23bc2f6ccd3f25506e5187ecb95ddc02
decrypted            = b'ATTACK AT DAWN!!'
round trip correct?  = True

正しいスカラ倍算に修正した実装で、secp256k1という実在の曲線上、暗号化→復号のラウンドトリップが完全に元の平文と一致することを確認できました。

攻撃1: ビット反転攻撃（方式B、MACなし）

秘密鍵はおろか、平文も一切見ずに、暗号文 C2 の1ビットだけを反転させると、復号結果の対応する1ビットだけが反転します。これはXORの線形性そのものであり、\(H(V)\) をハッシュしていても防げません（ハッシュはマスクの予測不可能性を保証するだけで、XORそのものの可展性は消えません）。

byte_index, bit_index = 7, 2
tampered = bytearray(C2)
tampered[byte_index] ^= (1 << bit_index)   # 攻撃者は鍵も平文も知らない
C2_tampered = bytes(tampered)

tampered_plain = decrypt_xor(C1, C2_tampered, x)

print(f"original C2 byte[{byte_index}]  = {C2[byte_index]:#04x} ({C2[byte_index]:08b})")
print(f"tampered C2 byte[{byte_index}]  = {C2_tampered[byte_index]:#04x} ({C2_tampered[byte_index]:08b})")
print(f"original plaintext byte[{byte_index}] = {plaintext[byte_index]:#04x} ({chr(plaintext[byte_index])!r})")
print(f"decrypted tampered byte[{byte_index}]  = {tampered_plain[byte_index]:#04x} ({chr(tampered_plain[byte_index])!r})")

other_before = plaintext[:byte_index] + plaintext[byte_index+1:]
other_after = tampered_plain[:byte_index] + tampered_plain[byte_index+1:]
observed_flip = plaintext[byte_index] ^ tampered_plain[byte_index]
print(f"other bytes unchanged?                 = {other_before == other_after}")
print(f"predicted flipped bit == observed flipped bit? {observed_flip == (1 << bit_index)}")

実行結果:

original C2 byte[7]  = 0x50 (01010000)
tampered C2 byte[7]  = 0x54 (01010100)
original plaintext byte[7] = 0x41 ('A')
decrypted tampered byte[7]  = 0x45 ('E')
other bytes unchanged?                 = True
predicted flipped bit == observed flipped bit? True

平文の8バイト目 'A' (0x41) は、ビット2だけを反転させたことで 'E' (0x45) になりました。他のバイトは一切変化していません。受信者はこの改ざんを検知する手段を一切持ちません — これがMACなしのElGamal（や、より一般にMACなしのストリーム暗号）を実運用に使ってはいけない理由です。

攻撃2: 準同型置換攻撃（方式A、点への加算）

方式A（メッセージを点として符号化するElGamal）では、攻撃者は選んだ点 \(\Delta\) を暗号文に加算するだけで、平文に同じ \(\Delta\) を加算した暗号文を、秘密鍵なしに作れます。

def encrypt_point(G, Y, M, r):
    C1 = scalar_mult(r, G)
    C2 = point_add(M, scalar_mult(r, Y))   # C2 = M + rY
    return C1, C2

def decrypt_point(C1, C2, x):
    shared = scalar_mult(x, C1)             # rY
    neg_shared = (shared[0], (-shared[1]) % p)
    return point_add(C2, neg_shared)        # C2 - rY = M

m_int = 424242                  # 平文を m_int * G という点として符号化
M = scalar_mult(m_int, G)
print(f"plaintext point M = {m_int} * G")

r2 = 0xE69396455486FDA66A933A72E87CE3DC17F928C7E9E875F71ECB53841918F22E  # 一時乱数
C1m, C2m = encrypt_point(G, Y, M, r2)
print(f"C1              = ({hex(C1m[0])[:20]}..., {hex(C1m[1])[:20]}...)")
print(f"C2 = M + rY     = ({hex(C2m[0])[:20]}..., {hex(C2m[1])[:20]}...)")

decrypted_M = decrypt_point(C1m, C2m, x)
print(f"decrypt(C1,C2) == M ? {decrypted_M == M}")

delta_int = 1000                # 攻撃者が選ぶシフト量（平文は知らない）
Delta = scalar_mult(delta_int, G)
C2m_prime = point_add(C2m, Delta)          # 秘密鍵なしで実行できる操作（攻撃者はM, delta_intを知らなくてよい）
print(f"C2' = ({hex(C2m_prime[0])[:20]}..., {hex(C2m_prime[1])[:20]}...)")

decrypted_M_prime = decrypt_point(C1m, C2m_prime, x)
expected = scalar_mult(m_int + delta_int, G)
print(f"decrypt(C1, C2') == (m + delta) * G ? {decrypted_M_prime == expected}")
print(f"decrypt(C1, C2') == original M ?      {decrypted_M_prime == M}")

実行結果:

plaintext point M = 424242 * G
C1              = (0x99c3dea5defae92ef3..., 0x1a2a447f3a3384cca2...)
C2 = M + rY     = (0x56cf3f830713ec3320..., 0x206f7166d51f59d3bb...)
decrypt(C1,C2) == M ? True

attacker computes C2' = C2 + Delta, Delta = 1000 * G (no private key used)
C2' = (0xa8111653ab30df5623..., 0x51e2d72086bc0b3c8e...)
decrypt(C1, C2') == (m + delta) * G ? True
decrypt(C1, C2') == original M ?      False

秘密鍵を一切使わずに \(C_2\) を書き換えた結果、受信者が正当に復号したはずの平文が \(M\) から \(M + \Delta = (424242 + 1000)G\) に化けました。復号処理自体はエラーを返さず、あたかも正しい暗号文であるかのように「別の平文」を返す点が、CCA2攻撃者にとって強力な足がかりになります（例えば、平文が金額を表す点だった場合、攻撃者は既知の額だけ金額を吊り上げた暗号文を作れてしまいます）。

まとめ

  • EC ElGamalの意味論的安全性（IND-CPA）は、DDH仮定への帰着によって証明できる。攻撃者が暗号文を区別できるなら、DH組と乱数組を区別できてしまう、という帰着の構造そのものが核心。
  • しかしDDHが困難であることは、改ざん耐性（IND-CCA2）を何ら保証しない。方式A（点符号化）は \(C_2' = C_2 + \Delta\) という準同型構造により、方式B（ハッシュXOR）はXORのビット単位の線形性により、秘密鍵なしで平文を狙って改変できる。これは実際に動くコードで確認した。
  • 任意のビット列を曲線上の点に効率的に埋め込む一般的な方法は存在しない（Koblitzの確率的符号化はあるが煩雑）。実務ではハッシュXOR方式（ECIES的構成）が好まれるが、整合性保護（MAC）なしでは常に展性を持つ。
  • 実運用でElGamal系の構成を使うなら、MACを付与するか、Fujisaki-Okamoto変換などでIND-CCA2安全に変換してから使う。生のElGamalをそのままネットワーク越しの通信に使ってはならない。

関連記事

関連ツール

参考文献

  • ElGamal, T. (1985). “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms”. CRYPTO ‘84.
  • Tsiounis, Y., & Yung, M. (1998). “On the Security of ElGamal Based Encryption”. PKC ‘98.（DDHへの帰着の標準的な扱い）
  • Fujisaki, E., & Okamoto, T. (1999). “Secure Integration of Asymmetric and Symmetric Encryption Schemes”. CRYPTO ‘99.（IND-CCA2化変換）
  • Koblitz, N. (1987). “Elliptic Curve Cryptosystems”. Mathematics of Computation, 48(177), 203–209.（確率的メッセージ符号化）
  • Vaudenay, S. (2002). “Security Flaws Induced by CBC Padding”. EUROCRYPT 2002.（パディングオラクル攻撃の一般形）
  • Certicom Research (2010). “SEC 2: Recommended Elliptic Curve Domain Parameters”. Version 2.0.（secp256k1のパラメータ）

この記事に関連する無料ツール

DevToolBox Moving Average Calculator SMA/EMA/WMA をブラウザで即座に計算 DevToolBox JSON Formatter JSONを整形・圧縮・バリデーション DevToolBox Regex Tester 正規表現をリアルタイムテスト

関連記事