VLSI implementation of double-base scalar multiplication on a twisted edwards curve with an efficiently computable endomorphism. Cryptology ePrint Archive: Report 2015/421

Abstract. The verification of an ECDSA signature requires a double-base scalar multiplication, an operation of the form k ·G+ l ·Q where G is a generator of a large elliptic curve group of prime order n, Q is an arbitrary element of said group, and k, l are two integers in the range of [1, n − 1]. We introduce in this paper an area-optimized VLSI design of a Prime-Field Arithmetic Unit (PFAU) that can serve as a loosely-coupled or tightly-coupled hardware accelerator in a system-on-chip to speed up the execution of double-base scalar multiplication. Our design is optimized for twisted Edwards curves with an efficiently computable endomorphism that allows one to reduce the number of point doublings by some 50 % compared to a conventional implementation. An example for such a special curve is −x2 + y2 = 1 + x2y2 over the 207-bit prime field Fp with p = 2207 − 5131. The PFAU prototype we describe in this paper features a (16 × 16)-bit multiplier and has an overall silicon area of 5821 gates when synthesized with a 0.13µ standard-cell library. It can be clocked with a frequency of up to 50 MHz and is capable to perform a constant-time multiplication in the mentioned 207-bit prime field in only 198 clock cycles. A complete double-base scalar multiplication has an execution time of some 365k cycles and requires the pre-computation of 15 points. Our design supports many trade-offs between performance and RAM requirements, which is a highly desirable property for future Internet-of-Things (IoT) applications