Optimized Karatsuba Squaring on 8-bit AVR Processors

Hwajeong Seo; Zhe Liu; Jongseok Choi; Howon Kim

Paper 2014/817

Optimized Karatsuba Squaring on 8-bit AVR Processors

Hwajeong Seo, Zhe Liu, Jongseok Choi, and Howon Kim

Abstract

Multi-precision squaring is a crucial operation for implementation of Elliptic Curve Cryptography. Particularly, when it comes to embedded processors, the operation should be designed carefully to execute expensive ECC operation on resource constrained devices. In order to bridge the gap between high overheads and limited computation capabilities, we present optimized Karatsuba squaring method for embedded processors. Traditional squaring computation can be divided into two sub-squaring and one sub-multiplication parts. Firstly we compute the multiplication part with the fastest Karatsuba multiplication and then remaining two squaring parts are conducted with the fastest sliding block doubling squaring. Proposed method sets the new speed records for multi-precision squaring, improving the execution time by up to 8.49% comparing to the best known works.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint. MINOR revision.
Contact author(s): hwajeong @ pusan ac kr
History: 2014-10-14: revised; 2014-10-12: received; See all versions
Short URL: https://ia.cr/2014/817
License: CC BY

BibTeX

@misc{cryptoeprint:2014/817,
      author = {Hwajeong Seo and Zhe Liu and Jongseok Choi and Howon Kim},
      title = {Optimized Karatsuba Squaring on 8-bit {AVR} Processors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/817},
      year = {2014},
      url = {https://eprint.iacr.org/2014/817}
}