Approaches to performance increasing of extended Euclidean algorithm for double precision division on single precision large integers

Authors

  • Сергей Александрович Гнатюк Национальный авиационный университет
  • Владислав Юрьевич Ковтун Национальный авиационный университет
  • Оксана Михайловна Бердник Национальный авиационный университет
  • Мария Григорьевна Ковтун Национальный авиационный университет

DOI:

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

Keywords:

division, remainder in division, large integer’s modular reduction, extended Euclidean algorithm

Abstract

Public key cryptography has significant processing and spatial complexity. In this regard, relevant scientific and technical challenge is to improve the performance of such transformations. In this paper proposed approaches of large integer’s division operation with double precision on single precision based on the Extended Euclidean Algorithm. These approaches include handling non-zero machine words in the most frequently used operations; using an semi-exact comparison of large integer, without for-word comparison; knowledge of the of Bézout equation parameters changing. These approaches are implemented in the modified algorithm, which has been software implemented. In experiments were compared numbers with double binary size dividend and single binary size divider with ratios for various filled and total binary length. Modified algorithm showed higher performance in 1.5-3 times, with dividend and divisor increasing binary length.

Author Biographies

Сергей Александрович Гнатюк, Национальный авиационный университет

Дата и место рождения: 1985 год, г. Нетешин, Хмельницкая область, Украина.

Образование: Национальный авиационный университет, 2007 год.

Должность: доцент кафедры безопасности информационных технологий с 2012 года.

Научные интересы: информационная безопасность, квантовая криптография, защита гражданской авиации от киберугроз, менеджмент инцидентов информационной безопасности.

Публикации: более 100 научных публикаций, среди которых монографии, статьи в международных и отечественных рецензированных специализированных журналах, патенты, авторские свидетельства на программные продукты и т.п.

Владислав Юрьевич Ковтун, Национальный авиационный университет

Дата и место рождения: 1978 год, г. Кировоград, Украина.

Образование: Харьковский военный университет, 2000 год.

Должность: доцент кафедры безопасности информационных технологий.

Научные интересы: информационная безопасность, быстрые арифметические преобразования в полях Галуа, криптосистемы с открытым ключом, криптоанализ криптографических преобразований с открытым ключом.

Публикации: более 50 научных публикаций, среди которых статьи в специализированных и зарубежных научных журналах, материалы конференций, патенты и др.

Оксана Михайловна Бердник, Национальный авиационный университет

Год и место рождения: 1973 год, г. Нежин, Черниговская область, Украина.

Образование: Нежинский государственный педагогический институт им. Н.В. Гоголя (с 2004 года – Нежинский государственный университет имени Николая Гоголя), 1996 год.

Должность: доцент кафедры прикладной математики с 2012 года.

Научные интересы: математическое моделирование, вычислительные методы, прикладные задачи математики.

Публикации: более 30 публикаций, среди которых научные статьи, материалы и тезисы докладов на конференциях, учебные пособия.

Мария Григорьевна Ковтун, Национальный авиационный университет

Дата и место рождения: 1989 год, г. Львов, Украина.

Образование: Национальный авиационный университет, 2011 год.

Должность: аспирант кафедры безопасности информационных технологий с 2014 года.

Научные интересы: информационная безопасность, быстрые криптографические преобразования в полях Галуа, криптосистемы с открытым ключом, криптоанализ криптографических преобразований с открытым ключом.

References

Библиотека многократной точности GMP. URL: https://gmplib.org

Bhattacharya J.: Rudiments of computer science. Kolkata.2010.ISBN: 978-93-80599-02-1

Stehle, P.Zimmermann: A Binary Recursive Gcd Algorithm. Algorithmic Number Theory. LNCS Volume 3076, 2004, pp 411-425. [4] L.Lhote, B.Vallée: Sharp Estimates for the Main Parameters of the Euclid Algorithm. LATIN 2006: Theoretical Informatics. LNCS Volume 3887, 2006, pp 689-702.

V. Dupaquis, A. Venelli: Redundant Modular Reduction Algorithms. Smart Card Research and Advanced Applications. LNCS Volume 7079, 2011, pp 102-114.

Уоррен Генри С. Алгоритмические трюки для программистов: Пер. с анг. – М.: Издательский дом «Вильямс» 2003. – 288 с.: ил. – Парал. тит. англ.

ДСТУ 4145–2002. Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривих. Формування та перевірка. – К.: Держстандарт України, 2002. –40с.

IEEE P1363–2000: Standard Specifications for Public Key Cryptography. – 2000. – 206 p. URL: http://www.ieee.org

P. Barrett. Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor. Proceedings CRYPTO'86, pp. 311-323.

L. Hars. Long Modular Multiplication for Cryptographic Applications.//Cryptographic Hardware and Embedded Systems - CHES 2004.//LNCS Volume 3156, 2004, pp 45-61

Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. - CRC Press; First edition (December 16, 1996), Fifth Printing. - 2001. –780 p.

P. Montgomery. Modular multiplication without trial division. Mathematics of Computation, 44(170):519–521, 1985.

Ковтун В.Ю., Охрименко А.А. Метод повышения производительности операции приве-дения по простому модулю. – Информационные технологи и системы в управлении, образовании, науке: Монография / Под ред.. проф. В.С. Пономаренко. – Х.: Вид-во ТОВ «Щедра садиба плюс», 2014.– С. 204-220.

J.-C. Bajard, S. Duquesne, M. Ercegovac. Combining leak–resistant arithmetic for elliptic curves defined over Fp and RNS representation. Publications Mathématiques de Besançon : Algèbre et Théorie des Nombres, 2013, pp.67-87. URL: http://pmb.univ-fcomte.fr

M. Taschwer. Modular multiplication using special prime moduli. Kommunikationssicherheit im Zeichen des Internet. DuD-Fachbeiträge 2001, pp 346-371.

N. Guillermin. A compressor for secure and high speed modular arithetic. Technical Report 354, Cryptology ePrint Archive (2011). URL: https://eprint.iacr.org/2015/193.pdf.

W. Hasenplaugh, G. Gaubatz, V. Gopal. Fast Modular Reduction. Proceedings of the 18th IEEE Symposium on Computer Arithmetic, pp 225-229 . IEEE Computer Society Washington, DC, USA 2007.

P. Giorgi, L. Imbert, T. Izard. Multipartite Modular Multiplication. RR-11024, 2011, pp.25.

J. Guajardo, R. Blumel, U. Krieger, C. Paar: Efficient Implementation of Elliptic Curve Crypto systems on the TI MSP430x33x Family of Microcontrollers. Public Key Cryptography. LNCS Volume 1992, 2001, pp. 365-382.

D. Hankerson, A. Menezes, and S.A. Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag, 2004. p. 98.

Chae Ho on Lim, Hyo Sun Hwang. Fast Modular Reduction With Precomputation. In Proceedings of Korea-Japan Joint Workshop on Information Security and Cryptology, Lecture.

Z. Cao, R. Wei, Xiao dong Lin. A Fast Modular Reduction Method. IACR Cryptology ePrint Archive, 2014. URL: https://eprint.iacr.org/2014/040.pdf

A. Bosselaers, R Govaerts, J Vandewalle. Comparions of three modular reduction functions. Advances in Cryptology—CRYPTO’93, 175-186.

Jerome A. Solinas. Generalized Mersenne Numbers. http://cacr.uwaterloo.ca/techreports/1999/ corr99-39.pdf

D. E. Knuth. The Art of Computer Programming: Seminumerical Algorithms. Addison-Wesley Publishing Company, Reading, MA, 1981.

H. Wu On Computation of Polynomial Modular Reduction, Tech. Rep., Centre of Applied Cryptographic Research, University of Waterloo, June 2000.

D. Takahashi. A Parallel Algorithm for Multiple-Precision Division by a Single-Precision Integer. Large-Scale Scientific Computing. LNCS Volume 4818, 2008, pp 729-736.

H.-Y. Lo, T.-Y. Chang, M.-C. Lee. Parallel Unidirectional Division Algorithms and Implementations. Journal of the Chinese Institute of Engineers, Taylor & Francis, Volume 24, Issue 4, July 2001, Pages 487-496.

Comba, P. G. Exponentiation cryptosystems on the IBM PC, IBM Systems Journal, Vol. 29, No. 4, December 1990. http://eprint.iacr.org/2012/482.pdf, http://eprint.iacr.org/2012/170.pdf

Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР. — 1962. — Т. 145. — № 2.

M. Johnson, B. Phung, T. Shackelford, S. Rueangvivatanakij. Modular Reduction of Large Integers Using Classical, Barrett, Montgomery Algorithms. URL: http://teal.gmu.edu/courses/ECE646/project/reports_2002/IP-1_report.pdf [32] S. Gueron. Enhanced Montgomery Multi-plication. Cryptographic Hardware and Embedded Systems — CHES 2002. Lecture Notes in Computer Science Volume 2523, 2003, pp 46-56.

N. Emmart, C.-C. Weems: Parallel multiple precision division by a single precision divisor. HiPC 2011: 1-9.

Алгоритмы деления Теодора Джебелина URL: https://gmplib.org/manual/Exact-Division.html, https://gmplib.org/manual/References.html#References.

T. Jebelean. Using the Parallel Karatsuba Algorithmfor Long Integer Multiplication and Division. Euro-Par'97 Parallel Processing. LNCS Volume 1300, 1997, pp 1169-1172. URL: http://web-ng.info.uvt.ro/~tudor/Literature-Parallel/97-08.pdf.

K. Hasselström. (2003). Fast Division of Large Integers A Comparison of Algorithm. Master’s Thesis in Computer Science at the School of Computer Science and Engineering, Royal Institute of Technology, February. URL: http://www.treskal.com/kalle/exjobb/original-report.pdf.

Задірака В.К. Комп’ютерна арифметика багаторозрядних чисел // В.К. Задірака, О.С. Олексюк. — К.: 2003. — 264.

Задирака В.К., Кудин А.М. Анализ стойкости криптографических и стегано-графических систем на основе общей теории оптимальных алгоритмов, Journal of Qafgaz University. — N 30. —2010. —С. 49–58.

Downloads

Published

2015-03-18

Issue

Vol. 21 No. 1 (2015)

Section

Cryptology