Integer multiplication algorithm with delayed carry mechanism for public key cryptosystems

Authors

  • Vladyslav Yu. KOVTUN National Aviation University
  • Andrew O. OKHRIMENKO National Aviation University

DOI:

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

Keywords:

multiplication of integers, software implementation, cryptographic transformation, cryptosystem, parallelism, delayed carry

Abstract

Authors have offered the approach to increase performance of software implementation of integer multiplication algorithm, for 32-bit and 64-bit platforms. The approach relies on delayed carry mechanism of significant bit in sum accumulation. This strategy allows preventing necessity to consider the significant bit carry at the each iteration of the sum accumulation loop. The delayed carry mechanism enables to reduce the total number of additions and apply the modern parallelization technologies effectively.

Author Biographies

Vladyslav Yu. KOVTUN, National Aviation University

Date and place of birth: 1978, Kіrovograd, Ukraine.

Education: Kharkiv Military University, 2000.

Current position & Functions: Associate Professor at IT-Security Dept since 2010.

Research interests: information security, quick arithmetic transformations in Galois fields, public key cryptosystems, cryptanalysis of cryptographic transformation with public-key.

Publications: over 40 scientific publications, papers in domestic & foreign scientific journals, international conferences proceedings, patents etc.

E-mail: vladislav.kovtun@gmail.com

Andrew O. OKHRIMENKO, National Aviation University

Date and place of birth: 1990, Vasilkiv, Kyiv region, Ukraine.

Education: National Aviation University, 2012.

Current position & Functions: Postgraduate student.

Research interests: information security, public key cryptosystems, network security, risk assessment, risk management.

Publications: over 40 scientific publications including papers, conference proceedings, international conferences materials, certificates of copyright registration etc.

E-mail: andrew.okhrimenko@gmail.com

References

Diffie W., Hellman M. E., “New directions in cryptography,” IEEE Transactions on Information Theory, vol. IT-22, pp. 644–654, 1976.

Comba P. G. Exponentiation cryptosystems on the IBM PC // IBM Systems Journal. –Vol. 29(4). 1990. pp. 526–538.

Brown M., Hankerson D., Lopez J., Menezes A. Software implementation of the NIST elliptic curves over prime fields // Research Report CORR 2000–55. Department of Combinatorics and Optimization, University of Waterloo. –Canada: Waterloo, Ontario, 2000. –21p.

Hong S-M., Oh S-Y., Yoon H. New Modular Multiplication algorithms for fast modular exponeniation // Advances in Cryptology Proceedings of Eurocrypt ’96. –Springer-Verlag. 1996. – pp.166-177.

Avanzi R. M. Aspects of hyperelliptic curves over large prime fields in software implementations // Cryptology ePrint Archive. – Report 2003/253. – 2003. – 23p. Available from: http://eprint.iacr.org

Paar C. Implementation options for finite filed arithmetic for elliptic curve cryptosystems // Worchester Polytechnic Institute. –ECC’99. – 1999. – 31p. Available from: http://www.ece.wpi.edu/ research/crypto.html

Gaubatz G. Versatile Montgomery multiplier architectures. Master thesis: electrical and computer engineering. – 2002. – Worcester polytechnic institute. –101p.

Johann Großschadl, Roberto M. Avanzi, Erkay Sava, Stefan Tillich. Energy-Efficient Software Implementation of Long Integer Modular Arithmetic // Advances in Cryptology Prociding in CHES’2005. – Springer-Verlag. 2005. LNCS 3659. pp. 75-90.

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

Weimerskirch A., Paar C. Generalizations of the Karatsuba Algorithm for Efficient Implementations. // Cryptology ePrint Archive. –Report 2006/224. –2006. –17p. Available from: http://eprint.iacr.org

Intel® 64 and IA-32 Architectures Optimization Reference Manual. Order Number: 248966-025. Available from: http://www.intel.com /content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf

The OpenMP API Specification for Parallel Programming. Available from: http://openmp.org /wp/openmp-specifications/

OpenMP in Visual C++. Available at: http:// http://msdn.microsoft.com/en-us/library /tt15eb9t.aspx

The GNU Multiply Precision Library (GMP). Available from: http://gmplib.org

LiDIA. Available from: https://www.cdc. informatik.tu-darmstadt.de/en/cdc

Multiprecision Unsigned Number Template Library (MUNTL). Available from: http://mktmk. narod.ru/eng/muntl/muntl.htm

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

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

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

BBNUM. Available from: http://www.iw-net.org/index.php?title=Bbnum_library

FLINT: Fast Library for Number Theory. Available from: http://www.flintlib.org

Multiprecision Integer and Rational Arithmetic C/C++ Library (MIRACL). Available from: http://indigo.ie/~mscott

LibTom Projects: LibTomMath, TomsFastMath. Available from: http://libtom.org

Abusharekh A., Gaj K. Comparative Analysis of Software Libraries for Public Key Cryptography // Software Performance Enhancement for Encryption and Decryption, SPEED’2007. June 11-12, 2007.

Giorgi P., Imbert L., Izard T. Multipartite Modular Multiplication. Preprint. Available from: http://hal.archives-ouvertes.fr/lirmm-00618437/fr/

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

NVIDIA. NVIDIA CUDA Programming Guide 2.0. Available from: http://developer.download.nvidia.com/compute/DevZone/docs/html/C/doc/CUDA_C_Programming_Guide.pdf

OpenCL The open standard for parallel programming of heterogeneous systems. Available from: http://www.khronos.org/opencl

Intel Threading Blocks. Available at: http://software.intel.com/en-us/articles/intel-tbb

Downloads

Issue

Vol. 19 No. 1 (2013)

Section

Cryptology