Performance increasing methods for binary field inversion
DOI:
https://doi.org/10.18372/2225-5036.20.6575Keywords:
asymmetric cryptography transformation, multiplicative inversion, Extended Euclidean Algorithm, binary field, polynomialAbstract
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%.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.
