エルガマル暗号

公開鍵 $h \equiv g^{x}$ を作り、 $(c_{1}, c_{2}) = (g^{k}, m h^{k})$ で暗号化し、 $m \equiv c_{2} (c_{1}^{x})^{- 1} (mod p)$ で復号できる。同じ $k$ が使い回されたとき、 $m_{2} \equiv m_{1} c_{2}^{'} c_{2}^{- 1} (mod p)$ から秘密鍵なしで平文を求められる

前提

ディフィー・ヘルマン鍵共有（大学数学暗号理論）
法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）

この技能までの道筋（26 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
n 進法（数学A 整数の性質）
繰り返し二乗法によるべき剰余（大学数学暗号理論）
ディフィー・ヘルマン鍵共有（大学数学暗号理論）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
ユークリッドの互除法（数学A 整数の性質）
1 次不定方程式の整数解（数学A 整数の性質）
法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）

説明

エルガマル暗号は、ディフィー・ヘルマン鍵共有のしくみを使った公開鍵暗号です。公開鍵があれば誰でも暗号化でき、秘密鍵を持つ人だけが復号できます。素数 $p$ と $g$ （ $1 < g < p$ ）を公開し、受信者は秘密鍵 $x$ から公開鍵 $h \equiv g^{x} (mod p)$ を作ります。送信者は平文 $m$ （ $1 \leq m \leq p - 1$ の整数）を毎回新しい乱数 $k$ で暗号文 $(c_{1}, c_{2})$ に変え、受信者は $x$ を使って $m$ を取り出します。さらに、同じ $k$ を使い回すと秘密鍵がなくても平文が漏れることも確かめます。

なぜそうしてよいのか

ディフィー・ヘルマン鍵共有で、受信者の秘密を $x$ 、送信者の秘密を $k$ とみなします。受信者の公開値は $h \equiv g^{x}$ 、送信者の公開値は $c_{1} \equiv g^{k}$ です。このとき両者が作れる共有鍵は $s \equiv h^{k} \equiv c_{1}^{x} \equiv g^{x k} (mod p)$ です。送信者はこの $s$ を「目隠し」として平文に掛け、 $c_{2} \equiv m s$ を送ります。受信者が $s$ を再現できるように、 $c_{1}$ も一緒に送ります。

受信者は自分の $x$ を使って $s \equiv c_{1}^{x}$ を計算できます。 $p$ は素数で、 $g$ は $p$ の倍数ではありません。そのため $s \equiv g^{x k}$ も $p$ の倍数ではなく、 $g cd (s, p) = 1$ となるので逆元 $s^{- 1} mod p$ が存在します。よって $c_{2} s^{- 1} \equiv m s s^{- 1} \equiv m (mod p)$ となり、平文が戻ります。 $1 \leq m \leq p - 1$ なので、 $m$ は余りとして一つに決まります。

安全性について、二つのことを区別しておきます。盗聴者が知っているのは $g, h \equiv g^{x}, c_{1} \equiv g^{k}$ です。復号するには、これらから $s \equiv g^{x k}$ を求める必要があります。この「 $g^{x}, g^{k}$ から $g^{x k}$ を求める問題」を計算ディフィー・ヘルマン問題といい、これが難しいことが、第三者に平文を求められないことの根拠です。一方、離散対数問題（ $h \equiv g^{x}$ から $x$ を求める問題）が易しいと、 $x$ が求まって誰でも復号できてしまいます。つまり離散対数の困難性は、秘密鍵 $x$ を求められないための条件であり、安全性に必要な条件です。ただし、 $x$ を求めずに $s$ を作る方法がないことまでは、これだけでは保証されません。

同じ $k$ で2つの平文 $m_{1}, m_{2}$ を暗号化すると、目隠し $s$ が共通になり、 $c_{2} \equiv m_{1} s$ 、 $c_{2}^{'} \equiv m_{2} s$ となります。 $1 \leq m_{1} \leq p - 1$ で $p$ は素数なので、 $g cd (m_{1}, p) = 1$ です。 $s$ も $p$ と互いに素なので、積 $c_{2} \equiv m_{1} s$ も $p$ の倍数ではありません。よって $c_{2}^{- 1} mod p$ と $m_{1}^{- 1} mod p$ はどちらも存在します。両式の比をとると $s$ が消えて $c_{2}^{'} c_{2}^{- 1} \equiv m_{2} m_{1}^{- 1}$ となります。したがって、 $m_{1}$ を知っている攻撃者は、秘密鍵なしで $m_{2} \equiv m_{1} c_{2}^{'} c_{2}^{- 1} (mod p)$ を計算できてしまいます。これが、 $k$ を毎回変えなければならない理由です。

手順

鍵を作る: 受信者は秘密鍵 $x$ （ $1 \leq x \leq p - 2$ ）を選ぶ。繰り返し二乗法で公開鍵 $h \equiv g^{x} (mod p)$ を計算し、 $(p, g, h)$ を公開する。
暗号化する: 送信者は毎回新しい乱数 $k$ （ $1 \leq k \leq p - 2$ ）を選ぶ。 $c_{1} \equiv g^{k}$ 、 $c_{2} \equiv m h^{k} (mod p)$ を計算して $(c_{1}, c_{2})$ を送る。
復号で目隠しを再現する: 受信者は $s \equiv c_{1}^{x} (mod p)$ を繰り返し二乗法で計算する（これは $h^{k}$ と等しい）。
逆元を求める: $g cd (s, p) = 1$ なので、拡張ユークリッドの互除法で $sy + p z = 1$ を解き、 $s^{- 1} \equiv y (mod p)$ を得る。
平文を取り出す: $m \equiv c_{2} s^{- 1} (mod p)$ を計算し、 $1$ 以上 $p - 1$ 以下の余りにする。
（ $k$ の使い回しを突く場合）同じ $k$ の暗号文 $c_{2}, c_{2}^{'}$ と既知の平文 $m_{1}$ を使う。 $c_{2} \equiv m_{1} s$ は $p$ と互いに素なので $c_{2}^{- 1} mod p$ が存在する。これを互除法で求め、 $m_{2} \equiv m_{1} c_{2}^{'} c_{2}^{- 1} (mod p)$ を計算する。

例題

エルガマル暗号で、公開パラメータを $p = 23$ 、 $g = 5$ 、受信者の秘密鍵を $x = 6$ とする。受信した暗号文 $(c_{1}, c_{2}) = (10, 14)$ を復号し、平文 $m$ （ $1 \leq m \leq 22$ ）を求めよ。

例題の解答

手順3（目隠しの再現）: $s \equiv 1 0^{6} (mod 23)$ を繰り返し二乗法で計算する。 $1 0^{2} = 100 \equiv 8$ 、 $1 0^{4} \equiv 8^{2} = 64 \equiv 18$ である。よって $1 0^{6} = 1 0^{4} \cdot 1 0^{2} \equiv 18 \cdot 8 = 144 \equiv 6 (mod 23)$ となり、 $s = 6$ である。

手順4（逆元）: $g cd (6, 23) = 1$ なので逆元は存在する。互除法を行うと $23 = 6 \cdot 3 + 5$ 、 $6 = 5 \cdot 1 + 1$ である。これを逆にたどると $1 = 6 - 5 = 6 - (23 - 6 \cdot 3) = 6 \cdot 4 - 23$ となる。よって $6^{- 1} \equiv 4 (mod 23)$ である（確かめ: $6 \cdot 4 = 24 \equiv 1$ ）。

手順5（平文の取り出し）: $m \equiv c_{2} s^{- 1} \equiv 14 \cdot 4 = 56 \equiv 56 - 46 = 10 (mod 23)$ 。

検算: 公開鍵は $h \equiv 5^{6} (mod 23)$ である。 $5^{2} \equiv 2$ 、 $5^{4} \equiv 4$ より $h \equiv 8$ となる。 $k = 3$ とすると $c_{1} \equiv 5^{3} = 125 \equiv 10$ 、 $h^{3} = 512 \equiv 6$ なので $c_{2} \equiv 10 \cdot 6 = 60 \equiv 14$ となり、受信した暗号文と一致する。よって $m = 10$ 。

答え: $10$

よくある誤り

復号で $h^{x}$ や $g^{x}$ を計算してしまう誤り。目隠しは $h^{k} \equiv g^{x k}$ であり、受信者が使えるのは $c_{1} \equiv g^{k}$ である。正しくは $s \equiv c_{1}^{x} (mod p)$ （例題では $1 0^{6} \equiv 6$ ）。
$c_{2}$ を $s$ で普通に割り算してしまう誤り（例: $14 \div 6$ は整数にならない）。正しくは逆元を掛けて、 $m \equiv c_{2} s^{- 1} \equiv 14 \cdot 4 \equiv 10 (mod 23)$ とする。
逆元を法 $p - 1$ で求めてしまう誤り。たとえば $6^{- 1} mod 22$ は、 $g cd (6, 22) = 2$ なので存在しない。平文の計算は法 $p$ で行うので、正しくは $6^{- 1} mod 23 = 4$ 。指数の $k$ や $x$ を扱うときの法 $p - 1$ と混同しないこと。
$k$ の使い回しで比の向きを逆にしてしまう誤り（ $m_{2} \equiv m_{1} c_{2} (c_{2}^{'})^{- 1}$ としてしまう）。 $c_{2} \equiv m_{1} s$ 、 $c_{2}^{'} \equiv m_{2} s$ なので、正しくは $m_{2} \equiv m_{1} c_{2}^{'} c_{2}^{- 1} (mod p)$ 。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

エルガマル暗号

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題