量子コンピュータとモナコイン (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 をかぶせれば何か素敵なサービスが作れそうな気がしませんか?

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

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

株式会社 VIPPOOL の事業紹介

今回のおはなし

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

今回はちょっと技術から離れて、株式会社 VIPPOOL がどんなことを
やっているのか、やろうとしているのか、お話ししたいと思います。

事業計画概要

株式会社 VIPPOOL は、株式会社 AXELL が 100% 株を持っている、
完全子会社です。なので、VIPPOOL の事業計画は、
親会社である AXELL が、AXELL の株主向けに色々と開示しています。

今回はその資料をベースに見ていきます。

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

まずはこれが、AXELL がその株主向けに開示している情報のページです。
https://www.axell.co.jp/ir/pdf/AXELL_IR20190509_2.pdf
この p.26 が VIPPOOL のページとなっています。

個々の事業について

まずは絶対に忘れてはならない、マイニングプール事業。
VIPPOOL ユーザの皆様ならば、今さら語るまでもないでしょう。
VIPPOOL の起源とも言える事業です。これは先日、個人から株式会社 VIPPOOL へ、
運営が移管されまして、現在も運営を継続しています。

そこから派生して、マイニングハードウェアの開発も進んでいます。
親会社 AXELL の持つ、回路設計・基板設計の技術を融合させて、
既存のものよりもより効率的なマイニングハードウェア(FPGA/ASIC)の
開発を進めております。こちらもいずれ、進捗を報告できる日が来ると思います。

マイニングハードウェアを開発したら、自社でマイニングして利益を得る計画もありますが、
そのハードウェアを販売することも、視野に入れて事業計画としています。

ASIC や FPGA の方が、GPU や CPU よりも電力パフォーマンスなどが良いのは当然ですが、
既存のものよりも使い勝手よく、安心して使用できる製品を開発することで、
健全なマイニング環境を形成し、ひいてはブロックチェーンの信頼性を高めることに
つながれば、とても良いのではないかと考えています。

また、資料では「分離型ウォレット」と書いてありますが、
これは要するにハードウェアウォレットのことです。
安心してモナコインを保有するには、やはりハードウェアウォレットが一番です。

既に市場には何種類ものハードウェアウォレットが流通しており、
国産のものも少しずつですが出てきているようです。
親会社 AXELL の持つ基板設計技術により、他社のものより信頼性の高いものを提供できるよう、
またモナコイン黎明期から運営を続けてきた「VIPPOOL」のブランドで、
みなさまに安心してご利用いただけるよう、開発を進めております。

この中のいずれも、企業様相手の B2B、一般ユーザ様への普及を目指した B2C、
どちらも視野に入れて販売の計画を練っていますので、みなさまどうぞご期待ください。

現状これ以上詳しいことはお話しできませんが、
親会社 AXELL の方から IR が出てき次第、こちらのブログや Twitter などで、
随時進捗をお知らせできればと思っています。

それでは今回はこの辺で。
今後とも、株式会社 VIPPOOL をどうぞよろしくお願いいたします。

楕円曲線論はじめの一歩 (14)

今回のおはなし

みなさんこんにちは。

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

前回は、楕円曲線上の有理点がなす群が、有限巡回群である、というお話をしました。

楕円曲線論」としてはこのくらいにしておいて、
そろそろ「楕円曲線暗号」に応用していくお話をして、
この連載を〆ようかと思います。

有限体上で定義される楕円曲線

これまで、楕円曲線は暗黙のうちに実数上で定義して、
その中の有理点について見てきました。

つまり、x 座標、y 座標ともに実数で考えれば、グラフに滑らかな曲線を描けるし、
その中で x 座標と y 座標がともに有理数になる点についてのみ考えてきたわけです。

これまでの知見を楕円曲線暗号として活用しようとすると、
コンピュータでは真の意味での実数は扱えないし、
有理数は桁が無限に必要という問題があります。

そこで、有限体上で楕円曲線を定義することを考えます。

有限体で定義した楕円曲線なら、扱う数は全て有限体の元なので、
固定長の自然数(ここでは 0 を含む)として扱えるため、
コンピュータで計算するにはうってつけなのです。

楕円曲線を有限体上で定義する」とはどういうことでしょうか。

楕円曲線の定義は y^2=x^3+ax+b の形の方程式でした。
「ここで出てくる全ての係数、変数が、有限体の元であるとする」
というわけです。

例えば、y は有限体の元なので、y^2 は、
有限体の位数を p としたとき、y^2 \bmod p で計算します。
a も x も有限体の元なので、axax \bmod p で計算します。

これならコンピュータで扱いやすそうですね。

で、今まで有理点にこだわってきた理由ですが、
実は、実数上で定義された楕円曲線の解(つまりグラフの点)の中でも、有理点には、
有限体上で定義された楕円曲線でも対応する点がある、という事実があります。

つまり、今まで有理点について考えてきたお話が、
すべて、有限体上で定義された楕円曲線についても通用するというわけです。

楕円曲線上の有理点について考えることは、
楕円曲線暗号にも役立つ、というわけです。

楕円曲線上の有限巡回群と ECDLP

楕円曲線上の有理点は有限巡回群をなす、というお話は前回しました。
これは、有限体上で定義された楕円曲線においても通用します。

楕円曲線のパラメータと、ベースポイントとなる点 G が公開されていて、
秘密の値、x をランダムに決めたとき、G を x 倍した点、P=xG を計算することは簡単です。

愚直に x 回足すと、x のビット数 l に対して最大 2^l-1 回の足し算を行う必要がありますが、
バイナリ法を使えば 2l 回の足し算で済みますから。

じゃあ、逆に、G を何倍かした値 P が与えられたとき、それが G を何倍した値なのか、
つまり、P から秘密の値 x を求めるにはどうするかと言うと、愚直にやって 2^l-1 回の足し算、
もしくは、現在知られているもっと効率の良い方法を使っても、指数関数になる回数の足し算が必要になります。
つまり、「逆は難しい」のです。

この後者でお話した問題、秘密の値 x を求めることを、ECDLP、楕円曲線上の離散対数問題と呼びます。

楕円曲線暗号は、前者が簡単で後者が難しい(現実的な時間で解けない)ことを仮定して設計されています。

まとめ

楕円曲線論を楕円曲線暗号として活用するための最後のピース、
有限体上での定義と、ECDLP についてお話しました。

ここまで連載を読んでいただけた方ならば、
もう、GoogleWikipedia で検索すれば出てくる程度の楕円曲線暗号の解説などは
ある程度読めるだけの基礎知識は身についているものと思います。

なので、これ以上の説明は、その辺の Web サイトや論文等におまかせして、
この連載はそろそろ終了にしようと思います。

みなさん、お付き合いいただき、ありがとうございました。
ご質問、ご意見等ありましたらお気軽にリプライください。
それではまた。

楕円曲線論はじめの一歩 (13)

今回のおはなし

みなさんこんにちは。

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

前回は、楕円曲線上の有理点がなす群が、複素平面上の点と準同型な関係にある。
というお話をしました。
今回は、複素平面との関連性から、楕円曲線上の有理点がなす群の性質を探ってみましょう。

位数 3 の点

前回の話の復習になりますが、楕円曲線上の有理点がなす群で、位数が 3 の有理点に対応する点を
複素平面上に図示してみましょう。

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

元々の平行四辺形の格子を、さらに 3 \times 3 に分割した点のいずれか。
その中の、とりあえず 1 つをピックアップしてみました。

この中の、どの点を選んでも、3 倍すると無限遠点に対応する、平行四辺形の頂点にたどり着くことが
確認できると思います。

複素平面上の格子の性質と楕円曲線の性質

今回は 3 \times 3 に分割しましたが、5 \times 5 に分割した場合は
必ず 5 倍すると無限遠点にたどり着きます。10 \times 10 なら 10 倍です。

複素平面上にある点は、必ず、その点で交差する n \times n の格子が存在するため、
どの点であっても、何倍かすれば必ず無限遠点に対応する点までたどり着けることになります。

また、楕円曲線上の有理点は、すべて複素平面上に対応する点があるため、
楕円曲線に戻って考えてみれば、

  1. 楕円曲線上の全ての有理点には、複素平面上に対応する点がある
  2. 複素平面上の全ての点は、平行四辺形をいくつかに区切った格子上にある
  3. 格子上にある点は、何倍かすれば平行四辺形の頂点に達する
  4. 平行四辺形の頂点は無限遠点に対応する

という4段を踏まえると、「楕円曲線上の有理点は何倍かすると無限遠点に達する」わけです。

無限遠点は、楕円曲線上の有理点のなす群の単位元でした。
何倍かすると単位元に戻る、ということは、最初の方でお話した時計の短針、あれと同じ構造なわけです。

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

これは 12 倍すると単位元に戻る例でした。

ということはつまり、楕円曲線上の有理点のなす群は、有限巡回群であることがわかります。

言い換えれば、楕円曲線から有理点を 1 つ、適当に選び出すと、
その点を何度も足し続けると、いつかは無限遠点にたどり着くわけです。

まとめ

今回は、楕円曲線上の有理点のなす群は、実は有限巡回群だった、というお話でした。

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