楕円曲線論おまけの一歩

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。
楕円曲線論はじめの一歩 (14) - VIPPOOL開発者ブログ
では、それまで実数体で定義された楕円曲線の有理点について
考察してきたのに、さらっと有限体上に再定義しました。

ここに理論の飛躍があるというご意見を頂いたので、
今回はそこについて詳しく見ていこうと思います。

準同型の厳密な定義

楕円曲線論はじめの一歩 (12) - VIPPOOL開発者ブログ
で触れた「準同型」という言葉。これが今回の鍵になります。

ここで触れた内容を数式で書いてみましょう。
楕円曲線上の点 P と Q があって、P と複素数 w_1 、Q と  w_2 が対応しています。
つまり、楕円曲線上の点からなる群 E から複素数体 C に変換する写像(関数)、
E \stackrel{f}{\to} C があって、w_1=f(P)w_2=f(Q) なわけです。

で、楕円曲線上の加法演算 A(P,Q) と、複素数体上の加算 A'(w_1,w_2)=w_1+w_2 があって、
楕円曲線上で加算した結果に対応する複素数 f(A(P,Q)) と、
先に複素数に変換して加算した A'(w_1,w_2) が等しい、ということでした。

まとめて数式で書くと
f(A(P,Q))=A'(f(P),f(Q))
ということです。

図にするとわかりやすいでしょうか。

f:id:y-hoshizuki:20200313213759p:plain

このように、楕円曲線上の点から複素数への写像と、加算演算の順番を入れ替えることができる。
もっと一般化して、「写像と演算の順序を入れ替えることができる」
というのが、準同型という言葉の意味です。

射影平面と有理点の準同型性

まず、 x=\frac{X}{Z} などと置いて3次元にした射影平面の話を思い出してください。
有理点と射影平面上の像は準同型な関係になっています。

説明の簡略化のため、X 軸だけ見てみましょう。Y 軸も同様に考えられます。

射影平面上の X 座標 G から、楕円曲線上の有理点 E の X 座標への写像
G \stackrel{g}{\to} E を考えてみましょう。

g(X,Z)=\frac{X}{Z}
写像となる関数です。有理点だけ考えているので、必ず分数で書き表せるところがポイントです。

実数上で定義された E の座標を計算するときは普通に
加算は A(x_1,x_2)=x_1+x_2 、乗算は M(x_1,x_2)=x_1 \times x_2 です。
一方、G の場合は加算 A'(X_1,Z_1,X_2,Z_2)=(X_1 \times Z_2 + X_2 \times Z_1, Z_1 \times Z_2) と定義します。
普通に通分して足してるだけです。乗算はもっと簡単 M'(X_1,Z_1,X_2,Z_2)=(X_1 \times X_2, Z_1 \times Z_2) です。

射影平面と有限体の準同型性

こちらも同じく見ていきましょう。

射影平面上の X 座標 G から、有限体 F への写像
G \stackrel{g'}{\to} F を考えてみます。

g'(X,Z)=X \times Z^{-1} \bmod p
写像となる関数です。p が素数であれば、逆元 Z^{-1} \bmod p は必ず存在するのがポイントです。

G 上での加算乗算は前述の通りなので、対応する F での演算は、
加算が A''(x_1,x_2)=x_1+x_2 \bmod p で、乗算が M''(x_1,x_2)=x_1 \times x_2 \bmod p です。

実数体上で定義した楕円曲線上の点の群と、有限体上で定義した点の群の準同型性

以上のお話から、「有理数体と射影平面が準同型」「射影平面と有限体が準同型」ということが
わかりましたね。ということは、「有理数体と有限体は準同型」ということが言えそうですね。

まとめ

今回は、楕円曲線論の最後でさらっと流した部分を詳しく見てみました。
またわかりづらい点などありましたら、ご指摘いただければ解説いたしますので、
お気軽にご意見ご感想など頂ければと思います。

今回はここまで。

承認数って何?~暗号資産の安全性~ (2)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は、暗号資産の安全性を説明するために、攻撃者の役になり切って、
どうやって改ざんを行うかについて考えました。
そして、その方法を数学で説明できるモデルに落とし込むところまでお話しました。

今回は、このモデルについて解析して、どういう条件で攻撃が成功するのか考え、
その反対の条件を満たせば安全だ、というお話をします。

ランダムウォークモデルでゴールする確率

これは前回出したモデルです。

f:id:y-hoshizuki:20191220180026p:plain

ここで登場するのが、承認数です。このすごろくの出発点とします。
つまり、攻撃者がどのタイミングから攻撃を開始するか、
という数字なわけです。とりあえず z としておきましょう。

bitcoin の元論文でも言及されていますが、
確率過程の面倒な議論はすっ飛ばして結果だけ書くと、
 \sum_{k=0}^z \frac{(z\frac{p}{1-p})^k e^{-z\frac{p}{1-p}}}{k!} (1-(\frac{p}{1-p})^{z-k})
の確率で改ざん攻撃に失敗します。一般的に確率は 100% を 1 とするので、
1 からこの値を引けば、成功する確率になります。

計算めんどうですね。そんなときは、みんな大好き Wolfram|Alpha: Computational Intelligence で計算できます。
以下の数式を入力してみてください。

sum (z*p/(1-p))^k*e^(-z*p/(1-p))/k!*(1-(p/(1-p))^(z-k)), k=0 to z, where p=0.4, z=6

p=0.4、つまり攻撃者のハッシュレートが全体の 40%、
z=6、つまり承認数 6 の状態から追いかけっこを開始した場合、
0.49602。つまり 49.602% の確率で失敗します。
1 から引いて 0.50398、つまり 50.398% の確率で成功します。

最後の where 以降がパラメータです。いろいろ変えてみて試してみてください。

専用の計算機を公開してる人もいます。
https://people.xiph.org/~greg/attack_success.html
こちらは成功率をそのまま表示します。

さて、ここから何がわかるでしょう

この式を見て、何かを感じ取れる人はそうそう居ないと思いますので、
いろいろパラメータを変えて試してみましょう。

10% 30% 49.99% 50%
1 20.4% 62.7% 99.9% 100%
6 0.02% 13.2% 99.9% 100%
10 0.000012% 4.16% 99.9% 100%
144 ≒0 ≒0 99.8% 100%

承認数と、攻撃者のハッシュレートの割合を変えながら、攻撃の成功率を求めてみました。

お気づきになられたでしょうか。攻撃者のハッシュレートの割合が 50% になった瞬間、
承認数をいくら増やしても、成功率が 100% になるのです。

これが「51% 攻撃」の意味です。
「どれだけ承認数を確保しても必ず改ざんが成功する条件」、
それが、「ハッシュレートの割合の 50% 以上を占める」なのです。

じゃあ、承認数いくつなら安全なの?

今度はモナコインを受け取る側、攻撃される側に立ってみましょう。

  1. あなたは何かの商品を販売しています
  2. お客さんからモナコインで支払いを受けました
  3. さて、承認数いくつまで待てば安全でしょうか?

これは、bitcoin wikiConfirmation - Bitcoin Wiki ページにあるとおり、
ケースバイケースとしか言いようがありません。

例えば、100円の価値のものを販売したとして、
1% の確率で持ち逃げされる可能性は高いと感じますか?低いと感じますか?
そのためにわざわざ何承認も待つより、いっそ 0 承認でも、
他のお客さんの接客をした方が利益になりませんか?

例えば、1億円の価値にあるものを販売したとして、
0.1% の確率で持ち逃げされる可能性は、高いと感じますか?低いと感じますか?
どこまで攻撃成功率が下がるまで待てば安心できますか?

これはそういう話になります。

また別の観点もあります。

攻撃用のハッシュレートを高めるにはそれなりの機材と電気代がかかります。
100円の価値のものを持ち逃げするために、数万、数十万と機材や電気代をかけますか?

昔から付き合いのある会社で、これからも付き合いがある可能性の高い取引先が、
高い費用と信用を失ってまで改ざんすると思えますか?

そういうことを総合的に見て、安全と思える承認数を決めてね、と bitcoin wiki には書いてあります。

適切に承認数を決めれば、通貨として安全に使えますよ、というのが、暗号資産の安全性の本質です。

まとめ

今回は、前回のランダムウォークモデルから攻撃成功率を計算して、
その意味や、承認数についてお話ししました。

承認数を適切に決めることで、安全性と利便性のバランスの取れた運用をするのが本来あるべき姿です。
また、51% 攻撃の意味についても少し触れました。正確な認識がもっと広まると嬉しいです。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

承認数って何?~暗号資産の安全性~ (1)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

今回はモナコインなどを送金する際に表示される「承認数」について、
また、これに関連して、どうして暗号資産が安全と言われるのか、
その辺りについてお話したいと思います。

また、世間で若干誤認されがちな、51% 攻撃についても少し触れたいと思います。

攻撃者を想定してみる

暗号の世界で「安全かどうか」を考えるときには、「攻撃者」を想定することが大事です。

というわけで、以下のシナリオを想定してみましょう。

  1. あなたはモナコインでお買い物をします
  2. その商品の価格は 1.0 MONA でした
  3. あなたは 1.0 MONA を送金し、商品を手に入れました
  4. はい、ここで 1.0 MONA の送金をなかったことにしましょう

これが、暗号資産の想定する「攻撃者」です。
あなたがこの立場になるとしたら、どんなやり方を思いつきますか?

一番に思いつきそうなのは、そう、ブロックチェーンの履歴の改ざんです。
履歴の改ざんをする方法について考えてみましょう。

ブロックチェーンの履歴の改ざん方法

ブロックチェーンは、おおむね一定時間ごとに新しいブロックを付けたしながら
伸びていきます。そして、複数のマイナーがいるため、ブロックのチェーンが分岐する
場合があります。

f:id:y-hoshizuki:20200106150903p:plain

この場合、しばらく様子を見て、ブロックの累積 difficulty が多い方のチェーンは、
それだけ多くの計算資源が投入されている、つまり、正当なノードが集まっている証拠。信用できる。
というわけで、短い方を切り捨てて、全員で長い方に集まるルールで動いています。

これこそ、PoW の根幹を成しているルールです。

ということは、このルールに背くマイナーがいれば、安全の根拠が崩れる、つまり改ざんに成功します。

f:id:y-hoshizuki:20200106150450p:plain

このように、累積 difficulty の大きいチェーンを無視して、1.0 MONA の支払いがなかった歴史のチェーンを
掘り続けるマイナーがいれば、まずは第一段階クリアです。

でも、この歴史のチェーンは、他の正当なノードから見ると「最長のものより短い」チェーンなので、
累積 difficulty はどうしても少なめになりがちです。そのため、このチェーンは無視されてなかったことにされます。

ではどうするか。

f:id:y-hoshizuki:20200106150523p:plain

このように、一瞬でもいいから、正当なチェーンよりも長く伸ばすことを目標にします。
累積 difficulty なので、長ければ長いほど、大きくなる傾向があるため、長さは重要なファクターです。
すると、他の正当なノードも、ルールにのっとって、この改ざんされた歴史が正しいものとしてマイニングを始めます。

これで、あなたの支払いはなかったことになり、でも商品は受け取った後なので、
両取りの状態、つまり商品をだまし取ることに成功するわけです。
つまり攻撃者は、一瞬でいいからこの状態になることを目標にします。

要約すると、「正当なチェーンと延長の追いかけっこをして、一瞬でも追い抜けば勝ち」というゲームです。

「ブロック延長の追いかけっこ」を「ランダムウォークモデル」で表す

さて、じゃぁどうすれば正当なノードよりも伸ばすことができるのでしょうか?

それを考察するために、数学的に扱うことができるモデルに落とし込みます。

まずは前提として、モナコインのマイナー全員の総ハッシュレート(演算能力)を 100 % として、
攻撃者側のハッシュレートが p % あると仮定します。

すると、正当な歴史のチェーンは、一定時間おきに 100-p % の確率で 1 ブロック伸びます。
反対に、改ざんされた歴史のチェーンは、一定時間おきに p % の確率で 1 ブロック伸びます。

この追いかけっこは、改ざんされた歴史のチェーンのブロック高(長さ)を基準点、0 として、
正当な歴史のチェーンのブロック高を相対値でみたとき、
以下のような状態遷移のモデルで数学的に表すことができます。

f:id:y-hoshizuki:20191220180026p:plain

これは、数学の世界では「ランダムウォークモデル」と呼ばれて、確率過程という分野で扱います。

すごろくのように、今の状態の位置にコマを置いて、確率に従ってコマを移動していくイメージです。
矢印についている確率が、その状態遷移が発生する確率です。

この図で、0 の位置が、正当な歴史と改ざんされた歴史のチェーンの長さがそろっている状態です。
1 は、改ざんされた歴史のチェーンが 1 ブロック短い状態です。
同様に、2 は、改ざんされた歴史のチェーンが 2 ブロック短い状態です。
反対に、-1 は改ざんされた歴史のチェーンの方が、正当な歴史のチェーンより 1 長い状態です。

つまり、-1 の状態に 1 度でも踏み込むことができれば、攻撃者の勝ちになります。

ちなみに、この図の子は、執筆者、星月が趣味で発注したイメージキャラです。
株式会社 VIPPOOL とは何の関係もないですが、図面がいつもフリー素材では味気ないので、
これからもたまに顔を出してもらう予定です。

まとめ

今回は、暗号資産の安全性を説明するために、攻撃者の役になり切って、
どうやって改ざんを行うかについて考えました。
そして、その方法を数学で説明できるモデルに落とし込むところまでお話しました。

次回は、このモデルについて解析して、どういう条件で攻撃が成功するのか考え、
その反対の条件を満たせば安全だ、というストーリーでお話します。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

量子コンピュータとモナコイン (2)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は、量子コンピュータについて基本的なお話と、
モナコインの公開鍵から、秘密鍵を計算できてしまう。
というお話をしました。
今回はその対策について考えてみましょう。

マイニングについて

まずは PoW の根幹をなしているハッシュ関数
これについては、量子コンピュータでも効率的な計算方法は見つかっていません。

つまり、量子コンピュータが実用化されても、データの改ざんは簡単にはできないことを意味します。

まずはブロックチェインとしての基礎は大丈夫そうですね。

送金について

次に、問題となる秘密鍵が計算できてしまう問題について、
こちらは、もう使っている人はいないと思いますが、
P2PK で送金してはいけません。

f:id:y-hoshizuki:20190912153531p:plain

このように、scriptPubKey に、公開鍵 xG が書かれているので、
ここから秘密鍵 x を計算して資産を盗まれてしまいます。

今、主流となっている P2PKH だとどうでしょう?

f:id:y-hoshizuki:20190912153554p:plain

scriptPubKey に書かれているのは、公開鍵のハッシュ、
ripemd160(sha256(xG)) です。ripemd160 も sha256 も、
量子コンピュータで逆算する効率のいい方法はまだ見つかっていません。
つまり、これなら安全。

……と思うでしょう?

f:id:y-hoshizuki:20190912153605p:plain

P2PKH は、UTXO をアンロックするときに公開鍵 xG を scriptSig に書いてしまうんですよね。

ということは……?

f:id:y-hoshizuki:20190912153617p:plain

そう、UTXO をそのままアンロックすることはできないけれども、
同じコインアドレスを使っている UTXO があれば、そちらをアンロックすることは
できてしまうのです。

つまり、
秘密鍵(コインアドレス)は使い捨て
・必ず毎回、すべての UTXO を使い切るように運用する
必要があります。

f:id:y-hoshizuki:20190912153630p:plain

さて、これで大丈夫でしょうか?

ところが、モナコインを含む暗号資産には、
「承認数」=「ブロックチェインに取り込まれてから掘られたブロックの高さ」
が増えるほどにトランザクションの改ざんが難しくなる。
という特徴があります。

言い換えれば、承認数が少なければ、例えば承認直後であれば、
トランザクションの改ざんは簡単に行うことができます。
つまり...

f:id:y-hoshizuki:20190926153349p:plain

このように、攻撃対象のアカウントから送金が行われたことを見つけ次第、
量子コンピュータ秘密鍵を割り出し、その秘密鍵で自分宛てに送金。
そしてそのトランザクションを含ませたブロックチェインを伸ばせば、
暗号資産を奪取することができてしまいます。

一度、元のチェインを追い越してしまえば、そちらが分岐と判断され破棄されます。
そして暗号資産を奪った方のチェインが正式なものとして扱われるようになります。

残念ながらこの対策は、現状できません。

まとめ

今回は、量子コンピュータが実用化された後、
どうすればモナコインを安全に使い続ける方法について考察しました。

P2PK でも P2PKH でも、暗号資産を奪われてしまいます。これは大変。

実用化が近くなれば、また BIP などで改善されることでしょう。
それに、256bit の楕円曲線暗号の計算ができるには、
まだまだ時間がかかりそうですので、しばらくは安心してもいいと思います。

米国 NIST の公開している資料 SP800-57 でも、量子コンピュータの実用化まで
含めて検討した上で、楕円曲線暗号 256bit は、2030 年以降も安心して使えると報告されています。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

量子コンピュータとモナコイン (1)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回、楕円曲線暗号の強さについてお話ししたところ、
Twitter で以下のコメントを見かけました。
量子コンピューターに対抗できそうなmonacoin」

ところが、残念ながら、モナコインは量子コンピュータに対しては、
完全に太刀打ちできません。残念ながら対策もありません。
今回はそういうお話をしようかと思います。

量子コンピュータの仕組み

まずは量子コンピュータがどういうものか。
というところから説明いたしましょう。

いわゆる普通のコンピュータは、FF (フリップフロップ) や、
キャパシタコンデンサ)の充電・放電を使って、0 と 1 のどちらかの状態を記憶しています。
これを 1 bit という単位で扱います。

FF をたくさん集めたものは SRAM と呼ばれ、CPU のレジスタやキャッシュに使われています。
コンデンサをたくさん集めたものは DRAM と呼ばれ、
PC のメインメモリや GPU のメモリに使われています。DDR4-SDRAM とか言われるものの後ろ4文字です。

一方、量子コンピュータは、「1 である確率が x%(つまり 0 である確率が 100-x%)」
という素子を使って計算します。これを 1 qubit という単位で扱います。

例えば普通のコンピュータでいうビット反転。1 qubit の計算で 1-a を計算してみると、
その出力結果は「1 である確率が 100-x%(つまり 0 である確率が x%)」となり、
その qubit を観測すると、100-x% の確率で 1 を観測でき、x% の確率で 0 を観測できます。

なんじゃそりゃ。と思われるかも知れませんが、こういうシステムを構築すると、
色々な計算がすごく効率的に計算できてしまうのです。不思議ですね。

まずはその例を見てみましょう。

量子コンピュータ素因数分解をしてみる

RSA 暗号では、2 つの大きな素数 p, q を用意して、その合成数 N = pq を公開鍵とします。
p, q が十分に大きければ、N の素因数分解は現行のコンピュータでは非常に難しいので、
公開してしまっても問題ない、ということです。

ところが、これは量子コンピュータを使うと効率的に解けてしまいます。

十分な数の qubit を並べて、p', q' と名付けましょう。量子ゲートと呼ばれる素子で計算を行います。
p'×q' を計算して、その結果が N と一致したときに p' と q' を観測しましょうか。
……この方法ではダメです。これではまだ従来のコンピュータの考えから抜け出せていません。

なぜなら、p' も q' も p'×q' の計算結果も、観測する時点で、各 qubit それぞれが、
それ自身の持つ確率で 0 か 1 かに収束するので、p' の観測結果と q' の観測結果を掛け算しても、
p'×q' の観測結果と一致する確率は qubit 数が増えるほど、0 に近くなります。
これでは話になりません。

じゃぁどうするのか。
ここで出てくるのが、有限巡回群の位数を求めるアルゴリズムです。
詳しい説明は量子力学の知識が必要になるため割愛しますが、
量子コンピュータは、有限巡回群の位数を求めるのが得意です。
なので、素因数分解の問題を、有限巡回群の位数を求める問題に帰着させます。

まず、N より小さな正の数 a をランダムに決めます。
十分な数の qubit を並べて、{ a^x \bmod N } という有限巡回群を作ります。
そうすると、この有限巡回群の位数φは、量子コンピュータなら簡単に計算できます。
オイラーの公式により、a^{(p-1)(q-1)} \bmod N=1 が成り立つため、
\phi = (p-1)(q-1) となります。p, q は大きな素数なので、2 は使いません。なので、
p も q も奇数ですので、p-1 も q-1 も偶数となります。というわけで、b=a^{\frac{\phi}{2}} \bmod N とします。
すると、b^2 \bmod N=1 となるので、b^2-1 \bmod N=0 です。
左辺を因数分解すると (b+1)(b-1) \bmod N=0 ですので、b+1 も b-1 も N と共通の約数を含みます。
なので、b+1 と N、b-1 と N の最大公約数を求めると(これは従来のコンピュータで効率的に計算できます)、
N の約数である p, q が計算できる。……という流れです。

これを、Shor のアルゴリズムと呼びます。

楕円曲線暗号量子コンピュータで解いてみる

楕円曲線暗号は、楕円曲線上のベースポイントとなる点 G は公開されていて、
秘密の値 x 倍した P=xG を公開鍵として使います。

以前、このブログでも紹介した通り、楕円曲線上の点のなす群は有限巡回群となっています。
参考:https://blog.vippool.net/entry/2019/04/08/125519

量子コンピュータは、有限巡回群で aG-bP=O となる a, b の組み合わせを求めるのも得意です。
ちなみに、ここで、P=O とすると、aG=O となり、G が生成する有限巡回群の位数を求める問題に
帰着することに注目してください。そう、素因数分解で使ったやつです。

さて、この式を aG-bP=aG-bxG=(a-bx)G と式変形すると、(a-bx)G=O となります。
一般的に使われている楕円曲線は、ベースポイントとその位数が公開されているので、
位数を n とすると、a-bx \bmod n=0 となります。
これを x について解くと、x=ab^{-1} \bmod n と解けます。
ここで、-1 乗は n を法とする逆元の意味です。

量子コンピュータはこの a, b を求めるのは得意で、
そこから x を求めるのは、現行のコンピュータでも、
拡張ユークリッドの互除法というアルゴリズムで効率的に計算できます。

モナコインで使われている ECDSA の公開鍵も、
secp256k1 という楕円曲線上でのベースポイント G の、
秘密鍵 x 倍、つまり xG を公開鍵としているため、
量子コンピュータがあれば、モナコインの公開鍵から秘密鍵を計算することができてしまいます。

これは困りました。
というわけで、次回はその対策について考察しようと思います。

まとめ

今回は、量子コンピュータの仕組みと、その応用の仕方。
そして、モナコインが危ない!というお話をしました。

次回はその解決策について考察します。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

楕円曲線暗号って何がすごいの?

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

今回は、bitcoin や monacoin など、主要な暗号資産で使われている、
楕円曲線暗号について、少しお話ししようと思います。

みなさんは、楕円曲線暗号についてどのように感じていますか?
「なんかよくわからないけど強そう」「普通の暗号より強いって聞いた」
そんな感じの印象を持っている方に、読んでいただきたい記事です。

暗号技術概論

暗号には、暗号化と復号で同じ鍵を使う対称鍵暗号(共通鍵暗号)と、
双方で異なる鍵を使う非対称鍵暗号の二種類があります。

共通鍵暗号としては、有名なところでは AES, 3DES などがあります。
非対称鍵暗号と比べると、「共通で使う鍵をどうやって安全に共有するか」
という問題があるものの、非常に演算が軽い、というメリットがあり、
現在でもよくつかわれています。

一方、非対称鍵暗号は、鍵が二種類存在するもののことで、
演算が重いというデメリットがありますが、
鍵を共有する手間がないというメリットを生かして、ただの暗号化以外にも、
電子署名などの応用がされています。暗号資産で使われているのも、
この電子署名の技術です。

旧世代の非対称鍵暗号

非対称鍵暗号では、ほとんどのものは離散対数問題が困難な有限巡回群を使います。
有限巡回群や、離散対数問題については、以前このブログで解説いたしましたので、
詳しくはそちらをご覧ください。

さて、かつて、非対称鍵暗号が実用化された時には、有限体乗法群が使われていました。
有限体 F(p) や、その拡大体 F(p^n) での演算、
y=b^x で、体のパラメータ p, n, b をパラメータとして公開し、
x を秘密鍵、y を公開鍵とする方法です。x と、パラメータの p, n, b から、
y を計算するのは簡単ですが、y とパラメータから x を計算するのは非常に難しい、と。

楕円曲線暗号の登場

ところが、この技術が普及するにつれて、y から x を計算する手法について、
様々な研究が行われてきました。現在では、それなりに効率のよい手法が発見されています。
そこで登場するのが、楕円曲線上の群です。
既存の暗号アルゴリズムで使っていた有限体乗法群を、そっくりそのまま、
楕円曲線上の群に入れ替えたものが作られました。

例えば、DH 鍵交換アルゴリズム楕円曲線バージョン、ECDH や、
ElGamal 暗号の楕円局背バージョン、EC-ElGamal、
DSA の楕円曲線バージョン ECDSA などです。

これらが、いわゆる楕円曲線暗号です。
暗号資産では、ECDSA を使用しているものが多いです。

楕円曲線暗号の強さ

各種暗号アルゴリズムの強さについては、米国の NIST という組織が調査しています。
今回は、そこの公開している SP800-57 という文書から引用してきます。

f:id:y-hoshizuki:20190814190653p:plain

この表で、左端が暗号の強度、AES を基準に何ビット相当の強さなのかを示した数字です。
真ん中の FFC が、有限体乗法群を用いた暗号で、L がいわゆる鍵長です。
また、ECC楕円曲線暗号で、f が鍵長です。

これを見るとわかる通り、有限体乗法群の 1024bit が、楕円曲線暗号の 160-223bit と同様で、
AES の 80bit 程度の強度というわけで、つまり「同じ強度で比べたら短いビット数で済む」
ということを示しています。

ただ、これは実は単純に楕円曲線の演算が重いため、総当たりにかかる時間が長い、という
ことを示しているだけで、「暗号として強い」ではなく「計算が重い」ことを示しているに過ぎません。

では、どこが強いのか。
この表をグラフにしてみてみましょう。

f:id:y-hoshizuki:20190814190711p:plain

横軸(上)が楕円曲線暗号の鍵長で、横軸(下)が有限体乗法群の鍵長です。縦軸が暗号の強さです。

これを見るとわかる通り、楕円曲線暗号は、暗号強度と鍵長が比例するように伸びていきますが、
有限体乗法群では、だんだん上がり方が鈍くなっています。
これこそが、「効率的な解き方が発見された」ということであり、
まだそれが見つかっていない楕円曲線暗号が強いと呼ばれる所以です。

つまり、今後、コンピュータの技術が進歩して計算能力が高くなっていくとします。
そうすると、当然、それに合わせて安全とされる暗号強度も高くなるわけですが、
楕円曲線暗号では比例して鍵長を伸ばせば済みますが、有限体乗法群では、すごい勢いで
鍵長を増やす必要があります。

例えば、先ほどの表に戻って、暗号強度 256bit 相当の強度が必要な時代になったとき、
楕円曲線暗号では鍵長 512bit で済みますが、有限体乗法群でその強度を実現するには、
15360bit もの長さが必要になるということです。

どうでしょう?これが、楕円曲線暗号が「強い」と言われる意味です。

まとめ

今回は、楕円曲線暗号が「強い」と言われる理由について、
簡単にお話ししました。

ただ単に、短い鍵長で同じ強度、という単純な話ではなく、
将来を見据えたときに安全性の高いものだ、というところを、
しっかりと押さえていただければと思います。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

VIPPOOL storage の紹介

今回のおはなし

みなさんこんにちは。
VIPPOOL でエンジニアをやっています、星月です。

株式会社 VIPPOOL は、3 月に OSS として VIPPOOL clerk/storage の
2 製品をリリースしましたが、今回はそのうちの 1 つ、使い方が簡単な方、
VIPPOOL storage の紹介をしたいと思います。

VIPPOOL storage とは

VIPPOOL storage とは、VIPPOOL がクラウドで運用しているサービス、
VIPPOOL clerk に Python から簡単にアクセスできるための Python ライブラリです。

VIPPOOL clerk へアクセスするだけのラッパーなので、できることはそれに準じますが、
電子署名作成の機能も実装していますので、新規トランザクション作成が
メソッド呼び出し一発で済むところがポイントです。

また、VIPPOOL clerk が秘密鍵をアップロードすることなくトランザクション
作成する機能を持つため、秘密鍵の漏洩の心配なく送金やデータの書き込みが行えます。

...などと説明してもわかりづらいと思いますので、
実際に使ってみましょう。

VIPPOOL storage をインストールする

PyPI に登録してありますので、インストールはコマンド一発、

$ python -m pip install vippool_storage

です。

初期設定等は特に不要です。

VIPPOOL storage を使ってみる ~ウォレットとして~

まずは秘密鍵を作りましょう。

$ python3
>>> from vippool.storage import vippool_storage
>>> w = vippool_storage( coind_type = 'monacoind_test' )
>>> print( w.privKey() )
363312610E6224A0DB04E9D3BCDCF72A1AC24CC6BFEEEF9EEB3766DD7CCD0B11
>>> print( w.address() )
mmSM1sFdMUBqPkGUPQPs72zXcXxJgrfY3g
>>> print( w.balance() )
None

今回はテストネットで試しているので coind_type = 'monacoind_test' と書いてますが、
メインネットでやる場合は省略できます。coind_type = 'monacoind' と書いても OK です。

最初に表示された HEX が秘密鍵です。その次にコインアドレスを表示しています。
まだ使われたことのないアドレスなので残高は None が返ってきています。
このアドレスにモナを送金してから続きを試します。

まずは以下の 2 行だけのファイルを作ります。ファイル名は wallet.py にでもしましょうか。

from vippool.storage import vippool_storage
w = vippool_storage( coind_type = 'monacoind_test', privKey = '363312610E6224A0DB04E9D3BCDCF72A1AC24CC6BFEEEF9EEB3766DD7CCD0B11' )

privKey は先ほど表示されたものをそのままコピペします。

$ python3
>>> from wallet import w
>>> print( w.balance() )
429.637

はい、残高がちゃんと見れますね。

送金してみましょう。

$ python3
>>> from wallet import w
>>> w.send( 'mt5xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx', 1, 0.001 )
'b25c6d563dbd6f9a7bf021a247dc8b218a92a56563ddcc26690b55c1f53d49e7'
>>> print( w.balance() )
428.636

1 tMONA を手数料 0.001 tMONA で送金しています。第一引数は送金先のアドレスです。
そうすると送金トランザクションの ID が返ってきます。しばらく待ってから残高を確認すると
ちゃんと送金額と手数料が減っていますね。

この時、秘密鍵はローカルの VIPPOOL storage ライブラリ内で電子署名作成に使うだけで、
サーバに送らずに送金を完結できるところがポイントです。流出を心配する必要がないわけです。

あとはこれに適当な UI をかぶせればウォレットアプリの完成です。
簡単ですね!

VIPPOOL storage を使ってみる ~ブロックチェーンライタ・リーダとして~

名前の由来としては、こちらの用途が先にありました。
送金機能はあくまでおまけです。

さて、それでは先ほどと同じように wallet.py を作ります。

$ python3
>>> from wallet import w
>>> print( w.balance() )
428.636
>>> print( w.write( b'ABCDEFG', 0.001 ) )
7eb74a8d2e85da3c971f7ee63cf2a2e284f2dd6350d4c57ce1a7e49b852e295e
>>> print( w.read( '7eb74a8d2e85da3c971f7ee63cf2a2e284f2dd6350d4c57ce1a7e49b852e295e' ) )
None
>>> print( w.read( '7eb74a8d2e85da3c971f7ee63cf2a2e284f2dd6350d4c57ce1a7e49b852e295e' ) )
b'ABCDEFG'

残高が残っていることを確認して、write メソッドでデータを書いてみます。
手数料は 0.001 tMONA です。帰ってきた TXID を引数にしばらく承認を待つと、
read メソッドで読めるようになります。

このデータはブロックチェーン上に記録されているため、
メインネットに書いたものはそう簡単には改ざんできません。

これに適当な UI をかぶせれば何か素敵なサービスが作れそうな気がしませんか?

何か作られた方はぜひ、開発チームまで教えていただけると、
今後のやる気になりますので、よろしくお願いします。

それでは、今回はこの辺で。