ПОДХОДЫ К ПОВЫШЕНИЮ ПРОИЗВОДИТЕЛЬНОСТИ ПРОГРАММНОЙ РЕАЛИЗАЦИИ ОПЕРАЦИИ УМНОЖЕНИЯ В ПОЛЕ ЦЕЛЫХ ЧИСЕЛ
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
Issue
Section
License
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
