ハッシュ#
皆さんはハッシュ関数の動作原理に比較的慣れていると思いますが、暗号学で使用されるハッシュ関数はcrypto-graphic hash functionと呼ばれます。
それには二つの重要な性質があります。一つは collision resistance（衝突耐性）と呼ばれるものです。ここでの collision はハッシュ衝突を指します。
もし二つの入力 x, y があり、x ≠ y で、ハッシュ関数がH(v)である場合、H(x) = H(y)となると、これがハッシュ衝突と呼ばれます。
異なる二つの入力から計算されたハッシュ値が等しいということです。ハッシュ衝突は非常に一般的です。私たちがハッシュテーブルを使用する過程でハッシュ衝突に遭遇することがあります。
異なる入力がハッシュテーブルの同じ位置にマッピングされる可能性があります。一般的に、ハッシュ衝突は避けられません。
なぜなら、入力空間は出力空間よりもはるかに大きいためです。例えば、256 ビットのハッシュ値があるとします。では、出力空間はどれくらい大きいのでしょうか。
すべてのハッシュ値の可能性は 2 の 256 乗であり、出力空間はこの大きさしかありません。しかし、入力空間は無限大であり得ます。
したがって、無限の多様な可能性があります。鳩の巣原理に従えば、必ず二つの入力が同じ出力にマッピングされる状況が発生します。
したがって、ここで言うcollision resistanceはハッシュ衝突が発生しないことを意味します。ある📖ではこの性質をcollision freeと呼んでいます。
この言い方はあまり好きではありません。なぜなら、それは人々に誤解を与えやすいからです。まるで衝突が発生しないかのように思われます。実際には、衝突は客観的に存在します。
この意味は、実際には効率的にハッシュ衝突を人為的に生成する方法はないということです。与えられたxに対して、H(x)とH(y)のハッシュ値がちょうど等しくなるような別のyを見つける良い方法はありません。効率的に見つける方法はありません。無理に探す場合は、力任せの解法を使用することができます。
例えば、xとyがある場合、すべての入力の可能性を列挙して、どれが計算されたハッシュ値とちょうど等しいかを確認します。この方法はbrute-forceと呼ばれます。
すべての値を列挙し、最終的にハッシュ値がちょうど衝突するものを見つけます。もし入力空間が非常に大きい場合、例えばハッシュ値が 256 ビットである場合、実際には力任せの解法を使用することは実行不可能です。その作業量は非常に大きすぎます。
では、collision resistanceという性質は何に役立つのでしょうか？
それはメッセージのダイジェストを求めるために使用できます。
例えば、mというメッセージがあるとします。そのハッシュ値H(m)を取ります。
このハッシュ値はこのメッセージのダイジェストと見なすことができます。これはこのメッセージの改ざんを検出するために使用されます。
例えば、誰かがこのメッセージの内容を変更した場合、そのハッシュ値は変わります。
したがって、collision resistanceという性質は、H(m')がH(m)とちょうど等しくなるような別のm'を見つけることができないことを意味します。
内容を改ざんすることはできず、検出されることもありません。例えば、非常に大きなファイルがあるとします。それをあるクラウドストレージサービスに保存したいとします。
必要なときに再度ダウンロードすることになりますが、どうやってダウンロードしたバージョンが、最初にアップロードしたバージョンと同じであることを確認するのでしょうか？
これにはハッシュ関数の衝突耐性の性質を利用できます。このファイルをアップロードする前に、まずハッシュ値を計算します。
このハッシュ値はローカルに保存します。将来的にダウンロードした後、再度ハッシュ値を計算します。そして、元々保存していたハッシュ値と比較します。もし同じであれば、
アップロードしたこのファイルは改ざんされていないことを示します。ダウンロードしたものは元々のバージョンです。これが衝突耐性の一つの用途です。
一点注意してください。数学的に衝突耐性であると証明できるハッシュ関数は存在しません。
つまり、私たちが今話している非常に重要な性質は、理論的には証明できないのです。
これは実践の経験に依存するしかありません。いくつかのハッシュ関数は、長い時間の検証を経てきました。
世界中には多くの暗号学の専門家がいますが、誰もハッシュ衝突を人為的に生成する方法を見つけていません。
したがって、これらのハッシュ関数は衝突耐性があると考えられています。つまり、実践的な経験です。
また、衝突耐性があると考えられていたハッシュ関数もありますが、後に人々がハッシュ衝突を生成する方法を見つけました。ここでの重要な例は MD5 です。MD5 はかつて非常に人気のあるハッシュ関数で、安全だと考えられていました。
しかし、今ではそれは通用しなくなり、私たちは人為的にハッシュ衝突を生成する方法を知っています。
暗号学で使用されるハッシュ関数には、もう一つの性質があります：hiding（隠蔽）。hiding とは何でしょうか？hiding は、ハッシュ関数の計算過程が一方向であることを意味します。
逆算は不可能で、与えられたxからそのハッシュ値H(x)を計算できますが、ハッシュ値H(x)から元の入力xを逆算することはできません。言い換えれば、
このハッシュ値H(x)は入力xに関する情報を漏らしていません。これが hiding です。しかし、実際にはこの入力を知りたい場合、方法はあります。どうするかというと、やはり力任せの方法を使います。すべての可能な入力値を列挙して、どの入力の値がH(x)と元のH(x)と等しいかを確認します。
そうすれば、元の入力xが何であるかを推測できます。したがって、力任せの解法は一つの方法です。hiding という性質が成立する前提は、この入力空間が十分に大きく、
そのために力任せの解法が不可能であることです。また、この入力の分布が比較的均等である必要があります。さまざまな可能性のある値の可能性がほぼ同じである必要があります。もしこの入力空間が非常に大きいとしても、
ほとんどのケースで値が少数のいくつかの値に集中している場合、比較的簡単に破られる可能性があります。
hiding という性質は何に役立つのでしょうか？それは衝突耐性という性質と組み合わせて、デジタルコミットメントを実現するために使用されます。このデジタルコミットメントは、封印された封筒のデジタル同等物とも呼ばれます。
現実の生活での封印された封筒は何に使われるのでしょうか？
例えば、ある人が株式市場を予測できるとします。次の日にどの株がストップ高になるかを予測できるとします。
その人が予測が正確であることをどうやって証明するのでしょうか？一つの方法は、その人が前日にテレビで予測結果を発表することです（私は xxx 株が次の日にストップ高になると予測します。）。
次の日の取引終了後に、その株が本当にストップ高になったかを確認すれば、予測が正確かどうかがわかります。
こうすることに問題はありますか？これは予測の正確さを確認する方法のようですが、問題があります。もし予測結果を事前に公開した場合、
株式市場に影響を与える可能性があります。例えば、その人が非常に有名で、皆がその人を株の神と見なしている場合、本来その株はストップ高にならないはずなのに、彼が公開予測をしたことで、
皆が必死に買いに走る結果、ストップ高になってしまうことがあります。当然、逆の状況もあり得ます。その株が本当にストップ高になる必要がある場合、誰かが場を乱そうとするかもしれません。
「あなたはストップ高になると予測したのだから、私はストップ高にならないようにする」と言って、必死に売りに出すこともあります。これらはすべて起こり得ることです。これにより、予測結果は事前に公開できないことが示されています。
しかし、予測結果を事前に公開しない場合、次の日の取引終了後に公開することになりますが、その予測結果が改ざんされていないかどうかをどうやって確認するのでしょうか？
最終的に公開された結果が、前日に作成されたものであるかどうかを確認する必要があります。これには、私たちが言う封印された封筒を使用する必要があります。
予測結果を紙に書き、それを封筒に入れて封をします。この封筒は第三者の公正機関に保管してもらいます。
次の日の取引終了後にそれを開封し、その結果が正確かどうかを確認します。現実の封印された封筒はこれです。
では、電子の世界では、デジタル封印された封筒をどうやって実現するのでしょうか？予測結果を入力xとしてハッシュ値を計算します。そして、このハッシュ値を公開することができます。hiding の性質があるため、あなたはこのハッシュ値から予測結果が何であるかを知ることはできません。そして次の日の取引終了後に、予測結果を公開します。衝突耐性の性質があるため、私の予測結果は改ざんされることはありません。もし改ざんされた場合、最初に公開されたハッシュ値と一致しなくなります。これにより、封印された封筒の機能を果たします。実際の操作にはいくつかの注意すべき詳細があります。hiding の性質の前提は何か。入力空間が十分に大きく、分布が比較的均等であることです。この入力がこの性質を満たさない場合、例えば、次の日にどの株がストップ高になるかを予測する場合、株は数千銘柄しかないため、入力空間は十分に大きくありません。一般的な方法は、この入力の後ろにランダムな数をランダムに結合し、それを一緒にハッシュを取ることです。つまり、これはxではなく、xの後ろに nonce を結合し、全体をハッシュします。H(x | Nonce)。この nonce は私たちが選んだランダムな数であり、選挙後に全体の入力が十分にランダムであることを保証します。そして、分布も十分に均等です。これは実際の操作で注意すべきいくつかの詳細です。
暗号学で要求されるこの二つの性質に加えて、ビットコインで使用されるハッシュ関数には三つ目の性質が要求されます。それは puzzle friendly（パズルフレンドリー）と呼ばれます。これは、ハッシュの計算が事前に予測できないことを意味します。入力を見ただけでは、そのハッシュ値が何であるかを知ることは非常に難しいのです。したがって、計算されたハッシュ値が特定の範囲内にあることを考えると、良い方法はなく、一つ一つ試すしかありません。どの入力がそのハッシュ値を計算するかを確認します。例えば、あるハッシュ値を得たいとします。前のkビットがすべて 0 である必要があります。0000000…0000000xxxxxxx..xxx 全体で 256 ビットで、最初のk個のゼロで始まる必要があります。どの入力がこのハッシュ値を計算するのかはわかりません。puzzle friendly という性質は、事前にはわからないということです。どの入力がこのハッシュ値を計算する可能性が高いかはわかりません。このハッシュ値を得るためには、一つ一つ試すしかありません。近道はありません。この性質がなぜ puzzle friendly と呼ばれるのかは、後でビットコインのマイニングプロセスについて説明します。皆さんは「マイニング」という言葉を聞いたことがあるかもしれません。マイニングは実際には nonce を見つけることです。この nonce はブロックのヘッダー内の他の情報と組み合わされ、入力としてハッシュを取り出します。そのハッシュ値は特定の目標閾値以下でなければなりません。これはH(block header) ≤ targetです。ビットコインはブロックチェーンであり、ブロックチェーンは一つ一つのブロックから成る連結リストです。各ブロックにはブロックヘッダー、block header があり、ブロックヘッダーには多くのフィールドがあります。その中に設定可能なランダム数 nonce のフィールドがあります。マイニングのプロセスは、さまざまな nonce を試し続けて、全体のブロックヘッダーをハッシュした後、指定された範囲内に収まるようにすることです。例えば、これが全体の出力空間 outspace です。求められるハッシュ値は、この一点だけが合法である必要があります。これが target space です。この puzzle friendly という性質は、マイニングのプロセスに近道がないことを意味します。大量の nonce を試し続けることで、要求に合った解を見つけることができます。したがって、このプロセスは作業証明として使用されます。これを proof of work と呼びます。あなたがマイニングを行い、要求に合った nonce を見つけた場合、それは必ず大量の作業を行った結果です。他に近道はありません。
ここで注意してください。マイニングのプロセスは、多くの作業量を必要とし、要求に合った nonce を見つけることが難しいですが、一旦誰かがそのような nonce を見つけて公開した場合、他の人がその nonce が要求に合っているかどうかを検証するのは非常に簡単です。ハッシュを一度計算するだけで済みます。この nonce はヘッダーの一部として、ハッシュ値を一度計算し、それが目標の閾値以下であるかどうかを確認します。マイニングは難しいが、検証は簡単です。この性質は difficult to solve, but easy to verify（解決は難しいが、検証は簡単）と呼ばれます。このようなマイニングパズルを設計する際には、この性質に注意が必要です。
ビットコインで使用されるハッシュ関数は SHA-256 です。この sha は secure hash algorithm の略です。私たちが話したこの三つの性質はすべて満たされています。ある学生は puzzle friendly と collision resistance が非常に似ていると感じるかもしれません。この二つの性質には一定の関連性がありますが、完全に同じではありません。私たちはビットコインが暗号学の二つの機能を使用していることを言いました。一つはハッシュ、もう一つは署名です。
署名#
ここで、最初の機能であるハッシュについての説明を終えます。次に署名について説明します。
署名について説明するためには、ビットコインシステムにおけるアカウント管理について触れる必要があります。日常生活でアカウントを開設したい場合、身分証明書を持って銀行に行き、口座開設手続きを行います。これが中央集権型システムにおけるアカウント管理の方法です。しかし、ビットコインは非中央集権的であり、銀行のような機関は存在しません。では、どうやってアカウントを開設するのでしょうか？各ユーザーが自分でアカウントを開設することを決定します。誰の承認も必要ありません。アカウント開設のプロセスは非常に簡単で、公開鍵と秘密鍵のペアを作成することです（public key, private key）。ローカルで公開鍵と秘密鍵のペアを生成します。これがビットコインにおけるアカウントを表します。公開鍵と秘密鍵の概念は非対称暗号の体系から来ています。これは asymmetric encryption algorithm と呼ばれます。最初の暗号体系は対称的でした。symmetric encryption algorithm と呼ばれます。例えば、二人が通信を行う場合、ある情報をあなたに送信したいとします。しかし、この通信ネットワークは盗聴される可能性があります。どうするかというと、私たち二人は事前に一つの鍵を決めます。それを encryption key と呼びます。私はこの情報を暗号化してあなたに送信します。あなたは受け取った後、その鍵を使って復号します。暗号化と復号に同じ鍵を使用するため、これが対称的な暗号体系と呼ばれます。この前提は、安全なチャネルが存在し、通信の両者にその鍵を配布できることです。明らかに、この鍵をネットワーク上で平文の形式で送信することはできません。私たちはネットワーク自体が安全でないと仮定しています。盗聴される可能性があるため、これが対称暗号体系の弱点です。鍵の配布があまり便利ではありません。この問題を解決するために非対称暗号体系が提案されました。私たちは一つの鍵ではなく、二つの鍵のペアを使用します。一つは公開鍵、もう一つは秘密鍵です。暗号化には公開鍵を使用し、復号には秘密鍵を使用します。例えば、あなたに情報を送信したい場合、あなたの公開鍵を使ってその情報を暗号化し、あなたは受け取った後、あなたの秘密鍵を使って復号します。元の情報を得ることができます。皆さん注意してください。暗号化と復号には同じ人の公開鍵と秘密鍵が使用されます。受信者の公開鍵と秘密鍵です。
これにはどんな利点があるのでしょうか？公開鍵は秘密にする必要がなく、暗号化に使用される公開鍵は秘密にする必要がなく、すべての人に知らせることができます。中には、自分のホームページに自分の公開鍵を載せている人もいます。誰でも知ることができます。秘密鍵は秘密にする必要があります。復号には秘密鍵が必要ですが、秘密鍵はローカルに保存しておけばよく、相手に送信する必要はありません。通信相手はあなたの秘密鍵を知る必要はありません。彼はあなたの公開鍵で暗号化します。あなたが彼に返信する場合、彼の公開鍵で暗号化します。相手の秘密鍵を知る必要はありません。これにより、対称暗号体系における鍵の配布の不便さが解決されます。ビットコインシステムでは、アカウントを作成するためにローカルで公開鍵と秘密鍵のペアを生成します。この公開鍵はあなたの銀行口座に相当します。他の人があなたに送金するには、あなたの公開鍵を知っていればよいのです。この秘密鍵はあなたのアカウントのパスワードに相当します。この秘密鍵を知っていれば、アカウントの資金を移動させることができます。さて、問題があります。前述のように、ビットコインシステムは暗号化されていません。彼は暗号通貨と呼ばれていますが、実際には暗号化されていません。情報はすべて公開されています。それでは、この公開鍵と秘密鍵は何のためにあるのでしょうか？実際には署名を行うために使用されます。
例えば、私はあなたに 10 ビットコインを送金したいとします。そして、この取引をブロックチェーンに公開します。他の人はどうやってこの取引が確かに私から発信されたものであることを知るのでしょうか？誰かが私になりすまして、こっそり私の口座からお金を移動させることはないのでしょうか？これには、取引を公開する際に自分の秘密鍵を使用してこの取引に署名する必要があります。そうすれば、他の人はこの取引を受け取った後、私の公開鍵を使ってこの署名の正当性を検証します。署名には秘密鍵が使用され、署名の検証にはその人の公開鍵が使用されます。
依然として同じ人です。すべての人が独立してアカウントを生成します。ローカルで独立して公開鍵と秘密鍵のペアを生成します。誰の承認も必要ありませんが、万が一二人が同じ公開鍵と秘密鍵のペアを生成した場合、どうすればよいのでしょうか？例えば、誰かがビットコインを盗もうとする場合、一つの方法は公開鍵と秘密鍵を生成し続け、生成した公開鍵がブロックチェーン上の既存の公開鍵と同じかどうかを比較することです。もし同じであれば、秘密鍵を使ってその口座のお金を盗むことができます。この攻撃方法は理論的には可能のように思えますが、実際には不可能です。例えば、256 ビットのハッシュ値の場合、同じ公開鍵と秘密鍵を生成する可能性は微々たるものです。例えば、あなたがスーパーコンピュータを持っていて、毎日大量の公開鍵と秘密鍵のペアを生成しても、二人の公開鍵と秘密鍵のペアが同じになる確率は無視できるほど小さいのです。この確率は地球が爆発する確率よりも小さいです。これまでのところ、この方法で攻撃に成功した人は発見されていません。ここで強調したいのは、公開鍵と秘密鍵を生成する際に良いランダムソースが必要であるということです。これを a good source of randomness と呼びます。公開鍵と秘密鍵を生成するプロセスは明らかにランダムです。もし選択したランダムソースが良くない場合、前述の分析は成り立たなくなります。二人の公開鍵と秘密鍵のペアが同じになる可能性が出てきます。ビットコインで使用される署名アルゴリズムは、公開鍵と秘密鍵を生成する際に良いランダムソースが必要なだけでなく、その後の各署名の際にも良いランダムソースが必要です。もし一度でも署名に使用するランダムソースが良くない場合、秘密鍵が漏洩する可能性があります。そして、それが全て終わりです。この点には十分注意してください。
私たちは二つの機能、すなわちハッシュと署名について説明しました。この二つの機能は組み合わせて使用することができます。ビットコインシステムでは、一般的にメッセージに対してハッシュを求め、その後そのハッシュ値に署名します。