# RSA暗号がうまくいくわけ
この資料は [RSA暗号の仕組みと安全性](https://mathtrain.jp/rsaango)を参考にしています．

- $(p, q)$：2つの異なる素数．
- $N = pq$, $M=(p-1)(q-1).$
- $r$: $M$と互いに素な自然数($M$と$r$の最大公約数が1)．
- $s$: $rs \equiv 1 \mod M$ ($rs$を$M$で割った余りが1)．
- $x$: 送りたいメッセージ．

とする．このとき，RSA暗号がうまくいくためには，
1. $r$ に対して, $s$が常にただ一つ決まる．
2. $x^{rs} \equiv x \mod N$となる(「$x^{rs}$を$N$で割った余り」の世界では，$x^{rs}$と$x$は等しい)

の2つが成立すればいい．

ここでは，2つめの命題を証明する．まず，
$$
a \equiv b \mod p \text{ かつ }
a \equiv b \mod q \Rightarrow a \equiv b \mod pq
$$
を示しておこう．
証明：合同の差の性質から，
$$
a - b \equiv 0 \mod p \text{ かつ } a-b \equiv 0\mod q
$$
より， $a-b$は $p$でも$q$でも割り切れるから，$pq$で割り切れる．従って，$a-b \equiv 0 \mod pq$が成り立つ．(証明終わり)

以上のことから，
$$
x^{rs} \equiv x \mod p
$$
となることが証明できればよい(対称性から$x^{rs} \equiv x \mod q$は自明)．

$x$が$p$の倍数の場合は$x^{rs} \equiv x \equiv 0$なので自明．

$x$が$p$の倍数でない場合，
$rs = M+1 = (p-1)(q-1)+1$だから，
$$
x^{rs} = x^{M+1} = x \cdot x^{(p-1)(q-1)}.
$$

[フェルマーの小定理](https://mathtrain.jp/fermat_petit)：
> $p$が素数で，$a$が任意の自然数のとき
> $$
> a^{p} \equiv a \mod p
> $$
> $p$が素数で，$a$が$p$と互いに素な自然数のとき，
> $$
> a^{p-1} \equiv 1 \mod p
> $$

より，
$$
x^{rs} = x \cdot x^{(p-1)(q-1)} \equiv x \mod p.
$$

従って, RSA暗号では，任意の$x$について$x^{rs} \equiv x \mod N$．