Methods of extracting root with the residues from multi-bit numbers to meet the challenges of asymmetric cryptography

Authors

  • Степан Дмитриевич Винничук The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine
  • Александр Васильевич Корнейко The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine
  • Евгений Васильевич Максименко The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

DOI:

https://doi.org/10.18372/2410-7840.18.11095

Keywords:

factorization, asymmetric cryptography, square root, division with remainder, diagonal method, method "in the column", modified method, multi-bit numbers

Abstract

Currently asymptotically the fastest factorization methods of multi-bit sequences are methods based on the fundamental ratios of Fermat algorithm. One of the most complex operations in the factorization method of Fermat is a procedure of extracting the square root. Existing methods of extracting the roots are refer to the number of iterative and require the implementation the quite large number the most complex arithmetic operations of multiplication and division. This in turn significantly affects on their temporal assessment. One of the ways of improving the productivity of existing methods for extracting the square root would be using a direct calculation of root without using operations of multiplication or division large numbers. Offered a new method for calculating the square root without using multiplication and division large numbers, which is a modification of the method of extracting roots "in the column." Made a comparative analysis of the described modified method "in a column" with the existing diagonal method (method of Tereshchenko). Offered to use this method in the procedures for analysis of asymmetric cryptographic algorithms

Author Biographies

Степан Дмитриевич Винничук, The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

Dr. Science in Eng., Head of Science Department of The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

Александр Васильевич Корнейко, The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

Ph.D. in Eng., Professor, Scientific Secretary of The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

Евгений Васильевич Максименко, The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

Doctoral Student of The G. Pukhov Institute for Energy Modeling Engineering of The National Academy Sciences of Ukraine

References

Корнейко А.В. Анализ известных вычислительных методов факторизации многоразрядных чисел / А.В. Корнейко, А.В. Жилин // Моделювання та інформаційні технології: Збірник наукових праць. – Вип. 61. – К.: ІПМЕ, 2011. – С. 3-13

Ишмухаметов Ш.Т. Методы факторизации натуральных чисел: учебное пособие / Ш.Т. Ишмухаметов. – Казань: Казан. ун-т, 2011. – 190 с.

Нестеренко А.Ю. Теоретико-числовые методы в криптографии: учебное пособие / А.Ю. Нестеренко. – М.: МГИЭМ, 2012. – 224 с.

Горбенко І.Д. Прикладна криптологія : монографія / І.Д. Горбенко, Ю.І. Горбенко. Видання 2-ге. – Харків: Форт, 2012. – 878 с.

Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – 2-е. – М.: Вильямс, 2005. – 1296 с.

Дональд Э. Кнут Искусство программирования. Том 2. – М.: Мир, 1979. – 727 c.

Square Root algorithm for C. [Электронный ресурс]. – Режим доступа: http://www. codeproject.com/Articles/570700/ SquareplusRootplusalgorithmplusforplusC.

Best Square Root Method. Algorithm. Function. [Электронный ресурс]. – Режим доступа: http://www.codeproject.com/Articles/69941/ Best-Square-Root-Method-Algorithm-Function-Precisi.

Терещенко А.Н. Быстрое вычисление квадратного и кубического корней без использования операций умножения и деления // Искусственный интеллект. – 2006. – Вып. 3. – С. 670-680.

Downloads

Published

2016-12-12

How to Cite

Винничук, С. Д., Корнейко, А. В., & Максименко, Е. В. (2016). Methods of extracting root with the residues from multi-bit numbers to meet the challenges of asymmetric cryptography. Ukrainian Information Security Research Journal, 18(4), 336–345. https://doi.org/10.18372/2410-7840.18.11095

Issue

Vol. 18 No. 4 (2016)

Section

Articles

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.