RSA暗号の計算方法&実際に計算してみる

投稿日：2022/02/27 更新日:2022/02/27

どうやって暗号化するのか？

計算式自体はとてもシンプルです。平文を $E$ 乗して $N$ で割った余りを求めるだけです。
$E$ はEncryption（暗号化）の頭文字です。

暗号文=\left(平文\right)^E\mod N

こちらも計算式はシンプルです。暗号文を $D$ 乗して $N$ で割った余りを求めるだけです。
$D$ はDecryption（復号化）の頭文字です。

平文 = \left(暗号文\right)^{D} \mod N

用語	解説
平文	暗号化する前の文。
暗号文	暗号化された文章。
x mod y	xをyで割った余り。プログラミングではx%yと書かれる。
E, D, N	整数

鍵の作成手順は次の通りです。

まず2つの素数 $p, q$ を用意します。そして、その2つを掛けたものが $N$ です。

N = p \times q

何とシンプル。。。

$L$ は $p-1$ と $q-1$ の最小公倍数（ $lcm$ ）です。
$p-1$ と $q-1$ の最小公倍数を $lcm(p-1, q-1)$ と書きます。

L = lcm(p-1, q-1)

$E$ は以下の条件式を満たすものです。

1 < E < L\\ gcd(E, L) = 1

$1 < E < L$ の中で $E$ と $L$ が最大公約数 $(gcd)$ が「1」、つまり互い素であるものです。
$E$ と $L$ の最大公約数を $gcd(E, L)$ と書きます。

$D$ は以下の条件式を満たすものです。

1 < D < L\\ (E\times D) \mod L = 1

$D$ は $1 < D < L$ の中で $E\times D$ の割ったあまりが「1」であるものです。

このようにして得られた $E$ と $N$ のペアが公開鍵、 $D$ と $N$ のペアが秘密鍵です！

$p=5$ , $q=11$ としてみます。どちらも素数です。

N=5\times 11=55

となり、 $N=55$ となりました！

$5-1$ と $11-1$ の最小公倍数を求めます

\begin{aligned} L &= lcm(5-1, 11-1) \\ &= lcm(4, 10)\\ &= 20 \end{aligned}

となり、 $L=20$ となりました！

$1 < E < 20$ の中で $gcd(E, 20) = 1$ となる数を探します。
$E = 3, 7, 11, ...$ と複数の候補があります。どれを選んでも良いです！
今回は $E=3$ とします！

$1 < D < 20$ の中で $(3\times D)\mod 20 = 1$ となる数を探します。
$D=7$ の時に条件を満たします！

得られた $(N,E) = (55, 3)$ が公開鍵、そして $(N,D) = (55, 7)$ が秘密鍵です！

暗号化できる平文には $N$ 未満の正の整数という条件があります。
今回は「4」を暗号化してみましょう！

先ほど求めたように $N=55, E=3$ です

\begin{aligned} 暗号文&=4^{3}\mod 55\\ &=64 \mod 55\\ &=9 \end{aligned}

となり、暗号文は「9」です！

先ほど求めたように $N=55, D=7$ です。暗号文「9」を復号化してみましょう！

\begin{aligned} 平文&=9^{7} \mod 55\\ &= 4782969 \mod 55\\ &= 4 \end{aligned}

となり、先ほど暗号化した「4」が得られてます！！

今回は世の中で多く使われているRSA暗号についてその計算方法を解説しました。日常生活での通信にこのような数学が生きていることが分かっていただけたら嬉しいです！

結城浩（2015）暗号技術入門　第3版