Software and Hardware Implementation of Hyperelliptic Curve Cryptosystems
Thomas Wollinger · 2004
The hyperelliptic curve cryptosystem is one of the emerging cryptographic primitives of the last years. This system offers the same security as established public-key cryptosystems, such as those based on RSA or elliptic curves, with much shorter operand length. Consequently, this system allows highly efficient computation of the underlying field arithmetic. However, until recently the common belief in industry and in the research community was that hyperelliptic curves are out of scope for any practical application. The reason being the complex group operation leading to a worse overall performance compared to established public-key primitives. The thesis at hand is a step towards the practical use of hyperelliptic curve cryptosystems (HECC) by narrowing the performance gap between elliptic curve (EC) and hyperelliptic curve cryptosystems. We were able to reduce the complexity of the group operation for small genus hyperelliptic curves and we provide efficient algorithms for the computation of the hyperelliptic curve cryptosystem. Our theoretical comparison between elliptic curve and hyperelliptic curve cryptosystems, as well as our software and hardware implementations show that the performance of both cryptographic primitives are in the same range. Surprisingly, the hyperelliptic curve cryptosystems even outperforms elliptic curves using certain curve parameters. The implementations we investigated range from a general purpose processor to a variety of different embedded processors, and also includes the prototype implementation of a hyperelliptic curve coprocessor on FPGAs. We were able to lower the complexity of the hyperelliptic curve group operations compared to the best known formulae. The highest performance on an embedded system was achieved on the ARM7TDMI running at 80MHz. The scalar multiplication (for a group order of approximately 2) for ECC, genus-2 HECC, and genus-3 HECC could be computed in about 100 milliseconds. More detailed analysis show that on embedded