Montgomery Multiplication in GF(2k)

被引：188

作者：

Koç Ç.K. ^{[1
]}

Acar T. ^{[1
]}

机构：

[1] Electrical and Computer Engineering, Oregon State University, Corvallis

来源：

Designs, Codes and Cryptography | 1998年 / 14卷 / 1期

关键词：

Cryptography; Finite fields; Multiplication;

D O I：

10.1023/A:1008208521515

中图分类号：

学科分类号：

摘要：

We show that the multiplication operation c = a · b ·r-1 in the field GF(2k) can be implemented significantly faster in software than the standard multiplication, where r is a special fixed element of the field. This operation is the finite field analogue of the Montgomery multiplication for modular multiplication of integers. We give the bit-level and word-level algorithms for computing the product, perform a thorough performance analysis, and compare the algorithm to the standard multiplication algorithm in GF(2k). The Montgomery multiplication can be used to obtain fast software implementations of the discrete exponentiation operation, and is particularly suitable for cryptographic applications where k is large.

引用

页码：57 / 69

页数：12

共 17 条

[1]

Agnew G.B., Mullin R.C., Onyszchuk I., Vanstone S.A., An implementation for a fast public-key cryptosystem, Journal of Cryptology, 3, 2, pp. 63-79, (1996)

[2]

Agnew G.B., Mullin R.C., Vanstone S.A., An implementation of elliptic curve cryptosystems over F<sub>2155</sub>, IEEE Journal on Selected Areas in Communications, 11, 5, pp. 804-813, (1993)

[3]

Diffie W., Hellman M.E., New directions in cryptography, IEEE Transactions on Information Theory, 22, pp. 644-654, (1976)

[4]

Dusse S.R., Kaliski Jr. B.S., A cryptographic library for the Motorola DSP56000, Advances in Cryptology - EUROCRYPT 90, Lecture Notes in Computer Science, 473, pp. 230-244, (1990)

[5]

Harper G., Menezes A., Vanstone S., Public-key cryptosystems with very small key lengths, Advances in Cryptology - EUROCRYPT 92, Lecture Notes in Computer Science, 658, pp. 163-173, (1992)

[6]

Knuth D.E., The Art of Computer Programming: Seminumerical Algorithms, 2, (1981)

[7]

Koblitz N., A Course in Number Theory and Cryptography, (1994)

[8]

Koc C.K., Acar T., Fast software exponentiation in GF(2<sup>k</sup>), Proceedings, 9th Symposium on Computer Arithmetic, pp. 225-231, (1997)

[9]

Lidl R., Niederreiter H., Introduction to Finite Fields and Their Applications, (1994)

[10]

McEliece R.J., Finite Fields for Computer Scientists and Engineers, (1987)

← 1 2 →