Substantiation of correctness and advantages of Lenstra factorization method on Edwards curves
Journal Title: Восточно-Европейский журнал передовых технологий - Year 2018, Vol 6, Issue 4
Abstract
<p>The factorization problem, which is the basis for many classical asymmetric cryptosystems (RSA, Rabin, and others) and a cryptographically strong generator of pseudo-random sequences (PBS), has been investigated in this paper. The methods that served as prototypes for the Lenstra method were described, the method for factorization of numbers, which is analogous to the Lenstra method on Edwards curves, has been proposed. To substantiate the correctness of the method, an appropriate mathematical apparatus was developed. In addition, an analog of the Lenstra method on Edwards curves was constructed with the use of the presented apparatus; the appropriate algorithm for the factorization of numbers was designed. The correctness of the method and correctness of the algorithm operation were substantiated mathematically; the top analytical estimates of its performance speed, as well as the lower estimates of success probability, have been strictly proved. The advantages of the developed method in comparison with the classical Lenstra method, which applies elliptic curves in the Weierstrass form, were presented and strictly substantiated. A comparative analysis of the new and the classical algorithms was performed.</p><p>Results of the research provided a strict proof that the new algorithm on full Edwards curves, in comparison with the classic one, has some advantages in terms of performance speed, by about 1.5 times. The presented experimental results show that the performance speed increases even larger (by up to 30 per cent) in case the twisted and quadratic curves are used instead of full Edwards curves. It was shown that the assessment of probability of success of the new method increases due to the emergence of new conditions that lead to success of the algorithm that are not satisfied for the classical Lenstra algorithm on Weierstrass curves.</p>The obtained results make it possible to decrease the time required for solving the problem on factorization by approximately 1.5 times, and thus, enable the faster breaking of cryptosystems whose stability is based on this problem
Authors and Affiliations
Lyudmyla Kovalchuk, Oleksij Bespalov, Nataliia Kuchynska, Polina Seliukh, Artem Zhylin, Vasyl Tsurkan
Keywords
Related Articles
- EP ID EP528265
- DOI 10.15587/1729-4061.2018.151090
- Views 59
- Downloads 0
Geometrical synthesis of spatial six-link guiding mechanisms
<p><span lang="EN-GB">The study considers problems of geometric synthesis of spatial hinge-lever six-link mechanisms with linear displacement of the final link performing the guiding function. The variants of arranging t...
The use of golden flax seeds and oats sourbread in the production of wheat bread
<p>In the course of development of bakery products enriched with physiologically active substances of non-traditional types of raw materials, cereal and oil-bearing crops enjoy popularity. The actual direction can be a c...
Development of the model of the antagonistic agents behavior under a cyber conflict
<p>The results of the development of the model of the antagonistic agents behavior in a cyber conflict are presented. It is shown that the resulting model can be used to analyze investment processes in security systems,...
Designing a combined device for determining the place of arc discharge
<p>We determined factors that arise during an arc discharge and detected possibility of their use to accelerate protection against arc closure. This enables creation of a combined device for accurate determination of an...
Research into parameters of magnetic treatment to modify the dispersefilled epoxy composite materials
<p>Improving the operational properties of epoxy composites makes it possible to extend the scope of their application. One of the techniques to enhance the strength and durability of epoxy composites is the use of magne...