RSA 暗号系の原理

$p$, $q$ を相異なる素数とし,

$$n = pq, \quad n' = (p-1)(q-1)$$

とおく. $e$ を

$${\rm gcd}(e,n') = 1$$

となる適当な数とする.

$$d e = 1 \ {\rm mod}\,n'$$

となる数 $d$ をとる. このような $d$ が存在してかつ 互除法アルゴリズムで構成できることは, 問題 17.1 で考察した.

定理 16.3   $m$ を $n$ 未満の数とする. このとき $c = m^e \ {\rm mod}\,n$ とすると,

$$c^d = m \ {\rm mod}\,n$$

が成り立つ.

証明: 定理 17.2 を $x = m^{q-1} \ {\rm mod}\,p$ に対して適用すると,

$$(m^{q-1})^{p-1} = m^{n'} = 1 \ {\rm mod}\,p$$

である. 同様の考察を素数 $q$ と $m^{p-1}$ に対しておこなうと,

$$(m^{p-1})^{q-1} = m^{n'} = 1 \ {\rm mod}\,q$$

がわかる. $m^{n'}-1$ は $p$ でも $q$ でも割り切れかつ $p$ と $q$ は相異なる素数であるので $m^{n'}-1$ は $pq=n$ で割り切れる. よって, $m^{n'} = 1 \ {\rm mod}\,n$ が成り立つ.

さて, 証明すべき式は, $(m^e)^d = m \ {\rm mod}\,n$ であるが, 仮定よりある整数 $f$ が存在して $ed = 1 + f n'$ が成り立つことおよび $m^{n'} = 1 \ {\rm mod}\,n$ を用いると, $(m^e)^d = m^{ ed } = m^{1+ f n'} = m (m^{n'})^f$ を $n$ で割った余りが $m$であることがわかる. 証明おわり.

上のような条件をみたす数の組の例としては, たとえば

$$p = 47, q = 79, n = 3713, n' = 3588, e = 37 , d = 97$$

がある. 最後の数, $d$ は inv(37,3588); で計算すればよい. したがって, 二つの素数 $p$, $q$ を用意すれば, 簡単に上のような条件を みたす数の組を作れる.

RSA 暗号系では, $p,q,d$ を秘密にし, $e, n$ を公開する. $(e,n)$ を公開鍵, $d$ を秘密鍵と呼ぶ. $m$ ($m$ は $n$ 未満の数) の暗号化は,

$$m^e \ {\rm mod}\,n$$

でおこなう. この暗号化されたメッセージの復号化(もとのメッセージにもどすこと)は, 秘密鍵 $d$ を利用して,

$$m^d \ {\rm mod}\,n$$

でおこなう. この計算で正しくメッセージ $m$ が復号できることは, 定理 17.3 で証明した.

さて, これのどこが暗号なんだろうと思った人もいるかもしれない. $e, n$ が公開されているのなら, $n$ を素因数分解して, $p$, $q$ を求め, ${\tt inv}(e,(p-1)*(q-1))$ をもとめれば, 秘密鍵 $d$ がわかってしまうではないか! ここで, 素因数分解は最大公約数 (GCD) の計算に比べて, コストのかかる計算だということを思い出してほしい. $p$, $q$ を十分大きい素数にとると, $pq$ の素因数分解分解の計算は非常に困難になる. したがって $p$, $q$ の秘密が保たれるのである.

参考: 量子計算機はこの素因数分解を高速にやってしまうということを Shor が示した. これが現在量子計算機がさかんに研究されている, ひとつの きっかけである.