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

Published: 2022/1/1


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

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

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

https://integers.hatenablog.com/entry/2016/07/24/163831

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

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

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

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


Tags: 数学rsa
Next: Elasticsearch で join フィールドの値でフィルタする方法
Prev: RSA 暗号が強擬素数を用いたことにより壊れない必要十分条件