暗号理論の問題

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

素数 $p = 53$ と、法 $53$ の原始根 $g = 2$ を公開パラメータとするエルガマル暗号を考える。受信者の公開鍵は $h = 17$ である（秘密鍵 $x$ は $h \equiv g^{x} (mod 53)$ を満たすが、公開されていない）。

平文 $m$ （ $1 \leq m \leq 52$ の整数）を暗号化するとき、送信者は乱数 $k$ （ $1 \leq k \leq 51$ の整数）を選び、
$c_{1} \equiv g^{k} (mod 53), c_{2} \equiv m h^{k} (mod 53) (0 \leq c_{1}, c_{2} \leq 52)$
として暗号文 $(c_{1}, c_{2})$ を送る。

ある送信者が、2 つの平文 $m_{1}, m_{2}$ を暗号化する際に、誤って同じ乱数 $k$ を使ってしまい、暗号文はそれぞれ
$(c_{1}, c_{2}) = (11, 32), (c_{1}^{'}, c_{2}^{'}) = (11, 38)$
となった。攻撃者は、1 つ目の平文が $m_{1} = 20$ であることを知っている。このとき、2 つ目の平文 $m_{2}$ を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

同じ乱数 $k$ を使っているので、2 つの暗号文の $c_{2}$ と $c_{2}^{'}$ には共通の値 $h^{k}$ が掛かっていることに注目する。

ヒント 2

$c_{2} \equiv m_{1} h^{k}$ , $c_{2}^{'} \equiv m_{2} h^{k} (mod 53)$ から $h^{k}$ を消去すると $m_{2} \equiv m_{1} c_{2}^{'} c_{2}^{- 1} (mod 53)$ となる。

ヒント 3

$h^{k} \equiv 32 \cdot 2 0^{- 1} (mod 53)$ で、 $2 0^{- 1} \equiv 8$ より $h^{k} \equiv 44 (mod 53)$ となる。あとは $38$ を $44$ で割る（ $44$ の逆元を掛ける）。

答えと解説

答えを見る

37

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

解説を読む

2 つの暗号文で同じ乱数 $k$ が使われているので、どちらも同じ値 $s \equiv h^{k} (mod 53)$ を平文に掛けている。
$c_{2} \equiv m_{1} s, c_{2}^{'} \equiv m_{2} s (mod 53)$

$s$ を求める。 $c_{2} \equiv m_{1} s$ より $s \equiv c_{2} m_{1}^{- 1} (mod 53)$ 。
$20 \cdot 8 = 160 = 3 \cdot 53 + 1$ なので $2 0^{- 1} \equiv 8 (mod 53)$ 。よって
$s \equiv 32 \cdot 8 = 256 = 4 \cdot 53 + 44 \equiv 44 (mod 53) .$

$m_{2}$ を求める。 $m_{2} \equiv c_{2}^{'} s^{- 1} (mod 53)$ である。 $44 \equiv - 9 (mod 53)$ で、 $9 \cdot 6 = 54 \equiv 1$ より $9^{- 1} \equiv 6$ 、したがって $4 4^{- 1} \equiv - 6 \equiv 47 (mod 53)$ 。よって
$m_{2} \equiv 38 \cdot 47 = 1786 = 33 \cdot 53 + 37 \equiv 37 (mod 53) .$

（別解： $m_{2} \equiv m_{1} c_{2}^{'} c_{2}^{- 1}$ を直接計算してもよい。 $32 \cdot 5 = 160 \equiv 1$ より $3 2^{- 1} \equiv 5$ なので、 $m_{2} \equiv 20 \cdot 38 \cdot 5 = 3800 = 71 \cdot 53 + 37 \equiv 37$ 。）

確かめ。 $2^{6} = 64 \equiv 11$ なので $k = 6$ であり、 $17 \equiv 2^{10}$ より $h^{k} \equiv 2^{60} \equiv 2^{8} = 256 \equiv 44$ （ $2^{52} \equiv 1$ を使った）。 $37 \cdot 44 = 1628 = 30 \cdot 53 + 38$ で、確かに $c_{2}^{'} = 38$ になる。

秘密鍵 $x$ を知らなくても、同じ乱数を使い回すと 1 つの平文が知られただけで他の平文が分かってしまう。

答え： $m_{2} = 37$

別解

同じ $k$ を使っているので、共有マスク $h^{k} mod 53$ が同じである。よって $c_{2} \equiv m_{1} h^{k}$ , $c_{2}^{'} \equiv m_{2} h^{k} (mod 53)$ より $m_{2} c_{2} \equiv m_{1} c_{2}^{'} (mod 53)$ 、すなわち $m_{2} \equiv m_{1} c_{2}^{'} c_{2}^{- 1} (mod 53)$ 。

$m_{1} = 20, c_{2} = 32, c_{2}^{'} = 38$ を代入すると $m_{2} \equiv 20 \cdot 38 \cdot 3 2^{- 1}$ 。
$3 2^{- 1}$ を求める: $32 \cdot 5 = 160 = 3 \cdot 53 + 1$ より $3 2^{- 1} \equiv 5$ 。
$20 \cdot 38 = 760 = 14 \cdot 53 + 18$ より $760 \equiv 18$ 。
$m_{2} \equiv 18 \cdot 5 = 90 \equiv 90 - 53 = 37 (mod 53)$ 。

検算: 共有マスクは $h^{k} \equiv c_{2} m_{1}^{- 1} = 32 \cdot 2 0^{- 1}$ 。 $2 0^{- 1} \equiv 8$ （ $160 \equiv 1$ ）なので $32 \cdot 8 = 256 \equiv 256 - 212 = 44$ 。 $m_{2} h^{k} = 37 \cdot 44 = 1628 = 30 \cdot 53 + 38$ より $\equiv 38 = c_{2}^{'}$ で一致する。また $1 \leq 37 \leq 52$ で平文の範囲内。

したがって $m_{2} = 37$ 。

この問題の確認

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

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

確認の方法について

間違いを報告する

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