暗号理論の問題

難易度 2教科書の演習問題レベル大学数学暗号理論

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

送信者は平文 $m$ （ $1 \leq m \leq 58$ を満たす整数）を暗号化するとき、一時鍵 $k$ を選び、
$c_{1} \equiv g^{k} (mod 59), c_{2} \equiv m h^{k} (mod 59) (0 \leq c_{1}, c_{2} \leq 58)$
として暗号文 $(c_{1}, c_{2})$ を送る。

ある送信者が、本来は毎回取り替えるべき一時鍵 $k$ を、2 つの平文 $m_{1}$ , $m_{2}$ の暗号化に同じ値のまま使ってしまった。その結果、送られた暗号文は次の 2 つである。
$(c_{1}, c_{2}) = (28, 56), (c_{1}^{'}, c_{2}^{'}) = (28, 43)$
攻撃者は、1 つ目の暗号文の平文が $m_{1} = 23$ であることを知っている。このとき、2 つ目の暗号文の平文 $m_{2}$ （ $1 \leq m_{2} \leq 58$ ）を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

2 つの暗号文の $c_{1}$ が等しいことから、同じ一時鍵 $k$ が使われ、マスクの値 $h^{k}$ も共通であることに注目する。

ヒント 2

$s \equiv h^{k}$ とおくと $c_{2} \equiv m_{1} s$ 、 $c_{2}^{'} \equiv m_{2} s (mod 59)$ である。既知の $m_{1}$ から $s$ を求め、その逆元を $c_{2}^{'}$ に掛ければよい。

ヒント 3

$2 3^{- 1} \equiv 18 (mod 59)$ より $s \equiv 56 \cdot 18 \equiv 5 (mod 59)$ となる。あとは $5$ の法 $59$ での逆元を求めて $43$ に掛ける。

答えと解説

答えを見る

44

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

解説を読む

同じ一時鍵 $k$ を使っているので、共有値 $s \equiv h^{k} (mod 59)$ は 2 つの暗号文で共通である。
$c_{2} \equiv m_{1} s, c_{2}^{'} \equiv m_{2} s (mod 59)$
が成り立つ。59 は素数なので、 $1$ 以上 $58$ 以下の整数は法 $59$ で逆元をもつ。

手順 1： $s$ を求める。 $s \equiv c_{2} m_{1}^{- 1} \equiv 56 \cdot 2 3^{- 1} (mod 59)$ である。 $2 3^{- 1}$ をユークリッドの互除法で求める。
$59 = 2 \cdot 23 + 13, 23 = 1 \cdot 13 + 10, 13 = 1 \cdot 10 + 3, 10 = 3 \cdot 3 + 1$
これを逆にたどると
$1 = 10 - 3 \cdot 3 = 4 \cdot 10 - 3 \cdot 13 = 4 \cdot 23 - 7 \cdot 13 = 18 \cdot 23 - 7 \cdot 59$
となる。よって $2 3^{- 1} \equiv 18 (mod 59)$ である（確認： $23 \cdot 18 = 414 = 7 \cdot 59 + 1$ ）。
したがって
$s \equiv 56 \cdot 18 = 1008 = 17 \cdot 59 + 5 \equiv 5 (mod 59) .$

手順 2： $m_{2}$ を求める。 $5 \cdot 12 = 60 \equiv 1$ より $s^{- 1} \equiv 12 (mod 59)$ である。よって
$m_{2} \equiv c_{2}^{'} s^{- 1} \equiv 43 \cdot 12 = 516 = 8 \cdot 59 + 44 \equiv 44 (mod 59) .$

検算： 秘密鍵を知らなくてもこの攻撃は成り立つが、実際には $h = 40 \equiv 2^{9}$ 、 $k = 20$ である。このとき $c_{1} \equiv 2^{20} \equiv 28$ 、 $s \equiv 2^{180} \equiv 2^{6} \equiv 5$ となり、 $44 \cdot 5 = 220 \equiv 43$ が成り立つ。値は一致している。

以上より $m_{2} = 44$ である。

別解

同じ一時鍵 $k$ を使っているので、 $h^{k}$ は 2 つの暗号文で共通である。したがって $c_{2} \equiv m_{1} h^{k}$ 、 $c_{2}^{'} \equiv m_{2} h^{k}$ より $m_{2} \equiv m_{1} c_{2}^{'} c_{2}^{- 1} (mod 59)$ となる。

$c_{2} = 56 \equiv - 3$ で、 $3 \cdot 20 = 60 \equiv 1$ より $3^{- 1} \equiv 20$ 。よって $5 6^{- 1} \equiv - 20 \equiv 39$ 。

$m_{1} c_{2}^{'} = 23 \cdot 43 = 989 \equiv 989 - 944 = 45$ 。

$m_{2} \equiv 45 \cdot 39 = 1755 \equiv 1755 - 1711 = 44 (mod 59)$ 。

検算1: $m_{2} c_{2} = 44 \cdot 56 = 2464 \equiv 2464 - 2419 = 45$ 、 $m_{1} c_{2}^{'} \equiv 45$ で一致する。

検算2: $2^{20} \equiv 28$ なので $k = 20$ 。 $40 \equiv 2^{9}$ なので $x = 9$ 。 $h^{k} = 2^{180}$ で、 $2^{58} \equiv 1$ より $2^{180} = 2^{6} = 64 \equiv 5$ 。 $m_{1} h^{k} = 23 \cdot 5 = 115 \equiv 56$ で $c_{2}$ と一致する。 $m_{2} h^{k} = 44 \cdot 5 = 220 \equiv 220 - 177 = 43$ で $c_{2}^{'}$ と一致する。

よって $m_{2} = 44$ 。

この問題の確認

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

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

確認の方法について

間違いを報告する

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