Understanding power in cryptography

(eng) The concept of power may be of fundamental importance in many application fields of cryptography. In the context of small embedded devices, of growing interest with the advent of the “information era”, it is crucial to make the best use of the device weak resources, especially electrical power and energy. Another example is cryptanalysis which requires a huge amount of computational effort to break cryptographic algorithms. To improve the success probability of the cryptanalytic attempts, it is essential to make the most out of the available computing power. This is even more relevant when the attacks are conducted from a constructive point of view, in order to assess the security level of cryptographic algorithms. This thesis deals with two contexts of cryptography in which power is of central concern: cryptanalysis with special-purpose hardware and cryptography for low-power embedded devices. The common approach we follow is to carefully understand the available power resources in the studied contexts. In the first part, we exploit the computational power of Field Programmable Gate Arrays (FPGAs) and Application-Specific Integrated Circuit (ASICs) for practical attacks on public-key cryptosystems. We first propose an improved architecture to implement the Elliptic Curve Method of factoring integers on FPGA. This method is very useful when aiming to break RSA. We then study how to tackle the Elliptic Curve Discrete Logarithm Problem, relying on ASICs, in the special case of Koblitz curves. Our results underline the vulnerability of the 131-bit key size for Elliptic Curve Cryptography. In the second part, our aim is to decrease the overhead of cryptography for small embedded devices. We first analyze the energy cost of communication and cryptography in wireless sensor networks, allowing the selection of the less consuming protocol to achieve a given cryptographic task. We then study how to adapt group signatures to low-power devices, these signatures being very appealing for privacy-preserving applications. Our cooperative solution makes group signatures tractable for small devices like contactless smart cards.