Hardware implementation of DBNS recoding for ECC processor

International audienceIn elliptic curve cryptography (ECC), arithmetic is a key element for designing efficient and secure cryptosystems. Finite fields arithmetic units should be fast to perform numerous and various computations (additions, subtractions, multiplications, inversions in the field) on large numbers (160-600 bits). For cost reasons, arithmetic operators should also be area, memory and power efficient. Finally, for security reasons, they should not reveal internal information during physical attacks such as side channel analysis. In this work, we study FPGA implementations of various recoding schemes for secure ECC coprocessors. In ECC protocols, the main operation is the scalar multiplication [k]P where k is a large integer (160-600 bits) and P a point on the elliptic curve. In order to prevent from side channel analysis, k should be recoded at run time. Standard recodings schemes are Non-Adjacent Forms (NAF and w-NAF) where a signed-digit representation is used. Double-Base Number System (DBNS) has been proposed to reduce the number of non-zero digits in DBNS recoded values. DBNS is a very redundant number system and it allows sparse representations of numbers. We study the implementation of DBNS recoding schemes in FPGA for secure ECC coprocessors. We implement and analyze the cost and speed of the greedy DBNS conversion and various on-line DBNS transformations operations. We compare the performance aspects of DBNS and standard recoding schemes such as NAF and w-NAF