臺灣博碩士論文加值系統

隨著比特幣越來越被廣泛使用，在使用比特幣進行付款或轉帳時，當中的安全性亦成為值得關注的議題之一。鑒於影響比特幣安全性的其中一個主要因素是找出私鑰的難易度，而這與解決橢圓曲線離散對數問題有很大關聯，所以本文將會探討在理論上可以應用到比特幣，並且可以用來解決橢圓曲線離散對數問題的純數學方法。此外，不單是原始方法，改良後的方法也會在本文中被提及，目的是通過研究可以用於尋找私鑰的方法來討論使用比特幣進行交易的安全性。

另一方面，與純數學方法相對應的是非純數學方法。非純數學方法雖然提供了找出私鑰的捷徑，但它們僅在程式存在某種漏洞的情況下才能被使用。思慮到這些方法仍有可能對比特幣的安全性構成威脅，本文也簡單描述了一部份較常提及的非純數學方法。

最後，結果顯示使用比特幣進行付款或轉帳在現階段算是安全的，但是，未來量子計算機的出現可能會改變現況。有見及此，本文在文未評價了量子計數機的影響。

With the popular usage of Bitcoin, safety in making payments or transactions becomes a topic of concern. In brief, the security chiefly relies on the easiness of finding the secret key/ private key in Bitcoin. To a large extent, this depends on how easy it is to resolve an Elliptic Curve Discrete Logarithm Problem (ECDLP). With that in mind, the main focus of this paper is to review any mathematical approaches and their variants that can theoretically tackle an ECDLP in Bitcoin. The objective is to discuss the security of Bitcoin by studying methods of uncovering the private key.

On the other hand, the existence of non-mathematical approaches provides an alternative to figure out the private key faster. Notably, they work only in the presence of implementation vulnerabilities. Even so, in consideration of the influence that non-mathematical approaches may bring about, this paper also includes an outline of some of the frequently mentioned ones.

Last but not least, results indicated that using Bitcoin for payments or transactions appears to be secure at this stage, but the development of quantum computers may alter the situation in the future. By taking this into account, this paper ends up with a comment on the impact of quantum computers on Bitcoin.

1 Introduction..............................................................1
2 Literature Review.....................................................3
3 Background.............................................................5
3.1 Elliptic Curves ......................................................5
3.2 secp256k1............................................................6
3.2.1 Automorphism of order 6...................................7
3.2.2 Six twists............................................................7
4 Mathematical approaches........................................8
4.1 Baby-Step-Giant-Step Algorithm...........................9
4.1.1 The original version............................................9
4.1.2 Interleaved Baby-Step-Giant-Step Algorithm....10
4.1.3 Baby-Step-Giant-Step Algorithm with negatio...10
4.1.4 Two Grumpy Giants and a Baby........................11
4.1.5 Supplementary: Efficient computation of point addition.......................................................................13
4.2 Pollard Rho Method..............................................15
4.2.1 The original version...........................................15
4.2.2 Adjustment on the function, f.............................16
4.2.3 Other cycle detection method............................17
4.2.4 Parallelization....................................................18
4.2.5 Utilizing automorphism.......................................20
4.3 Kangaroo Method..................................................24
4.3.1 The original version……………...........................24
4.3.2 Modification………………...................................25
4.3.3 Parallization…………………................................26
4.3.4 Using the negation map………...........................28
4.3.5 Introducing more kangaroos……........................29
5 More mathematical approaches to ECDLP...............31
5.1 MOV attack............................................................32
5.1.1 Preliminary………………....................................32
5.1.2 The Weil Pairing…………….............................. 32
5.1.3 The MOV attack……………................................34
5.2 Index Calculus Algorithm………............................40
5.2.1 The original index calculus algorithm…..............41
5.2.2 Summation polynomials…..................................41
5.2.3 Amadori et al.'s algorithm………........................42
5.2.4 McGuire and Mueller's algorithm…....................44
5.3 A further speedup – The GLV Method...................46
5.3.1 Idea behind the GLV method..............................46
5.3.2 Decomposition of k.............................................47
6 Non-mathematical Approaches................................48
6.1 Signing a transaction in Bitcoin.............................49
6.2 Related non-mathematical approaches................49
6.3 Other non-mathematical approaches...................50
7 A Remark on Quantum Computers.........................52
8 Conclusion...............................................................54
Reference...................................................................56

[1]Amadori, A., Pintore, F., ＆ Sala, M., On the discrete logarithm problem for prime- field elliptic curves. Finite Fields and Their Applications, 51, 168-182 (2018). doi: https://doi.org/10.1016/j.ffa.2018.01.009

[2]Balasubramanian, R., ＆ Koblitz, N., The Improbability That an Elliptic Curve Has Subexponential Discrete Log Problem under the Menezes-Okamoto- Vanstone Algorithm. Journal of Cryptography, 11 (2), 141-145 (1998). doi: 10.1007/s001459900040

[3]Bernstein, D. J., Lange, T., ＆ Schwabe, P., On the correct use of the negation map in the Pollard Rho method. In D. Catalano, N. Fazio, R. Gennaro, ＆ A. Nicolosi (Eds.), Public Key Cryptography – PKC 2011: 14th International Conference on Practice and Theory in Public Key Cryptography, Taormina, Italy, March 6-9, 2011 Proceedings, Springer, Berlin, pp. 128-146 (2011). doi: https://doi.org/10.1007/978-3-642-19379-8 8

[4]Bernstein, D. J., ＆ Lange, T., Two Grumpy giants and a baby. In E. W. Howe, ＆ K. S. Kedlaya (Eds.), Proceedings of the Tenth Algorithmic Number Theory Symposium, msp, USA, pp. 87-111 (2013). doi: 10.2140/obs.2013.1.87

[5]Biehl, I., Meyer, B., ＆ Muller, V., Differential Fault Attacks on Elliptic Curve Cryptosystems. In M. Bellare (Ed.), Advances in Cryptology – CRYPTO 2000: 20thAnnual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2000 Proceedings, Springer, Berlin, pp. 131-146 (2000). doi: https://doi.org/10.1007/3-540-44598-6 8

[6]Blake, I., Seroussi, G., ＆ Smart, N., Elliptic Curves in Cryptography. London, England: Cambridge University Press, 1999.

[7]Bos, J. W., Kleinjung, T., ＆ Lenstra, A. K., On the use of the Negation Map in the Pollard Rho Method. In G. Hanrot, F. Mora, ＆ E. Thome´ (Eds.), Algorithmic Number Theory 9th International Symposium, ANTS-IX Nancy, France, July 19-23, 2010 Proceedings, Springer, Berlin, pp. 66-82 (2010). doi:
https://doi.org/10.1007/978-3-642-14518-6 9

[8]Bos, J. W., Halderman, J. A., Heninger, N., Moore, J., Naehrig, M., ＆ Wustrow, E., Elliptic Curve Cryptography in Practice. In N. Christin, ＆ R. Safavi-Naini (Eds.), Financial Cryptography and Data Security: 18th International Conference, FC 2014, Christ Church, Barbados, March 3-7, 2014, Revised Selected Pa- pers, Springer, Berlin, pp. 157-175 (2014).

[9]Buchanan, B.,TheMost Significant Future Risk Around Blockchain: ECDSA . . . andMeet IOTA. (2018).[Blog post]. Available: https://medium.com/asecuritysite-when-bob-met-alice/the-most-significant- future-risk-around-blockchain-ecdsa-361b245219dc

[10]Certicom Reseach, Standards for Efficient Cryptography, SEC 2: Recommended Elliptic Curve Domain Parameters, Version 2.0. (2010). [Online]. Available: http://www.secg.org/

[11]Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., ＆ Vercauteren, F., Handbook of Elliptic and Hyperelliptic Curve Cryptography. Boca Raton, FL, USA: Chapman ＆ Hall/ CRC, 2006.

[12]Dale, O., Quantum Computing: What Threat Does It Pose to Bitcoin? (2018). [Blog post]. Available: https://blockonomi.com/bitcoin-quantum-computing/

[13]Duursma, I., Gaudry, P., ＆ Morain, F., Speeding up the discrete log compu- tation on curves with automorphisms. In K. Y. Lam, E. Okamoto, ＆ C. Xing (Eds.), Advances in Cryptology – ASIACRYPT’99: International Conference on the Theory and Application of Cryptology and Information Security, Singapore, November 14-18, 1999 Proceedings, Springer, Berlin, pp. 103-121 (1999). doi: https://doi.org/10.1007/978-3-540-48000-6 10

[14]Ezzouak, S., Elamrani, M., ＆ Azizi, A., A variant of Pollard’s Rho attack on el- liptic curve cryptosystems. Journal of Computer Science, 10 (8), 1575-1581(2014). doi: 10.3844/jcssp.2014.1575.1581

[15] Fowler, A. and Galbraith, S. D., Kangaroo Methods for Solving the Interval Dis- crete Logarithm Problem, B.S. thesis, Dept. Mathematics, Univ. Auckland, New Zealand. (2015). [Online]. Available: https://arxiv.org/abs/1501.07019

[16]Galbraith, S. D., ＆ Ruprai, R. S., Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval. In P.Q. Nguyen, ＆ D. Pointcheval (Eds.), Public Key Cryptography - PKC 2010: 13th Interna- tional Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010, Proceedings, Springer, Berlin, pp. 368-383 (2010). doi: 10.1007/978-3-642-13013-7

[17]Galbraith, S. D., Pollard, J. M., ＆ Ruprai, R., Computing Discrete Logarithms in an interval. Mathematics of Computations, 82 (282), 1181-1195 (2012). [Online]. Available: https://www.ams.org/publications/journals/journalsframework/mcom

[18]Galbraith, S. D., ＆ Gaudry, P., Recent progress on the elliptic curve discrete logarithm problem. Designs, Codes and Cryptography, 78 (1), 51-72 (2016). doi: https://doi.org/10.1007/s10623-015-0146-7

[19]Galbraith, S. D., Wang, P., ＆ Zhang, F., Computing Elliptic Curve Discrete Logarithms with Improved Baby-step Giant-step Algorithm. Advances in Mathematics of Communications, 11 (3), 453-469 (2017). doi: 10.3934/amc.2017038

[20]Galbraith, S. D., Ed., Mathematics of Public Key Cryptography. Version 2.0. (2018). [Online]. Available: https://www.math.auckland.ac.nz/ sgal018/crypto- book/main.pdf

[21]Gallant, R., Lambert, R.,＆ Vanstone, S., Improving the parallelized Pollard Lambdasearch on anomalous binarycurves. Mathematics of Computations,69 (232), 1699-1705 (1999). [Online]. Available:http://www.ams.org/journals/mcom/2000-69-232/S0025-5718-99- 01119-9/S0025-5718-99-01119-9.pdf

[22]Gallant, R. P., Lambert, R. J., ＆ Vanstone, S. A., Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms. In J. Kilian (Ed.), Advances in Cryptology – CRYPTO 2001: 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001 Proceedings, Springer, Berlin, pp. 190-200 (2001). doi: https://doi.org/10.1007/3-540-44647-8 11

[23]Gaudry, P., ＆ Schost, E´. A low-memory parallel version of Matsuo, Chao and Tsujii’s algorithm. In D. Buell (Ed.), Algorithmic Number Theory: 6 the International Symposium, ANTS-VI, Ants-vi, Burlington, Vt, USA, June 13-18, 2004, Proceedings, Springer, Berlin, pp. 208-223 (2004).

[24]Genkin, D., Pachmanov, L., Pipman, I., Tromer, E., ＆ Yarom, Y., ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 1626-1638 (2016). doi: 10.1145/2976749.2978353

[25]Harasawa, R., Shikata, J., Suzuki, J., ＆ Imai, H., Comparing the MOV and FR Reductions in Elliptic Curve Cryptography. In J. Stern (Ed.), Advances in Cryptology – EUROCRYPT ’99: International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999 Proceedings, Springer, Berlin, pp. 190-205 (1999). doi: https://doi.org/10.1007/3-540-48910-
X 14

[26]Howgrave-Graham, N. A., ＆ Smart, N. P. Lattice Attacks on Digital Signature Schemes. Designs, Codes and Cryptography, 23 (3), 283-290 (2001). doi: https://doi.org/10.1023/A:1011214926272

[27]Koblitz, N., Elliptic Curve Cryptosystems. Mathematics of Computation, 48 (177), 203-209 (1987). doi: https://doi.org/10.1090/S0025-5718-1987-0866109-5

[28]Mayer, H., ECDSA Security in Bitcoin and Ethereum: a Research Survey. (2016). [Onine]. Avaiable: https://www.semanticscholar.org/paper/ ECDSA-Security-in-Bitcoin-and-Ethereum-%3A-a-Research-Mayer/ 17856bad4335c8ca7419aab2c715ea25ce5e0621

[29]McGuire,G., ＆ Mueller,D. A., New Index Calculus Algorithm for the Elliptic Curve DiscreteLogarithm Problem and Summation Polynomial Evaluation.(2018). [Oline]. Available: https://www.semanticscholar.org/paper/A-New-Index-Calculus-Algorithm-for- the-Elliptic-and-McGuire Mueller/bcb0ee080958dfbc81e0b70364b7c953feb0232b

[30]Menezes, A., Vanstone, S., ＆ Okamoto, T., Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. IEEE Transactions on Information Theory, 39 (5), 1639-1646 (1993).

[31]Miller, V. S., Use of Elliptic Curves in Cryptography. In H. C. Williams (Ed.), Advances in Cryptology - CRYPT0 ’85, LNCS 218, Springer, Berlin, pp. 417- 426 (1986).

[32]Miller, V. S., The Weil Pairing, and Its Efficient Calculation. Journal of Cryptog- raphy, 17, 235-261 (2004). doi: 10.1007/s00145-004-0315-8

[33]Miyaji, A., Nakabayashi, M., ＆ Takano, S., New Explicit Conditions of Elliptic Curve Traces for FR-Reduction. IEICE Transaction on Fundamentals of Electron- ics, Communications and Computer Sciences, 84 (5), 1234-1243 (2001).

[34]Nivasch, G., Cycle Detection Using a Stack. Information Processing Letters, 90 (3),135-140 (2004). doi: https://doi.org/10.1016/j.ipl.2004.01.016

[35]Pollard, J. M., Monte Carlo Methods for Index Computation (mod p). Mathemat- ics of Computation, 32 (143), 918-924 (1978). doi: 10.2307/2006496

[36]Pollard, J. M., Kangaroos, Monopoly and Discrete Logarithms. Journal of Cryp- tography, 13 (4), 437-447 (2000). doi: https://doi.org/10.1007/s001450010010

[37]SafeCurves, SafeCurves: choosing safe curves for elliptic-curve cryptography. (n.d.). [Online]. Available: http://safecurves.cr.yp.to/index.html

[38]Samtani, N. J., How Would Quantum Computing Impact the Security of Bitcoin by Enhancing Our Ability to Solve the Elliptic Curve Discrete Logarithm Problem?. (2018). [Online]. Available: https://papers.ssrn.com/sol3/papers.cfm?abstract id=3232101

[39]Semaev, I., Summation polynomials and the discrete logarithm problem on elliptic curves. (2004). [Online]. Available: https://eprint.iacr.org/2004/031.pdf

[40]Shikata, J., Zheng, Y., Suzuki, J., ＆ Imai, H., Optimizing the Menezes-Okamoto- Vanstone (MOV) Algorithm for Non-Supersingular Elliptic Curves. In K. Y. Lam,
E. Okamoto, ＆ C. Xing (Eds.), Advances in Cryptology – ASIACRYPT’99: Inter- national Conference on the Theory and Application of Cryptology and Information Security, Singapore, November 14-18, 1999 Proceedings, Springer, Berlin, pp. 86-102 (1999). doi: 10.1007/b72231

[41]Sica, F., Ciet, M., ＆ Quisquater, J. J., Analysis of the Gallant-Lambert-Vanstone Method based on Efficient Endomorphisms: Elliptic and Hyperelliptic Curves. In K. Nyberg, ＆ H. Heys (Eds.), Selected Areas in Cryptography: 9th Annual International Workshop, SAC 2002, St. John’s, Newfoundland, Canada, August 15-16, 2002, Revised Papers, Springer, Berlin, pp. 21-36 (2003).

[42]Silverman J. H., The Arithmetic of Elliptic Curves. New York, NY, USA: Springer, 1986.

[43]Teske, E., Speeding Up Pollard’s Rho Method for Computing Discrete Logarithms. In J. P. Buhler (Ed.), Algorithmic Number Theory: Third International Sympo- sium, ANTS-III, Portland, Oregon, USA, June 21–25, 1998 Proceedings, Springer,
Berlin, pp. 541-554 (1998). doi: https://doi.org/10.1007/BFb0054891

[44]Teske, E., Computing discrete logarithms with the parallelized kangaroo method. Discrete Applied Mathematics, 130 (1), 61-82 (2003). doi: 10.1016/S0166- 218X(02)00590-5

[45]Van Oorschot, P., ＆ Wiener, M. J., Parallel Collision Search with Crypt- analytic Applications. Journal of Cryptography, 12 (1), 1-28 (1999). doi: 10.1007/PL00003816

[46]Wang, P., ＆ Zang F., Computing Elliptic Curve Discrete Logarithms with the Negation Map. Information Science, 195, 277-286 (2012). doi: https://doi.org/10.1016/j.ins.2012.01.044

[47]Wiener, M. J., ＆ Zuccherato, R. J., Faster Attacks on Elliptic Curve Cryp- tosystems. In S. Tavares, ＆ H. Meijer (Eds.), Selected Areas in Cryptogra- phy: 5th Annual International Workshop, SAC’98 Kingston, Ontario, Canada, August 17-18, 1998 Proceedings, Springer, Berlin, pp. 190-200 (1999). doi: https://doi.org/10.1007/3-540-48892-8 15