8/21 サマーウォーズを見てRSA暗号について調べた

普段テレビはほとんど見ないのだけれど, 先日は金曜ロードショーのサマーウォーズを見てました.
相変わらずいつ見てもいい作品だなぁとか夏希先輩かわいいなぁとか思いつつ, Twitterでわいわいしてました.

サマーウォーズが放送されると必ず話題に上がるのが健二が解いているあの暗号の話.
解いている様子の描写からRSA暗号じゃないかと言われています.
RSA暗号というと素因数分解というイメージが強いのですが, あまり暗号化と複合の部分がどういう原理でできているのかについては理解できてませんでした.
というわけで, サマーウォーズを見ながらいろいろと調べて考えてみたことをまとめてみたいと思います.

公開鍵暗号方式

そもそも, RSA暗号は公開鍵暗号方式の一種で, 2つの鍵を用いて暗号化と復号を行います.
簡単に言うと, 以下の2つの性質を持つような暗号です.

1. 片方の鍵で暗号化したら, もう片方の鍵でしか復号できない.
2. 片方の鍵からはもう片方の鍵は(簡単には)推測できない.

RSA暗号の基本的な仕組み

RSA暗号の基本的な仕組みについてはWikipediaなどを参照してもらうと良いと思うのですが, 簡単に書いておきます.
RSA暗号 - Wikipedia

$p$ , $q$ : 任意の素数, $n = pq$
$e$ : $(p - 1)(q - 1)$ と互いに素な任意の正の整数(公開鍵)
$d$ : $ed = 1 \pmod{(p - 1)(q - 1)}$ を満たす正の整数(秘密鍵)
$m$ : 平文, $C$ : 暗号文
暗号化: $C = m^e \pmod{n}$
復号: $m = C^d \pmod{n}$

というわけで, 実は累乗が計算できれば暗号化と復号は簡単にできます...
ってほんまか？となるわけですね.
これってつまり, $m^{ed} = m \pmod{n}$ が成り立つってことに他ならないわけです.
さすがに自明ではないよなぁ......と.

復号がうまくいくのはフェルマーの小定理で説明できる

『高校数学の美しい物語』の説明がわかりやすかったです.

mathtrain.jp

少し補足をすると, 合同式には以下の性質があります.

$a = b \pmod{p}$ かつ $a = b \pmod{q}$ ならば $a = b \pmod{lcm(p, q)}$
( $lcm(p, q)$ は $p$ と $q$ の最小公倍数を表す.)

つまり, $m^{ed} = m \pmod{n}$ を示すためには, $m^{ed} = m \pmod{p}$ を示せば十分ということになります.

興味深いのは, フェルマーの小定理を用いているところです.
これを利用してうまく暗号化ができるようになっているわけですね, 賢い.

素因数分解の困難性が安全を保証している

公開鍵暗号方式なので, 公開鍵 $(e, n)$ から秘密鍵 $(d, n)$ が推測されると暗号を突破されてしまいます.
秘密鍵を推測するためには $ed = 1 \pmod{(p - 1)(q - 1)}$ を満たす $d$ を計算する必要があります.
つまり, $n$ を素因数分解して $p$ , $q$ を求め, $(p - 1)(q - 1)$ を計算する必要があるわけです.

素因数分解は $p$ , $q$ が十分に大きな素数であれば現実的な時間で解くことはできません.
逆に言えば, 素因数分解ができてしまえば暗号を解読することができます.

「RSA暗号 = 素因数分解」というイメージ

サマーウォーズを見ながら, 流れてくるRSA暗号についてのツイートを眺めていたのですが, 「素因数分解する暗号」という説明が結構多かった気がします.
まぁ確かに「ふたつの素数 $(p, q)$ から積 $n$ を求めるのは簡単だけれど, $n$ から $(p, q)$ を計算するのは困難」と言われると, なんとなくわかったような気がしてしまうんですよね.
「素因数分解が効率よくできない」って直感的なのでそういう説明が出てくるのはわかるのですが, それって誤解の原因になりやすいんじゃないかなぁと.