Performance increasing methods for binary field inversion

Authors

  • Владислав Юрійович Ковтун Национальный авиационный университет
  • Марія Григорівна Булах Национальный авиационный университет

DOI:

https://doi.org/10.18372/2225-5036.20.6575

Keywords:

asymmetric cryptography transformation, multiplicative inversion, Extended Euclidean Algorithm, binary field, polynomial

Abstract

Authors propose several methods for increasing performance of multiplicative inversion algorithm in binary fields based on Extended Euclidean Algorithm. First method is based on Extended Euclidean Algorithm specific: either invariant polynomial   is a same or swaps with invariant polynomial u. Thus, it does not necessary to compute degree of polynomial  . Next method is based on «next fit element» in polynomial degree computation: on each iteration of Extended Euclidean Algorithm execution, degree of invariant polynomial   decreases at list one. On next iteration Extended Euclidean Algorithm degree searches from where it left off the previous time. Proposed methods allow to increase performance of software implementation of inversion in binary field for 32-bit architectures on 15-20%.

Author Biographies

Владислав Юрійович Ковтун, Национальный авиационный университет

Год и место рождения: 1978, Кировоград, Украина.

Образование: Харьковский Военный Университет, 2000.

Должность: доцент кафедры безопасности информационных технологий с 2010 года.

Научные интересы: информационная безопасность, быстрые арифметические преобразования в полях Галуа, криптосистемы с открытым ключом, криптоанализ криптографических преобразований с открытым ключом.

Публикации: более 50 научных публикаций, среди которых статьи в специализированых и зарубежных научных журналах, материалы конференций, патенты и др.

Марія Григорівна Булах, Национальный авиационный университет

Год и место рождения: 1989, Львов, Украина.

Образование: Национальный авиационный университет, 2010.

Должность: соискатель кафедры безопасности информационных технологий с 2014 года.

Научные интересы: информационная безопасность, быстрые арифметические преобразования в полях Галуа, криптосистемы с открытым ключом, криптоанализ криптографических преобразований с открытым ключом.

References

IEEE Std 1363-2000: Standard Specifications For Public Key Cryptography. Institute of Electrical and Electronics Engineers, 2000. — 228 p. URL: http://grouper.ieee.org/groups/1363/

ISO/IEC 15946-2:2002. Information technology — Security techniques — Cryptographic techniques based on elliptic curves —Part 2: Digital signatures, 2007, 36 p.

ДСТУ 4145-2002. Информационные технологии. Криптографическая защита информации. Цифровая подпись, основанная на эллиптических кривых. Формирование и проверка. — К. : Держ-стандарт України, 2003. — 39 с.

D. Hankerson, J. Hernandez, A. Menezes. Software implementation of Elliptic Curve Cryptography over binary fields. Proceedings of Workshop on Cryptographic Hardware and Embedded System, 2000, LNCS Vol. 1965, pp. 1-24.

Intel® 64 and IA-32 Architectures Optimization Reference Manual. Order Number: 248966-025, 2013, 660 p. URL: http://www.intel.com/ content/www/us/en/architecture-and-technology/64-ia-32-architectures-optimization-manual.html

Giorgi P. Izard T, Tisserand A. Comparison of Modular Arithmetic Algorithms on GPUs // ParCo'09: International Conference on Parallel Computing, France, 2009, 8 p. URL: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00424288/fr/

Zhijie Jerry Shi and Hai Yan. Software Implementations of Elliptic Curve Cryptography // International Journal of Network Security, 2008, Vol.7, No.2, pp. 57–166.

TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks. URL: http://discovery.csc.ncsu.edu/software/TinyECC/

Galois Field Arithmetic Library. URL: http://www.partow.net/projects/galois/

MPFQ: Fast Finite Fields Library. URL: http://mpfq.gforge.inria.fr/

LibTom Projects: LibTomPoly. URL: http://libtom.org

Sean Eron Anderson. Bit Twiddling Hacks. URL: http://graphics.stanford.edu/~seander/bithacks.html

National Institute of Standards and Technology, Recommended Elliptic Curves for Federal Government Use, Appendix to FIPS 186-2, 2000, 43 p.

NVIDIA. NVIDIA CUDA Programming Guide 5.0, 2013, 214 p. URL: http://docs.nvidia.com/ cuda/cuda-c-programming-guide/

M. Bluhm, S. Gueron. Fast Software Implementation of Binary Elliptic Curve Cryptography // Cryptology ePrint Archive, Report 2013/741, 2013, 19 p. URL: http://eprint.iacr.org/2013/741.pdf

E. M. Mahé, J.-M. Chauvet. Fast GPGPU-Based Elliptic Curve Scalar Multiplication // Cryptology ePrint Archive, Report 2014/198, 2014, 9 p. URL: http://eprint.iacr.org/2014/198.pdf

Aaron E. Cohen, Keshab K. Parhi. GPU accelerated elliptic curve cryptography in GF(2m) // 53rd IEEE International Midwest Symposium on Circuits and Systems (MWSCAS), 2010, pp. 57-60.

Tony Cheneau, Aymen Boudguiga, Maryline Laurent. Significantly Improved Performances Of The Cryptographically Generated Addresses Thanks To ECC And GPGPU // Computers and Security Journal (CoSe), Elsevier, 2010, Vol. 29, pp. 419-431.

Downloads

Published

2014-05-02

How to Cite

Ковтун, В. Ю., & Булах, М. Г. (2014). Performance increasing methods for binary field inversion. Ukrainian Scientific Journal of Information Security, 20(1), 55–61. https://doi.org/10.18372/2225-5036.20.6575

Issue

Vol. 20 No. 1 (2014)

Section

Cryptology

License

The scientific journal "Ukrainian Scientific Journal of Information Security" adheres to the principles of open science and provides free, free and permanent access to all published materials. The goal of the policy is to increase the visibility, citation and impact of the results of scientific research in the field of information security. The journal works according to the principles of Open Access and does not charge a fee for access to published articles.

All articles are published in Open Access under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.

Copyright

Authors who publish their works in the journal “Ukrainian Scientific Journal of Information Security”:

  • retain the copyright to their publications;

  • grant the journal the right of first publication of the article;

  • agree to the distribution of their materials under the CC BY 4.0 license;

  • have the right to reuse, archive, and distribute their works (including in institutional and subject repositories), provided that proper reference is made to the original publication in the journal.