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

Published: 2021/12/30


まず、 RSA 暗号の定義については以前の記事を参照。

RSA 暗号は、その秘密鍵である素数 pp, qq の生成にあたり、ミラー–ラビン素数判定法を用いるのが一般的ではあるが、このアルゴリズムは確率的にしか合成数であることを検出できず、ごく小さな確率ではあるが、合成数がこのテストを通過してしまう場合がある。 このような合成数のことを、一般的に強擬素数と呼ぶ。

今、RSA 暗号で復号が成功することの証明は、秘密鍵 pp, qq が素数であることに依存していた。 pp ないし qq が、その実、強擬素数であった場合に、 RSA 暗号がどのように振る舞うのか、特に、メッセージを問題なく復号化できるかどうかは、自明ではない。 なので、それについて調べた結果を記す。

必要条件1: NN は平方因子を持たない整数である

RSA による暗号化と復号化で 0M<N0 \leq M < N を満たす全ての MM が正しく復号できるためには、 NN は平方因子を持たない整数である必要がある。

証明

今、仮に NN が平方因子を持っていたとする。 NN の素因数分解して、 pip_i を素数として、 N=ipiriN = \prod_{i} p_i^{r_i} と表せる。 NN が平方因子を持っているとき、この中の添字 jj が存在して、 rj2r_j \geq 2

剰余環に対して一般化された中国剰余の定理によれば、 Z/NZi(Z/piriZ)\mathbb{Z}/N\mathbb{Z} \cong \prod_{i} (\mathbb{Z}/p_i^{r_i}\mathbb{Z}) であり、 Mpjrj1(modpjrj)M \equiv p_j^{r_j - 1} \pmod{p_j^{r_j}} であった時、

M2=pjrj+rj2=pjrjpjrj20(modpjrj)\begin{align*} M^2 &=& p_j^{r_j + r_j - 2} &\\ &=& p_j^{r_j}p_j^{r_j - 2} &\\ &\equiv& 0 &\pmod{p_j^{r_j}} \\ \end{align*}

であり、 M0(modpjrj)M \equiv 0 \pmod{p_j^{r_j}} であった場合と区別がつかなくなってしまい、復号が正しく動かないことが分かる。 (雑に言うと、 Z/pjrjZ\mathbb{Z}/p_j^{r_j}\mathbb{Z} は零因子を持っているため、べき乗を行う操作は全単射ではない)

必要条件2: NN のすべての素因数 pip_i に対して、 pi1ed1p_i-1 \mid ed-1

NN が平方因子を持たない整数であったとする。 このとき素数 pip_i を用いて、 N=ipiN = \prod_i p_i と記述できる。 すべての MMMedM(modN)M^{ed} \equiv M \pmod{N} を満たすことは、各 ii に注目すれば、そのすべてで MedM(modpi)M^{ed} \equiv M \pmod{p_i} が成立することと等しい。 特に、各 Z/piZ\mathbb{Z}/p_i\mathbb{Z} には原始根が存在し、その原始根に対しては、繰り返しのかけ算で巡回するので、それに対しても eded 乗した時に元の数とmodpi\mod p_i で等しくなるためには、 pi1ed1p_i - 1\mid ed - 1 であることが必要十分であると分かる。

必要十分条件のまとめ

RSA 暗号が全ての可能なメッセージ MM に対して壊れないための必要十分条件は、

  1. N=pqN \coloncolonequals pq が平方因子を持たない整数であること、かつ
  2. NN のすべての素因数 pip_i に対して、 pi1ed1p_i - 1 \mid ed - 1

定理: pp ないし qq は、素数であるかカーマイケル数であって、互いに素であれば、 RSA によってメッセージは壊れない

https://en.wikipedia.org/wiki/Carmichael_number

カーマイケル数には、以下の性質がある。

  1. カーマイケル数は平方因子を持たない
  2. カーマイケル数 nn は、そのすべての素因子 pp に対して、 p1n1p - 1 \mid n - 1

よって、素数ないしカーマイケル数 pp, qq が互いに素であれば、 N=pqN = pq は平方因子を持たない。

また、 dd の定義により、ある整数 kk が存在して、 ed1=kLCM(p1,q1)ed - 1 = k\mathrm{LCM}(p-1, q-1) である。 今、 NN は平方因子を持たないので、その素因数 pip_i を用いて N=ipiN = \prod_i p_i と記述したとき、これがすべて ed1ed-1 を割り切れば良い。 ppqq が互いに素であると仮定したので、各 pip_i に対して pipp_i \mid p もしくは piqp_i \mid q が成り立つ。 pipp_i \mid p であったとしても証明の対称性を失わないので、これを仮定する。 この時、 pp が素数であるならば、 pi=pp_i = p なので、 pi1p1p_i - 1 \mid p - 1。 そうでない場合、前提により、 pp はカーマイケル数なので、上記の2つめのカーマイケル数の性質により、 pi1p1p_i - 1 \mid p - 1p1LCM(p1,q1)p - 1 \mid \mathrm{LCM}(p-1, q-1) であるため、 pi1LCM(p1,q1)p_i - 1 \mid \mathrm{LCM}(p-1, q-1)。 よって pi1ed1p_i -1\mid ed - 1 が成立する。

以上より、 pp, qq が互いに素であり、かつそれぞれが素数もしくはカーマイケル数である時、 RSA 暗号による暗号化と復号化の処理によって元のメッセージ MM が復元できることが示された。

メモ

pp, qq は、冒頭に述べた通り、実用上ありうるとしたら強擬素数、ではあるのだが、強擬素数であれば RSA が壊れないのかどうかは、ちょっとまだ分かっていない。


Tags: rsa数学
Next: RSA を既約剰余類群の観点で見たときのメモ
Prev: Google Search Console の動作に対する推測