RSA暗号

暗号化

問題文の通り。オーバーフローを防ぐため、計算の途中過程で毎回$n$で割った余りをとること。計算の際には、二分累乗法を使うことで計算量を$O(\log\ e)$に抑えられる。$\\$

復号

「RSA暗号の仕組み」の3.を満たすような$d$を求めると、$a$は$b^d$を$n$で割った余りとなる。$\\$

証明$\\$

問題文の最後にある「ヒント」より、$b^d\equiv a^{l(p-1)(q-1)+1}\ ({\rm mod}\ n)\ (l$は整数$)$と書けるので、$a^{l(p-1)(q-1)+1}\equiv a\ ({\rm mod}\ n)\cdots (1)$を示せば良い。$\\$ ここで、$a^{l(p-1)(q-1)+1}\equiv a\ ({\rm mod}\ p)\cdots (2),\ a^{l(p-1)(q-1)+1}\equiv a\ ({\rm mod}\ q)\cdots (3)$とする。$p,q$は相異なる素数であるから互いに素。よって、中国剰余定理より$(1)\Leftrightarrow (2)$かつ$(3)$が成立する。よって、$(2)$と$(3)$を示せば良い。$\\$

(2)の証明

ここでは${\rm mod}\ p$とする。$\\$ $a\equiv 0$ならば、$a^{l(p-1)(q-1)+1}\equiv 0\equiv a$となる。 $a\not\equiv 0$ならば、フェルマーの小定理より$a^{p-1}\equiv 1$なので、$a^{l(p-1)(q-1)+1}=(a^{p-1})^{l(q-1)}\cdot a\equiv1^{l(q-1)}\cdot a= a$となる。$\\$ 以上より、$(2)$が示された。$\\$

$(3)$は、上の証明で$p$と$q$を入れ替えることで示される。 以上より、$b^d\equiv a({\rm mod}\ n)$が示された。 $\\$

dの求め方$\\$

$e$は$\phi (n)$と互いに素なので、$de\equiv1({\rm mod}\ \ \phi(n))$を満たすような$d$は必ず存在し、$d$は$e$の${\rm mod}\ \phi(n)$における逆元である。

計算量について

下処理：$n$の素因数分解は$O(\sqrt{n}),\ d$の計算は$O(\log\phi (n))=O(\log\ n)$で行える。$\\$ 各$b_i$についての計算：二分累乗法により、$O(\log\ d)$で行える。$d<\phi(n)$なので、最悪の場合の計算量は$O(\log\phi (n))=O(\log\ n)$となる。$\\$ よって、計算量の合計は$O(\sqrt{n}+L\log\ n)$となる。

参考

実際の暗号において、$n$は$10^{300}$から$10^{1000}$程度の値になる。一方、$L$は1GBでも$10^9$程度なので、$\sqrt{n}\gg L$より実際のオーダーは$O(\sqrt{n})$となる。このことから、本暗号の解読において$n$の素因数分解がボトルネックになることを示すことができた。

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378