Viggo Haeggström Grunewald: Algebraic Foundations And Computational Attacks In Elliptic Curve Cryptography

Abstract.

Elliptic curve cryptography (ECC) is widely used in modern cryptographic systems and relies on the presumed hardness of the elliptic curve discrete logarithm problem (ECDLP), over suitably chosen curves. This thesis first develops the algebraic background including modular arithmetic, finite fields, the Weierstrass equation and the group law, before formally stating the ECDLP and examining potential attacks. We analyze the index-calculus method, a sub exponential algorithm, as an attack against the general discrete logarithm problem and discuss why it generally does not does not work for elliptic curves. After this we shift focus to Pollard’s rho and lambda methods by analyzing howpseudo-random walks, cycle detection and the extraction of the secret k from colliding states works. To evaluate practical performance, we implement Pollard’s rho algorithm in SageMath and test it in various scenarios. One test focuses on corroborating Washington’s heuristic that about twenty partitions of the subgroup generated by P is near-optimal. To do this, 50 randomly generated curves over prime fields of order roughly 108 were generated, varying the walk-partition parameter s ∈ {2, . . . ,40}.

The experiment shows a steep runtime decline up to s ≈ 15 and only marginal gains beyond s ≈ 20. We then benchmark our implemented version of Pollard’s rho against SageMath’s built in version. This tests shows that SageMath’s version is significantly more efficient, likely due to SageMath using cython. We then conclude by timing Pollard’s rho against Pollard’s kangaroo method using SageMath’s built in versions. Which highlights how information about the range of the secret k can greatly improve performance. If it is known that k ∈ (a,b) with L = b−a and |P| = n, we observe that for L = n/log (n) the runtime can be more than halved. Subsequent tests shows an even greater increase in speed for smaller intervals L.