Develop with pleasure!

福岡でCloudとかBlockchainとか。

自称サトシになる方法

最近また自称サトシが登場してるみたいだったので、自称サトシになるために必要なことを調べてみた。

ecdsa - If someone wanted to pretend to be Satoshi by posting a fake signature to defraud people how could they? - Bitcoin Stack Exchange

自称サトシになるには?

BitcoinGenesis Block↓のコインを移動することができれば、それは自称ではなく間違いなく本物のサトシだが、

https://en.bitcoin.it/wiki/Genesis_block

自称サトシが証明として提供しているのは、Genesis Blockのコインの送金先である公開鍵

04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f

に対して有効な署名。この有効な署名を作ることができるのは、対応する秘密鍵を知るサトシ本人であるというもの。

一見正しい論理に思えるが提供しているデータにトリックがある。まず、正しいECDSA署名についておさらいしておこう。

ECDSA署名の作成と検証

定義にあたって、以下の表記を使用する。

署名の作成

秘密鍵xとメッセージmを使って署名を作成する場合、手順をざっくり書くと以下のようになる。(他にも諸々細かい注意点はあるので詳細はRFCなど参照)

  1. ランダムな値kを選択する。
  2. R = kGを計算し、Rのx座標をrとする。
  3.  {s = \frac{H(m) + r \cdot x}{k}}を計算する。
  4. 計算してできた(r, s)が有効なECDSA署名。

署名の検証

検証者は署名(r, s)、メッセージm、公開鍵Pが与えられた状況で、以下を検証する。

  1. H(m)を計算する。
  2.  {\frac{H(m)}{s}G + \frac{r}{s}P}を計算し、算出した点のx座標がRと等しいか検証する。

自称サトシの証明の作り方

自称サトシも上記ECDSA署名(r, s)を提供しているわけだが、ここにトリックがあり上記のようなプロセスを経て作られたデータではないと思われる。どういうことかというと(r, s)とH(m)は提供しているが、m自体は提供していない。

メッセージのハッシュ値を計算する部分は、ECDSAのアルゴリズム上、必要不可欠な重要なパートであり、署名を検証する検証者は、署名対象のメッセージのハッシュを必ず自身で計算しなければならない。そうでない場合、ECDSAの安全性は保持されず、偽造が可能になる。

具体的にどういう不正ができるかとというと、以下のようにして(r, s)を計算できる。

  1. ランダムな値aとbを選択する。
  2. R = aG + bPとなるRを計算し、Rのx座標をrとする。
  3. メッセージのハッシュをH(m)を {r \cdot \frac{a}{b}}とする。
  4.  {s = \frac{r}{b}}とする。
  5. 上記(r, s)を署名とする。

これを検証するととうなるかというと、

 {\frac{H(m)}{s}G + \frac{r}{s}P =  \frac{r \cdot \frac{a}{b}}{s}G + \frac{r}{s}P = r \cdot \frac{a}{b} \cdot \frac{b}{r}G + r \cdot \frac{b}{r}P = aG + bP}

となり、R = aG + bPと等しくなり有効な署名として検証される。

このようなことで偽の署名を有効と認識しないためにも、検証者は必ずメッセージmからハッシュ値を計算し、その値を持って署名の検証をする必要がある。

今回の自称サトシが提供したのはあくまで、(r, s)とH(m)なので、これは上記のようにサトシの証明にはならない。また、ハッシュ値 {r \cdot \frac{a}{b}}となるようなプリイメージを見つけることができないかぎり、ECDSAの安全性自体を破るものでもない。

一応、しばらくしたら内容(プリイメージ)を明かすと発言しているので楽しみにしておきたい。