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

# 質問

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

  * そもそも暗号化が上手く動作しない?
  * それとも、暗号化はできるが、その通信は実は容易に傍受できてしまったりする?
CC BY-SA 4.0
2020-12-18T08:18:16.903
72738
2021-12-29T16:54:43.967
754
question
アルゴリズム 暗号理論 rsa
rsa で用いる素数 p, q がもし素数ではなかったら何がおこる?
[RSA暗号と擬素数](http://deztec.jp/x/05/faireal/faireal-7-01-index.html)

例えばこんなページで考察されていますが

確率的素数テストに合格してしまったが、実際には素数ではない数のことを擬素数と呼びます。そしてたまたま得られた鍵（＝素数）が擬素数であった場合というのは

\- 秘密鍵とは巨大な素数  
\- 公開鍵とは巨大な素数と巨大な素数の積（２つの素数の積）

であることが期待されているが、実は片方が擬素数だったという状況です。

RSA の処理は除算して余りを取るだけなので

> そもそも暗号化が上手く動作しない?

暗号・復号に関しては何の問題も発生しません。うまく動きます。

> その通信は実は容易に傍受できてしまったりする?

擬素数のほとんどは素数２つの積であったりするので、ブルートフォースな素因数分解に要する時間が短くなった、と考えることができます。が、もし暗号鍵が真に素数だったなら素因数分解（＝暗号解読）に1000年を要する状況が、擬素数だったら500年を要するくらいに短縮されるだけです。他にも事情があって、実際問題として第三者が傍受して有効な期間内に暗号を解いてしまう心配をする必要はないと考えてよいです。
CC BY-SA 4.0
2020-12-18T09:13:31.150
72744
2020-12-31T04:38:18.427
2020-12-31T04:38:18.427
3060
8589
72738
answer
秘密鍵(p,q)が合成数だった場合に実際にどうなるかは[RSA鍵の生成時に確率的素数判定法を使って問題ないのか -
hnwの日記](https://hnw.hatenablog.com/entry/20140610)に事例があります。

SSHの公開鍵認証で試した結果が記載されていますが、opensslで普通に暗号化・復号した場合は復号時に

```

    RSA operation error
    139806236009728:error:0407109F:rsa routines:RSA_padding_check_PKCS1_type_2:pkcs decoding error:crypto/rsa/rsa_pk1.c:251:
    139806236009728:error:04065072:rsa routines:rsa_ossl_private_decrypt:padding check failed:crypto/rsa/rsa_ossl.c:491:
    
```

こんなエラーで失敗します。(正確に言うとごく希に「エラーは出ないが誤った平文」になるときがあるはず)

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

RSAは3素数以上でも成り立つ(multi-prime RSA)ので、p,qのいずれかが合成数だったとしてもアルゴリズム的に破綻するわけではありません。

暗号化はそのまま走ります。(いずれにしても公開鍵は合成数なので)

復号はそのままでは動かないので手直しが必要です。(鍵の計算だけやり直せばよいのかロジックも直す必要があるのかまではわかりません。[Broken RSA -
バランスを取りたい](https://xrekkusu.hatenablog.jp/entry/2015/08/17/001939)によると鍵の計算だけでよい?)

誤った鍵で暗号化された暗号文がどれだけ危険かは、Miller-Rabin
素数判定法が「数値の質」まで判定してくれるのか、と言い換えることもできます。まともな実装で「たまたますり抜けた」が起きたぐらいなら多分大丈夫なんじゃないかな、と思いますが、突っ込んで考えてないのでよくわかりません。

そもそも「たまたますり抜けた」が現実に起きる可能性はほとんどない上、起きたとしても復号処理の結果でエラーになるか化けてるかで気づけるので、あまり気にすることでもない気がします。
CC BY-SA 4.0
2020-12-27T12:36:51.807
72924
2020-12-27T12:36:51.807
5793
72738
answer
ひとまず、「miller rabin の round は pass する可能性があるが、しかし素因数分解可能な素数」を用いて秘密鍵を作ってみました。

この鍵の prime1 は、 1195068768795265792518361315725116351898245581 であって、a = 2 のときの
miller-rabin は probably prime ですが、 a = 103 などで composite 判定されるような合成数です。(prime2
の方は、 [(openssl の) RSA
秘密鍵の中身はそれぞれ何を表す?](https://ja.stackoverflow.com/q/71820/754) から流用してます)

この鍵を用いて計算すると、例えば

```

    $ printf '%s\n' b | openssl rsautl -encrypt -inkey ./as_pem | openssl rsautl -decrypt -inkey ./as_pem
    b
    
```

となり、ひとまずだいたいの場合は、問題なく暗号・復号化が可能そうです。

どうして、合成数でも問題なく動作するのか (suzukis さんの回答と何が違うのか) はまだちょっと分かっていないです。

```

    Private-Key: (1686 bit)
    modulus:
        31:40:6f:5c:f1:04:91:ea:91:7f:de:66:77:6a:6f:
        18:14:34:fe:ce:56:d8:28:9c:7d:38:af:77:93:39:
        47:2f:cd:a1:5c:5f:fa:0e:8f:8c:93:08:87:0b:fa:
        40:32:7c:a6:29:5a:4a:03:b4:e5:4a:66:4d:84:cc:
        ef:cc:fb:92:72:8e:f4:03:6d:6c:16:d5:38:7e:2d:
        cc:3e:e9:71:3d:96:06:5b:f2:2b:29:45:27:03:93:
        bf:77:cb:35:c9:74:d6:72:5c:8b:2f:fe:d5:85:0e:
        6a:47:8a:6d:76:38:9c:9a:04:12:4c:e6:cd:2f:b2:
        65:50:47:2c:97:a7:bd:b9:16:2c:3e:ed:3b:1c:a6:
        b8:3c:20:32:ac:1c:06:5d:c8:9f:6e:44:67:b5:2f:
        6b:b2:77:4e:71:a8:62:4f:88:65:4b:4e:5e:dc:1b:
        83:5c:c8:68:d9:47:27:81:7c:e8:9c:0f:99:ed:de:
        20:5d:10:b2:fc:df:ab:44:57:22:a6:fe:a3:05:89:
        5c:0a:b1:70:8c:14:cc:de:34:7b:94:c0:b1:90:a7:
        a9
    publicExponent: 65537 (0x10001)
    privateExponent:
        08:43:56:7b:ba:1f:09:69:18:98:a2:a4:3f:d0:2e:
        4b:d4:a6:10:5b:6e:11:d6:ba:cb:eb:49:e2:02:0c:
        54:d9:d8:f4:6c:94:b6:4c:3d:8e:91:14:85:36:29:
        36:de:c9:a8:82:b9:f1:c1:f1:26:d7:29:a2:06:5d:
        c3:e3:51:c8:53:09:f1:8d:56:f0:db:e3:41:a7:19:
        f0:a1:21:ca:f2:c5:96:a7:cf:dc:bc:0b:2b:dc:d9:
        07:29:3c:f8:f2:bc:e2:81:ed:21:8d:be:c3:5f:2a:
        65:4b:c4:c2:b1:03:03:92:09:fd:16:a8:8b:02:45:
        8d:49:82:1c:f1:d2:c2:f9:69:4d:36:dd:cf:f4:c6:
        1f:56:e5:79:c1:41:ae:cc:8c:4b:73:35:10:d5:2a:
        ce:0c:33:23:6f:ef:bb:04:4e:20:65:a5:68:a6:d9:
        d0:70:8c:d2:35:dc:8e:0f:bb:2d:08:6b:43:89:49:
        bb:82:95:f2:06:a5:25:f3:cb:65:e8:ce:6d:7c:3c:
        83:a8:87:38:fd:a9:6c:3a:d3:38:82:aa:04:44:69:
        d5
    prime1:
        35:96:b7:77:66:7a:97:06:14:49:3b:eb:d9:d7:5c:
        9d:64:d9:cd
    prime2:
        00:eb:48:0c:37:c0:ea:db:a9:e6:c3:7c:a3:33:b2:
        2c:70:90:50:8d:b3:22:b1:55:75:6c:5e:b7:1a:32:
        4c:d9:fa:17:42:ba:ba:2c:dc:36:ce:71:6a:f6:f3:
        a7:0e:91:f1:61:b4:94:d8:07:dd:98:2a:88:6a:5e:
        fa:4f:84:cc:1a:25:fe:b7:71:5b:60:62:85:a8:0b:
        53:98:7c:26:09:98:ef:12:d0:93:03:9f:00:8a:ee:
        72:0d:c6:8f:21:9d:0a:ce:44:ef:8b:5c:18:c5:21:
        7c:7d:1e:a5:29:55:11:7e:ec:b3:14:8c:08:f3:33:
        dc:cf:c7:b7:74:a3:ad:ca:53:b3:72:71:23:1c:ea:
        99:7d:0b:81:77:d0:82:67:26:aa:9d:ac:ec:bf:d0:
        df:63:86:61:68:c4:89:ab:ff:36:14:6a:ef:09:91:
        82:30:d7:b7:36:5c:cf:c5:c2:91:04:4d:1a:2c:64:
        66:ea:a9:4b:29:5d:a1:80:fb:ae:2e:b9:4d
    exponent1:
        0d:bf:a3:46:60:e6:66:c4:ca:83:97:7a:05:23:b9:
        c1:2f:d4:a9
    exponent2:
        00:a0:52:32:c9:16:f2:b2:05:be:d1:fc:2e:f4:fd:
        f6:dc:28:ea:4a:f4:02:b2:d5:a9:b2:d3:83:6f:1d:
        51:52:c2:e0:70:be:ee:37:bd:42:b7:3f:7f:84:91:
        18:87:8c:18:ef:db:ee:04:9a:af:7b:8d:97:f0:eb:
        91:22:f8:39:5f:a3:fe:42:1f:c3:05:15:7d:3f:b9:
        a0:17:ea:98:bc:b7:72:48:de:c9:1e:91:8c:fc:1e:
        68:a7:4c:62:a1:a3:f2:06:05:e1:38:93:e3:e9:07:
        dd:5d:20:b1:a8:4d:68:23:95:c4:9d:3e:a2:a6:9d:
        f3:5b:be:1a:1b:27:a1:37:99:fb:50:03:19:cb:0d:
        6c:d3:51:30:c2:64:d9:46:d2:89:35:f1:ec:4c:f4:
        56:13:ea:30:9c:04:38:4f:74:12:f4:ac:bc:ff:47:
        20:70:89:bd:35:14:df:1b:41:6e:31:81:1c:51:9d:
        84:a7:67:fe:68:4c:7d:cd:77:32:04:72:8d
    coefficient:
        0d:0f:ef:59:13:2a:d5:2a:b0:71:66:1f:cb:82:99:
        3a:e0:17:1d
    -----BEGIN RSA PRIVATE KEY-----
    MIIDewIBAAKB0zFAb1zxBJHqkX/eZndqbxgUNP7OVtgonH04r3eTOUcvzaFcX/oO
    j4yTCIcL+kAyfKYpWkoDtOVKZk2EzO/M+5JyjvQDbWwW1Th+Lcw+6XE9lgZb8isp
    RScDk793yzXJdNZyXIsv/tWFDmpHim12OJyaBBJM5s0vsmVQRyyXp725Fiw+7Tsc
    prg8IDKsHAZdyJ9uRGe1L2uyd05xqGJPiGVLTl7cG4NcyGjZRyeBfOicD5nt3iBd
    ELL836tEVyKm/qMFiVwKsXCMFMzeNHuUwLGQp6kCAwEAAQKB0whDVnu6HwlpGJii
    pD/QLkvUphBbbhHWusvrSeICDFTZ2PRslLZMPY6RFIU2KTbeyaiCufHB8SbXKaIG
    XcPjUchTCfGNVvDb40GnGfChIcryxZanz9y8Cyvc2QcpPPjyvOKB7SGNvsNfKmVL
    xMKxAwOSCf0WqIsCRY1Jghzx0sL5aU023c/0xh9W5XnBQa7MjEtzNRDVKs4MMyNv
    77sETiBlpWim2dBwjNI13I4Puy0Ia0OJSbuClfIGpSXzy2Xozm18PIOohzj9qWw6
    0ziCqgREadUCEzWWt3dmepcGFEk769nXXJ1k2c0CgcEA60gMN8Dq26nmw3yjM7Is
    cJBQjbMisVV1bF63GjJM2foXQrq6LNw2znFq9vOnDpHxYbSU2AfdmCqIal76T4TM
    GiX+t3FbYGKFqAtTmHwmCZjvEtCTA58Aiu5yDcaPIZ0KzkTvi1wYxSF8fR6lKVUR
    fuyzFIwI8zPcz8e3dKOtylOzcnEjHOqZfQuBd9CCZyaqnazsv9DfY4ZhaMSJq/82
    FGrvCZGCMNe3NlzPxcKRBE0aLGRm6qlLKV2hgPuuLrlNAhMNv6NGYOZmxMqDl3oF
    I7nBL9SpAoHBAKBSMskW8rIFvtH8LvT99two6kr0ArLVqbLTg28dUVLC4HC+7je9
    Qrc/f4SRGIeMGO/b7gSar3uNl/DrkSL4OV+j/kIfwwUVfT+5oBfqmLy3ckjeyR6R
    jPweaKdMYqGj8gYF4TiT4+kH3V0gsahNaCOVxJ0+oqad81u+GhsnoTeZ+1ADGcsN
    bNNRMMJk2UbSiTXx7Ez0VhPqMJwEOE90EvSsvP9HIHCJvTUU3xtBbjGBHFGdhKdn
    /mhMfc13MgRyjQITDQ/vWRMq1SqwcWYfy4KZOuAXHQ==
    -----END RSA PRIVATE KEY-----
    
```
CC BY-SA 4.0
2020-12-30T14:20:36.553
72987
2020-12-30T14:20:36.553
754
72738
answer
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 は壊れない。
CC BY-SA 4.0
2021-12-29T16:54:43.967
85402
2021-12-29T16:54:43.967
754
72738
answer