RSA暗号

RSA暗号は公開鍵暗号で最初に考えられた方式です。ここでは論文 R. L. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, CACM 21, No.2 (1978) に従って説明します。

公開鍵暗号は、メッセージ $M$ を暗号化する関数 $E(M)$ と、それを復号する（つまり元に戻す）関数 $D(E(M)) = M$ から成ります。$E()$ は公開しますが、$D()$ は秘密にしておきます。$E()$ から $D()$ を導くことは簡単にはできません。

RSA暗号では $D(E(M)) = M$ だけでなく $E(D(M)) = M$ も成り立ちます。暗号化されていないメッセージ $M$ を復号するというのは変な気がしますが、RSA暗号ではどんなメッセージも何らかのメッセージを暗号化したものですので、$E(D(M))$ という操作が可能です。この性質はデジタル署名に使います。

このような性質を持つ $E()$ と $D()$ の簡単な例を挙げます。

n = 2773
e = 17
d = 157  

def E(M):
    return pow(M, e, n)

def D(M):
    return pow(M, d, n)

ここで pow(M, e, n) は M の e 乗を n で割った余りを求めるPythonの組み込み関数です。メッセージ M は 0 以上 n 未満の整数とします。

本当にこれが $D(E(M)) = M$ や $E(D(M)) = M$ を満たすでしょうか。

E(1234)

1793

D(E(1234))

1234

E(D(1234))

1234

for i in range(n):
    if D(E(i)) != i:
        print(i)

どうやらどんな $M$ についても $D(E(M)) = E(D(M)) = M$ が成り立ちそうです。

要は $E(M) = M^e \bmod n$、$D(M) = M^d \bmod n$ なので $D(E(M)) = E(D(M))$ は自明ですが、$D(E(M)) = M$ になるためには $e$、$d$、$n$ をうまく選ばなければなりません。また、$E()$ すなわち $e$、$n$ が公開されても $d$ が簡単に導けないことが必要ですが、そのためには $n$ をもっと大きくする必要があります。

この後の話は、多少の数学の知識が必要です。

まず、二つの非常に大きい（1000ビット規模の）素数 $p$、$q$ を選び、$n = pq$ とします。上の簡単な例では $p=47$、$q=59$ で、$n = pq = 2773$ です。

$\phi(n) = (p-1)(q-1) = 46 \times 58 = 2668$ を計算します。$\phi(n)$ はオイラー（Euler）のトーシェント（totient）関数と呼ばれ、一般には $n$ と互いに素な 1 以上 $n$ 以下の自然数の個数と定義されますが、$p$、$q$ が素数の場合は $\phi(p) = p-1$、$\phi(pq) = (p-1)(q-1)$ が成り立ちます。

$\phi(n)$ と互いに素な数 $d$ を選びます。ここでは $d = 157$ としました。

$de \bmod \phi(n) = 1$ となるような $e$ を選びます。ここでは $e = 17$ としました。$de = 157 \times 17 = 2669$ ですから確かに $de \bmod 2668 = 1$ になっています。

これで $D(E(M)) = (M^e)^d = M^{de} = M^{1 + k\phi(n)}$ ですが、オイラーの定理 $M^{\phi(n)} \bmod n = 1$ を使えば $D(E(M)) = M$ が示されます。