RSA を既約剰余類群の観点で見たときのメモ

RSA 暗号は、本質的には既約剰余類群 $(\mathbb{Z}/N\mathbb{Z})^{\times}$ が巡回群であることを利用して、その巡回の位数を求めるためには $N$ の素因数分解が必要であることをその難しさとしている。

(自然数 $N$ を法とした)既約剰余類群とは、剰余類 $(\mathbb{Z}/N\mathbb{Z})$ に対して、その乗法について着目し、 $N$ と互いに素である数字は乗算してもやはり $N$ と互いに素になることから、これを群として扱う時にこれを表す言葉。 上にも書いたが、これを $(\mathbb{Z}/N\mathbb{Z})^{\times}$ と表記する。

既約剰余類群について、これはその構造が解明されていて、例えば以下のリンクに詳しい。

(Z/nZ)*の群構造 - INTEGERS

この記事ではの群構造についてまとめています。 1.1 と素因数分解されているとき、中国剰余定理によってが成り立つので、を得る。すなわち、問題はのときに帰着される(は自然数)。 1.2 のとき、が成り立つ。証明. 奇数が存在して、と書けることを示せばよい。に関する帰納法で証明する。なので、。が存在したと仮定すると、より、とすればよい(このときは奇数)。 Q.E.D. 1.3 命題 次の群の同型が成立する：証明. のときは明らか。、とする。また、(resp. )が生成するの部分群を (resp. )と表す。で割ったあまりを考えることによって、がわかるので、自然な埋め込みがある。1.2よりなので、が…

integers.hatenablog.com

RFC 上の RSAにおいて用いられているカーマイケル関数も、この既約剰余類群の構造から導くことが可能。

特に一般的に $p$, $q$ を素数として $N \coloncolonequals pq$ である場合、 $(\mathbb{Z}/N\mathbb{Z}) \cong (\mathbb{Z}/p\mathbb{Z}) \times (\mathbb{Z}/q\mathbb{Z})$ であること、$(\mathbb{Z}/p\mathbb{Z})^{\times}$, $(\mathbb{Z}/q\mathbb{Z})^{\times}$ はそれぞれ $(\mathbb{Z}/p\mathbb{Z})$, $(\mathbb{Z}/q\mathbb{Z})$ から $0$ を除いた要素からなる巡回群となっている。 有限個数の巡回群は、その任意の要素が生成する部分群はやはり巡回し、その位数は元の巡回群の位数の約数となる。 そのことからも、既約剰余類群の個数の倍数の回数乗算を行うことで、既約剰余類群に属する要素はそのまま復元し、そうでない 0 はそのまま 0 となることから暗号化と復号化の合成が恒等関数と同じであることが分かる。

RSA 暗号が強擬素数を用いたことにより壊れない必要十分条件

以前上記の記事で示した、 $N$ が平方因子を持たない整数である、という条件は、それぞれの分解した剰余類において、対応する既約剰余類群は $0$ のみが省かれていること、という条件に等しい。