Efficient and secure Montgomery curves over TMVP-friendly primes for next-generation ECC

Date

2026-3-25

Author

Orhon Kılıç, Neriman Gamze

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

135
views

0
downloads

Cite This

As elliptic curve cryptography enters an era of hybrid post-quantum deployment and long-term data protection, there is growing demand for curves that combine security margins well beyond current standards with efficient, constant-time implementations. This thesis addresses that need through the design, security analysis, and optimized implementation of two new Montgomery-form elliptic curves: Curve5453, defined over the Crandall prime p = 2^545-3 with approximately 271 bits of classical security, and Curve6071, defined over the Mersenne prime p = 2^607-1 with approximately 302 bits, which is the highest security level among any SafeCurves-compliant curve to date. Both curves are generated through a fully rigid and deterministic procedure that selects the smallest Montgomery coefficient A ≡ 2 (mod 4) such that both the curve and its quadratic twist have near-prime order, and the smallest base-point x-coordinate generating the prime-order subgroup, mirroring the generation strategies of Curve25519 and Curve448. Security verification against the full SafeCurves framework confirms that Curve6071 satisfies all 11 criteria, while Curve5453 satisfies 10 of 11, lacking only completeness. The central technical contribution is the systematic application of Toeplitz Matrix-Vector Product (TMVP) decomposition to field arithmetic. Five radix representations are developed across the two underlying fields (three for F_{2^545-3} and two for F_{2^607-1}), four of which cast field multiplication as a Toeplitz matrix-vector product that admits tailored decomposition strategies. These reduce the number of single-precision multiplications required for field multiplication from 100 (schoolbook) to 77 (10-limb TMVP), 60 (9-limb two-level TMVP), and 54 (12-limb three-level TMVP), demonstrating that co-optimizing limb count, radix width, and TMVP structure yields multiplication counts well below what any single representation can achieve. The complete arithmetic pipeline, including the constant-time Montgomery ladder, Fermat-based inversion, and seventeen multiplication strategies, is implemented in portable C and benchmarked on ARM64 (Apple M1 Pro) and x86-64 (Intel Core i7-8565U). On ARM64, the best methods achieve 112 cycles for field multiplication on both curves, with scalar multiplication reaching 755,616 cycles for Curve5453 (26% faster than the DONNA baseline) and 853,337 cycles for Curve6071. A comparative assessment on x86-64 shows that Curve5453 reaches 1,674,139 cycles, approximately 1.8x slower than E-521's reported 943,000 cycles on Haswell, while providing 12 additional bits of security with portable C versus hand-optimized assembly; Curve6071 reaches 1,497,513 cycles, 1.6x slower despite 43 additional bits of security. An ECDH throughput comparison against OpenSSL 3.6.0 on ARM64 demonstrates that Curve5453 achieves 90.6% of NIST P-521's throughput with 12 extra bits of security, and both curves outperform Brainpool P-512 by factors of 3.1x to 3.4x despite operating over larger fields.

Subject Keywords

Elliptic curve cryptography, Montgomery curves, Safecurves, Toeplitz matrix-vector product, Field arithmetic, Scalar multiplication, High-security curves

URI

https://hdl.handle.net/11511/119002

Collections

Graduate School of Applied Mathematics, Thesis