ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 3. Vol. 26. 2020

DOI: 10.17587/it.26.159-168

M. A. Cherepniov, Ph. D., Professor, e-mail: cherepniov@gmail.com, "Kontzern "Avtomatika", S. S. Gracheva, Cand. Sci. (Tech.), Associate Professor, Department of Statistics and Data Analysis, e-mail: statgracheva@mail.ru, National Research University Higher School of Economics

Solution of the Diffie-Hellman Problem on Some Elliptic Curves Satisfying GOST 34.10—2018

This article is devoted to cryptanalysis of the often used Diffie-Hellman scheme of public key distribution. Starting with the article Menezes-Okamoto-Vanstone, the idea of which was previously stated in the works of I. Semaev, considerable interest from the point of view of attacking crypto-protokols on elliptic curves, began to acquire the degree of expansion or MOV-degree. In English literature, this parameter (hereinafter k) is called "embedding degree". We mean the extension of the coefficient field of the elliptic curve, which contains all the points of the original Prime order p. The random value of this parameter approaches the value of p, which results in the length of the entry of the element of the corresponding extension not much less than p×logp. In the standard GOST 34.10—2018, this parameter is proposed to take more than 31, which allows you to use this extension, since the length of the record of its elements is not more than k×logp. In this paper, we propose a polynomial algorithm for solving the recognition and ordinary Diffie-Hellman problem, effective for some such curves. This means that public key distribution schemes constructed using these curves are insecure. The proposed algorithm is based on the choice of such a pairing, which is nontrivially defined at all points of order p and can be represented as a rational function of relatively small degree. A reduction of the Diffie-Hellman problem to such an address is obtained by Verheul. The proposed construction is based on the non-reduced Ate pairing. Proposed new mechanisms to extend the scope of the considered pairing with the Frobenius automorphism and the reduction of inversion for the second argument (lying in the extension field of coefficients of the curve) to the solution of a system of linear equations with the subsequent search of the roots of polynomials of small degree. Estimates for the probability of solvability of the equations obtained by taking a random representative of an adjacent class representing the pairing value are presented.
Keywords: public key distribution scheme, elliptic curves, Diffie-Hellman problem, Tate pairing, Ate pairing, Frobenius automorphism

P. 159–168

To the contents