Article

A Scalable and Unified Multiplier Architecture for Finite Fields GF(p) and GF(2m)

Authors:

Alexandre F. Tenca,

Çetin Kaya KoçAuthors Info & Claims

CHES '00: Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems

Pages 277 - 292

Published: 17 August 2000 Publication History

Abstract

We describe a scalable and unified architecture for a Montgomery multiplication module which operates in both types of finite fields GF(p) and GF(2^m). The unified architecture requires only slightly more area than that of the multiplier architecture for the field GF(p). The multiplier is scalable, which means that a fixed-area multiplication module can handle operands of any size, and also, the wordsize can be selected based on the area and performance requirements. We utilize the concurrency in the Montgomery multiplication operation by employing a pipelining design methodology. The upper limit on the precision of the scalable and unified Montgomery multiplier is dictated only by the available memory to store the operands and internal results, and the module is capable of performing infinite-precision Montgomery multiplication in both types of finite fields.

References

[1]

G. B. Agnew, R. C. Mullin, and S. A. Vanstone. An implementation of elliptic curve cryptosystems over F ₂155. IEEE Journal on Selected Areas in Communications, 11(5):804-813, June 1993.

[2]

A. Bernal and A. Guyot. Design of a modular multiplier based on Montgomery's algorithm. In 13th Conference on Design of Circuits and Integrated Systems, pages 680-685, Madrid, Spain, November 17-20 1998.

[3]

W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22:644-654, November 1976.

[4]

S. E. Eldridge and C. D. Walter. Hardware implementation of Montgomery's modular multiplication algorithm. IEEE Transactions on Computers, 42(6):693- 699, June 1993.

[5]

Steve Furber. ARM System Architecture. Addison-Wesley, Reading, MA, 1997.

[6]

B. S. Kaliski Jr. The Montgomery inverse and its applications. IEEE Transactions on Computers, 44(8):1064-1065, August 1995.

[7]

N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48(177):203-209, January 1987.

[8]

Ç. K. Koç. High-Speed RSA Implementation. Technical Report TR 201, RSA Laboratories, 73 pages, November 1994.

[9]

Ç. K. Koç and T. Acar. Montgomery multiplication in GF(2^k). Designs, Codes and Cryptography, 14(1):57-69, April 1998.

[10]

Ç. K. Koç, T. Acar, and B. S. Kaliski Jr. Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro, 16(3):26-33, June 1996.

[11]

P. Kornerup. High-radix modular multiplication for cryptosystems. In E. Swartzlander, Jr., M. J. Irwin, and G. Jullien, editors, Proceedings, 11th Symposium on Computer Arithmetic, pages 277-283, Windsor, Ontario, June 29 - July 2 1993. IEEE Computer Society Press, Los Alamitos, CA.

[12]

A. J. Menezes. Elliptic Curve Public Key Cryptosystems. Kluwer Academic Publishers, Boston, MA, 1993.

[13]

P. L. Montgomery. Modular multiplication without trial division. Mathematics of Computation, 44(170):519-521, April 1985.

[14]

D. Naccache and D. M'Raïhi. Cryptographic smart cards. IEEE Micro, 16(3):14- 24, June 1996.

[15]

National Institute for Standards and Technology. Digital Signature Standard (DSS). FIPS PUB 186-2, January 2000.

[16]

H. Orup. Simplifying quotient determination in high-radix modular multiplication. In S. Knowles and W. H. McAllister, editors, Proceedings, 12th Symposium on Computer Arithmetic, pages 193-199, Bath, England, July 19-21 1995. IEEE Computer Society Press, Los Alamitos, CA.

[17]

J.-J. Quisquater and C. Couvreur. Fast decipherment algorithm for RSA publickey cryptosystem. Electronics Letters, 18(21):905-907, October 1982.

[18]

A. Royo, J. Moran, and J. C. Lopez. Design and implementation of a coprocessor for cryptography applications. In European Design and Test Conference, pages 213-217, Paris, France, March 17-20 1997.

[19]

E. Savaş and Ç. K. Koç. The Montgomery modular inverse - revisited. IEEE Transactions on Computers, 49(8), July 2000. To appear.

[20]

A. F. Tenca and Ç. K. Koç. A scalable architecture for Montgomery multiplication. In Ç. K. Koç and C. Paar, editors, Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science, No. 1717, pages 94-108. Springer, Berlin, Germany, 1999.

[21]

C. D. Walter. Space/Time trade-offs for higher radix modular multiplication using repeated addition. IEEE Transactions on Computers, 46(2):139-141, February 1997.

Cited By

Malik M(2010)Efficient implementation of elliptic curve cryptography using low-power digital signal processorProceedings of the 12th international conference on Advanced communication technology10.5555/1833006.1833115(1464-1468)Online publication date: 7-Feb-2010
https://dl.acm.org/doi/10.5555/1833006.1833115
Großschädl J(2009)Full-custom VLSI design of a unified multiplier for elliptic curve cryptography on RFID tagsProceedings of the 5th international conference on Information security and cryptology10.5555/1950111.1950146(366-382)Online publication date: 12-Dec-2009
https://dl.acm.org/doi/10.5555/1950111.1950146
Tanimura KNara RKohara SShimizu KShi YTogawa NYanagisawa MOhtsuki TKyung CChoi KHa S(2008)Scalable unified dual-radix architecture for montgomery multiplication in GF(P) and GF(2)Proceedings of the 2008 Asia and South Pacific Design Automation Conference10.5555/1356802.1356970(697-702)Online publication date: 21-Jan-2008
https://dl.acm.org/doi/10.5555/1356802.1356970
Show More Cited By

A Scalable and Unified Multiplier Architecture for Finite Fields GF(p) and GF(2m)
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis

Recommendations

A Bit-Serial Unified Multiplier Architecture for Finite Fields GF(p) and GF(2m)
CHES '01: Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems

The performance of elliptic curve cryptosystems is primarily determined by an efficient implementation of the arithmetic operations in the underlying finite field. This paper presents a hardware architecture for a unified multiplier which operates in ...
Scalable unified dual-radix architecture for montgomery multiplication in GF(P) and GF(2ⁿ)
ASP-DAC '08: Proceedings of the 2008 Asia and South Pacific Design Automation Conference

Modular multiplication is the most dominant arithmetic operation in elliptic curve cryptography (ECC), which is a type of public-key cryptography. Montgomery multiplication is commonly used as a technique for the modular multiplication and required ...
Novel Radix Finite Field Multiplier for GF(2m)

In this paper, a new High-Radix Finite Field multiplication algorithm for GF(2m) is proposed for the first time. The proposed multiplication algorithm can operate in a Digit-serial fashion, and hence can give a trade-off between the speed, the area , ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CHES '00: Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems

August 2000

354 pages

ISBN:354041455X

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 August 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Malik M(2010)Efficient implementation of elliptic curve cryptography using low-power digital signal processorProceedings of the 12th international conference on Advanced communication technology10.5555/1833006.1833115(1464-1468)Online publication date: 7-Feb-2010
https://dl.acm.org/doi/10.5555/1833006.1833115
Großschädl J(2009)Full-custom VLSI design of a unified multiplier for elliptic curve cryptography on RFID tagsProceedings of the 5th international conference on Information security and cryptology10.5555/1950111.1950146(366-382)Online publication date: 12-Dec-2009
https://dl.acm.org/doi/10.5555/1950111.1950146
Tanimura KNara RKohara SShimizu KShi YTogawa NYanagisawa MOhtsuki TKyung CChoi KHa S(2008)Scalable unified dual-radix architecture for montgomery multiplication in GF(P) and GF(2)Proceedings of the 2008 Asia and South Pacific Design Automation Conference10.5555/1356802.1356970(697-702)Online publication date: 21-Jan-2008
https://dl.acm.org/doi/10.5555/1356802.1356970
Vejda TPage DGroßschädl J(2007)Instruction set extensions for pairing-based cryptographyProceedings of the First international conference on Pairing-Based Cryptography10.5555/2394336.2394355(208-224)Online publication date: 2-Jul-2007
https://dl.acm.org/doi/10.5555/2394336.2394355
Meurice de Dormale GQuisquater J(2007)High-speed hardware implementations of Elliptic Curve CryptographyJournal of Systems Architecture: the EUROMICRO Journal10.5555/1224257.122454453:2-3(72-84)Online publication date: 1-Feb-2007
https://dl.acm.org/doi/10.5555/1224257.1224544
Fan HHasan M(2007)A New Approach to Subquadratic Space Complexity Parallel Multipliers for Extended Binary FieldsIEEE Transactions on Computers10.1109/TC.2007.1956:2(224-233)Online publication date: 1-Feb-2007
https://dl.acm.org/doi/10.1109/TC.2007.19
Tillich SGroßschädl J(2007)VLSI Implementation of a Functional Unit to Accelerate ECC and AES on 32-Bit ProcessorsProceedings of the 1st international workshop on Arithmetic of Finite Fields10.1007/978-3-540-73074-3_5(40-54)Online publication date: 21-Jun-2007
https://dl.acm.org/doi/10.1007/978-3-540-73074-3_5
Fan HHasan M(2006)Relationship between GF(2^m) Montgomery and Shifted Polynomial Basis Multiplication AlgorithmsIEEE Transactions on Computers10.1109/TC.2006.15255:9(1202-1206)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1109/TC.2006.152
Koschuch MLechner JWeitzer AGroßschädl JSzekely ATillich SWolkerstorfer J(2006)Hardware/software co-design of elliptic curve cryptography on an 8051 microcontrollerProceedings of the 8th international conference on Cryptographic Hardware and Embedded Systems10.1007/11894063_34(430-444)Online publication date: 10-Oct-2006
https://dl.acm.org/doi/10.1007/11894063_34
Majeed J(2005)FPGA based communication security for wireless sensor networksProceedings of the 4th WSEAS International Conference on Electronic, Signal Processing and Control10.5555/1366599.1366635(1-8)Online publication date: 25-Apr-2005
https://dl.acm.org/doi/10.5555/1366599.1366635
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents