狙った公開鍵から秘密鍵[本物]を奪取
ショアのアルゴリズム

ショアのアルゴリズムとは？

ショアのアルゴリズム（Shor’s Algorithm）は量子コンピュータ上で動作する特殊なアルゴリズムでRSAやECDSAといった従来の公開鍵暗号を破る力を持ちます。

何が「危険」なのか？

従来の暗号は、次のような「逆に解くのが非常に難しい問題」に安全性を依存しています。

• RSA暗号 → 大きな整数の素因数分解
• ECDSA（楕円曲線暗号） → 離散対数問題

これらの問題は、現在のスーパーコンピュータでも解くのに数千年～数億年はかかるとされています。しかし、ショアのアルゴリズムは量子コンピュータを使うことでこれらを指数関数的に高速化。すなわち、古典では得ることができない周期を求めてしまうので短時間で解いてしまうのです。

公開鍵があれば、秘密鍵も出る

ショアのアルゴリズムが最も恐れられている理由はここにあります。一度でも「公開鍵」を出せば、それだけで秘密鍵を逆算できてしまう。つまり、以下のような状況が現実になります。

• 古い「使用済み」トランザクションに署名が残っている場合、そこに公開鍵もあります。
  → その公開鍵から秘密鍵が量子で逆算される
  → もしその公開鍵によってロックされた残高が他に未使用トランザクションとして存在する場合、そのトランザクションのロックを破った秘密鍵で署名することでそこにある資産が奪われる。

ただし、ショアのアルゴリズムは非常に高度なエンタングルメントが求められ難しい

量子演算の中でも特にその維持が難しいとされるエンタングルメント。量子もつれですね。

ショアのアルゴリズムでは、秘密鍵を導出する手掛かりとなる周期という解をこのエンタングルメントで結び付けておく必要があるのでこれが途中で崩れると、それだけで正しい解が取り出せなくなります。

それなら大丈夫……？

いいえ。そうとはなりません。なぜならブロックチェーンの秘密鍵を奪取するのが目的であるのならショアのアルゴリズムなんて使いません。つまり、公開鍵をみるのではなく……別の場所をみるのです。よって他にも手法がたくさんあるということです。