RSA暗号

RSA暗号はもっとも古い公開鍵暗号で、1974年頃にイギリスの諜報機関GHCQのJ.エリスらが考案した暗号方式です。もっとも、それは国家機密として公となることはなく、RSA暗号は1977年に独自に再発見したRivest, Shamir, Adlemanのイニシャルからとって命名されています。RSA暗号のアルゴリズムは次の通りです。

相異なる素数$p, q$ (できれば桁数がほぼ同じで、かつ $gcd(p-1, q-1)=2$となるものが好ましいとされている) を生成し、整数 $(p-1)(q-1)$ と互いに素な整数 $e$ を選び、 $$ed \equiv 1 \pmod{(p-1)(q-1)}$$ を満たす整数 $d$ を求めておく。このような整数$d$の存在は、ベズーの補題によって保証され、拡張ユークリッド互除法 (多項式時間アルゴリズム) で求めることができます。 $n := pq$ (RSAモジュールとよぶ) として、 $(n, e)$ を公開鍵として公開します。 $d$ は秘密鍵として使用し、 $p, q$ は秘密にしておきます。

暗号化するときは、平文 $m$ に対して、 $$m^e \mod{n}$$ を計算して、これを暗号文とします。

秘密鍵$d$をもっている人が、平文$m$の暗号文$m^e$を復号するときは、これを$d$乗します。すると、

$$m^{ed} \equiv m \pmod{n}$$

となって、平文を復号できます。

復号がこのようにうまくいくことは、 (平文$m$が$n$と公約数をもつ場合を除いては) フェルマーの小定理を一般化したオイラーの定理によって説明できます。

オイラーの定理によれば、$m$と$pq$が互いに素のときは、

$$m^{(p-1)(q-1)} \equiv 1 \pmod{pq}$$

でした。

ところで、$ed \equiv 1 \pmod{(p-1)(q-1)}$ の意味するところは、「$ed$を$(p-1)(q-1)$で割ると$1$余る」なのだから、ある整数$k$があって、

$$ed = (p-1)(q-1)k + 1$$

となります。

ですので、$m$と$pq \ (=n)$が互いに素のときであれば、

$$m^{ed} = m^{(p-1)(q-1)k+1} = (m^{(p-1)(q-1)})^k \cdot m \equiv 1^k \cdot m \equiv m \pmod{n (=pq)}$$

となり、復号できることが確かめられます。

$m$と$n$が互いに素でないときも、次のようにうまく復号できることが確かめられます。まず、$\mod{n}$をとっているのですから、平文が最大で$n$通りしかありえなく¹って、$0 \le m \lt n$ となることに注意してください。

$0 \le m \lt n$ ですから、$m$は$n$の倍数ではなく、$n$と$1, -1$以外の公約数をもちます²。$n=pq$なのですから、

$$gcd(m, n) = p$$

あるいは

$$gcd(m, n) = q$$

のいずれかになりますが、ここでは$gcd(m,n)=p$とおきましょう。$gcd(m,n)=q$の場合も全く同じように証明できるため、どちらか一方だけ証明できればそれで良いのです。

このとき、ある$k \in \mathbb{Z}$があって、

$$m=kp$$

となります。$p$は$m$の約数であると言っているだけです。$gcd(m,n)=p$なので、$p$は$m$の約数でもあるし、$n$の約数でもあるからです。

整数の除算 (割り算) は常に可能なのだから、ある$j, r$があって、

$$m=jq+r, 0 \le r \lt q$$

も言えます。

$p, q$が相異なる素数であることから、$gcd(p,q)=1$ですから、ベズーの補題より、ある整数$s,t$があって、

$$ps+qt=1$$

です。このとき、この式の両辺を$q$で割った余りを考えることで、

$$ps \equiv 1 \pmod{q}$$

であることを後々使います。

さて、では $m^\prime = m^{ed}$ が $m^\prime \equiv m \pmod{n}$ となることを証明します。

まず、

$$\begin{align} m^\prime &\equiv m^{ed} \equiv kp^{ed} \equiv 0 \pmod{p} \\\ m^\prime &\equiv m^{ed} \equiv r^{ed} \pmod{q} \\\ &\equiv (r^{q-1})^{k(p-1)+1} \\\ &\equiv (r^{q-1})^{k(p-1)} \cdot r \\\ &\equiv r \pmod{q} \end{align}$$

なので³、$m^\prime$は連立合同式

$$m^\prime \equiv 0 \pmod{p} \\\ m^\prime \equiv r \pmod{q}$$

の解となっています。このような連立合同式は中国の剰余定理　で説明した通りの方法で解を求めることができます。解 $m^\prime$ は、

$$\begin{align} m^\prime &\equiv 0 \cdot \frac{pq}{p} y_p + r \cdot \frac{pq}{q} y_q \pmod{n \ (=pq)} \\\ &\equiv rpy_q \pmod{n} \end{align}$$

となります。ここで、$y_p, y_q$は、

$$\frac{pq}{p} y_p = qy_p \equiv 1 \pmod{p} \\\ \frac{pq}{q} y_q = py_q \equiv 1 \pmod{q}$$

を満たす整数とします。

$$ps \equiv 1 \pmod{q}$$

でしたから、

$$ps \equiv py_q \equiv 1 \pmod{q}$$

であり、上式の$py_q$を$ps$で置き換えると、

$$m^\prime \equiv rps \pmod{n}$$

ここに、

$$m = kp = jq + r \Rightarrow r = kp - jq$$

を代入して、

$$\begin{align} m^\prime &\equiv rps \equiv (kp - jq)ps \pmod{n} \\\ &\equiv kpps - js \cdot pq \\\ &\equiv kpps \pmod{n \ (=pq)} \end{align}$$

右辺に、

$$ps + qt = 1 \Rightarrow ps = 1 - qt$$

を代入して、

$$\begin{align} m^\prime &\equiv kp(1 - qt) \\\ &\equiv kp - kt\cdot pq \\\ &\equiv kp \pmod{n \ (=pq)} \\\ &\equiv m \pmod{n} \end{align}$$

以上より、$m$と$n \ (=pq)$が互いに素でない場合も、復号できることが確認できました。

¹. 数学的な言い回しになりますが、平文空間が暗号文空間より大きいと、単射になりません。単射でないということは、どうあがいても、１つの暗号文に複数の平文が対応することがありえて、一意に復号できません。よって、暗号として利用できる関数である以上は、平文空間の大きさは暗号文空間の大きさ以下でなくてはなりません。なお、1つの平文が複数の暗号文に対応する場合については一意に復号可能です。古典暗号では、ホモフォニック暗号がそのような暗号のひとつです。 ↩

². 「互いに素ではない」の言い換えになっていることに気づきましたか？ ↩

³. 後半はフェルマーの小定理を使っています。$q$が素数なので、$r^{q-1} \equiv 1 \pmod{q}$ ですね。 ↩