rsa で用いる素数 p, q がもし素数ではなかったら何がおこる?


[rsa の素数のペアはどのように生成される?](https://ja.stackoverflow.com/q/72115/754)
の問いで調べていった結果、 RSA の秘密鍵(素数 p, q) は Miller-Rabin
のテストによって、確率的にそれが素数であることを判定しているのだ、ということを学びました。ここでふと、これだけ世の中で RSA
鍵が使われているのであれば、そのうちのひとつぐらいは、 Miller-Rabin の素数判定を Pass
した合成数を素数として取り扱ってしまっているケースがあるのではないか、と思いました。

# 質問

もし、 RSA の秘密鍵の素数たちのいずれかが、その実、素数ではなく合成数だった場合、何が発生しますか?

  * そもそも暗号化が上手く動作しない?
  * それとも、暗号化はできるが、その通信は実は容易に傍受できてしまったりする?




RSA 暗号を用いて、暗号化と復号化を行った場合、

  1. 法として用いる自然数`N`が、[平方因子をもたない整数](https://ja.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E5%9B%A0%E5%AD%90%E3%82%92%E3%82%82%E3%81%9F%E3%81%AA%E3%81%84%E6%95%B4%E6%95%B0)であること
  2. `N` のすべての素因数 `p_i` に対して、 `p_i - 1` が `ed - 1` を割り切る (e は公開鍵の指数部、 d は秘密鍵。)

の2つが、すべての 0 <= M < N に対して RSA の暗号化と復号化を行った際に、元のメッセージ M を取得できる必要十分条件。

また、用いた(擬)素数 p, q が、互いに素であって、かつそれぞれが素数であるかカーマイケル数である時に、任意のメッセージ `M` は RSA
の暗号化と復号化の処理で元に戻る。( M ≡ M^{ed} mod N が成立する)

<https://blog.yukii.work/posts/2021-12-30-condition-for-rsa-not-to-break>

下に証明を記述しますが、ここのサイトでは数式が記述できなかったと思うので、数式を用いたより見やすい記述は、上記の記事に記載したので、そこから確認できます。

# 証明

前提として、 `e` を公開鍵、`p`,`q` を(疑)素数、 `N:=pq`, `d` を `ed ≡ 1 (mod LCM(p-1,q-1))`
を見たす自然数とする。

## 平方因子を持たない整数である必要性

今、仮に `N` が平方因子を持っていたと仮定する。

すると、N を素因数分解して、素数 p_i と、その乗数 r_i を用いて、 N = Πp_i^{r_i} が得られた時、 r_j >= 2 を満たす添字
j が存在する。

(Z/NZ)
は剰余環であるが、[一般化された中国人剰余定理](https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E3%81%AE%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86#%E5%AE%9A%E7%90%86%E3%81%AE%E4%B8%80%E8%88%AC%E5%8C%96)を用いて
(Z/NZ) ~= Π(Z/p_i^{r_i}Z) と各素因数たちの剰余環の直積と同型である。

(Z/p_j^{r_j}Z) の剰余環のふるまいに注目すると、この環は r_j>=2 より、 p_j の倍数が零因子となる。よってこの剰余環は 0
それ自身と p_j の倍数のうちのいずれかが、 M をかける演算によって 0 になっていくので、全射ではない。全射でないので、これを繰り返し適用しても
(Z/p_j^{r_j}Z)全体への射にはならず、引いては Z/NZ においても全射ではないことが分かり、すべてのメッセージ M
は復元できないことが分かる。

## p_i - 1 が ed-1 を割り切れば必要十分

N が平方因子を持たない整数であったとする。Nの真の素因数たちを p_i としたとき、その積として N は表せる。それらについて (Z/NZ) ~=
Π(Z/p_iZ) で分解してそれぞれの剰余環部分について考える。 p_i は素数なので、ある原始根p'が存在して、 p'^{p_i - 2} !≡ 1
mod p_i かつ p'^{p_i - 1} ≡ 1 mod p_i。この原始根についても ed 乗で復元されている必要があるので、 p_i - 1 |
ed - 1。これはすべての i について成立することで、 M^ed ≡ M であるために必要十分的。

## カーマイケル数または素数であれば復元可能

[カーマイケル数](https://en.wikipedia.org/wiki/Carmichael_number) には以下の性質がある。

  1. 平方因子を持たない
  2. すべての素因数 p に対して、 p - 1 は「そのカーマイケル数自身 - 1」を割り切る

p, q が互いに素、かつ、素数もしくはカーマイケル数であったとする。

互いに素な平方因子を持たない2つの数たちの積は、やはり平方因子を持たない。よってこの条件の元 N は平方因子を持たない。

N のすべての素因数をそれぞれ p_i として表して、 p, q は互いに素なので、 p_i | p もしくは p_i | q が成立する。仮に p_i |
p であったとすると、 p が素数であれば p_i = p より p_i - 1 | p -1 | LCM(p-1, q-1)。 p
がカーマイケル数であれば、カーマイケル数の性質により p_i - 1 | p - 1 | LCM(p-1, q-1)。

今、 d の定義によりある整数 k を用いて ed - 1 = kLCM(p-1, q-1) と表わせるので、よって p_i - 1 | ed - 1。

以上より、 p, q が互いに素であって、素数もしくはカーマイケル数であれば RSA は壊れない。




RSA 暗号を用いて、暗号化と復号化を行った場合、

  1. 法として用いる自然数`N`が、[平方因子をもたない整数](https://ja.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E5%9B%A0%E5%AD%90%E3%82%92%E3%82%82%E3%81%9F%E3%81%AA%E3%81%84%E6%95%B4%E6%95%B0)であること
  2. `N` のすべての素因数 `p_i` に対して、 `p_i - 1` が `ed - 1` を割り切る (e は公開鍵の指数部、 d は秘密鍵。)

の2つが、すべての 0 <= M < N に対して RSA の暗号化と復号化を行った際に、元のメッセージ M を取得できる必要十分条件。

また、用いた(擬)素数 p, q が、互いに素であって、かつそれぞれが素数であるかカーマイケル数である時に、任意のメッセージ `M` は RSA
の暗号化と復号化の処理で元に戻る。( M ≡ M^{ed} mod N が成立する)

<https://blog.yukii.work/posts/2021-12-30-condition-for-rsa-not-to-break>

下に証明を記述しますが、ここのサイトでは数式が記述できなかったと思うので、数式を用いたより見やすい記述は、上記の記事に記載したので、そこから確認できます。

# 証明

前提として、 `e` を公開鍵、`p`,`q` を(疑)素数、 `N:=pq`, `d` を `ed ≡ 1 (mod LCM(p-1,q-1))`
を見たす自然数とする。

## 平方因子を持たない整数である必要性

今、仮に `N` が平方因子を持っていたと仮定する。

すると、N を素因数分解して、素数 p_i と、その乗数 r_i を用いて、 N = Πp_i^{r_i} が得られた時、 r_j >= 2 を満たす添字
j が存在する。

(Z/NZ)
は剰余環であるが、[一般化された中国人剰余定理](https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E3%81%AE%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86#%E5%AE%9A%E7%90%86%E3%81%AE%E4%B8%80%E8%88%AC%E5%8C%96)を用いて
(Z/NZ) ~= Π(Z/p_i^{r_i}Z) と各素因数たちの剰余環の直積と同型である。

(Z/p_j^{r_j}Z) の剰余環のふるまいに注目すると、この環は r_j>=2 より、 p_j の倍数が零因子となる。よってこの剰余環は 0
それ自身と p_j の倍数のうちのいずれかが、 M をかける演算によって 0 になっていくので、全射ではない。全射でないので、これを繰り返し適用しても
(Z/p_j^{r_j}Z)全体への射にはならず、引いては Z/NZ においても全射ではないことが分かり、すべてのメッセージ M
は復元できないことが分かる。

## p_i - 1 が ed-1 を割り切れば必要十分

N が平方因子を持たない整数であったとする。Nの真の素因数たちを p_i としたとき、その積として N は表せる。それらについて (Z/NZ) ~=
Π(Z/p_iZ) で分解してそれぞれの剰余環部分について考える。 p_i は素数なので、ある原始根p'が存在して、 p'^{p_i - 2} !≡ 1
mod p_i かつ p'^{p_i - 1} ≡ 1 mod p_i。この原始根についても ed 乗で復元されている必要があるので、 p_i - 1 |
ed - 1。これはすべての i について成立することで、 M^ed ≡ M であるために必要十分的。

## カーマイケル数または素数であれば復元可能

[カーマイケル数](https://en.wikipedia.org/wiki/Carmichael_number) には以下の性質がある。

  1. 平方因子を持たない
  2. すべての素因数 p に対して、 p - 1 は「そのカーマイケル数自身 - 1」を割り切る

p, q が互いに素、かつ、素数もしくはカーマイケル数であったとする。

互いに素な平方因子を持たない2つの数たちの積は、やはり平方因子を持たない。よってこの条件の元 N は平方因子を持たない。

N のすべての素因数をそれぞれ p_i として表して、 p, q は互いに素なので、 p_i | p もしくは p_i | q が成立する。仮に p_i |
p であったとすると、 p が素数であれば p_i = p より p_i - 1 | p -1 | LCM(p-1, q-1)。 p
がカーマイケル数であれば、カーマイケル数の性質により p_i - 1 | p - 1 | LCM(p-1, q-1)。

今、 d の定義によりある整数 k を用いて ed - 1 = kLCM(p-1, q-1) と表わせるので、よって p_i - 1 | ed - 1。

以上より、 p, q が互いに素であって、素数もしくはカーマイケル数であれば RSA は壊れない。

