暗号理論の問題

難易度 3期末試験の応用レベル大学数学暗号理論

素数 $p = 101$ と法 $101$ の原始根 $g$ を用いるエルガマル暗号を考える。受信者の秘密鍵を $a$ 、公開鍵を $h \equiv g^{a} (mod p)$ とする。平文 $m$ （ $1 \leq m \leq 100$ の整数）は、送信者が整数 $k$ （ $1 \leq k \leq 99$ ）を選び
$c_{1} \equiv g^{k}, c_{2} \equiv m h^{k} (mod p) (0 \leq c_{1}, c_{2} \leq 100)$
として暗号文 $(c_{1}, c_{2})$ に暗号化される。

送信者は、誤って同じ $k$ を使い回して 2 つの平文 $m_{1}, m_{2}$ を暗号化し、暗号文 $(14, 19)$ と $(14, 45)$ をこの順に送った。盗聴者は $1$ つ目の平文が $m_{1} = 20$ であることを知っている。 $2$ つ目の平文 $m_{2}$ を求めよ。

この問題で使うもの

エルガマル暗号（説明と入口の問題）
法 $m$ での逆元（拡張ユークリッドの互除法）（説明と入口の問題）

この問題を解けるようになるまで（27 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

同じ $k$ を使うと、2 つの暗号文の第 2 成分には同じ数 $h^{k}$ が掛けられている。秘密鍵 $a$ や $k$ を求める必要はない。

ヒント 2

$19 \equiv m_{1} h^{k}$ , $45 \equiv m_{2} h^{k} (mod 101)$ から $h^{k}$ を消去すると $m_{2} \equiv 45 \cdot 1 9^{- 1} \cdot m_{1} (mod 101)$ 。

ヒント 3

ユークリッドの互除法で $1 9^{- 1} \equiv 16 (mod 101)$ が求まる。あとは $45 \cdot 16 \cdot 20$ を法 $101$ で計算する。

答えと解説

答えを見る

58

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

2 つの暗号文は同じ $k$ で作られているので、第 1 成分はどちらも $c_{1} \equiv g^{k} \equiv 14$ で等しく、第 2 成分には同じマスク $s \equiv h^{k} (mod 101)$ が掛けられている。したがって
$19 \equiv m_{1} s, 45 \equiv m_{2} s (mod 101) .$

$s$ を消去する. $101$ は素数で $19 \neq \equiv 0$ なので、 $19$ は法 $101$ で逆元をもつ。第 1 式から $s \equiv 19 m_{1}^{- 1}$ を第 2 式に代入すると $45 \equiv m_{2} \cdot 19 m_{1}^{- 1}$ 、すなわち
$m_{2} \equiv 45 \cdot 1 9^{- 1} \cdot m_{1} (mod 101) .$

$1 9^{- 1}$ の計算. ユークリッドの互除法より $101 = 5 \cdot 19 + 6$ 、 $19 = 3 \cdot 6 + 1$ 。逆にたどると
$1 = 19 - 3 \cdot 6 = 19 - 3 (101 - 5 \cdot 19) = 16 \cdot 19 - 3 \cdot 101$
なので $1 9^{- 1} \equiv 16 (mod 101)$ （実際 $19 \cdot 16 = 304 = 3 \cdot 101 + 1$ ）。

$m_{2}$ の計算.
$45 \cdot 16 = 720 = 7 \cdot 101 + 13 \equiv 13, 13 \cdot 20 = 260 = 2 \cdot 101 + 58 \equiv 58.$
よって $m_{2} \equiv 58 (mod 101)$ で、 $1 \leq m_{2} \leq 100$ より $m_{2} = 58$ 。

検算. $20 \cdot 5 = 100 \equiv - 1$ より $2 0^{- 1} \equiv - 5 \equiv 96$ なので $s \equiv 19 \cdot 96 = 1824 = 18 \cdot 101 + 6 \equiv 6$ 。実際 $20 \cdot 6 = 120 \equiv 19$ 、 $58 \cdot 6 = 348 = 3 \cdot 101 + 45 \equiv 45$ で、与えられた暗号文と一致する。

このように、エルガマル暗号で $k$ を使い回すと、1 つの平文が漏れただけで、秘密鍵 $a$ も $k$ も知らずに他の平文が復元されてしまう。

別解

同じ $k$ を使っているので、2 つの暗号文の $c_{1}$ は等しく（どちらも $14$ ）、 $h^{k}$ も共通である。それを $s = h^{k} mod 101$ とおくと、 $c_{2} \equiv m s (mod 101)$ である。

よって $19 \equiv 20 s$ 、 $45 \equiv m_{2} s (mod 101)$ 。辺々の比をとると（ $s \neq \equiv 0$ 、 $c_{2} = 19 \neq \equiv 0$ ）
$\frac{m _{2}}{m _{1}} \equiv \frac{45}{19} (mod 101) \Rightarrow m_{2} \equiv 20 \cdot 45 \cdot 1 9^{- 1} (mod 101) .$

$1 9^{- 1}$ を拡張ユークリッドの互除法で求める。 $101 = 5 \cdot 19 + 6$ 、 $19 = 3 \cdot 6 + 1$ より
$1 = 19 - 3 \cdot 6 = 19 - 3 (101 - 5 \cdot 19) = 16 \cdot 19 - 3 \cdot 101$ 。よって $1 9^{- 1} \equiv 16$ 。確認: $19 \cdot 16 = 304 = 3 \cdot 101 + 1$ 。

$20 \cdot 45 = 900 = 8 \cdot 101 + 92$ より $900 \equiv 92$ 。 $92 \cdot 16 = 1472 = 14 \cdot 101 + 58$ より $m_{2} \equiv 58$ 。

検算: $19 \cdot 58 = 1102 = 10 \cdot 101 + 92$ で、 $20 \cdot 45 \equiv 92$ と一致する（ $m_{1} c_{2}^{'} \equiv m_{2} c_{2}$ が成り立つ）。また $1 \leq 58 \leq 100$ を満たす。

答え: $m_{2} = 58$ 。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる