VLSI Implementation of Double-Base Scalar Multiplication on a Twisted Edwards Curve with an Efficiently Computable Endomorphism

Zhe Liu, Husen Wang, Johann Großschädl, Zhi Hu, and Ingrid Verbauwhede

Abstract

The verification of an ECDSA signature requires a double-base scalar multiplication, an operation of the form $k \cdot G + l \cdot 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 $-x^2 + y^2 = 1 + x^2y^2$ over the 207-bit prime field $F_p$ with $p = 2^{207} - 5131$. The PFAU prototype we describe in this paper features a ($16 \times 16$)-bit multiplier and has an overall silicon area of 5821 gates when synthesized with a $0.13\mu$ 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.

Available format(s)
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
elliptic curve cryptosystemdigital signatures
Contact author(s)
husen wang @ esat kuleuven be
History
Short URL
https://ia.cr/2015/421

CC BY

BibTeX

@misc{cryptoeprint:2015/421,
author = {Zhe Liu and Husen Wang and Johann Großschädl and Zhi Hu and Ingrid Verbauwhede},
title = {VLSI Implementation of Double-Base Scalar Multiplication on a Twisted Edwards Curve with an Efficiently Computable Endomorphism},
howpublished = {Cryptology ePrint Archive, Paper 2015/421},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/421}},
url = {https://eprint.iacr.org/2015/421}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.