Examination and implementation of the fast method for computing the order of elliptic curve
І.Д. Горбенко, Roman Hanzia · Eastern-European Journal of Enterprise Technologies · 2017
Present study provides detailed analysis of the theoretical and experimental complexity of methods for canonical lift of elliptic curves that are defined over the binary field. The SST, MSST and Harley methods were used in the research. Results of theoretical studies revealed that the fastest (by execution time) algorithm for computing the order of the curve is the Harley method. Present work gives the substantiation (approximately 10 seconds for 1024 bits) of this method and the possibility of its application for binary fields. By the data obtained, we constructed a program model of the examined methods for canonical lift of elliptic curves and computing the norm. The software model allowed us to conduct experimental analysis of the algorithms for canonical lift of elliptic curves. In present article we experimentally confirmed a quasi quadratic dependence of the field size, over which curve is defined, and the time required for its canonical lift. Based on the results received, it is possible to argue that at present the fastest method for canonical lift is the Harley method. Our work demonstrated that the given method might be employed to modify the Ukrainian standard of electronic digital signature.The relevance of research is related to the emergence of threats to the protection of information from the quantum cryptoanalysis for most modern asymmetric cryptosystems. However, modern cryptosystems should exist over the time that is necessary to find the candidates to replace them from the post-quantum cryptosystems. During such "transition period", classical cryptosystems should provide for the necessary level of stability, even under condition of constant extension of size in the system-wide parameters. The Ukrainian standard DSTU 4145–2002 has limitations on the size of system-wide parameters (up to 431 bits) and may not be able to account for a large reserve of stability. In addition, given the adoption of new standards for encryption and hash functions, in order to ensure the same level of security with the apparatus of elliptic curves, the latter must have parameters of size to 1024 bits.