ПОДХОДЫ К ПОВЫШЕНИЮ ПРОИЗВОДИТЕЛЬНОСТИ ПРОГРАММНОЙ РЕАЛИЗАЦИИ ОПЕРАЦИИ УМНОЖЕНИЯ В ПОЛЕ ЦЕЛЫХ ЧИСЕЛ
DOI:
https://doi.org/10.18372/2410-7840.14.2066Keywords:
умножение целых чисел, программная реализация, криптографические преобразования, криптосистема, поле целых чисел, распараллеливаниеAbstract
Авторами предлагается подход к увеличению производительности программной реализации алгоритма умножения в поле чисел для 32-х и 64-х разрядных платформ, который состоит в использовании механизма отложенного учета переноса из старшего разряда при накоплении суммы, что позволяет избежать необходимости учета переноса из старшего разряда на каждой итерации цикла накопления суммы. Отложенный перенос дает возможность уменьшить общее число операций сложения и эффективно применять существующие технологии распараллеливания.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 at: http://eprint.iacr.org
Paar C. Implementation options for finite filed arithmetic for elliptic curve cryptosystems // Worchester Polytechnic Institute. –ECC’99. –1999. –31p. Available at: 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. URL: 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 at: http://eprint.iacr.org
Intel® 64 and IA-32 Architectures Optimization Reference Manual. Order Number: 248966-025. Available at: http://intel.com
The OpenMP API Specification for Parallel Programming. Available at: http://openmp.org
OpenMP in Visual C++. Available at: http:// http://msdn.microsoft.com/en-us/library/tt15eb9t.aspx
The GNU Multiply Precision Library (GMP). URL: http://gmplib.org/
LiDIA. URL: https://www.cdc.informatik.tu-darmstadt.de/en/cdc
Multiprecision Unsigned Number Template Library (MUNTL). URL: http://mktmk.narod.ru/eng/muntl/muntl.htm
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/
BBNUM. URL: http://www.iw-net.org/index.php?title=Bbnum_library
FLINT: Fast Library for Number Theory. URL: http://www.flintlib.org
Multiprecision Integer and Rational Arithmetic C/C++ Library (MIRACL). URL: http://indigo.ie/~mscott
LibTom Projects: LibTomMath, TomsFastMath. URL: 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. URL: 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. 2008.
Downloads
How to Cite
Issue
Section
License
The scientific journal adheres to the principles of Open Access and provides free, immediate, and permanent access to all published materials without financial, technical, or legal barriers for readers.
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:
-
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.
