戻せないかけ算

通販のサイトで買い物をします。いま初めて開いた店です。店の人と会ったことはありませんし、番号を隠すための合言葉を前もって決めたこともありません。それでもカード番号は、途中の誰にも読まれずに店まで届きます。

昔からある暗号は、同じ鍵で閉めて、同じ鍵で開けます。これを共通鍵暗号（かける鍵と開ける鍵が同じ暗号）といいます。手紙を送る前に、同じ鍵を相手に渡しておかなければなりません。

その鍵を、どうやって渡すのでしょうか。鍵を安全に渡せるなら、最初から手紙もそのやり方で渡せばよいはずです。

もう一つ困ることがあります。相手ごとに別の鍵が要るので、みんなが互いに連絡しようとすると、鍵の数がふくらみます。

人数が10倍になると、鍵の数はおよそ100倍になります。ネット通販の店が客ひとりずつに別の鍵を配って管理するのは、現実的ではありません。

閉める道具と開ける道具を別々にする。それだけで、鍵を前もって渡す必要がなくなります。これが公開鍵暗号です。1977年に発表されたRSA暗号は、その代表です。

写真は、点ひとつひとつの明るさを表す数の並びです。その数を1つずつ暗号にかけると、絵は消えます。秘密鍵で戻すと、元の絵が現れます。

この3枚は、いまこの画面の中で計算しています。真ん中の絵は、途中の通信を盗み見た人に見えているものです。

本物の鍵は600桁を超えますが、仕組みは小さい数でも変わりません。素数を2つ選ぶところから、暗号にして、戻すところまでを並べます。

送る側は y = x^e mod n（xをe回かけて、nで割った余り）を計算するだけです。受け取る側は x = y^d mod n で元に戻します。使う数が違うだけで、やっていることは同じ形です。

講義ノート（データエンジニアリング演習 第10回）では、eをb、dをaと書いています。ここでは公開鍵の指数をe（encrypt）、秘密鍵の指数をd（decrypt）と書きます。

鍵づくりで自分が決めるのは、素数2つだけです。あとは決まった手順で出てきます。

pとqは違う素数にします。同じ素数を2回使うと、後で出てくる復号が成り立たなくなります。

y = x^e mod n

x = y^d mod n

eが大きくなると、xをe回かけるのは大変です。そこでくり返し二乗法（2乗しながら必要なところだけ掛ける方法）を使います。下の表が、その全部の手数です。

eを2進数で書いた桁の数だけで済みます。

文字は、まず番号（文字コード）に直してから暗号にかけます。

—

明るさは0から255までの数です。この数がn以上になると暗号にかけられません。素数を小さく選ぶと、ここで足りなくなります。なお暗号文の値は0からn−1までの範囲に広がるので、真ん中の絵には256で割った余りを明るさとして出しています。

公開されているのは n と e だけです。n は2つの素数のかけ算でできているので、n を素因数分解できれば p と q が分かります。p と q が分かれば φ(n) が出て、秘密鍵 d まで出ます。

いまの鍵は小さいので、一瞬で終わります。では、桁を増やすとどうなるでしょうか。

桁が2つ増えるたびに、かかる時間はおよそ10倍になります。足し算ではなく、かけ算で伸びます。

実測した速さから引き伸ばした見積もりです。

17と19をかけて323。これは数秒でできます。では逆に、323を渡されて「2つの素数のかけ算に戻して」と言われたらどうでしょう。3で割ってみて、5で割ってみて、7で割ってみて……と試すことになります。

桁が増えると、この差が開きます。かけ算にかかる手間は桁数に比例する程度ですが、総当たりの素因数分解は桁が増えるごとに約3倍に伸びます。STEP2の表で実際に見たとおりです。

行きは速く、帰りは遅い。この一方通行が、RSA暗号の安全性そのものです。

だから公開鍵 n を配っても平気です。n から p と q を取り出せれば秘密鍵は作れますが、その計算が終わらないのです。

鍵の長さは、nを2進数で書いたときの桁数で表します。2048ビットは10進で約617桁です。

分解する側も、STEP2のような総当たりはしません。数体ふるい法という、はるかに速い方法があります。それでも829桁ぶん（829ビット）を分解するのに、のべ2700年ぶんの計算機時間がかかりました。桁をその2.5倍にした2048ビットには、いまのところ手が届きません。

鍵を長くすると、暗号にする計算も重くなります。長ければ長いほど良い、ではなく、守りたい年数と処理の重さのつり合いで決めます。

HTTPSでは、通信の中身そのものは共通鍵暗号で暗号にしています。公開鍵暗号は重いからです。使うのは最初にその共通鍵を渡すところだけ。STEP1で立てた「鍵をどうやって渡すか」という問題を、ここで解いています。

署名は、鍵の使い方を入れ替えたものです。自分の秘密鍵でかけたものは、公開鍵で誰でも戻せます。中身は隠せませんが、戻せたという事実が、本人が作ったことの証明になります。

1994年にショアが、量子コンピュータなら素因数分解を桁違いに速く解ける手順を示しました。十分な大きさの量子コンピュータができれば、RSA暗号の一方通行は一方通行でなくなります。

ただし、いまある量子コンピュータは2048ビットの鍵を分解できる規模には遠く届いていません。現時点で実際の脅威になっているわけではありません。実験で分解できているのは、ごく小さい数にとどまります。

それでも、いま盗んで保存しておき、量子コンピュータができてから読む、という攻め方はありえます。そのため、量子コンピュータでも解きにくい計算に土台を置きかえた耐量子暗号の研究と標準化が進んでいます。2024年には最初の標準が定められ、置きかえが始まったところです。

どの暗号も「いまのところ解かれていない計算」に寄りかかっています。何を難しい問題だと考えるかが変われば、暗号も作り直します。

このシリーズで扱ってきたのは、すべて同じ材料です。0と1の並びを、どう置きかえるか。

← 前に触るとよいのは どこまで直せるか。あちらは壊れた0と1を誰でも元に戻せるようにする話で、こちらは鍵を持たない人には戻せないようにする話です。上の表にある「どこまで縮むか」と並べると、圧縮では偏りを味方にし、暗号では偏りを消す、という違いも見えます。暗号文を圧縮してもほとんど縮まないのは、そのためです。

「現実的な時間で終わらない」という論点をもう一度見るなら どの順で回るか へ。あちらは終わらないことに困る側、こちらは終わらないことに助けられる側です。