Abstract
Due to the prevalance of e-commerce increases year by year, the demand for information security also increases. In order to provide comprehensive and robust security sevices, we need security solutions built from cryptosystems including secret-key cryptosystems and public-key cryptosystems. Using Rivest-Shamir-Adleman algorithm (RSA) as the public-key cryptosystem has been prevailed over years. However, in recent years, elliptic curve cryptography (ECC) has emerged as an alternative to other public-key cryptosystems because it can provide the same security level with a smaller key size. Therefore it has advantage to be implemented in smart cards, PDA, cellular phones and other embedded systems. In elliptic curve cryptography, the most time-consuming operation is the scalar point multiplication, so we propose a new algorithm to compute scalar point multiplication over GF($2^n$) with the on-the-fly recoding. Due to the framework of a finite state machine within this algorithm, it is easy to implement in hardware. Besides, it is also not difficult to implement in software. It improves the conventional scalar point multiplication method, double-and-add (affine), around 12.8%, and can compete other scalar point multiplication methods, such as Montgomery scalar point multiplication or addition-subtraction method if the cost ratio of modular inverse to modular multiplication is not high. Based on this new algorithm, a scalable dual-field ECC processor is also implemented. Due to the word-based design, it can process larger key size when the memory is expanded.