毎日使うネットバンキングやログイン、メッセージはすべて暗号化されています。その暗号の中心にあるのは、とても単純な数学の事実です。2つの素数をかけるのはかんたんですが、その積をもとの2つの素数に分けるのはとても難しいのです。ここでは小さな数でそのアイデアをたどってみましょう。(一部は高校レベルの内容です。)
15 = 3×5 を確かめるのは一瞬ですし、逆に「15の素因数は何?」と聞かれてもすぐ答えられます。困るのは数が大きくなってからです。コンピュータは2つの素数をかけて600桁を超える数を一瞬でつくれますが、その数からもとの2つの素数にさかのぼるのは、スーパーコンピュータでも手に負えません。RSAは、この「かけるのはかんたん、分解するのは難しい」という非対称性をそのままカギとして使っています。
数を1つ選び、わり切れる数が見つかるまで約数の候補を入力しましょう。何回目で見つかったかを数えると、数が大きくなるにつれてどれほど大変になるかがわかります。
本物のRSAでは数百桁の素数を使いますが、しくみを見るために、ここでは p=5 と q=11 という小さな2つの素数で鍵をつくります。
メッセージを1つの数 m だと考えます。公開鍵(e)で暗号化し、自分だけが持つ秘密鍵(d)で、もとのメッセージに復号します。
公開鍵(n と e)は誰でも見られます。しかし、そこからもとのメッセージを取り出すには、n を素因数分解して p と q を見つける必要があります。この例(n=55)なら 5×11 と3秒で分解できてしまいますが、本物のRSAでは n は600桁を超えます。
その大きさの数を素因数分解するには、世界中のコンピュータを総動員しても宇宙の年齢より長い時間がかかると見積もられています。だから n を公開しても安全なのです。私たちのネットの安全は、「素因数分解は難しい」という事実の上に成り立っています。数学的に証明されたわけではありませんが、速い方法はまだ誰にも見つかっていません。
楕円曲線暗号(ECC)は、素因数分解のかわりに、楕円曲線上の離散対数問題という別の難しい問題を使います。しくみはちがっても、ねらいは同じです。一方向にはかんたんで、逆向きにはとても難しい問題を見つけることです。ECCはRSAよりずっと短い鍵で同じくらいの安全性が得られるので、バッテリーや処理能力の限られたスマートフォンやIoT機器、ビットコインのような暗号資産のウォレットでよく使われています。
新しい脅威、量子コンピュータもあります。ショアのアルゴリズムという量子アルゴリズムは、少なくとも理論上は、素因数分解も離散対数もはるかに速く解けることが知られています。今の量子コンピュータではまだ本物のRSAは破れませんが、大規模で安定した量子コンピュータができれば、RSAもECCも危うくなります。
そこで、量子コンピュータでも難しいままの問題(たとえば格子問題)にもとづく「耐量子計算機暗号(ポスト量子暗号)」の研究がさかんに進められています。アメリカ国立標準技術研究所(NIST)は2024年に最初の公式な耐量子暗号の標準を発表しました。これらは今のRSAやECCを少しずつ置きかえたり、並行して使われたりしていくと見込まれています。