この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

暗号理論の問題

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

受信者は素数 $p = 11$ , $q = 19$ を選び、 $n = pq = 209$ と暗号化指数 $e = 7$ を公開鍵として公開した。送信者は平文 $m$ （ $0 \leq m \leq 208$ を満たす整数）を
$c \equiv m^{e} (mod n), 0 \leq c \leq 208$
によって暗号化し、暗号文 $c = 68$ を受信者に送った。

受信者は秘密鍵の復号指数 $d$ を $e d \equiv 1 (mod (p - 1) (q - 1))$ , $1 \leq d \leq (p - 1) (q - 1) - 1$ を満たす整数として求め、 $m \equiv c^{d} (mod n)$ により復号する。平文 $m$ を求めよ。

この問題で使うもの

RSA 暗号の鍵生成・暗号化・復号（説明と入口の問題）
法 $m$ での逆元（拡張ユークリッドの互除法）（説明と入口の問題）
合同式（説明と入口の問題）
1 次不定方程式の整数解（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

まず $(p - 1) (q - 1)$ を計算し、拡張ユークリッドの互除法で $7 d \equiv 1 (mod 180)$ を満たす $d$ を求めましょう。

ヒント 2

$6 8^{d} mod 209$ を直接計算するのは大変なので、 $209 = 11 \cdot 19$ を使い、法 $11$ と法 $19$ で別々にフェルマーの小定理で指数を小さくしてから、中国剰余定理で組み合わせます。

ヒント 3

$d = 103$ です。法 $11$ では $68 \equiv 2$ で $6 8^{103} \equiv 2^{3}$ 、法 $19$ では $68 \equiv 11$ で $6 8^{103} \equiv 1 1^{13}$ となります。 $1 1^{3} (mod 19)$ を計算してみましょう。

答えと解説

答えを見る

30

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

解説を読む

1. 復号指数 $d$ を求める。

$(p - 1) (q - 1) = 10 \cdot 18 = 180$ なので、 $7 d \equiv 1 (mod 180)$ を解く。ユークリッドの互除法より
$180 = 7 \cdot 25 + 5, 7 = 5 \cdot 1 + 2, 5 = 2 \cdot 2 + 1.$
これを逆にたどると
$1 = 5 - 2 \cdot 2 = 5 - 2 (7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3 (180 - 25 \cdot 7) - 2 \cdot 7 = 3 \cdot 180 - 77 \cdot 7.$
よって $7 \cdot (- 77) \equiv 1 (mod 180)$ であり、 $d \equiv - 77 \equiv 103 (mod 180)$ 。実際 $7 \cdot 103 = 721 = 4 \cdot 180 + 1$ である。したがって $d = 103$ 。

2. 中国剰余定理を使って $m \equiv 6 8^{103} (mod 209)$ を計算する。

$209 = 11 \cdot 19$ なので、法 $11$ と法 $19$ で別々に計算する。 $68$ は $11$ でも $19$ でも割り切れないので、フェルマーの小定理が使える。

- 法 $11$ : $68 \equiv 2$ 。フェルマーの小定理より $2^{10} \equiv 1 (mod 11)$ 。 $103 = 10 \cdot 10 + 3$ なので
$6 8^{103} \equiv 2^{3} = 8 (mod 11) .$
- 法 $19$ : $68 \equiv 68 - 57 = 11$ 。フェルマーの小定理より $1 1^{18} \equiv 1 (mod 19)$ 。 $103 = 18 \cdot 5 + 13$ なので $6 8^{103} \equiv 1 1^{13} (mod 19)$ 。ここで $1 1^{2} = 121 \equiv 121 - 114 = 7$ 、 $1 1^{3} \equiv 7 \cdot 11 = 77 \equiv 77 - 76 = 1 (mod 19)$ だから
$1 1^{13} = (1 1^{3})^{4} \cdot 11 \equiv 11 (mod 19) .$

3. 連立合同式を解く。

$m \equiv 8 (mod 11)$ , $m \equiv 11 (mod 19)$ を解く。 $m = 11 + 19 k$ とおくと、 $19 \equiv 8 (mod 11)$ より
$11 + 19 k \equiv 0 + 8 k \equiv 8 (mod 11) ⟹ k \equiv 1 (mod 11) .$
よって $m = 11 + 19 = 30$ （ $0 \leq m \leq 208$ の範囲でただ 1 つ）。

確認: $3 0^{7} mod 209$ を計算する。法 $11$ で $30 \equiv 8$ 、 $8^{2} \equiv 9$ 、 $8^{4} \equiv 81 \equiv 4$ 、 $8^{7} = 8^{4} \cdot 8^{2} \cdot 8 \equiv 4 \cdot 9 \cdot 8 = 288 \equiv 2$ 。法 $19$ で $30 \equiv 11$ 、 $1 1^{7} = (1 1^{3})^{2} \cdot 11 \equiv 11$ 。 $68 \equiv 2 (mod 11)$ 、 $68 \equiv 11 (mod 19)$ と一致するので、確かに $3 0^{7} \equiv 68 (mod 209)$ である。

したがって平文は $m = 30$ 。

別解

$(p - 1) (q - 1) = 10 \cdot 18 = 180$ 。 $e d \equiv 1 (mod 180)$ , $7 d \equiv 1$ を解くと $7 \cdot 103 = 721 = 4 \cdot 180 + 1$ より $d = 103$ （ $1 \leq d \leq 179$ の範囲でただ 1 つ）。\n\n $m \equiv c^{d} (mod 209)$ を中国剰余定理で計算する。\n- mod 11: $c = 68 \equiv 2$ 。 $d \equiv 103 \equiv 3 (mod 10)$ （フェルマーの小定理）。 $m \equiv 2^{3} = 8 (mod 11)$ 。\n- mod 19: $c = 68 \equiv 11$ 。 $d \equiv 103 \equiv 13 (mod 18)$ 。 $1 1^{2} = 121 \equiv 7$ , $1 1^{3} \equiv 77 \equiv 1$ なので $1 1^{13} = 1 1^{12} \cdot 11 \equiv 11 (mod 19)$ 。 $m \equiv 11 (mod 19)$ 。\n\n $m = 11 + 19 k$ とおくと $11 + 19 k \equiv 8 (mod 11)$ 、すなわち $8 k \equiv - 3 \equiv 8$ より $k \equiv 1 (mod 11)$ 。 $k = 1$ で $m = 30$ （ $0 \leq m \leq 208$ の範囲でただ 1 つ）。\n\n検算: $3 0^{2} = 900 \equiv 64$ , $3 0^{4} \equiv 6 4^{2} = 4096 \equiv 125$ , $3 0^{7} = 3 0^{4} \cdot 3 0^{2} \cdot 30 \equiv 125 \cdot 64 \cdot 30$ 。 $125 \cdot 64 = 8000 \equiv 58$ , $58 \cdot 30 = 1740 \equiv 68 (mod 209)$ となり $c = 68$ に一致。

暗号理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題