こんにちは。くろこんです。今回は最近勉強した知識を使った解説記事です。
記事の概要
まずは、こちらの X でのポストをご覧ください。
SHA-256 のクラックに触れたイーロンマスク氏のポストです。
このポストの返信にもあるのですが、通常は SHA-256 がクラックされる、とは言いません。しかし、この言い方が成り立つ文脈もあります。このあたりが理解できるような説明を目指す記事となっています。たとえ話が主なもので、数式など厳密なものは出てこないようになっています。
そもそも secp256k1 や SHA-256 とは
ビットコイン関連の量子コンピュータの話題では secp256k1 という署名方式が触れられることが多いです。一方でマイニングのときには SHA-256 や RIPEMD-160 などの名前が挙がります。
これらはどのように違うのでしょうか？
| 分類 | 例 | 説明 |
|---|---|---|
| 署名方式 | secp256k1 | 誰が書いたメッセージか数学的に保証する方法 |
| 暗号学的ハッシュ関数 | SHA-256 RIPEMD-160 | 入力を見た目がランダムな文字列に変換する |
ビットコインでは、secp256k1 と SHA-256 は、それぞれ異なる役割を果たします。
secp256k1
署名方式で、誰が書いたメッセージか数学的に保証する方法です。私というアカウントでログインして「私はＡさんに 1BTC 送ります」というのにサインすることで、周りからは「私さんがサインしてるからこの 1BTC は今はＡさんのものだ」と判断されることになります。
「私はＡさんに 1BTC 送ります」（私のサイン）
のように文章の後に続いてサインをします。この文字は本人にしか書けないような文字にします。
なかなかイメージが難しいですが、手元に「遺伝子が同じ血液かどうか判別できる薬」があったとしましょう。（私のサイン）の部分が血液でのハンコされていた場合 「サンプルの血液があればその薬で本人かどうか確認できる」 というようなイメージです。例えば、（私のサイン）から（私の血判）に置き換えても大丈夫です。
| 元の言葉 | 例え |
|---|---|
| 署名方式 | 書いた人が本人か確認する方法のこと。指紋採取だったり筆跡鑑定だったりいろいろやり方がある。 |
| secp256k1 | 「遺伝子が同じ血液かどうか判別できる薬」で書いた人が本人か確認する方法のこと 。参加する人にこの薬は配って、みんな利用できる。 |
| 秘密鍵 | 遺伝子。自分だけが持っている情報で、パスワードにあたる。 |
| 公開鍵 | 血液。「遺伝子が同じ血液かどうか判別できる薬」で使ってもらうために公開しておく。 |
| 署名 | 血液のハンコ。血判。「遺伝子が同じ血液かどうか判別できる薬」と公開鍵の血液で本人と確認できる。 |
SHA-256
ハッシュ関数と呼ばれる関数で、入力するとランダムに見える文字列が返ってきます。RIPEMD-160 は SHA-256 と処理が違いますが、ハッシュ関数であることは同じなので、今回は SHA-256 だけに注目します。「入力するとランダムに見える文字列が返ってくる」というのは 「商品が隠されている自動販売機」 というのが直感的です。
| 元の言葉 | 例え |
|---|---|
| ハッシュ関数（暗号学的ハッシュ関数） | 「商品が隠されている自動販売機」。わけのわからないものがいきなりでてくる。隣のボタンと商品の関連性が無い。ただし、同じボタンを押せば同じ商品がでてくる。 |
| SHA-256 | ハッシュ関数（暗号学的ハッシュ関数）の１つ。 「渋谷駅から一番近い「商品が隠されている自動販売機」」 というようなもの。 |
ビットコインにおいては、取引の決定に用いられます。ここではおおざっぱな説明をします。厳密に正確ではないですが、流れは合っている、くらいに思ってもらえればと思います。
「私はＡさんに 1BTC 送ります」（私のサイン） を SHA-256 に入力する → 5e884898....
先ほどの secp256k1 のサイン済みの内容をそのまま入力するとランダムに値が決まります。
「私はＡさんに 1BTC 送ります」（私のサイン）ああああ を SHA-256 に入力する → da280471....
「私はＡさんに 1BTC 送ります」（私のサイン）あああい を SHA-256 に入力する → 51d0e56f....
「私はＡさんに 1BTC 送ります」（私のサイン）あああう を SHA-256 に入力する → 8dc62927....
入力に対してランダムに見える文字列が返ってくるということは、サイン済みの内容のおしりに少し文字を足して値を変えることができます。もう少し頑張ると、
「私はＡさんに 1BTC 送ります」（私のサイン）げかむろ を SHA-256 に入力する → 00000000....
運よく値が 0 ばかりになることがあります。このとき、
「私はＡさんに 1BTC 送ります」（私のサイン）
が取引として有効とみなされます。対応するよくわからない文字列（今回は『げかむろ』）を見つけてくれた人がいるので、他の人が十分頑張って認めてくれたから有効にしよう、となります。
もう一つ、この「げかむろ」を見つけた人にビットコインを付与する、というルールがあります。このビットコインの付与こそが、いわゆるマイニングと呼ばれるものです。
……たとえ話をするということなので、これも例えます！
例えたほう難しいかもしれないビットコインの SHA-256
「渋谷駅から一番近い「商品が隠されている自動販売機」」 には「７１×７１×７１×７１個のボタン」があるとします。７１というのは、先ほどマイニングにひらがなを使ったので、４６音と濁音半濁音を合わせて７１。４文字なので４回かけています。25411681 個くらいボタンがあります。
「私はＡさんに 1BTC 送ります」（私のサイン）
↓
わたしは ＋ ええさん ＋ にいちお ＋ くります ＋ わたしの ＋ さいん
↓
43 15 11 25 + 3 3 10 45 + 21 1 16 4 + 7 39 30 12 + 43 15 11 24 + 10 1 45 0
↓
だえじり（56 3 52 39）
こうやって４文字ごとに区切れば、自然に自動販売機の押すボタンを決められます。例えば、４文字目は
25 + 45 + 4 + 12 + 24 + 0 = 110 → 39 → り
のように足し算の結果を 71 で割った余りを求めています。繰り上がりを３文字目に反映はしていません。「私はＡさんに 1BTC 送ります」（私のサイン）というメッセージから上記の計算で「だえじり」を決めます。「だえじり」は$56 × 71 × 71 × 71 + 3 × 71 × 71 + 52 × 71 + 39$なので…… 20061870 番目のボタンを押します（白目）。
出てきた商品は……シャープペンシルの替え芯（0.7mm 濃さB）でした。ビットコインのマイニングでは、出てくる商品が 缶ビール（酒税法上のビール 350ml） になるまでメッセージを加工しなければなりません。
「私はＡさんに 1BTC 送ります」（私のサイン）いいいい
↓
わたしは ＋ ええさん ＋ にいちお ＋ くります ＋ わたしの ＋ さいん ＋ いいいい
↓
43 15 11 25 + 3 3 10 45 + 21 1 16 4 + 7 39 30 12 + 43 15 11 24 + 10 1 45 0 + 1 1 1 1
↓
ぢおずる（57 4 53 40）
……えーっと、20424894 番目のボタンを押すと……今度の商品は板チョコでした。缶ビールではありません。
…………
…………
…………
うーん……おっと？ 「げかむろ」で加工したら、 Ｓ社の缶ビール(350ml) が！ 「げかむろ」を使って「私はＡさんに 1BTC 送ります」（私のサイン）を、ビットコインのマイニングの結果として登録しよう！
……というのが、ビットコインの取引の登録であって、マイニングのイメージです。
余談ですが 「とてつもなく無駄に「商品が隠されている自動販売機」が動いているな」 と思った場合、それは正しいです。ビットコインのマイニングというのは「ビットコインのためだけにされる処理」であって、それ以外に全く意味のない処理です。
現実世界でも信じられないほどの回数 SHA-256 は、ビットコインのマイニングを通して処理されています。ビットコインが環境に悪いという場合、多くの場合にこのビットコイン以外にとって無駄な処理のことをいいます。
secp256k1 と SHA-256 のクラック
上記のように、secp256k1 と SHA-256 では、それぞれ役割が違うため、クラックと言う場合、起こることが異なります。
secp256k1 のクラック
これは分かりやすく、秘密鍵が流出することです。「遺伝子が同じ血液かどうか判別できる薬」で例えるなら、 「遺伝子が特定されて血液を複製されてしまう」 というようなことです。
もし秘密鍵が流出すると、秘密鍵を盗んだ人は先ほどの「私さん」の財布からいくらでもほかの人にビットコインを送れてしまいます。 「複製した血液の血判でいくらでもサインできる」 ということです。
「遺伝子を特定して血液を複製」などというのは、並大抵の技術力ではないわけです。しかし、そのような水準の難しいことを力押しでしてしまうのではないかと、量子コンピュータは期待されています。
量子コンピュータでのクラックと言う場合、署名の電子的な筆跡からパスワードはもしかしてこんなものでは？ と当ててしまう処理に相当します。現在のコンピューターでは難しい処理ですが、十分に余裕のある量子コンピュータでは計算できる可能性があると考えられています。
SHA-256 のクラック
まず、通常の文脈では、SHA-256 にクラックという言葉は使いません。一方で、secp256k1 の場合は、署名方法なので高い技術力で署名に不正ができたりすると、クラックと表現します。
「遺伝子を特定して血液を複製して血判を押す」 というのはいかにも悪いことのように見えます。一方で 「渋谷駅から一番近い「商品が隠されている自動販売機」で缶ビール（酒税法上のビール 350ml）を出すには〇〇〇〇番目のボタンを押すといい」 というと、攻略情報には見えますが悪いことかと言われるとなんとも、となります。
ここでは「ビットコインにおける SHA-256 のクラック」について説明します。ビットコインにおいては SHA-256 が組み込まれていて、SHA-256 がクラックされることも起こりうるわけです。
ここで悪知恵を働かせて、
『「私はＡさんに 1BTC 送ります」（私のサイン）げかむろ』 → 取り消し
↓ 変更
『「私はＡさんに 0.01BTC 送ります」（私のサイン）ＸＸＸＸ』
に書き換えようとたくらみます。Ａさんにもう払ったけど、書き換えちゃえば減らなかったことになるんじゃないの？ ということです。
「私はＡさんに 0.01BTC 送ります」（私のサイン）ああああ を SHA-256 に入力する → 73603d0d....
「私はＡさんに 0.01BTC 送ります」（私のサイン）あああい を SHA-256 に入力する → 6aabbdd6....
「私はＡさんに 0.01BTC 送ります」（私のサイン）あああう を SHA-256 に入力する → 2a11ef72....
・
・
・
「私はＡさんに 0.01BTC 送ります」（私のサイン）べこくん を SHA-256 に入力する → 00000000....
よし、できました。「べこくん」なら新しいメッセージでも、0 ばっかりに変換されて、Ａ社の缶ビール(350ml)が出てきました。これに書き換えれば大儲け……としている間にビットコインは姿を変えています。
『「私はＡさんに 1BTC 送ります」（私のサイン）げかむろ』『「ＢさんはＣさんに 0.5 BTC 送ります」（Ｂさんのサイン）しゆすえ』『「ＤさんはＥさんに 0.1 BTC 送ります」（Ｄさんのサイン）しじうる』……
なんだかすごく長くなってる……！？
『「私はＡさんに 1BTC 送ります」（私のサイン）げかむろ』が前提になった文字列の書き込み、つまりマイニングが世界中からされます。
ここで、ビットコインは 「マイニングの書き込みが最も長いものが優先される」 というルールがあります。このルールのせいで、書き換えたマイニングの結果は無視されてしまいます。
言い換えれば、本当は『「私はＡさんに 1BTC 送ります」（私のサイン）げかむろ』の前にもたくさんの取引がくっついる、ということになります。
……『「ＵさんはＶさんに 0.4BTC 送ります」（Ｕさんのサイン）むくさほ』『「ＸさんはＹさんに 0.2BTC 送ります」（Ｘさんのサイン）むぶいい』『「私はＡさんに 1BTC 送ります」（私のサイン）げかむろ』
こんな感じで、前にたくさん取引がくっついているのが本当の姿だったことになります。こういったルールによって悪知恵は通用しないようになっています。
通用しない理由は「缶ビール（酒税法上のビール 350ml）を出す入力が見つけにくい」と考えることもできます。自分が書き換えている時間に、世界中の他人が書き込むから、間に合わないということです。
他人より簡単に書き換えられるなら、後出しでマイニングの計算をしても追いつくため、さっきのような悪知恵もまかり通ってしまうわけです。そして、これが量子コンピュータによる SHA-256 のクラックと考えることができます。
あまりの速度で 「 SHA-256 が 00000000.... になる答えを探せる」 ことになれば、量子コンピュータの持ち主の思うように取引を無効にできてしまいます。
secp256k1 と SHA-256 のクラックのまとめ
以上をまとめると、それぞれのクラックの違いは以下のようになります。
secp256k1 のクラック
- パスワードの流出や特定に相当。
- クラックされると、保有しているビットコインを好きに使われてしまう。
- 公開鍵から秘密鍵を特定するのは、周りからはとてつもない先進科学に見える。例えば「遺伝子を特定して血液を複製」など。
- 備考として、パスワードを知ればよいので、時間はかかってもよいし、そもそも量子コンピュータでなくてもよい。極端に言えば、盗んでもよい。
SHA-256 のクラック
- 取引を有効無効にするマイニングを無制限に行える、ことに相当。
- 量子コンピュータの威力で他人のマイニングを無視するほどの速度を出す。とてつもなく速いが、周りからはそれだけに見える。
- 通常は「SHA-256 のクラック」とは言わない。例えば「渋谷駅から一番近い「商品が隠されている自動販売機」で缶ビール（酒税法上のビール 350ml）を出すには〇〇〇〇番目のボタンを押すといい」といっても、それだけでは悪いことには見えない。
- それでもクラックと言うなら暗に「ビットコインにおける SHA-256 のクラック」のようなものを表す。驚異的な速度で SHA-256 の処理をして出し抜く、のようなクラックの文脈が存在する。（冒頭のポストは、ビットコインは大丈夫か？ と捉えるのが自然ということです）
- 備考として、量子コンピュータでないと厳しい（量子コンピュータでなくてもいい方法はみんなやってるだろうから）。また、他人が取引を有効にしたのを盗み見ても無駄で、もし一時的に使えても気づかれてすぐに対策されてしまう。
以上で今回の記事は終わりになりますが、この内容を読んで少しでも計算機科学のことを知ってもらえればと思います。