everyone! As a beginner, I would like to ask you a question. The best algorithm known for cracking (done by anonymous snooper) this problem （Discrete logarithm problem of elliptic curve or ECDSA）is Pollard’s rho method, and takes about the square root of πp/2, where p is the modulus. My questions are: (1) Elliptical encryption (done by designer and sender) also takes time. Can this time also be expressed by modulus p? (2) After the other party receives the information, it needs to be verified. This verification (done by receiver of information) also takes time. Can the time for verification also be expressed by modulus? That is to say, can the above three kinds of time be put into a frame for comparison, and they are all compared with the parameters of elliptic curve (it is best to use modulus or order of Base point). My intention is to know which of these three times is the slowest and which is the fastest. But there is no doubt that the time to crack is definitely the slowest, and the time for encryption and verification is definitely much shorter. But how to quantify them? Is there any literature recommendation that compares them? It would be best to give a simple example. Thank you very much!
1 Answer
Let $n$ be the number of points in the curve group and $p$ the size of the field. The quoted estimate for Pollard $\rho$ is $\sqrt {\pi n/2}$ which is the number of elliptic curve group operations required. To sign a ECDSA message (assuming that you already have your key pair) is an elliptic curve scalar point multiplication which takes (using windowed double-and-add) $(1+\epsilon)\log n$ elliptic curve group operations. To verify is 2 elliptic curve scalar multiplications which is $(2+\epsilon)\log n$ elliptic curve group operations. If you have to generate a key pair, that adds another elliptic curve scalar multiplication.
The elliptic curve group operation will get harder with $p$ as well and the exact complexity is subject to a range of variant algorithms. An estimate of $O(\log^2p)$ for each elliptic curve group would not be hugely inaccurate though.
-
$\begingroup$ Almost. $N$ should be the cost of an elliptic curve group operation (which should be $O(\log^2 Z)$) rather than the order. Also you should have $T_{AT}=N\sqrt{\pi n/2}$. I'm also doing the mathematician thing of using $\epsilon$ to mean number that gets close to 0 for large $n$, in your example $\epsilon=1/4$ would work. I haven't explicitly checked your $T_{AT}$, but the numbers look right. $\endgroup$– Daniel SMar 9, 2021 at 12:13
-
$\begingroup$ 1) $n\approx Z$ is true for almost all curves in cryptographic use. The book should make it clear that $\sqrt{\pi n/2}$ is the expected number of steps needed in Pollard $\rho$ (e.g. in en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms introductory paragraph it quotes this many "steps"). Each step is a group operation and the cost $N$ will vary with the size of the group. 2) The cost of elliptic curve point multiplications can be read about here: en.wikipedia.org/wiki/… $\endgroup$– Daniel SMar 9, 2021 at 13:52
-
$\begingroup$ Thank you, Daniel. According to some literature, "If the data size of modular multiplication is n, and the complexity of one modular multiplication (MM) is
O(n^2logn), To sign a ECDSA message, there are 1 dot product operation, 1 modular inversion operation, and 2 modular multiplications. Nine MM equal 1 modular inversion, and the total operations are denoted as T, thenT=(logn+ 11)n^2. To verify there are 2 dot products, 1 modular inversion, and 2 MM, thenN=(2logn+ 11)n^2". Could you tell me why above are different from yours? Is it right? What is data size of modular? $\endgroup$ Mar 9, 2021 at 14:55 -
$\begingroup$ I think that the author got things a bit mixed up. The main cost is the elliptic curve point multiply which would take $O(n^3)$ operations in their notation, I assume that this is what they are calling the "dot product operation". There's also a constant factor as elliptic curve group operations use several modular multiplies each (perhaps 12 or so en.wikipedia.org/wiki/… ). The expressions should then be $T=(12n+11)n^2$ and $N=(24n+11)n^2$. The data size of the multiplication is $\log_2 Z$ in your notation or 256 in your example. $\endgroup$– Daniel SMar 9, 2021 at 18:16
-
$\begingroup$ Mine are right and their's are not, though it would be best to consult an independent expert in such circumstances. In my view the best comparator is to say that $T_v/T_{en}\sim 2$ and $T_{AT}/T_{en}\sim\sqrt{\pi n/2}/\log n$. $\endgroup$– Daniel SMar 9, 2021 at 19:38