ПОДХОДЫ К ПОВЫШЕНИЮ ПРОИЗВОДИТЕЛЬНОСТИ ПРОГРАММНОЙ РЕАЛИЗАЦИИ ОПЕРАЦИИ УМНОЖЕНИЯ В ПОЛЕ ЦЕЛЫХ ЧИСЕЛ
DOI:
https://doi.org/10.18372/2410-7840.14.2066Ключові слова:
умножение целых чисел, программная реализация, криптографические преобразования, криптосистема, поле целых чисел, распараллеливаниеАнотація
Авторами предлагается подход к увеличению производительности программной реализации алгоритма умножения в поле чисел для 32-х и 64-х разрядных платформ, который состоит в использовании механизма отложенного учета переноса из старшего разряда при накоплении суммы, что позволяет избежать необходимости учета переноса из старшего разряда на каждой итерации цикла накопления суммы. Отложенный перенос дает возможность уменьшить общее число операций сложения и эффективно применять существующие технологии распараллеливания.Посилання
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.
##submission.downloads##
Номер
Розділ
Ліцензія
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:- Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
- Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
- Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).