暗号理論の問題

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

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

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

ある送信者が、本来は毎回選び直すべき $k$ を使い回して、2 つの平文 $m_{1}, m_{2}$ を同じ $k$ で暗号化した。得られた暗号文は
$m_{1} の暗号文 : (51, 11), m_{2} の暗号文 : (51, 7)$
である。攻撃者は何らかの方法で $m_{1} = 20$ であることを知った。秘密鍵 $x$ を求めずに、平文 $m_{2}$ （ $1 \leq m_{2} \leq 88$ の整数）を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

同じ $k$ を使うと、2 つの暗号文の $c_{2}$ には共通の因子 $h^{k}$ が掛かっていることに注目しよう。

ヒント 2

$s \equiv h^{k}$ とおくと $11 \equiv 20 s$ , $7 \equiv m_{2} s (mod 89)$ 。法 $89$ での逆元（拡張ユークリッドの互除法）を使えば $s$ が求まる。

ヒント 3

$2 0^{- 1} \equiv 49 (mod 89)$ なので $s \equiv 11 \cdot 49 \equiv 5 (mod 89)$ 。あとは $7 \equiv 5 m_{2}$ を解けばよい。

答えと解説

答えを見る

37

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

解説を読む

2 つの暗号文は同じ $k$ で作られているので、 $s \equiv h^{k} (mod 89)$ とおくと
$11 \equiv m_{1} s (mod 89), 7 \equiv m_{2} s (mod 89)$
が成り立つ（実際、 $c_{1}$ が等しければ $h^{k} \equiv (g^{k})^{x} \equiv c_{1}^{x}$ も等しい）。 $89$ は素数で $s \neq \equiv 0$ なので、 $s$ や $m_{1}$ は法 $89$ で逆元をもつ。

1. $s$ を求める。 $m_{1} = 20$ の逆元を求める。 $89 = 20 \cdot 4 + 9$ , $20 = 9 \cdot 2 + 2$ , $9 = 2 \cdot 4 + 1$ より
$1 = 9 - 4 \cdot 2 = 9 - 4 (20 - 2 \cdot 9) = 9 \cdot 9 - 4 \cdot 20 = 9 (89 - 4 \cdot 20) - 4 \cdot 20 = 9 \cdot 89 - 40 \cdot 20.$
よって $2 0^{- 1} \equiv - 40 \equiv 49 (mod 89)$ （確認: $20 \cdot 49 = 980 = 89 \cdot 11 + 1$ ）。したがって
$s \equiv 11 \cdot 49 = 539 = 89 \cdot 6 + 5 \equiv 5 (mod 89) .$

2. $m_{2}$ を求める。 $5 \cdot 18 = 90 \equiv 1$ より $5^{- 1} \equiv 18 (mod 89)$ 。よって
$m_{2} \equiv 7 \cdot 18 = 126 \equiv 126 - 89 = 37 (mod 89) .$

（別解: $m_{2} \equiv m_{1} \cdot 7 \cdot 1 1^{- 1}$ を使ってもよい。 $11 \cdot 81 = 891 = 89 \cdot 10 + 1$ より $1 1^{- 1} \equiv 81$ で、 $20 \cdot 7 \cdot 81 = 11340 = 89 \cdot 127 + 37$ となり同じ結果になる。）

検算: $37 \cdot 5 = 185 = 89 \cdot 2 + 7$ で、 $c_{2} = 7$ と一致する。

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

別解

同じ $k$ を使っているので、共通の値 $s \equiv h^{k} (mod 89)$ に対して $c_{2} \equiv m s$ が成り立つ。よって $11 \equiv 20 s$ , $7 \equiv m_{2} s (mod 89)$ であり、両辺の比をとると $m_{2} \equiv m_{1} \cdot \frac{7}{11} (mod 89)$ となる。

$11 \cdot 8 = 88 \equiv - 1$ より $1 1^{- 1} \equiv - 8 \equiv 81 (mod 89)$ 。

$m_{2} \equiv 20 \cdot 7 \cdot (- 8) = - 1120 (mod 89)$ 。 $89 \cdot 12 = 1068$ , $1120 - 1068 = 52$ なので $m_{2} \equiv - 52 \equiv 37$ 。

検算: $37 \cdot 11 = 407 = 4 \cdot 89 + 51 \equiv 51$ 、 $20 \cdot 7 = 140 = 89 + 51 \equiv 51$ で一致する。したがって $m_{2} = 37$ 。

この問題の確認

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

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

確認の方法について

間違いを報告する

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