Author:

Keywords:

Applied Cryptography, Public Key, Hardware

Abstract:

Public Key Cryptography (PKC) is a critical component of today’s information infrastructure. The use of PKC covers a wide spectrum of devices ranging from web servers to mobile handsets, from contact smart cards to passive RFID tags. Therefore, PKC implementations tailored to different environments need specific optimizations to meet the requirements for performance, power and security against physical attacks.This thesis focuses on arithmetic and architecture design for PKC. In thefirst part, we analyze the computation structures of RSA, Elliptic CurveCryptography (ECC), Hyperelliptic Curve Cryptography (HECC), Torus-based cryptography and Pairings, and explore various representations, algorithms and architectures for different design targets. In particular, we propose a multi-core Montgomery multiplier, a low-complexity modular multiplication algorithm for pairings, and two novel architectures for low-area implementations of HECC.In the second part, we use efficient arithmetic as the basis for hardware-based cryptanalysis. The security margin of a cryptosystem erodes continuously due to Moore’s law. We study the power of FPGA clusters to break ECC using the parallelized Pollard rho method and implement this attack on an FPGA where we try to maximize the number of Pollard rho iterations per second. We also give an estimation of the effort to break ECC2-131 and ECC2k-160 with state-of-the-art FPGAs.In the third and final part, we provide a systematic overview of implementation attacks and countermeasures for ECC. By monitoring the timing, power consumption, electromagnetic emission of the device or by inserting faults, adversaries can gain information about internal data or operations and extract the secret key without mathematically breaking the primitives. We provide implementers of ECC with ready-to-use recommendations of which combinations of countermeasures result in a secure implementation.