Architectural extensions for elliptic curve cryptography over GF(2m) on 8-bit microprocessors

We describe and analyze architectural extensions to accelerate the public key cryptosystem elliptic curve cryptography (ECC) on 8-bit microprocessors. We show that simple extensions of the data path suffice to efficiently support ECC over GF(2^m). These extensions include an extended multiplier that generates results for both integer multiplications and multiplications in fields GF(2^m) and a multiply-accumulate instruction for efficiently performing multiple precision multiplications. To our knowledge, this is the first paper that quantifies performance of standard NIST and SECG elliptic curves over GF(2^m) on an 8-bit microprocessor equipped with a dual field multiplier. On the ATmegal28 microprocessor running at 8 MHz we measured an execution time of 0.29 s for a 163-bit ECC point multiplication over GF(2^m), 0.81s for a 160-bit ECC point multiplication over GF(p), and 11 s for a 1024-bit RSA private key operation - the chosen key sizes provide equivalent security strength.