狙った公開鍵から秘密鍵[本物]を奪取
ショアのアルゴリズム
目次 [INDEX]
ショアのアルゴリズムとは？
ショアのアルゴリズム（Shor’s Algorithm）は、量子コンピュータ上で動作する特殊なアルゴリズムで、RSAやECDSAといった従来の公開鍵暗号を破る力を持ちます。
何が「危険」なのか？
従来の暗号は、次のような「逆に解くのが非常に難しい問題」に安全性を依存しています。
- RSA暗号 → 大きな整数の素因数分解
- ECDSA（楕円曲線暗号） → 離散対数問題
これらの問題は、現在のスーパーコンピュータでも解くのに数千年～数億年はかかるとされています。しかし、ショアのアルゴリズムは、量子コンピュータを使うことで、これらを指数関数的に高速化、すなわち、古典では得ることができない周期を求めてしまうので、短時間で解いてしまうのです。
公開鍵があれば、秘密鍵も出る
ショアのアルゴリズムが最も恐れられている理由はここにあります。
一度でも「公開鍵」を出せば、それだけで秘密鍵を逆算できてしまうつまり、以下のような状況が現実になります。
- 古い「使用済み」トランザクションに署名が残っている場合、そこに公開鍵もあります。
→ その公開鍵から秘密鍵が量子で逆算される
→ もしその公開鍵によってロックされた残高が、他に未使用トランザクションとして存在する場合、そのトランザクションのロックを破った秘密鍵で署名することで、そこにある資産が奪われる
ただし、ショアのアルゴリズムは非常に高度なエンタングルメントが求められ難しい
量子演算の中でも特にその維持が難しいとされるエンタングルメント。量子もつれですね。
ショアのアルゴリズムでは、秘密鍵を導出する手掛かりとなる周期という解を、このエンタングルメントで結び付けておく必要があるので、これが途中で崩れると、それだけで正しい解が取り出せなくなります。よって、これが「ブロックチェーンにとって量子による身近な脅威」かと言われれば、それには疑問符が浮かびます。
でも、それならブロックチェーンで量子など気にする必要ない？ いいえ、やはり「あれ」を持ってましたね。
いいえ。それなら大丈夫……とは、なりません。
なぜなら、ブロックチェーンの秘密鍵を奪取するのが目的であるのなら、ショアのアルゴリズムなんて使いません。つまり、公開鍵をみるのではなく……別の場所をみるのです。それが、以下のような「秘密鍵ラグ構造」となっております。