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

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

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

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

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

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

証明

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

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

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

必要条件2: $N$ のすべての素因数 $p_i$ に対して、 $p_i-1 \mid ed-1$

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

必要十分条件のまとめ

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

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

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

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

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

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

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

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

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

メモ

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