The New Modified Methodology to Solve ECDLP Based on Brute Force Attack

摘要

Elliptic curve cryptography (ECC) is one of public key cryptography suitable for the limited storages and low power devices. The reason is that ECC has the same security level with other public key cryptographies, although bits length is very small. However, ECC is based on Elliptic Curve Discrete Logarithm Problem (ECDLP) that is very difficult to be solved. At present, many algorithms were introduced to solve the problem. Nevertheless, the efficiency of each algorithm is based on the characteristic of k, Q= kP, when Q and P are known points on the curve, and type of curve. Deeply, brute force attack is one of techniques to solve ECDLP. This algorithm has very high performance when k is small. However, to find k, 2P, 3P, 4P, ..., (k - 1)P and kP must be computed. Thus, numbers of inversion process are k - 1. Moreover, for traditional brute force attack, y's points must be computed all loops computation. In this paper, the new method based on brute force attack, is called Resolving Elliptic Curve Discrete Logarithm Problem by Decreasing Inversion Processes and Finding only x's points (RIX-ECDLP), is proposed. The key is to remove some inversion processes and y's points out of the computation. In fact, every two point additions can be done with only one inversion process. The experimental results show that RIX-ECDLP can reduce time about 10-20% based on size of k and prime number.