RSA暗号のlcmとphi(φ)の違い

Lの求め方が２つある

RSA暗号で$p,q$２つの素数があるとき、$L$の計算に最小公倍数(lcm(p-1, q-1))とオイラー関数(φ(pq) = (p-1, q-1))を用いる２通りがあります。

$$\begin{aligned} L &= \text{lcm} (p-1, q-1) \\ L &= (p-1)*(q-1) \end{aligned}$$

この２つの違いについて説明します。

結論

$\text{lcm}$はRSA暗号が成り立つための必要十分条件

オイラー関数はRSA暗号が成り立つ十分条件

$\text{lcm}$を用いる方が$d$を小さくできるため高速化に繋がる。どちらを用いても、数学的に問題は無い。

証明

前提知識：RSA暗号の計算方法、フェルマーの小定理

RSA暗号が成立するためには以下の式を満たす必要があります。

$$M = M^{ed} \mod N$$

この式を変形していきます。

$$\begin{align} M(M^{ed-1} - 1) &= 0 \mod N \notag \\ M^{ed-1} - 1 &= 0 \mod N \notag\\ \end{align}$$

ところで、$N = pq$であるので、$M^{ed-1} - 1 = 0 \mod pq$ということは、$M^{ed-1} - 1$は$p$の倍数かつ、$q$の倍数であると分かります。

式で表現すると、

$$\begin{align} M^{ed-1} - 1 &= 0 \mod p \\ M^{ed-1} - 1 &= 0 \mod q \\ \end{align}$$

となります。これら２つは$\text{mod}$の値が違うだけです。$M^{ed-1} - 1 = 0 \mod p$を式(1)、$M^{ed-1} - 1 = 0 \mod q$を式(2)とします

ここで、フェルマーの小定理を考えます。

$$a^{p-1} = 1 \mod p$$

この式の両辺を$a$倍し、変形します。

$$\begin{align} a^p = a \mod p \notag \\ a(a^{p -1} - 1) = 0 \mod p \notag \\ a^{p -1} - 1 = 0 \mod p \\ \end{align}$$

得られた$a^{p -1} - 1 = 0 \mod p$を式(3)とします。

ここで、式(1)と式(3)を見ると、

$$\begin{aligned} M^{ed-1} - 1 &= 0 \mod p \\ a^{p -1} - 1 &= 0 \mod p \end{aligned}$$

式(1)が成立するには$ed-1 = k(p-1)$となる$(1 \leqq)k$が存在すれば良いことになります。

同様の手順で式(2)が成立するには$ed-1 = l(q-1)$となる$(1 \leqq)l$が存在すれば良いことになります。

つまり、$ed-1$は$p-1$の倍数かつ、$q-1$の倍数、であることが必要です。

$p-1$の倍数かつ、$q-1$の倍数である数を$L$としたとき、以下の式が成立することが。RSA暗号が成立する条件です。

$$ed - 1 = 0 \mod L$$

となります

参考文献

はやわかり RSA :https://www.mew.org/~kazu/doc/rsa.html

(最終閲覧：2022/09/24)