Improved multi-precision squaring for low-end RISC microcontrollers

Younho Lee, Ill Hee Kim, Yongsu Park

Research output: Contribution to journalArticle

16 Citations (Scopus)

Abstract

We present an enhanced multi-precision squaring algorithm for low-end RISC microcontrollers. Generally, they have many general-purpose registers and limited bus size (8-32 bits). The proposed scheme employs a new technique, "lazy doubling" with optimizing computing sequences; so, it is significantly faster than the previous algorithms. Mathematical analysis shows that the number of clocks required by the proposed algorithm is about 67 of those required by the carry-catcher squaring algorithm. To the best of our knowledge this is known to be the fastest squaring algorithm. Experimental results on the ATmega128 microprocessor show that our algorithm is about 1.5 times faster than the carry-catcher squaring algorithm in terms of the number of clocks required. As squaring is a key operation in public key cryptography, the proposed algorithm can contribute to lowering power consumption in secure WSNs (wireless sensor networks) or secure embedded systems.

Original languageEnglish
Pages (from-to)60-71
Number of pages12
JournalJournal of Systems and Software
Volume86
Issue number1
DOIs
StatePublished - 2013 Jan 1

Fingerprint

Reduced instruction set computing
Microcontrollers
Clocks
Public key cryptography
Embedded systems
Microprocessor chips
Wireless sensor networks
Electric power utilization

Keywords

  • Low-end microprocessor
  • Multi-precision squaring
  • Public key cryptography
  • Security
  • Sensor networks

Cite this

@article{a67e2e1df3e74467b1fc75cb4de1e6f3,
title = "Improved multi-precision squaring for low-end RISC microcontrollers",
abstract = "We present an enhanced multi-precision squaring algorithm for low-end RISC microcontrollers. Generally, they have many general-purpose registers and limited bus size (8-32 bits). The proposed scheme employs a new technique, {"}lazy doubling{"} with optimizing computing sequences; so, it is significantly faster than the previous algorithms. Mathematical analysis shows that the number of clocks required by the proposed algorithm is about 67 of those required by the carry-catcher squaring algorithm. To the best of our knowledge this is known to be the fastest squaring algorithm. Experimental results on the ATmega128 microprocessor show that our algorithm is about 1.5 times faster than the carry-catcher squaring algorithm in terms of the number of clocks required. As squaring is a key operation in public key cryptography, the proposed algorithm can contribute to lowering power consumption in secure WSNs (wireless sensor networks) or secure embedded systems.",
keywords = "Low-end microprocessor, Multi-precision squaring, Public key cryptography, Security, Sensor networks",
author = "Younho Lee and Kim, {Ill Hee} and Yongsu Park",
year = "2013",
month = "1",
day = "1",
doi = "10.1016/j.jss.2012.06.074",
language = "English",
volume = "86",
pages = "60--71",
journal = "Journal of Systems and Software",
issn = "0164-1212",
number = "1",

}

Improved multi-precision squaring for low-end RISC microcontrollers. / Lee, Younho; Kim, Ill Hee; Park, Yongsu.

In: Journal of Systems and Software, Vol. 86, No. 1, 01.01.2013, p. 60-71.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Improved multi-precision squaring for low-end RISC microcontrollers

AU - Lee, Younho

AU - Kim, Ill Hee

AU - Park, Yongsu

PY - 2013/1/1

Y1 - 2013/1/1

N2 - We present an enhanced multi-precision squaring algorithm for low-end RISC microcontrollers. Generally, they have many general-purpose registers and limited bus size (8-32 bits). The proposed scheme employs a new technique, "lazy doubling" with optimizing computing sequences; so, it is significantly faster than the previous algorithms. Mathematical analysis shows that the number of clocks required by the proposed algorithm is about 67 of those required by the carry-catcher squaring algorithm. To the best of our knowledge this is known to be the fastest squaring algorithm. Experimental results on the ATmega128 microprocessor show that our algorithm is about 1.5 times faster than the carry-catcher squaring algorithm in terms of the number of clocks required. As squaring is a key operation in public key cryptography, the proposed algorithm can contribute to lowering power consumption in secure WSNs (wireless sensor networks) or secure embedded systems.

AB - We present an enhanced multi-precision squaring algorithm for low-end RISC microcontrollers. Generally, they have many general-purpose registers and limited bus size (8-32 bits). The proposed scheme employs a new technique, "lazy doubling" with optimizing computing sequences; so, it is significantly faster than the previous algorithms. Mathematical analysis shows that the number of clocks required by the proposed algorithm is about 67 of those required by the carry-catcher squaring algorithm. To the best of our knowledge this is known to be the fastest squaring algorithm. Experimental results on the ATmega128 microprocessor show that our algorithm is about 1.5 times faster than the carry-catcher squaring algorithm in terms of the number of clocks required. As squaring is a key operation in public key cryptography, the proposed algorithm can contribute to lowering power consumption in secure WSNs (wireless sensor networks) or secure embedded systems.

KW - Low-end microprocessor

KW - Multi-precision squaring

KW - Public key cryptography

KW - Security

KW - Sensor networks

UR - http://www.scopus.com/inward/record.url?scp=84868641501&partnerID=8YFLogxK

U2 - 10.1016/j.jss.2012.06.074

DO - 10.1016/j.jss.2012.06.074

M3 - Article

AN - SCOPUS:84868641501

VL - 86

SP - 60

EP - 71

JO - Journal of Systems and Software

JF - Journal of Systems and Software

SN - 0164-1212

IS - 1

ER -