RSA暗号は、1977年に発表されて以来、インターネットの安全を支え続けてきた公開鍵暗号の代表格です。Webサイトの通信、電子署名、ソフトウェアの正当性確認——意識することはなくても、私たちは毎日RSAのお世話になっています。
このRSAの安全性は、たったひとつの事実に支えられています。「大きな数の掛け算は一瞬でできるが、その逆——素因数分解——は途方もなく時間がかかる」。この記事では、なぜ計算の難しさが暗号の強さになるのかを、数式を使わずに解説します。ここが腹落ちすると、量子コンピュータがなぜ暗号の脅威になるのかも自然に理解できます。
一方通行の計算——RSAの心臓部
簡単な実験をしてみましょう。「61 × 53 は？」——電卓なしでも少し頑張れば 3233 と出せます。では逆に、「3233 は、どの2つの素数の掛け算？」——こちらは総当たりで試していくしかなく、急に苦しくなります。
数字が大きくなるほど、この差は絶望的に開きます。数百桁の素数2つを掛け算するのはコンピュータなら一瞬ですが、その積を素因数分解して元の2つの素数を割り出すのは、現在の最速のコンピュータと最良の解き方をもってしても、宇宙の年齢を超える時間がかかると見積もられる規模になります。
このような「行きは簡単、帰りは事実上不可能」な計算を一方向性関数と呼びます。RSAはこの非対称性を利用して、「誰でも暗号化できる（掛け算側）が、秘密の素数を知っている本人しか復号できない（素因数分解側）」という仕組みを作りました。よく聞く「鍵長2048ビット」とは、この積となる数の大きさのことで、桁数でいえば600桁を超える数を使っている、という意味です。
公開鍵と秘密鍵——南京錠のたとえ
RSAは公開鍵暗号という方式の代表です。鍵がペアになっているのが特徴で、南京錠にたとえるとよく分かります。
- 公開鍵＝開いた南京錠。誰にでも配ってよい。相手はメッセージを箱に入れ、この南京錠をパチンと閉めて送る（＝暗号化。閉めるのは誰でもできる）
- 秘密鍵＝南京錠を開ける鍵。自分だけが持つ。閉まった箱を開けられるのは自分だけ（＝復号）
「南京錠を閉める」が素数の掛け算に、「鍵なしでこじ開ける」が素因数分解に対応します。こじ開けが事実上不可能だから、南京錠（公開鍵）は世界中に配って構わない——これがRSAの発明的なところです。
さらにこのペアは逆向きにも使えます。秘密鍵で「封をする」と、対応する公開鍵を持つ誰もが「この封は本人にしか作れない」と確認できる。これが電子署名で、契約書の電子化やソフトウェア更新の正当性確認を支えています。
どこで使われているか、そしてなぜ今が転換点か
RSAが実際に働いている場所を挙げると、その影響範囲の広さが分かります。
- Webサイトの通信（TLS）——ブラウザの鍵マークの裏側で、通信相手の確認や暗号鍵の受け渡しに使われてきました
- 電子署名・電子証明書——契約、請求、行政手続きの電子化の土台
- ソフトウェア署名——OSやアプリの更新が「本物の開発元によるもの」であることの保証
- VPN・メール暗号化・ICカードなど
問題は、RSAの安全性の根拠である「素因数分解は事実上不可能」が、量子コンピュータという新しい計算機の登場で崩れる見込みであることです。1994年に発表されたShorのアルゴリズムは、十分な規模の量子コンピュータがあれば素因数分解を現実的な時間で解けることを示しました。まだその規模の量子コンピュータは存在しませんが、各国は耐量子暗号（PQC）への移行をすでに始めています。40年働いた暗号の世代交代が、いま静かに進んでいるのです。
