# 研究まとめ

# 序論
楕円曲線暗号とは，1985年ごろにMiller氏とKoblitz氏が同時期に発明した暗号である．この暗号は楕円曲線上の離散対数問題(ECDLP)を安全性の根拠とし，実際にビットコインの電子署名に用いられている．ECDLPが解かれることは暗号が解かれることを意味する．

ECDLPは通常，複数の計算機を結合させたコンピュータクラスタを使って解かれる．Certicom 社（現 BlackBerry 社）は 1997年に ECC Challenge と名付けた，楕円曲線暗号の解読コンテストを実施した[1]．このコンテストでは79ビットの暗号が1997年，89ビットの暗号が1998年，97ビットの暗号が1999年に解読されている．97ビットの暗号は，後で述べる Pollardのrho法を並列化することで解かれた[2]．この方法では少なくとも16の国に設置された1200台以上のコンピュータを用い，53日間かけて解かれている．他の成果として，2015年に70台の計算機を用いて94bit，2017年には1029台の計算機を用いて114bitのECDLPがDistinguished point methodを組み合わせたRho法を使って現実的な時間で解かれている[3][4]．また，解読する際に発生する点の保存を複数のDNSサーバを用いて分散させ，効率的にECDLPを解く方法も提案されている[5]．

ECDLPを解くアルゴリズムは総当たり法よりも効率的なものとして，ShankのBSGS法，Pollardのrho法などが知られている.また，Pollardのrho法は用いる関数を変えることができるため，幾つか種類が存在する．

本研究はECDLPを解く幾つかのアルゴリズムを高速化が期待できるC++で実装し，一台の計算機がそれらのコンピュータクラスタにどこまで迫れるか検証した．それと共に将来の暗号の危殆化問題についても考察する．

# 結論

【結果】

結論として，40bit時点で，CPUのボトルネックを抑えた改良型Rho法の並列化プログラムKRho-Iが最も効率的なプログラムであることが分かった．
しかし，KRho-Iは一回に保存する点の数や，保存する特徴点の条件により解読時間が異なる．
ビット数によって解読時間が最速となるパラメータも違うため，更なる検証が必要である．
また，並列化はできなかったものの，Rho-Floyd法は他の高速化されていないプログラムと比べて最も高速なものであった．
これは並列化や高速化されたプログラムを除き，コリジョンペアを最も効率的に探索するアルゴリズムだと言える．

KRho-Iを使ってSecp256k1の解読時間を予測

どこまで迫れたかを書く(検証が必要)

【今後の展望】

Secp256k1を解くのに約$4.062\times10^{33}$年必要であった．

これはあくまでも今現在のコンピュータの性能で解いた場合であり，コンピュータの性能は進化することも考えなければならない．そこでムーアの法則について考えてみる．ムーアの法則は，「18～24か月で集積回路に搭載されるトランジスタ数が2倍になる」という経験則である．コンピュータの性能面からはプロセッサの微細化，高速省電力化と解釈され，定性的には計算機の性能が18～24か月で2倍になると考えられる[11]．

ムーアの法則がうまく機能しているとすれば，性能が2倍になれば，解読時間が半分になると仮定して，ECDLPを一年で解くには$4.062 \times 10^{33} / 2^{111.6} \approx1$ つまり，最短で今から$(18 \times 111.6 / 12) + 1= 168$年後の2190年にECDLPが解けることが予測できる．それでも時間がかかるため現実的に解けるとは言えない．

<!-- また計算機のプロセッサの問題として，トランジスタの微細化は原子サイズに近いており，計算機の性能が伸び悩み始めている[2]．その他にスケーリング則の破綻や発熱問題もある．したがって，ムーアの法則は永続的ではなく，いつか限界が来ること予想される．
-->

また，ムーアの法則が将来にわたって成り立ったと仮定した場合，2次元実装を継続する場合，極端な微細化の例として，電子1個を最小の素子としてトランジスタを実装したとしても，2036年に限界に達すると予想されている[12]．2次元実装ではなく，3次元実装によりプロセッサの高性能化が図られているが[13]，今後100年以上にわたりムーアの法則が成り立つとは考え難い．

この他に，現在のスーパーコンピュータのように，極めて多くのノードをネットワークを介して接続し，超並列処理により解読を試みる手法を発展させる場合を考える．この場合にも消費電力の問題の他，連続稼働するかという信頼性の問題，プログラミングの問題，I/O の問題などが存在する．このことから，現在知られているアルゴリズムを用いて暗号を古典コンピュータで解くことはやはり困難である．

しかし，古典コンピュータの計算性能を大きく上回る次世代のコンピュータとして量子コンピュータが考案されている．現状の量子コンピュータは21の素因数分解ができる程度の性能[14]だが，量子コンピュータが実用レベルになればECDLPは飛躍的に速く解けることが知られている[15]．

これに対処すべく，NISTでは量子コンピュータの攻撃に耐えれる，耐量子計算機暗号(PQC)を検討している[16][17]．NISTはPQC標準化プロジェクトとして2016年にPQC標準化開始の宣言を行い，世界中から量子コンピュータに耐えれる暗号を募った．募られた暗号は第2ラウンドで7つの最終選考と8つの代替候補に絞られ，現在第3ラウンドの選考に突入している．候補の中には本研究のキーワードでもある楕円曲線に関連したSIKEと呼ばれる暗号もある．NISTは今後，2022年から2024年の間に規格の草案をまとめる予定だ．

## 参考文献

### 序論に使えそう
ターゲットとする過去の研究：クラスターを用いたECDLPの計算

[1]
https://www.certicom.com/content/certicom/en/the-certicom-ecc-challenge.html

[2]E. Teske, “Speeding up Pollard’srho method for computing discrete logarithms”, Algorithmic Number Theory, Lecture Notes in Computer Science, 1423 (1998), Springer-Verlag, 541-554.

[3]Solving 94bit ECDLP with 70 computers in parallel 2015
url{https://doi.org/10.5281/zenodo.1108905}

[4]Solving 114bit ECDLP for a Barreto Naehrig Curve.
url{https://doi.org/10.1007/978-3-319-78556-1_13}

[5]2台以上のDNSサーバを使ったECDLP解読
url{https://ci.nii.ac.jp/naid/40020791182}

### 結論に使えそう

[11]G. E. Moore, Cramming more components onto integrated circuits,
Electronics, Vol. 38, No. 8, pp. 114–117 (1965)
url{https://newsroom.intel.com/wp-content/uploads/sites/11/2018/05/moores-law-electronics.pdf}

[12]J. R. Powell, "The Quantum Limit to Moore's Law," in Proceedings of the IEEE, vol. 96, no. 8, pp. 1247-1248, Aug. 2008,
url{https://doi.org/10.1109/JPROC.2008.925411}

[13]D. B. Ingerly et al.,
Foveros: 3D Integration and the use of Face-to-Face Chip Stacking for Logic Devices
2019 IEEE International Electron Devices Meeting (IEDM), San Francisco, CA, IEEE, 2019
url{https://doi.org/10.1109/IEDM19573.2019.8993637}

[14] Demonstration of Shor’s factoring algorithm for N = 21 on IBM quantum processors
https://www.nature.com/articles/s41598-021-95973-w

[15]M. Mosca and A. Ekert, “The hidden subgroup problem and eigenvalue estimation on a quantum computer”, Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communication, Lecture Notes in Computer Science, 1509(1999), Springer-Verlag.

[16]IPA:CRYPTEC2020
https://www.cryptrec.go.jp/report/cryptrec-rp-2000-2020.pdf

[17]NIST PQC
https://csrc.nist.gov/projects/post-quantum-cryptography

### アーカイブ参考文献

GPUだと更に早いということが書かれている
https://research.tue.nl/en/publications/parallel-cryptanalysis

ムーアの法則の限界について
https://www.publickey1.jp/blog/16/qcon_tokyo_2016_3.html

量子計算機を用いても，同種写像を効率的に見つけるアルゴリズムは現時点で構成されていない．
https://www.jstage.jst.go.jp/article/essfr/14/4/14_329/_article/-char/ja