暗号理論の問題

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

$p, q$ を相異なる奇素数とし、 $n = pq$ 、 $φ = (p - 1) (q - 1)$ とおく。正の整数 $e, d$ は $e d \equiv 1 (mod φ)$ をみたすとする（RSA 暗号の公開鍵 $(n, e)$ と秘密鍵 $d$ ）。中国剰余定理を使った高速な復号（CRT-RSA）のために、次を定める。
- $d_{p}$ を $d$ を $p - 1$ で割った余り、 $d_{q}$ を $d$ を $q - 1$ で割った余りとする（ $0 \leq d_{p} \leq p - 2$ 、 $0 \leq d_{q} \leq q - 2$ ）。
- 整数 $u$ を、 $q u \equiv 1 (mod p)$ をみたす整数のうちの 1 つとする（ $p, q$ は相異なる素数なので、このような $u$ は存在する）。

$0 \leq c < n$ をみたす整数 $c$ （暗号文）に対して、
- $m_{p}$ を $c^{d_{p}}$ を $p$ で割った余り、 $m_{q}$ を $c^{d_{q}}$ を $q$ で割った余り（ $0 \leq m_{p} \leq p - 1$ 、 $0 \leq m_{q} \leq q - 1$ ）、
- $h$ を $u (m_{p} - m_{q})$ を $p$ で割った余り（ $0 \leq h \leq p - 1$ ）、
- $m = m_{q} + q h$

とおく。ここで $c$ は $n$ と互いに素であるとは限らない（ $c = 0$ や、 $c$ が $p$ または $q$ の倍数である場合も含む）。また、整数 $a$ に対して $a^{0} = 1$ と定める（ $a = 0$ のときも含む）。このとき、 $0 \leq m < n$ かつ $m \equiv c^{d} (mod n)$ であることを証明せよ。

ただし、フェルマーの小定理と、「整数 $x$ が相異なる素数 $p, q$ のそれぞれで割り切れるならば $pq$ で割り切れる」ことは用いてよい。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$m \equiv c^{d}$ を $p$ を法とする場合と $q$ を法とする場合に分けて示し、最後にまとめよう。範囲 $0 \leq m < n$ は別に評価する。

ヒント 2

鍵になるのは $c^{d} \equiv c^{d_{p}} (mod p)$ 。 $d = d_{p} + t (p - 1)$ と書いてフェルマーの小定理を使うが、 $p ∣ c$ の場合には $d_{p} \geq 1$ であることが必要になる。

ヒント 3

$g cd (d, φ) = 1$ から $g cd (d, p - 1) = 1$ を導くと $d_{p} \neq = 0$ がわかる。 $m$ を $p$ で割った余りを考えるときは $q u \equiv 1 (mod p)$ を使うと $m \equiv m_{p}$ となる。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$g cd (d, φ) = 1$ から $g cd (d, p - 1) = 1$ を導き、 $p - 1 \geq 2$ を使って $d_{p} \geq 1$ （ $d_{q}$ も同様）を示している（2 点）
$d = d_{p} + t (p - 1)$ と書き、 $p ∤ c$ ではフェルマーの小定理、 $p ∣ c$ では $d, d_{p} \geq 1$ を使って、どちらの場合も $c^{d} \equiv c^{d_{p}} (mod p)$ を示している（3 点）
$m_{q}, h$ の範囲から $0 \leq m \leq pq - 1$ を評価している（1 点）
$m \equiv m_{q} (mod q)$ と、 $q u \equiv 1$ を使った $m \equiv m_{p} (mod p)$ を示し、 $c^{d}$ との合同をそれぞれ導いている（3 点）
$p, q$ が相異なる素数であることから $n ∣ m - c^{d}$ を結論している（1 点）

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

模範解答を読む

方針. $m \equiv c^{d}$ を $p$ を法とする場合と $q$ を法とする場合に分けて示し、最後に $n = pq$ を法とする合同式にまとめる。そのために、まず $c^{d_{p}} \equiv c^{d} (mod p)$ （ $q$ についても同様）を示す。 $p ∣ c$ の場合には、 $d_{p} = 0$ だと $c^{d_{p}} = 1$ となって $c^{d} \equiv 0$ と合わなくなるので、 $d_{p} \geq 1$ であることを最初に確かめる。

ステップ 1: $d_{p} \geq 1$ かつ $d_{q} \geq 1$ . $e d \equiv 1 (mod φ)$ より、ある整数 $k$ で $e d - k φ = 1$ と書ける。 $d$ と $φ$ の正の公約数 $g$ は $e d - k φ = 1$ を割り切るので $g = 1$ 、すなわち $g cd (d, φ) = 1$ 。 $p - 1$ は $φ = (p - 1) (q - 1)$ の約数なので、 $d$ と $p - 1$ の公約数は $d$ と $φ$ の公約数でもあり、 $g cd (d, p - 1) = 1$ 。 $p$ は奇素数なので $p \geq 3$ 、すなわち $p - 1 \geq 2$ であり、もし $d_{p} = 0$ なら $p - 1 ∣ d$ となって $g cd (d, p - 1) = p - 1 \geq 2$ となり矛盾する。よって $d_{p} \geq 1$ 。 $q$ も奇素数で $q - 1$ も $φ$ の約数なので、 $p$ を $q$ に置き換えた同じ議論で $d_{q} \geq 1$ 。

ステップ 2: $c^{d} \equiv c^{d_{p}} (mod p)$ . $d_{p}$ は正の整数 $d$ を $p - 1$ で割った余りなので、0 以上の整数 $t$ （商）で $d = d_{p} + t (p - 1)$ と書ける。
- $p ∣ c$ のとき: $d \geq 1$ （仮定）、 $d_{p} \geq 1$ （ステップ 1）なので、 $c^{d}$ も $c^{d_{p}}$ も因数 $c$ を少なくとも 1 つ含み、 $p$ で割り切れる。よって $c^{d} \equiv 0 \equiv c^{d_{p}} (mod p)$ 。
- $p ∤ c$ のとき: $p$ は素数なのでフェルマーの小定理より $c^{p - 1} \equiv 1 (mod p)$ 。よって $c^{d} = c^{d_{p}} (c^{p - 1})^{t} \equiv c^{d_{p}} \cdot 1^{t} = c^{d_{p}} (mod p)$ 。

いずれの場合も $c^{d} \equiv c^{d_{p}} \equiv m_{p} (mod p)$ 。 $p$ を $q$ に、 $d_{p}$ を $d_{q}$ に置き換えた同じ議論（ステップ 1 で $d_{q} \geq 1$ も示してあり、 $q$ も素数なのでフェルマーの小定理が使える）により、 $c^{d} \equiv m_{q} (mod q)$ 。

ステップ 3: $0 \leq m < n$ . $0 \leq m_{q} \leq q - 1$ 、 $0 \leq h \leq p - 1$ なので
$0 \leq m = m_{q} + q h \leq (q - 1) + q (p - 1) = pq - 1 < n .$

ステップ 4: $m \equiv c^{d} (mod q)$ . $m = m_{q} + q h \equiv m_{q} (mod q)$ であり、ステップ 2 より $m_{q} \equiv c^{d} (mod q)$ 。

ステップ 5: $m \equiv c^{d} (mod p)$ . $h$ の定義より $h \equiv u (m_{p} - m_{q}) (mod p)$ 、また $q u \equiv 1 (mod p)$ なので
$m = m_{q} + q h \equiv m_{q} + q u (m_{p} - m_{q}) \equiv m_{q} + 1 \cdot (m_{p} - m_{q}) = m_{p} (mod p) .$
ステップ 2 より $m_{p} \equiv c^{d} (mod p)$ なので $m \equiv c^{d} (mod p)$ 。

ステップ 6: まとめ. ステップ 4, 5 より整数 $m - c^{d}$ は $p$ でも $q$ でも割り切れる。 $p, q$ は相異なる素数なので、用いてよい事実より $pq = n$ で割り切れ、 $m \equiv c^{d} (mod n)$ 。

以上より、CRT-RSA で計算した $m$ は $0 \leq m < n$ かつ $m \equiv c^{d} (mod n)$ をみたす。すなわち $m$ は通常の RSA 復号で得られる $c^{d}$ を $n$ で割った余りと一致する。 $■$

この問題の確認

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

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

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