Aspects of fast and secure arithmetics for elliptic curve cryptography

Elliptic curves began to be applied to cryptography in the middle of the eighties. In the last ten years, elliptic curves have been introduced in more and more secure applications, and especially in smart card implementations. This induces new problems (e.g. fast computations, side-channel immune implementations, storage size reduction etc) for which solutions have to be found. In this thesis, we deal with the arithmetic of elliptic curves, speedup techniques and secure implementations against side-channel analysis. We propose some new fast exponentiation methods. We generalize endomorphism-based integer decomposition to elliptic curves defined over a prime field. We also present a new way to speed-up computation on Koblitz curve combining point halving and endomorphism-based decomposition. We generalize faults attacks against elliptic curve cryptosystems and relax physical assumptions. Finally we develop new countermeasures for simple and differential side-channel analysis against elliptic curve implementations. Their performance penalty is generally very small and sometime null. Then, alternatively some secure implementations with similar performance to unprotected ones are presented.