Методи підвищення продуктивності операції інвертування у двійковому полі
DOI:
https://doi.org/10.18372/2225-5036.20.6575Ключові слова:
асиметричні криптографічні перетворення, мультиплікативне інвертування, розширений алгоритм Евкліда, двійкове поле, поліномАнотація
Автори пропонують ряд методів збільшення продуктивності алгоритму мультиплікативного інвертування у двійковому полі на основі розширеного алгоритму Евкліда. Перший метод ґрунтується на специфіці самого розширеного алгоритму Евкліда: інваріантний поліном або залишається без змін, або обмінюється вмістом з інваріантним поліномом u, це дозволяє уникнути необхідності обчислення ступеня полінома. Наступний метод заснований на методі «наступного підходящого індексу» при обчисленні ступеня полінома: враховуючи той факт, що в процесі роботи розширеного алгоритму Евкліда, ступінь інваріантного полінома зменшується хоча б на 1, то при подальшому обчисленні ступеня полінома можна враховувати поточне значення ступеня. Запропоновані методи дозволяють збільшити продуктивність програмної реалізації інвертування для 32-х розрядних платформ на 15-20%.Посилання
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.
