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

暗号理論の問題

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

素数 $p = 17$ , $q = 23$ を用いて RSA 暗号の鍵を作る。 $n = pq = 391$ とし、公開鍵の暗号化指数を $e = 5$ とする。秘密鍵の復号指数 $d$ は、 $e d \equiv 1 (mod (p - 1) (q - 1))$ を満たす $1 \leq d < (p - 1) (q - 1)$ の整数とする。

平文 $m$ （ $0 \leq m < n$ を満たす整数）を $c \equiv m^{e} (mod n)$ , $0 \leq c < n$ により暗号化したところ、暗号文 $c = 223$ が得られた。平文 $m$ を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

まず $(p - 1) (q - 1)$ を計算し、 $e$ の逆元として復号指数 $d$ を求めましょう。そのあと $m \equiv c^{d} (mod n)$ を計算します。

ヒント 2

$d$ は拡張ユークリッドの互除法で求められます。 $c^{d} mod 391$ は、 $391 = 17 \cdot 23$ を利用して $mod 17$ と $mod 23$ に分け、フェルマーの小定理で指数を小さくしてから中国剰余定理でまとめると楽です。

ヒント 3

$d = 141$ です。 $141 \equiv 13 (mod 16)$ , $141 \equiv 9 (mod 22)$ なので、 $m \equiv 2^{13} \equiv 15 (mod 17)$ 、 $m \equiv 1 6^{9} \equiv 8 (mod 23)$ となります。あとはこの 2 つを同時に満たす $0 \leq m < 391$ を求めます。

答えと解説

答えを見る

100

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

解説を読む

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

$φ = (p - 1) (q - 1) = 16 \cdot 22 = 352$

$5 d \equiv 1 (mod 352)$ を拡張ユークリッドの互除法で解く。
$352 = 5 \cdot 70 + 2, 5 = 2 \cdot 2 + 1$
より
$1 = 5 - 2 \cdot 2 = 5 - 2 (352 - 5 \cdot 70) = 5 \cdot 141 - 2 \cdot 352$
よって $d = 141$ （確認: $5 \cdot 141 = 705 = 2 \cdot 352 + 1$ ）。

2. 復号 $m \equiv c^{d} (mod 391)$ を中国剰余定理で計算する。

$391 = 17 \cdot 23$ なので、 $mod 17$ と $mod 23$ に分けて計算する。フェルマーの小定理より、 $17$ で割り切れない $a$ について $a^{16} \equiv 1 (mod 17)$ 、 $23$ で割り切れない $a$ について $a^{22} \equiv 1 (mod 23)$ なので、指数はそれぞれ $16$ , $22$ で割った余りに減らせる。
$141 = 16 \cdot 8 + 13, 141 = 22 \cdot 6 + 9$

(i) $mod 17$ : $223 = 17 \cdot 13 + 2$ より $c \equiv 2$ 。 $2^{4} = 16 \equiv - 1$ , $2^{8} \equiv 1$ だから
$2^{13} = 2^{8} \cdot 2^{4} \cdot 2 \equiv 1 \cdot (- 1) \cdot 2 = - 2 \equiv 15 (mod 17)$

(ii) $mod 23$ : $223 = 23 \cdot 9 + 16$ より $c \equiv 16 = 2^{4}$ 。 $2^{11} = 2048 = 23 \cdot 89 + 1$ より $2^{11} \equiv 1$ だから
$1 6^{9} = 2^{36} = (2^{11})^{3} \cdot 2^{3} \equiv 8 (mod 23)$

(iii) $m \equiv 15 (mod 17)$ , $m \equiv 8 (mod 23)$ を解く。 $m = 15 + 17 k$ とおくと
$15 + 17 k \equiv 8 (mod 23) ⟺ 17 k \equiv - 7 \equiv 16 (mod 23)$
$17 \cdot 19 = 323 = 23 \cdot 14 + 1$ より $1 7^{- 1} \equiv 19 (mod 23)$ 。よって
$k \equiv 16 \cdot 19 = 304 = 23 \cdot 13 + 5 \equiv 5 (mod 23)$
$k = 5$ とすると $m = 15 + 85 = 100$ で、 $0 \leq m < 391$ を満たす。

3. 検算。 $10 0^{2} = 10000 \equiv 225$ , $10 0^{4} \equiv 22 5^{2} = 50625 \equiv 186$ , $10 0^{5} \equiv 186 \cdot 100 = 18600 \equiv 223 (mod 391)$ となり、確かに $c = 223$ になる。

したがって $m = 100$ 。

別解

$(p - 1) (q - 1) = 16 \cdot 22 = 352$ 。 $5 d \equiv 1 (mod 352)$ を解く。 $5 \cdot 141 = 705 = 2 \cdot 352 + 1$ より $d = 141$ 。

復号は $m \equiv c^{d} (mod 391)$ 。 $391 = 17 \cdot 23$ なので中国剰余定理で求める。

$223 \equiv 2 (mod 17)$ 、 $223 \equiv 16 (mod 23)$ 。

(i) $mod 17$ : $d \equiv 141 \equiv 13 (mod 16)$ より $m \equiv 2^{13}$ 。 $2^{4} \equiv - 1$ , $2^{8} \equiv 1$ なので $2^{13} = 2^{8} \cdot 2^{4} \cdot 2 \equiv - 2 \equiv 15$ 。

(ii) $mod 23$ : $d \equiv 141 \equiv 9 (mod 22)$ より $m \equiv 1 6^{9} = 2^{36}$ 。 $2^{11} \equiv 1 (mod 23)$ なので $2^{36} = 2^{33} \cdot 2^{3} \equiv 8$ 。

(iii) $m \equiv 15 (mod 17)$ , $m \equiv 8 (mod 23)$ 。 $m = 8 + 23 k$ とおくと $8 + 23 k \equiv 15 (mod 17)$ 、すなわち $6 k \equiv 7 (mod 17)$ 。 $6^{- 1} \equiv 3$ より $k \equiv 21 \equiv 4$ 。よって $m = 8 + 92 = 100$ 。

検算: $100 \equiv 15 (mod 17)$ 、 $1 5^{5} \equiv (- 2)^{5} = - 32 \equiv 2 (mod 17)$ （ $223 \equiv 2$ と一致）。 $100 \equiv 8 (mod 23)$ 、 $8^{2} = 64 \equiv 18$ , $8^{4} \equiv 1 8^{2} = 324 \equiv 2$ , $8^{5} \equiv 16 (mod 23)$ （ $223 \equiv 16$ と一致）。 $0 \leq 100 < 391$ を満たす。

暗号理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題