COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

整数の剰余

整数の剰余

問題≪フェルマーの小定理と RSA 暗号の原理≫

 $a,$ $b,$ $a',$ $b',$ $c,$ $n$ を整数とし, $p,$ $q$ を相異なる素数とする. $a-a'$ が $n$ で割り切れるとき, $a \equiv a'\ (\text{mod}\ n)$ と表す. 次のことを示せ.
(1)
$a \equiv a',$ $b \equiv b'\ (\text{mod}\ n)$ ならば, $ab \equiv a'b'\ (\text{mod}\ n)$ が成り立つ.
(2)
$c$ が $p$ の倍数でないとする. このとき, $ac \equiv a'c\ (\text{mod}\ p)$ ならば, $a \equiv a'\ (\text{mod}\ p)$ が成り立つ.
(3)
$a$ が $p$ の倍数でないとき, $p-1$ 以下の正の整数全体から成る集合を $G$ とおき, $k \in G$ なる各整数 $k$ に対して $ak$ を $p$ で割った余りを $r_k$ とおくと, $\{ r_k|k \in G\} = G$ が成り立つ.
(4)
$a$ が $p$ の倍数でないとき, $a^{p-1} \equiv 1\ (\text{mod}\ p)$ が成り立つ.
(5)
$n = pq$ とし, 整数 $e,$ $d$ が \[ ed \equiv 1\ (\text{mod}{(p-1)(q-1)})\] を満たすとする. このとき, $n$ と互いに素な整数 $a,$ $b$ に対して, $a^e \equiv b\ (\text{mod}\ n)$ ならば, $b^d \equiv a\ (\text{mod}\ n)$ が成り立つ.

解答例

(1)
$a \equiv a',$ $b \equiv b'\ (\text{mod}\ n)$ ならば,
$a = a'+n\alpha,$ $b = b'+n\beta$ ($\alpha,$ $\beta$: 整数)
と書けて, \[ ab = a'b'+n(\alpha b'+a'\beta +n\alpha\beta ) \equiv a'b'\ (\text{mod}\ n)\] となる.
(2)
$c$ が $p$ と互いに素であることに注意すると, \begin{align*} ac \equiv a'c\ (\text{mod}\ p) &\iff ac-a'c\text{ は }p\text{ の倍数} \\ &\iff (a-a')c\text{ は }p\text{ の倍数} \\ &\iff a-a'\text{ は }p\text{ の倍数} \\ &\iff a \equiv a'\ (\text{mod}\ p) \end{align*} となる.
(3)
$k \in G,$ $l \in G,$ $k \neq l$ なる整数 $k,$ $l$ に対して, $k \not\equiv l\ (\text{mod}\ p)$ であるから, $a$ が $p$ と互いに素であるという仮定と (2) の対偶から, $ak \not\equiv al\ (\text{mod}\ p)$ が成り立ち, よって $r_k \neq r_l$ が成り立つ.
これは $\{ r_k|k \in G\} = G$ が成り立つことを意味する.
(4)
$k \in G$ なるすべての整数 $k$ について $ak \equiv r_k\ (\text{mod}\ p)$ の辺々を掛けると, (1), (3) から \[ a^{n-1}(p-1)! \equiv (p-1)!\ (\text{mod}\ p)\] となる. $(p-1)!$ は $p$ と互いに素なので, (2) から, $a^{n-1} \equiv 1\ (\text{mod}\ p)$ が成り立つ.
(5)
仮定から, $ed$ はある整数 $k$ を用いて \[ ed = (p-1)(q-1)k+1\] と書ける. よって, \begin{align*} b^d &\equiv (a^e)^d = a^{ed} \\ &= a^{(p-1)(q-1)k+1} = (a^{p-1})^{(q-1)k}a \\ &\equiv 1^{(q-1)k}a = a\ (\text{mod}\ p) \end{align*} が成り立つ. 同様にして, $b^d \equiv a\ (\text{mod}\ q)$ が示される.
よって, $b^d-a$ は $p,$ $q$ の倍数であるが, $p,$ $q$ は相異なる素数であるから, $b^d-a$ は $pq = n$ の倍数である.
すなわち, $b^d \equiv a\ (\text{mod}\ n)$ が成り立つ.

背景

  • (4) の結果は「フェルマーの小定理」(Fermat's little theorem)として知られている.
  • 「フェルマーの小定理」は「オイラーの定理」(Euler's theorem) $a^{\varphi (n)} \equiv 1\ (\text{mod}\ n)$ に一般化される. ここで, $\varphi (n)$ は正の整数 $n$ を $n$ と互いに素な $n$ 以下の正の整数の個数に対応させる関数で, 「オイラーのトーシェント関数」(Euler's totient function)と呼ばれる.
  • 上記の整数 $n,$ $e,$ $d$ を用いて,「RSA 暗号」(RSA encryption)と呼ばれる暗号が, 次の方法で実現できる.
    (i)
    公開鍵の公開: $n,$ $e$ の値を送信者と受信者の間で共有する.
    (ii)
    暗号文の送信: 送信者は, 整数 $a$ ($n$ と互いに素, $0 \leqq a < n$)の値を伝えたいとき, $a^e$ を $n$ で割った余り $b$ の値を受信者に送る.
    (iii)
    復号: 受信者は, 秘密にしておいた $d$ の値を用いて, $b^d$ を $n$ で割った余りを計算して, 送信者がもともと伝えたかった整数 $a$ の値を求める.
     本問では, (iii) の方法でなぜもとの値が求まるのかを示した. $n$ が相異なる素数 $p,$ $q$ の積であるとき $\varphi (n) = (p-1)(q-1)$ であるから, 復号には $n = pq$ の場合の「オイラーの定理」$a^{\varphi (n)} \equiv 1\ (\text{mod}\ n)$ を利用している.
     この暗号方式には, 受信者が $n,$ $e$ の値を公開するだけで複数の送信者に安全に暗号化の方法を知らせられるという利点がある. このような暗号を「公開鍵暗号」(public-key encryption)と呼ぶ. 「RSA 暗号」は, 電子メールやインターネット通信, カード情報の処理など, さまざまな場面で使われている. なお,「RSA 暗号」は巨大な整数の素因数分解の難しさを通信の安全性の根拠にしているため, $p,$ $q$ には数百桁の素数が用いられている.