Architectural Enhancements for Montgomery Multiplication on Embedded RISC Processors

Johann Großschädl; Guy Armand Kamendje

doi:10.1007/978-3-540-45203-4_32

Architectural Enhancements for Montgomery Multiplication on Embedded RISC Processors

Johann Großschädl, Guy Armand Kamendje

Institute of Applied Information Processing and Communications (7050)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

Montgomery multiplication normally spends over 90% of its execution time in inner loops executing some kind of multiply-and-add operations. The performance of these critical code sections can be greatly improved by customizing the processor’s instruction set for low-level arithmetic functions. In this paper, we investigate the potential of architectural enhancements for multiple-precision Montgomery multiplication according to the so-called Finely Integrated Product Scanning (FIPS) method. We present instruction set extensions to accelerate the FIPS inner loop operation based on the availability of a multiply/accumulate (MAC) unit with a wide accumulator. Finally, we estimate the execution time of a 1024-bit Montgomery multiplication on an extended MIPS32 core and discuss the impact of the multiplier latency.

Original language	English
Title of host publication	Applied Cryptography and Network Security — ACNS 2003
Place of Publication	Berlin
Publisher	Springer Verlag
Pages	418-434
ISBN (Print)	3-540-20208-0
DOIs	https://doi.org/10.1007/978-3-540-45203-4_32
Publication status	Published - 2003
Event	1st International Conference on Applied Cryptography and Network Security: ACNS 2003 - Kunming, China Duration: 16 Oct 2003 → 19 Oct 2003

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	2846

Conference

Conference	1st International Conference on Applied Cryptography and Network Security
Country/Territory	China
City	Kunming
Period	16/10/03 → 19/10/03

Treatment code (Nähere Zuordnung)

Application
Experimental

Access to Document

10.1007/978-3-540-45203-4_32

ACNS2003_AEMFinal published version, 318 KB

Instruction Set Extensions and Architectural Enhancements for Public-Key Cryptography on General-Purpose RISC Processors
Tillich, S., Großschädl, J., Szekely, A. & Posch, K.
1/12/03 → 31/10/06
Project: Research project
Crypto Module with USB Interface (USB_CRYPT)
Wolkerstorfer, J. & Aigner, M. J.
1/01/01 → 31/12/03
Project: Research project

Cite this

Architectural Enhancements for Montgomery Multiplication on Embedded RISC Processors. / Großschädl, Johann; Kamendje, Guy Armand.
Applied Cryptography and Network Security — ACNS 2003. Berlin: Springer Verlag, 2003. p. 418-434 (Lecture Notes in Computer Science; Vol. 2846).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Großschädl, J & Kamendje, GA 2003, Architectural Enhancements for Montgomery Multiplication on Embedded RISC Processors. in Applied Cryptography and Network Security — ACNS 2003. Lecture Notes in Computer Science, vol. 2846, Springer Verlag, Berlin, pp. 418-434, 1st International Conference on Applied Cryptography and Network Security, Kunming, China, 16/10/03. https://doi.org/10.1007/978-3-540-45203-4_32

@inproceedings{1d033a461580487f97ae055f35c9caf1,

title = "Architectural Enhancements for Montgomery Multiplication on Embedded RISC Processors",

abstract = "Montgomery multiplication normally spends over 90% of its execution time in inner loops executing some kind of multiply-and-add operations. The performance of these critical code sections can be greatly improved by customizing the processor{\textquoteright}s instruction set for low-level arithmetic functions. In this paper, we investigate the potential of architectural enhancements for multiple-precision Montgomery multiplication according to the so-called Finely Integrated Product Scanning (FIPS) method. We present instruction set extensions to accelerate the FIPS inner loop operation based on the availability of a multiply/accumulate (MAC) unit with a wide accumulator. Finally, we estimate the execution time of a 1024-bit Montgomery multiplication on an extended MIPS32 core and discuss the impact of the multiplier latency.",

author = "Johann Gro{\ss}sch{\"a}dl and Kamendje, {Guy Armand}",

year = "2003",

doi = "10.1007/978-3-540-45203-4_32",

language = "English",

isbn = "3-540-20208-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "418--434",

booktitle = "Applied Cryptography and Network Security — ACNS 2003",

address = "Germany",

note = "1st International Conference on Applied Cryptography and Network Security : ACNS 2003 ; Conference date: 16-10-2003 Through 19-10-2003",

}

TY - GEN

T1 - Architectural Enhancements for Montgomery Multiplication on Embedded RISC Processors

AU - Großschädl, Johann

AU - Kamendje, Guy Armand

PY - 2003

Y1 - 2003

N2 - Montgomery multiplication normally spends over 90% of its execution time in inner loops executing some kind of multiply-and-add operations. The performance of these critical code sections can be greatly improved by customizing the processor’s instruction set for low-level arithmetic functions. In this paper, we investigate the potential of architectural enhancements for multiple-precision Montgomery multiplication according to the so-called Finely Integrated Product Scanning (FIPS) method. We present instruction set extensions to accelerate the FIPS inner loop operation based on the availability of a multiply/accumulate (MAC) unit with a wide accumulator. Finally, we estimate the execution time of a 1024-bit Montgomery multiplication on an extended MIPS32 core and discuss the impact of the multiplier latency.

AB - Montgomery multiplication normally spends over 90% of its execution time in inner loops executing some kind of multiply-and-add operations. The performance of these critical code sections can be greatly improved by customizing the processor’s instruction set for low-level arithmetic functions. In this paper, we investigate the potential of architectural enhancements for multiple-precision Montgomery multiplication according to the so-called Finely Integrated Product Scanning (FIPS) method. We present instruction set extensions to accelerate the FIPS inner loop operation based on the availability of a multiply/accumulate (MAC) unit with a wide accumulator. Finally, we estimate the execution time of a 1024-bit Montgomery multiplication on an extended MIPS32 core and discuss the impact of the multiplier latency.

U2 - 10.1007/978-3-540-45203-4_32

DO - 10.1007/978-3-540-45203-4_32

M3 - Conference paper

SN - 3-540-20208-0

T3 - Lecture Notes in Computer Science

SP - 418

EP - 434

BT - Applied Cryptography and Network Security — ACNS 2003

PB - Springer Verlag

CY - Berlin

T2 - 1st International Conference on Applied Cryptography and Network Security

Y2 - 16 October 2003 through 19 October 2003

ER -

Architectural Enhancements for Montgomery Multiplication on Embedded RISC Processors

Abstract

Publication series

Conference

Treatment code (Nähere Zuordnung)

Access to Document

Fingerprint

Projects

Instruction Set Extensions and Architectural Enhancements for Public-Key Cryptography on General-Purpose RISC Processors

Crypto Module with USB Interface (USB_CRYPT)

Cite this