Cryptology ePrint Archive: Report 2014/817

Optimized Karatsuba Squaring on 8-bit AVR Processors

Hwajeong Seo, Zhe Liu, Jongseok Choi, 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.

Category / Keywords: implementation /

Date: received 8 Oct 2014, last revised 14 Oct 2014

Contact author: hwajeong at pusan ac kr

Available format(s): PDF | BibTeX Citation

Version: 20141014:081615 (All versions of this report)

Short URL: ia.cr/2014/817

Discussion forum: Show discussion | Start new discussion