暗号理論の問題

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

RSA 暗号の受信者は、相異なる素数 $p, q$ を選んで $n = pq$ とし、公開鍵 $(n, e) = (437, 5)$ を公開した。秘密鍵の復号指数 $d$ は
$e d \equiv 1 (mod φ (n)), 1 \leq d < φ (n)$
を満たす整数である。ここで $φ (n) = (p - 1) (q - 1)$ である。送信者は平文 $m$ （ $0 \leq m \leq 436$ を満たす整数）を $c \equiv m^{e} (mod n)$ （ $0 \leq c \leq 436$ ）によって暗号化して送る。

いま攻撃者は、 $p, q$ そのものは知らないが、 $φ (n) = 396$ であることを知った。さらに暗号文 $c = 98$ を傍受した。この暗号文に対応する平文 $m$ を求めよ。

この問題で使うもの

RSA 暗号の鍵生成・暗号化・復号（説明と入口の問題）
法 $m$ での逆元（拡張ユークリッドの互除法）（説明と入口の問題）
繰り返し二乗法によるべき剰余（説明と入口の問題）
合同式（説明と入口の問題）
1 次不定方程式の整数解（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$n$ と $φ (n)$ がわかると $p + q$ と $pq$ がわかるので、 $p, q$ を 2 次方程式の解として求められます。そのあと $d$ を求めて復号します。

ヒント 2

$p + q = n - φ (n) + 1$ です。 $d$ は $5 d \equiv 1 (mod 396)$ の解で、復号 $c^{d} mod n$ は法 $p$ , 法 $q$ に分けて計算し中国剰余定理でまとめると楽です。

ヒント 3

$p + q = 42$ , $pq = 437$ から ${p, q} = {19, 23}$ 、 $d = 317$ です。 $317 \equiv 11 (mod 18)$ , $317 \equiv 9 (mod 22)$ なので、 $9 8^{11} mod 19$ と $9 8^{9} mod 23$ を計算しましょう。

答えと解説

答えを見る

200

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

解説を読む

1. $p, q$ を求める。
$φ (n) = (p - 1) (q - 1) = pq - (p + q) + 1 = n - (p + q) + 1$ なので
$p + q = n - φ (n) + 1 = 437 - 396 + 1 = 42, pq = 437.$
よって $p, q$ は 2 次方程式 $t^{2} - 42 t + 437 = 0$ の 2 解である。判別式は $4 2^{2} - 4 \cdot 437 = 1764 - 1748 = 16$ なので
$t = \frac{42 \pm 4}{2} = 23, 19.$
したがって ${p, q} = {19, 23}$ （実際 $19 \cdot 23 = 437$ , $18 \cdot 22 = 396$ ）。

2. 復号指数 $d$ を求める。
$5 d \equiv 1 (mod 396)$ を解く。 $396 = 5 \cdot 79 + 1$ より $5 \cdot (- 79) \equiv 1 (mod 396)$ 。よって $d \equiv - 79 \equiv 317 (mod 396)$ 、すなわち $d = 317$ （確認: $5 \cdot 317 = 1585 = 4 \cdot 396 + 1$ ）。

3. 中国剰余定理を使って $m \equiv c^{d} (mod 437)$ を計算する。
RSA の正当性（オイラーの定理・フェルマーの小定理）により $m \equiv c^{d} (mod n)$ である。 $19, 23$ ごとに計算する。フェルマーの小定理より指数はそれぞれ $18, 22$ を法として減らせる:
$317 = 18 \cdot 17 + 11, 317 = 22 \cdot 14 + 9.$

法 $19$ : $98 \equiv 3$ 。 $3^{2} = 9, 3^{4} = 81 \equiv 5, 3^{8} \equiv 25 \equiv 6$ 。よって $3^{11} = 3^{8} \cdot 3^{2} \cdot 3 \equiv 6 \cdot 9 \cdot 3 = 162 \equiv 10 (mod 19)$ 。
法 $23$ : $98 \equiv 6$ 。 $6^{2} = 36 \equiv 13, 6^{4} \equiv 169 \equiv 8, 6^{8} \equiv 64 \equiv 18$ 。よって $6^{9} = 6^{8} \cdot 6 \equiv 108 \equiv 16 (mod 23)$ 。

したがって $m \equiv 10 (mod 19)$ , $m \equiv 16 (mod 23)$ 。 $m = 10 + 19 k$ とおくと $10 + 19 k \equiv 16 (mod 23)$ より $19 k \equiv 6$ 、すなわち $- 4 k \equiv 6$ 、 $4 k \equiv 17 (mod 23)$ 。 $4 \cdot 6 = 24 \equiv 1$ なので $k \equiv 6 \cdot 17 = 102 \equiv 10 (mod 23)$ 。よって $m = 10 + 190 = 200$ 。

4. 検算。 $200 \equiv 10 (mod 19)$ で $1 0^{5} \equiv 3$ 、 $200 \equiv 16 (mod 23)$ で $1 6^{5} \equiv 6$ 。 $c \equiv 3 (mod 19)$ , $c \equiv 6 (mod 23)$ を満たす $0 \leq c \leq 436$ は $c = 98$ で、与えられた暗号文と一致する。

答え: $m = 200$

別解

$n = 437 = 19 \cdot 23$ であり、 $φ (n) = 18 \cdot 22 = 396$ で問題の条件と一致する。

$5 d \equiv 1 (mod 396)$ を解く。 $5 \cdot 317 = 1585 = 4 \cdot 396 + 1$ より $d = 317$ 。

$m \equiv 9 8^{317} (mod 437)$ を中国剰余定理で計算する。

(1) 法 19 のとき： $98 \equiv 3$ 。指数は $317 \equiv 11 (mod 18)$ 。 $3^{11} \equiv 10 (mod 19)$ （ $3^{5} \equiv 15, 3^{10} \equiv 16, 3^{11} \equiv 48 \equiv 10$ ）。よって $m \equiv 10 (mod 19)$ 。

(2) 法 23 のとき： $98 \equiv 6$ 。指数は $317 \equiv 9 (mod 22)$ 。 $6^{2} \equiv 13, 6^{3} \equiv 9, 6^{6} \equiv 12, 6^{9} \equiv 12 \cdot 9 = 108 \equiv 16$ 。よって $m \equiv 16 (mod 23)$ 。

(3) 連立合同式を解く： $m = 10 + 19 k$ とおくと $19 k \equiv 6 (mod 23)$ 。 $19 \equiv - 4$ より $4 k \equiv 17 (mod 23)$ 。 $4^{- 1} \equiv 6$ なので $k \equiv 102 \equiv 10$ 。よって $m = 10 + 190 = 200$ 。

検算： $20 0^{5} mod 19$ ： $200 \equiv 10$ 、 $1 0^{5} \equiv 3 \equiv 98 (mod 19)$ 。 $20 0^{5} mod 23$ ： $200 \equiv 16$ 、 $1 6^{5} \equiv 6 \equiv 98 (mod 23)$ 。よって $20 0^{5} \equiv 98 (mod 437)$ が成り立つ。

答え： $m = 200$

この問題の確認

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

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

確認の方法について

間違いを報告する

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