A fast inversion algorithm and low-complexity architecture over GF(2 m)

Sosun Kim; Nam Su Chang; Chang Han Kim; Young Ho Park; Jongin Lim

doi:10.1007/11596981_1

A fast inversion algorithm and low-complexity architecture over GF(2 ^m)

Sosun Kim, Nam Su Chang, Chang Han Kim, Young Ho Park, Jongin Lim

School of Cybersecurity

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

The performance of public-key cryptosystems is mainly appointed by the underlying finite field arithmetic. Among the basic arithmetic operations over finite field, the multiplicative inversion is the most time consuming operation. In this paper, a fast inversion algorithm over GF(2^m) with the polynomial basis representation is proposed, The proposed algorithm executes in about 27.5% or 45.6% less iterations than the extended binary gcd algorithm (EBGA) or the montgomery inverse algorithm (MIA) over GF(2¹⁶³), respectively. In addition, we propose a new hardware architecture to apply for low-complexity systems. The proposed architecture takes approximately 48.3% or 24.0% less the number of reduction operations than [4] or [8] over GF(2 ²³⁹), respectively. Furthermore, it executes in about 21.8% less the number of addition operations than [8] over GF(2¹⁶³).

Original language	English
Title of host publication	Computational Intelligence and Security - International Conference, CIS 2005, Proceedings
Publisher	Springer Verlag
Pages	1-8
Number of pages	8
ISBN (Print)	3540308199, 9783540308195
DOIs	https://doi.org/10.1007/11596981_1
Publication status	Published - 2005
Event	International Conference on Computational Intelligence and Security, CIS 2005 - Xi'an, China Duration: 2005 Dec 15 → 2005 Dec 19

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3802 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	International Conference on Computational Intelligence and Security, CIS 2005
Country/Territory	China
City	Xi'an
Period	05/12/15 → 05/12/19

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/11596981_1

Cite this

Kim, S., Chang, N. S., Kim, C. H., Park, Y. H., & Lim, J. (2005). A fast inversion algorithm and low-complexity architecture over GF(2 ^m). In Computational Intelligence and Security - International Conference, CIS 2005, Proceedings (pp. 1-8). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3802 LNAI). Springer Verlag. https://doi.org/10.1007/11596981_1

A fast inversion algorithm and low-complexity architecture over GF(2 ^m). / Kim, Sosun; Chang, Nam Su; Kim, Chang Han et al.
Computational Intelligence and Security - International Conference, CIS 2005, Proceedings. Springer Verlag, 2005. p. 1-8 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3802 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kim, S, Chang, NS, Kim, CH, Park, YH & Lim, J 2005, A fast inversion algorithm and low-complexity architecture over GF(2 ^m). in Computational Intelligence and Security - International Conference, CIS 2005, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3802 LNAI, Springer Verlag, pp. 1-8, International Conference on Computational Intelligence and Security, CIS 2005, Xi'an, China, 05/12/15. https://doi.org/10.1007/11596981_1

Kim S, Chang NS, Kim CH, Park YH, Lim J. A fast inversion algorithm and low-complexity architecture over GF(2 ^m). In Computational Intelligence and Security - International Conference, CIS 2005, Proceedings. Springer Verlag. 2005. p. 1-8. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11596981_1

Kim, Sosun ; Chang, Nam Su ; Kim, Chang Han et al. / A fast inversion algorithm and low-complexity architecture over GF(2 ^m). Computational Intelligence and Security - International Conference, CIS 2005, Proceedings. Springer Verlag, 2005. pp. 1-8 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ae327b0e4bb24eefa439f6ef51d65c6e,

title = "A fast inversion algorithm and low-complexity architecture over GF(2 m)",

abstract = "The performance of public-key cryptosystems is mainly appointed by the underlying finite field arithmetic. Among the basic arithmetic operations over finite field, the multiplicative inversion is the most time consuming operation. In this paper, a fast inversion algorithm over GF(2m) with the polynomial basis representation is proposed, The proposed algorithm executes in about 27.5% or 45.6% less iterations than the extended binary gcd algorithm (EBGA) or the montgomery inverse algorithm (MIA) over GF(2163), respectively. In addition, we propose a new hardware architecture to apply for low-complexity systems. The proposed architecture takes approximately 48.3% or 24.0% less the number of reduction operations than [4] or [8] over GF(2 239), respectively. Furthermore, it executes in about 21.8% less the number of addition operations than [8] over GF(2163).",

author = "Sosun Kim and Chang, {Nam Su} and Kim, {Chang Han} and Park, {Young Ho} and Jongin Lim",

year = "2005",

doi = "10.1007/11596981_1",

language = "English",

isbn = "3540308199",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "1--8",

booktitle = "Computational Intelligence and Security - International Conference, CIS 2005, Proceedings",

note = "International Conference on Computational Intelligence and Security, CIS 2005 ; Conference date: 15-12-2005 Through 19-12-2005",

}

TY - GEN

T1 - A fast inversion algorithm and low-complexity architecture over GF(2 m)

AU - Kim, Sosun

AU - Chang, Nam Su

AU - Kim, Chang Han

AU - Park, Young Ho

AU - Lim, Jongin

PY - 2005

Y1 - 2005

N2 - The performance of public-key cryptosystems is mainly appointed by the underlying finite field arithmetic. Among the basic arithmetic operations over finite field, the multiplicative inversion is the most time consuming operation. In this paper, a fast inversion algorithm over GF(2m) with the polynomial basis representation is proposed, The proposed algorithm executes in about 27.5% or 45.6% less iterations than the extended binary gcd algorithm (EBGA) or the montgomery inverse algorithm (MIA) over GF(2163), respectively. In addition, we propose a new hardware architecture to apply for low-complexity systems. The proposed architecture takes approximately 48.3% or 24.0% less the number of reduction operations than [4] or [8] over GF(2 239), respectively. Furthermore, it executes in about 21.8% less the number of addition operations than [8] over GF(2163).

AB - The performance of public-key cryptosystems is mainly appointed by the underlying finite field arithmetic. Among the basic arithmetic operations over finite field, the multiplicative inversion is the most time consuming operation. In this paper, a fast inversion algorithm over GF(2m) with the polynomial basis representation is proposed, The proposed algorithm executes in about 27.5% or 45.6% less iterations than the extended binary gcd algorithm (EBGA) or the montgomery inverse algorithm (MIA) over GF(2163), respectively. In addition, we propose a new hardware architecture to apply for low-complexity systems. The proposed architecture takes approximately 48.3% or 24.0% less the number of reduction operations than [4] or [8] over GF(2 239), respectively. Furthermore, it executes in about 21.8% less the number of addition operations than [8] over GF(2163).

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

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

U2 - 10.1007/11596981_1

DO - 10.1007/11596981_1

M3 - Conference contribution

AN - SCOPUS:33646838609

SN - 3540308199

SN - 9783540308195

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 8

BT - Computational Intelligence and Security - International Conference, CIS 2005, Proceedings

PB - Springer Verlag

T2 - International Conference on Computational Intelligence and Security, CIS 2005

Y2 - 15 December 2005 through 19 December 2005

ER -