暗号理論の問題

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

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

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

ある送信者が、2 つの平文 $m_{1}$ , $m_{2}$ を暗号化する際に、誤って同じ乱数 $k$ を使ってしまった。その結果、暗号文はそれぞれ
$(c_{1}, c_{2}) = (6, 11), (c_{1}^{'}, c_{2}^{'}) = (6, 42)$
となった。攻撃者は何らかの方法で $m_{1} = 25$ であることを知った。このとき、秘密鍵 $x$ や乱数 $k$ を求めずに得られる $m_{2}$ （ $1 \leq m_{2} \leq 60$ の整数）を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

2 つの暗号文で $c_{1}$ が等しいことから、同じ乱数 $k$ が使われ、 $c_{2}$ と $c_{2}^{'}$ には共通の因子 $h^{k}$ が掛かっていることに注目しよう。

ヒント 2

$s \equiv h^{k}$ とおくと $c_{2} \equiv m_{1} s$ , $c_{2}^{'} \equiv m_{2} s (mod 61)$ 。よって $s \equiv c_{2} m_{1}^{- 1}$ 、 $m_{2} \equiv c_{2}^{'} s^{- 1} (mod 61)$ で求められる。逆元はユークリッドの互除法で求める。

ヒント 3

$2 5^{- 1} \equiv 22 (mod 61)$ なので $s \equiv 11 \cdot 22 \equiv 59 (mod 61)$ となる。あとは $59$ の法 $61$ での逆元を求めて $42$ に掛ければよい。

答えと解説

答えを見る

40

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

解説を読む

同じ乱数 $k$ を使っているので、2 つの暗号文に共通の値
$s \equiv h^{k} (mod 61)$
が現れ、
$c_{2} \equiv m_{1} s, c_{2}^{'} \equiv m_{2} s (mod 61)$
が成り立つ（実際 $c_{1} = c_{1}^{'} = 6$ であることからも同じ $k$ と分かる）。 $61$ は素数なので、 $1 \leq m_{1} \leq 60$ は法 $61$ で逆元をもつ。

$s$ を求める. $s \equiv c_{2} m_{1}^{- 1} (mod 61)$ である。 $25$ の法 $61$ での逆元を求める。ユークリッドの互除法より
$61 = 2 \cdot 25 + 11, 25 = 2 \cdot 11 + 3, 11 = 3 \cdot 3 + 2, 3 = 1 \cdot 2 + 1$
これを逆にたどると
$1 = 3 - 2 = 3 - (11 - 3 \cdot 3) = 4 \cdot 3 - 11 = 4 (25 - 2 \cdot 11) - 11 = 4 \cdot 25 - 9 \cdot 11$
$= 4 \cdot 25 - 9 (61 - 2 \cdot 25) = 22 \cdot 25 - 9 \cdot 61$
よって $2 5^{- 1} \equiv 22 (mod 61)$ （確認: $25 \cdot 22 = 550 = 9 \cdot 61 + 1$ ）。したがって
$s \equiv 11 \cdot 22 = 242 = 3 \cdot 61 + 59 \equiv 59 \equiv - 2 (mod 61)$

$m_{2}$ を求める. $m_{2} \equiv c_{2}^{'} s^{- 1} (mod 61)$ である。 $s \equiv - 2$ の逆元は、 $2 \cdot 31 = 62 \equiv 1$ より $2^{- 1} \equiv 31$ なので $(- 2)^{- 1} \equiv - 31 \equiv 30 (mod 61)$ （確認: $59 \cdot 30 = 1770 = 29 \cdot 61 + 1$ ）。よって
$m_{2} \equiv 42 \cdot 30 = 1260 = 20 \cdot 61 + 40 \equiv 40 (mod 61)$

検算. 実際、 $x = 13$ （ $2^{13} = 8192 = 134 \cdot 61 + 18$ ）、 $k = 7$ （ $2^{7} = 128 = 2 \cdot 61 + 6$ ）であり、 $h^{k} = 1 8^{7} \equiv 59 (mod 61)$ 、 $25 \cdot 59 \equiv 11$ 、 $40 \cdot 59 \equiv 42 (mod 61)$ となって与えられた暗号文と一致する。

まとめると、 $m_{2} \equiv m_{1} c_{2}^{'} c_{2}^{- 1} (mod 61)$ により、秘密鍵を知らなくても $m_{2} = 40$ が得られる。

別解

同じ $k$ を使うと共有鍵 $s = h^{k} mod 61$ が同じになる。 $c_{2} \equiv m_{1} s$ 、 $c_{2}^{'} \equiv m_{2} s$ より
$\frac{c _{2}^{'}}{c _{2}} \equiv \frac{m _{2}}{m _{1}} (mod 61) ⟹ m_{2} \equiv m_{1} c_{2}^{'} c_{2}^{- 1} (mod 61) .$
$11 \cdot 50 = 550 = 61 \cdot 9 + 1$ より $1 1^{- 1} \equiv 50$ 。したがって
$m_{2} \equiv 25 \cdot 42 \cdot 50$ 。 $25 \cdot 42 = 1050 = 61 \cdot 17 + 13$ より $13$ 、 $13 \cdot 50 = 650 = 61 \cdot 10 + 40$ より $m_{2} \equiv 40$ 。
検算: $2 5^{- 1} \equiv 22$ （ $25 \cdot 22 = 550 \equiv 1$ ）なので $s \equiv 11 \cdot 22 = 242 \equiv 59 \equiv - 2$ 。 $s^{- 1} \equiv - 31 \equiv 30$ （ $(- 2) (- 31) = 62 \equiv 1$ ）。 $m_{2} \equiv 42 \cdot 30 = 1260 = 61 \cdot 20 + 40 \equiv 40$ 。一致。
よって $m_{2} = 40$ 。

この問題の確認

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

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

確認の方法について

間違いを報告する

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