足し算だけの世界の物語～第二話「デジタル署名（による認証）」

足し算だけの世界と前回のあらすじ

ここは足し算だけの世界。この世界には、「計算」は足し算しかありません。掛け算も引き算も、ましてやテトレーションもペンテーションもありませんが、それでも人々は平和に暮らしていました。

その平和に一つの影が忍び寄ります。悪の秘密結社が郵政公社を乗っ取り暗黒郵政公社と化してしまったのです。暗黒郵政公社は郵便物の盗み見による脅迫事業を開始し、人々は平和を脅かされることになったのです。

ボブとの文通を楽しんでいたアリスもそんな暗黒郵政公社の悪行に脅かされていた一人です。しかしアリスは秘奥義「DH 鍵共有」を編み出し、暗黒郵政公社に郵便物を盗み見られずに済むようになりました。

ですが、これはアリスと暗黒郵政公社の熾烈な戦いの幕開けに過ぎなかったのです…

暗黒郵政公社の新事業「改竄・なりすまし事業」

暗黒郵政公社はさらなる新事業計画「改竄・なりすまし事業」を発表しました。これはその名の通り、郵便物の改竄およびなりすまし郵便の発送により詐欺等を行うというものでした。

たとえば通販の振込先を自分の口座に改竄したり…

息子になりすました手紙を送り、金銭を騙し取ろうというのです。

この発表は、今まで数々の戦場で地獄を見てきたアリスでさえも戦慄させました。アリス秘奥義「DH 鍵共有」によって郵便物の盗み見を防ぐことに成功したアリスとボブでしたが、それは暗黒郵政公社がその悪行を「盗み見」だけにとどめていた場合の話です。

たとえば暗黒郵政公社がボブになりすまして鍵共有をおこなってきたら、たとえ鍵のかかった箱に手紙を入れて送っても鍵番号を共有した相手は実際には暗黒郵政公社なので、騙されて秘密を教えてしまうかもしれません。

また たとえ本物のボブと DH 鍵共有を使ってやりとりしていても、以下のように手紙を改竄すればアリスとボブの間のやり取りを盗み見ることができてしまうことにも気づきました。

改竄による鍵共有の突破

（前回の話を読んでいない方は、まずは「鍵共有」の部分 だけでも読むことをオススメします。）

アリスはボブと鍵共有をしようと思って、まず「初期数」を送ります。暗黒郵政公社は、これはそのまま改竄せずにボブに送ります。（ただし盗み見てメモしてはおきます。）

続いてアリスとボブはそれぞれ適当な数値「秘密数」を決め、それに初期数を足した数「公開数」を求めるのですが、暗黒郵政公社も同様に「秘密数」を決め、「公開数」を求めておきます。

そうしたらアリスとボブはお互いに「公開数」を送り合うわけですが、暗黒郵政公社はその手紙を改竄し、自分の「公開数」に書き変えた上で送ってしまいます。

アリスとボブ、そして暗黒郵政公社は、受け取った「公開数」に自分の「秘密数」を足します。すると下図のようにアリスとボブではなく、アリスと暗黒郵政公社、そしてボブと暗黒郵政公社の間で同じ鍵番号を共有することになってしまいます。

ボブは鍵のかかる箱を、アリスと共有した（と思っているが実際には暗黒郵政公社と共有してしまっている）「83」にロックしてアリスに送りますが、暗黒郵政公社はその鍵番号を知っているので鍵を開けて中の手紙を盗み見ることができてしまいます。

暗黒郵政公社はその後手紙を戻し、鍵を「73」に変更して再度ロックした上でアリスに送ります。アリスはボブと共有した（と思っているが実際には暗黒郵政公社と共有してしまっている）「73」で鍵を開けることができたので、「ああ、ボブとちゃんと鍵番号が共有できた」と思い込んでしまいます。¹

このように、暗黒郵政公社が改竄もできる状況では、鍵共有だけでは盗み見を防ぐことはできないのです。

なりすましにしろ改竄にしろ、その公開数が（暗黒郵政公社ではなく）間違いなくアリス／ボブのものであることを確かめる仕組み、すなわち認証が必要なのです。

「すでに共有した鍵番号を使い続ければいいのでは？」

（この部分は「足し算だけの世界」での都合による話であり重要ではないので、読み飛ばしても構いません。）

暗黒郵政公社の改竄事業が始まる前に、アリスとボブはすでに鍵共有によって鍵番号の共有に成功しています。それであれば、その番号を改竄事業開始後にも継続して使い続ければいいのではないか？と思った方もいるかもしれません。

ですがもともと改竄事業発表以前から、アリスとボブは定期的に鍵共有をやり直して鍵番号を変更していました。なぜなら、同じ鍵番号を使い続けることのリスクに気づいていたからです。

アリスたちが使っていた箱は、6桁までしか鍵番号に設定できませんでした。6桁ということはつまり、100万通りの鍵番号です。暗黒郵政公社が 000000 から 999999 までをすべて試してしまえば、必ず箱を開けることができてしまいます。

とはいえさすがに100万通りをすべて試すのにはかなりの時間がかかるので、一通の手紙に対して全部試すのは現実的ではありません。ですが、毎回少しずつ違う番号を試していったらどうでしょう？

たとえば上図のように毎回1000通りを試していれば、アリスとボブが同じ鍵番号で1000通手紙をやりとりすると、確実に鍵を開けられてしまうことになります。そして同じ鍵番号を使い続けている場合、一度開けられてしまえばその後もずっと開けられてしまうことになります。² ですのでアリスとボブは、定期的に鍵番号を変更することを取り決めていたのです。³

改竄・なりすまし対策「署名」

ところで実はアリスとボブは、暗黒郵政公社が改竄・なりすまし事業を正式発表する前から、そうしたことが行われる可能性を考慮し対策をおこなっていました。それは「署名」です。

アリスたちは手紙本文は手書きしないこともありましたが、その場合も必ず手紙一枚一枚に手書きで「署名」、すなわち自分の名前を書いていました。アリスもボブもなかなかにクセのある字だったこともあり、暗黒郵政公社が署名をマネしようとしても簡単にはマネできず、お互いの署名を何度も見てきている二人であれば偽の署名を見破ることができました。

しかし、アリスが暗黒郵政公社に送り込んだ諜報員から、暗黒郵政公社の恐ろしい発明品が完成間近だという情報が入りました。その名は「筆跡コピーペン」。その名の通り、このペンを使えば他人の筆跡をそっくりマネて文字を書くことができてしまうという悪魔の発明品です。筆跡コピーペンが完成しだい暗黒郵政公社は改竄・なりすまし事業を開始する予定であり、そうなってしまえばいくらアリスたちが手紙に署名をしていたとしても、暗黒郵政公社はその署名をそっくりマネて偽の手紙を書くことができてしまうのです。⁴

その情報を知ったアリスたちは焦りました。筆跡コピーペンが完成し改竄事業が始まったあとからでは、二人がそれに対抗するのがさらに難しくなるのは明らかです。だとすれば、改竄事業開始後にも安全に鍵共有ができるような何らかの方法の準備を、筆跡コピーペン完成前に済ませておくしかありません。

アリスは不眠不休で考えた末に、ついにそうした方法を思いつきました。アリスはその究極奥義を、「できた…これこそ邪（じゃ）悪の化身たる暗黒郵政公社の野望を打ち砕く、署名に代わる新たな方法！」、略して「デジタル署名」と名付けました。では、この究極奥義：デジタル署名の中身を見てみましょう！

署名の本質

まずその前に、アリスがデジタル署名を思いつくまでの過程を少し見てみましょう。

そもそも、どうして「署名」は認証に使えたのでしょうか？それは、「署名」は本人ではないとできないが、「署名の検証」（つまり、その署名が本人のものであることの確認）は誰でもできる、という性質があるからです。

ということは、同様に「行為Ａは本人ではないとできないが、それに対応した行為Ｂは誰でもできる」ような行為のペアＡ・Ｂがあれば、行為Ａを「署名」、行為Ｂを「検証」として使えるということです。

さて この「足し算だけの世界」では、「★と▲を足した数はいくら？」という質問にはすぐに答えられるのですが、「★を足すと▲になる数はいくら？」という質問には簡単には答えられないのでした。

★と▲を足した数はいくら？	★を足すと▲になる数はいくら？
簡単に計算できる。	簡単には計算できない。 特に数が大きい場合は、事実上計算不可能。

アリスはこの性質をうまく使うことで、「本人ではないとできない計算」と「それに対応した誰でもできる計算」という計算のペアを作ることはできないか、と考えたのです。

デジタル署名

まずアリスとボブは、暗黒郵政公社が改竄・なりすまし事業を開始する前に、適当な数を２つ作りました。そしてその２数を足し合わせます。最初に用意した数の１つを「署名数」、もう１つの数を「検証数（小）」、足し合わせた数を「検証数（大）」と呼ぶことにします。

そして「検証数（小・大）」を、お互いに送りあいます。この時、検証数は暗黒郵政公社に盗み見されてしまっても問題ありません。⁵

（※ 計算しやすいように小さい数値を使っていますが、実際にはもっと大きな数値を使います。）

さて、鍵共有を行います。まずはいつものように「初期数」を送り、「秘密数」を決めて「公開数」（＝初期数＋秘密数）を計算します。ここまでは今まで通りです。

そうしたら今までは「公開数」（たとえば 33 ）をただ送っていましたが、「公開数」に「署名数」を足した数値（この例であれば、2033）を計算し、それを一緒にこのように送ります。

ボブへ
私の公開数は 33 だよ！
その証拠に、「2033」に私の検証数（小）「1000」を足してみて！
「33」に私の検証数（大）「3000」を足した数と等しくなるから！

アリス

この手紙を受け取ったボブは、まず手紙に書かれた「検証数（小・大）」が 以前アリスから送られたものと等しいか確認します。⁶

そうしたら、アリスの手紙通り「2033」に検証数（小）「1000」を足してみると、「3033」になります。同様に「33」に検証数（大）「3000」を足してみると、こちらも「3033」と両者が等しくなりました。そうなったならば、この公開数は確かにアリスのもの（暗黒郵政公社がなりすましたり、改竄したりしたものではない）と判断できるのです。

そう、「公開数＋署名数」という数を作れるのは「署名数」を知っているアリスだけですが、その数に「検証数（小）」を足したら「公開数＋検証数（大）」と等しくなることは誰でも確かめられる…これはまさに上に書いた署名の本質です。

同様のことをボブ→アリスでもおこなった上で、後は今まで通り「相手の公開数」＋「自分の秘密数」から鍵番号を求め、それ以後は鍵のかかった箱でのやり取りに移行します。

このデジタル署名によって、暗黒郵政公社が改竄・なりすましをしたとしても そのことに気づけるようになり、安心して鍵共有を行うことができるようになったのです。

これで本当に安全？

さて、気になるのは「この方法で本当に安全と言えるのか」です。

暗黒郵政公社の側は、「公開数」「検証数（小）」「検証数（大）」を手に入れることができます。⁷ ここから「『検証数（小）』を足すと、『公開数＋検証数（大）』と等しくなる数」を改竄や盗み見によって作ることはできないでしょうか？

まず、我々の世界であれば簡単に求められるこの計算ですが、この世界の「『★を足すと▲になる数』を簡単には求められない」という性質から、「1000 を足すと、3033 と等しくなる数」を計算によって求めるのは困難です。

では、他の数を改竄していいならどうでしょう？

まず「公開数」だけを改竄する場合を考えます。「『検証数（小）』を足すと、『公開数＋検証数（大）』と等しくなる数」とは公開数がいくつであろうが「公開数＋署名数」のことなので、「署名数」を知ることができない限り「公開数」だけをいくら改竄しても無駄です。

「検証数（小・大）」を改竄していいならば、目当ての数を作ることができます。暗黒郵政公社も自分で「検証数（小）」「署名数」「検証数（大）」を作り、このように手紙を送ります。

ですが上で書いたとおり、ボブは「まず手紙に書かれた『検証数（小・大）』が 以前アリスから送られたものと等しいか確認」します。ですので その時点で改竄がバレてしまうのです。

結論として、「署名数」を知らないアリス以外は「『検証数（小）』を足すと、『公開数＋検証数（大）』と等しくなる数」を作ることはできないので、このデジタル署名をアリスの認証として使うことができるのです。

次回予告

こうして平穏な文通生活を取り戻したアリスとボブ。しかし、彼ら以外の人たちは今も暗黒郵政公社の悪行に苦しめられる日々を過ごしている…アリスはそのことに心を痛めていたのです。

今こそ世界を救うのだ、アリス！次回「PKI」、お楽しみに！

余談

前話の次回予告で「デジタル署名」と書いてしまいましたが、デジタル署名全般についての話ではなくなってしまったので「デジタル署名（による認証）」と改題しました。

前話では DH 鍵共有をかなりそのまま「足し算だけの世界」に落とし込んだのですが、今回はそれがうまく行かなかったのでオリジナルの方式になっています。そのため、もしかしたら「足し算だけの世界」であっても署名を偽造できるような脆弱性があるかもしれません。そうした問題点があるようでしたらコメントお願いします。

1. 「中間者攻撃」と呼ばれる攻撃手法の一つです。ここでは暗黒郵政公社が盗み見だけをしていますが、実際には盗み見だけでなく改竄も可能になります。 ↩

2. ここでは「一度鍵番号を知られてしまうと、その後の通信を解読されてしまう」という点を鍵番号を頻繁に変更するべき理由として書きましたが、実際の暗号通信においてはむしろ逆の理由で共通鍵を頻繁に変更しています。
   手紙と違ってデジタルデータは容易にコピーできるので、たとえ共通鍵を見破れず暗号を解読できなくても「鍵が手に入ったときのために、とりあえず暗号文をコピーしてとっておく」ということが可能です。そのため共通鍵を使いまわしている場合、「一度共通鍵を知られてしまうと、それ以前の暗号文まで解読されてしまう」のです。（詳しくは「Forward secrecy」で調べてください。） ↩

3. 一応補足しておきますが、これは「パスワードは定期変更するべき」という（誤った）主張とは性質が異なります。
   この例では「鍵番号は、総当たりによって現実的な時間で破ることができる」「攻撃者（暗黒郵政公社）は鍵番号を知ることができたら、そのことを気付かれないようにして長期的に悪用（盗み見）する可能性が高い」ので鍵番号を定期的に変更することに充分なメリットがあります。
   しかし一般的にパスワードは安易なものにしていない限り総当たりで破るのは現実的な時間では困難ですし、もし攻撃者がパスワードを入手したらすぐに露骨に悪用（オンラインバンキングであれば自分の口座にお金を振り込むなど）する可能性が高いので、定期変更にはあまりメリットがなく却って安易なパスワードを増やすデメリットのほうが大きいと言えます。 ↩

4. もちろん我々の世界に「筆跡コピーペン」などというものはありませんが、「デジタル技術」こそがそれにあたります。デジタルデータであれば、そっくりそのままコピーすることが可能だからです。 ↩

5. ただし、あくまでも「暗黒郵政公社が改竄・なりすまし事業を開始する前」でなければなりません。 ↩

6. そもそも手紙に「検証数（小・大）」を書かなくてもいいんですが、実際に我々の世界で行われているやり方に近づけるためにそうしました。 ↩

7. 他にも「初期数」「ボブの公開数・検証数（小・大）」も手に入りますが、ここでは特に必要ないので省略しました。 ↩