Efficient Algorithms for Elliptic Curve Cryptography

Intractable problems are the heart of the public key cryptography and bring computational intensive operations into a cryptosystem. The mathematically proven hardest intractable problem lies within the boundaries of elliptic curve arithmetic. The software and hardware implementations of such an elliptic curve cryptosystem have become challenging due to the computational intensive operations, namely, single and double scalar multiplications.;Double-base number system is endowed with the very lucrative property, sparseness which makes it so important in some digital design applications. We exploit the sparseness of double-base number system to represent a scalar and a pair of scalars in some efficient ways to speed up both single and double scalar multiplications.;Sometimes, the integer multiplication heavily dominates the total cost of so-called scalar multiplications. Therefore, we introduce a novel algorithm to improve the area of a hardware implementation of an integer multiplier. The construction of new multiplier architecture is based on double-base number system.;Koblitz curves are a special set of elliptic curves that perform scalar multiplication efficiently. They have superior performance especially in elliptic curve cryptosystem hardware implementations. An integer should be converted into a specific representation called tau-adic expansion to obtain the advantage of use of Koblitz curves. We propose an efficient hardware architecture for the conversion of an integer to tau-adic expansion.;We extend our hardware implementations for Koblitz curves to double scalar multiplication by introducing another new algorithm and corresponding hardware architecture for generating a sparse, low Hamming weight joint tau-adic expansion for a pair of integers.