１．はじめに
当方新卒エンジニア、もう入社して３ヶ月半が経ちすっかり夏になってしまいました（ 研修をまだ終えていないのは別の話）。
何もすることがない週末Netflixで物色していると、ありました今見たい作品 「サマーウォーズ」。言わずと知れた名作夏映画ですね。
その中で主人公の小磯健二くんが手計算で 2056桁のRSA暗号を一晩で解いてしまった、という描写があります。
よく「現実的に不可能」といわれるのを聞くこの描写ですが、自分自身あまりRSA暗号のことは知らなかったので調べた内容をお裾分けしようと思います。
この記事は「サマーウォーズ」をきっかけに初学者がRSA暗号の仕組みと素因数分解のアルゴリズムについての入り口としてざっくり考えてみることを目的にしています。
そのため大学レベルの厳密な数学的な議論やRSAの暗号化・復号を行うコードを実装してみる、みたいな内容にはなっていないのであしからず。
２．RSA暗号の仕組み
受信者側がすること
RSA暗号は公開鍵暗号と言われる暗号方式に属します。有名なので詳しい説明は省略しますが、情報の送信者に使ってもらう公開鍵と、送信者が暗号化した内容を受信者が複合するための秘密鍵を用意する必要があります。
公開鍵暗号について詳しく知りたい方むけの記事↓
この先で暗号を使って通信をするにあたって受信者が行うことを説明します。
「なんでそんな値を求めるんだよ」となるかもしれないですが、最後でちゃんとなぜうまくいくのか説明するので、一旦「そういうものなんだな」と思って読んでもらえると嬉しいです。
2つの大きな素数を選び積を求める
まず、巨大な素数の組(p,q)（現在主流になっているRSA-2048だとそれぞれ約300桁）を選び、それらの積Nを求めます。
例） $p=61, q=53, N=61×53=3233$
Nは公開鍵の一部になります。p,qは秘密鍵の一部になるので公開してはいけません。
オイラー関数を計算する
先の手順で求めたNに対してオイラー関数$\phi(N)$（1からNまでの整数のうちNと互いに素であるものの個数）を計算します。
\begin{align}
\phi(N)&=N-\frac{N}{p}-\frac{N}{q}+\frac{N}{pq}\\
&=pq-q-p+1\\
&=(p-1)(q-1)
\end{align}
例） $\phi(3233)=60×52=3120$
ここから秘密鍵を求めるのでこの$\phi(N)$は公開してはいけません。
公開指数を選ぶ
次に $1<e<\phi(N)$ で $gcd(e,\phi(N))=1$ になる数eを選びます。
つまりeと$\phi(N)$が互いに素になるようにするということです。
よく使われるのは65537です。２進数のビット列にした時先頭と末尾以外の桁が０になってくれるため計算が軽くなります。
このeは暗号化の際に使用するので公開します。
秘密指数を選ぶ
最後に $d×e\equiv1 \ (mod \ \phi(N))$ となるようにdを決めます。
このdは復号時に使用する秘密鍵のため公開してはいけません。
公開鍵と秘密鍵の完成
ここまでで鍵が完成しました。
公開鍵 $(N,e)$
秘密鍵 $d$ （実際にはp,qなども保存します）
暗号化と復号
ここからは暗号化と復号をどのように行うかを説明します。
暗号化
送りたいメッセージを数字Mに変換します。
なお、変換の方法は文字をUTF-8などの文字コードに置き換え、16進数の並びを連結したものを10進数の数字に戻します。
例）文字列"ABC"のMを求める
A,B,Cを文字コードで表すとそれぞれ41,42,43となります。
これを連結すると414243となります。
これを10進数に戻します。$414243_{16}=427683_{10}$となるので文字列"ABC"のMは4276803となります。
次にこの計算したMに対して暗号文$C=M^{e} \ (mod \ N)$ を計算します。
これで暗号化は完了です。
復号
送信者から送られてきたCに対して、$C^{d} \ (mod \ N)$ を計算するとこれが暗号化する前のMに一致します。
なぜこれで復号できるのか
前提としてオイラーの定理：$M^{\phi(N)}\equiv1 \ (mod \ N)$が成り立ちます。
暗号化から復号までにやっているのは結局$C^{d}=M^{de}$.
そして$de\equiv1 \ (mod \ \phi(N))$より$de=k\phi(N)+1 \ (k \in \mathbb{Z})$と書けるので
\begin{align}
M^{de}&=M^{k\phi(N)+1}\\
&=M^{k\phi(N)}・M\\
&\equiv1・M \ (mod \ N)\\
&\equiv M \ (mod \ N)
\end{align}
で復号操作を経て暗号化前のMに戻ってくることができました！
では攻撃者はなにをするか
まず公開されている情報を思い出しましょう。公開されているのは公開鍵の$(N,e)$のみです。しかし、仮に暗号化されたCを入手することができてもそれを復号するには秘密鍵のdが必要です。そしてdを求めるためにはeと$\phi(N)$が必要で、$\phi(N)$を求めるためにはp,qが必要なので、結局攻撃者は公開鍵のNを素因数分解してp,qを特定する必要があります。
３．RSA暗号はなぜ安全なのか
ここまでで公開されている巨大な素数２つの積Mを素因数分解できればRSA暗号を破ることができるということがわかりました。ではなぜRSA暗号が安全と言われているのか。それには受信者が行う「素数かどうか」を判定することと２数の積を求めるのは比較的簡単なのに対し、攻撃者が行う「素因数分解をする」ことが現状とても難しいという構造が関係しています。
ここからは素数判定と素因数分解のアルゴリズムを見ながらそれぞれの難易度の違いを確認していきたいと思います。
ここから先はややアルゴリズムの中身について数式を用いた説明に内容が偏ります
素数判定
素数判定には様々な方法がありますが、RSA暗号のp,qを用意する際に一般的に使われているのがMiller-Rabin素数判定法です。
詳しい説明は省くので参考記事を置いておきます。
このMiller-Rabin素数判定法は確率論的素数判定法です。
ざっくりいうと素数かどうか判定したい数に使用するパラメータを変えながら複数回の操作（操作の中身は上の記事を見ていただければと思います）を加えて、その結果が「その数が素数であるための必要条件」を満たすかを確かめ、必要条件を満たさないものをどんどん篩にかけていって精度を高めるイメージです。
素数判定には決定論的に多項式時間で収まるAKS素数判定法もありますが、上記のMiller-Rabin法に比べて大幅に遅いこと、Miller-Rabin法を繰り返し行うことで精度が指数関数的に向上し実用上問題ないことからそちらを使うことがほとんどのようです。
素因数分解
素因数分解には様々な方法があります。一番身近なものだとNを素因数分解する際に１以上$\sqrt N$以下の素数で割れるかを順番に確かめる試し割り法がなどがありますが、これではRSA暗号に使われるような巨大な素数の積には到底太刀打ちできません。（AIに聞いてみると世界最速級のスパコンでもRSA-2048を試し割り法で解くには宇宙の年齢の$10^{272}$倍かかるらしいです苦笑）
平方合同を探す
試し割り法では手当たり次第に割れるかどうかを確認しますが効率がよくありません。
ここでは見方を変えて、Nを割れる可能性が高いものを狙い撃ちできる方法がないか考えてみましょう。
そこで和と差の積の因数分解：$x^2-y^2=(x+y)(x-y)$に着目します。
もし平方したものをNで割った余りが等しい（平方合同な）数の組が見つかったらどうでしょうか。
このときNを法として次が成り立ちます。
\begin{align}
x^2 &\equiv y^2\\
(x+y)(x-y) &\equiv 0
\end{align}
ここからわかるのは、p,qのようなNの素因数が$(x+y)$と$(x-y)$の中に含まれているということです。もしp,qが別々の項に含まれるような非自明なケースを引き当てることができれば、最大公約数によって因数を取り出せます。
例）$N=15 \ $のとき
簡単な例ですが15を上の方法で素因数分解することを考えましょう。
まずは15で割った余りが等しい平方数の組を探します。簡単なものだと$x=4,\ y=1$がこれに該当します。
ここで$x-y=3$と$N=15$の最大公約数を考えます。この２数の最大公約数はユークリッドの互除法を用いることによってNの素因数分解を直接考えることなく３と求めることができます。
したがって15は3を因数に持つことがわかり、そこから芋づる式に5を因数に持つことも分かります。
上の例から分かるのはうまく条件を満たす数のペアが見つかれば素因数分解を行う操作を最大公約数を求める簡単な操作に帰着させることができるということです。
しかし、上で扱った例はあまりに出来すぎています。
実際には、
- そもそもどうやって平方合同を探すのか
- 見つかった平方合同が素因数分解につながる非自明な結果を導くとは限らない
という問題があるので、効率よく平方合同を作る方法を考えます。
$x^2-N$に着目する（二次ふるい法）
上の方法において平方合同を探すのが大変なのは変数がxとyの２種類あり、それを同時に動かして条件を満たすか確かめなければならないからです。
そこで、yを直接探すのではなく、x^2-Nという値に注目します。なぜなら、
$x^2 - N \equiv x^2 \ (mod \ N)$
だからです。もし$x^2-N$が平方になれば、その平方根をyとして平方合同を作ることができます。
複数の数を掛け合わせて平方数を作る
ただしここでまた壁にぶつかります。その壁とは$x^2-N$が偶然平方数になることはほぼないということです。
そこで発想を変えて、いくつかのxに対して$x^2-N$を計算し、それらを掛け合わせて平方数を作ることを考えてみます。そのためには、どの値同士を掛ければ平方になるのかを効率よく探す必要があります。
平方数になる条件と指数ベクトル
整数を素因数分解すると$2^a \times 3^b \times 5^c \times \dotsb$のように表せます。
この数が平方数になるための必要十分条件はすべての指数が偶数であることです。
つまり重要なのは素因数そのものではなく、各素因数の指数の偶奇だということになります。
そこで、$x^2-N$を指数の偶奇を表すベクトルに変換します。
例えば105を表現したい時、
$105 = 2^0 \times 3^1 \times 5^1 \times 7^1 \ \longrightarrow \ (0,1,1,1)$
のように表現します。
また、5145を表現したい時、
$5145 = 2^0 \times 3^1 \times 5^1 \times 7^3 \ \longrightarrow \ (0,1,1,3)$
ですが偶奇だけ見られれば十分なので(0,1,1,1)として扱えます。
ただし、この方法にも問題があります。それは素因数の種類が増えるほどベクトルの次元が大きくなってしまうということです。
例えば、$2 \times 5 \times 13 \times 19 \times \dotsb $のような素因数を多く含む値ばかりを集めると管理するベクトルの次元がどんどん大きくなり、計算が重くなってしまいます。
そこで、小さい素数だけで構成される値を優先的に集めます。このような値をスムーズ数と呼びます。
スムーズ数とはすべての素因数が指定された値以下の整数のことです。例えば、ある数の素因数がすべて７以下であれば、その数は「7-スムーズ数」と呼ばれます。
では実際にスムーズ数を集めて、そこから素因数分解を行ってみます。
ex）$N=5671(53×107)$ の素因数分解
まずは様々なxで$x^2-N$を計算し、スムーズ数になるものを集めます。
i) $x=76$のとき
$x^2 - N = 76^2 - 5671 = 105 = 2^0 \times 3^1 \times 5^1 \times 7^1 \longrightarrow (0,1,1,1)$
ii) $x=104$のとき
$x^2 - N = 104^2 - 5671 = 5145 = 2^0 \times 3^1 \times 5^1 \times 7^3 \longrightarrow (0,1,1,1)$
ここで２数をかけて平方数になるかを確かめます。整数同士を掛けることはその整数の指数ベクトルを足すことに対応します。上の2つの指数ベクトルを足すと、
$(0,1,1,1) + (0,1,1,1) \equiv (0,0,0,0) \ (mod \ 2)$
となります。ここからすべての素因数に関して指数が偶数になっていることがわかるので、105×5145は平方数だということがわかります。
実際計算してみると
\begin{align}
105 &= 3 \times 5 \times 7 \\
5145 &= 3 \times 5 \times 7^3 \\
105 \times 5145 &= 3^2 \times 5^2 \times 7^4 \\
&= (3 \times 5 \times 7^2) ^2 \\
&= 735^2
\end{align}
ここで5671を法とすると
\begin{align}
76^2 &\equiv 76^2 - 5671 = 105\\
104^2 &\equiv 104^2 - 5671 = 5145\\
\end{align}
両辺掛け合わせて
\begin{align}
(76 \times 104) ^2 &\equiv 105 \times 5145 \\
7904 ^2 &\equiv 735^2
\end{align}
より$(x,y)=(7904,735)$で平方合同を見つけることができました。
ここからは先に述べた通り$M=5671$ と$x - y = 7169$の最大公約数を求めていき、
$gcd(5671,7169) = 107$
なので5671が107を素因数に持つことがわかり、そこから芋づる式に5671=53×107と求めることができます。
実際に用いられている方法は？
ここまで紹介した平方合同から素因数分解を考える方法は二次ふるい法と呼ばれています。
この方法は単純な試し割り法に比べると比較にならないほど高速ですが、巨大な整数を対象にすると新たな問題が出てきます。
それは対象の整数を大きくすればするほど$x^2-N$の中に巨大な素因数が紛れ込みやすくなることで、スムーズ数になる確率が小さくなるので、ベクトルの線形性を確かめるための計算量が増えてしまうことです。
そこで登場するのが数体ふるい法です。数体ふるい法の基本的な考え方は二次ふるい法と変わりませんが、考える範囲を整数の範囲から拡張することでより多くのスムーズ数の候補をより効率的に探索できるようになっているようです。
この数体ふるい法は2020年に約829bit（10進数表記で250桁）のRSA-250の素因数分解に成功していますが、それでも現在主流になっているRSA-2048はその10^20~10^30倍の計算量が求められるらしいので、現在のアルゴリズムが根本から見直されるような効率的な物が見つからない限りはRSA暗号の安全性は揺るがないとのこと。
しかもRSA暗号の強いところは効率的なアルゴリズムが見つかったとしても桁数を増やせば難易度が指数関数的に向上するところ。P≠NP予想が反証されない限りは大丈夫でしょう。
結論
ここまでアルゴリズムに話が偏ったので忘れかけていましたが、本記事のきっかけは「サマーウォーズ」の小磯健二くんがどれくらい超人的かを理解したいというところでした。
作中で登場した2056桁のRSA暗号はbit長に直すと約6830bit。単純に考えると現在主流のRSA-2048の３倍以上のbit長で難易度も10^35~10^40倍。それを2009年に一晩で解いてしまう健二くん、やはり人外である。