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

暗号理論の問題

難易度 1教科書の例題レベル大学数学暗号理論

受信者は素数 $p = 7$ , $q = 13$ を選び、 $n = pq = 91$ とした。暗号化指数を $e = 5$ とし、公開鍵 $(n, e) = (91, 5)$ を公開した。復号指数 $d$ は
$e d \equiv 1 (mod (p - 1) (q - 1)), 1 \leq d \leq (p - 1) (q - 1) - 1$
を満たす整数である。送信者は平文 $m$ （ $0 \leq m \leq 90$ を満たす整数）を $c \equiv m^{e} (mod n)$ （ $0 \leq c \leq 90$ ）で暗号化し、暗号文 $c = 82$ を送った。受信者が $m \equiv c^{d} (mod n)$ で復号して得る平文 $m$ を求めよ。

この問題で使うもの

RSA 暗号の鍵生成・暗号化・復号（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

RSA 暗号の復号の手順を使います。まず $(p - 1) (q - 1)$ を計算し、拡張ユークリッドの互除法で $5 d \equiv 1 (mod (p - 1) (q - 1))$ を満たす $d$ を求め、そのあと $c^{d} mod 91$ を計算します。

ヒント 2

$(p - 1) (q - 1) = 72$ です。 $72 = 5 \cdot 14 + 2$ , $5 = 2 \cdot 2 + 1$ を逆にたどると $d$ が求まります。べき剰余では $82 \equiv - 9 (mod 91)$ と $9^{3} = 729$ に注目すると計算が短くなります。

ヒント 3

$d = 29$ です。 $9^{3} \equiv 1 (mod 91)$ と $29 = 3 \cdot 9 + 2$ を使うと、 $8 2^{29} \equiv - 9^{2} (mod 91)$ となります。あとは $0 \leq m \leq 90$ の範囲の値に直しましょう。

答えと解説

答えを見る

10

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

解説を読む

手順 1： $(p - 1) (q - 1)$ を求める。
$(p - 1) (q - 1) = 6 \cdot 12 = 72.$

手順 2：復号指数 $d$ を求める。 $5 d \equiv 1 (mod 72)$ を満たす $d$ を拡張ユークリッドの互除法で求める。
$72 = 5 \cdot 14 + 2, 5 = 2 \cdot 2 + 1.$
これを逆にたどると
$1 = 5 - 2 \cdot 2 = 5 - 2 (72 - 5 \cdot 14) = 5 \cdot 29 - 2 \cdot 72.$
よって $5 \cdot 29 \equiv 1 (mod 72)$ であり、 $1 \leq d \leq 71$ より $d = 29$ 。（確認： $5 \cdot 29 = 145 = 2 \cdot 72 + 1$ 。）

手順 3： $m \equiv 8 2^{29} (mod 91)$ を計算する。
$82 = 91 - 9$ より $82 \equiv - 9 (mod 91)$ 。また
$9^{2} = 81, 9^{3} = 729 = 8 \cdot 91 + 1 \equiv 1 (mod 91) .$
$29 = 3 \cdot 9 + 2$ なので
$8 2^{29} \equiv (- 9)^{29} = - 9^{29} = - (9^{3})^{9} \cdot 9^{2} \equiv - 1^{9} \cdot 81 = - 81 (mod 91) .$
$- 81 + 91 = 10$ より $m \equiv 10 (mod 91)$ 。 $0 \leq m \leq 90$ なので $m = 10$ 。

確認（暗号化）： $1 0^{2} = 100 \equiv 9$ , $1 0^{4} \equiv 81$ , $1 0^{5} \equiv 81 \cdot 10 = 810 = 8 \cdot 91 + 82 \equiv 82 (mod 91)$ となり、暗号文 $c = 82$ と一致する。

答え： $m = 10$

別解

$(p - 1) (q - 1) = 6 \cdot 12 = 72$ である。 $5 d \equiv 1 (mod 72)$ を満たす $d$ は $5 \cdot 29 = 145 = 2 \cdot 72 + 1$ より $d = 29$ である（ $1 \leq d \leq 71$ の範囲で一意）。

$m \equiv 8 2^{29} (mod 91)$ を中国剰余定理で求める。

$mod 7$ ： $82 \equiv 5$ 。 $29 \equiv 5 (mod 6)$ なので $5^{29} \equiv 5^{5}$ 。 $5^{2} \equiv 4$ , $5^{4} \equiv 2$ , $5^{5} \equiv 10 \equiv 3$ 。よって $m \equiv 3 (mod 7)$ 。
$mod 13$ ： $82 \equiv 4$ 。 $29 \equiv 5 (mod 12)$ なので $4^{29} \equiv 4^{5} = 1024 \equiv 10$ （ $13 \cdot 78 = 1014$ ）。よって $m \equiv 10 (mod 13)$ 。

$m \equiv 10 (mod 13)$ の候補 $10, 23, 36, \dots$ のうち、 $10 \equiv 3 (mod 7)$ なので $m = 10$ が条件を満たす。

検算： $1 0^{5} = 100000 = 91 \cdot 1098 + 82$ （ $91 \cdot 1098 = 99918$ ）なので $1 0^{5} \equiv 82 (mod 91)$ となり、 $c = 82$ と一致する。

よって平文は $m = 10$ である。

暗号理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題