私たちが毎日使うネットバンキングやログイン、メッセージアプリは、すべて暗号化されています。その暗号の中心にあるのは、とても単純な数学の事実です。2つの素数をかけるのはかんたんですが、その積をもとの2つの素数に素因数分解するのはとても難しいのです。

15 = 3×5 を確かめるのは一瞬です。逆向きに「15を素因数分解すると?」と考えるのも、まだかんたんです。困るのは数が大きくなってからです。2つの素数をかけて600桁を超える数をつくるのは、コンピュータなら一瞬です。ところが、その巨大な数からさかのぼってもとの2つの素数を見つけるのは、スーパーコンピュータでも事実上不可能です。RSA暗号は、この「かけるのはかんたん、分解するのは難しい」という非対称性をそのままカギとして使っています。

5 × 11 かんたん = 55 (600桁の数なら)とても難しい n → p, q を探す
かけるのはかんたんでも、大きな数をもとの因数に分解するのはとても難しい

このアイデアは小さな数で試せます。素数 p=5 と q=11 を選ぶと、n=p×q=55 です。メッセージを1つの数(m)だと考えると、公開鍵(e)で暗号化し、自分だけが知っている秘密鍵(d)でもとの数に復号できます。暗号化に使う n と e は誰でも見られますが、そこからもとのメッセージを取り出すには、n を素因数分解して p と q を見つける必要があります。この例(n=55)なら 5×11 とすぐに解けますが、本物のRSAでは600桁を超える n を使います。今あるすべてのコンピュータが力を合わせても、分解には宇宙の年齢より長い時間がかかると見積もられています。

RSAは1977年に、リベスト、シャミア、エーデルマンの3人がつくりました(RSAは3人の名前の頭文字です)。「素因数分解が難しいことは数学的に証明されていないが、実際には速い方法が誰にも見つかっていない」という事実が、今まさに私たちのネットの安全を守っているのです。

ほかの種類の暗号もあります。楕円曲線暗号(ECC)は、素因数分解のかわりに、楕円曲線上の離散対数問題という別の難しい数学の問題を使います。RSAより短い鍵で同じくらいの安全性が得られるので、スマートフォンや暗号資産のウォレットで広く使われています。さらに、新しい脅威も近づいています。量子コンピュータです。ショアのアルゴリズムという量子アルゴリズムは、理論上、素因数分解をはるかに速く解けることが知られています。そのため、大規模で安定した量子コンピュータが登場すれば、RSAもECCも危うくなるかもしれません。そこで、量子コンピュータでも難しいままの新しい数学の問題にもとづく「耐量子計算機暗号(ポスト量子暗号)」の研究がさかんに進められており、アメリカ国立標準技術研究所(NIST)は2024年に最初の公式な耐量子暗号の標準を発表しました。アクティビティのページでは、小さな数で素因数分解の難しさを体験し、自分でRSAの鍵をつくって、暗号化と復号の流れを一歩ずつたどることができます。