A Small and Fast Software Implementation of Elliptic Curve Cryptosystems over GF(p) on a 16-Bit Microcomputer

Toshio HASEGAWA  Junko NAKAJIMA  Mitsuru MATSUI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.1   pp.98-106
Publication Date: 1999/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
public key cryptography,  elliptic curve cryptosystem,  GF(p),  16-bit microcomputer,  implementation,  

Full Text: PDF(192.4KB)>>
Buy this Article




Summary: 
Recently the study and implementation of elliptic curve cryptosystems (ECC) have developed rapidly and its achievements have become a center of attraction. ECC has the advantage of high-speed processing in software even on restricted environments such as smart cards. In this paper, we concentrate on complete software implementation of ECC over a prime field on a 16-bit microcomputer M16C (10 MHz). We propose a new type of prime characteristic of base field suitable for small and fast implementation, and also improve basic elliptic arithmetic formulas. We report a small and fast software implementation of a cryptographic library which supports 160-bit elliptic curve DSA (ECDSA) signature generation, verification and SHA-1 on the processor. This library also includes general integer arithmetic routines for applicability to other cryptographic algorithms. We successfully implemented the library in 4 Kbyte code/data size including SHA-1, and confirmed a speed of 150 msec for generating an ECDSA signature and 630 msec for verifying an ECDSA signature on M16C.