ちりもつもればミルキーウェイ

好奇心に可処分時間が奪われる

すべての平文mに対してのRSAの証明

暗号数学

はじめに

これは RSA完全理解 Advent Calendar の14日目の記事です

以前 p, qと互いに素なmでのRSAの証明をやりましたが、今回はp, qと互いに素でないときも含めた証明をやろうと思います。

探しても $p, q$ と $m$ が互いに素でないときに言及する証明は少ないので、なにかの参考になればうれしいです。

必要な知識などは前と変わらず基本的にはフェルマーの小定理がわかっていれば問題ないです。それではやっていこう

RSAの操作おさらい

準備するもの

互いに素な素数 $p, q$ と $n = p\times q$ となる $n$
$(p-1)(q-1)$ と互いに素な $e$ (逆元 $d$ の存在を保証するため)
$ed\equiv 1\pmod{(p-1)(q-1)}$ となる $d$ (剰余環における $e$ の逆元 $d$ )

暗号化/復号操作

$Enc(m, e, n) = m^{e}\bmod n$
$Dec(c, d, n) = c^{d}\bmod n$

つまり

$(m^{e})^{d} = m^{ed} \equiv m\pmod n$

が成り立てばよいです。このあたりの事前条件の説明は以前の証明でより詳しく触れているので気になる方はそちらへどうぞ

証明

$n$ の素因数である $p, q$ それぞれについて見ていきます。まずは $p$ についてです。

じつは $p$ と $m$ が互いに素のときとそうでないとき、どちらについても $m^{ed} \equiv m \pmod p$ であることを示せます

$p$ と $m$ が互いに素な場合

まず $ed$ について、条件より $ed\equiv 1\pmod{(p-1)(q-1)}$ となるように生成しているため $(p-1)(q-1)$ の倍数に1足したものと考えられます。そのため

$ed = s(p-1)(q-1) + 1$

とかけます。
これを $p$ についてフェルマーの小定理を意識した形にすると $s(q-1)$ を $k$ とおいて

$ed = k(p-1) + 1$

フェルマーの小定理より、 $ed=k(p−1)+1$ を証明したい式に代入すると以下のように整理できます

$\displaystyle m^{k(q-1) + 1} \\ = m\cdot (m^{(p-1)})^{k} \\ \equiv m\cdot (1)^{k} \\ \equiv m\pmod p$

$p$ と $m$ が互いに素ではない場合

$p$ は素数なので $m \equiv 0\pmod p$ である。
$p$ の倍数は何度べき乗しても $p$ の倍数のままなので

$m^{ed} \equiv 0\pmod p$

また、このとき $m \equiv 0\pmod p$ であるので以下のようにも表せる

$m^{ed} \equiv m\pmod p$

以上よりいずれの場合も $m^{ed} \equiv m \pmod p$ がなりたつことがわかります。
これを変形すると

$m^{ed} -m \equiv 0 \pmod p$

となり割り切れることがわかります。
同様の手順で $q$ についても

$m^{ed} -m \equiv 0 \pmod q$

となります。
$p, q$ は相違なる素数ですから $n$ でも割り切れます

$m^{ed} -m \equiv 0 \pmod n$

ここで $m^{ed}$ について $m$ を引いて $n$ で割り切れるということは $ln + m$ と表すこともできます。
ここまでの流れを整理すると

$m^{ed} \\ \equiv ln + m \\ \equiv m\pmod n$

となり $p, q$ と $m$ が互いに素でもそうでなくとも $m^{ed} \equiv m\pmod n$ が成り立つことがわかりました。証明終了