|
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
|
Fast Elliptic Curve Multiplications with SIMD Operations
Tetsuya IZU Tsuyoshi TAKAGI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E87-A
No.1
pp.85-93 Publication Date: 2004/01/01 Online ISSN:
DOI: Print ISSN: 0916-8508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Asymmetric Cipher Keyword: Elliptic Curve Cryptosystems (ECC), scalar multiplication, window method, SIMD operations, side channel attacks,
Full Text: PDF(291.1KB)>>
Summary:
The Single Instruction, Multiple Data (SIMD) architecture enables computation in parallel on a single processor. The SIMD operations are implemented on some processors such as Pentium 3/4, Athlon, SPARC, or even on smart cards. This paper proposes efficient algorithms for assembling an elliptic curve addition (ECADD), doubling (ECDBL), and k-iterated ECDBL (k-ECDBL) with SIMD operations. We optimize the number of auxiliary variables and the order of basic field operations used for these addition formulas. If an addition chain has k-bit zero run, we can replace k-time ECDBLs to the proposed faster k-ECDBL and the total efficiency of the scalar multiplication can be improved. Using the singed binary chain, we can compute a scalar multiplication about 10% faster than the previously fastest algorithm proposed by Aoki et al. Combined with the sliding window method or the width-w NAF window method, we also achieve about 10% faster parallelized scalar multiplication algorithms with SIMD operations. For the implementation on smart cards, we establish two fast parallelized scalar multiplication algorithms with SIMD resistant against side channel attacks.
|
|
|