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 57
- Downloads 0
Prediction of specific electrical resistivity of polymeric composites based on carbon fabrics
<p class="a">We have proposed an improved approach to forecasting electrical resistivity of composite materials based on carbon fabrics by using a finite element method that takes into consideration a deformation of the...
Study into the rolling of a double-layered powdered core in a metallic sheath
<p>We have developed an analytical model of the stressed-strained state of the two-layered powdered core in a metal sheath in the deformation zone when fabricating a composite material by rolling. Based on the constructe...
Development of a system for graphic captcha systems recognition using competing cellular automata
<p>Peculiarities of the use of competing cellular automata for problems of recognition of complex captcha systems have been explored. For this purpose, the concept of competing cellular automata has been introduced and a...
Forecasting the estimated time of arrival for a cargo dispatch delivered by a freight train along a railway section
<p>This paper reports a method for predicting the expected time of arrival (ETA) of a cargo dispatch taking into consideration determining the duration at which a freight train travels along a railroad section where trai...
Selection of new working fluids for a heat-using compression refrigerating machine with the block «turbine- compressor»
<p>The compression heat-using refrigerating machines operating in the Chistiakov-Plotnikov cycle use recycled waste heat of power machines as primary energy for producing cold of various temperature potentials thus savin...